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 result(4);
bool isLoad = false;
AliasAnalysis::Location loc;
if (StoreInst *store = dyn_cast(i))
loc = AA->getLocation(store);
else if (LoadInst *load = dyn_cast(i)) {
loc = AA->getLocation(load);
isLoad = true;
}
else
errs() << “pow!”;
MDA->getNonLocalPointerDependency(loc, isLoad, bb, result);
for (SmallVectorImpl::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”;
}
}