I've tried this with GCC 4.7.1 on Debian x86_64 and did not get it to work in constant time with -O2.

I'm guessing (from the OP's usage of -install_name) that he's been compiling this on OSX. I wonder what did my compiler miss that the OP's didn't?

EDIT: just tried with clang and got constant time behaviour, interesting

EDIT 2: reading the comments in the post, I now suspect it has to do with integer overflow. However, compiling with -fwrapv did not change anything. Need to dig into it more.

EDIT 3: it seem that clang simply notices that the computation can be done in constant time, whereas gcc does not. I'm not sure if it's actually useful in real world code, but it's certainly somewhat magical to see a compiler understand that you can substitute the entire loop with a simple calculation