Using GCC 4.9.0 as of 20130327 : $ cat ssa.c int a, *b; void f(void) { if(a) { int k; for(a = 0; a < 1; a++) { int **q; f(); for(; **q; ++**q) lbl: if(a) { a = 0; goto lbl; } b = &k; } } goto lbl; } $ xgcc -O1 -w ssa.c ssa.c: In function ‘f’: ssa.c:3:6: error: definition in block 12 follows the use void f(void) ^ for SSA_NAME: _17 in statement: # VUSE <.MEM_21> D__lsm.5_2 = *_17; ssa.c:3:6: internal compiler error: verify_ssa failed Please submit a full bug report, with preprocessed source if appropriate. See <http://gcc.gnu.org/bugs.html> for instructions.
Confirmed. Bisecting...
Something goes wrong in LIM.
Mine.
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.
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 ...
FWIW, started with http://gcc.gnu.org/viewcvs/gcc?view=revision&revision=196769
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.
Ok, so one reason is that we simply "ignore" dependencies when computing what stmts to move (which happens in the same processing order): static bool add_dependency (tree def, struct lim_aux_data *data, struct loop *loop, bool add_cost) { ... max_loop = outermost_invariant_loop (def, loop); if (!max_loop) return false; ... def_data = get_lim_data (def_stmt); if (!def_data) return true; so, when we don't know anything about the stmt we depend on because we didn't visit it yet outermost_invariant_loop returns garbage in this case. But I got side-tracked by the above (which still should be fixed IMHO), as also store-motion does not properly initialize dependence.
Created attachment 29744 [details] 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).
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.
Author: rguenth Date: Tue Apr 16 15:32:26 2013 New Revision: 198001 URL: http://gcc.gnu.org/viewcvs?rev=198001&root=gcc&view=rev Log: 2013-04-16 Richard Biener <rguenther@suse.de> PR tree-optimization/56756 * tree-ssa-loop-im.c (struct first_mem_ref_loc_1): New functor. (first_mem_ref_loc): New. (execute_sm): Place the load temporarily before a previous access instead of in the latch edge to ensure its SSA dependencies are defined at points dominating the load. * gcc.dg/torture/pr56756.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/torture/pr56756.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-loop-im.c