Loading...
Searching...
No Matches
Simplify_Internal.h
Go to the documentation of this file.
#ifndef HALIDE_SIMPLIFY_VISITORS_H
#define HALIDE_SIMPLIFY_VISITORS_H
/** \file
* The simplifier is separated into multiple compilation units with
* this single shared header to speed up the build. This file is not
* exported in Halide.h. */
#include "Bounds.h"
#include "ConstantInterval.h"
#include "IRMatch.h"
#include "IRPrinter.h"
#include "IRVisitor.h"
#include "Scope.h"
// Because this file is only included by the simplify methods and
// doesn't go into Halide.h, we're free to use any old names for our
// macros.
#define LOG_EXPR_MUTATIONS 0
#define LOG_STMT_MUTATIONS 0
// On old compilers, some visitors would use large stack frames,
// because they use expression templates that generate large numbers
// of temporary objects when they are built and matched against. If we
// wrap the expressions that imply lots of temporaries in a lambda, we
// can get these large frames out of the recursive path.
#define EVAL_IN_LAMBDA(x) (([&]() HALIDE_NEVER_INLINE { return (x); })())
namespace Halide {
namespace Internal {
class Simplify : public VariadicVisitor<Simplify, Expr, Stmt> {
using Super = VariadicVisitor<Simplify, Expr, Stmt>;
public:
Simplify(bool r, const Scope<Interval> *bi, const Scope<ModulusRemainder> *ai);
struct ExprInfo {
// We track constant integer bounds when they exist
ConstantInterval bounds;
// And the alignment of integer variables
ModulusRemainder alignment;
void trim_bounds_using_alignment() {
if (alignment.modulus == 0) {
bounds = ConstantInterval::single_point(alignment.remainder);
} else if (alignment.modulus > 1) {
if (bounds.min_defined) {
int64_t adjustment;
bool no_overflow = sub_with_overflow(64, alignment.remainder, mod_imp(bounds.min, alignment.modulus), &adjustment);
adjustment = mod_imp(adjustment, alignment.modulus);
int64_t new_min;
no_overflow &= add_with_overflow(64, bounds.min, adjustment, &new_min);
if (no_overflow) {
bounds.min = new_min;
}
}
if (bounds.max_defined) {
int64_t adjustment;
bool no_overflow = sub_with_overflow(64, mod_imp(bounds.max, alignment.modulus), alignment.remainder, &adjustment);
adjustment = mod_imp(adjustment, alignment.modulus);
int64_t new_max;
no_overflow &= sub_with_overflow(64, bounds.max, adjustment, &new_max);
if (no_overflow) {
bounds.max = new_max;
}
}
}
if (bounds.is_single_point()) {
alignment.modulus = 0;
alignment.remainder = bounds.min;
}
if (bounds.is_bounded() && bounds.min > bounds.max) {
// Impossible, we must be in unreachable code. TODO: surface
// this to the simplify instance's in_unreachable flag.
bounds.max = bounds.min;
}
}
uint64_t largest_power_of_two_factor(uint64_t x) const {
// Consider the bits of x from MSB to LSB. Say there are three
// trailing zeros, and the four high bits are unknown:
// a b c d 1 0 0 0
// The largest power of two factor of a number is the trailing bits
// up to and including the first 1. In this example that's 1000
// (i.e. 8).
// Negating is flipping the bits and adding one. First we flip:
// ~a ~b ~c ~d 0 1 1 1
// Then we add one:
// ~a ~b ~c ~d 1 0 0 0
// If we bitwise and this with the original, the unknown bits cancel
// out, and we get left with just the largest power of two
// factor. If we want a mask of the trailing zeros instead, we can
// just subtract one.
return x & -x;
}
void cast_to(Type t) {
if ((!t.is_int() && !t.is_uint()) || (t.is_int() && t.bits() >= 32)) {
return;
}
// We've just done some infinite-integer operation on a bounded
// integer type, and we need to project the bounds and alignment
// back in-range.
if (!t.can_represent(bounds)) {
if (t.bits() >= 64) {
// Just preserve any power-of-two factor in the modulus. When
// alignment.modulus == 0, the value is some positive constant
// representable as any 64-bit integer type, so there's no
// wraparound.
if (alignment.modulus > 0) {
alignment.modulus = largest_power_of_two_factor(alignment.modulus);
alignment.remainder &= alignment.modulus - 1;
}
} else {
// A narrowing integer cast that could possibly overflow adds
// some unknown multiple of 2^bits
alignment = alignment + ModulusRemainder(((int64_t)1 << t.bits()), 0);
}
}
// Truncate the bounds to the new type.
bounds.cast_to(t);
}
// Mix in existing knowledge about this Expr
void intersect(const ExprInfo &other) {
if (bounds < other.bounds || other.bounds < bounds) {
// Impossible. We must be in unreachable code. TODO: It might
// be nice to surface this to the simplify instance's
// in_unreachable flag, but we'd have to be sure that it's going
// to be caught at the right place.
return;
}
bounds = ConstantInterval::make_intersection(bounds, other.bounds);
alignment = ModulusRemainder::intersect(alignment, other.alignment);
trim_bounds_using_alignment();
}
// An alternative representation for information about integers is that
// certain bits have known values in the 2s complement
// representation. This is a useful form for analyzing bitwise ops, so
// we provide conversions to and from that representation. For narrow
// types, this represent what the bits would be if they were sign or
// zero-extended to 64 bits, so for uints the high bits are known to be
// zero, and for ints it depends on whether or not we knew the high bit
// to begin with.
struct BitsKnown {
// A mask which is 1 where we know the value of that bit
uint64_t mask;
// The actual value of the known bits
uint64_t value;
uint64_t known_zeros() const {
return mask & ~value;
}
uint64_t known_ones() const {
return mask & value;
}
bool all_bits_known() const {
return mask == (uint64_t)(-1);
}
BitsKnown operator&(const BitsKnown &other) const {
// Where either has known zeros, we have known zeros in the result
uint64_t zeros = known_zeros() | other.known_zeros();
// Where both have a known one, we have a known one in the result
uint64_t ones = known_ones() & other.known_ones();
return {zeros | ones, ones};
}
BitsKnown operator|(const BitsKnown &other) const {
// Where either has known ones, we have known ones in the result
uint64_t ones = known_ones() | other.known_ones();
// Where both have a known zero, we have a known zero in the result.
uint64_t zeros = known_zeros() & other.known_zeros();
return {zeros | ones, ones};
}
BitsKnown operator^(const BitsKnown &other) const {
// Unlike & and |, we need to know both bits to know anything.
uint64_t new_mask = mask & other.mask;
return {new_mask, (value ^ other.value) & new_mask};
}
};
BitsKnown to_bits_known(const Type &type) const;
void from_bits_known(BitsKnown known, const Type &type);
};
HALIDE_ALWAYS_INLINE
void clear_expr_info(ExprInfo *info) {
if (info) {
*info = ExprInfo{};
}
}
void set_expr_info_to_constant(ExprInfo *info, int64_t c) const {
if (info) {
info->bounds = ConstantInterval::single_point(c);
info->alignment = ModulusRemainder{0, c};
}
}
int64_t normalize_constant(const Type &t, int64_t c) {
// If this is supposed to be an int32, but the constant is not
// representable as an int32, we have a problem, because the Halide
// simplifier is unsound with respect to int32 overflow (see
// https://github.com/halide/Halide/issues/3245).
// It's tempting to just say we return a signed_integer_overflow, for
// which we know nothing, but if we're in this function we're making a
// constant, so we clearly decided not to do that in the caller. Is this
// a bug in the caller? No, this intentionally happens when
// constant-folding narrowing casts, and changing that behavior to
// return signed_integer_overflow breaks a bunch of real code, because
// unfortunately that's how people express wrapping casts to int32. We
// could return an ExprInfo that says "I know nothing", but we're also
// returning a constant Expr, so the next mutation is just going to
// infer everything there is to infer about a constant. The best we can
// do at this point is just wrap to the right number of bits.
int dropped_bits = 64 - t.bits();
if (t.is_int()) {
c <<= dropped_bits;
c >>= dropped_bits; // sign-extend
} else if (t.is_uint()) {
// For uints, normalization is considerably less problematic
c <<= dropped_bits;
c = (int64_t)(((uint64_t)c >> dropped_bits)); // zero-extend
}
return c;
}
// We never want to return make_const anything in the simplifier without
// also setting the ExprInfo, so shadow the global make_const.
Expr make_const(const Type &t, int64_t c, ExprInfo *info) {
c = normalize_constant(t, c);
set_expr_info_to_constant(info, c);
return Halide::Internal::make_const(t, c);
}
Expr make_const(const Type &t, uint64_t c, ExprInfo *info) {
c = normalize_constant(t, c);
if ((int64_t)c >= 0) {
// This is representable as an int64_t
set_expr_info_to_constant(info, (int64_t)c);
} else if (info) {
// If it's not representable as an int64, we can't express
// everything we know about it in ExprInfo.
// We can say that it's big:
info->bounds = ConstantInterval::bounded_below(INT64_MAX);
// And we can say what we know about the bottom 62 bits (2^62 is the
// largest power of two we can represent as an int64_t):
int64_t modulus = (int64_t)1 << 62;
info->alignment = {modulus, (int64_t)c & (modulus - 1)};
}
return Halide::Internal::make_const(t, c);
}
HALIDE_ALWAYS_INLINE
Expr make_const(const Type &t, double c, ExprInfo *info) {
// We don't currently track information about floats
return Halide::Internal::make_const(t, c);
}
HALIDE_ALWAYS_INLINE
Expr const_false(int lanes, ExprInfo *info) {
return make_const(UInt(1, lanes), (int64_t)0, info);
}
HALIDE_ALWAYS_INLINE
Expr const_true(int lanes, ExprInfo *info) {
return make_const(UInt(1, lanes), (int64_t)1, info);
}
#if (LOG_EXPR_MUTATIONS || LOG_STMT_MUTATIONS)
int debug_indent = 0;
#endif
#if LOG_EXPR_MUTATIONS
Expr mutate(const Expr &e, ExprInfo *b) {
internal_assert(debug_indent >= 0);
const std::string spaces(debug_indent, ' ');
debug(1) << spaces << "Simplifying Expr: " << e << "\n";
debug_indent++;
Expr new_e = Super::dispatch(e, b);
debug_indent--;
if (!new_e.same_as(e)) {
debug(1)
<< spaces << "Before: " << e << "\n"
<< spaces << "After: " << new_e << "\n";
if (b) {
debug(1)
<< spaces << "Bounds: " << b->bounds << " " << b->alignment << "\n";
if (auto i = as_const_int(new_e)) {
internal_assert(b->bounds.contains(*i))
<< e << "\n"
<< new_e << "\n"
<< b->bounds;
} else if (auto i = as_const_uint(new_e)) {
internal_assert(b->bounds.contains(*i))
<< e << "\n"
<< new_e << "\n"
<< b->bounds;
}
if (new_e.type().is_uint() &&
new_e.type().bits() < 64 &&
!is_signed_integer_overflow(new_e)) {
internal_assert(b->bounds.min_defined && b->bounds.min >= 0)
<< e << "\n"
<< new_e << "\n"
<< b->bounds;
}
}
}
internal_assert(e.type() == new_e.type());
return new_e;
}
#else
HALIDE_ALWAYS_INLINE
Expr mutate(const Expr &e, ExprInfo *b) {
// This gets inlined into every call to mutate, so do not add any code here.
return Super::dispatch(e, b);
}
#endif
#if LOG_STMT_MUTATIONS
Stmt mutate(const Stmt &s) {
const std::string spaces(debug_indent, ' ');
debug(1) << spaces << "Simplifying Stmt: " << s << "\n";
debug_indent++;
Stmt new_s = Super::dispatch(s);
debug_indent--;
if (!new_s.same_as(s)) {
debug(1)
<< spaces << "Before: " << s << "\n"
<< spaces << "After: " << new_s << "\n";
}
return new_s;
}
#else
Stmt mutate(const Stmt &s) {
return Super::dispatch(s);
}
#endif
bool remove_dead_code;
// Returns true iff t is an integral type where overflow is undefined
HALIDE_ALWAYS_INLINE
bool no_overflow_int(Type t) {
return t.is_int() && t.bits() >= 32;
}
HALIDE_ALWAYS_INLINE
bool no_overflow_scalar_int(Type t) {
return t.is_scalar() && no_overflow_int(t);
}
// Returns true iff t does not have a well defined overflow behavior.
HALIDE_ALWAYS_INLINE
bool no_overflow(Type t) {
return t.is_float() || no_overflow_int(t);
}
struct VarInfo {
Expr replacement;
int old_uses, new_uses;
};
// Tracked for all let vars
Scope<VarInfo> var_info;
// Only tracked for integer let vars
Scope<ExprInfo> bounds_and_alignment_info;
// Symbols used by rewrite rules
IRMatcher::Wild<0> x;
IRMatcher::Wild<1> y;
IRMatcher::Wild<2> z;
IRMatcher::Wild<3> w;
IRMatcher::Wild<4> u;
IRMatcher::Wild<5> v;
IRMatcher::WildConst<0> c0;
IRMatcher::WildConst<1> c1;
IRMatcher::WildConst<2> c2;
IRMatcher::WildConst<3> c3;
IRMatcher::WildConst<4> c4;
IRMatcher::WildConst<5> c5;
// Tracks whether or not we're inside a vector loop. Certain
// transformations are not a good idea if the code is to be
// vectorized.
bool in_vector_loop = false;
// Tracks whether or not the current IR is unconditionally unreachable.
bool in_unreachable = false;
// If we encounter a reference to a buffer (a Load, Store, Call,
// or Provide), there's an implicit dependence on some associated
// symbols.
void found_buffer_reference(const std::string &name, size_t dimensions = 0);
// Put the args to a commutative op in a canonical order
HALIDE_ALWAYS_INLINE
bool should_commute(const Expr &a, const Expr &b) {
if (a.node_type() < b.node_type()) {
return true;
}
if (a.node_type() > b.node_type()) {
return false;
}
if (a.node_type() == IRNodeType::Variable) {
const Variable *va = a.as<Variable>();
const Variable *vb = b.as<Variable>();
return va->name.compare(vb->name) > 0;
}
return false;
}
std::set<Expr, IRDeepCompare> truths, falsehoods;
struct ScopedFact {
Simplify *simplify;
std::vector<const Variable *> pop_list;
std::vector<const Variable *> bounds_pop_list;
std::set<Expr, IRDeepCompare> truths, falsehoods;
void learn_false(const Expr &fact);
void learn_true(const Expr &fact);
void learn_upper_bound(const Variable *v, int64_t val);
void learn_lower_bound(const Variable *v, int64_t val);
// Replace exprs known to be truths or falsehoods with const_true or const_false.
Expr substitute_facts(const Expr &e);
Stmt substitute_facts(const Stmt &s);
ScopedFact(Simplify *s)
: simplify(s) {
}
~ScopedFact();
// allow move but not copy
ScopedFact(const ScopedFact &that) = delete;
ScopedFact(ScopedFact &&that) = default;
};
// Tell the simplifier to learn from and exploit a boolean
// condition, over the lifetime of the returned object.
ScopedFact scoped_truth(const Expr &fact) {
ScopedFact f(this);
f.learn_true(fact);
return f;
}
// Tell the simplifier to assume a boolean condition is false over
// the lifetime of the returned object.
ScopedFact scoped_falsehood(const Expr &fact) {
ScopedFact f(this);
f.learn_false(fact);
return f;
}
Stmt mutate_let_body(const Stmt &s, ExprInfo *) {
return mutate(s);
}
Expr mutate_let_body(const Expr &e, ExprInfo *info) {
return mutate(e, info);
}
template<typename T, typename Body>
Body simplify_let(const T *op, ExprInfo *info);
Expr visit(const IntImm *op, ExprInfo *info);
Expr visit(const UIntImm *op, ExprInfo *info);
Expr visit(const FloatImm *op, ExprInfo *info);
Expr visit(const StringImm *op, ExprInfo *info);
Expr visit(const Broadcast *op, ExprInfo *info);
Expr visit(const Cast *op, ExprInfo *info);
Expr visit(const Reinterpret *op, ExprInfo *info);
Expr visit(const Variable *op, ExprInfo *info);
Expr visit(const Add *op, ExprInfo *info);
Expr visit(const Sub *op, ExprInfo *info);
Expr visit(const Mul *op, ExprInfo *info);
Expr visit(const Div *op, ExprInfo *info);
Expr visit(const Mod *op, ExprInfo *info);
Expr visit(const Min *op, ExprInfo *info);
Expr visit(const Max *op, ExprInfo *info);
Expr visit(const EQ *op, ExprInfo *info);
Expr visit(const NE *op, ExprInfo *info);
Expr visit(const LT *op, ExprInfo *info);
Expr visit(const LE *op, ExprInfo *info);
Expr visit(const GT *op, ExprInfo *info);
Expr visit(const GE *op, ExprInfo *info);
Expr visit(const And *op, ExprInfo *info);
Expr visit(const Or *op, ExprInfo *info);
Expr visit(const Not *op, ExprInfo *info);
Expr visit(const Select *op, ExprInfo *info);
Expr visit(const Ramp *op, ExprInfo *info);
Stmt visit(const IfThenElse *op);
Expr visit(const Load *op, ExprInfo *info);
Expr visit(const Call *op, ExprInfo *info);
Expr visit(const Shuffle *op, ExprInfo *info);
Expr visit(const VectorReduce *op, ExprInfo *info);
Expr visit(const Let *op, ExprInfo *info);
Stmt visit(const LetStmt *op);
Stmt visit(const AssertStmt *op);
Stmt visit(const For *op);
Stmt visit(const Provide *op);
Stmt visit(const Store *op);
Stmt visit(const Allocate *op);
Stmt visit(const Evaluate *op);
Stmt visit(const ProducerConsumer *op);
Stmt visit(const Block *op);
Stmt visit(const Realize *op);
Stmt visit(const Prefetch *op);
Stmt visit(const Free *op);
Stmt visit(const Acquire *op);
Stmt visit(const Fork *op);
Stmt visit(const Atomic *op);
Stmt visit(const HoistedStorage *op);
std::pair<std::vector<Expr>, bool> mutate_with_changes(const std::vector<Expr> &old_exprs);
};
} // namespace Internal
} // namespace Halide
#endif
Bounds.h
Methods for computing the upper and lower bounds of an expression, and the regions of a function read...
ConstantInterval.h
Defines the ConstantInterval class, and operators on it.
debug
#define debug(n)
For optional debugging during codegen, use the debug macro as follows:
Definition Debug.h:52
internal_assert
#define internal_assert(c)
Definition Error.h:218
HALIDE_ALWAYS_INLINE
#define HALIDE_ALWAYS_INLINE
Definition HalideRuntime.h:49
IRMatch.h
Defines a method to match a fragment of IR against a pattern containing wildcards.
IRPrinter.h
This header file defines operators that let you dump a Halide expression, statement,...
IRVisitor.h
Defines the base class for things that recursively walk over the IR.
Scope.h
Defines the Scope class, which is used for keeping track of names in a scope while traversing IR.
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::Simplify::visit
Stmt visit(const HoistedStorage *op)
Halide::Internal::Simplify::const_false
HALIDE_ALWAYS_INLINE Expr const_false(int lanes, ExprInfo *info)
Definition Simplify_Internal.h:275
Halide::Internal::Simplify::visit
Expr visit(const LE *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const ProducerConsumer *op)
Halide::Internal::Simplify::mutate
HALIDE_ALWAYS_INLINE Expr mutate(const Expr &e, ExprInfo *b)
Definition Simplify_Internal.h:330
Halide::Internal::Simplify::z
IRMatcher::Wild< 2 > z
Definition Simplify_Internal.h:389
Halide::Internal::Simplify::bounds_and_alignment_info
Scope< ExprInfo > bounds_and_alignment_info
Definition Simplify_Internal.h:384
Halide::Internal::Simplify::clear_expr_info
HALIDE_ALWAYS_INLINE void clear_expr_info(ExprInfo *info)
Definition Simplify_Internal.h:199
Halide::Internal::Simplify::visit
Expr visit(const Variable *op, ExprInfo *info)
Halide::Internal::Simplify::c5
IRMatcher::WildConst< 5 > c5
Definition Simplify_Internal.h:398
Halide::Internal::Simplify::found_buffer_reference
void found_buffer_reference(const std::string &name, size_t dimensions=0)
Halide::Internal::Simplify::visit
Stmt visit(const Block *op)
Halide::Internal::Simplify::visit
Expr visit(const Load *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const Cast *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const AssertStmt *op)
Halide::Internal::Simplify::u
IRMatcher::Wild< 4 > u
Definition Simplify_Internal.h:391
Halide::Internal::Simplify::mutate
Stmt mutate(const Stmt &s)
Definition Simplify_Internal.h:351
Halide::Internal::Simplify::visit
Stmt visit(const Evaluate *op)
Halide::Internal::Simplify::visit
Expr visit(const Let *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const LT *op, ExprInfo *info)
Halide::Internal::Simplify::Simplify
Simplify(bool r, const Scope< Interval > *bi, const Scope< ModulusRemainder > *ai)
Halide::Internal::Simplify::visit
Expr visit(const Ramp *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const Prefetch *op)
Halide::Internal::Simplify::no_overflow
HALIDE_ALWAYS_INLINE bool no_overflow(Type t)
Definition Simplify_Internal.h:371
Halide::Internal::Simplify::c1
IRMatcher::WildConst< 1 > c1
Definition Simplify_Internal.h:394
Halide::Internal::Simplify::visit
Expr visit(const Shuffle *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const IfThenElse *op)
Halide::Internal::Simplify::visit
Expr visit(const Mod *op, ExprInfo *info)
Halide::Internal::Simplify::v
IRMatcher::Wild< 5 > v
Definition Simplify_Internal.h:392
Halide::Internal::Simplify::c0
IRMatcher::WildConst< 0 > c0
Definition Simplify_Internal.h:393
Halide::Internal::Simplify::y
IRMatcher::Wild< 1 > y
Definition Simplify_Internal.h:388
Halide::Internal::Simplify::in_unreachable
bool in_unreachable
Definition Simplify_Internal.h:406
Halide::Internal::Simplify::remove_dead_code
bool remove_dead_code
Definition Simplify_Internal.h:356
Halide::Internal::Simplify::scoped_truth
ScopedFact scoped_truth(const Expr &fact)
Definition Simplify_Internal.h:462
Halide::Internal::Simplify::c3
IRMatcher::WildConst< 3 > c3
Definition Simplify_Internal.h:396
Halide::Internal::Simplify::visit
Expr visit(const UIntImm *op, ExprInfo *info)
Halide::Internal::Simplify::const_true
HALIDE_ALWAYS_INLINE Expr const_true(int lanes, ExprInfo *info)
Definition Simplify_Internal.h:280
Halide::Internal::Simplify::visit
Expr visit(const Add *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const Max *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const Mul *op, ExprInfo *info)
Halide::Internal::Simplify::c2
IRMatcher::WildConst< 2 > c2
Definition Simplify_Internal.h:395
Halide::Internal::Simplify::visit
Expr visit(const StringImm *op, ExprInfo *info)
Halide::Internal::Simplify::in_vector_loop
bool in_vector_loop
Definition Simplify_Internal.h:403
Halide::Internal::Simplify::var_info
Scope< VarInfo > var_info
Definition Simplify_Internal.h:381
Halide::Internal::Simplify::visit
Expr visit(const VectorReduce *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const Min *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const Reinterpret *op, ExprInfo *info)
Halide::Internal::Simplify::w
IRMatcher::Wild< 3 > w
Definition Simplify_Internal.h:390
Halide::Internal::Simplify::make_const
HALIDE_ALWAYS_INLINE Expr make_const(const Type &t, double c, ExprInfo *info)
Definition Simplify_Internal.h:269
Halide::Internal::Simplify::visit
Expr visit(const NE *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const For *op)
Halide::Internal::Simplify::visit
Expr visit(const Select *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const Atomic *op)
Halide::Internal::Simplify::visit
Expr visit(const Div *op, ExprInfo *info)
Halide::Internal::Simplify::make_const
Expr make_const(const Type &t, int64_t c, ExprInfo *info)
Definition Simplify_Internal.h:243
Halide::Internal::Simplify::visit
Expr visit(const GE *op, ExprInfo *info)
Halide::Internal::Simplify::normalize_constant
int64_t normalize_constant(const Type &t, int64_t c)
Definition Simplify_Internal.h:212
Halide::Internal::Simplify::visit
Stmt visit(const Provide *op)
Halide::Internal::Simplify::visit
Expr visit(const Not *op, ExprInfo *info)
Halide::Internal::Simplify::simplify_let
Body simplify_let(const T *op, ExprInfo *info)
Halide::Internal::Simplify::mutate_let_body
Expr mutate_let_body(const Expr &e, ExprInfo *info)
Definition Simplify_Internal.h:479
Halide::Internal::Simplify::visit
Expr visit(const Or *op, ExprInfo *info)
Halide::Internal::Simplify::x
IRMatcher::Wild< 0 > x
Definition Simplify_Internal.h:387
Halide::Internal::Simplify::visit
Expr visit(const FloatImm *op, ExprInfo *info)
Halide::Internal::Simplify::mutate_let_body
Stmt mutate_let_body(const Stmt &s, ExprInfo *)
Definition Simplify_Internal.h:476
Halide::Internal::Simplify::visit
Stmt visit(const Acquire *op)
Halide::Internal::Simplify::set_expr_info_to_constant
void set_expr_info_to_constant(ExprInfo *info, int64_t c) const
Definition Simplify_Internal.h:205
Halide::Internal::Simplify::visit
Stmt visit(const Fork *op)
Halide::Internal::Simplify::no_overflow_int
HALIDE_ALWAYS_INLINE bool no_overflow_int(Type t)
Definition Simplify_Internal.h:360
Halide::Internal::Simplify::truths
std::set< Expr, IRDeepCompare > truths
Definition Simplify_Internal.h:432
Halide::Internal::Simplify::scoped_falsehood
ScopedFact scoped_falsehood(const Expr &fact)
Definition Simplify_Internal.h:470
Halide::Internal::Simplify::should_commute
HALIDE_ALWAYS_INLINE bool should_commute(const Expr &a, const Expr &b)
Definition Simplify_Internal.h:415
Halide::Internal::Simplify::visit
Expr visit(const Broadcast *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const Sub *op, ExprInfo *info)
Halide::Internal::Simplify::mutate_with_changes
std::pair< std::vector< Expr >, bool > mutate_with_changes(const std::vector< Expr > &old_exprs)
Halide::Internal::Simplify::visit
Stmt visit(const Store *op)
Halide::Internal::Simplify::visit
Expr visit(const GT *op, ExprInfo *info)
Halide::Internal::Simplify::no_overflow_scalar_int
HALIDE_ALWAYS_INLINE bool no_overflow_scalar_int(Type t)
Definition Simplify_Internal.h:365
Halide::Internal::Simplify::make_const
Expr make_const(const Type &t, uint64_t c, ExprInfo *info)
Definition Simplify_Internal.h:249
Halide::Internal::Simplify::visit
Stmt visit(const Free *op)
Halide::Internal::Simplify::c4
IRMatcher::WildConst< 4 > c4
Definition Simplify_Internal.h:397
Halide::Internal::Simplify::visit
Expr visit(const Call *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const Allocate *op)
Halide::Internal::Simplify::visit
Stmt visit(const Realize *op)
Halide::Internal::Simplify::visit
Expr visit(const EQ *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Stmt visit(const LetStmt *op)
Halide::Internal::Simplify::falsehoods
std::set< Expr, IRDeepCompare > falsehoods
Definition Simplify_Internal.h:432
Halide::Internal::Simplify::visit
Expr visit(const IntImm *op, ExprInfo *info)
Halide::Internal::Simplify::visit
Expr visit(const And *op, ExprInfo *info)
Halide::Internal::VariadicVisitor
A visitor/mutator capable of passing arbitrary arguments to the visit methods using CRTP and returnin...
Definition IRVisitor.h:163
Halide::Internal::VariadicVisitor< Simplify, Expr, Stmt >::dispatch
HALIDE_ALWAYS_INLINE Stmt dispatch(const Stmt &s, Args &&...args)
Definition IRVisitor.h:337
Halide::Internal::as_const_int
std::optional< int64_t > as_const_int(const Expr &e)
If an expression is an IntImm or a Broadcast of an IntImm, return a its value.
Halide::Internal::as_const_uint
std::optional< uint64_t > as_const_uint(const Expr &e)
If an expression is a UIntImm or a Broadcast of a UIntImm, return its value.
Halide::Internal::make_const
Expr make_const(Type t, int64_t val)
Construct an immediate of the given type from any numeric C++ type.
Halide::Internal::is_signed_integer_overflow
bool is_signed_integer_overflow(const Expr &expr)
Check if an expression is a signed_integer_overflow.
Halide::Internal::mod_imp
T mod_imp(T a, T b)
Implementations of division and mod that are specific to Halide.
Definition IROperator.h:257
Halide::Internal::add_with_overflow
HALIDE_MUST_USE_RESULT bool add_with_overflow(int bits, int64_t a, int64_t b, int64_t *result)
Routines to perform arithmetic on signed types without triggering signed overflow.
Halide::Internal::sub_with_overflow
HALIDE_MUST_USE_RESULT bool sub_with_overflow(int bits, int64_t a, int64_t b, int64_t *result)
Halide::Internal::IRNodeType::Variable
@ Variable
Definition Expr.h:37
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition AbstractGenerator.h:19
Halide::UInt
Type UInt(int bits, int lanes=1)
Constructing an unsigned integer type.
Definition Type.h:546
uint64_t
unsigned __INT64_TYPE__ uint64_t
Definition runtime_internal.h:23
int64_t
signed __INT64_TYPE__ int64_t
Definition runtime_internal.h:22
Halide::Expr
A fragment of Halide syntax.
Definition Expr.h:258
Halide::Expr::type
HALIDE_ALWAYS_INLINE Type type() const
Get the type of this expression node.
Definition Expr.h:327
Halide::Internal::Acquire
Definition IR.h:872
Halide::Internal::Add
The sum of two expressions.
Definition IR.h:56
Halide::Internal::Allocate
Allocate a scratch area called with the given name, type, and size.
Definition IR.h:371
Halide::Internal::And
Logical and - are both expressions true.
Definition IR.h:175
Halide::Internal::AssertStmt
If the 'condition' is false, then evaluate and return the message, which should be a call to an error...
Definition IR.h:294
Halide::Internal::Atomic
Lock all the Store nodes in the body statement.
Definition IR.h:994
Halide::Internal::Block
A sequence of statements to be executed in-order.
Definition IR.h:442
Halide::Internal::Broadcast
A vector with 'lanes' elements, in which every element is 'value'.
Definition IR.h:259
Halide::Internal::Call
A function call.
Definition IR.h:490
Halide::Internal::Cast
The actual IR nodes begin here.
Definition IR.h:30
Halide::Internal::ConstantInterval
A class to represent ranges of integers.
Definition ConstantInterval.h:18
Halide::Internal::ConstantInterval::make_intersection
static ConstantInterval make_intersection(const ConstantInterval &a, const ConstantInterval &b)
Construct the largest interval contained within two intervals.
Halide::Internal::ConstantInterval::bounded_below
static ConstantInterval bounded_below(int64_t min)
Construct intervals bounded above or below.
Halide::Internal::ConstantInterval::single_point
static ConstantInterval single_point(int64_t x)
Construct an interval representing a single point.
Halide::Internal::Div
The ratio of two expressions.
Definition IR.h:83
Halide::Internal::EQ
Is the first expression equal to the second.
Definition IR.h:121
Halide::Internal::Evaluate
Evaluate and discard an expression, presumably because it has some side-effect.
Definition IR.h:476
Halide::Internal::FloatImm
Floating point constants.
Definition Expr.h:236
Halide::Internal::For
A for loop.
Definition IR.h:848
Halide::Internal::Fork
A pair of statements executed concurrently.
Definition IR.h:457
Halide::Internal::Free
Free the resources associated with the given buffer.
Definition IR.h:413
Halide::Internal::GE
Is the first expression greater than or equal to the second.
Definition IR.h:166
Halide::Internal::GT
Is the first expression greater than the second.
Definition IR.h:157
Halide::Internal::HoistedStorage
Represents a location where storage will be hoisted to for a Func / Realize node with a given name.
Definition IR.h:978
Halide::Internal::IRHandle::as
const T * as() const
Downcast this ir node to its actual type (e.g.
Definition Expr.h:205
Halide::Internal::IRHandle::node_type
IRNodeType node_type() const
Definition Expr.h:212
Halide::Internal::IRMatcher::WildConst
Definition IRMatch.h:396
Halide::Internal::IRMatcher::Wild
Definition IRMatch.h:454
Halide::Internal::IfThenElse
An if-then-else block.
Definition IR.h:466
Halide::Internal::IntImm
Integer constants.
Definition Expr.h:218
Halide::Internal::IntrusivePtr::same_as
HALIDE_ALWAYS_INLINE bool same_as(const IntrusivePtr &other) const
Definition IntrusivePtr.h:171
Halide::Internal::LE
Is the first expression less than or equal to the second.
Definition IR.h:148
Halide::Internal::LT
Is the first expression less than the second.
Definition IR.h:139
Halide::Internal::Let
A let expression, like you might find in a functional language.
Definition IR.h:271
Halide::Internal::LetStmt
The statement form of a let node.
Definition IR.h:282
Halide::Internal::Load
Load a value from a named symbol if predicate is true.
Definition IR.h:217
Halide::Internal::Max
The greater of two values.
Definition IR.h:112
Halide::Internal::Min
The lesser of two values.
Definition IR.h:103
Halide::Internal::Mod
The remainder of a / b.
Definition IR.h:94
Halide::Internal::ModulusRemainder
The result of modulus_remainder analysis.
Definition ModulusRemainder.h:33
Halide::Internal::ModulusRemainder::intersect
static ModulusRemainder intersect(const ModulusRemainder &a, const ModulusRemainder &b)
Halide::Internal::Mul
The product of two expressions.
Definition IR.h:74
Halide::Internal::NE
Is the first expression not equal to the second.
Definition IR.h:130
Halide::Internal::Not
Logical not - true if the expression false.
Definition IR.h:193
Halide::Internal::Or
Logical or - is at least one of the expression true.
Definition IR.h:184
Halide::Internal::Prefetch
Represent a multi-dimensional region of a Func or an ImageParam that needs to be prefetched.
Definition IR.h:956
Halide::Internal::ProducerConsumer
This node is a helpful annotation to do with permissions.
Definition IR.h:315
Halide::Internal::Provide
This defines the value of a function at a multi-dimensional location.
Definition IR.h:354
Halide::Internal::Ramp
A linear ramp vector node.
Definition IR.h:247
Halide::Internal::Realize
Allocate a multi-dimensional buffer of the given type and size.
Definition IR.h:427
Halide::Internal::Reinterpret
Reinterpret value as another type, without affecting any of the bits (on little-endian systems).
Definition IR.h:47
Halide::Internal::Select
A ternary operator.
Definition IR.h:204
Halide::Internal::Shuffle
Construct a new vector by taking elements from another sequence of vectors.
Definition IR.h:884
Halide::Internal::Simplify::ExprInfo::BitsKnown
Definition Simplify_Internal.h:153
Halide::Internal::Simplify::ExprInfo::BitsKnown::operator&
BitsKnown operator&(const BitsKnown &other) const
Definition Simplify_Internal.h:171
Halide::Internal::Simplify::ExprInfo::BitsKnown::all_bits_known
bool all_bits_known() const
Definition Simplify_Internal.h:167
Halide::Internal::Simplify::ExprInfo::BitsKnown::known_zeros
uint64_t known_zeros() const
Definition Simplify_Internal.h:159
Halide::Internal::Simplify::ExprInfo::BitsKnown::known_ones
uint64_t known_ones() const
Definition Simplify_Internal.h:163
Halide::Internal::Simplify::ExprInfo::BitsKnown::operator|
BitsKnown operator|(const BitsKnown &other) const
Definition Simplify_Internal.h:179
Halide::Internal::Simplify::ExprInfo::BitsKnown::operator^
BitsKnown operator^(const BitsKnown &other) const
Definition Simplify_Internal.h:187
Halide::Internal::Simplify::ExprInfo::BitsKnown::value
uint64_t value
Definition Simplify_Internal.h:157
Halide::Internal::Simplify::ExprInfo::BitsKnown::mask
uint64_t mask
Definition Simplify_Internal.h:155
Halide::Internal::Simplify::ExprInfo
Definition Simplify_Internal.h:39
Halide::Internal::Simplify::ExprInfo::largest_power_of_two_factor
uint64_t largest_power_of_two_factor(uint64_t x) const
Definition Simplify_Internal.h:83
Halide::Internal::Simplify::ExprInfo::intersect
void intersect(const ExprInfo &other)
Definition Simplify_Internal.h:132
Halide::Internal::Simplify::ExprInfo::bounds
ConstantInterval bounds
Definition Simplify_Internal.h:41
Halide::Internal::Simplify::ExprInfo::trim_bounds_using_alignment
void trim_bounds_using_alignment()
Definition Simplify_Internal.h:45
Halide::Internal::Simplify::ExprInfo::alignment
ModulusRemainder alignment
Definition Simplify_Internal.h:43
Halide::Internal::Simplify::ExprInfo::from_bits_known
void from_bits_known(BitsKnown known, const Type &type)
Halide::Internal::Simplify::ExprInfo::cast_to
void cast_to(Type t)
Definition Simplify_Internal.h:101
Halide::Internal::Simplify::ExprInfo::to_bits_known
BitsKnown to_bits_known(const Type &type) const
Halide::Internal::Simplify::ScopedFact
Definition Simplify_Internal.h:434
Halide::Internal::Simplify::ScopedFact::ScopedFact
ScopedFact(ScopedFact &&that)=default
Halide::Internal::Simplify::ScopedFact::learn_true
void learn_true(const Expr &fact)
Halide::Internal::Simplify::ScopedFact::learn_false
void learn_false(const Expr &fact)
Halide::Internal::Simplify::ScopedFact::bounds_pop_list
std::vector< const Variable * > bounds_pop_list
Definition Simplify_Internal.h:438
Halide::Internal::Simplify::ScopedFact::ScopedFact
ScopedFact(const ScopedFact &that)=delete
Halide::Internal::Simplify::ScopedFact::truths
std::set< Expr, IRDeepCompare > truths
Definition Simplify_Internal.h:439
Halide::Internal::Simplify::ScopedFact::pop_list
std::vector< const Variable * > pop_list
Definition Simplify_Internal.h:437
Halide::Internal::Simplify::ScopedFact::learn_lower_bound
void learn_lower_bound(const Variable *v, int64_t val)
Halide::Internal::Simplify::ScopedFact::falsehoods
std::set< Expr, IRDeepCompare > falsehoods
Definition Simplify_Internal.h:439
Halide::Internal::Simplify::ScopedFact::substitute_facts
Expr substitute_facts(const Expr &e)
Halide::Internal::Simplify::ScopedFact::ScopedFact
ScopedFact(Simplify *s)
Definition Simplify_Internal.h:450
Halide::Internal::Simplify::ScopedFact::simplify
Simplify * simplify
Definition Simplify_Internal.h:435
Halide::Internal::Simplify::ScopedFact::substitute_facts
Stmt substitute_facts(const Stmt &s)
Halide::Internal::Simplify::ScopedFact::~ScopedFact
~ScopedFact()
Halide::Internal::Simplify::ScopedFact::learn_upper_bound
void learn_upper_bound(const Variable *v, int64_t val)
Halide::Internal::Simplify::VarInfo
Definition Simplify_Internal.h:375
Halide::Internal::Simplify::VarInfo::replacement
Expr replacement
Definition Simplify_Internal.h:376
Halide::Internal::Simplify::VarInfo::old_uses
int old_uses
Definition Simplify_Internal.h:377
Halide::Internal::Simplify::VarInfo::new_uses
int new_uses
Definition Simplify_Internal.h:377
Halide::Internal::Stmt
A reference-counted handle to a statement node.
Definition Expr.h:427
Halide::Internal::Store
Store a 'value' to the buffer called 'name' at a given 'index' if 'predicate' is true.
Definition IR.h:333
Halide::Internal::StringImm
String constants.
Definition Expr.h:245
Halide::Internal::Sub
The difference of two expressions.
Definition IR.h:65
Halide::Internal::UIntImm
Unsigned integer constants.
Definition Expr.h:227
Halide::Internal::Variable
A named variable.
Definition IR.h:801
Halide::Internal::Variable::name
std::string name
Definition IR.h:802
Halide::Internal::VectorReduce
Horizontally reduce a vector to a scalar or narrower vector using the given commutative and associati...
Definition IR.h:1012
Halide::Type
Types in the halide type system.
Definition Type.h:283
Halide::Type::is_int
HALIDE_ALWAYS_INLINE bool is_int() const
Is this type a signed integer type?
Definition Type.h:435
Halide::Type::is_uint
HALIDE_ALWAYS_INLINE bool is_uint() const
Is this type an unsigned integer type?
Definition Type.h:441
Halide::Type::bits
HALIDE_ALWAYS_INLINE int bits() const
Return the bit size of a single element of this type.
Definition Type.h:349
Halide::Type::can_represent
bool can_represent(Type other) const
Can this type represent all values of another type?
Halide::Type::is_scalar
HALIDE_ALWAYS_INLINE bool is_scalar() const
Is this type a scalar type?
Definition Type.h:417
Halide::Type::is_float
HALIDE_ALWAYS_INLINE bool is_float() const
Is this type a floating point type (float or double).
Definition Type.h:423