文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Published in “The 13 th International Static Analysis Symposium”, Korea, 2006 Catching an
侵权投诉

Published in “The 13 th International Static Analysis Symposium”, Korea, 2006 Catching an

Abstract. Although there are many register allocation algorithms that work well, it can be difficult to correctly implement these algorithms. As a result, it is common for bugs to remain in the register allocator, even after the compiler is released. The r

Published in “The 13th International Static Analysis Symposium”, Korea, 2006

Catching and Identifying Bugs in Register Allocation

Yuqiang Huang , Bruce R. Childers , and Mary Lou Soffa

Department of Computer Science

University of Pittsburgh

Pittsburgh, Pennsylvania 15260

{yuqiangh, childers}@cs.pitt.edu Department of Computer Science University of Virginia Charlottesville, Virginia 22904 soffa@cs.virginia.edu

Abstract. Although there are many register allocation algorithms that work

well, it can be difficult to correctly implement these algorithms. As a result, it

is common for bugs to remain in the register allocator, even after the

compiler is released. The register allocator may run, but bugs can cause it to

produce incorrect output code. The output program may even execute

properly on some test data, but errors can remain. In this paper, we propose

novel data flow analyses to statically check that the output code from the

register allocator is correct in terms of its data dependences. The approach is

accurate, fast, and can identify and report error locations and types. No false

alarms are produced. The paper describes our approach, called SARAC, and

a tool, called ra-analyzer, that statically checks a register allocation and

reports the errors it finds. The tool has an average compile-time overhead of

only 8% and a modest average memory overhead of 85KB.

1 Introduction

One of the most critical compiler transformations is register allocation, as a good allocator can make a dramatic difference in obtaining good performance [4, 11]. One study even reported that careful register allocation makes one order of magnitude difference in performance [26]! Thus, considerable effort has been given to developing new allocation algorithms or variants of existing ones [2-7, 11, 12, 24, 26, 28, 30]. Given the many algorithm variants and the complexity of modern architectures, implementing register allocation is often a complex and error prone task. Particularly, it is difficult to detect and locate bugs in an erroneous output of the allocator if the code runs to completion. Some efforts [13, 18, 21] have proposed techniques to ensure the allocator’s implementation is correct. In this paper, we describe a novel technique to check the correctness of register allocation and also to report the bugs. This technique is useful throughout the lifetime of a compiler, particularly during the development period.

Although a compiler undergoes much testing, bugs in the register allocator often slip past regression tests and are reported after release. What is worse is that many of these bugs cause the compiler to fail on some input programs, but not on others. The generated code may have bugs, although the compiler did not crash. Such latent bugs will not be discovered until a particular test input causes the program to fail. Assuming that a test input catches the bug, the developer is likely to believe that the bug is in the program itself, rather than the compiler. She will spend much time and effort tracking

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email