<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hi Sergei, Jakob,<br>
<br>
Thanks for your comments !<br>
<br>
On 07/06/2012 20:41, Sergei Larin wrote:
<blockquote cite="mid:03e301cd44dd$35f8ee60$a1eacb20$@org"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
<meta name="Generator" content="Microsoft Word 12 (filtered
medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif][if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Jakob,<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">
Please see my comments below. Hope this helps.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Sergei<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span
style="font-size:10.5pt;font-family:Consolas;color:#1F497D">--<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.5pt;font-family:Consolas;color:#1F497D">Qualcomm
Innovation Center, Inc. is a member of Code Aurora Forum.<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<div style="border-width: medium medium medium 1.5pt;
border-style: none none none solid; border-color:
-moz-use-text-color -moz-use-text-color -moz-use-text-color
blue; -moz-border-top-colors: none; -moz-border-right-colors:
none; -moz-border-bottom-colors: none;
-moz-border-left-colors: none; -moz-border-image: none;
padding: 0in 0in 0in 4pt;">
<div>
<div style="border:none;border-top:solid #B5C4DF
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">
Jakob Stoklund Olesen [<a class="moz-txt-link-freetext" href="mailto:stoklund@2pi.dk">mailto:stoklund@2pi.dk</a>] <br>
<b>Sent:</b> Thursday, June 07, 2012 1:02 PM<br>
<b>To:</b> Sergei Larin<br>
<b>Cc:</b> 'Ivan Llopard'; 'LLVM Developers Mailing
List'<br>
<b>Subject:</b> Re: [LLVMdev] Instruction bundles
before RA: Rematerialization<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Jun 7, 2012, at 10:25 AM, "Sergei
Larin" <<a moz-do-not-send="true"
href="mailto:slarin@codeaurora.org">slarin@codeaurora.org</a>>
wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<p class="MsoNormal"><span
style="font-size:11.5pt;font-family:"Calibri","sans-serif";color:#1F497D;background:white">Generally
as far as I concern, there is no way “generic” (platform
independent) code can add instructions to bundles
optimally</span><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">I agree, there are too many ways of
modeling stuff with bundles. That is why I took the
philosophical stance of treating bundles as black boxes
during RA. I think the target should be involved whenever
bundles are formed, and we shouldn't delete instructions
from inside bundles without permission from the target.</p>
</div>
</div>
</div>
</blockquote>
<br>
I also agree. Adding instructions into a bundle strongly depends on
the target and may be a quite complex task, sometimes too complex to
be done at allocation time if allocation speed is an issue. Removing
them should relax resource constraints in almost every conventional
VLIW target and it's something that the RA can potentially handle in
a simple way by *consulting the target before*.<br>
<br>
<blockquote cite="mid:03e301cd44dd$35f8ee60$a1eacb20$@org"
type="cite">
<div class="WordSection1">
<div style="border-width: medium medium medium 1.5pt;
border-style: none none none solid; border-color:
-moz-use-text-color -moz-use-text-color -moz-use-text-color
blue; -moz-border-top-colors: none; -moz-border-right-colors:
none; -moz-border-bottom-colors: none;
-moz-border-left-colors: none; -moz-border-image: none;
padding: 0in 0in 0in 4pt;">
<div>
<p class="MsoNormal"><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I think we need to tweak some of the
TargetInstrInfo hooks to make bundle remat possible. I
would like your input.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Rematerialization has multiple steps:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">1. Feasibility. RA knows the bundle
defining a given SSA value of a virtual register. It
calls TII.isTriviallyReMaterializable() to determine if
the defining instruction can (and should) be
rematerialized. See LiveRangeEdit::anyRematerializable().<o:p></o:p></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">[Larin,
Sergei] Obviously if you treat bundle as a black box
this does not make much sense… or
isTriviallyReMaterializable() should be able to
parse bundle and produce compound answer. Problem is
– you will not be able to find many opportunities
like that. On the other hand if you detect a
_single_ instruction as a remat candidate inside a
bundle, you might chose to dissolve (disassemble)
the bundle (if possible, as I said before) and treat
new serial group as you normally would for remat.
There should be a platform dependent pass to
rebundle this new serial sequence again, but even if
it is not done, but if the dissolution was
performed properly, this will be a performance, not
a correctness issue. As a side note, you might chose
simply remove desired instruction from the bundle
(often it is possible and trivial to do without
affecting semantics) and proceed as described above.
_BUT_ instruction removal does need back end
support. Example:<o:p></o:p></span></i></b></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">{
<o:p></o:p></span></i></b></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">r0
= add (r0, r1);<o:p></o:p></span></i></b></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">
P0 = cmp (r0.new, r0);<o:p></o:p></span></i></b></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">}<o:p></o:p></span></i></b></p>
<p class="MsoNormal"><b><i><span style="font-size: 11pt;
font-family:
"Calibri","sans-serif"; color:
rgb(31, 73, 125);"> The r0.new means that the new
value of r0 is used (reg file bypass in the same
cycle). You can see all possible implications of
this. To offload this mental logic to the back end,
we need a utility of form CanMoveMIBeforeBundle(MI,
BundleHeader)/ CanMoveMIAfterBundle(MI,
BundleHeader)/ MoveMIBeforeBundle(MI, BundleHeader)/
MoveMIAfterBundle(MI, BundleHeader). Calling this
repeatedly should achieve desired effect – remove
what could be removed, and live what needs to remain
bundled intact. The move utility can change
instruction properly for each target.</span></i></b></p>
</div>
</div>
</div>
</blockquote>
<br>
That's explains the hook isLegalToPruneDependencies() in the
packetizer :-).<br>
<br>
I don't see why that case cannot be handled by the existent model
and needs that kind of API's. For example, if 'add' needs to be
rematted, it's possible as long as all its operands are available at
the remat position. The same holds for 'cmp'. The original 'add'
cannot be removed because of its internal read and the RA should
consult the target before.<br>
Anyway, I think we both agree that instruction removal is a
target-specific task. It also remains simple compared to the
insertion of instructions into a bundle.<br>
<br>
<blockquote cite="mid:03e301cd44dd$35f8ee60$a1eacb20$@org"
type="cite">
<div class="WordSection1">
<div style="border-width: medium medium medium 1.5pt;
border-style: none none none solid; border-color:
-moz-use-text-color -moz-use-text-color -moz-use-text-color
blue; -moz-border-top-colors: none; -moz-border-right-colors:
none; -moz-border-bottom-colors: none;
-moz-border-left-colors: none; -moz-border-image: none;
padding: 0in 0in 0in 4pt;">
<div>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p></o:p></span></i></b></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal">2. Feasibility at desired
location. LiveRangeEdit::canRematerializeAt() then checks
that the instruction can be rematerialized at the new
location. This can fail if the instruction depends on
virtual register values that are not available at the new
location.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">[Larin,
Sergei] This looks similar to the previous case.
Good thing that you can potentially have zero cost
remat (if you can place your new instruction inside
existing bundle), but to know this you need an
answer _while_ you are computing the cost. For that
I can easily imagine a back end hook of something
like CanAddMIToBundle(MI, BundleHeader). This is
often easier than the previous task.</span></i></b></p>
</div>
</div>
</div>
</blockquote>
<br>
I like the idea. The cost can potentially be zero, at least from a
latency point of view (we care about power consumption also).<br>
Conversely, I don't like the fact that the RA looks for bundling
opportunities while rematting, but it's just a personal feeling. As
you pointed out for Hexagon, bundling is a complex task and
sometimes it cannot be managed in a simple way. In our BE, a DFA to
model resource constraints is not enough and a wrapper has been
created which adds complexity to the process.<br>
<br>
<blockquote cite="mid:03e301cd44dd$35f8ee60$a1eacb20$@org"
type="cite">
<div class="WordSection1">
<div style="border-width: medium medium medium 1.5pt;
border-style: none none none solid; border-color:
-moz-use-text-color -moz-use-text-color -moz-use-text-color
blue; -moz-border-top-colors: none; -moz-border-right-colors:
none; -moz-border-bottom-colors: none;
-moz-border-left-colors: none; -moz-border-image: none;
padding: 0in 0in 0in 4pt;">
<div>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal">3.
Remat. LiveRangeEdit::rematerializeAt() calls
TII.reMaterialize() (sic) to insert a copy of the defining
instruction at the new location.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">[Larin,
Sergei] At this point you need to update liveness on
bundle level, and then update global picture.
Updating liveness on bundle level also might need
help from the back end. See the above example with
.new, and you can easily imagine local defs/kills
inside a bundle that should not even be visible
outside the black box. As of now I consider this
mechanism somewhat broken on trunk (it is overly
pessimistic)… but API in this case is rather
straightforward. </span></i></b></p>
</div>
</div>
</div>
</blockquote>
<br>
I thought internals def/use were already modelled, is it right ?<br>
<br>
<blockquote cite="mid:03e301cd44dd$35f8ee60$a1eacb20$@org"
type="cite">
<div class="WordSection1">
<div style="border-width: medium medium medium 1.5pt;
border-style: none none none solid; border-color:
-moz-use-text-color -moz-use-text-color -moz-use-text-color
blue; -moz-border-top-colors: none; -moz-border-right-colors:
none; -moz-border-bottom-colors: none;
-moz-border-left-colors: none; -moz-border-image: none;
padding: 0in 0in 0in 4pt;">
<div>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal">4. Shrink original live range. The
original live range may be smaller after some uses have
been rematerialized. This may discover dead defs if there
are no remaining uses.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</blockquote>
<br>
IMHO, as long as internal defs/uses are taken into account, I don't
see any particular problem.<br>
<br>
<blockquote cite="mid:03e301cd44dd$35f8ee60$a1eacb20$@org"
type="cite">
<div class="WordSection1">
<div style="border-width: medium medium medium 1.5pt;
border-style: none none none solid; border-color:
-moz-use-text-color -moz-use-text-color -moz-use-text-color
blue; -moz-border-top-colors: none; -moz-border-right-colors:
none; -moz-border-bottom-colors: none;
-moz-border-left-colors: none; -moz-border-image: none;
padding: 0in 0in 0in 4pt;">
<div>
<p class="MsoNormal">5. LiveRangeEdit::eliminateDeadDefs()
erases the dead defs.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><i><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">[Larin,
Sergei] Last two should be easy with the above API
support – if you can CanMoveMIBeforeBundle(..)
outside the bundle, you can use existing API to
delete it.</span></i></b></p>
</div>
</div>
</div>
</blockquote>
<br>
How can be dead defs eliminated by calling CanMoveMIBeforeBundle() ?<br>
<br>
<br>
Ivan<br>
<br>
<blockquote cite="mid:03e301cd44dd$35f8ee60$a1eacb20$@org"
type="cite">
<div class="WordSection1">
<div style="border:none;border-left:solid blue 1.5pt;padding:0in
0in 0in 4.0pt">
<div>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal">It looks like each of these steps
require some help from the target if they are to handle
bundles.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">/jakob<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</blockquote>
</body>
</html>