Fast Predicate-Aware Dataflow Analysis
Original Publication Date: 2003-Jun-26
Included in the Prior Art Database: 2003-Jun-26
Predication using Boolean operand guards reduces the overhead of the conditional branches and enhances code optimization, but dataflow analysis for predicated code cannot find accurate results without any predication knowledge. We propose a fast algorithm for predicate-aware dataflow analysis. We first compute the reachability information using bitvectors for sets of adjacent instructions sharing the same predicate register to handle multiple paths efficiently. We then perform the dataflow analysis by propagating the properties using the reachability information. We implemented our algorithm and demonstrated that register allocation using our technique is 2.59 times as fast as that using the PQS-based approach.