#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/CodeGen/MachineInstr.h"
+#include "llvm/Target/TargetLowering.h"
namespace llvm {
class AliasAnalysis;
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
/// 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.
- 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 latency = 1, unsigned Reg = 0,
- bool isNormalMemory = false, bool isMustAlias = false,
- bool isArtificial = false)
- : Dep(S, kind), Contents(), Latency(latency), MinLatency(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;
+ }
/// Return true if the specified SDep is equivalent except for latency.
bool overlaps(const SDep &Other) const {
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 && 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();
/// 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;
}
/// 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:
/// 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),
- TopReadyCycle(0), BotReadyCycle(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),
- TopReadyCycle(0), BotReadyCycle(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),
- TopReadyCycle(0), BotReadyCycle(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 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;
/// 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;
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.
projects / oota-llvm.git / blobdiff