From 29d05c005fa88b3a59697a2e538f46cf79413548 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Thu, 27 Jun 2019 21:52:10 +0000 Subject: [CodeGen] [SelectionDAG] More efficient code for X % C == 0 (UREM case) (try 3) Summary: I'm submitting a new revision since i don't understand how to reclaim/reopen/take over the existing one, D50222. There is no such action in "Add Action" menu... This implements an optimization described in Hacker's Delight 10-17: when `C` is constant, the result of `X % C == 0` can be computed more cheaply without actually calculating the remainder. The motivation is discussed here: https://bugs.llvm.org/show_bug.cgi?id=35479. This is a recommit, the original commit rL364563 was reverted in rL364568 because test-suite detected miscompile - the new comparison constant 'Q' was being computed incorrectly (we divided by `D0` instead of `D`). Original patch D50222 by @hermord (Dmytro Shynkevych) Notes: - In principle, it's possible to also handle the `X % C1 == C2` case, as discussed on bugzilla. This seems to require an extra branch on overflow, so I refrained from implementing this for now. - An explicit check for when the `REM` can be reduced to just its LHS is included: the `X % C` == 0 optimization breaks `test1` in `test/CodeGen/X86/jump_sign.ll` otherwise. I hadn't managed to find a better way to not generate worse output in this case. - The `test/CodeGen/X86/jump_sign.ll` regresses, and is being fixed by a followup patch D63390. Reviewers: RKSimon, craig.topper, spatel, hermord, xbolva00 Reviewed By: RKSimon, xbolva00 Subscribers: dexonsmith, kristina, xbolva00, javed.absar, llvm-commits, hermord Tags: #llvm Differential Revision: https://reviews.llvm.org/D63391 llvm-svn: 364600 --- llvm/lib/Support/APInt.cpp | 2 ++ 1 file changed, 2 insertions(+) (limited to 'llvm/lib/Support/APInt.cpp') diff --git a/llvm/lib/Support/APInt.cpp b/llvm/lib/Support/APInt.cpp index 9c59d93b737..d008055bd45 100644 --- a/llvm/lib/Support/APInt.cpp +++ b/llvm/lib/Support/APInt.cpp @@ -1095,6 +1095,8 @@ APInt APInt::sqrt() const { /// however we simplify it to speed up calculating only the inverse, and take /// advantage of div+rem calculations. We also use some tricks to avoid copying /// (potentially large) APInts around. +/// WARNING: a value of '0' may be returned, +/// signifying that no multiplicative inverse exists! APInt APInt::multiplicativeInverse(const APInt& modulo) const { assert(ult(modulo) && "This APInt must be smaller than the modulo"); -- cgit v1.2.3