I don't think my previous mail got through but if it does please disregard it, my suspiscions as to the cause of the problem were incorrect.

While testing my armhf porting work I came across a case where parameters were passed incorrectly to a function with a large number of parameters (14 single, 1 double). Initially I thought this was because of the compilers lack of knowlage of the conflict between double registers and odd numbered single registers. However looking more closely this appears not to be the case. The full assembler is attached and highlights of it are below.

# Register r0 allocated
ldr r0,.Lj14
# Register r0 released
# Register s0 allocated
flds s0,[r0]
# Register s0 released
# Register s20 allocated
fcpys s20,s0
<--snip a load of stuff not involving s20-->
# Register r0 allocated
ldr r0,.Lj54
# Register r0 released
# Register s0 allocated
flds s0,[r0]
# Register s0 released
# Register s20 allocated
fcpys s20,s0
<--snip a load of stuff not involving s20-->
# Register s20 released
# Register s13 allocated
fcpys s13,s20
<--snip a load of stuff not involving s20-->
# Register s20 released
# Register s3 allocated
fcpys s3,s20

Looking at the code it seems that the compiler is loading the constants into temporary registers and then copying them to the final locations for passing them to the parameters. However for some reason it is using S20 to store two different temporary values at the same time. Any idea what could cause this and how to debug it? S20 is NOT used for passing parameters to funtions.

While testing my armhf porting work (which I will send on request, including it in this mail seems to make it too big for the list to accept) I came across a case where parameters were passed incorrectly to a function with a large number of parameters (14 single, 1 double). Initially I thought this was because of the compilers lack of knowlage of the conflict between double registers and odd numbered single registers. However looking more closely this appears not to be the case. The full assembler is attached and highlights of it are below.

# Register r0 allocated
Looking at the code it seems that the compiler is loading the constants ldr r0,.Lj14
# Register r0 released
# Register s0 allocated
flds s0,[r0]
# Register s0 released
# Register s20 allocated
fcpys s20,s0
<--snip a load of stuff not involving s20-->
# Register r0 allocated
ldr r0,.Lj54
# Register r0 released
# Register s0 allocated
flds s0,[r0]
# Register s0 released
# Register s20 allocated
fcpys s20,s0
<--snip a load of stuff not involving s20-->
# Register s20 released
# Register s13 allocated
fcpys s13,s20
<--snip a load of stuff not involving s20-->
# Register s20 released
# Register s3 allocated
fcpys s3,s20

Looking at the code it seems that the compiler is loading the constants into temporary registers and then copying them to the final locations for passing them to the parameters. However for some reason it is using S20 to store two different temporary values at the same time. Any idea what could cause this and how to debug it? S20 is NOT used for passing parameters to funtions.

I have a hunch it may be a spilling related issue but i've no idea where to look to confirm/refute that theory.

Op Sat, 17 Mar 2012, schreef peter green:

This usually has to do with the code generator generating incorrect allocations. The code genator generates code with an infinite amount of imaginary registers and inserts allocations & deallocations. Later the register allocator check which imaginary registers conflict. If they don't conflict it can decide to "coalesce" them into the same imaginary register to reduce register pressure.

Please use the command line option -sr to check the generated code before register allocation. You can likely find the cause in there.

Daniël

Daniël Mantione wrote

Please use the command line option -sr to check the generated code before register allocation.

Done and attatched.

You can likely find the cause in there.

The code with imaginary registers looks correct to me. It seems to load each parameter into a seperate even numbered imaginary register (using odd numbered imaginary registers as temporaries in the process) allocating them as it goes. Then copies them to the locations needed for the function call deallocating them as it goes.

So it seems to me that the problem is in the translation of the form using imaginary registers to the form using real registers. Can you explain (or point me to documentation on) how this form is translated into a form using real registers. In particular what exactly happens when there are not enough real registers free to assign a real register for every imaginary register that is in use at a given time?

My current suspiscion is that something is missing regarding handling of running out of VFP registers and it hasn't been noticed before because noone has tried to do what i'm doing (implementing a calling convention using VFP registers and then stress testing it) but i've no idea where to look in the sourcecode to confirm/refute that idea.

Op Sun, 18 Mar 2012, schreef peter green:

I agree, both imaginary registers are correctly allocated and freed.

