Add option to enable/disable LiveDebugValues pass.

[tvvikram]

Summary

It is 'on' by default.

[kcc]

please make it false by default since the phase is not really working (compilation times out)

[echristo]

Can we actually add an equivalent clang debug tuning option called "-fvar-tracking" similar to the gcc one here as well?

-eric

[tvvikram]

In D15945#321093, @kcc wrote:

please make it false by default since the phase is not really working (compilation times out)

I kept it 'on' as it works in most of the cases. I will try to submit a patch by EoD that fixes the issue.

[tvvikram]

I noticed with a.ll, the test case from https://llvm.org/bugs/show_bug.cgi?id=26055, that there are too many DEBUG_VALUE instructions getting inserted. Statistics showed >6L instructions getting inserted:
616584 live-debug-values - Number of DBG_VALUE instructions inserted

One reason is the presence of too many basic blocks within the function. With so many blocks, the convergence takes really long time. I thought of ignoring functions with more basic blocks. But instead, I have added a simple heuristic to stop convergence after certain number of iterations. Currently the max iterations is arbitrary (chosen to be 10).

[tvvikram]

In D15945#321100, @echristo wrote:

Can we actually add an equivalent clang debug tuning option called "-fvar-tracking" similar to the gcc one here as well?

-eric

+1!

[samsonov]

Note that test case in https://llvm.org/bugs/show_bug.cgi?id=26055 is produced from auto-generated code, so its BB structure should be very regular, and you can come up with rather precise estimate of how many passes you will need to converge. Does current bound (10) make compile time reasonable for that case?

-fvar-tracking: yes, please! It would be nice to be able to toggle this pass from frontend.

I have a number of comments regarding the code as well, but I will rather see quick fixes (or revert) committed ASAP: this is hurting us pretty badly, as we can't build several projects with optimization and debug info enabled.

[tvvikram]

In D15945#321360, @samsonov wrote:

Note that test case in https://llvm.org/bugs/show_bug.cgi?id=26055 is produced from auto-generated code, so its BB structure should be very regular, and you can come up with rather precise estimate of how many passes you will need to converge. Does current bound (10) make compile time reasonable for that case?

Yes. The compile time is now almost equal (~0.8 sec on my machine).

[• dberlin]

Okay, i'm confused.

(Note: I helped write var-tracking for GCC).

Let's ignore the inefficient data structure usage here (ie appending lists instead of using constant time splices, using lists instead of hash maps, etc).

The reason your convergence is slow, is, AFAICT, because you are using a random basic block order for processing the dataflow problem.

You should be walking blocks in reverse postorder, which is the optimal order for this problem, and will significantly speed up convergence.

I'm also going to take a pass at writing comments on the algorithmic issues here.

[• dberlin]

lib/CodeGen/LiveDebugValues.cpp

299

Can you please explain, precisely, what this accomplishes?
Besides badly needing a comment explaining what is going on,
it is really complicated, and if i'm reading it right, really slow (N^2 or worse) for the datastructures you have here.

323

This looks like another N^2 part.
You either should be keeping these things in a hash map or at the very least, and ordered set so that you can do this fast.

390

Please use a SmallPtrSet<BasicBlock *, 16> Visited to to track whether you visited a block or not, don't go searching through the worklist.

[• dberlin]

lib/CodeGen/LiveDebugValues.cpp

83

There is no reason for this to be a global variable.
Please just make your transfer functions return bools and | them together.

85

Ditto.

374

You really need to be iterating in reverse postorder.

One trivial way to do that is to use the ordering and two worklists.

std::priority_queue <unsigned int> worklist;
std::priority_queue <unsigned int> pending;

DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
DenseMap<unsigned int, MachineBasicBlock *> OrderToBB

ReversePostOrderTraversal<MachineBasicBlock *> RPOT(entryblock);
unsigned int RPONumber = 0;
for (auto I = RPOT.begin(), auto E = RPOT.end(); I != E; ++I) {
  BBToOrder[*I] = RPONumber;
  OrderToBB[RPONumber] = *I;
  worklist.push_back(RPONumber);
  ++RPONumber;
}


