[GVNHoist] Prune out useless CHI insertions

[labrinea]

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.

[xbolva00]

lib/Transforms/Scalar/GVNHoist.cpp

792

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

same below

[xbolva00]

lib/Transforms/Scalar/GVNHoist.cpp

792

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

[labrinea]

lib/Transforms/Scalar/GVNHoist.cpp

792

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

[efriedma]

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]

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)

[sebpop]

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]

lib/Transforms/Scalar/GVNHoist.cpp

803

Okay, that makes sense.

[labrinea]

So, is everyone happy with this change?

[efriedma]

Seems fine to me.

lib/Transforms/Scalar/GVNHoist.cpp

158

You didn't reply to this comment?

[labrinea]

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]

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]

LGTM

lib/Transforms/Scalar/GVNHoist.cpp

158

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

[hiraditya]

lib/Transforms/Scalar/GVNHoist.cpp

803

A given instruction has always the same Value Number.

Correct!

[hiraditya]

Do you need help with pushing the changes?

[labrinea]

In D50323#1205193, @hiraditya wrote:

Do you need help with pushing the changes?

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

[xbolva00]

Check https://bugs.llvm.org/show_bug.cgi?id=38912

[hiraditya]

https://bugs.llvm.org/show_bug.cgi?id=38807 has been fixed.

lib/Transforms/Scalar/GVNHoist.cpp

struct CHIArg {
   Instruction *I;
 
   bool operator==(const CHIArg &A) { return VN == A.VN; }
   bool operator!=(const CHIArg &A) { return !(*this == A); }
 };
 
 using CHIIt = SmallVectorImpl<CHIArg>::iterator;
 using CHIArgs = iterator_range<CHIIt>;
+using CHICache = DenseMap<BasicBlock *, SmallPtrSet<Instruction *, 2>>;
 using OutValuesType = DenseMap<BasicBlock *, SmallVector<CHIArg, 2>>;
 using InValuesType =
     DenseMap<BasicBlock *, SmallVector<std::pair<VNType, Instruction *>, 2>>;
 
 // An invalid value number Used when inserting a single value number into
 // VNtoInsns.
 enum : unsigned { InvalidVN = ~2U };
 
void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
     // - Remove the chi-nodes with missing entries
     // - Remove values from CHI-nodes which do not truly flow out, e.g.,
     //   modified along the path.
     // - Collect the remaining values that are still anticipable
     SmallVector<BasicBlock *, 2> IDFBlocks;
     ReverseIDFCalculator IDFs(*PDT);
     OutValuesType OutValue;
     InValuesType InValue;
+    CHICache CachedCHIs;
     for (const auto &R : Ranks) {
       const SmallVecInsn &V = Map.lookup(R);
       if (V.size() < 2)
         continue;
       const VNType &VN = R;
       SmallPtrSet<BasicBlock *, 2> VNBlocks;
       for (auto &I : V) {
         BasicBlock *BBI = I->getParent();
         if (!hasEH(BBI))
           VNBlocks.insert(BBI);
       }
       // Compute the Post Dominance Frontiers of each basic block
       // The dominance frontier of a live block X in the reverse
       // control graph is the set of blocks upon which X is control
       // dependent. The following sequence computes the set of blocks
       // which currently have dead terminators that are control
       // dependence sources of a block which is in NewLiveBlocks.
       IDFs.setDefiningBlocks(VNBlocks);
       IDFs.calculate(IDFBlocks);
 
       // Make a map of BB vs instructions to be hoisted.
       for (unsigned i = 0; i < V.size(); ++i) {
         InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
       }
       // Insert empty CHI node for this VN. This is used to factor out
       // basic blocks where the ANTIC can potentially change.
-      for (auto IDFB : IDFBlocks) { // TODO: Prune out useless CHI insertions.
+      for (auto IDFB : IDFBlocks) {
         for (unsigned i = 0; i < V.size(); ++i) {
           CHIArg C = {VN, nullptr, nullptr};
            // Ignore spurious PDFs.
-          if (DT->properlyDominates(IDFB, V[i]->getParent())) {
+          if (DT->properlyDominates(IDFB, V[i]->getParent()) &&
+              CachedCHIs[IDFB].insert(V[i]).second) {
             OutValue[IDFB].push_back(C);
             LLVM_DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->getName()
                               << ", for Insn: " << *V[i]);
           }
         }
       }
     }
 
     // Insert CHI args at each PDF to iterate on factored graph of