Do not select EhPad BB in MachineBlockPlacement when there is regular BB to schedule

[deadalnix]

Summary

EHPad BB are not entered the classic way and therefor do not need to be placed after their predecessors. This patch make sure EHPad BB are not chosen amongst successors to form chains, and are selected as last resort when selecting the best candidate.

EHPad are scheduled in reverse probability order in order to have them flow into each others naturally.

[deadalnix]

@rafael , This is screwing with test/CodeGen/PowerPC/pr25802.ll , I'm not sure what the problem is and what this test is checking. Can you have a look ?

[deadalnix]

As per discussion with @rafael , deleting pr25802.ll

[deadalnix]

looks like you were involved in D17830 , so you may want to review that one.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

545 ↗

(On Diff #49246)

The new code really lowers the readability. Can you describe the algorithm here? Is it

1. if the best non eh block exists, return it; otherwise
2. return the least likely eh pad?

if that is the case, why not simply skip eh blocks in the original worklist loop. If the best bb is found return it, otherwise have another helper loop to find the least likely eh pad?

[chandlerc]

lib/CodeGen/MachineBlockPlacement.cpp

545 ↗

(On Diff #49246)

I agree that this makes it essentially unreadable. =/

I'd suggest instead to maintain two worklists, one of non-EH-pads, and another of EH-pads. Then you can write the direct loop over each, and you can even put the algorithm David suggested in a comment on the second loop. =]

Note that looping over the worklist twice could be quite expensive, which is why I'd suggest two lists.

[deadalnix]

lib/CodeGen/MachineBlockPlacement.cpp

545 ↗

(On Diff #49246)

@davisxl : Yes, that is exactly what this is doing. Going over the ehpad starting with the least likely makes them flow into each other more naturally. Consider you have something like:

hotehpad:
  br exit  // fallthrought
exit:
  ret
coldehpad:
  br exit

vs

coldehpad:
  br exit
hotehpad:
  br exit  // fallthrought
exit:
  ret

@chandlerc , ok for the 2 worklists.

[deadalnix]

Use a separate worklist for ehpads

[deadalnix]

ping

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

420 ↗

(On Diff #49981)

Why is it always good to skip ehpad? With real profile data, can ehpad be 'hotter' than some of the cold blocks?

561 ↗

(On Diff #49981)

Your patch forces ehpad to be skipped when doing regular layout which is fine. However how is this following layout (enabled by this strategy)

entry, hot, then, cold, clp, hlp, lpret

better than:

entry, hot, then, cold, hlp, lpret, clp?

Of course, both are better than the following:

entry, hot, then, cold, hlp, clp, lpret

[deadalnix]

lib/CodeGen/MachineBlockPlacement.cpp

420 ↗

(On Diff #49981)

There is no point in eagerly scheduling ehpadsas they are never reached the "conventional" way. When you reach an EHPad, you've gone throught the personality function and a bunch of other runtime code, which makes it pretty much irrelevant where it is. Even if the EHPad ends up hotter than some other BB, the way you get to the EHPad makes it irrelevant if it is scheduled eagerly.

There is also considerations linked to D17555 , as to make sure all EHPads ends up on the same side of the split, which simplify dramatically LSDA generation.

561 ↗

(On Diff #49981)

It is very common for ehpad to flow into each others and I get a ton of backedge scheduling hotlp before coldlp, and potentially longer jumps overall. I'm not too opposed to go

entry, hot, then, cold, hlp, lpret, clp

But the other way around is more readable and easier to understand, and, as mentioned, it doesn't really matter where the landing pad starts so there is no real big drawback schedulign them the other way around.

Note that without that patch, you don't get

entry, hot, then, cold, hlp, clp, lpret

but

entry, hot, then, hlp, lpret, cold, clp

Which really doesn't make any sense as you end up having to jump over lp to reach cold, which is never a win, even if lp is hotter than cold.

[davidxl]

Sorry for the delay -- for some reason I did not receive the email notification at all..

lib/CodeGen/MachineBlockPlacement.cpp

420 ↗

(On Diff #49981)

This makes total sense.

563 ↗

(On Diff #49981)

Since there is no fundamental difference between
entry, hot, then, cold, hlp, lpret, clp vs
entry, hot, then, cold, clp, hlp, lpret

I think change at line 563 should be removed -- it is a distraction to the main code IMO. Some of the test changes can also be avoided.

[deadalnix]

lib/CodeGen/MachineBlockPlacement.cpp

563 ↗

(On Diff #49981)

It can be done if you feel strongly about it. But please consider the following. Quite often, ehpad code flow into each others. See pseudocode :

  invoke @foo to %then unwind label %outerlp
then:
  invoke @foo to %exit unwind label %innerlp
exit:
  ret void
innerlp:
  landingpad { i8*, i32 } cleanup
  br %innercleanup
innercleanup:
  ; Do inner cleanup
  br %outercleanup
outerlp:
  landingpad { i8*, i32 } cleanup
  br %outercleanup
outercleanup:
  ; Do outer cleanup
  resume

Note that this is typical RAII kind of code and/or nested try, or any combiantion of these. Long story short, this kind of pattern are very common.

Now, if you compute the probabilities, outerlp is consider more probable than innerlp, as the preceding invoke is itself more probable. That means that unwinding code ends up being scheduled completely backward every time. Here you'd get :

outerlp, outercleanup, innerlp, innercleanup // which branch to outercleanup

This is the most simple case, but it if very common to have more level of nesting than that in the unwind path and it gets worse. You end with a "corkscrew" like basic block scheduling which I don't think is good.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

563 ↗

(On Diff #49981)

This is a convincing example that shows benefit of using this layout for lp. I suggest adding a small test case to cover this (i.e, inner scope ehpad 'flows' into outer ehpads in the final layout).

By the way, I think the fillworklist change can be separated out as a NFC refactoring.

[deadalnix]

Extracted NFC change into D18077
Added a test for the corkscrew ehpad scheduling mentionned in the comments

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

621 ↗

(On Diff #50397)

suggest this change:

if (Chain.UnschedulePredecesors == 0) {

MBB = *Chain.begin();
auto &WorkList = (MBB->isEHPad() ? EHPadWorkList: BlockWorkList);
WorkList.push_back(MBB);

}

test/CodeGen/X86/block-placement.ll

1145 ↗

(On Diff #50397)

Where is innnercleanup?

1159 ↗

(On Diff #50397)

Can you shuffle the lp labels into different orders in the original source?

[deadalnix]

test/CodeGen/X86/block-placement.ll

1145 ↗

(On Diff #50397)

It end up being merged in innrerlp by some pass along the road.

1159 ↗

(On Diff #50397)

Sure, will do.

[deadalnix]

Scramble lp blocks in the test

[davidxl]

Please rebase the patch after the refactoring code is in.

test/CodeGen/X86/block-placement.ll

1137 ↗

(On Diff #50561)

Please use more plain word for the comments of this test case.

[deadalnix]

Add explaination for the scheduling of EHPad being from the least probably one to the most probable one, including some ASCII art.

Rebase on top of D18077

[deadalnix]

Ping ?

[davidxl]

test/CodeGen/X86/seh-safe-div-win32.ll

68 ↗

(On Diff #51223)

Not sure if it matters in practice. It seems that the changes in layout behavior for catch handlers as demonstrated in this test case may not be the target problem this patch intends to solve (but changed due to a side effect). In this case, it seems more natural to have handler0 laid before handler1. Do you think this is an issue?

[deadalnix]

test/CodeGen/X86/seh-safe-div-win32.ll

68 ↗

(On Diff #51223)

I'm not sure it changes anything in practice here as the 2 landing pads do not flow into each others. The most important part seems to me that __try.cont is scheduled before the landingpads. That being said, maybe we want a bit more tweaking for windows style EH if it turns out that this is a problem.

[davidxl]

test/CodeGen/X86/seh-safe-div-win32.ll

68 ↗

(On Diff #51223)

The patch is probably good as it is now. Regarding this particular case, what kind of tweaking do you have in mind (just in case it is needed which I hope not)?

[deadalnix]

test/CodeGen/X86/seh-safe-div-win32.ll

68 ↗

(On Diff #51223)

I'm not sure at this stage. I'd like to establish this is actually a problem worth solving before speculating on a possible solution.

[deadalnix]

@davidxl is there a reason to not merge this ? If not I'd like to proceed.

[davidxl]

I am ok with the patch -- but please wait a little longer in case other reviewers want to chime in.

[deadalnix]

Rebase and resolve conflict. Also ping ?

[deadalnix]

Ping ?

[deadalnix]

Rebase and resolve conflicts. If nobody has anythign against this, I'd like to merge it.

[chandlerc]

I still have some unanswered questions here, but I don't think we need to solve them in this patch, it seems like a pretty strict improvement as-is. LGTM.

Also, thanks to David for doing the lion's share of the review here. =]

lib/CodeGen/MachineBlockPlacement.cpp

376 ↗

(On Diff #52883)

80-columns / clang-format

567–580 ↗

(On Diff #52883)

This goal makes perfect sense, but I'm not 100% convinced that the probabilities are a really reliable way of achieving it. I don't tihnk you need to solve all of this right away though, maybe just leave a FIXME that we should have a more principled way of ensuring nice layout of nested cleanups?

1151 ↗

(On Diff #52883)

80-columns / clang-format

[deadalnix]

Format and add comment about the cleanup layout.

llvm/trunk/lib/CodeGen/MachineBlockPlacement.cpp

class MachineBlockPlacement : public MachineFunctionPass {
   /// This mapping allows efficiently moving from any given basic block to the
   /// BlockChain it participates in, if any. We use it to, among other things,
   /// allow implicitly defining edges between chains as the existing edges
   /// between basic blocks.
   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 
   void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
                            SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
+                           SmallVectorImpl<MachineBasicBlock *> &EHPadWorkList,
                            const BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
                                          BlockChain &Chain,
                                          const BlockFilterSet *BlockFilter);
   MachineBasicBlock *
   selectBestCandidateBlock(BlockChain &Chain,
                            SmallVectorImpl<MachineBasicBlock *> &WorkList);
   MachineBasicBlock *
   getFirstUnplacedBlock(MachineFunction &F, const BlockChain &PlacedChain,
                         MachineFunction::iterator &PrevUnplacedBlockIt,
                         const BlockFilterSet *BlockFilter);
 
   /// \brief Add a basic block to the work list if it is apropriate.
   ///
   /// If the optional parameter BlockFilter is provided, only MBB
   /// present in the set will be added to the worklist. If nullptr
   /// is provided, no filtering occurs.
   void fillWorkLists(MachineBasicBlock *MBB,
                      SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
                      SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
+                     SmallVectorImpl<MachineBasicBlock *> &EHPadWorkList,
                      const BlockFilterSet *BlockFilter);
   void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
                   SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
+                  SmallVectorImpl<MachineBasicBlock *> &EHPadWorkList,
                   const BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *findBestLoopTop(MachineLoop &L,
                                      const BlockFilterSet &LoopBlockSet);
   MachineBasicBlock *findBestLoopExit(MachineFunction &F, MachineLoop &L,
                                       const BlockFilterSet &LoopBlockSet);
   BlockFilterSet collectLoopBlockSet(MachineFunction &F, MachineLoop &L);
   void buildLoopChains(MachineFunction &F, MachineLoop &L);
   void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB,

 ///
 /// When a chain is being merged into the "placed" chain, this routine will
 /// quickly walk the successors of each block in the chain and mark them as
 /// having one fewer active predecessor. It also adds any successors of this
 /// chain which reach the zero-predecessor state to the worklist passed in.
 void MachineBlockPlacement::markChainSuccessors(
     BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
+    SmallVectorImpl<MachineBasicBlock *> &EHPadWorkList,
     const BlockFilterSet *BlockFilter) {
   // Walk all the blocks in this chain, marking their successors as having
   // a predecessor placed.
   for (MachineBasicBlock *MBB : Chain) {
     // Add any successors for which this is the only un-placed in-loop
     // predecessor to the worklist as a viable candidate for CFG-neutral
     // placement. No subsequent placement of this block will violate the CFG
     // shape, so we get to use heuristics to choose a favorable placement.
     for (MachineBasicBlock *Succ : MBB->successors()) {
       if (BlockFilter && !BlockFilter->count(Succ))
         continue;
       BlockChain &SuccChain = *BlockToChain[Succ];
       // Disregard edges within a fixed chain, or edges to the loop header.
       if (&Chain == &SuccChain || Succ == LoopHeaderBB)
         continue;
 
       // This is a cross-chain edge that is within the loop, so decrement the
       // loop predecessor count of the destination chain.
-      if (SuccChain.UnscheduledPredecessors > 0 && --SuccChain.UnscheduledPredecessors == 0)
-        BlockWorkList.push_back(*SuccChain.begin());
+      if (SuccChain.UnscheduledPredecessors == 0 ||
+          --SuccChain.UnscheduledPredecessors > 0)
+        continue;
+
+      auto *MBB = *SuccChain.begin();
+      if (MBB->isEHPad())
+        EHPadWorkList.push_back(MBB);
+      else
+        BlockWorkList.push_back(MBB);
     }
   }
 }
 
 /// \brief Select the best successor for a block.
 ///
 /// This looks across all successors of a particular block and attempts to
 /// select the "best" one to be the layout successor. It only considers direct
MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
   // due to CFG constraint (the probability of C->D is not greater than
   // HotProb). If we exclude E that is not in BlockFilter when calculating the
   // probability of C->D, D will be selected and we will get A C D B as the
   // layout of this loop.
   auto AdjustedSumProb = BranchProbability::getOne();
   SmallVector<MachineBasicBlock *, 4> Successors;
   for (MachineBasicBlock *Succ : BB->successors()) {
     bool SkipSucc = false;
-    if (BlockFilter && !BlockFilter->count(Succ)) {
+    if (Succ->isEHPad() || (BlockFilter && !BlockFilter->count(Succ))) {
       SkipSucc = true;
     } else {
       BlockChain *SuccChain = BlockToChain[Succ];
       if (SuccChain == &Chain) {
         SkipSucc = true;
       } else if (Succ != *SuccChain->begin()) {
         DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> Mid chain!\n");
         continue;
MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
   // FIXME: If this shows up on profiles, it could be folded (at the cost of
   // some code complexity) into the loop below.
   WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(),
                                 [&](MachineBasicBlock *BB) {
                                   return BlockToChain.lookup(BB) == &Chain;
                                 }),
                  WorkList.end());
 
+  if (WorkList.empty())
+    return nullptr;
+
+  bool IsEHPad = WorkList[0]->isEHPad();
+
   MachineBasicBlock *BestBlock = nullptr;
   BlockFrequency BestFreq;
   for (MachineBasicBlock *MBB : WorkList) {
+    assert(MBB->isEHPad() == IsEHPad);
+
     BlockChain &SuccChain = *BlockToChain[MBB];
     if (&SuccChain == &Chain)
       continue;
 
     assert(SuccChain.UnscheduledPredecessors == 0 && "Found CFG-violating block");
 
     BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB);
     DEBUG(dbgs() << "    " << getBlockName(MBB) << " -> ";
           MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n");
-    if (BestBlock && BestFreq >= CandidateFreq)
+
+    // For ehpad, we layout the least probable first as to avoid jumping back
+    // from least probable landingpads to more probable ones.
+    //
+    // FIXME: Using probability is probably (!) not the best way to achieve
+    // this. We should probably have a more principled approach to layout
+    // cleanup code.
+    //
+    // The goal is to get:
+    //
+    //                 +--------------------------+
+    //                 |                          V
+    // InnerLp -> InnerCleanup    OuterLp -> OuterCleanup -> Resume
+    //
+    // Rather than:
+    //
+    //                 +-------------------------------------+
+    //                 V                                     |
+    // OuterLp -> OuterCleanup -> Resume     InnerLp -> InnerCleanup
+    if (BestBlock && (IsEHPad ^ (BestFreq >= CandidateFreq)))
       continue;
+
     BestBlock = MBB;
     BestFreq = CandidateFreq;
   }
+
   return BestBlock;
 }
 
 /// \brief Retrieve the first unplaced basic block.
 ///
 /// This routine is called when we are unable to use the CFG to walk through
 /// all of the basic blocks and form a chain due to unnatural loops in the CFG.
 /// We walk through the function's blocks in order, starting from the
MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock(
   }
   return nullptr;
 }
 
 void MachineBlockPlacement::fillWorkLists(
     MachineBasicBlock *MBB,
     SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
+    SmallVectorImpl<MachineBasicBlock *> &EHPadWorkList,
     const BlockFilterSet *BlockFilter = nullptr) {
   BlockChain &Chain = *BlockToChain[MBB];
   if (!UpdatedPreds.insert(&Chain).second)
     return;
 
   assert(Chain.UnscheduledPredecessors == 0);
   for (MachineBasicBlock *ChainBB : Chain) {
     assert(BlockToChain[ChainBB] == &Chain);
     for (MachineBasicBlock *Pred : ChainBB->predecessors()) {
       if (BlockFilter && !BlockFilter->count(Pred))
         continue;
       if (BlockToChain[Pred] == &Chain)
         continue;
       ++Chain.UnscheduledPredecessors;
     }
   }
 
-  if (Chain.UnscheduledPredecessors == 0)
-    BlockWorkList.push_back(*Chain.begin());
+  if (Chain.UnscheduledPredecessors != 0)
+    return;
+
+  MBB = *Chain.begin();
+  if (MBB->isEHPad())
+    EHPadWorkList.push_back(MBB);
+  else
+    BlockWorkList.push_back(MBB);
 }
 
 void MachineBlockPlacement::buildChain(
     MachineBasicBlock *BB, BlockChain &Chain,
     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
+    SmallVectorImpl<MachineBasicBlock *> &EHPadWorkList,
     const BlockFilterSet *BlockFilter) {
   assert(BB);
   assert(BlockToChain[BB] == &Chain);
   MachineFunction &F = *BB->getParent();
   MachineFunction::iterator PrevUnplacedBlockIt = F.begin();
 
   MachineBasicBlock *LoopHeaderBB = BB;
-  markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter);
+  markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, EHPadWorkList,
+                      BlockFilter);
   BB = *std::prev(Chain.end());
   for (;;) {
     assert(BB);
     assert(BlockToChain[BB] == &Chain);
     assert(*std::prev(Chain.end()) == BB);
 
     // Look for the best viable successor if there is one to place immediately
     // after this block.
     MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter);
 
     // If an immediate successor isn't available, look for the best viable
     // block among those we've identified as not violating the loop's CFG at
     // this point. This won't be a fallthrough, but it will increase locality.
     if (!BestSucc)
       BestSucc = selectBestCandidateBlock(Chain, BlockWorkList);
+    if (!BestSucc)
+      BestSucc = selectBestCandidateBlock(Chain, EHPadWorkList);
 
     if (!BestSucc) {
       BestSucc =
           getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, BlockFilter);
       if (!BestSucc)
         break;
 
       DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the "
                       "layout successor until the CFG reduces\n");
     }
 
     // Place this block, updating the datastructures to reflect its placement.
     BlockChain &SuccChain = *BlockToChain[BestSucc];
     // Zero out UnscheduledPredecessors for the successor we're about to merge in case
     // we selected a successor that didn't fit naturally into the CFG.
     SuccChain.UnscheduledPredecessors = 0;
     DEBUG(dbgs() << "Merging from " << getBlockName(BB) << " to "
                  << getBlockName(BestSucc) << "\n");
-    markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter);
+    markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, EHPadWorkList,
+                        BlockFilter);
     Chain.merge(BestSucc, &SuccChain);
     BB = *std::prev(Chain.end());
   }
 
   DEBUG(dbgs() << "Finished forming chain for header block "
                << getBlockName(*Chain.begin()) << "\n");
 }
 

 void MachineBlockPlacement::buildLoopChains(MachineFunction &F,
                                             MachineLoop &L) {
   // First recurse through any nested loops, building chains for those inner
   // loops.
   for (MachineLoop *InnerLoop : L)
     buildLoopChains(F, *InnerLoop);
 
   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
+  SmallVector<MachineBasicBlock *, 16> EHPadWorkList;
   BlockFilterSet LoopBlockSet = collectLoopBlockSet(F, L);
 
   // Check if we have profile data for this function. If yes, we will rotate
   // this loop by modeling costs more precisely which requires the profile data
   // for better layout.
   bool RotateLoopWithProfile =
       PreciseRotationCost && F.getFunction()->getEntryCount();
 
void MachineBlockPlacement::buildLoopChains(MachineFunction &F,
   // FIXME: This is a really lame way of walking the chains in the loop: we
   // walk the blocks, and use a set to prevent visiting a particular chain
   // twice.
   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
   assert(LoopChain.UnscheduledPredecessors == 0);
   UpdatedPreds.insert(&LoopChain);
 
   for (MachineBasicBlock *LoopBB : LoopBlockSet)
-    fillWorkLists(LoopBB, UpdatedPreds, BlockWorkList, &LoopBlockSet);
+    fillWorkLists(LoopBB, UpdatedPreds, BlockWorkList, EHPadWorkList,
+                  &LoopBlockSet);
 
-  buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet);
+  buildChain(LoopTop, LoopChain, BlockWorkList, EHPadWorkList, &LoopBlockSet);
 
   if (RotateLoopWithProfile)
     rotateLoopWithProfile(LoopChain, L, LoopBlockSet);
   else
     rotateLoop(LoopChain, ExitingBB, LoopBlockSet);
 
   DEBUG({
     // Crash at the end so we get all of the debugging output first.
if (OutlineOptionalBranches) {
     }
   }
 
   // Build any loop-based chains.
   for (MachineLoop *L : *MLI)
     buildLoopChains(F, *L);
 
   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
+  SmallVector<MachineBasicBlock *, 16> EHPadWorkList;
 
   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
   for (MachineBasicBlock &MBB : F)
-    fillWorkLists(&MBB, UpdatedPreds, BlockWorkList);
+    fillWorkLists(&MBB, UpdatedPreds, BlockWorkList, EHPadWorkList);
 
   BlockChain &FunctionChain = *BlockToChain[&F.front()];
-  buildChain(&F.front(), FunctionChain, BlockWorkList);
+  buildChain(&F.front(), FunctionChain, BlockWorkList, EHPadWorkList);
 
 #ifndef NDEBUG
   typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType;
 #endif
   DEBUG({
     // Crash at the end so we get all of the debugging output first.
     bool BadFunc = false;
     FunctionBlockSetType FunctionBlockSet;

llvm/trunk/test/CodeGen/PowerPC/pr25802.ll

-; RUN: llc < %s | FileCheck %s
-; CHECK: .long   .Ltmp9-.Ltmp8         #   Call between .Ltmp8 and .Ltmp9
-
-; We used to crash in filetype=obj when computing a negative value.
-; RUN: llc -filetype=obj < %s
-
-target triple = "powerpc--netbsd"
-@_ZTI1I = external constant { i8*, i8* }
-define void @f(i8 %foo, i32 %bar) personality i8* bitcast (void ()* @g to i8*) {
-  invoke void @g()
-          to label %try.cont unwind label %lpad
-lpad:                                             ; preds = %0
-  %tmp = landingpad { i8*, i32 }
-          catch i8* bitcast ({ i8*, i8* }* @_ZTI1I to i8*)
-  br i1 undef, label %catch10, label %catch
-catch10:                                          ; preds = %lpad
-  %tmp8 = load i32, i32* undef, align 4
-  %conv.i.i = zext i8 %foo to i32
-  %cond.i.i = select i1 undef, i32 %conv.i.i, i32 %tmp8
-  invoke void @_Z24__put_character_sequenceIccEvR1AIT_T0_Ej(i32 %cond.i.i)
-          to label %invoke.cont20 unwind label %lpad15
-invoke.cont20:                                    ; preds = %catch10
-  ret void
-try.cont:                                         ; preds = %0
-  ret void
-catch:                                            ; preds = %lpad
-  %tmp14 = load i32, i32* undef, align 4
-  %conv.i.i34 = zext i8 %foo to i32
-  %cond.i.i35 = select i1 undef, i32 %conv.i.i34, i32 %tmp14
-  invoke void @_Z24__put_character_sequenceIccEvR1AIT_T0_Ej(i32 %cond.i.i35)
-          to label %invoke.cont8 unwind label %lpad3
-invoke.cont8:                                     ; preds = %call2.i.i.noexc36
-  ret void
-lpad3:                                            ; preds = %call2.i.i.noexc36, %catch
-  %tmp16 = landingpad { i8*, i32 }
-          cleanup
-  invoke void @g()
-          to label %eh.resume unwind label %terminate.lpad
-lpad15:                                           ; preds = %catch10
-  %tmp19 = landingpad { i8*, i32 }
-          cleanup
-  invoke void @g()
-          to label %eh.resume unwind label %terminate.lpad
-eh.resume:                                        ; preds = %lpad15, %lpad3
-  ret void
-terminate.lpad:                                   ; preds = %lpad15, %lpad3
-  %tmp22 = landingpad { i8*, i32 }
-          catch i8* null
-  ret void
-}
-declare void @g()
-declare void @_Z24__put_character_sequenceIccEvR1AIT_T0_Ej(i32)

llvm/trunk/test/CodeGen/X86/block-placement.ll

else:
   %gep2 = getelementptr i32, i32* %a, i32 2
   %val2 = load i32, i32* %gep2
   br label %exit
 
 exit:
   %ret = phi i32 [ %val1, %then ], [ %val2, %else ]
   ret i32 %ret
 }
+
+; Make sure we put landingpads out of the way.
+declare i32 @pers(...)
+
+declare i32 @foo();
+
+declare i32 @bar();
+
+define i32 @test_lp(i32 %a) personality i32 (...)* @pers {
+; CHECK-LABEL: test_lp:
+; CHECK: %entry
+; CHECK: %hot
+; CHECK: %then
+; CHECK: %cold
+; CHECK: %coldlp
+; CHECK: %hotlp
+; CHECK: %lpret
+entry:
+  %0 = icmp sgt i32 %a, 1
+  br i1 %0, label %hot, label %cold, !prof !4
+
+hot:
+  %1 = invoke i32 @foo()
+          to label %then unwind label %hotlp
+
+cold:
+  %2 = invoke i32 @bar()
+          to label %then unwind label %coldlp
+
+then:
+  %3 = phi i32 [ %1, %hot ], [ %2, %cold ]
+  ret i32 %3
+
+hotlp:
+  %4 = landingpad { i8*, i32 }
+          cleanup
+  br label %lpret
+
+coldlp:
+  %5 = landingpad { i8*, i32 }
+          cleanup
+  br label %lpret
+
+lpret:
+  %6 = phi i32 [-1, %hotlp], [-2, %coldlp]
+  %7 = add i32 %6, 42
+  ret i32 %7
+}
+
+!4 = !{!"branch_weights", i32 65536, i32 0}
+
+; Make sure that ehpad are scheduled from the least probable one
+; to the most probable one. See selectBestCandidateBlock as to why.
+declare void @clean();
+
+define void @test_flow_unwind() personality i32 (...)* @pers {
+; CHECK-LABEL: test_flow_unwind:
+; CHECK: %entry
+; CHECK: %then
+; CHECK: %exit
+; CHECK: %innerlp
+; CHECK: %outerlp
+; CHECK: %outercleanup
+entry:
+  %0 = invoke i32 @foo()
+          to label %then unwind label %outerlp
+
+then:
+  %1 = invoke i32 @bar()
+          to label %exit unwind label %innerlp
+
+exit:
+  ret void
+
+innerlp:
+  %2 = landingpad { i8*, i32 }
+          cleanup
+  br label %innercleanup
+
+outerlp:
+  %3 = landingpad { i8*, i32 }
+          cleanup
+  br label %outercleanup
+
+outercleanup:
+  %4 = phi { i8*, i32 } [%2, %innercleanup], [%3, %outerlp]
+  call void @clean()
+  resume { i8*, i32 } %4
+
+innercleanup:
+  call void @clean()
+  br label %outercleanup
+}

llvm/trunk/test/CodeGen/X86/seh-safe-div-win32.ll

 ; CHECK: leal [[rloc]],
 ; CHECK: calll _try_body
 ; CHECK: [[cont_bb:LBB0_[0-9]+]]:
 ; CHECK: movl [[rloc]], %eax
 ; CHECK: retl
 
 ; Landing pad code
 
-; CHECK: [[handler0:LBB0_[0-9]+]]: # %handler0
+; CHECK: [[handler1:LBB0_[0-9]+]]: # %handler1
 ;   Restore SP
 ; CHECK: movl {{.*}}(%ebp), %esp
 ; CHECK: calll _puts
 ; CHECK: jmp [[cont_bb]]
 
-; CHECK: [[handler1:LBB0_[0-9]+]]: # %handler1
+; CHECK: [[handler0:LBB0_[0-9]+]]: # %handler0
 ;   Restore SP
 ; CHECK: movl {{.*}}(%ebp), %esp
 ; CHECK: calll _puts
 ; CHECK: jmp [[cont_bb]]
 
 ; CHECK: .section .xdata,"dr"
 ; CHECK: L__ehtable$safe_div:
 ; CHECK-NEXT: .long -1

llvm/trunk/test/CodeGen/X86/seh-safe-div.ll

 ; CHECK: callq try_body
 ; CHECK-NEXT: .Ltmp1
 ; CHECK: [[cont_bb:\.LBB0_[0-9]+]]:
 ; CHECK: movl [[rloc]], %eax
 ; CHECK: retq
 
 ; Landing pad code
 
-; CHECK: [[handler0:\.LBB0_[0-9]+]]: # %handler0
+; CHECK: [[handler1:\.LBB0_[0-9]+]]: # %handler1
 ; CHECK: callq puts
-; CHECK: movl $-1, [[rloc]]
+; CHECK: movl $-2, [[rloc]]
 ; CHECK: jmp [[cont_bb]]
 
-; CHECK: [[handler1:\.LBB0_[0-9]+]]: # %handler1
+; CHECK: [[handler0:\.LBB0_[0-9]+]]: # %handler0
 ; CHECK: callq puts
-; CHECK: movl $-2, [[rloc]]
+; CHECK: movl $-1, [[rloc]]
 ; CHECK: jmp [[cont_bb]]
 
 ; CHECK: .seh_handlerdata
 ; CHECK-NEXT: .Lsafe_div$parent_frame_offset
 ; CHECK-NEXT: .long (.Llsda_end0-.Llsda_begin0)/16
 ; CHECK-NEXT: .Llsda_begin0:
 ; CHECK-NEXT: .long .Ltmp0@IMGREL+1
 ; CHECK-NEXT: .long .Ltmp1@IMGREL+1

llvm/trunk/test/CodeGen/X86/win-catchpad.ll

 ; X86: movl $0, -{{[0-9]+}}(%ebp)
 ; X86: leal -[[local_offs:[0-9]+]](%ebp), %[[addr_reg:[a-z]+]]
 ; X86-DAG: pushl %[[addr_reg]]
 ; X86-DAG: pushl $1
 ; X86: calll _f
 ; X86: [[contbb:LBB0_[0-9]+]]: # %try.cont
 ; X86: retl
 
-; X86: [[restorebb1:LBB0_[0-9]+]]: # Block address taken
-; X86-NEXT:                        # %handler1
-; X86-NEXT: addl $12, %ebp
-; X86: jmp [[contbb]]
-
 ; FIXME: These should be de-duplicated.
 ; X86: [[restorebb2:LBB0_[0-9]+]]: # Block address taken
 ; X86-NEXT:                        # %handler2
 ; X86-NEXT: addl $12, %ebp
 ; X86: jmp [[contbb]]
 
+; X86: [[restorebb1:LBB0_[0-9]+]]: # Block address taken
+; X86-NEXT:                        # %handler1
+; X86-NEXT: addl $12, %ebp
+; X86: jmp [[contbb]]
+
 ; X86: "?catch$[[catch1bb:[0-9]+]]@?0?try_catch_catch@4HA":
 ; X86: LBB0_[[catch1bb]]: # %handler1{{$}}
 ; X86: pushl %ebp
 ; X86: subl $8, %esp
 ; X86: addl $12, %ebp
 ; X86: movl %esp, -[[sp_offset]](%ebp)
 ; X86-DAG: movl -32(%ebp), %[[e_reg:[a-z]+]]
 ; X86-DAG: leal -[[local_offs]](%ebp), %[[addr_reg:[a-z]+]]