llvm alloca dependencies

Project Infrastructure LLVM Dev List Archives
#1

Hello everyone !

I am trying to determine for certain Load instructions from my pass their corresponding Alloca instructions (that can be in other previous blocks). The chain can be something like : TargetLoad(var) -> other stores/loads that use var (or dependencies on var) -> alloca(var). , linked on several basic blocks. Do you know how can I do it?

I tried to use the methods from DependenceAnalysis and MemoryDependenceAnalysis, but the results were not correct. For instance, MemoryDependenceAnalysis::getDependency should be good with option “Def”, but works only for stores, not for loads. Also I have a segfault when trying to use MemoryDependenceAnalysis::getNonLocalPointerDependency or MemoryDependenceAnalysis::getPointerDependencyFrom . When I try to check my result using MemDepResult::getDef(), the result for Load instructions is the same instruction ! So its depending on itself, that being weird since it is using a variable that is previously defined in the code.

I also was no able to use DependenceAnalysis::depends() or getSrc() etc.

The alternative of making the intersection for identifying common parts between all the variables used by target_load_instructions and all the allocated variables is not an option. Because there might be something like : alloca(a) ... c=a*b+4 .... load(c).

Thank you for any suggestion !

#2

This sounds like an alias analysis query that you’re trying to do. There are a couple of options: 1) Cycle through all the allocas and ask if they alias with the loaded pointer. You can use any of the alias analysis implementations available for LLVM. Alternatively, I think LLVM might have a class called AliasSetTracker which can do something similar for you. 2) Use DSA from the poolalloc project. The DSNodeEquivs pass can be used to determine if a load and an alloca alias. Depending on your situation, DSA may give better or worse results than LLVM’s current alias analysis algorithms. I would think that DSA can do a better job for pointers stored into memory locations. – John T.

#3

Hello again,

I want to ask you some piece of advice if it is possible.

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)

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).

First, I tried the point 1) suggested by you. AliasSetTracker uses methods from AliasAnalysis, so I tried to use directly those methods.
After I see all the must-aliases, I categorize them into 2 :

  1. category A : aliases with allocas
  2. category B: aliases without allocas
    For category A, is straight ahead for what I need.
    For category B, I check if there is an instruction where the variable is used also from an instruction from the aliases from category A. If it is, it is ok.

But the following given me no result at all (and they should, I have dependencies - meaning Load j is used multiple times in my code, so the pointers should be must-alias) I have all the Load instructions in an array loadInstrArray. :

  1. if( AA.isMustAlias(Loci,Locj) ) - no result
  2. if( AA.alias(Loci,Locj) ) - wrong results, like “LOAD %2 = load i32* %j, align 4 IS DEPENDENT ON %3 = load i32* %c, align 4”
    where j is totally independent from c
  3. if( AA.getModRefInfo(allocaInstrArray[j],Loci) ) - no result

Second, I tried to use methods from DependencyAnalysis class.

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

Third, I tried methods from MemoryDependenceAnalysis class - the existing pass http://llvm.org/docs/doxygen/html/MemDepPrinter_8cpp_source.html .

  1. I have wrong results, like : %1 = load i32* %j, align 4 IS Clobber FROM: store i32 0, i32* %c, align 4
  2. then I tried to get only DEF (not clobber), since I only need to see the correspondent Alloca for every Load. I don’t have any result for Loads. I also checked with getDef() method, so Loads are dependent on themselves
  3. I have to mention that I commented line 00131, since I had an unsolved segfault and not the parameters are the problem.

Fourth, I took a look in to DSNodeEquivs pass suggested by you. I think that getMemberForValue() method I can use. To be honest, I tried to focus on the classes that are already existent on LLVM.

What do you think I should focus on, what approach is better to take into account and what to eliminate?

Thank you a lot for your time !