Hi LLVMers,<div><br></div><div>I'm writing a LLVM backend for C*Core, an ISA derived from Motorola M*Core. I was wondering if someone wrote some IR level optimization passes for backend porting before ISel, such as an IR transformation from GEP to integer conversion/calculating instructions, and PHI combination. Here's the bubble sorting example. <font class="Apple-style-span" color="#FF0000">The IR codes below are changed by hand and I try to write passes to do such modifications automatically.</font></div>
<div><br></div><div><div>C codes (bubbleSort.c):</div></div><blockquote class="webkit-indent-blockquote" style="margin:0 0 0 40px;border:none;padding:0px"><div><div>void bubbleSort(int *arr, int n) {</div></div><div><div>
int i, j;</div></div><div><div><br></div></div><div><div> int sz = n - 1;</div></div><div><div> for (i = 0; i < sz; i++)</div></div><div><div> for (j = 0; j < sz - i; j++)</div></div><div><div> if(*(arr+j) > *(arr+j+1)) {</div>
</div><div><div> int t = *(arr+j);</div></div><div><div> *(arr+j) = *(arr+j+1);</div></div><div><div> *(arr+j+1) = t;</div></div><div><div> }</div></div><div><div>}</div></div></blockquote><div>
<br>
</div><div>Part of assemble codes (bubbleSort-gcc-O2.s) from GCC M*Core backend with -O2:</div>
<blockquote class="webkit-indent-blockquote" style="margin:0 0 0 40px;border:none;padding:0px"><div><div>.L3:</div></div><div><div>cmplti<span style="white-space:pre-wrap"> </span>r3,1</div></div><div><div>jbt<span style="white-space:pre-wrap"> </span>.L6</div>
</div><div><div><font color="#FF0000">mov</font><span style="white-space:pre-wrap"><font color="#FF0000"> </font></span><font color="#FF0000">r7,r2</font></div></div><div><div>movi<span style="white-space:pre-wrap"> </span>r6,0</div>
</div><div><div><br></div><div>.L5:</div></div><div><div>ldw<span style="white-space:pre-wrap"> </span>r5,(<font class="Apple-style-span" color="#FF0000">r7</font>)</div></div><div><div>ldw<span style="white-space:pre-wrap"> </span>r4,(r7,4)</div>
</div><div><div><span class="Apple-style-span" style="white-space:pre-wrap"> ...</span></div></div><div><div>.L4:</div></div><div><div>addi<span style="white-space:pre-wrap"> </span>r6,1</div></div><div><div><font color="#FF0000">addi</font><span style="white-space:pre-wrap"><font color="#FF0000"> </font></span><font color="#FF0000">r7,4</font></div>
</div><div><div>cmpne<span style="white-space:pre-wrap"> </span>r3,r6</div></div><div><div>jbt<span style="white-space:pre-wrap"> </span>.L5</div></div></blockquote><div>
<div><br></div></div><div>The address calculating formula for such code is </div><div>
N(0) = arr;<br clear="all"><div>N(n) = N(n-1) + ElementSize, n>= 1</div><div><br></div><div>which r2 stands for arr, r7 stands for the next address, and ElementSize of int type is 4.</div><div><br></div><div><br></div>
<div>However, LLVM GEP adopts a rule as N(n) = arr + n * ElementSize, and may produce several instructions to compute the address.</div><div><br></div><div>Here's IR codes (bubbleSort-O3.ll) generated by Clang -O3:</div>
</div><blockquote class="webkit-indent-blockquote" style="margin:0 0 0 40px;border:none;padding:0px"><div><div>for.body4:</div></div><div><div><div>
%j.018 = phi i32 [ 0, %<a href="http://for.body4.lr.ph">for.body4.lr.ph</a> ], [ %add.ptr.sum, %for.inc ]</div></div></div><div><div><div> %add.ptr.sum = add i32 %j.018, 1</div></div></div><div><div><div> %add.ptr6 = getelementptr inbounds i32* %arr, i32 %add.ptr.sum</div>
</div></div><div><div> %1 = load i32* %add.ptr6, align 4, !tbaa !0</div></div></blockquote><div><div><br></div><div>and thus generated assembly codes (bubbleSort-mcore-O3.s) by llc -march=mcore as following:</div></div>
<blockquote class="webkit-indent-blockquote" style="margin:0 0 0 40px;border:none;padding:0px">
<div><div><div><font class="Apple-style-span" color="#FF0000">mov</font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" color="#FF0000"> </font></span><font class="Apple-style-span" color="#FF0000">r13,r6</font></div>
</div></div><div><div><div><font class="Apple-style-span" color="#FF0000">lsli</font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" color="#FF0000"> </font></span><font class="Apple-style-span" color="#FF0000">r13, 2</font></div>
</div></div><div><div><div><font class="Apple-style-span" color="#FF0000">mov</font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" color="#FF0000"> </font></span><font class="Apple-style-span" color="#FF0000">r14,r2</font></div>
</div></div><div><div><div><font class="Apple-style-span" color="#FF0000">addu</font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" color="#FF0000"> </font></span><font class="Apple-style-span" color="#FF0000">r14,r13</font></div>
</div></div><div><div><div>ldw r13, (<font class="Apple-style-span" color="#FF0000">r14</font>, 4)</div></div></div></blockquote><div><div>in which r6 stands for %j.018, r2 stands for arr, and lsli N means left logic shift N bits.</div>
<div><br></div><div><font class="Apple-style-span" color="#FF0000">(It may be meaningless, but I don't know a better way to get good codes as GCC)</font></div><div>If I modified IR(bubbleSort-cast-1.ll) by transforming GEP to integer instructions and calculating the address as below, and I could get codes(bubbleSort-mcore-cast-1.s) as same as GCC shown above.</div>
</div><blockquote class="webkit-indent-blockquote" style="margin:0 0 0 40px;border:none;padding:0px"><div><div><a href="http://for.body4.lr.ph">for.body4.lr.ph</a>:</div></div><div><div>%base = <font class="Apple-style-span" color="#FF0000">ptrtoint </font>i32* %arr to i32</div>
</div><div><div><br></div></div><div><div>for.body4:</div></div><div><div><div> %cast = <font class="Apple-style-span" color="#FF0000">phi </font>i32 [ %base, %<a href="http://for.body4.lr.ph">for.body4.lr.ph</a> ], [ %cast.next, %for.inc ]</div>
</div></div><div><div><div> %ptr = <font class="Apple-style-span" color="#FF0000">inttoptr </font>i32 %cast to i32*</div></div></div><div><div><div> %add.ptr6 = getelementptr inbounds i32* %ptr, i32 1</div></div></div>
<div>
<div><div> %1 = load i32* %add.ptr6, align 4, !tbaa !0</div></div></div><div><div><br></div></div><div><div>for.inc: </div></div><div><div> %cast.next = <font class="Apple-style-span" color="#FF0000">add </font>i32 %cast, 4</div>
</div></blockquote><div><div><br></div><div>The idea for such GEP cast pass is </div><div> 1) check the fourth operand of GEP (<idx>) whether a binary instruction such as add or sub (go 2)), or not (return).</div>
<div>
2) create the pointer-to-int instructions in the "preheader" block(%<a href="http://for.body4.lr.ph">for.body4.lr.ph</a>) and a step-by-step instruction in the next block (%for.inc).</div><div> 3) create a PHI instruction and a int-to-pointer instruction in the current block.</div>
<div> 4) replace the old GEP with the new GEP.</div><div><br></div><div><br></div><div>Next, I may reduce IR variables like %i.020, %sub2, %inc15 in bubbleSort-cast-2.ll and obtain better codes shown in bubbleSort-mcore-cast-2.s.</div>
</div><div>The yellow codes are the original IR, and the red are modified ones:</div><div><br></div><blockquote class="webkit-indent-blockquote" style="margin:0 0 0 40px;border:none;padding:0px"><div><div>for.cond1.preheader: ; preds = %entry, %for.inc14</div>
</div><div><div><div> %indvars.iv = phi i32 [ %indvars.iv.next, %for.inc14 ], [ %sub, %entry ]</div></div></div><div><div><div><font class="Apple-style-span" color="#FF6600"> ;%i.020 = phi i32 [ %inc15, %for.inc14 ], [ 0, %entry ]</font></div>
</div></div><div><div><div><font class="Apple-style-span" color="#FF6600"> ;%sub2 = sub nsw i32 %sub, %i.020</font></div></div></div><div><div><div><font class="Apple-style-span" color="#FF6600"> ;%cmp317 = icmp sgt i32 %sub2, 0</font></div>
</div></div><div><div><div><font class="Apple-style-span" color="#FF0000"> %cmp317 = icmp sgt i32 %indvars.iv, 0</font></div></div></div><div><div> br i1 %cmp317, label %<a href="http://for.body4.lr.ph">for.body4.lr.ph</a>, label %for.inc14</div>
</div><div><div><br></div></div><div><div><div>for.inc14: ; preds = %for.inc, %for.cond1.preheader</div></div></div><div><div><div><font class="Apple-style-span" color="#FF6600"> ;%inc15 = add nsw i32 %i.020, 1</font></div>
</div></div><div><div><div> %indvars.iv.next = add i32 %indvars.iv, -1</div></div></div><div><div><div><font class="Apple-style-span" color="#FF6600"> ;%exitcond21 = icmp eq i32 %inc15, %sub</font></div></div></div><div>
<div><div> <font class="Apple-style-span" color="#FF0000"> %exitcond21 = icmp eq i32 %indvars.iv.next, 0</font></div></div></div><div><div><div> br i1 %exitcond21, label %for.end16, label %for.cond1.preheader</div></div>
</div></blockquote><div><div><br></div><div>I think, the condition for applying such PHI optimization are</div><div> 1) the same entry points for several PHI instructions in one basic block, such as %for.inc14 and %entry.</div>
<div> 2) the same step but may in two different directions, such as %indvars.iv and %i.020 are both changed by 1, although the former increase and the latter decrease.</div><div><br></div><div>Any suggestions are welcome!</div>
<div><br></div><div>Regards,</div><div>Zuyu Zhang</div>
<div style="zoom:100%"></div><br>
</div>