This is an archive of the discontinued LLVM Phabricator instance.

Differential D40146

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

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

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

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
brzycki updated this revision to Diff 125642.Dec 5 2017, 3:51 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).

brzycki updated this revision to Diff 125749.Dec 6 2017, 9:19 AM
brzycki retitled this revision from [JumpThreading] (WIP) Deferred preservation of DT and LVI across the pass. to [JumpThreading] Deferred preservation of DT and LVI across the pass..
brzycki edited the summary of this revision. (Show Details)

Comment and whitespace cleanup. NFC.

brzycki updated this revision to Diff 125778.Dec 6 2017, 11:49 AM

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

sebpop accepted this revision.Dec 6 2017, 7:54 PM

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

Thanks!

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

Please add braces around the else clause.

llvm/lib/Transforms/Utils/Local.cpp
1857–1859

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
kuhar edited edge metadata.Dec 7 2017, 9:59 AM

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
54

Can the DT ever be null within the class? If not, maybe it would make sense to keep a reference instead?

103

Maybe it'd make more sense to return a reference?

128

Shouldn't this be guarded by a macro? LLVM_DUMP_METHOD
Can dump() be marked as const?

llvm/lib/IR/Dominators.cpp
401

This doesn't seem to modify any internal state, const should work here.

402

I think this should be llvm::dbgs

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

I think we can reserve (2 * size(successors(SplitBB)) + 3 here to have a single allocation

brzycki updated this revision to Diff 125992.Dec 7 2017, 10:35 AM

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

brzycki updated this revision to Diff 126031.Dec 7 2017, 1:36 PM
brzycki marked 7 inline comments as done.

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

brzycki updated this revision to Diff 126034.Dec 7 2017, 1:46 PM
brzycki marked an inline comment as done.

Comment cleanup to better match the code. NFC.

kuhar accepted this revision.Dec 7 2017, 1:49 PM

LGTM

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

@dberlin Any objections to me committing this code?

llvm/include/llvm/IR/DeferredDominance.h
54

IT cannot be nullptr. I have changed it to a ref.

128

I wasn't aware of these wrapper macros for dump, thanks for pointing them out. Added.

llvm/lib/IR/Dominators.cpp
401

Agreed.

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

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

One remark: why new here instead of just putting it on the stack? If you need to pass the ownership around, who deallocates it?

brzycki updated this revision to Diff 126468.Dec 11 2017, 4:21 PM
brzycki marked an inline comment as done.

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

Nit: DeferredDominance DDT = DeferredDominance(*DT) can be just DeferredDominance DDT(*DT);

brzycki updated this revision to Diff 126562.Dec 12 2017, 9:20 AM
brzycki marked an inline comment as done.

Cleaned up DDT init nit.

brzycki updated this revision to Diff 126608.Dec 12 2017, 12:45 PM

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.
brzycki reopened this revision.Dec 14 2017, 2:27 PM

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

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
brzycki updated this revision to Diff 127027.Dec 14 2017, 2:28 PM

Refactored patch to prevent -fmodules circular dependency errors.

kuhar added a comment.Dec 14 2017, 2:32 PM

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.

brzycki added a comment.Dec 14 2017, 3:39 PM
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.

brzycki added a comment.EditedDec 14 2017, 3:42 PM

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.
brzycki added a comment.Dec 15 2017, 7:38 AM
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.

kuhar added a comment.Dec 15 2017, 8:29 AM
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
brzycki added a comment.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.

brzycki updated this revision to Diff 127381.Dec 18 2017, 9:27 AM

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

sebpop accepted this revision.Dec 18 2017, 9:54 AM

LGTM.
-fmodules can be fought in another patch.

kuhar accepted this revision.Dec 18 2017, 11:26 AM

LGTM

dmgreen mentioned this in D41302: [LoopSimplify] Preserve Post Dom Trees across Loop Simplify.Dec 19 2017, 10:27 AM
brzycki updated this revision to Diff 128529.Jan 3 2018, 9:07 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.

sebpop accepted this revision.Jan 3 2018, 1:06 PM

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.
rnk added a subscriber: rnk.Jan 4 2018, 3:22 PM

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)
rnk added a comment.Jan 4 2018, 3:56 PM

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

rnk added a comment.Jan 4 2018, 5:18 PM

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.

brzycki reopened this revision.Jan 5 2018, 8:47 AM

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
brzycki added a comment.Jan 5 2018, 8:49 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.

brzycki added a comment.Jan 5 2018, 9:29 AM
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.

brzycki updated this revision to Diff 128964.EditedJan 8 2018, 11:46 AM

Fxed assert() caused when compiling Chrome.

Comments are inline describing where the patch was applied.

brzycki added a comment.Jan 8 2018, 2:14 PM

@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

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.

971

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
269

The reduced testcase that crashed LLVM discovered when compiling Chrome.

kuhar added a comment.Jan 8 2018, 2:29 PM

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

Looks reasonable.

You can use llvm::find here, something like this if (llvm::find(successors(*I), DestBB) == succ_end(*I))

971

Just like above.

llvm/test/Transforms/JumpThreading/ddt-crash.ll
269

Wouldn't it be better to add it in a separate file?

brzycki marked 9 inline comments as done.EditedJan 9 2018, 2:16 PM
brzycki added a subscriber: kuba.

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
brzycki updated this revision to Diff 129330.Jan 10 2018, 1:27 PM

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
brzycki updated this revision to Diff 129526.Jan 11 2018, 2:26 PM

Fixed comments in unit test.

kuhar accepted this revision.Jan 11 2018, 5:49 PM

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()

brzycki marked 16 inline comments as done.Jan 12 2018, 12:15 PM

@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.

brzycki updated this revision to Diff 129681.Jan 12 2018, 12:16 PM
brzycki marked 3 inline comments as done.

Update nits in the unit test for clarity.

kuhar accepted this revision.Jan 12 2018, 12:22 PM

Looks good now, thanks for the changes!

llvm/unittests/IR/DeferredDominanceTest.cpp
212 ↗(On Diff #129681)

Nit: missing comma.

brzycki updated this revision to Diff 129688.Jan 12 2018, 12:46 PM

Fixed punctuation in unit test comment. NFC.

brzycki marked an inline comment as done.Jan 12 2018, 12:46 PM

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.
MatzeB added a subscriber: MatzeB.Jan 18 2018, 2:51 PM

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?

kuhar added a comment.Jan 18 2018, 3:06 PM
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.

MatzeB added a comment.Jan 18 2018, 3:09 PM
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)...

