Subject: /lib/c2 fails to remove redundant 'tst' and 'branch's Index: lib/c21.c 2.11BSD Description: /lib/c2 (the "optimizer") fails to remove redundant 'tst' instructions (see #1 in the Repeat-By section). This was due to c2's not treating the 'tst' instruction as being capable of setting the condition codes. also, /lib/c2 does not collapse adjacent 'branches' to the same label after a 'tst' (see #2 below). In general branches can not be merged. However, following a 'tst' instruction it is known that the C and V condition code bits are 0 and some branches can be merged. overall the savings are worth the small increase in compilation time. recompiling the kernel using the new optimizer saved 2 clicks (128 bytes) of text in the kernel itself and 1 click (64 bytes) in the networking portion (/netnix). Repeat-By: Look at the generated code for this test program (it's not contrived, this occurs in sys/kern_clock.c). The multiple branch situation occurs even more frequently than the nested 'if'. int x; main() { if (x) if (x > 0) exit(); } OLD Optimizer ------------- _main: tst _x jeq L3 tst _x #1 jmi L3 jeq L3 #2 jsr pc,_exit L3: jmp cret NEW Optimizer ------------ _main: tst _x jle L3 jsr pc,_exit L3: jmp cret A saving of 8 bytes! Fix: Apply the following patch to 'c21.c', recompile and install c2. ---------------------------------------------------------------------- *** /usr/src/lib/c2/c21.c.old Fri Oct 4 08:39:10 1991 --- /usr/src/lib/c2/c21.c Sun Oct 20 16:15:12 1991 *************** *** 229,235 **** --- 229,254 ---- p = p->back; nchange++; } + /* + * If the instruction prior to the conditional branch was a 'tst' then + * save the condition code status. The C construct: + * if (x) + * if (x > 0) + * generates "tst _x; jeq ...; tst _x; jmi ...;jeq ...". The code below removes + * the second "tst _x", leaving "tst _x; jeq ...;jmi ...; jeq ...". + */ + if (p->back->op == TST) { + singop(p->back); + setcc(regs[RT1]); + break; + } } + /* + * If the previous instruction was also a conditional branch then + * attempt to merge the two into a single branch. + */ + if (p->back->op == CBR) + fixupbr(p); case CFCC: ccloc[0] = 0; continue; *************** *** 242,247 **** --- 261,316 ---- } } } + + /* + * This table is used to convert two branches to the same label after a + * 'tst' (which clears the C and V condition codes) into a single branch. + * Entries which translate to JBR could eventually cause the 'tst' instruction + * to be eliminated as well, but that can wait for now. There are unused or + * impossible combinations ('tst' followed by 'jlo' for example. since + * 'tst' clears C it makes little sense to 'jlo/bcs') in the table, it + * would have cost more in code to remove them than the entries themselves. + * + * Example: "tst _x; jmi L3; jeq L3". Find the row for 'jmi', then look + * at the column for 'jeq', the resulting "opcode" is 'jle'. + */ + char brtable[12][12] = { + /* jeq jne jle jge jlt jgt jlo jhi jlos jhis jpl jmi */ + /* jeq */ {JEQ ,JBR ,JLE ,JGE ,JLE ,JGE ,JEQ ,JBR ,JEQ ,JBR ,JGE ,JLE}, + /* jne */ {JBR ,JNE ,JBR ,JBR ,JNE ,JNE ,JNE ,JNE ,JBR ,JBR ,JBR ,JNE}, + /* jle */ {JLE ,JBR ,JLE ,JBR ,JLE ,JBR ,JLE ,JBR ,JLE ,JBR ,JBR ,JLE}, + /* jge */ {JGE ,JBR ,JBR ,JGE ,JBR ,JGE ,JGE ,JBR ,JGE ,JBR ,JGE ,JBR}, + /* jlt */ {JLE ,JNE ,JLE ,JBR ,JLT ,JNE ,JLT ,JBR ,JLE ,JBR ,JBR ,JLT}, + /* jgt */ {JGE ,JNE ,JBR ,JGE ,JNE ,JGT ,JGT ,JGT ,JBR ,JGE ,JGE ,JNE}, + /* jlo */ {JEQ ,JNE ,JLE ,JGE ,JLT ,JGT ,JLO ,JHI ,JLOS,JHIS,JPL ,JMI}, + /* jhi */ {JBR ,JNE ,JBR ,JBR ,JNE ,JNE ,JNE ,JNE ,JBR ,JBR ,JBR ,JNE}, + /* jlos*/ {JEQ ,JBR ,JLE ,JGE ,JLE ,JGE ,JLE ,JBR ,JEQ ,JBR ,JGE ,JLE}, + /* jhis*/ {JBR ,JBR ,JBR ,JBR ,JBR ,JBR ,JBR ,JBR ,JBR ,JBR ,JBR ,JBR}, + /* jpl */ {JGE ,JBR ,JBR ,JGE ,JBR ,JGE ,JGE ,JBR ,JGE ,JBR ,JGE ,JBR}, + /* jmi */ {JLE ,JNE ,JLE ,JBR ,JLT ,JNE ,JLT ,JNE ,JLE ,JLT ,JBR ,JLT} + }; + + fixupbr(p) + register struct node *p; + { + register struct node *p1, *p2; + int op; + + p1 = p->back; + p2 = p1->back; + if (p->labno != p1->labno) + return; + if (p2->op != TST) { + if (p2->op == CBR && p2->back->op == TST) + goto ok; + return; + } + ok: p->subop = brtable[p->subop][p1->subop]; + nchange++; + nredunj++; + p2->forw = p; + p->back = p1->back; + } jumpsw() {