Quuxplusone
commented
11 years ago Attached s000_post_cgp.ll (5507 bytes, application/octet-stream): Post-LSR IR
Closed Quuxplusone closed 9 years ago
Quuxplusone
commented
11 years ago Attached s000_post_cgp.ll (5507 bytes, application/octet-stream): Post-LSR IR
Quuxplusone
commented
11 years ago Attached s000.ll (5484 bytes, application/octet-stream): The IR (before CodeGenPrep passes)
Quuxplusone
commented
11 years ago Ah, yes. This is a problem in the basic aa code that does phi-speculation.
Right now it looks at the first operand of the two phis. If these operands are
NoAlias, it will assume the phis to be no-alias and process the remaining phi
operands under this assumption.
If you would change the order of operands in the example you will get a no-
alias.
Now, I believe that we could speculate phi's value to be noalias even before we
looked at any of its operands and then look at the operands under this
assumption and try to disprove it (right now we only do this if the first
operand was no-alias).
Since we don't keep any state around for other queries and any value cycle will
eventually include the instruction that disproves the noalias I think we should
be save.
Here is the example i use to convince myself of this.
pre_header:
x0 =
y0 =
outer_loop:
x1 = phi(x0, x4)
y2 = phi(y0, y4)
inner_loop:
x2 = phi(x1, x3)
y2 = phi(y1, y3)
x3 = add x2, <1 or 2>
y3 = add x2, 1
br cond, inner_loop, outer_loop_backedge
outer_loop_backedge:
x4 = add x2, <1 or 2>
y4 = add y2, 1
br cond2, outer_loop, exitbb
exit_bb:
We will eventually end up at either
isNoAlias((x3,y3) under assumption that noAlias(x2, y2))
isNoAlias((x4,y4) under the assumpton that noAlias(x2, y2))
isNoAlias(x0, y0)
In either case we can deduce the correct fact even though the assumption might
be wrong.(In reply to comment #2)
> Ah, yes. This is a problem in the basic aa code that does phi-speculation.
> Right now it looks at the first operand of the two phis. If these operands are
> NoAlias, it will assume the phis to be no-alias and process the remaining phi
> operands under this assumption.
>
> If you would change the order of operands in the example you will get a
> no-alias.
Are you referring to this code in BasicAliasAnalysis::aliasPHI:
AliasResult Alias =
aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
V2Size, V2TBAAInfo);
if (Alias == MayAlias)
return MayAlias;
We need to check the different indicies, not just the first, right? Is there
any reason not to loop here over all phi indicies?
>
> Now, I believe that we could speculate phi's value to be noalias even before
we
> looked at any of its operands and then look at the operands under this
> assumption and try to disprove it (right now we only do this if the first
> operand was no-alias).
>
> Since we don't keep any state around for other queries and any value cycle
will
> eventually include the instruction that disproves the noalias I think we
should
> be save.
>
> Here is the example i use to convince myself of this.
>
> pre_header:
> x0 =
> y0 =
>
> outer_loop:
> x1 = phi(x0, x4)
> y2 = phi(y0, y4)
>
> inner_loop:
> x2 = phi(x1, x3)
> y2 = phi(y1, y3)
> x3 = add x2, <1 or 2>
> y3 = add x2, 1
> br cond, inner_loop, outer_loop_backedge
>
> outer_loop_backedge:
> x4 = add x2, <1 or 2>
> y4 = add y2, 1
> br cond2, outer_loop, exitbb
>
> exit_bb:
>
> We will eventually end up at either
> isNoAlias((x3,y3) under assumption that noAlias(x2, y2))
> isNoAlias((x4,y4) under the assumpton that noAlias(x2, y2))
> isNoAlias(x0, y0)
>
> In either case we can deduce the correct fact even though the assumption might
> be wrong.
If we were to loop over all incoming phi indicies, does that differ from what
you're proposing?
Thanks!Yes it is the code in this vicinity.
The relevant code (pseudo, simplified) currently does something like:
aliasPhi(phi, phi2) {
alias = aliasCheck first operand op1, op2 of phi,phi2
if (alias == MayAlias)
return alias
if (alias == NoAlias)
AliasCache[phi, phi2] = NoAlias
for (remaining operand op1, op2 of phi, ph2)
merge aliasCheck(op1, op2) with previous alias result
return alias
}
What I am suggesting is to move the assumption that phi, phi2 don't alias up.
AliasCache[phi, phi2] = NoAlias
for (every operand op1, op2 of phi, ph2)
merge aliasCheck(op1, op2) with previous alias result
return alias
I left out the part that resets the cache.
(In reply to comment #3)
> (In reply to comment #2)
> > Ah, yes. This is a problem in the basic aa code that does phi-speculation.
> > Right now it looks at the first operand of the two phis. If these operands
are
> > NoAlias, it will assume the phis to be no-alias and process the remaining
phi
> > operands under this assumption.
> >
> > If you would change the order of operands in the example you will get a
> > no-alias.
>
> Are you referring to this code in BasicAliasAnalysis::aliasPHI:
> AliasResult Alias =
> aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
> PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
> V2Size, V2TBAAInfo);
> if (Alias == MayAlias)
> return MayAlias;
>
> We need to check the different indicies, not just the first, right? Is there
> any reason not to loop here over all phi indicies?(In reply to comment #4)
> Yes it is the code in this vicinity.
>
> The relevant code (pseudo, simplified) currently does something like:
>
> aliasPhi(phi, phi2) {
>
> alias = aliasCheck first operand op1, op2 of phi,phi2
>
> if (alias == MayAlias)
> return alias
>
> if (alias == NoAlias)
> AliasCache[phi, phi2] = NoAlias
>
> for (remaining operand op1, op2 of phi, ph2)
> merge aliasCheck(op1, op2) with previous alias result
>
> return alias
>
> }
>
>
> What I am suggesting is to move the assumption that phi, phi2 don't alias up.
>
>
> AliasCache[phi, phi2] = NoAlias
>
> for (every operand op1, op2 of phi, ph2)
> merge aliasCheck(op1, op2) with previous alias result
>
> return alias
>
>
> I left out the part that resets the cache.
Yes, that seems right. We should check that the phi operands don't alias under
the assumption that the current phis don't alias.
In other words, the only way for the current phis to alias is if one of their
non-self-derived operands alias. This makes sense because if none of the non-
self-derived operands alias, then the phis must be derived from different base
pointers, and cannot themselves alias.
Do you want to code the patch, or shall I?
-Hal
>
> (In reply to comment #3)
> > (In reply to comment #2)
> > > Ah, yes. This is a problem in the basic aa code that does phi-speculation.
> > > Right now it looks at the first operand of the two phis. If these
operands are
> > > NoAlias, it will assume the phis to be no-alias and process the remaining
phi
> > > operands under this assumption.
> > >
> > > If you would change the order of operands in the example you will get a
> > > no-alias.
> >
> > Are you referring to this code in BasicAliasAnalysis::aliasPHI:
> > AliasResult Alias =
> > aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
> > PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
> > V2Size, V2TBAAInfo);
> > if (Alias == MayAlias)
> > return MayAlias;
> >
> > We need to check the different indicies, not just the first, right? Is there
> > any reason not to loop here over all phi indicies?> Yes, that seems right. We should check that the phi operands don't alias under
> the assumption that the current phis don't alias.
Yup.
> In other words, the only way for the current phis to alias is if one of their
> non-self-derived operands alias. This makes sense because if none of the
> non-self-derived operands alias, then the phis must be derived from different
> base pointers, and cannot themselves alias.
I am not sure I agree with the description or maybe I misunderstand it.
Counterexample:
ptr = a
ptr2 = a+1
loop:
p = phi(ptr, p1)
q = phi(ptr2, q1)
p1 = add 2, p
q1 = add 1, q
Here ptr, ptr2 don't alias (although they are derived from the same base
pointer) but p,q do after the first iteration.
But the logic that is there already handles those cases correctly.
> Do you want to code the patch, or shall I?
How quickly you need this? ;)
>
> -Hal
>
> >
> > (In reply to comment #3)
> > > (In reply to comment #2)
> > > > Ah, yes. This is a problem in the basic aa code that does phi-
speculation.
> > > > Right now it looks at the first operand of the two phis. If these
operands are
> > > > NoAlias, it will assume the phis to be no-alias and process the
remaining phi
> > > > operands under this assumption.
> > > >
> > > > If you would change the order of operands in the example you will get a
> > > > no-alias.
> > >
> > > Are you referring to this code in BasicAliasAnalysis::aliasPHI:
> > > AliasResult Alias =
> > > aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
> > > PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
> > > V2Size, V2TBAAInfo);
> > > if (Alias == MayAlias)
> > > return MayAlias;
> > >
> > > We need to check the different indicies, not just the first, right? Is
there
> > > any reason not to loop here over all phi indicies?I would probably do it sometime by or over thanksgiving.
Quuxplusone
commented
11 years ago (In reply to comment #6)
> > Yes, that seems right. We should check that the phi operands don't alias
under
> > the assumption that the current phis don't alias.
> Yup.
>
> > In other words, the only way for the current phis to alias is if one of
their
> > non-self-derived operands alias. This makes sense because if none of the
> > non-self-derived operands alias, then the phis must be derived from
different
> > base pointers, and cannot themselves alias.
>
> I am not sure I agree with the description or maybe I misunderstand it.
>
> Counterexample:
>
> ptr = a
> ptr2 = a+1
>
> loop:
> p = phi(ptr, p1)
> q = phi(ptr2, q1)
> p1 = add 2, p
> q1 = add 1, q
>
> Here ptr, ptr2 don't alias (although they are derived from the same base
> pointer) but p,q do after the first iteration.
Okay, yes. I did not say what I was thinking. What I was thinking was: if we
can prove that the phi operands derive from disjoint base pointers, then the
phis cannot alias.
>
> But the logic that is there already handles those cases correctly.
How?
>
>
> > Do you want to code the patch, or shall I?
>
> How quickly you need this? ;)
>
> >
> > -Hal
> >
> > >
> > > (In reply to comment #3)
> > > > (In reply to comment #2)
> > > > > Ah, yes. This is a problem in the basic aa code that does phi-
speculation.
> > > > > Right now it looks at the first operand of the two phis. If these
operands are
> > > > > NoAlias, it will assume the phis to be no-alias and process the
remaining phi
> > > > > operands under this assumption.
> > > > >
> > > > > If you would change the order of operands in the example you will get
a
> > > > > no-alias.
> > > >
> > > > Are you referring to this code in BasicAliasAnalysis::aliasPHI:
> > > > AliasResult Alias =
> > > > aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
> > > > PN2->getIncomingValueForBlock(PN-
>getIncomingBlock(0)),
> > > > V2Size, V2TBAAInfo);
> > > > if (Alias == MayAlias)
> > > > return MayAlias;
> > > >
> > > > We need to check the different indicies, not just the first, right? Is
there
> > > > any reason not to loop here over all phi indicies?(In reply to comment #7)
> I would probably do it sometime by or over thanksgiving.
That would be great, thanks!
In the mean time, is there a reason the current code only checks the first phi
operands? Would picking the first operand not from the current block be better?(In reply to comment #9)
> (In reply to comment #7)
> > I would probably do it sometime by or over thanksgiving.
>
> That would be great, thanks!
>
> In the mean time, is there a reason the current code only checks the first phi
> operands? Would picking the first operand not from the current block be
better?
Yes that would have been better.(In reply to comment #8)
> (In reply to comment #6)
> > > Yes, that seems right. We should check that the phi operands don't alias
under
> > > the assumption that the current phis don't alias.
> > Yup.
> >
> > > In other words, the only way for the current phis to alias is if one of
their
> > > non-self-derived operands alias. This makes sense because if none of the
> > > non-self-derived operands alias, then the phis must be derived from
different
> > > base pointers, and cannot themselves alias.
> >
> > I am not sure I agree with the description or maybe I misunderstand it.
> >
> > Counterexample:
> >
> > ptr = a
> > ptr2 = a+1
> >
> > loop:
> > p = phi(ptr, p1)
> > q = phi(ptr2, q1)
> > p1 = add 2, p
> > q1 = add 1, q
> >
> > Here ptr, ptr2 don't alias (although they are derived from the same base
> > pointer) but p,q do after the first iteration.
>
> Okay, yes. I did not say what I was thinking. What I was thinking was: if we
> can prove that the phi operands derive from disjoint base pointers, then the
> phis cannot alias.
>
> >
> > But the logic that is there already handles those cases correctly.
>
> How?
In
gep Ptr1, 0, 1
gep Ptr2, 0, 1
we check whether Ptr1, Ptr2 are NoAlias. if they are we check that the indices
match and if they do we can return NoAlias.(In reply to comment #11)
> (In reply to comment #8)
> > (In reply to comment #6)
> > > > Yes, that seems right. We should check that the phi operands don't
alias under
> > > > the assumption that the current phis don't alias.
> > > Yup.
> > >
> > > > In other words, the only way for the current phis to alias is if one of
their
> > > > non-self-derived operands alias. This makes sense because if none of the
> > > > non-self-derived operands alias, then the phis must be derived from
different
> > > > base pointers, and cannot themselves alias.
> > >
> > > I am not sure I agree with the description or maybe I misunderstand it.
> > >
> > > Counterexample:
> > >
> > > ptr = a
> > > ptr2 = a+1
> > >
> > > loop:
> > > p = phi(ptr, p1)
> > > q = phi(ptr2, q1)
> > > p1 = add 2, p
> > > q1 = add 1, q
> > >
> > > Here ptr, ptr2 don't alias (although they are derived from the same base
> > > pointer) but p,q do after the first iteration.
> >
> > Okay, yes. I did not say what I was thinking. What I was thinking was: if we
> > can prove that the phi operands derive from disjoint base pointers, then the
> > phis cannot alias.
> >
> > >
> > > But the logic that is there already handles those cases correctly.
> >
> > How?
> In
>
> gep Ptr1, 0, 1
> gep Ptr2, 0, 1
>
> we check whether Ptr1, Ptr2 are NoAlias. if they are we check that the indices
> match and if they do we can return NoAlias.
So you're saying that in:
> > p1 = add 2, p
> > q1 = add 1, q
we would return MayAlias because the indicies don't match, right?(In reply to comment #12)
> > > How?
> > In
> >
> > gep Ptr1, 0, 1
> > gep Ptr2, 0, 1
> >
> > we check whether Ptr1, Ptr2 are NoAlias. if they are we check that the
indices
> > match and if they do we can return NoAlias.
>
> So you're saying that in:
> > > p1 = add 2, p
> > > q1 = add 1, q
> we would return MayAlias because the indicies don't match, right?
Yes.(In reply to comment #13)
> (In reply to comment #12)
> > > > How?
> > > In
> > >
> > > gep Ptr1, 0, 1
> > > gep Ptr2, 0, 1
> > >
> > > we check whether Ptr1, Ptr2 are NoAlias. if they are we check that the
indices
> > > match and if they do we can return NoAlias.
> >
> > So you're saying that in:
> > > > p1 = add 2, p
> > > > q1 = add 1, q
> > we would return MayAlias because the indicies don't match, right?
>
>
> Yes.
Alright. This will still be true even if you change the query algorithm as
you've suggested, right?(In reply to comment #14)
> (In reply to comment #13)
> > (In reply to comment #12)
> > > > > How?
> > > > In
> > > >
> > > > gep Ptr1, 0, 1
> > > > gep Ptr2, 0, 1
> > > >
> > > > we check whether Ptr1, Ptr2 are NoAlias. if they are we check that the
indices
> > > > match and if they do we can return NoAlias.
> > >
> > > So you're saying that in:
> > > > > p1 = add 2, p
> > > > > q1 = add 1, q
> > > we would return MayAlias because the indicies don't match, right?
> >
> >
> > Yes.
>
> Alright. This will still be true even if you change the query algorithm as
> you've suggested, right?
Yep.Is this defect still open ? I do not see a patch attached to it ? Has the problem been fixed ?
Quuxplusone
commented
9 years ago (In reply to comment #16)
> Is this defect still open ? I do not see a patch attached to it ?
We don't generally attach patches to bug reports. Instead, they're sent to the
llvm-commits list for review. Please see
http://llvm.org/docs/DeveloperPolicy.html#code-reviews for more information.
> Has the
> problem been fixed ?
Yes, it was fixed in r168245; a more-general solution was implemented in
r169788.
Thanks for pinging this, we had forgotten to close it!
s000_post_cgp.ll(5507 bytes, application/octet-stream)s000.ll(5484 bytes, application/octet-stream)