MatzeB added a comment.Jan 18 2018, 3:12 PM

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

kuhar added a comment.Jan 18 2018, 3:23 PM
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?

MatzeB added a comment.Jan 18 2018, 3:30 PM
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...

kuhar added a comment.EditedJan 18 2018, 3:34 PM
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...

MatzeB added a comment.Jan 18 2018, 5:53 PM

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
brzycki added a comment.Jan 19 2018, 8:32 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 ↗(On Diff #129694)

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 ↗(On Diff #129694)

Hi @fhahn , when I initially did the work to preserve DT across JumpThreading I tried to do two things:

  1. Minimize the changes to external calls.
  2. 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. :)

• dberlin added subscribers: brzycki, junbuml, kuhar, sebpop.Mar 19 2018, 11:55 AM

+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.

fhahn added a comment.Mar 19 2018, 1:33 PM
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 :)

alexcrichton added a subscriber: alexcrichton.Jul 6 2018, 6:37 PM

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

PathSize
llvm/
include/
llvm/
IR/
190 lines
Transforms/
Scalar/
6 lines
Utils/
3 lines
21 lines
lib/
IR/
52 lines
Transforms/
Scalar/
2 lines
176 lines
Utils/
16 lines
198 lines
test/
Analysis/
LazyValueAnalysis/
3 lines
Transforms/
JumpThreading/
265 lines
51 lines

Diff 125642

llvm/include/llvm/IR/DeferredDominance.h

  • This file was added.
//===- DeferredDominance.h - Deferred Dominator/Post-Dominators -*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the DeferredDominance class, which provides deferred
// updates to Dominators (and optionally Post-Dominators).
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_IR_DEFERREDDOMINANCE_H
#define LLVM_IR_DEFERREDDOMINANCE_H
#include "llvm/ADT/SmallSet.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
namespace llvm {
/// \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_) {}
kuharUnsubmitted
Done
ReplyInline Actions

Can the DT ever be null within the class? If not, maybe it would make sense to keep a reference instead?

kuhar: Can the DT ever be null within the class? If not, maybe it would make sense to keep a reference…
brzyckiAuthorUnsubmitted
Not Done
ReplyInline Actions

IT cannot be nullptr. I have changed it to a ref.

brzycki: IT cannot be nullptr. I have changed it to a ref.
/// \brief Queues multiple updates and discards duplicates.
void 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());
}
}
void insertEdge(BasicBlock *From, BasicBlock *To) {
applyUpdate(DominatorTree::Insert, From, To);
}
void deleteEdge(BasicBlock *From, BasicBlock *To) {
applyUpdate(DominatorTree::Delete, From, To);
}
/// \brief Delays the deletion of a basic block until a flush() event.
void 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 values need to be 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 pendingDeletedBB(BasicBlock *DelBB) {
if (DeletedBBs.empty())
return false;
return DeletedBBs.count(DelBB) != 0;
}
/// \brief Flushes all pending updates and block deletions. Returns a
/// DominatorTree pointer to be used by the caller for analysis.
DominatorTree *flush() {
// Updates to DT must happen before blocks are deleted below. Otherwise the
kuharUnsubmitted
Done
ReplyInline Actions

Maybe it'd make more sense to return a reference?

kuhar: Maybe it'd make more sense to return a reference?
// 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 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.
void dump();
kuharUnsubmitted
Done
ReplyInline Actions

Shouldn't this be guarded by a macro? LLVM_DUMP_METHOD
Can dump() be marked as const?

kuhar: Shouldn't this be guarded by a macro? `LLVM_DUMP_METHOD` Can dump() be marked as const?
brzyckiAuthorUnsubmitted
Not Done
ReplyInline Actions

I wasn't aware of these wrapper macros for dump, thanks for pointing them out. Added.

brzycki: I wasn't aware of these wrapper macros for dump, thanks for pointing them out. Added.
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) {
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 both exist which 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 flushDelBB() {
if (DeletedBBs.empty())
return false;
for (auto *BB : DeletedBBs)
BB->eraseFromParent();
DeletedBBs.clear();
return true;
}
};
} // end namespace llvm
#endif // LLVM_IR_DEFERREDDOMINANCE_H

llvm/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/include/llvm/Transforms/Utils/BasicBlockUtils.h

Show All 19 Lines
#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/ArrayRef.h"
#include "llvm/IR/BasicBlock.h" #include "llvm/IR/BasicBlock.h"
#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 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 261 Lines • Show Last 20 Lines

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

Show All 18 Lines
#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/TinyPtrVector.h" #include "llvm/ADT/TinyPtrVector.h"
#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/IR/CallSite.h" #include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h" #include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h" #include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h" #include "llvm/IR/DataLayout.h"
#include "llvm/IR/DeferredDominance.h"
#include "llvm/IR/Dominators.h" #include "llvm/IR/Dominators.h"
#include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/Operator.h" #include "llvm/IR/Operator.h"
#include "llvm/IR/Type.h" #include "llvm/IR/Type.h"
#include "llvm/IR/User.h" #include "llvm/IR/User.h"
#include "llvm/IR/Value.h" #include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h" #include "llvm/Support/Casting.h"
#include <cstdint> #include <cstdint>
▲ Show 20 Lines • Show All 69 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 181 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/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/DeferredDominance.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 354 Lines • ▼ Show 20 Linesvoid 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.
//
//===----------------------------------------------------------------------===//
void DeferredDominance::dump() {
kuharUnsubmitted
Done
ReplyInline Actions

This doesn't seem to modify any internal state, const should work here.

kuhar: This doesn't seem to modify any internal state, const should work here.
brzyckiAuthorUnsubmitted
Done
ReplyInline Actions

Agreed.

brzycki: Agreed.
raw_ostream &OS = llvm::outs();
kuharUnsubmitted
Done
ReplyInline Actions

I think this should be llvm::dbgs

kuhar: I think this should be 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";
}
}

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

Show First 20 Lines • Show All 71 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 555 Lines • Show Last 20 Lines

llvm/lib/Transforms/Scalar/JumpThreading.cpp

