<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 02/26/2015 02:31 AM, Nema, Ashutosh
wrote:<br>
</div>
<blockquote
cite="mid:2F8F96CFA7F90A4E8369B27E43E50D9C09542880@SCYBEXDAG02.amd.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<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.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;}
/* List Definitions */
@list l0
{mso-list-id:1066536356;
mso-list-type:hybrid;
mso-list-template-ids:651046860 67698711 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-number-format:alpha-lower;
mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></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">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.</p>
</div>
</blockquote>
I'm concerned about this approach. LICM is deliberately somewhat
conservative about aliasing to avoid compile time impact. In
practice, we defer some of the harder cases to GVN in the form of
full redundancy and partial redundancy elimination. It's not clear
to me that versioning a loop in LICM is a good use of either compile
time or code size. In particular, I'm concerned about the code size
increase that can result from recursive application of loop
versioning. <br>
<br>
I think this is an interesting idea, but the profitability
heuristics will need to be incredibly carefully tuned. It would be
really really easy to have a net negative impact on the quality of
generated code while doing something that seems like a good idea
within LICM. Can you spell out the profitability heuristics you're
planning on using? You might want to look at what Sanjoy has been
doing with IRCE. This is a specialized form of Index Set Splitting
with the roughly the same problem to solve. <br>
<br>
Have you looked at trying to make LICM more precise with regards to
aliasing? I was looking at this a while back and it seemed like
there was plenty of room for cheap changes with payoff here. (One
example: a read only call in a loop collapses all alias sets.
Oops.)<br>
<br>
(It's not clear to me whether you're proposing a new pass, or
extending LICM. If the former, much of my concern disappears. If
the later, you'll need to really justify the complexity.)<br>
<br>
<blockquote
cite="mid:2F8F96CFA7F90A4E8369B27E43E50D9C09542880@SCYBEXDAG02.amd.com"
type="cite">
<div class="WordSection1">
<p class="MsoNormal"><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
moz-do-not-send="true" href="http://reviews.llvm.org/D7900">http://reviews.llvm.org/D7900</a></p>
</div>
</blockquote>
If you're expecting review, this needs to go to llvm-commits. <br>
<br>
I have not really looked at it, but one high level comment. You've
got a couple of really long functions that need to be broken up into
semantic pieces. Reviewing in the current form would be hard. <br>
<blockquote
cite="mid:2F8F96CFA7F90A4E8369B27E43E50D9C09542880@SCYBEXDAG02.amd.com"
type="cite">
<div class="WordSection1">
<p class="MsoNormal"><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>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</body>
</html>