[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Guile-commits] 02/02: Simplify live variable computation for graphs wit
From: |
Andy Wingo |
Subject: |
[Guile-commits] 02/02: Simplify live variable computation for graphs without loops |
Date: |
Wed, 29 Nov 2017 15:01:35 -0500 (EST) |
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 +