BasicAliasAnalysis and out-of-bound GEP indices

Hi!

While investigating into the PR1782 I spent some time analyzing
BasicAliasAnalysis.cpp. While the mentioned problem should be fixed now
(I hope), I have discovered some other possibilities for a bug to occur.

In the case of checking for aliasing of two pointer values, where at
least one of them is a GEP instruction with out-of-bound indices,
BasicAliasAnalysis can return NoAlias, even if the values point the same
memory cell. I'm not sure if it's an error, as out-of-bound indexing can
bring undefined result (as stated in LangRef.html).

Please, take a look at this code (BasicAA results are in comments).

ehci-hcd-reduced.i (833 Bytes)

It's an optimization opportunity!

When behavior is undefined, we're free to interpret it to be "whatever makes optimization easiest." If the two do actually happen to alias, well, it's the programmer's fault anyways, because they were doing something undefined!

--Owen

Sadly, this will break a very common idiom. In GCC, we discovered it
to be common enough that it broke a *bunch* of C code.

In particular, you will break

struct foo {
int a;
char name[0];
}

bar = malloc(sizeof (struct foo) + strlen("thisismyname") + 1);
strcpy(bar->name, "thisismyname");

It only started turning up when we started doing higher level loop
opts and used alias info in dependence testing. It would end up
reversing or interchanging loops around these things which while
legal, broke enough software that we got yelled at.

So we special case the [0] at end of struct case.

Hi,

Sadly, this will break a very common idiom. In GCC, we discovered it
to be common enough that it broke a *bunch* of C code.

In particular, you will break

struct foo {
int a;
char name[0];
}

bar = malloc(sizeof (struct foo) + strlen("thisismyname") + 1);
strcpy(bar->name, "thisismyname");

It only started turning up when we started doing higher level loop
opts and used alias info in dependence testing. It would end up
reversing or interchanging loops around these things which while
legal, broke enough software that we got yelled at.

So we special case the [0] at end of struct case.

as noted in LangRef,

"Note that 'variable sized arrays' can be implemented in LLVM with a zero
length array. Normally, accesses past the end of an array are undefined in
LLVM (e.g. it is illegal to access the 5th element of a 3 element array). As
a special case, however, zero length arrays are recognized to be variable
length. This allows implementation of 'pascal style arrays' with the LLVM
type "{ i32, [0 x float]}", for example."

so this example should work fine (it wouldn't work if it was char name[1]
though).

Ciao,

Duncan.

Hi,

> Sadly, this will break a very common idiom. In GCC, we discovered it
> to be common enough that it broke a *bunch* of C code.
>
> In particular, you will break
>
> struct foo {
> int a;
> char name[0];
> }
>
> bar = malloc(sizeof (struct foo) + strlen("thisismyname") + 1);
> strcpy(bar->name, "thisismyname");
>
>
> It only started turning up when we started doing higher level loop
> opts and used alias info in dependence testing. It would end up
> reversing or interchanging loops around these things which while
> legal, broke enough software that we got yelled at.
>
> So we special case the [0] at end of struct case.

as noted in LangRef,

"Note that 'variable sized arrays' can be implemented in LLVM with a zero
length array. Normally, accesses past the end of an array are undefined in
LLVM (e.g. it is illegal to access the 5th element of a 3 element array). As
a special case, however, zero length arrays are recognized to be variable
length. This allows implementation of 'pascal style arrays' with the LLVM
type "{ i32, [0 x float]}", for example."

so this example should work fine (it wouldn't work if it was char name[1]
though).

Then the original reported code is fine, and the bug is in llvm or
llvm-gc (IE Owen is wrong)
Note:

struct device;

struct usb_bus {
struct device *controller;
};

struct usb_hcd {
struct usb_bus self;

unsigned long hcd_priv[0];
};

...

You'll notice that the LLVM assembly example he gave is NOT equivalent to the C code. The LLVM assembly uses arrays of declared sized, whereas a correct translation of the above C code into LLVM assembly would not.

--Owen

Hi,

Daniel Berlin wrote:

Then the original reported code is fine, and the bug is in llvm or
llvm-gc (IE Owen is wrong)

There is, actually, no problem with this example.
I attached it, because it contains some specific programming technique,
for which, after instcombining, a weird GEP is generated. I've pasted
fragments of generated assembly code below, if someone is interested.

These are the types declared in the code:

%struct.device = type opaque ; simplified
%struct.ehci_hcd = type opaque ; simplified
%struct.usb_bus = type { %struct.device* }
%struct.usb_hcd = type { %struct.usb_bus, [0 x i32] }

And this is are the interesting instructions. %hcd is a function
argument of type %struct.usb_hcd:

-= before instcombine =-
; based on some facts it is known the second field of
; structure pointed by %hcd is of type %struct.ehci_hcd
%tmp9 = getelementptr %struct.usb_hcd* %hcd, i32 0, i32 1
%tmp910 = bitcast [0 x i32]* %tmp9 to %struct.ehci_hcd*

; later in the source, a pointer to the parent struct is obtained
; from %tmp910 using inner field's offset knowledge
; (__builtin_offsetof operator in the C source)
%tmp1415 = bitcast %struct.ehci_hcd* %tmp910 to [0 x i32]*
%tmp1617 = bitcast [0 x i32]* %tmp1415 to i8*
%tmp18 = getelementptr i8* %tmp1617, i32 -4
%tmp1819 = bitcast i8* %tmp18 to %struct.usb_hcd*

-= after instcombine =-
%tmp18 = getelementptr %struct.usb_hcd* %hcd, i32 0, i32 1, i32 -1

%tmp1819 = bitcast i32* %tmp18 to %struct.usb_hcd*

It is an example of GEP instruction that, on purpose, crosses the bounds
of an inner field to reach a field from the outer structure. It seems to
be correct, assuming negative index is also allowed for a variable-sized
array. BasicAA is correct for in this case, as it seems to treat
conservatively any indexing of a variable-sized array.

--Wojtek

Right, that's the key distinction. For a VLA, you don't know where it might end (without more complex reasoning), so you can't assume that a given GEP is undefined. However, for arrays with declared length, it is easy to tell when you're doing something undefined by GEPing past the end. This latter case is the optimization opportunity.

--Owen