#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
#define LLVM_CODEGEN_SCHEDULEDAG_H
-#include "llvm/CodeGen/MachineBasicBlock.h"
-#include "llvm/Target/TargetLowering.h"
-#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Target/TargetLowering.h"
namespace llvm {
- class AliasAnalysis;
class SUnit;
class MachineConstantPool;
class MachineFunction;
class MachineRegisterInfo;
class MachineInstr;
+ struct MCSchedClassDesc;
class TargetRegisterInfo;
class ScheduleDAG;
class SDNode;
Order ///< Any other ordering dependency.
};
+ // Strong dependencies must be respected by the scheduler. Artificial
+ // dependencies may be removed only if they are redundant with another
+ // strong depedence.
+ //
+ // Weak dependencies may be violated by the scheduling strategy, but only if
+ // the strategy can prove it is correct to do so.
+ //
+ // Strong OrderKinds must occur before "Weak".
+ // Weak OrderKinds must occur after "Weak".
+ enum OrderKind {
+ Barrier, ///< An unknown scheduling barrier.
+ MayAliasMem, ///< Nonvolatile load/Store instructions that may alias.
+ MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
+ Artificial, ///< Arbitrary strong DAG edge (no real dependence).
+ Weak, ///< Arbitrary weak DAG edge.
+ Cluster ///< Weak DAG edge linking a chain of clustered instrs.
+ };
+
private:
/// Dep - A pointer to the depending/depended-on SUnit, and an enum
/// indicating the kind of the dependency.
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;
+ unsigned OrdKind; // enum OrderKind
} Contents;
/// Latency - The time associated with this edge. Often this is just
/// 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() : Dep(nullptr, 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) {
+ SDep(SUnit *S, Kind kind, unsigned Reg)
+ : Dep(S, kind), Contents() {
switch (kind) {
+ default:
+ llvm_unreachable("Reg given for non-register dependence!");
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;
+ Latency = 0;
break;
- case Order:
- assert(Reg == 0 && "Reg given for non-register dependence!");
- Contents.Order.isNormalMemory = isNormalMemory;
- Contents.Order.isMustAlias = isMustAlias;
- Contents.Order.isArtificial = isArtificial;
+ case Data:
+ Contents.Reg = Reg;
+ Latency = 1;
break;
}
}
+ SDep(SUnit *S, OrderKind kind)
+ : Dep(S, Order), Contents(), Latency(0) {
+ Contents.OrdKind = kind;
+ }
- bool operator==(const SDep &Other) const {
- if (Dep != Other.Dep || Latency != Other.Latency) return false;
+ /// Return true if the specified SDep is equivalent except for latency.
+ bool overlaps(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;
+ return Contents.OrdKind == Other.Contents.OrdKind;
}
llvm_unreachable("Invalid dependency kind!");
}
+ bool operator==(const SDep &Other) const {
+ return overlaps(Other) && Latency == Other.Latency;
+ }
+
bool operator!=(const SDep &Other) const {
return !operator==(Other);
}
/// 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;
+ return getKind() == Order && (Contents.OrdKind == MayAliasMem
+ || Contents.OrdKind == MustAliasMem);
+ }
+
+ /// isBarrier - Test if this is an Order dependence that is marked
+ /// as a barrier.
+ bool isBarrier() const {
+ return getKind() == Order && Contents.OrdKind == Barrier;
+ }
+
+ /// isNormalMemoryOrBarrier - Test if this is could be any kind of memory
+ /// dependence.
+ bool isNormalMemoryOrBarrier() const {
+ return (isNormalMemory() || isBarrier());
}
/// 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;
+ return getKind() == Order && Contents.OrdKind == MustAliasMem;
+ }
+
+ /// isWeak - Test if this a weak dependence. Weak dependencies are
+ /// considered DAG edges for height computation and other heuristics, but do
+ /// not force ordering. Breaking a weak edge may require the scheduler to
+ /// compensate, for example by inserting a copy.
+ bool isWeak() const {
+ return getKind() == Order && Contents.OrdKind >= Weak;
}
/// 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;
+ return getKind() == Order && Contents.OrdKind == Artificial;
+ }
+
+ /// isCluster - Test if this is an Order dependence that is marked
+ /// as "cluster", meaning it is artificial and wants to be adjacent.
+ bool isCluster() const {
+ return getKind() == Order && Contents.OrdKind == Cluster;
}
/// isAssignedRegDep - Test if this is a Data dependence that is
/// SUnit - Scheduling unit. This is a node in the scheduling DAG.
class SUnit {
private:
+ enum : unsigned { BoundaryID = ~0u };
+
SDNode *Node; // Representative node.
MachineInstr *Instr; // Alternatively, a MachineInstr.
public:
// this node was cloned.
// (SD scheduling only)
+ const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass.
+
// 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 pred_iterator;
- 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;
+ typedef SmallVectorImpl<SDep>::iterator pred_iterator;
+ typedef SmallVectorImpl<SDep>::iterator succ_iterator;
+ typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
+ typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
unsigned NodeNum; // Entry # of node in the node vector.
unsigned NodeQueueId; // Queue id of node.
unsigned NumSuccs; // # of SDep::Data sucss.
unsigned NumPredsLeft; // # of preds not scheduled.
unsigned NumSuccsLeft; // # of succs not scheduled.
+ unsigned WeakPredsLeft; // # of weak preds not scheduled.
+ unsigned WeakSuccsLeft; // # of weak succs not scheduled.
unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use.
unsigned short Latency; // Node latency.
bool isVRegCycle : 1; // May use and def the same vreg.
bool isCallOp : 1; // Is a function call operand.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isCommutable : 1; // Is a commutable instruction.
+ bool hasPhysRegUses : 1; // Has physreg uses.
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 isScheduleHigh : 1; // True if preferable to schedule high.
bool isScheduleLow : 1; // True if preferable to schedule low.
bool isCloned : 1; // True if this node has been cloned.
+ bool isUnbuffered : 1; // Uses an unbuffered resource.
+ bool hasReservedResource : 1; // Uses a reserved resource.
Sched::Preference SchedulingPref; // Scheduling preference.
private:
unsigned Depth; // Node depth.
unsigned Height; // Node height.
public:
+ unsigned TopReadyCycle; // Cycle relative to start when node is ready.
+ unsigned BotReadyCycle; // Cycle relative to end when node is ready.
+
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), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
- NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0),
- isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
- isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
+ : Node(node), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr),
+ NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0),
+ NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0),
+ NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false),
+ isCallOp(false), isTwoAddress(false), isCommutable(false),
+ hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
isScheduleHigh(false), isScheduleLow(false), isCloned(false),
- SchedulingPref(Sched::None),
- isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
- CopyDstRC(NULL), CopySrcRC(NULL) {}
+ isUnbuffered(false), hasReservedResource(false),
+ SchedulingPref(Sched::None), isDepthCurrent(false),
+ isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0),
+ BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {}
/// 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), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
- NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0),
- isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
- isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
+ : Node(nullptr), Instr(instr), OrigNode(nullptr), SchedClass(nullptr),
+ NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0),
+ NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0),
+ NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false),
+ isCallOp(false), isTwoAddress(false), isCommutable(false),
+ hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
isScheduleHigh(false), isScheduleLow(false), isCloned(false),
- SchedulingPref(Sched::None),
- isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
- CopyDstRC(NULL), CopySrcRC(NULL) {}
+ isUnbuffered(false), hasReservedResource(false),
+ SchedulingPref(Sched::None), isDepthCurrent(false),
+ isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0),
+ BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {}
/// SUnit - Construct a placeholder SUnit.
SUnit()
- : Node(0), Instr(0), OrigNode(0), NodeNum(~0u),
- NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
- NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0),
- isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
- isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
+ : Node(nullptr), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr),
+ NodeNum(BoundaryID), NodeQueueId(0), NumPreds(0), NumSuccs(0),
+ NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0),
+ NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false),
+ isCallOp(false), isTwoAddress(false), isCommutable(false),
+ hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
isPending(false), isAvailable(false), isScheduled(false),
isScheduleHigh(false), isScheduleLow(false), isCloned(false),
- SchedulingPref(Sched::None),
- isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
- CopyDstRC(NULL), CopySrcRC(NULL) {}
+ isUnbuffered(false), hasReservedResource(false),
+ SchedulingPref(Sched::None), isDepthCurrent(false),
+ isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0),
+ BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {}
+
+ /// \brief Boundary nodes are placeholders for the boundary of the
+ /// scheduling region.
+ ///
+ /// BoundaryNodes can have DAG edges, including Data edges, but they do not
+ /// correspond to schedulable entities (e.g. instructions) and do not have a
+ /// valid ID. Consequently, always check for boundary nodes before accessing
+ /// an assoicative data structure keyed on node ID.
+ bool isBoundaryNode() const { return NodeNum == BoundaryID; }
/// setNode - Assign the representative SDNode for this SUnit.
/// This may be used during pre-regalloc scheduling.
/// 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.
- bool addPred(const SDep &D);
+ bool addPred(const SDep &D, bool Required = true);
/// 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
return false;
}
+ bool isTopReady() const {
+ return NumPredsLeft == 0;
+ }
+ bool isBottomReady() const {
+ return NumSuccsLeft == 0;
+ }
+
+ /// \brief Order this node's predecessor edges such that the critical path
+ /// edge occurs first.
+ void biasCriticalPath();
+
void dump(const ScheduleDAG *G) const;
void dumpAll(const ScheduleDAG *G) const;
void print(raw_ostream &O, const ScheduleDAG *G) const;
virtual void dump(ScheduleDAG *) const {}
- /// ScheduledNode - As each node is scheduled, this method is invoked. This
+ /// 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 scheduledNode(SUnit *) {}
- virtual void UnscheduledNode(SUnit *) {}
+ virtual void unscheduledNode(SUnit *) {}
void setCurCycle(unsigned Cycle) {
CurCycle = Cycle;
class ScheduleDAG {
public:
- 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
MachineFunction &MF; // Machine function
MachineRegisterInfo &MRI; // Virtual/real register map
- 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.
virtual ~ScheduleDAG();
+ /// clearDAG - clear the DAG state (between regions).
+ void clearDAG();
+
/// getInstrDesc - Return the MCInstrDesc of this SUnit.
/// Return NULL for SDNodes without a machine opcode.
const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
/// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
/// using 'dot'.
///
- void viewGraph(const Twine &Name, const Twine &Title);
- void viewGraph();
-
- /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock
- /// according to the order specified in Sequence.
- ///
- virtual MachineBasicBlock *EmitSchedule() = 0;
+ virtual void viewGraph(const Twine &Name, const Twine &Title);
+ virtual void viewGraph();
virtual void dumpNode(const SUnit *SU) const = 0;
unsigned VerifyScheduledDAG(bool isBottomUp);
#endif
- protected:
- /// Run - perform scheduling.
- ///
- void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos);
-
- /// ComputeLatency - Compute node latency.
- ///
- virtual void ComputeLatency(SUnit *SU) = 0;
-
- /// 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);
-
private:
// Return the MCInstrDesc of this SDNode or NULL.
const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
}
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!");
- Operand = I.Operand;
- return *this;
- }
-
pointer operator*() const {
return Node->Preds[Operand].getSUnit();
}
class ScheduleDAGTopologicalSort {
/// SUnits - A reference to the ScheduleDAG's SUnits.
std::vector<SUnit> &SUnits;
+ SUnit *ExitSU;
/// Index2Node - Maps topological index to the node number.
std::vector<int> Index2Node;
void Allocate(int n, int index);
public:
- explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits);
+ ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
/// InitDAGTopologicalSorting - create the initial topological
/// ordering from the DAG to be scheduled.
/// IsReachable - Checks if SU is reachable from TargetSU.
bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
- /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU
- /// will create a cycle.
- bool WillCreateCycle(SUnit *SU, SUnit *TargetSU);
+ /// WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle.
+ bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
/// AddPred - Updates the topological ordering to accommodate an edge
/// to be added from SUnit X to SUnit Y.