path: root/lib/CodeGen/AggressiveAntiDepBreaker.cpp

//===----- AggressiveAntiDepBreaker.cpp - Anti-dep breaker ----------------===//
//
//                     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 AggressiveAntiDepBreaker class, which
// implements register anti-dependence breaking during post-RA
// scheduling. It attempts to break all anti-dependencies within a
// block.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "post-RA-sched"
#include "AggressiveAntiDepBreaker.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
using namespace llvm;

// If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod
static cl::opt<int>
DebugDiv("agg-antidep-debugdiv",
         cl::desc("Debug control for aggressive anti-dep breaker"),
         cl::init(0), cl::Hidden);
static cl::opt<int>
DebugMod("agg-antidep-debugmod",
         cl::desc("Debug control for aggressive anti-dep breaker"),
         cl::init(0), cl::Hidden);

AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,
                                               MachineBasicBlock *BB) :
  NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
  GroupNodeIndices(TargetRegs, 0),
  KillIndices(TargetRegs, 0),
  DefIndices(TargetRegs, 0)
{
  const unsigned BBSize = BB->size();
  for (unsigned i = 0; i < NumTargetRegs; ++i) {
    // Initialize all registers to be in their own group. Initially we
    // assign the register to the same-indexed GroupNode.
    GroupNodeIndices[i] = i;
    // Initialize the indices to indicate that no registers are live.
    KillIndices[i] = ~0u;
    DefIndices[i] = BBSize;
  }
}

unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) {
  unsigned Node = GroupNodeIndices[Reg];
  while (GroupNodes[Node] != Node)
    Node = GroupNodes[Node];

  return Node;
}

void AggressiveAntiDepState::GetGroupRegs(
  unsigned Group,
  std::vector<unsigned> &Regs,
  std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
{
  for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
    if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
      Regs.push_back(Reg);
  }
}

unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2)
{
  assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!");
  assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!");

  // find group for each register
  unsigned Group1 = GetGroup(Reg1);
  unsigned Group2 = GetGroup(Reg2);

  // if either group is 0, then that must become the parent
  unsigned Parent = (Group1 == 0) ? Group1 : Group2;
  unsigned Other = (Parent == Group1) ? Group2 : Group1;
  GroupNodes.at(Other) = Parent;
  return Parent;
}

unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg)
{
  // Create a new GroupNode for Reg. Reg's existing GroupNode must
  // stay as is because there could be other GroupNodes referring to
  // it.
  unsigned idx = GroupNodes.size();
  GroupNodes.push_back(idx);
  GroupNodeIndices[Reg] = idx;
  return idx;
}

bool AggressiveAntiDepState::IsLive(unsigned Reg)
{
  // KillIndex must be defined and DefIndex not defined for a register
  // to be live.
  return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
}



AggressiveAntiDepBreaker::
AggressiveAntiDepBreaker(MachineFunction& MFi,
                         const RegisterClassInfo &RCI,
                         TargetSubtargetInfo::RegClassVector& CriticalPathRCs) :
  AntiDepBreaker(), MF(MFi),
  MRI(MF.getRegInfo()),
  TII(MF.getTarget().getInstrInfo()),
  TRI(MF.getTarget().getRegisterInfo()),
  RegClassInfo(RCI),
  State(NULL) {
  /* Collect a bitset of all registers that are only broken if they
     are on the critical path. */
  for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) {
    BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]);
    if (CriticalPathSet.none())
      CriticalPathSet = CPSet;
    else
      CriticalPathSet |= CPSet;
   }

  DEBUG(dbgs() << "AntiDep Critical-Path Registers:");
  DEBUG(for (int r = CriticalPathSet.find_first(); r != -1;
             r = CriticalPathSet.find_next(