#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/PointerIntPair.h"
namespace llvm {
struct SUnit;
class TargetRegisterClass;
template<class Graph> class GraphWriter;
- /// SDep - Scheduling dependency. It keeps track of dependent nodes,
- /// cost of the depdenency, etc.
- struct SDep {
- SUnit *Dep; // Dependent - either a predecessor or a successor.
- unsigned Reg; // If non-zero, this dep is a physreg dependency.
- int Cost; // Cost of the dependency.
- bool isCtrl : 1; // True iff it's a control dependency.
- bool isArtificial : 1; // True iff it's an artificial ctrl dep added
- // during sched that may be safely deleted if
- // necessary.
- bool isAntiDep : 1; // True iff it's an anti-dependency (on a physical
- // register.
- SDep(SUnit *d, unsigned r, int t, bool c, bool a, bool anti)
- : Dep(d), Reg(r), Cost(t), isCtrl(c), isArtificial(a), isAntiDep(anti) {}
+ /// SDep - Scheduling dependency. This represents one direction of an
+ /// edge in the scheduling DAG.
+ class SDep {
+ public:
+ /// Kind - These are the different kinds of scheduling dependencies.
+ enum Kind {
+ Data, ///< Regular data dependence (aka true-dependence).
+ Anti, ///< A register anti-dependedence (aka WAR).
+ Output, ///< A register output-dependence (aka WAW).
+ Order ///< Any other ordering dependency.
+ };
+
+ private:
+ /// Dep - A pointer to the depending/depended-on SUnit, and an enum
+ /// indicating the kind of the dependency.
+ PointerIntPair<SUnit *, 2, Kind> Dep;
+
+ /// Contents - A union discriminated by the dependence kind.
+ union {
+ /// Reg - For Data, Anti, and Output dependencies, the associated
+ /// register. For Data dependencies that don't currently have a register
+ /// assigned, this is set to zero.
+ unsigned Reg;
+
+ /// Order - Additional information about Order dependencies.
+ struct {
+ /// isNormalMemory - True if both sides of the dependence
+ /// access memory in non-volatile and fully modeled ways.
+ bool isNormalMemory : 1;
+
+ /// isMustAlias - True if both sides of the dependence are known to
+ /// access the same memory.
+ bool isMustAlias : 1;
+
+ /// isArtificial - True if this is an artificial dependency, meaning
+ /// it is not necessary for program correctness, and may be safely
+ /// deleted if necessary.
+ bool isArtificial : 1;
+ } Order;
+ } Contents;
+
+ /// Latency - The time associated with this edge. Often this is just
+ /// the value of the Latency field of the predecessor, however advanced
+ /// models may provide additional information about specific edges.
+ unsigned Latency;
+
+ public:
+ /// SDep - Construct a null SDep. This is only for use by container
+ /// classes which require default constructors. SUnits may not
+ /// have null SDep edges.
+ SDep() : Dep(0, Data) {}
+
+ /// SDep - Construct an SDep with the specified values.
+ SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0,
+ bool isNormalMemory = false, bool isMustAlias = false,
+ bool isArtificial = false)
+ : Dep(S, kind), Contents(), Latency(latency) {
+ switch (kind) {
+ case Anti:
+ case Output:
+ assert(Reg != 0 &&
+ "SDep::Anti and SDep::Output must use a non-zero Reg!");
+ // fall through
+ case Data:
+ assert(!isMustAlias && "isMustAlias only applies with SDep::Order!");
+ assert(!isArtificial && "isArtificial only applies with SDep::Order!");
+ Contents.Reg = Reg;
+ break;
+ case Order:
+ assert(Reg == 0 && "Reg given for non-register dependence!");
+ Contents.Order.isNormalMemory = isNormalMemory;
+ Contents.Order.isMustAlias = isMustAlias;
+ Contents.Order.isArtificial = isArtificial;
+ break;
+ }
+ }
+
+ bool operator==(const SDep &Other) const {
+ if (Dep != Other.Dep) return false;
+ switch (Dep.getInt()) {
+ case Data:
+ case Anti:
+ case Output:
+ return Contents.Reg == Other.Contents.Reg;
+ case Order:
+ return Contents.Order.isNormalMemory ==
+ Other.Contents.Order.isNormalMemory &&
+ Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias &&
+ Contents.Order.isArtificial == Other.Contents.Order.isArtificial;
+ }
+ assert(0 && "Invalid dependency kind!");
+ return false;
+ }
+
+ bool operator!=(const SDep &Other) const {
+ return !operator==(Other);
+ }
+
+ /// getLatency - Return the latency value for this edge, which roughly
+ /// means the minimum number of cycles that must elapse between the
+ /// predecessor and the successor, given that they have this edge
+ /// between them.
+ unsigned getLatency() const {
+ return Latency;
+ }
+
+ //// getSUnit - Return the SUnit to which this edge points.
+ SUnit *getSUnit() const {
+ return Dep.getPointer();
+ }
+
+ //// setSUnit - Assign the SUnit to which this edge points.
+ void setSUnit(SUnit *SU) {
+ Dep.setPointer(SU);
+ }
+
+ /// getKind - Return an enum value representing the kind of the dependence.
+ Kind getKind() const {
+ return Dep.getInt();
+ }
+
+ /// isCtrl - Shorthand for getKind() != SDep::Data.
+ bool isCtrl() const {
+ return getKind() != Data;
+ }
+
+ /// isArtificial - Test if this is an Order dependence that is marked
+ /// as "artificial", meaning it isn't necessary for correctness.
+ bool isArtificial() const {
+ return getKind() == Order && Contents.Order.isArtificial;
+ }
+
+ /// isMustAlias - Test if this is an Order dependence that is marked
+ /// as "must alias", meaning that the SUnits at either end of the edge
+ /// have a memory dependence on a known memory location.
+ bool isMustAlias() const {
+ return getKind() == Order && Contents.Order.isMustAlias;
+ }
+
+ /// isAssignedRegDep - Test if this is a Data dependence that is
+ /// associated with a register.
+ bool isAssignedRegDep() const {
+ return getKind() == Data && Contents.Reg != 0;
+ }
+
+ /// getReg - Return the register associated with this edge. This is
+ /// only valid on Data, Anti, and Output edges. On Data edges, this
+ /// value may be zero, meaning there is no associated register.
+ unsigned getReg() const {
+ assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
+ "getReg called on non-register dependence edge!");
+ return Contents.Reg;
+ }
+
+ /// setReg - Assign the associated register for this edge. This is
+ /// only valid on Data, Anti, and Output edges. On Anti and Output
+ /// edges, this value must not be zero. On Data edges, the value may
+ /// be zero, which would mean that no specific register is associated
+ /// with this edge.
+ void setReg(unsigned Reg) {
+ assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
+ "setReg called on non-register dependence edge!");
+ assert((getKind() != Anti || Reg != 0) &&
+ "SDep::Anti edge cannot use the zero register!");
+ assert((getKind() != Output || Reg != 0) &&
+ "SDep::Output edge cannot use the zero register!");
+ Contents.Reg = Reg;
+ }
};
/// SUnit - Scheduling unit. This is a node in the scheduling DAG.
unsigned NodeNum; // Entry # of node in the node vector.
unsigned NodeQueueId; // Queue id of node.
unsigned short Latency; // Node latency.
- short NumPreds; // # of non-control preds.
- short NumSuccs; // # of non-control sucss.
+ short NumPreds; // # of SDep::Data preds.
+ short NumSuccs; // # of SDep::Data sucss.
short NumPredsLeft; // # of preds not scheduled.
short NumSuccsLeft; // # of succs not scheduled.
bool isTwoAddress : 1; // Is a two-address instruction.
return Instr;
}
- /// addPred - This adds the specified node as a pred of the current node if
+ /// addPred - This adds the specified edge as a pred of the current node if
/// not already. It also adds the current node as a successor of the
/// specified node. This returns true if this is a new pred.
- bool addPred(SUnit *N, bool isCtrl, bool isArtificial,
- unsigned PhyReg = 0, int Cost = 1, bool isAntiDep = false) {
+ bool addPred(const SDep &D) {
+ // If this node already has this depenence, don't add a redundant one.
for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
- if (Preds[i].Dep == N &&
- Preds[i].isCtrl == isCtrl &&
- Preds[i].isArtificial == isArtificial &&
- Preds[i].isAntiDep == isAntiDep)
+ if (Preds[i] == D)
return false;
- Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isArtificial, isAntiDep));
- N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl,
- isArtificial, isAntiDep));
- if (!isCtrl) {
+ // Add a pred to this SUnit.
+ Preds.push_back(D);
+ // Now add a corresponding succ to N.
+ SDep P = D;
+ P.setSUnit(this);
+ SUnit *N = D.getSUnit();
+ N->Succs.push_back(P);
+ // Update the bookkeeping.
+ if (D.getKind() == SDep::Data) {
++NumPreds;
++N->NumSuccs;
}
return true;
}
- bool removePred(SUnit *N, bool isCtrl, bool isArtificial, bool isAntiDep) {
+ /// removePred - This removes the specified edge as a pred of the current
+ /// node if it exists. It also removes the current node as a successor of
+ /// the specified node. This returns true if the edge existed and was
+ /// removed.
+ bool removePred(const SDep &D) {
+ // Find the matching predecessor.
for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
I != E; ++I)
- if (I->Dep == N &&
- I->isCtrl == isCtrl &&
- I->isArtificial == isArtificial &&
- I->isAntiDep == isAntiDep) {
+ if (*I == D) {
bool FoundSucc = false;
+ // Find the corresponding successor in N.
+ SDep P = D;
+ P.setSUnit(this);
+ SUnit *N = D.getSUnit();
for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
EE = N->Succs.end(); II != EE; ++II)
- if (II->Dep == this &&
- II->isCtrl == isCtrl && II->isArtificial == isArtificial &&
- II->isAntiDep == isAntiDep) {
+ if (*II == P) {
FoundSucc = true;
N->Succs.erase(II);
break;
}
assert(FoundSucc && "Mismatching preds / succs lists!");
Preds.erase(I);
- if (!isCtrl) {
+ // Update the bookkeeping;
+ if (D.getKind() == SDep::Data) {
--NumPreds;
--N->NumSuccs;
}
bool isPred(SUnit *N) {
for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
- if (Preds[i].Dep == N)
+ if (Preds[i].getSUnit() == N)
return true;
return false;
}
bool isSucc(SUnit *N) {
for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
- if (Succs[i].Dep == N)
+ if (Succs[i].getSUnit() == N)
return true;
return false;
}
}
pointer operator*() const {
- return Node->Preds[Operand].Dep;
+ return Node->Preds[Operand].getSUnit();
}
pointer operator->() const { return operator*(); }
unsigned getOperand() const { return Operand; }
const SUnit *getNode() const { return Node; }
- bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; }
- bool isArtificialDep() const { return Node->Preds[Operand].isArtificial; }
+ /// isCtrlDep - Test if this is not an SDep::Data dependence.
+ bool isCtrlDep() const {
+ return Node->Preds[Operand].isCtrl();
+ }
+ bool isArtificialDep() const {
+ return Node->Preds[Operand].isArtificial();
+ }
};
template <> struct GraphTraits<SUnit*> {
#include "llvm/CodeGen/ScheduleDAG.h"
namespace llvm {
- struct SUnit;
- class MachineConstantPool;
- class MachineFunction;
- class MachineModuleInfo;
- class MachineRegisterInfo;
- class MachineInstr;
- class TargetRegisterInfo;
- class ScheduleDAG;
- class SelectionDAG;
- class SelectionDAGISel;
- class TargetInstrInfo;
- class TargetInstrDesc;
- class TargetLowering;
- class TargetMachine;
- class TargetRegisterClass;
-
class ScheduleDAGInstrs : public ScheduleDAG {
public:
ScheduleDAGInstrs(MachineBasicBlock *bb,
#include "llvm/ADT/SmallSet.h"
namespace llvm {
- struct SUnit;
- class MachineConstantPool;
- class MachineFunction;
- class MachineModuleInfo;
- class MachineRegisterInfo;
- class MachineInstr;
- class TargetRegisterInfo;
- class ScheduleDAG;
- class SelectionDAG;
- class SelectionDAGISel;
- class TargetInstrInfo;
- class TargetInstrDesc;
- class TargetLowering;
- class TargetMachine;
- class TargetRegisterClass;
-
/// HazardRecognizer - This determines whether or not an instruction can be
/// issued this cycle, and whether or not a noop needs to be inserted to handle
/// the hazard.
unsigned MaxSuccLatency = 0;
for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end();
I != E; ++I) {
- int SuccLatency = Latencies[I->Dep->NodeNum];
+ int SuccLatency = Latencies[I->getSUnit()->NodeNum];
if (SuccLatency == -1) {
AllDone = false;
- WorkList.push_back(I->Dep);
+ WorkList.push_back(I->getSUnit());
} else {
// This assumes that there's no delay for reusing registers.
- unsigned NewLatency =
- SuccLatency + ((I->isCtrl && I->Reg != 0) ? 1 : CurLatency);
+ unsigned NewLatency = SuccLatency + CurLatency;
MaxSuccLatency = std::max(MaxSuccLatency, NewLatency);
}
}
Latency = SU->Latency + SuccLat;
for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
I != E; ++I)
- WorkList.push_back(std::make_pair(I->Dep, Latency));
+ WorkList.push_back(std::make_pair(I->getSUnit(), Latency));
}
}
}
SUnit *OnlyAvailablePred = 0;
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- SUnit &Pred = *I->Dep;
+ SUnit &Pred = *I->getSUnit();
if (!Pred.isScheduled) {
// We found an available, but not scheduled, predecessor. If it's the
// only one we have found, keep track of it... otherwise give up.
unsigned NumNodesBlocking = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- if (getSingleUnscheduledPred(I->Dep) == SU)
+ if (getSingleUnscheduledPred(I->getSUnit()) == SU)
++NumNodesBlocking;
NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- AdjustPriorityOfUnscheduledPreds(I->Dep);
+ AdjustPriorityOfUnscheduledPreds(I->getSUnit());
}
/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
void Schedule();
private:
- void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
+ void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
bool BreakAntiDependencies();
SUnit *SU = &SUnits[*I];
for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
P != PE; ++P) {
- SUnit *PredSU = P->Dep;
+ SUnit *PredSU = P->getSUnit();
// This assumes that there's no delay for reusing registers.
- unsigned PredLatency = (P->isCtrl && P->Reg != 0) ? 1 : PredSU->Latency;
+ unsigned PredLatency = P->getLatency();
unsigned PredTotalLatency = PredSU->CycleBound + PredLatency;
if (SU->CycleBound < PredTotalLatency ||
- (SU->CycleBound == PredTotalLatency && !P->isAntiDep)) {
+ (SU->CycleBound == PredTotalLatency &&
+ P->getKind() == SDep::Anti)) {
SU->CycleBound = PredTotalLatency;
CriticalPath[*I] = &*P;
}
BitVector AllocatableSet = TRI->getAllocatableSet(*MF);
DenseMap<MachineInstr *, unsigned> CriticalAntiDeps;
for (SUnit *SU = Max; CriticalPath[SU->NodeNum];
- SU = CriticalPath[SU->NodeNum]->Dep) {
+ SU = CriticalPath[SU->NodeNum]->getSUnit()) {
SDep *Edge = CriticalPath[SU->NodeNum];
- SUnit *NextSU = Edge->Dep;
- unsigned AntiDepReg = Edge->Reg;
+ SUnit *NextSU = Edge->getSUnit();
// Only consider anti-dependence edges.
- if (!Edge->isAntiDep)
+ if (Edge->getKind() != SDep::Anti)
continue;
+ unsigned AntiDepReg = Edge->getReg();
assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
// Don't break anti-dependencies on non-allocatable registers.
if (!AllocatableSet.test(AntiDepReg))
// break it.
for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
P != PE; ++P)
- if (P->Dep == NextSU ?
- (!P->isAntiDep || P->Reg != AntiDepReg) :
- (!P->isCtrl && !P->isAntiDep && P->Reg == AntiDepReg)) {
+ if (P->getSUnit() == NextSU ?
+ (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
+ (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
AntiDepReg = 0;
break;
}
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the PendingQueue if the count reaches zero. Also update its cycle bound.
-void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
+ SUnit *SuccSU = SuccEdge->getSUnit();
--SuccSU->NumPredsLeft;
#ifndef NDEBUG
// Compute how many cycles it will be before this actually becomes
// available. This is the max of the start time of all predecessors plus
// their latencies.
- // If this is a token edge, we don't need to wait for the latency of the
- // preceeding instruction (e.g. a long-latency load) unless there is also
- // some other data dependence.
- unsigned PredDoneCycle = SU->Cycle;
- if (!isChain)
- PredDoneCycle += SU->Latency;
- else if (SU->Latency)
- PredDoneCycle += 1;
+ unsigned PredDoneCycle = SU->Cycle + SuccEdge->getLatency();
SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle);
if (SuccSU->NumPredsLeft == 0) {
// Top down: release successors.
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- ReleaseSucc(SU, I->Dep, I->isCtrl);
+ ReleaseSucc(SU, &*I);
SU->isScheduled = true;
AvailableQueue.ScheduledNode(SU);
PendingQueue.pop_back();
--i; --e;
} else {
- assert(PendingQueue[i]->CycleBound > CurCycle && "Negative latency?");
+ assert(PendingQueue[i]->CycleBound > CurCycle && "Non-positive latency?");
}
}
// So, just iterate over all predecessors and take the longest path
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- unsigned PredDepth = I->Dep->Depth;
+ unsigned PredDepth = I->getSUnit()->Depth;
if (PredDepth+1 > SUDepth) {
SUDepth = PredDepth + 1;
}
// Update degrees of all nodes depending on current SUnit
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- SUnit *SU = I->Dep;
+ SUnit *SU = I->getSUnit();
if (!--SU->Depth)
// If all dependencies of the node are processed already,
// then the longest path for the node can be computed now
// So, just iterate over all successors and take the longest path
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- unsigned SuccHeight = I->Dep->Height;
+ unsigned SuccHeight = I->getSUnit()->Height;
if (SuccHeight+1 > SUHeight) {
SUHeight = SuccHeight + 1;
}
// Update degrees of all nodes depending on current SUnit
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- SUnit *SU = I->Dep;
+ SUnit *SU = I->getSUnit();
if (!--SU->Height)
// If all dependencies of the node are processed already,
// then the longest path for the node can be computed now
cerr << " Predecessors:\n";
for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
I != E; ++I) {
- if (I->isCtrl)
- cerr << " ch #";
- else
- cerr << " val #";
- cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
- if (I->isArtificial)
+ cerr << " ";
+ switch (I->getKind()) {
+ case SDep::Data: cerr << "val "; break;
+ case SDep::Anti: cerr << "anti"; break;
+ case SDep::Output: cerr << "out "; break;
+ case SDep::Order: cerr << "ch "; break;
+ }
+ cerr << "#";
+ cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")";
+ if (I->isArtificial())
cerr << " *";
cerr << "\n";
}
cerr << " Successors:\n";
for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
I != E; ++I) {
- if (I->isCtrl)
- cerr << " ch #";
- else
- cerr << " val #";
- cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
- if (I->isArtificial)
+ cerr << " ";
+ switch (I->getKind()) {
+ case SDep::Data: cerr << "val "; break;
+ case SDep::Anti: cerr << "anti"; break;
+ case SDep::Output: cerr << "out "; break;
+ case SDep::Order: cerr << "ch "; break;
+ }
+ cerr << "#";
+ cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")";
+ if (I->isArtificial())
cerr << " *";
cerr << "\n";
}
Allocate(SU->NodeNum, --Id);
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- SUnit *SU = I->Dep;
+ SUnit *SU = I->getSUnit();
if (!--Node2Index[SU->NodeNum])
// If all dependencies of the node are processed already,
// then the node can be computed now.
SUnit *SU = &SUnits[i];
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- assert(Node2Index[SU->NodeNum] > Node2Index[I->Dep->NodeNum] &&
+ assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] &&
"Wrong topological sorting");
}
}
WorkList.pop_back();
Visited.set(SU->NodeNum);
for (int I = SU->Succs.size()-1; I >= 0; --I) {
- int s = SU->Succs[I].Dep->NodeNum;
+ int s = SU->Succs[I].getSUnit()->NodeNum;
if (Node2Index[s] == UpperBound) {
HasLoop = true;
return;
}
// Visit successors if not already and in affected region.
if (!Visited.test(s) && Node2Index[s] < UpperBound) {
- WorkList.push_back(SU->Succs[I].Dep);
+ WorkList.push_back(SU->Succs[I].getSUnit());
}
}
}
return true;
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I)
- if (I->Cost < 0 && IsReachable(TargetSU, I->Dep))
+ if (I->isAssignedRegDep() &&
+ IsReachable(TargetSU, I->getSUnit()))
return true;
return false;
}
DenseMap<SUnit*, unsigned> &VRBaseMap) {
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl) continue; // ignore chain preds
- if (I->Dep->CopyDstRC) {
+ if (I->isCtrl()) continue; // ignore chain preds
+ if (I->getSUnit()->CopyDstRC) {
// Copy to physical register.
- DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep);
+ DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit());
assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
// Find the destination physical register.
unsigned Reg = 0;
for (SUnit::const_succ_iterator II = SU->Succs.begin(),
EE = SU->Succs.end(); II != EE; ++II) {
- if (I->Reg) {
- Reg = I->Reg;
+ if (I->getReg()) {
+ Reg = I->getReg();
break;
}
}
- assert(I->Reg && "Unknown physical register!");
+ assert(I->getReg() && "Unknown physical register!");
TII->copyRegToReg(*BB, BB->end(), Reg, VRI->second,
SU->CopyDstRC, SU->CopySrcRC);
} else {
// Copy from physical register.
- assert(I->Reg && "Unknown physical register!");
+ assert(I->getReg() && "Unknown physical register!");
unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
isNew = isNew; // Silence compiler warning.
assert(isNew && "Node emitted out of order - early");
- TII->copyRegToReg(*BB, BB->end(), VRBase, I->Reg,
+ TII->copyRegToReg(*BB, BB->end(), VRBase, I->getReg(),
SU->CopyDstRC, SU->CopySrcRC);
}
break;
void ScheduleDAGInstrs::BuildSchedUnits() {
SUnits.clear();
SUnits.reserve(BB->size());
- int Cost = 1; // FIXME
// We build scheduling units by walking a block's instruction list from bottom
// to top.
MachineInstr *MI = prior(MII);
SUnit *SU = NewSUnit(MI);
+ // Assign the Latency field of SU using target-provided information.
+ ComputeLatency(SU);
+
// Add register-based dependencies (data, anti, and output).
for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
const MachineOperand &MO = MI->getOperand(j);
std::vector<SUnit *> &UseList = Uses[Reg];
SUnit *&Def = Defs[Reg];
// Optionally add output and anti dependencies.
+ // TODO: Using a latency of 1 here assumes there's no cost for
+ // reusing registers.
+ SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
if (Def && Def != SU)
- Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
- /*PhyReg=*/Reg, Cost, /*isAntiDep=*/MO.isUse());
+ Def->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/Reg));
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
SUnit *&Def = Defs[*Alias];
if (Def && Def != SU)
- Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
- /*PhyReg=*/*Alias, Cost, /*isAntiDep=*/MO.isUse());
+ Def->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/ *Alias));
}
if (MO.isDef()) {
// Add any data dependencies.
for (unsigned i = 0, e = UseList.size(); i != e; ++i)
if (UseList[i] != SU)
- UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
- /*PhysReg=*/Reg, Cost);
+ UseList[i]->addPred(SDep(SU, SDep::Data, SU->Latency, Reg));
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
std::vector<SUnit *> &UseList = Uses[*Alias];
for (unsigned i = 0, e = UseList.size(); i != e; ++i)
if (UseList[i] != SU)
- UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
- /*PhysReg=*/*Alias, Cost);
+ UseList[i]->addPred(SDep(SU, SDep::Data, SU->Latency, *Alias));
}
UseList.clear();
// This is the conservative case. Add dependencies on all memory
// references.
if (Chain)
- Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
Chain = SU;
for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
- PendingLoads[k]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
PendingLoads.clear();
for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
E = MemDefs.end(); I != E; ++I) {
- I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
I->second = SU;
}
for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
MemUses.begin(), E = MemUses.end(); I != E; ++I) {
for (unsigned i = 0, e = I->second.size(); i != e; ++i)
- I->second[i]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ I->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency));
I->second.clear();
}
// See if it is known to just have a single memory reference.
// Handle the def in MemDefs, if there is one.
std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
if (I != MemDefs.end()) {
- I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
+ /*isNormalMemory=*/true));
I->second = SU;
} else {
MemDefs[V] = SU;
MemUses.find(V);
if (J != MemUses.end()) {
for (unsigned i = 0, e = J->second.size(); i != e; ++i)
- J->second[i]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ J->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
+ /*isNormalMemory=*/true));
J->second.clear();
}
// Add a general dependence too, if needed.
if (Chain)
- Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
} else
// Treat all other stores conservatively.
goto new_chain;
const Value *V = MI->memoperands_begin()->getValue();
std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
if (I != MemDefs.end())
- I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
+ /*isNormalMemory=*/true));
MemUses[V].push_back(SU);
// Add a general dependence too, if needed.
if (Chain && (!ChainMMO ||
(ChainMMO->isStore() || ChainMMO->isVolatile())))
- Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
} else if (MI->hasVolatileMemoryRef()) {
// Treat volatile loads conservatively. Note that this includes
// cases where memoperand information is unavailable.
} else {
// A normal load. Just depend on the general chain.
if (Chain)
- Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
PendingLoads.push_back(SU);
}
}
// Add chain edges from the terminator to ensure that all the work of the
// block is completed before any control transfers.
if (Terminator && SU->Succs.empty())
- Terminator->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+ Terminator->addPred(SDep(SU, SDep::Order, SU->Latency));
if (TID.isTerminator() || MI->isLabel())
Terminator = SU;
-
- // Assign the Latency field of SU using target-provided information.
- ComputeLatency(SU);
}
}
void Schedule();
- /// AddPred - This adds the specified node X as a predecessor of
- /// the current node Y if not already.
+ /// AddPred - adds a predecessor edge to SUnit SU.
/// This returns true if this is a new predecessor.
- bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isArtificial,
- unsigned PhyReg = 0, int Cost = 1);
+ bool AddPred(SUnit *SU, const SDep &D) {
+ return SU->addPred(D);
+ }
- /// RemovePred - This removes the specified node N from the predecessors of
- /// the current node M.
- bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isArtificial);
+ /// RemovePred - removes a predecessor edge from SUnit SU.
+ /// This returns true if an edge was removed.
+ bool RemovePred(SUnit *SU, const SDep &D) {
+ return SU->removePred(D);
+ }
private:
- void ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain);
+ void ReleasePred(SUnit *SU, SDep *PredEdge);
void ScheduleNodeBottomUp(SUnit*, unsigned);
SUnit *CopyAndMoveSuccessors(SUnit*);
void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned,
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGFast::ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain) {
+void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) {
+ SUnit *PredSU = PredEdge->getSUnit();
--PredSU->NumSuccsLeft;
#ifndef NDEBUG
// Bottom up: release predecessors
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- ReleasePred(SU, I->Dep, I->isCtrl);
- if (I->Cost < 0) {
+ ReleasePred(SU, &*I);
+ if (I->isAssignedRegDep()) {
// This is a physical register dependency and it's impossible or
// expensive to copy the register. Make sure nothing that can
// clobber the register is scheduled between the predecessor and
// this node.
- if (!LiveRegDefs[I->Reg]) {
+ if (!LiveRegDefs[I->getReg()]) {
++NumLiveRegs;
- LiveRegDefs[I->Reg] = I->Dep;
- LiveRegCycles[I->Reg] = CurCycle;
+ LiveRegDefs[I->getReg()] = I->getSUnit();
+ LiveRegCycles[I->getReg()] = CurCycle;
}
}
}
// Release all the implicit physical register defs that are live.
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->Cost < 0) {
- if (LiveRegCycles[I->Reg] == I->Dep->Cycle) {
+ if (I->isAssignedRegDep()) {
+ if (LiveRegCycles[I->getReg()] == I->getSUnit()->Cycle) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
- assert(LiveRegDefs[I->Reg] == SU &&
+ assert(LiveRegDefs[I->getReg()] == SU &&
"Physical register dependency violated?");
--NumLiveRegs;
- LiveRegDefs[I->Reg] = NULL;
- LiveRegCycles[I->Reg] = 0;
+ LiveRegDefs[I->getReg()] = NULL;
+ LiveRegCycles[I->getReg()] = 0;
}
}
}
SU->isScheduled = true;
}
-/// AddPred - adds an edge from SUnit X to SUnit Y.
-bool ScheduleDAGFast::AddPred(SUnit *Y, SUnit *X, bool isCtrl,
- bool isArtificial, unsigned PhyReg, int Cost) {
- return Y->addPred(X, isCtrl, isArtificial, PhyReg, Cost);
-}
-
-/// RemovePred - This removes the specified node N from the predecessors of
-/// the current node M.
-bool ScheduleDAGFast::RemovePred(SUnit *M, SUnit *N,
- bool isCtrl, bool isArtificial) {
- return M->removePred(N, isCtrl, isArtificial, false);
-}
-
/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
/// successors to the newly created node.
SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) {
LoadSU->Height = SU->Height;
}
- SUnit *ChainPred = NULL;
+ SDep ChainPred;
SmallVector<SDep, 4> ChainSuccs;
SmallVector<SDep, 4> LoadPreds;
SmallVector<SDep, 4> NodePreds;
SmallVector<SDep, 4> NodeSuccs;
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl)
- ChainPred = I->Dep;
- else if (I->Dep->getNode() && I->Dep->getNode()->isOperandOf(LoadNode))
- LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+ if (I->isCtrl())
+ ChainPred = *I;
+ else if (I->getSUnit()->getNode() &&
+ I->getSUnit()->getNode()->isOperandOf(LoadNode))
+ LoadPreds.push_back(*I);
else
- NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+ NodePreds.push_back(*I);
}
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isCtrl)
- ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
- I->isCtrl, I->isArtificial, I->isAntiDep));
+ if (I->isCtrl())
+ ChainSuccs.push_back(*I);
else
- NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
- I->isCtrl, I->isArtificial, I->isAntiDep));
+ NodeSuccs.push_back(*I);
}
- if (ChainPred) {
- RemovePred(SU, ChainPred, true, false);
+ if (ChainPred.getSUnit()) {
+ RemovePred(SU, ChainPred);
if (isNewLoad)
- AddPred(LoadSU, ChainPred, true, false);
+ AddPred(LoadSU, ChainPred);
}
for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
- SDep *Pred = &LoadPreds[i];
- RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
+ const SDep &Pred = LoadPreds[i];
+ RemovePred(SU, Pred);
if (isNewLoad) {
- AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
- Pred->Reg, Pred->Cost);
+ AddPred(LoadSU, Pred);
}
}
for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
- SDep *Pred = &NodePreds[i];
- RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
- AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
- Pred->Reg, Pred->Cost);
+ const SDep &Pred = NodePreds[i];
+ RemovePred(SU, Pred);
+ AddPred(NewSU, Pred);
}
for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
- SDep *Succ = &NodeSuccs[i];
- RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
- AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isArtificial,
- Succ->Reg, Succ->Cost);
+ SDep D = NodeSuccs[i];
+ SUnit *SuccDep = D.getSUnit();
+ D.setSUnit(SU);
+ RemovePred(SuccDep, D);
+ D.setSUnit(NewSU);
+ AddPred(SuccDep, D);
}
for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
- SDep *Succ = &ChainSuccs[i];
- RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
+ SDep D = ChainSuccs[i];
+ SUnit *SuccDep = D.getSUnit();
+ D.setSUnit(SU);
+ RemovePred(SuccDep, D);
if (isNewLoad) {
- AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isArtificial,
- Succ->Reg, Succ->Cost);
+ D.setSUnit(LoadSU);
+ AddPred(SuccDep, D);
}
}
if (isNewLoad) {
- AddPred(NewSU, LoadSU, false, false);
+ AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency));
}
++NumUnfolds;
// New SUnit has the exact same predecessors.
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I)
- if (!I->isArtificial) {
- AddPred(NewSU, I->Dep, I->isCtrl, false, I->Reg, I->Cost);
- NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1);
+ if (!I->isArtificial()) {
+ AddPred(NewSU, *I);
+ NewSU->Depth = std::max(NewSU->Depth, I->getSUnit()->Depth+1);
}
// Only copy scheduled successors. Cut them from old node's successor
// list and move them over.
- SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+ SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isArtificial)
+ if (I->isArtificial())
continue;
- if (I->Dep->isScheduled) {
- NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1);
- AddPred(I->Dep, NewSU, I->isCtrl, false, I->Reg, I->Cost);
- DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+ SUnit *SuccSU = I->getSUnit();
+ if (SuccSU->isScheduled) {
+ NewSU->Height = std::max(NewSU->Height, SuccSU->Height+1);
+ SDep D = *I;
+ D.setSUnit(NewSU);
+ AddPred(SuccSU, D);
+ D.setSUnit(SU);
+ DelDeps.push_back(std::make_pair(SuccSU, D));
}
}
for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
- SUnit *Succ = DelDeps[i].first;
- bool isCtrl = DelDeps[i].second;
- RemovePred(Succ, SU, isCtrl, false);
+ RemovePred(DelDeps[i].first, DelDeps[i].second);
}
++NumDups;
// Only copy scheduled successors. Cut them from old node's successor
// list and move them over.
- SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+ SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isArtificial)
+ if (I->isArtificial())
continue;
- if (I->Dep->isScheduled) {
- AddPred(I->Dep, CopyToSU, I->isCtrl, false, I->Reg, I->Cost);
- DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+ SUnit *SuccSU = I->getSUnit();
+ if (SuccSU->isScheduled) {
+ SDep D = *I;
+ D.setSUnit(CopyToSU);
+ AddPred(SuccSU, D);
+ DelDeps.push_back(std::make_pair(SuccSU, *I));
}
}
for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
- SUnit *Succ = DelDeps[i].first;
- bool isCtrl = DelDeps[i].second;
- RemovePred(Succ, SU, isCtrl, false);
+ RemovePred(DelDeps[i].first, DelDeps[i].second);
}
- AddPred(CopyFromSU, SU, false, false, Reg, -1);
- AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1);
+ AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
+ AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
Copies.push_back(CopyFromSU);
Copies.push_back(CopyToSU);
// If this node would clobber any "live" register, then it's not ready.
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->Cost < 0) {
- unsigned Reg = I->Reg;
- if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->Dep) {
+ if (I->isAssignedRegDep()) {
+ unsigned Reg = I->getReg();
+ if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) {
if (RegAdded.insert(Reg))
LRegs.push_back(Reg);
}
for (const unsigned *Alias = TRI->getAliasSet(Reg);
*Alias; ++Alias)
- if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->Dep) {
+ if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) {
if (RegAdded.insert(*Alias))
LRegs.push_back(*Alias);
}
InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
DOUT << "Adding an edge from SU # " << TrySU->NodeNum
<< " to SU #" << Copies.front()->NodeNum << "\n";
- AddPred(TrySU, Copies.front(), true, true);
+ AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isNormalMemory=*/false,
+ /*isMustAlias=*/false, /*isArtificial=*/true));
NewDef = Copies.back();
}
DOUT << "Adding an edge from SU # " << NewDef->NodeNum
<< " to SU #" << TrySU->NodeNum << "\n";
LiveRegDefs[Reg] = NewDef;
- AddPred(NewDef, TrySU, true, true);
+ AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isNormalMemory=*/false,
+ /*isMustAlias=*/false, /*isArtificial=*/true));
TrySU->isAvailable = false;
CurSU = NewDef;
}
void Schedule();
private:
- void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
+ void ReleaseSucc(SUnit *SU, const SDep &D);
void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
};
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the PendingQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+void ScheduleDAGList::ReleaseSucc(SUnit *SU, const SDep &D) {
+ SUnit *SuccSU = D.getSUnit();
--SuccSU->NumPredsLeft;
#ifndef NDEBUG
// Compute the cycle when this SUnit actually becomes available. This
// is the max of the start time of all predecessors plus their latencies.
- // If this is a token edge, we don't need to wait for the latency of the
- // preceeding instruction (e.g. a long-latency load) unless there is also
- // some other data dependence.
- unsigned PredDoneCycle = SU->Cycle;
- if (!isChain)
- PredDoneCycle += SU->Latency;
- else if (SU->Latency)
- PredDoneCycle += 1;
+ unsigned PredDoneCycle = SU->Cycle + SU->Latency;
SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle);
if (SuccSU->NumPredsLeft == 0) {
// Top down: release successors.
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- ReleaseSucc(SU, I->Dep, I->isCtrl);
+ ReleaseSucc(SU, *I);
SU->isScheduled = true;
AvailableQueue->ScheduledNode(SU);
return Topo.WillCreateCycle(SU, TargetSU);
}
- /// AddPred - This adds the specified node X as a predecessor of
- /// the current node Y if not already.
+ /// AddPred - adds a predecessor edge to SUnit SU.
/// This returns true if this is a new predecessor.
/// Updates the topological ordering if required.
- bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isArtificial,
- unsigned PhyReg = 0, int Cost = 1) {
- Topo.AddPred(Y, X);
- return Y->addPred(X, isCtrl, isArtificial, PhyReg, Cost);
+ bool AddPred(SUnit *SU, const SDep &D) {
+ Topo.AddPred(SU, D.getSUnit());
+ return SU->addPred(D);
}
- /// RemovePred - This removes the specified node N from the predecessors of
- /// the current node M. Updates the topological ordering if required.
- bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isArtificial) {
- Topo.RemovePred(M, N);
- return M->removePred(N, isCtrl, isArtificial, false);
+ /// RemovePred - removes a predecessor edge from SUnit SU.
+ /// This returns true if an edge was removed.
+ /// Updates the topological ordering if required.
+ bool RemovePred(SUnit *SU, const SDep &D) {
+ Topo.RemovePred(SU, D.getSUnit());
+ return SU->removePred(D);
}
private:
- void ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain);
- void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
- void CapturePred(SUnit*, SUnit*, bool);
+ void ReleasePred(SUnit *SU, SDep *PredEdge);
+ void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
+ void CapturePred(SDep *PredEdge);
void ScheduleNodeBottomUp(SUnit*, unsigned);
void ScheduleNodeTopDown(SUnit*, unsigned);
void UnscheduleNodeBottomUp(SUnit*);
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (!I->isCtrl)
- OperandSeen.insert(I->Dep->OrigNode);
+ if (!I->isCtrl())
+ OperandSeen.insert(I->getSUnit()->OrigNode);
}
}
}
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGRRList::ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain) {
+void ScheduleDAGRRList::ReleasePred(SUnit *SU, SDep *PredEdge) {
+ SUnit *PredSU = PredEdge->getSUnit();
--PredSU->NumSuccsLeft;
#ifndef NDEBUG
// Bottom up: release predecessors
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- ReleasePred(SU, I->Dep, I->isCtrl);
- if (I->Cost < 0) {
+ ReleasePred(SU, &*I);
+ if (I->isAssignedRegDep()) {
// This is a physical register dependency and it's impossible or
// expensive to copy the register. Make sure nothing that can
// clobber the register is scheduled between the predecessor and
// this node.
- if (!LiveRegDefs[I->Reg]) {
+ if (!LiveRegDefs[I->getReg()]) {
++NumLiveRegs;
- LiveRegDefs[I->Reg] = I->Dep;
- LiveRegCycles[I->Reg] = CurCycle;
+ LiveRegDefs[I->getReg()] = I->getSUnit();
+ LiveRegCycles[I->getReg()] = CurCycle;
}
}
}
// Release all the implicit physical register defs that are live.
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->Cost < 0) {
- if (LiveRegCycles[I->Reg] == I->Dep->Cycle) {
+ if (I->isAssignedRegDep()) {
+ if (LiveRegCycles[I->getReg()] == I->getSUnit()->Cycle) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
- assert(LiveRegDefs[I->Reg] == SU &&
+ assert(LiveRegDefs[I->getReg()] == SU &&
"Physical register dependency violated?");
--NumLiveRegs;
- LiveRegDefs[I->Reg] = NULL;
- LiveRegCycles[I->Reg] = 0;
+ LiveRegDefs[I->getReg()] = NULL;
+ LiveRegCycles[I->getReg()] = 0;
}
}
}
/// CapturePred - This does the opposite of ReleasePred. Since SU is being
/// unscheduled, incrcease the succ left count of its predecessors. Remove
/// them from AvailableQueue if necessary.
-void ScheduleDAGRRList::CapturePred(SUnit *PredSU, SUnit *SU, bool isChain) {
+void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
+ SUnit *PredSU = PredEdge->getSUnit();
if (PredSU->isAvailable) {
PredSU->isAvailable = false;
if (!PredSU->isPending)
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- CapturePred(I->Dep, SU, I->isCtrl);
- if (I->Cost < 0 && SU->Cycle == LiveRegCycles[I->Reg]) {
+ CapturePred(&*I);
+ if (I->isAssignedRegDep() && SU->Cycle == LiveRegCycles[I->getReg()]) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
- assert(LiveRegDefs[I->Reg] == I->Dep &&
+ assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
"Physical register dependency violated?");
--NumLiveRegs;
- LiveRegDefs[I->Reg] = NULL;
- LiveRegCycles[I->Reg] = 0;
+ LiveRegDefs[I->getReg()] = NULL;
+ LiveRegCycles[I->getReg()] = 0;
}
}
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->Cost < 0) {
- if (!LiveRegDefs[I->Reg]) {
- LiveRegDefs[I->Reg] = SU;
+ if (I->isAssignedRegDep()) {
+ if (!LiveRegDefs[I->getReg()]) {
+ LiveRegDefs[I->getReg()] = SU;
++NumLiveRegs;
}
- if (I->Dep->Cycle < LiveRegCycles[I->Reg])
- LiveRegCycles[I->Reg] = I->Dep->Cycle;
+ if (I->getSUnit()->Cycle < LiveRegCycles[I->getReg()])
+ LiveRegCycles[I->getReg()] = I->getSUnit()->Cycle;
}
}
NewSU->Height = SU->Height;
ComputeLatency(NewSU);
- SUnit *ChainPred = NULL;
+ SDep ChainPred;
SmallVector<SDep, 4> ChainSuccs;
SmallVector<SDep, 4> LoadPreds;
SmallVector<SDep, 4> NodePreds;
SmallVector<SDep, 4> NodeSuccs;
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl)
- ChainPred = I->Dep;
- else if (I->Dep->getNode() && I->Dep->getNode()->isOperandOf(LoadNode))
- LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+ if (I->isCtrl())
+ ChainPred = *I;
+ else if (I->getSUnit()->getNode() &&
+ I->getSUnit()->getNode()->isOperandOf(LoadNode))
+ LoadPreds.push_back(*I);
else
- NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+ NodePreds.push_back(*I);
}
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isCtrl)
- ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
- I->isCtrl, I->isArtificial, I->isAntiDep));
+ if (I->isCtrl())
+ ChainSuccs.push_back(*I);
else
- NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
- I->isCtrl, I->isArtificial, I->isAntiDep));
+ NodeSuccs.push_back(*I);
}
- if (ChainPred) {
- RemovePred(SU, ChainPred, true, false);
+ if (ChainPred.getSUnit()) {
+ RemovePred(SU, ChainPred);
if (isNewLoad)
- AddPred(LoadSU, ChainPred, true, false);
+ AddPred(LoadSU, ChainPred);
}
for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
- SDep *Pred = &LoadPreds[i];
- RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
+ const SDep &Pred = LoadPreds[i];
+ RemovePred(SU, Pred);
if (isNewLoad) {
- AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
- Pred->Reg, Pred->Cost);
+ AddPred(LoadSU, Pred);
}
}
for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
- SDep *Pred = &NodePreds[i];
- RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
- AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
- Pred->Reg, Pred->Cost);
+ const SDep &Pred = NodePreds[i];
+ RemovePred(SU, Pred);
+ AddPred(NewSU, Pred);
}
for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
- SDep *Succ = &NodeSuccs[i];
- RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
- AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isArtificial,
- Succ->Reg, Succ->Cost);
+ SDep D = NodeSuccs[i];
+ SUnit *SuccDep = D.getSUnit();
+ D.setSUnit(SU);
+ RemovePred(SuccDep, D);
+ D.setSUnit(NewSU);
+ AddPred(SuccDep, D);
}
for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
- SDep *Succ = &ChainSuccs[i];
- RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
+ SDep D = ChainSuccs[i];
+ SUnit *SuccDep = D.getSUnit();
+ D.setSUnit(SU);
+ RemovePred(SuccDep, D);
if (isNewLoad) {
- AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isArtificial,
- Succ->Reg, Succ->Cost);
+ D.setSUnit(LoadSU);
+ AddPred(SuccDep, D);
}
}
if (isNewLoad) {
- AddPred(NewSU, LoadSU, false, false);
+ AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency));
}
if (isNewLoad)
// New SUnit has the exact same predecessors.
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I)
- if (!I->isArtificial) {
- AddPred(NewSU, I->Dep, I->isCtrl, false, I->Reg, I->Cost);
- NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1);
+ if (!I->isArtificial()) {
+ AddPred(NewSU, *I);
+ NewSU->Depth = std::max(NewSU->Depth, I->getSUnit()->Depth+1);
}
// Only copy scheduled successors. Cut them from old node's successor
// list and move them over.
- SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+ SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isArtificial)
+ if (I->isArtificial())
continue;
- if (I->Dep->isScheduled) {
- NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1);
- AddPred(I->Dep, NewSU, I->isCtrl, false, I->Reg, I->Cost);
- DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+ SUnit *SuccSU = I->getSUnit();
+ if (SuccSU->isScheduled) {
+ NewSU->Height = std::max(NewSU->Height, SuccSU->Height+1);
+ SDep D = *I;
+ D.setSUnit(NewSU);
+ AddPred(SuccSU, D);
+ D.setSUnit(SU);
+ DelDeps.push_back(std::make_pair(SuccSU, D));
}
}
for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
- SUnit *Succ = DelDeps[i].first;
- bool isCtrl = DelDeps[i].second;
- RemovePred(Succ, SU, isCtrl, false);
+ RemovePred(DelDeps[i].first, DelDeps[i].second);
}
AvailableQueue->updateNode(SU);
// Only copy scheduled successors. Cut them from old node's successor
// list and move them over.
- SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+ SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isArtificial)
+ if (I->isArtificial())
continue;
- if (I->Dep->isScheduled) {
- CopyToSU->Height = std::max(CopyToSU->Height, I->Dep->Height+1);
- AddPred(I->Dep, CopyToSU, I->isCtrl, false, I->Reg, I->Cost);
- DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+ SUnit *SuccSU = I->getSUnit();
+ if (SuccSU->isScheduled) {
+ SDep D = *I;
+ D.setSUnit(CopyToSU);
+ AddPred(SuccSU, D);
+ DelDeps.push_back(std::make_pair(SuccSU, *I));
}
}
for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
- SUnit *Succ = DelDeps[i].first;
- bool isCtrl = DelDeps[i].second;
- RemovePred(Succ, SU, isCtrl, false);
+ RemovePred(DelDeps[i].first, DelDeps[i].second);
}
- AddPred(CopyFromSU, SU, false, false, Reg, -1);
- AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1);
+ AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
+ AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
AvailableQueue->updateNode(SU);
AvailableQueue->addNode(CopyFromSU);
// If this node would clobber any "live" register, then it's not ready.
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->Cost < 0) {
- unsigned Reg = I->Reg;
- if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->Dep) {
+ if (I->isAssignedRegDep()) {
+ unsigned Reg = I->getReg();
+ if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) {
if (RegAdded.insert(Reg))
LRegs.push_back(Reg);
}
for (const unsigned *Alias = TRI->getAliasSet(Reg);
*Alias; ++Alias)
- if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->Dep) {
+ if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) {
if (RegAdded.insert(*Alias))
LRegs.push_back(*Alias);
}
OldSU->isAvailable = false;
AvailableQueue->remove(OldSU);
}
- AddPred(TrySU, OldSU, true, true);
+ AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isNormalMemory=*/false,
+ /*isMustAlias=*/false, /*isArtificial=*/true));
// If one or more successors has been unscheduled, then the current
// node is no longer avaialable. Schedule a successor that's now
// available instead.
InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
DOUT << "Adding an edge from SU # " << TrySU->NodeNum
<< " to SU #" << Copies.front()->NodeNum << "\n";
- AddPred(TrySU, Copies.front(), true, true);
+ AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isMustAlias=*/false,
+ /*isArtificial=*/true));
NewDef = Copies.back();
}
DOUT << "Adding an edge from SU # " << NewDef->NodeNum
<< " to SU #" << TrySU->NodeNum << "\n";
LiveRegDefs[Reg] = NewDef;
- AddPred(NewDef, TrySU, true, true);
+ AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isMustAlias=*/false,
+ /*isArtificial=*/true));
TrySU->isAvailable = false;
CurSU = NewDef;
}
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
+ SUnit *SuccSU = SuccEdge->getSUnit();
--SuccSU->NumPredsLeft;
#ifndef NDEBUG
// Top down: release successors
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- ReleaseSucc(SU, I->Dep, I->isCtrl);
+ ReleaseSucc(SU, &*I);
SU->isScheduled = true;
AvailableQueue->ScheduledNode(SU);
unsigned Extra = 0;
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl) continue; // ignore chain preds
- SUnit *PredSU = I->Dep;
+ if (I->isCtrl()) continue; // ignore chain preds
+ SUnit *PredSU = I->getSUnit();
unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
if (PredSethiUllman > SethiUllmanNumber) {
SethiUllmanNumber = PredSethiUllman;
Extra = 0;
- } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl)
+ } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl())
++Extra;
}
unsigned MaxCycle = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- unsigned Cycle = I->Dep->Cycle;
+ unsigned Cycle = I->getSUnit()->Cycle;
// If there are bunch of CopyToRegs stacked up, they should be considered
// to be at the same position.
- if (I->Dep->getNode() && I->Dep->getNode()->getOpcode() == ISD::CopyToReg)
- Cycle = closestSucc(I->Dep)+1;
+ if (I->getSUnit()->getNode() &&
+ I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
+ Cycle = closestSucc(I->getSUnit())+1;
if (Cycle > MaxCycle)
MaxCycle = Cycle;
}
unsigned Scratches = 0;
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl) continue; // ignore chain preds
- if (!I->Dep->getNode() || I->Dep->getNode()->getOpcode() != ISD::CopyFromReg)
+ if (I->isCtrl()) continue; // ignore chain preds
+ if (!I->getSUnit()->getNode() ||
+ I->getSUnit()->getNode()->getOpcode() != ISD::CopyFromReg)
Scratches++;
}
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isCtrl) continue; // ignore chain succs
- if (!I->Dep->getNode() || I->Dep->getNode()->getOpcode() != ISD::CopyToReg)
+ if (I->isCtrl()) continue; // ignore chain succs
+ if (!I->getSUnit()->getNode() ||
+ I->getSUnit()->getNode()->getOpcode() != ISD::CopyToReg)
Scratches += 10;
}
return Scratches;
static bool hasCopyToRegUse(const SUnit *SU) {
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isCtrl) continue;
- const SUnit *SuccSU = I->Dep;
+ if (I->isCtrl()) continue;
+ const SUnit *SuccSU = I->getSUnit();
if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
return true;
}
if (!DUSU) continue;
for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
E = DUSU->Succs.end(); I != E; ++I) {
- if (I->isCtrl) continue;
- SUnit *SuccSU = I->Dep;
+ if (I->isCtrl()) continue;
+ SUnit *SuccSU = I->getSUnit();
if (SuccSU == SU)
continue;
// Be conservative. Ignore if nodes aren't at roughly the same
!scheduleDAG->IsReachable(SuccSU, SU)) {
DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum
<< " to SU #" << SuccSU->NodeNum << "\n";
- scheduleDAG->AddPred(SU, SuccSU, true, true);
+ scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isMustAlias=*/false,
+ /*isArtificial=*/true));
}
}
}
unsigned Sum = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- const SUnit *SuccSU = I->Dep;
+ const SUnit *SuccSU = I->getSUnit();
for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
EE = SuccSU->Preds.end(); II != EE; ++II) {
- SUnit *PredSU = II->Dep;
+ SUnit *PredSU = II->getSUnit();
if (!PredSU->isScheduled)
if (++Sum > Limit)
return Sum;
int Cost = 1;
// Determine if this is a physical register dependency.
CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
- SU->addPred(OpSU, isChain, false, PhysReg, Cost);
+ assert((PhysReg == 0 || !isChain) &&
+ "Chain dependence via physreg data?");
+ SU->addPred(SDep(OpSU, isChain ? SDep::Order : SDep::Data,
+ OpSU->Latency, PhysReg));
}
}
}
projects / oota-llvm.git / commitdiff