Page MenuHomePhabricator

[GVNHoist] Prune out useless CHI insertions
ClosedPublic

Authored by labrinea on Aug 6 2018, 1:46 AM.

Details

Summary

When I turned on GVNHoist, the ubsan buildbot crashed upon compiling SemaChecking.cpp with out of memory:

FAILED: tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.o 
/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang++   -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/clang/lib/Sema -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/tools/clang/lib/Sema -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/tools/clang/include -Itools/clang/include -I/usr/include/libxml2 -Iinclude -I/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/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 -Wcovered-switch-default -Wno-class-memaccess -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 -fno-common -Woverloaded-virtual -Wno-nested-anon-types -O3    -UNDEBUG  -fno-exceptions -fno-rtti -MD -MT tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.o -MF tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.o.d -o tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.o -c /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/tools/clang/lib/Sema/SemaChecking.cpp
LLVM ERROR: out of memory
Stack dump:
0.	Program arguments: /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -main-file-name SemaChecking.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 -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -coverage-notes-file /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan/tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.gcno -resource-dir /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/lib/clang/7.0.0 -dependency-file tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.o.d -sys-header-deps -MT tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.o -D GTEST_HAS_RTTI=0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/clang/lib/Sema -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/tools/clang/lib/Sema -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/tools/clang/include -I tools/clang/include -I /usr/include/libxml2 -I include -I /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/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/7.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 -Wcovered-switch-default -Wno-class-memaccess -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -Woverloaded-virtual -Wno-nested-anon-types -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,float-divide-by-zero,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 -fno-common -fdiagnostics-show-option -fcolor-diagnostics -vectorize-loops -vectorize-slp -o tools/clang/lib/Sema/CMakeFiles/clangSema.dir/SemaChecking.cpp.o -x c++ /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm/tools/clang/lib/Sema/SemaChecking.cpp -faddrsig 
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/tools/clang/lib/Sema/SemaChecking.cpp'.
4.	Running pass 'Early GVN Hoisting of Expressions' on function '@_ZN5clang4Sema22CheckHexagonBuiltinCpuEjPNS_8CallExprE'
#0 0x000055ea64e89e2a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x252de2a)
#1 0x000055ea64e88315 llvm::sys::RunSignalHandlers() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x252c315)
#2 0x000055ea64e8842c SignalHandler(int) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x252c42c)
#3 0x00007fb2ec32f0c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x110c0)
#4 0x00007fb2eb0eefff gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x32fff)
#5 0x00007fb2eb0f042a abort (/lib/x86_64-linux-gnu/libc.so.6+0x3442a)
#6 0x000055ea64e2cd8c llvm::report_bad_alloc_error(char const*, bool) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x24d0d8c)
#7 0x000055ea64c6d1df llvm::SmallVectorTemplateBase<llvm::CHIArg, false>::grow(unsigned long) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x23111df)
#8 0x000055ea64c76b55 llvm::GVNHoist::computeInsertionPoints(llvm::DenseMap<std::pair<unsigned int, unsigned int>, llvm::SmallVector<llvm::Instruction*, 4u>, llvm::DenseMapInfo<std::pair<unsigned int, unsigned int> >, llvm::detail::DenseMapPair<std::pair<unsigned int, unsigned int>, llvm::SmallVector<llvm::Instruction*, 4u> > > const&, llvm::SmallVector<std::pair<llvm::BasicBlock*, llvm::SmallVector<llvm::Instruction*, 4u> >, 4u>&, llvm::GVNHoist::InsKind) (.constprop.541) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x231ab55)
#9 0x000055ea64c77538 llvm::GVNHoist::hoistExpressions(llvm::Function&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x231b538)
#10 0x000055ea64c77d12 llvm::GVNHoist::run(llvm::Function&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x231bd12)
#11 0x000055ea64c78278 llvm::GVNHoistLegacyPass::runOnFunction(llvm::Function&) (.part.531) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x231c278)
#12 0x000055ea6495831f llvm::FPPassManager::runOnFunction(llvm::Function&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x1ffc31f)
#13 0x000055ea64360047 (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x1a04047)
#14 0x000055ea64958ef8 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x1ffcef8)
#15 0x000055ea65075ec0 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-7+0x2719ec0)
#16 0x000055ea65812a74 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x2eb6a74)
#17 0x000055ea65fcb669 clang::ParseAST(clang::Sema&, bool, bool) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x366f669)
#18 0x000055ea65811cd9 clang::CodeGenAction::ExecuteAction() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x2eb5cd9)
#19 0x000055ea654b0dee clang::FrontendAction::Execute() (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x2b54dee)
#20 0x000055ea6547c286 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x2b20286)
#21 0x000055ea65550a11 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0x2bf4a11)
#22 0x000055ea635c6b60 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0xc6ab60)
#23 0x000055ea63539442 main (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0xbdd442)
#24 0x00007fb2eb0dc2e1 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e1)
#25 0x000055ea635c278a _start (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build0/bin/clang-7+0xc6678a)
clang-7: error: unable to execute command: Aborted
clang-7: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 7.0.0 (trunk 338242)
Target: x86_64-unknown-linux-gnu
Thread model: posix

