[LLVMdev] llvm alloca dependencies

[Duncan Sands]

Hi Alexandru,

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

>
> 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>> 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
>
>
>
>
> --
> Best regards,
> Alexandru Ionut Diaconescu
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>