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