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 >
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<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 <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
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130125/782f1f9f/attachment.html>
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 > >