<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><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]--></head><body lang=EN-US link=blue vlink=purple><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:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt'><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 [mailto:stoklund@2pi.dk] <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 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.<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:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'> 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.<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><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><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><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><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></body></html>