/*
	A peephole optimizer for lcc
	----------------------------

Section 1:
---------
Overall design.
The optimizer receives its input from the compiler as an ascii instruction
stream. When the function 'genasm' sees a label, it will send the contents of
the buffer to the optimizer with a call to the function 'SendToOptimizer'.
The entry point in this file is the function 'ChangeBlock', that performs the
following actions:
	1. Parses the instructions, setting flags for certain characteristics,
	   setting register numbers, etc.
	2. Calls the 'Optimize block' function the scan the block for instruction
	   to be changed/deleted.

The strategy of this peephole optimizer is to build a machine state, and
try to keep it coherent with the operations performed in a block. It will
try to eliminate redundant loads of registers, replace certains registers
with other free ones, replace certain sequences of instruction lcc generates
with other more efficient ones, etc. It is certainly limited to lcc, since
many of the (implicit) assumptions about the code would preclude its use
as a more general peephole optimizer.

*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ANALYZER
#ifdef STANDALONE
#define DEBUGOPTIM
#include <time.h>
int vmask[] = { 1, 0 };
#endif
extern int genlabel(int);
#include <assert.h>
#define MAXIDSIZE 50
/*
The 'Instruction' data structure. This is built now by the parser of
instructions, but it would naturally much more efficient to have the
characteristics of those instructions built in to the tables of the
compiler
*/
typedef struct tagInstruction {
	unsigned char Name[10]; /* opcode */
	unsigned char src[MAXIDSIZE];  /* source of the data */
	unsigned char dst[MAXIDSIZE];  /* destination of the data */
	unsigned char *Start;   /* Pointer to the beginning of the instruction */
				/* in the assembler buffer */
	unsigned char *End;	/* pointer to the end of the instruction */
	long Flags;
	unsigned short ChangedIdx; /* Index of the replace instruction in the */
				/* instruction table */
	unsigned short SrcReg;  /* Source register number */
	unsigned short DstReg;  /* destination reg number */
}Instruction;
/* instruction Flags field */
#define DELETED			0x1
#define CHANGED			0x2
#define ISCALL			0x4
#define CLOBBERS		0x8
#define ISLOCAL			0x10
#define ISARGUMENT		0x20
#define SRCDEREFERENCE	0x40
#define DSTDEREFERENCE	0x80
#define SRCOFFSET		0x100
#define DSTOFFSET		0x200
#define ISJUMP			0x400
#define ISFLOAT			0x800
#define TRUNCATED		0x1000
#define ISMOVL			0x2000
#define ISMOVSB			0x4000
#define	ISGENERICMOVE	0x8000
#define ISMOVSWL		0x10000
#define ISMOVSBL		0x20000
#define ISLEAL			0x40000
#define ISCOMPARE		0x80000
#define ISREGSRC		0x100000
#define ISREGDST		0x200000
#define ADDED			0x400000
#define STACKADJUST		0x800000

/*
The instruction table contains two parts:
1. The instructions that belong to the block being analyzed now.
2. The changed instructions.

Each changed instruction contains the index of the position of the changed
instruction contents in its ChangedIndex field, set by the function
'GetNextChangedInstruction'
*/
/* Number of instructions in the instruction table */
#define MAXINSTRUCTION 600
/* Register numbers */
#define EAX		1
#define EBX		2
#define ECX		3
#define	EDX		4
#define ESI		5
#define EDI		6
#define EBP		7
#define	ESP		8
#define	AX		9
#define	BX		10
#define CX		11
#define DX		12
#define SI		13
#define DI		14
#define BP		15
#define SP		16
static char *RegisterNames[] = {
	"NULL",
	"eax",
	"ebx",
	"ecx",
	"edx",
	"esi",
	"edi",
	"ebp",
	"esp"
};
int ediIsSaved=1,esiIsSaved=1;
static Instruction InstructionTable[MAXINSTRUCTION];
static int InstructionIndex = 0;
static int recursion = 0;

typedef struct tagbasicBlock {
	char Label[25];
	int calls;
	int NrOfInstructions;
	char Registers[SP+1];
	int Flags;
	unsigned short FirstCall; /* Index of the first 'call' instruction */
	unsigned short LastCall;  /* Index of the last 'call' instruction */
	unsigned short ChangedCounter;
	unsigned short deleted;
}BasicBlock;
extern int GetLastFunctionLabel(void);
static unsigned char *Nullst = "NULL";
/*
We keep the state of the machine in this character vector.
Each position points towards a character string that
indicates the contents of the register.
*/
static unsigned char *State[ESP+1];
static int deleted = 0,redundant = 0;
static int lastLabel = 0;
static int hasRegisterVariables;
/*
The peephole optimizer can be compiled as a standalone module. It
will emit very verbose output...
*/
#ifdef DEBUGOPTIM
static char *buffer;
#define Printf printf
#define Printf1(a) printf(a)
#define Printf2(a,b) printf(a,b)
#define Printf3(a,b,c) printf(a,b,c)
extern int hasAllocA;
#else
#define Printf1(a)
#define Printf2(a,b)
#define Printf3(a,b,c)
extern int hasAllocA;
#endif
extern char *FindStringConstant(char *name);

#ifdef STANDALONE
int hasAllocA = 0;
main(int argc,char *argv[])
{
	FILE *f;
	int l,nl;
	unsigned char *newb;

	f = fopen(argv[1],"r");
	if (f == NULL) {
		fprintf(stderr,"Impossible to open %s\n",argv[1]);
		return(1);
	}
	fseek(f,0,SEEK_END);
	l = ftell(f);
	fseek(f,0,SEEK_SET);
	buffer = malloc(l+10);
	memset(buffer,0,l+10);
	l = fread(buffer,1,l,f);
	fclose(f);
	Printf("Optimizing %s\n",argv[1]);
	nl = ScanAsm(buffer,l,&newb);
	Printf("%d instructions deleted,redundant %d\n",deleted,redundant);
	f = fopen("output.out","w");
	fwrite(newb,1,nl,f);
	fclose(f);
}
static int genlabel(int n)
{
	static int label = 99999;

	label += n;
	return label - n;
}

#endif

/*
This routine searches the InstructionTable for an index where
it will put the next changed instruction. Those instructions
start at the end of the basic block.
*/
static Instruction *GetNextChangedInstruction(Instruction *Ins,BasicBlock *bb)
{
	Instruction *insDst;

	if (bb->ChangedCounter  >= MAXINSTRUCTION) {
		fprintf(stderr,"overflow of changed index in basic block %s\n",bb->Label);
		exit(1);
	}
	Ins->Flags |= CHANGED;
	Ins->ChangedIdx = bb->ChangedCounter;
	insDst = &InstructionTable[bb->ChangedCounter];
	bb->ChangedCounter++;
	memset(insDst,0,sizeof(Instruction));
	return(insDst);
}
static Instruction *ChangeInstruction(Instruction *ins,BasicBlock *bb,char *name,char *src,char *dst)
{
	Instruction *result;

	result = GetNextChangedInstruction(ins,bb);
	strcpy(result->Name,name);
	strcpy(result->src,src);
	strcpy(result->dst,dst);
	return(result);
}

#ifdef STANDALONE
/*
This routine searches the start of the basic block. It looks
for a label, that should start with the '_$' prefix. Change
this if the prefix is different.
*/
static char *FindBeginBlock(char *bp,BasicBlock *bb)
{
	if (*bp == '_' && bp[1] == '$') {
		char *p;
		p = bp+2;
		while (*p && *p != '\n' && *p != ':') p++;
		if (*p == ':') goto retgood;
		if (*p == 0) return(NULL);
	}
	while (*bp) {
		if (bp[0] == '\n' && bp[1] == '_') {
			bp++;
			if (bp[1] == '$') {
				int i;
retgood:
				i = 0;
				while (*bp && *bp != '\n') bb->Label[i++] = *bp++;
				if (*bp == '\n') bp++;
				return(bp);
			}
			else {
				char *p = bp;

				while (*p && *p != '\n') {
					if (*p == ':') {
						goto retgood;
					}
					else if (*p == ',') {
						bp = p;
						break;
					}
					p++;
				}
			}
		}
		else if (*bp == '.' && bp[1] == 'd' && bp[2] == 'a' && bp[3] == 't') {
scanfortext:
			bp++;
			for (;;) {
				while (*bp && *bp != '.')
					bp++;
				if (*bp == '.' && !strncmp(bp,".text",5))
					break;
				else if (*bp == 0) break;
				else if (*bp == '.') bp++;
			}
			if (bp == NULL) return(NULL);
			if (*bp == 0) return(NULL);
		}
		else if (*bp == '.' && bp[1] == 'b' && bp[2] == 's' && bp[3] == 's')
			goto scanfortext;
		else bp++;
	}
	return(NULL);
}
#endif
/* Converts a register name into a register number */
static int GetRegNumber(char *name)
{
	register char *n = name;
	if (*n == 'e') n++;
	else {
		char tmp[3];
		tmp[0] = 'e';
		tmp[1] = *n++;
		tmp[2] = (*n == 'l') ? 'x' : *n;
		return(ESP+GetRegNumber(tmp));
	}
	switch (*n++) {
		case 'a': return(EAX);
		case 'b': return (*n == 'x')? EBX : EBP;
		case 'c': return(ECX);
		case 'd': return( *n == 'x')? EDX : EDI;
		case 's': return (*n == 'i') ? ESI : ESP;
	}
	fprintf(stderr,"bad register name %c%c%c\n",name[0],name[1],name[2]);
	exit(1);
	return(0);
}

/*
Parser for one instruction. It separates the instruction into
opcode (Name field), source and destination.
*/
static char *AddNextInstruction(unsigned char *bp,BasicBlock *bb,unsigned char **pp)
{
	unsigned char *p,*start;
	int i,regcount,firstCodeChar;
	Instruction *ins;

	start = p = bp;
	if (*p == '_' && p[1] == '$') {
		*pp = bp;
		return(NULL);
	}
	if (*bp == 1) {
		while (*bp == 1) bp++;
	}
	if (*bp == '\t') bp++;
	if (*bp == ';')
		goto skipline;
	if (*bp == '.') {
		if (!strncmp(bp,".data",5) || !strncmp(bp,".bss",4)) {
			bp = strstr(bp,".text");
			*pp = bp;
			return(bp);
		}
skipline:
		while (*bp && *bp != '\n') bp++;
		if (*bp == '\n') bp++;
		*pp = bp;
		if (*bp == 0) return(NULL);
		return(bp);
	}
	if (InstructionIndex < MAXINSTRUCTION-50) {
		ins = &InstructionTable[InstructionIndex];
		InstructionIndex++;
		memset(ins,0,sizeof(Instruction));
	}
	else {
		fprintf(stderr,"Basic block too big!\n");
		return(NULL);
	}
	i = 0;
	firstCodeChar = *bp;
	if (firstCodeChar == 'j')
		ins->Flags |= ISJUMP;
	else if (firstCodeChar == 'f')
		ins->Flags |= ISFLOAT;
	while (*bp >= 'a' && *bp <= 'z') {
		if (i < 10)
			ins->Name[i++] = *bp++;
		if (i > 8) {
			ins->Name[i] = 0;
			fprintf(stderr,"overflow in instruction name %s ",ins->Name);
			while (*bp && *bp != '\n') fprintf(stderr,"%c",*bp++);
			fprintf(stderr,"\n");
			exit(1);
		}
	}
	ins->Start = start;
	bb->NrOfInstructions++;
	ins->Name[i] = 0;
	if (i > 3 && ins->Name[0] == 'm' && ins->Name[1] == 'o' &&
		ins->Name[2] == 'v') {
		if (ins->Name[3] == 'l') ins->Flags |= ISMOVL;
		else if (ins->Name[3] == 's' && ins->Name[4] == 'b' && ins->Name[5] == 0) {
			ins->Flags |= ISMOVSB;
		}
		else if (ins->Name[3] == 's' && (ins->Name[4] == 'w' || ins->Name[4] == 'b')
			&& ins->Name[5] == 'l') {
			if (ins->Name[4] == 'w') ins->Flags |= ISMOVSWL;
			else ins->Flags |= ISMOVSBL;
		}
		ins->Flags |= ISGENERICMOVE;
	}
	if (i == 3 && !strcmp(ins->Name,"ret")) {
		while (*bp && *bp != '\n') bp++;
		if (*bp == '\n') bp++;
		*pp = bp;
		ins->End = bp;
		return(NULL);
	}
	if (i == 4 && firstCodeChar == 'l' && ins->Name[1] == 'e' &&
		ins->Name[3] == 'l')
		ins->Flags |= ISLEAL;
	if (i == 4 && firstCodeChar == 'c' && ins->Name[2] == 'p' 
		&& ins->Name[3] == 'l' && ins->Name[1] == 'm') {
		ins->Flags |= ISCOMPARE;
	}
	while (*bp == ' ' || *bp == '\t') bp++;
	if (*bp == '\n') {
		bp++;
		ins->End = bp;
		*pp = bp;
		return(bp);
	}
	i = regcount = 0;
	if (*bp == '%') ins->Flags |= ISREGSRC;
	while (*bp && *bp != ',') {
		int c = *bp;
		if (c == '\n') break;
		if (i < MAXIDSIZE)
			ins->src[i++] = c;
		else ins->Flags |= TRUNCATED;
		bp++;
		if (c == '(') {
			ins->Flags |= SRCOFFSET;
			while (*bp && *bp != ')') {
				c = *bp++;
				if (i < 40)
					ins->src[i++] = c;
				if (c == ',') {
					ins->Flags |= SRCDEREFERENCE;
				}
				else if (c == '%') {
					int r;

					r = GetRegNumber(bp);
					if (regcount == 0) ins->SrcReg = r;
					else ins->SrcReg |= (r << 8);
					regcount++;
				}
			}
			if (*bp == ')') ins->src[i++] = *bp++;
		}
		else if (c == '%') {
			int r;

			r = GetRegNumber(bp);
			if (regcount == 0) ins->SrcReg = r;
			else ins->SrcReg |= (r << 8);
			regcount++;
		}
		else if (c == '_') {
			while (*bp && ((*bp >= 'a' && *bp <= 'z') || (*bp >= 'A' && *bp <= 'Z'))) {
				if (*bp == ',') break;
				if (i < MAXIDSIZE) {
					ins->src[i++] = *bp++;
				}
				else {
					ins->Flags |= TRUNCATED;
					bp++;
				}
			}
		}
	}
	if (*bp == ',' || (*bp == ' ' || *bp == '\t')) bp++;
	else if (*bp == '\n'){
		if (!strcmp(ins->Name,"call")) {
			ins->Flags |= ISCALL;
			bb->Flags |= ISCALL;
			if (bb->FirstCall == 0)
				bb->FirstCall = (unsigned char)(InstructionIndex-1);
			bb->LastCall = (unsigned char)(InstructionIndex-1);
		}
		bp++;
		ins->End = bp;
		return(bp);
	}
	while (*bp == ' ' || *bp == '\t') bp++;
	if (*bp == '%') ins->Flags |= ISREGDST;
	i = regcount = 0;
	while (*bp && *bp != ' ' && *bp != '\n') {
		int c = *bp++;
		if (i < MAXIDSIZE)
			ins->dst[i++] = (unsigned char)c;
		else
			ins->Flags |= TRUNCATED;
		if (c == '(') {
			ins->Flags |= DSTOFFSET;
			while (*bp && *bp != ')') {
				c = *bp++;
				if (i < MAXIDSIZE)
					ins->dst[i++] = (unsigned char)c;
				else ins->Flags |= TRUNCATED;
				if (c == ',') {
					ins->Flags |= DSTDEREFERENCE;
				}
				else if (c == '%') {
					int r;

					r = GetRegNumber(bp);
					if (regcount == 0) ins->DstReg = (unsigned char)r;
					else ins->DstReg |= (r << 8);
					regcount++;
				}
			}
			if (*bp == ')' && i < MAXIDSIZE) ins->dst[i++] = *bp++;
			else if (i >= MAXIDSIZE) ins->Flags |= TRUNCATED;
		}
		else if (c == '%') {
			int r;

			r = GetRegNumber(bp);
			if (regcount == 0) ins->DstReg = r;
			else ins->DstReg |= (r << 8);
			regcount++;
		}
		else if (c == '_') {
			while (*bp && ((*bp >= 'a' && *bp <= 'z') || (*bp >= 'A' && *bp <= 'Z'))) {
				if (*bp == ',') break;
				if (i < MAXIDSIZE) {
					ins->dst[i++] = *bp++;
				}
				else {
					ins->Flags |= TRUNCATED;
					bp++;
				}
			}
		}
	}
	while (*bp && *bp != '\n') bp++;
	if (*bp == 0) {
		ins->End = bp;
		*pp = NULL;
		return(NULL);
	}
	if (*bp == '\n') bp++;
	ins->End = bp;
	return(bp);
}

