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/tirx/expr.h>
 
#include <unordered_map>
 
namespace tvm {
namespace arith {
 
using tirx::IterVar;
using tirx::Var;
using tirx::VarNode;
 
class AnalyzerObj;
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 ffi::Object {
 public:
  TVM_FFI_DECLARE_OBJECT_INFO("ir.IntSet", IntSetNode, ffi::Object);
};
 
class IntSet : public ffi::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(const 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_FFI_DEFINE_OBJECT_REF_METHODS_NULLABLE(IntSet, ffi::ObjectRef, IntSetNode);
};
 
//-----------------------------------------------
// Integer set legacy API.
//------------------------------------------------
ffi::Map<Var, IntSet> ConvertDomMap(const std::unordered_map<const VarNode*, IntSet>& dom_map);
IntSet EvalSet(PrimExpr e, const ffi::Map<IterVar, IntSet>& dom_map);
IntSet EvalSet(PrimExpr e, const ffi::Map<Var, IntSet>& dom_map);
IntSet EvalSet(PrimExpr e, const std::unordered_map<const tirx::VarNode*, IntSet>& dom_map);
IntSet EvalSet(Range r, const ffi::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);
ffi::Array<IntSet> EvalSet(const ffi::Array<Range>& region, const ffi::Map<Var, IntSet>& dom_map);
using ExprIntSetMap = std::unordered_map<PrimExpr, IntSet, ffi::ObjectPtrHash, ffi::ObjectPtrEqual>;
ExprIntSetMap EvalSetForEachSubExpr(PrimExpr e,
                                    const std::unordered_map<const VarNode*, IntSet>& dom_map);
 
IntSet Union(const ffi::Array<IntSet>& sets);
 
ffi::Array<IntSet> UnionRegion(const ffi::Array<ffi::Array<IntSet>>& nd_int_sets);
 
IntSet UnionLowerBound(const ffi::Array<IntSet>& sets);
 
ffi::Array<IntSet> UnionRegionLowerBound(const ffi::Array<ffi::Array<IntSet>>& nd_int_sets);
 
IntSet Intersect(const ffi::Array<IntSet>& sets);
 
ffi::Map<Var, arith::IntSet> AsIntSet(const ffi::Map<Var, Range>& var_dom);
 
TVM_DLL ffi::Optional<ffi::Array<IntSet>> EstimateRegionStrictBound(
    const ffi::Array<Range>& region, const ffi::Map<Var, Range>& var_dom, const PrimExpr& predicate,
    const arith::Analyzer& analyzer);
 
TVM_DLL ffi::Optional<ffi::Array<IntSet>> EstimateRegionLowerBound(
    const ffi::Array<Range>& region, const ffi::Map<Var, Range>& var_dom, const PrimExpr& predicate,
    const arith::Analyzer& analyzer);
 
TVM_DLL ffi::Array<IntSet> EstimateRegionUpperBound(const ffi::Array<Range>& region,
                                                    const ffi::Map<Var, Range>& var_dom,
                                                    const PrimExpr& predicate,
                                                    const arith::Analyzer& analyzer);
 
}  // namespace arith
}  // namespace tvm
#endif  // TVM_ARITH_INT_SET_H_