blob: 050fef5d25ed6dc923539bf60ffd8ec4fabec442 [file] [log] [blame]
//===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/ReachingDefAnalysis.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
using namespace llvm;
#define DEBUG_TYPE "reaching-deps-analysis"
char ReachingDefAnalysis::ID = 0;
INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
true)
void ReachingDefAnalysis::enterBasicBlock(
const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
MachineBasicBlock *MBB = TraversedMBB.MBB;
unsigned MBBNumber = MBB->getNumber();
assert(MBBNumber < MBBReachingDefs.size() &&
"Unexpected basic block number.");
MBBReachingDefs[MBBNumber].resize(NumRegUnits);
// Reset instruction counter in each basic block.
CurInstr = 0;
// Set up LiveRegs to represent registers entering MBB.
// Default values are 'nothing happened a long time ago'.
if (LiveRegs.empty())
LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
// This is the entry block.
if (MBB->pred_empty()) {
for (const auto &LI : MBB->liveins()) {
for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
// Treat function live-ins as if they were defined just before the first
// instruction. Usually, function arguments are set up immediately
// before the call.
LiveRegs[*Unit] = -1;
MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
}
}
LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
return;
}
// Try to coalesce live-out registers from predecessors.
for (MachineBasicBlock *pred : MBB->predecessors()) {
assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
"Should have pre-allocated MBBInfos for all MBBs");
const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
// Incoming is null if this is a backedge from a BB
// we haven't processed yet
if (Incoming.empty())
continue;
for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
// Use the most recent predecessor def for each register.
LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
if ((LiveRegs[Unit] != ReachingDefDefaultVal))
MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
}
}
LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
<< (!TraversedMBB.IsDone ? ": incomplete\n"
: ": all preds known\n"));
}
void ReachingDefAnalysis::leaveBasicBlock(
const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
assert(!LiveRegs.empty() && "Must enter basic block first.");
unsigned MBBNumber = TraversedMBB.MBB->getNumber();
assert(MBBNumber < MBBOutRegsInfos.size() &&
"Unexpected basic block number.");
// Save register clearances at end of MBB - used by enterBasicBlock().
MBBOutRegsInfos[MBBNumber] = LiveRegs;
// While processing the basic block, we kept `Def` relative to the start
// of the basic block for convenience. However, future use of this information
// only cares about the clearance from the end of the block, so adjust
// everything to be relative to the end of the basic block.
for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
OutLiveReg -= CurInstr;
LiveRegs.clear();
}
void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
assert(!MI->isDebugInstr() && "Won't process debug instructions");
unsigned MBBNumber = MI->getParent()->getNumber();
assert(MBBNumber < MBBReachingDefs.size() &&
"Unexpected basic block number.");
const MCInstrDesc &MCID = MI->getDesc();
for (unsigned i = 0,
e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.getReg())
continue;
if (MO.isUse())
continue;
for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
// This instruction explicitly defines the current reg unit.
LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr
<< '\t' << *MI);
// How many instructions since this reg unit was last written?
LiveRegs[*Unit] = CurInstr;
MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
}
}
InstIds[MI] = CurInstr;
++CurInstr;
}
void ReachingDefAnalysis::processBasicBlock(
const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
enterBasicBlock(TraversedMBB);
for (MachineInstr &MI : *TraversedMBB.MBB) {
if (!MI.isDebugInstr())
processDefs(&MI);
}
leaveBasicBlock(TraversedMBB);
}
bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
if (skipFunction(mf.getFunction()))
return false;
MF = &mf;
TRI = MF->getSubtarget().getRegisterInfo();
LiveRegs.clear();
NumRegUnits = TRI->getNumRegUnits();
MBBReachingDefs.resize(mf.getNumBlockIDs());
LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
// Initialize the MBBOutRegsInfos
MBBOutRegsInfos.resize(mf.getNumBlockIDs());
// Traverse the basic blocks.
LoopTraversal Traversal;
LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
processBasicBlock(TraversedMBB);
}
// Sorting all reaching defs found for a ceartin reg unit in a given BB.
for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
llvm::sort(RegUnitDefs.begin(), RegUnitDefs.end());
}
return false;
}
void ReachingDefAnalysis::releaseMemory() {
// Clear the internal vectors.
MBBOutRegsInfos.clear();
MBBReachingDefs.clear();
InstIds.clear();
}
int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
assert(InstIds.count(MI) && "Unexpected machine instuction.");
int InstId = InstIds[MI];
int DefRes = ReachingDefDefaultVal;
unsigned MBBNumber = MI->getParent()->getNumber();
assert(MBBNumber < MBBReachingDefs.size() &&
"Unexpected basic block number.");
int LatestDef = ReachingDefDefaultVal;
for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
if (Def >= InstId)
break;
DefRes = Def;
}
LatestDef = std::max(LatestDef, DefRes);
}
return LatestDef;
}
int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
assert(InstIds.count(MI) && "Unexpected machine instuction.");
return InstIds[MI] - getReachingDef(MI, PhysReg);
}