public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH, MELT] add dominance functions
@ 2011-05-18 20:12 Pierre Vittet
  2011-05-19 10:28 ` Basile Starynkevitch
  0 siblings, 1 reply; 6+ messages in thread
From: Pierre Vittet @ 2011-05-18 20:12 UTC (permalink / raw)
  To: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 1845 bytes --]

Hello,

I have written a patch to allow the use of the GCC dominance functions 
into MELT.

This is made in order to abstract the use of calculate_dominance_info 
and free_dominance_info:
     If the user use one of the MELT dominance related functions, it 
will only call calculate_dominance_info and register a call to 
free_dominance_info (at the end of the MELT pass) if the dominance info 
were not previously calculated.

The idea is :
     - dominance info were already calculated (in a previous pass):
         -we can use dominance info and at the end of pass, no call is 
made to free_dominance_info (as we expect a next pass to use dominance 
info and to free only when necessary).

     -dominance info were not already calculated:
         -We first compute dominance info, use them during the pass and 
free them at the end of the plugin pass (as we don't expect a next pass 
to use it).

Unsafe functions are only for internal use and so are not exported.

I have compiled GCC MELT with the patch and successfully test the functions.


Changelog:
2011-05-17  Pierre Vittet <piervit@pvittet.com>

     * melt/xtramelt-ana-base.melt
     (is_dominance_info_available, is_post_dominance_info_available,
     calculate_dominance_info_unsafe,
     calculate_post_dominance_info_unsafe,
     free_dominance_info, free_post_dominance_info,
     calculate_dominance_info,
     calculate_post_dominance_info, debug_dominance_info,
     debug_post_dominance_info, get_immediate_dominator_unsafe,
     get_immediate_dominator, get_immediate_post_dominator_unsafe,
     get_immediate_post_dominator, dominated_by_other_unsafe,
     dominated_by_other, post_dominated_by_other_unsafe,
     post_dominated_by_other, foreach_dominated_unsafe,
     dominated_by_bb_iterator): Add primitives, functions, iterators for
     using dominance info.



[-- Attachment #2: add_dominance_function.diff --]
[-- Type: text/plain, Size: 8956 bytes --]

Index: gcc/melt/xtramelt-ana-base.melt
===================================================================
--- gcc/melt/xtramelt-ana-base.melt	(revision 173832)
+++ gcc/melt/xtramelt-ana-base.melt	(working copy)
@@ -1910,6 +1910,242 @@
 (defprimitive basicblock_nth_succ_edge  (:basic_block bb :long ix) :edge
   #{(($bb && $ix>=0 && $ix<EDGE_COUNT($bb->succs))?EDGE_SUCC($bb,$ix):NULL)}#)
 
+;Primitives concerning dominance in basic_blocks
+;those functions mainly come from gcc/dominance.c
+
+(defprimitive is_dominance_info_available () :long
+  :doc #{Check if dominance info are already calculated.
+        User normally doesn't have to call this primitive, as MELT functions
+        check if there is a need to use this.
+        }#
+  #{dom_info_available_p(CDI_DOMINATORS)}#
+)
+
+(defprimitive is_post_dominance_info_available () :long
+  :doc #{Check if post dominance info are already calculated.
+        User normally doesn't have to call this primitive, as MELT functions
+        check if there is a need to use this.
+       }#
+  #{dom_info_available_p(CDI_POST_DOMINATORS)}#
+)
+
+(defprimitive calculate_dominance_info_unsafe() :void
+  :doc #{This primitive is internaly called, user doesn't need it.
+    Build the struct containing dominance info.
+    This struct is necessary to use others dominance related function.
+    This function is unsafe because it does not register any future call to
+    free_dominance_info. 
+    }#
+  #{calculate_dominance_info(CDI_DOMINATORS)}#
+)
+
+(defprimitive calculate_post_dominance_info_unsafe () :void
+  :doc #{This primitive is internaly called, user doesn't need it.
+    Build the struct containing post dominance info.
+    This struct is necessary to use other dominance related function.
+    This function is unsafe because it does not register any future call to
+    free_dominance_info. 
+    }#
+  #{calculate_dominance_info(CDI_POST_DOMINATORS)}#
+)
+
+(defprimitive free_dominance_info () :void
+  :doc #{This primitive is internaly called, user doesn't need it.
+  Clear dominance info if they have been allocated.
+  }#
+  #{free_dominance_info(CDI_DOMINATORS)}#
+)
+
+(defprimitive free_post_dominance_info () :void
+  :doc #{This primitive is internaly called, user doesn't need it.
+  Clear post dominance info if they have been allocated.
+  }#
+  #{free_dominance_info(CDI_POST_DOMINATORS)}#
+)
+
+(defun calculate_dominance_info()
+  :doc #{This primitive is internaly called, user doesn't need it.
+  Build the struct containing dominance info.
+  This struct is necessary to use other dominance related info.
+  It place a call to free dominance info when pass is finished if it is
+  necessary.
+  }#
+  (if (is_dominance_info_available)
+    () ;; do nothing
+    (progn ;; else calculate dom and ask to free them at end of pass
+      (calculate_dominance_info_unsafe)
+      (at_end_melt_pass_first free_dominance_info)
+    ))
+)
+
+(defun calculate_post_dominance_info () 
+  :doc #{This primitive is internaly called, user doesn't need it
+  Build the struct containing post dominance info.
+  This struct is necessary to use other post dominance related info.
+  It place a call to free dominance info when pass is finished if it is
+  necessary.
+  }#
+  (if (is_post_dominance_info_available)
+    ()  ;; do nothing
+    (progn ;; else calculate dom and ask to free them at end of pass
+      (calculate_post_dominance_info)
+      (at_end_melt_pass_first free_post_dominance_info)
+    ))
+)
+
+(defun debug_dominance_info () 
+  :doc#{Print to stderr all dominance relation, in the format "bb1->bb2".}#
+  (calculate_dominance_info)
+  (each_bb_current_fun () (:basic_block curbb)
+    (let ( (:basic_block dombb (basicblock_content (get_immediate_dominator
+                                  (make_basicblock discr_basic_block curbb)))))
+      (if dombb 
+        (code_chunk debugpostdomchunk 
+        #{/*$DEBUGPOSTDOMCHUNK*/
+        fprintf (stderr, "%i dominated by %i\n", $CURBB->index, $DOMBB->index);
+        }#
+      ))
+    )
+  )
+)
+
+(defun debug_post_dominance_info ()
+  :doc#{Print to stderr all post dominance relation, in the format
+  "bb1->bb2".}#
+  (calculate_post_dominance_info) 
+  (each_bb_current_fun () (:basic_block curbb)
+    (let ( (:basic_block dombb (basicblock_content 
+              (get_immediate_post_dominator (make_basicblock discr_basic_block
+                                                                    curbb)))))
+      (if dombb 
+        (code_chunk debugpostdomchunk 
+        #{/*$DEBUGPOSTDOMCHUNK*/
+        fprintf (stderr, "%i dominated by %i\n", $CURBB->index, $DOMBB->index);
+        }#
+      ))
+    )
+  )
+)
+
+(defprimitive get_immediate_dominator_unsafe(:basic_block bb) :basic_block
+  :doc#{It doesn't check that dominance info are build, use
+    get_immediate_dominator instead.}#
+  #{($bb) ? get_immediate_dominator (CDI_DOMINATORS, $bb) : NULL}#
+)
+
+(defun get_immediate_dominator(bb) 
+ :doc#{Return the next immediate dominator of the basic_block $BB as a MELT
+value.}#
+  (if (is_basicblock bb)
+  (progn
+    (calculate_dominance_info) 
+    (return (make_basicblock discr_basic_block 
+      (get_immediate_dominator_unsafe (basicblock_content bb))))))
+)
+
+(defprimitive get_immediate_post_dominator_unsafe(:basic_block bb) :basic_block
+  :doc#{It doesn't check that post_dominance info are build, use
+    get_immediate_post_dominator instead.}#
+  #{($bb) ? get_immediate_dominator (CDI_POST_DOMINATORS, $bb) : NULL}#
+)
+
+(defun get_immediate_post_dominator(bb) 
+ :doc#{Return the next immediate post dominator of the basic_block $BB as a
+MELT value.}#
+ (if (is_basicblock bb)
+ (progn
+ (calculate_post_dominance_info) 
+  (return (make_basicblock discr_basic_block 
+    (get_immediate_post_dominator_unsafe (basicblock_content bb))))))
+)
+
+(defprimitive 
+  dominated_by_other_unsafe(:basic_block bbA :basic_block bbB) :long
+  :doc#{It doesn't check that dominance info are build, use
+    dominated_by_other instead.}#
+  #{ (($bbA) && ($bbB)) ?
+      dominated_by_p (CDI_DOMINATORS, $bbA, $bbB) 
+      : 0 
+  }#
+)
+
+(defun dominated_by_other(bbA bbB)
+  :doc#{true if basic_block $BBA is dominated by basic_block $BBB.}#
+  (if (and (is_basicblock bbA) (is_basicblock bbB))
+  (progn
+    (calculate_dominance_info) 
+    (if (dominated_by_other_unsafe (basicblock_content bbA) 
+                                   (basicblock_content bbB))
+      (return :true)
+    )))
+)
+
+(defprimitive 
+  post_dominated_by_other_unsafe(:basic_block bbA :basic_block bbB) :long
+  :doc#{It doesn't check that post_dominance info are build, use
+    post_dominated_by_other instead.}#
+  #{ (($bbA) && ($bbB)) ?
+      dominated_by_p (CDI_POST_DOMINATORS, $bbA, $bbB) 
+      : 0 
+  }#
+)
+
+(defun post_dominated_by_other(bbA bbB)
+  :doc#{true if basic_block $BBA is post dominated by basic_block BBB.}#
+  (if (and (is_basicblock bbA) (is_basicblock bbB))
+  (progn
+    (calculate_post_dominance_info) 
+    (if (post_dominated_by_other_unsafe (basicblock_content bbA) 
+                                   (basicblock_content bbB))
+      (return :true)
+    )))
+)
+
+(defciterator foreach_dominated_unsafe
+  (:basic_block dominator_bb)
+  ebbdomd
+  (:basic_block dominated_bb)
+  #{
+    /* $EBBDOMD before+ */
+
+    VEC (basic_block, heap)*  $EBBDOMD#_bbvec = 0;
+    unsigned int $EBBDOMD#_ix = 0;
+    basic_block $EBBDOMD#_bb = 0;
+
+    if($DOMINATOR_BB){
+      $EBBDOMD#_bbvec = get_dominated_by(CDI_DOMINATORS, $DOMINATOR_BB);
+      if($EBBDOMD#_bbvec){
+        FOR_EACH_VEC_ELT (basic_block, $EBBDOMD#_bbvec, 
+          $EBBDOMD#_ix, $EBBDOMD#_bb){
+          if (!$EBBDOMD#_ix)
+            continue;
+          $DOMINATED_BB = $EBBDOMD#_bb;
+     /*$EBBDOMD before- */}#
+      ;;after expansion
+  #{/*$EBBDOMD after+ */
+          }
+      }}
+    VEC_free (basic_block, heap, $EBBDOMD#_bbvec);
+    $EBBDOMD#_bbvec = 0;
+    $EBBDOMD#_bb = 0;
+    /* $EBBDOMD after- */}#
+)
+
+;;; 
+(defun dominated_by_bb_iterator (f data bb)
+  :doc #{run function $F on every basicblocks dominated by $BB with $DATA as
+  first parameters and ending with the dominated basicblock as last
+  parameters.
+  }#
+  (calculate_dominance_info)
+  (foreach_dominated_unsafe
+    ((basicblock_content bb))
+    (:basic_block dominated_bb)
+    (f data dominated_bb)
+  )
+)
+
+
 ;;;;
 (defprimitive null_gimpleseq () :gimple_seq #{((gimple_seq)0)}#)
 ;;;;;;;;;;;;;;;;
@@ -2931,6 +3167,17 @@ and discriminant $DIS, usually $DISCR_MIXED_LOCATI
  basicblock_nb_succ
  basicblock_phinodes
  basicblock_single_succ 
+ debug_dominance_info
+ debug_post_dominance_info
+ get_immediate_dominator
+ get_immediate_post_dominator
+ dominated_by_other
+ post_dominated_by_other
+ dominated_by_bb_iterator
+ get_immediate_dominator
+ get_immediate_post_dominator
+ dominated_by_other
+ post_dominated_by_other
  cfun_decl
  cfun_gimple_body
  cfun_has_cfg

^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-05-22 15:27 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-05-18 20:12 [PATCH, MELT] add dominance functions Pierre Vittet
2011-05-19 10:28 ` Basile Starynkevitch
2011-05-20 11:47   ` Pierre Vittet
2011-05-20 14:09     ` Basile Starynkevitch
2011-05-22 18:01       ` Gerald Pfeifer
2011-05-22 18:49         ` Basile Starynkevitch

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).