This is an archive of the discontinued LLVM Phabricator instance.

Differential D29254

Do not propagate DebugLoc across basic blocks
ClosedPublic

Authored by twoh on Jan 28 2017, 3:50 PM.

Details

Reviewers
andreadb
aprantl
wolfgangp
Commits
rG75acec8a1487: Do not propagate DebugLoc across basic blocks
rL293688: Do not propagate DebugLoc across basic blocks
Summary

DebugLoc shouldn't be propagated across basic blocks to prevent incorrect stepping and imprecise sample profile result. rL288903 addressed the wrong DebugLoc propagation issue by limiting the copy of DebugLoc when GVN removes a fully redundant load that is dominated by some other load. However, DebugLoc is still incorrectly propagated in the following example:

1:  extern int g;
2: 
3:  void foo(int x, int y, int z) {
4:    if (x)
5:      g = 0;
6:    else
7:      g = 1;
8:
9:    int i = 0;
10:   for ( ; i < y ; i++)
11:     if (i > z)
12:       g++;
13: }

Below is LLVM IR representation of the program before GVN:

@g = external local_unnamed_addr global i32, align 4

; Function Attrs: nounwind uwtable
define void @foo(i32 %x, i32 %y, i32 %z) local_unnamed_addr #0 !dbg !4 {
entry:
  %not.tobool = icmp eq i32 %x, 0, !dbg !8
  %.sink = zext i1 %not.tobool to i32, !dbg !8
  store i32 %.sink, i32* @g, align 4, !tbaa !9
  %cmp8 = icmp sgt i32 %y, 0, !dbg !13
  br i1 %cmp8, label %for.body.preheader, label %for.end, !dbg !17

for.body.preheader:                               ; preds = %entry
  br label %for.body, !dbg !19

for.body:                                         ; preds = %for.body.preheader, %for.inc
  %i.09 = phi i32 [ %inc4, %for.inc ], [ 0, %for.body.preheader ]
  %cmp1 = icmp sgt i32 %i.09, %z, !dbg !19
  br i1 %cmp1, label %if.then2, label %for.inc, !dbg !21

if.then2:                                         ; preds = %for.body
  %0 = load i32, i32* @g, align 4, !dbg !22, !tbaa !9
  %inc = add nsw i32 %0, 1, !dbg !22
  store i32 %inc, i32* @g, align 4, !dbg !22, !tbaa !9
  br label %for.inc, !dbg !23

for.inc:                                          ; preds = %for.body, %if.then2
  %inc4 = add nuw nsw i32 %i.09, 1, !dbg !24
  %exitcond = icmp ne i32 %inc4, %y, !dbg !13
  br i1 %exitcond, label %for.body, label %for.end.loopexit, !dbg !17

for.end.loopexit:                                 ; preds = %for.inc
  br label %for.end, !dbg !26

for.end:                                          ; preds = %for.end.loopexit, %entry
  ret void, !dbg !26
}

where

!21 = !DILocation(line: 11, column: 9, scope: !15)
!22 = !DILocation(line: 12, column: 8, scope: !20)
!23 = !DILocation(line: 12, column: 7, scope: !20)
!24 = !DILocation(line: 10, column: 20, scope: !25)

And below is after GVN:

@g = external local_unnamed_addr global i32, align 4

define void @foo(i32 %x, i32 %y, i32 %z) local_unnamed_addr !dbg !4 {
entry:
  %not.tobool = icmp eq i32 %x, 0, !dbg !8
  %.sink = zext i1 %not.tobool to i32, !dbg !8
  store i32 %.sink, i32* @g, align 4, !tbaa !9
  %cmp8 = icmp sgt i32 %y, 0, !dbg !13
  br i1 %cmp8, label %for.body.preheader, label %for.end, !dbg !17

for.body.preheader:                               ; preds = %entry
  br label %for.body, !dbg !19

for.body:                                         ; preds = %for.inc, %for.body.preheader
  %0 = phi i32 [ %1, %for.inc ], [ %.sink, %for.body.preheader ], !dbg !21
  %i.09 = phi i32 [ %inc4, %for.inc ], [ 0, %for.body.preheader ]
  %cmp1 = icmp sgt i32 %i.09, %z, !dbg !19
  br i1 %cmp1, label %if.then2, label %for.inc, !dbg !22

if.then2:                                         ; preds = %for.body
  %inc = add nsw i32 %0, 1, !dbg !21
  store i32 %inc, i32* @g, align 4, !dbg !21, !tbaa !9
  br label %for.inc, !dbg !23

for.inc:                                          ; preds = %if.then2, %for.body
  %1 = phi i32 [ %inc, %if.then2 ], [ %0, %for.body ]
  %inc4 = add nuw nsw i32 %i.09, 1, !dbg !24
  %exitcond = icmp ne i32 %inc4, %y, !dbg !13
  br i1 %exitcond, label %for.body, label %for.end.loopexit, !dbg !17

for.end.loopexit:                                 ; preds = %for.inc
  br label %for.end, !dbg !26

for.end:                                          ; preds = %for.end.loopexit, %entry
  ret void, !dbg !26
}

