1 ;;;; predicate VOPs for the x86 VM
3 ;;;; This software is part of the SBCL system. See the README file for
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.
16 ;;; The unconditional branch, emitted when we can't drop through to the desired
17 ;;; destination. Dest is the continuation we transfer control to.
24 ;;;; Generic conditional VOPs
26 ;;; The generic conditional branch, emitted immediately after test
27 ;;; VOPs that only set flags.
29 ;;; FLAGS is a list of condition descriptors. If the first descriptor
30 ;;; is CL:NOT, the test was true if all the remaining conditions are
31 ;;; false. Otherwise, the test was true if any of the conditions is.
33 ;;; NOT-P flips the meaning of the test, as with regular :CONDITIONAL
34 ;;; VOP. If NOT-P is true, the code must branch to dest if the test was
35 ;;; false. Otherwise, the code must branch to dest if the test was true.
37 (define-vop (branch-if)
38 (:info dest not-p flags
)
41 (let ((flags (conditional-flags-flags flags
)))
43 ;; Specifying multiple flags is an extremely confusing convention that supports
44 ;; floating-point inequality tests utilizing the flag register in an unusual way,
45 ;; as documented in the COMISS and COMISD instructions:
46 ;; "the ZF, PF, and CF flags in the EFLAGS register according
47 ;; to the result (unordered, greater than, less than, or equal)"
48 ;; I think it would have been better if, instead of allowing more than one flag,
49 ;; we passed in a pseudo-condition code such as ':sf<=' and deferred to this vop
50 ;; to interpret the abstract condition in terms of how to CPU sets the bits
51 ;; in those particular instructions.
52 ;; Note that other architectures allow only 1 flag in branch-if, if it works at all.
53 ;; Enable this assertion if you need to sanity-check the preceding claim.
54 ;; There's really no "dynamic" reason for it to fail.
56 (aver (memq (vop-name (sb-c::vop-prev vop
))
57 '(<single-float
<double-float
<=single-float
<=double-float
58 >single-float
>double-float
>=single-float
>=double-float
59 =/single-float
=/double-float
))))
60 (when (eq (car flags
) 'not
)
62 (setf not-p
(not not-p
)))
63 (cond ((null (rest flags
))
66 (negate-condition (first flags
))
70 (let ((not-lab (gen-label))
71 (last (car (last flags
))))
72 (dolist (flag (butlast flags
))
73 (inst jmp flag not-lab
))
74 (inst jmp
(negate-condition last
) dest
)
75 (emit-label not-lab
)))
78 (inst jmp flag dest
)))))))
80 (define-vop (jump-table)
81 (:args
(index :scs
(signed-reg unsigned-reg any-reg
)
83 (:info targets otherwise min max
)
84 (:temporary
(:sc any-reg
:from
(:argument
0)) offset
)
85 (:temporary
(:sc unsigned-reg
) table
)
87 (let ((fixnump (sc-is index any-reg
)))
94 (let ((byte-disp (- (* min n-word-bytes
))))
95 (if (and (not otherwise
)
96 (typep byte-disp
'(signed-byte 32)))
98 (let ((diff (- (fix min
))))
99 (unless (typep diff
'(signed-byte 32))
100 (inst mov table diff
)
102 (cond ((location= offset index
)
103 (inst add offset diff
))
105 (inst lea offset
(ea diff index
))
106 (setf index offset
)))))))
108 (inst cmp index
(fix (- max min
)))
109 (inst jmp
:a otherwise
))
110 (inst lea table
(register-inline-constant :jump-table targets
))
112 (ea disp table index
(if fixnump
4 8))
113 (ea table index
(if fixnump
4 8)))))))))
115 (defun convert-conditional-move-p (dst-tn)
117 ((descriptor-reg any-reg
)
123 ;; FIXME: Can't use CMOV with byte registers, and characters live
124 ;; in such outside of unicode builds. A better solution then just
125 ;; disabling MOVE-IF/CHAR should be possible, though.
133 (define-vop (move-if)
134 (:args
(then) (else))
137 (:temporary
(:sc unsigned-reg
) temp
)
139 (let* ((flags (conditional-flags-flags flags
))
140 (not-p (eq (first flags
) 'not
))
142 (when not-p
(pop flags
))
143 (when (location= res then
)
145 (setf not-p
(not not-p
)))
146 (flet ((load-immediate (dst constant-tn
147 &optional
(sc-reg dst
))
148 (let ((encode (encode-value-if-immediate constant-tn
149 (sc-is sc-reg any-reg descriptor-reg
))))
150 (if (typep encode
'(unsigned-byte 31))
154 ;; Can't use ZEROIZE, since XOR will affect the flags.
155 (inst mov dst encode
))))
156 (cond ((null (rest flags
))
157 (cond ((sc-is else immediate
)
158 (load-immediate res else
))
162 (cond ((sc-is then immediate
)
163 (load-immediate temp then res
)
167 (inst cmov size
(if not-p
168 (negate-condition (first flags
))
173 (cond ((sc-is then immediate
)
174 (when (location= else res
)
177 (load-immediate res then
))
178 ((location= else res
)
184 (when (sc-is else immediate
)
185 (load-immediate temp else res
)
188 (inst cmov flag res else
)))
190 (if (sc-is else immediate
)
191 (load-immediate res else
)
193 (when (sc-is then immediate
)
194 (load-immediate temp then res
)
197 (inst cmov flag res then
))))))))
199 (macrolet ((def-move-if (name type reg stack
)
200 `(define-vop (,name move-if
)
201 (:args
(then :scs
(immediate ,@(ensure-list reg
) ,stack
) :to
:eval
202 :load-if
(not (or (sc-is then immediate
)
203 (and (sc-is then
,stack
)
204 (not (location= else res
))))))
205 (else :scs
(immediate ,@(ensure-list reg
) ,stack
) :target res
206 :load-if
(not (sc-is else immediate
,stack
))))
207 (:arg-types
,type
,type
)
208 (:results
(res :scs
,(ensure-list reg
)))
209 (:result-types
,type
))))
210 (def-move-if move-if
/t t
(descriptor-reg any-reg
) control-stack
)
211 (def-move-if move-if
/unsigned unsigned-num unsigned-reg unsigned-stack
)
212 (def-move-if move-if
/signed signed-num signed-reg signed-stack
)
213 ;; FIXME: See convert-conditional-move-p above.
215 (def-move-if move-if
/char character character-reg character-stack
)
216 (def-move-if move-if
/sap system-area-pointer sap-reg sap-stack
))
218 ;;; Return a hint about how to calculate the answer from X,Y and flags.
219 ;;; Return NIL to give up.
220 (defun computable-from-flags-p (res x y flags
)
221 ;; TODO: handle unsigned-reg
222 (unless (and (singleton-p flags
)
223 (sc-is res sb-vm
::any-reg sb-vm
::descriptor-reg
))
224 (return-from computable-from-flags-p nil
))
225 ;; There are plenty more algebraic transforms possible,
226 ;; but this picks off some very common cases.
227 (flet ((try-shift (x y
)
229 (typep y
'(and fixnum unsigned-byte
))
232 (try-add (x y
) ; commutative
233 ;; (signed-byte 32) is gonna work for sure.
234 ;; Other things might too, but "perfect is the enemy of good".
235 ;; The constant in LEA is pre-fixnumized.
236 ;; Post-fixnumizing instead would open up a few more possibilities.
239 (typep (fixnumize x
) '(signed-byte 32))
240 (typep (fixnumize y
) '(signed-byte 32))
241 (member (abs (fixnumize (- x y
))) '(2 4 8))
243 (or #+sb-thread
(or (and (eq x t
) (eq y nil
) 'boolean
)
244 (and (eq x nil
) (eq y t
) 'boolean
))
249 (define-vop (compute-from-flags)
250 (:args
(x-tn :scs
(immediate constant
))
251 (y-tn :scs
(immediate constant
)))
252 (:results
(res :scs
(any-reg descriptor-reg
)))
255 (let* ((x (tn-value x-tn
))
257 #+gs-seg
(thread-tn nil
)
258 (hint (computable-from-flags-p res x y flags
))
262 ;; FIXNUMP -> {T,NIL} could be special-cased, reducing the instruction count by
263 ;; 1 or 2 depending on whether the argument and result are in the same register.
264 ;; Best case would be "AND :dword res, arg, 1 ; MOV res, [ea]".
266 ;; T is at the lower address, so to pick it out we need index=0
267 ;; which makes the condition in (IF BIT T NIL) often flipped.
268 (setq flag
(negate-condition flag
)))
270 (inst movzx
'(:byte
:dword
) res res
)
272 (ea thread-segment-reg
(ash thread-t-nil-constants-slot word-shift
)
276 (setq flag
(negate-condition flag
)))
277 (let ((bit (1- (integer-length (fixnumize (logior x y
))))))
279 (inst movzx
'(:byte
:dword
) res res
)
280 (inst shl
(if (> bit
31) :qword
:dword
) res bit
)))
282 (let* ((x (fixnumize x
))
285 (delta (abs (- x y
)))
286 ;; [RES+RES+n] encodes more compactly than [RES*2+n]
287 (ea (if (= delta
2) (ea min res res
) (ea min nil res delta
))))
289 (setq flag
(negate-condition flag
)))
291 (inst movzx
'(:byte
:dword
) res res
)
292 ;; Retain bit 63... if either is negative
293 (inst lea
(if (or (minusp x
) (minusp y
)) :qword
:dword
) res ea
)))))))
295 ;;;; conditional VOPs
297 ;;; Note: a constant-tn is allowed in CMP; it uses an EA displacement,
298 ;;; not immediate data.
300 (:args
(x :scs
(any-reg descriptor-reg control-stack
))
301 (y :scs
(any-reg descriptor-reg control-stack immediate constant
)))
306 (:temporary
(:sc unsigned-reg
) temp
)
310 (inst cmp x
(cond ((sc-is x descriptor-reg any-reg
) y
)
311 (t (inst mov temp y
) temp
))))
313 (let* ((value (encode-value-if-immediate y
))
314 (immediate (plausible-signed-imm32-operand-p value
)))
315 (when (and (null (tn-value y
)) (tn-ref-type x-tn-ref
))
316 ;; if the complement of X's type with respect to type NULL can't
317 ;; be a cons, then we don't need a 4-byte comparison against NIL.
318 ;; It suffices to test the low byte. Similar logic could pertain to many
319 ;; other type tests, e.g. STRINGP on known (OR INSTANCE STRING)
320 ;; could skip the widetag test.
321 ;; I'm starting to wonder if it would be better to expose the lowtag/widetag
322 ;; tests in IR1 as an AND expression so that type inference can remove what's
323 ;; possible to deduce. The we just need a way to efficiently recombine
324 ;; the AND back to one vop where we can. "selection DAG, anyone?"
325 (when (not (types-equal-or-intersect
326 (type-difference (tn-ref-type x-tn-ref
) (specifier-type 'null
))
327 (specifier-type 'cons
)))
328 (inst cmp
:byte x
(logand nil-value
#xff
))
329 (return-from if-eq
)))
330 (cond ((fixup-p value
) ; immobile object
332 ((and (zerop value
) (sc-is x any-reg descriptor-reg
))
335 (inst cmp x immediate
))
336 ((not (sc-is x control-stack
))
337 (inst cmp x
(constantize value
)))
339 (inst mov temp value
)
340 (inst cmp x temp
)))))
341 ((and (sc-is x control-stack
) (sc-is y control-stack
))
347 ;; The template above is a very good fallback for the generic
348 ;; case. However, it is sometimes possible to perform unboxed
349 ;; comparisons. Repurpose char= and eql templates here, instead
350 ;; of forcing values to be boxed and then compared.
352 ;; We only weaken EQL => EQ for characters and fixnums, and detect
353 ;; when types definitely mismatch. No need to import other EQL
354 ;; VOPs (e.g. floats).
355 (macrolet ((def (eq-name eql-name cost
)
356 `(define-vop (,eq-name
,eql-name
)
358 (:variant-cost
,cost
))))
359 (def fast-if-eq-character fast-char
=/character
3)
360 (def fast-if-eq-character
/c fast-char
=/character
/c
2)
361 (def fast-if-eq-fixnum fast-eql
/fixnum
3)
362 (def fast-if-eq-fixnum
/c fast-eql-c
/fixnum
2)
363 (def fast-if-eq-signed fast-if-eql
/signed
5)
364 (def fast-if-eq-signed
/c fast-if-eql-c
/signed
4)
365 (def fast-if-eq-unsigned fast-if-eql
/unsigned
5)
366 (def fast-if-eq-unsigned
/c fast-if-eql-c
/unsigned
4))
368 (define-vop (%instance-ref-eq
)
369 (:args
(instance :scs
(descriptor-reg))
370 (x :scs
(descriptor-reg any-reg
)
371 :load-if
(or (not (sc-is x immediate
))
374 (not (signed-byte #.
(- 32 n-fixnum-tag-bits
))))))))
375 (:arg-types
* (:constant
(unsigned-byte 16)) *)
377 (:translate %instance-ref-eq
)
382 (ea (+ (- instance-pointer-lowtag
)
383 (ash (+ slot instance-slots-offset
) word-shift
))
385 (encode-value-if-immediate x
))))
387 ;;; See comment below about ASSUMPTIONS
388 (eval-when (:compile-toplevel
)
389 (assert (eql other-pointer-lowtag
#b1111
))
390 ;; This is also assumed in src/runtime/x86-64-assem.S
391 (assert (eql (min bignum-widetag ratio-widetag single-float-widetag double-float-widetag
392 complex-rational-widetag complex-single-float-widetag complex-double-float-widetag
)
394 (assert (eql (max bignum-widetag ratio-widetag single-float-widetag double-float-widetag
395 complex-rational-widetag complex-single-float-widetag complex-double-float-widetag
)
396 complex-double-float-widetag
)))
398 ;;; Most uses of EQL are transformed into a non-generic form, but when we need
399 ;;; the general form, it's possible to make it nearly as efficient as EQ.
400 ;;; I think it's worth the extra 25 bytes or so per call site versus just
401 ;;; punting to an assembly routine always.
403 (:args
(x :scs
(any-reg descriptor-reg
) :target rdi
)
404 (y :scs
(any-reg descriptor-reg
) :target rsi
))
405 (:arg-refs x-ref y-ref
)
409 (:temporary
(:sc unsigned-reg
:offset rdi-offset
:from
(:argument
0)) rdi
)
410 (:temporary
(:sc unsigned-reg
:offset rsi-offset
:from
(:argument
1)) rsi
)
411 (:temporary
(:sc unsigned-reg
:offset rax-offset
) rax
)
412 (:temporary
(:sc unsigned-reg
:offset r11-offset
) asm-temp
)
417 (inst jmp
:e done
) ; affirmative
418 (let ((x-ratiop (csubtypep (tn-ref-type x-ref
) (specifier-type 'ratio
)))
419 (y-ratiop (csubtypep (tn-ref-type y-ref
) (specifier-type 'ratio
))))
420 (cond ((and x-ratiop y-ratiop
)
423 (invoke-asm-routine 'call
'eql-ratio vop
))
424 ((or x-ratiop y-ratiop
)
425 (let ((check (if x-ratiop
428 (%lea-for-lowtag-test rax check other-pointer-lowtag
)
429 (inst test
:byte rax other-pointer-lowtag
)
431 (inst cmp
:byte
(ea -
15 check
) ratio-widetag
)
435 (invoke-asm-routine 'call
'eql-ratio vop
))
437 ;; If they are not both OTHER-POINTER objects, return false.
438 ;; ASSUMPTION: other-pointer-lowtag = #b1111
439 ;; This ANDing trick would be wrong if, e.g., the OTHER-POINTER tag
440 ;; were #b0011 and the two inputs had lowtags #b0111 and #b1011
441 ;; which when ANDed look like #b0011.
442 ;; We use :BYTE rather than :DWORD here because byte-sized
443 ;; operations on the accumulator encode more compactly.
444 (inst mov
:byte rax x
)
445 (inst and
:byte rax y
) ; now AL = #x_F only if both lowtags were #xF
446 (inst not
:byte rax
) ; now AL = #x_0 only if it was #x_F
447 (inst and
:byte rax
#b00001111
) ; will be all 0 if ok
448 (inst jmp
:ne done
) ; negative
450 ;; If the widetags are not the same, return false.
451 ;; Using a :dword compare gets us the bignum length check almost for free
452 ;; unless the length's representation requires more 4 bytes.
453 ;; I bet nobody would mind if MAXIMUM-BIGNUM-LENGTH were #xFFFFFF.
454 (inst mov
:dword rax
(ea (- other-pointer-lowtag
) x
))
455 (inst cmp
:dword rax
(ea (- other-pointer-lowtag
) y
))
456 (inst jmp
:ne done
) ; negative
458 ;; If not a numeric widetag, return false. See ASSUMPTIONS re widetag order.
459 (inst sub
:byte rax bignum-widetag
)
460 (inst cmp
:byte rax
(- complex-double-float-widetag bignum-widetag
))
461 ;; "above" means CF=0 and ZF=0 so we're returning the right thing here
463 ;; The hand-written assembly code receives args in the C arg registers.
464 ;; It also receives AL holding the biased down widetag.
465 ;; Anything else it needs will be callee-saved.
466 (move rdi x
) ; load the C call args
468 (invoke-asm-routine 'call
'generic-eql vop
))))