>> As part of the advanced compilers course semester project (at >> UIUC), we >> are starting to implement array dependence analysis for LLVM.Great! This is something we've needed for a long time.> I'm currently working on a similar project and hoping to finish it in > about two weeks.Cool! I think the most critical part of this is to get a good interface for dependence analysis. There are lots of interesting implementations that have various time/space tradeoffs. For example, it would be great if Omega was available as an option, even if the compiler didn't use it by default. This argues for making dependence analysis implementations pluggable like alias analyses.> As for now, I'm focusing on the dependency analysis engine and publish > only a simplistic interface (it only allows to check whether a loop > carries a memory dependence). However, the engine is quite > self-contained and should be easy to attach to a different interface. > For instance, the engine will be able to find dependence direction > vectors for an instruction pair.Sounds good. If you have the interface nailed down, it would be good to post what the query interface looks like. Vikram and others have a lot of experience with dependence analysis and know what sorts of queries various clients are interested in. They can help give feedback on the direction you're pursuing independent of the implementation.>> Any suggestion on features, tests and/or interface are welcome.I'd suggest looking at: Using the chains of recurrences algebra for data dependence testing and induction variable substitution MS Thesis, Johnie Birch Array Data Dependence Testing with the Chains of Recurrences Algebra http://citeseer.ist.psu.edu/vanengelen04array.html An empirical evaluation of chains of recurrences for array dependence testing http://doi.acm.org/10.1145/1152154.1152198 etc.>> From my experience I can say it's essential to use a precise alias > analysis as the base for the array dependence analysis. Fortunately, > using Data Structure or Andersen's AA for the whole program can > provide > really good results.Yep, but any particular dep analysis implementation should just require AliasAnalysis instead of a specific implementation. This lets the client (e.g. llvm-gcc) decide what passes to plug together. -Chris
Hi,> Cool! I think the most critical part of this is to get a good > interface for dependence analysis. There are lots of interesting > implementations that have various time/space tradeoffs. > > For example, it would be great if Omega was available as an option, > even if the compiler didn't use it by default. This argues for making > dependence analysis implementations pluggable like alias analyses.Yes, I also thought about it that way. I think we may look at the dependence analysis in LLVM at three levels (from the lowest to the highest one): 1) Testing for dependence given two sequences of GEP indices assuming that base pointers are the same. The indices could have a SCEV form or even be preprocessed to something simpler (affine expressions for example). 2) Testing for dependence of two instructions (that access memory). It would use alias analysis to answer some queries immediately, or to check whether two GEP base pointers equal. If the latter is the case, 1) would be used to check for dependences. 3) Complex queries (for example: does the given loop carry dependence?). It would use 2) and summarize its results. Only the first level could be pluggable allowing to interchange or chain core dependency testing techniques. I think there will be no use in making pluggable the higher ones (please, correct me if I am wrong). This approach would require to divide the analysis structure into two parts, say; DependenceAnalysis and IndexingTester. That said, I must admit I haven't made it that way in my prototype. I have it in mind, but I'm currently trying to keep things simple and just to check whether the precision of my implementation is worth anything.> Sounds good. If you have the interface nailed down, it would be good > to post what the query interface looks like. Vikram and others have a > lot of experience with dependence analysis and know what sorts of > queries various clients are interested in. They can help give > feedback on the direction you're pursuing independent of the > implementation.Ok. I'll post it when it crystallizes (what should happen soon).> I'd suggest looking at: > > Using the chains of recurrences algebra for data dependence testing > and induction variable substitution > MS Thesis, Johnie Birch > > Array Data Dependence Testing with the Chains of Recurrences Algebra > http://citeseer.ist.psu.edu/vanengelen04array.html > > An empirical evaluation of chains of recurrences for array dependence > testing > http://doi.acm.org/10.1145/1152154.1152198I've read the second one, but am not sure if it's easy to implement if overflow and unknown signedness are taken into account. For now, I will stick to the classical Banerjee test. If time allows I'll return to the article.>>> From my experience I can say it's essential to use a precise alias >> analysis as the base for the array dependence analysis. Fortunately, >> using Data Structure or Andersen's AA for the whole program can >> provide >> really good results. > > Yep, but any particular dep analysis implementation should just > require AliasAnalysis instead of a specific implementation. This lets > the client (e.g. llvm-gcc) decide what passes to plug together.You're right. From the implementation point of view the choice of alias analysis doesn't matter at all. Wojtek
On Mar 18, 2008, at 9:21 AM, Wojciech Matyjewicz wrote:> Hi, > >> Cool! I think the most critical part of this is to get a good >> interface for dependence analysis. There are lots of interesting >> implementations that have various time/space tradeoffs. >> >> For example, it would be great if Omega was available as an option, >> even if the compiler didn't use it by default. This argues for >> making >> dependence analysis implementations pluggable like alias analyses. > > Yes, I also thought about it that way. I think we may look at the > dependence analysis in LLVM at three levels (from the lowest to the > highest one): > > 1) Testing for dependence given two sequences of GEP indices assuming > that base pointers are the same. The indices could have a SCEV form or > even be preprocessed to something simpler (affine expressions for > example). > > 2) Testing for dependence of two instructions (that access memory). It > would use alias analysis to answer some queries immediately, or to > check > whether two GEP base pointers equal. If the latter is the case, 1) > would > be used to check for dependences. > > 3) Complex queries (for example: does the given loop carry > dependence?). > It would use 2) and summarize its results. > > Only the first level could be pluggable allowing to interchange or > chain > core dependency testing techniques. I think there will be no use in > making pluggable the higher ones (please, correct me if I am wrong). > This approach would require to divide the analysis structure into two > parts, say; DependenceAnalysis and IndexingTester.This all sounds great to me!> That said, I must admit I haven't made it that way in my prototype. I > have it in mind, but I'm currently trying to keep things simple and > just > to check whether the precision of my implementation is worth anything.I'm fine with starting simple and generalizing it out from there. I'd actually recommend against trying to implement a maximally precise dependence analyzer without a client. With no client, there is no way to test that you're getting correct results and whether the improvements in precision are actually useful. I'd suggest starting out with a simple checker, e.g. that handles simple affine cases, and some client (a loop xform?). This should be enough to get the transformation working on simple loops, and when the client is tested and working there, you can use it to evaluate whether the precision improvements are worthwhile. If you're looking for a simple client, I'd suggest something like loop reversal. This requires a pretty simple dependence test and can be useful for some targets. The idea is to turn: for (i = 0 .. 100) A[i] = 4; into: for (i = 100 .. 0) A[i] = 4; Another transform that needs dependence analysis which would be even more useful (but still very simple) is a "loops to memset/memcpy" pass. This optimization would speed up the 'viterbi' program in the test suite a *lot* for the various 'history' loops. A simple version of this is: for (i = 0 .. 100) A[i] = 0; -> memset(A, 0, sizeof(A[0])*100);>> I'd suggest looking at: >> >> Using the chains of recurrences algebra for data dependence testing >> and induction variable substitution >> MS Thesis, Johnie Birch >> >> Array Data Dependence Testing with the Chains of Recurrences Algebra >> http://citeseer.ist.psu.edu/vanengelen04array.html >> >> An empirical evaluation of chains of recurrences for array dependence >> testing >> http://doi.acm.org/10.1145/1152154.1152198 > > I've read the second one, but am not sure if it's easy to implement if > overflow and unknown signedness are taken into account. For now, I > will > stick to the classical Banerjee test. If time allows I'll return to > the > article.Ok. Starting simple is good. Thanks again for working on this, this is a major hole in llvm, -Chris
Wojtek, If you like, I can help guide this SoC project. I would also like to see if we can coordinate with Alex and Albert, who are doing the class project here. As a first comment, your 3 layers are a good organization but two comments: 1. Layer 1 shd also look at loop bounds and array bounds: those can be used to disprove some deps. 2. The interface will also need to compute direction and perhaps distance vectors. Those may or may not be easy to put in one of your layers (say, layer 3, where they belong). --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.org ...... Original Message ....... On Tue, 18 Mar 2008 11:21:38 -0500 "Wojciech Matyjewicz" <wmatyjewicz at fastmail.fm> wrote:>Hi, > >> Cool! I think the most critical part of this is to get a good >> interface for dependence analysis. There are lots of interesting >> implementations that have various time/space tradeoffs. >> >> For example, it would be great if Omega was available as an option, >> even if the compiler didn't use it by default. This argues for making >> dependence analysis implementations pluggable like alias analyses. > >Yes, I also thought about it that way. I think we may look at the >dependence analysis in LLVM at three levels (from the lowest to the >highest one): > >1) Testing for dependence given two sequences of GEP indices assuming >that base pointers are the same. The indices could have a SCEV form or >even be preprocessed to something simpler (affine expressions for example). > >2) Testing for dependence of two instructions (that access memory). It >would use alias analysis to answer some queries immediately, or to check >whether two GEP base pointers equal. If the latter is the case, 1) would >be used to check for dependences. > >3) Complex queries (for example: does the given loop carry dependence?). >It would use 2) and summarize its results. > >Only the first level could be pluggable allowing to interchange or chain >core dependency testing techniques. I think there will be no use in >making pluggable the higher ones (please, correct me if I am wrong). >This approach would require to divide the analysis structure into two >parts, say; DependenceAnalysis and IndexingTester. > >That said, I must admit I haven't made it that way in my prototype. I >have it in mind, but I'm currently trying to keep things simple and just >to check whether the precision of my implementation is worth anything. > >> Sounds good. If you have the interface nailed down, it would be good >> to post what the query interface looks like. Vikram and others have a >> lot of experience with dependence analysis and know what sorts of >> queries various clients are interested in. They can help give >> feedback on the direction you're pursuing independent of the >> implementation. > >Ok. I'll post it when it crystallizes (what should happen soon). > >> I'd suggest looking at: >> >> Using the chains of recurrences algebra for data dependence testing >> and induction variable substitution >> MS Thesis, Johnie Birch >> >> Array Data Dependence Testing with the Chains of Recurrences Algebra >> http://citeseer.ist.psu.edu/vanengelen04array.html >> >> An empirical evaluation of chains of recurrences for array dependence >> testing >> http://doi.acm.org/10.1145/1152154.1152198 > >I've read the second one, but am not sure if it's easy to implement if >overflow and unknown signedness are taken into account. For now, I will >stick to the classical Banerjee test. If time allows I'll return to the >article. > >>>> From my experience I can say it's essential to use a precise alias >>> analysis as the base for the array dependence analysis. Fortunately, >>> using Data Structure or Andersen's AA for the whole program can >>> provide >>> really good results. >> >> Yep, but any particular dep analysis implementation should just >> require AliasAnalysis instead of a specific implementation. This lets >> the client (e.g. llvm-gcc) decide what passes to plug together. > >You're right. From the implementation point of view the choice of alias >analysis doesn't matter at all. > >Wojtek >_______________________________________________ >LLVM Developers mailing list >LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev