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-environment 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-ENVIRONMENT 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                       (environment-debug-live-tn temp
  53                                                  (lambda-environment fun)))))
  54         (setf (tn-leaf res) var)
  55         (setf (leaf-info var) res))))
  56   (values))
  57
  58 ;;; Give CLAMBDA an IR2-ENVIRONMENT structure. (And in order to
  59 ;;; properly initialize the new structure, we make the TNs which hold
  60 ;;; environment values and the old-FP/return-PC.)
  61 (defun assign-ir2-environment (clambda)
  62   (declare (type clambda clambda))
  63   (let ((lambda-environment (lambda-environment clambda))
  64         (reversed-ir2-environment-alist nil))
  65     ;; FIXME: should be MAPCAR, not DOLIST
  66     (dolist (thing (environment-closure lambda-environment))
  67       (let ((ptype (etypecase thing
  68                      (lambda-var
  69                       (if (lambda-var-indirect thing)
  70                           *backend-t-primitive-type*
  71                           (primitive-type (leaf-type thing))))
  72                      (nlx-info *backend-t-primitive-type*))))
  73         (push (cons thing (make-normal-tn ptype))
  74               reversed-ir2-environment-alist)))
  75
  76     (let ((res (make-ir2-environment
  77                 :environment (nreverse reversed-ir2-environment-alist)
  78                 :return-pc-pass (make-return-pc-passing-location
  79                                  (external-entry-point-p clambda)))))
  80       (setf (environment-info lambda-environment) res)
  81       (setf (ir2-environment-old-fp res)
  82             (make-old-fp-save-location lambda-environment))
  83       (setf (ir2-environment-return-pc res)
  84             (make-return-pc-save-location lambda-environment))))
  85
  86   (values))
  87
  88 ;;; Return true if FUN's result continuation is used in a
  89 ;;; tail-recursive full call. We only consider explicit :FULL calls.
  90 ;;; It is assumed that known calls are never part of a tail-recursive
  91 ;;; loop, so we don't need to enforce tail-recursion. In any case, we
  92 ;;; don't know which known calls will actually be full calls until
  93 ;;; after LTN.
  94 (defun has-full-call-use (fun)
  95   (declare (type clambda fun))
  96   (let ((return (lambda-return fun)))
  97     (and return
  98          (do-uses (use (return-result return) nil)
  99            (when (and (node-tail-p use)
 100                       (basic-combination-p use)
 101                       (eq (basic-combination-kind use) :full))
 102              (return t))))))
 103
 104 ;;; Return true if we should use the standard (unknown) return
 105 ;;; convention for a TAIL-SET. We use the standard return convention
 106 ;;; when:
 107 ;;; -- We must use the standard convention to preserve tail-recursion,
 108 ;;;    since the TAIL-SET contains both an XEP and a TR full call.
 109 ;;; -- It appears to be more efficient to use the standard convention,
 110 ;;;    since there are no non-TR local calls that could benefit from
 111 ;;;    a non-standard convention.
 112 (defun use-standard-returns (tails)
 113   (declare (type tail-set tails))
 114   (let ((funs (tail-set-functions tails)))
 115     (or (and (find-if #'external-entry-point-p funs)
 116              (find-if #'has-full-call-use funs))
 117         (block punt
 118           (dolist (fun funs t)
 119             (dolist (ref (leaf-refs fun))
 120               (let* ((cont (node-cont ref))
 121                      (dest (continuation-dest cont)))
 122                 (when (and dest
 123                            (not (node-tail-p dest))
 124                            (basic-combination-p dest)
 125                            (eq (basic-combination-fun dest) cont)
 126                            (eq (basic-combination-kind dest) :local))
 127                   (return-from punt nil)))))))))
 128
 129 ;;; If policy indicates, give an efficiency note about our inability to
 130 ;;; use the known return convention. We try to find a function in the
 131 ;;; tail set with non-constant return values to use as context. If
 132 ;;; there is no such function, then be more vague.
 133 (defun return-value-efficiency-note (tails)
 134   (declare (type tail-set tails))
 135   (let ((funs (tail-set-functions tails)))
 136     (when (policy (lambda-bind (first funs))
 137                   (> (max speed space)
 138                      inhibit-warnings))
 139       (dolist (fun funs
 140                    (let ((*compiler-error-context* (lambda-bind (first funs))))
 141                      (compiler-note
 142                       "Return value count mismatch prevents known return ~
 143                        from these functions:~
 144                        ~{~%  ~A~}"
 145                       (remove nil (mapcar #'leaf-name 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                (external-entry-point-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 ((env (lambda-environment fun)))
 208     (dolist (nlx (environment-nlx-info env))
 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 env)))))
 215   (values))