1 /* 2 * Copyright (c) 2023 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef MAPLEBE_INCLUDE_CG_LIST_SCHEDULER_H 17 #define MAPLEBE_INCLUDE_CG_LIST_SCHEDULER_H 18 19 #include <utility> 20 #include "cg.h" 21 #include "deps.h" 22 #include "cg_cdg.h" 23 #include "schedule_heuristic.h" 24 25 namespace maplebe { 26 #define LIST_SCHEDULE_DUMP CG_DEBUG_FUNC(cgFunc) 27 using SchedRankFunctor = bool (*)(const DepNode *node1, const DepNode *node2); 28 29 constexpr uint32 kClinitAdvanceCycle = 12; 30 constexpr uint32 kAdrpLdrAdvanceCycle = 4; 31 constexpr uint32 kClinitTailAdvanceCycle = 6; 32 33 class CommonScheduleInfo { 34 public: CommonScheduleInfo(MemPool & memPool)35 explicit CommonScheduleInfo(MemPool &memPool) 36 : csiAlloc(&memPool), candidates(csiAlloc.Adapter()), schedResults(csiAlloc.Adapter()) 37 { 38 } 39 ~CommonScheduleInfo() = default; 40 GetCandidates()41 MapleVector<DepNode *> &GetCandidates() 42 { 43 return candidates; 44 } AddCandidates(DepNode * depNode)45 void AddCandidates(DepNode *depNode) 46 { 47 (void)candidates.emplace_back(depNode); 48 } EraseNodeFromCandidates(const DepNode * depNode)49 void EraseNodeFromCandidates(const DepNode *depNode) 50 { 51 for (auto iter = candidates.begin(); iter != candidates.end(); ++iter) { 52 if (*iter == depNode) { 53 (void)candidates.erase(iter); 54 return; 55 } 56 } 57 } EraseIterFromCandidates(MapleVector<DepNode * >::iterator depIter)58 MapleVector<DepNode *>::iterator EraseIterFromCandidates(MapleVector<DepNode *>::iterator depIter) 59 { 60 return candidates.erase(depIter); 61 } GetSchedResults()62 MapleVector<DepNode *> &GetSchedResults() 63 { 64 return schedResults; 65 } AddSchedResults(DepNode * depNode)66 void AddSchedResults(DepNode *depNode) 67 { 68 (void)schedResults.emplace_back(depNode); 69 } GetSchedResultsSize()70 std::size_t GetSchedResultsSize() const 71 { 72 return schedResults.size(); 73 } 74 75 private: 76 MapleAllocator csiAlloc; 77 // Candidate instructions list of current BB, 78 // by control flow sequence 79 MapleVector<DepNode *> candidates; 80 // Scheduled results list of current BB 81 // for global-scheduler, it stored only to the last depNode of current BB 82 MapleVector<DepNode *> schedResults; 83 }; 84 85 class ListScheduler { 86 public: 87 ListScheduler(MemPool &memPool, CGFunc &func, SchedRankFunctor rankFunc, bool delayHeu = true, 88 std::string pName = "") listSchedMp(memPool)89 : listSchedMp(memPool), 90 listSchedAlloc(&memPool), 91 cgFunc(func), 92 rankScheduleInsns(rankFunc), 93 doDelayHeuristics(delayHeu), 94 phaseName(std::move(pName)), 95 waitingQueue(listSchedAlloc.Adapter()), 96 readyList(listSchedAlloc.Adapter()) 97 { 98 } 99 ListScheduler(MemPool &memPool, CGFunc &func, bool delayHeu = true, std::string pName = "") listSchedMp(memPool)100 : listSchedMp(memPool), 101 listSchedAlloc(&memPool), 102 cgFunc(func), 103 doDelayHeuristics(delayHeu), 104 phaseName(std::move(pName)), 105 waitingQueue(listSchedAlloc.Adapter()), 106 readyList(listSchedAlloc.Adapter()) 107 { 108 } ~ListScheduler()109 virtual ~ListScheduler() 110 { 111 mad = nullptr; 112 } 113 PhaseName()114 std::string PhaseName() const 115 { 116 if (phaseName.empty()) { 117 return "listscheduler"; 118 } else { 119 return phaseName; 120 } 121 } 122 123 // The entry of list-scheduler 124 // cdgNode: current scheduled BB 125 void DoListScheduling(); 126 void ComputeDelayPriority(); 127 // Compute the earliest start cycle, update maxEStart 128 void ComputeEStart(uint32 cycle); 129 // Compute the latest start cycle 130 void ComputeLStart(); 131 // Calculate the most used unitKind index 132 void CalculateMostUsedUnitKindCount(); 133 SetCommonSchedInfo(CommonScheduleInfo & csi)134 void SetCommonSchedInfo(CommonScheduleInfo &csi) 135 { 136 commonSchedInfo = &csi; 137 } SetCDGRegion(CDGRegion & cdgRegion)138 void SetCDGRegion(CDGRegion &cdgRegion) 139 { 140 region = &cdgRegion; 141 } SetCDGNode(CDGNode & cdgNode)142 void SetCDGNode(CDGNode &cdgNode) 143 { 144 curCDGNode = &cdgNode; 145 } GetCurrCycle()146 uint32 GetCurrCycle() const 147 { 148 return currCycle; 149 } GetMaxLStart()150 uint32 GetMaxLStart() const 151 { 152 return maxLStart; 153 } GetMaxDelay()154 uint32 GetMaxDelay() const 155 { 156 return maxDelay; 157 } SetUnitTest(bool flag)158 void SetUnitTest(bool flag) 159 { 160 isUnitTest = flag; 161 } 162 163 protected: 164 void Init(); 165 void CandidateToWaitingQueue(); 166 void WaitingQueueToReadyList(); 167 void InitInfoBeforeCompEStart(uint32 cycle, std::vector<DepNode *> &traversalList); 168 void InitInfoBeforeCompLStart(std::vector<DepNode *> &traversalList); 169 void UpdateInfoBeforeSelectNode(); 170 void SortReadyList(); 171 void UpdateEStart(DepNode &schedNode); 172 void UpdateInfoAfterSelectNode(DepNode &schedNode); 173 void UpdateNodesInReadyList(); 174 void UpdateAdvanceCycle(const DepNode &schedNode); 175 void CountUnitKind(const DepNode &depNode, std::array<uint32, kUnitKindLast> &unitKindCount) const; 176 void DumpWaitingQueue() const; 177 void DumpReadyList() const; 178 void DumpScheduledResult() const; 179 void DumpDelay() const; 180 void DumpEStartLStartOfAllNodes(); 181 void DumpDepNodeInfo(const BB &curBB, MapleVector<DepNode *> &nodes, const std::string state) const; 182 void DumpReservation(const DepNode &depNode) const; 183 EraseNodeFromReadyList(const DepNode * depNode)184 void EraseNodeFromReadyList(const DepNode *depNode) 185 { 186 for (auto iter = readyList.begin(); iter != readyList.end(); ++iter) { 187 if (*iter == depNode) { 188 (void)readyList.erase(iter); 189 return; 190 } 191 } 192 } EraseIterFromReadyList(MapleVector<DepNode * >::iterator depIter)193 MapleVector<DepNode *>::iterator EraseIterFromReadyList(MapleVector<DepNode *>::iterator depIter) 194 { 195 return readyList.erase(depIter); 196 } 197 EraseIterFromWaitingQueue(MapleVector<DepNode * >::iterator depIter)198 MapleVector<DepNode *>::iterator EraseIterFromWaitingQueue(MapleVector<DepNode *>::iterator depIter) 199 { 200 return waitingQueue.erase(depIter); 201 } 202 203 // Default rank readyList function by delay heuristic, 204 // which uses delay as algorithm of computing priority DelayRankScheduleInsns(const DepNode * node1,const DepNode * node2)205 static bool DelayRankScheduleInsns(const DepNode *node1, const DepNode *node2) 206 { 207 // p as an acronym for priority 208 CompareDelay compareDelay; 209 int p1 = compareDelay(*node1, *node2); 210 if (p1 != 0) { 211 return p1 > 0; 212 } 213 214 CompareDataCache compareDataCache; 215 int p2 = compareDataCache(*node1, *node2); 216 if (p2 != 0) { 217 return p2 > 0; 218 } 219 220 CompareClassOfLastScheduledNode compareClassOfLSN(lastSchedInsnId); 221 int p3 = compareClassOfLSN(*node1, *node2); 222 if (p3 != 0) { 223 return p3 > 0; 224 } 225 226 CompareSuccNodeSize compareSuccNodeSize; 227 int p4 = compareSuccNodeSize(*node1, *node2); 228 if (p4 != 0) { 229 return p4 > 0; 230 } 231 232 CompareInsnID compareInsnId; 233 int p6 = compareInsnId(*node1, *node2); 234 if (p6 != 0) { 235 return p6 > 0; 236 } 237 238 // default 239 return true; 240 } 241 242 static bool CriticalPathRankScheduleInsns(const DepNode *node1, const DepNode *node2); 243 244 MemPool &listSchedMp; 245 MapleAllocator listSchedAlloc; 246 CGFunc &cgFunc; 247 MAD *mad = nullptr; // CPU resources 248 CDGRegion *region = nullptr; // the current region 249 CDGNode *curCDGNode = nullptr; // the current scheduled BB 250 CommonScheduleInfo *commonSchedInfo = nullptr; // common scheduling info that prepared by other scheduler 251 // The function ptr that computes instruction priority based on heuristic rules, 252 // list-scheduler provides default implementations and supports customization by other schedulers 253 SchedRankFunctor rankScheduleInsns = nullptr; 254 bool doDelayHeuristics = true; // true: compute delay; false: compute eStart & lStart 255 std::string phaseName; // for dumping log 256 // A node is moved from [candidates] to [waitingQueue] when it's all data dependency are met 257 MapleVector<DepNode *> waitingQueue; 258 // A node is moved from [waitingQueue] to [readyList] when resources required by it are free and 259 // estart-cycle <= curr-cycle 260 MapleVector<DepNode *> readyList; 261 uint32 currCycle = 0; // Simulates the CPU clock during scheduling 262 uint32 advancedCycle = 0; // Using after an instruction is scheduled, record its execution cycles 263 uint32 maxEStart = 0; // Update when the eStart of depNodes are recalculated 264 uint32 maxLStart = 0; // Ideal total cycles that is equivalent to critical path length 265 uint32 maxDelay = 0; // Ideal total cycles that is equivalent to max delay 266 uint32 scheduledNodeNum = 0; // The number of instructions that are scheduled 267 static uint32 lastSchedInsnId; // Last scheduled insnId, for heuristic function 268 DepNode *lastSchedNode = nullptr; // Last scheduled node 269 bool isUnitTest = false; 270 }; 271 } // namespace maplebe 272 273 #endif // MAPLEBE_INCLUDE_CG_LIST_SCHEDULER_H 274