[LLVMdev] Accurate (non-local) memory dependence analysis

[Ignacio Laguna]

Hi everyone,

Is there any LLVM pass to get memory dependencies for may- and 
most-alias cases? I tried using (and reading the code of) 
'MemoryDependenceAnalysis' and 'MemDepPrinter', but all I'm able to 
infer are "local" memory dependencies, that is, within the same basic 
block. When the dependence is found to be non-local (e.g., from another 
basic block), the interface doesn't tell me the instruction it depends on.

Here's an example (optimizing with -mem2reg):

int main()
{
	int size = 3;
	double x[size];
	x[0] = 1.0;
	x[1] = 2.0;
	x[2] = 3.0;
	
	if (size == 3)
	{
		// do something
		x[2] = 100;
	}

	x[0] = x[1] + 1.0;
	
	return 0;
}

entry:
   %0 = zext i32 3 to i64
   %1 = call i8* @llvm.stacksave()
   %vla = alloca double, i64 %0, align 16
   %arrayidx = getelementptr inbounds double* %vla, i64 0
   store double 1.000000e+00, double* %arrayidx, align 8
   %arrayidx1 = getelementptr inbounds double* %vla, i64 1
   store double 2.000000e+00, double* %arrayidx1, align 8
   %arrayidx2 = getelementptr inbounds double* %vla, i64 2
   store double 3.000000e+00, double* %arrayidx2, align 8
   %cmp = icmp eq i32 3, 3
   br i1 %cmp, label %if.then, label %if.end

if.then:                            ; preds = %entry
   %arrayidx3 = getelementptr inbounds double* %vla, i64 2
   store double 1.000000e+02, double* %arrayidx3, align 8
   br label %if.end

if.end:                             ; preds = %if.then, %entry
   %arrayidx4 = getelementptr inbounds double* %vla, i64 1
   %2 = load double* %arrayidx4, align 8
   %add = fadd double %2, 1.000000e+00
   %arrayidx5 = getelementptr inbounds double* %vla, i64 0
   store double %add, double* %arrayidx5, align 8
   call void @llvm.stackrestore(i8* %1)
   ret i32 0

I would like to find that the load in instruction %2 (in if.end) may 
depend on the second store instruction in entry, since they access the 
same memory location (and "if.end" post-dominates "entry"). However, 
using the "MemoryDependenceAnalysis" pass, I'm only able to know that 
there is a non-local dependence (the found instruction is always NULL).

I use this code (for non-local dependencies):

MemoryDependenceAnalysis *MDA;
....
SmallVector<NonLocalDepResult, 4> NLDI;
MDA->getNonLocalPointerDependency(loc, isLoad, inst->getParent(), NLDI);
for (SmallVectorImpl<NonLocalDepResult>::const_iterator I = 
NLDI.begin(), E = NLDI.end(); I != E; ++I)
{
   const MemDepResult &depRes = I->getResult();
   if (depRes.getInst())
   {
     // But this instruction is NULL...
   }
}

Is this because this analysis is conservative (only covers must-alias, 
and not may-alias cases)?

Thank you!


-- 
Ignacio Laguna
Center for Applied Scientific Computing (CASC)
Lawrence Livermore National Laboratory