[LLVMdev] What makes register allocation expensive?

[Mars Saxman]

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.