<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:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:odc="urn:schemas-microsoft-com:office:odc" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:rtc="http://microsoft.com/officenet/conferencing" xmlns:D="DAV:" xmlns:Repl="http://schemas.microsoft.com/repl/" xmlns:mt="http://schemas.microsoft.com/sharepoint/soap/meetings/" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ppda="http://www.passport.com/NameSpace.xsd" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcs="http://schemas.microsoft.com/data/udc/soap" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:udcp2p="http://schemas.microsoft.com/data/udc/parttopart" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:dsss="http://schemas.microsoft.com/office/2006/digsig-setup" xmlns:dssi="http://schemas.microsoft.com/office/2006/digsig" xmlns:mdssi="http://schemas.openxmlformats.org/package/2006/digital-signature" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:spwp="http://microsoft.com/sharepoint/webpartpages" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:pptsl="http://schemas.microsoft.com/sharepoint/soap/SlideLibrary/" xmlns:spsl="http://microsoft.com/webservices/SharePointPortalServer/PublishedLinksService" xmlns:Z="urn:schemas-microsoft-com:" xmlns:tax="http://schemas.microsoft.com/sharepoint/taxonomy/soap/" xmlns:tns="http://schemas.microsoft.com/sharepoint/soap/recordsrepository/" xmlns:spsup="http://microsoft.com/webservices/SharePointPortalServer/UserProfileService" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:st="" 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 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-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;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@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">I’m in the process of reading and understanding the background and implementation of the MachinePipeliner’s swing modulo scheduling algorithm.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In short, my question is: “Does the swing modulo scheduling algorithm work for simple classes of irregular loops such as ‘while (x != null) { x = x->next; }’ ”. This is an important loop shape to optimize in embedded benchmarks like coremark
(core_list_join, reverse, find, etc.). Since the loop control is often load -> conditional branch, targets with high latency loads can often see performance boosts when the load and branch are pipelined to hide the load latency.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I understand the ModuloScheduleExpander would need some heavy modification, as it relies on helpers like “createTripCountGreaterCondition” and “adjustTripCount”, both of which are nonsensical in an irregular loop. I think that’s a separate
question at the moment. There are other issues with irregular loops that I’m aware of, such operations sensitive to overexecuction like loads/stores, but there are well-known solutions for those problems, especially on targets that support instruction predication
in hardware.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Our team has investigated pipelining irregular loops before, and found good results with some relatively straightforward additions to our internal implementation :
<a href="https://dl.acm.org/doi/abs/10.1145/384196.384216">https://dl.acm.org/doi/abs/10.1145/384196.384216</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">One common theme that seems to exist in all the SMS papers’ examples and in the implementation is that the scheduling DAG does not consider the branch in the schedule. In fact, in the implementation, if the successor of any instruction
in the DAG happens to be the branch (usually also in an SUnit object as ExitSU), the algorithm ends up crashing llc with a null-pointer dereference.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I first encountered this when dealing with a regular loop of the form:<o:p></o:p></p>
<p class="MsoNormal">%loop.body:<o:p></o:p></p>
<p class="MsoNormal"> %3 = PHI %1, %loop.preheader, %2, %loop.body<o:p></o:p></p>
<p class="MsoNormal"> …<o:p></o:p></p>
<p class="MsoNormal"> %2 = decrement %3<o:p></o:p></p>
<p class="MsoNormal"> branch-conditional (%2 > 0)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">When calculating ALAP, the decrement’s successor (the branch) is not considered, and we end up trying to access an element in ScheduleInfo that doesn’t exist.<o:p></o:p></p>
<p class="MsoNormal">I worked around this problem quite simply: I removed the PHI and decrement, hiding it inside of a pseudo-branch instruction with side effects.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Now, however, I’m dealing with an irregular loop, and have run into the same problem with no obvious solution.<o:p></o:p></p>
<p class="MsoNormal">If the base algorithm should work for some types of single-block irregular loops, I’d be more than happy to investigate and/or work with someone to make the changes and upstream them.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Regards,<o:p></o:p></p>
<p class="MsoNormal">J.B. Nagurne<o:p></o:p></p>
<p class="MsoNormal">Code Generation<o:p></o:p></p>
<p class="MsoNormal">Texas Instruments<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>