This is an archive of the discontinued LLVM Phabricator instance.

Paths

Table of Contentst

-
llvm/trunk/
-
trunk/
-
include/llvm/
-
llvm/
-
IR/
-
Dominators.h
-
Transforms/
-
Scalar/
-
JumpThreading.h
-
Utils/
-
BasicBlockUtils.h
-
Local.h
-
lib/
-
IR/
-
Dominators.cpp
-
Transforms/
-
Scalar/
-
CorrelatedValuePropagation.cpp
2
JumpThreading.cpp
-
Utils/
-
BasicBlockUtils.cpp
-
Local.cpp
-
test/
-
Analysis/LazyValueAnalysis/
-
LazyValueAnalysis/
-
lvi-after-jumpthreading.ll
-
Transforms/JumpThreading/
-
JumpThreading/
-
ddt-crash.ll
-
ddt-crash2.ll
-
lvi-tristate.ll
-
unittests/IR/
-
IR/
-
CMakeLists.txt
-
DeferredDominanceTest.cpp

Differential D40146

[JumpThreading] Preservation of DT and LVI across the pass
ClosedPublic

Authored by brzycki on Nov 16 2017, 12:38 PM.

Download Raw Diff

Details

Reviewers

• dberlin
kuhar
sebpop

Commits

rG9b7ae23256d8: [JumpThreading] Preservation of DT and LVI across the pass
rGcdad6c0b60d5: [JumpThreading] Preservation of DT and LVI across the pass
rGd989af98b302: [JumpThreading] Preservation of DT and LVI across the pass
rL322401: [JumpThreading] Preservation of DT and LVI across the pass
rL321825: [JumpThreading] Preservation of DT and LVI across the pass
rL320612: [JumpThreading] Preservation of DT and LVI across the pass

Summary

See D37528 for a previous (non-deferred) version of this patch and its description.

Preserves dominance in a deferred manner using a new class DeferredDominance. This reduces the performance impact of updating the DominatorTree at every edge insertion and deletion. A user may call DDT->flush() within JumpThreading for an up-to-date DT. This patch currently has one flush() at the end of runImpl() to ensure DT is preserved across the pass.

LVI is also preserved to help subsequent passes such as CorrelatedValuePropagation. LVI is simpler to maintain and is done immediately (not deferred). The code to perfom the preversation was minimally altered and was simply marked as preserved for the PassManager to be informed.

This extends the analysis available to JumpThreading for future enhancements. One example is loop boundary threading.

Diff Detail

Repository: rL LLVM

Event Timeline

brzycki created this revision.Nov 16 2017, 12:38 PM

Herald added a subscriber: hiraditya. · View Herald TranscriptNov 16 2017, 12:38 PM

This version passes make check and test-suite runs. It adds about 0.7-1.5% overhead to JumpThreading depending on the test case (and the run taken).

Comment and whitespace cleanup. NFC.

Ran lvi-tristate.ll through opt -metarenamer for consistency with the rest of LLVM. Also did another round of whitespace and comment fixes.

The patch looks good to me.
Please address the few inline comments and commit.

Thanks!

