summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Support/APInt.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [APInt] Make toString use udivrem instead of calling the divide helper ↵Craig Topper2017-05-101-8/+9
| | | | | | | | | | method directly. Do a better job of reusing allocations while looping. NFCI This lets toString take advantage of the degenerate case checks in udivrem and is just generally cleaner. One minor downside of this is that the divisor APInt now needs to be the same size as Tmp which requires an additional allocation. But we were doing a poor job of reusing allocations before so the new code should still be an improvement. llvm-svn: 302704
* [APInt] Use uint32_t instead of unsigned for the storage type throughout the ↵Craig Topper2017-05-101-39/+34
| | | | | | divide code. Use Lo_32/Hi_32/Make_64 helpers instead of casts and shifts. NFCI llvm-svn: 302703
* [APInt] Use getRawData to slightly simplify some code.Craig Topper2017-05-101-2/+2
| | | | llvm-svn: 302702
* [APInt] Remove check for single word since single word was handled earlier ↵Craig Topper2017-05-101-2/+2
| | | | | | in the function. NFC llvm-svn: 302701
* [APInt] Fix indentation of tcDivide. Combine variable declaration and ↵Craig Topper2017-05-101-15/+13
| | | | | | initialization. llvm-svn: 302626
* [APInt] Use getNumWords function in udiv/urem/udivrem instead of ↵Craig Topper2017-05-101-12/+6
| | | | | | reimplementinging it. llvm-svn: 302625
* [APInt] Remove return value from tcFullMultiply.Craig Topper2017-05-091-11/+5
| | | | | | | | The description says it returns the number of words needed to represent the results. But the way it was coded it always returns (lhsWords + rhsWords) or (lhsWords + rhsWords - 1). But the result could be even smaller than that and it wouldn't tell you. No one uses the result today so rather than try to fix it, just remove it. llvm-svn: 302551
* [APInt] Use default constructor instead of explicitly creating a 1-bit APInt ↵Craig Topper2017-05-081-2/+2
| | | | | | | | in udiv and urem. NFC The default constructor does the same thing. llvm-svn: 302487
* [APInt] Remove 'else' after 'return' in udiv and urem. NFCCraig Topper2017-05-081-9/+7
| | | | llvm-svn: 302486
* [APInt] Modify tcMultiplyPart's overflow detection to not depend on 'i' from ↵Craig Topper2017-05-081-6/+5
| | | | | | | | the earlier loop. NFC The value of 'i' is always the smaller of DstParts and SrcParts so we can just use that fact to write all the code in terms of SrcParts and DstParts. llvm-svn: 302408
* [APInt] Use std::min instead of writing the same thing with the ternary ↵Craig Topper2017-05-081-1/+1
| | | | | | operator. NFC llvm-svn: 302407
* [APInt] Remove 'else' after 'return' in tcMultiply methods. NFCCraig Topper2017-05-081-24/+23
| | | | llvm-svn: 302406
* [APInt] Take advantage of new operator*=(uint64_t) to remove a temporary APInt.Craig Topper2017-05-081-5/+1
| | | | llvm-svn: 302403
* [APInt] Add support for multiplying by a uint64_t.Craig Topper2017-05-081-0/+10
| | | | | | This makes multiply similar to add, sub, xor, and, and or. llvm-svn: 302402
* [APInt] Reduce number of allocations involved in multiplying. Reduce worst ↵Craig Topper2017-05-041-110/+10
| | | | | | | | | | | | | | | | | | | | | | case multiply size Currently multiply is implemented in operator*=. Operator* makes a copy and uses operator*= to modify the copy. Operator*= itself allocates a temporary buffer to hold the multiply result as it computes it. Then copies it to the buffer in *this. Operator*= attempts to bound the size of the result based on the number of active bits in its inputs. It also has a couple special cases to handle 0 inputs without any memory allocations or multiply operations. The best case is that it calculates a single word regardless of input bit width. The worst case is that it calculates the a 2x input width result and drop the upper bits. Since operator* uses operator*= it incurs two allocations, one for a copy of *this and one for the temporary allocation. Neither of these allocations are kept after the method operation is done. The main usage in the backend appears to be ConstantRange::multiply which uses operator* rather than operator*=. This patch moves the multiply operation to operator* and implements operator*= using it. This avoids the copy in operator*. operator* now allocates a result buffer sized the same width as its inputs no matter what. This buffer will be used as the buffer for the returned APInt. Finally, we reuse tcMultiply to implement the multiply operation. This function is capable of not calculating additional upper words that will be discarded. This change does lose the special optimizations for the inputs using less words than their size implies. But it also removed the getActiveBits calls from all multiplies. If we think those optimizations are important we could look at providing additional bounds to tcMultiply to limit the computations. Differential Revision: https://reviews.llvm.org/D32830 llvm-svn: 302171
* [APInt] Give the value union a name so we can remove assumptions on VAL ↵Craig Topper2017-05-031-145/+144
| | | | | | | | | | | | | | being the larger member Currently several places assume the VAL member is always at least the same size as pVal. In particular for a memcpy in the move assignment operator. While this is a true assumption, it isn't good practice to assume this. This patch gives the union a name so we can write the memcpy in terms of the union itself. This also adds a similar memcpy to the move constructor where we previously just copied using VAL directly. This patch is mostly just a mechanical addition of the U in front of VAL and pVAL everywhere. But several constructors had to be modified since we can't directly initializer a field of named union from the initializer list. Differential Revision: https://reviews.llvm.org/D30629 llvm-svn: 302040
* [APInt] Move APInt::getSplat out of line.Craig Topper2017-05-021-0/+11
| | | | | | I think this method is probably too complex to be inlined. llvm-svn: 301901
* [APInt] Move the setBit and clearBit methods inline.Craig Topper2017-05-021-16/+0
| | | | | | This makes setBit/clearBit more consistent with setBits which is already inlined. llvm-svn: 301900
* [APInt] Use inplace shift methods where possible. NFCICraig Topper2017-04-281-3/+4
| | | | llvm-svn: 301612
* [APInt] Simplify the zext and sext methodsCraig Topper2017-04-241-33/+18
| | | | | | | | | | This replaces a hand written copy loop with a call to memcpy for both zext and sext. For sext, it replaces multiple if/else blocks propagating sign information forward. Now we just do a copy, a sign extension on the last copied word, a memset, and clearUnusedBits. Differential Revision: https://reviews.llvm.org/D32417 llvm-svn: 301201
* [APInt] Add ashrInPlace method and rewrite ashr to make a copy and then call ↵Craig Topper2017-04-241-76/+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] Fix repeated word in comments. NFCCraig Topper2017-04-241-2/+2
| | | | llvm-svn: 301192
* [APInt] Make behavior of ashr by BitWidth consistent between single and ↵Craig Topper2017-04-241-1/+3
| | | | | | | | 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-5/+2
| | | | | | | | 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] Fix a few places that use APInt::getRawData to operate ↵Renato Golin2017-04-231-4/+3
| | | | | | | | | | | | | | | | within the normal API." This reverts commit r301105, 4, 3 and 1, as a follow up of the previous revert, which broke even more bots. For reference: Revert "[APInt] Use operator<<= where possible. NFC" Revert "[APInt] Use operator<<= instead of shl where possible. NFC" Revert "[APInt] Use ashInPlace where possible." PR32754. llvm-svn: 301111
* Revert "[APInt] Add ashrInPlace method and implement ashr using it. Also fix ↵Renato Golin2017-04-231-26/+73
| | | | | | | | | | 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] Use operator<<= instead of shl where possible. NFCCraig Topper2017-04-231-3/+4
| | | | llvm-svn: 301103
* [APInt] Add ashrInPlace method and implement ashr using it. Also fix a bug ↵Craig Topper2017-04-221-73/+26
| | | | | | | | 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] Remove unnecessary min with BitWidth from countTrailingOnesSlowCase.Craig Topper2017-04-221-1/+2
| | | | | | The unused upper bits are guaranteed to be 0 so we don't need to worry about accidentally counting them. llvm-svn: 301091
* [APInt] Add WORD_MAX constant and use it instead of UINT64_MAX. NFCCraig Topper2017-04-221-15/+15
| | | | llvm-svn: 301069
* [APInt] Add compare/compareSigned methods that return -1, 0, 1. Reimplement ↵Craig Topper2017-04-211-35/+9
| | | | | | | | | | | | | | | | slt/ult and friends using them Currently sle and ule have to call slt/ult and eq to get the proper answer. This results in extra code for both calls and additional scans of multiword APInts. This patch replaces slt/ult with a compareSigned/compare that can return -1, 0, or 1 so we can cover all the comparison functions with a single call. While I was there I removed the activeBits calls and other checks at the start of the slow part of ult. Both of the activeBits calls potentially scan through each of the APInts separately. I can't imagine that's any better than just scanning them in parallel and doing the compares. Now we just share the code with tcCompare. These changes seem to be good for about a 7-8k reduction on the size of the opt binary on my local x86-64 build. Differential Revision: https://reviews.llvm.org/D32339 llvm-svn: 300995
* [APInt] Add isSubsetOf method that can check if one APInt is a subset of ↵Craig Topper2017-04-201-0/+8
| | | | | | | | | | | | | | 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
* [APInt] Implement APInt::intersects without creating a temporary APInt in ↵Craig Topper2017-04-201-0/+8
| | | | | | | | | | | | | | | | the multiword case Summary: This is a simple question we should be able to answer without creating a temporary to hold the AND result. We can also get an early out as soon as we find a word that intersects. Reviewers: RKSimon, hans, spatel, davide Reviewed By: hans, davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32253 llvm-svn: 300812
* [APInt] Implement operator==(uint64_t) similar to ugt/ult(uint64_t) to ↵Craig Topper2017-04-191-8/+0
| | | | | | remove one of the out of line EqualsSlowCase methods. llvm-svn: 300799
* [APInt] Move the 'return *this' from the slow cases of assignment operators ↵Craig Topper2017-04-191-10/+7
| | | | | | | | inline. We should let the compiler see that the fast/slow cases both return *this. I don't think we chain assignments together very often so this shouldn't matter much. llvm-svn: 300715
* [APInt] Inline the single word case of lshrInPlace similar to what we do for ↵Craig Topper2017-04-181-9/+1
| | | | | | <<=. llvm-svn: 300577
* [APInt] Use lshrInPlace to replace lshr where possibleCraig Topper2017-04-181-4/+4
| | | | | | | | | | This patch uses lshrInPlace to replace code where the object that lshr is called on is being overwritten with the result. This adds an lshrInPlace(const APInt &) version as well. Differential Revision: https://reviews.llvm.org/D32155 llvm-svn: 300566
* [APInt] Cleanup the reverseBits slow case a little.Craig Topper2017-04-181-6/+4
| | | | | | Use lshrInPlace. Use single bit extract and operator|=(uint64_t) to avoid a few temporary APInts. llvm-svn: 300527
* [APInt] Make operator<<= shift in place. Improve the implementation of ↵Craig Topper2017-04-181-78/+24
| | | | | | 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-68/+25
| | | | | | | | | | | | 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] Fix a bug in lshr by a value more than 64 bits above the bit width.Craig Topper2017-04-161-1/+1
| | | | | | 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-70/+82
| | | | | | | | | | | 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] Reorder fields to avoid a hole in the middle of the classCraig Topper2017-04-131-1/+1
| | | | | | | | | | | | | | | | | | | Summary: APInt is currently implemented with an unsigned BitWidth field first and then a uint_64/pointer union. Due to the 64-bit size of the union there is a hole after the bitwidth. Putting the union first allows the class to be packed. Making it 12 bytes instead of 16 bytes. An APSInt goes from 20 bytes to 16 bytes. This shows a 4k reduction on the size of the opt binary on my local x86-64 build. So this enables some other improvement to the code as well. Reviewers: dblaikie, RKSimon, hans, davide Reviewed By: davide Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D32001 llvm-svn: 300171
* [APInt] Generalize the implementation of tcIncrement to support adding a ↵Craig Topper2017-04-131-64/+40
| | | | | | full 'word' by introducing tcAddPart. Use this to support tcIncrement, operator++ and operator+=(uint64_t). Do the same for subtract. NFCI. llvm-svn: 300169
* [APInt] Make use of whichWord and maskBit to simplify some code. NFCCraig Topper2017-04-021-5/+3
| | | | llvm-svn: 299342
* [APInt] Add a public typedef for the internal type of APInt use it instead ↵Craig Topper2017-04-021-81/+81
| | | | | | | | | | | | | | | | 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
* [X86] Use tcAdd/tcSubtract to implement the slow case of operator+=/operator-=.Craig Topper2017-04-021-33/+3
| | | | llvm-svn: 299326
* [APInt] Combine declaration and initialization. NFCCraig Topper2017-04-021-6/+2
| | | | llvm-svn: 299325
* [APInt] Simplify some code by using operator+=(uint64_t) instead of doing a ↵Craig Topper2017-04-021-7/+2
| | | | | | more complex assignment into a temporary APInt just to use the APInt operator+=. llvm-svn: 299324
* [APInt] Fix typo in comment. NFCCraig Topper2017-04-021-1/+1
| | | | llvm-svn: 299323
OpenPOWER on IntegriCloud