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 16/** 17 * Generic Data Flow Analysis Framework 18 * 19 * This module provides a generic framework for implementing data flow analyses, 20 * such as Reaching Definitions, Live Variables, and Available Expressions. 21 * The framework is designed to be flexible and extensible, allowing users to 22 * define custom flow graphs, transfer functions, and meet operations. 23 * 24 * Design Notes: 25 * - The framework is designed to be generic and reusable, allowing users to 26 * implement custom data flow analyses by defining appropriate transfer functions 27 * and meet operations. 28 * - The solver uses a worklist algorithm to efficiently compute the MFP solution. 29 * - The analysis can be configured as either forward or backward, depending on 30 * the problem requirements. 31 * 32 */ 33 34/** 35 * Represents a flow graph for data flow analysis. 36 * Provides access to nodes in post-order and reverse post-order, as well as 37 * methods to retrieve successors and predecessors of a given node. 38 * 39 * @template T - The type of nodes in the graph (e.g., node IDs or node objects). 40 */ 41export interface FlowGraph<T> { 42 // Nodes in reverse post-order, which is useful for backward data flow analysis. 43 nodesInReversePostOrder?: T[]; 44 // Nodes in post-order, which is useful for forward data flow analysis. 45 nodesInPostOrder: T[]; 46 // Get precessors of Node t. 47 pred(t: T): T[]; 48 // Get successors of Node t. 49 succ(t: T): T[]; 50} 51 52/** 53 * DS (Data Set) is an interface that defines the basic operations for a data set. 54 * It requires the data set to be iterable, comparable, and countable. 55 */ 56interface DS { 57 /** 58 * Returns an iterator that allows iterating over the elements of the data set. 59 * @returns An iterable iterator over the elements of the data set. 60 */ 61 [Symbol.iterator](): IterableIterator<any>; 62 63 /** 64 * Checks whether the current data set is equal to another data set. 65 */ 66 equals(d: DS): boolean; 67 68 /** 69 * Counts the number of elements in the data set. 70 */ 71 count(): number; 72} 73 74/** 75 * Represents the transfer function used in data flow analysis. 76 * The transfer function computes the output value (out set) of a node 77 * based on its input value (in set) and the node's properties. 78 * 79 * @template Node - The type of nodes in the graph. 80 * @template V - The type of data flow values (e.g., sets, bit vectors). 81 */ 82export interface TransferFunction<Node, V> { 83 /** 84 * Computes the output value for a node based on its input value. 85 * 86 * @param n - The node for which the output value is computed. 87 * @param x - The input value (in set) for the node. 88 * @returns The output value (out set) for the node. 89 */ 90 apply(n: Node, x: V): V; 91} 92 93/** 94 * Represents a data flow problem, encapsulating all the necessary components 95 * for performing data flow analysis, such as the flow graph, transfer function, 96 * meet operation, and initialization configuration. 97 * 98 * @template Node - The type of nodes in the graph. 99 * @template V - The type of data flow values. 100 */ 101export interface DataFlowProblem<Node, V> { 102 /** 103 * The flow graph for the data flow analysis. 104 */ 105 flowGraph: FlowGraph<Node>; 106 /** 107 * The transfer function used to compute out sets from in sets. 108 */ 109 transferFunction: TransferFunction<Node, V>; 110 /** 111 * The meet operation used to combine values from multiple paths (e.g., union or intersection). 112 */ 113 meet: (a: V, b: V) => V; 114 /** 115 * The initialization configuration for in and out sets. 116 */ 117 initIn: Map<Node, V>; 118 initOut: Map<Node, V>; 119 /** 120 * Indicates whether the analysis is forward (true) or backward (false). 121 */ 122 forward: boolean; 123 /** 124 * The empty value used to initialize in and out sets (e.g., an empty set). 125 */ 126 empty: V; 127} 128 129/** 130 * Represents the result of a data flow analysis. 131 * Contains the in and out sets for each node, as well as the corresponding data flow problem. 132 * 133 * @template Node - The type of nodes in the graph. 134 * @template V - The type of data flow values. 135 */ 136export class Solution<Node, V> { 137 in: Map<Node, V>; 138 out: Map<Node, V>; 139 problem: DataFlowProblem<Node, V>; 140 141 constructor(i: Map<Node, V>, out: Map<Node, V>, problem: DataFlowProblem<Node, V>) { 142 this.in = i; 143 this.out = out; 144 this.problem = problem; 145 } 146} 147 148/** 149 * A solver for data flow analysis problems. 150 * Implements forward and backward data flow analysis using a worklist algorithm. 151 * The solver computes the Maximum Fixed Point (MFP) solution, which is a safe 152 * over-approximation of the ideal Meet-Over-All-Paths (MOP) solution. 153 */ 154export class MFPDataFlowSolver { 155 /** 156 * Computes the MFP solution for a forward data flow analysis problem. 157 * 158 * @template Node - The type of nodes in the graph. 159 * @template V - The type of data flow values. 160 * @param problem - The data flow problem to solve. 161 * @returns The solution containing the in and out sets for all nodes. 162 */ 163 calculateMopSolutionForwards<Node, V extends DS>(problem: DataFlowProblem<Node, V>): Solution<Node, V> { 164 let _out: Map<Node, V> = problem.initOut; 165 let _in: Map<Node, V> = problem.initIn; 166 let workList: Node[] = problem.flowGraph.nodesInPostOrder; 167 let newEntries: Set<Node> = new Set(); 168 169 while (workList.length > 0) { 170 newEntries.clear(); 171 workList.forEach(n => { 172 let inSet: V | undefined; 173 const predecessors = problem.flowGraph.pred(n); 174 if (predecessors && predecessors.length > 0) { 175 const predecessorOuts = predecessors.map(pred => _out.get(pred)); 176 inSet = predecessorOuts.reduce((acc, cur) => problem.meet(acc!, cur!), problem.empty); 177 } else { 178 inSet = problem.empty; 179 } 180 181 _in.set(n, inSet!); 182 let old: V | undefined = _out.get(n); 183 let newSet: V = problem.transferFunction.apply(n, inSet!); 184 185 if (!old || old.count() === 0 || !old.equals(newSet)) { 186 _out.set(n, newSet); 187 problem.flowGraph.succ(n).forEach(succ => newEntries.add(succ)); 188 } 189 }); 190 191 workList = [...newEntries]; 192 } 193 194 return new Solution(_in, _out, problem); 195 } 196 197 /** 198 * Computes the MFP solution for a backward data flow analysis problem. 199 * 200 * @template Node - The type of nodes in the graph. 201 * @template V - The type of data flow values. 202 * @param problem - The data flow problem to solve. 203 * @returns The solution containing the in and out sets for all nodes. 204 */ 205 calculateMopSolutionBackwards<Node, T extends DS>(problem: DataFlowProblem<Node, T>): Solution<Node, T> { 206 let _out: Map<Node, T> = problem.initOut; 207 let _in: Map<Node, T> = problem.initIn; 208 let workList: Node[] = problem.flowGraph.nodesInPostOrder; 209 let newEntries: Set<Node> = new Set(); 210 211 while (workList.length > 0) { 212 newEntries.clear(); 213 workList.forEach(n => { 214 let outSet: T = problem.flowGraph.succ(n).reduce((acc, curr) => { 215 return problem.meet(acc, _in.get(curr)!); 216 }, problem.empty); 217 218 _out.set(n, outSet); 219 let old: T | undefined = _in.get(n); 220 let newSet: T = problem.transferFunction.apply(n, outSet); 221 if (!old || !old.equals(newSet)) { 222 _in.set(n, newSet); 223 problem.flowGraph.pred(n).forEach(pred => newEntries.add(pred)); 224 } 225 }); 226 227 workList = [...newEntries]; 228 } 229 230 return new Solution(_in, _out, problem); 231 } 232} 233