X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=371ac6c34d08999f205ea9d5fde2bd43fadff75e;hb=2c46deb1d07f4588ee70059cdd4c7145f81bc8e8;hp=18bef1c4028666545e7eaad73c07dc0cf34aa7e1;hpb=a5a73ad15905c18843a8312bb3f20f5c501744de;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 18bef1c4028..371ac6c34d0 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -17,11 +17,10 @@ #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 { @@ -53,11 +52,21 @@ 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. }; @@ -81,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 @@ -111,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; } @@ -133,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 { @@ -154,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(); @@ -206,7 +196,7 @@ namespace llvm { /// 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 @@ -273,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. @@ -293,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. @@ -322,10 +313,10 @@ namespace llvm { 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), + 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) {} @@ -336,10 +327,10 @@ namespace llvm { 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), + 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) {} @@ -349,10 +340,10 @@ namespace llvm { 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), + 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) {} @@ -578,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; @@ -717,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.