#define LLVM_CODEGEN_SCHEDULEDAG_H
#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/GraphTraits.h"
class SUnit;
class MachineConstantPool;
class MachineFunction;
- class MachineModuleInfo;
class MachineRegisterInfo;
class MachineInstr;
class TargetRegisterInfo;
class SDNode;
class TargetInstrInfo;
class TargetInstrDesc;
- class TargetLowering;
class TargetMachine;
class TargetRegisterClass;
template<class Graph> class GraphWriter;
}
};
+ template <>
+ struct isPodLike<SDep> { static const bool value = true; };
+
/// SUnit - Scheduling unit. This is a node in the scheduling DAG.
class SUnit {
private:
public:
SUnit *OrigNode; // If not this, the node from which
// this node was cloned.
-
- // Preds/Succs - The SUnits before/after us in the graph. The boolean value
- // is true if the edge is a token chain edge, false if it is a value edge.
+
+ // Preds/Succs - The SUnits before/after us in the graph.
SmallVector<SDep, 4> Preds; // All sunit predecessors.
SmallVector<SDep, 4> Succs; // All sunit successors.
typedef SmallVector<SDep, 4>::iterator succ_iterator;
typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
-
+
unsigned NodeNum; // Entry # of node in the node vector.
unsigned NodeQueueId; // Queue id of node.
- unsigned short Latency; // Node latency.
unsigned NumPreds; // # of SDep::Data preds.
unsigned NumSuccs; // # of SDep::Data sucss.
unsigned NumPredsLeft; // # of preds not scheduled.
unsigned NumSuccsLeft; // # of succs not scheduled.
+ unsigned short Latency; // Node latency.
+ bool isCall : 1; // Is a function call.
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 isScheduled : 1; // True once scheduled.
bool isScheduleHigh : 1; // True if preferable to schedule high.
bool isCloned : 1; // True if this node has been cloned.
+ Sched::Preference SchedulingPref; // Scheduling preference.
+
+ SmallVector<MachineInstr*, 4> DbgInstrList; // dbg_values referencing this.
private:
bool isDepthCurrent : 1; // True if Depth is current.
bool isHeightCurrent : 1; // True if Height is current.
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),
- hasPhysRegClobbers(false),
+ : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum),
+ NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
+ NumSuccsLeft(0), Latency(0),
+ isCall(false), isTwoAddress(false), isCommutable(false),
+ hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
isScheduleHigh(false), isCloned(false),
+ SchedulingPref(Sched::None),
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),
- hasPhysRegClobbers(false),
+ : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum),
+ NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
+ NumSuccsLeft(0), Latency(0),
+ isCall(false), isTwoAddress(false), isCommutable(false),
+ hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
isScheduleHigh(false), isCloned(false),
+ SchedulingPref(Sched::None),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
CopyDstRC(NULL), CopySrcRC(NULL) {}
/// SUnit - Construct a placeholder SUnit.
SUnit()
- : Node(0), Instr(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),
+ : Node(0), Instr(0), OrigNode(0), NodeNum(~0u),
+ NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
+ NumSuccsLeft(0), Latency(0),
+ isCall(false), isTwoAddress(false), isCommutable(false),
+ hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
isScheduleHigh(false), isCloned(false),
+ SchedulingPref(Sched::None),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
CopyDstRC(NULL), CopySrcRC(NULL) {}
return Node;
}
+ /// isInstr - Return true if this SUnit refers to a machine instruction as
+ /// opposed to an SDNode.
+ bool isInstr() const { return Instr; }
+
/// setInstr - Assign the instruction for the SUnit.
/// This may be used during post-regalloc scheduling.
void setInstr(MachineInstr *MI) {
/// 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();
+ 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();
+ 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.
+ /// 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.
+ /// 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
return true;
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)
return true;
return false;
}
-
+
void dump(const ScheduleDAG *G) const;
void dumpAll(const ScheduleDAG *G) const;
void print(raw_ostream &O, const ScheduleDAG *G) const;
//===--------------------------------------------------------------------===//
/// SchedulingPriorityQueue - This interface is used to plug different
/// priorities computation algorithms into the list scheduler. It implements
- /// the interface of a standard priority queue, where nodes are inserted in
+ /// the interface of a standard priority queue, where nodes are inserted in
/// arbitrary order and returned in priority order. The computation of the
/// priority and the representation of the queue are totally up to the
/// implementation to decide.
- ///
+ ///
class SchedulingPriorityQueue {
+ unsigned CurCycle;
+ bool HasReadyFilter;
public:
+ SchedulingPriorityQueue(bool rf = false):
+ CurCycle(0), HasReadyFilter(rf) {}
virtual ~SchedulingPriorityQueue() {}
-
+
+ virtual bool isBottomUp() const = 0;
+
virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
virtual void addNode(const SUnit *SU) = 0;
virtual void updateNode(const SUnit *SU) = 0;
virtual void releaseState() = 0;
- virtual unsigned size() const = 0;
virtual bool empty() const = 0;
+
+ bool hasReadyFilter() const { return HasReadyFilter; }
+
+ virtual bool isReady(SUnit *U) const {
+ assert(!HasReadyFilter && "The ready filter must override isReady()");
+ return true;
+ }
virtual void push(SUnit *U) = 0;
-
- virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
+
+ void push_all(const std::vector<SUnit *> &Nodes) {
+ for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
+ E = Nodes.end(); I != E; ++I)
+ push(*I);
+ }
+
virtual SUnit *pop() = 0;
virtual void remove(SUnit *SU) = 0;
+ virtual void dump(ScheduleDAG *DAG) const {}
+
/// ScheduledNode - As each node is scheduled, this method is invoked. This
/// allows the priority function to adjust the priority of related
/// unscheduled nodes, for example.
virtual void ScheduledNode(SUnit *) {}
virtual void UnscheduledNode(SUnit *) {}
+
+ void setCurCycle(unsigned Cycle) {
+ CurCycle = Cycle;
+ }
+
+ unsigned getCurCycle() const {
+ return CurCycle;
+ }
};
class ScheduleDAG {
const TargetMachine &TM; // Target processor
const TargetInstrInfo *TII; // Target instruction information
const TargetRegisterInfo *TRI; // Target processor register info
- 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.
virtual ~ScheduleDAG();
+ /// getInstrDesc - Return the TargetInstrDesc of this SUnit.
+ /// Return NULL for SDNodes without a machine opcode.
+ const TargetInstrDesc *getInstrDesc(const SUnit *SU) const {
+ if (SU->isInstr()) return &SU->getInstr()->getDesc();
+ return getNodeDesc(SU->getNode());
+ }
+
/// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
/// using 'dot'.
///
void viewGraph();
-
+
/// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock
/// according to the order specified in Sequence.
///
- virtual MachineBasicBlock*
- EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*>*) = 0;
+ virtual MachineBasicBlock *EmitSchedule() = 0;
void dumpSchedule() const;
void EmitNoop();
void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
+
+ private:
+ // Return the TargetInstrDesc of this SDNode or NULL.
+ const TargetInstrDesc *getNodeDesc(const SDNode *Node) const;
};
class SUnitIterator : public std::iterator<std::forward_iterator_tag,
/// Visited - a set of nodes visited during a DFS traversal.
BitVector Visited;
- /// DFS - make a DFS traversal and mark all nodes affected by the
+ /// DFS - make a DFS traversal and mark all nodes affected by the
/// edge insertion. These nodes will later get new topological indexes
/// by means of the Shift method.
void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
public:
explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits);
- /// InitDAGTopologicalSorting - create the initial topological
+ /// InitDAGTopologicalSorting - create the initial topological
/// ordering from the DAG to be scheduled.
void InitDAGTopologicalSorting();