From 9bf29f0784972e5280e53595007c25cc5c95406c Mon Sep 17 00:00:00 2001 From: Stephen Adams Date: Wed, 6 Mar 1996 14:22:27 +0000 Subject: [PATCH] Changed the cycle breaking code to use a hash-table to avoid quadratic behaviour. The bulk of the problem was the code was both slow and quadratic. There was a higher order call to EQ? in the middle of a `map lookup', so 10-20% of SIMPLIFY's time was spent going out of line to funcall EQ? Added a comment on how to improve the cycle breaking code. --- v8/src/compiler/midend/simplify.scm | 28 +++++++++++++++++++--------- 1 file changed, 19 insertions(+), 9 deletions(-) diff --git a/v8/src/compiler/midend/simplify.scm b/v8/src/compiler/midend/simplify.scm index f864ae05f..192bda6f8 100644 --- a/v8/src/compiler/midend/simplify.scm +++ b/v8/src/compiler/midend/simplify.scm @@ -1,6 +1,6 @@ #| -*-Scheme-*- -$Id: simplify.scm,v 1.17 1995/08/19 13:42:24 adams Exp $ +$Id: simplify.scm,v 1.18 1996/03/06 14:22:27 adams Exp $ Copyright (c) 1994-1995 Massachusetts Institute of Technology @@ -86,15 +86,25 @@ MIT in each case. |# ;; where ENVIRONMENT is either #F or the environment for the lambda ;; expression bound to this name (define unsafe-cyclic-reference? + ;; Maps a LAMBDA form to a boolean: was this LAMBDA chosen to break + ;; cycles? Things that we do not take into account but we should: + ;; (1) If for some reason we would not try to substitute the lambda, + ;; then it already breaks a cycle. (2) we should put lambdas + ;; with simple inline-able bodies last so they don't break a cycle + ;; by accident. (3) the DFS should be rooted in the LETREC's body. (if mutually-recursive? - (let ((finder (association-procedure eq? second))) - (make-breaks-cycle? (map second bindings) - (lambda (name) - (let* ((triple (finder name bindings)) - (env (first triple))) - (if env - (simplify/env/free-calls env) - '()))))) + (let ((table (make-monotonic-strong-eq-hash-table))) + (define (insert! triple) + (monotonic-strong-eq-hash-table/put! + table + (second triple) ;name + (if (first triple) + (simplify/env/free-calls (first triple)) + '()))) + (for-each insert! bindings) + (make-breaks-cycle? + (map second bindings) + (lambda (name) (monotonic-strong-eq-hash-table/get table name #F)))) (lambda (lambda-expr) lambda-expr #F))) (simplify/bindings env unsafe-cyclic-reference? -- 2.25.1