blob: 458dcf2b0e26db67ac94e3c100d21c382ad99a0d [file] [log] [blame]
//===- ExecutionDomainFix.cpp - Fix execution domain issues ----*- 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/ExecutionDomainFix.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
using namespace llvm;
#define DEBUG_TYPE "execution-deps-fix"
iterator_range<SmallVectorImpl<int>::const_iterator>
ExecutionDomainFix::regIndices(unsigned Reg) const {
assert(Reg < AliasMap.size() && "Invalid register");
const auto &Entry = AliasMap[Reg];
return make_range(Entry.begin(), Entry.end());
}
DomainValue *ExecutionDomainFix::alloc(int domain) {
DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
: Avail.pop_back_val();
if (domain >= 0)
dv->addDomain(domain);
assert(dv->Refs == 0 && "Reference count wasn't cleared");
assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
return dv;
}
void ExecutionDomainFix::release(DomainValue *DV) {
while (DV) {
assert(DV->Refs && "Bad DomainValue");
if (--DV->Refs)
return;
// There are no more DV references. Collapse any contained instructions.
if (DV->AvailableDomains && !DV->isCollapsed())
collapse(DV, DV->getFirstDomain());
DomainValue *Next = DV->Next;
DV->clear();
Avail.push_back(DV);
// Also release the next DomainValue in the chain.
DV = Next;
}
}
DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
DomainValue *DV = DVRef;
if (!DV || !DV->Next)
return DV;
// DV has a chain. Find the end.
do
DV = DV->Next;
while (DV->Next);
// Update DVRef to point to DV.
retain(DV);
release(DVRef);
DVRef = DV;
return DV;
}
void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {
assert(unsigned(rx) < NumRegs && "Invalid index");
assert(!LiveRegs.empty() && "Must enter basic block first.");
if (LiveRegs[rx] == dv)
return;
if (LiveRegs[rx])
release(LiveRegs[rx]);
LiveRegs[rx] = retain(dv);
}
void ExecutionDomainFix::kill(int rx) {
assert(unsigned(rx) < NumRegs && "Invalid index");
assert(!LiveRegs.empty() && "Must enter basic block first.");
if (!LiveRegs[rx])
return;
release(LiveRegs[rx]);
LiveRegs[rx] = nullptr;
}
void ExecutionDomainFix::force(int rx, unsigned domain) {
assert(unsigned(rx) < NumRegs && "Invalid index");
assert(!LiveRegs.empty() && "Must enter basic block first.");
if (DomainValue *dv = LiveRegs[rx]) {
if (dv->isCollapsed())
dv->addDomain(domain);
else if (dv->hasDomain(domain))
collapse(dv, domain);
else {
// This is an incompatible open DomainValue. Collapse it to whatever and
// force the new value into domain. This costs a domain crossing.
collapse(dv, dv->getFirstDomain());
assert(LiveRegs[rx] && "Not live after collapse?");
LiveRegs[rx]->addDomain(domain);
}
} else {
// Set up basic collapsed DomainValue.
setLiveReg(rx, alloc(domain));
}
}
void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
assert(dv->hasDomain(domain) && "Cannot collapse");
// Collapse all the instructions.
while (!dv->Instrs.empty())
TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
dv->setSingleDomain(domain);
// If there are multiple users, give them new, unique DomainValues.
if (!LiveRegs.empty() && dv->Refs > 1)
for (unsigned rx = 0; rx != NumRegs; ++rx)
if (LiveRegs[rx] == dv)
setLiveReg(rx, alloc(domain));
}
bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
assert(!A->isCollapsed() && "Cannot merge into collapsed");
assert(!B->isCollapsed() && "Cannot merge from collapsed");
if (A == B)
return true;
// Restrict to the domains that A and B have in common.
unsigned common = A->getCommonDomains(B->AvailableDomains);
if (!common)
return false;
A->AvailableDomains = common;
A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
// Clear the old DomainValue so we won't try to swizzle instructions twice.
B->clear();
// All uses of B are referred to A.
B->Next = retain(A);
for (unsigned rx = 0; rx != NumRegs; ++rx) {
assert(!LiveRegs.empty() && "no space allocated for live registers");
if (LiveRegs[rx] == B)
setLiveReg(rx, A);
}
return true;
}
void ExecutionDomainFix::enterBasicBlock(
const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
MachineBasicBlock *MBB = TraversedMBB.MBB;
// Set up LiveRegs to represent registers entering MBB.
// Set default domain values to 'no domain' (nullptr)
if (LiveRegs.empty())
LiveRegs.assign(NumRegs, nullptr);
// This is the entry block.
if (MBB->pred_empty()) {
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");
LiveRegsDVInfo &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 rx = 0; rx != NumRegs; ++rx) {
DomainValue *pdv = resolve(Incoming[rx]);
if (!pdv)
continue;
if (!LiveRegs[rx]) {
setLiveReg(rx, pdv);
continue;
}
// We have a live DomainValue from more than one predecessor.
if (LiveRegs[rx]->isCollapsed()) {
// We are already collapsed, but predecessor is not. Force it.
unsigned Domain = LiveRegs[rx]->getFirstDomain();
if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
collapse(pdv, Domain);
continue;
}
// Currently open, merge in predecessor.
if (!pdv->isCollapsed())
merge(LiveRegs[rx], pdv);
else
force(rx, pdv->getFirstDomain());
}
}
LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
<< (!TraversedMBB.IsDone ? ": incomplete\n"
: ": all preds known\n"));
}
void ExecutionDomainFix::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().
for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
release(OldLiveReg);
}
MBBOutRegsInfos[MBBNumber] = LiveRegs;
LiveRegs.clear();
}
bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
// Update instructions with explicit execution domains.
std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
if (DomP.first) {
if (DomP.second)
visitSoftInstr(MI, DomP.second);
else
visitHardInstr(MI, DomP.first);
}
return !DomP.first;
}
void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
assert(!MI->isDebugInstr() && "Won't process debug values");
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())
continue;
if (MO.isUse())
continue;
for (int rx : regIndices(MO.getReg())) {
// This instruction explicitly defines rx.
LLVM_DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << *MI);
// Kill off domains redefined by generic instructions.
if (Kill)
kill(rx);
}
}
}
void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
// Collapse all uses.
for (unsigned i = mi->getDesc().getNumDefs(),
e = mi->getDesc().getNumOperands();
i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg())
continue;
for (int rx : regIndices(mo.getReg())) {
force(rx, domain);
}
}
// Kill all defs and force them.
for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg())
continue;
for (int rx : regIndices(mo.getReg())) {
kill(rx);
force(rx, domain);
}
}
}
void ExecutionDomainFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
// Bitmask of available domains for this instruction after taking collapsed
// operands into account.
unsigned available = mask;
// Scan the explicit use operands for incoming domains.
SmallVector<int, 4> used;
if (!LiveRegs.empty())
for (unsigned i = mi->getDesc().getNumDefs(),
e = mi->getDesc().getNumOperands();
i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg())
continue;
for (int rx : regIndices(mo.getReg())) {
DomainValue *dv = LiveRegs[rx];
if (dv == nullptr)
continue;
// Bitmask of domains that dv and available have in common.
unsigned common = dv->getCommonDomains(available);
// Is it possible to use this collapsed register for free?
if (dv->isCollapsed()) {
// Restrict available domains to the ones in common with the operand.
// If there are no common domains, we must pay the cross-domain
// penalty for this operand.
if (common)
available = common;
} else if (common)
// Open DomainValue is compatible, save it for merging.
used.push_back(rx);
else
// Open DomainValue is not compatible with instruction. It is useless
// now.
kill(rx);
}
}
// If the collapsed operands force a single domain, propagate the collapse.
if (isPowerOf2_32(available)) {
unsigned domain = countTrailingZeros(available);
TII->setExecutionDomain(*mi, domain);
visitHardInstr(mi, domain);
return;
}
// Kill off any remaining uses that don't match available, and build a list of
// incoming DomainValues that we want to merge.
SmallVector<int, 4> Regs;
for (int rx : used) {
assert(!LiveRegs.empty() && "no space allocated for live registers");
DomainValue *&LR = LiveRegs[rx];
// This useless DomainValue could have been missed above.
if (!LR->getCommonDomains(available)) {
kill(rx);
continue;
}
// Sorted insertion.
// Enables giving priority to the latest domains during merging.
auto I = std::upper_bound(
Regs.begin(), Regs.end(), rx, [&](int LHS, const int RHS) {
return RDA->getReachingDef(mi, RC->getRegister(LHS)) <
RDA->getReachingDef(mi, RC->getRegister(RHS));
});
Regs.insert(I, rx);
}
// doms are now sorted in order of appearance. Try to merge them all, giving
// priority to the latest ones.
DomainValue *dv = nullptr;
while (!Regs.empty()) {
if (!dv) {
dv = LiveRegs[Regs.pop_back_val()];
// Force the first dv to match the current instruction.
dv->AvailableDomains = dv->getCommonDomains(available);
assert(dv->AvailableDomains && "Domain should have been filtered");
continue;
}
DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
// Skip already merged values.
if (Latest == dv || Latest->Next)
continue;
if (merge(dv, Latest))
continue;
// If latest didn't merge, it is useless now. Kill all registers using it.
for (int i : used) {
assert(!LiveRegs.empty() && "no space allocated for live registers");
if (LiveRegs[i] == Latest)
kill(i);
}
}
// dv is the DomainValue we are going to use for this instruction.
if (!dv) {
dv = alloc();
dv->AvailableDomains = available;
}
dv->Instrs.push_back(mi);
// Finally set all defs and non-collapsed uses to dv. We must iterate through
// all the operators, including imp-def ones.
for (MachineOperand &mo : mi->operands()) {
if (!mo.isReg())
continue;
for (int rx : regIndices(mo.getReg())) {
if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
kill(rx);
setLiveReg(rx, dv);
}
}
}
}
void ExecutionDomainFix::processBasicBlock(
const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
enterBasicBlock(TraversedMBB);
// If this block is not done, it makes little sense to make any decisions
// based on clearance information. We need to make a second pass anyway,
// and by then we'll have better information, so we can avoid doing the work
// to try and break dependencies now.
for (MachineInstr &MI : *TraversedMBB.MBB) {
if (!MI.isDebugInstr()) {
bool Kill = false;
if (TraversedMBB.PrimaryPass)
Kill = visitInstr(&MI);
processDefs(&MI, Kill);
}
}
leaveBasicBlock(TraversedMBB);
}
bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) {
if (skipFunction(mf.getFunction()))
return false;
MF = &mf;
TII = MF->getSubtarget().getInstrInfo();
TRI = MF->getSubtarget().getRegisterInfo();
LiveRegs.clear();
assert(NumRegs == RC->getNumRegs() && "Bad regclass");
LLVM_DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "
<< TRI->getRegClassName(RC) << " **********\n");
// If no relevant registers are used in the function, we can skip it
// completely.
bool anyregs = false;
const MachineRegisterInfo &MRI = mf.getRegInfo();
for (unsigned Reg : *RC) {
if (MRI.isPhysRegUsed(Reg)) {
anyregs = true;
break;
}
}
if (!anyregs)
return false;
RDA = &getAnalysis<ReachingDefAnalysis>();
// Initialize the AliasMap on the first use.
if (AliasMap.empty()) {
// Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
// therefore the LiveRegs array.
AliasMap.resize(TRI->getNumRegs());
for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
++AI)
AliasMap[*AI].push_back(i);
}
// 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);
}
for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
for (DomainValue *OutLiveReg : OutLiveRegs) {
if (OutLiveReg)
release(OutLiveReg);
}
}
MBBOutRegsInfos.clear();
Avail.clear();
Allocator.DestroyAll();
return false;
}