summaryrefslogtreecommitdiff
path: root/lib/CodeGen
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen')
-rw-r--r--lib/CodeGen/AggressiveAntiDepBreaker.cpp282
-rw-r--r--lib/CodeGen/AggressiveAntiDepBreaker.h103
-rw-r--r--lib/CodeGen/CriticalAntiDepBreaker.h4
-rw-r--r--lib/CodeGen/PostRASchedulerList.cpp19
4 files changed, 259 insertions, 149 deletions
diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.cpp b/lib/CodeGen/AggressiveAntiDepBreaker.cpp
index 0fb15eae0d..fef2c50089 100644
--- a/lib/CodeGen/AggressiveAntiDepBreaker.cpp
+++ b/lib/CodeGen/AggressiveAntiDepBreaker.cpp
@@ -22,36 +22,109 @@
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
-
using namespace llvm;
+static cl::opt<int>
+AntiDepTrials("agg-antidep-trials",
+ cl::desc("Maximum number of anti-dependency breaking passes"),
+ cl::init(2), cl::Hidden);
+
+AggressiveAntiDepState::AggressiveAntiDepState(MachineBasicBlock *BB) :
+ GroupNodes(TargetRegisterInfo::FirstVirtualRegister, 0) {
+ // Initialize all registers to be in their own group. Initially we
+ // assign the register to the same-indexed GroupNode.
+ for (unsigned i = 0; i < TargetRegisterInfo::FirstVirtualRegister; ++i)
+ GroupNodeIndices[i] = i;
+
+ // Initialize the indices to indicate that no registers are live.
+ std::fill(KillIndices, array_endof(KillIndices), ~0u);
+ std::fill(DefIndices, array_endof(DefIndices), BB->size());
+}
+
+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)
+{
+ for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) {
+ if (GetGroup(Reg) == Group)
+ 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) :
AntiDepBreaker(), MF(MFi),
MRI(MF.getRegInfo()),
TRI(MF.getTarget().getRegisterInfo()),
AllocatableSet(TRI->getAllocatableSet(MF)),
- GroupNodes(TargetRegisterInfo::FirstVirtualRegister, 0)
-{
+ State(NULL), SavedState(NULL) {
}
AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
+ delete State;
+ delete SavedState;
}
-void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
- // Initialize all registers to be in their own group. Initially we
- // assign the register to the same-indexed GroupNode.
- for (unsigned i = 0; i < TargetRegisterInfo::FirstVirtualRegister; ++i)
- GroupNodeIndices[i] = i;
+unsigned AggressiveAntiDepBreaker::GetMaxTrials() {
+ if (AntiDepTrials <= 0)
+ return 1;
+ return AntiDepTrials;
+}
- // Initialize the indices to indicate that no registers are live.
- std::fill(KillIndices, array_endof(KillIndices), ~0u);
- std::fill(DefIndices, array_endof(DefIndices), BB->size());
+void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
+ assert(State == NULL);
+ State = new AggressiveAntiDepState(BB);
bool IsReturnBlock = (!BB->empty() && BB->back().getDesc().isReturn());
+ unsigned *KillIndices = State->GetKillIndices();
+ unsigned *DefIndices = State->GetDefIndices();
// Determine the live-out physregs for this block.
if (IsReturnBlock) {
@@ -59,13 +132,13 @@ void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(),
E = MRI.liveout_end(); I != E; ++I) {
unsigned Reg = *I;
- UnionGroups(Reg, 0);
+ State->UnionGroups(Reg, 0);
KillIndices[Reg] = BB->size();
DefIndices[Reg] = ~0u;
// Repeat, for all aliases.
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
unsigned AliasReg = *Alias;
- UnionGroups(AliasReg, 0);
+ State->UnionGroups(AliasReg, 0);
KillIndices[AliasReg] = BB->size();
DefIndices[AliasReg] = ~0u;
}
@@ -77,13 +150,13 @@ void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
E = (*SI)->livein_end(); I != E; ++I) {
unsigned Reg = *I;
- UnionGroups(Reg, 0);
+ State->UnionGroups(Reg, 0);
KillIndices[Reg] = BB->size();
DefIndices[Reg] = ~0u;
// Repeat, for all aliases.
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
unsigned AliasReg = *Alias;
- UnionGroups(AliasReg, 0);
+ State->UnionGroups(AliasReg, 0);
KillIndices[AliasReg] = BB->size();
DefIndices[AliasReg] = ~0u;
}
@@ -98,13 +171,13 @@ void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) {
unsigned Reg = *I;
if (!IsReturnBlock && !Pristine.test(Reg)) continue;
- UnionGroups(Reg, 0);
+ State->UnionGroups(Reg, 0);
KillIndices[Reg] = BB->size();
DefIndices[Reg] = ~0u;
// Repeat, for all aliases.
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
unsigned AliasReg = *Alias;
- UnionGroups(AliasReg, 0);
+ State->UnionGroups(AliasReg, 0);
KillIndices[AliasReg] = BB->size();
DefIndices[AliasReg] = ~0u;
}
@@ -112,7 +185,10 @@ void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
}
void AggressiveAntiDepBreaker::FinishBlock() {
- RegRefs.clear();
+ delete State;
+ State = NULL;
+ delete SavedState;
+ SavedState = NULL;
}
void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
@@ -122,6 +198,7 @@ void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
DEBUG(errs() << "Observe: ");
DEBUG(MI->dump());
+ unsigned *DefIndices = State->GetDefIndices();
for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) {
// If Reg is current live, then mark that it can't be renamed as
// we don't know the extent of its live-range anymore (now that it
@@ -129,11 +206,11 @@ void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
// previous schedule region, then set its def index to the most
// conservative location (i.e. the beginning of the previous
// schedule region).
- if (IsLive(Reg)) {
- DEBUG(if (GetGroup(Reg) != 0)
+ if (State->IsLive(Reg)) {
+ DEBUG(if (State->GetGroup(Reg) != 0)
errs() << " " << TRI->getName(Reg) << "=g" <<
- GetGroup(Reg) << "->g0(region live-out)");
- UnionGroups(Reg, 0);
+ State->GetGroup(Reg) << "->g0(region live-out)");
+ State->UnionGroups(Reg, 0);
} else if ((DefIndices[Reg] < InsertPosIndex) && (DefIndices[Reg] >= Count)) {
DefIndices[Reg] = Count;
}
@@ -143,57 +220,10 @@ void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count,
GetPassthruRegs(MI, PassthruRegs);
PrescanInstruction(MI, Count, PassthruRegs);
ScanInstruction(MI, Count);
-}
-
-unsigned AggressiveAntiDepBreaker::GetGroup(unsigned Reg)
-{
- unsigned Node = GroupNodeIndices[Reg];
- while (GroupNodes[Node] != Node)
- Node = GroupNodes[Node];
- return Node;
-}
-
-void AggressiveAntiDepBreaker::GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs)
-{
- for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) {
- if (GetGroup(Reg) == Group)
- Regs.push_back(Reg);
- }
-}
-
-unsigned AggressiveAntiDepBreaker::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 AggressiveAntiDepBreaker::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 AggressiveAntiDepBreaker::IsLive(unsigned Reg)
-{
- // KillIndex must be defined and DefIndex not defined for a register
- // to be live.
- return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
+ // We're starting a new schedule region so forget any saved state.
+ delete SavedState;
+ SavedState = NULL;
}
bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI,
@@ -249,6 +279,10 @@ static void AntiDepPathStep(SUnit *SU, std::vector<SDep*>& Edges) {
void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Count,
std::set<unsigned>& PassthruRegs) {
+ unsigned *DefIndices = State->GetDefIndices();
+ std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
+ RegRefs = State->GetRegRefs();
+
// Scan the register defs for this instruction and update
// live-ranges, groups and RegRefs.
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
@@ -275,23 +309,23 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Cou
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
- DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg));
+ DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << State->GetGroup(Reg));
// If MI's defs have special allocation requirement, don't allow
// any def registers to be changed. Also assume all registers
// defined in a call must not be changed (ABI).
if (MI->getDesc().isCall() || MI->getDesc().hasExtraDefRegAllocReq()) {
- DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
- UnionGroups(Reg, 0);
+ DEBUG(if (State->GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
+ State->UnionGroups(Reg, 0);
}
// Any aliased that are live at this point are completely or
// partially defined here, so group those subregisters with Reg.
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
unsigned AliasReg = *Alias;
- if (IsLive(AliasReg)) {
- UnionGroups(Reg, AliasReg);
- DEBUG(errs() << "->g" << GetGroup(Reg) << "(via " <<
+ if (State->IsLive(AliasReg)) {
+ State->UnionGroups(Reg, AliasReg);
+ DEBUG(errs() << "->g" << State->GetGroup(Reg) << "(via " <<
TRI->getName(AliasReg) << ")");
}
}
@@ -300,7 +334,7 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Cou
const TargetRegisterClass *RC = NULL;
if (i < MI->getDesc().getNumOperands())
RC = MI->getDesc().OpInfo[i].getRegClass(TRI);
- RegisterReference RR = { &MO, RC };
+ AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
RegRefs.insert(std::make_pair(Reg, RR));
}
@@ -310,6 +344,10 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Cou
void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI,
unsigned Count) {
DEBUG(errs() << "\tUse Groups:");
+ unsigned *KillIndices = State->GetKillIndices();
+ unsigned *DefIndices = State->GetDefIndices();
+ std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
+ RegRefs = State->GetRegRefs();
// Scan the register uses for this instruction and update
// live-ranges, groups and RegRefs.
@@ -319,29 +357,30 @@ void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI,
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
- DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg));
+ DEBUG(errs() << " " << TRI->getName(Reg) << "=g" <<
+ State->GetGroup(Reg));
// It wasn't previously live but now it is, this is a kill. Forget
// the previous live-range information and start a new live-range
// for the register.
- if (!IsLive(Reg)) {
+ if (!State->IsLive(Reg)) {
KillIndices[Reg] = Count;
DefIndices[Reg] = ~0u;
RegRefs.erase(Reg);
- LeaveGroup(Reg);
- DEBUG(errs() << "->g" << GetGroup(Reg) << "(last-use)");
+ State->LeaveGroup(Reg);
+ DEBUG(errs() << "->g" << State->GetGroup(Reg) << "(last-use)");
}
// Repeat, for subregisters.
for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
*Subreg; ++Subreg) {
unsigned SubregReg = *Subreg;
- if (!IsLive(SubregReg)) {
+ if (!State->IsLive(SubregReg)) {
KillIndices[SubregReg] = Count;
DefIndices[SubregReg] = ~0u;
RegRefs.erase(SubregReg);
- LeaveGroup(SubregReg);
+ State->LeaveGroup(SubregReg);
DEBUG(errs() << " " << TRI->getName(SubregReg) << "->g" <<
- GetGroup(SubregReg) << "(last-use)");
+ State->GetGroup(SubregReg) << "(last-use)");
}
}
@@ -349,15 +388,15 @@ void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI,
// any use registers to be changed. Also assume all registers
// used in a call must not be changed (ABI).
if (MI->getDesc().isCall() || MI->getDesc().hasExtraSrcRegAllocReq()) {
- DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
- UnionGroups(Reg, 0);
+ DEBUG(if (State->GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
+ State->UnionGroups(Reg, 0);
}
// Note register reference...
const TargetRegisterClass *RC = NULL;
if (i < MI->getDesc().getNumOperands())
RC = MI->getDesc().OpInfo[i].getRegClass(TRI);
- RegisterReference RR = { &MO, RC };
+ AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
RegRefs.insert(std::make_pair(Reg, RR));
}
@@ -377,14 +416,14 @@ void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI,
if (FirstReg != 0) {
DEBUG(errs() << "=" << TRI->getName(Reg));
- UnionGroups(FirstReg, Reg);
+ State->UnionGroups(FirstReg, Reg);
} else {
DEBUG(errs() << " " << TRI->getName(Reg));
FirstReg = Reg;
}
}
- DEBUG(errs() << "->g" << GetGroup(FirstReg) << '\n');
+ DEBUG(errs() << "->g" << State->GetGroup(FirstReg) << '\n');
}
}
@@ -395,10 +434,12 @@ BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) {
// Check all references that need rewriting for Reg. For each, use
// the corresponding register class to narrow the set of registers
// that are appropriate for renaming.
- std::pair<std::multimap<unsigned, RegisterReference>::iterator,
- std::multimap<unsigned, RegisterReference>::iterator>
- Range = RegRefs.equal_range(Reg);
- for (std::multimap<unsigned, RegisterReference>::iterator
+ std::pair<std::multimap<unsigned,
+ AggressiveAntiDepState::RegisterReference>::iterator,
+ std::multimap<unsigned,
+ AggressiveAntiDepState::RegisterReference>::iterator>
+ Range = State->GetRegRefs().equal_range(Reg);
+ for (std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>::iterator
Q = Range.first, QE = Range.second; Q != QE; ++Q) {
const TargetRegisterClass *RC = Q->second.RC;
if (RC == NULL) continue;
@@ -420,11 +461,16 @@ BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) {
bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
unsigned AntiDepGroupIndex,
std::map<unsigned, unsigned> &RenameMap) {
+ unsigned *KillIndices = State->GetKillIndices();
+ unsigned *DefIndices = State->GetDefIndices();
+ std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
+ RegRefs = State->GetRegRefs();
+
// Collect all registers in the same group as AntiDepReg. These all
// need to be renamed together if we are to break the
// anti-dependence.
std::vector<unsigned> Regs;
- GetGroupRegs(AntiDepGroupIndex, Regs);
+ State->GetGroupRegs(AntiDepGroupIndex, Regs);
assert(Regs.size() > 0 && "Empty register group!");
if (Regs.size() == 0)
return false;
@@ -484,7 +530,7 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
// If Reg is dead and Reg's most recent def is not before
// SuperRegs's kill, it's safe to replace SuperReg with
// Reg. We must also check all subregisters of Reg.
- if (IsLive(Reg) || (KillIndices[SuperReg] > DefIndices[Reg])) {
+ if (State->IsLive(Reg) || (KillIndices[SuperReg] > DefIndices[Reg])) {
DEBUG(errs() << "(live)");
continue;
} else {
@@ -492,7 +538,7 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
*Subreg; ++Subreg) {
unsigned SubregReg = *Subreg;
- if (IsLive(SubregReg) || (KillIndices[SuperReg] > DefIndices[SubregReg])) {
+ if (State->IsLive(SubregReg) || (KillIndices[SuperReg] > DefIndices[SubregReg])) {
DEBUG(errs() << "(subreg " << TRI->getName(SubregReg) << " live)");
found = true;
break;
@@ -518,13 +564,29 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
/// BreakAntiDependencies - Identifiy anti-dependencies within the
/// ScheduleDAG and break them by renaming registers.
///
-unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(std::vector<SUnit>& SUnits,
- MachineBasicBlock::iterator& Begin,
- MachineBasicBlock::iterator& End,
- unsigned InsertPosIndex) {
+unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
+ std::vector<SUnit>& SUnits,
+ MachineBasicBlock::iterator& Begin,
+ MachineBasicBlock::iterator& End,
+ unsigned InsertPosIndex) {
+ unsigned *KillIndices = State->GetKillIndices();
+ unsigned *DefIndices = State->GetDefIndices();
+ std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
+ RegRefs = State->GetRegRefs();
+
// The code below assumes that there is at least one instruction,
// so just duck out immediately if the block is empty.
if (SUnits.empty()) return false;
+
+ // Manage saved state to enable multiple passes...
+ if (AntiDepTrials > 1) {
+ if (SavedState == NULL) {
+ SavedState = new AggressiveAntiDepState(*State);
+ } else {
+ delete State;
+ State = new AggressiveAntiDepState(*SavedState);
+ }
+ }
// ...need a map from MI to SUnit.
std::map<MachineInstr *, SUnit *> MISUnitMap;
@@ -539,7 +601,7 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(std::vector<SUnit>& SUn
{
DEBUG(errs() << "Available regs:");
for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
- if (!IsLive(Reg))
+ if (!State->IsLive(Reg))
DEBUG(errs() << " " << TRI->getName(Reg));
}
DEBUG(errs() << '\n');
@@ -623,7 +685,7 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(std::vector<SUnit>& SUn
if (AntiDepReg == 0) continue;
// Determine AntiDepReg's register group.
- const unsigned GroupIndex = GetGroup(AntiDepReg);
+ const unsigned GroupIndex = State->GetGroup(AntiDepReg);
if (GroupIndex == 0) {
DEBUG(errs() << " (zero group)\n");
continue;
@@ -649,10 +711,12 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(std::vector<SUnit>& SUn
// Update the references to the old register CurrReg to
// refer to the new register NewReg.
- std::pair<std::multimap<unsigned, RegisterReference>::iterator,
- std::multimap<unsigned, RegisterReference>::iterator>
+ std::pair<std::multimap<unsigned,
+ AggressiveAntiDepState::RegisterReference>::iterator,
+ std::multimap<unsigned,
+ AggressiveAntiDepState::RegisterReference>::iterator>
Range = RegRefs.equal_range(CurrReg);
- for (std::multimap<unsigned, RegisterReference>::iterator
+ for (std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>::iterator
Q = Range.first, QE = Range.second; Q != QE; ++Q) {
Q->second.Operand->setReg(NewReg);
}
@@ -660,12 +724,12 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(std::vector<SUnit>& SUn
// We just went back in time and modified history; the
// liveness information for CurrReg is now inconsistent. Set
// the state as if it were dead.
- UnionGroups(NewReg, 0);
+ State->UnionGroups(NewReg, 0);
RegRefs.erase(NewReg);
DefIndices[NewReg] = DefIndices[CurrReg];
KillIndices[NewReg] = KillIndices[CurrReg];
- UnionGroups(CurrReg, 0);
+ State->UnionGroups(CurrReg, 0);
RegRefs.erase(CurrReg);
DefIndices[CurrReg] = KillIndices[CurrReg];
KillIndices[CurrReg] = ~0u;
diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.h b/lib/CodeGen/AggressiveAntiDepBreaker.h
index e6b7268e77..f4a05290c0 100644
--- a/lib/CodeGen/AggressiveAntiDepBreaker.h
+++ b/lib/CodeGen/AggressiveAntiDepBreaker.h
@@ -28,11 +28,12 @@
#include "llvm/ADT/SmallSet.h"
namespace llvm {
- class AggressiveAntiDepBreaker : public AntiDepBreaker {
- MachineFunction& MF;
- MachineRegisterInfo &MRI;
- const TargetRegisterInfo *TRI;
-
+ /// Class AggressiveAntiDepState
+ /// Contains all the state necessary for anti-dep breaking. We place
+ /// into a separate class so be can conveniently save/restore it to
+ /// enable multi-pass anti-dep breaking.
+ class AggressiveAntiDepState {
+ public:
/// RegisterReference - Information about a register reference
/// within a liverange
typedef struct {
@@ -42,59 +43,43 @@ namespace llvm {
const TargetRegisterClass *RC;
} RegisterReference;
- /// AllocatableSet - The set of allocatable registers.
- /// We'll be ignoring anti-dependencies on non-allocatable registers,
- /// because they may not be safe to break.
- const BitVector AllocatableSet;
-
+ private:
/// GroupNodes - Implements a disjoint-union data structure to
/// form register groups. A node is represented by an index into
/// the vector. A node can "point to" itself to indicate that it
/// is the parent of a group, or point to another node to indicate
/// that it is a member of the same group as that node.
std::vector<unsigned> GroupNodes;
-
+
/// GroupNodeIndices - For each register, the index of the GroupNode
/// currently representing the group that the register belongs to.
/// Register 0 is always represented by the 0 group, a group
/// composed of registers that are not eligible for anti-aliasing.
unsigned GroupNodeIndices[TargetRegisterInfo::FirstVirtualRegister];
-
- /// RegRegs - Map registers to all their references within a live range.
+
+ /// RegRefs - Map registers to all their references within a live range.
std::multimap<unsigned, RegisterReference> RegRefs;
-
+
/// KillIndices - The index of the most recent kill (proceding bottom-up),
/// or ~0u if the register is not live.
unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister];
-
+
/// DefIndices - The index of the most recent complete def (proceding bottom
/// up), or ~0u if the register is live.
unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister];
public:
- AggressiveAntiDepBreaker(MachineFunction& MFi);
- ~AggressiveAntiDepBreaker();
+ AggressiveAntiDepState(MachineBasicBlock *BB);
- /// Start - Initialize anti-dep breaking for a new basic block.
- void StartBlock(MachineBasicBlock *BB);
-
- /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path
- /// of the ScheduleDAG and break them by renaming registers.
- ///
- unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits,
- MachineBasicBlock::iterator& Begin,
- MachineBasicBlock::iterator& End,
- unsigned InsertPosIndex);
+ /// GetKillIndices - Return the kill indices.
+ unsigned *GetKillIndices() { return KillIndices; }
- /// Observe - Update liveness information to account for the current
- /// instruction, which will not be scheduled.
- ///
- void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex);
+ /// GetDefIndices - Return the define indices.
+ unsigned *GetDefIndices() { return DefIndices; }
- /// Finish - Finish anti-dep breaking for a basic block.
- void FinishBlock();
+ /// GetRegRefs - Return the RegRefs map.
+ std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; }
- private:
// GetGroup - Get the group for a register. The returned value is
// the index of the GroupNode representing the group.
unsigned GetGroup(unsigned Reg);
@@ -115,7 +100,57 @@ namespace llvm {
/// IsLive - Return true if Reg is live
bool IsLive(unsigned Reg);
+ };
+
+
+ /// Class AggressiveAntiDepBreaker
+ class AggressiveAntiDepBreaker : public AntiDepBreaker {
+ MachineFunction& MF;
+ MachineRegisterInfo &MRI;
+ const TargetRegisterInfo *TRI;
+
+ /// AllocatableSet - The set of allocatable registers.
+ /// We'll be ignoring anti-dependencies on non-allocatable registers,
+ /// because they may not be safe to break.
+ const BitVector AllocatableSet;
+
+ /// State - The state used to identify and rename anti-dependence
+ /// registers.
+ AggressiveAntiDepState *State;
+
+ /// SavedState - The state for the start of an anti-dep
+ /// region. Used to restore the state at the beginning of each
+ /// pass
+ AggressiveAntiDepState *SavedState;
+
+ public:
+ AggressiveAntiDepBreaker(MachineFunction& MFi);
+ ~AggressiveAntiDepBreaker();
+ /// GetMaxTrials - As anti-dependencies are broken, additional
+ /// dependencies may be exposed, so multiple passes are required.
+ unsigned GetMaxTrials();
+
+ /// Start - Initialize anti-dep breaking for a new basic block.
+ void StartBlock(MachineBasicBlock *BB);
+
+ /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path
+ /// of the ScheduleDAG and break them by renaming registers.
+ ///
+ unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits,
+ MachineBasicBlock::iterator& Begin,
+ MachineBasicBlock::iterator& End,
+ unsigned InsertPosIndex);
+
+ /// Observe - Update liveness information to account for the current
+ /// instruction, which will not be scheduled.
+ ///
+ void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex);
+
+ /// Finish - Finish anti-dep breaking for a basic block.
+ void FinishBlock();
+
+ private:
/// IsImplicitDefUse - Return true if MO represents a register
/// that is both implicitly used and defined in MI
bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO);
diff --git a/lib/CodeGen/CriticalAntiDepBreaker.h b/lib/CodeGen/CriticalAntiDepBreaker.h
index 830b29a060..700851c297 100644
--- a/lib/CodeGen/CriticalAntiDepBreaker.h
+++ b/lib/CodeGen/CriticalAntiDepBreaker.h
@@ -64,6 +64,10 @@ namespace llvm {
CriticalAntiDepBreaker(MachineFunction& MFi);
~CriticalAntiDepBreaker();
+ /// GetMaxTrials - Critical path anti-dependence breaking requires
+ /// only a single pass
+ unsigned GetMaxTrials() { return 1; }
+
/// Start - Initialize anti-dep breaking for a new basic block.
void StartBlock(MachineBasicBlock *BB);
diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp
index 8fe20876bc..c3cae8a4be 100644
--- a/lib/CodeGen/PostRASchedulerList.cpp
+++ b/lib/CodeGen/PostRASchedulerList.cpp
@@ -40,6 +40,7 @@
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtarget.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
@@ -315,16 +316,20 @@ void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) {
/// Schedule - Schedule the instruction range using list scheduling.
///
void SchedulePostRATDList::Schedule() {
- DEBUG(errs() << "********** List Scheduling **********\n");
-
// Build the scheduling graph.
BuildSchedGraph(AA);
if (AntiDepBreak != NULL) {
- unsigned Broken =
- AntiDepBreak->BreakAntiDependencies(SUnits, Begin, InsertPos,
- InsertPosIndex);
- if (Broken > 0) {
+ for (unsigned i = 0, Trials = AntiDepBreak->GetMaxTrials();
+ i < Trials; ++i) {
+ DEBUG(errs() << "********** Break Anti-Deps, Trial " <<
+ i << " **********\n");
+ unsigned Broken =
+ AntiDepBreak->BreakAntiDependencies(SUnits, Begin, InsertPos,
+ InsertPosIndex);
+ if (Broken == 0)
+ break;
+
// We made changes. Update the dependency graph.
// Theoretically we could update the graph in place:
// When a live range is changed to use a different register, remove
@@ -340,6 +345,8 @@ void SchedulePostRATDList::Schedule() {
}
}
+ DEBUG(errs() << "********** List Scheduling **********\n");
+
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(this));
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-12 22:49:10 +0000