[WinEHPrepare] Add rudimentary support for the new EH instructions

[majnemer]

Summary

This adds somewhat basic preparation functionality including:

• Formation of funclets via coloring basic blocks.
• Cloning of polychromatic blocks to ensure that funclets have unique program counters.
• Demotion of values used between different funclets.
• Some amount of cleanup once we have removed predecessors from basic blocks.
• Verification that we are left with a CFG that makes some amount of sense.

N.B. Arguments and numbering still need to be done.

[majnemer]

• handle phi nodes
• Handle PHI nodes prefacing EH pads too

[majnemer]

• handle phi nodes
• Handle PHI nodes prefacing EH pads too
• PHIs don't need to be postprocessed

[rnk]

The demotion logic seems pretty heinous, but I hear improvements are on the way, so I'm not going to dig too much into it.

lib/CodeGen/WinEHPrepare.cpp

2922

I expect many cleanup funclets will be one BB. SmallVector<1>?

2926–2927

pop_back_val?

2942–2947

I think you can remove the IsCatch and IsCleanup predicates and stop at either kind of ret. If the CFG gets mangled, this will stop us from going off into the weeds earlier.

3244

Do you want these in a release build? #ifndef NDEBUG?

lib/CodeGen/WinEHPrepare.cpp

 
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/TinyPtrVector.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LibCallSemantics.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/CodeGen/WinEHFuncInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
private:
   void mapLandingPadBlocks(LandingPadInst *LPad, LandingPadActions &Actions);
   CatchHandler *findCatchHandler(BasicBlock *BB, BasicBlock *&NextBB,
                                  VisitedBlockSet &VisitedBlocks);
   void findCleanupHandlers(LandingPadActions &Actions, BasicBlock *StartBB,
                            BasicBlock *EndBB);
 
   void processSEHCatchHandler(CatchHandler *Handler, BasicBlock *StartBB);
 
+  bool prepareExplicitEH(Function &F);
+  void numberFunclet(BasicBlock *InitialBB, BasicBlock *FuncletBB);
+
   Triple TheTriple;
 
   // All fields are reset by runOnFunction.
   DominatorTree *DT = nullptr;
   const TargetLibraryInfo *LibInfo = nullptr;
   EHPersonality Personality = EHPersonality::Unknown;
   CatchHandlerMapTy CatchHandlerMap;
   CleanupHandlerMapTy CleanupHandlerMap;
private:
   // outlined but before the outlined code is pruned from the parent function.
   DenseMap<const BasicBlock *, BasicBlock *> LPadTargetBlocks;
 
   // Map from outlined handler to call to parent local address. Only used for
   // 32-bit EH.
   DenseMap<Function *, Value *> HandlerToParentFP;
 
   AllocaInst *SEHExceptionCodeSlot = nullptr;
+
+  std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
+  std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
 };
 
 class WinEHFrameVariableMaterializer : public ValueMaterializer {
 public:
   WinEHFrameVariableMaterializer(Function *OutlinedFn, Value *ParentFP,
                                  FrameVarInfoMap &FrameVarInfo);
   ~WinEHFrameVariableMaterializer() override {}
 

 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
                    false, false)
 
 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
   return new WinEHPrepare(TM);
 }
 
 bool WinEHPrepare::runOnFunction(Function &Fn) {
+  if (!Fn.hasPersonalityFn())
+    return false;
+
   // No need to prepare outlined handlers.
   if (Fn.hasFnAttribute("wineh-parent"))
     return false;
 
+  // Classify the personality to see what kind of preparation we need.
+  Personality = classifyEHPersonality(Fn.getPersonalityFn());
+
+  // Do nothing if this is not an MSVC personality.
+  if (!isMSVCEHPersonality(Personality))
+    return false;
+
   SmallVector<LandingPadInst *, 4> LPads;
   SmallVector<ResumeInst *, 4> Resumes;
+  bool ForExplicitEH = false;
   for (BasicBlock &BB : Fn) {
-    if (auto *LP = BB.getLandingPadInst())
+    if (auto *LP = BB.getLandingPadInst()) {
       LPads.push_back(LP);
+    } else if (BB.getFirstNonPHI()->isEHPad()) {
+      ForExplicitEH = true;
+      break;
+    }
     if (auto *Resume = dyn_cast<ResumeInst>(BB.getTerminator()))
       Resumes.push_back(Resume);
   }
 
+  if (ForExplicitEH)
+    return prepareExplicitEH(Fn);
+
   // No need to prepare functions that lack landing pads.
   if (LPads.empty())
     return false;
 
-  // Classify the personality to see what kind of preparation we need.
-  Personality = classifyEHPersonality(Fn.getPersonalityFn());
-
-  // Do nothing if this is not an MSVC personality.
-  if (!isMSVCEHPersonality(Personality))
-    return false;
-
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   // If there were any landing pads, prepareExceptionHandlers will make changes.
   prepareExceptionHandlers(Fn, LPads);
   return true;
 }
 
void llvm::calculateWinCXXEHStateNumbers(const Function *ParentFn,
   Num.VisitedHandlers.clear();
   Num.calculateStateNumbers(*ParentFn);
   // Pop everything on the handler stack.
   // It may be necessary to call this more than once because a handler can
   // be pushed on the stack as a result of clearing the stack.
   while (!Num.HandlerStack.empty())
     Num.processCallSite(None, ImmutableCallSite());
 }
+
+void WinEHPrepare::numberFunclet(BasicBlock *InitialBB, BasicBlock *FuncletBB) {
+  Instruction *FirstNonPHI = FuncletBB->getFirstNonPHI();
+  bool IsCatch = isa<CatchPadInst>(FirstNonPHI);
+  bool IsCleanup = isa<CleanupPadInst>(FirstNonPHI);
+
+  // Initialize the worklist with the funclet's entry point.
+  std::vector<BasicBlock *> Worklist;
+  Worklist.push_back(InitialBB);
+
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.back();
+    Worklist.pop_back();
+
+    // There can be only one "pad" basic block in the funclet: the initial one.
+    if (BB != FuncletBB && BB->isEHPad())
+      continue;
+
+    // Add 'FuncletBB' as a possible color for 'BB'.
+    if (BlockColors[BB].insert(FuncletBB).second == false) {
+      // Skip basic blocks which we have already visited.
+      continue;
+    }
+
+    FuncletBlocks[FuncletBB].insert(BB);
+
+    Instruction *Terminator = BB->getTerminator();
+    // The catchret's successors cannot be part of the funclet.
+    if (IsCatch && isa<CatchReturnInst>(Terminator))
+      continue;
+    // The cleanupret's successors cannot be part of the funclet.
+    if (IsCleanup && isa<CleanupReturnInst>(Terminator))
+      continue;
+
+    Worklist.insert(Worklist.end(), succ_begin(BB), succ_end(BB));
+  }
+}
+
+bool WinEHPrepare::prepareExplicitEH(Function &F) {
+  LLVMContext &Context = F.getContext();
+  // Remove unreachable blocks.  It is not valuable to assign them a color and
+  // their existence can trick us into thinking values are alive when they are
+  // not.
+  removeUnreachableBlocks(F);
+
+  BasicBlock *EntryBlock = &F.getEntryBlock();
+
+  // Number everything starting from the entry block.
+  numberFunclet(EntryBlock, EntryBlock);
+
+  for (BasicBlock &BB : F) {
+    // Remove single entry PHIs to simplify preparation.
+    if (auto *PN = dyn_cast<PHINode>(BB.begin()))
+      if (PN->getNumIncomingValues() == 1)
+        FoldSingleEntryPHINodes(&BB);
+
+    // EH pad instructions are always the first non-PHI nodes in a block if they
+    // are at all present.
+    Instruction *I = BB.getFirstNonPHI();
+    if (I->isEHPad())
+      numberFunclet(&BB, &BB);
+
+    // It is possible for a normal basic block to only be reachable via an
+    // exceptional basic block.  The successor of a catchret is the only case
+    // where this is possible.
+    if (auto *CRI = dyn_cast<CatchReturnInst>(BB.getTerminator()))
+      numberFunclet(CRI->getSuccessor(), EntryBlock);
+  }
+
+  // Insert cleanuppads before EH blocks with PHI nodes.
+  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
+    BasicBlock *BB = FI++;
+    // Skip any BBs which aren't EH pads.
+    if (!BB->isEHPad())
+      continue;
+    // Skip any cleanuppads, they can hold non-PHI instructions.
+    if (isa<CleanupPadInst>(BB->getFirstNonPHI()))
+      continue;
+    // Skip any EH pads without PHIs, we don't need to worry about demoting into
+    // them.
+    if (!isa<PHINode>(BB->begin()))
+      continue;
+
+    // Create our new cleanuppad BB, terminate it with a cleanupret.
+    auto *NewCleanupBB = BasicBlock::Create(
+        Context, Twine(BB->getName(), ".wineh.phibb"), &F, BB);
+    auto *CPI = CleanupPadInst::Create(Type::getVoidTy(Context), {BB}, "",
+                                       NewCleanupBB);
+    CleanupReturnInst::Create(Context, /*RetVal=*/nullptr, BB, NewCleanupBB);
+
+    // Update the funclet data structures to keep them in the loop.
+    BlockColors[NewCleanupBB].insert(NewCleanupBB);
+    FuncletBlocks[NewCleanupBB].insert(NewCleanupBB);
+
+    // Reparent PHIs from the old EH BB into the cleanuppad.
+    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
+      Instruction *I = BI++;
+      auto *PN = dyn_cast<PHINode>(I);
+      // Stop at the first non-PHI.
+      if (!PN)
+        break;
+      PN->removeFromParent();
+      PN->insertBefore(CPI);
+    }
+
+    // Redirect predecessors from the old EH BB to the cleanuppad.
+    std::set<BasicBlock *> Preds;
+    Preds.insert(pred_begin(BB), pred_end(BB));
+    for (BasicBlock *Pred : Preds) {
+      // Don't redirect the new cleanuppad to itself!
+      if (Pred == NewCleanupBB)
+        continue;
+      TerminatorInst *TI = Pred->getTerminator();
+      for (unsigned TII = 0, TIE = TI->getNumSuccessors(); TII != TIE; ++TII) {
+        BasicBlock *Successor = TI->getSuccessor(TII);
+        if (Successor == BB)
+          TI->setSuccessor(TII, NewCleanupBB);
+      }
+    }
+  }
+
+  // Get rid of polychromatic PHI nodes.
+  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
+    BasicBlock *BB = FI++;
+    std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
+    bool IsEHPad = BB->isEHPad();
+    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
+      Instruction *I = BI++;
+      auto *PN = dyn_cast<PHINode>(I);
+      // Stop at the first non-PHI node.
+      if (!PN)
+        break;
+
+      // EH pads cannot be lowered with PHI nodes prefacing them.
+      if (IsEHPad) {
+        // We should have removed PHIs from all non-cleanuppad blocks.
+        if (!isa<CleanupPadInst>(BB->getFirstNonPHI()))
+          report_fatal_error("Unexpected PHI on EH Pad");
+        DemotePHIToStack(PN);
+        continue;
+      }
+
+      // See if *all* the basic blocks involved in this PHI node are in the
+      // same, lone, color.  If so, demotion is not needed.
+      bool SameColor = ColorsForBB.size() == 1;
+      if (SameColor) {
+        for (unsigned PNI = 0, PNE = PN->getNumIncomingValues(); PNI != PNE;
+             ++PNI) {
+          BasicBlock *IncomingBB = PN->getIncomingBlock(PNI);
+          std::set<BasicBlock *> &ColorsForIncomingBB = BlockColors[IncomingBB];
+          // If the colors differ, bail out early and demote.
+          if (ColorsForIncomingBB != ColorsForBB) {
+            SameColor = false;
+            break;
+          }
+        }
+      }
+
+      if (!SameColor)
+        DemotePHIToStack(PN);
+    }
+  }
+
+  // Turn all inter-funclet uses of a Value into loads and stores.
+  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
+    BasicBlock *BB = FI++;
+    std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
+    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
+      Instruction *I = BI++;
+      // Funclets are permitted to use static allocas.
+      if (auto *AI = dyn_cast<AllocaInst>(I))
+        if (AI->isStaticAlloca())
+          continue;
+
+      // FIXME: Our spill-placement algorithm is incredibly naive.  We should
+      // try to sink+hoist as much as possible to avoid redundant stores and reloads.
+      DenseMap<BasicBlock *, Value *> Loads;
+      AllocaInst *SpillSlot = nullptr;
+      for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+           UI != UE;) {
+        Use &U = *UI++;
+        auto *UsingInst = cast<Instruction>(U.getUser());
+        BasicBlock *UsingBB = UsingInst->getParent();
+
+        // Is the Use inside a block which is colored with a subset of the Def?
+        // If so, we don't need to escape the Def because we will clone
+        // ourselves our own private copy.
+        std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
+        if (std::includes(ColorsForBB.begin(), ColorsForBB.end(),
+                          ColorsForUsingBB.begin(), ColorsForUsingBB.end()))
+          continue;
+
+        // Lazilly create the spill slot.  We spill immediately after the value
+        // in the BasicBlock.
+        // FIXME: This can be improved to spill at the block exit points.
+        if (!SpillSlot)
+          SpillSlot = new AllocaInst(I->getType(), nullptr,
+                                     Twine(I->getName(), ".wineh.spillslot"),
+                                     EntryBlock->begin());
+
+        if (auto *PN = dyn_cast<PHINode>(UsingInst)) {
+          // If this is a PHI node, we can't insert a load of the value before
+          // the use.  Instead insert the load in the predecessor block
+          // corresponding to the incoming value.
+          //
+          // Note that if there are multiple edges from a basic block to this
+          // PHI node that we cannot have multiple loads.  The problem is that
+          // the resulting PHI node will have multiple values (from each load)
+          // coming in from the same block, which is illegal SSA form.
+          // For this reason, we keep track of and reuse loads we insert.
+          BasicBlock *IncomingBlock = PN->getIncomingBlock(U);
+          Value *&V = Loads[IncomingBlock];
+          // Insert the load into the predecessor block
+          if (!V)
+            V = new LoadInst(SpillSlot, Twine(I->getName(), ".wineh.reload"),
+                             /*Volatile=*/false,
+                             IncomingBlock->getTerminator());
+          U.set(V);
+        } else {
+          // Reload right before the old use.
+          // FIXME: This can be improved to reload at a block entry point.
+          Value *V =
+              new LoadInst(SpillSlot, Twine(I->getName(), ".wineh.reload"),
+                           /*Volatile=*/false, UsingInst);
+          U.set(V);
+        }
+      }
+      if (SpillSlot) {
+        // Insert stores of the computed value into the stack slot.
+        // We have to be careful if I is an invoke instruction,
+        // because we can't insert the store AFTER the terminator instruction.
+        BasicBlock::iterator InsertPt;
+        if (!isa<TerminatorInst>(I)) {
+          InsertPt = I;
+          ++InsertPt;
+          // Don't insert before PHI nodes or EH pad instrs.
+          for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
+            ;
+        } else {
+          auto *II = cast<InvokeInst>(I);
+          // We cannot demote invoke instructions to the stack if their normal
+          // edge is critical. Therefore, split the critical edge and create a
+          // basic block into which the store can be inserted.
+          if (!II->getNormalDest()->getSinglePredecessor()) {
+            unsigned SuccNum = GetSuccessorNumber(BB, II->getNormalDest());
+            assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
+            BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
+            assert(NewBlock && "Unable to split critical edge.");
+            // Update the color mapping for the newly split edge.
+            std::set<BasicBlock *> &ColorsForUsingBB =
+                BlockColors[II->getParent()];
+            BlockColors[NewBlock] = ColorsForUsingBB;
+            for (BasicBlock *FuncletPad : ColorsForUsingBB)
+              FuncletBlocks[FuncletPad].insert(NewBlock);
+          }
+          InsertPt = II->getNormalDest()->getFirstInsertionPt();
+        }
+        new StoreInst(I, SpillSlot, InsertPt);
+      }
+    }
+  }
+
+  // We need to clone all blocks which belong to multiple funclets.  Values are
+  // remapped throughout the funclet to propogate both the new instructions
+  // *and* the new basic blocks themselves.
+  for (auto &Funclet : FuncletBlocks) {
+    BasicBlock *FuncletPadBB = Funclet.first;
+    std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
+
+    std::map<BasicBlock *, BasicBlock *> Orig2Clone;
+    ValueToValueMapTy VMap;
+    for (BasicBlock *BB : BlocksInFunclet) {
+      std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
+      // We don't need to do anything if the block is monochromatic.
+      size_t NumColorsForBB = ColorsForBB.size();
+      if (NumColorsForBB == 1)
+        continue;
+
+      assert(!isa<PHINode>(BB->front()) &&
+             "Polychromatic PHI nodes should have been demoted!");
+
+      // Create a new basic block and copy instructions into it!
+      BasicBlock *CBB = CloneBasicBlock(
+          BB, VMap, Twine(".for.", FuncletPadBB->getName()), &F);
+
+      // Add basic block mapping.
+      VMap[BB] = CBB;
+
+      // Record delta operations that we need to perform to our color mappings.
+      Orig2Clone[BB] = CBB;
+    }
+
+    // Update our color mappings to reflect that one block has lost a color and
+    // another has gained a color.
+    for (auto &BBMapping : Orig2Clone) {
+      BasicBlock *OldBlock = BBMapping.first;
+      BasicBlock *NewBlock = BBMapping.second;
+
+      BlocksInFunclet.insert(NewBlock);
+      BlockColors[NewBlock].insert(FuncletPadBB);
+
+      BlocksInFunclet.erase(OldBlock);
+      BlockColors[OldBlock].erase(FuncletPadBB);
+    }
+
+    // Loop over all of the instructions in the function, fixing up operand
+    // references as we go.  This uses VMap to do all the hard work.
+    for (BasicBlock *BB : BlocksInFunclet)
+      // Loop over all instructions, fixing each one as we find it...
+      for (Instruction &I : *BB)
+        RemapInstruction(&I, VMap, RF_IgnoreMissingEntries);
+  }
+
+  // Clean-up some of the mess we made by removing useles PHI nodes, trivial
+  // branches, etc.
+  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
+    BasicBlock *BB = FI++;
+    SimplifyInstructionsInBlock(BB);
+    ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
+    MergeBlockIntoPredecessor(BB);
+  }
+
+  // TODO: Do something about cleanupblocks which branch to implausible
+  // cleanuprets.
+
+  // We might have some unreachable blocks after cleaning up some impossible
+  // control flow.
+  removeUnreachableBlocks(F);
+
+  // Recolor the CFG to verify that all is well.
+  for (BasicBlock &BB : F) {
+    size_t NumColors = BlockColors[&BB].size();
+    assert(NumColors == 1 && "Expected monochromatic BB!");
+    if (NumColors == 0)
+      report_fatal_error("Uncolored BB!");
+    if (NumColors > 1)
+      report_fatal_error("Multicolor BB!");
+    bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
+    assert(!EHPadHasPHI && "EH Pad still has a PHI!");
+    if (EHPadHasPHI)
+      report_fatal_error("EH Pad still has a PHI!");
+  }
+
+  BlockColors.clear();
+  FuncletBlocks.clear();
+  return true;
+}

lib/Transforms/Utils/DemoteRegToStack.cpp

for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
     }
     new StoreInst(P->getIncomingValue(i), Slot,
                   P->getIncomingBlock(i)->getTerminator());
   }
 
   // Insert a load in place of the PHI and replace all uses.
   BasicBlock::iterator InsertPt = P;
 
-  for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt)
+  for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
     /* empty */;   // Don't insert before PHI nodes or landingpad instrs.
 
   Value *V = new LoadInst(Slot, P->getName()+".reload", InsertPt);
   P->replaceAllUsesWith(V);
 
   // Delete PHI.
   P->eraseFromParent();
   return Slot;
 }