[llvm-dev] Loop Invariants Detection questions

[Thomas RUBIANO via llvm-dev]

Thank you again Eli,

I would like to know if it's not better to use DependenceAnalysis to know
which instruction depends on others…
I'm running this pass on a simple example:
…
while.body:                                       ; preds = %while.cond
  %1 = load i32, i32* %y, align 4 ← I1
  %2 = load i32, i32* %y, align 4
  %mul = mul nsw i32 %1, %2 ← I2
  store i32 %mul, i32* %z, align 4
  %3 = load i32, i32* %z, align 4
  call void @use(i32 %3)
  %4 = load i32, i32* %x, align 4
  %5 = load i32, i32* %x, align 4
  %add = add nsw i32 %4, %5
  store i32 %add, i32* %y, align 4
  %6 = load i32, i32* %y, align 4
  call void @use(i32 %6)
  %7 = load i32, i32* %x2, align 4
  store i32 %7, i32* %x, align 4
  %8 = load i32, i32* %x, align 4
  call void @use(i32 %8)
  br label %while.cond
…

and here, for instance, I'm expecting to have a dependence between
%1 = load i32, i32* %y, align 4 → I1
… ↓ …
%mul = mul nsw i32 %1, %2 → I2

simply because the %mul uses %1 as input.

But when I dump the dependence "depends(I1,I2,true)" I have nothing… null.
Did I forget something?

On Thu, Jan 19, 2017 at 8:04 PM, Friedman, Eli <efriedma at codeaurora.org>
wrote:

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


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