summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Support/APInt.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [APInt] Add saturating truncation methodsRoman Lebedev2019-11-081-0/+25
| | | | | | | | | | | | | | | | Summary: The signed one is needed for implementation of `ConstantRange::smul_sat()`, unsigned is for completeness only. Reviewers: nikic, RKSimon, spatel Reviewed By: nikic Subscribers: hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69993
* [NFC][APInt] Fix typos in comments.Miloš Stojanović2019-11-061-3/+3
| | | | Testing git commit access.
* [APInt] Introduce APIntOps::GetMostSignificantDifferentBit()Roman Lebedev2019-10-261-0/+8
| | | | | | | | | | | | | | | | | | Summary: Compare two values, and if they are different, return the position of the most significant bit that is different in the values. Needed for D69387. Reviewers: nikic, spatel, sanjoy, RKSimon Reviewed By: nikic Subscribers: xbolva00, hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69439
* [APInt] Add saturating left-shift opsRoman Lebedev2019-10-251-0/+19
| | | | | | | | | | | | | | | | Summary: There are `*_ov()` functions already, so at least for consistency it may be good to also have saturating variants. These may or may not be needed for `ConstantRange`'s `shlWithNoWrap()` Reviewers: spatel, nikic Reviewed By: nikic Subscribers: hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69398
* [APInt] Add saturating multiply opsRoman Lebedev2019-10-251-0/+21
| | | | | | | | | | | | | | | | Summary: There are `*_ov()` functions already, so at least for consistency it may be good to also have saturating variants. These may or may not be needed for `ConstantRange`'s `mulWithNoWrap()` Reviewers: spatel, nikic Reviewed By: nikic Subscribers: hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69397
* Fix compile-time regression caused by rL371928Daniel Sanders2019-09-181-0/+52
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Also fixup rL371928 for cases that occur on our out-of-tree backend There were still quite a few intermediate APInts and this caused the compile time of MCCodeEmitter for our target to jump from 16s up to ~5m40s. This patch, brings it back down to ~17s by eliminating pretty much all of them using two new APInt functions (extractBitsAsZExtValue(), insertBits() but with a uint64_t). The exact conditions for eliminating them is that the field extracted/inserted must be <=64-bit which is almost always true. Note: The two new APInt API's assume that APInt::WordSize is at least 64-bit because that means they touch at most 2 APInt words. They statically assert that's true. It seems very unlikely that someone is patching it to be smaller so this should be fine. Reviewers: jmolloy Reviewed By: jmolloy Subscribers: hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67686 llvm-svn: 372243
* [C++2a] Add __builtin_bit_cast, used to implement std::bit_castErik Pilkington2019-07-021-0/+53
| | | | | | | | | | | | | | | | | | This commit adds a new builtin, __builtin_bit_cast(T, v), which performs a bit_cast from a value v to a type T. This expression can be evaluated at compile time under specific circumstances. The compile time evaluation currently doesn't support bit-fields, but I'm planning on fixing this in a follow up (some of the logic for figuring this out is in CodeGen). I'm also planning follow-ups for supporting some more esoteric types that the constexpr evaluator supports, as well as extending __builtin_memcpy constexpr evaluation to use the same infrastructure. rdar://44987528 Differential revision: https://reviews.llvm.org/D62825 llvm-svn: 364954
* [APInt] Fix getBitsNeeded for INT_MIN valuesDmitry Venikov2019-06-291-1/+4
| | | | | | | | | | | | | | | | Summary: This patch fixes behaviour of APInt::getBitsNeeded for INT_MIN 10 bits values. Reviewers: regehr, RKSimon Reviewed By: RKSimon Subscribers: grandinj, dexonsmith, kristina, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63691 llvm-svn: 364710
* [CodeGen] [SelectionDAG] More efficient code for X % C == 0 (UREM case) (try 3)Roman Lebedev2019-06-271-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [APInt] Optimize umul_ovFangrui Song2019-04-191-5/+12
| | | | | | | | | | | | | Change two costly udiv() calls to lshr(1)*RHS + left-shift + plus On one 64-bit umul_ov benchmark, I measured an obvious improvement: 12.8129s -> 3.6257s Note, there may be some value to special case 64-bit (the most common case) with __builtin_umulll_overflow(). Differential Revision: https://reviews.llvm.org/D60669 llvm-svn: 358730
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [APInt] Add methods for saturated add and subSanjay Patel2018-11-201-0/+36
| | | | | | | | | | | | This adds the sadd_sat, uadd_sat, ssub_sat, usub_sat methods for performing saturating additions and subtractions to APInt. Split out from D54237. Patch by: nikic (Nikita Popov) Differential Revision: https://reviews.llvm.org/D54332 llvm-svn: 347324
* ADT: add <bit> header, implement C++20 bit_cast, useJF Bastien2018-09-081-14/+7
| | | | | | | | | | | | | | Summary: I saw a few places that were punning through a union of FP and integer, and that made me sad. Luckily, C++20 adds bit_cast for exactly that purpose. Implement our own version in ADT (without constexpr, leaving us a bit sad), and use it in the few places my grep-fu found silly union punning. This was originally committed as r341728 and reverted in r341730. Reviewers: javed.absar, steven_wu, srhines Subscribers: dexonsmith, llvm-commits Differential Revision: https://reviews.llvm.org/D51693 llvm-svn: 341741
* Revert "ADT: add <bit> header, implement C++20 bit_cast, use"JF Bastien2018-09-071-7/+14
| | | | | | Bots sad. Looks like missing std::is_trivially_copyable. llvm-svn: 341730
* ADT: add <bit> header, implement C++20 bit_cast, useJF Bastien2018-09-071-14/+7
| | | | | | | | | | | | Summary: I saw a few places that were punning through a union of FP and integer, and that made me sad. Luckily, C++20 adds bit_cast for exactly that purpose. Implement our own version in ADT (without constexpr, leaving us a bit sad), and use it in the few places my grep-fu found silly union punning. Reviewers: javed.absar Subscribers: dexonsmith, llvm-commits Differential Revision: https://reviews.llvm.org/D51693 llvm-svn: 341728
* [ADT] Replace APInt::WORD_MAX with APInt::WORDTYPE_MAXSimon Pilgrim2018-08-161-9/+9
| | | | | | | | | | | | The windows SDK defines WORD_MAX, so any poor soul that wants to use LLVM in a project that depends on the windows SDK gets a build error. Given that it actually describes the maximal value of WordType, it actually fits even better than WORD_MAX Patch by: @miscco Differential Revision: https://reviews.llvm.org/D50777 llvm-svn: 339863
* Fix modules build with different technique to suppress Knuth debuggingTim Northover2018-08-061-37/+33
| | | | | | | | | | Currently we use #pragma push_macro(LLVM_DEBUG) to fiddle with the LLVM_DEBUG macro so that we can silence debugging the Knuth division algorithm unless it's actually desired. Unfortunately this is incompatible with enabling modules while building LLVM (via LLVM_ENABLE_MODULES=ON), probably due to a bug being fixed by D33004. llvm-svn: 339009
* Unbreak build after r338758: specify lambda return type explicitlyKrzysztof Parzyszek2018-08-021-1/+1
| | | | llvm-svn: 338760
* [SCEV] Properly solve quadratic equationsKrzysztof Parzyszek2018-08-021-0/+191
| | | | | | Differential Revision: https://reviews.llvm.org/D48283 llvm-svn: 338758
* [APInt] Keep the original bit width in quotient and remainderKrzysztof Parzyszek2018-07-191-16/+17
| | | | | | | | | | | Some trivial cases in udivrem were handled by directly assigning 0 or 1 to APInt objects. This would set the bit width to 1, instead of the bit width of the inputs. A potentially undesirable side effect of that is that with the bit width of 1, 1 equals -1. Differential Revision: https://reviews.llvm.org/D49554 llvm-svn: 337478
* Fix MSVC "not all control paths return a value" warnings. NFCI.Simon Pilgrim2018-06-261-0/+2
| | | | llvm-svn: 335584
* [APInt] Add helpers for rounding u/sdivs.Tim Shen2018-06-251-0/+46
| | | | | | | | | | Reviewers: sanjoy, craig.topper Subscribers: jlebar, hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48498 llvm-svn: 335557
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-35/+37
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Remove @brief commands from doxygen comments, too.Adrian Prantl2018-05-011-11/+11
| | | | | | | | | | | | | | | | | This is a follow-up to r331272. We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\@brief'); do perl -pi -e 's/\@brief //g' $i & done https://reviews.llvm.org/D46290 llvm-svn: 331275
* IWYU for llvm-config.h in llvm, additions.Nico Weber2018-04-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See r331124 for how I made a list of files missing the include. I then ran this Python script: for f in open('filelist.txt'): f = f.strip() fl = open(f).readlines() found = False for i in xrange(len(fl)): p = '#include "llvm/' if not fl[i].startswith(p): continue if fl[i][len(p):] > 'Config': fl.insert(i, '#include "llvm/Config/llvm-config.h"\n') found = True break if not found: print 'not found', f else: open(f, 'w').write(''.join(fl)) and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p` and tried to fix include ordering and whatnot. No intended behavior change. llvm-svn: 331184
* [NFC] fix trivial typos in comments and error messageHiroshi Inoue2018-04-091-1/+1
| | | | | | "is is" -> "is", "are are" -> "are" llvm-svn: 329546
* [ADT] Simplify getMemory. NFCFangrui Song2018-03-231-5/+2
| | | | llvm-svn: 328334
* [APInt] Fix extractBits to correctly handle Result.isSingleWord() case.Tim Shen2018-02-161-1/+2
| | | | | | | | | | | | Summary: extractBits assumes that `!this->isSingleWord() implies !Result.isSingleWord()`, which may not necessarily be true. Handle both cases. Reviewers: RKSimon Subscribers: sanjoy, llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D43363 llvm-svn: 325311
* Recommit r318963 "[APInt] Don't print debug messages from the APInt knuth ↵Craig Topper2017-11-241-0/+10
| | | | | | | | | | | | | | division algorithm by default" The previous commit had the condition in the do/while backwards. Debug builds currently print out low level details of the Knuth division algorithm when -debug is used. This information isn't useful in most cases and just adds noise to the log. This adds a new preprocessor flag to enable the prints in the knuth division code in APInt. Differential Revision: https://reviews.llvm.org/D40404 llvm-svn: 318966
* Revert 318963 "[APInt] Don't print debug messages from the APInt knuth ↵Craig Topper2017-11-241-10/+0
| | | | | | | | division algorithm by default" I seem to have botched the logic when switching to push_macro llvm-svn: 318964
* [APInt] Don't print debug messages from the APInt knuth division algorithm ↵Craig Topper2017-11-241-0/+10
| | | | | | | | | | | | by default Debug builds currently print out low level details of the Knuth division algorithm when -debug is used. This information isn't useful in most cases and just adds noise to the log. This adds a new preprocessor flag to enable the prints in the knuth division code in APInt. Differential Revision: https://reviews.llvm.org/D40404 llvm-svn: 318963
* Reverting r315590; it did not include changes for llvm-tblgen, which is ↵Aaron Ballman2017-10-151-1/+1
| | | | | | | | causing link errors for several people. Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1 llvm-svn: 315854
* [dump] Remove NDEBUG from test to enable dump methods [NFC]Don Hinton2017-10-121-1/+1
| | | | | | | | | | | | | | | Summary: Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP. Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods. Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so it'll be picked up by public headers. Differential Revision: https://reviews.llvm.org/D38406 llvm-svn: 315590
* [APInt] Move the single word cases of countTrailingZeros and ↵Craig Topper2017-06-231-7/+2
| | | | | | countLeadingOnes inline for consistency with countTrailingOnes and countLeadingZeros. NFCI llvm-svn: 306153
* [APInt] Use std::end to avoid mentioning the size of a local buffer repeatedly.Craig Topper2017-05-241-2/+2
| | | | llvm-svn: 303726
* [APInt] Add support for dividing or remainder by a uint64_t or int64_t.Craig Topper2017-05-191-56/+197
| | | | | | | | | | | | | | | | | | | Summary: This patch adds udiv/sdiv/urem/srem/udivrem/sdivrem methods that can divide by a uint64_t. This makes division consistent with all the other arithmetic operations. This modifies the interface of the divide helper method to work on raw arrays instead of APInts. This way we can pass the uint64_t in for the RHS without wrapping it in an APInt. This required moving all the Quotient and Remainder allocation handling up to the callers. For udiv/urem this was as simple as just creating the Quotient/Remainder with the right size when they were declared. For udivrem we have to rely on reallocate not changing the contents of the variable LHS or RHS is aliased with the Quotient or Remainder APInts. We also have to zero the upper bits of Remainder and Quotient that divide doesn't write to if lhsWords/rhsWords is smaller than the width. I've update the toString method to use the new udivrem. Reviewers: hans, dblaikie, RKSimon Reviewed By: RKSimon Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33310 llvm-svn: 303431
* [APInt] Simplify a for loop initialization based on the fact that 'n' is ↵Craig Topper2017-05-151-1/+1
| | | | | | known to be 1 by an earlier 'if'. llvm-svn: 303120
* [APInt] Use Lo_32/Hi_32/Make_64 in a few more places in the divide code. NFCICraig Topper2017-05-131-6/+6
| | | | llvm-svn: 302983
* [APInt] Fix typo in comment. NFCCraig Topper2017-05-131-1/+1
| | | | llvm-svn: 302974
* [APInt] Add early outs for a division by 1 to udiv/urem/udivremCraig Topper2017-05-121-4/+18
| | | | | | | | We already counted the number of bits in the RHS so its pretty cheap to just check if the RHS is 1. Differential Revision: https://reviews.llvm.org/D33154 llvm-svn: 302953
* [APInt] In udivrem, remember the bit width in a local variable so we don't ↵Craig Topper2017-05-121-4/+5
| | | | | | | | reread it from the LHS which might be aliased with Quotient or Remainder. This helped the compiler generate better code for the single word case. It was able to remember that the bit width was still a single word when it created the Remainder APInt and not create code for it possibly being multiword. llvm-svn: 302952
* [APInt] Add an assert to check for divide by zero in udivrem. NFCCraig Topper2017-05-121-0/+1
| | | | | | udiv and urem already had the same assert. llvm-svn: 302931
* [APInt] Remove unnecessary checks of rhsWords==1 with lhsWords==1 from udiv ↵Craig Topper2017-05-121-2/+2
| | | | | | | | and udivrem. NFC At this point in the code rhsWords is guaranteed to be non-zero and less than or equal to lhsWords. So if lhsWords is 1, rhsWords must also be 1. urem alread had the check removed so this makes all 3 consistent. llvm-svn: 302930
* [APInt] Fix a case where udivrem might delete and create a new allocation ↵Craig Topper2017-05-121-2/+5
| | | | | | instead of reusing the original. llvm-svn: 302882
* [APInt] Add a utility method to change the bit width and storage size of an ↵Craig Topper2017-05-121-42/+31
| | | | | | | | | | | | | | | | | | | APInt. Summary: This adds a resize method to APInt that manages deleting/allocating storage for an APInt and changes its bit width. Use this to simplify code in copy assignment and divide. The assignment code in particular was overly complicated. Treating every possible case as a separate implementation. I'm also pretty sure the clearUnusedBits code at the end was unnecessary. Since we always copying whole words from the source APInt. All unused bits should be clear in the source. Reviewers: hans, RKSimon Reviewed By: RKSimon Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33073 llvm-svn: 302863
* [APInt] Remove an APInt copy from the return of APInt::multiplicativeInverse.Craig Topper2017-05-111-1/+4
| | | | llvm-svn: 302816
* [APInt] Fix typo in comment. NFCCraig Topper2017-05-111-1/+1
| | | | llvm-svn: 302815
* [APInt] Remove an unneeded extra temporary APInt from toString.Craig Topper2017-05-111-5/+1
| | | | | | Turns out udivrem can write its output to the same location as one of its inputs so the extra temporary isn't needed. llvm-svn: 302772
* [APInt] Use negate() instead of copying an APInt to negate it and then ↵Craig Topper2017-05-111-3/+3
| | | | | | writing back over the original value. llvm-svn: 302770
* [APInt] Add negate helper method to implement twos complement. Use it to ↵Craig Topper2017-05-101-6/+3
| | | | | | shorten code. llvm-svn: 302716
OpenPOWER on IntegriCloud