range.c

/*  $VER: vbcc (range.c) $Revision: 1.1 $    */
/*  range analysis and related optimizations */

#include "opt.h"

static char FILE_[]=__FILE__;


#define RANGESIZE (sizeof(range)*(vcount+1))

range *rangebuf;

static void clear_range(range *p,int i)
{
  Var *v;
  int t;

  v=vilist[i];
  t=v->vtyp->flags;
  if(ISINT(t)){
    if(t&UNSIGNED){
      p[i].min.vumax=Z0;
      p[i].max.vumax=tu_max[t&NQ];
    }else{
      p[i].min.vmax=t_min[t&NQ];
      p[i].max.vmax=t_max[t&NQ];
    }
  }
}

void print_ranges(FILE *f,range *p)
{
  int i,t;
  Var *v;
  for(i=0;i<vcount-rcount;i++){
    v=vilist[i];
    t=v->vtyp->flags;
    if(ISINT(t)){
      fprintf(f,"%03d %s (%p): ",i,v->identifier,v);
      if(t&UNSIGNED){
	printzum(f,p[i].min.vumax);
	fprintf(f,"...");
	printzum(f,p[i].max.vumax);
      }else{
	printzm(f,p[i].min.vmax);
	fprintf(f,"...");
	printzm(f,p[i].max.vmax);
      }
      fprintf(f,"\n");
    }
  }
}

static void combine_ranges(range *d,range *n)
{
  int i,t;
  Var *v;
  for(i=0;i<vcount-rcount;i++){
    v=vilist[i];
    t=v->vtyp->flags;
    if(ISINT(t)){
      if(t&UNSIGNED){
	if(zumleq(n[i].min.vumax,d[i].min.vumax))
	  d[i].min.vumax=n[i].min.vumax;
	if(zumleq(d[i].max.vumax,n[i].max.vumax))
	  d[i].max.vumax=n[i].max.vumax;
      }else{
	if(zmleq(n[i].min.vmax,d[i].min.vmax))
	  d[i].min.vmax=n[i].min.vmax;
	if(zmleq(d[i].max.vmax,n[i].max.vmax))
	  d[i].max.vmax=n[i].max.vmax;
      }
    }
  }
}

static int update_ranges(range *d,range *n)
{
  int i,t,change=0;
  Var *v;
  for(i=0;i<vcount-rcount;i++){
    v=vilist[i];
    t=v->vtyp->flags;
    if(ISINT(t)){
      if(t&UNSIGNED){
	if(!zumeqto(n[i].min.vumax,d[i].min.vumax)){
	  d[i].min.vumax=n[i].min.vumax;
	  change=1;
	}
	if(!zumeqto(d[i].max.vumax,n[i].max.vumax)){
	  d[i].max.vumax=n[i].max.vumax;
	  change=1;
	}
      }else{
	if(!zmeqto(n[i].min.vmax,d[i].min.vmax)){
	  d[i].min.vmax=n[i].min.vmax;
	  change=1;
	}
	if(!zmeqto(d[i].max.vmax,n[i].max.vmax)){
	  d[i].max.vmax=n[i].max.vmax;
	  change=1;
	}
      }
    }
  }
  return change;
}

void do_ranges(range *d,IC *p)
{
  int i,j,t,c=p->code;
  if((p->z.flags&(VAR|DREFOBJ))==VAR){
    i=p->z.v->index;
    t=p->z.v->vtyp->flags;
    if(c==ASSIGN){
      if((p->typf&NU)!=(t&NU)){
	clear_range(d,i);
      }else if((p->q1.flags&(KONST|DREFOBJ))==KONST){
	eval_const(&p->q1.val,t);
	if(t&UNSIGNED)
	  d[i].min.vumax=d[i].max.vumax=vumax; 
	else
	  d[i].min.vmax=d[i].max.vmax=vmax; 
      }else if((p->q1.flags&(VAR|DREFOBJ))==VAR&&(p->q1.v->vtyp->flags&NU)==(t&NU)){
	j=p->q1.v->index;
	d[i].min=d[j].min;
	d[i].max=d[j].max;
      }else
	clear_range(d,i);
    }else{
      clear_range(d,i);
    }
  }else{
    j=p->change_cnt;
    for(i=0;i<j;i++){
      if(!(p->change_list[i].flags&DREFOBJ))
	clear_range(d,p->change_list[i].v->index);
    }
  }
}

static void insert_max(range *p,int t)
{
  if(t&UNSIGNED){
    if(!zumleq(p->max.vumax,vumax))
      p->max.vumax=vumax;
    if(!zumleq(p->min.vumax,p->max.vumax))
      p->min.vumax=vumax;
  }else{
    if(!zmleq(p->max.vmax,vmax))
      p->max.vmax=vmax;
    if(!zmleq(p->min.vmax,p->max.vmax))
      p->min.vmax=vmax;
  }
}

static void insert_min(range *p,int t)
{
  if(t&UNSIGNED){
    if(!zumleq(vumax,p->min.vumax))
      p->min.vumax=vumax;
    if(!zumleq(p->min.vumax,p->max.vumax))
      p->max.vumax=vumax;
  }else{
    if(!zmleq(vmax,p->min.vmax))
      p->min.vmax=vmax;
    if(!zmleq(p->min.vmax,p->max.vmax))
      p->max.vmax=vmax;
  }
}

