summaryrefslogtreecommitdiff
path: root/module/language/tree-il/optimize.scm
AgeCommit message (Collapse)AuthorFilesLines
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>.
2011-09-24tree-il-any bugfixAndy Wingo1-1/+3
* module/language/tree-il/optimize.scm (tree-il-any): Fix to be called on all values, including leaves. It didn't matter for the use case, though.
2011-09-24minor peval style tweakAndy Wingo1-1/+1
* module/language/tree-il/optimize.scm (peval): Minor refactor to <lexical-ref> copy propagation.
2011-09-24fix alpha-rename for kwargsAndy Wingo1-2/+12
* module/language/tree-il/optimize.scm (alpha-rename): Fix alpha-renaming of keyword arguments.
2011-09-23peval: Rectify style.Ludovic Courtès1-7/+7
* module/language/tree-il/optimize.scm (peval): Rename `src' to `lv-src', and `src2' to `src'; pass `make-let-values' the right source locations. Reindent `let*'.
2011-09-21peval comment & reindentationAndy Wingo1-3/+9
* module/language/tree-il/optimize.scm (peval): Add a comment regarding failure modes, and reindent one clause.
2011-09-21fix comment regarding alpha-renamingAndy Wingo1-4/+3
* module/language/tree-il/optimize.scm (peval): Fix comment regarding alpha-renaming: it's not simply the allocator that needs unique names; rather, all transformations depend on it.
2011-09-21better pure-expression?Andy Wingo1-0/+5
* module/language/tree-il/optimize.scm (peval): Allow dynref, fix, and let-values to be pure expressions.
2011-09-21more alpha-rename robustnessAndy Wingo1-0/+27
* module/language/tree-il/optimize.scm (alpha-rename): Handle all kinds of tree-il, with the current exceptions of lexical set!, prompt, and abort.
2011-09-21more robust alpha-renamingAndy Wingo1-3/+11
* module/language/tree-il/optimize.scm (fresh-gensyms): New helper. (alpha-rename): Name the new gensyms using the old names as templates, not the old gensyms. This prevents accidental collisions between gensyms, if #{x 1}# becomes #{x 12}# instead of #{x 2}#.
2011-09-21peval: inlining of let-valuesAndy Wingo1-0/+95
* module/language/tree-il/optimize.scm (peval): Add support for let-values. Try to inline the consumer into the body of the producer, if there is only one return point, and we can figure out how many values are being returned, and that number is compatible with the consumer.
2011-09-21peval support for more formsAndy Wingo1-0/+29
* module/language/tree-il/optimize.scm (peval): Add support for fix, dynwind, dynlet, dynref, module-set, and toplevel-set. (Mutating a variable directly is similar to calling a function that does so behind our backs, so this presents no additional problem.)
2011-09-21more optimize.scm factoringAndy Wingo1-4/+11
* module/language/tree-il/optimize.scm (vlist-any): New helper. (peval): Use it here.
2011-09-21optimize.scm refactorAndy Wingo1-24/+30
* module/language/tree-il/optimize.scm (let/ec, tree-il-any): New helpers. (code-contains-calls?): Use them here.
2011-09-18peval: Abort inlining when the residual code contains recursive calls.Ludovic Courtès1-8/+43
* module/language/tree-il/optimize.scm (code-contains-calls?): New procedure. (peval): Use it and abort inlining if the residual code of a procedure application contains recursive calls. Suggested by Wingo, Waddell, and Dybvig. Fixes <http://debbugs.gnu.org/9542>. * test-suite/tests/tree-il.test ("partial evaluation"): Update 2 tests that relied on the previous behavior. Add 1 another test.
2011-09-17peval: Typo.Ludovic Courtès1-1/+1
* module/language/tree-il/optimize.scm (peval)[maybe-unlambda]: Fix typo in comment.
2011-09-17peval: Alpha-rename anonymous lambdas that are duplicated.Ludovic Courtès1-0/+71
* module/language/tree-il/optimize.scm (alpha-rename): New procedure. (peval)[maybe-unlambda]: Use it. * test-suite/tests/tree-il.test ("partial evaluation"): Add two test cases for <https://lists.gnu.org/archive/html/bug-guile/2011-09/msg00019.html>.
2011-09-13peval: Use `resolve-primitives!'.Ludovic Courtès1-13/+11
* module/language/tree-il/optimize.scm (peval): Add `cenv' optional argument; caller updated. Use `resolve-primitives!' to resolve <primitive-ref> expressions.
2011-09-13peval: Clarify `pure-expression?'.Ludovic Courtès1-2/+3
* module/language/tree-il/optimize.scm (peval)[pure-expression?]: Clarify the comment.
2011-09-13peval: Inline thunks.Ludovic Courtès1-1/+1
* module/language/tree-il/optimize.scm (peval): Inline thunks. * test-suite/tests/tree-il.test ("partial evaluation"): Add test.
2011-09-13peval: Use the right scope when replacing a lambda by a lexical-ref.Ludovic Courtès1-15/+24
* module/language/tree-il/optimize.scm (peval)[maybe-unlambda]: New procedures. Use it to de-duplicate named lambdas. This fixes the scoping bug described at <https://lists.gnu.org/archive/html/bug-guile/2011-09/msg00019.html>. * test-suite/tests/tree-il.test ("partial evaluation"): Add tests to reproduce the bug.
2011-09-13peval: Add tests for inlining with both static & dynamic arguments.Ludovic Courtès1-3/+4
* module/language/tree-il/optimize.scm (peval): Improve comment on the inlining heuristics. * test-suite/tests/tree-il.test ("partial evaluation"): Add two tests.
2011-09-11peval: Propagate only pure expressions to lambdas.Ludovic Courtès1-6/+8
* module/language/tree-il/optimize.scm (peval): Propagate ARGS to BODY only when all of ARGS are pure. Change APP to use `maybe-unconst' for its arguments. * test-suite/tests/tree-il.test ("partial evaluation"): Add tests for mutability preservation and non-propagation of non-constant arguments to lambdas.
2011-09-11peval: Try hard to preserve mutability.Ludovic Courtès1-18/+70
* module/language/tree-il/optimize.scm (peval)[make-values]: Distinguish between 1 or another number of values. [mutable?, make-value-construction, maybe-unconst]: New procedures. Use it in <let>, <letrec>, <toplevel-define>, and <lambda-case>. * test-suite/tests/tree-il.test ("partial evaluation"): Add tests for mutability preservation.
2011-09-09Add a partial evaluator for use in the compiler.Ludovic Courtès1-5/+244
Thanks to William R. Cook for his excellent tutorial, <http://softlang.uni-koblenz.de/dsl11/>. * module/language/tree-il/optimize.scm (optimize!): Call `peval' unless the #:partial-eval? option asks otherwise. (peval): New procedure. * module/language/tree-il/inline.scm: Add comment. * module/language/tree-il/primitives.scm (*primitive-constructors*): New variable. (*effect-free-primitives*): Use it. (constructor-primitive?): New primitive. * test-suite/tests/tree-il.test (assert-tree-il->glil): Extend to support `with-partial-evaluation', `without-partial-evaluation', and `with-options'. (peval): New binding. (pass-if-peval): New macro. ("lexical refs"): Run tests without partial evaluation. ("letrec"): Likewise. ("the or hack"): Likewise. ("conditional"): Likewise, for some tests. ("sequence"): Adjust to new generated code. ("partial evaluation"): New test prefix.