Go to the previous, next section.

# Example 6 - Expand Code for Dependence Testing

This is a simple version of a SUIF pass that is included in the release. This pass was created to solve the following problem.

The SUIF dependence analyzer is a linear affine expression based analyzer. It cannot handle any non-linear array access functions. But when observing real code, we found that there are some simple non-linear access functions that are common in some code. For example,

```do i = 1, 100
A[SKIP*i] = A[SKIP*i-1] ...
enddo
```

where SKIP is a symbolic coefficient variable. We wanted to extend our dependence analyzer to handle these cases. But one complication is that the dependence of the loop varies with the sign of SKIP. When SKIP > 0, there is a true-dependence of (1); when SKIP < 0, there is an anti-dependence of (1); and when SKIP==0, there is no dependence. The best way to handle this was to create three different loop nests for the above single nest.

```if SKIP == 0 then
do i = 1, 100
A[0] = A[-1] ...
enddo
else if SKIP > 0
do i = 1, 100
A[SKIP*i] = A[SKIP*i-1] ...
enddo
else // SKIP < 0
SKIP2 = -SKIP   // SKIP2 > 0
do i = 1, 100
A[-SKIP2*i] = A[-SKIP2*i-1] ...
enddo
endif
```

Since the case of non-linear access functions is not that common, we decided to run a pre-processor before the dependence test to identify the existence of non-linear array access functions and triplicate the enclosing loop nest to reflect the sign of the symbolic coefficients. In this example we'll present this compiler pass which is called PREDEP.

PREDEP executes two passes over each procedure. In the first pass, it will identify the existance of symbolic coefficients and mark the loop nests. In the second pass, all the marked loop nests are triplicated. Communication between the passes is done using annotations. Annotations are also used to communicate information from this pass to the dependence tests run by subsequent passes.

## predep.h

```/**************************************************************************
***                                                                    ***
*** Support for two passes.                                            ***
***                                                                    ***
*** 1) Identify array accesses that have symbolic coefficients         ***
***                                                                    ***
*** 2) Duplicate the loop nests such that in each nest the symbolic    ***
***    coefficient can only be >0, <0 or ==0.                          ***
**************************************************************************/
class depset {
var_sym * vs;               // place-holders used in a map function
operand repl;
public:
depset()                                            {       }

// For the first pass
void find_and_mark(tree_node_list * tnl);
void find_and_mark(tree_node * tn);
void find_and_mark(instruction * ins);
void find_and_mark(in_array *, int i);
void find_and_mark(tree_node * n, in_array * ia, var_sym * v);

void update_annotation(char * annote, suif_object * sa, var_sym * v);

// For the Second pass
void break_loops(tree_node_list * tnl);
void break_loops(tree_node * tn);
void break_loops(instruction * ins);
void replace_var(instruction * ins);
static void each_tree_node(tree_node * tn, void * x);
block mk_blk(base_symtab * bs, tree_node * tn, int mode);
};

extern char * k_break_up;     // local annotation to communicate between passes
extern char * k_depset_done;  // write-back annotation to inform dependence lib
extern char * k_symconst_ok;  // write-back the list of symbolic coefficients
```

## main.cc