llvm/lib/Transforms/Scalar/JumpThreading.cpp
2025 ↗	(On Diff #125778)	Please add braces around the else clause.
llvm/lib/Transforms/Utils/Local.cpp
1858 ↗	(On Diff #125778)	Please move the ++I back in the body of the for loop and remove --I.

This revision is now accepted and ready to land.Dec 6 2017, 7:54 PM

Great work! I don't have time to check the jump-threading, but the dominance part looks solid. I only found a couple of issues.

llvm/include/llvm/IR/DeferredDominance.h
53 ↗	(On Diff #125778)	Can the DT ever be null within the class? If not, maybe it would make sense to keep a reference instead?
102 ↗	(On Diff #125778)	Maybe it'd make more sense to return a reference?
127 ↗	(On Diff #125778)	Shouldn't this be guarded by a macro? `LLVM_DUMP_METHOD` Can dump() be marked as const?
llvm/lib/IR/Dominators.cpp
402 ↗	(On Diff #125778)	This doesn't seem to modify any internal state, const should work here.
403 ↗	(On Diff #125778)	I think this should be llvm::dbgs
llvm/lib/Transforms/Scalar/JumpThreading.cpp
2474 ↗	(On Diff #125778)	I think we can reserve (2 * size(successors(SplitBB)) + 3 here to have a single allocation

Updated diff with @sebpop 's comments and rebased to tip.

Added updates from @kuhar 's review (Thanks Kuba!).

Comment cleanup to better match the code. NFC.

LGTM

brzycki mentioned this in D38559: [JumpThreading] Use runtime parameter to allow for DT and LVI preservation..Dec 7 2017, 2:25 PM

@dberlin Any objections to me committing this code?

llvm/include/llvm/IR/DeferredDominance.h
53 ↗	(On Diff #125778)	IT cannot be nullptr. I have changed it to a ref.
127 ↗	(On Diff #125778)	I wasn't aware of these wrapper macros for dump, thanks for pointing them out. Added.
llvm/lib/IR/Dominators.cpp
402 ↗	(On Diff #125778)	Agreed.
llvm/lib/Transforms/Scalar/JumpThreading.cpp
2474 ↗	(On Diff #125778)	I did this and also added others where the size was trivial to calculate.

kuhar added inline comments.Dec 8 2017, 1:17 PM

llvm/lib/Transforms/Scalar/JumpThreading.cpp
289 ↗	(On Diff #126034)	One remark: why new here instead of just putting it on the stack? If you need to pass the ownership around, who deallocates it?

Removed usage of "new" and rebased to tip.

kuhar added inline comments.Dec 12 2017, 7:11 AM

llvm/lib/Transforms/Scalar/JumpThreading.cpp
289 ↗	(On Diff #126034)	Nit: `DeferredDominance DDT = DeferredDominance(DT)` can be just `DeferredDominance DDT(DT);`

Cleaned up DDT init nit.

Fixed incorrectly-sized Update.reserve() call and resolved merge conflict to rebase onto tip.

brzycki retitled this revision from [JumpThreading] Deferred preservation of DT and LVI across the pass. to [JumpThreading] Preservation of DT and LVI across the pass.Dec 13 2017, 12:41 PM

brzycki edited the summary of this revision. (Show Details)

Closed by commit rL320612: [JumpThreading] Preservation of DT and LVI across the pass (authored by brzycki). · Explain WhyDec 13 2017, 12:53 PM

This revision was automatically updated to reflect the committed changes.

This patch caused a build break when attempting to use -fmodules due to a cyclic header dependency chain. I've refactored the patch to no longer use DeferredDominance.h (the code now lives as a class in Dominators.h). I also moved one of the methods into Dominators.cpp that needed Constants.h and Instructions.h. @sebpop and @kuhar could you please review again?

llvm/lib/Transforms/Scalar/JumpThreading.cpp
289 ↗	(On Diff #126034)	Ah, I forgot I had that. This is stale code from an older attempt at working the class into JumpThreading. I'll fix it in the next diff. Thanks for catching this.

This revision is now accepted and ready to land.Dec 14 2017, 2:27 PM

Refactored patch to prevent -fmodules circular dependency errors.

Which files and includes formed the cycle? There are a lot of files that require dominators.h, and I'm not convinced adding a new class to is a good idea, given that it currently has just one user.

In D40146#955920, @kuhar wrote:

Which files and includes formed the cycle? There are a lot of files that require dominators.h, and I'm not convinced adding a new class to is a good idea, given that it currently has just one user.

Hi @kuhar , this started with a BuildBot failure. After investigating further I recreated the problem locally and found the following error message:

[291/1841] Building CXX object lib/IR/CMakeFiles/LLVMCore.dir/IRBuilder.cpp.o
FAILED: lib/IR/CMakeFiles/LLVMCore.dir/IRBuilder.cpp.o
/work/brzycki/tip1/install/bin/clang++  -DGTEST_HAS_RTTI=0 -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/IR -I/work/brzycki/stage1/llvm-project/llvm/lib/IR -I/usr/include/libxml2 -Iinclude -I/work/brzycki/stage1/llvm-project/llvm/include -stdlib=libc++ -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -std=c++11 -fmodules -fmodules-cache-path=/work/brzycki/stage1/build/module.cache -Xclang -fmodules-local-submodule-visibility -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wcovered-switch-default -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -fcolor-diagnostics -ffunction-sections -fdata-sections -O3 -DNDEBUG    -fno-exceptions -fno-rtti -MD -MT lib/IR/CMakeFiles/LLVMCore.dir/IRBuilder.cpp.o -MF lib/IR/CMakeFiles/LLVMCore.dir/IRBuilder.cpp.o.d -o lib/IR/CMakeFiles/LLVMCore.dir/IRBuilder.cpp.o -c /work/brzycki/stage1/llvm-project/llvm/lib/IR/IRBuilder.cpp
While building module 'LLVM_intrinsic_gen' imported from /work/brzycki/stage1/llvm-project/llvm/lib/IR/IRBuilder.cpp:15:
While building module 'LLVM_IR' imported from /work/brzycki/stage1/llvm-project/llvm/include/llvm/IR/Argument.h:20:
In file included from <module-includes>:30:
/work/brzycki/stage1/llvm-project/llvm/include/llvm/IR/DeferredDominance.h:20:10: fatal error: cyclic dependency in module 'LLVM_intrinsic_gen': LLVM_intrinsic_gen -> LLVM_IR -> LLVM_intrinsic_gen
#include "llvm/IR/Dominators.h"
         ^
While building module 'LLVM_intrinsic_gen' imported from /work/brzycki/stage1/llvm-project/llvm/lib/IR/IRBuilder.cpp:15:
In file included from <module-includes>:1:
/work/brzycki/stage1/llvm-project/llvm/include/llvm/IR/Argument.h:20:10: fatal error: could not build module 'LLVM_IR'
#include "llvm/IR/Value.h"
 ~~~~~~~~^~~~~~~~~~~~~~~~~
/work/brzycki/stage1/llvm-project/llvm/lib/IR/IRBuilder.cpp:15:10: fatal error: could not build module 'LLVM_intrinsic_gen'
#include "llvm/IR/IRBuilder.h"
 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
3 errors generated.

This is the first of many showing the circular problem. What's worse is if I move only the offending method (delBB) into Dominators.cpp I start to get another set of cyclic errors due to the relatopnship between DeferredDominance.h and Dominators.h. I tried to keep DeferredDominance.h but could not find a way that satisfied -fmodules.

Here is another failure linking it directly to DeferredDominance.h:

[292/1841] Building CXX object lib/IR/CMakeFiles/LLVMCore.dir/BasicBlock.cpp.o
FAILED: lib/IR/CMakeFiles/LLVMCore.dir/BasicBlock.cpp.o
/work/brzycki/tip1/install/bin/clang++  -DGTEST_HAS_RTTI=0 -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/IR -I/work/brzycki/stage1/llvm-project/llvm/lib/IR -I/usr/include/libxml2 -Iinclude -I/work/brzycki/stage1/llvm-project/llvm/include -stdlib=libc++ -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -std=c++11 -fmodules -fmodules-cache-path=/work/brzycki/stage1/build/module.cache -Xclang -fmodules-local-submodule-visibility -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wcovered-switch-default -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -fcolor-diagnostics -ffunction-sections -fdata-sections -O3 -DNDEBUG    -fno-exceptions -fno-rtti -MD -MT lib/IR/CMakeFiles/LLVMCore.dir/BasicBlock.cpp.o -MF lib/IR/CMakeFiles/LLVMCore.dir/BasicBlock.cpp.o.d -o lib/IR/CMakeFiles/LLVMCore.dir/BasicBlock.cpp.o -c /work/brzycki/stage1/llvm-project/llvm/lib/IR/BasicBlock.cpp
While building module 'LLVM_IR' imported from /work/brzycki/stage1/llvm-project/llvm/lib/IR/BasicBlock.cpp:14:
While building module 'LLVM_intrinsic_gen' imported from /work/brzycki/stage1/llvm-project/llvm/include/llvm/IR/DeferredDominance.h:20:
In file included from <module-includes>:1:
/work/brzycki/stage1/llvm-project/llvm/include/llvm/IR/Argument.h:20:10: fatal error: cyclic dependency in module 'LLVM_IR': LLVM_IR -> LLVM_intrinsic_gen -> LLVM_IR
#include "llvm/IR/Value.h"
         ^
While building module 'LLVM_IR' imported from /work/brzycki/stage1/llvm-project/llvm/lib/IR/BasicBlock.cpp:14:
In file included from <module-includes>:30:
/work/brzycki/stage1/llvm-project/llvm/include/llvm/IR/DeferredDominance.h:20:10: fatal error: could not build module 'LLVM_intrinsic_gen'
#include "llvm/IR/Dominators.h"
 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/work/brzycki/stage1/llvm-project/llvm/lib/IR/BasicBlock.cpp:14:10: fatal error: could not build module 'LLVM_IR'
#include "llvm/IR/BasicBlock.h"
 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
3 errors generated.

In D40146#955920, @kuhar wrote:

Which files and includes formed the cycle? There are a lot of files that require dominators.h, and I'm not convinced adding a new class to is a good idea, given that it currently has just one user.

@kuhar would it help if I put all the larger functions in Dominators.cpp to prevent aggressive inlining? That would make it a relatively small class.

In D40146#956763, @brzycki wrote:

In D40146#955920, @kuhar wrote:

Which files and includes formed the cycle? There are a lot of files that require dominators.h, and I'm not convinced adding a new class to is a good idea, given that it currently has just one user.

@kuhar would it help if I put all the larger functions in Dominators.cpp to prevent aggressive inlining? That would make it a relatively small class.

That sounds better.

I wonder what caused the original cycle. I'm not entirely sure how modules are built, but have you tried getting rid of the include in Local.h? If that's not enough to break the cycle, I don't have any idea better than yours.

brzycki added a subscriber: rsmith.Dec 18 2017, 8:42 AM

I wonder what caused the original cycle. I'm not entirely sure how modules are built, but have you tried getting rid of the include in Local.h? If that's not enough to break the cycle, I don't have any idea better than yours.

It's a bit of a mystery to me how -fmodules actually works. I am getting cyclic errors when compiling a file that does not include either of Dominators.h or DeferredDominance.h. I have emailed @rsmith requesting his expertise if he can help us understand this.

I'm currently working on a version of the patch with no functions inlined in the header. I should have the updated diff available for review shortly.

Update patch with a minimal class definition of DeferredDominance in Dominators.h. Also removed an unnecessary #include of Dominators.h in JumpThreading.h

LGTM.
-fmodules can be fought in another patch.

LGTM

dmgreen mentioned this in D41302: [LoopSimplify] Preserve Post Dom Trees across Loop Simplify.Dec 19 2017, 10:27 AM

Getting patch ready to commit again. Rebased to llvm tip, rancheck, check-all, and test-suite on x86_64. Also passed building with LLVM_ENABLE_MODULES=1.

Looks good to me. Please commit. Thanks Brian!

Closed by commit rL321825: [JumpThreading] Preservation of DT and LVI across the pass (authored by brzycki). · Explain WhyJan 4 2018, 1:58 PM

This revision was automatically updated to reflect the committed changes.

I'm seeing crashes while building Chromium that I think are caused by this change. The stack trace follows. I will revert and prepare a standalone reproducer.
https://ci.chromium.org/buildbot/chromium.clang/ToTLinux/1285
https://logs.chromium.org/v/?s=chromium%2Fbb%2Fchromium.clang%2FToTLinux%2F1285%2F%2B%2Frecipes%2Fsteps%2Fcompile%2F0%2Fstdout

FAILED: obj/third_party/flatbuffers/compiler_files/idl_parser.o 
../../third_party/llvm-build/Release+Asserts/bin/clang++ -MMD -MF obj/third_party/flatbuffers/compiler_files/idl_parser.o.d -DV8_DEPRECATION_WARNINGS -DUSE_UDEV -DUSE_AURA=1 -DUSE_GLIB=1 -DUSE_NSS_CERTS=1 -DUSE_X11=1 -DFULL_SAFE_BROWSING -DSAFE_BROWSING_CSD -DSAFE_BROWSING_DB_LOCAL -DCHROMIUM_BUILD -DFIELDTRIAL_TESTING_ENABLED -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -D_LARGEFILE64_SOURCE -DCR_CLANG_REVISION=\"321826\" -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -DCOMPONENT_BUILD -DNDEBUG -DNVALGRIND -DDYNAMIC_ANNOTATIONS_ENABLED=0 -I../../third_party/flatbuffers/src/grpc -I../.. -Igen -I../../third_party/flatbuffers/src/include -fno-strict-aliasing --param=ssp-buffer-size=4 -fstack-protector -Wno-builtin-macro-redefined -D__DATE__= -D__TIME__= -D__TIMESTAMP__= -funwind-tables -fPIC -pipe -B../../third_party/binutils/Linux_x64/Release/bin -pthread -fcolor-diagnostics -Xclang -mllvm -Xclang -instcombine-lower-dbg-declare=0 -no-canonical-prefixes -m64 -march=x86-64 -Wall -Werror -Wextra -Wno-missing-field-initializers -Wno-unused-parameter -Wno-c++11-narrowing -Wno-covered-switch-default -Wno-unneeded-internal-declaration -Wno-inconsistent-missing-override -Wno-undefined-var-template -Wno-nonportable-include-path -Wno-address-of-packed-member -Wno-unused-lambda-capture -Wno-user-defined-warnings -Wno-enum-compare-switch -Wno-tautological-unsigned-zero-compare -Wno-null-pointer-arithmetic -Wno-tautological-constant-compare -Wtautological-constant-out-of-range-compare -O2 -fno-ident -fdata-sections -ffunction-sections -fno-omit-frame-pointer -g2 -ggnu-pubnames -fvisibility=hidden -Wheader-hygiene -Wstring-conversion -Wtautological-overlap-compare -Wno-exit-time-destructors -std=gnu++14 -fno-exceptions -fno-rtti -nostdinc++ -isystem../../buildtools/third_party/libc++/trunk/include -isystem../../buildtools/third_party/libc++abi/trunk/include --sysroot=../../build/linux/debian_stretch_amd64-sysroot -fvisibility-inlines-hidden -c ../../third_party/flatbuffers/src/src/idl_parser.cpp -o obj/third_party/flatbuffers/compiler_files/idl_parser.o
clang++: /b/c/b/ToTLinux/src/third_party/llvm/include/llvm/Support/GenericDomTreeConstruction.h:1107: static void llvm::DomTreeBuilder::SemiNCAInfo<DomTreeT>::EraseNode(DomTreeT&, llvm::DomTreeBuilder::SemiNCAInfo<DomTreeT>::TreeNodePtr) [with DomTreeT = llvm::DominatorTreeBase<llvm::BasicBlock, false>; llvm::DomTreeBuilder::SemiNCAInfo<DomTreeT>::TreeNodePtr = llvm::DomTreeNodeBase<llvm::BasicBlock>*; typename DomTreeT::NodeType = llvm::BasicBlock]: Assertion `TN->getNumChildren() == 0 && "Not a tree leaf"' failed.
#0 0x000000000222e74a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x222e74a)
#1 0x000000000222c82e llvm::sys::RunSignalHandlers() (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x222c82e)
#2 0x000000000222c992 SignalHandler(int) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x222c992)
#3 0x00007ff2fe151330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#4 0x00007ff2fcd40c37 gsignal /build/eglibc-SvCtMH/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#5 0x00007ff2fcd44028 abort /build/eglibc-SvCtMH/eglibc-2.19/stdlib/abort.c:91:0
#6 0x00007ff2fcd39bf6 __assert_fail_base /build/eglibc-SvCtMH/eglibc-2.19/assert/assert.c:92:0
#7 0x00007ff2fcd39ca2 (/lib/x86_64-linux-gnu/libc.so.6+0x2fca2)
#8 0x0000000001d5b3f6 llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::DeleteUnreachable(llvm::DominatorTreeBase<llvm::BasicBlock, false>&, llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::BatchUpdateInfo*, llvm::DomTreeNodeBase<llvm::BasicBlock>*) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1d5b3f6)
#9 0x0000000001d5b786 llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::DeleteEdge(llvm::DominatorTreeBase<llvm::BasicBlock, false>&, llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::BatchUpdateInfo*, llvm::BasicBlock*, llvm::BasicBlock*) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1d5b786)
#10 0x0000000001d640aa llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::ApplyNextUpdate(llvm::DominatorTreeBase<llvm::BasicBlock, false>&, llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::BatchUpdateInfo&) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1d640aa)
#11 0x0000000001d66e09 llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::ApplyUpdates(llvm::DominatorTreeBase<llvm::BasicBlock, false>&, llvm::ArrayRef<llvm::DomTreeBuilder::Update<llvm::BasicBlock*> >) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1d66e09)
#12 0x0000000001d67020 llvm::DeferredDominance::flush() (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1d67020)
#13 0x0000000002086930 llvm::JumpThreadingPass::runImpl(llvm::Function&, llvm::TargetLibraryInfo*, llvm::LazyValueInfo*, llvm::AAResults*, llvm::DeferredDominance*, bool, std::unique_ptr<llvm::BlockFrequencyInfo, std::default_delete<llvm::BlockFrequencyInfo> >, std::unique_ptr<llvm::BranchProbabilityInfo, std::default_delete<llvm::BranchProbabilityInfo> >) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x2086930)
#14 0x0000000002086f56 (anonymous namespace)::JumpThreading::runOnFunction(llvm::Function&) [clone .part.671] (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x2086f56)
#15 0x0000000001da84b3 llvm::FPPassManager::runOnFunction(llvm::Function&) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1da84b3)
#16 0x0000000001875f1f (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1875f1f)
#17 0x0000000001da8dff llvm::legacy::PassManagerImpl::run(llvm::Module&) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x1da8dff)
#18 0x00000000023c4a8b (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x23c4a8b)
#19 0x00000000023c5e07 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> >) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x23c5e07)
#20 0x0000000002ad9bab clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x2ad9bab)
#21 0x0000000002efd652 clang::ParseAST(clang::Sema&, bool, bool) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x2efd652)
#22 0x0000000002ad91ef clang::CodeGenAction::ExecuteAction() (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x2ad91ef)
#23 0x000000000277deb6 clang::FrontendAction::Execute() (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x277deb6)
#24 0x000000000275462e clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x275462e)
#25 0x000000000280fafb clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0x280fafb)
#26 0x0000000000bf1f98 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (../../third_party/llvm-build/Release+Asserts/bin/clang+++0xbf1f98)
#27 0x0000000000b836eb main (../../third_party/llvm-build/Release+Asserts/bin/clang+++0xb836eb)
#28 0x00007ff2fcd2bf45 __libc_start_main /build/eglibc-SvCtMH/eglibc-2.19/csu/libc-start.c:321:0
#29 0x0000000000bed219 _start (../../third_party/llvm-build/Release+Asserts/bin/clang+++0xbed219)

I made a reproducer and am reducing it. I'll upload it some time later today.

CReduce got this reduction, but I think you can go further:

struct a {
  int b;
};
class c {
public:
  c(bool) : d() {}
  ~c() {}
  bool e() { return d; }
  bool d;
};
class f : a {
  c g();
  c h();
  c i();
};
enum { j };
c f::h() {
  switch (b)
  case j: {
    auto a(i());
    if (a.e())
      return a;
  }
    return 0;
}
c f::i() {
  {
    auto b(g());
    if (b.e())
      return b;
  }
  return 0;
}

Use the command line clang -cc1 idl_parser.cpp -S -emit-llvm -O2 -o t.ll.

The patch was reverted in r321832 by @rnk for the following reason:

This reverts r321825, it causes crashes in Chromium. Reproducer forthcoming.

This revision is now accepted and ready to land.Jan 5 2018, 8:47 AM

In D40146#967965, @rnk wrote:

CReduce got this reduction, but I think you can go further:

Thank you @rnk for reducing the test case. I don't think you need to go further, I'll convert to llvm bytecode inside gdb and reduce with bugpoint once I verify the crash locally. Once there I'll post the .ll.

In D40146#968442, @brzycki wrote:

The patch was reverted in r321832 by @rnk for the following reason:

This reverts r321825, it causes crashes in Chromium. Reproducer forthcoming.

This is the reduced llvm IR that triggers the failure:

%struct.hoge = type { i8 }

define void @widget(%struct.hoge* noalias sret %arg) local_unnamed_addr #0 align 2 personality i8* bitcast (i32 (...)* @quux to i8*) {
bb:
  %tmp = load i32, i32* undef, align 4
  %tmp1 = icmp eq i32 %tmp, 0
  br i1 %tmp1, label %bb2, label %bb13

bb2:
  %tmp3 = getelementptr inbounds %struct.hoge, %struct.hoge* %arg, i64 0, i32 0
  %tmp4 = load i8, i8* %tmp3, align 1
  %tmp5 = icmp eq i8 %tmp4, 0
  br i1 %tmp5, label %bb6, label %bb7

bb6:
  store i8 0, i8* %tmp3, align 1
  br label %bb7

bb7:
  %tmp8 = load i8, i8* %tmp3, align 1
  %tmp9 = icmp ne i8 %tmp8, 0
  %tmp10 = select i1 %tmp9, i1 true, i1 false
  br i1 %tmp10, label %bb12, label %bb11

bb11:
  br label %bb12

bb12:
  br i1 %tmp9, label %bb14, label %bb13

bb13:
  unreachable

bb14:
  ret void
}

declare i32 @quux(...)

And compile with opt -S -jump-threading <foo.ll

I'm debugging it now and will add to ddt-crash.ll when I re-submit with a fix.

Fxed assert() caused when compiling Chrome.

Comments are inline describing where the patch was applied.

@kuhar if you have the time I would appreciate your feedback on the fix and if you're still ok with the patch.

llvm/lib/Transforms/Utils/Local.cpp
669 ↗	(On Diff #128964)	I did not see this fail in the specific case of the Chrome assert(). However, it is entirely possible on this code path for the same issue to occur which is why I added the check.
975 ↗	(On Diff #128964)	This check is the fix for the assert() discovered by @rnk . The shape of the IR had an existing edge from *I to Succ. Inserting was incorrect since the DT already had a pre-existing edge. It caused the balancing of Insertions/Deletions to be incorrect.
llvm/test/Transforms/JumpThreading/ddt-crash.ll
268 ↗	(On Diff #128964)	The reduced testcase that crashed LLVM discovered when compiling Chrome.

I'm a little bit worried that the tests depend on jumpthreading and it's not obvious what the sequence of operations on DDT is. It's difficult to come up with CFG for all the edge cases and I think it would be better to have something equivalent to the tests for DT and PDT incremental updates.
I'm OK with reapplying this, but when it causes a couple more crashes I'd strongly consider some more exhaustive testing approach.

llvm/lib/Transforms/Utils/Local.cpp
669 ↗	(On Diff #128964)	Looks reasonable. You can use llvm::find here, something like this `if (llvm::find(successors(I), DestBB) == succ_end(I))`
975 ↗	(On Diff #128964)	Just like above.
llvm/test/Transforms/JumpThreading/ddt-crash.ll
268 ↗	(On Diff #128964)	Wouldn't it be better to add it in a separate file?

I'm OK with reapplying this, but when it causes a couple more crashes I'd strongly consider some more exhaustive testing approach.

Thanks @kuhar for the review. I agree with you that DDT should have a unittest module and I've started work on it. I have the skeleton in place and am working on the actual tests now. I'm still trying to determine the set of unique CFG shapes/mutations to test for.

dmgreen added a subscriber: dmgreen.Jan 10 2018, 9:32 AM

Fixed Chrome build patch with suggestions from @kuhar . Added a first pass at DDT unit tests.

Herald added a subscriber: mgorny. · View Herald TranscriptJan 10 2018, 1:27 PM

Fixed comments in unit test.

Thanks for the tests, they look good to me. Found only some nits.

llvm/unittests/IR/DeferredDominanceTest.cpp
10 ↗	(On Diff #129526)	Unused?
57 ↗	(On Diff #129526)	While unlikely it makes a difference, it would be better to use `ASSERT(DDT.flush().verify())` instead -- it's able to catch much more errors and explain them. And the old verifier asserts upon failure, which can be surprising.
70 ↗	(On Diff #129526)	Nit: s/delete/Delete + missing comma at the end
95 ↗	(On Diff #129526)	`!isa<UnreachableInst>` would be more readable, or `ASSERT_NOT(isa<...>(...))`, if the library supports is.
99 ↗	(On Diff #129526)	`!isa<UnreachableInst>` would be more readable
105 ↗	(On Diff #129526)	Better to use `ASSERT(...verify())`
132 ↗	(On Diff #129526)	verify()
211 ↗	(On Diff #129526)	verify()
223 ↗	(On Diff #129526)	verify()
226 ↗	(On Diff #129526)	!isa
230 ↗	(On Diff #129526)	!isa
237 ↗	(On Diff #129526)	verify()
306 ↗	(On Diff #129526)	!isa
329 ↗	(On Diff #129526)	!isa
333 ↗	(On Diff #129526)	isa
344 ↗	(On Diff #129526)	verify()

@kuba Thank you again for the careful review. I'm uploading a new diff shortly. If you could give it a quick LGTM I'll try to push the patch to tip again today.

llvm/unittests/IR/DeferredDominanceTest.cpp
10 ↗	(On Diff #129526)	Yes. Removed.
57 ↗	(On Diff #129526)	Done. I used `ASSERT_TRUE(DDT.flush().verify())` because `ASSERT()` isn't a valid macro.
95 ↗	(On Diff #129526)	I'll use `isa<>` with the `ASSERT_TRUE()` and `ASSERT_FALSE()` macros.

Update nits in the unit test for clarity.

Looks good now, thanks for the changes!

llvm/unittests/IR/DeferredDominanceTest.cpp
212 ↗	(On Diff #129681)	Nit: missing comma.

Fixed punctuation in unit test comment. NFC.

Preparing to commit to SVN.

Closed by commit rL322401: [JumpThreading] Preservation of DT and LVI across the pass (authored by brzycki). · Explain WhyJan 12 2018, 1:08 PM

This revision was automatically updated to reflect the committed changes.

I'm currently seeing release+assert clang compilers apparently being stuck in an endless loop in the llvm test-suite (well I aborted after 10 minutes for a single file) hanging in some dominance tree verification code when I inspect the backtrace in lldb. Could this be caused by this commit?

In D40146#980980, @MatzeB wrote:

I'm currently seeing release+assert clang compilers apparently being stuck in an endless loop in the llvm test-suite (well I aborted after 10 minutes for a single file) hanging in some dominance tree verification code when I inspect the backtrace in lldb. Could this be caused by this commit?

Are you compiling with EXPENSIVE_CHECKS enabled? The full domtree verification is O(n^3), but is only run with expensive checks or -verify-dom-info, and can blow up on some weird CFG-s.

In D40146#981001, @kuhar wrote:

In D40146#980980, @MatzeB wrote:

I'm currently seeing release+assert clang compilers apparently being stuck in an endless loop in the llvm test-suite (well I aborted after 10 minutes for a single file) hanging in some dominance tree verification code when I inspect the backtrace in lldb. Could this be caused by this commit?

Are you compiling with EXPENSIVE_CHECKS enabled? The full domtree verification is O(n^3), but is only run with expensive checks or -verify-dom-info, and can blow up on some weird CFG-s.

Oh indeed, looks like my build had EXPENSIVE_CHECKS enabled (which was not intentional in this case)...

That said it's sad to not being able to compile the llvm test-suite with expensive checks enabled (in 60min at least)...

In D40146#981017, @MatzeB wrote:

That said it's sad to not being able to compile the llvm test-suite with expensive checks enabled (in 60min at least)...

What kind of machine are you using and how many threads do you allow it to create to run the test suite?

@dannyb

It's possible to make the verification O(N) but it's algorithmically incredibly complicated :)

Alternatively, we could make DT.verify() only run sibling property check when -verify-dom-info is set, and make it incomplete but O(N^2) with just EXPENSIVE_CHECKS. In my experience 99% of DT problems are caught in parent property check, so maybe that would be good enough?

In D40146#981028, @kuhar wrote:

In D40146#981017, @MatzeB wrote:

That said it's sad to not being able to compile the llvm test-suite with expensive checks enabled (in 60min at least)...

What kind of machine are you using and how many threads do you allow it to create to run the test suite?

That build was on a Core i5, 4 Cores @ 3.4Ghz with ninja spawning 6 clang processes (crosscompiling to aarch64).

Some files like sqlite3.c felt like they would never finish...

@dannyb

It's possible to make the verification O(N) but it's algorithmically incredibly complicated :)

Alternatively, we could make DT.verify() only run sibling property check when -verify-dom-info is set, and make it incomplete but O(N^2) with just EXPENSIVE_CHECKS. In my experience 99% of DT problems are caught in parent property check, so maybe that would be good enough?

I can't speak about the differences, but if the verifier is so slow that people will never finish the test-suite with expensive checks, then we won't catch problems there either...

In D40146#981043, @MatzeB wrote:

That build was on a Core i5, 4 Cores @ 3.4Ghz with ninja spawning 6 clang processes (crosscompiling to aarch64).

Some files like sqlite3.c felt like they would never finish...

Can you try timing it and setting the timeout higher? It would be interesting to get more data on how it performs. So far the only report I remember was about 2-core iMac or Mac-mini taking ~7 hours, but that's rather on the extreme side of the spectrum...

Just finished this:

time /Users/mbraun/lntenv/sandbox/test_suite_device_636d761d305a435b9592881371973ec4/compiler/bin/clang -DNDEBUG -I/Users/mbraun/lntenv/sandbox/test_suite_device_636d761d305a435b9592881371973ec4/test-suite/MultiSource/Applications/sqlite3 -IMultiSource/Applications/sqlite3 -B /Applications/Xcode.app/Contents/Developer/Toolchains/iOS11.1.xctoolchain/usr/bin -O3 -DNDEBUG -arch arm64 -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS11.1.Internal.sdk -w -Werror=date-time -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DSQLITE_OMIT_LOAD_EXTENSION=1 -DSQLITE_THREADSAFE=0 -I. -MD -MT MultiSource/Applications/sqlite3/CMakeFiles/sqlite3.dir/sqlite3.c.o -MF MultiSource/Applications/sqlite3/CMakeFiles/sqlite3.dir/sqlite3.c.o.d -o MultiSource/Applications/sqlite3/CMakeFiles/sqlite3.dir/sqlite3.c.o -c /Users/mbraun/lntenv/sandbox/test_suite_device_636d761d305a435b9592881371973ec4/test-suite/MultiSource/Applications/sqlite3/sqlite3.c -ftime-report
===-------------------------------------------------------------------------===
                         Miscellaneous Ungrouped Timers
===-------------------------------------------------------------------------===

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  6370.2168 (100.0%)  14.7216 ( 99.9%)  6384.9384 (100.0%)  7828.5324 (100.0%)  Code Generation Time
   0.2016 (  0.0%)   0.0144 (  0.1%)   0.2160 (  0.0%)   0.2402 (  0.0%)  LLVM IR Generation Time
  6370.4184 (100.0%)  14.7360 (100.0%)  6385.1544 (100.0%)  7828.7725 (100.0%)  Total

===-------------------------------------------------------------------------===
                              Register Allocation
===-------------------------------------------------------------------------===
  Total Execution Time: 0.4495 seconds (0.4523 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.4150 ( 92.9%)   0.0015 ( 49.4%)   0.4165 ( 92.7%)   0.4193 ( 92.7%)  Global Splitting
   0.0171 (  3.8%)   0.0004 ( 13.9%)   0.0176 (  3.9%)   0.0176 (  3.9%)  Spiller
   0.0106 (  2.4%)   0.0009 ( 30.6%)   0.0115 (  2.6%)   0.0115 (  2.5%)  Evict
   0.0037 (  0.8%)   0.0002 (  5.9%)   0.0039 (  0.9%)   0.0038 (  0.9%)  Seed Live Regs
   0.0001 (  0.0%)   0.0000 (  0.2%)   0.0001 (  0.0%)   0.0001 (  0.0%)  Local Splitting
   0.4465 (100.0%)   0.0030 (100.0%)   0.4495 (100.0%)   0.4523 (100.0%)  Total

===-------------------------------------------------------------------------===
                      Instruction Selection and Scheduling
===-------------------------------------------------------------------------===
  Total Execution Time: 2.8514 seconds (2.8514 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.7690 ( 27.6%)   0.0069 ( 10.6%)   0.7759 ( 27.2%)   0.7765 ( 27.2%)  Type Legalization
   0.5942 ( 21.3%)   0.0068 ( 10.4%)   0.6010 ( 21.1%)   0.6008 ( 21.1%)  Instruction Selection
   0.4215 ( 15.1%)   0.0066 ( 10.1%)   0.4281 ( 15.0%)   0.4282 ( 15.0%)  DAG Legalization
   0.3966 ( 14.2%)   0.0094 ( 14.4%)   0.4060 ( 14.2%)   0.4068 ( 14.3%)  DAG Combining 1
   0.2121 (  7.6%)   0.0066 ( 10.1%)   0.2187 (  7.7%)   0.2185 (  7.7%)  DAG Combining 2
   0.1681 (  6.0%)   0.0077 ( 11.9%)   0.1759 (  6.2%)   0.1753 (  6.1%)  Instruction Scheduling
   0.0892 (  3.2%)   0.0070 ( 10.8%)   0.0962 (  3.4%)   0.0961 (  3.4%)  Instruction Creation
   0.0848 (  3.0%)   0.0015 (  2.3%)   0.0863 (  3.0%)   0.0864 (  3.0%)  DAG Combining after legalize types
   0.0322 (  1.2%)   0.0063 (  9.7%)   0.0385 (  1.4%)   0.0383 (  1.3%)  Instruction Scheduling Cleanup
   0.0174 (  0.6%)   0.0064 (  9.8%)   0.0238 (  0.8%)   0.0235 (  0.8%)  Vector Legalization
   0.0007 (  0.0%)   0.0000 (  0.0%)   0.0007 (  0.0%)   0.0007 (  0.0%)  Type Legalization 2
   0.0002 (  0.0%)   0.0000 (  0.0%)   0.0002 (  0.0%)   0.0002 (  0.0%)  DAG Combining after legalize vectors
   2.7863 (100.0%)   0.0651 (100.0%)   2.8514 (100.0%)   2.8514 (100.0%)  Total

===-------------------------------------------------------------------------===
                                 DWARF Emission
===-------------------------------------------------------------------------===
  Total Execution Time: 0.0029 seconds (0.0029 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.0010 ( 57.7%)   0.0005 ( 43.8%)   0.0015 ( 52.3%)   0.0015 ( 52.5%)  DWARF Exception Writer
   0.0007 ( 40.2%)   0.0006 ( 56.0%)   0.0013 ( 46.3%)   0.0013 ( 46.1%)  Debug Info Emission
   0.0000 (  2.1%)   0.0000 (  0.2%)   0.0000 (  1.4%)   0.0000 (  1.3%)  DWARF Debug Writer
   0.0018 (100.0%)   0.0011 (100.0%)   0.0029 (100.0%)   0.0029 (100.0%)  Total

===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 6383.6554 seconds (7826.9875 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  1811.0822 ( 28.4%)   4.0908 ( 28.5%)  1815.1730 ( 28.4%)  2283.3040 ( 29.2%)  Dominator Tree Construction
  1382.5721 ( 21.7%)   3.1086 ( 21.7%)  1385.6807 ( 21.7%)  1746.6788 ( 22.3%)  Dominator Tree Construction
  1017.1956 ( 16.0%)   2.2479 ( 15.7%)  1019.4436 ( 16.0%)  1282.1470 ( 16.4%)  Dominator Tree Construction
  698.5721 ( 11.0%)   1.6101 ( 11.2%)  700.1822 ( 11.0%)  881.0982 ( 11.3%)  Dominator Tree Construction
  591.7651 (  9.3%)   1.0344 (  7.2%)  592.7994 (  9.3%)  648.0347 (  8.3%)  Dominator Tree Construction
  366.1419 (  5.7%)   0.8411 (  5.9%)  366.9830 (  5.7%)  461.8269 (  5.9%)  Dominator Tree Construction
  260.9003 (  4.1%)   0.1933 (  1.3%)  261.0936 (  4.1%)  261.1696 (  3.3%)  Dominator Tree Construction
  17.1747 (  0.3%)   0.0606 (  0.4%)  17.2353 (  0.3%)  21.9036 (  0.3%)  Dominator Tree Construction
   9.6751 (  0.2%)   0.0234 (  0.2%)   9.6985 (  0.2%)  12.1725 (  0.2%)  Unroll loops
   8.6642 (  0.1%)   0.0201 (  0.1%)   8.6843 (  0.1%)  10.9126 (  0.1%)  Dominator Tree Construction
   7.3346 (  0.1%)   0.0175 (  0.1%)   7.3521 (  0.1%)   9.2415 (  0.1%)  Dominator Tree Construction
   8.2538 (  0.1%)   0.0315 (  0.2%)   8.2853 (  0.1%)   8.2870 (  0.1%)  Verify generated machine code
   8.2532 (  0.1%)   0.0292 (  0.2%)   8.2824 (  0.1%)   8.2841 (  0.1%)  Verify generated machine code
   8.2382 (  0.1%)   0.0271 (  0.2%)   8.2654 (  0.1%)   8.2677 (  0.1%)  Verify generated machine code
   7.9754 (  0.1%)   0.0311 (  0.2%)   8.0065 (  0.1%)   8.0083 (  0.1%)  Verify generated machine code
   7.8422 (  0.1%)   0.0405 (  0.3%)   7.8828 (  0.1%)   7.8843 (  0.1%)  Verify generated machine code
   7.8252 (  0.1%)   0.0231 (  0.2%)   7.8483 (  0.1%)   7.8504 (  0.1%)  Verify generated machine code
   7.6636 (  0.1%)   0.0252 (  0.2%)   7.6889 (  0.1%)   7.6907 (  0.1%)  Verify generated machine code
   7.6414 (  0.1%)   0.0302 (  0.2%)   7.6716 (  0.1%)   7.6736 (  0.1%)  Verify generated machine code
   6.0292 (  0.1%)   0.0141 (  0.1%)   6.0433 (  0.1%)   7.6656 (  0.1%)  Dominator Tree Construction
   7.6319 (  0.1%)   0.0283 (  0.2%)   7.6602 (  0.1%)   7.6616 (  0.1%)  Verify generated machine code
   7.6192 (  0.1%)   0.0290 (  0.2%)   7.6483 (  0.1%)   7.6509 (  0.1%)  Verify generated machine code
   7.6059 (  0.1%)   0.0307 (  0.2%)   7.6366 (  0.1%)   7.6380 (  0.1%)  Verify generated machine code
   7.6062 (  0.1%)   0.0277 (  0.2%)   7.6339 (  0.1%)   7.6353 (  0.1%)  Verify generated machine code
   7.5977 (  0.1%)   0.0263 (  0.2%)   7.6240 (  0.1%)   7.6275 (  0.1%)  Verify generated machine code
   7.5916 (  0.1%)   0.0262 (  0.2%)   7.6179 (  0.1%)   7.6196 (  0.1%)  Verify generated machine code
   7.5885 (  0.1%)   0.0276 (  0.2%)   7.6161 (  0.1%)   7.6178 (  0.1%)  Verify generated machine code
   7.0549 (  0.1%)   0.0309 (  0.2%)   7.0858 (  0.1%)   7.1104 (  0.1%)  Verify generated machine code
   6.7323 (  0.1%)   0.0297 (  0.2%)   6.7620 (  0.1%)   6.7643 (  0.1%)  Verify generated machine code
   6.7279 (  0.1%)   0.0283 (  0.2%)   6.7563 (  0.1%)   6.7581 (  0.1%)  Verify generated machine code
   6.5326 (  0.1%)   0.0313 (  0.2%)   6.5640 (  0.1%)   6.5701 (  0.1%)  Verify generated machine code
   3.6521 (  0.1%)   0.0138 (  0.1%)   3.6658 (  0.1%)   4.5258 (  0.1%)  Natural Loop Information
   3.5962 (  0.1%)   0.1294 (  0.9%)   3.7256 (  0.1%)   3.7271 (  0.0%)  AArch64 Instruction Selection
   2.9391 (  0.0%)   0.0073 (  0.1%)   2.9464 (  0.0%)   3.7231 (  0.0%)  Dominator Tree Construction
   2.9442 (  0.0%)   0.0111 (  0.1%)   2.9553 (  0.0%)   3.7108 (  0.0%)  Natural Loop Information
   2.8810 (  0.0%)   0.0071 (  0.0%)   2.8881 (  0.0%)   3.6305 (  0.0%)  Conditionally eliminate dead library calls
   2.1528 (  0.0%)   0.0078 (  0.1%)   2.1606 (  0.0%)   2.6682 (  0.0%)  Natural Loop Information
   2.4722 (  0.0%)   0.0024 (  0.0%)   2.4746 (  0.0%)   2.4753 (  0.0%)  Dominator Tree Construction
   2.4647 (  0.0%)   0.0019 (  0.0%)   2.4666 (  0.0%)   2.4675 (  0.0%)  Dominator Tree Construction
   2.2790 (  0.0%)   0.0020 (  0.0%)   2.2809 (  0.0%)   2.2817 (  0.0%)  Dominator Tree Construction
   2.2531 (  0.0%)   0.0025 (  0.0%)   2.2556 (  0.0%)   2.2569 (  0.0%)  Dominator Tree Construction
   1.4120 (  0.0%)   0.0059 (  0.0%)   1.4178 (  0.0%)   1.8723 (  0.0%)  Natural Loop Information
   1.1641 (  0.0%)   0.0061 (  0.0%)   1.1702 (  0.0%)   1.4764 (  0.0%)  Global Value Numbering
   1.2461 (  0.0%)   0.0036 (  0.0%)   1.2496 (  0.0%)   1.3694 (  0.0%)  Natural Loop Information
   0.9376 (  0.0%)   0.0070 (  0.0%)   0.9446 (  0.0%)   1.1897 (  0.0%)  Function Integration/Inlining
   0.7963 (  0.0%)   0.0036 (  0.0%)   0.7999 (  0.0%)   1.0116 (  0.0%)  Natural Loop Information
   0.5423 (  0.0%)   0.0036 (  0.0%)   0.5459 (  0.0%)   0.6912 (  0.0%)  Loop-Closed SSA Form Pass
   0.6131 (  0.0%)   0.0063 (  0.0%)   0.6193 (  0.0%)   0.6229 (  0.0%)  Greedy Register Allocator
   0.5654 (  0.0%)   0.0021 (  0.0%)   0.5675 (  0.0%)   0.5673 (  0.0%)  Natural Loop Information
   0.4210 (  0.0%)   0.0029 (  0.0%)   0.4239 (  0.0%)   0.5253 (  0.0%)  Loop-Closed SSA Form Pass
   0.3984 (  0.0%)   0.0027 (  0.0%)   0.4011 (  0.0%)   0.4982 (  0.0%)  Combine redundant instructions
   0.4655 (  0.0%)   0.0041 (  0.0%)   0.4697 (  0.0%)   0.4696 (  0.0%)  MachineDominator Tree Construction
   0.3331 (  0.0%)   0.0015 (  0.0%)   0.3346 (  0.0%)   0.4409 (  0.0%)  Combine redundant instructions
   0.3392 (  0.0%)   0.0023 (  0.0%)   0.3415 (  0.0%)   0.4190 (  0.0%)  Memory SSA
   0.3212 (  0.0%)   0.0020 (  0.0%)   0.3231 (  0.0%)   0.4088 (  0.0%)  Induction Variable Simplification
   0.3208 (  0.0%)   0.0013 (  0.0%)   0.3220 (  0.0%)   0.4033 (  0.0%)  Combine redundant instructions
   0.3170 (  0.0%)   0.0014 (  0.0%)   0.3184 (  0.0%)   0.3923 (  0.0%)  Combine redundant instructions
   0.3066 (  0.0%)   0.0021 (  0.0%)   0.3087 (  0.0%)   0.3766 (  0.0%)  Dominator Tree Construction
   0.2977 (  0.0%)   0.0018 (  0.0%)   0.2995 (  0.0%)   0.3759 (  0.0%)  Dominator Tree Construction
   0.2807 (  0.0%)   0.0015 (  0.0%)   0.2822 (  0.0%)   0.3461 (  0.0%)  Jump Threading
   0.2826 (  0.0%)   0.0017 (  0.0%)   0.2843 (  0.0%)   0.3406 (  0.0%)  Loop Invariant Code Motion
   0.2603 (  0.0%)   0.0014 (  0.0%)   0.2617 (  0.0%)   0.3391 (  0.0%)  Combine redundant instructions
   0.2491 (  0.0%)   0.0009 (  0.0%)   0.2500 (  0.0%)   0.3350 (  0.0%)  Combine redundant instructions
   0.2363 (  0.0%)   0.0026 (  0.0%)   0.2389 (  0.0%)   0.3077 (  0.0%)  Value Propagation
   0.2211 (  0.0%)   0.0023 (  0.0%)   0.2234 (  0.0%)   0.2958 (  0.0%)  Value Propagation
   0.2552 (  0.0%)   0.0014 (  0.0%)   0.2566 (  0.0%)   0.2904 (  0.0%)  Loop Invariant Code Motion
   0.2106 (  0.0%)   0.0012 (  0.0%)   0.2118 (  0.0%)   0.2593 (  0.0%)  Loop Invariant Code Motion
   0.2006 (  0.0%)   0.0011 (  0.0%)   0.2017 (  0.0%)   0.2477 (  0.0%)  Jump Threading
   0.1906 (  0.0%)   0.0008 (  0.0%)   0.1914 (  0.0%)   0.2445 (  0.0%)  Combine redundant instructions
   0.1688 (  0.0%)   0.0012 (  0.0%)   0.1701 (  0.0%)   0.2214 (  0.0%)  Combine redundant instructions
   0.2186 (  0.0%)   0.0005 (  0.0%)   0.2191 (  0.0%)   0.2190 (  0.0%)  CodeGen Prepare
   0.2039 (  0.0%)   0.0011 (  0.0%)   0.2050 (  0.0%)   0.2052 (  0.0%)  Loop Strength Reduction
   0.1543 (  0.0%)   0.0012 (  0.0%)   0.1555 (  0.0%)   0.1961 (  0.0%)  Dominator Tree Construction
   0.1449 (  0.0%)   0.0013 (  0.0%)   0.1462 (  0.0%)   0.1786 (  0.0%)  Loop-Closed SSA Form Pass
   0.1419 (  0.0%)   0.0009 (  0.0%)   0.1428 (  0.0%)   0.1740 (  0.0%)  Loop-Closed SSA Form Pass
   0.1378 (  0.0%)   0.0009 (  0.0%)   0.1387 (  0.0%)   0.1699 (  0.0%)  Loop-Closed SSA Form Pass
   0.1411 (  0.0%)   0.0009 (  0.0%)   0.1421 (  0.0%)   0.1679 (  0.0%)  Loop-Closed SSA Form Pass
   0.1325 (  0.0%)   0.0011 (  0.0%)   0.1336 (  0.0%)   0.1608 (  0.0%)  Unroll loops
   0.1148 (  0.0%)   0.0009 (  0.0%)   0.1157 (  0.0%)   0.1537 (  0.0%)  Early CSE w/ MemorySSA
   0.1457 (  0.0%)   0.0004 (  0.0%)   0.1460 (  0.0%)   0.1461 (  0.0%)  Machine Instruction Scheduler
   0.1085 (  0.0%)   0.0014 (  0.0%)   0.1099 (  0.0%)   0.1438 (  0.0%)  Rotate Loops
   0.1248 (  0.0%)   0.0007 (  0.0%)   0.1255 (  0.0%)   0.1376 (  0.0%)  Loop-Closed SSA Form Pass
   0.1098 (  0.0%)   0.0012 (  0.0%)   0.1111 (  0.0%)   0.1338 (  0.0%)  SROA
   0.1266 (  0.0%)   0.0014 (  0.0%)   0.1279 (  0.0%)   0.1279 (  0.0%)  Live Interval Analysis
   0.1229 (  0.0%)   0.0013 (  0.0%)   0.1242 (  0.0%)   0.1241 (  0.0%)  Induction Variable Users
   0.1173 (  0.0%)   0.0004 (  0.0%)   0.1177 (  0.0%)   0.1179 (  0.0%)  Control Flow Optimizer
   0.1097 (  0.0%)   0.0013 (  0.0%)   0.1109 (  0.0%)   0.1109 (  0.0%)  MachineDominator Tree Construction
   0.1093 (  0.0%)   0.0004 (  0.0%)   0.1097 (  0.0%)   0.1104 (  0.0%)  Branch Probability Basic Block Placement
   0.0864 (  0.0%)   0.0005 (  0.0%)   0.0869 (  0.0%)   0.1040 (  0.0%)  SLP Vectorizer
   0.0992 (  0.0%)   0.0004 (  0.0%)   0.0996 (  0.0%)   0.0995 (  0.0%)  Simple Register Coalescing
   0.0934 (  0.0%)   0.0007 (  0.0%)   0.0942 (  0.0%)   0.0942 (  0.0%)  Live Variable Analysis
   0.0662 (  0.0%)   0.0008 (  0.0%)   0.0670 (  0.0%)   0.0925 (  0.0%)  Reassociate expressions
   0.0714 (  0.0%)   0.0023 (  0.0%)   0.0737 (  0.0%)   0.0922 (  0.0%)  Called Value Propagation
   0.0730 (  0.0%)   0.0007 (  0.0%)   0.0738 (  0.0%)   0.0906 (  0.0%)  Simplify the CFG
   0.0708 (  0.0%)   0.0004 (  0.0%)   0.0712 (  0.0%)   0.0893 (  0.0%)  Simplify the CFG
   0.0646 (  0.0%)   0.0007 (  0.0%)   0.0653 (  0.0%)   0.0856 (  0.0%)  Simplify the CFG
   0.0646 (  0.0%)   0.0014 (  0.0%)   0.0660 (  0.0%)   0.0816 (  0.0%)  Sparse Conditional Constant Propagation
   0.0559 (  0.0%)   0.0012 (  0.0%)   0.0571 (  0.0%)   0.0801 (  0.0%)  Unswitch loops
   0.0744 (  0.0%)   0.0006 (  0.0%)   0.0751 (  0.0%)   0.0773 (  0.0%)  Simplify the CFG
   0.0651 (  0.0%)   0.0007 (  0.0%)   0.0658 (  0.0%)   0.0751 (  0.0%)  Dead Store Elimination
   0.0740 (  0.0%)   0.0007 (  0.0%)   0.0746 (  0.0%)   0.0746 (  0.0%)  Verify generated machine code
   0.0543 (  0.0%)   0.0008 (  0.0%)   0.0551 (  0.0%)   0.0728 (  0.0%)  Module Verifier
   0.0710 (  0.0%)   0.0008 (  0.0%)   0.0718 (  0.0%)   0.0728 (  0.0%)  Verify generated machine code
   0.0694 (  0.0%)   0.0013 (  0.0%)   0.0707 (  0.0%)   0.0712 (  0.0%)  Verify generated machine code
   0.0688 (  0.0%)   0.0007 (  0.0%)   0.0695 (  0.0%)   0.0708 (  0.0%)  Verify generated machine code
   0.0685 (  0.0%)   0.0006 (  0.0%)   0.0690 (  0.0%)   0.0691 (  0.0%)  Verify generated machine code
   0.0381 (  0.0%)   0.0009 (  0.0%)   0.0390 (  0.0%)   0.0688 (  0.0%)  Natural Loop Information
   0.0674 (  0.0%)   0.0007 (  0.0%)   0.0681 (  0.0%)   0.0688 (  0.0%)  Verify generated machine code
   0.0677 (  0.0%)   0.0005 (  0.0%)   0.0683 (  0.0%)   0.0683 (  0.0%)  Verify generated machine code
   0.0676 (  0.0%)   0.0006 (  0.0%)   0.0682 (  0.0%)   0.0683 (  0.0%)  Verify generated machine code
   0.0676 (  0.0%)   0.0006 (  0.0%)   0.0682 (  0.0%)   0.0682 (  0.0%)  Verify generated machine code
   0.0672 (  0.0%)   0.0003 (  0.0%)   0.0675 (  0.0%)   0.0676 (  0.0%)  Verify generated machine code
   0.0661 (  0.0%)   0.0006 (  0.0%)   0.0667 (  0.0%)   0.0670 (  0.0%)  Verify generated machine code
   0.0661 (  0.0%)   0.0006 (  0.0%)   0.0668 (  0.0%)   0.0670 (  0.0%)  Verify generated machine code
   0.0653 (  0.0%)   0.0006 (  0.0%)   0.0658 (  0.0%)   0.0658 (  0.0%)  Verify generated machine code
   0.0640 (  0.0%)   0.0005 (  0.0%)   0.0644 (  0.0%)   0.0644 (  0.0%)  Module Verifier
   0.0407 (  0.0%)   0.0005 (  0.0%)   0.0411 (  0.0%)   0.0634 (  0.0%)  Loop Vectorization
   0.0510 (  0.0%)   0.0007 (  0.0%)   0.0516 (  0.0%)   0.0631 (  0.0%)  Simplify the CFG
   0.0478 (  0.0%)   0.0003 (  0.0%)   0.0481 (  0.0%)   0.0617 (  0.0%)  Simplify the CFG
   0.0591 (  0.0%)   0.0005 (  0.0%)   0.0597 (  0.0%)   0.0613 (  0.0%)  Verify generated machine code
   0.0551 (  0.0%)   0.0007 (  0.0%)   0.0558 (  0.0%)   0.0608 (  0.0%)  Aggressive Dead Code Elimination
   0.0576 (  0.0%)   0.0008 (  0.0%)   0.0584 (  0.0%)   0.0607 (  0.0%)  Verify generated machine code
   0.0600 (  0.0%)   0.0003 (  0.0%)   0.0603 (  0.0%)   0.0603 (  0.0%)  Verify generated machine code
   0.0570 (  0.0%)   0.0005 (  0.0%)   0.0575 (  0.0%)   0.0595 (  0.0%)  Verify generated machine code
   0.0581 (  0.0%)   0.0003 (  0.0%)   0.0584 (  0.0%)   0.0584 (  0.0%)  Verify generated machine code
   0.0571 (  0.0%)   0.0003 (  0.0%)   0.0574 (  0.0%)   0.0574 (  0.0%)  Machine code sinking
   0.0568 (  0.0%)   0.0003 (  0.0%)   0.0571 (  0.0%)   0.0571 (  0.0%)  Module Verifier
   0.0545 (  0.0%)   0.0020 (  0.0%)   0.0565 (  0.0%)   0.0566 (  0.0%)  AArch64 Assembly Printer
   0.0387 (  0.0%)   0.0009 (  0.0%)   0.0396 (  0.0%)   0.0564 (  0.0%)  Natural Loop Information
   0.0424 (  0.0%)   0.0007 (  0.0%)   0.0431 (  0.0%)   0.0562 (  0.0%)  Early CSE
   0.0492 (  0.0%)   0.0003 (  0.0%)   0.0496 (  0.0%)   0.0545 (  0.0%)  Remove redundant instructions
   0.0358 (  0.0%)   0.0009 (  0.0%)   0.0368 (  0.0%)   0.0522 (  0.0%)  Natural Loop Information
   0.0388 (  0.0%)   0.0026 (  0.0%)   0.0414 (  0.0%)   0.0516 (  0.0%)  Interprocedural Sparse Conditional Constant Propagation
   0.0506 (  0.0%)   0.0003 (  0.0%)   0.0509 (  0.0%)   0.0510 (  0.0%)  Eliminate PHI nodes for register allocation
   0.0463 (  0.0%)   0.0007 (  0.0%)   0.0470 (  0.0%)   0.0475 (  0.0%)  MachineDominator Tree Construction
   0.0385 (  0.0%)   0.0007 (  0.0%)   0.0392 (  0.0%)   0.0462 (  0.0%)  Bit-Tracking Dead Code Elimination
   0.0431 (  0.0%)   0.0008 (  0.0%)   0.0438 (  0.0%)   0.0439 (  0.0%)  Merge disjoint stack slots
   0.0371 (  0.0%)   0.0005 (  0.0%)   0.0376 (  0.0%)   0.0438 (  0.0%)  Loop Load Elimination
   0.0329 (  0.0%)   0.0006 (  0.0%)   0.0335 (  0.0%)   0.0432 (  0.0%)  Simplify the CFG
   0.0239 (  0.0%)   0.0003 (  0.0%)   0.0242 (  0.0%)   0.0430 (  0.0%)  Branch Probability Analysis
   0.0419 (  0.0%)   0.0003 (  0.0%)   0.0422 (  0.0%)   0.0421 (  0.0%)  Simplify the CFG
   0.0328 (  0.0%)   0.0009 (  0.0%)   0.0337 (  0.0%)   0.0417 (  0.0%)  Post-Dominator Tree Construction
   0.0336 (  0.0%)   0.0008 (  0.0%)   0.0344 (  0.0%)   0.0414 (  0.0%)  Simplify the CFG
   0.0147 (  0.0%)   0.0012 (  0.0%)   0.0158 (  0.0%)   0.0368 (  0.0%)  Recognize loop idioms
   0.0290 (  0.0%)   0.0006 (  0.0%)   0.0296 (  0.0%)   0.0365 (  0.0%)  Branch Probability Analysis
   0.0268 (  0.0%)   0.0006 (  0.0%)   0.0275 (  0.0%)   0.0365 (  0.0%)  SROA
   0.0196 (  0.0%)   0.0027 (  0.0%)   0.0223 (  0.0%)   0.0359 (  0.0%)  Scalar Evolution Analysis
   0.0333 (  0.0%)   0.0003 (  0.0%)   0.0336 (  0.0%)   0.0336 (  0.0%)  Virtual Register Rewriter
   0.0332 (  0.0%)   0.0003 (  0.0%)   0.0335 (  0.0%)   0.0335 (  0.0%)  Machine Loop Invariant Code Motion
   0.0322 (  0.0%)   0.0003 (  0.0%)   0.0325 (  0.0%)   0.0325 (  0.0%)  AArch64 load / store optimization pass
   0.0318 (  0.0%)   0.0003 (  0.0%)   0.0321 (  0.0%)   0.0321 (  0.0%)  Machine InstCombiner
   0.0313 (  0.0%)   0.0004 (  0.0%)   0.0317 (  0.0%)   0.0316 (  0.0%)  MachineDominator Tree Construction
   0.0201 (  0.0%)   0.0007 (  0.0%)   0.0208 (  0.0%)   0.0315 (  0.0%)  Block Frequency Analysis
   0.0297 (  0.0%)   0.0003 (  0.0%)   0.0301 (  0.0%)   0.0300 (  0.0%)  Machine Common Subexpression Elimination
   0.0144 (  0.0%)   0.0029 (  0.0%)   0.0173 (  0.0%)   0.0293 (  0.0%)  Canonicalize natural loops
   0.0186 (  0.0%)   0.0106 (  0.1%)   0.0292 (  0.0%)   0.0288 (  0.0%)  Insert stack protectors
   0.0212 (  0.0%)   0.0004 (  0.0%)   0.0216 (  0.0%)   0.0288 (  0.0%)  Branch Probability Analysis
   0.0283 (  0.0%)   0.0003 (  0.0%)   0.0286 (  0.0%)   0.0285 (  0.0%)  Peephole Optimizations
   0.0097 (  0.0%)   0.0128 (  0.1%)   0.0224 (  0.0%)   0.0278 (  0.0%)  Globals Alias Analysis
   0.0187 (  0.0%)   0.0006 (  0.0%)   0.0193 (  0.0%)   0.0265 (  0.0%)  Deduce function attributes
   0.0216 (  0.0%)   0.0006 (  0.0%)   0.0222 (  0.0%)   0.0260 (  0.0%)  Dominator Tree Construction
   0.0088 (  0.0%)   0.0154 (  0.1%)   0.0242 (  0.0%)   0.0244 (  0.0%)  Machine Module Information
   0.0163 (  0.0%)   0.0006 (  0.0%)   0.0169 (  0.0%)   0.0241 (  0.0%)  Tail Call Elimination
   0.0233 (  0.0%)   0.0004 (  0.0%)   0.0237 (  0.0%)   0.0237 (  0.0%)  Natural Loop Information
   0.0220 (  0.0%)   0.0004 (  0.0%)   0.0224 (  0.0%)   0.0224 (  0.0%)  Natural Loop Information
   0.0205 (  0.0%)   0.0001 (  0.0%)   0.0206 (  0.0%)   0.0220 (  0.0%)  Global Variable Optimizer
   0.0211 (  0.0%)   0.0003 (  0.0%)   0.0214 (  0.0%)   0.0213 (  0.0%)  MachinePostDominator Tree Construction
   0.0125 (  0.0%)   0.0024 (  0.0%)   0.0149 (  0.0%)   0.0212 (  0.0%)  Canonicalize natural loops
   0.0133 (  0.0%)   0.0006 (  0.0%)   0.0139 (  0.0%)   0.0211 (  0.0%)  Natural Loop Information
   0.0203 (  0.0%)   0.0002 (  0.0%)   0.0206 (  0.0%)   0.0206 (  0.0%)  Prologue/Epilogue Insertion & Frame Finalization
   0.0189 (  0.0%)   0.0005 (  0.0%)   0.0194 (  0.0%)   0.0204 (  0.0%)  Branch Probability Analysis
   0.0082 (  0.0%)   0.0120 (  0.1%)   0.0202 (  0.0%)   0.0202 (  0.0%)  Function Alias Analysis Results
   0.0146 (  0.0%)   0.0008 (  0.0%)   0.0155 (  0.0%)   0.0199 (  0.0%)  Natural Loop Information
   0.0194 (  0.0%)   0.0003 (  0.0%)   0.0196 (  0.0%)   0.0199 (  0.0%)  MachinePostDominator Tree Construction
   0.0190 (  0.0%)   0.0007 (  0.0%)   0.0197 (  0.0%)   0.0197 (  0.0%)  MachinePostDominator Tree Construction
   0.0138 (  0.0%)   0.0006 (  0.0%)   0.0143 (  0.0%)   0.0194 (  0.0%)  Natural Loop Information
   0.0181 (  0.0%)   0.0003 (  0.0%)   0.0183 (  0.0%)   0.0184 (  0.0%)  Branch Probability Analysis
   0.0142 (  0.0%)   0.0004 (  0.0%)   0.0146 (  0.0%)   0.0182 (  0.0%)  Block Frequency Analysis
   0.0178 (  0.0%)   0.0002 (  0.0%)   0.0180 (  0.0%)   0.0180 (  0.0%)  Machine Copy Propagation Pass
   0.0131 (  0.0%)   0.0009 (  0.0%)   0.0140 (  0.0%)   0.0180 (  0.0%)  Lazy Value Information Analysis
   0.0175 (  0.0%)   0.0005 (  0.0%)   0.0179 (  0.0%)   0.0179 (  0.0%)  Branch Probability Analysis
   0.0172 (  0.0%)   0.0003 (  0.0%)   0.0174 (  0.0%)   0.0174 (  0.0%)  MachineDominator Tree Construction
   0.0163 (  0.0%)   0.0003 (  0.0%)   0.0166 (  0.0%)   0.0169 (  0.0%)  MachineDominator Tree Construction
   0.0157 (  0.0%)   0.0006 (  0.0%)   0.0163 (  0.0%)   0.0163 (  0.0%)  MemCpy Optimization
   0.0126 (  0.0%)   0.0037 (  0.0%)   0.0163 (  0.0%)   0.0163 (  0.0%)  Free MachineFunction
   0.0160 (  0.0%)   0.0003 (  0.0%)   0.0163 (  0.0%)   0.0163 (  0.0%)  Two-Address instruction pass
   0.0111 (  0.0%)   0.0008 (  0.0%)   0.0118 (  0.0%)   0.0158 (  0.0%)  Canonicalize natural loops
   0.0155 (  0.0%)   0.0003 (  0.0%)   0.0158 (  0.0%)   0.0157 (  0.0%)  Dominator Tree Construction
   0.0147 (  0.0%)   0.0003 (  0.0%)   0.0150 (  0.0%)   0.0152 (  0.0%)  MachineDominator Tree Construction
   0.0134 (  0.0%)   0.0008 (  0.0%)   0.0143 (  0.0%)   0.0152 (  0.0%)  Lazy Value Information Analysis
   0.0080 (  0.0%)   0.0000 (  0.0%)   0.0080 (  0.0%)   0.0148 (  0.0%)  CallGraph Construction
   0.0118 (  0.0%)   0.0006 (  0.0%)   0.0124 (  0.0%)   0.0148 (  0.0%)  Block Frequency Analysis
   0.0026 (  0.0%)   0.0006 (  0.0%)   0.0032 (  0.0%)   0.0145 (  0.0%)  Scalar Evolution Analysis
   0.0142 (  0.0%)   0.0003 (  0.0%)   0.0144 (  0.0%)   0.0144 (  0.0%)  AArch64 Conditional Compares
   0.0130 (  0.0%)   0.0008 (  0.0%)   0.0138 (  0.0%)   0.0138 (  0.0%)  Machine Block Frequency Analysis
   0.0125 (  0.0%)   0.0012 (  0.0%)   0.0138 (  0.0%)   0.0138 (  0.0%)  Canonicalize natural loops
   0.0082 (  0.0%)   0.0003 (  0.0%)   0.0085 (  0.0%)   0.0133 (  0.0%)  Float to int
   0.0095 (  0.0%)   0.0033 (  0.0%)   0.0128 (  0.0%)   0.0128 (  0.0%)  Machine Natural Loop Construction
   0.0080 (  0.0%)   0.0000 (  0.0%)   0.0080 (  0.0%)   0.0127 (  0.0%)  CallGraph Construction
   0.0102 (  0.0%)   0.0025 (  0.0%)   0.0127 (  0.0%)   0.0126 (  0.0%)  Slot index numbering
   0.0119 (  0.0%)   0.0002 (  0.0%)   0.0122 (  0.0%)   0.0122 (  0.0%)  Block Frequency Analysis
   0.0114 (  0.0%)   0.0003 (  0.0%)   0.0118 (  0.0%)   0.0118 (  0.0%)  Block Frequency Analysis
   0.0051 (  0.0%)   0.0033 (  0.0%)   0.0084 (  0.0%)   0.0116 (  0.0%)  Function Alias Analysis Results
   0.0111 (  0.0%)   0.0003 (  0.0%)   0.0115 (  0.0%)   0.0115 (  0.0%)  Machine Block Frequency Analysis
   0.0110 (  0.0%)   0.0004 (  0.0%)   0.0114 (  0.0%)   0.0114 (  0.0%)  Machine Block Frequency Analysis
   0.0105 (  0.0%)   0.0007 (  0.0%)   0.0112 (  0.0%)   0.0112 (  0.0%)  Rotate Loops
   0.0098 (  0.0%)   0.0011 (  0.0%)   0.0109 (  0.0%)   0.0109 (  0.0%)  Delete dead loops
   0.0105 (  0.0%)   0.0002 (  0.0%)   0.0108 (  0.0%)   0.0108 (  0.0%)  Machine Block Frequency Analysis
   0.0103 (  0.0%)   0.0003 (  0.0%)   0.0106 (  0.0%)   0.0106 (  0.0%)  Remove dead machine instructions
   0.0102 (  0.0%)   0.0003 (  0.0%)   0.0105 (  0.0%)   0.0105 (  0.0%)  Constant Hoisting
   0.0095 (  0.0%)   0.0010 (  0.0%)   0.0105 (  0.0%)   0.0104 (  0.0%)  Scalar Evolution Analysis
   0.0100 (  0.0%)   0.0003 (  0.0%)   0.0103 (  0.0%)   0.0104 (  0.0%)  AArch64 Collect Linker Optimization Hint (LOH)
   0.0094 (  0.0%)   0.0008 (  0.0%)   0.0102 (  0.0%)   0.0102 (  0.0%)  Machine Natural Loop Construction
   0.0042 (  0.0%)   0.0021 (  0.0%)   0.0063 (  0.0%)   0.0099 (  0.0%)  Function Alias Analysis Results
   0.0045 (  0.0%)   0.0003 (  0.0%)   0.0047 (  0.0%)   0.0099 (  0.0%)  Canonicalize natural loops
   0.0076 (  0.0%)   0.0021 (  0.0%)   0.0097 (  0.0%)   0.0098 (  0.0%)  Scalar Evolution Analysis
   0.0090 (  0.0%)   0.0007 (  0.0%)   0.0097 (  0.0%)   0.0097 (  0.0%)  Canonicalize natural loops
   0.0087 (  0.0%)   0.0008 (  0.0%)   0.0095 (  0.0%)   0.0095 (  0.0%)  Slot index numbering
   0.0036 (  0.0%)   0.0005 (  0.0%)   0.0041 (  0.0%)   0.0094 (  0.0%)  Function Alias Analysis Results
   0.0091 (  0.0%)   0.0004 (  0.0%)   0.0095 (  0.0%)   0.0094 (  0.0%)  Remove dead machine instructions
   0.0088 (  0.0%)   0.0002 (  0.0%)   0.0090 (  0.0%)   0.0090 (  0.0%)  Machine Natural Loop Construction
   0.0087 (  0.0%)   0.0002 (  0.0%)   0.0090 (  0.0%)   0.0090 (  0.0%)  Machine Loop Invariant Code Motion
   0.0085 (  0.0%)   0.0006 (  0.0%)   0.0090 (  0.0%)   0.0090 (  0.0%)  Canonicalize natural loops
   0.0087 (  0.0%)   0.0002 (  0.0%)   0.0090 (  0.0%)   0.0090 (  0.0%)  Natural Loop Information
   0.0027 (  0.0%)   0.0018 (  0.0%)   0.0045 (  0.0%)   0.0089 (  0.0%)  Function Alias Analysis Results
   0.0089 (  0.0%)   0.0000 (  0.0%)   0.0089 (  0.0%)   0.0089 (  0.0%)  Global Variable Optimizer
   0.0040 (  0.0%)   0.0030 (  0.0%)   0.0070 (  0.0%)   0.0088 (  0.0%)  Globals Alias Analysis
   0.0083 (  0.0%)   0.0003 (  0.0%)   0.0085 (  0.0%)   0.0088 (  0.0%)  Machine Natural Loop Construction
   0.0080 (  0.0%)   0.0005 (  0.0%)   0.0085 (  0.0%)   0.0087 (  0.0%)  Machine Natural Loop Construction
   0.0082 (  0.0%)   0.0002 (  0.0%)   0.0085 (  0.0%)   0.0085 (  0.0%)  Loop Data Prefetch
   0.0079 (  0.0%)   0.0006 (  0.0%)   0.0085 (  0.0%)   0.0084 (  0.0%)  Promote 'by reference' arguments to scalars
   0.0037 (  0.0%)   0.0046 (  0.0%)   0.0083 (  0.0%)   0.0084 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0078 (  0.0%)   0.0004 (  0.0%)   0.0082 (  0.0%)   0.0082 (  0.0%)  Machine Natural Loop Construction
   0.0074 (  0.0%)   0.0003 (  0.0%)   0.0077 (  0.0%)   0.0078 (  0.0%)  Machine Natural Loop Construction
   0.0045 (  0.0%)   0.0000 (  0.0%)   0.0045 (  0.0%)   0.0078 (  0.0%)  Dead Argument Elimination
   0.0075 (  0.0%)   0.0002 (  0.0%)   0.0077 (  0.0%)   0.0077 (  0.0%)  AArch64 Dead register definitions
   0.0027 (  0.0%)   0.0026 (  0.0%)   0.0054 (  0.0%)   0.0074 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0073 (  0.0%)   0.0000 (  0.0%)   0.0074 (  0.0%)   0.0074 (  0.0%)  AArch64 Promote Constant
   0.0049 (  0.0%)   0.0006 (  0.0%)   0.0055 (  0.0%)   0.0073 (  0.0%)  Memory Dependence Analysis
   0.0066 (  0.0%)   0.0006 (  0.0%)   0.0073 (  0.0%)   0.0072 (  0.0%)  Scalar Evolution Analysis
   0.0016 (  0.0%)   0.0024 (  0.0%)   0.0040 (  0.0%)   0.0072 (  0.0%)  LCSSA Verifier
   0.0011 (  0.0%)   0.0008 (  0.0%)   0.0019 (  0.0%)   0.0072 (  0.0%)  Lazy Branch Probability Analysis
   0.0069 (  0.0%)   0.0002 (  0.0%)   0.0071 (  0.0%)   0.0071 (  0.0%)  Expand Atomic instructions
   0.0069 (  0.0%)   0.0002 (  0.0%)   0.0071 (  0.0%)   0.0071 (  0.0%)  Early If-Conversion
   0.0066 (  0.0%)   0.0002 (  0.0%)   0.0069 (  0.0%)   0.0069 (  0.0%)  AArch64 pseudo instruction expansion pass
   0.0065 (  0.0%)   0.0003 (  0.0%)   0.0068 (  0.0%)   0.0068 (  0.0%)  Branch relaxation pass
   0.0035 (  0.0%)   0.0005 (  0.0%)   0.0040 (  0.0%)   0.0065 (  0.0%)  Function Alias Analysis Results
   0.0055 (  0.0%)   0.0010 (  0.0%)   0.0065 (  0.0%)   0.0065 (  0.0%)  Scalar Evolution Analysis
   0.0059 (  0.0%)   0.0003 (  0.0%)   0.0062 (  0.0%)   0.0062 (  0.0%)  Stack Slot Coloring
   0.0050 (  0.0%)   0.0007 (  0.0%)   0.0058 (  0.0%)   0.0060 (  0.0%)  Canonicalize natural loops
   0.0035 (  0.0%)   0.0005 (  0.0%)   0.0040 (  0.0%)   0.0060 (  0.0%)  Call-site splitting
   0.0054 (  0.0%)   0.0006 (  0.0%)   0.0060 (  0.0%)   0.0060 (  0.0%)  MergedLoadStoreMotion
   0.0057 (  0.0%)   0.0002 (  0.0%)   0.0059 (  0.0%)   0.0059 (  0.0%)  AArch64 Condition Optimizer
   0.0037 (  0.0%)   0.0008 (  0.0%)   0.0045 (  0.0%)   0.0059 (  0.0%)  Function Alias Analysis Results
   0.0055 (  0.0%)   0.0002 (  0.0%)   0.0057 (  0.0%)   0.0057 (  0.0%)  Expand memcmp() to load/stores
   0.0035 (  0.0%)   0.0010 (  0.0%)   0.0046 (  0.0%)   0.0056 (  0.0%)  Function Alias Analysis Results
   0.0013 (  0.0%)   0.0005 (  0.0%)   0.0018 (  0.0%)   0.0054 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0047 (  0.0%)   0.0006 (  0.0%)   0.0053 (  0.0%)   0.0053 (  0.0%)  Remove unused exception handling info
   0.0049 (  0.0%)   0.0002 (  0.0%)   0.0051 (  0.0%)   0.0051 (  0.0%)  Tail Duplication
   0.0007 (  0.0%)   0.0006 (  0.0%)   0.0012 (  0.0%)   0.0051 (  0.0%)  Optimization Remark Emitter
   0.0043 (  0.0%)   0.0007 (  0.0%)   0.0050 (  0.0%)   0.0050 (  0.0%)  Canonicalize natural loops
   0.0022 (  0.0%)   0.0027 (  0.0%)   0.0049 (  0.0%)   0.0049 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0045 (  0.0%)   0.0002 (  0.0%)   0.0047 (  0.0%)   0.0048 (  0.0%)  Remove unreachable machine basic blocks
   0.0047 (  0.0%)   0.0000 (  0.0%)   0.0047 (  0.0%)   0.0047 (  0.0%)  CallGraph Construction
   0.0019 (  0.0%)   0.0029 (  0.0%)   0.0048 (  0.0%)   0.0047 (  0.0%)  LCSSA Verifier
   0.0007 (  0.0%)   0.0008 (  0.0%)   0.0014 (  0.0%)   0.0047 (  0.0%)  Lazy Block Frequency Analysis
   0.0044 (  0.0%)   0.0002 (  0.0%)   0.0047 (  0.0%)   0.0046 (  0.0%)  Shrink Wrapping analysis
   0.0040 (  0.0%)   0.0005 (  0.0%)   0.0045 (  0.0%)   0.0046 (  0.0%)  PGOMemOPSize
   0.0043 (  0.0%)   0.0002 (  0.0%)   0.0045 (  0.0%)   0.0045 (  0.0%)  Post-RA pseudo instruction expansion pass
   0.0036 (  0.0%)   0.0009 (  0.0%)   0.0044 (  0.0%)   0.0044 (  0.0%)  Function Alias Analysis Results
   0.0004 (  0.0%)   0.0005 (  0.0%)   0.0009 (  0.0%)   0.0043 (  0.0%)  Lazy Block Frequency Analysis
   0.0038 (  0.0%)   0.0003 (  0.0%)   0.0041 (  0.0%)   0.0042 (  0.0%)  AArch64 Redundant Copy Elimination
   0.0036 (  0.0%)   0.0005 (  0.0%)   0.0041 (  0.0%)   0.0042 (  0.0%)  Function Alias Analysis Results
   0.0033 (  0.0%)   0.0008 (  0.0%)   0.0042 (  0.0%)   0.0041 (  0.0%)  Function Alias Analysis Results
   0.0036 (  0.0%)   0.0005 (  0.0%)   0.0041 (  0.0%)   0.0041 (  0.0%)  Function Alias Analysis Results
   0.0038 (  0.0%)   0.0002 (  0.0%)   0.0041 (  0.0%)   0.0041 (  0.0%)  Scalar Evolution Analysis
   0.0035 (  0.0%)   0.0005 (  0.0%)   0.0040 (  0.0%)   0.0040 (  0.0%)  Function Alias Analysis Results
   0.0038 (  0.0%)   0.0003 (  0.0%)   0.0041 (  0.0%)   0.0040 (  0.0%)  Hoist/decompose integer division and remainder
   0.0038 (  0.0%)   0.0002 (  0.0%)   0.0040 (  0.0%)   0.0040 (  0.0%)  Tail Duplication
   0.0037 (  0.0%)   0.0003 (  0.0%)   0.0040 (  0.0%)   0.0040 (  0.0%)  Scalar Evolution Analysis
   0.0037 (  0.0%)   0.0002 (  0.0%)   0.0039 (  0.0%)   0.0039 (  0.0%)  Partially inline calls to library functions
   0.0034 (  0.0%)   0.0005 (  0.0%)   0.0039 (  0.0%)   0.0039 (  0.0%)  Function Alias Analysis Results
   0.0033 (  0.0%)   0.0002 (  0.0%)   0.0036 (  0.0%)   0.0035 (  0.0%)  AArch64 Store Pair Suppression
   0.0028 (  0.0%)   0.0007 (  0.0%)   0.0035 (  0.0%)   0.0035 (  0.0%)  Scalar Evolution Analysis
   0.0026 (  0.0%)   0.0008 (  0.0%)   0.0034 (  0.0%)   0.0034 (  0.0%)  Function Alias Analysis Results
   0.0032 (  0.0%)   0.0002 (  0.0%)   0.0034 (  0.0%)   0.0034 (  0.0%)  Remove unreachable blocks from the CFG
   0.0030 (  0.0%)   0.0002 (  0.0%)   0.0032 (  0.0%)   0.0032 (  0.0%)  Scalar Evolution Analysis
   0.0025 (  0.0%)   0.0007 (  0.0%)   0.0032 (  0.0%)   0.0032 (  0.0%)  Loop Sink
   0.0025 (  0.0%)   0.0006 (  0.0%)   0.0030 (  0.0%)   0.0030 (  0.0%)  Scalar Evolution Analysis
   0.0028 (  0.0%)   0.0002 (  0.0%)   0.0030 (  0.0%)   0.0030 (  0.0%)  Interleaved Access Pass
   0.0027 (  0.0%)   0.0002 (  0.0%)   0.0030 (  0.0%)   0.0030 (  0.0%)  AArch64 Conditional Branch Tuning
   0.0023 (  0.0%)   0.0006 (  0.0%)   0.0029 (  0.0%)   0.0029 (  0.0%)  Speculatively execute instructions if target has divergent branches
   0.0026 (  0.0%)   0.0002 (  0.0%)   0.0028 (  0.0%)   0.0028 (  0.0%)  Process Implicit Definitions
   0.0017 (  0.0%)   0.0011 (  0.0%)   0.0028 (  0.0%)   0.0028 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0017 (  0.0%)   0.0010 (  0.0%)   0.0028 (  0.0%)   0.0028 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0022 (  0.0%)   0.0005 (  0.0%)   0.0026 (  0.0%)   0.0027 (  0.0%)  Machine Trace Metrics
   0.0027 (  0.0%)   0.0000 (  0.0%)   0.0027 (  0.0%)   0.0027 (  0.0%)  Dead Global Elimination
   0.0024 (  0.0%)   0.0002 (  0.0%)   0.0026 (  0.0%)   0.0027 (  0.0%)  Local Stack Slot Allocation
   0.0024 (  0.0%)   0.0002 (  0.0%)   0.0026 (  0.0%)   0.0026 (  0.0%)  Optimize machine instruction PHIs
   0.0022 (  0.0%)   0.0003 (  0.0%)   0.0025 (  0.0%)   0.0026 (  0.0%)  Debug Variable Analysis
   0.0018 (  0.0%)   0.0008 (  0.0%)   0.0026 (  0.0%)   0.0026 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0023 (  0.0%)   0.0002 (  0.0%)   0.0026 (  0.0%)   0.0026 (  0.0%)  Expand ISel Pseudo-instructions
   0.0020 (  0.0%)   0.0006 (  0.0%)   0.0025 (  0.0%)   0.0026 (  0.0%)  Function Alias Analysis Results
   0.0026 (  0.0%)   0.0000 (  0.0%)   0.0026 (  0.0%)   0.0026 (  0.0%)  Dead Global Elimination
   0.0015 (  0.0%)   0.0010 (  0.0%)   0.0026 (  0.0%)   0.0025 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0023 (  0.0%)   0.0002 (  0.0%)   0.0025 (  0.0%)   0.0025 (  0.0%)  Loop Access Analysis
   0.0004 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0025 (  0.0%)  Loop Access Analysis
   0.0014 (  0.0%)   0.0011 (  0.0%)   0.0025 (  0.0%)   0.0024 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0022 (  0.0%)   0.0002 (  0.0%)   0.0024 (  0.0%)   0.0024 (  0.0%)  Scalarize Masked Memory Intrinsics
   0.0016 (  0.0%)   0.0006 (  0.0%)   0.0021 (  0.0%)   0.0023 (  0.0%)  Function Alias Analysis Results
   0.0015 (  0.0%)   0.0008 (  0.0%)   0.0023 (  0.0%)   0.0023 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0020 (  0.0%)   0.0002 (  0.0%)   0.0022 (  0.0%)   0.0022 (  0.0%)  Expand reduction intrinsics
   0.0009 (  0.0%)   0.0013 (  0.0%)   0.0022 (  0.0%)   0.0021 (  0.0%)  LCSSA Verifier
   0.0015 (  0.0%)   0.0006 (  0.0%)   0.0021 (  0.0%)   0.0021 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0013 (  0.0%)   0.0008 (  0.0%)   0.0021 (  0.0%)   0.0021 (  0.0%)  Memory Dependence Analysis
   0.0015 (  0.0%)   0.0006 (  0.0%)   0.0021 (  0.0%)   0.0020 (  0.0%)  Demanded bits analysis
   0.0017 (  0.0%)   0.0003 (  0.0%)   0.0020 (  0.0%)   0.0020 (  0.0%)  Function Alias Analysis Results
   0.0016 (  0.0%)   0.0003 (  0.0%)   0.0020 (  0.0%)   0.0020 (  0.0%)  Bundle Machine CFG Edges
   0.0017 (  0.0%)   0.0002 (  0.0%)   0.0019 (  0.0%)   0.0020 (  0.0%)  Function Alias Analysis Results
   0.0014 (  0.0%)   0.0005 (  0.0%)   0.0020 (  0.0%)   0.0019 (  0.0%)  Lower 'expect' Intrinsics
   0.0011 (  0.0%)   0.0009 (  0.0%)   0.0019 (  0.0%)   0.0019 (  0.0%)  Lazy Branch Probability Analysis
   0.0010 (  0.0%)   0.0008 (  0.0%)   0.0018 (  0.0%)   0.0018 (  0.0%)  Lazy Branch Probability Analysis
   0.0015 (  0.0%)   0.0003 (  0.0%)   0.0018 (  0.0%)   0.0018 (  0.0%)  Function Alias Analysis Results
   0.0010 (  0.0%)   0.0009 (  0.0%)   0.0018 (  0.0%)   0.0018 (  0.0%)  Lazy Branch Probability Analysis
   0.0008 (  0.0%)   0.0010 (  0.0%)   0.0018 (  0.0%)   0.0018 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0012 (  0.0%)   0.0005 (  0.0%)   0.0017 (  0.0%)   0.0017 (  0.0%)  Promote Memory to Register
   0.0008 (  0.0%)   0.0005 (  0.0%)   0.0013 (  0.0%)   0.0017 (  0.0%)  Lazy Branch Probability Analysis
   0.0008 (  0.0%)   0.0008 (  0.0%)   0.0016 (  0.0%)   0.0017 (  0.0%)  Lazy Branch Probability Analysis
   0.0009 (  0.0%)   0.0008 (  0.0%)   0.0017 (  0.0%)   0.0016 (  0.0%)  Memory Dependence Analysis
   0.0013 (  0.0%)   0.0002 (  0.0%)   0.0015 (  0.0%)   0.0016 (  0.0%)  Exception handling preparation
   0.0011 (  0.0%)   0.0004 (  0.0%)   0.0015 (  0.0%)   0.0015 (  0.0%)  Spill Code Placement Analysis
   0.0009 (  0.0%)   0.0006 (  0.0%)   0.0015 (  0.0%)   0.0015 (  0.0%)  Machine Trace Metrics
   0.0007 (  0.0%)   0.0008 (  0.0%)   0.0015 (  0.0%)   0.0015 (  0.0%)  Lazy Block Frequency Analysis
   0.0006 (  0.0%)   0.0008 (  0.0%)   0.0014 (  0.0%)   0.0014 (  0.0%)  Lazy Block Frequency Analysis
   0.0012 (  0.0%)   0.0002 (  0.0%)   0.0014 (  0.0%)   0.0014 (  0.0%)  Loop Distribution
   0.0010 (  0.0%)   0.0003 (  0.0%)   0.0014 (  0.0%)   0.0014 (  0.0%)  Live Register Matrix
   0.0008 (  0.0%)   0.0006 (  0.0%)   0.0014 (  0.0%)   0.0013 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0006 (  0.0%)   0.0008 (  0.0%)   0.0014 (  0.0%)   0.0013 (  0.0%)  Lazy Block Frequency Analysis
   0.0006 (  0.0%)   0.0008 (  0.0%)   0.0013 (  0.0%)   0.0013 (  0.0%)  Lazy Block Frequency Analysis
   0.0006 (  0.0%)   0.0006 (  0.0%)   0.0012 (  0.0%)   0.0013 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0010 (  0.0%)   0.0002 (  0.0%)   0.0013 (  0.0%)   0.0012 (  0.0%)  AArch64 SIMD instructions optimization pass
   0.0005 (  0.0%)   0.0007 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  LCSSA Verifier
   0.0007 (  0.0%)   0.0006 (  0.0%)   0.0013 (  0.0%)   0.0012 (  0.0%)  Optimization Remark Emitter
   0.0005 (  0.0%)   0.0007 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  LCSSA Verifier
   0.0007 (  0.0%)   0.0005 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  Lazy Branch Probability Analysis
   0.0005 (  0.0%)   0.0007 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  LCSSA Verifier
   0.0005 (  0.0%)   0.0007 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  LCSSA Verifier
   0.0007 (  0.0%)   0.0005 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  Optimization Remark Emitter
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0012 (  0.0%)  Optimization Remark Emitter
   0.0006 (  0.0%)   0.0006 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  Optimization Remark Emitter
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0012 (  0.0%)  Lazy Branch Probability Analysis
   0.0008 (  0.0%)   0.0004 (  0.0%)   0.0012 (  0.0%)   0.0012 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0007 (  0.0%)   0.0005 (  0.0%)   0.0012 (  0.0%)   0.0011 (  0.0%)  Live Stack Slot Analysis
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0011 (  0.0%)  Lazy Branch Probability Analysis
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0011 (  0.0%)  Optimization Remark Emitter
   0.0006 (  0.0%)   0.0006 (  0.0%)   0.0011 (  0.0%)   0.0011 (  0.0%)  Lazy Block Frequency Analysis
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0011 (  0.0%)  Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0011 (  0.0%)  Optimization Remark Emitter
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0011 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0006 (  0.0%)   0.0005 (  0.0%)   0.0011 (  0.0%)   0.0011 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0005 (  0.0%)   0.0005 (  0.0%)   0.0010 (  0.0%)   0.0010 (  0.0%)  Optimization Remark Emitter
   0.0007 (  0.0%)   0.0003 (  0.0%)   0.0010 (  0.0%)   0.0010 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0008 (  0.0%)   0.0002 (  0.0%)   0.0010 (  0.0%)   0.0010 (  0.0%)  Function Alias Analysis Results
   0.0004 (  0.0%)   0.0005 (  0.0%)   0.0009 (  0.0%)   0.0010 (  0.0%)  Lazy Block Frequency Analysis
   0.0005 (  0.0%)   0.0003 (  0.0%)   0.0009 (  0.0%)   0.0009 (  0.0%)  Lazy Branch Probability Analysis
   0.0005 (  0.0%)   0.0004 (  0.0%)   0.0009 (  0.0%)   0.0009 (  0.0%)  Lazy Branch Probability Analysis
   0.0004 (  0.0%)   0.0005 (  0.0%)   0.0008 (  0.0%)   0.0008 (  0.0%)  Lazy Block Frequency Analysis
   0.0005 (  0.0%)   0.0003 (  0.0%)   0.0008 (  0.0%)   0.0008 (  0.0%)  Lazy Branch Probability Analysis
   0.0006 (  0.0%)   0.0002 (  0.0%)   0.0008 (  0.0%)   0.0008 (  0.0%)  Falkor HW Prefetch Fix
   0.0005 (  0.0%)   0.0003 (  0.0%)   0.0008 (  0.0%)   0.0008 (  0.0%)  Virtual Register Map
   0.0005 (  0.0%)   0.0002 (  0.0%)   0.0007 (  0.0%)   0.0007 (  0.0%)  Alignment from assumptions
   0.0004 (  0.0%)   0.0002 (  0.0%)   0.0007 (  0.0%)   0.0007 (  0.0%)  Lazy Branch Probability Analysis
   0.0003 (  0.0%)   0.0004 (  0.0%)   0.0007 (  0.0%)   0.0007 (  0.0%)  Lazy Block Frequency Analysis
   0.0003 (  0.0%)   0.0003 (  0.0%)   0.0007 (  0.0%)   0.0007 (  0.0%)  Lazy Machine Block Frequency Analysis
   0.0003 (  0.0%)   0.0004 (  0.0%)   0.0007 (  0.0%)   0.0007 (  0.0%)  Lazy Block Frequency Analysis
   0.0003 (  0.0%)   0.0004 (  0.0%)   0.0007 (  0.0%)   0.0007 (  0.0%)  Lazy Machine Block Frequency Analysis
   0.0004 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Basic Alias Analysis (stateless AA impl)
   0.0006 (  0.0%)   0.0000 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Deduce function attributes in RPO
   0.0003 (  0.0%)   0.0004 (  0.0%)   0.0007 (  0.0%)   0.0006 (  0.0%)  Lazy Block Frequency Analysis
   0.0003 (  0.0%)   0.0003 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Lazy Branch Probability Analysis
   0.0004 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Machine Optimization Remark Emitter
   0.0004 (  0.0%)   0.0003 (  0.0%)   0.0007 (  0.0%)   0.0006 (  0.0%)  Loop Access Analysis
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Optimization Remark Emitter
   0.0004 (  0.0%)   0.0003 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Machine Optimization Remark Emitter
   0.0004 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Implement the 'patchable-function' attribute
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Optimization Remark Emitter
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Optimization Remark Emitter
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Insert XRay ops
   0.0003 (  0.0%)   0.0003 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Lazy Branch Probability Analysis
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0006 (  0.0%)  Demanded bits analysis
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Optimization Remark Emitter
   0.0003 (  0.0%)   0.0003 (  0.0%)   0.0006 (  0.0%)   0.0006 (  0.0%)  Optimization Remark Emitter
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0006 (  0.0%)  Insert fentry calls
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0005 (  0.0%)  Machine Optimization Remark Emitter
   0.0005 (  0.0%)   0.0000 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Merge Duplicate Global Constants
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  StackMap Liveness Analysis
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0006 (  0.0%)   0.0005 (  0.0%)  PostRA Machine Instruction Scheduler
   0.0003 (  0.0%)   0.0003 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Live DEBUG_VALUE analysis
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Optimization Remark Emitter
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Falkor HW Prefetch Fix Late Phase
   0.0003 (  0.0%)   0.0003 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Optimization Remark Emitter
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  A57 FP Anti-dependency breaker
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Detect Dead Lanes
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Demanded bits analysis
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Optimization Remark Emitter
   0.0002 (  0.0%)   0.0003 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Lazy Block Frequency Analysis
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Lazy Machine Block Frequency Analysis
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Instrument function entry/exit with calls to e.g. mcount() (post inlining)
   0.0003 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Rename Disconnected Subregister Components
   0.0002 (  0.0%)   0.0003 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Contiguously Lay Out Funclets
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Safe Stack instrumentation pass
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0005 (  0.0%)  Analyze Machine Code For Garbage Collection
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0005 (  0.0%)   0.0004 (  0.0%)  Lazy Block Frequency Analysis
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0004 (  0.0%)   0.0004 (  0.0%)  Merge internal globals
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0004 (  0.0%)   0.0004 (  0.0%)  Lazy Block Frequency Analysis
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0004 (  0.0%)   0.0004 (  0.0%)  Shadow Stack GC Lowering
   0.0002 (  0.0%)   0.0002 (  0.0%)   0.0004 (  0.0%)   0.0004 (  0.0%)  Lower Garbage Collection Instructions
   0.0002 (  0.0%)   0.0003 (  0.0%)   0.0004 (  0.0%)   0.0004 (  0.0%)  Target Library Information
   0.0002 (  0.0%)   0.0003 (  0.0%)   0.0004 (  0.0%)   0.0004 (  0.0%)  ObjC ARC contraction
   0.0002 (  0.0%)   0.0000 (  0.0%)   0.0002 (  0.0%)   0.0002 (  0.0%)  Dominator Tree Construction
   0.0001 (  0.0%)   0.0001 (  0.0%)   0.0002 (  0.0%)   0.0002 (  0.0%)  Create Garbage Collector Module Metadata
   0.0002 (  0.0%)   0.0000 (  0.0%)   0.0002 (  0.0%)   0.0002 (  0.0%)  Infer set function attributes
   0.0001 (  0.0%)   0.0000 (  0.0%)   0.0001 (  0.0%)   0.0001 (  0.0%)  Assumption Cache Tracker
   0.0001 (  0.0%)   0.0000 (  0.0%)   0.0001 (  0.0%)   0.0001 (  0.0%)  Assumption Cache Tracker
   0.0001 (  0.0%)   0.0000 (  0.0%)   0.0001 (  0.0%)   0.0001 (  0.0%)  Strip Unused Function Prototypes
   0.0001 (  0.0%)   0.0000 (  0.0%)   0.0001 (  0.0%)   0.0001 (  0.0%)  Eliminate Available Externally Globals
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Pre-ISel Intrinsic Lowering
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Force set function attributes
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Rewrite Symbols
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Target Transform Information
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Target Pass Configuration
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Target Transform Information
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Profile summary info
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Scoped NoAlias Alias Analysis
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Profile summary info
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  A No-Op Barrier Pass
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Type-Based Alias Analysis
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Scoped NoAlias Alias Analysis
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Target Library Information
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Machine Branch Probability Analysis
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Type-Based Alias Analysis
  6369.3137 (100.0%)  14.3417 (100.0%)  6383.6554 (100.0%)  7826.9875 (100.0%)  Total

===-------------------------------------------------------------------------===
                          Clang front-end time report
===-------------------------------------------------------------------------===
  Total Execution Time: 6385.4041 seconds (7829.0221 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  6370.6518 (100.0%)  14.7523 (100.0%)  6385.4041 (100.0%)  7829.0221 (100.0%)  Clang front-end timer
  6370.6518 (100.0%)  14.7523 (100.0%)  6385.4041 (100.0%)  7829.0221 (100.0%)  Total


real	130m29.070s
user	106m10.663s

brzycki mentioned this in D38558: [JumpThreading] Preserve DT and LVI across the pass..Jan 19 2018, 8:24 AM

@MatzeB wrote:
Some files like sqlite3.c felt like they would never finish...

sqlite3.c has some rediculously large functions where they emit 3000+ basic blocks per function. It doesn't surprise me you see the worst timing on them and it's even worse if I perform the DT updates incrementally instead of a large batch. On my test machine, an Intel(R) Xeon(R) CPU E5-4660 v4 @ 2.20GHz it takes test-suite's sqlite3.c around 7-8 minutes to compile when using a Debug compiler. Release is much faster, somewhere around 15-25 seconds.

a.elovikov added a subscriber: a.elovikov.Jan 26 2018, 6:01 AM

Herald added a subscriber: hintonda. · View Herald TranscriptJan 26 2018, 6:01 AM

fhahn added a subscriber: fhahn.Mar 19 2018, 8:42 AM

fhahn added inline comments.

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp
2610	I think DuplicateInstructionsInSplitBetween can easily update the DT itself: D44629. Is it better to do the update incrementally here or make DuplicateInstructionsInSplitBetween take care of it (via splitBlock)? Letting functions update the DT themselves seems to be what similar functions do. We do not have access to the plain DT here though, which makes that slightly trickier and that's why I want to check what's better before doing any changes here :)

brzycki added inline comments.Mar 19 2018, 9:08 AM

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp
2610	Hi @fhahn , when I initially did the work to preserve `DT` across JumpThreading I tried to do two things: Minimize the changes to external calls. Update the `DT` real-time. Compile time testing showed that updating the `DT` real-time was just too slow. This not-so-great compromise is the deferred class we have today. Any time we have to call `DDT-flush()` incurs a compile-time penalty which is why you can find external calls that take `DT` as a parameter but I didn't use it because it'd require me to flush first. I'd also like to avoid having multiple functions that take both a `DT` and a `DDT` parameter. It complexifies function signatures, positional `nullPtr` placement, and more branchy checks inside these routines. I know that @kuhar is leading a GSoC topic to unify the DT/PDT/DDT interface and it may be worth following that before spending any of your time trying to hack on this mess... You are more than welcome to see if you can make changes here, just make sure test-suite ctmark isn't adversely impacted when you do. :)

+1. Real time updating in the presence of how JT operates right now is too
costly.
The lazy analysis it uses require DT be updated at all times, forever
(instead of say, once an iteration).
There is no way to update the domtree 100000 times a pass and make it fast
:)
What we should be targeting is O(10)-O(100) updates.

In D40146#1042130, @dberlin wrote:

+1. Real time updating in the presence of how JT operates right now is too
costly.
The lazy analysis it uses require DT be updated at all times, forever
(instead of say, once an iteration).
There is no way to update the domtree 100000 times a pass and make it fast
:)
What we should be targeting is O(10)-O(100) updates.

Thanks for the feedback. As DuplicateInstructionsInSplitBetween does not take a dominator tree as arugment, it might be better to pass in a DeferredDominance object to update the DT to start with and do the update incrementally. I am just trying to figure out the best way going forward, as I need to update the DT after DuplicateInstructionsInSplitBetween in D43173 too :)

This is a bit late on this, but we're currently trying to upgrade LLVM in Rust and we've run into a performance regression bisected to this change, if those here familiar with this commit could help investigate that it'd be much appreciated!

Revision Contents

Path

Size

llvm/

trunk/

include/

llvm/

IR/

Dominators.h

84 lines

Transforms/

Scalar/

JumpThreading.h

6 lines

Utils/

BasicBlockUtils.h

3 lines

Local.h

20 lines

lib/

IR/

Dominators.cpp

188 lines

Transforms/

Scalar/

CorrelatedValuePropagation.cpp

2 lines

JumpThreading.cpp

174 lines

Utils/

BasicBlockUtils.cpp

18 lines

Local.cpp

209 lines

test/

Analysis/

LazyValueAnalysis/

lvi-after-jumpthreading.ll

3 lines

Transforms/

JumpThreading/

ddt-crash.ll

265 lines

ddt-crash2.ll

40 lines

lvi-tristate.ll

50 lines

unittests/

IR/

CMakeLists.txt

1 line

DeferredDominanceTest.cpp

344 lines

Diff 129694

llvm/trunk/include/llvm/IR/Dominators.h

Show First 20 Lines • Show All 284 Lines • ▼ Show 20 Lines	void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesAll();		AU.setPreservesAll();
}		}

void releaseMemory() override { DT.releaseMemory(); }		void releaseMemory() override { DT.releaseMemory(); }

void print(raw_ostream &OS, const Module *M = nullptr) const override;		void print(raw_ostream &OS, const Module *M = nullptr) const override;
};		};

		//===-------------------------------------
		/// \brief Class to defer updates to a DominatorTree.
		///
		/// Definition: Applying updates to every edge insertion and deletion is
		/// expensive and not necessary. When one needs the DominatorTree for analysis
		/// they can request a flush() to perform a larger batch update. This has the
		/// advantage of the DominatorTree inspecting the set of updates to find
		/// duplicates or unnecessary subtree updates.
		///
		/// The scope of DeferredDominance operates at a Function level.
		///
		/// It is not necessary for the user to scrub the updates for duplicates or
		/// updates that point to the same block (Delete, BB_A, BB_A). Performance
		/// can be gained if the caller attempts to batch updates before submitting
		/// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
		/// occur.
		///
		/// It is required for the state of the LLVM IR to be applied before
		/// submitting updates. The update routines must analyze the current state
		/// between a pair of (From, To) basic blocks to determine if the update
		/// needs to be queued.
		/// Example (good):
		/// TerminatorInstructionBB->removeFromParent();
		/// DDT->deleteEdge(BB, Successor);
		/// Example (bad):
		/// DDT->deleteEdge(BB, Successor);
		/// TerminatorInstructionBB->removeFromParent();
		class DeferredDominance {
		public:
		DeferredDominance(DominatorTree &DT_) : DT(DT_) {}

		/// \brief Queues multiple updates and discards duplicates.
		void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);

		/// \brief Helper method for a single edge insertion. It's almost always
		/// better to batch updates and call applyUpdates to quickly remove duplicate
		/// edges. This is best used when there is only a single insertion needed to
		/// update Dominators.
		void insertEdge(BasicBlock From, BasicBlock To);

		/// \brief Helper method for a single edge deletion. It's almost always better
		/// to batch updates and call applyUpdates to quickly remove duplicate edges.
		/// This is best used when there is only a single deletion needed to update
		/// Dominators.
		void deleteEdge(BasicBlock From, BasicBlock To);

		/// \brief Delays the deletion of a basic block until a flush() event.
		void deleteBB(BasicBlock *DelBB);

		/// \brief Returns true if DelBB is awaiting deletion at a flush() event.
		bool pendingDeletedBB(BasicBlock *DelBB);

		/// \brief Flushes all pending updates and block deletions. Returns a
		/// correct DominatorTree reference to be used by the caller for analysis.
		DominatorTree &flush();

		/// \brief Drops all internal state and forces a (slow) recalculation of the
		/// DominatorTree based on the current state of the LLVM IR in F. This should
		/// only be used in corner cases such as the Entry block of F being deleted.
		void recalculate(Function &F);

		/// \brief Debug method to help view the state of pending updates.
		LLVM_DUMP_METHOD void dump() const;

		private:
		DominatorTree &DT;
		SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
		SmallPtrSet<BasicBlock *, 8> DeletedBBs;

		/// Apply an update (Kind, From, To) to the internal queued updates. The
		/// update is only added when determined to be necessary. Checks for
		/// self-domination, unnecessary updates, duplicate requests, and balanced
		/// pairs of requests are all performed. Returns true if the update is
		/// queued and false if it is discarded.
		bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
		BasicBlock *To);

		/// Performs all pending basic block deletions. We have to defer the deletion
		/// of these blocks until after the DominatorTree updates are applied. The
		/// internal workings of the DominatorTree code expect every update's From
		/// and To blocks to exist and to be a member of the same Function.
		bool flushDelBB();
		};

} // end namespace llvm		} // end namespace llvm

#endif // LLVM_IR_DOMINATORS_H		#endif // LLVM_IR_DOMINATORS_H

llvm/trunk/include/llvm/Transforms/Scalar/JumpThreading.h

Show All 28 Lines

namespace llvm {		namespace llvm {

class BasicBlock;		class BasicBlock;
class BinaryOperator;		class BinaryOperator;
class BranchInst;		class BranchInst;
class CmpInst;		class CmpInst;
class Constant;		class Constant;
		class DeferredDominance;
class Function;		class Function;
class Instruction;		class Instruction;
class IntrinsicInst;		class IntrinsicInst;
class LazyValueInfo;		class LazyValueInfo;
class LoadInst;		class LoadInst;
class PHINode;		class PHINode;
class TargetLibraryInfo;		class TargetLibraryInfo;
class Value;		class Value;
Show All 27 Lines
/// if (X < 3) {		/// if (X < 3) {
///		///
/// In this case, the unconditional branch at the end of the first if can be		/// In this case, the unconditional branch at the end of the first if can be
/// revectored to the false side of the second if.		/// revectored to the false side of the second if.
class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {		class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
TargetLibraryInfo *TLI;		TargetLibraryInfo *TLI;
LazyValueInfo *LVI;		LazyValueInfo *LVI;
AliasAnalysis *AA;		AliasAnalysis *AA;
		DeferredDominance *DDT;
std::unique_ptr<BlockFrequencyInfo> BFI;		std::unique_ptr<BlockFrequencyInfo> BFI;
std::unique_ptr<BranchProbabilityInfo> BPI;		std::unique_ptr<BranchProbabilityInfo> BPI;
bool HasProfileData = false;		bool HasProfileData = false;
bool HasGuards = false;		bool HasGuards = false;
#ifdef NDEBUG		#ifdef NDEBUG
SmallPtrSet<const BasicBlock *, 16> LoopHeaders;		SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
#else		#else
SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;		SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
Show All 14 Lines	struct RecursionSetRemover {
~RecursionSetRemover() { TheSet.erase(ThePair); }		~RecursionSetRemover() { TheSet.erase(ThePair); }
};		};

public:		public:
JumpThreadingPass(int T = -1);		JumpThreadingPass(int T = -1);

// Glue for old PM.		// Glue for old PM.
bool runImpl(Function &F, TargetLibraryInfo TLI_, LazyValueInfo LVI_,		bool runImpl(Function &F, TargetLibraryInfo TLI_, LazyValueInfo LVI_,
AliasAnalysis *AA_, bool HasProfileData_,		AliasAnalysis AA_, DeferredDominance DDT_,
std::unique_ptr<BlockFrequencyInfo> BFI_,		bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_,
std::unique_ptr<BranchProbabilityInfo> BPI_);		std::unique_ptr<BranchProbabilityInfo> BPI_);

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);		PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

void releaseMemory() {		void releaseMemory() {
BFI.reset();		BFI.reset();
BPI.reset();		BPI.reset();
}		}
Show All 40 Lines

llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h

	Show All 21 Lines
	#include "llvm/IR/CFG.h"			#include "llvm/IR/CFG.h"
	#include "llvm/IR/InstrTypes.h"			#include "llvm/IR/InstrTypes.h"
	#include <cassert>			#include <cassert>

	namespace llvm {			namespace llvm {

	class BlockFrequencyInfo;			class BlockFrequencyInfo;
	class BranchProbabilityInfo;			class BranchProbabilityInfo;
				class DeferredDominance;
	class DominatorTree;			class DominatorTree;
	class Function;			class Function;
	class Instruction;			class Instruction;
	class LoopInfo;			class LoopInfo;
	class MDNode;			class MDNode;
	class MemoryDependenceResults;			class MemoryDependenceResults;
	class ReturnInst;			class ReturnInst;
	class TargetLibraryInfo;			class TargetLibraryInfo;
	class Value;			class Value;

	/// Delete the specified block, which must have no predecessors.			/// Delete the specified block, which must have no predecessors.
	void DeleteDeadBlock(BasicBlock *BB);			void DeleteDeadBlock(BasicBlock BB, DeferredDominance DDT = nullptr);

	/// We know that BB has one predecessor. If there are any single-entry PHI nodes			/// We know that BB has one predecessor. If there are any single-entry PHI nodes
	/// in it, fold them away. This handles the case when all entries to the PHI			/// in it, fold them away. This handles the case when all entries to the PHI
	/// nodes in a block are guaranteed equal, such as when the block has exactly			/// nodes in a block are guaranteed equal, such as when the block has exactly
	/// one predecessor.			/// one predecessor.
	void FoldSingleEntryPHINodes(BasicBlock *BB,			void FoldSingleEntryPHINodes(BasicBlock *BB,
	MemoryDependenceResults *MemDep = nullptr);			MemoryDependenceResults *MemDep = nullptr);

	▲ Show 20 Lines • Show All 264 Lines • Show Last 20 Lines

llvm/trunk/include/llvm/Transforms/Utils/Local.h

	Show First 20 Lines • Show All 111 Lines • ▼ Show 20 Lines
	/// If a terminator instruction is predicated on a constant value, convert it			/// If a terminator instruction is predicated on a constant value, convert it
	/// into an unconditional branch to the constant destination.			/// into an unconditional branch to the constant destination.
	/// This is a nontrivial operation because the successors of this basic block			/// This is a nontrivial operation because the successors of this basic block
	/// must have their PHI nodes updated.			/// must have their PHI nodes updated.
	/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch			/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
	/// conditions and indirectbr addresses this might make dead if			/// conditions and indirectbr addresses this might make dead if
	/// DeleteDeadConditions is true.			/// DeleteDeadConditions is true.
	bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,			bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
	const TargetLibraryInfo *TLI = nullptr);			const TargetLibraryInfo *TLI = nullptr,
				DeferredDominance *DDT = nullptr);

	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//
	// Local dead code elimination.			// Local dead code elimination.
	//			//

	/// Return true if the result produced by the instruction is not used, and the			/// Return true if the result produced by the instruction is not used, and the
	/// instruction has no side effects.			/// instruction has no side effects.
	bool isInstructionTriviallyDead(Instruction *I,			bool isInstructionTriviallyDead(Instruction *I,
	Show All 37 Lines
	///			///
	/// Unlike the removePredecessor method, this attempts to simplify uses of PHI			/// Unlike the removePredecessor method, this attempts to simplify uses of PHI
	/// nodes that collapse into identity values. For example, if we have:			/// nodes that collapse into identity values. For example, if we have:
	/// x = phi(1, 0, 0, 0)			/// x = phi(1, 0, 0, 0)
	/// y = and x, z			/// y = and x, z
	///			///
	/// .. and delete the predecessor corresponding to the '1', this will attempt to			/// .. and delete the predecessor corresponding to the '1', this will attempt to
	/// recursively fold the 'and' to 0.			/// recursively fold the 'and' to 0.
	void RemovePredecessorAndSimplify(BasicBlock BB, BasicBlock Pred);			void RemovePredecessorAndSimplify(BasicBlock BB, BasicBlock Pred,
				DeferredDominance *DDT = nullptr);

	/// BB is a block with one predecessor and its predecessor is known to have one			/// BB is a block with one predecessor and its predecessor is known to have one
	/// successor (BB!). Eliminate the edge between them, moving the instructions in			/// successor (BB!). Eliminate the edge between them, moving the instructions in
	/// the predecessor into BB. This deletes the predecessor block.			/// the predecessor into BB. This deletes the predecessor block.
	void MergeBasicBlockIntoOnlyPred(BasicBlock BB, DominatorTree DT = nullptr);			void MergeBasicBlockIntoOnlyPred(BasicBlock BB, DominatorTree DT = nullptr,
				DeferredDominance *DDT = nullptr);

	/// BB is known to contain an unconditional branch, and contains no instructions			/// BB is known to contain an unconditional branch, and contains no instructions
	/// other than PHI nodes, potential debug intrinsics and the branch. If			/// other than PHI nodes, potential debug intrinsics and the branch. If
	/// possible, eliminate BB by rewriting all the predecessors to branch to the			/// possible, eliminate BB by rewriting all the predecessors to branch to the
	/// successor block and return true. If we can't transform, return false.			/// successor block and return true. If we can't transform, return false.
	bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);			bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
				DeferredDominance *DDT = nullptr);

	/// Check for and eliminate duplicate PHI nodes in this block. This doesn't try			/// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
	/// to be clever about PHI nodes which differ only in the order of the incoming			/// to be clever about PHI nodes which differ only in the order of the incoming
	/// values, but instcombine orders them so it usually won't matter.			/// values, but instcombine orders them so it usually won't matter.
	bool EliminateDuplicatePHINodes(BasicBlock *BB);			bool EliminateDuplicatePHINodes(BasicBlock *BB);

	/// This function is used to do simplification of a CFG. For example, it			/// This function is used to do simplification of a CFG. For example, it
	/// adjusts branches to branches to eliminate the extra hop, it eliminates			/// adjusts branches to branches to eliminate the extra hop, it eliminates
	▲ Show 20 Lines • Show All 186 Lines • ▼ Show 20 Lines

	/// Remove all instructions from a basic block other than it's terminator			/// Remove all instructions from a basic block other than it's terminator
	/// and any present EH pad instructions.			/// and any present EH pad instructions.
	unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);			unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);

	/// Insert an unreachable instruction before the specified			/// Insert an unreachable instruction before the specified
	/// instruction, making it and the rest of the code in the block dead.			/// instruction, making it and the rest of the code in the block dead.
	unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,			unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,
	bool PreserveLCSSA = false);			bool PreserveLCSSA = false,
				DeferredDominance *DDT = nullptr);

	/// Convert the CallInst to InvokeInst with the specified unwind edge basic			/// Convert the CallInst to InvokeInst with the specified unwind edge basic
	/// block. This also splits the basic block where CI is located, because			/// block. This also splits the basic block where CI is located, because
	/// InvokeInst is a terminator instruction. Returns the newly split basic			/// InvokeInst is a terminator instruction. Returns the newly split basic
	/// block.			/// block.
	BasicBlock changeToInvokeAndSplitBasicBlock(CallInst CI,			BasicBlock changeToInvokeAndSplitBasicBlock(CallInst CI,
	BasicBlock *UnwindEdge);			BasicBlock *UnwindEdge);

	/// Replace 'BB's terminator with one that does not have an unwind successor			/// Replace 'BB's terminator with one that does not have an unwind successor
	/// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind			/// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind
	/// successor.			/// successor.
	///			///
	/// \param BB Block whose terminator will be replaced. Its terminator must			/// \param BB Block whose terminator will be replaced. Its terminator must
	/// have an unwind successor.			/// have an unwind successor.
	void removeUnwindEdge(BasicBlock *BB);			void removeUnwindEdge(BasicBlock BB, DeferredDominance DDT = nullptr);

	/// Remove all blocks that can not be reached from the function's entry.			/// Remove all blocks that can not be reached from the function's entry.
	///			///
	/// Returns true if any basic block was removed.			/// Returns true if any basic block was removed.
	bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr);			bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
				DeferredDominance *DDT = nullptr);

	/// Combine the metadata of two instructions so that K can replace J			/// Combine the metadata of two instructions so that K can replace J
	///			///
	/// Metadata not listed as known via KnownIDs is removed			/// Metadata not listed as known via KnownIDs is removed
	void combineMetadata(Instruction K, const Instruction J, ArrayRef<unsigned> KnownIDs);			void combineMetadata(Instruction K, const Instruction J, ArrayRef<unsigned> KnownIDs);

	/// Combine the metadata of two instructions so that K can replace J. This			/// Combine the metadata of two instructions so that K can replace J. This
	/// specifically handles the case of CSE-like transformations.			/// specifically handles the case of CSE-like transformations.
	▲ Show 20 Lines • Show All 81 Lines • Show Last 20 Lines

llvm/trunk/lib/IR/Dominators.cpp

Show All 12 Lines
// needed to support the Verifier pass.		// needed to support the Verifier pass.
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#include "llvm/IR/Dominators.h"		#include "llvm/IR/Dominators.h"
#include "llvm/ADT/DepthFirstIterator.h"		#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"		#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/IR/CFG.h"		#include "llvm/IR/CFG.h"
		#include "llvm/IR/Constants.h"
#include "llvm/IR/Instructions.h"		#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"		#include "llvm/IR/PassManager.h"
#include "llvm/Support/CommandLine.h"		#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"		#include "llvm/Support/Debug.h"
#include "llvm/Support/GenericDomTreeConstruction.h"		#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/raw_ostream.h"		#include "llvm/Support/raw_ostream.h"
#include <algorithm>		#include <algorithm>
using namespace llvm;		using namespace llvm;
▲ Show 20 Lines • Show All 355 Lines • ▼ Show 20 Lines	void DominatorTreeWrapperPass::verifyAnalysis() const {
if (VerifyDomInfo)		if (VerifyDomInfo)
DT.verifyDomTree();		DT.verifyDomTree();
}		}

void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {		void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
DT.print(OS);		DT.print(OS);
}		}

		//===----------------------------------------------------------------------===//
		// DeferredDominance Implementation
		//===----------------------------------------------------------------------===//
		//
		// The implementation details of the DeferredDominance class which allows
		// one to queue updates to a DominatorTree.
		//
		//===----------------------------------------------------------------------===//

		/// \brief Queues multiple updates and discards duplicates.
		void DeferredDominance::applyUpdates(
		ArrayRef<DominatorTree::UpdateType> Updates) {
		SmallVector<DominatorTree::UpdateType, 8> Seen;
		for (auto U : Updates)
		// Avoid duplicates to applyUpdate() to save on analysis.
		if (std::none_of(Seen.begin(), Seen.end(),
		[U](DominatorTree::UpdateType S) { return S == U; })) {
		Seen.push_back(U);
		applyUpdate(U.getKind(), U.getFrom(), U.getTo());
		}
		}

		/// \brief Helper method for a single edge insertion. It's almost always better
		/// to batch updates and call applyUpdates to quickly remove duplicate edges.
		/// This is best used when there is only a single insertion needed to update
		/// Dominators.
		void DeferredDominance::insertEdge(BasicBlock From, BasicBlock To) {
		applyUpdate(DominatorTree::Insert, From, To);
		}

		/// \brief Helper method for a single edge deletion. It's almost always better
		/// to batch updates and call applyUpdates to quickly remove duplicate edges.
		/// This is best used when there is only a single deletion needed to update
		/// Dominators.
		void DeferredDominance::deleteEdge(BasicBlock From, BasicBlock To) {
		applyUpdate(DominatorTree::Delete, From, To);
		}

		/// \brief Delays the deletion of a basic block until a flush() event.
		void DeferredDominance::deleteBB(BasicBlock *DelBB) {
		assert(DelBB && "Invalid push_back of nullptr DelBB.");
		assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
		// DelBB is unreachable and all its instructions are dead.
		while (!DelBB->empty()) {
		Instruction &I = DelBB->back();
		// Replace used instructions with an arbitrary value (undef).
		if (!I.use_empty())
		I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
		DelBB->getInstList().pop_back();
		}
		// Make sure DelBB has a valid terminator instruction. As long as DelBB is a
		// Child of Function F it must contain valid IR.
		new UnreachableInst(DelBB->getContext(), DelBB);
		DeletedBBs.insert(DelBB);
		}

		/// \brief Returns true if DelBB is awaiting deletion at a flush() event.
		bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
		if (DeletedBBs.empty())
		return false;
		return DeletedBBs.count(DelBB) != 0;
		}

		/// \brief Flushes all pending updates and block deletions. Returns a
		/// correct DominatorTree reference to be used by the caller for analysis.
		DominatorTree &DeferredDominance::flush() {
		// Updates to DT must happen before blocks are deleted below. Otherwise the
		// DT traversal will encounter badref blocks and assert.
		if (!PendUpdates.empty()) {
		DT.applyUpdates(PendUpdates);
		PendUpdates.clear();
		}
		flushDelBB();
		return DT;
		}

		/// \brief Drops all internal state and forces a (slow) recalculation of the
		/// DominatorTree based on the current state of the LLVM IR in F. This should
		/// only be used in corner cases such as the Entry block of F being deleted.
		void DeferredDominance::recalculate(Function &F) {
		// flushDelBB must be flushed before the recalculation. The state of the IR
		// must be consistent before the DT traversal algorithm determines the
		// actual DT.
		if (flushDelBB() \|\| !PendUpdates.empty()) {
		DT.recalculate(F);
		PendUpdates.clear();
		}
		}

		/// \brief Debug method to help view the state of pending updates.
		#if !defined(NDEBUG) \|\| defined(LLVM_ENABLE_DUMP)
		LLVM_DUMP_METHOD void DeferredDominance::dump() const {
		raw_ostream &OS = llvm::dbgs();
		OS << "PendUpdates:\n";
		int I = 0;
		for (auto U : PendUpdates) {
		OS << " " << I << " : ";
		++I;
		if (U.getKind() == DominatorTree::Insert)
		OS << "Insert, ";
		else
		OS << "Delete, ";
		BasicBlock *From = U.getFrom();
		if (From) {
		auto S = From->getName();
		if (!From->hasName())
		S = "(no name)";
		OS << S << "(" << From << "), ";
		} else {
		OS << "(badref), ";
		}
		BasicBlock *To = U.getTo();
		if (To) {
		auto S = To->getName();
		if (!To->hasName())
		S = "(no_name)";
		OS << S << "(" << To << ")\n";
		} else {
		OS << "(badref)\n";
		}
		}
		OS << "DeletedBBs:\n";
		I = 0;
		for (auto BB : DeletedBBs) {
		OS << " " << I << " : ";
		++I;
		if (BB->hasName())
		OS << BB->getName() << "(";
		else
		OS << "(no_name)(";
		OS << BB << ")\n";
		}
		}
		#endif

		/// Apply an update (Kind, From, To) to the internal queued updates. The
		/// update is only added when determined to be necessary. Checks for
		/// self-domination, unnecessary updates, duplicate requests, and balanced
		/// pairs of requests are all performed. Returns true if the update is
		/// queued and false if it is discarded.
		bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
		BasicBlock From, BasicBlock To) {
		if (From == To)
		return false; // Cannot dominate self; discard update.

		// Discard updates by inspecting the current state of successors of From.
		// Since applyUpdate() must be called after the Terminator of From is
		// altered we can determine if the update is unnecessary.
		bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
		[To](BasicBlock *B) { return B == To; });
		if (Kind == DominatorTree::Insert && !HasEdge)
		return false; // Unnecessary Insert: edge does not exist in IR.
		if (Kind == DominatorTree::Delete && HasEdge)
		return false; // Unnecessary Delete: edge still exists in IR.

		// Analyze pending updates to determine if the update is unnecessary.
		DominatorTree::UpdateType Update = {Kind, From, To};
		DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
		? DominatorTree::Insert
		: DominatorTree::Delete,
		From, To};
		for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
		if (Update == *I)
		return false; // Discard duplicate updates.
		if (Invert == *I) {
		// Update and Invert are both valid (equivalent to a no-op). Remove
		// Invert from PendUpdates and discard the Update.
		PendUpdates.erase(I);
		return false;
		}
		}
		PendUpdates.push_back(Update); // Save the valid update.
		return true;
		}

		/// Performs all pending basic block deletions. We have to defer the deletion
		/// of these blocks until after the DominatorTree updates are applied. The
		/// internal workings of the DominatorTree code expect every update's From
		/// and To blocks to exist and to be a member of the same Function.
		bool DeferredDominance::flushDelBB() {
		if (DeletedBBs.empty())
		return false;
		for (auto *BB : DeletedBBs)
		BB->eraseFromParent();
		DeletedBBs.clear();
		return true;
		}

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

Show First 20 Lines • Show All 72 Lines • ▼ Show 20 Lines	public:

CorrelatedValuePropagation(): FunctionPass(ID) {		CorrelatedValuePropagation(): FunctionPass(ID) {
initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());		initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
}		}

bool runOnFunction(Function &F) override;		bool runOnFunction(Function &F) override;

void getAnalysisUsage(AnalysisUsage &AU) const override {		void getAnalysisUsage(AnalysisUsage &AU) const override {
		AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<LazyValueInfoWrapperPass>();		AU.addRequired<LazyValueInfoWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();		AU.addPreserved<GlobalsAAWrapperPass>();
}		}
};		};

} // end anonymous namespace		} // end anonymous namespace

char CorrelatedValuePropagation::ID = 0;		char CorrelatedValuePropagation::ID = 0;

INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",		INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
"Value Propagation", false, false)		"Value Propagation", false, false)
		INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)		INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",		INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
"Value Propagation", false, false)		"Value Propagation", false, false)

// Public interface to the Value Propagation pass		// Public interface to the Value Propagation pass
Pass *llvm::createCorrelatedValuePropagationPass() {		Pass *llvm::createCorrelatedValuePropagationPass() {
return new CorrelatedValuePropagation();		return new CorrelatedValuePropagation();
}		}
▲ Show 20 Lines • Show All 574 Lines • Show Last 20 Lines

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

Show First 20 Lines • Show All 125 Lines • ▼ Show 20 Lines	public:

JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {		JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
initializeJumpThreadingPass(*PassRegistry::getPassRegistry());		initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
}		}

bool runOnFunction(Function &F) override;		bool runOnFunction(Function &F) override;

void getAnalysisUsage(AnalysisUsage &AU) const override {		void getAnalysisUsage(AnalysisUsage &AU) const override {
if (PrintLVIAfterJumpThreading)
AU.addRequired<DominatorTreeWrapperPass>();		AU.addRequired<DominatorTreeWrapperPass>();
		AU.addPreserved<DominatorTreeWrapperPass>();
AU.addRequired<AAResultsWrapperPass>();		AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<LazyValueInfoWrapperPass>();		AU.addRequired<LazyValueInfoWrapperPass>();
		AU.addPreserved<LazyValueInfoWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();		AU.addPreserved<GlobalsAAWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();		AU.addRequired<TargetLibraryInfoWrapperPass>();
}		}

void releaseMemory() override { Impl.releaseMemory(); }		void releaseMemory() override { Impl.releaseMemory(); }
};		};

} // end anonymous namespace		} // end anonymous namespace

char JumpThreading::ID = 0;		char JumpThreading::ID = 0;

INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",		INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
"Jump Threading", false, false)		"Jump Threading", false, false)
		INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)		INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)		INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)		INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(JumpThreading, "jump-threading",		INITIALIZE_PASS_END(JumpThreading, "jump-threading",
"Jump Threading", false, false)		"Jump Threading", false, false)

// Public interface to the Jump Threading pass		// Public interface to the Jump Threading pass
FunctionPass *llvm::createJumpThreadingPass(int Threshold) {		FunctionPass *llvm::createJumpThreadingPass(int Threshold) {
▲ Show 20 Lines • Show All 114 Lines • ▼ Show 20 Lines	static void updatePredecessorProfileMetadata(PHINode PN, BasicBlock BB) {
}		}
}		}

/// runOnFunction - Toplevel algorithm.		/// runOnFunction - Toplevel algorithm.
bool JumpThreading::runOnFunction(Function &F) {		bool JumpThreading::runOnFunction(Function &F) {
if (skipFunction(F))		if (skipFunction(F))
return false;		return false;
auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();		auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
		// Get DT analysis before LVI. When LVI is initialized it conditionally adds
		// DT if it's available.
		auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();		auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();		auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
		DeferredDominance DDT(*DT);
std::unique_ptr<BlockFrequencyInfo> BFI;		std::unique_ptr<BlockFrequencyInfo> BFI;
std::unique_ptr<BranchProbabilityInfo> BPI;		std::unique_ptr<BranchProbabilityInfo> BPI;
bool HasProfileData = F.hasProfileData();		bool HasProfileData = F.hasProfileData();
if (HasProfileData) {		if (HasProfileData) {
LoopInfo LI{DominatorTree(F)};		LoopInfo LI{DominatorTree(F)};
BPI.reset(new BranchProbabilityInfo(F, LI, TLI));		BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));		BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
}		}

bool Changed = Impl.runImpl(F, TLI, LVI, AA, HasProfileData, std::move(BFI),		bool Changed = Impl.runImpl(F, TLI, LVI, AA, &DDT, HasProfileData,
std::move(BPI));		std::move(BFI), std::move(BPI));
if (PrintLVIAfterJumpThreading) {		if (PrintLVIAfterJumpThreading) {
dbgs() << "LVI for function '" << F.getName() << "':\n";		dbgs() << "LVI for function '" << F.getName() << "':\n";
LVI->printLVI(F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),		LVI->printLVI(F, *DT, dbgs());
dbgs());
}		}
return Changed;		return Changed;
}		}

PreservedAnalyses JumpThreadingPass::run(Function &F,		PreservedAnalyses JumpThreadingPass::run(Function &F,
FunctionAnalysisManager &AM) {		FunctionAnalysisManager &AM) {
auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);		auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
		// Get DT analysis before LVI. When LVI is initialized it conditionally adds
		// DT if it's available.
		auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
auto &LVI = AM.getResult<LazyValueAnalysis>(F);		auto &LVI = AM.getResult<LazyValueAnalysis>(F);
auto &AA = AM.getResult<AAManager>(F);		auto &AA = AM.getResult<AAManager>(F);
		DeferredDominance DDT(DT);

std::unique_ptr<BlockFrequencyInfo> BFI;		std::unique_ptr<BlockFrequencyInfo> BFI;
std::unique_ptr<BranchProbabilityInfo> BPI;		std::unique_ptr<BranchProbabilityInfo> BPI;
if (F.hasProfileData()) {		if (F.hasProfileData()) {
LoopInfo LI{DominatorTree(F)};		LoopInfo LI{DominatorTree(F)};
BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));		BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));		BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
}		}

bool Changed = runImpl(F, &TLI, &LVI, &AA, HasProfileData, std::move(BFI),		bool Changed = runImpl(F, &TLI, &LVI, &AA, &DDT, HasProfileData,
std::move(BPI));		std::move(BFI), std::move(BPI));

if (!Changed)		if (!Changed)
return PreservedAnalyses::all();		return PreservedAnalyses::all();
PreservedAnalyses PA;		PreservedAnalyses PA;
PA.preserve<GlobalsAA>();		PA.preserve<GlobalsAA>();
		PA.preserve<DominatorTreeAnalysis>();
		PA.preserve<LazyValueAnalysis>();
return PA;		return PA;
}		}

bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,		bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
LazyValueInfo LVI_, AliasAnalysis AA_,		LazyValueInfo LVI_, AliasAnalysis AA_,
bool HasProfileData_,		DeferredDominance *DDT_, bool HasProfileData_,
std::unique_ptr<BlockFrequencyInfo> BFI_,		std::unique_ptr<BlockFrequencyInfo> BFI_,
std::unique_ptr<BranchProbabilityInfo> BPI_) {		std::unique_ptr<BranchProbabilityInfo> BPI_) {
DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");		DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
TLI = TLI_;		TLI = TLI_;
LVI = LVI_;		LVI = LVI_;
AA = AA_;		AA = AA_;
		DDT = DDT_;
BFI.reset();		BFI.reset();
BPI.reset();		BPI.reset();
// When profile data is available, we need to update edge weights after		// When profile data is available, we need to update edge weights after
// successful jump threading, which requires both BPI and BFI being available.		// successful jump threading, which requires both BPI and BFI being available.
HasProfileData = HasProfileData_;		HasProfileData = HasProfileData_;
auto *GuardDecl = F.getParent()->getFunction(		auto *GuardDecl = F.getParent()->getFunction(
Intrinsic::getName(Intrinsic::experimental_guard));		Intrinsic::getName(Intrinsic::experimental_guard));
HasGuards = GuardDecl && !GuardDecl->use_empty();		HasGuards = GuardDecl && !GuardDecl->use_empty();
if (HasProfileData) {		if (HasProfileData) {
BPI = std::move(BPI_);		BPI = std::move(BPI_);
BFI = std::move(BFI_);		BFI = std::move(BFI_);
}		}

// Remove unreachable blocks from function as they may result in infinite		// Remove unreachable blocks from function as they may result in infinite
// loop. We do threading if we found something profitable. Jump threading a		// loop. We do threading if we found something profitable. Jump threading a
// branch can create other opportunities. If these opportunities form a cycle		// branch can create other opportunities. If these opportunities form a cycle
// i.e. if any jump threading is undoing previous threading in the path, then		// i.e. if any jump threading is undoing previous threading in the path, then
// we will loop forever. We take care of this issue by not jump threading for		// we will loop forever. We take care of this issue by not jump threading for
// back edges. This works for normal cases but not for unreachable blocks as		// back edges. This works for normal cases but not for unreachable blocks as
// they may have cycle with no back edge.		// they may have cycle with no back edge.
bool EverChanged = false;		bool EverChanged = false;
EverChanged \|= removeUnreachableBlocks(F, LVI);		EverChanged \|= removeUnreachableBlocks(F, LVI, DDT);

FindLoopHeaders(F);		FindLoopHeaders(F);

bool Changed;		bool Changed;
do {		do {
Changed = false;		Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E;) {		for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
BasicBlock BB = &I;		BasicBlock BB = &I;
// Thread all of the branches we can over this block.		// Thread all of the branches we can over this block.
while (ProcessBlock(BB))		while (ProcessBlock(BB))
Changed = true;		Changed = true;

++I;		++I;

		// Don't thread branches over a block that's slated for deletion.
		if (DDT->pendingDeletedBB(BB))
		continue;

// If the block is trivially dead, zap it. This eliminates the successor		// If the block is trivially dead, zap it. This eliminates the successor
// edges which simplifies the CFG.		// edges which simplifies the CFG.
if (pred_empty(BB) &&		if (pred_empty(BB) &&
BB != &BB->getParent()->getEntryBlock()) {		BB != &BB->getParent()->getEntryBlock()) {
DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()		DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()
<< "' with terminator: " << *BB->getTerminator() << '\n');		<< "' with terminator: " << *BB->getTerminator() << '\n');
LoopHeaders.erase(BB);		LoopHeaders.erase(BB);
LVI->eraseBlock(BB);		LVI->eraseBlock(BB);
DeleteDeadBlock(BB);		DeleteDeadBlock(BB, DDT);
Changed = true;		Changed = true;
continue;		continue;
}		}

BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());		BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());

// Can't thread an unconditional jump, but if the block is "almost		// Can't thread an unconditional jump, but if the block is "almost
// empty", we can replace uses of it with uses of the successor and make		// empty", we can replace uses of it with uses of the successor and make
// this dead.		// this dead.
// We should not eliminate the loop header or latch either, because		// We should not eliminate the loop header or latch either, because
// eliminating a loop header or latch might later prevent LoopSimplify		// eliminating a loop header or latch might later prevent LoopSimplify
// from transforming nested loops into simplified form. We will rely on		// from transforming nested loops into simplified form. We will rely on
// later passes in backend to clean up empty blocks.		// later passes in backend to clean up empty blocks.
if (BI && BI->isUnconditional() &&		if (BI && BI->isUnconditional() &&
BB != &BB->getParent()->getEntryBlock() &&		BB != &BB->getParent()->getEntryBlock() &&
// If the terminator is the only non-phi instruction, try to nuke it.		// If the terminator is the only non-phi instruction, try to nuke it.
BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB) &&		BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB) &&
!LoopHeaders.count(BI->getSuccessor(0))) {		!LoopHeaders.count(BI->getSuccessor(0))) {
// FIXME: It is always conservatively correct to drop the info		// FIXME: It is always conservatively correct to drop the info
// for a block even if it doesn't get erased. This isn't totally		// for a block even if it doesn't get erased. This isn't totally
// awesome, but it allows us to use AssertingVH to prevent nasty		// awesome, but it allows us to use AssertingVH to prevent nasty
// dangling pointer issues within LazyValueInfo.		// dangling pointer issues within LazyValueInfo.
LVI->eraseBlock(BB);		LVI->eraseBlock(BB);
if (TryToSimplifyUncondBranchFromEmptyBlock(BB))		if (TryToSimplifyUncondBranchFromEmptyBlock(BB, DDT))
Changed = true;		Changed = true;
}		}
}		}
EverChanged \|= Changed;		EverChanged \|= Changed;
} while (Changed);		} while (Changed);

LoopHeaders.clear();		LoopHeaders.clear();
		DDT->flush();
return EverChanged;		return EverChanged;
}		}

// Replace uses of Cond with ToVal when safe to do so. If all uses are		// Replace uses of Cond with ToVal when safe to do so. If all uses are
// replaced, we can remove Cond. We cannot blindly replace all uses of Cond		// replaced, we can remove Cond. We cannot blindly replace all uses of Cond
// because we may incorrectly replace uses when guards/assumes are uses of		// because we may incorrectly replace uses when guards/assumes are uses of
// of `Cond` and we used the guards/assume to reason about the `Cond` value		// of `Cond` and we used the guards/assume to reason about the `Cond` value
// at the end of block. RAUW unconditionally replaces all uses		// at the end of block. RAUW unconditionally replaces all uses
▲ Show 20 Lines • Show All 507 Lines • ▼ Show 20 Lines	static bool hasAddressTakenAndUsed(BasicBlock *BB) {
return !BA->use_empty();		return !BA->use_empty();
}		}

/// ProcessBlock - If there are any predecessors whose control can be threaded		/// ProcessBlock - If there are any predecessors whose control can be threaded
/// through to a successor, transform them now.		/// through to a successor, transform them now.
bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {		bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
// If the block is trivially dead, just return and let the caller nuke it.		// If the block is trivially dead, just return and let the caller nuke it.
// This simplifies other transformations.		// This simplifies other transformations.
if (pred_empty(BB) &&		if (DDT->pendingDeletedBB(BB) \|\|
BB != &BB->getParent()->getEntryBlock())		(pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
return false;		return false;

// If this block has a single predecessor, and if that pred has a single		// If this block has a single predecessor, and if that pred has a single
// successor, merge the blocks. This encourages recursive jump threading		// successor, merge the blocks. This encourages recursive jump threading
// because now the condition in this block can be threaded through		// because now the condition in this block can be threaded through
// predecessors of our predecessor block.		// predecessors of our predecessor block.
if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {		if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
const TerminatorInst *TI = SinglePred->getTerminator();		const TerminatorInst *TI = SinglePred->getTerminator();
if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&		if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
SinglePred != BB && !hasAddressTakenAndUsed(BB)) {		SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
// If SinglePred was a loop header, BB becomes one.		// If SinglePred was a loop header, BB becomes one.
if (LoopHeaders.erase(SinglePred))		if (LoopHeaders.erase(SinglePred))
LoopHeaders.insert(BB);		LoopHeaders.insert(BB);

LVI->eraseBlock(SinglePred);		LVI->eraseBlock(SinglePred);
MergeBasicBlockIntoOnlyPred(BB);		MergeBasicBlockIntoOnlyPred(BB, nullptr, DDT);

// Now that BB is merged into SinglePred (i.e. SinglePred Code followed by		// Now that BB is merged into SinglePred (i.e. SinglePred Code followed by
// BB code within one basic block `BB`), we need to invalidate the LVI		// BB code within one basic block `BB`), we need to invalidate the LVI
// information associated with BB, because the LVI information need not be		// information associated with BB, because the LVI information need not be
// true for all of BB after the merge. For example,		// true for all of BB after the merge. For example,
// Before the merge, LVI info and code is as follows:		// Before the merge, LVI info and code is as follows:
// SinglePred: <LVI info1 for %p val>		// SinglePred: <LVI info1 for %p val>
// %y = use of %p		// %y = use of %p
▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines	if (SimpleVal) {
Condition = SimpleVal;		Condition = SimpleVal;
}		}
}		}

// If the terminator is branching on an undef, we can pick any of the		// If the terminator is branching on an undef, we can pick any of the
// successors to branch to. Let GetBestDestForJumpOnUndef decide.		// successors to branch to. Let GetBestDestForJumpOnUndef decide.
if (isa<UndefValue>(Condition)) {		if (isa<UndefValue>(Condition)) {
unsigned BestSucc = GetBestDestForJumpOnUndef(BB);		unsigned BestSucc = GetBestDestForJumpOnUndef(BB);
		std::vector<DominatorTree::UpdateType> Updates;

// Fold the branch/switch.		// Fold the branch/switch.
TerminatorInst *BBTerm = BB->getTerminator();		TerminatorInst *BBTerm = BB->getTerminator();
		Updates.reserve(BBTerm->getNumSuccessors());
for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {		for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
if (i == BestSucc) continue;		if (i == BestSucc) continue;
BBTerm->getSuccessor(i)->removePredecessor(BB, true);		BasicBlock *Succ = BBTerm->getSuccessor(i);
		Succ->removePredecessor(BB, true);
		Updates.push_back({DominatorTree::Delete, BB, Succ});
}		}

DEBUG(dbgs() << " In block '" << BB->getName()		DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding undef terminator: " << *BBTerm << '\n');		<< "' folding undef terminator: " << *BBTerm << '\n');
BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);		BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
BBTerm->eraseFromParent();		BBTerm->eraseFromParent();
		DDT->applyUpdates(Updates);
return true;		return true;
}		}

// If the terminator of this block is branching on a constant, simplify the		// If the terminator of this block is branching on a constant, simplify the
// terminator to an unconditional branch. This can occur due to threading in		// terminator to an unconditional branch. This can occur due to threading in
// other blocks.		// other blocks.
if (getKnownConstant(Condition, Preference)) {		if (getKnownConstant(Condition, Preference)) {
DEBUG(dbgs() << " In block '" << BB->getName()		DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding terminator: " << *BB->getTerminator() << '\n');		<< "' folding terminator: " << *BB->getTerminator() << '\n');
++NumFolds;		++NumFolds;
ConstantFoldTerminator(BB, true);		ConstantFoldTerminator(BB, true, nullptr, DDT);
return true;		return true;
}		}

Instruction *CondInst = dyn_cast<Instruction>(Condition);		Instruction *CondInst = dyn_cast<Instruction>(Condition);

// All the rest of our checks depend on the condition being an instruction.		// All the rest of our checks depend on the condition being an instruction.
if (!CondInst) {		if (!CondInst) {
// FIXME: Unify this with code below.		// FIXME: Unify this with code below.
Show All 16 Lines	if (CondBr && CondConst) {
assert(CondBr->isConditional() && "Threading on unconditional terminator");		assert(CondBr->isConditional() && "Threading on unconditional terminator");

LazyValueInfo::Tristate Ret =		LazyValueInfo::Tristate Ret =
LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),		LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
CondConst, CondBr);		CondConst, CondBr);
if (Ret != LazyValueInfo::Unknown) {		if (Ret != LazyValueInfo::Unknown) {
unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;		unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;		unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);		BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
		ToRemoveSucc->removePredecessor(BB, true);
BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);		BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
CondBr->eraseFromParent();		CondBr->eraseFromParent();
if (CondCmp->use_empty())		if (CondCmp->use_empty())
CondCmp->eraseFromParent();		CondCmp->eraseFromParent();
// We can safely replace some uses of the CondInst if it has		// We can safely replace some uses of the CondInst if it has
// exactly one value as returned by LVI. RAUW is incorrect in the		// exactly one value as returned by LVI. RAUW is incorrect in the
// presence of guards and assumes, that have the `Cond` as the use. This		// presence of guards and assumes, that have the `Cond` as the use. This
// is because we use the guards/assume to reason about the `Cond` value		// is because we use the guards/assume to reason about the `Cond` value
// at the end of block, but RAUW unconditionally replaces all uses		// at the end of block, but RAUW unconditionally replaces all uses
// including the guards/assumes themselves and the uses before the		// including the guards/assumes themselves and the uses before the
// guard/assume.		// guard/assume.
else if (CondCmp->getParent() == BB) {		else if (CondCmp->getParent() == BB) {
auto *CI = Ret == LazyValueInfo::True ?		auto *CI = Ret == LazyValueInfo::True ?
ConstantInt::getTrue(CondCmp->getType()) :		ConstantInt::getTrue(CondCmp->getType()) :
ConstantInt::getFalse(CondCmp->getType());		ConstantInt::getFalse(CondCmp->getType());
ReplaceFoldableUses(CondCmp, CI);		ReplaceFoldableUses(CondCmp, CI);
}		}
		DDT->deleteEdge(BB, ToRemoveSucc);
return true;		return true;
}		}

// We did not manage to simplify this branch, try to see whether		// We did not manage to simplify this branch, try to see whether
// CondCmp depends on a known phi-select pattern.		// CondCmp depends on a known phi-select pattern.
if (TryToUnfoldSelect(CondCmp, BB))		if (TryToUnfoldSelect(CondCmp, BB))
return true;		return true;
}		}
▲ Show 20 Lines • Show All 62 Lines • ▼ Show 20 Lines	if (!PBI \|\| !PBI->isConditional())
return false;		return false;
if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)		if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
return false;		return false;

bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;		bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
Optional<bool> Implication =		Optional<bool> Implication =
isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);		isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
if (Implication) {		if (Implication) {
BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB);		BasicBlock KeepSucc = BI->getSuccessor(Implication ? 0 : 1);
BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI);		BasicBlock RemoveSucc = BI->getSuccessor(Implication ? 1 : 0);
		RemoveSucc->removePredecessor(BB);
		BranchInst::Create(KeepSucc, BI);
BI->eraseFromParent();		BI->eraseFromParent();
		DDT->deleteEdge(BB, RemoveSucc);
return true;		return true;
}		}
CurrentBB = CurrentPred;		CurrentBB = CurrentPred;
CurrentPred = CurrentBB->getSinglePredecessor();		CurrentPred = CurrentBB->getSinglePredecessor();
}		}

return false;		return false;
}		}
▲ Show 20 Lines • Show All 390 Lines • ▼ Show 20 Lines	bool JumpThreadingPass::ProcessThreadableEdges(Value Cond, BasicBlock BB,

// If all the predecessors go to a single known successor, we want to fold,		// If all the predecessors go to a single known successor, we want to fold,
// not thread. By doing so, we do not need to duplicate the current block and		// not thread. By doing so, we do not need to duplicate the current block and
// also miss potential opportunities in case we dont/cant duplicate.		// also miss potential opportunities in case we dont/cant duplicate.
if (OnlyDest && OnlyDest != MultipleDestSentinel) {		if (OnlyDest && OnlyDest != MultipleDestSentinel) {
if (PredWithKnownDest ==		if (PredWithKnownDest ==
(size_t)std::distance(pred_begin(BB), pred_end(BB))) {		(size_t)std::distance(pred_begin(BB), pred_end(BB))) {
bool SeenFirstBranchToOnlyDest = false;		bool SeenFirstBranchToOnlyDest = false;
		std::vector <DominatorTree::UpdateType> Updates;
		Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
for (BasicBlock *SuccBB : successors(BB)) {		for (BasicBlock *SuccBB : successors(BB)) {
if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest)		if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.		SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
else		} else {
SuccBB->removePredecessor(BB, true); // This is unreachable successor.		SuccBB->removePredecessor(BB, true); // This is unreachable successor.
		Updates.push_back({DominatorTree::Delete, BB, SuccBB});
		}
}		}

// Finally update the terminator.		// Finally update the terminator.
TerminatorInst *Term = BB->getTerminator();		TerminatorInst *Term = BB->getTerminator();
BranchInst::Create(OnlyDest, Term);		BranchInst::Create(OnlyDest, Term);
Term->eraseFromParent();		Term->eraseFromParent();
		DDT->applyUpdates(Updates);

// If the condition is now dead due to the removal of the old terminator,		// If the condition is now dead due to the removal of the old terminator,
// erase it.		// erase it.
if (auto *CondInst = dyn_cast<Instruction>(Cond)) {		if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())		if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
CondInst->eraseFromParent();		CondInst->eraseFromParent();
// We can safely replace some uses of the CondInst if it has		// We can safely replace some uses of the CondInst if it has
// exactly one value as returned by LVI. RAUW is incorrect in the		// exactly one value as returned by LVI. RAUW is incorrect in the
▲ Show 20 Lines • Show All 346 Lines • ▼ Show 20 Lines	bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
// us to simplify any PHI nodes in BB.		// us to simplify any PHI nodes in BB.
TerminatorInst *PredTerm = PredBB->getTerminator();		TerminatorInst *PredTerm = PredBB->getTerminator();
for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)		for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
if (PredTerm->getSuccessor(i) == BB) {		if (PredTerm->getSuccessor(i) == BB) {
BB->removePredecessor(PredBB, true);		BB->removePredecessor(PredBB, true);
PredTerm->setSuccessor(i, NewBB);		PredTerm->setSuccessor(i, NewBB);
}		}

		DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
		{DominatorTree::Insert, PredBB, NewBB},
		{DominatorTree::Delete, PredBB, BB}});

// At this point, the IR is fully up to date and consistent. Do a quick scan		// At this point, the IR is fully up to date and consistent. Do a quick scan
// over the new instructions and zap any that are constants or dead. This		// over the new instructions and zap any that are constants or dead. This
// frequently happens because of phi translation.		// frequently happens because of phi translation.
SimplifyInstructionsInBlock(NewBB, TLI);		SimplifyInstructionsInBlock(NewBB, TLI);

// Update the edge weight from BB to SuccBB, which should be less than before.		// Update the edge weight from BB to SuccBB, which should be less than before.
UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);		UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);

// Threaded an edge!		// Threaded an edge!
++NumThreads;		++NumThreads;
return true;		return true;
}		}

/// Create a new basic block that will be the predecessor of BB and successor of		/// Create a new basic block that will be the predecessor of BB and successor of
/// all blocks in Preds. When profile data is available, update the frequency of		/// all blocks in Preds. When profile data is available, update the frequency of
/// this new block.		/// this new block.
BasicBlock JumpThreadingPass::SplitBlockPreds(BasicBlock BB,		BasicBlock JumpThreadingPass::SplitBlockPreds(BasicBlock BB,
ArrayRef<BasicBlock *> Preds,		ArrayRef<BasicBlock *> Preds,
const char *Suffix) {		const char *Suffix) {
		SmallVector<BasicBlock *, 2> NewBBs;

// Collect the frequencies of all predecessors of BB, which will be used to		// Collect the frequencies of all predecessors of BB, which will be used to
// update the edge weight on BB->SuccBB.		// update the edge weight of the result of splitting predecessors.
BlockFrequency PredBBFreq(0);		DenseMap<BasicBlock *, BlockFrequency> FreqMap;
if (HasProfileData)		if (HasProfileData)
for (auto Pred : Preds)		for (auto Pred : Preds)
PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB);		FreqMap.insert(std::make_pair(
		Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));

		// In the case when BB is a LandingPad block we create 2 new predecessors
		// instead of just one.
		if (BB->isLandingPad()) {
		std::string NewName = std::string(Suffix) + ".split-lp";
		SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs);
		} else {
		NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix));
		}

BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix);		std::vector<DominatorTree::UpdateType> Updates;
		Updates.reserve((2 * Preds.size()) + NewBBs.size());
		for (auto NewBB : NewBBs) {
		BlockFrequency NewBBFreq(0);
		Updates.push_back({DominatorTree::Insert, NewBB, BB});
		for (auto Pred : predecessors(NewBB)) {
		Updates.push_back({DominatorTree::Delete, Pred, BB});
		Updates.push_back({DominatorTree::Insert, Pred, NewBB});
		if (HasProfileData) // Update frequencies between Pred -> NewBB.
		NewBBFreq += FreqMap.lookup(Pred);
		}
		if (HasProfileData) // Apply the summed frequency to NewBB.
		BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
		}

// Set the block frequency of the newly created PredBB, which is the sum of		DDT->applyUpdates(Updates);
// frequencies of Preds.		return NewBBs[0];
if (HasProfileData)
BFI->setBlockFreq(PredBB, PredBBFreq.getFrequency());
return PredBB;
}		}

bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {		bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
const TerminatorInst *TI = BB->getTerminator();		const TerminatorInst *TI = BB->getTerminator();
assert(TI->getNumSuccessors() > 1 && "not a split");		assert(TI->getNumSuccessors() > 1 && "not a split");

MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);		MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
if (!WeightsNode)		if (!WeightsNode)
▲ Show 20 Lines • Show All 127 Lines • ▼ Show 20 Lines	unsigned DuplicationCost =
getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);		getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
if (DuplicationCost > BBDupThreshold) {		if (DuplicationCost > BBDupThreshold) {
DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()		DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
<< "' - Cost is too high: " << DuplicationCost << "\n");		<< "' - Cost is too high: " << DuplicationCost << "\n");
return false;		return false;
}		}

// And finally, do it! Start by factoring the predecessors if needed.		// And finally, do it! Start by factoring the predecessors if needed.
		std::vector<DominatorTree::UpdateType> Updates;
BasicBlock *PredBB;		BasicBlock *PredBB;
if (PredBBs.size() == 1)		if (PredBBs.size() == 1)
PredBB = PredBBs[0];		PredBB = PredBBs[0];
else {		else {
DEBUG(dbgs() << " Factoring out " << PredBBs.size()		DEBUG(dbgs() << " Factoring out " << PredBBs.size()
<< " common predecessors.\n");		<< " common predecessors.\n");
PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");		PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
}		}
		Updates.push_back({DominatorTree::Delete, PredBB, BB});

// Okay, we decided to do this! Clone all the instructions in BB onto the end		// Okay, we decided to do this! Clone all the instructions in BB onto the end
// of PredBB.		// of PredBB.
DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '"		DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '"
<< PredBB->getName() << "' to eliminate branch on phi. Cost: "		<< PredBB->getName() << "' to eliminate branch on phi. Cost: "
<< DuplicationCost << " block is:" << *BB << "\n");		<< DuplicationCost << " block is:" << *BB << "\n");

// Unless PredBB ends with an unconditional branch, split the edge so that we		// Unless PredBB ends with an unconditional branch, split the edge so that we
// can just clone the bits from BB into the end of the new PredBB.		// can just clone the bits from BB into the end of the new PredBB.
BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());		BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());

if (!OldPredBranch \|\| !OldPredBranch->isUnconditional()) {		if (!OldPredBranch \|\| !OldPredBranch->isUnconditional()) {
PredBB = SplitEdge(PredBB, BB);		BasicBlock *OldPredBB = PredBB;
		PredBB = SplitEdge(OldPredBB, BB);
		Updates.push_back({DominatorTree::Insert, OldPredBB, PredBB});
		Updates.push_back({DominatorTree::Insert, PredBB, BB});
		Updates.push_back({DominatorTree::Delete, OldPredBB, BB});
OldPredBranch = cast<BranchInst>(PredBB->getTerminator());		OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
}		}

// We are going to have to map operands from the original BB block into the		// We are going to have to map operands from the original BB block into the
// PredBB block. Evaluate PHI nodes in BB.		// PredBB block. Evaluate PHI nodes in BB.
DenseMap<Instruction, Value> ValueMapping;		DenseMap<Instruction, Value> ValueMapping;

BasicBlock::iterator BI = BB->begin();		BasicBlock::iterator BI = BB->begin();
Show All 25 Lines	if (Value *IV = SimplifyInstruction(
}		}
} else {		} else {
ValueMapping[&*BI] = New;		ValueMapping[&*BI] = New;
}		}
if (New) {		if (New) {
// Otherwise, insert the new instruction into the block.		// Otherwise, insert the new instruction into the block.
New->setName(BI->getName());		New->setName(BI->getName());
PredBB->getInstList().insert(OldPredBranch->getIterator(), New);		PredBB->getInstList().insert(OldPredBranch->getIterator(), New);
		// Update Dominance from simplified New instruction operands.
		for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
		if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
		Updates.push_back({DominatorTree::Insert, PredBB, SuccBB});
}		}
}		}

// Check to see if the targets of the branch had PHI nodes. If so, we need to		// Check to see if the targets of the branch had PHI nodes. If so, we need to
// add entries to the PHI nodes for branch from PredBB now.		// add entries to the PHI nodes for branch from PredBB now.
BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());		BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());
AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,		AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,
ValueMapping);		ValueMapping);
Show All 39 Lines	bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
}		}

// PredBB no longer jumps to BB, remove entries in the PHI node for the edge		// PredBB no longer jumps to BB, remove entries in the PHI node for the edge
// that we nuked.		// that we nuked.
BB->removePredecessor(PredBB, true);		BB->removePredecessor(PredBB, true);

// Remove the unconditional branch at the end of the PredBB block.		// Remove the unconditional branch at the end of the PredBB block.
OldPredBranch->eraseFromParent();		OldPredBranch->eraseFromParent();
		DDT->applyUpdates(Updates);

++NumDupes;		++NumDupes;
return true;		return true;
}		}

/// TryToUnfoldSelect - Look for blocks of the form		/// TryToUnfoldSelect - Look for blocks of the form
/// bb1:		/// bb1:
/// %a = select		/// %a = select
▲ Show 20 Lines • Show All 56 Lines • ▼ Show 20 Lines	if ((LHSFolds != LazyValueInfo::Unknown \|\|
NewBB->getInstList().insert(NewBB->end(), PredTerm);		NewBB->getInstList().insert(NewBB->end(), PredTerm);
// Create a conditional branch and update PHI nodes.		// Create a conditional branch and update PHI nodes.
BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);		BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
CondLHS->setIncomingValue(I, SI->getFalseValue());		CondLHS->setIncomingValue(I, SI->getFalseValue());
CondLHS->addIncoming(SI->getTrueValue(), NewBB);		CondLHS->addIncoming(SI->getTrueValue(), NewBB);
// The select is now dead.		// The select is now dead.
SI->eraseFromParent();		SI->eraseFromParent();

		DDT->applyUpdates({{DominatorTree::Insert, NewBB, BB},
		{DominatorTree::Insert, Pred, NewBB}});
// Update any other PHI nodes in BB.		// Update any other PHI nodes in BB.
for (BasicBlock::iterator BI = BB->begin();		for (BasicBlock::iterator BI = BB->begin();
PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)		PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
if (Phi != CondLHS)		if (Phi != CondLHS)
Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);		Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
return true;		return true;
}		}
}		}
▲ Show 20 Lines • Show All 62 Lines • ▼ Show 20 Lines	for (Use &U : PN->uses()) {
}		}
}		}

if (!SI)		if (!SI)
continue;		continue;
// Expand the select.		// Expand the select.
TerminatorInst *Term =		TerminatorInst *Term =
SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);		SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
		BasicBlock *SplitBB = SI->getParent();
		BasicBlock *NewBB = Term->getParent();
PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);		PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
NewPN->addIncoming(SI->getTrueValue(), Term->getParent());		NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
NewPN->addIncoming(SI->getFalseValue(), BB);		NewPN->addIncoming(SI->getFalseValue(), BB);
SI->replaceAllUsesWith(NewPN);		SI->replaceAllUsesWith(NewPN);
SI->eraseFromParent();		SI->eraseFromParent();
		// NewBB and SplitBB are newly created blocks which require insertion.
		std::vector<DominatorTree::UpdateType> Updates;
		Updates.reserve((2 * SplitBB->getTerminator()->getNumSuccessors()) + 3);
		Updates.push_back({DominatorTree::Insert, BB, SplitBB});
		Updates.push_back({DominatorTree::Insert, BB, NewBB});
		Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
		// BB's successors were moved to SplitBB, update DDT accordingly.
		for (auto *Succ : successors(SplitBB)) {
		Updates.push_back({DominatorTree::Delete, BB, Succ});
		Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
		}
		DDT->applyUpdates(Updates);
return true;		return true;
}		}
return false;		return false;
}		}

/// Try to propagate a guard from the current BB into one of its predecessors		/// Try to propagate a guard from the current BB into one of its predecessors
/// in case if another branch of execution implies that the condition of this		/// in case if another branch of execution implies that the condition of this
/// guard is always true. Currently we only process the simplest case that		/// guard is always true. Currently we only process the simplest case that
▲ Show 20 Lines • Show All 70 Lines • ▼ Show 20 Lines	else {
Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);		Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
if (Impl && *Impl)		if (Impl && *Impl)
FalseDestIsSafe = true;		FalseDestIsSafe = true;
}		}

if (!TrueDestIsSafe && !FalseDestIsSafe)		if (!TrueDestIsSafe && !FalseDestIsSafe)
return false;		return false;

BasicBlock *UnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;		BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
BasicBlock *GuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;		BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;

ValueToValueMapTy UnguardedMapping, GuardedMapping;		ValueToValueMapTy UnguardedMapping, GuardedMapping;
Instruction *AfterGuard = Guard->getNextNode();		Instruction *AfterGuard = Guard->getNextNode();
unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);		unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);
if (Cost > BBDupThreshold)		if (Cost > BBDupThreshold)
return false;		return false;
// Duplicate all instructions before the guard and the guard itself to the		// Duplicate all instructions before the guard and the guard itself to the
// branch where implication is not proved.		// branch where implication is not proved.
GuardedBlock = DuplicateInstructionsInSplitBetween(		BasicBlock *GuardedBlock = DuplicateInstructionsInSplitBetween(
BB, GuardedBlock, AfterGuard, GuardedMapping);		BB, PredGuardedBlock, AfterGuard, GuardedMapping);
assert(GuardedBlock && "Could not create the guarded block?");		assert(GuardedBlock && "Could not create the guarded block?");
// Duplicate all instructions before the guard in the unguarded branch.		// Duplicate all instructions before the guard in the unguarded branch.
// Since we have successfully duplicated the guarded block and this block		// Since we have successfully duplicated the guarded block and this block
// has fewer instructions, we expect it to succeed.		// has fewer instructions, we expect it to succeed.
UnguardedBlock = DuplicateInstructionsInSplitBetween(BB, UnguardedBlock,		BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween(
Guard, UnguardedMapping);		BB, PredUnguardedBlock, Guard, UnguardedMapping);
assert(UnguardedBlock && "Could not create the unguarded block?");		assert(UnguardedBlock && "Could not create the unguarded block?");
DEBUG(dbgs() << "Moved guard " << *Guard << " to block "		DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
<< GuardedBlock->getName() << "\n");		<< GuardedBlock->getName() << "\n");
		// DuplicateInstructionsInSplitBetween inserts a new block "BB.split" between
		// PredBB and BB. We need to perform two inserts and one delete for each of
		// the above calls to update Dominators.
		DDT->applyUpdates(
		fhahnUnsubmitted Not Done Reply Inline Actions I think DuplicateInstructionsInSplitBetween can easily update the DT itself: D44629. Is it better to do the update incrementally here or make DuplicateInstructionsInSplitBetween take care of it (via splitBlock)? Letting functions update the DT themselves seems to be what similar functions do. We do not have access to the plain DT here though, which makes that slightly trickier and that's why I want to check what's better before doing any changes here :) fhahn: I think DuplicateInstructionsInSplitBetween can easily update the DT itself: D44629. Is it…
		brzyckiAuthorUnsubmitted Not Done Reply Inline Actions Hi @fhahn , when I initially did the work to preserve `DT` across JumpThreading I tried to do two things: Minimize the changes to external calls. Update the `DT` real-time. Compile time testing showed that updating the `DT` real-time was just too slow. This not-so-great compromise is the deferred class we have today. Any time we have to call `DDT-flush()` incurs a compile-time penalty which is why you can find external calls that take `DT` as a parameter but I didn't use it because it'd require me to flush first. I'd also like to avoid having multiple functions that take both a `DT` and a `DDT` parameter. It complexifies function signatures, positional `nullPtr` placement, and more branchy checks inside these routines. I know that @kuhar is leading a GSoC topic to unify the DT/PDT/DDT interface and it may be worth following that before spending any of your time trying to hack on this mess... You are more than welcome to see if you can make changes here, just make sure test-suite ctmark isn't adversely impacted when you do. :) brzycki: Hi @fhahn , when I initially did the work to preserve `DT` across JumpThreading I tried to do…
		{// Guarded block split.
		{DominatorTree::Delete, PredGuardedBlock, BB},
		{DominatorTree::Insert, PredGuardedBlock, GuardedBlock},
		{DominatorTree::Insert, GuardedBlock, BB},
		// Unguarded block split.
		{DominatorTree::Delete, PredUnguardedBlock, BB},
		{DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock},
		{DominatorTree::Insert, UnguardedBlock, BB}});
// Some instructions before the guard may still have uses. For them, we need		// Some instructions before the guard may still have uses. For them, we need
// to create Phi nodes merging their copies in both guarded and unguarded		// to create Phi nodes merging their copies in both guarded and unguarded
// branches. Those instructions that have no uses can be just removed.		// branches. Those instructions that have no uses can be just removed.
SmallVector<Instruction *, 4> ToRemove;		SmallVector<Instruction *, 4> ToRemove;
for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)		for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
if (!isa<PHINode>(&*BI))		if (!isa<PHINode>(&*BI))
ToRemove.push_back(&*BI);		ToRemove.push_back(&*BI);

Show All 15 Lines

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

	Show All 39 Lines
	#include <cassert>			#include <cassert>
	#include <cstdint>			#include <cstdint>
	#include <string>			#include <string>
	#include <utility>			#include <utility>
	#include <vector>			#include <vector>

	using namespace llvm;			using namespace llvm;

	void llvm::DeleteDeadBlock(BasicBlock *BB) {			void llvm::DeleteDeadBlock(BasicBlock BB, DeferredDominance DDT) {
	assert((pred_begin(BB) == pred_end(BB) \|\|			assert((pred_begin(BB) == pred_end(BB) \|\|
	// Can delete self loop.			// Can delete self loop.
	BB->getSinglePredecessor() == BB) && "Block is not dead!");			BB->getSinglePredecessor() == BB) && "Block is not dead!");
	TerminatorInst *BBTerm = BB->getTerminator();			TerminatorInst *BBTerm = BB->getTerminator();
				std::vector<DominatorTree::UpdateType> Updates;

	// Loop through all of our successors and make sure they know that one			// Loop through all of our successors and make sure they know that one
	// of their predecessors is going away.			// of their predecessors is going away.
	for (BasicBlock *Succ : BBTerm->successors())			if (DDT)
				Updates.reserve(BBTerm->getNumSuccessors());
				for (BasicBlock *Succ : BBTerm->successors()) {
	Succ->removePredecessor(BB);			Succ->removePredecessor(BB);
				if (DDT)
				Updates.push_back({DominatorTree::Delete, BB, Succ});
				}

	// Zap all the instructions in the block.			// Zap all the instructions in the block.
	while (!BB->empty()) {			while (!BB->empty()) {
	Instruction &I = BB->back();			Instruction &I = BB->back();
	// If this instruction is used, replace uses with an arbitrary value.			// If this instruction is used, replace uses with an arbitrary value.
	// Because control flow can't get here, we don't care what we replace the			// Because control flow can't get here, we don't care what we replace the
	// value with. Note that since this block is unreachable, and all values			// value with. Note that since this block is unreachable, and all values
	// contained within it must dominate their uses, that all uses will			// contained within it must dominate their uses, that all uses will
	// eventually be removed (they are themselves dead).			// eventually be removed (they are themselves dead).
	if (!I.use_empty())			if (!I.use_empty())
	I.replaceAllUsesWith(UndefValue::get(I.getType()));			I.replaceAllUsesWith(UndefValue::get(I.getType()));
	BB->getInstList().pop_back();			BB->getInstList().pop_back();
	}			}

	// Zap the block!			if (DDT) {
	BB->eraseFromParent();			DDT->applyUpdates(Updates);
				DDT->deleteBB(BB); // Deferred deletion of BB.
				} else {
				BB->eraseFromParent(); // Zap the block!
				}
	}			}

	void llvm::FoldSingleEntryPHINodes(BasicBlock *BB,			void llvm::FoldSingleEntryPHINodes(BasicBlock *BB,
	MemoryDependenceResults *MemDep) {			MemoryDependenceResults *MemDep) {
	if (!isa<PHINode>(BB->begin())) return;			if (!isa<PHINode>(BB->begin())) return;

	while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {			while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
	if (PN->getIncomingValue(0) != PN)			if (PN->getIncomingValue(0) != PN)
	▲ Show 20 Lines • Show All 723 Lines • Show Last 20 Lines

llvm/trunk/lib/Transforms/Utils/Local.cpp

Show First 20 Lines • Show All 94 Lines • ▼ Show 20 Lines
/// ConstantFoldTerminator - If a terminator instruction is predicated on a		/// ConstantFoldTerminator - If a terminator instruction is predicated on a
/// constant value, convert it into an unconditional branch to the constant		/// constant value, convert it into an unconditional branch to the constant
/// destination. This is a nontrivial operation because the successors of this		/// destination. This is a nontrivial operation because the successors of this
/// basic block must have their PHI nodes updated.		/// basic block must have their PHI nodes updated.
/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch		/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
/// conditions and indirectbr addresses this might make dead if		/// conditions and indirectbr addresses this might make dead if
/// DeleteDeadConditions is true.		/// DeleteDeadConditions is true.
bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,		bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
const TargetLibraryInfo *TLI) {		const TargetLibraryInfo *TLI,
		DeferredDominance *DDT) {
TerminatorInst *T = BB->getTerminator();		TerminatorInst *T = BB->getTerminator();
IRBuilder<> Builder(T);		IRBuilder<> Builder(T);

// Branch - See if we are conditional jumping on constant		// Branch - See if we are conditional jumping on constant
if (auto *BI = dyn_cast<BranchInst>(T)) {		if (auto *BI = dyn_cast<BranchInst>(T)) {
if (BI->isUnconditional()) return false; // Can't optimize uncond branch		if (BI->isUnconditional()) return false; // Can't optimize uncond branch
BasicBlock *Dest1 = BI->getSuccessor(0);		BasicBlock *Dest1 = BI->getSuccessor(0);
BasicBlock *Dest2 = BI->getSuccessor(1);		BasicBlock *Dest2 = BI->getSuccessor(1);

if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {		if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
// Are we branching on constant?		// Are we branching on constant?
// YES. Change to unconditional branch...		// YES. Change to unconditional branch...
BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;		BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;		BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;

// Let the basic block know that we are letting go of it. Based on this,		// Let the basic block know that we are letting go of it. Based on this,
// it will adjust it's PHI nodes.		// it will adjust it's PHI nodes.
OldDest->removePredecessor(BB);		OldDest->removePredecessor(BB);

// Replace the conditional branch with an unconditional one.		// Replace the conditional branch with an unconditional one.
Builder.CreateBr(Destination);		Builder.CreateBr(Destination);
BI->eraseFromParent();		BI->eraseFromParent();
		if (DDT)
		DDT->deleteEdge(BB, OldDest);
return true;		return true;
}		}

if (Dest2 == Dest1) { // Conditional branch to same location?		if (Dest2 == Dest1) { // Conditional branch to same location?
// This branch matches something like this:		// This branch matches something like this:
// br bool %cond, label %Dest, label %Dest		// br bool %cond, label %Dest, label %Dest
// and changes it into: br label %Dest		// and changes it into: br label %Dest

▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines	for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
// Remove weight for this case.		// Remove weight for this case.
std::swap(Weights[idx+1], Weights.back());		std::swap(Weights[idx+1], Weights.back());
Weights.pop_back();		Weights.pop_back();
SI->setMetadata(LLVMContext::MD_prof,		SI->setMetadata(LLVMContext::MD_prof,
MDBuilder(BB->getContext()).		MDBuilder(BB->getContext()).
createBranchWeights(Weights));		createBranchWeights(Weights));
}		}
// Remove this entry.		// Remove this entry.
DefaultDest->removePredecessor(SI->getParent());		BasicBlock *ParentBB = SI->getParent();
		DefaultDest->removePredecessor(ParentBB);
i = SI->removeCase(i);		i = SI->removeCase(i);
e = SI->case_end();		e = SI->case_end();
		if (DDT)
		DDT->deleteEdge(ParentBB, DefaultDest);
continue;		continue;
}		}

// Otherwise, check to see if the switch only branches to one destination.		// Otherwise, check to see if the switch only branches to one destination.
// We do this by reseting "TheOnlyDest" to null when we find two non-equal		// We do this by reseting "TheOnlyDest" to null when we find two non-equal
// destinations.		// destinations.
if (i->getCaseSuccessor() != TheOnlyDest)		if (i->getCaseSuccessor() != TheOnlyDest)
TheOnlyDest = nullptr;		TheOnlyDest = nullptr;
Show All 9 Lines	if (auto *SI = dyn_cast<SwitchInst>(T)) {
}		}

// If we found a single destination that we can fold the switch into, do so		// If we found a single destination that we can fold the switch into, do so
// now.		// now.
if (TheOnlyDest) {		if (TheOnlyDest) {
// Insert the new branch.		// Insert the new branch.
Builder.CreateBr(TheOnlyDest);		Builder.CreateBr(TheOnlyDest);
BasicBlock *BB = SI->getParent();		BasicBlock *BB = SI->getParent();
		std::vector <DominatorTree::UpdateType> Updates;
		if (DDT)
		Updates.reserve(SI->getNumSuccessors() - 1);

// Remove entries from PHI nodes which we no longer branch to...		// Remove entries from PHI nodes which we no longer branch to...
for (BasicBlock *Succ : SI->successors()) {		for (BasicBlock *Succ : SI->successors()) {
// Found case matching a constant operand?		// Found case matching a constant operand?
if (Succ == TheOnlyDest)		if (Succ == TheOnlyDest) {
TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest		TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
else		} else {
Succ->removePredecessor(BB);		Succ->removePredecessor(BB);
		if (DDT)
		Updates.push_back({DominatorTree::Delete, BB, Succ});
		}
}		}

// Delete the old switch.		// Delete the old switch.
Value *Cond = SI->getCondition();		Value *Cond = SI->getCondition();
SI->eraseFromParent();		SI->eraseFromParent();
if (DeleteDeadConditions)		if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);		RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
		if (DDT)
		DDT->applyUpdates(Updates);
return true;		return true;
}		}

if (SI->getNumCases() == 1) {		if (SI->getNumCases() == 1) {
// Otherwise, we can fold this switch into a conditional branch		// Otherwise, we can fold this switch into a conditional branch
// instruction if it has only one non-default destination.		// instruction if it has only one non-default destination.
auto FirstCase = *SI->case_begin();		auto FirstCase = *SI->case_begin();
Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),		Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
Show All 29 Lines	if (auto *SI = dyn_cast<SwitchInst>(T)) {
return false;		return false;
}		}

if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {		if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {
// indirectbr blockaddress(@F, @BB) -> br label @BB		// indirectbr blockaddress(@F, @BB) -> br label @BB
if (auto *BA =		if (auto *BA =
dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {		dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
BasicBlock *TheOnlyDest = BA->getBasicBlock();		BasicBlock *TheOnlyDest = BA->getBasicBlock();
		std::vector <DominatorTree::UpdateType> Updates;
		if (DDT)
		Updates.reserve(IBI->getNumDestinations() - 1);

// Insert the new branch.		// Insert the new branch.
Builder.CreateBr(TheOnlyDest);		Builder.CreateBr(TheOnlyDest);

for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {		for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
if (IBI->getDestination(i) == TheOnlyDest)		if (IBI->getDestination(i) == TheOnlyDest) {
TheOnlyDest = nullptr;		TheOnlyDest = nullptr;
else		} else {
IBI->getDestination(i)->removePredecessor(IBI->getParent());		BasicBlock *ParentBB = IBI->getParent();
		BasicBlock *DestBB = IBI->getDestination(i);
		DestBB->removePredecessor(ParentBB);
		if (DDT)
		Updates.push_back({DominatorTree::Delete, ParentBB, DestBB});
		}
}		}
Value *Address = IBI->getAddress();		Value *Address = IBI->getAddress();
IBI->eraseFromParent();		IBI->eraseFromParent();
if (DeleteDeadConditions)		if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);		RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);

// If we didn't find our destination in the IBI successor list, then we		// If we didn't find our destination in the IBI successor list, then we
// have undefined behavior. Replace the unconditional branch with an		// have undefined behavior. Replace the unconditional branch with an
// 'unreachable' instruction.		// 'unreachable' instruction.
if (TheOnlyDest) {		if (TheOnlyDest) {
BB->getTerminator()->eraseFromParent();		BB->getTerminator()->eraseFromParent();
new UnreachableInst(BB->getContext(), BB);		new UnreachableInst(BB->getContext(), BB);
}		}

		if (DDT)
		DDT->applyUpdates(Updates);
return true;		return true;
}		}
}		}

return false;		return false;
}		}

//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
▲ Show 20 Lines • Show All 260 Lines • ▼ Show 20 Lines
///		///
/// Unlike the removePredecessor method, this attempts to simplify uses of PHI		/// Unlike the removePredecessor method, this attempts to simplify uses of PHI
/// nodes that collapse into identity values. For example, if we have:		/// nodes that collapse into identity values. For example, if we have:
/// x = phi(1, 0, 0, 0)		/// x = phi(1, 0, 0, 0)
/// y = and x, z		/// y = and x, z
///		///
/// .. and delete the predecessor corresponding to the '1', this will attempt to		/// .. and delete the predecessor corresponding to the '1', this will attempt to
/// recursively fold the and to 0.		/// recursively fold the and to 0.
void llvm::RemovePredecessorAndSimplify(BasicBlock BB, BasicBlock Pred) {		void llvm::RemovePredecessorAndSimplify(BasicBlock BB, BasicBlock Pred,
		DeferredDominance *DDT) {
// This only adjusts blocks with PHI nodes.		// This only adjusts blocks with PHI nodes.
if (!isa<PHINode>(BB->begin()))		if (!isa<PHINode>(BB->begin()))
return;		return;

// Remove the entries for Pred from the PHI nodes in BB, but do not simplify		// Remove the entries for Pred from the PHI nodes in BB, but do not simplify
// them down. This will leave us with single entry phi nodes and other phis		// them down. This will leave us with single entry phi nodes and other phis
// that can be removed.		// that can be removed.
BB->removePredecessor(Pred, true);		BB->removePredecessor(Pred, true);

WeakTrackingVH PhiIt = &BB->front();		WeakTrackingVH PhiIt = &BB->front();
while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {		while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));		PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
Value *OldPhiIt = PhiIt;		Value *OldPhiIt = PhiIt;

if (!recursivelySimplifyInstruction(PN))		if (!recursivelySimplifyInstruction(PN))
continue;		continue;

// If recursive simplification ended up deleting the next PHI node we would		// If recursive simplification ended up deleting the next PHI node we would
// iterate to, then our iterator is invalid, restart scanning from the top		// iterate to, then our iterator is invalid, restart scanning from the top
// of the block.		// of the block.
if (PhiIt != OldPhiIt) PhiIt = &BB->front();		if (PhiIt != OldPhiIt) PhiIt = &BB->front();
}		}
		if (DDT)
		DDT->deleteEdge(Pred, BB);
}		}

/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its		/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
/// predecessor is known to have one successor (DestBB!). Eliminate the edge		/// predecessor is known to have one successor (DestBB!). Eliminate the edge
/// between them, moving the instructions in the predecessor into DestBB and		/// between them, moving the instructions in the predecessor into DestBB and
/// deleting the predecessor block.		/// deleting the predecessor block.
void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock DestBB, DominatorTree DT) {		void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock DestBB, DominatorTree DT,
		DeferredDominance *DDT) {
		assert(!(DT && DDT) && "Cannot call with both DT and DDT.");

// If BB has single-entry PHI nodes, fold them.		// If BB has single-entry PHI nodes, fold them.
while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {		while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
Value *NewVal = PN->getIncomingValue(0);		Value *NewVal = PN->getIncomingValue(0);
// Replace self referencing PHI with undef, it must be dead.		// Replace self referencing PHI with undef, it must be dead.
if (NewVal == PN) NewVal = UndefValue::get(PN->getType());		if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
PN->replaceAllUsesWith(NewVal);		PN->replaceAllUsesWith(NewVal);
PN->eraseFromParent();		PN->eraseFromParent();
}		}

BasicBlock *PredBB = DestBB->getSinglePredecessor();		BasicBlock *PredBB = DestBB->getSinglePredecessor();
assert(PredBB && "Block doesn't have a single predecessor!");		assert(PredBB && "Block doesn't have a single predecessor!");

		bool ReplaceEntryBB = false;
		if (PredBB == &DestBB->getParent()->getEntryBlock())
		ReplaceEntryBB = true;

		// Deferred DT update: Collect all the edges that enter PredBB. These
		// dominator edges will be redirected to DestBB.
		std::vector <DominatorTree::UpdateType> Updates;
		if (DDT && !ReplaceEntryBB) {
		Updates.reserve(1 +
		(2 * std::distance(pred_begin(PredBB), pred_end(PredBB))));
		Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
		for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) {
		Updates.push_back({DominatorTree::Delete, *I, PredBB});
		// This predecessor of PredBB may already have DestBB as a successor.
		if (llvm::find(successors(I), DestBB) == succ_end(I))
		Updates.push_back({DominatorTree::Insert, *I, DestBB});
		}
		}

// Zap anything that took the address of DestBB. Not doing this will give the		// Zap anything that took the address of DestBB. Not doing this will give the
// address an invalid value.		// address an invalid value.
if (DestBB->hasAddressTaken()) {		if (DestBB->hasAddressTaken()) {
BlockAddress *BA = BlockAddress::get(DestBB);		BlockAddress *BA = BlockAddress::get(DestBB);
Constant *Replacement =		Constant *Replacement =
ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1);		ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1);
BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,		BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
BA->getType()));		BA->getType()));
BA->destroyConstant();		BA->destroyConstant();
}		}

// Anything that branched to PredBB now branches to DestBB.		// Anything that branched to PredBB now branches to DestBB.
PredBB->replaceAllUsesWith(DestBB);		PredBB->replaceAllUsesWith(DestBB);

// Splice all the instructions from PredBB to DestBB.		// Splice all the instructions from PredBB to DestBB.
PredBB->getTerminator()->eraseFromParent();		PredBB->getTerminator()->eraseFromParent();
DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());		DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());

// If the PredBB is the entry block of the function, move DestBB up to		// If the PredBB is the entry block of the function, move DestBB up to
// become the entry block after we erase PredBB.		// become the entry block after we erase PredBB.
if (PredBB == &DestBB->getParent()->getEntryBlock())		if (ReplaceEntryBB)
DestBB->moveAfter(PredBB);		DestBB->moveAfter(PredBB);

if (DT) {		if (DT) {
// For some irreducible CFG we end up having forward-unreachable blocks		// For some irreducible CFG we end up having forward-unreachable blocks
// so check if getNode returns a valid node before updating the domtree.		// so check if getNode returns a valid node before updating the domtree.
if (DomTreeNode *DTN = DT->getNode(PredBB)) {		if (DomTreeNode *DTN = DT->getNode(PredBB)) {
BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();		BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();
DT->changeImmediateDominator(DestBB, PredBBIDom);		DT->changeImmediateDominator(DestBB, PredBBIDom);
DT->eraseNode(PredBB);		DT->eraseNode(PredBB);
}		}
}		}
// Nuke BB.
PredBB->eraseFromParent();		if (DDT) {
		DDT->deleteBB(PredBB); // Deferred deletion of BB.
		if (ReplaceEntryBB)
		// The entry block was removed and there is no external interface for the
		// dominator tree to be notified of this change. In this corner-case we
		// recalculate the entire tree.

This is an archive of the discontinued LLVM Phabricator instance.

[JumpThreading] Preservation of DT and LVI across the passClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 129694

llvm/trunk/include/llvm/IR/Dominators.h

llvm/trunk/include/llvm/Transforms/Scalar/JumpThreading.h

llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h

llvm/trunk/include/llvm/Transforms/Utils/Local.h

llvm/trunk/lib/IR/Dominators.cpp

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

llvm/trunk/lib/Transforms/Utils/Local.cpp

[JumpThreading] Preservation of DT and LVI across the pass
ClosedPublic