[LLVMdev] BasicAliasAnalysis and out-of-bound GEP indices

[Daniel Berlin]

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.

On 11/13/07, Owen Anderson <resistor at mac.com> wrote:
> 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
>
> On Nov 13, 2007, at 4:13 PM, Wojciech Matyjewicz wrote:
>
> > 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).
> > ---
> > target datalayout =
> > "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-
> > f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
> >
> > %ty1 = type [2 x [2 x i8]]
> > %ty2 = type [2 x {i8, [2 x i8]}]
> >
> > @G = external global %ty1
> > @H = external global %ty2
> >
> > ; alias(%a, %b, 1, 1) returns NoAlias,
> > ; although they point to the same memory cell
> > define void @fun1() {
> > entry:
> >        %a = getelementptr %ty1* @G, i32 0, i32 1, i32 -2
> >        %b = bitcast %ty1* @G to i8*
> >        ret void
> > }
> >
> > ; alias(%c, %d, 1, 1) returns NoAlias,
> > ; although they may point to the same memory cell (if %x == -2)
> > define void @fun2(i32 %x) {
> > entry:
> >        %c = getelementptr %ty1* @G, i32 0, i32 1, i32 %x
> >        %d = bitcast %ty1* @G to i8*
> >        ret void
> > }
> >
> > ; alias(%e, %f, 1, 1) returns NoAlias,
> > ; although they may point to the same memory cell (if %z == 2)
> > define void @fun3(i32 %z) {
> > entry:
> >        %e = getelementptr %ty2* @H, i32 0, i32 1, i32 0
> >        %f = getelementptr %ty2* @H, i32 0, i32 0, i32 1, i32 %z
> >        ret void
> > }
> > ---
> >
> > Should we treat this as a bug (I may attempt to prepare a patch
> > then)?.
> > I suppose these are real corner cases, rather improbable to occur in
> > real-world programs. However, something similiar (but no so weird) can
> > be produced from the attached C source. It is a reduced version of
> > preprocessed ehci-hcd.c file (from Linux kernel; compilation of this
> > file discovered bug #1782).
> >
> > --Wojtek
> > struct device;
> >
> > struct usb_bus {
> >  struct device *controller;
> > };
> >
> > struct usb_hcd {
> >  struct usb_bus self;
> >
> >  unsigned long hcd_priv[0];
> > };
> >
> > struct ehci_hcd;
> >
> > static inline __attribute__((always_inline)) struct ehci_hcd
> > *hcd_to_ehci (struct usb_hcd *hcd)
> > {
> >  return (struct ehci_hcd *) (hcd->hcd_priv);
> > }
> >
> > static inline __attribute__((always_inline)) struct usb_hcd
> > *ehci_to_hcd (struct ehci_hcd *ehci)
> > {
> >  return ({ const typeof( ((struct usb_hcd *)0)->hcd_priv ) *__mptr =
> > ((void *) ehci); (struct usb_hcd *)( (char *)__mptr -
> > __builtin_offsetof(struct usb_hcd,hcd_priv) );});
> > }
> >
> > struct device *x;
> >
> > static int ehci_pci_setup(struct usb_hcd *hcd)
> > {
> >  struct ehci_hcd *ehci = hcd_to_ehci(hcd);
> >  // [...]
> >  // store of expression added in order to prevent it from being DCE'ed
> >  x = ehci_to_hcd(ehci)->self.controller;
> >  // [...]
> > }
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>