Page MenuHomePhabricator

[BasicAA] Make sure context instruction is symmetric
ClosedPublic

Authored by nikic on Dec 13 2020, 12:14 PM.

Details

Summary

D71264 started using a context instruction in a computeKnownBits() call. However, if aliasing between two GEPs is checked, then the choice of context instruction will be different for alias(GEP1, GEP2) and alias(GEP2, GEP1), which is not supposed to happen.

Resolve this by remembering which GEP a certain VarIndex belongs to, and use that as the context instruction. This makes the choice of context instruction symmetric.

Diff Detail

Event Timeline

nikic created this revision.Dec 13 2020, 12:14 PM
nikic requested review of this revision.Dec 13 2020, 12:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 13 2020, 12:14 PM

Can't we use any dominator for the context? If so, why not use findNearestCommonDominator instead of giving up?

nikic updated this revision to Diff 311684.Dec 14 2020, 1:25 PM

Use different approach: Store which GEP a certain index belongs to and use that as the context instruction. I think this makes more sense than the previous approach, even if it may be fully optimal if one GEP dominates the other.

nikic added a comment.Dec 14 2020, 1:31 PM

Can't we use any dominator for the context? If so, why not use findNearestCommonDominator instead of giving up?

Yes, that would be legal as well (but also sub-optimal). Annoyingly we don't have an instruction-level NCD API (D91767 was recently not accepted), though in this case just taking the terminator of the BB NCD should work fine.

Taking a step back though, I think my original direction here probably wasn't the best, and it would make more sense to use whichever GEP the index actually belonged to as context. That may also be non-optimal (if the index is on a dominating GEP), but I think it's more predictable and doesn't have any odd "cliffs". I have updated the patch to that effect.

nikic edited the summary of this revision. (Show Details)Dec 15 2020, 11:32 AM

Maybe I don't understand this so I figure I ask: Couldn't we know about V2 at position Ctx1 than we know at Ctx2? If so, would it be correct to use Ctx1 information? I get the feeling that the answers are both "true" but I want to confirm first.

nikic added a comment.Dec 22 2020, 2:23 PM

Maybe I don't understand this so I figure I ask: Couldn't we know about V2 at position Ctx1 than we know at Ctx2? If so, would it be correct to use Ctx1 information? I get the feeling that the answers are both "true" but I want to confirm first.

I'm not sure I got the question right, so possibly the answer is way off base...

When considering getModRef() between two instructions, the returned AA information is only (in the general case) valid under the assumption that both instructions have been executed. (This is most obvious for the case of noalias attributes/metadata.) As such, the information can only be valid at program points that are reachable from both instructions. The alias() interface then only considers the stored/loaded operands, rather than the load/store instruction itself, which is a conservative approximation. Once again, the result of the alias API is only valid at program points that are reachable from both operand defs. We can then use either of the operands as context, because the region of validity for the AA result has to be reachable from both. It's once again a conservative approximation. So if we have a VarIndex on GEP1 we could also use GEP2 as context, and the other way around. This patch just picks the GEP it occurs on to ensure the choice is predictable/symmetric.

jdoerfert accepted this revision.Dec 22 2020, 2:44 PM

^ This matches what I was expecting, thanks.

I would like us to (eventually) pick the most precise context but this improves over the status quo and looks correct, so LGTM.

This revision is now accepted and ready to land.Dec 22 2020, 2:44 PM
This revision was automatically updated to reflect the committed changes.