[Sbcl-devel] Bad effect of FOLD-INDEX-ADDRESSING

[Douglas Katzman]

Hi developers,

Below is a minimized version of some code which elicits a compiler bug preventing access to half of this constant array. 

-31 to -1 are good arguments to FOO - they should index the zeroth element of the array onward.

* (defun compute-my-array () (make-array 63))

* (defun foo (v)                                                                                                                        

  (if (typep v '(integer -31 31))                                                                                                       

      (let ((index (+ v 31)))                                                                                                           

        (aref #.(compute-my-array) index))                                                                                              

      (error "Bad val: ~S" v)))

* (foo -31)

debugger invoked on a TYPE-ERROR in thread

#<THREAD "main thread" RUNNING {10029F94B3}>:

  The value -31 is not of type (MOD 4611686018427387901).

The disassembly is illuminating:

; disassembly for FOO

; 02AB99EC:       F6C301           TEST BL, 1                 ; no-arg-parsing entry point

;      9EF:       7543             JNE L1

;      9F1:       488BCB           MOV RCX, RBX

;      9F4:       4883F9C2         CMP RCX, -62

;      9F8:       7C3A             JL L1

;      9FA:       488BCB           MOV RCX, RBX

;      9FD:       4883F93E         CMP RCX, 62

;      A01:       7F31             JNLE L1

;      A03:       488BCB           MOV RCX, RBX

;      A06:       4883F900         CMP RCX, 0

;      A0A:       7C18             JL L0

;      A0C:       488BCB           MOV RCX, RBX

;      A0F:       488B056AFFFFFF   MOV RAX, [RIP-150]         ; #(0 0 0 0 ...)

;      A16:       488B9488F9000000 MOV RDX, [RAX+RCX*4+249]

The optimization of using the SIB addressing mode to fold in the constant offset of 31 has not informed the bound check that the valid range of the index (register RCX) is -31 to 31 - and the explicit typep check has already concluded that that it is exactly in that range.  The "CMP RCX, 0 / JL L0" is bogus.  (L0 is the label for the error trap)

I haven't yet checked how this affects SVREF in the latest code which bypasses some parts of the AREF transforms.

[Nathan Froyd]

The problem here is that the AREF gets converted to:

(SB-KERNEL:DATA-VECTOR-REF-WITH-OFFSET <array> V <offset>)

and the compiler doesn't know that V's type (which has been asserted
to be an array index) can actually vary based on the value of OFFSET
(31 in this case).

I think the right thing to do here is a DEFOPTIMIZER for
DATA-VECTOR-REF-WITH-OFFSET that looks something like:

(in-package :sb-c)
(defoptimizer (data-vector-ref-with-offset optimizer) ((array index
offset) node)
(let ((did-something nil))
(do-uses (n index)
(when (and (cast-p n)
(eq (cast-type-check n) t)
(constant-lvar-p offset)
(numeric-type-p (cast-asserted-type n))
(numeric-type-p (cast-type-to-check n)))
(let* ((value (lvar-value offset))
(upper-array-limit (1- sb!xc:array-dimension-limit))
(actual-index-type (modified-numeric-type (cast-type-to-check n)
:low (- value)
:high (min upper-array-limit
(- upper-array-limit value)))))
(setf (cast-asserted-type n) actual-index-type
(cast-type-to-check n) actual-index-type
(cast-reoptimize n) t
did-something t))))
did-something))

But this is getting into parts of IR1 that I don't know very well,
hence the overzealous checking. I haven't tried bootstrapping with
this, but it does have the expected effect on the assembly:

; 0621799C: 40F6C601 TEST SIL, 1 ;
no-arg-parsing entry point
; A0: 752A JNE L0
; A2: 488BCE MOV RCX, RSI
; A5: 4883F9C2 CMP RCX, -62
; A9: 7C21 JL L0
; AB: 488BCE MOV RCX, RSI
; AE: 4883F93E CMP RCX, 62
; B2: 7F18 JNLE L0
; B4: 488BCE MOV RCX, RSI
; B7: 488B0572FFFFFF MOV RAX, [RIP-142] ; #(0 0 0 0
; ...)
; BE: 488B9488F9000000 MOV RDX, [RAX+RCX*4+249]

Those more experienced in IR1...does the above look plausible? Are
there better ways to express what we want to do here?

-Nathan

> ------------------------------------------------------------------------------
> Learn Graph Databases - Download FREE O'Reilly Book
> "Graph Databases" is the definitive new guide to graph databases and
> their applications. This 200-page book is written by three acclaimed
> leaders in the field. The early access version is available now.
> Download your free book today! http://p.sf.net/sfu/neotech_d2d_may
> _______________________________________________
> Sbcl-devel mailing list
> Sbcl-...@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/sbcl-devel
>

------------------------------------------------------------------------------
Learn Graph Databases - Download FREE O'Reilly Book
"Graph Databases" is the definitive new guide to graph databases and
their applications. This 200-page book is written by three acclaimed
leaders in the field. The early access version is available now.
Download your free book today! http://p.sf.net/sfu/neotech_d2d_may
_______________________________________________
Sbcl-devel mailing list
Sbcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel

[Paul Khuong]

Nathan Froyd wrote:
> The problem here is that the AREF gets converted to:
>
> (SB-KERNEL:DATA-VECTOR-REF-WITH-OFFSET<array> V<offset>)
>
> and the compiler doesn't know that V's type (which has been asserted
> to be an array index) can actually vary based on the value of OFFSET
> (31 in this case).
>
> I think the right thing to do here is a DEFOPTIMIZER for
> DATA-VECTOR-REF-WITH-OFFSET that looks something like:

[frob any cast to take the offset into account ...]

That doesn't look right: other transforms might already have fired based
on the asserted INDEX type.

I think what we should do is:
1. let DATA-VECTOR-FOO-WITH-OFFSET accept any signed-word as input;
2. insert range checks if necessary.

For 2, I think the best way would be to determine at IR2-conversion-time
whether we need to check bounds. It's probably easiest to use an
IR2-CONVERT optimized to splice in something like a
DATA-VECTOR-FOO-WITH-OFFSET/CHECK VOP: doing it all in a single VOP
makes it easier to check for overflow (if necessary) and check bounds.

Paul Khuong

[Paul Khuong]

Paul Khuong wrote:
> Nathan Froyd wrote:
>> The problem here is that the AREF gets converted to:
>>
>> (SB-KERNEL:DATA-VECTOR-REF-WITH-OFFSET<array> V<offset>)
>>
>> and the compiler doesn't know that V's type (which has been asserted
>> to be an array index) can actually vary based on the value of OFFSET
>> (31 in this case).

[...]

>
> [frob any cast to take the offset into account ...]
>
> That doesn't look right: other transforms might already have fired based
> on the asserted INDEX type.
>
> I think what we should do is:
> 1. let DATA-VECTOR-FOO-WITH-OFFSET accept any signed-word as input;
> 2. insert range checks if necessary.

I played with this for a while, and I think it's actually simpler: all
the *-with-offset VOPs accept fixnums for the index argument. Moreover,
any range checking is done before hitting *-with-offset, so if we can
fold some indices, the original index was statically known to be OK. So,
AFAICT, the right fix is to adjust the defknowns to allow arbitrary
fixnum indices, and to only fold-index-addressing when the new index
argument would still be a fixnum (otherwise we won't be able to
translate the form). There's another issue in fold-index-addressing: in
the last argument to sb!vm::foldable-constant-offset-p, the arguments
for FUNC are flipped... that's probably the reason we don't have more
reports of failure to translate data-vector-ref-with-offset.

Paul Khuong

------------------------------------------------------------------------------
Try New Relic Now & We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service
that delivers powerful full stack analytics. Optimize and monitor your
browser, app, & servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may