[Assignment Tracking Analysis][2/*] Remove redundant location definitions

[Orlando]

Summary

Implement the removeRedundantDbgInstrs cleanup from lib/Transforms/Utils/BasicBlockUtils.cpp for FunctionVarLocBuilder's variable location definitions.

Removing redundant entries has the obvious benefits of reducing peak memory when using the results of the analysis and reducing the final number of MIR debug instructions.

It also has a less obvious benefit. This patch is not an NFC change because SelectionDAG has a habit of doing Bad Things with variable locations - removing the number of location definitions tends to reduce the number of Bad Things.

Two examples I have seen:

1. Argument SDDbgValues hoisted above undef `SDDbgValues.
2. undef SDDbgValues in a block of contiguous SDDbgValues spuriously changing order.

---

Tests coming in a later patch.

[StephenTozer]

Minor comments, otherwise LGTM.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

1501

YMMV so just a suggestion, but could the entry block stuff be moved into a separate function? As-is there's a DenseMap in this function, which is reasonably large even when unused (and possibly can't be optimized out by the compiler since it's dependent on the return value of BB->isEntryBlock()?), and in terms of behaviour it seems like two fairly distinct behaviours bundled into one function. I can also see how it may make sense to have them together in a single forward-scanning function though, so your call on whether to split it or not.

1547

[jmorse]

This is all fine and well; are redundant variable locations a common case and which should we optimise for? IIUC every instruction with debug-info results in a SmallVector copy right now, which isn't necessary if that specific position hasn't had debug-info change. IMO, adding a "ChangedPosition" flag that's used to skip setWedge if it isn't true would be beneficial.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

1469

Ideally Key would be a reference to avoid any un-necessary copying, I think doing that hinges on feedback in the parent patch.

1514

One extra malloc per block seems like quite a bit, use SmallDenseMap?

[Orlando]

Factored out removeUndefDbgLocsFromEntryBlock and addressed other comments.

[Orlando]

In D136321#3943496, @jmorse wrote:

This is all fine and well; are redundant variable locations a common case and which should we optimise for? IIUC every instruction with debug-info results in a SmallVector copy right now, which isn't necessary if that specific position hasn't had debug-info change. IMO, adding a "ChangedPosition" flag that's used to skip setWedge if it isn't true would be beneficial.

In the previous patch I changed setWedge to take an r-value reference. I don't have a good feeling as to whether grow, move, reset in a loop (growing from the start each time) is more or less performant than grow, copy, clear (which is something we could do instead by moving the vector out of the loops). I tried profiling this but on my test case the difference is lost in the noise. I've gone with the grow, move, reset version for now to avoid adding a setWedge overload but this can always be changed if we find a pathological case. I've added some statistics so we can get a better feel for this "in the wild" and adjust later. The anecdotal results I got for a compiling a single file were about 1% of wedges get modified, which may support the case for grow, copy, clear.

[Orlando]

Squashed into 1d1de7467c32d52926ca56b9167a2c65c451ecfa

[Orlando]

Squashed into 1d1de7467c32d52926ca56b9167a2c65c451ecfa

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

 #include "llvm/CodeGen/AssignmentTrackingAnalysis.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/UniqueVector.h"
 #include "llvm/Analysis/Interval.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PrintPasses.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include <assert.h>
 #include <cstdint>
 #include <sstream>
 #include <unordered_map>
 
 using namespace llvm;
 #define DEBUG_TYPE "debug-ata"
 
+STATISTIC(NumDefsScanned, "Number of dbg locs that get scanned for removal");
+STATISTIC(NumDefsRemoved, "Number of dbg locs removed");
+STATISTIC(NumWedgesScanned, "Number of dbg wedges scanned");
+STATISTIC(NumWedgesChanged, "Number of dbg wedges changed");
+
 static cl::opt<unsigned>
     MaxNumBlocks("debug-ata-max-blocks", cl::init(10000),
                  cl::desc("Maximum num basic blocks before debug info dropped"),
                  cl::Hidden);
 /// Print the results of the analysis. Respects -filter-print-funcs.
 static cl::opt<bool> PrintResults("print-debug-ata", cl::init(false),
                                   cl::Hidden);
 
for (auto &I : BB) {
                            DVI->getExpression(), DVI->getDebugLoc(),
                            GetValue());
       InsertedAnyIntrinsics = true;
     }
   }
   return InsertedAnyIntrinsics;
 }
 
+/// Remove redundant definitions within sequences of consecutive location defs.
+/// This is done using a backward scan to keep the last def describing a
+/// specific variable/fragment.
+///
+/// This implements removeRedundantDbgInstrsUsingBackwardScan from
+/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
+/// FunctionVarLocsBuilder instead of with intrinsics.
+static bool
+removeRedundantDbgLocsUsingBackwardScan(const BasicBlock *BB,
+                                        FunctionVarLocsBuilder &FnVarLocs) {
+  bool Changed = false;
+  SmallDenseSet<DebugVariable> VariableSet;
+
+  // Scan over the entire block, not just over the instructions mapped by
+  // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
+  // instructions.
+  for (const Instruction &I : reverse(*BB)) {
+    if (!isa<DbgVariableIntrinsic>(I)) {
+      // Sequence of consecutive defs ended. Clear map for the next one.
+      VariableSet.clear();
+    }
+
+    // Get the location defs that start just before this instruction.
+    const auto *Locs = FnVarLocs.getWedge(&I);
+    if (!Locs)
+      continue;
+
+    NumWedgesScanned++;
+    bool ChangedThisWedge = false;
+    // The new pruned set of defs, reversed because we're scanning backwards.
+    SmallVector<VarLocInfo> NewDefsReversed;
+
+    // Iterate over the existing defs in reverse.
+    for (auto RIt = Locs->rbegin(), REnd = Locs->rend(); RIt != REnd; ++RIt) {
+      NumDefsScanned++;
+      const DebugVariable &Key = FnVarLocs.getVariable(RIt->VariableID);
+      bool FirstDefOfFragment = VariableSet.insert(Key).second;
+
+      // If the same variable fragment is described more than once it is enough
+      // to keep the last one (i.e. the first found in this reverse iteration).
+      if (FirstDefOfFragment) {
+        // New def found: keep it.
+        NewDefsReversed.push_back(*RIt);
+      } else {
+        // Redundant def found: throw it away. Since the wedge of defs is being
+        // rebuilt, doing nothing is the same as deleting an entry.
+        ChangedThisWedge = true;
+        NumDefsRemoved++;
+      }
+      continue;
+    }
+
+    // Un-reverse the defs and replace the wedge with the pruned version.
+    if (ChangedThisWedge) {
+      std::reverse(NewDefsReversed.begin(), NewDefsReversed.end());
+      FnVarLocs.setWedge(&I, std::move(NewDefsReversed));
+      NumWedgesChanged++;
+      Changed = true;
+    }
+  }
+
+  return Changed;
+}
+
+/// Remove redundant location defs using a forward scan. This can remove a
+/// location definition that is redundant due to indicating that a variable has
+/// the same value as is already being indicated by an earlier def.
+///
+/// This implements removeRedundantDbgInstrsUsingForwardScan from
+/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
+/// FunctionVarLocsBuilder instead of with intrinsics
+static bool
+removeRedundantDbgLocsUsingForwardScan(const BasicBlock *BB,
+                                       FunctionVarLocsBuilder &FnVarLocs) {
+  bool Changed = false;
+  DenseMap<DebugVariable, std::pair<Value *, DIExpression *>> VariableMap;
+
+  // Scan over the entire block, not just over the instructions mapped by
+  // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
+  // instructions.
+  for (const Instruction &I : *BB) {
+    // Get the defs that come just before this instruction.
+    const auto *Locs = FnVarLocs.getWedge(&I);
+    if (!Locs)
+      continue;
+
+    NumWedgesScanned++;
+    bool ChangedThisWedge = false;
+    // The new pruned set of defs.
+    SmallVector<VarLocInfo> NewDefs;
+
+    // Iterate over the existing defs.
+    for (const VarLocInfo &Loc : *Locs) {
+      NumDefsScanned++;
+      DebugVariable Key(FnVarLocs.getVariable(Loc.VariableID).getVariable(),
+                        NoneType(), Loc.DL.getInlinedAt());
+      auto VMI = VariableMap.find(Key);
+
+      // Update the map if we found a new value/expression describing the
+      // variable, or if the variable wasn't mapped already.
+      if (VMI == VariableMap.end() || VMI->second.first != Loc.V ||
+          VMI->second.second != Loc.Expr) {
+        VariableMap[Key] = {Loc.V, Loc.Expr};
+        NewDefs.push_back(Loc);
+        continue;
+      }
+
+      // Did not insert this Loc, which is the same as removing it.
+      ChangedThisWedge = true;
+      NumDefsRemoved++;
+    }
+
+    // Replace the existing wedge with the pruned version.
+    if (ChangedThisWedge) {
+      FnVarLocs.setWedge(&I, std::move(NewDefs));
+      NumWedgesChanged++;
+      Changed = true;
+    }
+  }
+
+  return Changed;
+}
+
+static bool
+removeUndefDbgLocsFromEntryBlock(const BasicBlock *BB,
+                                 FunctionVarLocsBuilder &FnVarLocs) {
+  assert(BB->isEntryBlock());
+  // Do extra work to ensure that we remove semantically unimportant undefs.
+  //
+  // This is to work around the fact that SelectionDAG will hoist dbg.values
+  // using argument values to the top of the entry block. That can move arg
+  // dbg.values before undef and constant dbg.values which they previously
+  // followed. The easiest thing to do is to just try to feed SelectionDAG
+  // input it's happy with.
+  //
+  // Map of {Variable x: Fragments y} where the fragments y of variable x have
+  // have at least one non-undef location defined already. Don't use directly,
+  // instead call DefineBits and HasDefinedBits.
+  SmallDenseMap<DebugAggregate, SmallDenseSet<DIExpression::FragmentInfo>>
+      VarsWithDef;
+  // Specify that V (a fragment of A) has a non-undef location.
+  auto DefineBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) {
+    VarsWithDef[A].insert(V.getFragmentOrDefault());
+  };
+  // Return true if a non-undef location has been defined for V (a fragment of
+  // A). Doesn't imply that the location is currently non-undef, just that a
+  // non-undef location has been seen previously.
+  auto HasDefinedBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) {
+    auto FragsIt = VarsWithDef.find(A);
+    if (FragsIt == VarsWithDef.end())
+      return false;
+    return llvm::any_of(FragsIt->second, [V](auto Frag) {
+      return DIExpression::fragmentsOverlap(Frag, V.getFragmentOrDefault());
+    });
+  };
+
+  bool Changed = false;
+  DenseMap<DebugVariable, std::pair<Value *, DIExpression *>> VariableMap;
+
+  // Scan over the entire block, not just over the instructions mapped by
+  // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
+  // instructions.
+  for (const Instruction &I : *BB) {
+    // Get the defs that come just before this instruction.
+    const auto *Locs = FnVarLocs.getWedge(&I);
+    if (!Locs)
+      continue;
+
+    NumWedgesScanned++;
+    bool ChangedThisWedge = false;
+    // The new pruned set of defs.
+    SmallVector<VarLocInfo> NewDefs;
+
+    // Iterate over the existing defs.
+    for (const VarLocInfo &Loc : *Locs) {
+      NumDefsScanned++;
+      DebugAggregate Aggr{FnVarLocs.getVariable(Loc.VariableID).getVariable(),
+                          Loc.DL.getInlinedAt()};
+      DebugVariable Var = FnVarLocs.getVariable(Loc.VariableID);
+
+      // Remove undef entries that are encountered before any non-undef
+      // intrinsics from the entry block.
+      if (isa<UndefValue>(Loc.V) && !HasDefinedBits(Aggr, Var)) {
+        // Did not insert this Loc, which is the same as removing it.
+        NumDefsRemoved++;
+        ChangedThisWedge = true;
+        continue;
+      }
+
+      DefineBits(Aggr, Var);
+      NewDefs.push_back(Loc);
+    }
+
+    // Replace the existing wedge with the pruned version.
+    if (ChangedThisWedge) {
+      FnVarLocs.setWedge(&I, std::move(NewDefs));
+      NumWedgesChanged++;
+      Changed = true;
+    }
+  }
+
+  return Changed;
+}
+
+static bool removeRedundantDbgLocs(const BasicBlock *BB,
+                                   FunctionVarLocsBuilder &FnVarLocs) {
+  bool MadeChanges = false;
+  MadeChanges |= removeRedundantDbgLocsUsingBackwardScan(BB, FnVarLocs);
+  if (BB->isEntryBlock())
+    MadeChanges |= removeUndefDbgLocsFromEntryBlock(BB, FnVarLocs);
+  MadeChanges |= removeRedundantDbgLocsUsingForwardScan(BB, FnVarLocs);
+
+  if (MadeChanges)
+    LLVM_DEBUG(dbgs() << "Removed redundant dbg locs from: " << BB->getName()
+                      << "\n");
+  return MadeChanges;
+}
+
 static DenseSet<DebugAggregate> findVarsWithStackSlot(Function &Fn) {
   DenseSet<DebugAggregate> Result;
   for (auto &BB : Fn) {
     for (auto &I : BB) {
       // Any variable linked to an instruction is considered
       // interesting. Ideally we only need to check Allocas, however, a
       // DIAssignID might get dropped from an alloca but not stores. In that
       // case, we need to consider the variable interesting for NFC behaviour
       // with this change. TODO: Consider only looking at allocas.
       for (DbgAssignIntrinsic *DAI : at::getAssignmentMarkers(&I)) {
         Result.insert({DAI->getVariable(), DAI->getDebugLoc().getInlinedAt()});
       }
     }
   }
   return Result;
 }
 
 static void analyzeFunction(Function &Fn, const DataLayout &Layout,
                             FunctionVarLocsBuilder *FnVarLocs) {
   // The analysis will generate location definitions for all variables, but we
   // only need to perform a dataflow on the set of variables which have a stack
   // slot. Find those now.
   DenseSet<DebugAggregate> VarsWithStackSlot = findVarsWithStackSlot(Fn);
+
+  bool Changed = false;
+
   AssignmentTrackingLowering Pass(Fn, Layout, &VarsWithStackSlot);
-  Pass.run(FnVarLocs);
+  Changed = Pass.run(FnVarLocs);
+
+  if (Changed) {
+    // Remove redundant entries. As well as reducing memory consumption and
+    // avoiding waiting cycles later by burning some now, this has another
+    // important job. That is to work around some SelectionDAG quirks. See
+    // removeRedundantDbgLocsUsingForwardScan comments for more info on that.
+    for (auto &BB : Fn)
+      removeRedundantDbgLocs(&BB, *FnVarLocs);
+  }
 }
 
 bool AssignmentTrackingAnalysis::runOnFunction(Function &F) {
   LLVM_DEBUG(dbgs() << "AssignmentTrackingAnalysis run on " << F.getName()
                     << "\n");
   auto DL = std::make_unique<DataLayout>(F.getParent());
 
   // Clear previous results.