summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/ADT
Commit message (Collapse)AuthorAgeFilesLines
...
* [RISCV] Recognise riscv32 and riscv64 in triple parsing codeAlex Bradbury2016-11-011-0/+36
| | | | | | | | | | | This is the first in a series of 10 initial patches that incrementally add an MC layer for RISC-V to LLVM. See <http://lists.llvm.org/pipermail/llvm-dev/2016-August/103748.html> for more discussion. Differential Revision: https://reviews.llvm.org/D23557 llvm-svn: 285707
* [unittests] STLExtrasTest: Remove an MSVC 2013 workaround, NFCI.Vedant Kumar2016-10-251-2/+1
| | | | | | Let's see what the bots have to say about this... llvm-svn: 285091
* [ADT] Zip range adapterMehdi Amini2016-10-191-0/+63
| | | | | | | | | | | | | | | This augments the STLExtras toolset with a zip iterator and range adapter. Zip comes in two varieties: `zip`, which will zip to the shortest of the input ranges, and `zip_first`, which limits its `begin() == end()` checks to just the first range. Recommit r284035 after MSVC2013 support has been dropped. Patch by: Bryant Wong <github.com/bryant> Differential Revision: https://reviews.llvm.org/D23252 llvm-svn: 284623
* [ADT] Remove CachedHash<T>.Justin Lebar2016-10-181-49/+0
| | | | | | | | Nobody is using it. Differential Revision: https://reviews.llvm.org/D25630 llvm-svn: 284503
* [ADT] Add an initializer_list constructor to {Small,}DenseSet.Justin Lebar2016-10-171-0/+15
| | | | | | | | | | Reviewers: timshen Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25629 llvm-svn: 284433
* [ADT] Add SmallDenseSet.Justin Lebar2016-10-171-1/+5
| | | | | | | | | | | | Summary: This matches SmallDenseMap. Reviewers: timshen Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25628 llvm-svn: 284432
* PR30711: Fix incorrect profiling of 'long long' in FoldingSet, then use it toRichard Smith2016-10-161-0/+21
| | | | | | fix TBAA violation in profiling of pointers. llvm-svn: 284336
* Define "contiki" OS specifier.David L Kreitzer2016-10-141-0/+6
| | | | | | | | Patch by Michael LeMay Differential revision: http://reviews.llvm.org/D24897 llvm-svn: 284240
* Revert "[ADT] Zip range adapter"Mehdi Amini2016-10-121-63/+0
| | | | | | This reverts commit r284035, which breaks with MSVC 2013. llvm-svn: 284037
* [ADT] Zip range adapterMehdi Amini2016-10-121-0/+63
| | | | | | | | | | | | | This augments the STLExtras toolset with a zip iterator and range adapter. Zip comes in two varieties: `zip`, which will zip to the shortest of the input ranges, and `zip_first`, which limits its `begin() == end()` checks to just the first krange. Patch by: Bryant Wong <github.com/bryant> Differential Revision: https://reviews.llvm.org/D23252 llvm-svn: 284035
* Re-apply "Disallow ArrayRef assignment from temporaries."Jordan Rose2016-10-111-0/+28
| | | | | | | | | | This re-applies r283798, disabled in r283803, with the static_assert tests disabled under MSVC. The deleted functions still seem to catch mistakes in MSVC, so it's not a significant loss. Part of rdar://problem/16375365 llvm-svn: 283935
* Revert "Disallow ArrayRef assignment from temporaries."Zachary Turner2016-10-101-23/+0
| | | | | | | | | | | This reverts commit r283798, as it causes static asserts on MSVC 2015 with the following errors: ArrayRefTest.cpp(38): error C2338: Assigning from single prvalue element ArrayRefTest.cpp(41): error C2338: Assigning from single xvalue element ArrayRefTest.cpp(47): error C2338: Assigning from an initializer list llvm-svn: 283803
* Rename llvm::apply -> llvm::apply_tuple.Zachary Turner2016-10-101-3/+3
| | | | | | | | | | | llvm::cl already has a function called llvm::apply() so this is causing an ODR violation. The STLExtras version should win the vote on which one gets to be called apply() since it is named after the equivalent STL function, but since renaiming the cl version is more difficult, let's do this for now to get the bots green. llvm-svn: 283800
* Disallow ArrayRef assignment from temporaries.Jordan Rose2016-10-101-0/+23
| | | | | | | | | | | | | | | | | | | | | | | | Without this, the following statements will create ArrayRefs that refer to temporary storage that goes out of scope by the end of the line: someArrayRef = getSingleElement(); someArrayRef = {elem1, elem2}; Note that the constructor still has this problem: ArrayRef<Element> someArrayRef = getSingleElement(); ArrayRef<Element> someArrayRef = {elem1, elem2}; but that's a little harder to get rid of because we want to be able to use this in calls: takesArrayRef(getSingleElement()); takesArrayRef({elem1, elem2}); Part of rdar://problem/16375365. Reviewed by Duncan Exon Smith. llvm-svn: 283798
* [ADT] Don't use make_pointee_iterator in IteratorTest.Justin Lebar2016-10-101-25/+20
| | | | llvm-svn: 283794
* Add llvm::apply to STLExtras.Zachary Turner2016-10-101-0/+45
| | | | | | | | | This is equivalent to the C++14 std::apply(). Since we are not using C++14 yet, this allows us to still make use of apply anyway. Differential revision: https://reviews.llvm.org/D25100 llvm-svn: 283779
* [ADT] Add make_pointe{e,r}_iterator.Justin Lebar2016-10-101-20/+25
| | | | | | | | | | Reviewers: timshen Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25418 llvm-svn: 283765
* [ADT] Let MapVector handle non-copyable values.Justin Lebar2016-10-101-0/+18
| | | | | | | | | | | | Summary: The keys must still be copyable, because we store two copies of them. Reviewers: timshen Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25404 llvm-svn: 283764
* [Triple] Add triple for FuchsiaPetr Hosek2016-10-061-0/+6
| | | | | | | | Fuchsia is a new operating system. Differential Revision: https://reviews.llvm.org/D25116 llvm-svn: 283419
* Remove extra semicolonReid Kleckner2016-10-051-1/+1
| | | | llvm-svn: 283395
* Fix the build with MSVC 2013, still cannot default move ctors yetReid Kleckner2016-10-051-1/+2
| | | | | | Ten days. llvm-svn: 283394
* Modify df_iterator to support post-order actionsDavid Callahan2016-10-051-0/+2
| | | | | | | | | | | | Summary: This makes a change to the state used to maintain visited information for depth first iterator. We know assume a method "completed(...)" which is called after all children of a node have been visited. In all existing cases, this method does nothing so this patch has no functional changes. It will however allow a client to distinguish back from cross edges in a DFS tree. Reviewers: nadav, mehdi_amini, dberlin Subscribers: MatzeB, mzolotukhin, twoh, freik, llvm-commits Differential Revision: https://reviews.llvm.org/D25191 llvm-svn: 283391
* [ADT] Add missing const_iterator DenseSet::find() constVitaly Buka2016-10-051-11/+25
| | | | | | | | | | | | Summary: Probably overlooked. Reviewers: eugenis, dblaikie Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24689 llvm-svn: 283377
* Fix build due to comparison of std::pairs.Zachary Turner2016-10-051-16/+20
| | | | llvm-svn: 283342
* Add llvm::enumerate() range adapter.Zachary Turner2016-10-051-27/+128
| | | | | | | | | This allows you to enumerate over a range using a range-based for while the return type contains the index of the enumeration. Differential revision: https://reviews.llvm.org/D25124 llvm-svn: 283337
* [Support] Add case-insensitive versions of StringSwitch members.Zachary Turner2016-10-041-0/+99
| | | | | | | | | This adds support for CaseLower, CasesLower, StartsWithLower, and EndsWithLower. Differential revision: https://reviews.llvm.org/D24686 llvm-svn: 283244
* Add unit tests for StringSwitch.Zachary Turner2016-10-032-0/+108
| | | | | | Differential revision: https://reviews.llvm.org/D25205 llvm-svn: 283138
* Turn LLVM_ENABLE_ABI_BREAKING_CHECKS into a 0/1 definition likeJoerg Sonnenberger2016-09-301-1/+1
| | | | | | | LLVM_ENABLE_THREADS. Include llvm-config.h explicitly in headers to make sure that the definition is available. llvm-svn: 282907
* Resubmit "Add llvm::enumerate() to STLExtras."Zachary Turner2016-09-301-0/+49
| | | | | | | | The CL was originally failing due to the use of some C++14 specific features, so I've removed those. Hopefully this will satisfy the bots. llvm-svn: 282867
* Revert "Add llvm::enumerate() to STLExtras."Zachary Turner2016-09-291-49/+0
| | | | | | | This reverts commit r282804 as it seems to use some C++ features that not all compilers support. llvm-svn: 282809
* Add llvm::enumerate() to STLExtras.Zachary Turner2016-09-291-0/+49
| | | | | | | | | enumerate allows you to iterate over a range by pairing the iterator's value with its index in the enumeration. This gives you most of the benefits of using a for loop while still allowing the range syntax. llvm-svn: 282804
* Add llvm::join_items to StringExtras.Zachary Turner2016-09-272-0/+53
| | | | | | | | | | | | | | | | llvm::join_items is similar to llvm::join, which produces a string by concatenating a sequence of values together separated by a given separator. But it differs in that the arguments to llvm::join() are same-type members of a container, whereas the arguments to llvm::join_items are arbitrary types passed into a variadic template. The only requirement on parameters to llvm::join_items (including for the separator themselves) is that they be implicitly convertible to std::string or have an overload of std::string::operator+ Differential Revision: https://reviews.llvm.org/D24880 llvm-svn: 282502
* Fix signed / unsigned comparison.Zachary Turner2016-09-251-2/+2
| | | | llvm-svn: 282348
* Add some predicated searching functions to StringRef.Zachary Turner2016-09-251-0/+56
| | | | | | | | | | | | | | | | | | | | | | This adds 4 new functions to StringRef, which can be used to take or drop characters while a certain condition is met, or until a certain condition is met. They are: take_while - Return characters until a condition is not met. take_until - Return characters until a condition is met. drop_while - Remove characters until a condition is not met. drop_until - Remove characters until a condition is met. Internally, all of these functions delegate to two additional helper functions which can be used to search for the position of a character meeting or not meeting a condition, which are: find_if - Find the first character matching a predicate. find_if_not - Find the first character not matching a predicate. Differential Revision: https://reviews.llvm.org/D24842 llvm-svn: 282346
* Triple: Add opencl environment typeTom Stellard2016-09-231-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: For AMDGPU, we have been using the operating system component of the triple for specifying the low-level runtime that is being used. The rationale for this is that the host operating system (e.g. Linux) is irrelevant for GPU code, since its execution enviroment will be mostly controled by the low-level runtime being used to execute the code. In most cases, higher level languages have their own runtime which is implemented on top of the low-level runtime. The kernel ABIs of each language mostly depend on the low-level runtime, but there may be some slight differences between languages. OpenCL for example, may append additional arguments to the kernel in order to pass values like global offsets or buffers for printf. OpenMP, HCC, or other languages may want to add their own values which differ from OpenCL. The reason for adding a new opencl environment type is to make it possible for the backend to distinguish between the ABIs of the higher-level languages and handle them correctly. It seems cleaner to use the enviroment component for this rather than creating a new OS type for every combination of low-level runtime / high-level language. Reviewers: Anastasia, chandlerc Subscribers: whchung, pekka.jaaskelainen, wdng, yaxunl, llvm-commits Differential Revision: https://reviews.llvm.org/D24735 llvm-svn: 282218
* Fix build breakage due to typo in cast.Zachary Turner2016-09-221-0/+2
| | | | llvm-svn: 282183
* Speculative fix for build failures due to consumeInteger.Zachary Turner2016-09-221-1/+2
| | | | | | | | | | | | | | | | A recent patch added support for consumeInteger() and made getAsInteger delegate to this function. A few buildbots are failing as a result with an assertion failure. On a hunch, I tested what happens if I call getAsInteger() on an empty string, and sure enough it crashes the same way that the buildbots are crashing. I confirmed that getAsInteger() on an empty string did not crash before my patch, so I suspect this to be the cause. I also added a unit test for the empty string. llvm-svn: 282170
* [Support] Add StringRef::consumeInteger.Zachary Turner2016-09-221-0/+177
| | | | | | | | | | | | | | | | | | | | | StringRef::getInteger() exists and treats the entire string as an integer of the specified radix, failing if any invalid characters are encountered or the number overflows. Sometimes you might have something like "123456foo" and you want to get the number 123456 and leave the string "foo" remaining. This is similar to what would be possible by using the standard runtime library functions strtoul et al and specifying an end pointer. This patch adds consumeInteger(), which does exactly that. It consumes as much as possible until an invalid character is found, and modifies the StringRef in place so that upon return only the portion of the StringRef after the number remains. Differential Revision: https://reviews.llvm.org/D24778 llvm-svn: 282164
* ADT: Never allocate nodes in iplist<> and ilist<>Duncan P. N. Exon Smith2016-09-111-8/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | Remove createNode() and any API that depending on it, and add HasCreateNode to the list of checks for HasObsoleteCustomizations. Now an ilist *never* allocates (this was already true for iplist). This factors out all the differences between iplist and ilist. I'll aim to rename both to "owning_ilist" eventually, to call out the interesting (not exactly intrusive) ownership semantics. In the meantime, I've left both names around to reduce code churn. One of the deleted APIs is the ilist copy constructor. I've lifted up and tested iplist::cloneFrom (ala simple_ilist::cloneFrom) as a replacement. Users of ilist<> and iplist<> that want the list to allocate nodes have a few options: - use std::list; - use AllocatorList or BumpPtrList (or build a similarly trivial list); - use cloneFrom (which is explicit at the call site); or - allocate at the call site. See r280573, r281177, r281181, and r281182 for examples of what to do if you're updating out-of-tree code. llvm-svn: 281184
* ADT: Add AllocatorList, and use it for yaml::TokenDuncan P. N. Exon Smith2016-09-112-0/+244
| | | | | | | | | | | | | | | | | | | | | | | | | | | | - Add AllocatorList, a non-intrusive list that owns an LLVM-style allocator and provides a std::list-like interface (trivially built on top of simple_ilist), - add a typedef (and unit tests) for BumpPtrList, and - use BumpPtrList for the list of llvm::yaml::Token (i.e., TokenQueueT). TokenQueueT has no need for the complexity of an intrusive list. The only reason to inherit from ilist was to customize the allocator. TokenQueueT was the only example in-tree of using ilist<> in a truly non-intrusive way. Moreover, this removes the final use of the non-intrusive ilist_traits<>::createNode (after r280573, r281177, and r281181). I have a WIP patch that removes this customization point (and the API that relies on it) that I plan to commit soon. Note: AllocatorList owns the allocator, which limits the viable API (e.g., splicing must be on the same list). For now I've left out any problematic API. It wouldn't be hard to split AllocatorList into two layers: an Impl class that calls DerivedT::getAlloc (via CRTP), and derived classes that handle Allocator ownership/reference/etc semantics; and then implement splice with appropriate assertions; but TBH we should probably just customize the std::list allocators at that point. llvm-svn: 281182
* ADT: Add sentinel tracking and custom tags to ilistsDuncan P. N. Exon Smith2016-09-116-16/+220
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This adds two declarative configuration options for intrusive lists (available for simple_ilist, iplist, and ilist). Both of these options affect ilist_node interoperability and need to be passed both to the node and the list. Instead of adding a new traits class, they're specified as optional template parameters (in any order). The two options: 1. Pass ilist_sentinel_tracking<true> or ilist_sentinel_tracking<false> to control whether there's a bit on ilist_node "prev" pointer indicating whether it's the sentinel. The default behaviour is to use a bit if and only if LLVM_ENABLE_ABI_BREAKING_CHECKS. 2. Pass ilist_tag<TagA> and ilist_tag<TagB> to allow insertion of a single node into two different lists (simultaneously). I have an immediate use-case for (1) ilist_sentinel_tracking: fixing the validation semantics of MachineBasicBlock::reverse_iterator to match ilist::reverse_iterator (ala r280032: see the comments at the end of the commit message there). I'm adding (2) ilist_tag in the same commit to validate that the options framework supports expansion. Justin Bogner mentioned this might enable a possible cleanup in SelectionDAG, but I'll leave this to others to explore. In the meantime, the unit tests and the comments for simple_ilist and ilist_node have usage examples. Note that there's a layer of indirection to support optional, out-of-order, template paramaters. Internal classes are templated on an instantiation of the non-variadic ilist_detail::node_options. User-facing classes use ilist_detail::compute_node_options to compute the correct instantiation of ilist_detail::node_options. The comments for ilist_detail::is_valid_option describe how to add new options (e.g., ilist_packed_int<int NumBits>). llvm-svn: 281167
* ADT: Move ilist_node_access to ilist_detail::NodeAccess...Duncan P. N. Exon Smith2016-09-102-5/+10
| | | | | | | | | | | | | | | | | ... and make a few ilist-internal API changes, in preparation for changing how ilist_node is templated. The only effect for ilist users should be changing the friend target from llvm::ilist_node_access to llvm::ilist_detail::NodeAccess (which is only necessary when they inherit privately from ilist_node). - Split out SpecificNodeAccess, which has overloads of getNodePtr and getValuePtr that are untemplated. - Use more typedefs to prevent more changes later. - Force inheritance to use *NodeAccess (to emphasize that ilist *users* shouldn't be doing this). There should be no functionality change here. llvm-svn: 281142
* ADT: Use typedefs for ilist_base and ilist_node_base, NFCDuncan P. N. Exon Smith2016-09-101-25/+28
| | | | | | | This is a prep commit to minimize changes in a follow-up that is adding a template parameter to ilist_node_base and ilist_base. llvm-svn: 281141
* ADT: Fix up IListTest.privateNode and get it passingDuncan P. N. Exon Smith2016-09-031-3/+3
| | | | | | | | This test was using the wrong type, and so not actually testing much. ilist_iterator constructors weren't going through ilist_node_access, so they didn't actually work with private inheritance. llvm-svn: 280564
* s/static inline/static/ for headers I have changed in r279475. NFC.Tim Shen2016-08-311-5/+3
| | | | llvm-svn: 280257
* Fix unit test after function name change.Zachary Turner2016-08-301-4/+4
| | | | llvm-svn: 280129
* ADT: Split ilist_node_traits into alloc and callback, NFCDuncan P. N. Exon Smith2016-08-301-9/+25
| | | | | | | | | | | | | | | | Many lists want to override only allocation semantics, or callbacks for iplist. Split these up to prevent code duplication. - Specialize ilist_alloc_traits to change the implementations of deleteNode() and createNode(). - One common desire is to do nothing deleteNode() and disable createNode(). Specialize ilist_alloc_traits to inherit from ilist_noalloc_traits for that behaviour. - Specialize ilist_callback_traits to use the addNodeToList(), removeNodeFromList(), and transferNodesFromList() callbacks. As a drive-by, add some coverage to the callback-related unit tests. llvm-svn: 280128
* Add StringRef::take_front and StringRef::take_backZachary Turner2016-08-302-0/+57
| | | | | | | Reviewed By: majnemer, rnk Differential Revision: https://reviews.llvm.org/D23965 llvm-svn: 280114
* ADT: Split out simple_ilist, a simple intrusive listDuncan P. N. Exon Smith2016-08-304-38/+650
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Split out a new, low-level intrusive list type with clear semantics. Unlike iplist (and ilist), all operations on simple_ilist are intrusive, and simple_ilist never takes ownership of its nodes. This enables an intuitive API that has the right defaults for intrusive lists. - insert() takes references (not pointers!) to nodes (in iplist/ilist, passing a reference will cause the node to be copied). - erase() takes only iterators (like std::list), and does not destroy the nodes. - remove() takes only references and has the same behaviour as erase(). - clear() does not destroy the nodes. - The destructor does not destroy the nodes. - New API {erase,remove,clear}AndDispose() take an extra Disposer functor for callsites that want to call some disposal routine (e.g., std::default_delete). This list is not currently configurable, and has no callbacks. The initial motivation was to fix iplist<>::sort to work correctly (even with callbacks in ilist_traits<>). iplist<> uses simple_ilist<>::sort directly. The new test in unittests/IR/ModuleTest.cpp crashes without this commit. Fixing sort() via a low-level layer provided a good opportunity to: - Unit test the low-level functionality thoroughly. - Modernize the API, largely inspired by other intrusive list implementations. Here's a sketch of a longer-term plan: - Create BumpPtrList<>, a non-intrusive list implemented using simple_ilist<>, and use it for the Token list in lib/Support/YAMLParser.cpp. This will factor out the only real use of createNode(). - Evolve the iplist<> and ilist<> APIs in the direction of simple_ilist<>, making allocation/deallocation explicit at call sites (similar to simple_ilist<>::eraseAndDispose()). - Factor out remaining calls to createNode() and deleteNode() and remove the customization from ilist_traits<>. - Transition uses of iplist<>/ilist<> that don't need callbacks over to simple_ilist<>. llvm-svn: 280107
* ADT: Explode include/llvm/ADT/{ilist,ilist_node}.h, NFCDuncan P. N. Exon Smith2016-08-302-2/+2
| | | | | | | | | | | | | | | | | | | | | I'm working on a lower-level intrusive list that can be used stand-alone, and splitting the files up a bit will make the code easier to organize. Explode the ilist headers in advance to improve blame lists in the future. - Move ilist_node_base from ilist_node.h to ilist_node_base.h. - Move ilist_base from ilist.h to ilist_base.h. - Move ilist_iterator from ilist.h to ilist_iterator.h. - Move ilist_node_access from ilist.h to ilist_node.h to support ilist_iterator. - Update unit tests to #include smaller headers. - Clang-format the moved things. I noticed in transit that there is a simplify_type specialization for ilist_iterator. Since there is no longer an implicit conversion from ilist<T>::iterator to T*, this doesn't make sense (effectively it's a form of implicit conversion). For now I've added a FIXME. llvm-svn: 280047
OpenPOWER on IntegriCloud