| blob | 5ba56f466ec9b0f14d305ad9db49d6c5a0e7505e |
1 ;;;; This file contains code which does the translation of lambda
2 ;;;; forms from Lisp code to the first intermediate representation
3 ;;;; (IR1).
5 ;;;; This software is part of the SBCL system. See the README file for
6 ;;;; more information.
7 ;;;;
8 ;;;; This software is derived from the CMU CL system, which was
9 ;;;; written at Carnegie Mellon University and released into the
10 ;;;; public domain. The software is in the public domain and is
11 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
12 ;;;; files for more information.
16 ;;;; LAMBDA hackery
18 ;;;; FIXME: where is that file?
19 ;;;; Note: Take a look at the compiler-overview.tex section on "Hairy
20 ;;;; function representation" before you seriously mess with this
21 ;;;; stuff.
23 ;;; Verify that the NAME is a legal name for a variable and return a
24 ;;; VAR structure for it, filling in info if it is globally special.
25 ;;; If it is losing, we punt with a COMPILER-ERROR. NAMES-SO-FAR is a
26 ;;; list of names which have previously been bound. If the NAME is in
27 ;;; this list, then we error out.
35 name
36 context))
40 name))
43 local variable.~:@>"
44 name))
47 as a local variable.~:@>"
48 name))
58 ;;; Make the default keyword for a &KEY arg, checking that the keyword
59 ;;; isn't already used by one of the VARS.
64 symbol)))
71 "The keyword ~S appears more than once in the lambda list."
72 key))))
73 key))
75 ;;; Parse a lambda list into a list of VAR structures, stripping off
76 ;;; any &AUX bindings. Each arg name is checked for legality, and
77 ;;; duplicate names are checked for. If an arg is globally special,
78 ;;; the var is marked as :SPECIAL instead of :LEXICAL. &KEY,
79 ;;; &OPTIONAL and &REST args are annotated with an ARG-INFO structure
80 ;;; which contains the extra information. If we hit something losing,
81 ;;; we bug out with COMPILER-ERROR. These values are returned:
82 ;;; 1. a list of the var structures for each top level argument;
83 ;;; 2. a flag indicating whether &KEY was specified;
84 ;;; 3. a flag indicating whether other &KEY args are allowed;
85 ;;; 4. a list of the &AUX variables; and
86 ;;; 5. a list of the &AUX values.
88 make-lambda-vars))
97 ;; for optionals and keywords args.
145 t)))
166 nil))))
183 ;;; This is similar to IR1-CONVERT-PROGN-BODY except that we
184 ;;; sequentially bind each AUX-VAR to the corresponding AUX-VAL before
185 ;;; converting the body. If there are no bindings, just convert the
186 ;;; body, otherwise do one binding and recurse on the rest.
187 ;;;
188 ;;; FIXME: This could and probably should be converted to use
189 ;;; SOURCE-NAME and DEBUG-NAME. But I (WHN) don't use &AUX bindings,
190 ;;; so I'm not motivated. Patches will be accepted...
192 post-binding-lexenv)
204 :post-binding-lexenv post-binding-lexenv
206 '&aux-bindings
207 aux-vars))))
213 ;;; This is similar to IR1-CONVERT-PROGN-BODY except that code to bind
214 ;;; the SPECVAR for each SVAR to the value of the variable is wrapped
215 ;;; around the body. If there are no special bindings, we just convert
216 ;;; the body, otherwise we do one special binding and recurse on the
217 ;;; rest.
218 ;;;
219 ;;; We make a cleanup and introduce it into the lexical
220 ;;; environment. If there are multiple special bindings, the cleanup
221 ;;; for the blocks will end up being the innermost one. We force NEXT
222 ;;; to start a block outside of this cleanup, causing cleanup code to
223 ;;; be emitted when the scope is exited.
231 post-binding-lexenv))
244 body aux-vars aux-vals
246 post-binding-lexenv)))))
249 ;;; Create a lambda node out of some code, returning the result. The
250 ;;; bindings are specified by the list of VAR structures VARS. We deal
251 ;;; with adding the names to the LEXENV-VARS for the conversion. The
252 ;;; result is added to the NEW-FUNCTIONALS in the *CURRENT-COMPONENT*
253 ;;; and linked to the component head and tail.
254 ;;;
255 ;;; We detect special bindings here, replacing the original VAR in the
256 ;;; lambda list with a temporary variable. We then pass a list of the
257 ;;; special vars to IR1-CONVERT-SPECIAL-BINDINGS, which actually emits
258 ;;; the special binding code.
259 ;;;
260 ;;; We ignore any ARG-INFO in the VARS, trusting that someone else is
261 ;;; dealing with &NONSENSE, except for &REST vars with DYNAMIC-EXTENT.
262 ;;;
263 ;;; AUX-VARS is a list of VAR structures for variables that are to be
264 ;;; sequentially bound. Each AUX-VAL is a form that is to be evaluated
265 ;;; to get the initial value for the corresponding AUX-VAR.
267 vars
268 &key
269 aux-vars
270 aux-vals
272 debug-name
274 post-binding-lexenv
275 system-lambda)
278 ;; We're about to try to put new blocks into *CURRENT-COMPONENT*.
283 :bind bind
284 :%source-name source-name
285 :%debug-name debug-name
294 ;; just to check: This function should fail internal assertions if
295 ;; we didn't set up a valid debug name above.
296 ;;
297 ;; (In SBCL we try to make everything have a debug name, since we
298 ;; lack the omniscient perspective the original implementors used
299 ;; to decide which things didn't need one.)
307 ;; As far as I can see, LAMBDA-VAR-HOME should never have
308 ;; been set before. Let's make sure. -- WHN 2001-09-29
321 :lambda lambda
344 result-lvar body
346 post-binding-lexenv)))))
351 lambda))
353 ;;; Entry point CLAMBDAs have a special kind
360 entry)
362 ;;; Create the actual entry-point function for an optional entry
363 ;;; point. The lambda binds copies of each of the VARS, then calls FUN
364 ;;; with the argument VALS and the DEFAULTS. Presumably the VALS refer
365 ;;; to the VARS by name. The VALS are passed in the reverse order.
366 ;;;
367 ;;; If any of the copies of the vars are referenced more than once,
368 ;;; then we mark the corresponding var as EVER-USED to inhibit
369 ;;; "defined but not read" warnings for arguments that are only used
370 ;;; by default forms.
380 fvars))
392 ;; See lengthy comment at top of 'seqtran'
393 ;; as to why muffling is not done during xc.
394 #-sb-xc-host
400 arg-vars
401 ;; FIXME: Would be nice to
402 ;; share these names instead
403 ;; of consing up several
404 ;; identical ones. Oh well.
406 '&optional-processor
407 name)
408 :note-lexical-bindings nil
413 fvars arg-vars)
414 fun))
416 ;;; This function deals with supplied-p vars in optional arguments. If
417 ;;; there is no supplied-p arg, then we just call
418 ;;; IR1-CONVERT-HAIRY-ARGS on the remaining arguments, and generate a
419 ;;; optional entry that calls the result. If there is a supplied-p
420 ;;; var, then we add it into the default vars and throw a T into the
421 ;;; entry values. The resulting entry point function is returned.
423 entry-vars entry-vals
424 vars supplied-p-p body
425 aux-vars aux-vals
426 source-name debug-name
427 force post-binding-lexenv
428 system-lambda)
431 aux-vars aux-vals))
441 res
447 source-name debug-name
448 force post-binding-lexenv system-lambda)
450 res
456 source-name debug-name
457 force post-binding-lexenv system-lambda))))
459 ;; We want to delay converting the entry, but there exist
460 ;; problems: hidden references should not be established to
461 ;; lambdas of kind NIL should not have (otherwise the compiler
462 ;; might let-convert or delete them) and to variables.
465 supplied-p-p ; this entry will be of kind NIL
468 default-vars default-vals
470 name)
473 ;; DEFAULT can contain a reference to a
474 ;; to-be-optimized-away function/block/tag, so better to
475 ;; reduce code now (but we possibly lose syntax checking
476 ;; in an unreachable code).
480 default-vars default-vals
481 defaults
482 name)
483 res)))))))
485 ;;; Create the MORE-ENTRY function for the OPTIONAL-DISPATCH RES.
486 ;;; ENTRY-VARS and ENTRY-VALS describe the fixed arguments. REST is
487 ;;; the var for any &REST arg. KEYS is a list of the &KEY arg vars.
488 ;;;
489 ;;; The most interesting thing that we do is parse keywords. We create
490 ;;; a bunch of temporary variables to hold the result of the parse,
491 ;;; and then loop over the supplied arguments, setting the appropriate
492 ;;; temps for the supplied keyword. Note that it is significant that
493 ;;; we iterate over the keywords in reverse order --- this implements
494 ;;; the CL requirement that (when a keyword appears more than once)
495 ;;; the first value is used.
496 ;;;
497 ;;; If there is no supplied-p var, then we initialize the temp to the
498 ;;; default and just pass the temp into the main entry. Since
499 ;;; non-constant &KEY args are forcibly given a supplied-p var, we
500 ;;; know that the default is constant, and thus safe to evaluate out
501 ;;; of order.
502 ;;;
503 ;;; If there is a supplied-p var, then we create temps for both the
504 ;;; value and the supplied-p, and pass them into the main entry,
505 ;;; letting it worry about defaulting.
506 ;;;
507 ;;; We deal with :ALLOW-OTHER-KEYS by delaying unknown keyword errors
508 ;;; until we have scanned all the keywords.
535 ;; The reason for all the noise with
536 ;; STACK-GROWS-DOWNWARD-NOT-UPWARD is to enable generation of
537 ;; slightly more efficient code on x86oid processors. (We can
538 ;; hoist the negation of the index outside the main parsing loop
539 ;; and take advantage of the base+index+displacement addressing
540 ;; mode on x86oids.)
554 #!+stack-grows-downward-not-upward
556 #!-stack-grows-downward-not-upward n-value-temp
559 #!-stack-grows-downward-not-upward
574 nil
579 t
610 #!-stack-grows-downward-not-upward
620 #!+stack-grows-downward-not-upward
641 :note-lexical-bindings nil
648 ;;; This is called by IR1-CONVERT-HAIRY-ARGS when we run into a &REST
649 ;;; or &KEY arg. The arguments are similar to that function, but we
650 ;;; split off any &REST arg and pass it in separately. REST is the
651 ;;; &REST arg var, or NIL if there is no &REST arg. KEYS is a list of
652 ;;; the &KEY argument vars.
653 ;;;
654 ;;; When there are &KEY arguments, we introduce temporary gensym
655 ;;; variables to hold the values while keyword defaulting is in
656 ;;; progress to get the required sequential binding semantics.
657 ;;;
658 ;;; This gets interesting mainly when there are &KEY arguments with
659 ;;; supplied-p vars or non-constant defaults. In either case, pass in
660 ;;; a supplied-p var. If the default is non-constant, we introduce an
661 ;;; IF in the main entry that tests the supplied-p var and decides
662 ;;; whether to evaluate the default or not. In this case, the real
663 ;;; incoming value is NIL, so we must union NULL with the declared
664 ;;; type when computing the type for the main entry's argument.
666 rest more-context more-count keys supplied-p-p
667 body aux-vars aux-vals source-name debug-name
668 post-binding-lexenv system-lambda)
671 aux-vars aux-vals))
680 ;; Make up two extra variables, and squirrel them away in
681 ;; ARG-INFO-DEFAULT for transforming (VALUES-LIST REST) into
682 ;; (%MORE-ARG-VALUES CONTEXT 0 COUNT) when possible.
694 more-count count))))
706 ;; was: (format nil "~A-DEFAULTING-TEMP" (leaf-source-name key))
725 nil
745 :post-binding-lexenv post-binding-lexenv
746 :source-name source-name
747 :debug-name debug-name
755 name)
761 last-entry)
762 res)
764 last-entry)))
766 ;;; This function generates the entry point functions for the
767 ;;; OPTIONAL-DISPATCH RES. We accomplish this by recursion on the list
768 ;;; of arguments, analyzing the arglist on the way down and generating
769 ;;; entry points on the way up.
770 ;;;
771 ;;; DEFAULT-VARS is a reversed list of all the argument vars processed
772 ;;; so far, including supplied-p vars. DEFAULT-VALS is a list of the
773 ;;; names of the DEFAULT-VARS.
774 ;;;
775 ;;; ENTRY-VARS is a reversed list of processed argument vars,
776 ;;; excluding supplied-p vars. ENTRY-VALS is a list things that can be
777 ;;; evaluated to get the values for all the vars from the ENTRY-VARS.
778 ;;; It has the var name for each required or optional arg, and has T
779 ;;; for each supplied-p arg.
780 ;;;
781 ;;; VARS is a list of the LAMBDA-VAR structures for arguments that
782 ;;; haven't been processed yet. SUPPLIED-P-P is true if a supplied-p
783 ;;; argument has already been processed; only in this case are the
784 ;;; DEFAULT-XXX and ENTRY-XXX different.
785 ;;;
786 ;;; The result at each point is a lambda which should be called by the
787 ;;; above level to default the remaining arguments and evaluate the
788 ;;; body. We cause the body to be evaluated by converting it and
789 ;;; returning it as the result when the recursion bottoms out.
790 ;;;
791 ;;; Each level in the recursion also adds its entry point function to
792 ;;; the result OPTIONAL-DISPATCH. For most arguments, the defaulting
793 ;;; function and the entry point function will be the same, but when
794 ;;; SUPPLIED-P args are present they may be different.
795 ;;;
796 ;;; When we run into a &REST or &KEY arg, we punt out to
797 ;;; IR1-CONVERT-MORE, which finishes for us in this case.
799 entry-vars entry-vals
800 vars supplied-p-p body aux-vars
801 aux-vals
802 source-name debug-name
803 force post-binding-lexenv
804 system-lambda)
807 aux-vars aux-vals))
811 ;; Handle &KEY with no keys...
813 entry-vars entry-vals
814 nil nil nil vars supplied-p-p body aux-vars
815 aux-vals source-name debug-name
816 post-binding-lexenv system-lambda)
820 :aux-vars aux-vars
821 :aux-vals aux-vals
822 :post-binding-lexenv post-binding-lexenv
823 :source-name source-name
824 :debug-name debug-name
832 name)
833 res)
834 fun)
836 fun)))
843 source-name debug-name
844 nil post-binding-lexenv system-lambda)))
850 (:optional
852 res default-vars default-vals
853 entry-vars entry-vals vars supplied-p-p body
854 aux-vars aux-vals
855 source-name debug-name
856 force post-binding-lexenv
857 system-lambda)))
858 ;; See GENERATE-OPTIONAL-DEFAULT-ENTRY.
863 ep entry-vars entry-vals nil
865 ep)
866 res)
868 ep))
870 ep))
871 (:rest
873 entry-vars entry-vals
875 aux-vars aux-vals
876 source-name debug-name
877 post-binding-lexenv system-lambda))
878 (:more-context
880 entry-vars entry-vals
882 body aux-vars aux-vals
883 source-name debug-name
884 post-binding-lexenv system-lambda))
885 (:keyword
887 entry-vars entry-vals
888 nil nil nil vars supplied-p-p body aux-vars
889 aux-vals source-name debug-name
890 post-binding-lexenv system-lambda)))))))
892 ;;; This function deals with the case where we have to make an
893 ;;; OPTIONAL-DISPATCH to represent a LAMBDA. We cons up the result and
894 ;;; call IR1-CONVERT-HAIRY-ARGS to do the work. When it is done, we
895 ;;; figure out the MIN-ARGS and MAX-ARGS.
897 &key post-binding-lexenv
899 debug-name system-lambda)
903 :allowp allowp
904 :keyp keyp
905 :%source-name source-name
906 :%debug-name debug-name
913 source-name debug-name nil post-binding-lexenv
914 system-lambda)
915 ;; ir1-convert-hairy-args can throw 'locall-already-let-converted
916 ;; push optional-dispatch into the current component only after it
917 ;; normally returned
923 res))
925 ;;; Convert a LAMBDA form into a LAMBDA leaf or an OPTIONAL-DISPATCH leaf.
927 debug-name maybe-add-debug-catch
928 system-lambda)
932 form))
935 'lambda
937 form))
940 "The lambda expression has a missing or non-list lambda list:~% ~S"
941 form))
958 forms))
960 forms
965 allow-other-keys
966 aux-vars aux-vals
967 :post-binding-lexenv post-binding-lexenv
968 :source-name source-name
969 :debug-name debug-name
973 :aux-vars aux-vars
974 :aux-vals aux-vals
975 :post-binding-lexenv post-binding-lexenv
976 :source-name source-name
977 :debug-name debug-name
983 lambda-list))
986 ;; KLUDGE: Not counting TL-XEPs is a lie, of course, but
987 ;; keeps things less confusing to users of TIME, where this
988 ;; count gets used.
991 res))))
994 #!+unwind-to-frame-and-call-vop
998 ;; Just ensure that there won't be any tail-calls, IR2 magic will
999 ;; handle the rest.
1001 #!-unwind-to-frame-and-call-vop
1004 return-value-tag
1005 ;; If DEBUG-CATCH-TAG is thrown (with a thunk as the value) the
1006 ;; RETURN-FROM is elided and we funcall the thunk instead. That
1007 ;; thunk might either return a value (for a RETURN-FROM-FRAME)
1008 ;; or call this same function again (for a RESTART-FRAME).
1009 ;; -- JES, 2007-01-09
1012 ;; Use a constant catch tag instead of consing a new one for every
1013 ;; entry to this block. The uniquencess of the catch tags is
1014 ;; ensured when the tag is throw by the debugger. It'll allocate a
1015 ;; new tag, and modify the reference this tag in the proper
1016 ;; catch-block structure to refer to that new tag. This
1017 ;; significantly decreases the runtime cost of high debug levels.
1018 ;; -- JES, 2007-01-09
1024 ;;; helper for LAMBDA-like things, to massage them into a form
1025 ;;; suitable for IR1-CONVERT-LAMBDA.
1027 &key
1029 debug-name)
1035 :maybe-add-debug-catch t
1036 :source-name source-name
1044 :maybe-add-debug-catch t
1051 ;; Don't treat recursive stubs like CAR as self-calls
1052 ;; Maybe just use the fact that it is a known function?
1053 ;; Though a known function may be used
1054 ;; because of some other attributues but
1055 ;; still wants to get optimized self calls
1065 res defined-fun-res))
1066 res)
1068 :maybe-add-debug-catch t
1069 :debug-name
1073 :source-name source-name
1075 \f
1076 ;;; Convert the forms produced by RECONSTRUCT-LEXENV to LEXENV
1081 lexenv
1084 (:declare
1087 (:macro
1094 (:symbol-macro
1102 ;;; Convert FUN as a lambda in the null environment, but use the
1103 ;;; current compilation policy. Note that FUN may be a
1104 ;;; LAMBDA-WITH-LEXENV, so we may have to augment the environment to
1105 ;;; reflect the state at the definition site.
1107 &key
1109 debug-name
1110 system-lambda)
1116 fun))
1121 ;; Inherit MUFFLE-CONDITIONS from the call-site lexenv
1122 ;; rather than the definition-site lexenv, since it seems
1123 ;; like a much more common case.
1127 :source-name source-name
1128 :debug-name debug-name
1131 clambda))
1132 ;;;; defining global functions
1133 ;;; Given a lambda-list, return a FUN-TYPE object representing the signature:
1134 ;;; return type is *, and each individual arguments type is T -- but we get
1135 ;;; the argument counts and keywords.
1142 ;; When it comes to building a type, &REST means pretty much the
1143 ;; same thing as &MORE.
1148 key-list))))
1152 ;;; Get a DEFINED-FUN object for a function we are about to define. If
1153 ;;; the function has been forward referenced, then substitute for the
1154 ;;; previous references.
1164 :%source-name name
1166 :declared
1175 ;; If *FREE-FUNS* has a previously converted definition
1176 ;; for this name, then blow it away and try again.
1182 ;;; Check a new global function definition for consistency with
1183 ;;; previous declaration or definition, and assert argument/result
1184 ;;; types if appropriate. This assertion is suppressed by the
1185 ;;; EXPLICIT-CHECK attribute, which is specified on functions that
1186 ;;; check their argument types as a consequence of type dispatching.
1187 ;;; This avoids redundant checks such as NUMBERP on the args to +, etc.
1193 fun type
1194 ;; KLUDGE: Common Lisp is such a dynamic language that in general
1195 ;; all we can do here is issue a STYLE-WARNING. It would be nice
1196 ;; to issue a full WARNING in the special case of type mismatches
1197 ;; within a compilation unit (as in section 3.2.2.3 of the spec)
1198 ;; but at least as of sbcl-0.6.11, we don't keep track of whether
1199 ;; the mismatched data came from the same compilation unit, so we
1200 ;; can't do that. -- WHN 2001-02-11
1205 :really-assert
1209 explicit-check))))
1211 "previous declaration"
1214 ;;; Used for global inline expansion. Earlier something like this was
1215 ;;; used by %DEFUN too. FIXME: And now it's probably worth rethinking
1216 ;;; whether this function is a good idea at all.
1218 ;; Unless a :INLINE function, we temporarily clobber the inline
1219 ;; expansion. This prevents recursive inline expansion of
1220 ;; opportunistic pseudo-inlines.
1224 :source-name name
1225 ;; prevent instrumentation of
1226 ;; known function expansions
1231 ;; Associate VAR with the FUN -- and in case of an optional dispatch
1232 ;; with the various entry-points. This allows XREF to know where the
1233 ;; inline CLAMBDA comes from.
1239 ;; Delayed entry-point.
1246 g)))))))))
1252 ;; substitute for any old references
1259 fun))
1264 inline-lambda)
1267 inline-lambda)))
1271 ;;; the even-at-compile-time part of DEFUN
1272 ;;;
1273 ;;; The INLINE-LAMBDA is a LAMBDA-WITH-LEXENV, or NIL if there is no
1274 ;;; inline expansion.
1293 ;; old CMU CL comment:
1294 ;; If there is a type from a previous definition, blast it,
1295 ;; since it is obsolete.
1298 ;; FIXME: If this is a block compilation thing, shouldn't
1299 ;; we be setting the type to the full derived type for the
1300 ;; definition, instead of this most general function type?
1305 ;; Similar to above, detect duplicate definitions within a file,
1306 ;; but the package lock check is unnecessary - it's handled elsewhere.
1307 ;;
1308 ;; Additionally, this is a STYLE-WARNING, not a WARNING, because there is
1309 ;; meaningful behavior that can be ascribed to some redefinitions, e.g.
1310 ;; (defmacro foo () first-definition)
1311 ;; (defun f () (use-it (foo )))
1312 ;; (defmacro foo () other-definition)
1313 ;; will use the first definition when compiling F, but make the second available
1314 ;; in the loaded fasl. In this usage it would have made sense to wrap the
1315 ;; respective definitions with EVAL-WHEN for different situations,
1316 ;; but as long as the compile-time behavior is deterministic, it's just bad style
1317 ;; and not flat-out wrong, though there is indeed some waste in the fasl.
1318 ;;
1319 ;; KIND is the globaldb KIND of this NAME
1329 \f
1330 ;;; Entry point utilities
1332 ;;; Return a function for the Nth entry point.