llvm dev - Aug 2014 - [LLVMdev] For alias analysis, It's gcc too aggressive or LLVM need to improve?

Hi all,

Recently, I found gcc can generate faster codes by localizing global
variable inside loop and only write back once before function return. Gcc
can do this because its alias analysis think it's safe. But for below case,
gcc gives different result from -O0 and -O2.

#include <stdio.h>
struct heap {int index; int b;};
struct heap **ptr;
int aa;

int main() {
  struct heap element;
  struct heap *array[2];
  array[0] = (struct heap *)&aa;
  array[1] = &element;
  ptr = array;
  aa = 1;
  int i;
  for (i =0; i< 2; i++) {
    printf("i is %d, aa is %d\n", i, aa);
    ptr[i]->index = 0;
  }
  return 0;
}

$gcc test.c -O0
$./a.out
i is 0, aa is 1
i is 1, aa is 0

$gcc test.c -O2
$./a.out
i is 0, aa is 1
i is 1, aa is 1

The version of gcc I tried this is 4.8.2 (Ubuntu 4.8.2-19ubuntu1).

On Clang side, it always give the expected result(as the result of gcc -O0)
no matter with the optimization level. But it also lose the opportunity to
localize variable aa and introduced extra load instruction inside loop
because LLVM alias analysis think aa are not independent with the value ptr
point to.

Then my question is,

1. Is this C program legal or not? Especially the type conversion between
int pointer and struct pointer. But at least there's no warning or error
posted during compiling time on both Clang and gcc side.

2. What we should do in LLVM side? LLVM gives correct result on this corner
case no matter it's legal or not, but sacrifices performance on most
generic cases. Did this need a improvement?




-- 
Best Regards,

Kevin Qin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140731/deb22c05/attachment.html>

Hi Kevin,

your C program invokes undefined behavior when it dereferences pointers
that have been converted to other types. See for example
http://stackoverflow.com/questions/4810417/c-when-is-casting-between-pointer-types-not-undefined-behavior

Because of this, the program could do anything... in particular, you can
expect the output of different compilers to be different.

Cheers,
Jonas


On Thu, Jul 31, 2014 at 8:38 AM, Kevin Qin <kevinqindev at gmail.com>
wrote:
> Hi all,
>
> Recently, I found gcc can generate faster codes by localizing global
> variable inside loop and only write back once before function return. Gcc
> can do this because its alias analysis think it's safe. But for below
case,
> gcc gives different result from -O0 and -O2.
>
> #include <stdio.h>
> struct heap {int index; int b;};
> struct heap **ptr;
> int aa;
>
> int main() {
>   struct heap element;
>    struct heap *array[2];
>   array[0] = (struct heap *)&aa;
>   array[1] = &element;
>   ptr = array;
>   aa = 1;
>   int i;
>   for (i =0; i< 2; i++) {
>     printf("i is %d, aa is %d\n", i, aa);
>     ptr[i]->index = 0;
>   }
>   return 0;
> }
>
> $gcc test.c -O0
> $./a.out
> i is 0, aa is 1
> i is 1, aa is 0
>
> $gcc test.c -O2
> $./a.out
> i is 0, aa is 1
> i is 1, aa is 1
>
> The version of gcc I tried this is 4.8.2 (Ubuntu 4.8.2-19ubuntu1).
>
> On Clang side, it always give the expected result(as the result of gcc
> -O0) no matter with the optimization level. But it also lose the
> opportunity to localize variable aa and introduced extra load instruction
> inside loop because LLVM alias analysis think aa are not independent with
> the value ptr point to.
>
> Then my question is,
>
> 1. Is this C program legal or not? Especially the type conversion between
> int pointer and struct pointer. But at least there's no warning or
error
> posted during compiling time on both Clang and gcc side.
>
> 2. What we should do in LLVM side? LLVM gives correct result on this
> corner case no matter it's legal or not, but sacrifices performance on
> most generic cases. Did this need a improvement?
>
>
>
>
> --
> Best Regards,
>
> Kevin Qin
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140808/d15eeb13/attachment.html>

> your C program invokes undefined behavior when it dereferences pointers
that
> have been converted to other types. See for example
>
http://stackoverflow.com/questions/4810417/c-when-is-casting-between-pointer-types-not-undefined-behavior
I don't think it's quite that simple.The type-based aliasing rules
come from 6.5p7 of C11, I think. That says:

"An object shall have its stored value accessed only by an lvalue
expression that has one of
the following types:
  + a type compatible with the effective type of the object,
  [...]
  + an aggregate or union type that includes one of the aforementioned
types among its members [...]"

That would seem to allow this usage: aa (effective type "int") is
being accessed via an lvalue "ptr[i]->index" of type
"int".

The second point would even seem to allow something like "ptr[i] ..."
if aa was declared "int aa[2];", though that seems to be going
too far. It also seems to be very difficult to pin down a meaning
(from the standard) for "a->b" if a is not a pointer to an object
with
the correct effective type. So the entire area is probably one that's
open to interpretation.

I've added cfe-dev to the list; they're the *professional* language
lawyers.

Cheers.

Tim.