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
6 ;;;; This software is part of the SBCL system. See the README file for
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.
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)))
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))))
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))
43 (let* ((type (if (lambda-var-indirect var)
44 *backend-t-primitive-type*
45 (primitive-type (leaf-type var))))
46 (res (make-normal-tn type))
47 (node (lambda-bind fun))
48 (debug-variable-p (not (or (and let-p (policy node (< debug 3)))
49 (policy node (zerop debug))
50 (policy node (= speed 3))))))
52 ((and (lambda-var-indirect var)
53 (not (lambda-var-explicit-value-cell var)))
54 ;; Force closed-over indirect LAMBDA-VARs without explicit
55 ;; VALUE-CELLs to the stack, and make sure that they are
56 ;; live over the dynamic contour of the physenv.
57 (setf (tn-sc res) (svref *backend-sc-numbers*
58 sb!vm:control-stack-sc-number))
59 ;; KLUDGE: In the case of a tail-local-call, the entire
60 ;; stack frame is overwritten by the physenv of the called
61 ;; function. Unfortunately, the tail-call appears to end
62 ;; the dynamic contour of the physenv, meaning that the
63 ;; stack slot occupied by the LAMBDA-VAR may be reassigned.
64 ;; Ideally, we might make the TN physenv-live across the
65 ;; physenvs of the tail-set of the lambda, but as a stopgap
66 ;; we can make it component-live instead.
67 (component-live-tn res)
69 (physenv-live-tn res (lambda-physenv fun)))
72 (physenv-debug-live-tn res (lambda-physenv fun))))
74 (setf (tn-leaf res) var)
75 (setf (leaf-info var) res))))
78 ;;; Give CLAMBDA an IR2-PHYSENV structure. (And in order to
79 ;;; properly initialize the new structure, we make the TNs which hold
80 ;;; environment values and the old-FP/return-PC.)
81 (defun assign-ir2-physenv (clambda)
82 (declare (type clambda clambda))
83 (let ((lambda-physenv (lambda-physenv clambda))
84 (reversed-ir2-physenv-alist nil))
85 ;; FIXME: should be MAPCAR, not DOLIST
86 (dolist (thing (physenv-closure lambda-physenv))
87 (let ((ptype (etypecase thing
89 (if (lambda-var-indirect thing)
90 *backend-t-primitive-type*
91 (primitive-type (leaf-type thing))))
92 (nlx-info *backend-t-primitive-type*)
93 (clambda *backend-t-primitive-type*))))
94 (push (cons thing (make-normal-tn ptype))
95 reversed-ir2-physenv-alist)))
97 (let ((res (make-ir2-physenv
98 :closure (nreverse reversed-ir2-physenv-alist)
99 :return-pc-pass (make-return-pc-passing-location
101 (setf (physenv-info lambda-physenv) res)
102 (setf (ir2-physenv-old-fp res)
103 (make-old-fp-save-location lambda-physenv))
104 (setf (ir2-physenv-return-pc res)
105 (make-return-pc-save-location lambda-physenv))))
109 ;;; Return true if FUN's result is used in a tail-recursive full
110 ;;; call. We only consider explicit :FULL calls. It is assumed that
111 ;;; known calls are never part of a tail-recursive loop, so we don't
112 ;;; need to enforce tail-recursion. In any case, we don't know which
113 ;;; known calls will actually be full calls until after LTN.
114 (defun has-full-call-use (fun)
115 (declare (type clambda fun))
116 (let ((return (lambda-return fun)))
118 (do-uses (use (return-result return) nil)
119 (when (and (node-tail-p use)
120 (basic-combination-p use)
121 (eq (basic-combination-kind use) :full))
124 ;;; Return true if we should use the standard (unknown) return
125 ;;; convention for a TAIL-SET. We use the standard return convention
127 ;;; -- We must use the standard convention to preserve tail-recursion,
128 ;;; since the TAIL-SET contains both an XEP and a TR full call.
129 ;;; -- It appears to be more efficient to use the standard convention,
130 ;;; since there are no non-TR local calls that could benefit from
131 ;;; a non-standard convention.
132 ;;; -- We're compiling with RETURN-FROM-FRAME instrumentation, which
133 ;;; only works (on x86 and x86-64) for the standard convention.
134 (defun use-standard-returns (tails)
135 (declare (type tail-set tails))
136 (let ((funs (tail-set-funs tails)))
137 (or (and (find-if #'xep-p funs)
138 (find-if #'has-full-call-use funs))
139 (some (lambda (fun) (policy fun (>= insert-debug-catch 2))) funs)
142 (dolist (ref (leaf-refs fun))
143 (let* ((lvar (node-lvar ref))
144 (dest (and lvar (lvar-dest lvar))))
145 (when (and (basic-combination-p dest)
146 (not (node-tail-p dest))
147 (eq (basic-combination-fun dest) lvar)
148 (eq (basic-combination-kind dest) :local))
149 (return-from punt nil)))))))))
151 ;;; If policy indicates, give an efficiency note about our inability to
152 ;;; use the known return convention. We try to find a function in the
153 ;;; tail set with non-constant return values to use as context. If
154 ;;; there is no such function, then be more vague.
155 (defun return-value-efficiency-note (tails)
156 (declare (type tail-set tails))
157 (let ((funs (tail-set-funs tails)))
158 (when (policy (lambda-bind (first funs))
162 (let ((*compiler-error-context* (lambda-bind (first funs))))
164 "Return value count mismatch prevents known return ~
165 from these functions:~
167 (mapcar #'leaf-source-name
168 (remove-if-not #'leaf-has-source-name-p funs)))))
169 (let ((ret (lambda-return fun)))
171 (let ((rtype (return-result-type ret)))
172 (multiple-value-bind (ignore count) (values-types rtype)
173 (declare (ignore ignore))
174 (when (eq count :unknown)
175 (let ((*compiler-error-context* (lambda-bind fun)))
177 "Return type not fixed values, so can't use known return ~
179 (type-specifier rtype)))
183 ;;; Return a RETURN-INFO structure describing how we should return
184 ;;; from functions in the specified tail set. We use the unknown
185 ;;; values convention if the number of values is unknown, or if it is
186 ;;; a good idea for some other reason. Otherwise we allocate passing
187 ;;; locations for a fixed number of values.
188 (defun return-info-for-set (tails)
189 (declare (type tail-set tails))
190 (multiple-value-bind (types count) (values-types (tail-set-type tails))
191 (let ((ptypes (mapcar #'primitive-type types))
192 (use-standard (use-standard-returns tails)))
193 (when (and (eq count :unknown) (not use-standard)
194 (not (eq (tail-set-type tails) *empty-type*)))
195 (return-value-efficiency-note tails))
196 (if (or (eq count :unknown) use-standard)
197 (make-return-info :kind :unknown
200 (make-return-info :kind :fixed
203 :locations (mapcar #'make-normal-tn ptypes))))))
205 ;;; If TAIL-SET doesn't have any INFO, then make a RETURN-INFO for it.
206 ;;; If we choose a return convention other than :UNKNOWN, and this
207 ;;; environment is for an XEP, then break tail recursion on the XEP
208 ;;; calls, since we must always use unknown values when returning from
210 (defun assign-return-locations (fun)
211 (declare (type clambda fun))
212 (let* ((tails (lambda-tail-set fun))
213 (returns (or (tail-set-info tails)
214 (setf (tail-set-info tails)
215 (return-info-for-set tails))))
216 (return (lambda-return fun)))
218 (not (eq (return-info-kind returns) :unknown))
220 (do-uses (use (return-result return))
221 (setf (node-tail-p use) nil))))
224 ;;; Make an IR2-NLX-INFO structure for each NLX entry point recorded.
225 ;;; We call a VM supplied function to make the SAVE-SP restricted on
226 ;;; the stack. The NLX-ENTRY VOP's :FORCE-TO-STACK SAVE-P value
227 ;;; doesn't do this, since the SP is an argument to the VOP, and thus
228 ;;; isn't live afterwards.
229 (defun assign-ir2-nlx-info (fun)
230 (declare (type clambda fun))
231 (let ((physenv (lambda-physenv fun)))
232 (dolist (nlx (physenv-nlx-info physenv))
233 (setf (nlx-info-info nlx)
235 :home (when (member (cleanup-kind (nlx-info-cleanup nlx))
237 (if (nlx-info-safe-p nlx)
238 (make-normal-tn *backend-t-primitive-type*)
239 (make-stack-pointer-tn)))
240 :save-sp (make-nlx-sp-tn physenv)))))