[LLVMdev] What makes register allocation expensive?

[David Tweed]

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