section on CPU pipelines later in this chapter). It is also possible to partially
unroll a loop so that the number of iterations is reduced by performing more
than one iteration in each cycle of the loop.
When going over switchblocks, compilers can determine what would be
the most efficient approach for searching for the correct case in runtime. This
can be either a direct table where the individual blocks are accessed using the
operand, or using different kinds of tree-based search approaches.
Another good example of a code structuring optimization is the way that
loops are rearranged to make them more efficient. The most common high-
level loop construct is the pretested loop, where the loop’s condition is tested
before the loop’s body is executed. The problem with this construct is that it
requires an extra unconditional jump at the end of the loop’s body in order to
jump back to the beginning of the loop (for comparison, posttested loops only
have a single conditional branch instruction at the end of the loop, which
makes them more efficient). Because of this, it is common for optimizers to
convert pretested loops to posttested loops. In some cases, this requires the
insertion of an ifstatement before the beginning of the loop, so as to make
sure the loop is not entered when its condition isn’t satisfied.
Code structure optimizations are discussed in more detail in Appendix A.
Redundancy Elimination
Redundancy eliminationis a significant element in the field of code optimization
that is of little interest to reversers. Programmers frequently produce code that
includes redundancies such as repeating the same calculation more than once,
assigning values to variables without ever using them, and so on. Optimizers
have algorithms that search for such redundancies and eliminate them.
For example, programmers routinely leave static expressions inside loops,
which is wasteful because there is no need to repeatedly compute them—they
are unaffected by the loop’s progress. A good optimizer identifies such state-
ments and relocates them to an area outside of the loop in order to improve on
the code’s efficiency.
Optimizers can also streamline pointer arithmetic by efficiently calculating
the address of an item within an array or data structure and making sure that
the result is cached so that the calculation isn’t repeated if that item needs to be
accessed again later on in the code.
Back End
A compiler’s back end, also sometimes called the code generator, is responsi-
ble for generating target-specific code from the intermediate code generated
and processed in the earlier phases of the compilation process. This is where
the intermediate representation “meets” the target-specific language, which is
usually some kind of a low-level assembly language.
Low-Level Software 57