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