[Reassociation] Place moved instructions after landing pads

[greened]

Summary

Reassociation's NegateValue moved instructions to the beginning of
blocks (after PHIs) without checking for landingpad instructions.
It's possible for reassociation to happen within a landingpad block so
we need to make sure we don't move things too early in the block.
This change advances the insertion point past any landingpad.

If the insertion point is then a catchswitch, don't try to reuse an
existing neg but just create a new one at BI, as if we hadn't found
an existing neg at all.

[greened]

Rebased on latest master and fixed test name.

[efriedma]

llvm/lib/Transforms/Scalar/Reassociate.cpp

876

Explicitly checking for LandingPad isn't sufficient on Windows. There are two issues: one, you need to use isEHPad() to check for all the relevant exception-handling instructions, and two, you can't insert a negate into a block with a catchswitch.

[greened]

llvm/lib/Transforms/Scalar/Reassociate.cpp

876

This code moves the negate around within the local block, so presumably the negate is already in the block and therefore there should be no catchswitch, right?

I will update this to use isEHPad. Thanks!

[efriedma]

llvm/lib/Transforms/Scalar/Reassociate.cpp

876

This code moves the negate around within the local block

No? It moves the negate into the same block as the definition of "V", which as far as I can tell is not the same block where the "sub" instruction was originally located. (There's a dominance relationship, but that isn't really helpful here.)

In particular, the case I'm worried about is where "V" is a phi in the same basic block as a catchswitch.

[greened]

Updated to use isEHPad.

[greened]

llvm/lib/Transforms/Scalar/Reassociate.cpp

876

Ack, you are right. In the code where I observed the crash they were in the same block but it does not have to be so. Will update.

[greened]

llvm/lib/Transforms/Scalar/Reassociate.cpp

876

Hrm. If we get into the situation where V is a PHI and there's a catchswitch right after it, what should we do? Just bail out of the loop and create a new neg before BI? That seems better than trying to replicate the neg at each destination of the catchswitch. I am not at all familiar with this code so I don't know what the implications are.

[greened]

Bail out of the loop that found an existing neg if there is a catchswitch
and just create a new neg instead.

[efriedma]

llvm/lib/Transforms/Scalar/Reassociate.cpp

891

I don't think this does what you want; isEHPad() is true for catchswitch. (It would be nice to have a testcase.)

I'm fine with bailing out of the loop in this rare case.

[greened]

llvm/lib/Transforms/Scalar/Reassociate.cpp

891

You are right. Unfortunately, I am not confident I could construct a valid artificial testcase using catchswitch.

[greened]

Updated to account for isEHPad including catchswitch. I'm not very happy with the hacky use of FoundCatchSwitch but could not think of a way to do this that keeps things relatively clear/readable and doesn't put the for loop into a deeper nesting level or completely reformat the function.

[efriedma]

To produce a catchswitch with a PHI, you can run "clang --target=aarch64-pc-windows-msvc -S -emit-llvm -O2" over something like the following:

void g();
void g2();
void use(int, int);
void f(bool b) {
  int z;
  try {
    if (b) {
      z = 3;
      g();
    } else {
      z = 5;
      g2();
    }
  } catch (...) {
    return use(z,-z);
  }
}

You should be able to modify that to produce an appropriate testcase.

[greened]

Added a test for catchswitch and fixed a bug with falling off the end of a basic block.

[efriedma]

LGTM with a minor comment.

llvm/lib/Transforms/Scalar/Reassociate.cpp

877

Maybe adjust this comment a little? V could also be a PHI in a non-landingpad block.

[FlameTop]

Looks like some lines got truncated from the head of the first test file. Test is failing due to no run line.

[greened]

In D61089#1495346, @FlameTop wrote:

Looks like some lines got truncated from the head of the first test file. Test is failing due to no run line.

I think Reid checked in a fix before I could get to it. Thanks for the report.

llvm/lib/Transforms/Scalar/Reassociate.cpp

for (User *U : V->users()) {
     // non-instruction value) or right after the definition.  These negates will
     // be zapped by reassociate later, so we don't need much finesse here.
     BinaryOperator *TheNeg = cast<BinaryOperator>(U);
 
     // Verify that the negate is in this function, V might be a constant expr.
     if (TheNeg->getParent()->getParent() != BI->getParent()->getParent())
       continue;
 
+    bool FoundCatchSwitch = false;
+
     BasicBlock::iterator InsertPt;
     if (Instruction *InstInput = dyn_cast<Instruction>(V)) {
       if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) {
         InsertPt = II->getNormalDest()->begin();
       } else {
         InsertPt = ++InstInput->getIterator();
       }
-      while (isa<PHINode>(InsertPt)) ++InsertPt;
+
+      const BasicBlock *BB = InsertPt->getParent();
+
+      // It's possible that V is a PHI in a landingpad block, so make
+      // sure we don't move anything before the landingpad.
+      while (InsertPt != BB->end() && (isa<PHINode>(InsertPt) ||
+                                       InsertPt->isEHPad())) {
+        if (isa<CatchSwitchInst>(InsertPt))
+          FoundCatchSwitch = true;
+        ++InsertPt;
+      }
     } else {
       InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin();
     }
