Halide
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 } // namespace Internal
56 } // namespace Halide
57 
58 #endif
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
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::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Expr.h