1.0.45.5: life: Propagate implicit value cells through tail-calls.
[sbcl.git] / OPTIMIZATIONS
1 #1
2 (defun mysl (s)
3     (declare (simple-string s))
4     (declare (optimize (speed 3) (safety 0) (debug 0)))
5     (let ((c 0))
6       (declare (fixnum c))
7       (dotimes (i (length s))
8         (when (eql (aref s i) #\1)
9           (incf c)))
10       c))
11
12 * On X86 I is represented as a tagged integer.
13
14 * Unnecessary move:
15   3: SLOT S!11[EDX] {SB-C::VECTOR-LENGTH 1 7} => t23[EAX]
16   4: MOVE t23[EAX] => t24[EBX]
17
18 --------------------------------------------------------------------------------
19 #2
20 (defun quux (v)
21   (declare (optimize (speed 3) (safety 0) (space 2) (debug 0)))
22   (declare (type (simple-array double-float 1) v))
23   (let ((s 0d0))
24     (declare (type double-float s))
25     (dotimes (i (length v))
26       (setq s (+ s (aref v i))))
27     s))
28
29 * Python does not combine + with AREF, so generates extra move and
30   allocates a register.
31
32 * On X86 Python thinks that all FP registers are directly accessible
33   and emits costy MOVE ... => FR1.
34
35 --------------------------------------------------------------------------------
36 #3
37 (defun bar (n)
38   (declare (optimize (speed 3) (safety 0) (space 2))
39            (type fixnum n))
40   (let ((v (make-list n)))
41     (setq v (make-array n))
42     (length v)))
43
44 * IR1 does not optimize away (MAKE-LIST N).
45 --------------------------------------------------------------------------------
46 #4
47 (defun bar (v1 v2)
48   (declare (optimize (speed 3) (safety 0) (space 2))
49            (type (simple-array base-char 1) v1 v2))
50   (dotimes (i (length v1))
51     (setf (aref v2 i) (aref v1 i))))
52
53 VOP DATA-VECTOR-SET/SIMPLE-STRING V2!14[EDI] t32[EAX] t30[S2]>t33[CL]
54                                   => t34[S2]<t35[AL] 
55         MOV     #<TN t33[CL]>, #<TN t30[S2]>
56         MOV     BYTE PTR [EDI+EAX+1], #<TN t33[CL]>
57         MOV     #<TN t35[AL]>, #<TN t33[CL]>
58         MOV     #<TN t34[S2]>, #<TN t35[AL]>
59
60 * The value of DATA-VECTOR-SET is not used, so there is no need in the
61   last two moves.
62
63 * And why two moves?
64 --------------------------------------------------------------------------------
65 #8
66 (defun foo (d)
67   (declare (optimize (speed 3) (safety 0) (debug 0)))
68   (declare (type (double-float 0d0 1d0) d))
69   (loop for i fixnum from 1 to 5
70         for x1 double-float = (sin d) ;;; !!!
71         do (loop for j fixnum from 1 to 4
72                  sum x1 double-float)))
73
74 Without the marked declaration Python will use boxed representation for X1.
75
76 This is equivalent to
77
78 (let ((x nil))
79   (setq x 0d0)
80   ;; use of X as DOUBLE-FLOAT
81 )
82
83 The initial binding is effectless, and without it X is of type
84 DOUBLE-FLOAT. Unhopefully, IR1 does not optimize away effectless
85 SETs/bindings, and IR2 does not perform type inference.
86 --------------------------------------------------------------------------------
87 #9 "Multi-path constant folding"
88 (defun foo (x)
89   (if (= (cond ((irgh x) 0)
90                ((buh x) 1)
91                (t 2))
92          0)
93       :yes
94       :no))
95
96 This code could be optimized to
97
98 (defun foo (x)
99   (cond ((irgh x) :yes)
100         ((buh x) :no)
101         (t :no)))
102 --------------------------------------------------------------------------------
103 #11
104 (inverted variant of #9)
105
106 (lambda (x)
107   (let ((y (sap-alien x c-string)))
108     (list (alien-sap y)
109           (alien-sap y))))
110
111 It could be optimized to
112
113 (lambda (x) (list x x))
114
115 (if Y were used only once, the current compiler would optimize it)
116 --------------------------------------------------------------------------------
117 #12
118 (typep (truly-the (simple-array * (*)) x) 'simple-vector)
119
120 tests lowtag.
121 --------------------------------------------------------------------------------
122 #13
123 FAST-+/FIXNUM and similar should accept unboxed arguments in interests
124 of representation selection. Problem: inter-TN dependencies.
125 --------------------------------------------------------------------------------
126 #14
127 The derived type of (/ (THE (DOUBLE-FLOAT (0D0)) X) (THE (DOUBLE-FLOAT
128 1D0) Y)) is (DOUBLE-FLOAT 0.0d0). While it might be reasonable, it is
129 better to derive (OR (MEMBER 0.0d0) (DOUBLE-FLOAT (0.0d0))).
130 --------------------------------------------------------------------------------
131 #15
132 On the alpha, the system is reluctant to refer directly to a constant bignum,
133 preferring to load a large constant through a slow sequence of instructions,
134 then cons up a bignum for it:
135
136 (LAMBDA (A)
137   (DECLARE (OPTIMIZE (SAFETY 1) (SPEED 3) (DEBUG 1))
138            (TYPE (INTEGER -10000 10000) A)
139            (IGNORABLE A))
140   (CASE A
141     ((89 125 16) (ASH A (MIN 18 -706)))
142     (T (DPB -3 (BYTE 30 30) -1))))
143 --------------------------------------------------------------------------------
144 #16
145 (do ((i 0 (1+ i)))
146     ((= i (the (integer 0 100) n)))
147   ...)
148
149 It is commonly expected for Python to derive (FIXNUMP I). (If ``='' is
150 replaced with ``>='', Python will do.)
151 --------------------------------------------------------------------------------
152 #17 
153 Type tests for (ARRAY BIT), (ARRAY T) and similar go through full
154 %TYPEP, even though it is relatively simple to establish the arrayness
155 of an object and also to obtain the element type of an array.  As of
156 sbcl-0.8.12.30, this affects at least DUMP-OBJECT through
157 COMPOUND-OBJECT-P, and (LABELS MAYBE-EMIT-MAKE-LOAD-FORMS GROVEL)
158 through TYPEP UNBOXED-ARRAY, within the compiler itself.
159 --------------------------------------------------------------------------------
160 #18
161 (lambda (x) (declare (null x)) (sxhash x)) goes through SYMBOL-HASH
162 rather than either constant-folding or manipulating NIL-VALUE or
163 NULL-TN directly.
164 --------------------------------------------------------------------------------
165 #20
166 (defun-with-dx foo (x)
167   (flet ((make (x)
168            (let ((l (list nil nil)))
169              (setf (first l) x)
170              (setf (second l) (1- x))
171              l)))
172     (let ((l (make x)))
173       (declare (dynamic-extent l))
174       (mapc #'print l))))
175
176 Result of MAKE is not stack allocated.
177 --------------------------------------------------------------------------------
178 #22
179 IR2 does not perform unused code flushing.
180 --------------------------------------------------------------------------------
181 #24
182 a. Iterations on &REST lists, returning them as VALUES could be
183    rewritten with &MORE vectors.
184 b. Implement local unknown-values mv-call (useful for fast type checking).
185 --------------------------------------------------------------------------------
186 #26
187 SBCL cannot derive upper bound for I and uses generic arithmetic here:
188
189 (defun foo (l)
190   (declare (vector l))
191   (dotimes (i (length l))
192     (if (block nil
193           (map-foo (lambda (x) (if x (return t)))
194                    l))
195         t
196         nil)))
197
198 (So the constraint propagator or a possible future SSA-convertor
199 should know the connection between an NLE and its CLEANUP.)
200 --------------------------------------------------------------------------------
201 #27
202 Initialization of stack-allocated arrays is inefficient: we always
203 fill the vector with zeroes, even when it is not needed (as for
204 platforms with conservative GC or for arrays of unboxed objectes) and
205 is performed later explicitely.
206
207 (This is harder than it might look at first glance, as MAKE-ARRAY is smart
208 enough to eliminate something like ':initial-element 0'.  Such an optimization
209 is valid if the vector is being allocated in the heap, but not if it is being
210 allocated on the stack.  You could remove this optimization, but that makes
211 the heap-allocated case somewhat slower...)
212
213 To do this, extend ALLOCATE-VECTOR with ALLOW-JUNK argument, and when
214 stack allocating don't zero if it is true -- and probably ALLOW-JUNK iff
215 the vector is a specialized one (cannot have pointers.)
216 --------------------------------------------------------------------------------
217 #28
218 a. Accessing raw slots in structure instances is more inefficient than
219 it could be; if we placed raw slots before the header word, we would
220 not need to do arithmetic at runtime to access them.  (But beware:
221 this would complicate handling of the interior pointer).
222
223 b. (Also note that raw slots are currently disabled on HPPA)
224 --------------------------------------------------------------------------------
225 #29
226 Python is overly zealous when converting high-level CL functions, such
227 as MIN/MAX, LOGBITP, and LOGTEST, to low-level CL functions.  Reducing
228 Python's aggressiveness would make it easier to effect changes such as
229
230 x86-64:
231 * direct MIN/MAX on {SINGLE,DOUBLE}-FLOATs ({MIN,MAX}S{S,D})
232
233 x86-64:
234 * direct LOGBITP on word-sized integers and fixnums (BT + JC)
235
236 x86{,-64}/PPC:
237 * branch-free MIN/MAX on word-sized integers and fixnums (floats could
238   be handled too, modulo safety considerations on the PPC)
239
240 x86-64:
241 * efficient LOGTESTs on word-sized integers and fixnums (TEST)
242
243 etc., etc.
244
245 (The framework for this has been implemented as of 0.9.9.18; see the
246 vm-support-routine COMBINATION-IMPLEMENTATION-STYLE and its use in
247 src/compiler/ir1opt.lisp, IR1-OPTIMIZE-COMBINATION.  The above
248 optimizations are left as an exercise for the reader.)
249 --------------------------------------------------------------------------------
250 #30
251 (defun foo (x y)
252   (< x y))
253
254 FOO's IR1 representation is roughly:
255
256 (defun foo (x y)
257   (if (< x y)
258       T
259       NIL))
260
261 However, if a full call is generated for < (and similarly for other
262 predicate functions), then the IF is unnecessary, since the return value
263 of (< x y) is already T or NIL.
264 --------------------------------------------------------------------------------
265 #31
266 The typecheck generated for a declaration like (integer 0 45) on x86 looks
267 like:
268
269 ;      12B:       F6C203           TEST DL, 3
270 ;      12E:       753B             JNE L1
271 ;      130:       8BC2             MOV EAX, EDX
272 ;      132:       83F800           CMP EAX, 0
273 ;      135:       7C34             JL L1
274 ;      137:       8BC2             MOV EAX, EDX
275 ;      139:       3DB4000000       CMP EAX, 180
276 ;      13E:       7F2B             JNLE L1
277
278 A better code sequence for this would be:
279
280   TEST DL, 3
281   JNE L1
282   MOV EAX, EDX
283   CMP EAX, 180
284   JBE L1
285
286 Doing an unsigned comparison means that, similarly to %CHECK-BOUND, we can
287 combine the <0 and >=bound tests.  This sort of test is generated often
288 in SBCL and any array-based code that's serious about type-checking its
289 indices.
290 --------------------------------------------------------------------------------
291 #32
292 The code for a vector bounds check on x86 (similarly on x86-64) where
293 the vector is in EDX and the index in EAX looks like:
294
295 ;       49: L0:   8B5AFD           MOV EBX, [EDX-3]
296 ;       4C:       39C3             CMP EBX, EAX
297 ;       4E:       7632             JBE L2
298
299 because %CHECK-BOUND is used for bounds-checking any array dimension.
300 A more efficient specialization (%CHECK-BOUND/VECTOR) would produce:
301
302   CMP [EDX-3], EAX
303   JBE L2
304
305 Which is slightly shorter and avoids using a register.
306 --------------------------------------------------------------------------------
307 #33
308 Reports from the Java camp indicate that using an SSE2-based
309 floating-point backend on x86 when possible is highly preferable to
310 using the x86 FP stack.  It would be nice if SBCL included an SSE2-based
311 floating point backend with a compile-time option to switch between the
312 two.
313 --------------------------------------------------------------------------------
314 #35
315 Compiling
316
317 (defun foo (a i)
318   (declare (type simple-vector a))
319   (aref a i))
320
321 results in the following x86 code:
322
323 ; 115886E9:       F7C703000000     TEST EDI, 3                ; no-arg-parsing entry point
324 ;      6EF:       7510             JNE L0
325 ;      6F1:       8BC7             MOV EAX, EDI
326 ;      6F3:       83F800           CMP EAX, 0
327 ;      6F6:       7C09             JL L0
328 ;      6F8:       8BC7             MOV EAX, EDI
329 ;      6FA:       3DF8FFFF7F       CMP EAX, 2147483640
330 ;      6FF:       7E0F             JLE L1
331 ;      701: L0:   8B057C865811     MOV EAX, [#x1158867C]      ; '(MOD
332                                                               ;   536870911)
333 ;      707:       0F0B0A           BREAK 10                   ; error trap
334 ;      70A:       05               BYTE #X05
335 ;      70B:       1F               BYTE #X1F                  ; OBJECT-NOT-TYPE-ERROR
336 ;      70C:       FECE01           BYTE #XFE, #XCE, #X01      ; EDI
337 ;      70F:       0E               BYTE #X0E                  ; EAX
338 ;      710: L1:   8B42FD           MOV EAX, [EDX-3]
339 ;      713:       8BCF             MOV ECX, EDI
340 ;      715:       39C8             CMP EAX, ECX
341 ;      717:       7620             JBE L2
342 ;      719:       8B540A01         MOV EDX, [EDX+ECX+1]
343
344 ... plus the standard return sequence and some error blocks.  The
345 `TEST EDI, 3' and associated comparisons are to ensure that `I' is a
346 positive fixnum.  The associated comparisons are unnecessary, as the
347 %CHECK-BOUND VOP only requires its tested index to be a fixnum and takes
348 care of the negative fixnum case itself.
349
350 {HAIRY-,}DATA-VECTOR-REF are DEFKNOWN'd with EXPLICIT-CHECK, which would
351 seem to take care of this, but EXPLICIT-CHECK only seems to be used when
352 compiling calls to unknown functions or similar.  Furthermore,
353 EXPLICIT-CHECK, as NJF understands it, doesn't have the right
354 semantics--it suppresses all type checking of arguments, whereas what we
355 really want is to ensure that the argument is a fixnum, but not check
356 its positiveness.
357 --------------------------------------------------------------------------------
358 #36
359
360 In #35, the CMP EAX, $foo instructions are all preceded by a MOV.  They
361 appear to be unnecessary, but are necessary because in IR2, EDI is a
362 DESCRIPTOR-REG, whereas EAX is an ANY-REG--and the comparison VOPs only
363 accept ANY-REGs.  Therefore, the MOVs are "necessary" to ensure that the
364 comparison VOP receives an TN of the appropriate storage class.
365
366 Obviously, it would be better if a) we only performed one MOV prior to
367 all three comparisons or b) eliminated the necessity of the MOV(s)
368 altogether.  The former option is probably easier than the latter.
369
370 --------------------------------------------------------------------------------
371 #38
372
373 (setf (subseq s1 start1 end1) (subseq s2 start2 end1))
374
375 could be transformed into
376
377 (let ((#:s2 s2)
378       (#:start2 start2)
379       (#:end2 end2))
380  (replace s1 #:s2 :start1 start1 :end1 end1 :start2 #:start2 :end2 #:end2))
381
382 when the return value is unused, avoiding the need to cons up the new sequence.
383
384 --------------------------------------------------------------------------------
385 #39
386
387 (let ((*foo* 42)) ...)
388
389 currently compiles to code that ensures the TLS index at runtime, which
390 is both a decently large chunk of code and unnecessary, as we could ensure
391 the TLS index at load-time as well.
392
393 --------------------------------------------------------------------------------
394 #40
395
396 When FTYPE is declared -- to say (function (t t t t t) t), and
397 function has a compiler-macro,
398
399   (apply #'foo 'x1 x2 'x3 more)
400
401 can be transformed into
402
403   (apply (lambda (x2 x4 x5) (foo 'x1 x2 'x3 x4 x5)) x2 more)
404
405 which allows compiler-macro-expansion for FOO. (Only constant
406 arguments can be moved inside the new lambda -- otherwise evaluation
407 order is altered.)
408
409 --------------------------------------------------------------------------------
410 #41
411
412 The unibyte external formats are written in a very generic way.  Three
413 optimizations immediately applicable that could be automatically
414 generated:
415
416 (a) if the external format merely permutes the first 256 characters, a
417     constant-time lookup (rather than a binary search) could be
418     performed on output.  This applies at least to EBCDIC, which
419     currently has a hand-rolled mapper instead.
420
421 (b) if there are no undefined characters corresponding to the 256
422     codes, then no error checking need be done on input.
423
424 (c) if there is a way to use particular bits of the exceptional
425     characters, constant-time output (rather than binary search) can
426     still be achieved as used to be done by the latin-9 external
427     format before 1.0.31.