aboutsummaryrefslogtreecommitdiff
path: root/unittests/ADT
AgeCommit message (Collapse)Author
2011-04-28Remove bounded StringRef::compare() since nothing but Clang SA was using it ↵Lenny Maiorani
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
2011-04-15Implements StringRef::compare with bounds. It is behaves similarly to ↵Lenny Maiorani
strncmp(). Unit tests also included. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129582 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-30Avoid turning a floating point division with a constant power of two into a ↵Benjamin Kramer
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
2011-03-30Add APFloat::getExactInverse.Benjamin Kramer
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
2011-03-17Add an argument to APInt's magic udiv calculation to specify the number of ↵Benjamin Kramer
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
2011-02-21The signed version of our "magic number" computation for the integer ↵Cameron Zwarich
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
2011-02-03Part of this test is invariant inside the inner loop - move it outsideDuncan Sands
the loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124784 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-02Remove NoVendor and NoOS, added in commit 123990, from Triple. While itDuncan Sands
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
2011-01-27Don't infinitely recurse! Patch by Marius Wachtler!Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124366 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-21Clang was not parsing target triples involving EABI and was generating wrong ↵Renato Golin
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
2010-12-21Add ADT/IntEqClasses.h as a light-weight implementation of EquivalenceClasses.h.Jakob Stoklund Olesen
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
2010-12-17Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo seesJakob Stoklund Olesen
monotonic keys. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122093 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17It is allowed to call IntervalMap::const_iterator::advanceTo() with a key thatJakob Stoklund Olesen
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
2010-12-17Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122081 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Complete tests for IntervalMapOverlaps.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122019 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-16Add basic test exposing many bugs.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121995 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-03Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limitedJakob Stoklund Olesen
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
2010-12-01Support/ADT/Twine: Add toNullTerminatedStringRef.Michael J. Spencer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120600 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-01PR5207: Rename overloaded APInt methods set(), clear(), flip() toJay Foad
setAllBits(), setBit(unsigned), etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120564 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-29Merge System into Support.Michael J. Spencer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120298 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-28Disallow overlapping inserts, even when inserting the same value.Jakob Stoklund Olesen
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
2010-11-28Add default constructors for iterators.Jakob Stoklund Olesen
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
2010-11-28Implement const_iterator::advanceTo().Jakob Stoklund Olesen
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
2010-11-27Add more tests for erase(). Fix a few exposed bugs.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-27Add test case with randomly ordered insertions, massive coalescing.Jakob Stoklund Olesen
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
2010-11-26Add B+-tree test case that creates a height 3 tree with a smaller root node.Jakob Stoklund Olesen
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
2010-11-24Tweak ImmutableMap/ImmutableSet/ImmutableList APIsTed Kremenek
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
2010-11-19Implement IntervalMap::clear().Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Support backwards iteration starting from end().Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Add test for PR 8111. By Frits van Bommel.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119870 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Add ADT/IntervalMap.Jakob Stoklund Olesen
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
2010-11-19Revert "Add ADT/IntervalMap.", GCC doesn't like it.Jakob Stoklund Olesen
This reverts r119772. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Add ADT/IntervalMap.Jakob Stoklund Olesen
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
2010-10-23Switch attribute macros to use 'LLVM_' as a prefix. We retain the old namesChandler Carruth
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
2010-09-27Move ValueMapTest from ADT to VMCore so that ADT doesn't needDan Gohman
to link in "core". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114831 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-27Add an all() method to BitVector, for testing whether all bits are set.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114830 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-16Add better support for environment portion of triple. Original patch byDuncan Sands
Cameron Esfahani, tweaked to use array_lengthof. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114073 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-14Attempt to unbreak the FreeBSD buildbot by XFAILing a unit test that seems to beJakob Stoklund Olesen
miscompiled by the system gcc-4.2.1 The test remains enabled for the second-stage test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113824 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-26StringRef::compare_numeric also differed from StringRef::compare for ↵Benjamin Kramer
characters > 127. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112189 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-26Do unsigned char comparisons in StringRef::compare_lower to be more ↵Benjamin Kramer
consistent with compare in corner cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112185 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-19Silence 'unused' warning.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111539 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-12Add a 'normalize' method to the Triple class, which takes a mucked upDuncan Sands
target triple and straightens it out. This does less than gcc's script config.sub, for example it turns i386-mingw32 into i386--mingw32 not i386-pc-mingw32, but it does a decent job of turning funky triples into something that the rest of the Triple class can understand. The plan is to use this to canonicalize triple's when they are first provided by users, and have the rest of LLVM only deal with canonical triples. Once this is done the special case workarounds in the Triple constructor can be removed, making the class more regular and easier to use. The comments and unittests for the Triple class are already adjusted in this patch appropriately for this brave new world of increased uniformity. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110909 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-08Remove the ValueMap copy constructor. It's not used anywhere,Duncan Sands
and removing it catches the mistake of passing a ValueMap by copy rather than by reference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110549 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-30Fix the ValueMap copy constructor. The issue is that the map keys are valueDuncan Sands
handles with a pointer to the containing map. When a map is copied, these pointers need to be corrected to point to the new map. If not, then consider the case of a map M1 which maps a value V to something. Create a copy M2 of M1. At this point there are two value handles on V, one representing V as a key in M1, the other representing V as a key in M2. But both value handles point to M1 as the containing map. Now delete V. The value handles remove themselves from their containing map (which destroys them), but only the first value handle is successful: the second one cannot remove itself from M1 as (once the first one has removed itself) there is nothing there to remove; it is therefore not destroyed. This causes an assertion failure "All references to V were not removed?". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109851 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-13Switch from EXPECT_EQ({true,false, ...) to the more canonicalChandler Carruth
EXPECT_{TRUE,FALSE}(...) macros. This also prevents suprious warnings about bool-to-pointer conversion that occurs withit EXPECT_EQ. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108248 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-10Use non-bool values for .count.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108048 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-08ADT: Add DAGDeltaAlgorithm, which is a DAG minimization algorithm built on ↵Daniel Dunbar
top of the standard 'delta debugging' algorithm. - This can give substantial speedups in the delta process for inputs we can construct dependency information for. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@105612 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-26Add StringRef::compare_numeric and use it to sort TableGen register records.Jakob Stoklund Olesen
This means that our Registers are now ordered R7, R8, R9, R10, R12, ... Not R1, R10, R11, R12, R2, R3, ... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104745 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-13Fix const ilist_node::get{Prev,Next}Node() to actually compile. Picky, picky.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103723 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-12ADT: Add ilist_node::get{Prev,Next}Node, which return the adjacent node or null.Daniel Dunbar
- This provides a convenient alternative to using something llvm::prior or manual iterator access, for example:: if (T *Prev = foo->getPrevNode()) ... instead of:: iterator it(foo); if (it != begin()) { --it; ... } - Chris, please review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103647 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-01-26 13:36:23 +0000