Page MenuHomePhabricator

Fix crash in Dependence Analysis module
ClosedPublic

Authored by karthikthecool on Mar 9 2015, 3:30 AM.

Details

Reviewers
spop
hfinkel
Summary

Hi All,
This crash in Dependency analysis is because we assume here that in case of UsefulGEP both source and destination have the same number of operands which may not be true. This incorrect assumption results in crash while populating Pairs. Fix the same.
Consider the case -

struct s{
  int A[10][10];
  int C[10][10][10]; 
} S;
void dep_constraint_crash_test(int k,int N)  {
   for( int i=0;i<N;i++)
     for( int j=0;j<N;j++)
       S.A[0][0] = S.C[0][0][k];
}

In this case the GEP corresponding to store has 2 operands and that corresponding to load has 3 operands. This was resulting in a crash during dependency analysis.
Please let me know your inputs on the patch.

Thanks and Regards
Karthik Bhat

Diff Detail

Repository
rL LLVM

Event Timeline

karthikthecool retitled this revision from to Fix crash in Dependence Analysis module.
karthikthecool updated this object.
karthikthecool edited the test plan for this revision. (Show Details)
karthikthecool added reviewers: hfinkel, spop.
karthikthecool set the repository for this revision to rL LLVM.
karthikthecool added a subscriber: Unknown Object (MLST).
hfinkel edited edge metadata.Mar 9 2015, 12:34 PM

I don't object to this fix, as such, but is the logic you're fixing even right? Your test case has:

struct s {
  int A[10][10];
  int C[10][10][10]; 
} S;

void dep_constraint_crash_test(int k,int N) {
  for( int i=0;i<N;i++)
    for( int j=0;j<N;j++)
      S.A[0][0] = S.C[0][0][k];
}

but what if it has:

struct s {
  int C[10][10][10]; 
  int A[10][10];
} S;

void dep_constraint_crash_test(int k,int N) {
  for( int i=0;i<N;i++)
    for( int j=0;j<N;j++)
      S.A[0][0] = S.C[0][0][k];
}

what does it say about the dependence of the two? If k > 10, then it could overlap with S.A[0][0].

Hi Hal,
The logic added currently prevents marking the GEP as UsefulGEP and hence different GEP index are not compared independently.
Dependency analysis currently reports an anti dependency between the 2 memory access as -

da analyze - consistent input [S S]!
da analyze - anti [S S|<]!
da analyze - consistent output [S S]!

as it is not considered as UsefulGEP as it doesn't know if k can overflow or not.

I understand from http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130701/179665.html that it is not valid to independently analyze 2 different indices of a GEP as the higher index may overflow into lower index but if it is provable at compile time that this never happens then we can still use this part of the code as is.
So we might want to add additional checks that concludes if a GEP is UsefulGEP and hence can be analyzed independently?
I still need to go through this module in more detail but i feel that part of code inside UsefulGEP will be valid if we can conculde that we can independetly analyze different indices of a GetElementPointer.
Please if you could let me know if i'm thinking in the right direction. Will go through this module in more detail.
Thanks and Regards
Karthik Bhat

hfinkel accepted this revision.Mar 10 2015, 5:27 AM
hfinkel edited edge metadata.

Hi Hal,
The logic added currently prevents marking the GEP as UsefulGEP and hence different GEP index are not compared independently.

Okay, LGTM.

Dependency analysis currently reports an anti dependency between the 2 memory access as -

da analyze - consistent input [S S]!
da analyze - anti [S S|<]!
da analyze - consistent output [S S]!

as it is not considered as UsefulGEP as it doesn't know if k can overflow or not.

I understand from http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130701/179665.html that it is not valid to independently analyze 2 different indices of a GEP as the higher index may overflow into lower index but if it is provable at compile time that this never happens then we can still use this part of the code as is.
So we might want to add additional checks that concludes if a GEP is UsefulGEP and hence can be analyzed independently?

Yes, we might. I'm not sure whether this is useful, or whether we should just rely on / extend the delinearization analysis instead. Using the GEPs as a 'good guess' that require validation is likely reasonable.

I still need to go through this module in more detail but i feel that part of code inside UsefulGEP will be valid if we can conculde that we can independetly analyze different indices of a GetElementPointer.
Please if you could let me know if i'm thinking in the right direction. Will go through this module in more detail.

Sounds good. Please do (but this fix is fine for now).

Thanks and Regards
Karthik Bhat

This revision is now accepted and ready to land.Mar 10 2015, 5:27 AM

Thanks Hal. Comitted as r231784.
Will try to understand delinearization analysis and get back shortly.
Can you also have a look at D8059 when you find time.
Thanks and Regards
Karthik Bhat