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