[GVN] Do not try to split critical edges with indbr preds in loop.

[fhahn]

Summary

splitCriticalEdges may crash while updating LI in case one of the
predecessors has a indbr and is in a different loop than the
predecessor, because it cannot split blocks with indbr terminators.

This crash was exposed by 189efe295b6e.

[efriedma]

There's a separate bailout "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE" earlier, so any block in the CriticalEdgePred has a non-indirectbr terminator. However, if LoadBB has any predecessor which is an indirectbr, even if it's not the edge we want to split, the call to llvm::SplitCriticalEdge fails. This is because it's trying to do something more than just split the critical edge. I guess here, it's trying to preserve LoopSimplify form: %exit is an exit block, so it should only have predecessors inside the loop.

It should be possible to preserve the invariant here. For the testcase, the resulting function looks something like the following. We create a new basic block exit.latch1 to split the edge. Then we split exit at the beginning of the block, before any non-PHI instructions. Then exit.latch1 branches to the split block. (See also llvm::SplitIndirectBrCriticalEdges.)

bb:
  br label %loop.header

loop.header:
  store i32 0, i32* %p3, align 4
  indirectbr i8* %p1, [label %loop.latch1, label %loop.latch2]

loop.latch1:
  %c = call i1 @cond()
  br i1 %c, label %loop.header, label %exit.latch1

loop.latch2:
  indirectbr i8* %p2, [label %loop.header, label %exit]

exit.latch1:
  br label %exit.split

exit:
  br label %exit.split

exit.split:
  %x = load i32, i32* %p3, align 4
  %y = add i32 %x, 0
  ret i32 %y

I'm a little skeptical it's a good idea to bail out of GVN, as opposed to fixing SplitCriticalEdge. If SplitCriticalEdge was private to GVN, maybe it would be okay. But as it is, I think it's a ticking time bomb if SplitCriticalEdge "randomly" crashes on certain edges due to undocumented constraints.

[fhahn]

In D81494#2083191, @efriedma wrote:

There's a separate bailout "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE" earlier, so any block in the CriticalEdgePred has a non-indirectbr terminator. However, if LoadBB has any predecessor which is an indirectbr, even if it's not the edge we want to split, the call to llvm::SplitCriticalEdge fails. This is because it's trying to do something more than just split the critical edge. I guess here, it's trying to preserve LoopSimplify form: %exit is an exit block, so it should only have predecessors inside the loop.

Exactly! Sorry for not making it clear in the description.

It should be possible to preserve the invariant here. For the testcase, the resulting function looks something like the following. We create a new basic block exit.latch1 to split the edge. Then we split exit at the beginning of the block, before any non-PHI instructions. Then exit.latch1 branches to the split block. (See also llvm::SplitIndirectBrCriticalEdges.)

Right, that should work. I tried, but unfortunately it means moving instructions to a different block & potentially introducing new PHIs and some users of SplitCriticalEdge do not seem to like it (especially the MemoryDependenceAnalysis caching....). I've put up the patch there D81584, but some of the issues are not resolved yet (and I am not sure if it is the best way forward at the moment, given that users seem not prepared for instructions being moved).

I'm a little skeptical it's a good idea to bail out of GVN, as opposed to fixing SplitCriticalEdge. If SplitCriticalEdge was private to GVN, maybe it would be okay. But as it is, I think it's a ticking time bomb if SplitCriticalEdge "randomly" crashes on certain edges due to undocumented constraints.

yes it seems a bit odd to have the check here in GVN. I've put up D81582, which updates SplitCriticalEdge to return nullptr before making any changes, if it would have to split a block with a indirectbr terminator. That should ensure we do not run into the crash for other users. GVN itself seems to bail out on blocks it *things* SplitCriticalEdge cannot handle, but that seems a bit fragile in general.

[fhahn]

This has since been fixed.

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;
+
+  bool HasLI = this->LI;
+  // Keep track if there are predecessors in a different loop than LoadBB with
+  // indbr terminators. We cannot use splitCriticalEdges, as we might have to
+  // split a predecessor with an indbr, which is not supported.
+  Loop *LoadBBL = HasLI ? this->LI->getLoopFor(LoadBB) : nullptr;
+  bool PredHasIndirectBr = false;
   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;
     }
 
+    PredHasIndirectBr |= HasLI ? this->LI->getLoopFor(Pred) != LoadBBL &&
+                                     isa<IndirectBrInst>(Pred->getTerminator())
+                               : false;
     if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks, 0)) {
       continue;
     }
 
     if (Pred->getTerminator()->getNumSuccessors() != 1) {
       if (isa<IndirectBrInst>(Pred->getTerminator())) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 
   // If this load is unavailable in multiple predecessors, reject it.
   // FIXME: If we could restructure the CFG, we could make a common pred with
   // all the preds that don't have an available LI and insert a new load into
   // that one block.
   if (NumUnavailablePreds != 1)
       return false;
 
+  if (PredHasIndirectBr) {
+    LLVM_DEBUG(dbgs() << "COULD NOT PRE LOAD BECAUSE INDBR EDGE IN LOOP\n");
+    return false;
+  }
+
   // Split critical edges, and update the unavailable predecessors accordingly.
   for (BasicBlock *OrigPred : CriticalEdgePred) {
     BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
     assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
     PredLoads[NewPred] = nullptr;
     LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
                       << LoadBB->getName() << '\n');
   }

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
+}