Jump table optimization in case macros.

Hi All,

Brief demo time. In TXR 192, the case macros now not only use a hash table lookup for symbolic keys but also direct table lookup for integer and character keys.

When there are enough keys that are all integers or all characters, and they are clustered in a small range, the behavior is as exemplified by the example below. The swtch virtual machine instruction at address 18 is used to dispatch directly to the cases. Cases 106 through 109 result in the same jump address being wired into four slots in the table.

The generated code checks whether x is an integer, and that it's in the expected range.

Pay attention to the omitted case 103.  It has an entry in the jump table which branches to address 30.  The code at 30, loads datum d001 into the output register; d001 is the #:nohit symbol: a unique symbol (gensym) distinct from any possible value.

So in other words, the missing cases in the range are treated as a "no hit", just like out-of-range or wrongly typed values.

Code starting at 39 checks whether the prior lookup produced the "no hit" indicator and in that case executes the fallback t case, and takes its value.

1> (compile-toplevel
    '(caseql x
       (100 'hundred)
       (101 'one-oh-one)
       (102 'one-oh-two)
       ;; left out deliberately (103 'one-oh-three)
       (104 'one-oh-four)
       (105 'one-oh-five)
       ((106 107 108 109) 'one-oh-six-nine)
       (t   'notfound)))
** warning: (expr-1:2) unbound variable x
#
2> (disassemble *1)
data:
 d000: x
 d001: #:nohit
 d002: hundred
 d003: one-oh-one
 d004: one-oh-two
 d005: one-oh-four
 d006: one-oh-five
 d007: one-oh-six-nine
 d008: notfound
funs:
    0: integerp
    1: <=
    2: -
code:
    0: 04020002 frame 2 2
    1: 78400800 getv v00000 d000
    2: 30810401 movsr v00001 d001
    3: 24010003 gcall t003 0 v00000
    4: 08000000
    5: 4800000C if t003 12
    6: 00000003
    7: 39910004 movrsi t004 100
    8: 39B50005 movrsi t005 109
    9: 24030003 gcall t003 1 t004 v00000 t005
   10: 00040001
   11: 00050800
   12: 48000027 if t003 39
   13: 00000003
   14: 39910005 movrsi t005 100
   15: 24020004 gcall t004 2 v00000 t005
   16: 08000002
   17: 00000005
   18: 540A0004 swtch t004 24 26 28 30 32 34 36 36 36 36
   19: 001A0018
   20: 001E001C
   21: 00220020
   22: 00240024
   23: 00240024
   24: 30810402 movsr v00001 d002
   25: 44000026 jmp 38
   26: 30810403 movsr v00001 d003
   27: 44000026 jmp 38
   28: 30810404 movsr v00001 d004
   29: 44000026 jmp 38
   30: 30810401 movsr v00001 d001
   31: 44000026 jmp 38
   32: 30810405 movsr v00001 d005
   33: 44000026 jmp 38
   34: 30810406 movsr v00001 d006
   35: 44000026 jmp 38
   36: 30810407 movsr v00001 d007
   37: 44000026 jmp 38
   38: 30030801 movsr t003 v00001
   39: 4C00002B ifq v00001 d001 43
   40: 08010401
   41: 30020408 movsr t002 d008
   42: 4400002C jmp 44
   43: 30020801 movsr t002 v00001
   44: 10000002 end t002
   45: 10000002 end t002
instruction count:
   33