I've used a cache for inserted CHIs to avoid excessive memory usage.

Diff Detail

Event Timeline

labrinea created this revision.Aug 6 2018, 1:46 AM
xbolva00 added inline comments.Aug 6 2018, 3:34 AM
lib/Transforms/Scalar/GVNHoist.cpp
792

unsigned i = 0, e = V.size(); i < e; ++i

same below

xbolva00 added inline comments.Aug 6 2018, 3:38 AM
lib/Transforms/Scalar/GVNHoist.cpp
792

or better if possible.. for (auto &I : V) ?

labrinea added inline comments.Aug 6 2018, 6:28 AM
lib/Transforms/Scalar/GVNHoist.cpp
792

Seems a nit and irrelevant to my changes, but I could do that.

efriedma added inline comments.
lib/Transforms/Scalar/GVNHoist.cpp
158

DenseSet<std::pair<BasicBlock*, Instruction*>> is probably more efficient if you expect a small number of instructions per BB.

792

(If you do decide to fix this, please do it in a separate commit.)

803

If I'm following the code correctly, we push V.size() copies of C into OutValue[IDFB]? That seems weird; can you explain why we do that?

CachedCHIs is a set of instructions, but OutValue is a map of CHIArgs. A given instruction can have multiple value numbers, right? What's the impact of only allowing one of those numbers to be inserted in OutValue?

labrinea added inline comments.Aug 7 2018, 3:07 AM
lib/Transforms/Scalar/GVNHoist.cpp
803

If I'm following the code correctly, we push V.size() copies of C into OutValue[IDFB]? That seems weird; can you explain why we do that?

We create an empty CHI-node with the same Value Number for each instruction in V. Then in fillChiArgs() we fill the CHI-nodes using the Rename Stack, while walking the post-dominator tree top-down. Using ubsan I realized we create a huge amount of CHIs that correspond to the same <VN,Instr> pair for a given IDFB.

CachedCHIs is a set of instructions, but OutValue is a map of CHIArgs. A given instruction can have multiple value numbers, right? What's the impact of only allowing one of those numbers to be inserted in OutValue?

I think not. A given instruction has always the same Value Number. @sebpop do you have better insight on this? Maybe we could use something like this to be more assertive but I believe it's unnecessary:
using CHICache = DenseMap<BasicBlock *, SmallSet<std::pair<VNType, Instruction *>, 2>>;
(or a DenseSet if preferable)

A given instruction has always the same Value Number.

That is correct: the integer Number that GVN returns is the same for instructions that compute the same Values at run time.
Asking GVN to provide a number for a given instruction will result in the same integer.

efriedma added inline comments.Aug 8 2018, 11:40 AM
lib/Transforms/Scalar/GVNHoist.cpp
803

Okay, that makes sense.

So, is everyone happy with this change?

Seems fine to me.

lib/Transforms/Scalar/GVNHoist.cpp
158

You didn't reply to this comment?

labrinea added inline comments.Aug 10 2018, 5:29 AM
lib/Transforms/Scalar/GVNHoist.cpp
158

There are approximately 30 unit tests under llvm/test/Transforms/GVNHoist. I am not sure how representative they are compared to a real program. The maximum number of instructions for a given IDFB was 3.8 on average. I saw lots of 2s and a few 3s, 4s, 6s, 8s and 12s. When compiling SemaChecking.cpp the maximun number of instructions for a given IDFB was about 5000. I compiled the file both using a DenseSet of std::pair and a DenseMap of SmallPtrSet. The latter was approximately 20% faster (comparing only once). So what's the verdict? Maybe use a DenseMap with a SmallPtrSet of 4 or 8?

labrinea added inline comments.Aug 10 2018, 5:42 AM
lib/Transforms/Scalar/GVNHoist.cpp
158

I forgot to mention that the numbers in the above comment are without a sanitizer for the unit tests, and with ubsan for SemaChecking.cpp.

efriedma accepted this revision.Aug 10 2018, 12:11 PM

LGTM

lib/Transforms/Scalar/GVNHoist.cpp
158

If you've measured, I'll trust your numbers.

This revision is now accepted and ready to land.Aug 10 2018, 12:11 PM
hiraditya added inline comments.Aug 13 2018, 11:41 AM
lib/Transforms/Scalar/GVNHoist.cpp
803

A given instruction has always the same Value Number.

Correct!

Do you need help with pushing the changes?

Do you need help with pushing the changes?

Apologies for delaying this, I was out of office. I'll rebase and push it asap.

Closed by commit rL340818: [GVNHoist] Prune out useless CHI insertions (authored by alelab01, committed by ). · Explain WhyAug 28 2018, 4:08 AM
This revision was automatically updated to reflect the committed changes.