From 7759a4f4afa6448af2ba2495a40816b70683748d Mon Sep 17 00:00:00 2001 From: dkf Date: Wed, 5 Jun 2013 23:05:58 +0000 Subject: Added optimizing of jump-to-nop and jump-to-jump cases. Ta to AK for suggesting. --- generic/tclOptimize.c | 209 ++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 152 insertions(+), 57 deletions(-) diff --git a/generic/tclOptimize.c b/generic/tclOptimize.c index 18dc208..3e0d351 100644 --- a/generic/tclOptimize.c +++ b/generic/tclOptimize.c @@ -13,18 +13,45 @@ #include "tclCompile.h" #include +/* + * Forward declarations. + */ + +static void LocateTargetAddresses(CompileEnv *envPtr, + Tcl_HashTable *tablePtr); + +/* + * Helper macros. + */ + #define DefineTargetAddress(tablePtr, address) \ ((void) Tcl_CreateHashEntry((tablePtr), (void *) (address), &isNew)) #define IsTargetAddress(tablePtr, address) \ (Tcl_FindHashEntry((tablePtr), (void *) (address)) != NULL) +#define AddrLength(address) \ + (tclInstructionTable[*(unsigned char *)(address)].numBytes) +#define InstLength(instruction) \ + (tclInstructionTable[(unsigned char)(instruction)].numBytes) +/* + * ---------------------------------------------------------------------- + * + * LocateTargetAddresses -- + * + * Populate a hash table with places that we need to be careful around + * because they're the targets of various kinds of jumps and other + * non-local behavior. + * + * ---------------------------------------------------------------------- + */ + static void LocateTargetAddresses( CompileEnv *envPtr, Tcl_HashTable *tablePtr) { - unsigned char *pc, *target; - int size, isNew, i; + unsigned char *currentInstPtr, *targetInstPtr; + int isNew, i; Tcl_HashEntry *hPtr; Tcl_HashSearch hSearch; @@ -44,36 +71,39 @@ LocateTargetAddresses( * 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) { + for (currentInstPtr = envPtr->codeStart ; + currentInstPtr < envPtr->codeNext ; + currentInstPtr += AddrLength(currentInstPtr)) { + switch (*currentInstPtr) { case INST_JUMP1: case INST_JUMP_TRUE1: case INST_JUMP_FALSE1: - target = pc + TclGetInt1AtPtr(pc+1); + targetInstPtr = currentInstPtr+TclGetInt1AtPtr(currentInstPtr+1); goto storeTarget; case INST_JUMP4: case INST_JUMP_TRUE4: case INST_JUMP_FALSE4: - target = pc + TclGetInt4AtPtr(pc+1); + targetInstPtr = currentInstPtr+TclGetInt4AtPtr(currentInstPtr+1); goto storeTarget; case INST_BEGIN_CATCH4: - target = envPtr->codeStart + envPtr->exceptArrayPtr[ - TclGetUInt4AtPtr(pc+1)].codeOffset; + targetInstPtr = envPtr->codeStart + envPtr->exceptArrayPtr[ + TclGetUInt4AtPtr(currentInstPtr+1)].codeOffset; storeTarget: - DefineTargetAddress(tablePtr, target); + DefineTargetAddress(tablePtr, targetInstPtr); break; case INST_JUMP_TABLE: hPtr = Tcl_FirstHashEntry( - &JUMPTABLEINFO(envPtr, pc+1)->hashTable, &hSearch); + &JUMPTABLEINFO(envPtr, currentInstPtr+1)->hashTable, + &hSearch); for (; hPtr ; hPtr = Tcl_NextHashEntry(&hSearch)) { - target = pc + PTR2INT(Tcl_GetHashValue(hPtr)); - DefineTargetAddress(tablePtr, target); + targetInstPtr = currentInstPtr + + PTR2INT(Tcl_GetHashValue(hPtr)); + DefineTargetAddress(tablePtr, targetInstPtr); } break; case INST_RETURN_CODE_BRANCH: for (i=TCL_ERROR ; iexceptArrayPtr[i]; if (rangePtr->type == CATCH_EXCEPTION_RANGE) { - target = envPtr->codeStart + rangePtr->catchOffset; - DefineTargetAddress(tablePtr, target); + targetInstPtr = envPtr->codeStart + rangePtr->catchOffset; + DefineTargetAddress(tablePtr, targetInstPtr); } else { - target = envPtr->codeStart + rangePtr->breakOffset; - DefineTargetAddress(tablePtr, target); + targetInstPtr = envPtr->codeStart + rangePtr->breakOffset; + DefineTargetAddress(tablePtr, targetInstPtr); if (rangePtr->continueOffset >= 0) { - target = envPtr->codeStart + rangePtr->continueOffset; - DefineTargetAddress(tablePtr, target); + targetInstPtr = envPtr->codeStart + rangePtr->continueOffset; + DefineTargetAddress(tablePtr, targetInstPtr); } } } @@ -123,7 +153,7 @@ void TclOptimizeBytecode( CompileEnv *envPtr) { - unsigned char *pc; + unsigned char *currentInstPtr; int size; Tcl_HashTable targets; @@ -135,73 +165,74 @@ TclOptimizeBytecode( */ LocateTargetAddresses(envPtr, &targets); - for (pc = envPtr->codeStart ; pc < envPtr->codeNext ; pc += size) { - int blank = 0, i, inst; + for (currentInstPtr = envPtr->codeStart ; + currentInstPtr < envPtr->codeNext ; currentInstPtr += size) { + int blank = 0, i, nextInst; - size = tclInstructionTable[*pc].numBytes; - while (*(pc+size) == INST_NOP) { - if (IsTargetAddress(&targets, pc + size)) { + size = AddrLength(currentInstPtr); + while (*(currentInstPtr+size) == INST_NOP) { + if (IsTargetAddress(&targets, currentInstPtr + size)) { break; } - size += tclInstructionTable[INST_NOP].numBytes; + size += InstLength(INST_NOP); } - if (IsTargetAddress(&targets, pc + size)) { + if (IsTargetAddress(&targets, currentInstPtr + size)) { continue; } - inst = *(pc + size); - switch (*pc) { + nextInst = *(currentInstPtr + size); + switch (*currentInstPtr) { case INST_PUSH1: - if (inst == INST_POP) { - blank = size + tclInstructionTable[inst].numBytes; - } else if (inst == INST_CONCAT1 - && TclGetUInt1AtPtr(pc + size + 1) == 2) { + if (nextInst == INST_POP) { + blank = size + InstLength(nextInst); + } else if (nextInst == INST_CONCAT1 + && TclGetUInt1AtPtr(currentInstPtr + size + 1) == 2) { Tcl_Obj *litPtr = TclFetchLiteral(envPtr, - TclGetUInt1AtPtr(pc + 1)); + TclGetUInt1AtPtr(currentInstPtr + 1)); int numBytes; (void) Tcl_GetStringFromObj(litPtr, &numBytes); if (numBytes == 0) { - blank = size + tclInstructionTable[inst].numBytes; + blank = size + InstLength(nextInst); } } break; case INST_PUSH4: - if (inst == INST_POP) { + if (nextInst == INST_POP) { blank = size + 1; - } else if (inst == INST_CONCAT1 - && TclGetUInt1AtPtr(pc + size + 1) == 2) { + } else if (nextInst == INST_CONCAT1 + && TclGetUInt1AtPtr(currentInstPtr + size + 1) == 2) { Tcl_Obj *litPtr = TclFetchLiteral(envPtr, - TclGetUInt4AtPtr(pc + 1)); + TclGetUInt4AtPtr(currentInstPtr + 1)); int numBytes; (void) Tcl_GetStringFromObj(litPtr, &numBytes); if (numBytes == 0) { - blank = size + tclInstructionTable[inst].numBytes; + blank = size + InstLength(nextInst); } } break; case INST_LNOT: - switch (inst) { + switch (nextInst) { case INST_JUMP_TRUE1: blank = size; - *(pc + size) = INST_JUMP_FALSE1; + *(currentInstPtr + size) = INST_JUMP_FALSE1; break; case INST_JUMP_FALSE1: blank = size; - *(pc + size) = INST_JUMP_TRUE1; + *(currentInstPtr + size) = INST_JUMP_TRUE1; break; case INST_JUMP_TRUE4: blank = size; - *(pc + size) = INST_JUMP_FALSE4; + *(currentInstPtr + size) = INST_JUMP_FALSE4; break; case INST_JUMP_FALSE4: blank = size; - *(pc + size) = INST_JUMP_TRUE4; + *(currentInstPtr + size) = INST_JUMP_TRUE4; break; } break; case INST_TRY_CVT_TO_NUMERIC: - switch (inst) { + switch (nextInst) { case INST_JUMP_TRUE1: case INST_JUMP_TRUE4: case INST_JUMP_FALSE1: @@ -242,7 +273,7 @@ TclOptimizeBytecode( } if (blank > 0) { for (i=0 ; icodeStart ; + currentInstPtr < envPtr->codeNext-1 ; + currentInstPtr += AddrLength(currentInstPtr)) { + int offset, delta; + + switch (*currentInstPtr) { + case INST_JUMP1: + case INST_JUMP_TRUE1: + case INST_JUMP_FALSE1: + offset = TclGetInt1AtPtr(currentInstPtr + 1); + delta = 0; + advanceNext1: + if (offset + delta == 0) { + continue; + } + if (offset + delta < -128 || offset + delta > 127) { + TclStoreInt1AtPtr(offset, currentInstPtr + 1); + continue; + } + offset += delta; + switch (*(currentInstPtr + offset)) { + case INST_NOP: + delta = InstLength(INST_NOP); + goto advanceNext1; + case INST_JUMP1: + delta = TclGetInt1AtPtr(currentInstPtr + offset + 1); + goto advanceNext1; + case INST_JUMP4: + delta = TclGetInt4AtPtr(currentInstPtr + offset + 1); + goto advanceNext1; + default: + TclStoreInt1AtPtr(offset, currentInstPtr + 1); + continue; + } + case INST_JUMP4: + case INST_JUMP_TRUE4: + case INST_JUMP_FALSE4: + offset = TclGetInt4AtPtr(currentInstPtr + 1); + advanceNext4: + if (offset == 0) { + continue; + } + switch (*(currentInstPtr + offset)) { + case INST_NOP: + offset += InstLength(INST_NOP); + goto advanceNext4; + case INST_JUMP1: + offset += TclGetInt1AtPtr(currentInstPtr + offset + 1); + goto advanceNext4; + case INST_JUMP4: + offset += TclGetInt4AtPtr(currentInstPtr + offset + 1); + goto advanceNext4; + default: + TclStoreInt4AtPtr(offset, currentInstPtr + 1); + continue; + } + } + } + + /* * Trim unreachable instructions after a DONE. */ LocateTargetAddresses(envPtr, &targets); - for (pc = envPtr->codeStart ; pc < envPtr->codeNext-1 ; pc += size) { + for (currentInstPtr = envPtr->codeStart ; + currentInstPtr < envPtr->codeNext-1 ; + currentInstPtr += AddrLength(currentInstPtr)) { int clear = 0; - size = tclInstructionTable[*pc].numBytes; - if (*pc != INST_DONE) { + if (*currentInstPtr != INST_DONE) { continue; } - assert (size == 1); - while (!IsTargetAddress(&targets, pc + 1 + clear)) { - clear += tclInstructionTable[*(pc + 1 + clear)].numBytes; + + while (!IsTargetAddress(&targets, currentInstPtr + 1 + clear)) { + clear += AddrLength(currentInstPtr + 1 + clear); } - if (pc + 1 + clear == envPtr->codeNext) { + if (currentInstPtr + 1 + clear == envPtr->codeNext) { envPtr->codeNext -= clear; } else { while (clear --> 0) { - *(pc + 1 + clear) = INST_NOP; + *(currentInstPtr + 1 + clear) = INST_NOP; } } } -- cgit v0.12 From d2874a90b95a1cac70a0c8e84908154356a9a18d Mon Sep 17 00:00:00 2001 From: dkf Date: Thu, 6 Jun 2013 06:53:55 +0000 Subject: Split the optimizer up. Remove the dreaded 'goto' from which doesn't need it. --- generic/tclOptimize.c | 208 ++++++++++++++++++++++++++++++-------------------- 1 file changed, 127 insertions(+), 81 deletions(-) diff --git a/generic/tclOptimize.c b/generic/tclOptimize.c index 3e0d351..7d4226e 100644 --- a/generic/tclOptimize.c +++ b/generic/tclOptimize.c @@ -17,8 +17,11 @@ * Forward declarations. */ +static void AdvanceJumps(CompileEnv *envPtr); +static void ConvertZeroEffectToNOP(CompileEnv *envPtr); static void LocateTargetAddresses(CompileEnv *envPtr, Tcl_HashTable *tablePtr); +static void TrimUnreachable(CompileEnv *envPtr); /* * Helper macros. @@ -142,27 +145,67 @@ LocateTargetAddresses( /* * ---------------------------------------------------------------------- * - * TclOptimizeBytecode -- + * TrimUnreachable -- * - * A very simple peephole optimizer for bytecode. + * Converts code that provably can't be executed into NOPs and reduces + * the overall reported length of the bytecode where that is possible. * * ---------------------------------------------------------------------- */ -void -TclOptimizeBytecode( +static void +TrimUnreachable( CompileEnv *envPtr) { unsigned char *currentInstPtr; - 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 (currentInstPtr = envPtr->codeStart ; + currentInstPtr < envPtr->codeNext-1 ; + currentInstPtr += AddrLength(currentInstPtr)) { + int clear = 0; + + if (*currentInstPtr != INST_DONE) { + continue; + } + + while (!IsTargetAddress(&targets, currentInstPtr + 1 + clear)) { + clear += AddrLength(currentInstPtr + 1 + clear); + } + if (currentInstPtr + 1 + clear == envPtr->codeNext) { + envPtr->codeNext -= clear; + } else { + while (clear --> 0) { + *(currentInstPtr + 1 + clear) = INST_NOP; + } + } + } + + Tcl_DeleteHashTable(&targets); +} + +/* + * ---------------------------------------------------------------------- + * + * ConvertZeroEffectToNOP -- + * + * 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. + * + * ---------------------------------------------------------------------- + */ + +static void +ConvertZeroEffectToNOP( + CompileEnv *envPtr) +{ + unsigned char *currentInstPtr; + int size; + Tcl_HashTable targets; LocateTargetAddresses(envPtr, &targets); for (currentInstPtr = envPtr->codeStart ; @@ -211,6 +254,7 @@ TclOptimizeBytecode( } } break; + case INST_LNOT: switch (nextInst) { case INST_JUMP_TRUE1: @@ -231,6 +275,7 @@ TclOptimizeBytecode( break; } break; + case INST_TRY_CVT_TO_NUMERIC: switch (nextInst) { case INST_JUMP_TRUE1: @@ -271,6 +316,7 @@ TclOptimizeBytecode( } break; } + if (blank > 0) { for (i=0 ; icodeStart ; currentInstPtr < envPtr->codeNext-1 ; @@ -294,82 +355,67 @@ TclOptimizeBytecode( case INST_JUMP_TRUE1: case INST_JUMP_FALSE1: offset = TclGetInt1AtPtr(currentInstPtr + 1); - delta = 0; - advanceNext1: - if (offset + delta == 0) { - continue; - } - if (offset + delta < -128 || offset + delta > 127) { - TclStoreInt1AtPtr(offset, currentInstPtr + 1); - continue; - } - offset += delta; - switch (*(currentInstPtr + offset)) { - case INST_NOP: - delta = InstLength(INST_NOP); - goto advanceNext1; - case INST_JUMP1: - delta = TclGetInt1AtPtr(currentInstPtr + offset + 1); - goto advanceNext1; - case INST_JUMP4: - delta = TclGetInt4AtPtr(currentInstPtr + offset + 1); - goto advanceNext1; - default: - TclStoreInt1AtPtr(offset, currentInstPtr + 1); - continue; + for (delta=0 ; offset+delta != 0 ;) { + if (offset + delta < -128 || offset + delta > 127) { + break; + } + offset += delta; + switch (*(currentInstPtr + offset)) { + case INST_NOP: + delta = InstLength(INST_NOP); + continue; + case INST_JUMP1: + delta = TclGetInt1AtPtr(currentInstPtr + offset + 1); + continue; + case INST_JUMP4: + delta = TclGetInt4AtPtr(currentInstPtr + offset + 1); + continue; + } + break; } + TclStoreInt1AtPtr(offset, currentInstPtr + 1); + continue; + case INST_JUMP4: case INST_JUMP_TRUE4: case INST_JUMP_FALSE4: - offset = TclGetInt4AtPtr(currentInstPtr + 1); - advanceNext4: - if (offset == 0) { - continue; - } - switch (*(currentInstPtr + offset)) { - case INST_NOP: - offset += InstLength(INST_NOP); - goto advanceNext4; - case INST_JUMP1: - offset += TclGetInt1AtPtr(currentInstPtr + offset + 1); - goto advanceNext4; - case INST_JUMP4: - offset += TclGetInt4AtPtr(currentInstPtr + offset + 1); - goto advanceNext4; - default: - TclStoreInt4AtPtr(offset, currentInstPtr + 1); - continue; + for (offset = TclGetInt4AtPtr(currentInstPtr + 1); offset!=0 ;) { + switch (*(currentInstPtr + offset)) { + case INST_NOP: + offset += InstLength(INST_NOP); + continue; + case INST_JUMP1: + offset += TclGetInt1AtPtr(currentInstPtr + offset + 1); + continue; + case INST_JUMP4: + offset += TclGetInt4AtPtr(currentInstPtr + offset + 1); + continue; + } + break; } - } - } - - /* - * Trim unreachable instructions after a DONE. - */ - - LocateTargetAddresses(envPtr, &targets); - for (currentInstPtr = envPtr->codeStart ; - currentInstPtr < envPtr->codeNext-1 ; - currentInstPtr += AddrLength(currentInstPtr)) { - int clear = 0; - - if (*currentInstPtr != INST_DONE) { + TclStoreInt4AtPtr(offset, currentInstPtr + 1); continue; } - - while (!IsTargetAddress(&targets, currentInstPtr + 1 + clear)) { - clear += AddrLength(currentInstPtr + 1 + clear); - } - if (currentInstPtr + 1 + clear == envPtr->codeNext) { - envPtr->codeNext -= clear; - } else { - while (clear --> 0) { - *(currentInstPtr + 1 + clear) = INST_NOP; - } - } } +} + +/* + * ---------------------------------------------------------------------- + * + * TclOptimizeBytecode -- + * + * A very simple peephole optimizer for bytecode. + * + * ---------------------------------------------------------------------- + */ - Tcl_DeleteHashTable(&targets); +void +TclOptimizeBytecode( + CompileEnv *envPtr) +{ + ConvertZeroEffectToNOP(envPtr); + AdvanceJumps(envPtr); + TrimUnreachable(envPtr); } /* -- cgit v0.12 From 6f9ac2478c554fbf3fff18e76b690199ade088cb Mon Sep 17 00:00:00 2001 From: dkf Date: Thu, 6 Jun 2013 06:56:20 +0000 Subject: Minor grammar fix. --- generic/tclCompile.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/generic/tclCompile.h b/generic/tclCompile.h index fdb281b..908dceb 100644 --- a/generic/tclCompile.h +++ b/generic/tclCompile.h @@ -122,9 +122,9 @@ typedef struct ExceptionAux { * problem. */ int expandTargetDepth; /* The stack depth expected at the outermost * expansion within the loop. Not meaningful - * if there have are no open expansions - * between the looping level and the point of - * jump issue. */ + * if there are no open expansions between the + * looping level and the point of jump + * issue. */ int numBreakTargets; /* The number of [break]s that want to be * targeted to the place where this loop * exception will be bound to. */ -- cgit v0.12