[Verifier][WinEH] Check funclet tokens on intrinsic calls that may lower to function calls

[sgraenitz]

Summary

WinEHPrepare requires funclet operand bundles ("tokens") on function calls from EH funclets to prevent them from getting removed as "implausible" calls. This includes calls to intrinsic functions that lower to function calls in the course of IR transformations (e.g. ObjC ARC runtime calls).

We can not detect such cases in WinEHPrepare itself, because at this point they mixed up with valid implausible calls. These must be removed to guarantee that the EH backend can assign unique colors and EH state numbers to all blocks.

This patch allows the IR Verifier to detect missing and dangling funclet tokens. Non-conforming IR becomes illegal and miscompilations are detected early. In order to find funclet pad instructions for funclets that extend over multiple blocks, we have to calculate EH funclet colors. As coloring can be expensive, it runs on-demand and results are cached per function.

[sgraenitz]

llvm/test/Transforms/ObjCARC/invoke-2.ll

42

The verifier already caught this, which I assume is a bug that sat here unnoticed for years -- catchpad without catchret?

[rnk]

llvm/lib/IR/Verifier.cpp

4909

This property should be validated for invokes, calls, and callbr, right?

5757

I think these comments should discuss the purpose of this verification. Maybe we can say:

// Verify that each function call belongs to exactly one funclet (or the main function),
// and that there aren't any unmediated control transfers between funclets.

llvm/test/Transforms/ObjCARC/invoke-2.ll

42

Looks like a bug to me

[sgraenitz]

Update comment

llvm/lib/IR/Verifier.cpp

4909

If I understand correctly, we can guarantee that for IR right after codegen, but not in between transformations -- because transformations must be allowed to introduce implausible calls? If we could guarantee it for calls across all transformations, then WinEHPrepare::removeImplausibleInstructions() doesn't seem to be necessary.

5757

belongs to exactly one funclet (or the main function)

As mentioned in D137944, I am not sure we can guarantee that when running the verifier in between transformations

[sgraenitz]

Is there any more feedback on this extension of the verifier?

[sgraenitz]

Ping

[sgraenitz]

This review belongs to a series of patches. I am planning to land it towards the end of next week, so that it's ready for the next release branching in February. If you have any more remarks, please let me know soon.

[efriedma]

Would it make sense to check calls to non-intrinsic functions here? I don't see any meaningful distinction between an intrinsic that will be lowered to a non-intrinsic call, vs. an actual call.

Would it make sense to allow dangling funclet tokens in unreachable code? In particular, I'm concerned about cases where a bit of code is logically inside a funclet, but control flow simplification cuts it off from the funclet entry. (WinEHPrepare will throw away unreachable code anyway, so it shouldn't care.)

[sgraenitz]

Thanks for your feedback @efriedma

In D138123#4067201, @efriedma wrote:

Would it make sense to check calls to non-intrinsic functions here? I don't see any meaningful distinction between an intrinsic that will be lowered to a non-intrinsic call, vs. an actual call.

Front-ends that target WinEH are responsible for setting up funclet tokens for function calls. In Clang this happens in generic code paths and it works reliably. While we could check it here for all cases, it doesn't seem necessary and it would add overhead. The compromise to check funclet tokens for certain intrinsic calls arised from the fact that middle-end passes can add/replace intrinsics and sometimes miss to set up funclet tokens. One current example is here: https://reviews.llvm.org/D137944#C3801853OL1776

It would be handy to catch these cases early in the verifier. Reid explained some more background here: https://reviews.llvm.org/D134866#3824796

Would it make sense to allow dangling funclet tokens in unreachable code? In particular, I'm concerned about cases where a bit of code is logically inside a funclet, but control flow simplification cuts it off from the funclet entry. (WinEHPrepare will throw away unreachable code anyway, so it shouldn't care.)

Good point. I am not an expert for details in simplifycfg. If it produces such cases legally and doesn't clean them up (and instead rely on WinEHPrepare), that's odd but it needs to be considered. Dangling tokens were the symptom I observed in https://reviews.llvm.org/D134866 (which turned out to be a front-end codegen issue) and catching them here would be great, but they used to be less frequent than missing token cases and I guess we could live without them for now.

[efriedma]

In D138123#4072713, @sgraenitz wrote:

Thanks for your feedback @efriedma

In D138123#4067201, @efriedma wrote:

Would it make sense to check calls to non-intrinsic functions here? I don't see any meaningful distinction between an intrinsic that will be lowered to a non-intrinsic call, vs. an actual call.

Front-ends that target WinEH are responsible for setting up funclet tokens for function calls. In Clang this happens in generic code paths and it works reliably. While we could check it here for all cases, it doesn't seem necessary and it would add overhead. The compromise to check funclet tokens for certain intrinsic calls arised from the fact that middle-end passes can add/replace intrinsics and sometimes miss to set up funclet tokens. One current example is here: https://reviews.llvm.org/D137944#C3801853OL1776