Show All 31 Lines
#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h" #include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h" #include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h" #include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h" #include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h" #include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h" #include "llvm/IR/DataLayout.h"
#include "llvm/IR/DeferredDominance.h"
#include "llvm/IR/Dominators.h" #include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h" #include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h" #include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h" #include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h" #include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h" #include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h" #include "llvm/IR/LLVMContext.h"
▲ Show 20 Lines • Show All 78 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 Linesstatic 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 = new DeferredDominance(DT);
kuharUnsubmitted
Done
ReplyInline Actions

One remark: why new here instead of just putting it on the stack? If you need to pass the ownership around, who deallocates it?

kuhar: One remark: why new here instead of just putting it on the stack? If you need to pass the…
brzyckiAuthorUnsubmitted
Done
ReplyInline Actions

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.

brzycki: Ah, I forgot I had that. This is stale code from an older attempt at working the class into…
kuharUnsubmitted
Done
ReplyInline Actions

Nit: DeferredDominance DDT = DeferredDominance(*DT) can be just DeferredDominance DDT(*DT);

kuhar: Nit: `DeferredDominance DDT = DeferredDominance(*DT)` can be just `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.getEntryCount().hasValue(); bool HasProfileData = F.getEntryCount().hasValue();
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 = new DeferredDominance(&DT);
std::unique_ptr<BlockFrequencyInfo> BFI; std::unique_ptr<BlockFrequencyInfo> BFI;
std::unique_ptr<BranchProbabilityInfo> BPI; std::unique_ptr<BranchProbabilityInfo> BPI;
bool HasProfileData = F.getEntryCount().hasValue(); bool HasProfileData = F.getEntryCount().hasValue();
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 = 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 Linesstatic 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();
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 376 Lines • ▼ Show 20 Linesbool 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;
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 318 Lines • ▼ Show 20 Lines for (Use &U : I.uses()) {
if (PHINode *UserPN = dyn_cast<PHINode>(User)) { if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
if (UserPN->getIncomingBlock(U) == BB) if (UserPN->getIncomingBlock(U) == BB)
continue; continue;
} else if (User->getParent() == BB) } else if (User->getParent() == BB)
continue; continue;
UsesToRename.push_back(&U); UsesToRename.push_back(&U);
} }
// If there are no uses outside the block, we're done with this instruction. // If there are no uses outside the block, we're done with this instruction.
if (UsesToRename.empty()) if (UsesToRename.empty())
continue; continue;
DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n"); DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
// We found a use of I outside of BB. Rename all uses of I that are outside // We found a use of I outside of BB. Rename all uses of I that are outside
// its block to be uses of the appropriate PHI node etc. See ValuesInBlocks // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
Show All 12 Linesbool 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) {
std::vector<DominatorTree::UpdateType> Updates;
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)));
BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix); // 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
sebpopUnsubmitted
Done
ReplyInline Actions

Please add braces around the else clause.

sebpop: Please add braces around the else clause.
NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix));
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 Linesbool 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();
// From the point of view of the DDT, both NewBB and SplitBB are newly
// created blocks. We first need to handle the edges caused by inserting an
kuharUnsubmitted
Done
ReplyInline Actions

I think we can reserve (2 * size(successors(SplitBB)) + 3 here to have a single allocation

kuhar: I think we can reserve (2 * size(successors(SplitBB)) + 3 here to have a single allocation
brzyckiAuthorUnsubmitted
Done
ReplyInline Actions

I did this and also added others where the size was trivial to calculate.

brzycki: I did this and also added others where the size was trivial to calculate.
// if..then block.
std::vector <DominatorTree::UpdateType> Updates;
Updates.push_back({DominatorTree::Insert, BB, SplitBB});
Updates.push_back({DominatorTree::Insert, BB, NewBB});
Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
// The successors of BB are now the successors of SplitBB. We need to remove
// them as successors of BB and attach them as successors of SplitBB.
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(
{// 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/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()) 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 724 Lines • Show Last 20 Lines

llvm/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 (BranchInst *BI = dyn_cast<BranchInst>(T)) { if (BranchInst *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);
Show All 10 Lines if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
// 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 (SwitchInst *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;
// 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 (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
return false; return false;
} }
if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
// indirectbr blockaddress(@F, @BB) -> br label @BB // indirectbr blockaddress(@F, @BB) -> br label @BB
if (BlockAddress *BA = if (BlockAddress *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;
// 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.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});
Updates.push_back({DominatorTree::Insert, *I, DestBB});
}
}
brzyckiAuthorUnsubmitted
Done
ReplyInline Actions

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.

brzycki: I did not see this fail in the specific case of the Chrome assert(). However, it is entirely…
kuharUnsubmitted
Done
ReplyInline Actions

Looks reasonable.

You can use llvm::find here, something like this if (llvm::find(successors(*I), DestBB) == succ_end(*I))

kuhar: Looks reasonable. You can use llvm::find here, something like this `if (llvm::find(successors…
// 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.
DDT->recalculate(*(DestBB->getParent()));
else
DDT->applyUpdates(Updates);
} else {
PredBB->eraseFromParent(); // Nuke BB.
}
} }
/// CanMergeValues - Return true if we can choose one of these values to use /// CanMergeValues - Return true if we can choose one of these values to use
/// in place of the other. Note that we will always choose the non-undef /// in place of the other. Note that we will always choose the non-undef
/// value to keep. /// value to keep.
static bool CanMergeValues(Value *First, Value *Second) { static bool CanMergeValues(Value *First, Value *Second) {
return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
} }
▲ Show 20 Lines • Show All 190 Lines • ▼ Show 20 Linesstatic void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
replaceUndefValuesInPhi(PN, IncomingValues); replaceUndefValuesInPhi(PN, IncomingValues);
} }
/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
/// unconditional branch, and contains no instructions other than PHI nodes, /// unconditional branch, and contains no instructions other than PHI nodes,
/// potential side-effect free intrinsics and the branch. If possible, /// potential side-effect free intrinsics and the branch. If possible,
/// eliminate BB by rewriting all the predecessors to branch to the successor /// eliminate BB by rewriting all the predecessors to branch to the successor
/// block and return true. If we can't transform, return false. /// block and return true. If we can't transform, return false.
bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
DeferredDominance *DDT) {
assert(BB != &BB->getParent()->getEntryBlock() && assert(BB != &BB->getParent()->getEntryBlock() &&
"TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
// We can't eliminate infinite loops. // We can't eliminate infinite loops.
BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
if (BB == Succ) return false; if (BB == Succ) return false;
// Check to see if merging these blocks would cause conflicts for any of the // Check to see if merging these blocks would cause conflicts for any of the
Show All 24 Lines while (isa<PHINode>(*BBI)) {
} }
} }
++BBI; ++BBI;
} }
} }
DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
// Collect all the edges that enter BB, discarding edges to itself and
// duplicates. These dominator edges will be redirected to Succ.
std::vector<DominatorTree::UpdateType> Updates;
if (DDT) {
Updates.push_back({DominatorTree::Delete, BB, Succ});
for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
Updates.push_back({DominatorTree::Delete, *I, BB});
Updates.push_back({DominatorTree::Insert, *I, Succ});
}
brzyckiAuthorUnsubmitted
Done
ReplyInline Actions

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.

