Go to the previous, next section.

An Example

An example of using the dependence analyzer is given at the end of this section. Most of the code deals with finding array accesses in a program in SUIF. To use the dependence analyzer, there are two main points to which readers should pay additional attention. First, before DependenceTest can be called for array accesses in a given procedure, fill_in_access must be called to annotate the code with information needed by the dependence analyzer. In our code below, note that method do_proc calls fill_in_access before processing each procedure body. Given two array accesses, method print_dep demonstrates the simplicity of testing for dependence between two array accesses. print_dep first tests whether the accesses are data dependent by calling DependenceTest, then the result of the test is output to stdout using the print method of class dvlist. Lastly, note the files stdlib.h, suif.h, useful.h and dependence.h must be included.

#include "suif.h"
#include "useful.h"
#include "dependence.h"
#include <stdlib.h>

/***************************************************************************
 * Declare a new class which is a list of "in_array"'s                     *
 ***************************************************************************/
DECLARE_DLIST_CLASS(array_instr_list, in_array *);

void find_array_instr(tree_node_list * tnl, array_instr_list * ail);
void find_array_instr(tree_node * tn, array_instr_list * ail);
void find_array_instr(instruction * i, array_instr_list * ail);


/***************************************************************************
 * 
 ***************************************************************************/
void print_dep(in_array * ai1, in_array * ai2)
{
    dvlist * dep = DependenceTest(ai1, ai2);
    assert(dep);
    if(!dep->indep()) 
        dep->print(stdout);
}


/***************************************************************************
 *
 ***************************************************************************/
void process_array_instr_list(array_instr_list * ail) 
{
    array_instr_list_iter iter1(ail);
    while(!iter1.is_empty()) {
        in_array * ai1 = iter1.step();
        if(is_lhs(ai1)) {
            var_sym * vs1 = get_sym_of_array(ai1);
            print_array_access(ai1);
            printf("Output\n");
            print_dep(ai1, ai1);

            printf("True/anti\n");
            array_instr_list_iter iter2(ail);
            while(!iter2.is_empty()) {
                in_array * ai2 = iter2.step();
                var_sym * vs2 = get_sym_of_array(ai2);
                if(vs1 == vs2)
                    if(!is_lhs(ai2))
                        print_dep(ai1, ai2);
            }
        }
    }

    
}


/***************************************************************************
 * The main iterator over structured control-flow.                         *
 * When there is no outer for loop ail will be NULL.  ail will be assigned *
 * at the outermost for loops. All the array accesses are collected and    *
 * print routine is called at the outermost for loop.                      *
 ***************************************************************************/
void find_array_instr(tree_node_list * tnl, array_instr_list * ail)
{
    tree_node_list_iter iter(tnl);
    while(!iter.is_empty()) {
        tree_node * tn = iter.step();
        
        switch(tn->kind()) {
        case TREE_FOR:
            tree_for * tnf = (tree_for *)tn;
            find_array_instr(tnf->lb_list(), ail);
            find_array_instr(tnf->ub_list(), ail);
            find_array_instr(tnf->step_list(), ail);
            
            boolean outermost = FALSE;
            array_instr_list * ail_bdy = ail;
            if(ail_bdy == NULL) {
                outermost = TRUE;
                ail_bdy = new array_instr_list;
            }
            printf("For loop %s %s\n", 
                   tnf->index()->name(), 
                   outermost?"(Outermost)":"");
            
            find_array_instr(tnf->landing_pad(), ail_bdy);
            find_array_instr(tnf->body(), ail_bdy);
            
            if(outermost) process_array_instr_list(ail_bdy);
            break;
            
        case TREE_IF:
            tree_if * tni = (tree_if *)tn;
            find_array_instr(tni->header(), ail);
            find_array_instr(tni->then_part(), ail);
            find_array_instr(tni->else_part(), ail);
            break;
            
        case TREE_LOOP:
            tree_loop * tnl = (tree_loop *)tn;
            find_array_instr(tnl->body(), ail);
            find_array_instr(tnl->test(), ail);
            break;
            
        case TREE_BLOCK:
            tree_block * tnb = (tree_block *)tn;
            find_array_instr(tnb->body(), ail);
            break;
            
        case TREE_INSTR:
            tree_instr * tnin = (tree_instr *)tn;
            if(ail)
                find_array_instr(tnin->instr(), ail);
            break;
            
        default:
            assert(0);
            break;
        }
    }
}


/***************************************************************************
 * Iterate over all the instructions of expression trees, add array        *
 * instructions to the list.                                               *
 ***************************************************************************/
void find_array_instr(instruction * ins, array_instr_list * ail)
{
    if(ins->opcode() == io_array) {
        assert(ail);
        in_array * ia = (in_array *)ins;
        ail->append(ia);
    }

    for(int i=0; i<ins->num_srcs(); i++) {
        operand op(ins->src_op(i));
        if(op.is_instr())
            find_array_instr(op.instr(), ail);
    }
}


/***************************************************************************
 * create the annotations needed by dependence by calling fill_in_access   *
 * and start processing..                                                  *
 ***************************************************************************/
void do_proc(tree_proc * tp)
{
    proc_sym * psym = tp->proc();
    printf("=======%s======= \n", psym->name());
    fill_in_access(tp);
    find_array_instr(tp->body(), NULL);
}

/***************************************************************************
 * Initialize and iterate over all the procedures.                         *
 ***************************************************************************/
main(int argc, char * argv[])
{
    start_suif(argc, argv);
    suif_proc_iter(argc, argv, do_proc);
}

Go to the previous, next section.