src/luac/opt.c

   1 /*
   2 ** $Id: opt.c,v 1.12 1999/07/02 19:34:26 lhf Exp $
   3 ** optimize bytecodes
   4 ** See Copyright Notice in lua.h
   5 */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include "luac.h"
  11
  12 static void FixArg(Byte* p, int i, int j, int isconst)
  13 {
  14  if (j==i)
  15   ;
  16  else if (i<=MAX_BYTE)          /* j<i, so j fits where i did */
  17   p[1]=j;
  18  else if (i<=MAX_WORD)
  19  {
  20   if (isconst && j<=MAX_BYTE)   /* may use byte variant instead */
  21   {
  22    p[0]++;                      /* byte variant follows word variant */
  23    p[1]=j;
  24    p[2]=NOP;
  25   }
  26   else                          /* stuck with word variant */
  27   {
  28    p[1]=j>>8;
  29    p[2]=j;
  30   }
  31  }
  32  else                           /* previous instruction must've been LONGARG */
  33  {
  34   if (isconst && j<=MAX_WORD) p[-2]=p[-1]=NOP; else p[-1]=j>>16;
  35   p[1]=j>>8;
  36   p[2]=j;
  37  }
  38 }
  39
  40 static void FixConstants(TProtoFunc* tf, int* C)
  41 {
  42  Byte* code=tf->code;
  43  Byte* p=code;
  44  int longarg=0;
  45  for (;;)
  46  {
  47   Opcode OP;
  48   int n=INFO(tf,p,&OP);
  49   int op=OP.class;
  50   int i=OP.arg+longarg;
  51   longarg=0;
  52   if (op==PUSHCONSTANT || op==GETGLOBAL || op==GETDOTTED ||
  53       op==PUSHSELF     || op==SETGLOBAL || op==CLOSURE)
  54    FixArg(p,i,C[i],1);
  55   else if (op==LONGARG) longarg=i<<16;
  56   else if (op==ENDCODE) break;
  57   p+=n;
  58  }
  59 }
  60
  61 #define UNREF   1                       /* "type" of unused constants */
  62 #define BIAS    128                     /* mark for used constants */
  63
  64 static void NoUnrefs(TProtoFunc* tf)
  65 {
  66  int i,n=tf->nconsts;
  67  Byte* code=tf->code;
  68  Byte* p=code;
  69  int longarg=0;
  70  for (;;)                               /* mark all used constants */
  71  {
  72   Opcode OP;
  73   int n=INFO(tf,p,&OP);
  74   int op=OP.class;
  75   int i=OP.arg+longarg;
  76   longarg=0;
  77   if (op==PUSHCONSTANT || op==GETGLOBAL || op==GETDOTTED ||
  78       op==PUSHSELF     || op==SETGLOBAL || op==CLOSURE)
  79   {
  80    TObject* o=tf->consts+i;
  81    if (ttype(o)<=0) ttype(o)+=BIAS;     /* mark as used */
  82   }
  83   else if (op==LONGARG) longarg=i<<16;
  84   else if (op==ENDCODE) break;
  85   p+=n;
  86  }
  87  for (i=0; i<n; i++)                    /* mark all unused constants */
  88  {
  89   TObject* o=tf->consts+i;
  90   if (ttype(o)<=0)
  91    ttype(o)=UNREF;                      /* mark as unused */
  92   else
  93    ttype(o)-=BIAS;                      /* unmark used constant */
  94  }
  95 }
  96
  97 #define CMP(oa,ob,f)    memcmp(&f(oa),&f(ob),sizeof(f(oa)))
  98
  99 static int compare(TProtoFunc* tf, int ia, int ib)
 100 {
 101  TObject* oa=tf->consts+ia;
 102  TObject* ob=tf->consts+ib;
 103  int t=ttype(oa)-ttype(ob);
 104  if (t) return t;
 105  switch (ttype(oa))
 106  {
 107   case LUA_T_NUMBER:    return CMP(oa,ob,nvalue);
 108   case LUA_T_STRING:    return CMP(oa,ob,tsvalue);
 109   case LUA_T_PROTO:     return CMP(oa,ob,tfvalue);
 110   case LUA_T_NIL:       return 0;
 111   case UNREF:           return 0;
 112   default:              return ia-ib;   /* cannot happen */
 113  }
 114 }
 115
 116 static TProtoFunc* TF;                  /* for sort */
 117
 118 static int compare1(const void* a, const void* b)
 119 {
 120  int ia=*(int*)a;
 121  int ib=*(int*)b;
 122  int t=compare(TF,ia,ib);
 123  return (t) ? t : ia-ib;
 124 }
 125
 126 static void OptConstants(TProtoFunc* tf)
 127 {
 128  static int* C=NULL;
 129  static int* D=NULL;
 130  int i,k;
 131  int n=tf->nconsts;
 132  if (n==0) return;
 133  luaM_reallocvector(C,n,int);
 134  luaM_reallocvector(D,n,int);
 135  NoUnrefs(tf);
 136  for (i=0; i<n; i++) C[i]=D[i]=i;       /* group duplicates */
 137  TF=tf; qsort(C,n,sizeof(C[0]),compare1);
 138  k=C[0];                                /* build duplicate table */
 139  for (i=1; i<n; i++)
 140  {
 141   int j=C[i];
 142   if (compare(tf,k,j)==0) D[j]=k; else k=j;
 143  }
 144  k=0;                                   /* build rename map & pack constants */
 145  for (i=0; i<n; i++)
 146  {
 147   if (D[i]==i)                          /* new value */
 148   {
 149    TObject* o=tf->consts+i;
 150    if (ttype(o)!=UNREF)
 151    {
 152     tf->consts[k]=tf->consts[i];
 153     C[i]=k++;
 154    }
 155   }
 156   else C[i]=C[D[i]];
 157  }
 158  if (k<n)
 159  {
 160 printf("\t" SOURCE " reduced constants from %d to %d\n",
 161          tf->source->str,tf->lineDefined,n,k);
 162   FixConstants(tf,C);
 163   tf->nconsts=k;
 164  }
 165 }
 166
 167 static int NoDebug(TProtoFunc* tf)
 168 {
 169  Byte* code=tf->code;
 170  Byte* p=code;
 171  int lop=NOP;                           /* last opcode */
 172  int nop=0;
 173  for (;;)                               /* change SETLINE to NOP */
 174  {
 175   Opcode OP;
 176   int n=INFO(tf,p,&OP);
 177   int op=OP.class;
 178   if (op==NOP) ++nop;
 179   else if (op==SETLINE)
 180   {
 181    int m;
 182    if (lop==LONGARG) m=2; else if (lop==LONGARGW) m=3; else m=0;
 183    nop+=n+m; memset(p-m,NOP,n+m);
 184   }
 185   else if (op==ENDCODE) break;
 186   lop=OP.op;
 187   p+=n;
 188  }
 189  return nop;
 190 }
 191
 192 static int FixJump(TProtoFunc* tf, Byte* a, Byte* b)
 193 {
 194  Byte* p;
 195  int nop=0;
 196  for (p=a; p<b; )
 197  {
 198   Opcode OP;
 199   int n=INFO(tf,p,&OP);
 200   int op=OP.class;
 201   if (op==NOP) ++nop;
 202   else if (op==ENDCODE) break;
 203   p+=n;
 204  }
 205  return nop;
 206 }
 207
 208 static void FixJumps(TProtoFunc* tf)
 209 {
 210  Byte* code=tf->code;
 211  Byte* p=code;
 212  int longarg=0;
 213  for (;;)
 214  {
 215   Opcode OP;
 216   int n=INFO(tf,p,&OP);
 217   int op=OP.class;
 218   int i=OP.arg+longarg;
 219   int nop=0;
 220   longarg=0;
 221   if (op==ENDCODE) break;
 222   else if (op==IFTUPJMP || op==IFFUPJMP)
 223    nop=FixJump(tf,p-i+n,p);
 224   else if (op==ONTJMP || op==ONFJMP || op==JMP || op==IFFJMP)
 225    nop=FixJump(tf,p,p+i+n);
 226   else if (op==LONGARG) longarg=i<<16;
 227   if (nop>0) FixArg(p,i,i-nop,0);
 228   p+=n;
 229  }
 230 }
 231
 232 static void PackCode(TProtoFunc* tf)
 233 {
 234  Byte* code=tf->code;
 235  Byte* p=code;
 236  Byte* q=code;
 237  for (;;)
 238  {
 239   Opcode OP;
 240   int n=INFO(tf,p,&OP);
 241   int op=OP.class;
 242   if (op!=NOP) { memcpy(q,p,n); q+=n; }
 243   p+=n;
 244   if (op==ENDCODE) break;
 245  }
 246 printf("\t" SOURCE " reduced code from %d to %d\n",
 247         tf->source->str,tf->lineDefined,(int)(p-code),(int)(q-code));
 248 }
 249
 250 static void OptCode(TProtoFunc* tf)
 251 {
 252  if (NoDebug(tf)==0) return;            /* cannot improve code */
 253  FixJumps(tf);
 254  PackCode(tf);
 255 }
 256
 257 static void OptFunction(TProtoFunc* tf);
 258
 259 static void OptFunctions(TProtoFunc* tf)
 260 {
 261  int i,n=tf->nconsts;
 262  for (i=0; i<n; i++)
 263  {
 264   TObject* o=tf->consts+i;
 265   if (ttype(o)==LUA_T_PROTO) OptFunction(tfvalue(o));
 266  }
 267 }
 268
 269 static void OptFunction(TProtoFunc* tf)
 270 {
 271  OptConstants(tf);
 272  OptCode(tf);
 273  OptFunctions(tf);
 274  tf->source=luaS_new("");
 275  tf->locvars=NULL;
 276 }
 277
 278 void luaU_optchunk(TProtoFunc* Main)
 279 {
 280  OptFunction(Main);
 281 }