1/* 2 * Copyright (c) 2024-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 { Cfg } from './Cfg'; 18 19export class DominanceFinder { 20 private blocks: BasicBlock[] = []; 21 private blockToIdx = new Map<BasicBlock, number>(); 22 private idoms: number[] = []; 23 private domFrontiers: number[][] = []; 24 25 constructor(cfg: Cfg) { 26 this.blocks = Array.from(cfg.getBlocks()); 27 for (let i = 0; i < this.blocks.length; i++) { 28 let block = this.blocks[i]; 29 this.blockToIdx.set(block, i); 30 } 31 const startingBlock = cfg.getStartingBlock(); 32 33 // calculate immediate dominator for each block 34 this.idoms = new Array<number>(this.blocks.length); 35 this.idoms[0] = 0; 36 for (let i = 1; i < this.idoms.length; i++) { 37 this.idoms[i] = -1; 38 } 39 let isChanged = true; 40 while (isChanged) { 41 isChanged = false; 42 for (const block of this.blocks) { 43 if (block === startingBlock) { 44 continue; 45 } 46 let blockIdx = this.blockToIdx.get(block) as number; 47 let preds = Array.from(block.getPredecessors()); 48 let newIdom = this.getFirstDefinedBlockPredIdx(preds); 49 if (preds.length <= 0 || newIdom === -1) { 50 continue; 51 } 52 for (const pred of preds) { 53 let predIdx = this.blockToIdx.get(pred) as number; 54 this.idoms[predIdx] !== -1 ? (newIdom = this.intersect(newIdom, predIdx)) : null; 55 } 56 if (this.idoms[blockIdx] !== newIdom) { 57 this.idoms[blockIdx] = newIdom; 58 isChanged = true; 59 } 60 } 61 } 62 63 // calculate dominance frontiers for each block 64 this.domFrontiers = new Array(this.blocks.length); 65 for (let i = 0; i < this.domFrontiers.length; i++) { 66 this.domFrontiers[i] = new Array<number>(); 67 } 68 for (const block of this.blocks) { 69 let preds = Array.from(block.getPredecessors()); 70 if (preds.length <= 1) { 71 continue; 72 } 73 let blockIdx = this.blockToIdx.get(block) as number; 74 for (const pred of preds) { 75 let predIdx = this.blockToIdx.get(pred) as number; 76 while (predIdx !== this.idoms[blockIdx]) { 77 this.domFrontiers[predIdx].push(blockIdx); 78 predIdx = this.idoms[predIdx]; 79 } 80 } 81 } 82 } 83 84 public getDominanceFrontiers(block: BasicBlock): Set<BasicBlock> { 85 if (!this.blockToIdx.has(block)) { 86 throw new Error('The given block: ' + block + ' is not in Cfg!'); 87 } 88 let idx = this.blockToIdx.get(block) as number; 89 let dfs = new Set<BasicBlock>(); 90 let dfsIdx = this.domFrontiers[idx]; 91 for (const dfIdx of dfsIdx) { 92 dfs.add(this.blocks[dfIdx]); 93 } 94 return dfs; 95 } 96 97 public getBlocks(): BasicBlock[] { 98 return this.blocks; 99 } 100 101 public getBlockToIdx(): Map<BasicBlock, number> { 102 return this.blockToIdx; 103 } 104 105 public getImmediateDominators(): number[] { 106 return this.idoms; 107 } 108 109 private getFirstDefinedBlockPredIdx(preds: BasicBlock[]): number { 110 for (const block of preds) { 111 let idx = this.blockToIdx.get(block) as number; 112 if (this.idoms[idx] !== -1) { 113 return idx; 114 } 115 } 116 return -1; 117 } 118 119 private intersect(a: number, b: number): number { 120 while (a !== b) { 121 if (a > b) { 122 a = this.idoms[a]; 123 } else { 124 b = this.idoms[b]; 125 } 126 } 127 return a; 128 } 129} 130