lcc 4.2 two-operand target problem

[Brian Davis]

In attempting to write an .md file for a homebrew
two-operand RISC, I've hit what appears to be an
lcc 4.2 register allocation bug affecting two-operand
targets having register locals.

I can reproduce the problem with a simple edit to the
existing <mips.md> target by changing the ADDI4 template
to use a two-operand rule.

I thought I'd check here on the chance that someone else
has already worked though this problem; see also [2a]
for another post describing this issue.

--------------------------
Problem Detail:

When targeting a two operand architecture, lcc 4.2 generates
code that overwrites the destination operand register before
it has been used as a source operand.

This happens whenever the destination is a register local
that also appears as the second source operand in the
lcc %c = OP(%0,%1) expression being matched.

Given:
:
: register int i,j;
:
: i = j + i;
:

Lcc emits the following code on a modified[3a-d] 4.2 MIPS
target having a hypothetical two-operand ADD/SUB.

Emitted code for i = j + i stomps on reg $30 before the add:
:
: move $30,$23
: add2u $30,$30
:

Note that the targets shipped with lcc 4.2 are all either
three-operand machines (Alpha/MIPS/SPARC), or two-operand
machines without register locals (x86), so it is plausible
that this escaped notice in the lcc 4.2 test cases.

(it is also plausible that I'm making a silly mistake somehere)

The code in ralloc() intended[4] to prevent this problem
never kicks in for register locals, which are already
allocated and assigned to an expression tree at the point
in a compilation when that ralloc() register masking code
is visited.

Adding[5] an assert to emitasm() to test "kids[1]" seems
to catch the bug in action.

--------------------------
Temporary debug patch

Hacking[6] <gen.c>'s rtarget() to always insert a temp
register load dodges the problem at the cost of extra
register moves everywhere:

code for i = j + i with rtarget hack:
:
: move $24,$30
: add2u $24,$23
: move $30,$24
:

I'm not sure that rtarget() is actually the best place in
the compiler to attempt a real patch for the problem.

It seems like swapping operands could avoid the overwrite
in most cases, especially on a two-operand target having
a Reverse Subtract instruction.

But I don't know enough about the lcc DAG/tree processing
to see where & how to do this properly without accidentally
introducing a heinous bug for other code sequences.

- Brian


References:

[1] F&H-95 "A retargetable C compiler: design and implementation", Fraser & Hanson , 1995


[2a] solitary 2008 comp.compilers.lcc post describing the same problem
http://groups.google.com/group/comp.compilers.lcc/msg/c9eb1c4c0b555988

[2b] obligatory xkcd reference for [2a]
http://xkcd.com/979/


[3] Changes to lcc 4.2 to create two operand ADDI4 and SUBI4 patterns:

[3a] start with the lcc 4.2 distribution :
https://github.com/drh/lcc/tree/v4_2

[3b] patch get() in <gram.c,y> to accept column 0 "!" as a line comment in .md template sections:

if (*bp == 0) {
bp = buf;
*bp = 0;
+
+ /* patch to accept "!" in column 0 as a line comment character in pattern section of .md files */
+ do
+ {
+ if (fgets(buf, sizeof buf, infp) == NULL) return EOF;
+ yylineno++;
+
+ } while (buf[0] == '!');
+

[3c] patch <mips.md> to change ADDI4 target instruction to a two operand template:

-reg: ADDI4(reg,rc) "addu $%c,$%0,%1\n" 1
+
+!
+! replace normal ADDI4 instruction, addu, with hypothetical add2u
+! in order to test two operand register allocation
+!
+!reg: ADDI4(reg,rc) "addu $%c,$%0,%1\n" 1
+reg: ADDI4(reg,rc) "?move $%c,$%0\nadd2u $%c,%1\n" 1
+

[3d] patch <mips.md> to change SUBI4 target instruction to a two operand template:

-reg: SUBI4(reg,rc) "subu $%c,$%0,%1\n" 1
+
+!
+! replace normal SUBI4 instruction, subu, with hypothetical sub2u
+! in order to test two operand register allocation
+!
+!reg: SUBI4(reg,rc) "subu $%c,$%0,%1\n" 1
+reg: SUBI4(reg,rc) "?move $%c,$%0\nsub2u $%c,%1\n" 1
+


[4] F&H-95, page 419, description of two operand register masking code in <gen.c>
"
" Such templates change the output register before reading
" all input registers, so they violate the rule above.
"
" To handle two operand instructions, we mark their code
" templates with a leading question mark. <snip>
"
" When ralloc sees such a rule, it edits mask to prevent
" reallocation of all input registers but the first
"


[5] <gen.c> add an assert to emitasm() to catch any destination register overwrites

if (*fmt == '?') {
+
+ //
+ // check for two-operand destination overwrite
+ //
+ assert( p->syms[RX] != p->x.kids[1]->syms[RX] );
+


[6] <gen.c> hack rtarget() to always assign a temporary register:

- if (r != q->syms[RX] && !q->syms[RX]->x.wildcard) {
+ //
+ // original code:
+ // if (r != q->syms[RX] && !q->syms[RX]->x.wildcard) {
+ //
+ // temporary debug hack, always allocating temp patches two-operand bug at the cost of temp loads everywhere
+ //
+ if ( 1 ) {
+


[7] complete test program to reproduce problem

//
// <bug_two_operand_md.c>
//
// Reproducer for LCC 4.2 register overwrite bug.
//
// This bug affects two operand machines using register locals.
//
// Two-operand instruction templates generate bad code
// whenever when %c == %1 in the tree being matched:
//
// %c = OP(%0,%1)
//
// Assembly snippets below were generated by a modifed lcc4.2 <mips.md>
// having ADDI4 and SUBI4 changed to use two-operand templates:
//
// reg: ADDI4(reg,rc) "?move $%c,$%0\nadd2u $%c,%1\n" 1
//
// reg: SUBI4(reg,rc) "?move $%c,$%0\nsub2u $%c,%1\n" 1
//
main()
{
register int i = 1;
register int j = 2;
register int k = 4;
//
// Register allocator assigns i to $30, j to $23, k to $22 :
//
// la $30,1
// la $23,2
// la $22,4
//


i = i + j; // emitted code OK
//
// destination and first operand match, so "?move %c,%0" is not emitted:
//
// add2u $30,$23
//


i = k + j; // emitted code OK
//
// overwrite of %c by move is harmless here because old value of i is not used:
//
// move $30,$22
// add2u $30,$23
//


i = j + i; // emitted code fails
//
// %1, aka destination, is overwritten by move before add :
//
// move $30,$23
// add2u $30,$30
//


i = j - i; // emitted code fails
//
// %1, aka destination, is overwritten by move before subtract :
//
// move $30,$23
// sub2u $30,$30
//


return(0);
}

[brim...@aol.com]

Following up to my earlier post about register overwrites
in two-operand lcc 4.2 targets, here are some additional
notes on what I've tried so far.

If anyone out there has a known good lcc 4.2 build that
they can use to try out the two-operand MIPS target test
code, I would welcome any feedback.

----------------------------

Prior to making the <mips.md> edits for the two-operand
test described in my last post, I verified that the
cross compiler with an unmodified MIPS target passed
the .s and .2 output file test suite comparisons run by:

nmake -f makefile.nt TARGET=mips\irix test

----------------------------

I originally was building lcc as a native application
on XP using Visual Studio 2005 and <makefile.nt>, with
slight edits[1] to avoid link errors.

In order to reduce the chances of this being a compiler
build problem, I have also built lcc 4.2 with both a native
MinGW gcc, and under CygWin. ( Linux & OSX up next )

Both these compiler builds emitted code having the same
register overwrite problem.

----------------------------
A correction to the two-operand-overwrite assert in my
first post (need to check for a null pointer, otherwise
assert crashes for non-trivial input source code)

if (*fmt == '?') {

//

// check for two-operand destination overwrite

//
- assert( p->syms[RX] != p->x.kids[1]->syms[RX] );
+ assert( !(p->x.kids[1]) || ( p->syms[RX] != p->x.kids[1]->syms[RX] ) );


-Brian


[1] edits to fix lcc link errors with Visual Studio 2005

- compiler/linker flag -MLd no longer supported ( single threaded static library )
replaced with -MTd [ makefile.nt : CFLAGS, LDFLAGS definitions changed ]

- name clash between microsoft library function and lcc static 'outp'
renamed static to 'outptr' [ cpp.h, cpp.c, include.c, macro.c ]

The resulting compiler will run as a cross compiler to
emit assembly source files, but won't create x86 executables
( lcc can't digest the VS 2005 library header files )

[Jun Woong]

Brian Davis <brimda...@aol.com> wrote:
[problem description snipped]

> --------------------------
> Temporary debug patch
>
>  Hacking[6] <gen.c>'s rtarget() to always insert a temp
> register load dodges the problem at the cost of extra
> register moves everywhere:
>
> code for i = j + i with rtarget hack:
> :
> : move $24,$30
> : add2u $24,$23
> : move $30,$24
> :
>
>  I'm not sure that rtarget() is actually the best place in
> the compiler to attempt a real patch for the problem.
>

I think two approaches are possible in the back-end:
- add LOADs even if nodes have wildcards in RX while targeting and
tear unnecessary LOADs off nodes after reducing, or
- add LOADs only when nodes possibly overwrite their operands after
reducing.

(We would have a cleaner solution if instruction templates were
visible at rtarget() or if register allocation for register
variables were deferred.)

I thought the second one was simpler to implement and the result is:

A new function that is to be invoked after reduce() in rewrite():

static void addload(p) Node p; {
Node q;
int i, rulenum;

for (i = 0; i < NELEMS(p->kids); i++) {
q = p->kids[i];
if (q) {
if (p->x.inst && q->x.inst) {
rulenum = getrule(q, q->x.inst);
if (IR->x._templates[rulenum][0] == '?') {
Symbol s = q->syms[RX];
assert(s);
if (s->x.regnode && s->x.regnode->vbl) {
q->syms[RX] = NULL;
rtarget(p, i, s);
setreg(q, rmap[optype(q->op)]);
(*IR->x._label)(p);
reduce(p, p->x.inst);
}
}
}
addload(q);
}
}
}

This adds intervening LOADs to nodes when their instruction template
starts with '?' and their RX is targeted to a register variable. It
should be an overkill because there are cases where it is safe to
overwrite register variables, but not easy (and not worthwhile) to
identify them since the lifetime of those variables spans a function
(that is, not limited within a forest).

To ensure insertion of LOADs by rtarget() above, I also had to revise
rtarget():

// assert(q->syms[RX]);
if (r != q->syms[RX] && (!q->syms[RX] || !q->syms[RX]->x.wildcard)) {

(I'm working on based on lcc3 not 4, so these modifications were
tested with lcc3, but I think there will be no problem with lcc4.)

>  It seems like swapping operands could avoid the overwrite
> in most cases, especially on a two-operand target having
> a Reverse Subtract instruction.
>
>  But I don't know enough about the lcc DAG/tree processing
> to see where & how to do this properly without accidentally
> introducing a heinous bug for other code sequences.

Considering that lcc is designed to separate the front-end from its
back-ends, swapping operands in the front end to avoid problems
possibly occurred in regster allocation does not seem to be a good
approach.


--
Jun, Woong (woong.jun at gmail.com)
http://code.woong.org

[Brian Davis]

Jun Woong wrote:
>
> - add LOADs only when nodes possibly overwrite their
> operands after reducing.
>

Many thanks for taking the time to put together an
alternative patch to my sledgehammer hack of rtarget()

This addload() patch seems to fix the problem, at least for
the tests I've run so far.

For the example code I posted earlier, the extra register
loads grow the function body from 11 to 16 instructions.
( see code snippets [1] below )

>
> (I'm working on based on lcc3 not 4, so these modifications were
> tested with lcc3, but I think there will be no problem with lcc4.)
>

rmap has changed to a function call in lcc 4.2 :

- setreg(q, rmap[optype(q->op)]);
+ setreg(q, (*IR->x.rmap)(optype(q->op)) );

Other than that, your patch seems fine with 4.2

It is also useful to know that this problem also occurs in 3.x

>
>> It seems like swapping operands could avoid the overwrite
>> in most cases, especially on a two-operand target having
>> a Reverse Subtract instruction.
>
>> But I don't know enough about the lcc DAG/tree processing
>> to see where & how to do this properly without accidentally
>> introducing a heinous bug for other code sequences.
>
> Considering that lcc is designed to separate the front-end
> from its back-ends, swapping operands in the front end to
> avoid problems possibly occurred in regster allocation does
> not seem to be a good approach.
>

I wasn't sure when I wrote that exactly where & how to
accomplish such an operand swap.

(Although I've written plenty of embedded C over the years,
I know very little about compiler internals.)

>
> (We would have a cleaner solution if instruction templates
> were visible at rtarget() or if register allocation for
> register variables were deferred.)
>

Thinking about this again six months later in light of your
explanation, perhaps if I mark the instruction templates as
commutative, by replacing "?" with a variant character such
as "@" , the operand swap could then be done at the assembly
level in emit() when all is known.

So a commutative two-operand ADD template would look like this:

reg : ADDI4(reg,rca5) "@ mov %c,%0\n add %c,%1\n"

And given %c = %0 + %1 , with %c == %1
%c = r11
%0 = r10
%1 = r11

instead of emitting this sequence which overwrites r11:

mov r11,r10
add r11,r11

emit() would instead skip the MOV and swap the %0 and %1
operands for the instruction template :

add r11,r10

Using a prefix variant such as "@" would also serve to prevent
your patch ( looking for "?" ) from inserting the extra load
for the commutative operations that can be fixed up in emit()

-Brian


[1] Code snippets before & after addload() patch

Given the C test code from my earlier post (condensed):

main()
{
register int i = 1;
register int j = 2;
register int k = 4;

i = i + j;

i = k + j;

i = j + i;

i = j - i;

return(0);
}


YARD target, unpatched, 11 instructions, with overwrites

; function body
mov r11,#1 ; reg:cg5
mov r10,#2 ; reg:cg5
mov r9,#4 ; reg:cg5
add r11,r10
mov r11,r9
add r11,r10
mov r11,r10 ;; operand overwrite!!!
add r11,r11
mov r11,r10 ;; operand overwrite!!!
sub r11,r11
mov r0,#0 ; reg:cg5


YARD target, with addload() patch, 16 instructions:

; function body
mov r11,#1 ; reg:cg5
mov r10,#2 ; reg:cg5
mov r9,#4 ; reg:cg5
mov r7,r11
add r7,r10
mov r11,r7
mov r7,r9
add r7,r10
mov r11,r7
mov r7,r10
add r7,r11
mov r11,r7
mov r7,r10
sub r7,r11
mov r11,r7
mov r0,#0 ; reg:cg5


Above generated with my experimental, unfinished yard.md target:
http://code.google.com/p/lcc-homebrew/

[Brian Davis]

Following up to my April 15th post:

>
> perhaps if I mark the instruction templates as commutative,
> by replacing "?" with a variant character such as "@" ,
> the operand swap could then be done at the assembly level
> in emit() when all is known.
>

I have prototyped this approach[1] of swapping in emitasm()

Since most operations are commutative, I instead used '?'
for commutative ops, and "@" for non-commutative, requiring
fewer edits for existing targets using "?".

If a two-operand overwrite is detected, the problematic move
is omitted and the operands are swapped when the instruction
template is emitted.

-------------

My target machine uses mulops_calls for div/mod, which leaves
subtract as the only non-commutative operation to deal with.

I am currently using emit2() to fix up subtracts, by swapping
in a Reverse Subtract as needed for reg-reg subtracts:

reg : SUBI4(reg,reg) "#\n" 1
...
static void emit2(Node p)
...
case SUB+I: case SUB+U:
dst = getregnum( p );
src0 = getregnum( p->x.kids[0] );
src1 = getregnum( p->x.kids[1] );

//
// handle two operand destination/src overlaps
//
if ( dst == src0 )
{
//
// omit mov
//
print(" sub %s,%s\n", ireg[dst]->x.name, ireg[src1]->x.name );
}

else if ( dst == src1 )
{
//
// fixup %c == %1 by switching to Reverse Subtract
//
print(" rsub %s,%s\n", ireg[dst]->x.name, ireg[src0]->x.name );
}

else
{
//
// no overlap, emit mov + sub sequence
//
print(" mov %s,%s\n sub %s,%s\n", ireg[dst]->x.name, ireg[src0]-
>x.name, ireg[dst]->x.name, ireg[src1]->x.name );
}

break;


-------------

I think I could manage this with patterns rather than emit2(),
if I extend the "@" pattern string to three sections:

"@ [move prefix] | [normal pattern] | [swap pattern] "

- [move prefix] would be emitted when !( ( %c == %0 ) || ( %c ==
%1 ) )

- [normal pattern] would be used when ( %c != %1 )

- [swap pattern] would be used when ( %c == %1 )


-Brian


[1] Code snippets before & after emitasm() swap patch

generated with my experimental, unfinished yard.md target:
http://code.google.com/p/lcc-homebrew/

Given the C test code from my earlier post (condensed):

main()
{
register int i = 1;
register int j = 2;
register int k = 4;

i = i + j;

i = k + j;

i = j + i;

i = j - i;

return(0);
}


YARD target, unpatched, 11 instructions, with overwrites

; function body
mov r11,#1 ; reg:cg5
mov r10,#2 ; reg:cg5
mov r9,#4 ; reg:cg5
add r11,r10
mov r11,r9
add r11,r10
mov r11,r10 ;; operand overwrite!!!
add r11,r11
mov r11,r10 ;; operand overwrite!!!
sub r11,r11
mov r0,#0 ; reg:cg5

YARD target, with emitasm() swap patch, 9 instructions:

; function body
mov r11,#1 ; reg:cg5
mov r10,#2 ; reg:cg5
mov r9,#4 ; reg:cg5

add r11,r10
mov r11,r9
add r11,r10

add r11,r10 ;; operand swap: r11 = r10 OP r11
rsub r11,r10 ;; emit2 SUB: r11 = r10 - r11
mov r0,#0 ; reg:cg5