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 #6
  66 09:49:05 <jtra> I have found a case in those where suboptimal code is
  67   generate with nested loops, it might be moderately easy to fix that
  68 09:49:28 <jtra> see
  69   http://www.bagley.org/~doug/shootout/bench/nestedloop/nestedloop.cmucl
  70 09:50:30 <jtra> if you add declarations to dotimes, generated code is
  71   almost optimal, but most inner loops run out of registers and use
  72   memory location for iteration variable
  73
  74 ;;; -*- mode: lisp -*-
  75 ;;; http://www.bagley.org/~doug/shootout/
  76 ;;; from Friedrich Dominicus
  77
  78 (defun main ()
  79   (let ((n (parse-integer (or (car (last extensions:*command-line-strings*)) "1")))
  80         (x 0))
  81     (declare (fixnum n)
  82              (fixnum x)
  83              (optimize (speed 3) (debug 0) (safety 0)))
  84     (dotimes (a n)
  85       (dotimes (b n)
  86         (dotimes (c n)
  87           (dotimes (d n)
  88             (dotimes (e n)
  89               (dotimes (f n)
  90                 (incf x)))))))
  91    (format t "~A~%" x)))
  92 --------------------------------------------------------------------------------
  93 #8
  94 (defun foo (d)
  95   (declare (optimize (speed 3) (safety 0) (debug 0)))
  96   (declare (type (double-float 0d0 1d0) d))
  97   (loop for i fixnum from 1 to 5
  98         for x1 double-float = (sin d) ;;; !!!
  99         do (loop for j fixnum from 1 to 4
 100                  sum x1 double-float)))
 101
 102 Without the marked declaration Python will use boxed representation for X1.
 103
 104 This is equivalent to
 105
 106 (let ((x nil))
 107   (setq x 0d0)
 108   ;; use of X as DOUBLE-FLOAT
 109 )
 110
 111 The initial binding is effectless, and without it X is of type
 112 DOUBLE-FLOAT. Unhopefully, IR1 does not optimize away effectless
 113 SETs/bindings, and IR2 does not perform type inference.
 114 --------------------------------------------------------------------------------
 115 #9 "Multi-path constant folding"
 116 (defun foo (x)
 117   (if (= (cond ((irgh x) 0)
 118                ((buh x) 1)
 119                (t 2))
 120          0)
 121       :yes
 122       :no))
 123
 124 This code could be optimized to
 125
 126 (defun foo (x)
 127   (cond ((irgh x) :yes)
 128         ((buh x) :no)
 129         (t :no)))
 130 --------------------------------------------------------------------------------
 131 #11
 132 (inverted variant of #9)
 133
 134 (lambda (x)
 135   (let ((y (sap-alien x c-string)))
 136     (list (alien-sap y)
 137           (alien-sap y))))
 138
 139 It could be optimized to
 140
 141 (lambda (x) (list x x))
 142
 143 (if Y were used only once, the current compiler would optimize it)
 144 --------------------------------------------------------------------------------
 145 #12
 146 (typep (truly-the (simple-array * (*)) x) 'simple-vector)
 147
 148 tests lowtag.
 149 --------------------------------------------------------------------------------
 150 #13
 151 FAST-+/FIXNUM and similar should accept unboxed arguments in interests
 152 of representation selection. Problem: inter-TN dependencies.
 153 --------------------------------------------------------------------------------
 154 #14
 155 The derived type of (/ (THE (DOUBLE-FLOAT (0D0)) X) (THE (DOUBLE-FLOAT
 156 1D0) Y)) is (DOUBLE-FLOAT 0.0d0). While it might be reasonable, it is
 157 better to derive (OR (MEMBER 0.0d0) (DOUBLE-FLOAT (0.0d0))).
 158 --------------------------------------------------------------------------------
 159 #15
 160 On the alpha, the system is reluctant to refer directly to a constant bignum,
 161 preferring to load a large constant through a slow sequence of instructions,
 162 then cons up a bignum for it:
 163
 164 (LAMBDA (A)
 165   (DECLARE (OPTIMIZE (SAFETY 1) (SPEED 3) (DEBUG 1))
 166            (TYPE (INTEGER -10000 10000) A)
 167            (IGNORABLE A))
 168   (CASE A
 169     ((89 125 16) (ASH A (MIN 18 -706)))
 170     (T (DPB -3 (BYTE 30 30) -1))))
 171 --------------------------------------------------------------------------------
 172 #16
 173 (do ((i 0 (1+ i)))
 174     ((= i (the (integer 0 100) n)))
 175   ...)
 176
 177 It is commonly expected for Python to derive (FIXNUMP I). (If ``='' is
 178 replaced with ``>='', Python will do.)
 179 --------------------------------------------------------------------------------