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

Authored by mattd on Thu, Jan 25, 11:36 AM.

Details

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).

Diff Detail

Repository
rL LLVM
mattd created this revision.Thu, Jan 25, 11:36 AM
vsk accepted this revision.Thu, Jan 25, 11:53 AM

LGTM, this is great.

lib/Transforms/Utils/Local.cpp
1349 ↗(On Diff #131489)

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

This revision is now accepted and ready to land.Thu, Jan 25, 11:53 AM
aprantl accepted this revision.Thu, Jan 25, 11:56 AM

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?

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 added a comment.Thu, Jan 25, 11:59 AM

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 added inline comments.Thu, Jan 25, 12:00 PM
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.

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

That would help readability a lot, etc..

vsk added a comment.Thu, Jan 25, 12:04 PM

That would help readability a lot, etc..

Sure thing

This revision was automatically updated to reflect the committed changes.
vsk added a comment.Thu, Jan 25, 3:08 PM

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
 }

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

vsk added a comment.Thu, Jan 25, 3:23 PM

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 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.

In D42551#988512, @vsk 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 added a comment.Thu, Jan 25, 3:28 PM

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

davide reopened this revision.Thu, Jan 25, 3:29 PM

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

This revision is now accepted and ready to land.Thu, Jan 25, 3:29 PM
davide requested changes to this revision.Thu, Jan 25, 3:30 PM
This revision now requires changes to proceed.Thu, Jan 25, 3:30 PM
vsk added a comment.Thu, Jan 25, 3:30 PM
In D42551#988512, @vsk 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 added a comment.Thu, Jan 25, 3:32 PM

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

mattd added a comment.Thu, Jan 25, 3:33 PM
In D42551#988531, @vsk wrote:
In D42551#988512, @vsk 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 added a comment.Thu, Jan 25, 3:42 PM

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

vsk added a comment.Thu, Jan 25, 3:50 PM

Checked in the fix: r323482

mattd added a comment.Thu, Jan 25, 4:05 PM
In D42551#988556, @vsk wrote:

Checked in the fix: r323482

Thanks!

vsk accepted this revision.Fri, Jan 26, 1:37 PM

The bots are happy with r323482.

mattd updated this revision to Diff 133074.Tue, Feb 6, 2:09 PM

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 added inline comments.Tue, Feb 6, 2:26 PM
lib/Transforms/Utils/Local.cpp
1371 ↗(On Diff #133074)
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 added inline comments.Tue, Feb 6, 2:43 PM
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 updated this revision to Diff 133110.Tue, Feb 6, 4:14 PM
  • Removed function comments and lifetime intrinsics from the test case.
  • Use isEHPad in place of the explicit CatchSwitch instruction check.
vsk accepted this revision.Tue, Feb 6, 4:18 PM

Thanks, lgtm.

mattd added a comment.Tue, Feb 13, 9:05 AM

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 added a comment.Tue, Feb 13, 9:37 AM

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 added a comment.Tue, Feb 13, 9:49 AM
In D42551#1006407, @vsk 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 added a comment.Tue, Feb 13, 9:59 AM

@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."

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.

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

@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.

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

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 added a comment.Wed, Feb 21, 4:45 PM

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 added a comment.Fri, Feb 23, 9:35 AM

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.

This revision was not accepted when it landed; it landed in state Needs Review.Fri, Feb 23, 9:40 AM
This revision was automatically updated to reflect the committed changes.