summaryrefslogtreecommitdiff
path: root/unittests/ADT
Commit message (Collapse)AuthorAge
...
* SparseSet: Add support for key-derived indexes and arbitrary key types.Andrew Trick2012-04-20
| | | | | | | | | | | | | | | | | | | This nicely handles the most common case of virtual register sets, but also handles anticipated cases where we will map pointers to IDs. The goal is not to develop a completely generic SparseSet template. Instead we want to handle the expected uses within llvm without any template antics in the client code. I'm adding a bit of template nastiness here, and some assumption about expected usage in order to make the client code very clean. The expected common uses cases I'm designing for: - integer keys that need to be reindexed, and may map to additional data - densely numbered objects where we want pointer keys because no number->object map exists. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155227 91177308-0d34-0410-b5e6-96231b3b80d8
* Add triple support for the IBM BG/P and BG/Q supercomputers.Hal Finkel2012-04-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153882 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix warnings.Michael J. Spencer2012-03-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152522 91177308-0d34-0410-b5e6-96231b3b80d8
* Make StringRef::getAsInteger work with all integer types. Before this changeMichael J. Spencer2012-03-10
| | | | | | | | it would fail with {,u}int64_t on x86-64 Linux. This also removes code duplication. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152517 91177308-0d34-0410-b5e6-96231b3b80d8
* Add support to the hashing infrastructure for automatically hashing bothChandler Carruth2012-03-07
| | | | | | | | | | | | | | | | | | integral and enumeration types. This is accomplished with a bit of template type trait magic. Thanks to Richard Smith for the core idea here to detect viable types by detecting the set of types which can be default constructed in a template parameter. This is used (in conjunction with a system for detecting nullptr_t should it exist) to provide an is_integral_or_enum type trait that doesn't need a whitelist or direct compiler support. With this, the hashing is extended to the more general facility. This will be used in a subsequent commit to hashing more things, but I wanted to make sure the type trait magic went through the build bots separately in case other compilers don't like this formulation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152217 91177308-0d34-0410-b5e6-96231b3b80d8
* SmallPtrSet: Provide a more efficient implementation of swap than the ↵Benjamin Kramer2012-03-06
| | | | | | | | | default triple-copy std::swap. This currently assumes that both sets have the same SmallSize to keep the implementation simple, a limitation that can be lifted if someone cares. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152143 91177308-0d34-0410-b5e6-96231b3b80d8
* Add generic support for hashing StringRef objects using the new hashing library.Chandler Carruth2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152003 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach the hashing facilities how to hash std::string objects.Chandler Carruth2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152000 91177308-0d34-0410-b5e6-96231b3b80d8
* Split this test up into two smaller, and more focused tests.Chandler Carruth2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151999 91177308-0d34-0410-b5e6-96231b3b80d8
* Move the NonPOD struct out of the anonymous namespace instead of adding ↵Francois Pichet2012-03-03
| | | | | | | | llvm:: everywhere to fix the HashingTest on MSVC . chandlerc proposed this better solution on IRC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151974 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixes the Hashing tests on MSVC by adding llvm:: prefix to hash_value ↵Francois Pichet2012-03-03
| | | | | | function call. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151971 91177308-0d34-0410-b5e6-96231b3b80d8
* unittests/ADT/HashingTest.cpp: Temporarily disable a new test introduced in ↵NAKAMURA Takumi2012-03-03
| | | | | | r151891, to appease msvc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151970 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify the pair optimization. Rather than using complex type traits,Chandler Carruth2012-03-02
| | | | | | | | | | | | | | just ensure that the number of bytes in the pair is the sum of the bytes in each side of the pair. As long as thats true, there are no extra bytes that might be padding. Also add a few tests that previously would have slipped through the checking. The more accurate checking mechanism catches these and ensures they are handled conservatively correctly. Thanks to Duncan for prodding me to do this right and more simply. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151891 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a golden data test that I missed somehow the first time around.Chandler Carruth2012-03-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151886 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bad indenting that was left over from cut/paste of the golden valuesChandler Carruth2012-03-02
| | | | | | for 32-bit builds in here. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151885 91177308-0d34-0410-b5e6-96231b3b80d8
* We really want to hash pairs of directly-hashable data as directlyChandler Carruth2012-03-02
| | | | | | | | | | | | | | | | | | | | | | | | | | hashable data. This matters when we have pair<T*, U*> as a key, which is quite common in DenseMap, etc. To that end, we need to detect when this is safe. The requirements on a generic std::pair<T, U> are: 1) Both T and U must satisfy the existing is_hashable_data trait. Note that this includes the requirement that T and U have no internal padding bits or other bits not contributing directly to equality. 2) The alignment constraints of std::pair<T, U> do not require padding between consecutive objects. 3) The alignment constraints of U and the size of T do not conspire to require padding between the first and second elements. Grow two somewhat magical traits to detect this by forming a pod structure and inspecting offset artifacts on it. Hopefully this won't cause any compilers to panic. Added and adjusted tests now that pairs, even nested pairs, are treated as just sequences of data. Thanks to Jeffrey Yasskin for helping me sort through this and reviewing the somewhat subtle traits. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151883 91177308-0d34-0410-b5e6-96231b3b80d8
* Add support for hashing pairs by delegating to each sub-object. There isChandler Carruth2012-03-02
| | | | | | | | | | | | | | | | | an open question of whether we can do better than this by treating pairs as boring data containers and directly hashing the two subobjects. This at least makes the API reasonable. In order to make this change, I reorganized the header a bit. I lifted the declarations of the hash_value functions up to the top of the header with their doxygen comments as these are intended for users to interact with. They shouldn't have to wade through implementation details. I then defined them at the very end so that they could be defined in terms of hash_combine or any other hashing infrastructure. Added various pair-hashing unittests. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151882 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the misguided extension here that reserved two special values inChandler Carruth2012-03-02
| | | | | | | | | | | the hash_code. I'm not sure what I was thinking here, the use cases for special values are in the *keys*, not in the hashes of those keys. We can always resurrect this if needed, or clients can accomplish the same goal themselves. This makes the general case somewhat faster (~5 cycles faster on my machine) and smaller with less branching. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151865 91177308-0d34-0410-b5e6-96231b3b80d8
* Re-disable the debug output. The comment is there explaining why we wantChandler Carruth2012-03-01
| | | | | | | | to keep this around -- updating golden tests is annoying otherwise. Thanks to Benjamin for pointing this omission out on IRC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151860 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide the 32-bit variant of the golden tests. Not sure how I forgot toChandler Carruth2012-03-01
| | | | | | do this initially, sorry. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151857 91177308-0d34-0410-b5e6-96231b3b80d8
* Rewrite LLVM's generalized support library for hashing to follow the APIChandler Carruth2012-03-01
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | of the proposed standard hashing interfaces (N3333), and to use a modified and tuned version of the CityHash algorithm. Some of the highlights of this change: -- Significantly higher quality hashing algorithm with very well distributed results, and extremely few collisions. Should be close to a checksum for up to 64-bit keys. Very little clustering or clumping of hash codes, to better distribute load on probed hash tables. -- Built-in support for reserved values. -- Simplified API that composes cleanly with other C++ idioms and APIs. -- Better scaling performance as keys grow. This is the fastest algorithm I've found and measured for moderately sized keys (such as show up in some of the uniquing and folding use cases) -- Support for enabling per-execution seeds to prevent table ordering or other artifacts of hashing algorithms to impact the output of LLVM. The seeding would make each run different and highlight these problems during bootstrap. This implementation was tested extensively using the SMHasher test suite, and pased with flying colors, doing better than the original CityHash algorithm even. I've included a unittest, although it is somewhat minimal at the moment. I've also added (or refactored into the proper location) type traits necessary to implement this, and converted users of GeneralHash over. My only immediate concerns with this implementation is the performance of hashing small keys. I've already started working to improve this, and will continue to do so. Currently, the only algorithms faster produce lower quality results, but it is likely there is a better compromise than the current one. Many thanks to Jeffrey Yasskin who did most of the work on the N3333 paper, pair-programmed some of this code, and reviewed much of it. Many thanks also go to Geoff Pike Pike and Jyrki Alakuijala, the original authors of CityHash on which this is heavily based, and Austin Appleby who created MurmurHash and the SMHasher test suite. Also thanks to Nadav, Tobias, Howard, Jay, Nick, Ahmed, and Duncan for all of the review comments! If there are further comments or concerns, please let me know and I'll jump on 'em. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151822 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typos.Jakob Stoklund Olesen2012-02-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151163 91177308-0d34-0410-b5e6-96231b3b80d8
* Support was removed from LLVM's MIPS backend for the PSP variant of thatChandler Carruth2012-02-22
| | | | | | | | | | | | | chip in r139383, and the PSP components of the triple are really annoying to parse. Let's leave this chapter behind. There is no reason to expect LLVM to see a PSP-related triple these days, and so no reasonable motivation to support them. It might be reasonable to prune a few of the older MIPS triple forms in general, but as those at least cause no burden on parsing (they aren't both a chip and an OS!), I'm happy to leave them in for now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151156 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a Briggs and Torczon sparse set implementation.Jakob Stoklund Olesen2012-02-22
| | | | | | | | | | | For objects that can be identified by small unsigned keys, SparseSet provides constant time clear() and fast deterministic iteration. Insert, erase, and find operations are typically faster than hash tables. SparseSet is useful for keeping information about physical registers, virtual registers, or numbered basic blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151110 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch the llvm::Triple class to immediately parse the triple string onChandler Carruth2012-02-21
| | | | | | | | | construction. Simplify its interface, implementation, and users accordingly as there is no longer an 'uninitialized' state to check for. Also, fixes a bug lurking in the interface as there was one method that didn't correctly check for initialization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151024 91177308-0d34-0410-b5e6-96231b3b80d8
* Hashing.h - utilities for hashing various data types.Talin2012-02-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150890 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a unittest for rotating a really big APInt.Benjamin Kramer2012-02-07
| | | | | | Clang miscompiles it under certain circumstances, and it's a good exercise for APInt. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149986 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce helpers to compute the 32-bit varaints and 64-bit variants ofChandler Carruth2012-02-06
| | | | | | | some architectures. These are useful for interacting with multiarch or bi-arch GCC (or GCC-based) toolchains. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149895 91177308-0d34-0410-b5e6-96231b3b80d8
* RefCountedBaseVPTR needs the IntrusiveRefCntPtrInfo as friend,Manuel Klimek2012-01-31
| | | | | | | | | | | | | | now that this handles the release / retain calls. Adds a regression test for that bug (which is a compile-time regression) and for the last two changes to the IntrusiveRefCntPtr, especially tests for the memory leak due to copy construction of the ref-counted object and ensuring that the traits are used for release / retain calls. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149411 91177308-0d34-0410-b5e6-96231b3b80d8
* Add various coarse bit-width architecture predicates to llvm::Triple.Chandler Carruth2012-01-31
| | | | | | | These are very useful for frontends and other utilities reasoning about or selecting between triples. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149353 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap::find_as() and unit tests.Talin2012-01-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149229 91177308-0d34-0410-b5e6-96231b3b80d8
* Additional methods for SmallString.Talin2012-01-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148881 91177308-0d34-0410-b5e6-96231b3b80d8
* Add portable bit mask operations to BitVector.Jakob Stoklund Olesen2012-01-17
| | | | | | | | | | | | BitVector uses the native word size for its internal representation. That doesn't work well for literal bit masks in source code. This patch adds BitVector operations to efficiently apply literal bit masks specified as arrays of uint32_t. Since each array entry always holds exactly 32 bits, these portable bit masks can be source code literals, probably produced by TableGen. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148272 91177308-0d34-0410-b5e6-96231b3b80d8
* Some unittests for APInt rotates; patch by Cameron McInally.Eli Friedman2011-12-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147186 91177308-0d34-0410-b5e6-96231b3b80d8
* As Doug pointed out (and I really should know), it is perfectly easy toChandler Carruth2011-12-17
| | | | | | | | | make VariadicFunction actually be trivial. Do so, and also make it look more like your standard trivial functor by making it a struct with no access specifiers. The unit test is updated to initialize its functors properly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146827 91177308-0d34-0410-b5e6-96231b3b80d8
* APInt: update asserts for base-36Dylan Noblesmith2011-12-16
| | | | | | | | Hexatridecimal was added in r139695. And fix the unittest that now triggers the assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146754 91177308-0d34-0410-b5e6-96231b3b80d8
* Put the '*' in the right place in the unit test. Forgot to fix up thisChandler Carruth2011-12-16
| | | | | | bit of style, sorry. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146733 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a generic collection of class templates to ADT for buildingChandler Carruth2011-12-16
| | | | | | | | | | | | variadic-like functions in C++98. See the comments in the header file for a more detailed description of how these work. We plan to use these extensively in the AST matching library. This code and idea were originally authored by Zhanyong Wan. I've condensed it using macros to reduce repeatition and adjusted it to fit better with LLVM's ADT. Thanks to both David Blaikie and Doug Gregor for the review! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146729 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix APFloat::convert so that it handles narrowing conversions correctly; itEli Friedman2011-11-26
| | | | | | | | | | was returning incorrect values in rare cases, and incorrectly marking exact conversions as inexact in some more common cases. Fixes PR11406, and a missed optimization in test/CodeGen/X86/fp-stack-O0.ll. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145141 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a bad char heuristic to StringRef::find.Benjamin Kramer2011-10-15
| | | | | | | | | Based on Horspool's simplified version of Boyer-Moore. We use a constant-sized table of uint8_ts to keep cache thrashing low, needles bigger than 255 bytes are uncommon anyways. The worst case is still O(n*m) but we do a lot better on the average case now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142061 91177308-0d34-0410-b5e6-96231b3b80d8
* Attempt to fix MSVC build.Eli Friedman2011-10-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141831 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix APFloat::getLargest so that it actually returns the correct value. ↵Eli Friedman2011-10-12
| | | | | | Found by accident while reviewing a patch to nearby code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141816 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix APInt::operator*= so that it computes the correct result for large ↵Eli Friedman2011-10-07
| | | | | | integers where there is unsigned overflow. Fix APFloat::toString so that it doesn't depend on the incorrect behavior in common cases (and computes the correct result in some rare cases). Fixes PR11086. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141441 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug in compare_numeric().Jakob Stoklund Olesen2011-09-30
| | | | | | Thanks to Alexandru Dura and Jonas Paulsson for finding it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140859 91177308-0d34-0410-b5e6-96231b3b80d8
* Add APInt support for converting to/from hexatridecimal stringsDouglas Gregor2011-09-14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139695 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a test that wasn't testing the right thing.Matt Beaumont-Gay2011-08-29
| | | | | | | | The APFloat "Zero" test was actually calling the APFloat(const fltSemantics &, integerPart) constructor, and EXPECT_EQ was treating 0 and -0 as equal. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138745 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid undefined behaviour if somehow NUM_GRAPHS equals 2^32 (orDuncan Sands2011-07-29
| | | | | | | | whatever the size of unsigned is), though this can't actually occur for any integer value of NUM_NODES. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136460 91177308-0d34-0410-b5e6-96231b3b80d8
* 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-16 10:32:51 +0000