1 ;;;; This file contains the control analysis pass in the compiler.
2 ;;;; This pass determines the order in which the IR2 blocks are to be
3 ;;;; emitted, attempting to minimize the associated branching costs.
5 ;;;; At this point, we commit to generating IR2 (and ultimately
6 ;;;; assembler) for reachable blocks. Before this phase there might be
7 ;;;; blocks that are unreachable but still appear in the DFO, due in
8 ;;;; inadequate optimization, etc.
10 ;;;; This software is part of the SBCL system. See the README file for
11 ;;;; more information.
13 ;;;; This software is derived from the CMU CL system, which was
14 ;;;; written at Carnegie Mellon University and released into the
15 ;;;; public domain. The software is in the public domain and is
16 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
17 ;;;; files for more information.
21 ;;; Insert BLOCK in the emission order after the block AFTER.
22 (defun add-to-emit-order (block after
)
23 (declare (type block-annotation block after
))
24 (let ((next (block-annotation-next after
)))
25 (setf (block-annotation-next after
) block
)
26 (setf (block-annotation-prev block
) after
)
27 (setf (block-annotation-next block
) next
)
28 (setf (block-annotation-prev next
) block
))
31 ;;; If BLOCK looks like the head of a loop, then attempt to rotate it.
32 ;;; A block looks like a loop head if the number of some predecessor
33 ;;; is less than the block's number. Since blocks are numbered in
34 ;;; reverse DFN, this will identify loop heads in a reducible flow
37 ;;; When we find a suspected loop head, we scan back from the tail to
38 ;;; find an alternate loop head. This substitution preserves the
39 ;;; correctness of the walk, since the old head can be reached from
40 ;;; the new head. We determine the new head by scanning as far back as
41 ;;; we can find increasing block numbers. Beats me if this is in
42 ;;; general optimal, but it works in simple cases.
44 ;;; This optimization is inhibited in functions with NLX EPs, since it
45 ;;; is hard to do this without possibly messing up the special-case
46 ;;; walking from NLX EPs described in CONTROL-ANALYZE-1-FUN. We also
47 ;;; suppress rotation of loop heads which are the start of a function
48 ;;; (i.e. tail calls), as the debugger wants functions to start at the
50 (defun find-rotated-loop-head (block)
51 (declare (type cblock block
))
52 (let* ((num (block-number block
))
53 (env (block-physenv block
))
54 (pred (dolist (pred (block-pred block
) nil
)
55 (when (and (not (block-flag pred
))
56 (eq (block-physenv pred
) env
)
57 (< (block-number pred
) num
))
61 (not (physenv-nlx-info env
))
62 (not (eq (lambda-block (block-home-lambda block
)) block
)))
64 (current-num (block-number pred
)))
67 (dolist (pred (block-pred current
) (return-from DONE
))
70 (when (and (not (block-flag pred
))
71 (eq (block-physenv pred
) env
)
72 (> (block-number pred
) current-num
))
73 (setq current pred current-num
(block-number pred
))
75 (aver (not (block-flag current
)))
80 ;;; Do a graph walk linking blocks into the emit order as we go. We
81 ;;; call FIND-ROTATED-LOOP-HEAD to do while-loop optimization.
83 ;;; We treat blocks ending in tail local calls to other environments
84 ;;; specially. We can't walked the called function immediately, since
85 ;;; it is in a different function and we must keep the code for a
86 ;;; function contiguous. Instead, we return the function that we want
87 ;;; to call so that it can be walked as soon as possible, which is
88 ;;; hopefully immediately.
90 ;;; If any of the recursive calls ends in a tail local call, then we
91 ;;; return the last such function, since it is the only one we can
92 ;;; possibly drop through to. (But it doesn't have to be from the last
93 ;;; block walked, since that call might not have added anything.)
95 ;;; We defer walking successors whose successor is the component tail
96 ;;; (end in an error, NLX or tail full call.) This is to discourage
97 ;;; making error code the drop-through.
98 (defun control-analyze-block (block tail block-info-constructor
)
99 (declare (type cblock block
)
100 (type block-annotation tail
)
101 (type function block-info-constructor
))
102 (unless (block-flag block
)
103 (let ((block (find-rotated-loop-head block
)))
104 (setf (block-flag block
) t
)
105 (aver (and (block-component block
) (not (block-delete-p block
))))
106 (add-to-emit-order (or (block-info block
)
107 (setf (block-info block
)
108 (funcall block-info-constructor block
)))
109 (block-annotation-prev tail
))
111 (let ((last (block-last block
)))
112 (cond ((and (combination-p last
) (node-tail-p last
)
113 (eq (basic-combination-kind last
) :local
)
114 (not (eq (node-physenv last
)
115 (lambda-physenv (combination-lambda last
)))))
116 (combination-lambda last
))
118 (let ((component-tail (component-tail (block-component block
)))
119 (block-succ (block-succ block
))
121 (dolist (succ block-succ
)
122 (unless (eq (first (block-succ succ
)) component-tail
)
123 (let ((res (control-analyze-block
124 succ tail block-info-constructor
)))
125 (when res
(setq fun res
)))))
126 (dolist (succ block-succ
)
127 (control-analyze-block succ tail block-info-constructor
))
130 ;;; Analyze all of the NLX EPs first to ensure that code reachable
131 ;;; only from a NLX is emitted contiguously with the code reachable
132 ;;; from the BIND. Code reachable from the BIND is inserted *before*
133 ;;; the NLX code so that the BIND marks the beginning of the code for
134 ;;; the function. If the walks from NLX EPs reach the BIND block, then
135 ;;; we just move it to the beginning.
137 ;;; If the walk from the BIND node encountered a tail local call, then
138 ;;; we start over again there to help the call drop through. Of
139 ;;; course, it will never get a drop-through if either function has
141 (defun control-analyze-1-fun (fun component block-info-constructor
)
142 (declare (type clambda fun
)
143 (type component component
)
144 (type function block-info-constructor
))
145 (let* ((tail-block (block-info (component-tail component
)))
146 (prev-block (block-annotation-prev tail-block
))
147 (bind-block (node-block (lambda-bind fun
))))
148 (unless (block-flag bind-block
)
149 (dolist (nlx (physenv-nlx-info (lambda-physenv fun
)))
150 (control-analyze-block (nlx-info-target nlx
) tail-block
151 block-info-constructor
))
153 ((block-flag bind-block
)
154 (let* ((block-note (block-info bind-block
))
155 (prev (block-annotation-prev block-note
))
156 (next (block-annotation-next block-note
)))
157 (setf (block-annotation-prev next
) prev
)
158 (setf (block-annotation-next prev
) next
)
159 (add-to-emit-order block-note prev-block
)))
161 (let ((new-fun (control-analyze-block bind-block
162 (block-annotation-next
164 block-info-constructor
)))
166 (control-analyze-1-fun new-fun component
167 block-info-constructor
)))))))
170 ;;; Do control analysis on COMPONENT, finding the emit order. Our only
171 ;;; cleverness here is that we walk XEP's first to increase the
172 ;;; probability that the tail call will be a drop-through.
174 ;;; When we are done, we delete blocks that weren't reached by the
175 ;;; walk. Some return blocks are made unreachable by LTN without
176 ;;; setting COMPONENT-REANALYZE. We remove all deleted blocks from the
177 ;;; IR2-COMPONENT VALUES-RECEIVERS to keep stack analysis from getting
179 (defevent control-deleted-block
"control analysis deleted dead block")
180 (defun control-analyze (component block-info-constructor
)
181 (declare (type component component
)
182 (type function block-info-constructor
))
183 (let* ((head (component-head component
))
184 (head-block (funcall block-info-constructor head
))
185 (tail (component-tail component
))
186 (tail-block (funcall block-info-constructor tail
)))
187 (setf (block-info head
) head-block
)
188 (setf (block-info tail
) tail-block
)
189 (setf (block-annotation-prev tail-block
) head-block
)
190 (setf (block-annotation-next head-block
) tail-block
)
192 (clear-flags component
)
194 (dolist (fun (component-lambdas component
))
196 (control-analyze-1-fun fun component block-info-constructor
)))
198 (dolist (fun (component-lambdas component
))
199 (control-analyze-1-fun fun component block-info-constructor
))
201 (do-blocks (block component
)
202 (unless (block-flag block
)
203 (event control-deleted-block
(block-start-node block
))
204 (delete-block block
))))
206 (let ((2comp (component-info component
)))
207 (when (ir2-component-p 2comp
)
208 ;; If it's not an IR2-COMPONENT, don't worry about it.
209 (setf (ir2-component-values-receivers 2comp
)
210 (delete-if-not #'block-component
211 (ir2-component-values-receivers 2comp
)))))