[DebugInfo][InstrRef][NFC] Cache some PHI resolutions

[jmorse]

Summary

Install a cache of DBG_INSTR_REF -> ValueIDNum resolutions, for scenarios where the value has to be reconstructed from several DBG_PHIs. Whenever this happens, it's because branch folding + tail duplication has messed with the SSA form of the program, and we have to solve a mini SSA problem to find the variable value. This is always called twice, so it makes sense to cache the value.

There's a secondary reason, which is that the resolveDbgPHIs function makes use of the per-register machine-value tables, potentially late in the LiveDebugValues process. Those are about to be freed earlier in the next patch I upload, so it's good to cache and avoid the second call to resolveDbgPHIs. There's also a compile time improvement for a few benchmarks [0]

[0] http://llvm-compile-time-tracker.com/compare.php?from=7dfb73512c6ba1eb720e6a0da954f262c6bb53fe&to=fd6b2a1e76dc22f808f031e4e50b27a851776e48&stat=instructions

[dblaikie]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

3455–3456

Given the need to touch every return from this function, and they're fairly spread out - might be good to refactor the non-cache-hit part of the function into another function, call that from the caching version and only have to have one SeenDbgPHIs.insert call that then ends up relatively close to the SeenDbgPHIs lookup code too?

(& I guess operations in this function invalidate the SeenDbgPHIs iterator, otherwise you could use that (possibly even call insert) later on to save the extra lookup)

[StephenTozer]

Seems like a good change - the compile time improvement is nice, and this doesn't look like it should have a noticeable memory footprint. LGTM with the other comments addressed.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

3455–3456

+1, better readability + prevents someone in the future from adding a new return without the cache insert.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

869

Nit.

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

3455–3456

Clearly I was missing a lot of caffeine when writing this patch, this is definitely the right solution.

[jmorse]

Shuffle PHI-resolution-caching into its own method.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

private:
   /// location problem -- we use LLVMs SSA Updater to fix changes by
   /// optimizations that destroy PHI instructions.
   SmallVector<DebugPHIRecord, 32> DebugPHINumToValue;
 
   // Map of overlapping variable fragments.
   OverlapMap OverlapFragments;
   VarToFragments SeenFragments;
 
+  /// Mapping of DBG_INSTR_REF instructions to their values, for those
+  /// DBG_INSTR_REFs that call resolveDbgPHIs. These variable references solve
+  /// a mini SSA problem caused by DBG_PHIs being cloned, this collection caches
+  /// the result.
+  DenseMap<MachineInstr *, Optional<ValueIDNum>> SeenDbgPHIs;
+
   /// True if we need to examine call instructions for stack clobbers. We
   /// normally assume that they don't clobber SP, but stack probes on Windows
   /// do.
   bool AdjustsStackInCalls = false;
 
   /// If AdjustsStackInCalls is true, this holds the name of the target's stack
   /// probe function, which is the function we expect will alter the stack
   /// pointer.
private:
   /// \p Here the position of a DBG_INSTR_REF seeking a machine value number
   /// \p InstrNum Debug instruction number defined by DBG_PHI instructions.
   /// \returns The machine value number at position Here, or None.
   Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF,
                                       ValueIDNum **MLiveOuts,
                                       ValueIDNum **MLiveIns, MachineInstr &Here,
                                       uint64_t InstrNum);
 
+  Optional<ValueIDNum> resolveDbgPHIsImpl(MachineFunction &MF,
+                                          ValueIDNum **MLiveOuts,
+                                          ValueIDNum **MLiveIns,
+                                          MachineInstr &Here,
+                                          uint64_t InstrNum);
+
   /// Step through the function, recording register definitions and movements
   /// in an MLocTracker. Convert the observations into a per-block transfer
   /// function in \p MLocTransfer, suitable for using with the machine value
   /// location dataflow problem.
   void
   produceMLocTransferFunction(MachineFunction &MF,
                               SmallVectorImpl<MLocTransferMap> &MLocTransfer,
                               unsigned MaxNumBlocks);

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   ArtificialBlocks.clear();
   OrderToBB.clear();
   BBToOrder.clear();
   BBNumToRPO.clear();
   DebugInstrNumToInstr.clear();
   DebugPHINumToValue.clear();
   OverlapFragments.clear();
   SeenFragments.clear();
+  SeenDbgPHIs.clear();
 
   return Changed;
 }
 
 LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
   return new InstrRefBasedLDV();
 }
 

 
 } // end namespace llvm
 
 Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
                                                       ValueIDNum **MLiveOuts,
                                                       ValueIDNum **MLiveIns,
                                                       MachineInstr &Here,
                                                       uint64_t InstrNum) {
+  // This function will be called twice per DBG_INSTR_REF, and might end up
+  // computing lots of SSA information: memoize it.
+  auto SeenDbgPHIIt = SeenDbgPHIs.find(&Here);
+  if (SeenDbgPHIIt != SeenDbgPHIs.end())
+    return SeenDbgPHIIt->second;
+
+  Optional<ValueIDNum> Result =
+      resolveDbgPHIsImpl(MF, MLiveOuts, MLiveIns, Here, InstrNum);
+  SeenDbgPHIs.insert({&Here, Result});
+  return Result;
+}
+
+Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIsImpl(
+    MachineFunction &MF, ValueIDNum **MLiveOuts, ValueIDNum **MLiveIns,
+    MachineInstr &Here, uint64_t InstrNum) {
   // Pick out records of DBG_PHI instructions that have been observed. If there
   // are none, then we cannot compute a value number.
   auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
                                     DebugPHINumToValue.end(), InstrNum);
   auto LowerIt = RangePair.first;
   auto UpperIt = RangePair.second;
 
   // No DBG_PHI means there can be no location.
for (const auto &DBG_PHI : DBGPHIRange) {
     AvailableValues.insert(std::make_pair(Block, Num.asU64()));
   }
 
   LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());
   const auto &AvailIt = AvailableValues.find(HereBlock);
   if (AvailIt != AvailableValues.end()) {
     // Actually, we already know what the value is -- the Use is in the same
     // block as the Def.
     return ValueIDNum::fromU64(AvailIt->second);
   }
 
   // Otherwise, we must use the SSA Updater. It will identify the value number
   // that we are to use, and the PHIs that must happen along the way.
   SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
   BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));
   ValueIDNum Result = ValueIDNum::fromU64(ResultInt);
 
   // We have the number for a PHI, or possibly live-through value, to be used