X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fvop.lisp;h=ae18a61183fca96fff76fe8afd8872c3924384b6;hb=19319c931fc1636835dbef71808cc10e252bcf45;hp=b4316cccaf9f3502aa52f803798de906b24dc2c3;hpb=95a6db7329b91dd90d165dd4057b9b5098d34aa2;p=sbcl.git diff --git a/src/compiler/vop.lisp b/src/compiler/vop.lisp index b4316cc..ae18a61 100644 --- a/src/compiler/vop.lisp +++ b/src/compiler/vop.lisp @@ -14,40 +14,41 @@ ;;; the largest number of TNs whose liveness changes that we can have ;;; in any block -(defconstant local-tn-limit 64) +(def!constant local-tn-limit 64) (deftype local-tn-number () `(integer 0 (,local-tn-limit))) (deftype local-tn-count () `(integer 0 ,local-tn-limit)) (deftype local-tn-vector () `(simple-vector ,local-tn-limit)) (deftype local-tn-bit-vector () `(simple-bit-vector ,local-tn-limit)) -;;; Type of an SC number. +;;; type of an SC number (deftype sc-number () `(integer 0 (,sc-number-limit))) -;;; Types for vectors indexed by SC numbers. +;;; types for vectors indexed by SC numbers (deftype sc-vector () `(simple-vector ,sc-number-limit)) (deftype sc-bit-vector () `(simple-bit-vector ,sc-number-limit)) -;;; The different policies we can use to determine the coding strategy. -(deftype policies () +;;; the different policies we can use to determine the coding strategy +(deftype ltn-policy () '(member :safe :small :fast :fast-safe)) ;;;; PRIMITIVE-TYPEs -;;; The primitive type is used to represent the aspects of type interesting -;;; to the VM. Selection of IR2 translation templates is done on the basis of -;;; the primitive types of the operands, and the primitive type of a value -;;; is used to constrain the possible representations of that value. -(defstruct primitive-type - ;; The name of this primitive-type. +;;; A PRIMITIVE-TYPE is used to represent the aspects of type +;;; interesting to the VM. Selection of IR2 translation templates is +;;; done on the basis of the primitive types of the operands, and the +;;; primitive type of a value is used to constrain the possible +;;; representations of that value. +(defstruct (primitive-type (:copier nil)) + ;; the name of this PRIMITIVE-TYPE (name nil :type symbol) - ;; A list the SC numbers for all the SCs that a TN of this type can be - ;; allocated in. + ;; a list of the SC numbers for all the SCs that a TN of this type + ;; can be allocated in (scs nil :type list) - ;; The Lisp type equivalent to this type. If this type could never be - ;; returned by Primitive-Type, then this is the NIL (or empty) type. - (type (required-argument) :type ctype) - ;; The template used to check that an object is of this type. This is a + ;; the Lisp type equivalent to this type. If this type could never be + ;; returned by PRIMITIVE-TYPE, then this is the NIL (or empty) type + (specifier (missing-arg) :type type-specifier) + ;; the template used to check that an object is of this type. This is a ;; template of one argument and one result, both of primitive-type T. If ;; the argument is of the correct type, then it is delivered into the ;; result. If the type is incorrect, then an error is signalled. @@ -58,111 +59,121 @@ ;;;; IR1 annotations used for IR2 conversion -;;; Block-Info -;;; Holds the IR2-Block structure. If there are overflow blocks, then this -;;; points to the first IR2-Block. The Block-Info of the dummy component -;;; head and tail are dummy IR2 blocks that begin and end the emission order -;;; thread. +;;; BLOCK-INFO +;;; Holds the IR2-BLOCK structure. If there are overflow blocks, +;;; then this points to the first IR2-BLOCK. The BLOCK-INFO of the +;;; dummy component head and tail are dummy IR2 blocks that begin +;;; and end the emission order thread. ;;; -;;; Component-Info -;;; Holds the IR2-Component structure. +;;; COMPONENT-INFO +;;; Holds the IR2-COMPONENT structure. ;;; -;;; Continuation-Info -;;; Holds the IR2-Continuation structure. Continuations whose values aren't -;;; used won't have any. +;;; LVAR-INFO +;;; Holds the IR2-LVAR structure. LVARs whose values aren't used +;;; won't have any. XXX ;;; -;;; Cleanup-Info -;;; If non-null, then a TN in which the affected dynamic environment pointer -;;; should be saved after the binding is instantiated. +;;; CLEANUP-INFO +;;; If non-null, then a TN in which the affected dynamic +;;; environment pointer should be saved after the binding is +;;; instantiated. ;;; -;;; Environment-Info -;;; Holds the IR2-Environment structure. +;;; PHYSENV-INFO +;;; Holds the IR2-PHYSENV structure. ;;; -;;; Tail-Set-Info -;;; Holds the Return-Info structure. +;;; TAIL-SET-INFO +;;; Holds the RETURN-INFO structure. ;;; -;;; NLX-Info-Info -;;; Holds the IR2-NLX-Info structure. +;;; NLX-INFO-INFO +;;; Holds the IR2-NLX-INFO structure. ;;; -;;; Leaf-Info -;;; If a non-set lexical variable, the TN that holds the value in the home -;;; environment. If a constant, then the corresponding constant TN. -;;; If an XEP lambda, then the corresponding Entry-Info structure. +;;; LEAF-INFO +;;; If a non-set lexical variable, the TN that holds the value in +;;; the home environment. If a constant, then the corresponding +;;; constant TN. If an XEP lambda, then the corresponding +;;; Entry-Info structure. ;;; -;;; Basic-Combination-Info +;;; BASIC-COMBINATION-INFO ;;; The template chosen by LTN, or -;;; :FULL if this is definitely a full call. -;;; :FUNNY if this is an oddball thing with IR2-convert. -;;; :LOCAL if this is a local call. +;;; :FULL if this is definitely a full call. +;;; :FUNNY if this is an oddball thing with IR2-convert. +;;; :LOCAL if this is a local call. ;;; -;;; Node-Tail-P +;;; NODE-TAIL-P ;;; After LTN analysis, this is true only in combination nodes that are ;;; truly tail recursive. -;;; The IR2-Block structure holds information about a block that is used during -;;; and after IR2 conversion. It is stored in the Block-Info slot for the -;;; associated block. +;;; An IR2-BLOCK holds information about a block that is used during +;;; and after IR2 conversion. It is stored in the BLOCK-INFO slot for +;;; the associated block. (defstruct (ir2-block (:include block-annotation) - (:constructor make-ir2-block (block))) - ;; The IR2-Block's number, which differs from Block's Block-Number if any - ;; blocks are split. This is assigned by lifetime analysis. + (:constructor make-ir2-block (block)) + (:copier nil)) + ;; the IR2-BLOCK's number, which differs from BLOCK's BLOCK-NUMBER + ;; if any blocks are split. This is assigned by lifetime analysis. (number nil :type (or index null)) - ;; Information about unknown-values continuations that is used by stack - ;; analysis to do stack simulation. A unknown-values continuation is Pushed - ;; if its Dest is in another block. Similarly, a continuation is Popped if - ;; its Dest is in this block but has its uses elsewhere. The continuations - ;; are in the order that are pushed/popped in the block. Note that the args - ;; to a single MV-Combination appear reversed in Popped, since we must - ;; effectively pop the last argument first. All pops must come before all - ;; pushes (although internal MV uses may be interleaved.) Popped is computed - ;; by LTN, and Pushed is computed by stack analysis. + ;; information about unknown-values LVARs that is used by stack + ;; analysis to do stack simulation. An UNKNOWN-VALUES LVAR is PUSHED + ;; if its DEST is in another block. Similarly, a LVAR is POPPED if + ;; its DEST is in this block but has its uses elsewhere. The LVARs + ;; are in the order that are pushed/popped in the block. Note that + ;; the args to a single MV-COMBINATION appear reversed in POPPED, + ;; since we must effectively pop the last argument first. All pops + ;; must come before all pushes (although internal MV uses may be + ;; interleaved.) POPPED is computed by LTN, and PUSHED is computed + ;; by stack analysis. (pushed () :type list) (popped () :type list) - ;; The result of stack analysis: lists of all the unknown-values - ;; continuations on the stack at the block start and end, topmost - ;; continuation first. + ;; the result of stack analysis: lists of all the unknown-values + ;; LVARs on the stack at the block start and end, topmost LVAR + ;; first. (start-stack () :type list) (end-stack () :type list) - ;; The first and last VOP in this block. If there are none, both slots are - ;; null. + ;; the first and last VOP in this block. If there are none, both + ;; slots are null. (start-vop nil :type (or vop null)) (last-vop nil :type (or vop null)) - ;; Number of local TNs actually allocated. + ;; the number of local TNs actually allocated (local-tn-count 0 :type local-tn-count) - ;; A vector that maps local TN numbers to TNs. Some entries may be NIL, - ;; indicating that that number is unused. (This allows us to delete local - ;; conflict information without compressing the LTN numbers.) - ;; - ;; If an entry is :More, then this block contains only a single VOP. This - ;; VOP has so many more arguments and/or results that they cannot all be - ;; assigned distinct LTN numbers. In this case, we assign all the more args - ;; one LTN number, and all the more results another LTN number. We can do - ;; this, since more operands are referenced simultaneously as far as conflict - ;; analysis is concerned. Note that all these :More TNs will be global TNs. + ;; a vector that maps local TN numbers to TNs. Some entries may be + ;; NIL, indicating that that number is unused. (This allows us to + ;; delete local conflict information without compressing the LTN + ;; numbers.) + ;; + ;; If an entry is :MORE, then this block contains only a single VOP. + ;; This VOP has so many more arguments and/or results that they + ;; cannot all be assigned distinct LTN numbers. In this case, we + ;; assign all the more args one LTN number, and all the more results + ;; another LTN number. We can do this, since more operands are + ;; referenced simultaneously as far as conflict analysis is + ;; concerned. Note that all these :MORE TNs will be global TNs. (local-tns (make-array local-tn-limit) :type local-tn-vector) - ;; Bit-vectors used during lifetime analysis to keep track of references to - ;; local TNs. When indexed by the LTN number, the index for a TN is non-zero - ;; in Written if it is ever written in the block, and in Live-Out if - ;; the first reference is a read. + ;; Bit-vectors used during lifetime analysis to keep track of + ;; references to local TNs. When indexed by the LTN number, the + ;; index for a TN is non-zero in WRITTEN if it is ever written in + ;; the block, and in LIVE-OUT if the first reference is a read. (written (make-array local-tn-limit :element-type 'bit - :initial-element 0) - :type local-tn-bit-vector) + :initial-element 0) + :type local-tn-bit-vector) (live-out (make-array local-tn-limit :element-type 'bit) - :type local-tn-bit-vector) - ;; Similar to the above, but is updated by lifetime flow analysis to have a 1 - ;; for LTN numbers of TNs live at the end of the block. This takes into - ;; account all TNs that aren't :Live. - (live-in (make-array local-tn-limit :element-type 'bit - :initial-element 0) - :type local-tn-bit-vector) - ;; A thread running through the global-conflicts structures for this block, - ;; sorted by TN number. + :type local-tn-bit-vector) + ;; This is similar to the above, but is updated by lifetime flow + ;; analysis to have a 1 for LTN numbers of TNs live at the end of + ;; the block. This takes into account all TNs that aren't :LIVE. + (live-in (make-array local-tn-limit :element-type 'bit :initial-element 0) + :type local-tn-bit-vector) + ;; a thread running through the global-conflicts structures for this + ;; block, sorted by TN number (global-tns nil :type (or global-conflicts null)) - ;; The assembler label that points to the beginning of the code for this - ;; block. Null when we haven't assigned a label yet. + ;; the assembler label that points to the beginning of the code for + ;; this block, or NIL when we haven't assigned a label yet (%label nil) - ;; List of Location-Info structures describing all the interesting (to the - ;; debugger) locations in this block. + ;; the assembler label that points to the trampoline for this block, + ;; or NIL if unassigned yet. Only meaningful for local call targets. + (%trampoline-label nil) + ;; T if the preceding block assumes it can drop thru to %label + (dropped-thru-to nil) + ;; list of LOCATION-INFO structures describing all the interesting + ;; (to the debugger) locations in this block (locations nil :type list)) (defprinter (ir2-block) @@ -173,204 +184,216 @@ (local-tn-count :test (not (zerop local-tn-count))) (%label :test %label)) -;;; The IR2-Continuation structure is used to annotate continuations that are -;;; used as a function result continuation or that receive MVs. -(defstruct (ir2-continuation - (:constructor make-ir2-continuation (primitive-type))) - ;; If this is :Delayed, then this is a single value continuation for which - ;; the evaluation of the use is to be postponed until the evaluation of - ;; destination. This can be done for ref nodes or predicates whose - ;; destination is an IF. - ;; - ;; If this is :Fixed, then this continuation has a fixed number of values, - ;; with the TNs in Locs. - ;; - ;; If this is :Unknown, then this is an unknown-values continuation, using - ;; the passing locations in Locs. - ;; - ;; If this is :Unused, then this continuation should never actually be used +;;; An IR2-LVAR structure is used to annotate LVARs that are used as a +;;; function result LVARs or that receive MVs. +(defstruct (ir2-lvar + (:constructor make-ir2-lvar (primitive-type)) + (:copier nil)) + ;; If this is :DELAYED, then this is a single value LVAR for which + ;; the evaluation of the use is to be postponed until the evaluation + ;; of destination. This can be done for ref nodes or predicates + ;; whose destination is an IF. + ;; + ;; If this is :FIXED, then this LVAR has a fixed number of values, + ;; with the TNs in LOCS. + ;; + ;; If this is :UNKNOWN, then this is an unknown-values LVAR, using + ;; the passing locations in LOCS. + ;; + ;; If this is :UNUSED, then this LVAR should never actually be used ;; as the destination of a value: it is only used tail-recursively. (kind :fixed :type (member :delayed :fixed :unknown :unused)) - ;; The primitive-type of the first value of this continuation. This is - ;; primarily for internal use during LTN, but it also records the type - ;; restriction on delayed references. In multiple-value contexts, this is - ;; null to indicate that it is meaningless. This is always (primitive-type - ;; (continuation-type cont)), which may be more restrictive than the - ;; tn-primitive-type of the value TN. This is becase the value TN must hold - ;; any possible type that could be computed (before type checking.) + ;; The primitive-type of the first value of this LVAR. This is + ;; primarily for internal use during LTN, but it also records the + ;; type restriction on delayed references. In multiple-value + ;; contexts, this is null to indicate that it is meaningless. This + ;; is always (primitive-type (lvar-type cont)), which may be more + ;; restrictive than the tn-primitive-type of the value TN. This is + ;; becase the value TN must hold any possible type that could be + ;; computed (before type checking.) XXX (primitive-type nil :type (or primitive-type null)) - ;; Locations used to hold the values of the continuation. If the number - ;; of values if fixed, then there is one TN per value. If the number of - ;; values is unknown, then this is a two-list of TNs holding the start of the - ;; values glob and the number of values. Note that since type checking is - ;; the responsibility of the values receiver, these TNs primitive type is - ;; only based on the proven type information. - (locs nil :type list)) + ;; Locations used to hold the values of the LVAR. If the number of + ;; values if fixed, then there is one TN per value. If the number of + ;; values is unknown, then this is a two-list of TNs holding the + ;; start of the values glob and the number of values. Note that + ;; since type checking is the responsibility of the values receiver, + ;; these TNs primitive type is only based on the proven type + ;; information. + (locs nil :type list) + (stack-pointer nil :type (or tn null))) -(defprinter (ir2-continuation) +(defprinter (ir2-lvar) kind primitive-type locs) -;;; The IR2-Component serves mostly to accumulate non-code information about -;;; the component being compiled. -(defstruct ir2-component - ;; The counter used to allocate global TN numbers. +;;; An IR2-COMPONENT serves mostly to accumulate non-code information +;;; about the component being compiled. +(defstruct (ir2-component (:copier nil)) + ;; the counter used to allocate global TN numbers (global-tn-counter 0 :type index) - ;; Normal-TNs is the head of the list of all the normal TNs that need to be - ;; packed, linked through the Next slot. We place TNs on this list when we - ;; allocate them so that Pack can find them. + ;; NORMAL-TNS is the head of the list of all the normal TNs that + ;; need to be packed, linked through the Next slot. We place TNs on + ;; this list when we allocate them so that Pack can find them. ;; - ;; Restricted-TNs are TNs that must be packed within a finite SC. We pack - ;; these TNs first to ensure that the restrictions will be satisfied (if - ;; possible). + ;; RESTRICTED-TNS are TNs that must be packed within a finite SC. We + ;; pack these TNs first to ensure that the restrictions will be + ;; satisfied (if possible). ;; - ;; Wired-TNs are TNs that must be packed at a specific location. The SC - ;; and Offset are already filled in. + ;; WIRED-TNs are TNs that must be packed at a specific location. The + ;; SC and OFFSET are already filled in. ;; - ;; Constant-TNs are non-packed TNs that represent constants. :Constant TNs - ;; may eventually be converted to :Cached-Constant normal TNs. + ;; CONSTANT-TNs are non-packed TNs that represent constants. (normal-tns nil :type (or tn null)) (restricted-tns nil :type (or tn null)) (wired-tns nil :type (or tn null)) (constant-tns nil :type (or tn null)) - ;; A list of all the :COMPONENT TNs (live throughout the component.) These - ;; TNs will also appear in the {NORMAL,RESTRICTED,WIRED} TNs as appropriate - ;; to their location. + ;; a list of all the :COMPONENT TNs (live throughout the component). + ;; These TNs will also appear in the {NORMAL,RESTRICTED,WIRED} TNs + ;; as appropriate to their location. (component-tns () :type list) ;; If this component has a NFP, then this is it. (nfp nil :type (or tn null)) - ;; A list of the explicitly specified save TNs (kind :SPECIFIED-SAVE). These - ;; TNs will also appear in the {NORMAL,RESTRICTED,WIRED} TNs as appropriate - ;; to their location. + ;; a list of the explicitly specified save TNs (kind + ;; :SPECIFIED-SAVE). These TNs will also appear in the + ;; {NORMAL,RESTRICTED,WIRED} TNs as appropriate to their location. (specified-save-tns () :type list) - ;; Values-Receivers is a list of all the blocks whose ir2-block has a - ;; non-null value for Popped. This slot is initialized by LTN-Analyze as an - ;; input to Stack-Analyze. + ;; a list of all the blocks whose IR2-BLOCK has a non-null value for + ;; POPPED. This slot is initialized by LTN-ANALYZE as an input to + ;; STACK-ANALYZE. (values-receivers nil :type list) - ;; An adjustable vector that records all the constants in the constant pool. - ;; A non-immediate :Constant TN with offset 0 refers to the constant in - ;; element 0, etc. Normal constants are represented by the placing the - ;; Constant leaf in this vector. A load-time constant is distinguished by - ;; being a cons (Kind . What). Kind is a keyword indicating how the constant - ;; is computed, and What is some context. + ;; an adjustable vector that records all the constants in the + ;; constant pool. A non-immediate :CONSTANT TN with offset 0 refers + ;; to the constant in element 0, etc. Normal constants are + ;; represented by the placing the CONSTANT leaf in this vector. A + ;; load-time constant is distinguished by being a cons (KIND . + ;; WHAT). KIND is a keyword indicating how the constant is computed, + ;; and WHAT is some context. ;; ;; These load-time constants are recognized: ;; ;; (:entry . ) - ;; Is replaced by the code pointer for the specified function. This is - ;; how compiled code (including DEFUN) gets its hands on a function. - ;; is the XEP lambda for the called function; its Leaf-Info - ;; should be an Entry-Info structure. + ;; Is replaced by the code pointer for the specified function. + ;; This is how compiled code (including DEFUN) gets its hands on + ;; a function. is the XEP lambda for the called + ;; function; its LEAF-INFO should be an ENTRY-INFO structure. ;; ;; (:label .