As you see, GVN removes the load in if.then2 block and creates a phi instruction in for.body for it. The problem is that DebugLoc of remove load instruction is propagated to the newly created phi instruction, which is wrong. rL288903 cannot handle this case because ValuesPerBlock.size() is not 1 in this example when the load is removed.

Diff Detail

Event Timeline

twoh created this revision.Jan 28 2017, 3:50 PM
twoh edited the summary of this revision. (Show Details)Jan 28 2017, 3:51 PM
twoh edited the summary of this revision. (Show Details)
davide added a subscriber: davide.Jan 28 2017, 3:54 PM
davide added inline comments.
test/Transforms/GVN/debugloc.ll
2–7

Can you please add the same test to NewGVN (and XFAIL for now)

twoh updated this revision to Diff 86199.Jan 28 2017, 10:33 PM

Improve the test and added to NewGVN as well (with XFAIL).

Harbormaster completed remote builds in B3386: Diff 86199.Jan 28 2017, 10:33 PM
wolfgangp edited edge metadata.Jan 31 2017, 11:30 AM

This looks good to me, but I'd like Andrea to take a look as well.

andreadb accepted this revision.Jan 31 2017, 12:38 PM

This patch looks good to me.

We shouldn't propagate the debugloc from the load to the newly created phi node. Otherwise, we risk to introduce an incorrect stepping. When leaving the SSA form, all the phi nodes are replaced by COPY instructions. Luckily, most copies become redundant after regalloc; however, some copies may survive register allocation.
In the example, if the COPY obtained from %0 = phi i32 [ %1, %for.inc ], [ %.sink, %for.body.preheader ], !dbg !21 survives regalloc, then we would have an incorrect stepping.

Thanks for fixing it.

This revision is now accepted and ready to land.Jan 31 2017, 12:38 PM
twoh closed this revision.Jan 31 2017, 1:08 PM

Revision Contents

PathSize
lib/
Transforms/
Scalar/
4 lines
test/
Transforms/
GVN/
77 lines
NewGVN/
78 lines

Diff 86199

lib/Transforms/Scalar/GVN.cpp

