#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 {
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.
};
/// 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();
|| 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.
/// 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
/// SUnit - Scheduling unit. This is a node in the scheduling DAG.
class SUnit {
private:
- enum { BoundaryID = ~0u };
+ enum LLVM_ENUM_INT_TYPE(unsigned) { BoundaryID = ~0u };
SDNode *Node; // Representative node.
MachineInstr *Instr; // Alternatively, a MachineInstr.
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.
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:
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), isUnbuffered(false),
+ hasReservedResource(false), SchedulingPref(Sched::None),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
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), isUnbuffered(false),
+ hasReservedResource(false), SchedulingPref(Sched::None),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
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), isUnbuffered(false),
+ hasReservedResource(false), SchedulingPref(Sched::None),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
/// 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;
/// 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