optimize.c

雏形java的解释器源码。配合flex和bison可以工作

{ if (c==NULL) return 0;
  return is_goto(c,label) || is_ifeq(c,label) || is_ifne(c,label) || 
         is_if_acmpeq(c,label) || is_if_acmpne(c,label) || 
         is_ifnull(c,label) || is_ifnonnull(c,label) ||
         is_if_icmpeq(c,label) || is_if_icmpgt(c,label) || 
         is_if_icmplt(c,label) || is_if_icmple(c,label) || 
         is_if_icmpge(c,label) || is_if_icmpne(c,label);
}

LABEL *currentlabels;   /* points to current labels table */
LABEL **currentlabelstable; /* pointer to field in AST 
			       pointing to labels table */
int currentlabelstablesize;
int _label; /* current offset of last used label */

CODE *destination(int label)
{ return currentlabels[label].position;
}

int copylabel(int label)
{ currentlabels[label].sources++;
  return label;
}

void droplabel(int label)
{ currentlabels[label].sources--;
}

int deadlabel(int label)
{ return currentlabels[label].sources==0;
}

int uniquelabel(int label)
{ return currentlabels[label].sources==1;
}

/* returns next available index into label table.  If the table is full
 * it doubles the size of the table, copying old entries into the new table
 * and then fixing the pointer from the AST to this new table.
 */  
int next_label()
{ int i;
    
  _label++;
  if (_label==currentlabelstablesize)
    { /* allocate new table, double the size */ 
      currentlabels=Malloc(currentlabelstablesize*2*sizeof(LABEL));
      /* copy entries to new table */
      for (i=0;i<currentlabelstablesize;i++)
        currentlabels[i]=(*currentlabelstable)[i];
      currentlabelstablesize*=2;
      /* fixup pointer in AST to new table */
      *currentlabelstable=currentlabels;
    }
  return(_label);
}


/* inserts a new entry in label table */
void INSERTnewlabel(int i,char* name,CODE *target,int count)
{ currentlabels[i].name = name;
  currentlabels[i].position = target;
  currentlabels[i].sources = count;
}


/***** Helper functions to replace k instructions starting at at c by 
       the sequence of Code pointed to by r.   *****/

/* Replaces a sequence of instructions by another.  WARNING: Make sure the
 * k instructions you are removing cannot be branched into from pieces of code 
 * outside of the part you are removing.
 * If you remove instructions that branch to a label you must explicitly
 * do a droplabel for them.  (see replace_modified below that will do this
 * automatically for you)
 */ 
int replace(CODE **c, int k, CODE *r)
{ CODE *p;
  int i;
  p = *c;
  for (i=0; i<k; i++) p=p->next;
  if (r==NULL) {
     *c = p;
  } else {
     *c = r;
     while (r->next!=NULL) r=r->next;
     r->next = p;
  }
  return 1;
}

/*  
 *  Replace_modified - replaces a sequence of instructions by another one
 *  Changes have been made to automatically drop labels if needed.
 */
int replace_modified(CODE **c, int k, CODE *r)
{ CODE *p;
  int i;
  p = *c;
 for (i=0; i<k; i++) {
   int label;
   if (uses_label(p, &label) && !deadlabel(label))
     droplabel(label);
   p=p->next;
  }
  if (r==NULL) {
      *c = p;
    }
  else {
    *c = r;
    while (r->next!=NULL) r=r->next;
    r->next = p;
  }
  return 1;
}
 
/*
 * kill_line - simply removes the line *c from the bytecode, drops labels
 *             if needed.
 */
int kill_line(CODE **c)
{
  return replace_modified(c,1,NULL);
}

/*
 * stack_effect -  computes three quantities given a line of code:
 * 1. inc contains the height difference of the stack after the operation.
 * 2. affected contains the lowest element on the stack affected by this 
 *    bytecode.
 * 3. used contains the lowest element on the stack used by this bytecode 
 * (Positions are relative to the starting point).
 * e.g
 * For a swap operation inc=0, affected = -2, used=-2.
 * For a load operation, inc=+1, affected = 0, used=0.
 * For a dup operation, inc=1, affected=0, used=-1. 
 *
 * Note that we always have :
 * used<=affected.
 * affected<=0
 *
 * The return value of the function tell the user if the the code is of 
 * a type which might invalidate stack analysis:
 * 0: normal
 * 1: goto
 * 2: comparison
 * 3: label
 * 4: return
 */

