Page MenuHomePhabricator

[SimplifyCFG] Make ValueEqaulityComparison freeze-aware.
Needs ReviewPublic

Authored by hyeongyukim on Jul 25 2021, 8:44 PM.

Details

Summary
  cond1.fr = freeze(%v != 0)
  cond2.fr = freeze(%v == 0)
  br i1 %cond1.fr, label %body1, label %split

split:
  br %cond2.fr, label %body2, label %body3

%cond2.fr is always true in the split block.
But currently, this analysis is not performed when conditions are frozen.
This problem can be solved by modifying isValueEqualityComparison and GetValueEqualityComparisonCases.

Diff Detail

Unit TestsFailed

TimeTest
3,160 msx64 debian > libarcher.barrier::barrier.c
Script: -- : 'RUN: at line 14'; /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/barrier/barrier.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/barrier/Output/barrier.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/barrier/Output/barrier.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/barrier/Output/barrier.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/barrier/barrier.c
3,160 msx64 debian > libarcher.critical::critical.c
Script: -- : 'RUN: at line 15'; /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/critical/critical.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/critical.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/critical.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/critical.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/critical/critical.c
3,490 msx64 debian > libarcher.critical::lock.c
Script: -- : 'RUN: at line 15'; /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/critical/lock.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/lock.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/lock.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/lock.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/critical/lock.c
3,420 msx64 debian > libarcher.parallel::parallel-firstprivate.c
Script: -- : 'RUN: at line 15'; /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/parallel/parallel-firstprivate.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-firstprivate.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-firstprivate.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-firstprivate.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/parallel/parallel-firstprivate.c
3,210 msx64 debian > libarcher.parallel::parallel-simple2.c
Script: -- : 'RUN: at line 15'; /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/parallel/parallel-simple2.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple2.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple2.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple2.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/parallel/parallel-simple2.c
View Full Test Results (21 Failed)

Event Timeline

hyeongyukim created this revision.Jul 25 2021, 8:44 PM
hyeongyukim requested review of this revision.Jul 25 2021, 8:44 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2021, 8:44 PM

remove braces

hyeongyukim added a comment.EditedJul 25 2021, 9:01 PM

This patch was discovered in the process of solving D106041. (Like D106233)
If this patch is accepted, the performance regression caused by D106041 will be reduced.

hyeongyukim edited the summary of this revision. (Show Details)Jul 25 2021, 9:04 PM

Hmm.. would it make sense if SimplifyCFG also pushes freeze into icmp's arguments?

It's because it isn't clear whether isValueEqualityComparison should allow freeze(icmp eq x, y) or not..

Pushing the freeze into the operand of the icmp would be a lot easier to reason about; the existing code would just work. Not sure we can really do it effectively inside SimplifyCFG; we'd probably also need some code to merge freeze operations on the same value.

Trying to analyze (freeze (icmp a, b)) directly is potentially problematic. The biggest problem is that if the freeze has multiple uses, they have to evaluate to the same value. Some specific transforms might also need to introduce freeze operations.

nikic added a comment.Jul 26 2021, 2:20 PM

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

I'll ask a slightly different question.
Does simplifycfg itself insert said freeze that is problematic here, and thus blocks itselves forward progress?

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

I'll ask a slightly different question.
Does simplifycfg itself insert said freeze that is problematic here, and thus blocks itselves forward progress?

SimplyCFG does not insert Freeze. This freeze is inserted by loop unswitch.(D106041)

As the relevant optimizations already exist in InstCombine (D105392, D106233) is the motivation here a phase ordering problem? No InstCombine + SimplifyCFG runs at the relevant pipeline position?

You're right. This problem can be solved by D105392.
However, this problem may remain by order of Instcombine and SimplifyCFG.
How about calling pushFreezeToPreventPoisonFromPropagating(implemented by D105392) in SimplifyCFG? It will solve more general cases of performance degradation

I think something along the lines of the current patch could be fine, but i'm against doing instcombine's work here.

There are more problems caused by a freeze that is not yet pushed.
Is it okay to send separate patches to solve those problems?

I think something along the lines of the current patch could be fine, but i'm against doing instcombine's work here.

Can you tell me the things that would be good to modify in this patch?

aqjune added a comment.EditedJul 30 2021, 5:36 PM

If loop unswitch introduced the freeze, what about adding an extra InstCombine pass between the loop unswitch and SimplifyCFG?