https://github.com/halide/Halide
Revision d5e425ee29f165b9de3527a267837093f99e59be authored by Pranav Bhandarkar on 28 October 2020, 20:19:40 UTC, committed by GitHub on 28 October 2020, 20:19:40 UTC
* Push lets near their uses (whenever possible) while CSEing +=

The CSE pass tries to do CSE jointly on the index and value of store nodes.
This is to stop:
f[x] = f[x] + y
from turning into
f[x] = f[z] + y
This is because the two 'x' indices are not CSE'd together.

However, one problem with jointly CSEing the store index and vaues
is that after CSEing, the pass puts the lets
(the values that were CSE'd) before the new store. That is we get,

let(t0...)
let(t1...)
f[t0] = f[t0] + function_of(t1)

Suppose however, there was nothing to CSE between the store index and value, that is
the index was unchanged after CSE. In that case, moving lets before the store puts the
lets too far away from their uses. This is ok except, there are passes like LoopCarry
that are beneficial when they are able to see a long continuous block of stores (eg. when
unrolling). But now, they'll see a long sequence of LetStmts.
Instead, if the index was unchanged after CSE, we should build up the stores as

f[x] = let(t0.. in (value));

This way LoopCarry is given a chance to see a series of stores.
Handling this in CSE, means the LoopCarry pass need not be complicated.

Change-Id: Iae19e1f69a6b38f3224a64b0c4781533e3862970

* In CSE, when we bundle together the store index and store value,
create LetStmts only for CSE'd values that are needed by the store index.
The rest can be Let expressions around the store value.

* Formatting fix for printing the IR after CSE

* Be smarter about pushing lets near their uses when CSEing +=

In a previous patch, in the code that handles CSEing += store operations,
we weren't general enough; we only handled the specific case when the
store index remained unchanged when CSE'd together with the store value.

This patch is more general. Even if the store index changes, only the
use-def chains created from the values used by the new store index that
end in defs created by CSE are retained as Let stmts around the new store.
Others go as Let expressions around the store value.

* Fix some formatting issues exposed by clang-format and remove
the inclusion of ExprUsesVar.h in CSE.cpp because it is not
used anymore.

* Use override in GetVarsUsed in CSE.cpp
1 parent 7896513
History
Tip revision: d5e425ee29f165b9de3527a267837093f99e59be authored by Pranav Bhandarkar on 28 October 2020, 20:19:40 UTC
Push lets near their uses (whenever possible) while CSEing += (#5387)
Tip revision: d5e425e
File Mode Size
.github
apps
cmake
dependencies
doc
packaging
python_bindings
src
test
tools
tutorial
util
.clang-format -rw-r--r-- 1.5 KB
.clang-format-ignore -rw-r--r-- 265 bytes
.clang-tidy -rw-r--r-- 1.8 KB
.gitattributes -rw-r--r-- 342 bytes
.gitignore -rw-r--r-- 1.1 KB
.gitmodules -rw-r--r-- 0 bytes
CMakeLists.txt -rw-r--r-- 4.5 KB
CODE_OF_CONDUCT.md -rw-r--r-- 3.5 KB
LICENSE.txt -rw-r--r-- 3.2 KB
Makefile -rw-r--r-- 94.7 KB
README.md -rw-r--r-- 20.8 KB
README_cmake.md -rw-r--r-- 66.5 KB
README_rungen.md -rw-r--r-- 12.1 KB
README_webassembly.md -rw-r--r-- 7.5 KB
run-clang-format.sh -rwxr-xr-x 1.1 KB
run-clang-tidy.sh -rwxr-xr-x 2.8 KB

README.md

back to top