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 bool IfReplaceWithAssertNonNull(const BB &bb) const; 56 void Verify() const; 57 void VerifyLabels() const; 58 void Dump() const; 59 bool FindExprUse(const BaseNode &expr, StIdx stIdx) const; 60 bool FindUse(const StmtNode &stmt, StIdx stIdx) const; 61 bool FindDef(const StmtNode &stmt, StIdx stIdx) const; 62 bool HasNoOccBetween(StmtNode &from, const StmtNode &to, StIdx stIdx) const; 63 BB *NewBasicBlock(); 64 BB &InsertNewBasicBlock(const BB &position, bool isInsertBefore = true); 65 void DeleteBasicBlock(const BB &bb); 66 BB *NextBB(const BB *bb); 67 BB *PrevBB(const BB *bb); 68 GetFunc()69 const MeFunction &GetFunc() const 70 { 71 return func; 72 } 73 GetHasDoWhile()74 bool GetHasDoWhile() const 75 { 76 return hasDoWhile; 77 } 78 SetHasDoWhile(bool hdw)79 void SetHasDoWhile(bool hdw) 80 { 81 hasDoWhile = hdw; 82 } 83 GetAlloc()84 MapleAllocator &GetAlloc() 85 { 86 return mecfgAlloc; 87 } 88 SetNextBBId(uint32 currNextBBId)89 void SetNextBBId(uint32 currNextBBId) 90 { 91 nextBBId = currNextBBId; 92 } GetNextBBId()93 uint32 GetNextBBId() const 94 { 95 return nextBBId; 96 } DecNextBBId()97 void DecNextBBId() 98 { 99 --nextBBId; 100 } 101 GetAllBBs()102 MapleVector<BB *> &GetAllBBs() 103 { 104 return bbVec; 105 } 106 begin()107 iterator begin() 108 { 109 return bbVec.begin(); 110 } begin()111 const_iterator begin() const 112 { 113 return bbVec.begin(); 114 } cbegin()115 const_iterator cbegin() const 116 { 117 return bbVec.cbegin(); 118 } 119 end()120 iterator end() 121 { 122 return bbVec.end(); 123 } end()124 const_iterator end() const 125 { 126 return bbVec.end(); 127 } cend()128 const_iterator cend() const 129 { 130 return bbVec.cend(); 131 } 132 rbegin()133 reverse_iterator rbegin() 134 { 135 return bbVec.rbegin(); 136 } rbegin()137 const_reverse_iterator rbegin() const 138 { 139 return bbVec.rbegin(); 140 } crbegin()141 const_reverse_iterator crbegin() const 142 { 143 return bbVec.crbegin(); 144 } 145 rend()146 reverse_iterator rend() 147 { 148 return bbVec.rend(); 149 } rend()150 const_reverse_iterator rend() const 151 { 152 return bbVec.rend(); 153 } crend()154 const_reverse_iterator crend() const 155 { 156 return bbVec.crend(); 157 } 158 front()159 reference front() 160 { 161 return bbVec.front(); 162 } 163 back()164 reference back() 165 { 166 return bbVec.back(); 167 } 168 front()169 const_reference front() const 170 { 171 return bbVec.front(); 172 } 173 back()174 const_reference back() const 175 { 176 return bbVec.back(); 177 } 178 empty()179 bool empty() const 180 { 181 return bbVec.empty(); 182 } 183 size()184 size_t size() const 185 { 186 return bbVec.size(); 187 } valid_begin()188 FilterIterator<const_iterator> valid_begin() const 189 { 190 return build_filter_iterator(begin(), std::bind(FilterNullPtr<const_iterator>, std::placeholders::_1, end())); 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(), 201 std::bind(FilterNullPtr<const_reverse_iterator>, std::placeholders::_1, rend())); 202 } 203 valid_rend()204 FilterIterator<const_reverse_iterator> valid_rend() const 205 { 206 return build_filter_iterator(rend()); 207 } 208 common_entry()209 const_iterator common_entry() const 210 { 211 return begin(); 212 } 213 context_begin()214 const_iterator context_begin() const 215 { 216 return ++(++begin()); 217 } 218 context_end()219 const_iterator context_end() const 220 { 221 return end(); 222 } 223 common_exit()224 const_iterator common_exit() const 225 { 226 return ++begin(); 227 } 228 NumBBs()229 uint32 NumBBs() const 230 { 231 return nextBBId; 232 } 233 ValidBBNum()234 uint32 ValidBBNum() const 235 { 236 uint32 num = 0; 237 for (auto bbit = valid_begin(); bbit != valid_end(); ++bbit) { 238 ++num; 239 } 240 return num; 241 } 242 GetLabelBBIdMap()243 const MapleUnorderedMap<LabelIdx, BB *> &GetLabelBBIdMap() const 244 { 245 return labelBBIdMap; 246 } GetLabelBBAt(LabelIdx idx)247 BB *GetLabelBBAt(LabelIdx idx) const 248 { 249 auto it = labelBBIdMap.find(idx); 250 if (it != labelBBIdMap.end()) { 251 return it->second; 252 } 253 return nullptr; 254 } 255 SetLabelBBAt(LabelIdx idx,BB * bb)256 void SetLabelBBAt(LabelIdx idx, BB *bb) 257 { 258 labelBBIdMap[idx] = bb; 259 } EraseLabelBBAt(LabelIdx idx)260 void EraseLabelBBAt(LabelIdx idx) 261 { 262 labelBBIdMap.erase(idx); 263 } 264 GetBBFromID(BBId bbID)265 BB *GetBBFromID(BBId bbID) const 266 { 267 DEBUG_ASSERT(bbID < bbVec.size(), "array index out of range"); 268 return bbVec.at(bbID); 269 } 270 NullifyBBByID(BBId bbID)271 void NullifyBBByID(BBId bbID) 272 { 273 DEBUG_ASSERT(bbID < bbVec.size(), "array index out of range"); 274 bbVec.at(bbID) = nullptr; 275 } 276 GetCommonEntryBB()277 BB *GetCommonEntryBB() const 278 { 279 return *common_entry(); 280 } 281 GetCommonExitBB()282 BB *GetCommonExitBB() const 283 { 284 return *common_exit(); 285 } 286 GetFirstBB()287 BB *GetFirstBB() const 288 { 289 if (GetCommonEntryBB()->GetUniqueSucc()) { 290 return GetCommonEntryBB()->GetUniqueSucc(); 291 } 292 return *(++(++valid_begin())); 293 } 294 GetLastBB()295 BB *GetLastBB() const 296 { 297 return *valid_rbegin(); 298 } 299 SetBBTryNodeMap(BB & bb,StmtNode & tryStmt)300 void SetBBTryNodeMap(BB &bb, StmtNode &tryStmt) 301 { 302 bbTryNodeMap[&bb] = &tryStmt; 303 } 304 GetBBTryNodeMap()305 const MapleUnorderedMap<BB *, StmtNode *> &GetBBTryNodeMap() const 306 { 307 return bbTryNodeMap; 308 } 309 GetEndTryBB2TryBB()310 const MapleUnorderedMap<BB *, BB *> &GetEndTryBB2TryBB() const 311 { 312 return endTryBB2TryBB; 313 } 314 GetTryBBFromEndTryBB(BB * endTryBB)315 const BB *GetTryBBFromEndTryBB(BB *endTryBB) const 316 { 317 auto it = endTryBB2TryBB.find(endTryBB); 318 return it == endTryBB2TryBB.end() ? nullptr : it->second; 319 } 320 GetTryBBFromEndTryBB(BB * endTryBB)321 BB *GetTryBBFromEndTryBB(BB *endTryBB) 322 { 323 auto it = endTryBB2TryBB.find(endTryBB); 324 return it == endTryBB2TryBB.end() ? nullptr : it->second; 325 } 326 SetBBTryBBMap(BB * currBB,BB * tryBB)327 void SetBBTryBBMap(BB *currBB, BB *tryBB) 328 { 329 endTryBB2TryBB[currBB] = tryBB; 330 } SetTryBBByOtherEndTryBB(BB * endTryBB,BB * otherTryBB)331 void SetTryBBByOtherEndTryBB(BB *endTryBB, BB *otherTryBB) 332 { 333 endTryBB2TryBB[endTryBB] = endTryBB2TryBB[otherTryBB]; 334 } 335 336 void CreateBasicBlocks(); 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