Show First 20 Lines • Show All 1,708 Lines • ▼ Show 20 Lines if (UnavailableBlocks.empty()) {
LI->replaceAllUsesWith(V); LI->replaceAllUsesWith(V);
if (isa<PHINode>(V)) if (isa<PHINode>(V))
V->takeName(LI); V->takeName(LI);
if (Instruction *I = dyn_cast<Instruction>(V)) if (Instruction *I = dyn_cast<Instruction>(V))
// If instruction I has debug info, then we should not update it. // If instruction I has debug info, then we should not update it.
// Also, if I has a null DebugLoc, then it is still potentially incorrect // Also, if I has a null DebugLoc, then it is still potentially incorrect
// to propagate LI's DebugLoc because LI may not post-dominate I. // to propagate LI's DebugLoc because LI may not post-dominate I.
if (LI->getDebugLoc() && ValuesPerBlock.size() != 1) if (LI->getDebugLoc() && LI->getParent() == I->getParent())
I->setDebugLoc(LI->getDebugLoc()); I->setDebugLoc(LI->getDebugLoc());
if (V->getType()->getScalarType()->isPointerTy()) if (V->getType()->getScalarType()->isPointerTy())
MD->invalidateCachedPointerInfo(V); MD->invalidateCachedPointerInfo(V);
markInstructionForDeletion(LI); markInstructionForDeletion(LI);
++NumGVNLoad; ++NumGVNLoad;
reportLoadElim(LI, V, ORE); reportLoadElim(LI, V, ORE);
return true; return true;
} }
▲ Show 20 Lines • Show All 65 Lines • ▼ Show 20 Lines
static void patchReplacementInstruction(Instruction *I, Value *Repl) { static void patchReplacementInstruction(Instruction *I, Value *Repl) {
auto *ReplInst = dyn_cast<Instruction>(Repl); auto *ReplInst = dyn_cast<Instruction>(Repl);
if (!ReplInst) if (!ReplInst)
return; return;
// Patch the replacement so that it is not more restrictive than the value // Patch the replacement so that it is not more restrictive than the value
// being replaced. // being replaced.
// Note that if 'I' is a load being replaced by some operation, // Note that if 'I' is a load being replaced by some operation,
// for example, by an arithmetic operation, then andIRFlags() // for example, by an arithmetic operation, then andIRFlags()
// would just erase all math flags from the original arithmetic // would just erase all math flags from the original arithmetic
// operation, which is clearly not wanted and not needed. // operation, which is clearly not wanted and not needed.
if (!isa<LoadInst>(I)) if (!isa<LoadInst>(I))
ReplInst->andIRFlags(I); ReplInst->andIRFlags(I);
// FIXME: If both the original and replacement value are part of the // FIXME: If both the original and replacement value are part of the
// same control-flow region (meaning that the execution of one // same control-flow region (meaning that the execution of one
▲ Show 20 Lines • Show All 1,003 Lines • Show Last 20 Lines

test/Transforms/GVN/debugloc.ll

  • This file was added.
; RUN: opt < %s -gvn -S | FileCheck %s
; CHECK: {{^}}for.body:
; CHECK-NEXT: [[VREG1:%[^ ]+]] = phi{{.*}}[[VREG2:%[^ ]+]],{{.*}}%.sink,
; CHECK-NOT: !dbg
; CHECK-SAME: {{$}}
; CHECK: {{^}}for.inc:
; CHECK-NEXT: [[VREG2]] = phi{{.*}}%inc,{{.*}}[[VREG1]]
davideUnsubmitted
Not Done
ReplyInline Actions

Can you please add the same test to NewGVN (and XFAIL for now)

davide: Can you please add the same test to NewGVN (and XFAIL for now)
target triple = "x86_64-unknown-linux-gnu"
@g = external local_unnamed_addr global i32, align 4
; Function Attrs: nounwind uwtable
define void @foo(i32 %x, i32 %y, i32 %z) local_unnamed_addr #0 !dbg !4 {
entry:
%not.tobool = icmp eq i32 %x, 0, !dbg !8
%.sink = zext i1 %not.tobool to i32, !dbg !8
store i32 %.sink, i32* @g, align 4, !tbaa !9
%cmp8 = icmp sgt i32 %y, 0, !dbg !13
br i1 %cmp8, label %for.body.preheader, label %for.end, !dbg !17
for.body.preheader: ; preds = %entry
br label %for.body, !dbg !19
for.body: ; preds = %for.body.preheader, %for.inc
%i.09 = phi i32 [ %inc4, %for.inc ], [ 0, %for.body.preheader ]
%cmp1 = icmp sgt i32 %i.09, %z, !dbg !19
br i1 %cmp1, label %if.then2, label %for.inc, !dbg !21
if.then2: ; preds = %for.body
%0 = load i32, i32* @g, align 4, !dbg !22, !tbaa !9
%inc = add nsw i32 %0, 1, !dbg !22
store i32 %inc, i32* @g, align 4, !dbg !22, !tbaa !9
br label %for.inc, !dbg !23
for.inc: ; preds = %for.body, %if.then2
%inc4 = add nuw nsw i32 %i.09, 1, !dbg !24
%exitcond = icmp ne i32 %inc4, %y, !dbg !13
br i1 %exitcond, label %for.body, label %for.end.loopexit, !dbg !17
for.end.loopexit: ; preds = %for.inc
br label %for.end, !dbg !26
for.end: ; preds = %for.end.loopexit, %entry
ret void, !dbg !26
}
!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1)
!1 = !DIFile(filename: "foo.c", directory: "b/")
!2 = !{i32 2, !"Dwarf Version", i32 4}
!3 = !{i32 2, !"Debug Info Version", i32 3}
!4 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 3, type: !5, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
!5 = !DISubroutineType(types: !6)
!6 = !{null, !7, !7, !7}
!7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
!8 = !DILocation(line: 4, column: 7, scope: !4)
!9 = !{!10, !10, i64 0}
!10 = !{!"int", !11, i64 0}
!11 = !{!"omnipotent char", !12, i64 0}
!12 = !{!"Simple C/C++ TBAA"}
!13 = !DILocation(line: 10, column: 13, scope: !14)
!14 = !DILexicalBlockFile(scope: !15, file: !1, discriminator: 1)
!15 = distinct !DILexicalBlock(scope: !16, file: !1, line: 10, column: 3)
!16 = distinct !DILexicalBlock(scope: !4, file: !1, line: 10, column: 3)
!17 = !DILocation(line: 10, column: 3, scope: !18)
!18 = !DILexicalBlockFile(scope: !16, file: !1, discriminator: 1)
!19 = !DILocation(line: 11, column: 11, scope: !20)
!20 = distinct !DILexicalBlock(scope: !15, file: !1, line: 11, column: 9)
!21 = !DILocation(line: 11, column: 9, scope: !15)
!22 = !DILocation(line: 12, column: 8, scope: !20)
!23 = !DILocation(line: 12, column: 7, scope: !20)
!24 = !DILocation(line: 10, column: 20, scope: !25)
!25 = !DILexicalBlockFile(scope: !15, file: !1, discriminator: 2)
!26 = !DILocation(line: 13, column: 1, scope: !4)
!llvm.dbg.cu = !{!0}
!llvm.module.flags = !{!2, !3}