int stack_effect(CODE *c, int *inc, int *affected, int *used)
{
  char *stringpos;
  if(c!=NULL) {
    
  switch(c->kind) {
    case nopCK:
	case iincCK:
      *inc=*used=*affected=0;
      break;
      
	case instanceofCK:
    case getfieldCK:	
    case i2cCK:
    case inegCK:
      *inc=0;
      *used=*affected=-1;
      break;
      
    case checkcastCK:
      *inc = *affected =0;
      *used= -1;
      break;
    
    case swapCK:
      *inc=0;
      *used=*affected=-2;
      break;

    case labelCK:
      *inc=*used=*affected=0;
      return 3;
      break; 
      
    case newCK:
    case iloadCK:
    case aloadCK:
    case ldc_intCK:
    case ldc_stringCK:
    case aconst_nullCK:
      *inc = +1;
      *affected=*used=0;
      break;
      
    case dupCK:
      *inc=1;
      *affected=0;
      *used=-1;
      break;
      
    case popCK:	
    case istoreCK:
    case astoreCK:
      *inc=*used=*affected= -1;
      break;

    case iremCK:
    case isubCK:
    case idivCK:
    case iaddCK:
    case imulCK:
      *inc=-1;
      *used=*affected=-2;
      break;
      
    case putfieldCK:
      *used=*affected=*inc = -2;
      break;
      
    case invokevirtualCK:
    case invokenonvirtualCK:
      *inc=-1; /* receiver */
      if(c->kind==invokevirtualCK)
        stringpos = c->val.invokevirtualC;
      else
        stringpos = c->val.invokenonvirtualC;
      
      while((*stringpos) != '(') stringpos++;
      stringpos++;

      /* one for each formal */
      while((*stringpos) != ')') {
        (*inc)--;
        if((*stringpos)=='L')
          while((*stringpos)!=';') stringpos++;
        stringpos++;
      }
      stringpos++;

      *used = *affected = *inc;	

      /* if not void, then pushes return value */
      if((*stringpos)!='V')
        (*inc)++;
      break;
      
    case gotoCK:
      *used = *affected = *inc =0;
      return 1;
      break;
      
    case ifeqCK:
    case ifneCK:
    case ifnullCK:
    case ifnonnullCK:
      *inc = *used = *affected = -1;
      return 2;
      break;
      
    case if_icmpeqCK:
    case if_icmpneCK:
    case if_icmpgtCK:
    case if_icmpltCK:
    case if_icmpleCK:
    case if_icmpgeCK:
    case if_acmpeqCK:
    case if_acmpneCK:
      *inc = *used = *affected = -2;
      return 2;
      break;
      
    case returnCK:
      *inc = *used = *affected = 0;
      return 4;
    case areturnCK:
    case ireturnCK:
      *inc = *used = *affected = -1;
      return 4;
      break;
      
    default:
      printf("Stack_Effect: unrecognized code kind\n");
      *inc=*used=*affected=0;
      break;
    }
  }
  return 0;  
}

typedef int(*OPTI)(CODE **);

/*************************  MAIN OPTIMIZATION LOOP **********************/

int add_pattern(char *name, OPTI pattern);

#define ADD_PATTERN(x) add_pattern(#x, x)

/* Here is a null_pattern that is usefull as a place holder in your array. */
int null_pattern(CODE **c)  { return 0; }

/* Your patterns get included here */
#include "patterns.h"

/* Fabien: modifications to improve peephole framework */
/* Fall00 and before: optimization and OPTS were defined in patterns.h */

#ifndef OPTS

#define MAX_PATTERNS 100

char *opti_name[MAX_PATTERNS]; /* name of the patterns */
OPTI optimization[MAX_PATTERNS];
int frequencies[MAX_PATTERNS];
int OPTS = 0;

int add_pattern(char *name, OPTI pattern)
{
	if (OPTS > MAX_PATTERNS) {
		printf ("cannot add any more pattern");
		return 0;
	}
	opti_name[OPTS] = name;
	optimization[OPTS] = pattern;
	OPTS++;
	return 1;
}
#else
int frequencies[OPTS];
/* dummy add_pattern, because it should not be used in that case */
int add_pattern(char *name, OPTI pattern) {return 0;}
#endif /* ifndef OPTS */


int optiCHANGE;

void optiCODEtraverse(CODE **c)
{ int i,change;
  change = 1;
  if (*c!=NULL) {
     while (change) {
       change = 0;
       for (i=0; i<OPTS; i++) {
	  int optimized;
	  optimized = optimization[i](c);
	  if (optimized) frequencies[i]++;
          change = change | optimized;
       }
       optiCHANGE = optiCHANGE || change;
     }
     if (*c!=NULL) optiCODEtraverse(&((*c)->next));
  }
} 

void optiCODE(CODE **c)
{ optiCHANGE = 1;
  while (optiCHANGE) {
    optiCHANGE = 0;
    optiCODEtraverse(c);
  }
}

void optiPROGRAMrec(PROGRAM *p)
{ if (p!=NULL) {
    optiPROGRAMrec(p->next);
    optiCLASSFILE(p->classfile);
  }
}

void optiPROGRAM(PROGRAM *p)
{
  int i;
  for(i = 0; i < OPTS; i++)
    frequencies[i] = 0;

#ifndef OPTS
  init_patterns();
#endif
  
  if (p!=NULL) {
    optiPROGRAMrec(p->next);
    optiCLASSFILE(p->classfile);
  }

  printf("\nFrequencies:\n");
  for(i = 0; i < OPTS; i++)
#ifdef OPTS
      printf("%d\t", frequencies[i]);
#else
      printf("%s: %d\n", opti_name[i], frequencies[i]);
#endif
  
  printf("\n");
}

void optiCLASSFILE(CLASSFILE *c)
{ if (c!=NULL) {
     optiCLASSFILE(c->next);
     optiCLASS(c->class);
  }
}

void optiCLASS(CLASS *c)
{ if (!c->external) {
     optiCONSTRUCTOR(c->constructors);
     optiMETHOD(c->methods);
  }
}

void optiCONSTRUCTOR(CONSTRUCTOR *c)
{ if (c!=NULL) {
     optiCONSTRUCTOR(c->next);
     currentlabels = c->labels;
     currentlabelstable = &(c->labels);
     currentlabelstablesize = c->labelcount;
     _label=currentlabelstablesize-1;
     optiCODE(&c->opcodes);
     /* Feng fix */
     c->labelcount=_label+1;
  }
}

void optiMETHOD(METHOD *m)
{ if (m!=NULL) {
     optiMETHOD(m->next);
     currentlabels = m->labels;
     currentlabelstable = &(m->labels);
     currentlabelstablesize = m->labelcount;
     _label=currentlabelstablesize-1;
     optiCODE(&m->opcodes);
     /* Feng fix */
     m->labelcount=_label+1;
  }
}