[LLVMdev] Memory Dependence Analysis: getNonLocalDependency()

[Owen Anderson]

On Jul 28, 2008, at 3:47 PM, Prakash Prabhu wrote:

> Hi,
>
> I have a question about the memory dependence analysis. I am trying  
> to use it to selectively enumerate a set of pairs of (load, store)  
> instructions for every function by calling getNonLocalDependency()  
> on the MemoryDependenceAnalysis. This populates a  
> DenseMap<BasicBlock*, Value*>. I just looked up an usage of this in  
> GVN.cpp:
>
> MD->getNonLocalDependency(C, deps);
>
> for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(),
>            E = deps.end(); I != E; ++I) {
>         if (I->second == MemoryDependenceAnalysis::None) {
>          ....
>         } else if (I->second != MemoryDependenceAnalysis::NonLocal) {
>             ....
>           } else {
>              ....
>           }
>         }
>       }
>
> From the documentation, I got to know that MD can return the set of  
> inter-block dependencies for any instruction (which is great!).
> My question is: what does None, Local and NonLocal (special markers  
> defined in MemoryDependenceAnalysis.cpp) mean in this context ?

None signals that the analysis reached the beginning of the function  
(or an unreachable block with no predecessors) without finding a  
dependency.  NonLocal marks blocks which it searched, and did not find  
a dependency within.  There is no Local flag.  ;-)
>
> Given a store statement, my objective is to identify other load  
> statements that it is dependent on ? I tried this code and it seems  
> to run, but I wanted to make sure I am not missing anything (as a  
> consequence of not knowing the semantics of None, Local and  
> NonLocal) :
>
>     for (DenseMap<BasicBlock*, Value*>::iterator B = depMap.begin(),
>                                 E = depMap.end(); B != E; B++)
>     {
>         if (B->second == MemoryDependenceAnalysis::None ||     B- 
> >second == MemoryDependenceAnalysis::NonLocal)
>             continue;
>         Value* depV = B->second;
>         if (isa<LoadInst>(depV))
>         {
>             ...
>          }
>      }
>

You might want a special case for None, since you may need to bail out  
if there is a path from entry to your instruction that does not  
contain a dependency.  Otherwise, it looks fine offhand.

As an aside, memdep could really be cleaned up.  It is fairly tailored  
to the kind of queries that DSE and GVN care about.  It would be kind  
of nice if, say, it took a flag to indicate if you care about Load- 
Load, Load-Store, Store-Load, or Store-Store dependencies.  Something  
to add to that grand to-do list in the sky.

--Owen