<div dir="ltr"><div><div><div><div><div><div>Thank you again Eli,<br><br></div>I would like to know if it's not better to use DependenceAnalysis to know which instruction depends on others…<br></div>I'm running this pass on a simple example:<br>…<br>while.body: ; preds = %while.cond<br> %1 = load i32, i32* %y, align 4 ← I1<br> %2 = load i32, i32* %y, align 4<br> %mul = mul nsw i32 %1, %2 ← I2<br> store i32 %mul, i32* %z, align 4<br> %3 = load i32, i32* %z, align 4<br> call void @use(i32 %3)<br> %4 = load i32, i32* %x, align 4<br> %5 = load i32, i32* %x, align 4<br> %add = add nsw i32 %4, %5<br> store i32 %add, i32* %y, align 4<br> %6 = load i32, i32* %y, align 4<br> call void @use(i32 %6)<br> %7 = load i32, i32* %x2, align 4<br> store i32 %7, i32* %x, align 4<br> %8 = load i32, i32* %x, align 4<br> call void @use(i32 %8)<br> br label %while.cond<br>…<br><br></div>and here, for instance, I'm expecting to have a dependence between <br>%1 = load i32, i32* %y, align 4 → I1<br>… ↓ …<br> %mul = mul nsw i32 %1, %2 → I2<br><br></div>simply because the %mul uses %1 as input.<br><br></div>But when I dump the dependence "depends(I1,I2,true)" I have nothing… null.<br></div>Did I forget something?<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 19, 2017 at 8:04 PM, Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"><div><div class="h5">
<div class="m_-2000578491068410997moz-cite-prefix">On 1/19/2017 2:16 AM, Thomas RUBIANO
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Jan 18, 2017 at 8:05 PM,
Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>
wrote:<br>
<blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<div bgcolor="#FFFFFF"><span class="m_-2000578491068410997gmail-">
<div class="m_-2000578491068410997gmail-m_-1396804328854282964moz-cite-prefix">On
1/18/2017 2:56 AM, Thomas RUBIANO wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Ty Eli for your answer.<br>
<div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Tue, Jan 17, 2017
at 8:11 PM, Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">On
1/17/2017 7:12 AM, Thomas RUBIANO via
llvm-dev wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> Hi
all!<br>
<br>
I'm new here, and would like to
implement my own Loop Invariant
Detection adding some more information
on Quasi-Invariants.<br>
<br>
First, is there anything about
Quasi-Invariants detection in LLVM I
would missed?<br>
<br>
I've seen LICM using
LoopInfo::isLoopInvariant for finding
invariants.<br>
It seems that this method considers a
Value invariant if:<br>
- 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?)<br>
</blockquote>
<br>
</span> isLoopInvariant just checks
whether the definition of a value is an
instruction inside the loop.<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-"><br>
</span></blockquote>
<div><br>
</div>
<div>Ok, the term "definition" makes it
clear. Do, if here it's:<br>
<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">%1
= load i32, i32* %fact, align 4</span><br>
<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">%mul
= mul nsw i32 %1, %2<br>
<br>
</span><br>
<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">load
i32, i32* %fact, align 4 is the def of
%1 and it's inside the loop then it's
not invariant…<br>
</span></div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
</span> Exactly. If LICM can prove the load is in fact
invariant, it will move it out of the loop.<span class="m_-2000578491068410997gmail-"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div>
<div class="gmail_extra">
<div class="gmail_quote">
<div><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-"><br>
</span></div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> -
this Value is not an Instruction (then
a Constant I guess…).<br>
</blockquote>
<br>
</span> Or an function argument, or a few
other obscure things which don't really
matter in this context.<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-"><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
I've seen LoopAccessAnalysis using it
too. What does this analysis do
exactly on loop invariant address?<br>
</blockquote>
<br>
</span> ScalarEvolution::isLoopInvaria<wbr>nt
works on SCEV expressions instead of
Values, but it's essentially the same
thing.<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-"><br>
</span></blockquote>
<div><br>
</div>
<div>What can offer this SCEV expression
more than Values? <br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
</span><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">See
the comment at the beginning of
lib/Analysis/ScalarEvolution.c<wbr>pp for a brief
description and some references.</span><span class="m_-2000578491068410997gmail-"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-"></span><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div>
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> <br>
Also DependenceAnalysis seems to give
dependence information on memory refs.
But it seems to not be used by LICM…<br>
</blockquote>
<br>
</span> Yes, the current LICM uses alias
analysis in a more direct manner (look for
AliasSetTracker).<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-"><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> <br>
Also MemoryDependenceAnalysis
"determines, for a given memory
operation, what preceding memory
operations it depends on".<br>
<br>
My question is: Where is really done
this dependence analysis. The one
which figures out which Instructions
depends on others?<br>
<br>
Simply if I have:<br>
%0 = load i32, i32* %coucou, align 4<br>
%1 = load i32, i32* %fact, align 4<br>
%2 = load i32, i32* %i, align 4<br>
%mul = mul nsw i32 %1, %2<br>
<br>
mul instruction will depends on the
two precedents loads because it uses
their results %1 and %2 but not the
first one.<br>
<br>
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 ^^'<br>
</blockquote>
<br>
</span> If you call "operands()" on the
Instruction, it will return %1 and %2.
Please keep in mind that LLVM IR is SSA.<span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-HOEnZb"><font color="#888888"><br>
</font></span></blockquote>
<div><br>
</div>
<div>Yes but if I understand well, the
AliasSetTracker can tell me which load it
corresponds to… <br>
How can I use this AliasSetTracker to
disambiguate the registers?<br>
</div>
<div>Here it's just having the
correspondence %1 → %fact and %2 → %i <br>
</div>
<div><br>
</div>
<div>It would be just perfect for me to have
the "real" In and Out of each Instruction.<br>
</div>
<div>Maybe I should work on another level or
with another object representation?<br>
</div>
<div><br>
</div>
<div>Ty again :)<br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
</span> Can you show me the complete function you're
looking at? Have you run mem2reg on your IR?<span class="m_-2000578491068410997gmail-"><br>
</span></div>
</blockquote>
<div><br>
</div>
<div>I was looking the LoopInvariantCodeMotion::<wbr>runOnLoop.<br>
<br>
</div>
<div>No I didn't run mem2reg on my IR…<br>
</div>
<div>Is it necessary?<br>
</div>
</div>
</div>
</div>
</blockquote>
<br></div></div>
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.<span class=""><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>I finally use the address of the operands and
instruction to have a kind of ID of each %<num><br>
</div>
<div>It seems that it refers well what I want…<br>
<br>
</div>
<div>Let be the Instruction I:<br>
</div>
<div><span class="m_-2000578491068410997gmail-"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">%0 = mul
nsw i32 %1, %2<br>
<br>
</span></span></div>
<div><span class="m_-2000578491068410997gmail-"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">&I =
0x3d9f850 → %0<br>
</span></span></div>
<div><span class="m_-2000578491068410997gmail-"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">operands(0)→get()
= 0x3d9f7bc → %1<br>
</span></span></div>
<div><span class="m_-2000578491068410997gmail-"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">operands(1)→get()
= 0x3d9f80c → %2<br>
<br>
</span></span></div>
<div><span class="m_-2000578491068410997gmail-"><span class="m_-2000578491068410997gmail-m_-1396804328854282964gmail-">then it
should be ok if I take this for finding my
dependencies between Instructions?<br>
</span></span></div>
<div> </div>
</div>
</div>
</div>
</blockquote>
<br></span>
Yes, you can use an Instruction* to identify an instruction.<span class=""><br>
<br>
-Eli<br>
<pre class="m_-2000578491068410997moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</span></div>
</blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"> RUBIANO Thomas<br></div>
</div>