X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=371ac6c34d08999f205ea9d5fde2bd43fadff75e;hb=2c46deb1d07f4588ee70059cdd4c7145f81bc8e8;hp=7e0ca1478e5fbdc9e7d22ad1d6362215c37817bb;hpb=8d4abb2446f80986ad5136bbec30c5da18cd6f4b;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 7e0ca1478e5..371ac6c34d0 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -16,13 +16,12 @@ #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; @@ -53,11 +52,22 @@ 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. }; private: @@ -80,11 +90,6 @@ namespace llvm { /// 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 @@ -110,10 +115,9 @@ namespace llvm { 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; } @@ -132,8 +136,7 @@ namespace llvm { } 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 { @@ -153,18 +156,6 @@ namespace llvm { 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(); @@ -200,12 +191,26 @@ namespace llvm { 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 { @@ -243,6 +248,8 @@ namespace llvm { /// 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: @@ -256,10 +263,10 @@ namespace llvm { SmallVector Preds; // All sunit predecessors. SmallVector Succs; // All sunit successors. - typedef SmallVector::iterator pred_iterator; - typedef SmallVector::iterator succ_iterator; - typedef SmallVector::const_iterator const_pred_iterator; - typedef SmallVector::const_iterator const_succ_iterator; + typedef SmallVectorImpl::iterator pred_iterator; + typedef SmallVectorImpl::iterator succ_iterator; + typedef SmallVectorImpl::const_iterator const_pred_iterator; + typedef SmallVectorImpl::const_iterator const_succ_iterator; unsigned NodeNum; // Entry # of node in the node vector. unsigned NodeQueueId; // Queue id of node. @@ -267,6 +274,8 @@ namespace llvm { 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. @@ -274,6 +283,7 @@ namespace llvm { 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. @@ -301,12 +311,12 @@ namespace llvm { 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) {} @@ -315,28 +325,37 @@ namespace llvm { 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) { @@ -372,7 +391,7 @@ namespace llvm { /// 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 @@ -438,6 +457,10 @@ namespace llvm { 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; @@ -546,8 +569,8 @@ namespace llvm { /// 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; @@ -654,6 +677,7 @@ namespace llvm { class ScheduleDAGTopologicalSort { /// SUnits - A reference to the ScheduleDAG's SUnits. std::vector &SUnits; + SUnit *ExitSU; /// Index2Node - Maps topological index to the node number. std::vector Index2Node; @@ -675,7 +699,7 @@ namespace llvm { void Allocate(int n, int index); public: - explicit ScheduleDAGTopologicalSort(std::vector &SUnits); + ScheduleDAGTopologicalSort(std::vector &SUnits, SUnit *ExitSU); /// InitDAGTopologicalSorting - create the initial topological /// ordering from the DAG to be scheduled. @@ -684,9 +708,8 @@ namespace llvm { /// 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.