Fix WinEHPrepare bug with multiple catch handlers

[andrew.w.kaylor]

Summary

This fixes the bug with multiple catch handlers at the same level. The test case looks like this:

void f() {
  try {
    may_throw();
  }
  catch (int) {
  }
  catch (float) {
  }
}

With this IR:

; Function Attrs: uwtable
define void @"\01?f@@YAXXZ"() #0 {
entry:
  %exn.slot = alloca i8*
  %ehselector.slot = alloca i32
  %0 = alloca float, align 4
  %1 = alloca i32, align 4
  invoke void @"\01?may_throw@@YAXXZ"()
          to label %invoke.cont unwind label %lpad

invoke.cont:                                      ; preds = %entry
  br label %try.cont

lpad:                                             ; preds = %entry
  %2 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
          catch %eh.HandlerMapEntry* @llvm.eh.handlermapentry.H
          catch %eh.HandlerMapEntry* @llvm.eh.handlermapentry.M
  %3 = extractvalue { i8*, i32 } %2, 0
  store i8* %3, i8** %exn.slot
  %4 = extractvalue { i8*, i32 } %2, 1
  store i32 %4, i32* %ehselector.slot
  br label %catch.dispatch

catch.dispatch:                                   ; preds = %lpad
  %sel = load i32, i32* %ehselector.slot
  %5 = call i32 @llvm.eh.typeid.for(i8* bitcast (%eh.HandlerMapEntry* @llvm.eh.handlermapentry.H to i8*)) #3
  %matches = icmp eq i32 %sel, %5
  br i1 %matches, label %catch2, label %catch.fallthrough

catch2:                                           ; preds = %catch.dispatch
  %exn3 = load i8*, i8** %exn.slot
  %6 = bitcast i32* %1 to i8*
  call void @llvm.eh.begincatch(i8* %exn3, i8* %6) #3
  call void @llvm.eh.endcatch() #3
  br label %try.cont

try.cont:                                         ; preds = %catch2, %catch, %invoke.cont
  ret void

catch.fallthrough:                                ; preds = %catch.dispatch
  %7 = call i32 @llvm.eh.typeid.for(i8* bitcast (%eh.HandlerMapEntry* @llvm.eh.handlermapentry.M to i8*)) #3
  %matches1 = icmp eq i32 %sel, %7
  br i1 %matches1, label %catch, label %eh.resume

catch:                                            ; preds = %catch.fallthrough
  %exn = load i8*, i8** %exn.slot
  %8 = bitcast float* %0 to i8*
  call void @llvm.eh.begincatch(i8* %exn, i8* %8) #3
  call void @llvm.eh.endcatch() #3
  br label %try.cont

eh.resume:                                        ; preds = %catch.fallthrough
  %exn4 = load i8*, i8** %exn.slot
  %sel5 = load i32, i32* %ehselector.slot
  %lpad.val = insertvalue { i8*, i32 } undef, i8* %exn4, 0
  %lpad.val6 = insertvalue { i8*, i32 } %lpad.val, i32 %sel5, 1
  resume { i8*, i32 } %lpad.val6
}

It's a small fix, but I thought it was worth pausing to talk about because the code involved seems potentially brittle.

The problem in this case was that the landing pad selector value was being loaded in one catch dispatch block but being referenced in two blocks. Neither the landing pad block mapping code nor the catch handling code were expecting this. For this case it was fairly simple to extend the code to recognize what was happening, but it raises a concern in my mind that the selector value, which we must be able to recognize for this pass to work properly, can be shuffled around through any manner of transformation. I can't see why it would be manipulated, beyond the basic optimizations to avoid storing and reloading it, but it can happen.

Do you think this needs to be more robust?

[rnk]

Test case?

I was on vacation Thurs/Fri, so I'm a little slow today.

[andrew.w.kaylor]

I've got mixed feelings about test cases for the kind of bugs that are showing up at this stage of the implementation. I tested this with the case shown in the comments, but I'm not sure we want to clutter the test suite with a large variety of trivial cases. I think that it would be better to have a more robust suite of tests later that would include things like this. That said, I'm willing to add the trivial test cases if the consensus is that we should do it that way..

[andrew.w.kaylor]

Adding a fix for an unrelated problem where an llvm.eh.endcatch call is not immediately followed by an unconditional branch instruction:

define void @f() {
entry:
  invoke void @f() to label %try.cont unwind label %lpad

lpad:                                             ; preds = %entry
  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*)
          catch i8* null
  %1 = extractvalue { i8*, i32 } %0, 0
  tail call void @llvm.eh.begincatch(i8* %1, i8* null) #0
  tail call void @llvm.eh.endcatch() #0
  ret void

try.cont:                                         ; preds = %entry
  ret void
}

I considered splitting the block in the mapLandingPadBlocks code, but that involved extra searching for the endcatch calls, while this code already has the needed location.

[rnk]

