[Bug tree-optimization/23821] [4.0/4.1 Regression] DOM and VRP creating harder to optimize code

[Bug tree-optimization/23821] [4.0/4.1 Regression] DOM and VRP creating harder to optimize code

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |minor


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1 Regression] DOM and VRP creating harder to optimize code

[mmitchel at gcc dot gnu dot org]

------- Comment #3 from mmitchel at gcc dot gnu dot org  2005-10-31 05:42 -------
Leaving as P2, pending investigation.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1 Regression] DOM and VRP creating harder to optimize code

[steven at gcc dot gnu dot org]

------- Comment #4 from steven at gcc dot gnu dot org  2005-11-13 16:17 -------
What happens here is just copy propagation by DOM and VRP for "conditional
copies", e.g. with "if (a==b) ..." we can record b as a copy of a, or a as a
copy of b.  In this case, copy propagation just happens to make IV analysis
hard (or impossible).

Now, this sounds bad.  But does this code really happen often enough in real
world code to justify spending hours on figuring out how to fix this?

Zdenek, where does your example come from?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1 Regression] DOM and VRP creating harder to optimize code

[rakdver at gcc dot gnu dot org]

------- Comment #5 from rakdver at gcc dot gnu dot org  2005-11-14 09:16 -------
The testcase comes from gcc testsuite.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2 Regression] DOM and VRP creating harder to optimize code

[steven at gcc dot gnu dot org]

------- Comment #6 from steven at gcc dot gnu dot org  2006-02-09 23:05 -------
It seems to me that this is only a SCEV enhancement request.  Seb?


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |spop at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2 Regression] DOM and VRP creating harder to optimize code

[rakdver at gcc dot gnu dot org]

------- Comment #7 from rakdver at gcc dot gnu dot org  2006-02-09 23:52 -------
There is no simple way how scev could determine that x == i at the end of loop
(unless we insert something like ASSERT_EXPRs at the condition).  Persuading
dom and VRP not to perform this transformation would probably be much easier.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2 Regression] DOM and VRP creating harder to optimize code

[sebastian dot pop at cri dot ensmp dot fr]

------- Comment #8 from sebastian dot pop at cri dot ensmp dot fr  2006-02-13 08:45 -------
Subject: Re:  [4.0/4.1/4.2 Regression] DOM and VRP creating harder to optimize
code

This case reminds me the peeled chrec unification that I had to
disable on autovect branch (I probably have to run the transformation
as a stand alone pass outside the analyzer for not disturbing the user
passes).  In that case we're looking at a code like

loop
  x = phi (0, a)
  a = phi (1, a + 1)
endloop

such that a simple transformation can make "x" a simple iv.  This case
is also quite important, as it occurs about 300 times during a bootstrap.

Now for the current problem, we could run a pass just after loop_init
for cleaning all these constructs.  As suggested, we would have to
build an equivalence relation either like VRP, or on demand.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2 Regression] DOM and VRP creating harder to optimize code

[mmitchel at gcc dot gnu dot org]

------- Comment #9 from mmitchel at gcc dot gnu dot org  2006-02-24 00:26 -------
This issue will not be resolved in GCC 4.1.0; retargeted at GCC 4.1.1.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.3                       |4.1.1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2 Regression] DOM and VRP creating harder to optimize code

[mmitchel at gcc dot gnu dot org]

------- Comment #10 from mmitchel at gcc dot gnu dot org  2006-05-25 02:33 -------
Will not be fixed in 4.1.1; adjust target milestone to 4.1.2.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.1                       |4.1.2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.2                       |4.1.3


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[spop at gcc dot gnu dot org]

------- Comment #11 from spop at gcc dot gnu dot org  2007-10-19 21:54 -------
Subject: Re:  [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to
optimize code

Just looking again to this old bug...

The problem with VRP/DOM is that they just state equalities, and then
they apply the substitution without really looking at the direction in
which to apply the substitution: so half of the time the transform is
probably a win ;-)

If you look at the transform that VRP/DOM do for the original
testcase, i.e. with the condition:

      if (x != i)
        abort ();

this is harmful, as VRP/DOM decides to replace i by x in the induction
variable i = i + 1, and we end with a code that is harder to analyze
later on.  Now, after reversing the operands in the condition,

      if (i != x)
        abort ();

