[DebugInfo][InstrRef] Take a short-cut when propagating variable values if there's only one value

[jmorse]

Summary

This is a performance patch that also partially fixes https://llvm.org/PR48091, by propagating variable values past out-of-scope blocks.

Key observation: when converting to SSA, if you only have a single variable definition, then the variable has that value in every dominated block, and no well defined value in all other blocks. Seeing how InstrRefBasedLDV does PHI-placement and value propagation, which is often slow, we can use this observation to simplify variable value propagation when there's only one variable definition.

Observe this CFG (replicated in the test below):

     entry
    /  |  \
   /   v   \
  /   bb1   \    <--- Single variable assignment happens here
 /   /   \   \
/   v     v   \
| bb2     bb3 |
|   \    /    |
|    v  v     |
|     bb4     |
 \   /   \    /
  v v     v  v
   bb5    bb6    <---  Dominance frontier is here

The general InstrRefBasedLDV algorithm would place PHIs at bb5 and bb6, on the dominance frontier of the variable assignment. We'd then do some value propagation to work out whether those PHIs could be eliminated, and finally decided that they could never be resolved to a variable location, and drop the variable location in those blocks. The speed optimisation is to, in scenarios like this where there are single assignments, to just propagate the assigned value into each dominated block, and no other blocks. That avoids PHI placement and elimination. This leads to a geomean CTMark speed improvement of 0.9% [0], horray.

However, this change isn't NFC, as it partially fixes https://llvm.org/PR48091 . Observe the attached test: if we make bb2's lexical scope something out-of-scope for the variable being analysed, then VarLocBasedLDV doesn't propagate the variable location through it to bb4. I think VarLocBasedLDV does this because of performance reasons; with this change, we _do_ propagate the variable into bb4, meaning InstrRefBasedLDV diverges from VarLocBasedLDV a little.

I think this is a legitimate improvement in coverage: if there wasn't an out of scope block in the way, we would always propagate into dominated blocks like bb4 anyway. The fact that there's an out-of-scope block can only because of optimisations AFAIUI -- and I can't think of a functional reason why the intervening block might change the variable value in a different scope. If it was an artificial block (with no source locations), we already propagate through it anyway.

Testing: [0], plus I built clang-3.4 and observed some 5k more variable locations as a result of this, the benefits of the functional change. I also experimented with aborting placePHIsForSingleVarDefinition if it saw an out-of-scope block: doing so produces an identical clang 3.4 binary (modulo the usual differences).

[0] http://llvm-compile-time-tracker.com/compare.php?from=1b09d0c42b42be219dd0984e0714d68b4a36cd3e&to=ac78c9434e1a33a137c07054f1c2300083524ca0&stat=instructions

[StephenTozer]

LGTM, nice performance improvement!

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

private:
 
   /// Install PHI values into the live-in array for each block, according to
   /// the IDF of each register.
   void placeMLocPHIs(MachineFunction &MF,
                      SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
                      ValueIDNum **MInLocs,
                      SmallVectorImpl<MLocTransferMap> &MLocTransfer);
 
+  /// Propagate variable values to blocks in the common case where there's
+  /// only one value assigned to the variable. This function has better
+  /// performance as it doesn't have to find the dominance frontier between
+  /// different assignments.
+  void placePHIsForSingleVarDefinition(
+          const SmallPtrSetImpl<MachineBasicBlock *> &InScopeBlocks,
+          MachineBasicBlock *MBB, SmallVectorImpl<VLocTracker> &AllTheVLocs,
+          const DebugVariable &Var, LiveInsT &Output);
+
   /// Calculate the iterated-dominance-frontier for a set of defs, using the
   /// existing LLVM facilities for this. Works for a single "value" or
   /// machine/variable location.
   /// \p AllBlocks Set of blocks where we might consume the value.
   /// \p DefBlocks Set of blocks where the value/location is defined.
   /// \p PHIBlocks Output set of blocks where PHIs must be placed.
   void BlockPHIPlacement(const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
                          const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

for (auto &Var : VarsWeCareAbout) {
     for (const MachineBasicBlock *ExpMBB : BlocksToExplore) {
       auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;
       if (TransferFunc.find(Var) != TransferFunc.end())
         DefBlocks.insert(const_cast<MachineBasicBlock *>(ExpMBB));
     }
 
     SmallVector<MachineBasicBlock *, 32> PHIBlocks;
 
-    // Request the set of PHIs we should insert for this variable.
+    // Request the set of PHIs we should insert for this variable. If there's
+    // only one value definition, things are very simple.
+    if (DefBlocks.size() == 1) {
+      placePHIsForSingleVarDefinition(MutBlocksToExplore, *DefBlocks.begin(),
+                                      AllTheVLocs, Var, Output);
+      continue;
+    }
+
+    // Otherwise: we need to place PHIs through SSA and propagate values.
     BlockPHIPlacement(MutBlocksToExplore, DefBlocks, PHIBlocks);
 
     // Insert PHIs into the per-block live-in tables for this variable.
     for (MachineBasicBlock *PHIMBB : PHIBlocks) {
       unsigned BlockNo = PHIMBB->getNumber();
       DbgValue *LiveIn = LiveInIdx[PHIMBB];
       *LiveIn = DbgValue(BlockNo, EmptyProperties, DbgValue::VPHI);
     }
for (auto *MBB : BlockOrders) {
       Output[MBB->getNumber()].push_back(std::make_pair(Var, *BlockLiveIn));
     }
   } // Per-variable loop.
 
   BlockOrders.clear();
   BlocksToExplore.clear();
 }
 