/* Adds instructions to the basic block until it finds a label
*/
static unsigned char *FindEndBlock(unsigned char *bp,BasicBlock *bb,unsigned char *stop)
{
	unsigned char *r=bp,*result;
	bb->NrOfInstructions = 0;
	while ((r=AddNextInstruction(r,bb,&result))!=NULL) {
		if (InstructionIndex > 0 
			&& InstructionTable[InstructionIndex-1].Flags & TRUNCATED) {
			result = NULL;
			bb->NrOfInstructions = 0;
			fprintf(stderr,"Maximum identifier length exceeded.\n");
			fprintf(stderr,"Quitting optimization\n");
			return NULL;
		}
		if (r && r >= stop) break;
	}
	return(result);
}
#ifdef STANDALONE
static char *FindBasicBlock(unsigned char *bp,BasicBlock *block,unsigned char *stop)
{
	char *bb,*be;


	bb = FindBeginBlock(bp,block);
	if (bb == NULL) return(NULL);
	be = FindEndBlock(bb,block,stop);
	return(be);
}
#endif
/* Invalidates the contents of the given register ('which') if
   they are equal to the given character string.
*/
static void doclobber(unsigned char *p,int which)
{
	if (p == Nullst) return;
	if (p == NULL) return;
	if (which != EAX && State[EAX] && !strcmp(State[EAX],p)) {
		Printf1("eax = NULL\n");
		State[EAX] = Nullst;
	}
	if (which != EBX && State[EBX] && !strcmp(State[EBX],p)) {
		Printf1("ebx = NULL\n");
		State[EBX] = Nullst;
	}
	if (which != ECX && State[ECX] && !strcmp(State[ECX],p)) {
		Printf1("ecx = NULL\n");
		State[ECX] = Nullst;
	}
	if (which != EDX && State[EDX] && !strcmp(State[EDX],p)) {
		Printf1("edx = NULL\n");
		State[EDX] = Nullst;
	}
	if (which != ESI && State[ESI] && !strcmp(State[ESI],p)) {
		Printf1("esi = NULL\n");
		State[ESI] = Nullst;
	}
	if (which != EDI && State[EDI] && !strcmp(State[EDI],p)) {
		Printf1("edi = NULL\n");
		State[EDI] = Nullst;
	}
}

/* Replaces in the given buffer (str) the register named
   'src' with the register named 'dst' and writes the
   modified output into the 'out' buffer
*/
static int doreplace(unsigned char *str,unsigned char *src,unsigned char *dst,unsigned char *out)
{
	unsigned char *p = str;
	unsigned char *d = out;
	int result = 0;

	while (*p) {
		if (*p == '%') {
			*d++ = *p++;
			if (p[0] == src[0] && p[1] == src[1] && p[2] == src[2]) {
				*d++ = dst[0];
				*d++ = dst[1];
				*d++ = dst[2];
				p += 3;
				result++;
			}
			else if (p[0] != 'e') {
				if (p[0] == src[1] && p[1] == src[2]) {
					*d++ = dst[1];
					*d++ = dst[2];
					p += 2;
					result++;
				}
				else if (p[0] == src[1] && p[1] == 'l' && src[2] == 'x') {
					*d++ = dst[1];
					*d++ = 'l';
					p += 2;
				}
			}
		}
		else *d++ = *p++;
	}
	*d = 0;
	return(result);
}

static int fixRegNr(int SrcReg,int reg,int oldreg)
{
	int r1,r2;

	if (SrcReg < ESP) return reg;
	else if (SrcReg < SP) {
		return reg + ESP;
	}
	else if (SrcReg & 0xFF00) {
		r1 = SrcReg & 0xFF;
		r2 = SrcReg >> 8;
		if (oldreg == r1) {
			return (reg | (r2 << 8));
		}
		else if (oldreg == r2) {
			return ((reg << 8) | r1);
		}
		else 
			printf("internal compiler error 123 in optimizer\n");
	}
	return 0;
}

static int ReplaceRegister(char *regsrc,char *regdst,BasicBlock *bb,int first,int last,int reg)
{
	Instruction *ins,*insDst;
	unsigned char *src,*dst;
	int dochanged,oldreg;

	ins = &InstructionTable[first];
	if (ins->Flags & CHANGED) {
		insDst = &InstructionTable[ins->ChangedIdx];
		dst = insDst->dst;
		src = insDst->src;
	}
	else {
		dst = ins->dst;
		src = ins->src;
	}
	ins->Flags |= CHANGED;
	ins->ChangedIdx = bb->ChangedCounter;
	insDst = &InstructionTable[bb->ChangedCounter];
	bb->ChangedCounter++;
	oldreg = GetRegNumber(regsrc);
	memset(insDst,0,sizeof(Instruction));
	if (!doreplace(dst,regsrc,regdst,insDst->dst)) {
		bb->ChangedCounter--;
		return(0);
	}
	ins->DstReg = reg;
	strcpy(insDst->src,src);
	strcpy(insDst->Name,ins->Name);
	first++;
	ins++;
	while (first <= last) {
		dochanged = 0;
		if (ins->Flags & CHANGED) {
			insDst = &InstructionTable[ins->ChangedIdx];
			src = insDst->src;
			dst = insDst->dst;
		}
		else {
			src = ins->src;
			dst = ins->dst;
		}
		insDst = GetNextChangedInstruction(ins,bb);
		strcpy(insDst->Name,ins->Name);
		if (doreplace(src,regsrc,regdst,insDst->src)) {
			ins->SrcReg = fixRegNr(ins->SrcReg,reg,oldreg);
			dochanged++;
		}
		if (first != last) {
			if (doreplace(dst,regsrc,regdst,insDst->dst)) {
				ins->DstReg = fixRegNr(ins->DstReg,reg,oldreg);
				dochanged++;
			}
		}
		else strcpy(insDst->dst,dst);
		if (dochanged) {
			ins->Flags |= CHANGED;
		}
		else {
			bb->ChangedCounter--;
			ins->Flags &= ~ CHANGED;
		}
		first++;
		ins++;
	}
	bb->Registers[reg] = 1;
	return(1);
}

int testSafeReplacement(char *s)
{
	if (*s++ != '(') return 0;
	if (*s++ != '%') return 0;
	if (*s++ != 'e') return 0;
	s += 2;
	if (*s++ != ',') return 0;
	if (*s++ != '%') return 0;
	if (*s++ != 'e') return 0;
	s += 2;
	if (*s != ')') return 0;
	return 1;
}

static int AvoidClobber(char *reg,int idxInstruction,BasicBlock *bb)
{
	int i,n,lastidx;
	Instruction *ins;

	if (State[ECX] != NULL && State[ECX] != Nullst) {
		if (State[EDX] != NULL && State[EDX] != Nullst) {
			return(0);
		}
	}
	i = idxInstruction+1;
	n = bb->NrOfInstructions;
	if (i >= n) return(0);
	ins = &InstructionTable[i];
	lastidx = -1;
	/* Find the first instruction that stores into that register */
	while (i < n) {
		if (ins->Flags & (CHANGED|ISCALL|TRUNCATED)) return(0);
		if (ins->SrcReg > EBP || ins->DstReg > EBP) {
			if (ins->SrcReg > EBP) {
				if (!testSafeReplacement(ins->src)) return 0;
			}
			if (ins->DstReg > EBP) {
				if (!testSafeReplacement(ins->dst)) return 0;
			}
		}
		if (ins->Name[0] == 'f') return(0);
		if (ins->Name[0] == 'i') {
			if (!strncmp(ins->Name,"idiv",4)) return(0);
			if (!strncmp(ins->Name,"imul",4)) return(0);
		}
		else if (!strncmp(ins->Name,"div",3)) return(0);
		else if (!strncmp(ins->Name,"mul",3)) return(0);
		if (ins->DstReg == ECX || ins->DstReg == EDX) return(0);
		if (ins->SrcReg == EDX || ins->DstReg == ECX) return(0);
		if (ins->dst[0] == '%') { /* if is a register store operation */
			if (ins->Flags & ISGENERICMOVE)
			if (ins->dst[1] == *reg && ins->dst[2] == reg[1] && ins->dst[3] == reg[2]) {
				if (ins->SrcReg > EBP) return(0);
				if (ins->dst[1] == ins->src[1] && ins->dst[2] == ins->src[2] &&
					ins->dst[3] == ins->src[3] && ins->src[0] == ins->dst[0]) {
					goto goon;
				}
				lastidx = i;
				break;
			}
		}
goon:
		i++;
		ins++;
	}
	if (lastidx < 0) return(0);
	if (State[ECX] == NULL || State[ECX] == Nullst) {
		int r = ReplaceRegister(reg,"ecx",bb,idxInstruction,lastidx,ECX);
		return (r)? ECX : 0;
	}
	if (State[EDX] == NULL || State[EDX] == Nullst) {
		int r = ReplaceRegister(reg,"edx",bb,idxInstruction,lastidx,EDX);
		return (r)? EDX : 0;
	}
	return(0);
}
static int IsAliveValue(BasicBlock *bb,int idx,int regNum)
{
	int i = idx,flags;
	Instruction *ins = &InstructionTable[idx];

	if (hasRegisterVariables) {
		if (regNum == ESI) return 1;
		if (regNum == EBX) return 1;
		if (regNum == EDI) return 1;
	}
	while (i < bb->NrOfInstructions) {
		if (ins->SrcReg == regNum) return(1);
		if (ins->SrcReg > EBP) return(1);
		if (ins->DstReg > EBP) {
			if (!(ins->DstReg == ESP && ins->src[0] == '$' && ins->Name[0] == 'a'))
				return(1);
		}
		flags = ins->Flags;
		if ((flags & ISGENERICMOVE) == 0) {
			if (ins->DstReg == regNum) {
				if (ins->Flags & ISLEAL) return(0);
				return(1);
			}
			if (ins->Flags & ISCOMPARE &&
				ins->SrcReg == regNum)
				return 1;
			if (ins->Name[0] == 'o' && ins->Name[1] == 'r' &&
				ins->SrcReg == regNum)
				return 1;
			if (ins->Name[0] == 'a' && ins->Name[1] == 'n' &&
				ins->SrcReg == regNum)
				return 1;
		}
		if (flags & ISCALL) {
			if (regNum == EAX || regNum == ECX || regNum == EDX)
				return(0);
		}
		if (regNum == EAX || regNum == ECX) {
			if (ins->Name[0] == 'i') {
				if (!strncmp(ins->Name,"idiv",4)) return(1);
				if (!strncmp(ins->Name,"imul",4)) return(1);
			}
			else if (!strncmp(ins->Name,"div",3)) return(1);
			else if (!strncmp(ins->Name,"mul",3)) return(1);
		}
		if (!strcmp(ins->Name,"rep")) return(1);
		if (!strncmp(ins->Name,"movs",4)
			|| !strncmp(ins->Name,"stos",4) || !strncmp(ins->Name,"scas",4)) {
			return 1;
		}
		if (flags & ISGENERICMOVE) {
			if (ins->dst[0] == '%' && ins->DstReg == regNum)
				return(0);
			else if (ins->DstReg == regNum) return(1);
		}
		ins++;
		i++;
	}
	return(0);
}

static int isUsedInBlock(int idxInstruction,unsigned char *old,BasicBlock *bb,int aReg)
{
	int c = *old;
	Instruction *ins;
	int result = 0;

	ins = &InstructionTable[idxInstruction];
	while (idxInstruction < bb->NrOfInstructions) {
		if (c == ins->src[0] && !strcmp(ins->src,old)) {
			result++;
		}
		if (c == ins->dst[0] && !strcmp(ins->dst,old)) {
			if (strcmp(ins->Name,"cmpl"))
				return(result);
			else result++;
		}
		if (ins->Flags & (ISCALL|CHANGED)) return(0);
		if (ins->DstReg == ECX || ins->DstReg == EDX)
			return(0);
		if (ins->SrcReg == ECX || ins->SrcReg == EDX)
			return(0);
		if (ins->Name[2] == 'q' && ins->Name[1] == 'd')
			return(0);
		if (ins->Name[0] == 'r' && ins->Name[1] == 'e' && ins->Name[2] == 'p')
			return(0);
		if (ins->Name[0] == 's' && ins->Name[1] == 'h' && ins->Name[3] == 'l')
			return(0);
		if (ins->src[0] == '%' && ins->src[1] == 'c')
			return(0);
		if (ins->dst[0] == '%' && (ins->Flags & ISGENERICMOVE) && ins->DstReg == aReg) {
			if (ins->SrcReg != aReg)
				break;
		}
		ins++;
		idxInstruction++;
	}
	return(result);
}

