llvm dev - Oct 2013 - [LLVMdev] What makes register allocation expensive?

Compile times increased by roughly 20X after upgrading the Radian 
compiler project from LLVM 3.1 to 3.3. I am curious whether this is 
considered normal. If it is not, I would appreciate some help figuring 
out what it is about the Radian compiler's output which is causing LLVM 
to spend so much time compiling such small programs.

I recorded these times with Apple's Xcode Instruments (version 4.6.1). 
The input is the most basic program in the test suite; it prints "hello, 
world" and counts from 1 to 10, so it is about a dozen lines long and 
refers to maybe five hundred lines of library code. All times are in 
milliseconds, and the total includes both compilation and program 
execution.

llvm-3.1:
2722 total
2342 llvm::ExecutionEngine::runFunctionAsMain
	1144 SelectionDAGIsel::runOnMachineFunction
	294 RegisterCoalescer::runOnMachineFunction
	116 RAGreedy::runOnMachineFunction

llvm-3.3:
53683 total
52661 llvm::ExecutionEngine::runFunctionAsMain
	16955 RAGreedy::runOnMachineFunction
	15149 RegisterCoalescer::runOnMachineFunction
	15072 SelectionDAGIsel::runOnMachineFunction

Both cases use createJIT with default values, so optimization is 
presumably llvm::CodeGenOpt::Default.

Disabling optimization yields a more reasonable run time with llvm-3.3:
1028 total
712 llvm::ExecutionEngine::runFunctionAsMain
	491 SelectionDAGISel::runOnMachineFunction
	85 RAFast::runOnMachineFunction

But even llvm::CodeGenOpt::Less has become very expensive:
7633 total
7307 llvm::ExecutionEngine::runFunctionAsMain
	3386 SelectionDAGISel::runOnMachineFunction
	1311 RAGreedy::runOnMachineFunction
	1157 RegisterCoalescer::runOnMachineFunction

What might have changed between LLVM 3.1 and 3.3 which would cause such 
a dramatic change in compile times?

Thank you for any suggestions of places I should begin to look.

Hi, so just to verify the obvious: these are both the same type of build
(Release-Asserts, or whatever) rather than an optimized 3.1 vs a 3.3 debug
build? (I know this is unlikely, but I've managed to mix-up my
configurations in the past so it is worth checking before trying more
involved options). A 20x slow-down that looks to be on everything (rather
than one component) is a strong symptom for this.

Cheers,
Dave 

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Mars Saxman
Sent: 08 October 2013 03:03
To: llvmdev at cs.uiuc.edu
Subject: [LLVMdev] What makes register allocation expensive?

Compile times increased by roughly 20X after upgrading the Radian 
compiler project from LLVM 3.1 to 3.3. I am curious whether this is 
considered normal. If it is not, I would appreciate some help figuring 
out what it is about the Radian compiler's output which is causing LLVM 
to spend so much time compiling such small programs.

I recorded these times with Apple's Xcode Instruments (version 4.6.1). 
The input is the most basic program in the test suite; it prints "hello, 
world" and counts from 1 to 10, so it is about a dozen lines long and 
refers to maybe five hundred lines of library code. All times are in 
milliseconds, and the total includes both compilation and program 
execution.

llvm-3.1:
2722 total
2342 llvm::ExecutionEngine::runFunctionAsMain
	1144 SelectionDAGIsel::runOnMachineFunction
	294 RegisterCoalescer::runOnMachineFunction
	116 RAGreedy::runOnMachineFunction

llvm-3.3:
53683 total
52661 llvm::ExecutionEngine::runFunctionAsMain
	16955 RAGreedy::runOnMachineFunction
	15149 RegisterCoalescer::runOnMachineFunction
	15072 SelectionDAGIsel::runOnMachineFunction

Both cases use createJIT with default values, so optimization is 
presumably llvm::CodeGenOpt::Default.

Disabling optimization yields a more reasonable run time with llvm-3.3:
1028 total
712 llvm::ExecutionEngine::runFunctionAsMain
	491 SelectionDAGISel::runOnMachineFunction
	85 RAFast::runOnMachineFunction

But even llvm::CodeGenOpt::Less has become very expensive:
7633 total
7307 llvm::ExecutionEngine::runFunctionAsMain
	3386 SelectionDAGISel::runOnMachineFunction
	1311 RAGreedy::runOnMachineFunction
	1157 RegisterCoalescer::runOnMachineFunction

What might have changed between LLVM 3.1 and 3.3 which would cause such 
a dramatic change in compile times?

Thank you for any suggestions of places I should begin to look.

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On 2013-10-08 01:31, David Tweed wrote:
> Hi, so just to verify the obvious: these are both the same type of 
> build
> (Release-Asserts, or whatever) rather than an optimized 3.1 vs a 3.3 
> debug
> build?
Sure enough, that explains the difference. I was sure it couldn't 
possibly be something that simple, since git history shows that the only 
change in the setup script was the version number, but of course that 
doesn't show the command line arguments used to invoke the script. I 
must have switched at some point in the past and forgotten about it. 
(And the build machine isn't running right now, so I only have my laptop 
to test it on.)

Thank you - back to more productive work now...