[Guile-commits] 02/02: Simplify live variable computation for graphs without loops

[Andy Wingo]

wingo pushed a commit to branch master
in repository guile.

commit 39520f879a41821ad63ed85fd227b9ec421cb8b7
Author: Andy Wingo <address@hidden>
Date:   Wed Nov 29 19:57:48 2017 +0100

    Simplify live variable computation for graphs without loops
    
    * module/language/cps/slot-allocation.scm
      (compute-reverse-control-flow-order): For graphs without back-edges,
      use a simplified computation of reverse control flow order.
---
 module/language/cps/slot-allocation.scm | 40 ++++++++++++++++++++++++---------
 1 file changed, 29 insertions(+), 11 deletions(-)

diff --git a/module/language/cps/slot-allocation.scm 
b/module/language/cps/slot-allocation.scm
index 7106584..21f3e7f 100644
--- a/module/language/cps/slot-allocation.scm
+++ b/module/language/cps/slot-allocation.scm
@@ -23,6 +23,7 @@
 ;;; Code:
 
 (define-module (language cps slot-allocation)
+  #:use-module (ice-9 control)
   #:use-module (ice-9 match)
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-9)
@@ -171,17 +172,34 @@ by a label, respectively."
 
 (define (compute-reverse-control-flow-order preds)
   "Return a LABEL->ORDER bijection where ORDER is a contiguous set of
-integers starting from 0 and incrementing in sort order."
-  ;; This is more involved than forward control flow because not all
-  ;; live labels are reachable from the tail.
-  (persistent-intmap
-   (fold2 (lambda (component order n)
-            (intset-fold (lambda (label order n)
-                           (values (intmap-add! order label n)
-                                   (1+ n)))
-                         component order n))
-          (reverse (compute-sorted-strongly-connected-components preds))
-          empty-intmap 0)))
+integers starting from 0 and incrementing in sort order.  There is a
+precondition that labels in PREDS are already renumbered in reverse post
+order."
+  (define (has-back-edge? preds)
+    (let/ec return
+      (intmap-fold (lambda (label labels)
+                     (intset-fold (lambda (pred)
+                                    (if (<= label pred)
+                                        (return #t)
+                                        (values)))
+                                  labels)
+                     (values))
+                   preds)
+      #f))
+  (if (has-back-edge? preds)
+      ;; This is more involved than forward control flow because not all
+      ;; live labels are reachable from the tail.
+      (persistent-intmap
+       (fold2 (lambda (component order n)
+                (intset-fold (lambda (label order n)
+                               (values (intmap-add! order label n)
+                                       (1+ n)))
+                             component order n))
+              (reverse (compute-sorted-strongly-connected-components preds))
+              empty-intmap 0))
+      ;; Just reverse forward control flow.
+      (let ((max (intmap-prev preds)))
+        (intmap-map (lambda (label labels) (- max label)) preds))))
 
 (define* (add-prompt-control-flow-edges conts succs #:key complete?)
   "For all prompts in DFG in the range [MIN-LABEL, MIN-LABEL +