bpt/guile.git
10 years agoTweak arities debugging representation
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 :/

10 years agoBeginnings of local variable information
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.

10 years agoRemove needless label remapping in slot-allocation
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.

10 years agoDFA datums don't rename their labels
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.

10 years agoBetter backtraces for optimized closures
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.

10 years agostatprof avoids mucking with VM trace levels when not counting calls
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.

10 years agoBetter state handling in statprof
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.

10 years agoOptimize make-stack
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.

10 years agoscm_c_make_frame takes struct scm_frame as arg
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.

10 years agoRefactor to frames code
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.

10 years agoOptimize make-global-cont-folder
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.

10 years agoImprove disassembly for optimized closures
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.

10 years agoRemove debugging code in closure-conversion
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.

10 years agoEval has no more free variables
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!

10 years agoClosure conversion eliminates self-references introduced by fixpoint
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.

10 years agoRefactor to closure-conversion
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.

10 years agoAvoid consing an unbound-arg marker in the evaluator
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.

10 years agoOptimize closures with one free variable
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.

10 years agoWell-known closures represented using pairs or vectors
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.

10 years agoUpdate verify-cps
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.

10 years agoAvoid creating closures with no free variables
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.

10 years agoHard-wire calls to known procedures
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.

10 years agoclosure conversion computes well-known functions
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.

10 years agoFirst-order CPS has $program and $closure forms
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.

10 years agoSeparate make-cont-folder into global and local variants
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.

10 years agoRoot higher-order CPS term is always $kfun $cont
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.

10 years agoClosure conversion, reify-primitives use $kfun $cont
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.

10 years agoPreparation for compile-bytecode to work on $kfun $conts
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.

10 years agocompute-dfg takes a $kfun $cont, not a $fun
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.

10 years agowith-fresh-name-state takes a cont, not a $fun
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.

10 years agoFunction defined by make-cont-folder takes a cont, not a $fun
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.

10 years agoRename $kentry to $kfun
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.

10 years agosrc and meta are fields of $kentry, not $fun
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.

10 years agoRemove tests for old Tree-IL CSE module
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:

10 years agoRemove obsolete comment in compile-bytecode.scm
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.

10 years agoNew pass to avoid free variable creation for self-recursion
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.

10 years agoCompile some standalone tests to bytecode
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.

10 years agoRemove old Tree-IL CSE pass
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?.

10 years agoFlow-sensitive analysis of truth values
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.

10 years agoAdd effects for specialized primitives
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.

10 years agoMinor cleanup/optimization in CSE
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.

10 years agoPrune bailouts after contification
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.

10 years agoMatch and srfi-9 expose their bailouts to the CSE pass
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.

10 years agoRemove &bailout; replace uses of &unknown-effects with &all-effects
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:

10 years agoRemove parts of CSE that deal with bailout
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.

10 years agoAdd prune-bailouts pass
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.

10 years agoDisable Tree-IL CSE
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.

10 years agoFix effects analysis for cached-module-box
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.

10 years agoFix coverage expectations
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.

10 years agoMore bailout preparation work
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.

10 years agoPrepare for CSE bailout propagation
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.

10 years agoAdd common subexpression elimination pass on CPS
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.

10 years agoEffects analysis tweaks
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.

10 years agoFix verify-cps to work
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.

10 years agoconstant-needs-allocation? fix
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.

10 years agoRemove variable-set! clause from compile-fun
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.

10 years agoEffects analysis: define causes-all-effects?
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.

10 years agobuild-cps niceties
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).

10 years agoMinor CSE optimization
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.

10 years agoAdd with-fresh-name-state-from-dfg
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.

10 years ago(test-suite lib) uses plain old catch, not stack-catch
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.

10 years agoRefactor toplevel scope name generation in compile-cps
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.

10 years agocompute-max-label-and-var takes letrec vars into account.
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.

10 years agoFix DCE for refactor-introduced borkage
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.

10 years agoFix prune-top-level-scopes to allow collisions between var, scope, cont names
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.

10 years agoUpdate old-style REPL code for deprecation
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.

10 years agoRemove CFA data type
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.

10 years ago$dfa includes CFA fields
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).

10 years agoMore CFA removals
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.

10 years agoSimplify analyze-reverse-control-flow
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.

10 years agoanalyze-control-flow only used in reverse direction; make private
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.

10 years agoFix DFG compute-reachable bug
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...

10 years agoOptimize two-list srfi-1 map
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.

10 years agoSpeed up compute-label-and-var-ranges
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.

10 years agoFix compute-label-and-var-ranges for global DFG computation
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.

10 years agoRenumber doesn't visit unreachable continuations
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.

10 years agoRenumber returns label/var counters for use in let-fresh
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.

10 years agoRefactor DCE to not build a CFA
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.

10 years agoSimplification renumbers instead of local prune-continuation pass
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.

10 years agoDFA uses DFG var numbering
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.

10 years agoAllocate-slots avoids building CFA
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.

10 years agoCompile-fun takes advantage of sorted output of "renumber", avoids CFA
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.

10 years agoCPS renumbering pass sorts conts in topological order
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.

10 years agoAdd visit-cont-successors helper
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.

10 years agoFix analyze-control-flow to preserve order among unordered labels
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.

10 years agoUse Tree-IL-like case-lambda clause chaining in CPS
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.

10 years agoRewrite control-point? to avoid consing
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.

10 years agoRemove succs from DFG
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.

10 years agoSimplify boot-9 and srfi-1 map
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.

10 years agoAvoid consing in compute-label-and-var-ranges.
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.

10 years agoScope and scope-level in DFG vector
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.

10 years agoPredecessors and successors in DFG vectors
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.

10 years agoDFG refactor
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.

10 years agoRenumber functions before emitting code
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.

10 years agoAdd renumber module
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

10 years agoReplace use-map in DFG with separate def / use vectors
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.

10 years agoRemove "sym" from $use-map
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.

10 years ago$use-map no longer has name member
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.

10 years ago$dfa no longer includes name vector (can get that from dfg)
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.

10 years agoDFG stores conts, blocks, and use-maps in vectors
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.