<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif;" dir="ltr">
<p style="margin-top:0;margin-bottom:0">Note the llvm/lib/Analysis/Delinearization.cpp recommends</p>
<p style="margin-top:0;margin-bottom:0">SCEVAddRecExpr::delinearize().</p>
<p style="margin-top:0;margin-bottom:0">See also llvm/lib/Analysis/DependenceAnalysis.cpp w/r the GEP operator.</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">Also note this 2015 paper:</p>
<p style="margin-top:0;margin-bottom:0"></p>
<ul>
<li><em>On recovering multi-dimensional arrays in Polly</em><br>
Tobias Grosser, Sebastian Pop, J. Ramanujam, P. Sadayappan <br>
Impact2015 at HiPEAC, Amsterdam, The Netherlands<br>
Slides & Paper: <a previewremoved="true" class="OWAAutoLink" id="LPlnk295461" href="http://impact.gforge.inria.fr/impact2015/">
Impact 2015</a></li></ul>
<a previewremoved="true" id="LPlnk367701" href="http://impact.gforge.inria.fr/impact2015/" class="OWAAutoLink">
http://impact.gforge.inria.fr/impact2015/</a>
<p></p>
<br>
<p style="margin-top:0;margin-bottom:0">Delinearization is useful, particularly when the code has been hand linearized,</p>
<p style="margin-top:0;margin-bottom:0">as is often the case for C/C++. Nonetheless, information may be lost by lowering</p>
<p style="margin-top:0;margin-bottom:0">multidimenional array references early. Consider:</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0"> float A[n1][n2], B[n2];</p>
<p style="margin-top:0;margin-bottom:0"> for (i = 0; i < ni; ++i)</p>
<p style="margin-top:0;margin-bottom:0"> for (j = 0; j < nj; ++j)</p>
<p style="margin-top:0;margin-bottom:0"> A[ix[i]][j] += B[j];</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">Even in C, the compiler may assume 0 <= j < n2.</p>
<p style="margin-top:0;margin-bottom:0">In Fortran this is beyond dispute. But after linearization,</p>
<p style="margin-top:0;margin-bottom:0">even with delinearization, the fact that nj <= n2 is not</p>
<p style="margin-top:0;margin-bottom:0">known at compile time. If the subscripts to A where</p>
<p style="margin-top:0;margin-bottom:0">interchange the situation is even worse, as 0 <= ix[i] < n2</p>
<p style="margin-top:0;margin-bottom:0">is expensive to verify.</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">So delinearization provide a benefit w/r hand linearized subscripts,</p>
<p style="margin-top:0;margin-bottom:0">while analysis of actual multidimensional references is best</p>
<p style="margin-top:0;margin-bottom:0">done prior to linearization - before information is lost.</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">Gary Elsesser</p>
<p style="margin-top:0;margin-bottom:0"> Cray, Inc.</p>
<p style="margin-top:0;margin-bottom:0"> Bloomington, MN</p>
<p style="margin-top:0;margin-bottom:0"> gwe@cray.com</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0"><br>
<br>
</p>
</div>
</body>
</html>