[Debug] Add dbg.value intrinsics for PHIs created during LCSSA.

[mattd]

Summary

This patch is an enhancement to propagate dbg.value information when Phis are created on behalf of LCSSA.
I noticed a case where a value carried across a loop was reported as <optimized out>.

Specifically this case:

int bar(int x, int y) {
  return x + y;
}

int foo(int size) {
  int val = 0;
  for (int i = 0; i < size; ++i) {
    val = bar(val, i);  // Both val and i are correct
  }
  return val; // <optimized out>
}

In the above case, after all of the interesting computation completes our value
is reported as "optimized out." This change will add a dbg.value to correct this.

This patch also moves the dbg.value insertion routine from LoopRotation.cpp
into Local.cpp, so that we can share it in both places (LoopRotation and LCSSA).

[vsk]

LGTM, this is great.

lib/Transforms/Utils/Local.cpp

1349

No need to check !BB defensively since we're asserting it.

[aprantl]

Thanks, this LGTM. Patches are generally easier to review when you separate out the NFC parts (moving the function to local) into a separate commit.

lib/Transforms/Utils/LCSSA.cpp

226

Is this the one line that is not NFC in this patch?

[mattd]

Thanks for the approval @vsk. I do not have commit access, so I'll need someone to commit this on my behalf. Should I remove the paranoia- check you noted?

[vsk]

In D42551#988319, @mattd wrote:

Thanks for the approval @vsk. I do not have commit access, so I'll need someone to commit this on my behalf. Should I remove the paranoia- check you noted?

It's OK, I'll remove the check and commit this for you.

lib/Transforms/Utils/LCSSA.cpp

226

Yep, everything else looks like code movement.

[mattd]

lib/Transforms/Utils/LCSSA.cpp

226

Tanks for the review @aprantl. This line is a functional change. Previously we did not introduce dbg.values here.

[davide]

ehm, just one thing, can you please commit the NFC refactoring separately? (i.e. can you split this in two separate patches)

[davide]

That would help readability a lot, etc..

[vsk]

In D42551#988327, @davide wrote:

That would help readability a lot, etc..

Sure thing

[mattd]

Thanks @vsk

[vsk]

I think we hit a snafu:

http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/8260

The unwind destination does not have an exception handling instruction!
  %call.i84 = invoke i32 %14(%"class.std::__1::basic_streambuf"* nonnull %10)
          to label %invoke.cont9 unwind label %lpad6, !dbg !11517
LandingPadInst not the first non-PHI instruction in the block.
  %18 = landingpad { i8*, i32 }
          catch i8* null, !dbg !11530
The unwind destination does not have an exception handling instruction!
  %call.i89 = invoke i32 %13(%"class.std::__1::basic_streambuf"* nonnull %9)
          to label %invoke.cont6 unwind label %lpad3, !dbg !11918
LandingPadInst not the first non-PHI instruction in the block.
  %17 = landingpad { i8*, i32 }
          catch i8* null, !dbg !11933
The unwind destination does not have an exception handling instruction!
  %call.i86 = invoke i32 %14(%"class.std::__1::basic_streambuf.4"* nonnull %10)
          to label %invoke.cont9 unwind label %lpad6, !dbg !15662
LandingPadInst not the first non-PHI instruction in the block.
  %18 = landingpad { i8*, i32 }
          catch i8* null, !dbg !15673
The unwind destination does not have an exception handling instruction!
  %call.i91 = invoke i32 %13(%"class.std::__1::basic_streambuf.4"* nonnull %9)
          to label %invoke.cont6 unwind label %lpad3, !dbg !16044
LandingPadInst not the first non-PHI instruction in the block.
  %17 = landingpad { i8*, i32 }
          catch i8* null, !dbg !16057
LLVM ERROR: Broken module found, compilation aborted!

Candidate fix:

diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index a7eaffd1a7a..05194a1aed5 100644
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -1373,7 +1373,7 @@ void llvm::insertDebugValuesForPHIs(BasicBlock *BB,
         auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI));
         NewDbgII->setOperand(0, PhiMAV);
         BasicBlock *Parent = PHI->getParent();
-        NewDbgII->insertBefore(Parent->getFirstNonPHIOrDbgOrLifetime());
+        NewDbgII->insertAfter(Parent->getFirstNonPHIOrDbgOrLifetime());
       }
     }
   }
diff --git a/test/Transforms/LCSSA/basictest.ll b/test/Transforms/LCSSA/basictest.ll
index 284de862eec..7c6df70e1db 100644
--- a/test/Transforms/LCSSA/basictest.ll
+++ b/test/Transforms/LCSSA/basictest.ll
@@ -19,8 +19,9 @@ post.if:		; preds = %if.false, %if.true
 	br i1 %S2, label %loop.exit, label %loop.interior
 loop.exit:		; preds = %post.if
 ; CHECK: %X3.lcssa = phi i32
-; CHECK2: call void @llvm.dbg.value(metadata i32 %X3.lcssa, metadata !11, metadata !DIExpression()), !dbg !19
 ; CHECK: %X4 = add i32 3, %X3.lcssa
+; CHECK2: add i32 3, %X3.lcssa
+; CHECK2: call void @llvm.dbg.value(metadata i32 %X3.lcssa, metadata !11, metadata !DIExpression()), !dbg !19
 	%X4 = add i32 3, %X3		; <i32> [#uses=0]
 	ret void
 }

[aprantl]

I don't think this is correct. What if the first nonphi instruction is the terminator?

[vsk]

In D42551#988510, @aprantl wrote:

I don't think this is correct. What if the first nonphi instruction is the terminator?

Oh I see. What about just inserting the dbg.value before the terminator? That should work for landingpad etc.

[davide]

In D42551#988510, @aprantl wrote:

I don't think this is correct. What if the first nonphi instruction is the terminator?

Agree, this doesn't work for empty blocks. You can probably also have a block with only PHIs (dead phi-nodes) & a terminator as Adrian describes.

[davide]

In D42551#988512, @vsk wrote:

In D42551#988510, @aprantl wrote:

I don't think this is correct. What if the first nonphi instruction is the terminator?

Oh I see. What about just inserting the dbg.value before the terminator? That should work for landingpad etc.

