summaryrefslogtreecommitdiff
path: root/module/language/tree-il/fix-letrec.scm
AgeCommit message (Collapse)AuthorFilesLines
2025-01-22Optimize ordering edges in fix-letrecAndy Wingo1-2/+4
* module/language/tree-il/fix-letrec.scm (compute-sccs): Instead of depending on all previous complex bindings, we can just depend on the most recent one. Decreases the graph size.
2025-01-22Fix bad algorithmic growth in fix-letrecAndy Wingo1-153/+216
We were using list sets, which when you end up with thousands of bindings in an SCC reaches the point where we are off the quadratic end of the curve. Fix to use intsets and intmaps instead. * module/language/tree-il/fix-letrec.scm (compute-ids): New function. (compute-referenced-and-assigned): Rename from analyze-lexicals, and compute intsets. (make-compute-free-variables): Rename from free-variables, return a procedure instead of a hash table, and use intsets. Use a global cache to avoid quadratic behavior with regard to binding depth. (compute-complex): Compute a global set of "complex" variables, as an intset. (compute-sccs): Use intsets and intmaps to compute the free-variable and ordering edges. (fix-scc, fix-term): Refactorings. (reorder-bindings): Avoid a linear search. (fix-letrec): Refactor.
2023-06-19Excise use of `record-case`Andy Wingo1-24/+18
This macro expands to field accessors, which in the case of tree-il-src will force an eager conversion of the source info to alists.
2023-02-24Add 'record-case' to '.dir-locals.el'.Ludovic Courtès1-4/+0
* module/language/tree-il/fix-letrec.scm (fix-letrec): Remove "Local Variables" bit. * .dir-locals.el (scheme-mode): Add 'record-case'.
2021-04-21Optimize letrec* binding order in fix-letrecAndy Wingo1-3/+41
* module/language/tree-il/fix-letrec.scm (reorder-bindings): (fix-letrec): Reorder definitions so that lambdas tend to stick together, to avoid "complex" expressions interposing in lambda SCCs.
2019-08-18Add "mod" field to tree-il toplevel ref, set, defineAndy Wingo1-2/+2
Add "mod" field to <toplevel-ref>, <toplevel-set>, and <toplevel-define>, indicating the expander's idea of what the current module is when a toplevel variable is accessed or created. This will help in later optimizations. * libguile/expand.c (TOPLEVEL_REF, TOPLEVEL_SET, TOPLEVEL_DEFINE) (expand, expand_define, expand_set_x, convert_assignment): * libguile/expand.h (SCM_EXPANDED_TOPLEVEL_REF_FIELD_NAMES): (SCM_MAKE_EXPANDED_TOPLEVEL_REF, SCM_EXPANDED_TOPLEVEL_SET_FIELD_NAMES): (SCM_MAKE_EXPANDED_TOPLEVEL_SET, SCM_EXPANDED_TOPLEVEL_DEFINE_FIELD_NAMES): (SCM_MAKE_EXPANDED_TOPLEVEL_DEFINE): * module/ice-9/compile-psyntax.scm (translate-literal-syntax-objects): * module/ice-9/psyntax-pp.scm: * module/ice-9/psyntax.scm: * module/language/tree-il.scm: * module/language/tree-il.scm (parse-tree-il, make-tree-il-folder): (pre-post-order): * module/language/tree-il/analyze.scm (goops-toplevel-definition): (macro-use-before-definition-analysis, proc-ref?, format-analysis): * module/language/tree-il/compile-cps.scm (convert): * module/language/tree-il/debug.scm (verify-tree-il): * module/language/tree-il/effects.scm (make-effects-analyzer): * module/language/tree-il/fix-letrec.scm (free-variables): * module/language/tree-il/peval.scm (peval): * test-suite/tests/tree-il.test: Adapt uses.
2019-08-13Update peval tests for fix-letrecAndy Wingo1-1/+1
* module/language/tree-il/fix-letrec.scm (fix-scc): Initial binding of letrec values is unspecified, not false. * test-suite/tests/peval.test (pass-if-peval): Fix letrec before pevalling. Update tests. A couple got better, no regressions.
2019-08-13Implement "Fixing Letrec (reloaded)"Andy Wingo1-257/+229
* module/language/tree-il/fix-letrec.scm: Update algorithm to use approach from "Fixing Letrec (reloaded)", which sorts mutually recursive bindings by using Tarjan's algorithm to partition the bindings into strongly-connected components. The result is that users can use letrec* or internal definitions and get a result that is as efficient as manual placement of let / letrec.
2017-03-07psyntax: Generate identifiers in a deterministic fashion.Mark H Weaver1-2/+4
Fixes <http://bugs.gnu.org/20272>. * module/ice-9/boot-9.scm (module-generate-unique-id!) (module-gensym): New procedures. (module): Add 'next-unique-id' field. (the-root-module): Inherit 'next-unique-id' value from early stub. (make-module, make-autoload-interface): Adjust calls to module-constructor. * module/ice-9/psyntax.scm (gen-label, new-mark): Generate unique identifiers from the module name and the per-module unique-id. (build-lexical-var, generate-temporaries): Use 'module-gensym' instead of 'gensym'. * module/ice-9/psyntax-pp.scm: Regenerate. * module/language/tree-il/fix-letrec.scm (fix-letrec!): Use 'module-gensym' instead of 'gensym'. * module/system/base/syntax.scm (define-record): Likewise. (transform-record): Likewise. Co-authored-by: Ludovic Courtès <ludo@gnu.org>
2013-06-10Tree-il post-order rewriter no longer destructiveAndy Wingo1-4/+4
* module/language/tree-il.scm (pre-post-order): New helper, like pre-order! and post-order! but not destructive. (post-order): Implement in terms of pre-post-order, and rename from post-order!. * module/ice-9/compile-psyntax.scm (squeeze-tree-il): * module/language/tree-il/canonicalize.scm (canonicalize): * module/language/tree-il/fix-letrec.scm (fix-letrec): * module/language/tree-il/primitives.scm (resolve-primitives): Use post-order, and rename from the destructive variants (squeeze-tree-il!, canonicalize!, etc). Adapt callers. * test-suite/tests/tree-il.test (strip-source): Adapt to post-order. * test-suite/tests/cse.test: * test-suite/tests/peval.test: * module/language/tree-il/optimize.scm: Adapt callers.
2012-07-06Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo1-13/+23
Conflicts: libguile/expand.c libguile/hashtab.c libguile/ports.c libguile/vectors.c libguile/weaks.c module/language/ecmascript/compile-tree-il.scm module/language/tree-il/effects.scm module/language/tree-il/fix-letrec.scm module/language/tree-il/peval.scm test-suite/tests/peval.test
2012-07-05fix-letrec uses effects.scm for effects analysisAndy Wingo1-12/+22
* module/language/tree-il/fix-letrec.scm: Use effects.scm for effects analysis, instead of primitives.scm. (simple-expression?, partition-vars): Adapt.
2012-05-21Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo1-4/+24
Conflicts: module/language/tree-il/analyze.scm module/language/tree-il/effects.scm module/language/tree-il/fix-letrec.scm module/language/tree-il/peval.scm test-suite/tests/cse.test test-suite/tests/peval.test
2012-05-15fix-letrec tweakAndy Wingo1-4/+18
* module/language/tree-il/fix-letrec.scm (make-sequence*, fix-letrec!): When turning unreferenced bindings into sequences, don't bother emitting trivially constant expressions in effect position.
2012-01-10Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo1-1/+1
Conflicts: libguile/__scm.h libguile/array-map.c libguile/procprop.c libguile/tags.h module/ice-9/deprecated.scm module/ice-9/psyntax-pp.scm module/ice-9/psyntax.scm test-suite/standalone/test-num2integral.c test-suite/tests/regexp.test
2012-01-05Placate a number of `syntax-check' verifications.Ludovic Courtès1-1/+1
- "filesystem" -> "file system" - remove doubled words - use EXIT_* macros instead of literal numbers - update `syntax-check' exclusion files
2011-06-02sequence of expressions -> seq of head and tailAndy Wingo1-7/+7
* libguile/expand.h: * module/language/tree-il.scm: Rename "sequence" to "seq", and instead of taking a list of expressions, take a head and a tail. * module/language/tree-il/analyze.scm: * module/language/tree-il/compile-glil.scm: * module/language/tree-il/fix-letrec.scm: * module/language/tree-il/spec.scm: * module/language/elisp/compile-tree-il.scm: * module/ice-9/psyntax.scm: * module/ice-9/psyntax-pp.scm: * module/ice-9/eval.scm: * libguile/memoize.h: * libguile/memoize.c: * libguile/expand.c: * libguile/eval.c: Adapt to the new seq format.
2011-06-02add <primcall> to tree-ilAndy Wingo1-3/+2
* libguile/expand.c: * libguile/expand.h (SCM_EXPANDED_PRIMCALL_TYPE_NAME): (SCM_EXPANDED_PRIMCALL_FIELD_NAMES): (SCM_EXPANDED_PRIMCALL_SRC): (SCM_EXPANDED_PRIMCALL_NAME): (SCM_EXPANDED_PRIMCALL_ARGS): (SCM_MAKE_EXPANDED_PRIMCALL): Add "primcall" Tree-IL type. * doc/ref/compiler.texi (Tree-IL): Update docs. * libguile/memoize.c (memoize): Memoizer for primcalls. * module/ice-9/psyntax.scm: Build primcalls, sometimes. Also change build-primref to just make a primitive-ref. * module/language/tree-il.scm: Add primcall to the exports, parsers, serializers, etc. * module/language/tree-il/analyze.scm: * module/language/tree-il/compile-glil.scm: * module/language/tree-il/fix-letrec.scm: * module/language/tree-il/inline.scm: * module/language/tree-il/primitives.scm: * module/language/elisp/compile-tree-il.scm: Add primcall support. * test-suite/tests/tree-il.test: Use primcalls sometimes.
2011-06-02rename <application> to <call>Andy Wingo1-1/+1
* doc/ref/compiler.texi (The Scheme Compiler): Update docs. * libguile/expand.h: * libguile/expand.c: * module/language/tree-il.scm: Rename <application> to <call>. Change the external representation from (apply proc arg ...) to (call proc arg ...). * libguile/memoize.c: * module/ice-9/psyntax-pp.scm: * module/ice-9/psyntax.scm: * module/language/brainfuck/compile-tree-il.scm: * module/language/ecmascript/compile-tree-il.scm: * module/language/elisp/compile-tree-il.scm: * module/language/tree-il/analyze.scm: * module/language/tree-il/compile-glil.scm: * module/language/tree-il/fix-letrec.scm: * module/language/tree-il/inline.scm: * module/language/tree-il/primitives.scm: * test-suite/tests/tree-il.test: Update all callers.
2011-03-09fix-letrec tweaksAndy Wingo1-81/+68
* module/language/tree-il/fix-letrec.scm (partition-vars): Previously, for letrec* we treated all unreferenced vars as complex, because of orderings of effects that could arise in their definitions. But we can actually keep simple and lambda vars as unreferenced, as their initializers cannot cause side effects. (fix-letrec!): Remove letrec* -> letrec code, as it's unneeded.
2011-03-06Handle `letrec*' like `letrec' in simple cases.Ludovic Courtès1-59/+82
* module/language/tree-il/fix-letrec.scm (fix-letrec!): When X is a `letrec*' with only lambdas and simple expressions, analyze it as if it were a `letrec'. * test-suite/tests/tree-il.test ("letrec"): Add test for `(letrec* (x y) (xx yy) ((const 1) (const 2)) (lexical y yy))'.
2011-01-23Remove unexpected non-ASCII character.Ludovic Courtès1-1/+1
* module/language/tree-il/fix-letrec.scm: Replace U+2019 with an ASCII quote. The iconv implementation on FreeBSD would immediately notice and bail out when reading it under a US-ASCII locale.
2010-06-17compiler support for letrec*Andy Wingo1-34/+66
* test-suite/tests/tree-il.test ("letrec"): Add some tests. * module/language/tree-il/compile-glil.scm (flatten): Add support for compiling letrec* in its unoptimized form. * module/language/tree-il/fix-letrec.scm (simple-expression?): Parameterize, so that letrec* will not treat `(car x)' as primitive (because it could raise an exception). (partition-vars): Lump unreferenced vars in with complex vars, when compiling letrec*. (fix-letrec!): No need to evaluate inits within a let for letrec*.
2010-06-11comment in fix-letrecAndy Wingo1-0/+1
* module/language/tree-il/fix-letrec.scm (simple-expression?): Add a small FIXME.
2010-05-02rename `vars' field in tree-il binding constructs to `gensyms'Andy Wingo1-40/+40
* module/language/tree-il.scm (<tree-il>): Rename `vars' fields of <let>, <letrec>, <fix>, and <lambda-case> to `gensyms'. For clarity, and to match <lexical-ref>. * module/language/tree-il.scm: * module/language/tree-il/analyze.scm: * module/language/tree-il/compile-glil.scm: * module/language/tree-il/fix-letrec.scm: * module/language/tree-il/inline.scm: Update all callers.
2009-12-11rename <conditional> then and else to consequent and alternateAndy Wingo1-3/+3
* module/language/tree-il.scm (<tree-il>): Rename the "then" and "else" clauses of <conditional> to "consequent" and "alternate". More verbose, yes, but that way we avoid unexpected behavior with "else". (parse-tree-il, unparse-tree-il, tree-il->scheme, tree-il-fold): (make-tree-il-folder, post-order!, pre-order!) * module/language/tree-il/analyze.scm (analyze-lexicals): * module/language/tree-il/compile-glil.scm (flatten): * module/language/tree-il/fix-letrec.scm (simple-expression?): Update callers.
2009-08-12"fix" <let>-bound lambda expressions tooAndy Wingo1-1/+61
* module/language/tree-il/compile-glil.scm (compile-glil): Compute warnings before optimizing, as unreferenced variables will be optimized out. * libguile/_scm.h: Fix C99 comment. * module/language/tree-il/fix-letrec.scm (partition-vars): Also analyze let-bound vars. (fix-letrec!): Fix a bug whereby a set! to an unreffed var would be called for value, not effect. Also "fix" <let>-bound lambda expressions -- really speeds up pmatch. * test-suite/tests/tree-il.test ("lexical sets", "the or hack"): Update to take into account the new optimizations.
2009-08-06actually implement "fixing letrec"Andy Wingo1-1/+152
* module/Makefile.am (SOURCES): Reorganize so GHIL is compiled last, along with ecmascript. * module/language/scheme/spec.scm: Remove references to GHIL, as it's bitrotten and obsolete.. * module/language/tree-il.scm (make-tree-il-folder): Rework so that we only have down and up procs, and call down and up on each element. * module/language/tree-il/analyze.scm (analyze-lexicals): Fix a thinko handling let-values. * module/language/tree-il/fix-letrec.scm: Actually implement fixing letrec. The resulting code will perform better, but violations of the letrec restriction are not detected. This behavior is allowed by the spec, but it is undesirable. Perhaps that will be fixed later. * module/language/tree-il/inline.scm (inline!): Fix a case in which ((lambda args foo)) would be erroneously inlined to foo. Remove empty let, letrec, and fix statements. * module/language/tree-il/primitives.scm (effect-free-primitive?): New public predicate.
2009-08-05add <fix> tree-il construct, and compile itAndy Wingo1-0/+29
* libguile/vm-i-system.c (fix-closure): New instruction, for wiring together fixpoint procedures. * module/Makefile.am (TREE_IL_LANG_SOURCES): Add fix-letrec.scm. * module/language/glil/compile-assembly.scm (glil->assembly): Reindent the <glil-lexical> case, and handle 'fix for locally-bound vars. * module/language/tree-il.scm (<fix>): Add the <fix> tree-il type and accessors, for fixed-point bindings. This IL construct is taken from the Waddell paper. (parse-tree-il, unparse-tree-il, tree-il->scheme, tree-il-fold) (pre-order!, post-order!): Update for <fix>. * module/language/tree-il/analyze.scm (analyze-lexicals): Update for <fix>. The difference here is that the bindings may not be assigned, and are not marked as such. They are not boxed. (report-unused-variables): Update for <fix>. * module/language/tree-il/compile-glil.scm (flatten): Compile <fix> to GLIL. * module/language/tree-il/fix-letrec.scm: A stub implementation of fixing letrec -- will flesh out in a separate commit. * module/language/tree-il/inline.scm: Fix license, it was mistakenly added with LGPL v2.1+. * module/language/tree-il/optimize.scm (optimize!): Run the fix-letrec! pass.