X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fnode.lisp;h=4f0ad48b24378f091091ca15b7c940e8a65721c2;hb=988afd9d54ba6c8a915544822658824ab6ae0d6c;hp=b44d7a2c9e7dd502760946898b96df534c276efd;hpb=57e21c4b62e8c1a1ee7ef59ed2abb0c864fb06bc;p=sbcl.git diff --git a/src/compiler/node.lisp b/src/compiler/node.lisp index b44d7a2..4f0ad48 100644 --- a/src/compiler/node.lisp +++ b/src/compiler/node.lisp @@ -12,20 +12,15 @@ (in-package "SB!C") -;;; The front-end data structure (IR1) is composed of nodes and -;;; continuations. The general idea is that continuations contain -;;; top-down information and nodes contain bottom-up, derived -;;; information. A continuation represents a place in the code, while -;;; a node represents code that does something. -;;; -;;; This representation is more of a flow-graph than an augmented -;;; syntax tree. The evaluation order is explicitly represented in the -;;; linkage by continuations, rather than being implicit in the nodes -;;; which receive the the results of evaluation. This allows us to -;;; decouple the flow of results from the flow of control. A -;;; continuation represents both, but the continuation can represent -;;; the case of a discarded result by having no DEST. +;;; The front-end data structure (IR1) is composed of nodes, +;;; representing actual evaluations. Linear sequences of nodes in +;;; control-flow order are combined into blocks (but see +;;; JOIN-SUCCESSOR-IF-POSSIBLE for precise conditions); control +;;; transfers inside a block are represented with CTRANs and between +;;; blocks -- with BLOCK-SUCC/BLOCK-PRED lists; data transfers are +;;; represented with LVARs. +;;; "Lead-in" Control TRANsfer [to some node] (def!struct (ctran (:make-load-form-fun ignore-it) (:constructor make-ctran)) @@ -41,77 +36,69 @@ ;; has already been determined. ;; ;; :BLOCK-START - ;; The continuation that is the START of BLOCK. This is the only kind - ;; of continuation that can have more than one use. The BLOCK's - ;; START-USES is a list of all the uses. + ;; The continuation that is the START of BLOCK. ;; ;; :INSIDE-BLOCK ;; A continuation that is the NEXT of some node in BLOCK. (kind :unused :type (member :unused :inside-block :block-start)) - ;; If this is a NODE, then it is the node which is to be evaluated - ;; next. This is always null in :DELETED and :UNUSED continuations, - ;; and will be null in a :INSIDE-BLOCK continuation when this is the - ;; CONT of the LAST. + ;; A NODE which is to be evaluated next. Null only temporary. (next nil :type (or node null)) ;; the node where this CTRAN is used, if unique. This is always null - ;; in :DELETED, :UNUSED and :BLOCK-START CTRANs, and is never null - ;; in :INSIDE-BLOCK continuations. + ;; in :UNUSED and :BLOCK-START CTRANs, and is never null in + ;; :INSIDE-BLOCK continuations. (use nil :type (or node null)) ;; the basic block this continuation is in. This is null only in - ;; :DELETED and :UNUSED continuations. Note that blocks that are - ;; unreachable but still in the DFO may receive deleted - ;; continuations, so it isn't o.k. to assume that any continuation - ;; that you pick up out of its DEST node has a BLOCK. - (block nil :type (or cblock null)) - ;; something or other that the back end annotates this continuation with - (info nil)) + ;; :UNUSED continuations. + (block nil :type (or cblock null))) + +(def!method print-object ((x ctran) stream) + (print-unreadable-object (x stream :type t :identity t) + (format stream " #~D" (cont-num x)))) +;;; Linear VARiable. Multiple-value (possibly of unknown number) +;;; temporal storage. (def!struct (lvar (:make-load-form-fun ignore-it) (:constructor make-lvar (&optional dest))) ;; The node which receives this value. NIL only temporarily. (dest nil :type (or node null)) - ;; cached type of this continuation's value. If NIL, then this must - ;; be recomputed: see CONTINUATION-DERIVED-TYPE. + ;; cached type of this lvar's value. If NIL, then this must be + ;; recomputed: see LVAR-DERIVED-TYPE. (%derived-type nil :type (or ctype null)) - ;; the node where this continuation is used, if unique. This is always - ;; null in :DELETED and :UNUSED continuations, and is never null in - ;; :INSIDE-BLOCK continuations. In a :BLOCK-START continuation, the - ;; BLOCK's START-USES indicate whether NIL means no uses or more - ;; than one use. + ;; the node (if unique) or a list of nodes where this lvar is used. (uses nil :type (or node list)) - ;; set to true when something about this continuation's value has - ;; changed. See REOPTIMIZE-CONTINUATION. This provides a way for IR1 + ;; set to true when something about this lvar's value has + ;; changed. See REOPTIMIZE-LVAR. This provides a way for IR1 ;; optimize to determine which operands to a node have changed. If ;; the optimizer for this node type doesn't care, it can elect not ;; to clear this flag. (reoptimize t :type boolean) ;; Cached type which is checked by DEST. If NIL, then this must be - ;; recomputed: see CONTINUATION-EXTERNALLY-CHECKABLE-TYPE. + ;; recomputed: see LVAR-EXTERNALLY-CHECKABLE-TYPE. (%externally-checkable-type nil :type (or null ctype)) - ;; something or other that the back end annotates this continuation with + ;; if the LVAR value is DYNAMIC-EXTENT, CLEANUP protecting it. + (dynamic-extent nil :type (or null cleanup)) + ;; something or other that the back end annotates this lvar with (info nil)) -#+nil -(def!method print-object ((x continuation) stream) +(def!method print-object ((x lvar) stream) (print-unreadable-object (x stream :type t :identity t) (format stream " #~D" (cont-num x)))) -(defstruct (node (:constructor nil) +(def!struct (node (:constructor nil) (:copier nil)) ;; unique ID for debugging #!+sb-show (id (new-object-id) :read-only t) ;; True if this node needs to be optimized. This is set to true - ;; whenever something changes about the value of a continuation - ;; whose DEST is this node. + ;; whenever something changes about the value of an lvar whose DEST + ;; is this node. (reoptimize t :type boolean) - ;; the continuation which receives the value of this node. This also - ;; indicates what we do controlwise after evaluating this node. This - ;; may be null during IR1 conversion. + ;; the ctran indicating what we do controlwise after evaluating this + ;; node. This is null if the node is the last in its block. (next nil :type (or ctran null)) - ;; the continuation that this node is the NEXT of. This is null - ;; during IR1 conversion when we haven't linked the node in yet or - ;; in nodes that have been deleted from the IR1 by UNLINK-NODE. + ;; the ctran that this node is the NEXT of. This is null during IR1 + ;; conversion when we haven't linked the node in yet or in nodes + ;; that have been deleted from the IR1 by UNLINK-NODE. (prev nil :type (or ctran null)) ;; the lexical environment this node was converted in (lexenv *lexenv* :type lexenv) @@ -149,13 +136,14 @@ ;; can null out this slot. (tail-p nil :type boolean)) -(defstruct (valued-node (:conc-name node-) +(def!struct (valued-node (:conc-name node-) (:include node) (:constructor nil) (:copier nil)) ;; the bottom-up derived type for this node. (derived-type *wild-type* :type ctype) - ;; may be NIL if the value is unused. + ;; Lvar, receiving the values, produced by this node. May be NIL if + ;; the value is unused. (lvar nil :type (or lvar null))) ;;; Flags that are used to indicate various things about a block, such @@ -164,7 +152,7 @@ ;;; lvar whose DEST is in this block. This indicates that the ;;; value-driven (forward) IR1 optimizations should be done on this block. ;;; -- FLUSH-P is set when code in this block becomes potentially flushable, -;;; usually due to a continuation's DEST becoming null. +;;; usually due to an lvar's DEST becoming null. ;;; -- TYPE-CHECK is true when the type check phase should be run on this ;;; block. IR1 optimize can introduce new blocks after type check has ;;; already run. We need to check these blocks, but there is no point in @@ -174,12 +162,11 @@ ;;; phases should not attempt to examine or modify blocks with DELETE-P ;;; set, since they may: ;;; - be in the process of being deleted, or -;;; - have no successors, or -;;; - receive :DELETED continuations. +;;; - have no successors. ;;; -- TYPE-ASSERTED, TEST-MODIFIED ;;; These flags are used to indicate that something in this block ;;; might be of interest to constraint propagation. TYPE-ASSERTED -;;; is set when a continuation type assertion is strengthened. +;;; is set when an lvar type assertion is strengthened. ;;; TEST-MODIFIED is set whenever the test for the ending IF has ;;; changed (may be true when there is no IF.) (!def-boolean-attribute block @@ -204,7 +191,7 @@ ;;; order. This latter numbering also forms the basis of the block ;;; numbering in the debug-info (though that is relative to the start ;;; of the function.) -(defstruct (cblock (:include sset-element) +(def!struct (cblock (:include sset-element) (:constructor make-block (start)) (:constructor make-block-key) (:conc-name block-) @@ -217,10 +204,9 @@ ;; 3. blocks with DELETE-P set (zero) (pred nil :type list) (succ nil :type list) - ;; the ctran which heads this block (either a :BLOCK-START or - ;; :DELETED-BLOCK-START), or NIL when we haven't made the start - ;; ctran yet (and in the dummy component head and tail - ;; blocks) + ;; the ctran which heads this block (a :BLOCK-START), or NIL when we + ;; haven't made the start ctran yet (and in the dummy component head + ;; and tail blocks) (start nil :type (or ctran null)) ;; the last node in this block. This is NIL when we are in the ;; process of building a block (and in the dummy component head and @@ -241,6 +227,13 @@ (gen nil) (in nil) (out nil) + ;; Set of all blocks that dominate this block. NIL is interpreted + ;; as "all blocks in component". + (dominators nil :type (or null sset)) + ;; the LOOP that this block belongs to + (loop nil :type (or null cloop)) + ;; next block in the loop. + (loop-next nil :type (or null cblock)) ;; the component this block is in, or NIL temporarily during IR1 ;; conversion and in deleted blocks (component (progn @@ -266,7 +259,7 @@ ;;; The BLOCK-ANNOTATION class is inherited (via :INCLUDE) by ;;; different BLOCK-INFO annotation structures so that code ;;; (specifically control analysis) can be shared. -(defstruct (block-annotation (:constructor nil) +(def!struct (block-annotation (:constructor nil) (:copier nil)) ;; The IR1 block that this block is in the INFO for. (block (missing-arg) :type cblock) @@ -288,9 +281,9 @@ ;;; size of flow analysis problems, this allows back-end data ;;; structures to be reclaimed after the compilation of each ;;; component. -(defstruct (component (:copier nil) - (:constructor - make-component (head tail &aux (last-block tail)))) +(def!struct (component (:copier nil) + (:constructor + make-component (head tail &aux (last-block tail)))) ;; unique ID for debugging #!+sb-show (id (new-object-id) :read-only t) ;; the kind of component @@ -388,7 +381,13 @@ ;; has already been analyzed, but new references have been added by ;; inline expansion. Unlike NEW-FUNCTIONALS, this is not disjoint ;; from COMPONENT-LAMBDAS. - (reanalyze-functionals nil :type list)) + (reanalyze-functionals nil :type list) + (delete-blocks nil :type list) + (nlx-info-generated-p nil :type boolean) + ;; this is filled by physical environment analysis + (dx-lvars nil :type list) + ;; The default LOOP in the component. + (outer-loop (make-loop :kind :outer :head head) :type cloop)) (defprinter (component :identity t) name #!+sb-show id @@ -431,25 +430,34 @@ ;;; The "mess-up" action is explicitly represented by a funny function ;;; call or ENTRY node. ;;; -;;; We guarantee that CLEANUPs only need to be done at block boundaries -;;; by requiring that the exit continuations initially head their +;;; We guarantee that CLEANUPs only need to be done at block +;;; boundaries by requiring that the exit ctrans initially head their ;;; blocks, and then by not merging blocks when there is a cleanup ;;; change. -(defstruct (cleanup (:copier nil)) +(def!struct (cleanup (:copier nil)) ;; the kind of thing that has to be cleaned up (kind (missing-arg) - :type (member :special-bind :catch :unwind-protect :block :tagbody)) + :type (member :special-bind :catch :unwind-protect + :block :tagbody :dynamic-extent)) ;; the node that messes things up. This is the last node in the ;; non-messed-up environment. Null only temporarily. This could be ;; deleted due to unreachability. (mess-up nil :type (or node null)) - ;; a list of all the NLX-INFO structures whose NLX-INFO-CLEANUP is - ;; this cleanup. This is filled in by physical environment analysis. - (nlx-info nil :type list)) + ;; For all kinds, except :DYNAMIC-EXTENT: a list of all the NLX-INFO + ;; structures whose NLX-INFO-CLEANUP is this cleanup. This is filled + ;; in by physical environment analysis. + ;; + ;; For :DYNAMIC-EXTENT: a list of all DX LVARs, preserved by this + ;; cleanup. This is filled when the cleanup is created (now by + ;; locall call analysis) and is rechecked by physical environment + ;; analysis. + (info nil :type list)) (defprinter (cleanup :identity t) kind mess-up - (nlx-info :test nlx-info)) + (info :test info)) +(defmacro cleanup-nlx-info (cleanup) + `(cleanup-info ,cleanup)) ;;; A PHYSENV represents the result of physical environment analysis. ;;; @@ -473,7 +481,7 @@ ;;; structure is attached to INFO and used to keep track of ;;; associations between these names and less-abstract things (like ;;; TNs, or eventually stack slots and registers). -- WHN 2001-09-29 -(defstruct (physenv (:copier nil)) +(def!struct (physenv (:copier nil)) ;; the function that allocates this physical environment (lambda (missing-arg) :type clambda :read-only t) ;; This ultimately converges to a list of all the LAMBDA-VARs and @@ -507,7 +515,7 @@ ;;; The tail set is somewhat approximate, because it is too early to ;;; be sure which calls will be tail-recursive. Any call that *might* ;;; end up tail-recursive causes TAIL-SET merging. -(defstruct (tail-set) +(def!struct (tail-set) ;; a list of all the LAMBDAs in this tail set (funs nil :type list) ;; our current best guess of the type returned by these functions. @@ -608,6 +616,8 @@ ;; true if there was ever a REF or SET node for this leaf. This may ;; be true when REFS and SETS are null, since code can be deleted. (ever-used nil :type boolean) + ;; is it declared dynamic-extent? + (dynamic-extent nil :type boolean) ;; some kind of info used by the back end (info nil)) @@ -753,7 +763,7 @@ ;; a lambda that is used in only one local call, and has in ;; effect been substituted directly inline. The return node is ;; deleted, and the result is computed with the actual result - ;; continuation for the call. + ;; lvar for the call. ;; ;; :MV-LET ;; Similar to :LET (as per FUNCTIONAL-LETLIKE-P), but the call @@ -800,9 +810,12 @@ ;; :DELETED ;; This function has been found to be uncallable, and has been ;; marked for deletion. + ;; + ;; :ZOMBIE + ;; Effectless [MV-]LET; has no BIND node. (kind nil :type (member nil :optional :deleted :external :toplevel :escape :cleanup :let :mv-let :assignment - :toplevel-xep)) + :zombie :toplevel-xep)) ;; Is this a function that some external entity (e.g. the fasl dumper) ;; refers to, so that even when it appears to have no references, it ;; shouldn't be deleted? In the old days (before @@ -896,10 +909,10 @@ ;; bind (because there are no variables left), but have not yet ;; actually deleted the LAMBDA yet. (bind nil :type (or bind null)) - ;; the RETURN node for this LAMBDA, or NIL if it has been deleted. - ;; This marks the end of the lambda, receiving the result of the - ;; body. In a LET, the return node is deleted, and the body delivers - ;; the value to the actual continuation. The return may also be + ;; the RETURN node for this LAMBDA, or NIL if it has been + ;; deleted. This marks the end of the lambda, receiving the result + ;; of the body. In a LET, the return node is deleted, and the body + ;; delivers the value to the actual lvar. The return may also be ;; deleted if it is unreachable. (return nil :type (or creturn null)) ;; If this CLAMBDA is a LET, then this slot holds the LAMBDA whose @@ -934,11 +947,15 @@ ;; retain it so that if the LET is deleted (due to a lack of vars), ;; we will still have caller's lexenv to figure out which cleanup is ;; in effect. - (call-lexenv nil :type (or lexenv null))) + (call-lexenv nil :type (or lexenv null)) + ;; list of embedded lambdas + (children nil :type list) + (parent nil :type (or clambda null))) (defprinter (clambda :conc-name lambda- :identity t) %source-name %debug-name #!+sb-show id + kind (type :test (not (eq type *universal-type*))) (where-from :test (not (eq where-from :assumed))) (vars :prin1 (mapcar #'leaf-source-name vars))) @@ -1099,7 +1116,7 @@ ;;; A REF represents a reference to a LEAF. REF-REOPTIMIZE is ;;; initially (and forever) NIL, since REFs don't receive any values ;;; and don't have any IR1 optimizer. -(defstruct (ref (:include valued-node (reoptimize nil)) +(def!struct (ref (:include valued-node (reoptimize nil)) (:constructor make-ref (leaf &aux (leaf-type (leaf-type leaf)) @@ -1113,9 +1130,7 @@ leaf) ;;; Naturally, the IF node always appears at the end of a block. -;;; NODE-CONT is a dummy continuation, and is there only to keep -;;; people happy. -(defstruct (cif (:include node) +(def!struct (cif (:include node) (:conc-name if-) (:predicate if-p) (:constructor make-if) @@ -1131,7 +1146,7 @@ consequent alternative) -(defstruct (cset (:include valued-node +(def!struct (cset (:include valued-node (derived-type (make-single-value-type *universal-type*))) (:conc-name set-) @@ -1149,9 +1164,8 @@ ;;; The BASIC-COMBINATION structure is used to represent both normal ;;; and multiple value combinations. In a let-like function call, this ;;; node appears at the end of its block and the body of the called -;;; function appears as the successor. The NODE-CONT remains the -;;; continuation which receives the value of the call. XXX -(defstruct (basic-combination (:include valued-node) +;;; function appears as the successor; the NODE-LVAR is null. +(def!struct (basic-combination (:include valued-node) (:constructor nil) (:copier nil)) ;; LVAR for the function @@ -1162,20 +1176,23 @@ (args nil :type list) ;; the kind of function call being made. :LOCAL means that this is a ;; local call to a function in the same component, and that argument - ;; syntax checking has been done, etc. Calls to known global - ;; functions are represented by storing the FUN-INFO for the - ;; function in this slot. :FULL is a call to an (as yet) unknown - ;; function. :ERROR is like :FULL, but means that we have discovered - ;; that the call contains an error, and should not be reconsidered - ;; for optimization. - (kind :full :type (or (member :local :full :error) fun-info)) + ;; syntax checking has been done, etc. Calls to known global + ;; functions are represented by storing :KNOWN in this slot and the + ;; FUN-INFO for that function in the FUN-INFO slot. :FULL is a call + ;; to an (as yet) unknown function, or to a known function declared + ;; NOTINLINE. :ERROR is like :FULL, but means that we have + ;; discovered that the call contains an error, and should not be + ;; reconsidered for optimization. + (kind :full :type (member :local :full :error :known)) + ;; if a call to a known global function, contains the FUN-INFO. + (fun-info nil :type (or fun-info null)) ;; some kind of information attached to this node by the back end (info nil)) ;;; The COMBINATION node represents all normal function calls, ;;; including FUNCALL. This is distinct from BASIC-COMBINATION so that ;;; an MV-COMBINATION isn't COMBINATION-P. -(defstruct (combination (:include basic-combination) +(def!struct (combination (:include basic-combination) (:constructor make-combination (fun)) (:copier nil))) (defprinter (combination :identity t) @@ -1187,18 +1204,10 @@ "")) args))) -(defun call-full-like-p (call) - (declare (type combination call)) - (let ((kind (basic-combination-kind call))) - (or (eq kind :full) - (and (fun-info-p kind) - (null (fun-info-templates kind)) - (not (fun-info-ir2-convert kind)))))) - ;;; An MV-COMBINATION is to MULTIPLE-VALUE-CALL as a COMBINATION is to ;;; FUNCALL. This is used to implement all the multiple-value ;;; receiving forms. -(defstruct (mv-combination (:include basic-combination) +(def!struct (mv-combination (:include basic-combination) (:constructor make-mv-combination (fun)) (:copier nil))) (defprinter (mv-combination) @@ -1207,7 +1216,7 @@ ;;; The BIND node marks the beginning of a lambda body and represents ;;; the creation and initialization of the variables. -(defstruct (bind (:include node) +(def!struct (bind (:include node) (:copier nil)) ;; the lambda we are binding variables for. Null when we are ;; creating the LAMBDA during IR1 translation. @@ -1219,7 +1228,7 @@ ;;; return values and represents the control transfer on return. This ;;; is also where we stick information used for TAIL-SET type ;;; inference. -(defstruct (creturn (:include node) +(def!struct (creturn (:include node) (:conc-name return-) (:predicate return-p) (:constructor make-return) @@ -1241,7 +1250,7 @@ ;;; The CAST node represents type assertions. The check for ;;; TYPE-TO-CHECK is performed and then the VALUE is declared to be of ;;; type ASSERTED-TYPE. -(defstruct (cast (:include valued-node) +(def!struct (cast (:include valued-node) (:constructor %make-cast)) (asserted-type (missing-arg) :type ctype) (type-to-check (missing-arg) :type ctype) @@ -1251,9 +1260,12 @@ ;; NIL ;; No type check is necessary (VALUE type is a subtype of the TYPE-TO-CHECK.) ;; + ;; :EXTERNAL + ;; Type check will be performed by NODE-DEST. + ;; ;; T ;; A type check is needed. - (%type-check t :type (member t nil)) + (%type-check t :type (member t :external nil)) ;; the lvar which is checked (value (missing-arg) :type lvar)) (defprinter (cast :identity t) @@ -1270,7 +1282,7 @@ ;;; The ENTRY node serves to mark the start of the dynamic extent of a ;;; lexical exit. It is the mess-up node for the corresponding :ENTRY ;;; cleanup. -(defstruct (entry (:include node) +(def!struct (entry (:include node) (:copier nil)) ;; All of the EXIT nodes for potential non-local exits to this point. (exits nil :type list) @@ -1283,9 +1295,10 @@ ;;; if necessary. This is interposed between the uses of the exit ;;; continuation and the exit continuation's DEST. Instead of using ;;; the returned value being delivered directly to the exit -;;; continuation, it is delivered to our VALUE continuation. The -;;; original exit continuation is the exit node's CONT. -(defstruct (exit (:include valued-node) +;;; continuation, it is delivered to our VALUE lvar. The original exit +;;; lvar is the exit node's LVAR; physenv analysis also makes it the +;;; lvar of %NLX-ENTRY call. +(def!struct (exit (:include valued-node) (:copier nil)) ;; the ENTRY node that this is an exit for. If null, this is a ;; degenerate exit. A degenerate exit is used to "fill" an empty @@ -1302,7 +1315,7 @@ ;;;; miscellaneous IR1 structures -(defstruct (undefined-warning +(def!struct (undefined-warning #-no-ansi-print-object (:print-object (lambda (x s) (print-unreadable-object (x s :type t)