So it seems to me that the problem is in the translation of the form using imaginary registers to the form using real registers. Can you explain (or point me to documentation on) how this form is translated into a form using real registers.

The algorithm used is called "iterated register coalescing", an advanced form of graph colouting and was designed by Andrew W. Appel. He describes in detail in his book "Modern Compiler Implementation in C".

Basically the registers are put into "worklists", and then 4 procedures:
* simplify -> takes registers out of the graph that can safely be coloured
* coalesce -> tries to coalesce registers together to reduce pressure
* freeze -> selects registers that have a chance to be coalesced and should therefore not be spilled yet
* spill -> selects a register that should move to memory.

These procedures are called iteratively until the worklists are empty. Then the graph is coloured.

In particular what exactly happens when there are not enough real registers free to assign a real register for every imaginary register that is in use at a given time?

Then a register is spilled, i.e. replace by a location in memory. This may be possible without new registers:

mov ireg30d,ireg29d -> mov ireg30d,[ebp-40]

... but in some cases a help register is needed:

mov ireg30d,[ebp+20] -> mov ireg99d,[ebp+20] mov [ebp-40],ireg99d

Should a new register is needed, register allocation is completely restarted with the new code.

It doesn't look like spilling happens in your example: I don't see moves from/to the stack frame as temporary location.

Perhaps the first thing to check is to add a breakpoint in Tinterferencebitmap.setbitmap.

The "versions" of s20 use superregister 50 and 70, so a setbitmap (50,70) or (70,50) should be called at some point to tell the register allocator both registers are active at the same time and cannot be coalesced.

Daniël

Thanks for the info.

My suspiscion was that the compiler was trying to spill but not actually generating any code to implement the spill.

I added a debug writeln to setbitmap and it does seem to be being called with both 50,70 and 70,50. Full output is at http://pastebin.com/3jd8zNkh

Op Sun, 18 Mar 2012, schreef peter green:

Okay, it is quite unlikely that the register allocator itself ignores such an interference, so you may be rigth it tries to spill but nothing happens.

You can check this by adding a breakpoint in Trgobj.spill_registers and and check the contents of spillednodes, or the value of t in the loop that iterates through it.

If the register is being spilled, Trgobj.spill_register will call Trgobj.instr_spill_register to modify an instruction using the register. This procedure will in turn call the CPU specific procedures Trgcpu.do_spill_read and Trgcpu.do_spill_written to modify the code.

Do_spill_read and do_spill_written are the routines to check if they contain the right support for mregisters (I don't see any specific code there at the moment).

Daniël

The algorithm used is called "iterated register coalescing", an advanced form of graph colouting and was designed by Andrew W. Appel. He describes in detail in his book "Modern Compiler Implementation in C".

Thanks, I think i'll grab a copy from the uni library tomorrow.

Basically the registers are put into "worklists"

How does it decice which worklist to put a register in? do registers move between the worklists?

Is this process run seperately for each type of register (int/float/mm)?

P.S. I tried putting debug writelns in the code that generates spills and it doesn't seem to be being called for my current testcase :/ (this wasn't the only testcase that failed but I feel it's best to approach them one at a time).

Ok that wasn't the issue but you were right about not being the register allocator.

Turns out the actual cause was a one character typo in armreg.dat (no I didn't introduce it).

S30,$04,$06,$0F,s20,0,0

Should be

S30,$04,$06,$0F,s20,0,0

So it was assigning two different registers as it should but when it came to actually write out the assembler file it wrote out s20 for both of them.

The good news is that all test cases involving up to 15 parameters (including the "14 singles one double" case I was discussing) are now fixed :)
The bad news is that a number of testcases are still failing. Next on my list is 16 singles.

Doh seems I pasted the wrong line twice, it really should be

S30,$04,$06,$0F,s30,0,0

Please don't change it in trunk at the moment through because my armhf porting work makes a lot of other changes to armreg.dat and I doubt this bug is hitting anyone else at the moment.

peter green wrote

The bad news is that a number of testcases are still failing. Next on my list is 16 singles.

Ok that was easy, a small logic flaw in my code was preventing a parameter being correctly assigned to the last available single precision register when it should have been. And with that fixed all the parameter combinations I try seem to work.

Now I just have to clean up my patch and submit it :)