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_LOOP_H 17 #define MAPLEBE_INCLUDE_CG_LOOP_H 18 19 #include "cg_phase.h" 20 #include "cgbb.h" 21 #include "insn.h" 22 #include "maple_phase.h" 23 24 namespace maplebe { 25 class LoopHierarchy { 26 public: 27 struct HeadIDCmp { operatorHeadIDCmp28 bool operator()(const LoopHierarchy *loopHierarchy1, const LoopHierarchy *loopHierarchy2) const 29 { 30 CHECK_NULL_FATAL(loopHierarchy1); 31 CHECK_NULL_FATAL(loopHierarchy2); 32 return (loopHierarchy1->GetHeader()->GetId() < loopHierarchy2->GetHeader()->GetId()); 33 } 34 }; 35 LoopHierarchy(MemPool & memPool)36 explicit LoopHierarchy(MemPool &memPool) 37 : loopMemPool(&memPool), 38 otherLoopEntries(loopMemPool.Adapter()), 39 loopMembers(loopMemPool.Adapter()), 40 backedge(loopMemPool.Adapter()), 41 exits(loopMemPool.Adapter()), 42 innerLoops(loopMemPool.Adapter()) 43 { 44 } 45 46 virtual ~LoopHierarchy() = default; 47 GetHeader()48 BB *GetHeader() const 49 { 50 return header; 51 } GetLoopMembers()52 const MapleSet<BB *, BBIdCmp> &GetLoopMembers() const 53 { 54 return loopMembers; 55 } GetBackedge()56 const MapleSet<BB *, BBIdCmp> &GetBackedge() const 57 { 58 return backedge; 59 } GetBackedgeNonConst()60 MapleSet<BB *, BBIdCmp> &GetBackedgeNonConst() 61 { 62 return backedge; 63 } GetExits()64 const MapleSet<BB *, BBIdCmp> &GetExits() const 65 { 66 return exits; 67 } GetInnerLoops()68 const MapleSet<LoopHierarchy *, HeadIDCmp> &GetInnerLoops() const 69 { 70 return innerLoops; 71 } GetOuterLoop()72 const LoopHierarchy *GetOuterLoop() const 73 { 74 return outerLoop; 75 } GetPrev()76 LoopHierarchy *GetPrev() 77 { 78 return prev; 79 } GetNext()80 LoopHierarchy *GetNext() 81 { 82 return next; 83 } 84 EraseLoopMembers(MapleSet<BB *,BBIdCmp>::iterator it)85 MapleSet<BB *, BBIdCmp>::iterator EraseLoopMembers(MapleSet<BB *, BBIdCmp>::iterator it) 86 { 87 return loopMembers.erase(it); 88 } InsertLoopMembers(BB & bb)89 void InsertLoopMembers(BB &bb) 90 { 91 (void)loopMembers.insert(&bb); 92 } InsertBackedge(BB & bb)93 void InsertBackedge(BB &bb) 94 { 95 (void)backedge.insert(&bb); 96 } InsertExit(BB & bb)97 void InsertExit(BB &bb) 98 { 99 (void)exits.insert(&bb); 100 } InsertInnerLoops(LoopHierarchy & loop)101 void InsertInnerLoops(LoopHierarchy &loop) 102 { 103 (void)innerLoops.insert(&loop); 104 } SetHeader(BB & bb)105 void SetHeader(BB &bb) 106 { 107 header = &bb; 108 } SetOuterLoop(LoopHierarchy & loop)109 void SetOuterLoop(LoopHierarchy &loop) 110 { 111 outerLoop = &loop; 112 } SetPrev(LoopHierarchy * loop)113 void SetPrev(LoopHierarchy *loop) 114 { 115 prev = loop; 116 } SetNext(LoopHierarchy * loop)117 void SetNext(LoopHierarchy *loop) 118 { 119 next = loop; 120 } 121 void PrintLoops(const std::string &name) const; 122 123 protected: 124 LoopHierarchy *prev = nullptr; 125 LoopHierarchy *next = nullptr; 126 127 private: 128 MapleAllocator loopMemPool; 129 BB *header = nullptr; 130 131 public: 132 MapleSet<BB *, BBIdCmp> otherLoopEntries; 133 MapleSet<BB *, BBIdCmp> loopMembers; 134 MapleSet<BB *, BBIdCmp> backedge; 135 MapleSet<BB *, BBIdCmp> exits; 136 MapleSet<LoopHierarchy *, HeadIDCmp> innerLoops; 137 LoopHierarchy *outerLoop = nullptr; 138 }; 139 140 class LoopFinder : public AnalysisResult { 141 public: LoopFinder(CGFunc & func,MemPool & mem)142 LoopFinder(CGFunc &func, MemPool &mem) 143 : AnalysisResult(&mem), 144 cgFunc(&func), 145 memPool(&mem), 146 loopMemPool(memPool), 147 visitedBBs(loopMemPool.Adapter()), 148 sortedBBs(loopMemPool.Adapter()), 149 dfsBBs(loopMemPool.Adapter()), 150 onPathBBs(loopMemPool.Adapter()), 151 recurseVisited(loopMemPool.Adapter()) 152 { 153 } 154 155 ~LoopFinder() override = default; 156 157 void formLoop(BB *headBB, BB *backBB); 158 void seekBackEdge(BB *bb, MapleList<BB *> succs); 159 void seekCycles(); 160 void markExtraEntryAndEncl(); 161 bool HasSameHeader(const LoopHierarchy *lp1, const LoopHierarchy *lp2); 162 void MergeLoops(); 163 void SortLoops(); 164 void UpdateOuterForInnerLoop(BB *bb, LoopHierarchy *outer); 165 void UpdateOuterLoop(const LoopHierarchy *loop); 166 void CreateInnerLoop(LoopHierarchy &inner, LoopHierarchy &outer); 167 void DetectInnerLoop(); 168 void UpdateCGFunc(); 169 void FormLoopHierarchy(); 170 171 private: 172 CGFunc *cgFunc; 173 MemPool *memPool; 174 MapleAllocator loopMemPool; 175 MapleVector<bool> visitedBBs; 176 MapleVector<BB *> sortedBBs; 177 MapleStack<BB *> dfsBBs; 178 MapleVector<bool> onPathBBs; 179 MapleVector<bool> recurseVisited; 180 LoopHierarchy *loops = nullptr; 181 }; 182 183 class CGFuncLoops { 184 public: CGFuncLoops(MemPool & memPool)185 explicit CGFuncLoops(MemPool &memPool) 186 : loopMemPool(&memPool), 187 multiEntries(loopMemPool.Adapter()), 188 loopMembers(loopMemPool.Adapter()), 189 backedge(loopMemPool.Adapter()), 190 exits(loopMemPool.Adapter()), 191 innerLoops(loopMemPool.Adapter()) 192 { 193 } 194 195 ~CGFuncLoops() = default; 196 197 void CheckOverlappingInnerLoops(const MapleVector<CGFuncLoops *> &iLoops, const MapleVector<BB *> &loopMem) const; 198 void CheckLoops() const; 199 void PrintLoops(const CGFuncLoops &funcLoop) const; 200 GetHeader()201 const BB *GetHeader() const 202 { 203 return header; 204 } GetMultiEntries()205 const MapleVector<BB *> &GetMultiEntries() const 206 { 207 return multiEntries; 208 } GetLoopMembers()209 const MapleVector<BB *> &GetLoopMembers() const 210 { 211 return loopMembers; 212 } GetBackedge()213 const MapleVector<BB *> &GetBackedge() const 214 { 215 return backedge; 216 } GetExits()217 const MapleVector<BB *> &GetExits() const 218 { 219 return exits; 220 } GetInnerLoops()221 const MapleVector<CGFuncLoops *> &GetInnerLoops() const 222 { 223 return innerLoops; 224 } GetOuterLoop()225 const CGFuncLoops *GetOuterLoop() const 226 { 227 return outerLoop; 228 } GetLoopLevel()229 uint32 GetLoopLevel() const 230 { 231 return loopLevel; 232 } 233 AddMultiEntries(BB & bb)234 void AddMultiEntries(BB &bb) 235 { 236 multiEntries.emplace_back(&bb); 237 } AddLoopMembers(BB & bb)238 void AddLoopMembers(BB &bb) 239 { 240 loopMembers.emplace_back(&bb); 241 } AddBackedge(BB & bb)242 void AddBackedge(BB &bb) 243 { 244 backedge.emplace_back(&bb); 245 } AddExit(BB & bb)246 void AddExit(BB &bb) 247 { 248 exits.emplace_back(&bb); 249 } AddInnerLoops(CGFuncLoops & loop)250 void AddInnerLoops(CGFuncLoops &loop) 251 { 252 innerLoops.emplace_back(&loop); 253 } SetHeader(BB & bb)254 void SetHeader(BB &bb) 255 { 256 header = &bb; 257 } SetOuterLoop(CGFuncLoops & loop)258 void SetOuterLoop(CGFuncLoops &loop) 259 { 260 outerLoop = &loop; 261 } SetLoopLevel(uint32 val)262 void SetLoopLevel(uint32 val) 263 { 264 loopLevel = val; 265 } 266 267 private: 268 MapleAllocator loopMemPool; 269 BB *header = nullptr; 270 MapleVector<BB *> multiEntries; 271 MapleVector<BB *> loopMembers; 272 MapleVector<BB *> backedge; 273 MapleVector<BB *> exits; 274 MapleVector<CGFuncLoops *> innerLoops; 275 CGFuncLoops *outerLoop = nullptr; 276 uint32 loopLevel = 0; 277 }; 278 279 struct CGFuncLoopCmp { operatorCGFuncLoopCmp280 bool operator()(const CGFuncLoops *lhs, const CGFuncLoops *rhs) const 281 { 282 CHECK_NULL_FATAL(lhs); 283 CHECK_NULL_FATAL(rhs); 284 return lhs->GetHeader()->GetId() < rhs->GetHeader()->GetId(); 285 } 286 }; 287 288 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgLoopAnalysis, maplebe::CGFunc); 289 MAPLE_FUNC_PHASE_DECLARE_END 290 } /* namespace maplebe */ 291 292 #endif /* MAPLEBE_INCLUDE_CG_LOOP_H */ 293