Memory Dependence Analysis: getNonLocalDependency()

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 ?
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(depV))
{

}
}

Thanks in advance for any pointers!

  • Prakash

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. :wink:

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

Thanks for the quick reply, Owen. I went through the code in MemoryDependenceAnalysis.cpp again. Since DenseMap<BasicBlock*, Value*> maps a BasicBlock to a single Value (Instruction) and it is populated by a DFS on the reverse Control Flow Graph starting at the query instruction’s block, is it correct to say that the last dependent instruction in each visited basic block is what is mapped ? For example, if a basicblock B has two instructions:

B:

store i32 1, i32* %i, align 4 (say inst1)

load i32* %i, align 4 ; :39 [#uses=1] (say inst2)

and suppose i had one more Store instruction to %i outside B which is the query, then when B is visited, in the DenseMap only the mapping <B, inst2> is added and not <B, inst1> ?

I am guessing that this information is sufficient for most code-hoisting optimizations since just the knowledge that a basic block has some load/store instruction accessing the same (modulo the pointer analysis) address is sufficient to prevent the transformation from causing an unsafe code-movement ?

thanks,
Prakash

Yup, that's exactly right.

--Owen