| blob | 8844aeb59e96a8f82c92683c762c0565c5329516 |
1 ;;;; This file implements the constraint propagation phase of the
2 ;;;; compiler, which uses global flow analysis to obtain dynamic type
3 ;;;; information.
5 ;;;; This software is part of the SBCL system. See the README file for
6 ;;;; more information.
7 ;;;;
8 ;;;; This software is derived from the CMU CL system, which was
9 ;;;; written at Carnegie Mellon University and released into the
10 ;;;; public domain. The software is in the public domain and is
11 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
12 ;;;; files for more information.
14 ;;; TODO:
15 ;;;
16 ;;; -- documentation
17 ;;;
18 ;;; -- MV-BIND, :ASSIGNMENT
20 ;;; Problems:
21 ;;;
22 ;;; -- Constraint propagation badly interacts with bottom-up type
23 ;;; inference. Consider
24 ;;;
25 ;;; (defun foo (n &aux (i 42))
26 ;;; (declare (optimize speed))
27 ;;; (declare (fixnum n)
28 ;;; #+nil (type (integer 0) i))
29 ;;; (tagbody
30 ;;; (setq i 0)
31 ;;; :loop
32 ;;; (when (>= i n) (go :exit))
33 ;;; (setq i (1+ i))
34 ;;; (go :loop)
35 ;;; :exit))
36 ;;;
37 ;;; In this case CP cannot even infer that I is of class INTEGER.
38 ;;;
39 ;;; -- In the above example if we place the check after SETQ, CP will
40 ;;; fail to infer (< I FIXNUM): is does not understand that this
41 ;;; constraint follows from (TYPEP I (INTEGER 0 0)).
43 ;;; BUGS:
44 ;;;
45 ;;; -- this code does not check whether SET appears between REF and a
46 ;;; test (bug 233b)
54 ;; the kind of constraint we have:
55 ;;
56 ;; TYPEP
57 ;; X is a LAMBDA-VAR and Y is a CTYPE. The value of X is
58 ;; constrained to be of type Y.
59 ;;
60 ;; > or <
61 ;; X is a lambda-var and Y is a CTYPE. The relation holds
62 ;; between X and some object of type Y.
63 ;;
64 ;; EQL
65 ;; X is a LAMBDA-VAR Y is a LAMBDA-VAR or a CONSTANT. The
66 ;; relation is asserted to hold.
68 ;; The operands to the relation.
71 ;; If true, negates the sense of the constraint, so the relation
72 ;; does *not* hold.
77 ;;; Return a constraint for the specified arguments. We only create a
78 ;;; new constraint if there isn't already an equivalent old one,
79 ;;; guaranteeing that all equivalent constraints are EQ. This
80 ;;; shouldn't be called on LAMBDA-VARs with no CONSTRAINTS set.
104 cx)
105 y)))
111 new)))
113 ;;; If REF is to a LAMBDA-VAR with CONSTRAINTs (i.e. we can do flow
114 ;;; analysis on it), then return the LAMBDA-VAR, otherwise NIL.
121 leaf)))
123 ;;; If LVAR's USE is a REF, then return OK-REF-LAMBDA-VAR of the USE,
124 ;;; otherwise NIL.
132 ;;;; Searching constraints
134 ;;; Add the indicated test constraint to BLOCK, marking the block as
135 ;;; having a new assertion when the constriant was not already
136 ;;; present. We don't add the constraint if the block has multiple
137 ;;; predecessors, since it only holds on this particular path.
147 ;;; Add complementary constraints to the consequent and alternative
148 ;;; blocks of IF. We do nothing if X is NIL.
151 ;; Note: Even if we do (IF test exp exp) => (PROGN test exp)
152 ;; optimization, the *MAX-OPTIMIZE-ITERATIONS* cutoff means
153 ;; that we can't guarantee that the optimization will be
154 ;; done, so we still need to avoid barfing on this case.
161 ;;; Add test constraints to the consequent and alternative blocks of
162 ;;; the test represented by USE.
183 val
185 nil)))))
197 nil)))))
198 ((< >)
205 nil))
209 nil))))
215 ptype nil)))))))))
218 ;;; Set the TEST-CONSTRAINT in the successors of BLOCK according to
219 ;;; the condition it tests.
231 ;;;; Applying constraints
233 ;;; Return true if X is an integer NUMERIC-TYPE.
240 ;;; Given that an inequality holds on values of type X and Y, return a
241 ;;; new type for X. If GREATER is true, then X was greater than Y,
242 ;;; otherwise less. If OR-EQUAL is true, then the inequality was
243 ;;; inclusive, i.e. >=.
244 ;;;
245 ;;; If GREATER (or not), then we max (or min) in Y's lower (or upper)
246 ;;; bound into X and return that result. If not OR-EQUAL, we can go
247 ;;; one greater (less) than Y's bound.
267 ;;; Return true if X is a float NUMERIC-TYPE.
274 ;;; Exactly the same as CONSTRAIN-INTEGER-TYPE, but for float numbers.
282 x
290 x))
293 x
298 ;; Both X and Y are not null. Find the max.
300 ;; An open lower bound is greater than a close
301 ;; lower bound because the open bound doesn't
302 ;; contain the bound, so choose an open lower
303 ;; bound.
306 ;; Same as above, but for the min of upper bounds
307 ;; Both X and Y are not null. Find the min.
309 ;; An open upper bound is less than a closed
310 ;; upper bound because the open bound doesn't
311 ;; contain the bound, so choose an open lower
312 ;; bound.
317 y-bound)
319 x-bound)
328 ;;; Given the set of CONSTRAINTS for a variable and the current set of
329 ;;; restrictions from flow analysis IN, set the type for REF
330 ;;; accordingly.
362 ((< >)
373 )))))
383 res)))))))
387 ;;;; Flow analysis
389 ;;; Local propagation
390 ;;; -- [TODO: For any LAMBDA-VAR ref with a type check, add that
391 ;;; constraint.]
392 ;;; -- For any LAMBDA-VAR set, delete all constraints on that var; add
393 ;;; a type constraint based on the new value type.
397 sset)
398 constraint-propagate-in-block))
416 ;; if VAR has no SETs, type inference is
417 ;; fully performed by IR1 optimizer
443 gen)
445 ;;; BLOCK-KILL is just a list of the LAMBDA-VARs killed, so we must
446 ;;; compute the kill set when there are any vars killed. We bum this a
447 ;;; bit by special-casing when only one var is killed, and just using
448 ;;; that var's constraints as the kill set. This set could possibly be
449 ;;; precomputed, but it would have to be invalidated whenever any
450 ;;; constraint is added, which would be a pain.
470 out))
472 ;;; Compute the initial flow analysis sets for BLOCK:
473 ;;; -- Compute IN/OUT sets; if OUT of a predecessor is not yet
474 ;;; computed, assume it to be a universal set (this is only
475 ;;; possible in a loop)
476 ;;;
477 ;;; Return T if we have found a loop.
503 loop-p))))
505 ;;; BLOCK-IN becomes the intersection of the OUT of the predecessors.
506 ;;; Our OUT is:
507 ;;; gen U (in - kill)
508 ;;;
509 ;;; Return True if we have done something.
516 res))))
520 nil
523 ;;; Deliver the results of constraint propagation to REFs in BLOCK.
524 ;;; During this pass, we also do local constraint propagation by
525 ;;; adding in constraints as we seem them during the pass through the
526 ;;; block.
536 ;;; Give an empty constraints set to any var that doesn't have one and
537 ;;; isn't a set closure var. Since a var that we previously rejected
538 ;;; looks identical to one that is new, so we optimistically keep
539 ;;; hoping that vars stop being closed over or lose their sets.
553 ;;; How many blocks does COMPONENT have?
559 result))
578 ;; something is wrong.