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