当前位置:文档下载 > 所有分类 > Semantics of program representation graphs
免费下载此文档

Semantics of program representation graphs

Program representation graphs are a recently introduced intermediate representation form for programs. In this paper, we develop a mathematical semantics for these graphs by interpreting them as data-flow graphs. We also study the relation between this sem

SEMANTICSOFPROGRAMREPRESENTATIONGRAPHSG.RAMALINGAMandTHOMASREPS

UniversityofWisconsin Madison

Programrepresentationgraphsarearecentlyintroducedintermediaterepresentationformforprograms.Inthispaper,wedevelopamathematicalsemanticsforthesegraphsbyinterpretingthemasdata- owgraphs.Wealsostudytherelationbetweenthissemanticsandthestandardoperationalsemanticsofprograms.Weshowthatthesemanticsoftheprogramrepresentationgraphsismorede nedthantheprogramsemanticsandthatforstatesonwhichaprogramter-minatesnormally,thePRGsemanticsisidenticaltotheprogramsemantics.

CRCategoriesandSubjectDescriptors:D.3.4[ProgrammingLanguages]:Processors-compilers,interpreters,optimization;E.1[DataStructures]graphs

GeneralTerms:Theory

AdditionalKeyWordsandPhrases:controldependence, owdependence,programdependencegraph,programrepresentationgraph,semantics

1.INTRODUCTION

Inthispaper,wedevelopamathematicalsemanticsforprogramrepresentationgraphs(PRGs)andstudyitsrelationtothestandard(operational)semanticsofprograms.Programrepresentationgraphsareaninter-mediaterepresentationofprograms,introducedbyYangetal.[Yang89]inanalgorithmfordetectingpro-gramcomponentsthatexhibitidenticalexecutionbehaviours.Theycombinefeaturesofstatic-single-assignmentforms(SSAforms)[Shap70,Alpe88,Cytr89,Rose88]andprogramdependencegraphs(PDGs)

[Kuck81,Ferr87,Horw89].Theyhavealsobeenusedinanewalgorithmformergingprogramvariants[Yang89a].

Programdependencegraphshavebeenusedasanintermediateprogramrepresentationinvariousappli-cationssuchasvectorization,parallelization[Kuck81],andmergingprogramvariants[Horw89].Horwitzetal.[Horw88]werethe rsttoaddressthequestionofwhetherPDGswere“adequate”asprogramrepresentations.Theyshowed(forasimpli edprogramminglanguage)thatiftheprogramdependencegraphsoftwoprogramsareisomorphic,theprogramsareequivalentinthefollowingsense:foranyinitialstateσ,eitherbothprogramsdivergeorbothhaltwiththesame nalstate.

ThisworkwassupportedinpartbyaDavidandLucilePackardFellowshipforScienceandEngineering,bytheNationalScienceFoundationundergrantDCR-8552602,bytheDefenseAdvancedResearchProjectsAgency,monitoredbytheOf ceofNavalResearchundercontractN00014-88-K-0590,aswellasbygrantsfromIBM,DEC,andXerox.

Authors’address:ComputerSciencesDepartment,UniversityofWisconsin Madison,1210W.DaytonSt.,Madison,WI53706.Copyright©1989byG.RamalingamandThomasW.Reps.Allrightsreserved.

第1页

免费下载Word文档免费下载:Semantics of program representation graphs

(下载1-23页,共23页)

我要评论

返回顶部