brzycki: This check is the fix for the assert() discovered by @rnk . The shape of the IR had an…
kuharUnsubmitted
Done
ReplyInline Actions

Just like above.

kuhar: Just like above.
}
if (isa<PHINode>(Succ->begin())) { if (isa<PHINode>(Succ->begin())) {
// If there is more than one pred of succ, and there are PHI nodes in // If there is more than one pred of succ, and there are PHI nodes in
// the successor, then we need to add incoming edges for the PHI nodes // the successor, then we need to add incoming edges for the PHI nodes
// //
const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
// Loop over all of the PHI nodes in the successor of BB. // Loop over all of the PHI nodes in the successor of BB.
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
Show All 28 Lines if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock *Pred = *PI; BasicBlock *Pred = *PI;
Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD); Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
} }
// Everything that jumped to BB now goes to Succ. // Everything that jumped to BB now goes to Succ.
BB->replaceAllUsesWith(Succ); BB->replaceAllUsesWith(Succ);
if (!Succ->hasName()) Succ->takeName(BB); if (!Succ->hasName()) Succ->takeName(BB);
if (DDT) {
DDT->deleteBB(BB); // Deferred deletion of the old basic block.
DDT->applyUpdates(Updates);
} else {
BB->eraseFromParent(); // Delete the old basic block. BB->eraseFromParent(); // Delete the old basic block.
}
return true; return true;
} }
/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
/// nodes in this block. This doesn't try to be clever about PHI nodes /// nodes in this block. This doesn't try to be clever about PHI nodes
/// which differ only in the order of the incoming values, but instcombine /// which differ only in the order of the incoming values, but instcombine
/// orders them so it usually won't matter. /// orders them so it usually won't matter.
bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
▲ Show 20 Lines • Show All 483 Lines • ▼ Show 20 Lines while (EndInst != &BB->front()) {
if (!isa<DbgInfoIntrinsic>(Inst)) if (!isa<DbgInfoIntrinsic>(Inst))
++NumDeadInst; ++NumDeadInst;
Inst->eraseFromParent(); Inst->eraseFromParent();
} }
return NumDeadInst; return NumDeadInst;
} }
unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
bool PreserveLCSSA) { bool PreserveLCSSA, DeferredDominance *DDT) {
BasicBlock *BB = I->getParent(); BasicBlock *BB = I->getParent();
std::vector <DominatorTree::UpdateType> Updates;
// Loop over all of the successors, removing BB's entry from any PHI // Loop over all of the successors, removing BB's entry from any PHI
// nodes. // nodes.
for (BasicBlock *Successor : successors(BB)) for (BasicBlock *Successor : successors(BB)) {
Successor->removePredecessor(BB, PreserveLCSSA); Successor->removePredecessor(BB, PreserveLCSSA);
if (DDT)
Updates.push_back({DominatorTree::Delete, BB, Successor});
}
// Insert a call to llvm.trap right before this. This turns the undefined // Insert a call to llvm.trap right before this. This turns the undefined
// behavior into a hard fail instead of falling through into random code. // behavior into a hard fail instead of falling through into random code.
if (UseLLVMTrap) { if (UseLLVMTrap) {
Function *TrapFn = Function *TrapFn =
Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
CallInst *CallTrap = CallInst::Create(TrapFn, "", I); CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
CallTrap->setDebugLoc(I->getDebugLoc()); CallTrap->setDebugLoc(I->getDebugLoc());
} }
new UnreachableInst(I->getContext(), I); new UnreachableInst(I->getContext(), I);
// All instructions after this are dead. // All instructions after this are dead.
unsigned NumInstrsRemoved = 0; unsigned NumInstrsRemoved = 0;
BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end(); BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
while (BBI != BBE) { while (BBI != BBE) {
if (!BBI->use_empty()) if (!BBI->use_empty())
BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
BB->getInstList().erase(BBI++); BB->getInstList().erase(BBI++);
++NumInstrsRemoved; ++NumInstrsRemoved;
} }
if (DDT)
DDT->applyUpdates(Updates);
return NumInstrsRemoved; return NumInstrsRemoved;
} }
/// changeToCall - Convert the specified invoke into a normal call. /// changeToCall - Convert the specified invoke into a normal call.
static void changeToCall(InvokeInst *II) { static void changeToCall(InvokeInst *II, DeferredDominance *DDT = nullptr) {
SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end()); SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
SmallVector<OperandBundleDef, 1> OpBundles; SmallVector<OperandBundleDef, 1> OpBundles;
II->getOperandBundlesAsDefs(OpBundles); II->getOperandBundlesAsDefs(OpBundles);
CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles, CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
"", II); "", II);
NewCall->takeName(II); NewCall->takeName(II);
NewCall->setCallingConv(II->getCallingConv()); NewCall->setCallingConv(II->getCallingConv());
NewCall->setAttributes(II->getAttributes()); NewCall->setAttributes(II->getAttributes());
NewCall->setDebugLoc(II->getDebugLoc()); NewCall->setDebugLoc(II->getDebugLoc());
II->replaceAllUsesWith(NewCall); II->replaceAllUsesWith(NewCall);
// Follow the call by a branch to the normal destination. // Follow the call by a branch to the normal destination.
BranchInst::Create(II->getNormalDest(), II); BasicBlock *NormalDestBB = II->getNormalDest();
BranchInst::Create(NormalDestBB, II);
// Update PHI nodes in the unwind destination // Update PHI nodes in the unwind destination
II->getUnwindDest()->removePredecessor(II->getParent()); BasicBlock *BB = II->getParent();
BasicBlock *UnwindDestBB = II->getUnwindDest();
UnwindDestBB->removePredecessor(BB);
II->eraseFromParent(); II->eraseFromParent();
if (DDT)
DDT->deleteEdge(BB, UnwindDestBB);
} }
BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
BasicBlock *UnwindEdge) { BasicBlock *UnwindEdge) {
BasicBlock *BB = CI->getParent(); BasicBlock *BB = CI->getParent();
// Convert this function call into an invoke instruction. First, split the // Convert this function call into an invoke instruction. First, split the
// basic block. // basic block.
Show All 24 LinesBasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
CI->replaceAllUsesWith(II); CI->replaceAllUsesWith(II);
// Delete the original call // Delete the original call
Split->getInstList().pop_front(); Split->getInstList().pop_front();
return Split; return Split;
} }
static bool markAliveBlocks(Function &F, static bool markAliveBlocks(Function &F,
SmallPtrSetImpl<BasicBlock*> &Reachable) { SmallPtrSetImpl<BasicBlock *> &Reachable,
DeferredDominance *DDT = nullptr) {
SmallVector<BasicBlock*, 128> Worklist; SmallVector<BasicBlock *, 128> Worklist;
BasicBlock *BB = &F.front(); BasicBlock *BB = &F.front();
Worklist.push_back(BB); Worklist.push_back(BB);
Reachable.insert(BB); Reachable.insert(BB);
bool Changed = false; bool Changed = false;
do { do {
BB = Worklist.pop_back_val(); BB = Worklist.pop_back_val();
// Do a quick scan of the basic block, turning any obviously unreachable // Do a quick scan of the basic block, turning any obviously unreachable
// instructions into LLVM unreachable insts. The instruction combining pass // instructions into LLVM unreachable insts. The instruction combining pass
// canonicalizes unreachable insts into stores to null or undef. // canonicalizes unreachable insts into stores to null or undef.
for (Instruction &I : *BB) { for (Instruction &I : *BB) {
// Assumptions that are known to be false are equivalent to unreachable. // Assumptions that are known to be false are equivalent to unreachable.
// Also, if the condition is undefined, then we make the choice most // Also, if the condition is undefined, then we make the choice most
// beneficial to the optimizer, and choose that to also be unreachable. // beneficial to the optimizer, and choose that to also be unreachable.
if (auto *II = dyn_cast<IntrinsicInst>(&I)) { if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
if (II->getIntrinsicID() == Intrinsic::assume) { if (II->getIntrinsicID() == Intrinsic::assume) {
if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) { if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
// Don't insert a call to llvm.trap right before the unreachable. // Don't insert a call to llvm.trap right before the unreachable.
changeToUnreachable(II, false); changeToUnreachable(II, false, false, DDT);
Changed = true; Changed = true;
break; break;
} }
} }
if (II->getIntrinsicID() == Intrinsic::experimental_guard) { if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
// A call to the guard intrinsic bails out of the current compilation // A call to the guard intrinsic bails out of the current compilation
// unit if the predicate passed to it is false. If the predicate is a // unit if the predicate passed to it is false. If the predicate is a
// constant false, then we know the guard will bail out of the current // constant false, then we know the guard will bail out of the current
// compile unconditionally, so all code following it is dead. // compile unconditionally, so all code following it is dead.
// //
// Note: unlike in llvm.assume, it is not "obviously profitable" for // Note: unlike in llvm.assume, it is not "obviously profitable" for
// guards to treat `undef` as `false` since a guard on `undef` can // guards to treat `undef` as `false` since a guard on `undef` can
// still be useful for widening. // still be useful for widening.
if (match(II->getArgOperand(0), m_Zero())) if (match(II->getArgOperand(0), m_Zero()))
if (!isa<UnreachableInst>(II->getNextNode())) { if (!isa<UnreachableInst>(II->getNextNode())) {
changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false); changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false,
false, DDT);
Changed = true; Changed = true;
break; break;
} }
} }
} }
if (auto *CI = dyn_cast<CallInst>(&I)) { if (auto *CI = dyn_cast<CallInst>(&I)) {
Value *Callee = CI->getCalledValue(); Value *Callee = CI->getCalledValue();
if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
changeToUnreachable(CI, /*UseLLVMTrap=*/false); changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DDT);
Changed = true; Changed = true;
break; break;
} }
if (CI->doesNotReturn()) { if (CI->doesNotReturn()) {
// If we found a call to a no-return function, insert an unreachable // If we found a call to a no-return function, insert an unreachable
// instruction after it. Make sure there isn't *already* one there // instruction after it. Make sure there isn't *already* one there
// though. // though.
if (!isa<UnreachableInst>(CI->getNextNode())) { if (!isa<UnreachableInst>(CI->getNextNode())) {
// Don't insert a call to llvm.trap right before the unreachable. // Don't insert a call to llvm.trap right before the unreachable.
changeToUnreachable(CI->getNextNode(), false); changeToUnreachable(CI->getNextNode(), false, false, DDT);
Changed = true; Changed = true;
} }
break; break;
} }
} }
// Store to undef and store to null are undefined and used to signal that // Store to undef and store to null are undefined and used to signal that
// they should be changed to unreachable by passes that can't modify the // they should be changed to unreachable by passes that can't modify the
// CFG. // CFG.
if (auto *SI = dyn_cast<StoreInst>(&I)) { if (auto *SI = dyn_cast<StoreInst>(&I)) {
// Don't touch volatile stores. // Don't touch volatile stores.
if (SI->isVolatile()) continue; if (SI->isVolatile()) continue;
Value *Ptr = SI->getOperand(1); Value *Ptr = SI->getOperand(1);
if (isa<UndefValue>(Ptr) || if (isa<UndefValue>(Ptr) ||
(isa<ConstantPointerNull>(Ptr) && (isa<ConstantPointerNull>(Ptr) &&
SI->getPointerAddressSpace() == 0)) { SI->getPointerAddressSpace() == 0)) {
changeToUnreachable(SI, true); changeToUnreachable(SI, true, false, DDT);
Changed = true; Changed = true;
break; break;
} }
} }
} }
TerminatorInst *Terminator = BB->getTerminator(); TerminatorInst *Terminator = BB->getTerminator();
if (auto *II = dyn_cast<InvokeInst>(Terminator)) { if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
// Turn invokes that call 'nounwind' functions into ordinary calls. // Turn invokes that call 'nounwind' functions into ordinary calls.
Value *Callee = II->getCalledValue(); Value *Callee = II->getCalledValue();
if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
changeToUnreachable(II, true); changeToUnreachable(II, true, false, DDT);
Changed = true; Changed = true;
} else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
if (II->use_empty() && II->onlyReadsMemory()) { if (II->use_empty() && II->onlyReadsMemory()) {
// jump to the normal destination branch. // jump to the normal destination branch.
BranchInst::Create(II->getNormalDest(), II); BasicBlock *NormalDestBB = II->getNormalDest();
II->getUnwindDest()->removePredecessor(II->getParent()); BasicBlock *UnwindDestBB = II->getUnwindDest();
BranchInst::Create(NormalDestBB, II);
UnwindDestBB->removePredecessor(II->getParent());
II->eraseFromParent(); II->eraseFromParent();
if (DDT)
DDT->deleteEdge(BB, UnwindDestBB);
} else } else
changeToCall(II); changeToCall(II, DDT);
Changed = true; Changed = true;
} }
} else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) { } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
// Remove catchpads which cannot be reached. // Remove catchpads which cannot be reached.
struct CatchPadDenseMapInfo { struct CatchPadDenseMapInfo {
static CatchPadInst *getEmptyKey() { static CatchPadInst *getEmptyKey() {
return DenseMapInfo<CatchPadInst *>::getEmptyKey(); return DenseMapInfo<CatchPadInst *>::getEmptyKey();
} }
Show All 29 Lines if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
CatchSwitch->removeHandler(I); CatchSwitch->removeHandler(I);
--I; --I;
--E; --E;
Changed = true; Changed = true;
} }
} }
} }
Changed |= ConstantFoldTerminator(BB, true); Changed |= ConstantFoldTerminator(BB, true, nullptr, DDT);
for (BasicBlock *Successor : successors(BB)) for (BasicBlock *Successor : successors(BB))
if (Reachable.insert(Successor).second) if (Reachable.insert(Successor).second)
Worklist.push_back(Successor); Worklist.push_back(Successor);
} while (!Worklist.empty()); } while (!Worklist.empty());
return Changed; return Changed;
} }
void llvm::removeUnwindEdge(BasicBlock *BB) { void llvm::removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT) {
TerminatorInst *TI = BB->getTerminator(); TerminatorInst *TI = BB->getTerminator();
if (auto *II = dyn_cast<InvokeInst>(TI)) { if (auto *II = dyn_cast<InvokeInst>(TI)) {
changeToCall(II); changeToCall(II, DDT);
return; return;
} }
TerminatorInst *NewTI; TerminatorInst *NewTI;
BasicBlock *UnwindDest; BasicBlock *UnwindDest;
if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) { if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
UnwindDest = CRI->getUnwindDest(); UnwindDest = CRI->getUnwindDest();
} else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) { } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
auto *NewCatchSwitch = CatchSwitchInst::Create( auto *NewCatchSwitch = CatchSwitchInst::Create(
CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(), CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
CatchSwitch->getName(), CatchSwitch); CatchSwitch->getName(), CatchSwitch);
for (BasicBlock *PadBB : CatchSwitch->handlers()) for (BasicBlock *PadBB : CatchSwitch->handlers())
NewCatchSwitch->addHandler(PadBB); NewCatchSwitch->addHandler(PadBB);
NewTI = NewCatchSwitch; NewTI = NewCatchSwitch;
UnwindDest = CatchSwitch->getUnwindDest(); UnwindDest = CatchSwitch->getUnwindDest();
} else { } else {
llvm_unreachable("Could not find unwind successor"); llvm_unreachable("Could not find unwind successor");
} }
NewTI->takeName(TI); NewTI->takeName(TI);
NewTI->setDebugLoc(TI->getDebugLoc()); NewTI->setDebugLoc(TI->getDebugLoc());
UnwindDest->removePredecessor(BB); UnwindDest->removePredecessor(BB);
TI->replaceAllUsesWith(NewTI); TI->replaceAllUsesWith(NewTI);
TI->eraseFromParent(); TI->eraseFromParent();
if (DDT)
DDT->deleteEdge(BB, UnwindDest);
} }
/// removeUnreachableBlocks - Remove blocks that are not reachable, even /// removeUnreachableBlocks - Remove blocks that are not reachable, even
/// if they are in a dead cycle. Return true if a change was made, false /// if they are in a dead cycle. Return true if a change was made, false
/// otherwise. If `LVI` is passed, this function preserves LazyValueInfo /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
/// after modifying the CFG. /// after modifying the CFG.
bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) { bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
DeferredDominance *DDT) {
SmallPtrSet<BasicBlock*, 16> Reachable; SmallPtrSet<BasicBlock*, 16> Reachable;
bool Changed = markAliveBlocks(F, Reachable); bool Changed = markAliveBlocks(F, Reachable, DDT);
// If there are unreachable blocks in the CFG... // If there are unreachable blocks in the CFG...
if (Reachable.size() == F.size()) if (Reachable.size() == F.size())
return Changed; return Changed;
assert(Reachable.size() < F.size()); assert(Reachable.size() < F.size());
NumRemoved += F.size()-Reachable.size(); NumRemoved += F.size()-Reachable.size();
// Loop over all of the basic blocks that are not reachable, dropping all of // Loop over all of the basic blocks that are not reachable, dropping all of
// their internal references... // their internal references. Update DDT and LVI if available.
for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { std::vector <DominatorTree::UpdateType> Updates;
if (Reachable.count(&*BB)) for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
auto *BB = &*I;
if (Reachable.count(BB))
continue; continue;
for (BasicBlock *Successor : successors(BB)) {
for (BasicBlock *Successor : successors(&*BB))
if (Reachable.count(Successor)) if (Reachable.count(Successor))
Successor->removePredecessor(&*BB); Successor->removePredecessor(BB);
if (DDT)
Updates.push_back({DominatorTree::Delete, BB, Successor});
}
if (LVI) if (LVI)
LVI->eraseBlock(&*BB); LVI->eraseBlock(BB);
BB->dropAllReferences(); BB->dropAllReferences();
} }
for (Function::iterator I = ++F.begin(); I != F.end();) for (Function::iterator I = ++F.begin(); I != F.end(); ++I) {
if (!Reachable.count(&*I)) auto *BB = &*I;
if (Reachable.count(BB))
continue;
if (DDT) {
DDT->deleteBB(BB); // deferred deletion of BB.
} else {
I = F.getBasicBlockList().erase(I); I = F.getBasicBlockList().erase(I);
else --I; // We deleted a block and need to "freeze" incrementing.
++I; }
}
sebpopUnsubmitted
Done
ReplyInline Actions

