diff options
| -rw-r--r-- | generic/tclOptimize.c | 287 |
1 files changed, 287 insertions, 0 deletions
diff --git a/generic/tclOptimize.c b/generic/tclOptimize.c new file mode 100644 index 0000000..18dc208 --- /dev/null +++ b/generic/tclOptimize.c @@ -0,0 +1,287 @@ +/* + * tclOptimize.c -- + * + * This file contains the bytecode optimizer. + * + * Copyright (c) 2013 by Donal Fellows. + * + * See the file "license.terms" for information on usage and redistribution of + * this file, and for a DISCLAIMER OF ALL WARRANTIES. + */ + +#include "tclInt.h" +#include "tclCompile.h" +#include <assert.h> + +#define DefineTargetAddress(tablePtr, address) \ + ((void) Tcl_CreateHashEntry((tablePtr), (void *) (address), &isNew)) +#define IsTargetAddress(tablePtr, address) \ + (Tcl_FindHashEntry((tablePtr), (void *) (address)) != NULL) + +static void +LocateTargetAddresses( + CompileEnv *envPtr, + Tcl_HashTable *tablePtr) +{ + unsigned char *pc, *target; + int size, isNew, i; + Tcl_HashEntry *hPtr; + Tcl_HashSearch hSearch; + + Tcl_InitHashTable(tablePtr, TCL_ONE_WORD_KEYS); + + /* + * The starts of commands represent target addresses. + */ + + for (i=0 ; i<envPtr->numCommands ; i++) { + DefineTargetAddress(tablePtr, + envPtr->codeStart + envPtr->cmdMapPtr[i].codeOffset); + } + + /* + * Find places where we should be careful about replacing instructions + * because they are the targets of various types of jumps. + */ + + for (pc = envPtr->codeStart ; pc < envPtr->codeNext ; pc += size) { + size = tclInstructionTable[*pc].numBytes; + switch (*pc) { + case INST_JUMP1: + case INST_JUMP_TRUE1: + case INST_JUMP_FALSE1: + target = pc + TclGetInt1AtPtr(pc+1); + goto storeTarget; + case INST_JUMP4: + case INST_JUMP_TRUE4: + case INST_JUMP_FALSE4: + target = pc + TclGetInt4AtPtr(pc+1); + goto storeTarget; + case INST_BEGIN_CATCH4: + target = envPtr->codeStart + envPtr->exceptArrayPtr[ + TclGetUInt4AtPtr(pc+1)].codeOffset; + storeTarget: + DefineTargetAddress(tablePtr, target); + break; + case INST_JUMP_TABLE: + hPtr = Tcl_FirstHashEntry( + &JUMPTABLEINFO(envPtr, pc+1)->hashTable, &hSearch); + for (; hPtr ; hPtr = Tcl_NextHashEntry(&hSearch)) { + target = pc + PTR2INT(Tcl_GetHashValue(hPtr)); + DefineTargetAddress(tablePtr, target); + } + break; + case INST_RETURN_CODE_BRANCH: + for (i=TCL_ERROR ; i<TCL_CONTINUE+1 ; i++) { + DefineTargetAddress(tablePtr, pc + 2*i - 1); + } + break; + case INST_START_CMD: + assert (envPtr->atCmdStart < 2); + } + } + + /* + * Add a marker *after* the last bytecode instruction. WARNING: points to + * one past the end! + */ + + DefineTargetAddress(tablePtr, pc); + + /* + * Enter in the targets of exception ranges. + */ + + for (i=0 ; i<envPtr->exceptArrayNext ; i++) { + ExceptionRange *rangePtr = &envPtr->exceptArrayPtr[i]; + + if (rangePtr->type == CATCH_EXCEPTION_RANGE) { + target = envPtr->codeStart + rangePtr->catchOffset; + DefineTargetAddress(tablePtr, target); + } else { + target = envPtr->codeStart + rangePtr->breakOffset; + DefineTargetAddress(tablePtr, target); + if (rangePtr->continueOffset >= 0) { + target = envPtr->codeStart + rangePtr->continueOffset; + DefineTargetAddress(tablePtr, target); + } + } + } +} + +/* + * ---------------------------------------------------------------------- + * + * TclOptimizeBytecode -- + * + * A very simple peephole optimizer for bytecode. + * + * ---------------------------------------------------------------------- + */ + +void +TclOptimizeBytecode( + CompileEnv *envPtr) +{ + unsigned char *pc; + int size; + Tcl_HashTable targets; + + /* + * Replace PUSH/POP sequences (when non-hazardous) with NOPs. Also replace + * PUSH empty/CONCAT and TRY_CVT_NUMERIC (when followed by an operation + * that guarantees the check for arithmeticity) and eliminate LNOT when we + * can invert the following JUMP condition. + */ + + LocateTargetAddresses(envPtr, &targets); + for (pc = envPtr->codeStart ; pc < envPtr->codeNext ; pc += size) { + int blank = 0, i, inst; + + size = tclInstructionTable[*pc].numBytes; + while (*(pc+size) == INST_NOP) { + if (IsTargetAddress(&targets, pc + size)) { + break; + } + size += tclInstructionTable[INST_NOP].numBytes; + } + if (IsTargetAddress(&targets, pc + size)) { + continue; + } + inst = *(pc + size); + switch (*pc) { + case INST_PUSH1: + if (inst == INST_POP) { + blank = size + tclInstructionTable[inst].numBytes; + } else if (inst == INST_CONCAT1 + && TclGetUInt1AtPtr(pc + size + 1) == 2) { + Tcl_Obj *litPtr = TclFetchLiteral(envPtr, + TclGetUInt1AtPtr(pc + 1)); + int numBytes; + + (void) Tcl_GetStringFromObj(litPtr, &numBytes); + if (numBytes == 0) { + blank = size + tclInstructionTable[inst].numBytes; + } + } + break; + case INST_PUSH4: + if (inst == INST_POP) { + blank = size + 1; + } else if (inst == INST_CONCAT1 + && TclGetUInt1AtPtr(pc + size + 1) == 2) { + Tcl_Obj *litPtr = TclFetchLiteral(envPtr, + TclGetUInt4AtPtr(pc + 1)); + int numBytes; + + (void) Tcl_GetStringFromObj(litPtr, &numBytes); + if (numBytes == 0) { + blank = size + tclInstructionTable[inst].numBytes; + } + } + break; + case INST_LNOT: + switch (inst) { + case INST_JUMP_TRUE1: + blank = size; + *(pc + size) = INST_JUMP_FALSE1; + break; + case INST_JUMP_FALSE1: + blank = size; + *(pc + size) = INST_JUMP_TRUE1; + break; + case INST_JUMP_TRUE4: + blank = size; + *(pc + size) = INST_JUMP_FALSE4; + break; + case INST_JUMP_FALSE4: + blank = size; + *(pc + size) = INST_JUMP_TRUE4; + break; + } + break; + case INST_TRY_CVT_TO_NUMERIC: + switch (inst) { + case INST_JUMP_TRUE1: + case INST_JUMP_TRUE4: + case INST_JUMP_FALSE1: + case INST_JUMP_FALSE4: + case INST_INCR_SCALAR1: + case INST_INCR_ARRAY1: + case INST_INCR_ARRAY_STK: + case INST_INCR_SCALAR_STK: + case INST_INCR_STK: + case INST_LOR: + case INST_LAND: + case INST_EQ: + case INST_NEQ: + case INST_LT: + case INST_LE: + case INST_GT: + case INST_GE: + case INST_MOD: + case INST_LSHIFT: + case INST_RSHIFT: + case INST_BITOR: + case INST_BITXOR: + case INST_BITAND: + case INST_EXPON: + case INST_ADD: + case INST_SUB: + case INST_DIV: + case INST_MULT: + case INST_LNOT: + case INST_BITNOT: + case INST_UMINUS: + case INST_UPLUS: + case INST_TRY_CVT_TO_NUMERIC: + blank = size; + break; + } + break; + } + if (blank > 0) { + for (i=0 ; i<blank ; i++) { + *(pc + i) = INST_NOP; + } + size = blank; + } + } + Tcl_DeleteHashTable(&targets); + + /* + * Trim unreachable instructions after a DONE. + */ + + LocateTargetAddresses(envPtr, &targets); + for (pc = envPtr->codeStart ; pc < envPtr->codeNext-1 ; pc += size) { + int clear = 0; + + size = tclInstructionTable[*pc].numBytes; + if (*pc != INST_DONE) { + continue; + } + assert (size == 1); + while (!IsTargetAddress(&targets, pc + 1 + clear)) { + clear += tclInstructionTable[*(pc + 1 + clear)].numBytes; + } + if (pc + 1 + clear == envPtr->codeNext) { + envPtr->codeNext -= clear; + } else { + while (clear --> 0) { + *(pc + 1 + clear) = INST_NOP; + } + } + } + + Tcl_DeleteHashTable(&targets); +} + +/* + * Local Variables: + * mode: c + * c-basic-offset: 4 + * fill-column: 78 + * tab-width: 8 + * End: + */ |