What I'm thinking is, he needs to factor all the instructions out into separate functions so that he stops hitting the optimization boundaries (or he may be able to override them with parameters to the compiler). Then, mark the hot paths with the expect builting.
One that's in, use profile guided optimization (again name varies based on compiler), to feed the compiler with more frequency information on the branches. Partial inlining (not sure if GCC has this opt yet) should take care of the rest.
As for the register assignment, well that's hard to get right while getting the instruction scheduling right at the same time. Profile guided optimization will help guide the global register allocator in the right direction, but it likely won't be perfect. Thankfully, on modern architectures, register to register moves are pretty much NOPs thanks to register files, short circuting, and out of order.
* that C-code interpreters force the compiler to do register allocation across the slow paths of all instructions, even though the interpreter dev can in this case definitely predict which things need to be in registers;
* and, the optimizer in the compiler makes it hard to tune the code for the 20% that does 80% of the work, where an assembly program can hoist the slow path code out of the I-cache entirely.