<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Exchange Server">
<!-- converted from rtf -->
<style><!-- .EmailQuote { margin-left: 1pt; padding-left: 4pt; border-left: #800000 2px solid; } --></style>
</head>
<body>
<font face="Calibri" size="2"><span style="font-size:11pt;">
<div>Hi,</div>
<div> </div>
<div>This is a proposal about implementing strided memory access vectorization.</div>
<div> </div>
<div>Currently LLVM does not support strided access vectorization completely, some support is available via Interleave vectorization.</div>
<div> </div>
<div>There are two main overheads with strided vectorizations:</div>
<ul style="margin:0;padding-left:36pt;">
<li>An overhead of <b>consolidating</b> data into an operable vector.</li><li>An overhead of <b>distributing</b> the data elements after the operations.</li></ul>
<div> </div>
<div>Because of these overheads LLVM finds strided memory vectorization is not profitable and generating serial code sequence over vectorized code.</div>
<div>GATHER & SCATTER instruction support is available on few(not all) targets for consolidation & distribution operations.</div>
<div> </div>
<div>In this approach we are trying to handle cases like this:</div>
<div><i>for (int i = 0; i < len; i++)</i></div>
<div><i> a[i*3] = b[i*2] + c[i*3];</i></div>
<div> </div>
<div>We model strided memory load & store using shuffle & load/mask-store operations.</div>
<ul style="margin:0;padding-left:36pt;">
<li>Load is modeled as loads followed by shuffle.</li><li>Store is modeled as shuffle followed by mask store.</li><li>To minimize load and store operation introduced ‘SkipFactor’.</li></ul>
<div> </div>
<div>‘SkipFactor’:</div>
<ul style="margin:0;padding-left:36pt;">
<li>Multiple load operation required for consolidating data into an operable vector.</li><li>Between various loads we skip by few offsets to effective consolidate.</li><li>SkipFactor is the number of additional offsets required to move from the previous vector load memory-end address for the next vector load.</li><li>SkipFactor allows all memory loads to be considered as identical (From valid element perspective).</li><li>SkipFactor = (Stride - (VF % Stride)) % Stride)</li></ul>
<div> </div>
<div>For example:</div>
<div><img src="cid:EF90A2CD62892247BC508D8D018FA7E4@namprd12.prod.outlook.com"> </div>
<div> </div>
<div><b>How </b><b>LOAD</b><b> is modeled:</b></div>
<div><u>Load stride 3 (i.e. load for b [ 3 * i ])</u></div>
<div> %5 = getelementptr inbounds i32, i32* %b, i64 %.lhs</div>
<div> %6 = bitcast i32* %5 to <4 x i32>*</div>
<div> <font color="red">%stride.load27 = load <4 x i32>, <4 x i32>* %6, align 1, !tbaa !1</font></div>
<div> %7 = getelementptr i32, i32* %5, i64 6 </div>
<div> %8 = bitcast i32* %7 to <4 x i32>*</div>
<div> <font color="red"> %stride.load28 = load <4 x i32>, <4 x i32>* %8, align 1, !tbaa !1</font></div>
<div><font color="#2E74B5"> %strided.vec29 = shufflevector <4 x i32> %stride.load27, <4 x i32> %stride.load28, <4 x i32> <i32 0, i32 3, i32 4, i32 7></font></div>
<div> </div>
<div><b>How </b><b>STORE</b><b> is modeled:</b></div>
<div><u>Store with stride 3 (i.e. store to c [ 3 * i ])</u></div>
<div> %10 = getelementptr inbounds i32, i32* %c, i64 %.lhs</div>
<div> %11 = bitcast i32* %10 to <4 x i32>*</div>
<div><font color="#2E74B5"> %interleaved.vec = shufflevector <4 x i32> %StoreResult, <4 x i32> undef, <4 x i32> <i32 0, i32 undef, i32 undef, i32 1></font></div>
<div> <font color="red">call void @llvm.masked.store.v4i32(<4 x i32> %interleaved.vec, <4 x i32>* %11, i32 4, <4 x i1> <i1 true, i1 false, i1 false, i1 true>)</font></div>
<div> %12 = getelementptr i32, i32* %10, i64 6</div>
<div> %13 = bitcast i32* %12 to <4 x i32>*</div>
<div> <font color="#2E74B5">%interleaved.vec30 = shufflevector <4 x i32> %StoreResult, <4 x i32> undef, <4 x i32> <i32 2, i32 undef, i32 undef, i32 3></font></div>
<div><font color="red"> call void @llvm.masked.store.v4i32(<4 x i32> %interleaved.vec30, <4 x i32>* %13, i32 4, <4 x i1> <i1 true, i1 false, i1 false, i1 true>)</font></div>
<div> </div>
<div>NOTE: For Stride 3 SkipFactor is 2, that’s why the second GEP offset by 6(4+2).</div>
<div> </div>
<div>To enable this feature below LLVM changes required.</div>
<ol style="margin:0;padding-left:36pt;">
<li>Identify strided memory access (Its already there i.e. interleave vectorizer does this)</li><li>Costing changes:</li></ol>
<ol type="a" style="margin:0;padding-left:72pt;">
<li>Identify number of Load[s]/Store[s] & Shuffle[s] required to model Load/Store operation by considering SkipFactor.</li><li>Return total cost by adding Load[s]/Store[s] and shuffle[s] costs.</li></ol>
<ol start="3" style="margin:0;padding-left:36pt;">
<li>Transform:</li></ol>
<ol type="a" start="3" style="margin:0;padding-left:72pt;">
<li>Generate Shuffle[s] followed by Mask-Store[s] instructions to model a Store operation.</li><li>Generate Load[s] followed by Shuffle[s] instructions to model a Load operation.</li></ol>
<div> </div>
<div>Implemented a working prototype to demonstrate this feature, its available at below review-thread.</div>
<div><a href="http://reviews.llvm.org/D21363"><font color="#0563C1"><u>http://reviews.llvm.org/D21363</u></font></a></div>
<div> </div>
<div>Use below option to enable this feature:</div>
<div>“-mllvm -enable-interleaved-mem-accesses -mllvm -enable-strided-vectorization”</div>
<div> </div>
<div><b><u>Gains observed with prototype</u></b><b><u>:</u></b></div>
<div>TSVC kernel S111 1.15x</div>
<div>TSVC kernel S1111 1.42x</div>
<div> </div>
<div>If community is interested in the above work, I have below plan:</div>
<div> </div>
<div>I’m not sure keeping this feature separate or the part of current interleave vectorizer ?</div>
<div> </div>
<ol style="margin:0;padding-left:36pt;">
<li>Will enable interleave vectorizer on X86 (If this feature is going as an enhancement on interleave vectorizer)</li><li>If it’s going with interleave vectorizer, will modify its infra to support this.</li><li>Will enable strided vectorization by submitting changes on costing & transform.</li></ol>
<div> </div>
<div>Please share your valuable thoughts.</div>
<div> </div>
<div>Thanks,</div>
<div>Ashutosh</div>
<div> </div>
</span></font>
</body>
</html>