Go to the previous, next section.

Example 4 - Print Dependence Vectors

At each outermost loop nest, this pass will print all the true, anti and output dependence vectors for each array write access.

prog4.cc

#include <stdlib.h>
#include "suif.h"
#include "useful.h"
#include "dependence.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);
}

The makefile is the same as the previous example.

Testing the pass

Let's use the following input file:

input4.c

double A[10000];
double B[100][100];

test1(int IU, int JU, int KU)
{
    int i, j, k;
    for(i=0; i<IU; i++) 
        for(j=0; j<JU; j++) {
            for(k=8; k<KU; k++) 
                A[k] = A[k-8];
            B[i][j] = B[i+1][j] + A[i];
        }
    for(i=0; i<IU; i++) 
        for(j=0; j<JU; j++) 
            B[i][j] = B[i][j] + B[i+1][j];
}

test2( int KU)
{
    int  k;

    for(k=8; k<KU; k++) 
        A[k] = A[1] + A[k] + A[k+8];
}

Test session

csh> prog4 input4.spd
=======test1=======
For loop i (Outermost)
For loop j
For loop k
A[k]
Output
( + * 0 )
( 0 + 0 )
( 0 0 0 )
True/anti
( + * -8 )
( 0 + -8 )
( + * + )
( + * 0 )
( + * - )
( 0 + + )
( 0 0 + )
( 0 + 0 )
( 0 0 0 )
( 0 + - )
B[i,j]
Output
( 0 0 )
True/anti
( 1 0 )
For loop i (Outermost)
For loop j
B[i,j]
Output
( 0 0 )
True/anti
( 0 0 )
( 1 0 )
=======test2=======
For loop k (Outermost)
A[k]
Output
( 0 )
True/anti
( 0 )
( 8 )
csh>

Go to the previous, next section.