[llvm-dev] Semantics for non-byte-sized stores? (or whenever "store size in bits" is different than "size in bits")

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] Semantics for non-byte-sized stores? (or whenever "store size in bits" is different than "size in bits")

Shawn Webb via llvm-dev
It is possible to ask DataLayout about getTypeSizeInBits and also getTypeStoreSize.

And there is a table showing an example of what it could look like:

  /// Size examples:
  ///
  /// Type        SizeInBits  StoreSizeInBits  AllocSizeInBits[*]
  /// ----        ----------  ---------------  ---------------
  ///  i1            1           8                8
  ///  i8            8           8                8
  ///  i19          19          24               32
  ///  i32          32          32               32
  ///  i100        100         104              128
  ///  i128        128         128              128
  ///  Float        32          32               32
  ///  Double       64          64               64
  ///  X86_FP80     80          80               96
  ///
  /// [*] The alloc size depends on the alignment, and thus on the target.
  ///     These values are for x86-32 linux.


Assume that I have LLVM IR for a union between two types that are mapped to i32 and i19.
And then I have two overlapping stores to this union such as:

  %u = alloca %union
  %u32 = bitcast %union* %u to i32*
  %u19 = bitcast %union* %u to i19*
  store i32 -1, i32* %u32
  store i19  0, i19* %u19
  %result = load i32, i32* %u32

How many bits are guaranteed to be zero in %result?
How many bits are guaranteed to be one in %result?

To be more specific:

 a) Is the i19 store defined as only writing 19 bits (even if store size is larger, so it will become a load-modify-write after legalization)?

 b) Is the i19 store defined as touching 24 bits, so we get 5 bits that are undefined (or always zero-extended/sign-extended)?

 c) Is this target specific (and nothing that opt should know about)?

I've got a feeling that the I get different results if feeding the above IR directly into llc, or if I pass it through "opt -dse" first.
(and that might be OK if some bits are undefined in %result)

The actual problem that lead me into these questions is that DeadStoreElimination asserts/miscompiles (depending on endianness) when having something like this instead (partial overwrite of a store that isn't byte-sized):

  %u = alloca %union
  %u32 = bitcast %union* %u to i32*
  %u19 = bitcast %union* %u to i19*
  %u16 = bitcast %union* %u to i16*
  store i19  0, i19* %u19
  store i16 -1, i16* %u16
  %result = load i32, i32* %u32

I'm planning to write a PR (and make a bugfix) but got uncertain about what the correct behavior would be here.

Yet another question is if the i19 value is guaranteed to be placed in the least significant end of the 3 bytes that are tainted by the store?

/Björn (bjope)
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Semantics for non-byte-sized stores? (or whenever "store size in bits" is different than "size in bits")

Shawn Webb via llvm-dev
Comments inline

> -----Original Message-----
> From: llvm-dev <[hidden email]> On Behalf Of Björn
> Pettersson A via llvm-dev
> Sent: Friday, May 17, 2019 7:34 AM
> To: [hidden email]
> Subject: [EXT] [llvm-dev] Semantics for non-byte-sized stores? (or whenever
> "store size in bits" is different than "size in bits")
>
> Assume that I have LLVM IR for a union between two types that are mapped to
> i32 and i19.
> And then I have two overlapping stores to this union such as:
>
>   %u = alloca %union
>   %u32 = bitcast %union* %u to i32*
>   %u19 = bitcast %union* %u to i19*
>   store i32 -1, i32* %u32
>   store i19  0, i19* %u19
>   %result = load i32, i32* %u32
>
> How many bits are guaranteed to be zero in %result?

According to LangRef, 19.  In practice, 24.

> How many bits are guaranteed to be one in %result?

8.

> To be more specific:
>
>  a) Is the i19 store defined as only writing 19 bits (even if store size is larger, so it
> will become a load-modify-write after legalization)?

Loads and stores only operate on a whole number of bytes, determined by getTypeStoreSize.  So 24 bits are stored, and no bits are loaded.
 
>  b) Is the i19 store defined as touching 24 bits, so we get 5 bits that are
> undefined (or always zero-extended/sign-extended)?

LangRef says the 5 bits are determined by the target: an i19 load is only defined if the value was constructed using an i19 store.  But in practice, SelectionDAG legalization always zero-extends stores, and loads assume the value is zero-extended.

>   %u = alloca %union
>   %u32 = bitcast %union* %u to i32*
>   %u19 = bitcast %union* %u to i19*
>   %u16 = bitcast %union* %u to i16*
>   store i19  0, i19* %u19
>   store i16 -1, i16* %u16
>   %result = load i32, i32* %u32

The first store stores three bytes, the second store stores two bytes, the load loads four bytes.  So there's one byte of data from the first store, and two bytes from the second.

> Yet another question is if the i19 value is guaranteed to be placed in the least
> significant end of the 3 bytes that are tainted by the store?

IIRC, this isn't formally specified in LangRef, but in practice an i19 is laid out as if it were zero-extended to i24.  I'd suggest bailing out of any transform that would care, though.

