issue-#41 fixing a register allocation problem
- Josef Templ
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
issue-#41 fixing a register allocation problem
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
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
Re: issue-#41 fixing a register allocation problem
I did this patch on oberoncore, here the source comments :old register selection order: 0, 2, 6, 7, 1, 3
proposed register selection order: 0, 2, 1, 3, 6, 7
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*)
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 order: AX,DX,CX,SI,DI,BXThe '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.
it is safe too.
luowy
- Josef Templ
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
Re: issue-#41 fixing a register allocation problem
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
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
Re: issue-#41 fixing a register allocation problem
the compiler source and the trap view give us:
1,BX is not used by the register allocator,
DevCPC486.Enter
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
this problem can be fixed by hint or force select a byte register @ DevCPC486.Assign
without touching the GetReg procedure., if we are afraid of some side effect.
3,
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
1,BX is not used by the register allocator,
DevCPC486.Enter
Code: Select all
SetReg({AX, CX, DX, SI, DI}); (* allReg := reg; *)
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 !!! *)
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;
...
3,
"run out of byte registers" or word registers is possible when the statement is complexed enough,I think.have you also considered that you may run out of byte registers
if you use AX, BX, CX, DX first?
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
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
Re: issue-#41 fixing a register allocation problem
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.
- Josef
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;
Re: issue-#41 fixing a register allocation problem
good,the explain(clue) is very useful to think over this problem,though I have readed the source sevel timesJosef Templ wrote: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.
but not thought about it.
done, I think so.Josef Templ wrote: 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;
luowy
- Josef Templ
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
Re: issue-#41 fixing a register allocation problem
I have committed this last version to the topic branch.
- Josef
- Josef
- DGDanforth
- Posts: 1061
- Joined: Tue Sep 17, 2013 1:16 am
- Location: Palo Alto, California, USA
- Contact:
Re: issue-#41 fixing a register allocation problem
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.
machine coding (Texas InstrumentsTMS32010/25 chips) and knowing the complexity of thoses
makes me shy far away from such issues.
- Josef Templ
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
Re: issue-#41 fixing a register allocation problem
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
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
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
Re: issue-#41 fixing a register allocation problem
The voting is finished.
I have merged the changes into master.
- Josef
I have merged the changes into master.
- Josef