1
Fork 0
mirror of https://git.savannah.gnu.org/git/guile.git synced 2025-04-30 20:00:19 +02:00
Commit graph

20 commits

Author SHA1 Message Date
Andy Wingo
03998db647 Add new pass to optimize branch chains to table dispatch
* module/language/cps/switch.scm: New pass.

* module/Makefile.am (SOURCES):
* am/bootstrap.am (SOURCES): Add switch.scm.

* module/system/base/optimize.scm (available-optimizations):
* module/language/cps/optimize.scm (optimize-first-order-cps): Run
  switch optimization at level 2.

* libguile/hash.c (JENKINS_LOOKUP3_HASHWORD2): Add note regarding
  cross-compilation.

* module/language/cps/graphs.scm (intmap-select): New definition.
* module/language/cps/utils.scm (compute-singly-referenced-labels): Move
  here, from various places.  Doesn't take a body intset argument.

* module/language/cps/contification.scm:
* module/language/cps/closure-conversion.scm:
* module/language/cps/simplify.scm: Use compute-singly-referenced-labels
  from utils.

* module/language/cps/effects-analysis.scm (annotation->memory-kind*):
  (annotation->memory-kind): Add symbol annotation cases.
2020-08-12 23:30:08 +02:00
Andy Wingo
cd5ab6377b Add $switch CPS term kind
* module/language/cps.scm ($switch): New term.
* doc/ref/compiler.texi (CPS in Guile): Add documentation.

* module/language/cps.scm (build-term, parse-cps, unparse-cps)
* module/language/cps/closure-conversion.scm (compute-non-operator-uses)
  (compute-singly-referenced-labels, rewrite-shared-closure-calls)
  (compute-free-vars, convert-one)
* module/language/cps/compile-bytecode.scm (compile-function)
* module/language/cps/contification.scm (compute-singly-referenced-labels)
  (compute-contification-candidates, apply-contification)
* module/language/cps/cse.scm (compute-truthy-expressions)
  (forward-cont, term-successors, eliminate-common-subexpressions-in-fun)
* module/language/cps/dce.scm (compute-known-allocations)
  (compute-live-code, process-eliminations)
* module/language/cps/devirtualize-integers.scm (compute-use-counts)
  (peel-trace)
* module/language/cps/effects-analysis.scm (compute-effects)
* module/language/cps/licm.scm (hoist-one, hoist-in-loop)
* module/language/cps/loop-instrumentation.scm (compute-loop-headers)
* module/language/cps/peel-loops.scm (rename-cont)
* module/language/cps/renumber.scm (sort-labels-locally, renumber)
* module/language/cps/rotate-loops.scm (rotate-loop)
  (rotate-loops-in-function)
* module/language/cps/self-references.scm (resolve-self-references)
* module/language/cps/simplify.scm (compute-singly-referenced-vars)
  (eta-reduce, compute-singly-referenced-labels, beta-reduce)
* module/language/cps/slot-allocation.scm (compute-defs-and-uses)
  (add-prompt-control-flow-edges, compute-var-representations)
* module/language/cps/specialize-numbers.scm (compute-significant-bits)
* module/language/cps/split-rec.scm (compute-free-vars)
* module/language/cps/type-fold.scm (local-type-fold)
* module/language/cps/types.scm (successor-count, infer-types)
* module/language/cps/utils.scm (compute-function-body)
  (compute-successors, compute-predecessors)
* module/language/cps/verify.scm (compute-available-definitions)
  (check-valid-var-uses, check-arities): Add support for new term.
2020-08-12 23:30:08 +02:00
Andy Wingo
bba4ce222d Split graph utilities out of (language cps utils)
* module/language/cps/graphs.scm: New file.
* module/language/cps/utils.scm: Re-export functions from graphs.scm.
* am/bootstrap.am:
* module/Makefile.am: Add to build.
2019-08-13 12:53:10 +02:00
Andy Wingo
f6c07e4eb2 Add compiler support for eliding closure bindings
* module/language/cps/closure-conversion.scm (compute-elidable-closures):
  New function.
  (convert-one, convert-closures): Add ability to set "self" variable of
  $kfun to $f, hopefully avoiding passing that argument in some cases.
* module/language/cps/compile-bytecode.scm (compile-function): Pass the
  has-closure? bit on through to the assembler.
* module/system/vm/assembler.scm (begin-standard-arity)
  (begin-opt-arity, begin-kw-arity): Only reserve space for the closure
  as appropriate.
* module/language/cps/slot-allocation.scm (allocate-args)
  (compute-defs-and-uses, compute-needs-slot)
  (compute-var-representations): Allow for closure slot allocation
  differences.
