1 ;;;; structures for the second (virtual machine) intermediate
2 ;;;; representation in the compiler, IR2
4 ;;;; This software is part of the SBCL system. See the README file for
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.
15 ;;; the largest number of TNs whose liveness changes that we can have
17 (def!constant local-tn-limit 64)
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))
24 ;;; type of an SC number
25 (deftype sc-number () `(integer 0 (,sc-number-limit)))
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))
31 ;;; the different policies we can use to determine the coding strategy
32 (deftype ltn-policy ()
33 '(member :safe :small :fast :fast-safe))
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
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)))
57 (defprinter (primitive-type)
60 ;;;; IR1 annotations used for IR2 conversion
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.
69 ;;; Holds the IR2-COMPONENT structure.
72 ;;; Holds the IR2-LVAR structure. LVARs whose values aren't used
73 ;;; won't have any. XXX
76 ;;; If non-null, then a TN in which the affected dynamic
77 ;;; environment pointer should be saved after the binding is
81 ;;; Holds the IR2-PHYSENV structure.
84 ;;; Holds the RETURN-INFO structure.
87 ;;; Holds the IR2-NLX-INFO structure.
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.
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.
102 ;;; After LTN analysis, this is true only in combination nodes that are
103 ;;; truly tail recursive.
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))
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
129 (start-stack () :type list)
130 (end-stack () :type list)
131 ;; the first and last VOP in this block. If there are none, both
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
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
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
170 ;; the assembler label that points to the trampoline for this block,
171 ;; or NIL if unassigned yet. Only meaningful for local call targets.
172 (%trampoline-label nil)
173 ;; T if the preceding block assumes it can drop thru to %label
174 (dropped-thru-to nil)
175 ;; list of LOCATION-INFO structures describing all the interesting
176 ;; (to the debugger) locations in this block
177 (locations nil :type list))
179 (defprinter (ir2-block)
180 (pushed :test pushed)
181 (popped :test popped)
182 (start-vop :test start-vop)
183 (last-vop :test last-vop)
184 (local-tn-count :test (not (zerop local-tn-count)))
185 (%label :test %label))
187 ;;; An IR2-LVAR structure is used to annotate LVARs that are used as a
188 ;;; function result LVARs or that receive MVs.
190 (:constructor make-ir2-lvar (primitive-type))
192 ;; If this is :DELAYED, then this is a single value LVAR for which
193 ;; the evaluation of the use is to be postponed until the evaluation
194 ;; of destination. This can be done for ref nodes or predicates
195 ;; whose destination is an IF.
197 ;; If this is :FIXED, then this LVAR has a fixed number of values,
198 ;; with the TNs in LOCS.
200 ;; If this is :UNKNOWN, then this is an unknown-values LVAR, using
201 ;; the passing locations in LOCS.
203 ;; If this is :UNUSED, then this LVAR should never actually be used
204 ;; as the destination of a value: it is only used tail-recursively.
205 (kind :fixed :type (member :delayed :fixed :unknown :unused))
206 ;; The primitive-type of the first value of this LVAR. This is
207 ;; primarily for internal use during LTN, but it also records the
208 ;; type restriction on delayed references. In multiple-value
209 ;; contexts, this is null to indicate that it is meaningless. This
210 ;; is always (primitive-type (lvar-type cont)), which may be more
211 ;; restrictive than the tn-primitive-type of the value TN. This is
212 ;; becase the value TN must hold any possible type that could be
213 ;; computed (before type checking.) XXX
214 (primitive-type nil :type (or primitive-type null))
215 ;; Locations used to hold the values of the LVAR. If the number of
216 ;; values if fixed, then there is one TN per value. If the number of
217 ;; values is unknown, then this is a two-list of TNs holding the
218 ;; start of the values glob and the number of values. Note that
219 ;; since type checking is the responsibility of the values receiver,
220 ;; these TNs primitive type is only based on the proven type
222 (locs nil :type list)
223 (stack-pointer nil :type (or tn null)))
225 (defprinter (ir2-lvar)
230 ;;; An IR2-COMPONENT serves mostly to accumulate non-code information
231 ;;; about the component being compiled.
232 (defstruct (ir2-component (:copier nil))
233 ;; the counter used to allocate global TN numbers
234 (global-tn-counter 0 :type index)
235 ;; NORMAL-TNS is the head of the list of all the normal TNs that
236 ;; need to be packed, linked through the Next slot. We place TNs on
237 ;; this list when we allocate them so that Pack can find them.
239 ;; RESTRICTED-TNS are TNs that must be packed within a finite SC. We
240 ;; pack these TNs first to ensure that the restrictions will be
241 ;; satisfied (if possible).
243 ;; WIRED-TNs are TNs that must be packed at a specific location. The
244 ;; SC and OFFSET are already filled in.
246 ;; CONSTANT-TNs are non-packed TNs that represent constants.
247 (normal-tns nil :type (or tn null))
248 (restricted-tns nil :type (or tn null))
249 (wired-tns nil :type (or tn null))
250 (constant-tns nil :type (or tn null))
251 ;; a list of all the :COMPONENT TNs (live throughout the component).
252 ;; These TNs will also appear in the {NORMAL,RESTRICTED,WIRED} TNs
253 ;; as appropriate to their location.
254 (component-tns () :type list)
255 ;; If this component has a NFP, then this is it.
256 (nfp nil :type (or tn null))
257 ;; a list of the explicitly specified save TNs (kind
258 ;; :SPECIFIED-SAVE). These TNs will also appear in the
259 ;; {NORMAL,RESTRICTED,WIRED} TNs as appropriate to their location.
260 (specified-save-tns () :type list)
261 ;; a list of all the blocks whose IR2-BLOCK has a non-null value for
262 ;; POPPED. This slot is initialized by LTN-ANALYZE as an input to
264 (values-receivers nil :type list)
265 ;; an adjustable vector that records all the constants in the
266 ;; constant pool. A non-immediate :CONSTANT TN with offset 0 refers
267 ;; to the constant in element 0, etc. Normal constants are
268 ;; represented by the placing the CONSTANT leaf in this vector. A
269 ;; load-time constant is distinguished by being a cons (KIND .
270 ;; WHAT). KIND is a keyword indicating how the constant is computed,
271 ;; and WHAT is some context.
273 ;; These load-time constants are recognized:
275 ;; (:entry . <function>)
276 ;; Is replaced by the code pointer for the specified function.
277 ;; This is how compiled code (including DEFUN) gets its hands on
278 ;; a function. <function> is the XEP lambda for the called
279 ;; function; its LEAF-INFO should be an ENTRY-INFO structure.
281 ;; (:label . <label>)
282 ;; Is replaced with the byte offset of that label from the start
283 ;; of the code vector (including the header length.)
285 ;; A null entry in this vector is a placeholder for implementation
286 ;; overhead that is eventually stuffed in somehow.
287 (constants (make-array 10 :fill-pointer 0 :adjustable t) :type vector)
288 ;; some kind of info about the component's run-time representation.
289 ;; This is filled in by the VM supplied SELECT-COMPONENT-FORMAT function.
291 ;; a list of the ENTRY-INFO structures describing all of the entries
292 ;; into this component. Filled in by entry analysis.
293 (entries nil :type list)
294 ;; head of the list of :ALIAS TNs in this component, threaded by TN-NEXT
295 (alias-tns nil :type (or tn null))
296 ;; SPILLED-VOPS is a hashtable translating from "interesting" VOPs
297 ;; to a list of the TNs spilled at that VOP. This is used when
298 ;; computing debug info so that we don't consider the TN's value to
299 ;; be valid when it is in fact somewhere else. SPILLED-TNS has T for
300 ;; every "interesting" TN that is ever spilled, providing a
301 ;; representation that is more convenient some places.
302 (spilled-vops (make-hash-table :test 'eq) :type hash-table)
303 (spilled-tns (make-hash-table :test 'eq) :type hash-table)
304 ;; dynamic vop count info. This is needed by both ir2-convert and
305 ;; setup-dynamic-count-info. (But only if we are generating code to
306 ;; collect dynamic statistics.)
308 (dyncount-info nil :type (or null dyncount-info)))
310 ;;; An ENTRY-INFO condenses all the information that the dumper needs
311 ;;; to create each XEP's function entry data structure. ENTRY-INFO
312 ;;; structures are sometimes created before they are initialized,
313 ;;; since IR2 conversion may need to compile a forward reference. In
314 ;;; this case the slots aren't actually initialized until entry
316 (defstruct (entry-info (:copier nil))
317 ;; TN, containing closure (if needed) for this function in the home
319 (closure-tn nil :type (or null tn))
320 ;; a label pointing to the entry vector for this function, or NIL
321 ;; before ENTRY-ANALYZE runs
322 (offset nil :type (or label null))
323 ;; If this function was defined using DEFUN, then this is the name
324 ;; of the function, a symbol or (SETF <symbol>). Otherwise, this is
325 ;; some string that is intended to be informative.
326 (name "<not computed>" :type (or simple-string list symbol))
327 ;; the argument list that the function was defined with.
328 (arguments nil :type list)
329 ;; a function type specifier representing the arguments and results
331 (type 'function :type (or list (member function)))
332 ;; docstring and/or xref information for the XEP
333 (info nil :type (or null simple-vector string (cons string simple-vector))))
335 ;;; An IR2-PHYSENV is used to annotate non-LET LAMBDAs with their
336 ;;; passing locations. It is stored in the PHYSENV-INFO.
337 (defstruct (ir2-physenv (:copier nil))
338 ;; TN info for closed-over things within the function: an alist
339 ;; mapping from NLX-INFOs and LAMBDA-VARs to TNs holding the
340 ;; corresponding thing within this function
342 ;; Elements of this list have a one-to-one correspondence with
343 ;; elements of the PHYSENV-CLOSURE list of the PHYSENV object that
345 (closure (missing-arg) :type list :read-only t)
346 ;; the TNs that hold the OLD-FP and RETURN-PC within the function.
347 ;; We always save these so that the debugger can do a backtrace,
348 ;; even if the function has no return (and thus never uses them).
349 ;; Null only temporarily.
350 (old-fp nil :type (or tn null))
351 (return-pc nil :type (or tn null))
352 ;; The passing location for the RETURN-PC. The return PC is treated
353 ;; differently from the other arguments, since in some
354 ;; implementations we may use a call instruction that requires the
355 ;; return PC to be passed in a particular place.
356 (return-pc-pass (missing-arg) :type tn :read-only t)
357 ;; True if this function has a frame on the number stack. This is
358 ;; set by representation selection whenever it is possible that some
359 ;; function in our tail set will make use of the number stack.
360 (number-stack-p nil :type boolean)
361 ;; a list of all the :ENVIRONMENT TNs live in this environment
362 (live-tns nil :type list)
363 ;; a list of all the :DEBUG-ENVIRONMENT TNs live in this environment
364 (debug-live-tns nil :type list)
365 ;; a label that marks the start of elsewhere code for this function,
366 ;; or null until this label is assigned by codegen. Used for
367 ;; maintaining the debug source map.
368 (elsewhere-start nil :type (or label null))
369 ;; a label that marks the first location in this function at which
370 ;; the environment is properly initialized, i.e. arguments moved
371 ;; from their passing locations, etc. This is the start of the
372 ;; function as far as the debugger is concerned.
373 (environment-start nil :type (or label null)))
374 (defprinter (ir2-physenv)
380 ;;; A RETURN-INFO is used by GTN to represent the return strategy and
381 ;;; locations for all the functions in a given TAIL-SET. It is stored
382 ;;; in the TAIL-SET-INFO.
383 (defstruct (return-info (:copier nil))
384 ;; The return convention used:
385 ;; -- If :UNKNOWN, we use the standard return convention.
386 ;; -- If :FIXED, we use the known-values convention.
387 (kind (missing-arg) :type (member :fixed :unknown))
388 ;; the number of values returned, or :UNKNOWN if we don't know.
389 ;; COUNT may be known when KIND is :UNKNOWN, since we may choose the
390 ;; standard return convention for other reasons.
391 (count (missing-arg) :type (or index (member :unknown)))
392 ;; If count isn't :UNKNOWN, then this is a list of the
393 ;; primitive-types of each value.
394 (types () :type list)
395 ;; If kind is :FIXED, then this is the list of the TNs that we
396 ;; return the values in.
397 (locations () :type list))
398 (defprinter (return-info)
404 (defstruct (ir2-nlx-info (:copier nil))
405 ;; If the kind is :ENTRY (a lexical exit), then in the home
406 ;; environment, this holds a VALUE-CELL object containing the unwind
407 ;; block pointer. In the other cases nobody directly references the
408 ;; unwind-block, so we leave this slot null.
409 (home nil :type (or tn null))
410 ;; the saved control stack pointer
411 (save-sp (missing-arg) :type tn)
412 ;; the list of dynamic state save TNs
413 (dynamic-state (list* (make-stack-pointer-tn)
414 (make-dynamic-state-tns))
416 ;; the target label for NLX entry
417 (target (gen-label) :type label))
418 (defprinter (ir2-nlx-info)
423 (defstruct (cloop (:conc-name loop-)
425 (:constructor make-loop)
427 ;; The kind of loop that this is. These values are legal:
430 ;; This is the outermost loop structure, and represents all the
431 ;; code in a component.
434 ;; A normal loop with only one entry.
437 ;; A segment of a "strange loop" in a non-reducible flow graph.
438 (kind (missing-arg) :type (member :outer :natural :strange))
439 ;; The first and last blocks in the loop. There may be more than one tail,
440 ;; since there may be multiple back branches to the same head.
441 (head nil :type (or cblock null))
442 (tail nil :type list)
443 ;; A list of all the blocks in this loop or its inferiors that have a
444 ;; successor outside of the loop.
445 (exits nil :type list)
446 ;; The loop that this loop is nested within. This is null in the outermost
448 (superior nil :type (or cloop null))
449 ;; A list of the loops nested directly within this one.
450 (inferiors nil :type list)
451 (depth 0 :type fixnum)
452 ;; The head of the list of blocks directly within this loop. We must recurse
453 ;; on INFERIORS to find all the blocks.
454 (blocks nil :type (or null cblock))
455 ;; Backend saves the first emitted block of each loop here.
458 (defprinter (cloop :conc-name loop-)
465 ;;;; VOPs and templates
467 ;;; A VOP is a Virtual Operation. It represents an operation and the
468 ;;; operands to the operation.
469 (def!struct (vop (:constructor make-vop (block node info args results))
471 ;; VOP-INFO structure containing static info about the operation
472 (info nil :type (or vop-info null))
473 ;; the IR2-BLOCK this VOP is in
474 (block (missing-arg) :type ir2-block)
475 ;; VOPs evaluated after and before this one. Null at the
476 ;; beginning/end of the block, and temporarily during IR2
478 (next nil :type (or vop null))
479 (prev nil :type (or vop null))
480 ;; heads of the TN-REF lists for operand TNs, linked using the
482 (args nil :type (or tn-ref null))
483 (results nil :type (or tn-ref null))
484 ;; head of the list of write refs for each explicitly allocated
485 ;; temporary, linked together using the ACROSS slot
486 (temps nil :type (or tn-ref null))
487 ;; head of the list of all TN-REFs for references in this VOP,
488 ;; linked by the NEXT-REF slot. There will be one entry for each
489 ;; operand and two (a read and a write) for each temporary.
490 (refs nil :type (or tn-ref null))
491 ;; stuff that is passed uninterpreted from IR2 conversion to
492 ;; codegen. The meaning of this slot is totally dependent on the VOP.
494 ;; the node that generated this VOP, for keeping track of debug info
495 (node nil :type (or node null))
496 ;; LOCAL-TN-BIT-VECTOR representing the set of TNs live after args
497 ;; are read and before results are written. This is only filled in
498 ;; when VOP-INFO-SAVE-P is non-null.
499 (save-set nil :type (or local-tn-bit-vector null)))
501 (info :prin1 (vop-info-name info))
504 (codegen-info :test codegen-info))
506 ;;; A TN-REF object contains information about a particular reference
507 ;;; to a TN. The information in TN-REFs largely determines how TNs are
509 (def!struct (tn-ref (:constructor make-tn-ref (tn write-p))
512 (tn (missing-arg) :type tn)
513 ;; Is this is a write reference? (as opposed to a read reference)
514 (write-p nil :type boolean)
515 ;; the link for a list running through all TN-REFs for this TN of
516 ;; the same kind (read or write)
517 (next nil :type (or tn-ref null))
518 ;; the VOP where the reference happens, or NIL temporarily
519 (vop nil :type (or vop null))
520 ;; the link for a list of all TN-REFs in VOP, in reverse order of
522 (next-ref nil :type (or tn-ref null))
523 ;; the link for a list of the TN-REFs in VOP of the same kind
524 ;; (argument, result, temp)
525 (across nil :type (or tn-ref null))
526 ;; If true, this is a TN-REF also in VOP whose TN we would like
527 ;; packed in the same location as our TN. Read and write refs are
528 ;; always paired: TARGET in the read points to the write, and
530 (target nil :type (or null tn-ref))
531 ;; the load TN allocated for this operand, if any
532 (load-tn nil :type (or tn null)))
536 (vop :test vop :prin1 (vop-info-name (vop-info vop))))
538 ;;; A TEMPLATE object represents a particular IR2 coding strategy for
539 ;;; a known function.
540 (def!struct (template (:constructor nil)
541 #-sb-xc-host (:pure t))
542 ;; the symbol name of this VOP. This is used when printing the VOP
543 ;; and is also used to provide a handle for definition and
545 (name nil :type symbol)
546 ;; the arg/result type restrictions. We compute this from the
547 ;; PRIMITIVE-TYPE restrictions to make life easier for IR1 phases
548 ;; that need to anticipate LTN's template selection.
549 (type (missing-arg) :type ctype)
550 ;; lists of restrictions on the argument and result types. A
551 ;; restriction may take several forms:
552 ;; -- The restriction * is no restriction at all.
553 ;; -- A restriction (:OR <primitive-type>*) means that the operand
554 ;; must have one of the specified primitive types.
555 ;; -- A restriction (:CONSTANT <predicate> <type-spec>) means that the
556 ;; argument (not a result) must be a compile-time constant that
557 ;; satisfies the specified predicate function. In this case, the
558 ;; constant value will be passed as an info argument rather than
559 ;; as a normal argument. <type-spec> is a Lisp type specifier for
560 ;; the type tested by the predicate, used when we want to represent
561 ;; the type constraint as a Lisp function type.
563 ;; If RESULT-TYPES is :CONDITIONAL, then this is an IF-FOO style
564 ;; conditional that yields its result as a control transfer. The
565 ;; emit function takes two info arguments: the target label and a
566 ;; boolean flag indicating whether to negate the sense of the test.
568 ;; If RESULT-TYPES is a cons whose car is :CONDITIONAL, then this is
569 ;; a flag-setting VOP. The rest is a list of condition descriptors to
570 ;; be interpreted by the BRANCH-IF VOP (see $ARCH/pred.lisp).
571 (arg-types nil :type list)
572 (result-types nil :type (or list (member :conditional) (cons (eql :conditional))))
573 ;; the primitive type restriction applied to each extra argument or
574 ;; result following the fixed operands. If NIL, no extra
575 ;; args/results are allowed. Otherwise, either * or a (:OR ...) list
576 ;; as described for the {ARG,RESULT}-TYPES.
577 (more-args-type nil :type (or (member nil *) cons))
578 (more-results-type nil :type (or (member nil *) cons))
579 ;; If true, this is a function that is called with no arguments to
580 ;; see whether this template can be emitted. This is used to
581 ;; conditionally compile for different target hardware
582 ;; configuarations (e.g. FP hardware.)
583 (guard nil :type (or function null))
584 ;; the policy under which this template is the best translation.
585 ;; Note that LTN might use this template under other policies if it
586 ;; can't figure out anything better to do.
587 (ltn-policy (missing-arg) :type ltn-policy)
588 ;; the base cost for this template, given optimistic assumptions
589 ;; such as no operand loading, etc.
590 (cost (missing-arg) :type index)
591 ;; If true, then this is a short noun-like phrase describing what
592 ;; this VOP "does", i.e. the implementation strategy. This is for
593 ;; use in efficiency notes.
594 (note nil :type (or string null))
595 ;; the number of trailing arguments to VOP or %PRIMITIVE that we
596 ;; bundle into a list and pass into the emit function. This provides
597 ;; a way to pass uninterpreted stuff directly to the code generator.
598 (info-arg-count 0 :type index))
599 (defprinter (template)
603 (more-args-type :test more-args-type :prin1 more-args-type)
604 (more-results-type :test more-results-type :prin1 more-results-type)
608 (info-arg-count :test (not (zerop info-arg-count))))
610 ;;; A VOP-INFO object holds the constant information for a given
611 ;;; virtual operation. We include TEMPLATE so that functions with a
612 ;;; direct VOP equivalent can be translated easily.
613 (def!struct (vop-info
615 (:make-load-form-fun ignore-it))
616 ;; side effects of this VOP and side effects that affect the value
618 (effects (missing-arg) :type attributes)
619 (affected (missing-arg) :type attributes)
620 ;; If true, causes special casing of TNs live after this VOP that
622 ;; -- If T, all such TNs that are allocated in a SC with a defined
623 ;; save-sc will be saved in a TN in the save SC before the VOP
624 ;; and restored after the VOP. This is used by call VOPs. A bit
625 ;; vector representing the live TNs is stored in the VOP-SAVE-SET.
626 ;; -- If :FORCE-TO-STACK, all such TNs will made into :ENVIRONMENT TNs
627 ;; and forced to be allocated in SCs without any save-sc. This is
628 ;; used by NLX entry vops.
629 ;; -- If :COMPUTE-ONLY, just compute the save set, don't do any saving.
630 ;; This is used to get the live variables for debug info.
631 (save-p nil :type (member t nil :force-to-stack :compute-only))
632 ;; info for automatic emission of move-arg VOPs by representation
633 ;; selection. If NIL, then do nothing special. If non-null, then
634 ;; there must be a more arg. Each more arg is moved to its passing
635 ;; location using the appropriate representation-specific MOVE-ARG
636 ;; VOP. The first (fixed) argument must be the control-stack frame
637 ;; pointer for the frame to move into. The first info arg is the
638 ;; list of passing locations.
640 ;; Additional constraints depend on the value:
646 ;; The second (fixed) arg is the NFP for the called function (from
650 ;; If needed, the old NFP is computed using COMPUTE-OLD-NFP.
651 (move-args nil :type (member nil :full-call :local-call :known-return))
652 ;; a list of sc-vectors representing the loading costs of each fixed
653 ;; argument and result
654 (arg-costs nil :type list)
655 (result-costs nil :type list)
656 ;; if true, SC-VECTORs representing the loading costs for any more
658 (more-arg-costs nil :type (or sc-vector null))
659 (more-result-costs nil :type (or sc-vector null))
660 ;; lists of SC-VECTORs mapping each SC to the SCs that we can load
661 ;; into. If a SC is directly acceptable to the VOP, then the entry
662 ;; is T. Otherwise, it is a list of the SC numbers of all the SCs
663 ;; that we can load into. This list will be empty if there is no
664 ;; load function which loads from that SC to an SC allowed by the
665 ;; operand SC restriction.
666 (arg-load-scs nil :type list)
667 (result-load-scs nil :type list)
668 ;; if true, a function that is called with the VOP to do operand
669 ;; targeting. This is done by modifying the TN-REF-TARGET slots in
670 ;; the TN-REFS so that they point to other TN-REFS in the same VOP.
671 (target-fun nil :type (or null function))
672 ;; a function that emits assembly code for a use of this VOP when it
673 ;; is called with the VOP structure. This is null if this VOP has no
674 ;; specified generator (i.e. if it exists only to be inherited by
676 (generator-function nil :type (or function null))
677 ;; a list of things that are used to parameterize an inherited
678 ;; generator. This allows the same generator function to be used for
679 ;; a group of VOPs with similar implementations.
680 (variant nil :type list)
681 ;; the number of arguments and results. Each regular arg/result
682 ;; counts as one, and all the more args/results together count as 1.
683 (num-args 0 :type index)
684 (num-results 0 :type index)
685 ;; a vector of the temporaries the vop needs. See EMIT-VOP
686 ;; in vmdef for information on how the temps are encoded.
687 (temps nil :type (or null (specializable-vector (unsigned-byte 16))))
688 ;; the order all the refs for this vop should be put in. Each
689 ;; operand is assigned a number in the following ordering: args,
690 ;; more-args, results, more-results, temps. This vector represents
691 ;; the order the operands should be put into in the next-ref link.
692 (ref-ordering nil :type (or null (specializable-vector (unsigned-byte 8))))
693 ;; a vector of the various targets that should be done. Each element
694 ;; encodes the source ref (shifted 8, it is also encoded in
695 ;; MAX-VOP-TN-REFS) and the dest ref index.
696 (targets nil :type (or null (specializable-vector (unsigned-byte 16)))))
700 ;;; copied from docs/internals/retargeting.tex by WHN 19990707:
702 ;;; A Storage Base represents a physical storage resource such as a
703 ;;; register set or stack frame. Storage bases for non-global
704 ;;; resources such as the stack are relativized by the environment
705 ;;; that the TN is allocated in. Packing conflict information is kept
706 ;;; in the storage base, but non-packed storage resources such as
707 ;;; closure environments also have storage bases.
709 ;;; Some storage bases:
710 ;;; General purpose registers
711 ;;; Floating point registers
712 ;;; Boxed (control) stack environment
713 ;;; Unboxed (number) stack environment
714 ;;; Closure environment
716 ;;; A storage class is a potentially arbitrary set of the elements in
717 ;;; a storage base. Although conceptually there may be a hierarchy of
718 ;;; storage classes such as "all registers", "boxed registers", "boxed
719 ;;; scratch registers", this doesn't exist at the implementation
720 ;;; level. Such things can be done by specifying storage classes whose
721 ;;; locations overlap. A TN shouldn't have lots of overlapping SC's as
722 ;;; legal SC's, since time would be wasted repeatedly attempting to
723 ;;; pack in the same locations.
728 ;;; Reg: any register (immediate objects)
729 ;;; Save-Reg: a boxed register near r15 (registers easily saved in a call)
730 ;;; Boxed-Reg: any boxed register (any boxed object)
731 ;;; Unboxed-Reg: any unboxed register (any unboxed object)
732 ;;; Float-Reg, Double-Float-Reg: float in FP register.
733 ;;; Stack: boxed object on the stack (on control stack)
734 ;;; Word: any 32bit unboxed object on nstack.
735 ;;; Double: any 64bit unboxed object on nstack.
737 ;;; The SB structure represents the global information associated with
739 (def!struct (sb (:make-load-form-fun just-dump-it-normally))
740 ;; name, for printing and reference
741 (name nil :type symbol)
742 ;; the kind of storage base (which determines the packing
744 (kind :non-packed :type (member :finite :unbounded :non-packed))
745 ;; the number of elements in the SB. If finite, this is the total
746 ;; size. If unbounded, this is the size that the SB is initially
748 (size 0 :type index))
752 ;;; A FINITE-SB holds information needed by the packing algorithm for
754 (def!struct (finite-sb (:include sb))
755 ;; the minimum number of location by which to grow this SB
756 ;; if it is :unbounded
757 (size-increment 1 :type index)
758 ;; current-size must always be a multiple of this. It is assumed
759 ;; to be a power of two.
760 (size-alignment 1 :type index)
761 ;; the number of locations currently allocated in this SB
762 (current-size 0 :type index)
763 ;; the last location packed in, used by pack to scatter TNs to
764 ;; prevent a few locations from getting all the TNs, and thus
765 ;; getting overcrowded, reducing the possibilities for targeting.
766 (last-offset 0 :type index)
767 ;; a vector containing, for each location in this SB, a vector
768 ;; indexed by IR2 block numbers, holding local conflict bit vectors.
769 ;; A TN must not be packed in a given location within a particular
770 ;; block if the LTN number for that TN in that block corresponds to
771 ;; a set bit in the bit-vector.
772 (conflicts '#() :type simple-vector)
773 ;; a vector containing, for each location in this SB, a bit-vector
774 ;; indexed by IR2 block numbers. If the bit corresponding to a block
775 ;; is set, then the location is in use somewhere in the block, and
776 ;; thus has a conflict for always-live TNs.
777 (always-live '#() :type simple-vector)
778 (always-live-count '#() :type simple-vector)
779 ;; a vector containing the TN currently live in each location in the
780 ;; SB, or NIL if the location is unused. This is used during load-tn pack.
781 (live-tns '#() :type simple-vector)
782 ;; the number of blocks for which the ALWAYS-LIVE and CONFLICTS
783 ;; might not be virgin, and thus must be reinitialized when PACK
784 ;; starts. Less then the length of those vectors when not all of the
785 ;; length was used on the previously packed component.
786 (last-block-count 0 :type index))
788 ;;; the SC structure holds the storage base that storage is allocated
789 ;;; in and information used to select locations within the SB
790 (def!struct (sc (:copier nil))
791 ;; name, for printing and reference
792 (name nil :type symbol)
793 ;; the number used to index SC cost vectors
794 (number 0 :type sc-number)
795 ;; the storage base that this SC allocates storage from
796 (sb nil :type (or sb null))
797 ;; the size of elements in this SC, in units of locations in the SB
798 (element-size 0 :type index)
799 ;; if our SB is finite, a list of the locations in this SC
800 (locations nil :type list)
801 ;; a list of the alternate (save) SCs for this SC
802 (alternate-scs nil :type list)
803 ;; a list of the constant SCs that can me moved into this SC
804 (constant-scs nil :type list)
805 ;; true if the values in this SC needs to be saved across calls
806 (save-p nil :type boolean)
807 ;; vectors mapping from SC numbers to information about how to load
808 ;; from the index SC to this one. MOVE-FUNS holds the names of
809 ;; the functions used to do loading, and LOAD-COSTS holds the cost
810 ;; of the corresponding move functions. If loading is impossible,
811 ;; then the entries are NIL. LOAD-COSTS is initialized to have a 0
813 (move-funs (make-array sc-number-limit :initial-element nil)
815 (load-costs (make-array sc-number-limit :initial-element nil)
817 ;; a vector mapping from SC numbers to possibly
818 ;; representation-specific move and coerce VOPs. Each entry is a
819 ;; list of VOP-INFOs for VOPs that move/coerce an object in the
820 ;; index SC's representation into this SC's representation. This
821 ;; vector is filled out with entries for all SCs that can somehow be
822 ;; coerced into this SC, not just those VOPs defined to directly
823 ;; move into this SC (i.e. it allows for operand loading on the move
826 ;; When there are multiple applicable VOPs, the template arg and
827 ;; result type restrictions are used to determine which one to use.
828 ;; The list is sorted by increasing cost, so the first applicable
829 ;; VOP should be used.
831 ;; Move (or move-arg) VOPs with descriptor results shouldn't have
832 ;; TNs wired in the standard argument registers, since there may
833 ;; already be live TNs wired in those locations holding the values
834 ;; that we are setting up for unknown-values return.
835 (move-vops (make-array sc-number-limit :initial-element nil)
837 ;; the costs corresponding to the MOVE-VOPS. Separate because this
838 ;; info is needed at meta-compile time, while the MOVE-VOPs don't
839 ;; exist till load time. If no move is defined, then the entry is
841 (move-costs (make-array sc-number-limit :initial-element nil)
843 ;; similar to Move-VOPs, except that we only ever use the entries
844 ;; for this SC and its alternates, since we never combine complex
845 ;; representation conversion with argument passing.
846 (move-arg-vops (make-array sc-number-limit :initial-element nil)
848 ;; true if this SC or one of its alternates in in the NUMBER-STACK SB.
849 (number-stack-p nil :type boolean)
850 ;; alignment restriction. The offset must be an even multiple of this.
851 ;; this must be a power of two.
852 (alignment 1 :type (and index (integer 1)))
853 ;; a list of locations that we avoid packing in during normal
854 ;; register allocation to ensure that these locations will be free
855 ;; for operand loading. This prevents load-TN packing from thrashing
856 ;; by spilling a lot.
857 (reserve-locations nil :type list))
863 (def!struct (tn (:include sset-element)
864 (:constructor make-random-tn)
865 (:constructor make-tn (number kind primitive-type sc))
867 ;; The kind of TN this is:
870 ;; A normal, non-constant TN, representing a variable or temporary.
871 ;; Lifetime information is computed so that packing can be done.
874 ;; A TN that has hidden references (debugger or NLX), and thus must be
875 ;; allocated for the duration of the environment it is referenced in.
877 ;; :DEBUG-ENVIRONMENT
878 ;; Like :ENVIRONMENT, but is used for TNs that we want to be able to
879 ;; target to/from and that don't absolutely have to be live
880 ;; everywhere. These TNs are live in all blocks in the environment
881 ;; that don't reference this TN.
884 ;; A TN that implicitly conflicts with all other TNs. No conflict
889 ;; A TN used for saving a :NORMAL TN across function calls. The
890 ;; lifetime information slots are unitialized: get the original
891 ;; TN out of the SAVE-TN slot and use it for conflicts. SAVE-ONCE
892 ;; is like :SAVE, except that it is only save once at the single
893 ;; writer of the original TN.
896 ;; A TN that was explicitly specified as the save TN for another TN.
897 ;; When we actually get around to doing the saving, this will be
898 ;; changed to :SAVE or :SAVE-ONCE.
901 ;; A load-TN used to compute an argument or result that is
902 ;; restricted to some finite SB. Load TNs don't have any conflict
903 ;; information. Load TN pack uses a special local conflict
904 ;; determination method.
907 ;; Represents a constant, with TN-LEAF a CONSTANT leaf. Lifetime
908 ;; information isn't computed, since the value isn't allocated by
909 ;; pack, but is instead generated as a load at each use. Since
910 ;; lifetime analysis isn't done on :CONSTANT TNs, they don't have
911 ;; LOCAL-NUMBERs and similar stuff.
914 ;; A special kind of TN used to represent initialization of local
915 ;; call arguments in the caller. It provides another name for the
916 ;; argument TN so that lifetime analysis doesn't get confused by
917 ;; self-recursive calls. Lifetime analysis treats this the same
918 ;; as :NORMAL, but then at the end merges the conflict info into
919 ;; the original TN and replaces all uses of the alias with the
920 ;; original TN. SAVE-TN holds the aliased TN.
922 :type (member :normal :environment :debug-environment
923 :save :save-once :specified-save :load :constant
925 ;; the primitive-type for this TN's value. Null in restricted or
927 (primitive-type nil :type (or primitive-type null))
928 ;; If this TN represents a variable or constant, then this is the
929 ;; corresponding LEAF.
930 (leaf nil :type (or leaf null))
931 ;; thread that links TNs together so that we can find them
932 (next nil :type (or tn null))
933 ;; head of TN-REF lists for reads and writes of this TN
934 (reads nil :type (or tn-ref null))
935 (writes nil :type (or tn-ref null))
936 ;; a link we use when building various temporary TN lists
937 (next* nil :type (or tn null))
938 ;; some block that contains a reference to this TN, or NIL if we
939 ;; haven't seen any reference yet. If the TN is local, then this is
940 ;; the block it is local to.
941 (local nil :type (or ir2-block null))
942 ;; If a local TN, the block relative number for this TN. Global TNs
943 ;; whose liveness changes within a block are also assigned a local
944 ;; number during the conflicts analysis of that block. If the TN has
945 ;; no local number within the block, then this is NIL.
946 (local-number nil :type (or local-tn-number null))
947 ;; If this object is a local TN, this slot is a bit-vector with 1
948 ;; for the local-number of every TN that we conflict with.
949 (local-conflicts (make-array local-tn-limit
952 :type local-tn-bit-vector)
953 ;; head of the list of GLOBAL-CONFLICTS structures for a global TN.
954 ;; This list is sorted by block number (i.e. reverse DFO), allowing
955 ;; the intersection between the lifetimes for two global TNs to be
956 ;; easily found. If null, then this TN is a local TN.
957 (global-conflicts nil :type (or global-conflicts null))
958 ;; During lifetime analysis, this is used as a pointer into the
959 ;; conflicts chain, for scanning through blocks in reverse DFO.
960 (current-conflict nil)
961 ;; In a :SAVE TN, this is the TN saved. In a :NORMAL or :ENVIRONMENT
962 ;; TN, this is the associated save TN. In TNs with no save TN, this
964 (save-tn nil :type (or tn null))
965 ;; After pack, the SC we packed into. Beforehand, the SC we want to
966 ;; pack into, or null if we don't know.
967 (sc nil :type (or sc null))
968 ;; the offset within the SB that this TN is packed into. This is what
969 ;; indicates that the TN is packed
970 (offset nil :type (or index null))
971 ;; some kind of info about how important this TN is
972 (cost 0 :type fixnum)
973 ;; If a :ENVIRONMENT or :DEBUG-ENVIRONMENT TN, this is the
974 ;; physical environment that the TN is live throughout.
975 (physenv nil :type (or physenv null))
976 ;; The depth of the deepest loop that this TN is used in.
977 (loop-depth 0 :type fixnum))
978 (def!method print-object ((tn tn) stream)
979 (print-unreadable-object (tn stream :type t)
980 ;; KLUDGE: The distinction between PRINT-TN and PRINT-OBJECT on TN is
981 ;; not very mnemonic. -- WHN 20000124
982 (print-tn-guts tn stream)))
984 ;;; The GLOBAL-CONFLICTS structure represents the conflicts for global
985 ;;; TNs. Each global TN has a list of these structures, one for each
986 ;;; block that it is live in. In addition to representing the result of
987 ;;; lifetime analysis, the global conflicts structure is used during
988 ;;; lifetime analysis to represent the set of TNs live at the start of
990 (defstruct (global-conflicts
991 (:constructor make-global-conflicts (kind tn block number))
993 ;; the IR2-BLOCK that this structure represents the conflicts for
994 (block (missing-arg) :type ir2-block)
995 ;; thread running through all the GLOBAL-CONFLICTSs for BLOCK. This
996 ;; thread is sorted by TN number
997 (next-blockwise nil :type (or global-conflicts null))
998 ;; the way that TN is used by BLOCK
1001 ;; The TN is read before it is written. It starts the block live,
1002 ;; but is written within the block.
1005 ;; The TN is written before any read. It starts the block dead,
1006 ;; and need not have a read within the block.
1009 ;; The TN is read, but never written. It starts the block live,
1010 ;; and is not killed by the block. Lifetime analysis will promote
1011 ;; :READ-ONLY TNs to :LIVE if they are live at the block end.
1014 ;; The TN is not referenced. It is live everywhere in the block.
1015 (kind :read-only :type (member :read :write :read-only :live))
1016 ;; a local conflicts vector representing conflicts with TNs live in
1017 ;; BLOCK. The index for the local TN number of each TN we conflict
1018 ;; with in this block is 1. To find the full conflict set, the :LIVE
1019 ;; TNs for BLOCK must also be included. This slot is not meaningful
1020 ;; when KIND is :LIVE.
1021 (conflicts (make-array local-tn-limit
1024 :type local-tn-bit-vector)
1025 ;; the TN we are recording conflicts for.
1026 (tn (missing-arg) :type tn)
1027 ;; thread through all the GLOBAL-CONFLICTSs for TN
1028 (next-tnwise nil :type (or global-conflicts null))
1029 ;; TN's local TN number in BLOCK. :LIVE TNs don't have local numbers.
1030 (number nil :type (or local-tn-number null)))
1031 (defprinter (global-conflicts)
1035 (number :test number))