Andy Wingo [Wed, 16 Apr 2014 10:59:45 +0000 (12:59 +0200)]
Implement frame-bindings
* module/system/vm/frame.scm (parse-code, compute-predecessors):
(compute-genv, compute-defs-by-slot, compute-killv, available-bindings):
(frame-bindings): Add a bunch of hairy code to compute the set of
bindings that are live in a frame.
Andy Wingo [Wed, 16 Apr 2014 10:58:35 +0000 (12:58 +0200)]
Add arity-code
* module/system/vm/debug.scm (arity-code): New interface.
Andy Wingo [Wed, 16 Apr 2014 10:58:20 +0000 (12:58 +0200)]
Add parsing interfaces to the disassembler
* module/system/vm/disassembler.scm (instruction-length):
(instruction-has-fallthrough?, instruction-relative-jump-targets):
(instruction-slot-clobbers): New interfaces; to be used when
determining the bindings available at a given point of a procedure.
Andy Wingo [Wed, 16 Apr 2014 10:51:34 +0000 (12:51 +0200)]
Fix up some opcode metadata
* libguile/vm-engine.c (make-long-immediate, static-ref): Mark as "dst"
instructions.
Andy Wingo [Tue, 15 Apr 2014 20:24:48 +0000 (22:24 +0200)]
Add ability to query local definitions for a procedure
* module/system/vm/debug.scm (arity-definitions): New interface.
* module/system/vm/program.scm (make-binding, binding:boxed?)
(binding:index, binding:start, binding:end): Remove.
(binding:definition-offset, binding:slot): Add.
(program-arity-bindings-for-ip): Rename from program-bindings-for-ip,
as it gives all definitions in an arity. The user will have to do
data-flow analysis to recover the set of variables that are actually
available at any given point.
(arity->arguments-alist): Remove crufty code.
Andy Wingo [Tue, 15 Apr 2014 20:00:30 +0000 (22:00 +0200)]
Fix rtl tests
* module/system/vm/assembler.scm (write-arities): Add a diagnostic.
* test-suite/tests/rtl.test: Fix tests to emit "definition"
instructions.
Andy Wingo [Tue, 15 Apr 2014 19:47:46 +0000 (21:47 +0200)]
Fix frame-call-representation for primitive applications
* module/system/vm/frame.scm (frame-call-representation): Fix to work
for primitives.
* test-suite/tests/eval.test ("stacks"): Update expected result for
substring.
Andy Wingo [Tue, 15 Apr 2014 18:25:16 +0000 (20:25 +0200)]
Assembler residualizes local variable definition locations
* module/system/vm/assembler.scm (write-arities): Serialize definition
locations after names.
(definition): Store definition as a byte offset.
Andy Wingo [Tue, 15 Apr 2014 18:20:01 +0000 (20:20 +0200)]
Bump minor objcode version for recent changes
* libguile/_scm.h (SCM_OBJCODE_MINOR_VERSION):
* module/system/vm/assembler.scm (*bytecode-minor-version*): Bump.
Andy Wingo [Tue, 15 Apr 2014 15:52:41 +0000 (17:52 +0200)]
Write all local variable names into the arities section
* module/system/vm/assembler.scm (put-uleb128, put-sleb128)
(port-position): Lift out these helpers.
(arity-header-len, write-arities, link-arities): Add "nlocals" to the
arity headers. Write names of all locals into the arities section,
not just the arguments. Write them as uleb128's instead of uint32's,
to save space.
* module/system/vm/debug.scm (arity-header-len, arity-nlocals*)
(arity-nlocals, arity-locals, arity-arguments-alist): Adapt to new
encoding for arities.
Andy Wingo [Tue, 15 Apr 2014 13:27:19 +0000 (15:27 +0200)]
Tweak arities debugging representation
* module/system/vm/assembler.scm (meta-arities-size, write-arity-links):
* module/system/vm/debug.scm (arity-keyword-args)
(arity-arguments-alist): Rewrite to put they keyword literals link
first. Unfortunately requires a recompile :/
Andy Wingo [Tue, 15 Apr 2014 12:02:25 +0000 (14:02 +0200)]
Beginnings of local variable information
* module/system/vm/assembler.scm (<arity>, begin-kw-arity, end-arity):
(definition): Add definition macro-instruction. Arrange to record
variable definitions.
* module/language/cps/compile-bytecode.scm (compile-fun): Emit
definition macro-instructions as appropriate.
Andy Wingo [Tue, 15 Apr 2014 10:25:26 +0000 (12:25 +0200)]
Remove needless label remapping in slot-allocation
* module/language/cps/slot-allocation.scm (dead-after-def?):
(dead-after-use?, allocate-slots): Remove some needless remapping
between label indexes in the CFA, the DFA, and their names.
Andy Wingo [Tue, 15 Apr 2014 10:16:41 +0000 (12:16 +0200)]
DFA datums don't rename their labels
* module/language/cps/dfg.scm (analyze-reverse-control-flow): Don't
compute and return an order vector; it's not needed.
($dfa): Remove label renaming. We can just rename labels before
returning the DFA.
(dfa-k-idx, dfa-k-sym, dfa-k-count): Adapt.
(compute-live-variables): Adapt, and rename labels before returning.
Andy Wingo [Tue, 15 Apr 2014 09:18:50 +0000 (11:18 +0200)]
Better backtraces for optimized closures
* module/system/vm/debug.scm (arity-keyword-args, find-program-arity):
New exports.
* module/system/vm/frame.scm (frame-call-representation): Prefer to use
the frame IP to get the procedure.
Andy Wingo [Mon, 14 Apr 2014 15:06:05 +0000 (17:06 +0200)]
statprof avoids mucking with VM trace levels when not counting calls
* module/statprof.scm (statprof-start, statprof-stop): Don't futz the vm
trace level when we aren't counting calls. With this change, statprof
now imposes no overhead on the measured program.
Andy Wingo [Mon, 14 Apr 2014 14:54:51 +0000 (16:54 +0200)]
Better state handling in statprof
* module/statprof.scm (statprof-fold-call-data)
(statprof-proc-call-data): Add optional state arg.
(gcprof): Add optional port arg, and pass state arg explicitly.
(statprof-display-anomalies, statprof-display)
(statprof-call-data->stats): Pass state explicitly.
Andy Wingo [Mon, 14 Apr 2014 14:31:02 +0000 (16:31 +0200)]
Optimize make-stack
* libguile/continuations.h:
* libguile/continuations.c (scm_i_continuation_to_frame): Operate on
low-level C structures instead of heap objects.
* libguile/frames.h:
* libguile/frames.c (frame_offset, frame_stack_base): Const args.
(scm_c_frame_closure): New helper.
(scm_frame_procedure): Use the new helper.
* libguile/stacks.c (stack_depth, narrow_stack, scm_make_stack): Rework
to avoid allocating frames as we traverse the stack, and to avoid an
n**2 case where there are outer cuts.
Andy Wingo [Mon, 14 Apr 2014 13:14:26 +0000 (15:14 +0200)]
scm_c_make_frame takes struct scm_frame as arg
* libguile/frames.h:
* libguile/frames.c (scm_c_make_frame): Adapt to take a const struct
scm_frame as the argument. Adapt callers.
* libguile/continuations.c:
* libguile/stacks.c: Adapt callers.
Andy Wingo [Mon, 14 Apr 2014 12:54:14 +0000 (14:54 +0200)]
Refactor to frames code
* libguile/frames.h:
* libguile/frames.c (scm_c_frame_previous): New internal helper.
(scm_frame_previous): Use the helper.
(RELOC): Take kind and low-level frame args separately. Adapt
callers.
(frame_stack_base, frame_offset): New helpers.
(scm_i_frame_offset, scm_i_frame_stack_base): Use low-level helpers.
Andy Wingo [Mon, 14 Apr 2014 11:53:35 +0000 (13:53 +0200)]
Optimize make-global-cont-folder
* module/language/cps.scm (make-global-cont-folder): Inline the
fold-values, as peval doesn't do so. Allows closure conversion to
avoid any closure creation.
Andy Wingo [Sun, 13 Apr 2014 12:40:22 +0000 (14:40 +0200)]
Improve disassembly for optimized closures
* module/system/vm/disassembler.scm (code-annotation): Add call-label
and tail-call-label cases.
(disassemble-addr): With call-label we can see sets of mutually
recursive functions, so keep a global "visited?" set.
Andy Wingo [Sun, 13 Apr 2014 12:26:03 +0000 (14:26 +0200)]
Remove debugging code in closure-conversion
* module/language/cps/closure-conversion.scm (prune-free-vars): Remove
pk.
Andy Wingo [Sun, 13 Apr 2014 12:22:22 +0000 (14:22 +0200)]
Eval has no more free variables
* module/ice-9/eval.scm (primitive-eval): Expand out the call to
make-general-closure, so that make-general-closure becomes
well-known. Now eval has no more free variables!
Andy Wingo [Sun, 13 Apr 2014 12:21:25 +0000 (14:21 +0200)]
Closure conversion eliminates self-references introduced by fixpoint
* module/language/cps/closure-conversion.scm (analyze-closures): Build a
bound-vars set as well, to resolve introduced self-references.
(prune-free-vars, convert-one): Arrange to eliminate self-references.
Andy Wingo [Sun, 13 Apr 2014 11:52:56 +0000 (13:52 +0200)]
Refactor to closure-conversion
* module/language/cps/closure-conversion.scm (convert-one): Refactor to
pull in helpers locally, as they will need more state.
Andy Wingo [Sun, 13 Apr 2014 10:21:36 +0000 (12:21 +0200)]
Avoid consing an unbound-arg marker in the evaluator
* module/ice-9/eval.scm (primitive-eval): Turns out we don't need to
cons to make the unbound-arg marker.
Andy Wingo [Sun, 13 Apr 2014 09:47:17 +0000 (11:47 +0200)]
Optimize closures with one free variable
* module/language/cps/closure-conversion.scm (convert-free-var)
(allocate-closure, init-closure, prune-free-vars, convert-one)
(convert-closures): Optimize closures with one free variable.
Andy Wingo [Sat, 12 Apr 2014 21:31:08 +0000 (23:31 +0200)]
Well-known closures represented using pairs or vectors
* module/language/cps/closure-conversion.scm (convert-free-var):
(convert-free-vars): Take self-known? param, to do the right thing for
well-known closures.
(allocate-closure): New helper. Well-known closures are represented
using pairs or vectors.
(init-closure): Adapt tpo DTRT for well-known closures.
(prune-free-vars): Move up.
(convert-one): Adapt to new well-known closure representation.
Andy Wingo [Sat, 12 Apr 2014 20:42:23 +0000 (22:42 +0200)]
Update verify-cps
* module/language/cps/verify.scm (verify-cps): Update for recent CPS
changes.
Andy Wingo [Sat, 12 Apr 2014 17:46:23 +0000 (19:46 +0200)]
Avoid creating closures with no free variables
* module/language/cps/closure-conversion.scm (init-closure): Return just
one value.
(analyze-closures): Rewrite the well-known set to key off the label
instead of the closure identifiers before returning.
(convert-one): Avoid creating closure objects at runtime or load-time
when "instantiating" or calling well-known closures with no free
variables.
(prune-free-vars): New pass.
(convert-closures): Adapt.
Andy Wingo [Sat, 12 Apr 2014 14:12:33 +0000 (16:12 +0200)]
Hard-wire calls to known procedures
* module/language/cps/closure-conversion.scm (analyze-closures):
(convert-one, convert-closures): Hard-wire calls to known procedures
by transforming $call to $callk.
Andy Wingo [Sat, 12 Apr 2014 13:53:58 +0000 (15:53 +0200)]
closure conversion computes well-known functions
* module/language/cps/closure-conversion.scm (analyze-closures)
(convert-closures, convert-one): Adapt to compute well-known
functions. We don't yet produce $callk though.
Andy Wingo [Sat, 12 Apr 2014 09:52:38 +0000 (11:52 +0200)]
First-order CPS has $program and $closure forms
* module/language/cps.scm ($closure, $program): New CPS types, part of
low-level (first-order) CPS.
(build-cps-exp, build-cps-term, parse-cps, unparse-cps)
(compute-max-label-and-var): Update for new CPS types.
* module/language/cps/closure-conversion.scm: Rewrite to produce a
$program with $closures, and no $funs.
* module/language/cps/reify-primitives.scm:
* module/language/cps/compile-bytecode.scm (compile-fun):
(compile-bytecode): Adapt to new first-order format.
* module/language/cps/dfg.scm (compute-dfg): Add $closure case.
* module/language/cps/renumber.scm (renumber): Allow this pass to work
on either format.
* module/language/cps/slot-allocation.scm (allocate-slots): Add $closure
case.
Andy Wingo [Fri, 11 Apr 2014 16:01:23 +0000 (18:01 +0200)]
Separate make-cont-folder into global and local variants
* module/language/cps.scm (make-global-cont-folder)
(make-local-cont-folder): Separate this macro in two. It's hot and
the difference can be important for perf.
* module/language/cps/dfg.scm (compute-label-and-var-ranges):
* module/language/cps/cse.scm (compute-label-and-var-ranges):
* module/language/cps/dce.scm (compute-live-code): Adapt.
Andy Wingo [Fri, 11 Apr 2014 12:01:27 +0000 (14:01 +0200)]
Root higher-order CPS term is always $kfun $cont
* module/language/cps/arities.scm:
* module/language/cps/closure-conversion.scm:
* module/language/cps/compile-bytecode.scm:
* module/language/cps/constructors.scm:
* module/language/cps/contification.scm:
* module/language/cps/cse.scm:
* module/language/cps/dce.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/prune-bailouts.scm:
* module/language/cps/prune-top-level-scopes.scm:
* module/language/cps/renumber.scm:
* module/language/cps/self-references.scm:
* module/language/cps/simplify.scm:
* module/language/cps/specialize-primcalls.scm:
* module/language/tree-il/compile-cps.scm: Adapt to produce and consume
raw $kfun $cont instances.
* .dir-locals.el: Update $letrec indentation.
Andy Wingo [Fri, 11 Apr 2014 09:51:34 +0000 (11:51 +0200)]
Closure conversion, reify-primitives use $kfun $cont
* module/language/cps/closure-conversion.scm: Produce a $kfun $cont.
* module/language/cps/reify-primitives.scm: Produce and consume $kfun
$cont.
* module/language/cps/compile-bytecode.scm: Adapt.
Andy Wingo [Fri, 11 Apr 2014 09:34:50 +0000 (11:34 +0200)]
Preparation for compile-bytecode to work on $kfun $conts
* module/language/cps/compile-bytecode.scm (compile-fun): Change to take
a $kfun $cont instead of a $fun.
(visit-funs): Change likewise, and call the proc on $kfun $cont's, not
$fun's.
(compile-bytecode): Adapt.
* module/language/cps/dfg.scm (analyze-reverse-control-flow): Adapt to
expect a $kfun $cont.
Andy Wingo [Fri, 11 Apr 2014 09:22:06 +0000 (11:22 +0200)]
compute-dfg takes a $kfun $cont, not a $fun
* module/language/cps/dfg.scm (compute-dfg): Take a $kfun $cont instead
of a $fun.
* module/language/cps/arities.scm:
* module/language/cps/compile-bytecode.scm:
* module/language/cps/contification.scm:
* module/language/cps/cse.scm:
* module/language/cps/dce.scm:
* module/language/cps/simplify.scm:
* module/language/cps/specialize-primcalls.scm: Adapt callers.
Andy Wingo [Fri, 11 Apr 2014 08:21:04 +0000 (10:21 +0200)]
with-fresh-name-state takes a cont, not a $fun
* module/language/cps.scm (with-fresh-name-state): Take a cont instead
of a fun.
* module/language/cps/closure-conversion.scm:
* module/language/cps/constructors.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/prune-bailouts.scm:
* module/language/cps/reify-primitives.scm: Adapt.
Andy Wingo [Fri, 11 Apr 2014 08:12:37 +0000 (10:12 +0200)]
Function defined by make-cont-folder takes a cont, not a $fun
* module/language/cps.scm (make-cont-folder): Take a cont instead of a
$fun.
(with-fresh-name-state): Adapt.
* module/language/cps/cse.scm (compute-label-and-var-ranges):
* module/language/cps/dce.scm (compute-live-code):
* module/language/cps/dfg.scm (compute-dfg):
* module/language/cps/elide-values.scm (elide-values):
* module/language/cps/reify-primitives.scm (reify-primitives):
* module/language/cps/renumber.scm (compute-new-labels-and-vars):
(renumber): Adapt.
Andy Wingo [Thu, 10 Apr 2014 10:11:35 +0000 (12:11 +0200)]
Rename $kentry to $kfun
* module/language/cps.scm ($kfun): Rename from $kentry.
* module/language/cps/arities.scm:
* module/language/cps/closure-conversion.scm:
* module/language/cps/compile-bytecode.scm:
* module/language/cps/constructors.scm:
* module/language/cps/contification.scm:
* module/language/cps/cse.scm:
* module/language/cps/dce.scm:
* module/language/cps/dfg.scm:
* module/language/cps/effects-analysis.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/prune-bailouts.scm:
* module/language/cps/prune-top-level-scopes.scm:
* module/language/cps/reify-primitives.scm:
* module/language/cps/renumber.scm:
* module/language/cps/self-references.scm:
* module/language/cps/simplify.scm:
* module/language/cps/slot-allocation.scm:
* module/language/cps/specialize-primcalls.scm:
* module/language/cps/verify.scm:
* module/language/tree-il/compile-cps.scm: Adapt users.
Andy Wingo [Thu, 10 Apr 2014 08:50:17 +0000 (10:50 +0200)]
src and meta are fields of $kentry, not $fun
* module/language/cps.scm ($kentry, $fun): Attach "src" and "meta" on
the $kentry, not the $fun. This prepares us for $callk to $kentry
continuations that have no corresponding $fun.
* module/language/cps/arities.scm:
* module/language/cps/closure-conversion.scm:
* module/language/cps/compile-bytecode.scm:
* module/language/cps/constructors.scm:
* module/language/cps/contification.scm:
* module/language/cps/cse.scm:
* module/language/cps/dce.scm:
* module/language/cps/dfg.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/prune-bailouts.scm:
* module/language/cps/prune-top-level-scopes.scm:
* module/language/cps/reify-primitives.scm:
* module/language/cps/renumber.scm:
* module/language/cps/self-references.scm:
* module/language/cps/simplify.scm:
* module/language/cps/slot-allocation.scm:
* module/language/cps/specialize-primcalls.scm:
* module/language/cps/verify.scm:
* module/language/tree-il/compile-cps.scm: Adapt.
Andy Wingo [Thu, 10 Apr 2014 07:25:38 +0000 (09:25 +0200)]
Remove tests for old Tree-IL CSE module
* test-suite/tests/cse.test: Remove.
* test-suite/Makefile.am:
Andy Wingo [Tue, 8 Apr 2014 12:10:36 +0000 (14:10 +0200)]
Remove obsolete comment in compile-bytecode.scm
* module/language/cps/compile-bytecode.scm (optimize): Remove an
obsolete comment.
Andy Wingo [Tue, 8 Apr 2014 19:41:42 +0000 (21:41 +0200)]
New pass to avoid free variable creation for self-recursion
* module/language/cps/self-references.scm: New pass, avoids the need for
self-recursion to allocate free variables.
* module/Makefile.am:
* module/language/cps/compile-bytecode.scm: Wire up the new pass.
Andy Wingo [Tue, 8 Apr 2014 08:06:40 +0000 (10:06 +0200)]
Compile some standalone tests to bytecode
* test-suite/standalone/test-out-of-memory:
* test-suite/standalone/test-stack-overflow: Compile these files before
running them. That way, recursion can check the stack-overflow
mechanism instead of the memory allocation mechanism. We compile
beforehand as a prepass so as not to impose an rlimit on a Guile that
previously ran auto-compilation.
Andy Wingo [Sun, 6 Apr 2014 09:08:05 +0000 (11:08 +0200)]
Remove old Tree-IL CSE pass
* module/language/tree-il/cse.scm: Delete.
* module/language/tree-il/optimize.scm: Remove use of Tree-IL CSE.
* module/Makefile.am: Remove language/tree-il/cse.scm.
* module/language/cps/compile-bytecode.scm: Rename CSE keyword to
#:cse?.
Andy Wingo [Sat, 5 Apr 2014 19:08:09 +0000 (21:08 +0200)]
Flow-sensitive analysis of truth values
* module/language/cps/cse.scm (compute-truthy-expressions):
(compute-equivalent-subexpressions, apply-cse): Arrange to infer
truthiness of expressions, and use that information to elide redundant
tests.
Andy Wingo [Sat, 5 Apr 2014 19:06:35 +0000 (21:06 +0200)]
Add effects for specialized primitives
* module/language/cps/effects-analysis.scm (make-vector)
(make-vector/immediate, vector-ref/immediate, vector-set!/immediate)
(struct-ref/immediate, struct-set!/immediate): Add effects.
Andy Wingo [Sat, 5 Apr 2014 12:38:37 +0000 (14:38 +0200)]
Minor cleanup/optimization in CSE
* module/language/cps/cse.scm (compute-available-expressions): Remove
needless for-each definition.
(compute-equivalent-subexpressions): Optimize for-each/2.
Andy Wingo [Sat, 5 Apr 2014 10:16:34 +0000 (12:16 +0200)]
Prune bailouts after contification
* module/language/cps/compile-bytecode.scm (optimize): Prune bailouts
after contifying, so that we return to the tail of the contified
function.
Andy Wingo [Sat, 5 Apr 2014 09:56:44 +0000 (11:56 +0200)]
Match and srfi-9 expose their bailouts to the CSE pass
* module/ice-9/match.upstream.scm (match-next): Inline a call to
"error", so the new CSE pass will see this case as a bailout.
* module/srfi/srfi-9.scm (throw-bad-struct): Reimplement as a syntax
rule, so that the CSE pass sees the "throw" call.
Andy Wingo [Sat, 5 Apr 2014 09:21:33 +0000 (11:21 +0200)]
Remove &bailout; replace uses of &unknown-effects with &all-effects
* module/language/cps/effects-analysis.scm (&bailout): Remove effect.
(&unknown-effects): Remove. Replace uses with &all-effects.
* module/language/cps/cse.scm:
Andy Wingo [Sat, 5 Apr 2014 09:18:20 +0000 (11:18 +0200)]
Remove parts of CSE that deal with bailout
* module/language/cps/cse.scm (compute-available-expressions, cse):
(compute-idoms, compute-equivalent-subexpressions, apply-cse): Remove
attempts to deal with bailout, as the bailout pass handles that
already.
Andy Wingo [Sat, 5 Apr 2014 09:08:47 +0000 (11:08 +0200)]
Add prune-bailouts pass
* module/language/cps/prune-bailouts.scm: New pass.
* module/language/cps/compile-bytecode.scm: Wire it up.
* module/Makefile.am: Add new file.
Andy Wingo [Sat, 5 Apr 2014 08:27:26 +0000 (10:27 +0200)]
Disable Tree-IL CSE
* module/language/tree-il/optimize.scm (optimize): Disable Tree-IL CSE
by default.
Andy Wingo [Sat, 5 Apr 2014 09:32:06 +0000 (11:32 +0200)]
Fix effects analysis for cached-module-box
* module/language/cps/effects-analysis.scm (cached-module-box): Fix
expected arity.
Andy Wingo [Fri, 4 Apr 2014 14:49:59 +0000 (16:49 +0200)]
Fix coverage expectations
* test-suite/tests/coverage.test ("line-execution-counts"): Update
expectations. Since there's nothing to do at the loop header and the
renaming of X happens at the end of the loops, the compiled code only
sees the loop header once.
Andy Wingo [Fri, 4 Apr 2014 12:29:11 +0000 (14:29 +0200)]
More bailout preparation work
* module/language/cps/cse.scm (compute-available-expressions): Compute a
bailout set -- or at least, set things up so that we can do so.
(compute-idoms): Don't add predecessors that bail out.
(apply-cse, cse, compute-equivalent-subexpressions): Thread the
bailout set through the computations.
Andy Wingo [Fri, 4 Apr 2014 11:42:54 +0000 (13:42 +0200)]
Prepare for CSE bailout propagation
* module/language/cps/cse.scm (compute-available-expressions): Prepare
for being able to prune joins from bailouts. Always loop after the
first iteration.
* module/language/cps/effects-analysis.scm: Remove &possible-bailout.
Rename &definite-bailout to &bailout, and rename
&all-effects-but-bailout to &unknown-effects.
Andy Wingo [Fri, 4 Apr 2014 10:15:10 +0000 (12:15 +0200)]
Add common subexpression elimination pass on CPS
* module/language/cps/cse.scm: New file.
* module/language/cps/compile-bytecode.scm: Wire up CSE, on by default.
Currently using the #:cps-cse? keyword.
* module/Makefile.am: Add new file.
Andy Wingo [Fri, 4 Apr 2014 10:08:52 +0000 (12:08 +0200)]
Effects analysis tweaks
* module/language/cps/effects-analysis.scm: Add &fluid-environment
effect, a dependency of fluid-ref and fluid-set!, and an effect of
push-fluid/pop-fluid.
(list): Depend on &cdr.
(resolve, cached-toplevel-box, cached-module-box): Don't depend on
&box.
Andy Wingo [Fri, 4 Apr 2014 10:07:24 +0000 (12:07 +0200)]
Fix verify-cps to work
* module/language/cps/verify.scm (verify-cps): Relax requirements for
variable names to be symbols.
Andy Wingo [Fri, 4 Apr 2014 10:06:59 +0000 (12:06 +0200)]
constant-needs-allocation? fix
* module/language/cps/dfg.scm (constant-needs-allocation?): Constants
need allocation when they are used as a slot-needing operand, not when
they are not used as an immediate operand. Fixes the case where one
var is used in both ways after CSE, in struct-set!/immediate.
Andy Wingo [Fri, 4 Apr 2014 08:39:42 +0000 (10:39 +0200)]
Remove variable-set! clause from compile-fun
* module/language/cps/compile-bytecode.scm (compile-fun): Remove
vestigial `variable-set!' clause.
Andy Wingo [Thu, 3 Apr 2014 14:37:07 +0000 (16:37 +0200)]
Effects analysis: define causes-all-effects?
* module/language/cps/effects-analysis.scm (causes-all-effects?): New
export.
Andy Wingo [Thu, 3 Apr 2014 14:36:23 +0000 (16:36 +0200)]
build-cps niceties
* module/language/cps.scm (build-cps-exp, build-cont-body): Respect
unquote in list builders (kargs, call, callk, primcall, and values).
Andy Wingo [Thu, 3 Apr 2014 07:40:18 +0000 (09:40 +0200)]
Minor CSE optimization
* module/language/tree-il/cse.scm (cse): Use hashq instead of modulo to
convert a full-width hash value to a vector index.
Andy Wingo [Wed, 2 Apr 2014 14:25:07 +0000 (16:25 +0200)]
Add with-fresh-name-state-from-dfg
* module/language/cps/dfg.scm (with-fresh-name-state-from-dfg): New
helper.
($dfg, compute-dfg): Store max-var and max-label in the dfg.
* module/language/cps.scm (with-fresh-name-state): Don't raise an error
on recursive invocation; that was mostly useful when finding a bug.
* module/language/cps/arities.scm (fix-arities):
* module/language/cps/specialize-primcalls.scm (specialize-primcalls):
Use the new helper.
* .dir-locals.el: Update.
Andy Wingo [Wed, 2 Apr 2014 20:00:14 +0000 (22:00 +0200)]
(test-suite lib) uses plain old catch, not stack-catch
* test-suite/test-suite/lib.scm (run-test-exception): Refactor to just
use "catch" instead of stack-catch.
Andy Wingo [Wed, 2 Apr 2014 13:58:06 +0000 (15:58 +0200)]
Refactor toplevel scope name generation in compile-cps
* module/language/tree-il/compile-cps.scm (scope-counter, fresh-scope-id):
(toplevel-box, capture-toplevel-scope, convert, cps-convert/thunk):
Refactor to avoid abusing the var counter to generate scope
identifiers.
Andy Wingo [Wed, 2 Apr 2014 13:48:13 +0000 (15:48 +0200)]
compute-max-label-and-var takes letrec vars into account.
* module/language/cps.scm (compute-max-label-and-var): Fix to take
letrec vars into account.
Andy Wingo [Wed, 2 Apr 2014 13:41:14 +0000 (15:41 +0200)]
Fix DCE for refactor-introduced borkage
* module/language/cps/dce.scm ($fun-data, compute-live-code)
(process-eliminations): Fix clownshoes regarding fun-data field names
and order.
Andy Wingo [Wed, 2 Apr 2014 13:40:03 +0000 (15:40 +0200)]
Fix prune-top-level-scopes to allow collisions between var, scope, cont names
* module/language/cps/prune-top-level-scopes.scm (compute-referenced-scopes):
Fix to not assume that scope names, continuation names, and var names
are mutually unique.
(prune-top-level-scopes): Better variable names.
Andy Wingo [Wed, 2 Apr 2014 10:08:48 +0000 (12:08 +0200)]
Update old-style REPL code for deprecation
* module/ice-9/scm-style-repl.scm:
* module/ice-9/save-stack.scm: As the deprecated bindings have been
removed from the default environment, use #:export instead of
#:replace.
Andy Wingo [Wed, 2 Apr 2014 10:00:09 +0000 (12:00 +0200)]
Remove CFA data type
* module/language/cps/dfg.scm: Remove CFA data type.
(analyze-reverse-control-flow): Take min-label and label-count as
args, and return multiple values instead of returning a CFA object.
(compute-live-variables): Rework to accept multiple values from
analyze-reverse-control-flow.
($dfa): Update comments.
Andy Wingo [Wed, 2 Apr 2014 09:45:26 +0000 (11:45 +0200)]
$dfa includes CFA fields
* module/language/cps/dfg.scm ($dfa): Include CFA min-label, k-map, and
k-order inline.
(dfa-k-idx, dfa-k-sym, dfa-k-count): Adapt.
(compute-live-variables): Extract fields of CFA for make-dfa.
(print-dfa): Adapt (and fix positional record matching).
Andy Wingo [Wed, 2 Apr 2014 09:23:41 +0000 (11:23 +0200)]
More CFA removals
* module/language/cps/dfg.scm (compute-reachable): Reword docstring.
(visit-prompt-control-flow): Likewise.
($dominator-analysis): Change to store min-label instead of CFA.
(compute-idoms, compute-join-edges, mark-loop-body, identify-loops):
Take min-label and label-count, and use the DFG's preds list instead
of requiring a fresh renumbered one.
(analyze-dominators): Adapt to use a DFG with a label range instead of
a CFA.
Andy Wingo [Wed, 2 Apr 2014 09:04:04 +0000 (11:04 +0200)]
Simplify analyze-reverse-control-flow
* module/language/cps/dfg.scm (analyze-reverse-control-flow): Use the
DFG's label count and min label analysis instead of rolling our own.
Andy Wingo [Wed, 2 Apr 2014 09:01:39 +0000 (11:01 +0200)]
analyze-control-flow only used in reverse direction; make private
* module/language/cps/dfg.scm ($cfa): Use a vector to map labels to
indices. Don't export any CFA bindings.
(cfa-k-idx): Adapt.
(compute-reachable, find-prompts, compute-interval):
(find-prompt-bodies, visit-prompt-control-flow): Take a DFG as an
argument instead of a CFA.
(analyze-reverse-control-flow): Refactor from analyze-control-flow, as
it is only used in the reverse case. Simplify accordingly, inlining
the RPO sort.
(compute-live-variables): Adapt to call analyze-reverse-control-flow
instead.
Andy Wingo [Tue, 1 Apr 2014 18:55:31 +0000 (20:55 +0200)]
Fix DFG compute-reachable bug
* module/language/cps/dfg.scm (compute-reachable): Fix embarassing bug
where we wouldn't actually iterate to fixpoint. I haven't seen it
yet, but that's just luck...
Andy Wingo [Tue, 1 Apr 2014 18:52:15 +0000 (20:52 +0200)]
Optimize two-list srfi-1 map
* module/srfi/srfi-1.scm (map): Optimize the two-list variant.
Andy Wingo [Tue, 1 Apr 2014 16:20:02 +0000 (18:20 +0200)]
Speed up compute-label-and-var-ranges
* module/language/cps/dfg.scm (compute-label-and-var-ranges): Duplicate
the cont-folder cases in the global/not-global cases. Lets the
optimizer DTRT.
Andy Wingo [Tue, 1 Apr 2014 16:16:00 +0000 (18:16 +0200)]
Fix compute-label-and-var-ranges for global DFG computation
* module/language/cps/dfg.scm (compute-label-and-var-ranges): Fix to
work with global DFGs -- it wasn't taking $letrec into account for var
ranges.
* module/language/cps/dce.scm (compute-live-code): Use bitvectors to
represent the live var set.
Andy Wingo [Tue, 1 Apr 2014 15:51:26 +0000 (17:51 +0200)]
Renumber doesn't visit unreachable continuations
* module/language/cps/renumber.scm (compute-new-labels-and-vars): Don't
visit functions that are not reachable.
(renumber): Reindent.
Andy Wingo [Tue, 1 Apr 2014 14:47:11 +0000 (16:47 +0200)]
Renumber returns label/var counters for use in let-fresh
* module/language/cps/renumber.scm (renumber): Refactor to return the
label and var counters as additional values.
* module/language/cps/dce.scm (eliminate-dead-code): Use the renumber
label/var counters to initialize the fresh name state.
Andy Wingo [Tue, 1 Apr 2014 14:43:55 +0000 (16:43 +0200)]
Refactor DCE to not build a CFA
* module/language/cps/effects-analysis.scm (compute-effects): Change to
analyze the effects for a subrange of a DFG's continuations.
* module/language/cps/dce.scm (compute-defs, $fun-data, compute-live-code):
(process-eliminations, eliminate-dead-code): Renumber before
eliminating dead code, to avoid computing a CFG and other data.
Andy Wingo [Tue, 1 Apr 2014 13:56:45 +0000 (15:56 +0200)]
Simplification renumbers instead of local prune-continuation pass
* module/language/cps/simplify.scm (simplify): Use renumbering instead
of rolling our own prune-continuations pass.
Andy Wingo [Tue, 1 Apr 2014 13:42:12 +0000 (15:42 +0200)]
DFA uses DFG var numbering
* module/language/cps/dfg.scm ($dfa): Instead of a var-map table an a
syms vector, use the DFG's var numbering.
(dfa-var-idx, dfa-var-sym, compute-live-variables): Adapt.
Andy Wingo [Tue, 1 Apr 2014 13:21:28 +0000 (15:21 +0200)]
Allocate-slots avoids building CFA
* module/language/cps/slot-allocation.scm (allocate-slots): Rework to
avoid computing a CFA, and just relying on the incoming term to have
sorted labels.
Andy Wingo [Tue, 1 Apr 2014 10:42:09 +0000 (12:42 +0200)]
Compile-fun takes advantage of sorted output of "renumber", avoids CFA
* module/language/cps/dfg.scm ($dfg): Rename nvars and nlabels fields to
var-count and label-count. Export dfg-min-var, dfg-min-label,
dfg-label-count, dfg-var-count.
* module/language/cps/compile-bytecode.scm (compile-fun): No need to
build a CFA given the renumbering pass. Adapt to treat labels as
ordered small integer in a contiguous vector.
Andy Wingo [Tue, 1 Apr 2014 10:03:37 +0000 (12:03 +0200)]
CPS renumbering pass sorts conts in topological order
* module/language/cps/renumber.scm (sort-conts)
(compute-new-labels-and-vars): Rework to sort the labels in
topological order, and to prune any unreachable labels.
Andy Wingo [Tue, 1 Apr 2014 09:59:03 +0000 (11:59 +0200)]
Add visit-cont-successors helper
* module/language/cps/dfg.scm (lookup-successors, control-point?): Use
the new helper.
* module/language/cps.scm (visit-cont-successors): New helper.
Andy Wingo [Mon, 31 Mar 2014 16:08:11 +0000 (18:08 +0200)]
Fix analyze-control-flow to preserve order among unordered labels
* module/language/cps/dfg.scm (analyze-control-flow): Sort blocks to
preserve order among unordered successors.
(lookup-successors): Choose a more natural order, now that it doesn't
matter.
Andy Wingo [Mon, 31 Mar 2014 14:38:53 +0000 (16:38 +0200)]
Use Tree-IL-like case-lambda clause chaining in CPS
* module/language/cps.scm ($kclause, $kentry): Instead of having an
entry continuation contain a list of clauses, have the clauses contain
clauses (as in Tree-IL). In some ways it's not as convenient but it
does reflect the continuation tree correctly.
* module/language/cps/arities.scm:
* module/language/cps/closure-conversion.scm:
* module/language/cps/compile-bytecode.scm:
* module/language/cps/constructors.scm:
* module/language/cps/contification.scm:
* module/language/cps/dce.scm:
* module/language/cps/dfg.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/prune-top-level-scopes.scm:
* module/language/cps/reify-primitives.scm:
* module/language/cps/renumber.scm:
* module/language/cps/simplify.scm:
* module/language/cps/slot-allocation.scm:
* module/language/cps/specialize-primcalls.scm:
* module/language/cps/verify.scm:
* module/language/tree-il/compile-cps.scm: Adapt aaaaaaall users.
Andy Wingo [Mon, 31 Mar 2014 10:10:08 +0000 (12:10 +0200)]
Rewrite control-point? to avoid consing
* module/language/cps/dfg.scm (control-point?): Rewrite to avoid consing
a successors list.
Andy Wingo [Mon, 31 Mar 2014 10:09:46 +0000 (12:09 +0200)]
Remove succs from DFG
* module/language/cps/dfg.scm ($dfg): Remove "succs" from DFG. Instead
we can compute the successors set on-demand.
(lookup-successors): Adapt.
Andy Wingo [Sun, 30 Mar 2014 20:28:07 +0000 (22:28 +0200)]
Simplify boot-9 and srfi-1 map
* module/ice-9/boot-9.scm (map):
* module/srfi/srfi-1.scm (map): Simplify the implementations to check
for list? beforehand. It's faster, and it will be needed if we decide
to go recursive.
Andy Wingo [Sun, 30 Mar 2014 19:28:10 +0000 (21:28 +0200)]
Avoid consing in compute-label-and-var-ranges.
* module/language/cps/dfg.scm (compute-label-and-var-ranges): Avoid
consing.