Loading...
Searching...
No Matches
ModulusRemainder.h
Go to the documentation of this file.
#ifndef HALIDE_MODULUS_REMAINDER_H
#define HALIDE_MODULUS_REMAINDER_H
/** \file
* Routines for statically determining what expressions are divisible by.
*/
#include <cstdint>
#include "Util.h"
namespace Halide {
struct Expr;
namespace Internal {
template<typename T>
class Scope;
/** The result of modulus_remainder analysis. These represent strided
* subsets of the integers. A ModulusRemainder object m represents all
* integers x such that there exists y such that x == m.modulus * y +
* m.remainder. Note that under this definition a set containing a
* single integer (a constant) is represented using a modulus of
* zero. These sets can be combined with several mathematical
* operators in the obvious way. E.g. m1 + m2 contains (at least) all
* integers x1 + x2 such that x1 belongs to m1 and x2 belongs to
* m2. These combinations are conservative. If some internal math
* would overflow, it defaults to all of the integers (modulus == 1,
* remainder == 0). */
struct ModulusRemainder {
ModulusRemainder() = default;
ModulusRemainder(int64_t m, int64_t r)
: modulus(m), remainder(r) {
}
int64_t modulus = 1, remainder = 0;
// Take a conservatively-large union of two sets. Contains all
// elements from both sets, and maybe some more stuff.
static ModulusRemainder unify(const ModulusRemainder &a, const ModulusRemainder &b);
// Take a conservatively-large intersection. Everything in the
// result is in at least one of the two sets, but not always both.
static ModulusRemainder intersect(const ModulusRemainder &a, const ModulusRemainder &b);
bool operator==(const ModulusRemainder &other) const {
return (modulus == other.modulus) && (remainder == other.remainder);
}
};
ModulusRemainder operator+(const ModulusRemainder &a, const ModulusRemainder &b);
ModulusRemainder operator-(const ModulusRemainder &a, const ModulusRemainder &b);
ModulusRemainder operator*(const ModulusRemainder &a, const ModulusRemainder &b);
ModulusRemainder operator/(const ModulusRemainder &a, const ModulusRemainder &b);
ModulusRemainder operator%(const ModulusRemainder &a, const ModulusRemainder &b);
ModulusRemainder operator+(const ModulusRemainder &a, int64_t b);
ModulusRemainder operator-(const ModulusRemainder &a, int64_t b);
ModulusRemainder operator*(const ModulusRemainder &a, int64_t b);
ModulusRemainder operator/(const ModulusRemainder &a, int64_t b);
ModulusRemainder operator%(const ModulusRemainder &a, int64_t b);
/** For things like alignment analysis, often it's helpful to know
* if an integer expression is some multiple of a constant plus
* some other constant. For example, it is straight-forward to
* deduce that ((10*x + 2)*(6*y - 3) - 1) is congruent to five
* modulo six.
*
* We get the most information when the modulus is large. E.g. if
* something is congruent to 208 modulo 384, then we also know it's
* congruent to 0 mod 8, and we can possibly use it as an index for an
* aligned load. If all else fails, we can just say that an integer is
* congruent to zero modulo one.
*/
ModulusRemainder modulus_remainder(const Expr &e);
/** If we have alignment information about external variables, we can
* let the analysis know about that using this version of
* modulus_remainder: */
ModulusRemainder modulus_remainder(const Expr &e, const Scope<ModulusRemainder> &scope);
/** Reduce an expression modulo some integer. Returns true and assigns
* to remainder if an answer could be found. */
///@{
HALIDE_MUST_USE_RESULT bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder);
HALIDE_MUST_USE_RESULT bool reduce_expr_modulo(const Expr &e, int64_t modulus, int64_t *remainder, const Scope<ModulusRemainder> &scope);
///@}
void modulus_remainder_test();
/** The greatest common divisor of two integers */
int64_t gcd(int64_t, int64_t);
/** The least common multiple of two integers */
int64_t lcm(int64_t, int64_t);
} // namespace Internal
} // namespace Halide
#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
Definition AbstractGenerator.h:24
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
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