<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 1/18/2017 2:56 AM, Thomas RUBIANO
wrote:<br>
</div>
<blockquote
cite="mid:CAGwBFn0=NRd0K2ZVLm+vFxzQs6PWZuecKmw1c241nRowUE7yUg@mail.gmail.com"
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
moz-do-not-send="true" 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"><span
class="gmail-">On 1/17/2017 7:12 AM, Thomas RUBIANO
via llvm-dev wrote:<br>
<blockquote style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"
class="gmail_quote">
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-"><br>
</span></blockquote>
<div><br>
</div>
<div>Ok, the term "definition" makes it clear. Do, if here
it's:<br>
<span class="gmail-">%1 = load i32, i32* %fact, align 4</span><br>
<span class="gmail-">%mul = mul nsw i32 %1, %2<br>
<br>
</span><br>
<span class="gmail-">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>
Exactly. If LICM can prove the load is in fact invariant, it will
move it out of the loop.<br>
<br>
<blockquote
cite="mid:CAGwBFn0=NRd0K2ZVLm+vFxzQs6PWZuecKmw1c241nRowUE7yUg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div class="gmail_extra">
<div class="gmail_quote">
<div><span class="gmail-"><br>
</span></div>
<blockquote style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex" class="gmail_quote"><span
class="gmail-">
<br>
<blockquote style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"
class="gmail_quote">
- 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-"><br>
<br>
<blockquote style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"
class="gmail_quote">
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-"><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 class="gmail-">See the comment at the beginning of
lib/Analysis/ScalarEvolution.cpp for a brief description and some
references.</span><span class="gmail-"></span><br>
<br>
<blockquote
cite="mid:CAGwBFn0=NRd0K2ZVLm+vFxzQs6PWZuecKmw1c241nRowUE7yUg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex" class="gmail_quote"><span
class="gmail-">
<br>
<blockquote style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"
class="gmail_quote">
<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-"><br>
<br>
<blockquote style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"
class="gmail_quote">
<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-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>
Can you show me the complete function you're looking at? Have you
run mem2reg on your IR?<br>
<br>
-Eli<br>
<pre class="moz-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>
</body>
</html>