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