Optimize movz/movk on ARM64

Since ARM64 has an ISA with fixed 32-bit instruction width, the move instructions have space for 16-bit unsigned immediate. To move bigger immediate value, we need to move the value in multiple steps using chunks of 16-bits (movz/movk). Due to this, multiple mov instructions are generated to load a single bigger value in register in contrast to x64 where a single mov can load bigger immediate.

I wanted to see if it has been already evaluated or if it is feasible to store such immediate values in a literal pool and load the values from the pool using ldr instead of moving using multi-step movz/movk. I know this would involve accessing memory instead and might end up being slower. In fact, the examples I have tried on clang/gcc, they use movz/movk mostly.

I have also noticed cases where we try to move 2 immediates back to back that are just bytes apart from each other. E.g. Below is the code generated for Vector4.Add(Vector4, Vector4) method where it tries to load the parameters before performing fadd.

        D29D9900          movz    x0, #0xecc8
        F2A785E0          movk    x0, #0x3c2f LSL #16
        F2C051C0          movk    x0, #654 LSL #32
        F9400000          ldr     x0, [x0]            # <==== loads from address 0x6543c2fecc8
        FD400410          ldr     d16, [x0,#8]
        D29D9800          movz    x0, #0xecc0
        F2A785E0          movk    x0, #0x3c2f LSL #16
        F2C051C0          movk    x0, #654 LSL #32    # <==== loads from address 0x6543c2fecc0
        F9400000          ldr     x0, [x0]
        FD400411          ldr     d17, [x0,#8]
        0E31D610          fadd    v16.2s, v16.2s, v17.2s

The 2nd set of move instructions can be optimized by doing sub x0, x0, 8.

Just to get the stats to see how often we need to generate higher immediate values, I ran crossgen tool on all (or most) of the libraries and dumped the assembly code produced from it for ARM64. Then I extracted out the methods and the portion of code that uses movz/movk pair to load the immediates. There were total 191028 methods crossgened out of which 4578 methods contained pair of movz/movk. In all there were 11856 groups of movz/movk instructions.
You can see the summary in movs.txt.

Some of the questions I am thinking about on seeing the above results:

Some of the Utf8Parser methods loads constant multiple times and can it be optimized to reuse the value?
Is it possible to re-evaluate constant propagation for certain scenarios where the value of constant is big and since it gets propagated, we end up creating these mov sequence multiple times?
Should we tweak our inline heuristics because of the amount of code generated for ARM64 is more than that for Intel?
Can we eliminate some of the movz/movk by doing arithmetic manipulation, the way I mentioned in above example?
And finally, is it beneficial to use literal pool table for certain scenarios?

References:

category:cq
theme:optimization
skill-level:intermediate
cost:medium

I couldn't figure out the best area label to add to this issue. Please help me learn by adding exactly one area label.

@TamarChristinaArm

@TamarChristinaArm , @BruceForstall , @sdmaclea, @dotnet/jit-contrib

Hmm I wouldn't add yet another indirection here with the literal pool. I'm assuming that the address it's building is the address of the managed heap?

        D29D9900          movz    x0, #0xecc8
        F2A785E0          movk    x0, #0x3c2f LSL #16
        F2C051C0          movk    x0, #654 LSL #32
        F9400000          ldr     x0, [x0]            # <==== loads from address 0x6543c2fecc8
        FD400410          ldr     d16, [x0,#8]

Since it's loading an address into x0 and then load a value based on that address.
So isn't 0x6543c2fecc8 the address of a value in the heap?

The 2nd set of move instructions can be optimized by doing sub x0, x0, 8.

You don't need this if it kept the value live longer. I think this is what you meant with no# 2 in your list right?

The block above could be

        D29D9800          movz    x0, #0xecc0
        F2A785E0          movk    x0, #0x3c2f LSL #16
        F2C051C0          movk    x0, #654 LSL #32    # <==== loads from address 0x6543c2fecc0
        F9400000          ldr     x1, [x0]
        FD400411          ldr     d17, [x1,#8]
        F9400000          ldr     x0, [x0, 8]            # <==== loads from address 0x6543c2fecc8
        FD400410          ldr     d16, [x0,#8]

So essentially you pick an anchor use offsets based on that.

If you know the PC value during assembling you can also use adrp + add.
If Indeed the code above is addressing some kind of heap, and if the heap can be aligned to a 4K boundary then you can do

adrp x0, <pcrel offset to 4K aligned heap>
add x0, x0, <offset into heap>

to replace the three movs. On modern cores the latencies would be the same though, but might be easier to share x0 this way if you can't do it via the addressing mode.

The literal pool contaminates the DCache with data from the instructions.
Literal pools are often not packed well so the cache will not be used efficiently
The literal pool stresses the Load/Store side of the processor. So it would perform worse in Load/Store bound situations
The mov/movk are nearly free from an execution standpoint. They can be executed early in the processor and will rarely block other instructions.
However as you note mov/movk are denser. They contaminate the ICache. In an ICache bound app, your approach could be beneficial.

So in general I would suspect moving mov/movk to literal pool would reduce performance.

If you know the PC value during assembling

We would know the PC during live JIT, but not during crossgen. We need relocatable code. The loader could fix up these non-relocatable entries but I would doubt it is worth it.

I thought I had added movn to the mov/movk mix. It helped a bit with code density with negative constants.

We would know the PC during live JIT, but not during crossgen. We need relocatable code. The loader could fix up these non-relocatable entries but I would doubt it is worth it.

Is there no support for relocations?

The register allocator attempts to reuse constants within a BasicBlock but it has no notion of reusing a partial constant - i.e. if we have the same high bits in one constant as another, we could in theory avoid redefining those high bits, but that would require a different kind of analysis, and some way to communicate the partial-reuse state of these constants.

Is there no support for relocations?

There is some support. I am not sure how extensive it is. It would require relocation table entries which would bloat/complicate the code and slow loading. The relocation table would require making the loaded code writable, not share with other processes, and run relocation code. It could be expensive from a memory usage perspective.

That was why I guessed it would work better for live JIT in later optimization tiers.

You mentioned constants using PC relative constants to reach the heap. It seems like that would be a new relocation feature....

The CSE phase currently doesn't try to CSE identical large constants, or constants that are within a short distance to each other. It is something that I want to look into.

@briansull

@briansull - Once we do this, will it optimize these patterns? Here it loads the same MethodTable address twice to create different array size.

        D2888000          movz    x0, #0x4400
        F2B64920          movk    x0, #0xb249 LSL #16
        F2CFFEE0          movk    x0, #0x7ff7 LSL #32
        D2800121          mov     x1, #9
        97E5B98F          bl      CORINFO_HELP_NEWARR_1_VC
        AA0003F3          mov     x19, x0
        D2888000          movz    x0, #0x4400
        F2B64920          movk    x0, #0xb249 LSL #16
        F2CFFEE0          movk    x0, #0x7ff7 LSL #32
        D2800221          mov     x1, #17
        97E5B989          bl      CORINFO_HELP_NEWARR_1_VC
        AA0003F4          mov     x20, x0

@kunalspathak

@kunalspathak - that's a case where the register allocator might have reused the constant, except that it's only opportunistic and it doesn't do any analysis ahead of time to figure out that in order to reuse in this case it would need to allocate a callee-save register. I wonder if it might be useful to add some analysis for that (i.e. how often would it help, and what would the additional analysis cost in throughput)?

In the above case I believe that we compute the constant into a scratch register that is killed by the call to the JitHelper, so it doesn't get reused.

With the CSE approach we have heuristics that try to balance the cost of allocating a new local variable, (in a caller saved register) and possibly having to spill and reload an extra register in the prolog and epilog to hold this constant value in a register across a call.
These CSE heuristics just look at a few things and it doesn't do any global analysis. So if the heuristic finds that 80% of the cases that match the current CSE candidate are profitable, it would make a CSE.

In the above case I believe that we compute the constant into a scratch register that is killed by the call to the JitHelper, so it doesn't get reused.

But it sounds like whatever you do with CSE you'd still need this changed right? You don't want it to spill and reload it after the call when it had plenty of free registers available. (In this case also not move it to some non-caller saved registers if it would have allocated to that register to begin with.)

Out of pure curiosity, is most things such as this implemented as a single pass? e.g. can the register allocator tell that there's a function call coming up and which ABI it needs?

Not saying it should for this case. Just wondering what information I can reasonably expect the RA to know.

When we make it into a CSE we assign the constant into a GT_LCl_VAR which the register allocator knows how to handle properly. It will typically correctly pick either a caller cased or scratch register to hold the CSE value, depending upon the liveness requirements.

I will investigate this issue further, so I have assigned this issue to myself.

Out of pure curiosity, is most things such as this implemented as a single pass? e.g. can the register allocator tell that there's a function call coming up and which ABI it needs?

The register allocator, in its build phase, will record which values are live across a call, and will attempt to put them in callee-save registers. Note, though, that we don't have any form of rematerialization (#6264) to allow the constant to be reconstructed if it's spilled, so if it doesn't get a callee-save register it will be spilled and restored from the stack.

Another example taken from Rand

private static s_seed = 7774755;
private static int Rand()
{
    s_seed = (s_seed * 77 + 13218009) % 3687091;
    return s_seed;
}

We generate asm code:

        D2966000          movz    x0, #0xb300
        F2B5E260          movk    x0, #0xaf13 LSL #16
        F2CFFEE0          movk    x0, #0x7ff7 LSL #32
        D2966001          movz    x1, #0xb300           # <--- can be just mov x1, x0
        F2B5E261          movk    x1, #0xaf13 LSL #16
        F2CFFEE1          movk    x1, #0x7ff7 LSL #32
        B9400021          ldr     w1, [x1]
...
...
        4B020021          sub     w1, w1, w2
        B9000001          str     w1, [x0]
        B9400000          ldr     w0, [x0]

You can just read from x0 both times, so you don't need/want a mov there :)

You can just read from x0 both times, so you don't need/want a mov there :)

True. :)

The change #39096 will fix this issue

Fixed with #39096

Navigation Menu

Repository navigation

Optimize movz/movk on ARM64 #34732

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Optimize movz/movk on ARM64 #34732

Description

Activity

Dotnet-GitSync-Bot commented on Apr 9, 2020

kunalspathak commented on Apr 9, 2020

TamarChristinaArm commented on Apr 9, 2020

sdmaclea commented on Apr 9, 2020

sdmaclea commented on Apr 9, 2020

TamarChristinaArm commented on Apr 9, 2020

CarolEidt commented on Apr 9, 2020

sdmaclea commented on Apr 9, 2020

briansull commented on Apr 9, 2020

kunalspathak commented on Apr 10, 2020

CarolEidt commented on Apr 10, 2020

briansull commented on Apr 10, 2020

TamarChristinaArm commented on Apr 14, 2020

briansull commented on Apr 14, 2020

briansull commented on Apr 14, 2020

CarolEidt commented on Apr 14, 2020

kunalspathak commented on Apr 15, 2020

TamarChristinaArm commented on Apr 16, 2020

kunalspathak commented on Apr 16, 2020

briansull commented on Jun 25, 2020

briansull commented on Jul 29, 2020

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions