bool f(unsigned x, unsigned y, unsigned* res) { *res = x * y; return x && ((*res / x) != y); } This can be optimized to `return __builtin_mul_overflow(x, y, res);`. This transformation is done by LLVM, but not by GCC.
Created attachment 49913 [details] gcc11-pr95852-wip.patch Untested WIP patch. This handles the transformation to mullo but doesn't yet optimize away the x != 0 && (which can be done of course only if the x != 0 guarded basic block contains only specific statements we'd need to pattern recognize. Furthermore, signed multiplication can be handled similarly, but it will need even more work because of the casts.
Created attachment 49919 [details] gcc11-pr95852.patch Full untested patch (so far only for unsigned __builtin_mul_overflow{,_p} pattern matching though). Signed will be handled incrementally.
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>: https://gcc.gnu.org/g:a2106317cd6673e110b347c70f21e25fbb23379e commit r11-6579-ga2106317cd6673e110b347c70f21e25fbb23379e Author: Jakub Jelinek <jakub@redhat.com> Date: Mon Jan 11 10:32:07 2021 +0100 widening_mul: Pattern recognize unsigned multiplication with overflow check [PR95852] The following patch pattern recognizes some forms of multiplication followed by overflow check through division by one of the operands compared to the other one, with optional removal of guarding non-zero check for that operand if possible. The patterns are replaced with effectively __builtin_mul_overflow or __builtin_mul_overflow_p. The testcases cover 64 different forms of that. 2021-01-11 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/95852 * tree-ssa-math-opts.c (maybe_optimize_guarding_check): New function. (uaddsub_overflow_check_p): Renamed to ... (arith_overflow_check_p): ... this. Handle also multiplication with overflow check. (match_uaddsub_overflow): Renamed to ... (match_arith_overflow): ... this. Add cfg_changed argument. Handle also multiplication with overflow check. Adjust function comment. (math_opts_dom_walker::after_dom_children): Adjust callers. Call match_arith_overflow also for MULT_EXPR. * gcc.target/i386/pr95852-1.c: New test. * gcc.target/i386/pr95852-2.c: New test.
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>: https://gcc.gnu.org/g:9febe9e4be7812519258ea3ed4f38bbc1a61624b commit r11-6580-g9febe9e4be7812519258ea3ed4f38bbc1a61624b Author: Jakub Jelinek <jakub@redhat.com> Date: Mon Jan 11 10:34:07 2021 +0100 widening_mul: Pattern recognize also signed multiplication with overflow check [PR95852] On top of the previous widening_mul patch, this one recognizes also (non-perfect) signed multiplication with overflow, like: int f5 (int x, int y, int *res) { *res = (unsigned) x * y; return x && (*res / x) != y; } The problem with such checks is that they invoke UB if x is -1 and y is INT_MIN during the division, but perhaps the code knows that those values won't appear. As that case is UB, we can do for that case whatever we want and handling that case as signed overflow is the best option. If x is a constant not equal to -1, then the checks are 100% correct though. Haven't tried to pattern match bullet-proof checks, because I really don't know if users would write it in real-world code like that, perhaps *res = (unsigned) x * y; return x && (x == -1 ? (*res / y) != x : (*res / x) != y); ? https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow suggests to use twice as wide multiplication (perhaps we should handle that too, for both signed and unsigned), or some very large code with 4 different divisions nested in many conditionals, no way one can match all the possible variants thereof. 2021-01-11 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/95852 * tree-ssa-math-opts.c (maybe_optimize_guarding_check): Change mul_stmts parameter type to vec<gimple *> &. Before cond_stmt allow in the bb any of the stmts in that vector, div_stmt and up to 3 cast stmts. (arith_cast_equal_p): New function. (arith_overflow_check_p): Add cast_stmt argument, handle signed multiply overflow checks. (match_arith_overflow): Adjust caller. Handle signed multiply overflow checks. * gcc.target/i386/pr95852-3.c: New test. * gcc.target/i386/pr95852-4.c: New test.
Fixed.