Halide
Bounds.h
Go to the documentation of this file.
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 
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  */
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 };
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. */
56 
57  /** The bounds if it is touched. */
58  std::vector<Interval> bounds;
59 
60  Box() = default;
61  explicit Box(size_t sz)
62  : bounds(sz) {
63  }
64  explicit Box(const std::vector<Interval> &b)
65  : bounds(b) {
66  }
67 
68  size_t size() const {
69  return bounds.size();
70  }
71  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  }
80  void resize(size_t sz) {
81  bounds.resize(sz);
82  }
83  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
Halide::Internal::boxes_overlap
bool boxes_overlap(const Box &a, const Box &b)
Test if box a could possibly overlap box b.
Halide::Internal::box_intersection
Box box_intersection(const Box &a, const Box &b)
The intersection of two boxes.
Scope.h
Halide::Internal::empty_func_value_bounds
const FuncValueBounds & empty_func_value_bounds()
Halide::Internal::Box::bounds
std::vector< Interval > bounds
The bounds if it is touched.
Definition: Bounds.h:58
Halide::Internal::Box::operator<<
friend std::ostream & operator<<(std::ostream &stream, const Box &b)
Halide::Internal::Direction::Upper
@ Upper
Halide::Internal::bounds_test
void bounds_test()
Halide::Internal::box_touched
Box box_touched(const Expr &e, const std::string &fn, const Scope< Interval > &scope=Scope< Interval >::empty_scope(), const FuncValueBounds &func_bounds=empty_func_value_bounds())
Halide::Internal::Box::Box
Box(const std::vector< Interval > &b)
Definition: Bounds.h:64
Halide::Internal::box_union
Box box_union(const Box &a, const Box &b)
The union of two boxes.
Halide::Internal::Direction
Direction
Given a varying expression, try to find a constant that is either: An upper bound (always greater tha...
Definition: Bounds.h:42
Halide::Internal::FuncValueBounds
std::map< std::pair< std::string, int >, Interval > FuncValueBounds
Definition: Bounds.h:15
Halide::Internal::Box::Box
Box()=default
Halide::Internal::Scope
A common pattern when traversing Halide IR is that you need to keep track of stuff when you find a Le...
Definition: ModulusRemainder.h:17
Halide::Internal::find_constant_bound
Expr find_constant_bound(const Expr &e, Direction d, const Scope< Interval > &scope=Scope< Interval >::empty_scope())
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
Halide::Internal::Box::push_back
void push_back(const Interval &i)
Definition: Bounds.h:83
Halide::Internal::Box::size
size_t size() const
Definition: Bounds.h:68
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Internal::Box::operator[]
Interval & operator[](size_t i)
Definition: Bounds.h:74
Halide::Internal::box_required
Box box_required(const Expr &e, const std::string &fn, const Scope< Interval > &scope=Scope< Interval >::empty_scope(), const FuncValueBounds &func_bounds=empty_func_value_bounds())
Variants of the above that are only concerned with a single function.
Halide::Internal::box_provided
Box box_provided(const Expr &e, const std::string &fn, const Scope< Interval > &scope=Scope< Interval >::empty_scope(), const FuncValueBounds &func_bounds=empty_func_value_bounds())
Halide::Internal::Direction::Lower
@ Lower
Halide::Internal::Box::Box
Box(size_t sz)
Definition: Bounds.h:61
Halide::Internal::Interval
A class to represent ranges of Exprs.
Definition: Interval.h:14
Halide::Internal::Function
A reference-counted handle to Halide's internal representation of a function.
Definition: Function.h:38
Halide::Internal::compute_function_value_bounds
FuncValueBounds compute_function_value_bounds(const std::vector< std::string > &order, const std::map< std::string, Function > &env)
Compute the maximum and minimum possible value for each function in an environment.
Halide::Internal::Scope::empty_scope
static const Scope< T > & empty_scope()
A const ref to an empty scope.
Definition: Scope.h:120
Halide::Internal::Box::resize
void resize(size_t sz)
Definition: Bounds.h:80
Halide::Internal::Box::maybe_unused
bool maybe_unused() const
Check if the used condition is defined and not trivially true.
Halide::Internal::Box::used
Expr used
The conditions under which this region may be touched.
Definition: Bounds.h:55
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:256
Halide::Internal::boxes_touched
std::map< std::string, Box > boxes_touched(const Expr &e, const Scope< Interval > &scope=Scope< Interval >::empty_scope(), const FuncValueBounds &func_bounds=empty_func_value_bounds())
Compute rectangular domains large enough to cover all the 'Call's and 'Provides's to each function th...
Interval.h
Halide::Internal::Box::operator[]
const Interval & operator[](size_t i) const
Definition: Bounds.h:77
Halide::Internal::find_constant_bounds
Interval find_constant_bounds(const Expr &e, const Scope< Interval > &scope)
Find bounds for a varying expression that are either constants or +/-inf.
Halide::Internal::box_contains
bool box_contains(const Box &a, const Box &b)
Test if box a provably contains box b.
Halide::Internal::boxes_provided
std::map< std::string, Box > boxes_provided(const Expr &e, const Scope< Interval > &scope=Scope< Interval >::empty_scope(), const FuncValueBounds &func_bounds=empty_func_value_bounds())
Compute rectangular domains large enough to cover all the 'Provides's to each function that occurs wi...
Halide::Internal::boxes_required
std::map< std::string, Box > boxes_required(const Expr &e, const Scope< Interval > &scope=Scope< Interval >::empty_scope(), const FuncValueBounds &func_bounds=empty_func_value_bounds())
Compute rectangular domains large enough to cover all the 'Call's to each function that occurs within...
Halide::Internal::bounds_of_expr_in_scope
Interval bounds_of_expr_in_scope(const Expr &expr, const Scope< Interval > &scope, const FuncValueBounds &func_bounds=empty_func_value_bounds(), bool const_bound=false)
Given an expression in some variables, and a map from those variables to their bounds (in the form of...
Halide::Internal::merge_boxes
void merge_boxes(Box &a, const Box &b)
Expand box a to encompass box b.
Halide::Internal::Box::empty
bool empty() const
Definition: Bounds.h:71
Halide::Internal::Box
Represents the bounds of a region of arbitrary dimension.
Definition: Bounds.h:53