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 | |
34 | namespace tvm { |
35 | namespace 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 | */ |
44 | class 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 | */ |
85 | class 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 | */ |
124 | TVM_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 | */ |
133 | TVM_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 | |