Storage Assignment to Decrease Code SizeSTAN LIAOSynopsys, Inc.andSRINIVAS DEVADASMassachusetts Institute of TechnologyandKURT KEUTZER, STEVEN TJIANG, and ALBERT WANGSynopsys, Inc.DSP architectures typically provide indirect addressing modes with autoincrement and decrement. In addition,indexing mode is generally not available, and there are usually few, if any, general-purpose registers. Hence, itis necessary to use address registers and perform address arithmetic to access automatic variables. Subsumingthe address arithmetic into autoincrement and decrement modes improves the size of the generated code. In thisarticle we present a formulation of the problem of optimal storage assignment such that explicit instructionsfor address arithmetic are minimized. We prove that for the case of a single address register the decisionproblem is NP-complete, even for a single basic block. We then generalize the problem to multiple addressregisters. For both cases heuristic algorithms are given, and experimental results are presented.Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors—compilers; optimizationGeneral Terms: Algorithms, ExperimentationAdditional Key Words and Phrases: Code size, compilation, storage assignment1. INTRODUCTIONMicroprocessors such as microcontrollers and fixed-point digital signal processors (DSPs)are increasingly being embedded into many electronic products. In fact, the use ofmicroprocessors in embedded systems outnumbers the use of processors in both the PCand the workstation market combined. Two trends are becoming clear in the designof embedded systems. First, considerations for cost, power, and reliability are forcingThis research was supported in part by the Advanced Research Projects Agency under contract DABT63-94-C-0053 and in part by a NSF Young Investigator Award with matching funds from Mitsubishi Corporation.A version of this article was presented at the 1995 ACM/SIGPLAN Conference on Programming LanguageDesign and Implementation, La Jolla, California, June 19–22, 1995.Authors’ addresses: S. Liao, K. Keutzer, S. Tjiang, and A. Wang, Synopsys, Inc., 700 East MiddlefieldRoad, Mountain View, CA 94043-4033; email: {stanliao; keutzer; tjiang; awang}@synopsys.com; S. Devadas,Research Laboratory of Electronics, Massachusetts Institute of Technology, MA 02139-4307; email: [email protected] to make digital/hard copy of all or part of this material without fee is granted provided that thecopies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, thetitle of the publication, and its date appear, and notice is given that copying is by permission of the Associationfor Computing Machinery, Inc. (ACM). To copy otherwise, to republish, to post on servers, or to redistributeto lists requires prior specific permission and/or a fee.c 1996 ACM 0164-0925/96/0500-0235 $03.50ACM Transactions on Programming Languages and Systems, Vol. 18, No. 3, May 1996, Pages 235–253.236 · Stan Liao et al.designers into taking the next step: incorporating all the electronics—microprocessor,program ROM and RAM, and application-specific circuit components—into a singleintegrated circuit. Second, the amount of software incorporated into embedded systemsis growing larger and more complex.The first trend elevates code density to a new level of importance because programcode resides in on-chip ROM, the size of which translates directly into silicon area andcost. Moreover, designers often devote a significant amount of time to reduce code size sothat the code will fit into available ROM, as exceeding on-chip ROM size could requireexpensive redesign of the entire IC [Ganssle 1992, p. 18] and even of the whole system.The second trend—increasing software and system complexity—mandates the use ofhigh-level languages (HLLs) in order to decrease development costs and time-to-market.However, current compilers for microcontrollers and fixed-point DSPs generate code thatleaves much room for improvement [ˇZivojnovi´c et al. 1994]—thus programming in anHLL can incur penalties on code size and performance.While optimizing compilers have proved effective for general-purpose processors,the irregular data-paths and small number of registers found in embedded processors,especially fixed-point DSPs, remain a challenge to compilers. The direct application ofconventional code optimization methods (e.g., Aho et al. [1986]) has thus far been unableto generate code that efficiently uses the features of fixed-point DSP architectures.We believe that generating the best code for embedded processors will require notonly traditional optimization techniques, but also new techniques that take advantage ofspecial architectural features and that decrease code size. This article presents one ofour efforts at developing such techniques: a data lay-out algorithm that decreases codesize.Many architectures (e.g., the VAX, TI TMS320C25, most embedded controllers) pro-vide indirect addressing modes with autoincrement/autodecrement arithmetic. These fea-tures allow for efficient sequential access of memory and increase code density, be-cause they subsume address arithmetic instructions and result in shorter instructions invariable-length instruction architectures. In particular, DSPs and embedded controllersare designed assuming software that runs on them would make heavy use of autoincre-ment/autodecrement addressing. In many cases, the set of available addressing modesin DSPs and controllers does not include a mode for indexing with a constant offset.Therefore, it is necessary to allocate a register and perform address arithmetic to accessvariables. Subsuming the address arithmetic into autoincrement/autodecrement modesimproves both the size and performance of the generated code.The placement of variables in storage has a significant impact on the effectiveness ofsubsumption. Our compiler delays storage allocation of variables, moving it from thefront-end to the code generation step that selects addressing modes, thereby increasingopportunities to use efficient autoincrement/autodecrement modes. We formulate thisdelayed storage allocation as the offset assignment problem. Although some modern DSParchitectures permit increments and decrements of values other than one (e.g., MotorolaDSP56000), it is costly to use this feature if the modifier value varies frequently. Thisis because extra instructions are required to set the