[WinEH] Update LCSSA to handle catchswitch with handlers inside and outside a loop

[andrew.w.kaylor]

Summary

When a try block occurs inside a loop with one catch handler that continues in the loop and another that exits the loop, the catchswitch instruction (which returns a token value) will be used by blocks inside and outside the loop. This causes the LCSSA pass to want to create a PHI node in the block outside the loop to reference the catchswitch, but that isn't allowed.

This patch updates the LCSSA pass and the Loop::isLCSSAForm function to skip over token values.

[majnemer]

test/CodeGen/X86/catch-lcssa.ll

1 ↗

(On Diff #43195)

Can we move this test to "test/Transforms/LCSSA" and just use "opt -lcssa -S" ?

[mzolotukhin]

test/CodeGen/X86/catch-lcssa.ll

1 ↗

(On Diff #43195)

Also, could you please run "opt -instnamer" on the test?

[andrew.w.kaylor]

test/CodeGen/X86/catch-lcssa.ll

1 ↗

(On Diff #43195)

The reason I put it here was so that it wouldn't choke the non-X86 buildbots. I know I could add a REQUIRES line to the test, but it doesn't seem like that is the typical way this is handled.

I'll see if I can strip it down enough to work without referencing anything X86-specific.

[rnk]

test/CodeGen/X86/catch-lcssa.ll

1 ↗

(On Diff #43195)

You can use an x86 target triple in opt without the x86 backend just fine. There should be other examples of this.

[andrew.w.kaylor]

test/CodeGen/X86/catch-lcssa.ll

1 ↗

(On Diff #43195)

I would have thought so, but I broke a bunch of buildbots that way recently. In that case I was using the triple in the command line to run the test. Is it possible that just having it embedded in the IR yields a different result?

[majnemer]

test/CodeGen/X86/catch-lcssa.ll

1 ↗

(On Diff #43195)

IIRC, the test you added was for CodeGenPrep which is fundamentally a target-specific test. This is test is not so it should be fine to keep it generic.

[andrew.w.kaylor]

Moved and cleaned up test.

[majnemer]

LGTM

[reames]

I'm a bit concerned by this change. Specifically, I'm worried that various optimization passes have built in assumptions about what LCSSA means. If an optimization pass expects to have to only update PHIs in loop exists, this change could lead to crashes or potentially silent miscompiles. Have you reviewed the loop transform passes to understand the implications of the changed invariant?

[andrew.w.kaylor]

In D15630#313904, @reames wrote:

I'm a bit concerned by this change. Specifically, I'm worried that various optimization passes have built in assumptions about what LCSSA means. If an optimization pass expects to have to only update PHIs in loop exists, this change could lead to crashes or potentially silent miscompiles. Have you reviewed the loop transform passes to understand the implications of the changed invariant?

David tells me that CodeMetrics::analyzeBasicBlock already disables loop optimizations involving live-out token type SSA values.

I just reviewed all the passes that are calling either LoopInfo::isLCSSAForm() or LoopInfo::isRecursivelyLCSSAForm(), and it does appear to me that they will be safe with this change. Loop unroll and loop unswitch both call CodeMetrics::analyzeBasicBlock and I verified experimentally that the sort of code involved in this patch won't be unrolled. LCIM is slightly more involved, but I believe that it won't move code involving tokens. Finally, IndVarSimplify does exactly what you are suggesting (i.e. uses the existence of PHI nodes to determine whether a value is used on an exit path) but again I don't think there is a risk of it operating on token values.

[reames]

Thanks for checking. SGTM

Philip

llvm/trunk/lib/Analysis/LoopInfo.cpp

PHINode *Loop::getCanonicalInductionVariable() const {
   }
   return nullptr;
 }
 
 /// isLCSSAForm - Return true if the Loop is in LCSSA form
 bool Loop::isLCSSAForm(DominatorTree &DT) const {
   for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) {
     BasicBlock *BB = *BI;
-    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I)
+    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) {
+      // Tokens can't be used in PHI nodes and live-out tokens prevent loop
+      // optimizations, so for the purposes of considered LCSSA form, we
+      // can ignore them.
+      if (I->getType()->isTokenTy())
+        continue;
+
       for (Use &U : I->uses()) {
         Instruction *UI = cast<Instruction>(U.getUser());
         BasicBlock *UserBB = UI->getParent();
         if (PHINode *P = dyn_cast<PHINode>(UI))
           UserBB = P->getIncomingBlock(U);
 
         // Check the current block, as a fast-path, before checking whether
         // the use is anywhere in the loop.  Most values are used in the same
         // block they are defined in.  Also, blocks not reachable from the
         // entry are special; uses in them don't need to go through PHIs.
         if (UserBB != BB &&
             !contains(UserBB) &&
             DT.isReachableFromEntry(UserBB))
           return false;
       }
     }
+  }
 
   return true;
 }
 
 bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const {
   if (!isLCSSAForm(DT))
     return false;
 

llvm/trunk/lib/Transforms/Utils/LCSSA.cpp

 /// Given an instruction in the loop, check to see if it has any uses that are
 /// outside the current loop.  If so, insert LCSSA PHI nodes and rewrite the
 /// uses.
 static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
                                const SmallVectorImpl<BasicBlock *> &ExitBlocks,
                                PredIteratorCache &PredCache, LoopInfo *LI) {
   SmallVector<Use *, 16> UsesToRewrite;
 
+  // Tokens cannot be used in PHI nodes, so we skip over them.
+  // We can run into tokens which are live out of a loop with catchswitch
+  // instructions in Windows EH if the catchswitch has one catchpad which
+  // is inside the loop and another which is not.
+  if (Inst.getType()->isTokenTy())
+    return false;
+
   BasicBlock *InstBB = Inst.getParent();
 
   for (Use &U : Inst.uses()) {
     Instruction *User = cast<Instruction>(U.getUser());
     BasicBlock *UserBB = User->getParent();
     if (PHINode *PN = dyn_cast<PHINode>(User))
       UserBB = PN->getIncomingBlock(U);
 

llvm/trunk/test/Transforms/LCSSA/mixed-catch.ll

+; RUN: opt -lcssa -S < %s | FileCheck %s
+
+; This test is based on the following C++ code:
+;
+; void f()
+; {
+;   for (int i=0; i<12; i++) {
+;     try {
+;       if (i==3)
+;         throw i;
+;     } catch (int) {
+;       continue;
+;     } catch (...) { }
+;     if (i==3) break;
+;   }
+; }
+;
+; The loop info analysis identifies the catch pad for the second catch as being
+; outside the loop (because it returns to %for.end) but the associated
+; catchswitch block is identified as being inside the loop.  Because of this
+; analysis, the LCSSA pass wants to create a PHI node in the catchpad block
+; for the catchswitch value, but this is a token, so it can't.
+
+define void @f() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  %tmp = alloca i32, align 4
+  %i7 = alloca i32, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 12
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %cond = icmp eq i32 %i.0, 3
+  br i1 %cond, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  store i32 %i.0, i32* %tmp, align 4
+  %tmp1 = bitcast i32* %tmp to i8*
+  invoke void @_CxxThrowException(i8* %tmp1, %eh.ThrowInfo* nonnull @_TI1H) #1
+          to label %unreachable unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %if.then
+  %tmp2 = catchswitch within none [label %catch, label %catch2] unwind to caller
+
+catch:                                            ; preds = %catch.dispatch
+  %tmp3 = catchpad within %tmp2 [%rtti.TypeDescriptor2* @"\01??_R0H@8", i32 0, i32* %i7]
+  catchret from %tmp3 to label %for.inc
+
+catch2:                                           ; preds = %catch.dispatch
+  %tmp4 = catchpad within %tmp2 [i8* null, i32 64, i8* null]
+  catchret from %tmp4 to label %for.end
+
+for.inc:                                          ; preds = %catch, %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %catch2, %for.cond
+  ret void
+
+unreachable:                                      ; preds = %if.then
+  unreachable
+}
+
+; CHECK-LABEL: define void @f()
+; CHECK: catch2:
+; CHECK-NOT: phi
+; CHECK:   %tmp4 = catchpad within %tmp2
+; CHECK:   catchret from %tmp4 to label %for.end
+
+%rtti.TypeDescriptor2 = type { i8**, i8*, [3 x i8] }
+%eh.CatchableType = type { i32, i32, i32, i32, i32, i32, i32 }
+%eh.CatchableTypeArray.1 = type { i32, [1 x i32] }
+%eh.ThrowInfo = type { i32, i32, i32, i32 }
+
+$"\01??_R0H@8" = comdat any
+
+$"_CT??_R0H@84" = comdat any
+
+$_CTA1H = comdat any
+
+$_TI1H = comdat any
+
+@"\01??_7type_info@@6B@" = external constant i8*
+@"\01??_R0H@8" = linkonce_odr global %rtti.TypeDescriptor2 { i8** @"\01??_7type_info@@6B@", i8* null, [3 x i8] c".H\00" }, comdat
+@__ImageBase = external constant i8
+@"_CT??_R0H@84" = linkonce_odr unnamed_addr constant %eh.CatchableType { i32 1, i32 trunc (i64 sub nuw nsw (i64 ptrtoint (%rtti.TypeDescriptor2* @"\01??_R0H@8" to i64), i64 ptrtoint (i8* @__ImageBase to i64)) to i32), i32 0, i32 -1, i32 0, i32 4, i32 0 }, section ".xdata", comdat
+@_CTA1H = linkonce_odr unnamed_addr constant %eh.CatchableTypeArray.1 { i32 1, [1 x i32] [i32 trunc (i64 sub nuw nsw (i64 ptrtoint (%eh.CatchableType* @"_CT??_R0H@84" to i64), i64 ptrtoint (i8* @__ImageBase to i64)) to i32)] }, section ".xdata", comdat
+@_TI1H = linkonce_odr unnamed_addr constant %eh.ThrowInfo { i32 0, i32 0, i32 0, i32 trunc (i64 sub nuw nsw (i64 ptrtoint (%eh.CatchableTypeArray.1* @_CTA1H to i64), i64 ptrtoint (i8* @__ImageBase to i64)) to i32) }, section ".xdata", comdat
+
+declare void @_CxxThrowException(i8*, %eh.ThrowInfo*)
+
+declare i32 @__CxxFrameHandler3(...)