static int TestIfReturnFalse(Instruction *nextIns,int regNum)
{
	nextIns++;
	if (!strcmp(nextIns->Name,"jne")) {
		nextIns++;
		if (nextIns->Flags & ISMOVL) {
			if (nextIns->src[0] == '$' && nextIns->src[1] == '0'
				&& nextIns->src[2] == 0) {
				if (nextIns->dst[0] == '%' && nextIns->DstReg == regNum) {
					nextIns->Flags |= DELETED;
					Printf1("Optimization 12\n");
					return(1);
				}
			}
		}
	}
	return(0);
}

static void ChangeRedundantLoad(Instruction *ins,int regNum,BasicBlock *bb,int idxInstruction,int changeFlag)
{
	unsigned char *regname,tbuf[60];
	Instruction *insDst,*nextIns;
	int SrcReg;

	nextIns = &InstructionTable[idxInstruction+1];
	regname = RegisterNames[regNum];
	if (hasRegisterVariables) goto skipOptims;
	if (nextIns->Flags & (CHANGED|DELETED)) goto skipOptims;
	if (nextIns->Flags & (ISGENERICMOVE|ISLEAL)) {
		SrcReg = nextIns->SrcReg;
		if (nextIns->Flags & ISLEAL) {
			if (nextIns->DstReg == ins->DstReg) {
				if (SrcReg > SP) {
					if (((SrcReg & 0xFF) == ins->DstReg) ||
						(((SrcReg >> 8)&0xFF) == ins->DstReg)) {
						SrcReg = ins->DstReg;
						if (doreplace(nextIns->src,RegisterNames[SrcReg],RegisterNames[regNum],tbuf))  {
							ins->Flags |= DELETED;
							deleted++;
							redundant--;
							insDst = ChangeInstruction(nextIns,bb,nextIns->Name,tbuf,nextIns->dst);
							SrcReg = nextIns->SrcReg;
							if ((SrcReg & 0xFF) == ins->DstReg) {
								regNum = ((SrcReg&0xFF)|regNum);
							}
							else {
								regNum = (regNum << 8) | (SrcReg >> 8);
							}
							nextIns->SrcReg = regNum;
							Printf1("Optimization Nr 10\n");
							return;
						}
					}
				}
			}
		}
		/*
			Try to catch sequences like:
				movl    %edi,      -4(%ebp)
				.
				.
				.
			    movl    -4(%ebp),  %esi deleted
  				movswl  50(%esi),  %esi Replace by: movswl   50(%edi), %esi
			The rationale is that it is not worth to move a register into another,
			if that register will be used both as source and destination.
			Replace the source by the register, sparing one instruction.
			N.B. This will produce a wonderful BUG if the test is not done
			for a sequence like:
			    movl -8(%ebp),%edi                       deleted
    			movl %edi,(,%edi)    movl        %eax,     (,%edi)

			Since -8(%ebp) was in %eax, the deleting of the first
			instruction will use whatever was in edi before!!!
			This will happen when you assign a member of a structure to
			itself, for instance
				structure->Next = structure;
			to make a circular list.

		*/
		if (nextIns->SrcReg == ins->DstReg && 
			nextIns->DstReg == ins->DstReg
			&& ins->DstReg < EBP 
			&& ((nextIns->Flags & DSTDEREFERENCE)==0)) {
			if (doreplace(nextIns->src,RegisterNames[SrcReg],RegisterNames[regNum],tbuf))  {
				ins->Flags |= DELETED;
				State[ins->DstReg] = Nullst;
				deleted++;
				redundant--;
				insDst = ChangeInstruction(nextIns,bb,nextIns->Name,tbuf,nextIns->dst);
				nextIns->SrcReg = regNum;
				Printf1("Optimization Nr 9\n");
				return;
			}
		}
		if ((nextIns->Flags & CHANGED) == 0 &&
			ins->DstReg < EBP &&
			nextIns->DstReg == ins->DstReg && !IsAliveValue(bb,idxInstruction+1,ins->DstReg)) {
			if (doreplace(nextIns->dst,RegisterNames[nextIns->DstReg],RegisterNames[regNum],tbuf))  {
				ins->Flags |= DELETED;
				deleted++;
				redundant--;
				insDst = ChangeInstruction(nextIns,bb,nextIns->Name,nextIns->src,tbuf);
				State[ins->DstReg] = Nullst;
				nextIns->DstReg = regNum;
				Printf1("Optimization 9.1\n");
				return;
			}
		}
#if 1
		/* Replace
			movl %eax,%edi
			movl %edi,-24(%ebp)

			with
			movl %eax,-24(%ebp)

		*/
		else if (nextIns->SrcReg == ins->DstReg && (ins->Flags & ISREGDST) &&
				(nextIns->Flags & CHANGED) == 0 && 
				ins->DstReg < EBP &&
				(ins->Flags & ISMOVL) &&
				(nextIns->Flags & ISMOVL) && (nextIns->Flags & ISREGSRC)) {
			if (!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
				sprintf(tbuf,"%%%s",regname);
				insDst = ChangeInstruction(nextIns,bb,nextIns->Name,tbuf,nextIns->dst);
				nextIns->SrcReg = regNum;
				ins->Flags |= DELETED;
				deleted++;
				redundant--;
				State[ins->DstReg] = Nullst;
				Printf1("Optimization 18\n");
				return;
			}
		}
#endif
		else if (nextIns->src[0] == '$' && nextIns->DstReg == ins->DstReg) {
			insDst = nextIns + 1;
			if ((insDst->Flags & ISMOVL) && 
				ins->DstReg < EBP &&
				(insDst->Flags & ISREGDST)
				&& insDst->DstReg == ins->DstReg) {
				if (doreplace(nextIns->dst,RegisterNames[nextIns->DstReg],RegisterNames[regNum],tbuf))  {
					ins->Flags |= DELETED;
					deleted++;
					redundant--;
					State[ins->DstReg] = Nullst;
					insDst = ChangeInstruction(nextIns,bb,nextIns->Name,nextIns->src,tbuf);
					nextIns->SrcReg = regNum;
					Printf1("Optimization Nr 14\n");
					return;
				}
			}
		}
	}
	/* Replace sequences like
		cmpl $0,%esi
		by
		or   %esi,%esi
		that is shorter
	*/
	else if (nextIns->src[0] == '$' && nextIns->src[1] == '0' && nextIns->src[2] == 0) {
		if (nextIns->Flags & ISCOMPARE && nextIns->dst[0] == '%') {
			if (nextIns->DstReg == ins->DstReg && !IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
				ins->Flags |= DELETED;
				deleted++;
				redundant--;
				sprintf(tbuf,"%%%s",regname);
				insDst = ChangeInstruction(nextIns,bb,"or",tbuf,tbuf);
				Printf1("Optimization Nr 11\n");
				TestIfReturnFalse(nextIns,regNum);
				return;
			}
		}
	}
	/* Try to catch sequences like
		movl %eax,%edi
		cmpl $45, %edi

		and replace them with
		cmpl $45,%eax
	*/
	else if ((nextIns->Flags & (CHANGED|DELETED)) == 0 && 
			(nextIns->Flags & ISCOMPARE) &&
			ins->DstReg < EBP &&
			 nextIns->src[0] == '$' && nextIns->dst[0] == '%' &&
			 !strcmp(nextIns->dst,ins->dst) && !IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
		sprintf(tbuf,"%%%s",regname);
		insDst = ChangeInstruction(nextIns,bb,nextIns->Name,nextIns->src,tbuf);
		ins->Flags |= DELETED;
		nextIns->DstReg = regNum;
		State[ins->DstReg] = Nullst;
		Printf1("Optimization 17\n");
		deleted++;
		redundant--;
		return;
	}
	/* Try to change a sequence of instructions like:
		movl %eax,%edi
		cmpl %edi,-4(%ebp)

		into

		cmpl %eax,-4(%ebp)
		Conditions:
			1. Do not mess with already changed instructions (too complex)
			2. Must be a compare operation
			3. The source must be a register
			4. That register should be the same that is being moved
	*/
	else if ((nextIns->Flags & CHANGED)==0 &&
		ins->DstReg < EBP &&
		(nextIns->Flags & ISCOMPARE) && nextIns->src[0] == '%' &&
			nextIns->SrcReg == ins->DstReg) {
		sprintf(tbuf,"%%%s",regname);
		insDst = ChangeInstruction(nextIns,bb,nextIns->Name,tbuf,nextIns->dst);
		ins->Flags |= DELETED;
		deleted++;
		redundant--;
		State[ins->DstReg] = Nullst;
		Printf1("Optimization 15\n");
		return;

	}
	else if ((nextIns->Flags & CHANGED)== 0 && 
		!strcmp(nextIns->Name,"addl") &&
		ins->DstReg < EBP &&
			 nextIns->src[0] == '$' &&  nextIns->DstReg == ins->DstReg &&
			 nextIns->dst[0] == '%' && ins->dst[0] == '%') {
	/* Try to change a sequence of instructions like:
		movl %eax,%edi
		addl $5,%edi

		into

		leal 5(%eax),%edi
		Conditions:
			1. Do not mess with already changed instructions (too complex)
			2. Must be a addl operation
			3. The source must be an immediate
			4. The destination register should be the same as the source register
	*/
		sprintf(tbuf,"%s(%%%s)",nextIns->src+1,regname);
		insDst = ChangeInstruction(nextIns,bb,"leal",tbuf,ins->dst);
		nextIns->Flags |= ISLEAL;
		nextIns->SrcReg = regNum;
		nextIns->DstReg = ins->DstReg;
		ins->Flags |= DELETED;
		deleted++;
		redundant--;
		State[ins->DstReg] = Nullst;
		Printf1("Optimization 16\n");
		return;

	}
	/*
		Try to substitute
		mov %eax,%edi
		push %edi

		with
		push %eax
	*/
	else if ((ins->Flags & ISMOVL) && 
		(nextIns->Flags & (CHANGED|DELETED)) == 0 && nextIns->Name[0] == 'p' &&
			 nextIns->Name[1] == 'u' && nextIns->src[0] == '%' &&
			 nextIns->SrcReg == ins->DstReg) {
		if (!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
			sprintf(tbuf,"%%%s",regname);
			insDst = ChangeInstruction(nextIns,bb,nextIns->Name,tbuf,"");
			ins->Flags |= DELETED;
			deleted++;
			redundant--;
			State[ins->DstReg] = Nullst;
			Printf1("Optimization 18\n");
			return;
		}
	}
skipOptims:
	if (!changeFlag) return;
	if (strlen(ins->src) <4) return;
	if (ins->DstReg > EBP) return;
	if (strcmp(ins->Name,"movl")) {
		/*
			We can use this byte widening instructions only with memory
			references. I assume that the compiler widens the arguments always
			before loading a register with a 16 or 8 bit value, a safe
			assumption I suppose.
		*/
//		strcpy(insDst->Name,"movl"); /*++++++++++++++++++*/
		return;
	}
//	else	strcpy(insDst->Name,ins->Name);
	insDst = GetNextChangedInstruction(ins,bb);
	strcpy(insDst->Name,ins->Name);
	/* Print the regname into the source of the changed instruction */
	sprintf(tbuf,"%%%s",regname);
	strcpy(insDst->src,tbuf);
	/* The destination doesn't change */
	strcpy(insDst->dst,ins->dst);
	/* Update flags etc */
	ins->SrcReg = regNum;
	Printf1("Optimization 5\n");
}

static int ReadValue(char *src)
{
	int result,r;

	if (src[0] == '0' && (src[1] == 'x' || src[1] == 'X')) {
		r = sscanf(src+2,"%x",&result);
	}
	else {
		r = sscanf(src,"%d",&result);
	}
	if (r) return(result);
	return(0);
}

static Instruction *GetLastInstruction(int idxInstruction)
{
	int li = idxInstruction;
	Instruction *lastIns = NULL;

	do {
		li--;
		lastIns = &InstructionTable[li];
	} while (li >= 0 && (lastIns->Flags & DELETED));
	if (li >= 0) return(lastIns);
	return(NULL);
}
#if 1
static int CheckValueAlreadyLoaded(char *p)
{
	if (State[EAX] && !strcmp(State[EAX],p)) {
		return(EAX);
	}
	if (State[EBX] && !strcmp(State[EBX],p)) {
		return(EBX);
	}
	if (State[ECX] && !strcmp(State[ECX],p)) {
		return(ECX);
	}
	if (State[EDX] && !strcmp(State[EDX],p)) {
		return(EDX);
	}
	if (State[ESI] && !strcmp(State[ESI],p)) {
		return(ESI);
	}
	if (State[EDI] && !strcmp(State[EDI],p)) {
		return(EDI);
	}
	return(0);
}
#endif
void FixCalls(Instruction *ins,BasicBlock *bb,int idxInstruction)
{
	int last,i,first;

	ins->Flags &= ~ISCALL;
	if (idxInstruction == bb->LastCall) {
		if (bb->FirstCall == idxInstruction) {
			bb->FirstCall = bb->LastCall = 0;
			return;
		}
		last = bb->FirstCall;
		for (i=bb->FirstCall+1;i<idxInstruction-1;i++) {
			if (InstructionTable[i].Flags & ISCALL)
				last = i;
		}
		if (last == bb->FirstCall) {
			bb->FirstCall = bb->LastCall = 0;
			return;
		}
		bb->LastCall = last;
		return;
	}
	if (idxInstruction == bb->FirstCall) {
		if (bb->LastCall == idxInstruction) {
			bb->FirstCall = bb->LastCall = 0;
			return;
		}
		first = 0;
		for (i=bb->FirstCall+1;i<bb->LastCall;i++) {
			if (InstructionTable[i].Flags & ISCALL) {
				first = i;
				break;
			}
		}
		bb->FirstCall = first;
		if (first == 0) bb->LastCall = 0;
		return;
	}
}
static char tbuf[70];
static unsigned char *src;
static unsigned char *dst;
static unsigned char *opcode;
static unsigned char *old,*savesrc;
static int regdst,regsrc,isImmediate;
static int aReg,isMovl,isRedundant;
static Instruction *insDst,*lastIns,*changedInstruction,*nextIns;
static Instruction *ins;
static BasicBlock *bb;
static int idxInstruction;

