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

Add profiling to the timer-interrupt handler. When the target operating-system process is interrupted while running, record its saved instruction pointer, map that address to a code region in the executable, and increment an address histogram. Addresses with many samples identify regions consuming a large fraction of execution time. The executable's code can then be disassembled around these addresses even when source and symbolic names are absent.

This is statistical program profiling: uniform samples of running time estimate time spent in code, not exact execution counts. Restrict samples to the desired process and distinguish application execution from unrelated kernel work. A sufficiently fine address histogram and many samples reveal hot loops; varying the sample interval reduces synchronization bias. If exact visit counts rather than time hotspots are needed, arrange breakpoint or single-step traps, or rewrite the binary to add counters, accepting their much larger overhead. Source code is not required to associate sampled execution with instruction addresses.

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.