#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <climits>
-#include <queue>
#include "llvm/Support/CommandLine.h"
using namespace llvm;
CalculateHeights();
InitDAGTopologicalSorting();
- AvailableQueue->initNodes(SUnitMap, SUnits);
+ AvailableQueue->initNodes(SUnits);
// Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
if (isBottomUp)
continue;
SDNode *OpN = SU->Node->getOperand(j).Val;
- SUnit *OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo];
+ SUnit *OpSU = isPassiveNode(OpN) ? NULL : &SUnits[OpN->getNodeId()];
if (OpSU && OperandSeen.count(OpSU) == 1) {
// Ok, so SU is not the last use of OpSU, but SU is two-address so
// it will clobber OpSU. Try to commute SU if no other source operands
for (unsigned k = 0; k < NumOps; ++k) {
if (k != j) {
OpN = SU->Node->getOperand(k).Val;
- OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo];
+ OpSU = isPassiveNode(OpN) ? NULL : &SUnits[OpN->getNodeId()];
if (OpSU && OperandSeen.count(OpSU) == 1) {
DoCommute = false;
break;
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
if (!I->isCtrl)
- OperandSeen.insert(I->Dep);
+ OperandSeen.insert(I->Dep->OrigNode);
}
}
}
SUnit *NewSU;
bool TryUnfold = false;
for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
- MVT::ValueType VT = N->getValueType(i);
+ MVT VT = N->getValueType(i);
if (VT == MVT::Flag)
return NULL;
else if (VT == MVT::Other)
}
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
const SDOperand &Op = N->getOperand(i);
- MVT::ValueType VT = Op.Val->getValueType(Op.ResNo);
+ MVT VT = Op.Val->getValueType(Op.ResNo);
if (VT == MVT::Flag)
return NULL;
}
if (TryUnfold) {
- SmallVector<SDNode*, 4> NewNodes;
+ SmallVector<SDNode*, 2> NewNodes;
if (!TII->unfoldMemoryOperand(DAG, N, NewNodes))
return NULL;
SDOperand(LoadNode, 1));
SUnit *NewSU = CreateNewSUnit(N);
- SUnitMap[N].push_back(NewSU);
+ assert(N->getNodeId() == -1 && "Node already inserted!");
+ N->setNodeId(NewSU->NodeNum);
+
const TargetInstrDesc &TID = TII->get(N->getTargetOpcode());
for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
// but it has different alignment or volatileness.
bool isNewLoad = true;
SUnit *LoadSU;
- DenseMap<SDNode*, std::vector<SUnit*> >::iterator SMI =
- SUnitMap.find(LoadNode);
- if (SMI != SUnitMap.end()) {
- LoadSU = SMI->second.front();
+ if (LoadNode->getNodeId() != -1) {
+ LoadSU = &SUnits[LoadNode->getNodeId()];
isNewLoad = false;
} else {
LoadSU = CreateNewSUnit(LoadNode);
- SUnitMap[LoadNode].push_back(LoadSU);
+ LoadNode->setNodeId(LoadSU->NodeNum);
LoadSU->Depth = SU->Depth;
LoadSU->Height = SU->Height;
/// getPhysicalRegisterVT - Returns the ValueType of the physical register
/// definition of the specified node.
/// FIXME: Move to SelectionDAG?
-static MVT::ValueType getPhysicalRegisterVT(SDNode *N, unsigned Reg,
- const TargetInstrInfo *TII) {
+static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
+ const TargetInstrInfo *TII) {
const TargetInstrDesc &TID = TII->get(N->getTargetOpcode());
assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
unsigned NumRes = TID.getNumDefs();
unsigned CurCycle = 0;
// Add root to Available queue.
if (!SUnits.empty()) {
- SUnit *RootSU = SUnitMap[DAG.getRoot().Val].front();
+ SUnit *RootSU = &SUnits[DAG.getRoot().Val->getNodeId()];
assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
RootSU->isAvailable = true;
AvailableQueue->push(RootSU);
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
SmallVector<SUnit*, 4> NotReady;
+ Sequence.reserve(SUnits.size());
while (!AvailableQueue->empty()) {
bool Delayed = false;
DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
SUnit *NewDef = CopyAndMoveSuccessors(LRDef);
if (!NewDef) {
// Issue expensive cross register class copies.
- MVT::ValueType VT = getPhysicalRegisterVT(LRDef->Node, Reg, TII);
+ MVT VT = getPhysicalRegisterVT(LRDef->Node, Reg, TII);
const TargetRegisterClass *RC =
TRI->getPhysicalRegisterRegClass(Reg, VT);
const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
std::vector<SUnit*> NotReady;
+ Sequence.reserve(SUnits.size());
while (!AvailableQueue->empty()) {
SUnit *CurSU = AvailableQueue->pop();
while (CurSU && CurSU->CycleBound > CurCycle) {
template<class SF>
class VISIBILITY_HIDDEN RegReductionPriorityQueue
: public SchedulingPriorityQueue {
- std::set<SUnit*, SF> Queue;
+ PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue;
unsigned currentQueueId;
public:
RegReductionPriorityQueue() :
Queue(SF(this)), currentQueueId(0) {}
- virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
- std::vector<SUnit> &sunits) {}
+ virtual void initNodes(std::vector<SUnit> &sunits) {}
virtual void addNode(const SUnit *SU) {}
void push(SUnit *U) {
assert(!U->NodeQueueId && "Node in the queue already");
U->NodeQueueId = ++currentQueueId;
- Queue.insert(U);
+ Queue.push(U);
}
void push_all(const std::vector<SUnit *> &Nodes) {
SUnit *pop() {
if (empty()) return NULL;
- typename std::set<SUnit*, SF>::iterator i = prior(Queue.end());
- SUnit *V = *i;
- Queue.erase(i);
+ SUnit *V = Queue.top();
+ Queue.pop();
V->NodeQueueId = 0;
return V;
}
void remove(SUnit *SU) {
assert(!Queue.empty() && "Queue is empty!");
- size_t RemovedNum = Queue.erase(SU);
- RemovedNum; // Silence compiler warning.
- assert(RemovedNum > 0 && "Not in queue!");
- assert(RemovedNum == 1 && "Multiple times in the queue!");
+ assert(SU->NodeQueueId != 0 && "Not in queue!");
+ Queue.erase_one(SU);
SU->NodeQueueId = 0;
}
};
- template<class SF>
class VISIBILITY_HIDDEN BURegReductionPriorityQueue
- : public RegReductionPriorityQueue<SF> {
- // SUnitMap SDNode to SUnit mapping (n -> n).
- DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
-
+ : public RegReductionPriorityQueue<bu_ls_rr_sort> {
// SUnits - The SUnits for the current graph.
const std::vector<SUnit> *SUnits;
const TargetRegisterInfo *tri)
: TII(tii), TRI(tri), scheduleDAG(NULL) {}
- void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
- std::vector<SUnit> &sunits) {
- SUnitMap = &sumap;
+ void initNodes(std::vector<SUnit> &sunits) {
SUnits = &sunits;
// Add pseudo dependency edges for two-address nodes.
AddPseudoTwoAddrDeps();
};
- template<class SF>
class VISIBILITY_HIDDEN TDRegReductionPriorityQueue
- : public RegReductionPriorityQueue<SF> {
- // SUnitMap SDNode to SUnit mapping (n -> n).
- DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
-
+ : public RegReductionPriorityQueue<td_ls_rr_sort> {
// SUnits - The SUnits for the current graph.
const std::vector<SUnit> *SUnits;
public:
TDRegReductionPriorityQueue() {}
- void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
- std::vector<SUnit> &sunits) {
- SUnitMap = &sumap;
+ void initNodes(std::vector<SUnit> &sunits) {
SUnits = &sunits;
// Calculate node priorities.
CalculateSethiUllmanNumbers();
return (left->NodeQueueId > right->NodeQueueId);
}
-template<class SF> bool
-BURegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) {
+bool
+BURegReductionPriorityQueue::canClobber(const SUnit *SU, const SUnit *Op) {
if (SU->isTwoAddress) {
unsigned Opc = SU->Node->getTargetOpcode();
const TargetInstrDesc &TID = TII->get(Opc);
for (unsigned i = 0; i != NumOps; ++i) {
if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
SDNode *DU = SU->Node->getOperand(i).Val;
- if ((*SUnitMap).find(DU) != (*SUnitMap).end() &&
- Op == (*SUnitMap)[DU][SU->InstanceNo])
+ if (DU->getNodeId() != -1 &&
+ Op->OrigNode == &(*SUnits)[DU->getNodeId()])
return true;
}
}
}
/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
-/// physical register def.
+/// physical register defs.
static bool canClobberPhysRegDefs(SUnit *SuccSU, SUnit *SU,
const TargetInstrInfo *TII,
const TargetRegisterInfo *TRI) {
SDNode *N = SuccSU->Node;
unsigned NumDefs = TII->get(N->getTargetOpcode()).getNumDefs();
const unsigned *ImpDefs = TII->get(N->getTargetOpcode()).getImplicitDefs();
- if (!ImpDefs)
- return false;
+ assert(ImpDefs && "Caller should check hasPhysRegDefs");
const unsigned *SUImpDefs =
TII->get(SU->Node->getTargetOpcode()).getImplicitDefs();
if (!SUImpDefs)
return false;
for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
- MVT::ValueType VT = N->getValueType(i);
+ MVT VT = N->getValueType(i);
if (VT == MVT::Flag || VT == MVT::Other)
continue;
unsigned Reg = ImpDefs[i - NumDefs];
/// one that has a CopyToReg use (more likely to be a loop induction update).
/// If both are two-address, but one is commutable while the other is not
/// commutable, favor the one that's not commutable.
-template<class SF>
-void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
+void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() {
for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
SUnit *SU = (SUnit *)&((*SUnits)[i]);
if (!SU->isTwoAddress)
for (unsigned j = 0; j != NumOps; ++j) {
if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) != -1) {
SDNode *DU = SU->Node->getOperand(j).Val;
- if ((*SUnitMap).find(DU) == (*SUnitMap).end())
+ if (DU->getNodeId() == -1)
continue;
- SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo];
+ const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
if (!DUSU) continue;
- for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end();
- I != E; ++I) {
+ for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
+ E = DUSU->Succs.end(); I != E; ++I) {
if (I->isCtrl) continue;
SUnit *SuccSU = I->Dep;
if (SuccSU == SU)
/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
/// Smaller number is the higher priority.
-template<class SF>
-unsigned BURegReductionPriorityQueue<SF>::
+unsigned BURegReductionPriorityQueue::
CalcNodeSethiUllmanNumber(const SUnit *SU) {
unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
if (SethiUllmanNumber != 0)
/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
/// scheduling units.
-template<class SF>
-void BURegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
+void BURegReductionPriorityQueue::CalculateSethiUllmanNumbers() {
SethiUllmanNumbers.assign(SUnits->size(), 0);
for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
/// Smaller number is the higher priority.
-template<class SF>
-unsigned TDRegReductionPriorityQueue<SF>::
+unsigned TDRegReductionPriorityQueue::
CalcNodeSethiUllmanNumber(const SUnit *SU) {
unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
if (SethiUllmanNumber != 0)
/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
/// scheduling units.
-template<class SF>
-void TDRegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
+void TDRegReductionPriorityQueue::CalculateSethiUllmanNumbers() {
SethiUllmanNumbers.assign(SUnits->size(), 0);
for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo();
const TargetRegisterInfo *TRI = DAG->getTarget().getRegisterInfo();
- BURegReductionPriorityQueue<bu_ls_rr_sort> *priorityQueue =
- new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII, TRI);
+ BURegReductionPriorityQueue *priorityQueue =
+ new BURegReductionPriorityQueue(TII, TRI);
ScheduleDAGRRList * scheduleDAG =
new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, priorityQueue);
SelectionDAG *DAG,
MachineBasicBlock *BB) {
return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false,
- new TDRegReductionPriorityQueue<td_ls_rr_sort>());
+ new TDRegReductionPriorityQueue());
}