From ae692f2baedf53504af2715993b166950e185a55 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Mon, 12 Nov 2012 19:28:57 +0000 Subject: misched: Infrastructure for weak DAG edges. This adds support for weak DAG edges to the general scheduling infrastructure in preparation for MachineScheduler support for heuristics based on weak edges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167738 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/ScheduleDAG.h | 61 +++++++++++++++++++++++++------------- 1 file changed, 40 insertions(+), 21 deletions(-) (limited to 'include') diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 7e0ca1478e..2b6429fbeb 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -57,7 +57,8 @@ namespace llvm { 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 weak DAG edge (no actual dependence). + Cluster ///< Weak DAG edge linking a chain of clustered instrs. }; private: @@ -200,12 +201,27 @@ 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 == Artificial || Contents.OrdKind == Cluster); + } + /// 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 { @@ -267,6 +283,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. @@ -301,12 +319,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), 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,12 +333,12 @@ 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), 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) {} @@ -328,12 +346,12 @@ namespace llvm { SUnit() : Node(0), Instr(0), OrigNode(0), SchedClass(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), - 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), 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) {} @@ -372,7 +390,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 @@ -654,6 +672,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 +694,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. -- cgit v1.2.3