[PATCH, PR68976] Use reaching def phi arg in sese_add_exit_phis_edge

[PATCH, PR68976] Use reaching def phi arg in sese_add_exit_phis_edge

[Tom de Vries]

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

Hi,

Consider testcase test.c:
...
int kw = -1, hv = -1, ju;
int mc[1];

void
foo (void)
{
   for (; kw; ++kw)
     for (; hv; ++hv)
       for (ju = 0; ju < 2; ++ju)
     mc[kw+1] = mc[0];
}
...

When compiled with -O2 -fgraphite-identity, we run into an ICE:
...
test.c: In function ‘foo’:
test.c:5:1: internal compiler error: Segmentation fault
  foo (void)
  ^~~

0xefb0cc crash_signal
     src/gcc/toplev.c:334
0xf62761 ssa_default_def(function*, tree_node*)
     src/gcc/tree-dfa.c:305
0xf62b08 get_or_create_ssa_default_def(function*, tree_node*)
     src/gcc/tree-dfa.c:357
0xfa9a21 get_reaching_def
     src/gcc/tree-into-ssa.c:1168
0xfab8b4 rewrite_update_phi_arguments
     src/gcc/tree-into-ssa.c:2017
0xfabd49 rewrite_update_dom_walker::before_dom_children(basic_block_def*)
     src/gcc/tree-into-ssa.c:2137
0x1c3a9a0 dom_walker::walk(basic_block_def*)
     src/gcc/domwalk.c:265
0xfabe35 rewrite_blocks
     src/gcc/tree-into-ssa.c:2194
0xfaeb45 update_ssa(unsigned int)
     src/gcc/tree-into-ssa.c:3356
0x1c75308 graphite_regenerate_ast_isl(scop*)
     src/gcc/graphite-isl-ast-to-gimple.c:3319
0x1c6c572 graphite_transform_loops()
     src/gcc/graphite.c:329
0x1c6c5f6 graphite_transforms
     src/gcc/graphite.c:356
0x1c6c719 execute
     src/gcc/graphite.c:433
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.
...

The scenario leading up to the ICE is as follows:

Before scop detection, we have bb 16, jumping to either bb 17 or bb 18, 
in which _6 and _24 are defined:
...
   <bb 16>:
   ...
   if (hv_lsm.8_23 != 0)
     goto <bb 18>;
   else
     goto <bb 17>;

   <bb 17>:
   _6 = kw.0_30 + 1;
   goto <bb 8>;

   <bb 18>:
   _24 = kw.0_30 + 1;
   goto <bb 4>;
...

And bb 8, were we join _6 and _24 in a phi:
...
   <bb 8>:
   # prephitmp_7 = PHI <_24(7), _6(17)>
   ...
...

BB 18 is a preheader block for a loop with exit edge bb 7 -> bb 8.

During scop detection/canonicalize_loop_closed_ssa_form, an exit phi is 
introduced in the loop for _24:
...
   <bb 21>:
   # _58 = PHI <_24(22)>
...
Note that _24 is not defined in the loop, but before it. AFAIU the 
header comment of canonicalize_loop_closed_ssa_form, this phi is not 
needed. That might be the root cause of the bug, but I'm not sure, so I 
proceed here assuming that's not the case.

After the introduction of the exit phi, the join phi looks like:
...
   <bb 8>:
   # prephitmp_7 = PHI <_58(21), _6(17)>
...

After scop detection, we enter graphite_regenerate_ast_isl with region:
...
(gdb) p region.region.entry.src.index
$2 = 18
(gdb) p region.region.entry.dest.index
$3 = 4
(gdb) p region.region.exit.src.index
$4 = 21
(gdb) p region.region.exit.dest.index
$5 = 8
...
In other words, the loop with header block 4 + loop exit block 21.

In graphite_regenerate_ast_isl, we move the region into a condition:
...
if (1)
   A; /* generate graphite code here.  */
else
   REGION;
...
Consequently, the def _58 (defined in the region) no longer dominates 
the use in the join phi.

An empty condition join block is introduced:
...
   <bb 25>:
...

And in sese_insert_phis_for_liveouts, we introduce a new phi, to join 
the values of both side of the condition:
...
   <bb 25>:
   # _22 = PHI <_58(28), _58(21)>
...
An ssa rename mapping is introduced from _58 to _22, such that once we 
do update_ssa, the join phi in bb 8 will use _22 instead of _58.

For the new phi in bb 25, the phi edge coming from region has the def in 
the region dominating the use in the phi.

For the other edge (coming from A), that's not the case. That does not 
necessary result in an ICE. Usually, there's a region rename (with 
corresponding rename in the ssa name mapping) registered that gives the 
corresponding value in A, and update_ssa manages to fill in the correct 
values.

In the case of this PR, there's no such rename, we run into the ICE.

