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.
Andy Wingo [Sun, 30 Mar 2014 19:14:31 +0000 (21:14 +0200)]
Scope and scope-level in DFG vector
* module/language/cps/dfg.scm ($dfg): Hoist scopes and scope levels out
of $block and into $dfg. Adapt all callers.
Andy Wingo [Sun, 30 Mar 2014 18:55:57 +0000 (20:55 +0200)]
Predecessors and successors in DFG vectors
* module/language/cps/dfg.scm ($dfg, $block): Record predecessors and
successors in vectors instead of in $block data structures. Adapt
users.
Andy Wingo [Sun, 30 Mar 2014 18:27:31 +0000 (20:27 +0200)]
DFG refactor
* module/language/cps/dfg.scm (lookup-cont, lookup-block):
(lookup-def, constant-needs-allocation?): Rework these accessors to
avoid completely destructuring the $dfg.
Andy Wingo [Sun, 30 Mar 2014 17:31:07 +0000 (19:31 +0200)]
Renumber functions before emitting code
* module/language/cps/compile-bytecode.scm (compile-bytecode): Renumber
a function before going to compile it, so that the vars and labels are
contiguous within each function.
Andy Wingo [Sun, 30 Mar 2014 17:09:40 +0000 (19:09 +0200)]
Add renumber module
* module/language/cps/renumber.scm: New module.
* module/Makefile.am: Add to build.
fix renumber
Andy Wingo [Sun, 30 Mar 2014 09:48:47 +0000 (11:48 +0200)]
Replace use-map in DFG with separate def / use vectors
* module/language/cps/dfg.scm ($dfg, $use-map): Replace use-map vector
with "defs" and "uses" vectors. Adapt callers.
Andy Wingo [Sun, 30 Mar 2014 09:36:59 +0000 (11:36 +0200)]
Remove "sym" from $use-map
* module/language/cps/dfg.scm ($use-map): Remove "sym" from use-map;
it's redundant. Adapt callers.
Andy Wingo [Sun, 30 Mar 2014 09:25:23 +0000 (11:25 +0200)]
$use-map no longer has name member
* module/language/cps/dfg.scm ($use-map): Remove name member. Adapt
users.
Andy Wingo [Sun, 30 Mar 2014 09:23:51 +0000 (11:23 +0200)]
$dfa no longer includes name vector (can get that from dfg)
* module/language/cps/dfg.scm ($dfa, dfa-var-name):
(compute-live-variables, print-dfa): Remove "names" from DFAs.
Andy Wingo [Sun, 30 Mar 2014 09:14:45 +0000 (11:14 +0200)]
DFG stores conts, blocks, and use-maps in vectors
* module/language/cps/dfg.scm ($dfg): Change to store conts, blocks, and
use-maps as vectors. A DFG also records the minimum label, minimum
variable, and the number of labels and variables. The first entry in
one of these vectors corresponds to the minimum. This can be
optimum in the local case if the conts and variables have been renamed
appropriately.
Adapt callers.
(compute-live-variables): Adapt. This is currently suboptimal but it
works, so it's a useful base for optimization.
Andy Wingo [Sun, 30 Mar 2014 08:41:31 +0000 (10:41 +0200)]
lookup-cont takes a DFG as its argument
* module/language/cps/dfg.scm (lookup-cont): Change to take a DFG
instead of a cont table.
(build-cont-table): Change to return a vector.
* module/language/cps/arities.scm:
* module/language/cps/contification.scm:
* module/language/cps/dce.scm:
* module/language/cps/effects-analysis.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/reify-primitives.scm:
* module/language/cps/simplify.scm:
* module/language/cps/slot-allocation.scm: Adapt to lookup-cont and
build-cont-table changes.
Andy Wingo [Sat, 29 Mar 2014 06:56:08 +0000 (07:56 +0100)]
Public make-cont-folder
* module/language/cps.scm (make-cont-folder): Add global? parameter, and
make public.
(fold-conts): Adapt.
(fold-local-conts): Use make-cont-folder, and take a function instead
of a continuation.
* module/language/cps/arities.scm (fix-clause-arities, fix-arities*):
* module/language/cps/compile-bytecode.scm (collect-conts):
* module/language/cps/elide-values.scm (elide-values*): Adapt to
fold-local-conts change.
Andy Wingo [Fri, 28 Mar 2014 21:27:48 +0000 (22:27 +0100)]
Vars and labels are separate namespaces
* module/language/cps.scm (fresh-var, with-fresh-name-state): Vars have
their own namespace.
Andy Wingo [Fri, 28 Mar 2014 20:55:46 +0000 (21:55 +0100)]
Prepare for decoupling of var/label name uniqueness
* module/language/cps/simplify.scm (compute-beta-reductions):
(beta-reduce): Separate state into two tables, so we can relax current
guarantee that vars and labels are mutually unique.
Andy Wingo [Fri, 28 Mar 2014 20:32:26 +0000 (21:32 +0100)]
Update verify-cps
* module/language/cps/verify.scm (verify-cps): Vars should only be exact
integers now.
Andy Wingo [Fri, 28 Mar 2014 20:30:55 +0000 (21:30 +0100)]
CPS conversion renames incoming gensyms to small integers
* module/language/tree-il/compile-cps.scm (fold-formals)
(unbound?, init-default-value, convert): Arrange to rename incoming
gensyms as small integers.
(canonicalize): Convert vector and abort here too.
Andy Wingo [Fri, 28 Mar 2014 18:17:22 +0000 (19:17 +0100)]
Less copying in tree-il pre-order / post-order.
* module/language/tree-il.scm (pre-post-order): If the pre handler
doesn't modify the components of a tree-il expression, avoid copying a
new one.
Andy Wingo [Fri, 28 Mar 2014 16:51:37 +0000 (17:51 +0100)]
Prompt-related refactor in compile-cps
* module/language/tree-il/compile-cps.scm (fix-prompts): New procedure.
Eta-expand prompts before compiling to ensure that they have inline
handlers.
Andy Wingo [Fri, 28 Mar 2014 15:57:40 +0000 (16:57 +0100)]
DCE uses fresh-var instead of gensym
* module/language/cps/dce.scm (eliminate-dead-code): Use fresh-var
instead of gensym.
Andy Wingo [Fri, 28 Mar 2014 15:55:15 +0000 (16:55 +0100)]
Adapt verify-cps to CPS changes
* module/language/cps/verify.scm (verify-cps): Update to expect integer
labels, and to allow integer variables.
Andy Wingo [Fri, 28 Mar 2014 15:29:16 +0000 (16:29 +0100)]
Replace all let-gensyms uses with let-fresh
* .dir-locals.el: Add with-fresh-name-state.
* module/language/cps.scm (fresh-label, fresh-var): Signal an error if
the counters are not initialized.
(with-fresh-name-state): New macro.
(make-cont-folder): New macro, generates an n-ary folder.
(compute-max-label-and-var): New function, uses make-cont-folder.
(fold-conts): Use make-cont-folder.
(let-gensyms): Remove.
* module/language/cps/arities.scm:
* module/language/cps/closure-conversion.scm:
* module/language/cps/constructors.scm:
* module/language/cps/dce.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/reify-primitives.scm:
* module/language/cps/specialize-primcalls.scm: Use let-fresh instead of
let-gensyms, and wrap in a with-fresh-name-state as needed.
* module/language/tree-il/compile-cps.scm: Remove hack to avoid
importing let-gensyms from (language tree-il).
Andy Wingo [Fri, 28 Mar 2014 13:23:51 +0000 (14:23 +0100)]
Remove unneeded local exact-integer? definition
* module/system/vm/assembler.scm (link-debug): Remove unneeded
exact-integer? definition.
Andy Wingo [Fri, 28 Mar 2014 13:21:06 +0000 (14:21 +0100)]
Continuation labels and variable identifiers may be integers
* module/language/cps.scm (label-counter, var-counter): New parameters,
for producing fresh label and var names.
(fresh-label, fresh-var): New procedures.
(let-fresh): New macro, will replace let-gensyms.
(build-cps-term): Use let-fresh.
* module/language/tree-il/compile-cps.scm: Use let-fresh to generate
fresh names.
* module/system/vm/assembler.scm (make-meta, begin-kw-arity): Allow
exact integers as labels.
(link-debug): Explicitly mark low-pc as being an "addr" value.
Andy Wingo [Wed, 26 Mar 2014 09:47:40 +0000 (10:47 +0100)]
Sloppier matching in setitimer tests
* test-suite/tests/signals.test: Update setitimer tests to sloppily
match both times -- it seems that the interval can also be sloppy on
some platforms, sadly.
Andy Wingo [Wed, 26 Mar 2014 09:35:53 +0000 (10:35 +0100)]
Adapt test-out-of-memory to work on 32-bit systems
* test-suite/standalone/test-out-of-memory (*limit*): Reduce limit to 50 MB.
Adapt vector test to avoid exceeding maximum vector size on 32-bit
systems.
Andy Wingo [Sat, 22 Mar 2014 15:06:39 +0000 (16:06 +0100)]
Fix compile warnings
* libguile/throw.c (catch): Fix bad declarations.
* libguile/stackchk.c (reset_scm_stack_checking_enabled_p): Remove
unused static function.