I've been considering formalizing the current SelectionDAG behavior in LangRef, but I haven't written a patch.

-Eli
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Semantics for non-byte-sized stores? (or whenever "store size in bits" is different than "size in bits")

Shawn Webb via llvm-dev
Thanks Eli!

I was looking for the information in the LangRef, but I guess I was stupid enough not to read the semantics for load/store (I thought that I would find the information in the earlier parts before the description of operations).

Afaict we can end up with different kinds of problems in DeadStoreElimination today.
Worst case scenario includes miscompiles.
So, I wrote a PR here:
  https://bugs.llvm.org/show_bug.cgi?id=41949



One part in the LangRef baffled me:

"When loading a value of a type like ``i20`` with a size that is not an integral number
of bytes, the result is undefined if the value was not originally
written using a store of the same type."

I think that when using unions it is common that there could be different types
used in the store and the load. Example first using two separate i16 stores to
store an { i16, i16 } structure, followed by an i32 load that loads all the 32 bits
in one single operation.

  %a = alloca i32
  %b = bitcast i32* %a to { i16, i16 }*
  %b0 = getelementptr inbounds { i16, i16 }, { i16, i16 }* %b, i32 0, i32 0
  %b1 = getelementptr inbounds { i16, i16 }, { i16, i16 }* %b, i32 0, i32 1
  store i16 10, i16* %b0
  store i16 20, i16* %b1
  ...
  %x = load i32, i32* %a

Is the result of the load really undefined for such IR?
(Or maybe this is something that would need to be formalized as well?)

/Björn

> -----Original Message-----
> From: Eli Friedman <[hidden email]>
> Sent: den 17 maj 2019 21:09
> To: Björn Pettersson A <[hidden email]>; llvm-dev <llvm-
> [hidden email]>
> Subject: RE: [llvm-dev] Semantics for non-byte-sized stores? (or whenever
> "store size in bits" is different than "size in bits")
>
> Comments inline
>
> > -----Original Message-----
> > From: llvm-dev <[hidden email]> On Behalf Of Björn
> > Pettersson A via llvm-dev
> > Sent: Friday, May 17, 2019 7:34 AM
> > To: [hidden email]
> > Subject: [EXT] [llvm-dev] Semantics for non-byte-sized stores? (or
> whenever
> > "store size in bits" is different than "size in bits")
> >
> > Assume that I have LLVM IR for a union between two types that are mapped
> to
> > i32 and i19.
> > And then I have two overlapping stores to this union such as:
> >
> >   %u = alloca %union
> >   %u32 = bitcast %union* %u to i32*
> >   %u19 = bitcast %union* %u to i19*
> >   store i32 -1, i32* %u32
> >   store i19  0, i19* %u19
> >   %result = load i32, i32* %u32
> >
> > How many bits are guaranteed to be zero in %result?
>
> According to LangRef, 19.  In practice, 24.
>
> > How many bits are guaranteed to be one in %result?
>
> 8.
>
> > To be more specific:
> >
> >  a) Is the i19 store defined as only writing 19 bits (even if store size
> is larger, so it
> > will become a load-modify-write after legalization)?
>
> Loads and stores only operate on a whole number of bytes, determined by
> getTypeStoreSize.  So 24 bits are stored, and no bits are loaded.
>
> >  b) Is the i19 store defined as touching 24 bits, so we get 5 bits that
> are
> > undefined (or always zero-extended/sign-extended)?
>
> LangRef says the 5 bits are determined by the target: an i19 load is only
> defined if the value was constructed using an i19 store.  But in practice,
> SelectionDAG legalization always zero-extends stores, and loads assume the
> value is zero-extended.
>
> >   %u = alloca %union
> >   %u32 = bitcast %union* %u to i32*
> >   %u19 = bitcast %union* %u to i19*
> >   %u16 = bitcast %union* %u to i16*
> >   store i19  0, i19* %u19
> >   store i16 -1, i16* %u16
> >   %result = load i32, i32* %u32
>
> The first store stores three bytes, the second store stores two bytes, the
> load loads four bytes.  So there's one byte of data from the first store,
> and two bytes from the second.
>
> > Yet another question is if the i19 value is guaranteed to be placed in
> the least
> > significant end of the 3 bytes that are tainted by the store?
>
> IIRC, this isn't formally specified in LangRef, but in practice an i19 is
> laid out as if it were zero-extended to i24.  I'd suggest bailing out of
> any transform that would care, though.
>
> I've been considering formalizing the current SelectionDAG behavior in
> LangRef, but I haven't written a patch.
>
> -Eli
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Semantics for non-byte-sized stores? (or whenever "store size in bits" is different than "size in bits")

Shawn Webb via llvm-dev
Thanks for filing a clear bug.

For the union example, the LangRef rule you cite isn't supposed to mean you can't copy the bits of a union.  It's basically just an optimization for non-integral loads: the backend isn't required to explicitly mask away non-value bits of the load.  So for example, you can't store i8 -1 to an address, then load it as an i1.

-Eli

