[LoopSimplify] Restoring the normalization of br instructions.

[dbakunevich]

Summary

As part of a particular optimization (InstCombine for example),
the situations may occur when we exit the loop on the true branch.
This transformation breaks a number of optimizations.
Therefore, it was decided to restore such instructions.

[lebedev.ri]

You did not invert the branch condition.

[dbakunevich]

In D139876#3989779, @lebedev.ri wrote:

You did not invert the branch condition.

Fixed it

[lebedev.ri]

And what if the condition had other users?
And what if the condition was not relational?

Please just insert xor %cond, -1.
This is missing tests (please precommit) that now are getting optimized.

[nikic]

This is almost certainly not the correct way to fix whatever problem you're trying to fix. If an optimization doesn't work with commuted branch targets, then that optimization needs to be fixed.

[mkazantsev]

In D139876#3990029, @nikic wrote:

This is almost certainly not the correct way to fix whatever problem you're trying to fix. If an optimization doesn't work with commuted branch targets, then that optimization needs to be fixed.

There is always a tradeoff between having a canonical form and expecting this canonical form in transforms, and trying to support everything. I've seen enough cases where exit by false isn't [fully] supported, so saying that "fallthrough stays in loop is our canonical form" isn't a that bad idea in general.

Besides, even if it's not about the optimizations, codegen will still do something similar when it tries to lay out the blocks. So generally I like the idea of this patch (though I think the place for doing it is wrong).

llvm/lib/Transforms/Utils/LoopSimplify.cpp

543

How is that even possible?
UB here.

545

m_match(BI, m_Br(m_ICmp (...) )

548

Changed = true somewhere?

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Transforms/Utils/LoopSimplify.cpp

if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
                      << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
                      << ExitingBlock->getName() << "\n");
 
           BI->setCondition(ConstantInt::get(Cond->getType(),
                                             !L->contains(BI->getSuccessor(0))));
 
           Changed = true;
         }
+        BasicBlock *TrueBB, *FalseBB;
+        using namespace PatternMatch;
+        if (match(BI, m_Br(m_Value(), TrueBB, FalseBB)) &&
+            !L->contains(TrueBB) && L->contains(FalseBB)) {
+          if (isa<BinaryOperator>(BI->getCondition())) {
+            if (dyn_cast<BinaryOperator>(BI->getCondition())->swapOperands())
+              BI->swapSuccessors();
+          } else if (isa<ICmpInst>(BI->getCondition())) {
+            dyn_cast<ICmpInst>(BI->getCondition())->swapOperands();
+            BI->swapSuccessors();
+          }
+        }
       }
 
   // Does the loop already have a preheader?  If so, don't insert one.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader) {
     Preheader = InsertPreheaderForLoop(L, DT, LI, MSSAU, PreserveLCSSA);
     if (Preheader)
       Changed = true;