#define LLVM_CODEGEN_SCHEDULEDAG_H
#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/Target/TargetLowering.h"
namespace llvm {
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 weak DAG edge (no actual dependence).
+ Artificial, ///< Arbitrary strong DAG edge (no real dependence).
+ Weak, ///< Arbitrary weak DAG edge.
Cluster ///< Weak DAG edge linking a chain of clustered instrs.
};
/// the value of the Latency field of the predecessor, however advanced
/// models may provide additional information about specific edges.
unsigned Latency;
- /// Record MinLatency seperately from "expected" Latency.
- ///
- /// FIXME: this field is not packed on LP64. Convert to 16-bit DAG edge
- /// latency after introducing saturating truncation.
- unsigned MinLatency;
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() : Dep(nullptr, Data) {}
/// SDep - Construct an SDep with the specified values.
SDep(SUnit *S, Kind kind, unsigned Reg)
Latency = 1;
break;
}
- MinLatency = Latency;
}
SDep(SUnit *S, OrderKind kind)
- : Dep(S, Order), Contents(), Latency(0), MinLatency(0) {
+ : Dep(S, Order), Contents(), Latency(0) {
Contents.OrdKind = kind;
}
}
bool operator==(const SDep &Other) const {
- return overlaps(Other)
- && Latency == Other.Latency && MinLatency == Other.MinLatency;
+ return overlaps(Other) && Latency == Other.Latency;
}
bool operator!=(const SDep &Other) const {
Latency = Lat;
}
- /// getMinLatency - Return the minimum latency for this edge. Minimum
- /// latency is used for scheduling groups, while normal (expected) latency
- /// is for instruction cost and critical path.
- unsigned getMinLatency() const {
- return MinLatency;
- }
-
- /// setMinLatency - Set the minimum latency for this edge.
- void setMinLatency(unsigned Lat) {
- MinLatency = Lat;
- }
-
//// getSUnit - Return the SUnit to which this edge points.
SUnit *getSUnit() const {
return Dep.getPointer();
|| 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;
+ }
+
/// 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.
/// 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 == Cluster;
+ return getKind() == Order && Contents.OrdKind >= Weak;
}
/// isArtificial - Test if this is an Order dependence that is marked
/// 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:
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.
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:
/// 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), SchedClass(0), 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), 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),
- TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
+ : 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),
+ 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), SchedClass(0), 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), 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),
- TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
+ : 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),
+ 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), SchedClass(0), NodeNum(~0u),
- 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), 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),
- TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
+ : 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),
+ 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.
/// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
/// using 'dot'.
///
- void viewGraph(const Twine &Name, const Twine &Title);
- void viewGraph();
+ virtual void viewGraph(const Twine &Name, const Twine &Title);
+ virtual void viewGraph();
virtual void dumpNode(const SUnit *SU) const = 0;
/// 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.