Please move the ++I back in the body of the for loop and remove --I.

sebpop: Please move the ++I back in the body of the for loop and remove --I.
if (DDT)
DDT->applyUpdates(Updates);
return true; return true;
} }
void llvm::combineMetadata(Instruction *K, const Instruction *J, void llvm::combineMetadata(Instruction *K, const Instruction *J,
ArrayRef<unsigned> KnownIDs) { ArrayRef<unsigned> KnownIDs) {
SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
K->dropUnknownNonDebugMetadata(KnownIDs); K->dropUnknownNonDebugMetadata(KnownIDs);
K->getAllMetadataOtherThanDebugLoc(Metadata); K->getAllMetadataOtherThanDebugLoc(Metadata);
▲ Show 20 Lines • Show All 514 Lines • Show Last 20 Lines

llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll

Show All 13 Lines
; CHECK-NEXT: ; LatticeVal for: 'i32 %a' is: overdefined ; CHECK-NEXT: ; LatticeVal for: 'i32 %a' is: overdefined
; CHECK-NEXT: ; LatticeVal for: 'i32 %length' is: overdefined ; CHECK-NEXT: ; LatticeVal for: 'i32 %length' is: overdefined
br label %loop br label %loop
; CHECK-LABEL: backedge: ; CHECK-LABEL: backedge:
; CHECK-NEXT: ; LatticeVal for: 'i32 %a' is: overdefined ; CHECK-NEXT: ; LatticeVal for: 'i32 %a' is: overdefined
; CHECK-NEXT: ; LatticeVal for: 'i32 %length' is: overdefined ; CHECK-NEXT: ; LatticeVal for: 'i32 %length' is: overdefined
; CHECK-NEXT: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400> ; CHECK-NEXT: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400>
; CHECK-NEXT: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 400>
; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] ; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
; CHECK-NEXT: ; LatticeVal for: ' %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401> ; CHECK-NEXT: ; LatticeVal for: ' %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401>
; CHECK-NEXT: ; LatticeVal for: ' %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401>
; CHECK-NEXT: %iv.next = add nsw i32 %iv, 1 ; CHECK-NEXT: %iv.next = add nsw i32 %iv, 1
; CHECK-NEXT: ; LatticeVal for: ' %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined ; CHECK-NEXT: ; LatticeVal for: ' %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
; CHECK-NEXT: ; LatticeVal for: ' %cont = icmp slt i32 %iv.next, 400' in BB: '%exit' is: constantrange<0, -1>
; CHECK-NEXT: %cont = icmp slt i32 %iv.next, 400 ; CHECK-NEXT: %cont = icmp slt i32 %iv.next, 400
; CHECK-NOT: loop ; CHECK-NOT: loop
loop: loop:
%iv = phi i32 [0, %entry], [%iv.next, %backedge] %iv = phi i32 [0, %entry], [%iv.next, %backedge]
%cnd = icmp sge i32 %iv, 0 %cnd = icmp sge i32 %iv, 0
br i1 %cnd, label %backedge, label %exit br i1 %cnd, label %backedge, label %exit
backedge: backedge:
▲ Show 20 Lines • Show All 153 Lines • Show Last 20 Lines

llvm/test/Transforms/JumpThreading/ddt-crash.ll

  • This file was added.
; RUN: opt < %s -jump-threading -disable-output
%struct.ham = type { i8, i8, i16, i32 }
%struct.zot = type { i32 (...)** }
%struct.quux.0 = type { %struct.wombat }
%struct.wombat = type { %struct.zot }
@global = external global %struct.ham*, align 8
@global.1 = external constant i8*
declare i32 @wombat.2()
define void @blam() {
bb:
%tmp = load i32, i32* undef
%tmp1 = icmp eq i32 %tmp, 0
br i1 %tmp1, label %bb11, label %bb2
bb2:
%tmp3 = tail call i32 @wombat.2()
switch i32 %tmp3, label %bb4 [
i32 0, label %bb5
i32 1, label %bb7
i32 2, label %bb7
i32 3, label %bb11
]
bb4:
br label %bb7
bb5:
%tmp6 = tail call i32 @wombat.2()
br label %bb7
bb7:
%tmp8 = phi i32 [ 0, %bb5 ], [ 1, %bb4 ], [ 2, %bb2 ], [ 2, %bb2 ]
%tmp9 = icmp eq i32 %tmp8, 0
br i1 %tmp9, label %bb11, label %bb10
bb10:
ret void
bb11:
ret void
}
define void @spam(%struct.ham* %arg) {
bb:
%tmp = load i8, i8* undef, align 8
switch i8 %tmp, label %bb11 [
i8 1, label %bb11
i8 2, label %bb11
i8 3, label %bb1
i8 4, label %bb1
]
bb1:
br label %bb2
bb2:
%tmp3 = phi i32 [ 0, %bb1 ], [ %tmp3, %bb8 ]
br label %bb4
bb4:
%tmp5 = load i8, i8* undef, align 8
switch i8 %tmp5, label %bb11 [
i8 0, label %bb11
i8 1, label %bb10
i8 2, label %bb10
i8 3, label %bb6
i8 4, label %bb6
]
bb6:
br label %bb7
bb7:
br i1 undef, label %bb8, label %bb10
bb8:
%tmp9 = icmp eq %struct.ham* undef, %arg
br i1 %tmp9, label %bb10, label %bb2
bb10:
switch i32 %tmp3, label %bb4 [
i32 0, label %bb14
i32 1, label %bb11
i32 2, label %bb12
]
bb11:
unreachable
bb12:
%tmp13 = load %struct.ham*, %struct.ham** undef
br label %bb14
bb14:
%tmp15 = phi %struct.ham* [ %tmp13, %bb12 ], [ null, %bb10 ]
br label %bb16
bb16:
%tmp17 = load i8, i8* undef, align 8
switch i8 %tmp17, label %bb11 [
i8 0, label %bb11
i8 11, label %bb18
i8 12, label %bb18
]
bb18:
br label %bb19
bb19:
br label %bb20
bb20:
%tmp21 = load %struct.ham*, %struct.ham** undef
switch i8 undef, label %bb22 [
i8 0, label %bb4
i8 11, label %bb10
i8 12, label %bb10
]
bb22:
br label %bb23
bb23:
%tmp24 = icmp eq %struct.ham* %tmp21, null
br i1 %tmp24, label %bb35, label %bb25
bb25:
%tmp26 = icmp eq %struct.ham* %tmp15, null
br i1 %tmp26, label %bb34, label %bb27
bb27:
%tmp28 = load %struct.ham*, %struct.ham** undef
%tmp29 = icmp eq %struct.ham* %tmp28, %tmp21
br i1 %tmp29, label %bb35, label %bb30
bb30:
br label %bb31
bb31:
%tmp32 = load i8, i8* undef, align 8
%tmp33 = icmp eq i8 %tmp32, 0
br i1 %tmp33, label %bb31, label %bb34
bb34:
br label %bb35
bb35:
%tmp36 = phi i1 [ true, %bb34 ], [ false, %bb23 ], [ true, %bb27 ]
br label %bb37
bb37:
%tmp38 = icmp eq %struct.ham* %tmp15, null
br i1 %tmp38, label %bb39, label %bb41
bb39:
%tmp40 = load %struct.ham*, %struct.ham** @global
br label %bb41
bb41:
%tmp42 = select i1 %tmp36, %struct.ham* undef, %struct.ham* undef
ret void
}
declare i32 @foo(...)
define void @zot() align 2 personality i8* bitcast (i32 (...)* @foo to i8*) {
bb:
invoke void @bar()
to label %bb1 unwind label %bb3
bb1:
invoke void @bar()
to label %bb2 unwind label %bb4
bb2:
invoke void @bar()
to label %bb6 unwind label %bb17
bb3:
%tmp = landingpad { i8*, i32 }
catch i8* bitcast (i8** @global.1 to i8*)
catch i8* null
unreachable
bb4:
%tmp5 = landingpad { i8*, i32 }
catch i8* bitcast (i8** @global.1 to i8*)
catch i8* null
unreachable
bb6:
invoke void @bar()
to label %bb7 unwind label %bb19
bb7:
invoke void @bar()
to label %bb10 unwind label %bb8
bb8:
%tmp9 = landingpad { i8*, i32 }
cleanup
catch i8* bitcast (i8** @global.1 to i8*)
catch i8* null
unreachable
bb10:
%tmp11 = load i32 (%struct.zot*)*, i32 (%struct.zot*)** undef, align 8
%tmp12 = invoke i32 %tmp11(%struct.zot* nonnull undef)
to label %bb13 unwind label %bb21
bb13:
invoke void @bar()
to label %bb14 unwind label %bb23
bb14:
%tmp15 = load i32 (%struct.zot*)*, i32 (%struct.zot*)** undef, align 8
%tmp16 = invoke i32 %tmp15(%struct.zot* nonnull undef)
to label %bb26 unwind label %bb23
bb17:
%tmp18 = landingpad { i8*, i32 }
catch i8* bitcast (i8** @global.1 to i8*)
catch i8* null
unreachable
bb19:
%tmp20 = landingpad { i8*, i32 }
catch i8* bitcast (i8** @global.1 to i8*)
catch i8* null
unreachable
bb21:
%tmp22 = landingpad { i8*, i32 }
catch i8* bitcast (i8** @global.1 to i8*)
catch i8* null
unreachable
bb23:
%tmp24 = phi %struct.quux.0* [ null, %bb26 ], [ null, %bb14 ], [ undef, %bb13 ]
%tmp25 = landingpad { i8*, i32 }
catch i8* bitcast (i8** @global.1 to i8*)
catch i8* null
br label %bb30
bb26:
%tmp27 = load i32 (%struct.zot*)*, i32 (%struct.zot*)** undef, align 8
%tmp28 = invoke i32 %tmp27(%struct.zot* nonnull undef)
to label %bb29 unwind label %bb23
bb29:
unreachable
bb30:
%tmp31 = icmp eq %struct.quux.0* %tmp24, null
br i1 %tmp31, label %bb32, label %bb29
bb32:
unreachable
}
declare void @bar()
brzyckiAuthorUnsubmitted
Done
ReplyInline Actions

The reduced testcase that crashed LLVM discovered when compiling Chrome.

brzycki: The reduced testcase that crashed LLVM discovered when compiling Chrome.
kuharUnsubmitted
Done
ReplyInline Actions

Wouldn't it be better to add it in a separate file?

kuhar: Wouldn't it be better to add it in a separate file?

llvm/test/Transforms/JumpThreading/lvi-tristate.ll

  • This file was added.
; RUN: opt -jump-threading -simplifycfg -S < %s | FileCheck %s
; CHECK-NOT: BB2:
; CHECK-NOT: BB3:
; CHECK-NOT: BB4:
; CHECK-NOT: BB6:
; CHECK-NOT: BB7:
; CHECK: entry:
; CHECK: BB0:
; CHECK: BB1:
; CHECK: BB5:
; CHECK: exit:
declare void @foo() local_unnamed_addr
define fastcc void @test() unnamed_addr {
entry:
%0 = and i32 undef, 1073741823
%1 = icmp eq i32 %0, 2
br i1 %1, label %BB7, label %BB0
BB0:
%2 = icmp eq i32 %0, 3
br i1 %2, label %exit, label %BB1
BB1:
%3 = icmp eq i32 %0, 5
br i1 %3, label %BB2, label %BB3
BB2:
tail call void @foo()
br label %BB3
BB3:
br i1 %2, label %exit, label %BB4
BB4:
%4 = icmp eq i32 %0, 4
br i1 %4, label %exit, label %BB5
BB5:
br i1 %4, label %BB6, label %exit
BB6:
br label %exit
BB7:
br label %BB0
exit:
ret void
}