[perl #108276] avoid deep recursion in Perl_op_free()

Based on a patch by Niels Thykier, with the following changes:

- the stack is allocated dynamically, rather than with a fixed depth
  of 10

- reordered the loop to avoid pushing the argument and immediately
  popping it.  This wasn't a big deal with the auto stack, but avoids
  a Newx() call for freeing leaf nodes
perldelta for 0997db6f4222
t/TEST: add -w to shebang, fix a used-once warning

Adding -w should be ok, despite peculiar code style; it avoids
require, unlike "use strict".  Added risk of perl brokenness seems
vanishingly small.  Fix one used-once warning thus exposed, and one
test in FileHandle.t surprised by t/TEST's new '-w' in the shebang.
t/TEST: move our @found out to its real scope

commit c96083ea8213 added our @found inside sub _find_tests,
but testing with strict exposes probs:

  $ perl -cw -Ilib -Mstrict t/TEST
  Variable "@found" is not imported at t/TEST line 198.
  Variable "@found" is not imported at t/TEST line 202.
  Global symbol "@found" requires explicit package name at t/TEST line 198.
  Global symbol "@found" requires explicit package name at t/TEST line 202.

No point in arguing, hoist decl out to file scope.
t/TEST: $failure doesnt need to use defined

$failure handling in <$results> processing loop does not need extra
subtlety of defined-ness checks - just give it an initial (false)
value, and check for truth.
t/TEST: add a common timestamp

Commit 0978c4bed computed a timestamp string as part of an output
filename, make it available for others.
t/TEST: comment some of the <$results> loop vars

Add comments to var declarations, to help clarify loop operation.
t/TEST: move do_nothing test after option-handling code

As explained in commit c537bcda1, $do_nothing's purpose is to prevent
TEST from actually running the tests, so that it can be required by
harness, and its routines reused.

This patch moves TEST's $do_nothing check after its option-handling
code, allowing those options to be used to alter the behavior of the
TEST subroutines when called by harness, the same as when they're
called from TEST::main.

TODO: With TEST's option handling done even for $do_nothing cases, it
consumes all options before harness sees them, so harness options -v
and -torture are broken.  There are multiple ways to handle it, all
needing some consensus:

- harness does selective option scanning before requiring TEST.  It
  could either consume its options or pass them thru once it handles
  them.

- both -v and -torture are implemented by TEST and harness, and mean
  qualitatively the same thing.  OTOH, any consumers of the respective
  outputs may care about differences.  Simply, could rename one of
  each option to avoid the conflict.

- use of $TEST::verbose (or are namespaces also to be avoided?)
t/TEST: add -lxperf option to run tests under linux's perf stat

With this patch, TEST can run each test-script under linux's perf
stat.  Since previous patch honors options for $do_nothing / requires,
harness can use perf stat too.

 t]$ ./perl -I../lib TEST -lxperf
 t]$ ./perl harness -lxperf

"perf stat" output is comparable to that of "valgrind --tool=cachegrind"
but it takes very little extra CPU to run:

				export TEST_OPTS=-lxperf
	time make test		time make test
	--------------		--------------
	real	25m41.122s	real	26m30.719s
	user	18m28.773s	user	18m43.286s
	sys	1m12.705s	sys	1m33.398s

Given this small runtime cost, porters might be inclined to use it and
inspect the data.  There may be some core regression tests that are
useful for benchmarking purposes.

EXAMPLES:

 Performance counter stats for './perl base/cond.t':

          2.077911 task-clock                #    0.640 CPUs utilized
                 2 context-switches          #    0.963 K/sec
                 1 cpu-migrations            #    0.481 K/sec
               519 page-faults               #    0.250 M/sec
         2,753,978 cycles                    #    1.325 GHz
         1,725,265 stalled-cycles-frontend   #   62.65% frontend cycles idle
         2,405,122 stalled-cycles-backend    #   87.33% backend  cycles idle
         3,278,429 instructions              #    1.19  insns per cycle
                                             #    0.73  stalled cycles per insn [52.13%]
     <not counted> branches
     <not counted> branch-misses

       0.003244748 seconds time elapsed