I understand why we need to split the block after llvm.eh.endcatch, but I don't really see why we should be treating icmps specially. Maybe we should pre-populate the value map with all dominating EH value stores instead? I'm looking at the broken test case and looking at how to fix it.

Feel free to commit the basic block splitting separately.

[rnk]

I agree we shouldn't clutter the test suite with too many trivial cases, but I think a single try with multiple catches is an interesting basic case that we should handle.

[andrew.w.kaylor]

That's pretty much why I put this up for review. I'm not entirely happy with this solution to the original problem (referencing a loaded EH selector value in a block whose cloning director didn't see it being loaded). The problem arises from the decision not to start cloning at the original landing pad block. The mapLandingPadUsers code tries to handle this sort of thing by looking at all the places where the original values are stored, but if there's an efficient way to find all of the places where it is loaded again, I'm not aware of it.

The way that the cloning works, the first time we're forced to deal with the unrecognized %sel value would be in the materializeValueFor() method and by then it's too late (unless we shared the mapped landing pad values with the materializer and that seems very ugly).

Of course, if we want to be entirely bullet-proof the problem is even worse. You can imagine all sorts of ways that a selector value could be manipulated such that the handler cloning code isn't even looking at a load of the original stored value. In practice, the only things that I would ever expect to happen to the selector value are (1) extract from the aggregate, (2) insert into another aggregate value, (3) stored to a memory location, (4) loaded from a memory location, (5) compared with a result of llvm.eh.typeid.for(). I'm just not sure it's reasonable to impose this as a limitation.

[rnk]

Here's an idea. What if before outlining, we run mem2reg (see llvm::PromoteMemToReg) on all EH value objects? This should greatly simplify the existing preparation code, because we won't need to track stores of selectors and EH pointers anymore. Even at -O0, these allocas are not visible to the user, so removing them is useful. If the frontend produces IR that fails to promote, I think it's totally reasonable for WinEHPrepare to assert.

[andrew.w.kaylor]

That sounds pretty reasonable. I'll give it a try and add test cases.

[andrew.w.kaylor]

Added code to promote extracted landing pad values to registers.
Removed code which was made obsolete by the above change.
Added a test case.

[andrew.w.kaylor]

lib/CodeGen/WinEHPrepare.cpp

1532

Again, ignore this.

1537

Oops. This shouldn't be here. I forgot to delete it when testing proved it wasn't needed.

[rnk]

LGTM with the #if 0 code removed. The promotion seems like a nice simplification. :)

lib/CodeGen/WinEHPrepare.cpp

384

My understanding is that you are also required to change the INITIALIZE_TM_PASS code to use INITIALIZE_TM_PASS_BEGIN / END and INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass). See DwarfEHPrepare. I could be wrong, the pass registry stuff is all ugly goo that will hopefully be removed when the new pass manager happens.

[rnk]

(Setting the "accept revision" phab bit this time...)

One other thing worth thinking about is remapping phis of EH values in situations like this:

void might_throw();
void f() {
  try {
    try { might_throw(); } catch (int) { }
    try { might_throw(); } catch (int) { }
  } catch (int) {
  }
}

In this situation, there should be two landingpads, and the outermost EH dispatch block will use a phi of the two lpad selector values.

We can handle this later by recursively adding phis of selector values to ExtractedSelectors.

lib/CodeGen/WinEHPrepare.cpp

bool WinEHPrepare::runOnFunction(Function &Fn) {
   return true;
 }
 
 bool WinEHPrepare::doFinalization(Module &M) {
   return false;
 }
 
 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
 
 bool WinEHPrepare::prepareExceptionHandlers(
     Function &F, SmallVectorImpl<LandingPadInst *> &LPads) {
   // These containers are used to re-map frame variables that are used in
   // outlined catch and cleanup handlers.  They will be populated as the
   // handlers are outlined.
   FrameVarInfoMap FrameVarInfo;
 
   bool HandlersOutlined = false;
if (LPadMap.mapIfEHPtrLoad(Load)) {
       VMap[Inst] = UndefValue::get(Int8PtrType);
       return CloningDirector::SkipInstruction;
     }
 
     // Any other loads just get cloned.
     return CloningDirector::CloneInstruction;
   }
 