both VRP/DOM will just say let's replace x by i, and then everything
is okay, so it's a win ;-)

Here is a patch for VRP to avoid random substitutions of symbolic
expressions, although this might not be the best approach to solve
the problem.

Index: tree-vrp.c
===================================================================
--- tree-vrp.c  (revision 129493)
+++ tree-vrp.c  (working copy)
@@ -6000,7 +6000,8 @@ vrp_finalize (void)
   for (i = 0; i < num_ssa_names; i++)
     if (vr_value[i]
        && vr_value[i]->type == VR_RANGE
-       && vr_value[i]->min == vr_value[i]->max)
+       && vr_value[i]->min == vr_value[i]->max
+       && !symbolic_range_p (vr_value[i]))
       {
        single_val_range[i].value = vr_value[i]->min;
        do_value_subst_p = true;

DOM has a similar code, but is more intricated, and also probably more
careful sometimes, looking at the loop depth of the definition before
replacing it, for avoiding to undo a LICM.  I think that the code that
looks at the profitability of this transformation could be shared
between VRP and DOM.

Sebastian


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[steven at gcc dot gnu dot org]

------- Comment #12 from steven at gcc dot gnu dot org  2007-12-16 23:17 -------
Open regression with no activity since February 14.  Ping?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[spop at gcc dot gnu dot org]

------- Comment #13 from spop at gcc dot gnu dot org  2008-01-10 00:09 -------
Subject: Re:  [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to
optimize code

For fixing this bug, one option is to disable symbolic propagations,
as in the patchlet that I sent before, and also in the DOM pass.
We have to show that there is no value in doing these transformations.

Sebastian


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[spop at gcc dot gnu dot org]

-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |spop at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2006-08-27 21:48:05         |2008-01-11 22:27:42
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[sebpop at gmail dot com]

------- Comment #14 from sebpop at gmail dot com  2008-01-12 00:11 -------
Subject: Re:  [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to
optimize code

Patch: http://gcc.gnu.org/ml/gcc-patches/2008-01/msg00518.html


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2008-01-12 10:49 -------
I think symbolic substitutions should be only done if the resulting stmt can
be simplified to a constant.  Now for VRP my long-term plan is to get rid of
symbolic ranges altogether to make it cheaper and easier to keep value-range
information across passes.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[pinskia at gmail dot com]

------- Comment #16 from pinskia at gmail dot com  2008-01-12 12:26 -------
Subject: Re:  [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to
optimize code

> ------- Comment #15 from rguenth at gcc dot gnu dot org  2008-01-12 10:49 -------
> I think symbolic substitutions should be only done if the resulting stmt can
> be simplified to a constant.  Now for VRP my long-term plan is to get rid of
> symbolic ranges altogether to make it cheaper and easier to keep value-range
> information across passes.

Actually I think it is wrong to get rid of symbolic ranges.  I have
filed a couple of bugs about adding more symbol ranges with respect of
VRP.

-- Pinski


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #17 from rguenth at gcc dot gnu dot org  2008-01-12 12:29 -------
Can you point me to those?

I still think we should separate VRP of constant and symbolic ranges.  For
symbolic stuff we eventually want to utilize a theorem prover.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.0/4.1/4.2/4.3 Regression] DOM and VRP creating harder to optimize code

[pinskia at gcc dot gnu dot org]

------- Comment #18 from pinskia at gcc dot gnu dot org  2008-01-12 12:36 -------
(In reply to comment #17)
> Can you point me to those?

PR25643 and PR25145 .

Thanks,
Andrew Pinski


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.2/4.3/4.4 Regression] DOM and VRP creating harder to optimize code

[jsm28 at gcc dot gnu dot org]

------- Comment #19 from jsm28 at gcc dot gnu dot org  2008-07-04 20:02 -------
Closing 4.1 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.1/4.2/4.3/4.4 Regression]|[4.2/4.3/4.4 Regression] DOM
                   |DOM and VRP creating harder |and VRP creating harder to
                   |to optimize code            |optimize code
   Target Milestone|4.1.3                       |4.2.5


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[jsm28 at gcc dot gnu dot org]

------- Comment #20 from jsm28 at gcc dot gnu dot org  2009-03-31 18:55 -------
Closing 4.2 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.2/4.3/4.4/4.5 Regression]|[4.3/4.4/4.5 Regression] DOM
                   |DOM and VRP creating harder |and VRP creating harder to
                   |to optimize code            |optimize code
   Target Milestone|4.2.5                       |4.3.4


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[spop at gcc dot gnu dot org]

------- Comment #21 from spop at gcc dot gnu dot org  2009-07-22 16:27 -------
I will let Richi to solve this problem:
http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01187.html

Sebastian


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|spop at gcc dot gnu dot org |unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #22 from rguenth at gcc dot gnu dot org  2009-07-22 19:33 -------
I will have a look.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-01-11 22:27:42         |2009-07-22 19:33:14
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #23 from rguenth at gcc dot gnu dot org  2009-08-04 12:26 -------
GCC 4.3.4 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.4                       |4.3.5


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #24 from rguenth at gcc dot gnu dot org  2009-09-23 15:23 -------
A simple band-aid for DOM is IMHO ok here, sth like:

Index: tree-ssa-dom.c
===================================================================
--- tree-ssa-dom.c      (revision 152059)
+++ tree-ssa-dom.c      (working copy)
@@ -2031,6 +2031,12 @@ cprop_operand (gimple stmt, use_operand_
       if (loop_depth_of_name (val) > loop_depth_of_name (op))
        return false;

+      /* Do not propagate copies into simple IV increment statements.
+         See PR23821 for how this can disturb IV analysis.  */
+      if (TREE_CODE (val) != INTEGER_CST
+         && simple_iv_increment_p (stmt))
+       return false;
+
       /* Dump details.  */
       if (dump_file && (dump_flags & TDF_DETAILS))
        {


the patch from comment #11 is also ok, randomly propagating one or the
other operand doesn't sound useful.  I will throw both patches to
performance testing.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rahul at icerasemi dot com]

------- Comment #25 from rahul at icerasemi dot com  2009-09-25 14:26 -------
Do the fixes in comment #11 and #24 alone solve the missed induction variable
problem?

I'm using the 4.4.1 release branch and it doesn't seem to work for me.
After DOM i get

# i_10 = PHI <x_4(3)>
i_5 = i_10 + 1;

and PHI propagation turns this into

i_5 = x_4 + 1;


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #26 from rguenth at gcc dot gnu dot org  2009-09-25 14:39 -------
It works for me on the trunk - I don't think this is worth fixing on release
branches.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #27 from rguenth at gcc dot gnu dot org  2009-09-25 14:59 -------
It also works with 4.4 for me.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rahul at icerasemi dot com]

------- Comment #28 from rahul at icerasemi dot com  2009-09-25 17:10 -------
Sorry, I also had changes to move loop header copying before FRE from
http://gcc.gnu.org/ml/gcc/2009-09/msg00434.html.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #29 from rguenth at gcc dot gnu dot org  2009-09-28 11:17 -------
Can you file a new bug for that issue?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4/4.5 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #30 from rguenth at gcc dot gnu dot org  2009-10-05 13:18 -------
Subject: Bug 23821

Author: rguenth
Date: Mon Oct  5 13:18:09 2009
New Revision: 152449

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=152449
Log:
2009-10-05  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/23821
        * tree-vrp.c (vrp_finalize): Do not perform copy propagation.
        * tree-ssa-dom.c (cprop_operand): Do not propagate copies into
        simple IV increments.

        * gcc.dg/torture/pr23821.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr23821.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-dom.c
    trunk/gcc/tree-vrp.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821

[Bug tree-optimization/23821] [4.3/4.4 Regression] DOM and VRP creating harder to optimize code

[rguenth at gcc dot gnu dot org]

------- Comment #31 from rguenth at gcc dot gnu dot org  2009-10-05 13:19 -------
Fixed for 4.5.0, not going to fix it for the branches.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to fail|4.0.4                       |4.0.4 4.1.2 4.2.4 4.3.4
                   |                            |4.4.1
      Known to work|                            |4.5.0
         Resolution|                            |FIXED
            Summary|[4.3/4.4/4.5 Regression] DOM|[4.3/4.4 Regression] DOM and
                   |and VRP creating harder to  |VRP creating harder to
                   |optimize code               |optimize code
   Target Milestone|4.3.5                       |4.5.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23821