<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Hi Frank, </div><div class=""><br class=""></div><br class=""><div><blockquote type="cite" class=""><div class="">On Aug 8, 2014, at 12:16 PM, Frank Winter <<a href="mailto:fwinter@jlab.org" class="">fwinter@jlab.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type" class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<div class="moz-cite-prefix">Hi Nadav,<br class="">
<br class="">
increasing the number of instructions per bucket indeed results in
a completely vectorized version of the given small function. For a
medium-size function I had to increase the bucket size to 8192 to
achieve full vectorization.<br class=""></div></div></div></blockquote><div><br class=""></div><div>This means that you had at least 8192 stores in that medium-sized function. :) I wonder why it is necessary to vectorize two stores with thousands of other store instructions in between. Are you sure you need such a high number? </div><br class=""><blockquote type="cite" class=""><div class=""><div bgcolor="#FFFFFF" text="#000000" class=""><div class="moz-cite-prefix">
<br class="">
If I then try this setup on one of my larger functions (containing
one huge basic block) it seems that the O(n^2) algorithm you were
talking about hits me hard here. After 10min in SLP I sent the
termination signal by hand.<br class="">
<br class="">
I remember the documentation saying that SLP is a quite versatile
vectorizer. I was wondering if I only need to vectorize the
load/store/arithmetic a single basic block and nothing else, are
there any parts in SLP that I could deactivate in order to reduce
the time needed for optimization?<br class=""></div></div></div></blockquote><div><br class=""></div><div>The SLP vectorizer starts by finding sequences of consecutive stores. It sounds like most of the time is spent in the code that find consecutive store sequence. You could probably verify this assumption using a profiler. </div><div><br class=""></div><div>I think that one way to move forward would be to improve the routine that finds consecutive stores. At the moment we iterate over all possibly combinations and use SCEV to figure out if two stores are consecutive. We can’t simply ’sort’ the stores based on the distance from some location because there could be multiple base indices. I think that one way to improve the search is to sort the store instructions into buckets according to their memory type. </div><div><br class=""></div><div>Thanks,</div><div>Nadav</div><br class=""><blockquote type="cite" class=""><div class=""><div bgcolor="#FFFFFF" text="#000000" class=""><div class="moz-cite-prefix">
<br class="">
Thanks,<br class="">
Frank<br class="">
<br class="">
<br class="">
On 08/08/2014 01:13 PM, Nadav Rotem wrote:<br class="">
</div>
<blockquote cite="mid:87C8A770-EE54-4AA8-A93B-D3842657BDE5@apple.com" type="cite" class="">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252" class="">
<div class="">Hi Frank, </div>
<div class=""><br class="">
</div>
<div class="">Thanks for working on this. Please look
at vectorizeStoreChains. In this function we process all of the
stores in the function in buckets of 16 elements because
constructing consecutive stores is implemented using an O(n^2)
algorithm. You can try to increase this threshold to 128 and see
if it helps. </div>
<div class=""><br class="">
</div>
<div class="">I also agree with Renato and Chad that adding a flag
to tell the SLP-vectorizer to put more effort (compile time)
into the problem is a good idea.</div>
<div class=""><br class="">
</div>
<div class="">Thanks,</div>
<div class="">Nadav </div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<br class="">
<div class="">
<blockquote type="cite" class="">
<div class="">On Aug 8, 2014, at 8:27 AM, Frank Winter <<a moz-do-not-send="true" href="mailto:fwinter@jlab.org" class="">fwinter@jlab.org</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class=""><span style="font-family: Helvetica; font-size:
12px; font-style: normal; font-variant: normal;
font-weight: normal; letter-spacing: normal; line-height:
normal; orphans: auto; text-align: start; text-indent:
0px; text-transform: none; white-space: normal; widows:
auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;
float: none; display: inline !important;" class="">I
changed the max. recursion depth to 36, and tried then
1000 (from the original value of 12) and it did not
improve SLP's optimization capabilities on my input
function. For example, the attached function is (by
design) perfectly vectorizable into 4-packed single
precision SIMD load/add/store. The SLP vectorizer just
does nothing with it.</span><br style="font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant: normal; font-weight: normal; letter-spacing:
normal; line-height: normal; orphans: auto; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; widows: auto; word-spacing: 0px;
-webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">I ran</span><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">opt
-default-data-layout="e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-basicaa -slp-vectorizer -S < mod_vec_p_vec.ll</span><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">with
RecursionMaxDepth = 12, 36, and 1000.</span><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">Thanks,</span><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">Frank</span><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">On 08/07/2014
12:57 PM, Renato Golin wrote:</span><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<blockquote type="cite" style="font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant: normal;
font-weight: normal; letter-spacing: normal; line-height:
normal; orphans: auto; text-align: start; text-indent:
0px; text-transform: none; white-space: normal; widows:
auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">On 7 August 2014 17:33, Chad Rosier <<a moz-do-not-send="true" href="mailto:mcrosier@codeaurora.org" class="">mcrosier@codeaurora.org</a>>
wrote:<br class="">
<blockquote type="cite" class="">You might consider filing
a bug (<a moz-do-not-send="true" href="http://llvm.org/bugs" class="">llvm.org/bugs</a>)
requesting a flag, but I<br class="">
don't know if the code owners want to expose such a
flag.<br class="">
</blockquote>
I'm not sure that's a good idea as a raw access to that
limit, as<br class="">
there are no guarantees that it'll stay the same. But
maybe a flag<br class="">
turning some "aggressive" behaviour from SLP that would
then change<br class="">
that threshold (and maybe some others) would be a good
flag to have, I<br class="">
think.<br class="">
<br class="">
This could maybe be a way to deprecate the BB vectorizer
faster than<br class="">
we would otherwise. But that would depend on all missing
BB features<br class="">
to be implemented in SLP.<br class="">
<br class="">
An item in bugzilla seems appropriate.<br class="">
<br class="">
cheers,<br class="">
--renato<br class="">
</blockquote>
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span id="cid:B096A441-8971-4224-8A0D-465916107A27@apple.com" class=""><mod_vec_p_vec.ll></span><span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
none; display: inline !important;" class="">LLVM
Developers mailing list</span><br style="font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant: normal; font-weight: normal; letter-spacing:
normal; line-height: normal; orphans: auto; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; widows: auto; word-spacing: 0px;
-webkit-text-stroke-width: 0px;" class="">
<a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">LLVMdev@cs.uiuc.edu</a><span style="font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant: normal; font-weight: normal; letter-spacing:
normal; line-height: normal; orphans: auto; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; widows: auto; word-spacing: 0px;
-webkit-text-stroke-width: 0px; float: none; display:
inline !important;" class=""><span class="Apple-converted-space"> </span> </span><a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu/" style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">http://llvm.cs.uiuc.edu</a><br style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<a moz-do-not-send="true" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></div>
</blockquote>
</div>
<br class="">
</blockquote>
<br class="">
<br class="">
</div>
</div></blockquote></div><br class=""></body></html>