Page MenuHomePhabricator

[LV] Support chained phis as incoming values for first-order recurs.
Changes PlannedPublic

Authored by fhahn on Feb 13 2022, 3:41 AM.

Details

Reviewers
Ayal
spatel
gilr
Summary

If the incoming previous value of a first-order recurrence is a phi in
the header, go through incoming values from the latch until we find a
non-phi value. Use this as the new Previous, all uses in the header
will be dominated by the original phi, but need to be moved after
the non-phi previous value.

Diff Detail

Unit TestsFailed

TimeTest
70 msx64 debian > LLVM.ExecutionEngine/JITLink/RISCV::ELF_jal.s
Script: -- : 'RUN: at line 1'; rm -rf /var/lib/buildkite-agent/builds/llvm-project/build/test/ExecutionEngine/JITLink/RISCV/Output/ELF_jal.s.tmp && mkdir -p /var/lib/buildkite-agent/builds/llvm-project/build/test/ExecutionEngine/JITLink/RISCV/Output/ELF_jal.s.tmp
100 msx64 debian > LLVM.Transforms/LoopVectorize::first-order-recurrence-chains.ll
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt -loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/LoopVectorize/first-order-recurrence-chains.ll | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/LoopVectorize/first-order-recurrence-chains.ll
60,040 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
70 msx64 debian > Polly.ScopInfo/NonAffine::non_affine_loop_used_later.ll
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt -polly-process-unprofitable -polly-remarks-minimal -polly-use-llvm-names -polly-import-jscop-dir=/var/lib/buildkite-agent/builds/llvm-project/polly/test/ScopInfo/NonAffine -polly-codegen-verify -polly-scops -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops -analyze < /var/lib/buildkite-agent/builds/llvm-project/polly/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/polly/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
60,050 msx64 debian > libFuzzer.libFuzzer::large.test
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -O2 -gline-tables-only -fsanitize=address,fuzzer -I/var/lib/buildkite-agent/builds/llvm-project/compiler-rt/lib/fuzzer -m64 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/fuzzer/LargeTest.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/fuzzer/X86_64DefaultLinuxConfig/Output/large.test.tmp-LargeTest

Event Timeline

fhahn created this revision.Feb 13 2022, 3:41 AM
fhahn requested review of this revision.Feb 13 2022, 3:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 13 2022, 3:41 AM
david-arm added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8886–8897

This change looks like it might potentially affect reductions too, since now we're potentially not recording the recipe for reductions. Should there be a reduction test for this too, or an assert that Ingredient2Recipe[Inc] is always non-null for reductions?

8888

nit: Should this just be !Ingredient2Recipe[Inc] as I thought LLVM convention wasn't to compare ==/!= with nullptr?

9268

nit: Whitespace change.

fhahn updated this revision to Diff 409651.Feb 17 2022, 7:39 AM

Address comments, make sure we record all first-order recurrence and reduction phi recipes, add assert .

fhahn marked 3 inline comments as done.Feb 17 2022, 7:43 AM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8886–8897

I don't think the change should impact reductions, as the code here only skips recording Inc if it is not already marked for recording. I added an assertion that if we already have a recipe recorded at this point, it must be a reduction or first-order recurrence phi.

8888

I think it would be best to use find() as not to insert new entries. Updated.

9268

removed , thanks!

fhahn planned changes to this revision.Feb 22 2022, 2:14 AM
fhahn marked 3 inline comments as done.

Need to make some changes before the next round of reviews.

bsmith added a subscriber: bsmith.Feb 28 2022, 3:00 AM
Allen added a subscriber: Allen.Mar 6 2022, 7:35 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 6 2022, 7:35 PM
TKaipeng added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8869

Should we record recipes for induction phis? It's possible to be the incoming value for later phis.

Is there any update on this change? It provides some nice improvements to various workloads we have been looking at and would be good to get in.

Is there any update on this change? It provides some nice improvements to various workloads we have been looking at and would be good to get in.

I'm planning to pick this up again fairly soon. There's some other work ongoing to break things up a bit and model codegen for entry & exit values explicitly. I think it would be good to make the transitions for first-order recurrence first and then update the patch.

Is there any update on this change? It provides some nice improvements to various workloads we have been looking at and would be good to get in.

I'm planning to pick this up again fairly soon. There's some other work ongoing to break things up a bit and model codegen for entry & exit values explicitly. I think it would be good to make the transitions for first-order recurrence first and then update the patch.

Hi, sorry to prod this again, is there any update on this, specifically which reviews/issues is this waiting on? We're very keen to push this forwards as it addresses some important issues for us, we are willing to help with development/patches in any areas that need it.