Addressing Mode Selection

The addressing mode selection (AMS) problem deals with the generation of addressing modes for a given offset layout and a given address register assignment. It can be seen as a global code-selection technique for DSP-processors for fully utilizing the address generation unit -- even for complex address modes.

Consider the pseudo code of the example above. The goal of AMS is to optimize the addressing modes of register ar0. The underlying target architecture supports indirect addressing mode *(ar), post modification addressing mode *(ar0++), *(ar0-), *(ar0+=c), and indexing addressing mode *(ar+c). The optimal output program for minimal execution time is shown in the same figure on the right-hand side. The add instruction can be moved out of the loop and post modification addressing modes can be used instead of indexing addressing modes in line (5) and (6). An explicit add instruction for the address register must be prior to the loop and in line (4), but this takes less cycles than the code given in the original program.

AMS is an separable problem and can be performed for every address register independent of the other ones. The decision, which address mode is the cheapest, is based on a cost model (code size, speed, etc.). In general AMS is NP complete.

The basic transformation is a local offset shift between statements of a program. Let us consider two subsequent statements stmt1;stmt2. Both statements use address register ar for accessing memory and modify the value of the address register. Now, the principle idea of AMS is to shift the value of ar between those two statements. We replace stmt1 by stmt1' and statement stmt2 by stmt2'. The semantics of stmt1' and stmt2' are given by stmt1;ar+=delta; and ar-=delta;stmt2, respectively. Depending on the offset value delta, cheaper addressing modes might be employed for both statements. This is achieved by replacing the increment of the address register and the prior address operation by a cheaper addressing mode (also known as strength reduction).

The AMS problem has been studied by Eckstein and Scholz (2003). Their approach is based on partitioned boolean quadratic programming (PBQP) that allows highly parameterizable cost models and a wide range of addressing modes.