This is an archive of the discontinued LLVM Phabricator instance.

Improve LSR debug-info
ClosedPublic

Authored by markus on Sep 10 2020, 11:02 PM.

Details

Summary

This is a prototype implementation of what was discussed in http://lists.llvm.org/pipermail/llvm-dev/2020-September/144990.html

So, given the following input compiled with clang -g -O3 lsrdbg.c -mllvm -print-after-all

#pragma donotinline
void foo(unsigned char *p) {
#pragma clang loop unroll(disable)
  for (unsigned char i = 0; i < 32; i++) {
    p += 3;
    *p = i;
  }
}

the IR shows that after LSR two llvm.dbg.value have been updated to reference %lsr.iv instead of the deleted %p.addr.05 and %add.ptr. Also note the compensation in one of the DIExpression.

*** IR Dump After Canonicalize Freeze Instructions in Loops ***
; Preheader:
entry:
  call void @llvm.dbg.value(metadata i8* %p, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  call void @llvm.dbg.value(metadata i8 0, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  br label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>)

; Loop:
for.body:                                         ; preds = %entry, %for.body
  %i.06 = phi i8 [ 0, %entry ], [ %inc, %for.body ]
  %p.addr.05 = phi i8* [ %p, %entry ], [ %add.ptr, %for.body ]
  call void @llvm.dbg.value(metadata i8 %i.06, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  call void @llvm.dbg.value(metadata i8* %p.addr.05, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  %add.ptr = getelementptr inbounds i8, i8* %p.addr.05, i64 3, !dbg !DILocation(line: 5, column: 7, scope: <0x1015cd00>)
  call void @llvm.dbg.value(metadata i8* %add.ptr, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  store i8 %i.06, i8* %add.ptr, align 1, !dbg !DILocation(line: 6, column: 8, scope: <0x1015cd00>), !tbaa <0x1015c2f8>
  %inc = add nuw nsw i8 %i.06, 1, !dbg !DILocation(line: 4, column: 38, scope: <0x1015c580>)
  call void @llvm.dbg.value(metadata i8 %inc, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  %exitcond.not = icmp eq i8 %inc, 32, !dbg !DILocation(line: 4, column: 31, scope: <0x1015c580>)
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>), !llvm.loop <0x1015d820>

; Exit blocks
for.cond.cleanup:                                 ; preds = %for.body
  ret void, !dbg !DILocation(line: 8, column: 1, scope: <0x101530a0>)
The following llvm.dbg.value needs to be updated:
  {(3 + %p)<nsw>,+,3}<nuw><%for.body> :  call void @llvm.dbg.value(metadata i8* %add.ptr, metadata !13, metadata !DIExpression()), !dbg !16
    {(3 + %p)<nsw>,+,3}<nuw><%for.body> :  %lsr.iv = phi i8* [ %scevgep, %entry ], [ %scevgep7, %for.body ]
      Match with offset 0
  {%p,+,3}<nuw><%for.body> :  call void @llvm.dbg.value(metadata i8* %p.addr.05, metadata !13, metadata !DIExpression()), !dbg !16
    {(3 + %p)<nsw>,+,3}<nuw><%for.body> :  %lsr.iv = phi i8* [ %scevgep, %entry ], [ %scevgep7, %for.body ]
      Match with offset -3
*** IR Dump After Loop Strength Reduction ***
; Preheader:
entry:
  call void @llvm.dbg.value(metadata i8* %p, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  call void @llvm.dbg.value(metadata i8 0, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  %scevgep = getelementptr i8, i8* %p, i64 3, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>)
  br label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>)

; Loop:
for.body:                                         ; preds = %entry, %for.body
  %lsr.iv = phi i8* [ %scevgep, %entry ], [ %scevgep7, %for.body ]
  %i.06 = phi i8 [ 0, %entry ], [ %inc, %for.body ]
  call void @llvm.dbg.value(metadata i8 %i.06, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  call void @llvm.dbg.value(metadata i8* %lsr.iv, metadata <0x10159f90>, metadata !DIExpression(DW_OP_constu, 3, DW_OP_minus, DW_OP_stack_value)), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  call void @llvm.dbg.value(metadata i8* %lsr.iv, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  store i8 %i.06, i8* %lsr.iv, align 1, !dbg !DILocation(line: 6, column: 8, scope: <0x1015cd00>), !tbaa <0x1015c2f8>
  %inc = add nuw nsw i8 %i.06, 1, !dbg !DILocation(line: 4, column: 38, scope: <0x1015c580>)
  call void @llvm.dbg.value(metadata i8 %inc, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  %scevgep7 = getelementptr i8, i8* %lsr.iv, i64 3, !dbg !DILocation(line: 4, column: 31, scope: <0x1015c580>)
  %exitcond.not = icmp eq i8 %inc, 32, !dbg !DILocation(line: 4, column: 31, scope: <0x1015c580>)
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>), !llvm.loop <0x1015d820>

; Exit blocks
for.cond.cleanup:                                 ; preds = %for.body
  ret void, !dbg !DILocation(line: 8, column: 1, scope: <0x101530a0>)

Diff Detail

Event Timeline

markus created this revision.Sep 10 2020, 11:02 PM
markus requested review of this revision.Sep 10 2020, 11:02 PM
markus added inline comments.Sep 10 2020, 11:12 PM
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
5878

There must be a better way to get hold of these. I would assume that LSR itself keeps track of the phi-node instructions it builds

5884

There must be a better way to do this. Perhaps we can modify DeleteDeadPHIs to accept an additional std::function argument that replaces the salvageDebugInfo call. It would still default to salvageDebugInfo but would allow us to pass a lambda here that does the SCEV comparison (and possible replace) on the dbg-uses right before an instruction is about to be removed.

markus added inline comments.Sep 11 2020, 12:40 AM
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
5884

Actually I see that commit 37b96d51d0cfc82a64598aaae2a567fa77e44de9 introduced a AboutToDeleteCallback that seem to serve exactly this purpose. We just need to expose it a bit further up in DeleteDeadPHIs.

Could you add test that showcases the effect?

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
5817

either we check the result or this should be
auto *UseOfI = cast<Instruction>()

markus updated this revision to Diff 291534.Sep 14 2020, 3:58 AM
markus added a reviewer: aprantl.

Change of appraoch. Instead of hooking into deleteDeadPHIs with an AboutToDeleteCallback we do a pre-pass to store a way the llvm.dbg.value of the loop as well as their SCEV expressions. After LSR has done its thing we go through those stored away llvm.dbg.value and if any of them now has an undef variable location we try to update it using its stored SCEV.

At least this way is clean and simple.

markus retitled this revision from [WIP] Improve LSR debug-info to Improve LSR debug-info.Sep 15 2020, 5:11 AM
markus edited the summary of this revision. (Show Details)
markus added a reviewer: dblaikie.
markus updated this revision to Diff 293092.Sep 21 2020, 1:23 AM

Updated with full context patch.

This is looking good, a few nits inline. Some slightly broader questions: do you know if there's any risk of debug-info affecting decisions made by SCEV, i.e. causing codegen to change when compiling -g? I don't have any reason to believe that could be the case, but it's a fear in the back of my mind.

Why does the DIExpression need to become a temporary / be cloned -- my understanding is that it's immutable metadata once created, so we should be able to keep the raw pointer to it.

I ran a clang-3.4 build with this patch, and according to llvm-locstats roughly 6000 variable locations have left the 0% coverage bucket, while roughly 6000 (potentially the same) variables have entered the 100% coverage bucket. That's about 0.2% of all variables, which is a decent improvement to get.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
5794

Can this be brace initialized?

5830
if (!isa<...>(...))
  continue;`

To save some indentation.

llvm/test/Transforms/LoopStrengthReduce/dbg-preserve-0.ll
30

It's best practice to capture the metadata reference number and confirm it further down with

CHECK: ![[VARNUMBER]]  = !DILocalVariable(name: "p"

or similar.

40–41

Best to delete any un-necessary attributes to reduce later maintenence.

markus updated this revision to Diff 293657.Sep 22 2020, 11:58 PM
markus marked 3 inline comments as done.

Fixed most of the review remarks.

This is looking good, a few nits inline. Some slightly broader questions: do you know if there's any risk of debug-info affecting decisions made by SCEV, i.e. causing codegen to change when compiling -g? I don't have any reason to believe that could be the case, but it's a fear in the back of my mind.

I would not expect so. AFAIK it is part of the LLVM debug-info philosophy that no transformation may be affected by the presence of debug-info so that would be a bug (elsewhere) if any transformation behaved differently due to the updated llvm.dbg.value intrinsics. As for that fact that we borrow the SCEV object from LSR to do some additional queries I cant see how that would reasonably affect any further queries passed to that SCEV object. But of course that is just my gut felling.

Why does the DIExpression need to become a temporary / be cloned -- my understanding is that it's immutable metadata once created, so we should be able to keep the raw pointer to it.

Turns out that it did not. I initially got some compilation errors that led me to beleive that the simple pointer approach was not possible. So I guess this is fine as long as the memory of the DIExpression we are pointing at is not released when it is possiby replaced during salvageDebugInfo as part of the normal LSR.

I ran a clang-3.4 build with this patch, and according to llvm-locstats roughly 6000 variable locations have left the 0% coverage bucket, while roughly 6000 (potentially the same) variables have entered the 100% coverage bucket. That's about 0.2% of all variables, which is a decent improvement to get.

Cool. Thanks for taking the time.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
5794

Quite possibly but I seem to be unable to pull it off :)

jmorse accepted this revision.Sep 23 2020, 3:16 AM

LGTM; I guess it'd be better if SCEV exposed a helper method, rather than this patch having to expose one, but that's well out of scope.

This revision is now accepted and ready to land.Sep 23 2020, 3:16 AM
bjope added a subscriber: bjope.Sep 28 2020, 12:54 AM
bjope added inline comments.
llvm/test/Transforms/LoopStrengthReduce/dbg-preserve-0.ll
6

Is the target triple needed?

Since the test is put in a general folder and not a target specific one, I guess this could lead to problems if the x86 target isn't built.

bjope added inline comments.Sep 28 2020, 12:58 AM
llvm/test/Transforms/LoopStrengthReduce/dbg-preserve-0.ll
44

I usually clear these (no gain in exposing my own directory structures in upstream test cases).

markus updated this revision to Diff 294902.Sep 29 2020, 1:13 AM

Addressed minor comments by @bjope

markus marked 2 inline comments as done.Sep 29 2020, 1:14 AM
bjope accepted this revision.Sep 29 2020, 4:39 AM

One more nit related to making computeConstantDifference public , but I'm happy with the fixup related to making the test case more target-agnostic.

llvm/include/llvm/Analysis/ScalarEvolution.h
1779

nit: Probably cleaner to move this declaration up into the public section, now when it is made available in the public API.

markus updated this revision to Diff 294940.Sep 29 2020, 5:16 AM
markus marked an inline comment as done.
markus updated this revision to Diff 295236.Sep 30 2020, 4:20 AM

Added safety code to make sure that we are comparing SCEVs of the same Type.

markus updated this revision to Diff 295492.Oct 1 2020, 1:47 AM

Tuns out that previous "safety code" caused problems when bootstraping clang. Apparently it is not safe to do getType() on all SCEVs so instead we now store away the type information and compare on the Value instead of the SCEV.

markus requested review of this revision.Oct 1 2020, 1:50 AM

Really minor changes since last approved revision but I would prefer if someone gave a renewed blessing.

bjope accepted this revision.Oct 2 2020, 6:36 AM

I've checked the late "better safe than sorry type checks" and they LGTM.

This revision is now accepted and ready to land.Oct 2 2020, 6:36 AM
This revision was landed with ongoing or failed builds.Oct 5 2020, 12:55 AM
This revision was automatically updated to reflect the committed changes.
nikic added a subscriber: nikic.Oct 5 2020, 10:10 AM

I've temporarily reverted this change, because it breaks building test-suite using the ReleaseLTO-g.cmake configuration: https://llvm-compile-time-tracker.com/show_error.php?commit=a3caf7f6102dc863425f9714b099af58397f0cd2

I thought this was a crash in clang, but now that I look again this is apparently the linker crashing, which should be GNU ld 2.34 in this case. So possibly the generated debug info exposes a linker bug?

nikic added a comment.Oct 5 2020, 10:18 AM

Ah, I forgot that this is an LTO configuration, so naturally it would crash inside the linker :) And indeed, the backtrace shows that the crash occurs during LSR:

0x00007ffff3b2bb7e in ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
(gdb) bt
#0  0x00007ffff3b2bb7e in ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#1  0x00007ffff3b2e990 in (anonymous namespace)::LoopStrengthReduce::runOnLoop(llvm::Loop*, llvm::LPPassManager&) () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#2  0x00007ffff40a586b in llvm::LPPassManager::runOnFunction(llvm::Function&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#3  0x00007ffff44d6858 in llvm::FPPassManager::runOnFunction(llvm::Function&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#4  0x00007ffff44d73a9 in llvm::FPPassManager::runOnModule(llvm::Module&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#5  0x00007ffff44d5a03 in llvm::legacy::PassManagerImpl::run(llvm::Module&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#6  0x00007ffff2b546ce in (anonymous namespace)::codegen(llvm::lto::Config const&, llvm::TargetMachine*, std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, unsigned int, llvm::Module&, llvm::ModuleSummaryIndex const&)
    () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#7  0x00007ffff2b55437 in llvm::lto::backend(llvm::lto::Config const&, std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, unsigned int, std::unique_ptr<llvm::Module, std::default_delete<llvm::Module> >, llvm::ModuleSummaryIndex&) () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#8  0x00007ffff2b4a9ed in llvm::lto::LTO::runRegularLTO(std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#9  0x00007ffff2b4b001 in llvm::lto::LTO::run(std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, std::function<std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)> (unsigned int, llvm::StringRef)>) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#10 0x00007ffff18604e5 in runLTO() () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#11 0x00007ffff1862047 in all_symbols_read_hook() ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#12 0x0000555555584572 in ?? ()
#13 0x00005555555784f7 in ?? ()
#14 0x0000555555564445 in ?? ()
#15 0x00007ffff7c760b3 in __libc_start_main (main=0x555555563df0, argc=253, argv=0x7fffffff87f8, 
    init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, 
    stack_end=0x7fffffff87e8) at ../csu/libc-start.c:308
#16 0x0000555555564aee in ?? ()
saugustine added inline comments.
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
5796

Someone reverted this change while I was tracking down a segfault related to it, but the problem is with this line.
Sometimes D->getVariableLocation() returns null because a variable's location has been lost or can't be found.

A simple fix would be a null check on this line:

if (!V || !SE.isSCEVable(V->getType())))

markus added a comment.Oct 6 2020, 5:47 AM

@nikic, @saugustine, thanks for reverting and having a look. I did not receive any notification mail about those build-bot failures AFAICT. I got two but one failure went away on a subsequent run and the other complained about internal compiler error in g++ which seemed unrelated. Anyway I will try to reproduce locally and address the issue as suggested. Thanks again.

markus updated this revision to Diff 308665.Dec 1 2020, 8:19 AM
markus added a reviewer: reames.

Addressing the issues with use of stored SCEV after IR had been deleted (see https://reviews.llvm.org/D91711).

The new approach is to, before rewrite, compute a set of SCEV equivalent values (with potential offset) and then store these values with a WeakVH to detect deletion.

After rewrite, for those llvm.dbg.value that now reference undef we pick one of the remaining equivalent values (if any).

So from a black-box point of view operation should be identical to before but now without abusing the SCEV API.

markus reopened this revision.Dec 1 2020, 8:19 AM
This revision is now accepted and ready to land.Dec 1 2020, 8:19 AM
markus requested review of this revision.Dec 1 2020, 8:20 AM
jmorse accepted this revision.Dec 7 2020, 9:52 AM

LGTM, this sounds like it works just as well as before, thanks for pursuing.

(I was wondering whether we need to handle dbg.values with nullptr operands, but with D80264 landed, we don't need to worry about that any more.

This revision is now accepted and ready to land.Dec 7 2020, 9:52 AM
This revision was landed with ongoing or failed builds.Dec 14 2020, 7:16 AM
This revision was automatically updated to reflect the committed changes.