BasicAA confused after LSR

[hfinkel]

Bugzilla Link	14351
Resolution	FIXED
Resolved on	Jan 28, 2015 06:18
Version	trunk
OS	Linux
Attachments	Post-LSR IR, The IR (before CodeGenPrep passes)

Extended Description

BasicAA is confused by LSR, and this causes aliasing-analysis based dependency breaking to be ineffective on unrolled loops.

After LSR, the basic form of the loop is: for.body4: ; preds = %for.body4, %for.cond2.preheader %lsr.iv4 = phi [16000 x double] [ %11, %for.body4 ], [ bitcast (double getelementptr inbounds ([16000 x double] @​Y, i64 0, i64 8) to [16000 x double]), %for.cond2.preheader ] %lsr.iv1 = phi [16000 x double] [ %10, %for.body4 ], [ @​X, %for.cond2.preheader ] %lsr.iv = phi i32 [ %lsr.iv.next, %for.body4 ], [ 16000, %for.cond2.preheader ] %lsr.iv46 = bitcast [16000 x double] %lsr.iv4 to <4 x double> %lsr.iv12 = bitcast [16000 x double] %lsr.iv1 to <4 x double> ... %scevgep11 = getelementptr <4 x double> %lsr.iv46, i64 -2 %6 = load <4 x double> %scevgep11, align 32, !tbaa !​0 ... store <4 x double> %add, <4 x double> %lsr.iv12, align 32, !tbaa !​0 ... %scevgep = getelementptr [16000 x double] %lsr.iv1, i64 0, i64 16 %10 = bitcast double %scevgep to [16000 x double] %scevgep5 = getelementptr [16000 x double] %lsr.iv4, i64 0, i64 16 %11 = bitcast double %scevgep5 to [16000 x double]

pointers derived from %lsr.iv4 and %lsr.iv1 come from different underlying objects, but BasicAA does not see this.

MayAlias: <4 x double> %lsr.iv12, <4 x double> %scevgep11

The full test case is attached.

[hfinkel]

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!

[llvmbot]

Is this defect still open ? I do not see a patch attached to it ? Has the problem been fixed ?

[llvmbot]

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.

[hfinkel]

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?

[llvmbot]

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.

[hfinkel]

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?

[llvmbot]

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.

[llvmbot]

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.

[hfinkel]

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?

[hfinkel]

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

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?

[llvmbot]

I would probably do it sometime by or over thanksgiving.

[llvmbot]

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

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?

[hfinkel]

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

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?

[llvmbot]

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.

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?

[hfinkel]

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!

[llvmbot]

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.