<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=koi8-r">
<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;}
@font-face
{font-family:Verdana;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:"MS PGothic";
panose-1:2 11 6 0 7 2 5 8 2 4;}
@font-face
{font-family:"\@MS PGothic";}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:JA;}
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;
mso-fareast-language:JA;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"MS PGothic",sans-serif;
mso-fareast-language:JA;}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.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;}
/* List Definitions */
@list l0
{mso-list-id:342637181;
mso-list-type:hybrid;
mso-list-template-ids:1134315968 67698705 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{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;}
@list l1
{mso-list-id:634604049;
mso-list-template-ids:1241004388;}
@list l2
{mso-list-id:1207135025;
mso-list-template-ids:-372750802;}
@list l2:level1
{mso-level-start-at:2;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;}
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]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">When shufflevector was first introduced to IR and SelectionDAG, it required the output and input types to be identical. The IR shufflevector was later extended to allow arbitrary output types, but
the SelectionDAG SHUFFLE_VECTOR was never changed. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">This has generally worked out okay for most uses because size-changing shuffles are rare, and a lot of the interesting size-changing shuffles can be expressed in terms of CONCAT_VECTORS or EXTRACT_SUBVECTOR.
But maybe it’s worth revisiting shuffle representations at the SelectionDAG level.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">-Eli<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Wei Zhao via llvm-dev<br>
<b>Sent:</b> Thursday, October 31, 2019 1:51 PM<br>
<b>To:</b> llvm-dev@lists.llvm.org<br>
<b>Subject:</b> [EXT] [llvm-dev] Questions about type based "createBuildVecShuffle()" in DAG Combiner<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In LLVM DAG Combiner, DAGCombiner::createBuildVecShuffle() is type based.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">DAGCombiner.cpp, <o:p></o:p></p>
<p class="MsoNormal"> 17184 // We can't generate a shuffle node with mismatched input and output types.
<o:p></o:p></p>
<p class="MsoNormal"> 17185 // Try to make the types match the type of the output.
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l0 level1 lfo3">The codes following the above comment are trying to do a matching job between the input vectors and the output vector. Why the code is based on the assumption that only matched type
can be allowed to do a vector shuffle?<o:p></o:p></li></ol>
<p class="MsoNormal" style="margin-left:.25in"> A shuffle takes some fields of data from the input vector and reassembles them in the output vector. It is purely a data movement operation. The input vector is the container for the source data, and the
output vector is the container for the resulting data. Why these two containers have to have the same vector type?<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.25in">For example, <o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.25in">VT’s type: v2i16 <o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.25in">VecIn1 and VecIn2’s type: v4i16<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.25in">We take two i16 elements, each from VecIn1 and VecIn2 separately. With the current code, because of their type difference, there will be no shuffle generated
<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.25in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.25in">The requirement to create a shuffle operation should be: the capacity (SizeInBits) of the output vector can hold all the extracted data from the input vector container
<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.25in">So as long as the total SizeInBits of the input data extracted from the input vectors does not exceed the total SizeInBits of the out vector, the shuffle should be allowed to create. Sure there are some other checks
needed like indexes cannot be the same to avoid two data being placed in the same position.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0in" start="2" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l0 level1 lfo3">Another inconsistence is that the split of the vector right before the createBuildVecShuffle()<o:p></o:p></li></ol>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">DAGCombiner.cpp, <o:p></o:p></p>
<p class="MsoListParagraph"> 17436 // If all the Operands of BUILD_VECTOR extract from same
<o:p></o:p></p>
<p class="MsoListParagraph"> 17437 // vector, then split the vector efficiently based on the maximum
<o:p></o:p></p>
<p class="MsoListParagraph"> 17438 // vector access index and adjust the VectorMask and <o:p></o:p></p>
<p class="MsoListParagraph"> 17439 // VecIn accordingly. <o:p></o:p></p>
<p class="MsoListParagraph"><o:p> </o:p></p>
<p class="MsoListParagraph">This split will create a new vector type which most likely will not be the same as the output vector type. For example, if the previous vector input container and output container both have a type v8i16, after splitting, the input
vector will have type v4i16, again this will cause no shuffle being created later by the type based createBuildVecShuffle(), missing some shuffle operations. This type based shuffle node creation makes many optimization error-prone.
<o:p></o:p></p>
<p class="MsoListParagraph"><o:p> </o:p></p>
<p class="MsoListParagraph" style="margin-left:0in"> Looks like the input/output container type based approach to create a shuffle node will miss some shuffle operations which makes the generated code less efficient.<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:0in"><o:p> </o:p></p>
<p class="MsoListParagraph" style="margin-left:0in"> Any comment why it was first designed like this?
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="color:#1F497D">Wei </span><span style="font-size:12.0pt;font-family:"Verdana",sans-serif;color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>