diff options
author | Evan Cheng <evan.cheng@apple.com> | 2008-07-01 18:05:03 +0000 |
---|---|---|
committer | Evan Cheng <evan.cheng@apple.com> | 2008-07-01 18:05:03 +0000 |
commit | 4576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5 (patch) | |
tree | a690f1ae281e93b319feae2d94150ea71278ec4f /lib/CodeGen/SelectionDAG | |
parent | ebffb660a68384dd8b5e2ff36d68e94a3920611b (diff) | |
download | external_llvm-4576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5.zip external_llvm-4576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5.tar.gz external_llvm-4576f6d7a9c0f2c6a3b6c5d4d8a3063bbf763ae5.tar.bz2 |
Do not use computationally expensive scheduling heuristics with -fast.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52971 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/SelectionDAG')
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp | 2 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 98 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 9 |
3 files changed, 59 insertions, 50 deletions
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index 40c26c2..8a1dade 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -548,7 +548,7 @@ void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { /// recognizer and deletes it when done. ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB) { + MachineBasicBlock *BB, bool Fast) { return new ScheduleDAGList(*DAG, BB, DAG->getTarget(), new LatencyPriorityQueue(), IS->CreateTargetHazardRecognizer()); diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index f6d68f1..f881737 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -58,6 +58,8 @@ private: /// isBottomUp - This is true if the scheduling problem is bottom-up, false if /// it is top-down. bool isBottomUp; + + bool Fast; /// AvailableQueue - The priority queue to use for the available SUnits. SchedulingPriorityQueue *AvailableQueue; @@ -71,9 +73,9 @@ private: public: ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb, - const TargetMachine &tm, bool isbottomup, - SchedulingPriorityQueue *availqueue) - : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), + const TargetMachine &tm, bool isbottomup, bool f, + SchedulingPriorityQueue *availqueue) + : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), Fast(f), AvailableQueue(availqueue) { } @@ -144,36 +146,6 @@ private: /// even after dynamic insertions of new edges. /// This allows a very fast implementation of IsReachable. - - /** - The idea of the algorithm is taken from - "Online algorithms for managing the topological order of - a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly - This is the MNR algorithm, which was first introduced by - A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in - "Maintaining a topological order under edge insertions". - - Short description of the algorithm: - - Topological ordering, ord, of a DAG maps each node to a topological - index so that for all edges X->Y it is the case that ord(X) < ord(Y). - - This means that if there is a path from the node X to the node Z, - then ord(X) < ord(Z). - - This property can be used to check for reachability of nodes: - if Z is reachable from X, then an insertion of the edge Z->X would - create a cycle. - - The algorithm first computes a topological ordering for the DAG by initializing - the Index2Node and Node2Index arrays and then tries to keep the ordering - up-to-date after edge insertions by reordering the DAG. - - On insertion of the edge X->Y, the algorithm first marks by calling DFS the - nodes reachable from Y, and then shifts them using Shift to lie immediately - after X in Index2Node. - */ - /// InitDAGTopologicalSorting - create the initial topological /// ordering from the DAG to be scheduled. void InitDAGTopologicalSorting(); @@ -212,8 +184,10 @@ void ScheduleDAGRRList::Schedule() { DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) SUnits[su].dumpAll(&DAG)); - CalculateDepths(); - CalculateHeights(); + if (!Fast) { + CalculateDepths(); + CalculateHeights(); + } InitDAGTopologicalSorting(); AvailableQueue->initNodes(SUnits); @@ -225,8 +199,9 @@ void ScheduleDAGRRList::Schedule() { ListScheduleTopDown(); AvailableQueue->releaseState(); - - CommuteNodesToReducePressure(); + + if (!Fast) + CommuteNodesToReducePressure(); DOUT << "*** Final schedule ***\n"; DEBUG(dumpSchedule()); @@ -449,6 +424,33 @@ inline void ScheduleDAGRRList::Allocate(int n, int index) { /// InitDAGTopologicalSorting - create the initial topological /// ordering from the DAG to be scheduled. + +/// The idea of the algorithm is taken from +/// "Online algorithms for managing the topological order of +/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly +/// This is the MNR algorithm, which was first introduced by +/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in +/// "Maintaining a topological order under edge insertions". +/// +/// Short description of the algorithm: +/// +/// Topological ordering, ord, of a DAG maps each node to a topological +/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). +/// +/// This means that if there is a path from the node X to the node Z, +/// then ord(X) < ord(Z). +/// +/// This property can be used to check for reachability of nodes: +/// if Z is reachable from X, then an insertion of the edge Z->X would +/// create a cycle. +/// +/// The algorithm first computes a topological ordering for the DAG by +/// initializing the Index2Node and Node2Index arrays and then tries to keep +/// the ordering up-to-date after edge insertions by reordering the DAG. +/// +/// On insertion of the edge X->Y, the algorithm first marks by calling DFS +/// the nodes reachable from Y, and then shifts them using Shift to lie +/// immediately after X in Index2Node. void ScheduleDAGRRList::InitDAGTopologicalSorting() { unsigned DAGSize = SUnits.size(); std::vector<unsigned> InDegree(DAGSize); @@ -1335,15 +1337,19 @@ namespace { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; ScheduleDAGRRList *scheduleDAG; + + bool Fast; public: explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii, - const TargetRegisterInfo *tri) - : TII(tii), TRI(tri), scheduleDAG(NULL) {} + const TargetRegisterInfo *tri, + bool f) + : TII(tii), TRI(tri), scheduleDAG(NULL), Fast(f) {} void initNodes(std::vector<SUnit> &sunits) { SUnits = &sunits; // Add pseudo dependency edges for two-address nodes. - AddPseudoTwoAddrDeps(); + if (!Fast) + AddPseudoTwoAddrDeps(); // Calculate node priorities. CalculateSethiUllmanNumbers(); } @@ -1821,23 +1827,25 @@ void TDRegReductionPriorityQueue::CalculateSethiUllmanNumbers() { llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB) { + MachineBasicBlock *BB, + bool Fast) { const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo(); const TargetRegisterInfo *TRI = DAG->getTarget().getRegisterInfo(); BURegReductionPriorityQueue *priorityQueue = - new BURegReductionPriorityQueue(TII, TRI); + new BURegReductionPriorityQueue(TII, TRI, Fast); ScheduleDAGRRList * scheduleDAG = - new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, priorityQueue); + new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, Fast,priorityQueue); priorityQueue->setScheduleDAG(scheduleDAG); return scheduleDAG; } llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB) { - return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false, + MachineBasicBlock *BB, + bool Fast) { + return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false, Fast, new TDRegReductionPriorityQueue()); } diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 8ba2b78..9ee4192 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -266,15 +266,16 @@ namespace llvm { /// for the target. ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB) { + MachineBasicBlock *BB, + bool Fast) { TargetLowering &TLI = IS->getTargetLowering(); if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) { - return createTDListDAGScheduler(IS, DAG, BB); + return createTDListDAGScheduler(IS, DAG, BB, Fast); } else { assert(TLI.getSchedulingPreference() == TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); - return createBURRListDAGScheduler(IS, DAG, BB); + return createBURRListDAGScheduler(IS, DAG, BB, Fast); } } @@ -5611,7 +5612,7 @@ void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { RegisterScheduler::setDefault(Ctor); } - ScheduleDAG *SL = Ctor(this, &DAG, BB); + ScheduleDAG *SL = Ctor(this, &DAG, BB, FastISel); BB = SL->Run(); if (ViewSUnitDAGs) SL->viewGraph(); |