#include "llvm/ADT/PointerIntPair.h"
namespace llvm {
- struct SUnit;
+ class AliasAnalysis;
+ class SUnit;
class MachineConstantPool;
class MachineFunction;
class MachineModuleInfo;
class MachineInstr;
class TargetRegisterInfo;
class ScheduleDAG;
- class SelectionDAG;
class SDNode;
class TargetInstrInfo;
class TargetInstrDesc;
return Latency;
}
+ /// setLatency - Set the latency for this edge.
+ void setLatency(unsigned Lat) {
+ Latency = Lat;
+ }
+
//// getSUnit - Return the SUnit to which this edge points.
SUnit *getSUnit() const {
return Dep.getPointer();
return getKind() != Data;
}
+ /// isNormalMemory - Test if this is an Order dependence between two
+ /// memory accesses where both sides of the dependence access memory
+ /// in non-volatile and fully modeled ways.
+ bool isNormalMemory() const {
+ return getKind() == Order && Contents.Order.isNormalMemory;
+ }
+
/// 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.
};
/// SUnit - Scheduling unit. This is a node in the scheduling DAG.
- struct SUnit {
+ class SUnit {
private:
SDNode *Node; // Representative node.
MachineInstr *Instr; // Alternatively, a MachineInstr.
+ MachineInstr *DbgInstr; // A dbg_value referencing this.
public:
SUnit *OrigNode; // If not this, the node from which
// this node was cloned.
unsigned NodeNum; // Entry # of node in the node vector.
unsigned NodeQueueId; // Queue id of node.
unsigned short Latency; // Node latency.
- short NumPreds; // # of SDep::Data preds.
- short NumSuccs; // # of SDep::Data sucss.
- short NumPredsLeft; // # of preds not scheduled.
- short NumSuccsLeft; // # of succs not scheduled.
+ unsigned NumPreds; // # of SDep::Data preds.
+ unsigned NumSuccs; // # of SDep::Data sucss.
+ unsigned NumPredsLeft; // # of preds not scheduled.
+ unsigned NumSuccsLeft; // # of succs not scheduled.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isCommutable : 1; // Is a commutable instruction.
bool hasPhysRegDefs : 1; // Has physreg defs that are being used.
+ bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not.
bool isPending : 1; // True once pending.
bool isAvailable : 1; // True once available.
bool isScheduled : 1; // True once scheduled.
- unsigned CycleBound; // Upper/lower cycle to be scheduled at.
- unsigned Cycle; // Once scheduled, the cycle of the op.
- unsigned Depth; // Node depth;
- unsigned Height; // Node height;
+ bool isScheduleHigh : 1; // True if preferable to schedule high.
+ bool isCloned : 1; // True if this node has been cloned.
+ private:
+ bool isDepthCurrent : 1; // True if Depth is current.
+ bool isHeightCurrent : 1; // True if Height is current.
+ unsigned Depth; // Node depth.
+ unsigned Height; // Node height.
+ public:
const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
const TargetRegisterClass *CopySrcRC;
/// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
/// an SDNode and any nodes flagged to it.
SUnit(SDNode *node, unsigned nodenum)
- : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
- Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
- isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
+ : Node(node), Instr(0), DbgInstr(0), OrigNode(0), NodeNum(nodenum),
+ NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
+ NumSuccsLeft(0), isTwoAddress(false), isCommutable(false),
+ hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
- CycleBound(0), Cycle(~0u), Depth(0), Height(0),
+ isScheduleHigh(false), isCloned(false),
+ isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
CopyDstRC(NULL), CopySrcRC(NULL) {}
/// SUnit - Construct an SUnit for post-regalloc scheduling to represent
/// a MachineInstr.
SUnit(MachineInstr *instr, unsigned nodenum)
- : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
- Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
- isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
+ : Node(0), Instr(instr), DbgInstr(0), OrigNode(0), NodeNum(nodenum),
+ NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
+ NumSuccsLeft(0), isTwoAddress(false), isCommutable(false),
+ hasPhysRegDefs(false), hasPhysRegClobbers(false),
+ isPending(false), isAvailable(false), isScheduled(false),
+ isScheduleHigh(false), isCloned(false),
+ isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
+ CopyDstRC(NULL), CopySrcRC(NULL) {}
+
+ /// SUnit - Construct a placeholder SUnit.
+ SUnit()
+ : Node(0), Instr(0), DbgInstr(0), OrigNode(0), NodeNum(~0u),
+ NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
+ NumSuccsLeft(0), isTwoAddress(false), isCommutable(false),
+ hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
- CycleBound(0), Cycle(~0u), Depth(0), Height(0),
+ isScheduleHigh(false), isCloned(false),
+ isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
CopyDstRC(NULL), CopySrcRC(NULL) {}
/// setNode - Assign the representative SDNode for this SUnit.
return Instr;
}
+ /// setDbgInstr - Assign the debug instruction for the SUnit.
+ /// This may be used during post-regalloc scheduling.
+ void setDbgInstr(MachineInstr *MI) {
+ assert(!Node && "Setting debug MachineInstr of SUnit with SDNode!");
+ DbgInstr = MI;
+ }
+
+ /// getDbgInstr - Return the debug MachineInstr for this SUnit.
+ /// This may be used during post-regalloc scheduling.
+ MachineInstr *getDbgInstr() const {
+ assert(!Node && "Reading debug MachineInstr of SUnit with SDNode!");
+ return DbgInstr;
+ }
+
/// 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(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] == D)
- return false;
- // 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;
- }
- if (!N->isScheduled)
- ++NumPredsLeft;
- if (!isScheduled)
- ++N->NumSuccsLeft;
- return true;
- }
+ /// specified node.
+ void addPred(const SDep &D);
/// 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 == 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 == P) {
- FoundSucc = true;
- N->Succs.erase(II);
- break;
- }
- assert(FoundSucc && "Mismatching preds / succs lists!");
- Preds.erase(I);
- // Update the bookkeeping;
- if (D.getKind() == SDep::Data) {
- --NumPreds;
- --N->NumSuccs;
- }
- if (!N->isScheduled)
- --NumPredsLeft;
- if (!isScheduled)
- --N->NumSuccsLeft;
- return true;
- }
- return false;
- }
-
+ /// the specified node.
+ void removePred(const SDep &D);
+
+ /// getDepth - Return the depth of this node, which is the length of the
+ /// maximum path up to any node with has no predecessors.
+ unsigned getDepth() const {
+ if (!isDepthCurrent)
+ const_cast<SUnit *>(this)->ComputeDepth();
+ return Depth;
+ }
+
+ /// getHeight - Return the height of this node, which is the length of the
+ /// maximum path down to any node with has no successors.
+ unsigned getHeight() const {
+ if (!isHeightCurrent)
+ const_cast<SUnit *>(this)->ComputeHeight();
+ return Height;
+ }
+
+ /// setDepthToAtLeast - If NewDepth is greater than this node's
+ /// depth value, set it to be the new depth value. This also
+ /// recursively marks successor nodes dirty.
+ void setDepthToAtLeast(unsigned NewDepth);
+
+ /// setDepthToAtLeast - If NewDepth is greater than this node's
+ /// depth value, set it to be the new height value. This also
+ /// recursively marks predecessor nodes dirty.
+ void setHeightToAtLeast(unsigned NewHeight);
+
+ /// setDepthDirty - Set a flag in this node to indicate that its
+ /// stored Depth value will require recomputation the next time
+ /// getDepth() is called.
+ void setDepthDirty();
+
+ /// setHeightDirty - Set a flag in this node to indicate that its
+ /// stored Height value will require recomputation the next time
+ /// getHeight() is called.
+ void setHeightDirty();
+
+ /// isPred - Test if node N is a predecessor of this node.
bool isPred(SUnit *N) {
for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
if (Preds[i].getSUnit() == N)
return false;
}
+ /// isSucc - Test if node N is a successor of this node.
bool isSucc(SUnit *N) {
for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
if (Succs[i].getSUnit() == N)
void dump(const ScheduleDAG *G) const;
void dumpAll(const ScheduleDAG *G) const;
void print(raw_ostream &O, const ScheduleDAG *G) const;
+
+ private:
+ void ComputeDepth();
+ void ComputeHeight();
};
//===--------------------------------------------------------------------===//
class ScheduleDAG {
public:
- SelectionDAG *DAG; // DAG of the current basic block
- MachineBasicBlock *BB; // Current basic block
+ MachineBasicBlock *BB; // The block in which to insert instructions
+ MachineBasicBlock::iterator InsertPos;// The position to insert instructions
const TargetMachine &TM; // Target processor
const TargetInstrInfo *TII; // Target instruction information
const TargetRegisterInfo *TRI; // Target processor register info
- TargetLowering *TLI; // Target lowering info
- MachineFunction *MF; // Machine function
+ const TargetLowering *TLI; // Target lowering info
+ MachineFunction &MF; // Machine function
MachineRegisterInfo &MRI; // Virtual/real register map
MachineConstantPool *ConstPool; // Target constant pool
std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s
// represent noop instructions.
std::vector<SUnit> SUnits; // The scheduling units.
+ SUnit EntrySU; // Special node for the region entry.
+ SUnit ExitSU; // Special node for the region exit.
- ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
- const TargetMachine &tm);
+ explicit ScheduleDAG(MachineFunction &mf);
virtual ~ScheduleDAG();
///
void viewGraph();
- /// Run - perform scheduling.
- ///
- void Run();
-
- /// BuildSchedUnits - Build SUnits and set up their Preds and Succs
- /// to form the scheduling dependency graph.
- ///
- virtual void BuildSchedUnits() = 0;
-
- /// ComputeLatency - Compute node latency.
- ///
- virtual void ComputeLatency(SUnit *SU) { SU->Latency = 1; }
-
- /// CalculateDepths, CalculateHeights - Calculate node depth / height.
+ /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock
+ /// according to the order specified in Sequence.
///
- void CalculateDepths();
- void CalculateHeights();
-
- protected:
- /// EmitNoop - Emit a noop instruction.
- ///
- void EmitNoop();
-
- public:
- virtual MachineBasicBlock *EmitSchedule() = 0;
+ virtual MachineBasicBlock*
+ EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*>*) = 0;
void dumpSchedule() const;
- /// Schedule - Order nodes according to selected style, filling
- /// in the Sequence member.
- ///
- virtual void Schedule() = 0;
-
virtual void dumpNode(const SUnit *SU) const = 0;
/// getGraphNodeLabel - Return a label for an SUnit node in a visualization
#endif
protected:
- void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO);
+ /// Run - perform scheduling.
+ ///
+ void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos);
+
+ /// BuildSchedGraph - Build SUnits and set up their Preds and Succs
+ /// to form the scheduling dependency graph.
+ ///
+ virtual void BuildSchedGraph(AliasAnalysis *AA) = 0;
- void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
+ /// ComputeLatency - Compute node latency.
+ ///
+ virtual void ComputeLatency(SUnit *SU) = 0;
- private:
- /// EmitLiveInCopy - Emit a copy for a live in physical register. If the
- /// physical register has only a single copy use, then coalesced the copy
- /// if possible.
- void EmitLiveInCopy(MachineBasicBlock *MBB,
- MachineBasicBlock::iterator &InsertPos,
- unsigned VirtReg, unsigned PhysReg,
- const TargetRegisterClass *RC,
- DenseMap<MachineInstr*, unsigned> &CopyRegMap);
-
- /// EmitLiveInCopies - If this is the first basic block in the function,
- /// and if it has live ins that need to be copied into vregs, emit the
- /// copies into the top of the block.
- void EmitLiveInCopies(MachineBasicBlock *MBB);
+ /// ComputeOperandLatency - Override dependence edge latency using
+ /// operand use/def information
+ ///
+ virtual void ComputeOperandLatency(SUnit *, SUnit *,
+ SDep&) const { }
+
+ /// Schedule - Order nodes according to selected style, filling
+ /// in the Sequence member.
+ ///
+ virtual void Schedule() = 0;
+
+ /// ForceUnitLatencies - Return true if all scheduling edges should be given
+ /// a latency value of one. The default is to return false; schedulers may
+ /// override this as needed.
+ virtual bool ForceUnitLatencies() const { return false; }
+
+ /// EmitNoop - Emit a noop instruction.
+ ///
+ void EmitNoop();
+
+ void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
};
- class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> {
+ class SUnitIterator : public std::iterator<std::forward_iterator_tag,
+ SUnit, ptrdiff_t> {
SUnit *Node;
unsigned Operand;
bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
const SUnitIterator &operator=(const SUnitIterator &I) {
- assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
+ assert(I.Node==Node && "Cannot assign iterators to two different nodes!");
Operand = I.Operand;
return *this;
}