|
Another important branch in address code optimisation for DSPs is address register assignment. Such techniques are used to assign address registers to access data for which the memory layout has been already defined. It can be directly applied to access array elements inside program loops, or to reduce the number of update instructions resulting from using offset assignment.
The problem of assigning address registers to array references, inside basic blocks, is known as Local Array Reference Allocation (LARA). It has been originally studied by Araujo (1996) and Leupers (1998). The solutions to LARA are based on solving a path covering problem in a graph, called Indexing Graph (IG). In the IG, vertices are associated to array references, and edges correspond to an opportunity of using auto-increment to redirect address registers from one reference to another. Paths on the IG represent a sequence of array references that share the same address register, such that only auto-increment instructions are required to move from one reference to another (or, in another words, no update instruction is required to access all references on the path).
In the example below, array references, inside the loop on the left, are modelled as an IG (on the right). All references can be accessed by two address registers, corresponding to the red path (AR0) and blue path (AR1). Loop-carried paths on the IG, like edge (6)-(1), can also share the same address register across consecutive loop iterations.
The problem of assigning address registers to array references, across basic blocks, is known as Global Array Reference Allocation (GARA). It has been originally proposed by Araujo (2000) and its solution is based on an operation called live range merge. Each range is associated to a set of array references and one address register. The merge combines two live ranges into a new range that shares the same address register. The cost of a merge is measured by the number of update instructions required to access all array references in the resulting range. Live ranges are merged, a pair at a time, until the final number of ranges is equal to the total number of address registers in the architecture.
In the example below, two live ranges are represented (red and blue), and each one is associated to a different address register. After they are merged, a single range results (figure on the right) that uses a common address register (ar) to access all array references in the resulting range, and to perform update operations (dashed lines on the right). Symbols ++ (--) following array references show the utilization of auto-increment (decrement) mode by "ar" at some array references.
Based on the approach above, a number of enhancements and generalizations have been published, including
- Exploitation of loop-carried path covering in LARA
- Improvement of live range merge using SSA-form and dynamic programming in GARA.
|
