int_set.h

Go to the documentation of this file.

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

#ifndef TVM_ARITH_INT_SET_H_
#define TVM_ARITH_INT_SET_H_

#include <tvm/ir/expr.h>
#include <tvm/tir/expr.h>

#include <unordered_map>

namespace tvm {
namespace arith {

using tir::IterVar;
using tir::Var;
using tir::VarNode;

class Analyzer;

//-----------------------------------------------
// Integer set data structure.
//
// This is a API build on top of the base
// integer analysis API to provide set analysis.
//------------------------------------------------
enum SignType { kPositive, kNegative, kZero, kUnknown };

class IntSetNode : public Object {
 public:
  static constexpr const char* _type_key = "IntSet";
  static constexpr bool _type_has_method_sequal_reduce = false;
  TVM_DECLARE_BASE_OBJECT_INFO(IntSetNode, Object);
};

class IntSet : public ObjectRef {
 public:
  Range CoverRange(Range max_range) const;
  PrimExpr min() const;
  PrimExpr max() const;
  SignType GetSignType() const;
  bool IsNothing() const;
  bool IsEverything() const;
  bool IsSinglePoint() const;
  bool CanProveSinglePoint(Analyzer* ana) const;
  // TODO(tvm-team): update all CanProve to explicitly take
  // analyzer to encourage more analyzer reuse
  bool CanProvePositive() const;
  bool CanProveNegative() const;
  bool CanProveNonPositive() const;
  bool CanProveNonNegative() const;
  bool HasUpperBound() const;
  bool HasLowerBound() const;

  PrimExpr PointValue() const;
  bool MatchRange(const tvm::Range& r) const;
  static IntSet Nothing();
  static IntSet Everything();
  static IntSet SinglePoint(PrimExpr point);
  static IntSet Vector(PrimExpr vec);
  static IntSet FromMinExtent(PrimExpr min, PrimExpr extent);
  static IntSet FromRange(tvm::Range r);
  static IntSet Interval(PrimExpr min, PrimExpr max);

  TVM_DEFINE_OBJECT_REF_METHODS(IntSet, ObjectRef, IntSetNode);
};

//-----------------------------------------------
// Integer set legacy API.
//------------------------------------------------
Map<Var, IntSet> ConvertDomMap(const std::unordered_map<const VarNode*, IntSet>& dom_map);
IntSet EvalSet(PrimExpr e, const Map<IterVar, IntSet>& dom_map);
IntSet EvalSet(PrimExpr e, const Map<Var, IntSet>& dom_map);
IntSet EvalSet(PrimExpr e, const std::unordered_map<const tir::VarNode*, IntSet>& dom_map);
IntSet EvalSet(Range r, const Map<IterVar, IntSet>& dom_map);

IntSet EvalSet(IntSet s, const std::unordered_map<const VarNode*, IntSet>& dom_map);
IntSet EvalSet(Range r, const std::unordered_map<const VarNode*, IntSet>& dom_map);
Array<IntSet> EvalSet(const Array<Range>& region, const Map<Var, IntSet>& dom_map);
using ExprIntSetMap = std::unordered_map<PrimExpr, IntSet, ObjectPtrHash, ObjectPtrEqual>;
ExprIntSetMap EvalSetForEachSubExpr(PrimExpr e,
                                    const std::unordered_map<const VarNode*, IntSet>& dom_map);

IntSet Union(const Array<IntSet>& sets);

Array<IntSet> UnionRegion(const Array<Array<IntSet>>& nd_int_sets);

IntSet UnionLowerBound(const Array<IntSet>& sets);

Array<IntSet> UnionRegionLowerBound(const Array<Array<IntSet>>& nd_int_sets);

IntSet Intersect(const Array<IntSet>& sets);

Map<Var, arith::IntSet> AsIntSet(const Map<Var, Range>& var_dom);

TVM_DLL Optional<Array<IntSet>> EstimateRegionStrictBound(const Array<Range>& region,
                                                          const Map<Var, Range>& var_dom,
                                                          const PrimExpr& predicate,
                                                          arith::Analyzer* analyzer);

TVM_DLL Optional<Array<IntSet>> EstimateRegionLowerBound(const Array<Range>& region,
                                                         const Map<Var, Range>& var_dom,
                                                         const PrimExpr& predicate,
                                                         arith::Analyzer* analyzer);

TVM_DLL Array<IntSet> EstimateRegionUpperBound(const Array<Range>& region,
                                               const Map<Var, Range>& var_dom,
                                               const PrimExpr& predicate,
                                               arith::Analyzer* analyzer);

}  // namespace arith
}  // namespace tvm
#endif  // TVM_ARITH_INT_SET_H_