holloway@deas.harvard.edu

Division of Engineering and Applied Sciences

Harvard University

Revised May 2, 1998

- Introduction
- Class bit_vector_problem
- Class bit_vector_problem_plus
- Live Variable Analysis
- Unset Variable Analysis
- Mapping Registers and Symbols to Bit-vector Indices
- Boolean Bitset Functions
- Connecting to the DFA Library
- Likely Extensions of the DFA Library
- Acknowledgments
- References
- Indecent Exposure

Data flow analysis (DFA) is a textbook example of code reuse
**[cite bibdragon, bibcrafting]**. Available expressions, or live
variables, or reaching definitions, or other useful sets of properties
can be computed for all points in a program using a generic
algorithmic framework. Typically, the property sets are represented
as bit vectors, and the generic algorithm propagates them iteratively
over a flow graph, transforming them monotonically to reflect the
effects of basic blocks and the confluence of edges, until they
converge at all points. Different problems have different initial
conditions for the bit vectors (empty or full), different confluence
transformations (union or intersection), different directions of
traversal (with control flow or against it), and different rules for
expressing the effects of a basic block. But the fact that their
solvers fit a common pattern is useful, because once the framework is
in place, it enables new analyzers to be added quickly and correctly.

The DFA library of machine SUIF **[cite bibmachsuif]** (*machsuif*, for
short) is a framework for iterative, bit-vector-based data flow analyzers.
It builds on machine SUIF's control flow graph (CFG) library **[cite bibcfg]**,
but without the need to alter or extend the CFG classes. Each specific
data flow solver is derived from an abstract `bit_vector_problem`

class,
which incorporates the generic machinery.
Section [->] describes this class. For now, the DFA
library contains just one solver, which computes live variables. The
interfaces of this liveness analyzer and its related utilities are
described in Section [->]. Section [->]
gives directions for incorporating the library in SUIF compiler passes, and
Section [->] discusses likely directions for its extension.

`bit_vector_problem`

The `bit_vector_problem`

class is a parent class for
bit-vector-based DFA problems. It was modeled after a similar class
originally implemented by Steve Tjiang of Synopsys and Prof.
Todd Mowry's students at the University of Toronto. Here is its
declaration:

<class`bit_vector_problem`

>=(U->)const int INFINITY = 0x7fffffff; enum DFA_direction_type { forward, backward }; class bit_vector_problem { private: DFA_direction_type dfa_dir; protected: cfg *the_cfg; DFA_direction_type direction() { return dfa_dir; } virtual void build_sets() = 0; virtual boolean solver_ops(cfg_node *n) = 0; public: bit_vector_problem(DFA_direction_type dir, cfg *graph); boolean solve(int iteration_limit = INFINITY); };

This class is abstract; a particular data flow analyzer is created by
deriving a subclass of it. The abstract class is explicitly parameterized
by the two arguments of its constructor: the direction (`forward`

or
`backward`

) of bit-vector propagation and the CFG of the program to be
analyzed. The iterative propagation algorithm is defined by method
`solve(iteration_limit)`

, which returns true unless it reaches
`iteration_limit`

traversals of the CFG before the analysis converges.

The `bit_vector_problem`

class above is also implicitly parameterized by
its two pure virtual methods:

`build_sets()`

must initialize the bit vectors for the graph, and it should represent the effect of each node so that the solving phase can combine bit vectors, without having to inspect code.`solver_ops(cfg_node *n)`

finds and combines the bit vectors of nodes impinging on`n`

and then propagates the result through`n`

using its precomputed effect description. These two aspects of`solver_ops`

's role are sometimes called*confluence*and*transfer*, respectively. It also detects whether propagation has produced any change in`n`

's attached properties. If so, it returns true; otherwise, false.

`bit_vector_problem`

dictates the way that
properties are associated with CFG nodes. Property sets even don't
need to be vectors of bits. However, Section [->]
defines a simple scheme for connecting bit vectors with CFG nodes, and this
is likely to be useful for most analyzers.
Class `bit_vector_problem`

resides in module `bit_vector_dfa`

, which
has the following header file.

<bit_vector_dfa.h>= /* Bit-vector-based dataflow analysis problems */<SUIF copyright>#ifndef BIT_VECTOR_DFA_H #define BIT_VECTOR_DFA_H<class#endif /* BIT_VECTOR_DFA_H */`bit_vector_problem`

>

`bit_vector_problem_plus`

The `bit_vector_problem_plus`

class is an attempt to replace
`bit_vector_problem`

for bit-vector-based DFA problems.

- It adds functionality for initializing bit sets.
- It adds standard functionality for handling splits or joins in the CFG.
- It only asks the user to supply Gen and Kill iterators over (presumably) small sets. And walks each block once.

<class`bit_vector_problem_plus`

