Halide 16.0.0
Halide compiler and libraries
IREquality.h
Go to the documentation of this file.
1#ifndef HALIDE_IR_EQUALITY_H
2#define HALIDE_IR_EQUALITY_H
3
4/** \file
5 * Methods to test Exprs and Stmts for equality of value
6 */
7
8#include "Expr.h"
9
10namespace Halide {
11namespace Internal {
12
13/** A compare struct suitable for use in std::map and std::set that
14 * computes a lexical ordering on IR nodes. */
16 bool operator()(const Expr &a, const Expr &b) const;
17 bool operator()(const Stmt &a, const Stmt &b) const;
18};
19
20/** Lossily track known equal exprs with a cache. On collision, the
21 * old pair is evicted. Used below by ExprWithCompareCache. */
23private:
24 struct Entry {
25 Expr a, b;
26 };
27
28 int bits;
29
30 uint32_t hash(const Expr &a, const Expr &b) const {
31 // Note this hash is symmetric in a and b, so that a
32 // comparison in a and b hashes to the same bucket as
33 // a comparison on b and a.
34 uint64_t pa = (uint64_t)(a.get());
35 uint64_t pb = (uint64_t)(b.get());
36 uint64_t mix = (pa + pb) + (pa ^ pb);
37 mix ^= (mix >> bits);
38 mix ^= (mix >> (bits * 2));
39 uint32_t bottom = mix & ((1 << bits) - 1);
40 return bottom;
41 }
42
43 std::vector<Entry> entries;
44
45public:
46 void insert(const Expr &a, const Expr &b) {
47 uint32_t h = hash(a, b);
48 entries[h].a = a;
49 entries[h].b = b;
50 }
51
52 bool contains(const Expr &a, const Expr &b) const {
53 uint32_t h = hash(a, b);
54 const Entry &e = entries[h];
55 return ((a.same_as(e.a) && b.same_as(e.b)) ||
56 (a.same_as(e.b) && b.same_as(e.a)));
57 }
58
59 void clear() {
60 for (auto &entry : entries) {
61 entry.a = Expr();
62 entry.b = Expr();
63 }
64 }
65
66 IRCompareCache() = default;
68 : bits(b), entries(static_cast<size_t>(1) << bits) {
69 }
70};
71
72/** A wrapper about Exprs so that they can be deeply compared with a
73 * cache for known-equal subexpressions. Useful for unsanitized Exprs
74 * coming in from the front-end, which may be horrible graphs with
75 * sub-expressions that are equal by value but not by identity. This
76 * isn't a comparison object like IRDeepCompare above, because libc++
77 * requires that comparison objects be stateless (and constructs a new
78 * one for each comparison!), so they can't have a cache associated
79 * with them. However, by sneakily making the cache a mutable member
80 * of the objects being compared, we can dodge this issue.
81 *
82 * Clunky example usage:
83 *
84\code
85Expr a, b, c, query;
86std::set<ExprWithCompareCache> s;
87IRCompareCache cache(8);
88s.insert(ExprWithCompareCache(a, &cache));
89s.insert(ExprWithCompareCache(b, &cache));
90s.insert(ExprWithCompareCache(c, &cache));
91if (m.contains(ExprWithCompareCache(query, &cache))) {...}
92\endcode
93 *
94 */
97 mutable IRCompareCache *cache = nullptr;
98
101 : expr(e), cache(c) {
102 }
103
104 /** The comparison uses (and updates) the cache */
105 bool operator<(const ExprWithCompareCache &other) const;
106};
107
108/** Compare IR nodes for equality of value. Traverses entire IR
109 * tree. For equality of reference, use Expr::same_as. If you're
110 * comparing non-CSE'd Exprs, use graph_equal, which is safe for nasty
111 * graphs of IR nodes. */
112// @{
113bool equal(const Expr &a, const Expr &b);
114bool equal(const Stmt &a, const Stmt &b);
115bool graph_equal(const Expr &a, const Expr &b);
116bool graph_equal(const Stmt &a, const Stmt &b);
117// @}
118
119/** Order unsanitized IRNodes for use in a map key */
120// @{
121bool graph_less_than(const Expr &a, const Expr &b);
122bool graph_less_than(const Stmt &a, const Stmt &b);
123// @}
124
126
127} // namespace Internal
128} // namespace Halide
129
130#endif
Base classes for Halide expressions (Halide::Expr) and statements (Halide::Internal::Stmt)
Lossily track known equal exprs with a cache.
Definition: IREquality.h:22
void insert(const Expr &a, const Expr &b)
Definition: IREquality.h:46
bool contains(const Expr &a, const Expr &b) const
Definition: IREquality.h:52
bool graph_equal(const Expr &a, const Expr &b)
bool equal(const RDom &bounds0, const RDom &bounds1)
Return true if bounds0 and bounds1 represent the same bounds.
bool graph_less_than(const Expr &a, const Expr &b)
Order unsanitized IRNodes for use in a map key.
void ir_equality_test()
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
@ Internal
Not visible externally, similar to 'static' linkage in C.
unsigned __INT64_TYPE__ uint64_t
__SIZE_TYPE__ size_t
unsigned __INT32_TYPE__ uint32_t
A fragment of Halide syntax.
Definition: Expr.h:257
HALIDE_ALWAYS_INLINE const Internal::BaseExprNode * get() const
Override get() to return a BaseExprNode * instead of an IRNode *.
Definition: Expr.h:315
A wrapper about Exprs so that they can be deeply compared with a cache for known-equal subexpressions...
Definition: IREquality.h:95
ExprWithCompareCache(const Expr &e, IRCompareCache *c)
Definition: IREquality.h:100
bool operator<(const ExprWithCompareCache &other) const
The comparison uses (and updates) the cache.
A compare struct suitable for use in std::map and std::set that computes a lexical ordering on IR nod...
Definition: IREquality.h:15
bool operator()(const Expr &a, const Expr &b) const
bool operator()(const Stmt &a, const Stmt &b) const
HALIDE_ALWAYS_INLINE bool same_as(const IntrusivePtr &other) const
Definition: IntrusivePtr.h:168
A reference-counted handle to a statement node.
Definition: Expr.h:418