So far, we have had SelectionDAG nodes consisting of target-supported instructions and operands. However, the code is still in DAG representation. The target architecture executes instructions in sequential form. So, the next logical step is to schedule the SelectionDAG nodes.
A scheduler assigns the order of execution of instructions from the DAG. In this process, it takes into account various heuristics, such as register pressure, to optimize the execution order of instructions and to minimize latencies in instruction execution. After assigning the order of execution to the DAG nodes, the nodes are converted into a list of MachineInstrs and the SelectionDAG nodes are destroyed.
There are several basic structures that are defined in the ScheduleDAG.h file and implemented in the ScheduleDAG.cpp file. The ScheduleDAG class is a base class for other schedulers to inherit, and it provides only graph-related manipulation operations such as an iterator, DFS, topological sorting, functions for moving nodes around, and so on:
class ScheduleDAG {
public:
const TargetMachine &TM; // Target processor
const TargetInstrInfo *TII; // Target instruction
const TargetRegisterInfo *TRI; // Target processor register info
MachineFunction &MF; // Machine function
MachineRegisterInfo &MRI; // Virtual/real register map
std::vector<SUnit> SUnits; // The scheduling units.
SUnit EntrySU; // Special node for the region entry.
SUnit ExitSU; // Special node for the region exit.
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 dumpNode(const SUnit *SU) const = 0;
private:
const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
};
class SUnitIterator : public std::iterator<std::forward_iterator_tag,
SUnit, ptrdiff_t> {
};
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*> {
…};
// Topological sorting of DAG to linear set of instructions
class ScheduleDAGTopologicalSort {
std::vector<SUnit> &SUnits;
SUnit *ExitSU;
std::vector<int> Index2Node;
std::vector<int> Node2Index;
BitVector Visited;
// DFS to be run on DAG to sort topologically
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 *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();}}The scheduling algorithm implements the scheduling of instructions in the SelectionDAG class, which involves a variety of algorithms such as topological sorting, depth-first searching, manipulating functions, moving nodes, and iterating over a list of instructions. It takes into account various heuristics, such as register pressure, spilling cost, live interval analysis, and so on to determine the best possible scheduling of instructions.