while (changed) {
<go through worklist, use OrderToBB[I] to get BB from worklist> 
put necessary successors on pending using BBToOrder.
std::swap(worklist, pending)
Clear pending.
}

[tvvikram]

Thanks @dberlin for the suggestions and working on it (http://reviews.llvm.org/D16039)

lib/CodeGen/LiveDebugValues.cpp

 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <deque>
 #include <list>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "live-debug-values"
 
+static cl::opt<bool>
+EnableLDV("live-debug-values", cl::init(true),
+          cl::desc("Enable the live debug values pass"), cl::Hidden);
+
 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
 
 namespace {
 
 class LiveDebugValues : public MachineFunctionPass {
 
 private:
   const TargetRegisterInfo *TRI;
struct VarLoc {
     VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
 
     bool operator==(const VarLoc &V) const;
   };
 
   typedef std::list<VarLoc> VarLocList;
   typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB;
 
   bool OLChanged; // OutgoingLocs got changed for this bb.
   bool MBBJoined; // The MBB was joined.
 
   void transferDebugValue(MachineInstr &MI, VarLocList &OpenRanges);
   void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges);
   void transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges,
                               VarLocInMBB &OutLocs);
   void transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs);
 
   void join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs);
 
for (auto p : MBB.predecessors()) {
     // Just copy over the Out locs to incoming locs for the first predecessor.
     if (p == *MBB.pred_begin()) {
       InLocsT = OL->second;
       continue;
     }
 
     // Join with this predecessor.
     VarLocList &VLL = OL->second;
     InLocsT.erase(std::remove_if(InLocsT.begin(), InLocsT.end(),
                                  [&](VarLoc &ILT) {
                                    return (std::find_if(VLL.begin(), VLL.end(),
                                                         [&](const VarLoc &V) {
                                                           return (ILT == V);
                                                         }) == VLL.end());
                                  }),
                   InLocsT.end());
   }
 
   if (InLocsT.empty())
     return;
 
   if (InLocs.find(&MBB) == InLocs.end()) {
     // Create space for new Incoming locs entries.
     VarLocList VLL;
     InLocs.insert(std::make_pair(&MBB, std::move(VLL)));
   }
   auto IL = InLocs.find(&MBB);
   assert(IL != InLocs.end());
   VarLocList &ILL = IL->second;
 
   // Insert DBG_VALUE instructions, if not already inserted.
   for (auto ILT : InLocsT) {
     if (std::find_if(ILL.begin(), ILL.end(), [&](const VarLoc &I) {
           return (ILT == I);
         }) == ILL.end()) {
       // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
       // new range is started for the var from the mbb's beginning by inserting
       // a new DBG_VALUE. transfer() will end this range however appropriate.
       const MachineInstr *DMI = ILT.MI;
       MachineInstr *MI =
           BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 
   // Construct a worklist of MBBs.
   for (auto &MBB : MF)
     BBWorklist.push_back(&MBB);
 
   // Perform join() and transfer() using the worklist until the ranges converge
   // Ranges have converged when the worklist is empty.
   while (!BBWorklist.empty()) {
     MachineBasicBlock *MBB = BBWorklist.front();
     BBWorklist.pop_front();
 
     join(*MBB, OutLocs, InLocs);
 
     if (MBBJoined) {
       Changed = true;
       for (auto &MI : *MBB)
         transfer(MI, OpenRanges, OutLocs);
       DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
       DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
 
       if (OLChanged) {
         OLChanged = false;
         for (auto s : MBB->successors())
           if (std::find(BBWorklist.begin(), BBWorklist.end(), s) ==
               BBWorklist.end()) // add if not already present.
             BBWorklist.push_back(s);
       }
     }
   }
   DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
   DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
   return Changed;
 }
 
 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
+  if (!EnableLDV)
+    return false;
+
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
 
   bool Changed = false;
 
   Changed |= ExtendRanges(MF);
 
   return Changed;
 }