Halide
Associativity.h
Go to the documentation of this file.
1 #ifndef HALIDE_ASSOCIATIVITY_H
2 #define HALIDE_ASSOCIATIVITY_H
3 
4 /** \file
5  *
6  * Methods for extracting an associative operator from a Func's update definition
7  * if there is any and computing the identity of the associative operator.
8  */
9 #include <functional>
10 #include <string>
11 #include <utility>
12 #include <vector>
13 
14 #include "AssociativeOpsTable.h"
15 #include "Expr.h"
16 
17 namespace Halide {
18 namespace Internal {
19 
20 /**
21  * Represent the equivalent associative op of an update definition.
22  * For example, the following associative Expr, min(f(x), g(r.x) + 2),
23  * where f(x) is the self-recurrence term, is represented as:
24  \code
25  AssociativeOp assoc(
26  AssociativePattern(min(x, y), +inf, true),
27  {Replacement("x", f(x))},
28  {Replacement("y", g(r.x) + 2)},
29  true
30  );
31  \endcode
32  *
33  * 'pattern' contains the list of equivalent binary/unary operators (+ identities)
34  * for each Tuple element in the update definition. 'pattern' also contains
35  * a boolean that indicates if the op is also commutative. 'xs' and 'ys'
36  * contain the corresponding definition of each variable in the list of
37  * binary operators.
38  *
39  * For unary operator, 'xs' is not set, i.e. it will be a pair of empty string
40  * and undefined Expr: {"", Expr()}. 'pattern' will only contain the 'y' term in
41  * this case. For example, min(g(r.x), 4), will be represented as:
42  \code
43  AssociativeOp assoc(
44  AssociativePattern(y, 0, false),
45  {Replacement("", Expr())},
46  {Replacement("y", min(g(r.x), 4))},
47  true
48  );
49  \endcode
50  *
51  * Self-assignment, f(x) = f(x), will be represented as:
52  \code
53  AssociativeOp assoc(
54  AssociativePattern(x, 0, true),
55  {Replacement("x", f(x))},
56  {Replacement("", Expr())},
57  true
58  );
59  \endcode
60  * For both unary operator and self-assignment cases, the identity does not
61  * matter. It can be anything.
62  */
63 struct AssociativeOp {
64  struct Replacement {
65  /** Variable name that is used to replace the expr in 'op'. */
66  std::string var;
68 
69  Replacement() = default;
70  Replacement(const std::string &var, Expr expr)
71  : var(var), expr(std::move(expr)) {
72  }
73 
74  bool operator==(const Replacement &other) const {
75  return (var == other.var) && equal(expr, other.expr);
76  }
77  bool operator!=(const Replacement &other) const {
78  return !(*this == other);
79  }
80  };
81 
82  /** List of pairs of binary associative op and its identity. */
84  std::vector<Replacement> xs;
85  std::vector<Replacement> ys;
87 
89  : is_associative(false) {
90  }
92  : pattern(size), xs(size), ys(size), is_associative(false) {
93  }
94  AssociativeOp(const AssociativePattern &p, const std::vector<Replacement> &xs,
95  const std::vector<Replacement> &ys, bool is_associative)
97  }
98 
99  bool associative() const {
100  return is_associative;
101  }
102  bool commutative() const {
103  return pattern.is_commutative;
104  }
105  size_t size() const {
106  return pattern.size();
107  }
108 };
109 
110 /**
111  * Given an update definition of a Func 'f', determine its equivalent
112  * associative binary/unary operator if there is any. 'is_associative'
113  * indicates if the operation was successfuly proven as associative.
114  */
115 AssociativeOp prove_associativity(
116  const std::string &f, std::vector<Expr> args, std::vector<Expr> exprs);
117 
118 void associativity_test();
119 
120 } // namespace Internal
121 } // namespace Halide
122 
123 #endif
Halide::Internal::associativity_test
void associativity_test()
Halide::Internal::AssociativeOp::Replacement::expr
Expr expr
Definition: Associativity.h:67
Halide::Internal::AssociativeOp::AssociativeOp
AssociativeOp(const AssociativePattern &p, const std::vector< Replacement > &xs, const std::vector< Replacement > &ys, bool is_associative)
Definition: Associativity.h:94
Halide::Internal::AssociativeOp::commutative
bool commutative() const
Definition: Associativity.h:102
Halide::Internal::AssociativeOp::AssociativeOp
AssociativeOp()
Definition: Associativity.h:88
Halide::Internal::AssociativeOp
Represent the equivalent associative op of an update definition.
Definition: Associativity.h:63
Halide::Internal::AssociativeOp::size
size_t size() const
Definition: Associativity.h:105
Halide::Internal::AssociativeOp::is_associative
bool is_associative
Definition: Associativity.h:86
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Internal::prove_associativity
AssociativeOp prove_associativity(const std::string &f, std::vector< Expr > args, std::vector< Expr > exprs)
Given an update definition of a Func 'f', determine its equivalent associative binary/unary operator ...
Halide::Internal::AssociativeOp::Replacement::var
std::string var
Variable name that is used to replace the expr in 'op'.
Definition: Associativity.h:66
Halide::Internal::AssociativeOp::Replacement::operator!=
bool operator!=(const Replacement &other) const
Definition: Associativity.h:77
Halide::Internal::AssociativeOp::Replacement::Replacement
Replacement(const std::string &var, Expr expr)
Definition: Associativity.h:70
Expr.h
Halide::Internal::equal
bool equal(const RDom &bounds0, const RDom &bounds1)
Return true if bounds0 and bounds1 represent the same bounds.
Halide::Internal::AssociativePattern::size
size_t size() const
Definition: AssociativeOpsTable.h:67
Halide::Internal::AssociativeOp::ys
std::vector< Replacement > ys
Definition: Associativity.h:85
Halide::Internal::AssociativeOp::associative
bool associative() const
Definition: Associativity.h:99
Halide::Internal::AssociativePattern::is_commutative
bool is_commutative
Indicate if the associative op is also commutative.
Definition: AssociativeOpsTable.h:38
Halide::Internal::AssociativeOp::Replacement::Replacement
Replacement()=default
AssociativeOpsTable.h
Halide::Internal::AssociativeOp::Replacement
Definition: Associativity.h:64
Halide::Internal::AssociativePattern
Represent an associative op with its identity.
Definition: AssociativeOpsTable.h:32
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:256
Halide::Internal::AssociativeOp::Replacement::operator==
bool operator==(const Replacement &other) const
Definition: Associativity.h:74
Halide::Internal::AssociativeOp::xs
std::vector< Replacement > xs
Definition: Associativity.h:84
Halide::Internal::AssociativeOp::AssociativeOp
AssociativeOp(size_t size)
Definition: Associativity.h:91
Halide::Internal::AssociativeOp::pattern
AssociativePattern pattern
List of pairs of binary associative op and its identity.
Definition: Associativity.h:83