[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

Richard Biener  changed:

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |FIXED

--- Comment #8 from Richard Biener  ---
Fixed.

[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

--- Comment #7 from Richard Biener  ---
Author: rguenth
Date: Thu Jan 21 08:50:38 2016
New Revision: 232666

URL: https://gcc.gnu.org/viewcvs?rev=232666=gcc=rev
Log:
2016-01-21  Richard Biener  

PR tree-optimization/69378
* tree-ssa-sccvn.c (dominated_by_p_w_unex): New function.
(set_ssa_val_to): Use it for dominance checks taking into
account not executable edges.

Modified:
trunk/gcc/ChangeLog
trunk/gcc/tree-ssa-sccvn.c

[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

Richard Biener  changed:

   What|Removed |Added

 Status|UNCONFIRMED |ASSIGNED
   Last reconfirmed||2016-01-20
 CC|rguenther at suse dot de   |
   Assignee|unassigned at gcc dot gnu.org  |rguenth at gcc dot 
gnu.org
 Blocks||69117
 Ever confirmed|0   |1
Summary|FAIL:   |[6 Regression] FAIL:
   |g++.dg/tree-ssa/pr61034.C   |g++.dg/tree-ssa/pr61034.C
   Target Milestone|--- |6.0

--- Comment #1 from Richard Biener  ---
Did r232603 fix it by chance?


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69117
[Bug 69117] [6 Regression] wrong code at -O1 -fstrict-aliasing

[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[thopre01 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

--- Comment #2 from Thomas Preud'homme  ---
Sadly no, it didn't.

[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[thopre01 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

--- Comment #6 from Thomas Preud'homme  ---
This patch works for me on this testcase.

[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

--- Comment #3 from Richard Biener  ---
Ok, difference is in PRE:

--- a/pr61034.C.123t.pre2016-01-20 10:27:14.052404275 +0100
+++ b/pr61034.C.123t.pre2016-01-20 10:26:24.331842158 +0100
@@ -778,289 +778,344 @@
 Value numbering store SR.21_304->count to 2
 Setting value number of .MEM_132 to .MEM_132 (changed)
 Value numbering _48 stmt = _48 = MEM[(struct O *)_248].count;
-Setting value number of _48 to 2 (changed)
+Setting value number of _48 to _48 (changed)
 Value numbering _49 stmt = _49 = _48 + -1;
-Match-and-simplified _48 + -1 to 1
-RHS _48 + -1 simplified to 1
-Setting value number of _49 to 1 (changed)
+Setting value number of _49 to _49 (changed)
...

and the reason is that the dominance queries I do for the PR69117 fix do not
honor the edges we computed as unreachable.  The first case we hit that ends
up pessimizing points-to info during VN is quite simple:

:
# RANGE [2, 2147483647] NONZERO 2147483647
_57 = _56 + 1;
MEM[(struct O *)_248].count = _57;
if (_75 > 1)
  goto ;
else
  goto ;

:
goto ;

:
# PT = { D.5028 }
# ALIGN = 8, MISALIGN = 0
# USE = nonlocal 
# CLB = nonlocal 
_266 = __builtin_malloc (16);
MEM[(struct O *)_266].num = _202;
# RANGE [1, 2147483646] NONZERO 2147483647
_280 = _74;
MEM[(struct O *)_194].count = _74;
MEM[(struct O *)_266].count = 1;
D.4995 ={v} {CLOBBER};

:
# PT = { D.5024 D.5028 }
# ALIGN = 8, MISALIGN = 0
# SR.21_304 = PHI <_194(41), _266(15)>

with _75 > 1 known to be true and the edge 41 -> 16 not executable we
value-number SR.21_304 to _266 but clear points-to info of that on the
way unnecessarily.

So we can open-code a wrapper around dominated_by_p and handle some
simple CFG cases with not executable edges.  I'm not sure it's worth
to covering everything like by looking up the common immediate dominator
and figuring out if there is an always executed path through both nodes
starting from it.  [I believe it's enough to handle the case with
equal immediate dominator]

[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

--- Comment #5 from Richard Biener  ---
Created attachment 37406
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=37406=edit
patch for testing

Patch I am testing.

[Bug tree-optimization/69378] [6 Regression] FAIL: g++.dg/tree-ssa/pr61034.C

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378

Richard Biener  changed:

   What|Removed |Added

 CC||law at gcc dot gnu.org

--- Comment #4 from Richard Biener  ---
The dominator walk (recording temporary relations / equivalences) is
pessmimized
by not considering not executable edges as well (by unnecessarily popping off
those).  Consider a diamond with one half not executable - the conditional
relations / equivalences still hold in the merger.

The following patch fixes this regression though dominated_by_p_w_unex
is somewhat awkward.  We could do better by iterating but the key
issue is to identify quickly if there is any (exeecutable) path from bb2 to
bb1,
otherwise we'll iterate to entry or exit (dependent on which direction
we iterate) - that'll be too costly.

For example we could iterate by following bb2s single executable
successors, verifying they do have a single executable predecessor,
until we hit bb1 (or exit ...).  [if not single executable successor
continue with the successor that has the executable path from bb2 to bb1...]

Maybe the patch is already too sophisticated and I should simply do
a max. n (1?) depth walk like that.

That said, "fixing" the dominator walk for DOM / SCCVN would certainly
be interesting as well - I'm not sure we can compute dominators
"on-the-fly" though, that is, keep the efficient stack of cond
equivalences, for all but very simple CFG shapes.

Index: gcc/tree-ssa-sccvn.c
===
--- gcc/tree-ssa-sccvn.c(revision 232603)
+++ gcc/tree-ssa-sccvn.c(working copy)
@@ -2969,6 +2969,31 @@ print_scc (FILE *out, vec scc)
   fprintf (out, "\n");
 }

+/* Return true if BB1 is dominated by BB2 taking into account edges
+   that are not executable in the region starting from the
+   common immediate dominator.  */
+
+static bool
+dominated_by_p_w_unex (basic_block bb1, basic_block bb2)
+{
+  if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
+return true;
+
+  /* Go up to the immediate dominator of bb2 and see if that is post-dominated
+ by bb2 taking into account un-executable edges.  */
+  basic_block idom2 = get_immediate_dominator (CDI_DOMINATORS, bb2);
+  if (EDGE_COUNT (idom2->succs) != 2)
+return false;
+  if ((! (EDGE_SUCC (idom2, 0)->flags & EDGE_EXECUTABLE)
+   && dominated_by_p (CDI_DOMINATORS, bb2, EDGE_SUCC (idom2, 1)->dest))
+  || (! (EDGE_SUCC (idom2, 1)->flags & EDGE_EXECUTABLE)
+ && dominated_by_p (CDI_DOMINATORS, bb2, EDGE_SUCC (idom2, 0)->dest)))
+/* Re-do the dominance check with the immediate dominator.  */
+return dominated_by_p (CDI_DOMINATORS, bb1, idom2);
+
+  return false;
+}
+
 /* Set the value number of FROM to TO, return true if it has changed
as a result.  */

@@ -3046,13 +3071,13 @@ set_ssa_val_to (tree from, tree to)
  && SSA_NAME_RANGE_INFO (to))
{
  if (SSA_NAME_IS_DEFAULT_DEF (to)
- || dominated_by_p (CDI_DOMINATORS,
+ || dominated_by_p_w_unex (
 gimple_bb (SSA_NAME_DEF_STMT (from)),
 gimple_bb (SSA_NAME_DEF_STMT (to
/* Keep the info from the dominator.  */
;
  else if (SSA_NAME_IS_DEFAULT_DEF (from)
-  || dominated_by_p (CDI_DOMINATORS,
+  || dominated_by_p_w_unex (
  gimple_bb (SSA_NAME_DEF_STMT (to)),
  gimple_bb (SSA_NAME_DEF_STMT
(from
{
@@ -3076,13 +3101,13 @@ set_ssa_val_to (tree from, tree to)
   && SSA_NAME_PTR_INFO (to))
{
  if (SSA_NAME_IS_DEFAULT_DEF (to)
- || dominated_by_p (CDI_DOMINATORS,
+ || dominated_by_p_w_unex (
 gimple_bb (SSA_NAME_DEF_STMT (from)),
 gimple_bb (SSA_NAME_DEF_STMT (to
/* Keep the info from the dominator.  */
;
  else if (SSA_NAME_IS_DEFAULT_DEF (from)
-  || dominated_by_p (CDI_DOMINATORS,
+  || dominated_by_p_w_unex (
  gimple_bb (SSA_NAME_DEF_STMT (to)),
  gimple_bb (SSA_NAME_DEF_STMT
(from
{


Alternative "algorithm":

/* Return true if BB1 is dominated by BB2 taking into account edges
   that are not executable.  */

static bool
dominated_by_p_w_unex (basic_block bb1, basic_block bb2)
{
  if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
return true;

  /* Before iterating we'd like to know if there exists a
 (executable) path from bb2 to bb1 at all, if not we can
 directly return