summaryrefslogtreecommitdiff
path: root/unittests/ADT
Commit message (Collapse)AuthorAge
* Remove extra semicolon.Jakub Staszak2011-07-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136432 91177308-0d34-0410-b5e6-96231b3b80d8
* Use unsigned rather than uint16_t in case anyone feels like testingDuncan Sands2011-07-28
| | | | | | | | | | more graphs, like all graphs with 5 nodes or less. With a 32 bit unsigned type, the maximum is graphs with 6 nodes or less, but that would take a while to test - 5 nodes or less already requires a few seconds. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136354 91177308-0d34-0410-b5e6-96231b3b80d8
* Check an additional property specific to the way LLVMDuncan Sands2011-07-28
| | | | | | | iterates over SCC's. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136353 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a unittest for the simply connected components (SCC) iterator class.Duncan Sands2011-07-28
| | | | | | | | | This computes every graph with 4 or fewer nodes, and checks that the SCC class indeed returns exactly the simply connected components reachable from the initial node. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136351 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove some code that is no longer needed now that googletest knows howJay Foad2011-07-27
| | | | | | to print STL containers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136213 91177308-0d34-0410-b5e6-96231b3b80d8
* Add Twine support for characters, and switch twine to use a union internallyChris Lattner2011-07-24
| | | | | | | to eliminate some casting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135888 91177308-0d34-0410-b5e6-96231b3b80d8
* Add APInt(numBits, ArrayRef<uint64_t> bigVal) constructor to prevent future ↵Jeffrey Yasskin2011-07-18
| | | | | | | | | ambiguity errors like the one corrected by r135261. Migrate all LLVM callers of the old constructor to the new one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135431 91177308-0d34-0410-b5e6-96231b3b80d8
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an APFloat::convertToInt(APSInt) function that automatically manages theJeffrey Yasskin2011-07-15
| | | | | | memory for the result. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135259 91177308-0d34-0410-b5e6-96231b3b80d8
* The key of a StringMap can contain nul's in it, so having first() returnChris Lattner2011-07-14
| | | | | | | const char* doesn't make sense. Have it return StringRef instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135167 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a subtle issue in SmallVector. The following code did not work as expected:Owen Anderson2011-07-06
| | | | | | | | | | vec.insert(vec.begin(), vec[3]); The issue was that vec[3] returns a reference into the vector, which is invalidated when insert() memmove's the elements down to make space. The method needs to specifically detect and handle this case to correctly match std::vector's semantics. Thanks to Howard Hinnant for clarifying the correct behavior, and explaining how std::vector solves this problem. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134554 91177308-0d34-0410-b5e6-96231b3b80d8
* unittests: add test for APInt::toString()Dylan Noblesmith2011-06-15
| | | | | | | | Follow up to r133032. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133107 91177308-0d34-0410-b5e6-96231b3b80d8
* Try fixing ↵Argyrios Kyrtzidis2011-06-15
| | | | | | http://google1.osuosl.org:8011/builders/clang-i686-freebsd/builds/3548 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133081 91177308-0d34-0410-b5e6-96231b3b80d8
* Add unit tests for ADT/PackedVectorArgyrios Kyrtzidis2011-06-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133075 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove bounded StringRef::compare() since nothing but Clang SA was using it ↵Lenny Maiorani2011-04-28
| | | | | | and it is just as easy to use StringRef::substr() preceding StringRef::compare() to achieve the same thing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130430 91177308-0d34-0410-b5e6-96231b3b80d8
* Implements StringRef::compare with bounds. It is behaves similarly to ↵Lenny Maiorani2011-04-15
| | | | | | strncmp(). Unit tests also included. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129582 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid turning a floating point division with a constant power of two into a ↵Benjamin Kramer2011-03-30
| | | | | | | | | denormal multiplication. Some platforms may treat denormals as zero, on other platforms multiplication with a subnormal is slower than dividing by a normal. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128555 91177308-0d34-0410-b5e6-96231b3b80d8
* Add APFloat::getExactInverse.Benjamin Kramer2011-03-30
| | | | | | | | | | | | | | The idea is, that if an ieee 754 float is divided by a power of two, we can turn the division into a cheaper multiplication. This function sees if we can get an exact multiplicative inverse for a divisor and returns it if possible. This is the hard part of PR9587. I tested many inputs against llvm-gcc's frotend implementation of this optimization and didn't find any difference. However, floating point is the land of weird edge cases, so any review would be appreciated. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128545 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an argument to APInt's magic udiv calculation to specify the number of ↵Benjamin Kramer2011-03-17
| | | | | | | | bits that are known zero in the divided number. This will come in handy soon. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127828 91177308-0d34-0410-b5e6-96231b3b80d8
* The signed version of our "magic number" computation for the integer ↵Cameron Zwarich2011-02-21
| | | | | | | | | | | | | approximation of a constant had a minor typo introduced when copying it from the book, which caused it to favor negative approximations over positive approximations in many cases. Positive approximations require fewer operations beyond the multiplication. In the case of division by 3, we still generate code that is a single instruction larger than GCC's code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126097 91177308-0d34-0410-b5e6-96231b3b80d8
* Part of this test is invariant inside the inner loop - move it outsideDuncan Sands2011-02-03
| | | | | | | the loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124784 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove NoVendor and NoOS, added in commit 123990, from Triple. While itDuncan Sands2011-02-02
| | | | | | | | | | may be useful to understand "none", this is not the place for it. Tweak the fix to Normalize while there: the fix added in 123990 works correctly, but I like this way better. Finally, now that Triple understands some non-trivial environment values, teach the unittests about them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124720 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't infinitely recurse! Patch by Marius Wachtler!Chris Lattner2011-01-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124366 91177308-0d34-0410-b5e6-96231b3b80d8
* Clang was not parsing target triples involving EABI and was generating wrong ↵Renato Golin2011-01-21
| | | | | | IR (wrong PCS) and passing the wrong information down llc via the target-triple printed in IR. I've fixed this by adding the parsing of EABI into LLVM's Triple class and using it to choose the correct PCS in Clang's Tools. A Clang patch is on its way to use this infrastructure. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123990 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ADT/IntEqClasses.h as a light-weight implementation of EquivalenceClasses.h.Jakob Stoklund Olesen2010-12-21
| | | | | | | | | | This implementation already exists as ConnectedVNInfoEqClasses in LiveInterval.cpp, and it seems to be generally useful to have a light-weight way of forming equivalence classes of small integers. IntEqClasses doesn't allow enumeration of the elements in a class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122293 91177308-0d34-0410-b5e6-96231b3b80d8
* Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo seesJakob Stoklund Olesen2010-12-17
| | | | | | monotonic keys. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122093 91177308-0d34-0410-b5e6-96231b3b80d8
* It is allowed to call IntervalMap::const_iterator::advanceTo() with a key thatJakob Stoklund Olesen2010-12-17
| | | | | | | | moves the iterator to end(), and it is valid to call it on end(). That means it is valid to call advanceTo() with any monotonic key sequence. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122092 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap.Jakob Stoklund Olesen2010-12-17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122081 91177308-0d34-0410-b5e6-96231b3b80d8
* Complete tests for IntervalMapOverlaps.Jakob Stoklund Olesen2010-12-17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122019 91177308-0d34-0410-b5e6-96231b3b80d8
* Add basic test exposing many bugs.Jakob Stoklund Olesen2010-12-16
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121995 91177308-0d34-0410-b5e6-96231b3b80d8
* Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limitedJakob Stoklund Olesen2010-12-03
| | | | | | | | | | | editing of the current interval. These methods may cause coalescing, there are corresponding set*Unchecked methods for editing without coalescing. The non-coalescing methods are useful for applying monotonic transforms to all keys or values in a map without accidentally coalescing transformed and untransformed intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120829 91177308-0d34-0410-b5e6-96231b3b80d8
* Support/ADT/Twine: Add toNullTerminatedStringRef.Michael J. Spencer2010-12-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120600 91177308-0d34-0410-b5e6-96231b3b80d8
* PR5207: Rename overloaded APInt methods set(), clear(), flip() toJay Foad2010-12-01
| | | | | | setAllBits(), setBit(unsigned), etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120564 91177308-0d34-0410-b5e6-96231b3b80d8
* Merge System into Support.Michael J. Spencer2010-11-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120298 91177308-0d34-0410-b5e6-96231b3b80d8
* Disallow overlapping inserts, even when inserting the same value.Jakob Stoklund Olesen2010-11-28
| | | | | | | | | | | We always disallowed overlapping inserts with different values, and this makes the insertion code smaller and faster. If an overwriting insert is needed, it can be added as a separate method that trims any existing intervals before inserting. The immediate use cases for IntervalMap don't need this - they only use disjoint insertions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120264 91177308-0d34-0410-b5e6-96231b3b80d8
* Add default constructors for iterators.Jakob Stoklund Olesen2010-11-28
| | | | | | | These iterators don't point anywhere, and they can't be compared to anything. They are only good for assigning to. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120239 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement const_iterator::advanceTo().Jakob Stoklund Olesen2010-11-28
| | | | | | | This is a version of find() that always searches forwards and is faster for local searches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120237 91177308-0d34-0410-b5e6-96231b3b80d8
* Add more tests for erase(). Fix a few exposed bugs.Jakob Stoklund Olesen2010-11-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
* Add test case with randomly ordered insertions, massive coalescing.Jakob Stoklund Olesen2010-11-27
| | | | | | | | | | Implement iterator::erase() in a simple version that erases nodes when they become empty, but doesn't try to redistribute elements among siblings for better packing. Handle coalescing across leaf nodes which may require erasing entries. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120226 91177308-0d34-0410-b5e6-96231b3b80d8
* Add B+-tree test case that creates a height 3 tree with a smaller root node.Jakob Stoklund Olesen2010-11-26
| | | | | | Change temporary debugging code to write a dot file directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120171 91177308-0d34-0410-b5e6-96231b3b80d8
* Tweak ImmutableMap/ImmutableSet/ImmutableList APIsTed Kremenek2010-11-24
| | | | | | | | | | to use lowercase letters for the start of most method names and to replace some method names with more descriptive names (e.g., "getLeft()" instead of "Left()"). No real functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120070 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement IntervalMap::clear().Jakob Stoklund Olesen2010-11-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
* Support backwards iteration starting from end().Jakob Stoklund Olesen2010-11-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
* Add test for PR 8111. By Frits van Bommel.Dale Johannesen2010-11-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119870 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ADT/IntervalMap.Jakob Stoklund Olesen2010-11-19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a sorted interval map data structure for small keys and values with automatic coalescing and bidirectional iteration over coalesced intervals. Except for coalescing intervals, it provides similar functionality to std::map. It is however much more compact for small keys and values, and hopefully faster too. The container object itself can hold the first few intervals without any allocations, then it switches to a cache conscious B+-tree representation. A recycling allocator can be shared between many containers, even between containers holding different types. The IntervalMap is initially intended to be used with SlotIndex intervals for: - Backing store for LiveIntervalUnion that is smaller and faster than std::set. - Backing store for LiveInterval with less overhead than std::vector for typical intervals and O(N log N) merging of large intervals. 99% of virtual registers need 4 entries or less and would benefit from the small object optimization. - Backing store for LiveDebugVariable which doesn't exist yet, but will track debug variables during register allocation. This is a work in progress. Missing items are: - Performance metrics. - erase(). - insert() shrinkage. - clear(). - More performance metrics. - Simplification and detemplatization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119787 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "Add ADT/IntervalMap.", GCC doesn't like it.Jakob Stoklund Olesen2010-11-19
| | | | | | This reverts r119772. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ADT/IntervalMap.Jakob Stoklund Olesen2010-11-19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a sorted interval map data structure for small keys and values with automatic coalescing and bidirectional iteration over coalesced intervals. Except for coalescing intervals, it provides similar functionality to std::map. It is however much more compact for small keys and values, and hopefully faster too. The container object itself can hold the first few intervals without any allocations, then it switches to a cache conscious B+-tree representation. A recycling allocator can be shared between many containers, even between containers holding different types. The IntervalMap is initially intended to be used with SlotIndex intervals for: - Backing store for LiveIntervalUnion that is smaller and faster than std::set. - Backing store for LiveInterval with less overhead than std::vector for typical intervals and O(N log N) merging of large intervals. 99% of virtual registers need 4 entries or less and would benefit from the small object optimization. - Backing store for LiveDebugVariable which doesn't exist yet, but will track debug variables during register allocation. This is a work in progress. Missing items are: - Performance metrics. - erase(). - insert() shrinkage. - clear(). - More performance metrics. - Simplification and detemplatization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119772 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch attribute macros to use 'LLVM_' as a prefix. We retain the old namesChandler Carruth2010-10-23
| | | | | | | until other LLVM projects using these are cleaned up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117200 91177308-0d34-0410-b5e6-96231b3b80d8
* Move ValueMapTest from ADT to VMCore so that ADT doesn't needDan Gohman2010-09-27
| | | | | | | to link in "core". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114831 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an all() method to BitVector, for testing whether all bits are set.Dan Gohman2010-09-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114830 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-03 05:12:37 +0000