> -----Original Message-----
> From: Björn Pettersson A <[hidden email]>
> Sent: Monday, May 20, 2019 11:52 AM
> To: Eli Friedman <[hidden email]>; llvm-dev <[hidden email]>
> Subject: [EXT] RE: [llvm-dev] Semantics for non-byte-sized stores? (or whenever
> "store size in bits" is different than "size in bits")
>
> Thanks Eli!
>
> I was looking for the information in the LangRef, but I guess I was stupid enough
> not to read the semantics for load/store (I thought that I would find the
> information in the earlier parts before the description of operations).
>
> Afaict we can end up with different kinds of problems in DeadStoreElimination
> today.
> Worst case scenario includes miscompiles.
> So, I wrote a PR here:
>   https://bugs.llvm.org/show_bug.cgi?id=41949
>
>
>
> One part in the LangRef baffled me:
>
> "When loading a value of a type like ``i20`` with a size that is not an integral
> number
> of bytes, the result is undefined if the value was not originally
> written using a store of the same type."
>
> I think that when using unions it is common that there could be different types
> used in the store and the load. Example first using two separate i16 stores to
> store an { i16, i16 } structure, followed by an i32 load that loads all the 32 bits
> in one single operation.
>
>   %a = alloca i32
>   %b = bitcast i32* %a to { i16, i16 }*
>   %b0 = getelementptr inbounds { i16, i16 }, { i16, i16 }* %b, i32 0, i32 0
>   %b1 = getelementptr inbounds { i16, i16 }, { i16, i16 }* %b, i32 0, i32 1
>   store i16 10, i16* %b0
>   store i16 20, i16* %b1
>   ...
>   %x = load i32, i32* %a
>
> Is the result of the load really undefined for such IR?
> (Or maybe this is something that would need to be formalized as well?)
>
> /Björn
>
> > -----Original Message-----
> > From: Eli Friedman <[hidden email]>
> > Sent: den 17 maj 2019 21:09
> > To: Björn Pettersson A <[hidden email]>; llvm-dev <llvm-
> > [hidden email]>
> > Subject: RE: [llvm-dev] Semantics for non-byte-sized stores? (or whenever
> > "store size in bits" is different than "size in bits")
> >
> > Comments inline
> >
> > > -----Original Message-----
> > > From: llvm-dev <[hidden email]> On Behalf Of Björn
> > > Pettersson A via llvm-dev
> > > Sent: Friday, May 17, 2019 7:34 AM
> > > To: [hidden email]
> > > Subject: [EXT] [llvm-dev] Semantics for non-byte-sized stores? (or
> > whenever
> > > "store size in bits" is different than "size in bits")
> > >
> > > Assume that I have LLVM IR for a union between two types that are mapped
> > to
> > > i32 and i19.
> > > And then I have two overlapping stores to this union such as:
> > >
> > >   %u = alloca %union
> > >   %u32 = bitcast %union* %u to i32*
> > >   %u19 = bitcast %union* %u to i19*
> > >   store i32 -1, i32* %u32
> > >   store i19  0, i19* %u19
> > >   %result = load i32, i32* %u32
> > >
> > > How many bits are guaranteed to be zero in %result?
> >
> > According to LangRef, 19.  In practice, 24.
> >
> > > How many bits are guaranteed to be one in %result?
> >
> > 8.
> >
> > > To be more specific:
> > >
> > >  a) Is the i19 store defined as only writing 19 bits (even if store size
> > is larger, so it
> > > will become a load-modify-write after legalization)?
> >
> > Loads and stores only operate on a whole number of bytes, determined by
> > getTypeStoreSize.  So 24 bits are stored, and no bits are loaded.
> >
> > >  b) Is the i19 store defined as touching 24 bits, so we get 5 bits that
> > are
> > > undefined (or always zero-extended/sign-extended)?
> >
> > LangRef says the 5 bits are determined by the target: an i19 load is only
> > defined if the value was constructed using an i19 store.  But in practice,
> > SelectionDAG legalization always zero-extends stores, and loads assume the
> > value is zero-extended.
> >
> > >   %u = alloca %union
> > >   %u32 = bitcast %union* %u to i32*
> > >   %u19 = bitcast %union* %u to i19*
> > >   %u16 = bitcast %union* %u to i16*
> > >   store i19  0, i19* %u19
> > >   store i16 -1, i16* %u16
> > >   %result = load i32, i32* %u32
> >
> > The first store stores three bytes, the second store stores two bytes, the
> > load loads four bytes.  So there's one byte of data from the first store,
> > and two bytes from the second.
> >
> > > Yet another question is if the i19 value is guaranteed to be placed in
> > the least
> > > significant end of the 3 bytes that are tainted by the store?
> >
> > IIRC, this isn't formally specified in LangRef, but in practice an i19 is
> > laid out as if it were zero-extended to i24.  I'd suggest bailing out of
> > any transform that would care, though.
> >
> > I've been considering formalizing the current SelectionDAG behavior in
> > LangRef, but I haven't written a patch.
> >
> > -Eli
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev