vendor/llvm/llvm-trunk-r338150

1 files changed, 181 insertions, 80 deletions

diff --git a/lib/CodeGen/LiveDebugValues.cpp b/lib/CodeGen/LiveDebugValues.cpp
index 19ec281079cb..fea83e92de8f 100644
--- a/lib/CodeGen/LiveDebugValues.cpp
+++ b/lib/CodeGen/LiveDebugValues.cpp
@@ -40,6 +40,8 @@
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
+#include "llvm/CodeGen/RegisterScavenging.h"
+#include "llvm/Config/llvm-config.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Function.h"
@@ -64,7 +66,7 @@ using namespace llvm;
 
 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
 
-// \brief If @MI is a DBG_VALUE with debug value described by a defined
+// If @MI is a DBG_VALUE with debug value described by a defined
 // register, returns the number of this register. In the other case, returns 0.
 static unsigned isDbgValueDescribedByReg(const MachineInstr &MI) {
   assert(MI.isDebugValue() && "expected a DBG_VALUE");
@@ -81,6 +83,7 @@ private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
+  BitVector CalleeSavedRegs;
   LexicalScopes LS;
 
   /// Keeps track of lexical scopes associated with a user value's source
@@ -178,11 +181,11 @@ private:
   using VarLocMap = UniqueVector<VarLoc>;
   using VarLocSet = SparseBitVector<>;
   using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
-  struct SpillDebugPair {
-    MachineInstr *SpillInst;
+  struct TransferDebugPair {
+    MachineInstr *TransferInst;
     MachineInstr *DebugInst;
   };
-  using SpillMap = SmallVector<SpillDebugPair, 4>;
+  using TransferMap = SmallVector<TransferDebugPair, 4>;
 
   /// This holds the working set of currently open ranges. For fast
   /// access, this is done both as a set of VarLocIDs, and a map of
@@ -235,18 +238,23 @@ private:
   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF,
                           unsigned &Reg);
   int extractSpillBaseRegAndOffset(const MachineInstr &MI, unsigned &Reg);
+  void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                               TransferMap &Transfers, VarLocMap &VarLocIDs,
+                               unsigned OldVarID, unsigned NewReg = 0);
 
   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                           VarLocMap &VarLocIDs);
   void transferSpillInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                         VarLocMap &VarLocIDs, SpillMap &Spills);
+                         VarLocMap &VarLocIDs, TransferMap &Transfers);
+  void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                            VarLocMap &VarLocIDs, TransferMap &Transfers);
   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
                            const VarLocMap &VarLocIDs);
   bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
                               VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
-  bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, SpillMap &Spills,
-                bool transferSpills);
+  bool process(MachineInstr &MI, OpenRangesSet &OpenRanges,
+               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
+               TransferMap &Transfers, bool transferChanges);
 
   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
             const VarLocMap &VarLocIDs,
@@ -369,6 +377,54 @@ void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
   }
 }
 
+/// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
+/// with \p OldVarID should be deleted form \p OpenRanges and replaced with
+/// new VarLoc. If \p NewReg is different than default zero value then the
+/// new location will be register location created by the copy like instruction,
+/// otherwise it is variable's location on the stack.
+void LiveDebugValues::insertTransferDebugPair(
+    MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
+    VarLocMap &VarLocIDs, unsigned OldVarID, unsigned NewReg) {
+  const MachineInstr *DMI = &VarLocIDs[OldVarID].MI;
+  MachineFunction *MF = MI.getParent()->getParent();
+  MachineInstr *NewDMI;
+  if (NewReg) {
+    // Create a DBG_VALUE instruction to describe the Var in its new
+    // register location.
+    NewDMI = BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(),
+                     DMI->isIndirectDebugValue(), NewReg,
+                     DMI->getDebugVariable(), DMI->getDebugExpression());
+    if (DMI->isIndirectDebugValue())
+      NewDMI->getOperand(1).setImm(DMI->getOperand(1).getImm());
+    LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register copy: ";
+               NewDMI->print(dbgs(), false, false, false, TII));
+  } else {
+    // Create a DBG_VALUE instruction to describe the Var in its spilled
+    // location.
+    unsigned SpillBase;
+    int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase);
+    auto *SpillExpr = DIExpression::prepend(DMI->getDebugExpression(),
+                                            DIExpression::NoDeref, SpillOffset);
+    NewDMI = BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase,
+                     DMI->getDebugVariable(), SpillExpr);
+    LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
+               NewDMI->print(dbgs(), false, false, false, TII));
+  }
+
+  // The newly created DBG_VALUE instruction NewDMI must be inserted after
+  // MI. Keep track of the pairing.
+  TransferDebugPair MIP = {&MI, NewDMI};
+  Transfers.push_back(MIP);
+
+  // End all previous ranges of Var.
+  OpenRanges.erase(VarLocIDs[OldVarID].Var);
+
+  // Add the VarLoc to OpenRanges.
+  VarLoc VL(*NewDMI, LS);
+  unsigned LocID = VarLocIDs.insert(VL);
+  OpenRanges.insert(LocID, VL.Var);
+}
+
 /// A definition of a register may mark the end of a range.
 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
                                           OpenRangesSet &OpenRanges,
@@ -426,28 +482,51 @@ bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
         FrameInfo.isSpillSlotObjectIndex(FI)))
     return false;
 
-  // In a spill instruction generated by the InlineSpiller the spilled register
-  // has its kill flag set. Return false if we don't find such a register.
-  Reg = 0;
+  auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
+    if (!MO.isReg() || !MO.isUse()) {
+      Reg = 0;
+      return false;
+    }
+    Reg = MO.getReg();
+    return MO.isKill();
+  };
+
   for (const MachineOperand &MO : MI.operands()) {
-    if (MO.isReg() && MO.isUse() && MO.isKill()) {
-      Reg = MO.getReg();
-      break;
+    // In a spill instruction generated by the InlineSpiller the spilled
+    // register has its kill flag set.
+    if (isKilledReg(MO, Reg))
+      return true;
+    if (Reg != 0) {
+      // Check whether next instruction kills the spilled register.
+      // FIXME: Current solution does not cover search for killed register in
+      // bundles and instructions further down the chain.
+      auto NextI = std::next(MI.getIterator());
+      // Skip next instruction that points to basic block end iterator.
+      if (MI.getParent()->end() == NextI)
+        continue;
+      unsigned RegNext;
+      for (const MachineOperand &MONext : NextI->operands()) {
+        // Return true if we came across the register from the
+        // previous spill instruction that is killed in NextI.
+        if (isKilledReg(MONext, RegNext) && RegNext == Reg)
+          return true;
+      }
     }
   }
-  return Reg != 0;
+  // Return false if we didn't find spilled register.
+  return false;
 }
 
 /// A spilled register may indicate that we have to end the current range of
 /// a variable and create a new one for the spill location.
