[LLVMdev] llvm alloca dependencies

[Duncan Sands]

Hi Alexandru,

On 25/01/13 13:47, Alexandru Ionut Diaconescu wrote:
> 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.

>
> Sorry if the question was asked without any testing with optimizations enabled.
>
> Basically, my plan is :
>
> if (Inst->getOpcode()==Instruction::Load)
>      {
>          LoadInst *LD10 = cast<LoadInst>(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 !
>
>
>     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.
>
>
>         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
>
>
>
>         On Thu, Jan 24, 2013 at 6:03 PM, Preston Briggs
>         <preston.briggs at gmail.com <mailto:preston.briggs at gmail.com>
>         <mailto:preston.briggs at gmail.__com <mailto:preston.briggs at gmail.com>>>
>         wrote:
>
>               > 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
>
>