1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20/*!
21 * \file int_set.h
22 * \brief Internal data structure for integer set.
23 */
24#ifndef TVM_ARITH_INTERVAL_SET_H_
25#define TVM_ARITH_INTERVAL_SET_H_
26
27#include <tvm/arith/analyzer.h>
28#include <tvm/tir/op.h>
29
30#include <limits>
31
32#include "const_fold.h"
33
34namespace tvm {
35namespace arith {
36
37// Acknowledgement: IntervalSet design originates from Halide.
38/*!
39 * \brief Symbolic interval set.
40 *
41 * \note We intentionally keep the internal of IntSet private,
42 as we might change it later.
43 */
44class IntervalSetNode : public IntSetNode {
45 public:
46 /*! \brief Minimum value in the interval. */
47 PrimExpr min_value;
48 /*! \brief Maximum value in the interval. */
49 PrimExpr max_value;
50
51 // visitor overload.
52 void VisitAttrs(tvm::AttrVisitor* v) {
53 v->Visit("min_value", &min_value);
54 v->Visit("max_value", &max_value);
55 }
56
57 /*! \return Whether the interval has upper bound. */
58 bool HasUpperBound() const { return !is_pos_inf(max_value) && !IsEmpty(); }
59 /*! \return Whether the interval has lower bound. */
60 bool HasLowerBound() const { return !is_neg_inf(min_value) && !IsEmpty(); }
61 /*! \return Whether the interval is a single point. */
62 bool IsSinglePoint() const {
63 if (min_value.same_as(max_value)) {
64 return true;
65 }
66 Analyzer analyzer;
67 return analyzer.CanProveEqual(min_value, max_value);
68 }
69 /*! \return whether interval represent nothing */
70 bool IsEmpty() const {
71 // during computations, either extreme could occur.
72 return is_pos_inf(min_value) || is_neg_inf(max_value);
73 }
74 /*! \return whether interval represent everything */
75 bool IsEverything() const { return is_neg_inf(min_value) && is_pos_inf(max_value); }
76
77 static constexpr const char* _type_key = "arith.IntervalSet";
78 TVM_DECLARE_FINAL_OBJECT_INFO(IntervalSetNode, IntSetNode);
79};
80
81/*!
82 * \brief Interval set used for symbolic integer analysis.
83 * \sa IntervalSetNode
84 */
85class IntervalSet : public IntSet {
86 public:
87 /*!
88 * \brief Make a new instance of interval set.
89 * \param min_value The minimum value in the interval.
90 * \param max_value The maximum value in the interval.
91 * \return The created set.
92 */
93 TVM_DLL IntervalSet(PrimExpr min_value, PrimExpr max_value);
94
95 /*!
96 * \brief Create an IntervalSet that represents a single point.
97 * \param value The value to be represented.
98 * \return The result set.
99 */
100 static IntervalSet SinglePoint(PrimExpr value) { return IntervalSet(value, value); }
101 /*!
102 * \brief Create an IntervalSet that represents everything.
103 * \param value The value to be represented.
104 * \return The result set.
105 */
106 static IntervalSet Everything() { return IntervalSet(neg_inf(), pos_inf()); }
107 /*!
108 * \brief Create an empty eet.
109 * \return The result set.
110 */
111 static IntervalSet Empty() { return IntervalSet(pos_inf(), neg_inf()); }
112
113 TVM_DEFINE_OBJECT_REF_COW_METHOD(IntervalSetNode);
114 TVM_DEFINE_OBJECT_REF_METHODS(IntervalSet, IntSet, IntervalSetNode);
115};
116
117/*!
118 * \brief Create union of two IntervalSets.
119 * \param analyzer The analyzer for simplification analysis.
120 * \param a The first set.
121 * \param b The second set.
122 * \return The result set.
123 */
124TVM_DLL IntervalSet Union(Analyzer* analyzer, IntervalSet a, IntervalSet b);
125
126/*!
127 * \brief Create insersection of two IntervalSets.
128 * \param analzyer The analyzer for simplification analysis.
129 * \param a The first set.
130 * \param b The second set.
131 * \return The result set.
132 */
133TVM_DLL IntervalSet Intersect(Analyzer* analzyer, IntervalSet a, IntervalSet b);
134
135} // namespace arith
136} // namespace tvm
137
138#endif // TVM_ARITH_INTERVAL_SET_H_
139