Working on the optimizer, and finding a few bugs in bytecode generation.

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:
+ */