Toward Automatic Debugging of Compilers

TU\JAlW AUTOt·lATIC OEllUGGirlG OF COHPILERS*

Hanan Samet Computer Science Departr.1ent University of i1aryland College Park, t1aryland 20742

Abstract

Autoraatic debugging is examined in the context of compiler correctness. A system is described 11hose goal is to prove the correctness of translations involving heuristically optimized code. The class of errors that can be detected and corrected using such a system is also discussed.

Keywor~s and phrases: debugging, compilers, error de tee t1.on, error correction, program verification

INTRODUCTION

In [Samet77a] we describe the use of a cot:lpiler testing systeoa [Samet75] in detecting errors in heuristically optimized code as well as t;h~ prospects for automatically correcting them. Th1.s work is motivated by the realization tlnt often there is no a priori knowledge of how certain cor.1puter programs are to be optimized. In such a case, there may be a need to resort to heuristics· thereby nec~ssitating a mechanism for verifying that the .var1.ous attempts at optimization do indeed function properly.

, ~ompiler testing is a technique of proving tnat g1.ven a compiler (or any translation procedure) and a program to be compiled the translation .has been cor~ectly performed. Co~piler testing rel1.es on the ex1.stence of an intermediate representation comr:ton to both the source and object programs. This representation reflects all of the computations performed on all ::>ossible execution paths. Given the existence of such a representation, t~e testing p~ocedure consists of three steps. F1.rst, the !ugh level langua<>e program i~ converted to the intermediate representat1.on via the use of a suitable set of syntactic transformations [Samet77b]. Second, the low level program must be converted to the intermediate representation. This is achieved by use of a process termed symbolic interpretation [Samet76] which interprets procedural descriptions of low level machine operations to build the intermediate representation. Third, a check must be performed of the equivalence of the two representations. This check is in the form of a procedure which applies equivalence preserving transformations to the results of the first two steps in attempting to reduce them to a conunon representation. This technique has been applied to LISP and PDP-10 assembly language.

Errors in the translated prograon that are caused by the translation process are categorized into four classes. Errors of the first class are detected by the s¥mbolic interpretation procedure while the remain1.ng three classes are detected during the proof procedure as computations are being matched ln the two intermediate representations.

• ( 1) Errors pertaining program include illegal stack operations on structures, etc. to the well-formedness of the improper calling sequences, pointer formats, illegal certain high level data
• All of the computations in one of the intermediate representations were found to exist in the other representation, but the

*This work was supported in part by the Advanced Research Projects Agency of the Department of Defense under Contract DAHC 15-73-c-0435. The views expressed are those of the author.

reverse is not true. Such an error may arise when certain side effect cor:tputations occur in one of the programs and not in the other. Alternatively~ this may also arise \~hen certain t~sts are pertormed in one program and not in tne other.

1. There are occasions when each of the intermediate representations reflects the perforr?ance of, the sar.1e coraputations along each executl.on pata, yet, the two representations are not identical. This occurs when the results of the execution paths are different.
2. The actual proof procedure may reach a point at which it cannot continue. This is the case when a function in the intermediate representati<:>n of the l<:JW l~vel progra<:t can not be matched w1.th a funct1.on 1.n the intermediate representation corresponding to the original high level program.

Error correction is a difficult task. In [Samet77a] we show how the following heuristics are used to debug an incorrectly translated complex function (l 05 instructions). ~Jhenever an error occurs in a function, we determine if the error is caused by the wrong function being applied to a set of arguments or the correct funct1.on being applied t<? the wrong set of arguments. Our approach is f1.rst to attempt to correct the function. Next, an attempt is made to correct the arguments. \Jhen correcting arguonents, we know the accumulators which must contain the aq~uments and thus we can 1mrk backwards to determ1.ne where and when the wrong values were computed and loaded into the accumulators. Often t~e debugging process is aided by the presence of 1.nst rue t ions that manipulate data that will no longer be referenced in the program. Such instructions often serve as candidates for removal and replacement by the ~orrect.instruction. Errors also occur frequently 1n test .Lng the wrong sense of a condition. This is especially common with arithmetic relations such as less than and greater than. Such occurrences are signaled by the presence of errors in both subtrees of a condition in close proximity (in terms of the losical flow of the prosram) to the instruction at wh1.ch the condition 1.s tested. This can be corrected in the following manner. Reverse the sense of the test. If all of the errors disappear then the diasnosis is clearly correct. If some of t~e errors d1.sappear, then the diagnosis is guite l1.kely to be valid. The previous is espec1.ally true if at least one error in each subtree disappears after making the change. Note that changing the sense of the test may lead to new errors. However, as long as some of the current errors disappear, the correction is likely to be valid.

The above heuristics ~~ere used in a manual process to debug the erroneous program. We believe that many of these errors could be corrected automatically. However, there is a need to ~onti~ue exercising the proof system with erroneous encod1.ngs to determine if any more error correction heuristics can be discovered.

[Samet75] - Samet, H., "Automatically Proving the Correctness of Translations Involving Optimized Code," Ph.D. Thesis, Stanford Artificial Intelligence Project Memo AIM-259 1 Computer Science Department, Stanford University, 1975.

[Samet76] - Samet, H., "Compiler Testing Via Symbolic Interpretation 1 " troceed!n~s of the ACH 2~th Annual Conference, 197 , pp. 9 -497.

[Samet77a) - Samet, H., "A Study in Automatic Debugging of Compilers," TR-545, Computer Science Department, University of ~~ryland, College Park, ~1aryland, 1977.

[Samet77b] Samet, H., "A Normal Form for Compiler Testing," b:Qceedini'S of the SIGART-S IQPLAN ~ymposium on ArtiHHal Intelligence and rogramming Languages, ·