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 |