[Vm-dev] Re: RTL and MIPS

[Eliot Miranda]

Hi Ryan

   replying to the list because this may be of more general interest)

On Thu, Nov 5, 2015 at 6:01 PM, Ryan Macnak <rmacnak at gmail.com> wrote:

> Hi Eliot,
>
> I've been looking into a MIPSEL port of Cog. MIPS is about as simple an
> architecture as one could hope for, and supporting it would bring Cog up to
> par with the architectures supported by Android and Chrome OS (modulo the
> 64-bit support in flight). I've managed to produce a function stack VM with
> only a few extra ifdefs and a stub Alien implementation.
>
> A Cog port looks fairly straightforward, except for the RTL's assumption
> of condition flags. MIPS doesn't have condition flags, which means to
> efficiently translate tests and branches we need to consider the test and
> branch together, instead of independently as Cog is currently setup to do.
> E.g.,
>
> CmpR: a R: b
> JumpZero: target
> =>
> BEQ a, b, target
>
> AddR: a R: b
> JumpOverflow: target
> =>
> MOV t1, b
> ADDU b, a, b
> XOR t2, b, a
> XOR t1, b, t1
> AND t1, t1, t2
> BLTZ t1, target
>
> One way to handle this is to remove compare, test and conditional branches
> from the RTL and add combined instructions like CmpR:R:JumpEqual: and
> AddR:R:JumpOverflow:. Another is to allow concretization to look at the
> preceding or following instruction. What do you think?
>

I think the former is too much work.  I had assumed that the JIT takes
advantage of the separation of comparison/arithmetic from conditional
branch, but when I looked the other day I couldn't find an example.  So in
principle it's a valid approach.

However, I expect that the latter is extremely simple.  The pattern I would
investigate is to do the work in computeMaximumSize, adding support for
accessing the previous instruction.  So e.g. rewrite

computeMaximumSizes
"This pass assigns maximum sizes to all abstract instructions and
eliminates jump fixups.
It hence assigns the maximum address an instruction will occur at which
allows the next
pass to conservatively size jumps."
<inline: false>
<var: #abstractInstruction type: #'AbstractInstruction *'>
| relativeAddress |
literalsManager dumpLiterals: false.
relativeAddress := 0.
0 to: opcodeIndex - 1 do:
[:i| | abstractInstruction |
abstractInstruction := self abstractInstructionAt: i.
abstractInstruction
address: relativeAddress;
maxSize: abstractInstruction computeMaximumSize.
relativeAddress := relativeAddress + abstractInstruction maxSize]

to

computeMaximumSizes
"This pass assigns maximum sizes to all abstract instructions and
eliminates jump fixups.
It hence assigns the maximum address an instruction will occur at which
allows the next
pass to conservatively size jumps."
<inline: false>
<var: #abstractInstruction type: #'AbstractInstruction *'>
| relativeAddress |
literalsManager dumpLiterals: false.
relativeAddress := 0.
0 to: opcodeIndex - 1 do:
[:i| | abstractInstruction |
abstractInstruction := self abstractInstructionAt: i.
abstractInstruction
address: relativeAddress;
>> maxSize: (abstractInstruction computeMaximumSizeAt: i).
relativeAddress := relativeAddress + abstractInstruction maxSize]

and have the CogMIPSELCompiler's computeMaximumSIzeAt: search back for the
associated compare instruction, absorb it into the current (and possibly
following branch), and collapse the comparison to a label.  There are
sequences like this in 32-bit Spur's genInnerPrimitiveAtPut: that require
absorbing the comparison into more than one conditional:

cogit CmpCq: objectMemory arrayFormat R: formatReg.
jumpNotIndexablePointers := cogit JumpBelow: 0.
jumpHasFixedFields := cogit JumpNonZero: 0.

> Also, how do branch offsets get fixed if the actual size of an RTL
> instruction is smaller than what is answered by computeMaximumSize?
>

The idea is that branch distances are computed when the maximum sizes are
known, and that if a branch is long when jumping across the maximum
distance it must remain so when later generated, even if intervening
instructions are small enough to render the distance small.  So...

Branch offsets are fixed by the following algorithm in
Cogit>>computeMaximumSizes (1.), Cogit>>generateInstructionsAt: (2. 3.) &
CogAbstractInstruction>>#sizePCDependentInstructionAt: (2.).

1. Make a pass over the sequence of instructions assigning their maximum
size.  This will be the same as the actual size for all non-pc-dependent
instructions. Assign addresses to instructions based on this maximum size
2. Make a pass over the sequence of instructions computing actual sizes of
pc-dependent instructions (jumps, pc-relative data references) based on
these max sizes.  If a branch distance is small  jumping across maximum
sizes it will remain small when jumping across actual sizes.
3. Make a final pass that generates machine code (to the memory inside each
instruction) that computes actual size.  For the pc-dependent instructions,
if they needed large offsets in pass 2 they use large offsets even if only
a small offset is needed jumping over actual sizes.  This keeps the offset
computation stable and hence these three passes are sufficient.

_,,,^..^,,,_
best, Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20151114/111c96f3/attachment.htm