perf stat --repeat N also computes std-deviation for each measurement
it does, so this patch makes that feature available.  Std-dev will
tell us when performance differences are lost in the noise.

 ./perl TEST -v -lxperf=10 re/pat_rt_report.t
   perf stat --repeat 10 -- ./perl -I.. -MTestInit re/pat_rt_report.t
     ./perl -I.. -MTestInit re/pat_rt_report.t

 Performance counter stats for './perl -I.. -MTestInit re/pat_rt_report.t' (10 runs):

         98.749506 task-clock                #    0.001 CPUs utilized            ( +- 23.68% )
                68 context-switches          #    0.686 K/sec                    ( +- 82.04% )
                10 cpu-migrations            #    0.097 K/sec                    ( +- 17.44% )
             2,956 page-faults               #    0.030 M/sec                    ( +- 23.22% )
       254,477,657 cycles                    #    2.577 GHz                      ( +- 26.02% ) [50.43%]
        75,556,485 stalled-cycles-frontend   #   29.69% frontend cycles idle     ( +- 19.50% ) [50.93%]
        62,921,965 stalled-cycles-backend    #   24.73% backend  cycles idle     ( +- 25.21% ) [51.50%]
       241,522,257 instructions              #    0.95  insns per cycle
                                             #    0.31  stalled cycles per insn  ( +- 34.07% ) [50.96%]
        53,147,072 branches                  #  538.201 M/sec                    ( +- 31.19% ) [50.18%]
         2,451,318 branch-misses             #    4.61% of all branches          ( +- 11.32% ) [49.95%]

     141.101988701 seconds time elapsed                                          ( +- 99.91% )

The patch has 3 parts:

An addition to TEST:_cmd() which wraps the test invocation inside a
"perf stat ..." as shown above, using a %cmdwrap template.

Option-parsing code, which handles several option forms:
  1) -lxperf
      writes file "$tstamp.perf" into ./t (after `cd $t && ...`)
  2) -lxperf=4
      adds "--repeat 4" to perf stat invocation.
  3) -lxperf=(key=val) pairs
      known key=value pairs (with =defaults given)
       - tool=perf	# path to tool
       - cmd=stat	# todo try others, perf record, etc
       - reps=1		#
       - rptdir		# write reports to a separate data-repo, safe from git clean -dxf
       - name   	# to convey branch-name and/or config-info, tstamp is prefixed,
       - opts		# passthru options to perf-stat

$ENV{TEST_OPTS} is split on /;/ and prepended to @ARGV before option
handling, so the following export will affect both make jobs.

  export TEST_OPTS="-v;-lxperf=reps=3:rptdir=$HOME/perl/perfdata"
  make test
  make test_harness

NOTES:

Test script output under perf stat --repeat 4 violates the "plan just
once" rule of TAPv13 spec.  It could be extended:

   "The plan cannot appear in the middle of the output, only at
    beginning or end.  Multiple sets of (plan + tests) are allowed, if
    all plans agree"

perf stat --repeat N causes perf to compute std-deviation(s) for each
measure.  1st example below is w/o repeat, 2nd with it, corresponding
to the TEST and harness examples above.  I dont know how to read into
the numbers, but theres value in having them; they provide some
estimate of "noise-floor" on performance for a given test.

The -opts option passthru to perf stat allows "-x," to cause perf stat
to emit CSV output.  This is easier to parse than the human readable
output, but doesnt include the computed/normalized values, nor the
name that the "Performance counter stats" (see examples) are for.

TODO

Probable rework of -lxperf option parsing
- no way now to get output to STDOUT, only to file. maybe not worth having
- keep (k=v:)+ form
- use name="%B-%G-%T.perf" by default "$branch-$sha1st6-$timestamp.perf"
- use wr=1 to save file
- dir=$HOME/perfruns (shorten rptdir)