It would be handy to catch these cases early in the verifier. Reid explained some more background here: https://reviews.llvm.org/D134866#3824796

Okay

Would it make sense to allow dangling funclet tokens in unreachable code? In particular, I'm concerned about cases where a bit of code is logically inside a funclet, but control flow simplification cuts it off from the funclet entry. (WinEHPrepare will throw away unreachable code anyway, so it shouldn't care.)

Good point. I am not an expert for details in simplifycfg. If it produces such cases legally and doesn't clean them up (and instead rely on WinEHPrepare), that's odd but it needs to be considered. Dangling tokens were the symptom I observed in https://reviews.llvm.org/D134866 (which turned out to be a front-end codegen issue) and catching them here would be great, but they used to be less frequent than missing token cases and I guess we could live without them for now.

I'm concerned specifically about cases where a block is unreachable in the sense of isReachableFromEntry. I'm not concerned about SimplifyCFG itself (that cleans up dead blocks); more concerned about, for example, clang omitting some control flow due to an if (0), but we emit the body of the if because it contains a label.

[sgraenitz]

Rebase and drop check for dangling funclet tokens

[sgraenitz]

Thanks for your quick reply!

more concerned about, for example, clang omitting some control flow due to an if (0), but we emit the body of the if because it contains a label

I didn't manage to reproduce this quickly. If you have more specific ideas for a reproducer, please let me know. Maybe next time I work on this, I can investigate in more detail!

In the meantime I dropped the dangling funclet checks and rebased to TOT. Dou think we can give this a try?

[efriedma]

LGTM

I didn't manage to reproduce this quickly. If you have more specific ideas for a reproducer, please let me know.

Something like the following:

void g1(), g2();
void f() {
  try {
    g();
  } catch (...) {
    return;
    Z: g(); goto Z;
  }
}

[sgraenitz]

Thanks! Unfortunately the release branched earlier this year so this didn't make it into 16.x

llvm/lib/IR/Verifier.cpp

 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/EHPersonalities.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   /// Stores the count of how many objects were passed to llvm.localescape for a
   /// given function and the largest index passed to llvm.localrecover.
   DenseMap<Function *, std::pair<unsigned, unsigned>> FrameEscapeInfo;
 
   // Maps catchswitches and cleanuppads that unwind to siblings to the
   // terminators that indicate the unwind, used to detect cycles therein.
   MapVector<Instruction *, Instruction *> SiblingFuncletInfo;
 
+  /// Cache which blocks are in which funclet, if an EH funclet personality is
+  /// in use. Otherwise empty.
+  DenseMap<BasicBlock *, ColorVector> BlockEHFuncletColors;
+
   /// Cache of constants visited in search of ConstantExprs.
   SmallPtrSet<const Constant *, 32> ConstantExprVisited;
 
   /// Cache of declarations of the llvm.experimental.deoptimize.<ty> intrinsic.
   SmallVector<const Function *, 4> DeoptimizeDeclarations;
 
   /// Cache of attribute lists verified.
   SmallPtrSet<const void *, 32> AttributeListsVisited;
