Guido Araujo
Sharad Malik
ABSTRACT
Abstract: This paper examines the problem of code generation for expression trees on non-homogeneous register set architectures. It proposes and proves the optimality of an O(n) algorithm for the tasks of instruction selection, register allocation and scheduling on a class of architectures defined as the [1,/spl infin/] model. Optimality is guaranteed by sufficient conditions derived from the register transfer graph (RTG), a structural representation of the architecture which depends exclusively on the processor instruction set architecture (ISA). Experimental results using the TMS320C25 as the target processor show the efficacy of the approach.
- 1.A.V. Aho, t/. bethi, and J.D. U llman. C'ompilers, Principles, Techniques and Tools. Addison Wesley, Boston, 1988. Google Scholar
Digital Library
- 2.M.R. Garey and D.S. Johnson. Computers and Intractability. W. H. Freeman and Company, New York, 1979. Google ScholarDigital Library
- 3.A.V. Aho and S.C. Johnson. Optimal code generation for expression trees. Journal of the A CM, 23(3):488- 501, July 1976. Google ScholarDigital Library
- 4.B. Wess. Automatic instruction code generation based on trellis diagrams. In Proc. Int. Conf. Circuits and Systems, volume 2, pages 645-648, 1992.Google ScholarCross Ref
- 5.A.V. Aho, M. Ganapathi, and S.W.K Tjiang. Code generation using tree matching and dynamic programming. A CM Trans. Prog. Lang. and Systems, 11(4):491-516, October 1989. Google ScholarDigital Library
- 6.C.W. Fraser, D.R. Hanson, and T.A. Proebsting. Engineering a simple, efficient code generator. Journal of the A CM, 22(12):248-262, March 1993.Google Scholar
- 7.Tjiang S.W.K. An olive twig. Technical report, Synopsys Inc., 1993.Google Scholar
- 8.R. Sethi and J.D. Ullman. The generation of optimal code for arithmetic expressions. Journal of the A CM, 17(4):715-728, October 1970. Google ScholarDigital Library
- 9.V. Zivojnovic, J.M. Velarde, and C. Scl~ger. DSP- stone, a DSP benchmarking methodology. Technical report, Aachen University of Thecnology, August 1994.Google Scholar
- 10.Liao S.Y., Devadas S., Keutzer K., Tjiang S., and Wang A. Storage assignment to decrease code size. Accepted for publication in 1995 ACM Conference on Programming Language Design and Implementation. Google ScholarDigital Library
Index Terms
- Optimal code generation for embedded memory non-homogeneous register architectures
Recommendations
Integrated instruction selection and register allocation for compact code generation exploiting freeform mixing of 16- and 32-bit instructions
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimizationFor memory constrained embedded systems code size is at least as important as performance. One way of increasing code density is to exploit compact instruction formats, e.g. ARM Thumb, where the processor either operates in standard or compact ...
A study of time redundant fault tolerance techniques for superscalar processors
DFT '95: Proceedings of the IEEE International Workshop on Defect and Fault Tolerance in VLSI SystemsAs more and more transistors are incorporated into processor chips, the circuits are becoming more and more error-prone, necessitating the introduction of fault tolerance techniques. This paper investigates techniques to incorporate fault tolerance in ...
Optimal integrated code generation for VLIW architectures: Research Articles
10th International Workshop on Compilers for Parallel Computers (CPC 2003)We present a dynamic programming method for optimal integrated code generation for basic blocks that minimizes execution time. It can be applied to single-issue pipelined processors, in-order-issue superscalar processors, VLIW architectures with a ...
Comments