Loading...
Searching...
No Matches
Associativity.h
Go to the documentation of this file.
#ifndef HALIDE_ASSOCIATIVITY_H
#define HALIDE_ASSOCIATIVITY_H
/** \file
*
* Methods for extracting an associative operator from a Func's update definition
* if there is any and computing the identity of the associative operator.
*/
#include <string>
#include <vector>
#include "AssociativeOpsTable.h"
#include "Expr.h"
namespace Halide {
namespace Internal {
/**
* Represent the equivalent associative op of an update definition.
* For example, the following associative Expr, min(f(x), g(r.x) + 2),
* where f(x) is the self-recurrence term, is represented as:
\code
AssociativeOp assoc(
AssociativePattern(min(x, y), +inf, true),
{Replacement("x", f(x))},
{Replacement("y", g(r.x) + 2)},
true
);
\endcode
*
* 'pattern' contains the list of equivalent binary/unary operators (+ identities)
* for each Tuple element in the update definition. 'pattern' also contains
* a boolean that indicates if the op is also commutative. 'xs' and 'ys'
* contain the corresponding definition of each variable in the list of
* binary operators.
*
* For unary operator, 'xs' is not set, i.e. it will be a pair of empty string
* and undefined Expr: {"", Expr()}. 'pattern' will only contain the 'y' term in
* this case. For example, min(g(r.x), 4), will be represented as:
\code
AssociativeOp assoc(
AssociativePattern(y, 0, false),
{Replacement("", Expr())},
{Replacement("y", min(g(r.x), 4))},
true
);
\endcode
*
* Self-assignment, f(x) = f(x), will be represented as:
\code
AssociativeOp assoc(
AssociativePattern(x, 0, true),
{Replacement("x", f(x))},
{Replacement("", Expr())},
true
);
\endcode
* For both unary operator and self-assignment cases, the identity does not
* matter. It can be anything.
*/
struct AssociativeOp {
struct Replacement {
/** Variable name that is used to replace the expr in 'op'. */
std::string var;
Expr expr;
Replacement() = default;
Replacement(const std::string &var, Expr expr)
: var(var), expr(std::move(expr)) {
}
bool operator==(const Replacement &other) const {
return (var == other.var) && equal(expr, other.expr);
}
bool operator!=(const Replacement &other) const {
return !(*this == other);
}
};
/** List of pairs of binary associative op and its identity. */
AssociativePattern pattern;
std::vector<Replacement> xs;
std::vector<Replacement> ys;
bool is_associative = false;
AssociativeOp() = default;
AssociativeOp(size_t size)
: pattern(size), xs(size), ys(size) {
}
AssociativeOp(const AssociativePattern &p, const std::vector<Replacement> &xs,
const std::vector<Replacement> &ys, bool is_associative)
: pattern(p), xs(xs), ys(ys), is_associative(is_associative) {
}
bool associative() const {
return is_associative;
}
bool commutative() const {
return pattern.is_commutative;
}
size_t size() const {
return pattern.size();
}
};
/**
* Given an update definition of a Func 'f', determine its equivalent
* associative binary/unary operator if there is any. 'is_associative'
* indicates if the operation was successfuly proven as associative.
*/
AssociativeOp prove_associativity(
const std::string &f, std::vector<Expr> args, std::vector<Expr> exprs);
void associativity_test();
} // namespace Internal
} // namespace Halide
#endif
AssociativeOpsTable.h
Tables listing associative operators and their identities.
Expr.h
Base classes for Halide expressions (Halide::Expr) and statements (Halide::Internal::Stmt).
Halide::Internal
Definition AbstractGenerator.h:24
Halide::Internal::equal
bool equal(const RDom &bounds0, const RDom &bounds1)
Return true if bounds0 and bounds1 represent the same bounds.
Halide::Internal::associativity_test
void associativity_test()
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
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition AbstractGenerator.h:19
Halide::Expr
A fragment of Halide syntax.
Definition Expr.h:258
Halide::Internal::AssociativeOp::Replacement::var
std::string var
Variable name that is used to replace the expr in 'op'.
Definition Associativity.h:64
Halide::Internal::AssociativeOp::Replacement::operator!=
bool operator!=(const Replacement &other) const
Definition Associativity.h:75
Halide::Internal::AssociativeOp::Replacement::Replacement
Replacement()=default
Halide::Internal::AssociativeOp::Replacement::operator==
bool operator==(const Replacement &other) const
Definition Associativity.h:72
Halide::Internal::AssociativeOp::Replacement::Replacement
Replacement(const std::string &var, Expr expr)
Definition Associativity.h:68
Halide::Internal::AssociativeOp::Replacement::expr
Expr expr
Definition Associativity.h:65
Halide::Internal::AssociativeOp
Represent the equivalent associative op of an update definition.
Definition Associativity.h:61
Halide::Internal::AssociativeOp::ys
std::vector< Replacement > ys
Definition Associativity.h:83
Halide::Internal::AssociativeOp::xs
std::vector< Replacement > xs
Definition Associativity.h:82
Halide::Internal::AssociativeOp::associative
bool associative() const
Definition Associativity.h:95
Halide::Internal::AssociativeOp::AssociativeOp
AssociativeOp()=default
Halide::Internal::AssociativeOp::size
size_t size() const
Definition Associativity.h:101
Halide::Internal::AssociativeOp::commutative
bool commutative() const
Definition Associativity.h:98
Halide::Internal::AssociativeOp::AssociativeOp
AssociativeOp(size_t size)
Definition Associativity.h:87
Halide::Internal::AssociativeOp::pattern
AssociativePattern pattern
List of pairs of binary associative op and its identity.
Definition Associativity.h:81
Halide::Internal::AssociativeOp::AssociativeOp
AssociativeOp(const AssociativePattern &p, const std::vector< Replacement > &xs, const std::vector< Replacement > &ys, bool is_associative)
Definition Associativity.h:90
Halide::Internal::AssociativeOp::is_associative
bool is_associative
Definition Associativity.h:84
Halide::Internal::AssociativePattern
Represent an associative op with its identity.
Definition AssociativeOpsTable.h:31