#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
#define LLVM_CODEGEN_SCHEDULEDAG_H
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/GraphTraits.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;
class SUnit;
class MachineConstantPool;
class MachineFunction;
class MachineRegisterInfo;
class MachineInstr;
struct MCSchedClassDesc;
class TargetRegisterInfo;
class ScheduleDAG;
class SDNode;
class TargetInstrInfo;
class MCInstrDesc;
class TargetMachine;
class TargetRegisterClass;
template<class Graph> class GraphWriter;
class SDep {
public:
enum Kind {
Data, Anti, Output, Order };
enum OrderKind {
Barrier, MayAliasMem, MustAliasMem, Artificial, Weak, Cluster };
private:
PointerIntPair<SUnit *, 2, Kind> Dep;
union {
unsigned Reg;
unsigned OrdKind; } Contents;
unsigned Latency;
public:
SDep() : Dep(nullptr, Data) {}
SDep(SUnit *S, Kind kind, unsigned Reg)
: Dep(S, kind), Contents() {
switch (kind) {
default:
llvm_unreachable("Reg given for non-register dependence!");
case Anti:
case Output:
assert(Reg != 0 &&
"SDep::Anti and SDep::Output must use a non-zero Reg!");
Contents.Reg = Reg;
Latency = 0;
break;
case Data:
Contents.Reg = Reg;
Latency = 1;
break;
}
}
SDep(SUnit *S, OrderKind kind)
: Dep(S, Order), Contents(), Latency(0) {
Contents.OrdKind = kind;
}
bool overlaps(const SDep &Other) const {
if (Dep != Other.Dep) return false;
switch (Dep.getInt()) {
case Data:
case Anti:
case Output:
return Contents.Reg == Other.Contents.Reg;
case Order:
return Contents.OrdKind == Other.Contents.OrdKind;
}
llvm_unreachable("Invalid dependency kind!");
}
bool operator==(const SDep &Other) const {
return overlaps(Other) && Latency == Other.Latency;
}
bool operator!=(const SDep &Other) const {
return !operator==(Other);
}
unsigned getLatency() const {
return Latency;
}
void setLatency(unsigned Lat) {
Latency = Lat;
}
SUnit *getSUnit() const {
return Dep.getPointer();
}
void setSUnit(SUnit *SU) {
Dep.setPointer(SU);
}
Kind getKind() const {
return Dep.getInt();
}
bool isCtrl() const {
return getKind() != Data;
}
bool isNormalMemory() const {
return getKind() == Order && (Contents.OrdKind == MayAliasMem
|| Contents.OrdKind == MustAliasMem);
}
bool isBarrier() const {
return getKind() == Order && Contents.OrdKind == Barrier;
}
bool isNormalMemoryOrBarrier() const {
return (isNormalMemory() || isBarrier());
}
bool isMustAlias() const {
return getKind() == Order && Contents.OrdKind == MustAliasMem;
}
bool isWeak() const {
return getKind() == Order && Contents.OrdKind >= Weak;
}
bool isArtificial() const {
return getKind() == Order && Contents.OrdKind == Artificial;
}
bool isCluster() const {
return getKind() == Order && Contents.OrdKind == Cluster;
}
bool isAssignedRegDep() const {
return getKind() == Data && Contents.Reg != 0;
}
unsigned getReg() const {
assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
"getReg called on non-register dependence edge!");
return Contents.Reg;
}
void setReg(unsigned Reg) {
assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
"setReg called on non-register dependence edge!");
assert((getKind() != Anti || Reg != 0) &&
"SDep::Anti edge cannot use the zero register!");
assert((getKind() != Output || Reg != 0) &&
"SDep::Output edge cannot use the zero register!");
Contents.Reg = Reg;
}
};
template <>
struct isPodLike<SDep> { static const bool value = true; };
class SUnit {
private:
enum : unsigned { BoundaryID = ~0u };
SDNode *Node; MachineInstr *Instr; public:
SUnit *OrigNode;
const MCSchedClassDesc *SchedClass;
SmallVector<SDep, 4> Preds; SmallVector<SDep, 4> Succs;
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; unsigned NodeQueueId; unsigned NumPreds; unsigned NumSuccs; unsigned NumPredsLeft; unsigned NumSuccsLeft; unsigned WeakPredsLeft; unsigned WeakSuccsLeft; unsigned short NumRegDefsLeft; unsigned short Latency; bool isVRegCycle : 1; bool isCall : 1; bool isCallOp : 1; bool isTwoAddress : 1; bool isCommutable : 1; bool hasPhysRegUses : 1; bool hasPhysRegDefs : 1; bool hasPhysRegClobbers : 1; bool isPending : 1; bool isAvailable : 1; bool isScheduled : 1; bool isScheduleHigh : 1; bool isScheduleLow : 1; bool isCloned : 1; bool isUnbuffered : 1; bool hasReservedResource : 1; Sched::Preference SchedulingPref;
private:
bool isDepthCurrent : 1; bool isHeightCurrent : 1; unsigned Depth; unsigned Height; public:
unsigned TopReadyCycle; unsigned BotReadyCycle;
const TargetRegisterClass *CopyDstRC; const TargetRegisterClass *CopySrcRC;
SUnit(SDNode *node, unsigned nodenum)
: Node(node), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr),
NodeNum(nodenum), 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),
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(nullptr), CopySrcRC(nullptr) {}
SUnit(MachineInstr *instr, unsigned nodenum)
: Node(nullptr), Instr(instr), OrigNode(nullptr), SchedClass(nullptr),
NodeNum(nodenum), 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),
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(nullptr), CopySrcRC(nullptr) {}
SUnit()
: Node(nullptr), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr),
NodeNum(BoundaryID), 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),
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(nullptr), CopySrcRC(nullptr) {}
bool isBoundaryNode() const { return NodeNum == BoundaryID; };
void setNode(SDNode *N) {
assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
Node = N;
}
SDNode *getNode() const {
assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
return Node;
}
bool isInstr() const { return Instr; }
void setInstr(MachineInstr *MI) {
assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
Instr = MI;
}
MachineInstr *getInstr() const {
assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
return Instr;
}
bool addPred(const SDep &D, bool Required = true);
void removePred(const SDep &D);
unsigned getDepth() const {
if (!isDepthCurrent)
const_cast<SUnit *>(this)->ComputeDepth();
return Depth;
}
unsigned getHeight() const {
if (!isHeightCurrent)
const_cast<SUnit *>(this)->ComputeHeight();
return Height;
}
void setDepthToAtLeast(unsigned NewDepth);
void setHeightToAtLeast(unsigned NewHeight);
void setDepthDirty();
void setHeightDirty();
bool isPred(SUnit *N) {
for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
if (Preds[i].getSUnit() == N)
return true;
return false;
}
bool isSucc(SUnit *N) {
for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
if (Succs[i].getSUnit() == N)
return true;
return false;
}
bool isTopReady() const {
return NumPredsLeft == 0;
}
bool isBottomReady() const {
return NumSuccsLeft == 0;
}
void biasCriticalPath();
void dump(const ScheduleDAG *G) const;
void dumpAll(const ScheduleDAG *G) const;
void print(raw_ostream &O, const ScheduleDAG *G) const;
private:
void ComputeDepth();
void ComputeHeight();
};
class SchedulingPriorityQueue {
virtual void anchor();
unsigned CurCycle;
bool HasReadyFilter;
public:
SchedulingPriorityQueue(bool rf = false):
CurCycle(0), HasReadyFilter(rf) {}
virtual ~SchedulingPriorityQueue() {}
virtual bool isBottomUp() const = 0;
virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
virtual void addNode(const SUnit *SU) = 0;
virtual void updateNode(const SUnit *SU) = 0;
virtual void releaseState() = 0;
virtual bool empty() const = 0;
bool hasReadyFilter() const { return HasReadyFilter; }
virtual bool tracksRegPressure() const { return false; }
virtual bool isReady(SUnit *) const {
assert(!HasReadyFilter && "The ready filter must override isReady()");
return true;
}
virtual void push(SUnit *U) = 0;
void push_all(const std::vector<SUnit *> &Nodes) {
for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
E = Nodes.end(); I != E; ++I)
push(*I);
}
virtual SUnit *pop() = 0;
virtual void remove(SUnit *SU) = 0;
virtual void dump(ScheduleDAG *) const {}
virtual void scheduledNode(SUnit *) {}
virtual void unscheduledNode(SUnit *) {}
void setCurCycle(unsigned Cycle) {
CurCycle = Cycle;
}
unsigned getCurCycle() const {
return CurCycle;
}
};
class ScheduleDAG {
public:
const TargetMachine &TM; const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; MachineFunction &MF; MachineRegisterInfo &MRI; std::vector<SUnit> SUnits; SUnit EntrySU; SUnit ExitSU;
#ifdef NDEBUG
static const bool StressSched = false;
#else
bool StressSched;
#endif
explicit ScheduleDAG(MachineFunction &mf);
virtual ~ScheduleDAG();
void clearDAG();
const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
if (SU->isInstr()) return &SU->getInstr()->getDesc();
return getNodeDesc(SU->getNode());
}
virtual void viewGraph(const Twine &Name, const Twine &Title);
virtual void viewGraph();
virtual void dumpNode(const SUnit *SU) const = 0;
virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
virtual std::string getDAGName() const = 0;
virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
#ifndef NDEBUG
unsigned VerifyScheduledDAG(bool isBottomUp);
#endif
private:
const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
};
class SUnitIterator : public std::iterator<std::forward_iterator_tag,
SUnit, ptrdiff_t> {
SUnit *Node;
unsigned Operand;
SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
public:
bool operator==(const SUnitIterator& x) const {
return Operand == x.Operand;
}
bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
const SUnitIterator &operator=(const SUnitIterator &I) {
assert(I.Node==Node && "Cannot assign iterators to two different nodes!");
Operand = I.Operand;
return *this;
}
pointer operator*() const {
return Node->Preds[Operand].getSUnit();
}
pointer operator->() const { return operator*(); }
SUnitIterator& operator++() { ++Operand;
return *this;
}
SUnitIterator operator++(int) { SUnitIterator tmp = *this; ++*this; return tmp;
}
static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
static SUnitIterator end (SUnit *N) {
return SUnitIterator(N, (unsigned)N->Preds.size());
}
unsigned getOperand() const { return Operand; }
const SUnit *getNode() const { return Node; }
bool isCtrlDep() const {
return getSDep().isCtrl();
}
bool isArtificialDep() const {
return getSDep().isArtificial();
}
const SDep &getSDep() const {
return Node->Preds[Operand];
}
};
template <> struct GraphTraits<SUnit*> {
typedef SUnit NodeType;
typedef SUnitIterator ChildIteratorType;
static inline NodeType *getEntryNode(SUnit *N) { return N; }
static inline ChildIteratorType child_begin(NodeType *N) {
return SUnitIterator::begin(N);
}
static inline ChildIteratorType child_end(NodeType *N) {
return SUnitIterator::end(N);
}
};
template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
typedef std::vector<SUnit>::iterator nodes_iterator;
static nodes_iterator nodes_begin(ScheduleDAG *G) {
return G->SUnits.begin();
}
static nodes_iterator nodes_end(ScheduleDAG *G) {
return G->SUnits.end();
}
};
class ScheduleDAGTopologicalSort {
std::vector<SUnit> &SUnits;
SUnit *ExitSU;
std::vector<int> Index2Node;
std::vector<int> Node2Index;
BitVector Visited;
void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
void Shift(BitVector& Visited, int LowerBound, int UpperBound);
void Allocate(int n, int index);
public:
ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
void InitDAGTopologicalSorting();
bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
void AddPred(SUnit *Y, SUnit *X);
void RemovePred(SUnit *M, SUnit *N);
typedef std::vector<int>::iterator iterator;
typedef std::vector<int>::const_iterator const_iterator;
iterator begin() { return Index2Node.begin(); }
const_iterator begin() const { return Index2Node.begin(); }
iterator end() { return Index2Node.end(); }
const_iterator end() const { return Index2Node.end(); }
typedef std::vector<int>::reverse_iterator reverse_iterator;
typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
reverse_iterator rbegin() { return Index2Node.rbegin(); }
const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
reverse_iterator rend() { return Index2Node.rend(); }
const_reverse_iterator rend() const { return Index2Node.rend(); }
};
}
#endif