<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Benedict,<div><br></div><div>LLVM has a reasonably nice loop optimization *framework* and support code like loop extraction and SCEV, but relatively few existing loop optimizations. I think it would be relatively easy for you to add the ones you want. In addition, we have just begun developing a new parallelizing compiler infrastructure based on LLVM at Illinois and I expect more loop optimizations for both parallelism and locality to be added in the near future.</div><div><br></div><div>--Vikram</div><div><div apple-content-edited="true"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div><div><div><div><div><span class="Apple-style-span" style="font-style: italic; "><a href="http://llvm.org/~vadve">http://llvm.org/~vadve</a></span></div><br><br></div></div></div></div></div></div></span></div></span></div></span> </div><br><div><div>On Jun 11, 2008, at 5:59 AM, Gaster, Benedict wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div lang="EN-US" link="blue" vlink="purple"><div class="Section1"><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">Hello,<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">We are currently evaluating LLVM as a compiler technology against Open64 and have a few questions regarding its currently status with respect to optimizations in particular.<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">Control flow is often expensive on the architectures we are considering and as such loop optimizations, e.g. unroll and jam, can play an important role. For example, consider the following program<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">int a[4][4];<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">int b[4][4];<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">int c[4][4];<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">int main(void)<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">{<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> int i, j, k;<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> <o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> for(i = 0; i < 4; i++)<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> {<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> for(j = 0; j < 4; j++)<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> {<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> c[i][j] = 0;<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> for (k = 0; k < 4; k++)<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> c[i][j] = a[i][k] * b[k][j] + c[i][j];<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> }<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> }<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> <o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> return c[2][3];<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">}<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">If I compile this with std-compile-opts the inner loops are completely unrolled and thus unroll-and-jam is not important here but I’m assuming this is down to the fact that the loop bounds are known and small. Assuming this was not the case what I would like to be able to do is unroll the loop iterating over “j” some number of times and then fuse the resulting instances of the inner loop, e.g:<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">for(i=O; i<4; i++)<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> for(j=O; j<4; j+=2)<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> {<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> c[i][j] = 0;<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> c [i][j+1]= 0;<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> for(k=O; k<4; k++)<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> {<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> c[i] [j] = a[i][k]*b[k] [j]+c[i][j];<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> c[i][j+1]= a[i][k]*b[k] [j+1]+c[i] [j+1];<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> }<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "> }<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">Of course this is the well known unroll-and-jam optimization, described by Car and Kennedy*, and I was wondering if there are plans to add this and other additional loop optimizations to LLVM in the near future?<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">Thanks for any information you can provide around this.<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">Ben<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; ">*<span style="font-size: 10pt; font-family: Arial, sans-serif; ">S. Carr and K. Kennedy, “Improving the ratio of memory operations to floating-point operations in loops,”</span><span style="font-size: 9pt; font-family: Arial, sans-serif; ">ACM<span class="Apple-converted-space"> </span></span><span style="font-size: 10pt; font-family: Arial, sans-serif; ">Transactions on<span class="Apple-converted-space"> </span></span><span style="font-size: 9pt; font-family: Arial, sans-serif; ">Programming Languages and Systems,<span class="Apple-converted-space"> </span></span><span style="font-size: 10pt; font-family: Arial, sans-serif; ">vol. 16, no. 6, pp. 1768-1810, 1994.</span><o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><span style="color: navy; "><span><image001.gif></span><o:p></o:p></span></div><table class="MsoNormalTable" border="0" cellspacing="0" cellpadding="0"><tbody><tr><td width="89" style="width: 66.75pt; padding-top: 0.75pt; padding-right: 0.75pt; padding-bottom: 0.75pt; padding-left: 0.75pt; "></td><td style="padding-top: 0.75pt; padding-right: 0.75pt; padding-bottom: 0.75pt; padding-left: 0.75pt; "></td></tr></tbody></table><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif; "><o:p> </o:p></div><span><ATT00001.txt></span></div></div></span></blockquote></div><br></div></body></html>