llvm dev - Jan 2017 - Loop Invariants Detection questions

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>

On 1/18/2017 2:56 AM, Thomas RUBIANO wrote:
> Ty Eli for your answer.
>
> On Tue, Jan 17, 2017 at 8:11 PM, Friedman, Eli 
> <efriedma at codeaurora.org <mailto: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…
Exactly.  If LICM can prove the load is in fact invariant, it will move 
it out of 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.
>
>
> What can offer this SCEV expression more than Values?
See the comment at the beginning of lib/Analysis/ScalarEvolution.cpp for 
a brief description and some references.
>
>
>         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 :)
Can you show me the complete function you're looking at?  Have you run 
mem2reg on your IR?

-Eli

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

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

On Wed, Jan 18, 2017 at 8:05 PM, Friedman, Eli <efriedma at
codeaurora.org>
wrote:
> On 1/18/2017 2:56 AM, Thomas RUBIANO wrote:
>
> 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…
>
>
> Exactly.  If LICM can prove the load is in fact invariant, it will move it
> out of 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.
>>
>
> What can offer this SCEV expression more than Values?
>
>
> See the comment at the beginning of lib/Analysis/ScalarEvolution.cpp for
> a brief description and some references.
>
>
>>
>>> 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 :)
>
>
> Can you show me the complete function you're looking at?  Have you run
> mem2reg on your IR?
>
I was looking the LoopInvariantCodeMotion::runOnLoop.

No I didn't run mem2reg on my IR…
Is it necessary?

I finally use the address of the operands and instruction to have a kind of
ID of each %<num>
It seems that it refers well what I want…

Let be the Instruction I:
%0 = mul nsw i32 %1, %2

&I = 0x3d9f850 → %0
operands(0)→get() = 0x3d9f7bc → %1
operands(1)→get() = 0x3d9f80c → %2

then it should be ok if I take this for finding my dependencies between
Instructions?

>
> -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/20170119/14a05939/attachment.html>