Dan Gohman | 04f4f4f | 2008-08-12 17:42:33 +0000 | [diff] [blame] | 1 | //===----- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler --===// |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This implements bottom-up and top-down register pressure reduction list |
| 11 | // schedulers, using standard algorithms. The basic approach uses a priority |
| 12 | // queue of available nodes to schedule. One at a time, nodes are taken from |
| 13 | // the priority queue (thus in priority order), checked for legality to |
| 14 | // schedule, and emitted if legal. |
| 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
Dale Johannesen | e7e7d0d | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 18 | #define DEBUG_TYPE "pre-RA-sched" |
Dan Gohman | 84fbac5 | 2009-02-06 17:22:58 +0000 | [diff] [blame] | 19 | #include "ScheduleDAGSDNodes.h" |
Jim Laskey | eb577ba | 2006-08-02 12:30:23 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/SchedulerRegistry.h" |
Dan Gohman | 79ce276 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/SelectionDAGISel.h" |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 22 | #include "llvm/Target/TargetRegisterInfo.h" |
Owen Anderson | 07000c6 | 2006-05-12 06:33:49 +0000 | [diff] [blame] | 23 | #include "llvm/Target/TargetData.h" |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 24 | #include "llvm/Target/TargetMachine.h" |
| 25 | #include "llvm/Target/TargetInstrInfo.h" |
| 26 | #include "llvm/Support/Debug.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 27 | #include "llvm/Support/Compiler.h" |
Dan Gohman | 3627e34 | 2008-06-21 18:35:25 +0000 | [diff] [blame] | 28 | #include "llvm/ADT/PriorityQueue.h" |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 29 | #include "llvm/ADT/SmallSet.h" |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 30 | #include "llvm/ADT/Statistic.h" |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 31 | #include "llvm/ADT/STLExtras.h" |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 32 | #include <climits> |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 33 | using namespace llvm; |
| 34 | |
Dan Gohman | cffbd25 | 2008-03-25 17:10:29 +0000 | [diff] [blame] | 35 | STATISTIC(NumBacktracks, "Number of times scheduler backtracked"); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 36 | STATISTIC(NumUnfolds, "Number of nodes unfolded"); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 37 | STATISTIC(NumDups, "Number of duplicated nodes"); |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 38 | STATISTIC(NumPRCopies, "Number of physical register copies"); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 39 | |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 40 | static RegisterScheduler |
| 41 | burrListDAGScheduler("list-burr", |
Dan Gohman | b8cab92 | 2008-10-14 20:25:08 +0000 | [diff] [blame] | 42 | "Bottom-up register reduction list scheduling", |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 43 | createBURRListDAGScheduler); |
| 44 | static RegisterScheduler |
| 45 | tdrListrDAGScheduler("list-tdrr", |
Dan Gohman | b8cab92 | 2008-10-14 20:25:08 +0000 | [diff] [blame] | 46 | "Top-down register reduction list scheduling", |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 47 | createTDRRListDAGScheduler); |
| 48 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 49 | namespace { |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 50 | //===----------------------------------------------------------------------===// |
| 51 | /// ScheduleDAGRRList - The actual register reduction list scheduler |
| 52 | /// implementation. This supports both top-down and bottom-up scheduling. |
| 53 | /// |
Dan Gohman | 343f0c0 | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 54 | class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes { |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 55 | private: |
| 56 | /// isBottomUp - This is true if the scheduling problem is bottom-up, false if |
| 57 | /// it is top-down. |
| 58 | bool isBottomUp; |
Evan Cheng | 4576f6d | 2008-07-01 18:05:03 +0000 | [diff] [blame] | 59 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 60 | /// AvailableQueue - The priority queue to use for the available SUnits. |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 61 | SchedulingPriorityQueue *AvailableQueue; |
| 62 | |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 63 | /// LiveRegDefs - A set of physical registers and their definition |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 64 | /// that are "live". These nodes must be scheduled before any other nodes that |
| 65 | /// modifies the registers can be scheduled. |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 66 | unsigned NumLiveRegs; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 67 | std::vector<SUnit*> LiveRegDefs; |
| 68 | std::vector<unsigned> LiveRegCycles; |
| 69 | |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 70 | /// Topo - A topological ordering for SUnits which permits fast IsReachable |
| 71 | /// and similar queries. |
| 72 | ScheduleDAGTopologicalSort Topo; |
| 73 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 74 | public: |
Dan Gohman | 79ce276 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 75 | ScheduleDAGRRList(MachineFunction &mf, |
| 76 | bool isbottomup, |
Evan Cheng | 4576f6d | 2008-07-01 18:05:03 +0000 | [diff] [blame] | 77 | SchedulingPriorityQueue *availqueue) |
Dan Gohman | 79ce276 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 78 | : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup), |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 79 | AvailableQueue(availqueue), Topo(SUnits) { |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 80 | } |
| 81 | |
| 82 | ~ScheduleDAGRRList() { |
| 83 | delete AvailableQueue; |
| 84 | } |
| 85 | |
| 86 | void Schedule(); |
| 87 | |
Roman Levenstein | 8dba9af | 2008-03-26 11:23:38 +0000 | [diff] [blame] | 88 | /// IsReachable - Checks if SU is reachable from TargetSU. |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 89 | bool IsReachable(const SUnit *SU, const SUnit *TargetSU) { |
| 90 | return Topo.IsReachable(SU, TargetSU); |
| 91 | } |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 92 | |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 93 | /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 94 | /// create a cycle. |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 95 | bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) { |
| 96 | return Topo.WillCreateCycle(SU, TargetSU); |
| 97 | } |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 98 | |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 99 | /// AddPred - adds a predecessor edge to SUnit SU. |
Roman Levenstein | 8dba9af | 2008-03-26 11:23:38 +0000 | [diff] [blame] | 100 | /// This returns true if this is a new predecessor. |
| 101 | /// Updates the topological ordering if required. |
Dan Gohman | ffa3912 | 2008-12-16 01:00:55 +0000 | [diff] [blame] | 102 | void AddPred(SUnit *SU, const SDep &D) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 103 | Topo.AddPred(SU, D.getSUnit()); |
Dan Gohman | ffa3912 | 2008-12-16 01:00:55 +0000 | [diff] [blame] | 104 | SU->addPred(D); |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 105 | } |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 106 | |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 107 | /// RemovePred - removes a predecessor edge from SUnit SU. |
| 108 | /// This returns true if an edge was removed. |
| 109 | /// Updates the topological ordering if required. |
Dan Gohman | ffa3912 | 2008-12-16 01:00:55 +0000 | [diff] [blame] | 110 | void RemovePred(SUnit *SU, const SDep &D) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 111 | Topo.RemovePred(SU, D.getSUnit()); |
Dan Gohman | ffa3912 | 2008-12-16 01:00:55 +0000 | [diff] [blame] | 112 | SU->removePred(D); |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 113 | } |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 114 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 115 | private: |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 116 | void ReleasePred(SUnit *SU, const SDep *PredEdge); |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 117 | void ReleasePredecessors(SUnit *SU, unsigned CurCycle); |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 118 | void ReleaseSucc(SUnit *SU, const SDep *SuccEdge); |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 119 | void ReleaseSuccessors(SUnit *SU); |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 120 | void CapturePred(SDep *PredEdge); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 121 | void ScheduleNodeBottomUp(SUnit*, unsigned); |
| 122 | void ScheduleNodeTopDown(SUnit*, unsigned); |
| 123 | void UnscheduleNodeBottomUp(SUnit*); |
| 124 | void BacktrackBottomUp(SUnit*, unsigned, unsigned&); |
| 125 | SUnit *CopyAndMoveSuccessors(SUnit*); |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 126 | void InsertCopiesAndMoveSuccs(SUnit*, unsigned, |
| 127 | const TargetRegisterClass*, |
| 128 | const TargetRegisterClass*, |
| 129 | SmallVector<SUnit*, 2>&); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 130 | bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 131 | void ListScheduleTopDown(); |
| 132 | void ListScheduleBottomUp(); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 133 | |
| 134 | |
| 135 | /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it. |
Roman Levenstein | 8dba9af | 2008-03-26 11:23:38 +0000 | [diff] [blame] | 136 | /// Updates the topological ordering if required. |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 137 | SUnit *CreateNewSUnit(SDNode *N) { |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 138 | unsigned NumSUnits = SUnits.size(); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 139 | SUnit *NewNode = NewSUnit(N); |
Roman Levenstein | 8dba9af | 2008-03-26 11:23:38 +0000 | [diff] [blame] | 140 | // Update the topological ordering. |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 141 | if (NewNode->NodeNum >= NumSUnits) |
| 142 | Topo.InitDAGTopologicalSorting(); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 143 | return NewNode; |
| 144 | } |
| 145 | |
Roman Levenstein | 8dba9af | 2008-03-26 11:23:38 +0000 | [diff] [blame] | 146 | /// CreateClone - Creates a new SUnit from an existing one. |
| 147 | /// Updates the topological ordering if required. |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 148 | SUnit *CreateClone(SUnit *N) { |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 149 | unsigned NumSUnits = SUnits.size(); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 150 | SUnit *NewNode = Clone(N); |
Roman Levenstein | 8dba9af | 2008-03-26 11:23:38 +0000 | [diff] [blame] | 151 | // Update the topological ordering. |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 152 | if (NewNode->NodeNum >= NumSUnits) |
| 153 | Topo.InitDAGTopologicalSorting(); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 154 | return NewNode; |
| 155 | } |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 156 | |
| 157 | /// ForceUnitLatencies - Return true, since register-pressure-reducing |
| 158 | /// scheduling doesn't need actual latency information. |
| 159 | bool ForceUnitLatencies() const { return true; } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 160 | }; |
| 161 | } // end anonymous namespace |
| 162 | |
| 163 | |
| 164 | /// Schedule - Schedule the DAG using list scheduling. |
| 165 | void ScheduleDAGRRList::Schedule() { |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 166 | DOUT << "********** List Scheduling **********\n"; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 167 | |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 168 | NumLiveRegs = 0; |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 169 | LiveRegDefs.resize(TRI->getNumRegs(), NULL); |
| 170 | LiveRegCycles.resize(TRI->getNumRegs(), 0); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 171 | |
Dan Gohman | c9a5b9e | 2008-12-23 18:36:58 +0000 | [diff] [blame] | 172 | // Build the scheduling graph. |
| 173 | BuildSchedGraph(); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 174 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 175 | DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) |
Dan Gohman | 3cc6243 | 2008-11-18 02:06:40 +0000 | [diff] [blame] | 176 | SUnits[su].dumpAll(this)); |
Dan Gohman | 21d9003 | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 177 | Topo.InitDAGTopologicalSorting(); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 178 | |
Dan Gohman | 94d7a5f | 2008-06-21 19:18:17 +0000 | [diff] [blame] | 179 | AvailableQueue->initNodes(SUnits); |
Dan Gohman | 8d1bfad | 2007-08-20 19:28:38 +0000 | [diff] [blame] | 180 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 181 | // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. |
| 182 | if (isBottomUp) |
| 183 | ListScheduleBottomUp(); |
| 184 | else |
| 185 | ListScheduleTopDown(); |
| 186 | |
| 187 | AvailableQueue->releaseState(); |
Evan Cheng | 13d41b9 | 2006-05-12 01:58:24 +0000 | [diff] [blame] | 188 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 189 | |
| 190 | //===----------------------------------------------------------------------===// |
| 191 | // Bottom-Up Scheduling |
| 192 | //===----------------------------------------------------------------------===// |
| 193 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 194 | /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to |
Dan Gohman | 8d1bfad | 2007-08-20 19:28:38 +0000 | [diff] [blame] | 195 | /// the AvailableQueue if the count reaches zero. Also update its cycle bound. |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 196 | void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 197 | SUnit *PredSU = PredEdge->getSUnit(); |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 198 | --PredSU->NumSuccsLeft; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 199 | |
| 200 | #ifndef NDEBUG |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 201 | if (PredSU->NumSuccsLeft < 0) { |
Dan Gohman | 2d093f3 | 2008-11-18 00:38:59 +0000 | [diff] [blame] | 202 | cerr << "*** Scheduling failed! ***\n"; |
Dan Gohman | 3cc6243 | 2008-11-18 02:06:40 +0000 | [diff] [blame] | 203 | PredSU->dump(this); |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 204 | cerr << " has been released too many times!\n"; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 205 | assert(0); |
| 206 | } |
| 207 | #endif |
| 208 | |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 209 | // If all the node's successors are scheduled, this node is ready |
| 210 | // to be scheduled. Ignore the special EntrySU node. |
| 211 | if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { |
Dan Gohman | 80792f3 | 2008-04-15 01:22:18 +0000 | [diff] [blame] | 212 | PredSU->isAvailable = true; |
| 213 | AvailableQueue->push(PredSU); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 214 | } |
| 215 | } |
| 216 | |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 217 | void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 218 | // Bottom up: release predecessors |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 219 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 220 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 221 | ReleasePred(SU, &*I); |
| 222 | if (I->isAssignedRegDep()) { |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 223 | // This is a physical register dependency and it's impossible or |
| 224 | // expensive to copy the register. Make sure nothing that can |
| 225 | // clobber the register is scheduled between the predecessor and |
| 226 | // this node. |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 227 | if (!LiveRegDefs[I->getReg()]) { |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 228 | ++NumLiveRegs; |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 229 | LiveRegDefs[I->getReg()] = I->getSUnit(); |
| 230 | LiveRegCycles[I->getReg()] = CurCycle; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 231 | } |
| 232 | } |
| 233 | } |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending |
| 237 | /// count of its predecessors. If a predecessor pending count is zero, add it to |
| 238 | /// the Available queue. |
| 239 | void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { |
| 240 | DOUT << "*** Scheduling [" << CurCycle << "]: "; |
| 241 | DEBUG(SU->dump(this)); |
| 242 | |
| 243 | assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); |
| 244 | SU->setHeightToAtLeast(CurCycle); |
| 245 | Sequence.push_back(SU); |
| 246 | |
| 247 | ReleasePredecessors(SU, CurCycle); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 248 | |
| 249 | // Release all the implicit physical register defs that are live. |
| 250 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 251 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 252 | if (I->isAssignedRegDep()) { |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 253 | if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) { |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 254 | assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 255 | assert(LiveRegDefs[I->getReg()] == SU && |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 256 | "Physical register dependency violated?"); |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 257 | --NumLiveRegs; |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 258 | LiveRegDefs[I->getReg()] = NULL; |
| 259 | LiveRegCycles[I->getReg()] = 0; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 260 | } |
| 261 | } |
| 262 | } |
| 263 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 264 | SU->isScheduled = true; |
Dan Gohman | 1256f5f | 2008-11-18 21:22:20 +0000 | [diff] [blame] | 265 | AvailableQueue->ScheduledNode(SU); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 266 | } |
| 267 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 268 | /// CapturePred - This does the opposite of ReleasePred. Since SU is being |
| 269 | /// unscheduled, incrcease the succ left count of its predecessors. Remove |
| 270 | /// them from AvailableQueue if necessary. |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 271 | void ScheduleDAGRRList::CapturePred(SDep *PredEdge) { |
| 272 | SUnit *PredSU = PredEdge->getSUnit(); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 273 | if (PredSU->isAvailable) { |
| 274 | PredSU->isAvailable = false; |
| 275 | if (!PredSU->isPending) |
| 276 | AvailableQueue->remove(PredSU); |
| 277 | } |
| 278 | |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 279 | ++PredSU->NumSuccsLeft; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 280 | } |
| 281 | |
| 282 | /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and |
| 283 | /// its predecessor states to reflect the change. |
| 284 | void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) { |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 285 | DOUT << "*** Unscheduling [" << SU->getHeight() << "]: "; |
Dan Gohman | 3cc6243 | 2008-11-18 02:06:40 +0000 | [diff] [blame] | 286 | DEBUG(SU->dump(this)); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 287 | |
| 288 | AvailableQueue->UnscheduledNode(SU); |
| 289 | |
| 290 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
| 291 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 292 | CapturePred(&*I); |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 293 | if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) { |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 294 | assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 295 | assert(LiveRegDefs[I->getReg()] == I->getSUnit() && |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 296 | "Physical register dependency violated?"); |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 297 | --NumLiveRegs; |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 298 | LiveRegDefs[I->getReg()] = NULL; |
| 299 | LiveRegCycles[I->getReg()] = 0; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 300 | } |
| 301 | } |
| 302 | |
| 303 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 304 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 305 | if (I->isAssignedRegDep()) { |
| 306 | if (!LiveRegDefs[I->getReg()]) { |
| 307 | LiveRegDefs[I->getReg()] = SU; |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 308 | ++NumLiveRegs; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 309 | } |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 310 | if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()]) |
| 311 | LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight(); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 312 | } |
| 313 | } |
| 314 | |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 315 | SU->setHeightDirty(); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 316 | SU->isScheduled = false; |
| 317 | SU->isAvailable = true; |
| 318 | AvailableQueue->push(SU); |
| 319 | } |
| 320 | |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 321 | /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 322 | /// BTCycle in order to schedule a specific node. |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 323 | void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, |
| 324 | unsigned &CurCycle) { |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 325 | SUnit *OldSU = NULL; |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 326 | while (CurCycle > BtCycle) { |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 327 | OldSU = Sequence.back(); |
| 328 | Sequence.pop_back(); |
| 329 | if (SU->isSucc(OldSU)) |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 330 | // Don't try to remove SU from AvailableQueue. |
| 331 | SU->isAvailable = false; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 332 | UnscheduleNodeBottomUp(OldSU); |
| 333 | --CurCycle; |
| 334 | } |
| 335 | |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 336 | assert(!SU->isSucc(OldSU) && "Something is wrong!"); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 337 | |
| 338 | ++NumBacktracks; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 339 | } |
| 340 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 341 | /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled |
| 342 | /// successors to the newly created node. |
| 343 | SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { |
Dan Gohman | d23e0f8 | 2008-11-13 23:24:17 +0000 | [diff] [blame] | 344 | if (SU->getNode()->getFlaggedNode()) |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 345 | return NULL; |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 346 | |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 347 | SDNode *N = SU->getNode(); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 348 | if (!N) |
| 349 | return NULL; |
| 350 | |
| 351 | SUnit *NewSU; |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 352 | bool TryUnfold = false; |
Evan Cheng | d5cb5a4 | 2007-10-05 01:42:35 +0000 | [diff] [blame] | 353 | for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { |
Duncan Sands | 83ec4b6 | 2008-06-06 12:08:01 +0000 | [diff] [blame] | 354 | MVT VT = N->getValueType(i); |
Evan Cheng | d5cb5a4 | 2007-10-05 01:42:35 +0000 | [diff] [blame] | 355 | if (VT == MVT::Flag) |
| 356 | return NULL; |
| 357 | else if (VT == MVT::Other) |
| 358 | TryUnfold = true; |
| 359 | } |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 360 | for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 361 | const SDValue &Op = N->getOperand(i); |
Gabor Greif | ba36cb5 | 2008-08-28 21:40:38 +0000 | [diff] [blame] | 362 | MVT VT = Op.getNode()->getValueType(Op.getResNo()); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 363 | if (VT == MVT::Flag) |
| 364 | return NULL; |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 365 | } |
| 366 | |
| 367 | if (TryUnfold) { |
Dan Gohman | 4c8c830 | 2008-06-21 15:52:51 +0000 | [diff] [blame] | 368 | SmallVector<SDNode*, 2> NewNodes; |
Dan Gohman | a23b3b8 | 2008-11-13 21:21:28 +0000 | [diff] [blame] | 369 | if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 370 | return NULL; |
| 371 | |
| 372 | DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; |
| 373 | assert(NewNodes.size() == 2 && "Expected a load folding node!"); |
| 374 | |
| 375 | N = NewNodes[1]; |
| 376 | SDNode *LoadNode = NewNodes[0]; |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 377 | unsigned NumVals = N->getNumValues(); |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 378 | unsigned OldNumVals = SU->getNode()->getNumValues(); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 379 | for (unsigned i = 0; i != NumVals; ++i) |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 380 | DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); |
| 381 | DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), |
Dan Gohman | a23b3b8 | 2008-11-13 21:21:28 +0000 | [diff] [blame] | 382 | SDValue(LoadNode, 1)); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 383 | |
Dan Gohman | b13af2f | 2008-11-11 21:34:44 +0000 | [diff] [blame] | 384 | // LoadNode may already exist. This can happen when there is another |
| 385 | // load from the same location and producing the same type of value |
| 386 | // but it has different alignment or volatileness. |
| 387 | bool isNewLoad = true; |
| 388 | SUnit *LoadSU; |
| 389 | if (LoadNode->getNodeId() != -1) { |
| 390 | LoadSU = &SUnits[LoadNode->getNodeId()]; |
| 391 | isNewLoad = false; |
| 392 | } else { |
| 393 | LoadSU = CreateNewSUnit(LoadNode); |
| 394 | LoadNode->setNodeId(LoadSU->NodeNum); |
Dan Gohman | b13af2f | 2008-11-11 21:34:44 +0000 | [diff] [blame] | 395 | ComputeLatency(LoadSU); |
| 396 | } |
| 397 | |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 398 | SUnit *NewSU = CreateNewSUnit(N); |
Dan Gohman | 94d7a5f | 2008-06-21 19:18:17 +0000 | [diff] [blame] | 399 | assert(N->getNodeId() == -1 && "Node already inserted!"); |
| 400 | N->setNodeId(NewSU->NodeNum); |
Dan Gohman | 4c8c830 | 2008-06-21 15:52:51 +0000 | [diff] [blame] | 401 | |
Dan Gohman | e8be6c6 | 2008-07-17 19:10:17 +0000 | [diff] [blame] | 402 | const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); |
Dan Gohman | 94ebde1 | 2008-02-16 00:25:40 +0000 | [diff] [blame] | 403 | for (unsigned i = 0; i != TID.getNumOperands(); ++i) { |
Chris Lattner | 3db805e | 2008-01-07 06:47:00 +0000 | [diff] [blame] | 404 | if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 405 | NewSU->isTwoAddress = true; |
| 406 | break; |
| 407 | } |
| 408 | } |
Chris Lattner | 3db805e | 2008-01-07 06:47:00 +0000 | [diff] [blame] | 409 | if (TID.isCommutable()) |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 410 | NewSU->isCommutable = true; |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 411 | ComputeLatency(NewSU); |
| 412 | |
Dan Gohman | fa9afef | 2009-03-23 20:20:43 +0000 | [diff] [blame] | 413 | // Record all the edges to and from the old SU, by category. |
Dan Gohman | 16e8eda | 2009-03-06 02:23:01 +0000 | [diff] [blame] | 414 | SmallVector<SDep, 4> ChainPreds; |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 415 | SmallVector<SDep, 4> ChainSuccs; |
| 416 | SmallVector<SDep, 4> LoadPreds; |
| 417 | SmallVector<SDep, 4> NodePreds; |
| 418 | SmallVector<SDep, 4> NodeSuccs; |
| 419 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
| 420 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 421 | if (I->isCtrl()) |
Dan Gohman | 16e8eda | 2009-03-06 02:23:01 +0000 | [diff] [blame] | 422 | ChainPreds.push_back(*I); |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 423 | else if (I->getSUnit()->getNode() && |
| 424 | I->getSUnit()->getNode()->isOperandOf(LoadNode)) |
| 425 | LoadPreds.push_back(*I); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 426 | else |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 427 | NodePreds.push_back(*I); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 428 | } |
| 429 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 430 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 431 | if (I->isCtrl()) |
| 432 | ChainSuccs.push_back(*I); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 433 | else |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 434 | NodeSuccs.push_back(*I); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 435 | } |
| 436 | |
Dan Gohman | fa9afef | 2009-03-23 20:20:43 +0000 | [diff] [blame] | 437 | // Now assign edges to the newly-created nodes. |
Dan Gohman | 16e8eda | 2009-03-06 02:23:01 +0000 | [diff] [blame] | 438 | for (unsigned i = 0, e = ChainPreds.size(); i != e; ++i) { |
| 439 | const SDep &Pred = ChainPreds[i]; |
| 440 | RemovePred(SU, Pred); |
Dan Gohman | 80792f3 | 2008-04-15 01:22:18 +0000 | [diff] [blame] | 441 | if (isNewLoad) |
Dan Gohman | 16e8eda | 2009-03-06 02:23:01 +0000 | [diff] [blame] | 442 | AddPred(LoadSU, Pred); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 443 | } |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 444 | for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 445 | const SDep &Pred = LoadPreds[i]; |
| 446 | RemovePred(SU, Pred); |
Dan Gohman | 16e8eda | 2009-03-06 02:23:01 +0000 | [diff] [blame] | 447 | if (isNewLoad) |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 448 | AddPred(LoadSU, Pred); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 449 | } |
| 450 | for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 451 | const SDep &Pred = NodePreds[i]; |
| 452 | RemovePred(SU, Pred); |
| 453 | AddPred(NewSU, Pred); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 454 | } |
| 455 | for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 456 | SDep D = NodeSuccs[i]; |
| 457 | SUnit *SuccDep = D.getSUnit(); |
| 458 | D.setSUnit(SU); |
| 459 | RemovePred(SuccDep, D); |
| 460 | D.setSUnit(NewSU); |
| 461 | AddPred(SuccDep, D); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 462 | } |
| 463 | for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 464 | SDep D = ChainSuccs[i]; |
| 465 | SUnit *SuccDep = D.getSUnit(); |
| 466 | D.setSUnit(SU); |
| 467 | RemovePred(SuccDep, D); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 468 | if (isNewLoad) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 469 | D.setSUnit(LoadSU); |
| 470 | AddPred(SuccDep, D); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 471 | } |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 472 | } |
Dan Gohman | fa9afef | 2009-03-23 20:20:43 +0000 | [diff] [blame] | 473 | |
| 474 | // Add a data dependency to reflect that NewSU reads the value defined |
| 475 | // by LoadSU. |
| 476 | AddPred(NewSU, SDep(LoadSU, SDep::Data, LoadSU->Latency)); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 477 | |
Evan Cheng | beec823 | 2007-12-18 08:42:10 +0000 | [diff] [blame] | 478 | if (isNewLoad) |
| 479 | AvailableQueue->addNode(LoadSU); |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 480 | AvailableQueue->addNode(NewSU); |
| 481 | |
| 482 | ++NumUnfolds; |
| 483 | |
| 484 | if (NewSU->NumSuccsLeft == 0) { |
| 485 | NewSU->isAvailable = true; |
| 486 | return NewSU; |
Evan Cheng | beec823 | 2007-12-18 08:42:10 +0000 | [diff] [blame] | 487 | } |
| 488 | SU = NewSU; |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 489 | } |
| 490 | |
| 491 | DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 492 | NewSU = CreateClone(SU); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 493 | |
| 494 | // New SUnit has the exact same predecessors. |
| 495 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
| 496 | I != E; ++I) |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 497 | if (!I->isArtificial()) |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 498 | AddPred(NewSU, *I); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 499 | |
| 500 | // Only copy scheduled successors. Cut them from old node's successor |
| 501 | // list and move them over. |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 502 | SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 503 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 504 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 505 | if (I->isArtificial()) |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 506 | continue; |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 507 | SUnit *SuccSU = I->getSUnit(); |
| 508 | if (SuccSU->isScheduled) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 509 | SDep D = *I; |
| 510 | D.setSUnit(NewSU); |
| 511 | AddPred(SuccSU, D); |
| 512 | D.setSUnit(SU); |
| 513 | DelDeps.push_back(std::make_pair(SuccSU, D)); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 514 | } |
| 515 | } |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 516 | for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 517 | RemovePred(DelDeps[i].first, DelDeps[i].second); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 518 | |
| 519 | AvailableQueue->updateNode(SU); |
| 520 | AvailableQueue->addNode(NewSU); |
| 521 | |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 522 | ++NumDups; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 523 | return NewSU; |
| 524 | } |
| 525 | |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 526 | /// InsertCopiesAndMoveSuccs - Insert register copies and move all |
| 527 | /// scheduled successors of the given SUnit to the last copy. |
| 528 | void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, |
| 529 | const TargetRegisterClass *DestRC, |
| 530 | const TargetRegisterClass *SrcRC, |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 531 | SmallVector<SUnit*, 2> &Copies) { |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 532 | SUnit *CopyFromSU = CreateNewSUnit(NULL); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 533 | CopyFromSU->CopySrcRC = SrcRC; |
| 534 | CopyFromSU->CopyDstRC = DestRC; |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 535 | |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 536 | SUnit *CopyToSU = CreateNewSUnit(NULL); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 537 | CopyToSU->CopySrcRC = DestRC; |
| 538 | CopyToSU->CopyDstRC = SrcRC; |
| 539 | |
| 540 | // Only copy scheduled successors. Cut them from old node's successor |
| 541 | // list and move them over. |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 542 | SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 543 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 544 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 545 | if (I->isArtificial()) |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 546 | continue; |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 547 | SUnit *SuccSU = I->getSUnit(); |
| 548 | if (SuccSU->isScheduled) { |
| 549 | SDep D = *I; |
| 550 | D.setSUnit(CopyToSU); |
| 551 | AddPred(SuccSU, D); |
| 552 | DelDeps.push_back(std::make_pair(SuccSU, *I)); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 553 | } |
| 554 | } |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 555 | for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 556 | RemovePred(DelDeps[i].first, DelDeps[i].second); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 557 | |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 558 | AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg)); |
| 559 | AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0)); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 560 | |
| 561 | AvailableQueue->updateNode(SU); |
| 562 | AvailableQueue->addNode(CopyFromSU); |
| 563 | AvailableQueue->addNode(CopyToSU); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 564 | Copies.push_back(CopyFromSU); |
| 565 | Copies.push_back(CopyToSU); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 566 | |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 567 | ++NumPRCopies; |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 568 | } |
| 569 | |
| 570 | /// getPhysicalRegisterVT - Returns the ValueType of the physical register |
| 571 | /// definition of the specified node. |
| 572 | /// FIXME: Move to SelectionDAG? |
Duncan Sands | 83ec4b6 | 2008-06-06 12:08:01 +0000 | [diff] [blame] | 573 | static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, |
| 574 | const TargetInstrInfo *TII) { |
Dan Gohman | e8be6c6 | 2008-07-17 19:10:17 +0000 | [diff] [blame] | 575 | const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 576 | assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); |
Chris Lattner | 349c495 | 2008-01-07 03:13:06 +0000 | [diff] [blame] | 577 | unsigned NumRes = TID.getNumDefs(); |
| 578 | for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { |
Evan Cheng | 42d6027 | 2007-09-26 21:36:17 +0000 | [diff] [blame] | 579 | if (Reg == *ImpDef) |
| 580 | break; |
| 581 | ++NumRes; |
| 582 | } |
| 583 | return N->getValueType(NumRes); |
| 584 | } |
| 585 | |
Evan Cheng | 599a6a8 | 2009-03-04 01:41:49 +0000 | [diff] [blame] | 586 | /// CheckForLiveRegDef - Return true and update live register vector if the |
| 587 | /// specified register def of the specified SUnit clobbers any "live" registers. |
| 588 | static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, |
| 589 | std::vector<SUnit*> &LiveRegDefs, |
| 590 | SmallSet<unsigned, 4> &RegAdded, |
| 591 | SmallVector<unsigned, 4> &LRegs, |
| 592 | const TargetRegisterInfo *TRI) { |
| 593 | bool Added = false; |
| 594 | if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != SU) { |
| 595 | if (RegAdded.insert(Reg)) { |
| 596 | LRegs.push_back(Reg); |
| 597 | Added = true; |
| 598 | } |
| 599 | } |
| 600 | for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) |
| 601 | if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) { |
| 602 | if (RegAdded.insert(*Alias)) { |
| 603 | LRegs.push_back(*Alias); |
| 604 | Added = true; |
| 605 | } |
| 606 | } |
| 607 | return Added; |
| 608 | } |
| 609 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 610 | /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay |
| 611 | /// scheduling of the given node to satisfy live physical register dependencies. |
| 612 | /// If the specific node is the last one that's available to schedule, do |
| 613 | /// whatever is necessary (i.e. backtracking or cloning) to make it possible. |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 614 | bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, |
| 615 | SmallVector<unsigned, 4> &LRegs){ |
Dan Gohman | 086ec99 | 2008-09-23 18:50:48 +0000 | [diff] [blame] | 616 | if (NumLiveRegs == 0) |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 617 | return false; |
| 618 | |
Evan Cheng | cd1c00c | 2007-09-27 18:46:06 +0000 | [diff] [blame] | 619 | SmallSet<unsigned, 4> RegAdded; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 620 | // If this node would clobber any "live" register, then it's not ready. |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 621 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
| 622 | I != E; ++I) { |
Evan Cheng | 599a6a8 | 2009-03-04 01:41:49 +0000 | [diff] [blame] | 623 | if (I->isAssignedRegDep()) |
| 624 | CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs, |
| 625 | RegAdded, LRegs, TRI); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 626 | } |
| 627 | |
Dan Gohman | d23e0f8 | 2008-11-13 23:24:17 +0000 | [diff] [blame] | 628 | for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) { |
Evan Cheng | 599a6a8 | 2009-03-04 01:41:49 +0000 | [diff] [blame] | 629 | if (Node->getOpcode() == ISD::INLINEASM) { |
| 630 | // Inline asm can clobber physical defs. |
| 631 | unsigned NumOps = Node->getNumOperands(); |
| 632 | if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag) |
| 633 | --NumOps; // Ignore the flag operand. |
| 634 | |
| 635 | for (unsigned i = 2; i != NumOps;) { |
| 636 | unsigned Flags = |
| 637 | cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue(); |
Evan Cheng | 697cbbf | 2009-03-20 18:03:34 +0000 | [diff] [blame] | 638 | unsigned NumVals = (Flags & 0xffff) >> 3; |
Evan Cheng | 599a6a8 | 2009-03-04 01:41:49 +0000 | [diff] [blame] | 639 | |
| 640 | ++i; // Skip the ID value. |
| 641 | if ((Flags & 7) == 2 || (Flags & 7) == 6) { |
| 642 | // Check for def of register or earlyclobber register. |
| 643 | for (; NumVals; --NumVals, ++i) { |
| 644 | unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg(); |
| 645 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) |
| 646 | CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI); |
| 647 | } |
| 648 | } else |
| 649 | i += NumVals; |
| 650 | } |
| 651 | continue; |
| 652 | } |
| 653 | |
Dan Gohman | d23e0f8 | 2008-11-13 23:24:17 +0000 | [diff] [blame] | 654 | if (!Node->isMachineOpcode()) |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 655 | continue; |
Dan Gohman | e8be6c6 | 2008-07-17 19:10:17 +0000 | [diff] [blame] | 656 | const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 657 | if (!TID.ImplicitDefs) |
| 658 | continue; |
Evan Cheng | 599a6a8 | 2009-03-04 01:41:49 +0000 | [diff] [blame] | 659 | for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) |
| 660 | CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 661 | } |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 662 | return !LRegs.empty(); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 663 | } |
| 664 | |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 665 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 666 | /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up |
| 667 | /// schedulers. |
| 668 | void ScheduleDAGRRList::ListScheduleBottomUp() { |
| 669 | unsigned CurCycle = 0; |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 670 | |
| 671 | // Release any predecessors of the special Exit node. |
| 672 | ReleasePredecessors(&ExitSU, CurCycle); |
| 673 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 674 | // Add root to Available queue. |
Dan Gohman | 80792f3 | 2008-04-15 01:22:18 +0000 | [diff] [blame] | 675 | if (!SUnits.empty()) { |
Dan Gohman | a23b3b8 | 2008-11-13 21:21:28 +0000 | [diff] [blame] | 676 | SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; |
Dan Gohman | 80792f3 | 2008-04-15 01:22:18 +0000 | [diff] [blame] | 677 | assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); |
| 678 | RootSU->isAvailable = true; |
| 679 | AvailableQueue->push(RootSU); |
| 680 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 681 | |
| 682 | // While Available queue is not empty, grab the node with the highest |
Dan Gohman | 8d1bfad | 2007-08-20 19:28:38 +0000 | [diff] [blame] | 683 | // priority. If it is not ready put it back. Schedule the node. |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 684 | SmallVector<SUnit*, 4> NotReady; |
Dan Gohman | 8cb8245 | 2008-06-23 21:15:00 +0000 | [diff] [blame] | 685 | DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; |
Dan Gohman | 4c8c830 | 2008-06-21 15:52:51 +0000 | [diff] [blame] | 686 | Sequence.reserve(SUnits.size()); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 687 | while (!AvailableQueue->empty()) { |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 688 | bool Delayed = false; |
Dan Gohman | 8cb8245 | 2008-06-23 21:15:00 +0000 | [diff] [blame] | 689 | LRegsMap.clear(); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 690 | SUnit *CurSU = AvailableQueue->pop(); |
| 691 | while (CurSU) { |
Dan Gohman | f209c2c | 2008-11-21 01:30:54 +0000 | [diff] [blame] | 692 | SmallVector<unsigned, 4> LRegs; |
| 693 | if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) |
| 694 | break; |
| 695 | Delayed = true; |
| 696 | LRegsMap.insert(std::make_pair(CurSU, LRegs)); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 697 | |
| 698 | CurSU->isPending = true; // This SU is not in AvailableQueue right now. |
| 699 | NotReady.push_back(CurSU); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 700 | CurSU = AvailableQueue->pop(); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 701 | } |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 702 | |
| 703 | // All candidates are delayed due to live physical reg dependencies. |
| 704 | // Try backtracking, code duplication, or inserting cross class copies |
| 705 | // to resolve it. |
| 706 | if (Delayed && !CurSU) { |
| 707 | for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { |
| 708 | SUnit *TrySU = NotReady[i]; |
| 709 | SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; |
| 710 | |
| 711 | // Try unscheduling up to the point where it's safe to schedule |
| 712 | // this node. |
| 713 | unsigned LiveCycle = CurCycle; |
| 714 | for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) { |
| 715 | unsigned Reg = LRegs[j]; |
| 716 | unsigned LCycle = LiveRegCycles[Reg]; |
| 717 | LiveCycle = std::min(LiveCycle, LCycle); |
| 718 | } |
| 719 | SUnit *OldSU = Sequence[LiveCycle]; |
| 720 | if (!WillCreateCycle(TrySU, OldSU)) { |
| 721 | BacktrackBottomUp(TrySU, LiveCycle, CurCycle); |
| 722 | // Force the current node to be scheduled before the node that |
| 723 | // requires the physical reg dep. |
| 724 | if (OldSU->isAvailable) { |
| 725 | OldSU->isAvailable = false; |
| 726 | AvailableQueue->remove(OldSU); |
| 727 | } |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 728 | AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1, |
| 729 | /*Reg=*/0, /*isNormalMemory=*/false, |
| 730 | /*isMustAlias=*/false, /*isArtificial=*/true)); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 731 | // If one or more successors has been unscheduled, then the current |
| 732 | // node is no longer avaialable. Schedule a successor that's now |
| 733 | // available instead. |
| 734 | if (!TrySU->isAvailable) |
| 735 | CurSU = AvailableQueue->pop(); |
| 736 | else { |
| 737 | CurSU = TrySU; |
| 738 | TrySU->isPending = false; |
| 739 | NotReady.erase(NotReady.begin()+i); |
| 740 | } |
| 741 | break; |
| 742 | } |
| 743 | } |
| 744 | |
| 745 | if (!CurSU) { |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 746 | // Can't backtrack. If it's too expensive to copy the value, then try |
| 747 | // duplicate the nodes that produces these "too expensive to copy" |
| 748 | // values to break the dependency. In case even that doesn't work, |
| 749 | // insert cross class copies. |
| 750 | // If it's not too expensive, i.e. cost != -1, issue copies. |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 751 | SUnit *TrySU = NotReady[0]; |
| 752 | SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; |
| 753 | assert(LRegs.size() == 1 && "Can't handle this yet!"); |
| 754 | unsigned Reg = LRegs[0]; |
| 755 | SUnit *LRDef = LiveRegDefs[Reg]; |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 756 | MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); |
| 757 | const TargetRegisterClass *RC = |
| 758 | TRI->getPhysicalRegisterRegClass(Reg, VT); |
| 759 | const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); |
| 760 | |
| 761 | // If cross copy register class is null, then it must be possible copy |
| 762 | // the value directly. Do not try duplicate the def. |
| 763 | SUnit *NewDef = 0; |
| 764 | if (DestRC) |
| 765 | NewDef = CopyAndMoveSuccessors(LRDef); |
| 766 | else |
| 767 | DestRC = RC; |
Evan Cheng | f10c973 | 2007-10-05 01:39:18 +0000 | [diff] [blame] | 768 | if (!NewDef) { |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 769 | // Issue copies, these can be expensive cross register class copies. |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 770 | SmallVector<SUnit*, 2> Copies; |
Evan Cheng | c29a56d | 2009-01-12 03:19:55 +0000 | [diff] [blame] | 771 | InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); |
Evan Cheng | 84036a7 | 2009-01-09 20:42:34 +0000 | [diff] [blame] | 772 | DOUT << "Adding an edge from SU #" << TrySU->NodeNum |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 773 | << " to SU #" << Copies.front()->NodeNum << "\n"; |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 774 | AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1, |
Dan Gohman | ce0d4b7 | 2009-01-06 01:28:56 +0000 | [diff] [blame] | 775 | /*Reg=*/0, /*isNormalMemory=*/false, |
| 776 | /*isMustAlias=*/false, |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 777 | /*isArtificial=*/true)); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 778 | NewDef = Copies.back(); |
| 779 | } |
| 780 | |
Evan Cheng | 84036a7 | 2009-01-09 20:42:34 +0000 | [diff] [blame] | 781 | DOUT << "Adding an edge from SU #" << NewDef->NodeNum |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 782 | << " to SU #" << TrySU->NodeNum << "\n"; |
| 783 | LiveRegDefs[Reg] = NewDef; |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 784 | AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1, |
Dan Gohman | ce0d4b7 | 2009-01-06 01:28:56 +0000 | [diff] [blame] | 785 | /*Reg=*/0, /*isNormalMemory=*/false, |
| 786 | /*isMustAlias=*/false, |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 787 | /*isArtificial=*/true)); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 788 | TrySU->isAvailable = false; |
| 789 | CurSU = NewDef; |
| 790 | } |
| 791 | |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 792 | assert(CurSU && "Unable to resolve live physical register dependencies!"); |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 793 | } |
| 794 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 795 | // Add the nodes that aren't ready back onto the available list. |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 796 | for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { |
| 797 | NotReady[i]->isPending = false; |
Evan Cheng | a2ee275 | 2007-09-27 07:09:03 +0000 | [diff] [blame] | 798 | // May no longer be available due to backtracking. |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 799 | if (NotReady[i]->isAvailable) |
| 800 | AvailableQueue->push(NotReady[i]); |
| 801 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 802 | NotReady.clear(); |
| 803 | |
Dan Gohman | 47d1a21 | 2008-11-21 00:10:42 +0000 | [diff] [blame] | 804 | if (CurSU) |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 805 | ScheduleNodeBottomUp(CurSU, CurCycle); |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 806 | ++CurCycle; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 807 | } |
| 808 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 809 | // Reverse the order if it is bottom up. |
| 810 | std::reverse(Sequence.begin(), Sequence.end()); |
| 811 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 812 | #ifndef NDEBUG |
Dan Gohman | a1e6d36 | 2008-11-20 01:26:25 +0000 | [diff] [blame] | 813 | VerifySchedule(isBottomUp); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 814 | #endif |
| 815 | } |
| 816 | |
| 817 | //===----------------------------------------------------------------------===// |
| 818 | // Top-Down Scheduling |
| 819 | //===----------------------------------------------------------------------===// |
| 820 | |
| 821 | /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to |
Dan Gohman | 8d1bfad | 2007-08-20 19:28:38 +0000 | [diff] [blame] | 822 | /// the AvailableQueue if the count reaches zero. Also update its cycle bound. |
Dan Gohman | 1cc6b8e | 2009-01-29 19:49:27 +0000 | [diff] [blame] | 823 | void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 824 | SUnit *SuccSU = SuccEdge->getSUnit(); |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 825 | --SuccSU->NumPredsLeft; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 826 | |
| 827 | #ifndef NDEBUG |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 828 | if (SuccSU->NumPredsLeft < 0) { |
Dan Gohman | 2d093f3 | 2008-11-18 00:38:59 +0000 | [diff] [blame] | 829 | cerr << "*** Scheduling failed! ***\n"; |
Dan Gohman | 3cc6243 | 2008-11-18 02:06:40 +0000 | [diff] [blame] | 830 | SuccSU->dump(this); |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 831 | cerr << " has been released too many times!\n"; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 832 | assert(0); |
| 833 | } |
| 834 | #endif |
| 835 | |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 836 | // If all the node's predecessors are scheduled, this node is ready |
| 837 | // to be scheduled. Ignore the special ExitSU node. |
| 838 | if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 839 | SuccSU->isAvailable = true; |
| 840 | AvailableQueue->push(SuccSU); |
| 841 | } |
| 842 | } |
| 843 | |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 844 | void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) { |
| 845 | // Top down: release successors |
| 846 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 847 | I != E; ++I) { |
| 848 | assert(!I->isAssignedRegDep() && |
| 849 | "The list-tdrr scheduler doesn't yet support physreg dependencies!"); |
| 850 | |
| 851 | ReleaseSucc(SU, &*I); |
| 852 | } |
| 853 | } |
| 854 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 855 | /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending |
| 856 | /// count of its successors. If a successor pending count is zero, add it to |
| 857 | /// the Available queue. |
Evan Cheng | 6b8e5a9 | 2006-05-30 18:05:39 +0000 | [diff] [blame] | 858 | void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 859 | DOUT << "*** Scheduling [" << CurCycle << "]: "; |
Dan Gohman | 3cc6243 | 2008-11-18 02:06:40 +0000 | [diff] [blame] | 860 | DEBUG(SU->dump(this)); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 861 | |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 862 | assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); |
| 863 | SU->setDepthToAtLeast(CurCycle); |
Dan Gohman | 8123419 | 2008-11-17 21:31:02 +0000 | [diff] [blame] | 864 | Sequence.push_back(SU); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 865 | |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 866 | ReleaseSuccessors(SU); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 867 | SU->isScheduled = true; |
Dan Gohman | 8123419 | 2008-11-17 21:31:02 +0000 | [diff] [blame] | 868 | AvailableQueue->ScheduledNode(SU); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 869 | } |
| 870 | |
Dan Gohman | 8d1bfad | 2007-08-20 19:28:38 +0000 | [diff] [blame] | 871 | /// ListScheduleTopDown - The main loop of list scheduling for top-down |
| 872 | /// schedulers. |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 873 | void ScheduleDAGRRList::ListScheduleTopDown() { |
| 874 | unsigned CurCycle = 0; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 875 | |
Dan Gohman | 9e64bbb | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 876 | // Release any successors of the special Entry node. |
| 877 | ReleaseSuccessors(&EntrySU); |
| 878 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 879 | // All leaves to Available queue. |
| 880 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
| 881 | // It is available if it has no predecessors. |
Dan Gohman | 80792f3 | 2008-04-15 01:22:18 +0000 | [diff] [blame] | 882 | if (SUnits[i].Preds.empty()) { |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 883 | AvailableQueue->push(&SUnits[i]); |
| 884 | SUnits[i].isAvailable = true; |
| 885 | } |
| 886 | } |
| 887 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 888 | // While Available queue is not empty, grab the node with the highest |
Dan Gohman | 8d1bfad | 2007-08-20 19:28:38 +0000 | [diff] [blame] | 889 | // priority. If it is not ready put it back. Schedule the node. |
Dan Gohman | 4c8c830 | 2008-06-21 15:52:51 +0000 | [diff] [blame] | 890 | Sequence.reserve(SUnits.size()); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 891 | while (!AvailableQueue->empty()) { |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 892 | SUnit *CurSU = AvailableQueue->pop(); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 893 | |
Dan Gohman | 47d1a21 | 2008-11-21 00:10:42 +0000 | [diff] [blame] | 894 | if (CurSU) |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 895 | ScheduleNodeTopDown(CurSU, CurCycle); |
Dan Gohman | 80792f3 | 2008-04-15 01:22:18 +0000 | [diff] [blame] | 896 | ++CurCycle; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 897 | } |
| 898 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 899 | #ifndef NDEBUG |
Dan Gohman | a1e6d36 | 2008-11-20 01:26:25 +0000 | [diff] [blame] | 900 | VerifySchedule(isBottomUp); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 901 | #endif |
| 902 | } |
| 903 | |
| 904 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 905 | //===----------------------------------------------------------------------===// |
| 906 | // RegReductionPriorityQueue Implementation |
| 907 | //===----------------------------------------------------------------------===// |
| 908 | // |
| 909 | // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers |
| 910 | // to reduce register pressure. |
| 911 | // |
| 912 | namespace { |
| 913 | template<class SF> |
| 914 | class RegReductionPriorityQueue; |
| 915 | |
| 916 | /// Sorting functions for the Available queue. |
| 917 | struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { |
| 918 | RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; |
| 919 | bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} |
| 920 | bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} |
| 921 | |
| 922 | bool operator()(const SUnit* left, const SUnit* right) const; |
| 923 | }; |
| 924 | |
| 925 | struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { |
| 926 | RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; |
| 927 | td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} |
| 928 | td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} |
| 929 | |
| 930 | bool operator()(const SUnit* left, const SUnit* right) const; |
| 931 | }; |
| 932 | } // end anonymous namespace |
| 933 | |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 934 | /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number. |
| 935 | /// Smaller number is the higher priority. |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 936 | static unsigned |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 937 | CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) { |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 938 | unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum]; |
| 939 | if (SethiUllmanNumber != 0) |
| 940 | return SethiUllmanNumber; |
| 941 | |
| 942 | unsigned Extra = 0; |
| 943 | for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
| 944 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 945 | if (I->isCtrl()) continue; // ignore chain preds |
| 946 | SUnit *PredSU = I->getSUnit(); |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 947 | unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers); |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 948 | if (PredSethiUllman > SethiUllmanNumber) { |
| 949 | SethiUllmanNumber = PredSethiUllman; |
| 950 | Extra = 0; |
Evan Cheng | 8182347 | 2009-02-12 08:59:45 +0000 | [diff] [blame] | 951 | } else if (PredSethiUllman == SethiUllmanNumber) |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 952 | ++Extra; |
| 953 | } |
| 954 | |
| 955 | SethiUllmanNumber += Extra; |
| 956 | |
| 957 | if (SethiUllmanNumber == 0) |
| 958 | SethiUllmanNumber = 1; |
| 959 | |
| 960 | return SethiUllmanNumber; |
| 961 | } |
| 962 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 963 | namespace { |
| 964 | template<class SF> |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 965 | class VISIBILITY_HIDDEN RegReductionPriorityQueue |
| 966 | : public SchedulingPriorityQueue { |
Dan Gohman | 3627e34 | 2008-06-21 18:35:25 +0000 | [diff] [blame] | 967 | PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue; |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 968 | unsigned currentQueueId; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 969 | |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 970 | protected: |
| 971 | // SUnits - The SUnits for the current graph. |
| 972 | std::vector<SUnit> *SUnits; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 973 | |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 974 | const TargetInstrInfo *TII; |
| 975 | const TargetRegisterInfo *TRI; |
| 976 | ScheduleDAGRRList *scheduleDAG; |
| 977 | |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 978 | // SethiUllmanNumbers - The SethiUllman number for each node. |
| 979 | std::vector<unsigned> SethiUllmanNumbers; |
| 980 | |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 981 | public: |
| 982 | RegReductionPriorityQueue(const TargetInstrInfo *tii, |
| 983 | const TargetRegisterInfo *tri) : |
| 984 | Queue(SF(this)), currentQueueId(0), |
| 985 | TII(tii), TRI(tri), scheduleDAG(NULL) {} |
| 986 | |
| 987 | void initNodes(std::vector<SUnit> &sunits) { |
| 988 | SUnits = &sunits; |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 989 | // Add pseudo dependency edges for two-address nodes. |
| 990 | AddPseudoTwoAddrDeps(); |
Dan Gohman | 002b44f | 2009-03-24 00:49:12 +0000 | [diff] [blame] | 991 | // Reroute edges to nodes with multiple uses. |
| 992 | PrescheduleNodesWithMultipleUses(); |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 993 | // Calculate node priorities. |
| 994 | CalculateSethiUllmanNumbers(); |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 995 | } |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 996 | |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 997 | void addNode(const SUnit *SU) { |
| 998 | unsigned SUSize = SethiUllmanNumbers.size(); |
| 999 | if (SUnits->size() > SUSize) |
| 1000 | SethiUllmanNumbers.resize(SUSize*2, 0); |
| 1001 | CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers); |
| 1002 | } |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 1003 | |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1004 | void updateNode(const SUnit *SU) { |
| 1005 | SethiUllmanNumbers[SU->NodeNum] = 0; |
| 1006 | CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers); |
| 1007 | } |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 1008 | |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1009 | void releaseState() { |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1010 | SUnits = 0; |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1011 | SethiUllmanNumbers.clear(); |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1012 | } |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1013 | |
| 1014 | unsigned getNodePriority(const SUnit *SU) const { |
| 1015 | assert(SU->NodeNum < SethiUllmanNumbers.size()); |
| 1016 | unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0; |
Dan Gohman | 25fd403 | 2009-01-07 22:30:55 +0000 | [diff] [blame] | 1017 | if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1018 | // CopyToReg should be close to its uses to facilitate coalescing and |
| 1019 | // avoid spilling. |
| 1020 | return 0; |
Dan Gohman | 25fd403 | 2009-01-07 22:30:55 +0000 | [diff] [blame] | 1021 | if (Opc == TargetInstrInfo::EXTRACT_SUBREG || |
Dan Gohman | 8af808a | 2009-04-16 20:57:10 +0000 | [diff] [blame^] | 1022 | Opc == TargetInstrInfo::SUBREG_TO_REG || |
Dan Gohman | 25fd403 | 2009-01-07 22:30:55 +0000 | [diff] [blame] | 1023 | Opc == TargetInstrInfo::INSERT_SUBREG) |
Dan Gohman | 8af808a | 2009-04-16 20:57:10 +0000 | [diff] [blame^] | 1024 | // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be |
| 1025 | // close to their uses to facilitate coalescing. |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1026 | return 0; |
Dan Gohman | c8db34c | 2009-02-11 21:29:39 +0000 | [diff] [blame] | 1027 | if (SU->NumSuccs == 0 && SU->NumPreds != 0) |
| 1028 | // If SU does not have a register use, i.e. it doesn't produce a value |
| 1029 | // that would be consumed (e.g. store), then it terminates a chain of |
| 1030 | // computation. Give it a large SethiUllman number so it will be |
| 1031 | // scheduled right before its predecessors that it doesn't lengthen |
| 1032 | // their live ranges. |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1033 | return 0xffff; |
Dan Gohman | c8db34c | 2009-02-11 21:29:39 +0000 | [diff] [blame] | 1034 | if (SU->NumPreds == 0 && SU->NumSuccs != 0) |
| 1035 | // If SU does not have a register def, schedule it close to its uses |
| 1036 | // because it does not lengthen any live ranges. |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1037 | return 0; |
Dan Gohman | 25fd403 | 2009-01-07 22:30:55 +0000 | [diff] [blame] | 1038 | return SethiUllmanNumbers[SU->NodeNum]; |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1039 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1040 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 1041 | unsigned size() const { return Queue.size(); } |
| 1042 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1043 | bool empty() const { return Queue.empty(); } |
| 1044 | |
| 1045 | void push(SUnit *U) { |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1046 | assert(!U->NodeQueueId && "Node in the queue already"); |
| 1047 | U->NodeQueueId = ++currentQueueId; |
Dan Gohman | 3627e34 | 2008-06-21 18:35:25 +0000 | [diff] [blame] | 1048 | Queue.push(U); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1049 | } |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1050 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1051 | void push_all(const std::vector<SUnit *> &Nodes) { |
| 1052 | for (unsigned i = 0, e = Nodes.size(); i != e; ++i) |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1053 | push(Nodes[i]); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1054 | } |
| 1055 | |
| 1056 | SUnit *pop() { |
Evan Cheng | 6b8e5a9 | 2006-05-30 18:05:39 +0000 | [diff] [blame] | 1057 | if (empty()) return NULL; |
Dan Gohman | 3627e34 | 2008-06-21 18:35:25 +0000 | [diff] [blame] | 1058 | SUnit *V = Queue.top(); |
| 1059 | Queue.pop(); |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1060 | V->NodeQueueId = 0; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1061 | return V; |
| 1062 | } |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1063 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 1064 | void remove(SUnit *SU) { |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1065 | assert(!Queue.empty() && "Queue is empty!"); |
Dan Gohman | 3627e34 | 2008-06-21 18:35:25 +0000 | [diff] [blame] | 1066 | assert(SU->NodeQueueId != 0 && "Not in queue!"); |
| 1067 | Queue.erase_one(SU); |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1068 | SU->NodeQueueId = 0; |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1069 | } |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1070 | |
| 1071 | void setScheduleDAG(ScheduleDAGRRList *scheduleDag) { |
| 1072 | scheduleDAG = scheduleDag; |
| 1073 | } |
| 1074 | |
| 1075 | protected: |
| 1076 | bool canClobber(const SUnit *SU, const SUnit *Op); |
| 1077 | void AddPseudoTwoAddrDeps(); |
Dan Gohman | 002b44f | 2009-03-24 00:49:12 +0000 | [diff] [blame] | 1078 | void PrescheduleNodesWithMultipleUses(); |
Evan Cheng | c8edc64 | 2007-01-08 23:55:53 +0000 | [diff] [blame] | 1079 | void CalculateSethiUllmanNumbers(); |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 1080 | }; |
| 1081 | |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1082 | typedef RegReductionPriorityQueue<bu_ls_rr_sort> |
| 1083 | BURegReductionPriorityQueue; |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 1084 | |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1085 | typedef RegReductionPriorityQueue<td_ls_rr_sort> |
| 1086 | TDRegReductionPriorityQueue; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1087 | } |
| 1088 | |
Evan Cheng | c6deb3d | 2007-03-14 22:43:40 +0000 | [diff] [blame] | 1089 | /// closestSucc - Returns the scheduled cycle of the successor which is |
Dan Gohman | b398fca | 2009-03-12 23:55:10 +0000 | [diff] [blame] | 1090 | /// closest to the current cycle. |
Evan Cheng | 61230d1 | 2007-03-13 23:25:11 +0000 | [diff] [blame] | 1091 | static unsigned closestSucc(const SUnit *SU) { |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1092 | unsigned MaxHeight = 0; |
Evan Cheng | 61230d1 | 2007-03-13 23:25:11 +0000 | [diff] [blame] | 1093 | for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
Evan Cheng | c6deb3d | 2007-03-14 22:43:40 +0000 | [diff] [blame] | 1094 | I != E; ++I) { |
Evan Cheng | f0e366a | 2009-02-10 08:30:11 +0000 | [diff] [blame] | 1095 | if (I->isCtrl()) continue; // ignore chain succs |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1096 | unsigned Height = I->getSUnit()->getHeight(); |
Evan Cheng | c6deb3d | 2007-03-14 22:43:40 +0000 | [diff] [blame] | 1097 | // If there are bunch of CopyToRegs stacked up, they should be considered |
| 1098 | // to be at the same position. |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 1099 | if (I->getSUnit()->getNode() && |
| 1100 | I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg) |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1101 | Height = closestSucc(I->getSUnit())+1; |
| 1102 | if (Height > MaxHeight) |
| 1103 | MaxHeight = Height; |
Evan Cheng | c6deb3d | 2007-03-14 22:43:40 +0000 | [diff] [blame] | 1104 | } |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1105 | return MaxHeight; |
Evan Cheng | 61230d1 | 2007-03-13 23:25:11 +0000 | [diff] [blame] | 1106 | } |
| 1107 | |
Evan Cheng | d6c0758 | 2007-12-20 02:22:36 +0000 | [diff] [blame] | 1108 | /// calcMaxScratches - Returns an cost estimate of the worse case requirement |
Evan Cheng | 8182347 | 2009-02-12 08:59:45 +0000 | [diff] [blame] | 1109 | /// for scratch registers, i.e. number of data dependencies. |
Evan Cheng | d6c0758 | 2007-12-20 02:22:36 +0000 | [diff] [blame] | 1110 | static unsigned calcMaxScratches(const SUnit *SU) { |
| 1111 | unsigned Scratches = 0; |
| 1112 | for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
Evan Cheng | f2b1471 | 2009-02-12 09:52:13 +0000 | [diff] [blame] | 1113 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 1114 | if (I->isCtrl()) continue; // ignore chain preds |
Evan Cheng | f2b1471 | 2009-02-12 09:52:13 +0000 | [diff] [blame] | 1115 | Scratches++; |
| 1116 | } |
Evan Cheng | d6c0758 | 2007-12-20 02:22:36 +0000 | [diff] [blame] | 1117 | return Scratches; |
| 1118 | } |
| 1119 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1120 | // Bottom up |
| 1121 | bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { |
Evan Cheng | c8edc64 | 2007-01-08 23:55:53 +0000 | [diff] [blame] | 1122 | unsigned LPriority = SPQ->getNodePriority(left); |
| 1123 | unsigned RPriority = SPQ->getNodePriority(right); |
Evan Cheng | 84d4a2b | 2008-03-01 00:39:47 +0000 | [diff] [blame] | 1124 | if (LPriority != RPriority) |
| 1125 | return LPriority > RPriority; |
| 1126 | |
| 1127 | // Try schedule def + use closer when Sethi-Ullman numbers are the same. |
| 1128 | // e.g. |
| 1129 | // t1 = op t2, c1 |
| 1130 | // t3 = op t4, c2 |
| 1131 | // |
| 1132 | // and the following instructions are both ready. |
| 1133 | // t2 = op c3 |
| 1134 | // t4 = op c4 |
| 1135 | // |
| 1136 | // Then schedule t2 = op first. |
| 1137 | // i.e. |
| 1138 | // t4 = op c4 |
| 1139 | // t2 = op c3 |
| 1140 | // t1 = op t2, c1 |
| 1141 | // t3 = op t4, c2 |
| 1142 | // |
| 1143 | // This creates more short live intervals. |
| 1144 | unsigned LDist = closestSucc(left); |
| 1145 | unsigned RDist = closestSucc(right); |
| 1146 | if (LDist != RDist) |
| 1147 | return LDist < RDist; |
| 1148 | |
Evan Cheng | 8182347 | 2009-02-12 08:59:45 +0000 | [diff] [blame] | 1149 | // How many registers becomes live when the node is scheduled. |
Evan Cheng | 84d4a2b | 2008-03-01 00:39:47 +0000 | [diff] [blame] | 1150 | unsigned LScratch = calcMaxScratches(left); |
| 1151 | unsigned RScratch = calcMaxScratches(right); |
| 1152 | if (LScratch != RScratch) |
| 1153 | return LScratch > RScratch; |
| 1154 | |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1155 | if (left->getHeight() != right->getHeight()) |
| 1156 | return left->getHeight() > right->getHeight(); |
Evan Cheng | 84d4a2b | 2008-03-01 00:39:47 +0000 | [diff] [blame] | 1157 | |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1158 | if (left->getDepth() != right->getDepth()) |
| 1159 | return left->getDepth() < right->getDepth(); |
Evan Cheng | 84d4a2b | 2008-03-01 00:39:47 +0000 | [diff] [blame] | 1160 | |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1161 | assert(left->NodeQueueId && right->NodeQueueId && |
| 1162 | "NodeQueueId cannot be zero"); |
| 1163 | return (left->NodeQueueId > right->NodeQueueId); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1164 | } |
| 1165 | |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1166 | template<class SF> |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 1167 | bool |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1168 | RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) { |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1169 | if (SU->isTwoAddress) { |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 1170 | unsigned Opc = SU->getNode()->getMachineOpcode(); |
Chris Lattner | 749c6f6 | 2008-01-07 07:27:27 +0000 | [diff] [blame] | 1171 | const TargetInstrDesc &TID = TII->get(Opc); |
Chris Lattner | 3db805e | 2008-01-07 06:47:00 +0000 | [diff] [blame] | 1172 | unsigned NumRes = TID.getNumDefs(); |
Dan Gohman | 3b66555 | 2008-02-15 20:50:13 +0000 | [diff] [blame] | 1173 | unsigned NumOps = TID.getNumOperands() - NumRes; |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1174 | for (unsigned i = 0; i != NumOps; ++i) { |
Chris Lattner | 3db805e | 2008-01-07 06:47:00 +0000 | [diff] [blame] | 1175 | if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) { |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 1176 | SDNode *DU = SU->getNode()->getOperand(i).getNode(); |
Dan Gohman | 94d7a5f | 2008-06-21 19:18:17 +0000 | [diff] [blame] | 1177 | if (DU->getNodeId() != -1 && |
| 1178 | Op->OrigNode == &(*SUnits)[DU->getNodeId()]) |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1179 | return true; |
| 1180 | } |
| 1181 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1182 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1183 | return false; |
| 1184 | } |
| 1185 | |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1186 | |
Evan Cheng | 22a5299 | 2007-09-28 22:32:30 +0000 | [diff] [blame] | 1187 | /// hasCopyToRegUse - Return true if SU has a value successor that is a |
| 1188 | /// CopyToReg node. |
Dan Gohman | 430b8a2 | 2008-08-05 14:45:15 +0000 | [diff] [blame] | 1189 | static bool hasCopyToRegUse(const SUnit *SU) { |
Evan Cheng | 22a5299 | 2007-09-28 22:32:30 +0000 | [diff] [blame] | 1190 | for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 1191 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 1192 | if (I->isCtrl()) continue; |
| 1193 | const SUnit *SuccSU = I->getSUnit(); |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 1194 | if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg) |
Evan Cheng | 22a5299 | 2007-09-28 22:32:30 +0000 | [diff] [blame] | 1195 | return true; |
| 1196 | } |
| 1197 | return false; |
| 1198 | } |
| 1199 | |
Evan Cheng | 180c210 | 2007-12-20 09:25:31 +0000 | [diff] [blame] | 1200 | /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's |
Dan Gohman | 2f1d310 | 2008-06-21 22:05:24 +0000 | [diff] [blame] | 1201 | /// physical register defs. |
Dan Gohman | 430b8a2 | 2008-08-05 14:45:15 +0000 | [diff] [blame] | 1202 | static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU, |
Evan Cheng | 180c210 | 2007-12-20 09:25:31 +0000 | [diff] [blame] | 1203 | const TargetInstrInfo *TII, |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 1204 | const TargetRegisterInfo *TRI) { |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 1205 | SDNode *N = SuccSU->getNode(); |
Dan Gohman | e8be6c6 | 2008-07-17 19:10:17 +0000 | [diff] [blame] | 1206 | unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs(); |
| 1207 | const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs(); |
Dan Gohman | 2f1d310 | 2008-06-21 22:05:24 +0000 | [diff] [blame] | 1208 | assert(ImpDefs && "Caller should check hasPhysRegDefs"); |
Dan Gohman | a5c8ae2 | 2009-03-23 16:23:01 +0000 | [diff] [blame] | 1209 | for (const SDNode *SUNode = SU->getNode(); SUNode; |
| 1210 | SUNode = SUNode->getFlaggedNode()) { |
| 1211 | if (!SUNode->isMachineOpcode()) |
Evan Cheng | 180c210 | 2007-12-20 09:25:31 +0000 | [diff] [blame] | 1212 | continue; |
Dan Gohman | a5c8ae2 | 2009-03-23 16:23:01 +0000 | [diff] [blame] | 1213 | const unsigned *SUImpDefs = |
| 1214 | TII->get(SUNode->getMachineOpcode()).getImplicitDefs(); |
| 1215 | if (!SUImpDefs) |
| 1216 | return false; |
| 1217 | for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) { |
| 1218 | MVT VT = N->getValueType(i); |
| 1219 | if (VT == MVT::Flag || VT == MVT::Other) |
| 1220 | continue; |
| 1221 | if (!N->hasAnyUseOfValue(i)) |
| 1222 | continue; |
| 1223 | unsigned Reg = ImpDefs[i - NumDefs]; |
| 1224 | for (;*SUImpDefs; ++SUImpDefs) { |
| 1225 | unsigned SUReg = *SUImpDefs; |
| 1226 | if (TRI->regsOverlap(Reg, SUReg)) |
| 1227 | return true; |
| 1228 | } |
Evan Cheng | 180c210 | 2007-12-20 09:25:31 +0000 | [diff] [blame] | 1229 | } |
| 1230 | } |
| 1231 | return false; |
| 1232 | } |
| 1233 | |
Dan Gohman | 002b44f | 2009-03-24 00:49:12 +0000 | [diff] [blame] | 1234 | /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses |
| 1235 | /// are not handled well by the general register pressure reduction |
| 1236 | /// heuristics. When presented with code like this: |
| 1237 | /// |
| 1238 | /// N |
| 1239 | /// / | |
| 1240 | /// / | |
| 1241 | /// U store |
| 1242 | /// | |
| 1243 | /// ... |
| 1244 | /// |
| 1245 | /// the heuristics tend to push the store up, but since the |
| 1246 | /// operand of the store has another use (U), this would increase |
| 1247 | /// the length of that other use (the U->N edge). |
| 1248 | /// |
| 1249 | /// This function transforms code like the above to route U's |
| 1250 | /// dependence through the store when possible, like this: |
| 1251 | /// |
| 1252 | /// N |
| 1253 | /// || |
| 1254 | /// || |
| 1255 | /// store |
| 1256 | /// | |
| 1257 | /// U |
| 1258 | /// | |
| 1259 | /// ... |
| 1260 | /// |
| 1261 | /// This results in the store being scheduled immediately |
| 1262 | /// after N, which shortens the U->N live range, reducing |
| 1263 | /// register pressure. |
| 1264 | /// |
| 1265 | template<class SF> |
| 1266 | void RegReductionPriorityQueue<SF>::PrescheduleNodesWithMultipleUses() { |
| 1267 | // Visit all the nodes in topological order, working top-down. |
| 1268 | for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { |
| 1269 | SUnit *SU = &(*SUnits)[i]; |
| 1270 | // For now, only look at nodes with no data successors, such as stores. |
| 1271 | // These are especially important, due to the heuristics in |
| 1272 | // getNodePriority for nodes with no data successors. |
| 1273 | if (SU->NumSuccs != 0) |
| 1274 | continue; |
| 1275 | // For now, only look at nodes with exactly one data predecessor. |
| 1276 | if (SU->NumPreds != 1) |
| 1277 | continue; |
| 1278 | // Avoid prescheduling copies to virtual registers, which don't behave |
| 1279 | // like other nodes from the perspective of scheduling heuristics. |
| 1280 | if (SDNode *N = SU->getNode()) |
| 1281 | if (N->getOpcode() == ISD::CopyToReg && |
| 1282 | TargetRegisterInfo::isVirtualRegister |
| 1283 | (cast<RegisterSDNode>(N->getOperand(1))->getReg())) |
| 1284 | continue; |
| 1285 | |
| 1286 | // Locate the single data predecessor. |
| 1287 | SUnit *PredSU = 0; |
| 1288 | for (SUnit::const_pred_iterator II = SU->Preds.begin(), |
| 1289 | EE = SU->Preds.end(); II != EE; ++II) |
| 1290 | if (!II->isCtrl()) { |
| 1291 | PredSU = II->getSUnit(); |
| 1292 | break; |
| 1293 | } |
| 1294 | assert(PredSU); |
| 1295 | |
| 1296 | // Don't rewrite edges that carry physregs, because that requires additional |
| 1297 | // support infrastructure. |
| 1298 | if (PredSU->hasPhysRegDefs) |
| 1299 | continue; |
| 1300 | // Short-circuit the case where SU is PredSU's only data successor. |
| 1301 | if (PredSU->NumSuccs == 1) |
| 1302 | continue; |
| 1303 | // Avoid prescheduling to copies from virtual registers, which don't behave |
| 1304 | // like other nodes from the perspective of scheduling // heuristics. |
| 1305 | if (SDNode *N = SU->getNode()) |
| 1306 | if (N->getOpcode() == ISD::CopyFromReg && |
| 1307 | TargetRegisterInfo::isVirtualRegister |
| 1308 | (cast<RegisterSDNode>(N->getOperand(1))->getReg())) |
| 1309 | continue; |
| 1310 | |
| 1311 | // Perform checks on the successors of PredSU. |
| 1312 | for (SUnit::const_succ_iterator II = PredSU->Succs.begin(), |
| 1313 | EE = PredSU->Succs.end(); II != EE; ++II) { |
| 1314 | SUnit *PredSuccSU = II->getSUnit(); |
| 1315 | if (PredSuccSU == SU) continue; |
| 1316 | // If PredSU has another successor with no data successors, for |
| 1317 | // now don't attempt to choose either over the other. |
| 1318 | if (PredSuccSU->NumSuccs == 0) |
| 1319 | goto outer_loop_continue; |
| 1320 | // Don't break physical register dependencies. |
| 1321 | if (SU->hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs) |
| 1322 | if (canClobberPhysRegDefs(PredSuccSU, SU, TII, TRI)) |
| 1323 | goto outer_loop_continue; |
| 1324 | // Don't introduce graph cycles. |
| 1325 | if (scheduleDAG->IsReachable(SU, PredSuccSU)) |
| 1326 | goto outer_loop_continue; |
| 1327 | } |
| 1328 | |
| 1329 | // Ok, the transformation is safe and the heuristics suggest it is |
| 1330 | // profitable. Update the graph. |
| 1331 | DOUT << "Prescheduling SU # " << SU->NodeNum |
| 1332 | << " next to PredSU # " << PredSU->NodeNum |
| 1333 | << " to guide scheduling in the presence of multiple uses\n"; |
| 1334 | for (unsigned i = 0; i != PredSU->Succs.size(); ++i) { |
| 1335 | SDep Edge = PredSU->Succs[i]; |
| 1336 | assert(!Edge.isAssignedRegDep()); |
| 1337 | SUnit *SuccSU = Edge.getSUnit(); |
| 1338 | if (SuccSU != SU) { |
| 1339 | Edge.setSUnit(PredSU); |
| 1340 | scheduleDAG->RemovePred(SuccSU, Edge); |
| 1341 | scheduleDAG->AddPred(SU, Edge); |
| 1342 | Edge.setSUnit(SU); |
| 1343 | scheduleDAG->AddPred(SuccSU, Edge); |
| 1344 | --i; |
| 1345 | } |
| 1346 | } |
| 1347 | outer_loop_continue:; |
| 1348 | } |
| 1349 | } |
| 1350 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1351 | /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses |
| 1352 | /// it as a def&use operand. Add a pseudo control edge from it to the other |
| 1353 | /// node (if it won't create a cycle) so the two-address one will be scheduled |
Evan Cheng | 22a5299 | 2007-09-28 22:32:30 +0000 | [diff] [blame] | 1354 | /// first (lower in the schedule). If both nodes are two-address, favor the |
| 1355 | /// one that has a CopyToReg use (more likely to be a loop induction update). |
| 1356 | /// If both are two-address, but one is commutable while the other is not |
| 1357 | /// commutable, favor the one that's not commutable. |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1358 | template<class SF> |
| 1359 | void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1360 | for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { |
Dan Gohman | 430b8a2 | 2008-08-05 14:45:15 +0000 | [diff] [blame] | 1361 | SUnit *SU = &(*SUnits)[i]; |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1362 | if (!SU->isTwoAddress) |
| 1363 | continue; |
| 1364 | |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 1365 | SDNode *Node = SU->getNode(); |
Dan Gohman | d23e0f8 | 2008-11-13 23:24:17 +0000 | [diff] [blame] | 1366 | if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode()) |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1367 | continue; |
| 1368 | |
Dan Gohman | e8be6c6 | 2008-07-17 19:10:17 +0000 | [diff] [blame] | 1369 | unsigned Opc = Node->getMachineOpcode(); |
Chris Lattner | 749c6f6 | 2008-01-07 07:27:27 +0000 | [diff] [blame] | 1370 | const TargetInstrDesc &TID = TII->get(Opc); |
Chris Lattner | 3db805e | 2008-01-07 06:47:00 +0000 | [diff] [blame] | 1371 | unsigned NumRes = TID.getNumDefs(); |
Dan Gohman | 3b66555 | 2008-02-15 20:50:13 +0000 | [diff] [blame] | 1372 | unsigned NumOps = TID.getNumOperands() - NumRes; |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1373 | for (unsigned j = 0; j != NumOps; ++j) { |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1374 | if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1) |
| 1375 | continue; |
| 1376 | SDNode *DU = SU->getNode()->getOperand(j).getNode(); |
| 1377 | if (DU->getNodeId() == -1) |
| 1378 | continue; |
| 1379 | const SUnit *DUSU = &(*SUnits)[DU->getNodeId()]; |
| 1380 | if (!DUSU) continue; |
| 1381 | for (SUnit::const_succ_iterator I = DUSU->Succs.begin(), |
| 1382 | E = DUSU->Succs.end(); I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 1383 | if (I->isCtrl()) continue; |
| 1384 | SUnit *SuccSU = I->getSUnit(); |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1385 | if (SuccSU == SU) |
Evan Cheng | 7da8f39 | 2007-11-09 01:27:11 +0000 | [diff] [blame] | 1386 | continue; |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1387 | // Be conservative. Ignore if nodes aren't at roughly the same |
| 1388 | // depth and height. |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1389 | if (SuccSU->getHeight() < SU->getHeight() && |
| 1390 | (SU->getHeight() - SuccSU->getHeight()) > 1) |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1391 | continue; |
| 1392 | if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode()) |
| 1393 | continue; |
| 1394 | // Don't constrain nodes with physical register defs if the |
| 1395 | // predecessor can clobber them. |
Dan Gohman | 8f4aa33 | 2009-03-24 00:50:07 +0000 | [diff] [blame] | 1396 | if (SuccSU->hasPhysRegDefs && SU->hasPhysRegClobbers) { |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1397 | if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI)) |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 1398 | continue; |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1399 | } |
Dan Gohman | 8af808a | 2009-04-16 20:57:10 +0000 | [diff] [blame^] | 1400 | // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG; |
| 1401 | // these may be coalesced away. We want them close to their uses. |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1402 | unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode(); |
| 1403 | if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG || |
Dan Gohman | 8af808a | 2009-04-16 20:57:10 +0000 | [diff] [blame^] | 1404 | SuccOpc == TargetInstrInfo::INSERT_SUBREG || |
| 1405 | SuccOpc == TargetInstrInfo::SUBREG_TO_REG) |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1406 | continue; |
| 1407 | if ((!canClobber(SuccSU, DUSU) || |
| 1408 | (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) || |
| 1409 | (!SU->isCommutable && SuccSU->isCommutable)) && |
| 1410 | !scheduleDAG->IsReachable(SuccSU, SU)) { |
Dan Gohman | b29ffc8 | 2008-12-04 02:14:57 +0000 | [diff] [blame] | 1411 | DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum |
Dan Gohman | c2f9062 | 2008-11-19 02:00:32 +0000 | [diff] [blame] | 1412 | << " to SU #" << SuccSU->NodeNum << "\n"; |
Dan Gohman | fd2163b | 2009-01-06 01:19:04 +0000 | [diff] [blame] | 1413 | scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0, |
Dan Gohman | ce0d4b7 | 2009-01-06 01:28:56 +0000 | [diff] [blame] | 1414 | /*Reg=*/0, /*isNormalMemory=*/false, |
| 1415 | /*isMustAlias=*/false, |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 1416 | /*isArtificial=*/true)); |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 1417 | } |
| 1418 | } |
| 1419 | } |
| 1420 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1421 | } |
| 1422 | |
Evan Cheng | c8edc64 | 2007-01-08 23:55:53 +0000 | [diff] [blame] | 1423 | /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all |
| 1424 | /// scheduling units. |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1425 | template<class SF> |
| 1426 | void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1427 | SethiUllmanNumbers.assign(SUnits->size(), 0); |
| 1428 | |
| 1429 | for (unsigned i = 0, e = SUnits->size(); i != e; ++i) |
Dan Gohman | 117f3e9 | 2008-11-20 03:30:37 +0000 | [diff] [blame] | 1430 | CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers); |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 1431 | } |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1432 | |
Roman Levenstein | d7d3ea0 | 2008-03-27 09:44:37 +0000 | [diff] [blame] | 1433 | /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled |
Roman Levenstein | 95d4184 | 2008-03-27 09:14:57 +0000 | [diff] [blame] | 1434 | /// predecessors of the successors of the SUnit SU. Stop when the provided |
| 1435 | /// limit is exceeded. |
Roman Levenstein | 95d4184 | 2008-03-27 09:14:57 +0000 | [diff] [blame] | 1436 | static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU, |
| 1437 | unsigned Limit) { |
| 1438 | unsigned Sum = 0; |
| 1439 | for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 1440 | I != E; ++I) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 1441 | const SUnit *SuccSU = I->getSUnit(); |
Roman Levenstein | 95d4184 | 2008-03-27 09:14:57 +0000 | [diff] [blame] | 1442 | for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(), |
| 1443 | EE = SuccSU->Preds.end(); II != EE; ++II) { |
Dan Gohman | 54e4c36 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 1444 | SUnit *PredSU = II->getSUnit(); |
Evan Cheng | fd5da6c | 2008-03-29 18:34:22 +0000 | [diff] [blame] | 1445 | if (!PredSU->isScheduled) |
| 1446 | if (++Sum > Limit) |
| 1447 | return Sum; |
Roman Levenstein | 95d4184 | 2008-03-27 09:14:57 +0000 | [diff] [blame] | 1448 | } |
| 1449 | } |
| 1450 | return Sum; |
| 1451 | } |
| 1452 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1453 | |
| 1454 | // Top down |
| 1455 | bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { |
Evan Cheng | c8edc64 | 2007-01-08 23:55:53 +0000 | [diff] [blame] | 1456 | unsigned LPriority = SPQ->getNodePriority(left); |
| 1457 | unsigned RPriority = SPQ->getNodePriority(right); |
Dan Gohman | 550f5af | 2008-11-13 21:36:12 +0000 | [diff] [blame] | 1458 | bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode(); |
| 1459 | bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode(); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1460 | bool LIsFloater = LIsTarget && left->NumPreds == 0; |
| 1461 | bool RIsFloater = RIsTarget && right->NumPreds == 0; |
Roman Levenstein | 95d4184 | 2008-03-27 09:14:57 +0000 | [diff] [blame] | 1462 | unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0; |
| 1463 | unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1464 | |
| 1465 | if (left->NumSuccs == 0 && right->NumSuccs != 0) |
| 1466 | return false; |
| 1467 | else if (left->NumSuccs != 0 && right->NumSuccs == 0) |
| 1468 | return true; |
| 1469 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1470 | if (LIsFloater) |
| 1471 | LBonus -= 2; |
| 1472 | if (RIsFloater) |
| 1473 | RBonus -= 2; |
| 1474 | if (left->NumSuccs == 1) |
| 1475 | LBonus += 2; |
| 1476 | if (right->NumSuccs == 1) |
| 1477 | RBonus += 2; |
| 1478 | |
Evan Cheng | 84d4a2b | 2008-03-01 00:39:47 +0000 | [diff] [blame] | 1479 | if (LPriority+LBonus != RPriority+RBonus) |
| 1480 | return LPriority+LBonus < RPriority+RBonus; |
Anton Korobeynikov | 4c71dfe | 2008-02-20 11:10:28 +0000 | [diff] [blame] | 1481 | |
Dan Gohman | 3f23744 | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 1482 | if (left->getDepth() != right->getDepth()) |
| 1483 | return left->getDepth() < right->getDepth(); |
Evan Cheng | 84d4a2b | 2008-03-01 00:39:47 +0000 | [diff] [blame] | 1484 | |
| 1485 | if (left->NumSuccsLeft != right->NumSuccsLeft) |
| 1486 | return left->NumSuccsLeft > right->NumSuccsLeft; |
| 1487 | |
Roman Levenstein | a0201d5 | 2008-04-29 09:07:59 +0000 | [diff] [blame] | 1488 | assert(left->NodeQueueId && right->NodeQueueId && |
| 1489 | "NodeQueueId cannot be zero"); |
| 1490 | return (left->NodeQueueId > right->NodeQueueId); |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1491 | } |
| 1492 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1493 | //===----------------------------------------------------------------------===// |
| 1494 | // Public Constructor Functions |
| 1495 | //===----------------------------------------------------------------------===// |
| 1496 | |
Dan Gohman | 47ac0f0 | 2009-02-11 04:27:20 +0000 | [diff] [blame] | 1497 | llvm::ScheduleDAGSDNodes * |
| 1498 | llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, bool) { |
Dan Gohman | 79ce276 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 1499 | const TargetMachine &TM = IS->TM; |
| 1500 | const TargetInstrInfo *TII = TM.getInstrInfo(); |
| 1501 | const TargetRegisterInfo *TRI = TM.getRegisterInfo(); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 1502 | |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 1503 | BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI); |
Roman Levenstein | e513ba4 | 2008-03-26 09:18:09 +0000 | [diff] [blame] | 1504 | |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 1505 | ScheduleDAGRRList *SD = |
Dan Gohman | 79ce276 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 1506 | new ScheduleDAGRRList(*IS->MF, true, PQ); |
Evan Cheng | c6be777 | 2008-07-02 09:23:51 +0000 | [diff] [blame] | 1507 | PQ->setScheduleDAG(SD); |
| 1508 | return SD; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1509 | } |
| 1510 | |
Dan Gohman | 47ac0f0 | 2009-02-11 04:27:20 +0000 | [diff] [blame] | 1511 | llvm::ScheduleDAGSDNodes * |
| 1512 | llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, bool) { |
Dan Gohman | 79ce276 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 1513 | const TargetMachine &TM = IS->TM; |
| 1514 | const TargetInstrInfo *TII = TM.getInstrInfo(); |
| 1515 | const TargetRegisterInfo *TRI = TM.getRegisterInfo(); |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1516 | |
| 1517 | TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI); |
| 1518 | |
Dan Gohman | 79ce276 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 1519 | ScheduleDAGRRList *SD = |
| 1520 | new ScheduleDAGRRList(*IS->MF, false, PQ); |
Dan Gohman | 6be2ee4 | 2008-11-20 02:45:51 +0000 | [diff] [blame] | 1521 | PQ->setScheduleDAG(SD); |
| 1522 | return SD; |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 1523 | } |