#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;
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.
};
private:
/// 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
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();
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.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
/// associated with a register.
bool isAssignedRegDep() const {
/// SUnit - Scheduling unit. This is a node in the scheduling DAG.
class SUnit {
private:
+ enum { 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.
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.
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), 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),
+ 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) {}
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), 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),
+ 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) {}
/// SUnit - Construct a placeholder SUnit.
SUnit()
- : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(~0u),
+ : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(BoundaryID),
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),
- isPending(false), isAvailable(false), isScheduled(false),
- isScheduleHigh(false), isScheduleLow(false), isCloned(false),
- SchedulingPref(Sched::None),
+ 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) {}
+ /// \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.
void setNode(SDNode *N) {
/// 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