LiveDebugVariables.cpp

//===- LiveDebugVariables.cpp - Tracking debug info variables -------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the LiveDebugVariables analysis.
//
// Remove all DBG_VALUE instructions referencing virtual registers and replace
// them with a data structure tracking where live user variables are kept - in a
// virtual register or in a stack slot.
//
// Allow the data structure to be updated during register allocation when values
// are moved between registers and stack slots. Finally emit new DBG_VALUE
// instructions after register allocation is complete.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "livedebug"
#include "LiveDebugVariables.h"
#include "VirtRegMap.h"
#include "llvm/Constants.h"
#include "llvm/Metadata.h"
#include "llvm/Value.h"
#include "llvm/Analysis/DebugInfo.h"
#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LexicalScopes.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"

using namespace llvm;

static cl::opt<bool>
EnableLDV("live-debug-variables", cl::init(true),
          cl::desc("Enable the live debug variables pass"), cl::Hidden);

STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted");
char LiveDebugVariables::ID = 0;

INITIALIZE_PASS_BEGIN(LiveDebugVariables, "livedebugvars",
                "Debug Variable Analysis", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_END(LiveDebugVariables, "livedebugvars",
                "Debug Variable Analysis", false, false)

void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<MachineDominatorTree>();
  AU.addRequiredTransitive<LiveIntervals>();
  AU.setPreservesAll();
  MachineFunctionPass::getAnalysisUsage(AU);
}

LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID), pImpl(0) {
  initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
}

/// LocMap - Map of where a user value is live, and its location.
typedef IntervalMap<SlotIndex, unsigned, 4> LocMap;

namespace {
/// UserValueScopes - Keeps track of lexical scopes associated with an
/// user value's source location.
class UserValueScopes {
  DebugLoc DL;
  LexicalScopes &LS;
  SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;

public:
  UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(D), LS(L) {}

  /// dominates - Return true if current scope dominates at least one machine
  /// instruction in a given machine basic block.
  bool dominates(MachineBasicBlock *MBB) {
    if (LBlocks.empty())
      LS.getMachineBasicBlocks(DL, LBlocks);
    if (LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB))
      return true;
    return false;
  }
};
} // end anonymous namespace

/// UserValue - A user value is a part of a debug info user variable.
///
/// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
/// holds part of a user variable. The part is identified by a byte offset.
///
/// UserValues are grouped into equivalence classes for easier searching. Two
/// user values are related if they refer to the same variable, or if they are
/// held by the same virtual register. The equivalence class is the transitive
/// closure of that relation.
namespace {
class LDVImpl;
class UserValue {
  const MDNode *variable; ///< The debug info variable we are part of.
  unsigned offset;        ///< Byte offset into variable.
  DebugLoc dl;            ///< The debug location for the variable. This is
                          ///< used by dwarf writer to find lexical scope.
  UserValue *leader;      ///< Equivalence class leader.
  UserValue *next;        ///< Next value in equivalence class, or null.

  /// Numbered locations referenced by locmap.
  SmallVector<MachineOperand, 4> locations;

  /// Map of slot indices where this value is live.
  LocMap locInts;

  /// coalesceLocation - After LocNo was changed, check if it has become
  /// identical to another location, and coalesce them. This may cause LocNo or
  /// a later location to be erased, but no earlier location will be erased.
  void coalesceLocation(unsigned LocNo);

  /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
  void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo,
                        LiveIntervals &LIS, const TargetInstrInfo &TII);

  /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
  /// is live. Returns true if any changes were made.
  bool splitLocation(unsigned OldLocNo, ArrayRef<LiveInterval*> NewRegs);

public:
  /// UserValue - Create a new UserValue.
  UserValue(const MDNode *var, unsigned o, DebugLoc L,
            LocMap::Allocator &alloc)
    : variable(var), offset(o), dl(L), leader(this), next(0), locInts(alloc)
  {}

  /// getLeader - Get the leader of this value's equivalence class.
  UserValue *getLeader() {
    UserValue *l = leader;
    while (l != l->leader)
      l = l->leader;
    return leader = l;
  }

  /// getNext - Return the next UserValue in the equivalence class.
  UserValue *getNext() const { return next; }

  /// match - Does this UserValue match the parameters?
  bool match(const MDNode *Var, unsigned Offset) const {
    return Var == variable && Offset == offset;
  }

  /// merge - Merge equivalence classes.
  static UserValue *merge(UserValue *L1, UserValue *L2) {
    L2 = L2->getLeader();
    if (!L1)
      return L2;
    L1 = L1->getLeader();
    if (L1 == L2)
      return L1;
    // Splice L2 before L1's members.
    UserValue *End = L2;
    while (End->next)
      End->leader = L1, End = End->next;
    End->leader = L1;
    End->next = L1->next;
    L1->next = L2;
    return L1;
  }

  /// getLocationNo - Return the location number that matches Loc.
  unsigned getLocationNo(const MachineOperand &LocMO) {
    if (LocMO.isReg()) {
      if (LocMO.getReg() == 0)
        return ~0u;
      // For register locations we dont care about use/def and other flags.
      for (unsigned i = 0, e = locations.size(); i != e; ++i)
        if (locations[i].isReg() &&
            locations[i].getReg() == LocMO.getReg() &&
            locations[i].getSubReg() == LocMO.getSubReg())
          return i;
    } else
      for (unsigned i = 0, e = locations.size(); i != e; ++i)
        if (LocMO.isIdenticalTo(locations[i]))
          return i;
    locations.push_back(LocMO);
    // We are storing a MachineOperand outside a MachineInstr.
    locations.back().clearParent();
    // Don't store def operands.
    if (locations.back().isReg())
      locations.back().setIsUse();
    return locations.size() - 1;
  }

  /// mapVirtRegs - Ensure that all virtual register locations are mapped.