llvm dev - Jul 2008 - [LLVMdev] 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<LoadInst>(depV))
        {
            ...
         }
     }

Thanks in advance for any pointers!

- Prakash
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080728/daa0b6ee/attachment.html>

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

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           ; <i32>: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


On Mon, Jul 28, 2008 at 7:40 PM, Owen Anderson <resistor at mac.com>
wrote:
>
> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080728/73205f8a/attachment.html>