[Bug tree-optimization/56756] ICE: verify_ssa failed (definition in block n follows the use !)

[Bug tree-optimization/56756] ICE: verify_ssa failed (definition in block n follows the use !)

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-03-28
                 CC|                            |mpolacek at gcc dot gnu.org
      Known to work|                            |4.7.3
   Target Milestone|---                         |4.9.0
     Ever Confirmed|0                           |1
      Known to fail|                            |4.9.0

--- Comment #1 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-03-28 07:10:23 UTC ---
Confirmed.  Bisecting...

[Bug tree-optimization/56756] ICE: verify_ssa failed (definition in block n follows the use !)

[mpolacek at gcc dot gnu.org]

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

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-03-28 07:38:04 UTC ---
Something goes wrong in LIM.

[Bug tree-optimization/56756] [4.9 Regression] ICE: verify_ssa failed (definition in block n follows the use !)

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |rguenth at gcc dot gnu.org
      Known to work|                            |4.8.0
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
            Summary|ICE: verify_ssa failed      |[4.9 Regression] ICE:
                   |(definition in block n      |verify_ssa failed
                   |follows the use !)          |(definition in block n
                   |                            |follows the use !)

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-28 09:45:59 UTC ---
Mine.

[Bug tree-optimization/56756] [4.9 Regression] ICE: verify_ssa failed (definition in block n follows the use !)

[mpolacek at gcc dot gnu.org]

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

--- Comment #4 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-03-28 09:54:58 UTC ---
It seems that move_computations_stmt firstly inserts into bb 11
# VUSE <.MEM_21>
D__lsm.5 = *_17;
and then
# VUSE <.MEM_21>
_17 = *q_8(D);

move_computations then commits these inserts.

[Bug tree-optimization/56756] [4.9 Regression] ICE: verify_ssa failed (definition in block n follows the use !)

[rguenther at suse dot de]

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

--- Comment #5 from rguenther at suse dot de <rguenther at suse dot de> 2013-03-28 10:07:29 UTC ---
On Thu, 28 Mar 2013, mpolacek at gcc dot gnu.org wrote:

> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56756
> 
> --- Comment #4 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-03-28 09:54:58 UTC ---
> It seems that move_computations_stmt firstly inserts into bb 11
> # VUSE <.MEM_21>
> D__lsm.5 = *_17;
> and then
> # VUSE <.MEM_21>
> _17 = *q_8(D);
> 
> move_computations then commits these inserts.

LIM relies on dom-walk to walk blocks in a order that processes
SSA definitions before uses.  But that is not what a dom-walk
guarantees ...

[Bug tree-optimization/56756] [4.9 Regression] ICE: verify_ssa failed (definition in block n follows the use !)

[mpolacek at gcc dot gnu.org]

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

--- Comment #6 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-03-28 10:11:55 UTC ---
FWIW, started with http://gcc.gnu.org/viewcvs/gcc?view=revision&revision=196769

[Bug tree-optimization/56756] [4.9 Regression] ICE: verify_ssa failed (definition in block n follows the use !)

[rguenther at suse dot de]

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

--- Comment #7 from rguenther at suse dot de <rguenther at suse dot de> 2013-03-28 10:26:48 UTC ---
On Thu, 28 Mar 2013, mpolacek at gcc dot gnu.org wrote:

> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56756
> 
> --- Comment #6 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-03-28 10:11:55 UTC ---
> FWIW, started with http://gcc.gnu.org/viewcvs/gcc?view=revision&revision=196769

Yes, I was expecting that.  This orders blocks in a different
"random" order when visiting dominator children.  It tries
to order them in inverted postorder - which is exactly deterministically
"wrong" for LIM, as it visits loop blocks with a loop exit edge
last.

[Bug tree-optimization/56756] [4.9 Regression] ICE: verify_ssa failed (definition in block n follows the use !)

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-28 12:42:17 UTC ---
Created attachment 29744
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29744
patch

This patch makes us not rely on a dominator walk to magically get us process
stmts in the correct order but instead uses the dependences we record for
each stmt to make sure we moved them before uses.  And fixes things to
actually record all dependences (translating stmt to bb dependencies before
that walk may speed up things for some testcases, processing in a good
order from the start can avoid the recursion - processing stmts rather than
BBs with a worklist is another possibility - we should be able to "drain"
the depends vector into the worklist).

[Bug tree-optimization/56756] [4.9 Regression] ICE: verify_ssa failed (definition in block n follows the use !)

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> 2013-04-16 11:56:26 UTC ---
The issue is that

static void
execute_sm (struct loop *loop, vec<edge> exits, mem_ref_p ref)
{
...
  /* Emit the load code into the latch, so that we are sure it will
     be processed after all dependencies.  */
  latch_edge = loop_latch_edge (loop);

is no longer working.  It wasn't working by design before either.
We temporarily create

    <header> <-----------\
       |                 |
      if ()              |
     /   \               |
         _17 = *q_8(D);  |
     \   /               |
     D__lsm.5 = *_17;-----

that is invalid SSA form and expect a dominator walk to visit
_17 = *q_8(D) before visiting D__lsm.5 = *_17;

So a simpler fix than the attached one finds a better temporary
insertion place for D__lsm.5 =  *_17;

Placing the load at a random existing load or store would be the
best.  I'm reworking the patch to do that.