```#include <stdlib.h>
#include <time.h>
#include <suif.h>
#include <dependence.h>
#include <builder.h>
#include "predep.h"

char * k_break_up;
char * k_depset_done;
char * k_symconst_ok;

char * timestamp;

/***************************************************************************
* process each procedure                                                  *
***************************************************************************/
void do_proc(tree_proc * tp)
{
// identify the current procedure for the builder
block::set_proc(tp);

immed_list * iml;
// is depset_is_run annotation already in the input procedure??
if(iml = (immed_list *)tp->get_annote(k_depset_done)) {
// if so print when it has been run.
fprintf(stderr,
" Warnning: the input file has previously "
"been processed by predep\n");
immed_list_iter ili(iml);
while(!ili.is_empty())
fprintf(stderr, "   on %s", ili.step().string());
} else
iml = new immed_list;    // empty list

// at the current timestamp to the list of timestamps
iml->append(immed(timestamp));

// put the depset_done annotation on tree_proc so that
// 1) later predep passes will print a warnning message
// 2) dependence library will activate the test when
//    symbolic coefficients are present.
tp->prepend_annote(k_depset_done, iml);

// Create access vectors, need to be run if dependence library is used
fill_in_access(tp);

depset R;

// First pass, identify the loop nests with symbolic coefficients
R.find_and_mark(tp->body());
// Second pass, duplicate those loop nests
R.break_loops(tp->body());
}

/***************************************************************************
* Do initialization, and call the proc iterator                           *
***************************************************************************/
main(int argc, char * argv[])
{
// suif initializer
start_suif(argc, argv);

// initialize a local annotation used to communicate between the 2 passes
ANNOTE(k_break_up, "breakup", FALSE);
// initilize the written-back annotation to communicate with later passes
// (running predep again and calls to the dependence library)
ANNOTE(k_depset_done, "depset_is_run", TRUE);
// If a symbolic coefficient was processed, write that fact down at the
// outermost loopnest to help the dependence checker.
ANNOTE(k_symconst_ok, "depset_symconst_ok", TRUE);

// create a time-stamp
time_t tm;
tm = time(NULL);
timestamp = ctime(&tm);

// iterate over all the procedures in the input files and
// produce output files.
suif_proc_iter(argc, argv, do_proc, TRUE, TRUE, TRUE);
}
```

## find.cc

