Alfie Richards <[email protected]> writes:
> 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.
Hmm, interesting. I hadn't seen that approach being proposed before.
I think the "classical" idea (is SVE old enough for things to be
classical?) was that we would have two copies of the non-speculative
part of the loop body: a full vector version for when no fault is
detected and an FFR-predicated version for when FFR has zero bits.
The FFR-predicated version would advance by less than a full vector,
which like you say would affect induction vectors. But as Robin says,
my understanding is that the .LEN code already supports that.
(We would still be advancing by a whole number of scalar iterations,
so invariant vectors shouldn't need to change.)
The supposed advantages of that were (IIRC):
(1) The full vector version would be the same as for a non-FFR loop.
That is, the overhead for the "good" case would be even lower
than above.
(2) It would reduce the number of vector iterations.
(3) In practice, a load would only be suppressed starting at index X if
X corresponds to a natural boundary (at least a cache boundary).
Restarting the loop at that point might make future iterations
"more aligned", which might be faster in its own right, but might
also reduce the risk of future false suppressed faults.
Like you say below, it would be better to avoid first-faulting loads
if all pointers are well-aligned. If we do that, (3) would only come
into play for mutually misaligned pointers (or for -O2). But even for
mutually misaligned pointers, it could be better (or no worse) to be
aligned to one pointer than be misaligned to all pointers.
The advantage of your approach is that it would scale well for multiple
groups of FFR loads in the same loop. We don't support that yet AIUI,
but we could in future.
However, if I'm reading the above assembly correctly, it looks like:
next_mask_ffr_81 = next_mask_79 & next_mask_ffr_80;
ends up using the RDFFR result even for the "good" path. Is:
# next_mask_ffr_80 = PHI <{ -1, ... }(3), _84(15)>
getting optimised to _84 based on:
if (ffr_mask_83 == { -1, ... })
? That would be a legitimate optimisation as far as gimple is concerned,
but my understanding is that it would be harmful for performance.
> - We preserve the state of the FFR register over the vectoried loop.
> This is to prevent code written with intrinsics breaking by clobbering
> their value in the FFR register. However, as the FFR is not preserved by
> the AAPCS, this is nearly always optimized out.
Do we also manage to optimise it away if the vectorised loop occurs between
two independent FFR-using intrinsic loops? If so, then yeah, I agree that
this is probably the right approach.
> - One downside of this approach is I dont think it will translate cleanly for
> len based loop vectorization (riscv). However, as I understand it, the
> riscv equivalent feature never does partial loads unless there is a genuine
> fault, so we will not need to worry about recovering back to
> vectorized code after a partial read (as it will either take the early break
> or the fault). So no fixup should be needed and can use a subset of this.
>
> == Remaining work to do ==
>
> - Versioning
> As FFR introduces overhead, it will always be slower than a mutually
> aligned loop. So my ideal code generation for a vector with two pointers
> requiring safe speculative reads is:
>
> At O2, where we do not want to incur the code size cost of versioning,
> instead just use FFR to vectorize the loop (if profitable).
>
> At O3, version to create a mutually aligned non-FFR case and a (current
> code gen)
> if the pointers are mutually misaligned.
>
> This "FFR versioning" is not yet implemented.
>
> - Costing
> I haven't done anything to cost FFR yet, we will want accurate costing of
> FFR
> vs scalar and vs non-FFR vectorized to make the decisions on versioning and
> what to use.
>
> - Optimization of the generated code
> The generated code has room for improvement, primarily using rdffrs would
> be a performance gain, and reducing some of the moves within the hot
> section of the loop.
Yeah. As mentioned privately, I think one option for the RDFFRS thing
would be to add an internal fn such as .FAULT_DETECTED and have ISEL
convert:
if (ffr_mask_83 == { -1, ... })
to:
temp = .FAULT_DETECTED (ffr_mask_83);
if (temp != 0)
when the optab is implemented. .FAULT_DETECTED could then take
advantage of the lack of 0->1 transitions.
Thanks,
Richard
