[BreakCritEdges] Support preserving loop-simplify form with indirectbr. (WIP)

[fhahn]

Summary

This patch updates SplitCriticalEdges preserve loop-simplify form, even
if we would have to split the predecessors of the exit block.

Instead of splitting the predecessors of the exit block, it splits the
exit block at the first non-PHI instruction and updates the branch in
the new block to jump to the new split block. It also adds PHIs as
required.

Unfortunately a few users rely on the contents of a block not being
moved. I managed to fix most of them, but I am not too sure what to do
about the caching in MemoryDependenceAnalsysis.

[efriedma]

We could make preserving LoopSimplify form optional, and let users turn it on with CriticalEdgeSplittingOptions. That way, if some user isn't prepared to handle the transform, they can just let LoopSimplify form break, and fix it up later if necessary. We probably should do that anyway: there isn't any obvious connection between preserving LoopInfo and preserving LoopSimplify form.

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

324

Missing LoopInfo update?

[fhahn]

In D81584#2085788, @efriedma wrote:

We could make preserving LoopSimplify form optional, and let users turn it on with CriticalEdgeSplittingOptions. That way, if some user isn't prepared to handle the transform, they can just let LoopSimplify form break, and fix it up later if necessary. We probably should do that anyway: there isn't any obvious connection between preserving LoopInfo and preserving LoopSimplify form.

Agreed. I think that would go well with D81582, i.e. have a PreserveLoopSimplify option, that guarantees loop-simplify form is preserved or nullptr is returned if it's not possible. If PreserveLoopSimplify is false, don't preserve it if it is not possible . But currently GVN for example preserves loop-simplify form, but I suppose we could change that. Might be best as a follow-on of the bail out if preserving is not possible. What do you think?

Also, do you agree that preserving loop-simplify form by moving instructions to a different BB is more trouble than it is worth?

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

324

I don't think we need to do anything about LI here, as the block should already be added to LI by SplitBlock and we only adjust the successor to another successor in the same loop I think.

[efriedma]

Agreed. I think that would go well with D81582, i.e. have a PreserveLoopSimplify option, that guarantees loop-simplify form is preserved or nullptr is returned if it's not possible

We can kill off the call to SplitBlockPredecessors, and add an option to bail out if preserving loop-simplify form would require transforming other edges, sure. (I'd rather not condition it on whether the other edges are IndirectBr edges; I'd like to avoid obscure IndirectBr edge cases where possible.)

Also, do you agree that preserving loop-simplify form by moving instructions to a different BB is more trouble than it is worth?

This doesn't seem worse than calling SplitBlockPredecessors(), in terms of transforming the CFG in unpredictable ways.

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

324

Okay, that makes sense.

[fhahn]

In D81584#2086163, @efriedma wrote:

Agreed. I think that would go well with D81582, i.e. have a PreserveLoopSimplify option, that guarantees loop-simplify form is preserved or nullptr is returned if it's not possible

We can kill off the call to SplitBlockPredecessors, and add an option to bail out if preserving loop-simplify form would require transforming other edges, sure. (I'd rather not condition it on whether the other edges are IndirectBr edges; I'd like to avoid obscure IndirectBr edge cases where possible.)

Ok. In the short term, I'd like the fix the crash in GVN asap. Preserving simplify-form as in this patch will require a bit of extra work in a couple of places. I think in the short-term, it might be best to add a PreserveLoopSimplify option and have GVN not preserve loop-simplify form, until this patch is ready. What do you think?

Also, do you agree that preserving loop-simplify form by moving instructions to a different BB is more trouble than it is worth?

This doesn't seem worse than calling SplitBlockPredecessors(), in terms of transforming the CFG in unpredictable ways.

Agreed, unfortunately the existing users don't deal too gratefully with moving instructions, but I don't think anything in the SplitCriticalEdges interface guarantees that. If you are not concerned about the general approach and the small hoops that existing users have to jump through (see GVN & LSR changes), I am happy to continue with this approach, but it will probably require a few additional changes.

[efriedma]

I think in the short-term, it might be best to add a PreserveLoopSimplify option and have GVN not preserve loop-simplify form, until this patch is ready. What do you think?

That seems reasonable. I'm not sure why GVN is trying to preserve LoopSimplify in the first place.

[fhahn]

In D81584#2086602, @efriedma wrote:

I think in the short-term, it might be best to add a PreserveLoopSimplify option and have GVN not preserve loop-simplify form, until this patch is ready. What do you think?

That seems reasonable. I'm not sure why GVN is trying to preserve LoopSimplify in the first place.

I think it was because I initially *thought* all the utilities used to modify the CFG actually preserve loop-simplify form. I updated D81582 with the option & made GVN use it. It would be great if you could take a look.

[fhahn]

Should be superseded by D81582

llvm/lib/Transforms/Scalar/GVN.cpp

bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   MapVector<BasicBlock *, Value *> PredLoads;
   DenseMap<BasicBlock*, char> FullyAvailableBlocks;
   for (const AvailableValueInBlock &AV : ValuesPerBlock)
     FullyAvailableBlocks[AV.BB] = true;
   for (BasicBlock *UnavailableBB : UnavailableBlocks)
     FullyAvailableBlocks[UnavailableBB] = false;
 
   SmallVector<BasicBlock *, 4> CriticalEdgePred;
+
   for (BasicBlock *Pred : predecessors(LoadBB)) {
     // If any predecessor block is an EH pad that does not allow non-PHI
     // instructions before the terminator, we can't PRE the load.
     if (Pred->getTerminator()->isEHPad()) {
       LLVM_DEBUG(
           dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
                  << Pred->getName() << "': " << *LI << '\n');
       return false;
assert(InstrsToErase.empty() &&
          "We expect InstrsToErase to be empty across iterations");
   if (DeadBlocks.count(BB))
     return false;
 
   // Clearing map before every BB because it can be used only for single BB.
   ReplaceOperandsWithMap.clear();
   bool ChangedFunction = false;
 
+  auto eraseInstrs = [this, BB](bool BBContentsMoved) {
+    // If we need some instructions deleted, do it now.
+    NumGVNInstr += InstrsToErase.size();
+
+    for (auto *I : InstrsToErase) {
+      assert((BBContentsMoved || I->getParent() == BB) &&
+             "Removing instruction from wrong block?");
+      LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
+      salvageKnowledge(I, AC);
+      salvageDebugInfo(*I);
+      if (MD)
+        MD->removeInstruction(I);
+      LLVM_DEBUG(verifyRemoved(I));
+      ICF->removeInstruction(I);
+      I->eraseFromParent();
+    }
+    InstrsToErase.clear();
+  };
+
   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
        BI != BE;) {
     if (!ReplaceOperandsWithMap.empty())
       ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
     ChangedFunction |= processInstruction(&*BI);
 
+    if (BB->getTerminator()->getIterator() == BB->begin()) {
+      eraseInstrs(true);
+      return ChangedFunction;
+    }
+
     if (InstrsToErase.empty()) {
       ++BI;
       continue;
     }
 
-    // If we need some instructions deleted, do it now.
-    NumGVNInstr += InstrsToErase.size();
-
     // Avoid iterator invalidation.
     bool AtStart = BI == BB->begin();
     if (!AtStart)
       --BI;
 
-    for (auto *I : InstrsToErase) {
-      assert(I->getParent() == BB && "Removing instruction from wrong block?");
-      LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
-      salvageKnowledge(I, AC);
-      salvageDebugInfo(*I);
-      if (MD) MD->removeInstruction(I);
-      LLVM_DEBUG(verifyRemoved(I));
-      ICF->removeInstruction(I);
-      I->eraseFromParent();
-    }
-    InstrsToErase.clear();
+    eraseInstrs(false);
 
     if (AtStart)
       BI = BB->begin();
     else
       ++BI;
   }
 
   return ChangedFunction;

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

if (PN->getIncomingValue(i) == LF.OperandValToReplace) {
             SmallVector<BasicBlock*, 2> NewBBs;
             SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, &DT, &LI);
             NewBB = NewBBs[0];
           }
           // If NewBB==NULL, then SplitCriticalEdge refused to split because all
           // phi predecessors are identical. The simple thing to do is skip
           // splitting in this case rather than complicate the API.
           if (NewBB) {
+            auto *MergeBlock = NewBB->getSingleSuccessor();
+            for (auto &MergePN : MergeBlock->phis()) {
+              if (&MergePN == PN) {
+                PN = &MergePN;
+                break;
+              }
+              if (any_of(MergePN.incoming_values(),
+                         [PN](Value *Inc) { return Inc == PN; })) {
+                PN = &MergePN;
+                break;
+              }
+            }
             // If PN is outside of the loop and BB is in the loop, we want to
             // move the block to be immediately before the PHI block, not
             // immediately after BB.
             if (L->contains(BB) && !L->contains(PN))
               NewBB->moveBefore(PN->getParent());
 
             // Splitting the edge can reduce the number of PHI entries we have.
             e = PN->getNumIncomingValues();

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

if (Loop *TIL = LI->getLoopFor(TIBB)) {
             // No need to re-simplify, it wasn't to start with.
             LoopPreds.clear();
             break;
           }
           LoopPreds.push_back(P);
         }
         if (!LoopPreds.empty()) {
           assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
-          BasicBlock *NewExitBB = SplitBlockPredecessors(
-              DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
           if (Options.PreserveLCSSA)
-            createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
+            createPHIsForSplitLoopExit(LoopPreds, NewBB, DestBB);
+          auto *ExitCont = SplitBlock(DestBB, DestBB->getFirstNonPHI(), DT, LI,
+                                      MSSAU, DestBB->getName() + ".cont");
+          NewBB->getTerminator()->setSuccessor(0, ExitCont);
+          for (auto &PN : DestBB->phis()) {
+            PHINode *NewExitContPhi = PHINode::Create(
+                PN.getType(), 2, PN.getName(), &*ExitCont->begin());
+            PN.replaceAllUsesWith(NewExitContPhi);
+            NewExitContPhi->addIncoming(PN.getIncomingValueForBlock(NewBB),
+                                        NewBB);
+            NewExitContPhi->addIncoming(&PN, DestBB);
+            PN.removeIncomingValue(NewBB);
+          }
+
+          DT->applyUpdates({{DominatorTree::Insert, NewBB, ExitCont},
+                            {DominatorTree::Delete, NewBB, DestBB}});
         }
       }
     }
   }
 
   return NewBB;
 }
 

llvm/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll

 
 bb15:
   %tmp16 = load i8*, i8** %tmp, align 8
   %tmp17 = load i8, i8* %tmp16, align 1
   %tmp18 = icmp eq i8 %tmp17, 0
   br label %bb19
 
 ; CHECK-LABEL: bb6:
-; CHECK:         br i1 undef, label %bb15split, label %bb10
+; CHECK:         br i1 undef, label %bb15, label %bb10
 
-; CHECK-LABEL: bb15split:                                        ; preds = %bb6
-; CHECK-NEXT:    br label %bb15
+; CHECK-LABEL: bb15:                                        ; preds = %bb6
+; CHECK-NEXT:    br label %bb15.cont
 
-; CHECK-LABEL: bb15:
-; CHECK:         %tmp17 = phi i8 [ %tmp8, %bb15split ], [ %tmp17.pre, %bb1.bb15_crit_edge ]
+; CHECK-LABEL: bb15.cont:
+; CHECK:         %tmp17 = phi i8 [ %tmp17.pre, %bb1.bb15_crit_edge ], [ %tmp8, %bb15 ]
 
 bb19:                                             ; preds = %bb15
   ret i1 %tmp18
 }
 
 declare void @isalnum() nounwind inlinehint ssp

llvm/test/Transforms/GVN/critical-edge-split-indbr-pred-in-loop.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -gvn -S -verify-loop-info %s | FileCheck %s
+
+; Make sure we do not try to split blocks with indirectbr terminators in a
+; loop while trying to preserve loop info.
+
+declare i1 @cond()
+
+define i32 @foo(i8* %p1, i8* %p2, i32* %p3) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
+; CHECK:       loop.header:
+; CHECK-NEXT:    store i32 0, i32* [[P3:%.*]], align 4
+; CHECK-NEXT:    indirectbr i8* [[P1:%.*]], [label [[LOOP_LATCH1:%.*]], label %loop.latch2]
+; CHECK:       loop.latch1:
+; CHECK-NEXT:    [[C:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br i1 [[C]], label [[LOOP_HEADER]], label [[EXIT:%.*]]
+; CHECK:       loop.latch2:
+; CHECK-NEXT:    indirectbr i8* [[P2:%.*]], [label [[LOOP_HEADER]], label %exit]
+; CHECK:       exit:
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P3]], align 4
+; CHECK-NEXT:    ret i32 [[X]]
+;
+bb:
+  br label %loop.header
+
+loop.header:                                      ; preds = %loop.latch2, %loop.latch1, %bb
+  store i32 0, i32* %p3, align 4
+  indirectbr i8* %p1, [label %loop.latch1, label %loop.latch2]
+
+loop.latch1:                                      ; preds = %loop.header
+  %c = call i1 @cond()
+  br i1 %c, label %loop.header, label %exit
+
+loop.latch2:                                      ; preds = %loop.header
+  indirectbr i8* %p2, [label %loop.header, label %exit]
+
+exit:                                             ; preds = %loop.latch2, %loop.latch1
+  %x = load i32, i32* %p3, align 4
+  %y = add i32 %x, 0
+  ret i32 %y
+}

llvm/test/Transforms/Util/PR37334-break-crit-edges-require-dt.ll

 
 define void @f1() {
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY:%.*]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]
 ; CHECK:       for.cond.for.end_crit_edge:
-; CHECK-NEXT:    br label [[FOR_END:%.*]]
+; CHECK-NEXT:    br label [[FOR_END_CONT:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    br i1 true, label [[FOR_ENDSPLIT:%.*]], label [[FOR_INC:%.*]]
+; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_INC:%.*]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    br label [[FOR_COND]]
-; CHECK:       for.endsplit:
-; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
+; CHECK-NEXT:    br label [[FOR_END_CONT]]
+; CHECK:       for.end.cont:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   br i1 undef, label %for.body, label %for.end