|
Abstract : |
The classical dataflow approach to determine the set of variables that are live at some point in a program entails using an iterative algorithm across the entire program, usually with costly bitvector data structures. Methods based on sparse evaluation graphs exist, but these are solved on a per-variable basis and are also iterative. Inspired by our group's interest in sparse representations of use-def and def-use reference chains, we are investigating still another approach. In this paper, we present an algorithm for determining liveness of variables based on upwards exposed use information at control flow branch points, analogous to the collection of reaching definition information in the popular Static Single Assignment form. We demonstrate the use of our technique with two applications, building interference graphs and eliminating dead code, and show that this new reference chain approach has important advantages over previous methods., |
