GitHub PushEvent at 2014-01-29 13:23:34
Repository: llvm-project
Actor: chapuni
Payload: {"shas":[["b6123bf3467288217b380b2cb66b50cfc5543b7a","420c9fb3407b8e11ac322a0e7703f7b1f526df04@gmail.com","[LPM] Fix PR18643, another scary place where loop transforms failed to\npreserve loop simplify of enclosing loops.\n\nThe problem here starts with LoopRotation which ends up cloning code out\nof the latch into the new preheader it is buidling. This can create\na new edge from the preheader into the exit block of the loop which\nbreaks LoopSimplify form. The code tries to fix this by splitting the\ncritical edge between the latch and the exit block to get a new exit\nblock that only the latch dominates. This sadly isn't sufficient.\n\nThe exit block may be an exit block for multiple nested loops. When we\nclone an edge from the latch of the inner loop to the new preheader\nbeing built in the outer loop, we create an exiting edge from the outer\nloop to this exit block. Despite breaking the LoopSimplify form for the\ninner loop, this is fine for the outer loop. However, when we split the\nedge from the inner loop to the exit block, we create a new block which\nis in neither the inner nor outer loop as the new exit block. This is\na predecessor to the old exit block, and so the split itself takes the\nouter loop out of LoopSimplify form. We need to split every edge\nentering the exit block from inside a loop nested more deeply than the\nexit block in order to preserve all of the loop simplify constraints.\n\nOnce we try to do that, a problem with splitting critical edges\nsurfaces. Previously, we tried a very brute force to update LoopSimplify\nform by re-computing it for all exit blocks. We don't need to do this,\nand doing this much will sometimes but not always overlap with the\nLoopRotate bug fix. Instead, the code needs to specifically handle the\ncases which can start to violate LoopSimplify -- they aren't that\ncommon. We need to see if the destination of the split edge was a loop\nexit block in simplified form for the loop of the source of the edge.\nFor this to be true, all the predecessors need to be in the exact same\nloop as the source of the edge being split. If the dest block was\noriginally in this form, we have to split all of the deges back into\nthis loop to recover it. The old mechanism of doing this was\nconservatively correct because at least *one* of the exiting blocks it\nrewrote was the DestBB and so the DestBB's predecessors were fixed. But\nthis is a much more targeted way of doing it. Making it targeted is\nimportant, because ballooning the set of edges touched prevents\nLoopRotate from being able to split edges *it* needs to split to\npreserve loop simplify in a coherent way -- the critical edge splitting\nwould sometimes find the other edges in need of splitting but not\nothers.\n\nMany, *many* thanks for help from Nick reducing these test cases\nmightily. And helping lots with the analysis here as this one was quite\ntricky to track down.","Chandler Carruth",true]],"size":1,"ref":"refs/heads/master","head":"b6123bf3467288217b380b2cb66b50cfc5543b7a"}