ST20-C1 STMICROELECTRONICS [STMicroelectronics], ST20-C1 Datasheet - Page 179

• Manufacturer Part Number: ST20-C1
• Description: Instruction Set Reference Manual
• Manufacturer: STMICROELECTRONICS [STMicroelectronics]

This is because when the two offsets are reduced, their prefixing sequences take 1
byte less so that the two interlocking jumps will still transfer control to the same
instructions as before. This compaction of non-optimal prefix sequences is difficult to
perform and a better method is to slowly build up the prefix sequences so that the
optimal solution is achieved. The following algorithm performs this.
The stable state that is achieved will be the optimal state.
Where the code being analyzed has alignment directives, then it is possible that this
algorithm will not reach a stable state. One solution to this, is to allow the algorithm to
increase the instruction size but not allow it to reduce the size. This is achieved by
modifying stage 7 to choose the larger of: the currently calculated length, and the
previously calculated length. This approach does not always lead to minimal sized
code, but it guarantees termination of the algorithm.
Steps 2 and 3 can be combined so that the number of bytes required by each jump is
updated as the offset is calculated. This does mean that if an estimate is increased
then some previously calculated offsets may have been invalidated, but step 4 forces
another loop to be performed when those offsets can be corrected.
By initially setting the estimated size of offsets to zero, all jumps whose destination is
the next instruction are optimized out.
Knowledge of the structure of code generated by the compiler allows this process to
be performed on individual blocks of code rather than on the whole program. For
example it is often possible to optimize the prefixing in the code for the sub-compo-
nents of a programming language construct before the code for the construct is opti-
mized. When optimizing the construct it is known that the sub-components are already
optimal so they can each be considered as a fixed block of code which cannot be
reduced.
This algorithm may not be efficient for long sections of code whose underlying
structure is not known. If no knowledge of the structure is available (e.g. in an assem-
bler), all the code must be processed at once. In this case a code shrinking algorithm
where in step one the initial number of bytes is set to twice the number of bytes per
word is used. The prefix sequences then shr ink on each iteration of the loop. 1 or 2
iterations produce fairly good code although this method will not always produce
optimal code as it will not correctly prefix the pathological example given above.
5
6
7
8
Associate with each jump instruction or offset load an ‘estimate’ of the number
of bytes required to code it and initially set them all to 0.
Evaluate all jump and load offsets under the current assumptions of the size of
prefix sequences to the jumps and offset loads
For each jump or load offset set the number of bytes needed to the number in
the shortest sequence that will build up the current offset.
If any change was made to the number of bytes required then go back to 2 oth-
erwise the code has reached a stable state.
179/205