<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 15 (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;}
/* 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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
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:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle19
{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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal">Thanks Hal, Philip and Adam for reviewing this RFC.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Based on suggestion I have made below changes.<o:p></o:p></p>
<p class="MsoNormal">Code change available at: <a href="http://reviews.llvm.org/D9151">
<span style="color:windowtext">http://reviews.llvm.org/D9151</span></a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">1) Using LAA(Loop Access Analysis) for versioning feasibility & memcheck.<o:p></o:p></p>
<p class="MsoNormal">As the part of feasibility analysis started using LAA. <o:p>
</o:p></p>
<p class="MsoNormal">Earlier memcheck creation was implemented under Loop Versioning, now using
<o:p></o:p></p>
<p class="MsoNormal">LAA for this.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">2) Improved benefit analysis.<o:p></o:p></p>
<p class="MsoNormal">Introduced few checks to ensure the benefit of loop versioning.<o:p></o:p></p>
<p class="MsoNormal">- Checking number of possible invariant promotion vs total instructions of loop.<o:p></o:p></p>
<p class="MsoNormal">If this goes beyond certain threshold then only do loop versioning.<o:p></o:p></p>
<p class="MsoNormal">Kept this threshold as a hard value as 25%(total instruction of loop), also
<o:p></o:p></p>
<p class="MsoNormal">provided option to control this threshold.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- Similar added check for invariant stores vs total stores in loop, kept this
<o:p></o:p></p>
<p class="MsoNormal">threshold as a hard value 40%(total instruction of loop), also provided option
<o:p></o:p></p>
<p class="MsoNormal">to control this threshold.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">3) Introduced threshold command line parameter to control loop nest,
<o:p></o:p></p>
<p class="MsoNormal">benefit threshold etc.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- loopver-invar-store-threshold<o:p></o:p></p>
<p class="MsoNormal">This option is to control invariant store vs total store threshold,
<o:p></o:p></p>
<p class="MsoNormal">default 40% of total instruction.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- loopver-invar-threshold<o:p></o:p></p>
<p class="MsoNormal">This option is to control invariant load & store vs total instruction threshold,
<o:p></o:p></p>
<p class="MsoNormal">default 25% of total instruction.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- loopver-max-depth-threshold<o:p></o:p></p>
<p class="MsoNormal">This option is to control maximum depth for loops getting considered,
<o:p></o:p></p>
<p class="MsoNormal">default depth is 2.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- loopver-memcheck-ptr-threshold<o:p></o:p></p>
<p class="MsoNormal">This option is to control maximum pointer/address getting considered, default is 5.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">4) Code refactoring<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">5) Added test cases.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If possible, please review this change.<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">Ashutosh<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Nema, Ashutosh <br>
<b>Sent:</b> Thursday, February 26, 2015 4:01 PM<br>
<b>To:</b> llvmdev@cs.uiuc.edu<br>
<b>Subject:</b> RFC: Loop versioning for LICM<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I like to propose a new loop multi versioning optimization for LICM.
<o:p></o:p></p>
<p class="MsoNormal">For now I kept this for LICM only, but it can be used in multiple places.<o:p></o:p></p>
<p class="MsoNormal">The main motivation is to allow optimizations stuck because of memory
<o:p></o:p></p>
<p class="MsoNormal">alias dependencies. Most of the time when alias analysis is unsure about
<o:p></o:p></p>
<p class="MsoNormal">memory access and it says may-alias. This un surety from alias analysis restrict
<o:p></o:p></p>
<p class="MsoNormal">some of the memory based optimizations to proceed further.<o:p></o:p></p>
<p class="MsoNormal">We observed some cases with LICM, where things are beyond aliasing.
<o:p></o:p></p>
<p class="MsoNormal">In cases where alias analysis is unsure we like to use loop versioning as an alternative.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Loop Versioning will creates version of the loop with aggressive alias and the other
<o:p></o:p></p>
<p class="MsoNormal">with conservative (default) alias. Aggressive alias version of loop will have all the
<o:p></o:p></p>
<p class="MsoNormal">memory access marked as no-alias. These two version of loop will be preceded by a
<o:p></o:p></p>
<p class="MsoNormal">memory runtime check. This runtime check consists of bound checks for all unique memory
<o:p></o:p></p>
<p class="MsoNormal">accessed in loop, and it ensures aliasing of memory. Based on this check result at runtime
<o:p></o:p></p>
<p class="MsoNormal">any of the loops gets executed, if memory is non aliased then aggressive aliasing loop
<o:p></o:p></p>
<p class="MsoNormal">gets executed, else when memory is aliased then non aggressive aliased version gets executed.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">By setting no-alias to memory accessed in aggressive alias version of loop, enable other
<o:p></o:p></p>
<p class="MsoNormal">optimization to continue further.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Following are the top level steps:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">1) Perform loop do versioning feasibility check.<o:p></o:p></p>
<p class="MsoNormal">2) If loop is a candidate for versioning then create a memory bound check, by considering
<o:p></o:p></p>
<p class="MsoNormal"> all the memory access in loop body.<o:p></o:p></p>
<p class="MsoNormal">3) Clone original loop and set all memory access as no-alias in new loop.<o:p></o:p></p>
<p class="MsoNormal">4) Set original loop & versioned loop as a branch target of runtime check result.<o:p></o:p></p>
<p class="MsoNormal">5) Call LICM on aggressive alias versioned of loop(For now LICM is scheduled later and not directly
<o:p></o:p></p>
<p class="MsoNormal"> called from LoopVersioning pass).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Consider following test:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> 1 int foo(int * var1, int * var2, int * var3, unsigned itr) {<o:p></o:p></p>
<p class="MsoNormal"> 2 unsigned i = 0, j = 0;<o:p></o:p></p>
<p class="MsoNormal"> 3 for(; i < itr; i++) {<o:p></o:p></p>
<p class="MsoNormal"> 4 for(; j < itr; j++) {<o:p></o:p></p>
<p class="MsoNormal"> 5 var1[j] = itr + i;<o:p></o:p></p>
<p class="MsoNormal"> 6 var3[i] = var1[j] + var3[i];<o:p></o:p></p>
<p class="MsoNormal"> 7 }<o:p></o:p></p>
<p class="MsoNormal"> 8 }<o:p></o:p></p>
<p class="MsoNormal"> 9 }<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">At line #6 store to var3 can be moved out by LICM(promoteLoopAccessesToScalars)
<o:p></o:p></p>
<p class="MsoNormal">but because of alias analysis un surety about memory access it unable to move it out.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">After Loop versioning IR:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b><Versioned Loop><o:p></o:p></b></p>
<p class="MsoNormal">for.body3.loopVersion: ; preds = %for.body3.loopVersion.preheader, %for.body3.loopVersion<o:p></o:p></p>
<p class="MsoNormal"> %indvars.iv.loopVersion = phi i64 [ %indvars.iv.next.loopVersion, %for.body3.loopVersion ], [ %2, %for.body3.loopVersion.preheader ]<o:p></o:p></p>
<p class="MsoNormal"> %arrayidx.loopVersion = getelementptr inbounds i32* %var1, i64 %indvars.iv.loopVersion<o:p></o:p></p>
<p class="MsoNormal"> store i32 %add, i32* %arrayidx.loopVersion, align 4, !tbaa !1, !alias.scope !11, !noalias !11<o:p></o:p></p>
<p class="MsoNormal"> %indvars.iv.next.loopVersion = add nuw nsw i64 %indvars.iv.loopVersion, 1<o:p></o:p></p>
<p class="MsoNormal"> %lftr.wideiv.loopVersion = trunc i64 %indvars.iv.loopVersion to i32<o:p></o:p></p>
<p class="MsoNormal"> %exitcond.loopVersion = icmp eq i32 %lftr.wideiv.loopVersion, %0<o:p></o:p></p>
<p class="MsoNormal"> br i1 %exitcond.loopVersion, label %for.inc11.loopexit38, label %for.body3.loopVersion<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b><Original Loop><o:p></o:p></b></p>
<p class="MsoNormal">for.body3: ; preds = %for.body3.lr.ph, %for.body3<o:p></o:p></p>
<p class="MsoNormal"> %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ %2, %for.body3.lr.ph ]<o:p></o:p></p>
<p class="MsoNormal"> %arrayidx = getelementptr inbounds i32* %var1, i64 %indvars.iv<o:p></o:p></p>
<p class="MsoNormal"> store i32 %add, i32* %arrayidx, align 4, !tbaa !1<o:p></o:p></p>
<p class="MsoNormal"> %8 = load i32* %arrayidx7, align 4, !tbaa !1<o:p></o:p></p>
<p class="MsoNormal"> %add8 = add nsw i32 %8, %add<o:p></o:p></p>
<p class="MsoNormal"> <span style="background:silver;mso-highlight:silver">store i32 %add8, i32* %arrayidx7, align 4, !tbaa !1</span><o:p></o:p></p>
<p class="MsoNormal"> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1<o:p></o:p></p>
<p class="MsoNormal"> %lftr.wideiv = trunc i64 %indvars.iv to i32<o:p></o:p></p>
<p class="MsoNormal"> %exitcond = icmp eq i32 %lftr.wideiv, %0<o:p></o:p></p>
<p class="MsoNormal"> br i1 %exitcond, label %for.inc11, label %for.body3<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In versioned loop difference is visible, 1 store has moved out.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Following are some high level details about current implementation:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- LoopVersioning<o:p></o:p></p>
<p class="MsoNormal">LoopVersioning is main class which holds multi versioning functionality.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- LoopVersioning :: isVersioningBeneficial <o:p></o:p></p>
<p class="MsoNormal">Its member to ‘LoopVersioning’<o:p></o:p></p>
<p class="MsoNormal">Does feasibility check for loop versioning. <o:p></o:p></p>
<p class="MsoNormal">a) Checks layout of loop.<o:p></o:p></p>
<p class="MsoNormal">b) Instruction level check.<o:p></o:p></p>
<p class="MsoNormal">c) memory checks.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.25in"><o:p> </o:p></p>
<p class="MsoNormal">- LoopVersioning :: versionizeLoop<o:p></o:p></p>
<p class="MsoNormal">a) Clone original loo<o:p></o:p></p>
<p class="MsoNormal">b) Create a runtime memory check.<o:p></o:p></p>
<p class="MsoNormal">c) Add both loops under runtime check results target.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- RuntimeMemoryCheck<o:p></o:p></p>
<p class="MsoNormal">This class take cares runtime memory check.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">- RuntimeMemoryCheck ::createRuntimeCheck<o:p></o:p></p>
<p class="MsoNormal">It creates runtime memory check.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In this patch used maximum loop nest threshold as 2, and maximum number
<o:p></o:p></p>
<p class="MsoNormal">of pointers in runtime memory check as 5.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Later I like to make this as a utility so others can use it.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Requesting to go through patch for detailed approach.<o:p></o:p></p>
<p class="MsoNormal">Patch available at <a href="http://reviews.llvm.org/D7900">http://reviews.llvm.org/D7900</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Suggestions are comments are welcome.<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">Ashutosh<o:p></o:p></p>
</div>
</body>
</html>