Differential D111530
[TargetLowering] Optimize expanded SRL/SHL fed into SETCC ne/eq 0 Authored by fzhinkin on Oct 11 2021, 3:12 AM.
Details
During legalization SHL/SRL nodes could be expanded into expression Bug report: https://llvm.org/PR50197
Diff Detail
Event Timeline
Comment Actions Fixed typos, cleaned up the code.
Comment Actions please can you pre-commit these new tests to trunk with current codegen and then rebase to show the diff?
Comment Actions I don't have a permission to commit changes, so I'll appreciate if you can help me with it. Here's the patch adding new tests with checks generated for current trunk: Comment Actions Thank you! Rebase done. Also, thanks for adding i686 to X86's test, it revealed that my optimization does not work when we're legalizing i128 to i32. I'll check if that case could be easily supported. Comment Actions Handling of trees generated during legalization of i128/i256/etc to i32 is relatively simple, but in case of i686 some of these expressions are folded into funnel shifts before SimplifySetCC is applied to setcc.
Personally I'm leaning towards second option as it should be less fragile and easier to maintain. Comment Actions Makes sense to try (2) first - although I expect at least partial support for (1) might end up being required - you are handling a pattern that is almost a funnel shift much of the time. Comment Actions Unfortunately (2) doesn't work well, because nodes created during shift expansion may have several uses until type legalization finished, so I gave it up. Instead I supported funnel shifts TargetLowering::optimizeSetCCOfExpandedShift (did not support rotations and bit/byte swaps because such nodes should not be created during expanded shift's combining). While optimization works fine for i686 now there is an issue with AArch64: shifts expanded from types wider than i128 won't be optimized (see @opt_setcc_shl_ne_zero_i256) because for AArch64 funnel shift alike patterns combined into AArch64ISD::EXTR instead of FSHL/FSHR. I attempted to fix it by implementing (2), but the solution was fragile and didn't work in some cases. Comment Actions X86 changes look good. Are AArch64 changes actually a regressions, or are they just changes? Comment Actions Thanks! Comment Actions A change that only triggers for some (common?) cases and causes no regressions is a better step forward Comment Actions I agree. I don't think that i256 and wider types are something frequently you can see in real code.
Comment Actions I didn't step through everything here, so I may not be seeing the entire problem. There are 2 or more relatively simple folds that are missing both in IR and DAG, and adding those might solve this more generally and more easily than the proposed patch. Here are examples in Alive2: So it might be possible to solve the motivating bug without starting from icmp/setcc -- it's really a problem of combining shifts and funnel shifts in a way that is better for analysis/codegen. We can show a potential codegen improvement for x86 with a minimal example: % cat fsh.ll
declare i32 @llvm.fshl.i32 (i32, i32, i32)
declare i32 @llvm.fshr.i32 (i32, i32, i32)
define i32 @src(i32 %x, i32 %y) {
%y5 = shl i32 %y, 5
%fun3 = call i32 @llvm.fshr.i32(i32 %x, i32 %y, i32 27)
%or2 = or i32 %fun3, %y5
ret i32 %or2
}
define i32 @tgt(i32 %x, i32 %y) {
%x5 = shl i32 %x, 5
%rot3 = call i32 @llvm.fshl.i32(i32 %y, i32 %y, i32 5)
%or2 = or i32 %rot3, %x5
ret i32 %or2
}% llc -o - fsh.ll _src: shldl $5, %esi, %edi ; avoid shld if possible because it is slow on some targets movl %esi, %eax shll $5, %eax orl %edi, %eax ret _tgt: movl %esi, %eax shll $5, %edi roll $5, %eax orl %edi, %eax retq Comment Actions If I'm seeing the patterns correctly, there's at least one more possibility. Comment Actions Transformation from this change is not only about shifts recombination but (and mostly) about removal of shifts that will rotate bits of a value compared with zero. In that particular case such shifts could be safely eliminated, but in any other case it's not possible as it will change the result. By combining shifts differently (by replacing shift + funnel shift with rotate + shift, for example) we can improve performance on some platforms, but the case with icmp eq/ne 0 would still have to be handled separately as it allow transformation that is illegal otherwise. Comment Actions On the other hand it's just a special case where we're using "identify" instead of rotation. I agree that a general solution for shifts combining could be developed and used instead of the transformation from this change. Comment Actions @spatel I remembered why I didn't add a transformation into DAGCombiner and decided to perform specific transformation in TargetLowering::SimplifySetCC:
As a generalization I was thinking to extract rotation-matching part of this optimization to a separate method that will actually combine shifts into rotations, call if from both TargetLowering::SimplifySetCC and DAGCombiner::MatchRotate and then eliminate rotations in TargetLowering::SimplifySetCC. Comment Actions I'm not convinced yet that we need to include the setcc to handle the motivating bug. I noticed that we're missing an even more basic logic+shift transform (we miss this in IR too): I think that transform should work with any shift opcode and any bitwise logic opcode (as long as they are matching opcodes within any one transform). Would this patch still get the optimal result for the transformed code? Comment Actions Now that we're reducing the pattern more with: We still need 1-2 other patches to fix the motivating example, but I think we can get there with some small peepholes. Comment Actions @spatel fixed almost all cases (huge thanks for that), so this patch is no longer relevant. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
clang-format: please reformat the code