[llvm-dev] Loop Invariants Detection questions

[Friedman, Eli via llvm-dev]

On 1/19/2017 2:16 AM, Thomas RUBIANO wrote:
>
>
> On Wed, Jan 18, 2017 at 8:05 PM, Friedman, Eli 
> <efriedma at codeaurora.org <mailto: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 <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?
>
>
> I was looking the LoopInvariantCodeMotion::runOnLoop.
>
> No I didn't run mem2reg on my IR…
> Is it necessary?

It's not necessary for correctness, but if you want to understand how 
the LLVM optimizer works in practice, you'll want to look at realistic 
input to LICM.

>
> 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?

Yes, you can use an Instruction* to identify an instruction.

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