summaryrefslogtreecommitdiff
path: root/module/language/tree-il/optimize.scm
AgeCommit message (Collapse)AuthorFilesLines
2024-04-23Tree-IL lowerer has #:dump-optimized-tree-il? optionAndy Wingo1-4/+19
* module/language/tree-il/optimize.scm (make-optimizer): If the keyword argument #:dump-optimized-tree-il? is present, print the Tree-IL that will be handed to the next compiler. Also re-enable #:verify-tree-il?.
2024-03-13New optimization: demux-lambdaAndy Wingo1-1/+3
Can help reduce case-lambda* / lambda* at Tree-IL optimization-time. * module/language/tree-il/demux-lambda.scm: New file. * am/bootstrap.am (SOURCES): Add new file. * module/language/tree-il/optimize.scm (make-optimizer): * module/system/base/optimize.scm (available-optimizations): Enable demux-lambda at level 2.
2021-05-11Implement cross-module inliningAndy Wingo1-1/+2
* module/language/tree-il/optimize.scm (make-optimizer): Pass cross-module-inlining? to peval. * module/language/tree-il/peval.scm (peval): Add cross-module-inlining? kwarg. Try to inline public module-ref.
2021-05-11Add support for recording inlinable module exportsAndy Wingo1-2/+4
* module/language/tree-il/inlinable-exports.scm: New module. * am/bootstrap.am: * module/Makefile.am: * module/language/tree-il/optimize.scm (make-optimizer): * module/system/base/optimize.scm (available-optimizations): Wire up new module. * module/ice-9/boot-9.scm (module): Add inlinable-exports field. (define-module*): Add #:inlinable-exports kwarg.
2021-05-11Add pass to resolve free toplevel references in declarative modulesAndy Wingo1-0/+2
* am/bootstrap.am (SOURCES): * module/Makefile.am (SOURCES): * module/language/tree-il/optimize.scm (make-optimizer): Wire up the new pass. * module/language/tree-il/resolve-free-vars.scm: New pass. * module/system/base/optimize.scm (available-optimizations): Enable new pass at -O1.
2020-05-31Fix bug where private bindings would never be sealedAndy Wingo1-1/+1
* module/language/tree-il/optimize.scm (make-optimizer): Fix plumbing of -Oseal-private-bindings / -O3.
2020-05-14Tree-IL lowerer only loads needed optimizationsAndy Wingo1-37/+39
* module/language/tree-il/optimize.scm (make-optimizer): New procedure, to compute an optimizer given options, lazily loading optimization modules. (optimize): Use make-optimizer. (make-lowerer): Use make-optimizer, so as to only load needed optimizations. Speeds up bootstrap times.
2020-05-13Fix optimizers after language lowerer refactorAndy Wingo1-13/+12
* module/language/cps/optimize.scm (define-optimizer): (optimize-higher-order-cps, optimize-first-order-cps): (make-cps-lowerer): * module/language/tree-il/optimize.scm (optimize, make-lowerer): In an embarrassing bug, after parsing optimization arguments, we were aconsing them instead of the expected cons*. This meant the bootstrap was running all Tree-IL optimizations! Change to have optimizers not have defaults and use alists after parsing.
2020-05-11Avoid having "guild compile" load optimizersAndy Wingo1-15/+2
* module/language/cps/optimize.scm (cps-optimizations): * module/language/tree-il/optimize.scm (tree-il-optimizations): * module/system/base/optimize.scm (available-optimizations): Invert the dependency tree to hold the names and default optimization levels in a central place instead of in the optimizers. It moves definitions farther from uses, but it avoids us having to load the CPS optimizer if we don't need it, which improves bootstrap times.
2020-05-11Declare #:cps? as an available optimizationAndy Wingo1-1/+2
* module/language/tree-il/optimize.scm (tree-il-optimizations): Add #:cps?, on by default from -O1. This enables "guild compile -O2 -Ono-cps foo.scm".
2020-05-08Define new "lowering" phase in compilerAndy Wingo1-0/+12
* module/language/cps/compile-bytecode.scm (compile-bytecode): * module/language/tree-il/compile-bytecode.scm (compile-bytecode): * module/language/tree-il/compile-cps.scm (compile-cps): Rely on compiler to lower incoming term already. * module/language/tree-il/optimize.scm (make-lowerer): New procedure. * module/system/base/compile.scm (compute-lowerer): New procedure, replaceing add-default-optimizations. (compute-compiler): Lower before running compiler. * module/system/base/language.scm (<language>): Change optimizations-for-level field to "lowerer". * module/scripts/compile.scm (%options, compile): Parse -O0, -O1 and so on to #:optimization-level instead of expanding to all the optimization flags. * module/language/cps/optimize.scm (lower-cps): Move here from compile-bytecode.scm. (make-cps-lowerer): New function. * module/language/cps/spec.scm (cps): Declare lowerer.
2020-01-15Add eta-expansion pass after pevalAndy Wingo1-2/+5
* am/bootstrap.am (SOURCES): * module/Makefile.am (SOURCES): Add eta-expand.scm. * module/language/tree-il/eta-expand.scm: New file. * module/language/tree-il/optimize.scm (optimize) (tree-il-optimizations): Add eta-expansion at level 2.
2019-08-28At optimization level -O3, seal declarative module-private bindingsAndy Wingo1-1/+5
* module/language/tree-il/letrectify.scm (compute-private-toplevels): New function; computes the subset of declarative bindings that are private to a module. If the module exports a macro, all bindings are public, as we have no way to know what binding might be exported. (letrectify): Add #:seal-private-bindings? keyword arg. If true, avoid making boxes for private definitions. * module/language/tree-il/optimize.scm (optimize): Add -Oseal-private-bindings, enabled at -O3.
2019-08-25Letrectify only on -O2; update docsAndy Wingo1-1/+6
* doc/ref/api-evaluation.texi (Compilation): Document the -O options. * doc/ref/api-modules.texi (Using Guile Modules): @@ docs refer to declarative modules. (Creating Guile Modules): Use when for 1-armed if. (Declarative Modules): Make implications of declarative bindings more explicit, and explicitly document ways to disable the optimization. * module/language/tree-il/optimize.scm (tree-il-optimizations): Punt letrectification to -O2.
2019-08-18Enable letrectificationAndy Wingo1-4/+7
* module/language/tree-il/optimize.scm: Enable letrectification at -O1 and higher.
2019-08-13Run fix-letrec before pevalAndy Wingo1-3/+2
* module/language/tree-il/optimize.scm (optimize): Change to run fix-letrec before peval. Also, run it unconditionally, so that later passes don't have to deal with letrec. * module/language/tree-il/peval.scm (build-var-table, peval): Remove letrec cases.
2018-01-05Disable resolve-primitives pass below -O2Andy Wingo1-9/+23
* module/language/tree-il/optimize.scm (optimize): Disable resolve-primitives below -O2. This is because compile-cps is going to start expanding all primcalls it sees.
2018-01-05Add (system base optimize) moduleAndy Wingo1-4/+10
* module/system/base/optimize.scm: New module. * module/Makefile.am (SOURCES): * am/bootstrap.am (SOURCES): Add new module. * module/language/tree-il/optimize.scm (tree-il-optimizations): Rename from tree-il-default-optimization-options. Directly specify the optimization level at which a pass should be enabled. * module/language/cps/optimize.scm (cps-optimizations): Likewise, rename from cps-default-optimization-options. * module/scripts/compile.scm (%options, show-optimization-help): Adapt to use new module.
2015-10-22Wire up `guild compile -O0 foo.scm'Andy Wingo1-2/+6
* module/scripts/compile.scm (%options): Resurrect -O option and make it follow GCC, more or less. The default is equivalent to -O2. * module/language/cps/compile-bytecode.scm (lower-cps): * module/language/cps/optimize.scm (optimize-higher-order-cps): Move split-rec to run unconditionally for now, as closure conversion fails without it. (define-optimizer): Only verify the result if we are debugging, to save time. (cps-default-optimization-options): New exported procedure. * module/language/tree-il/optimize.scm (tree-il-default-optimization-options): New exported procedure.
2014-04-06Remove old Tree-IL CSE passAndy Wingo1-12/+3
* 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?.
2014-04-05Disable Tree-IL CSEAndy Wingo1-5/+6
* module/language/tree-il/optimize.scm (optimize): Disable Tree-IL CSE by default.
2013-06-10Pre-order tree-il rewrites are now non-destructiveAndy Wingo1-3/+3
* module/language/tree-il.scm (pre-order): Re-implement in terms of pre-post-order, and rename from pre-order!. * module/language/tree-il/primitives.scm (expand-primitives): Adapt to pre-order change, and rename from expand-primitives!. * module/language/tree-il/optimize.scm (optimize): Adapt to expand-primitives! change, and rename from optimize!. * module/language/tree-il/compile-glil.scm: * module/system/repl/common.scm: * test-suite/tests/cse.test: * test-suite/tests/peval.test: * test-suite/tests/tree-il.test: Adapt to expand-primitives and optimize changes.
2013-06-10Tree-il post-order rewriter no longer destructiveAndy Wingo1-3/+3
* 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-04-23enable cseAndy Wingo1-4/+12
* module/language/tree-il/optimize.scm: Enable CSE unless #:cse? #f is passed. * test-suite/tests/tree-il.test: Disable CSE for one test.
2011-10-07optimizer verifies its outputAndy Wingo1-2/+4
* module/language/tree-il/optimize.scm: Verify the result of partial evaluation.
2011-09-28separate peval and a new canonicalization pass into their own modulesAndy Wingo1-962/+2
* module/language/tree-il/peval.scm: Move to its own file. Remove the bits about <prompt> thunk-application bodies, as they are not optimizations, simply expectations of the compiler. `canonicalize' handles that now. * module/language/tree-il/optimize.scm: Use peval from its module. Don't call `inline!', as that's useless now. * module/language/tree-il/canonicalize.scm: New file, implementing a pass that `compile-tree-il' runs on the result from the optimizer. The compiler currently expects a <let> form to have bindings, for example, and this pass turns a <let> without bindings into its body. * module/language/tree-il/inline.scm: Deprecate, as `peval' does everything this function ever did. * module/language/tree-il/compile-glil.scm: Canonicalize after optimizing. This should allow us to skip the optimizer entirely, if we want. * module/Makefile.am: Update and reorder a little bit.
2011-09-28((lambda ...) ...) fixAndy Wingo1-2/+5
* module/language/tree-il/optimize.scm (peval): If it's a lambda in the operator position, inline without a nested counter, as it's not possible to increase code size.
2011-09-28peval: more effective binding pruningAndy Wingo1-29/+37
* module/language/tree-il/optimize.scm (peval): Factor prune-bindings out of `let' and company. Have it process unreferenced bindings in effect context instead of always residualizing non-constant expressions.
2011-09-28don't propagate pure primcalls that might not type-checkAndy Wingo1-1/+16
* module/language/tree-il/optimize.scm (types-check?): New helper, to determine if a primcall will apply without throwing an exception. (peval): constant-expression? returns #f for expressions that don't types-check?. Effect-free primitives that type-check are void.
2011-09-28peval works on all expressionsAndy Wingo1-499/+462
* module/language/tree-il/optimize.scm (alpha-rename, peval): Add <dynset> cases. Allow any kind of <application>. Remove the `catch' wrapper as now peval handles all kinds of expressions.
2011-09-28peval: elide make-prompt-tag in effect contextAndy Wingo1-3/+7
* module/language/tree-il/optimize.scm (peval): Fix a duplicate traversal for constructors in effect or test context. Add support for eliding make-prompt-tag. * test-suite/tests/tree-il.test ("partial evaluation"): Update the test for make-prompt-tag elision.
2011-09-28peval: add support for <prompt> and <abort>Andy Wingo1-2/+65
* module/language/tree-il/optimize.scm (alpha-rename, peval): Handle <prompt> and <abort>. Attempt to remove the prompt if the tag is otherwise unreferenced. * module/language/tree-il/primitives.scm (*primitive-constructors*): Add make-prompt-tag as a constructor. * test-suite/tests/tree-il.test ("partial evaluation"): Add a test that an prompt whose tag is unreferenced is removed.
2011-09-28peval: fix algorithmic behavior of `cons'Andy Wingo1-11/+12
* module/language/tree-il/optimize.scm (peval): Fix treatment of `cons' to not process the value twice, leading to n^2 work. This prevented primitives.scm from compiling in a reasonable amount of time, because it contained a `(foo ... ,@bar) form that resulted in a long sequence of nested conses, and no effort counter was in place as it was not within an inlining attempt.
2011-09-27peval: more strict accountingAndy Wingo1-30/+61
* module/language/tree-il/optimize.scm (transfer!, make-nested-counter): (make-recursive-counter, peval): Limit the algorithm's time to be strictly O(N) by transferring effort and size counters of recursive inlining attempts from containing counters. * test-suite/tests/tree-il.test ("partial evaluation"): Update expectations for the ((lambda (x) (x x)) (lambda (x) (x x))) case, as the new accounting policy will cause the entire inlining attempt to abort.
2011-09-26peval: fix inlining of lambda* with #:optionalAndy Wingo1-8/+2
* module/language/tree-il/optimize.scm (peval): Fix calculation of how many init expressions to drop when inlining lambdas. * test-suite/tests/tree-il.test ("partial evaluation"): Add tests.
2011-09-26remove unused peval helpersAndy Wingo1-11/+0
* module/language/tree-il/optimize.scm (peval): Remove a couple unused helpers.
2011-09-25peval: simpler and more precise treatment of mutabilityAndy Wingo1-70/+89
* module/language/tree-il/optimize.scm (peval): The old approach of optimistically producing constants and then de-constifying them at their uses was not only cumbersome but incorrect: it both failed to preserve identity in some cases and failed to retain immutable constant values. Instead, now we only produce constants if they really are constant and immutable. The constant folder has to have a few more algebraic cases to be as effective as it was, to destructure (car (cons _ _)) appropriately. On the plus side, now constructors and deconstructors can handle impure cases more generally. * test-suite/tests/tree-il.test ("partial evaluation"): Add constructor and destructuring tests. Adapt other tests to new expectations.
2011-09-25peval: add a bunch of missing maybe-unconst callsAndy Wingo1-9/+10
* module/language/tree-il/optimize.scm (peval): Add missing maybe-unconst calls. Things are getting ugly. They will get better in the next commit though.
2011-09-25peval uses effort counters, propagates lambdas more effectivelyAndy Wingo1-160/+207
* module/language/tree-il/optimize.scm (code-contains-calls?): Remove this helper, we will deal with recursion when it happens, not after the fact. (peval): Add keyword args for various size and effort limits. Instead of keeping a call stack, keep a chain of <counter> records, each with an abort continuation. If ever an inlining attempt is taking too long, measured in terms of number of trips through the main loop, the counter will abort. Add new contexts, `operator' and `operand'. They have different default size limits. In the future we should actually use the size counter, instead of these heuristics. The <lexical-ref> case is smarter now, and tries to avoid propagating too much data. Perhaps it should be dumber though, and use a counter. That would require changes to the environment structure. Inline <lambda> applications to <let>, so that we allow residual lexical references to have bindings. Add a `for-operand' helper, and use it for the RHS of `let' expressions. A `let' is an inlined `lambda'. `Let' and company no longer elide bindings if the result is a constant, as the arguments could have effects. Peval will still do as much as it can, though. * test-suite/tests/tree-il.test ("partial evaluation"): Update the tests for the new expectations. They are uniformly awesomer, with the exception of two cases in which pure but not constant data is not propagated.
2011-09-24prune unused letrec bindingsAndy Wingo1-1/+12
* module/language/tree-il/optimize.scm (peval): Prune unused `letrec' bindings.
2011-09-24more peval refactoringAndy Wingo1-7/+17
* module/language/tree-il/optimize.scm (peval): Rename `var-table' to `store', as we're going to put some more things in it. Rename `record-lexical-bindings' to `record-source-expression', which also takes the original, pre-renaming expression. Keep a mapping from new expressions to original expressions, available using the `source-expression' helper.
2011-09-24add helpers for effort countersAndy Wingo1-0/+55
* module/language/tree-il/optimize.scm (<counter>, abort-counter) (record-effort!, record-size!, find-counter, make-top-counter) (make-nested-counter, make-recursive-counter): New helpers, as yet unused, but which will implement fixed effort bounds on the inlining algorithm.
2011-09-24peval refactorAndy Wingo1-46/+48
* module/language/tree-il/optimize.scm (peval): Add for-value, for-test, for-effect, and for-tail helpers. Use them.
2011-09-24attempt to prune unreferenced bindingsAndy Wingo1-26/+62
* module/language/tree-il/optimize.scm (peval): Rename `record-lexicals' to `record-lexical-bindings'. Record residualized lexical references. Record lexical references in maybe-unlambda. Unfortunately this has the disadvantage that the speculative mapping of lambda expressions to lexical references records that reference, even if we are not going to residualize it. After processing a `let', prune pure unreferenced bindings. (We can do better than this in the future: we can simply process them for effect.) * test-suite/tests/tree-il.test (pass-if-peval): More debugging. ("partial evaluation"): Update to reflect the fact that the `y' binding won't be emitted.
2011-09-24peval handles lexical-setAndy Wingo1-15/+34
* module/language/tree-il/optimize.scm (alpha-rename, peval): Add support for lexical-set, while avoiding copy propagation and pruning of assigned variables.
2011-09-24peval: pre-analyze mutated or reffed-once lexicalsAndy Wingo1-0/+45
* module/language/tree-il/optimize.scm (<var>, build-var-table, peval): Before going into peval, build a table indicating refcounts and a set? flag for all lexicals. Add to the table when introducing new bindings (via alpha-renaming).
2011-09-24peval: don't propagate expressions that access memoryAndy Wingo1-9/+6
* module/language/tree-il/optimize.scm (peval): Rename `pure-expression?' to `constant-expression?', in the sense of GCC's `pure' and `const'. A <toplevel-ref> is not constant, because it can be mutated. A <dynref> isn't constant either, for the same reason. * test-suite/tests/tree-il.test ("partial evaluation"): Add a test, and update existing tests that assumed that toplevel-ref would propagate.
2011-09-24context-specific folding for peval in test and effect contextsAndy Wingo1-20/+54
* module/language/tree-il/optimize.scm (peval): Add a "test" context, which folds statically decidable values to <const>. Fold pure expressions to <void> in "effect" contexts. Adapt the <conditional> and <sequence> tests to simply look for <const> or <void> expressions, respectively.
2011-09-24thread a context through pevalAndy Wingo1-49/+62
* module/language/tree-il/optimize.scm (peval): Thread a "context" through the evaluator.
2011-09-24peval: various bugfixesAndy Wingo1-18/+21
* module/language/tree-il/optimize.scm (alpha-rename): Rename the init expressions of a <lambda-case>. (peval): Coalesce the <let-values> clauses. Fix pure-expression? matching of <lambda> clauses. Loop over and maybe-unconst the inits of a <lambda-case>.