src/luac/opt.c

   1 /*
   2 ** $Id: opt.c,v 1.4 1998/04/02 20:44:08 lhf Exp $
   3 ** optimize bytecodes
   4 ** See Copyright Notice in lua.h
   5 */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include "luac.h"
  10 #include "lmem.h"
  11
  12 static void FixConstants(TProtoFunc* tf, int* C)
  13 {
  14  Byte* code=tf->code;
  15  Byte* p=code;
  16  while (1)
  17  {
  18   Opcode OP;
  19   int n=INFO(tf,p,&OP);
  20   int op=OP.class;
  21   int i=OP.arg;
  22   if (op==ENDCODE) break;
  23   if (  op==PUSHCONSTANT || op==GETDOTTED || op==PUSHSELF ||
  24         op==GETGLOBAL    || op==SETGLOBAL)
  25   {
  26    int j=C[i];
  27    if (j==i)
  28     ;
  29    else if (n==1)
  30    {
  31     p[0]=op+j+1;
  32    }
  33    else if (n==2)
  34    {
  35     if (j<8) { p[0]=op+j+1; p[1]=NOP; } else p[1]=j;
  36    }
  37    else
  38    {
  39     if (j<=255)
  40     {
  41      p[0]=op;
  42      p[1]=j;
  43      p[2]=NOP;
  44     }
  45     else
  46     {
  47      p[1]= 0x0000FF & (j>>8);
  48      p[2]= 0x0000FF &  j;
  49     }
  50    }
  51   }
  52   p+=n;
  53  }
  54 }
  55
  56 static TProtoFunc* TF;
  57
  58 static int compare(const void* a, const void *b)
  59 {
  60  int ia=*(int*)a;
  61  int ib=*(int*)b;
  62  int t;
  63  TObject* oa=TF->consts+ia;
  64  TObject* ob=TF->consts+ib;
  65  t=ttype(oa)-ttype(ob);         if (t) return t;
  66  t=oa->value.i-ob->value.i;     if (t) return t;
  67  return ia-ib;
  68 }
  69
  70 static void OptConstants(TProtoFunc* tf)
  71 {
  72  static int* C=NULL;
  73  static int* D=NULL;
  74  int i,k;
  75  int n=tf->nconsts;
  76  if (n==0) return;
  77  C=luaM_reallocvector(C,n,int);
  78  D=luaM_reallocvector(D,n,int);
  79  for (i=0; i<n; i++) C[i]=D[i]=i;       /* group duplicates */
  80  TF=tf; qsort(C,n,sizeof(C[0]),compare);
  81  k=C[0];                                /* build duplicate table */
  82  for (i=1; i<n; i++)
  83  {
  84   int j=C[i];
  85   TObject* oa=tf->consts+k;
  86   TObject* ob=tf->consts+j;
  87   if (ttype(oa)==ttype(ob) && oa->value.i==ob->value.i) D[j]=k; else k=j;
  88  }
  89  k=0;                                   /* build rename map & pack constants */
  90  for (i=0; i<n; i++)
  91  {
  92   if (D[i]==i) { tf->consts[k]=tf->consts[i]; C[i]=k++; } else C[i]=C[D[i]];
  93  }
  94  if (k>=n) return;
  95 printf("\t\"%s\":%d reduced constants from %d to %d\n",
  96         tf->fileName->str,tf->lineDefined,n,k);
  97  tf->nconsts=k;
  98  FixConstants(tf,C);
  99 }
 100
 101 static int NoDebug(TProtoFunc* tf)
 102 {
 103  Byte* code=tf->code;
 104  Byte* p=code;
 105  int nop=0;
 106  while (1)                              /* change SETLINE to NOP */
 107  {
 108   Opcode OP;
 109   int n=INFO(tf,p,&OP);
 110   int op=OP.class;
 111   if (op==ENDCODE) break;
 112   if (op==NOP) ++nop;
 113   if (op==SETLINE) { nop+=n; memset(p,NOP,n); }
 114   p+=n;
 115  }
 116  return nop;
 117 }
 118
 119 static int FixJump(TProtoFunc* tf, Byte* a, Byte* b)
 120 {
 121  Byte* p;
 122  int nop=0;
 123  for (p=a; p<b; )
 124  {
 125   Opcode OP;
 126   int n=INFO(tf,p,&OP);
 127   int op=OP.class;
 128   if (op==ENDCODE) break;
 129   if (op==NOP) ++nop;
 130   p+=n;
 131  }
 132  return nop;
 133 }
 134
 135 static void FixJumps(TProtoFunc* tf)
 136 {
 137  Byte* code=tf->code;
 138  Byte* p=code;
 139  while (1)
 140  {
 141   Opcode OP;
 142   int n=INFO(tf,p,&OP);
 143   int op=OP.class;
 144   int i=OP.arg;
 145   int nop;
 146   if (op==ENDCODE) break;
 147   nop=0;
 148   if (op==IFTUPJMP || op==IFFUPJMP) nop=FixJump(tf,p-i+n,p); else
 149   if (op==ONTJMP || op==ONFJMP || op==JMP || op==IFFJMP) nop=FixJump(tf,p,p+i+n);
 150   if (nop>0)
 151   {
 152    int j=i-nop;
 153    if (n==2)
 154     p[1]=j;
 155    else
 156 #if 0
 157    {
 158     if (j<=255)                         /* does NOT work for nested loops */
 159     {
 160      if (op==IFTUPJMP || op==IFFUPJMP) --j;
 161      p[0]=OP.op-1;                      /* *JMP and *JMPW are consecutive */
 162      p[1]=j;
 163      p[2]=NOP;
 164     }
 165     else
 166 #endif
 167     {
 168      p[1]= 0x0000FF & (j>>8);
 169      p[2]= 0x0000FF &  j;
 170     }
 171 #if 0
 172    }
 173 #endif
 174   }
 175   p+=n;
 176  }
 177 }
 178
 179 static void PackCode(TProtoFunc* tf)
 180 {
 181  Byte* code=tf->code;
 182  Byte* p=code;
 183  Byte* q=code;
 184  while (1)
 185  {
 186   Opcode OP;
 187   int n=INFO(tf,p,&OP);
 188   int op=OP.class;
 189   if (op!=NOP) { memcpy(q,p,n); q+=n; }
 190   p+=n;
 191   if (op==ENDCODE) break;
 192  }
 193 printf("\t\"%s\":%d reduced code from %d to %d\n",
 194         tf->fileName->str,tf->lineDefined,(int)(p-code),(int)(q-code));
 195 }
 196
 197 static void OptCode(TProtoFunc* tf)
 198 {
 199  int nop=NoDebug(tf);
 200  if (nop==0) return;                    /* cannot improve code */
 201  FixJumps(tf);
 202  PackCode(tf);
 203 }
 204
 205 static void OptFunction(TProtoFunc* tf);
 206
 207 static void OptFunctions(TProtoFunc* tf)
 208 {
 209  int i,n=tf->nconsts;
 210  for (i=0; i<n; i++)
 211  {
 212   TObject* o=tf->consts+i;
 213   if (ttype(o)==LUA_T_PROTO) OptFunction(tfvalue(o));
 214  }
 215 }
 216
 217 static void OptFunction(TProtoFunc* tf)
 218 {
 219  tf->locvars=NULL;                      /* remove local variables table */
 220  OptConstants(tf);
 221  OptCode(tf);
 222  OptFunctions(tf);
 223 }
 224
 225 void OptChunk(TProtoFunc* Main)
 226 {
 227  OptFunction(Main);
 228 }