Vectorize/SandboxVectorizer/Interval.h

0001 //===- Interval.h -----------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // The Interval class is a generic interval of ordered objects that implement:
0010 // - T * T::getPrevNode()
0011 // - T * T::getNextNode()
0012 // - bool T::comesBefore(const T *) const
0013 //
0014 // This is currently used for Instruction intervals.
0015 // It provides an API for some basic operations on the interval, including some
0016 // simple set operations, like union, intersection and others.
0017 //
0018 //===----------------------------------------------------------------------===//
0019
0020 #ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_INSTRINTERVAL_H
0021 #define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_INSTRINTERVAL_H
0022
0023 #include "llvm/ADT/ArrayRef.h"
0024 #include "llvm/SandboxIR/Instruction.h"
0025 #include "llvm/Support/raw_ostream.h"
0026 #include <iterator>
0027 #include <type_traits>
0028
0029 namespace llvm::sandboxir {
0030
0031 /// A simple iterator for iterating the interval.
0032 template <typename T, typename IntervalType> class IntervalIterator {
0033   T *I;
0034   IntervalType &R;
0035
0036 public:
0037   using difference_type = std::ptrdiff_t;
0038   using value_type = T;
0039   using pointer = value_type *;
0040   using reference = T &;
0041   using iterator_category = std::bidirectional_iterator_tag;
0042
0043   IntervalIterator(T *I, IntervalType &R) : I(I), R(R) {}
0044   bool operator==(const IntervalIterator &Other) const {
0045     assert(&R == &Other.R && "Iterators belong to different regions!");
0046     return Other.I == I;
0047   }
0048   bool operator!=(const IntervalIterator &Other) const {
0049     return !(*this == Other);
0050   }
0051   IntervalIterator &operator++() {
0052     assert(I != nullptr && "already at end()!");
0053     I = I->getNextNode();
0054     return *this;
0055   }
0056   IntervalIterator operator++(int) {
0057     auto ItCopy = *this;
0058     ++*this;
0059     return ItCopy;
0060   }
0061   IntervalIterator &operator--() {
0062     // `I` is nullptr for end() when To is the BB terminator.
0063     I = I != nullptr ? I->getPrevNode() : R.bottom();
0064     return *this;
0065   }
0066   IntervalIterator operator--(int) {
0067     auto ItCopy = *this;
0068     --*this;
0069     return ItCopy;
0070   }
0071   template <typename HT = std::enable_if<std::is_same<T, T *&>::value>>
0072   T &operator*() {
0073     return *I;
0074   }
0075   T &operator*() const { return *I; }
0076 };
0077
0078 template <typename T> class Interval {
0079   T *Top;
0080   T *Bottom;
0081
0082 public:
0083   Interval() : Top(nullptr), Bottom(nullptr) {}
0084   Interval(T *Top, T *Bottom) : Top(Top), Bottom(Bottom) {
0085     assert((Top == Bottom || Top->comesBefore(Bottom)) &&
0086            "Top should come before Bottom!");
0087   }
0088   Interval(ArrayRef<T *> Elems) {
0089     assert(!Elems.empty() && "Expected non-empty Elems!");
0090     Top = Elems[0];
0091     Bottom = Elems[0];
0092     for (auto *I : drop_begin(Elems)) {
0093       if (I->comesBefore(Top))
0094         Top = I;
0095       else if (Bottom->comesBefore(I))
0096         Bottom = I;
0097     }
0098   }
0099   bool empty() const {
0100     assert(((Top == nullptr && Bottom == nullptr) ||
0101             (Top != nullptr && Bottom != nullptr)) &&
0102            "Either none or both should be null");
0103     return Top == nullptr;
0104   }
0105   bool contains(T *I) const {
0106     if (empty())
0107       return false;
0108     return (Top == I || Top->comesBefore(I)) &&
0109            (I == Bottom || I->comesBefore(Bottom));
0110   }
0111   T *top() const { return Top; }
0112   T *bottom() const { return Bottom; }
0113
0114   using iterator = IntervalIterator<T, Interval>;
0115   iterator begin() { return iterator(Top, *this); }
0116   iterator end() {
0117     return iterator(Bottom != nullptr ? Bottom->getNextNode() : nullptr, *this);
0118   }
0119   iterator begin() const {
0120     return iterator(Top, const_cast<Interval &>(*this));
0121   }
0122   iterator end() const {
0123     return iterator(Bottom != nullptr ? Bottom->getNextNode() : nullptr,
0124                     const_cast<Interval &>(*this));
0125   }
0126   /// Equality.
0127   bool operator==(const Interval &Other) const {
0128     return Top == Other.Top && Bottom == Other.Bottom;
0129   }
0130   /// Inequality.
0131   bool operator!=(const Interval &Other) const { return !(*this == Other); }
0132   /// \Returns true if this interval comes before \p Other in program order.
0133   /// This expects disjoint intervals.
0134   bool comesBefore(const Interval &Other) const {
0135     assert(disjoint(Other) && "Expect disjoint intervals!");
0136     return bottom()->comesBefore(Other.top());
0137   }
0138   /// \Returns true if this and \p Other have nothing in common.
0139   bool disjoint(const Interval &Other) const;
0140   /// \Returns the intersection between this and \p Other.
0141   // Example:
0142   // |----|   this
0143   //    |---| Other
0144   //    |-|   this->getIntersection(Other)
0145   Interval intersection(const Interval &Other) const {
0146     if (empty())
0147       return *this;
0148     if (Other.empty())
0149       return Interval();
0150     // 1. No overlap
0151     // A---B      this
0152     //       C--D Other
0153     if (Bottom->comesBefore(Other.Top) || Other.Bottom->comesBefore(Top))
0154       return Interval();
0155     // 2. Overlap.
0156     // A---B   this
0157     //   C--D  Other
0158     auto NewTopI = Top->comesBefore(Other.Top) ? Other.Top : Top;
0159     auto NewBottomI = Bottom->comesBefore(Other.Bottom) ? Bottom : Other.Bottom;
0160     return Interval(NewTopI, NewBottomI);
0161   }
0162   /// Difference operation. This returns up to two intervals.
0163   // Example:
0164   // |--------| this
0165   //    |-|     Other
0166   // |-|   |--| this - Other
0167   SmallVector<Interval, 2> operator-(const Interval &Other) {
0168     if (disjoint(Other))
0169       return {*this};
0170     if (Other.empty())
0171       return {*this};
0172     if (*this == Other)
0173       return {Interval()};
0174     Interval Intersection = intersection(Other);
0175     SmallVector<Interval, 2> Result;
0176     // Part 1, skip if empty.
0177     if (Top != Intersection.Top)
0178       Result.emplace_back(Top, Intersection.Top->getPrevNode());
0179     // Part 2, skip if empty.
0180     if (Intersection.Bottom != Bottom)
0181       Result.emplace_back(Intersection.Bottom->getNextNode(), Bottom);
0182     return Result;
0183   }
0184   /// \Returns the interval difference `this - Other`. This will crash in Debug
0185   /// if the result is not a single interval.
0186   Interval getSingleDiff(const Interval &Other) {
0187     auto Diff = *this - Other;
0188     assert(Diff.size() == 1 && "Expected a single interval!");
0189     return Diff[0];
0190   }
0191   /// \Returns a single interval that spans across both this and \p Other.
0192   // For example:
0193   // |---|        this
0194   //        |---| Other
0195   // |----------| this->getUnionInterval(Other)
0196   Interval getUnionInterval(const Interval &Other) {
0197     if (empty())
0198       return Other;
0199     if (Other.empty())
0200       return *this;
0201     auto *NewTop = Top->comesBefore(Other.Top) ? Top : Other.Top;
0202     auto *NewBottom = Bottom->comesBefore(Other.Bottom) ? Other.Bottom : Bottom;
0203     return {NewTop, NewBottom};
0204   }
0205
0206   /// Update the interval when \p I is about to be moved before \p Before.
0207   // SFINAE disables this for non-Instructions.
0208   template <typename HelperT = T>
0209   std::enable_if_t<std::is_same<HelperT, Instruction>::value, void>
0210   notifyMoveInstr(HelperT *I, decltype(I->getIterator()) BeforeIt) {
0211     assert(contains(I) && "Expect `I` in interval!");
0212     assert(I->getIterator() != BeforeIt && "Can't move `I` before itself!");
0213
0214     // Nothing to do if the instruction won't move.
0215     if (std::next(I->getIterator()) == BeforeIt)
0216       return;
0217
0218     T *NewTop = Top->getIterator() == BeforeIt ? I
0219                 : I == Top                     ? Top->getNextNode()
0220                                                : Top;
0221     T *NewBottom = std::next(Bottom->getIterator()) == BeforeIt ? I
0222                    : I == Bottom ? Bottom->getPrevNode()
0223                                  : Bottom;
0224     Top = NewTop;
0225     Bottom = NewBottom;
0226   }
0227
0228 #ifndef NDEBUG
0229   void print(raw_ostream &OS) const;
0230   LLVM_DUMP_METHOD void dump() const;
0231 #endif
0232 };
0233
0234 } // namespace llvm::sandboxir
0235
0236 #endif // LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_INSTRINTERVAL_H