[RFC] Introducing a byte type to LLVM

Of course, let's look at a simple example with GVN:
if (p == q) {
  *(p-1) = 0;
}

If p/q are integers, then it's perfectly fine to replace p with q or vice-versa inside the 'if'. GVN may decide to produce this:
if (p == q) {
  *(q-1) = 0;
}

Now consider that p/q are pointers. In particular they are the following:
char a[n];
char q[n];
char *p = a + n;

inlining the definitions, originally we had:
if (a+n == q) {
  *(a+n-1) = 0;
}

The program is well-defined. However, GVN produces a ill-defined program:
if (a+n == q) {
  *(q-1) = 0;
}

While a+n may have the same address as q, their provenance is different. You can dereference a[n-1], but you can't dereference q[-1], even if they have exactly the same address.

Pointer equalities can only be propagated if both pointers have the same provenance information. If two pointers are inbounds and compare equal, then they have the same provenance, for example. That's a case when GVN for pointers is correct.

Another class of issues is related with alias analysis and implicit casts done by integer loads. AA doesn't consider these implicit casts, which is incorrect. When we load an integer, we don't know if we are actually loading an integer or a "raw byte", as there's no way to distinguish. So, to be correct, we need to consider all integer loads as escaping pointers (unless we introduce a way to distinguish "raw byte" loads from integer loads). I gave one such example in my last reply to Johannes.

Please let me know if the example above isn't clear. Happy to elaborate further :slight_smile:

Thanks,
Nuno

See inline

That is not the problem. It is true that whether a+n and q compare equal is unspecified, but that is irrelevant. *If* they compare equal, then the if block must execute as written, else it must not. The only valid options are: either a[n-1] gets set to zero, or a[n-1] is left unmodified. Any transformation to undefined IR is invalid.

You can change the example to something that has fully defined behaviour, even, simply by:

   if (a+n == q) {
     *(a+n-1) = 0;
   } else {
     *(a+n-1) = 0;
   }

If LLVM fails to notice that the two branches are equivalent (allowing the branch to be eliminated entirely), you still have the exact same problem with the first branch potentially getting mis-optimised.

Cheers,
Harald van Dijk

IMHO, the ptr_provenance support that is part of the full restrict patches [0]
can likely help for these cases ? The allow to explicitly associate the ptr_provenance
of a load/store instruction.

In the past LLVM AA Tech Calls, we decided to pull those out of the full restrict
patches and prepare them for inclusion. (Which I still have on my list of todo's)

Greetings,

Jeroen Dobbelaere
[0] https://reviews.llvm.org/D68488 [PATCH 03/27] [noalias] [IR] Introduce ptr_provenance for LoadInst/StoreInst

Of course, let’s look at a simple example with GVN:
if (p == q) {
*(p-1) = 0;
}

If p/q are integers, then it’s perfectly fine to replace p with q or vice-versa inside the ‘if’.

If we start with:

char a[n];
char b[n];
long p = (long)(a+n);
long q = (long)b;
if (p == q) {
((char)p-1) = 0;
}

… what prevents us from observing the same issue?

This is (or at least should be) okay, I think, because p is ptrtoint(a+n), q is ptrtoint(b), the store is to inttoptr(p)-1, and we should already know not to fold inttoptr(ptrtoint(p)) to p. Per https://llvm.org/docs/LangRef.html#pointeraliasing, "A pointer value formed by an inttoptr is based on all pointer values that contribute (directly or indirectly) to the computation of the pointer’s value." The "or indirectly" part of that includes the p == q branch condition.[*] This means that (char*)p compares equal to a+n, (char*)q compares equal to b, but if p == q, then (char*)p and (char*)q are equivalent and either may be used to access a or b.

Cheers,
Harald van Dijk

[*] We have to consider all pointer values that contributed before optimisations, which we do not track, so unless that changes and we do somehow track it, effectively we have to consider all pointer values regardless of whether they contributed to handle the possibility that the p == q check may be optimised away.