The Data Flow Analysis Library of Machine SUIF

Glenn Holloway
holloway@deas.harvard.edu
Division of Engineering and Applied Sciences
Harvard University
Compatible with SUIF Release 1.1.2
Revised May 2, 1998

Introduction

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.

Class 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:

Note that nothing in class 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 bit_vector_problem>

#endif /* BIT_VECTOR_DFA_H */

Class bit_vector_problem_plus

[*]

The bit_vector_problem_plus class is an attempt to replace bit_vector_problem for bit-vector-based DFA problems. 

<class bit_vector_problem_plus>= (U->)
  <bit_vector_problem_plus enum>

class bit_vector_problem_plus {
private:
  <bit_vector_problem_plus private>

protected:
  <bit_vector_problem_plus protected>

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
};

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:

Other than initilization and deletion, the other public methods are

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:

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*);

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 bit_vector_problem_plus>

#endif /* BIT_VECTOR_DFA_PLUS_H */

Live Variable Analysis

[*]

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.

Using 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:
    <live_var_problem protected>

  protected:
    <live_var_problem private>
};

Constructing a live_var_problem.

As its declaration above shows, the live_var_problem constructor takes three arguments:

  1. The control flow graph of the program.
  2. [*] 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.
  3. [*] A function that inspects an instruction and produces two sets: variables that it defines and variables that it references.
The constructor performs the liveness analysis before it returns the constructed instance. That is, it invokes 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.

Accessing liveness results.

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

Instruction analysis for registers, real and potential.

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:

Function Instruction_def_use() is exported for use beyond the liveness application. The register allocator raga, for example, uses it as well.

Accessing liveness results.

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.

Extending class 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.

Header file for module 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 live_var_problem>
#endif /* LIVE_VAR_H */

Unset Variable Analysis

[*]

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.

Using class 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:
    <unset_var_problem protected>

  private:
    <unset_var_problem private>
};

The unset_var_problem constructor declared above takes three arguments:

  1. The control flow graph of the program.
  2. 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.
  3. 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.)
The constructor performs the unsetness analysis before returning the constructed instance by invoking bit_vector_problem::solve().

Extending class 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.

Header file for module unset_var

<unset_var.h>=
/* Interface for bit-vector-based unset variable analyzer */

<SUIF copyright>

#ifndef UNSET_VAR_H
#define UNSET_VAR_H

<class unset_var_problem>
#endif /* UNSET_VAR_H */

Mapping Registers and Symbols to Bit-vector Indices

[*]

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();

    <operand_bit_manager public>
    
  private:
    <operand_bit_manager private>
};

Constructing an operand_bit_manager.

As can be seen above, the constructor for class operand_bit_manager takes four arguments. All are optional.

  1. 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.
  2. [*] 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.
  3. An optional bucket count for the bit manager's hash table. Overriding the default value may affect performance, but not the table's capacity.
  4. An optional flag that, if true, causes the manager to build a reverse map from operands to their starting indices.

Using an 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.

Changing the index assignments for hard registers

[*]

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:

Header file for module 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 hard_reg_map>

#endif /* OPERAND_BIT_MANAGER_H */

Boolean Bitset Functions

[*]

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 bitsets. This will allow us to encode operations on bitsets 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 bitsets that they manipulate.

Using class bitset_function

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

protected:
  <bitset_function protected>

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::topfn() inlined>
  void topfn(int bitnum)  <bitset_function::topfn(bitnum) inlined>
  void botfn()            <bitset_function::botfn() inlined>
  void botfn(int bitnum)  <bitset_function::botfn(bitnum) inlined>
  void idfn()             <bitset_function::idfn() inlined>
  void idfn(int bitnum)   <bitset_function::idfn(bitnum) inlined>

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

  void print(FILE* fp = stdout);
};

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).

Header file for module 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 bitset_function>
#endif /* BITSET_FUNCTION_H */

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

Protected methods: subject to 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.

Private methods: subject to change without notice

<bitset_function private>= (<-U)

Inlined code: subject to change without notice

<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);
}

*

Connecting to the DFA Library

[*]

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>

Likely Extensions of the DFA Library

[*] Our plan is to add analyzers to the DFA framework as we need them. Our register allocator might give sharper performance if reaching definitions were used in combination with liveness analysis, for example.

Acknowledgments

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.

References

[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.

Indecent Exposure

Here we expose the private parts of the library's interfaces, with minimal commentary.

Class 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;

Class 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;

Class 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);

Class 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; }

*