[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 ↗

(On Diff #131489)

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 ↗

(On Diff #131489)

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 ↗

(On Diff #131489)

Yep, everything else looks like code movement.

[mattd]

lib/Transforms/Utils/LCSSA.cpp

226 ↗

(On Diff #131489)

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 ↗

(On Diff #133074)

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

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

36 ↗

(On Diff #133074)

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 ↗

(On Diff #133074)

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

36 ↗

(On Diff #133074)

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.

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

 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #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;
 
 #define DEBUG_TYPE "lcssa"
 
 STATISTIC(NumLCSSA, "Number of live out of a loop variables");
 
while (!Worklist.empty()) {
 
     // Post process PHI instructions that were inserted into another disjoint
     // loop and update their exits properly.
     for (auto *PostProcessPN : PostProcessPHIs)
       if (!PostProcessPN->use_empty())
         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.
   for (PHINode *PN : PHIsToRemove) {
     assert (PN->use_empty() && "Trying to remove a phi with uses.");
     PN->eraseFromParent();
   }
   return Changed;

llvm/trunk/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
 entry:
   br label %loop.interior
 loop.interior:    ; preds = %post.if, %entry
   br i1 %S2, label %if.true, label %if.false
 if.true:    ; preds = %loop.interior
   %X1 = add i32 0, 0    ; <i32> [#uses=1]
   br label %post.if
 if.false:   ; preds = %loop.interior
   %X2 = add i32 0, 1    ; <i32> [#uses=1]
   br label %post.if
 post.if:    ; preds = %if.false, %if.true
   %X3 = phi i32 [ %X1, %if.true ], [ %X2, %if.false ]    ; <i32> [#uses=1]
   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
   %X4 = add i32 3, %X3    ; <i32> [#uses=0]
   ret void
 }