[StructurizeCFG][DebugInfo] Maintain DILocations in the branches created by StructurizeCFG

[jmmartinez]

Summary

Make StructurizeCFG preserve the debug locations of the branch instructions it introduces.

[jmmartinez]

Updated todo comments before the weekend

[jmmartinez]

Small update to submit for review.

Check the following recordings to see the differences while debugging

• debugging after the patch, on a gpu, https://asciinema.org/a/8mZ7AWPtXccaRRRiMNHmE0VDP
• debugging before the patch, on a gpu, https://asciinema.org/a/oFX7YDmWx9xyAlQMYBM5Mabov
• debugging on a cpu (not affected by this patch), https://asciinema.org/a/3pib6TyoLBYSt1Zumh0edTAnE

Notice how the behaviour after the patch is applied matches what happens for the cpu case.

[jmmartinez]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

956

Fix this: remove empty line

[arsenm]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

859

Why can't you just directly set the debug info when the terminator is created?

[jmmartinez]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

859

That was my original approach, however I struggled to make it always work.

For example, in the function changeExit when the branch is created and appended to the basic-block, sometimes there is the old terminator that's going to be replaced, but sometims the basic-block is empty (when it's a new flow block created by getNextFlow).

In the end, I picked the current strategy since it was the simpler one.

[jmmartinez]

llvm/test/Transforms/StructurizeCFG/structurizecfg-debug-loc.ll

41

Remove this comment. This is the good behaviour.

71

Remove this one too. Again, this gives the good behaviour.

[jmmartinez]

Removed useless TODO and empty line

[arsenm]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

553

I think the current guidance is DebugLocs should be handled by const reference

[jmmartinez]

• Handle DebugLoc by const-ref instead of by copy

[jmmartinez]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

553

I changed to use a const-ref in here and in the loop in setTerminatorDebugLoc . Indeed, internally it uses a TrackingMDRef so it'd better to avoid constructing a new one. Thanks !

[arsenm]

LGTM (although I would be a bit happier if this was setting something at the creation point)

[jmmartinez]

Set DebugLoc at BranchInst creation

[jmmartinez]

In D135967#3888601, @arsenm wrote:

LGTM (although I would be a bit happier if this was setting something at the creation point)

I found a way to do it (although I wasn't able to get rid of the map).

[arsenm]

LGTM

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

 using PhiMap = MapVector<PHINode *, BBValueVector>;
 using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
 
 using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
 using BBPredicates = DenseMap<BasicBlock *, Value *>;
 using PredMap = DenseMap<BasicBlock *, BBPredicates>;
 using BB2BBMap = DenseMap<BasicBlock *, BasicBlock *>;
 
+using BranchDebugLocMap = DenseMap<BasicBlock *, DebugLoc>;
+
 // A traits type that is intended to be used in graph algorithms. The graph
 // traits starts at an entry node, and traverses the RegionNodes that are in
 // the Nodes set.
 struct SubGraphTraits {
   using NodeRef = std::pair<RegionNode *, SmallDenseSet<RegionNode *> *>;
   using BaseSuccIterator = GraphTraits<RegionNode *>::ChildIteratorType;
 
   // This wraps a set of Nodes into the iterator, so we know which edges to
class StructurizeCFG {
 
   PredMap Predicates;
   BranchVector Conditions;
 
   BB2BBMap Loops;
   PredMap LoopPreds;
   BranchVector LoopConds;
 
+  BranchDebugLocMap TermDL;
+
   RegionNode *PrevNode;
 
   void orderNodes();
 
   void analyzeLoops(RegionNode *N);
 
   Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
 
for (RegionNode *RN : reverse(Order)) {
     gatherPredicates(RN);
 
     // Remember that we've seen this node
     Visited.insert(RN->getEntry());
 
     // Find the last back edges
     analyzeLoops(RN);
   }
+
+  // Reset the collected term debug locations
+  TermDL.clear();
+
+  for (BasicBlock &BB : *Func) {
+    if (const DebugLoc &DL = BB.getTerminator()->getDebugLoc())
+      TermDL[&BB] = DL;
+  }
 }
 
 /// Insert the missing branch conditions
 void StructurizeCFG::insertConditions(bool Loops) {
   BranchVector &Conds = Loops ? LoopConds : Conditions;
   Value *Default = Loops ? BoolTrue : BoolFalse;
   SSAUpdater PhiInserter;
 
if (Node->isSubRegion()) {
     if (Dominator)
       DT->changeImmediateDominator(NewExit, Dominator);
 
     // Update the region info
     SubRegion->replaceExit(NewExit);
   } else {
     BasicBlock *BB = Node->getNodeAs<BasicBlock>();
     killTerminator(BB);
-    BranchInst::Create(NewExit, BB);
+    BranchInst *Br = BranchInst::Create(NewExit, BB);
+    Br->setDebugLoc(TermDL[BB]);
     addPhiValues(BB, NewExit);
     if (IncludeDominator)
       DT->changeImmediateDominator(NewExit, BB);
   }
 }
 
 /// Create a new flow node and update dominator tree and region info
 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
   LLVMContext &Context = Func->getContext();
   BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
                        Order.back()->getEntry();
   BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
                                         Func, Insert);
   FlowSet.insert(Flow);
+  TermDL[Flow] = TermDL[Dominator];
   DT->addNewBlock(Flow, Dominator);
   ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
   return Flow;
 }
 
 /// Create a new or reuse the previous node as flow node
 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
   BasicBlock *Entry = PrevNode->getEntry();
