Re: Hopelessly broken loop_father, loop_depth
On Mon, Aug 13, 2012 at 3:15 PM, Steven Bosscher wrote: > On Mon, Aug 13, 2012 at 1:27 PM, Richard Guenther > wrote: >> I wonder why we cache loop-depth at all ... given that it is a "simple" >> dereference bb->loop_father->superloops->base.prefix.num. For all >> the hassle to keep that cache up-to-date, that is. > > The cached bb->loop_depth saves two indirect references. But if it's > hard to maintain, I'd be happy to see it go away. Just so long as > bb->loop_father is correct (to be verified by a patch for the loop > verification code). loop_father is easier to keep up-to-date at least, and possibly should just work. A patch removing loop_depth just finished testing and I'll commit it in a sec. Richard. > Ciao! > Steven
Re: Hopelessly broken loop_father, loop_depth
On Mon, Aug 13, 2012 at 1:27 PM, Richard Guenther wrote: > I wonder why we cache loop-depth at all ... given that it is a "simple" > dereference bb->loop_father->superloops->base.prefix.num. For all > the hassle to keep that cache up-to-date, that is. The cached bb->loop_depth saves two indirect references. But if it's hard to maintain, I'd be happy to see it go away. Just so long as bb->loop_father is correct (to be verified by a patch for the loop verification code). Ciao! Steven
Re: Hopelessly broken loop_father, loop_depth
On Mon, Aug 13, 2012 at 12:57 PM, Richard Guenther wrote: > On Mon, Aug 13, 2012 at 12:22 PM, Richard Guenther > wrote: >> On Mon, Aug 13, 2012 at 12:21 PM, Richard Guenther >> wrote: >>> On Sun, Aug 12, 2012 at 2:02 PM, Steven Bosscher >>> wrote: On Sat, Aug 11, 2012 at 11:16 PM, Steven Bosscher wrote: > Lots of test cases fail with the attached patch. Lots still fail after correcting the verifier :-) 920723-1.c: In function 'f': 920723-1.c:14:1: error: bb 13 has loop depth 2, should be 1 f (int count, vector_t * pos, double r, double *rho) ^ 920723-1.c:14:1: error: bb 14 has loop depth 2, should be 1 920723-1.c:14:1: internal compiler error: in verify_loop_structure, at cfgloop.c:1598 >>> >>> That's a pre-existing bug in unswitching. When unswitching >>> simplifies the condition it unswitches on using simplify_using_entry_checks >>> it may turn an inner loop into an exit to an endless loop. But it does >>> not modify the loop stucture according to this change. >>> >>> void foo (int x, int r) >>> { >>> loop4: >>> if (r >= x) >>> { >>> goto loop4_latch; >>> } >>> else >>> { >>> loop5: >>> if (r >= x) >>> goto loop4_latch; >>> goto loop5; >>> } >>> loop4_latch: >>> goto loop4; >>> } >>> >>> simplified testcase that even fails at -O1. We mostly rely on cfg-cleanup >>> to fixup loops for us, so this is one case it does not handle properly. >> >> Actually that testcase fails verification right after a full loop >> discovery which >> DOM1 performs ... > > Fixed by attached patch. > >>> The quest of keeping loops up-to-date is hard ... but thanks for the >>> checking >>> code ;) > > Which probably still makes things fail elsewhere ;) Same issue in fix_loop_structure: /* Now fix the loop nesting. */ FOR_EACH_LOOP (li, loop, 0) { ploop = superloop[loop->num]; if (ploop != loop_outer (loop)) { flow_loop_tree_node_remove (loop); flow_loop_tree_node_add (ploop, loop); } } I wonder why we cache loop-depth at all ... given that it is a "simple" dereference bb->loop_father->superloops->base.prefix.num. For all the hassle to keep that cache up-to-date, that is. Would anybody mind removing basic_block->loop_depth? With C++ we can even have an overloaded loop_depth that works on both basic-blocks and loops ... Richard. > Richard. > >>> Richard. >>> Ciao! Steven
Re: Hopelessly broken loop_father, loop_depth
On Mon, Aug 13, 2012 at 12:22 PM, Richard Guenther wrote: > On Mon, Aug 13, 2012 at 12:21 PM, Richard Guenther > wrote: >> On Sun, Aug 12, 2012 at 2:02 PM, Steven Bosscher >> wrote: >>> On Sat, Aug 11, 2012 at 11:16 PM, Steven Bosscher >>> wrote: Lots of test cases fail with the attached patch. >>> >>> Lots still fail after correcting the verifier :-) >>> >>> 920723-1.c: In function 'f': >>> 920723-1.c:14:1: error: bb 13 has loop depth 2, should be 1 >>> f (int count, vector_t * pos, double r, double *rho) >>> ^ >>> 920723-1.c:14:1: error: bb 14 has loop depth 2, should be 1 >>> 920723-1.c:14:1: internal compiler error: in verify_loop_structure, at >>> cfgloop.c:1598 >> >> That's a pre-existing bug in unswitching. When unswitching >> simplifies the condition it unswitches on using simplify_using_entry_checks >> it may turn an inner loop into an exit to an endless loop. But it does >> not modify the loop stucture according to this change. >> >> void foo (int x, int r) >> { >> loop4: >> if (r >= x) >> { >> goto loop4_latch; >> } >> else >> { >> loop5: >> if (r >= x) >> goto loop4_latch; >> goto loop5; >> } >> loop4_latch: >> goto loop4; >> } >> >> simplified testcase that even fails at -O1. We mostly rely on cfg-cleanup >> to fixup loops for us, so this is one case it does not handle properly. > > Actually that testcase fails verification right after a full loop > discovery which > DOM1 performs ... Fixed by attached patch. >> The quest of keeping loops up-to-date is hard ... but thanks for the checking >> code ;) Which probably still makes things fail elsewhere ;) Richard. >> Richard. >> >>> Ciao! >>> Steven fix-loops-1 Description: Binary data
Re: Hopelessly broken loop_father, loop_depth
On Mon, Aug 13, 2012 at 12:21 PM, Richard Guenther wrote: > On Sun, Aug 12, 2012 at 2:02 PM, Steven Bosscher > wrote: >> On Sat, Aug 11, 2012 at 11:16 PM, Steven Bosscher >> wrote: >>> Lots of test cases fail with the attached patch. >> >> Lots still fail after correcting the verifier :-) >> >> 920723-1.c: In function 'f': >> 920723-1.c:14:1: error: bb 13 has loop depth 2, should be 1 >> f (int count, vector_t * pos, double r, double *rho) >> ^ >> 920723-1.c:14:1: error: bb 14 has loop depth 2, should be 1 >> 920723-1.c:14:1: internal compiler error: in verify_loop_structure, at >> cfgloop.c:1598 > > That's a pre-existing bug in unswitching. When unswitching > simplifies the condition it unswitches on using simplify_using_entry_checks > it may turn an inner loop into an exit to an endless loop. But it does > not modify the loop stucture according to this change. > > void foo (int x, int r) > { > loop4: > if (r >= x) > { > goto loop4_latch; > } > else > { > loop5: > if (r >= x) > goto loop4_latch; > goto loop5; > } > loop4_latch: > goto loop4; > } > > simplified testcase that even fails at -O1. We mostly rely on cfg-cleanup > to fixup loops for us, so this is one case it does not handle properly. Actually that testcase fails verification right after a full loop discovery which DOM1 performs ... > The quest of keeping loops up-to-date is hard ... but thanks for the checking > code ;) > > Richard. > >> Ciao! >> Steven
Re: Hopelessly broken loop_father, loop_depth
On Sun, Aug 12, 2012 at 2:02 PM, Steven Bosscher wrote: > On Sat, Aug 11, 2012 at 11:16 PM, Steven Bosscher > wrote: >> Lots of test cases fail with the attached patch. > > Lots still fail after correcting the verifier :-) > > 920723-1.c: In function 'f': > 920723-1.c:14:1: error: bb 13 has loop depth 2, should be 1 > f (int count, vector_t * pos, double r, double *rho) > ^ > 920723-1.c:14:1: error: bb 14 has loop depth 2, should be 1 > 920723-1.c:14:1: internal compiler error: in verify_loop_structure, at > cfgloop.c:1598 That's a pre-existing bug in unswitching. When unswitching simplifies the condition it unswitches on using simplify_using_entry_checks it may turn an inner loop into an exit to an endless loop. But it does not modify the loop stucture according to this change. void foo (int x, int r) { loop4: if (r >= x) { goto loop4_latch; } else { loop5: if (r >= x) goto loop4_latch; goto loop5; } loop4_latch: goto loop4; } simplified testcase that even fails at -O1. We mostly rely on cfg-cleanup to fixup loops for us, so this is one case it does not handle properly. The quest of keeping loops up-to-date is hard ... but thanks for the checking code ;) Richard. > Ciao! > Steven
Re: Hopelessly broken loop_father, loop_depth
On Sat, Aug 11, 2012 at 11:16 PM, Steven Bosscher wrote: > Lots of test cases fail with the attached patch. Lots still fail after correcting the verifier :-) 920723-1.c: In function 'f': 920723-1.c:14:1: error: bb 13 has loop depth 2, should be 1 f (int count, vector_t * pos, double r, double *rho) ^ 920723-1.c:14:1: error: bb 14 has loop depth 2, should be 1 920723-1.c:14:1: internal compiler error: in verify_loop_structure, at cfgloop.c:1598 Ciao! Steven tighten_loop_verifier.diff Description: Binary data
Hopelessly broken loop_father, loop_depth
Hello Richi, After a frustrating few days of trying to figure out what *I* was doing wrong trying to speed up rewrite_into_loop_closed_ssa(), I finally gave up and looked at the rest of GCC. One wouldn't expect anything to be very broken in an unpatched tree, after all, but the kind of failures I was seeing just couldn't be explained by any fault of my own. Such as loop_depth(bb->loop_father) != bb->loop_depth. Or even worse, flow_bb_inside_loop_p (bb->loop_father, bb) is false. This looks all related to maintaining loops in the GIMPLE optimizers, but quite frankly, I don't really understand how the loop updating API is supposed to work, and I'm not even sure whether bb->loop_depth and bb->loop_father are supposed to be accurate at all times (other places in the compiler appear to rely on this, but it's still not documented, and I've spent enough time on this already when it's probably fixed in a jiffy by you ;-). Could you please have a look at this breakage? (And please, document the loop stuff and also all the SSA name changes ASAP instead of postponing it to stage3 or later!) Lots of test cases fail with the attached patch. As a starting point for you, I'll mention 920723-1.c compiled with -O1 -ftree-unswitch-loops. This gives: 920723-1.c: In function 'f': 920723-1.c:33:1: error: bb 15 has father loop 3, should be loop 2 } ^ 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 8 has father loop 3, should be loop 2 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 13 has father loop 5, should be loop 2 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 16 has father loop 4, should be loop 2 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 17 has father loop 5, should be loop 2 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 5 has father loop 5, should be loop 2 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 7 has father loop 3, should be loop 2 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 6 has father loop 4, should be loop 2 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 1 920723-1.c:33:1: error: bb 13 has father loop 5, should be loop 3 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 2 920723-1.c:33:1: error: bb 16 has father loop 4, should be loop 3 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 2 920723-1.c:33:1: error: bb 17 has father loop 5, should be loop 3 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 2 920723-1.c:33:1: error: bb 5 has father loop 5, should be loop 3 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 2 920723-1.c:33:1: error: bb 6 has father loop 4, should be loop 3 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 2 920723-1.c:33:1: error: bb 5 has father loop 5, should be loop 4 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 3 920723-1.c:33:1: error: bb 13 has father loop 5, should be loop 4 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 3 920723-1.c:33:1: error: bb 17 has father loop 5, should be loop 4 920723-1.c:33:1: error: bb 1 has loop depth 0, should be 3 920723-1.c:33:1: internal compiler error: in verify_loop_structure, at cfgloop.c:1583 Please submit a full bug report, etc. BTW, it's quite annoying that loop_depth(loop_p) returns "unsigned int", but bb->loop_depth is just "int". Is loop_depth<0 used as a special case? If so, then I think loop_depth(loop_p) should be changed to return "int", otherwise bb->loop_depth should be made an "unsigned int". What do you think about this? Ciao! Steven tighten_loop_verifier.diff Description: Binary data