ARM64: loop array indexing inefficiencies

public int Test()
{
    int[] arr = new int[10];
    int i = 0;
    while (i < 9)
    {
        if (i >= 2) 
        {
            arr[i] = 1;  // <---- IG04
        }
        i++;
    }
    return 0;
}

The line arr[i] = 1 generates the following code to calculate the address of element to save the value.

...
G_M8556_IG04:
        93407C22          sxtw    x2, x1
        D37EF442          lsl     x2, x2, #2
        91004042          add     x2, x2, #16
        52800023          mov     w3, #1
        B8226803          str     w3, [x0, x2]
...

vs. how x64 generates:

G_M27956_IG04:
       4863CA               movsxd   rcx, edx
       C744881001000000     mov      dword ptr [rax+4*rcx+16], 1

The ARM64 pattern can be optimized to use post-index addressing mode using:

# x1 contains <<base address of arr>>+16
mov w0, 1
str w0, [x1], 4

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

@TamarChristinaArm

@TamarChristinaArm , @BruceForstall

@AndyAyersMS

A case of a simple optimization where a STR or LDR immediately followed by an address variable addition could be transformed to subsume the addition into the STR/LDR instruction was discussed here in the context of the intrinsics.

It looks like what you are suggesting would be a sequence of transformations, loop induction variable strength reduction, where we either wouldn't maintain i separately, or would maintain both i and <array base> + 16 + i * 4 in the loop.

cc @AndyAyersMS

Just verified that gcc seems to do that optimization but clang doesn't.
https://godbolt.org/z/Wp9Xhu

Just verified that gcc seems to do that optimization but clang doesn't.
https://godbolt.org/z/Wp9Xhu

Clang uses a more complicated addressing mode but also equally valid. (your example is missing an -O1).

        str     w8, [x9, x8, lsl #2]
        add     x8, x8, #1              // =1
        cmp     x8, #10                 // =10
        b.ne    .LBB0_1

Of course simpler addressing modes are always preferred :)

Note that we have to be careful with ref/byref creation and reporting. E.g., hoisting <array base> + 16 out of the loop to create a pointer to the array element base would create a byref pointer that needs to be reported. Note the comment in fgMorphArrayIndex:

// Be careful to only create the byref pointer when the full index expression is added to the array reference.
// We don't want to create a partial byref address expression that doesn't include the full index offset:
// a byref must point within the containing object. It is dangerous (especially when optimizations come into
// play) to create a "partial" byref that doesn't point exactly to the correct object; there is risk that
// the partial byref will not point within the object, and thus not get updated correctly during a GC.
// This is mostly a risk in fully-interruptible code regions.

The PR where this comment was introduced: dotnet/coreclr#17524

Right, if we have an address computation where the full computation tree has a mixture of positive and negative adjustments to the address, we need to be careful not to reassociate too broadly; all the intermediate results must be addresses within the bounds of the parent object.

Given that ARM doesn't have base + scaled index + offset addressing mode, it seems like we really need to be able to hoist <object base> [ref] + <array first element offset> [native int] out of a loop as a byref.

I think it worth moving this to 7.0 as I'd expect noticeable perf improvements from it:

I tried to implement it via https://github.com/dotnet/runtime/pull/60085/files and even emitted something similar but it needs more work.

I made some progress on this and re-assigning to myself if you don't mind

@EgorBo

@EgorBo you said that you completed this work. Can you link your PR and close this issue?

Yes, I believe this can be closed via a series of PRs for addressing modes, mainly

[arm64] JIT: Enable CSE/hoisting for "arrayBase + elementOffset" #61293

and follow ups:

Navigation Menu

Repository navigation

ARM64: loop array indexing inefficiencies #34810

6 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

ARM64: loop array indexing inefficiencies #34810

Description

Activity

kunalspathak commented on Apr 10, 2020

BruceForstall commented on Apr 10, 2020

kunalspathak commented on Apr 10, 2020

TamarChristinaArm commented on Apr 14, 2020

BruceForstall commented on Apr 23, 2020

BruceForstall commented on Apr 23, 2020

AndyAyersMS commented on Apr 23, 2020

BruceForstall commented on Apr 23, 2020

6 remaining items

EgorBo commented on Oct 7, 2021

EgorBo commented on Nov 1, 2021

JulieLeeMSFT commented on Feb 23, 2022

EgorBo commented on Feb 24, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions