[PATCH] Use RPO order for domwalk dominator children sort

Richard Biener rguenther@suse.de
Tue Oct 18 14:04:00 GMT 2016


For

extern void baz ();
extern void boo ();
extern void bla ();
int a[100];
void foo (int n)
{
  for (int j = 0; j < n; ++j)
    {
      if (a[j+5])
        {
          if (a[j])
            break;
          baz ();
        }
      else
        bla ();
      boo ();
    }
}

we happen to visit BBs in an unfortunate order so that we do not
have all predecessors visited when visiting the BB of boo().  This
is because domwalk uses a postorder on the inverted graph to
order dominator children -- that doesn't play well with loops
(as we've figured elsewhere before).  The following makes us use
RPO order instead.

This should help EVRP and DOM.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

Richard.

2016-10-18  Richard Biener  <rguenther@suse.de>

	* domwalk.c (dom_walker::walk): Use RPO order.

Index: gcc/domwalk.c
===================================================================
--- gcc/domwalk.c	(revision 241300)
+++ gcc/domwalk.c	(working copy)
@@ -243,7 +243,7 @@ dom_walker::walk (basic_block bb)
   if (m_dom_direction == CDI_DOMINATORS)
     {
       postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
-      postorder_num = inverted_post_order_compute (postorder);
+      postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
       bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
       for (int i = 0; i < postorder_num; ++i)
 	bb_postorder[postorder[i]] = i;



More information about the Gcc-patches mailing list