Halide 22.0.0 Halide compiler and libraries

SimplifyCorrelatedDifferences.h
Go to the documentation of this file.
1#ifndef HALIDE_SIMPLIFY_CORRELATED_DIFFERENCES
2#define HALIDE_SIMPLIFY_CORRELATED_DIFFERENCES
3
4#include "Expr.h"
5
6/** \file
7 * Defines a simplification pass for handling differences of correlated expressions.
8 */
9
10 namespace Halide {
11 namespace Internal {
12
13/** Symbolic interval arithmetic can be extremely conservative in
14 * cases where we analyze the difference between two correlated
15 * expressions. For example, consider:
16 *
17 * for x in [0, 10]:
18 * let y = x + 3
19 * let z = y - x
20 *
21 * x lies within [0, 10]. Interval arithmetic will correctly determine
22 * that y lies within [3, 13]. When z is encountered, it is treated as
23 * a difference of two independent variables, and gives [3 - 10, 13 -
24 * 0] = [-7, 13] instead of the tighter interval [3, 3]. It
25 * doesn't understand that y and x are correlated.
26 *
27 * In practice, this problem causes problems for unrolling, and
28 * arbitrarily-bad overconservative behavior in bounds inference
29 * (e.g. https://github.com/halide/Halide/issues/3697 )
30 *
31 * The function below attempts to address this by walking the IR,
32 * remembering whether each let variable is monotonic increasing,
33 * decreasing, unknown, or constant w.r.t each loop var. When it
34 * encounters a subtract node where both sides have the same
35 * monotonicity it substitutes, solves, and attempts to generally
36 * simplify as aggressively as possible to try to cancel out the
37 * repeated dependence on the loop var. The same is done for addition
38 * nodes with arguments of opposite monotonicity.
39 *
40 * Bounds inference is particularly sensitive to these false
41 * dependencies, but removing false dependencies also helps other
42 * lowering passes. E.g. if this simplification means a value no
43 * longer depends on a loop variable, it can remain scalar during
44 * vectorization of that loop, or we can lift it out as a loop
45 * invariant, or it might avoid some of the complex paths in GPU
46 * codegen that trigger when values depend on the block index
47 * (e.g. warp shuffles).
48 *
49 * This pass is safe to use on code with repeated instances of the
50 * same variable name (it must be, because we want to run it before
51 * allocation bounds inference).
52 */
53 Stmt simplify_correlated_differences(const Stmt &);
54
55/** Refactor the expression to remove correlated differences
56 * or rewrite them in a form that is more amenable to bounds
57 * inference. Performs a subset of what `simplify_correlated_differences`
58 * does. Can increase Expr size (i.e. does not follow the simplifier's
59 * reduction order).
60 */
61 Expr bound_correlated_differences(const Expr &expr);
62
63} // namespace Internal
64} // namespace Halide
65
66#endif
Expr.h
Base classes for Halide expressions (Halide::Expr) and statements (Halide::Internal::Stmt)
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::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
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