[LLVMdev] How to gather data dependences

[Preston Briggs]

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 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?

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>