llvm dev - Jan 2017 - Loop Invariants Detection questions

Hi all!

I'm new here, and would like to implement my own Loop Invariant Detection
adding some more information on Quasi-Invariants.

First, is there anything about Quasi-Invariants detection in LLVM I would
missed?

I've seen LICM using LoopInfo::isLoopInvariant for finding invariants.
It seems that this method considers a Value invariant if:
- it's an Instruction not presents in the current loop (what does it mean?
There is no dependence analysis on In and Out "variables" of all
instructions in the loop?)
- this Value is not an Instruction (then a Constant I guess…).

I've seen LoopAccessAnalysis using it too. What does this analysis do
exactly on loop invariant address?

Also DependenceAnalysis seems to give dependence information on memory
refs. But it seems to not be used by LICM…

Also MemoryDependenceAnalysis "determines, for a given memory operation,
what preceding memory operations it depends on".

My question is: Where is really done this dependence analysis. The one
which figures out which Instructions depends on others?

Simply if I have:
%0 = load i32, i32* %coucou, align 4
%1 = load i32, i32* %fact, align 4
%2 = load i32, i32* %i, align 4
%mul = mul nsw i32 %1, %2

mul instruction will depends on the two precedents loads because it uses
their results %1 and %2 but not the first one.

I guess this is done somewhere, and there is a special representation of
this information but I didn't find, I'm a bit lost ^^'

Is someone can show me the way? Or just explain what he knows about
Invariants and Instructions dependencies detection in LLVM… or just a good
link I should follow…

Ty :)

-- 
Thomas
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170117/d80ebdd6/attachment.html>

On 1/17/2017 7:12 AM, Thomas RUBIANO via llvm-dev wrote:
> Hi all!
>
> I'm new here, and would like to implement my own Loop Invariant 
> Detection adding some more information on Quasi-Invariants.
>
> First, is there anything about Quasi-Invariants detection in LLVM I 
> would missed?
>
> I've seen LICM using LoopInfo::isLoopInvariant for finding invariants.
> It seems that this method considers a Value invariant if:
> - it's an Instruction not presents in the current loop (what does it 
> mean? There is no dependence analysis on In and Out "variables"
of all
> instructions in the loop?)
isLoopInvariant just checks whether the definition of a value is an 
instruction inside the loop.
> - this Value is not an Instruction (then a Constant I guess…).
Or an function argument, or a few other obscure things which don't 
really matter in this context.
> I've seen LoopAccessAnalysis using it too. What does this analysis do 
> exactly on loop invariant address?
ScalarEvolution::isLoopInvariant works on SCEV expressions instead of 
Values, but it's essentially the same thing.
>
> Also DependenceAnalysis seems to give dependence information on memory 
> refs. But it seems to not be used by LICM…
Yes, the current LICM uses alias analysis in a more direct manner (look 
for AliasSetTracker).
>
> Also MemoryDependenceAnalysis "determines, for a given memory 
> operation, what preceding memory operations it depends on".
>
> My question is: Where is really done this dependence analysis. The one 
> which figures out which Instructions depends on others?
>
> Simply if I have:
> %0 = load i32, i32* %coucou, align 4
> %1 = load i32, i32* %fact, align 4
> %2 = load i32, i32* %i, align 4
> %mul = mul nsw i32 %1, %2
>
> mul instruction will depends on the two precedents loads because it 
> uses their results %1 and %2 but not the first one.
>
> I guess this is done somewhere, and there is a special representation 
> of this information but I didn't find, I'm a bit lost ^^'
If you call "operands()" on the Instruction, it will return %1 and %2.
Please keep in mind that LLVM IR is SSA.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

Ty Eli for your answer.

On Tue, Jan 17, 2017 at 8:11 PM, Friedman, Eli <efriedma at
codeaurora.org>
wrote:
> On 1/17/2017 7:12 AM, Thomas RUBIANO via llvm-dev wrote:
>
>> Hi all!
>>
>> I'm new here, and would like to implement my own Loop Invariant
Detection
>> adding some more information on Quasi-Invariants.
>>
>> First, is there anything about Quasi-Invariants detection in LLVM I
would
>> missed?
>>
>> I've seen LICM using LoopInfo::isLoopInvariant for finding
invariants.
>> It seems that this method considers a Value invariant if:
>> - it's an Instruction not presents in the current loop (what does
it
>> mean? There is no dependence analysis on In and Out
"variables" of all
>> instructions in the loop?)
>>
>
> isLoopInvariant just checks whether the definition of a value is an
> instruction inside the loop.
>
Ok, the term "definition" makes it clear. Do, if here it's:
%1 = load i32, i32* %fact, align 4
%mul = mul nsw i32 %1, %2


load i32, i32* %fact, align 4 is the def of %1 and it's inside the loop
then it's not invariant…

> - this Value is not an Instruction (then a Constant I guess…).
>>
>
> Or an function argument, or a few other obscure things which don't
really
> matter in this context.
>
> I've seen LoopAccessAnalysis using it too. What does this analysis do
>> exactly on loop invariant address?
>>
>
> ScalarEvolution::isLoopInvariant works on SCEV expressions instead of
> Values, but it's essentially the same thing.
>
What can offer this SCEV expression more than Values?
>
>
>> Also DependenceAnalysis seems to give dependence information on memory
>> refs. But it seems to not be used by LICM…
>>
>
> Yes, the current LICM uses alias analysis in a more direct manner (look
> for AliasSetTracker).
>
>
>> Also MemoryDependenceAnalysis "determines, for a given memory
operation,
>> what preceding memory operations it depends on".
>>
>> My question is: Where is really done this dependence analysis. The one
>> which figures out which Instructions depends on others?
>>
>> Simply if I have:
>> %0 = load i32, i32* %coucou, align 4
>> %1 = load i32, i32* %fact, align 4
>> %2 = load i32, i32* %i, align 4
>> %mul = mul nsw i32 %1, %2
>>
>> mul instruction will depends on the two precedents loads because it
uses
>> their results %1 and %2 but not the first one.
>>
>> I guess this is done somewhere, and there is a special representation
of
>> this information but I didn't find, I'm a bit lost ^^'
>>
>
> If you call "operands()" on the Instruction, it will return %1
and %2.
> Please keep in mind that LLVM IR is SSA.
>
Yes but if I understand well, the AliasSetTracker can tell me which load it
corresponds to…
How can I use this AliasSetTracker to disambiguate the registers?
Here it's just having the correspondence %1 → %fact and %2 → %i

It would be just perfect for me to have the "real" In and Out of each
Instruction.
Maybe I should work on another level or with another object representation?

Ty again :)
>
> -Eli
>
> --
> Employee of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
> Foundation Collaborative Project
>
>

-- 
 RUBIANO Thomas
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170118/51d879ce/attachment.html>