```#include <stdlib.h>
#include <suif.h>
#include <suifmath.h>
#include <builder.h>
#include <dependence.h>
#include "predep.h"

/***************************************************************************
***************************************************************************
****   First Pass                                                       ***
***************************************************************************
***************************************************************************/

tree_for *is_index(var_sym * v, tree_node *tn);  // defined in dependence lib
tree_for *find_inner(tree_node *n, var_sym * v); // defined in dependence lib
tree_for *find_outermost(tree_node *n);          // defined below

/***************************************************************************
* Iterate over a tree_node_list (see find_and_mark(tree_node *))          *
***************************************************************************/
void depset::find_and_mark(tree_node_list * tnl)
{
tree_node_list_iter iter(tnl);
while(!iter.is_empty()) {
tree_node * tn = iter.step();
find_and_mark(tn);
}
}

/***************************************************************************
* Iterate over all the control flow structure and call                    *
* find_and_mark(instruction *) on each expression tree                    *
***************************************************************************/
void depset::find_and_mark(tree_node * tn)
{
switch(tn->kind()) {
case TREE_FOR:
tree_for * tnf = (tree_for *)tn;
find_and_mark(tnf->lb_list());
find_and_mark(tnf->ub_list());
find_and_mark(tnf->step_list());
find_and_mark(tnf->body());
break;

case TREE_IF:
tree_if * tni = (tree_if *)tn;
find_and_mark(tni->then_part());
find_and_mark(tni->else_part());
break;

case TREE_LOOP:
tree_loop * tnl = (tree_loop *)tn;
find_and_mark(tnl->body());
find_and_mark(tnl->test());
break;

case TREE_BLOCK:
tree_block * tnb = (tree_block *)tn;
find_and_mark(tnb->body());
break;

case TREE_INSTR:
tree_instr * tnin = (tree_instr *)tn;
find_and_mark(tnin->instr());
break;

default:
assert(0);
break;
}
}

/***************************************************************************
* Iterate over the expression tree. When an array instruction is found    *
* check if any of the access functions are non-linear expressions.        *
* if so call find_and_mark(in_array *, int) with the array instruction    *
* and the array dimension where the access function is non-linear.        *
***************************************************************************/
void depset::find_and_mark(instruction * ins)
{
for(int i=0; i<ins->num_srcs(); i++) {
operand op(ins->src_op(i));
if(op.is_instr()) {
find_and_mark(op.instr());
if(op.instr()->opcode() == io_array) {
in_array * ina = (in_array *)op.instr();
array_info *ai = new array_info(ina, TRUE);

array_info_iter iter(ai);
int i = 0;
while(!iter.is_empty()) {
access_vector * av = iter.step();
if(av->too_messy) {
find_and_mark(ina, i);
}
i++;
}
}
}
}
}

/***************************************************************************
* Convert the access function to a linear inequality with symbolic        *
* coefficients.  If the access function cannot be converted into a liner  *
* ineq with symbolic coefficients, it is beyond the dependence analizer's *
* scope; thus give-up on that access                                      *
* Find all the symbolic coefficients and mark the outermost loopnest so   *
* that the next pass will duplicate the nests to handle the symbolic      *
* coefficients correctly                                                  *
* (calls find_and_mark(tree_node * n, in_array *, var_sym *v))            *
***************************************************************************/
void depset::find_and_mark(in_array * ina, int i)
{
operand op(ina->index(i));
assert(op.is_instr()); // otherwise cannot be too messy
instruction * acc = op.instr();
named_symcoeff_ineq * ineq;
ineq = named_symcoeff_ineq::convert_exp(acc);
if(ineq) {
ineq->print_exp();
for(int i=1; i<ineq->p(); i++)
find_and_mark(ina->parent(), ina, ineq->planes()[i].var());
} else
printf("Too messy\n");
}

/***************************************************************************
* Find the outermost for loop and mark it with a annotation so that the   *
* 2nd pass will duplicate the loop.                                       *
* The annotation has a list of variable symbols that are used as symbolic *
* coefficients within the loop nest                                       *
***************************************************************************/
void depset::find_and_mark(tree_node * n, in_array * ina, var_sym * v)
{
// if symbolc coefficient is a outer loop nest\'s induction variable.
if(is_index(v, n)) return;

// if symbolic coefficient is modified within the loop nest.
if(find_inner(n, v)) return;

// find the outermost loop nest
tree_node * tn = find_outermost(n);
assert(tn);

// make the annotation that marks break_up
update_annotation(k_break_up, tn, v);

// annotate the array instruciton with the symbolic coefficient name
update_annotation(k_symconst_ok, ina, v);
}

/***************************************************************************
* Annotation update:                                                      *
* If an annotation with a given name exist in the suif object update it   *
* otherwise create a new one.  If an annotation exist, check if the       *
* variable name is already in it; if not add the name to the list.        *
***************************************************************************/
void depset::update_annotation(char * ann, suif_object * sa, var_sym * v)
{
immed_list * il = (immed_list *)sa->get_annote(ann);
// there will be no annotation if v is the first var found.
// thus create a new list
if(il == NULL) il = new immed_list;

// Entries in the list should be unique, check if v is already in the list
immed_list_iter iter(il);
boolean found = FALSE;
while(!iter.is_empty())
if(iter.step().symbol() == v) found = TRUE;
// if not in the list, add v to the list
if(!found)
il->append(immed(v));

// Put back the updated annotation
sa->prepend_annote(ann, il);
}

/***************************************************************************
* Find the outermost for loop                                             *
***************************************************************************/
tree_for *find_outermost(tree_node *n)
{
tree_for * outermost = NULL;

while(n) {
if(n->kind() == TREE_FOR)
outermost = (tree_for *)n;
n = (n->parent())?n->parent()->parent():NULL;
}

return outermost;
}
```

## breakup.cc

