X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fx86%2Farith.lisp;h=4abd9c63b014d516649531ccfa13645730913224;hb=7deecae2d959173eda6a153d490c752c32050a9e;hp=46f5326ae6c55f306d62040357eeac14dffabcf7;hpb=0d871fd7a98fc4af92a8b942a1154761466ad8c9;p=sbcl.git diff --git a/src/compiler/x86/arith.lisp b/src/compiler/x86/arith.lisp index 46f5326..4abd9c6 100644 --- a/src/compiler/x86/arith.lisp +++ b/src/compiler/x86/arith.lisp @@ -46,13 +46,13 @@ (define-vop (fast-lognot/fixnum fixnum-unop) (:translate lognot) - (:generator 2 + (:generator 1 (move res x) (inst xor res (fixnumize -1)))) (define-vop (fast-lognot/signed signed-unop) (:translate lognot) - (:generator 1 + (:generator 2 (move res x) (inst not res))) @@ -359,7 +359,7 @@ (:note "inline fixnum arithmetic") (:generator 4 (move r x) - (inst sar r 2) + (inst sar r n-fixnum-tag-bits) (inst imul r y))) (define-vop (fast-*-c/fixnum=>fixnum fast-safe-arith-op) @@ -436,7 +436,7 @@ (:vop-var vop) (:save-p :compute-only) (:generator 31 - (let ((zero (generate-error-code vop division-by-zero-error x y))) + (let ((zero (generate-error-code vop 'division-by-zero-error x y))) (if (sc-is y any-reg) (inst test y y) ; smaller instruction (inst cmp y 0)) @@ -445,8 +445,9 @@ (inst cdq) (inst idiv eax y) (if (location= quo eax) - (inst shl eax 2) - (inst lea quo (make-ea :dword :index eax :scale 4))) + (inst shl eax n-fixnum-tag-bits) + (inst lea quo (make-ea :dword :index eax + :scale (ash 1 n-fixnum-tag-bits)))) (move rem edx))) (define-vop (fast-truncate-c/fixnum=>fixnum fast-safe-arith-op) @@ -471,8 +472,9 @@ (inst mov y-arg (fixnumize y)) (inst idiv eax y-arg) (if (location= quo eax) - (inst shl eax 2) - (inst lea quo (make-ea :dword :index eax :scale 4))) + (inst shl eax n-fixnum-tag-bits) + (inst lea quo (make-ea :dword :index eax + :scale (ash 1 n-fixnum-tag-bits)))) (move rem edx))) (define-vop (fast-truncate/unsigned=>unsigned fast-safe-arith-op) @@ -491,7 +493,7 @@ (:vop-var vop) (:save-p :compute-only) (:generator 33 - (let ((zero (generate-error-code vop division-by-zero-error x y))) + (let ((zero (generate-error-code vop 'division-by-zero-error x y))) (if (sc-is y unsigned-reg) (inst test y y) ; smaller instruction (inst cmp y 0)) @@ -542,7 +544,7 @@ (:vop-var vop) (:save-p :compute-only) (:generator 33 - (let ((zero (generate-error-code vop division-by-zero-error x y))) + (let ((zero (generate-error-code vop 'division-by-zero-error x y))) (if (sc-is y signed-reg) (inst test y y) ; smaller instruction (inst cmp y 0)) @@ -597,24 +599,27 @@ (:note "inline ASH") (:generator 2 (cond ((and (= amount 1) (not (location= number result))) - (inst lea result (make-ea :dword :index number :scale 2))) + (inst lea result (make-ea :dword :base number :index number))) ((and (= amount 2) (not (location= number result))) (inst lea result (make-ea :dword :index number :scale 4))) ((and (= amount 3) (not (location= number result))) (inst lea result (make-ea :dword :index number :scale 8))) (t (move result number) - (cond ((plusp amount) - ;; We don't have to worry about overflow because of the - ;; result type restriction. - (inst shl result amount)) - (t - ;; If the amount is greater than 31, only shift by 31. We - ;; have to do this because the shift instructions only look - ;; at the low five bits of the result. - (inst sar result (min 31 (- amount))) - ;; Fixnum correction. - (inst and result #xfffffffc))))))) + (cond ((< -32 amount 32) + ;; this code is used both in ASH and ASH-SMOD30, so + ;; be careful + (if (plusp amount) + (inst shl result amount) + (progn + (inst sar result (- amount)) + (inst and result (lognot fixnum-tag-mask))))) + ((plusp amount) + (if (sc-is result any-reg) + (inst xor result result) + (inst mov result 0))) + (t (inst sar result 31) + (inst and result (lognot fixnum-tag-mask)))))))) (define-vop (fast-ash-left/fixnum=>fixnum) (:translate ash) @@ -655,7 +660,7 @@ (:note "inline ASH") (:generator 3 (cond ((and (= amount 1) (not (location= number result))) - (inst lea result (make-ea :dword :index number :scale 2))) + (inst lea result (make-ea :dword :base number :index number))) ((and (= amount 2) (not (location= number result))) (inst lea result (make-ea :dword :index number :scale 4))) ((and (= amount 3) (not (location= number result))) @@ -682,7 +687,7 @@ (:note "inline ASH") (:generator 3 (cond ((and (= amount 1) (not (location= number result))) - (inst lea result (make-ea :dword :index number :scale 2))) + (inst lea result (make-ea :dword :base number :index number))) ((and (= amount 2) (not (location= number result))) (inst lea result (make-ea :dword :index number :scale 4))) ((and (= amount 3) (not (location= number result))) @@ -920,7 +925,9 @@ (:result-types unsigned-num) (:generator 28 (move res arg) - (inst cmp res 0) + (if (sc-is res unsigned-reg) + (inst test res res) + (inst cmp res 0)) (inst jmp :ge POS) (inst not res) POS @@ -953,49 +960,58 @@ (:translate logcount) (:note "inline (unsigned-byte 32) logcount") (:policy :fast-safe) - (:args (arg :scs (unsigned-reg))) + (:args (arg :scs (unsigned-reg) :target result)) (:arg-types unsigned-num) (:results (result :scs (unsigned-reg))) (:result-types positive-fixnum) - (:temporary (:sc unsigned-reg :from (:argument 0)) temp) - (:generator 30 + (:temporary (:sc unsigned-reg) temp) + (:generator 14 + ;; See the comments below for how the algorithm works. The tricks + ;; used can be found for example in AMD's software optimization + ;; guide or at "http://www.hackersdelight.org/HDcode/pop.cc" in the + ;; function "pop1". + ;; Calculate 2-bit sums. Note that the value of a two-digit binary + ;; number is the sum of the right digit and twice the left digit. + ;; Thus we can calculate the sum of the two digits by shifting the + ;; left digit to the right position and doing a two-bit subtraction. + ;; This subtraction will never create a borrow and thus can be made + ;; on all 16 2-digit numbers at once. (move result arg) - - (inst mov temp result) - (inst shr temp 1) + (move temp arg) + (inst shr result 1) (inst and result #x55555555) - (inst and temp #x55555555) - (inst add result temp) - - (inst mov temp result) + (inst sub temp result) + ;; Calculate 4-bit sums by straightforward shift, mask and add. + ;; Note that we shift the source operand of the MOV and not its + ;; destination so that the SHR and the MOV can execute in the same + ;; clock cycle. + (inst mov result temp) (inst shr temp 2) (inst and result #x33333333) (inst and temp #x33333333) (inst add result temp) - + ;; Calculate 8-bit sums. Since each sum is at most 8, which fits + ;; into 4 bits, we can apply the mask after the addition, saving one + ;; instruction. (inst mov temp result) - (inst shr temp 4) - (inst and result #x0f0f0f0f) - (inst and temp #x0f0f0f0f) + (inst shr result 4) (inst add result temp) - + (inst and result #x0f0f0f0f) + ;; Calculate the two 16-bit sums and the 32-bit sum. No masking is + ;; necessary inbetween since the final sum is at most 32 which fits + ;; into 6 bits. (inst mov temp result) - (inst shr temp 8) - (inst and result #x00ff00ff) - (inst and temp #x00ff00ff) + (inst shr result 8) (inst add result temp) - (inst mov temp result) - (inst shr temp 16) - (inst and result #x0000ffff) - (inst and temp #x0000ffff) - (inst add result temp))) + (inst shr result 16) + (inst add result temp) + (inst and result #xff))) ;;;; binary conditional VOPs (define-vop (fast-conditional) - (:conditional) - (:info target not-p) + (:conditional :e) (:effects) (:affected) (:policy :fast-safe)) @@ -1011,7 +1027,7 @@ (define-vop (fast-conditional-c/fixnum fast-conditional/fixnum) (:args (x :scs (any-reg control-stack))) (:arg-types tagged-num (:constant (signed-byte 30))) - (:info target not-p y)) + (:info y)) (define-vop (fast-conditional/signed fast-conditional) (:args (x :scs (signed-reg) @@ -1024,7 +1040,7 @@ (define-vop (fast-conditional-c/signed fast-conditional/signed) (:args (x :scs (signed-reg signed-stack))) (:arg-types signed-num (:constant (signed-byte 32))) - (:info target not-p y)) + (:info y)) (define-vop (fast-conditional/unsigned fast-conditional) (:args (x :scs (unsigned-reg) @@ -1037,10 +1053,72 @@ (define-vop (fast-conditional-c/unsigned fast-conditional/unsigned) (:args (x :scs (unsigned-reg unsigned-stack))) (:arg-types unsigned-num (:constant (unsigned-byte 32))) - (:info target not-p y)) + (:info y)) + +(macrolet ((define-logtest-vops () + `(progn + ,@(loop for suffix in '(/fixnum -c/fixnum + /signed -c/signed + /unsigned -c/unsigned) + for cost in '(4 3 6 5 6 5) + collect + `(define-vop (,(symbolicate "FAST-LOGTEST" suffix) + ,(symbolicate "FAST-CONDITIONAL" suffix)) + (:translate logtest) + (:conditional :ne) + (:generator ,cost + (emit-optimized-test-inst x + ,(if (eq suffix '-c/fixnum) + '(fixnumize y) + 'y)))))))) + (define-logtest-vops)) + +(defknown %logbitp (integer unsigned-byte) boolean + (movable foldable flushable always-translatable)) + +;;; only for constant folding within the compiler +(defun %logbitp (integer index) + (logbitp index integer)) + +;;; too much work to do the non-constant case (maybe?) +(define-vop (fast-logbitp-c/fixnum fast-conditional-c/fixnum) + (:translate %logbitp) + (:conditional :c) + (:arg-types tagged-num (:constant (integer 0 29))) + (:generator 4 + (inst bt x (+ y n-fixnum-tag-bits)))) +(define-vop (fast-logbitp/signed fast-conditional/signed) + (:args (x :scs (signed-reg signed-stack)) + (y :scs (signed-reg))) + (:translate %logbitp) + (:conditional :c) + (:generator 6 + (inst bt x y))) -(macrolet ((define-conditional-vop (tran cond unsigned not-cond not-unsigned) +(define-vop (fast-logbitp-c/signed fast-conditional-c/signed) + (:translate %logbitp) + (:conditional :c) + (:arg-types signed-num (:constant (integer 0 31))) + (:generator 5 + (inst bt x y))) + +(define-vop (fast-logbitp/unsigned fast-conditional/unsigned) + (:args (x :scs (unsigned-reg unsigned-stack)) + (y :scs (unsigned-reg))) + (:translate %logbitp) + (:conditional :c) + (:generator 6 + (inst bt x y))) + +(define-vop (fast-logbitp-c/unsigned fast-conditional-c/unsigned) + (:translate %logbitp) + (:conditional :c) + (:arg-types unsigned-num (:constant (integer 0 31))) + (:generator 5 + (inst bt x y))) + +(macrolet ((define-conditional-vop (tran cond unsigned) `(progn ,@(mapcar (lambda (suffix cost signed) @@ -1052,31 +1130,25 @@ (format nil "~:@(FAST-CONDITIONAL~A~)" suffix))) (:translate ,tran) + (:conditional ,(if signed + cond + unsigned)) (:generator ,cost (inst cmp x ,(if (eq suffix '-c/fixnum) '(fixnumize y) - 'y)) - (inst jmp (if not-p - ,(if signed - not-cond - not-unsigned) - ,(if signed - cond - unsigned)) - target)))) + 'y))))) '(/fixnum -c/fixnum /signed -c/signed /unsigned -c/unsigned) '(4 3 6 5 6 5) '(t t t t nil nil))))) - (define-conditional-vop < :l :b :ge :ae) - (define-conditional-vop > :g :a :le :be)) + (define-conditional-vop < :l :b) + (define-conditional-vop > :g :a)) (define-vop (fast-if-eql/signed fast-conditional/signed) (:translate eql) (:generator 6 - (inst cmp x y) - (inst jmp (if not-p :ne :e) target))) + (inst cmp x y))) (define-vop (fast-if-eql-c/signed fast-conditional-c/signed) (:translate eql) @@ -1084,14 +1156,12 @@ (cond ((and (sc-is x signed-reg) (zerop y)) (inst test x x)) ; smaller instruction (t - (inst cmp x y))) - (inst jmp (if not-p :ne :e) target))) + (inst cmp x y))))) (define-vop (fast-if-eql/unsigned fast-conditional/unsigned) (:translate eql) (:generator 6 - (inst cmp x y) - (inst jmp (if not-p :ne :e) target))) + (inst cmp x y))) (define-vop (fast-if-eql-c/unsigned fast-conditional-c/unsigned) (:translate eql) @@ -1099,8 +1169,7 @@ (cond ((and (sc-is x unsigned-reg) (zerop y)) (inst test x x)) ; smaller instruction (t - (inst cmp x y))) - (inst jmp (if not-p :ne :e) target))) + (inst cmp x y))))) ;;; EQL/FIXNUM is funny because the first arg can be of any type, not just a ;;; known fixnum. @@ -1120,8 +1189,7 @@ (:note "inline fixnum comparison") (:translate eql) (:generator 4 - (inst cmp x y) - (inst jmp (if not-p :ne :e) target))) + (inst cmp x y))) (define-vop (generic-eql/fixnum fast-eql/fixnum) (:args (x :scs (any-reg descriptor-reg) :load-if (not (and (sc-is x control-stack) @@ -1133,14 +1201,13 @@ (define-vop (fast-eql-c/fixnum fast-conditional/fixnum) (:args (x :scs (any-reg control-stack))) (:arg-types tagged-num (:constant (signed-byte 30))) - (:info target not-p y) + (:info y) (:translate eql) (:generator 2 (cond ((and (sc-is x any-reg) (zerop y)) (inst test x x)) ; smaller instruction (t - (inst cmp x (fixnumize y)))) - (inst jmp (if not-p :ne :e) target))) + (inst cmp x (fixnumize y)))))) (define-vop (generic-eql-c/fixnum fast-eql-c/fixnum) (:args (x :scs (any-reg descriptor-reg control-stack))) (:arg-types * (:constant (signed-byte 30))) @@ -1148,21 +1215,6 @@ ;;;; 32-bit logical operations -(define-vop (merge-bits) - (:translate merge-bits) - (:args (shift :scs (signed-reg unsigned-reg) :target ecx) - (prev :scs (unsigned-reg) :target result) - (next :scs (unsigned-reg))) - (:arg-types tagged-num unsigned-num unsigned-num) - (:temporary (:sc signed-reg :offset ecx-offset :from (:argument 0)) ecx) - (:results (result :scs (unsigned-reg) :from (:argument 1))) - (:result-types unsigned-num) - (:policy :fast-safe) - (:generator 4 - (move ecx shift) - (move result prev) - (inst shrd result next :cl))) - ;;; Only the lower 5 bits of the shift amount are significant. (define-vop (shift-towards-someplace) (:policy :fast-safe) @@ -1245,8 +1297,8 @@ (svop30f (intern (format nil "FAST-~S-SMOD30/FIXNUM=>FIXNUM" name))) (svop30cf (intern (format nil "FAST-~S-SMOD30-C/FIXNUM=>FIXNUM" name)))) `(progn - (define-modular-fun ,fun32 (x y) ,name :unsigned 32) - (define-modular-fun ,sfun30 (x y) ,name :signed 30) + (define-modular-fun ,fun32 (x y) ,name :untagged nil 32) + (define-modular-fun ,sfun30 (x y) ,name :tagged t 30) (define-mod-binop (,vop32u ,vopu) ,fun32) (define-vop (,vop32f ,vopf) (:translate ,fun32)) (define-vop (,svop30f ,vopf) (:translate ,sfun30)) @@ -1292,19 +1344,19 @@ (signed-byte 30) (foldable flushable movable)) -(define-modular-fun-optimizer %lea ((base index scale disp) :unsigned :width width) +(define-modular-fun-optimizer %lea ((base index scale disp) :untagged nil :width width) (when (and (<= width 32) (constant-lvar-p scale) (constant-lvar-p disp)) - (cut-to-width base :unsigned width) - (cut-to-width index :unsigned width) + (cut-to-width base :untagged width nil) + (cut-to-width index :untagged width nil) 'sb!vm::%lea-mod32)) -(define-modular-fun-optimizer %lea ((base index scale disp) :signed :width width) +(define-modular-fun-optimizer %lea ((base index scale disp) :tagged t :width width) (when (and (<= width 30) (constant-lvar-p scale) (constant-lvar-p disp)) - (cut-to-width base :signed width) - (cut-to-width index :signed width) + (cut-to-width base :tagged width t) + (cut-to-width index :tagged width t) 'sb!vm::%lea-smod30)) #+sb-xc-host @@ -1338,7 +1390,7 @@ (:translate %lea-smod30)) ;;; logical operations -(define-modular-fun lognot-mod32 (x) lognot :unsigned 32) +(define-modular-fun lognot-mod32 (x) lognot :untagged nil 32) (define-vop (lognot-mod32/word=>unsigned) (:translate lognot-mod32) (:args (x :scs (unsigned-reg signed-reg unsigned-stack signed-stack) :target r @@ -1361,20 +1413,6 @@ (move r x) (inst not r))) -(define-modular-fun logxor-mod32 (x y) logxor :unsigned 32) -(define-mod-binop (fast-logxor-mod32/word=>unsigned - fast-logxor/unsigned=>unsigned) - logxor-mod32) -(define-mod-binop-c (fast-logxor-mod32-c/word=>unsigned - fast-logxor-c/unsigned=>unsigned) - logxor-mod32) -(define-vop (fast-logxor-mod32/fixnum=>fixnum - fast-logxor/fixnum=>fixnum) - (:translate logxor-mod32)) -(define-vop (fast-logxor-mod32-c/fixnum=>fixnum - fast-logxor-c/fixnum=>fixnum) - (:translate logxor-mod32)) - (define-source-transform logeqv (&rest args) (if (oddp (length args)) `(logxor ,@args) @@ -1404,7 +1442,9 @@ (define-full-reffer bignum-ref * bignum-digits-offset other-pointer-lowtag (unsigned-reg) unsigned-num sb!bignum:%bignum-ref) - +(define-full-reffer+offset bignum-ref-with-offset * + bignum-digits-offset other-pointer-lowtag + (unsigned-reg) unsigned-num sb!bignum:%bignum-ref-with-offset) (define-full-setter bignum-set * bignum-digits-offset other-pointer-lowtag (unsigned-reg) unsigned-num sb!bignum:%bignum-set) @@ -1413,15 +1453,13 @@ (:policy :fast-safe) (:args (digit :scs (unsigned-reg))) (:arg-types unsigned-num) - (:conditional) - (:info target not-p) + (:conditional :ns) (:generator 3 - (inst or digit digit) - (inst jmp (if not-p :s :ns) target))) + (inst or digit digit))) ;;; For add and sub with carry the sc of carry argument is any-reg so -;;; the it may be passed as a fixnum or word and thus may be 0, 1, or +;;; that it may be passed as a fixnum or word and thus may be 0, 1, or ;;; 4. This is easy to deal with and may save a fixnum-word ;;; conversion. (define-vop (add-w/carry) @@ -1443,8 +1481,8 @@ (inst mov carry 0) (inst adc carry carry))) -;;; Note: the borrow is the oppostite of the x86 convention - 1 for no -;;; borrow and 0 for a borrow. +;;; Note: the borrow is 1 for no borrow and 0 for a borrow, the opposite +;;; of the x86 convention. (define-vop (sub-w/borrow) (:translate sb!bignum:%subtract-with-borrow) (:policy :fast-safe) @@ -1459,9 +1497,8 @@ (inst cmp c 1) ; Set the carry flag to 1 if c=0 else to 0 (move result a) (inst sbb result b) - (inst mov borrow 0) - (inst adc borrow borrow) - (inst xor borrow 1))) + (inst mov borrow 1) + (inst sbb borrow 0))) (define-vop (bignum-mult-and-add-3-arg) @@ -1546,7 +1583,7 @@ (:result-types unsigned-num) (:generator 1 (move digit fixnum) - (inst sar digit 2))) + (inst sar digit n-fixnum-tag-bits))) (define-vop (bignum-floor) (:translate sb!bignum:%floor) @@ -1582,7 +1619,7 @@ (:generator 1 (move res digit) (when (sc-is res any-reg control-stack) - (inst shl res 2)))) + (inst shl res n-fixnum-tag-bits)))) (define-vop (digit-ashr) (:translate sb!bignum:%ashr) @@ -1595,11 +1632,25 @@ :load-if (not (and (sc-is result unsigned-stack) (location= digit result))))) (:result-types unsigned-num) - (:generator 1 + (:generator 2 (move result digit) (move ecx count) (inst sar result :cl))) +(define-vop (digit-ashr/c) + (:translate sb!bignum:%ashr) + (:policy :fast-safe) + (:args (digit :scs (unsigned-reg unsigned-stack) :target result)) + (:arg-types unsigned-num (:constant (integer 0 31))) + (:info count) + (:results (result :scs (unsigned-reg) :from (:argument 0) + :load-if (not (and (sc-is result unsigned-stack) + (location= digit result))))) + (:result-types unsigned-num) + (:generator 1 + (move result digit) + (inst sar result count))) + (define-vop (digit-lshr digit-ashr) (:translate sb!bignum:%digit-logical-shift-right) (:generator 1 @@ -1651,10 +1702,7 @@ (:results (y :scs (unsigned-reg) :from (:eval 0))) (:result-types unsigned-num) (:generator 50 - (inst mov k (make-ea :dword :base state - :disp (- (* (+ 2 vector-data-offset) - n-word-bytes) - other-pointer-lowtag))) + (loadw k state (+ 2 vector-data-offset) other-pointer-lowtag) (inst cmp k 624) (inst jmp :ne no-update) (inst mov tmp state) ; The state is passed in EAX. @@ -1663,25 +1711,15 @@ (inst xor k k) NO-UPDATE ;; y = ptgfsr[k++]; - (inst mov y (make-ea :dword :base state :index k :scale 4 - :disp (- (* (+ 3 vector-data-offset) - n-word-bytes) - other-pointer-lowtag))) + (inst mov y (make-ea-for-vector-data state :index k :offset 3)) ;; y ^= (y >> 11); (inst shr y 11) - (inst xor y (make-ea :dword :base state :index k :scale 4 - :disp (- (* (+ 3 vector-data-offset) - n-word-bytes) - other-pointer-lowtag))) + (inst xor y (make-ea-for-vector-data state :index k :offset 3)) ;; y ^= (y << 7) & #x9d2c5680 (inst mov tmp y) (inst inc k) (inst shl tmp 7) - (inst mov (make-ea :dword :base state - :disp (- (* (+ 2 vector-data-offset) - n-word-bytes) - other-pointer-lowtag)) - k) + (storew k state (+ 2 vector-data-offset) other-pointer-lowtag) (inst and tmp #x9d2c5680) (inst xor y tmp) ;; y ^= (y << 15) & #xefc60000