X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=OPTIMIZATIONS;h=69f444748483bbcc9a3c7f3b741d70b0d3db3829;hb=8877972d33c4178384348bf8a8416926047ca357;hp=1f8746f14400565d7246281ee0710e2f5721de78;hpb=59ac7389b0bead82dfe2c94a5edab79dc9569c61;p=sbcl.git diff --git a/OPTIMIZATIONS b/OPTIMIZATIONS index 1f8746f..69f4447 100644 --- a/OPTIMIZATIONS +++ b/OPTIMIZATIONS @@ -62,34 +62,6 @@ VOP DATA-VECTOR-SET/SIMPLE-STRING V2!14[EDI] t32[EAX] t30[S2]>t33[CL] * And why two moves? -------------------------------------------------------------------------------- -#6 -09:49:05 I have found a case in those where suboptimal code is - generate with nested loops, it might be moderately easy to fix that -09:49:28 see - http://www.bagley.org/~doug/shootout/bench/nestedloop/nestedloop.cmucl -09:50:30 if you add declarations to dotimes, generated code is - almost optimal, but most inner loops run out of registers and use - memory location for iteration variable - -;;; -*- mode: lisp -*- -;;; http://www.bagley.org/~doug/shootout/ -;;; from Friedrich Dominicus - -(defun main () - (let ((n (parse-integer (or (car (last extensions:*command-line-strings*)) "1"))) - (x 0)) - (declare (fixnum n) - (fixnum x) - (optimize (speed 3) (debug 0) (safety 0))) - (dotimes (a n) - (dotimes (b n) - (dotimes (c n) - (dotimes (d n) - (dotimes (e n) - (dotimes (f n) - (incf x))))))) - (format t "~A~%" x))) --------------------------------------------------------------------------------- #8 (defun foo (d) (declare (optimize (speed 3) (safety 0) (debug 0))) @@ -190,3 +162,189 @@ through TYPEP UNBOXED-ARRAY, within the compiler itself. rather than either constant-folding or manipulating NIL-VALUE or NULL-TN directly. -------------------------------------------------------------------------------- +#19 + (let ((dx (if (foo) + (list x) + (list y z)))) + (declare (dynamic-extent dx)) + ...) + +DX is not allocated on stack. +-------------------------------------------------------------------------------- +#20 +(defun-with-dx foo (x) + (flet ((make (x) + (let ((l (list nil nil))) + (setf (first l) x) + (setf (second l) (1- x)) + l))) + (let ((l (make x))) + (declare (dynamic-extent l)) + (mapc #'print l)))) + +Result of MAKE is not stack allocated, which means that +stack-allocation of structures is impossible. +-------------------------------------------------------------------------------- +#21 +(defun-with-dx foo () + (let ((dx (list (list 1 2) (list 3 4)))) + (declare (dynamic-extent dx)) + ...)) + +External list in DX is allocated on stack, but internal are not. +-------------------------------------------------------------------------------- +#22 +IR2 does not perform unused code flushing. +-------------------------------------------------------------------------------- +#23 +Python does not know that &REST lists are LISTs (and cannot derive it). +-------------------------------------------------------------------------------- +#24 +a. Iterations on &REST lists, returning them as VALUES could be + rewritten with &MORE vectors. +b. Implement local unknown-values mv-call (useful for fast type checking). +-------------------------------------------------------------------------------- +#26 +SBCL cannot derive upper bound for I and uses generic arithmetic here: + +(defun foo (l) + (declare (vector l)) + (dotimes (i (length l)) + (if (block nil + (map-foo (lambda (x) (if x (return t))) + l)) + t + nil))) + +(So the constraint propagator or a possible future SSA-convertor +should know the connection between an NLE and its CLEANUP.) +-------------------------------------------------------------------------------- +#27 +Initialization of stack-allocated arrays is inefficient: we always +fill the vector with zeroes, even when it is not needed (as for +platforms with conservative GC or for arrays of unboxed objectes) and +is performed later explicitely. +-------------------------------------------------------------------------------- +#28 +a. Accessing raw slots in structure instances is more inefficient than +it could be; if we placed raw slots before the header word, we would +not need to do arithmetic at runtime to access them. (But beware: +this would complicate handling of the interior pointer). + +b. (Also note that raw slots are currently disabled on HPPA) +-------------------------------------------------------------------------------- +#29 +Python is overly zealous when converting high-level CL functions, such +as MIN/MAX, LOGBITP, and LOGTEST, to low-level CL functions. Reducing +Python's aggressiveness would make it easier to effect changes such as + +x86-64: +* direct MIN/MAX on {SINGLE,DOUBLE}-FLOATs ({MIN,MAX}S{S,D}) + +x86-64: +* direct LOGBITP on word-sized integers and fixnums (BT + JC) + +x86{,-64}/PPC: +* branch-free MIN/MAX on word-sized integers and fixnums (floats could + be handled too, modulo safety considerations on the PPC) + +x86-64: +* efficient LOGTESTs on word-sized integers and fixnums (TEST) + +etc., etc. + +(The framework for this has been implemented as of 0.9.9.18; see the +vm-support-routine COMBINATION-IMPLEMENTATION-STYLE and its use in +src/compiler/ir1opt.lisp, IR1-OPTIMIZE-COMBINATION. The above +optimizations are left as an exercise for the reader.) +-------------------------------------------------------------------------------- +#30 +(defun foo (x y) + (< x y)) + +FOO's IR1 representation is roughly: + +(defun foo (x y) + (if (< x y) + T + NIL)) + +However, if a full call is generated for < (and similarly for other +predicate functions), then the IF is unnecessary, since the return value +of (< x y) is already T or NIL. +-------------------------------------------------------------------------------- +#31 +The typecheck generated for a declaration like (integer 0 45) on x86 looks +like: + +; 12B: F6C203 TEST DL, 3 +; 12E: 753B JNE L1 +; 130: 8BC2 MOV EAX, EDX +; 132: 83F800 CMP EAX, 0 +; 135: 7C34 JL L1 +; 137: 8BC2 MOV EAX, EDX +; 139: 3DB4000000 CMP EAX, 180 +; 13E: 7F2B JNLE L1 + +A better code sequence for this would be: + + TEST DL, 3 + JNE L1 + MOV EAX, EDX + CMP EAX, 180 + JBE L1 + +Doing an unsigned comparison means that, similarly to %CHECK-BOUND, we can +combine the <0 and >=bound tests. This sort of test is generated often +in SBCL and any array-based code that's serious about type-checking its +indices. +-------------------------------------------------------------------------------- +#32 +The code for a vector bounds check on x86 (similarly on x86-64) where +the vector is in EDX and the index in EAX looks like: + +; 49: L0: 8B5AFD MOV EBX, [EDX-3] +; 4C: 39C3 CMP EBX, EAX +; 4E: 7632 JBE L2 + +because %CHECK-BOUND is used for bounds-checking any array dimension. +A more efficient specialization (%CHECK-BOUND/VECTOR) would produce: + + CMP [EDX-3], EAX + JBE L2 + +Which is slightly shorter and avoids using a register. +-------------------------------------------------------------------------------- +#33 +Reports from the Java camp indicate that using an SSE2-based +floating-point backend on x86 when possible is highly preferable to +using the x86 FP stack. It would be nice if SBCL included an SSE2-based +floating point backend with a compile-time option to switch between the +two. +-------------------------------------------------------------------------------- +#34 +Compiling + +(defun foo (x y) + (declare (type (integer 0 45) x y)) + (+ x y)) + +results in the following error trapping code for type-checking the +arguments: + +; 424: L0: 8B058CE31812 MOV EAX, [#x1218E38C] ; '(MOD 46) +; 42A: 0F0B0A BREAK 10 ; error trap +; 42D: 05 BYTE #X05 +; 42E: 1F BYTE #X1F ; OBJECT-NOT-TYPE-ERROR +; 42F: FECE01 BYTE #XFE, #XCE, #X01 ; EDI +; 432: 0E BYTE #X0E ; EAX +; 433: L1: 8B0590E31812 MOV EAX, [#x1218E390] ; '(MOD 46) +; 439: 0F0B0A BREAK 10 ; error trap +; 43C: 03 BYTE #X03 +; 43D: 1F BYTE #X1F ; OBJECT-NOT-TYPE-ERROR +; 43E: 8E BYTE #X8E ; EDX +; 43F: 0E BYTE #X0E ; EAX + +Notice that '(MOD 46) has two entries in the constant vector. Having +one would be preferable. +