<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 14 (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:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:"Arial Narrow";
panose-1:2 11 6 6 2 2 2 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"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Thx Gerolf. Let me investigate your suggestion.<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 #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Gerolf Hoflehner [mailto:ghoflehner@apple.com]
<br>
<b>Sent:</b> Saturday, June 13, 2015 3:37 AM<br>
<b>To:</b> Das, Dibyendu; Adam Nemet<br>
<b>Cc:</b> llvmdev@cs.uiuc.edu<br>
<b>Subject:</b> Re: [LLVMdev] Loop Vectorization and Store-Load Forwarding issue<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">+Adam<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I’m seeing more cases where the compiler makes guesses about the processor rather than querying a machine model. Rather than a sophisticated model there could be a basic/lightweight machine description file that can be queried when it is
available. In this specific example a formula like 'dependence distance/ width > store2load_fwd_delay' would help conflict modeling. Does that sound like a promising path forward?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Cheers<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Gerolf<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><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 Jun 11, 2015, at 10:11 PM, Das, Dibyendu <<a href="mailto:Dibyendu.Das@amd.com">Dibyendu.Das@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 have been looking into this small test case (Part A) where loop vectorization is disabled due to possible store-load forwarding conflict (Part B). As you can see, due to
the presence of dependence distance 2 the loop is vectorizable only for a width of 2. However, the presence of dependence distance 15 (due to y[j-15]) results in store-load forwarding issue as store packet of y[16:17] (iteration j=16) partially overlaps with
load packets of y[15:16] (iteration j=30) and y[17:18] (iteration j=32). As conflicts introduce additional delays in the store->load forwarding pipes, this fact is modeled in the method<span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Arial Narrow","sans-serif"">MemoryDepChecker::couldPreventStoreLoadForward()</span><span class="apple-converted-space"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif""> </span></span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif"">in
LoopAccessAnalysis.cpp. The function may turn off vectorization in the presence of such conflicts. Looking through the code gives me the feeling that it may be more conservative than desired. The reason being, if the dependence distance is high, the conflicting
store may flush out of the store pipe by the time the load is issued. And vectorization may become beneficial.<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"">I am seeing some performance improvements when I disable the method above. This is for x86. Hence I am seeking some advice on how to improve the following logic. Can we better
model<span class="apple-converted-space"> </span></span><span style="font-size:8.0pt;font-family:"Calibri","sans-serif"">NumCyclesForStoreLoadThroughMemory<span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif"">?
This may be way too high ? Or there are other ways to circumvent the basic problem ?<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"">-TIA<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif"">Dibyendu<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"">Part A:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:8.0pt;font-family:"Calibri","sans-serif""> const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize; // 512 for the test case shown</span><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:8.0pt;font-family:"Calibri","sans-serif""> // Maximum vector factor.</span><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:8.0pt;font-family:"Calibri","sans-serif""> unsigned MaxVFWithoutSLForwardIssues = VectorizerParams::MaxVectorWidth * TypeByteSize; <span class="apple-converted-space"> </span></span><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:8.0pt;font-family:"Calibri","sans-serif""> if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues)</span><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:8.0pt;font-family:"Calibri","sans-serif""> MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes;</span><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:8.0pt;font-family:"Calibri","sans-serif""> </span><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:8.0pt;font-family:"Calibri","sans-serif""> for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues; vf *= 2) {</span><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:8.0pt;font-family:"Calibri","sans-serif""> if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) {</span><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:8.0pt;font-family:"Calibri","sans-serif""> MaxVFWithoutSLForwardIssues = (vf >>=1);</span><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:8.0pt;font-family:"Calibri","sans-serif""> break;</span><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:8.0pt;font-family:"Calibri","sans-serif""> }</span><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:8.0pt;font-family:"Calibri","sans-serif""> }</span><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:8.0pt;font-family:"Calibri","sans-serif""> </span><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:8.0pt;font-family:"Calibri","sans-serif""> if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) {</span><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:8.0pt;font-family:"Calibri","sans-serif""> DEBUG(dbgs() << "LAA: Distance " << Distance <<</span><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:8.0pt;font-family:"Calibri","sans-serif""> " that could cause a store-load forwarding conflict\n");</span><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:8.0pt;font-family:"Calibri","sans-serif""> return true;</span><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:8.0pt;font-family:"Calibri","sans-serif""> }</span><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"">----------------------------<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Calibri","sans-serif"">Part B:</span><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:10.0pt;font-family:"Calibri","sans-serif"">typedef unsigned long long uint64;</span><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:10.0pt;font-family:"Calibri","sans-serif""> </span><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:10.0pt;font-family:"Calibri","sans-serif"">void foo(const unsigned char *m, unsigned int block, uint64 y[80])</span><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:10.0pt;font-family:"Calibri","sans-serif"">{</span><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:10.0pt;font-family:"Calibri","sans-serif""> const unsigned char *sblock;</span><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:10.0pt;font-family:"Calibri","sans-serif""> int i, j;</span><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:10.0pt;font-family:"Calibri","sans-serif""> </span><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:10.0pt;font-family:"Calibri","sans-serif""> for (i = 0; i < (int) block; i++) {</span><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:10.0pt;font-family:"Calibri","sans-serif""> sblock = m + (i << 7);</span><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:10.0pt;font-family:"Calibri","sans-serif""> </span><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:10.0pt;font-family:"Calibri","sans-serif""> for (j = 16; j < 80; j++) {</span><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:10.0pt;font-family:"Calibri","sans-serif""> y[j] = y[j - 2] + y[j - 15] ;</span><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:10.0pt;font-family:"Calibri","sans-serif""> }</span><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:10.0pt;font-family:"Calibri","sans-serif""> }</span><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:10.0pt;font-family:"Calibri","sans-serif"">}</span><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"">Part C:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif""><snip> from the debug dump during the LoopAccessAnalysis phase:<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"">LAA: Checking memory dependencies<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif"">LAA: Src Scev: {(8 + %y),+,8}<%for.body3>Sink Scev: {(128 + %y),+,8}<nsw><%for.body3>(Induction step: 1)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif"">LAA: Distance for %3 = load i64, i64* %arrayidx6, align 8 to store i64 %add, i64* %arrayidx8, align 8: 120<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif"">LAA: Distance 120 that could cause a store-load forwarding conflict<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""> <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""> <o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif"">_______________________________________________<br>
LLVM Developers mailing list<br>
</span><a href="mailto:LLVMdev@cs.uiuc.edu"><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif"">LLVMdev@cs.uiuc.edu</span></a><span class="apple-converted-space"><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif""> </span></span><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif""> </span><a href="http://llvm.cs.uiuc.edu/"><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif"">http://llvm.cs.uiuc.edu</span></a><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif""><br>
</span><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif"">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>
</div>
</body>
</html>