if (isPredictableTrue(Node)) {
     // Insert extra prefix node (or reuse last one)
     BasicBlock *Flow = needPrefix(false);
 
     // Insert extra postfix node (or use exit instead)
     BasicBlock *Entry = Node->getEntry();
     BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
 
     // let it point to entry and next block
-    Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
+    BranchInst *Br = BranchInst::Create(Entry, Next, BoolUndef, Flow);
+    Br->setDebugLoc(TermDL[Flow]);
+    Conditions.push_back(Br);
     addPhiValues(Flow, Entry);
     DT->changeImmediateDominator(Entry, Flow);
 
     PrevNode = Node;
     while (!Order.empty() && !Visited.count(LoopEnd) &&
            dominatesPredicates(Entry, Order.back())) {
       handleLoops(false, LoopEnd);
     }
while (!Visited.count(LoopEnd)) {
     handleLoops(false, LoopEnd);
   }
 
   assert(LoopStart != &LoopStart->getParent()->getEntryBlock());
 
   // Create an extra loop end node
   LoopEnd = needPrefix(false);
   BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
-  LoopConds.push_back(BranchInst::Create(Next, LoopStart,
-                                         BoolUndef, LoopEnd));
+  BranchInst *Br = BranchInst::Create(Next, LoopStart, BoolUndef, LoopEnd);
+  Br->setDebugLoc(TermDL[LoopEnd]);
+  LoopConds.push_back(Br);
   addPhiValues(LoopEnd, LoopStart);
   setPrevNode(Next);
 }
 
 /// After this function control flow looks like it should be, but
 /// branches and PHI nodes only have undefined conditions.
 void StructurizeCFG::createFlow() {
   BasicBlock *Exit = ParentRegion->getExit();
bool StructurizeCFG::run(Region *R, DominatorTree *DT) {
   DeletedPhis.clear();
   AddedPhis.clear();
   Predicates.clear();
   Conditions.clear();
   Loops.clear();
   LoopPreds.clear();
   LoopConds.clear();
   FlowSet.clear();
+  TermDL.clear();
 
   return true;
 }
 
 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
   return new StructurizeCFGLegacyPass(SkipUniformRegions);
 }
 

llvm/test/Transforms/StructurizeCFG/structurizecfg-debug-loc.ll

