Differential D19426
[AArch64] Use the reciprocal estimation machinery Authored by evandro on Apr 22 2016, 11:52 AM.
Details This patch adds support for estimating the square root, its reciprocal and division or reciprocal using the combiner generic reciprocal machinery. I intend to follow this patch with support for using the respective step instructions. Later, with support to consider the context, specifically whether it's bound by latency or throughput and whether the additional multiplications of the series overwhelm execution units already under pressure.
Diff Detail
Event TimelineComment Actions Ideally we would enable this everywhere (and not need to add additional features). Do you have any idea what the impact would be on other cores? Cheers, Comment Actions I have an idea on A57, where only sqrt(), but neither sqrtf() or any division, would be beneficial to emit the series instead. Then again, I'm testing the waters by opting to use additional features instead of a sequence of plethora of isCPU(). Perhaps it's time to use features, even of some other kind, so that all such nuances remain in the machine descriptions instead of peppered all over the rest of the source code. Perhaps not.
Comment Actions Thank you.
Comment Actions Hi Evandro, Wouldn't this require some form of -ffast-math flag? I assume precision will be affected somehow. cheers,
Comment Actions Thank you.
Comment Actions Hi,
I don't like the use of features here. They are a very large, indiscriminate hammer for when to enable this optimization. I don't know about Exynos M1, but on many chips the decision of whether to use reciprocals or not is contextual. Often, the iterative SQRT instruction is faster in latency than a reciprocal alternative. Not only because there is less instruction fetch/dispatch/issue overhead but also because the iterative version can exit early in hardware if the NR steps converge quickly. A reciprocal alternative has to have a fixed number of steps which must be enough for the worst case. The reciprocal has the advantage that it is fully pipelined whereas the iterative SQRT might not be. In my experiments, reciprocals are a poor choice for any situations where there are (a) few data items to process, or (b) the sqrt/div is on the critical path. So this sequence would be pessimized by changing to reciprocals: t = 0;
for (...) {
t = t + a[i];
t /= b[i];
}Because the divide is on the critical path and is a loop dependence, the core can never overlap executions of the divide, so changing to reciprocals and extending the critical path would be a lose. However here: for (...) {
a[i] = a[i] / b[i];
}We can vectorize and unroll this. For this, reciprocals could be a *significant* win. Your current implementation doesn't consider any of the situations where reciprocals might be beneficial or not, and it can't (because you've moved the heuristic out of TTI/TLI into Subtarget). Cheers, James Comment Actions James, It seems to me that your objection is not so much against this patch as against the machinery in the DAGCombiner. I understand your points, even adding that the series takes the pressure from the unit(s) that perform division and square root and puts it unto the unit(s) that perform multiplication. I do intend to investigate this issue further, but I think that it's incremental, if not tangential, to what this patch proposes. Finally, I'm interested in understanding better what you think would be more appropriate than using features. Thank you. Comment Actions Hi Evandro,
Perhaps. The important thing is how we decide whether to perform this optimisation or not. A hook function, as we normally use, has the ability to be extended to add more logic. A subtarget feature does not. I wouldn’t like to see optimization decisions being switched on or off by subtarget features. Cheers, James Comment Actions James,
Whether it is to use the series or not in a loop bound by latency, as in the 1st example, and in a loop bound by throughput, as in the 2nd example, or in a sequence with many multiplications is still something that would still depend on the sub-target. For, say, in a sub-target division or square root could take much longer than the series or there are plenty of units capable of multiplications. Hopefully the context of this hook may allow querying the sub-target about such details. I'll start working on this soon. Still, methinks that this patch is good for some sub-targets as is and it shouldn't be the enemy of "perfection". ;-) Thank you. Comment Actions Hi Evandro, This looks much nicer, thanks! Just a couple of readability issues left from my side. Cheers, James
Comment Actions In the meantime, I've been considering how to issue the iterations using FRSQRTS and FRECPS and it a possible way would be to have new SDNode for them, used directly by the DAGCombiner, which is by default lowered as a polynomial or, as for ARM, as the respective instructions. Thoughts? Thank you. Comment Actions It doesn't. AFAIK, ARM is the only target that has an instruction for the series steps. All the other targets that can estimate the initial value, X86, PPC, IA64, MIPS, compute the series steps with polynomials. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
I think it's better to use names something like:
FeatureReciprocalSqrtEstimate
FeatureReciprocalEstimate
They don't directly calculate DIV and SQRT. They calculate aproximate 1/DIV and 1/SQRT.