Simple Offset Assignment in Presence of Subword Data

摘要

Many embedded architectures support indirect addressing mode with autoincrement/autodecrement. By maximizing the use of this mode, generation of explicit instructions for performing address arithmetic can be avoided and thus reductions in code size and improvements in performance are achieved. Bartley and Liao et al. developed a method for finding a storage layout for program variables so that the use of autoincrement/autodecrement could be maximized. They introduced the Simple Offset Assignment (SOA) problem and solved it using a Path Cover (PC) formulation. We observe that many media and network processing applications make extensive use of subword data. Therefore, for such applications, by packing multiple subword variables into a single word, we can generate storage layouts that further reduce the cost of address arithmetic in two ways. First the need for address arithmetic is reduced as variables that are packed together share the same address. Second opportunities for using autoincrement and autodecrement instructions are increased as layouts are now possible which place a variable adjacent to more than two variables. This approach has become feasible because of the recent trend in embedded processor design which allows subword variables that are packed together to be accessed and manipulated without incurring performance penalty. We introduce the SubWord Offset Assignment (SWOA) problem and solve it using a Path Cover with Node Coalescing (PCwNC) formulation. Node coalescing corresponds to packing of multiple subword variables into a single word while path covering corresponds to placement of variables in adjacent memory locations to enable the use of autoincrement/autodecrement. We present three heuristics to solve the PCwNC problem. Experiments show that when the program is optimized for code size, the three proposed algorithms achieve 26%, 26.9% and 32% reduction in the number of static explicit address arithmetic instructions over Liao et al.'s algorithm. The algorithms also achieve 14.5%, 22.1% and 22.7% reduction in stack frame size. If the program is optimized for performance, the algorithms achieve 24.3%, 24.7% and 30.2% reduction in the dynamic instruction count of explicit address arithmetic instructions.