Non-Iterative liveness analysis for SSA based gimple descriptions. More...

#include "NI_SSA_liveness.hpp"
#include "application_manager.hpp"
#include "behavioral_helper.hpp"
#include "function_behavior.hpp"
#include "Parameter.hpp"
#include <fstream>
#include "dbgPrintHelper.hpp"
#include "string_manipulation.hpp"
#include "tree_basic_block.hpp"
#include "tree_helper.hpp"
#include "tree_manager.hpp"
#include "tree_reindex.hpp"

Include dependency graph for NI_SSA_liveness.cpp:

Go to the source code of this file.

Detailed Description

Non-Iterative liveness analysis for SSA based gimple descriptions.

Compute the liveness sets by exploring paths from variable use (Algorithm 4 and 5). Details of the algorithm can be found in the following technical report:

Florian Brandner, Benoit Boissinot, Alain Darte, Benoît Dupont de Dinechin, Fabrice Rastello "Computing Liveness Sets for SSA-Form Programs", inria-00558509, version 2

{BRANDNER:2011:INRIA-00558509:2, hal_id = {inria-00558509}, url = {http://hal.inria.fr/inria-00558509}, title = {{Computing Liveness Sets for SSA-Form Programs}}, author = {Brandner, Florian and Boissinot, Benoit and Darte, Alain and Dupont De Dinechin, Beno{\^}t and Rastello, Fabrice}, abstract = {{We revisit the problem of computing liveness sets, i.e., the set of variables live-in and live-out of basic blocks, for programs in strict SSA (static single assignment). Strict SSA is also known as SSA with dominance property because it ensures that the definition of a variable always dominates all its uses. This property can be exploited to optimize the computation of liveness sets. Our first contribution is the design of a fast data-flow algorithm, which, unlike traditional approaches, avoids the iterative calculation of a fixed point. Thanks to the properties of strict SSA form and the use of a loop-nesting forest, we show that two passes are sufficient. A first pass, similar to the initialization of iterative data-flow analysis, traverses the control-flow graph in postorder propagating liveness information backwards. A second pass then traverses the loop-nesting forest, updating liveness information within loops. Another approach is to propagate from uses to definition, one variable and one path at a time, instead of unioning sets as in standard data-flow analysis. Such a path-exploration strategy was proposed by Appel in his ''Tiger book'' and is also used in the LLVM compiler. Our second contribution is to show how to extend and optimize algorithms based on this idea to compute liveness sets one variable at a time using adequate data

Definition in file NI_SSA_liveness.cpp.