Zuyu Zhang
2012-Jul-30 16:23 UTC
[LLVMdev] IR optimization pass ideas for backend porting before ISel
Hi LLVMers, 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. The IR codes below are changed by hand and I try to write passes to do such modifications automatically. C codes (bubbleSort.c): void bubbleSort(int *arr, int n) { int i, j; int sz = n - 1; for (i = 0; i < sz; i++) for (j = 0; j < sz - i; j++) if(*(arr+j) > *(arr+j+1)) { int t = *(arr+j); *(arr+j) = *(arr+j+1); *(arr+j+1) = t; } } Part of assemble codes (bubbleSort-gcc-O2.s) from GCC M*Core backend with -O2: .L3: cmplti r3,1 jbt .L6 mov r7,r2 movi r6,0 .L5: ldw r5,(r7) ldw r4,(r7,4) ... .L4: addi r6,1 addi r7,4 cmpne r3,r6 jbt .L5 The address calculating formula for such code is N(0) = arr; N(n) = N(n-1) + ElementSize, n>= 1 which r2 stands for arr, r7 stands for the next address, and ElementSize of int type is 4. However, LLVM GEP adopts a rule as N(n) = arr + n * ElementSize, and may produce several instructions to compute the address. Here's IR codes (bubbleSort-O3.ll) generated by Clang -O3: for.body4: %j.018 = phi i32 [ 0, %for.body4.lr.ph ], [ %add.ptr.sum, %for.inc ] %add.ptr.sum = add i32 %j.018, 1 %add.ptr6 = getelementptr inbounds i32* %arr, i32 %add.ptr.sum %1 = load i32* %add.ptr6, align 4, !tbaa !0 and thus generated assembly codes (bubbleSort-mcore-O3.s) by llc -march=mcore as following: mov r13,r6 lsli r13, 2 mov r14,r2 addu r14,r13 ldw r13, (r14, 4) in which r6 stands for %j.018, r2 stands for arr, and lsli N means left logic shift N bits. (It may be meaningless, but I don't know a better way to get good codes as GCC) 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. for.body4.lr.ph: %base = ptrtoint i32* %arr to i32 for.body4: %cast = phi i32 [ %base, %for.body4.lr.ph ], [ %cast.next, %for.inc ] %ptr = inttoptr i32 %cast to i32* %add.ptr6 = getelementptr inbounds i32* %ptr, i32 1 %1 = load i32* %add.ptr6, align 4, !tbaa !0 for.inc: %cast.next = add i32 %cast, 4 The idea for such GEP cast pass is 1) check the fourth operand of GEP (<idx>) whether a binary instruction such as add or sub (go 2)), or not (return). 2) create the pointer-to-int instructions in the "preheader" block(% for.body4.lr.ph) and a step-by-step instruction in the next block (%for.inc). 3) create a PHI instruction and a int-to-pointer instruction in the current block. 4) replace the old GEP with the new GEP. 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. The yellow codes are the original IR, and the red are modified ones: for.cond1.preheader: ; preds = %entry, %for.inc14 %indvars.iv = phi i32 [ %indvars.iv.next, %for.inc14 ], [ %sub, %entry ] ;%i.020 = phi i32 [ %inc15, %for.inc14 ], [ 0, %entry ] ;%sub2 = sub nsw i32 %sub, %i.020 ;%cmp317 = icmp sgt i32 %sub2, 0 %cmp317 = icmp sgt i32 %indvars.iv, 0 br i1 %cmp317, label %for.body4.lr.ph, label %for.inc14 for.inc14: ; preds = %for.inc, %for.cond1.preheader ;%inc15 = add nsw i32 %i.020, 1 %indvars.iv.next = add i32 %indvars.iv, -1 ;%exitcond21 = icmp eq i32 %inc15, %sub %exitcond21 = icmp eq i32 %indvars.iv.next, 0 br i1 %exitcond21, label %for.end16, label %for.cond1.preheader I think, the condition for applying such PHI optimization are 1) the same entry points for several PHI instructions in one basic block, such as %for.inc14 and %entry. 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. Any suggestions are welcome! Regards, Zuyu Zhang -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort.c Type: text/x-csrc Size: 251 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment.c> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort-cast-1.ll Type: application/octet-stream Size: 2454 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort-cast-2.ll Type: application/octet-stream Size: 2547 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment-0001.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort-gcc-O2.s Type: application/octet-stream Size: 425 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment-0002.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort-mcore-cast-1.s Type: application/octet-stream Size: 1644 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment-0003.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort-mcore-cast-2.s Type: application/octet-stream Size: 1570 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment-0004.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort-mcore-O3.s Type: application/octet-stream Size: 1667 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment-0005.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: bubbleSort-O3.ll Type: application/octet-stream Size: 2351 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/a93ad7ee/attachment-0006.obj>