[LLVMdev] Memory Dependence Analysis

[Preston Briggs]

Howdy,

I'm working on writing a dependence analyzer (rather like what
LoopDependenceAnalysis wants to be, except a bit more general). While this
is a problem of many parts, I'm currently focusing on finding pairs of
memory references to test for dependence. Consider this contrived C code:

double test2(int n, double *restrict A, double *restrict B, bool flag) {
  if (flag) {
    A[0] = B[0];
    for (int i = 0; i < n; i++)
      A[i] = B[i] + A[i - 1];
  }
  else {
    for (int i = 0; i < n; i++)
      A[i] = A[i] + A[i - 1];
  }
  return A[n - 1];
}


An obvious approach is to test every memory reference against every other
memory reference, but that's O(n^2) in the number of memory references and
is imprecise to boot. In this example, the references to B are surely
disjoint from the references to A. Furthermore, the references to A in the
1st loop have nothing to do with the references to A in the 2nd loop. On
the other hand, the load from A in the return might be dependent on the
stores in both loops as well as the initialization of A[0].

I dreamed up a scheme that computed an SSA form based on alias sets and
worked from there. Then I read about MemoryDependenceAnalysis and noticed
that it claimed to compute the things I wanted. Namely, for every memory
reference (load, store, or call), it could tell me the set of interesting
instructions that might reach the current instruction. Sounds perfect!

I waded into the documentation (it doesn't really return the set of
instructions, instead it returns a pointer to the nearest prior instruction
and I can chase back to find the complete set, more or less) and wrote some
code and many test cases.

It doesn't really seem to behave as I had hoped. It's ok, I can write my
own, but I wondered if perhaps I'm not invoking it properly. Consider this
simpler example

double test2(int n, double *restrict A, double *restrict B) {
  A[0] = B[0];
  for (int i = 0; i < n; i++)
    A[i] = B[i] + A[i - 1];
  return A[n - 1];
}


I invoke opt like this:

opt -load ../../../../Debug/lib/preston.dylib -basicaa -mem2reg
-simplifycfg -loop-simplify -loop-rotate -simplifycfg --preston
--debug-pass=Structure < test.bc  > /dev/null


in an effort to simplify things a bit. This gives me pretty straightforward
code with 3 basic blocks. When I look at the loads using
MDA->getDependency(), we find that they are both NonLocal, which makes
sense. Chasing further, with MDA->getNonLocalPointerDependency(), I get a
vector of basic blocks (the 1st and 2nd, as expected), along with
indications that the query isUnknown. That surprised me; I had expected
that it would suggest isClobber for both loads and both blocks.  Am I doing
something wrong?  Or perhaps not chasing far enough?  Or perhaps
MemoryDependenceAnalysis is just not designed to solve my problem?

Below is an example of the sort of code I'm writing to learn my way around.
I apologize for giving people a chunk of code to read, but perhaps it will
help.

Thanks,
Preston


    // iterate over instructions in block
    for (BasicBlock::iterator i = b->begin(), e = b->end(); i != e; ++i) {
      errs() << *i << "\n";

      // look for loads and stores
      if (i->mayReadFromMemory() || i->mayWriteToMemory()) {

// get dependence for this instruction
MemDepResult d = MDA->getDependency(i);

if (d.isClobber())
  errs() << "clobber " << *(d.getInst());
if (d.isDef())
  errs() << "def " << *(d.getInst());
if (d.isNonLocal()) {
  errs() << "\tnot defined in this block\n";
  BasicBlock *bb = i->getParent();
  SmallVectorImpl<NonLocalDepResult> result(4);
  bool isLoad = false;
  AliasAnalysis::Location loc;
  if (StoreInst *store = dyn_cast<StoreInst>(i))
    loc = AA->getLocation(store);
  else if (LoadInst *load = dyn_cast<LoadInst>(i)) {
    loc = AA->getLocation(load);
    isLoad = true;
  }
  else
    errs() << "pow!";

  MDA->getNonLocalPointerDependency(loc, isLoad, bb, result);

  for (SmallVectorImpl<NonLocalDepResult>::iterator it=result.begin() ; it
< result.end(); it++ ) {
    errs() << "\tblock " << it->getBB() << " ";
    MemDepResult dd = it->getResult();
    if (dd.isClobber())
      errs() << "clobber\n";
    else if (dd.isDef())
      errs() << "def\n";
    else {
      if (dd.isNonLocal())
errs() << "nonLocal\n";
      if (dd.isNonFuncLocal())
errs() << "nonFuncLocal\n";
      if (dd.isUnknown())
errs() << "Unknown\n";
    }
  }
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111213/a7f8fb7d/attachment.html>