1 #include "Interval.h"
2 #include "IREquality.h"
3 #include "IRMatch.h"
4 #include "IROperator.h"
5
6 namespace Halide {
7 namespace Internal {
8
9 namespace {
10
11 IRMatcher::Wild<0> x;
12 IRMatcher::Wild<1> y;
13 IRMatcher::WildConst<0> c0;
14 IRMatcher::WildConst<1> c1;
15
make_max_helper(const Expr & a,const Expr & b)16 Expr make_max_helper(const Expr &a, const Expr &b) {
17 auto rewrite = IRMatcher::rewriter(IRMatcher::max(a, b), a.type());
18
19 Expr pos_inf = Interval::pos_inf();
20 Expr neg_inf = Interval::neg_inf();
21 if (rewrite(max(x, x), x) ||
22 rewrite(max(x, pos_inf), pos_inf) ||
23 rewrite(max(pos_inf, x), pos_inf) ||
24 rewrite(max(x, neg_inf), x) ||
25 rewrite(max(neg_inf, x), x) ||
26 rewrite(max(c0, c1), fold(max(c0, c1))) ||
27 rewrite(max(c0, x), max(x, c0)) ||
28 rewrite(max(max(x, c0), c1), max(x, fold(max(c0, c1)))) ||
29 rewrite(max(max(x, c0), y), max(max(x, y), c0)) ||
30 rewrite(max(x, max(y, c0)), max(max(x, y), c0)) ||
31 rewrite(max(max(x, y), x), a) ||
32 rewrite(max(max(x, y), y), a) ||
33 rewrite(max(x, max(x, y)), b) ||
34 rewrite(max(y, max(x, y)), b)) {
35 return rewrite.result;
36 } else {
37 return max(a, b);
38 }
39 }
40
make_min_helper(const Expr & a,const Expr & b)41 Expr make_min_helper(const Expr &a, const Expr &b) {
42 auto rewrite = IRMatcher::rewriter(IRMatcher::min(a, b), a.type());
43
44 Expr pos_inf = Interval::pos_inf();
45 Expr neg_inf = Interval::neg_inf();
46 if (rewrite(min(x, x), x) ||
47 rewrite(min(x, pos_inf), x) ||
48 rewrite(min(pos_inf, x), x) ||
49 rewrite(min(x, neg_inf), neg_inf) ||
50 rewrite(min(neg_inf, x), neg_inf) ||
51 rewrite(min(c0, c1), fold(min(c0, c1))) ||
52 rewrite(min(c0, x), min(x, c0)) ||
53 rewrite(min(min(x, c0), c1), min(x, fold(min(c0, c1)))) ||
54 rewrite(min(min(x, c0), y), min(min(x, y), c0)) ||
55 rewrite(min(x, min(y, c0)), min(min(x, y), c0)) ||
56 rewrite(min(min(x, y), x), a) ||
57 rewrite(min(min(x, y), y), a) ||
58 rewrite(min(x, min(x, y)), b) ||
59 rewrite(min(y, min(x, y)), b)) {
60 return rewrite.result;
61 } else {
62 return min(a, b);
63 }
64 }
65
66 } // namespace
67
everything()68 Interval Interval::everything() {
69 return Interval(neg_inf(), pos_inf());
70 }
71
nothing()72 Interval Interval::nothing() {
73 return Interval(pos_inf(), neg_inf());
74 }
75
single_point(const Expr & e)76 Interval Interval::single_point(const Expr &e) {
77 return Interval(e, e);
78 }
79
is_empty() const80 bool Interval::is_empty() const {
81 return min.same_as(pos_inf()) || max.same_as(neg_inf());
82 }
83
is_everything() const84 bool Interval::is_everything() const {
85 return min.same_as(neg_inf()) && max.same_as(pos_inf());
86 }
87
is_single_point() const88 bool Interval::is_single_point() const {
89 return min.same_as(max);
90 }
91
is_single_point(const Expr & e) const92 bool Interval::is_single_point(const Expr &e) const {
93 return min.same_as(e) && max.same_as(e);
94 }
95
has_upper_bound() const96 bool Interval::has_upper_bound() const {
97 return !max.same_as(pos_inf()) && !is_empty();
98 }
99
has_lower_bound() const100 bool Interval::has_lower_bound() const {
101 return !min.same_as(neg_inf()) && !is_empty();
102 }
103
is_bounded() const104 bool Interval::is_bounded() const {
105 return has_upper_bound() && has_lower_bound();
106 }
107
same_as(const Interval & other) const108 bool Interval::same_as(const Interval &other) const {
109 return min.same_as(other.min) && max.same_as(other.max);
110 }
111
operator ==(const Interval & other) const112 bool Interval::operator==(const Interval &other) const {
113 return (min.same_as(other.min)) && (max.same_as(other.max));
114 }
115
116 // This is called repeatedly by bounds inference and the solver to
117 // build large expressions, so we want to simplify eagerly to avoid
118 // monster expressions.
make_max(const Expr & a,const Expr & b)119 Expr Interval::make_max(const Expr &a, const Expr &b) {
120 return make_max_helper(a, b);
121 }
122
make_min(const Expr & a,const Expr & b)123 Expr Interval::make_min(const Expr &a, const Expr &b) {
124 return make_min_helper(a, b);
125 }
126
include(const Interval & i)127 void Interval::include(const Interval &i) {
128 max = Interval::make_max(max, i.max);
129 min = Interval::make_min(min, i.min);
130 }
131
include(const Expr & e)132 void Interval::include(const Expr &e) {
133 max = Interval::make_max(max, e);
134 min = Interval::make_min(min, e);
135 }
136
make_union(const Interval & a,const Interval & b)137 Interval Interval::make_union(const Interval &a, const Interval &b) {
138 Interval result = a;
139 result.include(b);
140 return result;
141 }
142
make_intersection(const Interval & a,const Interval & b)143 Interval Interval::make_intersection(const Interval &a, const Interval &b) {
144 return Interval(Interval::make_max(a.min, b.min),
145 Interval::make_min(a.max, b.max));
146 }
147
148 // Use Handle types for positive and negative infinity, to prevent
149 // accidentally doing arithmetic on them.
150 Expr Interval::pos_inf_expr = Variable::make(Handle(), "pos_inf");
151 Expr Interval::neg_inf_expr = Variable::make(Handle(), "neg_inf");
152
pos_inf_noinline()153 Expr Interval::pos_inf_noinline() {
154 return Interval::pos_inf_expr;
155 }
neg_inf_noinline()156 Expr Interval::neg_inf_noinline() {
157 return Interval::neg_inf_expr;
158 }
159
160 } // namespace Internal
161 } // namespace Halide
162