Page MenuHomePhabricator

[WIP][ScalarEvolution] Try harder to prove overflow in howManyLessThans.
Needs ReviewPublic

Authored by efriedma on Mon, Jul 19, 6:24 PM.

Details

Reviewers
reames
mkazantsev
Summary

If we have an instruction "add nsw (IV - Stride), Stride" feeding into the icmp, we know Start - Stride doesn't overflow.

It's unfortunate we can't deduce this more directly, but we don't really have any SCEV infrastructure to support this sort of check.

Diff Detail

Unit TestsFailed

TimeTest
1,360 msx64 debian > MemProfiler-x86_64-linux-dynamic.TestCases::test_new_load_store.cpp
Script: -- : 'RUN: at line 5'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fmemory-profile -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -shared-libsan -O0 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/memprof/TestCases/test_new_load_store.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/memprof/X86_64LinuxDynamicConfig/TestCases/Output/test_new_load_store.cpp.tmp
2,670 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
2,800 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
2,850 msx64 debian > libarcher.races::critical-unrelated.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/critical-unrelated.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/critical-unrelated.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/critical-unrelated.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/critical-unrelated.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/critical-unrelated.c
2,920 msx64 debian > libarcher.races::lock-nested-unrelated.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/lock-nested-unrelated.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-nested-unrelated.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/lock-nested-unrelated.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-nested-unrelated.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/lock-nested-unrelated.c
View Full Test Results (17 Failed)

Event Timeline

efriedma created this revision.Mon, Jul 19, 6:24 PM
efriedma requested review of this revision.Mon, Jul 19, 6:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Jul 19, 6:24 PM
efriedma updated this revision to Diff 359979.Mon, Jul 19, 6:26 PM

Missed a test update

reames requested changes to this revision.Tue, Jul 20, 9:58 AM

Not really a fan of the structure of this change. Bear with me as I talk through a couple of approaches (only the last of which may work.)

Let me throw out an approach for this in terms of SCEVs. I'm going to use the variable names from foo1 in trip-count-unknown-stride.ll to make this understandable.
%i.05 = {0, +, %s}
%add = {0 + %s, +, %s}

The condition we need to prove is that (0 + %s - %s < 0 + %s. (Remember that the start here is in terms of %add, not %i.05.)

One tactic would be to prove (0 - %s) < 0. (i.e. cancel %s on either side - we don't care whether the addition of %s would wrap in that step.) This reduces to proving %s > 0. This is interesting as we already have a framework for proving strides positive. Maybe we can extend that?

Interestingly, we can do that with SCEV. Consider the following code:

if (!PositiveStride) {
  if (IsSigned && NoWrap &&
      isLoopInvariant(RHS, L) && IV->getStart() == Stride &&
      isLoopEntryGuardedByCond(L, Cond, getZero(RHS->getType()), RHS) && 
      loopIsFiniteByAssumption(L))
    PositiveStride = true;
}

I'd written this for another purpose which didn't work out, but I think the structure is valid. This is maybe too specific for a zero start on i.05 - though maybe we can generalize?

Anyways, that isn't a fully solution, but I'd strongly prefer you try to use a SCEV proof here over mixing IR and SCEV proofs.

This revision now requires changes to proceed.Tue, Jul 20, 9:58 AM
efriedma planned changes to this revision.Tue, Jul 20, 12:08 PM
efriedma updated this revision to Diff 360226.Tue, Jul 20, 12:12 PM
efriedma retitled this revision from [ScalarEvolution] Try harder to prove overflow in howManyLessThans. to [WIP][ScalarEvolution] Try harder to prove overflow in howManyLessThans..

Added another interesting case to look at. Still considering possible solutions that don't involve poking at IR directly.

The easiest thing here would be if SCEV recorded the flags somewhere... but unfortunately, we don't; when we discover the flags aren't universally applicable, we throw them away. We could try to construct some sort of side-table, I guess, to provide an API getNoWrapFlagsWithContext(SCEV*, Instruction*). So basically the same logic as this, but factored away.

One alternative I considered is looking at the nowrap flags of the AddRec "IV - Stride". We do often manage to deduce nsw/nuw, and if the backedge is taken, it proves Start - Stride doesn't overflow. But if we're doing that, I'm not sure how we prove the case where the backedge isn't taken.