* module/language/cps/cse.scm (compute-defs):
* module/language/cps/dce.scm (compute-live-code):
* module/language/cps/renumber.scm (renumber, compute-renaming):
(allocate-args):
* module/language/cps/specialize-numbers.scm (compute-significant-bits):
(compute-defs):
* module/language/cps/split-rec.scm (compute-free-vars):
* module/language/cps/types.scm (infer-types):
* module/language/cps/utils.scm (compute-max-label-and-var):
* module/language/cps/verify.scm (check-distinct-vars):
(compute-available-definitions): Allow closure to be #f.
2019-06-07 17:01:37 +02:00
Andy Wingo
39729e8448 Rename $closure to $const-fun
* module/language/cps.scm ($const-fun): Rename from $closure, as we
  always use this now with nfree == 0.
* module/language/cps/closure-conversion.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/devirtualize-integers.scm:
* module/language/cps/effects-analysis.scm:
* module/language/cps/licm.scm:
* module/language/cps/peel-loops.scm:
* module/language/cps/renumber.scm:
* module/language/cps/rotate-loops.scm:
* module/language/cps/simplify.scm:
* module/language/cps/slot-allocation.scm:
* module/language/cps/specialize-numbers.scm:
* module/language/cps/types.scm:
* module/language/cps/utils.scm:
* module/language/cps/verify.scm: Adapt users.
2018-10-03 22:58:45 +02:00
Andy Wingo
9f98b4a5b1 Add $code CPS expression type
* module/language/cps.scm ($code): New CPS type, for labels as values.
  Add cases to all CPS type dispatches.  $closure now indicates only
  statically allocated closures.
* module/language/cps/closure-conversion.scm (convert-one): Only reify
  $closure for statically allocated procedures.  Otherwise allocate an
  object using low-level primitives.
* module/language/cps/compile-bytecode.scm (compile-function): Remove
  make-closure case.
* module/language/cps/slot-allocation.scm (compute-var-representations):
  $code produces a u64 value.
* module/system/vm/assembler.scm: Remove make-closure export.
* module/language/cps/contification.scm:
* module/language/cps/cse.scm:
* module/language/cps/dce.scm:
* module/language/cps/devirtualize-integers.scm:
* module/language/cps/effects-analysis.scm:
* module/language/cps/licm.scm:
* module/language/cps/peel-loops.scm:
* module/language/cps/renumber.scm:
* module/language/cps/rotate-loops.scm:
* module/language/cps/simplify.scm:
* module/language/cps/specialize-numbers.scm:
* module/language/cps/types.scm:
* module/language/cps/utils.scm:
* module/language/cps/verify.scm: Add cases for $code.
2018-04-10 17:06:27 +02:00
Andy Wingo
ad55ee83c3 $throw is a new kind of CPS term
* module/language/cps.scm ($throw): New term type that doesn't have a
  continuation.  Adapt all callers.  Remove now-unneeded
  "prune-bailouts" pass.
2018-01-03 21:25:55 +01:00
Andy Wingo
ee15ca1455 $prompt is now its own kind of CPS term.
* module/language/cps.scm ($prompt): Rework to be its own term kind.
  Now $continue always continues to a single continuation.  Adapt
  callers.
2018-01-03 17:32:43 +01:00
Andy Wingo
afb0a92d50 $branch is now a distinct CPS term type
* module/language/cps.scm ($branch): Refactor to be its own CPS term
  type, not relying on $continue to specify a continuation (which before
  was only for the false case) or a source location.  Update allllllll
  callers.
2018-01-03 16:16:39 +01:00
Andy Wingo
3600dbf0cc Refactor to finish the primcalls-take-parameters work
* module/language/cps/compile-bytecode.scm (compile-function): Remove
  helper to look up constants now that primcalls can take parameters.
* module/language/cps/devirtualize-integers.scm (peel-trace): Remove
  extra argument to expression-effects.
* module/language/cps/effects-analysis.scm (constant?, indexed-field):
  Remove unused definitions.
  (expression-effects): Remove "constants" argument; constants come from
  primcall params.
  (compute-effects): Don't compute a constants table.
* module/language/cps/slot-allocation.scm ($allocation): Remove
  "constant-values" field.
  (lookup-constant-value, lookup-maybe-constant-value): Remove; unused.
  (allocate-slots): Don't create a constants table.
* module/language/cps/specialize-primcalls.scm
  (compute-defining-expressions, compute-constant-values): Move these
  definitions here, which were previously in utils.scm
