wkt@ccadfa.adfa.oz.au (Warren Toomey) (10/15/90)
echo x - Readme
sed '/^X/s///' > Readme << '/'
XHere is the beginnings of an optimiser for Bruce Evans' '386 compiler. It
Xruns on .s files and does a few simplistic things.
X
XNote that this is an _Alphatest_ version. I know little about '386 code,
Xso I'm posting this for suggestions, other optimisations, bug fixes etc.
X
XAt the moment, opt is called by
X
X % opt [-o outfile] [-O2] infile
X
Xwhere infile and outfile are .s files produced by % bcc -3 -S ....
XIf the -o option is not used, output goes to stdout.
X
X-O2 invokes a 2nd pass, attempting to do some register optimisation.
XCurrently this doesn't work. I realised this morning that I have to
Xpush/pop some extra registers on the stack.
X
XThe included Makefile compiles opt.c, runs opt on its own .s,
Xcompiles the optimised code, and runs _that_ on opt.s, just to make
Xsure the optimised code works correctly.
X
XUse cdiff to compare the differences between the old and new .s files,
Xto see where optimisations have been done. Note that jumps, branches,
Xand returns, although not optimised, have different inter-word spacing.
X
XCould as many people try it on different input files, to find wrong
Xoptimisations! Also, modifying bcc.c to call opt would be nice.
X
X**** Note _alphatest_! This code is in no way guaranteed to work.
X
X Warren Toomey wkt@csadfa.cs.adfa.oz.au
/
echo x - opt.c
sed '/^X/s///' > opt.c << '/'
X#include <sys/types.h>
X#include <fcntl.h>
X#include <string.h>
X#include <stdio.h>
X
X/* Opt.c. An optimising pass for Bruce Evans' 32-bit Minix C compiler.
X * This is a very simplistic pass, and only easily made optimisations
X * are done.
X *
X * Written 1990 by Warren Toomey.
X */
X
X /* Each line is stored in a line structure given below.
X * Note dst, src or both may be NULL.
X */
Xstruct line { struct line *next;
X struct line *prev;
X char op;
X char *dst;
X char *src;
X };
X#define NULLINE (struct line *)0
X
X#define DST 0
X#define SRC 1
X#define NUMVAR 10
X
X /* Candidates for possible register replacement are
X * stored in the following structure. Name points to
X * the address on the stack. Stat holds # times used
X * as destination or source.
X */
Xstruct var { char *name;
X int stat[2];
X char used;
X } Var[NUMVAR];
X
X /* Global variables */
Xstruct line *Program; /* Beginning of line list */
Xstruct line *Tline; /* Temps used everywhere */
Xstruct line *Told;
Xstruct line *Label;
Xchar *Lastchar=NULL; /* Last char read in from input */
Xchar *Lastrtn=NULL; /* Last \n read in from input */
Xint Numopts=0; /* # pass1 optimisations */
Xint Regopts=0; /* # pass2 optimisations */
X
X#define BUFSIZE 16384
Xchar Buf[BUFSIZE]; /* Input buffer */
X
X#define endchar(x) x[strlen(x)-1]
X
X /* The op field in the line holds the operation name.
X * This saves time against strcmp'ing.
X */
X#define DATA 127
X#define NUMOPS 40
X
X#define MOV 0
X#define ADD 1
X#define CALL 2
X#define PUSH 3
X#define POP 4
X#define TEST 5
X#define CMP 6
X#define RET 7
X#define XOR 8
X#define BR 9
X#define BLO 10
X#define INC 11
X#define DEC 12
X#define J 13
X#define JAE 14
X#define JE 15
X#define JL 16
X#define JNE 17
X#define SHL 18
X#define SUB 19
X#define EXPORT 20
X#define DD 21
X#define BEQ 22
X#define BNE 23
X#define LEA 24
X#define JB 25
X#define MOVZX 26
X#define JGE 27
X#define BGE 28
X#define AND 29
X#define JLE 30
X#define BLT 31
X#define JA 32
X#define JG 33
X#define SEG 34
X#define RCL 35
X#define BLE 36
X#define OR 37
X#define JBE 38
X#define BGT 39
X
X /* These are used when printing lines out again */
Xchar *operation[NUMOPS] = {
X "mov",
X "add",
X "call",
X "push",
X "pop",
X "test",
X "cmp",
X "ret",
X "xor",
X "br",
X "blo",
X "inc",
X "dec",
X "j",
X "jae",
X "je",
X "jl",
X "jne",
X "shl",
X "sub",
X "export",
X "dd",
X "beq",
X "bne",
X "lea",
X "jb",
X "movzx",
X "jge",
X "bge",
X "and",
X "jle",
X "blt",
X "ja",
X "jg",
X "seg",
X "rcl",
X "ble",
X "or",
X "jbe",
X "bgt"
X };
X
X
X/* Unlink: unlink a line from the DLL, freeing it.
X */
Xstruct line *Unlink(l)
X struct line *l;
X {
X struct line *l2= l->next;
X if (l2) l2->prev= l->prev;
X if (l->prev) l->prev->next= l2;
X free(l); return(l2);
X }
X
X/* Insert: insert a new line after the given line.
X Return ptr to the new line.
X */
X
Xstruct line *Insert(l)
X struct line *l;
X {
X struct line *l2;
X
X l2= (struct line *)malloc(sizeof(struct line));
X if (l2==NULLINE) { perror("opt3"); exit(1); }
X l->next->prev= l2;
X l2->next= l->next;
X l2->prev= l;
X l->next= l2;
X return(l2);
X }
X
X
X/* Loadbuf loads some of the input file into a character buffer, and
X * builds a DLL of line structures which point into the buffer. It
X * returns 1 normally, 0 on end of file.
X */
Xint loadbuf(file)
X int file;
X {
X int j,amount,size;
X int left;
X char *b2, *t1, *t2;
X
X /* Initialise pointers */
X Told=Tline=Label=Program;
X
X /* Copy leftover stuff to top of buffer */
X if (Lastrtn!=NULL)
X {
X Lastrtn++;
X left= (int)(Lastchar - Lastrtn);
X memcpy(Buf,Lastrtn,left);
X }
X else left=0;
X
X /* Read a chunk into the buffer */
X size=BUFSIZE-left; b2= Buf + left;
X if ((j=read(file,b2,size))==-1) { perror("opt2"); exit(1); }
X amount= (j==size);
X
X /* Find the last carriage return */
X Lastchar= (char *)((int) b2 + j);
X for (Lastrtn=Lastchar;Lastrtn>Buf && *Lastrtn!='\n';Lastrtn--);
X
X /* Scan along, building the DLL */
X for (t1=Buf;t1<Lastrtn;)
X {
X#ifdef DEBUG
X printf("| Loop, input -->");
X for (t2=t1;*t2!='\n';t2++) putchar(*t2);
X putchar('\n');
X#endif
X if (Tline==NULLINE)
X { /* Malloc space for the line struct */
X Tline= (struct line *)malloc(sizeof(struct line));
X if (Tline==NULLINE) { perror("opt3"); exit(1); }
X Told->next=Tline; Tline->prev=Told; Tline->next=NULLINE;
X }
X Tline->dst= NULL; Tline->src=NULL;
X
X /* If not an operation, record as data */
X if (*t1=='.' || *t1=='|' || *t1=='_' || *t1=='\n')
X { Tline->op= DATA; Tline->src= t1;
X for (;*t1!='\n';t1++); *t1=0; t1++;
X }
X else
X { /* Find the operation */
X for (t2=t1;*t2!=' ' && *t2!='\t' && *t2!='\n';t2++);
X *t2=0;
X for (j=0;j<NUMOPS;j++)
X if (!strcmp(operation[j],t1)) { Tline->op=j; break; }
X if (j>=NUMOPS)
X { printf("| Unknown opcode %s\n",t1); Tline->op= DATA; }
X
X /* Now find the first operand */
X for (t2++;*t2==' ' || *t2=='\t';t2++);
X t1=t2;
X#ifdef DEBUG
X printf("| Operands are -->",t1);
X for (t2=t1;*t2!='\n';t2++) putchar(*t2);
X putchar('\n');
X#endif
X if (j!=RET)
X {
Xagain:
X for (t2=t1;*t2!='\n' && *t2!=',';t2++);
X switch(*t2)
X {
X case ',': Tline->dst=t1;
X *t2=0;
X t1=t2+1;
X goto again;
X case '\n': Tline->src=t1;
X *t2=0;
X t1=t2+1;
X }
X }
X }
X /* And finally move Tline and Told up */
X Told=Tline;
X Tline=Tline->next;
X }
X /* Free up lines from previous passes */
X Told->next=NULLINE;
X#ifdef NOTYET
X /* These lines cause assert errs in free() */
X for (; Tline!=NULLINE; Tline=Tline->next)
X { Told=Tline; free(Told); }
X#endif
X
X return(amount);
X }
X
X
X/* Printbuf prints out each line structure in the buffer to
X * the output file, as closely as it can to the original lines.
X */
Xprintbuf()
X {
X#ifdef DEBUG
X int i=0;
X#endif
X struct line *t1;
X
X for (t1=Program;t1!=NULLINE;t1=t1->next)
X {
X#ifdef DEBUG
X printf("| Iteration %d\n",i++);
X#endif
X if (t1->op==DATA)
X printf("%s\n",t1->src);
X else
X {
X printf("%s\t",operation[t1->op]);
X if (t1->dst!=NULL) printf("%s,",t1->dst);
X if (t1->src!=NULL) printf("%s",t1->src);
X printf("\n");
X }
X }
X }
X
X
X/* Pass1 does an extremely simplistic pass though the buffer, fixing up
X * simple things like inc, dec etc.
X */
Xpass1()
X {
X char op, *cptr;
X struct line *tnext;
X
X for (Tline=Program->next,Told=Program;Tline->next!=NULLINE;
X Told=Tline,Tline=Tline->next)
X switch(Tline->op)
X {
X /* Replace mov eax,addr with inc addr
X * inc eax
X * mov addr,eax
X * (same for dec)
X */
X case INC: op= INC;
X goto incdec;
X case DEC: op= DEC;
Xincdec:
X tnext=Tline->next;
X if (tnext->next==NULLINE || Told->op!=MOV
X || strcmp(tnext->dst,Told->src)) break;
X Told->op= op;
X Told->dst=NULL;
X Tline= Unlink(Tline);
X Unlink(Tline);
X Tline=Told;
X Numopts++;
X break;
X
X /* Replace xor eax,eax with mov addr,*0
X * mov addr,eax
X * or
X * xor al,al with mov byte addr,*0
X * mov addr,al
X */
X case XOR: Told=Tline->next;
X if (Told->op!=MOV) break;
X if (!strcmp(Tline->next->src,"al"))
X {
X cptr= Tline->dst;
X strcpy(cptr,"byte ");
X strcat(cptr,Told->dst);
X Told->dst= cptr;
X }
X Told->src= "*0";
X Tline= Unlink(Tline);
X Numopts++;
X break;
X
X /* Replace mov eax,addr with cmp addr,*val
X * cmp eax,*val
X */
X case CMP: if (Told->op!=MOV || strcmp(Tline->dst,Told->dst)
X || *(Tline->src)!='*')
X break;
X if (!strcmp(Tline->dst,"al"))
X {
X cptr= Told->dst - 4;
X strcpy(cptr,"byte ");
X strcat(cptr,Told->src);
X Tline->dst= cptr;
X }
X else Tline->dst= Told->src;
X Unlink(Told);
X Numopts++;
X break;
X
X /* Replace mov ebx,#label with push dword #label
X * push ebx
X */
X case PUSH: if (Told->op!=MOV || strcmp(Tline->src,Told->dst)
X || *(Told->src)!='#')
X break;
X Told->op= PUSH;
X cptr= Told->dst - 4;
X strcpy(cptr,"dword ");
X strcat(cptr,Told->src);
X Told->src= cptr;
X Told->dst=NULL;
X Tline=Unlink(Tline);
X Numopts++;
X break;
X
X /* Lots of mov mov optimisations */
X case MOV: if (Tline->next->op==MOV) movpass1();
X break;
X }
X }
X
X
X/* movpass1 handles cases when there are two movs in a row in pass1
X */
Xmovpass1()
X {
X Told=Tline->next;
X if (!strcmp(Tline->dst,Told->src))
X {
X /* Replace mov addr,eax with mov addr,eax
X * mov eax,addr
X */
X if (!strcmp(Tline->src,Told->dst))
X { Unlink(Told); Numopts++; return; }
X
X /* Replace mov eax,*val with mov addr,*val
X * mov addr,eax
X */
X if (*(Tline->src)=='*')
X { Told->src= Tline->src; Tline= Unlink(Tline); Numopts++; return; }
X }
X }
X
X/* Pass2 attempts to find unused function return values, and place
X * most commonly used local variables into registers
X */
Xpass2()
X {
X int i;
X
X for (Tline=Program;Tline!=NULLINE;Tline=Tline->next)
X {
X if ( (Tline->op==DATA) &&
X (*(Tline->src)=='|' ||
X (*(Tline->src)=='_' && endchar(Tline->src)==':')) )
X {
X /* If a label, optimise from last label to here */
X optvar(Tline);
X printf("| Starting opt on %s\n",Tline->src);
X /* Save label ptr and flush candidiates list */
X Label= Tline;
X for (i=0;i<NUMVAR;i++) Var[i].used=0;
X }
X else
X {
X#ifdef DEBUG
X printf("| Try with %s %s\n",Tline->dst,Tline->src);
X#endif
X /* else increase candidate stat if possible */
X if (Tline->src && *(Tline->src)=='-') incvar(Tline->src,SRC);
X if (Tline->dst && *(Tline->dst)=='-') incvar(Tline->dst,DST);
X }
X }
X }
X
X
X/* optvar: Optimise the local variables used in the last routine.
X * Takes a pointer to the last line, and uses Label which points
X * to the first line.
X */
Xoptvar(endline)
X struct line *endline;
X {
X int i,first=0,second=0,temp;
X char *c1="", *c2="";
X char *c;
X struct line *yatline;
X
X for (i=0;i<NUMVAR;i++)
X if (Var[i].used)
X {
X printf("| Var %s dst:%d src:%d\n",
X Var[i].name,Var[i].stat[DST],Var[i].stat[SRC]);
X /* Find the 2 highest candidates in order */
X temp= Var[i].stat[DST] + Var[i].stat[SRC];
X if (temp>=first)
X { second=first; c2=c1; first= temp; c1=Var[i].name; continue;}
X if (temp>=second)
X { second= temp; c2=Var[i].name; continue;}
X }
X if (first) printf("| 1st is %s\n",c1);
X if (second) printf("| 2nd is %s\n",c2);
X /* If no candidiates, return */
X if (!first) return;
X Regopts++;
X if (second) Regopts++;
X /* Else replace candidates on the lines */
X for (yatline=Label; yatline!=endline; yatline=yatline->next)
X {
X#ifdef DEBUG
X printf("| Yatline is %s ",operation[yatline->op]);
X if (yatline->dst) printf("%s,",yatline->dst);
X if (yatline->src) printf("%s",yatline->src);
X putchar('\n');
X#endif
X if (yatline->op==DATA) continue;
X /* We must add mov ecx,addr in process startup */
X if (yatline->op==PUSH)
X {
X#ifdef DEBUG
X printf("| Found push %s\n",yatline->src);
X#endif
X if (!strcmp(yatline->src,"esi"))
X {
X if (first) { yatline=Insert(yatline);
X yatline->op= MOV;
X yatline->src= c1;
X yatline->dst= "ecx";
X }
X if (second) { yatline=Insert(yatline);
X yatline->op= MOV;
X yatline->src= c2;
X yatline->dst= "edx";
X }
X continue;
X }
X /* Fix push dword addr with push reg */
X if ((c=strchr(yatline->src,'-'))!=NULL && !strcmp(c,c1))
X { yatline->src= "ecx"; continue; }
X if ((c=strchr(yatline->src,'-'))!=NULL && !strcmp(c,c2))
X { yatline->src= "edx"; continue; }
X }
X /* Now replace address with register */
X if (yatline->dst)
X {
X if (first && !strcmp(yatline->dst,c1)) yatline->dst="ecx";
X if (second && !strcmp(yatline->dst,c2)) yatline->dst="edx";
X }
X if (yatline->src)
X {
X if (first && !strcmp(yatline->src,c1)) yatline->src="ecx";
X if (second && !strcmp(yatline->src,c2)) yatline->src="edx";
X }
X }
X }
X
X
X/* incvar either increments the usage stats for the given variable,
X * or adds it to the list of variables.
X */
Xincvar(var,type)
X char *var;
X int type;
X {
X int i;
X
X#ifdef DEBUG
X printf("| In incvar\n");
X#endif
X for (i=0;i<NUMVAR;i++)
X { if (!Var[i].used) break;
X if (!strcmp(Var[i].name,var)) {
X#ifdef DEBUG
X printf("| Incrementing %s %d\n",var,type);
X#endif
X Var[i].stat[type]++; return; }
X }
X
X if (i<NUMVAR)
X {
X#ifdef DEBUG
X printf("| Adding %s %d\n",var,type);
X#endif
X Var[i].name=var; Var[i].used=1; Var[i].stat[type]=1; }
X }
X
X
Xusage()
X { fprintf(stderr,"Usage: opt [-o file] [-O2] infile\n"); exit(1); }
X
X
X/* The main program. See the usage() routine for more information
X * about how the call the program.
X */
Xmain(argc,argv)
X int argc;
X char *argv[];
X {
X FILE *zout;
X int i,dopass2=0,notdone;
X
X if (argc==1) usage();
X /* Get -o and -O2 flags */
X for (i=1;i<argc-1;i++)
X {
X if (!strcmp(argv[i],"-o"))
X {
X /* Open the output file */
X fclose(stdout);
X if ((zout=fopen(argv[i+1],"w"))==NULL)
X { perror("opt8"); exit(1); }
X }
X if (!strcmp(argv[i],"-O2")) dopass2=1;
X }
X
X /* Initialise one `line' for loadbuf to work */
X Program= (struct line *)malloc(sizeof(struct line));
X if (Program==NULLINE) { perror("opt9"); exit(1); }
X Program->next= NULLINE; Program->prev= NULLINE;
X Program->dst= NULL; Program->src=NULL;
X
X /* Initialiase var list for pass2 */
X for (i=0;i<NUMVAR;i++) Var[i].used=0;
X
X /* Open the input file */
X if ((i=open(argv[argc-1],O_RDONLY))==-1) { perror("opt1"); exit(1); }
X
X /* Loop, reading, optimising & writing */
X for (notdone=1;notdone;)
X {
X notdone= loadbuf(i);
X if (dopass2) pass2();
X pass1();
X printbuf();
X }
X /* Finally print out info on optimisations */
X printf("| %d optimisations done\n",Numopts);
X if (dopass2) printf("| %d register optimisations done\n",Regopts);
X }
/
echo x - Makefile
sed '/^X/s///' > Makefile << '/'
Xb.s: a opt.s
X ./a -o b.s opt.s
X
Xa: a.s
X bcc -o a a.s
X
Xa.s: opt opt.s
X ./opt -o a.s opt.s
X
Xopt.s: opt.c
X bcc -S opt.c
X
Xopt: opt.c
X bcc -o opt opt.c
/
--
Warren Toomey VK2XWT, recovered.
Deep in the bowels of ADFA Comp Science.
`It wasn't until Yr10 that I learnt how to use a colon'