Integration of generic program analysis tools into a software development environment

EricaGlynn

IanHayes

AnthonyMacDonald

SchoolofInformationTechnologyandElectricalEngineering

UniversityofQueenslandemail:erica@itee.uq.edu.au

Abstract

Supportandanalysismaintenanceforprogramtasksunderstandingcanbefacilitatedindevelopmentbyprogramanalysistechniques.Bothcontrol-flowanddata-flowmentingcantionorthatthesupportmayprogramprogrameitherbetextdisplayedwithcomprehensionadditionalbyaug-withtheinforma-programprogram,usedtogramThispapere.g.,allowfrommoresophisticatednavigationoftheoutlinesanidentifier’stheusetoitsdefinition.softwareanalysissupporttoaadditiongeneric,language-based,ofgenericpro-toolsdependentaredevelopmentimplementedenvironment.intwophases:Theaanalysisalanguage-independentprogram,phasesuchthatasextractsitsbasicinformationlanguage-fromphisticatedphasecontrolthatperformsflowgraph;andaseparationanalysisofthebasicinformation.amoreThisso-generatedforallowsanewprogramlanguage.analysistoolstobeeasily1

Introduction

Programquiringgram.knowledgecomprehensionaboutisathecomputerprocessofpro-ac-activitiesIncreasedreuse,asknowledgeenablessuchareprocess,underwayanddocumentation.bugcorrection,enhancement,toWhileeffortsedgetodayandsuchanalyticalsignificantautomatepoweramountstheunderstandingarerequiredofknowl-thatmanualprogramcomprehensionislargelya–Rugabertask.

(1995)

control-flowTheuseofprogramanalysistechniques,includingtified(Hechtassupportinganddata-flowsoftwareanalysis,hasbeeniden-and1977).Programanalysiscomprehensiontoolscanreducetaskstimeprocessresourcescreasebysupportingrequiredcomprehensionthroughouttheanddevelopmentthusnavigationthecostsableofinvolved.Forexampleenablinguserde-bothallowsathesoftwaredefinition-usedeveloperrelationshipforavari-quirementsThetypeStonemanandusageinformationtoforquicklythevariable.discovervironmentsspecification(Howdenforsoftware1982,Buxtondevelopment1980)re-avironment.necessarydescribespartstaticprogramanalysistoolsen-assistoolsprovideInthisofasupportcontext,minimaltodevelopersstaticlanguageprogramsupporten-byassisting

analy-Copyright󰀁

c2005,AustralianComputerSociety,Inc.Thispa-perappearedatTwenty-EighthAustralasianComputerScienceConference(ACSC2005),Newcastle,Australia.ConferencesinResearchandPracticeinInformationTechnology,Vol.38.VladimirEstivill-Castro,Ed.Reproductionforacademic,not-forprofitpurposespermittedprovidedthistextisincluded.

withtrytemporarysurvey,program-understandingconductedbytheauthors,tasks.Aevaluatedrecentindus-thesupportrequirementssoftwaredefineddevelopmentbyStoneman,environmentsfindingusingcon-thatofprovidedintegratedforprogramstaticflowunderstandinganalysistoolsthroughtheusevelopmentwithinmodern,commercial,isintegratedstillnotwellde-fromSoftwareenvironments.

texteditorsdevelopmentusedinconjunctionenvironmentswithcancommandrangelineenvironmentscompilerstopresentationprojectandgivingenhancedintegratedlanguage-basedincrementalin-linecontextsensitivehelp,environmentthegeneric,compilation.Inthisman,UQ󰀁(Jarrottintegrated,softwaredevelopmentWelshCarrington,support2001)wasextendedCook,Coyle,&MacDonaldwithJones,flowanalysisMacDonald2003,Tole-toolsto&inAlgorithmsprogramforunderstandingflowtasks.

application,theliterature(Muchnickanalysis1997).areHoweverwellrepresentedforoursentedplex,bytheseitwasresourcesfoundwerethatatthetechniquespre-ablethewithintightlycoupledtoothertechniquestimesandoverlynotcom-suit-representations.useofintermediateaprogramunderstandingandlowlevelcontextduetotechniquesoperationforflowAccordingly,analysiswasthemodificationmachinerequiredofcodetheofanintegrated,onsourcecodeartefactswithinthetocontextenablesisTooftoolsreduceforthegenericcostsofdevelopmentprovidingprogramenvironment.analy-ysisprogramsmultiplewrittenlanguages,inmultipleandlanguages,toallowtheanalysisthependentdesigntoolsshouldofbegeneric.Bygenericwemean,anal-thoseofthetheparticularanalysislanguagetoolsshouldasbeasinde-shouldcomponentsthebegeneratedthatfromaredependentonpossible,thelanguageandagelanguage.ahigh-leveldescriptionofprogrammingparadigmsIntegratedtool-setsallowcommonus-languages.languagesforsoftwareanddevelopersthetoolsusedacrossforvariousthoseutilisationopmentofProvidingtoolsisaadequatemajorgoalsupportofforefficientsoftwareenvironmentgrateddevelopmentresearchenvironment(Reissprovides1990).softwareAndevel-anidealsoftwaresetoftoolsforusethroughoutallstagesofinte-theintegrationlifedevelopmentofcycleprogram(Howdenanalysis1982,toolsReissinto1990).Thelevelingofsupportenvironmentsfordevelopmentwillbringengineersaboutsoftwareundertak-ahighercontrol-flowGenericityprogram-understandingflowanalysis.createstasks.

Inasignificantproblemforneedanalysis,thecontrolconstructsordertoperformoftheprogramcontrol-guagetoofbeCookidentifiable.et.al.(2002)Theattributewasusedgrammartodefinelan-thelanguage-specificducesIntheprogramremainderaspectsoftheanalysistools.

analysisofandthisthepaper,conceptsSectionthat2impact

