Loading...
Searching...
No Matches
SimplifyCorrelatedDifferences.h
Go to the documentation of this file.
#ifndef HALIDE_SIMPLIFY_CORRELATED_DIFFERENCES
#define HALIDE_SIMPLIFY_CORRELATED_DIFFERENCES
#include "Expr.h"
/** \file
* Defines a simplification pass for handling differences of correlated expressions.
*/
namespace Halide {
namespace Internal {
/** Symbolic interval arithmetic can be extremely conservative in
* cases where we analyze the difference between two correlated
* expressions. For example, consider:
*
* for x in [0, 10]:
* let y = x + 3
* let z = y - x
*
* x lies within [0, 10]. Interval arithmetic will correctly determine
* that y lies within [3, 13]. When z is encountered, it is treated as
* a difference of two independent variables, and gives [3 - 10, 13 -
* 0] = [-7, 13] instead of the tighter interval [3, 3]. It
* doesn't understand that y and x are correlated.
*
* In practice, this problem causes problems for unrolling, and
* arbitrarily-bad overconservative behavior in bounds inference
* (e.g. https://github.com/halide/Halide/issues/3697 )
*
* The function below attempts to address this by walking the IR,
* remembering whether each let variable is monotonic increasing,
* decreasing, unknown, or constant w.r.t each loop var. When it
* encounters a subtract node where both sides have the same
* monotonicity it substitutes, solves, and attempts to generally
* simplify as aggressively as possible to try to cancel out the
* repeated dependence on the loop var. The same is done for addition
* nodes with arguments of opposite monotonicity.
*
* Bounds inference is particularly sensitive to these false
* dependencies, but removing false dependencies also helps other
* lowering passes. E.g. if this simplification means a value no
* longer depends on a loop variable, it can remain scalar during
* vectorization of that loop, or we can lift it out as a loop
* invariant, or it might avoid some of the complex paths in GPU
* codegen that trigger when values depend on the block index
* (e.g. warp shuffles).
*
* This pass is safe to use on code with repeated instances of the
* same variable name (it must be, because we want to run it before
* allocation bounds inference).
*/
Stmt simplify_correlated_differences(const Stmt &);
/** Refactor the expression to remove correlated differences
* or rewrite them in a form that is more amenable to bounds
* inference. Performs a subset of what `simplify_correlated_differences`
* does. Can increase Expr size (i.e. does not follow the simplifier's
* reduction order).
*/
Expr bound_correlated_differences(const Expr &expr);
} // namespace Internal
} // namespace Halide
#endif
Expr.h
Base classes for Halide expressions (Halide::Expr) and statements (Halide::Internal::Stmt).
Halide::Internal
Definition AbstractGenerator.h:24
Halide::Internal::bound_correlated_differences
Expr bound_correlated_differences(const Expr &expr)
Refactor the expression to remove correlated differences or rewrite them in a form that is more amena...
Halide::Internal::simplify_correlated_differences
Stmt simplify_correlated_differences(const Stmt &)
Symbolic interval arithmetic can be extremely conservative in cases where we analyze the difference b...
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition AbstractGenerator.h:19
Halide::Expr
A fragment of Halide syntax.
Definition Expr.h:258
Halide::Internal::Stmt
A reference-counted handle to a statement node.
Definition Expr.h:427