Teach SplitBlockPredecessors how to handle landingpad blocks.

[igor-laevsky]

Summary

Currently SplitBlockPredecessors generates incorrect code in case if basic block we are going to split has a landingpad. Also seems like it is fairly common case among it's users to conditionally call either SplitBlockPredecessors or SplitLandingPadPredecessors. Because of this I think it is reasonable to add this condition directly into SplitBlockPredecessors.

[reames]

Minor comments inline. Once these are addressed, I'm willing to give an LGTM. As we discussed offline, I plan on waiting another day or two to give other interested parties time to comment.

include/llvm/Transforms/Utils/BasicBlockUtils.h

205 ↗

(On Diff #18704)

I'd suggest organizing the comment as:
This method returns <high level comment, true of each>. The specific transform performed depends on whether BB starts with a landingpad instruction.

If BB does not contain a landingpad ....

If BB does start with a landingpad ...

208 ↗

(On Diff #18704)

Given there is no longer a NumPreds argument, you can delete that part.

lib/Transforms/Utils/BasicBlockUtils.cpp

457 ↗

(On Diff #18704)

Given this is just duplicated from the header, delete the comment here.

480 ↗

(On Diff #18704)

Not sure it makes sense to add the extra suffix here. I'd just drop this.

[reames]

LGTM, per offline discussion, I will commit on your behalf.

llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h

 /// SplitBlock - Split the specified block at the specified instruction - every
 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
 /// to a new block.  The two blocks are joined by an unconditional branch and
 /// the loop info is updated.
 ///
 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt,
                        DominatorTree *DT = nullptr, LoopInfo *LI = nullptr);
 
-/// SplitBlockPredecessors - This method transforms BB by introducing a new
-/// basic block into the function, and moving some of the predecessors of BB to
-/// be predecessors of the new block.  The new predecessors are indicated by the
-/// Preds array, which has NumPreds elements in it.  The new block is given a
-/// suffix of 'Suffix'.  This function returns the new block.
+/// SplitBlockPredecessors - This method introduces at least one new basic block
+/// into the function and moves some of the predecessors of BB to be
+/// predecessors of the new block. The new predecessors are indicated by the
+/// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic
+/// block to which predecessors from Preds are now pointing.
+///
+/// If BB is a landingpad block then additional basicblock might be introduced.
+/// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
+/// details on this case.
 ///
 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
 /// In particular, it does not preserve LoopSimplify (because it's
 /// complicated to handle the case where one of the edges being split
 /// is an exit of a loop with other exits).
 ///
 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,

llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp

void LoopUnswitch::SplitExitEdges(Loop *L,
 
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
     BasicBlock *ExitBlock = ExitBlocks[i];
     SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
                                        pred_end(ExitBlock));
 
     // Although SplitBlockPredecessors doesn't preserve loop-simplify in
     // general, if we call it on all predecessors of all exits then it does.
-    if (!ExitBlock->isLandingPad()) {
-      SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa",
-                             /*AliasAnalysis*/ nullptr, DT, LI,
-                             /*PreserveLCSSA*/ true);
-    } else {
-      SmallVector<BasicBlock*, 2> NewBBs;
-      SplitLandingPadPredecessors(ExitBlock, Preds, ".us-lcssa", ".us-lcssa",
-                                  NewBBs, /*AliasAnalysis*/ nullptr, DT, LI,
-                                  /*PreserveLCSSA*/ true);
-    }
   }
 }
 
 /// UnswitchNontrivialCondition - We determined that the loop is profitable
 /// to unswitch when LIC equal Val.  Split it into loop versions and test the
 /// condition outside of either loop.  Return the loops created as Out1/Out2.
 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
                                                Loop *L) {

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
         NewPHI->addIncoming(V, IncomingBB);
       }
     }
 
     PN->addIncoming(NewPHI, NewBB);
   }
 }
 
-/// SplitBlockPredecessors - This method transforms BB by introducing a new
-/// basic block into the function, and moving some of the predecessors of BB to
-/// be predecessors of the new block.  The new predecessors are indicated by the
-/// Preds array, which has NumPreds elements in it.  The new block is given a
-/// suffix of 'Suffix'.
+/// SplitBlockPredecessors - This method introduces at least one new basic block
+/// into the function and moves some of the predecessors of BB to be
+/// predecessors of the new block. The new predecessors are indicated by the
+/// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic
+/// block to which predecessors from Preds are now pointing.
+///
+/// If BB is a landingpad block then additional basicblock might be introduced.
+/// It will have suffix of 'Suffix'+".split_lp".
+/// See SplitLandingPadPredecessors for more details on this case.
 ///
 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
 /// LoopInfo, and LCCSA but no other analyses. In particular, it does not
 /// preserve LoopSimplify (because it's complicated to handle the case where one
 /// of the edges being split is an exit of a loop with other exits).
 ///
 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
                                          ArrayRef<BasicBlock *> Preds,
                                          const char *Suffix, AliasAnalysis *AA,
                                          DominatorTree *DT, LoopInfo *LI,
                                          bool PreserveLCSSA) {
+  // For the landingpads we need to act a bit differently.
+  // Delegate this work to the SplitLandingPadPredecessors.
+  if (BB->isLandingPad()) {
+    SmallVector<BasicBlock*, 2> NewBBs;
+    std::string NewName = std::string(Suffix) + ".split-lp";
+
+    SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(),
+                                NewBBs, AA, DT, LI, PreserveLCSSA);
+    return NewBBs[0];
+  }
+
   // Create new basic block, insert right before the original block.
   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix,
                                          BB->getParent(), BB);
 
   // The new block unconditionally branches to the old block.
   BranchInst *BI = BranchInst::Create(BB, NewBB);
 
   // Move the edges from Preds to point to NewBB instead of BB.

llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp

if (!L->contains(P)) {         // Coming in from outside the loop?
 
       // Keep track of it.
       OutsideBlocks.push_back(P);
     }
   }
 
   // Split out the loop pre-header.
   BasicBlock *PreheaderBB;
-  if (!Header->isLandingPad()) {
-    PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader",
-                                         AA, DT, LI, PreserveLCSSA);
-  } else {
-    SmallVector<BasicBlock*, 2> NewBBs;
-    SplitLandingPadPredecessors(Header, OutsideBlocks, ".preheader",
-                                ".split-lp", NewBBs, AA, DT, LI, PreserveLCSSA);
-    PreheaderBB = NewBBs[0];
-  }
 
   PreheaderBB->getTerminator()->setDebugLoc(
                                       Header->getFirstNonPHI()->getDebugLoc());
   DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
                << PreheaderBB->getName() << "\n");
 
   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
   // code layout too horribly.
for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) {
     }
   }
 
   assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
   BasicBlock *NewExitBB = nullptr;
 
   bool PreserveLCSSA = PP->mustPreserveAnalysisID(LCSSAID);
 
-  if (Exit->isLandingPad()) {
-    SmallVector<BasicBlock*, 2> NewBBs;
-    SplitLandingPadPredecessors(Exit, LoopBlocks, ".loopexit", ".nonloopexit",
-                                NewBBs, AA, DT, LI, PreserveLCSSA);
-    NewExitBB = NewBBs[0];
-  } else {
-    NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", AA, DT,
-                                       LI, PreserveLCSSA);
-  }
 
   DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
                << NewExitBB->getName() << "\n");
   return NewExitBB;
 }
 
 /// Add the specified block, and all of its predecessors, to the specified set,
 /// if it's not already in there.  Stop predecessor traversal when we reach

llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp

static void ConnectProlog(Loop *L, Value *TripCount, unsigned Count,
   Instruction *InsertPt = PrologEnd->getTerminator();
   Instruction *BrLoopExit =
     new ICmpInst(InsertPt, ICmpInst::ICMP_ULT, TripCount,
                  ConstantInt::get(TripCount->getType(), Count));
   BasicBlock *Exit = L->getUniqueExitBlock();
   assert(Exit && "Loop must have a single exit block only");
   // Split the exit to maintain loop canonicalization guarantees
   SmallVector<BasicBlock*, 4> Preds(pred_begin(Exit), pred_end(Exit));
-  if (!Exit->isLandingPad()) {
-    SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", AA, DT, LI,
-                           P->mustPreserveAnalysisID(LCSSAID));
-  } else {
-    SmallVector<BasicBlock*, 2> NewBBs;
-    SplitLandingPadPredecessors(Exit, Preds, ".unr1-lcssa", ".unr2-lcssa",
-                                NewBBs, AA, DT, LI,
-                                P->mustPreserveAnalysisID(LCSSAID));
-  }
   // Add the branch to the exit block (around the unrolled loop)
   BranchInst::Create(Exit, NewPH, BrLoopExit, InsertPt);
   InsertPt->eraseFromParent();
 }
 
 /// Create a clone of the blocks in a loop and connect them together.
 /// If UnrollProlog is true, loop structure will not be cloned, otherwise a new
 /// loop will be created including all cloned blocks, and the iterator of it

llvm/trunk/test/Transforms/LoopSimplify/2011-12-14-LandingpadHeader.ll

 ; RUN: opt < %s -loop-simplify -S | FileCheck %s
 ; PR11575
 
 @catchtypeinfo = external unnamed_addr constant { i8*, i8*, i8* }
 
 define void @main() uwtable ssp {
 entry:
   invoke void @f1()
           to label %try.cont19 unwind label %catch
 
 ; CHECK: catch.preheader:
 ; CHECK-NEXT: landingpad
 ; CHECK: br label %catch
 
-; CHECK: catch.split-lp:
+; CHECK: catch.preheader.split-lp:
 ; CHECK-NEXT: landingpad
 ; CHECK: br label %catch
 
 catch:                                            ; preds = %if.else, %entry
   %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
           catch i8* bitcast ({ i8*, i8*, i8* }* @catchtypeinfo to i8*)
   invoke void @f3()
           to label %if.else unwind label %eh.resume