• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Avoid re-calculating the address of array data for consequent array accesses
2
3## Overview
4
5Since accessing an array element is done via an object and an element index,
6the address of the actual array data has to be infered from the object address.
7
8
9## Rationality
10
11Having multiple access to the same array on a control flow path results in
12in the unnecessary repetitive calculation of the data payload address.
13This means code bloating and possible performance degradation, so, avoiding
14the recalculation would reduce code size and bring some performance
15improvement.
16
17
18## Algorithm
19
20Detect multiple array accesses to an array that belong to one basic block or
21a chain of basic blocks that comprise a single control flow path and are not
22interspersed by instructions that call runtime. Calculate the payload address
23and use it in the form of the `AddI` instruction of the `ptr` type in further
24array acesses instead of object address. Replace the `{Store, Load}Array`
25instructions with the low-level `{Store, Load}` intructions.
26
27Do not process array accesses that are not inside a loop as optimizing
28non-repetetive sequences of instructions will not bring a measurable performance
29difference.
30
31## Examples
32
33Machine code before the transformation:
34
35```
36  # [inst]     7.ref  NewArray 181               v8(r21), v6(r2), v5 -> r21 (v31, v24, v17, v20, v27, v33)        bc: 0x00000002
37  # [inst]    24.i32  StoreArray                 v7(r21), v23(r19), v11p(r19)                                     bc: 0x00000013
38    00ac: add x16, x21, #0x10 // (16)
39    00b0: str w19, [x16, w19, uxtw #2]
40  # [inst]    31.i32  StoreArray                 v7(r21), v30(r23), v44(r24)                                      bc: 0x0000001f
41    00bc: add x16, x21, #0x10 // (16)
42    00c0: str w24, [x16, w23, uxtw #2]
43```
44
45Machine code after the transformation:
46
47```
48  # [inst]     7.ref  NewArray 181               v8(r21), v6(r2), v5 -> r21 (v47, v17, v20, v27, v33)             bc: 0x00000002
49  # [inst]    47.ptr  AddI                       v7(r21), 0x10 -> r25 (v49, v48)                                  bc: 0x00000002
50    00ac: add w25, w21, #0x10 // (16)
51  # [inst]    48.i32  Store 8                    v47(r25), v23(r19), v11p(r19)
52    00b0: str w19, [x25, w19, uxtw #2]
53  # [inst]    49.i32  Store 8                    v47(r25), v30(r23), v44(r24)
54    00bc: str w24, [x25, w23, uxtw #2]
55```
56