/*
* Copyright 1989 by Rayan S. Zachariassen, all rights reserved.
* This will be free software, but only when it is finished.
*/
/*
* This is an almost-standalone optimizer for the Shell pseudo-code.
* It usually improves execution time and code space by 20-40%.
*/
#include "hostenv.h"
#include <stdio.h>
#include <sys/stat.h>
#include "listutils.h"
#include "sh.h"
#include "shconfig.h"
#include "libsh.h"
#ifdef DEBUG
#define ASSERT_INRANGE(val,low,high) ({if (val < low || val > high) abort();})
#else
#define ASSERT_INRANGE(val,low,high)
#endif
#define LNEXT(x) (*((x)+1) & 0xFF)
#define LNEXTl(x) *((x)+1)
#define NEXT(x) (OutputTokens)LNEXT(x)
#define LNEXTNEXT(x) (*((x)+2) & 0xFF)
#define LNEXTNEXTl(x) *((x)+2)
#define NEXTNEXT(x) (OutputTokens)LNEXTNEXT(x)
/* NEXTNEXT only makes sense if nargs of NEXT(pc) is 0 */
#define LNEXTNEXTNEXT(x) (*((x)+3) & 0xFF)
#define LNEXTNEXTNEXTl(x) *((x)+3)
#define NEXTNEXTNEXT(x) (OutputTokens)LNEXTNEXTNEXT(x)
/* NEXTNEXTNEXT only makes sense if (as above) */
#define CODE(x) (OutputTokens)(code[(x)] & 0xFF)
#define JUMPADDRESS(x) ((code[(x)+1] & 0xFF) << 24 | \
(code[(x)+2] & 0xFF) << 16 | \
(code[(x)+3] & 0xFF) << 8 | \
(code[(x)+4] & 0xFF))
/*
* Shell pseudo-code optimizer.
*/
void *
optimize(print, Vcode, eocodep)
int print;
void *Vcode, **eocodep;
{
char *code = Vcode;
char *arg1, *bitmap;
char *pc, *spc;
char *eocode = (char*) *eocodep;
char *npc, *nspc, *ncode;
int *addrmap;
int coderange = (eocode - code)+1;
int cmd, argi1, i, j, k, scopetop = -1, commandtop = -1, quotenext;
short scope[MAXNSCOPES], command[MAXNCOMMANDS];
char *scopeaddr[MAXNSCOPES], *commandaddr[MAXNCOMMANDS];
quotenext = 0;
/* The ncode[] array may REPLACE the code[] array, thus it
MUST be malloc()ed buffer.. */
ncode = (char *)malloc(coderange);
if (ncode == NULL) {
fprintf(stderr, "%s: can't malloc %d bytes\n",
progname, (int)((char *)*eocodep - code));
return code;
}
#ifdef USE_ALLOCA
if ((addrmap = (int *)alloca((coderange) * sizeof(int))) == NULL ||
(bitmap = (char *)alloca((coderange)/8+1)) == NULL) {
fprintf(stderr, "%s: can't alloca %d bytes\n",
progname, (int)((char *)*eocodep - code));
return code;
}
memset(bitmap, 0, (coderange)/8+1);
#else /* Not USE_ALLOCA */
if ((addrmap = (int *)malloc((coderange) * sizeof(int))) == NULL ||
(bitmap = (char *)calloc((coderange)/8+1, 1)) == NULL) {
fprintf(stderr, "%s: can't malloc %d bytes\n",
progname, coderange);
if (addrmap) free(addrmap);
if (bitmap) free(bitmap);
/* If those previous ones succeeded, it was ncode that
failed.. no need to test and free it.. */
return code;
}
#endif
/* shut up compilers */
arg1 = NULL; spc = NULL; argi1 = 0;
again:
for (pc = code, npc = ncode; pc < eocode; ++pc) {
if ((*pc & 0xFF) >= ncommands) {
fprintf(stderr, "%s: unknown opcode %d at %d\n",
progname, (*pc & 0xFF), (int)(pc - code));
fprintf(stderr, "%s: previous opcode was %d\n",
progname, *(pc-1) & 0xFF);
break;
}
cmd = (*pc) & 0xFF;
if (print)
printf("%d:\t%s", (int)(pc-code), TOKEN_NAME(cmd));
spc = pc;
switch (TOKEN_NARGS(cmd)) {
case 1:
arg1 = (char *)++pc;
while (*pc != '\0')
++pc;
if (print)
printf("(%s)", arg1);
break;
case -1:
argi1 = (*++pc) & 0xFF;
argi1 <<= 8;
argi1 |= (*++pc) & 0xFF;
argi1 <<= 8;
argi1 |= (*++pc) & 0xFF;
argi1 <<= 8;
argi1 |= (*++pc) & 0xFF;
if (argi1 < 0 || argi1 > coderange-1)
printf("argi1 @%d outside coderange! %d (%d..%d)\n",
(int)(pc-code),argi1,0,coderange-1);
if (print)
printf("(%d)", argi1);
break;
}
nspc = npc;
ASSERT_INRANGE(spc-code,0,coderange-1);
addrmap[spc-code] = npc-ncode;
while (spc <= pc)
*npc++ = *spc++;
if (print) {
putchar('\n');
continue;
}
if (commandtop >= 0)
++command[commandtop];
switch ((OutputTokens)cmd) {
case sBufferSet:
if (quotenext == 0 && *arg1 == '\0') {
if (NEXT(pc) == sBufferAppend) {
npc = nspc;
LNEXTl(pc) = sBufferSet;
} else if (NEXT(pc) == sBufferSet) {
npc = nspc;
} else if ((NEXT(pc) == sDollarExpand
|| NEXT(pc) == sBufferQuote)
&& NEXTNEXT(pc) == sBufferAppend) {
npc = nspc;
LNEXTNEXTl(pc) = sBufferSet;
} else if (NEXT(pc) == sDollarExpand
&& NEXTNEXT(pc) == sBufferQuote
&& NEXTNEXTNEXT(pc) == sBufferAppend) {
npc = nspc;
LNEXTNEXTNEXTl(pc) = sBufferSet;
}
} else if (NEXT(pc) == sVariablePop
|| NEXT(pc) == sBufferSet
|| (NEXT(pc) == sIOsetOut
&& NEXTNEXT(pc) == sBufferSet))
npc = nspc;
break;
case sBufferQuote:
quotenext = 1;
continue;
case sBufferAppend:
case sBufferExpand:
case sBufferSetFromArgV:
case sArgVpush:
case sArgList:
case sVariableCdr:
case sVariablePush:
case sVariablePop:
case sVariableBuffer:
case sVariableAppend:
case sVariableLoopAttach:
break;
case sCommandPush:
if (NEXT(pc) == sCommandPop) {
npc = nspc; /* skip the CommandPush */
++pc; /* skip the CommandPop */
} else {
if (commandtop >= 0)
--command[commandtop];
command[++commandtop] = 0;
commandaddr[commandtop] = nspc;
}
break;
case sCommandPop:
--command[commandtop];
if (command[commandtop] == 0) {
/* this command push/pop pair is superfluous */
*commandaddr[commandtop] = (u_char)sNoOp;
npc = nspc; /* superfluous commandPop */
}
--commandtop;
break;
case sCommandCarryBuffer:
case sIOopen:
case sIOopenString:
case sIOopenPortal:
case sIOintoBuffer:
case sIOclose:
case sIOdup:
break;
case sIOsetIn:
case sIOsetInOut:
case sIOsetOut:
case sIOsetAppend:
if (NEXT(pc) == sIOdup)
npc = nspc; /* skip the sIOset{In,Out} */
break;
case sIOsetDesc:
case sAssign:
case sAssignTemporary:
break;
case sFunction:
case sJump:
while (CODE(argi1) == sJump)
argi1 = JUMPADDRESS(argi1);
if (argi1 == pc-code+1)
npc = nspc; /* superfluous Jump */
else {
*(npc-1) = argi1 & 0xff;
*(npc-2) = (argi1 >> 8) & 0xff;
*(npc-3) = (argi1 >> 16) & 0xff;
*(npc-4) = (argi1 >> 24) & 0xff;
}
if (npc != nspc /* jump wasn't superfluous */
&& NEXT(pc) == sJump) {
/* superfluous jump because it is cascaded */
ASSERT_INRANGE(pc-code+1,0,coderange-1);
addrmap[pc-code+1] = npc-ncode;
pc += 5; /* skip next Jump command */
}
if (npc != nspc) {
if (argi1 < pc-code) {
ASSERT_INRANGE(argi1,0,coderange-1);
i = addrmap[argi1];
} else {
ASSERT_INRANGE(npc-4-ncode,0,coderange-1);
i = -argi1, BITSET(bitmap,npc-4-ncode);
}
*(npc-1) = i & 0xff;
*(npc-2) = (i >> 8) & 0xff;
*(npc-3) = (i >> 16) & 0xff;
*(npc-4) = (i >> 24) & 0xff;
}
break;
case sBranchOrigin:
fprintf(stderr, "%s: unpatched branch at %d\n",
progname, (int)(pc-code));
break;
case sJumpFork:
while (CODE(argi1) == sJump)
argi1 = JUMPADDRESS(argi1);
if (argi1 < pc-code) {
ASSERT_INRANGE(argi1,0,coderange-1);
i = addrmap[argi1];
} else {
ASSERT_INRANGE(npc-4-ncode,0,coderange-1);
i = -argi1, BITSET(bitmap,npc-4-ncode);
}
*(npc-1) = i & 0xff;
*(npc-2) = (i >> 8) & 0xff;
*(npc-3) = (i >>16) & 0xff;
*(npc-4) = (i >>24) & 0xff;
break;
case sJumpIfFailure:
while (argi1 < (eocode - code)
&& (CODE(argi1) == sJump
|| CODE(argi1) == sJumpIfFailure)) {
argi1 = JUMPADDRESS(argi1);
}
if (argi1 < pc-code) {
ASSERT_INRANGE(argi1,0,coderange-1);
i = addrmap[argi1];
} else {
ASSERT_INRANGE(npc-4-ncode,0,coderange-1);
i = -argi1;
BITSET(bitmap, npc-4-ncode);
}
*(npc-1) = i & 0xff;
*(npc-2) = (i >> 8) & 0xff;
*(npc-3) = (i >> 16) & 0xff;
*(npc-4) = (i >> 24) & 0xff;
break;
#ifdef MAILER
case sSiftPush:
case sSiftBody:
case sSiftCompileRegexp:
case sSiftReevaluate:
case sSiftPop:
case sSiftBufferAppend:
case sTSiftPush:
case sTSiftBody:
case sTSiftCompileRegexp:
case sTSiftReevaluate:
case sTSiftPop:
/* case sTSiftBufferAppend: */
break;
case sJumpIfRegmatch:
case sTJumpIfRegmatch:
#endif /* MAILER */
case sJumpIfSuccess:
case sJumpIfNilVariable:
case sJumpIfFindVarNil:
case sJumpIfOrValueNil:
case sJumpLoopBreak:
case sJumpLoopContinue:
if (argi1 < pc-code) {
ASSERT_INRANGE(argi1,0,coderange-1);
i = addrmap[argi1];
} else {
ASSERT_INRANGE(npc-4-ncode,0,coderange-1);
i = -argi1, BITSET(bitmap,npc-4-ncode);
}
*(npc-1) = i & 0xff;
*(npc-2) = (i >> 8) & 0xff;
*(npc-3) = (i >> 16) & 0xff;
*(npc-4) = (i >> 24) & 0xff;
break;
case sJumpIfMatch:
while (CODE(argi1) == sJumpIfMatch
|| CODE(argi1) == sJump)
argi1 = JUMPADDRESS(argi1);
if (argi1 < pc-code) {
ASSERT_INRANGE(argi1,0,coderange-1);
i = addrmap[argi1];
} else {
ASSERT_INRANGE(npc-4-ncode,0,coderange-1);
i = -argi1, BITSET(bitmap,npc-4-ncode);
}
*(npc-1) = i & 0xff;
*(npc-2) = (i >> 8) & 0xff;
*(npc-3) = (i >> 16) & 0xff;
*(npc-4) = (i >> 24) & 0xff;
break;
case sLocalVariable:
--command[commandtop];
/* FALL THROUGH */
case sParameter:
scope[scopetop] = 1;
break;
case sScopePush:
scope[++scopetop] = 0;
scopeaddr[scopetop] = nspc;
if (commandtop >= 0)
--command[commandtop];
break;
case sScopePop:
if (scope[scopetop] == 0
/*
* WARNING!!! the following optimization is on
* the assumption that two ScopePop's in a row
* will only occur for local variables in a
* function, which is usually a benign assumption.
* IT MAY BECOME THE SOURCE OF STRANGE BEHAVIOUR!
*/
|| NEXT(pc) == sScopePop) {
/* this scope push/pop pair is superfluous */
*scopeaddr[scopetop] = (u_char)sNoOp;
npc = nspc; /* superfluous scopePop */
}
--scopetop;
if (commandtop >= 0)
--command[commandtop];
case sDollarExpand:
case sPrintAndExit:
case sLoopEnter:
case sLoopExit:
case sBackground:
break;
case sNoOp:
npc = nspc; /* superfluous command */
if (commandtop >= 0)
--command[commandtop];
break;
default:
break;
}
quotenext = 0;
}
if (print)
goto done;
ASSERT_INRANGE(spc-code,0,coderange-1);
addrmap[spc-code] = npc-ncode; /* in case we jump to after eocode */
for (i = 0; i <= npc-ncode; i += 8) { /* yes, the <= is on purpose */
ASSERT_INRANGE(i,0,coderange-1);
if (bitmap[i/8]) {
for (j = 0; j < 8; ++j) {
if (BITTEST(bitmap,i+j)) {
k = ncode[i+j ] & 0xFF;
k <<= 8;
k |= ncode[i+j+1] & 0xFF;
k <<= 8;
k |= ncode[i+j+2] & 0xFF;
k <<= 8;
k |= ncode[i+j+3] & 0xFF;
ASSERT_INRANGE(-k,0,coderange-1);
k = addrmap[-k];
ncode[i+j ] = (k >>24) & 0xff;
ncode[i+j+1] = (k >>16) & 0xff;
ncode[i+j+2] = (k >> 8) & 0xff;
ncode[i+j+3] = k & 0xff;
}
}
bitmap[i/8] = 0; /* so we can reuse the bitmap */
}
}
if (npc-ncode < pc-code) {
*eocodep = eocode = ncode + (npc-ncode);
spc = ncode;
ncode = code;
code = spc;
goto again;
}
done:
#ifndef USE_ALLOCA
free((char *)addrmap);
free(bitmap);
#endif
free(ncode);
return code;
}
syntax highlighted by Code2HTML, v. 0.9.1