Change split out from D72420, because I noticed it causes an unrelated test change. If the loop latch is a switch, then there can be multiple edges from the latch to the header. The LoopSimplify test changes because it's no longer necessary to split of an extra block in this case.
Diff Detail
Diff Detail
Event Timeline
Comment Actions
My concern with this is that there there might be some places where we're assuming the backedge of a loop latch is exactly one edge, and you might not have found them. There are a lot of places that call getLoopLatch or isLoopSimplifyForm, we don't really have much regression test coverage for this sort of construct, and the C/C++ tests most people run probably have few switches like this.
Comment Actions
I think this may break a fairly major assumption that there's a single backedge if there is a latch block. As a simple example, here's the comment from LoopSimplify:
// If the header has more than two predecessors at this point (from the
// preheader and from multiple backedges), we must adjust the loop.
BasicBlock *LoopLatch = L->getLoopLatch();
if (!LoopLatch) {The entire point of this code is to insert a single backedge for the canonicalized loop.
I'm open to being convinced that the change in canonical form to allow multiple identical backedges is reasonable, but I'd expect to see an argument to that form, not simple a code change.
I took a quick skim through IndVars, and there were initially some patterns which looked concerning around values on incoming edges until I remembered that duplicate edges require identical values in phis. But I could see consumer code which didn't properly account for that, so an audit is probably warranted.
For instance, it looks like anything using removeIncomingValue(BB, ...) is probably wrong after this change. A quick skim of LoopUnroll turned up at least one suspicious place.
Comment Actions
I'm open to being convinced that the change in canonical form to allow multiple identical backedges is reasonable, but I'd expect to see an argument to that form, not simple a code change.
The context here is D72420, which adds support for rotating loops that use a switch instruction rather than branch instruction for the loop exit condition. The loop rotation pass naturally asserts that the end result is going to be a loop that has an exiting latch. Of course it is possible to instead produce a separate latch block (as loop simplify currently does) and remove the requirement that the latch be exiting. However, that leaves us with a loop that we generally would not say to be in rotated form -- and indeed, successive applications of the loop rotate pass will continue to rotate it, effectively peeling off iterations one by one. It would be necessary to special case this structure in order to prevent additional rotations from occurring.
The use of multi edges for switches is a peculiarity of LLVMs representation, not an intrinsic property of the control flow graph. Structurally, I would expect that any optimizations that require a unique latch, or a unique latch that is also exiting, will remain applicable if the edges are repeated. Allowing this avoids having to either special case this kind of code, or give up optimization potential. (Practically this tends to not be very relevant right now, because loop passes generally bail on switches.)
I do understand the concern about breaking assumptions though.
Comment Actions
https://github.com/llvm/llvm-project/blob/ab72db7fc85266f094cc6b9452dd01f175c04cab/llvm/lib/Analysis/ScalarEvolutionExpander.cpp#L1300-L1325 => This piece of code in SCEVExpander breaks in practice (creating separate values for the same predecessor block).
Comment Actions
For other cases, we have multiple getters, such as:
- LoopBase::getUniqueExitBlock(): Only ensures single exit blocks, multiple edges to it possible.
- LoopBase::getExitBlock(): Ensures single exiting edge