Go to the previous, next section.

Example 5 - Rename Loop Indexes

This is a real SUIF pass with code modification used in our experiments. We wanted a unique and printable identifier for each loop. The loop index variable was the perfect candidate. But since the same variable may be used as the index for many loops, we wrote a pass to update the code and provide a unique variable for all the loop nests.

rename.h

#define MAXDEPTH        64

class rename {
    static int unum;
    var_sym * from_name[MAXDEPTH];
    var_sym * to_name[MAXDEPTH];
    int dep;
    boolean kill_ind_var;
public: 
    rename()                            { dep = 0; 
                                          kill_ind_var = FALSE; }
    void rename_for(tree_proc * tp);
    void rename_for(tree_node_list * tnl);
    void rename_for(tree_node * tn);
    void rename_for(instruction * ins);
    sym_node * rename_for(sym_node *);
    void begin_for(tree_for * tf);
    void finish_for(tree_for * tf);
    var_sym * find_map(var_sym *);
};

rename.cc

#include <stdlib.h>
#include <suif.h>
#include <suifmath.h>
#include <builder.h>
#include "rename.h"

int rename::unum = 0;

void rename::rename_for(tree_proc * tp)
{
    block::set_proc(tp);
    kill_ind_var = (tp->proc()->src_lang() == src_fortran);
    rename_for(tp->body());
}


/***************************************************************************
 * Recurse through the control flow structure renaming loop indices        *
 ***************************************************************************/
void rename::rename_for(tree_node_list * tnl)
{
    tree_node_list_iter iter(tnl);
    while(!iter.is_empty()) {
        tree_node * tn = iter.step();
        rename_for(tn);
    }
}


void rename::rename_for(tree_node * tn)
{
    switch(tn->kind()) {
    case TREE_FOR:
        tree_for * tnf = (tree_for *)tn;
        //printf("For loop %s\n", tnf->index()->name());
        rename_for(tnf->lb_list());
        rename_for(tnf->ub_list());
        rename_for(tnf->step_list());
        begin_for(tnf);
        rename_for(tnf->landing_pad());
        rename_for(tnf->body());
        finish_for(tnf);
        break;
        
    case TREE_IF:
        tree_if * tni = (tree_if *)tn;
        rename_for(tni->header());
        rename_for(tni->then_part());
        rename_for(tni->else_part());
        break;
        
    case TREE_LOOP:
        tree_loop * tnl = (tree_loop *)tn;
        rename_for(tnl->body());
        rename_for(tnl->test());
        break;
        
    case TREE_BLOCK:
        tree_block * tnb = (tree_block *)tn;
        rename_for(tnb->body());
        break;
        
    case TREE_INSTR:
        tree_instr * tnin = (tree_instr *)tn;
        rename_for(tnin->instr());
        break;

    default:
        assert(0);
        break;
    }
}


void rename::rename_for(instruction * ins)
{
    for(int i=0; i<ins->num_srcs(); i++) {
        operand op(ins->src_op(i));
        if(op.is_instr())
            rename_for(op.instr());
        else if(op.is_symbol()) {
            if(op.symbol()->is_var()) {
                var_sym * map = find_map((var_sym *)op.symbol());
                if(map) ins->set_src_op(i, operand(map));
            }
        }
    }
}

/***************************************************************************
 * Starting a for loop, find variable name to rename the index.            *
 ***************************************************************************/
void rename::begin_for(tree_for * tf)
{
    assert(dep < MAXDEPTH);
    from_name[dep] = tf->index();
    
    tree_proc * tp = tf->proc()->block();
    type_node * tn = tf->index()->type();
    char name[64];
    sprintf(name, "%s_%d", tf->index()->name(), unum++);
    to_name[dep] = (var_sym *)tp->symtab()->new_unique_var(tn, name);
    tf->set_index(to_name[dep]);
    dep++;
}


/***************************************************************************
 * Ending a for loop.  If needed, update the original index to curr. value *
 ***************************************************************************/
void rename::finish_for(tree_for * tf)
{
    if(!kill_ind_var) {
        block bf(from_name[dep-1]);
        block bt(to_name[dep-1]);
        block b(bf = bt);
        tree_node * tn = b.make_tree_node();
        tf->parent()->insert_after(tn, tf->list_e());
    }

    dep--;
    assert(dep >= 0);
}


var_sym * rename::find_map(var_sym *v)
{
    for(int i=0; i<dep; i++)
        if(from_name[i] == v) return to_name[i];
    return NULL;
}


/***************************************************************************
 * process each procedure                                                  *
 ***************************************************************************/
void do_proc(tree_proc * tp)
{
    rename R;
    R.rename_for(tp);
}


/***************************************************************************
 *                                                                         *
 ***************************************************************************/
main(int argc, char * argv[])
{ 
    start_suif(argc, argv);
    suif_proc_iter(argc, argv, do_proc, TRUE, TRUE, TRUE);
}    

Makefile

TARGET =	rename
LIBS =	-lbuilder -luseful -lsuif -lm
HEADERS =	rename.h
SRCS =		rename.cc 
OBJS =		rename.o  
all:		rename
install-bin:	install-prog
include $(SUIFHOME)/Makefile.std

Testing the pass

Let's use the following input file:

input5.c

main()
{
    int i, j, k;

    for (i=0; i<10; i++)
	for (j=0; j<10; j++)
	    k = k+1;
    
    for (i=10; i>0; i--)
	k = k-1;
}

Test session

csh> scc -V -.spd input5.c
CPP: /suif/suif/suifhome/mips-dec-ultrix/bin/cpp -D__SCC__ -D__LANGUAGE_C -D__unix 
-D__host_mips -D__mips -D__MIPSEL   -I/suif/suif/suifhome/mips-dec-ultrix/include -nostdinc 
-I/usr/include input5.c /tmp/scc22943_0.i
SNOOT: /suif/suif/suifhome/mips-dec-ultrix/bin/snoot   /tmp/scc22943_0.i /tmp/scc22943_1.snt
PORKY_DEFAULTS: /suif/suif/suifhome/mips-dec-ultrix/bin/porky -defaults
/tmp/scc22943_1.snt input5.spd
csh> rename input5.spd input5.out
csh> s2c input5.out
    [...]
extern int main()
  {
    int i;
    int j;
    int k;
    int i_03;
    int j_14;
    int i_25;

    for (i_03 = 0; i_03 < 10; i_03++)
      {
        for (j_14 = 0; j_14 < 10; j_14++)
          {
            k = k + 1;
          }
        j = j_14;
      }
    i = i_03;
    for (i_25 = 10; i_25 > 0; i_25--)
      {
        k = k - 1;
      }
    i = i_25;
    return 0;
  }
csh>

Go to the previous, next section.