I think the correct fix is that of skipping phis and landingpads (& maybe something else that requires to be the first instruction in a block?, don't remember, check langref or the verifier) and then insert the dbg value.

[mattd]

Additionally, I'm not sure insertingAfter would be correct either. It seems we might need a check for the cases that @davide mentions.

[davide]

There are other instructions that may be broken by this transformation, as LLVM requires them to be the first in the block, e.g. catchpad.
https://llvm.org/docs/LangRef.html#id1329

[vsk]

In D42551#988523, @davide wrote:

In D42551#988512, @vsk wrote:

In D42551#988510, @aprantl wrote:

I don't think this is correct. What if the first nonphi instruction is the terminator?

Oh I see. What about just inserting the dbg.value before the terminator? That should work for landingpad etc.

I think the correct fix is that of skipping phis and landingpads (& maybe something else that requires to be the first instruction in a block?, don't remember, check langref or the verifier) and then insert the dbg value.

BasicBlock::getFirstInsertionPt() seems to do it. Wdyt? http://llvm.org/doxygen/BasicBlock_8cpp_source.html#l00200

[vsk]

Davide and I chatted offline, and think BasicBlock::getFirstInsertionPt() should work. I'll test it out and watch the bots.

[mattd]

In D42551#988531, @vsk wrote:

In D42551#988523, @davide wrote:

In D42551#988512, @vsk wrote:

In D42551#988510, @aprantl wrote:

I don't think this is correct. What if the first nonphi instruction is the terminator?

Oh I see. What about just inserting the dbg.value before the terminator? That should work for landingpad etc.

I think the correct fix is that of skipping phis and landingpads (& maybe something else that requires to be the first instruction in a block?, don't remember, check langref or the verifier) and then insert the dbg value.

BasicBlock::getFirstInsertionPt() seems to do it. Wdyt? http://llvm.org/doxygen/BasicBlock_8cpp_source.html#l00200

That looks correct, as that routine checks both landing pad and phis.

[mattd]

I just ran a test on my end using getFirstInsertionPt, looks good, but no clue what greendragon will say.

[vsk]

Checked in the fix: r323482

[mattd]

In D42551#988556, @vsk wrote:

Checked in the fix: r323482

Thanks!

[vsk]

The bots are happy with r323482.

[mattd]

This is an updated patch to handle the insertion of dbg.value intrinsics on behalf of LCSSA PHI generation. The original logic was reverted due to a dbg.value instrinsic attempting to be inserted into a catchswitch block. According to LangRef, catchswitch are to be the only non-PHI instructions within a block:
"The catchswitch is both a terminator and a “pad” instruction, meaning that it must be both the first non-phi instruction and last instruction in the basic block. Therefore, it must be the only non-phi instruction in the block."

This patch restores the original logic, but with an added conditional that checks that the insertion point is not a catchswitch. The new test case was produced from PR36238 which uncovered the bug. I also hoisted the getParent and MetadataAsValue calls outside of the inner-loop, a bit of my own hand-spun licm.

The attached test case is a pass-fail situation. It will fail if built with assertions in the same location where PR36238 was triggering the assertion, or crash llvm otherwise.

[vsk]

lib/Transforms/Utils/Local.cpp

1371

Would isEHPad work better here (http://llvm.org/doxygen/classllvm_1_1Instruction.html#a5d3d315f678bc76e43b27d18e5d72829)?

test/Transforms/LCSSA/avoid-intrinsics-in-catchswitch.ll

37

Does the bug reproduce with the lifetime intrinsics stripped out? That might be a way to reduce the regression test a bit.

[mattd]

lib/Transforms/Utils/Local.cpp

1371

I was avoiding being so strict, but now that I think about it, since we are inserting instructions BEFORE the insertionPt and the other EH instructions require that they be the first non-PHI, I think we need to use isEHPad. Thanks for pointing that out.

test/Transforms/LCSSA/avoid-intrinsics-in-catchswitch.ll

37

Yes. I will strip those out. Thanks for the suggestion! I also removed some of the Attribute comments.

[mattd]

• Removed function comments and lifetime intrinsics from the test case.
• Use isEHPad in place of the explicit CatchSwitch instruction check.

[vsk]

Thanks, lgtm.

[mattd]

Ping. Is there anything else we need to do here? I think the remaining approval was due to the original patch being rejected because it did not cover the catch/landing pads, prior to using the getFirstInsertionPt().

[vsk]

In D42551#1006350, @mattd wrote:

Ping. Is there anything else we need to do here? I think the remaining approval was due to the original patch being rejected because it did not cover the catch/landing pads, prior to using the getFirstInsertionPt().

I'm not sure I follow, but the update of this patch from 02/06 looked good to me. To be safe I'll test this out with a stage2 build locally and report back.

[vsk]

In D42551#1006407, @vsk wrote:

In D42551#1006350, @mattd wrote:

Ping. Is there anything else we need to do here? I think the remaining approval was due to the original patch being rejected because it did not cover the catch/landing pads, prior to using the getFirstInsertionPt().

I'm not sure I follow, but the update of this patch from 02/06 looked good to me. To be safe I'll test this out with a stage2 build locally and report back.

No issues on a stage2 build (-O3 -g -fexceptions -fcxx-exceptions).

[mattd]

@vsk thanks! I was referring to a "requested change" on an earlier version of this patch, which (I think) is preventing this current change from showing up as "Ready to Land."

[• dberlin]

This adds another basic block walk per InstBB, because llvm::insertDebugValuesForPHIs walks the entire bb :(

LCSSA can already be quite slow.
Do you have compile time numbers on some of the cases where LCSSA is already slow.

[davide]

+ @mzolotukhin We have a test where LCSSA takes forever, we can measure the impact on that one, Michael is looking at this currently.

[mattd]

@dberlin, thanks for the comment. I do not have numbers for any of the cases where LCSSA is known to be a bottleneck, but I do see your point. Even on a small test case it is one of the more expensive passes, but that sample is probably too small to make any judgement upon.

[mattd]

@davide, thanks. I am interested to see what you all find out.

[mzolotukhin]

I checked on the test I had and didn't see any measurable change. If any slowdowns occur after this patch is committed, I'll let you know.

Michael

[mattd]

In D42551#1015339, @mzolotukhin wrote:

I checked on the test I had and didn't see any measurable change. If any slowdowns occur after this patch is committed, I'll let you know.

Great! Thanks for measuring this.

[mattd]

Based on @mzolotukhin's analysis, it doesn't seem that this change causes a significant performance impact, so I'm going ahead and pushing this patch.

lib/Transforms/Utils/LCSSA.cpp

 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 using namespace llvm;

         Worklist.push_back(PostProcessPN);
 
     // Keep track of PHI nodes that we want to remove because they did not have
-    // any uses rewritten.
+    // any uses rewritten. If the new PHI is used, store it so that we can
+    // try to propagate dbg.value intrinsics to it.
+    SmallVector<PHINode *, 2> NeedDbgValues;
     for (PHINode *PN : AddedPHIs)
       if (PN->use_empty())
         PHIsToRemove.insert(PN);
-
+      else
+        NeedDbgValues.push_back(PN);
+    insertDebugValuesForPHIs(InstBB, NeedDbgValues);
     Changed = true;
   }
   // Remove PHI nodes that did not have any uses rewritten.

lib/Transforms/Utils/Local.cpp

   // propagate the info through the new PHI.
   LLVMContext &C = BB->getContext();
   for (auto PHI : InsertedPHIs) {
+    BasicBlock *Parent = PHI->getParent();
+    // Avoid inserting an intrinsic into an EH block.
+    if (Parent->getFirstNonPHI()->isEHPad())
+      continue;
+    auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI));
     for (auto VI : PHI->operand_values()) {
       auto V = DbgValueMap.find(VI);
       if (V != DbgValueMap.end()) {
         auto *DbgII = cast<DbgInfoIntrinsic>(V->second);
         Instruction *NewDbgII = DbgII->clone();
-        auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI));
         NewDbgII->setOperand(0, PhiMAV);
-        BasicBlock *Parent = PHI->getParent();
         auto InsertionPt = Parent->getFirstInsertionPt();
         assert(InsertionPt != Parent->end() && "Ill-formed basic block");
         NewDbgII->insertBefore(&*InsertionPt);

test/Transforms/LCSSA/avoid-intrinsics-in-catchswitch.ll

+; RUN: opt < %s -debugify -licm -S 1>/dev/null
+;
+; The following test is from https://bugs.llvm.org/show_bug.cgi?id=36238
+; This test should pass (not assert or fault). The error that originally
+; provoked this test was regarding the LCSSA pass trying to insert a dbg.value
+; intrinsic into a catchswitch block.
+
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc19.11.0"
+
+%struct.e = type { i32 }
+%struct.d = type { i8 }
+%class.f = type { %class.b }
+%class.b = type { i8 }
+%struct.k = type opaque
+
+@"\01?l@@3HA" = local_unnamed_addr global i32 0, align 4
+
+define i32 @"\01?m@@YAJXZ"() personality i8* bitcast (i32 (...)* @__C_specific_handler to i8*) {
+entry:
+  %n = alloca %struct.e, align 4
+  %db = alloca i32, align 4
+  %o = alloca %struct.d, align 1
+  %q = alloca i8*, align 8
+  %r = alloca i32, align 4
+  %u = alloca i64, align 8
+  %s = alloca %class.f, align 1
+  %offset = alloca i64, align 8
+  %t = alloca i64, align 8
+  %status = alloca i32, align 4
+  call void (...) @llvm.localescape(%class.f* nonnull %s, i32* nonnull %status)
+  %0 = bitcast %struct.e* %n to i8*
+  %1 = bitcast i32* %db to i8*
+  %2 = getelementptr inbounds %struct.d, %struct.d* %o, i64 0, i32 0
+  %3 = bitcast i8** %q to i8*
+  %4 = bitcast i32* %r to i8*
+  %5 = bitcast i64* %u to i8*
+  %6 = getelementptr inbounds %class.f, %class.f* %s, i64 0, i32 0, i32 0
+  %7 = load i32, i32* @"\01?l@@3HA", align 4, !tbaa !3
+  %call = call %class.f* @"\01??0f@@QEAA@H@Z"(%class.f* nonnull %s, i32 %7)
+  %8 = bitcast i64* %offset to i8*
+  %9 = bitcast i64* %t to i8*
+  %10 = bitcast i32* %status to i8*
+  %11 = bitcast %class.f* %s to %struct.d*
+  %c = getelementptr inbounds %struct.e, %struct.e* %n, i64 0, i32 0
+  br label %for.cond
+
+for.cond:                                         ; preds = %cleanup.cont, %entry
+  %p.0 = phi i32 [ undef, %entry ], [ %call2, %cleanup.cont ]
+  invoke void @"\01?h@@YAXPEAH0HPEAIPEAPEAEPEA_K33PEAUd@@4@Z"(i32* nonnull %db, i32* nonnull %c, i32 undef, i32* nonnull %r, i8** nonnull %q, i64* nonnull %u, i64* nonnull %offset, i64* nonnull %t, %struct.d* nonnull %11, %struct.d* nonnull %o)
+          to label %__try.cont unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %for.cond
+  %12 = catchswitch within none [label %__except.ret] unwind label %ehcleanup
+
+__except.ret:                                     ; preds = %catch.dispatch
+  %13 = catchpad within %12 [i8* bitcast (i32 (i8*, i8*)* @"\01?filt$0@0@m@@" to i8*)]
+  catchret from %13 to label %cleanup7
+
+__try.cont:                                       ; preds = %for.cond
+  %tobool = icmp eq i32 %p.0, 0
+  br i1 %tobool, label %if.end, label %cleanup7
+
+if.end:                                           ; preds = %__try.cont
+  %call2 = invoke i32 @"\01?a@@YAJXZ"()
+          to label %cleanup.cont unwind label %ehcleanup
+
+cleanup.cont:                                     ; preds = %if.end
+  br label %for.cond
+
+ehcleanup:                                        ; preds = %if.end, %catch.dispatch
+  %14 = cleanuppad within none []
+  %g.i = getelementptr inbounds %class.f, %class.f* %s, i64 0, i32 0
+  call void @"\01??1b@@QEAA@XZ"(%class.b* nonnull %g.i) [ "funclet"(token %14) ]
+  cleanupret from %14 unwind to caller
+
+cleanup7:                                         ; preds = %__try.cont, %__except.ret
+  %p.2.ph = phi i32 [ 7, %__except.ret ], [ %p.0, %__try.cont ]
+  %g.i32 = getelementptr inbounds %class.f, %class.f* %s, i64 0, i32 0
+  call void @"\01??1b@@QEAA@XZ"(%class.b* nonnull %g.i32)
+  ret i32 %p.2.ph
+}
+
+declare %class.f* @"\01??0f@@QEAA@H@Z"(%class.f* returned, i32) unnamed_addr
+
+define internal i32 @"\01?filt$0@0@m@@"(i8* %exception_pointers, i8* %frame_pointer) personality i8* bitcast (i32 (...)* @__C_specific_handler to i8*) {
+entry:
+  %0 = tail call i8* @llvm.x86.seh.recoverfp(i8* bitcast (i32 ()* @"\01?m@@YAJXZ" to i8*), i8* %frame_pointer)
+  %1 = tail call i8* @llvm.localrecover(i8* bitcast (i32 ()* @"\01?m@@YAJXZ" to i8*), i8* %0, i32 0)
+  %2 = tail call i8* @llvm.localrecover(i8* bitcast (i32 ()* @"\01?m@@YAJXZ" to i8*), i8* %0, i32 1)
+  %status = bitcast i8* %2 to i32*
+  %agg.tmp = alloca %class.f, align 1
+  %3 = bitcast i8* %exception_pointers to i32**
+  %4 = load i32*, i32** %3, align 8
+  %5 = load i32, i32* %4, align 4
+  %6 = bitcast i8* %exception_pointers to %struct.k*
+  %7 = getelementptr inbounds %class.f, %class.f* %agg.tmp, i64 0, i32 0, i32 0
+  %8 = load i8, i8* %1, align 1
+  store i8 %8, i8* %7, align 1
+  %call = invoke i32 @"\01?j@@YAJVf@@JPEAUk@@PEAH@Z"(i8 %8, i32 %5, %struct.k* %6, i32* %status)
+          to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  %g.i = getelementptr inbounds %class.f, %class.f* %agg.tmp, i64 0, i32 0
+  call void @"\01??1b@@QEAA@XZ"(%class.b* nonnull %g.i)
+  ret i32 %call
+
+ehcleanup:                                        ; preds = %entry
+  %9 = cleanuppad within none []
+  %g.i2 = getelementptr inbounds %class.f, %class.f* %agg.tmp, i64 0, i32 0
+  call void @"\01??1b@@QEAA@XZ"(%class.b* nonnull %g.i2) [ "funclet"(token %9) ]
+  cleanupret from %9 unwind to caller
+}
+
+declare i8* @llvm.x86.seh.recoverfp(i8*, i8*)
+declare i8* @llvm.localrecover(i8*, i8*, i32)
+declare i32 @"\01?j@@YAJVf@@JPEAUk@@PEAH@Z"(i8, i32, %struct.k*, i32*) local_unnamed_addr
+declare i32 @__C_specific_handler(...)
+declare void @"\01?h@@YAXPEAH0HPEAIPEAPEAEPEA_K33PEAUd@@4@Z"(i32*, i32*, i32, i32*, i8**, i64*, i64*, i64*, %struct.d*, %struct.d*) local_unnamed_addr
+declare i32 @"\01?a@@YAJXZ"() local_unnamed_addr
+declare void @llvm.localescape(...)
+declare void @"\01??1b@@QEAA@XZ"(%class.b*) unnamed_addr
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 1, !"wchar_size", i32 2}
+!1 = !{i32 7, !"PIC Level", i32 2}
+!2 = !{!"clang"}
+!3 = !{!4, !4, i64 0}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C++ TBAA"}

test/Transforms/LCSSA/basictest.ll

 ; RUN: opt < %s -lcssa -S | FileCheck %s
 ; RUN: opt < %s -passes=lcssa -S | FileCheck %s
+; RUN: opt < %s -debugify -lcssa -S | FileCheck -check-prefix=CHECK2 %s
 
 define void @lcssa(i1 %S2) {
 ; CHECK-LABEL: @lcssa

   br i1 %S2, label %loop.exit, label %loop.interior
 loop.exit:    ; preds = %post.if
 ; CHECK: %X3.lcssa = phi i32
+; CHECK2: call void @llvm.dbg.value(metadata i32 %X3.lcssa, metadata !11, metadata !DIExpression()), !dbg !19
 ; CHECK: %X4 = add i32 3, %X3.lcssa
-
-; CHECK2: call void @llvm.dbg.value(metadata i32 %X3.lcssa, metadata !11, metadata !DIExpression()), !dbg !19
-; CHECK2-NEXT: add i32 3, %X3.lcssa
-; CHECK2: ret void
   %X4 = add i32 3, %X3    ; <i32> [#uses=0]
   ret void
 }