Go to the previous, next section.
At each outermost loop nest, this pass will print all the true, anti and output dependence vectors for each array write access.
#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.
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];
}
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.