Page MenuHomePhabricator

[SCEV] Apply conditions involving constants first in applyLoopGuards.
Needs ReviewPublic

Authored by fhahn on May 26 2022, 2:30 PM.

Details

Summary

In some cases the order conditions are applied in can pessimize results.
In general, applying conditions with constant operands should lead to
better results. I think ideally we would apply conditions with operands
that are not involved in any other condition first, but processing
conditions with constants should be a good start.

Alternatively we could re-write all collected expressions after
collecting them. But that's likely more expensive.

Depends on D126460.

Fixes #55645.

Diff Detail

Unit TestsFailed

TimeTest
60,100 msx64 debian > AddressSanitizer-x86_64-linux-dynamic.TestCases::scariness_score_test.cpp
Script: -- : 'RUN: at line 4'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -shared-libasan -O0 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/scariness_score_test.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxDynamicConfig/TestCases/Output/scariness_score_test.cpp.tmp
60,130 msx64 debian > AddressSanitizer-x86_64-linux.TestCases::scariness_score_test.cpp
Script: -- : 'RUN: at line 4'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -O0 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/scariness_score_test.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxConfig/TestCases/Output/scariness_score_test.cpp.tmp
60,050 msx64 debian > MLIR.Examples/standalone::test.toy
Script: -- : 'RUN: at line 1'; /usr/bin/cmake /var/lib/buildkite-agent/builds/llvm-project/mlir/examples/standalone -G "Ninja" -DCMAKE_CXX_COMPILER=/usr/bin/clang++ -DCMAKE_C_COMPILER=/usr/bin/clang -DLLVM_ENABLE_LIBCXX=OFF -DMLIR_DIR=/var/lib/buildkite-agent/builds/llvm-project/build/lib/cmake/mlir ; /usr/bin/cmake --build . --target check-standalone | tee /var/lib/buildkite-agent/builds/llvm-project/build/tools/mlir/test/Examples/standalone/Output/test.toy.tmp | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/mlir/test/Examples/standalone/test.toy

Event Timeline

fhahn created this revision.May 26 2022, 2:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 26 2022, 2:30 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn requested review of this revision.May 26 2022, 2:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 26 2022, 2:30 PM
nikic added inline comments.May 26 2022, 3:11 PM
llvm/lib/Analysis/ScalarEvolution.cpp
14565

I don't understand this comparison function. If A is constant and B is not, this returns that A is smaller than B. If B is constant and A is not then ... this also returns that A is smaller than B?

fhahn planned changes to this revision.May 27 2022, 3:23 AM

Thanks for taking a look! Unfortunately this only worked by accident and I missed that there aren't any tests with the conditions in reverse order.

I think the real issue here is that we need to apply the conditions that constraint the value range first and the rewriting as multiple last.

fhahn updated this revision to Diff 432523.May 27 2022, 4:52 AM

Update sort order to apply conditions that constraint ranges using max/min (predicates != EQ & != NE).

This ensures we rewrite conditons involving URem checks last, which can lead to better results.

alonkom added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
14554

Even with this sorting won't we lose information about the min/max values of the value?
For example if we know (tc > 0) and (tc % 8 == 0) and we process (tc % 8 == 0) last, AFAIU the SCEV expression will be overridden to (tc / 8) * 8 and we'll lose the fact that the trip count is also positive.

nikic added inline comments.May 30 2022, 3:56 AM
llvm/lib/Analysis/ScalarEvolution.cpp
14563

There may be range comparisons using eq/ne as well, with != 0 probably being the only important one. Possibly we should not be collecting Terms but already classified conditions (i.e. either known factor or known range limit)?

mkazantsev added inline comments.Mon, Sep 26, 2:56 AM
llvm/lib/Analysis/ScalarEvolution.cpp
14560

Use isRelational