Go to the previous, next section.

Example 3 - Print Array Accesses

In this example all the array accesses are printed in a given order. For each outermost loop nest, all the array acceses inside the body of that loops are printed. Accesses that are written (LHS) and read (RHS) are printed separately.

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


/***************************************************************************
 * Iterate over all the elements in the list and print each instruction.   *
 * The call to print_array_access which is defined in dependence/dodep.h,  *
 * will print the access in a C-like format.                               * 
 ***************************************************************************/
void print_array_instr_list(array_instr_list * ail) 
{
    array_instr_list_iter iter(ail);
    while(!iter.is_empty()) {
        in_array * ai = iter.step();
        print_array_access(ai);
    }
}


/***************************************************************************
 * Iterate over all the array accesses and seperate them in to two lists,  *
 * LHS in one and RHS in other.  The function is_lhs is defined in         *
 * useful.h  Then print the LHS and RHS accesses seperately.               *
 ***************************************************************************/
void process_array_instr_list(array_instr_list * ail) 
{
    array_instr_list lhs_list;
    array_instr_list rhs_list;
    array_instr_list_iter iter(ail);
    while(!iter.is_empty()) {
        in_array * ai = iter.step();
        if(is_lhs(ai)) 
            lhs_list.append(ai);
        else
            rhs_list.append(ai);
    }

    printf("LHS:\n");
    print_array_instr_list(&lhs_list);
    printf("RHS:\n");
    print_array_instr_list(&rhs_list);
}


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


/***************************************************************************
 * Start processing..                                                      *
 ***************************************************************************/
void do_proc(tree_proc * tp)
{
    proc_sym * psym = tp->proc();
    printf("=======%s======= \n", psym->name());
    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);
}

Makefile

TARGET = prog3
LIBS =		-ldependence -lsuifmath -lbuilder -luseful -lsuif -lm
SRCS =		prog3.cc
OBJS =		prog3.o

all:		prog3
install-bin:	install-prog

include $(SUIFHOME)/Makefile.std

Testing the pass

Let's use the following input file:

input3.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> prog3 input3.spd
=======test1=======
For loop i (Outermost)
For loop j
For loop k
LHS:
A[k]
B[i,j]
RHS:
A[k-8]
B[i+1,j]
A[i]
For loop i (Outermost)
For loop j
LHS:
B[i,j]
RHS:
B[i,j]
B[i+1,j]
=======test2=======
For loop k (Outermost)
LHS:
A[k]
RHS:
A[1]
A[k]
A[k-8]
csh>

Go to the previous, next section.