Using reps=2 yields "FAILED--seen duplicate leader" on every test.
Fixing this requires changes to TEST's <results> processing loop.  The
reps handling sub-option code is in this patch because it serves as a
test-case for further changes to optional behavior.

The command wrapper template is pretty minimal and constrained; the
output file name is "$dir/$timestamp$name.perfstat", chosen to match
with $timestamp.ttimes so that both file-types are browsable as a pair.

TEST_OPTS is split on ';', -lxperf is split on ':' into k=v pairs.
There may be scenarios where these delimiters are inconvenient, or the
simplistic parse is brittle.

   Performance counter stats for './perl base/cond.t' (3 runs):
t/TEST: simplify <$results> processing loop. - TAP13.1+

Support use of the --repeat=3 option of linux's perf stat.  This
basically means extending the TAPv13 spec (or t/TEST's implementation)
to allow repeated (ie R) plan executions (ie R occurrences of "1..N"
plus the preceding or following N * "ok"s), as long as all R plans
have the same N.

When a test script is run (under linux perf with --repeat=N), the
value of R is unavailable in the output; it is transparent other than
the repetition itself.  But we woundnt want it anyway; TAP readers
dont need to handle a new kind of input.  If we just allow R
repetitions of 1..N tests, we get loose coupling and dont care if
--repeat=5 were given.

Current legal TAP is essentially either:

  print "ok $_\n" for 1..N;	# 1A
  print "1..N\n";
  # OR [1]
  print "1..N\n";		# 1B
  print "ok $_\n" for 1..N;

The big simplification here is that under --repeat, leading vs
trailing "1..N"s are an irrelevant detail.

- "1..N" plans are only allowed before any tests, or after all of
  them, ie ($next==0 or $next==$plan).  We just verify this when
  "1..N" is seen in test output.

- $plan = undef initially, updated to N when "1..N" is 1st seen.

- $next=0 when "1..N" is seen [2].

- when 2nd+ "1..N" plans are seen, they are allowed if they agree on N.

- The change to if (defined $plan) accepts "1..0" as legal (ie SKIPs).

- $seen_leader and $trailing_leader are thus obsolete, replaced where
  needed by "if ($plan)", which is set only when "1..N" is seen.

- $seen_ok was used with $seen_leader to reset $next (test-count).
  now handled in [2]

- $max is also taken right from "1..N", replaced with <some-expr>($plan)

NOTES:

[1]: this patch allows BOTH 1A then 1B to run successfully, but not 1B
followed by 1A; the latter would fail on N+1 th test, because the
now-trailing "1..N" failed to reset $next.  This is an unimportant
corner case and doesnt warrant cluttering details in the code.
We are running maintained regression tests here, not logic bombs.

- On "1..N" occurrences:
  $Reps++ to count repeats (tested at end)
  reset $next = 0 after validating it [1]
  $nextreps++, like $next w/o reset.

- post-loop tests:
  change ($next == $max) test to ($nextreps == $Reps * $plan),
  which avoids the now resetting $next.

TODO:

This patch supports --repeat N in t/TEST only; harness is strict wrt
"only 1 plan", ala TAPv13, so make test_harness complains as follows,
and fails the tests.

  comp/use.t ........................................................ All 84 subtests passed
  comp/retainedlines.t .............................................. All 75 subtests passed
  comp/cmdopt.t ..................................................... All 44 subtests passed

Sort whats reported in summary data; unique tests or repeated tests ?
Reduce $totmax vs $max vs $Reps a bit, extra/redundant state is not helpful.
t/TEST: change timings Storable key: perf -> times, a better description

Commit 8e03ad8f6c wrote the tests' timing data to a Storable file
using 'perf' as the storage key, but now that we can capture real perf
stat data during make test, the old name is misleading - change it to
"times" to better describe its origin and character.
t/TEST: suppress 2 uninitialized envars under make test.valgrind

Recent addition of -w on shebang exposed 2 uninitialized vars, due to
VG_OPTS envar added in commit 11b1a7c9, which added glue to reuse
t/TEST's support for make test.valgrind to run linux perf.  The 2
use-cases are:

1. make test.valgrind
2. export VG_OPTS='stat -o perf-stat --append --'
   export VALGRIND=/usr/bin/perf
   export VG_TEST=--help
   make test.valgrind

Since 2 is rather non-obvious, clarify with comment here and in code.

TODO: this patch is old, and either needs to be revalidated, or
perhaps rethought; use-case 2 is mostly obsoleted by -lxperf option,
but case 1 still holds.
t/TEST: RFC start to separate out valgrind test support.

This patch creates an empty t/TestValgrind.pm file, and requires it
from t/TEST when ENV{PERL_VALGRIND} is set.  As such its seeks to
reinterpret the comments at the top of t/TEST.

I propose that the "no require allowed" rule appply to code reached
from "make test" without options.

Code used only for special case testing, like "make test.valgrind", or
with options passed in via $ENV{TEST_OPTS}, need not be constrained
like this.

A broken require is not something seen until the statement is executed
and throws an error.  There is nothing special about require at
parse-time that must be avoided, unless we're more than typically
paranoid.

 make test.valgrind
   /bin/sh -e ./runtests choose
     ./perl TEST
       sh -c valgrind --log-fd=3 --suppressions=perl.supp --leak-check=yes --leak-resolution=high --show-reachable=yes --num-callers=50 --track-origins=yes ./perl -I.. -MTestInit porting/podcheck.t 3>podcheck.t.valgrind-current
         valgrind --log-fd=3 --suppressions=perl.supp --leak-check=yes --leak-resolution=high --show-reachable=yes --num-callers=50 --track-origins=yes ./perl -I.. -MTestInit porting/podcheck.t

If this argument is accepted, it looks simple to move the VALGRIND
related code blocks into new subroutines in the now-empty
TestValgrind.pm file, and call them appropriately.
manisort
op.c: regularize OP_AELEMFAST_LEX vs OP_AELEMFAST setup.

commit 10884df96723d4 promoted CHANGE_TYPE as the "normal" way to
initialize op_type and op_ppaddr fields.  This suggests that
Perl_rpeep()s tweaking of OP_AELEMFAST and OP_AELEMFAST_LEX is
something of a special case.

It turns out that these are pretty normal too; since regen/opcode.pl
insures that PL_ppaddr[OP_AELEMFAST_LEX] == PL_ppaddr[OP_AELEMFAST],
the invariant: o->op_ppaddr == PL_ppaddr[o->op_type] holds after both
the OP_AELEMFAST and OP_AELEMFAST_LEX branches, and the stronger
semantics of CHANGE_TYPE() can be used to communicate this normality.

On a gcc x86-64 -DEBUGGING build, this enlarges 'size op.o' by 16
bytes, but before and after 'objdump -DS op.o' output suggests that
the code itself is identical.
op.c: CHANGE_TYPE for op_integerize and ck_spair

These 2 users do the ++o->op_type trick to modify the OP to its
optimized doppelganger.  But CHANGE_TYPE()s postcondition holds:
o->op_ppaddr = PL_ppaddr[o->op_type], so using it conveys this.
Also fix CHANGE_TYPE(o, ++type) expansion problem with an autovar
inside the "braces".
tweak PERL_TRACE_OPS for usability, add PERL_TRACE_OPS_PAD

Currently with -DPERL_TRACE_OPS builds, a histogram of all optypes
executed is always printed at END.  This is too noisy, so make print
dependent on comand-line option -D.  And dont print 0 values, which
dramatically reduces output for one-liner scripts.

Currently, the trace-ops histogram array (PL_op_exec_cnt[]) has 1
extra slot for counting exec-things (ie for hacking), name it
PERL_TRACE_OPS_PAD, change its default to 10, and implement
following exec-counts:

 - count total ops (in OP-max slot, reported as op-freed)
 - count odd/even op_types
 - count OPs with op_spare set
 - count OPs with "modified" op_ppaddr field
dump.c: runloop debug (skip this)

add DEBUG_U print when o->op_ppaddr != PL_ppaddr[o->op_type]

This is the case for mapstart, which is why dispatching
(*PL_ppaddr[o->op_type])(aTHX) directly would result in a
"panic:..unimplemented_op.." message.

When mismatch is seen, we do a cheesy search for another OP_TYPE with
that op_ppaddr.  This found MAPSTART using GREPSTART, but for truly
custom pp-functions it counts down to -1, and displays a sentinel
op-desc.  Its useful for next patch, further extended patch after it.
dump.c: dispatch pp-code from PL_ppaddr[] directly (skip this)

Dispatch most OPs using (*PL_ppaddr[PL_op->op_type])(aTHX) directly.

DO NOT APPLY

It would be nice if op_ppaddr was an optimization detail, not a
requirement to allow patching in new behavior.  Then we could test to
see what gains the op_ppaddr pointer confers upon execution.  Fully
eliminating op_ppaddr is hard, (and we're likely to just confirm the
pointer is good, even considering its cost), so we cheat here.

This patch does indirect dispatch for most optypes, ie:
  PL_op = (*PL_ppaddr[PL_op->op_type])(aTHX);
but some ops are "bad", and dispatched directly, ie:
  PL_op = PL_op->op_ppaddr(aTHX);

The "bad" ones are those OPs whose type is "modified"
(o->op_ppaddr != PL_ppaddr[o->op_type]), so we
blacklist OPs which panic the indirect way.

This is fundamentally broken; as b82b06b "Reimplement $[ as a module"
shows, practically all OP_s can be modified, we just blacklist those
that currently are modified by one or more tests.

But for research purposes, it does help us determine (eventually) the
slowdown of direct PL_ppaddr[optype], as follows:

- run time make test (etc, etc, etc) on blead vs this branch,
  if no measurable differences then stop, reexamine tests, etc.

- with -DPERL_TRACE_OPS, ++PL_op_exec_cnt[PL_op->op_type] will profile
  the ops run during a test.  From that, we can compute that say 95%
  of X-million OP_s deref'd PL_ppaddr[], causing any measured slowdown.

TODO:

develop a good benchmarking scenario. (ya, just like that ;-)
- need make test under perf
- perlbench - real runtimes, less overhead than core tests.

build a branch with extra op_junk pointer in OP, benchmark it to get
costs (cache, footprint) of extra pointer, and infer from that
(caveats apply) the savings by eliminating op_ppaddr.

collect and analyse a lot of data.

BLUE-SKY:

Actually eliminating op_ppaddr is possible:
- define op_custpp flag in OP
  setOpAddr, setOpType manage the flag
- setOpAddr inserts "modified" ppaddrs into PL_custom_ops (or similar)
- runops loop checks op_custpp flag, query PL_custom_ops for dispatch.
  probly expensive, so want low population of them.

dvar for added check
op.c: set op_spare/op_cust in LINKLIST under -DPERL_TRACE_OPS

In Perl_linklist, when (o->op_ppaddr != PL_ppaddr[o->op_type]), set
op_spare/op_cust bit, and increment last DPERL_TRACE_OPS_PAD slot
(extra.9 below).  This counts the OPs that have been modified by the
time theyre LINKED.

This appears to work - it finds same count of modified ops as 2
execution time tests previously added to Perl_runops_debug(): op-spare
bit set (extra.2,3), and the postcondition above (extra.4,5).

 $ ./perl -Ilib -D0 ext/arybase/t/splice.t
  extra.0: 40430
  extra.1: 68126
  extra.2: 108543
  extra.3: 13
  extra.4: 108543
  extra.5: 13
  extra.9: 13

TBD: extra.9 == extra.5 probably requires no loops over modified OPs.