Halide 16.0.0
Halide compiler and libraries
Loading...
Searching...
No Matches
ModulusRemainder.h
Go to the documentation of this file.
1#ifndef HALIDE_MODULUS_REMAINDER_H
2#define HALIDE_MODULUS_REMAINDER_H
3
4/** \file
5 * Routines for statically determining what expressions are divisible by.
6 */
7
8#include <cstdint>
9
10namespace Halide {
11
12struct Expr;
13
14namespace Internal {
15
16template<typename T>
17class Scope;
18
19/** The result of modulus_remainder analysis. These represent strided
20 * subsets of the integers. A ModulusRemainder object m represents all
21 * integers x such that there exists y such that x == m.modulus * y +
22 * m.remainder. Note that under this definition a set containing a
23 * single integer (a constant) is represented using a modulus of
24 * zero. These sets can be combined with several mathematical
25 * operators in the obvious way. E.g. m1 + m2 contains (at least) all
26 * integers x1 + x2 such that x1 belongs to m1 and x2 belongs to
27 * m2. These combinations are conservative. If some internal math
28 * would overflow, it defaults to all of the integers (modulus == 1,
29 * remainder == 0). */
30
32 ModulusRemainder() = default;
36
38
39 // Take a conservatively-large union of two sets. Contains all
40 // elements from both sets, and maybe some more stuff.
42
43 // Take a conservatively-large intersection. Everything in the
44 // result is in at least one of the two sets, but not always both.
46
47 bool operator==(const ModulusRemainder &other) const {
48 return (modulus == other.modulus) && (remainder == other.remainder);
49 }
50};
51
57
63
64/** For things like alignment analysis, often it's helpful to know
65 * if an integer expression is some multiple of a constant plus
66 * some other constant. For example, it is straight-forward to
67 * deduce that ((10*x + 2)*(6*y - 3) - 1) is congruent to five
68 * modulo six.
69 *
70 * We get the most information when the modulus is large. E.g. if
71 * something is congruent to 208 modulo 384, then we also know it's
72 * congruent to 0 mod 8, and we can possibly use it as an index for an
73 * aligned load. If all else fails, we can just say that an integer is
74 * congruent to zero modulo one.
75 */
77
78/** If we have alignment information about external variables, we can
79 * let the analysis know about that using this version of
80 * modulus_remainder: */
82
83/** Reduce an expression modulo some integer. Returns true and assigns
84 * to remainder if an answer could be found. */
85///@{
86bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder);
87bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder, const Scope<ModulusRemainder> &scope);
88///@}
89
91
92/** The greatest common divisor of two integers */
94
95/** The least common multiple of two integers */
97
98} // namespace Internal
99} // namespace Halide
100
101#endif
A common pattern when traversing Halide IR is that you need to keep track of stuff when you find a Le...
Definition Scope.h:94
ModulusRemainder modulus_remainder(const Expr &e)
For things like alignment analysis, often it's helpful to know if an integer expression is some multi...
int64_t gcd(int64_t, int64_t)
The greatest common divisor of two integers.
ModulusRemainder operator+(const ModulusRemainder &a, const ModulusRemainder &b)
ModulusRemainder operator%(const ModulusRemainder &a, const ModulusRemainder &b)
ModulusRemainder operator*(const ModulusRemainder &a, const ModulusRemainder &b)
bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder)
Reduce an expression modulo some integer.
void modulus_remainder_test()
ModulusRemainder operator-(const ModulusRemainder &a, const ModulusRemainder &b)
ModulusRemainder operator/(const ModulusRemainder &a, const ModulusRemainder &b)
int64_t lcm(int64_t, int64_t)
The least common multiple of two integers.
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
@ Internal
Not visible externally, similar to 'static' linkage in C.
Expr cast(Expr a)
Cast an expression to the halide type corresponding to the C++ type T.
Definition IROperator.h:358
signed __INT64_TYPE__ int64_t
A fragment of Halide syntax.
Definition Expr.h:257
The result of modulus_remainder analysis.
static ModulusRemainder unify(const ModulusRemainder &a, const ModulusRemainder &b)
ModulusRemainder(int64_t m, int64_t r)
bool operator==(const ModulusRemainder &other) const
static ModulusRemainder intersect(const ModulusRemainder &a, const ModulusRemainder &b)