+void InstrRefBasedLDV::placePHIsForSingleVarDefinition(
+    const SmallPtrSetImpl<MachineBasicBlock *> &InScopeBlocks,
+    MachineBasicBlock *AssignMBB, SmallVectorImpl<VLocTracker> &AllTheVLocs,
+    const DebugVariable &Var, LiveInsT &Output) {
+  // If there is a single definition of the variable, then working out it's
+  // value everywhere is very simple: it's every block dominated by the
+  // definition. At the dominance frontier, the usual algorithm would:
+  //  * Place PHIs,
+  //  * Propagate values into them,
+  //  * Find there's no incoming variable value from the other incoming branches
+  //    of the dominance frontier,
+  //  * Specify there's no variable value in blocks past the frontier.
+  // This is a common case, hence it's worth special-casing it.
+
+  // Pick out the variables value from the block transfer function.
+  VLocTracker &VLocs = AllTheVLocs[AssignMBB->getNumber()];
+  auto ValueIt = VLocs.Vars.find(Var);
+  const DbgValue &Value = ValueIt->second;
+
+  // Assign the variable value to entry to each dominated block that's in scope.
+  // Skip the definition block -- it's assigned the variable value in the middle
+  // of the block somewhere.
+  for (auto *ScopeBlock : InScopeBlocks) {
+    if (!DomTree->properlyDominates(AssignMBB, ScopeBlock))
+      continue;
+
+    Output[ScopeBlock->getNumber()].push_back({Var, Value});
+  }
+
+  // All blocks that aren't dominated have no live-in value, thus no variable
+  // value will be given to them.
+}
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void InstrRefBasedLDV::dump_mloc_transfer(
     const MLocTransferMap &mloc_transfer) const {
   for (auto &P : mloc_transfer) {
     std::string foo = MTracker->LocIdxToName(P.first);
     std::string bar = MTracker->IDAsString(P.second);
     dbgs() << "Loc " << foo << " --> " << bar << "\n";
   }

llvm/test/DebugInfo/MIR/InstrRef/single-assign-propagation.mir

+# RUN: llc %s -march=x86-64 -run-pass=livedebugvalues -o - \
+# RUN:       -experimental-debug-variable-locations=true \
+# RUN:     | FileCheck %s -implicit-check-not=DBG_VALUE
+# RUN: llc %s -march=x86-64 -run-pass=livedebugvalues -o - \
+# RUN:       -experimental-debug-variable-locations=false \
+# RUN:     | FileCheck %s --check-prefixes=VARLOC -implicit-check-not=DBG_VALUE
+#
+# This test is designed to stimulate a simplification of variable-value
+# propagation in InstrRefBasedLDV. When we only have a single assignment of
+# a variable, we don't have to completely enumerate all the PHIs the variable
+# has and then value propagate through them: the variable value is available
+# only in those blocks dominated by the assignment. Example in this test:
+#
+#             entry
+#            /  |  \
+#           /   v   \
+#          /   bb1   \    <--- Single variable assignment happens here
+#         /   /   \   \
+#        /   v     v   \
+#        | bb2     bb3 |
+#        |   \    /    |
+#        |    v  v     |
+#        |     bb4     |
+#         \   /   \    /
+#          v v     v  v
+#           bb5    bb6    <---  Dominance frontier is here
+#
+# The general InstrRefBasedLDV algorithm takes this CFG, places PHIs at bb5 and
+# bb6, then value-propagates until it's determined that they can't be
+# eliminated. Then, we determine that there's no machine location for such PHIs,
+# and no variable location is emitted.
+#
+# The fast way of doing this: observe that the variable value can never extend
+# past the dominance frontier of the block where the assignment happens. So
+# just propagate the variable value into the dominated blocks, and avoid the
+# general algorithm.
+#
+# Doing so introduces a functional change: VarLocBasedLDV won't propagate
+# variable locations through out-of-scope blocks, and InstrRefBasedLDV tries to
+# replicate VarLocBasedLDV most of the time. In the MIR below, bb2 is out of
+# scope. This effectively becomes another variable assignment (of undef), which
+# requires full SSA and value propagation to emulate what VarLocBasedLDV did.
+# Applying this speed optimisation makes us diverge from what VarLocBasedLDV
+# does by not treating the out-of-scope block as an effective undef assignment,
+# hence this test.
+#
+# CHECK-LABEL: bb.1:
+# CHECK:       DBG_VALUE
+# CHECK-LABEL: bb.2:
+## No location here because it's out-of-scope.
+# CHECK-LABEL: bb.3:
+# CHECK:       DBG_VALUE
+# CHECK-LABEL: bb.4:
+# CHECK:       DBG_VALUE
+#
+## VarLocBasedLDV will take the DBG_VALUE in the assignment block, propagate
+## to bb.3, but not into bb.4 because of the intervening out-of-scope block.
+#
+# VARLOC-LABEL: bb.1:
+# VARLOC:       DBG_VALUE
+# VARLOC-LABEL: bb.2:
+## No location here because it's out-of-scope.
+# VARLOC-LABEL: bb.3:
+# VARLOC:       DBG_VALUE
+#
+--- |
+  define i32 @_Z8bb_to_bb() local_unnamed_addr !dbg !12 {
+  entry:
+    ret i32 0, !dbg !17
+  }
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!7, !8, !9, !10}
+  !llvm.ident = !{!11}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, globals: !3, debugInfoForProfiling: true, nameTableKind: None)
+  !1 = !DIFile(filename: "main.cpp", directory: "F:\")
+  !2 = !{}
+  !3 = !{!4}
+  !4 = !DIGlobalVariableExpression(var: !5, expr: !DIExpression())
+  !5 = distinct !DIGlobalVariable(name: "start", scope: !0, file: !1, line: 4, type: !6, isLocal: false, isDefinition: true)
+  !6 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !7 = !{i32 2, !"Dwarf Version", i32 4}
+  !8 = !{i32 2, !"Debug Info Version", i32 3}
+  !9 = !{i32 1, !"wchar_size", i32 2}
+  !10 = !{i32 7, !"PIC Level", i32 2}
+  !11 = !{!"clang"}
+  !12 = distinct !DISubprogram(name: "bb_to_bb", linkageName: "bb_to_bb", scope: !1, file: !1, line: 6, type: !13, scopeLine: 6, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !15)
+  !13 = !DISubroutineType(types: !14)
+  !14 = !{!6, !6}
+  !15 = !{!16}
+  !16 = !DILocalVariable(name: "myVar", scope: !18, file: !1, line: 7, type: !6)
+  !17 = !DILocation(line: 10, scope: !18)
+  !18 = distinct !DILexicalBlock(scope: !12, file: !1, line: 1, column: 1)
+  !19 = distinct !DILexicalBlock(scope: !12, file: !1, line: 1, column: 1)
+  !20 = !DILocation(line: 10, scope: !19)
+
+...
+---
+name: _Z8bb_to_bb
+debugValueSubstitutions:
+  - { srcinst: 4, srcop: 0, dstinst: 3, dstop: 0, subreg: 0 }
+body:  |
+  bb.0.entry:
+    successors: %bb.1, %bb.5, %bb.6
+
+    $rax = MOV64ri 1, debug-instr-number 1, debug-location !17
+    JCC_1 %bb.5, 1, implicit $eflags
+    JCC_1 %bb.6, 2, implicit $eflags
+    JMP_1 %bb.1
+
+  bb.1:
+    successors: %bb.2, %bb.3
+
+    DBG_VALUE $rax, $noreg, !16, !DIExpression(), debug-location !17
+    JCC_1 %bb.3, 1, implicit $eflags, debug-location !17
+
+  bb.2:
+    successors: %bb.4
+
+    JMP_1 %bb.4, debug-location !20
+
+  bb.3:
+    successors: %bb.4
+
+    JMP_1 %bb.4, debug-location !17
+
+  bb.4:
+    successors: %bb.5, %bb.6
+
+    JCC_1 %bb.5, 1, implicit $eflags, debug-location !17
+    JMP_1 %bb.6, debug-location !17
+
+  bb.5:
+    RET 0, debug-location !17
+
+  bb.6:
+    RET 0, debug-location !17