RETARGETABLE COMPILER TECHNOLOGY FOR EMBEDDED SYSTEMS Retargetable Compiler Technology for Embedded Systems Tools and Applications by Rainer Leupers and Peter Marwedel University of Dortmund SPRINGER-SCIENCE+BUSINESS MEDIA, B.V. A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN 978-1-4419-4928-8 ISBN 978-1-4757-6420-8 (eBook) DOI 10.1007/978-1-4757-6420-8 Printed on acid-free paper All Rights Reserved © 2001 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers, Boston in 2001 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner. To Carl and Veronika, M alte, Gesine, and Ronja Contents Preface ix 1. INTRODUCTION 1 1.1 Embedded systems and their characteristics 1 1.2 Efficient hardware 3 1.3 Efficient software 4 1.3.1 How to specify embedded system software? 4 1.3.2 Efficient compilers 5 1.3.3 Retargetable compilers 6 2. COMPILERS IN EMBEDDED SYSTEM DESIGN 9 2.1 Design flow and hardware/software codesign 9 2.2 Design space exploration 11 2.2.1 Levels in the design space 11 2.2.2 Algorithm selection 14 2.2.3 Options for implementing algorithms 15 2.2.4 Process mapping and HW /SW partitioning 15 2.2.5 Memory system design 17 2.2.6 Instruction set options 18 2.2.6.1 Design of VLIW machines 18 2.2.6.2 Design of non-VLIW machines 21 2.2.6.3 Word length optimization 21 2.2.6.4 Register file sizing 23 2.2.7 Micro-architectural options 24 2.3 Design verification 26 3. SOME COMPILER TECHNOLOGY BACKGROUND 27 3.1 Front end 28 3.2 Intermediate representation 34 3.3 Backend 40 3.3.1 Code selection 40 vii viii RETARGETABLE COMPILER TECHNOLOGY 3.3.2 Scheduling 44 3.3.3 Register allocation 50 3.3.4 Address code optimization 53 3.3.5 Phase coupling issues 56 3.3.6 Peephole optimization 58 4. HISTORICAL OVERVIEW 59 4.1 Contributions from the compiler community 59 4.1.1 UN COL 59 4.1.2 Code generation for expressions 60 4.2 Contributions from microprogramming 61 4.2.1 Motivation 62 4.2.2 Early work 62 4.2.3 First retargetable microcode compilers 63 4.2.4 The MIMOLA project 64 5. RETARGETABLE COMPILER CASE STUDIES 67 5.1 Retargetable compilers for GPPs 68 5.1.1 GCC 68 5.1.2 LCC 71 5.1.3 Marion 75 5.1.4 PAGODE 76 5.1.5 SUIF /Machine SUIF 77 5.1.6 Zephyr/VPO 79 5.1.7 LANCE 81 5.2 Retargetable compilers for DSPs 84 5.2.1 CBC 84 5.2.2 REDA CO 87 5.2.3 CodeSyn/FlexW are 89 5.2.4 SPAM 91 5.2.5 RECORD 95 5.3 Retarget able compilers for VLIWs 98 5.3.1 ROCKET 98 5.3.2 IMPACT 99 5.3.3 Trimaran 100 5.3.4 Trimedia 102 5.3.5 AVIV 103 5.3.6 Mescal 105 5.4 Retargetable compilers for ASIPs 105 5.4.1 MSSQ 105 5.4.2 PEAS 110 5.4.3 Valen-C 113 5.4.4 EXPRESS 114 5.4.5 BUILDABONG 116 5.5 Special retargetability techniques 118 Contents ix 5.5.1 Code generation methods 118 5.5.1.1 Balakrishnan's microcode compiler 118 5.5.1.2 Mavaddat's formal language approach 119 5.5.1.3 Langevin's automata theoretic approach 119 5.5.1.4 Romer's automata theoretic approach 120 5.5.1.5 Wilson's ILP based code generator 121 5.5.1.6 FACTS 122 5.5.1.7 Bashford's CLP based code generator 123 5.5.1.8 Yamaguchi's code generator 125 5.5.2 Retargetable compilers for microcontrollers 125 5.5.2.1 Krohm's compiler 125 5.5.2.2 SDCC 126 5.5.3 Code generator generators 126 5.5.3.1 IBURG 126 5.5.3.2 OLIVE 129 5.5.3.3 BEG 131 5.5.4 Assembly-level optimization 132 5.5.4.1 SALTO 132 5.5.4.2 PROPAN 132 5.5.5 LISA 134 5.5.6 Compilers for industrial reconfigurable cores 137 5.5. 7 Retarget able test program generation 138 5.5.8 Retargetable estimation 139 5.5.9 Miscellaneous 140 5.6 Commercial retargetable compilers 141 5.6.1 CoSy 141 5.6.2 CHESS 142 5.6.3 Archelon 145 5.6.4 ucc 147 6. SUMMARY AND OUTLOOK 149 Appendices 152 Tabular overview of compiler tools 153 References 155 About the authors 171 Index 173 Preface Embedded systems are information processing systems embedded in larger products. They have their own characteristics which make them different from desktop systems. For example, they have to be imple mented efficiently, and the same holds for the increasing amount of em bedded software. Designing an efficient, software- and processor-based system requires that optimized processors are used. Such an optimiza tion requires a careful analysis of the design space, including a study of cost/performance tradeoffs. In order to avoid assembly language pro gramming for such studies, compilers are needed. For analyzing the effect of design options on the performance, these compilers should be capable of generating code for all potential hardware configurations. This is possible with retargetable compilers. Such compilers can be adapted to new hardware easily. Recently, many new approaches for designing such compilers have been developed. This book presents an overview and classification of these techniques. For each of the compilers, we mention key features, limitations, as well as software availability. The list of retargetable compilers covered has never been collected before. We also introduce key terms and techniques for compiler construction, explain where in the design flow retargetable compilers fit and present a history of retargetability. For people starting work on compilers for embedded systems, this book should save a significant time for finding references. The book is self-contained and requires only fundamental knowledge in software design. It is intended to be a key reference for researchers and designers working on embedded software, compilation, and processor optimization. It can also be used by people who need to get an overview quickly, such as consultants and advisors. Please enjoy reading this book! RAINER LEUPERS, PETER MARWEDEL xi Chapter 1 INTRODUCTION Writing this book was motivated by the growing usage of a large vari ety of processors in embedded systems. This trend has to be reflected in the corresponding development of still missing tools for the design of em bedded systems. In order to understand the requirements for such tools, we will first of all have to look at the characteristics of the application areas that we are considering. 1. Embedded systems and their characteristics Embedded systems can be defined as information processing systems which are integrated into larger systems. In such systems, information processing is usually not directly visible to the user, and customers will typically not buy a certain product -like a car or a mobile phone- be cause he or she is interested in the features of the information processing equipment. For example, customers will not buy a certain model of a mobile phone because of the brand name and the clock speed of the processor contained in the phone. They buy it because of the function ality that it provides, regardless of the electronic system supplying part of that function. The same applies to information processing in cars, trains, airplanes and smart homes, to mention some other examples of embedded systems. In many cases, the customer does not even recognize that information processing takes place, partly because the standard interfaces for PC-like equipment -like mice, keyboards and screens- are typically not available for embedded systems. Rather, push buttons and small displays are used as user interfaces. 1 2 RETARGETABLE COMPILER TECHNOLOGY Tools for the design of embedded systems are very much influenced by the characteristics of embedded systems. What are those characteristics ? The following list contains some of the most relevant ones: 1 Embedded systems have to be efficient. One of the most notable instances of this is the need for energy efficiency, which applies at least to all portable embedded systems. Mobile phones and personal digital assistants are a very good exam ple for this. They use orders of magnitude less energy than today's desktop computers and battery lifetime is a key argument for selling these systems. Energy consumption has also to be considered in the case of cars. Customers expect cars to be operational even after many weeks of not using them. Hence, the energy consumption of parked cars has to be extremely low. Weight is another aspect of efficiency. From looking at the mobile phone market (as well as at the laptop market) it becomes obvious that customers prefer light-weight systems. Silicon area is also very important, since many embedded systems have to be small and have to be fabricated at competitive prices. Many embedded systems -especially multimedia and communication systems- have very high performance requirements. These require ments have to be met with the least amount of resources. Progress in process technology might lead to less emphasis on the efficient use of silicon area and processor performance. However, progress in battery technology is expected to be slow. Hence, the importance of low energy consumption can be expected to increase in the foreseeable future. 2 Embedded systems are using an increasing amount of software. Only some peripheral components are implemented with special pur pose hardware. The main reason for this is the flexibility of software, enabling a short time to market, late design changes and easy pro duct upgrades. For most application areas, current processors are fast enough to meet performance requirements. Also, customers ask for more and more functions and these can be provided in software much easier than in special purpose hardware. As a result, it has been found that, for many application areas, the amount of software in embedded systems is doubling every two years [43].