[CGP] Hoist allocas used in catchpad instructions, if they are not in the entry block.

[clin1]

Summary

The Windows x86 EH implementation does not support dynamic stack allocation.

[clin1]

This is a possible solution for:
https://github.com/llvm/llvm-project/issues/60914

[efriedma]

Hoisting like this is completely unsafe; dynamic allocation is dynamic for a reason (because the allocation is variable size, or happens in a loop).

How do you end up with IR that looks like "@hoist"? clang shouldn't generate IR like that.

[LuoYuanke]

In D145275#4168604, @efriedma wrote:

Hoisting like this is completely unsafe; dynamic allocation is dynamic for a reason (because the allocation is variable size, or happens in a loop).

How do you end up with IR that looks like "@hoist"? clang shouldn't generate IR like that.

Can we ingore dynamic alloca like https://reviews.llvm.org/D145286?

[efriedma]

How do you end up with IR that looks like "@hoist"? clang shouldn't generate IR like that.

[clin1]

You're right, this IR won't come out of clang --- it's an artifact of a function shrinkwrapping project that someone was working on. The IR seems generically "legal" but was causing a crash later in codegen. The patch avoids the crash.
I just realized that this patch won't address the github issue linked above (60914) because it only hoists catchpad operands. Maybe a more generic solution in WinEH codegen is needed.

[efriedma]

In D145275#4168967, @clin1 wrote:

You're right, this IR won't come out of clang --- it's an artifact of a function shrinkwrapping project that someone was working on. The IR seems generically "legal" but was causing a crash later in codegen. The patch avoids the crash.

If the EH encoding requires that the catchpad point specifically at a static alloca, we should just consider that an invariant, and print a fatal error. I'm not completely sure it's an invariant, since I haven't looked at this part of Windows EH in a while, but that's the impression I get looking at D145286. Ideally the verifier should enforce it, but I'm not sure what the complete rules look like.

(I wouldn't recommend implementing shrink-wrapping by moving around allocas; you probably want something more along the lines of lifetime intrinsics. Maybe consider posting your design on Discourse for feedback.)

I just realized that this patch won't address the github issue linked above (60914) because it only hoists catchpad operands. Maybe a more generic solution in WinEH codegen is needed.

There's clearly a backend bug if dynamic allocation anywhere in the function breaks exception handling. MSVC manages to encode this somehow. (Maybe something related to the frame pointer.)

[clin1]

Thanks for your comments --- I will close this review, and see if a solution can be made on the codegen side.

llvm/lib/CodeGen/CodeGenPrepare.cpp

private:
   DominatorTree &getDT(Function &F) {
     if (!DT)
       DT = std::make_unique<DominatorTree>(F);
     return *DT;
   }
 
   void removeAllAssertingVHReferences(Value *V);
   bool eliminateAssumptions(Function &F);
+  bool hoistCatchPadAlloca(Function &F);
   bool eliminateFallThrough(Function &F);
   bool eliminateMostlyEmptyBlocks(Function &F);
   BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB);
   bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
   void eliminateMostlyEmptyBlock(BasicBlock *BB);
   bool isMergingEmptyBlockProfitable(BasicBlock *BB, BasicBlock *DestBB,
                                      bool isPreheader);
   bool makeBitReverse(Instruction &I);
while (BB != nullptr) {
       BB = Next;
     }
   }
 
   // Get rid of @llvm.assume builtins before attempting to eliminate empty
   // blocks, since there might be blocks that only contain @llvm.assume calls
   // (plus arguments that we can get rid of).
   EverMadeChange |= eliminateAssumptions(F);
-
+  // The frame allocator requires catchpad args to be allocated in the entry
+  // block.
+  EverMadeChange |= hoistCatchPadAlloca(F);
   // Eliminate blocks that contain only PHI nodes and an
   // unconditional branch.
   EverMadeChange |= eliminateMostlyEmptyBlocks(F);
 
   ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
   if (!DisableBranchOpts)
     EverMadeChange |= splitBranchCondition(F, ModifiedDT);
 

 #ifndef NDEBUG
   if (VerifyBFIUpdates)
     verifyBFIUpdates(F);
 #endif
 
   return EverMadeChange;
 }
 
