<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>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 <font face="Arial Narrow">MemoryDepChecker::couldPreventStoreLoadForward(</font><font face="Arial Narrow">)</font> 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.</div>
<div> </div>
<div>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 <font size="1"><span style="font-size:8pt;">NumCyclesForStoreLoadThroughMemory</span></font><font size="1"><span style="font-size:8pt;">
</span></font>? This may be way too high ? Or there are other ways to circumvent the basic problem ?</div>
<div> </div>
<div>-TIA</div>
<div>Dibyendu</div>
<div> </div>
<div>Part A:</div>
<div><font size="1"><span style="font-size:8pt;"> const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize; // 512 for the test case shown</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> // Maximum vector factor.</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> unsigned MaxVFWithoutSLForwardIssues = VectorizerParams::MaxVectorWidth * TypeByteSize; </span></font></div>
<div><font size="1"><span style="font-size:8pt;"> if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues)</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes;</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> </span></font></div>
<div><font size="1"><span style="font-size:8pt;"> for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues; vf *= 2) {</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) {</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> MaxVFWithoutSLForwardIssues = (vf >>=1);</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> break;</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> }</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> }</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> </span></font></div>
<div><font size="1"><span style="font-size:8pt;"> if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) {</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> DEBUG(dbgs() << "LAA: Distance " << Distance <<</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> " that could cause a store-load forwarding conflict\n");</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> return true;</span></font></div>
<div><font size="1"><span style="font-size:8pt;"> }</span></font></div>
<div>----------------------------</div>
<div><font size="2"><span style="font-size:10pt;">Part B:</span></font></div>
<div><font size="2"><span style="font-size:10pt;">typedef unsigned long long uint64;</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> </span></font></div>
<div><font size="2"><span style="font-size:10pt;">void foo(const unsigned char *m, unsigned int block, uint64 y[80])</span></font></div>
<div><font size="2"><span style="font-size:10pt;">{</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> const unsigned char *sblock;</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> int i, j;</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> </span></font></div>
<div><font size="2"><span style="font-size:10pt;"> for (i = 0; i < (int) block; i++) {</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> sblock = m + (i << 7);</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> </span></font></div>
<div><font size="2"><span style="font-size:10pt;"> for (j = 16; j < 80; j++) {</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> y[j] = y[j - 2] + y[j - 15] ;</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> }</span></font></div>
<div><font size="2"><span style="font-size:10pt;"> }</span></font></div>
<div><font size="2"><span style="font-size:10pt;">}</span></font></div>
<div>Part C:</div>
<div><snip> from the debug dump during the LoopAccessAnalysis phase:</div>
<div> </div>
<div>LAA: Checking memory dependencies</div>
<div>LAA: Src Scev: {(8 + %y),+,8}<%for.body3>Sink Scev: {(128 + %y),+,8}<nsw><%for.body3>(Induction step: 1)</div>
<div>LAA: Distance for %3 = load i64, i64* %arrayidx6, align 8 to store i64 %add, i64* %arrayidx8, align 8: 120</div>
<div>LAA: Distance 120 that could cause a store-load forwarding conflict</div>
<div> </div>
<div> </div>
<div> </div>
<div> </div>
</span></font>
</body>
</html>