RangeCounting.h

Go to the documentation of this file.

/* Copyright 2017-2020 CNRS-AIST JRL and CNRS-UM LIRMM */
 
#pragma once
 
#include <tvm/api.h>
 
#include <tvm/Range.h>
 
#include <list>
 
namespace tvm::internal
{
class TVM_DLLAPI RangeCounting
{
public:
  struct Limit
  {
    enum Type
    {
      Lower = -1,
      Cut = 0,
      Upper = 1
    };
 
    Limit(int i, Type type) : i_(i), type_(type) {}
 
    int i_;     // Value of the limit
    Type type_; // The type of the limit
 
    bool operator==(const Limit & other) const { return (i_ == other.i_ && type_ == other.type_); }
    bool operator<(const Limit & other) const { return i_ < other.i_ || (i_ == other.i_ && type_ < other.type_); }
    bool operator<=(const Limit & other) const { return i_ < other.i_ || (i_ == other.i_ && type_ <= other.type_); }
    bool operator>(const Limit & other) const { return i_ > other.i_ || (i_ == other.i_ && type_ > other.type_); }
    bool operator>=(const Limit & other) const { return i_ > other.i_ || (i_ == other.i_ && type_ >= other.type_); }
 
    friend std::ostream & operator<<(std::ostream & os, const Limit & lim)
    {
      os << "(" << lim.i_ << ", " << ((lim.type_ == Lower) ? "+" : ((lim.type_ == Cut) ? "|" : "-")) << ")";
      return os;
    }
  };
 
  bool add(const Range & r);
  bool remove(const Range & r);
 
  bool empty() const { return limits_.size() == 0; }
 
  const std::vector<Range> & ranges(bool splitOncountDiff = false) const;
  const std::list<Limit> & limits() const;
 
  int maxCount() const;
 
private:
  using It = std::list<Limit>::iterator;
 
  bool moveToFirstAfter(const Limit & val, It & it, int & depth, int depthCut = 0) const;
 
  void insert(const Limit & val, It & it, int & depth);
 
  bool recompute(bool change);
 
  bool isValid() const;
 
  std::list<Limit> limits_;              // The representation of the current state.
  mutable bool recompute_ = false;       // Need to recompute intervals_ without split. Used for lazy evaluation.
  mutable bool recomputeSplit_ = false;  // Need to recompute intervals_ with split. Used for lazy evaluation.
  mutable std::vector<Range> intervals_; // The range representation of the current state, reevaluated
                                         // if necessary when accessed (lazy evaluation).
};
} // namespace tvm::internal