1 #ifndef HALIDE_BOUNDS_H
2 #define HALIDE_BOUNDS_H
3 
4 /** \file
5  * Methods for computing the upper and lower bounds of an expression,
6  * and the regions of a function read or written by a statement.
7  */
8 
9 #include "Interval.h"
10 #include "Scope.h"
11 
12 namespace Halide {
13 namespace Internal {
14 
15 class Function;
16 
17 typedef std::map<std::pair<std::string, int>, Interval> FuncValueBounds;
18 
19 const FuncValueBounds &empty_func_value_bounds();
20 
21 /** Given an expression in some variables, and a map from those
22  * variables to their bounds (in the form of (minimum possible value,
23  * maximum possible value)), compute two expressions that give the
24  * minimum possible value and the maximum possible value of this
25  * expression. Max or min may be undefined expressions if the value is
26  * not bounded above or below. If the expression is a vector, also
27  * takes the bounds across the vector lanes and returns a scalar
28  * result.
29  *
30  * This is for tasks such as deducing the region of a buffer
31  * loaded by a chunk of code.
32  */
33 Interval bounds_of_expr_in_scope(const Expr &expr,
34                                  const Scope<Interval> &scope,
35                                  const FuncValueBounds &func_bounds = empty_func_value_bounds(),
36                                  bool const_bound = false);
37 
38 /** Given a varying expression, try to find a constant that is either:
39  * An upper bound (always greater than or equal to the expression), or
40  * A lower bound (always less than or equal to the expression)
41  * If it fails, returns an undefined Expr. */
42 enum class Direction { Upper,
43                        Lower };
44 Expr find_constant_bound(const Expr &e, Direction d,
45                          const Scope<Interval> &scope = Scope<Interval>::empty_scope());
46 
47 /** Find bounds for a varying expression that are either constants or
48  * +/-inf. */
49 Interval find_constant_bounds(const Expr &e, const Scope<Interval> &scope);
50 
51 /** Represents the bounds of a region of arbitrary dimension. Zero
52  * dimensions corresponds to a scalar region. */
53 struct Box {
54     /** The conditions under which this region may be touched. */
55     Expr used;
56 
57     /** The bounds if it is touched. */
58     std::vector<Interval> bounds;
59 
60     Box() = default;
BoxBox61     explicit Box(size_t sz)
62         : bounds(sz) {
63     }
BoxBox64     explicit Box(const std::vector<Interval> &b)
65         : bounds(b) {
66     }
67 
sizeBox68     size_t size() const {
69         return bounds.size();
70     }
emptyBox71     bool empty() const {
72         return bounds.empty();
73     }
74     Interval &operator[](size_t i) {
75         return bounds[i];
76     }
77     const Interval &operator[](size_t i) const {
78         return bounds[i];
79     }
resizeBox80     void resize(size_t sz) {
81         bounds.resize(sz);
82     }
push_backBox83     void push_back(const Interval &i) {
84         bounds.push_back(i);
85     }
86 
87     /** Check if the used condition is defined and not trivially true. */
88     bool maybe_unused() const;
89 
90     friend std::ostream &operator<<(std::ostream &stream, const Box &b);
91 };
92 
93 /** Expand box a to encompass box b */
94 void merge_boxes(Box &a, const Box &b);
95 
96 /** Test if box a could possibly overlap box b. */
97 bool boxes_overlap(const Box &a, const Box &b);
98 
99 /** The union of two boxes */
100 Box box_union(const Box &a, const Box &b);
101 
102 /** The intersection of two boxes */
103 Box box_intersection(const Box &a, const Box &b);
104 
105 /** Test if box a provably contains box b */
106 bool box_contains(const Box &a, const Box &b);
107 
108 /** Compute rectangular domains large enough to cover all the 'Call's
109  * to each function that occurs within a given statement or
110  * expression. This is useful for figuring out what regions of things
111  * to evaluate. */
112 // @{
113 std::map<std::string, Box> boxes_required(const Expr &e,
114                                           const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
115                                           const FuncValueBounds &func_bounds = empty_func_value_bounds());
116 std::map<std::string, Box> boxes_required(Stmt s,
117                                           const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
118                                           const FuncValueBounds &func_bounds = empty_func_value_bounds());
119 // @}
120 
121 /** Compute rectangular domains large enough to cover all the
122  * 'Provides's to each function that occurs within a given statement
123  * or expression. */
124 // @{
125 std::map<std::string, Box> boxes_provided(const Expr &e,
126                                           const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
127                                           const FuncValueBounds &func_bounds = empty_func_value_bounds());
128 std::map<std::string, Box> boxes_provided(Stmt s,
129                                           const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
130                                           const FuncValueBounds &func_bounds = empty_func_value_bounds());
131 // @}
132 
133 /** Compute rectangular domains large enough to cover all the 'Call's
134  * and 'Provides's to each function that occurs within a given
135  * statement or expression. */
136 // @{
137 std::map<std::string, Box> boxes_touched(const Expr &e,
138                                          const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
139                                          const FuncValueBounds &func_bounds = empty_func_value_bounds());
140 std::map<std::string, Box> boxes_touched(Stmt s,
141                                          const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
142                                          const FuncValueBounds &func_bounds = empty_func_value_bounds());
143 // @}
144 
145 /** Variants of the above that are only concerned with a single function. */
146 // @{
147 Box box_required(const Expr &e, const std::string &fn,
148                  const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
149                  const FuncValueBounds &func_bounds = empty_func_value_bounds());
150 Box box_required(Stmt s, const std::string &fn,
151                  const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
152                  const FuncValueBounds &func_bounds = empty_func_value_bounds());
153 
154 Box box_provided(const Expr &e, const std::string &fn,
155                  const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
156                  const FuncValueBounds &func_bounds = empty_func_value_bounds());
157 Box box_provided(Stmt s, const std::string &fn,
158                  const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
159                  const FuncValueBounds &func_bounds = empty_func_value_bounds());
160 
161 Box box_touched(const Expr &e, const std::string &fn,
162                 const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
163                 const FuncValueBounds &func_bounds = empty_func_value_bounds());
164 Box box_touched(Stmt s, const std::string &fn,
165                 const Scope<Interval> &scope = Scope<Interval>::empty_scope(),
166                 const FuncValueBounds &func_bounds = empty_func_value_bounds());
167 // @}
168 
169 /** Compute the maximum and minimum possible value for each function
170  * in an environment. */
171 FuncValueBounds compute_function_value_bounds(const std::vector<std::string> &order,
172                                               const std::map<std::string, Function> &env);
173 
174 void bounds_test();
175 
176 }  // namespace Internal
177 }  // namespace Halide
178 
179 #endif
180