Page MenuHomePhabricator

[IndVars] Use exit count reasoning to discharge obviously untaken exits
ClosedPublic

Authored by reames on Jun 24 2019, 12:23 PM.

Details

Summary

Continue in the spirit of D63618, and use exit count reasoning to prove away loop exits which can not be taken since the backedge taken count of the loop as a whole is provably less than the minimal BE count required to take this particular loop exit.

As demonstrated in the newly added tests, this triggers in a number of cases where IndVars was previously unable to discharge obviously redundant exit tests. And some not so obvious ones.

Suggestions on tests to exercise the backedge guard form would be very welcome. I'm not sure is the isKnownPredicate version actually gives us anything, but it's reasonable for completeness sake?

Diff Detail

Repository
rL LLVM

Event Timeline

reames created this revision.Jun 24 2019, 12:23 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 24 2019, 12:23 PM
nikic added inline comments.Jun 24 2019, 12:52 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
2734 ↗(On Diff #206276)

Some kind of copy and paste mistake? The second clause of the || fully subsumes the last.

reames marked an inline comment as done.Jun 25 2019, 10:33 AM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2734 ↗(On Diff #206276)

Yep, that should have been the backedge case. Good catch.

Now you see why I asked for ideas on how to test that case. :)

reames updated this revision to Diff 206493.Jun 25 2019, 11:46 AM

Address Nikita's catch.

reames updated this revision to Diff 208246.Jul 5 2019, 4:36 PM

Remove the untested code since no one suggested uses. Hopefully this should unblock review.

Some minor comments. Generally this makes sense but someone else should probably take a look as well.

lib/Transforms/Scalar/IndVarSimplify.cpp
2681 ↗(On Diff #208246)

BI, with this definition, is already available.

2709 ↗(On Diff #208246)

Same as above.

2717 ↗(On Diff #208246)

Same (non-trivial) code as above, could we extract it somehow?

reames updated this revision to Diff 208528.Jul 8 2019, 3:40 PM

Address review comments

reames marked 4 inline comments as done.Jul 8 2019, 3:42 PM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2717 ↗(On Diff #208246)

Seems like a reasonable suggestion. I'll explore options for a helper function in a follow on commit. We have this same pattern in a few other places as well.

nikic accepted this revision.Jul 11 2019, 1:21 PM

LGTM

lib/Transforms/Scalar/IndVarSimplify.cpp
2668 ↗(On Diff #208528)

nit: Unnecessary parens.

This revision is now accepted and ready to land.Jul 11 2019, 1:21 PM
This revision was automatically updated to reflect the committed changes.

The assertion assert(!ExitCount->isZero() && "Should have been folded above"); is failing during the unittest build on the UBSan bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/13940

FAILED: unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o 
/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang++   -DGTEST_HAS_RTTI=0 -DGTEST_HAS_TR1_TUPLE=0 -DGTEST_LANG_CXX11=1 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Iunittests/Support -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support -I/usr/include/libxml2 -Iinclude -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/include -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googletest/include -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googlemock/include -fsanitize=undefined -w -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -std=c++11 -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-class-memaccess -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -fno-omit-frame-pointer -gline-tables-only -fsanitize=undefined -fno-sanitize=vptr,function -fno-sanitize-recover=all -fsanitize-blacklist=/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/sanitizers/ubsan_blacklist.txt -fdiagnostics-color -ffunction-sections -fdata-sections -O3    -UNDEBUG  -Wno-variadic-macros -Wno-gnu-zero-variadic-macro-arguments -fno-exceptions -fno-rtti -MD -MT unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -MF unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o.d -o unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -c /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support/LEB128Test.cpp
clang-9: /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp:2813: bool {anonymous}::IndVarSimplify::run(llvm::Loop*): Assertion `!ExitCount->isZero() && "Should have been folded above"' failed.
Stack dump:
0.	Program arguments: /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -main-file-name LEB128Test.cpp -mrelocation-model pic -pic-level 2 -mthread-model posix -mdisable-fp-elim -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debug-info-kind=line-tables-only -dwarf-version=4 -debugger-tuning=gdb -ffunction-sections -fdata-sections -coverage-notes-file /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan/unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.gcno -resource-dir /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/lib/clang/9.0.0 -dependency-file unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o.d -sys-header-deps -MT unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -D GTEST_HAS_RTTI=0 -D GTEST_HAS_TR1_TUPLE=0 -D GTEST_LANG_CXX11=1 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I unittests/Support -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support -I /usr/include/libxml2 -I include -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/include -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googletest/include -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/unittest/googlemock/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-class-memaccess -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -Wno-variadic-macros -Wno-gnu-zero-variadic-macro-arguments -pedantic -w -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fsanitize=alignment,array-bounds,bool,builtin,enum,float-cast-overflow,integer-divide-by-zero,nonnull-attribute,null,object-size,pointer-overflow,return,returns-nonnull-attribute,shift-base,shift-exponent,signed-integer-overflow,unreachable,vla-bound -fsanitize-blacklist=/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/sanitizers/ubsan_blacklist.txt -fdepfile-entry=/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/utils/sanitizers/ubsan_blacklist.txt -fno-rtti -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -vectorize-loops -vectorize-slp -faddrsig -o unittests/Support/CMakeFiles/SupportTests.dir/LEB128Test.cpp.o -x c++ /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support/LEB128Test.cpp 
1.	<eof> parser at end of file
2.	Per-module optimization passes
3.	Running pass 'CallGraph Pass Manager' on module '/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/unittests/Support/LEB128Test.cpp'.
4.	Running pass 'Loop Pass Manager' on function '@_ZN12_GLOBAL__N_129LEB128Test_DecodeULEB128_Test8TestBodyEv'
5.	Running pass 'Induction Variable Simplification' on basic block '%do.body.i1427'
 #0 0x000056385b4fbb9a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2b1cb9a)
 #1 0x000056385b4f9925 llvm::sys::RunSignalHandlers() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2b1a925)
 #2 0x000056385b4f9a3c SignalHandler(int) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2b1aa3c)
 #3 0x00007f3bda1a10e0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x110e0)
 #4 0x00007f3bd8f60fff raise (/lib/x86_64-linux-gnu/libc.so.6+0x32fff)
 #5 0x00007f3bd8f6242a abort (/lib/x86_64-linux-gnu/libc.so.6+0x3442a)
 #6 0x00007f3bd8f59e67 (/lib/x86_64-linux-gnu/libc.so.6+0x2be67)
 #7 0x00007f3bd8f59f12 (/lib/x86_64-linux-gnu/libc.so.6+0x2bf12)
 #8 0x000056385b2ede4d (anonymous namespace)::IndVarSimplify::run(llvm::Loop*) (.part.484) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x290ee4d)
 #9 0x000056385b2ee9bf (anonymous namespace)::IndVarSimplifyLegacyPass::runOnLoop(llvm::Loop*, llvm::LPPassManager&) (.part.485) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x290f9bf)
#10 0x000056385a986f13 llvm::LPPassManager::runOnFunction(llvm::Function&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x1fa7f13)
#11 0x000056385af4c010 llvm::FPPassManager::runOnFunction(llvm::Function&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x256d010)
#12 0x000056385a8e16c5 (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x1f026c5)
#13 0x000056385af4cd54 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x256dd54)
#14 0x000056385b6f9a29 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2d1aa29)
#15 0x000056385b6fb358 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x2d1c358)
#16 0x000056385c106cfa clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3727cfa)
#17 0x000056385c99aac9 clang::ParseAST(clang::Sema&, bool, bool) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3fbbac9)
#18 0x000056385c104729 clang::CodeGenAction::ExecuteAction() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3725729)
#19 0x000056385bba1e41 clang::FrontendAction::Execute() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x31c2e41)
#20 0x000056385bb68c60 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3189c60)
#21 0x000056385bc48482 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0x3269482)
#22 0x0000563859933986 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0xf54986)
#23 0x00005638598a820d main (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0xec920d)
#24 0x00007f3bd8f4e2e1 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e1)
#25 0x000056385992fb4a _start (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-9+0xf50b4a)

Could someone please take a look?

The assertion assert(!ExitCount->isZero() && "Should have been folded above"); is failing during the unittest build on the UBSan bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/13940

I submitted a speculative fix for this in rL366241, but I'd really appreciate someone familiar with the bot extracting IR so that I can confirm there's only one issue here.