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 (file-comment
  18   "$Header$")
  19
  20 ;;; We make a pass over the component's environments, assigning argument
  21 ;;; passing locations and return conventions and TNs for local variables.
  22 (defun gtn-analyze (component)
  23   (setf (component-info component) (make-ir2-component))
  24   (let ((funs (component-lambdas component)))
  25     (dolist (fun funs)
  26       (assign-ir2-environment fun)
  27       (assign-return-locations fun)
  28       (assign-ir2-nlx-info fun)
  29       (assign-lambda-var-tns fun nil)
  30       (dolist (let (lambda-lets fun))
  31         (assign-lambda-var-tns let t))))
  32
  33   (values))
  34
  35 ;;; We have to allocate the home TNs for variables before we can call
  36 ;;; Assign-IR2-Environment so that we can close over TNs that haven't had their
  37 ;;; home environment assigned yet. Here we evaluate the DEBUG-INFO/SPEED
  38 ;;; tradeoff to determine how variables are allocated. If SPEED is 3, then all
  39 ;;; variables are subject to lifetime analysis. Otherwise, only Let-P variables
  40 ;;; are allocated normally, and that can be inhibited by DEBUG-INFO = 3.
  41 (defun assign-lambda-var-tns (fun let-p)
  42   (declare (type clambda fun))
  43   (dolist (var (lambda-vars fun))
  44     (when (leaf-refs var)
  45       (let* ((type (if (lambda-var-indirect var)
  46                        *backend-t-primitive-type*
  47                        (primitive-type (leaf-type var))))
  48              (temp (make-normal-tn type))
  49              (node (lambda-bind fun))
  50              (res (if (or (and let-p (policy node (< debug 3)))
  51                           (policy node (zerop debug))
  52                           (policy node (= speed 3)))
  53                       temp
  54                       (environment-debug-live-tn temp
  55                                                  (lambda-environment fun)))))
  56         (setf (tn-leaf res) var)
  57         (setf (leaf-info var) res))))
  58   (values))
  59
  60 ;;; Give an IR2-Environment structure to Fun. We make the TNs which hold
  61 ;;; environment values and the old-FP/return-PC.
  62 (defun assign-ir2-environment (fun)
  63   (declare (type clambda fun))
  64   (let ((env (lambda-environment fun)))
  65     (collect ((env))
  66       (dolist (thing (environment-closure env))
  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           (env (cons thing (make-normal-tn ptype)))))
  74
  75       (let ((res (make-ir2-environment
  76                   :environment (env)
  77                   :return-pc-pass (make-return-pc-passing-location
  78                                    (external-entry-point-p fun)))))
  79         (setf (environment-info env) res)
  80         (setf (ir2-environment-old-fp res)
  81               (make-old-fp-save-location env))
  82         (setf (ir2-environment-return-pc res)
  83               (make-return-pc-save-location env)))))
  84
  85   (values))
  86
  87 ;;; Return true if Fun's result continuation is used in a TR full call. We
  88 ;;; only consider explicit :Full calls. It is assumed that known calls are
  89 ;;; never part of a tail-recursive loop, so we don't need to enforce
  90 ;;; tail-recursion. In any case, we don't know which known calls will
  91 ;;; actually be full calls until after LTN.
  92 (defun has-full-call-use (fun)
  93   (declare (type clambda fun))
  94   (let ((return (lambda-return fun)))
  95     (and return
  96          (do-uses (use (return-result return) nil)
  97            (when (and (node-tail-p use)
  98                       (basic-combination-p use)
  99                       (eq (basic-combination-kind use) :full))
 100              (return t))))))
 101
 102 ;;; Return true if we should use the standard (unknown) return convention
 103 ;;; for a tail-set. We use the standard return convention when:
 104 ;;; -- We must use the standard convention to preserve tail-recursion, since
 105 ;;;    the tail-set contains both an XEP and a TR full call.
 106 ;;; -- It appears to be more efficient to use the standard convention, since
 107 ;;;    there are no non-TR local calls that could benefit from a non-standard
 108 ;;;    convention.
 109 (defun use-standard-returns (tails)
 110   (declare (type tail-set tails))
 111   (let ((funs (tail-set-functions tails)))
 112     (or (and (find-if #'external-entry-point-p funs)
 113              (find-if #'has-full-call-use funs))
 114         (block punt
 115           (dolist (fun funs t)
 116             (dolist (ref (leaf-refs fun))
 117               (let* ((cont (node-cont ref))
 118                      (dest (continuation-dest cont)))
 119                 (when (and dest
 120                            (not (node-tail-p dest))
 121                            (basic-combination-p dest)
 122                            (eq (basic-combination-fun dest) cont)
 123                            (eq (basic-combination-kind dest) :local))
 124                   (return-from punt nil)))))))))
 125
 126 ;;; If policy indicates, give an efficency note about our inability to use
 127 ;;; the known return convention. We try to find a function in the tail set
 128 ;;; with non-constant return values to use as context. If there is no such
 129 ;;; function, then be more vague.
 130 (defun return-value-efficency-note (tails)
 131   (declare (type tail-set tails))
 132   (let ((funs (tail-set-functions tails)))
 133     (when (policy (lambda-bind (first funs)) (> (max speed space) brevity))
 134       (dolist (fun funs
 135                    (let ((*compiler-error-context* (lambda-bind (first funs))))
 136                      (compiler-note
 137                       "Return value count mismatch prevents known return ~
 138                        from these functions:~
 139                        ~{~%  ~A~}"
 140                       (remove nil (mapcar #'leaf-name funs)))))
 141         (let ((ret (lambda-return fun)))
 142           (when ret
 143             (let ((rtype (return-result-type ret)))
 144               (multiple-value-bind (ignore count) (values-types rtype)
 145                 (declare (ignore ignore))
 146                 (when (eq count :unknown)
 147                   (let ((*compiler-error-context* (lambda-bind fun)))
 148                     (compiler-note
 149                      "Return type not fixed values, so can't use known return ~
 150                       convention:~%  ~S"
 151                      (type-specifier rtype)))
 152                   (return)))))))))
 153   (values))
 154
 155 ;;; Return a Return-Info structure describing how we should return from
 156 ;;; functions in the specified tail set. We use the unknown values convention
 157 ;;; if the number of values is unknown, or if it is a good idea for some other
 158 ;;; reason. Otherwise we allocate passing locations for a fixed number of
 159 ;;; values.
 160 (defun return-info-for-set (tails)
 161   (declare (type tail-set tails))
 162   (multiple-value-bind (types count) (values-types (tail-set-type tails))
 163     (let ((ptypes (mapcar #'primitive-type types))
 164           (use-standard (use-standard-returns tails)))
 165       (when (and (eq count :unknown) (not use-standard))
 166         (return-value-efficency-note tails))
 167       (if (or (eq count :unknown) use-standard)
 168           (make-return-info :kind :unknown
 169                             :count count
 170                             :types ptypes)
 171           (make-return-info :kind :fixed
 172                             :count count
 173                             :types ptypes
 174                             :locations (mapcar #'make-normal-tn ptypes))))))
 175
 176 ;;; If Tail-Set doesn't have any Info, then make a Return-Info for it. If
 177 ;;; we choose a return convention other than :Unknown, and this environment is
 178 ;;; for an XEP, then break tail recursion on the XEP calls, since we must
 179 ;;; always use unknown values when returning from an XEP.
 180 (defun assign-return-locations (fun)
 181   (declare (type clambda fun))
 182   (let* ((tails (lambda-tail-set fun))
 183          (returns (or (tail-set-info tails)
 184                       (setf (tail-set-info tails)
 185                             (return-info-for-set tails))))
 186          (return (lambda-return fun)))
 187     (when (and return
 188                (not (eq (return-info-kind returns) :unknown))
 189                (external-entry-point-p fun))
 190       (do-uses (use (return-result return))
 191         (setf (node-tail-p use) nil))))
 192   (values))
 193
 194 ;;; Make an IR2-NLX-Info structure for each NLX entry point recorded. We
 195 ;;; call a VM supplied function to make the Save-SP restricted on the stack.
 196 ;;; The NLX-Entry VOP's :Force-To-Stack Save-P value doesn't do this, since the
 197 ;;; SP is an argument to the VOP, and thus isn't live afterwards.
 198 (defun assign-ir2-nlx-info (fun)
 199   (declare (type clambda fun))
 200   (let ((env (lambda-environment fun)))
 201     (dolist (nlx (environment-nlx-info env))
 202       (setf (nlx-info-info nlx)
 203             (make-ir2-nlx-info
 204              :home (when (member (cleanup-kind (nlx-info-cleanup nlx))
 205                                  '(:block :tagbody))
 206                      (make-normal-tn *backend-t-primitive-type*))
 207              :save-sp (make-nlx-sp-tn env)))))
 208   (values))