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 { DominanceFinder } from './DominanceFinder'; 18 19export class DominanceTree { 20 private blocks: BasicBlock[] = []; 21 private blockToIdx = new Map<BasicBlock, number>(); 22 private children: number[][] = []; 23 private parents: number[] = []; 24 25 constructor(dominanceFinder: DominanceFinder) { 26 this.blocks = dominanceFinder.getBlocks(); 27 this.blockToIdx = dominanceFinder.getBlockToIdx(); 28 let idoms = dominanceFinder.getImmediateDominators(); 29 30 // build the tree 31 let treeSize = this.blocks.length; 32 this.children = new Array(treeSize); 33 this.parents = new Array(treeSize); 34 for (let i = 0; i < treeSize; i++) { 35 this.children[i] = []; 36 this.parents[i] = -1; 37 } 38 for (let i = 0; i < treeSize; i++) { 39 if (idoms[i] !== i) { 40 this.parents[i] = idoms[i]; 41 this.children[idoms[i]].push(i); 42 } 43 } 44 } 45 46 public getAllNodesDFS(): BasicBlock[] { 47 let dfsBlocks = new Array<BasicBlock>(); 48 let queue = new Array<BasicBlock>(); 49 queue.push(this.getRoot()); 50 while (queue.length !== 0) { 51 let curr = queue.splice(0, 1)[0]; 52 dfsBlocks.push(curr); 53 let childList = this.getChildren(curr); 54 if (childList.length !== 0) { 55 for (let i = childList.length - 1; i >= 0; i--) { 56 queue.splice(0, 0, childList[i]); 57 } 58 } 59 } 60 return dfsBlocks; 61 } 62 63 public getChildren(block: BasicBlock): BasicBlock[] { 64 let childList = new Array<BasicBlock>(); 65 let idx = this.blockToIdx.get(block) as number; 66 for (const i of this.children[idx]) { 67 childList.push(this.blocks[i]); 68 } 69 return childList; 70 } 71 72 public getRoot(): BasicBlock { 73 return this.blocks[0]; 74 } 75} 76