void Verifier::visitFunction(const Function &F) {
   if (F.hasPersonalityFn()) {
     auto *Per = dyn_cast<Function>(F.getPersonalityFn()->stripPointerCasts());
     if (Per)
       Check(Per->getParent() == F.getParent(),
             "Referencing personality function in another module!", &F,
             F.getParent(), Per, Per->getParent());
   }
 
+  // EH funclet coloring can be expensive, recompute on-demand
+  BlockEHFuncletColors.clear();
+
   if (F.isMaterializable()) {
     // Function has a body somewhere we can't see.
     Check(MDs.empty(), "unmaterialized function cannot have metadata", &F,
           MDs.empty() ? nullptr : MDs.front().second);
   } else if (F.isDeclaration()) {
     for (const auto &I : MDs) {
       // This is used for call site debug information.
       CheckDI(I.first != LLVMContext::MD_dbg ||
auto AllowLocs =
             : AreDebugLocsAllowed::No;
     visitMDNode(*Attachment.second, AllowLocs);
   }
 
   InstsInThisBlock.insert(&I);
 }
 
 /// Allow intrinsics to be verified in different ways.
 void Verifier::visitIntrinsicCall(Intrinsic::ID ID, CallBase &Call) {
   Function *IF = Call.getCalledFunction();
   Check(IF->isDeclaration(), "Intrinsic functions should never be defined!",
         IF);
 
   // Verify that the intrinsic prototype lines up with what the .td files
   // describe.
   FunctionType *IFTy = IF->getFunctionType();
   bool IsVarArg = IFTy->isVarArg();
#include "llvm/IR/ConstrainedOps.def"
   case Intrinsic::arm_strex: {
     Type *ElemTy = Call.getAttributes().getParamElementType(1);
     Check(ElemTy,
           "Intrinsic requires elementtype attribute on second argument.",
           &Call);
     break;
   }
   };
+
+  // Verify funclet operand bundles for WinEH-like personalities
+  if (IntrinsicInst::mayLowerToFunctionCall(ID)) {
+    Function *F = Call.getParent()->getParent();
+    if (F->hasPersonalityFn() &&
+        isScopedEHPersonality(classifyEHPersonality(F->getPersonalityFn()))) {
+      // Run EH funclet coloring on-demand and cache results for other intrinsic
+      // calls in this function
+      if (BlockEHFuncletColors.empty())
+        BlockEHFuncletColors = colorEHFunclets(*F);
+
+      // Check for catch-/cleanup-pad in first funclet block
+      bool InEHFunclet = false;
+      BasicBlock *CallBB = Call.getParent();
+      const ColorVector &CV = BlockEHFuncletColors.find(CallBB)->second;
+      assert(CV.size() > 0 && "Uncolored block");
+      for (BasicBlock *ColorFirstBB : CV)
+        if (dyn_cast_or_null<FuncletPadInst>(ColorFirstBB->getFirstNonPHI()))
+          InEHFunclet = true;
+
+      // Check for funclet operand bundle
+      bool HasToken = false;
+      for (unsigned I = 0, E = Call.getNumOperandBundles(); I != E; ++I)
+        if (Call.getOperandBundleAt(I).getTagID() == LLVMContext::OB_funclet)
+          HasToken = true;
+
+      // These cases can cause silent code truncations in WinEHPrepare
+      if (InEHFunclet) {
+        Check(HasToken, "Missing funclet token on intrinsic call", &Call);
+      } else {
+        Check(!HasToken, "Dangling funclet token on intrinsic call", &Call);
+      }
+    }
+  }
 }
 
 /// Carefully grab the subprogram from a local scope.
 ///
 /// This carefully grabs the subprogram from a local scope, avoiding the
 /// built-in assertions that would typically fire.
 static DISubprogram *getSubprogram(Metadata *LocalScope) {
   if (!LocalScope)

llvm/test/Transforms/ObjCARC/invoke-2.ll

 eh.cont:                                          ; preds = %invoke.cont, %catch
   tail call void @llvm.objc.release(i8* %0) #0, !clang.imprecise_release !0
   ret void
 
 catch:                                            ; preds = %catch.dispatch
   %4 = catchpad within %2 [i8* null, i32 0, i8* null]
   %exn.adjusted = tail call i8* @llvm.objc.begin_catch(i8* undef)
   tail call void @llvm.objc.end_catch(), !clang.arc.no_objc_arc_exceptions !0
-  br label %eh.cont
+  catchret from %4 to label %eh.cont
 }
 
 ; CHECK-LABEL: @f
 
 ; CHECK-NOT: tail call i8* @llvm.objc.retain(i8* %i)
 ; CHECK: load i8*, i8** @llvm.objc.SELECTOR_REFERENCES_, align 8
 
 ; CHECK: eh.cont:
 ; CHECK-NOT: call void @llvm.objc.release(i8*
 ; CHECK: ret void
 
 attributes #0 = { nounwind }
 
 !0 = !{}
 

llvm/test/Verifier/operand-bundles-wineh.ll

+; RUN: not opt -verify < %s 2>&1 | FileCheck %s
+
+define void @report_missing() personality ptr @__CxxFrameHandler3 {
+entry:
+  invoke void @may_throw() to label %eh.cont unwind label %catch.dispatch
+
+catch.dispatch:
+  %0 = catchswitch within none [label %catch] unwind to caller
+
+catch:
+  %1 = catchpad within %0 [ptr null, i32 0, ptr null]
+  br label %catch.cont
+
+catch.cont:
+; CHECK: Missing funclet token on intrinsic call
+  %2 = call ptr @llvm.objc.retain(ptr null)
+  catchret from %1 to label %eh.cont
+
+eh.cont:
+  ret void
+}
+
+define void @report_dangling() personality ptr @__CxxFrameHandler3 {
+entry:
+  invoke void @may_throw() to label %eh.cont unwind label %catch.dispatch
+
+catch.dispatch:
+  %0 = catchswitch within none [label %catch] unwind to caller
+
+catch:
+  %1 = catchpad within %0 [ptr null, i32 0, ptr null]
+  call void @do_something()
+  catchret from %1 to label %catchret.dest
+
+catchret.dest:
+; CHECK: Dangling funclet token on intrinsic call
+  %2 = call ptr @llvm.objc.retain(ptr null) [ "funclet"(token %1) ]
+  br label %eh.cont
+
+eh.cont:
+  ret void
+}
+
+declare void @may_throw()
+declare void @do_something()
+declare i32 @__CxxFrameHandler3(...)
+
+declare ptr @llvm.objc.retain(ptr) #0
+
+attributes #0 = { nounwind }