Type Analysis and Type-test Elimination in Oberon-2

The Language

W e consider an Oberon e programming language called SimpleOberonhic h omits complex data structures arrayslik or multilelv pointer structures but is complex enough to demonstrate the essential features of the approach The syntax of SimpleOberon is essentially given by the contextfree e grammar of Figure Central is the concept of Wirth type-extension whic h allows a programmer to create a new recordype by adding to an existingrecordype as illustratedin Figure In the example rt0 isthe basis-type ofrt1 and rt2 and frt0 rt1 rt2 rt3g isthesetofallextension types of rt0 Note thatevery type isan extensionype of itselfEach recordype correspondswitha pointer ype The static type ofa pointervariableisthe type ofits declaration itsdynamic type is runtime dependent and is an extensionypet of the static type Classesin object ted languagesdo not onlycontainthe data but alsothe methods formanipulatingthem In SimpleOberon thisisre in thatprocedures can be bound to recordypest A procedure bound to a recordype is also accessible in all its extensionypes unlessit isverwrittenForo example pv.P() representsa call of the particularypeound procedureP which isbound to thedynamic type ofthe pointer variablepv Conventions. As usualwe assume thatinheritanceisremoved from theargument pro gram which can be achieved by expandingallrecordype de by addingallin herited components except forypeoundt procedures being verwrittenWo e introduce a special recordype rtNIL correspondingtothecommon pointer ype ptNIL type of theNIL object Every recordype rt is an extensionypet ofrtNILnd ev ery typeound procedureP gets an equally y implemen tation bound tortNIL Statements containing aypet assertion are splitto twoin partsthe type assertion and the term with out theassertionFinallyfor typeound procedures and typeound procedure calls ew add thereceiverparameter asan ordinary parameter to theparameter list Goal of Type Analysis. The goaloftype analysisforSimpleOberonprogramsisto compute foreveryoccurrenceofa pointervariablethesetofdynamic types which can actuallyoccuratruntimeas preciselyas possibleCentralforaccomplishingthisisthe e of elemen tary statements on the ypet of a ariableThisv is summarized in Figure

Framework of Abstract Interpretation

Abstract interpretation has proved to be a powerful and theoreticallyl wframe work forstaticprogram analysis In thisarticlewe use the framework de velopedby Knoop and Ste and itsobject ted extensionby Knoop and Schreibergiven in and W e represent SimpleOberon by means of directededgeeled  ow graphs G 0 k where everyG i representsan ordinaryor typeound procedure main program is considereda parameterlessprocedure The systemG fG 0 kg iscalled program model The edgesofG represent both the statementsand thecontrol w of the under lying procedures while the nodes represent justprogram points Figure The functioncallee maps every edge represent in ga procedurecall tothesetofproceduresit may invoke Fortheobject tedsettingwe have ife representsan ordinary procedure callee e yields the singleton settaincon ingthisprocedure Ifitrepresentsa typeound procedurecallcallee e yieldsthe set ofallprocedureswhich arepossiblycalledat runtime i thesetofallequally proceduresbound to some extensionype ofthe staticype of the pointervariableat the callsiteor to rtNIL Dually the functioncaller yieldsthe setofallcallsitesofa procedureG i A program model G doesnot explicitlyrepresent thecontrol w caused by procedure callsTherefore we additionally considerinterproceduralthe program model G ofGhic h resultsfrom G by replacing eryedgeve E C by call edges leading from source eo the start node of every procedure ofcallee e and b y return edges connecting theend no des of the seprocedureswithdest e These edgesarelabeledy assignmentsre theparameter transfer
Abstract Semantics. The idea of abstractterpretationin is to replace the seman ticsofa program by a simplerabstractversionwhich istailored todealwitha speci problem The abstract seman tics isypicallyt inducedy ablocal abstract semantics 0 E C C which givesabstractmeaning toeveryedgeoftheinterprocedural program modelG in terms of a transformation on a complete latticeCuv Its elements are assumed to represent the data w information of terestFundamenin tal for
dealing with locariablesv of recursivprocedures is thetroductionin ofstacks of lattice elements and ofreturn functions R e C C C e E R s in Intuitivelyabstract stacks model the ordinary runtime stacks the return functions the e of returning from a procedurecallwhich requiresto maintainthe e on globalvariablesbut to reset thee on local ones
The global abstract semantics of a program results from one of thewingfollotwo glob alizationapproaches the erational meet over all paths approach and the maximal xed point
approach The MOP approach leadsto the MOP solutionand globalizeslocalabstractsemanticsby directlymimicingpossible program executionsit tersectsallinformationwhich belongto a program
pathreaching theprogram point underconsiderationThe MOP solution doesnot spec ify an e e computation procedurein generalThe MFP approach leads tothe MFP solutionin the senseofKam and Ullman Thisapproach inducesan iterativ computationprocedurewhich ise e ifthe functionlatticeon C satis the de scendinghainc condition and if the local semantic functionse 0 e E and the return functionsR e e E R aremonotonic In thissettingthe speci ofa data w analysis algorithm requires only fourtaryelemencomponents the data domain thelocal abstractsemanticsthereturnfunctional andthestart information ofterestin Correctness and Coincidence. The following theoremsgive su t conditionsfor thecorrectness safety and the coincidence precisionoftheMFP solutionwith respecto theMOP solutionAlong thelines of w e get
Theorem 3.1 (Correctness Theorem) The MFP solution is a correct approximation of the MOP solution, i. e., c C n N MFP 0 0) n v MOP 0 0) n , if the 0 ([[ ]] ([[ ]]  functions e 0, e E , and R e , e E R , are all monotonic.
Theorem 3.2 (Coincidence Theorem) The MFP solution and the MOP solution co- incide, i. e., c C n N MFP 0 0) n MOP ([[ ]] 0 0) n , if the functions e 0, 0 ([[ ]]  e E , and R e , e E R , are all distributive.

Type Analysis

Resolving the Interplay of Pointer Variables and Type-bound Procedures Central forypet analysis of Oberon e programs is to resolvthe complex interplay of pointer variables andypeoundt procedures the dynamic ypest of pointer variables and the procedures calledytypeoundb procedure calls depend utuallym on each other Like in and we resolvtheseinterdependenciesby decomposingtheanalysisinto two components dealing with the computation of dynamicypesoft pointer variables and the computation of potentially called proceduresBoth steps are repeatedtilun a com mon poin t is reached i both the sets delivered by and are in variant under furtherapplicationsofthe component analyses Both componentsrelyon information computed by theother Fortunatelythis t deadlock can be resolved by means ofthefunctioncallee Based on thestaticype declarations theprogramof it providesa safeapproximation of thesetsof potentially called proceduresThisinforma tion is initially tofedthein ypet analysis of step returning an approximation of the sets of dynamic ypesoft pointer variables accordingthisto informationViceversa thetype informationon pointervariablesinducesnow an improved approximationofthesetsof potentiallycalledproceduresThe repetitionstops ifthe new approximationprovided by step coincideswiththeformer one..