The patch fixes the PR detecting the case that there's no rename 
scheduled, and walking single-arg phis until we find a def that 
dominates the use in the phi (in the case of this test-case it's the def 
of _24). [ I'm not sure this the right fix in the right place though. ]

Bootstrapped and reg-tested on x86_64.

OK for trunk?

Thanks,
- Tom


[-- Attachment #2: 0001-Use-reaching-def-phi-arg-in-sese_add_exit_phis_edge.patch --]
[-- Type: text/x-patch, Size: 2947 bytes --]

Use reaching def phi arg in sese_add_exit_phis_edge

2016-01-15  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/68976
	* sese.c (sese_add_exit_phis_edge): Find phi arg for true_edge with
	reaching def, if not renamed.
	(sese_insert_phis_for_liveouts): Call sese_add_exit_phis_edge with extra
	arg.
---
 gcc/sese.c                              | 34 +++++++++++++++++++++++++++++----
 gcc/testsuite/gcc.dg/graphite/pr68976.c | 13 +++++++++++++
 2 files changed, 43 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/pr68976.c

diff --git a/gcc/sese.c b/gcc/sese.c
index 59d2770..27287e9 100644
--- a/gcc/sese.c
+++ b/gcc/sese.c
@@ -270,15 +270,41 @@ free_sese_info (sese_info_p region)
   XDELETE (region);
 }
 
-/* Add exit phis for USE on EXIT.  */
+/* Add exit phis for USE on EXIT in REGION.  */
 
 static void
-sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
+sese_add_exit_phis_edge (sese_info_p region, basic_block exit, tree use,
+			 edge false_e, edge true_e)
 {
   gphi *phi = create_phi_node (NULL_TREE, exit);
   create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
-  add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
+
+  vec <tree> *renames = region->rename_map->get (use);
+  bool use_renamed = renames && !renames->is_empty ();
+
+  if (use_renamed)
+    add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
+  else
+    {
+      /* Handle the case that use is defined by a PHI, which is just a copy, and
+	 the src of the copy can be used as argument for true_e.  */
+      tree arg = use;
+      while (true)
+	{
+	  if (TREE_CODE (arg) != SSA_NAME)
+	    break;
+	  if (dominated_by_p (CDI_DOMINATORS, true_e->src,
+			      gimple_bb (SSA_NAME_DEF_STMT (arg))))
+	    break;
+	  gcc_assert (gimple_code (SSA_NAME_DEF_STMT (arg)) == GIMPLE_PHI);
+	  gphi *use_def = as_a <gphi *> (SSA_NAME_DEF_STMT (arg));
+	  gcc_assert (gimple_phi_num_args (use_def) == 1);
+	  arg = gimple_phi_arg_def (use_def, 0);
+	}
+      add_phi_arg (phi, arg, true_e, UNKNOWN_LOCATION);
+    }
+
   update_stmt (phi);
 }
 
@@ -305,7 +331,7 @@ sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
 
   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
     if (!virtual_operand_p (ssa_name (i)))
-      sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
+      sese_add_exit_phis_edge (region, bb, ssa_name (i), false_e, true_e);
 
   BITMAP_FREE (liveouts);
 }
diff --git a/gcc/testsuite/gcc.dg/graphite/pr68976.c b/gcc/testsuite/gcc.dg/graphite/pr68976.c
new file mode 100644
index 0000000..165a740
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/pr68976.c
@@ -0,0 +1,13 @@
+/* { dg-options "-O2 -fgraphite-identity" } */
+
+int kw = -1, hv = -1, ju;
+int mc[1];
+
+void
+foo (void)
+{
+  for (; kw; ++kw)
+    for (; hv; ++hv)
+      for (ju = 0; ju < 2; ++ju)
+	mc[kw+1] = mc[0];
+}
-- 
1.9.1

Re: [PATCH, PR68976] Use reaching def phi arg in sese_add_exit_phis_edge

[Sebastian Pop]

On Fri, Jan 15, 2016 at 7:58 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> During scop detection/canonicalize_loop_closed_ssa_form, an exit phi is
> introduced in the loop for _24:
> ...
>   <bb 21>:
>   # _58 = PHI <_24(22)>
> ...
> Note that _24 is not defined in the loop, but before it. AFAIU the header
> comment of canonicalize_loop_closed_ssa_form, this phi is not needed. That
> might be the root cause of the bug,

I think that may be the problem, as it is invariant in the loops, so
it is considered to be a parameter of the scop.
Let me see if we could avoid adding that phi node in the first place.

Re: [PATCH, PR68976] Use reaching def phi arg in sese_add_exit_phis_edge

[Sebastian Pop]

On Fri, Jan 15, 2016 at 11:19 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Fri, Jan 15, 2016 at 7:58 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> During scop detection/canonicalize_loop_closed_ssa_form, an exit phi is
>> introduced in the loop for _24:
>> ...
>>   <bb 21>:
>>   # _58 = PHI <_24(22)>
>> ...
>> Note that _24 is not defined in the loop, but before it. AFAIU the header
>> comment of canonicalize_loop_closed_ssa_form, this phi is not needed. That
>> might be the root cause of the bug,
>
> I think that may be the problem, as it is invariant in the loops, so
> it is considered to be a parameter of the scop.
> Let me see if we could avoid adding that phi node in the first place.

I just sent out a patch that implements this.
Thanks Tom for pointing out the issue!