+; RUN: opt -S -o - -structurizecfg %s | FileCheck %s
+
+define void @if_then_else(i32 addrspace(1)* %out, i1 %arg) !dbg !7 {
+; CHECK: @if_then_else(
+; CHECK:  entry:
+; CHECK:    br i1 {{.*}}, label %if.else, label %Flow, !dbg [[ITE_ENTRY_DL:![0-9]+]]
+; CHECK:  Flow:
+; CHECK:    br i1 {{.*}}, label %if.then, label %exit, !dbg [[ITE_ENTRY_DL]]
+; CHECK:  if.then:
+; CHECK:    br label %exit, !dbg [[ITE_IFTHEN_DL:![0-9]+]]
+; CHECK:  if.else:
+; CHECK:    br label %Flow, !dbg [[ITE_IFELSE_DL:![0-9]+]]
+; CHECK:  exit:
+;
+entry:
+  br i1 %arg, label %if.then, label %if.else, !dbg !8
+
+if.then:
+  store i32 0, i32 addrspace(1)* %out, !dbg !9
+  br label %exit, !dbg !10
+
+if.else:
+  store i32 1, i32 addrspace(1)* %out, !dbg !11
+  br label %exit, !dbg !12
+
+exit:
+  ret void, !dbg !13
+}
+
+define void @while_loop(i32 addrspace(1)* %out) !dbg !14 {
+; CHECK: @while_loop(
+; CHECK:  entry:
+; CHECK:    br label %while.header, !dbg [[WHILE_ENTRY_DL:![0-9]+]]
+; CHECK:  while.header:
+; CHECK:    br i1 {{.*}}, label %while.body, label %Flow, !dbg [[WHILE_HEADER_DL:![0-9]+]]
+; CHECK:  while.body:
+; CHECK:    br label %Flow, !dbg [[WHILE_BODY_DL:![0-9]+]]
+; CHECK:  Flow:
+; CHECK:    br i1 {{.*}}, label %exit, label %while.header, !dbg [[WHILE_HEADER_DL]]
+; CHECK:  exit:
+;
+entry:
+  br label %while.header, !dbg !15
+
+while.header:
+  %cond = call i1 @loop_condition(), !dbg !16
+  br i1 %cond, label %while.body, label %exit, !dbg !17
+
+while.body:
+  store i32 1, i32 addrspace(1)* %out, !dbg !18
+  br label %while.header, !dbg !19
+
+exit:
+  ret void, !dbg !20
+}
+
+define void @while_multiple_exits(i32 addrspace(1)* %out) !dbg !21 {
+; CHECK: @while_multiple_exits(
+; CHECK:  entry:
+; CHECK:    br label %while.header, !dbg [[WHILEME_ENTRY_DL:![0-9]+]]
+; CHECK:  while.header:
+; CHECK:    br i1 {{.*}}, label %while.exiting, label %Flow, !dbg [[WHILEME_HEADER_DL:![0-9]+]]
+; CHECK:  while.exiting:
+; CHECK:    br label %Flow, !dbg [[WHILEME_EXITING_DL:![0-9]+]]
+; CHECK:  Flow:
+; CHECK:    br i1 {{.*}}, label %exit, label %while.header, !dbg [[WHILEME_HEADER_DL]] 
+; CHECK:  exit:
+;
+entry:
+  br label %while.header, !dbg !22
+
+while.header:
+  %cond0 = call i1 @loop_condition(), !dbg !23
+  br i1 %cond0, label %while.exiting, label %exit, !dbg !24
+
+while.exiting:
+  %cond1 = call i1 @loop_condition(), !dbg !25
+  br i1 %cond1, label %while.header, label %exit, !dbg !26
+
+exit:
+  ret void, !dbg !27
+}
+
+define void @nested_if_then_else(i32 addrspace(1)* %out, i1 %a, i1 %b) !dbg !28 {
+; CHECK: @nested_if_then_else(
+; CHECK:  entry:
+; CHECK:    br i1 {{.*}}, label %if.else, label %Flow4, !dbg [[NESTED_ENTRY_DL:![0-9]+]]
+; CHECK:  Flow4:
+; CHECK:    br i1 {{.*}}, label %if.then, label %exit, !dbg [[NESTED_ENTRY_DL]]
+; CHECK:  if.then:
+; CHECK:    br i1 {{.*}}, label %if.then.else, label %Flow2, !dbg [[NESTED_IFTHEN_DL:![0-9]+]]
+; CHECK:  Flow2:
+; CHECK:    br i1 {{.*}}, label %if.then.then, label %Flow3, !dbg [[NESTED_IFTHEN_DL]]
+; CHECK:  if.then.then:
+; CHECK:    br label %Flow3, !dbg [[NESTED_IFTHENTHEN_DL:![0-9]+]]
+; CHECK:  if.then.else:
+; CHECK:    br label %Flow2, !dbg [[NESTED_IFTHENELSE_DL:![0-9]+]]
+; CHECK:  if.else:
+; CHECK:    br i1 {{.*}}, label %if.else.else, label %Flow, !dbg [[NESTED_IFELSE_DL:![0-9]+]]
+; CHECK:  Flow:
+; CHECK:    br i1 {{.*}}, label %if.else.then, label %Flow1, !dbg [[NESTED_IFELSE_DL]]
+; CHECK:  if.else.then:
+; CHECK:    br label %Flow1, !dbg [[NESTED_IFELSETHEN_DL:![0-9]+]]
+; CHECK:  if.else.else:
+; CHECK:    br label %Flow, !dbg [[NESTED_IFELSEELSE_DL:![0-9]+]]
+; CHECK:  Flow1:
+; CHECK:    br label %Flow4, !dbg [[NESTED_IFELSE_DL]]
+; CHECK:  Flow3:
+; CHECK:    br label %exit, !dbg [[NESTED_IFTHEN_DL]]
+; CHECK:  exit:
+;
+entry:
+  br i1 %a, label %if.then, label %if.else, !dbg !29
+
+if.then:
+  br i1 %b, label %if.then.then, label %if.then.else, !dbg !30
+
+if.then.then:
+  store i32 0, i32 addrspace(1)* %out, !dbg !31
+  br label %exit, !dbg !32
+
+if.then.else:
+  store i32 1, i32 addrspace(1)* %out, !dbg !33
+  br label %exit, !dbg !34
+
+if.else:
+  br i1 %b, label %if.else.then, label %if.else.else, !dbg !35
+
+if.else.then:
+  store i32 2, i32 addrspace(1)* %out, !dbg !36
+  br label %exit, !dbg !37
+
+if.else.else:
+  store i32 3, i32 addrspace(1)* %out, !dbg !38
+  br label %exit, !dbg !39
+
+exit:
+  ret void, !dbg !40
+}
+
+declare i1 @loop_condition()
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!4, !5}
+
+; CHECK: [[ITE_ENTRY_DL]] = !DILocation(line: 2
+; CHECK: [[ITE_IFTHEN_DL]] = !DILocation(line: 4
+; CHECK: [[ITE_IFELSE_DL]] = !DILocation(line: 6
+; CHECK: [[WHILE_ENTRY_DL]] = !DILocation(line: 2
+; CHECK: [[WHILE_HEADER_DL]] = !DILocation(line: 4
+; CHECK: [[WHILE_BODY_DL]] = !DILocation(line: 6
+; CHECK: [[WHILEME_ENTRY_DL]] = !DILocation(line: 2
+; CHECK: [[WHILEME_HEADER_DL]] = !DILocation(line: 4
+; CHECK: [[WHILEME_EXITING_DL]] = !DILocation(line: 6
+; CHECK: [[NESTED_ENTRY_DL]] = !DILocation(line: 2
+; CHECK: [[NESTED_IFTHEN_DL]] = !DILocation(line: 3
+; CHECK: [[NESTED_IFTHENTHEN_DL]] = !DILocation(line: 5
+; CHECK: [[NESTED_IFTHENELSE_DL]] = !DILocation(line: 7
+; CHECK: [[NESTED_IFELSE_DL]] = !DILocation(line: 8
+; CHECK: [[NESTED_IFELSETHEN_DL]] = !DILocation(line: 10 
+; CHECK: [[NESTED_IFELSEELSE_DL]] = !DILocation(line: 12
+
+!0 = !{}
+!1 = !DIFile(filename: "dummy.ll", directory: "/some/random/directory")
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !0)
+!4 = !{i32 2, !"Dwarf Version", i32 5}
+!5 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = !DISubroutineType(types: !0)
+!7 = distinct !DISubprogram(name: "dummy", scope: !1, file: !1, line: 1, type: !6, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !2, retainedNodes: !0)
+!8 = !DILocation(line: 2, scope: !7)
+!9 = !DILocation(line: 3, scope: !7)
+!10 = !DILocation(line: 4, scope: !7)
+!11 = !DILocation(line: 5, scope: !7)
+!12 = !DILocation(line: 6, scope: !7)
+!13 = !DILocation(line: 7, scope: !7)
+!14 = distinct !DISubprogram(name: "dummy", scope: !1, file: !1, line: 1, type: !6, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !2, retainedNodes: !0)
+!15 = !DILocation(line: 2, scope: !14)
+!16 = !DILocation(line: 3, scope: !14)
+!17 = !DILocation(line: 4, scope: !14)
+!18 = !DILocation(line: 5, scope: !14)
+!19 = !DILocation(line: 6, scope: !14)
+!20 = !DILocation(line: 7, scope: !14)
+!21 = distinct !DISubprogram(name: "dummy", scope: !1, file: !1, line: 1, type: !6, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !2, retainedNodes: !0)
+!22 = !DILocation(line: 2, scope: !21)
+!23 = !DILocation(line: 3, scope: !21)
+!24 = !DILocation(line: 4, scope: !21)
+!25 = !DILocation(line: 5, scope: !21)
+!26 = !DILocation(line: 6, scope: !21)
+!27 = !DILocation(line: 7, scope: !21)
+!28 = distinct !DISubprogram(name: "dummy", scope: !1, file: !1, line: 1, type: !6, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !2, retainedNodes: !0)
+!29 = !DILocation(line: 2, scope: !28)
+!30 = !DILocation(line: 3, scope: !28)
+!31 = !DILocation(line: 4, scope: !28)
+!32 = !DILocation(line: 5, scope: !28)
+!33 = !DILocation(line: 6, scope: !28)
+!34 = !DILocation(line: 7, scope: !28)
+!35 = !DILocation(line: 8, scope: !28)
+!36 = !DILocation(line: 9, scope: !28)
+!37 = !DILocation(line: 10, scope: !28)
+!38 = !DILocation(line: 11, scope: !28)
+!39 = !DILocation(line: 12, scope: !28)
+!40 = !DILocation(line: 13, scope: !28)