intro-ontechniquestheabilityAintotoaintegrateprogrammingexistingprogramanalysismentbrief3.(UQoverview󰀁oftheprogrammingsupportsupportenvironment.environ-tegratingSectionaanalysis,4)discussesusedinthisprojectisgiveninSectionparticularlythedesigngenericchoicesanalysis,madeinintoin-aspectssoftwareofthedevelopmenttwophasesenvironment.ofthetoolsThedevelopedtechnicalarediscussedsummaryinSections5and6.Thepaperclosesfuturework.oftheoutcomesofthisworkandpotentialwitha2

Programanalysis

Control-flowturesanalysisisthestudyofthecontrolstruc-codeure(Wirth1.toofaInaprogram.thiscontrol-flowTheexample,graphtransformationofsourceaprogramisillustratedwrittenininFig-theto(asaderivation1976)isprogram,cyclesofundergoingcontrol-flowanalysis.InadditionPL0tointhegraphgraphscancorrespondingbeidentifiedgraphsdescribedcangramthenalongbeusedwithinMuchnickasinformation(1997)).thebasisforidentifyingThecontrol-flowmoreadvancedtheircyclespro-sis.

analysistechniques,includingdata-flowanaly-Unconditionalvar a : integer; A:read xbegin

Uncond.read x;

B: b := 0b := 0;Uncond.if x < 0 then

C:x < 0a := b + 1;Trueelse

D:a := b + 1a := b + 2;

Falsewrite a E:a := b + 2end .

Uncond.

