Tcl Source Code

The attached patch modifies the function
ValidatePcAndStackTop (used only under
TCL_COMPILE_DEBUG) to verify that no bytecode exceeds
its reported stack usage.

The testsuite bombs immediately! If we "relax" the
constraint somewhat (allow 1 in excess of the reported
stack usage) there are still 20 tests that panic.

I hereby declare open hunt season for the bugs in
tclCompCmds.c, possibly also in tclCompExpr.c and/or
tclCompile.c.

Logged In: YES 
user_id=148712

Fixed the overestimates for callBuiltinFunc1 and lindexmulti
in the HEAD.

Logged In: YES 
user_id=148712

Patch committed.

File Added - 14439: time.tcl

Logged In: YES 
user_id=148712

Added the script time.tcl for timing compilation; it
repeatedly compiles the body of two procs (heapsort in
tclbench, redirect in the ncgi module of tclbench).

The patch causes a slowdown of about 1% - nothing.

File Added - 14437: fixLevels2.patch

Logged In: YES 
user_id=148712

A new patch (fixLevels2.patch) that computes the tcl
required stack almost perfectly (see below), does it
automatically for code with no jumps and is not more
expensive than the original implementation. The patch also
includes the testing code (effective under
TCL_COMPILE_DEBUG) of validate.patch.

The way it works is:

1. the instruction description table got a new int field
stackEffect, populated at the start of tclCompile.c

2. the macros that push instructions (in tclCompile.h) also
manage the depth count. The computations are correct for
linear code; commands that have non-linear flow have to take
care to set the new field envPtr->currStackLevel correctly
at the start of each basic block.

3. the compile procs in (tclCompCmds.c, tclCompExpr.c) for
all commands that emit jumps were adapted:
TclCompileCatchCmd, TclCompileForCmd, TclCompileForeachCmd,
TclCompileIfCmd, TclCompileWhileCmd, CompileLandOrLorExpr,
CompileCondExpr. 

The stack balance of two instructions is overestimated:
  - callBuiltinFunc1 is set to have a stack balance of +1,
corresponding to inbuilt math functions with no arguments;
the correct is (1-numArgs).
  - lindexMulti is set to have a stack balance of (1-opnd)
instead of the correct (-opnd). This is the only instruction
that has the stack balance "coded" in the first operand
where the formula (1-opnd) is not correct ...

Both could be corrected, at the cost of a slight code
complication. As overestimates are safe, this was not deemed
necessary.

File Added - 13678: fixLevels1.patch.gz

Logged In: YES 
user_id=148712

A new quick&dirty patch (fixLevels1.patch). In this patch:

1. all stackDepth computations are removed from
tclCompCmds.c and tclCompile.c - this is nice, the compiler
got simpler.

2. the instruction description table got a new int field
stackEffect, populated at the start of tclCompile.c

3. the macros that push instructions (in tclCompile.h) also
manage the depth count

4. the function ValidatePcAndStackTop is updated as per
validate.patch

File Added - 13648: fixLevels0.patch

Logged In: YES 
user_id=148712

Here (fixLevels0.patch) is a quick and (very) dirty fix that
is guaranteed to avoid all segfaults, albeit at a possible
waste of memory.

This is just a "proof of concept" patch; more elaborate
variants are in consideration. Should we adopt this general
approach (postprocessing to determine the stack depth), a
larger patch will then simplify all compiler code to avoid
computing a value we throw away at the end ...

File Added - 13626: ex2.patch

Logged In: YES 
user_id=148712

The attached ex2.patch shows thekind of buglets that have to
be fixed in the compiler; it corrects the misbehaviour in
example 2, but not that in example 1.

Logged In: YES 
user_id=148712

Two nice examples of bad computations of the tcl stack depth
in expressions - straight from the testsuite.

Compiling with TCL_TRACE_COMPILE and setting
tcl_traceCompile to 2, we see:

Ex 1: reported depth 2, used depth 5

  ByteCode 0x814bb18, refCt 1, epoch 0, interp 0x8120028
(epoch 0)
  Source "expr {pow(2.1, 27.5-(24.4*(5%2)))}\n"
  Cmds 1, src 35, inst 16, litObjs 5, aux 0, stkDepth 2,
code/src 4.11
  Code 144 = header 100+inst 16+litObj 20+exc 0+aux 0+cmdMap
4
  Commands 1:
      1: pc 0-14, src 0-33
  Command 1: "expr {pow(2.1, 27.5-(24.4*(5%2)))}"
    (0) push1 0         # "2.1"
    (2) push1 1         # "27.5"
    (4) push1 2         # "24.4"
    (6) push1 3         # "5"
    (8) push1 4         # "2"
    (10) mod 
    (11) mult 
    (12) sub 
    (13) callBuiltinFunc1 13 
    (15) done 


Ex 2: reported depth 2, used depth 7

ByteCode 0x81553f8, refCt 1, epoch 0, interp 0x8120028
(epoch 0)
  Source "expr 2 + 3 +\n"
  Cmds 1, src 13, inst 18, litObjs 4, aux 0, stkDepth 2,
code/src 11.08
  Code 144 = header 100+inst 18+litObj 16+exc 0+aux 0+cmdMap
4
  Commands 1:
      1: pc 0-16, src 0-11
  Command 1: "expr 2 + 3 +"
    (0) push1 0         # "2"
    (2) push1 1         # " "
    (4) push1 2         # "+"
    (6) push1 1         # " "
    (8) push1 3         # "3"
    (10) push1 1        # " "
    (12) push1 2        # "+"
    (14) concat1 7 
    (16) exprStk 
    (17) done 

A fix for example 2 follows soon; it does *not* fix example
1, which shows that the problem may be quite general. It is
present since Tcl8.0

File Added - 13557: validate.patch