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
src
SimplifyCorrelatedDifferences.h
Generated by
1.8.17