* module/language/cps/utils.scm: Remove moved definitions.
2017-11-24 11:03:46 +01:00
Andy Wingo
6be04684e6 load-f64, etc take immediate parameters
* module/language/cps/compile-bytecode.scm (compile-function): Make
  load-f64, load-s64, and load-u64 take an immediate parameter instead
  of a CPS value.
* module/language/cps/effects-analysis.scm: Remove CPS argument from
  immediate load instructions.
* module/language/cps/slot-allocation.scm (compute-needs-slot): Remove
  special case for load-64 etc.
* module/language/cps/specialize-numbers.scm
  (specialize-u64-scm-comparison): Adapt.
* module/language/cps/specialize-primcalls.scm (specialize-primcalls):
  Adapt.
* module/language/cps/types.scm (define-type-inferrer*): Also take param
  argument.
  (define-type-inferrer, define-predicate-inferrer): Adapt.
  (define-type-inferrer/param): New helper.
  (load-f64, load-s64, load-u64): Adapt inferrers to pass on value from
  param.
* module/language/cps/utils.scm (compute-constant-values): Adapt.
2017-11-05 15:00:16 +01:00
Andy Wingo
c54c151eb6 $primcall has a "param" member
* module/language/cps.scm ($primcall): Add "param" member, which will be
  a constant parameter to the primcall.  The idea is that constants used
  by primcalls as immediates don't need to participate in optimizations
  in any way -- they should not participate in CSE, have the same
  lifetime as the primcall so not part of DCE either, and don't need
  slot allocation.  Indirecting them through a named $const binding is
  complication for no benefit.  This change should eventually improve
  compilation time and memory usage, once we fully take advantage of it,
  as the number of labels and variables will go down.
* 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/effects-analysis.scm:
* module/language/cps/elide-values.scm:
* module/language/cps/handle-interrupts.scm:
* module/language/cps/licm.scm:
* module/language/cps/peel-loops.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/rotate-loops.scm:
* module/language/cps/self-references.scm:
* module/language/cps/simplify.scm:
* module/language/cps/slot-allocation.scm:
* module/language/cps/specialize-numbers.scm:
* module/language/cps/specialize-primcalls.scm:
* module/language/cps/split-rec.scm:
* module/language/cps/type-checks.scm:
* module/language/cps/type-fold.scm:
* module/language/cps/types.scm:
* module/language/cps/utils.scm:
* module/language/cps/verify.scm:
* module/language/tree-il/compile-cps.scm: Adapt all users.
2017-11-05 15:00:16 +01:00
Andy Wingo
620b640a4e Fix bug in intmap-map
* module/language/cps/utils.scm (intmap-map): Use transient intmap-add!
  on an empty intmap to build the result instead of intmap-replace! on
  the argument.  Avoids spooky action-at-a-distance mutation of the
  argument if it happens to be a transient -- although the intmap-fold
  will correctly traverse a snapshot of the argument and the result will
  be correct, the argument value would be modified in place, causing
  strange results to calling code that passes in a transient.
2015-12-26 22:12:09 +01:00
Andy Wingo
3d6dd2f81c Add untagged bitwise operations
* libguile/vm-engine.c (ulogand, ulogior, ulogsub, ulsh, ursh)
  (scm->u64/truncate): New ops.
* module/language/cps/compile-bytecode.scm (compile-function):
* module/language/cps/effects-analysis.scm:
* module/language/cps/slot-allocation.scm (compute-var-representations):
* module/language/cps/specialize-primcalls.scm (specialize-primcalls):
* module/language/cps/types.scm:
* module/language/cps/utils.scm (compute-constant-values):
* module/system/vm/assembler.scm: Wire up support for the new ops.
2015-12-02 08:45:30 +01:00
Andy Wingo
a08b3d40f8 Untag values and indexes for all bytevector instructions
* libguile/vm-engine.c (bv-s8-ref, bv-s16-ref, bv-s32-ref, bv-s64-ref):
  Unbox index and return unboxed S32 value.
  (bv-s8-set!, bv-s16-set!, bv-s32-set!, bv-s64-set!): Unbox index and
  take unboxed S32 value.
  (bv-u8-ref, bv-u16-ref, bv-u32-ref, bv-u64-ref)
  (bv-s8-set!, bv-s16-set!, bv-s32-set!, bv-s64-set!): Likewise, but
  with unsigned values.
  (bv-f32-ref, bv-f32-set!, bv-f64-ref, bv-f64-set!): Use memcpy to
  access the value so we don't have to think about alignment.  GCC will
  inline this to a single instruction on architectures that support
  unaligned access.
