Page MenuHomePhabricator

[BasicAliasAnalysis] Allow idAddofNonZero() for values coming from the same loop iteration.
AcceptedPublic

Authored by Farhana on Jun 21 2017, 2:43 PM.

Details

Summary

This is a fix for the case in PR33549.

Current basic alias analysis is very conservative when it tries to analyze two GEP indices with the same base pointers. This patch tries to relax it a bit. It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet.

Diff Detail

Repository
rL LLVM

Event Timeline

Farhana created this revision.Jun 21 2017, 2:43 PM
Farhana updated this revision to Diff 103471.Jun 21 2017, 3:04 PM
dberlin edited edge metadata.Jun 21 2017, 3:32 PM

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I agree that my comment about loop iteration is misleading.

In order to call isAddOfNonZero() on index1 and index2 and check whether index2 equals to index1 + x( and, vice versa), we need to prove that we are working on the same copy of index1. Which means the instance that used in index1 is the same as the one used in index2.
If we haven’t visited any phis yet, we can assume that part of the code is flat and we have the same copy, right?

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

I totally agree with you. I was just thinking we might want a temporary solution(specifically a cheap one) while we are waiting on that.

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I agree that my comment about loop iteration is misleading.

In order to call isAddOfNonZero() on index1 and index2 and check whether index2 equals to index1 + x( and, vice versa), we need to prove that we are working on the same copy of index1. Which means the instance that used in index1 is the same as the one used in index2.
If we haven’t visited any phis yet, we can assume that part of the code is flat and we have the same copy, right?

This is precisely my question: Are you guaranteed that all codepaths end up here only in that situation?

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

I totally agree with you. I was just thinking we might want a temporary solution(specifically a cheap one) while we are waiting on that.

With no offense meant (and i'm happy to accept the patch if we can prove it right): This is precisely how BasicAA got into this situation.
We add stuff thinking "well, it's probably right", and then it turns out not to be ;)

So i want to be super careful that we can prove to ourselves that this is right.

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I agree that my comment about loop iteration is misleading.

In order to call isAddOfNonZero() on index1 and index2 and check whether index2 equals to index1 + x( and, vice versa), we need to prove that we are working on the same copy of index1. Which means the instance that used in index1 is the same as the one used in index2.
If we haven’t visited any phis yet, we can assume that part of the code is flat and we have the same copy, right?

This is precisely my question: Are you guaranteed that all codepaths end up here only in that situation?

Sorry, I misunderstood your question earlier.

Yes, it is guaranteed that BasicAA hasn't done any phi translation so far for these two GEP indices when the code path reached in that situation. It not only guarantees that the phi translation has not happened for these two indices, it also guarantees that the phi-translation hasn't happened any of its parent expressions either starting from the two root memory locations.

More Details:

After each alias analysis for a pair of memory locations BasicAA always clears out the VisitedPhiBBs. Checking only for whether VisitedPhiBBs is empty leaves the analysis still pretty conservative since we don't really check whether the phi translation has anything to do with these two GEP indices but it's probably good enough for a short term solution. Since there is a tradeoff, checking for GEP indices in phi translation will induce more compile time.

AliasResult BasicAAResult::alias(..) {
         ...
VisitedPhiBBs.clear();
return Alias;
}

alias():
VisitedPhiBBs = empty

    MemLoc1           
     /  \                    
 base idx1            
        |                                
       phi                           
   
  
   MemLoc2                                        
    /   \                                                                   
base  idx2 
       /  \
   idx1   N
     |
   phi  (no phis are translated so far. Therefore, idx1 in memloc2 and idx1 in memloc1 have the same live in value)

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

I totally agree with you. I was just thinking we might want a temporary solution(specifically a cheap one) while we are waiting on that.

With no offense meant (and i'm happy to accept the patch if we can prove it right): This is precisely how BasicAA got into this situation.
We add stuff thinking "well, it's probably right", and then it turns out not to be ;)

So i want to be super careful that we can prove to ourselves that this is right.

I understand your concern :).

Hi Daniel,

Any news on this?

Farhana

dberlin accepted this revision.Jul 5 2017, 9:38 AM

I'm fine with this for the moment, but, as you know, i think we gotta stop thinking "bandaids" :)

This revision is now accepted and ready to land.Jul 5 2017, 9:38 AM
This revision was automatically updated to reflect the committed changes.
chapuni reopened this revision.Jul 10 2017, 8:37 PM
chapuni added a subscriber: chapuni.

Reverted in r307613. This caused miscompilation.
See http://bb.pgr.jp/builders/bootstrap-clang-libcxx-lld-i686-linux/builds/172
(Note, reproduced locally w/o modules)

This revision is now accepted and ready to land.Jul 10 2017, 8:37 PM