.png){kind=icon}
.png){kind=icon}
Return
More precise construction of static single assignment programs using reaching definitions
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jss.2020.110590.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Static Single Assignment (SSA) form is an intermediate representation used for the analysis and optimization of programs in modern compilers. The phi-function placement is the most computationally expensive part of converting any program into its SSA form. The most widely-used phi-function placement algorithms are based on computing dominance frontiers (DF). However, this kind of algorithms works under the limiting assumption that all variables are defined at the beginning of the program, which is not the case for local variables. In this paper, we introduce an innovative phi-placement algorithm based on computing reaching definitions (RD), which generates a precise number of phi-functions. We provided theorems and proofs showing the correctness and the theoretical computational complexity of our algorithms. We implemented our approach and a well-known DF-based algorithm in the Clang/LLVM compiler framework, and performed experiments on a number of benchmarks. The results show that the limiting assumption of the DF-based algorithm when compared with the more accurate results of our RD-based approach leads to generating up to 87% (69% on average) superfluous phi-functions on all benchmarks, and thus brings about a significant precision loss. Moreover, even though our approach computes more information to generate precise results, it is able to analyze up to 92.96% procedures (65.63% on average) of all benchmarks with execution time within twice the execution time of the reference DF-based approach. (C) 2020 Elsevier Inc. All rights reserved.
Keywords:
Static single assignment
Program optimization
Program transformation
Reaching definition
Dataflow analysis
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.1
Papers:
5.4K
Citations:
8.4K