Project 3 PDF

Preview

Summary

Project 3 of Compilers. Assembly...

Description

CS 352 Spring 2019 Compiler Project 3 Posted March 30, 2019, Due April 27, 2019, 11:59pm 1. Introduction Thisprojectistobedonebyeachstudentindividually.ReviewtheAcademicHonestyPolicypostedon Piazzacarefully.Theduedate/timeisfirm,exceptforthegracedaysallottedtoeachstudent(seethe beginningnoteinProject1handoutaboutthegracedays). Thisisasubstantialprojectconsistingofseveralcomponents.Studentsarestronglyadvisedtostart early,followingthesuggestedtimeline. Studentsareremindedthat,withthescaleof100,Project3counts45. ThesourcecodeinMinijava+followsthesamegrammar (https://piazza.com/class_profile/get_resource/jqkfvqi3m1v1gq/js9ufjf6pp86cz)andthesametype rulesimplementedinProject2.Alltestcasesareassumedtobesyntacticallycorrectwithouttype violations. Youmayfindthedocument“ARM_Assembly_Tutorial.html”postedonPiazza (https://piazza.com/class_profile/get_resource/jqkfvqi3m1v1gq/jtoro1oqk046qz)usefulforthisproject, especiallyifyouarenewtoARMassembly.

2. Project Requirement ThissectiongivesanoverviewofthetasksinProject3.MinutedetailswillbeclarifiedonPiazzaas variousquestionsmaybeposedbystudents. ThemaintaskofProject3istoreplacetheinterpreterwrittenforProject2byanewASTtraversal schemethatconvertsaMiniJava+programintoanequivalentARMassemblycode,withtheadditional goaltomakethegeneratedcodeefficientbyusingregisterallocationschemestobediscussedinclass. Itisassumedthatthetestcaseswillnotcauserun‐timeexceptions.Hencenoerrorsaretobereported. Someofthetypecheckingcodeisstillneededforallocatingvariablesinthememoryandforgenerating address‐computinginstructions. Thecriteriatodeterminethecorrectnessofthegeneratedassemblycodeistorunitthroughsample inputs.TheoutputproducedbytheassemblycodemustagreewiththeexpectedresultoftheMiniJava+ program.(Whenindoubt,testtheMiniJava+programusingthestandardJavacompilation/execution tools.)

AsstatedinMiniJava+specpostedforProject1,thesemanticsofaMiniJava+followsthatinJava standard.StudentsshouldcarefullyreviewrelevantJavatyperulesandexecutionrulesasinProject2. Asdescribedinthelectureslides,thetargethardwareisaRaspberryPivirtualmachineimage.Please refertoLecture29andthepostedmini‐tutorialonPiazzafordetails.

3. The Grading Scheme RecallthatProject2handoutdividedMiniJava+programsintothreecategories.Project3continuesto usethatdivision.Part1constitutethebasiccases,constituting80%ofthetotalpoints.Ofthose,70%of thetotalpointsisattributedtothecorrectnessoftheoutputand10%ofthetotalpointsisattributedto theefficiencyofthegeneratedcode.Themetricofefficiencyistobeannouncedlater,dependingonthe successofinstallingaperformancecounterintheRaspberryPivirtualmachineimage.Themost importantfactorthatimpactstheefficiencyisexpectedtobehowwellregisterallocation isperformed. Part2ofthecasesaddsreferencestoarrayvariablesandclassinstancevariables.Themainworkfor Part2istogenerateaddress‐computationinstructionsforaccessingarrayelementsandinstance variables.Part2counts10%ofthetotalpoints. Part3,whichcounts10%ofthetotalpoints,addsmethodinvocation(whichmayberecursive).Grading willbebasedonbothcorrectnessandefficiency,whereefficiencyisprimarilyaffectedbyhowregister savingandrestoresareoptimized.Theweightofcorrectnessandefficiencyiscurrentlysetto5%eachof thetotalpoints,butwemayreviseitasweunderstandtheeffortinvolvedbetter.

4. A Suggested Implementation Plan 4.1Part1 RecallthatprogramsinPart1fallsintotwosetofcases,onewiththemainclassbutnootherclasses, andtheotherwithboththemainclassandoneotherclass.Thepurposeofhavinganadditionalclassis toallowthefullvarietyofstatementsintheprogram,exceptthegeneralcasesofmethodinvocation. Iftheprogramcontainsthemainclassalone,theonlystatementstobeimplementedwillineffectbe justtheprintingstatements.Eachinvocationoftheprintingmethodhasonlyoneargument,whichis eithertheresultofanintegerconstantexpressionorastringliteral.Instructionstoprintastringliteral followstheexamplegiveninLecture29,byinvokingtheprintfstandardfunction.Theassemblycodeto printtheresultofanintegerconstantexpressionwillbesimilar,exceptthatALUinstructionsthat evaluatetheconstantexpressionsshouldbegeneratedbytraversingtheASTsubtreeforthatexpression. Suchinstructionsareemittedfollowingapost‐ordertraversaloftheASTsubtree. IfaprograminPart1containsanotherclass,C1,besidesthemainclass,thentheargumentinaprinting method(invokedfromthemainmethod)maybethereturnvalueofyetanothermethod,saym1, declaredandimplementedinC1.Themethodm1willhavenoformalparametersinthetestcasesandit willnotmakeanymethodinvocation.Wesuggestthatcodegenerationforsuchaprogrambe

implementedfollowsapost‐ordertraversaloftheASTsubtreeofthemethodbodyofm1.Thus,the instructionstoloadtheoperandsaregeneratedfirst,whichisfollowedbythenextinstructionoperating ontheoperands,andsoon. Wesuggestthat,forPart1,allmethod‐localvariablesarefirstallocatedstatically,usingsymboliclabels asintheARMcodeexampleshowninclass.Similarly,thereturnedvaluefromm1canbestoredina staticlocationknowntothemainmethod.Thisallocationscheme,althoughnotageneralschemeforall MiniJava+programs,makesimplementationforPart1morestraightforwardthanallocatingthe variablestothestack.Thissimplerallocationschemeallowsstudentstofocusontheinstruction selectionforvariouskindsofstatements.AsstudentslaterproceedtoPart3,onlythememory referencinginstructions(includingthoseinPart1)needtobereplacedbytheconventionalstack‐based scheme.

4.2Part2 WhatisnewinPart2isthatarrayandinstancevariablesaredynamicallyconstructedbyinvokingthe standardlibraryfunctionmalloc()intheARMassemblycode.ThemainworkforPart2istodetermine thesizeoftherequestedblockfortheconstructedarrayorobjectandtogenerateaddress‐computation instructionstoaccessarrayelementsandinstancevariables.Therestofcodegenerationisthesameas inPart1.

4.3Part3 Generatingcodeforgeneralmethodinvocation(asdefinedinProject2)isthemainworkforPart3. Differentclassesmayhavenamesakemethods.Thesymboliclabelsintheassemblycodeforsuch methodscanbegeneratedbyconcatenatingtheclassnameandthemethodname. Methodinvocationinvolvesparameterpassingandregistersaving/restoring.Thisshouldfollowan applicationbinaryinterface(ABI).Wewillpostamini‐tutorialontheABIlater. Cross‐classreferencesofinstancevariablesinPart3requirescompile‐timedeterminationofoffsetsto beaddedtothebaseaddressofanobject.Theseissuesandhandlingmethodshavebeendiscussedin previouslectures. TheefficiencyofthecodegeneratedinPart3isprimarilyimpactedbyhowwellthecodeavoids unnecessarysavingandrestoringofregistersasonemethodinvokesanother.Thiswillbediscussedin thelectures.

5. Estimated Timeline 

Part1withoutefficiencyconcern(oneweek)



Part2(3days)



Registerallocationschemeforscalarvariables(oneweek)



Part3(oneweek+)





6. Submission instruction 1)Noofflinesubmission(suchasemail)isaccepted.  2)UsethefollowingcommandonCSlabmachinesthatrunanyLinuxOS,e.g.theXINUmachines(i.e., xinu01.cs~xinu20.cs)tosubmityourhomework. turnin–ccs352–pp3[yourworkingdirectory] Priortoexecutingtheturnincommand,itisveryimportantthatyouremoveallfilesinthesubmitted folderexceptthemakefile,theyaccprogram(.y),thelexprogram(.l),andthe.hand.cfilesyouwrite fortheproject.IfyouimplementinC++,similarcaremustbetaken. (YourhomedirectoriesaredirectlyaccessibletoyouonallCSlabmachines.) 3)YouarefreetowriteyourownMakefile,aslongasthefollowingrequirementsaremet. ThegraderwillrunyourMakefilebyexecutingthecommand“makemjavac”toproducetheexecutable programnameedmjavac.Hence,itisimportantthatyourMakefileproducessuchanexecutablewhen invoked. YoumustalsowriteyourMakefilesuchthatwhen“makeclean”isrun,allfiles,excepttheMakefile, yourYaccandlexprograms,andthe.hand.cfiles(ortheC++equivalents),areallremoved.Thisisto ensurethatthesystemdoesnotexceedthestoragelimitsetbythesystemstaff.  4)YourprogramMUSTcompileandrunwithoutanyerroronCSlab’sLinuxmachines.Pleasedoafinal testofthisbeforesubmission,especiallyifyoudoyourprojectonothercomputers. 5)Yourcodewillbetestedforgradinginthefollowingsteps: Step1:Werunthefollowingcommand >./mjavacprogram_name.java where“program_name.java”isthefilenamecontainingtheinputprogram.Yourcodemustproducethe ARMassemblycodeprogram_name.s.Notethefileextension“.s”. Step2:program_name.swillbeassembledandlinkedontheRaspberryPivirtualmachineimage,using command“gcc–oprogram_nameprogram_name.s” Step3:program_nameisexecutedandtheprint‐outexaminedforcorrectness.Efficiencyismeasured.

NOTE:Deviationfromtheaboverequirementwillgeta5pointofpenalty.(Forexample,ifyourcode receives90points,thefinalscoreontheBlackboardforthisassignmentwillbe85points.)

7. Discussion Online [ThissectionisessentiallycopiedfromProject1.] Theteachingstaffwillprovideasetoftestcasesandexpectedresults.Thesetestcasesareintendedas astartingpointforstudentstoformafullunderstandingoftheentiresetofvalidinput.Oneshouldfully expectthat,althoughsomeofthetestcasesmaybeverysimilartothepostones,therestmaywellbe quitedifferentandlikelygobeyondthescopenarrowlydefinedbythepostedtestcases. Studentsareencouragedtoshareanddiscusstestcasesonourcourse’spiazzasite.(Buildingtest casesingroupsisactuallyagoodpracticeusefulforyourcareer.)However,nopartofthesolutionis allowedtobeposted.Theteachingstaffwilldiligentlychecksubmissionsagainsteachotherandagainst submissionsfromprevioussemesters(ifapplicable). PleasedonotpostanycodesegmentonPiazza(noteveninprivatemessages)orinemailforTAsto debugforyou,becausemostofthetimeitisimpossibletolocateerrorswithoutactuallyrunningyour code.Onlyifyoutrulybelieveafewlinesofcodeexplainsyourquestionperfectlywellareyouallowed topostitinaprivatemessageonPiazzaalongwithaclearandspecifictechnicalquestion.Inallother cases,cometoanyPSOtofindhelpfromtheTAor,ifnoPSObesidesyoursiswithoutaschedule conflict,arrangeaspecialtimewithaTAforhelp.IftheTAsarenotabletofindtheproblemafteran effort,emailinstructortoexplainyourdifficulty.  ...