llvm dev - Jan 2017 - Loop Invariants Detection questions

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>

On 1/20/2017 4:43 AM, Thomas RUBIANO wrote:
> 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?
DependenceAnalysis computes whether the memory accesses in two 
instructions overlap.  A multiply doesn't access memory, therefore the 
memory accesses don't overlap.

-Eli

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

Yes, in fact I was not searching for that bur more dependence between
instructions.
And we can have that by recursively search on operands. I didn't know that
thank to the SSA form, operands give us the associated assignment
instructions then the potentially dependence tree.

Thank you for your help Eli :)

On Fri, Jan 20, 2017 at 7:23 PM, Friedman, Eli <efriedma at
codeaurora.org>
wrote:
> On 1/20/2017 4:43 AM, Thomas RUBIANO wrote:
>
>> 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?
>>
>
> DependenceAnalysis computes whether the memory accesses in two
> instructions overlap.  A multiply doesn't access memory, therefore the
> memory accesses don't overlap.
>
>
> -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/7076b9ce/attachment.html>