```#include <stdlib.h>
#include <suif.h>
#include <suifmath.h>
#include <builder.h>
#include <dependence.h>
#include "predep.h"

/***************************************************************************
***************************************************************************
****   Second Pass                                                      ***
***************************************************************************
***************************************************************************/

/***************************************************************************
* Go through  the tree node list, if any tree_node in the list is have an *
* duplicate annotation (with a symbolic coefficient variable), duplicate  *
* the body three times, create a construct such that each body will       *
* represent symconst==0, symconst>0 and symconst<0.                       *
***************************************************************************/
void depset::break_loops(tree_node_list * tnl)
{
tree_node_list_iter iter(tnl);
// iterate over tree node list
while(!iter.is_empty()) {
tree_node * tn = iter.step();
immed_list * il = (immed_list *)tn->get_annote(k_break_up);
// if a break_up annotation exist and the annotation has at least
// one symconst entry in it?
if(il && (il->count())) {
// take the first symbolic coefficient variable and put the rest back
immed im(il->pop());
tn->prepend_annote(k_break_up, il);
vs = (var_sym *)im.symbol();

// the scope of the current tree_node
base_symtab * bs = tn->scope();
assert(bs->is_block());

// use builder (blocks) to create the resulting code
// triplicate the tree_node (0, 1, -1 is the sign of symconst
block bl_zero(mk_blk(bs, tn, 0));
block bl_pos(mk_blk(bs, tn, 1));
block bl_neg(mk_blk(bs, tn, -1));

// placeholder for symbolic coefficient variable (vs)
block var(vs);
// the conditional that triplicate the tree_node into
// symconst==0, symconst>0 and symconst<0
block code(block::IF(var == block(0),
bl_zero,
block::IF(var > block(0),
bl_pos,
bl_neg)));

// create suif code out of the builder structure
tree_node * new_tn = code.make_tree_node((block_symtab *)bs);

// insert the suif code just before the current block.
// read suif/glist.h to understand how to do this insertion
// into the list
tnl->insert_after(new_tn, iter.cur_elem());

// remove the old tree_node (now it is in there from the
// above structure);
tnl->remove(iter.cur_elem());

delete tn;

// recusively go through the newly created structure (because
// the iterator will not do it)
break_loops(new_tn);

} else
break_loops(tn);    // no break-up found
}
}

/***************************************************************************
* Recursively go through the structured control flow and perform break-up *
***************************************************************************/
void depset::break_loops(tree_node * tn)
{
switch(tn->kind()) {
case TREE_FOR:
tree_for * tnf = (tree_for *)tn;
break_loops(tnf->body());
break;

case TREE_IF:
tree_if * tni = (tree_if *)tn;
break_loops(tni->then_part());
break_loops(tni->else_part());
break;

case TREE_LOOP:
tree_loop * tnl = (tree_loop *)tn;
break_loops(tnl->body());
break;

case TREE_BLOCK:
tree_block * tnb = (tree_block *)tn;
break_loops(tnb->body());
break;

case TREE_INSTR:
break;

default:
assert(0);
break;
}
}

/***************************************************************************
* Create a new tree_node (in the builder's block form) using the the      *
* tree_node.  The base symtab (bs) indicate where that block will be      *
* inserted in the original code (this is needed to do cloneing of symbol  *
* tables, symbols and types etc.)                                         *
* Mode will indicate if the resulting block will represent (vs==0),       *
* (vs>0) or (vs<0).                                                       *
* A new variable is created to reflect this fact, and the old vs is       *
* substituted by this new variable.                                       *
* When vs==0 vs is subsituted by 0, otherwise it is substitiuted by the   *
* new variable which is always >0                                         *
***************************************************************************/
block depset::mk_blk(base_symtab * bs, tree_node * tn, int mode)

{
char nm[128];
// name of the new variable
sprintf(nm, "%s_%s",vs->name(), (mode)?((mode>0)?"pos":"neg"):"zero");
// create a new variable
block n_s(block::new_sym(cst_int, nm));
// placeholder for the old symconst variable
block o_s(vs);
// two new blocks
block assign;
block replace;

// according to the mode create the replacement for symconst and
// the initialization of the new variable. Note that assign.set()
// is used insted of assign =  because (block = block) will create
// a new block that represents a C equal operator(i.e. = is overloaded)
if(mode == 0) {
assign.set(n_s = block(0));
replace.set(block(0));
} else if(mode > 0) {
assign.set(n_s = o_s);
replace.set(block(1)*n_s);
} else {
assign.set(n_s = block(-1)*o_s);
replace.set(block(-1)*n_s);
}

// create the suif code for replacement and set the repl operand to
// the resulting instruction.
instruction * ins = replace.make_instruction((block_symtab *)bs);
repl.set_instr(ins);

// clone the tree_node and replace all the sym consts's in the
// new tree node with the replacement
tree_node * tnx = tn->clone(bs);
tnx->map(each_tree_node, this);

// add the initialization of the new variable
block code(block::statement(assign, block(tnx, FALSE)));
return code;
}

/***************************************************************************
* Map function for structured control flow, when a tree instruction is    *
* found, call replace_var().                                              *
***************************************************************************/
void depset::each_tree_node(tree_node * tn, void * x)
{
depset * ds = (depset *) x;
if(tn->kind() == TREE_INSTR) {
tree_instr * ti = (tree_instr *)tn;
instruction * inst = ti->instr();
ds->replace_var(inst);
}
}

/***************************************************************************
* Recurse over the expression tree. Check if any operand is a symbolic    *
* coefficient variable, if so replace it with the repl operand.           *
***************************************************************************/
void depset::replace_var(instruction * ins)
{
for(int i=0; i<ins->num_srcs(); i++) {
operand op(ins->src_op(i));
if(op.is_instr())
replace_var(op.instr());
else if(op.is_symbol() && (op.symbol() == vs)) {
op.remove();
ins->set_src_op(i, repl.clone());
}
}
}
```

