(original) (raw)

On April 11, 2017 at 3:28:04 PM, Kostya Serebryany (kcc@google.com) wrote:
\> On Tue, Apr 11, 2017 at 3:14 PM, Sanjoy Das

> wrote:
\>
\> > Hi Kostya,
\> >
\> > On April 11, 2017 at 2:39:44 PM, Kostya Serebryany (kcc@google.com) wrote:
\> > > > ptr0 = malloc();
\> > > > free(ptr0);
\> > > > ptr1 = malloc();
\> > > >
\> > > > ptr0 and ptr1 will be NoAlias despite overlapping (there is actually a
\> > > > real soundness issue here in LLVM's semantics, but I don't want to
\> > > > digress). You can also recreate the pattern with realloc.
\> > > >
\> > >
\> > > In both of your examples there is no place in the program where both P0
\> > and
\> > > P1 are live simultaneously,
\> > > i.e. no analysis path is expected to query MayAlias(AccessToP0,
\> > > AccessToP1). No?
\> >
\> > I may be misunderstanding what you meant, but I don't see why not.
\> >
\> > Say you had (all values are SSA values):
\> >
\> > %p0 = malloc()
\> > store i32 0, i32\* %p0 // S0
\> > free(%p0)
\> > %p1 = malloc()
\> > store i32 1, i32\* %p1 // S1
\> >
\> > and some pass wanted to sink S0 to after S1\. So it starts checking
\> > "from the bottom", as
\> >
\> > Alias(S0, S1) = NoAlias
\> > Alias(S0, malloc()) = NoAlias
\> > Alias(S0, free(%p0)) = MayAlias
\> >
\> > etc. The last MayAlias will prevent it from doing the sink, but I
\> > don't see why it can't ask the Alias(S0, S1) question.
\> >
\>
\> Yea, that's a bit trickier.
\> But we can at least add checks for pairs of pointer accesses that the
\> analysis claims to be ok to reorder.

But that the problem right -- AA told you that S0 and S1 \*are\* okay to
reorder. In fact, if your original program would have been:

p0 = malloc()
free(p0)
p1 = malloc()
\*p0 = 20 // S0
\*p1 = 20 // S1

then S0 and S1 would have been okay to reorder (since the original
program has UB). But you cannot assert !overlap(p0, p1) in the well
defined program I mentioned earlier.

\-- Sanjoy

\>
\>
\>
\> >
\> > > > The same problem exists with constant addresses. LLVM states that
\> > > > constant locations are noalias with themselves, and you again have the
\> > > > "noalias does not imply pointer inequality" problem.
\> > >
\> > > That won't even have to be special cased, because if we emit a check
\> > > ConstPtr != ConstPtr,
\> > > such a check will be trivially optimized away.
\> >
\> > But won't it be constant folded to trigger the sanitizer crash /
\> > warning? That is, since LLVM will state the ConstPtr NoAlias
\> > ConstPtr, you'll emit the check:
\> >
\> > if (overlap(ConstPtr, Sz, ConstPtr, Sz))
\> > abort();
\> >
\> > which will get constant folded to
\> >
\> > if (true) abort();
\> >
\>
\> ah, yes, you are right, then this will have to be special-cased.
\>
\>
\> >
\> > If you meant that the implementation of overlap will differ based on
\> > whether the pointers are constant pointers or not, I'm not sure if
\> > that will work, since the fact that the values whose aliasness (I
\> > think I invented a new word :P ) you're checking could have been
\> > arbitrarily obscured (AA could have looked through PHIs and selects
\> > etc.) which will prevent you from rediscovering that the values were
\> > constant pointers in some cases.
\> >
\> > -- Sanjoy
\> >
\>