static int RegToRegCopy(void)
{
#if 1
	/* Replace
	movl %eax,%edi
    movl %edi,-24(%ebp)

    with
    movl %eax,-24(%ebp)

    */
    if (nextIns->SrcReg == ins->DstReg &&
		ins->DstReg != EAX &&
       (nextIns->Flags & CHANGED) == 0 && !strcmp(ins->Name,"movl") &&
       !strcmp(nextIns->Name,"movl") && nextIns->src[0] == '%') {
       if (!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
          insDst = ChangeInstruction(nextIns,bb,nextIns->Name,ins->src,nextIns->dst);
          nextIns->SrcReg = ins->SrcReg;
          ins->Flags |= DELETED;
          deleted++;
          Printf1("Optimization 18\n");
//		  printf("1:\t%s\t%s\t%s\n2:\t%s\t%s\t%s\n3:\t%s\t%s\t%s\n",ins->Name,ins->src,ins->dst,
//			nextIns->Name,nextIns->src,nextIns->dst,insDst->Name,insDst->src,insDst->dst);
		  State[ins->SrcReg] = nextIns->dst;
          return 2;
       }
    }
	return 0;
#endif
   /* Try to catch sequences like
         movl %eax,%edi
         cmpl $45, %edi
         and replace them with
         cmpl $45,%eax
   */
   if ((nextIns->Flags & CHANGED) == 0 && (nextIns->Flags & ISCOMPARE) &&
        nextIns->src[0] == '$' && nextIns->dst[0] == '%' &&
		nextIns->DstReg != EAX &&
        !strcmp(nextIns->dst,ins->dst) && 
		!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
        insDst = ChangeInstruction(nextIns,bb,nextIns->Name,nextIns->src,ins->src);
        ins->Flags |= DELETED;
        nextIns->DstReg = ins->SrcReg;
        Printf1("Optimization 17\n");
        deleted++;
        return 1;
	}
    return 0;
}


static int compare(void)
{
	int reg;

	if (ins->Flags & (CHANGED|DELETED))
		return 1;
	/*
		replace
		cmpl $0,reg
		by
		or reg,reg
	*/
	if (regdst && !regsrc && isImmediate && src[1] == '0' && src[2] == 0) {
		sprintf(tbuf,"%%%s",dst);
		ChangeInstruction(ins,bb,"or",tbuf,tbuf);
		Printf1("compl->or\n");
		TestIfReturnFalse(ins,ins->DstReg);
		return(1);
	}
	else
	if (regdst /*&& isImmediate*/ && idxInstruction > 1) {
		/*
			movl -4(%ebp),%esi
			cmpl $45,%esi
				to
			cmpl $45,-4(%ebp)
		*/
		lastIns = GetLastInstruction(idxInstruction);
		if (isImmediate &&
			!hasRegisterVariables &&
			lastIns && (lastIns->Flags & ISREGDST) &&
		    (lastIns->Flags & (CHANGED|DELETED)) == 0 &&
			(lastIns->Flags & ISMOVL) && 
			lastIns->DstReg == ins->DstReg	&& 
			(lastIns->Flags & ISREGSRC) == 0 &&
			!IsAliveValue(bb,idxInstruction+1,ins->DstReg)) {
			ChangeInstruction(ins,bb,opcode,ins->src,lastIns->src);
			lastIns->Flags |= DELETED;
			if (ins->DstReg < EBP)
				State[ins->DstReg] = NULL;
			deleted++;
			Printf1("Optimization 19\n");
			return(1);
		}
		/*
		movl	116(%esi),%esi
		cmpl	%esi,%edi
		to
		cmpl	116(%esi),%edi
		savings: two bytes
		*/
		if (regsrc &&
			!isImmediate &&
			!hasRegisterVariables &&
			lastIns && (lastIns->Flags & ISREGDST) &&
		    (lastIns->Flags & (CHANGED|DELETED)) == 0 &&
			(lastIns->Flags & ISMOVL) && 
			lastIns->DstReg == ins->SrcReg	&& 
			(lastIns->Flags & ISREGSRC) == 0 &&
			!IsAliveValue(bb,idxInstruction+1,lastIns->DstReg)) {
			ChangeInstruction(ins,bb,opcode,lastIns->src,ins->dst);
			lastIns->Flags |= DELETED;
			deleted++;
			State[ins->SrcReg] = Nullst;
			Printf1("Optimization 48\n");
			return(1);
		}
	}
	if (!regdst /*&& isImmediate*/ && ins->Name[3] == 'l') {
		reg = CheckValueAlreadyLoaded(ins->dst);
		if (reg) {
			sprintf(tbuf,"%%%s",RegisterNames[reg]);
			if (isImmediate && ins->src[1] == '0' && ins->src[2] == 0) {
				ChangeInstruction(ins,bb,"orl",tbuf,tbuf);
			}
			else ChangeInstruction(ins,bb,ins->Name,ins->src,tbuf);
			Printf1("Optimization 44\n");
		}
	}
	return 1;
}

static int inlinestrlen(void)
{
	Instruction *i1,*ip,*in;
	int condition;

	ip = NULL;
	/* i1 is the previous instruction. Should be a push of the
	   argument of strlen */
	i1 = &InstructionTable[idxInstruction-1];
	if (i1->Flags & (CHANGED|DELETED)) return 0;
	/* in is the next instruction after the call. Should be an addl */
	in = &InstructionTable[idxInstruction+1];
	if (idxInstruction > 1)
		ip = &InstructionTable[idxInstruction-2];
	if (i1->Name[0] == 'p'
		&& in->Name[0] == 'a') {
		if (State[EDI] == NULL)
			condition = 0;
		else 
			condition = IsAliveValue(bb,idxInstruction+2,EDI);
		if (!ediIsSaved) condition = 1;
		insDst = GetNextChangedInstruction(i1,bb);
		strcpy(insDst->Name,"movl");
		strcpy(insDst->src,i1->src);
		if (condition) {
			strcpy(insDst->dst,"%edx\n\txchg\t%edx,%edi");
			State[EDX] = Nullst;
		}
		else {
			strcpy(insDst->dst,"%edi");
			State[EDI] = Nullst;
		}
		changedInstruction = GetNextChangedInstruction(insDst,bb);
		insDst->Flags &= ~CHANGED;
		insDst->Flags |= ADDED;
		strcpy(changedInstruction->Name,"\txor\t%eax");
		strcpy(changedInstruction->src,",%eax\n\tstc\n\tsbb\t%ecx,%ecx\n\trepne\n\t");
		strcpy(changedInstruction->dst,"scasb\n\tneg\t%ecx\n\tleal\t-2(%ecx),%eax\n");
		/* This overflows by 1 byte. Since the next field of the
		   instruction is the 'Start' field and it is unused, we can
		   do that... */
		if (condition)
			strcat(changedInstruction->dst,"\tmovl\t%edx,%edi\n");
		else State[EDI] = Nullst;
		State[EAX] = Nullst;

		in->Flags |= DELETED;
		ins->Flags |= DELETED;
		FixCalls(ins,bb,idxInstruction);
		deleted += 2;
		return(2);
	}
	return 0;
}

static int call(void)
{
	int i;

	if (recursion == 0 && !strcmp(savesrc,"_strlen")) {
		i = inlinestrlen();
		if (i)	return i;
	}

	else if (recursion == 0 && idxInstruction > 1 &&
		InstructionTable[idxInstruction-1].Name[0] == 'f' &&
		(!strcmp(savesrc,"_sqrt") || !strcmp(savesrc,"_sin") ||
			!strcmp(savesrc,"_fabs") ||
			!strcmp(savesrc,"_cos"))) {
		Instruction *i1,*i2,*i3;

		i1 = &InstructionTable[idxInstruction-1];
		i2 = &InstructionTable[idxInstruction-2];
		i3 = &InstructionTable[idxInstruction+1];
		if (!strcmp(i1->Name,"fstpl") &&
			!strcmp(i2->Name,"subl") &&
			!strcmp(i3->Name,"addl")) {
			i1->Flags |= DELETED;
			deleted++;
			i2->Flags |= DELETED;
			deleted++;
			if (!strcmp(savesrc,"_sqrt"))
				insDst = ChangeInstruction(ins,bb,"fsqrt","","");
			else
			if (!strcmp(savesrc,"_sin"))
				insDst = ChangeInstruction(ins,bb,"fsin","","");
			else
			if (!strcmp(savesrc,"_cos"))
				insDst = ChangeInstruction(ins,bb,"fcos","","");
			else
			if (!strcmp(savesrc,"_fabs"))
				insDst = ChangeInstruction(ins,bb,"fabs","","");
			i3->Flags |= DELETED;
			deleted++;
			FixCalls(ins,bb,idxInstruction);
			return(2);
		}
	}
#if 0
	else
	if (/*recursion == 0 && ediIsSaved && esiIsSaved &&*/ !strncmp(savesrc,"_strcpy",7)) {
		char *strconstant;
		Instruction *i1,*i2,*in;
		int ix,len;

		ix = idxInstruction-1;
		i1 = &InstructionTable[ix--];
		if (i1->Flags & (CHANGED|DELETED)) goto skip1;
		i2 = &InstructionTable[ix--];
		if (i2->Flags & (CHANGED|DELETED)) goto skip1;
		if (i2->Name[0] == 'l' && !strcmp(i2->Name,"leal")) {
			if ((InstructionTable[ix].Flags & CHANGED) == 0) {
				i2 = &InstructionTable[ix--];
				if (i2->Name[0] == 'i' && !strcmp(i2->Name,"imul")) {
					i2 = &InstructionTable[ix--];
				}
				else if ((i2->Flags & ISMOVL) && (i2->Flags & CHANGED)==0)
					i2 = &InstructionTable[ix--];
			}
		}
		in = &InstructionTable[idxInstruction+1];
		if (!(i1->Name[0] == 'p' && i2->Name[0] == 'p'))
			goto skip1;
		if (!(i2->src[0] == '$' && i2->src[1] == '_' && i2->src[2] == '$'))
			goto skip1;
		strconstant = FindStringConstant(i2->src+3);
		len = strlen(strconstant)+1;
		ChangeInstruction(i2,bb,"movl",i2->src,"%esi");

		insDst = ChangeInstruction(i1,bb,"movl",i1->src,"%edi");

		sprintf(tbuf,"$%d",len);
		insDst = ChangeInstruction(ins,bb,"movl",tbuf,"%ecx");
		changedInstruction = GetNextChangedInstruction(insDst,bb);
		insDst->Flags &= ~CHANGED;
		insDst->Flags |= ADDED;
		strcpy(changedInstruction->Name,"\trep\n");
		changedInstruction->src[0] = changedInstruction->dst[0] = 0;

		if (in->Name[0] == 'a') {
			insDst = ChangeInstruction(in,bb,"movsb","","");
		}
		else strcpy(changedInstruction->src,"movsb\n");

		FixCalls(ins,bb,idxInstruction);
		printf("Optimization strcpy\n");
		return 2;
	}
#endif
	else
	if (hasRegisterVariables == 0 &&
		recursion == 0 && !strcmp(savesrc,"_memcpy")) {
		Instruction *i1,*i2,*i3,*in,*ip;
		int lab,saveEsi,saveEdi,ismovsw,ismovsd,isExactBytes;

		ip = NULL;
		i1 = &InstructionTable[idxInstruction-1];
		if (i1->Flags & (CHANGED|DELETED)) goto skip1;
		i2 = &InstructionTable[idxInstruction-2];
		if (i2->Flags & (CHANGED|DELETED)) goto skip1;
		i3 = &InstructionTable[idxInstruction-3];
		if (i3->Flags & (CHANGED|DELETED)) goto skip1;
		if (idxInstruction > 3)
			ip = &InstructionTable[idxInstruction-4];
		in = &InstructionTable[idxInstruction+1];
		if (in->Flags & (CHANGED|DELETED)) goto skip1;
		if (i1->Name[0] == 'p' && 
			i2->Name[0] == 'p' &&
			i3->Name[0] == 'p' &&
			in->Name[0] == 'a' &&
			(!strcmp(in->src,"$12")) &&
			(i1->Flags & CHANGED) == 0 &&
			(i2->Flags & CHANGED) == 0 &&
			(i3->Flags & CHANGED) == 0) {
			insDst = GetNextChangedInstruction(i3,bb);
			lab = 0;
			if (ip && (ip->Flags & CHANGED)== 0 && ip->Flags & ISMOVL &&
				ip->dst[0] == '%' &&
					(!strcmp(i3->src,ip->src)) &&
					(ip->DstReg == ESI || ip->DstReg == EDI)) {
					ip->Flags |= DELETED;
					deleted++;
					strcpy(insDst->Name,"movl");
					strcpy(insDst->src,ip->src);
			}
			else {
				strcpy(insDst->Name,"movl");
				strcpy(insDst->src,i3->src);
			}
			strcpy(insDst->dst,"%ecx");
			State[ECX] = Nullst;
			if (!ediIsSaved ) saveEdi = 1;
			else if (hasRegisterVariables) saveEdi=1;
			else saveEdi = IsAliveValue(bb,idxInstruction+2,EDI);
			if (!esiIsSaved || hasRegisterVariables) saveEsi = 1;
			else saveEsi = IsAliveValue(bb,idxInstruction+2,ESI);
			ismovsd = ismovsw = isExactBytes = 0;
			if (insDst->src[0] == '$' && insDst->src[1] >= '0' &&
				insDst->src[1] <= '9') {
				int t;

				t = atoi(&insDst->src[1]);
				if (t > 0) {
					if (0 == (t % 4)) {
						t /= 4;
						ismovsd = 1;
					}
					else if (0 == (t%2)) {
						t /= 2;
						ismovsw = 1;
					}
					if (ismovsd || ismovsw) {
						if (t == 1) {
							i3->Flags |= DELETED;
							i3->Flags &= ~CHANGED;
							deleted++;
							isExactBytes = 1;
						}
						else sprintf(insDst->src,"$%d",t);
					}
				}
			}
			if (i3->src[0] != '$') {
				changedInstruction = GetNextChangedInstruction(insDst,bb);
				insDst->Flags &= ~CHANGED;
				insDst->Flags |= ADDED;
				lab = genlabel(1);
				sprintf(changedInstruction->Name,"\tjecxz");
				sprintf(changedInstruction->src,"\t_$%d\n",lab);
			}

			insDst = GetNextChangedInstruction(i2,bb);
			strcpy(insDst->Name,"movl");
			strcpy(insDst->src,i2->src);
			if (saveEsi) {
				strcpy(insDst->dst,"%edx\n\txchg\t%edx,%esi");
				State[EDX] = Nullst;
			}
			else {
				strcpy(insDst->dst,"%esi");
				State[ESI] = Nullst;
			}

			insDst = GetNextChangedInstruction(i1,bb);
			strcpy(insDst->Name,"movl");
			strcpy(insDst->src,i1->src);
			if (saveEdi) {
				strcpy(insDst->dst,"%eax\n\txchg\t%eax,%edi");
				State[EAX] = Nullst;
			}
			else {
				strcpy(insDst->dst,"%edi");
				State[EDI] = Nullst;
			}
			if (!isExactBytes) {
				insDst = GetNextChangedInstruction(ins,bb);
				strcpy(insDst->Name,"rep");
				insDst->src[0] = insDst->dst[0] = 0;
			}
			else {
				ins->Flags |= DELETED;
				deleted++;
			}
			FixCalls(ins,bb,idxInstruction);

			insDst = GetNextChangedInstruction(in,bb);
			if (ismovsw) {
				strcpy(insDst->Name,"movsw");
			}
			else if (ismovsd) {
				strcpy(insDst->Name,"movsl");
			}
			else strcpy(insDst->Name,"movsb");
			if (saveEsi) {
				strcat(insDst->Name,"\n");
				strcpy(insDst->src,"mov\t%edx,%esi");
			}
			if (saveEdi) {
				if (!saveEsi) {
					strcat(insDst->Name,"\n");
					strcpy(insDst->src,"movl\t%eax,%edi");
				}
				else strcat(insDst->src,"\n\tmov\t%eax,%edi");
			}
			if (lab) {
				char tlabbuf[30];
				sprintf(tlabbuf,"\n_$%d:",lab);
				strcat(insDst->src,tlabbuf);
			}
			State[ESI] = Nullst;
			return(2);
		}
	}

	else if (!hasRegisterVariables && !strcmp(savesrc,"_memset")) {
		Instruction *i1,*i2,*i3,*in,*ip;
		int ix,isword,isdword,AvoidClobberingEax,AdjustStack;

		ip = NULL;
		isword = isdword = 0;
		ix = idxInstruction-1;
		i1 = &InstructionTable[ix--];
		if (i1->Flags & (CHANGED|DELETED)) goto skip1;
		i2 = &InstructionTable[ix--];
		if (i2->Flags & (CHANGED|DELETED)) goto skip1;
		if (i2->Name[0] == 'l' && !strcmp(i2->Name,"leal")) {
			if ((InstructionTable[ix].Flags & CHANGED) == 0) {
				i2 = &InstructionTable[ix--];
				if (i2->Name[0] == 'i' && !strcmp(i2->Name,"imul")) {
					i2 = &InstructionTable[ix--];
				}
				else if ((i2->Flags & ISMOVL) && (i2->Flags & CHANGED)==0)
					i2 = &InstructionTable[ix--];
			}
		}
		i3 = &InstructionTable[ix--];
		if (i3->Flags & (CHANGED|DELETED)) goto skip1;
		if (ix > 0)
			ip = &InstructionTable[ix--];
		in = &InstructionTable[idxInstruction+1];
		if (!strcmp(i1->src,"%eax"))
			AvoidClobberingEax = 1;
		else
			AvoidClobberingEax = 0;
		if (i1->Name[0] == 'p' && 
			i2->Name[0] == 'p' &&
			i3->Name[0] == 'p' && 
			in->Name[0] == 'a' &&
			(i1->Flags & CHANGED) == 0 && 
			(i2->Flags & CHANGED) == 0 &&
			(i3->Flags & CHANGED) == 0 &&
			(in->Flags & CHANGED) == 0 &&
			!(AvoidClobberingEax && !ediIsSaved)) {
			if (strcmp(in->src,"$12"))
				AdjustStack = atoi(&in->src[1]);
			else
				AdjustStack = 0;
			if (ip && (ip->Flags & ISMOVL) && !strcmp(ip->dst,i3->src)) {
				insDst = GetNextChangedInstruction(ip,bb);
				strcpy(insDst->Name,ip->Name);
				strcpy(insDst->src,ip->src);
				i3->Flags |= DELETED;
				deleted++;
			}
			else {
				insDst = GetNextChangedInstruction(i3,bb);
				strcpy(insDst->Name,"movl");
				if (i3->src[0] == '$' && !strcmp(i2->src,"$0")) {
					int val = ReadValue(&i3->src[1]);
					if (val) {
						if (!(val%4)) {
							val = val/4;
							isdword = 1;
						}
						else if (!(val & 1)) {
							val = val / 2;
							isword = 1;
						}
						sprintf(insDst->src,"$%d",val);
					}
					else
						strcpy(insDst->src,i3->src);
				}
				else {
					strcpy(insDst->src,i3->src);
				}
			}
			strcpy(insDst->dst,"%ecx");
			State[ECX] = Nullst;

			insDst = GetNextChangedInstruction(i2,bb);
			if ((!strcmp(i2->src,"$0")) || (!strcmp(i2->src,"$0x0"))) {
				strcpy(insDst->Name,"xor");
				if (AvoidClobberingEax) {
					strcpy(insDst->src,"%edi");
				}
				else {
					strcpy(insDst->src,"%eax");
				}
			}
			else {
				strcpy(insDst->Name,"movl");
				strcpy(insDst->src,i2->src);
			}
			if (!AvoidClobberingEax) {
				strcpy(insDst->dst,"%eax");
			}
			else {
				strcpy(insDst->dst,"%edi");
			}
			State[EAX] = Nullst;
			if (ediIsSaved == 0 || hasRegisterVariables) {
				changedInstruction = GetNextChangedInstruction(insDst,bb);
				insDst->Flags |= ADDED;
				insDst->Flags &= ~ CHANGED;
				strcpy(changedInstruction->Name,"\tpushl");
				strcpy(changedInstruction->src,"\t%edi\n");
				changedInstruction->dst[0] = 0;
			}

			insDst = GetNextChangedInstruction(i1,bb);
			if (strcmp(i1->src,"%edi")) {
				if (!AvoidClobberingEax) {
					strcpy(insDst->Name,"movl");
					strcpy(insDst->src,i1->src);
					strcpy(insDst->dst,"%edi");
				}
				else {
					strcpy(insDst->Name,"xchg");
					strcpy(insDst->src,"%eax");
					strcpy(insDst->dst,"%edi");
				}
			}
			else {
				i1->Flags |= DELETED;
				deleted++;
			}
			State[EDI] = Nullst;

			insDst = GetNextChangedInstruction(ins,bb);
			strcpy(insDst->Name,"rep");
			FixCalls(ins,bb,idxInstruction);

			insDst = GetNextChangedInstruction(in,bb);
			if (isdword)
				strcpy(insDst->Name,"stosl");
			else if (isword)
				strcpy(insDst->Name,"stosw");
			else strcpy(insDst->Name,"stosb");
			if (ediIsSaved == 0 || hasRegisterVariables) {
				changedInstruction = GetNextChangedInstruction(insDst,bb);
				insDst->Flags |= ADDED;
				insDst->Flags &= ~ CHANGED;
				strcpy(changedInstruction->Name,"\tpopl\t%edi\n");
				if (AdjustStack)
					sprintf(changedInstruction->dst,"\tadd\t$%d,%%esp\n",AdjustStack-12);
				State[EDX] = Nullst;
			}
			if (AdjustStack) {
				if (ediIsSaved) {
					changedInstruction = GetNextChangedInstruction(insDst,bb);
					insDst->Flags |= ADDED;
					insDst->Flags &= ~ CHANGED;
					strcpy(changedInstruction->Name,"\tadd\t");
					sprintf(changedInstruction->src,"$%d,",AdjustStack-12);
					strcpy(changedInstruction->dst,"%esp\n");
				}
			}
			Printf1("Optimization 22\n");
			return(2);
		}
	}
skip1:
	State[EAX] = State[ECX] = State[EDX] = Nullst;
	Printf1("eax = ecx = edx = NULL\n");
	if (State[ESI] && *State[ESI] == '_') State[ESI] = Nullst;
	if (State[EDI] && *State[EDI] == '_') State[EDI] = Nullst;
	if (State[EBX] && *State[EBX] == '_') State[EBX] = Nullst;
	return 0;
}

