home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mitsch75.zip / scheme-7_5_17-src.zip / scheme-7.5.17 / src / compiler / fgopt / conect.scm < prev    next >
Text File  |  1999-01-02  |  3KB  |  85 lines
  1. #| -*-Scheme-*-
  2.  
  3. $Id: conect.scm,v 4.5 1999/01/02 06:06:43 cph Exp $
  4.  
  5. Copyright (c) 1987, 1988, 1999 Massachusetts Institute of Technology
  6.  
  7. This program is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2 of the License, or (at
  10. your option) any later version.
  11.  
  12. This program is distributed in the hope that it will be useful, but
  13. WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15. General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software
  19. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20. |#
  21.  
  22. ;;;; FG Connectivity Analysis
  23.  
  24. (declare (usual-integrations))
  25.  
  26. (define (connectivity-analysis expression procedures)
  27.   (walk-node (expression-entry-node expression) (make-subgraph-color))
  28.   (for-each (lambda (procedure)
  29.           (if (not (procedure-direct-linked? procedure))
  30.           (walk-node (procedure-entry-node procedure)
  31.                  (make-subgraph-color))))
  32.         procedures))
  33.  
  34. (define (procedure-direct-linked? procedure)
  35.   (if (procedure-continuation? procedure)
  36.       (and (continuation/ever-known-operator? procedure)
  37.        (there-exists? (continuation/combinations procedure)
  38.          (lambda (combination)
  39.            (and (combination/inline? combination)
  40.             (combination/continuation-push combination)))))
  41.       (procedure-inline-code? procedure)))
  42.  
  43. (define (walk-node node color)
  44.   (let ((color* (node/subgraph-color node)))
  45.     (cond ((not color*)
  46.        (color-node! node color)
  47.        (walk-next node color))
  48.       ((not (eq? color color*))
  49.        (recolor-nodes! (subgraph-color/nodes color*) color)))))
  50.  
  51. (define (color-node! node color)
  52.   (set-node/subgraph-color! node color)
  53.   (set-subgraph-color/nodes! color (cons node (subgraph-color/nodes color))))
  54.  
  55. (define (recolor-nodes! nodes color)
  56.   (for-each (lambda (node)
  57.           (set-node/subgraph-color! node color))
  58.         nodes)
  59.   (set-subgraph-color/nodes! color
  60.                  (append! nodes (subgraph-color/nodes color))))
  61.  
  62. (define (walk-next node color)
  63.   (cfg-node-case (tagged-vector/tag node)
  64.     ((APPLICATION)
  65.      (case (application-type node)
  66.        ((COMBINATION)
  67.     (if (combination/inline? node)
  68.         (walk-continuation (combination/continuation node) color)
  69.         (let ((operator (rvalue-known-value (application-operator node))))
  70.           (if (and operator
  71.                (rvalue/procedure? operator)
  72.                (procedure-inline-code? operator))
  73.           (walk-node (procedure-entry-node operator) color)))))
  74.        ((RETURN)
  75.     (walk-continuation (return/operator node) color))))
  76.     ((VIRTUAL-RETURN POP ASSIGNMENT DEFINITION FG-NOOP STACK-OVERWRITE)
  77.      (walk-node (snode-next node) color))
  78.     ((TRUE-TEST)
  79.      (walk-node (pnode-consequent node) color)
  80.      (walk-node (pnode-alternative node) color))))
  81.  
  82. (define (walk-continuation continuation color)
  83.   (let ((rvalue (rvalue-known-value continuation)))
  84.     (if rvalue
  85.     (walk-node (continuation/entry-node rvalue) color))))