+// If a catchpad has a local allocated arg which is not allocated in the
+// entry block, hoist it to the entry block.
+bool CodeGenPrepare::hoistCatchPadAlloca(Function &F) {
+  if (!F.hasPersonalityFn())
+    return false;
+  bool MadeChange = false;
+  auto *EntryBlock = &(F.getEntryBlock());
+  for (BasicBlock &BB : F) {
+    CurInstIterator = BB.begin();
+    while (CurInstIterator != BB.end()) {
+      Instruction *I = &*(CurInstIterator++);
+      if (auto *CatchPad = dyn_cast<CatchPadInst>(I)) {
+        for (auto &Arg : CatchPad->arg_operands()) {
+          if (auto *AI = dyn_cast<AllocaInst>(&Arg)) {
+            if (AI->getParent() != EntryBlock) {
+              AI->removeFromParent();
+              AI->insertBefore(&*(EntryBlock->getFirstInsertionPt()));
+              MadeChange = true;
+            }
+          }
+        }
+      }
+    }
+  }
+  return MadeChange;
+}
+
 bool CodeGenPrepare::eliminateAssumptions(Function &F) {
   bool MadeChange = false;
   for (BasicBlock &BB : F) {
     CurInstIterator = BB.begin();
     while (CurInstIterator != BB.end()) {
       Instruction *I = &*(CurInstIterator++);
       if (auto *Assume = dyn_cast<AssumeInst>(I)) {
         MadeChange = true;

llvm/test/Transforms/CodeGenPrepare/catchpad-dynamic-alloca.ll

+; RUN: opt --codegenprepare -S %s | FileCheck %s
+
+target datalayout = "e-m:w-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc19.28.29334"
+
+%struct.widget = type { ptr, ptr, [8 x i8] }
+
+@global = external global %struct.widget
+
+; CHECK-LABEL: hoist
+; CHECK-NEXT: bb
+; CHECK-NEXT: %tmp = alloca i32
+; CHECK-NEXT: br i1{{.*}}%bb1
+define dso_local void @hoist() local_unnamed_addr #0 personality ptr @__CxxFrameHandler3 {
+bb:
+  br i1 poison, label %bb1, label %bb7
+
+bb1:                                              ; preds = %bb
+  %tmp = alloca i32, align 4
+  invoke void @snork()
+          to label %bb6 unwind label %bb2
+
+bb2:                                              ; preds = %bb1
+  %tmp3 = catchswitch within none [label %bb4] unwind label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = catchpad within %tmp3 [ptr @global, i32 0, ptr %tmp]
+  unreachable
+
+bb6:                                              ; preds = %bb1
+  unreachable
+
+bb7:                                              ; preds = %bb
+  ret void
+
+bb8:                                              ; preds = %bb2
+  %tmp9 = cleanuppad within none []
+  unreachable
+}
+
+; tmp2/tmp are in entry block, should not be moved.
+; check that ordering is not changed.
+
+; CHECK-LABEL: nohoist
+; CHECK: bb:
+; CHECK-NEXT: %tmp2 = alloca i32
+; CHECK-NEXT: %tmp = alloca i32
+define dso_local void @nohoist() local_unnamed_addr #0 personality ptr @__CxxFrameHandler3 {
+bb:
+  %tmp2 = alloca i32
+  %tmp = alloca i32, align 4
+  br i1 poison, label %bb1, label %bb7
+
+bb1:                                              ; preds = %bb
+  invoke void @snork()
+          to label %bb6 unwind label %bb2
+
+bb2:                                              ; preds = %bb1
+  %tmp3 = catchswitch within none [label %bb4] unwind label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = catchpad within %tmp3 [ptr @global, i32 0, ptr %tmp]
+  unreachable
+
+bb6:                                              ; preds = %bb1
+  unreachable
+
+bb7:                                              ; preds = %bb
+  ret void
+
+bb8:                                              ; preds = %bb2
+  %tmp9 = cleanuppad within none []
+  unreachable
+}
+
+
+; Function Attrs: nofree
+declare dso_local i32 @__CxxFrameHandler3(...) #0
+
+declare dso_local void @snork() local_unnamed_addr #0
+
+attributes #0 = { nofree }
+