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