Hi All,
This is my first attempt at an implementation of FFR.
I think this needs some background and explanation
(probably should be a comment at some point)
== AArch64 first faulting read ==
AArch64 first faulting reads are safe to execute speculatively because the
hardware is able to return less than a full vector read.
The loads (both "first faulting" (FF) and "non-faulting" (NF)) set a predicate
register (first fault register) with a mask of loaded elements.
The FF variant will fault only if the first active element to be loaded
causes a fault. This guarantees forwards progress.
The NF variant will never cause a fault, at the expense of possibly
loading no elements.
Architecturally, these loads are guaranteed to never cause a fault unless
it is a FF load and there is a fault for the first element.
However, the hardware can also do partial loads whenever it wants.
For instance this could happen at page boundaries or cache faults.
This means an FFR vectorized loop needs to be able to recover from partial
loads back to vectoried code.
(this seems to not be the case for riscv's equivalent feature).
Also of note, the first fault register starts as all 1's, and each subsequent
load updates it if they fail to load any elements by diabling the bits of
elements not loaded and all bits afterwards.
For instance, it may start as
[1,1,1,1,1,1,1,1]
then a load is executed and could change that to
[1,1,1,1,1,1,0,0]
But then the next load, even if it loads all elements, will not re-enable
the last two bits.
Additionally, you never get a state like
[1,1,1,1,1,0,0,1]
where there are inactive elements followed by an active element.
== Vectorized code structure ==
The use case currently is for loops with mutually misaligned pointers, both
of which require safe speculative reads, where we cannot peel for alignment, or
would not want to incur the code size cost of versioning to check if we can
peel.
For aarch64 this is only for early break as there aren't any other situations
where we need safe speculative reads.
Then for a loop such as
int
foo_no_vect (uint16_t *const restrict src1,
uint16_t *const restrict src2,
unsigned int n)
{
for (int i = 0; i < n; i++)
{
uint16_t v1 = src1[i];
uint16_t v2 = src2[i];
if (v1 + v2 == 0)
return 1;
}
return 0;
}
We generate the following:
GIMPLE (after dce):
_78 = max_mask_75 & _77;
ffr_preservation_82 = .READ_FAULT_STATE ();
.SET_FAULT_STATE ({ -1, ... });
<bb 3> [local count: 1014686025]:
# vectp_src1.7_45 = PHI <vectp_src1.7_46(7), vectp_src1.8_41(13)>
# vectp_src2.11_60 = PHI <vectp_src2.11_61(7), vectp_src2.12_56(13)>
# ivtmp_72 = PHI <ivtmp_73(7), 0(13)>
# loop_mask_48 = PHI <next_mask_ffr_81(7), _78(13)>
vect_v1_14.9_49 = .MASK_FIRSTFAULT_LOAD (vectp_src1.7_45, 64B, loop_mask_48,
{ 0, ... });
vect__5.10_55 = (vector([4,4]) int) vect_v1_14.9_49;
vect_v2_16.13_63 = .MASK_FIRSTFAULT_LOAD (vectp_src2.11_60, 64B,
loop_mask_48, { 0, ... });
vect__6.14_65 = (vector([4,4]) int) vect_v2_16.13_63;
ffr_mask_83 = .READ_FAULT_STATE ();
if (ffr_mask_83 == { -1, ... })
goto <bb 14>; [99.95%]
else
goto <bb 15>; [0.05%]
<bb 15> [local count: 10146860]:
.SET_FAULT_STATE ({ -1, ... });
_84 = ~ffr_mask_83;
ffr_loop_mask_85 = loop_mask_48 & ffr_mask_83;
<bb 14> [local count: 1014686025]:
# ffr_loop_mask_68 = PHI <loop_mask_48(3), ffr_loop_mask_85(15)>
# ffr_num_iters_36 = PHI <POLY_INT_CST [4, 4](3), 0(15)>
# next_mask_ffr_80 = PHI <{ -1, ... }(3), _84(15)>
vect__7.15_66 = vect__5.10_55 + vect__6.14_65;
mask_patt_28.16_67 = vect__7.15_66 == { 0, ... };
vec_mask_and_69 = mask_patt_28.16_67 & ffr_loop_mask_68;
if (vec_mask_and_69 != { 0, ... })
goto <bb 9>; [5.50%]
else
goto <bb 4>; [94.50%]
<bb 9> [local count: 55807731]:
.SET_FAULT_STATE (ffr_preservation_82);
goto <bb 5>; [100.00%]
<bb 4> [local count: 958878295]:
_47 = ffr_num_iters_36 * 2;
vectp_src1.7_46 = vectp_src1.7_45 + _47;
vectp_src2.11_61 = vectp_src2.11_60 + _47;
ivtmp_73 = ivtmp_72 + ffr_num_iters_36;
next_mask_79 = .WHILE_ULT (ivtmp_73, _74, { 0, ... });
next_mask_ffr_81 = next_mask_79 & next_mask_ffr_80;
if (next_mask_ffr_81 != { 0, ... })
goto <bb 7>; [94.50%]
else
goto <bb 12>; [5.50%]
<bb 12> [local count: 52738306]:
.SET_FAULT_STATE (ffr_preservation_82);
goto <bb 5>; [100.00%]
<bb 7> [local count: 906139989]:
goto <bb 3>; [100.00%]
<bb 5> [local count: 114863531]:
# _10 = PHI <1(9), 0(12), 0(2)>
return _10;
Or final assembly:
.L5:
add x4, x4, x3
whilelo p7.s, x4, x2
add x0, x0, x3, lsl 1
and p7.b, p7/z, p14.b, p14.b
add x1, x1, x3, lsl 1
ptest p15, p7.b
b.none .L7
.L6:
ldff1h z31.s, p7/z, [x0]
ldff1h z30.s, p7/z, [x1]
cntw x3
rdffr p14.b
nots p13.b, p15/z, p14.b
b.any .L11
.L4:
add z31.s, z31.s, z30.s
cmpeq p7.s, p7/z, z31.s, #0
b.none .L5
mov w0, 1
ret
== Notes ==
- When there is a "partial read", instead of treating that as a partial
iteration
and advancing by the number of loaded elements, we intead advance by 0
iterations ard repeat the same iteration with the previously processed
elements masked out. This preserves alignment with the starting position
and avoids having to do anything awkward such as possibly rotating
invariant vectors.
- This prioritises the "good" case, by trying to keep
the "full read" path as tight as possible, and adding
a fixup branch to handle the case where there is a partial read.
