[WinEH] Add a funclet layout pass

[majnemer]

Summary

Windows EH funclets need to be contiguous. The FuncletLayout pass will
ensure that the funclets are together and begin with a funclet entry MBB.

[rnk]

lgtm

lib/CodeGen/FuncletLayout.cpp

69

You can do:

if (!F.getMMI().hasEHFunclets())
  return false;

72

MBB.isEHFuncletEntry()

76

Now you can assert !empty

test/CodeGen/X86/funclet-layout.ll

31

s/is contains/contains/

32

Maybe throw in

CHECK-LABEL: _f:

34

CHECK: retl

35

ditto

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
 
   /// OptimizePHIs - This pass optimizes machine instruction PHIs
   /// to take advantage of opportunities created during DAG legalization.
   extern char &OptimizePHIsID;
 
   /// StackSlotColoring - This pass performs stack slot coloring.
   extern char &StackSlotColoringID;
 
+  /// \brief This pass lays out funclets contiguously.
+  extern char &FuncletLayoutID;
+
   /// createStackProtectorPass - This pass adds stack protectors to functions.
   ///
   FunctionPass *createStackProtectorPass(const TargetMachine *TM);
 
   /// createMachineVerifierPass - This pass verifies cenerated machine code
   /// instructions for correctness.
   ///
   FunctionPass *createMachineVerifierPass(const std::string& Banner);

include/llvm/InitializePasses.h

 void initializeWinEHPreparePass(PassRegistry&);
 void initializePlaceBackedgeSafepointsImplPass(PassRegistry&);
 void initializePlaceSafepointsPass(PassRegistry&);
 void initializeDwarfEHPreparePass(PassRegistry&);
 void initializeFloat2IntPass(PassRegistry&);
 void initializeLoopDistributePass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeDemandedBitsPass(PassRegistry&);
+void initializeFuncletLayoutPass(PassRegistry &);
 }
 
 #endif

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   DwarfEHPrepare.cpp
   EarlyIfConversion.cpp
   EdgeBundles.cpp
   ErlangGC.cpp
   ExecutionDepsFix.cpp
   ExpandISelPseudos.cpp
   ExpandPostRAPseudos.cpp
   FaultMaps.cpp
+  FuncletLayout.cpp
   GCMetadata.cpp
   GCMetadataPrinter.cpp
   GCRootLowering.cpp
   GCStrategy.cpp
   GlobalMerge.cpp
   IfConversion.cpp
   ImplicitNullChecks.cpp
   InlineSpiller.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeBranchFolderPassPass(Registry);
   initializeCodeGenPreparePass(Registry);
   initializeDeadMachineInstructionElimPass(Registry);
   initializeDwarfEHPreparePass(Registry);
   initializeEarlyIfConverterPass(Registry);
   initializeExpandISelPseudosPass(Registry);
   initializeExpandPostRAPass(Registry);
   initializeFinalizeMachineBundlesPass(Registry);
+  initializeFuncletLayoutPass(Registry);
   initializeGCMachineCodeAnalysisPass(Registry);
   initializeGCModuleInfoPass(Registry);
   initializeIfConverterPass(Registry);
   initializeLiveDebugVariablesPass(Registry);
   initializeLiveIntervalsPass(Registry);
   initializeLiveStacksPass(Registry);
   initializeLiveVariablesPass(Registry);
   initializeLocalStackSlotPassPass(Registry);

lib/CodeGen/FuncletLayout.cpp

+//===-- FuncletLayout.cpp - Contiguously lay out funclets -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements basic block placement transformations which result in
+// funclets being contiguous.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "funclet-layout"
+
+namespace {
+class FuncletLayout : public MachineFunctionPass {
+public:
+  static char ID; // Pass identification, replacement for typeid
+  FuncletLayout() : MachineFunctionPass(ID) {
+    initializeFuncletLayoutPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnMachineFunction(MachineFunction &F) override;
+};
+}
+
+static void
+collectFuncletMembers(MapVector<MachineBasicBlock *, int> &FuncletMembership,
+                      int Funclet, MachineBasicBlock *MBB) {
+  // Don't revisit blocks.
+  if (FuncletMembership.count(MBB) > 0)
+    return;
+
+  // Add this MBB to our funclet.
+  FuncletMembership[MBB] = Funclet;
+
+  bool IsReturn = false;
+  int NumTerminators = 0;
+  for (MachineInstr &MI : MBB->terminators()) {
+    IsReturn |= MI.isReturn();
+    ++NumTerminators;
+  }
+  assert((!IsReturn || NumTerminators == 1) &&
+         "Expected only one terminator when a return is present!");
+
+  // Returns are boundaries where funclet transfer can occur, don't follow
+  // successors.
+  if (IsReturn)
+    return;
+
+  for (MachineBasicBlock *SMBB : MBB->successors())
+    if (!SMBB->isEHPad())
+      collectFuncletMembers(FuncletMembership, Funclet, SMBB);
+}
+
+char FuncletLayout::ID = 0;
+char &llvm::FuncletLayoutID = FuncletLayout::ID;
+INITIALIZE_PASS(FuncletLayout, "funclet-layout",
+                "Contiguously Lay Out Funclets", false, false)
+
+bool FuncletLayout::runOnMachineFunction(MachineFunction &F) {
+  SmallVector<MachineBasicBlock *, 16> FuncletBlocks;
+  for (MachineBasicBlock &MBB : F)
+    if (MBB.isEHPad())
+      FuncletBlocks.push_back(&MBB);
+
+  // We don't have anything to do if there aren't any EH pads.
+  if (FuncletBlocks.empty())
+    return false;
+
+  MapVector<MachineBasicBlock *, int> FuncletMembership;
+  for (MachineBasicBlock *MBB : FuncletBlocks)
+    collectFuncletMembers(FuncletMembership, MBB->getNumber(), MBB);
+
+  for (std::pair<llvm::MachineBasicBlock *, int> &FuncletMember :
+       FuncletMembership) {
+    // Move this block to the end of the function.
+    MachineBasicBlock *MBB = FuncletMember.first;
+    MBB->moveAfter(--F.end());
+  }
+
+  return true;
+}

lib/CodeGen/Passes.cpp

void TargetPassConfig::addMachinePasses() {
   }
 
   // Basic block placement.
   if (getOptLevel() != CodeGenOpt::None)
     addBlockPlacement();
 
   addPreEmitPass();
 
+  addPass(&FuncletLayoutID, false);
+
   addPass(&StackMapLivenessID, false);
 
   AddingMachinePasses = false;
 }
 
 /// Add passes that optimize machine instructions in SSA form.
 void TargetPassConfig::addMachineSSAOptimization() {
   // Pre-ra tail duplication.

test/CodeGen/X86/funclet-layout.ll

+; RUN: llc -mtriple=x86_64-windows-msvc < %s | FileCheck %s
+
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+define void @f(i1 %B) personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @g()
+          to label %unreachable unwind label %catch.dispatch
+
+catch.dispatch:
+  %cp = catchpad [i8* null, i32 64, i8* null]
+          to label %catch unwind label %catchendblock
+
+catch:
+  br i1 %B, label %catchret, label %catch
+
+catchret:
+  catchret %cp to label %try.cont
+
+try.cont:
+  ret void
+
+catchendblock:
+  catchendpad unwind to caller
+
+unreachable:
+  unreachable
+}
+
+; The entry funclet is contains %entry and %try.cont
+; CHECK: # %entry
+; CHECK: # %try.cont
+
+; The catch funclet is contains %catch and %catchret
+; CHECK: # %catch
+; CHECK: # %catchret
+
+declare void @g()
+
+declare i32 @__CxxFrameHandler3(...)