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.

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

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.


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