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