<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Adam Nemet" <anemet@apple.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"Dangeti Tharun kumar" <cs15mtech11002@iith.ac.in>, "Santanu Das" <cs15mtech11018@iith.ac.in>, llvm-dev@lists.llvm.org<br><b>Sent: </b>Monday, October 10, 2016 4:52:18 PM<br><b>Subject: </b>Re: [llvm-dev] On Loop Distribution pass<br><br>
<br class=""><div><blockquote class=""><div class="">On Oct 10, 2016, at 2:50 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="" target="_blank">hfinkel@anl.gov</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br class="Apple-interchange-newline"><hr id="zwchr" style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;" class=""><b class="">From:<span class="Apple-converted-space"> </span></b>"Dangeti Tharun kumar via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class=""><b class="">To:<span class="Apple-converted-space"> </span></b><a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a><br class=""><b class="">Cc:<span class="Apple-converted-space"> </span></b>"Santanu Das" <<a href="mailto:cs15mtech11018@iith.ac.in" class="" target="_blank">cs15mtech11018@iith.ac.in</a>><br class=""><b class="">Sent:<span class="Apple-converted-space"> </span></b>Sunday, October 9, 2016 12:09:01 PM<br class=""><b class="">Subject:<span class="Apple-converted-space"> </span></b>[llvm-dev] On Loop Distribution pass<br class=""><br class=""><div dir="ltr" class="">Dear community,<div class=""><br class=""></div><div class="">Our team at IITH have been experimenting with loop-distribution pass in LLVM. We see the following results on few benchmarks.</div><div class=""><br class=""></div><div class=""><span id="gmail-docs-internal-guid-e7e6be9a-aa54-3006-2059-effa9157d485" class=""><div style="margin: 0pt 0px; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; font-family: 'courier new'; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">clang -O3 -mllvm -enable-loop-distribute -Rpass=loop-distribute file.c</span></div><div style="margin: 0pt 0px; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; font-family: 'courier new'; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><span style="font-size: 13.3333px; line-height: 18.4px;" class="">clang -O3 -mllvm -enable-loop-distribute -Rpass-analysis=loop-distribute file.c</span><br class=""></span></div><br class=""><br class=""><div style="margin: 0pt 0px; line-height: 1.38; text-indent: 36pt;" class=""><font class="" face="monospace, monospace"><a href="http://crd.lbl.gov/departments/computer-science/PAR/research/previous-projects/torch-testbed/" target="_blank" style="text-decoration: none;" class=""><span style="font-size: 16px; font-weight: 700; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">TORCH</span></a><span style="font-size: 16px; font-weight: 700; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">:</span></font></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38;" class=""><span style="font-size: 16px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" face="monospace, monospace">There are nearly 488 loops in this benchmark. LLVM was not able to distribute any loop.</font></span></div><font class="" face="monospace, monospace"><br class=""></font><div style="margin: 0pt 0px; line-height: 1.38; text-indent: 36pt;" class=""><font class="" face="monospace, monospace"><a href="https://github.com/shantanuatiith/TSVC_" target="_blank" style="text-decoration: none;" class=""><span style="font-size: 16px; font-weight: 700; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">TSVC</span></a><span style="font-size: 16px; font-weight: 700; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">:</span></font></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38;" class=""><font class="" face="monospace, monospace"><span style="font-size: 16px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">There are 151 loops coded in plain ‘C’, </span><span style="font-size: 16px; font-weight: 700; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">none</span><span style="font-size: 16px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""> of them got distributed. TSVC has particularly candidates valid for distribution like the one below. The inner loop in this example can be distributed.</span></font></div><font class="" face="monospace, monospace"><br class=""></font><div style="margin: 0pt 0px 0pt 36pt; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" color="#444444" face="monospace, monospace">for (int nl = 0; nl < ntimes/2; nl++) {</font></span></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" color="#444444" face="monospace, monospace">for (int i = 1; i < LEN; i++) {</font></span></div><div style="margin: 0pt 0px 0pt 108pt; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" color="#444444" face="monospace, monospace">a[i] += c[i] * d[i];</font></span></div><div style="margin: 0pt 0px 0pt 108pt; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" color="#444444" face="monospace, monospace">b[i] = b[i - 1] + a[i] + d[i];</font></span></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" color="#444444" face="monospace, monospace">}</font></span></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" color="#444444" face="monospace, monospace">dummy(a, b, c, d, e, aa, bb, cc, 0.);</font></span></div><div style="margin: 0pt 0px 0pt 36pt; line-height: 1.38; text-indent: 36pt;" class=""><span style="font-size: 13.3333px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" color="#444444" face="monospace, monospace"> }</font></span></div><font class="" face="monospace, monospace"><br class=""></font><div style="margin: 0pt 0px; line-height: 1.38;" class=""><font class="" face="monospace, monospace"><span style="font-size: 16px; vertical-align: baseline; background-color: transparent;" class=""> <a href="http://vhosts.eecs.umich.edu/mibench//" target="_blank" style="font-weight: 700; white-space: pre-wrap; text-decoration: none;" class="">MiBench</a></span><span style="font-size: 16px; font-weight: 700; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">:</span></font></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38;" class=""><span style="font-size: 16px; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class=""><font class="" face="monospace, monospace">There are 6539 loops in MiBench. <b class="">None</b> of the loops were distributed by the loop-distribution pass of LLVM.</font></span></div><font class="" face="monospace, monospace"><br class=""></font><div style="margin: 0pt 0px; line-height: 1.38;" class=""><font class="" face="monospace, monospace"><span style="font-size: 16px; vertical-align: baseline; background-color: transparent;" class=""> <a href="https://github.com/exmatex/CoMD" target="_blank" style="font-weight: 700; white-space: pre-wrap; text-decoration: none;" class="">CoMD</a></span><span style="font-size: 16px; font-weight: 700; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;" class="">:</span></font></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38;" class=""><span style="font-size: 16px; vertical-align: baseline; white-space: pre-wrap;" class=""><font class="" face="monospace, monospace">CoMD is a reference implementation of typical classical molecular dynamics algorithms and workloads.</font></span></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38;" class=""><font class="" face="monospace, monospace"><span style="font-size: 16px; vertical-align: baseline; white-space: pre-wrap;" class="">Out of 112 loops </span><span style="font-size: 16px; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;" class="">none</span><span style="font-size: 16px; vertical-align: baseline; white-space: pre-wrap;" class=""> of them are distributed.</span></font></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38;" class=""><span style="font-size: 16px; font-family: arial; vertical-align: baseline; white-space: pre-wrap;" class=""><br class=""></span></div><div style="margin: 0pt 0px 0pt 72pt; line-height: 1.38;" class=""><span style="font-size: 16px; font-family: arial; vertical-align: baseline; white-space: pre-wrap;" class=""><br class=""></span></div>For the specific loop I have shown above which is straight forward a good distribution candidate, the remark is "<b class="">loop not distributed: memory operations are safe for vectorization [-Rpass-analysis=loop-distribute]</b>". </span></div><div class=""><span class=""><br class=""></span></div><div class=""><span class="">Can someone reason these results and this remark?</span></div><div class=""><span id="DWT390" class=""><br class=""></span></div></div></blockquote><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">The current loop distribution implementation is focused on enabling vectorization. The comment at the top of the file says:</span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class=""> // This file implements the Loop Distribution Pass. Its main focus is to</span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class=""> // distribute loops that cannot be vectorized due to dependence cycles. It</span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class=""> // tries to isolate the offending dependences into a new loop allowing</span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class=""> // vectorization of the remaining parts.</span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Hopefully, this helps explain the diagnostic. Regarding why the loop you highlight is not distributed to enable the vectorization of the a[i] update, I don't know. Adam?</span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""></div></blockquote><div><br class=""></div><div id="DWT737">Yeah, it’s not immediate clear to me why we’re not distributing that. I think it’s s221() from TSVC. I will take a look later.</div></div></blockquote>Yes, it looks like s221.<br><br> -Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div><div></div><div><br class=""></div><div>Adam</div><br class=""><blockquote class=""><div class=""><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class=""> -Hal</span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span id="gmail-docs-internal-guid-e7e6be9a-aa54-3006-2059-effa9157d485" style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""></span><blockquote style="font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class=""><span class=""><br class="">I humbly request the community to correct me, if am missing something in my analysis.</span><div class=""><br class=""></div>--<span class="Apple-converted-space"> </span><br class=""><div class="gmail_signature"><div dir="ltr" class=""><div class=""><div dir="ltr" class="">Thank you<div class="">D Tharun kumar</div><div class="">CS15MTECH11002</div><div class="">9948373970</div><div class="">CSE-IITH</div></div></div></div></div></div></div><br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""></blockquote><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">--<span class="Apple-converted-space"> </span></span><br style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><div style="font-family: arial,helvetica,sans-serif; font-size: 13.3333px; font-style: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span class=""></span>Hal Finkel<br class="">Lead, Compiler Technology and Programming Languages<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory</div></div></blockquote></div><br class=""></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Lead, Compiler Technology and Programming Languages<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>