<div><div>Howdy,</div></div><div><br></div>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:<div>
<br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><span style="font-family:'courier new',monospace">double test2(int n, double *restrict A, double *restrict B, bool flag) {</span></div>
</div><div><span style="font-family:'courier new',monospace"> if (flag) {</span></div><div><div><span style="font-family:'courier new',monospace"> A[0] = B[0];</span></div>
</div><div><div><span style="font-family:'courier new',monospace"> for (int i = 0; i < n; i++)</span></div></div><div><div><span style="font-family:'courier new',monospace"> A[i] = B[i] + A[i - 1];</span></div>
</div><div><span style="font-family:'courier new',monospace"> }</span></div><div><span style="font-family:'courier new',monospace"> else {</span></div><div>
<div><div><span style="font-family:'courier new',monospace"> for (int i = 0; i < n; i++)</span></div></div><div><div><span style="font-family:'courier new',monospace"> A[i] = A[i] + A[i - 1];</span></div>
</div><div></div></div><div><span style="font-family:'courier new',monospace"> }</span></div><div><span style="font-family:'courier new',monospace"> return A[n - 1];</span></div>
<div><div><span style="font-family:'courier new',monospace">}</span></div></div></blockquote><div><div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><br></div></blockquote>
<div>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].</div>
<div><br></div>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!<br>
</div><div><br></div><div>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.</div>
<div><br></div><div>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</div><div><br></div></div>
<blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><div><font class="Apple-style-span" face="'courier new', monospace">double test2(int n, double *restrict A, double *restrict B) {</font></div>
</div></div><div><div><div><font class="Apple-style-span" face="'courier new', monospace"> A[0] = B[0];</font></div></div></div><div><div><div><font class="Apple-style-span" face="'courier new', monospace"> for (int i = 0; i < n; i++)</font></div>
</div></div><div><div><div><font class="Apple-style-span" face="'courier new', monospace"> A[i] = B[i] + A[i - 1];</font></div></div></div><div><div><div><font class="Apple-style-span" face="'courier new', monospace"> return A[n - 1];</font></div>
</div></div><div><div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div></div></div></blockquote><div><div><br></div><div>I invoke opt like this:</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px">
<div><div><div><font class="Apple-style-span" face="'courier new', monospace">opt -load ../../../../Debug/lib/preston.dylib -basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate -simplifycfg --preston --debug-pass=Structure < test.bc > /dev/null</font></div>
</div></div></blockquote><div><div><br></div><div>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?</div>
<div><br></div><div>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.</div><div><br></div><div>Thanks,</div><div>
Preston</div><div><br></div><div><br></div><div><div><div><font class="Apple-style-span" face="'courier new', monospace"> // iterate over instructions in block</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> for (BasicBlock::iterator i = b->begin(), e = b->end(); i != e; ++i) {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> errs() << *i << "\n";</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> // look for loads and stores</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> if (i->mayReadFromMemory() || i->mayWriteToMemory()) {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>// get dependence for this instruction</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>MemDepResult d = MDA->getDependency(i);</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><br>
</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>if (d.isClobber())</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> errs() << "clobber " << *(d.getInst());</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>if (d.isDef())</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> errs() << "def " << *(d.getInst());</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>if (d.isNonLocal()) {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> errs() << "\tnot defined in this block\n";</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> BasicBlock *bb = i->getParent();</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> SmallVectorImpl<NonLocalDepResult> result(4);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> bool isLoad = false;</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> AliasAnalysis::Location loc;</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> if (StoreInst *store = dyn_cast<StoreInst>(i))</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> loc = AA->getLocation(store);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> else if (LoadInst *load = dyn_cast<LoadInst>(i)) {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> loc = AA->getLocation(load);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> isLoad = true;</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> }</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> else</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> errs() << "pow!";</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> MDA->getNonLocalPointerDependency(loc, isLoad, bb, result);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> for (SmallVectorImpl<NonLocalDepResult>::iterator it=result.begin() ; it < result.end(); it++ ) {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> errs() << "\tblock " << it->getBB() << " ";</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> MemDepResult dd = it->getResult();</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> if (dd.isClobber())</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> errs() << "clobber\n";</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> else if (dd.isDef())</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> errs() << "def\n";</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> else {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> if (dd.isNonLocal())</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>errs() << "nonLocal\n";</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> if (dd.isNonFuncLocal())</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>errs() << "nonFuncLocal\n";</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> if (dd.isUnknown())</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>errs() << "Unknown\n";</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> }</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> }</font></div>
</div></div><div><br></div><div><br></div>
</div>