-namespace {
-
-/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or a
-/// group of nodes flagged together.
-struct SUnit {
- SDNode *Node; // Representative node.
- std::vector<SDNode*> FlaggedNodes; // All nodes flagged to Node.
- std::set<SUnit*> Preds; // All real predecessors.
- std::set<SUnit*> ChainPreds; // All chain predecessors.
- std::set<SUnit*> Succs; // All real successors.
- std::set<SUnit*> ChainSuccs; // All chain successors.
- int NumPredsLeft; // # of preds not scheduled.
- int NumSuccsLeft; // # of succs not scheduled.
- int NumChainPredsLeft; // # of chain preds not scheduled.
- int NumChainSuccsLeft; // # of chain succs not scheduled.
- int Priority1; // Scheduling priority 1.
- int Priority2; // Scheduling priority 2.
- bool isTwoAddress; // Is a two-address instruction.
- bool isDefNUseOperand; // Is a def&use operand.
- unsigned Latency; // Node latency.
- unsigned CycleBound; // Upper/lower cycle to be scheduled at.
- unsigned Slot; // Cycle node is scheduled at.
- SUnit *Next;
-
- SUnit(SDNode *node)
- : Node(node), NumPredsLeft(0), NumSuccsLeft(0),
- NumChainPredsLeft(0), NumChainSuccsLeft(0),
- Priority1(INT_MIN), Priority2(INT_MIN),
- isTwoAddress(false), isDefNUseOperand(false),
- Latency(0), CycleBound(0), Slot(0), Next(NULL) {}
-
- void dump(const SelectionDAG *G, bool All=true) const;
-};
-
-void SUnit::dump(const SelectionDAG *G, bool All) const {
- std::cerr << "SU: ";
- Node->dump(G);
- std::cerr << "\n";
- if (FlaggedNodes.size() != 0) {
- for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
- std::cerr << " ";
- FlaggedNodes[i]->dump(G);
- std::cerr << "\n";
- }
- }
-
- if (All) {
- std::cerr << " # preds left : " << NumPredsLeft << "\n";
- std::cerr << " # succs left : " << NumSuccsLeft << "\n";
- std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n";
- std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n";
- std::cerr << " Latency : " << Latency << "\n";
- std::cerr << " Priority : " << Priority1 << " , "
- << Priority2 << "\n";
-
- if (Preds.size() != 0) {
- std::cerr << " Predecessors:\n";
- for (std::set<SUnit*>::const_iterator I = Preds.begin(),
- E = Preds.end(); I != E; ++I) {
- std::cerr << " ";
- (*I)->dump(G, false);
- }
- }
- if (ChainPreds.size() != 0) {
- std::cerr << " Chained Preds:\n";
- for (std::set<SUnit*>::const_iterator I = ChainPreds.begin(),
- E = ChainPreds.end(); I != E; ++I) {
- std::cerr << " ";
- (*I)->dump(G, false);
- }
- }
- if (Succs.size() != 0) {
- std::cerr << " Successors:\n";
- for (std::set<SUnit*>::const_iterator I = Succs.begin(),
- E = Succs.end(); I != E; ++I) {
- std::cerr << " ";
- (*I)->dump(G, false);
- }
- }
- if (ChainSuccs.size() != 0) {
- std::cerr << " Chained succs:\n";
- for (std::set<SUnit*>::const_iterator I = ChainSuccs.begin(),
- E = ChainSuccs.end(); I != E; ++I) {
- std::cerr << " ";
- (*I)->dump(G, false);
- }
- }
- }
-}
-
-/// Sorting functions for the Available queue.
-struct ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
- bool operator()(const SUnit* left, const SUnit* right) const {
- bool LFloater = (left ->Preds.size() == 0);
- bool RFloater = (right->Preds.size() == 0);
- int LBonus = (int)left ->isDefNUseOperand;
- int RBonus = (int)right->isDefNUseOperand;
-
- // Special tie breaker: if two nodes share a operand, the one that
- // use it as a def&use operand is preferred.
- if (left->isTwoAddress && !right->isTwoAddress) {
- SDNode *DUNode = left->Node->getOperand(0).Val;
- if (DUNode->isOperand(right->Node))
- LBonus++;
- }
- if (!left->isTwoAddress && right->isTwoAddress) {
- SDNode *DUNode = right->Node->getOperand(0).Val;
- if (DUNode->isOperand(left->Node))
- RBonus++;
- }
-
- int LPriority1 = left ->Priority1 - LBonus;
- int RPriority1 = right->Priority1 - RBonus;
- int LPriority2 = left ->Priority2 + LBonus;
- int RPriority2 = right->Priority2 + RBonus;
-
- // Favor floaters (i.e. node with no non-passive predecessors):
- // e.g. MOV32ri.
- if (!LFloater && RFloater)
- return true;
- else if (LFloater == RFloater)
- if (LPriority1 > RPriority1)
- return true;
- else if (LPriority1 == RPriority1)
- if (LPriority2 < RPriority2)
- return true;
- else if (LPriority1 == RPriority1)
- if (left->CycleBound > right->CycleBound)
- return true;
-
- return false;
- }
-};