1 /* 2 * Copyright (c) 2021-2024 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 COMPILER_OPTIMIZER_IR_GRAPH_CLONER_H 17 #define COMPILER_OPTIMIZER_IR_GRAPH_CLONER_H 18 19 #include "inst.h" 20 #include "optimizer/analysis/loop_analyzer.h" 21 #include "optimizer/analysis/rpo.h" 22 #include "optimizer/ir/analysis.h" 23 #include "optimizer/ir/basicblock.h" 24 #include "optimizer/ir/graph.h" 25 #include "utils/arena_containers.h" 26 #include "utils/hash.h" 27 28 namespace ark::compiler { 29 class BasicBlock; 30 class Graph; 31 class Inst; 32 33 // NOLINTNEXTLINE(readability-redundant-declaration) 34 bool IsLoopSingleBackEdgeExitPoint(Loop *loop); 35 36 enum UnrollType : uint8_t { 37 UNROLL_WITH_SIDE_EXITS = 0, 38 UNROLL_WITHOUT_SIDE_EXITS = 1, 39 UNROLL_REMOVE_BACK_EDGE = 2, 40 UNROLL_POST_INCREMENT = UNROLL_REMOVE_BACK_EDGE, 41 UNROLL_CONSTANT_ITERATIONS = UNROLL_WITHOUT_SIDE_EXITS | UNROLL_REMOVE_BACK_EDGE 42 }; 43 44 enum class InstCloneType : uint8_t { CLONE_ALL, CLONE_INSTS }; 45 46 enum class CloneEdgeType : uint8_t { EDGE_PRED, EDGE_SUCC }; 47 48 /** 49 * Helper-class, provides methods to: 50 * - Clone the whole graph; 51 * - Clone loop; 52 * - Unroll loop; 53 * - Peel loop; 54 */ 55 class GraphCloner { 56 using PhiInputsMap = ArenaUnorderedMap<Inst *, Inst *>; 57 58 struct LoopUnrollData { 59 BasicBlock *header {nullptr}; 60 BasicBlock *backedge {nullptr}; 61 BasicBlock *exitBlock {nullptr}; 62 BasicBlock *outer {nullptr}; 63 ArenaVector<BasicBlock *> *blocks {nullptr}; 64 InstVector *phiUpdateInputs {nullptr}; 65 PhiInputsMap *phiReplacedInputs {nullptr}; 66 }; 67 68 protected: 69 struct LoopClonerData { 70 BasicBlock *outer {nullptr}; 71 BasicBlock *header {nullptr}; 72 BasicBlock *preHeader {nullptr}; 73 ArenaVector<BasicBlock *> *blocks {nullptr}; 74 }; 75 76 public: 77 PANDA_PUBLIC_API explicit GraphCloner(Graph *graph, ArenaAllocator *allocator, ArenaAllocator *localAllocator); 78 79 PANDA_PUBLIC_API Graph *CloneGraph(); 80 BasicBlock *CloneLoopHeader(BasicBlock *block, BasicBlock *outer, BasicBlock *replaceablePred); 81 Loop *CloneLoop(Loop *loop); 82 83 /** 84 * Make equal to the `factor` number of clones of loop body and insert them into the graph 85 * 86 * /----[pre-loop] 87 * | | 88 * | v 89 * | [loop-body]<----\ 90 * | | | | 91 * | | \-------/ 92 * | | 93 * | v 94 * \--->[outside-block] 95 * | 96 * v 97 * ... 98 * 99 * Cloning with side-exits: 100 * 101 * /----[pre-loop] 102 * | | 103 * | v 104 * | [loop-body]---------\ 105 * | | | 106 * | v | 107 * | [loop-body']------->| 108 * | | | 109 * | v | 110 * | [loop-body'']------>| 111 * | | | 112 * | v | 113 * | [resolver-block]<----/ 114 * | | 115 * | v 116 * \--->[outside-block] 117 * ... 118 * 119 * Cloning without side-exits: 120 * 121 * /----[pre-loop] 122 * | | 123 * | v 124 * | [loop-body] 125 * | | 126 * | v 127 * | [loop-body'] 128 * | | 129 * | v 130 * | [loop-body''] 131 * | | 132 * | v 133 * \--->[outside-block] 134 */ 135 template <UnrollType TYPE> UnrollLoopBody(Loop * loop,size_t factor)136 void UnrollLoopBody(Loop *loop, size_t factor) 137 { 138 ASSERT_PRINT(IsLoopSingleBackEdgeExitPoint(loop), "Cloning blocks doesn't have single entry/exit point"); 139 auto markerHolder = MarkerHolder(GetGraph()); 140 cloneMarker_ = markerHolder.GetMarker(); 141 auto unrollData = PrepareLoopToUnroll(loop, (TYPE & UnrollType::UNROLL_WITHOUT_SIDE_EXITS) == 0); 142 143 auto cloneCount = factor - 1; 144 for (size_t i = 0; i < cloneCount; i++) { 145 CloneBlocksAndInstructions<InstCloneType::CLONE_ALL, true>(*unrollData->blocks, GetGraph()); 146 BuildLoopUnrollControlFlow(unrollData); 147 // NOLINTNEXTLINE(bugprone-suspicious-semicolon, readability-braces-around-statements) 148 if constexpr ((TYPE & UnrollType::UNROLL_WITHOUT_SIDE_EXITS) != 0) { 149 // Users update should be done on the last no-side-exits unroll iteration 150 // before building loop data-flow 151 if (i + 1 == cloneCount) { // last_iteration 152 UpdateUsersAfterNoSideExitsUnroll(unrollData); 153 } 154 } 155 BuildLoopUnrollDataFlow(unrollData); 156 } 157 158 // NOLINTNEXTLINE(bugprone-suspicious-semicolon, readability-braces-around-statements) 159 if constexpr ((TYPE & UnrollType::UNROLL_REMOVE_BACK_EDGE) != 0) { 160 RemoveLoopBackEdge(unrollData); 161 } 162 // NOLINTNEXTLINE(bugprone-suspicious-semicolon, readability-braces-around-statements) 163 if constexpr (TYPE == UnrollType::UNROLL_CONSTANT_ITERATIONS) { 164 RemoveLoopPreHeader(unrollData); 165 } 166 ssb_.FixPhisWithCheckInputs(unrollData->outer); 167 } 168 169 protected: GetGraph()170 Graph *GetGraph() 171 { 172 return graph_; 173 } 174 GetClone(const BasicBlock * block)175 BasicBlock *GetClone(const BasicBlock *block) 176 { 177 ASSERT(block != nullptr); 178 ASSERT_PRINT(block->GetGraph() == GetGraph(), "GraphCloner probably caught disconnected block"); 179 ASSERT_DO(HasClone(block), block->Dump(&std::cerr)); 180 return cloneBlocks_[block->GetId()]; 181 } 182 183 template <CloneEdgeType EDGE_TYPE> CloneEdges(BasicBlock * block)184 void CloneEdges(BasicBlock *block) 185 { 186 auto clone = GetClone(block); 187 188 // NOLINTNEXTLINE(bugprone-suspicious-semicolon, readability-braces-around-statements) 189 if constexpr (EDGE_TYPE == CloneEdgeType::EDGE_SUCC) { 190 auto blockEdges = &block->GetSuccsBlocks(); 191 auto cloneEdges = &clone->GetSuccsBlocks(); 192 ASSERT(cloneEdges->empty()); 193 cloneEdges->reserve(blockEdges->size()); 194 for (auto edge : *blockEdges) { 195 cloneEdges->push_back(GetClone(edge)); 196 } 197 } else { 198 auto blockEdges = &block->GetPredsBlocks(); 199 auto cloneEdges = &clone->GetPredsBlocks(); 200 201 ASSERT(cloneEdges->empty()); 202 cloneEdges->reserve(blockEdges->size()); 203 for (auto edge : *blockEdges) { 204 cloneEdges->push_back(GetClone(edge)); 205 } 206 } 207 } 208 209 /** 210 * For each block of input vector create a new one empty block and populate it with the instructions, 211 * cloned form the original block 212 */ 213 template <InstCloneType TYPE, bool SKIP_SAFEPOINTS> CloneBlocksAndInstructions(const ArenaVector<BasicBlock * > & blocks,Graph * targetGraph)214 void CloneBlocksAndInstructions(const ArenaVector<BasicBlock *> &blocks, Graph *targetGraph) 215 { 216 cloneBlocks_.clear(); 217 cloneBlocks_.resize(GetGraph()->GetVectorBlocks().size(), nullptr); 218 cloneInstructions_.clear(); 219 size_t instCount = 0; 220 for (const auto &block : blocks) { 221 if (block != nullptr) { 222 auto clone = block->Clone(targetGraph); 223 cloneBlocks_[block->GetId()] = clone; 224 CloneInstructions<TYPE, SKIP_SAFEPOINTS>(block, clone, &instCount); 225 if (block->IsTryBegin()) { 226 clone->SetTryBegin(true); 227 targetGraph->AppendTryBeginBlock(clone); 228 } 229 if (block->IsTryEnd()) { 230 clone->SetTryEnd(true); 231 } 232 if (block->IsTry()) { 233 clone->SetTry(true); 234 } 235 if (block->IsCatch()) { 236 clone->SetCatch(true); 237 } 238 } 239 } 240 } 241 242 void MakeLoopCloneInfo(LoopClonerData *unrollData); 243 LoopClonerData *PrepareLoopToClone(Loop *loop); 244 void ProcessMarkedInsts(LoopClonerData *data); 245 BasicBlock *CreateNewOutsideSucc(BasicBlock *outsideSucc, BasicBlock *backEdge, BasicBlock *preHeader); 246 247 /** 248 * Use the following rules cloning the inputs: 249 * - if input of the original instruction has clone - insert this clone as input 250 * - otherwise - use original input as clone instruction input 251 */ 252 template <bool REPLACE_HEADER_PHI> 253 void SetCloneInputs(Inst *inst, BasicBlock *block = nullptr) 254 { 255 auto clone = GetClone(inst); 256 for (size_t i = 0; i < inst->GetInputsCount(); i++) { 257 auto input = inst->GetInput(i).GetInst(); 258 if (REPLACE_HEADER_PHI && IsInstLoopHeaderPhi(input, inst->GetBasicBlock()->GetLoop())) { 259 ASSERT(block != nullptr); 260 input = input->CastToPhi()->GetPhiInput(block); 261 } else if (HasClone(input)) { 262 input = GetClone(input); 263 } 264 265 if (clone->IsOperandsDynamic()) { 266 clone->AppendInput(input); 267 if (clone->IsSaveState()) { 268 static_cast<SaveStateInst *>(clone)->SetVirtualRegister( 269 i, static_cast<SaveStateInst *>(inst)->GetVirtualRegister(i)); 270 } else if (clone->IsPhi()) { 271 clone->CastToPhi()->SetPhiInputBbNum(i, inst->CastToPhi()->GetPhiInputBbNum(i)); 272 } 273 } else { 274 clone->SetInput(i, input); 275 } 276 } 277 } 278 279 void UpdateCaller(Inst *inst); 280 GetClone(Inst * inst)281 Inst *GetClone(Inst *inst) 282 { 283 ASSERT(inst != nullptr); 284 ASSERT(HasClone(inst)); 285 286 // We don't use clone_marker_ when cloning the whole graph, so lets at least check the basic block here 287 ASSERT(inst->GetBasicBlock() != nullptr); 288 ASSERT_PRINT(inst->GetBasicBlock()->GetGraph() == GetGraph(), 289 "GraphCloner probably caught an instruction from disconnected block"); 290 // Empty clone_blocks_ means we are cloning only one basic block 291 ASSERT(cloneBlocks_.empty() || HasClone(inst->GetBasicBlock())); 292 293 return cloneInstructions_[inst->GetCloneNumber()]; 294 } 295 296 // Cloned blocks and instructions getters HasClone(const BasicBlock * block)297 bool HasClone(const BasicBlock *block) 298 { 299 return (block->GetId() < cloneBlocks_.size()) && (cloneBlocks_[block->GetId()] != nullptr); 300 } 301 HasClone(Inst * inst)302 bool HasClone(Inst *inst) 303 { 304 return inst->IsMarked(cloneMarker_) && (inst->GetCloneNumber() < cloneInstructions_.size()); 305 } 306 307 private: 308 // Whole graph cloning 309 void CopyLoop(Loop *loop, Loop *clonedLoop); 310 void CloneLinearOrder(Graph *newGraph); 311 void BuildControlFlow(); 312 void BuildTryCatchLogic(Graph *newGraph); 313 void BuildDataFlow(); 314 void CloneConstantsInfo(Graph *newGraph); 315 void CloneAnalyses(Graph *newGraph); 316 // Loop cloning 317 void SplitPreHeader(Loop *loop); 318 GraphCloner::LoopClonerData *PopulateLoopClonerData(Loop *loop, BasicBlock *preHeader, BasicBlock *outsideSucc); 319 void BuildLoopCloneControlFlow(LoopClonerData *unrollData); 320 void BuildLoopCloneDataFlow(LoopClonerData *unrollData); 321 // Unroll cloning 322 LoopUnrollData *PrepareLoopToUnroll(Loop *loop, bool cloneSideExits); 323 BasicBlock *CreateResolverBlock(Loop *loop, BasicBlock *backEdge); 324 BasicBlock *SplitBackEdge(LoopUnrollData *unrollData, Loop *loop, BasicBlock *backEdge); 325 Inst *GetCompareInst(Inst *ifimm); 326 void UpdateUsersAfterNoSideExitsUnroll(const LoopUnrollData *unrollData); 327 void UpdateOutloopUsers(Loop *loop, Inst *inst); 328 void BuildLoopUnrollControlFlow(LoopUnrollData *unrollData); 329 void BuildLoopUnrollDataFlow(LoopUnrollData *unrollData); 330 void RemoveLoopBackEdge(const LoopUnrollData *unrollData); 331 void RemoveLoopPreHeader(const LoopUnrollData *unrollData); 332 // Loop header cloning 333 void BuildClonedLoopHeaderDataFlow(const BasicBlock &block, BasicBlock *resolver, BasicBlock *clone); 334 void UpdateUsersForClonedLoopHeader(Inst *inst, BasicBlock *outerBlock); 335 336 /// Clone block's instructions and append to the block's clone 337 template <InstCloneType TYPE, bool SKIP_SAFEPOINTS> CloneInstructions(const BasicBlock * block,BasicBlock * clone,size_t * instCount)338 void CloneInstructions(const BasicBlock *block, BasicBlock *clone, size_t *instCount) 339 { 340 for (auto inst : block->Insts()) { 341 if constexpr (SKIP_SAFEPOINTS) { // NOLINT 342 if (inst->GetOpcode() == Opcode::SafePoint) { 343 continue; 344 } 345 } 346 if constexpr (TYPE != InstCloneType::CLONE_ALL) { // NOLINT 347 if (inst->GetOpcode() == Opcode::NOP) { 348 continue; 349 } 350 } 351 352 auto *clonedInst = CloneInstruction(inst, instCount, clone->GetGraph()); 353 354 cloneInstMap_[inst] = clonedInst; 355 cloneInstMap_[clonedInst] = inst; 356 357 clone->AppendInst(clonedInst); 358 } 359 360 if constexpr (TYPE == InstCloneType::CLONE_ALL) { // NOLINT 361 for (auto phi : block->PhiInsts()) { 362 auto phiClone = CloneInstruction(phi, instCount, clone->GetGraph()); 363 cloneInstMap_[phi] = phiClone; 364 cloneInstMap_[phiClone] = phi; 365 clone->AppendPhi(phiClone->CastToPhi()); 366 } 367 } 368 } 369 370 /// Clone instruction and mark both: clone and cloned CloneInstruction(Inst * inst,size_t * instCount,Graph * targetGraph)371 Inst *CloneInstruction(Inst *inst, size_t *instCount, Graph *targetGraph) 372 { 373 inst->SetCloneNumber((*instCount)++); 374 auto instClone = inst->Clone(targetGraph); 375 cloneInstructions_.push_back(instClone); 376 inst->SetMarker(cloneMarker_); 377 instClone->SetMarker(cloneMarker_); 378 if (inst->GetBasicBlock()->GetGraph() != targetGraph) { 379 instClone->SetId(inst->GetId()); 380 } 381 return instClone; 382 } 383 384 bool IsInstLoopHeaderPhi(Inst *inst, Loop *loop); 385 386 // clone throwable inst -> catch blocks mapping 387 void CloneThrowableInstHandlers(Graph *newGraph); 388 389 protected: 390 Marker cloneMarker_ {UNDEF_MARKER}; // NOLINT(misc-non-private-member-variables-in-classes) 391 392 private: 393 Graph *graph_; 394 ArenaAllocator *allocator_; 395 ArenaAllocator *localAllocator_; 396 ArenaVector<BasicBlock *> cloneBlocks_; 397 InstVector cloneInstructions_; 398 SaveStateBridgesBuilder ssb_; 399 ArenaMap<const Inst *, const Inst *> cloneInstMap_; 400 }; 401 } // namespace ark::compiler 402 403 #endif // COMPILER_OPTIMIZER_IR_GRAPH_CLONER_H 404