issue-#41 fixing a register allocation problem

[Josef Templ]

This issue is about a compiler problem, which leads to a TRAP
due to the currently used register allocation strategy.

see http://redmine.blackboxframework.org/issues/41.

A proposal for fixing the problem exists in CPC 1.7 rc5.
It changes the global register allocation strategy such that registers
{0..3) are preferred over registers {6, 7} because {6, 7} cannot
be used in comparison operations and the compiler does not generate any code
for register copying.
old register selection order: 0, 2, 6, 7, 1, 3
proposed register selection order: 0, 2, 1, 3, 6, 7

In my opinion, it is not clear if the proposed fix solves the problem without the potential
danger of creating new problems for other code examples.

The old strategy tries to preserve 1 and 3 if possible because any of these can also be split into two byte registers.
The 'intermediate' register selection order: 0, 2, 1, 6, 7, 3 would also solve the problem
with less reordering. But again, it is not clear in which cases this might lead to
new problems.

Careful analysis is needed for this fix!
Ideally, the oberoncore people who proposed the fix should be involved.

I have included the proposed changes in the topic branch issue-#41.
see the diffs in http://redmine.blackboxframework.org/pr ... 87cd02fa38.

- Josef

[luowy]

old register selection order: 0, 2, 6, 7, 1, 3
proposed register selection order: 0, 2, 1, 3, 6, 7

I did this patch on oberoncore, here the source comments :

Code: Select all

			IF 0 IN s THEN n := 0         (*AX*)
			ELSIF 2 IN s THEN n := 2    (*DX*)
		(*
			ELSIF 6 IN s THEN n := 6     (*SI*)
			ELSIF 7 IN s THEN n := 7     (*DI*)
			ELSIF 1 IN s THEN n := 1    (*CX*)
			ELSE n := 3  (*BX*)
		*)
			ELSIF 1 IN s THEN n := 1    (*CX*)
			ELSIF 3 IN s THEN n := 3     (*BX*)
			ELSIF 6 IN s THEN n := 6     (*SI*)
			ELSE  n := 7     (*DI*)

c compiler and asm code more prefer order : AX,DX,CX,BX,SI,DI

for BX has be used as frame register(FP) of the nest(sub)procedure in BB compiler, so it get the last order.
but the compiler will backup the BX on the stack when using it as common register,so the reordering
is safe,no side efffect at all.

The 'intermediate' register selection order: 0, 2, 1, 6, 7, 3 would also solve the problem
with less reordering.But again, it is not clear in which cases this might lead to
new problems.

the order: AX,DX,CX,SI,DI,BX
it is safe too.


luowy

[Josef Templ]

Luowy, have you also considered that you may run out of byte registers
if you use AX, BX, CX, DX first?
My understanding is that the BB1.6 register allocation strategy tries to
balance the usage of 32-bit and byte registers by using CX, DX last.
Since I don't know much about the overall register handling in the
backend, I don't know how to construct such a case (and if there is such a case at all).
But one thing is for sure: if AX, BX, CX, DX are used and a byte register is needed,
the compiler reports an error message. So it is safe, but still a problem.
In addition: if AX, BX, CX, DX are used, then the next register
to be used cannot do a compare instruction, thus, it could TRAP again.

- Josef

[luowy]

the compiler source and the trap view give us:
1,BX is not used by the register allocator,
DevCPC486.Enter

Code: Select all

SetReg({AX, CX, DX, SI, DI});                   (* allReg := reg; *)

that is: only AX,DX,CX,SI,DI are valid

2,the trap is cleared:
the register SI which selected cant used as a byte register,DevCPC486.CheckRange

Code: Select all

ASSERT((x.mode # Reg) OR (max > 255) OR (max = 31) OR (x.reg < 4)); (* trap for x.reg =6 !!!  *)

this problem can be fixed by hint or force select a byte register @ DevCPC486.Assign

Code: Select all

.... 
 IF ~(x.form IN realSet) OR ~(y.form IN intSet) THEN 
    IF x.form IN {Byte, Bool, Char8, Int8} THEN  (* <<add this*)
      Assert(y, {high}, {stk})  (* Assert(y, {}, {stk,high}) *) (* <<add this*)
    ELSE (* <<add this*)
      Assert(y, {}, {stk}) 
    END;(* <<add this *)
  END;
...

without touching the GetReg procedure., if we are afraid of some side effect.

3,

have you also considered that you may run out of byte registers
if you use AX, BX, CX, DX first?

"run out of byte registers" or word registers is possible when the statement is complexed enough,I think.
but the compiler will give a trap error... we need a sample to analysis and fix it....

I dont known which one is better, you can make the jugement.

luowy

[Josef Templ]

The question is really if we can find a code example that uses more than the available registers.
In general, the compiler seems to free unused registers as soon as possible, so it is hard to come up
with such a code and it needs a good understanding of the register handling strategy.

For the left hand side of an assignment there seems to be a maximum of 2 registers needed (Ind, DInd).
So there is always at least one register from {AX, CX, DX} available for the right hand side.

If we go with reordering the register selection, a nice formulation would be the one below.
It uses symbolic names instead of numbers and it moves BX last because it is not used anyway.

Code: Select all

IF AX IN s THEN n := AX
ELSIF DX IN s THEN n := DX
ELSIF CX IN s THEN n := CX
ELSIF SI IN s THEN n := SI
ELSIF DI IN s THEN  n := DI
ELSE n := BX (* not used *)
END;

- Josef

[luowy]

For the left hand side of an assignment there seems to be a maximum of 2 registers needed (Ind, DInd).
So there is always at least one register from {AX, CX, DX} available for the right hand side.

good,the explain(clue) is very useful to think over this problem,though I have readed the source sevel times
but not thought about it.

IF AX IN s THEN n := AX
ELSIF DX IN s THEN n := DX
ELSIF CX IN s THEN n := CX
ELSIF SI IN s THEN n := SI
ELSIF DI IN s THEN n := DI
ELSE n := BX (* not used *)
END;

done, I think so.

luowy

[Josef Templ]

I have committed this last version to the topic branch.

- Josef

[DGDanforth]

For what it is worth, I can not address this issue. Having done only a minimal amount of
machine coding (Texas InstrumentsTMS32010/25 chips) and knowing the complexity of thoses
makes me shy far away from such issues.

[Josef Templ]

With the proposed changes I tried a number of test cases but could not exhaust the registers.
Also, the reordering is used by oberoncore for quite some time now and it is used in the CPC 1.7 edition.
So it seems that it is safe to merge the changes to master.

- Josef

[Josef Templ]

The voting is finished.
I have merged the changes into master.

- Josef