-/// We don't want to insert any instructions in transfer(), so we just create
-/// the DBG_VALUE witout inserting it and keep track of it in @Spills.
+/// We don't want to insert any instructions in process(), so we just create
+/// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
 /// It will be inserted into the BB when we're done iterating over the
 /// instructions.
 void LiveDebugValues::transferSpillInst(MachineInstr &MI,
                                         OpenRangesSet &OpenRanges,
                                         VarLocMap &VarLocIDs,
-                                        SpillMap &Spills) {
+                                        TransferMap &Transfers) {
   unsigned Reg;
   MachineFunction *MF = MI.getMF();
   if (!isSpillInstruction(MI, MF, Reg))
@@ -456,35 +535,49 @@ void LiveDebugValues::transferSpillInst(MachineInstr &MI,
   // Check if the register is the location of a debug value.
   for (unsigned ID : OpenRanges.getVarLocs()) {
     if (VarLocIDs[ID].isDescribedByReg() == Reg) {
-      DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
-                   << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
-
-      // Create a DBG_VALUE instruction to describe the Var in its spilled
-      // location, but don't insert it yet to avoid invalidating the
-      // iterator in our caller.
-      unsigned SpillBase;
-      int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase);
-      const MachineInstr *DMI = &VarLocIDs[ID].MI;
-      auto *SpillExpr = DIExpression::prepend(
-          DMI->getDebugExpression(), DIExpression::NoDeref, SpillOffset);
-      MachineInstr *SpDMI =
-          BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase,
-                  DMI->getDebugVariable(), SpillExpr);
-      DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
-            SpDMI->print(dbgs(), false, TII));
-
-      // The newly created DBG_VALUE instruction SpDMI must be inserted after
-      // MI. Keep track of the pairing.
-      SpillDebugPair MIP = {&MI, SpDMI};
-      Spills.push_back(MIP);
-
-      // End all previous ranges of Var.
-      OpenRanges.erase(VarLocIDs[ID].Var);
-
-      // Add the VarLoc to OpenRanges.
-      VarLoc VL(*SpDMI, LS);
-      unsigned SpillLocID = VarLocIDs.insert(VL);
-      OpenRanges.insert(SpillLocID, VL.Var);
+      LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
+                        << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
+      insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID);
+      return;
+    }
+  }
+}
+
+/// If \p MI is a register copy instruction, that copies a previously tracked
+/// value from one register to another register that is callee saved, we
+/// create new DBG_VALUE instruction  described with copy destination register.
+void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
+                                           OpenRangesSet &OpenRanges,
+                                           VarLocMap &VarLocIDs,
+                                           TransferMap &Transfers) {
+  const MachineOperand *SrcRegOp, *DestRegOp;
+
+  if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() ||
+      !DestRegOp->isDef())
+    return;
+
+  auto isCalleSavedReg = [&](unsigned Reg) {
+    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
+      if (CalleeSavedRegs.test(*RAI))
+        return true;
+    return false;
+  };
+
+  unsigned SrcReg = SrcRegOp->getReg();
+  unsigned DestReg = DestRegOp->getReg();
+
+  // We want to recognize instructions where destination register is callee
+  // saved register. If register that could be clobbered by the call is
+  // included, there would be a great chance that it is going to be clobbered
+  // soon. It is more likely that previous register location, which is callee
+  // saved, is going to stay unclobbered longer, even if it is killed.
+  if (!isCalleSavedReg(DestReg))
+    return;
+
+  for (unsigned ID : OpenRanges.getVarLocs()) {
+    if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
+      insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
+                              DestReg);
       return;
     }
   }
@@ -497,16 +590,18 @@ bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
                                              const VarLocMap &VarLocIDs) {
   bool Changed = false;
   const MachineBasicBlock *CurMBB = MI.getParent();
-  if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
+  if (!(MI.isTerminator() || (&MI == &CurMBB->back())))
     return false;
 
   if (OpenRanges.empty())
     return false;
 
-  DEBUG(for (unsigned ID : OpenRanges.getVarLocs()) {
-          // Copy OpenRanges to OutLocs, if not already present.
-          dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
-        });
+  LLVM_DEBUG(for (unsigned ID
+                  : OpenRanges.getVarLocs()) {
+    // Copy OpenRanges to OutLocs, if not already present.
+    dbgs() << "Add to OutLocs: ";
+    VarLocIDs[ID].dump();
+  });
   VarLocSet &VLS = OutLocs[CurMBB];
   Changed = VLS |= OpenRanges.getVarLocs();
   OpenRanges.clear();
@@ -514,14 +609,16 @@ bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
 }
 
 /// This routine creates OpenRanges and OutLocs.
-bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
-                               SpillMap &Spills, bool transferSpills) {
+bool LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                              VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
+                              TransferMap &Transfers, bool transferChanges) {
   bool Changed = false;
   transferDebugValue(MI, OpenRanges, VarLocIDs);
   transferRegisterDef(MI, OpenRanges, VarLocIDs);
-  if (transferSpills)
-    transferSpillInst(MI, OpenRanges, VarLocIDs, Spills);
+  if (transferChanges) {
+    transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
+    transferSpillInst(MI, OpenRanges, VarLocIDs, Transfers);
+  }
   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
   return Changed;
 }
