summaryrefslogtreecommitdiff
path: root/module/language
AgeCommit message (Collapse)AuthorFilesLines
2011-11-11Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo1-0/+22
2011-11-09when leaving a non-tail let, allow bound vals to be collectedAndy Wingo1-0/+22
* module/language/tree-il/compile-glil.scm (flatten-lambda-case): Clear lexical stack slots at the end of a non-tail let, letrec, or fix. Fixes http://debbugs.gnu.org/9900. * test-suite/tests/gc.test ("gc"): Add test.
2011-11-09inline dynwind guards for normal control flowAndy Wingo6-85/+99
* module/language/tree-il.scm (<tree-il>): Add `pre' and `post' fields to <dynwind>, so that we can inline the guard bodies in the normal control-flow case. It also avoids duplicating code in compile-glil, which probably hides more bugs in 2.0. (parse-tree-il, unparse-tree-il, tree-il->scheme, tree-il-fold) (make-tree-il-folder, post-order!, pre-order!): Update. * module/language/tree-il/analyze.scm (analyze-lexicals): Update. * module/language/tree-il/compile-glil.scm (flatten-lambda-case): Update to use `pre' and `post' instead of compiling code twice. * module/language/tree-il/debug.scm (verify-tree-il): Update. * module/language/tree-il/peval.scm (peval): Update. Instead of doing complicated things in <dynwind>, handle 'dynamic-wind primcalls. * module/language/tree-il/primitives.scm (*primitive-expand-table*): Remove 'dynamic-wind mess. Adapt '@dynamic-wind. * test-suite/tests/tree-il.test ("partial evaluation"): Update tests.
2011-11-09Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo2-16/+53
Conflicts: module/language/tree-il/peval.scm module/language/tree-il/primitives.scm test-suite/tests/tree-il.test
2011-11-09simplify primitives.scm for dynwindAndy Wingo1-30/+13
* module/language/tree-il/primitives.scm (*primitive-expand-table*): Remove a dynwind hack, as we have a good inliner now.
2011-11-09peval: fix dynwind bug.Andy Wingo1-2/+33
* module/language/tree-il/peval.scm (peval): The <dynwind> compiler will copy the winder and unwinder values, so make sure that they are constant, and if not, create lexical bindings. Fixes http://debbugs.gnu.org/9844. * test-suite/tests/tree-il.test ("partial evaluation"): Add a couple <dynwind> tests.
2011-11-09fix <dynwind> serialization.Andy Wingo1-3/+3
* module/language/tree-il.scm (unparse-tree-il): Fix <dynwind> serialization.
2011-11-09peval: don't copy assigned lexical bindingsAndy Wingo1-11/+17
* module/language/tree-il/peval.scm (peval): Since constant-expression? is used to determine whether to copy values, return #f if any lexical is assigned.
2011-11-04peval doesn't resolve primitivesAndy Wingo1-6/+1
* module/language/tree-il/peval.scm (peval): Don't resolve primitives, as resolve-primitives! handles that already. * test-suite/tests/tree-il.test (pass-if-peval): Always resolve and expand primitives. ("partial evaluation"): Update tests to assume expanded primitives.
2011-11-04resolve-primitives! does not primitivize local definitionsAndy Wingo1-2/+15
* module/language/tree-il/primitives.scm (resolve-primitives!): Don't resolve toplevels defined in the same compilation unit to primitives, as it could be that the module doesn't have those bindings yet.
2011-10-28add string-length, string-ref, vector-length instructionsAndy Wingo1-0/+3
* libguile/_scm.h (SCM_OBJCODE_MAJOR_VERSION): Bump the major version, indicating the first incompatibility between 2.0 and 2.2. * libguile/vm-i-scheme.c (string-length, string-ref, vector-length): New instructions. * module/language/tree-il/compile-glil.scm (*primcall-ops*): Add primcall ops for the new instructions.
2011-10-28add vector-length primitiveAndy Wingo1-2/+2
* module/language/tree-il/primitives.scm (*interesting-primitive-names*, *effect-free-primitives*): Recognize vector-length as an effect-free primitive.
2011-10-28simplify primitives.scmAndy Wingo1-30/+13
* module/language/tree-il/primitives.scm (*primitive-expand-table*): Remove a hack to compensate for the lack of a good inliner, now that we do have a good inliner.
2011-10-27fix the peval merge and a testAndy Wingo1-3/+4
* module/language/tree-il/peval.scm (peval): Accessor primitives applied to constants are pure if the call type-checks. Also, fold constants in accessor primcalls. * test-suite/tests/tree-il.test ("partial evaluation"): Fix the "yo" test.
2011-10-27Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo3-35/+43
Conflicts: GUILE-VERSION libguile/deprecated.c libguile/gc-malloc.c module/language/tree-il/peval.scm
2011-10-20fix misallocation of some <fix> proceduresAndy Wingo1-1/+1
* module/language/tree-il/analyze.scm (analyze-lexicals): When stepping into a non-tail form, we know that labels allocation will be invalid, so use an empty labels set. Fixes http://debbugs.gnu.org/9769. * test-suite/tests/tree-il.test ("labels allocation"): Add a test.
2011-10-10fold constants with accessorsAndy Wingo1-30/+36
* module/language/tree-il/peval.scm (peval): Factor constant folding out to a helper. Use it in the accessor case in addition to the normal effect-free-primitive case. * test-suite/tests/tree-il.test: Add a test.
2011-10-10recognize string primitivesAndy Wingo1-4/+10
* module/language/tree-il/primitives.scm (*interesting-primitive-names*): Add string?, string-length, and ref and set. (*primitive-accessors*): Add string-ref. (*effect-free-primitives*): Add string-length and string? (*effect+exception-free-primitives*): Add string?. (*singly-valued-primitives*): Add string-length and ref and set.
2011-10-10Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo4-354/+869
Does not include psyntax regeneration. Conflicts: module/ice-9/psyntax-pp.scm module/language/tree-il/peval.scm test-suite/tests/tree-il.test
2011-10-10peval support for memq and memvAndy Wingo1-0/+46
* module/language/tree-il/peval.scm (peval): Add special handlers for memq and memv, as inline.scm used to have. This is important for `case' clauses. It is very ugly, though. * test-suite/tests/tree-il.test ("partial evaluation"): Add tests.
2011-10-10add accessor-primitive?, peval uses itAndy Wingo2-40/+53
* module/language/tree-il/primitives.scm (*primitive-accessors*): New set of primitives: those that access mutable memory, but are otherwise pure. Include bytevector references here. (accessor-primitive?): New public predicate. * module/language/tree-il/peval.scm (peval): Refactor to distinguish constructor-primitive? from accessor-primitive?.
2011-10-10peval: visit operands on-demand, to inline mutually recursive bindingsAndy Wingo1-357/+353
This commit changes to use <operand> structures to hold the context needed to visit lexical bindings lazily, in context, instead of eagerly visiting them for value. This laziness enables inlining of mutually recursive bindings. * module/language/tree-il/peval.scm (<var>): Remove comment about copy propagation having to run build-var-table; things don't work like that any more. (build-var-table): Build <var> entries for all variables, even unreferenced variables. (alpha-rename): Remove. We will rename bindings on-demand now. (peval lookup-var): New helper, to fetch the <var> of a gensym. (peval fresh-gensyms): Fold here, under peval, and in it, handle updating the store to record a mapping between new names and <var> entries from the source program. (peval record-source-expression): Don't call build-var-table on the new expression, as alpha-renaming happens on-demand now. (peval prune-bindings): Rewrite to work with mutually-recursive bindings, while optionally preserving binding order. (peval extend-env): New helper. (peval loop): OK, here goes... Remove the `operand' context, as now we visit operands lazily. Add a `call' context, which does not copy-propagate lambda expressions, used to residualize a call after aborting an inlining attempt. Change the `env' to be a mapping of gensym to <operand>. Instead of looking up the operand's binding then alpha-renaming it, just rely on the fact that visiting the operand will rename it if necessary. If we residualize a lexical, do so with the fresh name from the environment. If we visit an operand and it doesn't turn out to be constant, we will never be able to copy it, and so cache that fact in the operand. If we residualize a binding and we know what the value should be, record that binding so that prune-bindings won't have to visit it again. If the operand folds to a constant, cache that too, to save effort when unrolling loops. For let, letrec, fix, and lambda-case, instead of visiting the bindings eagerly for value, simply record the source expressions and environments in an <operand> and rely on copy-propagation to visit them later in the right context. In the case of letrec and fix, this allows mutually-recursive bindings to be inlined. Refactor folding of "constructors" (which still need renaming) to avoid visiting operands twice in some contexts. For applications, if we have to abort, process the procedure in call context, which allows some folding but avoids copying lambdas. If we find a recursive procedure, mark intervening counters as recursive too, to allow for mutual recursion at the top level. For lambdas, if we are processing for value, record the source expression so we can detect recursion. This was previously done in the lexical-ref copy propagator. * test-suite/tests/tree-il.test ("partial evaluation"): Remove unused recursive lexicals in a couple of cases. Add a couple test cases for pruning. Add a few recursive binding cases.
2011-10-10peval: add operand structureAndy Wingo1-0/+57
* module/language/tree-il/peval.scm (<operand>): Add operand structure, to be used by peval.
2011-10-10peval: refactor loggingAndy Wingo1-5/+6
* module/language/tree-il/peval.scm: Make it easier to turn on logging.
2011-10-08peval: loggingAndy Wingo1-4/+52
* module/language/tree-il/peval.scm: Define a quick and dirty infrastructure for logging. Use it in peval.
2011-10-07peval: bugfix in constant-expression?Andy Wingo1-1/+2
* module/language/tree-il/peval.scm (constant-expression?): Correctly handle lambda-case alternates.
2011-10-07optimizer verifies its outputAndy Wingo1-2/+4
* module/language/tree-il/optimize.scm: Verify the result of partial evaluation.
2011-10-07add tree-il verifierAndy Wingo1-0/+261
* module/Makefile.am: Add debug.scm. * module/language/tree-il/debug.scm: New file, a verifier for tree-il.
2011-10-06peval refactorAndy Wingo1-9/+7
* module/language/tree-il/peval.scm (peval): Refactor the for-value, etc helpers.
2011-10-06comment peval.scmAndy Wingo1-126/+196
* module/language/tree-il/peval.scm: Add comments. Move alpha-rename later in the file.
2011-09-30peval: Recognize module-refs to primitives.Ludovic Courtès1-0/+9
* module/language/tree-il/optimize.scm (peval): Handle module-refs to primitives. * test-suite/tests/tree-il.test ("partial evaluation"): Add test, using `pmatch'.
2011-09-29Merge remote-tracking branch 'origin/stable-2.0'Andy Wingo11-352/+1209
This was a pretty big merge involving a fair amount of porting, especially to peval and its tests. I did not update psyntax-pp.scm, that comes in the next commit. Conflicts: module/ice-9/boot-9.scm module/ice-9/psyntax-pp.scm module/language/ecmascript/compile-tree-il.scm module/language/tree-il.scm module/language/tree-il/analyze.scm module/language/tree-il/inline.scm test-suite/tests/tree-il.test
2011-09-28separate peval and a new canonicalization pass into their own modulesAndy Wingo5-1160/+1044
* 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-28fix unparse-tree-il of <dynset>Andy Wingo1-1/+1
* module/language/tree-il.scm (unparse-tree-il): Fix printing of `dynset'.
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 Wingo2-3/+66
* 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.