Page MenuHomePhabricator

[WIP][InstCombine] Enhance the sinking to handle multiple uses
Needs ReviewPublic

Authored by hyeongyukim on Jul 31 2021, 9:47 AM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Summary

This change will enhance InstCombine to sink more instructions.
Currently, only single-use instructions are sinking, and this
change will allow multiple uses to sink as well.

Diff Detail

Unit TestsFailed

TimeTest
50 msx64 debian > LLVM.Transforms/InstCombine::intptr7.ll
Script: -- : 'RUN: at line 2'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt < /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/InstCombine/intptr7.ll -instcombine -S | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/InstCombine/intptr7.ll
100 msx64 debian > LLVM.Transforms/LoopVectorize::first-order-recurrence.ll
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt < /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/LoopVectorize/first-order-recurrence.ll -loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -dce -instcombine -S | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/LoopVectorize/first-order-recurrence.ll
80 msx64 debian > LLVM.Transforms/LoopVectorize::float-induction.ll
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt < /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/LoopVectorize/float-induction.ll -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -dce -instcombine -S | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --check-prefix VEC4_INTERL1 /var/lib/buildkite-agent/builds/llvm-project/llvm/test/Transforms/LoopVectorize/float-induction.ll
4,560 msx64 debian > libarcher.races::task-dependency.c
Script: -- : 'RUN: at line 13'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests -I /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/runtime/src -L /var/lib/buildkite-agent/builds/llvm-project/build/lib -Wl,-rpath,/var/lib/buildkite-agent/builds/llvm-project/build/lib /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/task-dependency.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/task-dependency.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/deflake.bash /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/task-dependency.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/task-dependency.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/task-dependency.c
50 msx64 windows > LLVM.Transforms/InstCombine::intptr7.ll
Script: -- : 'RUN: at line 2'; c:\ws\w4\llvm-project\premerge-checks\build\bin\opt.exe < C:\ws\w4\llvm-project\premerge-checks\llvm\test\Transforms\InstCombine\intptr7.ll -instcombine -S | c:\ws\w4\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w4\llvm-project\premerge-checks\llvm\test\Transforms\InstCombine\intptr7.ll
View Full Test Results (7 Failed)

Event Timeline

hyeongyukim created this revision.Jul 31 2021, 9:47 AM
hyeongyukim requested review of this revision.Jul 31 2021, 9:47 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 31 2021, 9:47 AM
hyeongyukim retitled this revision from [InstCombine] Enhance the sinking to handle multiple uses to [WIP][InstCombine] Enhance the sinking to handle multiple uses.Jul 31 2021, 9:51 AM

The test files below should be modified manually.

Transforms/LoopVectorize/first-order-recurrence.ll
Transforms/LoopVectorize/float-induction.ll
Transforms/InstCombine/intptr7.ll

I will remove the WIP after modifying these files.

Thanks for trying, but yikes.
Like i expected, this has a pretty interesting effect on the compile time:
https://llvm-compile-time-tracker.com/compare.php?from=ad28ff71647503c0a93f8b23a04844484f26f52b&to=c159423d2c3146b4c00fd00bd0d64ce802a74e03&stat=instructions

While i do expect this could be improved somewhat (1. pass instruction's current BB into findCommonDominator() and stop looping once CommonDom becomes that 2. ???),
i do think it's unresolvable in general, because why do we even perform this sinking in instcombine in the first place, does it allow some further instcombine folds?
We'll re-perform the same sinking each time we visit each instruction, that's a lot. If we'd just did it once, it would basically compile-time free.
Just thinking out loud.

Do we have to sink instruction in InstCombine?
Since InstCombine visits many instructions, it would be good to sink instructions outside of InstCombine.
Creating passes such as InstSink and calling them only once may also be a solution. How do you think?