summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/ADT/APIntTest.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [APInt][PatternMatch] Add 'is non-positive' predicateRoman Lebedev2019-12-031-0/+17
| | | | | It will be useful for implementing the fold mentioned in https://bugs.llvm.org/show_bug.cgi?id=44100#c4
* [APInt] add wrap support for `setBits` and `getBitsSet`czhengsz2019-11-191-0/+34
| | | | | | | | Add two new interfaces getBitsSet and getBitsSetWithWrap Reviewed by: lebedev.ri, craig.topper Differential Revision: https://reviews.llvm.org/D69032
* [APInt] Add saturating truncation methodsRoman Lebedev2019-11-081-0/+17
| | | | | | | | | | | | | | | | 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
* [APInt] Introduce APIntOps::GetMostSignificantDifferentBit()Roman Lebedev2019-10-261-0/+71
| | | | | | | | | | | | | | | | | | 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/+17
| | | | | | | | | | | | | | | | 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/+18
| | | | | | | | | | | | | | | | 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/+85
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix build when both gtest death tests and LLVM_NODISCARD are available.David Blaikie2019-08-051-9/+9
| | | | | | (matching r367495) llvm-svn: 367899
* [APInt] Introduce clearLowBits()Roman Lebedev2019-07-301-0/+65
| | | | | | | | | | | | | | | | Summary: Equivalent to `x & -2^K`. Reviewers: RKSimon, craig.topper Reviewed By: RKSimon, craig.topper Subscribers: dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65369 llvm-svn: 367287
* [APIntTest] multiplicativeInverse(): clarify testRoman Lebedev2019-07-021-4/+7
| | | | | | | Clarify that multiplicative inverse exists for all odd numbers, and does not exist for all even numbers (including 0). llvm-svn: 364920
* [APInt] Fix getBitsNeeded for INT_MIN valuesDmitry Venikov2019-06-291-2/+15
| | | | | | | | | | | | | | | | 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
* Silence gcc warning in testcase [NFC]Mikael Holmen2019-06-281-1/+1
| | | | | | | | | | | Without the fix gcc (7.4.0) complains with ../unittests/ADT/APIntTest.cpp: In member function 'virtual void {anonymous}::APIntTest_MultiplicativeInverseExaustive_Test::TestBody()': ../unittests/ADT/APIntTest.cpp:2510:36: error: comparison between signed and unsigned integer expressions [-Werror=sign-compare] for (unsigned Value = 0; Value < (1 << BitWidth); ++Value) { ~~~~~~^~~~~~~~~~~~~~~~~ llvm-svn: 364624
* [NFC][APInt] Add (exhaustive) test for multiplicativeInverse()Roman Lebedev2019-06-271-0/+17
| | | | | | | Else there is no direct test coverage at all. The function should either return '0' or precise answer. llvm-svn: 364599
* [APInt] Add PR40897 test caseSimon Pilgrim2019-06-011-0/+3
| | | | | | In reality APInt::getBitsNeeded(INT_MIN, base) cases require one less bit than is returned llvm-svn: 362301
* [APInt] Optimize umul_ovFangrui Song2019-04-191-0/+36
| | | | | | | | | | | | | 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/+24
| | | | | | | | | | | | 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
* [Unittests] Fix returning string in SolveQuadraticEquationWrapKrzysztof Parzyszek2018-08-021-3/+3
| | | | | | | Returning a Twine caused runtime failures. Convert it to std::string before retuning. llvm-svn: 338768
* [SCEV] Properly solve quadratic equationsKrzysztof Parzyszek2018-08-021-0/+86
| | | | | | Differential Revision: https://reviews.llvm.org/D48283 llvm-svn: 338758
* [APInt] Keep the original bit width in quotient and remainderKrzysztof Parzyszek2018-07-191-0/+32
| | | | | | | | | | | 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
* [APInt] Add helpers for rounding u/sdivs.Tim Shen2018-06-251-0/+67
| | | | | | | | | | Reviewers: sanjoy, craig.topper Subscribers: jlebar, hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48498 llvm-svn: 335557
* Bring back APInt self-move assignment check for MSVC onlyReid Kleckner2018-04-241-0/+32
| | | | | | | | | | | | | | | | | Summary: It was removed about a year ago in r300477. Bring it back, along with its unittest, when the MSVC STL is in use. The MSVC STL performs self-assignment in std::shuffle. These days, llvm::sort calls std::shuffle when expensive checks are enabled to help find non-determinism bugs. Reviewers: craig.topper, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D46028 llvm-svn: 330776
* [APInt] Fix extractBits to correctly handle Result.isSingleWord() case.Tim Shen2018-02-161-0/+7
| | | | | | | | | | | | 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
* [APInt] Add support for dividing or remainder by a uint64_t or int64_t.Craig Topper2017-05-191-0/+58
| | | | | | | | | | | | | | | | | | | 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] Add support for multiplying by a uint64_t.Craig Topper2017-05-081-0/+19
| | | | | | This makes multiply similar to add, sub, xor, and, and or. llvm-svn: 302402
* [APInt] Remove support for wrapping from APInt::setBits.Craig Topper2017-04-301-15/+15
| | | | | | | | This features isn't used anywhere in tree. It's existence seems to be preventing selfhost builds from inlining any of the setBits methods including setLowBits, setHighBits, and setBitsFrom. This is because the code makes the method recursive. If anyone needs this feature in the future we could consider adding a setBitsWithWrap method. This way only the calls that need it would pay for it. llvm-svn: 301769
* [APInt] Add ashrInPlace method and rewrite ashr to make a copy and then call ↵Craig Topper2017-04-241-0/+36
| | | | | | | | | | | | ashrInPlace. This patch adds an in place version of ashr to match lshr and shl which were recently added. I've tried to make this similar to the lshr code with additions to handle the sign extension. I've also tried to do this with less if checks than the current ashr code by sign extending the original result to a word boundary before doing any of the shifting. This removes a lot of the complexity of determining where to fill in sign bits after the shifting. Differential Revision: https://reviews.llvm.org/D32415 llvm-svn: 301198
* [APInt] Make behavior of ashr by BitWidth consistent between single and ↵Craig Topper2017-04-241-1/+1
| | | | | | | | multi word. Previously single word would always return 0 regardless of the original sign. Multi word would return all 0s or all 1s based on the original sign. Now single word takes into account the sign as well. llvm-svn: 301159
* [APInt] In sext single word case, use SignExtend64 and let the APInt ↵Craig Topper2017-04-231-0/+20
| | | | | | | | constructor mask off any excess bits. The current code is trying to be clever with shifts to avoid needing to clear unused bits. But it looks like the compiler is unable to optimize out the unused bit handling in the APInt constructor. Given this its better to just use SignExtend64 and have more readable code. llvm-svn: 301133
* Revert "[APInt] Add ashrInPlace method and implement ashr using it. Also fix ↵Renato Golin2017-04-231-19/+1
| | | | | | | | | | a bug in the shift by BitWidth handling." This reverts commit r301094, as it broke all ARM self-hosting bots. PR32754. llvm-svn: 301110
* [APInt] Add ashrInPlace method and implement ashr using it. Also fix a bug ↵Craig Topper2017-04-221-1/+19
| | | | | | | | in the shift by BitWidth handling. For single word, shift by BitWidth was always returning 0, but for multiword it was based on original sign. Now single word matches multi word. llvm-svn: 301094
* [APInt] Add isSubsetOf method that can check if one APInt is a subset of ↵Craig Topper2017-04-201-0/+29
| | | | | | | | | | | | | | another without creating temporary APInts This question comes up in many places in SimplifyDemandedBits. This makes it easy to ask without allocating additional temporary APInts. The BitVector class provides a similar functionality through its (IMHO badly named) test(const BitVector&) method. Though its output polarity is reversed. I've provided one example use case in this patch. I plan to do more as a follow up. Differential Revision: https://reviews.llvm.org/D32258 llvm-svn: 300851
* Recommit "[APInt] Add back the asserts that check that the APInt shift ↵Craig Topper2017-04-201-2/+2
| | | | | | | | methods aren't called with values larger than BitWidth." This includes a fix to clamp a right shift of larger than BitWidth in DAG combining. llvm-svn: 300816
* Revert r300811 "[APInt] Add back the asserts that check that the APInt shift ↵Craig Topper2017-04-201-2/+2
| | | | | | | | methods aren't called with values larger than BitWidth." This is failing a self host debug build. llvm-svn: 300813
* [APInt] Add back the asserts that check that the APInt shift methods aren't ↵Craig Topper2017-04-201-2/+2
| | | | | | | | called with values larger than BitWidth. The underlying tcShiftRight/tcShiftLeft functions support the larger bit widths but the APInt interface shouldn't rely on that. llvm-svn: 300811
* [APInt] Make operator<<= shift in place. Improve the implementation of ↵Craig Topper2017-04-181-0/+33
| | | | | | tcShiftLeft and use it to implement operator<<=. llvm-svn: 300526
* [APInt] Merge the multiword code from lshrInPlace and tcShiftRight into a ↵Craig Topper2017-04-171-5/+33
| | | | | | | | | | | | single implementation This merges the two different multiword shift right implementations into a single version located in tcShiftRight. lshrInPlace now calls tcShiftRight for the multiword case. I retained the memmove fast path from lshrInPlace and used a memset for the zeroing. The for loop is basically tcShiftRight's implementation with the zeroing and the intra-shift of 0 removed. Differential Revision: https://reviews.llvm.org/D32114 llvm-svn: 300503
* [APInt] Remove self move check from move assignment operatorCraig Topper2017-04-171-30/+2
| | | | | | | | | | | | This was added to work around a bug in MSVC 2013's implementation of stable_sort. That bug has been fixed as of MSVC 2015 so we shouldn't need this anymore. Technically the current implementation has undefined behavior because we only protect the deleting of the pVal array with the self move check. There is still a memcpy of that.VAL to VAL that isn't protected. In the case of self move those are the same local and memcpy is undefined for src and dst overlapping. This reduces the size of the opt binary on my local x86-64 build by about 4k. Differential Revision: https://reviews.llvm.org/D32116 llvm-svn: 300477
* [APInt] Fix a bug in lshr by a value more than 64 bits above the bit width.Craig Topper2017-04-161-0/+5
| | | | | | This was throwing an assert because we determined the intra-word shift amount by subtracting the size of the full word shift from the total shift amount. But we failed to account for the fact that we clipped the full word shifts by total words first. To fix this just calculate the intra-word shift as the remainder of dividing by bits per word. llvm-svn: 300405
* Remove all allocation and divisions from GreatestCommonDivisorRichard Smith2017-04-131-0/+43
| | | | | | | | | | | Switch from Euclid's algorithm to Stein's algorithm for computing GCD. This avoids the (expensive) APInt division operation in favour of bit operations. Remove all memory allocation from within the GCD loop by tweaking our `lshr` implementation so it can operate in-place. Differential Revision: https://reviews.llvm.org/D31968 llvm-svn: 300252
* [APInt] Move isMask and isShiftedMask out of APIntOps and into the APInt ↵Craig Topper2017-04-031-14/+15
| | | | | | | | | | class. Implement them without memory allocation for multiword This moves the isMask and isShiftedMask functions to be class methods. They now use the MathExtras.h function for single word size and leading/trailing zeros/ones or countPopulation for the multiword size. The previous implementation made multiple temorary memory allocations to do the bitwise arithmetic operations to match the MathExtras.h implementation. Differential Revision: https://reviews.llvm.org/D31565 llvm-svn: 299362
* [APInt] Add a public typedef for the internal type of APInt use it instead ↵Craig Topper2017-04-021-37/+37
| | | | | | | | | | | | | | | | of integerPart. Make APINT_BITS_PER_WORD and APINT_WORD_SIZE public. This patch is one step to attempt to unify the main APInt interface and the tc functions used by APFloat. This patch adds a WordType to APInt and uses that in all the tc functions. I've added temporary typedefs to APFloat to alias it to integerPart to keep the patch size down. I'll work on removing that in a future patch. In future patches I hope to reuse the tc functions to implement some of the main APInt functionality. I may remove APINT_ from BITS_PER_WORD and WORD_SIZE constants so that we don't have the repetitive APInt::APINT_ externally. Differential Revision: https://reviews.llvm.org/D31523 llvm-svn: 299341
* [APInt] Fix bugs in isShiftedMask to match behavior of the similar function ↵Craig Topper2017-03-311-8/+8
| | | | | | | | | | in MathExtras.h This removes a parameter from the routine that was responsible for a lot of the issue. It was a bit count that had to be set to the BitWidth of the APInt and would get passed to getLowBitsSet. This guaranteed the call to getLowBitsSet would create an all ones value. This was then compared to (V | (V-1)). So the only shifted masks we detected had to have the MSB set. The one in tree user is a transform in InstCombine that never fires due to earlier transforms covering the case better. I've submitted a patch to remove it completely, but for now I've just adapted it to the new interface for isShiftedMask. llvm-svn: 299273
* [APInt] Rewrite getLoBits in a way that will do one less memory allocation ↵Craig Topper2017-03-311-0/+18
| | | | | | in the multiword case. Rewrite getHiBits to use the class method version of lshr instead of the one in APIntOps. NFCI llvm-svn: 299243
* [APInt] Add unittests that demonstrate how very broken ↵Craig Topper2017-03-311-0/+25
| | | | | | | | | | APIntOps::isShiftedMask is. Did you know that 0 is a shifted mask? But 0x0000ff00 and 0x000000ff aren't? At least we get 0xff000000 right. I only see one usage of this function in the code base today and its in InstCombine. I think its protected against 0 being misreported as a mask. I guess we just don't have tests for the missed cases. llvm-svn: 299187
* [APInt] Use memset in setAllBits.Craig Topper2017-03-271-0/+38
| | | | llvm-svn: 298867
* Fix signed/unsigned comparison warningsSimon Pilgrim2017-03-101-11/+11
| | | | llvm-svn: 297460
* [APInt] Add APInt::insertBits() method to insert an APInt into a larger APIntSimon Pilgrim2017-03-101-0/+53
| | | | | | | | | | | | We currently have to insert bits via a temporary variable of the same size as the target with various shift/mask stages, resulting in further temporary variables, all of which require the allocation of memory for large APInts (MaskSizeInBits > 64). This is another of the compile time issues identified in PR32037 (see also D30265). This patch adds the APInt::insertBits() helper method which avoids the temporary memory allocation and masks/inserts the raw bits directly into the target. Differential Revision: https://reviews.llvm.org/D30780 llvm-svn: 297458
* Strip trailing whitespace.Simon Pilgrim2017-03-071-4/+1
| | | | llvm-svn: 297225
* [APInt] Add rvalue reference support to and, or, xor operations to allow ↵Craig Topper2017-03-071-0/+120
| | | | | | | | | | | | | | | | their memory allocation to be reused when possible This extends an earlier change that did similar for add and sub operations. With this first patch we lose the fastpath for the single word case as operator&= and friends don't support it. This can be added there if we think that's important. I had to change some functions in the APInt class since the operator overloads were moved out of the class and can't be used inside the class now. The getBitsSet change collides with another outstanding patch to implement it with setBits. But I didn't want to make this patch dependent on that series. I've also removed the Or, And, Xor functions which were rarely or never used. I already commited two changes to remove the only uses of Or that existed. Differential Revision: https://reviews.llvm.org/D30612 llvm-svn: 297121
OpenPOWER on IntegriCloud