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 <pier...@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.
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