@@ -532,7 +629,7 @@ bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
                            VarLocInMBB &InLocs, const VarLocMap &VarLocIDs,
                            SmallPtrSet<const MachineBasicBlock *, 16> &Visited) {
-  DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
+  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
   bool Changed = false;
 
   VarLocSet InLocsT; // Temporary incoming locations.
@@ -583,7 +680,7 @@ bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
   for (auto ID : Diff) {
     // 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.
+    // a new DBG_VALUE. process() will end this range however appropriate.
     const VarLoc &DiffIt = VarLocIDs[ID];
     const MachineInstr *DMI = &DiffIt.MI;
     MachineInstr *MI =
@@ -592,7 +689,7 @@ bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
                 DMI->getDebugVariable(), DMI->getDebugExpression());
     if (DMI->isIndirectDebugValue())
       MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
-    DEBUG(dbgs() << "Inserted: "; MI->dump(););
+    LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
     ILS.set(ID);
     ++NumInserted;
     Changed = true;
@@ -603,7 +700,7 @@ bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
-  DEBUG(dbgs() << "\nDebug Range Extension\n");
+  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
 
   bool Changed = false;
   bool OLChanged = false;
@@ -613,7 +710,7 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
   VarLocInMBB OutLocs;      // Ranges that exist beyond bb.
   VarLocInMBB InLocs;       // Ranges that are incoming after joining.
-  SpillMap Spills;          // DBG_VALUEs associated with spills.
+  TransferMap Transfers;    // DBG_VALUEs associated with spills.
 
   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
@@ -624,6 +721,8 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
                       std::greater<unsigned int>>
       Pending;
 
+  enum : bool { dontTransferChanges = false, transferChanges = true };
+
   // Initialize every mbb with OutLocs.
   // We are not looking at any spill instructions during the initial pass
   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
@@ -631,11 +730,11 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   // within the BB in which the spill occurs.
   for (auto &MBB : MF)
     for (auto &MI : MBB)
-      transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
-               /*transferSpills=*/false);
+      process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
+              dontTransferChanges);
 
-  DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization",
-                         dbgs()));
+  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
+                              "OutLocs after initialization", dbgs()));
 
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   unsigned int RPONumber = 0;
@@ -646,7 +745,7 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     ++RPONumber;
   }
   // This is a standard "union of predecessor outs" dataflow problem.
-  // To solve it, we perform join() and transfer() using the two worklist method
+  // To solve it, we perform join() and process() using the two worklist method
   // until the ranges converge.
   // Ranges have converged when both worklists are empty.
   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
@@ -655,7 +754,7 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     // thing twice.  We could avoid this with a custom priority queue, but this
     // is probably not worth it.
     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
-    DEBUG(dbgs() << "Processing Worklist\n");
+    LLVM_DEBUG(dbgs() << "Processing Worklist\n");
     while (!Worklist.empty()) {
       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
       Worklist.pop();
@@ -668,19 +767,19 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
         // examine spill instructions to see whether they spill registers that
         // correspond to user variables.
         for (auto &MI : *MBB)
-          OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
-                                /*transferSpills=*/true);
+          OLChanged |= process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
+                               transferChanges);
 
         // Add any DBG_VALUE instructions necessitated by spills.
-        for (auto &SP : Spills)
-          MBB->insertAfter(MachineBasicBlock::iterator(*SP.SpillInst),
-                           SP.DebugInst);
-        Spills.clear();
+        for (auto &TR : Transfers)
+          MBB->insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
+                           TR.DebugInst);
+        Transfers.clear();
 
-        DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
-                               "OutLocs after propagating", dbgs()));
-        DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
-                               "InLocs after propagating", dbgs()));
+        LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
+                                    "OutLocs after propagating", dbgs()));
+        LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
+                                    "InLocs after propagating", dbgs()));
 
         if (OLChanged) {
           OLChanged = false;
@@ -697,8 +796,8 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     assert(Pending.empty() && "Pending should be empty");
   }
 
-  DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
-  DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
+  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
+  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
   return Changed;
 }
 
@@ -715,6 +814,8 @@ bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
   TFI = MF.getSubtarget().getFrameLowering();
+  TFI->determineCalleeSaves(MF, CalleeSavedRegs,
+                            make_unique<RegScavenger>().get());
   LS.initialize(MF);
 
   bool Changed = ExtendRanges(MF);