Uncond. F:write aUncond.Figure1:Exampleprogramandcontrol-flowgraphniquesData-flowanalysisrepresentsasuiteoftech-ues.use.Onethatformstudyofdata-flowhowaprogramanalysisisusesmodification-dataval-mappingsModification-usementfromrelationsarethepoint-to-pointfiedmappings,itsorvalue.setoftheuseofanidentifiertothestate-Bystatementschainingthattogetherpotentiallythepoint-to-pointlastmodi-staticallygivendeterminingmodification-usethedatacanprovidedependenciesameansforofmappingsvariable.increatedFigureforthe2programshowsthemodification-useafromthediagramareboththepoint-to-pointofFigure1.mappingsVisibleaatchainidentifiersB).ofsuch(e.g.,mappingsx)to(e.g.,modifyingaatFstatements,dependsonandb3

Softwaredevelopmentenvironments

Workducedatronment,anTheexperimentalUniversityofQueenslandhaspro-&UQ󰀁(Tolemansoftwareetal.2001,developmentWelsh,Broomenvi-tiesKiongturesforcapturing1991),whichandisdistinguishedbyitsfacili-forgrammaticdisplayingwithinandmanipulatingrelationalstruc-formthesebetweensoftwaredocuments,and(Jonesstructures&Welshin1997,textualJarrottordia-&

var a : integer;begin

A:read x; B:b := 0; C:if x < 0 then D:

a := b + 1;else E:a := b + 2; F:

write aend .Figure2:Examplemodification-usechainMacDonaldinandthiscontext2003).Softwaredocuments(Welsh1994)ronmentrelations.UQconsist󰀁isaofgenericbothabstractlanguage-basedsyntaxtreesenvi-scriptionsinlanguage-specificofthat,thelanguages,whenprovideditprovideswithappropriateitsde-finesusedtheEnvironmentsupport.DescriptionTolemanLanguageet.al.users(2001)with(EDL)de-supportstodescribemechanismsUQ󰀁’slanguagesmulti-lingualandnaturepresentations.andprovidesEDLguages,relations,fordefiningandsemantictextualtools.

andgraphicallan-User−interactiveNon−user−interactive

Constructive

Constructive

Tool

Tool

DocumentServer

User−interactiveNon−user−interactiveNon−constructive

Non−constructive

Tool

ToolFigure3:UQ󰀁architecture

tralThetionaldocumentUQ󰀁architectureserverisshowninFigure3.Acen-(MacDonaldstructuresmanagesthesyntacticandrela-&Welshandensures1999).

theirpersistentstorageRelation

RelationTupleAbstractSyntaxTreeAbstractSyntaxTreeFigure4:UQ󰀁syntacticstructures

syntaxSyntactictionstrees.structuresTheseareareaugmentedrepresentedwithasn-aryabstractrela-between(astionalelementsshownininFiguretheabstract4)torepresentsyntaxconnectionswithinelementsmericabstractsyntaxcanbetrees,abstracttree.Rela-relations,syntaxtrees,nodesandUQbi-directional;data.Ingeneral,stringsornu-henceUQ󰀁relationsareN-arydatabases.

󰀁relationsismoreakinthetothatunderlyingusedinrelationalmodelofcessibleThedocumentThesetoacollectionserveroftoolsmakes(Welshthese&structuresYang1994).ac-ortheynottoolstheyinteractcanbecategorisedwiththeuser,dependingandwhetheronwhetherorlanguage-basedconstructsyntacticandrelationalstructures.notAandactiveconstructiveeditorisanexampleofaninteractiveandnon-constructivetool(Cooktools&Welshareless2001).common,Inter-butment,anexampleisaviewback-endoforaanon-editableread-onlyview,suchpreviewasaofcall-graphadocu-linkingwithsyntactictoolprogram.thatAstaticsemanticanalyserisaconstructsgeneratesofrelationalitsinformationpleaoferroranon-interactive,messagesandconstructiveisthusconsideredinputdocumenttool.Exportinganexam-fallspretty-printedversionofadocumenttopostscriptconstructivewithinthetools.

categoryofnon-interactiveandnon-portAlationenvironmentrecentadditionisthetoautomatictheUQ󰀁programmingspecificationofsup-re-(Cook,buildingtoolsviatheuseofameta-languageingWelsh&Hayes2002)extendingtheexist-languageenvironment1968)initioninwhichconsistsdescriptionattributesofanattributelanguage.Themeta-maybegrammar(Knuthguagecomplexsyntaxofrelationalandrecursionattributestousesrelations.implementaProlog-likeThedef-potentiallylan-atedandandabstractinthisabstractmannersyntaxcanbothtreetraversals.useexistingToolsrelationscre-inotherabstractcomponents.syntaxsyntaxtreestreestoandtheprovidesystemnewforutilisationrelations4

Design

Inflowthisguageanalysisresearch,inaamannersystemaswasindependentdevelopedtoconductpaperbeingthelanguagefocusesanalysedPL0ontheas(Wirthflowpossible.1976).analysesForofthelan-Twoassimplicity,thisUQthey󰀁tools,applythetoGraphtionBuilder(Section5)ofasSection6)were3,developed.andtheAnalysistool(Sec-bothofUsingthetoolclassifications(storednon-interactivecollaborationintheUQ󰀁andtheseconstructive.toolscanThebeusecategorisedofglobalmakingusetheresultsbetweendocumentofthetheflowtwoserver)tools,relationsinadditionallowstoBuilder.ThebyotherfirstofUQthe󰀁analysesavailablefortoolstools.

isthelanguage-specificEDLTheattributeTheGraphgrammarBuilderlanguageiswritten(CookusingGraphetal.UQ󰀁’sthearelationsmaintaskwhichofthedefineGraphtheBuildercontrol-flowistopopulate2002).graphtractsprogram.Theattributegrammaradditionallyex-ofsyntaxlanguage-specificstract(neededforpresentationinformationsuchasconcretenon-terminalssyntax(forvariables)canlanguageofresults)andab-modifyand/orsemanticsusesuchaswhichysisneededforuseinthesecondtool,thethevaluesAnal-ofindependentThetool.

secondofrelationscall-graphs,populatedAnalysisbytool.thetheThetoolsisthelanguage-GraphAnalysistoolusesthetheconductdata-flowanalysisBuilder(todeterminetocreatesultsmodification-useeffortofrelationships)andpresentthere-languagesrequiredbothformstosetofupflowflowanalysisanalysistotheforadditionaluser.Thethehasbeenminimisedbymakingasmuchofditionally,systemrectlytheaslanguage-independentaspossible.Ad-thedata-flowresponsibledesireanalysisforforinthelanguage-independenceisdi-thedecisionnottoimplementintegratedThetoolsdevelopmentweredevelopedEDLenvironment.forattributetheUQgrammar.From󰀁generic,anin-

tegratedimportantdevelopmentoncludesthesystemthatenvironmentperspective,itisthatthetoolstheyplacearetominimalworkwith.requirementsThisin-UQbe󰀁.Thisconformingrequirementtoexistingdictatedusagethattheparadigmstoolswouldforthegenericmentdesireandincrementalwherepossible.ItwasthattomotivatedworkwithinthethecreationexistingoftheUQ󰀁twoenviron-phaseapproach.independent,Byre-definitionimised.forthemakingamounttheAnalysistoollanguage-eachofthesystemthatrequiresciplesadditionaltoHadcomputeatoolthebeensubsequentlanguageismin-flowdevelopedfromfirstprin-developmentlanguagejustand/orwouldanalysisforPL0only,eachportingrequireofthethecompletere-Graphtheattributegrammarofthetool,language-specificratherthaningPlacingBuilder.

minimalrequirementsonthesystemguageintegratedoptimal.definitions,withevenalsowhereincludessuchusingdefinitionsexistingbe-aresub-lan-opedantworksForwithexample,thePL0the(Wirthflow1976)analysislanguagetooldevel-vari-mardefinedingusedforforPL0useininUQUQ󰀁.Unfortunatelythegram-proach.data-flowwhichRatheranalysis,󰀁isnotoptimalforconduct-thanrequireespeciallyusingagenericap-velopedcouldwasforthepotentiallyPL0language,impactchangesonexistingtothegrammar,toolsde-worktowithdevelopexistingmethodslanguagethatdesigns.weretheflexibledirectionenoughchosento5

GraphBuilder

ItcreationistheaandGraphpopulationBuilderofthattheisresponsibleforthetoolprogram’scontrol-flowgraph.relationsTheGraphrepresentingBuilderguagewasdefinedusinganattributegrammarlan-ecutable(Cookpiler.Thisbinaryetlanguage-specific(viaal.2002)C++code)andcompiledtoolusingisdesignedtheintoEDLanex-tocom-op-eratetoincrementallytoextractallinformationneededconductedenablecontrol-flowanddata-flowanalysistobetheinteractsAnalysisinatoollanguage-independent(Sectionmannerwithinnon-interactivewithinlationscontext,theUQ󰀁6).TheGraphBuildercreatingsystemandinapopulatingconstructive,toolsdocumentexceptbutnotthroughinteractingtheinterfaceswiththeuserre-providedoranyotherusedThegramtorelationsserver.

bythemodelthecreatedcontrol-flowbythegraphGraphBuilderareuseinasthewelllanguage-independentasextractotherinformationofarequiredgivenpro-forclassesWithinflowofrelations:theGraphthoseBuilderAnalysisoccurringtoolonlytheretool.

withinaretwothetributeanalysisBuilderrelations,attributeandthosegrammar,populatedknownbyaslocaltheGraphorat-system,knowntool,availableasglobalforordocumentusethroughoutserverrelations.theUQ󰀁5.1

Control-flowGraph

Wetions:representgraph,GraphEntryacontrol-flowformodellinggraphtheviarootthreeofrela-GraphExitGraphTransfortheinternalflowedges,andtheAsrepresentingthefinalnodesinthegraph.lationsshownthatinFigureprovide5,theitiscompletethecombinationcontrol-flowofthesere-lationsFigureBuilderthat5resultrepresentsfromthetheUQcalculations󰀁documentoftheservergraph.re-flowlations.graphtool.isTheundertakencalculationusingoftwoaprogram’sGraphlevelsofcontrol-grammarTherelationsfirstlevelwhich,areviatheUQ󰀁re-asynthesizedbottom-upattributeprocess,

constructstracttheflowgraphoftheprogramfromitsab-arepopulateinternalsyntaxtotree.theTheattributegrammarrelationstoelstheGraphthesecondGraphBuildertool,andareusedtorelations.levelTheofrelationsrelationscorrespondingatprocessinghavebeenkeptstructurallyequivalenttobothsimplifylev-guishedviawithintheirthenames.tool,Forhoweverexample,theytheareGraph-distin-Transserverrelation,edgesrelationdescribedresponsiblenext,forismaintainingtheUQ󰀁documenttheflowlationofwhichisacontrol-flowgraph.TheGraphTransre-internalisstructurallytousedtheduringequivalentGraphthetothetransrelationBuildercalculationtool.

processandisUncond.GraphEntry A:read xUncond. B: b := 0Uncond. C:x < 0TrueGraphTrans D:a := b + 1False

E:a := b + 2Uncond.Uncond. F:write aUncond.GraphExitFigure5:Control-flowgraphrelations

edgesTheGraphTransrelationrepresentscomponentofthecontrol-flowgraph.Itisthefundamentaltheinternal3-tuplecessorwithintheoftheGraphBuilder’sfinaloutput.EachanGraphTranslabellededge.relatesInEDL,anodeGraphTranstoitssuc-isdeclaredas:

RelationGraphTrans(Node,Label,Node).Withinsiblethecurrentconfigurationtherearethreebeedgestaken,edgelabels:Unconditionalforedgesthatmustpos-indefinedif,fromandwhilebranchingTrueandandrepeatconstructsFalserepresentingconditionalstatements.suchasthosefoundingtoallowextensionsforunrestrictedThelabelsbranch-wereandincludingpresentsarbitraryanexamplejumpingmultipleof(branchinglabelledgoto)statements.casestatements,arcs.

Figure5tentsUsingoftheofthesampleprogramofFigure1,thecon-GraphtheGraphTransBuilderarerelationdisplayedafterinTabletheinvocation1.

NodeLabelNode(from)(to)AUnconditionalBBUnconditionalCCTrueDCFalse

EDUnconditionalFE

Unconditional

F

Tablegram.

1:GraphTransrelationfortheexamplepro-TheGraphExitrelationstoresthenodesfortheend(s)ofacontrol-flowgraph,andisdefinedas:

relationGraphExit(Node,Label).

Tableforthe2programshowstheofcontentsFigure1.

oftheGraphExitrelationNodeLabel

F

Unconditional

Table2:GraphExitrelationfortheexampleprogram.points,Acontrol-flowpointlast(i.e.,statement(anorexitaconditionalgraphonexitmaypoint.possessAconditionalmultipleexitexitofTrueaprogramorFalseis)anmayiterativeoccurwhereconstructtheendsaFigurewithwhileawhileloop).loopForwillexample,haveanaprogramwhichditional6forthisprogramexit;showstheanexampleofaprogramexitwithonaFalsecon-.arecontentsshownofintheTableGraphExit3.

relationUncond.var x : integer; C1:read xbegin

Uncond.read x;

C2:x > 0while x > 0 do

TrueUncond.x := x - 1

C3:x := x - 1end .

FalseFigure6:Programwithaconditionalexit

NodeLabelC2

False

Tableconditional3:GraphExitexit.

relationfortheprogramwithationalMultiplegram/procedure,statementexitsismayoccurwhereacondi-whereandthelaststatementofapro-ments.atwoFiguremethodinlanguagessuchasJava,7providescanhavemultiplereturnstate-GraphExitexitpoints.relationTableanexampleofprogramwithforthis4showsexample.

thecontentsoftheUncond.var x : integer; E1:read xbegin

Uncond.read x;

E2: b := 0b := 0;Uncond.if x < 0 then

E3:x < 0write bTrueelse

E4:write bUncond.write x

Falseend .

E5:write xUncond.Figure7:ProgramwithmultipleexitsTheGraphEntryrelationisdefinedasrelationGraphEntry(Label,Node)

Itgraph.holdsthenodeforthebeginningoftions,theAstupleswiththeoftheGraphTransGraphEntryandrelationGraphExitacontrol-flowrepresent

rela-NodeLabel

E4UnconditionalE5Unconditional

Tablemultiple4:exits.

GraphExitrelationfortheprogramwitharelations,labellededge,Theeachhoweverunliketheothercontrol-flownecessaryGraphEntryflowlabelgraphmaypossessesseemredundant,onlyonebutentry.(e.g.,ofcasetostatements).supportmultiple-branchingitisTable5showsstatementsoftheFigureGraphEntry1.

relationfortheexamplethecontentsprogramLabel

NodeUnconditional

A

Tablegram.5:GraphEntryrelationfortheexamplepro-5.1.1

Procedures

TherelationsGraphmaincorrespondingBuildermaintainstotwosetsofcontrol-flow

TransProcExit)bodyandits(GraphEntryprocedures,collections(GraphProcEntryGraphExitforandaprogram’s,Graph-analysesandGraphProcTrans).Inter-proceduralGraph-syntaxtroducetrees,arecomplicatedandbyprocedurebyanalysingparameters,acrosswhichabstractableplicatedscopethe(Tippossibility1995).Staticofvariableanalysisaliasing,isfurtherandcom-vari-in-rationThesebyissuesrecursion.

providedthemotivationdecidedintotwosetsofrelations.Furthermore,fortheitsepa-wasandalgorithmmainthatmethodbymakingcouldberelationsthestructureusedinthesimilar,oftheprocedureAnalysisasingletooltraversal(Section6).

ExitInrequiresandadditionGraphProcTranstotheGraphProcEntryrelations,the,AnalysisGraphProc-toolcedurenodesconstructionoftoaitstherelationsubgraph.nodesmappingrepresentingthenameofeachpro-Thisinformationtheentryisusedandexittionusedofdata-flowofcall-graphs,analysisandduringtheapplica-intheholdthiswithininformationaprocedure.toistheThegloballyGraphProcMaprelationscopeddeclaredvariablesrelation:torelationGraphProcMap(String,Node,Node).Itsdure,parametersdureanditsentrycorrespondandtothenameoftheproce-includedpossessesmorethanexitonenodes.exitnode,Whereanaproce-systemforeachdistinctexit.ItisaconstrainttupleoftheisProcMapthatGraphProcExitmusttheexistentryrelations.withinandexittheGraphProcEntrynodeswithinGraph-and5.2

RelationPopulation

ThepilationGraphBuildertoolisgeneratedfinestaxusedforanoftheGraphBuilder.edlfile.fromThisthefilecom-de-populatingattributegrammar,relationtuples.withaThisProlog-likegrammarsyn-isandysisidentifytocalculatewrittenwhichissemanticthecontrol-flowspecifictoinformationgraphofaprogram,thelanguagefordata-flowtheprogramanal-isspecificysissysteminformation,in.AstheEDLthatrequiresitisfileprovidesthelanguage-definitiontheportionforofeachtheadditional

flowanal-language.finenon-terminal,theinheritedTheEDLfileprovidesphylumswhichde-tributesandandthesynthesisedrulesthatspecifyattributeshowforeachrequireguage,everyathatareevaluated.ThesemanticsofthetheEDLat-phylumforeverymustnon-terminalbedefinedinalan-guage’salternativeEBNFdeclarationontheright-handdeclared.Additionally,aruleissidedefinedofthewhichlan-forpopulatesphylumtheattributesdeclaredthedeclaration.Figure8providesinthetheexampleassociatedofdefinedStatementinTolemannon-terminaletal.(2001).

fromthePL0languageStatement=ReadStatement|IfStatement|....

(a)LanguageEDL

phylum{

Statementattributes:

relationrelationentryexit(Label,(Node,Label)Node)..

defaults:relationtrans(Node,Label,Node).}

...rule{Statement...}=ReadStatementrule{Statement...}=IfStatement...

(b)AttributegrammarEDL

FigureStatement

8:Language,phylumandruledefinitionfortheTheandcontrol-flowattributesgraphofanASTnodeusedtocalculateglobalexit.Theserelationsarehavetherelationsthesameentrytype,astransthetions.

GraphEntry,GraphTransandGraphExitrela-tiveTwostructured(oratomicclassesativeconstructssuch)ofconstructscanbeidentified:primi-assuchincludingstatementasanassignmentiflists,andbranchingstatement,andwhilestatements.anditer-Itflowisthestructuredstatementsthatdefinethecontrol-noPrimitivegraphofaprogram.

Forcontrol-flowconstructsstructure.

example,atransitionsarecondition(e.g.,(ancharacterisedemptyx<0transby)isanrelation).havingatomicrule{

Condition=Expthis->entry(UNCOND,this->exit(this,this).this->trans/*=UNCOND).Relations::UseTokens(\"PL0\explainedinempty.

Section5.3*/

\"Condition\

}

\"Ident\").

Figurestruct.

9:SpecificationforConditionprimitivecon-ConditionFigurein.9FromisthetheEDLentryruleandexitspecificationrelationsforainthetributeFigureConditionrule,therulefortheIfStatementdefinedtupleofthe10canIfStatementassertthatnodethe(“entrythis”)relationincludesat-aofentry(UNCOND,n)whenevertheentryrelationentrytheentryrelationConditionofnodeincludessuchatuple,i.e.,theasinglerelationtuple.ofThethethesyntaxConditionIfStatementforanode,nodeclausewhichincludestheoftheonlyform

hasforall(Nodethis->entry(UNCOND,n)

n)

:-Condition->entry(UNCOND,n)

isventionProlog-like.thatallHowever,uppercaseinsteadidentifiersofusingareProlog’simplicitlycon-universallyconstants,quantifiedandlowercaseidentifiersarevariablestificationaretheexplicitlynotationquantified.usediscaseTheinsensitiveexplicitandcausetionthisalsoisthespecifiesthetypeofthevariable.quan-Be-plefortheIfStatementonlyclausenode,definingthistheistheentryrela-withcontainedclauses:thedefinitionintherelation.Thiscanbecomparedonlytu-thethefirstspecifyingofexitrelationthatthewhichexitrequiresrelationtwothetainsStatementIfStatementnodenodes1,containsandtheexitrelationofoflabelstheexitrelationofs2.Forthethesecondthatitcon-ditionalmaybeeitherunconditional(exitUNCONDrelation)orcon-thetheexit(fromTRUEtheorFALSEcomponent)dependingstatementsupons1theandforms2of.

ruleIfStatement=\"if\"{

\"else\">

forall(Nodethis->entry(UNCOND,n)

:-Condition->entry(UNCOND,n)

n).

forall(Nodethis->exit(n,n,Labellbl)

lbl)

forall(Node:-s1->exit(n,this->exit(n,n,Labellbl).

:-s2->exit(n,lbl)

lbl)

lbl).

forall(Nodethis->trans(n1,n1,Node:-Condition->exit(n1,TRUE,n2)

n2)

forall(Nodes1->entry(UNCOND,n2)UNCOND).

,

this->trans(n1,n1,Noden2)

:-Condition->exit(n1,FALSE,n2)

s2->entry(UNCOND,n2)UNCOND).,

forallthis->trans(n1,(Noden1,Labellbl,Noden2)

forallthis->trans(n1,(Node:-s1->trans(n1,lbl,n2)

n1,Labellbl,lbl,Noden2)n2)

.

}

:-s2->trans(n1,lbl,n2)

lbl,n2).

Figure10:ifstatementruledefinition

followsTheattributegrammingabottom-upgrammarapproach.usedtoForcomputethegraphgrapherativeoflanguagesuchasPL0,thisastructuredmeansthatpro-thelowerconstruct)astructuredisbuiltconstructusing(atheconditionalattributesorit-assertslevelcomponentthatcomponents.thereareFortheIfStatementtheofruleitsofthethetothenodestransitionsthatformfromthetheentryconditionpointsFinally,transitionscomponentarelabelledstatementstrue(s1ands2),andthataddingoverallallthenestedrulecompletestransitionstheandwithindefinitionfalserespectively.s1andofs2transtobytheThesetthetheentrytransitionsoftransitions.

andexitsforoftheitssequencescomponentareconstructs,builtupusingexample,sameaddingamannerlistofasstatementsforbranchingconstructs.Forinexitnext.

ofoneatransitionstatementfromtothethenodenodeislinkedforrepresentingtogethertheentryofthebytheintheTheEDLpopulationdefinition.oftheTheglobalpopulationrelationsofisthesealsogivenrela-

tionsaintupleisdemonstratedtotheglobalinUseTokensFigure9withrelationtheadditionoftheSectionstruct.valueof5.3),avariablesignifyingatanythatacondition(explainedcanusethatgeneric.enablesItisthethepointwithinthecon-approachinformationtodata-flowheldintheseanalysisrelationstobe5.3

LanguageSemantics

AnotherthoseclassofglobalGraphBuilderrelationsareforholdusethatinthecapturegenerictheAnalysissemanticstool.ofaThesegivenlanguageindependentthenon-terminalsymbolsthatallowlanguage-relationsanalysisrepresentingtechniques.applicationTheofcontrol-flowanddata-flowofsisthecalculationlanguagethenameofinclusionthesourceoflanguageastringelementineachtoolsemanticstobegeneric.relationsMoreover,allowsthetheanaly-useoftheysislanguageanalysestoolcanbename,multi-lingualeffectively(i.e.,meansitcanthatconductflowanal-theguagesonprogramsfromadiverserangeoflan-BothTokensTheinthreeonesession).

relations,ModTokens,ically,capturethelanguageconstructsUseTokensandbythenon-terminalsofthelanguagedeclared(specif-and/ortheappropriatetheusethevalueEDLofavariable.definition)Forthatexample,canchangegivenandstatementthevaluesx:=y+z,thevalueofxismodifiedtionsTheofbothyandzareused.

alent,(explainedModTokensin,UseTokensandBothTokensrela-(String,andareturnbelow)arestructurallyequiv-nameString,oftype

String).Thefirstelementmationoftheapplies.thelanguageThesecondtowhichistheelementthissemanticisinfor-ficationnon-terminalnameand/oruse.constructThethirdthatelementcontainsthenameofspecifiesthemodi-thatand/orrepresentofthenon-terminaltheidentifiersymbolsthatfromiseitherthelanguagethemodifieduseused.Moreover,constructscanmodifyandstructsThemultipleBothTokensidentifiers.

relationisusedforlanguagesingleinon-terminal,thatbothmodifyforexampleandusetheavariablecon-i++usingaand+=tuplesUseTokens10syntaxfromrelationsC.Theand

areModTokenspairwisedisjoint.,BothTokensappearthatlations,ineitherappearoftheintheModTokensBothTokensandrelationdoThenotputedallfromandthewhileintersectionBothTokensofcouldallmodificationshaveUseTokensbeencom-re-wasuses,ofmaintained.forperformanceUsingthereasonscurrentarelationsseparateandtherelationunionmodifications,ModTokensandUseTokenswillsimilarlyBothTokensgivethethesetunionwillofalluses.ofgiveBothTokensthesetofandall6

Analysistool

ThesemanticsAnalysistoolusesthecontrol-flowGraphrelationsdefinedbythelanguage-specificandlanguagethatAnalysistheBuilderAnalysistool.Thechosenrepresentationsmeancallflowgraphs,tooltoolislanguageindependent.Theanddata-flowandperformspresentsdata-flowanalyses.

theresultsanalysis,ofbothconstructscontrol-proach.Theseactivitiesareundertakenviaafour-passap-graphInthefirstpass(Section6.1),thecontrol-flowusedisannotatedwiththevariablesmodifiedandtherbyeachnode.Followingthis,thegraphisinannotatedwiththeexecutionsignatures(definedfur-formsSectionananalysis6.2)forwhicheachnode.linkstheThemodificationsthirdpassper-and

usestation(Sectionpresentedofresults.6.3).TheTheresultsfinalofpasstheisflowforthepresen-appropriatebothlanguage-basedrelationstextuallytoandbefedthroughbacktheanalysestothecreationaregenericofnavigationcapabilitieseditorfor(Jarrottdisplay&usingMacDonalditsrelational2003).6.1

Pass1:Modification-Useannotation

Intothefirststage,thecontrol-flowgraphisannotatedeachreflectthevariablesthatareusedormodifiedbyysisthekenslanguagetoolparticularreliesnode.Duringthispass,theAnal-semanticsupontheinformationstoredwithinforminedeach,andnodeBothTokensofthe.relations:ModTokens,UseTo-control-flowThevariablesgraphmodified/usedingviaastate-basedtreetraversalalgorithm.aredeter-guagethesemanticsnon-terminalrelations,symbolsthedefinedtreetraversalwithinthemain-lan-Us-tainsavariablesmodifyingarecordforand/orofwhethereachnode.usingtheconstruct,constructandisclassifiesconsideredall6.2

Pass2:Executionsignatureannotation

Wefullhavedefinedaacannotvariable.setofnodessafeanalysisthatdeterminestheInthatmayhaveaffectedthevaluesofnodelowedbecauseaffectthesomevaluecasesofitamayvariableincludeatnodessomelaterthatatruntimethe-pathitisbetweenadeadpath.themAscannottheAnalysisbefol-toolsafeperformsthestaticmodification-useanalysisinapotentiallymanner,itwillidentifyasupersetofnodesthatorderlastmodifiedthevalueofavariable.Ingraphtoofdefinitelydeterminewhetheranodeofacontrol-flowturesavariableoronlypotentiallymodifiedthevaluetureofeachitisrequiredthattheexecutionsigna-ofpathpossibleofanodenodebederived.Theexecutionsigna-timesistheminimumandmaximumnumbergraphofanodeisexecutedinaparticularcanpresentsthecontrol-flowallgraph.Sinceacontrol-flowgetgraphnodetake,maymultiplepathstheexecutionofaprogramexist.pathsbetweenasourceandtar-inggraph,thatcanitiseitherbemarkedInthisascontext,compulsorynodes(1)ofmean-thesingleplepathoroptionalexecutedatapoint(0)inmeaningeverypathintheprogramthatoftheitwhereappearscontrol-flowmulti-inaoptionalpathsofrepresentexist.Theclassificationsofcompulsoryandmaximumacontrol-flowtionexecutiongraphtheminimumsignaturenode.executionsignature.Similarly,Theanodehasaecutedsignaturethejustoncerepresents(1)ormultiplewhethertimesamaximumnode(M).canexecu-beex-notationminimumandmaximumconstructsaregivenTogetherthesignatureWhile‘minimum..maximum’,theimportancee.g.,1..1and0..M.thelessanalysis,isapparenttheneedfromofforthethethepessimisticminimumexecutionnatureofwithinobvious.theaniterativeWhereconstruct,thevalueofmaximumsignatureisnodesavariableoccurringismodifiedalsoiterativeconstructbutbeforethemodificationwithinarevaluedependenttheonthenextoniteration),themodifyingandshouldstatementbeincluded(fortheirinample,setofmodifyingstatementsforthatnode.Forex-dependintoonFigurethemodification11theusesofofxxinW2,W3andW4foraccuratelycharacteristicsasafeanalysis),determineboththethefullmaximumsetinofW4nodes.Therefore,andminimum(neededtheItneedtobeused.

guishescalculationisthedevelopmentofofgenericmechanismsforoptimisingthecompileralgorithmsexecutionalgorithms.ofthissignaturesresearchthatdistin-Inorderfromtostandarddevelop

begin W1:read x ; W2:while x < 10 do W3:write x ; W4:x := x + 1 ; W5:

write xend .Figureiteration

11:Examplemodification-userelationshipforexecutionysis,signaturesforuseingenericdata-flowstudyitthisturesstudy,thewasstructuresnecessarytoreturntofirstprinciplesanal-andwaysofdeterminingofcontrol-flowtheexecutiongraphs.Duringsigna-structsofatomic,ofindividualimperativenodeslanguagesweredeveloped.canBasiccon-testedticsofrepetition.conditional,theseclassesThepre-testedbeclassifiedintoaregeneralrepetitionandpost-giveninexecutionTable6.

characteris-Structure

Lowerlimit

Upperlimit

Atomicstatement1

1

(assignment)Conditional01(if-else)

Pre-testedrepetition0M(while-do)

Post-testedrepetition1

M

(repeat-until)

Table6:GeneralcontrolstructureexecutionlimitsThebasicalgorithmusedtocalculatetheexecu-tionbasesignatureofaparticularnodeistodetermineitssinglesignature,closingexecution),whichanddefaultsthenconsiderto1..1each(compulsory,theconstructsinturn(e.g.,awhileloop),ofitstakeen-tureminimummaximumandthatofoftheitsownsurroundingminimumexecutionsigna-construct.ofitsownmaximumandconstruct,thatoftheandoutertheisetitionforthetreatmentOnedepartureoftheconditionfromtheabovealgorithmnotthereceiveandtheconditionalstatements.inThesepre-testednodesrep-dointheyaconditionalminimumsenseorpre-testedexecutioniterativecharacteristicconstructs,asoftheofcodeareparttheypresentedofarethosenotenclosedbythoseconstructs,inconstructs.Figure11,theForinitialexample,signatureusingstructW3is1..1,andthatoftheenclosingwhilecon-tionthesignatureis0..M.ofFromW3thesefigures,theactualexecu-urecontrol-flowgraphbecomesforthecode0..Mfragment.Figure12showseach11ofannotatedthenodes.withtheexecutionsignaturesfromFig-for6.3

Pass3:Analysisandlinking

Theofmayavariablefinalstagetoofthethemodificationsdata-flowanalysisofthevariablelinksallusesthatanduplinkingthelinkinghaveaffectedcontrol-flowpassusesitsvalueatthatpoint.Theanalysisgraphrecursion(towardstosearchthegraph’sfromanodemusttionshipbetogethernotedausewithitssetofmodifications.entry),Iteditor’sistransitive,thatsinceandthethemodification-useUQ󰀁rela-transitiverelationalpotentialrelations,navigationeachuseisfacilitylanguage-basedonlynicelyhandlesForexample,modificationsgiventhecode:

thatimmediatelylinkedprecedewiththeit.Uncond. W1: read x1..1Uncond. W2:x < 101..MTrue W3:write x0..MUncond.FalseUncond. W4:x := x + 10..M W5:write x1..1Uncond.Figuretions

12:Graphwithexecutionsignatureannota-C1:C2:readC3:ba:=b;

:=bb

+1;theC1useofbinC3willonlybelinkedwiththe.ingvalueUsingoftransitivity,binitispossibletodiscoverC2andthatnotthisthroughC3isdependentonC1vianavigat-tionshipsdiagrammaticallytherelationalforthesenodes.

withlinks.themodification-useFigure13presentsrela-read b;b := b + 1;a := bFigure13:Chainedmodification-userelationships6.4

Finalisation

UponAnalysiscompletionoftheanalysisandlinkingpass,theserverrelation.toolpopulatesThisrelationstheMod-UseisdefinedUQas:󰀁DocumentrelationMod-Use(String,Node,Node).Theingparameterscorrespondtothevariablethattentialused,thelast)themodificationASTnodethatandrepresentsisbe-thealast(orpo-Mod-Useuseisoccurring.1.

relationforTabletheexample7showsASTtheprogramcontentsnodeatwhichofFigureoftheVariableModNode

UseNode

xACbBDbBEaDFa

E

F

Table7:Mod-UserelationfortheexampleprogramaTable7nodesatnodeDandF)alsowhichgivesE).hasantwoexamplepossibleofamodificationsuse(ofvariable(at7

Summary

Thisdata-flowpaperenvironmentanalysisdescribedtotheadditionofcontrol-flowandstanding.ofThetokeysupportagenericcontributionimprovedsoftwarewasprogramdevelopmentnottheadditionunder-couldthebetooladdedsupportinaitself,predominatelybutthatthisgenerictoolmanner.

supportTheintodesignofthetoolsseparatedthehaviour.language-specificandlanguage-independentfunctionalitybe-fiedausingTheanattributelanguage-specificgrammarlanguage,behaviourfromwaswhichcodi-language-independentgraphbuildingtoolisautomaticallygenerated.Thegenericbehaviourwascodifiedinaasafedata-flowanalysistool.analysisTheusingAnalysistheexecutiontoolperformssigna-turesGraphofdata-flowBuilderthecontrol-flowtool.Amodificationgraphnodesofbuiltbythetionalthercompiler-basedanalysistechniquetechniqueswaswererequiredtraditionalfoundastotradi-niquesoverlyingorsimplycomplex,nottightlycoupledtootherbetech-ei-Fromduementthetoafocusonsuitablemachineforcodeprogramrepresentations.understand-withinleveloutputrelationshipsofthesetwoweretools,presentedvariabletoandstate-lowThethecapabilitiessoftwaredevelopmentprovidedbyenvironment.

theuserthisworkwillflowtechniques(Grundon,analysis,suchthatasrelyontheresultsofcontrol-al-instepUQ󰀁infutureHayes&FidgeTiming-Constraint1998)tobeimplementedAnalysisofindevelopingprojects.toolstosupportThisworktheisalsoafirstthelegacyModernizationObjectsystemsManagementsuchasGroup’sthoserequiredmodernizationaspartofADMproject(ObjectArchitecture-DrivenManagmentGroupDonaldTaskforce2003,Gerber,Glynn,Lawley,Mac-wareIntegration&Raymondsuchdevelopmentofprogram2004).

environmentanalysisbenefitstoolsintoasoft-fulysistoolsenvironments.workingwhichthatTheuserhasaccessthetouserspower-ofcanaidbeprograminvokedunderstandingwithintheusersandnormalanal-ing.tureTheenvironmentuserisnotconcernedandminimiseswithcontexttheswitch-languagesofthemanner.ofimplementation,interestarebutratherthatgenericallna-thevironmentsThetheisdevelopersupportedinaconsistentconcernedofsoftwaredevelopmenten-theperadditionlanguageofconsistentwitheffort.supportgenericitywhileasminimisingitenablesAcknowledgements

ThePhilauthorsgrammarCookwouldliketoacknowledgetheinputofcilitylanguageforhisdevelopmentandautomaticofthetoolUQgeneration󰀁attributefa-likementstousedonthankinearlierKerrythisresearch.draftsRaymondTheauthorswouldalsoofthisforpaper.herinsightfulcom-References

Buxton,grammingJ.(1980),DoDrequirementsforAdapro-TechnicalmentReportsupportAD-A100enviroments,404,STONEMAN,adahome.com/History/StonemanofDefense.AvailablefromUSDepart-gust2003.,http://www.AccessedAu-Cook,language-basedP.&Welsh,J.meeteditors:(2001),User‘Incrementalneedsandparsinghowin

31(15),them.’,1461–1468.Software-PraticeandExperiencetoCook,context-sensitiveP.,Welsh,J.&calCentreReport02–11,evaluationHayes,I.(2002),Incremental

Softwareincontext,Techni-ogy,(SVRC),SchoolofInformationVerificationResearchAustralia.

TheUniversityofQueensland,Brisbane,Technol-Gerber,A.,Glynn,E.,Lawley,M.,MacDonald,

A.&Raymond,K.(2004),KnowledgeDiscov-eryMetaModel-InitialSubmission,OMGSub-missionadmtf/04-04-01,ObjectManagementGroup.Grundon,S.,Hayes,I.&Fidge,C.(1998),Tim-ingconstraintanalysis,inC.McDonald,ed.,‘Proceedings21stAustralasianComputerSci-enceConference’,pp.575–586.Hecht,M.S.(1977),FlowAnalysisofComputerPro-grams,TheComputerScienceLibrary:Pro-grammingLanguageSeries,ElsevierNorth-Holland.Howden,W.(1982),‘Comtemporarysoftwaredevel-opmentenvironments’,CommunicationsoftheACM25(3),318–329.Jarrott,D.&MacDonald,A.(2003),Developingrela-tionalnavigationtoeffectivelyunderstandsoft-ware,in‘ProceedingsoftheTenthAsia-PacificSoftwareEngineeringConference(APSEC’03)’,IEEEComputerSociety,pp.144–153.Jones,T.&Welsh,J.(1997),Requirementsfor

ageneric,language-baseddiagrameditor,inM.Patel,ed.,‘Proceedingsof20thAustralianComputerScienceConference’,Vol.19,pp.316–325.Knuth,D.(1968),‘Semanticsofcontext-freelan-guages’,Math.SystemsTheory2(2),127–145.MacDonald,A.&Welsh,J.(1999),Persistenceinthe

UQ󰀁environment,TechnicalReport99–43,Soft-wareVerificationandResearchCentre,SchoolofInformationTechnologyandElectricalEngineer-ing,TheUniversityofQueensland,Brisbane,Australia.Muchnick,S.(1997),Advancedcompilerdesignand

implementation,MorganKaufmannPublishers.ObjectManagmentGroupADMTaskforce(2003),

RequestforProposal-Architecure-DrivenMod-ernization(ADM):KnowledgeDiscoveryMeta-Model(KDM),OMGRFPlt/03-11-04,ObjectManagementGroup.Reiss,S.(1990),‘Connectingtoolsusingmessage

passingintheFieldenvironment’,IEEESoft-ware7(4),57–66.Rugaber,S.(1995),‘Programcomprehension’,En-cyclopediaofComputerScienceandTechnology35(20),341–368.Tip,F.(1995),‘Asurveyofprogramslicingtech-niques’,JournalofProgrammingLanguages3,121–189.Toleman,M.,Carrington,D.,Cook,P.,Coyle,A.,

Jones,T.,MacDonald,A.&Welsh,J.(2001),Genericdescriptionofasoftwaredocumenten-vironment,inR.H.Sprague,ed.,‘Proceedingsofthe34thAnnualHawaiiInternationalConfer-enceonSystemSciences’,IEEEComputerSoci-ety.AlsofoundinSVRCTechnicalReport00-22.Welsh,J.(1994),Softwareishistory!,inA.W.

Roscoe,ed.,‘AClassicalMind:Essaysinhon-ourofC.A.R.Hoare’,PrenticeHall,chapter24,pp.419–430.Welsh,J.,Broom,B.&Kiong,D.(1991),‘Adesign

rationaleforalanguage-basededitor’,Software-PracticeandExperience21(9),923–948.

Welsh,J.&Yang,Y.(1994),‘Integrationofsemantic

toolsintodocumenteditors’,Software–Con-ceptsandTools15,68–81.Wirth,N.(1976),Algorithms+DataStructures=

Programs,Prentice-Hall.