make peep optimiser recurse mostly only shallowly
authorDavid Mitchell <davem@iabyn.com>
Tue, 5 Jul 2011 14:53:34 +0000 (15:53 +0100)
committerDavid Mitchell <davem@iabyn.com>
Thu, 14 Jul 2011 10:59:17 +0000 (11:59 +0100)
commit3c78429c102e0fe2ad30c60dfe52636b6071ef19
treef3db55e85727ab0a493181968dd0e9c56899b984
parentb65222daf37ead86c871b004cd5478701ba44b64
make peep optimiser recurse mostly only shallowly

Long blocks of code that include logical or loop ops (i.e. those with
multiple 'branches' of ops, such as op_other, op_redo etc) cause
Perl_rpeep to recurse deeply and eventaully SEGV.

For example this crashes, due to the ENTERLOOP:

    eval ("{\$x = 1 }\n" x 10000)

The deep recursion happens because the processing of the entire rest of
the code occurs in within the nested call. For example in the code

    A && B; C; D; E;

the ops are structured as

A -> AND -> C -> D -> E
       \   /
         B

where AND->op_next points to C, while AND->op_other points to B.
rpeep() would normally process each op in the op_next sequence in turn
(i.e. A/AND/C/D/E), but when it reaches AND, it recursively calls
rpeep(B), which happens to then process B/C/D/E. Finally it returns,
and the parent rpeep processes C, finds it's already done, and exits.

Clearly, if C,D,E etc also contain conditional/loop ops, then the
recursion level gradually stacks up.

The fix for this is to add a small deferred queue to rpeep().
Whenever rpeep wants to recurse with op_other or op_lastop etc,
it instead adds it to the deferred queue. Only if the queue is full is
rpeep actually called. The hope is that by deferring, when we do
eventually process it, enough of the main op_next chain has already been
processed to ensure that the child rpeep returns very early.

In the example above, processing of AND causes B to be added to the queue,
and the main rpeep process continues processing C, D etc. Sometime later,
the queue becomes full and B is processed via a recursive call to rpeep.
B is processed, and op_next is followed to C, but C is marked as already
processed, so the child rpeep returns almost immediately.

For LOOP ops, I've stopped following op_redoop and op_nextop, since
AFAIKT the ops these point to will also be reachable vie op_next anyway.
op_lastop is the exception; in while(1){..} only op_lastop points to the
rest of the code block.

Note that this commit doesn't guarantee only shallow recursion, it just
makes deep recursion fairly unlikely.

Note also that this commit causes the order of the processing of op_next
chains to be altered; this can affect the ordering of compiler warnings
and fatal messages among potentially other things.
ext/XS-APItest/t/peep.t
op.c
t/lib/strict/subs
t/op/threads.t