1/* 2 * Copyright (c) 2025 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 16import { BasicBlock } from '../BasicBlock'; 17import { ArkAssignStmt, ArkIfStmt, Stmt } from '../../base/Stmt'; 18import { AbstractInvokeExpr } from '../../base/Expr'; 19import { Builtin } from '../../common/Builtin'; 20import { ArkIRTransformer } from '../../common/ArkIRTransformer'; 21import { BlockBuilder } from './CfgBuilder'; 22 23/** 24 * Builder for loop in CFG 25 */ 26export class LoopBuilder { 27 public rebuildBlocksInLoop( 28 blockBuilderToCfgBlock: Map<BlockBuilder, BasicBlock>, 29 blocksContainLoopCondition: Set<BlockBuilder>, 30 basicBlockSet: Set<BasicBlock>, 31 blockBuilders: BlockBuilder[] 32 ): void { 33 for (const blockBuilder of blocksContainLoopCondition) { 34 if (!blockBuilderToCfgBlock.get(blockBuilder)) { 35 continue; 36 } 37 const block = blockBuilderToCfgBlock.get(blockBuilder) as BasicBlock; 38 39 const blockId = block.getId(); 40 const stmts = block.getStmts(); 41 const stmtsCnt = stmts.length; 42 const { ifStmtIdx, iteratorNextStmtIdx, dummyInitializerStmtIdx } = this.findIteratorIdx(stmts); 43 if (iteratorNextStmtIdx !== -1 || dummyInitializerStmtIdx !== -1) { 44 const lastStmtIdxBeforeCondition = iteratorNextStmtIdx !== -1 ? iteratorNextStmtIdx : dummyInitializerStmtIdx; 45 const stmtsInsertBeforeCondition = stmts.slice(0, lastStmtIdxBeforeCondition); 46 47 // If the loop body is empty, the loop conditional block should contain its own 48 const emptyLoopBody = blockBuilder.nexts.length === 1; 49 if (emptyLoopBody) { 50 blockBuilder.nexts.splice(0, 0, blockBuilder); 51 blockBuilder.lasts.push(blockBuilder); 52 block.getSuccessors().splice(0, 0, block); 53 block.addPredecessorBlock(block); 54 } 55 56 let prevBlockBuilderContainsLoop = this.doesPrevBlockBuilderContainLoop(blockBuilder, blockId, blocksContainLoopCondition); 57 if (prevBlockBuilderContainsLoop) { 58 // should create an extra block when previous block contains loop condition 59 this.insertBeforeConditionBlockBuilder( 60 blockBuilderToCfgBlock, 61 blockBuilder, 62 stmtsInsertBeforeCondition, 63 false, 64 basicBlockSet, 65 blockBuilders 66 ); 67 } else { 68 const blockBuilderBeforeCondition = blockBuilder.lasts[0]; 69 const blockBeforeCondition = blockBuilderToCfgBlock.get(blockBuilderBeforeCondition) as BasicBlock; 70 stmtsInsertBeforeCondition.forEach(stmt => blockBeforeCondition?.getStmts().push(stmt)); 71 } 72 if (dummyInitializerStmtIdx !== -1 && ifStmtIdx !== stmtsCnt - 1) { 73 // put incrementor statements into block which reenters condition 74 this.adjustIncrementorStmts( 75 stmts, 76 ifStmtIdx, 77 blockBuilder, 78 blockId, 79 blockBuilderToCfgBlock, 80 blocksContainLoopCondition, 81 basicBlockSet, 82 emptyLoopBody, 83 blockBuilders 84 ); 85 } else if (iteratorNextStmtIdx !== -1) { 86 // put statements which get value of iterator into block after condition 87 const blockBuilderAfterCondition = blockBuilder.nexts[0]; 88 const blockAfterCondition = blockBuilderToCfgBlock.get(blockBuilderAfterCondition) as BasicBlock; 89 const stmtsAfterCondition = stmts.slice(ifStmtIdx + 1); 90 blockAfterCondition?.getStmts().splice(0, 0, ...stmtsAfterCondition); 91 } 92 // remove statements which should not in condition 93 const firstStmtIdxInCondition = iteratorNextStmtIdx !== -1 ? iteratorNextStmtIdx : dummyInitializerStmtIdx + 1; 94 stmts.splice(0, firstStmtIdxInCondition); 95 stmts.splice(ifStmtIdx - firstStmtIdxInCondition + 1); 96 } 97 } 98 } 99 100 private doesPrevBlockBuilderContainLoop(currBlockBuilder: BlockBuilder, currBlockId: number, blocksContainLoopCondition: Set<BlockBuilder>): boolean { 101 let prevBlockBuilderContainsLoop = false; 102 for (const prevBlockBuilder of currBlockBuilder.lasts) { 103 if (prevBlockBuilder.id < currBlockId && blocksContainLoopCondition.has(prevBlockBuilder)) { 104 prevBlockBuilderContainsLoop = true; 105 break; 106 } 107 } 108 return prevBlockBuilderContainsLoop; 109 } 110 111 private insertBeforeConditionBlockBuilder( 112 blockBuilderToCfgBlock: Map<BlockBuilder, BasicBlock>, 113 conditionBlockBuilder: BlockBuilder, 114 stmtsInsertBeforeCondition: Stmt[], 115 collectReenter: Boolean, 116 basicBlockSet: Set<BasicBlock>, 117 blockBuilders: BlockBuilder[] 118 ): void { 119 if (stmtsInsertBeforeCondition.length === 0) { 120 return; 121 } 122 const blockId = conditionBlockBuilder.id; 123 const block = this.getBlockFromMap(blockBuilderToCfgBlock, conditionBlockBuilder); 124 const { blockBuildersBeforeCondition, blocksBeforeCondition, blockBuildersReenterCondition, blocksReenterCondition } = 125 this.collectBlocksBeforeAndReenter(blockBuilderToCfgBlock, conditionBlockBuilder, blockId); 126 127 const { collectedBlockBuilders, collectedBlocks } = this.getCollectedBlocks( 128 collectReenter, 129 blockBuildersBeforeCondition, 130 blocksBeforeCondition, 131 blockBuildersReenterCondition, 132 blocksReenterCondition 133 ); 134 135 const { blockBuilderInsertBeforeCondition, blockInsertBeforeCondition } = this.createAndLinkBlocks( 136 collectedBlockBuilders, 137 collectedBlocks, 138 conditionBlockBuilder, 139 stmtsInsertBeforeCondition, 140 block 141 ); 142 143 this.updatePredecessors( 144 collectedBlockBuilders, 145 blockBuilderToCfgBlock, 146 conditionBlockBuilder, 147 blockBuilderInsertBeforeCondition, 148 blockInsertBeforeCondition 149 ); 150 151 const { newPrevBlockBuildersBeforeCondition, newPrevBlocksBeforeCondition } = this.getNewPrevBlocks( 152 collectReenter, 153 blockBuildersBeforeCondition, 154 blocksBeforeCondition, 155 blockBuilderInsertBeforeCondition, 156 blockInsertBeforeCondition, 157 blockBuildersReenterCondition, 158 blocksReenterCondition 159 ); 160 161 this.updateConditionBlockBuilder(conditionBlockBuilder, newPrevBlockBuildersBeforeCondition, block, newPrevBlocksBeforeCondition); 162 163 this.finalizeInsertion(blockBuilderInsertBeforeCondition, blockInsertBeforeCondition, basicBlockSet, blockBuilderToCfgBlock, blockBuilders); 164 } 165 166 private getBlockFromMap(blockBuilderToCfgBlock: Map<BlockBuilder, BasicBlock>, conditionBlockBuilder: BlockBuilder): BasicBlock { 167 return blockBuilderToCfgBlock.get(conditionBlockBuilder) as BasicBlock; 168 } 169 170 private collectBlocksBeforeAndReenter( 171 blockBuilderToCfgBlock: Map<BlockBuilder, BasicBlock>, 172 conditionBlockBuilder: BlockBuilder, 173 blockId: number 174 ): { 175 blockBuildersBeforeCondition: BlockBuilder[]; 176 blocksBeforeCondition: BasicBlock[]; 177 blockBuildersReenterCondition: BlockBuilder[]; 178 blocksReenterCondition: BasicBlock[]; 179 } { 180 const blockBuildersBeforeCondition: BlockBuilder[] = []; 181 const blocksBeforeCondition: BasicBlock[] = []; 182 const blockBuildersReenterCondition: BlockBuilder[] = []; 183 const blocksReenterCondition: BasicBlock[] = []; 184 for (const prevBlockBuilder of conditionBlockBuilder.lasts) { 185 const prevBlock = blockBuilderToCfgBlock.get(prevBlockBuilder) as BasicBlock; 186 if (prevBlock.getId() < blockId) { 187 blockBuildersBeforeCondition.push(prevBlockBuilder); 188 blocksBeforeCondition.push(prevBlock); 189 } else { 190 blockBuildersReenterCondition.push(prevBlockBuilder); 191 blocksReenterCondition.push(prevBlock); 192 } 193 } 194 return { 195 blockBuildersBeforeCondition, 196 blocksBeforeCondition, 197 blockBuildersReenterCondition, 198 blocksReenterCondition, 199 }; 200 } 201 202 private getCollectedBlocks( 203 collectReenter: Boolean, 204 blockBuildersBeforeCondition: BlockBuilder[], 205 blocksBeforeCondition: BasicBlock[], 206 blockBuildersReenterCondition: BlockBuilder[], 207 blocksReenterCondition: BasicBlock[] 208 ): { collectedBlockBuilders: BlockBuilder[]; collectedBlocks: BasicBlock[] } { 209 let collectedBlockBuilders: BlockBuilder[] = []; 210 let collectedBlocks: BasicBlock[] = []; 211 if (collectReenter) { 212 collectedBlockBuilders = blockBuildersReenterCondition; 213 collectedBlocks = blocksReenterCondition; 214 } else { 215 collectedBlockBuilders = blockBuildersBeforeCondition; 216 collectedBlocks = blocksBeforeCondition; 217 } 218 return { collectedBlockBuilders, collectedBlocks }; 219 } 220 221 private createAndLinkBlocks( 222 collectedBlockBuilders: BlockBuilder[], 223 collectedBlocks: BasicBlock[], 224 conditionBlockBuilder: BlockBuilder, 225 stmtsInsertBeforeCondition: Stmt[], 226 block: BasicBlock 227 ): { 228 blockBuilderInsertBeforeCondition: BlockBuilder; 229 blockInsertBeforeCondition: BasicBlock; 230 } { 231 const blockBuilderInsertBeforeCondition = new BlockBuilder(-1, []); 232 blockBuilderInsertBeforeCondition.lasts.push(...collectedBlockBuilders); 233 blockBuilderInsertBeforeCondition.nexts.push(conditionBlockBuilder); 234 const blockInsertBeforeCondition = new BasicBlock(); 235 stmtsInsertBeforeCondition.forEach(stmt => blockInsertBeforeCondition.getStmts().push(stmt)); 236 blockInsertBeforeCondition.getPredecessors().push(...collectedBlocks); 237 blockInsertBeforeCondition.addSuccessorBlock(block); 238 return { blockBuilderInsertBeforeCondition, blockInsertBeforeCondition }; 239 } 240 241 private updatePredecessors( 242 collectedBlockBuilders: BlockBuilder[], 243 blockBuilderToCfgBlock: Map<BlockBuilder, BasicBlock>, 244 conditionBlockBuilder: BlockBuilder, 245 blockBuilderInsertBeforeCondition: BlockBuilder, 246 blockInsertBeforeCondition: BasicBlock 247 ): void { 248 for (const prevBlockBuilder of collectedBlockBuilders) { 249 const prevBlock = blockBuilderToCfgBlock.get(prevBlockBuilder) as BasicBlock; 250 for (let j = 0; j < prevBlockBuilder.nexts.length; j++) { 251 if (prevBlockBuilder.nexts[j] === conditionBlockBuilder) { 252 prevBlockBuilder.nexts[j] = blockBuilderInsertBeforeCondition; 253 prevBlock.setSuccessorBlock(j, blockInsertBeforeCondition); 254 break; 255 } 256 } 257 } 258 } 259 260 private getNewPrevBlocks( 261 collectReenter: Boolean, 262 blockBuildersBeforeCondition: BlockBuilder[], 263 blocksBeforeCondition: BasicBlock[], 264 blockBuilderInsertBeforeCondition: BlockBuilder, 265 blockInsertBeforeCondition: BasicBlock, 266 blockBuildersReenterCondition: BlockBuilder[], 267 blocksReenterCondition: BasicBlock[] 268 ): { 269 newPrevBlockBuildersBeforeCondition: BlockBuilder[]; 270 newPrevBlocksBeforeCondition: BasicBlock[]; 271 } { 272 let newPrevBlockBuildersBeforeCondition: BlockBuilder[] = []; 273 let newPrevBlocksBeforeCondition: BasicBlock[] = []; 274 if (collectReenter) { 275 newPrevBlockBuildersBeforeCondition = [...blockBuildersBeforeCondition, blockBuilderInsertBeforeCondition]; 276 newPrevBlocksBeforeCondition = [...blocksBeforeCondition, blockInsertBeforeCondition]; 277 } else { 278 newPrevBlockBuildersBeforeCondition = [blockBuilderInsertBeforeCondition, ...blockBuildersReenterCondition]; 279 newPrevBlocksBeforeCondition = [blockInsertBeforeCondition, ...blocksReenterCondition]; 280 } 281 return { 282 newPrevBlockBuildersBeforeCondition, 283 newPrevBlocksBeforeCondition, 284 }; 285 } 286 287 private updateConditionBlockBuilder( 288 conditionBlockBuilder: BlockBuilder, 289 newPrevBlockBuildersBeforeCondition: BlockBuilder[], 290 block: BasicBlock, 291 newPrevBlocksBeforeCondition: BasicBlock[] 292 ): void { 293 conditionBlockBuilder.lasts = newPrevBlockBuildersBeforeCondition; 294 const predecessorsCnt = block.getPredecessors().length; 295 block.getPredecessors().splice(0, predecessorsCnt, ...newPrevBlocksBeforeCondition); 296 } 297 298 private finalizeInsertion( 299 blockBuilderInsertBeforeCondition: BlockBuilder, 300 blockInsertBeforeCondition: BasicBlock, 301 basicBlockSet: Set<BasicBlock>, 302 blockBuilderToCfgBlock: Map<BlockBuilder, BasicBlock>, 303 blockBuilders: BlockBuilder[] 304 ): void { 305 blockBuilders.push(blockBuilderInsertBeforeCondition); 306 basicBlockSet.add(blockInsertBeforeCondition); 307 blockBuilderToCfgBlock.set(blockBuilderInsertBeforeCondition, blockInsertBeforeCondition); 308 } 309 310 private findIteratorIdx(stmts: Stmt[]): { 311 ifStmtIdx: number; 312 iteratorNextStmtIdx: number; 313 dummyInitializerStmtIdx: number; 314 } { 315 let ifStmtIdx = -1; 316 let iteratorNextStmtIdx = -1; 317 let dummyInitializerStmtIdx = -1; 318 const stmtsCnt = stmts.length; 319 for (let i = 0; i < stmtsCnt; i++) { 320 const stmt = stmts[i]; 321 if (stmt instanceof ArkAssignStmt && stmt.getRightOp() instanceof AbstractInvokeExpr) { 322 const invokeExpr = stmt.getRightOp() as AbstractInvokeExpr; 323 if (invokeExpr.getMethodSignature().getMethodSubSignature().getMethodName() === Builtin.ITERATOR_NEXT) { 324 iteratorNextStmtIdx = i; 325 continue; 326 } 327 } 328 if (stmt.toString() === ArkIRTransformer.DUMMY_LOOP_INITIALIZER_STMT) { 329 dummyInitializerStmtIdx = i; 330 continue; 331 } 332 if (stmt instanceof ArkIfStmt) { 333 ifStmtIdx = i; 334 break; 335 } 336 } 337 return { 338 ifStmtIdx: ifStmtIdx, 339 iteratorNextStmtIdx: iteratorNextStmtIdx, 340 dummyInitializerStmtIdx: dummyInitializerStmtIdx, 341 }; 342 } 343 344 private adjustIncrementorStmts( 345 stmts: Stmt[], 346 ifStmtIdx: number, 347 currBlockBuilder: BlockBuilder, 348 currBlockId: number, 349 blockBuilderToCfgBlock: Map<BlockBuilder, BasicBlock>, 350 blocksContainLoopCondition: Set<BlockBuilder>, 351 basicBlockSet: Set<BasicBlock>, 352 emptyLoopBody: boolean, 353 blockBuilders: BlockBuilder[] 354 ): void { 355 const stmtsReenterCondition = stmts.slice(ifStmtIdx + 1); 356 if (emptyLoopBody) { 357 const incrementorBlockBuilder = new BlockBuilder(-1, []); 358 incrementorBlockBuilder.lasts.push(currBlockBuilder); 359 currBlockBuilder.nexts[0] = incrementorBlockBuilder; 360 incrementorBlockBuilder.nexts.push(currBlockBuilder); 361 currBlockBuilder.lasts[1] = incrementorBlockBuilder; 362 const incrementorBlock = new BasicBlock(); 363 blockBuilderToCfgBlock.set(incrementorBlockBuilder, incrementorBlock); 364 stmtsReenterCondition.forEach(stmt => incrementorBlock.getStmts().push(stmt)); 365 const currBlock = blockBuilderToCfgBlock.get(currBlockBuilder) as BasicBlock; 366 incrementorBlock.getPredecessors().push(currBlock); 367 currBlock.setPredecessorBlock(1, incrementorBlock); 368 incrementorBlock.addSuccessorBlock(currBlock); 369 currBlock.setSuccessorBlock(0, incrementorBlock); 370 basicBlockSet.add(incrementorBlock); 371 return; 372 } 373 374 const blockBuildersReenterCondition: BlockBuilder[] = []; 375 for (const prevBlockBuilder of currBlockBuilder.lasts) { 376 const prevBlock = blockBuilderToCfgBlock.get(prevBlockBuilder) as BasicBlock; 377 378 if (prevBlock.getId() > currBlockId) { 379 blockBuildersReenterCondition.push(prevBlockBuilder); 380 } 381 } 382 383 if (blockBuildersReenterCondition.length > 1 || blocksContainLoopCondition.has(blockBuildersReenterCondition[0])) { 384 // put incrementor statements into an extra block 385 this.insertBeforeConditionBlockBuilder(blockBuilderToCfgBlock, currBlockBuilder, stmtsReenterCondition, true, basicBlockSet, blockBuilders); 386 } else { 387 // put incrementor statements into prev reenter block 388 const blockReenterCondition = blockBuilderToCfgBlock.get(blockBuildersReenterCondition[0]) as BasicBlock; 389 stmtsReenterCondition.forEach(stmt => blockReenterCondition?.getStmts().push(stmt)); 390 } 391 } 392} 393