Improve merging of debug locations (fixes PR 36410)

[uweigand]

Summary

PR 36410 describes a problem where as a result of hoisting common code from "then" and "else" branches of a condition to before the "if", we get a llvm.dbg.value intrinsic with an invalid location. For those intrinsics, the scope indicated in the !dbg location must be identical with the scope of the variable tracked by the intrinsics, or else the module verifier will abort. This constraint can be violated by the current algorithm of getMergedLocation.

To fix this problem, this patch re-implements the algorithm used in getMergedLocation as follows (for the case of merging call instructions):

• First, we determine a merged scope. This is closest common scope of the two locations. If this does not exist, use the current function as scope. Note that in the special case of debug intrinsics for the same variable, the scopes must be identical, and therefore this algorithm will always return the same scope as well.

• If both original locations were inline, we need to return an inline location as well. To determine the inlined-at location, we use the closest common location in the inlined-at chain of both locations. If none exist, use a compiler-generated location in the current function.

This should handle the following cases:

• Same location (inlined or non-inlined): return that location
• Locations in the same scope (non-inlined): return a compiler-generated location in that scope
• Locations in different but nested scopes (non-inlined): return a compiler-generated location in the outer scope
• Locations in the same scope or nested scopes, inlined directly at the same location: return the outer scope, using the original (shared) inlined-at chain
• Locations in the same scope or nested scopes, inlined indirectly at the same location: return the outer scope, using the longest common part of the two original inlined-at chains
• Locations in the same scope or nested scopes, inlined at different locations of the same function: return the outer scope, using an inlined-at pointing to a compiler-generated location in that function.

[aprantl]

This looks really good; let's think through the isa<DbgInfoIntrinsic> case:

This function only gets invoked when the two dbg.value calls are identical, which means the two DIScopes also must be identical (we might want to make this into an assertion). The inlinedAt, however may be different, and the ideal resolution of that case would be to keep both dbg.value instrinsics around. But I'd also be happy with pointing this deficiency out in a comment for now.

[uweigand]

I'm not sure I understand why we should keep two debug intrinsics around in just this case, and not in other cases where the original IR has differing debug intrinsics (e.g. for different variables)?

But in any case, keeping multiple debug intrinsics would need to be done in HoistThenElseCodeToIf, not here in getMergedLocation. So I think this should probably be a separate discussion independent of this patch ...

[aprantl]

I'm not sure I understand why we should keep two debug intrinsics around in just this case, and not in other cases where the original IR has differing debug intrinsics (e.g. for different variables)?

My assumption was that if the variables were different, this function would not have been called in the first place, since the two instructions were already different. That depends on how the caller of getMergedLocation is implemented of course.

I'm happy with this variant. Perhaps also let dblaikie sign off, since he mentioned in the PR that we also wanted to give this a closer look.

[dblaikie]

Have you considered a test case where there's a common scope within an inlinedAt location?

SP1 <- S1 <- IA1 <- L1
         \-- IA2 <- L2

I think it's reasonable for S1 to be the scope of the merged location - as much as it would be if IA1 and IA2 were not present. (SP = Subprogram, S = Scope, IA = InlinedAt, L = Location).

