New user self-registration is disabled due to spam. For an account please email bugs-admin@lists.llvm.org with your e-mail address and full name.

Bug 16756 - [CompileTime] GVN takes 60+% of -O3 compile time (was: JumpThreading takes 29% of the wall O3 compile time)
Summary: [CompileTime] GVN takes 60+% of -O3 compile time (was: JumpThreading takes 29...
Status: REOPENED
Alias: None
Product: clang
Classification: Unclassified
Component: -New Bugs (show other bugs)
Version: 3.2
Hardware: Macintosh MacOS X
: P normal
Assignee: Unassigned Clang Bugs
URL:
Keywords: slow-compile
Depends on:
Blocks:
 
Reported: 2013-07-30 17:01 PDT by Jonathan Ragan-Kelley
Modified: 2019-12-24 23:44 PST (History)
14 users (show)

See Also:
Fixed By Commit(s):


Attachments
Source file which causes slow compilation performance (44.43 KB, application/octet-stream)
2013-07-30 17:01 PDT, Jonathan Ragan-Kelley
Details
codegen_arm.bc, reproducer for compile time issue (644.62 KB, application/octet-stream)
2019-04-03 04:23 PDT, Florian Hahn
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Jonathan Ragan-Kelley 2013-07-30 17:01:31 PDT
Created attachment 10959 [details]
Source file which causes slow compilation performance

Halide is a not-especially-complicated C++ project (which happens to use LLVM internally, but that's not the subject of this bug):

  https://github.com/halide/Halide/

Its build process is simple. On most platforms, GCC and MSVC toolchains compile of the C++ source quickly. On OS X (10.8), the stock g++ (llvm-gcc-4.2-based) compiles all but one source file quickly. But on CodeGen_ARM.cpp (https://github.com/halide/Halide/blob/master/src/CodeGen_ARM.cpp), it is pathologically slow (>7 minutes on a 2.8ghz Core2 Xeon Mac Pro, ~5 on a Sandybridge MacBook Air). The same file compiles in the expected second or three on any Homebrew GCC version, using the full GNU toolchain.

Clearly, this tickles something serious in the Apple/LLVM toolchain. The process which chugs for minutes during this is named "clang". The only obvious potential standout here is the relatively complex stack-allocated array "patterns" in CodeGen_ARM::visit(const Cast *op).
Comment 1 Nick Lewycky 2013-07-30 17:29:37 PDT
CodeGen_ARM.cpp:1:10: fatal error: 'CodeGen_ARM.h' file not found
#include "CodeGen_ARM.h"
         ^

Could you preprocess it and upload the .ii?
Comment 2 Jonathan Ragan-Kelley 2013-07-30 17:46:48 PDT
Full preprocessed source here: https://gist.github.com/jrk/6117757

Compiled on OS X with: c++ -O3 CodeGen_ARM.ii. (Without -O3, performance is nominal.)
Comment 3 Eli Friedman 2013-07-30 19:01:35 PDT
-ftime-report points at SROA.  Probably unhappy because the CFG is extremely complex.
Comment 4 Duncan 2014-04-17 16:45:43 PDT
Just profiled this at r206481.

The SROA slowdown is the same as http://llvm.org/bugs/show_bug.cgi?id=17855.  Bottleneck is SSAUpdater.

Running Time	Self		Symbol Name
64684.0ms   43.5%	0.0	 	              (anonymous namespace)::SROA::runOnFunction(llvm::Function&)
64677.0ms   43.5%	1.0	 	               llvm::LoadAndStorePromoter::run(llvm::SmallVectorImpl<llvm::Instruction*> const&) const
64676.0ms   43.5%	0.0	 	                llvm::SSAUpdater::GetValueInMiddleOfBlock(llvm::BasicBlock*)
64676.0ms   43.5%	0.0	 	                 llvm::SSAUpdater::GetValueAtEndOfBlockInternal(llvm::BasicBlock*)
64672.0ms   43.5%	9.0	 	                  llvm::SSAUpdaterImpl<llvm::SSAUpdater>::GetValue(llvm::BasicBlock*)
64379.0ms   43.3%	63469.0	 	                   llvm::SSAUpdaterImpl<llvm::SSAUpdater>::FindAvailableVals(llvm::SmallVectorImpl<llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BBInfo*>*)

However, even more time is spent in CorrelatedValuePropagation.  The bottleneck there is LVIValueHandle::deleted().

Running Time	Self		Symbol Name
68279.0ms   46.0%	30.0	 	              (anonymous namespace)::CorrelatedValuePropagation::runOnFunction(llvm::Function&)
65876.0ms   44.3%	10.0	 	               llvm::Value::replaceAllUsesWith(llvm::Value*)
65856.0ms   44.3%	12.0	 	                llvm::ValueHandleBase::ValueIsRAUWd(llvm::Value*, llvm::Value*)
65818.0ms   44.3%	65474.0	 	                 (anonymous namespace)::LVIValueHandle::deleted()

I was going to close PR17855 as a dup, but now I'm thinking this PR should track the CorrelatedValuePropagation bottleneck, while PR17855 tracks the SROA slowdown.
Comment 5 Mehdi Amini 2015-08-23 17:25:44 PDT
r245820 fixes the SROA issue and improves -O3 compile-time from 113s to 12s on my machine.

Top5 is now:

Running Time	Self (ms)		Symbol Name
3445.0ms   29.4%	5.0	 	            (anonymous namespace)::JumpThreading::runOnFunction(llvm::Function&)
1483.0ms   12.6%	2.0	 	            (anonymous namespace)::GVN::runOnFunction(llvm::Function&)
1063.0ms    9.0%	17.0	 	            (anonymous namespace)::CorrelatedValuePropagation::runOnFunction(llvm::Function&)
697.0ms    5.9%	0.0	 	             (anonymous namespace)::X86DAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&)
589.0ms    5.0%	4.0	 	             (anonymous namespace)::RegisterCoalescer::runOnMachineFunction(llvm::MachineFunction&)
Comment 6 Reid Kleckner 2015-11-17 11:53:20 PST
Mehdi, sounds like this is fixed?
Comment 7 Mehdi Amini 2015-11-17 12:38:00 PST
As of r253350, nothing changed since my last update, still ~30% of the total clang invocation is spent in JumpThreading.
Did you get different measurements? I measured on OS X.
Comment 8 Reid Kleckner 2015-11-17 13:25:30 PST
(In reply to comment #7)
> As of r253350, nothing changed since my last update, still ~30% of the total
> clang invocation is spent in JumpThreading.
> Did you get different measurements? I measured on OS X.

No, but the original report was that the file took 7m to compile. You said it takes 12s now, despite the fact that 30% of the time is in JumpThreading. If you want to leave it open to track future improvements to JumpThreading or GVN, go for it.
Comment 9 Mehdi Amini 2015-11-17 13:29:07 PST
Oh I see, yes that was my idea when I did the previous measurements.
Do you think I should have closed this bug as fixed and opened a new one for JumpThreading?
Comment 10 Florian Hahn 2019-04-03 04:22:11 PDT
Majority of the compile time now spent in GVN. Updating the title to reflect that. Also attached codegen_arm.bc.

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

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   6.4170 ( 64.2%)   0.0243 ( 14.0%)   6.4413 ( 63.3%)   6.4422 ( 63.3%)  Global Value Numbering
   0.6697 (  6.7%)   0.0046 (  2.7%)   0.6743 (  6.6%)   0.6743 (  6.6%)  Value Propagation
   0.6127 (  6.1%)   0.0064 (  3.7%)   0.6191 (  6.1%)   0.6191 (  6.1%)  Jump Threading
   0.2233 (  2.2%)   0.0035 (  2.0%)   0.2268 (  2.2%)   0.2268 (  2.2%)  Function Integration/Inlining
   0.1531 (  1.5%)   0.0018 (  1.0%)   0.1550 (  1.5%)   0.1549 (  1.5%)  Jump Threading #2
Comment 11 Florian Hahn 2019-04-03 04:23:03 PDT
Created attachment 21722 [details]
codegen_arm.bc, reproducer for compile time issue