static void inc_val(int t)
{
  if(t&UNSIGNED){
    if(!zumeqto(vumax,tu_max[t&NU]))
      vumax=zumadd(vumax,ZU1);
  }else{
    if(!zmeqto(vmax,t_max[t&NU]))
      vmax=zmadd(vmax,Z1);
  }
}

static void dec_val(int t)
{
  if(t&UNSIGNED){
    if(!zumeqto(vumax,ZU0))
      vumax=zumsub(vumax,ZU1);
  }else{
    if(!zmeqto(vmax,t_min[t&NU]))
      vmax=zmsub(vmax,Z1);
  }
}

void range_analysis(flowgraph *fg)
{
  flowgraph *g;
  range *bp,*erange,*crange;
  Var *v;
  int i,t,done,pass;
  rangebuf=mymalloc(RANGESIZE*(2*basic_blocks+3));
  bp=rangebuf;
  for(i=0;i<vcount-rcount;i++)
    clear_range(bp,i);
  erange=bp;
  bp+=RANGESIZE;
  for(g=fg;g;g=g->normalout){
    g->ra_normalout=bp;
    memcpy(bp,erange,RANGESIZE);
    bp+=RANGESIZE;
    g->ra_branchout=bp;
    memcpy(bp,erange,RANGESIZE);
    bp+=RANGESIZE;
  }
  crange=bp;

  pass=1;
  do{
    if(DEBUG&1024) printf("range analysis pass %d\n",pass);
    done=1;
    for(g=fg;g;g=g->normalout){
      flowlist *lp;
      IC *p;
      int c,first=1;
      memcpy(crange,erange,RANGESIZE);
      for(lp=g->in;lp;lp=lp->next){
	if(lp->graph->normalout==g&&(!lp->graph->end||lp->graph->end->code!=BRA)){
	  if(first){
	    memcpy(crange,lp->graph->ra_normalout,RANGESIZE);
	    first=0;
	  }else
	    combine_ranges(crange,lp->graph->ra_normalout);
	}
	if(lp->graph->branchout==g){
	  if(first) {
	    memcpy(crange,lp->graph->ra_branchout,RANGESIZE);
	    first=0;
	  }else
	    combine_ranges(crange,lp->graph->ra_branchout);
	}
      }
      if(DEBUG&131072){
	printf("block %d, input:\n",g->index);
	print_ranges(stdout,crange);
      }
      for(p=g->start;p;p=p->next){
	do_ranges(crange,p);
	if(p==g->end||p->code==TEST||p->code==COMPARE) break;
      }
      if(p) c=p->code; else c=0;
      if(c==COMPARE||c==TEST){
	if((p->q1.flags&(VAR|DREFOBJ))==VAR&&(c==TEST||(p->q2.flags&(KONST|DREFOBJ))==KONST)){
	  IC *b=p->next;
	  range tmp;
	  while(b&&b->code<BEQ||b->code>BGT) b=b->next;
	  if(!b) ierror(0);
	  if(c==TEST){
	    vmax=Z0;
	    vumax=ZU0;
	  }else
	    eval_const(&p->q2.val,p->typf);
	  i=p->q1.v->index;
	  t=p->q1.v->vtyp->flags;
	  if(b->code==BEQ){
	    if(update_ranges(g->ra_normalout,crange)) done=0;
	    if(t&UNSIGNED)
	      crange[i].min.vumax=crange[i].max.vumax=vumax;
	    else
	      crange[i].min.vmax=crange[i].max.vmax=vmax;
	    if(update_ranges(g->ra_branchout,crange)) done=0;
	  }else if(b->code==BNE){
	    if(update_ranges(g->ra_branchout,crange)) done=0;
	    if(t&UNSIGNED)
	      crange[i].min.vumax=crange[i].min.vumax=vumax;
	    else
	      crange[i].max.vumax=crange[i].max.vumax=vumax;
	    if(update_ranges(g->ra_normalout,crange)) done=0;
	  }else if(b->code==BLT||b->code==BLE){
	    tmp=crange[i];
	    if(b->code==BLT) dec_val(t);
	    insert_max(&crange[i],t);
	    if(update_ranges(g->ra_branchout,crange)) done=0;
	    crange[i]=tmp;
	    inc_val(t);
	    insert_min(&crange[i],t);
	    if(update_ranges(g->ra_normalout,crange)) done=0;
	  }else if(b->code==BGE||b->code==BGT){
	    tmp=crange[i];
	    if(b->code==BGT) inc_val(t);
	    insert_min(&crange[i],t);
	    if(update_ranges(g->ra_branchout,crange)) done=0;
	    crange[i]=tmp;
	    dec_val(t);
	    insert_max(&crange[i],t);
	    if(update_ranges(g->ra_normalout,crange)) done=0;
	  }else
	    ierror(0);
	}else{
	  if(update_ranges(g->ra_branchout,crange)) done=0;
	  if(update_ranges(g->ra_normalout,crange)) done=0;
	}
      }else{
	if(g->branchout){
	  /* must be BRA as we checked for COMPARE/TEST above */
	  if(update_ranges(g->ra_branchout,crange))
	    done=0;
	}else{
	  if(update_ranges(g->ra_normalout,crange))
	    done=0;
	}
      }
      if(DEBUG&131072){
	printf("ra_branchout:\n");
	print_ranges(stdout,g->ra_branchout);
	printf("ra_normalout:\n");
	print_ranges(stdout,g->ra_normalout);
      }
    }
    pass++;
  }while(!done);
  
  
}