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