## Makefile

```TARGET =	predep
LIBS= -ldependence -lsuifmath -lbuilder -luseful -lsuif -lm
EXPORTS =
YSRCS =
CSRCS =
SRCS =		main.cc find.cc breakup.cc
OBJS =		main.o  find.o  breakup.o
EXTRA_YFLAGS =
EXTRA_CFLAGS =
EXTRA_CXXFLAGS =

all:		predep
install-bin:	install-prog

include \$(SUIFHOME)/Makefile.std
```

## Testing the pass

### input6.c

```double A[1000];

test(int SKIP)
{
int i;
for(i=1; i<=100; i++)
A[SKIP*i] = A[SKIP*i-1];
}
```

### Test session

```csh> scc -.spd input6.c
csh> predep input6.spd input6.sfo
SKIP*i >= 0
-1+SKIP*i >= 0
csh> printsuif input6.sfo > input6.sfo.txt
```

Here is the text version of the suif output. Note that there are annotations depset_is_run and depset_symconst_ok installed in the output.

### test.sfo.txt

```    ****************** GLOBALS ******************
Global symbol table: `globals'
........

****************** FILE test.sfo ******************
["history": "/suif/suif/suifhome/mips-dec-ultrix/bin/snoot /tmp/scc13049_0.i
/tmp/scc13049_1.snt"]
["history": "/suif/suif/suifhome/mips-dec-ultrix/bin/porky -defaults /tmp/sc
c13049_1.snt test.spd"]
["history": "predep test.spd test.sfo"]
["history": "printsuif test.sfo"]
File symbol table: `test.sfo'
........

PROC P:.test
["depset_is_run": "Sat Apr 23 15:23:23 1994"]
Procedure symbol table: `test'
Types:
<None>
Symbols:
........

1: mrk
["line": 6 "test.c"]
27: IF (Jumpto=L:test.__BLDR_4)
28:   bfalse  e1, L:test.__BLDR_4
29:     e1: seq t:g4 (i.32) test.SKIP, e2
30:       e2: ldc t:g4 (i.32) 0
IF THEN
31:   ldc t:g4 (i.32) test.SKIP_zero2 = 0
32:   FOR (Index=test.i Test=SLTE Cont=L:test.L1_1 Brk=L:test.L2_1)
FOR LB
50:     ldc t:g17 (i.32) 1
FOR UB
52:     ldc t:g17 (i.32) 100
FOR STEP
54:     ldc t:g17 (i.32) 1
FOR BODY
33:     mrk
["line": 6 "test.c"]
34:     mrk
["line": 6 "test.c"]
35:     mrk
["line": 7 "test.c"]
36:     memcpy  e1 = e2
37:       e1: array t:g35 (p.32) e3+0, size(64), index(e4), bound(e5)
["depset_symconst_ok": <test.SKIP,0>]
38:         e3: ldc t:g34 (p.32) <.A,0>
39:         e4: mul t:g17 (i.32) e6, test.i
40:           e6: ldc t:g4 (i.32) 0
41:         e5: ldc t:g4 (i.32) 1000
42:       e2: array t:g35 (p.32) e7+0, size(64), index(e8), bound(e9)
["depset_symconst_ok": <test.SKIP,0>]
43:         e7: ldc t:g34 (p.32) <.A,0>
44:         e8: sub t:g17 (i.32) e10, e11
45:           e10: mul t:g17 (i.32) e12, test.i
46:             e12: ldc t:g4 (i.32) 0
47:           e11: ldc t:g17 (i.32) 1
48:         e9: ldc t:g4 (i.32) 1000
FOR END
IF ELSE
55:   IF (Jumpto=L:test.__BLDR_3)
56:     bfalse  e1, L:test.__BLDR_3
57:       e1: sl t:g4 (i.32) e2, test.SKIP
58:         e2: ldc t:g4 (i.32) 0
IF THEN
59:     cpy t:g4 (i.32) test.SKIP_pos3 = e1
60:       e1: cvt t:g4 (i.32) test.SKIP
61:     FOR (Index=test.i Test=SLTE Cont=L:test.L1_2 Brk=L:test.L2_2)
FOR LB
81:       ldc t:g17 (i.32) 1
FOR UB
83:       ldc t:g17 (i.32) 100
FOR STEP
85:       ldc t:g17 (i.32) 1
FOR BODY
62:       mrk
["line": 6 "test.c"]
63:       mrk
["line": 6 "test.c"]
64:       mrk
["line": 7 "test.c"]
65:       memcpy  e1 = e2
66:         e1: array t:g35 (p.32) e3+0, size(64), index(e4), bound(e5)
["depset_symconst_ok": <test.SKIP,0>]
67:           e3: ldc t:g34 (p.32) <.A,0>
68:           e4: mul t:g17 (i.32) e6, test.i
69:             e6: mul t:g4 (i.32) e7, test.SKIP_pos3
70:               e7: ldc t:g4 (i.32) 1
71:           e5: ldc t:g4 (i.32) 1000
72:         e2: array t:g35 (p.32) e8+0, size(64), index(e9), bound(e10)
["depset_symconst_ok": <test.SKIP,0>]
73:           e8: ldc t:g34 (p.32) <.A,0>
74:           e9: sub t:g17 (i.32) e11, e12
75:             e11: mul t:g17 (i.32) e13, test.i
76:               e13: mul t:g4 (i.32) e14, test.SKIP_pos3
77:                 e14: ldc t:g4 (i.32) 1
78:             e12: ldc t:g17 (i.32) 1
79:           e10: ldc t:g4 (i.32) 1000
FOR END
IF ELSE
86:     mul t:g4 (i.32) test.SKIP_neg4 = e1, test.SKIP
87:       e1: ldc t:g4 (i.32) -1
88:     FOR (Index=test.i Test=SLTE Cont=L:test.L1_3 Brk=L:test.L2_3)
FOR LB
108:       ldc t:g17 (i.32) 1
FOR UB
110:       ldc t:g17 (i.32) 100
FOR STEP
112:       ldc t:g17 (i.32) 1
FOR BODY
89:       mrk
["line": 6 "test.c"]
90:       mrk
["line": 6 "test.c"]
91:       mrk
["line": 7 "test.c"]
92:       memcpy  e1 = e2
93:         e1: array t:g35 (p.32) e3+0, size(64), index(e4), bound(e5)
["depset_symconst_ok": <test.SKIP,0>]
94:           e3: ldc t:g34 (p.32) <.A,0>
95:           e4: mul t:g17 (i.32) e6, test.i
96:             e6: mul t:g4 (i.32) e7, test.SKIP_neg4
97:               e7: ldc t:g4 (i.32) -1
98:           e5: ldc t:g4 (i.32) 1000
99:         e2: array t:g35 (p.32) e8+0, size(64), index(e9), bound(e10)
["depset_symconst_ok": <test.SKIP,0>]
100:           e8: ldc t:g34 (p.32) <.A,0>
101:           e9: sub t:g17 (i.32) e11, e12
102:             e11: mul t:g17 (i.32) e13, test.i
103:               e13: mul t:g4 (i.32) e14, test.SKIP_neg4
104:                 e14: ldc t:g4 (i.32) -1
105:             e12: ldc t:g17 (i.32) 1
106:           e10: ldc t:g4 (i.32) 1000
FOR END
IF END
IF END
23: mrk
["line": 6 "test.c"]
24: mrk
["line": 8 "test.c"]
25: ret  e1
26:   e1: ldc t:g17 (i.32) 0
PROC END
```

Go to the previous, next section.