0.8.14.20: Documentation madness, yet again
[sbcl.git] / src / compiler / vop.lisp
1 ;;;; structures for the second (virtual machine) intermediate
2 ;;;; representation in the compiler, IR2
3
4 ;;;; This software is part of the SBCL system. See the README file for
5 ;;;; more information.
6 ;;;;
7 ;;;; This software is derived from the CMU CL system, which was
8 ;;;; written at Carnegie Mellon University and released into the
9 ;;;; public domain. The software is in the public domain and is
10 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
11 ;;;; files for more information.
12
13 (in-package "SB!C")
14
15 ;;; the largest number of TNs whose liveness changes that we can have
16 ;;; in any block
17 (def!constant local-tn-limit 64)
18
19 (deftype local-tn-number () `(integer 0 (,local-tn-limit)))
20 (deftype local-tn-count () `(integer 0 ,local-tn-limit))
21 (deftype local-tn-vector () `(simple-vector ,local-tn-limit))
22 (deftype local-tn-bit-vector () `(simple-bit-vector ,local-tn-limit))
23
24 ;;; type of an SC number
25 (deftype sc-number () `(integer 0 (,sc-number-limit)))
26
27 ;;; types for vectors indexed by SC numbers
28 (deftype sc-vector () `(simple-vector ,sc-number-limit))
29 (deftype sc-bit-vector () `(simple-bit-vector ,sc-number-limit))
30
31 ;;; the different policies we can use to determine the coding strategy
32 (deftype ltn-policy ()
33   '(member :safe :small :fast :fast-safe))
34 \f
35 ;;;; PRIMITIVE-TYPEs
36
37 ;;; A PRIMITIVE-TYPE is used to represent the aspects of type
38 ;;; interesting to the VM. Selection of IR2 translation templates is
39 ;;; done on the basis of the primitive types of the operands, and the
40 ;;; primitive type of a value is used to constrain the possible
41 ;;; representations of that value.
42 (defstruct (primitive-type (:copier nil))
43   ;; the name of this PRIMITIVE-TYPE
44   (name nil :type symbol)
45   ;; a list of the SC numbers for all the SCs that a TN of this type
46   ;; can be allocated in
47   (scs nil :type list)
48   ;; the Lisp type equivalent to this type. If this type could never be
49   ;; returned by PRIMITIVE-TYPE, then this is the NIL (or empty) type
50   (specifier (missing-arg) :type type-specifier)
51   ;; the template used to check that an object is of this type. This is a
52   ;; template of one argument and one result, both of primitive-type T. If
53   ;; the argument is of the correct type, then it is delivered into the
54   ;; result. If the type is incorrect, then an error is signalled.
55   (check nil :type (or template null)))
56
57 (defprinter (primitive-type)
58   name)
59 \f
60 ;;;; IR1 annotations used for IR2 conversion
61
62 ;;; BLOCK-INFO
63 ;;;    Holds the IR2-BLOCK structure. If there are overflow blocks,
64 ;;;    then this points to the first IR2-BLOCK. The BLOCK-INFO of the
65 ;;;    dummy component head and tail are dummy IR2 blocks that begin
66 ;;;    and end the emission order thread.
67 ;;;
68 ;;; COMPONENT-INFO
69 ;;;    Holds the IR2-COMPONENT structure.
70 ;;;
71 ;;; LVAR-INFO
72 ;;;    Holds the IR2-LVAR structure. LVARs whose values aren't used
73 ;;;    won't have any. XXX
74 ;;;
75 ;;; CLEANUP-INFO
76 ;;;    If non-null, then a TN in which the affected dynamic
77 ;;;    environment pointer should be saved after the binding is
78 ;;;    instantiated.
79 ;;;
80 ;;; PHYSENV-INFO
81 ;;;    Holds the IR2-PHYSENV structure.
82 ;;;
83 ;;; TAIL-SET-INFO
84 ;;;    Holds the RETURN-INFO structure.
85 ;;;
86 ;;; NLX-INFO-INFO
87 ;;;    Holds the IR2-NLX-INFO structure.
88 ;;;
89 ;;; LEAF-INFO
90 ;;;    If a non-set lexical variable, the TN that holds the value in
91 ;;;    the home environment. If a constant, then the corresponding
92 ;;;    constant TN. If an XEP lambda, then the corresponding
93 ;;;    Entry-Info structure.
94 ;;;
95 ;;; BASIC-COMBINATION-INFO
96 ;;;    The template chosen by LTN, or
97 ;;;     :FULL if this is definitely a full call.
98 ;;;     :FUNNY if this is an oddball thing with IR2-convert.
99 ;;;     :LOCAL if this is a local call.
100 ;;;
101 ;;; NODE-TAIL-P
102 ;;;    After LTN analysis, this is true only in combination nodes that are
103 ;;;    truly tail recursive.
104
105 ;;; An IR2-BLOCK holds information about a block that is used during
106 ;;; and after IR2 conversion. It is stored in the BLOCK-INFO slot for
107 ;;; the associated block.
108 (defstruct (ir2-block (:include block-annotation)
109                       (:constructor make-ir2-block (block))
110                       (:copier nil))
111   ;; the IR2-BLOCK's number, which differs from BLOCK's BLOCK-NUMBER
112   ;; if any blocks are split. This is assigned by lifetime analysis.
113   (number nil :type (or index null))
114   ;; information about unknown-values LVARs that is used by stack
115   ;; analysis to do stack simulation. An UNKNOWN-VALUES LVAR is PUSHED
116   ;; if its DEST is in another block. Similarly, a LVAR is POPPED if
117   ;; its DEST is in this block but has its uses elsewhere. The LVARs
118   ;; are in the order that are pushed/popped in the block. Note that
119   ;; the args to a single MV-COMBINATION appear reversed in POPPED,
120   ;; since we must effectively pop the last argument first. All pops
121   ;; must come before all pushes (although internal MV uses may be
122   ;; interleaved.) POPPED is computed by LTN, and PUSHED is computed
123   ;; by stack analysis.
124   (pushed () :type list)
125   (popped () :type list)
126   ;; the result of stack analysis: lists of all the unknown-values
127   ;; LVARs on the stack at the block start and end, topmost LVAR
128   ;; first.
129   (start-stack () :type list)
130   (end-stack () :type list)
131   ;; the first and last VOP in this block. If there are none, both
132   ;; slots are null.
133   (start-vop nil :type (or vop null))
134   (last-vop nil :type (or vop null))
135   ;; the number of local TNs actually allocated
136   (local-tn-count 0 :type local-tn-count)
137   ;; a vector that maps local TN numbers to TNs. Some entries may be
138   ;; NIL, indicating that that number is unused. (This allows us to
139   ;; delete local conflict information without compressing the LTN
140   ;; numbers.)
141   ;;
142   ;; If an entry is :MORE, then this block contains only a single VOP.
143   ;; This VOP has so many more arguments and/or results that they
144   ;; cannot all be assigned distinct LTN numbers. In this case, we
145   ;; assign all the more args one LTN number, and all the more results
146   ;; another LTN number. We can do this, since more operands are
147   ;; referenced simultaneously as far as conflict analysis is
148   ;; concerned. Note that all these :MORE TNs will be global TNs.
149   (local-tns (make-array local-tn-limit) :type local-tn-vector)
150   ;; Bit-vectors used during lifetime analysis to keep track of
151   ;; references to local TNs. When indexed by the LTN number, the
152   ;; index for a TN is non-zero in WRITTEN if it is ever written in
153   ;; the block, and in LIVE-OUT if the first reference is a read.
154   (written (make-array local-tn-limit :element-type 'bit
155                        :initial-element 0)
156            :type local-tn-bit-vector)
157   (live-out (make-array local-tn-limit :element-type 'bit)
158             :type local-tn-bit-vector)
159   ;; This is similar to the above, but is updated by lifetime flow
160   ;; analysis to have a 1 for LTN numbers of TNs live at the end of
161   ;; the block. This takes into account all TNs that aren't :LIVE.
162   (live-in (make-array local-tn-limit :element-type 'bit :initial-element 0)
163            :type local-tn-bit-vector)
164   ;; a thread running through the global-conflicts structures for this
165   ;; block, sorted by TN number
166   (global-tns nil :type (or global-conflicts null))
167   ;; the assembler label that points to the beginning of the code for
168   ;; this block, or NIL when we haven't assigned a label yet
169   (%label nil)
170   ;; list of LOCATION-INFO structures describing all the interesting
171   ;; (to the debugger) locations in this block
172   (locations nil :type list))
173
174 (defprinter (ir2-block)
175   (pushed :test pushed)
176   (popped :test popped)
177   (start-vop :test start-vop)
178   (last-vop :test last-vop)
179   (local-tn-count :test (not (zerop local-tn-count)))
180   (%label :test %label))
181
182 ;;; An IR2-LVAR structure is used to annotate LVARs that are used as a
183 ;;; function result LVARs or that receive MVs.
184 (defstruct (ir2-lvar
185             (:constructor make-ir2-lvar (primitive-type))
186             (:copier nil))
187   ;; If this is :DELAYED, then this is a single value LVAR for which
188   ;; the evaluation of the use is to be postponed until the evaluation
189   ;; of destination. This can be done for ref nodes or predicates
190   ;; whose destination is an IF.
191   ;;
192   ;; If this is :FIXED, then this LVAR has a fixed number of values,
193   ;; with the TNs in LOCS.
194   ;;
195   ;; If this is :UNKNOWN, then this is an unknown-values LVAR, using
196   ;; the passing locations in LOCS.
197   ;;
198   ;; If this is :UNUSED, then this LVAR should never actually be used
199   ;; as the destination of a value: it is only used tail-recursively.
200   (kind :fixed :type (member :delayed :fixed :unknown :unused))
201   ;; The primitive-type of the first value of this LVAR. This is
202   ;; primarily for internal use during LTN, but it also records the
203   ;; type restriction on delayed references. In multiple-value
204   ;; contexts, this is null to indicate that it is meaningless. This
205   ;; is always (primitive-type (lvar-type cont)), which may be more
206   ;; restrictive than the tn-primitive-type of the value TN. This is
207   ;; becase the value TN must hold any possible type that could be
208   ;; computed (before type checking.) XXX
209   (primitive-type nil :type (or primitive-type null))
210   ;; Locations used to hold the values of the LVAR. If the number of
211   ;; values if fixed, then there is one TN per value. If the number of
212   ;; values is unknown, then this is a two-list of TNs holding the
213   ;; start of the values glob and the number of values. Note that
214   ;; since type checking is the responsibility of the values receiver,
215   ;; these TNs primitive type is only based on the proven type
216   ;; information.
217   (locs nil :type list)
218   #!+stack-grows-downward-not-upward
219   (stack-pointer nil :type (or tn null)))
220 ;; For upward growing stack start of stack block and start of object
221 ;; differ only by lowtag.
222 #!-stack-grows-downward-not-upward
223 (defmacro ir2-lvar-stack-pointer (2lvar)
224   `(first (ir2-lvar-locs ,2lvar)))
225
226 (defprinter (ir2-lvar)
227   kind
228   primitive-type
229   locs)
230
231 ;;; An IR2-COMPONENT serves mostly to accumulate non-code information
232 ;;; about the component being compiled.
233 (defstruct (ir2-component (:copier nil))
234   ;; the counter used to allocate global TN numbers
235   (global-tn-counter 0 :type index)
236   ;; NORMAL-TNS is the head of the list of all the normal TNs that
237   ;; need to be packed, linked through the Next slot. We place TNs on
238   ;; this list when we allocate them so that Pack can find them.
239   ;;
240   ;; RESTRICTED-TNS are TNs that must be packed within a finite SC. We
241   ;; pack these TNs first to ensure that the restrictions will be
242   ;; satisfied (if possible).
243   ;;
244   ;; WIRED-TNs are TNs that must be packed at a specific location. The
245   ;; SC and OFFSET are already filled in.
246   ;;
247   ;; CONSTANT-TNs are non-packed TNs that represent constants.
248   ;; :CONSTANT TNs may eventually be converted to :CACHED-CONSTANT
249   ;; normal TNs.
250   ;;
251   ;; FIXME: What is :CACHED-CONSTANT?
252   (normal-tns nil :type (or tn null))
253   (restricted-tns nil :type (or tn null))
254   (wired-tns nil :type (or tn null))
255   (constant-tns nil :type (or tn null))
256   ;; a list of all the :COMPONENT TNs (live throughout the component).
257   ;; These TNs will also appear in the {NORMAL,RESTRICTED,WIRED} TNs
258   ;; as appropriate to their location.
259   (component-tns () :type list)
260   ;; If this component has a NFP, then this is it.
261   (nfp nil :type (or tn null))
262   ;; a list of the explicitly specified save TNs (kind
263   ;; :SPECIFIED-SAVE). These TNs will also appear in the
264   ;; {NORMAL,RESTRICTED,WIRED} TNs as appropriate to their location.
265   (specified-save-tns () :type list)
266   ;; a list of all the blocks whose IR2-BLOCK has a non-null value for
267   ;; POPPED. This slot is initialized by LTN-ANALYZE as an input to
268   ;; STACK-ANALYZE.
269   (values-receivers nil :type list)
270   ;; an adjustable vector that records all the constants in the
271   ;; constant pool. A non-immediate :CONSTANT TN with offset 0 refers
272   ;; to the constant in element 0, etc. Normal constants are
273   ;; represented by the placing the CONSTANT leaf in this vector. A
274   ;; load-time constant is distinguished by being a cons (KIND .
275   ;; WHAT). KIND is a keyword indicating how the constant is computed,
276   ;; and WHAT is some context.
277   ;;
278   ;; These load-time constants are recognized:
279   ;;
280   ;; (:entry . <function>)
281   ;;    Is replaced by the code pointer for the specified function.
282   ;;    This is how compiled code (including DEFUN) gets its hands on
283   ;;    a function. <function> is the XEP lambda for the called
284   ;;    function; its LEAF-INFO should be an ENTRY-INFO structure.
285   ;;
286   ;; (:label . <label>)
287   ;;    Is replaced with the byte offset of that label from the start
288   ;;    of the code vector (including the header length.)
289   ;;
290   ;; A null entry in this vector is a placeholder for implementation
291   ;; overhead that is eventually stuffed in somehow.
292   (constants (make-array 10 :fill-pointer 0 :adjustable t) :type vector)
293   ;; some kind of info about the component's run-time representation.
294   ;; This is filled in by the VM supplied SELECT-COMPONENT-FORMAT function.
295   format
296   ;; a list of the ENTRY-INFO structures describing all of the entries
297   ;; into this component. Filled in by entry analysis.
298   (entries nil :type list)
299   ;; head of the list of :ALIAS TNs in this component, threaded by TN-NEXT
300   (alias-tns nil :type (or tn null))
301   ;; SPILLED-VOPS is a hashtable translating from "interesting" VOPs
302   ;; to a list of the TNs spilled at that VOP. This is used when
303   ;; computing debug info so that we don't consider the TN's value to
304   ;; be valid when it is in fact somewhere else. SPILLED-TNS has T for
305   ;; every "interesting" TN that is ever spilled, providing a
306   ;; representation that is more convenient some places.
307   (spilled-vops (make-hash-table :test 'eq) :type hash-table)
308   (spilled-tns (make-hash-table :test 'eq) :type hash-table)
309   ;; dynamic vop count info. This is needed by both ir2-convert and
310   ;; setup-dynamic-count-info. (But only if we are generating code to
311   ;; collect dynamic statistics.)
312   #!+sb-dyncount
313   (dyncount-info nil :type (or null dyncount-info)))
314
315 ;;; An ENTRY-INFO condenses all the information that the dumper needs
316 ;;; to create each XEP's function entry data structure. ENTRY-INFO
317 ;;; structures are sometimes created before they are initialized,
318 ;;; since IR2 conversion may need to compile a forward reference. In
319 ;;; this case the slots aren't actually initialized until entry
320 ;;; analysis runs.
321 (defstruct (entry-info (:copier nil))
322   ;; Does this function have a non-null closure environment?
323   (closure-p nil :type boolean)
324   ;; a label pointing to the entry vector for this function, or NIL
325   ;; before ENTRY-ANALYZE runs
326   (offset nil :type (or label null))
327   ;; If this function was defined using DEFUN, then this is the name
328   ;; of the function, a symbol or (SETF <symbol>). Otherwise, this is
329   ;; some string that is intended to be informative.
330   (name "<not computed>" :type (or simple-string list symbol))
331   ;; the argument list that the function was defined with.
332   (arguments nil :type list)
333   ;; a function type specifier representing the arguments and results
334   ;; of this function
335   (type 'function :type (or list (member function))))
336
337 ;;; An IR2-PHYSENV is used to annotate non-LET LAMBDAs with their
338 ;;; passing locations. It is stored in the PHYSENV-INFO.
339 (defstruct (ir2-physenv (:copier nil))
340   ;; TN info for closed-over things within the function: an alist
341   ;; mapping from NLX-INFOs and LAMBDA-VARs to TNs holding the
342   ;; corresponding thing within this function
343   ;;
344   ;; Elements of this list have a one-to-one correspondence with
345   ;; elements of the PHYSENV-CLOSURE list of the PHYSENV object that
346   ;; links to us.
347   (closure (missing-arg) :type list :read-only t)
348   ;; the TNs that hold the OLD-FP and RETURN-PC within the function.
349   ;; We always save these so that the debugger can do a backtrace,
350   ;; even if the function has no return (and thus never uses them).
351   ;; Null only temporarily.
352   (old-fp nil :type (or tn null))
353   (return-pc nil :type (or tn null))
354   ;; The passing location for the RETURN-PC. The return PC is treated
355   ;; differently from the other arguments, since in some
356   ;; implementations we may use a call instruction that requires the
357   ;; return PC to be passed in a particular place.
358   (return-pc-pass (missing-arg) :type tn :read-only t)
359   ;; True if this function has a frame on the number stack. This is
360   ;; set by representation selection whenever it is possible that some
361   ;; function in our tail set will make use of the number stack.
362   (number-stack-p nil :type boolean)
363   ;; a list of all the :ENVIRONMENT TNs live in this environment
364   (live-tns nil :type list)
365   ;; a list of all the :DEBUG-ENVIRONMENT TNs live in this environment
366   (debug-live-tns nil :type list)
367   ;; a label that marks the start of elsewhere code for this function,
368   ;; or null until this label is assigned by codegen. Used for
369   ;; maintaining the debug source map.
370   (elsewhere-start nil :type (or label null))
371   ;; a label that marks the first location in this function at which
372   ;; the environment is properly initialized, i.e. arguments moved
373   ;; from their passing locations, etc. This is the start of the
374   ;; function as far as the debugger is concerned.
375   (environment-start nil :type (or label null)))
376 (defprinter (ir2-physenv)
377   closure
378   old-fp
379   return-pc
380   return-pc-pass)
381
382 ;;; A RETURN-INFO is used by GTN to represent the return strategy and
383 ;;; locations for all the functions in a given TAIL-SET. It is stored
384 ;;; in the TAIL-SET-INFO.
385 (defstruct (return-info (:copier nil))
386   ;; The return convention used:
387   ;; -- If :UNKNOWN, we use the standard return convention.
388   ;; -- If :FIXED, we use the known-values convention.
389   (kind (missing-arg) :type (member :fixed :unknown))
390   ;; the number of values returned, or :UNKNOWN if we don't know.
391   ;; COUNT may be known when KIND is :UNKNOWN, since we may choose the
392   ;; standard return convention for other reasons.
393   (count (missing-arg) :type (or index (member :unknown)))
394   ;; If count isn't :UNKNOWN, then this is a list of the
395   ;; primitive-types of each value.
396   (types () :type list)
397   ;; If kind is :FIXED, then this is the list of the TNs that we
398   ;; return the values in.
399   (locations () :type list))
400 (defprinter (return-info)
401   kind
402   count
403   types
404   locations)
405
406 (defstruct (ir2-nlx-info (:copier nil))
407   ;; If the kind is :ENTRY (a lexical exit), then in the home
408   ;; environment, this holds a VALUE-CELL object containing the unwind
409   ;; block pointer. In the other cases nobody directly references the
410   ;; unwind-block, so we leave this slot null.
411   (home nil :type (or tn null))
412   ;; the saved control stack pointer
413   (save-sp (missing-arg) :type tn)
414   ;; the list of dynamic state save TNs
415   (dynamic-state (list* (make-stack-pointer-tn)
416                         (make-dynamic-state-tns))
417                  :type list)
418   ;; the target label for NLX entry
419   (target (gen-label) :type label))
420 (defprinter (ir2-nlx-info)
421   home
422   save-sp
423   dynamic-state)
424 \f
425 ;;;; VOPs and templates
426
427 ;;; A VOP is a Virtual Operation. It represents an operation and the
428 ;;; operands to the operation.
429 (def!struct (vop (:constructor make-vop (block node info args results))
430                  (:copier nil))
431   ;; VOP-INFO structure containing static info about the operation
432   (info nil :type (or vop-info null))
433   ;; the IR2-BLOCK this VOP is in
434   (block (missing-arg) :type ir2-block)
435   ;; VOPs evaluated after and before this one. Null at the
436   ;; beginning/end of the block, and temporarily during IR2
437   ;; translation.
438   (next nil :type (or vop null))
439   (prev nil :type (or vop null))
440   ;; heads of the TN-REF lists for operand TNs, linked using the
441   ;; ACROSS slot
442   (args nil :type (or tn-ref null))
443   (results nil :type (or tn-ref null))
444   ;; head of the list of write refs for each explicitly allocated
445   ;; temporary, linked together using the ACROSS slot
446   (temps nil :type (or tn-ref null))
447   ;; head of the list of all TN-REFs for references in this VOP,
448   ;; linked by the NEXT-REF slot. There will be one entry for each
449   ;; operand and two (a read and a write) for each temporary.
450   (refs nil :type (or tn-ref null))
451   ;; stuff that is passed uninterpreted from IR2 conversion to
452   ;; codegen. The meaning of this slot is totally dependent on the VOP.
453   codegen-info
454   ;; the node that generated this VOP, for keeping track of debug info
455   (node nil :type (or node null))
456   ;; LOCAL-TN-BIT-VECTOR representing the set of TNs live after args
457   ;; are read and before results are written. This is only filled in
458   ;; when VOP-INFO-SAVE-P is non-null.
459   (save-set nil :type (or local-tn-bit-vector null)))
460 (defprinter (vop)
461   (info :prin1 (vop-info-name info))
462   args
463   results
464   (codegen-info :test codegen-info))
465
466 ;;; A TN-REF object contains information about a particular reference
467 ;;; to a TN. The information in TN-REFs largely determines how TNs are
468 ;;; packed.
469 (def!struct (tn-ref (:constructor make-tn-ref (tn write-p))
470                     (:copier nil))
471   ;; the TN referenced
472   (tn (missing-arg) :type tn)
473   ;; Is this is a write reference? (as opposed to a read reference)
474   (write-p nil :type boolean)
475   ;; the link for a list running through all TN-REFs for this TN of
476   ;; the same kind (read or write)
477   (next nil :type (or tn-ref null))
478   ;; the VOP where the reference happens, or NIL temporarily
479   (vop nil :type (or vop null))
480   ;; the link for a list of all TN-REFs in VOP, in reverse order of
481   ;; reference
482   (next-ref nil :type (or tn-ref null))
483   ;; the link for a list of the TN-REFs in VOP of the same kind
484   ;; (argument, result, temp)
485   (across nil :type (or tn-ref null))
486   ;; If true, this is a TN-REF also in VOP whose TN we would like
487   ;; packed in the same location as our TN. Read and write refs are
488   ;; always paired: TARGET in the read points to the write, and
489   ;; vice-versa.
490   (target nil :type (or null tn-ref))
491   ;; the load TN allocated for this operand, if any
492   (load-tn nil :type (or tn null)))
493 (defprinter (tn-ref)
494   tn
495   write-p
496   (vop :test vop :prin1 (vop-info-name (vop-info vop))))
497
498 ;;; A TEMPLATE object represents a particular IR2 coding strategy for
499 ;;; a known function.
500 (def!struct (template (:constructor nil)
501                       #-sb-xc-host (:pure t))
502   ;; the symbol name of this VOP. This is used when printing the VOP
503   ;; and is also used to provide a handle for definition and
504   ;; translation.
505   (name nil :type symbol)
506   ;; the arg/result type restrictions. We compute this from the
507   ;; PRIMITIVE-TYPE restrictions to make life easier for IR1 phases
508   ;; that need to anticipate LTN's template selection.
509   (type (missing-arg) :type ctype)
510   ;; lists of restrictions on the argument and result types. A
511   ;; restriction may take several forms:
512   ;; -- The restriction * is no restriction at all.
513   ;; -- A restriction (:OR <primitive-type>*) means that the operand 
514   ;;    must have one of the specified primitive types.
515   ;; -- A restriction (:CONSTANT <predicate> <type-spec>) means that the
516   ;;    argument (not a result) must be a compile-time constant that
517   ;;    satisfies the specified predicate function. In this case, the
518   ;;    constant value will be passed as an info argument rather than
519   ;;    as a normal argument. <type-spec> is a Lisp type specifier for
520   ;;    the type tested by the predicate, used when we want to represent
521   ;;    the type constraint as a Lisp function type.
522   ;;
523   ;; If RESULT-TYPES is :CONDITIONAL, then this is an IF-FOO style
524   ;; conditional that yields its result as a control transfer. The
525   ;; emit function takes two info arguments: the target label and a
526   ;; boolean flag indicating whether to negate the sense of the test.
527   (arg-types nil :type list)
528   (result-types nil :type (or list (member :conditional)))
529   ;; the primitive type restriction applied to each extra argument or
530   ;; result following the fixed operands. If NIL, no extra
531   ;; args/results are allowed. Otherwise, either * or a (:OR ...) list
532   ;; as described for the {ARG,RESULT}-TYPES.
533   (more-args-type nil :type (or (member nil *) cons))
534   (more-results-type nil :type (or (member nil *) cons))
535   ;; If true, this is a function that is called with no arguments to
536   ;; see whether this template can be emitted. This is used to
537   ;; conditionally compile for different target hardware
538   ;; configuarations (e.g. FP hardware.)
539   (guard nil :type (or function null))
540   ;; the policy under which this template is the best translation.
541   ;; Note that LTN might use this template under other policies if it
542   ;; can't figure out anything better to do.
543   (ltn-policy (missing-arg) :type ltn-policy)
544   ;; the base cost for this template, given optimistic assumptions
545   ;; such as no operand loading, etc.
546   (cost (missing-arg) :type index)
547   ;; If true, then this is a short noun-like phrase describing what
548   ;; this VOP "does", i.e. the implementation strategy. This is for
549   ;; use in efficiency notes.
550   (note nil :type (or string null))
551   ;; the number of trailing arguments to VOP or %PRIMITIVE that we
552   ;; bundle into a list and pass into the emit function. This provides
553   ;; a way to pass uninterpreted stuff directly to the code generator.
554   (info-arg-count 0 :type index)
555   ;; a function that emits the VOPs for this template. Arguments:
556   ;;  1] Node for source context.
557   ;;  2] IR2-BLOCK that we place the VOP in.
558   ;;  3] This structure.
559   ;;  4] Head of argument TN-REF list.
560   ;;  5] Head of result TN-REF list.
561   ;;  6] If INFO-ARG-COUNT is non-zero, then a list of the magic
562   ;;     arguments.
563   ;;
564   ;; Two values are returned: the first and last VOP emitted. This vop
565   ;; sequence must be linked into the VOP Next/Prev chain for the
566   ;; block. At least one VOP is always emitted.
567   (emit-function (missing-arg) :type function))
568 (defprinter (template)
569   name
570   arg-types
571   result-types
572   (more-args-type :test more-args-type :prin1 more-args-type)
573   (more-results-type :test more-results-type :prin1 more-results-type)
574   ltn-policy
575   cost
576   (note :test note)
577   (info-arg-count :test (not (zerop info-arg-count))))
578
579 ;;; A VOP-INFO object holds the constant information for a given
580 ;;; virtual operation. We include TEMPLATE so that functions with a
581 ;;; direct VOP equivalent can be translated easily.
582 (def!struct (vop-info
583              (:include template)
584              (:make-load-form-fun ignore-it))
585   ;; side effects of this VOP and side effects that affect the value
586   ;; of this VOP
587   (effects (missing-arg) :type attributes)
588   (affected (missing-arg) :type attributes)
589   ;; If true, causes special casing of TNs live after this VOP that
590   ;; aren't results:
591   ;; -- If T, all such TNs that are allocated in a SC with a defined
592   ;;    save-sc will be saved in a TN in the save SC before the VOP
593   ;;    and restored after the VOP. This is used by call VOPs. A bit
594   ;;    vector representing the live TNs is stored in the VOP-SAVE-SET.
595   ;; -- If :FORCE-TO-STACK, all such TNs will made into :ENVIRONMENT TNs
596   ;;    and forced to be allocated in SCs without any save-sc. This is
597   ;;    used by NLX entry vops.
598   ;; -- If :COMPUTE-ONLY, just compute the save set, don't do any saving.
599   ;;    This is used to get the live variables for debug info.
600   (save-p nil :type (member t nil :force-to-stack :compute-only))
601   ;; info for automatic emission of move-arg VOPs by representation
602   ;; selection. If NIL, then do nothing special. If non-null, then
603   ;; there must be a more arg. Each more arg is moved to its passing
604   ;; location using the appropriate representation-specific MOVE-ARG
605   ;; VOP. The first (fixed) argument must be the control-stack frame
606   ;; pointer for the frame to move into. The first info arg is the
607   ;; list of passing locations.
608   ;;
609   ;; Additional constraints depend on the value:
610   ;;
611   ;; :FULL-CALL
612   ;;     None.
613   ;;
614   ;; :LOCAL-CALL
615   ;;     The second (fixed) arg is the NFP for the called function (from
616   ;;     ALLOCATE-FRAME.)
617   ;;
618   ;; :KNOWN-RETURN
619   ;;     If needed, the old NFP is computed using COMPUTE-OLD-NFP.
620   (move-args nil :type (member nil :full-call :local-call :known-return))
621   ;; a list of sc-vectors representing the loading costs of each fixed
622   ;; argument and result
623   (arg-costs nil :type list)
624   (result-costs nil :type list)
625   ;; if true, SC-VECTORs representing the loading costs for any more
626   ;; args and results
627   (more-arg-costs nil :type (or sc-vector null))
628   (more-result-costs nil :type (or sc-vector null))
629   ;; lists of SC-VECTORs mapping each SC to the SCs that we can load
630   ;; into. If a SC is directly acceptable to the VOP, then the entry
631   ;; is T. Otherwise, it is a list of the SC numbers of all the SCs
632   ;; that we can load into. This list will be empty if there is no
633   ;; load function which loads from that SC to an SC allowed by the
634   ;; operand SC restriction.
635   (arg-load-scs nil :type list)
636   (result-load-scs nil :type list)
637   ;; if true, a function that is called with the VOP to do operand
638   ;; targeting. This is done by modifying the TN-REF-TARGET slots in
639   ;; the TN-REFS so that they point to other TN-REFS in the same VOP.
640   (target-fun nil :type (or null function))
641   ;; a function that emits assembly code for a use of this VOP when it
642   ;; is called with the VOP structure. This is null if this VOP has no
643   ;; specified generator (i.e. if it exists only to be inherited by
644   ;; other VOPs).
645   (generator-function nil :type (or function null))
646   ;; a list of things that are used to parameterize an inherited
647   ;; generator. This allows the same generator function to be used for
648   ;; a group of VOPs with similar implementations.
649   (variant nil :type list)
650   ;; the number of arguments and results. Each regular arg/result
651   ;; counts as one, and all the more args/results together count as 1.
652   (num-args 0 :type index)
653   (num-results 0 :type index)
654   ;; a vector of the temporaries the vop needs. See EMIT-GENERIC-VOP
655   ;; in vmdef for information on how the temps are encoded.
656   (temps nil :type (or null (specializable-vector (unsigned-byte 16))))
657   ;; the order all the refs for this vop should be put in. Each
658   ;; operand is assigned a number in the following ordering: args,
659   ;; more-args, results, more-results, temps. This vector represents
660   ;; the order the operands should be put into in the next-ref link.
661   (ref-ordering nil :type (or null (specializable-vector (unsigned-byte 8))))
662   ;; a vector of the various targets that should be done. Each element
663   ;; encodes the source ref (shifted 8, it is also encoded in
664   ;; MAX-VOP-TN-REFS) and the dest ref index.
665   (targets nil :type (or null (specializable-vector (unsigned-byte 16)))))
666 \f
667 ;;;; SBs and SCs
668
669 ;;; copied from docs/internals/retargeting.tex by WHN 19990707:
670 ;;;
671 ;;; A Storage Base represents a physical storage resource such as a
672 ;;; register set or stack frame. Storage bases for non-global
673 ;;; resources such as the stack are relativized by the environment
674 ;;; that the TN is allocated in. Packing conflict information is kept
675 ;;; in the storage base, but non-packed storage resources such as
676 ;;; closure environments also have storage bases.
677 ;;;
678 ;;; Some storage bases:
679 ;;;     General purpose registers
680 ;;;     Floating point registers
681 ;;;     Boxed (control) stack environment
682 ;;;     Unboxed (number) stack environment
683 ;;;     Closure environment
684 ;;;
685 ;;; A storage class is a potentially arbitrary set of the elements in
686 ;;; a storage base. Although conceptually there may be a hierarchy of
687 ;;; storage classes such as "all registers", "boxed registers", "boxed
688 ;;; scratch registers", this doesn't exist at the implementation
689 ;;; level. Such things can be done by specifying storage classes whose
690 ;;; locations overlap. A TN shouldn't have lots of overlapping SC's as
691 ;;; legal SC's, since time would be wasted repeatedly attempting to
692 ;;; pack in the same locations.
693 ;;;
694 ;;; ...
695 ;;;
696 ;;; Some SCs:
697 ;;;     Reg: any register (immediate objects)
698 ;;;     Save-Reg: a boxed register near r15 (registers easily saved in a call)
699 ;;;     Boxed-Reg: any boxed register (any boxed object)
700 ;;;     Unboxed-Reg: any unboxed register (any unboxed object)
701 ;;;     Float-Reg, Double-Float-Reg: float in FP register.
702 ;;;     Stack: boxed object on the stack (on control stack)
703 ;;;     Word: any 32bit unboxed object on nstack.
704 ;;;     Double: any 64bit unboxed object on nstack.
705
706 ;;; The SB structure represents the global information associated with
707 ;;; a storage base.
708 (def!struct (sb (:make-load-form-fun just-dump-it-normally))
709   ;; name, for printing and reference
710   (name nil :type symbol)
711   ;; the kind of storage base (which determines the packing
712   ;; algorithm)
713   (kind :non-packed :type (member :finite :unbounded :non-packed))
714   ;; the number of elements in the SB. If finite, this is the total
715   ;; size. If unbounded, this is the size that the SB is initially
716   ;; allocated at.
717   (size 0 :type index))
718 (defprinter (sb)
719   name)
720
721 ;;; A FINITE-SB holds information needed by the packing algorithm for
722 ;;; finite SBs.
723 (def!struct (finite-sb (:include sb))
724   ;; the number of locations currently allocated in this SB
725   (current-size 0 :type index)
726   ;; the last location packed in, used by pack to scatter TNs to
727   ;; prevent a few locations from getting all the TNs, and thus
728   ;; getting overcrowded, reducing the possibilities for targeting.
729   (last-offset 0 :type index)
730   ;; a vector containing, for each location in this SB, a vector
731   ;; indexed by IR2 block numbers, holding local conflict bit vectors.
732   ;; A TN must not be packed in a given location within a particular
733   ;; block if the LTN number for that TN in that block corresponds to
734   ;; a set bit in the bit-vector.
735   (conflicts '#() :type simple-vector)
736   ;; a vector containing, for each location in this SB, a bit-vector
737   ;; indexed by IR2 block numbers. If the bit corresponding to a block
738   ;; is set, then the location is in use somewhere in the block, and
739   ;; thus has a conflict for always-live TNs.
740   (always-live '#() :type simple-vector)
741   ;; a vector containing the TN currently live in each location in the
742   ;; SB, or NIL if the location is unused. This is used during load-tn pack.
743   (live-tns '#() :type simple-vector)
744   ;; the number of blocks for which the ALWAYS-LIVE and CONFLICTS
745   ;; might not be virgin, and thus must be reinitialized when PACK
746   ;; starts. Less then the length of those vectors when not all of the
747   ;; length was used on the previously packed component.
748   (last-block-count 0 :type index))
749
750 ;;; the SC structure holds the storage base that storage is allocated
751 ;;; in and information used to select locations within the SB
752 (def!struct (sc (:copier nil))
753   ;; name, for printing and reference
754   (name nil :type symbol)
755   ;; the number used to index SC cost vectors
756   (number 0 :type sc-number)
757   ;; the storage base that this SC allocates storage from
758   (sb nil :type (or sb null))
759   ;; the size of elements in this SC, in units of locations in the SB
760   (element-size 0 :type index)
761   ;; if our SB is finite, a list of the locations in this SC
762   (locations nil :type list)
763   ;; a list of the alternate (save) SCs for this SC
764   (alternate-scs nil :type list)
765   ;; a list of the constant SCs that can me moved into this SC
766   (constant-scs nil :type list)
767   ;; true if the values in this SC needs to be saved across calls
768   (save-p nil :type boolean)
769   ;; vectors mapping from SC numbers to information about how to load
770   ;; from the index SC to this one. MOVE-FUNS holds the names of
771   ;; the functions used to do loading, and LOAD-COSTS holds the cost
772   ;; of the corresponding move functions. If loading is impossible,
773   ;; then the entries are NIL. LOAD-COSTS is initialized to have a 0
774   ;; for this SC.
775   (move-funs (make-array sc-number-limit :initial-element nil)
776              :type sc-vector)
777   (load-costs (make-array sc-number-limit :initial-element nil)
778               :type sc-vector)
779   ;; a vector mapping from SC numbers to possibly
780   ;; representation-specific move and coerce VOPs. Each entry is a
781   ;; list of VOP-INFOs for VOPs that move/coerce an object in the
782   ;; index SC's representation into this SC's representation. This
783   ;; vector is filled out with entries for all SCs that can somehow be
784   ;; coerced into this SC, not just those VOPs defined to directly
785   ;; move into this SC (i.e. it allows for operand loading on the move
786   ;; VOP's operands.)
787   ;;
788   ;; When there are multiple applicable VOPs, the template arg and
789   ;; result type restrictions are used to determine which one to use.
790   ;; The list is sorted by increasing cost, so the first applicable
791   ;; VOP should be used.
792   ;;
793   ;; Move (or move-arg) VOPs with descriptor results shouldn't have
794   ;; TNs wired in the standard argument registers, since there may
795   ;; already be live TNs wired in those locations holding the values
796   ;; that we are setting up for unknown-values return.
797   (move-vops (make-array sc-number-limit :initial-element nil)
798              :type sc-vector)
799   ;; the costs corresponding to the MOVE-VOPS. Separate because this
800   ;; info is needed at meta-compile time, while the MOVE-VOPs don't
801   ;; exist till load time. If no move is defined, then the entry is
802   ;; NIL.
803   (move-costs (make-array sc-number-limit :initial-element nil)
804               :type sc-vector)
805   ;; similar to Move-VOPs, except that we only ever use the entries
806   ;; for this SC and its alternates, since we never combine complex
807   ;; representation conversion with argument passing.
808   (move-arg-vops (make-array sc-number-limit :initial-element nil)
809                  :type sc-vector)
810   ;; true if this SC or one of its alternates in in the NUMBER-STACK SB.
811   (number-stack-p nil :type boolean)
812   ;; alignment restriction. The offset must be an even multiple of this.
813   (alignment 1 :type (and index (integer 1)))
814   ;; a list of locations that we avoid packing in during normal
815   ;; register allocation to ensure that these locations will be free
816   ;; for operand loading. This prevents load-TN packing from thrashing
817   ;; by spilling a lot.
818   (reserve-locations nil :type list))
819 (defprinter (sc)
820   name)
821 \f
822 ;;;; TNs
823
824 (def!struct (tn (:include sset-element)
825                (:constructor make-random-tn)
826                (:constructor make-tn (number kind primitive-type sc))
827                (:copier nil))
828   ;; The kind of TN this is:
829   ;;
830   ;;   :NORMAL
831   ;;    A normal, non-constant TN, representing a variable or temporary.
832   ;;    Lifetime information is computed so that packing can be done.
833   ;;
834   ;;   :ENVIRONMENT
835   ;;    A TN that has hidden references (debugger or NLX), and thus must be
836   ;;    allocated for the duration of the environment it is referenced in.
837   ;;
838   ;;   :DEBUG-ENVIRONMENT
839   ;;    Like :ENVIRONMENT, but is used for TNs that we want to be able to
840   ;;    target to/from and that don't absolutely have to be live
841   ;;    everywhere. These TNs are live in all blocks in the environment
842   ;;    that don't reference this TN.
843   ;;
844   ;;   :COMPONENT
845   ;;    A TN that implicitly conflicts with all other TNs. No conflict
846   ;;    info is computed.
847   ;;
848   ;;   :SAVE
849   ;;   :SAVE-ONCE
850   ;;    A TN used for saving a :NORMAL TN across function calls. The
851   ;;    lifetime information slots are unitialized: get the original
852   ;;    TN our of the SAVE-TN slot and use it for conflicts. SAVE-ONCE
853   ;;    is like :SAVE, except that it is only save once at the single
854   ;;    writer of the original TN.
855   ;;
856   ;;   :SPECIFIED-SAVE
857   ;;    A TN that was explicitly specified as the save TN for another TN.
858   ;;    When we actually get around to doing the saving, this will be
859   ;;    changed to :SAVE or :SAVE-ONCE.
860   ;;
861   ;;   :LOAD
862   ;;    A load-TN used to compute an argument or result that is
863   ;;    restricted to some finite SB. Load TNs don't have any conflict
864   ;;    information. Load TN pack uses a special local conflict
865   ;;    determination method.
866   ;;
867   ;;   :CONSTANT
868   ;;    Represents a constant, with TN-LEAF a CONSTANT leaf. Lifetime
869   ;;    information isn't computed, since the value isn't allocated by
870   ;;    pack, but is instead generated as a load at each use. Since
871   ;;    lifetime analysis isn't done on :CONSTANT TNs, they don't have
872   ;;    LOCAL-NUMBERs and similar stuff.
873   ;;
874   ;;   :ALIAS
875   ;;    A special kind of TN used to represent initialization of local
876   ;;    call arguments in the caller. It provides another name for the
877   ;;    argument TN so that lifetime analysis doesn't get confused by
878   ;;    self-recursive calls. Lifetime analysis treats this the same
879   ;;    as :NORMAL, but then at the end merges the conflict info into
880   ;;    the original TN and replaces all uses of the alias with the
881   ;;    original TN. SAVE-TN holds the aliased TN.
882   (kind (missing-arg)
883         :type (member :normal :environment :debug-environment
884                       :save :save-once :specified-save :load :constant
885                       :component :alias))
886   ;; the primitive-type for this TN's value. Null in restricted or
887   ;; wired TNs.
888   (primitive-type nil :type (or primitive-type null))
889   ;; If this TN represents a variable or constant, then this is the
890   ;; corresponding LEAF.
891   (leaf nil :type (or leaf null))
892   ;; thread that links TNs together so that we can find them
893   (next nil :type (or tn null))
894   ;; head of TN-REF lists for reads and writes of this TN
895   (reads nil :type (or tn-ref null))
896   (writes nil :type (or tn-ref null))
897   ;; a link we use when building various temporary TN lists
898   (next* nil :type (or tn null))
899   ;; some block that contains a reference to this TN, or NIL if we
900   ;; haven't seen any reference yet. If the TN is local, then this is
901   ;; the block it is local to.
902   (local nil :type (or ir2-block null))
903   ;; If a local TN, the block relative number for this TN. Global TNs
904   ;; whose liveness changes within a block are also assigned a local
905   ;; number during the conflicts analysis of that block. If the TN has
906   ;; no local number within the block, then this is NIL.
907   (local-number nil :type (or local-tn-number null))
908   ;; If this object is a local TN, this slot is a bit-vector with 1
909   ;; for the local-number of every TN that we conflict with.
910   (local-conflicts (make-array local-tn-limit
911                                :element-type 'bit
912                                :initial-element 0)
913                    :type local-tn-bit-vector)
914   ;; head of the list of GLOBAL-CONFLICTS structures for a global TN.
915   ;; This list is sorted by block number (i.e. reverse DFO), allowing
916   ;; the intersection between the lifetimes for two global TNs to be
917   ;; easily found. If null, then this TN is a local TN.
918   (global-conflicts nil :type (or global-conflicts null))
919   ;; During lifetime analysis, this is used as a pointer into the
920   ;; conflicts chain, for scanning through blocks in reverse DFO.
921   (current-conflict nil)
922   ;; In a :SAVE TN, this is the TN saved. In a :NORMAL or :ENVIRONMENT
923   ;; TN, this is the associated save TN. In TNs with no save TN, this
924   ;; is null.
925   (save-tn nil :type (or tn null))
926   ;; After pack, the SC we packed into. Beforehand, the SC we want to
927   ;; pack into, or null if we don't know.
928   (sc nil :type (or sc null))
929   ;; the offset within the SB that this TN is packed into. This is what
930   ;; indicates that the TN is packed
931   (offset nil :type (or index null))
932   ;; some kind of info about how important this TN is
933   (cost 0 :type fixnum)
934   ;; If a :ENVIRONMENT or :DEBUG-ENVIRONMENT TN, this is the
935   ;; physical environment that the TN is live throughout.
936   (physenv nil :type (or physenv null)))
937 (def!method print-object ((tn tn) stream)
938   (print-unreadable-object (tn stream :type t)
939     ;; KLUDGE: The distinction between PRINT-TN and PRINT-OBJECT on TN is
940     ;; not very mnemonic. -- WHN 20000124
941     (print-tn-guts tn stream)))
942
943 ;;; The GLOBAL-CONFLICTS structure represents the conflicts for global
944 ;;; TNs. Each global TN has a list of these structures, one for each
945 ;;; block that it is live in. In addition to repsenting the result of
946 ;;; lifetime analysis, the global conflicts structure is used during
947 ;;; lifetime analysis to represent the set of TNs live at the start of
948 ;;; the IR2 block.
949 (defstruct (global-conflicts
950             (:constructor make-global-conflicts (kind tn block number))
951             (:copier nil))
952   ;; the IR2-BLOCK that this structure represents the conflicts for
953   (block (missing-arg) :type ir2-block)
954   ;; thread running through all the GLOBAL-CONFLICTSs for BLOCK. This
955   ;; thread is sorted by TN number
956   (next-blockwise nil :type (or global-conflicts null))
957   ;; the way that TN is used by BLOCK
958   ;;
959   ;;   :READ
960   ;;     The TN is read before it is written. It starts the block live,
961   ;;     but is written within the block.
962   ;;
963   ;;   :WRITE
964   ;;     The TN is written before any read. It starts the block dead,
965   ;;     and need not have a read within the block.
966   ;;
967   ;;   :READ-ONLY
968   ;;     The TN is read, but never written. It starts the block live,
969   ;;     and is not killed by the block. Lifetime analysis will promote
970   ;;     :READ-ONLY TNs to :LIVE if they are live at the block end.
971   ;;
972   ;;   :LIVE
973   ;;     The TN is not referenced. It is live everywhere in the block.
974   (kind :read-only :type (member :read :write :read-only :live))
975   ;; a local conflicts vector representing conflicts with TNs live in
976   ;; BLOCK. The index for the local TN number of each TN we conflict
977   ;; with in this block is 1. To find the full conflict set, the :LIVE
978   ;; TNs for BLOCK must also be included. This slot is not meaningful
979   ;; when KIND is :LIVE.
980   (conflicts (make-array local-tn-limit
981                          :element-type 'bit
982                          :initial-element 0)
983              :type local-tn-bit-vector)
984   ;; the TN we are recording conflicts for.
985   (tn (missing-arg) :type tn)
986   ;; thread through all the GLOBAL-CONFLICTSs for TN
987   (next-tnwise nil :type (or global-conflicts null))
988   ;; TN's local TN number in BLOCK. :LIVE TNs don't have local numbers.
989   (number nil :type (or local-tn-number null)))
990 (defprinter (global-conflicts)
991   tn
992   block
993   kind
994   (number :test number))