+
+    // We found a catchswitch in the block where we want to move the
+    // neg.  We cannot move anything into that block.  Bail and just
+    // create the neg before BI, as if we hadn't found an existing
+    // neg.
+    if (FoundCatchSwitch)
+      break;
+
     TheNeg->moveBefore(&*InsertPt);
     if (TheNeg->getOpcode() == Instruction::Sub) {
       TheNeg->setHasNoUnsignedWrap(false);
       TheNeg->setHasNoSignedWrap(false);
     } else {
       TheNeg->andIRFlags(BI);
     }
     ToRedo.insert(TheNeg);

llvm/test/Transforms/Reassociate/reassociate-catchswitch.ll

+; ModuleID = 'bugpoint-reduced-simplified.bc'
+source_filename = "catchswitch.cpp"
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc19.11.0"
+
+define dso_local void @"?f@@YAX_N@Z"(i1 %b) local_unnamed_addr #0 personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  br i1 %b, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  invoke void @"?g@@YAXXZ"()
+          to label %cleanup unwind label %catch.dispatch
+
+if.else:                                          ; preds = %entry
+  invoke void @"?g2@@YAXXZ"()
+          to label %cleanup unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %if.else, %if.then
+  %z.0 = phi i32 [ 3, %if.then ], [ 5, %if.else ]
+  %0 = catchswitch within none [label %catch] unwind to caller
+
+catch:                                            ; preds = %catch.dispatch
+  %1 = catchpad within %0 [i8* null, i32 64, i8* null]
+  %blech = sub nsw i32 5, %z.0
+  %sub = sub nsw i32 %blech, %z.0
+  call void @"?use@@YAXHH@Z"(i32 %z.0, i32 %sub) [ "funclet"(token %1) ]
+  unreachable
+
+cleanup:                                          ; preds = %if.else, %if.then
+  ret void
+}
+
+declare dso_local void @"?g@@YAXXZ"() local_unnamed_addr #0
+
+declare dso_local i32 @__CxxFrameHandler3(...)
+
+declare dso_local void @"?g2@@YAXXZ"() local_unnamed_addr #0
+
+declare dso_local void @"?use@@YAXHH@Z"(i32, i32) local_unnamed_addr #0
+
+attributes #0 = { "use-soft-float"="false" }

llvm/test/Transforms/Reassociate/reassociate-landingpad.ll

+; Reassociate used to move the negation of $time_1_P14.0 above the
+; landingpad.
+;
+; RUN: opt -reassociate -disable-output < %s
+;
+; ModuleID = 'bugpoint-reduced-simplified.bc'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%"lp.2234.4378.7378.12512.15079.17646.20213.22780.25347.27914.40747.53580.74113.76680.86947.89514.92081.94648.115163.130561" = type { i8*, i32 }
+%__type_info.2235.4379.7379.12513.15080.17647.20214.22781.25348.27915.40748.53581.74114.76681.86948.89515.92082.94649.115162.130560 = type { i64*, i8* }
+
+declare i32 @__gxx_personality_v0(...)
+
+declare void @b() #0
+
+define void @a() #0 personality i32 (...)* @__gxx_personality_v0 {
+", bb1":
+  invoke void @b()
+          to label %invoke.cont unwind label %"bb22"
+
+", bb8":                                          ; preds = %invoke.cont
+  invoke void @c()
+          to label %invoke.cont25 unwind label %"bb22"
+
+", bb15":                                         ; preds = %invoke.cont
+  ret void
+
+"bb22":     ; preds = %", bb8", %", bb1"
+  %"$time_1_P14.0" = phi i64 [ undef, %", bb8" ], [ undef, %", bb1" ]
+  %0 = landingpad %"lp.2234.4378.7378.12512.15079.17646.20213.22780.25347.27914.40747.53580.74113.76680.86947.89514.92081.94648.115163.130561"
+          cleanup
+          catch %__type_info.2235.4379.7379.12513.15080.17647.20214.22781.25348.27915.40748.53581.74114.76681.86948.89515.92082.94649.115162.130560* null
+  %r79 = sub i64 0, %"$time_1_P14.0"
+  %r81 = add i64 %r79, undef
+  %r93 = add i64 %r81, undef
+  %r95 = sub i64 %r93, %"$time_1_P14.0"
+  %r98 = icmp ult i64 %r95, undef
+  unreachable
+
+invoke.cont:                                      ; preds = %", bb1"
+  br i1 undef, label %", bb15", label %", bb8"
+
+invoke.cont25:                                    ; preds = %", bb8"
+  unreachable
+}
+
+declare void @c() #0
+
+attributes #0 = { "no-frame-pointer-elim-non-leaf" }
+
+!llvm.module.flags = !{!0}
+
+!0 = !{i32 1, !"Debug Info Version", i32 3}