Commit | Line | Data |
---|---|---|
f05517b2 AW |
1 | ;;; Continuation-passing style (CPS) intermediate language (IL) |
2 | ||
3 | ;; Copyright (C) 2014 Free Software Foundation, Inc. | |
4 | ||
5 | ;;;; This library is free software; you can redistribute it and/or | |
6 | ;;;; modify it under the terms of the GNU Lesser General Public | |
7 | ;;;; License as published by the Free Software Foundation; either | |
8 | ;;;; version 3 of the License, or (at your option) any later version. | |
9 | ;;;; | |
10 | ;;;; This library is distributed in the hope that it will be useful, | |
11 | ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | ;;;; Lesser General Public License for more details. | |
14 | ;;;; | |
15 | ;;;; You should have received a copy of the GNU Lesser General Public | |
16 | ;;;; License along with this library; if not, write to the Free Software | |
17 | ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
18 | ||
19 | ;;; Commentary: | |
20 | ;;; | |
21 | ;;; A pass to renumber variables and continuation labels so that they | |
22 | ;;; are contiguous within each function. | |
23 | ;;; | |
24 | ;;; Code: | |
25 | ||
26 | (define-module (language cps renumber) | |
27 | #:use-module (ice-9 match) | |
28 | #:use-module (language cps) | |
29 | #:export (renumber)) | |
30 | ||
31 | (define (visit-funs proc fun) | |
32 | (define (visit-cont cont) | |
33 | (match cont | |
34 | (($ $cont label cont) | |
35 | (match cont | |
36 | (($ $kargs names vars body) | |
37 | (visit-term body)) | |
90dce16d AW |
38 | (($ $kentry self tail clause) |
39 | (when clause | |
40 | (visit-cont clause))) | |
41 | (($ $kclause arity body alternate) | |
42 | (visit-cont body) | |
43 | (when alternate | |
44 | (visit-cont alternate))) | |
f05517b2 AW |
45 | ((or ($ $kreceive) ($ $kif)) |
46 | #f))))) | |
47 | (define (visit-term term) | |
48 | (match term | |
49 | (($ $letk conts body) | |
50 | (for-each visit-cont conts) | |
51 | (visit-term body)) | |
52 | (($ $letrec names syms funs body) | |
53 | (for-each visit-fun funs) | |
54 | (visit-term body)) | |
55 | (($ $continue k src (and fun ($ $fun))) | |
56 | (visit-fun fun)) | |
57 | (($ $continue k src _) | |
58 | #f))) | |
59 | (define (visit-fun fun) | |
60 | (proc fun) | |
61 | (match fun | |
62 | (($ $fun src meta free body) | |
63 | (visit-cont body)))) | |
64 | (visit-fun fun)) | |
65 | ||
66 | (define (compute-new-labels-and-vars fun) | |
67 | (call-with-values (lambda () (compute-max-label-and-var fun)) | |
68 | (lambda (max-label max-var) | |
69 | (let ((labels (make-vector (1+ max-label))) | |
70 | (next-label 0) | |
71 | (vars (make-vector (1+ max-var))) | |
72 | (next-var 0)) | |
73 | (define (relabel! label) | |
74 | (vector-set! labels label next-label) | |
75 | (set! next-label (1+ next-label))) | |
76 | (define (rename! var) | |
77 | (vector-set! vars var next-var) | |
78 | (set! next-var (1+ next-var))) | |
79 | (define (compute-names-in-fun fun) | |
80 | (define (visit-cont cont) | |
81 | (match cont | |
82 | (($ $cont label cont) | |
83 | (relabel! label) | |
84 | (match cont | |
85 | (($ $kargs names vars body) | |
86 | (for-each rename! vars) | |
87 | (visit-term body)) | |
90dce16d | 88 | (($ $kentry self tail clause) |
f05517b2 AW |
89 | (rename! self) |
90 | (visit-cont tail) | |
90dce16d AW |
91 | (when clause |
92 | (visit-cont clause))) | |
93 | (($ $kclause arity body alternate) | |
94 | (visit-cont body) | |
95 | (when alternate | |
96 | (visit-cont alternate))) | |
f05517b2 AW |
97 | ((or ($ $ktail) ($ $kreceive) ($ $kif)) |
98 | #f))))) | |
99 | (define (visit-term term) | |
100 | (match term | |
101 | (($ $letk conts body) | |
102 | (for-each visit-cont conts) | |
103 | (visit-term body)) | |
104 | (($ $letrec names syms funs body) | |
105 | (for-each rename! syms) | |
106 | (visit-term body)) | |
107 | (($ $continue k src _) | |
108 | #f))) | |
109 | (match fun | |
110 | (($ $fun src meta free body) | |
111 | (visit-cont body)))) | |
112 | ||
113 | (visit-funs compute-names-in-fun fun) | |
114 | (values labels vars))))) | |
115 | ||
116 | (define (renumber fun) | |
117 | (call-with-values (lambda () (compute-new-labels-and-vars fun)) | |
118 | (lambda (labels vars) | |
119 | (define (relabel label) (vector-ref labels label)) | |
120 | (define (rename var) (vector-ref vars var)) | |
121 | (define (rename-kw-arity arity) | |
122 | (match arity | |
123 | (($ $arity req opt rest kw aok?) | |
124 | (make-$arity req opt rest | |
125 | (map (match-lambda | |
126 | ((kw kw-name kw-var) | |
127 | (list kw kw-name (rename kw-var)))) | |
128 | kw) | |
129 | aok?)))) | |
130 | (define (visit-cont cont) | |
131 | (rewrite-cps-cont cont | |
132 | (($ $cont label ($ $kargs names vars body)) | |
133 | ((relabel label) | |
134 | ($kargs names (map rename vars) ,(visit-term body)))) | |
90dce16d | 135 | (($ $cont label ($ $kentry self tail clause)) |
f05517b2 AW |
136 | ((relabel label) |
137 | ($kentry (rename self) ,(visit-cont tail) | |
90dce16d | 138 | ,(and clause (visit-cont clause))))) |
f05517b2 AW |
139 | (($ $cont label ($ $ktail)) |
140 | ((relabel label) ($ktail))) | |
90dce16d | 141 | (($ $cont label ($ $kclause arity body alternate)) |
f05517b2 | 142 | ((relabel label) |
90dce16d AW |
143 | ($kclause ,(rename-kw-arity arity) ,(visit-cont body) |
144 | ,(and alternate (visit-cont alternate))))) | |
f05517b2 AW |
145 | (($ $cont label ($ $kreceive ($ $arity req () rest () #f) kargs)) |
146 | ((relabel label) ($kreceive req rest (relabel kargs)))) | |
147 | (($ $cont label ($ $kif kt kf)) | |
148 | ((relabel label) ($kif (relabel kt) (relabel kf)))))) | |
149 | (define (visit-term term) | |
150 | (rewrite-cps-term term | |
151 | (($ $letk conts body) | |
152 | ($letk ,(map visit-cont conts) | |
153 | ,(visit-term body))) | |
154 | (($ $letrec names vars funs body) | |
155 | ($letrec names (map rename vars) (map visit-fun funs) | |
156 | ,(visit-term body))) | |
157 | (($ $continue k src exp) | |
158 | ($continue (relabel k) src ,(visit-exp exp))))) | |
159 | (define (visit-exp exp) | |
160 | (match exp | |
161 | ((or ($ $void) ($ $const) ($ $prim)) | |
162 | exp) | |
163 | (($ $fun) | |
164 | (visit-fun exp)) | |
165 | (($ $values args) | |
166 | (let ((args (map rename args))) | |
167 | (build-cps-exp ($values args)))) | |
168 | (($ $call proc args) | |
169 | (let ((args (map rename args))) | |
170 | (build-cps-exp ($call (rename proc) args)))) | |
171 | (($ $callk k proc args) | |
172 | (let ((args (map rename args))) | |
173 | (build-cps-exp ($callk (relabel k) (rename proc) args)))) | |
174 | (($ $primcall name args) | |
175 | (let ((args (map rename args))) | |
176 | (build-cps-exp ($primcall name args)))) | |
177 | (($ $prompt escape? tag handler) | |
178 | (build-cps-exp | |
179 | ($prompt escape? (rename tag) (relabel handler)))))) | |
180 | (define (visit-fun fun) | |
181 | (rewrite-cps-exp fun | |
182 | (($ $fun src meta free body) | |
183 | ($fun src meta (map rename free) ,(visit-cont body))))) | |
184 | (visit-fun fun)))) |