llvm alloca dependencies

I tried methods related to point 1) suggested by you,
but I still have problems of finding dependencies.
What exactly I want to do:

I have a chain like : Alloca → Load(1) → … → Computation
where the variable might be changed → Store(new_var) → … → Load(n)

Your example is not very clear.
I don’t understand what’s involved in the “chain”.

Computation where the variable is changed = means that :
I might have Alloca(a), c=a+7000*b[32], Load(c)…ICMP(c, …)

I want to get the corresponding Alloca from every Load
(corresponding from the point of view of the variable used,
meaning that the Load is using a variables based/dependent on the Alloca or Allocas).

I don’t know any magical LLVM way to get all the answers.
My approach would be to do some ordinary data-flow analysis,
chasing back along def-use chains to find instructions that define
the registers used in the load, recursively, to the beginning.
If you hit an alloca, stop.

I tried to use methods from DependencyAnalysis class.

DependenceAnalysis. Seems like a bad start.
Dependence analysis is used to determine how two
array references may interact. Nothing to do with alloca.

  1. if (DA.depends(loadInstrArray[i],loadInstrArray[j],false)) - no result

I can’t say if this is correct or not without a more complete example.
For instance, in the code

for (i = 0; i < n; i += 2) {
loadInstr[i] = 0;
j = i + 1;
loadInstr[j] = 1;
}

there is no dependence between the two stores to loadInstr.
The two stores write entirely disjoint areas of memory.
On the other hand, if we have

for (i = 0; i < n; i++) {
loadInstr[i] = 0;
j = 2*i;
loadInstr[j] = 1;
}

we expect to find a more interesting pattern.

Preston

Thank you a lot for your response. I will try to use your approach with chasing back along def-use chains to find instructions that define the registers used in the load. Can you tell me please what class/methods/existing path are good for this? I assume that I must have a method with arguments like the variable used into a Load instruction and a “stop instruction”, like an Alloca.

However, if I have something like :

I1 : %a = alloca i32, align 4

I2 : %5 = load i32* %a, align 4
I3 : %b = add i32 %a, %c

I4 : %8 = load i32* %b, align 4

I4 is dependent on I1 since %8 is obtained using %a (indirectly)

I think it is better to check dependencies also between loads (for the case when a Load is not directly linked to an Alloca), so I can identify :

if ( ( I2 is dependent on I1 ) and ( I3 is dependent on I4 ) ) => I can check if I3 and I2 are dependent => indirectly I4 is dependent on I1

Hi Alexandru,

Thank you a lot for your response. I will try to use your approach with chasing
back along def-use chains to find instructions that define the registers used in
the load. Can you tell me please what class/methods/existing path are good for
this? I assume that I must have a method with arguments like the variable used
into a Load instruction and a "stop instruction", like an Alloca.

However, if I have something like :

I1 : %a = alloca i32, align 4
....
I2 : %5 = load i32* %a, align 4
I3 : %b = add i32 %a, %c
....
I4 : %8 = load i32* %b, align 4

I4 is dependent on I1 since %8 is obtained using %a (indirectly)

if the above is all that is happening with your alloca then the optimizers will
eliminate the alloca altogether. In optimized code you will pretty much only
have an alloca if the address of the alloca escapes the function. I suggest you
assume you are analysing optimized code, because it is much much easier to do
analysis with registers and phi nodes than to analyse memory accesses, and in
most cases the optimizers will do all the analysis for you and eliminate the
memory accesses.

Ciao, Duncan.

Hello Duncan,

I compiled LLVM without optimizations (because maybe I have to look to memory accesses in the future).
Maybe some of these optimizations I can enable when I am running my pass with opt ?

It is still one thing that I don’t understand. If the memory accesses will be eliminated, and I have the following situation:

%i = alloca i32, align 4
%j = alloca i32, align 4

%2 = load i32* %i, align 4
%3 = load i32* %j, align 4
%add = add nsw i32 %2, %3
%cmp2 = icmp sgt i32 %add, 2

How can I check that %cmp2 is dependent on both allocas?

Sorry if the question was asked without any testing with optimizations enabled.

Basically, my plan is :

if (Inst->getOpcode()==Instruction::Load)
{
LoadInst *LD10 = cast(Inst);
Value *C10 = LD10->getPointerOperand();
}

so I get all the good allocas. Then my plan is to check for each ICMP (thats what i have to do) the first or second operand and recursively proceed till I find only Load instructions and then get the corresponding allocas.

Thank you for your response !

Hi Alexandru,

Hello Duncan,

I compiled LLVM without optimizations (because maybe I have to look to memory
accesses in the future).

I think you are making life hard for yourself. You are trying to redo yourself
all kinds of tricky reasoning that the optimizers already know how to do.

Maybe some of these optimizations I can enable when I am running my pass with opt ?

Run at least mem2reg or sroa, and I suggest instcombine too.

It is still one thing that I don't understand. If the memory accesses will be
eliminated, and I have the following situation:

%i = alloca i32, align 4
%j = alloca i32, align 4
.....
%2 = load i32* %i, align 4
%3 = load i32* %j, align 4
%add = add nsw i32 %2, %3
%cmp2 = icmp sgt i32 %add, 2

How can I check that %cmp2 is dependent on both allocas?

As the allocas won't exist any more, there is nothing to check! I suggest you
just run some of the examples you have through all of the optimizers (using
"opt -std-compile-opts" for example) to see what they can handle for you, and
what they can't handle. Forget about analysing unoptimized code, there's no
point and it's too hard.

Ciao, Duncan.