<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=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@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: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;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
span.EmailStyle18
{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">Hi Adam,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks for looking into LoopVersioning work.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have gone through recent LoopAccessAnalysis changes and found some of the stuff
<o:p></o:p></p>
<p class="MsoNormal">overlaps (i.e. runtime memory check, loop access analysis etc.). LoopVersioning can
<o:p></o:p></p>
<p class="MsoNormal">use some of the things from LAA.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">LoopVersioning is a memory check based multi versioning optimization, it simply creates
<o:p></o:p></p>
<p class="MsoNormal">aggressive alias version of loop preceded by a memory check. It’s not concerned about
<o:p></o:p></p>
<p class="MsoNormal">the order of instructions and detailed dependency check that LoopVectorizer does.<o:p></o:p></p>
<p class="MsoNormal">It does some basic loop structure check, loop instruction checks & memory checks.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In general found LAA work is more inclined towards LoopVectorizer.
<o:p></o:p></p>
<p class="MsoNormal">Found some of the possible reusable functions are biased towards LoopVectorizer,
<o:p></o:p></p>
<p class="MsoNormal">they has specific condition checks for it. <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">It’s good to make some of the classes & function more generic and reusable.
<o:p></o:p></p>
<p class="MsoNormal">Will be covering some of the points in this mail.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b>RuntimeCheckEmitter<o:p></o:p></b></p>
<p class="MsoNormal">“RuntimeCheckEmitter::addRuntimeCheck”<o:p></o:p></p>
<p class="MsoNormal">While creating runtime check I have found, some of the things are not getting considered.<o:p></o:p></p>
<p class="MsoNormal">1) No need to check if two read only pointers intersect.<o:p></o:p></p>
<p class="MsoNormal">2) Only need to check pointers between two different dependency sets.<o:p></o:p></p>
<p class="MsoNormal">3) Only need to check pointers in the same alias set<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m sure if we like this to be used by other optimization then not all optimization appreciate
<o:p></o:p></p>
<p class="MsoNormal">above checks. Specifically LoopVersioning does not care about this, it expects all the pointers
<o:p></o:p></p>
<p class="MsoNormal">in a loop should be considered for a memory check. Also it does not care about different
<o:p></o:p></p>
<p class="MsoNormal">dependency set & different alias sets.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I suggest we can make these checks optional, and give flexibility to users of this class to set it.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">For the same suggesting following change:<o:p></o:p></p>
<p class="MsoNormal">1) <o:p></o:p></p>
<p class="MsoNormal">class RuntimeCheckEmitter {<o:p></o:p></p>
<p class="MsoNormal"> …………<o:p></o:p></p>
<p class="MsoNormal"> …………<o:p></o:p></p>
<p class="MsoNormal"> /// Consider readonly pointer intersection in memcheck
<o:p></o:p></p>
<p class="MsoNormal"> bool CheckReadOnlyPointersIntersection;<o:p></o:p></p>
<p class="MsoNormal"> /// Consider pointers in same dependency sets for memcheck.<o:p></o:p></p>
<p class="MsoNormal"> bool CheckPointersInSameDependencySet;<o:p></o:p></p>
<p class="MsoNormal"> /// Consider pointers in different Alias sets for memcheck<o:p></o:p></p>
<p class="MsoNormal"> bool CheckPointersInDifferentAliasSet<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Add the above 3 variables to class, and allow users of this class to set it.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">2) <o:p></o:p></p>
<p class="MsoNormal">In "RuntimeCheckEmitter::addRuntimeCheck" following 3 condition needs to<o:p></o:p></p>
<p class="MsoNormal">controlled by above conditional variables.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">a> <o:p></o:p></p>
<p class="MsoNormal"> Change Following Check:<o:p></o:p></p>
<p class="MsoNormal"> // No need to check if two readonly pointers intersect.<o:p></o:p></p>
<p class="MsoNormal"> if (!PtrRtCheck->IsWritePtr[i] && !PtrRtCheck->IsWritePtr[j])<o:p></o:p></p>
<p class="MsoNormal"> continue;<o:p></o:p></p>
<p class="MsoNormal"> To: <o:p></o:p></p>
<p class="MsoNormal"> // No need to check if two readonly pointers intersect.<o:p></o:p></p>
<p class="MsoNormal"> if (!CheckReadOnlyPointersIntersection && !PtrRtCheck->IsWritePtr[i] &&
<o:p></o:p></p>
<p class="MsoNormal"> !PtrRtCheck->IsWritePtr[j])<o:p></o:p></p>
<p class="MsoNormal"> continue; <o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">b><o:p></o:p></p>
<p class="MsoNormal"> Change Following Check:<o:p></o:p></p>
<p class="MsoNormal"> // Only need to check pointers between two different dependency sets.<o:p></o:p></p>
<p class="MsoNormal"> if (PtrRtCheck->DependencySetId[i] == PtrRtCheck->DependencySetId[j])<o:p></o:p></p>
<p class="MsoNormal"> continue; <o:p></o:p></p>
<p class="MsoNormal"> To: <o:p></o:p></p>
<p class="MsoNormal"> // Only need to check pointers between two different dependency sets.<o:p></o:p></p>
<p class="MsoNormal"> if (!CheckPointersInSameDependencySet && <o:p></o:p></p>
<p class="MsoNormal"> PtrRtCheck->DependencySetId[i] == PtrRtCheck->DependencySetId[j])<o:p></o:p></p>
<p class="MsoNormal"> continue; <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">c><o:p></o:p></p>
<p class="MsoNormal"> Change Following Check:<o:p></o:p></p>
<p class="MsoNormal"> // Only need to check pointers in the same alias set.<o:p></o:p></p>
<p class="MsoNormal"> if (PtrRtCheck->AliasSetId[i] != PtrRtCheck->AliasSetId[j])<o:p></o:p></p>
<p class="MsoNormal"> continue;<o:p></o:p></p>
<p class="MsoNormal"> To: <o:p></o:p></p>
<p class="MsoNormal"> // Only need to check pointers in the same alias set.<o:p></o:p></p>
<p class="MsoNormal"> if (!CheckPointersInDifferentAliasSet && <o:p></o:p></p>
<p class="MsoNormal"> PtrRtCheck->AliasSetId[i] != PtrRtCheck->AliasSetId[j])<o:p></o:p></p>
<p class="MsoNormal"> continue; <o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">By this we allowing RuntimeCheckEmitter as more flexible and providing user
<o:p></o:p></p>
<p class="MsoNormal">more control to use it.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b>LoopAccessAnalysis::analyzeLoop<o:p></o:p></b></p>
<p class="MsoNormal">Here again its very specific to LoopVectorizer. <o:p></o:p></p>
<p class="MsoNormal">The way it handles stores & loads may not be appreciated by other optimization
<o:p></o:p></p>
<p class="MsoNormal">expecting other treatment. I suggest we should think on flexibility for user to
<o:p></o:p></p>
<p class="MsoNormal">override load & store handling. We can provide virtual methods for load & store
<o:p></o:p></p>
<p class="MsoNormal">handling (i.e. analyzeLoads & analyzeStores). Also some of the optimization may not
<o:p></o:p></p>
<p class="MsoNormal">like call instruction, or further they like to analyze call. We should also think on those
<o:p></o:p></p>
<p class="MsoNormal">lines to make some provision.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">AccessAnalysis & LoopAccessAnalysis are tied up dependency check, If some analysis
<o:p></o:p></p>
<p class="MsoNormal">needs same functionality except dependency check then there should be provision available.<o:p></o:p></p>
<p class="MsoNormal">i.e. LoopVersioning needs similar stuff except dependency analysis, for now possibility is
<o:p></o:p></p>
<p class="MsoNormal">extend & rewrite functions by removing dependency checks. <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<span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><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>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Adam Nemet [mailto:anemet@apple.com]
<br>
<b>Sent:</b> Friday, February 27, 2015 12:40 AM<br>
<b>To:</b> Nema, Ashutosh<br>
<b>Cc:</b> llvmdev@cs.uiuc.edu<br>
<b>Subject:</b> Re: [LLVMdev] RFC: Loop versioning for LICM<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Hi Ashutosh,<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Have you been following the recent Loop Access Analysis work? LAA was split out from the Loop Vectorizer that have been performing the kind of loop versioning that you describe. The main reason was to be able to share this functionality
with other passes.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Loop Access Analysis is an analysis pass that computes basic memory dependence and the runtime checks. The versioning decision and then performing the transformation are left to the transform passes using this analysis.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If we decide that a stand-alone memcheck-based loop-versioning is desired we should probably use this analysis and possibly extend it instead of duplicating the code.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Adam<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On Feb 26, 2015, at 2:31 AM, Nema, Ashutosh <<a href="mailto:Ashutosh.Nema@amd.com">Ashutosh.Nema@amd.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">I like to propose a new loop multi versioning optimization for LICM.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">For now I kept this for LICM only, but it can be used in multiple places.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">The main motivation is to allow optimizations stuck because of memory<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">alias dependencies. Most of the time when alias analysis is unsure about<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">memory access and it says may-alias. This un surety from alias analysis restrict<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">some of the memory based optimizations to proceed further.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">We observed some cases with LICM, where things are beyond aliasing.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">In cases where alias analysis is unsure we like to use loop versioning as an alternative.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Loop Versioning will creates version of the loop with aggressive alias and the other<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">with conservative (default) alias. Aggressive alias version of loop will have all the<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">memory access marked as no-alias. These two version of loop will be preceded by a<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">memory runtime check. This runtime check consists of bound checks for all unique memory<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">accessed in loop, and it ensures aliasing of memory. Based on this check result at runtime<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">any of the loops gets executed, if memory is non aliased then aggressive aliasing loop<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">gets executed, else when memory is aliased then non aggressive aliased version gets executed.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">By setting no-alias to memory accessed in aggressive alias version of loop, enable other<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">optimization to continue further.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Following are the top level steps:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">1) Perform loop do versioning feasibility check.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">2) If loop is a candidate for versioning then create a memory bound check, by considering<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> all the memory access in loop body.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">3) Clone original loop and set all memory access as no-alias in new loop.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">4) Set original loop & versioned loop as a branch target of runtime check result.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">5) Call LICM on aggressive alias versioned of loop(For now LICM is scheduled later and not directly<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> called from LoopVersioning pass).<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Consider following test:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 1 int foo(int * var1, int * var2, int * var3, unsigned itr) {<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 2 unsigned i = 0, j = 0;<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 3 for(; i < itr; i++) {<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 4 for(; j < itr; j++) {<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 5 var1[j] = itr + i;<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 6 var3[i] = var1[j] + var3[i];<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 7 }<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 8 }<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> 9 }<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">At line #6 store to var3 can be moved out by LICM(promoteLoopAccessesToScalars)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">but because of alias analysis un surety about memory access it unable to move it out.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">After Loop versioning IR:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><Versioned Loop></span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">for.body3.loopVersion: ; preds = %for.body3.loopVersion.preheader, %for.body3.loopVersion<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %indvars.iv.loopVersion = phi i64 [ %indvars.iv.next.loopVersion, %for.body3.loopVersion ], [ %2, %for.body3.loopVersion.preheader ]<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %arrayidx.loopVersion = getelementptr inbounds i32* %var1, i64 %indvars.iv.loopVersion<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> store i32 %add, i32* %arrayidx.loopVersion, align 4, !tbaa !1, !alias.scope !11, !noalias !11<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %indvars.iv.next.loopVersion = add nuw nsw i64 %indvars.iv.loopVersion, 1<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %lftr.wideiv.loopVersion = trunc i64 %indvars.iv.loopVersion to i32<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %exitcond.loopVersion = icmp eq i32 %lftr.wideiv.loopVersion, %0<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> br i1 %exitcond.loopVersion, label %for.inc11.loopexit38, label %for.body3.loopVersion<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><Original Loop></span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">for.body3: ; preds = %for.body3.lr.ph, %for.body3<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ %2, %for.body3.lr.ph ]<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %arrayidx = getelementptr inbounds i32* %var1, i64 %indvars.iv<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> store i32 %add, i32* %arrayidx, align 4, !tbaa !1<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %8 = load i32* %arrayidx7, align 4, !tbaa !1<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %add8 = add nsw i32 %8, %add<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <span class="apple-converted-space"> </span><span style="background:silver">store i32 %add8, i32* %arrayidx7, align 4, !tbaa !1</span><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %lftr.wideiv = trunc i64 %indvars.iv to i32<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> %exitcond = icmp eq i32 %lftr.wideiv, %0<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> br i1 %exitcond, label %for.inc11, label %for.body3<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">In versioned loop difference is visible, 1 store has moved out.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Following are some high level details about current implementation:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">- LoopVersioning<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">LoopVersioning is main class which holds multi versioning functionality.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">- LoopVersioning :: isVersioningBeneficial<span class="apple-converted-space"> </span><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Its member to ‘LoopVersioning’<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Does feasibility check for loop versioning.<span class="apple-converted-space"> </span><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">a) Checks layout of loop.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">b) Instruction level check.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">c) memory checks.<o:p></o:p></span></p>
</div>
<div style="margin-left:.25in">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">- LoopVersioning :: versionizeLoop<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">a) Clone original loo<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">b) Create a runtime memory check.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">c) Add both loops under runtime check results target.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">- RuntimeMemoryCheck<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">This class take cares runtime memory check.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">- RuntimeMemoryCheck ::createRuntimeCheck<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">It creates runtime memory check.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">In this patch used maximum loop nest threshold as 2, and maximum number<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">of pointers in runtime memory check as 5.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Later I like to make this as a utility so others can use it.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Requesting to go through patch for detailed approach.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Patch available at<span class="apple-converted-space"> </span><a href="http://reviews.llvm.org/D7900"><span style="color:#954F72">http://reviews.llvm.org/D7900</span></a><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Suggestions are comments are welcome.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Regards,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Ashutosh<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">_______________________________________________<br>
LLVM Developers mailing list<br>
</span><a href="mailto:LLVMdev@cs.uiuc.edu"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:#954F72">LLVMdev@cs.uiuc.edu</span></a><span class="apple-converted-space"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"> </span></span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"> </span><a href="http://llvm.cs.uiuc.edu/"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:#954F72">http://llvm.cs.uiuc.edu</span></a><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
</span><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:#954F72">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</span></a><o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>