summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/ADT
Commit message (Collapse)AuthorAgeFilesLines
...
* Rename unittests/ADT/ilistTestTemp.cpp => IListTest.cppDuncan P. N. Exon Smith2016-08-302-15/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | And rename the tests inside from ilistTest to IListTest. This makes the file sort properly in the CMakeLists.txt (previously, sorting would throw it down to the end of the list) and is consistent with the tests I've added more recently. Why use IListNodeBaseTest.cpp (and a test name of IListNodeBaseTest)? - ilist_node_base_test is the obvious thing, since this is testing ilist_node_base. However, gtest disallows underscores in test names. - ilist_node_baseTest fails for the same reason. - ilistNodeBaseTest is weird, because it isn't in our usual TitleCaseTest form that we use for tests, and it also doesn't have the name of the tested class in it. - IlistNodeBaseTest matches TitleCaseTest, but "Ilist" is hard to read, and really "ilist" is an abbreviation for "IntrusiveList" so the lowercase "list" is strange. - That left IListNodeBaseTest. Note: I made this move in two stages, with a temporary filename of ilistTestTemp in between in r279524. This was in the hopes of avoiding problems on Git and SVN clients on case-insensitive filesystems, particularly on buildbots with incremental checkouts. llvm-svn: 280033
* ADT: Give ilist<T>::reverse_iterator a handle to the current nodeDuncan P. N. Exon Smith2016-08-302-0/+150
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Reverse iterators to doubly-linked lists can be simpler (and cheaper) than std::reverse_iterator. Make it so. In particular, change ilist<T>::reverse_iterator so that it is *never* invalidated unless the node it references is deleted. This matches the guarantees of ilist<T>::iterator. (Note: MachineBasicBlock::iterator is *not* an ilist iterator, but a MachineInstrBundleIterator<MachineInstr>. This commit does not change MachineBasicBlock::reverse_iterator, but it does update MachineBasicBlock::reverse_instr_iterator. See note at end of commit message for details on bundle iterators.) Given the list (with the Sentinel showing twice for simplicity): [Sentinel] <-> A <-> B <-> [Sentinel] the following is now true: 1. begin() represents A. 2. begin() holds the pointer for A. 3. end() represents [Sentinel]. 4. end() holds the poitner for [Sentinel]. 5. rbegin() represents B. 6. rbegin() holds the pointer for B. 7. rend() represents [Sentinel]. 8. rend() holds the pointer for [Sentinel]. The changes are #6 and #8. Here are some properties from the old scheme (which used std::reverse_iterator): - rbegin() held the pointer for [Sentinel] and rend() held the pointer for A; - operator*() cost two dereferences instead of one; - converting from a valid iterator to its valid reverse_iterator involved a confusing increment; and - "RI++->erase()" left RI invalid. The unintuitive replacement was "RI->erase(), RE = end()". With vector-like data structures these properties are hard to avoid (since past-the-beginning is not a valid pointer), and don't impose a real cost (since there's still only one dereference, and all iterators are invalidated on erase). But with lists, this was a poor design. Specifically, the following code (which obviously works with normal iterators) now works with ilist::reverse_iterator as well: for (auto RI = L.rbegin(), RE = L.rend(); RI != RE;) fooThatMightRemoveArgFromList(*RI++); Converting between iterator and reverse_iterator for the same node uses the getReverse() function. reverse_iterator iterator::getReverse(); iterator reverse_iterator::getReverse(); Why doesn't iterator <=> reverse_iterator conversion use constructors? In order to catch and update old code, reverse_iterator does not even have an explicit conversion from iterator. It wouldn't be safe because there would be no reasonable way to catch all the bugs from the changed semantic (see the changes at call sites that are part of this patch). Old code used this API: std::reverse_iterator::reverse_iterator(iterator); iterator std::reverse_iterator::base(); Here's how to update from old code to new (that incorporates the semantic change), assuming I is an ilist<>::iterator and RI is an ilist<>::reverse_iterator: [Old] ==> [New] reverse_iterator(I) (--I).getReverse() reverse_iterator(I) ++I.getReverse() --reverse_iterator(I) I.getReverse() reverse_iterator(++I) I.getReverse() RI.base() (--RI).getReverse() RI.base() ++RI.getReverse() --RI.base() RI.getReverse() (++RI).base() RI.getReverse() delete &*RI, RE = end() delete &*RI++ RI->erase(), RE = end() RI++->erase() ======================================= Note: bundle iterators are out of scope ======================================= MachineBasicBlock::iterator, also known as MachineInstrBundleIterator<MachineInstr>, is a wrapper to represent MachineInstr bundles. The idea is that each operator++ takes you to the beginning of the next bundle. Implementing a sane reverse iterator for this is harder than ilist. Here are the options: - Use std::reverse_iterator<MBB::i>. Store a handle to the beginning of the next bundle. A call to operator*() runs a loop (usually operator--() will be called 1 time, for unbundled instructions). Increment/decrement just works. This is the status quo. - Store a handle to the final node in the bundle. A call to operator*() still runs a loop, but it iterates one time fewer (usually operator--() will be called 0 times, for unbundled instructions). Increment/decrement just works. - Make the ilist_sentinel<MachineInstr> *always* store that it's the sentinel (instead of just in asserts mode). Then the bundle iterator can sniff the sentinel bit in operator++(). I initially tried implementing the end() option as part of this commit, but updating iterator/reverse_iterator conversion call sites was error-prone. I have a WIP series of patches that implements the final option. llvm-svn: 280032
* Fix ArrayRef initializer_list Ctor TestDavid Blaikie2016-08-251-1/+2
| | | | | | | | | | The InitializerList test had undefined behavior by creating a dangling pointer to the temporary initializer list. This patch removes the undefined behavior in the test by creating the initializer list directly. Reviewers: mehdi_amini, dblaikie Differential Revision: https://reviews.llvm.org/D23890 llvm-svn: 279783
* Rename unittests/ADT/ilistTest.cpp to ilistTestTemp.cpp (temporarily)Duncan P. N. Exon Smith2016-08-232-2/+5
| | | | | | | | | | | | I'll rename this to IListTest.cpp after a waiting period (tonight? tomorrow?), with a full explanation in that commit. First, I'm moving it aside because Git doesn't play well with case-only filename changes on case-insensitive file systems (and I suspect the same is true of SVN). This two-stage change should help to avoid spurious failures on bots that don't do clean checkouts. llvm-svn: 279524
* ADT: Separate some list manipulation API into ilist_base, NFCDuncan P. N. Exon Smith2016-08-224-0/+202
| | | | | | | | | | | | | | | | | | Separate algorithms in iplist<T> that don't depend on T into ilist_base, and unit test them. While I was adding unit tests for these algorithms anyway, I also added unit tests for ilist_node_base and ilist_sentinel<T>. To make the algorithms and unit tests easier to write, I also did the following minor changes as a drive-by: - encapsulate Prev/Next in ilist_node_base to so that algorithms are easier to read, and - update ilist_node_access API to take nodes by reference. There should be no real functionality change here. llvm-svn: 279484
* Fix header comment for unittests/ADT/ilistTest.cppDuncan P. N. Exon Smith2016-08-221-1/+1
| | | | llvm-svn: 279483
* [ADT] Actually mutate the iterator VisitStack.back().second, not its copy.Tim Shen2016-08-224-228/+307
| | | | | | | | | | | | | | | Summary: Before the change, *Opt never actually gets updated by the end of toNext(), so for every next time the loop has to start over from child_begin(). This bug doesn't affect the correctness, since Visited prevents it from re-entering the same node again; but it's slow. Reviewers: dberris, dblaikie, dannyb Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23649 llvm-svn: 279482
* [GraphTraits] Replace all NodeType usage with NodeRefTim Shen2016-08-221-5/+6
| | | | | | | | This should finish the GraphTraits migration. Differential Revision: http://reviews.llvm.org/D23730 llvm-svn: 279475
* Move unittests/Support/IteratorTest.cpp to unittests/ADT/Duncan P. N. Exon Smith2016-08-202-0/+213
| | | | | | This testing stuff from ADT, not Support. Fix the file location. llvm-svn: 279372
* Reapply "ADT: Remove UB in ilist (and use a circular linked list)"Duncan P. N. Exon Smith2016-08-191-0/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts commit r279053, reapplying r278974 after fixing PR29035 with r279104. Note that r279312 has been committed in the meantime, and this has been rebased on top of that. Otherwise it's identical to r278974. Note for maintainers of out-of-tree code (that I missed in the original message): if the new isKnownSentinel() assertion is firing from ilist_iterator<>::operator*(), this patch has identified a bug in your code. There are a few common patterns: - Some IR-related APIs htake an IRUnit* that might be nullptr, and pass in an incremented iterator as an insertion point. Some old code was using "&*++I", which in the case of end() only worked by fluke. If the IRUnit in question inherits from ilist_node_with_parent<>, you can use "I->getNextNode()". Otherwise, use "List.getNextNode(*I)". - In most other cases, crashes on &*I just need to check for I==end() before dereferencing. - There's also occasional code that sends iterators into a function, and then starts calling I->getOperand() (or other API). Either check for end() before the entering the function, or early exit. Note for if the static_assert with HasObsoleteCustomization is firing for you: - r278513 has examples of how to stop using custom sentinel traits. - r278532 removed ilist_nextprev_traits since no one was using it. See lld's r278469 for the only migration I needed to do. Original commit message follows. ---- This removes the undefined behaviour (UB) in ilist/ilist_node/etc., mainly by removing (gutting) the ilist_sentinel_traits customization point and canonicalizing on a single, efficient memory layout. This fixes PR26753. The new ilist is a doubly-linked circular list. - ilist_node_base has two ilist_node_base*: Next and Prev. Size-of: two pointers. - ilist_node<T> (size-of: two pointers) is a type-safe wrapper around ilist_node_base. - ilist_iterator<T> (size-of: two pointers) operates on an ilist_node<T>*, and downcasts to T* on dereference. - ilist_sentinel<T> (size-of: two pointers) is a wrapper around ilist_node<T> that has some extra API for list management. - ilist<T> (size-of: two pointers) has an ilist_sentinel<T>, whose address is returned for end(). The new memory layout matches ilist_half_embedded_sentinel_traits<T> exactly. The Head pointer that previously lived in ilist<T> is effectively glued to the ilist_half_node<T> that lived in ilist_half_embedded_sentinel_traits<T>, becoming the Next and Prev in the ilist_sentinel_node<T>, respectively. sizeof(ilist<T>) is now the size of two pointers, and there is never any additional storage for a sentinel. This is a much simpler design for a doubly-linked list, removing most of the corner cases of list manipulation (add, remove, etc.). In follow-up commits, I intend to move as many algorithms as possible into a non-templated base class (ilist_base) to reduce code size. Moreover, this fixes the UB in ilist_iterator/getNext/getPrev operations. Previously, ilist_iterator<T> operated on a T*, even when the sentinel was not of type T (i.e., ilist_embedded_sentinel_traits and ilist_half_embedded_sentinel_traits). This added UB to all operations involving end(). Now, ilist_iterator<T> operates on an ilist_node<T>*, and only downcasts when the full type is guaranteed to be T*. What did we lose? There used to be a crash (in some configurations) on ++end(). Curiously (via UB), ++end() would return begin() for users of ilist_half_embedded_sentinel_traits<T>, but otherwise ++end() would cause a nice dependable nullptr dereference, crashing instead of a possible infinite loop. Options: 1. Lose that behaviour. 2. Keep it, by stealing a bit from Prev in asserts builds. 3. Crash on dereference instead, using the same technique. Hans convinced me (because of the number of problems this and r278532 exposed on Windows) that we really need some assertion here, at least in the short term. I've opted for #3 since I think it catches more bugs. I added only a couple of unit tests to root out specific bugs I hit during bring-up, but otherwise this is tested implicitly via the extensive usage throughout LLVM. Planned follow-ups: - Remove ilist_*sentinel_traits<T>. Here I've just gutted them to prevent build failures in sub-projects. Once I stop referring to them in sub-projects, I'll come back and delete them. - Add ilist_base and move algorithms there. - Check and fix move construction and assignment. Eventually, there are other interesting directions: - Rewrite reverse iterators, so that rbegin().getNodePtr()==&*rbegin(). This allows much simpler logic when erasing elements during a reverse traversal. - Remove ilist_traits::createNode, by deleting the remaining API that creates nodes. Intrusive lists shouldn't be creating nodes themselves. - Remove ilist_traits::deleteNode, by (1) asserting that lists are empty on destruction and (2) changing API that calls it to take a Deleter functor (intrusive lists shouldn't be in the memory management business). - Reconfigure the remaining callback traits (addNodeToList, etc.) to be higher-level, pulling out a simple_ilist<T> that is much easier to read and understand. - Allow tags (e.g., ilist_node<T,tag1> and ilist_node<T,tag2>) so that T can be a member of multiple intrusive lists. llvm-svn: 279314
* Reapply "ADT: Tidy up ilist_traits static asserts, NFC"Duncan P. N. Exon Smith2016-08-191-0/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | This spiritually reapplies r279012 (reverted in r279052) without the r278974 parts. The differences: - Only the HasGetNext trait exists here, so I've only cleaned up (and tested) it. I still added HasObsoleteCustomization since I know this will be expanding when r278974 is reapplied. - I changed the unit tests to use static_assert to catch problems earlier in the build. - I added negative tests for the type traits. Original commit message follows. ---- Change the ilist traits to use decltype instead of sizeof, and add HasObsoleteCustomization so that additions to this list don't need to be added in two places. I suspect this will now work with MSVC, since the trait tested in r278991 seems to work. If for some reason it continues to fail on Windows I'll follow up by adding back the #ifndef _MSC_VER. llvm-svn: 279312
* [ADT] Add the worlds simplest STL extra. Or at least close to it.Chandler Carruth2016-08-192-0/+41
| | | | | | | | | | | | | | | | | This is a little class template that just builds an inheritance chain of empty classes. Despite how simple this is, it can be used to really nicely create ranked overload sets. I've added a unittest as much to document this as test it. You can pass an object of this type as an argument to a function overload set an it will call the first viable and enabled candidate at or below the rank of the object. I'm planning to use this in a subsequent commit to more clearly rank overload candidates used for SFINAE. All credit for this technique and both lines of code here to Richard Smith who was helping me rewrite the SFINAE check in question to much more effectively capture the intended set of checks. llvm-svn: 279197
* Reapply "ADT: Remove references in has_rbegin for reverse()"Duncan P. N. Exon Smith2016-08-181-9/+67
| | | | | | | | | | | | | | | | | | | | | | | This reverts commit r279086, reapplying r279084. I'm not sure what I ran before, because the compile failure for ADTTests reproduced locally. The problem is that TestRev is calling BidirectionalVector::rbegin() when the BidirectionalVector is const, but rbegin() is always non-const. I've updated BidirectionalVector::rbegin() to be callable from const. Original commit message follows. -- As a follow-up to r278991, add some tests that check that decltype(reverse(R).begin()) == decltype(R.rbegin()), and get them passing by adding std::remove_reference to has_rbegin. I'm using static_assert instead of EXPECT_TRUE (and updated the other has_rbegin check from r278991 in the same way) since I figure that's more helpful. llvm-svn: 279091
* Revert "ADT: Remove references in has_rbegin for reverse()"Duncan P. N. Exon Smith2016-08-181-62/+4
| | | | | | | This reverts commit r279084, since it failed on a bot: http://bb.pgr.jp/builders/cmake-llvm-x86_64-linux/builds/41733 llvm-svn: 279086
* ADT: Remove references in has_rbegin for reverse()Duncan P. N. Exon Smith2016-08-181-4/+62
| | | | | | | | | | | | As a follow-up to r278991, add some tests that check that decltype(reverse(R).begin()) == decltype(R.rbegin()), and get them passing by adding std::remove_reference to has_rbegin. I'm using static_assert instead of EXPECT_TRUE (and updated the other has_rbegin check from r278991 in the same way) since I figure that's more helpful. llvm-svn: 279084
* Revert "ADT: Remove UB in ilist (and use a circular linked list)"Diana Picus2016-08-181-62/+0
| | | | | | | This reverts commit r278974 which broke some of our bots (e.g. clang-cmake-aarch64-42vma, clang-cmake-aarch64-full). llvm-svn: 279053
* Revert "ADT: Tidy up ilist_traits static asserts, NFC"Diana Picus2016-08-181-17/+0
| | | | | | | This reverts commit r279012. r278974 broke some bots, I have to revert this to get to it. llvm-svn: 279052
* ADT: Tidy up ilist_traits static asserts, NFCDuncan P. N. Exon Smith2016-08-171-0/+17
| | | | | | | | | | | | Change the ilist traits to use decltype instead of sizeof, and add HasObsoleteCustomization so that additions to this list don't need to be added in two places. I suspect this will now work with MSVC, since the trait tested in r278991 seems to work. If for some reason it continues to fail on Windows I'll follow up by adding back the #ifndef _MSC_VER. llvm-svn: 279012
* Actually enable new test for const RangeAdapter. Missing from r278991Pete Cooper2016-08-171-1/+2
| | | | llvm-svn: 279000
* Fix reverse to work on const rbegin()/rend().Pete Cooper2016-08-171-0/+30
| | | | | | | | | | | | Duncan found that reverse worked on mutable rbegin(), but the has_rbegin trait didn't work with a const method. See http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160815/382890.html for more details. Turns out this was already solved in clang with has_getDecl. Copied that and made it work for rbegin. This includes the tests Duncan attached to that thread, including the traits test. llvm-svn: 278991
* ADT: Remove UB in ilist (and use a circular linked list)Duncan P. N. Exon Smith2016-08-171-0/+62
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This removes the undefined behaviour (UB) in ilist/ilist_node/etc., mainly by removing (gutting) the ilist_sentinel_traits customization point and canonicalizing on a single, efficient memory layout. This fixes PR26753. The new ilist is a doubly-linked circular list. - ilist_node_base has two ilist_node_base*: Next and Prev. Size-of: two pointers. - ilist_node<T> (size-of: two pointers) is a type-safe wrapper around ilist_node_base. - ilist_iterator<T> (size-of: two pointers) operates on an ilist_node<T>*, and downcasts to T* on dereference. - ilist_sentinel<T> (size-of: two pointers) is a wrapper around ilist_node<T> that has some extra API for list management. - ilist<T> (size-of: two pointers) has an ilist_sentinel<T>, whose address is returned for end(). The new memory layout matches ilist_half_embedded_sentinel_traits<T> exactly. The Head pointer that previously lived in ilist<T> is effectively glued to the ilist_half_node<T> that lived in ilist_half_embedded_sentinel_traits<T>, becoming the Next and Prev in the ilist_sentinel_node<T>, respectively. sizeof(ilist<T>) is now the size of two pointers, and there is never any additional storage for a sentinel. This is a much simpler design for a doubly-linked list, removing most of the corner cases of list manipulation (add, remove, etc.). In follow-up commits, I intend to move as many algorithms as possible into a non-templated base class (ilist_base) to reduce code size. Moreover, this fixes the UB in ilist_iterator/getNext/getPrev operations. Previously, ilist_iterator<T> operated on a T*, even when the sentinel was not of type T (i.e., ilist_embedded_sentinel_traits and ilist_half_embedded_sentinel_traits). This added UB to all operations involving end(). Now, ilist_iterator<T> operates on an ilist_node<T>*, and only downcasts when the full type is guaranteed to be T*. What did we lose? There used to be a crash (in some configurations) on ++end(). Curiously (via UB), ++end() would return begin() for users of ilist_half_embedded_sentinel_traits<T>, but otherwise ++end() would cause a nice dependable nullptr dereference, crashing instead of a possible infinite loop. Options: 1. Lose that behaviour. 2. Keep it, by stealing a bit from Prev in asserts builds. 3. Crash on dereference instead, using the same technique. Hans convinced me (because of the number of problems this and r278532 exposed on Windows) that we really need some assertion here, at least in the short term. I've opted for #3 since I think it catches more bugs. I added only a couple of unit tests to root out specific bugs I hit during bring-up, but otherwise this is tested implicitly via the extensive usage throughout LLVM. Planned follow-ups: - Remove ilist_*sentinel_traits<T>. Here I've just gutted them to prevent build failures in sub-projects. Once I stop referring to them in sub-projects, I'll come back and delete them. - Add ilist_base and move algorithms there. - Check and fix move construction and assignment. Eventually, there are other interesting directions: - Rewrite reverse iterators, so that rbegin().getNodePtr()==&*rbegin(). This allows much simpler logic when erasing elements during a reverse traversal. - Remove ilist_traits::createNode, by deleting the remaining API that creates nodes. Intrusive lists shouldn't be creating nodes themselves. - Remove ilist_traits::deleteNode, by (1) asserting that lists are empty on destruction and (2) changing API that calls it to take a Deleter functor (intrusive lists shouldn't be in the memory management business). - Reconfigure the remaining callback traits (addNodeToList, etc.) to be higher-level, pulling out a simple_ilist<T> that is much easier to read and understand. - Allow tags (e.g., ilist_node<T,tag1> and ilist_node<T,tag2>) so that T can be a member of multiple intrusive lists. llvm-svn: 278974
* Remove the Triple tests that stressing the TargetParser's behaviour.Zijiao Ma2016-08-171-191/+0
| | | | | | | | Now the tests of TargetParser is in place: unittests/Support/TargetParserTest.cpp. So the tests in TripleTest.cpp which actually stressing TargetParser's behavior could be removed. llvm-svn: 278899
* ADT: Add some missing coverage for iplist::spliceDuncan P. N. Exon Smith2016-08-171-0/+32
| | | | | | | | | | | | | | | | | | | | | These splices are interesting because they involve swapping two nodes in the same list. There are two ways to do this. Assuming: A -> B -> [Sentinel] You can either: - splice B before A, with: L.splice(A, L, B) or - splice A before Sentinel, with: L.splice(L.end(), L, A) to create: B -> A -> [Sentinel] These two swapping-splices are somewhat interesting corner cases for maintaining the list invariants. The tests pass even with my new ilist implementation, but I had some doubts about the latter when I was looking at weird UB effects. Since I can't find equivalent explicit test coverage elsewhere it seems prudent to commit. llvm-svn: 278887
* [ADT] Change PostOrderIterator to use NodeRef. NFC.Tim Shen2016-08-151-4/+4
| | | | | | | | | | Reviewers: dblaikie Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D23522 llvm-svn: 278752
* [ADT] Add a reserve() method to DenseSet as well as an insert() for R-valueMehdi Amini2016-08-131-0/+71
| | | | | | Recommit 278600 with some fixes to make the test more robust. llvm-svn: 278604
* Revert "[ADT] Add a reserve method to DenseSet as well as an insert() for ↵Mehdi Amini2016-08-131-63/+0
| | | | | | | | | R-value" This reverts commit r278600. The unittest does not pass on MSVC, there is an extra move. Investigating how to make it more robust. llvm-svn: 278603
* [ADT] Add a reserve method to DenseSet as well as an insert() for R-valueMehdi Amini2016-08-131-0/+63
| | | | llvm-svn: 278600
* [ADT] Add relation operators for OptionalTim Shen2016-08-111-11/+139
| | | | | | | | | | | | Summary: Make Optional's behavior the same as the coming std::optional. Reviewers: dblaikie Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23178 llvm-svn: 278397
* Fix UB in APInt::ashrJonathan Roelofs2016-08-101-0/+5
| | | | | | | | i64 -1, whose sign bit is the 0th one, can't be left shifted without invoking UB. https://reviews.llvm.org/D23362 llvm-svn: 278280
* [ADT] Add make_scope_exit().Tim Shen2016-08-102-0/+33
| | | | | | | | | | | | Summary: make_scope_exit() is described in C++ proposal p0052r2, which uses RAII to do cleanup works at scope exit. Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22796 llvm-svn: 278251
* [ADT] Make the triple test 1000x faster through more focused test cases.Chandler Carruth2016-08-061-53/+67
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The current approach isn't a long-term viable pattern. Given the set of architectures A, vendors V, operating systems O, and environments E, it does |A| * |V| * |O| * |E| * 4! tests. As LLVM grows, this test keeps getting slower, despite my working very hard to make it get some "optimizations" even in -O0 builds in order to lower the constant factors. Fundamentally, we're doing an unreasonable amount of work.i Looking at the specific thing being tested -- the goal seems very clearly to be testing the *permutations*, not the *combinations*. The combinations are driving up the complexity much more than anything else. Instead, test every possible value for a given triple entry in every permutation of *some* triple. This really seems to cover the core goal of the test. Every single possible triple component is tested in every position. But because we keep the rest of the triple constant, it does so in a dramatically more scalable amount of time. With this model we do (|A| + |V| + |O| + |E|) * 4! tests. For me on a debug build, this goes from running for 19 seconds to 19 milliseconds, or a 1000x improvement. This makes a world of difference for the critical path of 'ninja check-llvm' and other extremely common workflows. Thanks to Renato, Dean, and David for the helpful review comments and helping me refine the explanation of the change. Differential Revision: https://reviews.llvm.org/D23156 llvm-svn: 277912
* [ADT] NFC: Generalize GraphTraits requirement of "NodeType *" in interfaces ↵Tim Shen2016-08-011-0/+1
| | | | | | | | | | | | | | to "NodeRef", and migrate SCCIterator.h to use NodeRef Summary: By generalize the interface, users are able to inject more flexible Node token into the algorithm, for example, a pair of vector<Node>* and index integer. Currently I only migrated SCCIterator to use NodeRef, but more is coming. It's a NFC. Reviewers: dblaikie, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22937 llvm-svn: 277399
* [ADT] Add 'consume_front' and 'consume_back' methods to StringRef whichChandler Carruth2016-07-311-0/+32
| | | | | | | | | | | are very handy when parsing text. They are essentially a combination of startswith and a self-modifying drop_front, or endswith and drop_back respectively. Differential Revision: https://reviews.llvm.org/D22723 llvm-svn: 277288
* Remove obsolete XFAIL for a test that used to sometimes miscompile underDimitry Andric2016-07-261-5/+0
| | | | | | | FreeBSD with gcc 4.2.1, a long time ago (see r113824). Noticed by Pete Cooper. llvm-svn: 276730
* Use RValue refs in APInt add/sub methods.Pete Cooper2016-07-221-0/+169
| | | | | | | | | | | | | This adds versions of operator + and - which are optimized for the LHS/RHS of the operator being RValue's. When an RValue is available, we can use its storage space instead of allocating new space. On code such as ConstantRange which makes heavy use of APInt's over 64-bits in size, this results in significant numbers of saved allocations. Thanks to David Blaikie for all the review and most of the code here. llvm-svn: 276470
* [DenseMap] Add a C++17-style try_emplace method.Benjamin Kramer2016-07-211-0/+10
| | | | | | | | This provides an elegant pattern to solve the "construct if not in map already" problem we have many times in LLVM. Without try_emplace we either have to rely on a sentinel value (nullptr) or do two lookups. llvm-svn: 276277
* Rename StringMap::emplace_second to try_emplace.Benjamin Kramer2016-07-211-1/+1
| | | | | | | Coincidentally this function maps to the C++17 try_emplace. Rename it for consistentcy with C++17 std::map. NFC. llvm-svn: 276276
* Fix warnings in ImmutableSetTest and SequenceTest.Justin Lebar2016-07-172-5/+10
| | | | | | | | | | | | | | Doing "I++" inside of an EXPECT_* triggers warning: expression with side effects has no effect in an unevaluated context because EXPECT_* partially expands to EqHelper<(sizeof(::testing::internal::IsNullLiteralHelper(i++)) == 1)> which is an unevaluated context. llvm-svn: 275717
* [ADT] Add LLVM_MARK_AS_BITMASK_ENUM, used to enable bitwise operations on ↵Justin Lebar2016-07-132-0/+135
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | enums without static_cast. Summary: Normally when you do a bitwise operation on an enum value, you get back an instance of the underlying type (e.g. int). But using this macro, bitwise ops on your enum will return you back instances of the enum. This is particularly useful for enums which represent a combination of flags. Suppose you have a function which takes an int and a set of flags. One way to do this would be to take two numeric params: enum SomeFlags { F1 = 1, F2 = 2, F3 = 4, ... }; void Fn(int Num, int Flags); void foo() { Fn(42, F2 | F3); } But now if you get the order of arguments wrong, you won't get an error. You might try to fix this by changing the signature of Fn so it accepts a SomeFlags arg: enum SomeFlags { F1 = 1, F2 = 2, F3 = 4, ... }; void Fn(int Num, SomeFlags Flags); void foo() { Fn(42, static_cast<SomeFlags>(F2 | F3)); } But now we need a static cast after doing "F2 | F3" because the result of that computation is the enum's underlying type. This patch adds a mechanism which gives us the safety of the second approach with the brevity of the first. enum SomeFlags { F1 = 1, F2 = 2, F3 = 4, ..., F_MAX = 128, LLVM_MARK_AS_BITMASK_ENUM(F_MAX) }; void Fn(int Num, SomeFlags Flags); void foo() { Fn(42, F2 | F3); // No static_cast. } The LLVM_MARK_AS_BITMASK_ENUM macro enables overloads for bitwise operators on SomeFlags. Critically, these operators return the enum type, not its underlying type, so you don't need any static_casts. An advantage of this solution over the previously-proposed BitMask class [0, 1] is that we don't need any wrapper classes -- we can operate directly on the enum itself. The approach here is somewhat similar to OpenOffice's typed_flags_set [2]. But we skirt the need for a wrapper class (and a good deal of complexity) by judicious use of enable_if. We SFINAE on the presence of a particular enumerator (added by the LLVM_MARK_AS_BITMASK_ENUM macro) instead of using a traits class so that it's impossible to use the enum before the overloads are present. The solution here also seamlessly works across multiple namespaces. [0] http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150622/283369.html [1] http://lists.llvm.org/pipermail/llvm-commits/attachments/20150623/073434b6/attachment.obj [2] https://cgit.freedesktop.org/libreoffice/core/tree/include/o3tl/typed_flags_set.hxx Reviewers: chandlerc, rsmith Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D22279 llvm-svn: 275292
* [ADT] Add a new data structure for managing a priority worklist whereChandler Carruth2016-06-302-0/+107
| | | | | | | | | | | | | | | | | | | | | | | | re-insertion of entries into the worklist moves them to the end. This is fairly similar to a SetVector, but helps in the case where in addition to not inserting duplicates you want to adjust the sequence of a pop-off-the-back worklist. I'm not at all attached to the name of this data structure if others have better suggestions, but this is one that David Majnemer brought up in IRC discussions that seems plausible. I've trimmed the interface down somewhat from SetVector's interface because several things make less sense here IMO: iteration primarily. I'd prefer to add these back as we have users that need them. My use case doesn't even need all of what is provided here. =] I've also included a basic unittest to make sure this functions reasonably. Differential Revision: http://reviews.llvm.org/D21866 llvm-svn: 274198
* [Triple] Reimplement isLittleEndian(). Now it works for arm too.Davide Italiano2016-06-291-0/+8
| | | | | | Differential Revision: http://reviews.llvm.org/D21846 llvm-svn: 274154
* Add support for musl-libc on ARM Linux.Rafael Espindola2016-06-241-0/+6
| | | | | | Patch by Lei Zhang! llvm-svn: 273726
* Fix BitVector move ctor/assignment.Evgeniy Stepanov2016-06-161-0/+26
| | | | | | | | Current implementation leaves the object in an invalid state. This reverts commit bf0c389ac683cd6c0e5959b16537e59e5f4589e3. llvm-svn: 272965
* Add a Musl environment to the triple.Rafael Espindola2016-06-141-0/+6
| | | | | | | | It will be used in clang. Patch by Lei Zhang. llvm-svn: 272660
* Adding reserve and capacity methods to FoldingSetBen Craig2016-06-031-0/+133
| | | | | | http://reviews.llvm.org/D20930 llvm-svn: 271669
* [ADT] Pass ArrayRef::slice size_t instead of unsigned.Ahmed Bougacha2016-06-021-0/+15
| | | | | | | | | | Also fix slice wrappers drop_front and drop_back. The unittests are pretty awkward, but do the job; alternatives welcome! ..and yes, I do have ArrayRefs with more than 4 billion elements. llvm-svn: 271546
* Don't allocate in APInt::slt. NFC.Pete Cooper2016-05-261-0/+28
| | | | | | | | | | | | | | | | | | | | | | | APInt::slt was copying the LHS and RHS in to temporaries then making them unsigned so that it could use an unsigned comparision. It did this even on the paths which were trivial to give results for, such as the sign bit of the LHS being set while RHS was not set. This changes the logic to return out immediately in the trivial cases, and use an unsigned comparison in the remaining cases. But this time, just use the unsigned comparison directly without creating any temporaries. This works because, for example: true = (-2 slt -1) = (0xFE ult 0xFF) Also added some tests explicitly for slt with APInt's larger than 64-bits so that this new code is tested. Using the memory for 'opt -O2 verify-uselistorder.lto.opt.bc -o opt.bc' (see r236629 for details), this reduces the number of allocations from 26.8M to 23.9M. llvm-svn: 270881
* [ADT] Add an 'llvm::seq' function which produces an iterator range overChandler Carruth2016-05-132-0/+40
| | | | | | | | | | | | | | | | | | | | | | | | | a sequence of values. It increments through the values in the half-open range: [Begin, End), producing those values when indirecting the iterator. It should support integers, iterators, and any other type providing these basic arithmetic operations. This came up in the C++ standards committee meeting, and it seemed like a useful construct that LLVM might want as well, and I wanted to understand how easily we could solve it. I suspect this can be used to write simpler counting loops even in LLVM along the lines of: for (int i : seq(0, v.size())) { ... }; As part of this, I had to fix the lack of a proxy object returned from the operator[] in our iterator facade. Differential Revision: http://reviews.llvm.org/D17870 llvm-svn: 269390
* [ADT] Add drop_front method to ArrayRefReid Kleckner2016-05-031-0/+7
| | | | | | | | We have it for StringRef but not ArrayRef, and ArrayRef has drop_back, so I see no reason it shouldn't have drop_front. Splitting this out of a change that I have that will use this funcitonality. llvm-svn: 268434
* Add a CachedHash structure.Rafael Espindola2016-04-211-0/+49
| | | | | | | | | | | | | A DenseMap doesn't store the hashes, so it needs to recompute them when the table is resized. In some applications the hashing cost is noticeable. That is the case for example in lld for symbol names (StringRef). This patch adds a templated structure that can wraps any value that can go in a DenseMap and caches the hash. llvm-svn: 266981
OpenPOWER on IntegriCloud