Run-time Algorithm Specialisation - Specialization With Compilation

Specialization With Compilation

The specialized algorithm has to be represented in a form that can be interpreted. In many situations, usually when is to be computed on many values in a row, we can write as a code of a special abstract machine, and we often say that is compiled. Then the code itself can be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.

Instructions of the abstract machine can usually be represented as records. One field of such a record stores an integer tag that identifies the instruction type, other fields may be used for storing additional Parameters of the instruction, for example a pointer to another instruction representing a label, if the semantics of the instruction requires a jump. All instructions of a code can be stored in an array, or list, or tree.

Interpretation is done by fetching instructions in some order, identifying their type and executing the actions associated with this type. In C or C++ we can use a switch statement to associate some actions with different instruction tags. Modern compilers usually compile a switch statement with integer labels from a narrow range rather efficiently by storing the address of the statement corresponding to a value in the -th cell of a special array. One can exploit this by taking values for instruction tags from a small interval of integers.