Re: [PATCH] Use RPO order for domwalk dominator children sort

[Richard Biener]

On Thu, 20 Oct 2016, Andreas Schwab wrote:

> On Okt 18 2016, Richard Biener  wrote:
> 
> > * domwalk.c (dom_walker::walk): Use RPO order.
> 
> FAIL: gcc.dg/graphite/pr35356-1.c scan-tree-dump graphite "if \\(P_8 >= P_9 
> \\+ 1 && P_9 >= 0\\) \\{"

Fixed.

2016-10-20  Richard Biener  

* gcc.dg/graphite/pr35356-1.c: Update.

Index: testsuite/gcc.dg/graphite/pr35356-1.c
===
--- testsuite/gcc.dg/graphite/pr35356-1.c   (revision 241363)
+++ testsuite/gcc.dg/graphite/pr35356-1.c   (working copy)
@@ -34,4 +34,4 @@ if (n >= k + 1 && k >= 0) {
 
 */
 
-/* { dg-final { scan-tree-dump "if \\\(P_8 >= P_9 \\\+ 1 && P_9 >= 0\\\) \\\{" 
"graphite" } } */
+/* { dg-final { scan-tree-dump "if \\\(P_8 >= P_11 \\\+ 1 && P_11 >= 0\\\) 
\\\{" "graphite" } } */

Re: [PATCH] Use RPO order for domwalk dominator children sort

[Andreas Schwab]

On Okt 18 2016, Richard Biener  wrote:

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

FAIL: gcc.dg/graphite/pr35356-1.c scan-tree-dump graphite "if \\(P_8 >= P_9 \\+ 
1 && P_9 >= 0\\) \\{"

Andreas.

-- 
Andreas Schwab, SUSE Labs, sch...@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

[PATCH] Use RPO order for domwalk dominator children sort

[Richard Biener]

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  

* 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;