//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "execution-fix"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
using namespace llvm;
/// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
// First domain available.
unsigned getFirstDomain() const {
- return CountTrailingZeros_32(AvailableDomains);
+ return countTrailingZeros(AvailableDomains);
}
DomainValue() : Refs(0) { clear(); }
typedef DenseMap<MachineBasicBlock*, LiveReg*> LiveOutMap;
LiveOutMap LiveOuts;
+ /// List of undefined register reads in this block in forward order.
+ std::vector<std::pair<MachineInstr*, unsigned> > UndefReads;
+
+ /// Storage for register unit liveness.
+ LivePhysRegs LiveRegSet;
+
/// Current instruction number.
/// The first instruction in each basic block is 0.
int CurInstr;
ExeDepsFix(const TargetRegisterClass *rc)
: MachineFunctionPass(ID), RC(rc), NumRegs(RC->getNumRegs()) {}
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesAll();
MachineFunctionPass::getAnalysisUsage(AU);
}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
- virtual const char *getPassName() const {
+ const char *getPassName() const override {
return "Execution dependency fix";
}
void processDefs(MachineInstr*, bool Kill);
void visitSoftInstr(MachineInstr*, unsigned mask);
void visitHardInstr(MachineInstr*, unsigned domain);
+ bool shouldBreakDependence(MachineInstr*, unsigned OpIdx, unsigned Pref);
+ void processUndefReads(MachineBasicBlock*);
};
}
// Reset instruction counter in each basic block.
CurInstr = 0;
+ // Set up UndefReads to track undefined register reads.
+ UndefReads.clear();
+ LiveRegSet.clear();
+
// Set up LiveRegs to represent registers entering MBB.
if (!LiveRegs)
LiveRegs = new LiveReg[NumRegs];
processDefs(MI, !DomP.first);
}
+/// \brief Return true to if it makes sense to break dependence on a partial def
+/// or undef use.
+bool ExeDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
+ unsigned Pref) {
+ int rx = regIndex(MI->getOperand(OpIdx).getReg());
+ if (rx < 0)
+ return false;
+
+ unsigned Clearance = CurInstr - LiveRegs[rx].Def;
+ DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
+
+ if (Pref > Clearance) {
+ DEBUG(dbgs() << ": Break dependency.\n");
+ return true;
+ }
+ // The current clearance seems OK, but we may be ignoring a def from a
+ // back-edge.
+ if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) {
+ DEBUG(dbgs() << ": OK .\n");
+ return false;
+ }
+ // A def from an unprocessed back-edge may make us break this dependency.
+ DEBUG(dbgs() << ": Wait for back-edge to resolve.\n");
+ return false;
+}
+
// Update def-ages for registers defined by MI.
// If Kill is set, also kill off DomainValues clobbered by the defs.
+//
+// Also break dependencies on partial defs and undef uses.
void ExeDepsFix::processDefs(MachineInstr *MI, bool Kill) {
assert(!MI->isDebugValue() && "Won't process debug values");
+
+ // Break dependence on undef uses. Do this before updating LiveRegs below.
+ unsigned OpNum;
+ unsigned Pref = TII->getUndefRegClearance(MI, OpNum, TRI);
+ if (Pref) {
+ if (shouldBreakDependence(MI, OpNum, Pref))
+ UndefReads.push_back(std::make_pair(MI, OpNum));
+ }
const MCInstrDesc &MCID = MI->getDesc();
for (unsigned i = 0,
e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr
<< '\t' << *MI);
+ // Check clearance before partial register updates.
+ // Call breakDependence before setting LiveRegs[rx].Def.
+ unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI);
+ if (Pref && shouldBreakDependence(MI, i, Pref))
+ TII->breakPartialRegDependency(MI, i, TRI);
+
// How many instructions since rx was last written?
- unsigned Clearance = CurInstr - LiveRegs[rx].Def;
LiveRegs[rx].Def = CurInstr;
// Kill off domains redefined by generic instructions.
if (Kill)
kill(rx);
+ }
+ ++CurInstr;
+}
- // Verify clearance before partial register updates.
- unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI);
- if (!Pref)
- continue;
- DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
- if (Pref > Clearance) {
- DEBUG(dbgs() << ": Break dependency.\n");
- TII->breakPartialRegDependency(MI, i, TRI);
- continue;
- }
+/// \break Break false dependencies on undefined register reads.
+///
+/// Walk the block backward computing precise liveness. This is expensive, so we
+/// only do it on demand. Note that the occurrence of undefined register reads
+/// that should be broken is very rare, but when they occur we may have many in
+/// a single block.
+void ExeDepsFix::processUndefReads(MachineBasicBlock *MBB) {
+ if (UndefReads.empty())
+ return;
- // The current clearance seems OK, but we may be ignoring a def from a
- // back-edge.
- if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) {
- DEBUG(dbgs() << ": OK.\n");
- continue;
- }
+ // Collect this block's live out register units.
+ LiveRegSet.init(TRI);
+ LiveRegSet.addLiveOuts(MBB);
- // A def from an unprocessed back-edge may make us break this dependency.
- DEBUG(dbgs() << ": Wait for back-edge to resolve.\n");
- }
+ MachineInstr *UndefMI = UndefReads.back().first;
+ unsigned OpIdx = UndefReads.back().second;
- ++CurInstr;
+ for (MachineBasicBlock::reverse_iterator I = MBB->rbegin(), E = MBB->rend();
+ I != E; ++I) {
+ // Update liveness, including the current instruction's defs.
+ LiveRegSet.stepBackward(*I);
+
+ if (UndefMI == &*I) {
+ if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
+ TII->breakPartialRegDependency(UndefMI, OpIdx, TRI);
+
+ UndefReads.pop_back();
+ if (UndefReads.empty())
+ return;
+
+ UndefMI = UndefReads.back().first;
+ OpIdx = UndefReads.back().second;
+ }
+ }
}
// A hard instruction only works in one domain. All input registers will be
// 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
+ // If there are no common domains, we must pay the cross-domain
// penalty for this operand.
if (common) available = common;
} else if (common)
// If the collapsed operands force a single domain, propagate the collapse.
if (isPowerOf2_32(available)) {
- unsigned domain = CountTrailingZeros_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<LiveReg, 4> Regs;
- for (SmallVector<int, 4>::iterator i=used.begin(), e=used.end(); i!=e; ++i) {
+ for (SmallVectorImpl<int>::iterator i=used.begin(), e=used.end(); i!=e; ++i) {
int rx = *i;
const LiveReg &LR = LiveRegs[rx];
// This useless DomainValue could have been missed above.
}
// Sorted insertion.
bool Inserted = false;
- for (SmallVector<LiveReg, 4>::iterator i = Regs.begin(), e = Regs.end();
+ for (SmallVectorImpl<LiveReg>::iterator i = Regs.begin(), e = Regs.end();
i != e && !Inserted; ++i) {
if (LR.Def < i->Def) {
Inserted = true;
continue;
// If latest didn't merge, it is useless now. Kill all registers using it.
- for (SmallVector<int,4>::iterator i=used.begin(), e=used.end(); i != e; ++i)
+ for (SmallVectorImpl<int>::iterator i=used.begin(), e=used.end(); i!=e; ++i)
if (LiveRegs[*i].Value == Latest)
kill(*i);
}
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
++I)
visitInstr(I);
+ processUndefReads(MBB);
leaveBasicBlock(MBB);
}
++I)
if (!I->isDebugValue())
processDefs(I, false);
+ processUndefReads(MBB);
leaveBasicBlock(MBB);
}
delete[] FI->second;
}
LiveOuts.clear();
+ UndefReads.clear();
Avail.clear();
Allocator.DestroyAll();
projects / oota-llvm.git / blobdiff