[LLVMdev] Semantics of an Inbounds GetElementPtr

[Philip Reames]

I think this got settled on the review, but inferring anything about 
reachability from just a gep is wrong.  You can (and we do), infer that 
a *dereference* of a null pointer implies the path is unreachable, but 
merely doing address computation with a null pointer is entirely 
legitimate and common.

Going back to the original example:
define i8 @func(i8* %mem) {
   %test = icmp eq i8* %mem, null
   br i1 %test, label %done, label %mem.is.valid
mem.is.valid:
   %1 = getelementptr inbounds i8, i8* %mem, i64 4
   store i8 5, i8* %1, align 4
   br label %done
done:
   %after.phi = phi i8* [ %mem, %mem.is.valid ], [ null, %0 ]
   %2 = getelementptr inbounds i8, i8* %after.phi, i64 4
   %five = load i8, i8* %2, align 4
   ret i8 %five
}

 From "%five = load i8, i8* %2, align 4", we can infer that the edge 
entry->done is never taken.  Doing so would result in the unconditional 
dereference of a null pointer.  This would give us:

define i8 @func(i8* %mem) {
   br label %mem.is.valid
mem.is.valid:
   %1 = getelementptr inbounds i8, i8* %mem, i64 4
   store i8 5, i8* %1, align 4
   br label %done
done:
   %2 = getelementptr inbounds i8, i8* %mem, i64 4
   %five = load i8, i8* %2, align 4
   ret i8 %five
}

After store-load forwarding and combining basic blocks, we'd have:
define i8 @func(i8* %mem) {
   %1 = getelementptr inbounds i8, i8* %mem, i64 4
   store i8 5, i8* %1, align 4
   ret i8 5
}

That's as far as we can optimize that.

Well, not quite.  We can infer that the argument must be non-null, which 
can propagate the facts to the caller and allow simplifications there as 
well.  (I don't believe we currently do that, but we could.)

p.s. I haven't been really following this thread.  If I've miss 
something by jumping in late, feel free to correct me.

Philip

On 05/11/2015 08:07 AM, Daniel Berlin wrote:
> +Philip
> Looks pretty good. As i just said on the review, it would be really
> nice to know how often this triggers.
>
> Philip may be interested too, if they don't already have a null check
> removal pass of their own :)
>
>
> On Sat, May 9, 2015 at 6:35 AM, Nicholas White <n.j.white at gmail.com> wrote:
>> Thanks - that was very interesting. I've had a go at implementing it
>> here - http://reviews.llvm.org/D9634 - as an improvement to the SCCP
>> pass. It seems to work (see the test cases), but I had to make a few
>> compromises (making PtrUseVisitor look through phi nodes, only working
>> on CmpInst.isEquality() instructions, and making the SCCP pass
>> dependent on the PostDominatorTree pass). I think it's O(n);
>> PtrUseVisitor scans each Use at most once, and PostDominatorTree seems
>> linear in the number of predecessor blocks. It was easier to implement
>> by starting at a ptr-vs-null-checking CmpInst and analysing the code
>> forwards rather than by starting at an inbounds GEP instruction and
>> analysing the code backwards. What do you think?
>>
>> Thanks -
>>
>> Nick