[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

3416–3417

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

3416–3417

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

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

872

Nit.

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

3416–3417

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 colleciton 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.

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;
+
   // 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.
+    SeenDbgPHIs.insert({&Here, ValueIDNum::fromU64(AvailIt->second)});
     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);
 
Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
 
   for (auto &PHI : SortedPHIs) {
     ValueIDNum ThisBlockValueNum =
         MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()];
 
     // Are all these things actually defined?
     for (auto &PHIIt : PHI->IncomingValues) {
       // Any undef input means DBG_PHIs didn't dominate the use point.
-      if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
+      if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end()) {
+        SeenDbgPHIs.insert({&Here, None});
         return None;
+      }
 
       ValueIDNum ValueToCheck;
       ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];
 
       auto VVal = ValidatedValues.find(PHIIt.first);
       if (VVal == ValidatedValues.end()) {
         // We cross a loop, and this is a backedge. LLVMs tail duplication
         // happens so late that DBG_PHI instructions should not be able to
         // migrate into loops -- meaning we can only be live-through this
         // loop.
         ValueToCheck = ThisBlockValueNum;
       } else {
         // Does the block have as a live-out, in the location we're examining,
         // the value that we expect? If not, it's been moved or clobbered.
         ValueToCheck = VVal->second;
       }
 
-      if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
+      if (BlockLiveOuts[Loc.asU64()] != ValueToCheck) {
+        SeenDbgPHIs.insert({&Here, None});
         return None;
       }
+    }
 
     // Record this value as validated.
     ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});
   }
 
   // All the PHIs are valid: we can return what the SSAUpdater said our value
   // number was.
+  SeenDbgPHIs.insert({&Here, Result});
   return Result;
 }