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 { ArkIRTransformer, DummyStmt } from '../../common/ArkIRTransformer'; 18import { ArkAssignStmt, Stmt } from '../../base/Stmt'; 19import { Local } from '../../base/Local'; 20import { IRUtils } from '../../common/IRUtils'; 21 22/** 23 * Builder for condition in CFG 24 */ 25export class ConditionBuilder { 26 public rebuildBlocksContainConditionalOperator(basicBlockSet: Set<BasicBlock>, isArkUIBuilder: boolean): void { 27 if (isArkUIBuilder) { 28 this.deleteDummyConditionalOperatorStmt(basicBlockSet); 29 return; 30 } 31 32 const currBasicBlocks = Array.from(basicBlockSet); 33 for (const currBasicBlock of currBasicBlocks) { 34 const stmtsInCurrBasicBlock = Array.from(currBasicBlock.getStmts()); 35 const stmtsCnt = stmtsInCurrBasicBlock.length; 36 let conditionalOperatorEndPos = -1; 37 for (let i = stmtsCnt - 1; i >= 0; i--) { 38 const stmt = stmtsInCurrBasicBlock[i]; 39 if (stmt instanceof DummyStmt && stmt.toString()?.startsWith(ArkIRTransformer.DUMMY_CONDITIONAL_OPERATOR_END_STMT)) { 40 conditionalOperatorEndPos = i; 41 break; 42 } 43 } 44 if (conditionalOperatorEndPos === -1) { 45 continue; 46 } 47 48 let { generatedTopBlock: generatedTopBlock, generatedBottomBlocks: generatedBottomBlocks } = this.generateBlocksContainConditionalOperatorGroup( 49 stmtsInCurrBasicBlock.slice(0, conditionalOperatorEndPos + 1), 50 basicBlockSet 51 ); 52 53 if (conditionalOperatorEndPos !== stmtsCnt - 1) { 54 // need create a new basic block for rest statements 55 const { generatedTopBlock: extraBlock } = this.generateBlockWithoutConditionalOperator( 56 stmtsInCurrBasicBlock.slice(conditionalOperatorEndPos + 1) 57 ); 58 generatedBottomBlocks.forEach(generatedBottomBlock => { 59 generatedBottomBlock.addSuccessorBlock(extraBlock); 60 extraBlock.addPredecessorBlock(generatedBottomBlock); 61 }); 62 basicBlockSet.add(extraBlock); 63 generatedBottomBlocks = this.removeUnnecessaryBlocksInConditionalOperator(extraBlock, basicBlockSet); 64 } 65 this.relinkPrevAndSuccOfBlockContainConditionalOperator(currBasicBlock, generatedTopBlock, generatedBottomBlocks); 66 basicBlockSet.delete(currBasicBlock); 67 } 68 } 69 70 private relinkPrevAndSuccOfBlockContainConditionalOperator( 71 currBasicBlock: BasicBlock, 72 generatedTopBlock: BasicBlock, 73 generatedBottomBlocks: BasicBlock[] 74 ): void { 75 const predecessorsOfCurrBasicBlock = Array.from(currBasicBlock.getPredecessors()); 76 predecessorsOfCurrBasicBlock.forEach(predecessor => { 77 predecessor.removeSuccessorBlock(currBasicBlock); 78 currBasicBlock.removePredecessorBlock(predecessor); 79 generatedTopBlock.addPredecessorBlock(predecessor); 80 predecessor.addSuccessorBlock(generatedTopBlock); 81 }); 82 const successorsOfCurrBasicBlock = Array.from(currBasicBlock.getSuccessors()); 83 successorsOfCurrBasicBlock.forEach(successor => { 84 successor.removePredecessorBlock(currBasicBlock); 85 currBasicBlock.removeSuccessorBlock(successor); 86 generatedBottomBlocks.forEach(generatedBottomBlock => { 87 generatedBottomBlock.addSuccessorBlock(successor); 88 successor.addPredecessorBlock(generatedBottomBlock); 89 }); 90 }); 91 } 92 93 private generateBlocksContainConditionalOperatorGroup( 94 sourceStmts: Stmt[], 95 basicBlockSet: Set<BasicBlock> 96 ): { 97 generatedTopBlock: BasicBlock; 98 generatedBottomBlocks: BasicBlock[]; 99 } { 100 const { firstEndPos: firstEndPos } = this.findFirstConditionalOperator(sourceStmts); 101 if (firstEndPos === -1) { 102 return this.generateBlockWithoutConditionalOperator(sourceStmts); 103 } 104 const { 105 generatedTopBlock: firstGeneratedTopBlock, 106 generatedBottomBlocks: firstGeneratedBottomBlocks, 107 generatedAllBlocks: firstGeneratedAllBlocks, 108 } = this.generateBlocksContainSingleConditionalOperator(sourceStmts.slice(0, firstEndPos + 1)); 109 const generatedTopBlock = firstGeneratedTopBlock; 110 let generatedBottomBlocks = firstGeneratedBottomBlocks; 111 firstGeneratedAllBlocks.forEach(block => basicBlockSet.add(block)); 112 const stmtsCnt = sourceStmts.length; 113 if (firstEndPos !== stmtsCnt - 1) { 114 // need handle other conditional operators 115 const { generatedTopBlock: restGeneratedTopBlock, generatedBottomBlocks: restGeneratedBottomBlocks } = 116 this.generateBlocksContainConditionalOperatorGroup(sourceStmts.slice(firstEndPos + 1, stmtsCnt), basicBlockSet); 117 firstGeneratedBottomBlocks.forEach(firstGeneratedBottomBlock => { 118 firstGeneratedBottomBlock.addSuccessorBlock(restGeneratedTopBlock); 119 restGeneratedTopBlock.addPredecessorBlock(firstGeneratedBottomBlock); 120 }); 121 restGeneratedBottomBlocks.forEach(block => basicBlockSet.add(block)); 122 this.removeUnnecessaryBlocksInConditionalOperator(restGeneratedTopBlock, basicBlockSet); 123 generatedBottomBlocks = restGeneratedBottomBlocks; 124 } 125 return { generatedTopBlock, generatedBottomBlocks }; 126 } 127 128 private generateBlocksContainSingleConditionalOperator(sourceStmts: Stmt[]): { 129 generatedTopBlock: BasicBlock; 130 generatedBottomBlocks: BasicBlock[]; 131 generatedAllBlocks: BasicBlock[]; 132 } { 133 const { firstIfTruePos: ifTruePos, firstIfFalsePos: ifFalsePos, firstEndPos: endPos } = this.findFirstConditionalOperator(sourceStmts); 134 if (endPos === -1) { 135 return this.generateBlockWithoutConditionalOperator(sourceStmts); 136 } 137 const { generatedTopBlock: generatedTopBlock, generatedAllBlocks: generatedAllBlocks } = this.generateBlockWithoutConditionalOperator( 138 sourceStmts.slice(0, ifTruePos) 139 ); 140 let generatedBottomBlocks: BasicBlock[] = []; 141 const { 142 generatedTopBlock: generatedTopBlockOfTrueBranch, 143 generatedBottomBlocks: generatedBottomBlocksOfTrueBranch, 144 generatedAllBlocks: generatedAllBlocksOfTrueBranch, 145 } = this.generateBlocksContainSingleConditionalOperator(sourceStmts.slice(ifTruePos + 1, ifFalsePos)); 146 generatedBottomBlocks.push(...generatedBottomBlocksOfTrueBranch); 147 generatedAllBlocks.push(...generatedAllBlocksOfTrueBranch); 148 const { 149 generatedTopBlock: generatedTopBlockOfFalseBranch, 150 generatedBottomBlocks: generatedBottomBlocksOfFalseBranch, 151 generatedAllBlocks: generatedAllBlocksOfFalseBranch, 152 } = this.generateBlocksContainSingleConditionalOperator(sourceStmts.slice(ifFalsePos + 1, endPos)); 153 generatedBottomBlocks.push(...generatedBottomBlocksOfFalseBranch); 154 generatedAllBlocks.push(...generatedAllBlocksOfFalseBranch); 155 156 generatedTopBlock.addSuccessorBlock(generatedTopBlockOfTrueBranch); 157 generatedTopBlockOfTrueBranch.addPredecessorBlock(generatedTopBlock); 158 generatedTopBlock.addSuccessorBlock(generatedTopBlockOfFalseBranch); 159 generatedTopBlockOfFalseBranch.addPredecessorBlock(generatedTopBlock); 160 const stmtsCnt = sourceStmts.length; 161 if (endPos !== stmtsCnt - 1) { 162 // need create a new basic block for rest statements 163 const { generatedTopBlock: extraBlock } = this.generateBlockWithoutConditionalOperator(sourceStmts.slice(endPos + 1)); 164 generatedBottomBlocks.forEach(generatedBottomBlock => { 165 generatedBottomBlock.addSuccessorBlock(extraBlock); 166 extraBlock.addPredecessorBlock(generatedBottomBlock); 167 }); 168 generatedBottomBlocks = [extraBlock]; 169 generatedAllBlocks.push(extraBlock); 170 } 171 return { generatedTopBlock, generatedBottomBlocks, generatedAllBlocks }; 172 } 173 174 private generateBlockWithoutConditionalOperator(sourceStmts: Stmt[]): { 175 generatedTopBlock: BasicBlock; 176 generatedBottomBlocks: BasicBlock[]; 177 generatedAllBlocks: BasicBlock[]; 178 } { 179 const generatedBlock = new BasicBlock(); 180 sourceStmts.forEach(stmt => generatedBlock.addStmt(stmt)); 181 return { 182 generatedTopBlock: generatedBlock, 183 generatedBottomBlocks: [generatedBlock], 184 generatedAllBlocks: [generatedBlock], 185 }; 186 } 187 188 private deleteDummyConditionalOperatorStmt(basicBlockSet: Set<BasicBlock>): void { 189 for (const basicBlock of basicBlockSet) { 190 const stmts = Array.from(basicBlock.getStmts()); 191 for (const stmt of stmts) { 192 if (stmt instanceof DummyStmt && stmt.toString()?.startsWith(ArkIRTransformer.DUMMY_CONDITIONAL_OPERATOR)) { 193 basicBlock.remove(stmt); 194 } 195 } 196 } 197 } 198 199 private findFirstConditionalOperator(stmts: Stmt[]): { 200 firstIfTruePos: number; 201 firstIfFalsePos: number; 202 firstEndPos: number; 203 } { 204 let firstIfTruePos = -1; 205 let firstIfFalsePos = -1; 206 let firstEndPos = -1; 207 let firstConditionalOperatorNo = ''; 208 for (let i = 0; i < stmts.length; i++) { 209 const stmt = stmts[i]; 210 if (stmt instanceof DummyStmt) { 211 if (stmt.toString().startsWith(ArkIRTransformer.DUMMY_CONDITIONAL_OPERATOR_IF_TRUE_STMT) && firstIfTruePos === -1) { 212 firstIfTruePos = i; 213 firstConditionalOperatorNo = stmt.toString().replace(ArkIRTransformer.DUMMY_CONDITIONAL_OPERATOR_IF_TRUE_STMT, ''); 214 } else if (stmt.toString() === ArkIRTransformer.DUMMY_CONDITIONAL_OPERATOR_IF_FALSE_STMT + firstConditionalOperatorNo) { 215 firstIfFalsePos = i; 216 } else if (stmt.toString() === ArkIRTransformer.DUMMY_CONDITIONAL_OPERATOR_END_STMT + firstConditionalOperatorNo) { 217 firstEndPos = i; 218 } 219 } 220 } 221 return { firstIfTruePos, firstIfFalsePos, firstEndPos }; 222 } 223 224 private removeUnnecessaryBlocksInConditionalOperator(bottomBlock: BasicBlock, allBlocks: Set<BasicBlock>): BasicBlock[] { 225 const firstStmtInBottom = bottomBlock.getStmts()[0]; 226 if (!(firstStmtInBottom instanceof ArkAssignStmt)) { 227 return [bottomBlock]; 228 } 229 230 const targetValue = firstStmtInBottom.getLeftOp(); 231 const tempResultValue = firstStmtInBottom.getRightOp(); 232 if (!(targetValue instanceof Local && IRUtils.isTempLocal(tempResultValue))) { 233 return [bottomBlock]; 234 } 235 const oldPredecessors = Array.from(bottomBlock.getPredecessors()); 236 const newPredecessors: BasicBlock[] = []; 237 for (const predecessor of oldPredecessors) { 238 predecessor.removeSuccessorBlock(bottomBlock); 239 newPredecessors.push(...this.replaceTempRecursively(predecessor, targetValue as Local, tempResultValue as Local, allBlocks)); 240 } 241 242 bottomBlock.remove(firstStmtInBottom); 243 if (bottomBlock.getStmts().length === 0) { 244 // must be a new block without successors 245 allBlocks.delete(bottomBlock); 246 return newPredecessors; 247 } 248 249 oldPredecessors.forEach(oldPredecessor => { 250 bottomBlock.removePredecessorBlock(oldPredecessor); 251 }); 252 newPredecessors.forEach(newPredecessor => { 253 bottomBlock.addPredecessorBlock(newPredecessor); 254 newPredecessor.addSuccessorBlock(bottomBlock); 255 }); 256 return [bottomBlock]; 257 } 258 259 private replaceTempRecursively(currBottomBlock: BasicBlock, targetLocal: Local, tempResultLocal: Local, allBlocks: Set<BasicBlock>): BasicBlock[] { 260 const stmts = currBottomBlock.getStmts(); 261 const stmtsCnt = stmts.length; 262 let tempResultReassignStmt: Stmt | null = null; 263 for (let i = stmtsCnt - 1; i >= 0; i--) { 264 const stmt = stmts[i]; 265 if (stmt instanceof ArkAssignStmt && stmt.getLeftOp() === tempResultLocal) { 266 if (IRUtils.isTempLocal(stmt.getRightOp())) { 267 tempResultReassignStmt = stmt; 268 } else { 269 stmt.setLeftOp(targetLocal); 270 } 271 } 272 } 273 274 let newBottomBlocks: BasicBlock[] = []; 275 if (tempResultReassignStmt) { 276 const oldPredecessors = currBottomBlock.getPredecessors(); 277 const newPredecessors: BasicBlock[] = []; 278 const prevTempResultLocal = (tempResultReassignStmt as ArkAssignStmt).getRightOp() as Local; 279 for (const predecessor of oldPredecessors) { 280 predecessor.removeSuccessorBlock(currBottomBlock); 281 newPredecessors.push(...this.replaceTempRecursively(predecessor, targetLocal, prevTempResultLocal, allBlocks)); 282 } 283 284 currBottomBlock.remove(tempResultReassignStmt); 285 if (currBottomBlock.getStmts().length === 0) { 286 // remove this block 287 newBottomBlocks = newPredecessors; 288 allBlocks.delete(currBottomBlock); 289 } else { 290 currBottomBlock.getPredecessors().splice(0, oldPredecessors.length, ...newPredecessors); 291 newPredecessors.forEach(newPredecessor => { 292 newPredecessor.addSuccessorBlock(currBottomBlock); 293 }); 294 newBottomBlocks = [currBottomBlock]; 295 } 296 } else { 297 newBottomBlocks = [currBottomBlock]; 298 } 299 return newBottomBlocks; 300 } 301} 302