#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
#define LLVM_CODEGEN_SCHEDULEDAG_H
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/Target/TargetMachine.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"
namespace llvm {
class AliasAnalysis;
class SUnit;
class MachineConstantPool;
class MachineFunction;
class MachineRegisterInfo;
class MachineInstr;
class TargetRegisterInfo;
class ScheduleDAG;
class SDNode;
class TargetInstrInfo;
class TargetInstrDesc;
class TargetMachine;
class TargetRegisterClass;
template<class Graph> class GraphWriter;
class SDep {
public:
enum Kind {
Data, Anti, Output, Order };
private:
PointerIntPair<SUnit *, 2, Kind> Dep;
union {
unsigned Reg;
struct {
bool isNormalMemory : 1;
bool isMustAlias : 1;
bool isArtificial : 1;
} Order;
} Contents;
unsigned Latency;
public:
SDep() : Dep(0, Data) {}
SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0,
bool isNormalMemory = false, bool isMustAlias = false,
bool isArtificial = false)
: Dep(S, kind), Contents(), Latency(latency) {
switch (kind) {
case Anti:
case Output:
assert(Reg != 0 &&
"SDep::Anti and SDep::Output must use a non-zero Reg!");
case Data:
assert(!isMustAlias && "isMustAlias only applies with SDep::Order!");
assert(!isArtificial && "isArtificial only applies with SDep::Order!");
Contents.Reg = Reg;
break;
case Order:
assert(Reg == 0 && "Reg given for non-register dependence!");
Contents.Order.isNormalMemory = isNormalMemory;
Contents.Order.isMustAlias = isMustAlias;
Contents.Order.isArtificial = isArtificial;
break;
}
}
bool operator==(const SDep &Other) const {
if (Dep != Other.Dep || Latency != Other.Latency) return false;
switch (Dep.getInt()) {
case Data:
case Anti:
case Output:
return Contents.Reg == Other.Contents.Reg;
case Order:
return Contents.Order.isNormalMemory ==
Other.Contents.Order.isNormalMemory &&
Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias &&
Contents.Order.isArtificial == Other.Contents.Order.isArtificial;
}
assert(0 && "Invalid dependency kind!");
return false;
}
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.Order.isNormalMemory;
}
bool isMustAlias() const {
return getKind() == Order && Contents.Order.isMustAlias;
}
bool isArtificial() const {
return getKind() == Order && Contents.Order.isArtificial;
}
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:
SDNode *Node; MachineInstr *Instr; public:
SUnit *OrigNode;
SmallVector<SDep, 4> Preds; SmallVector<SDep, 4> Succs;
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;
unsigned NodeNum; unsigned NodeQueueId; unsigned NumPreds; unsigned NumSuccs; unsigned NumPredsLeft; unsigned NumSuccsLeft; unsigned short NumRegDefsLeft; unsigned short Latency; bool isVRegCycle : 1; bool isCall : 1; bool isCallOp : 1; bool isTwoAddress : 1; bool isCommutable : 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; Sched::Preference SchedulingPref;
SmallVector<MachineInstr*, 4> DbgInstrList; private:
bool isDepthCurrent : 1; bool isHeightCurrent : 1; unsigned Depth; unsigned Height; public:
const TargetRegisterClass *CopyDstRC; const TargetRegisterClass *CopySrcRC;
SUnit(SDNode *node, unsigned nodenum)
: Node(node), Instr(0), OrigNode(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),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
CopyDstRC(NULL), CopySrcRC(NULL) {}
SUnit(MachineInstr *instr, unsigned nodenum)
: Node(0), Instr(instr), OrigNode(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),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
CopyDstRC(NULL), CopySrcRC(NULL) {}
SUnit()
: Node(0), Instr(0), OrigNode(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),
isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
CopyDstRC(NULL), CopySrcRC(NULL) {}
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);
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;
}
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 {
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:
MachineBasicBlock *BB; MachineBasicBlock::iterator InsertPos; const TargetMachine &TM; const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; MachineFunction &MF; MachineRegisterInfo &MRI; std::vector<SUnit*> Sequence; std::vector<SUnit> SUnits; SUnit EntrySU; SUnit ExitSU;
explicit ScheduleDAG(MachineFunction &mf);
virtual ~ScheduleDAG();
const TargetInstrDesc *getInstrDesc(const SUnit *SU) const {
if (SU->isInstr()) return &SU->getInstr()->getDesc();
return getNodeDesc(SU->getNode());
}
void viewGraph();
virtual MachineBasicBlock *EmitSchedule() = 0;
void dumpSchedule() const;
virtual void dumpNode(const SUnit *SU) const = 0;
virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
#ifndef NDEBUG
void VerifySchedule(bool isBottomUp);
#endif
protected:
void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos);
virtual void BuildSchedGraph(AliasAnalysis *AA) = 0;
virtual void ComputeLatency(SUnit *SU) = 0;
virtual void ComputeOperandLatency(SUnit *, SUnit *,
SDep&) const { }
virtual void Schedule() = 0;
virtual bool ForceUnitLatencies() const { return false; }
void EmitNoop();
void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
private:
const TargetInstrDesc *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;
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:
explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits);
void InitDAGTopologicalSorting();
bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
bool WillCreateCycle(SUnit *SU, SUnit *TargetSU);
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