[DebugInfo][InstrRef][NFC] Don't build mappings of values to locations for un-needed values

[jmorse]

Summary

When finding locations for variable values at the start of a block, we build a large map of every value to every location, and then pick out the locations for values that are desired. This takes up quite a lot of time, because, unsurprisingly, there are usually more values in registers and stack slots than there are variables.

This patch instead creates a map of desired values to their locations, which are initially illegal locations. Then, as we examine every available value, we can select locations for values we care about, and ignore those that we don't. This substantially reduces the amount of work done (i.e., building a map up of values to locations that nothing wants or needs).

Geomean performance improvement of 1%: http://llvm-compile-time-tracker.com/compare.php?from=427eff43fcd470caa5cf44e10188c50f89b93af8&to=842aefd941f8e5f2d73b3178fdbbd7d27df9c55a&stat=instructions

[Orlando]

Nice! I have one question inline but this SGTM.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

323

Hmm... can ValuesPreferredLoc == ValueToLoc.end() ever be true now, with this patch?

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

323

Good point, I'll remove that when landing.

[Orlando]

LGTM

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

auto isCalleeSaved = [&](LocIdx L) {
       for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
         if (CalleeSavedRegs.test(*RAI))
           return true;
       return false;
     };
 
     // Map of the preferred location for each value.
     DenseMap<ValueIDNum, LocIdx> ValueToLoc;
+
+    // Initialized the preferred-location map with illegal locations, to be
+    // filled in later.
+    for (auto &VLoc : VLocs)
+      if (VLoc.second.Kind == DbgValue::Def)
+        ValueToLoc.insert({VLoc.second.ID, LocIdx::MakeIllegalLoc()});
+
     ActiveMLocs.reserve(VLocs.size());
     ActiveVLocs.reserve(VLocs.size());
 
     // Produce a map of value numbers to the current machine locs they live
     // in. When emulating VarLocBasedImpl, there should only be one
     // location; when not, we get to pick.
     for (auto Location : MTracker->locations()) {
       LocIdx Idx = Location.Idx;
       ValueIDNum &VNum = MLocs[Idx.asU64()];
       VarLocs.push_back(VNum);
 
-      // Short-circuit unnecessary preferred location update.
-      if (VLocs.empty())
+      // Is there a variable that wants a location for this value? If not, skip.
+      auto VIt = ValueToLoc.find(VNum);
+      if (VIt == ValueToLoc.end())
         continue;
 
-      auto it = ValueToLoc.find(VNum);
+      LocIdx CurLoc = VIt->second;
       // In order of preference, pick:
       //  * Callee saved registers,
       //  * Other registers,
       //  * Spill slots.
-      if (it == ValueToLoc.end() || MTracker->isSpill(it->second) ||
-          (!isCalleeSaved(it->second) && isCalleeSaved(Idx.asU64()))) {
+      if (CurLoc.isIllegal() || MTracker->isSpill(CurLoc) ||
+          (!isCalleeSaved(CurLoc) && isCalleeSaved(Idx.asU64()))) {
         // Insert, or overwrite if insertion failed.
-        auto PrefLocRes = ValueToLoc.insert(std::make_pair(VNum, Idx));
-        if (!PrefLocRes.second)
-          PrefLocRes.first->second = Idx;
+        VIt->second = Idx;
       }
     }
 
     // Now map variables to their picked LocIdxes.
     for (const auto &Var : VLocs) {
       if (Var.second.Kind == DbgValue::Const) {
         PendingDbgValues.push_back(
             emitMOLoc(*Var.second.MO, Var.first, Var.second.Properties));
         continue;
       }
 
       // If the value has no location, we can't make a variable location.
       const ValueIDNum &Num = Var.second.ID;
       auto ValuesPreferredLoc = ValueToLoc.find(Num);
-      if (ValuesPreferredLoc == ValueToLoc.end()) {
+      if (ValuesPreferredLoc->second.isIllegal()) {
         // If it's a def that occurs in this block, register it as a
         // use-before-def to be resolved as we step through the block.
         if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
           addUseBeforeDef(Var.first, Var.second.Properties, Num);
         else
           recoverAsEntryValue(Var.first, Var.second.Properties, Num);
         continue;
       }