<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/19/2017 2:16 AM, Thomas RUBIANO
wrote:<br>
</div>
<blockquote
cite="mid:CAGwBFn3P2STYnWL3TQbt3ZMHxnseD2Eyei5ntA3u0W0foesjXQ@mail.gmail.com"
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 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">
<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
moz-do-not-send="true" 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>
</div>
</div>
</div>
</div>
</blockquote>
<br>
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.<br>
<br>
<blockquote
cite="mid:CAGwBFn3P2STYnWL3TQbt3ZMHxnseD2Eyei5ntA3u0W0foesjXQ@mail.gmail.com"
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="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>
</div>
</div>
</div>
</blockquote>
<br>
Yes, you can use an Instruction* to identify an instruction.<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>