0.7.4.11:
[sbcl.git] / src / compiler / gtn.lisp
1 ;;;; This file contains the GTN pass in the compiler. GTN allocates
2 ;;;; the TNs that hold the values of lexical variables and determines
3 ;;;; the calling conventions and passing locations used in function
4 ;;;; calls.
5
6 ;;;; This software is part of the SBCL system. See the README file for
7 ;;;; more information.
8 ;;;;
9 ;;;; This software is derived from the CMU CL system, which was
10 ;;;; written at Carnegie Mellon University and released into the
11 ;;;; public domain. The software is in the public domain and is
12 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
13 ;;;; files for more information.
14
15 (in-package "SB!C")
16
17 ;;; We make a pass over the component's environments, assigning argument
18 ;;; passing locations and return conventions and TNs for local variables.
19 (defun gtn-analyze (component)
20   (setf (component-info component) (make-ir2-component))
21   (let ((funs (component-lambdas component)))
22     (dolist (fun funs)
23       (assign-ir2-physenv fun)
24       (assign-return-locations fun)
25       (assign-ir2-nlx-info fun)
26       (assign-lambda-var-tns fun nil)
27       (dolist (let (lambda-lets fun))
28         (assign-lambda-var-tns let t))))
29
30   (values))
31
32 ;;; We have to allocate the home TNs for variables before we can call
33 ;;; ASSIGN-IR2-PHYSENV so that we can close over TNs that haven't
34 ;;; had their home environment assigned yet. Here we evaluate the
35 ;;; DEBUG-INFO/SPEED tradeoff to determine how variables are
36 ;;; allocated. If SPEED is 3, then all variables are subject to
37 ;;; lifetime analysis. Otherwise, only LET-P variables are allocated
38 ;;; normally, and that can be inhibited by DEBUG-INFO = 3.
39 (defun assign-lambda-var-tns (fun let-p)
40   (declare (type clambda fun))
41   (dolist (var (lambda-vars fun))
42     (when (leaf-refs var)
43       (let* ((type (if (lambda-var-indirect var)
44                        *backend-t-primitive-type*
45                        (primitive-type (leaf-type var))))
46              (temp (make-normal-tn type))
47              (node (lambda-bind fun))
48              (res (if (or (and let-p (policy node (< debug 3)))
49                           (policy node (zerop debug))
50                           (policy node (= speed 3)))
51                       temp
52                       (physenv-debug-live-tn temp (lambda-physenv fun)))))
53         (setf (tn-leaf res) var)
54         (setf (leaf-info var) res))))
55   (values))
56
57 ;;; Give CLAMBDA an IR2-PHYSENV structure. (And in order to
58 ;;; properly initialize the new structure, we make the TNs which hold
59 ;;; environment values and the old-FP/return-PC.)
60 (defun assign-ir2-physenv (clambda)
61   (declare (type clambda clambda))
62   (let ((lambda-physenv (lambda-physenv clambda))
63         (reversed-ir2-physenv-alist nil))
64     ;; FIXME: should be MAPCAR, not DOLIST
65     (dolist (thing (physenv-closure lambda-physenv))
66       (let ((ptype (etypecase thing
67                      (lambda-var
68                       (if (lambda-var-indirect thing)
69                           *backend-t-primitive-type*
70                           (primitive-type (leaf-type thing))))
71                      (nlx-info *backend-t-primitive-type*))))
72         (push (cons thing (make-normal-tn ptype))
73               reversed-ir2-physenv-alist)))
74
75     (let ((res (make-ir2-physenv
76                 :closure (nreverse reversed-ir2-physenv-alist)
77                 :return-pc-pass (make-return-pc-passing-location
78                                  (xep-p clambda)))))
79       (setf (physenv-info lambda-physenv) res)
80       (setf (ir2-physenv-old-fp res)
81             (make-old-fp-save-location lambda-physenv))
82       (setf (ir2-physenv-return-pc res)
83             (make-return-pc-save-location lambda-physenv))))
84
85   (values))
86
87 ;;; Return true if FUN's result continuation is used in a
88 ;;; tail-recursive full call. We only consider explicit :FULL calls.
89 ;;; It is assumed that known calls are never part of a tail-recursive
90 ;;; loop, so we don't need to enforce tail-recursion. In any case, we
91 ;;; don't know which known calls will actually be full calls until
92 ;;; after LTN.
93 (defun has-full-call-use (fun)
94   (declare (type clambda fun))
95   (let ((return (lambda-return fun)))
96     (and return
97          (do-uses (use (return-result return) nil)
98            (when (and (node-tail-p use)
99                       (basic-combination-p use)
100                       (eq (basic-combination-kind use) :full))
101              (return t))))))
102
103 ;;; Return true if we should use the standard (unknown) return
104 ;;; convention for a TAIL-SET. We use the standard return convention
105 ;;; when:
106 ;;; -- We must use the standard convention to preserve tail-recursion,
107 ;;;    since the TAIL-SET contains both an XEP and a TR full call.
108 ;;; -- It appears to be more efficient to use the standard convention,
109 ;;;    since there are no non-TR local calls that could benefit from
110 ;;;    a non-standard convention.
111 (defun use-standard-returns (tails)
112   (declare (type tail-set tails))
113   (let ((funs (tail-set-funs tails)))
114     (or (and (find-if #'xep-p funs)
115              (find-if #'has-full-call-use funs))
116         (block punt
117           (dolist (fun funs t)
118             (dolist (ref (leaf-refs fun))
119               (let* ((cont (node-cont ref))
120                      (dest (continuation-dest cont)))
121                 (when (and dest
122                            (not (node-tail-p dest))
123                            (basic-combination-p dest)
124                            (eq (basic-combination-fun dest) cont)
125                            (eq (basic-combination-kind dest) :local))
126                   (return-from punt nil)))))))))
127
128 ;;; If policy indicates, give an efficiency note about our inability to
129 ;;; use the known return convention. We try to find a function in the
130 ;;; tail set with non-constant return values to use as context. If
131 ;;; there is no such function, then be more vague.
132 (defun return-value-efficiency-note (tails)
133   (declare (type tail-set tails))
134   (let ((funs (tail-set-funs tails)))
135     (when (policy (lambda-bind (first funs))
136                   (> (max speed space)
137                      inhibit-warnings))
138       (dolist (fun funs
139                    (let ((*compiler-error-context* (lambda-bind (first funs))))
140                      (compiler-note
141                       "Return value count mismatch prevents known return ~
142                        from these functions:~
143                        ~{~%  ~A~}"
144                       (mapcar #'leaf-source-name
145                               (remove-if-not #'leaf-has-source-name-p funs)))))
146         (let ((ret (lambda-return fun)))
147           (when ret
148             (let ((rtype (return-result-type ret)))
149               (multiple-value-bind (ignore count) (values-types rtype)
150                 (declare (ignore ignore))
151                 (when (eq count :unknown)
152                   (let ((*compiler-error-context* (lambda-bind fun)))
153                     (compiler-note
154                      "Return type not fixed values, so can't use known return ~
155                       convention:~%  ~S"
156                      (type-specifier rtype)))
157                   (return)))))))))
158   (values))
159
160 ;;; Return a RETURN-INFO structure describing how we should return
161 ;;; from functions in the specified tail set. We use the unknown
162 ;;; values convention if the number of values is unknown, or if it is
163 ;;; a good idea for some other reason. Otherwise we allocate passing
164 ;;; locations for a fixed number of values.
165 (defun return-info-for-set (tails)
166   (declare (type tail-set tails))
167   (multiple-value-bind (types count) (values-types (tail-set-type tails))
168     (let ((ptypes (mapcar #'primitive-type types))
169           (use-standard (use-standard-returns tails)))
170       (when (and (eq count :unknown) (not use-standard))
171         (return-value-efficiency-note tails))
172       (if (or (eq count :unknown) use-standard)
173           (make-return-info :kind :unknown
174                             :count count
175                             :types ptypes)
176           (make-return-info :kind :fixed
177                             :count count
178                             :types ptypes
179                             :locations (mapcar #'make-normal-tn ptypes))))))
180
181 ;;; If TAIL-SET doesn't have any INFO, then make a RETURN-INFO for it.
182 ;;; If we choose a return convention other than :UNKNOWN, and this
183 ;;; environment is for an XEP, then break tail recursion on the XEP
184 ;;; calls, since we must always use unknown values when returning from
185 ;;; an XEP.
186 (defun assign-return-locations (fun)
187   (declare (type clambda fun))
188   (let* ((tails (lambda-tail-set fun))
189          (returns (or (tail-set-info tails)
190                       (setf (tail-set-info tails)
191                             (return-info-for-set tails))))
192          (return (lambda-return fun)))
193     (when (and return
194                (not (eq (return-info-kind returns) :unknown))
195                (xep-p fun))
196       (do-uses (use (return-result return))
197         (setf (node-tail-p use) nil))))
198   (values))
199
200 ;;; Make an IR2-NLX-INFO structure for each NLX entry point recorded.
201 ;;; We call a VM supplied function to make the SAVE-SP restricted on
202 ;;; the stack. The NLX-ENTRY VOP's :FORCE-TO-STACK SAVE-P value
203 ;;; doesn't do this, since the SP is an argument to the VOP, and thus
204 ;;; isn't live afterwards.
205 (defun assign-ir2-nlx-info (fun)
206   (declare (type clambda fun))
207   (let ((physenv (lambda-physenv fun)))
208     (dolist (nlx (physenv-nlx-info physenv))
209       (setf (nlx-info-info nlx)
210             (make-ir2-nlx-info
211              :home (when (member (cleanup-kind (nlx-info-cleanup nlx))
212                                  '(:block :tagbody))
213                      (make-normal-tn *backend-t-primitive-type*))
214              :save-sp (make-nlx-sp-tn physenv)))))
215   (values))