| blob | 78f3819f4971c2194fcd27a0e544ff89570d7878 |
1 ;;;; optimizers for list and sequence functions
3 ;;;; This software is part of the SBCL system. See the README file for
4 ;;;; more information.
5 ;;;;
6 ;;;; This software is derived from the CMU CL system, which was
7 ;;;; written at Carnegie Mellon University and released into the
8 ;;;; public domain. The software is in the public domain and is
9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
10 ;;;; files for more information.
14 ;;; Regarding several reader-conditionalized MUFFLE-CONDITION declarations
15 ;;; throughout this file, here's why: Transforms produce sexprs that as far
16 ;;; as the compiler is concerned could have been user-supplied.
17 ;;; In as much as the forms mention a type-name, that name had best be
18 ;;; recognized, or else it's a style-warning (or worse).
19 ;;; And in cross-compilation, COMPILER-NOTE isn't known early enough for
20 ;;; the transforms in this file to refer to a known type.
21 ;;; But mysteriously the xc would report a style-warning about COMPILER-NOTE
22 ;;; - or any descendant - being unknown, and then go on with life.
23 ;;; How was this possible? Well, it's only trying to _parse_ the type
24 ;;; on account of the declarations saying to muffle things of that type.
25 ;;; Indeed the declaration merits a warning.
26 ;;; But this is an extremely sad and confusing state of affairs,
27 ;;; because while we expect some CODE-DELETION-NOTEs, we don't expect to see
28 ;;; that CODE-DELETION-NOTE is an undefined type.
29 ;;; Alternatively, we could invent DEFINE!-CONDITION which would cause
30 ;;; the cross-compiler to be born knowing all the required types.
31 ;;; Moreover, it would be nice if some of the declarations were commented
32 ;;; with their reason for existence.
34 \f
35 ;;;; mapping onto lists: the MAPFOO functions
37 ;; This expander allows a compiler-macro for FN to take effect by eliding
38 ;; a LET binding of it. Attempting to self-optimize like that isn't the usual
39 ;; SBCL way, however this is a countermeasure to an inhibition of a later
40 ;; optimization, and it is not an onerous change to the expander.
41 ;; We've gone to the trouble of inlining MAPfoo, but the inlined code
42 ;; prevented use of a compiler-macro because %FUNCALL (as opposed to FUNCALL)
43 ;; is not recognized. "Fixing" the compiler to understand %FUNCALL being
44 ;; the same isn't enough: the funarg must be a literal form because we can't
45 ;; know that a variable arg is a never-modified binding of 'F or #'F
46 ;; until IR1 has figured that out, at which point it is too late.
47 ;; [However, see lp# 632368 which asks for something like that.]
48 ;;
49 ;; Also, you might think there to be a subtle difference in behavior from
50 ;; delaying the reference to #'F versus referencing it once. But there is no
51 ;; difference - either way will use the #<fdefn> of F in the call.
52 ;; Of course, it would be ridiculously unportable to to rely on the
53 ;; fact that F can be changed (for its next call) while funcalling it.
54 ;;
61 arglists
72 (:nconc
76 ;; MUFFLE- is not injected when cross-compiling.
77 ;; See top of file for explanation.
79 #-sb-xc-host
86 (:list
90 ;; MUFFLE- is not injected when cross-compiling.
91 ;; See top of file for explanation.
93 #-sb-xc-host
98 (,endtest
101 ;; Accumulate using %RPLACD. RPLACD becomes (SETF CDR)
102 ;; which becomes %RPLACD but relies on "defsetfs".
103 ;; This is for effect, not value, so makes no difference.
105 ;; 0 is not written to the heap
130 \f
131 ;;;; mapping onto sequences: the MAP function
133 ;;; MAP is %MAP plus a check to make sure that any length specified in
134 ;;; the result type matches the actual result. We also wrap it in a
135 ;;; TRULY-THE for the most specific type we can determine.
140 ;; what we know about the type of the result. (Note that the
141 ;; "result type" argument is not necessarily the type of the
142 ;; result, since NIL means the result has NULL type.)
144 'consed-sequence
148 'null
149 result-type-arg-value)))))
153 ;; ANSI requires the length-related type check only
154 ;; when the SAFETY quality is 3... in other cases, we
155 ;; skip it, because it could be expensive.
156 bare)
159 result-type-arg))
162 result-type)))
169 bare
172 ;; FIXME: this is wrong, as not all subtypes of
173 ;; VECTOR are ARRAY-TYPEs [consider, for
174 ;; example, (OR (VECTOR T 3) (VECTOR T
175 ;; 4))]. However, it's difficult to see what we
176 ;; should put here... maybe we should
177 ;; GIVE-UP-IR1-TRANSFORM if the type is a
178 ;; subtype of VECTOR but not an ARRAY-TYPE?
179 bare))))))))
181 ;;; Return a DO loop, mapping a function FUN to elements of
182 ;;; sequences. SEQS is a list of lvars, SEQ-NAMES - list of variables,
183 ;;; bound to sequences, INTO - a variable, which is used in
184 ;;; MAP-INTO. RESULT and BODY are forms, which can use variables
185 ;;; FUNCALL-RESULT, containing the result of application of FUN, and
186 ;;; INDEX, containing the current position in sequences.
204 for seq-name in seq-names
245 :from-end t
247 body)))))
249 ;;; Try to compile %MAP efficiently when we can determine sequence
250 ;;; argument types at compile time.
253 "open code"
260 subtype-p
273 ;; The consing arity-1 cases can be implemented
274 ;; reasonably efficiently as function calls, and the cost
275 ;; of consing should be significantly larger than
276 ;; function call overhead, so we always compile these
277 ;; cases as full calls regardless of speed-versus-space
278 ;; optimization policy.
280 ;; (We use the same idiom, of returning a LAMBDA from
281 ;; DEFTRANSFORM, as is used in the DEFTRANSFORMs for
282 ;; FUNCALL and ALIEN-FUNCALL, and for the same
283 ;; reason: we need to get the runtime values of each
284 ;; of the &REST vars.)
309 all-seqs seq-args
310 :result result
311 :body push-dacc
317 ;;; MAP-INTO
321 "open code"
338 seqs seqs-names
344 funcall-result))
347 seqs seqs-names
353 result))
355 ;; %%vector-map-into-funs%% is not defined in xc
356 ;; if something needs to be faster in the compiler, it
357 ;; should declare the input sequences instead.
368 result))))
372 \f
373 ;;; FIXME: once the confusion over doing transforms with known-complex
374 ;;; arrays is over, we should also transform the calls to (AND (ARRAY
375 ;;; * (*)) (NOT (SIMPLE-ARRAY * (*)))) objects.
401 ;;; True if EQL comparisons involving type can be simplified to EQ.
407 ;; Write "%NAME-FUN1-FUN2-FUN3", etc. Not only is
408 ;; this ever so slightly faster then FORMAT, this
409 ;; way we are also proof against *PRINT-CASE*
410 ;; frobbing and such.
421 function-name key-functions variant)))
428 ;; If TEST is EQL, drop it.
431 ;; Ditto for KEY IDENTITY.
434 ;; Key can legally be NIL, but if it's NIL for sure we pretend it's
435 ;; not there at all. If it might be NIL, make up a form to that
436 ;; ensures it is a function.
480 key-form
490 ;; constant nil list
493 nil))
495 ;; specialized out-of-line version
500 ;; If KEY is IDENTITY, drop it.
503 ;; Key can legally be NIL, but if it's NIL for sure we pretend it's
504 ;; not there at all. If it might be NIL, make up a form to that
505 ;; ensures it is a function.
537 tail))
547 ;; constant nil list -- nothing to find!
548 nil)
550 ;; specialized out-of-line version
582 ',tail
584 nil)))
587 ;;; A similar transform used to apply to MEMBER and ASSOC, but since
588 ;;; TRANSFORM-LIST-ITEM-SEEK now takes care of them those transform
589 ;;; would never fire, and (%MEMBER-TEST ITEM LIST #'EQ) should be
590 ;;; almost as fast as MEMQ.
592 "convert to EQ test"
601 "open code"
617 *
634 "Unknown fill basher, please report to sbcl-devel: ~A"
635 basher-name)))
647 ;; BASH-VALUE is a word that we can repeatedly smash
648 ;; on the array: for less-than-word sized elements it
649 ;; contains multiple copies of the fill item.
658 (:tagged
660 (:char
662 (:bits
663 tmp)
664 (:single-float
667 (:double-float
671 (:complex-single-float
680 res))
685 (:tagged
687 (:char
689 (:bits
691 (:single-float
694 (:double-float
698 (:complex-single-float
710 res)))))
712 ;; KLUDGE: WITH-ARRAY data in its full glory is going to mess up
713 ;; dynamic-extent for MAKE-ARRAY :INITIAL-ELEMENT initialization.
718 ;; Minor abuse CHECK-BOUND for bounds checking.
719 ;; (- END START) may still end up negative, but
720 ;; the basher handle that.
724 start)))
733 seq))
743 ;; WITH-ARRAY-DATA did our range checks once and for all, so
744 ;; it'd be wasteful to check again on every AREF...
750 ;; ... though we still need to check that the new element can fit
751 ;; into the vector in safe code. -- CSR, 2002-07-05
761 :start start
763 \f
764 ;;;; hairy sequence transforms
766 ;;; FIXME: no hairy sequence transforms in SBCL?
767 ;;;
768 ;;; There used to be a bunch of commented out code about here,
769 ;;; containing the (apparent) beginning of hairy sequence transform
770 ;;; infrastructure. People interested in implementing better sequence
771 ;;; transforms might want to look at it for inspiration, even though
772 ;;; the actual code is ancient CMUCL -- and hence bitrotted. The code
773 ;;; was deleted in 1.0.7.23.
774 \f
775 ;;;; string operations
777 ;;; We transform the case-sensitive string predicates into a non-keyword
778 ;;; version. This is an IR1 transform so that we don't have to worry about
779 ;;; changing the order of evaluation.
783 * *)
792 ;;; Return a form that tests the free variables STRING1 and STRING2
793 ;;; for the ordering relationship specified by LESSP and EQUALP. The
794 ;;; start and end are also gotten from the environment. Both strings
795 ;;; must be SIMPLE-BASE-STRINGs.
802 string1 start1 end1 string2 start2 end2)))
812 (+ index
815 start1))))))
816 index)
860 `(,',result-fun
869 ;; An IF node doesn't care about the mismatch index.
870 ;; Transforming to (not (string= ..)) would lead to internal confusion
871 ;; due to incorrect typing: STRING/= can't return T, so return 0 for true.
877 \f
878 ;;;; transforms for sequence functions
880 ;;; Moved here from generic/vm-tran.lisp to satisfy clisp. Only applies
881 ;;; to vectors based on simple arrays.
885 ;;; FIXME: In the copy loops below, we code the loops in a strange
886 ;;; fashion:
887 ;;;
888 ;;; (do ((i (+ src-offset length) (1- i)))
889 ;;; ((<= i 0) ...)
890 ;;; (... (aref foo (1- i)) ...))
891 ;;;
892 ;;; rather than the more natural (and seemingly more efficient):
893 ;;;
894 ;;; (do ((i (1- (+ src-offset length)) (1- i)))
895 ;;; ((< i 0) ...)
896 ;;; (... (aref foo i) ...))
897 ;;;
898 ;;; (more efficient because we don't have to do the index adjusting on
899 ;;; every iteration of the loop)
900 ;;;
901 ;;; We do this to avoid a suboptimality in SBCL's backend. In the
902 ;;; latter case, the backend thinks I is a FIXNUM (which it is), but
903 ;;; when used as an array index, the backend thinks I is a
904 ;;; POSITIVE-FIXNUM (which it is). However, since the backend thinks of
905 ;;; these as distinct storage classes, it cannot coerce a move from a
906 ;;; FIXNUM TN to a POSITIVE-FIXNUM TN. The practical effect of this
907 ;;; deficiency is that we have two extra moves and increased register
908 ;;; pressure, which can lead to some spectacularly bad register
909 ;;; allocation. (sub-FIXME: the register allocation even with the
910 ;;; strangely written loops is not always excellent, either...). Doing
911 ;;; it the first way, above, means that I is always thought of as a
912 ;;; POSITIVE-FIXNUM and there are no issues.
913 ;;;
914 ;;; Besides, the *-WITH-OFFSET machinery will fold those index
915 ;;; adjustments in the first version into the array addressing at no
916 ;;; performance penalty!
918 ;;; This transform is critical to the performance of string streams. If
919 ;;; you tweak it, make sure that you compare the disassembly, if not the
920 ;;; performance of, the functions implementing string streams
921 ;;; (e.g. SB!IMPL::STRING-OUCH).
926 ,sequence-type1
943 n-element-bits)
946 seq1 start1 replace-len)))
949 ;; If the sequence types are different, SEQ1 and
950 ;; SEQ2 must be distinct arrays.
966 seq1))))
974 into forms
979 #!+sb-unicode
984 ;;; Expand simple cases of UB<SIZE>-BASH-COPY inline. "simple" is
985 ;;; defined as those cases where we are doing word-aligned copies from
986 ;;; both the source and the destination and we are copying from the same
987 ;;; offset from both the source and the destination. (The last
988 ;;; condition is there so we can determine the direction to copy at
989 ;;; compile time rather than runtime. Remember that UB<SIZE>-BASH-COPY
990 ;;; acts like memmove, not memcpy.) These conditions may seem rather
991 ;;; restrictive, but they do catch common cases, like allocating a (* 2
992 ;;; N)-size buffer and blitting in the old N-size buffer in.
995 dst dst-offset
996 length n-elems-per-word)
1003 ;; Avoid non-word aligned copies.
1006 ;; Avoid copies where we would have to insert code for
1007 ;; determining the direction of copying.
1010 ;; FIXME: The cross-compiler doesn't optimize TRUNCATE properly,
1011 ;; so we have to do its work here.
1013 'length
1016 ;; Handle any bits at the end.
1019 ;; FIXME: The shift amount on this ASH is
1020 ;; *always* negative, but the backend doesn't
1021 ;; have a NEGATIVE-FIXNUM primitive type, so we
1022 ;; wind up with a pile of code that tests the
1023 ;; sign of the shift count prior to shifting when
1024 ;; all we need is a simple negate and shift
1025 ;; right. Yuck.
1043 ;; Copy from the end to save a register.
1050 #.
1054 index)
1055 *)))
1060 dst dst-offset length
1065 ;;; We expand copy loops inline in SUBSEQ and COPY-SEQ if we're copying
1066 ;;; arrays with elements of size >= the word size. We do this because
1067 ;;; we know the arrays cannot alias (one was just consed), therefore we
1068 ;;; can determine at compile time the direction to copy, and for
1069 ;;; word-sized elements, UB<WORD-SIZE>-BASH-COPY will do a bit of
1070 ;;; needless checking to figure out what's going on. The same
1071 ;;; considerations apply if we are copying elements larger than the word
1072 ;;; size, with the additional twist that doing it inline is likely to
1073 ;;; cons far less than calling REPLACE and letting generic code do the
1074 ;;; work.
1075 ;;;
1076 ;;; However, we do not do this for elements whose size is < than the
1077 ;;; word size because we don't want to deal with any alignment issues
1078 ;;; inline. The UB*-BASH-COPY transforms might fix things up later
1079 ;;; anyway.
1083 ;; The two transforms that use this test already specify that their
1084 ;; sequence argument is a VECTOR,
1085 ;; so this seems like it would be more efficient as
1086 ;; and (not (array-type-complexp type))
1087 ;; (not (eq (array-type-element-type type) *wild-type*))
1088 ;; Anyway it no longer works to write this as a single specifier
1089 ;; '(or (simple-unboxed-array (*)) simple-vector) because that
1090 ;; type is just (simple-array * (*)) which isn't amenable to
1091 ;; inline copying since we don't know what it holds.
1096 element-type)
1110 ;; KLUDGE: The compiler is not able to derive that (+ offset
1111 ;; length) must be a fixnum, but arrives at (unsigned-byte 29).
1112 ;; We, however, know it must be so, as by this point the bounds
1113 ;; have already been checked.
1121 ;;; MAKE-SEQUENCE, SUBSEQ, COPY-SEQ
1140 ;; Require sameness of dim and complexp. Give up on
1141 ;; (OR (VECTOR CHARACTER) (VECTOR BASE-CHAR 2))
1142 ;; which eventually fails in the call to the function.
1146 dim)
1153 types))
1154 dim complexp))))))
1160 ;; VECTOR means (VECTOR T)
1162 t
1166 ;; Don't transform if size is present in the specifier
1167 ;; and the SIZE argument is not known to be equal.
1170 ;; not sure what it would mean to make it non-simple
1175 ;; no transform, but we can detect some style issues
1184 ;; As with MAKE-ARRAY, this is merely undefined
1185 ;; behavior, not an error.
1187 "The default initial element ~S is not a ~S."
1188 default-initial-element elt-type))))
1189 ;; In would be possible in some cases,
1190 ;; like :INITIAL-ELEMENT (IF X #\x #\y) in a call
1191 ;; to MAKE-SEQUENCE '(VECTOR (MEMBER #\A #\B))
1192 ;; to detect erroneous non-constants initializers,
1193 ;; but it is not important enough to bother with.
1196 elt-ctype)))
1197 ;; MAKE-ARRAY considers this a warning, not an error.
1199 :initial-element
1201 elt-type)))))
1206 *
1225 result))))
1244 result)))
1254 ;;; FIXME: it really should be possible to take advantage of the
1255 ;;; macros used in code/seq.lisp here to avoid duplication of code,
1256 ;;; and enable even funkier transformations.
1260 from-end)
1262 *
1263 :node node
1265 "open code"
1301 end2
1302 start2)))
1309 nil)
1310 ;; INDEX2 is FIXNUM, not an INDEX, as right before the loop
1311 ;; terminates is hits -1 when :FROM-END is true and :START2
1312 ;; is 0.
1330 elt)))
1337 elt)))
1343 ;;; Open-code CONCATENATE for strings. It would be possible to extend
1344 ;;; this transform to non-strings, but I chose to just do the case that
1345 ;;; should cover 95% of CONCATENATE performance complaints for now.
1346 ;;; -- JES, 2007-11-17
1347 ;;;
1348 ;;; Only handle the simple result type cases. If somebody does (CONCATENATE
1349 ;;; '(STRING 6) ...) their code won't be optimized, but nobody does that in
1350 ;;; practice.
1351 ;;;
1352 ;;; Limit full open coding based on length of constant sequences. Default
1353 ;;; value is chosen so that other parts of the compiler (constraint propagation
1354 ;;; mainly) won't go nonlinear too badly. It's not an exact number -- but
1355 ;;; in the right ballpark.
1361 ;; Out-of-line
1363 ;; Strings are handled more efficiently by
1364 ;; %concatenate-to-* functions
1366 for lvar in lvars
1370 var))))
1379 ;; Inline
1388 for var in vars
1392 sequence)
1393 ,var
1394 #-sb-xc-host
1413 for value in lvar-values
1414 for var in vars
1415 collect
1418 ;; Fold the array reads for constant arguments
1421 for i from 0
1422 collect
1423 ;; Without truly-the we get massive numbers
1424 ;; of pointless error traps.
1435 (#!+sb-unicode
1438 t)
1439 ,var
1447 .string.))))))
1450 ;; FIXME: This only accepts vectors without dimensions even though
1451 ;; it's not that hard to support them for the concatenate transform,
1452 ;; but it's probably not used often enough to bother.
1458 el-ctype))
1466 #!+sb-unicode
1468 #!-sb-unicode
1478 ;; Lists are faster to iterate over than vectors of
1479 ;; unknown type.
1481 for lvar in lvars
1484 var))))
1496 #!+sb-unicode
1499 ;; FIXME: other vectors may use inlined expansion from
1500 ;; STRING-CONCATENATE-TRANSFORM as well.
1507 `(%concatenate-to-simple-vector
1509 `(%concatenate-to-vector
1511 \f
1512 ;;;; CONS accessor DERIVE-TYPE optimizers
1515 ;; This and CDR needs to use LVAR-CONSERVATIVE-TYPE because type inference
1516 ;; gets confused by things like (SETF CAR).
1520 null-type)
1528 null-type)
1531 \f
1532 ;;;; FIND, POSITION, and their -IF and -IF-NOT variants
1534 ;;; We want to make sure that %FIND-POSITION is inline-expanded into
1535 ;;; %FIND-POSITION-IF only when %FIND-POSITION-IF has an inline
1536 ;;; expansion, so we factor out the condition into this function.
1540 ;; It's not worth trying to inline vector code unless we
1541 ;; know a fair amount about it at compile time.
1547 ;; Inlining on lists is generally worthwhile.
1548 )
1553 ;;; %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for LIST data
1556 ;; Circularity detection slows things down. It is permissible not to.
1557 ;; In fact, FIND is given as an archetypal example of a function that
1558 ;; "should be prepared to signal an error" but might not [CLHS 1.4.2].
1559 ;; We relax the definition of "safe" from safety=3 to >=2.
1561 ;; The secondary value is inconsequential when flowing into a non-MV
1562 ;; combination, so we avoid counting loop iterations if possible.
1563 ;; This is limited in power, but good enough, for want of a proper
1564 ;; dead-code-elimination phase of the compiler.
1593 ;; If you have as many as INDEX conses on a 32-bit build,
1594 ;; then you've either used up 4GB of memory (impossible)
1595 ;; or you're stuck in a circular list in unsafe code.
1596 ;; Correspondingly larger limit for 64-bit.
1600 ;; This hack of dealing with non-NIL FROM-END for list data
1601 ;; by iterating forward through the list and keeping track of
1602 ;; the last time we found a match might be more screwy than
1603 ;; what the user expects, but it seems to be allowed by the
1604 ;; ANSI standard. (And if the user is screwy enough to ask
1605 ;; for FROM-END behavior on list data, turnabout is fair play.)
1606 ;;
1607 ;; It's also not enormously efficient, calling PREDICATE
1608 ;; and KEY more often than necessary; but all the alternatives
1609 ;; seem to have their own efficiency problems.
1618 *
1619 :node node
1621 "expand inline"
1623 from-end start end node))))
1627 ;;; %FIND-POSITION for LIST data can be expanded into %FIND-POSITION-IF
1628 ;;; without loss of efficiency. (I.e., the optimizer should be able
1629 ;;; to straighten everything out.)
1632 *
1634 "expand inline"
1636 ;; The order of arguments for asymmetric tests
1637 ;; (e.g. #'<, as opposed to order-independent
1638 ;; tests like #'=) is specified in the spec
1639 ;; section 17.2.1 -- the O/Zi stuff there.
1642 sequence
1643 from-end
1644 start
1645 end
1648 ;;; The inline expansions for the VECTOR case are saved as macros so
1649 ;;; that we can share them between the DEFTRANSFORMs and the default
1650 ;;; cases in the DEFUNs. (This isn't needed for the LIST case, because
1651 ;;; the DEFTRANSFORMs for LIST are less choosy about when to expand.)
1653 from-end
1654 start
1655 end-arg
1656 element
1657 done-p-expr)
1666 ;; WITH-ARRAY-DATA has already performed bounds
1667 ;; checking, so we can safely elide the checks
1668 ;; in the inner loop.
1677 ;; (If we aren't fastidious about declaring that
1678 ;; INDEX might be -1, then (FIND 1 #() :FROM-END T)
1679 ;; can send us off into never-never land, since
1680 ;; INDEX is initialized to -1.)
1681 of-type index-or-minus-1
1689 from-end start end key test)
1691 (%find-position-or-find-position-if-vector-expansion
1692 sequence
1693 from-end
1694 start
1695 end
1696 element
1697 ;; (See the LIST transform for a discussion of the correct
1698 ;; argument order, i.e. whether the searched-for ,ITEM goes before
1699 ;; or after the checked sequence element.)
1703 from-end start end key)
1705 (%find-position-or-find-position-if-vector-expansion
1706 sequence
1707 from-end
1708 start
1709 end
1710 element
1714 from-end start end key)
1716 (%find-position-or-find-position-if-vector-expansion
1717 sequence
1718 from-end
1719 start
1720 end
1721 element
1724 ;;; %FIND-POSITION, %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for
1725 ;;; VECTOR data
1728 *
1730 "expand inline"
1732 '(%find-position-if-vector-macro predicate sequence
1733 from-end start end key))
1737 *
1739 "expand inline"
1741 '(%find-position-if-not-vector-macro predicate sequence
1742 from-end start end key))
1746 *
1748 "expand inline"
1750 '(%find-position-vector-macro item sequence
1751 from-end start end key test))
1780 *
1787 sequence
1790 form
1791 ;; Otherwise we'd get three instances of WITH-ARRAY-DATA from
1792 ;; %FIND-POSITION.
1799 ;; The type is known exactly, other transforms will take care of it.
1802 ;;; logic to unravel :TEST, :TEST-NOT, and :KEY options in FIND,
1803 ;;; POSITION-IF, etc.
1811 (,test-not
1812 ;; (Without DYNAMIC-EXTENT, this is potentially horribly
1813 ;; inefficient, but since the TEST-NOT option is deprecated
1814 ;; anyway, we don't care.)
1826 key test test-not)
1829 (%find-position item sequence
1830 from-end start
1831 end
1834 test test-not))))))
1841 end key)
1844 ,values-index
1846 sequence from-end
1847 start end
1852 ;;; the deprecated functions FIND-IF-NOT and POSITION-IF-NOT. We
1853 ;;; didn't bother to worry about optimizing them, except note that on
1854 ;;; Sat, Oct 06, 2001 at 04:22:38PM +0100, Christophe Rhodes wrote on
1855 ;;; sbcl-devel
1856 ;;;
1857 ;;; My understanding is that while the :test-not argument is
1858 ;;; deprecated in favour of :test (complement #'foo) because of
1859 ;;; semantic difficulties (what happens if both :test and :test-not
1860 ;;; are supplied, etc) the -if-not variants, while officially
1861 ;;; deprecated, would be undeprecated were X3J13 actually to produce
1862 ;;; a revised standard, as there are perfectly legitimate idiomatic
1863 ;;; reasons for allowing the -if-not versions equal status,
1864 ;;; particularly remove-if-not (== filter).
1865 ;;;
1866 ;;; This is only an informal understanding, I grant you, but
1867 ;;; perhaps it's worth optimizing the -if-not versions in the same
1868 ;;; way as the others?
1869 ;;;
1870 ;;; FIXME: Maybe remove uses of these deprecated functions within the
1871 ;;; implementation of SBCL.
1875 end key)
1878 ,values-index
1880 sequence from-end
1881 start end
1891 ;; If the bag is constant, use MEMBER
1892 ;; instead of FIND, since we have a
1893 ;; deftransform for MEMBER that can
1894 ;; open-code all of the comparisons when
1895 ;; the list is constant. -- JES, 2007-12-10
1907 index)
1916 end)))
1919 string
1925 \f
1926 ;;; (partially) constant-fold backq-* functions, or convert to their
1927 ;;; plain CL equivalent (now that they're not needed for pprinting).
1929 ;; Pop constant values from the end, list/list* them if any, and link
1930 ;; the remainder with list* at runtime.
1938 constants))
1944 `',tail
1959 ;; Merge adjacent constant values
1975 "Non-list or improper list spliced in ~
1987 \f