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