static int FindStateChanges(void)
{
	unsigned char *srcCopy;
	int result;

	opcode = ins->Name;
	savesrc = src = ins->src;
	dst = ins->dst;
	regdst = regsrc = isImmediate = aReg = 0;
	result = 1;
	assert((ins->Flags & TRUNCATED)==0);
	if (ins->Flags & CHANGED) {
		src = InstructionTable[ins->ChangedIdx].src;
		dst = InstructionTable[ins->ChangedIdx].dst;
	}
	if (ins->Flags & DELETED) return result;
	nextIns = &InstructionTable[idxInstruction+1];
	if (*dst == '%') {
		dst++;
		regdst = 1;
	}
	if (*src == '%') {
		src++;
		regsrc = 1;
	}
	else if (*src == '$')
		isImmediate = 1;
	isRedundant = 0;
	isMovl = (ins->Flags & ISMOVL)?1:0;
	if (dst[0] == '(') {
		/*
		replace
		mov	%esi	(,%edi)
		mov	(,%edi)	%esi
		*/
		if ( isMovl && nextIns->src[0] == '(' && !strcmp(src,nextIns->src)) {
			if (!strcmp(ins->src,nextIns->dst)) {
				nextIns->Flags |= DELETED;
				Printf1("Optimization 37\n");
				deleted++;
				result++;
			}
			else if (regsrc) {
				ChangeInstruction(nextIns,bb,nextIns->Name,ins->src,nextIns->dst);
			}
		}
		return result;
	}
	/*
	replace
	mov %ecx;%esi
	mov %esi,%ecx
	*/
	if (isMovl && regsrc && regdst && 
		ins->SrcReg < EBP &&
		(nextIns->Flags &(CHANGED|DELETED)) == 0 &&
		(nextIns->Flags & ISMOVL) &&
		nextIns->src[0] == '%' && nextIns->dst[0] == '%') {
		if (ins->DstReg == nextIns->SrcReg &&
			ins->SrcReg == nextIns->DstReg) {
			State[ins->DstReg] = Nullst;
			nextIns->Flags |= DELETED;
			deleted++;
			return 2;
		}
	}
	if (regdst && isMovl) {
		if (ins->SrcReg == ins->DstReg) {
			if (regsrc && !strcmp(src,dst)) {
					ins->Flags |= DELETED;
					deleted++;
					return result;
			}
		}
		/*
			Try to catch
				movl -24(%ebp),%edi
				pushl %edi

				and replace by
				push -24(%ebp)
		*/
		if (ins->SrcReg == EBP) {
			if (!hasRegisterVariables &&
				nextIns->Name[0] == 'p' && nextIns->Name[1] == 'u' &&
				(ins->Flags & SRCDEREFERENCE) == 0 &&
				(nextIns->Flags & ISREGSRC) && nextIns->SrcReg == ins->DstReg
				&& !strcmp(nextIns->src,ins->dst)
				&& (nextIns->Flags & SRCDEREFERENCE) == 0) {
				if (!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
					ChangeInstruction(ins,bb,"pushl",ins->src,"");
					nextIns->Flags |= DELETED;
					deleted++;
					Printf1("Optimization 23\n");
					return(result+1);
				}
			}
		}
		if (regsrc && 
			ins->SrcReg == AX	 && ins->DstReg == BX) {
			/* Try to replace
				movl %ax,%bx
				movb %bl,-1(%ebp)
				with
				movl %al,-1(%ebp)
			*/

			if ((nextIns->Flags & ISGENERICMOVE) && !strcmp(nextIns->src,"%bl")) {
				ChangeInstruction(nextIns,bb,nextIns->Name,"%al",nextIns->dst);
				ins->Flags |= DELETED;
				deleted++;
				Printf1("Optimization 24\n");
				return(result +1);
			}
		}
		if (!regsrc && !isImmediate) {
			if (State[EAX] && !strcmp(src,State[EAX])) {
				Printf2("%s was in eax\n",State[EAX]);
				if (ins->DstReg == EAX) {
					ins->Flags |= DELETED;
					deleted++;
				}
				else {
					redundant++;
					isRedundant = EAX;
				}
			}
			if (State[EBX] && !strcmp(src,State[EBX])) {
				Printf2("%s was in ebx\n",State[EBX]);
				if (ins->DstReg == EBX) {
					ins->Flags |= DELETED;
					deleted++;
				}
				else {
					redundant++;
					isRedundant = EBX;
				}
			}
			if (State[ECX] && !strcmp(src,State[ECX])) {
				Printf2("%s was in ecx\n",State[ECX]);
				if (ins->DstReg == ECX) {
					ins->Flags |= DELETED;
					deleted++;
				}
				else {
					redundant++;
					isRedundant = ECX;
				}
			}
			if (State[EDX] && !strcmp(src,State[EDX])) {
				Printf2("%s was in edx\n",State[EDX]);
				if (ins->DstReg == EDX) {
					ins->Flags |= DELETED;
					deleted++;
				}
				else {
					redundant++;
					isRedundant = EDX;
				}
			}
			if (State[ESI] && !strcmp(src,State[ESI])) {
				Printf2("%s was in esi\n",State[ESI]);
				if (ins->DstReg == ESI) {
					ins->Flags |= DELETED;
					deleted++;
				}
				else {
					redundant++;
					isRedundant = ESI;
				}
			}
			if (State[EDI] && !strcmp(src,State[EDI])) {
				Printf2("%s was in edi\n",State[EDI]);
				if (ins->DstReg == EDI) {
					ins->Flags |= DELETED;
					deleted++;
				}
				else {
					redundant++;
					isRedundant = EDI;
				}
			}
			if (isRedundant && /*!hasRegisterVariables &&*/
				src[0] != '$' && (ins->Flags & (CHANGED|DELETED)) == 0) {
				ChangeRedundantLoad(ins,isRedundant,bb,idxInstruction,1/*!hasRegisterVariables*/);
			}
		}
		if (ins->Flags & DELETED)
			return(result);
	}
	if (ins->DstReg > ESP) {
		if (ins->DstReg < SP+1) State[ins->DstReg-ESP] = Nullst;
		else if ((ins->Flags & ISGENERICMOVE) == 0) {
			int r;

			r = ins->DstReg & 0xFF;
			if (r < ESP) {
				State[r] = Nullst;
				Printf2("%s = NULL\n",RegisterNames[r]);
			}
			r = (ins->DstReg >> 8) & 0xFF;
			if (r < ESP) {
				State[r] = Nullst;
				Printf2("%s = NULL\n",RegisterNames[r]);
			}
		}
	}
	if (isMovl && 
		regsrc && 
		regdst && 
//		!hasRegisterVariables &&
		isImmediate == 0 &&
		(ins->Flags&CHANGED) == 0 &&
		ins->SrcReg < EBP &&
		ins->DstReg < EBP) {
		int i = RegToRegCopy();
		if (i) return i;
	}
	/*
	This should have taken into account the fact that after an 
	orl	%eax,%eax
	jne _$label
	%eax is zero. Then any 'xor %eax,%eax' after this can be deleted
	The results are disappointing. 210 bytes gained from 543188...
	*/
	if (isMovl == 0 && regsrc && regdst
		&& ins->SrcReg == ins->DstReg 
		&& opcode[0] == 'o' && opcode[1] == 'r'
		&& (opcode[2] == 0 || opcode[2] == 'l')
		&& ins->SrcReg < EBP) {
		if ((nextIns->Flags & (CHANGED|DELETED)) == 0
			&& !strcmp(nextIns->Name,"jne")) {
			Instruction *tmpins = nextIns;
			nextIns++;
			if ((nextIns->Flags & (CHANGED|DELETED)) == 0) {
				if (nextIns->SrcReg == ins->SrcReg &&
					nextIns->DstReg == ins->SrcReg &&
					nextIns->src[0] == '%' &&
					nextIns->dst[0] == '%' &&
					!strcmp(nextIns->Name,"xor")) {
					nextIns++;
					if (strcmp(nextIns->Name,"jmp")) {
						nextIns--;
						nextIns->Flags |= DELETED;
						deleted++;
						Printf1("Optimization 47\n");
					}
					else {
						// This is ridiculous. Changed from
						// 542968 to 542924: 44 bytes saved only!
						// should be faster though, since a jump is saved
						if (!strncmp(nextIns->End,tmpins->src,strlen(tmpins->src))
							&& ins->SrcReg == EAX) {
							int lab = atoi(nextIns->src+2);
							if (lab == lastLabel) {
								ChangeInstruction(tmpins,bb,"je",nextIns->src,"");
								nextIns--;
								nextIns->Flags |= DELETED;
								deleted++;
								nextIns++;
								nextIns->Flags |= DELETED;
								deleted++;
								return(4);
							}
						}
					}
				}
				else if (nextIns->src[0] == '$' &&
					nextIns->src[1] == '0' &&
					nextIns->src[2] == 0 &&
					(!strcmp(nextIns->Name,"movl") || (nextIns->Flags & ISCOMPARE))) {
					ChangeInstruction(nextIns,bb,nextIns->Name,ins->src,nextIns->dst);
					Printf1("Optimization 47\n");
					return(3);
				}
			}
		}
		return(result);
	}
	if ((isMovl == 0) && (ins->Flags & ISCOMPARE)) {
		return compare();
	}

	if ((ins->Flags & ISGENERICMOVE) == 0) {
		/* delete additions and substractions of zero */
		if ((ins->Flags & (CHANGED|DELETED))==0 &&
			(opcode[0] == 'a' && opcode[1] == 'd' && opcode[2] == 'd') ||
			(opcode[0] == 's' && opcode[1] == 'u' && opcode[2] == 'b')) {
			if (isImmediate && src[1] == '0') {
				if (src[2] == 0 || (src[2] == 'x' && src[3] == '0' && src[4] == 0)) {
					ins->Flags |= DELETED;
					return result;
				}
			}
			lastIns = GetLastInstruction(idxInstruction);
			/*
				Replace
				addl	$-1,reg
				by
				inc		reg
			*/
			if (((ins->Flags & CHANGED) == 0) && isImmediate && src[1] == '-'
				&& src[2] == '1' && src[3] == 0) {
				char *op;
				if (regdst) {
					tbuf[0] = '%';
					strcpy(tbuf+1,dst);
				}
				else strcpy(tbuf,dst);
				if (*opcode == 'a')
					op = "decl";
				else
					op = "incl";
				if (*dst != '%') doclobber(dst,10000);
				ChangeInstruction(ins,bb,op,tbuf,"");
				Printf1("addl/subl->inc/dec\n");
			}
			else
			/*
				Replace postincrement from
					mov mem,reg1	load value
					mov reg1,reg2	save old value in reg2
					inc reg1		add offset
					mov reg1,mem	store updated value

					to

					mov	mem,reg1	load value
					inc reg1		add offset
					xchg reg1,mem	store new value AND reload old
			*/
			if ((ins->Flags & CHANGED) == 0 && recursion == 0 &&
				(ins->Flags & ISREGDST) &&
//				!hasRegisterVariables &&
				isImmediate && idxInstruction >1) {
				if ((lastIns->Flags & ISREGSRC) && (lastIns->Flags & ISREGDST)
					&& (lastIns->Flags & ISMOVL) && 
					lastIns->DstReg == ins->DstReg &&
					!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
					Instruction *tmp;

					tmp = lastIns - 1;
					if (((tmp->Flags & CHANGED)==0) &&
						(tmp->Flags & ISMOVL) && 
						(tmp->Flags & ISREGSRC) == 0 &&
						tmp->DstReg == lastIns->SrcReg) {

						if ((nextIns->Flags & ISREGSRC) && !strcmp(tmp->src,nextIns->dst)) {
							char *srcC;
							if (lastIns->Flags & CHANGED) {
								srcC = InstructionTable[lastIns->ChangedIdx].src;
							}
							else
								srcC = lastIns->src;
							lastIns->Flags |= DELETED;
							deleted++;
							tmp->Flags &= ~DELETED;
							if (opcode[0] == 's') {
								sprintf(tbuf,"$-%s",src+1);
							}
							else strcpy(tbuf,src);
							ChangeInstruction(tmp,bb,"movl",nextIns->dst,srcC);
							insDst = ChangeInstruction(ins,bb,"add",tbuf,nextIns->dst);
							nextIns->Flags |= DELETED;
							deleted++;
							doclobber(insDst->src,10000);
							if (lastIns->SrcReg < ESP)
								State[lastIns->SrcReg] = Nullst;
							Printf3("%s = %s = NULL\n",RegisterNames[lastIns->SrcReg],
								RegisterNames[lastIns->DstReg]);
							Printf1("Optimization 13 (postincrement)\n");
							return(result+1);
						}
					}
					else if ((lastIns->Flags & CHANGED) == 0 && 
						!hasRegisterVariables) {
						unsigned char *minus;

						if (opcode[0] == 's') minus = "-";
						else minus = "";
						sprintf(tbuf,"%s%s(%s)",minus,ins->src+1,lastIns->src);
						ChangeInstruction(ins,bb,"leal",tbuf,ins->dst);
						lastIns->Flags |= DELETED;
						deleted++;
						if (ins->DstReg < ESP)
							State[ins->DstReg] = Nullst;
						Printf1("Optimization 16\n");
						return result;
					}
				}
			}
			if (((ins->Flags & CHANGED) == 0) && isImmediate && src[1] == '1'
				&& src[2] == 0) {
				char *op;
				if (regdst) {
					tbuf[0] = '%';
					strcpy(tbuf+1,dst);
				}
				else strcpy(tbuf,dst);
				if (*opcode == 'a')
					op = "incl";
				else
					op = "decl";
				if (*dst != '%') doclobber(dst,10000);
				ChangeInstruction(ins,bb,op,tbuf,"");
				Printf1("addl/subl->inc/dec\n");
			}
			if (((ins->Flags & CHANGED) == 0) && 
				! hasRegisterVariables &&
				isImmediate && regdst && idxInstruction > 0) {
				if (!strcmp(lastIns->Name,"movl") &&
					lastIns->dst[0] == '%' &&
					lastIns->SrcReg < EBP &&
					!strcmp(lastIns->src,nextIns->dst) &&
					!strcmp(lastIns->dst,ins->dst) &&
					!strcmp(ins->dst,nextIns->src) &&
					!IsAliveValue(bb,idxInstruction+2,ins->DstReg) ) {
					/* replace
					movl _var,%edi
					addl $8,%edi
					movl %edi,_var
					with
					addl $8,_var
					*/
					ChangeInstruction(ins,bb,ins->Name,ins->src,lastIns->src);
					lastIns->Flags |= DELETED;
					State[ins->DstReg] = Nullst;
					nextIns->Flags |= DELETED;
					Printf1("Optimization 42\n");
					deleted += 2;
					return(2);
				}
			}
		}
		if (isImmediate && 
			(ins->Flags & (CHANGED|DELETED)) == 0 &&
			opcode[0] == 't' && opcode[1] == 'e' &&
			opcode[2] == 's' && opcode[3] == 't') {
			int val;
			
			val = CheckValueAlreadyLoaded(ins->dst);
			if (val) {
				sprintf(tbuf,"%%%s",RegisterNames[val]);
				ChangeInstruction(ins,bb,ins->Name,ins->src,tbuf);
				Printf1("Optimization 44.5\n");
				return 1;
			}
			if (opcode[4] == 'l') {
				char * pval = ins->src;
				char *dst = ins->dst;
				char suffix=0;

				if (*pval == '$') pval++;
				if (*pval == '0' && pval[1] == 'x') {
					val = strtoul(pval+2,&pval,16);
				}
				else val = strtoul(pval,&pval,10);
				if (val > 0) {
					if (val < 128) {
						if (regdst && 
							(ins->DstReg == ESI || ins->DstReg == EDI)) {
							if (ins->DstReg == ESI)
								dst = "%si";
							else
								dst = "%di";
							suffix = 'w';
						}
						else {
							suffix = 'b';
							if (regdst) {
								if (ins->DstReg == EAX)
									dst = "%al";
								if (ins->DstReg == EBX)
									dst = "%bl";
								if (ins->DstReg == ECX)
									dst = "%cl";
								if (ins->DstReg == EDX)
									dst = "%dl";
							}
						}
					}
					else if (val < 65535) {
						suffix = 'w';
						if (regdst) {
							if (ins->DstReg == EAX)
								dst = "%ax";
							if (ins->DstReg == EBX)
								dst = "%bx";
							if (ins->DstReg == ECX)
								dst = "%cx";
							if (ins->DstReg == EDX)
								dst = "%dx";
							if (ins->DstReg == ESI)
								dst = "%si";
							if (ins->DstReg == EDI)
								dst = "%di";
						}
					}
					if (suffix) {
						sprintf(tbuf,"test%c",suffix);
						ChangeInstruction(ins,bb,tbuf,ins->src,dst);
						return(result);
					}
				}
			}
		}
		if ((opcode[0] == 'd' && opcode[1] == 'i' && opcode[2] == 'v') ||
			(opcode[0] == 'i' && opcode[1] == 'm' && opcode[2] == 'u') ||
			(opcode[0] == 'i' && opcode[1] == 'd' && opcode[2] == 'i') ||
			(opcode[0] == 'm' && opcode[1] == 'u' && opcode[2] == 'l')) {
			Printf1("div/mul: eax = edx = NULL\n");
			State[EAX] = State[EDX] = Nullst;
		}
		/*
		Try to replace a sequence of instructions like
		xor		%eax,%eax
		movl	%eax,memory1
		xor		%eax,%eax
		movl	%eax,memory2
		with
		xor		%eax,%eax
		movl	%eax,memory1
		movl	%eax,memory2
		*/
		if ((ins->Flags & CHANGED) == 0 &&
			opcode[0] == 'x' && opcode[1] == 'o' && opcode[2] == 'r') {
			if (ins->SrcReg == ins->DstReg && ins->SrcReg == EAX) {
				Instruction *ins1,*ins2;
				int idx = idxInstruction+1;

				for ( ; ;) {
					if (idx >= bb->NrOfInstructions) break;
					ins1 = &InstructionTable[idx];
					ins2 = &InstructionTable[idx+1];
					if (ins1->Flags & CHANGED) break;
					if (ins2->Flags & CHANGED) break;
					if ((ins1->Flags & ISGENERICMOVE) &&
						ins1->SrcReg == EAX &&
						ins1->src[0] == '%' &&
						ins2->Name[0] == 'x' && ins2->Name[1] == 'o' &&
						ins2->SrcReg == ins2->DstReg &&
						ins2->SrcReg == EAX &&
						ins2->src[0] == '%' && ins2->dst[0] == '%' &&
						ins2->src[2] == 'a' && ins2->dst[2] == 'a') {
						ins2->Flags |= DELETED;
						deleted++;
						Printf1("Optimization 31\n");
					}
					else if (
						(ins1->Flags & ISGENERICMOVE) &&
						ins1->SrcReg == EAX &&
						ins1->src[0] == '%' &&
						(ins2->Flags & ISGENERICMOVE) &&
						(!strcmp(ins2->src,"$0") || !strcmp(ins2->src,"$0x0")) &&
						(!strcmp(ins2->Name,"movl") || !strcmp(ins2->Name,"movw"))) {
						if (ins2->Name[3] == 'l')
							strcpy(tbuf,"%eax");
						else
							strcpy(tbuf,"%ax");
						ChangeInstruction(ins2,bb,ins2->Name,tbuf,ins2->dst);
						Printf1("Optimization 32\n");
						idx += 2;
						continue;
					}
					else break;
					idx += 2;
				}
			}
		}
		if ((opcode[0] == 'i' && opcode[1] == 'n' && opcode[2] == 'c') ||
			(opcode[0] == 'd' && opcode[1] == 'e' && opcode[2] == 'c')) {
				doclobber(savesrc,10000);
		}
		/* all arithmetic instructions are discarded */
		if (regsrc) {
			if (ins->SrcReg < ESP && State[ins->SrcReg]) {
				doclobber(State[ins->SrcReg],10000);
				State[ins->SrcReg] = Nullst;
			}
		}
		if (regdst) {
			if (ins->DstReg < ESP && State[ins->DstReg]) {
				doclobber(State[ins->DstReg],10000);
				State[ins->DstReg] = Nullst;
			}
		}
		doclobber(ins->dst,10000);
		if (opcode[0] == 'f') {
			if (opcode[1] == 's' && opcode[2] == 't'
				&& opcode[3] == 's') {
				State[EAX] = Nullst;
			}
			if (!strcmp(opcode,"fstpl")) {
				if (!strcmp(nextIns->Name,"fldl") &&
					!strcmp(nextIns->src,ins->src)) {
					nextIns->Flags |= DELETED;
					deleted++;
					ChangeInstruction(ins,bb,"fstl",ins->src,"");
					return(2);
				}
			}
		}
		src = Nullst;
	}
	old = Nullst;
	if ((isMovl == 0) && !strcmp("rep",opcode)) {
		Instruction *loadEcxIns;
		int i;

		Printf1("rep movsb: esi = edi = ecx = NULL\n");
		State[ESI] = State[EDI] = State[ECX] = Nullst;
		if (idxInstruction > 0 && nextIns->Name[4] == 'b' && nextIns->Name[0] == 'm') {
			i = idxInstruction-1;
			loadEcxIns = &InstructionTable[i];
			while (i >= 0) {
				if (loadEcxIns->DstReg == ECX) {
					if (loadEcxIns->src[0] == '$') break;
					else return result;
				}
				i--;
				loadEcxIns--;
			}
			/*
				replace in the block move instructions the
				movsb construct by movsw (100% faster) or the
				movsd (400% faster).
			*/
			if (i > 1) {
				int quantity;

				quantity = atoi(loadEcxIns->src + 1);
				if (quantity > 0) {
					char tbuf[10];
					int changed = 0;

					if (0 == (quantity % 4)) {
						quantity = quantity/4;
						changed = 'l';
					}
					else if (0 == (quantity % 2)) {
						quantity = quantity/2;
						changed = 'w';
					}
					if (changed) {
						sprintf(tbuf,"$%d",quantity);
						ChangeInstruction(loadEcxIns,bb,loadEcxIns->Name,tbuf,loadEcxIns->dst);

						sprintf(tbuf,"movs%c",changed);
						ChangeInstruction(nextIns,bb,tbuf,"","");
						Printf1("movsb->movsd\n");
					}
				}
			}
		}
		return result;
	}
	if (opcode[0] == 'm' && opcode[1] == 'o' && opcode[2] == 'v'
		&& opcode[3] == 's' && opcode[5] == 0 
		&& (opcode[4] == 'l' || opcode[4] == 'w' || opcode[4] == 'b')) {
		Printf1("rep movsb: esi = edi = ecx = NULL\n");
		State[ESI] = State[EDI] = State[ECX] = Nullst;
	}
	/*
	Test if the source of a push instruction is already in a register
	*/
	if ((ins->Flags & CHANGED) == 0 && !isImmediate &&
		!regsrc && opcode[0] == 'p' && opcode[1] == 'u'
		&& opcode[2] == 's') {
		int ir;
		for (ir = EAX; ir<EBP;ir++) {
			if (State[ir] &&
			  State[ir][0] != '%' &&
			 !strcmp(ins->src,State[ir])) {
				char tmpbuf[10];

				sprintf(tmpbuf,"%%%s",RegisterNames[ir]);
				ChangeInstruction(ins,bb,opcode,tmpbuf,"");
				Printf1("Optimization 37\n");
				return(result);
			}
		}
	}
	if (regdst) {
		if (ins->Flags & SRCDEREFERENCE) src = Nullst;
		else if ((ins->Flags & SRCOFFSET) && ins->SrcReg != EBP){
				src = Nullst;
		}
		else if (!isMovl) src = Nullst;
		aReg = ins->DstReg;
		if (aReg < EBP && aReg > 0) {
			old = State[aReg];
			if ((ins->Flags & CHANGED) == 0 &&
				old && 
				old != Nullst &&
				ins->SrcReg < ESP &&
//				! hasRegisterVariables &&
				(isMovl || (!strcmp(ins->Name,"movsbl") || !strcmp(ins->Name,"movswl")))) {
				if (isUsedInBlock(1+idxInstruction,old,bb,aReg)) {
					int r = AvoidClobber(RegisterNames[aReg],idxInstruction,bb);

					if (r) {
						Printf2("avoiding clobbering of %s\n",RegisterNames[aReg]);
						aReg = r;
						old = Nullst;
					}
					else ins->Flags |= CLOBBERS;
				}
				else ins->Flags |= CLOBBERS;
			}
			else ins->Flags |= CLOBBERS;
			if (regsrc) src = Nullst;
			State[aReg] = src;
			Printf3("%s = %s\n",RegisterNames[aReg],src);
			bb->Registers[aReg] = 1;
			if (ins->Flags & CHANGED) return(result);
		}
		if (((ins->Flags & CHANGED) == 0) && isMovl && isImmediate) {
			if (savesrc[1] == '0' && savesrc[2] == 0) {
				/*
				Replace
					movl $0,%eax
				with
					xor %eax,%eax
				*/
				ChangeInstruction(ins,bb,"xor",ins->dst,ins->dst);
				Printf1("xor added\n");
				if (ins->DstReg < ESP) State[ins->DstReg] = "$0";
				return(result);
			}
			if (savesrc[1] == '1' && savesrc[2] == 0) {
				changedInstruction = ChangeInstruction(ins,bb,"xor",ins->dst,ins->dst);
				changedInstruction->Flags &= ~CHANGED;
				changedInstruction->Flags |= ADDED;
				changedInstruction = GetNextChangedInstruction(changedInstruction,bb);
				sprintf(tbuf,"\tinc\t%s\n",ins->dst);
				strcpy(changedInstruction->Name,tbuf);
				if (ins->DstReg < ESP) State[ins->DstReg] = "$1";
				return(result);
			}

		}
		if (regsrc && ins->DstReg == EAX && idxInstruction > 2
			&& idxInstruction >= bb->NrOfInstructions-2
			&& isMovl 
			&& !hasRegisterVariables 
			&& ((InstructionTable[idxInstruction+1].Name[0] == 'j') ||
				(idxInstruction == bb->NrOfInstructions-1))) {
			lastIns = GetLastInstruction(idxInstruction);

			if (lastIns &&
				(lastIns->Flags & ISMOVL)  
				&& lastIns->DstReg == ins->SrcReg
				&& lastIns->DstReg < ESP
				&& ins->SrcReg < ESP
				&& lastIns->dst[0] == '%') {
				lastIns->Flags |= DELETED;
				if (lastIns->Flags & CHANGED) {
					changedInstruction = &InstructionTable[lastIns->ChangedIdx];
					srcCopy = changedInstruction->src;
					lastIns->Flags &= ~CHANGED;
				}
				else {
					srcCopy = lastIns->src;
				}
				deleted++;
				ChangeInstruction(ins,bb,opcode,srcCopy,ins->dst);
				Printf1("Redundant move\n");
			}
		}
		/* replace
			mov %edi %esi
			mov %esi -4(%ebp)
			with
			mov %edi, -4(%ebp)
			P.S. This is not worth the effort: 517476 to 517456
			*/
		if (regsrc && 
			!hasRegisterVariables &&
			isMovl && 
			idxInstruction < (bb->NrOfInstructions-1)
			&& aReg < EBP && ins->SrcReg < EBP
			&& (ins->Flags & CHANGED)==0) {

			if ((nextIns->Flags & ISMOVL) && (nextIns->Flags & CHANGED)==0
				&& (ins->DstReg == EDI || ins->DstReg == ESI)
				&& (nextIns->Flags & ISREGSRC) && nextIns->SrcReg == ins->DstReg
				/*&& (nextIns->Flags & ISREGDST) == 0*/ && (nextIns->SrcReg != nextIns->DstReg)
				&& (nextIns->DstReg < ESP)) {
				if (!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
					ins->Flags |= DELETED;
					ChangeInstruction(nextIns,bb,nextIns->Name,ins->src,nextIns->dst);
					deleted++;
					Printf1("Optimization 28\n");
					return(result);
				}
			}
		}
		/* replace
			mov -4(%ebp),%esi
			mov %esi %edi
			with
			mov  -4(%ebp),%edi
			*/
		if (regsrc && 
			!hasRegisterVariables &&
			isMovl && 
			idxInstruction > 0
			&& aReg < EBP && ins->SrcReg < EBP
			&& (ins->Flags & CHANGED)==0) {
			lastIns = &InstructionTable[idxInstruction-1];

			if ((lastIns->Flags & ISMOVL) && (lastIns->Flags & (CHANGED|DELETED))==0
				&& (ins->SrcReg == EDI || ins->SrcReg == ESI)
				&& (lastIns->Flags & ISREGDST) && lastIns->DstReg == ins->SrcReg
				&& (lastIns->Flags & ISREGSRC) == 0 && (lastIns->SrcReg != lastIns->DstReg)
				&& (lastIns->DstReg < ESP)) {
				if (!IsAliveValue(bb,idxInstruction+1,ins->SrcReg)) {
					ins->Flags |= DELETED;
					ChangeInstruction(lastIns,bb,lastIns->Name,lastIns->src,ins->dst);
					deleted++;
					State[lastIns->DstReg] = Nullst;
					Printf1("Optimization 29\n");
					return(result);
				}
			}
		}
		if ((ins->Flags & CHANGED) == 0 && 
			regdst && 
			!hasRegisterVariables &&
			regsrc && isMovl && aReg == EDI && ins->SrcReg == EAX) {
			int notAlive;
			/*
			replace
			movl	%eax,%edi
			or		%edi,%edi
			with
			or	%eax,%eax
			*/
			notAlive = !IsAliveValue(bb,idxInstruction+2,EDI);
			if (nextIns->Flags & CHANGED) notAlive = 0;
			if ((notAlive) &&
				(!strcmp(nextIns->src,nextIns->dst)) &&
				(!strcmp(nextIns->src,"%edi")) &&
				(nextIns->Name[0] == 'o' && nextIns->Name[1] == 'r')) {
				ins->Flags |= DELETED;
				ChangeInstruction(nextIns,bb,nextIns->Name,"%eax","%eax");
				ins->Flags |= DELETED;
				deleted++;
				Printf1("Optimization 33\n");
				return(result+1);
			}
			/*
			replace
			movl	%eax,%edi
			movl	%edi,memory reference
			*/
			else
				if ((notAlive) && !hasRegisterVariables &&
					(nextIns->Flags & ISMOVL) &&
					(nextIns->SrcReg == EDI) &&
					(nextIns->src[0] == '%')) {
					ChangeInstruction(nextIns,bb,nextIns->Name,"%eax",nextIns->dst);
					ins->Flags |= DELETED;
					deleted++;
					State[EAX] = nextIns->dst;
					Printf1("Optimization 34\n");
				}

			else {
				/*
				Change
				mov		%eax,%edi
				push	%edi
				with
				push	%eax
				*/
				if ( (notAlive) && (ins->Flags & ISMOVL) && 
					!hasRegisterVariables &&
					(nextIns->Name[0] == 'p' && nextIns->Name[1] == 'u') &&
					(!strcmp(nextIns->src,"%edi"))) {
					ChangeInstruction(nextIns,bb,nextIns->Name,"%eax","");
					ins->Flags |= DELETED;
					deleted++;
					Printf1("Optimization 35\n");
					return 2;
				}
				else if (hasRegisterVariables == 0 &&
					idxInstruction == (bb->NrOfInstructions-1)) {
					ins->Flags |= DELETED;
					deleted++;
					Printf1("Optimization 36\n");
					return(1);
				}
			}
		}
	}
	doclobber(old,aReg);
	old = Nullst;
	aReg = 10000;
	/*
	When storing into a register change the state accordingly. This provokes that
	only the LAST alias is saved. For instance:

		mov	-4(%ebp),%esi
		mov %esi,-20(%ebp)

	This will leave in State only '-20(%ebp)' at the ESI position, even if the
	reference to '-4(%ebp)' is still valid. The problem is that maintaining a
	state with aliases becomes hairy: any stores at a similar address will be
	difficult to catch.
	For instance:
		leal -4(%ebp),%edi
		pushl %edi
		call  _somefunction

	Now the value in edi could be wrong. This is why I do not store into the
	State any leal moves. In 99% of the cases this is too strong, and many
	optimizations that are possible are just not done because of this. The
	problem is that a compiler that generates good code in 99% of the cases
	is just buggy!
	*/
	if (ins->Flags & ISLEAL) {
		doclobber(ins->src,10000);
		if (ins->SrcReg < ESP) {
			State[EAX] = Nullst;
			State[EBX] = Nullst;
			State[ECX] = Nullst;
			State[EDX] = Nullst;
			State[ESI] = Nullst;
			State[EDI] = Nullst;
		}
		src = Nullst;
		/* try to change
			lea (%esi,%edi),%edi
			movl %edi,%eax

			into

			lea (%esi,%edi),%eax
		*/
		if ((nextIns->Flags & CHANGED) == 0 && 
			!hasRegisterVariables &&
			(ins->Flags & CHANGED) == 0 &&
			nextIns->SrcReg == ins->DstReg && (nextIns->Flags & ISMOVL) &&
			(nextIns->Flags & ISREGSRC) && (nextIns->Flags & ISREGDST)) {
			if (!IsAliveValue(bb,idxInstruction+2,ins->DstReg)) {
				ChangeInstruction(ins,bb,opcode,ins->src,nextIns->dst);
				nextIns->Flags |= DELETED;
				deleted++;
				Printf1("Optimization 27\n");
				return(result+1);
			}
		}
		return result;
	}
	if (regsrc && isMovl && (ins->Flags & (DSTDEREFERENCE)) == 0) {
		aReg = ins->SrcReg;
		if (aReg > 0 && aReg < EBP) {
			char *d = dst;
			old = State[aReg];
			if (ins->Flags & DSTOFFSET && ins->DstReg != EBP) {
				d = Nullst;
			}
			else d = dst;
			State[aReg] = d;
			Printf3("%s = %s\n",RegisterNames[aReg],d);
			bb->Registers[aReg] = 1;
		}
	}
	/*
		Try to catch sequences like
		    movl        %esi,   116(%edi)
    		movl   116(%edi),        %esi
	*/
	if (isMovl && regsrc && (regdst == 0)) {
		int flags;

		flags = nextIns->Flags;
		if ((flags & CHANGED)==0 &&(flags & ISMOVL) && !strcmp(nextIns->src,dst)) {
			if (nextIns->dst[0] == '%' && nextIns->DstReg == ins->SrcReg) {
				nextIns->Flags |= DELETED;
				deleted++;
				Printf1("Cross redundant load\n");
			}
		}

	}
	if ((nextIns->Flags & (DELETED|CHANGED)) == 0 &&
		(ins->Flags & (DELETED|CHANGED)) == 0 &&
		ins->Name[0] == 'm' &&
		ins->Name[1] == 'o' &&
		!strcmp(nextIns->Name,ins->Name) &&
		!strcmp(nextIns->src,ins->dst) &&
		!strcmp(nextIns->dst,ins->src)) {
		nextIns->Flags |= DELETED;
		deleted++;
		Printf1("Cross redundant load\n");
	}
	if (aReg != 10000 || old != Nullst)
		doclobber(old,aReg);
	if (aReg != 10000) doclobber(dst,aReg);
	/*
	If a memory location has been written to with an immediate, this invalidates
	any caching to that location in the State table.
	*/
	if (isImmediate && !regdst && ins->Name[0] == 'm' && ins->Name[1] == 'o' &&
		ins->Name[2] == 'v') {
		doclobber(dst,10000);
	}
	if (ins->Flags & ISCALL) {
		int i;
		i = call();
		if (i) return i;
	}
	return(result);
}
#ifndef ANALYZER
static int TransformJump(Instruction *fjump,Instruction *sjump,BasicBlock *bb)
{
	unsigned char *j = fjump->Name;
	unsigned char *newj = NULL;
	Instruction *insDst;

	j++;
	if (j[0] == 'g' && j[1] == 'e') {
		newj = "jl";
	}
	else if (j[0] == 'l') {
		if (j[1] == 'e')
			newj = "jg";
		else
			newj = "jge";
	}
	else if (j[0] == 'n' && j[1] == 'e')
		newj = "je";
	else if (j[0] == 'e')
		newj = "jne";
	else if (j[0] == 'g')
		newj = "jle";
	if (newj == NULL) {
		Printf2("Jump %s not found\n",fjump->Name);
		return(0);
	}
	insDst = GetNextChangedInstruction(fjump,bb);
	strcpy(insDst->Name,newj);
	strcpy(insDst->src,sjump->src);
	sjump->Flags |= DELETED;
	deleted++;
	return(1);
}
#endif
static int OptimizeBlock(void)
{
	Instruction *insDst;
	int i,f,last,nCalls;

	if (bb->NrOfInstructions == 0) return 0;
	Printf3("Block %s %d instructions\n",bb->Label,bb->NrOfInstructions);
	memset(State,0,sizeof(State));
	ins = InstructionTable;
	idxInstruction = last = 0;
	while (idxInstruction < bb->NrOfInstructions) {
		f = 1;
		if (ins->Name[0] != 'j') {
			int oldDeletedCount = deleted;
			f = FindStateChanges();
			bb->deleted += (deleted - oldDeletedCount);
		}
		idxInstruction += f;
		ins += f;
	}
	/*
		Try to replace a sequence of calls like:
			push	_var1
			push	_var2
			call	_someproc
			add		$8,%esp
			push	_var34
			push	_var36
			call	_someotherproc
			add		$8,%esp
			Eliminate all the additions to %esp and consolidate them in one
			addition at the end of the block. Rules:
			No intervening jumps (conditional or unconditional) should
			intervene, since that would leave the stack in a mess...
	*/
	if ((hasAllocA == 0) &&
		bb->FirstCall < bb->LastCall &&
		bb->LastCall != bb->NrOfInstructions) {
		for (i=bb->FirstCall; i<=bb->LastCall;i++) {
			if (InstructionTable[i].Flags & ISCALL) {
				char *Name = InstructionTable[i+1].Name;
				char *dst = InstructionTable[i+1].dst;
				if (Name[0] == 'a' &&
					Name[1] == 'd' &&
					dst[2] == 's' &&
					dst[3] == 'p') {
					InstructionTable[i].Flags |= STACKADJUST;
				}
			}
		}
		ins = &InstructionTable[bb->FirstCall];
		f = 0;
		nCalls = 0;
		last = bb->FirstCall;
		for (i=bb->FirstCall;i <=bb->LastCall;i++) {
			if (ins->Flags & ISJUMP) {
				ins = &InstructionTable[last+1];
				break;
			}
			else if (ins->Flags & STACKADJUST) {
				if (i == bb->NrOfInstructions-1) {
					f = 1;
					break;
				}
				ins++;
				if (strcmp("addl",ins->Name) || (ins->Flags & CHANGED)) {
					f = 1;
					break;
				}
				else ins--;
				last = i;
				nCalls++;
			}
			ins++;
		}
		if (f == 0 && nCalls > 1) {
			char tbuf[6];
			Instruction *modify = ins;
			ins = &InstructionTable[bb->FirstCall];
			f = 0;
			for (i=bb->FirstCall;i <=last;i++) {
				if (ins->Flags & STACKADJUST) {
					ins++;
					if (strcmp("addl",ins->Name)) {
						Printf1("Bailout\n");
						goto bailout;
					}
					f += atoi(&ins->src[1]);
					if (i != last) {
						ins->Flags |= DELETED;
						deleted++;
					}
				}
				else ins++;
			}
			modify = &InstructionTable[last+1];
			insDst = GetNextChangedInstruction(modify,bb);
			strcpy(insDst->Name,modify->Name);
			sprintf(tbuf,"$%d",f);
			strcpy(insDst->src,tbuf);
			strcpy(insDst->dst,modify->dst);
			Printf1("xxx\n");
		}
	}
	else if (bb->FirstCall && bb->FirstCall == bb->LastCall) {
		/* Replace
			add	$4,%esp	0x83c404 3 bytes
			with
			pop ecx 0x59 1 byte
		*/
		ins = &InstructionTable[bb->LastCall+1];
		if (ins->Name[0] == 'a' && ins->src[0] == '$' 
			&& ins->src[1] == '4' &&
			!strcmp(ins->dst,"%esp") &&
			ins->src[2] == 0) {
			insDst = GetNextChangedInstruction(ins,bb);
			strcpy(insDst->Name,"pop");
			strcpy(insDst->src,"%ecx");
			Printf1("pop ecx\n");

		}
	}
bailout:

#ifdef DEBUGOPTIM
	i = 0;
	ins = InstructionTable;
	while (i < bb->NrOfInstructions) {
		int donewline;

		donewline = 1;
		if (ins->src[0] && ins->dst[0])
			Printf("[%2d]%8s%12s,%12s",
				i+1,ins->Name,ins->src,ins->dst);
		else if (ins->src[0]) {
			Printf("[%2d]%8s%12s",
				i+1,ins->Name,ins->src);
		}
		else {
			Printf("[%2d]%8s",
				i+1,ins->Name);
		}
		if (ins->Flags & ISLOCAL) {
			Printf(" local");
		}
		if (ins->Flags & ISARGUMENT) {
			Printf(" argument");
		}
		if (ins->Flags & DELETED)
			Printf(" deleted");
		if (ins->Flags & CHANGED) {
			Instruction *insChanged;
			insChanged = &InstructionTable[ins->ChangedIdx];
			Printf(" %8s%12s,%12s",insChanged->Name,insChanged->src,insChanged->dst);
			if (insChanged->Flags & ADDED) {
				insChanged = &InstructionTable[insChanged->ChangedIdx];
				Printf("\n%s%s%s",insChanged->Name,insChanged->src,insChanged->dst);
				donewline = 0;
			}
		}
		if (donewline) Printf("\n");
		i++;
		ins++;
	}
	Printf("Regs used: ");
	if (bb->Registers[EAX]) Printf("eax ");
	if (bb->Registers[EBX]) Printf("ebx ");
	if (bb->Registers[ECX]) Printf("ecx ");
	if (bb->Registers[EDX]) Printf("edx ");
	if (bb->Registers[EDI]) Printf("edi ");
	if (bb->Registers[ESI]) Printf("esi ");
	if (bb->Flags & ISCALL) Printf("First call %d, last %d",1+bb->FirstCall,1+bb->LastCall);
	if (last) printf(" last to adjust: %d",last+1);
	Printf("\n\n");
#endif
	return(1);
}
int FindEbpOffset(char *ins)
{
	int c,r;
	char *p = ins;
	if (*p == '-') p++;
	while (*p >= '0' && *p <= '9')
		p++;
	if (*p != '(') return(0);
	c = *p;
	if (p[1] != '%') return(0);
	*p = 0;
	r = atoi(ins);
	*p = c;
	return(r);
}
/*
This function tries to eliminate last dead stores from a block that ends with an
inconditional jmp to the last function label. This is not very much worth the effort:
295574 to 295478
*/
static int CheckLastJump(BasicBlock *bb)
{
	Instruction *ins;
	char *p;
	int labelNr,nrIns,TableOffsets[11],usedOffsets,offset;

	nrIns = bb->NrOfInstructions;
	if (nrIns <= 2 || hasRegisterVariables) return(2);
	nrIns--;
	ins = &InstructionTable[nrIns];
	if (ins->Flags & (CHANGED|DELETED)) return(0);
	p = ins->Name;
	if (p[0] == 'j' && p[1] == 'm' && p[2] == 'p') {
		p = ins->src;
		/* Test if the jump goes to the next instruction */
		if (!strncmp(p,ins->End,strlen(p))) {
			ins->Flags |= DELETED;
			deleted++;
			return 2;
		}
		labelNr = atoi(p+2);
		lastIns = &InstructionTable[nrIns-1];
		if (labelNr == lastLabel) {
			ins--;
			nrIns--;
			if (ins->Flags & (CHANGED|DELETED)) return(0);
			p = ins->Name;
			if (!strcmp(p,"movl")) {
				if (ins->dst[0] == '%' && strcmp(ins->dst,"%eax")) {
					ins->Flags |= DELETED;
//					printf("%s %s %s\n",ins->Name,ins->src,ins->dst);
					Printf1("Optimization 45\n");
					return(1);
				}
			}
			usedOffsets = 0;
			while (nrIns > 0) {
				if (ins->Flags & (CHANGED|DELETED)) return(0);
				if (ins->Flags & (ISCALL|ISJUMP|ISFLOAT)) break;
				if (ins->SrcReg == EBP) {
					if (usedOffsets > 10) break;
					offset = FindEbpOffset(ins->src);
					if (offset == 0) break;
					TableOffsets[usedOffsets++] = offset;
				}
				if (ins->DstReg == EBP) {
					int i;

					offset = FindEbpOffset(ins->dst);
					if (offset == 0) break;
					for (i=0; i<usedOffsets;i++) {
						if (TableOffsets[i] == offset)
							return(2);
					}
					ins->Flags |= DELETED;
//					printf("%s %s %s\n",ins->Name,ins->src,ins->dst);
					Printf1("Optimization 46\n");
					return(2);
				}
				nrIns--;
				ins--;
			}
		}
	}
	return(2);
}
static int ChangeOutput(BasicBlock *bb,unsigned char *blockEnd,
				int origlen,unsigned char **pnew,unsigned char *start)
{
	int i,len,l;
	Instruction *ins,*insChanged;
	unsigned char *p,*q,*newbuffer;

	if (bb->NrOfInstructions == 0) return 0;
	ins = InstructionTable;
	len = 3*origlen;
	newbuffer = malloc(len);
	memset(newbuffer,0,len);
	p = newbuffer;
	len = ins->Start - start;
	memcpy(p,start,len);
	p += len;
	i = 0;
	q = ins->Start;
	while (i < bb->NrOfInstructions) {
		if ((ins->Flags & (DELETED|CHANGED))==0) {
			l = ins->End - ins->Start;
			memcpy(p,ins->Start,l);
			p += l;
			q = ins->End;
		}
		else if ((ins->Flags & CHANGED) && (0==(ins->Flags&DELETED))) {
			*p++ = '\t';
			insChanged = &InstructionTable[ins->ChangedIdx];
			q = insChanged->Name;
			while (*q) {
				*p++ = *q++;
			}
			q = insChanged->src;
			if (*q) *p++ = '\t';
			while (*q) {
				*p++ = *q++;
			}
			if (insChanged->dst[0]) {
				q = insChanged->dst;
				*p++ = ',';
				while (*q) {
					*p++ = *q++;
				}
			}
			*p++ = '\n';
			if (insChanged->Flags & ADDED) {
				insChanged = &InstructionTable[insChanged->ChangedIdx];
				q = insChanged->Name;
				while (*q) {
					*p++ = *q++;
				}
				q = insChanged->src;
				while (*q) {
					*p++ = *q++;
				}
				q = insChanged->dst;
				while (*q) {
					*p++ = *q++;
				}
			}
			q = ins->End;
		}
		else if (ins->Flags & DELETED) {
			q = ins->End;
		}
		if (q < blockEnd) {
			while (*q == '\t' && q[1] == '.') {
				while (*q && *q != '\n') {
					*p++ = *q++;
				}
				if (*q == '\n') *p++ = *q++;
			}
			ins++;
			i++;
		}
		else break;
	}
	if (q < blockEnd) {
		l = blockEnd - q;
		memcpy(p,q,l);
		p += l;
	}
	len = p - newbuffer;
	*pnew = newbuffer;
	return(len);
}
#ifdef STANDALONE
/* for the STANDALONE program */
int ScanAsm(unsigned char *buffer,int len,unsigned char **poutput)
{
	BasicBlock block;
	unsigned char *bp,*q,*p,*stop,*newbuffer,*pnewbuffer,*output,*oldbp;
	int i,TotalInstructions,newlen,oldDeleted;
	long t = time(NULL);

	hasRegisterVariables = vmask[0];
	bp = buffer;
	stop = buffer+len;
	TotalInstructions = 0;
	*stop = 0;
	output = malloc(3*len);
	pnewbuffer = output;
	while (bp && bp<stop) {
restart:
		oldDeleted = deleted;
		memset(&block,0,sizeof(BasicBlock));
		InstructionIndex = 0;
		oldbp = bp;
		bp = FindBasicBlock(bp,&block,stop);
		memset(&InstructionTable[InstructionIndex],0,sizeof(Instruction));
		block.ChangedCounter = (unsigned short)InstructionIndex+1;
		TotalInstructions += block.NrOfInstructions;
		bb = &block;
		OptimizeBlock();
		if (bp) {
			newlen = ChangeOutput(&block,bp,bp-oldbp,&newbuffer,oldbp);
			memcpy(pnewbuffer,newbuffer,newlen);
			pnewbuffer += newlen;
		}
		else break;
		if (oldDeleted != deleted && bp) {
			char *nbp;
			memset(&block,0,sizeof(BasicBlock));
			InstructionIndex = 0;
			nbp = FindBasicBlock(pnewbuffer-newlen,&block,pnewbuffer);
			memset(&InstructionTable[InstructionIndex],0,sizeof(Instruction));
			block.ChangedCounter = (unsigned short)InstructionIndex+1;
			bb = &block;
			OptimizeBlock();
		}
	}
	*poutput = output;
	Printf3(" %d instructions in time %d\n",TotalInstructions,time(NULL)-t);
	return(pnewbuffer - output);
}
#else
/*
Here is the interface with the rest of lcc
*/
extern int vmask[];
int ChangeBlock(unsigned char *buffer,int len)
{
	BasicBlock block;
	unsigned char *stop,*newbuffer;
	int l,oldDeleted,lastCheck=0;

	if (len == 0) return 0;
	lastLabel = GetLastFunctionLabel();
	recursion = 0;
	hasRegisterVariables = vmask[0];
//	if (hasRegisterVariables) return len;
restart:
	oldDeleted = deleted;
	stop = buffer + len;
	*stop = 0;
	memset(&block,0,sizeof(BasicBlock));
	InstructionIndex = 0;
	FindEndBlock(buffer,&block,stop);
	if (block.NrOfInstructions == 0) return(len);
	memset(&InstructionTable[InstructionIndex],0,sizeof(Instruction));
	block.ChangedCounter = (unsigned short) InstructionIndex+1;
	bb = &block;
	if (!OptimizeBlock())
		return(len);
	if (lastCheck < 2)
		lastCheck = CheckLastJump(&block);
	l = ChangeOutput(&block,buffer+len,len,&newbuffer,buffer);
	memcpy(buffer,newbuffer,l);
	if (len > l) {
		memset(&buffer[l],0,len-l);
	}
	free(newbuffer);
	if (oldDeleted != deleted || (block.ChangedCounter != InstructionIndex+1)) {
		len = l;
		recursion++;
		goto restart;
	}
	return(l);
}
#endif // STANDALONE