test/Transforms/NewGVN/debugloc.ll

  • This file was added.
; XFAIL: *
; RUN: opt < %s -newgvn -S | FileCheck %s
; CHECK: {{^}}for.body:
; CHECK-NEXT: [[VREG1:%[^ ]+]] = phi{{.*}}[[VREG2:%[^ ]+]],{{.*}}%.sink,
; CHECK-NOT: !dbg
; CHECK-SAME: {{$}}
; CHECK: {{^}}for.inc:
; CHECK-NEXT: [[VREG2]] = phi{{.*}}%inc,{{.*}}[[VREG1]]
target triple = "x86_64-unknown-linux-gnu"
@g = external local_unnamed_addr global i32, align 4
; Function Attrs: nounwind uwtable
define void @foo(i32 %x, i32 %y, i32 %z) local_unnamed_addr #0 !dbg !4 {
entry:
%not.tobool = icmp eq i32 %x, 0, !dbg !8
%.sink = zext i1 %not.tobool to i32, !dbg !8
store i32 %.sink, i32* @g, align 4, !tbaa !9
%cmp8 = icmp sgt i32 %y, 0, !dbg !13
br i1 %cmp8, label %for.body.preheader, label %for.end, !dbg !17
for.body.preheader: ; preds = %entry
br label %for.body, !dbg !19
for.body: ; preds = %for.body.preheader, %for.inc
%i.09 = phi i32 [ %inc4, %for.inc ], [ 0, %for.body.preheader ]
%cmp1 = icmp sgt i32 %i.09, %z, !dbg !19
br i1 %cmp1, label %if.then2, label %for.inc, !dbg !21
if.then2: ; preds = %for.body
%0 = load i32, i32* @g, align 4, !dbg !22, !tbaa !9
%inc = add nsw i32 %0, 1, !dbg !22
store i32 %inc, i32* @g, align 4, !dbg !22, !tbaa !9
br label %for.inc, !dbg !23
for.inc: ; preds = %for.body, %if.then2
%inc4 = add nuw nsw i32 %i.09, 1, !dbg !24
%exitcond = icmp ne i32 %inc4, %y, !dbg !13
br i1 %exitcond, label %for.body, label %for.end.loopexit, !dbg !17
for.end.loopexit: ; preds = %for.inc
br label %for.end, !dbg !26
for.end: ; preds = %for.end.loopexit, %entry
ret void, !dbg !26
}
!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1)
!1 = !DIFile(filename: "foo.c", directory: "b/")
!2 = !{i32 2, !"Dwarf Version", i32 4}
!3 = !{i32 2, !"Debug Info Version", i32 3}
!4 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 3, type: !5, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
!5 = !DISubroutineType(types: !6)
!6 = !{null, !7, !7, !7}
!7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
!8 = !DILocation(line: 4, column: 7, scope: !4)
!9 = !{!10, !10, i64 0}
!10 = !{!"int", !11, i64 0}
!11 = !{!"omnipotent char", !12, i64 0}
!12 = !{!"Simple C/C++ TBAA"}
!13 = !DILocation(line: 10, column: 13, scope: !14)
!14 = !DILexicalBlockFile(scope: !15, file: !1, discriminator: 1)
!15 = distinct !DILexicalBlock(scope: !16, file: !1, line: 10, column: 3)
!16 = distinct !DILexicalBlock(scope: !4, file: !1, line: 10, column: 3)
!17 = !DILocation(line: 10, column: 3, scope: !18)
!18 = !DILexicalBlockFile(scope: !16, file: !1, discriminator: 1)
!19 = !DILocation(line: 11, column: 11, scope: !20)
!20 = distinct !DILexicalBlock(scope: !15, file: !1, line: 11, column: 9)
!21 = !DILocation(line: 11, column: 9, scope: !15)
!22 = !DILocation(line: 12, column: 8, scope: !20)
!23 = !DILocation(line: 12, column: 7, scope: !20)
!24 = !DILocation(line: 10, column: 20, scope: !25)
!25 = !DILexicalBlockFile(scope: !15, file: !1, discriminator: 2)
!26 = !DILocation(line: 13, column: 1, scope: !4)
!llvm.dbg.cu = !{!0}
!llvm.module.flags = !{!2, !3}