>=(U->)<class bit_vector_problem_plus { private:`bit_vector_problem_plus`

enum><protected:`bit_vector_problem_plus`

private><public: bit_vector_problem_plus( DFA_direction_type dir, DFA_transfer at_each_instr, DFA_propagation propagation, DFA_keep_info needed_later, int bitset_size, cfg* the_cfg, bitset_function* entry_xfer_fn = NULL, bitset_function* exit_xfer_fn = NULL ); virtual ~bit_vector_problem_plus(); bit_set* in_set(cfg_node* basic_block); boolean in_set_contains(cfg_node* basic_block, int bit_num); bit_set* out_set(cfg_node* basic_block); boolean out_set_contains(cfg_node* basic_block, int bit_num); boolean solve(int iteration_limit = INFINITY); virtual void update_bit_set_size(int); void update_bit_set_for_instr(bit_set*,instruction*); void print(cfg_node* bb, FILE *fp = stdout); // debugging only };`bit_vector_problem_plus`

protected>

This is an attempt to parameterize the `bit_vector_problem`

class
so that a particular bit vector analysis can be defined using just
some parameters to the definition of a `bit_vector_problem`

and the
actual per instruction generation of appropriate gen and kill sets for
the analysis. It allows the user to override its standard behavior to
provide special functions for special cases, but if you find yourself
providing too many special functions, then you probably want to write
your own subclass of `bit_vector_problem`

.

The parameters are as follows:

`dir`

: the direction of the bit vector problem: either`forward`

following edges in the control flow direction from the`ENTRY`

node or`backward`

following edges in reverse from the`EXIT`

node.<

`bit_vector_problem_plus`

enum>=**(<-U)****[D->]**/* enum DFA_direction_type { forward, backward }; // defined in bit_vector_dfa.h */`at_each_instr`

: the transfer operation to be performed at each instructionin the basic block is either`S``standard_t`

which will cause the calculation of

where*out[*`S`] =in[`S`] - kill[`S`] gen[`S`]*in*and*out*depend to the direction of the problem.If you set this to

`special_t`

then you are responsible for overriding virtual method`special_transfer`

which takes a pointer to a`bitset_function*`

and updates the`bitset_function*`

as needed for the instruction. !!! oops pass instruction* !!!If

`standard_t`

is used, then you must write methods`gen_iterator_init`

,`gen_iterator`

,`kill_iterator_init`

, and`kill_iterator`

. The`_init`

methods indicate the beginning of iteration, they should set up any information necessary for the iterator. The`_iterator`

functions return either positive bit numbers for use in the`gen`

or`kill`

sets, or a negative number to indicate the end of iteration. See the`protected`

methods for more information.<

`bit_vector_problem_plus`

enum>+=**(<-U)****[<-D->]**enum DFA_transfer { standard_t, special_t };`propagation`

: If`propagation`

is`isect_p`

then for a block.`B`

If*in[*`B`] = _`P`**in**pred(`B`)out[`P`]`propagation`

is`union_p`

then for a block.`B`

where*in[*`B`] = _`P`**in**pred(`B`)out[`P`]*in*,*out*, and*pred*depend to the direction of the problem.If

`propagation`

is`special_p`

then you must supply a function`special_propagation`

which takes a`cfg_node_list_iter*`

and produces the*in[*`B`]`bit_set`

. !!! Oops, hook this up to our out sets!!!<

`bit_vector_problem_plus`

enum>+=**(<-U)****[<-D->]**enum DFA_propagation { isect_p, union_p, special_p };- Special treatment of
`entry`

and`exit`

nodes: By default`bit_map_problem_plus`

sets the transfer functions for the`entry`

and`exit`

nodes of the cfg to the identity function.It also sets the following values:

direction propagation sets value `forward`

`isect_p`

*in[*`E`NTRY]`universal`

`forward`

`union_p`

*in[*`E`NTRY]`clear`

`backward`

`isect_p`

*in[*`E`XIT]`universal`

`backward`

`union_p`

*in[*`E`XIT]`clear`

You can use

`entry_xfer_fn`

and`exit_xfer_fn`

to set transfer functions more appropriate to yout particular problem. `needed_later`

: Remember that the term`in`

in this code refers to the bit set of dataflow values at the end of the block*entered*by the dataflow analysis: which will be the top of the block for a`forward`

analysis and will be the bottom of the block for a`backward`

analysis.Your transformation will generally require the

`in`

data, wo you will want to set`needed_later`

to`in_k`

. But`out`

data may be saved with`out_k`

and both may be saved with`both_k`

.<

`bit_vector_problem_plus`

enum>+=**(<-U)****[<-D->]**enum DFA_keep_info { in_k, out_k, both_k };

`solve`

-- why not immediately: don't create bitsets before needed by user.<

`bit_vector_problem_plus`

enum>+=**(<-U)****[<-D]**/* const int INFINITY = 0x7fffffff; // defined in bit_vector_dfa.h */`in_set`

-- direction of analysis`in_set_contains`

`out_set`

`out_set_contains`

`update_bit_set_for_instr`

-- doesn't propagate across blocks, use`solve`

again if needed. After creating a`bit_vector_problem_plus`

Note that nothing in class `bit_vector_problem_plus`

dictates the
way that properties are associated with CFG nodes. However our
implementation uses the following storage:

- a
`bitset_function`

for each basic block in the CFG, during`solve`

. - a
`bit_set`

`in`

for each basic block, from`solve`

until the`bit_vector_problem_plus`

object is deleted. (Assuming`needed_later`

*=*`in_k`

). - a bit set
`out`

for each edge in the CFG, during`solve`

. (assuming`needed_later`

`out_k`

or`both_k`

).

The protected members of `bit_vector_problem_plus`

are declared:

<`bit_vector_problem_plus`

protected>=(<-U)int bitset_size; virtual void gen_iterator_init(instruction*) = 0; virtual int gen_iterator() = 0; virtual void kill_iterator_init(instruction*) = 0; virtual int kill_iterator() = 0; cfg* the_cfg; bitset_function* entry_xfer_fn; bitset_function* exit_xfer_fn; virtual bit_set* special_propagation(cfg_node_list_iter*); virtual void special_transfer(bitset_function*); DFA_direction_type direction; DFA_propagation propagation; DFA_transfer transfer; DFA_keep_info needed_later; void Delete_DFAP_bit_set_array(DFAP_bit_set_array*); void Delete_DFAP_bitset_function_array(DFAP_bitset_function_array*);

- Helper functions
`void Delete_DFAP_bit_set_array(DFAP_bit_set_array*)`

and`void Delete_DFAP_bitset_function_array(DFAP_bitset_function_array*)`

`protected`

so that they may be used by any derived class that needs to manipulate similar sets. - Gen and kill sets are considered to be sparse, so they are calculuated
by iterators supplied by the derived class.
`void gen_iterator_init(instruction*)`

,`int gen_iterator()`

,`void kill_iterator_init(instruction*)`

,`int kill_iterator()`

- Other protected members just store data passed to the initialization routine.

The private members of `bit_vector_problem_plus`

are declared:

<`bit_vector_problem_plus`

private>=(<-U)DFAP_bitset_function_array* bb_xfer; // transfer function: per block DFAP_bit_set_array* bb_in; // in bitset: per block DFAP_bit_set_array* bb_out; // out bitset: per block void meet(cfg_node*); // code pulled out of solve for readability void build_local_info(int); // code pulled out of solve for readability

<`bit_set_array`

declarations>=(U-> U->)[D->]DECLARE_X_ARRAY(DFAP_bit_set_array, bit_set, 100); DECLARE_X_ARRAY(DFAP_bitset_function_array, bitset_function, 100);

Class `bit_vector_problem_plus`

resides in module
`bit_vector_dfa_plus`

, which has the following header file.

<bit_vector_dfa_plus.h>= /* Highly parameterized bit-vector-based dataflow analysis problems */<SUIF copyright>#ifndef BIT_VECTOR_DFA_PLUS_H #define BIT_VECTOR_DFA_PLUS_H /* Using an enumeration and constant defined in bit_vector_dfa.h */ #include "bit_vector_dfa.h"<`bit_set_array`

declarations><class#endif /* BIT_VECTOR_DFA_PLUS_H */`bit_vector_problem_plus`

>

Aho, Sethi, and Ullman **[cite bibdragon]** present live variable analysis as a
typical backward data flow problem. Our implementation closely follows
their Algorithm 10.4. The variables on which it operates are operands of
machine SUIF instructions. A library client invokes the analyzer by
constructing an instance of class `live_var_problem`

, and it accesses the
results via methods of that class.

`live_var_problem`

Like all instances of `bit_vector_problem`

, a `live_var_problem`

embeds
a CFG at the time it is constructed. The methods providing liveness results
for each node of the CFG each take the node as an argument. Here is an
outline of the class:

<class`live_var_problem`

>=(U->)class live_var_problem : protected bit_vector_problem { typedef void (*instruction_def_use_f) (instruction *, operand_bit_manager *, bit_set *, bit_set *); public: live_var_problem(cfg *, operand_bit_manager *, instruction_def_use_f = Instruction_def_use); virtual ~live_var_problem(); boolean live_in(cfg_node *n, int var_num); boolean live_out(cfg_node *n, int var_num); bit_set *live_in_set(cfg_node *n); bit_set *live_out_set(cfg_node *n); protected:<protected:`live_var_problem`

protected><};`live_var_problem`

private>

`live_var_problem`

.
As its declaration above shows, the `live_var_problem`

constructor takes
three arguments:

- The control flow graph of the program.
**[*]**An*operand bit manager*, which tells the analyzer how many variables to expect and provides the mapping from operands representing variable occurrences to indices in bit vectors.**[*]**A function that inspects an instruction and produces two sets: variables that it defines and variables that it references.

`bit_vector_problem::solve()`

.
Argument ([<-]), the bit manager, is created as described in Section [->]. It tells the liveness analyzer how big to make the bit vectors that it associates with CFG nodes, and which bits to turn on to indicate liveness of a set of variables. It also allows operands to be screened, so that uninteresting variables are omitted from the analysis.

Argument ([<-]) provides a way to obtain the operand
definition and use semantics of instructions in the program. It is a
function taking two inputs and two result parameters. The inputs are an
instruction and a bit manager for identifying operands. The results are
bit vectors that must be modified by the function to reflect variables
defined and variables used, respectively, by its instruction argument.
This functional parameter of the `live_var_problem`

constructor can be
omitted. In that case, the helper function `Instruction_def_use()`

is
used. Its behavior is described just below.

There are two pairs of methods for accessing the results of liveness analysis at a given CFG node.

- Method
`live_in(cfg_node *n, int v)`

returns true exactly when the variable with index`v`

is live on entry to node`n`

. Method`live_out(cfg_node *n, int v)`

is similar for exit from`v`

. - Method
`live_in_set(cfg_node *n)`

returns (a pointer to) a bit vector representing variables live on entry to`n`

;`live_out_set(cfg_node *n)`

similarly returns the set live on exit. The caller should not modify the result sets of these methods.

For cases in which the variables of interest are registers, virtual
registers **[cite bibmachsuif]**, and symbols that might be assigned to
registers, the library provides this utility:

<function`Instruction_def_use`

>=(U->)void Instruction_def_use(instruction *, operand_bit_manager *, bit_set *def, bit_set *use);

This function first clears result vectors `def`

and `use`

,
then it scans the operands of the instruction. Using its bit
manager parameter to screen operands and to set bits, it
reflects destination operand occurrences in `def`

and source
occurrences in `use`

. Sources within effective address (EA)
operands are treated similarly, but a symbol occurring as a
memory reference in an EA calculation is not treated as a
variable occurrence.

For the most part, `Instruction_def_use()`

ignores opcodes.
It does, however, treat call and return instructions specially:

- At a call, it uses the
`k_regs_used`

annotation to determine what registers are being used to pass arguments; it adds these to`use`

. It also treats all argument, result, temporary, and assembler-temporary registers, in all banks, as ``defined'' by the callee, and so adds them to`def`

. - At a return, it uses the
`k_instr_ret`

annotation to decide whether a result is being returned in registers, and if so to mark the appropriate result register(s) in`use`

.

`Instruction_def_use()`

is exported for use beyond the
liveness application. The register allocator `raga`

, for example,
uses it as well.

Method `live_in(cfg_node *n, int v)`

of `live_var_problem`

returns true exactly when the variable with index `v`

is live
on entry to node `n`

. Method `live_out(cfg_node *n, int v)`

is similar for exit from `v`

.
Liveness information can also be obtained in set form:
`live_in_set(cfg_node *n)`

returns (a pointer to) the bit
vector representing variables live on entry to `n`

;
`live_out_set(cfg_node *n)`

similarly returns the set live on
exit. These results may or may not point to copies; the caller
should not modify the result sets.

`live_var_problem`

It has proven handy to make most of the implementation of
`live_var_problem`

accessible to derived classes, so we now
describe the protected part of its interface.

The implementation defines and extensible-array type
`bit_set_array`

that it uses to map CFG nodes to bit vectors.
For storage reclamation, it also provides a helper function
`Delete_bit_set_array(bit_set_array *a)`

that invokes `delete`

on
`a`

after first `delete`

'ing each of its elements. The array
type and the delete function are declared by:

<`bit_set_array`

declarations>+=(<-U U->)[<-D]DECLARE_X_ARRAY(bit_set_array, bit_set, 1024); void Delete_bit_set_array(bit_set_array *);

The protected members of `live_var_problem`

are declared:

<`live_var_problem`

protected>=(<-U)operand_bit_manager *bit_man; bit_set_array *defs; bit_set_array *uses; bit_set_array *live_ins; bit_set_array *live_outs; void build_sets(); boolean solver_ops(cfg_node *); virtual void build_local_info(int n); virtual void note_instr_def_use(int node, instruction *, bit_set *def, bit_set *use);

Here is a rundown of their meanings.

`bit_man`

, the bit manager, provides the size of bit vectors for the current problem.- The
`defs`

and`uses`

arrays map a CFG node to the local information needed when solving for liveness.`(*defs)[n]`

is the set of variables defined before being used in node number`n`

.`(*uses)[n]`

is the set used before being defined. - The
`live_ins`

and`live_outs`

arrays map a CFG node's number to the set of variables live on entry or exit to that node, respectively. `build_sets()`

and`solver_ops(cfg_node *)`

are the virtual methods that must be defined to satisfy the base class`bit_vector_problem`

.`build_local_info(n)`

computes`(*defs)[n]`

and`(*uses)[n]`

. It is declared`virtual`

as a ``hook'' for extenders to hang new functionality on.`note_instr_def_use(int n, instruction *instr, bit_set *def, bit_set *use)`

is called in`build_local_info(n)`

to assimilate the effect of instruction`instr`

on local liveness information. It also leaves`def`

and`use`

holding the def/use vectors for`instr`

. This helps make it another useful hook point.

`live_var`

Class `live_var_problem`

, type `bit_set_array`

, and the helper
`Instruction_def_use()`

are defined in module `live_var`

, which has
the following header file.

<live_var.h>= /* Interface for bit-vector-based live-variable analyzer */<SUIF copyright>#ifndef LIVE_VAR_H #define LIVE_VAR_H<`bit_set_array`

declarations><function`Instruction_def_use`

><class#endif /* LIVE_VAR_H */`live_var_problem`

>

Unset variable analysis is a simple forward-flow problem that determines, for any program point, the set of variables that have no definition reaching that point. If a variable is used at a point where it is ``unset'' in this sense, its value is unpredictable and the program is probably incorrect.

Of course, in a correct program a variable can be live at a point in a without having a meaningful value there, assuming that it is initialized before it is actually used at runtime. In register allocation, it's useful to recognize the live ranges of a variable by intersecting the results of unset variable analysis with liveness information.

`unset_var_problem`

The unset variable problem is similar to the liveness problem in that the
items whose flow is of interest are storable locations. Therefore the
operand bit manager (Section [->]) plays a similar
role in both solvers. Their implementations differ because unset-variables
pays attention only to definitions, not to uses. Moreover, it is a
forward-flow problem instead of backward, it uses intersection instead of
union as its confluence operator, and it starts from universal (full) bit
vectors rather than empty ones. However, the definition, use and extension
of class `unset_var_problem`

are analogous to those of class
`live_var_problem`

(Section [<-]).

<class`unset_var_problem`

>=(U->)class unset_var_problem : protected bit_vector_problem { typedef void (*instruction_def_use_f) (instruction *, operand_bit_manager *, bit_set *, bit_set *); public: unset_var_problem(cfg *, operand_bit_manager *, instruction_def_use_f = Instruction_def_use); virtual ~unset_var_problem(); boolean unset_in(cfg_node *n, int var_num); boolean unset_out(cfg_node *n, int var_num); bit_set *unset_in_set(cfg_node *n); bit_set *unset_out_set(cfg_node *n); protected:<private:`unset_var_problem`

protected><};`unset_var_problem`

private>

The `unset_var_problem`

constructor declared above takes three arguments:

- The control flow graph of the program.
- An operand bit manager giving the number of variables to allow for in the analysis and providing the map from operands representing relevant variables to indices in bit vectors.
- A function that analyzes the variables defined and used by one instruction. (The information about variable uses isn't needed, but it allows sharing of a single instruction-analysis helper function.)

`bit_vector_problem::solve()`

.

`unset_var_problem`

The protected members of `unset_var_problem`

are declared as
for class `live_var_problem`

, except that variable uses are not
of interest.

<`unset_var_problem`

protected>=(<-U)operand_bit_manager *bit_man; bit_set_array *defs; bit_set_array *unset_ins; bit_set_array *unset_outs; void build_sets(); boolean solver_ops(cfg_node *); virtual void build_local_info(int n); virtual void note_instr_def(int node, instruction *, bit_set *def);

Here is a review of the meanings of the above-declared members.

`bit_man`

, the bit manager, provides the size of bit vectors for the current problem and screens out irrelevant operands.- The
`defs`

array maps a CFG node to the local information needed when solving for liveness.`(*defs)[n]`

is the set of variables defined before being used in node number`n`

. - The
`unset_ins`

and`unset_outs`

arrays map a CFG node's number to the set of variables definitely uninitialized on entry or exit to that node, respectively. `build_sets()`

and`solver_ops(cfg_node *)`

are the virtual methods that must be defined to satisfy the base class`bit_vector_problem`

.`build_local_info(n)`

computes`(*defs)[n]`

. It is declared`virtual`

as a ``hook'' for extenders to hang new functionality on.`note_instr_def_use(int n, instruction *instr, bit_set *def)`

is called in`build_local_info(n)`

to assimilate the effect of instruction`instr`

on local unsetness information. It also leaves`def`

holding the defined-variable set for`instr`

. This makes it another useful hook point.

`unset_var`

<unset_var.h>= /* Interface for bit-vector-based unset variable analyzer */<SUIF copyright>#ifndef UNSET_VAR_H #define UNSET_VAR_H<class#endif /* UNSET_VAR_H */`unset_var_problem`

>

Specific solvers of bit-vector problems need to be told how large to make
the vectors and how to map a variable or expression in the program to one or
more bits in a bit vector. For the common case in which the program
entities of interest are register and symbol operands, an *operand bit
manager* serves these purposes. Before analysis, as the program to be
analyzed is first scanned, it assigns bit indices to operands. During
analysis, as operands are revisited, it provides efficient lookup of their
indices.

In general, a bit manager may assign more than one bit to an operand. A
hard-register operand's type may indicate that it spans more than one
natural (i.e., physical) register. In that case, the bit manager gives it
a range of indices covering the physical registers it represents. For
architectures with addressable subregisters, many analyzers want to treat
subregister grains **[cite bibmachsuif]** as potentially independent resources.
In that case, the bit manager associates a range of indices with each
natural register in the bank. The indices for a particular hard register
operand are again a function of both its register number and its type.
As a special case, a hard register operand with `type_void`

as its type
is treated as though its type had size equal to the natural width of the
register.

For example, on the MIPS-I architecture, *machsuif* might refer to
register `$f4`

using the integer *52*. An operand having that register
number and `type_double`

as its type is assigned the bit range
`[`52,53`]`, since a `double`

spans two registers in the
floating-point bank. On the *x86*, a register operand with
number 8 refers to general-purpose register `A`

. With `type_signed`

(or `type_void`

) as its type, the bit range given to it is
`[`8,11`]`. With `type_char`

instead, its bit range is the
singleton `[`8`]`.

Virtual registers and symbols always have single-bit ranges, but the same methods are used for dealing with them as for hard registers.

The class of operand bit managers is declared as follows:

<class`operand_bit_manager`

>=(U->)class hard_reg_map; class operand_bit_manager { public: typedef boolean (*filter_f)(operand); operand_bit_manager(filter_f = NULL, hard_reg_map * = NULL, int hash_table_size = 1024, boolean reverse_map = FALSE); ~operand_bit_manager();<private:`operand_bit_manager`

public><};`operand_bit_manager`

private>

`operand_bit_manager`

.
As can be seen above, the constructor for class `operand_bit_manager`

takes four arguments. All are optional.

- An optional filter predicate, a boolean function taking an operand as argument. If the filter is provided, the bit manager ignores any operand for which the filter returns false.
**[*]**An optional replacement for the map assigning index ranges to hard registers. By default, the first index in the range for a hard register operand is its abstract register number, and each bit stands for one addressable grain. Section [->] describes how to override this assignment by supplying a customized hard register map, and tells why that might be useful.- An optional bucket count for the bit manager's hash table. Overriding the default value may affect performance, but not the table's capacity.
- An optional flag that, if true, causes the manager to build a reverse map from operands to their starting indices.

`operand_bit_manager`

.The public methods of an operand bit manager object are declared as follows:

<`operand_bit_manager`

public>=(<-U)int num_bits() { return next_index; } boolean enroll(operand, int *index_ptr = NULL, int *count_ptr = NULL); void enroll(instruction *); boolean lookup(operand, int *index_ptr = NULL, int *count_ptr = NULL); boolean forget(operand); boolean insert(operand, bit_set *); boolean remove(operand, bit_set *); operand retrieve(int index, int skip); void print_entries(bit_set *, FILE *); boolean intersects(operand, bit_set *); boolean dst_intersects(instruction *, bit_set *); boolean src_intersects(instruction *, bit_set *);

Here's how the above methods are used.

`num_bits()`

returns the total number of bits allocated so far for all enrolled symbols and registers, including hard registers (which are enrolled automatically when the manager is constructed). This is the method that a data flow analyzer calls to find out how many bits to allocate in each bit vector.`enroll(operand opd, int *index_ptr, int *count_ptr)`

tries to put`opd`

under management. It returns true exactly when the operand is new and is entered successfully (not filtered out). In addition, if the method's optional arguments`index_ptr`

and/or`count_ptr`

are supplied, it uses them to return the bit range for the operand, if it has one. The first index is stored through`index_ptr`

; the length of the range, through`count_ptr`

. Return of the bit range via the optional result parameters may occur whether the operand is new or old. In particular, if a hard register has a bit range, it will be returned, although a hard register is never considered ``new'' to the manager.`enroll(instruction *)`

tries to enroll all the operands of its instruction argument. It returns nothing.`lookup(operand opd, int *index_ptr, int *count_ptr)`

returns true if`opd`

is under management, and in that case, optionally returns its bit range through result parameters. It is similar to`enroll(opd, index_ptr, count_ptr)`

, but it doesn't enroll a new operand, and it returns true exactly when the`opd`

is already under management. Thus it can return true for a hard register operand that passes the filter and has an associated bit range.`forget(operand opd)`

removes`opd`

from management without affecting the index assignents of other operands. It does nothing if`opd`

represents a hard register. It returns true exactly when it makes a change, i.e., when it causes`opd`

to be forgotten.`insert(operand opd, bit_set *bv)`

uses the bit manager to turn on the bits for an`opd`

in bit vector`bv`

. It returns true unless`opd`

is not under management.`remove(operand opd, bit_set *bv)`

is like`insert(opd, *bv)`

, but it turns the bits for`opd`

in`bv`

off instead of on.`retrieve(int index, int skip)`

returns the operand whose index range begins at`index`

, or else the null operand, if no such operand has been recorded. Since it is possible for more than one operand's range to begin at the same index, parameter`skip`

says how many to skip before returning one. Note that`retrieve`

can only return a non-null operand if the`reverse_map`

option is true when the bit manager is created.`print_entries(bit_set *bv, FILE *file)`

prints on`file`

a representation of the operands whose index ranges are covered by`bv`

. Requires that the manager was created with the`reverse_map`

option true.`intersects(operand opd, bit_set *bv)`

returns true exactly when any of the bits for`opd`

are turned on in bit vector`bv`

.`dst_intersects(instruction *instr, bit_set *bv)`

returns true if there is any destination operand`opd`

in`instr`

such that`intersects(opd, bv)`

is true.`src_intersects(instruction *instr, bit_set *bv)`

is like`dst_intersects(instr, bv)`

, but for the source operands of`instr`

.

In some applications of class `operand_bit_manager`

, it's not necessary
to allocate space in bit vectors for every addressable grain of every hard
register bank. The register allocator `raga`

, for example, processes one
bank at a time, and it never treats subregister grains independently.
Furthermore, its observed performance is quite sensitive to the sizes of
the bit vectors in use. That's the reason for the optional
argument ([<-]) of `operand_bit_manager`

's constructor.
It lets the client control which subset of the architecture's registers are
considered ``under management'' and exactly which bit ranges are assigned
to each.

Class `hard_reg_map`

provides this information, albeit in a slightly
indirect way. An instance of `hard_reg_map`

maps an abstract register
number to a pair (`index`

, `size`

), where `index`

is to be the
start of the register's assigned bit range, and `size`

is the amount of
register turf (in bits) to be represented by each bit in the range. For
example, suppose the mapping for the *x86*'s register 20, which is
general-purpose register `B`

, has the entry *(16, 8)*. Then a register
operand with register number 20 and type `type_signed`

is
given the index range *[16,19]* because the 32-bit type has four 8-bit
pieces. On the other hand, if register 20 maps instead to *(4, 32)*, then
the same operand would get the singleton range *[4]*.

When building a `hard_reg_map`

, it is only necessary to specify each
register to be managed and give its size-per-vector-bit, i.e., the number
of its bits to be covered by a single bit-vector entry. Starting indexes
are assigned automatically, in the order in which registers are entered in
the map.

Class `hard_reg_map`

is declared:

<class`hard_reg_map`

>=(U->)class hard_reg_map { public: hard_reg_map(); hard_reg_map(int capacity); ~hard_reg_map(); inline int length(); void enter(int reg, int size, boolean overlay = FALSE); int index(int reg); int size(int reg); private:<};`hard_reg_map`

private><`hard_reg_map`

inline>

Here's the rundown of its public methods:

`hard_reg_map()`

creates the full, ``natural'' map for the current`target_arch`

. That is, it places every register under management, it gives each its own abstract number as starting index, and a size-per-vector-bit equal to the addressable grain size for its bank.`hard_reg_map(int capacity)`

creates a map accommodating register numbers from 0 to`capacity-1`

. However, it shows*no*registers under management; they must be entered explicitly by calling method`enter()`

. Normally,`capacity`

is the total number of addressable grains for the current`target_arch`

.`length()`

yields the number of bits allocated to registers entered in the map so far.`enter(int reg, int size, boolean overlay)`

adds register`reg`

to the map, with`size`

as its size-per-vector-bit. By default,`overlay`

is false; in that case, this method assigns one or more new bits to cover`reg`

and increases`length()`

by the number assigned. When`overlay`

is true, no new bit index is assigned; instead, the last one assigned is reused.`index(int reg)`

returns the starting bit index associated with`reg`

.`size(int reg)`

returns the size-per-vector-bit for`reg`

.

`operand_bit_manager`

Classes `operand_bit_manager`

and `hard_reg_map`

are defined in module
`operand_bit_manager`

, which has the following header file:

<operand_bit_manager.h>= /* Operand bit manager interface */<SUIF copyright>#ifndef OPERAND_BIT_MANAGER_H #define OPERAND_BIT_MANAGER_H<class`operand_bit_manager`

><class#endif /* OPERAND_BIT_MANAGER_H */`hard_reg_map`

>

Muchnick, **[cite bibmuchnick]**, and many other authors present the
theoretical basis for dataflow problems in terms of ``flow functions''
or ``transfer functions''.

Here we define the three monotone boolean boolean functions,
extended pointwise to sets of booleans.
We define useful routines for applying these functions to `bitset`

s.
This will allow us to encode operations on `bitset`

s directly from
the theory.

The reason that we can get away with using the theory in practice is
that there are only three monotone boolean functions (the identity
function, the function that always returns the constant top (true, 1),
and the function that always returns the constant bottom (false, 0).
So we only need two bits to represent a monotone boolean boolean
function.
Thus the pointwise extension of boolean functions to sets of sets of
booleans, can be represented in only twice as much space as the
`bitset`

s that they manipulate.

`bitset_function`

<class`bitset_function`

>=(U->)class bitset_function { private:<protected:`bitset_function`

private><public: bitset_function(int initial_number_of_bits); ~bitset_function(); bitset_function(const bitset_function&); bitset_function& operator=(const bitset_function&); void topfn()`bitset_function`

protected><void topfn(int bitnum)`bitset_function::topfn()`

inlined><void botfn()`bitset_function::topfn(bitnum)`

inlined><void botfn(int bitnum)`bitset_function::botfn()`

inlined><void idfn()`bitset_function::botfn(bitnum)`

inlined><void idfn(int bitnum)`bitset_function::idfn()`

inlined><void apply(bit_set* updated)`bitset_function::idfn(bitnum)`

inlined><void compose(const bitset_function* old)`bitset_function::apply(updated)`

inlined><void print(FILE* fp = stdout); };`bitset_function::compose(old)`

inlined>

When you create a boolean bitset function, it is initialized to the identity function.

`topfn(n)`

modifies the function to set bit `n`

to 1 (top).

`topfn()`

modifies the function to set all bits to 1 (top).

`botfn(n)`

modifies the function to set bit `n`

to 0 (bottom).

`botfn()`

modifies the function to set all bits to 0 (bottom).

`idfn(n)`

modifies the function to pass the value of bit `n`

unchanged.

`idfn()`

modifies the function to pass the values of all bits unchanged.

`apply(b)`

applies the boolean function to a `bit_set*`

`b`

,
overwriting `b`

.

`f.compose(g)`

sets the function `f`

to `f`

* o *`g`

, overwriting `f`

.

We provide the standard copy constructor and assignment operator
functionality which may be used in combination with `compose`

to
perform nondestructuve composition (by performing destructuve
composition on a copy).

`bitset_function`

Class `bitset_function`

is defined in module `bitset_function`

, which has
the following header file.

<bitset_function.h>= /* Bit Set Definitions */<SUIF copyright>#ifndef BITSET_FUNCTION_H #define BITSET_FUNCTION_H #pragma interface<class#endif /* BITSET_FUNCTION_H */`bitset_function`

>

Close your eyes: the content of the following sections is are not for public viewing and may change without notice.

<`bitset_function`

protected>=(<-U)int hbn; bit_set* id; bit_set* cs; bitset_function();

`hbn`

is the number of the first unused bit (or the number of bits
managed by the bitset_function since it always manages bits starting
from bit 0).

`id`

is a bitset. If `id(n) == 0`

then the function is a constant
function at `n`

. If `id(n) == 1 && cs(n) == 0`

then the function
is the identity function at `n`

.

`cs`

is a bitset. If `id(n) == 0 && cs(n) == 0`

then the function
is the constant bottom function at `n`

. `id(n) == 0 && cs(n) == 1`

then the function is the constant top function at `n`

.

`bitset_function()`

is a constructor for internal use: private and
protected variables are set to default values and must be updated later
before the function is usable.

<`bitset_function`

private>=(<-U)

<`bitset_function::topfn()`

inlined>=(<-U){ id->clear(); // set function to "constant 1" on all bits cs->universal(); }

<`bitset_function::topfn(bitnum)`

inlined>=(<-U){ assert_msg(bitnum >= 0 && bitnum < hbn, ("bitset_function::topfn - bit %d not in range %d-%d", bitnum,0,hbn)); id->remove(bitnum); cs->add(bitnum); }

<`bitset_function::botfn()`

inlined>=(<-U){ id->clear(); // set function to "constant 0" on all bits cs->clear(); }

<`bitset_function::botfn(bitnum)`

inlined>=(<-U){ assert_msg(bitnum >= 0 && bitnum < hbn, ("bitset_function::botfn - bit %d not in range %d-%d", bitnum,0,hbn)); id->remove(bitnum); cs->remove(bitnum); }

<`bitset_function::idfn()`

inlined>=(<-U){ id->universal(); // set function to "identity" on all bits cs->clear(); }

<`bitset_function::idfn(bitnum)`

inlined>=(<-U){ assert_msg(bitnum >= 0 && bitnum < hbn, ("bitset_function::idfn - bit %d not in range %d-%d", bitnum,0,hbn)); id->add(bitnum); cs->remove(bitnum); }

<`bitset_function::apply(updated)`

inlined>=(<-U){ *updated *= *id; // if identity function, keep bits *updated += *cs; // set bits by const fns // requires representation invariant // that (cs == cs - id) }

<`bitset_function::compose(old)`

inlined>=(<-U){ bit_set tmp(0,hbn); // temporary bit set in scope tmp = *id; tmp *= *(old->cs); *cs += tmp; *id *= *(old->id); }

File `dfa.h`

is the only header file that a client module needs to
include. The name of the library archive is `libdfa.h`

, so add a
`-ldfa`

switch to those seen by the linker. This may need to appear
early in the list of library switches. For example, a pass may make no use
of hash tables, but may need the operand bit manager, which does use
hashing. In that case, `-ldfa`

must precede `-lsuif1`

, since
`libsuif1.a`

provides the hash table module.

<dfa.h>= /* Top-level Dataflow Analysis Header File */<SUIF copyright>#ifndef DFA_H #define DFA_H /* * Use a macro to include files so that they can be treated differently * when compiling the library than when compiling an application. */ #ifdef DFALIB #define DFAINCLFILE(F) #F #else #define DFAINCLFILE(F) <dfa/ ## F ## > #endif #include DFAINCLFILE(bit_vector_dfa.h) #include DFAINCLFILE(operand_bit_manager.h) #include DFAINCLFILE(live_var.h) #include DFAINCLFILE(live_var_more.h) /* For scheduling. To be moved. */ #include DFAINCLFILE(unset_var.h) #include DFAINCLFILE(def_teller.h) #include DFAINCLFILE(def_catalog.h) #include DFAINCLFILE(reaching_def.h) #include DFAINCLFILE(bitset_function.h) #include DFAINCLFILE(bit_vector_dfa_plus.h) #include DFAINCLFILE(live_varAD.h) #include DFAINCLFILE(instr_catalog.h) #endif /* DFA_H */

All of the code is protected by the following copyright notice.

<SUIF copyright>=(<-U <-U <-U U-> U-> <-U <-U)/* Copyright (c) 1996,1997 The President and Fellows of Harvard University All rights reserved. This software is provided under the terms described in the "suif_copyright.h" include file. */ #include <suif_copyright.h>

The DFA library was designed and initially implemented by Prof. Michael
Smith, leader of the HUBE research group at Harvard. As mentioned in
section [<-], his definition of the
`bit_vector_problem`

class was influenced by work of Steve Tjiang at
Synopsys and Prof. Todd Mowry's students at the University of Toronto.

The CFG library that is now part of machine SUIF has greatly eased both the implementation and use of the DFA library. It was implemented by Cliff Young, with contributions from Tony DeWitt and Gang Chen.

Gang Chen developed the initial version of the `operand_bit_manager`

class and made several suggestions that have improved the liveness
analyzer.

This work is supported by a National Science Foundation Young Investigator award, grant no. CCR-9457779. We also gratefully acknowledge the generous support of this research by Advanced Micro Devices, Digital Equipment, Hewlett-Packard, International Business Machines, and Intel.

**[1]** A. Aho, R. Sethi, and J. Ullman. *Compilers:
Principles, Techniques, and Tools.* Addison-Wesley, 1986.

**[2]** C. Fischer and R. LeBlanc. *Crafting a
Compiler.* Benjamin/Cummings, 1988.

**[3]** S. Muchnick. *Advanced Compiler Design and
Implementation.* Morgan Kaufmann, 1997.

**[4]** M. Smith. *Extending SUIF for Machine-specific
Optimizations.* The machine SUIF compiler documentation set, Harvard
University, 1996.

**[5]** C. Young. *The SUIF Control Flow Graph Library.* The
machine SUIF compiler documentation set, Harvard University, 1997.

`live_var_problem`

The hidden members of `live_var_problem`

are all variables. One
holds the instruction-analyzer function passed at instance
construction. The others are temporary bit vectors, declared as
class members to avoid repeated construction and destruction.

<`live_var_problem`

private>=(<-U)instruction_def_use_f instr_def_use_fun; bit_set *instr_def; bit_set *instr_use;

`unset_var_problem`

The hidden members of `unset_var_problem`

are identical to those for
`live_var_problem`

.

<`unset_var_problem`

private>=(<-U)instruction_def_use_f instr_def_use_fun; bit_set *instr_def; bit_set *instr_use;

`operand_bit_manager`

The private part of `operand_bit_manager`

declares the user-provided
operand filter and the next bit index to be assigned when an operand
is enrolled:

<`operand_bit_manager`

private>=(<-U)[D->]filter_f filter; int next_index;

It also records two data structures for mapping operands to
indices: `hard_map`

handles hard registers; `soft_map`

is
for virtual registers and symbols. And one for the reverse
mapping: `anti_map`

takes an index range back to the original
operand.

<`operand_bit_manager`

private>+=(<-U)[<-D->]hard_reg_map *hard_map; hash_table *soft_map; hash_table *anti_map;

Since the `hard_map`

can be either user-provided or internally
generated, there is a variable, `hard_map_own`

, that is null in
the former case and equal to `hard_map`

in the latter. The
class destructor applies `delete`

to this member.

<`operand_bit_manager`

private>+=(<-U)[<-D->]hard_reg_map *hard_map_own;

There are also temporary hash table entries, used to avoid storage thrashing on hash table entries.

<`operand_bit_manager`

private>+=(<-U)[<-D->]hash_e *next_soft_map_e; hash_e *next_anti_map_e;

The function members are simply subroutines of the public methods.

<`operand_bit_manager`

private>+=(<-U)[<-D]typedef void (bit_set::*bit_set_op)(int); boolean insert_or_remove(operand, bit_set *, bit_set_op op); boolean get_bit_range(operand, int *, int *, boolean); boolean hr_bit_range(operand, int *, int *); boolean covers_hr(bit_set *, operand);

`hard_reg_map`

Internally, a `hard_reg_map`

contains a counter for bit-index
assignment, a capacity value, and two arrays mapping a register
number to starting index and size-per-vector-bit, respectively.

<`hard_reg_map`

private>=(<-U)int next_index; int capacity; int *indexes; int *sizes;

Too simple not to compile inline:

<`hard_reg_map`

inline>=(<-U)inline int hard_reg_map::length() { return next_index; }

*<*: D1, U2, D3, U4`bit_set_array`

declarations>*<*: U1, D2`bitset_function`

private>*<*: U1, D2`bitset_function`

protected>*<*: U1, D2`bitset_function::apply(updated)`

inlined>*<*: U1, D2`bitset_function::botfn()`

inlined>*<*: U1, D2`bitset_function::botfn(bitnum)`

inlined>*<*: U1, D2`bitset_function::compose(old)`

inlined>*<bitset_function.h>*: D1*<*: U1, D2`bitset_function::idfn()`

inlined>*<*: U1, D2`bitset_function::idfn(bitnum)`

inlined>*<*: U1, D2`bitset_function::topfn()`

inlined>*<*: U1, D2`bitset_function::topfn(bitnum)`

inlined>*<bit_vector_dfa.h>*: D1*<bit_vector_dfa_plus.h>*: D1*<*: U1, D2, D3, D4, D5, D6`bit_vector_problem_plus`

enum>*<*: U1, D2`bit_vector_problem_plus`

private>*<*: U1, D2`bit_vector_problem_plus`

protected>*<class*: D1, U2`bitset_function`

>*<class*: D1, U2`bit_vector_problem`

>*<class*: D1, U2`bit_vector_problem_plus`

>*<class*: D1, U2`hard_reg_map`

>*<class*: D1, U2`live_var_problem`

>*<class*: D1, U2`operand_bit_manager`

>*<class*: D1, U2`unset_var_problem`

>*<dfa.h>*: D1*<function*: D1, U2`Instruction_def_use`

>*<*: U1, D2`hard_reg_map`

inline>*<*: U1, D2`hard_reg_map`

private>*<live_var.h>*: D1*<*: U1, D2`live_var_problem`

private>*<*: U1, D2`live_var_problem`

protected>*<*: U1, D2, D3, D4, D5, D6`operand_bit_manager`

private>*<*: U1, D2`operand_bit_manager`

public>*<operand_bit_manager.h>*: D1*<SUIF copyright>*: U1, U2, U3, U4, U5, U6, U7, D8*<unset_var.h>*: D1*<*: U1, D2`unset_var_problem`

private>*<*: U1, D2`unset_var_problem`

protected>