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