Page MenuHomePhabricator

Aliasing of constant pointers (inttoptr Const) for BasicAA

Authored by andrew.zhogin on Jul 1 2016, 7:10 AM.



This patch improves BasicAA to understand aliasing of constant pointers represented as inttoptr (Const).
It supports both IntToPtrInst (%a = inttoptr i32 16 to i32*) and ConstantExpr (store i32 1, i32* inttoptr (i32 16 to i32*)) nodes.
Pointers are considered 'NoAlias' if ptr1 + size1 <= ptr2 or ptr2 + size2 <= ptr1.
Pointers are considered 'MustAlias' if ptr1 == ptr2 and size1 == size2.
Pointers are considered 'PartialAlias' otherwise.
Also, there is a check of pointer type equality.

Constant pointer is a very rare case in common application code. But for some low-level programming (drivers, embedded e.t.c.) such optimization may be helpful.

Diff Detail

Event Timeline

andrew.zhogin retitled this revision from to Aliasing of constant pointers (inttoptr Const) for BasicAA.
andrew.zhogin updated this object.
andrew.zhogin added reviewers: hfinkel, chandlerc.
andrew.zhogin added a subscriber: llvm-commits.
asl added a subscriber: asl.Jul 1 2016, 9:12 AM
asl added inline comments.

Please follow LLVM style guidelines

Style changes

andrew.zhogin marked an inline comment as done.Jul 4 2016, 3:08 AM

This is missing a check for the address-space; address-spaces other than zero can behave in strange ways.

This doesn't correctly account for the width of the pointer: it's possible two pointers could overlap via wraparound.

I don't this is really a good idea, anyway: this seems likely to break someone's code which accidentally forgot to mark a pointer volatile, and unlikely to actually help performance.

if (V1Type == V2Type)

This should also check that address spaces are equal too, right?

Added bitwidth check for constants.

Please ignore my previous comments, they were overly terse and not quite correct.

Analyzing the numeric value of a pointer to determine two pointers are noalias is not safe, period.

On most operating systems, you can mmap() a page of memory to multiple addresses, and users will expect it to point to the same memory. The C++ standard addresses this explicitly for atomic operations: "Operations that are lock-free should also be address-free. That is, atomic operations on the same memory location via two different addresses will communicate atomically."

If you're dealing with unusual addressing systems, the pointer value also can't be used like this because the pointer could contain metadata that doesn't actually affect to the memory location.

It should be okay to determine that two pointers with the same value are MustAlias... but we already perform that check (see isValueEqualInPotentialCycles).

You could write a patch to return PartialAlias results for constant integer pointers where we can prove overlap, I guess.

andrew.zhogin abandoned this revision.Oct 16 2016, 7:34 PM