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 MAPLE_ME_INCLUDE_ME_CFG_H 17 #define MAPLE_ME_INCLUDE_ME_CFG_H 18 #include "me_function.h" 19 #include "maple_phase.h" 20 21 namespace maple { 22 class MeCFG : public AnalysisResult { 23 using BBPtrHolder = MapleVector<BB *>; 24 25 public: 26 using value_type = BBPtrHolder::value_type; 27 using size_type = BBPtrHolder::size_type; 28 using difference_type = BBPtrHolder::difference_type; 29 using pointer = BBPtrHolder::pointer; 30 using const_pointer = BBPtrHolder::const_pointer; 31 using reference = BBPtrHolder::reference; 32 using const_reference = BBPtrHolder::const_reference; 33 using iterator = BBPtrHolder::iterator; 34 using const_iterator = BBPtrHolder::const_iterator; 35 using reverse_iterator = BBPtrHolder::reverse_iterator; 36 using const_reverse_iterator = BBPtrHolder::const_reverse_iterator; 37 MeCFG(MemPool * memPool,MeFunction & f)38 MeCFG(MemPool *memPool, MeFunction &f) 39 : AnalysisResult(memPool), 40 mecfgAlloc(memPool), 41 func(f), 42 patternSet(mecfgAlloc.Adapter()), 43 bbVec(mecfgAlloc.Adapter()), 44 labelBBIdMap(mecfgAlloc.Adapter()), 45 bbTryNodeMap(mecfgAlloc.Adapter()), 46 endTryBB2TryBB(mecfgAlloc.Adapter()), 47 sccTopologicalVec(mecfgAlloc.Adapter()), 48 sccOfBB(mecfgAlloc.Adapter()), 49 backEdges(mecfgAlloc.Adapter()) 50 { 51 } 52 53 ~MeCFG() = default; 54 55 void Verify() const; 56 void VerifyLabels() const; 57 void Dump() const; 58 bool FindExprUse(const BaseNode &expr, StIdx stIdx) const; 59 bool FindDef(const StmtNode &stmt, StIdx stIdx) const; 60 BB *NewBasicBlock(); 61 BB &InsertNewBasicBlock(const BB &position, bool isInsertBefore = true); 62 void DeleteBasicBlock(const BB &bb); 63 BB *NextBB(const BB *bb); 64 65 BB *PrevBB(const BB *bb); 66 GetFunc()67 const MeFunction &GetFunc() const 68 { 69 return func; 70 } 71 GetHasDoWhile()72 bool GetHasDoWhile() const 73 { 74 return hasDoWhile; 75 } 76 SetHasDoWhile(bool hdw)77 void SetHasDoWhile(bool hdw) 78 { 79 hasDoWhile = hdw; 80 } 81 GetAlloc()82 MapleAllocator &GetAlloc() 83 { 84 return mecfgAlloc; 85 } 86 SetNextBBId(uint32 currNextBBId)87 void SetNextBBId(uint32 currNextBBId) 88 { 89 nextBBId = currNextBBId; 90 } GetNextBBId()91 uint32 GetNextBBId() const 92 { 93 return nextBBId; 94 } DecNextBBId()95 void DecNextBBId() 96 { 97 --nextBBId; 98 } 99 GetAllBBs()100 MapleVector<BB *> &GetAllBBs() 101 { 102 return bbVec; 103 } 104 begin()105 iterator begin() 106 { 107 return bbVec.begin(); 108 } begin()109 const_iterator begin() const 110 { 111 return bbVec.begin(); 112 } cbegin()113 const_iterator cbegin() const 114 { 115 return bbVec.cbegin(); 116 } 117 end()118 iterator end() 119 { 120 return bbVec.end(); 121 } end()122 const_iterator end() const 123 { 124 return bbVec.end(); 125 } cend()126 const_iterator cend() const 127 { 128 return bbVec.cend(); 129 } 130 rbegin()131 reverse_iterator rbegin() 132 { 133 return bbVec.rbegin(); 134 } rbegin()135 const_reverse_iterator rbegin() const 136 { 137 return bbVec.rbegin(); 138 } crbegin()139 const_reverse_iterator crbegin() const 140 { 141 return bbVec.crbegin(); 142 } 143 rend()144 reverse_iterator rend() 145 { 146 return bbVec.rend(); 147 } rend()148 const_reverse_iterator rend() const 149 { 150 return bbVec.rend(); 151 } crend()152 const_reverse_iterator crend() const 153 { 154 return bbVec.crend(); 155 } 156 front()157 reference front() 158 { 159 return bbVec.front(); 160 } 161 back()162 reference back() 163 { 164 return bbVec.back(); 165 } 166 front()167 const_reference front() const 168 { 169 return bbVec.front(); 170 } 171 back()172 const_reference back() const 173 { 174 return bbVec.back(); 175 } 176 empty()177 bool empty() const 178 { 179 return bbVec.empty(); 180 } 181 size()182 size_t size() const 183 { 184 return bbVec.size(); 185 } valid_begin()186 FilterIterator<const_iterator> valid_begin() const 187 { 188 return build_filter_iterator(begin(), [this](const_iterator it) { 189 return FilterNullPtr<const_iterator>(it, end()); 190 }); 191 } 192 valid_end()193 FilterIterator<const_iterator> valid_end() const 194 { 195 return build_filter_iterator(end()); 196 } 197 valid_rbegin()198 FilterIterator<const_reverse_iterator> valid_rbegin() const 199 { 200 return build_filter_iterator(rbegin(), [this](const_reverse_iterator it) { 201 return FilterNullPtr<const_reverse_iterator>(it, rend()); 202 }); 203 } 204 valid_rend()205 FilterIterator<const_reverse_iterator> valid_rend() const 206 { 207 return build_filter_iterator(rend()); 208 } 209 common_entry()210 const_iterator common_entry() const 211 { 212 return begin(); 213 } 214 context_begin()215 const_iterator context_begin() const 216 { 217 return ++(++begin()); 218 } 219 context_end()220 const_iterator context_end() const 221 { 222 return end(); 223 } 224 common_exit()225 const_iterator common_exit() const 226 { 227 return ++begin(); 228 } 229 NumBBs()230 uint32 NumBBs() const 231 { 232 return nextBBId; 233 } 234 ValidBBNum()235 uint32 ValidBBNum() const 236 { 237 uint32 num = 0; 238 for (auto bbit = valid_begin(); bbit != valid_end(); ++bbit) { 239 ++num; 240 } 241 return num; 242 } 243 GetLabelBBIdMap()244 const MapleUnorderedMap<LabelIdx, BB *> &GetLabelBBIdMap() const 245 { 246 return labelBBIdMap; 247 } GetLabelBBAt(LabelIdx idx)248 BB *GetLabelBBAt(LabelIdx idx) const 249 { 250 auto it = labelBBIdMap.find(idx); 251 if (it != labelBBIdMap.end()) { 252 return it->second; 253 } 254 return nullptr; 255 } 256 SetLabelBBAt(LabelIdx idx,BB * bb)257 void SetLabelBBAt(LabelIdx idx, BB *bb) 258 { 259 labelBBIdMap[idx] = bb; 260 } EraseLabelBBAt(LabelIdx idx)261 void EraseLabelBBAt(LabelIdx idx) 262 { 263 labelBBIdMap.erase(idx); 264 } 265 GetBBFromID(BBId bbID)266 BB *GetBBFromID(BBId bbID) const 267 { 268 DEBUG_ASSERT(bbID < bbVec.size(), "array index out of range"); 269 return bbVec.at(bbID); 270 } 271 NullifyBBByID(BBId bbID)272 void NullifyBBByID(BBId bbID) 273 { 274 DEBUG_ASSERT(bbID < bbVec.size(), "array index out of range"); 275 bbVec.at(bbID) = nullptr; 276 } 277 GetCommonEntryBB()278 BB *GetCommonEntryBB() const 279 { 280 return *common_entry(); 281 } 282 GetCommonExitBB()283 BB *GetCommonExitBB() const 284 { 285 return *common_exit(); 286 } 287 GetFirstBB()288 BB *GetFirstBB() const 289 { 290 if (GetCommonEntryBB()->GetUniqueSucc()) { 291 return GetCommonEntryBB()->GetUniqueSucc(); 292 } 293 return *(++(++valid_begin())); 294 } 295 GetLastBB()296 BB *GetLastBB() const 297 { 298 return *valid_rbegin(); 299 } 300 SetBBTryNodeMap(BB & bb,StmtNode & tryStmt)301 void SetBBTryNodeMap(BB &bb, StmtNode &tryStmt) 302 { 303 bbTryNodeMap[&bb] = &tryStmt; 304 } 305 GetBBTryNodeMap()306 const MapleUnorderedMap<BB *, StmtNode *> &GetBBTryNodeMap() const 307 { 308 return bbTryNodeMap; 309 } 310 GetEndTryBB2TryBB()311 const MapleUnorderedMap<BB *, BB *> &GetEndTryBB2TryBB() const 312 { 313 return endTryBB2TryBB; 314 } 315 GetTryBBFromEndTryBB(BB * endTryBB)316 const BB *GetTryBBFromEndTryBB(BB *endTryBB) const 317 { 318 auto it = endTryBB2TryBB.find(endTryBB); 319 return it == endTryBB2TryBB.end() ? nullptr : it->second; 320 } 321 GetTryBBFromEndTryBB(BB * endTryBB)322 BB *GetTryBBFromEndTryBB(BB *endTryBB) 323 { 324 auto it = endTryBB2TryBB.find(endTryBB); 325 return it == endTryBB2TryBB.end() ? nullptr : it->second; 326 } 327 SetBBTryBBMap(BB * currBB,BB * tryBB)328 void SetBBTryBBMap(BB *currBB, BB *tryBB) 329 { 330 endTryBB2TryBB[currBB] = tryBB; 331 } SetTryBBByOtherEndTryBB(BB * endTryBB,BB * otherTryBB)332 void SetTryBBByOtherEndTryBB(BB *endTryBB, BB *otherTryBB) 333 { 334 endTryBB2TryBB[endTryBB] = endTryBB2TryBB[otherTryBB]; 335 } 336 337 void SwapBBId(BB &bb1, BB &bb2); 338 void ConstructBBFreqFromStmtFreq(); 339 void ConstructStmtFreq(); 340 void ConstructEdgeFreqFromBBFreq(); 341 void VerifyBBFreq(); 342 343 private: 344 std::string ConstructFileNameToDump(const std::string &prefix) const; 345 bool IsStartTryBB(BB &meBB) const; 346 void SetTryBlockInfo(const StmtNode *nextStmt, StmtNode *tryStmt, BB *lastTryBB, BB *curBB, BB *newBB); 347 348 void VerifySCC(); 349 void SCCTopologicalSort(std::vector<SCCOfBBs *> &sccNodes); 350 void BuildSCCDFS(BB &bb, uint32 &visitIndex, std::vector<SCCOfBBs *> &sccNodes, std::vector<uint32> &visitedOrder, 351 std::vector<uint32> &lowestOrder, std::vector<bool> &inStack, std::stack<uint32> &visitStack); 352 353 MapleAllocator mecfgAlloc; 354 MeFunction &func; 355 MapleSet<LabelIdx> patternSet; 356 BBPtrHolder bbVec; 357 MapleUnorderedMap<LabelIdx, BB *> labelBBIdMap; 358 MapleUnorderedMap<BB *, StmtNode *> bbTryNodeMap; // maps isTry bb to its try stmt 359 MapleUnorderedMap<BB *, BB *> endTryBB2TryBB; // maps endtry bb to its try bb 360 bool hasDoWhile = false; 361 uint32 nextBBId = 0; 362 363 // BB SCC 364 MapleVector<SCCOfBBs *> sccTopologicalVec; 365 uint32 numOfSCCs = 0; 366 MapleVector<SCCOfBBs *> sccOfBB; 367 MapleSet<std::pair<uint32, uint32>> backEdges; 368 }; 369 } // namespace maple 370 #endif // MAPLE_ME_INCLUDE_ME_CFG_H 371