Live Variable Analysis(LVA) is to determine the set of variables that are live at some point in a program. The classical approaches for computing LVA use iterative algorithms across the entire programs based on the Data Flow Analysis(DFA) framework. In case of Zephyr compiler, average execution time of LVA takes 7% of the compilation time for the benchmark programs. So, faster LVA computation is crucial to reduce the total compilation time.
The classical LVA algorithm has many aspects for improvement. The iterative algorithm for LVA scans useless basic blocks and claculates large sets of variables repeatedly. These overheads can be reduced by marking visited basic blocks and calculating sets based on adjoin operation.
We propose the non-iterative algorithm for LVA based on used variables’ upward movement. Our algorithm produces the same result as the previous iterative algorithm. It is based on use-def chain. Variables are added to live variable sets of all basic blocks on the paths from used point to defined points with backward traversal of control-flow graph(CFG). The iterative algorithms updates the used variable sets of only directly connected basic blocks. But in our algorithm, each used variable affects all the basic blocks that the variable is live rather than directly connected ones. This process reduces the number of visiting basic blocks, which improves overall processing time. Experimental results say that our algorithm can reduce 36.4% of LVA excution time and 2.6% of overall computation time in Zephyr compiler with benchmark programs.
