-
Notifications
You must be signed in to change notification settings - Fork 12.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Sub-optimal optimization of abs(x) % n #49107
Comments
I think I was mistaken when I speculated about a problem with ignoring poison values from the absolute value calculation. It may be as simple as not optimizing abs(x) & 1 -> x & 1 and abs(x & 1) -> x & 1. |
This should help the examples with "abs": The examples with "srem" are trickier. Clearly, we are missing these basic transforms in IR: But we would have to bend our normal value usage rules to get those most basic folds to fire on the example with 2 uses of the srem result. That might be easier to justify as a backend (codegen) optimization. |
Here's another missed fold in IR (not sure if there's a way to generalize this any further): |
Here's a potential generalization of the above: ; replace abs-of-srem-by-positive-divisor with urem-of-abs define i5 @tgt(i5 %x, i5 %y) { As with many folds, there's a trade-off that we have to limit the power of the transform based on number of uses the more that we generalize (because we need to create extra instructions to keep the transform valid). If "x % 2" is the special and common case, we might as well just try to get that unless/until it is shown that we need to try harder. |
Committed as: So if I'm seeing it correctly, that leaves just the "is_odd_3" example as sub-optimal. That needs something like what I suggested in comment 2. |
If I'm not mistaken, the abs (srem X, 2) --> and X, 1 transformation can be made more generally as abs (srem X, n) --> urem X, n. The urem X, 2 special case already has a transformation --> and X, 1. |
The abs (srem X, n) --> urem X, n transformation makes most sense to me though I understand your point regarding limiting the power of the transformation. I don't have any examples right off-hand that would benefit from this more powerful transform. |
That's almost the same as what I was suggesting in comment 4, but the transform is only valid if we can guarantee that X is positive. This might make it clearer than my earlier example: If you comment out the 'assume' line, the transform doesn't hold. |
Extended Description
LLVM does not find all optimizations related to taking the remainder of the
absolute value of a signed number.
The following equivilent expressions result in sub-optimal code generation:
x % 2 == 1 || x % 2 == -1
std::abs(x % 2) == 1
std::abs(x) % 2 == 1
LLVM may be ignoring poison values for std::abs / @llvm.abs.* in making
optimizations for the remainder operation. Alternatively, LLVM may not be taking
the absolute value into account when performing algebraic operations on the
remainder instructions.
If x is guaranteed to be positive (e.g. it is unsigned or an induction variable),
LLVM does produce expected codegen. When std::abs is present, LLVM should be able
to take advantage of the remainder operation being odd (i.e. -x % n = -(x % n)).
The expected codegen is that of x % 2 != 0, x & 1, where LLVM generates a single
and instruction.
Godbolt comparison of these expressions: https://godbolt.org/z/1YPW1z4v7
The text was updated successfully, but these errors were encountered: