<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 target="_blank" href="mailto:efriedma@codeaurora.org">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="gmail-">
<div class="gmail-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 target="_blank" href="mailto:efriedma@codeaurora.org">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="gmail-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="gmail-m_-1396804328854282964gmail-"><br>
</span></blockquote>
<div><br>
</div>
<div>Ok, the term "definition" makes it clear. Do, if here
it's:<br>
<span class="gmail-m_-1396804328854282964gmail-">%1 = load i32, i32* %fact, align 4</span><br>
<span class="gmail-m_-1396804328854282964gmail-">%mul = mul nsw i32 %1, %2<br>
<br>
</span><br>
<span class="gmail-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="gmail-"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div>
<div class="gmail_extra">
<div class="gmail_quote">
<div><span class="gmail-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="gmail-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="gmail-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="gmail-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="gmail-m_-1396804328854282964gmail-">See the comment at the beginning of
lib/Analysis/ScalarEvolution.<wbr>cpp for a brief description and some
references.</span><span class="gmail-"><span class="gmail-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="gmail-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="gmail-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="gmail-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="gmail-"><br></span></div></blockquote><div><br></div><div>I was looking the LoopInvariantCodeMotion::runOnLoop.<br><br></div><div>No I didn't run mem2reg on my IR…<br></div><div>Is it necessary?<br><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="gmail-"><span class="gmail-m_-1396804328854282964gmail-">%0 = mul nsw i32 %1, %2<br><br></span></span></div><div><span class="gmail-"><span class="gmail-m_-1396804328854282964gmail-">&I = 0x3d9f850 → %0<br></span></span></div><div><span class="gmail-"><span class="gmail-m_-1396804328854282964gmail-">operands(0)→get() = 0x3d9f7bc → %1<br></span></span></div><div><span class="gmail-"><span class="gmail-m_-1396804328854282964gmail-">operands(1)→get() = 0x3d9f80c → %2<br><br></span></span></div><div><span class="gmail-"><span class="gmail-m_-1396804328854282964gmail-">then it should be ok if I take this for finding my dependencies between Instructions?<br></span></span></div><div> </div><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="gmail-">
<br>
-Eli<br>
<pre cols="72" class="gmail-m_-1396804328854282964moz-signature">--
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"> RUBIANO Thomas<br></div>
</div></div>