Halide 22.0.0 Halide compiler and libraries

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
10#include "Util.h"
11
12 namespace Halide {
13
14 struct Expr;
15
16 namespace Internal {
17
18 template<typename T>
19 class Scope;
20
21/** The result of modulus_remainder analysis. These represent strided
22 * subsets of the integers. A ModulusRemainder object m represents all
23 * integers x such that there exists y such that x == m.modulus * y +
24 * m.remainder. Note that under this definition a set containing a
25 * single integer (a constant) is represented using a modulus of
26 * zero. These sets can be combined with several mathematical
27 * operators in the obvious way. E.g. m1 + m2 contains (at least) all
28 * integers x1 + x2 such that x1 belongs to m1 and x2 belongs to
29 * m2. These combinations are conservative. If some internal math
30 * would overflow, it defaults to all of the integers (modulus == 1,
31 * remainder == 0). */
32
33 struct ModulusRemainder {
34 ModulusRemainder() = default;
35 ModulusRemainder(int64_t m, int64_t r)
36 : modulus(m), remainder(r) {
37 }
38
39 int64_t modulus = 1, remainder = 0;
40
41 // Take a conservatively-large union of two sets. Contains all
42 // elements from both sets, and maybe some more stuff.
43 static ModulusRemainder unify(const ModulusRemainder &a, const ModulusRemainder &b);
44
45 // Take a conservatively-large intersection. Everything in the
46 // result is in at least one of the two sets, but not always both.
47 static ModulusRemainder intersect(const ModulusRemainder &a, const ModulusRemainder &b);
48
49 bool operator==(const ModulusRemainder &other) const {
50 return (modulus == other.modulus) && (remainder == other.remainder);
51 }
52};
53
54 ModulusRemainder operator+(const ModulusRemainder &a, const ModulusRemainder &b);
55 ModulusRemainder operator-(const ModulusRemainder &a, const ModulusRemainder &b);
56 ModulusRemainder operator*(const ModulusRemainder &a, const ModulusRemainder &b);
57 ModulusRemainder operator/(const ModulusRemainder &a, const ModulusRemainder &b);
58 ModulusRemainder operator%(const ModulusRemainder &a, const ModulusRemainder &b);
59
60 ModulusRemainder operator+(const ModulusRemainder &a, int64_t b);
61 ModulusRemainder operator-(const ModulusRemainder &a, int64_t b);
62 ModulusRemainder operator*(const ModulusRemainder &a, int64_t b);
63 ModulusRemainder operator/(const ModulusRemainder &a, int64_t b);
64 ModulusRemainder operator%(const ModulusRemainder &a, int64_t b);
65
66/** For things like alignment analysis, often it's helpful to know
67 * if an integer expression is some multiple of a constant plus
68 * some other constant. For example, it is straight-forward to
69 * deduce that ((10*x + 2)*(6*y - 3) - 1) is congruent to five
70 * modulo six.
71 *
72 * We get the most information when the modulus is large. E.g. if
73 * something is congruent to 208 modulo 384, then we also know it's
74 * congruent to 0 mod 8, and we can possibly use it as an index for an
75 * aligned load. If all else fails, we can just say that an integer is
76 * congruent to zero modulo one.
77 */
78 ModulusRemainder modulus_remainder(const Expr &e);
79
80/** If we have alignment information about external variables, we can
81 * let the analysis know about that using this version of
82 * modulus_remainder: */
83 ModulusRemainder modulus_remainder(const Expr &e, const Scope<ModulusRemainder> &scope);
84
85/** Reduce an expression modulo some integer. Returns true and assigns
86 * to remainder if an answer could be found. */
87///@{
88 HALIDE_MUST_USE_RESULT bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder);
89 HALIDE_MUST_USE_RESULT bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder, const Scope<ModulusRemainder> &scope);
90///@}
91
92 void modulus_remainder_test();
93
94/** The greatest common divisor of two integers. Returns a positive result,
95 * unless both args are INT64_MIN. */
96 int64_t gcd(int64_t, int64_t);
97
98/** The least common multiple of two integers */
99 int64_t lcm(int64_t, int64_t);
100
101} // namespace Internal
102} // namespace Halide
103
104#endif
HALIDE_MUST_USE_RESULT
#define HALIDE_MUST_USE_RESULT
Definition: HalideRuntime.h:65
Util.h
Various utility functions used internally Halide.
Halide::Internal::Scope
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
Halide::Internal::operator*
ConstantInterval operator*(const ConstantInterval &a, const ConstantInterval &b)
Halide::Internal::modulus_remainder
ModulusRemainder modulus_remainder(const Expr &e)
For things like alignment analysis, often it's helpful to know if an integer expression is some multi...
Halide::Internal::gcd
int64_t gcd(int64_t, int64_t)
The greatest common divisor of two integers.
Halide::Internal::operator%
ConstantInterval operator%(const ConstantInterval &a, const ConstantInterval &b)
Halide::Internal::operator/
ConstantInterval operator/(const ConstantInterval &a, const ConstantInterval &b)
Halide::Internal::modulus_remainder_test
void modulus_remainder_test()
Halide::Internal::operator-
ConstantInterval operator-(const ConstantInterval &a, const ConstantInterval &b)
Halide::Internal::operator+
ConstantInterval operator+(const ConstantInterval &a, const ConstantInterval &b)
Arithmetic operators on ConstantIntervals.
Halide::Internal::reduce_expr_modulo
HALIDE_MUST_USE_RESULT bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder)
Reduce an expression modulo some integer.
Halide::Internal::lcm
int64_t lcm(int64_t, int64_t)
The least common multiple of two integers.
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
int64_t
signed __INT64_TYPE__ int64_t
Definition: runtime_internal.h:22
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:258
Halide::Internal::ModulusRemainder
The result of modulus_remainder analysis.
Definition: ModulusRemainder.h:33
Halide::Internal::ModulusRemainder::ModulusRemainder
ModulusRemainder()=default
Halide::Internal::ModulusRemainder::unify
static ModulusRemainder unify(const ModulusRemainder &a, const ModulusRemainder &b)
Halide::Internal::ModulusRemainder::ModulusRemainder
ModulusRemainder(int64_t m, int64_t r)
Definition: ModulusRemainder.h:35
Halide::Internal::ModulusRemainder::remainder
int64_t remainder
Definition: ModulusRemainder.h:39
Halide::Internal::ModulusRemainder::operator==
bool operator==(const ModulusRemainder &other) const
Definition: ModulusRemainder.h:49
Halide::Internal::ModulusRemainder::intersect
static ModulusRemainder intersect(const ModulusRemainder &a, const ModulusRemainder &b)
Halide::Internal::ModulusRemainder::modulus
int64_t modulus
Definition: ModulusRemainder.h:39