Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 8 / b / ii / Solution

Use strength reduction on the disassembled hot instructions. In a fixed-width wrapping integer model,The first replacement is a single left bit shift. For the second, preserve the original operand in a register, shift a copy left by four and subtract the original:This avoids a general multiplication if shifts and subtraction are cheaper on the target processor. The two identities hold for positive and negative two's complement operands when only the low $w$ result bits are required.

Because only a binary is available, patch the machine instructions and adjust displaced branches or use a jump to a replacement code block if the new sequence does not fit. Preserve live registers and the calling convention. If later instructions consume overflow or other condition flags, or the original multiplication produces a double-width result or traps on overflow, matching only the low-word arithmetic is insufficient: those effects must be reproduced or the transformation rejected. Finally, measure the modified program; a fast hardware multiply need not be slower than several replacement instructions.