Valmico <valmico88 at gmail.com> wrote:> I'm currently trying to develop new LLVM Pass that will generate > simple data dependencies graph. For now I'm trying to get familiar > with DependenceAnalysis. > My general idea is to traverse each function (runOnFunction) > top to bottom Instruction by Instruction, using DA.depends( I, I2, ...) > on every Instructions combination in function to check if they are > dependent on any others. > > Problem is that almost all (if not all) Instructions seems to be dependent > on others even if they write/read to/from different memory cells. > Also I'm getting Dependence (confused) object, not the FullDependence, > should i try to dynamically cast it to FullDependence, or is there a way > to determine which Dependence instance i got other way? > > Please help, I'm not an C++ nor LLVM programmer, but PHP-developer, > however i need it done asap. If you can help just a little, give me ahint,> i'll be very, very thankful for ANY support. > > Best Regards > ValmicoHi, The DependenceAnalysis pass isn't reliable yet; it has several errors that need to be corrected. These manifest by the analysis claiming there's no dependence when one in fact exists. Your proposed scheme of testing every pair of instructions is asymptotically expensive, requiring O(n^2) tests, where each test is already fairly expensive. I describe (or start to describe) a better approach here<https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph> . In the meantime, you should be getting better results than you report. You'll want to use several other passes in conjunction with DA. Try something like opt -basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate -simplifycfg -instcombine -indvars -da Also, a confused dependences mean that the analysis wasn't able to prove anything; a FullDependence means the analysis was able to prove some facts, though it wasn't actually able to disprove the dependence. It's not reasonable to cast a Dependence to a FullDependence. Preston -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130808/4d30fe92/attachment.html>
2013/8/8 Preston Briggs <preston.briggs at gmail.com>> > Hi, > > The DependenceAnalysis pass isn't reliable yet; it has several errors that > need to be corrected. These manifest by the analysis claiming there's no > dependence when one in fact exists. > > Your proposed scheme of testing every pair of instructions is > asymptotically expensive, requiring O(n^2) tests, where each test is > already fairly expensive. I describe (or start to describe) a better > approach here<https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph> > . > > In the meantime, you should be getting better results than you report. > You'll want to use several other passes in conjunction with DA. Try > something like > > opt -basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate > -simplifycfg -instcombine -indvars -da > > > Also, a confused dependences mean that the analysis wasn't able to prove > anything; a FullDependence means the analysis was able to prove some facts, > though it wasn't actually able to disprove the dependence. It's not > reasonable to cast a Dependence to a FullDependence. > > Preston > >Hi, I assume that DA is tool capable to give me an list of Dependencies in code or at least a easy way to test instructions without much knowledge about ZIV SIV, and other tests that has to be done find out dependencies? Personally i'm an PHP programmer and i feel lack of proper (at least for me) documentation with good use examples about LLVM, and it's modules like analysis, transforms etc. I agree that testing every pair is asymptotically expensive, requiring O(n^2), but it doesnt matter for me for now. This is code i came up for now: virtual bool runOnFunction(Function &F) { DependenceAnalysis &DA = this->getAnalysis<DependenceAnalysis>(); std::vector<Instruction*> instructions; for( inst_iterator I = inst_begin(F); I != inst_end(F); I++ ) { if( isa<StoreInst>( *I ) || isa<LoadInst>( *I ) ) { errs() << "Instruction " << *I << '\n'; for(std::vector<Instruction*>::iterator it instructions.begin(); it != instructions.end(); it++) { Dependence *dep = DA.depends(&*I,*it,false); if( dep == NULL ) { //errs() << " no dependence." << '\n'; } else if( dep->isConfused() == true ) { if( dep->isInput() ) { errs() << '\t' << **it << " input dependence." << '\n'; } else if( dep->isOutput() ) { errs() << '\t' << **it << " output dependence." << '\n'; } else if( dep->isFlow() ) { errs() << '\t' << **it << " flow dependence." << '\n'; } else if( dep->isAnti() ) { errs() << '\t' << **it << " anti dependence." << '\n'; } } else if( dep->isConfused() == false ) { errs() << "# full dependence." << '\n'; //if( FullDependence *FDep = cast<FullDependence>( dep ) ) { // errs() << " full dep casted" << '\n'; //} } } instructions.push_back(&*I); } } } Most likely i'm moving totally in wrong direction, but thats what happens when people do sth completly blindly. Please dont' bother performance concerns, it's my least problem. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130809/0941c160/attachment.html>
On Fri, Aug 9, 2013 at 1:05 PM, Valmico <valmico88 at gmail.com> wrote:> I assume that DA is tool capable to give me an list of Dependencies incode> or at least a easy way to test instructions without much knowledge aboutZIV SIV,> and other tests that has to be done find out dependencies?DA exists to support building a dependence graph. It checks to see if two instructions may refer to the same location in memory, working hard to understand array references. Someday the code to build a dependence graph will get written, but it doesn't exist yet. The weakness with your scheme, besides performance, is that it may report a dependence between two instructions that are never both executed. For example void zap(...) { if (...) A[0] = ... else A[0] = ... } your approach will claim there's an output dependence between the two stores to A, but in reality, code that executes one will never execute the other, so there can be no dependence.> This is code i came up for now: > > virtual bool runOnFunction(Function &F) { > > DependenceAnalysis &DA = this->getAnalysis<DependenceAnalysis>(); > > std::vector<Instruction*> instructions; > > for( inst_iterator I = inst_begin(F); I != inst_end(F); I++ ) { > if( isa<StoreInst>( *I ) || isa<LoadInst>( *I ) ) { > errs() << "Instruction " << *I << '\n'; > > for(std::vector<Instruction*>::iterator it instructions.begin(); it != instructions.end(); it++) { > Dependence *dep = DA.depends(&*I,*it,false); > if( dep == NULL ) { > //errs() << " no dependence." << '\n'; > } else if( dep->isConfused() == true ) { > if( dep->isInput() ) { > errs() << '\t' << **it << " input dependence." <<'\n';> } else if( dep->isOutput() ) { > errs() << '\t' << **it << " output dependence."<< '\n';> } else if( dep->isFlow() ) { > errs() << '\t' << **it << " flow dependence." <<'\n';> } else if( dep->isAnti() ) { > errs() << '\t' << **it << " anti dependence." <<'\n';> } > } else if( dep->isConfused() == false ) { > errs() << "# full dependence." << '\n'; > //if( FullDependence *FDep = cast<FullDependence>(dep ) ) {> // errs() << " full dep casted" << '\n'; > //} > } > } > > instructions.push_back(&*I); > } > } > }I'm sure an LLVM stud to do a cleaner job, but your code looks plausible. I'll note that anything you do for a confused dependence makes sense for a full dependence. So you can test for input, output, flow, etc. If you look at the code in lib/Analysis/DependenceAnalysis.cpp you can see how I exercise DA (in dumpExampleDependence) and how I print the info associated with a dependence (in Dependence::dump) Preston -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130809/bab0d8c7/attachment.html>