* libguile/vm.c (vm_error_out_of_range_uint64)
  (vm_error_out_of_range_int64): New helpers.

* module/language/cps/slot-allocation.scm (compute-var-representations):
  All bytevector ref operations produce untagged values.

* module/language/cps/types.scm (define-bytevector-accessors): Update
  for bytevector untagged indices and values.

* module/language/cps/utils.scm (compute-constant-values): Fix s64
  case.

* module/language/tree-il/compile-cps.scm (convert): Box results of all
  bytevector accesses, and unbox incoming indices and values.
2015-12-01 15:42:24 +01:00
Andy Wingo
8bf77f7192 Add support for unboxed s64 values
* libguile/frames.c (enum stack_item_representation):
  (scm_to_stack_item_representation):
  (scm_frame_local_ref, scm_frame_local_set_x): Support for S64
  representations.

* libguile/frames.h (union scm_vm_stack_element): Add signed 64-bit
  integer field.

* libguile/vm-engine.c (scm->s64, s64->scm, load-s64): New
  instructions.

* module/language/cps/compile-bytecode.scm (compile-function):
* module/language/cps/cse.scm (compute-equivalent-subexpressions):
* module/language/cps/effects-analysis.scm:
* module/language/cps/slot-allocation.scm (compute-var-representations)
  (compute-needs-slot, allocate-slots):
* module/language/cps/utils.scm (compute-constant-values):
* module/language/cps/specialize-primcalls.scm (specialize-primcalls):
  Add support for new primcalls.

* module/language/cps/types.scm (&s64): New type.
  (&s64-min, &s64-max, &u64-max): New convenience definitions.
  (&range-min, &range-max): Use &s64-min and &u64-max names.
  (scm->s64, load-s64, s64->scm): Add support for new primcalls.

* module/system/vm/assembler.scm (emit-scm->s64, emit-s64->scm)
  (emit-load-s64): New exports.
* module/system/vm/assembler.scm (write-arities): Support for s64
  slots.

* module/system/vm/debug.scm (arity-definitions): Support for s64
  slots.
2015-12-01 15:42:19 +01:00
Andy Wingo
f34688ad25 New instructions load-f64, load-u64
* libguile/instructions.c (FOR_EACH_INSTRUCTION_WORD_TYPE): Add word
  types for immediate f64 and u64 values.
  (TYPE_WIDTH): Bump up by a bit, now that we have 32 word types.
  (NOP, parse_instruction): Use 64-bit meta type.

* libguile/vm-engine.c (load-f64, load-u64): New instructions.

* module/language/bytecode.scm (compute-instruction-arity): Add parser
  for new instruction word types.

* module/language/cps/compile-bytecode.scm (compile-function): Add
  special-cased assemblers for new instructions, and also for scm->u64
  and u64->scm which I missed before.

* module/language/cps/effects-analysis.scm (load-f64, load-u64): New
  instructions.

* module/language/cps/slot-allocation.scm (compute-needs-slot): load-f64
  and load-u64 don't need slots.
  (compute-var-representations): Update for new instructions.

* module/language/cps/specialize-primcalls.scm (specialize-primcalls):
  Specialize scm->f64 and scm->u64 to make-f64 and make-u64.

* module/language/cps/types.scm (load-f64, load-u64): Wire up to type
  inference, though currently type inference only runs before
  specialization.

* module/language/cps/utils.scm (compute-defining-expressions): For some
  reason I don't understand, it's possible to see two definitions that
  are equal but not equal? here.  Allow for now.
  (compute-constant-values): Punch through type conversions to get
  constant u64/f64 values.

* module/system/vm/assembler.scm (assembler): Support for new word
  types.  Export the new assemblers.
2015-12-01 11:30:55 +01:00
Andy Wingo
4792577ab8 solve-flow-equations tweak
* module/language/cps/utils.scm (solve-flow-equations): Revert to take
  separate in and out maps.  Take an optional initial worklist.

* module/language/cps/slot-allocation.scm: Adapt to solve-flow-equations
  change.
2015-07-27 13:25:38 +02:00
Andy Wingo
bebc70c8b1 Move solve-flow-equations to utils
* module/language/cps/slot-allocation.scm (compute-lazy-vars):
  (compute-live-variables):  Adapt to solve-flow-equations interface
  change.

* module/language/cps/utils.scm (solve-flow-equations): Move here.  Use
  an init value instead of an init map.
2015-07-24 11:40:00 +02:00
Andy Wingo
4aabc205cc Add missing files
Last commit meant to rename files, not delete them.  Whoops!
2015-07-22 18:27:37 +02:00