I /think/ this should be achievable with a single walk, rather than two separate walks (one up scopes, one up inlinedAt's), perhaps?

[uweigand]

In D43687#1020083, @dblaikie wrote:

Have you considered a test case where there's a common scope within an inlinedAt location?

SP1 <- S1 <- IA1 <- L1
         \-- IA2 <- L2

I think it's reasonable for S1 to be the scope of the merged location - as much as it would be if IA1 and IA2 were not present. (SP = Subprogram, S = Scope, IA = InlinedAt, L = Location).

Well, there's variants of that scenario: L1 and L2 might already have the same scope, or they might have different scopes.

If L1 and L2 already have the same scope, this must remain the scope of the merged location, or else we break debug intrinsics again. If L1 and L2 have different scopes, my current code just uses LocA->getInlinedAtScope() as simple fallback scope, which actually happens to agree with S in your example. I guess this could still be refined for more complex cases later, if necessary ...

I /think/ this should be achievable with a single walk, rather than two separate walks (one up scopes, one up inlinedAt's), perhaps?

Well, if L1 and L2 have the same scope, we need to keep it (see above). But then if their inlined-at locations are different, we still need to come up with a merged inlined-at location without changing that common scope. That's why I have two loops.

[aprantl]

Ping! David, have all your concerns been addressed, or do we need to iterate some more on this?

[aprantl]

I just found out that this patch causes an assertion when compiling projects/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc:
Assertion failed: (isa<X>(Val) && "cast<Ty>() argument of incompatible type!"), function cast, file ../include/llvm/Support/Casting.h, line 255.

Let me know if you need more detailed instructions to reproduce.

[dblaikie]

Yeah, I still need to look more closely at this - my hunch/feeling is that,
while/if this approach is necessary for dbg.value intrinsics, it'd still
produce wrong or at least suboptimal locations in general. :/ (& I'm not
even sure it's the best thing for the dbg.values either... not sure what
should be done about them - perhaps they shouldn't be merged, instead
duplicated & keep their respective locations)

[dblaikie]

What does the resulting DWARF look like when the scope is preserved but the InlinedAt is commoned at a higher level? I feel like this would produce pretty broken debug info, right? It'd make it look like there was a call from a place that doesn't have such a call? (though I suppose that's what happens without inlining too)

(I wonder if it's the best thing to drop the location for the non-calls, or whether we'll eventually want to do this merging logic even to non-calls, to make for longer valid variable locations for example)

I guess this produces the same sort of line table/stacktrace behavior as if the inlined call had not been inlined, but merely commoned - except we're going to get some fictitious calls (if part of the two inlinings is commoned and part is not - now there will be, virtually, 3 calls/inlined subroutines, I think)

[uweigand]

In D43687#1031776, @aprantl wrote:

I just found out that this patch causes an assertion when compiling projects/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc:
Assertion failed: (isa<X>(Val) && "cast<Ty>() argument of incompatible type!"), function cast, file ../include/llvm/Support/Casting.h, line 255.

Let me know if you need more detailed instructions to reproduce.

Huh. Not only am I not seeing this, but I have a hard time even imagining how this change could possibly have that effect ...

What exactly are you doing to reproduce this?

[uweigand]

In D43687#1031791, @dblaikie wrote:

Yeah, I still need to look more closely at this - my hunch/feeling is that,
while/if this approach is necessary for dbg.value intrinsics, it'd still
produce wrong or at least suboptimal locations in general. :/ (& I'm not
even sure it's the best thing for the dbg.values either... not sure what
should be done about them - perhaps they shouldn't be merged, instead
duplicated & keep their respective locations)

OK. Maybe it is indeed a better choice to *not* merge dbg.value intrinsics, but just move over both sets from both sides of the "if" unchanged. In fact, if you have dbg.value intrinsics for *different* variables, they are currently just deleted -- moving them over should keep the (correct) information that *both* those variables now have the specfied value at the new location ...

I'll try and come up with a patch along those lines. If this approach works, we can abandon the patch in this Phabricator, and are free to instead implement whatever way to merge locations that seems best, without being constrained by the dbg.value requirements.

[aprantl]

What exactly are you doing to reproduce this?

I'm running the crash reproducer through delta now...

OK. Maybe it is indeed a better choice to *not* merge dbg.value intrinsics, but just move over both sets from both sides of the "if" unchanged. In fact, if you have dbg.value intrinsics for *different* variables, they are currently just deleted -- moving them over should keep the (correct) information that *both* those variables now have the specfied value at the new location ...

Keeping both intrinsics is always a safe choice.

[uweigand]

In D43687#1032868, @aprantl wrote:

OK. Maybe it is indeed a better choice to *not* merge dbg.value intrinsics, but just move over both sets from both sides of the "if" unchanged. In fact, if you have dbg.value intrinsics for *different* variables, they are currently just deleted -- moving them over should keep the (correct) information that *both* those variables now have the specfied value at the new location ...

Keeping both intrinsics is always a safe choice.

This is now here: https://reviews.llvm.org/D44312

[aprantl]

Testcase for the assertion:

typedef long uptr;
template <class> class A;
template <class> class allocator;
template <class, class, class> class __tree {
public:
  void __root() noexcept;
  __tree(int);
  ~__tree();
  void clear() noexcept;
};
template <class _Tp, class _Compare, class _Allocator>
__tree<_Tp, _Compare, _Allocator>::~__tree() {
  __root();
}
template <class _Tp, class _Compare, class _Allocator>
void __tree<_Tp, _Compare, _Allocator>::clear() noexcept {
  __root();
}
template <class _Key, class _Compare = _Key, class _Allocator = allocator<_Key>>
class set {
  typedef _Key value_type;
  typedef _Compare value_compare;
  typedef _Allocator allocator_type;
  typedef __tree<value_type, value_compare, allocator_type> __base;
  __base __tree_;

public:
  set() : __tree_(value_compare()) {}
  void clear() { __tree_.clear(); }
};
template <class> void RemoveEdges() {
  set<uptr> s;
  for (int it; it; it++)
    s.clear();
}
void BVGraph_RemoveEdges_TestTestBody() { RemoveEdges<A<char>>(); }

Test script:

$R/clang "-cc1" \
    "-triple" \
    "i386-apple-macosx10.9.0" \
    "-emit-obj" \
    "-disable-free" \
    "-main-file-name" \
    "sanitizer_bvgraph_test.cc" \
    "-mrelocation-model" \
    "pic" \
    "-pic-level" \
    "2" \
    "-mthread-model" \
    "posix" \
    "-mdisable-fp-elim" \
    "-fno-strict-return" \
    "-masm-verbose" \
    "-munwind-tables" \
    "-faligned-alloc-unavailable" \
    "-target-cpu" \
    "yonah" \
    "-dwarf-column-info" \
    "-debug-info-kind=line-tables-only" \
    "-dwarf-version=2" \
    "-debugger-tuning=lldb" \
    "-target-linker-version" \
    "299.9" \
    "-D" \
    "GTEST_NO_LLVM_RAW_OSTREAM=1" \
    "-D" \
    "GTEST_HAS_RTTI=0" \
    "-stdlib=libc++" \
    "-O2" \
    "-std=c++11" \
    "-fdeprecated-macro" \
    "-ferror-limit" \
    "19" \
    "-fmessage-length" \
    "0" \
    "-stack-protector" \
    "1" \
    "-fblocks" \
    "-fencode-extended-block-signature" \
    "-fno-rtti" \
    "-fobjc-runtime=macosx-fragile-10.9.0" \
    "-fobjc-subscripting-legacy-runtime" \
    "-fcxx-exceptions" \
    "-fexceptions" \
    "-fmax-type-align=16" \
    "-fdiagnostics-show-option" \
    "-vectorize-loops" \
    "-vectorize-slp" \
    "-x" \
    "c++" \
    "test.cpp" 2>&1 | grep "cast<Ty>() argument of incompatible type!"

[aprantl]

Interesting that it is -gline-tables-only.

[uweigand]

Ah, I see. Looks like the problem is that the DIScope -> getScope() loop can actually leave the function scope and go up all the way to file scope. This is not a good idea here. I think this needs to be restricted to DILocalScope instead. I'll update the patch.

[uweigand]

Fix the local scope bug.

[uweigand]

The original bug in PR 36410 is now fixed in r327622, so I won't pursue this attempt any further.

lib/IR/DebugInfoMetadata.cpp

if (!LocA || !LocB)
     return nullptr;
 
   if (LocA == LocB || !LocA->canDiscriminate(*LocB))
     return LocA;
 
   if (!dyn_cast_or_null<CallInst>(ForInst))
     return nullptr;
 
+  // Find closest common scope for LocA and LocB.
+  DILocalScope *CommonScope = nullptr;
+  SmallPtrSet<DILocalScope *, 5> ScopesA;
+  for (DILocalScope *S = LocA->getScope(); S;
+       S = dyn_cast_or_null<DILocalScope>(S->getScope().resolve()))
+    ScopesA.insert(S);
+  for (DILocalScope *S = LocB->getScope(); S;
+       S = dyn_cast_or_null<DILocalScope>(S->getScope().resolve()))
+    if (ScopesA.count(S)) {
+      CommonScope = S;
+      break;
+    }
+
+  // If no common scope exists, make up a new compiler-generated location.
+  // At this point the inlinedAt field will be meaningless as well.
+  if (!CommonScope)
+    return DILocation::get(LocA->getContext(),
+                           0, 0, LocA->getInlinedAtScope());
+
+  // If either LocA or LocB is not inlined, the merged location does not
+  // need to be inlined either.
+  if (LocA->getInlinedAt() == nullptr || LocB->getInlinedAt() == nullptr)
+    return DILocation::get(LocA->getContext(), 0, 0, CommonScope);
+
+  // Otherwise find the closest common inlined-at location for LocA and LocB.
+  DILocation *CommonInlinedAt = nullptr;
   SmallPtrSet<DILocation *, 5> InlinedLocationsA;
   for (DILocation *L = LocA->getInlinedAt(); L; L = L->getInlinedAt())
     InlinedLocationsA.insert(L);
-  const DILocation *Result = LocB;
-  for (DILocation *L = LocB->getInlinedAt(); L; L = L->getInlinedAt()) {
-    Result = L;
-    if (InlinedLocationsA.count(L))
+  for (DILocation *L = LocB->getInlinedAt(); L; L = L->getInlinedAt())
+    if (InlinedLocationsA.count(L)) {
+      CommonInlinedAt = L;
       break;
     }
-  return DILocation::get(Result->getContext(), 0, 0, Result->getScope(),
-                         Result->getInlinedAt());
+
+  // If no common inlined-at location exists, mark as inlined at a
+  // compiler-generated location in the current function.
+  if (!CommonInlinedAt)
+    CommonInlinedAt = DILocation::get(LocA->getContext(),
+                                      0, 0, LocA->getInlinedAtScope());
+
+  return DILocation::get(LocA->getContext(),
+                         0, 0, CommonScope, CommonInlinedAt);
 }
 
 DINode::DIFlags DINode::getFlag(StringRef Flag) {
   return StringSwitch<DIFlags>(Flag)
 #define HANDLE_DI_FLAG(ID, NAME) .Case("DIFlag" #NAME, Flag##NAME)
 #include "llvm/IR/DebugInfoFlags.def"
       .Default(DINode::FlagZero);
 }

test/Transforms/SimplifyCFG/hoist-dbgvalue-inlined.ll

+; RUN: opt -simplifycfg -S < %s | FileCheck %s
+; Verify that we don't crash due an invalid !dbg location on the hoisted llvm.dbg.value
+
+define i64 @caller(i64* %ptr, i64 %flag) !dbg !10 {
+; CHECK: llvm.dbg.value
+init:
+  %v9 = icmp eq i64 %flag, 0
+  br i1 %v9, label %a, label %b
+
+a:                                              ; preds = %init
+  %vala = load i64, i64* %ptr, align 8
+  call void @llvm.dbg.value(metadata i64 %vala, metadata !8, metadata !DIExpression()), !dbg !12
+  br label %test.exit
+
+b:                                              ; preds = %init
+  %valb = load i64, i64* %ptr, align 8
+  call void @llvm.dbg.value(metadata i64 %valb, metadata !8, metadata !DIExpression()), !dbg !13
+  %valbmasked = and i64 %valb, 1
+  br label %test.exit
+
+test.exit:                                      ; preds = %a, %b
+  %retv = phi i64 [ %vala, %a ], [ %valbmasked, %b ]
+  ret i64 %retv
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+attributes #0 = { nounwind readnone speculatable }
+
+!llvm.module.flags = !{!0}
+!llvm.dbg.cu = !{!1}
+
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !2, isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !3)
+!2 = !DIFile(filename: "optbug", directory: "")
+!3 = !{}
+!4 = distinct !DISubprogram(name: "callee", scope: !2, file: !2, line: 1, type: !5, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !1, variables: !7)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null}
+!7 = !{!8}
+!8 = !DILocalVariable(name: "var", scope: !4, file: !2, type: !9)
+!9 = !DIBasicType(name: "var_t", size: 64, encoding: DW_ATE_unsigned)
+!10 = distinct !DISubprogram(name: "caller", scope: !2, file: !2, line: 5, type: !5, isLocal: false, isDefinition: true, scopeLine: 5, isOptimized: false, unit: !1, variables: !3)
+!11 = distinct !DILocation(line: 6, scope: !10)
+!12 = !DILocation(line: 2, scope: !4, inlinedAt: !11)
+!13 = !DILocation(line: 3, scope: !4, inlinedAt: !11)

unittests/IR/MetadataTest.cpp

 TEST_F(DILocationTest, cloneTemporary) {
   MDNode *N = MDNode::get(Context, None);
   auto L = DILocation::getTemporary(Context, 2, 7, N);
   EXPECT_TRUE(L->isTemporary());
   auto L2 = L->clone();
   EXPECT_TRUE(L2->isTemporary());
 }
 
+TEST_F(DILocationTest, getMergedLocation) {
+  FunctionType *FT = FunctionType::get(Type::getVoidTy(Context), false);
+  auto *F = Function::Create(FT, GlobalValue::ExternalLinkage);
+  const CallInst *Call = CallInst::Create(F, None);
+
+  // Merging two identical locations should result in the same location.
+  {
+    DISubprogram *Prg = getSubprogram();
+    DILocation *L1 = DILocation::get(Context, 2, 7, Prg);
+    DILocation *L2 = DILocation::get(Context, 2, 7, Prg);
+    const DILocation *L = DILocation::getMergedLocation(L1, L2, nullptr);
+    EXPECT_EQ(2u, L->getLine());
+    EXPECT_EQ(7u, L->getColumn());
+    EXPECT_EQ(Prg, L->getScope());
+  }
+  // If the two locations are incompatible, there should be a null result.
+  {
+    DISubprogram *Prg = getSubprogram();
+    DILocation *L1 = DILocation::get(Context, 2, 7, Prg);
+    DILocation *L2 = DILocation::get(Context, 3, 7, Prg);
+    const DILocation *L = DILocation::getMergedLocation(L1, L2, nullptr);
+    EXPECT_EQ(nullptr, L);
+  }
+  // Unless we are merging locations for a call instruction.  If the
+  // scopes agree, the result should be a compiler-generated location
+  // in that same scope.
+  {
+    DISubprogram *Prg = getSubprogram();
+    DILocation *L1 = DILocation::get(Context, 2, 7, Prg);
+    DILocation *L2 = DILocation::get(Context, 3, 7, Prg);
+    const DILocation *L = DILocation::getMergedLocation(L1, L2, Call);
+    EXPECT_EQ(0u, L->getLine());
+    EXPECT_EQ(Prg, L->getScope());
+  }
+  // Likewise if the one scope is a sub-scope of the other.
+  {
+    DISubprogram *Prg = getSubprogram();
+    DILexicalBlock *B = DILexicalBlock::get(Context, Prg, getFile(), 5, 7);
+    DILocation *L1 = DILocation::get(Context, 2, 7, Prg);
+    DILocation *L2 = DILocation::get(Context, 3, 7, B);
+    const DILocation *L = DILocation::getMergedLocation(L1, L2, Call);
+    EXPECT_EQ(0u, L->getLine());
+    EXPECT_EQ(Prg, L->getScope());
+  }
+  // Even if the calls were inlined (possibly into different places),
+  // if they originate from the same scope, the result should also be
+  // a compiler-generated location in that same scope.
+  {
+    DISubprogram *IPrg = getSubprogram();
+    DILocation *I1 = DILocation::get(Context, 10, 7, IPrg);
+    DILocation *I2 = DILocation::get(Context, 11, 7, IPrg);
+    DISubprogram *Prg = getSubprogram();
+    DILocation *L1 = DILocation::get(Context, 2, 7, Prg, I1);
+    DILocation *L2 = DILocation::get(Context, 3, 7, Prg, I2);
+    const DILocation *L = DILocation::getMergedLocation(L1, L2, Call);
+    EXPECT_EQ(0u, L->getLine());
+    EXPECT_EQ(Prg, L->getScope());
+    EXPECT_NE(nullptr, L->getInlinedAt());
+  }
+  // Likewise if the one scope is a sub-scope of the other.
+  {
+    DISubprogram *IPrg = getSubprogram();
+    DILocation *I1 = DILocation::get(Context, 10, 7, IPrg);
+    DILocation *I2 = DILocation::get(Context, 11, 7, IPrg);
+    DISubprogram *Prg = getSubprogram();
+    DILexicalBlock *B = DILexicalBlock::get(Context, Prg, getFile(), 5, 7);
+    DILocation *L1 = DILocation::get(Context, 2, 7, Prg, I1);
+    DILocation *L2 = DILocation::get(Context, 3, 7, B, I2);
+    const DILocation *L = DILocation::getMergedLocation(L1, L2, Call);
+    EXPECT_EQ(0u, L->getLine());
+    EXPECT_EQ(Prg, L->getScope());
+    EXPECT_NE(nullptr, L->getInlinedAt());
+  }
+}
+
 typedef MetadataTest GenericDINodeTest;
 
 TEST_F(GenericDINodeTest, get) {
   StringRef Header = "header";
   auto *Empty = MDNode::get(Context, None);
   Metadata *Ops1[] = {Empty};
   auto *N = GenericDINode::get(Context, 15, Header, Ops1);
   EXPECT_EQ(15u, N->getTag());