LLVM  14.0.0git
STLExtras.h
Go to the documentation of this file.
1 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains some templates that are useful if you are working with the
10 // STL at all.
11 //
12 // No library is required when using these functions.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_ADT_STLEXTRAS_H
17 #define LLVM_ADT_STLEXTRAS_H
18 
19 #include "llvm/ADT/identity.h"
20 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/iterator.h"
25 #include "llvm/Config/abi-breaking.h"
27 #include <algorithm>
28 #include <cassert>
29 #include <cstddef>
30 #include <cstdint>
31 #include <cstdlib>
32 #include <functional>
33 #include <initializer_list>
34 #include <iterator>
35 #include <limits>
36 #include <memory>
37 #include <tuple>
38 #include <type_traits>
39 #include <utility>
40 
41 #ifdef EXPENSIVE_CHECKS
42 #include <random> // for std::mt19937
43 #endif
44 
45 namespace llvm {
46 
47 // Only used by compiler if both template types are the same. Useful when
48 // using SFINAE to test for the existence of member functions.
49 template <typename T, T> struct SameType;
50 
51 namespace detail {
52 
53 template <typename RangeT>
54 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
55 
56 template <typename RangeT>
57 using ValueOfRange = typename std::remove_reference<decltype(
58  *std::begin(std::declval<RangeT &>()))>::type;
59 
60 } // end namespace detail
61 
62 //===----------------------------------------------------------------------===//
63 // Extra additions to <type_traits>
64 //===----------------------------------------------------------------------===//
65 
66 template <typename T> struct make_const_ptr {
67  using type =
69 };
70 
71 template <typename T> struct make_const_ref {
72  using type = typename std::add_lvalue_reference<
74 };
75 
76 namespace detail {
77 template <typename...> using void_t = void;
78 template <class, template <class...> class Op, class... Args> struct detector {
79  using value_t = std::false_type;
80 };
81 template <template <class...> class Op, class... Args>
82 struct detector<void_t<Op<Args...>>, Op, Args...> {
83  using value_t = std::true_type;
84 };
85 } // end namespace detail
86 
87 /// Detects if a given trait holds for some set of arguments 'Args'.
88 /// For example, the given trait could be used to detect if a given type
89 /// has a copy assignment operator:
90 /// template<class T>
91 /// using has_copy_assign_t = decltype(std::declval<T&>()
92 /// = std::declval<const T&>());
93 /// bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;
94 template <template <class...> class Op, class... Args>
95 using is_detected = typename detail::detector<void, Op, Args...>::value_t;
96 
97 namespace detail {
98 template <typename Callable, typename... Args>
99 using is_invocable =
100  decltype(std::declval<Callable &>()(std::declval<Args>()...));
101 } // namespace detail
102 
103 /// Check if a Callable type can be invoked with the given set of arg types.
104 template <typename Callable, typename... Args>
106 
107 /// This class provides various trait information about a callable object.
108 /// * To access the number of arguments: Traits::num_args
109 /// * To access the type of an argument: Traits::arg_t<Index>
110 /// * To access the type of the result: Traits::result_t
111 template <typename T, bool isClass = std::is_class<T>::value>
112 struct function_traits : public function_traits<decltype(&T::operator())> {};
113 
114 /// Overload for class function types.
115 template <typename ClassType, typename ReturnType, typename... Args>
116 struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {
117  /// The number of arguments to this function.
118  enum { num_args = sizeof...(Args) };
119 
120  /// The result type of this function.
122 
123  /// The type of an argument to this function.
124  template <size_t Index>
125  using arg_t = typename std::tuple_element<Index, std::tuple<Args...>>::type;
126 };
127 /// Overload for class function types.
128 template <typename ClassType, typename ReturnType, typename... Args>
129 struct function_traits<ReturnType (ClassType::*)(Args...), false>
130  : function_traits<ReturnType (ClassType::*)(Args...) const> {};
131 /// Overload for non-class function types.
132 template <typename ReturnType, typename... Args>
133 struct function_traits<ReturnType (*)(Args...), false> {
134  /// The number of arguments to this function.
135  enum { num_args = sizeof...(Args) };
136 
137  /// The result type of this function.
139 
140  /// The type of an argument to this function.
141  template <size_t i>
142  using arg_t = typename std::tuple_element<i, std::tuple<Args...>>::type;
143 };
144 /// Overload for non-class function type references.
145 template <typename ReturnType, typename... Args>
146 struct function_traits<ReturnType (&)(Args...), false>
147  : public function_traits<ReturnType (*)(Args...)> {};
148 
149 /// traits class for checking whether type T is one of any of the given
150 /// types in the variadic list.
151 template <typename T, typename... Ts>
153 
154 /// traits class for checking whether type T is a base class for all
155 /// the given types in the variadic list.
156 template <typename T, typename... Ts>
158 
159 namespace detail {
160 template <typename T, typename... Us> struct TypesAreDistinct;
161 template <typename T, typename... Us>
162 struct TypesAreDistinct
163  : std::integral_constant<bool, !is_one_of<T, Us...>::value &&
164  TypesAreDistinct<Us...>::value> {};
165 template <typename T> struct TypesAreDistinct<T> : std::true_type {};
166 } // namespace detail
167 
168 /// Determine if all types in Ts are distinct.
169 ///
170 /// Useful to statically assert when Ts is intended to describe a non-multi set
171 /// of types.
172 ///
173 /// Expensive (currently quadratic in sizeof(Ts...)), and so should only be
174 /// asserted once per instantiation of a type which requires it.
175 template <typename... Ts> struct TypesAreDistinct;
176 template <> struct TypesAreDistinct<> : std::true_type {};
177 template <typename... Ts>
178 struct TypesAreDistinct
179  : std::integral_constant<bool, detail::TypesAreDistinct<Ts...>::value> {};
180 
181 /// Find the first index where a type appears in a list of types.
182 ///
183 /// FirstIndexOfType<T, Us...>::value is the first index of T in Us.
184 ///
185 /// Typically only meaningful when it is otherwise statically known that the
186 /// type pack has no duplicate types. This should be guaranteed explicitly with
187 /// static_assert(TypesAreDistinct<Us...>::value).
188 ///
189 /// It is a compile-time error to instantiate when T is not present in Us, i.e.
190 /// if is_one_of<T, Us...>::value is false.
191 template <typename T, typename... Us> struct FirstIndexOfType;
192 template <typename T, typename U, typename... Us>
193 struct FirstIndexOfType<T, U, Us...>
194  : std::integral_constant<size_t, 1 + FirstIndexOfType<T, Us...>::value> {};
195 template <typename T, typename... Us>
196 struct FirstIndexOfType<T, T, Us...> : std::integral_constant<size_t, 0> {};
197 
198 /// Find the type at a given index in a list of types.
199 ///
200 /// TypeAtIndex<I, Ts...> is the type at index I in Ts.
201 template <size_t I, typename... Ts>
202 using TypeAtIndex = std::tuple_element_t<I, std::tuple<Ts...>>;
203 
204 //===----------------------------------------------------------------------===//
205 // Extra additions to <iterator>
206 //===----------------------------------------------------------------------===//
207 
208 namespace adl_detail {
209 
210 using std::begin;
211 
212 template <typename ContainerTy>
213 decltype(auto) adl_begin(ContainerTy &&container) {
214  return begin(std::forward<ContainerTy>(container));
215 }
216 
217 using std::end;
218 
219 template <typename ContainerTy>
220 decltype(auto) adl_end(ContainerTy &&container) {
221  return end(std::forward<ContainerTy>(container));
222 }
223 
224 using std::swap;
225 
226 template <typename T>
227 void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
228  std::declval<T>()))) {
229  swap(std::forward<T>(lhs), std::forward<T>(rhs));
230 }
231 
232 } // end namespace adl_detail
233 
234 template <typename ContainerTy>
235 decltype(auto) adl_begin(ContainerTy &&container) {
236  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
237 }
238 
239 template <typename ContainerTy>
240 decltype(auto) adl_end(ContainerTy &&container) {
241  return adl_detail::adl_end(std::forward<ContainerTy>(container));
242 }
243 
244 template <typename T>
245 void adl_swap(T &&lhs, T &&rhs) noexcept(
246  noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
247  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
248 }
249 
250 /// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
251 template <typename T>
252 constexpr bool empty(const T &RangeOrContainer) {
253  return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
254 }
255 
256 /// Returns true if the given container only contains a single element.
257 template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
258  auto B = std::begin(C), E = std::end(C);
259  return B != E && std::next(B) == E;
260 }
261 
262 /// Return a range covering \p RangeOrContainer with the first N elements
263 /// excluded.
264 template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) {
265  return make_range(std::next(adl_begin(RangeOrContainer), N),
266  adl_end(RangeOrContainer));
267 }
268 
269 // mapped_iterator - This is a simple iterator adapter that causes a function to
270 // be applied whenever operator* is invoked on the iterator.
271 
272 template <typename ItTy, typename FuncTy,
273  typename ReferenceTy =
274  decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
276  : public iterator_adaptor_base<
277  mapped_iterator<ItTy, FuncTy>, ItTy,
278  typename std::iterator_traits<ItTy>::iterator_category,
279  std::remove_reference_t<ReferenceTy>,
280  typename std::iterator_traits<ItTy>::difference_type,
281  std::remove_reference_t<ReferenceTy> *, ReferenceTy> {
282 public:
283  mapped_iterator(ItTy U, FuncTy F)
285 
286  ItTy getCurrent() { return this->I; }
287 
288  const FuncTy &getFunction() const { return F; }
289 
290  ReferenceTy operator*() const { return F(*this->I); }
291 
292 private:
293  FuncTy F;
294 };
295 
296 // map_iterator - Provide a convenient way to create mapped_iterators, just like
297 // make_pair is useful for creating pairs...
298 template <class ItTy, class FuncTy>
301 }
302 
303 template <class ContainerTy, class FuncTy>
304 auto map_range(ContainerTy &&C, FuncTy F) {
305  return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
306 }
307 
308 /// A base type of mapped iterator, that is useful for building derived
309 /// iterators that do not need/want to store the map function (as in
310 /// mapped_iterator). These iterators must simply provide a `mapElement` method
311 /// that defines how to map a value of the iterator to the provided reference
312 /// type.
313 template <typename DerivedT, typename ItTy, typename ReferenceTy>
315  : public iterator_adaptor_base<
316  DerivedT, ItTy,
317  typename std::iterator_traits<ItTy>::iterator_category,
318  std::remove_reference_t<ReferenceTy>,
319  typename std::iterator_traits<ItTy>::difference_type,
320  std::remove_reference_t<ReferenceTy> *, ReferenceTy> {
321 public:
323 
326 
327  ItTy getCurrent() { return this->I; }
328 
329  ReferenceTy operator*() const {
330  return static_cast<const DerivedT &>(*this).mapElement(*this->I);
331  }
332 };
333 
334 /// Helper to determine if type T has a member called rbegin().
335 template <typename Ty> class has_rbegin_impl {
336  using yes = char[1];
337  using no = char[2];
338 
339  template <typename Inner>
340  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
341 
342  template <typename>
343  static no& test(...);
344 
345 public:
346  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
347 };
348 
349 /// Metafunction to determine if T& or T has a member called rbegin().
350 template <typename Ty>
351 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
352 };
353 
354 // Returns an iterator_range over the given container which iterates in reverse.
355 // Note that the container must have rbegin()/rend() methods for this to work.
356 template <typename ContainerTy>
357 auto reverse(ContainerTy &&C,
358  std::enable_if_t<has_rbegin<ContainerTy>::value> * = nullptr) {
359  return make_range(C.rbegin(), C.rend());
360 }
361 
362 // Returns an iterator_range over the given container which iterates in reverse.
363 // Note that the container must have begin()/end() methods which return
364 // bidirectional iterators for this to work.
365 template <typename ContainerTy>
366 auto reverse(ContainerTy &&C,
367  std::enable_if_t<!has_rbegin<ContainerTy>::value> * = nullptr) {
368  return make_range(std::make_reverse_iterator(std::end(C)),
369  std::make_reverse_iterator(std::begin(C)));
370 }
371 
372 /// An iterator adaptor that filters the elements of given inner iterators.
373 ///
374 /// The predicate parameter should be a callable object that accepts the wrapped
375 /// iterator's reference type and returns a bool. When incrementing or
376 /// decrementing the iterator, it will call the predicate on each element and
377 /// skip any where it returns false.
378 ///
379 /// \code
380 /// int A[] = { 1, 2, 3, 4 };
381 /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
382 /// // R contains { 1, 3 }.
383 /// \endcode
384 ///
385 /// Note: filter_iterator_base implements support for forward iteration.
386 /// filter_iterator_impl exists to provide support for bidirectional iteration,
387 /// conditional on whether the wrapped iterator supports it.
388 template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
390  : public iterator_adaptor_base<
391  filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
392  WrappedIteratorT,
393  typename std::common_type<
394  IterTag, typename std::iterator_traits<
395  WrappedIteratorT>::iterator_category>::type> {
396  using BaseT = typename filter_iterator_base::iterator_adaptor_base;
397 
398 protected:
401 
402  void findNextValid() {
403  while (this->I != End && !Pred(*this->I))
404  BaseT::operator++();
405  }
406 
407  // Construct the iterator. The begin iterator needs to know where the end
408  // is, so that it can properly stop when it gets there. The end iterator only
409  // needs the predicate to support bidirectional iteration.
412  : BaseT(Begin), End(End), Pred(Pred) {
413  findNextValid();
414  }
415 
416 public:
417  using BaseT::operator++;
418 
420  BaseT::operator++();
421  findNextValid();
422  return *this;
423  }
424 };
425 
426 /// Specialization of filter_iterator_base for forward iteration only.
427 template <typename WrappedIteratorT, typename PredicateT,
428  typename IterTag = std::forward_iterator_tag>
430  : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
431 public:
435 };
436 
437 /// Specialization of filter_iterator_base for bidirectional iteration.
438 template <typename WrappedIteratorT, typename PredicateT>
440  std::bidirectional_iterator_tag>
441  : public filter_iterator_base<WrappedIteratorT, PredicateT,
442  std::bidirectional_iterator_tag> {
443  using BaseT = typename filter_iterator_impl::filter_iterator_base;
444 
445  void findPrevValid() {
446  while (!this->Pred(*this->I))
447  BaseT::operator--();
448  }
449 
450 public:
451  using BaseT::operator--;
452 
455  : BaseT(Begin, End, Pred) {}
456 
458  BaseT::operator--();
459  findPrevValid();
460  return *this;
461  }
462 };
463 
464 namespace detail {
465 
466 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
467  using type = std::forward_iterator_tag;
468 };
469 
470 template <> struct fwd_or_bidi_tag_impl<true> {
471  using type = std::bidirectional_iterator_tag;
472 };
473 
474 /// Helper which sets its type member to forward_iterator_tag if the category
475 /// of \p IterT does not derive from bidirectional_iterator_tag, and to
476 /// bidirectional_iterator_tag otherwise.
477 template <typename IterT> struct fwd_or_bidi_tag {
478  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
479  std::bidirectional_iterator_tag,
480  typename std::iterator_traits<IterT>::iterator_category>::value>::type;
481 };
482 
483 } // namespace detail
484 
485 /// Defines filter_iterator to a suitable specialization of
486 /// filter_iterator_impl, based on the underlying iterator's category.
487 template <typename WrappedIteratorT, typename PredicateT>
491 
492 /// Convenience function that takes a range of elements and a predicate,
493 /// and return a new filter_iterator range.
494 ///
495 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
496 /// lifetime of that temporary is not kept by the returned range object, and the
497 /// temporary is going to be dropped on the floor after the make_iterator_range
498 /// full expression that contains this function call.
499 template <typename RangeT, typename PredicateT>
501 make_filter_range(RangeT &&Range, PredicateT Pred) {
502  using FilterIteratorT =
504  return make_range(
505  FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
506  std::end(std::forward<RangeT>(Range)), Pred),
507  FilterIteratorT(std::end(std::forward<RangeT>(Range)),
508  std::end(std::forward<RangeT>(Range)), Pred));
509 }
510 
511 /// A pseudo-iterator adaptor that is designed to implement "early increment"
512 /// style loops.
513 ///
514 /// This is *not a normal iterator* and should almost never be used directly. It
515 /// is intended primarily to be used with range based for loops and some range
516 /// algorithms.
517 ///
518 /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
519 /// somewhere between them. The constraints of these iterators are:
520 ///
521 /// - On construction or after being incremented, it is comparable and
522 /// dereferencable. It is *not* incrementable.
523 /// - After being dereferenced, it is neither comparable nor dereferencable, it
524 /// is only incrementable.
525 ///
526 /// This means you can only dereference the iterator once, and you can only
527 /// increment it once between dereferences.
528 template <typename WrappedIteratorT>
530  : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
531  WrappedIteratorT, std::input_iterator_tag> {
532  using BaseT = typename early_inc_iterator_impl::iterator_adaptor_base;
533 
534  using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
535 
536 protected:
537 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
538  bool IsEarlyIncremented = false;
539 #endif
540 
541 public:
543 
544  using BaseT::operator*;
545  decltype(*std::declval<WrappedIteratorT>()) operator*() {
546 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
547  assert(!IsEarlyIncremented && "Cannot dereference twice!");
548  IsEarlyIncremented = true;
549 #endif
550  return *(this->I)++;
551  }
552 
553  using BaseT::operator++;
555 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
556  assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
557  IsEarlyIncremented = false;
558 #endif
559  return *this;
560  }
561 
563  const early_inc_iterator_impl &RHS) {
564 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
565  assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!");
566 #endif
567  return (const BaseT &)LHS == (const BaseT &)RHS;
568  }
569 };
570 
571 /// Make a range that does early increment to allow mutation of the underlying
572 /// range without disrupting iteration.
573 ///
574 /// The underlying iterator will be incremented immediately after it is
575 /// dereferenced, allowing deletion of the current node or insertion of nodes to
576 /// not disrupt iteration provided they do not invalidate the *next* iterator --
577 /// the current iterator can be invalidated.
578 ///
579 /// This requires a very exact pattern of use that is only really suitable to
580 /// range based for loops and other range algorithms that explicitly guarantee
581 /// to dereference exactly once each element, and to increment exactly once each
582 /// element.
583 template <typename RangeT>
584 iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
585 make_early_inc_range(RangeT &&Range) {
586  using EarlyIncIteratorT =
588  return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
589  EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
590 }
591 
592 // forward declarations required by zip_shortest/zip_first/zip_longest
593 template <typename R, typename UnaryPredicate>
594 bool all_of(R &&range, UnaryPredicate P);
595 template <typename R, typename UnaryPredicate>
596 bool any_of(R &&range, UnaryPredicate P);
597 
598 namespace detail {
599 
600 using std::declval;
601 
602 // We have to alias this since inlining the actual type at the usage site
603 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
604 template<typename... Iters> struct ZipTupleType {
605  using type = std::tuple<decltype(*declval<Iters>())...>;
606 };
607 
608 template <typename ZipType, typename... Iters>
610  ZipType, typename std::common_type<std::bidirectional_iterator_tag,
611  typename std::iterator_traits<
612  Iters>::iterator_category...>::type,
613  // ^ TODO: Implement random access methods.
614  typename ZipTupleType<Iters...>::type,
615  typename std::iterator_traits<typename std::tuple_element<
616  0, std::tuple<Iters...>>::type>::difference_type,
617  // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
618  // inner iterators have the same difference_type. It would fail if, for
619  // instance, the second field's difference_type were non-numeric while the
620  // first is.
621  typename ZipTupleType<Iters...>::type *,
622  typename ZipTupleType<Iters...>::type>;
623 
624 template <typename ZipType, typename... Iters>
625 struct zip_common : public zip_traits<ZipType, Iters...> {
626  using Base = zip_traits<ZipType, Iters...>;
627  using value_type = typename Base::value_type;
628 
629  std::tuple<Iters...> iterators;
630 
631 protected:
632  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
633  return value_type(*std::get<Ns>(iterators)...);
634  }
635 
636  template <size_t... Ns>
637  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
638  return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
639  }
640 
641  template <size_t... Ns>
642  decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
643  return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
644  }
645 
646  template <size_t... Ns>
647  bool test_all_equals(const zip_common &other,
648  std::index_sequence<Ns...>) const {
649  return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) ==
650  std::get<Ns>(other.iterators)...},
651  identity<bool>{});
652  }
653 
654 public:
655  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
656 
658  return deref(std::index_sequence_for<Iters...>{});
659  }
660 
661  ZipType &operator++() {
662  iterators = tup_inc(std::index_sequence_for<Iters...>{});
663  return *reinterpret_cast<ZipType *>(this);
664  }
665 
666  ZipType &operator--() {
667  static_assert(Base::IsBidirectional,
668  "All inner iterators must be at least bidirectional.");
669  iterators = tup_dec(std::index_sequence_for<Iters...>{});
670  return *reinterpret_cast<ZipType *>(this);
671  }
672 
673  /// Return true if all the iterator are matching `other`'s iterators.
674  bool all_equals(zip_common &other) {
675  return test_all_equals(other, std::index_sequence_for<Iters...>{});
676  }
677 };
678 
679 template <typename... Iters>
680 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
681  using Base = zip_common<zip_first<Iters...>, Iters...>;
682 
683  bool operator==(const zip_first<Iters...> &other) const {
684  return std::get<0>(this->iterators) == std::get<0>(other.iterators);
685  }
686 
687  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
688 };
689 
690 template <typename... Iters>
691 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
692  template <size_t... Ns>
693  bool test(const zip_shortest<Iters...> &other,
694  std::index_sequence<Ns...>) const {
695  return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
696  std::get<Ns>(other.iterators)...},
697  identity<bool>{});
698  }
699 
700 public:
701  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
702 
703  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
704 
705  bool operator==(const zip_shortest<Iters...> &other) const {
706  return !test(other, std::index_sequence_for<Iters...>{});
707  }
708 };
709 
710 template <template <typename...> class ItType, typename... Args> class zippy {
711 public:
712  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
713  using iterator_category = typename iterator::iterator_category;
714  using value_type = typename iterator::value_type;
715  using difference_type = typename iterator::difference_type;
716  using pointer = typename iterator::pointer;
717  using reference = typename iterator::reference;
718 
719 private:
720  std::tuple<Args...> ts;
721 
722  template <size_t... Ns>
723  iterator begin_impl(std::index_sequence<Ns...>) const {
724  return iterator(std::begin(std::get<Ns>(ts))...);
725  }
726  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
727  return iterator(std::end(std::get<Ns>(ts))...);
728  }
729 
730 public:
731  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
732 
733  iterator begin() const {
734  return begin_impl(std::index_sequence_for<Args...>{});
735  }
736  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
737 };
738 
739 } // end namespace detail
740 
741 /// zip iterator for two or more iteratable types.
742 template <typename T, typename U, typename... Args>
744  Args &&... args) {
745  return detail::zippy<detail::zip_shortest, T, U, Args...>(
746  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
747 }
748 
749 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
750 /// be the shortest.
751 template <typename T, typename U, typename... Args>
753  Args &&... args) {
754  return detail::zippy<detail::zip_first, T, U, Args...>(
755  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
756 }
757 
758 namespace detail {
759 template <typename Iter>
760 Iter next_or_end(const Iter &I, const Iter &End) {
761  if (I == End)
762  return End;
763  return std::next(I);
764 }
765 
766 template <typename Iter>
767 auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
768  std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
769  if (I == End)
770  return None;
771  return *I;
772 }
773 
774 template <typename Iter> struct ZipLongestItemType {
775  using type =
776  llvm::Optional<typename std::remove_const<typename std::remove_reference<
777  decltype(*std::declval<Iter>())>::type>::type>;
778 };
779 
780 template <typename... Iters> struct ZipLongestTupleType {
782 };
783 
784 template <typename... Iters>
786  : public iterator_facade_base<
787  zip_longest_iterator<Iters...>,
788  typename std::common_type<
789  std::forward_iterator_tag,
790  typename std::iterator_traits<Iters>::iterator_category...>::type,
791  typename ZipLongestTupleType<Iters...>::type,
792  typename std::iterator_traits<typename std::tuple_element<
793  0, std::tuple<Iters...>>::type>::difference_type,
794  typename ZipLongestTupleType<Iters...>::type *,
795  typename ZipLongestTupleType<Iters...>::type> {
796 public:
797  using value_type = typename ZipLongestTupleType<Iters...>::type;
798 
799 private:
800  std::tuple<Iters...> iterators;
801  std::tuple<Iters...> end_iterators;
802 
803  template <size_t... Ns>
804  bool test(const zip_longest_iterator<Iters...> &other,
805  std::index_sequence<Ns...>) const {
806  return llvm::any_of(
807  std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
808  std::get<Ns>(other.iterators)...},
809  identity<bool>{});
810  }
811 
812  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
813  return value_type(
814  deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
815  }
816 
817  template <size_t... Ns>
818  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
819  return std::tuple<Iters...>(
820  next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
821  }
822 
823 public:
824  zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
825  : iterators(std::forward<Iters>(ts.first)...),
826  end_iterators(std::forward<Iters>(ts.second)...) {}
827 
829  return deref(std::index_sequence_for<Iters...>{});
830  }
831 
833  iterators = tup_inc(std::index_sequence_for<Iters...>{});
834  return *this;
835  }
836 
837  bool operator==(const zip_longest_iterator<Iters...> &other) const {
838  return !test(other, std::index_sequence_for<Iters...>{});
839  }
840 };
841 
842 template <typename... Args> class zip_longest_range {
843 public:
844  using iterator =
849  using pointer = typename iterator::pointer;
850  using reference = typename iterator::reference;
851 
852 private:
853  std::tuple<Args...> ts;
854 
855  template <size_t... Ns>
856  iterator begin_impl(std::index_sequence<Ns...>) const {
857  return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
858  adl_end(std::get<Ns>(ts)))...);
859  }
860 
861  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
862  return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
863  adl_end(std::get<Ns>(ts)))...);
864  }
865 
866 public:
867  zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
868 
869  iterator begin() const {
870  return begin_impl(std::index_sequence_for<Args...>{});
871  }
872  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
873 };
874 } // namespace detail
875 
876 /// Iterate over two or more iterators at the same time. Iteration continues
877 /// until all iterators reach the end. The llvm::Optional only contains a value
878 /// if the iterator has not reached the end.
879 template <typename T, typename U, typename... Args>
881  Args &&... args) {
882  return detail::zip_longest_range<T, U, Args...>(
883  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
884 }
885 
886 /// Iterator wrapper that concatenates sequences together.
887 ///
888 /// This can concatenate different iterators, even with different types, into
889 /// a single iterator provided the value types of all the concatenated
890 /// iterators expose `reference` and `pointer` types that can be converted to
891 /// `ValueT &` and `ValueT *` respectively. It doesn't support more
892 /// interesting/customized pointer or reference types.
893 ///
894 /// Currently this only supports forward or higher iterator categories as
895 /// inputs and always exposes a forward iterator interface.
896 template <typename ValueT, typename... IterTs>
898  : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
899  std::forward_iterator_tag, ValueT> {
900  using BaseT = typename concat_iterator::iterator_facade_base;
901 
902  /// We store both the current and end iterators for each concatenated
903  /// sequence in a tuple of pairs.
904  ///
905  /// Note that something like iterator_range seems nice at first here, but the
906  /// range properties are of little benefit and end up getting in the way
907  /// because we need to do mutation on the current iterators.
908  std::tuple<IterTs...> Begins;
909  std::tuple<IterTs...> Ends;
910 
911  /// Attempts to increment a specific iterator.
912  ///
913  /// Returns true if it was able to increment the iterator. Returns false if
914  /// the iterator is already at the end iterator.
915  template <size_t Index> bool incrementHelper() {
916  auto &Begin = std::get<Index>(Begins);
917  auto &End = std::get<Index>(Ends);
918  if (Begin == End)
919  return false;
920 
921  ++Begin;
922  return true;
923  }
924 
925  /// Increments the first non-end iterator.
926  ///
927  /// It is an error to call this with all iterators at the end.
928  template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
929  // Build a sequence of functions to increment each iterator if possible.
930  bool (concat_iterator::*IncrementHelperFns[])() = {
931  &concat_iterator::incrementHelper<Ns>...};
932 
933  // Loop over them, and stop as soon as we succeed at incrementing one.
934  for (auto &IncrementHelperFn : IncrementHelperFns)
935  if ((this->*IncrementHelperFn)())
936  return;
937 
938  llvm_unreachable("Attempted to increment an end concat iterator!");
939  }
940 
941  /// Returns null if the specified iterator is at the end. Otherwise,
942  /// dereferences the iterator and returns the address of the resulting
943  /// reference.
944  template <size_t Index> ValueT *getHelper() const {
945  auto &Begin = std::get<Index>(Begins);
946  auto &End = std::get<Index>(Ends);
947  if (Begin == End)
948  return nullptr;
949 
950  return &*Begin;
951  }
952 
953  /// Finds the first non-end iterator, dereferences, and returns the resulting
954  /// reference.
955  ///
956  /// It is an error to call this with all iterators at the end.
957  template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
958  // Build a sequence of functions to get from iterator if possible.
959  ValueT *(concat_iterator::*GetHelperFns[])() const = {
960  &concat_iterator::getHelper<Ns>...};
961 
962  // Loop over them, and return the first result we find.
963  for (auto &GetHelperFn : GetHelperFns)
964  if (ValueT *P = (this->*GetHelperFn)())
965  return *P;
966 
967  llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
968  }
969 
970 public:
971  /// Constructs an iterator from a sequence of ranges.
972  ///
973  /// We need the full range to know how to switch between each of the
974  /// iterators.
975  template <typename... RangeTs>
976  explicit concat_iterator(RangeTs &&... Ranges)
977  : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
978 
979  using BaseT::operator++;
980 
982  increment(std::index_sequence_for<IterTs...>());
983  return *this;
984  }
985 
986  ValueT &operator*() const {
987  return get(std::index_sequence_for<IterTs...>());
988  }
989 
990  bool operator==(const concat_iterator &RHS) const {
991  return Begins == RHS.Begins && Ends == RHS.Ends;
992  }
993 };
994 
995 namespace detail {
996 
997 /// Helper to store a sequence of ranges being concatenated and access them.
998 ///
999 /// This is designed to facilitate providing actual storage when temporaries
1000 /// are passed into the constructor such that we can use it as part of range
1001 /// based for loops.
1002 template <typename ValueT, typename... RangeTs> class concat_range {
1003 public:
1004  using iterator =
1006  decltype(std::begin(std::declval<RangeTs &>()))...>;
1007 
1008 private:
1009  std::tuple<RangeTs...> Ranges;
1010 
1011  template <size_t... Ns>
1012  iterator begin_impl(std::index_sequence<Ns...>) {
1013  return iterator(std::get<Ns>(Ranges)...);
1014  }
1015  template <size_t... Ns>
1016  iterator begin_impl(std::index_sequence<Ns...>) const {
1017  return iterator(std::get<Ns>(Ranges)...);
1018  }
1019  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
1020  return iterator(make_range(std::end(std::get<Ns>(Ranges)),
1021  std::end(std::get<Ns>(Ranges)))...);
1022  }
1023  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
1024  return iterator(make_range(std::end(std::get<Ns>(Ranges)),
1025  std::end(std::get<Ns>(Ranges)))...);
1026  }
1027 
1028 public:
1029  concat_range(RangeTs &&... Ranges)
1030  : Ranges(std::forward<RangeTs>(Ranges)...) {}
1031 
1033  return begin_impl(std::index_sequence_for<RangeTs...>{});
1034  }
1035  iterator begin() const {
1036  return begin_impl(std::index_sequence_for<RangeTs...>{});
1037  }
1039  return end_impl(std::index_sequence_for<RangeTs...>{});
1040  }
1041  iterator end() const {
1042  return end_impl(std::index_sequence_for<RangeTs...>{});
1043  }
1044 };
1045 
1046 } // end namespace detail
1047 
1048 /// Concatenated range across two or more ranges.
1049 ///
1050 /// The desired value type must be explicitly specified.
1051 template <typename ValueT, typename... RangeTs>
1052 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
1053  static_assert(sizeof...(RangeTs) > 1,
1054  "Need more than one range to concatenate!");
1055  return detail::concat_range<ValueT, RangeTs...>(
1056  std::forward<RangeTs>(Ranges)...);
1057 }
1058 
1059 /// A utility class used to implement an iterator that contains some base object
1060 /// and an index. The iterator moves the index but keeps the base constant.
1061 template <typename DerivedT, typename BaseT, typename T,
1062  typename PointerT = T *, typename ReferenceT = T &>
1064  : public llvm::iterator_facade_base<DerivedT,
1065  std::random_access_iterator_tag, T,
1066  std::ptrdiff_t, PointerT, ReferenceT> {
1067 public:
1069  assert(base == rhs.base && "incompatible iterators");
1070  return index - rhs.index;
1071  }
1072  bool operator==(const indexed_accessor_iterator &rhs) const {
1073  return base == rhs.base && index == rhs.index;
1074  }
1075  bool operator<(const indexed_accessor_iterator &rhs) const {
1076  assert(base == rhs.base && "incompatible iterators");
1077  return index < rhs.index;
1078  }
1079 
1080  DerivedT &operator+=(ptrdiff_t offset) {
1081  this->index += offset;
1082  return static_cast<DerivedT &>(*this);
1083  }
1084  DerivedT &operator-=(ptrdiff_t offset) {
1085  this->index -= offset;
1086  return static_cast<DerivedT &>(*this);
1087  }
1088 
1089  /// Returns the current index of the iterator.
1090  ptrdiff_t getIndex() const { return index; }
1091 
1092  /// Returns the current base of the iterator.
1093  const BaseT &getBase() const { return base; }
1094 
1095 protected:
1097  : base(base), index(index) {}
1100 };
1101 
1102 namespace detail {
1103 /// The class represents the base of a range of indexed_accessor_iterators. It
1104 /// provides support for many different range functionalities, e.g.
1105 /// drop_front/slice/etc.. Derived range classes must implement the following
1106 /// static methods:
1107 /// * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
1108 /// - Dereference an iterator pointing to the base object at the given
1109 /// index.
1110 /// * BaseT offset_base(const BaseT &base, ptrdiff_t index)
1111 /// - Return a new base that is offset from the provide base by 'index'
1112 /// elements.
1113 template <typename DerivedT, typename BaseT, typename T,
1114  typename PointerT = T *, typename ReferenceT = T &>
1116 public:
1118 
1119  /// An iterator element of this range.
1120  class iterator : public indexed_accessor_iterator<iterator, BaseT, T,
1121  PointerT, ReferenceT> {
1122  public:
1123  // Index into this iterator, invoking a static method on the derived type.
1124  ReferenceT operator*() const {
1125  return DerivedT::dereference_iterator(this->getBase(), this->getIndex());
1126  }
1127 
1128  private:
1129  iterator(BaseT owner, ptrdiff_t curIndex)
1130  : iterator::indexed_accessor_iterator(owner, curIndex) {}
1131 
1132  /// Allow access to the constructor.
1133  friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT,
1134  ReferenceT>;
1135  };
1136 
1138  : base(offset_base(begin.getBase(), begin.getIndex())),
1139  count(end.getIndex() - begin.getIndex()) {}
1141  : indexed_accessor_range_base(range.begin(), range.end()) {}
1143  : base(base), count(count) {}
1144 
1145  iterator begin() const { return iterator(base, 0); }
1146  iterator end() const { return iterator(base, count); }
1147  ReferenceT operator[](size_t Index) const {
1148  assert(Index < size() && "invalid index for value range");
1149  return DerivedT::dereference_iterator(base, static_cast<ptrdiff_t>(Index));
1150  }
1151  ReferenceT front() const {
1152  assert(!empty() && "expected non-empty range");
1153  return (*this)[0];
1154  }
1155  ReferenceT back() const {
1156  assert(!empty() && "expected non-empty range");
1157  return (*this)[size() - 1];
1158  }
1159 
1160  /// Compare this range with another.
1161  template <typename OtherT> bool operator==(const OtherT &other) const {
1162  return size() ==
1163  static_cast<size_t>(std::distance(other.begin(), other.end())) &&
1164  std::equal(begin(), end(), other.begin());
1165  }
1166  template <typename OtherT> bool operator!=(const OtherT &other) const {
1167  return !(*this == other);
1168  }
1169 
1170  /// Return the size of this range.
1171  size_t size() const { return count; }
1172 
1173  /// Return if the range is empty.
1174  bool empty() const { return size() == 0; }
1175 
1176  /// Drop the first N elements, and keep M elements.
1177  DerivedT slice(size_t n, size_t m) const {
1178  assert(n + m <= size() && "invalid size specifiers");
1179  return DerivedT(offset_base(base, n), m);
1180  }
1181 
1182  /// Drop the first n elements.
1183  DerivedT drop_front(size_t n = 1) const {
1184  assert(size() >= n && "Dropping more elements than exist");
1185  return slice(n, size() - n);
1186  }
1187  /// Drop the last n elements.
1188  DerivedT drop_back(size_t n = 1) const {
1189  assert(size() >= n && "Dropping more elements than exist");
1190  return DerivedT(base, size() - n);
1191  }
1192 
1193  /// Take the first n elements.
1194  DerivedT take_front(size_t n = 1) const {
1195  return n < size() ? drop_back(size() - n)
1196  : static_cast<const DerivedT &>(*this);
1197  }
1198 
1199  /// Take the last n elements.
1200  DerivedT take_back(size_t n = 1) const {
1201  return n < size() ? drop_front(size() - n)
1202  : static_cast<const DerivedT &>(*this);
1203  }
1204 
1205  /// Allow conversion to any type accepting an iterator_range.
1206  template <typename RangeT, typename = std::enable_if_t<std::is_constructible<
1207  RangeT, iterator_range<iterator>>::value>>
1208  operator RangeT() const {
1209  return RangeT(iterator_range<iterator>(*this));
1210  }
1211 
1212  /// Returns the base of this range.
1213  const BaseT &getBase() const { return base; }
1214 
1215 private:
1216  /// Offset the given base by the given amount.
1217  static BaseT offset_base(const BaseT &base, size_t n) {
1218  return n == 0 ? base : DerivedT::offset_base(base, n);
1219  }
1220 
1221 protected:
1225  operator=(const indexed_accessor_range_base &) = default;
1226 
1227  /// The base that owns the provided range of values.
1229  /// The size from the owning range.
1231 };
1232 } // end namespace detail
1233 
1234 /// This class provides an implementation of a range of
1235 /// indexed_accessor_iterators where the base is not indexable. Ranges with
1236 /// bases that are offsetable should derive from indexed_accessor_range_base
1237 /// instead. Derived range classes are expected to implement the following
1238 /// static method:
1239 /// * ReferenceT dereference(const BaseT &base, ptrdiff_t index)
1240 /// - Dereference an iterator pointing to a parent base at the given index.
1241 template <typename DerivedT, typename BaseT, typename T,
1242  typename PointerT = T *, typename ReferenceT = T &>
1245  DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1246 public:
1248  : detail::indexed_accessor_range_base<
1249  DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
1250  std::make_pair(base, startIndex), count) {}
1252  DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
1253  ReferenceT>::indexed_accessor_range_base;
1254 
1255  /// Returns the current base of the range.
1256  const BaseT &getBase() const { return this->base.first; }
1257 
1258  /// Returns the current start index of the range.
1259  ptrdiff_t getStartIndex() const { return this->base.second; }
1260 
1261  /// See `detail::indexed_accessor_range_base` for details.
1262  static std::pair<BaseT, ptrdiff_t>
1263  offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
1264  // We encode the internal base as a pair of the derived base and a start
1265  // index into the derived base.
1266  return std::make_pair(base.first, base.second + index);
1267  }
1268  /// See `detail::indexed_accessor_range_base` for details.
1269  static ReferenceT
1270  dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base,
1271  ptrdiff_t index) {
1272  return DerivedT::dereference(base.first, base.second + index);
1273  }
1274 };
1275 
1276 namespace detail {
1277 /// Return a reference to the first or second member of a reference. Otherwise,
1278 /// return a copy of the member of a temporary.
1279 ///
1280 /// When passing a range whose iterators return values instead of references,
1281 /// the reference must be dropped from `decltype((elt.first))`, which will
1282 /// always be a reference, to avoid returning a reference to a temporary.
1283 template <typename EltTy, typename FirstTy> class first_or_second_type {
1284 public:
1285  using type =
1286  typename std::conditional_t<std::is_reference<EltTy>::value, FirstTy,
1287  std::remove_reference_t<FirstTy>>;
1288 };
1289 } // end namespace detail
1290 
1291 /// Given a container of pairs, return a range over the first elements.
1292 template <typename ContainerTy> auto make_first_range(ContainerTy &&c) {
1293  using EltTy = decltype((*std::begin(c)));
1294  return llvm::map_range(std::forward<ContainerTy>(c),
1295  [](EltTy elt) -> typename detail::first_or_second_type<
1296  EltTy, decltype((elt.first))>::type {
1297  return elt.first;
1298  });
1299 }
1300 
1301 /// Given a container of pairs, return a range over the second elements.
1302 template <typename ContainerTy> auto make_second_range(ContainerTy &&c) {
1303  using EltTy = decltype((*std::begin(c)));
1304  return llvm::map_range(
1305  std::forward<ContainerTy>(c),
1306  [](EltTy elt) ->
1307  typename detail::first_or_second_type<EltTy,
1308  decltype((elt.second))>::type {
1309  return elt.second;
1310  });
1311 }
1312 
1313 //===----------------------------------------------------------------------===//
1314 // Extra additions to <utility>
1315 //===----------------------------------------------------------------------===//
1316 
1317 /// Function object to check whether the first component of a std::pair
1318 /// compares less than the first component of another std::pair.
1319 struct less_first {
1320  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1321  return std::less<>()(lhs.first, rhs.first);
1322  }
1323 };
1324 
1325 /// Function object to check whether the second component of a std::pair
1326 /// compares less than the second component of another std::pair.
1327 struct less_second {
1328  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1329  return std::less<>()(lhs.second, rhs.second);
1330  }
1331 };
1332 
1333 /// \brief Function object to apply a binary function to the first component of
1334 /// a std::pair.
1335 template<typename FuncTy>
1336 struct on_first {
1337  FuncTy func;
1338 
1339  template <typename T>
1340  decltype(auto) operator()(const T &lhs, const T &rhs) const {
1341  return func(lhs.first, rhs.first);
1342  }
1343 };
1344 
1345 /// Utility type to build an inheritance chain that makes it easy to rank
1346 /// overload candidates.
1347 template <int N> struct rank : rank<N - 1> {};
1348 template <> struct rank<0> {};
1349 
1350 /// traits class for checking whether type T is one of any of the given
1351 /// types in the variadic list.
1352 template <typename T, typename... Ts>
1354 
1355 /// traits class for checking whether type T is a base class for all
1356 /// the given types in the variadic list.
1357 template <typename T, typename... Ts>
1359 
1360 namespace detail {
1361 template <typename... Ts> struct Visitor;
1362 
1363 template <typename HeadT, typename... TailTs>
1364 struct Visitor<HeadT, TailTs...> : remove_cvref_t<HeadT>, Visitor<TailTs...> {
1365  explicit constexpr Visitor(HeadT &&Head, TailTs &&...Tail)
1366  : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)),
1367  Visitor<TailTs...>(std::forward<TailTs>(Tail)...) {}
1370 };
1371 
1372 template <typename HeadT> struct Visitor<HeadT> : remove_cvref_t<HeadT> {
1373  explicit constexpr Visitor(HeadT &&Head)
1374  : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)) {}
1376 };
1377 } // namespace detail
1378 
1379 /// Returns an opaquely-typed Callable object whose operator() overload set is
1380 /// the sum of the operator() overload sets of each CallableT in CallableTs.
1381 ///
1382 /// The type of the returned object derives from each CallableT in CallableTs.
1383 /// The returned object is constructed by invoking the appropriate copy or move
1384 /// constructor of each CallableT, as selected by overload resolution on the
1385 /// corresponding argument to makeVisitor.
1386 ///
1387 /// Example:
1388 ///
1389 /// \code
1390 /// auto visitor = makeVisitor([](auto) { return "unhandled type"; },
1391 /// [](int i) { return "int"; },
1392 /// [](std::string s) { return "str"; });
1393 /// auto a = visitor(42); // `a` is now "int".
1394 /// auto b = visitor("foo"); // `b` is now "str".
1395 /// auto c = visitor(3.14f); // `c` is now "unhandled type".
1396 /// \endcode
1397 ///
1398 /// Example of making a visitor with a lambda which captures a move-only type:
1399 ///
1400 /// \code
1401 /// std::unique_ptr<FooHandler> FH = /* ... */;
1402 /// auto visitor = makeVisitor(
1403 /// [FH{std::move(FH)}](Foo F) { return FH->handle(F); },
1404 /// [](int i) { return i; },
1405 /// [](std::string s) { return atoi(s); });
1406 /// \endcode
1407 template <typename... CallableTs>
1408 constexpr decltype(auto) makeVisitor(CallableTs &&...Callables) {
1409  return detail::Visitor<CallableTs...>(std::forward<CallableTs>(Callables)...);
1410 }
1411 
1412 //===----------------------------------------------------------------------===//
1413 // Extra additions for arrays
1414 //===----------------------------------------------------------------------===//
1415 
1416 // We have a copy here so that LLVM behaves the same when using different
1417 // standard libraries.
1418 template <class Iterator, class RNG>
1419 void shuffle(Iterator first, Iterator last, RNG &&g) {
1420  // It would be better to use a std::uniform_int_distribution,
1421  // but that would be stdlib dependent.
1422  typedef
1423  typename std::iterator_traits<Iterator>::difference_type difference_type;
1424  for (auto size = last - first; size > 1; ++first, (void)--size) {
1425  difference_type offset = g() % size;
1426  // Avoid self-assignment due to incorrect assertions in libstdc++
1427  // containers (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828).
1428  if (offset != difference_type(0))
1429  std::iter_swap(first, first + offset);
1430  }
1431 }
1432 
1433 /// Find the length of an array.
1434 template <class T, std::size_t N>
1435 constexpr inline size_t array_lengthof(T (&)[N]) {
1436  return N;
1437 }
1438 
1439 /// Adapt std::less<T> for array_pod_sort.
1440 template<typename T>
1441 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1442  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1443  *reinterpret_cast<const T*>(P2)))
1444  return -1;
1445  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1446  *reinterpret_cast<const T*>(P1)))
1447  return 1;
1448  return 0;
1449 }
1450 
1451 /// get_array_pod_sort_comparator - This is an internal helper function used to
1452 /// get type deduction of T right.
1453 template<typename T>
1455  (const void*, const void*) {
1456  return array_pod_sort_comparator<T>;
1457 }
1458 
1459 #ifdef EXPENSIVE_CHECKS
1460 namespace detail {
1461 
1462 inline unsigned presortShuffleEntropy() {
1463  static unsigned Result(std::random_device{}());
1464  return Result;
1465 }
1466 
1467 template <class IteratorTy>
1468 inline void presortShuffle(IteratorTy Start, IteratorTy End) {
1469  std::mt19937 Generator(presortShuffleEntropy());
1470  llvm::shuffle(Start, End, Generator);
1471 }
1472 
1473 } // end namespace detail
1474 #endif
1475 
1476 /// array_pod_sort - This sorts an array with the specified start and end
1477 /// extent. This is just like std::sort, except that it calls qsort instead of
1478 /// using an inlined template. qsort is slightly slower than std::sort, but
1479 /// most sorts are not performance critical in LLVM and std::sort has to be
1480 /// template instantiated for each type, leading to significant measured code
1481 /// bloat. This function should generally be used instead of std::sort where
1482 /// possible.
1483 ///
1484 /// This function assumes that you have simple POD-like types that can be
1485 /// compared with std::less and can be moved with memcpy. If this isn't true,
1486 /// you should use std::sort.
1487 ///
1488 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
1489 /// default to std::less.
1490 template<class IteratorTy>
1491 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1492  // Don't inefficiently call qsort with one element or trigger undefined
1493  // behavior with an empty sequence.
1494  auto NElts = End - Start;
1495  if (NElts <= 1) return;
1496 #ifdef EXPENSIVE_CHECKS
1497  detail::presortShuffle<IteratorTy>(Start, End);
1498 #endif
1499  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1500 }
1501 
1502 template <class IteratorTy>
1503 inline void array_pod_sort(
1504  IteratorTy Start, IteratorTy End,
1505  int (*Compare)(
1506  const typename std::iterator_traits<IteratorTy>::value_type *,
1507  const typename std::iterator_traits<IteratorTy>::value_type *)) {
1508  // Don't inefficiently call qsort with one element or trigger undefined
1509  // behavior with an empty sequence.
1510  auto NElts = End - Start;
1511  if (NElts <= 1) return;
1512 #ifdef EXPENSIVE_CHECKS
1513  detail::presortShuffle<IteratorTy>(Start, End);
1514 #endif
1515  qsort(&*Start, NElts, sizeof(*Start),
1516  reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1517 }
1518 
1519 namespace detail {
1520 template <typename T>
1521 // We can use qsort if the iterator type is a pointer and the underlying value
1522 // is trivially copyable.
1523 using sort_trivially_copyable = conjunction<
1524  std::is_pointer<T>,
1525  std::is_trivially_copyable<typename std::iterator_traits<T>::value_type>>;
1526 } // namespace detail
1527 
1528 // Provide wrappers to std::sort which shuffle the elements before sorting
1529 // to help uncover non-deterministic behavior (PR35135).
1530 template <typename IteratorTy,
1531  std::enable_if_t<!detail::sort_trivially_copyable<IteratorTy>::value,
1532  int> = 0>
1533 inline void sort(IteratorTy Start, IteratorTy End) {
1534 #ifdef EXPENSIVE_CHECKS
1535  detail::presortShuffle<IteratorTy>(Start, End);
1536 #endif
1537  std::sort(Start, End);
1538 }
1539 
1540 // Forward trivially copyable types to array_pod_sort. This avoids a large
1541 // amount of code bloat for a minor performance hit.
1542 template <typename IteratorTy,
1543  std::enable_if_t<detail::sort_trivially_copyable<IteratorTy>::value,
1544  int> = 0>
1545 inline void sort(IteratorTy Start, IteratorTy End) {
1546  array_pod_sort(Start, End);
1547 }
1548 
1549 template <typename Container> inline void sort(Container &&C) {
1551 }
1552 
1553 template <typename IteratorTy, typename Compare>
1554 inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1555 #ifdef EXPENSIVE_CHECKS
1556  detail::presortShuffle<IteratorTy>(Start, End);
1557 #endif
1558  std::sort(Start, End, Comp);
1559 }
1560 
1561 template <typename Container, typename Compare>
1562 inline void sort(Container &&C, Compare Comp) {
1563  llvm::sort(adl_begin(C), adl_end(C), Comp);
1564 }
1565 
1566 //===----------------------------------------------------------------------===//
1567 // Extra additions to <algorithm>
1568 //===----------------------------------------------------------------------===//
1569 
1570 /// Get the size of a range. This is a wrapper function around std::distance
1571 /// which is only enabled when the operation is O(1).
1572 template <typename R>
1573 auto size(R &&Range,
1574  std::enable_if_t<
1575  std::is_base_of<std::random_access_iterator_tag,
1576  typename std::iterator_traits<decltype(
1577  Range.begin())>::iterator_category>::value,
1578  void> * = nullptr) {
1579  return std::distance(Range.begin(), Range.end());
1580 }
1581 
1582 /// Provide wrappers to std::for_each which take ranges instead of having to
1583 /// pass begin/end explicitly.
1584 template <typename R, typename UnaryFunction>
1585 UnaryFunction for_each(R &&Range, UnaryFunction F) {
1586  return std::for_each(adl_begin(Range), adl_end(Range), F);
1587 }
1588 
1589 /// Provide wrappers to std::all_of which take ranges instead of having to pass
1590 /// begin/end explicitly.
1591 template <typename R, typename UnaryPredicate>
1592 bool all_of(R &&Range, UnaryPredicate P) {
1593  return std::all_of(adl_begin(Range), adl_end(Range), P);
1594 }
1595 
1596 /// Provide wrappers to std::any_of which take ranges instead of having to pass
1597 /// begin/end explicitly.
1598 template <typename R, typename UnaryPredicate>
1599 bool any_of(R &&Range, UnaryPredicate P) {
1600  return std::any_of(adl_begin(Range), adl_end(Range), P);
1601 }
1602 
1603 /// Provide wrappers to std::none_of which take ranges instead of having to pass
1604 /// begin/end explicitly.
1605 template <typename R, typename UnaryPredicate>
1606 bool none_of(R &&Range, UnaryPredicate P) {
1607  return std::none_of(adl_begin(Range), adl_end(Range), P);
1608 }
1609 
1610 /// Provide wrappers to std::find which take ranges instead of having to pass
1611 /// begin/end explicitly.
1612 template <typename R, typename T> auto find(R &&Range, const T &Val) {
1613  return std::find(adl_begin(Range), adl_end(Range), Val);
1614 }
1615 
1616 /// Provide wrappers to std::find_if which take ranges instead of having to pass
1617 /// begin/end explicitly.
1618 template <typename R, typename UnaryPredicate>
1619 auto find_if(R &&Range, UnaryPredicate P) {
1620  return std::find_if(adl_begin(Range), adl_end(Range), P);
1621 }
1622 
1623 template <typename R, typename UnaryPredicate>
1624 auto find_if_not(R &&Range, UnaryPredicate P) {
1625  return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1626 }
1627 
1628 /// Provide wrappers to std::remove_if which take ranges instead of having to
1629 /// pass begin/end explicitly.
1630 template <typename R, typename UnaryPredicate>
1631 auto remove_if(R &&Range, UnaryPredicate P) {
1632  return std::remove_if(adl_begin(Range), adl_end(Range), P);
1633 }
1634 
1635 /// Provide wrappers to std::copy_if which take ranges instead of having to
1636 /// pass begin/end explicitly.
1637 template <typename R, typename OutputIt, typename UnaryPredicate>
1638 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1639  return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1640 }
1641 
1642 template <typename R, typename OutputIt>
1643 OutputIt copy(R &&Range, OutputIt Out) {
1644  return std::copy(adl_begin(Range), adl_end(Range), Out);
1645 }
1646 
1647 /// Provide wrappers to std::move which take ranges instead of having to
1648 /// pass begin/end explicitly.
1649 template <typename R, typename OutputIt>
1650 OutputIt move(R &&Range, OutputIt Out) {
1651  return std::move(adl_begin(Range), adl_end(Range), Out);
1652 }
1653 
1654 /// Wrapper function around std::find to detect if an element exists
1655 /// in a container.
1656 template <typename R, typename E>
1657 bool is_contained(R &&Range, const E &Element) {
1658  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1659 }
1660 
1661 /// Wrapper function around std::is_sorted to check if elements in a range \p R
1662 /// are sorted with respect to a comparator \p C.
1663 template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
1664  return std::is_sorted(adl_begin(Range), adl_end(Range), C);
1665 }
1666 
1667 /// Wrapper function around std::is_sorted to check if elements in a range \p R
1668 /// are sorted in non-descending order.
1669 template <typename R> bool is_sorted(R &&Range) {
1670  return std::is_sorted(adl_begin(Range), adl_end(Range));
1671 }
1672 
1673 /// Wrapper function around std::count to count the number of times an element
1674 /// \p Element occurs in the given range \p Range.
1675 template <typename R, typename E> auto count(R &&Range, const E &Element) {
1676  return std::count(adl_begin(Range), adl_end(Range), Element);
1677 }
1678 
1679 /// Wrapper function around std::count_if to count the number of times an
1680 /// element satisfying a given predicate occurs in a range.
1681 template <typename R, typename UnaryPredicate>
1682 auto count_if(R &&Range, UnaryPredicate P) {
1683  return std::count_if(adl_begin(Range), adl_end(Range), P);
1684 }
1685 
1686 /// Wrapper function around std::transform to apply a function to a range and
1687 /// store the result elsewhere.
1688 template <typename R, typename OutputIt, typename UnaryFunction>
1689 OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F) {
1690  return std::transform(adl_begin(Range), adl_end(Range), d_first, F);
1691 }
1692 
1693 /// Provide wrappers to std::partition which take ranges instead of having to
1694 /// pass begin/end explicitly.
1695 template <typename R, typename UnaryPredicate>
1696 auto partition(R &&Range, UnaryPredicate P) {
1697  return std::partition(adl_begin(Range), adl_end(Range), P);
1698 }
1699 
1700 /// Provide wrappers to std::lower_bound which take ranges instead of having to
1701 /// pass begin/end explicitly.
1702 template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) {
1703  return std::lower_bound(adl_begin(Range), adl_end(Range),
1704  std::forward<T>(Value));
1705 }
1706 
1707 template <typename R, typename T, typename Compare>
1708 auto lower_bound(R &&Range, T &&Value, Compare C) {
1709  return std::lower_bound(adl_begin(Range), adl_end(Range),
1710  std::forward<T>(Value), C);
1711 }
1712 
1713 /// Provide wrappers to std::upper_bound which take ranges instead of having to
1714 /// pass begin/end explicitly.
1715 template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) {
1716  return std::upper_bound(adl_begin(Range), adl_end(Range),
1717  std::forward<T>(Value));
1718 }
1719 
1720 template <typename R, typename T, typename Compare>
1721 auto upper_bound(R &&Range, T &&Value, Compare C) {
1722  return std::upper_bound(adl_begin(Range), adl_end(Range),
1723  std::forward<T>(Value), C);
1724 }
1725 
1726 template <typename R>
1727 void stable_sort(R &&Range) {
1728  std::stable_sort(adl_begin(Range), adl_end(Range));
1729 }
1730 
1731 template <typename R, typename Compare>
1732 void stable_sort(R &&Range, Compare C) {
1733  std::stable_sort(adl_begin(Range), adl_end(Range), C);
1734 }
1735 
1736 /// Binary search for the first iterator in a range where a predicate is false.
1737 /// Requires that C is always true below some limit, and always false above it.
1738 template <typename R, typename Predicate,
1739  typename Val = decltype(*adl_begin(std::declval<R>()))>
1740 auto partition_point(R &&Range, Predicate P) {
1741  return std::partition_point(adl_begin(Range), adl_end(Range), P);
1742 }
1743 
1744 template<typename Range, typename Predicate>
1745 auto unique(Range &&R, Predicate P) {
1746  return std::unique(adl_begin(R), adl_end(R), P);
1747 }
1748 
1749 /// Wrapper function around std::equal to detect if pair-wise elements between
1750 /// two ranges are the same.
1751 template <typename L, typename R> bool equal(L &&LRange, R &&RRange) {
1752  return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange),
1753  adl_end(RRange));
1754 }
1755 
1756 /// Wrapper function around std::equal to detect if all elements
1757 /// in a container are same.
1758 template <typename R>
1759 bool is_splat(R &&Range) {
1760  size_t range_size = size(Range);
1761  return range_size != 0 && (range_size == 1 ||
1762  std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1763 }
1764 
1765 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
1766 /// `erase_if` which is equivalent to:
1767 ///
1768 /// C.erase(remove_if(C, pred), C.end());
1769 ///
1770 /// This version works for any container with an erase method call accepting
1771 /// two iterators.
1772 template <typename Container, typename UnaryPredicate>
1773 void erase_if(Container &C, UnaryPredicate P) {
1774  C.erase(remove_if(C, P), C.end());
1775 }
1776 
1777 /// Wrapper function to remove a value from a container:
1778 ///
1779 /// C.erase(remove(C.begin(), C.end(), V), C.end());
1780 template <typename Container, typename ValueType>
1781 void erase_value(Container &C, ValueType V) {
1782  C.erase(std::remove(C.begin(), C.end(), V), C.end());
1783 }
1784 
1785 /// Wrapper function to append a range to a container.
1786 ///
1787 /// C.insert(C.end(), R.begin(), R.end());
1788 template <typename Container, typename Range>
1789 inline void append_range(Container &C, Range &&R) {
1790  C.insert(C.end(), R.begin(), R.end());
1791 }
1792 
1793 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1794 /// the range [ValIt, ValEnd) (which is not from the same container).
1795 template<typename Container, typename RandomAccessIterator>
1796 void replace(Container &Cont, typename Container::iterator ContIt,
1797  typename Container::iterator ContEnd, RandomAccessIterator ValIt,
1798  RandomAccessIterator ValEnd) {
1799  while (true) {
1800  if (ValIt == ValEnd) {
1801  Cont.erase(ContIt, ContEnd);
1802  return;
1803  } else if (ContIt == ContEnd) {
1804  Cont.insert(ContIt, ValIt, ValEnd);
1805  return;
1806  }
1807  *ContIt++ = *ValIt++;
1808  }
1809 }
1810 
1811 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1812 /// the range R.
1813 template<typename Container, typename Range = std::initializer_list<
1814  typename Container::value_type>>
1815 void replace(Container &Cont, typename Container::iterator ContIt,
1816  typename Container::iterator ContEnd, Range R) {
1817  replace(Cont, ContIt, ContEnd, R.begin(), R.end());
1818 }
1819 
1820 /// An STL-style algorithm similar to std::for_each that applies a second
1821 /// functor between every pair of elements.
1822 ///
1823 /// This provides the control flow logic to, for example, print a
1824 /// comma-separated list:
1825 /// \code
1826 /// interleave(names.begin(), names.end(),
1827 /// [&](StringRef name) { os << name; },
1828 /// [&] { os << ", "; });
1829 /// \endcode
1830 template <typename ForwardIterator, typename UnaryFunctor,
1831  typename NullaryFunctor,
1832  typename = typename std::enable_if<
1833  !std::is_constructible<StringRef, UnaryFunctor>::value &&
1834  !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1835 inline void interleave(ForwardIterator begin, ForwardIterator end,
1836  UnaryFunctor each_fn, NullaryFunctor between_fn) {
1837  if (begin == end)
1838  return;
1839  each_fn(*begin);
1840  ++begin;
1841  for (; begin != end; ++begin) {
1842  between_fn();
1843  each_fn(*begin);
1844  }
1845 }
1846 
1847 template <typename Container, typename UnaryFunctor, typename NullaryFunctor,
1848  typename = typename std::enable_if<
1849  !std::is_constructible<StringRef, UnaryFunctor>::value &&
1850  !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1851 inline void interleave(const Container &c, UnaryFunctor each_fn,
1852  NullaryFunctor between_fn) {
1853  interleave(c.begin(), c.end(), each_fn, between_fn);
1854 }
1855 
1856 /// Overload of interleave for the common case of string separator.
1857 template <typename Container, typename UnaryFunctor, typename StreamT,
1858  typename T = detail::ValueOfRange<Container>>
1859 inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn,
1860  const StringRef &separator) {
1861  interleave(c.begin(), c.end(), each_fn, [&] { os << separator; });
1862 }
1863 template <typename Container, typename StreamT,
1864  typename T = detail::ValueOfRange<Container>>
1865 inline void interleave(const Container &c, StreamT &os,
1866  const StringRef &separator) {
1867  interleave(
1868  c, os, [&](const T &a) { os << a; }, separator);
1869 }
1870 
1871 template <typename Container, typename UnaryFunctor, typename StreamT,
1872  typename T = detail::ValueOfRange<Container>>
1873 inline void interleaveComma(const Container &c, StreamT &os,
1874  UnaryFunctor each_fn) {
1875  interleave(c, os, each_fn, ", ");
1876 }
1877 template <typename Container, typename StreamT,
1878  typename T = detail::ValueOfRange<Container>>
1879 inline void interleaveComma(const Container &c, StreamT &os) {
1880  interleaveComma(c, os, [&](const T &a) { os << a; });
1881 }
1882 
1883 //===----------------------------------------------------------------------===//
1884 // Extra additions to <memory>
1885 //===----------------------------------------------------------------------===//
1886 
1887 struct FreeDeleter {
1888  void operator()(void* v) {
1889  ::free(v);
1890  }
1891 };
1892 
1893 template<typename First, typename Second>
1894 struct pair_hash {
1895  size_t operator()(const std::pair<First, Second> &P) const {
1896  return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1897  }
1898 };
1899 
1900 /// Binary functor that adapts to any other binary functor after dereferencing
1901 /// operands.
1902 template <typename T> struct deref {
1904 
1905  // Could be further improved to cope with non-derivable functors and
1906  // non-binary functors (should be a variadic template member function
1907  // operator()).
1908  template <typename A, typename B> auto operator()(A &lhs, B &rhs) const {
1909  assert(lhs);
1910  assert(rhs);
1911  return func(*lhs, *rhs);
1912  }
1913 };
1914 
1915 namespace detail {
1916 
1917 template <typename R> class enumerator_iter;
1918 
1919 template <typename R> struct result_pair {
1920  using value_reference =
1921  typename std::iterator_traits<IterOfRange<R>>::reference;
1922 
1923  friend class enumerator_iter<R>;
1924 
1925  result_pair() = default;
1926  result_pair(std::size_t Index, IterOfRange<R> Iter)
1927  : Index(Index), Iter(Iter) {}
1928 
1930  : Index(Other.Index), Iter(Other.Iter) {}
1932  Index = Other.Index;
1933  Iter = Other.Iter;
1934  return *this;
1935  }
1936 
1937  std::size_t index() const { return Index; }
1938  value_reference value() const { return *Iter; }
1939 
1940 private:
1942  IterOfRange<R> Iter;
1943 };
1944 
1945 template <typename R>
1946 class enumerator_iter
1947  : public iterator_facade_base<enumerator_iter<R>, std::forward_iterator_tag,
1948  const result_pair<R>> {
1949  using result_type = result_pair<R>;
1950 
1951 public:
1953  : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1954 
1956  : Result(Index, Iter) {}
1957 
1958  const result_type &operator*() const { return Result; }
1959 
1961  assert(Result.Index != std::numeric_limits<size_t>::max());
1962  ++Result.Iter;
1963  ++Result.Index;
1964  return *this;
1965  }
1966 
1967  bool operator==(const enumerator_iter &RHS) const {
1968  // Don't compare indices here, only iterators. It's possible for an end
1969  // iterator to have different indices depending on whether it was created
1970  // by calling std::end() versus incrementing a valid iterator.
1971  return Result.Iter == RHS.Result.Iter;
1972  }
1973 
1974  enumerator_iter(const enumerator_iter &Other) : Result(Other.Result) {}
1976  Result = Other.Result;
1977  return *this;
1978  }
1979 
1980 private:
1981  result_type Result;
1982 };
1983 
1984 template <typename R> class enumerator {
1985 public:
1986  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1987 
1989  return enumerator_iter<R>(0, std::begin(TheRange));
1990  }
1992  return enumerator_iter<R>(0, std::begin(TheRange));
1993  }
1994 
1996  return enumerator_iter<R>(std::end(TheRange));
1997  }
1999  return enumerator_iter<R>(std::end(TheRange));
2000  }
2001 
2002 private:
2003  R TheRange;
2004 };
2005 
2006 } // end namespace detail
2007 
2008 /// Given an input range, returns a new range whose values are are pair (A,B)
2009 /// such that A is the 0-based index of the item in the sequence, and B is
2010 /// the value from the original sequence. Example:
2011 ///
2012 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
2013 /// for (auto X : enumerate(Items)) {
2014 /// printf("Item %d - %c\n", X.index(), X.value());
2015 /// }
2016 ///
2017 /// Output:
2018 /// Item 0 - A
2019 /// Item 1 - B
2020 /// Item 2 - C
2021 /// Item 3 - D
2022 ///
2023 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
2024  return detail::enumerator<R>(std::forward<R>(TheRange));
2025 }
2026 
2027 namespace detail {
2028 
2029 template <typename F, typename Tuple, std::size_t... I>
2030 decltype(auto) apply_tuple_impl(F &&f, Tuple &&t, std::index_sequence<I...>) {
2031  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
2032 }
2033 
2034 } // end namespace detail
2035 
2036 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
2037 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
2038 /// return the result.
2039 template <typename F, typename Tuple>
2040 decltype(auto) apply_tuple(F &&f, Tuple &&t) {
2041  using Indices = std::make_index_sequence<
2043 
2044  return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
2045  Indices{});
2046 }
2047 
2048 namespace detail {
2049 
2050 template <typename Predicate, typename... Args>
2052  auto z = zip(args...);
2053  auto it = z.begin();
2054  auto end = z.end();
2055  while (it != end) {
2056  if (!apply_tuple([&](auto &&...args) { return P(args...); }, *it))
2057  return false;
2058  ++it;
2059  }
2060  return it.all_equals(end);
2061 }
2062 
2063 // Just an adaptor to switch the order of argument and have the predicate before
2064 // the zipped inputs.
2065 template <typename... ArgsThenPredicate, size_t... InputIndexes>
2067  std::tuple<ArgsThenPredicate...> argsThenPredicate,
2068  std::index_sequence<InputIndexes...>) {
2069  auto constexpr OutputIndex =
2070  std::tuple_size<decltype(argsThenPredicate)>::value - 1;
2071  return all_of_zip_predicate_first(std::get<OutputIndex>(argsThenPredicate),
2072  std::get<InputIndexes>(argsThenPredicate)...);
2073 }
2074 
2075 } // end namespace detail
2076 
2077 /// Compare two zipped ranges using the provided predicate (as last argument).
2078 /// Return true if all elements satisfy the predicate and false otherwise.
2079 // Return false if the zipped iterator aren't all at end (size mismatch).
2080 template <typename... ArgsAndPredicate>
2081 bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate) {
2083  std::forward_as_tuple(argsAndPredicate...),
2084  std::make_index_sequence<sizeof...(argsAndPredicate) - 1>{});
2085 }
2086 
2087 /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
2088 /// time. Not meant for use with random-access iterators.
2089 /// Can optionally take a predicate to filter lazily some items.
2090 template <typename IterTy,
2091  typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2093  IterTy &&Begin, IterTy &&End, unsigned N,
2094  Pred &&ShouldBeCounted =
2095  [](const decltype(*std::declval<IterTy>()) &) { return true; },
2096  std::enable_if_t<
2097  !std::is_base_of<std::random_access_iterator_tag,
2098  typename std::iterator_traits<std::remove_reference_t<
2099  decltype(Begin)>>::iterator_category>::value,
2100  void> * = nullptr) {
2101  for (; N; ++Begin) {
2102  if (Begin == End)
2103  return false; // Too few.
2104  N -= ShouldBeCounted(*Begin);
2105  }
2106  for (; Begin != End; ++Begin)
2107  if (ShouldBeCounted(*Begin))
2108  return false; // Too many.
2109  return true;
2110 }
2111 
2112 /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
2113 /// time. Not meant for use with random-access iterators.
2114 /// Can optionally take a predicate to lazily filter some items.
2115 template <typename IterTy,
2116  typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2118  IterTy &&Begin, IterTy &&End, unsigned N,
2119  Pred &&ShouldBeCounted =
2120  [](const decltype(*std::declval<IterTy>()) &) { return true; },
2121  std::enable_if_t<
2122  !std::is_base_of<std::random_access_iterator_tag,
2123  typename std::iterator_traits<std::remove_reference_t<
2124  decltype(Begin)>>::iterator_category>::value,
2125  void> * = nullptr) {
2126  for (; N; ++Begin) {
2127  if (Begin == End)
2128  return false; // Too few.
2129  N -= ShouldBeCounted(*Begin);
2130  }
2131  return true;
2132 }
2133 
2134 /// Returns true if the sequence [Begin, End) has N or less items. Can
2135 /// optionally take a predicate to lazily filter some items.
2136 template <typename IterTy,
2137  typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2139  IterTy &&Begin, IterTy &&End, unsigned N,
2140  Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) {
2141  return true;
2142  }) {
2144  return !hasNItemsOrMore(Begin, End, N + 1, ShouldBeCounted);
2145 }
2146 
2147 /// Returns true if the given container has exactly N items
2148 template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) {
2149  return hasNItems(std::begin(C), std::end(C), N);
2150 }
2151 
2152 /// Returns true if the given container has N or more items
2153 template <typename ContainerTy>
2154 bool hasNItemsOrMore(ContainerTy &&C, unsigned N) {
2155  return hasNItemsOrMore(std::begin(C), std::end(C), N);
2156 }
2157 
2158 /// Returns true if the given container has N or less items
2159 template <typename ContainerTy>
2160 bool hasNItemsOrLess(ContainerTy &&C, unsigned N) {
2161  return hasNItemsOrLess(std::begin(C), std::end(C), N);
2162 }
2163 
2164 /// Returns a raw pointer that represents the same address as the argument.
2165 ///
2166 /// This implementation can be removed once we move to C++20 where it's defined
2167 /// as std::to_address().
2168 ///
2169 /// The std::pointer_traits<>::to_address(p) variations of these overloads has
2170 /// not been implemented.
2171 template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
2172 template <class T> constexpr T *to_address(T *P) { return P; }
2173 
2174 } // end namespace llvm
2175 
2176 #endif // LLVM_ADT_STLEXTRAS_H
z
return z
Definition: README.txt:14
i
i
Definition: README.txt:29
llvm::detail::zip_first::zip_first
zip_first(Iters &&... ts)
Definition: STLExtras.h:687
llvm::detail::zip_longest_range::pointer
typename iterator::pointer pointer
Definition: STLExtras.h:849
llvm::detail::indexed_accessor_range_base::size
size_t size() const
Return the size of this range.
Definition: STLExtras.h:1171
llvm::detail::indexed_accessor_range_base::front
ReferenceT front() const
Definition: STLExtras.h:1151
llvm::orc::BaseT
RTTIExtends< ObjectLinkingLayer, ObjectLayer > BaseT
Definition: ObjectLinkingLayer.cpp:614
llvm::hasNItemsOrLess
bool hasNItemsOrLess(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;})
Returns true if the sequence [Begin, End) has N or less items.
Definition: STLExtras.h:2138
llvm::detail::enumerator_iter::operator==
bool operator==(const enumerator_iter &RHS) const
Definition: STLExtras.h:1967
llvm::array_pod_sort
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1491
llvm::detail::enumerator::end
enumerator_iter< R > end()
Definition: STLExtras.h:1995
llvm::less_second
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:1327
llvm::filter_iterator_base::End
WrappedIteratorT End
Definition: STLExtras.h:399
llvm::detail::ValueOfRange
typename std::remove_reference< decltype(*std::begin(std::declval< RangeT & >()))>::type ValueOfRange
Definition: STLExtras.h:58
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::filter_iterator_impl< WrappedIteratorT, PredicateT, std::bidirectional_iterator_tag >::filter_iterator_impl
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:453
llvm::mapped_iterator_base::mapped_iterator_base
mapped_iterator_base(ItTy U)
Definition: STLExtras.h:324
llvm::detail::indexed_accessor_range_base::empty
bool empty() const
Return if the range is empty.
Definition: STLExtras.h:1174
llvm::upper_bound
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1715
llvm::mapped_iterator_base::operator*
ReferenceTy operator*() const
Definition: STLExtras.h:329
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1606
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:264
Optional.h
llvm::indexed_accessor_iterator::index
ptrdiff_t index
Definition: STLExtras.h:1099
llvm::detail::IterOfRange
decltype(std::begin(std::declval< RangeT & >())) IterOfRange
Definition: STLExtras.h:54
llvm::indexed_accessor_range::getStartIndex
ptrdiff_t getStartIndex() const
Returns the current start index of the range.
Definition: STLExtras.h:1259
llvm::indexed_accessor_iterator::operator==
bool operator==(const indexed_accessor_iterator &rhs) const
Definition: STLExtras.h:1072
llvm::concat_iterator::concat_iterator
concat_iterator(RangeTs &&... Ranges)
Constructs an iterator from a sequence of ranges.
Definition: STLExtras.h:976
llvm::hasNItems
bool hasNItems(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;}, std::enable_if_t< !std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< std::remove_reference_t< decltype(Begin)>>::iterator_category >::value, void > *=nullptr)
Return true if the sequence [Begin, End) has exactly N items.
Definition: STLExtras.h:2092
T
llvm::detail::enumerator::enumerator
enumerator(R &&Range)
Definition: STLExtras.h:1986
llvm::detail::zip_common::zip_common
zip_common(Iters &&... ts)
Definition: STLExtras.h:655
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1702
pointer
Replace within non kernel function use of LDS with pointer
Definition: AMDGPUReplaceLDSUseWithPointer.cpp:631
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::indexed_accessor_iterator::operator+=
DerivedT & operator+=(ptrdiff_t offset)
Definition: STLExtras.h:1080
llvm::iterator_facade_base< zip_longest_iterator< Iters... >, std::common_type< std::forward_iterator_tag, std::iterator_traits< Iters >::iterator_category... >::type, ZipLongestTupleType< Iters... >::type, std::iterator_traits< std::tuple_element< 0, std::tuple< Iters... > >::type >::difference_type, ZipLongestTupleType< Iters... >::type *, ZipLongestTupleType< Iters... >::type >::pointer
ZipLongestTupleType< Iters... >::type * pointer
Definition: iterator.h:85
llvm::detail::Visitor< HeadT, TailTs... >::Visitor
constexpr Visitor(HeadT &&Head, TailTs &&...Tail)
Definition: STLExtras.h:1365
llvm::mapped_iterator_base
A base type of mapped iterator, that is useful for building derived iterators that do not need/want t...
Definition: STLExtras.h:314
llvm::detail::indexed_accessor_range_base::take_front
DerivedT take_front(size_t n=1) const
Take the first n elements.
Definition: STLExtras.h:1194
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2023
llvm::iterator_adaptor_base< mapped_iterator< ItTy, FuncTy >, ItTy, std::iterator_traits< ItTy >::iterator_category, std::remove_reference_t< decltype(std::declval< FuncTy >()(*std::declval< ItTy >())) >, std::iterator_traits< ItTy >::difference_type, std::remove_reference_t< decltype(std::declval< FuncTy >()(*std::declval< ItTy >())) > *, decltype(std::declval< FuncTy >()(*std::declval< ItTy >())) >::I
ItTy I
Definition: iterator.h:241
ErrorHandling.h
llvm::is_sorted
bool is_sorted(R &&Range)
Wrapper function around std::is_sorted to check if elements in a range R are sorted in non-descending...
Definition: STLExtras.h:1669
llvm::detail::zip_longest_range::begin
iterator begin() const
Definition: STLExtras.h:869
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1773
llvm::indexed_accessor_iterator::operator<
bool operator<(const indexed_accessor_iterator &rhs) const
Definition: STLExtras.h:1075
llvm::detail::zip_longest_iterator::operator++
zip_longest_iterator< Iters... > & operator++()
Definition: STLExtras.h:832
llvm::stable_sort
void stable_sort(R &&Range, Compare C)
Definition: STLExtras.h:1732
llvm::detail::enumerator_iter::enumerator_iter
enumerator_iter(IterOfRange< R > EndIter)
Definition: STLExtras.h:1952
llvm::detail::zip_common
Definition: STLExtras.h:625
llvm::detail::Visitor< HeadT >::Visitor
constexpr Visitor(HeadT &&Head)
Definition: STLExtras.h:1373
llvm::interleaveComma
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:1873
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::adl_detail::adl_swap
void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval< T >(), std::declval< T >())))
Definition: STLExtras.h:227
llvm::filter_iterator_impl
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:429
llvm::detail::indexed_accessor_range_base::drop_front
DerivedT drop_front(size_t n=1) const
Drop the first n elements.
Definition: STLExtras.h:1183
llvm::detail::result_pair::result_pair
result_pair(const result_pair< R > &Other)
Definition: STLExtras.h:1929
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:357
llvm::detail::apply_tuple_impl
decltype(auto) apply_tuple_impl(F &&f, Tuple &&t, std::index_sequence< I... >)
Definition: STLExtras.h:2030
llvm::detail::zip_common::test_all_equals
bool test_all_equals(const zip_common &other, std::index_sequence< Ns... >) const
Definition: STLExtras.h:647
llvm::detail::zippy::iterator
ItType< decltype(std::begin(std::declval< Args >()))... > iterator
Definition: STLExtras.h:712
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:235
llvm::iterator_adaptor_base< filter_iterator_base< WrappedIteratorT, PredicateT, IterTag >, WrappedIteratorT, std::common_type< IterTag, std::iterator_traits< WrappedIteratorT >::iterator_category >::type >::iterator_adaptor_base
iterator_adaptor_base()=default
llvm::copy
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1643
llvm::upper_bound
auto upper_bound(R &&Range, T &&Value, Compare C)
Definition: STLExtras.h:1721
llvm::Optional
Definition: APInt.h:33
llvm::detail::void_t
void void_t
Definition: STLExtras.h:77
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::mapped_iterator
Definition: STLExtras.h:275
llvm::apply_tuple
decltype(auto) apply_tuple(F &&f, Tuple &&t)
Given an input tuple (a1, a2, ..., an), pass the arguments of the tuple variadically to f as if by ca...
Definition: STLExtras.h:2040
llvm::detail::Visitor
Definition: STLExtras.h:1361
g
should just be implemented with a CLZ instruction Since there are other e g
Definition: README.txt:709
llvm::iterator_facade_base::value_type
T value_type
Definition: iterator.h:83
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
llvm::concat_iterator
Iterator wrapper that concatenates sequences together.
Definition: STLExtras.h:897
llvm::make_first_range
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Definition: STLExtras.h:1292
llvm::detail::result_pair::result_pair
result_pair()=default
llvm::detail::result_pair::result_pair
result_pair(std::size_t Index, IterOfRange< R > Iter)
Definition: STLExtras.h:1926
llvm::zip_first
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&... args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest.
Definition: STLExtras.h:752
llvm::mapped_iterator::getCurrent
ItTy getCurrent()
Definition: STLExtras.h:286
llvm::count_if
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1682
llvm::has_rbegin
Metafunction to determine if T& or T has a member called rbegin().
Definition: STLExtras.h:351
llvm::detail::zip_longest_iterator::zip_longest_iterator
zip_longest_iterator(std::pair< Iters &&, Iters && >... ts)
Definition: STLExtras.h:824
llvm::detail::ZipTupleType
Definition: STLExtras.h:604
size_t
llvm::map_iterator
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
Definition: STLExtras.h:299
llvm::disjunction
Definition: STLForwardCompat.h:40
llvm::detail::zippy::pointer
typename iterator::pointer pointer
Definition: STLExtras.h:716
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:208
llvm::detail::indexed_accessor_range_base::drop_back
DerivedT drop_back(size_t n=1) const
Drop the last n elements.
Definition: STLExtras.h:1188
llvm::is_detected
typename detail::detector< void, Op, Args... >::value_t is_detected
Detects if a given trait holds for some set of arguments 'Args'.
Definition: STLExtras.h:95
llvm::indexed_accessor_range::offset_base
static std::pair< BaseT, ptrdiff_t > offset_base(const std::pair< BaseT, ptrdiff_t > &base, ptrdiff_t index)
See detail::indexed_accessor_range_base for details.
Definition: STLExtras.h:1263
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::iterator_facade_base::IsBidirectional
@ IsBidirectional
Definition: iterator.h:92
llvm::filter_iterator_impl::filter_iterator_impl
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:432
llvm::detail::zip_longest_range::reference
typename iterator::reference reference
Definition: STLExtras.h:850
llvm::detail::indexed_accessor_range_base::end
iterator end() const
Definition: STLExtras.h:1146
llvm::conjunction
Definition: STLForwardCompat.h:32
llvm::filter_iterator_base::operator++
filter_iterator_base & operator++()
Definition: STLExtras.h:419
llvm::make_const_ref::type
typename std::add_lvalue_reference< typename std::add_const< T >::type >::type type
Definition: STLExtras.h:73
llvm::remove_if
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1631
llvm::detail::enumerator_iter
Definition: STLExtras.h:1917
llvm::detail::zip_longest_range::value_type
typename iterator::value_type value_type
Definition: STLExtras.h:847
llvm::interleave
void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn)
An STL-style algorithm similar to std::for_each that applies a second functor between every pair of e...
Definition: STLExtras.h:1835
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::detail::zip_longest_iterator::value_type
typename ZipLongestTupleType< Iters... >::type value_type
Definition: STLExtras.h:797
llvm::detail::ZipLongestItemType
Definition: STLExtras.h:774
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1592
llvm::detail::ZipLongestTupleType::type
std::tuple< typename ZipLongestItemType< Iters >::type... > type
Definition: STLExtras.h:781
llvm::indexed_accessor_range::getBase
const BaseT & getBase() const
Returns the current base of the range.
Definition: STLExtras.h:1256
llvm::detail::indexed_accessor_range_base::slice
DerivedT slice(size_t n, size_t m) const
Drop the first N elements, and keep M elements.
Definition: STLExtras.h:1177
llvm::make_second_range
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
Definition: STLExtras.h:1302
ptrdiff_t
llvm::detail::zippy::begin
iterator begin() const
Definition: STLExtras.h:733
llvm::make_const_ref
Definition: STLExtras.h:71
f
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
llvm::indexed_accessor_iterator
A utility class used to implement an iterator that contains some base object and an index.
Definition: STLExtras.h:1063
P2
This might compile to this xmm1 xorps xmm0 movss xmm0 ret Now consider if the code caused xmm1 to get spilled This might produce this xmm1 movaps xmm0 movaps xmm1 movss xmm0 ret since the reload is only used by these we could fold it into the producing something like xmm1 movaps xmm0 ret saving two instructions The basic idea is that a reload from a spill if only one byte chunk is bring in zeros the one element instead of elements This can be used to simplify a variety of shuffle where the elements are fixed zeros This code generates ugly probably due to costs being off or< 4 x float > * P2
Definition: README-SSE.txt:278
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::FreeDeleter::operator()
void operator()(void *v)
Definition: STLExtras.h:1888
llvm::adl_end
decltype(auto) adl_end(ContainerTy &&container)
Definition: STLExtras.h:240
llvm::function_traits< ReturnType(*)(Args...), false >::result_t
ReturnType result_t
The result type of this function.
Definition: STLExtras.h:138
llvm::less_first
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:1319
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
ItTy
llvm::detail::zippy::end
iterator end() const
Definition: STLExtras.h:736
llvm::function_traits
This class provides various trait information about a callable object.
Definition: STLExtras.h:112
llvm::detail::zippy::difference_type
typename iterator::difference_type difference_type
Definition: STLExtras.h:715
llvm::concat_iterator::operator*
ValueT & operator*() const
Definition: STLExtras.h:986
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::mapped_iterator::getFunction
const FuncTy & getFunction() const
Definition: STLExtras.h:288
llvm::indexed_accessor_iterator::getBase
const BaseT & getBase() const
Returns the current base of the iterator.
Definition: STLExtras.h:1093
test
Definition: README.txt:37
llvm::early_inc_iterator_impl::operator++
early_inc_iterator_impl & operator++()
Definition: STLExtras.h:554
llvm::detail::zip_common::operator*
value_type operator*() const
Definition: STLExtras.h:657
llvm::detail::concat_range::begin
iterator begin() const
Definition: STLExtras.h:1035
llvm::detail::enumerator_iter::operator*
const result_type & operator*() const
Definition: STLExtras.h:1958
t
bitcast float %x to i32 %s=and i32 %t, 2147483647 %d=bitcast i32 %s to float ret float %d } declare float @fabsf(float %n) define float @bar(float %x) nounwind { %d=call float @fabsf(float %x) ret float %d } This IR(from PR6194):target datalayout="e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple="x86_64-apple-darwin10.0.0" %0=type { double, double } %struct.float3=type { float, float, float } define void @test(%0, %struct.float3 *nocapture %res) nounwind noinline ssp { entry:%tmp18=extractvalue %0 %0, 0 t
Definition: README-SSE.txt:788
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::early_inc_iterator_impl
A pseudo-iterator adaptor that is designed to implement "early increment" style loops.
Definition: STLExtras.h:529
llvm::replace
void replace(Container &Cont, typename Container::iterator ContIt, typename Container::iterator ContEnd, RandomAccessIterator ValIt, RandomAccessIterator ValEnd)
Given a sequence container Cont, replace the range [ContIt, ContEnd) with the range [ValIt,...
Definition: STLExtras.h:1796
llvm::detail::result_pair::index
std::size_t index() const
Definition: STLExtras.h:1937
llvm::detail::zippy::value_type
typename iterator::value_type value_type
Definition: STLExtras.h:714
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::detail::indexed_accessor_range_base::operator!=
bool operator!=(const OtherT &other) const
Definition: STLExtras.h:1166
llvm::detail::indexed_accessor_range_base::base
BaseT base
The base that owns the provided range of values.
Definition: STLExtras.h:1228
STLForwardCompat.h
llvm::function_traits< ReturnType(*)(Args...), false >::arg_t
typename std::tuple_element< i, std::tuple< Args... > >::type arg_t
The type of an argument to this function.
Definition: STLExtras.h:142
llvm::detail::concat_range::end
iterator end()
Definition: STLExtras.h:1038
llvm::detail::indexed_accessor_range_base::indexed_accessor_range_base
indexed_accessor_range_base(iterator begin, iterator end)
Definition: STLExtras.h:1137
llvm::hasNItemsOrMore
bool hasNItemsOrMore(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;}, std::enable_if_t< !std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< std::remove_reference_t< decltype(Begin)>>::iterator_category >::value, void > *=nullptr)
Return true if the sequence [Begin, End) has N or more items.
Definition: STLExtras.h:2117
STLFunctionalExtras.h
llvm::has_rbegin_impl::value
static const bool value
Definition: STLExtras.h:346
llvm::detail::ZipLongestTupleType
Definition: STLExtras.h:780
llvm::detail::enumerator_iter::enumerator_iter
enumerator_iter(std::size_t Index, IterOfRange< R > Iter)
Definition: STLExtras.h:1955
llvm::less_first::operator()
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:1320
llvm::detail::enumerator::end
enumerator_iter< R > end() const
Definition: STLExtras.h:1998
PredicateT
llvm::on_first::func
FuncTy func
Definition: STLExtras.h:1337
llvm::detail::zippy::zippy
zippy(Args &&... ts_)
Definition: STLExtras.h:731
c
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int c
Definition: README.txt:418
llvm::array_lengthof
constexpr size_t array_lengthof(T(&)[N])
Find the length of an array.
Definition: STLExtras.h:1435
llvm::early_inc_iterator_impl::early_inc_iterator_impl
early_inc_iterator_impl(WrappedIteratorT I)
Definition: STLExtras.h:542
llvm::None
const NoneType None
Definition: None.h:23
llvm::zip_longest
detail::zip_longest_range< T, U, Args... > zip_longest(T &&t, U &&u, Args &&... args)
Iterate over two or more iterators at the same time.
Definition: STLExtras.h:880
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1781
llvm::detail::zip_shortest
Definition: STLExtras.h:691
llvm::detail::zip_longest_iterator::operator==
bool operator==(const zip_longest_iterator< Iters... > &other) const
Definition: STLExtras.h:837
llvm::get_array_pod_sort_comparator
int(*)(const void *, const void *) get_array_pod_sort_comparator(const T &)
get_array_pod_sort_comparator - This is an internal helper function used to get type deduction of T r...
Definition: STLExtras.h:1454
llvm::filter_iterator_base::findNextValid
void findNextValid()
Definition: STLExtras.h:402
llvm::iterator_facade_base< zip_longest_iterator< Iters... >, std::common_type< std::forward_iterator_tag, std::iterator_traits< Iters >::iterator_category... >::type, ZipLongestTupleType< Iters... >::type, std::iterator_traits< std::tuple_element< 0, std::tuple< Iters... > >::type >::difference_type, ZipLongestTupleType< Iters... >::type *, ZipLongestTupleType< Iters... >::type >::reference
ZipLongestTupleType< Iters... >::type reference
Definition: iterator.h:86
llvm::detail::indexed_accessor_range_base::iterator::operator*
ReferenceT operator*() const
Definition: STLExtras.h:1124
llvm::FirstIndexOfType
Find the first index where a type appears in a list of types.
Definition: STLExtras.h:191
llvm::mapped_iterator_base::getCurrent
ItTy getCurrent()
Definition: STLExtras.h:327
llvm::detail::concat_range::end
iterator end() const
Definition: STLExtras.h:1041
llvm::detail::result_pair::operator=
result_pair & operator=(const result_pair &Other)
Definition: STLExtras.h:1931
llvm::detail::indexed_accessor_range_base::take_back
DerivedT take_back(size_t n=1) const
Take the last n elements.
Definition: STLExtras.h:1200
llvm::rank
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:1347
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::detail::result_pair::value_reference
typename std::iterator_traits< IterOfRange< R > >::reference value_reference
Definition: STLExtras.h:1921
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
llvm::filter_iterator_impl< WrappedIteratorT, PredicateT, std::bidirectional_iterator_tag >::operator--
filter_iterator_impl & operator--()
Definition: STLExtras.h:457
llvm::count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1675
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
index
splat index
Definition: README_ALTIVEC.txt:181
llvm::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1585
llvm::equal
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Definition: STLExtras.h:1751
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1612
llvm::detail::zip_common::tup_inc
decltype(iterators) tup_inc(std::index_sequence< Ns... >) const
Definition: STLExtras.h:637
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::function_traits< ReturnType(ClassType::*)(Args...) const, false >::result_t
ReturnType result_t
The result type of this function.
Definition: STLExtras.h:121
llvm::filter_iterator_base::Pred
PredicateT Pred
Definition: STLExtras.h:400
llvm::detail::indexed_accessor_range_base::begin
iterator begin() const
Definition: STLExtras.h:1145
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value, Compare C)
Definition: STLExtras.h:1708
llvm::detail::indexed_accessor_range_base::count
ptrdiff_t count
The size from the owning range.
Definition: STLExtras.h:1230
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::make_const_ptr::type
typename std::add_pointer< typename std::add_const< T >::type >::type type
Definition: STLExtras.h:68
llvm::indexed_accessor_iterator::operator-=
DerivedT & operator-=(ptrdiff_t offset)
Definition: STLExtras.h:1084
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
llvm::indexed_accessor_iterator::indexed_accessor_iterator
indexed_accessor_iterator(BaseT base, ptrdiff_t index)
Definition: STLExtras.h:1096
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:585
llvm::is_invocable
is_detected< detail::is_invocable, Callable, Args... > is_invocable
Check if a Callable type can be invoked with the given set of arg types.
Definition: STLExtras.h:105
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1657
llvm::makeVisitor
constexpr decltype(auto) makeVisitor(CallableTs &&...Callables)
Returns an opaquely-typed Callable object whose operator() overload set is the sum of the operator() ...
Definition: STLExtras.h:1408
llvm::concat
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1052
llvm::detail::enumerator_iter::operator++
enumerator_iter & operator++()
Definition: STLExtras.h:1960
llvm::detail::ZipTupleType::type
std::tuple< decltype(*declval< Iters >())... > type
Definition: STLExtras.h:605
llvm::detail::zippy
Definition: STLExtras.h:710
llvm::adl_swap
void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(adl_detail::adl_swap(std::declval< T >(), std::declval< T >())))
Definition: STLExtras.h:245
llvm::pair_hash
Definition: STLExtras.h:1894
llvm::shuffle
void shuffle(Iterator first, Iterator last, RNG &&g)
Definition: STLExtras.h:1419
llvm::early_inc_iterator_impl::operator==
friend bool operator==(const early_inc_iterator_impl &LHS, const early_inc_iterator_impl &RHS)
Definition: STLExtras.h:562
llvm::less_second::operator()
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:1328
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1650
llvm::detail::zippy::iterator_category
typename iterator::iterator_category iterator_category
Definition: STLExtras.h:713
llvm::to_address
auto to_address(const Ptr &P)
Returns a raw pointer that represents the same address as the argument.
Definition: STLExtras.h:2171
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:852
llvm::iterator_facade_base< zip_longest_iterator< Iters... >, std::common_type< std::forward_iterator_tag, std::iterator_traits< Iters >::iterator_category... >::type, ZipLongestTupleType< Iters... >::type, std::iterator_traits< std::tuple_element< 0, std::tuple< Iters... > >::type >::difference_type, ZipLongestTupleType< Iters... >::type *, ZipLongestTupleType< Iters... >::type >::difference_type
std::iterator_traits< std::tuple_element< 0, std::tuple< Iters... > >::type >::difference_type difference_type
Definition: iterator.h:84
llvm::detail::enumerator::begin
enumerator_iter< R > begin() const
Definition: STLExtras.h:1991
iterator_range.h
llvm::deref::func
T func
Definition: STLExtras.h:1903
llvm::is_splat
bool is_splat(R &&Range)
Wrapper function around std::equal to detect if all elements in a container are same.
Definition: STLExtras.h:1759
llvm::detail::concat_range::begin
iterator begin()
Definition: STLExtras.h:1032
llvm::zip
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:743
llvm::detail::indexed_accessor_range_base::operator==
bool operator==(const OtherT &other) const
Compare this range with another.
Definition: STLExtras.h:1161
llvm::ARM::WinEH::ReturnType
ReturnType
Definition: ARMWinEH.h:25
llvm::mapped_iterator::operator*
ReferenceTy operator*() const
Definition: STLExtras.h:290
llvm::detail::detector< void_t< Op< Args... > >, Op, Args... >::value_t
std::true_type value_t
Definition: STLExtras.h:83
llvm::detail::enumerator_iter::enumerator_iter
enumerator_iter(const enumerator_iter &Other)
Definition: STLExtras.h:1974
Compare
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
Definition: README_P9.txt:309
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1573
llvm::detail::indexed_accessor_range_base::indexed_accessor_range_base
indexed_accessor_range_base(BaseT base, ptrdiff_t count)
Definition: STLExtras.h:1142
llvm::sys::fs::remove
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
llvm::hasSingleElement
bool hasSingleElement(ContainerTy &&C)
Returns true if the given container only contains a single element.
Definition: STLExtras.h:257
llvm::detail::zip_common::deref
value_type deref(std::index_sequence< Ns... >) const
Definition: STLExtras.h:632
llvm::detail::detector
Definition: STLExtras.h:78
llvm::TypeAtIndex
std::tuple_element_t< I, std::tuple< Ts... > > TypeAtIndex
Find the type at a given index in a list of types.
Definition: STLExtras.h:202
remove_cvref_t
llvm::detail::indexed_accessor_range_base::getBase
const BaseT & getBase() const
Returns the base of this range.
Definition: STLExtras.h:1213
llvm::detail::fwd_or_bidi_tag_impl< true >::type
std::bidirectional_iterator_tag type
Definition: STLExtras.h:471
llvm::detail::zip_common::operator++
ZipType & operator++()
Definition: STLExtras.h:661
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1599
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::pair_hash::operator()
size_t operator()(const std::pair< First, Second > &P) const
Definition: STLExtras.h:1895
llvm::identity
Definition: identity.h:21
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::transform
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1689
ValueT
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1789
llvm::on_first
Function object to apply a binary function to the first component of a std::pair.
Definition: STLExtras.h:1336
llvm::detail::next_or_end
Iter next_or_end(const Iter &I, const Iter &End)
Definition: STLExtras.h:760
llvm::detail::zip_longest_range::zip_longest_range
zip_longest_range(Args &&... ts_)
Definition: STLExtras.h:867
llvm::partition
auto partition(R &&Range, UnaryPredicate P)
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1696
llvm::detail::indexed_accessor_range_base::indexed_accessor_range_base
indexed_accessor_range_base(const iterator_range< iterator > &range)
Definition: STLExtras.h:1140
llvm::detail::zip_common::value_type
typename Base::value_type value_type
Definition: STLExtras.h:627
llvm::indexed_accessor_iterator::getIndex
ptrdiff_t getIndex() const
Returns the current index of the iterator.
Definition: STLExtras.h:1090
llvm::make_filter_range
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:501
llvm::filter_iterator_base
An iterator adaptor that filters the elements of given inner iterators.
Definition: STLExtras.h:389
llvm::detail::indexed_accessor_range_base::operator[]
ReferenceT operator[](size_t Index) const
Definition: STLExtras.h:1147
llvm::PointerUnion< const Value *, const PseudoSourceValue * >
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1619
llvm::detail::all_of_zip_predicate_last
bool all_of_zip_predicate_last(std::tuple< ArgsThenPredicate... > argsThenPredicate, std::index_sequence< InputIndexes... >)
Definition: STLExtras.h:2066
llvm::partition_point
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:1740
llvm::detail::TypesAreDistinct
Definition: STLExtras.h:160
llvm::detail::zip_longest_range::end
iterator end() const
Definition: STLExtras.h:872
llvm::detail::fwd_or_bidi_tag::type
typename fwd_or_bidi_tag_impl< std::is_base_of< std::bidirectional_iterator_tag, typename std::iterator_traits< IterT >::iterator_category >::value >::type type
Definition: STLExtras.h:480
llvm::map_range
auto map_range(ContainerTy &&C, FuncTy F)
Definition: STLExtras.h:304
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1727
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:252
llvm::detail::zip_first
Definition: STLExtras.h:680
llvm::detail::all_of_zip_predicate_first
bool all_of_zip_predicate_first(Predicate &&P, Args &&...args)
Definition: STLExtras.h:2051
std
Definition: BitVector.h:850
llvm::copy_if
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1638
llvm::detail::zip_common::tup_dec
decltype(iterators) tup_dec(std::index_sequence< Ns... >) const
Definition: STLExtras.h:642
llvm::indexed_accessor_range::dereference_iterator
static ReferenceT dereference_iterator(const std::pair< BaseT, ptrdiff_t > &base, ptrdiff_t index)
See detail::indexed_accessor_range_base for details.
Definition: STLExtras.h:1270
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::detail::concat_range
Helper to store a sequence of ranges being concatenated and access them.
Definition: STLExtras.h:1002
llvm::detail::indexed_accessor_range_base::operator=
indexed_accessor_range_base & operator=(const indexed_accessor_range_base &)=default
llvm::adl_detail::adl_begin
decltype(auto) adl_begin(ContainerTy &&container)
Definition: STLExtras.h:213
llvm::has_rbegin_impl
Helper to determine if type T has a member called rbegin().
Definition: STLExtras.h:335
llvm::adl_begin
decltype(auto) adl_begin(ContainerTy &&container)
Definition: STLExtras.h:235
llvm::detail::fwd_or_bidi_tag_impl::type
std::forward_iterator_tag type
Definition: STLExtras.h:467
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1533
llvm::detail::concat_range::iterator
concat_iterator< ValueT, decltype(std::begin(std::declval< RangeTs & >()))... > iterator
Definition: STLExtras.h:1006
llvm::filter_iterator_base::filter_iterator_base
filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:410
llvm::is_sorted
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition: STLExtras.h:1663
llvm::detail::detector::value_t
std::false_type value_t
Definition: STLExtras.h:79
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1745
llvm::SameType
Definition: STLExtras.h:49
transform
instcombine should handle this transform
Definition: README.txt:262
llvm::all_of_zip
bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate)
Compare two zipped ranges using the provided predicate (as last argument).
Definition: STLExtras.h:2081
llvm::detail::result_pair
Definition: STLExtras.h:1919
llvm::detail::first_or_second_type
Return a reference to the first or second member of a reference.
Definition: STLExtras.h:1283
llvm::function_traits< ReturnType(ClassType::*)(Args...) const, false >::arg_t
typename std::tuple_element< Index, std::tuple< Args... > >::type arg_t
The type of an argument to this function.
Definition: STLExtras.h:125
llvm::detail::zippy::reference
typename iterator::reference reference
Definition: STLExtras.h:717
llvm::FreeDeleter
Definition: STLExtras.h:1887
identity.h
llvm::concat_iterator::operator++
concat_iterator & operator++()
Definition: STLExtras.h:981
llvm::detail::indexed_accessor_range_base::iterator
An iterator element of this range.
Definition: STLExtras.h:1120
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
llvm::detail::concat_range::concat_range
concat_range(RangeTs &&... Ranges)
Definition: STLExtras.h:1029
llvm::array_pod_sort_comparator
int array_pod_sort_comparator(const void *P1, const void *P2)
Adapt std::less<T> for array_pod_sort.
Definition: STLExtras.h:1441
llvm::detail::zip_longest_range::iterator
zip_longest_iterator< decltype(adl_begin(std::declval< Args >()))... > iterator
Definition: STLExtras.h:845
llvm::detail::zip_common::all_equals
bool all_equals(zip_common &other)
Return true if all the iterator are matching other's iterators.
Definition: STLExtras.h:674
N
#define N
llvm::concat_iterator::operator==
bool operator==(const concat_iterator &RHS) const
Definition: STLExtras.h:990
llvm::detail::enumerator_iter::operator=
enumerator_iter & operator=(const enumerator_iter &Other)
Definition: STLExtras.h:1975
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::detail::enumerator::begin
enumerator_iter< R > begin()
Definition: STLExtras.h:1988
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::detail::zip_common::operator--
ZipType & operator--()
Definition: STLExtras.h:666
llvm::detail::indexed_accessor_range_base
The class represents the base of a range of indexed_accessor_iterators.
Definition: STLExtras.h:1115
llvm::detail::zip_longest_iterator
Definition: STLExtras.h:785
llvm::detail::fwd_or_bidi_tag
Helper which sets its type member to forward_iterator_tag if the category of IterT does not derive fr...
Definition: STLExtras.h:477
llvm::detail::zip_longest_range
Definition: STLExtras.h:842
llvm::indexed_accessor_range
This class provides an implementation of a range of indexed_accessor_iterators where the base is not ...
Definition: STLExtras.h:1243
llvm::make_const_ptr
Definition: STLExtras.h:66
llvm::detail::zip_shortest::operator==
bool operator==(const zip_shortest< Iters... > &other) const
Definition: STLExtras.h:705
llvm::indexed_accessor_iterator::operator-
ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const
Definition: STLExtras.h:1068
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::sort
void sort(Container &&C, Compare Comp)
Definition: STLExtras.h:1562
llvm::indexed_accessor_iterator::base
BaseT base
Definition: STLExtras.h:1098
llvm::iterator_facade_base< zip_longest_iterator< Iters... >, std::common_type< std::forward_iterator_tag, std::iterator_traits< Iters >::iterator_category... >::type, ZipLongestTupleType< Iters... >::type, std::iterator_traits< std::tuple_element< 0, std::tuple< Iters... > >::type >::difference_type, ZipLongestTupleType< Iters... >::type *, ZipLongestTupleType< Iters... >::type >::iterator_category
std::common_type< std::forward_iterator_tag, std::iterator_traits< Iters >::iterator_category... >::type iterator_category
Definition: iterator.h:82
llvm::indexed_accessor_range::indexed_accessor_range
indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
Definition: STLExtras.h:1247
llvm::deref::operator()
auto operator()(A &lhs, B &rhs) const
Definition: STLExtras.h:1908
llvm::detail::result_pair::value
value_reference value() const
Definition: STLExtras.h:1938
llvm::detail::indexed_accessor_range_base::back
ReferenceT back() const
Definition: STLExtras.h:1155
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
WrappedIteratorT
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
llvm::detail::zip_common::iterators
std::tuple< Iters... > iterators
Definition: STLExtras.h:629
llvm::detail::zip_longest_iterator::operator*
value_type operator*() const
Definition: STLExtras.h:828
llvm::detail::zip_longest_range::iterator_category
typename iterator::iterator_category iterator_category
Definition: STLExtras.h:846
llvm::detail::fwd_or_bidi_tag_impl
Definition: STLExtras.h:466
llvm::detail::deref_or_none
auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional< std::remove_const_t< std::remove_reference_t< decltype(*I)>>>
Definition: STLExtras.h:767
llvm::mapped_iterator::mapped_iterator
mapped_iterator(ItTy U, FuncTy F)
Definition: STLExtras.h:283
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::deref
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:1902
llvm::adl_detail::adl_end
decltype(auto) adl_end(ContainerTy &&container)
Definition: STLExtras.h:220
llvm::detail::zip_first::operator==
bool operator==(const zip_first< Iters... > &other) const
Definition: STLExtras.h:683
llvm::find_if_not
auto find_if_not(R &&Range, UnaryPredicate P)
Definition: STLExtras.h:1624
llvm::detail::zip_longest_range::difference_type
typename iterator::difference_type difference_type
Definition: STLExtras.h:848
llvm::TypesAreDistinct
Determine if all types in Ts are distinct.
Definition: STLExtras.h:175
llvm::detail::zip_shortest::zip_shortest
zip_shortest(Iters &&... ts)
Definition: STLExtras.h:703
llvm::detail::enumerator
Definition: STLExtras.h:1984
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1198
llvm::detail::sort_trivially_copyable
conjunction< std::is_pointer< T >, std::is_trivially_copyable< typename std::iterator_traits< T >::value_type > > sort_trivially_copyable
Definition: STLExtras.h:1525
llvm::detail::is_invocable
decltype(std::declval< Callable & >()(std::declval< Args >()...)) is_invocable
Definition: STLExtras.h:100
llvm::detail::first_or_second_type::type
typename std::conditional_t< std::is_reference< EltTy >::value, FirstTy, std::remove_reference_t< FirstTy > > type
Definition: STLExtras.h:1287