+  if (auto *Compare = dyn_cast<CmpInst>(Inst)) {
+    // Look for compare instructions that use selector values that were not
+    // defined in the current block.  A series of related catch dispatch blocks
+    // will share a loaded selector value, but after the first dispatch block
+    // we will have started outlining after the value is loaded.  We can
+    // spot this case by looking at the compare operands.
+    for (auto &U : Compare->operands()) {
+      // Ignore any operands we've already mapped.
+      if (VMap.count(U.get()))
+        continue;
+      if (auto *Load = dyn_cast<LoadInst>(U.get())) {
+        if (LPadMap.mapIfSelectorLoad(Load))
+          VMap[Load] = ConstantInt::get(SelectorIDType, 1);
+        break;
+      }
+    }
+    // Whether we mapped a selector load above or not, the compare gets cloned.
+    return CloningDirector::CloneInstruction;
+  }
+
   // Nested landing pads will be cloned as stubs, with just the
   // landingpad instruction and an unreachable instruction. When
   // all landingpads have been outlined, we'll replace this with the
   // llvm.eh.actions call and indirect branch created when the
   // landing pad was outlined.
   if (auto *NestedLPad = dyn_cast<LandingPadInst>(Inst)) {
     Instruction *NewInst = NestedLPad->clone();
     if (NestedLPad->hasName())
WinEHCatchDirector::handleEndCatch(ValueToValueMapTy &VMap,
   // or at the end of the catch block.  However, a catch-all handler may call
   // end catch from the original landing pad.  If the call occurs in a nested
   // landing pad block, we must skip it and continue so that the landing pad
   // gets cloned.
   auto *ParentBB = IntrinCall->getParent();
   if (ParentBB->isLandingPad() && !LPadMap.isOriginLandingPadBlock(ParentBB))
     return CloningDirector::SkipInstruction;
 
-  // If an end catch occurs anywhere else the next instruction should be an
-  // unconditional branch instruction that we want to replace with a return
-  // to the the address of the branch target.
-  const BasicBlock *EndCatchBB = IntrinCall->getParent();
-  const TerminatorInst *Terminator = EndCatchBB->getTerminator();
-  const BranchInst *Branch = dyn_cast<BranchInst>(Terminator);
-  assert(Branch && Branch->isUnconditional());
-  assert(std::next(BasicBlock::const_iterator(IntrinCall)) ==
-         BasicBlock::const_iterator(Branch));
-
-  BasicBlock *ContinueLabel = Branch->getSuccessor(0);
-  ReturnInst::Create(NewBB->getContext(), BlockAddress::get(ContinueLabel),
-                     NewBB);
-  ReturnTargets.push_back(ContinueLabel);
+  // If an end catch occurs anywhere else we want to terminate the handler
+  // with a return to the code that follows the endcatch call.  If the
+  // next instruction is not an unconditional branch, we need to split the
+  // block to provide a clear target for the return instruction.
+  BasicBlock *ContinueBB;
+  auto Next = std::next(BasicBlock::const_iterator(IntrinCall));
+  const BranchInst *Branch = dyn_cast<BranchInst>(Next);
+  if (!Branch || !Branch->isUnconditional()) {
+    // We're interrupting the cloning process at this location, so the
+    // const_cast we're doing here will not cause a problem.
+    ContinueBB = SplitBlock(const_cast<BasicBlock *>(ParentBB),
+                            const_cast<IntrinsicInst *>(IntrinCall));
+  } else {
+    ContinueBB = Branch->getSuccessor(0);
+  }
+
+  ReturnInst::Create(NewBB->getContext(), BlockAddress::get(ContinueBB), NewBB);
+  ReturnTargets.push_back(ContinueBB);
 
   // We just added a terminator to the cloned block.
   // Tell the caller to stop processing the current basic block so that
   // the branch instruction will be skipped.
   return CloningDirector::StopCloningBB;
 }
 
 CloningDirector::CloningAction WinEHCatchDirector::handleTypeIdFor(
if (Branch) {
         for (BasicBlock::iterator II = BB->getFirstNonPHIOrDbg(),
                                   IE = BB->end();
              II != IE; ++II) {
           Instruction *Inst = II;
           if (LPadMap && LPadMap->isLandingPadSpecificInst(Inst))
             continue;
           if (Inst == Compare || Inst == Branch)
             continue;
-          if (!Inst->hasOneUse() || (Inst->user_back() != Compare))
+          // Loads of selector values may be used by multiple blocks, but if the
+          // loaded value is used in this block, it should be used by the
+          // compare instruction.
+          if (auto *Load = dyn_cast<LoadInst>(Inst)) {
+            for (auto *U : Load->users()) {
+              if (cast<Instruction>(U)->getParent() == BB && U != Compare)
                 return createCleanupHandler(CleanupHandlerMap, BB);
+            }
+            continue;
+          }
           if (match(Inst, m_Intrinsic<Intrinsic::eh_typeid_for>()))
             continue;
-          if (!isa<LoadInst>(Inst))
-            return createCleanupHandler(CleanupHandlerMap, BB);
         }
         // The selector dispatch block should always terminate our search.
         assert(BB == EndBB);
         return nullptr;
       } else {
         // Look for empty blocks with unconditional branches.
         for (BasicBlock::iterator II = BB->getFirstNonPHIOrDbg(),
                                   IE = BB->end();
if (Branch) {
           return nullptr;
         // The branch was unconditional.
         BB = Branch->getSuccessor(0);
         continue;
       } // End else of if branch was conditional
     }   // End if Branch
 
     // Anything else makes this interesting cleanup code.
     return createCleanupHandler(CleanupHandlerMap, BB);
   }
   return nullptr;
 }