Halide
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 
10 namespace Halide {
11 namespace Internal {
12 
13 /** A compare struct suitable for use in std::map and std::set that
14  * computes a lexical ordering on IR nodes. */
15 struct IRDeepCompare {
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. */
23 private:
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 
45 public:
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 (size_t i = 0; i < entries.size(); i++) {
61  entries[i].a = Expr();
62  entries[i].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
85 Expr a, b, c, query;
86 std::set<ExprWithCompareCache> s;
87 IRCompareCache cache(8);
88 s.insert(ExprWithCompareCache(a, &cache));
89 s.insert(ExprWithCompareCache(b, &cache));
90 s.insert(ExprWithCompareCache(c, &cache));
91 if (m.contains(ExprWithCompareCache(query, &cache))) {...}
92 \endcode
93  *
94  */
98 
100  : cache(nullptr) {
101  }
103  : expr(e), cache(c) {
104  }
105 
106  /** The comparison uses (and updates) the cache */
107  bool operator<(const ExprWithCompareCache &other) const;
108 };
109 
110 /** Compare IR nodes for equality of value. Traverses entire IR
111  * tree. For equality of reference, use Expr::same_as. If you're
112  * comparing non-CSE'd Exprs, use graph_equal, which is safe for nasty
113  * graphs of IR nodes. */
114 // @{
115 bool equal(const Expr &a, const Expr &b);
116 bool equal(const Stmt &a, const Stmt &b);
117 bool graph_equal(const Expr &a, const Expr &b);
118 bool graph_equal(const Stmt &a, const Stmt &b);
119 // @}
120 
121 void ir_equality_test();
122 
123 } // namespace Internal
124 } // namespace Halide
125 
126 #endif
Halide::Internal::IRCompareCache::IRCompareCache
IRCompareCache(int b)
Definition: IREquality.h:67
Halide::Internal::IRDeepCompare::operator()
bool operator()(const Expr &a, const Expr &b) const
Halide::Internal::IRCompareCache::IRCompareCache
IRCompareCache()=default
Halide::Internal::ir_equality_test
void ir_equality_test()
Halide::Internal::Stmt
A reference-counted handle to a statement node.
Definition: Expr.h:409
uint64_t
unsigned __INT64_TYPE__ uint64_t
Definition: runtime_internal.h:19
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
Halide::Internal::IRDeepCompare
A compare struct suitable for use in std::map and std::set that computes a lexical ordering on IR nod...
Definition: IREquality.h:15
Halide::Internal::ExprWithCompareCache::operator<
bool operator<(const ExprWithCompareCache &other) const
The comparison uses (and updates) the cache.
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Internal::IRCompareCache::clear
void clear()
Definition: IREquality.h:59
size_t
__SIZE_TYPE__ size_t
Definition: runtime_internal.h:27
Halide::Internal::ExprWithCompareCache::expr
Expr expr
Definition: IREquality.h:96
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::IRCompareCache::insert
void insert(const Expr &a, const Expr &b)
Definition: IREquality.h:46
Halide::Internal::ExprWithCompareCache::ExprWithCompareCache
ExprWithCompareCache()
Definition: IREquality.h:99
Halide::Internal::IRCompareCache::contains
bool contains(const Expr &a, const Expr &b) const
Definition: IREquality.h:52
Halide::Internal::IRCompareCache
Lossily track known equal exprs with a cache.
Definition: IREquality.h:22
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:256
Halide::Internal::ExprWithCompareCache::cache
IRCompareCache * cache
Definition: IREquality.h:97
Halide::Expr::get
const HALIDE_ALWAYS_INLINE Internal::BaseExprNode * get() const
Override get() to return a BaseExprNode * instead of an IRNode *.
Definition: Expr.h:314
uint32_t
unsigned __INT32_TYPE__ uint32_t
Definition: runtime_internal.h:21
Halide::Internal::ExprWithCompareCache::ExprWithCompareCache
ExprWithCompareCache(const Expr &e, IRCompareCache *c)
Definition: IREquality.h:102
Halide::Internal::ExprWithCompareCache
A wrapper about Exprs so that they can be deeply compared with a cache for known-equal subexpressions...
Definition: IREquality.h:95
Halide::Internal::graph_equal
bool graph_equal(const Expr &a, const Expr &b)
Halide::Internal::IntrusivePtr::same_as
HALIDE_ALWAYS_INLINE bool same_as(const IntrusivePtr &other) const
Definition: IntrusivePtr.h:163