Sparse Iteration Conditional Constant Propagation in the Sea of Nodes

Conditional constant propagation is a compiler optimization that computes constant values for expressions in the input program and detects certain unreachable branches. It uses a data flow analysis that traverses the program’s control flow graph to discover instructions that produce constant values. In this paper we document work currently in progress to adapt conditional constant propagation to the Sea of Nodes program representation. In the Sea of Nodes, the program is represented as a graph in which most nodes ‘float’ and are only restricted by data flow edges. Classical data flow anal- ysis is not possible in this setting because most operations are not ordered and not assigned to basic blocks. We present a novel approach to data flow analysis opti- mized for the Sea of Nodes. The analysis starts from known constant nodes in the graph and propagates information di- rectly along data flow edges. Most nodes in the graph can never contribute new constants and are therefore never vis- ited, a property we call sparse iteration. Dependences on control flow are taken into account by ordering SSA 𝜙-nodes according to a carefully defined priority metric. Our analysis is implemented in the GraalVM compiler. Experiments on the Renaissance benchmark suite show that sparse iteration only visits 20.5 % of all nodes in the graph, while finding new constants leading to an average speedup of 3 % over GraalVM’s optimized baseline.