ATourThroughthePortableCCompiler S.C.Johnson Introduction ACcompilerhasbeenimplementedthathasprovedtobequiteportable,servingasthe basisforCcompilersonroughlyadozenmachines,includingtheHoneywell6000,IBM370,and Interdata8/32.ThecompilerishighlycompatiblewiththeClanguagestandard.1 Amongthegoalsofthiscompilerareportability,highreliability,andtheuseofstate-of-the-arttechniquesandtoolswhereverpractical.Althoughtheefficiencyofthecompilingprocessis notaprimarygoal,thecompilerisefficientenough,andproducesgoodenoughcode,toserveasa productioncompiler. ThelanguageimplementedishighlycompatiblewiththecurrentPDP-11versionofC. Moreover,roughly75%ofthecompiler,includingnearlyallthesyntacticandsemanticroutines,is machineindependent.Thecompileralsoservesasthemajorportionoftheprogramlint, describedelsewhere.2 Anumberofearlierattemptstomakeportablecompilersareworthnoting.WhileonCO-OPassignmenttoBellLabsin1973,AlanSnyderwroteaportableCcompilerwhichwasthe basisofhisMaster’sThesisatM.I.T.3Thiscompilerwasveryslowandcomplicated,andcontainedanumberofratherseriousimplementationdifficulties;nevertheless,anumberofSnyder’s ideasappearinthiswork. Mostearlierportablecompilers,includingSnyder’s,haveproceededbydefininganintermediatelanguage,perhapsbasedonthree-addresscodeorcodeforastackmachine,andwritinga machineindependentprogramtotranslatefromthesourcecodetothisintermediatecode.The intermediatecodeisthenreadbyasecondpass,andinterpretedorcompiled.Thisapproachis elegant,andhasanumberofadvantages,especiallyifthetargetmachineisfarremovedfromthe host.Itsuffersfromsomedisadvantagesaswell.Someconstructions,likeinitializationandsubroutineprologs,aredifficultorexpensivetoexpressinamachineindependentwaythatstillallows themtobeeasilyadaptedtothetargetassemblers.Mostoftheseapproachesrequireasymbol tabletobeconstructedinthesecond(machinedependent)pass,and/orrequirepowerfultarget assemblers.Also,manyconversionoperatorsmaybegeneratedthathavenoeffectonagiven machine,butmaybeneededonothers(forexample,pointertopointerconversionsusuallydo nothinginC,butmustbegeneratedbecausetherearesomemachineswheretheyaresignificant). Forthesereasons,thefirstpassoftheportablecompilerisnotentirelymachineindependent.Itcontainssomemachinedependentfeatures,suchasinitialization,subroutineprologand epilog,certainstorageallocationfunctions,codefortheswitchstatement,andcodetothrowout unneededconversionoperators. Asacrudemeasureofthedegreeofportabilityactuallyachieved,theInterdata8/32Ccompilerhasroughly600machinedependentlinesofsourceoutof4600inPass1,and1000outof 3400inPass2.Intotal,1600outof8000,or20%,ofthetotalsourceismachinedependent(12% inPass1,30%inPass2).Thesepercentagescanbeexpectedtoriseslightlyasthecompileris tuned.Thepercentageofmachine-dependentcodefortheIBMis22%,fortheHoneywell25%.If theassemblerformatandstructurewerethesameforallthesemachines,perhapsanother5-10% ofthecodewouldbecomemachineindependent. Thesefiguresaresufficientlymisleadingastobealmostmeaningless.Alargefractionofthe machinedependentcodecanbeconvertedinastraightforward,almostmechanicalway.Onthe otherhand,acertainamountofthecoderequreshardintellectualefforttoconvert,sincethe -2-algorithmsembodiedinthispartofthecodearetypicallycomplicatedandmachinedependent. Tosummarize,however,ifyouneedaCcompilerwrittenforamachinewithareasonable architecture,thecompilerisalreadythreequartersfinished! Overview Thispaperdiscussesthestructureandorganizationoftheportablecompiler.Theintentis togivethebigpicture,ratherthandiscussingthedetailsofaparticularmachineimplementation. Afterabriefoverviewandadiscussionofthesourcefilestructure,thepaperdescribesthemajor datastructures,andthendelvesmorecloselyintothetwopasses.Someofthetheoreticalworkon whichthecompilerisbased,anditsapplicationtothecompiler,isdiscussedelsewhere.4Oneof themajordesignissuesinanyCcompiler,thedesignofthecallingsequenceandstackframe,is thesubjectofaseparatememorandum.5 Thecompilerconsistsoftwopasses,pass1andpass2,thattogetherturnCsourcecodeinto assemblercodeforthetargetmachine.Thetwopassesareprecededbyapreprocessor,thathandlesthe#defineand#includestatements,andrelatedfeatures(e.g.,#ifdef,etc.).Itisa nearlymachineindependentprogram,andwillnotbefurtherdiscussedhere. Theoutputofthepreprocessorisatextfilethatisreadasthestandardinputofthefirst pass.Thisproducesasstandardoutputanothertextfilethatbecomesthestandardinputofthe secondpass.Thesecondpassproduces,asstandardoutput,thedesiredassemblerlanguage sourcecode.Thepreprocessorandthetwopassesallwriteerrormessagesonthestandarderror file.ThusthecompileritselfmakesfewdemandsontheI/Olibrarysupport,aidinginthebootstrappingprocess. Althoughthecompilerisdividedintotwopasses,thisrepresentshistoricalaccidentmore thandeepnecessity.Infact,thecompilercanoptionallybeloadedsothatbothpassesoperatein thesameprogram.This‘‘onepass’’operationeliminatestheoverheadofreadingandwritingthe intermediatefile,sothecompileroperatesabout30%fasterinthismode.Italsooccupiesabout 30%morespacethanthelargerofthetwocomponentpasses. Becausethecompilerisfundamentallystructuredastwopasses,evenwhenloadedasone, thisdocumentprimarilydescribesthetwopassversion. Thefirstpassdoesthelexicalanalysis,parsing,andsymboltablemaintenance.Italsoconstructsparsetreesforexpressions,andkeepstrackofthetypesofthenodesinthesetrees.Additionalcodeisdevotedtoinitialization.Machinedependentportionsofthefirstpassservetogeneratesubroutineprologsandepilogs,codeforswitches,andcodeforbranches,labeldefinitions, alignmentoperations,changesoflocationcounter,etc. Theintermediatefileisatextfileorganizedintolines.Linesbeginningwitharightparenthesisarecopiedbythesecondpassdirectlytoitsoutputfile,withtheparenthesisstrippedoff. Thus,whenthefirstpassproducesassemblycode,suchassubroutineprologs,etc.,eachlineis prefacedwitharightparenthesis;thesecondpasspassestheselinestothroughtotheassembler. Themajorjobdonebythesecondpassisgenerationofcodeforexpressions.Theexpression parsetreesproducedinthefirstpassarewrittenontotheintermediatefileinPolishPrefixform: first,thereisalinebeginningwithaperiod,followedbythesourcefilelinenumberandnameon whichtheexpressionappeared(fordebuggingpurposes).Thesuccessivelinesrepresentthenodes oftheparsetree,onenodeperline.Eachlinecontainsthenodenumber,type,andanyvalues (e.g.,valuesofconstants)thatmayappearinthenode.Linesrepresentingnodeswithdescendantsareimmediatelyfollowedbytheleftsubtreeofdescendants,thentheright.Sincethe numberofdescendantsofanynodeiscompletelydeterminedbythenodenumber,thereisno needtomarktheendofthetree. Thereareonlytwootherlinetypesintheintermediatefile.Linesbeginningwithaleft squarebracket(‘[’)representthebeginningofblocks(delimitedby{...}intheCsource);lines beginningwithrightsquarebrackets(‘]’)representtheendofblocks.Theremainderofthese linestellhowmuchstackspace,andhowmanyregistervariables,arecurrentlyinuse.

-3-Thus,thesecondpassreadstheintermediatefiles,copiesthe‘)’lines,makesnoteofthe informationinthe‘[’and‘]’lines,anddevotesmostofitsefforttothe‘.’linesandtheirassociatedexpressiontrees,turningthemturnsintoassemblycodetoevaluatetheexpressions. Intheonepassversionofthecompiler,theexpressiontreesthatarebuiltbythefirstpass havebeendeclaredtohaveroomforthesecondpassinformationaswell.Insteadofwritingthe treesontoanintermediatefile,eachtreeistransformedinplaceintoanacceptableformforthe codegenerator.Thecodegeneratorthenwritestheresultofcompilingthistreeontothestandardoutput.Insteadof‘[’and‘]’linesintheintermediatefile,theinformationispasseddirectly tothesecondpassroutines.Assemblycodeproducedbythefirstpassissimplywrittenout,withouttheneedfor’)’attheheadofeachline. TheSourceFiles Thecompilersourceconsistsof22sourcefiles.Twofiles,manifestandmacdefs,areheader filesincludedwithallotherfiles.Manifesthasdeclarationsforthenodenumbers,types,storage classes,andotherglobaldatadefinitions.Macdefshasmachine-dependentdefinitions,suchasthe sizeandalignmentofthevariousdatarepresentations.Twomachineindependentheaderfiles, mfile1andmfile2,containthedatastructureandmanifestdefinitionsforthefirstandsecond passes,respectively.Inthesecondpass,amachinedependentheaderfile,mac2defs,containsdeclarationsofregisternames,etc. Thereisafile,common,containing(machineindependent)routinesusedinbothpasses. Theseincluderoutinesforallocatingandfreeingtrees,walkingovertrees,printingdebugging information,andprintingerrormessages.Therearetwodummyfiles,comm1.candcomm2.c, thatsimplyincludecommonwithinthescopeoftheappropriatepass1orpass2headerfiles. Whenthecompilerisloadedasasinglepass,commononlyneedstobeincludedonce:comm2.cis notneeded. Entiresectionsofthisdocumentaredevotedtothedetailedstructureofthepasses.Forthe moment,wejustgiveabriefdescriptionofthefiles.Thefirstpassisobtainedbycompilingand loadingscan.c,cgram.c,xdefs.c,pftn.c,trees.c,optim.c,local.c,code.c,andcomm1.c.Scan.cisthe lexicalanalyzer,whichisusedbycgram.c,theresultofapplyingYacc6totheinputgrammar cgram.y.Xdefs.cisashortfileofexternaldefinitions.Pftn.cmaintainsthesymboltable,and doesinitialization.Trees.cbuildstheexpressiontrees,andcomputesthenodetypes.Optim.c doessomemachineindependentoptimizationsontheexpressiontrees.Comm1.cincludescommon,thatcontainsserviceroutinescommontothetwopassesofthecompiler.Alltheabovefiles aremachineindependent.Thefileslocal.candcode.ccontainmachinedependentcodeforgeneratingsubroutineprologs,switchcode,andthelike. Thesecondpassisproducedbycompilingandloadingreader.c,allo.c,match.c,comm1.c, order.c,local.c,andtable.c.Reader.creadstheintermediatefile,andcontrolsthemajorlogicof thecodegeneration.Allo.ckeepstrackofbusyandfreeregisters.Match.ccontrolsthematching ofcodetemplatestosubtreesoftheexpressiontreetobecompiled.Comm2.cincludesthefile common,asinthefirstpass.Theabovefilesaremachineindependent.Order.ccontrolsthe machinedependentdetailsofthecodegenerationstrategy.Local2.chasmanysmallmachine dependentroutines,andtablesofopcodes,registertypes,etc.Table.chasthecodetemplate tables,whicharealsoclearlymachinedependent. DataStructureConsiderations. Thissectiondiscussesthenodenumbers,typewords,andexpressiontrees,usedthroughout bothpassesofthecompiler. Thefilemanifestdefinesthosesymbolsusedthroughoutbothpasses.Theintentistouse thesamesymbolname(e.g.,MINUS)forthegivenoperatorthroughoutthelexicalanalysis,parsing,treebuilding,andcodegenerationphases;thisrequiressomesynchronizationwiththeYacc inputfile,cgram.y,aswell.

-4-AtokenlikeMINUSmaybeseeninthelexicalanalyzerbeforeitisknownwhetheritisa unaryorbinaryoperator;clearly,itisnecessarytoknowthisbythetimetheparsetreeisconstructed.Thus,anoperator(reallyamacro)calledUNARYisprovided,sothatMINUSand UNARYMINUSarebothdistinctnodenumbers.Similarly,manybinaryoperatorsexistinan assignmentform(forexample,−=),andtheoperatorASGmaybeappliedtosuchnodenamesto generatenewones,e.g.ASGMINUS. Itisfrequentlydesirabletoknowifanoderepresentsaleaf(nodescendants),aunaryoperator(onedescendant)orabinaryoperator(twodescendants).Themacrooptype(o)returnsoneof themanifestconstantsLTYPE,UTYPE,orBITYPE,respectively,dependingonthenode numbero.Similarly,asgop(o)returnstrueifoisanassignmentoperatornumber(=,+=,etc.), andlogop(o)returnstrueifoisarelationalorlogical(&&,||,or!)operator. Chasarichtypingstructure,withapotentiallyinfinitenumberoftypes.Tobeginwith, therearethebasictypes:CHAR,SHORT,INT,LONG,theunsignedversionsknownasUCHAR, USHORT,UNSIGNED,ULONG,andFLOAT,DOUBLE,andfinallySTRTY(astructure), UNIONTY,andENUMTY.Then,therearethreeoperatorsthatcanbeappliedtotypestomake others:iftisatype,wemaypotentiallyhavetypespointertot,functionreturningt,andarrayof t’sgeneratedfromt.Thus,anarbitrarytypeinCconsistsofabasictype,andzeroormoreof theseoperators. Inthecompiler,atypeisrepresentedbyanunsignedinteger;therightmostfourbitshold thebasictype,andtheremainingbitsaredividedintotwo-bitfields,containing0(nooperator), oroneofthethreeoperatorsdescribedabove.Themodifiersarereadrighttoleftintheword, startingwiththetwo-bitfieldadjacenttothebasictype,untilafieldwith0initisreached.The macrosPTR,FTN,andARYrepresentthepointerto,functionreturning,andarrayofoperators. Themacrovaluesareshiftedsothattheyalignwiththefirsttwo-bitfield;thusPTR+INTrepre-sentsthetypeforanintegerpointer,and ARY+(PTR<<2)+(FTN<<4)+DOUBLE representsthetypeofanarrayofpointerstofunctionsreturningdoubles. Thetypewordsareordinarilymanipulatedbymacros.Iftisatypeword,BTYPE(t)gives thebasictype.ISPTR(t),ISARY(t),andISFTN(t)askifanobjectofthistypeisapointer, array,orafunction,respectively.MODTYPE(t,b)setsthebasictypeofttob.DECREF(t)gives thetyperesultingfromremovingthefirstoperatorfromt.Thus,iftisapointertot’,afunction returningt’,oranarrayoft’,thenDECREF(t)wouldequalt’.INCREF(t)givesthetyperepresentingapointertot.Finally,thereareoperatorsfordealingwiththeunsignedtypes.ISUN-SIGNED(t)returnstrueiftisoneofthefourbasicunsignedtypes;inthiscase,DEUNSIGN(t) givestheassociated‘signed’type.Similarly,UNSIGNABLE(t)returnstrueiftisoneofthefour basictypesthatcouldbecomeunsigned,andENUNSIGN(t)returnstheunsignedanalogueoftin thiscase. Theotherimportantglobaldatastructureisthatofexpressiontrees.Theactualshapesof thenodesaregiveninmfile1andmfile2.Theyarenotthesameinthetwopasses;thefirstpass nodescontaindimensionandsizeinformation,whilethesecondpassnodescontainregisterallocationinformation.Nevertheless,allnodescontainfieldscalledop,containingthenodenumber, andtype,containingthetypeword.Afunctioncalledtalloc()returnsapointertoanewtree node.Tofreeanode,itsopfieldneedmerelybesettoFREE.Theotherfieldsinthenodewill remainintactatleastuntilthenextallocation. Nodesrepresentingbinaryoperatorscontainfields,leftandright,thatcontainpointersto theleftandrightdescendants.Unaryoperatornodeshavetheleftfield,andavaluefieldcalled rval.Leafnodes,withnodescendants,havetwovaluefields:lvalandrval. Atappropriatetimes,thefunctiontcheck()canbecalled,tocheckthattherearenobusy nodesremaining.Thisisusedasacompilerconsistencycheck.Thefunctiontcopy(p)takesa pointerpthatpointstoanexpressiontree,andreturnsapointertoadisjointcopyofthetree. Thefunctionwalkf(p,f)performsapostorderwalkofthetreepointedtobyp,andappliesthe -5-functionftoeachnode.Thefunctionfwalk(p,f,d)doesapreorderwalkofthetreepointedtoby p.Ateachnode,itcallsafunctionf,passingtoitthenodepointer,avaluepasseddownfromits ancestor,andtwopointerstovaluestobepasseddowntotheleftandrightdescendants(ifany). Thevaluedisthevaluepasseddowntotheroot.Fwalkisusedforanumberoftreelabelingand debuggingactivities. Theothermajordatastructure,thesymboltable,existsonlyinpassone,andwillbediscussedlater. PassOne Thefirstpassdoeslexicalanalysis,parsing,symboltablemaintenance,treebuilding,optimization,andanumberofmachinedependentthings.Thispassislargelymachineindependent, andthemachineindependentsectionscanbeprettysuccessfullyignored.Thus,theywillbeonly sketchedhere. LexicalAnalysis Thelexicalanalyzerisaconceptuallysimpleroutinethatreadstheinputandreturnsthe tokensoftheClanguageasitencountersthem:names,constants,operators,andkeywords.The conceptualsimplicityofthisjobisconfoundedabitbyseveralothersimplejobsthatunfortunatelymustgoonsimultaneously.Theseinclude •Keepingtrackofthecurrentfilenameandlinenumber,andoccasionallysettingthisinformationastheresultofpreprocessorcontrollines. •Skippingcomments. •Properlydealingwithoctal,decimal,hex,floatingpoint,andcharacterconstants,aswellas characterstrings. Toachievespeed,theprogrammaintainsseveraltablesthatareindexedintobycharacter value,totellthelexicalanalyzerwhattodonext.Toachieveportability,thesetablesmustbe initializedeachtimethecompilerisrun,inorderthatthetableentriesreflectthelocalcharacter setvalues. Parsing Asmentionedabove,theparserisgeneratedbyYaccfromthegrammaronfilecgram.y. Thegrammarisrelativelyreadable,butcontainssomeunusualfeaturesthatareworthcomment. Perhapsthestrangestfeatureofthegrammaristhetreatmentofdeclarations.Theproblem istokeeptrackofthebasictypeandthestorageclasswhileinterpretingthevariousstars,brackets,andparenthesesthatmaysurroundagivenname.Theentiredeclarationmechanismmustbe recursive,sincedeclarationsmayappearwithindeclarationsofstructuresandunions,oreven withinasizeofconstructioninsideadimensioninanotherdeclaration! Therearesomedifficultiesinusingabottom-upparser,suchasproducedbyYacc,tohandle constructionswherealotofleftcontextinformationmustbekeptaround.Theproblemisthat theoriginalPDP-11compileristop-downinimplementation,andsomeofthesemanticsofC reflectthis.Inatop-downparser,theinputrulesarerestrictedsomewhat,butonecannaturally associatetemporarystoragewitharuleataveryearlystageintherecognitionofthatrule.Ina bottom-upparser,thereismorefreedominthespecificationofrules,butitismoredifficultto knowwhatruleisbeingmatcheduntiltheentireruleisseen.Theparserdescribedbycgram.c makeseffectiveuseofthebottom-upparsingmechanisminsomeplaces(notablythetreatmentof expressions),butstrugglesagainsttherestrictionsinothers.Theusualresultisthatitisnecessarytorunastackofvalues‘‘ontheside’’,independentoftheYaccvaluestack,inordertobe abletostoreandaccessinformationdeepwithininnerconstructions,wheretherelationshipofthe rulesbeingrecognizedtothetotalpictureisnotyetclear. Inthecaseofdeclarations,theattributeinformation(type,etc.)foradeclarationiscarefullykeptimmediatelytotheleftofthedeclarator(thatpartofthedeclarationinvolvingthe -6-name).Inthisway,whenitistimetodeclarethename,thenameandthetypeinformationcan bequicklybroughttogether.The‘‘$0’’mechanismofYaccisusedtoaccomplishthis.Theresult isnotpretty,butitworks.Thestorageclassinformationchangesmoreslowly,soitiskeptinan externalvariable,andstackedifnecessary.Someofthegrammarcouldbeconsiderablycleaned upbyusingsomemorerecentfeaturesofYacc,notablyactionswithinrulesandtheabilityto returnmultiplevaluesforactions. Astackisalsousedtokeeptrackofthecurrentlocationtobebranchedtowhenabreakor continuestatementisprocessed. ThisuseofexternalstacksdatesfromthetimewhenYaccdidnotpermitvaluestobestructures.Some,ormost,ofthisuseofexternalstackscouldbeeliminatedbyredoingthegrammar tousethemechanismsnowprovided.Therearesomeareas,however,particularlytheprocessing ofstructure,union,andenumdeclarations,functionprologs,andswitchstatementprocessing, whenhavingalltheaffecteddatatogetherinanarrayspeedslaterprocessing;inthiscase,useof externalstorageseemsessential. Thecgram.yfilealsocontainssomesmallfunctionsusedasutilityfunctionsintheparser. Theseincluderoutinesforsavingcasevaluesandlabelsinprocessingswitches,andstackingand poppingvaluesontheexternalstackdescribedabove. StorageClasses Chasafinite,butfairlyextensive,numberofstorageclassesavailable.Oneofthecompiler designdecisionswastoprocessthestorageclassinformationtotallyinthefirstpass;bythesecondpass,thisinformationmusthavebeentotallydealtwith.Thismeansthatallofthestorage allocationmusttakeplaceinthefirstpass,sothatreferencestoautomaticsandparameterscan beturnedintoreferencestocellslyingacertainnumberofbytesoffsetfromcertainmachineregisters.Muchofthistransformationismachinedependent,andstronglydependsonthestorage class. TheclassesincludeEXTERN(forexternallydeclared,butnotdefinedvariables),EXTDEF (forexternaldefinitions),andsimilardistinctionsforUSTATICandSTATIC,UFORTRANand FORTRAN(forfortranfunctions)andULABELandLABEL.ThestorageclassesREGISTER andAUTOareobvious,asareSTNAME,UNAME,andENAME(forstructure,union,andenumerationtags),andtheassociatedMOS,MOU,andMOE(forthemembers).TYPEDEFis treatedasastorageclassaswell.Therearetwospecialstorageclasses:PARAMandSNULL. SNULLisusedtodistinguishthecasewherenoexplicitstorageclasshasbeengiven;beforean entryismadeinthesymboltablethetruestorageclassisdiscovered.Similarly,PARAMisused forthetemporaryentryinthesymboltablemadebeforethedeclarationoffunctionparametersis completed. Themostcomplexityinthestorageclassprocesscomesfrombitfields.Aseparatestorage classiskeptforeachwidthbitfield;akbitbitfieldhasstorageclasskplusFIELD.Thisenables thesizetobequicklyrecoveredfromthestorageclass. SymbolTableMaintenance. Thesymboltableroutinesdofarmorethansimplyenternamesintothesymboltable;considerablesemanticprocessingandcheckingisdoneaswell.Forexample,ifanewdeclaration comesin,itmustbecheckedtoseeifthereisapreviousdeclarationofthesamesymbol.Ifthere is,therearemanycases.Thedeclarationsmayagreeandbecompatible(forexample,anextern declarationcanappeartwice)inwhichcasethenewdeclarationisignored.Thenewdeclaration mayaddinformation(suchasanexplicitarraydimension)toanalreadypresentdeclaration.The newdeclarationmaybedifferent,butstillcorrect(forexample,anexterndeclarationofsomethingmaybeentered,andthenlaterthedefinitionmaybeseen).Thenewdeclarationmaybe incompatible,butappearinaninnerblock;inthiscase,theolddeclarationiscarefullyhidden away,andthenewonecomesintoforceuntiltheblockisleft.Finally,thedeclarationsmaybe incompatible,andanerrormessagemustbeproduced.

-7-Anumberofotherfactorsmakeforadditionalcomplexity.Thetypedeclaredbytheuseris notalwaysthetypeenteredintothesymboltable(forexample,ifanformalparametertoafunctionisdeclaredtobeanarray,Crequiresthatthisbechangedintoapointerbeforeentryinthe symboltable).Moreover,therearevariouskindsofillegaltypesthatmaybedeclaredwhichare difficulttocheckforsyntactically(forexample,afunctionreturninganarray).Finally,thereisa strangefeatureinCthatrequiresstructuretagnamesandmembernamesforstructuresand unionstobetakenfromadifferentlogicalsymboltablethanordinaryidentifiers.Keepingtrack ofwhichkindofnameisinvolvedisabitofstruggle(considertypedefnamesusedwithinstructuredeclarations,forexample). Thesymboltablehandlingroutineshavebeenrewrittenanumberoftimestoextendfeatures,improveperformance,andfixbugs.Theyaddresstheaboveproblemswithreasonableeffectivenessbutasingularlackofgrace. Whenanameisreadintheinput,itishashed,andtheroutinelookupiscalled,together withaflagwhichtellswhichsymboltableshouldbesearched(actually,bothsymboltablesare storedinone,andaflagisusedtodistinguishindividualentries).Ifthenameisfound,lookup returnstheindextotheentryfound;otherwise,itmakesanewentry,marksitUNDEF(undefined),andreturnstheindexofthenewentry.ThisindexisstoredinthervalfieldofaNAME node. Whenadeclarationisbeingparsed,thisNAMEnodeismadepartofatreewithUNARY MULnodesforeach*,LBnodesforeacharraydescriptor(therightdescendanthasthedimension),andUNARYCALLnodesforeachfunctiondescriptor.Thistreeispassedtotheroutine tymerge,alongwiththeattributetypeofthewholedeclaration;thisroutinecollapsesthetreetoa singlenode,bycallingtyreduce,andthenmodifiesthetypetoreflecttheoveralltypeofthedeclaration. Dimensionandsizeinformationisstoredinatablecalleddimtab.Toproperlydescribea typeinC,oneneedsnotjustthetypeinformationbutalsosizeinformation(forstructuresand enums)anddimensioninformation(forarrays).Sizesandoffsetsaredealtwithinthecompiler bygivingtheassociatedindicesintodimtab.Tymergeandtyreducecalldstashtoputthediscovereddimensionsawayintothedimtabarray.Tymergereturnsapointertoasinglenodethatcontainsthesymboltableindexinitsrvalfield,andthesizeanddimensionindicesinfieldscsizand cdim,respectively.Thisinformationisproperlyconsideredpartofthetypeinthefirstpass,and iscarriedaroundatalltimes. Toenteranelementintothesymboltable,theroutinedefidiscalled;itishandedastorage class,andapointertothenodeproducedbytymerge.Defidcallsfixtype,whichadjustsand checksthegiventypedependingonthestorageclass,andconvertsnulltypesappropriately.It thencallsfixclass,whichdoesasimilarjobforthestorageclass;itishere,forexample,thatregisterdeclarationsareeitherallowedorchangedtoauto. Thenewdeclarationisnowcomparedagainstanolderone,ifpresent,andseveralpagesof validitychecksperformed.Ifthedefinitionsarecompatible,withpossiblysomeaddedinformation,theprocessingisstraightforward.Ifthedefinitionsdiffer,theblocklevelsofthecurrentand theolddeclarationarecompared.Thecurrentblockleveliskeptinblevel,anexternalvariable; theolddeclarationleveliskeptinthesymboltable.Blocklevel0isforexternaldeclarations,1is forargumentstofunctions,and2andaboveareblockswithinafunction.Ifthecurrentblock levelisthesameastheolddeclaration,anerrorresults.Ifthecurrentblocklevelishigher,the newdeclarationoverridestheold.Thisisdonebymarkingtheoldsymboltableentry‘‘hidden’’, andmakinganewentry,marked‘‘hiding’’.Lookupwillskipoverhiddenentries.Whenablockis left,thesymboltableissearched,andanyentriesdefinedinthatblockaredestroyed;iftheyhid otherentries,theoldentriesare‘‘unhidden’’. Thisniceblockstructureiswarpedabitbecauselabelsdonotfollowtheblockstructure rules(onecandoagotointoablock,forexample);defaultdefinitionsoffunctionsininnerblocks alsopersistclearouttotheoutermostscope.Thisimpliesthatcleaningupthesymboltableafter blockexitismoresubtlethanitmightfirstseem.

-8-Forsuccessfulnewdefinitions,defidalsoinitializesa‘‘generalpurpose’’field,offset,inthe symboltable.Itcontainsthestackoffsetforautomaticsandparameters,theregisternumberfor registervariables,thebitoffsetintothestructureforstructuremembers,andtheinternallabel numberforstaticvariablesandlabels.Theoffsetfieldissetbyfallocforbitfields,anddclstruct forstructuresandunions. Thesymboltableentryitselfthuscontainsthename,typeword,sizeanddimensionoffsets, offsetvalue,anddeclarationblocklevel.Italsohasafieldofflags,describingwhatsymboltable thenameisin,andwhethertheentryishidden,orhidesanother.Finally,afieldgivestheline numberofthelastuse,orofthedefinition,ofthename.Thisisusedmainlyfordiagnostics,but isusefultolintaswell. Insomespecialcases,thereismorethantheaboveamountofinformationkeptfortheuse ofthecompiler.Thisisespeciallytruewithstructures;foruseininitialization,structuredeclarationsmusthaveaccesstoalistofthemembersofthestructure.Thislistisalsokeptindimtab. Becauseastructurecanbementionedlongbeforethemembersareknown,itisnecessarytohave anotherlevelofindirectioninthetable.Thetwowordsfollowingthecsizentryindimtabare usedtoholdthealignmentofthestructure,andtheindexindimtabofthelistofmembers.This listcontainsthesymboltableindicesforthestructuremembers,terminatedbya−1. TreeBuilding Theportablecompilertransformsexpressionsintoexpressiontrees.Astheparserrecognizes eachrulemakingupanexpression,itcallsbuildtreewhichisgivenanoperatornumber,andpointerstotheleftandrightdescendants.Buildtreefirstexaminestheleftandrightdescendants,and, iftheyarebothconstants,andtheoperatorisappropriate,simplydoestheconstantcomputation atcompiletime,andreturnstheresultasaconstant.Otherwise,buildtreeallocatesanodeforthe headofthetree,attachesthedescendantstoit,andensuresthatconversionoperatorsaregeneratedifneeded,andthatthetypeofthenewnodeisconsistentwiththetypesoftheoperands. Thereisalsoaconsiderableamountofsemanticcomplexityhere;manycombinationsoftypesare illegal,andtheportablecompilermakesastrongefforttocheckthelegalityofexpressiontypes completely.Thisisdonebothforlintpurposes,andtopreventsuchsemanticerrorsfrombeing passedthroughtothecodegenerator. Theheartofbuildtreeisalargetable,accessedbytheroutineopact.Thisroutinemapsthe typesoftheleftandrightoperandsintoarathersmallersetofdescriptors,andthenaccessesa table(actuallyencodedinaswitchstatement)whichforeachoperatorandpairoftypescausesan actiontobereturned.Theactionsarelogicalor’sofanumberofseparateactions,whichmaybe carriedoutbybuildtree.Thesecomponentactionsmayincludecheckingtheleftsidetoensure thatitisanlvalue(canbestoredinto),applyingatypeconversiontotheleftorrightoperand, settingthetypeofthenewnodetothetypeoftheleftorrightoperand,callingvariousroutines tobalancethetypesoftheleftandrightoperands,andsuppressingtheordinaryconversionof arraysandfunctionoperandstopointers.AnimportantoperationisOTHER,whichcausessome specialcodetobeinvokedinbuildtree,tohandleissueswhichareuniquetoaparticularoperator. Examplesofthisarestructureandunionreference(actuallyhandledbytheroutinestref),the buildingofNAME,ICON,STRINGandFCON(floatingpointconstant)nodes,unary*and&, structureassignment,andcalls.Inthecaseofunary*and&,buildtreewillcancela*appliedto atree,thetopnodeofwhichis&,andconversely. AnotherspecialoperationisPUN;thiscausesthecompilertocheckfortypemismatches, suchasintermixingpointersandintegers. Thetreatmentofconversionoperatorsisstillaratherstrangeareaofthecompiler(andof C!).Therecentintroductionoftypecastshasonlyconfoundedthissituation.Mostoftheconversionoperatorsaregeneratedbycallstotymatchandptmatch,bothofwhicharegivenatree, andaskedtomaketheoperandsagreeintype.Ptmatchtreatsthecasewhereoneoftheoperands isapointer;tymatchtreatsallothercases.Wheretheseroutineshavedecidedonthepropertype foranoperand,theycallmakety,whichishandedatree,andatypeword,dimensionoffset,and sizeoffset.Ifnecessary,itinsertsaconversionoperationtomakethetypescorrect.Conversion -9-operationsareneverinsertedontheleftsideofassignmentoperators,however.Therearetwo conversionoperatorsused;PCONV,iftheconversionistoanon-basictype(usuallyapointer), andSCONV,iftheconversionistoabasictype(scalar). Toallowformaximumflexibility,everynodeproducedbybuildtreeisgiventoamachine dependentroutine,clocal,immediatelyafteritisproduced.Thisistoallowmoreorlessimmediaterewritingofthosenodeswhichmustbeadaptedforthelocalmachine.Theconversionoperationsaregiventoclocalaswell;onmostmachines,manyoftheseconversionsdonothing,and shouldbethrownaway(beingcarefultoretainthetype).Ifthisoperationisdonetooearly,however,latercallstobuildtreemaygetconfusedaboutcorrecttypeofthesubtrees;thusclocalis giventheconversionopsonlyaftertheentiretreeisbuilt.Thistopicwillbedealtwithinmore detaillater. Initialization Initializationisoneofthemessierareasintheportablecompiler.Theonlyconsolationis thatmostofthemesstakesplaceinthemachineindependentpart,whereitismaybesafely ignoredbytheimplementorofthecompilerforaparticularmachine. Thebasicproblemisthatthesemanticsofinitializationreallycallsforaco-routinestruc-ture;onecollectionofprogramsreadingconstantsfromtheinputstream,whileanother,indepen-dentsetofprogramsplacestheseconstantsintotheappropriatespotsinmemory.Thedramatic differencesinthelocalassemblersalsocometotheforehere.Theparsingproblemsaredealtwith bykeepingaratherextensivestackcontainingthecurrentstateoftheinitialization;theassembler problemsaredealtwithbyhavingafairnumberofmachinedependentroutines. Thestackcontainsthesymboltablenumber,type,dimensionindex,andsizeindexforthe currentidentifierbeinginitialized.Anotherentryhastheoffset,inbits,ofthebeginningofthe currentidentifier.Anotherentrykeepstrackofhowmanyelementshavebeenseen,ifthecurrent identifierisanarray.Stillanotherentrykeepstrackofthecurrentmemberofastructurebeing initialized.Finally,thereisanentrycontainingflagswhichkeeptrackofthecurrentstateofthe initializationprocess(e.g.,tellifa}hasbeenseenforthecurrentidentifier.) Whenaninitializationbegins,theroutinebeginitiscalled;ithandlesthealignmentrestrictions,ifany,andcallsinstktocreatethestackentry.Thisisdonebyfirstmakinganentryonthe topofthestackfortheitembeinginitialized.Ifthetopentryisanarray,anotherentryismade onthestackforthefirstelement.Ifthetopentryisastructure,anotherentryismadeonthe stackforthefirstmemberofthestructure.Thiscontinuesuntilthetopelementofthestackisa scalar.Instkthenreturns,andtheparserbeginscollectinginitializers. Whenaconstantisobtained,theroutinedoinitiscalled;itexaminesthestack,anddoes whateverisnecessarytoassignthecurrentconstanttothescalaronthetopofthestack.gotscal isthencalled,whichrearrangesthestacksothatthenextscalartobeinitializedgetsplacedon topofthestack.Thisprocesscontinuesuntiltheendoftheinitializers;endinitcleansup.Ifa{ or}isencounteredinthestringofinitializers,itishandledbycallingilbraceorirbrace,respectively. Acentralissueisthetreatmentofthe‘‘holes’’thatariseasaresultofalignmentrestrictions orexplicitrequestsforholesinbitfields.Thereisaglobalvariable,inoff,whichcontainsthecurrentoffsetintheinitialization(alloffsetsinthefirstpassofthecompilerareinbits).Doinitfiguresoutfromthetopentryonthestacktheexpectedbitoffsetofthenextidentifier;itcallsthe machinedependentroutineinforcewhich,inamachinedependentway,forcestheassemblertoset asidespaceifneedbesothatthenextscalarseenwillgointotheappropriatebitoffsetposition. Thescalaritselfispassedtooneofthemachinedependentroutinesfincode(forfloatingpointinitialization),incode(forfields,andotherinitializationslessthananintinsize),andcinit(forall otherinitializations).Thesizeispassedtoalltheseroutines,anditisuptothemachinedependentroutinestoensurethattheinitializeroccupiesexactlytherightsize. Characterstringsrepresentabitofanexception.Ifacharacterstringisseenastheinitializerforapointer,thecharactersmakingupthestringmustbeputoutunderadifferentlocation -10-counter.Whenthelexicalanalyzerseesthequoteattheheadofacharacterstring,itreturnsthe tokenSTRING,butdoesnotdoanythingwiththecontents.Theparsercallsgetstr,whichsets uptheappropriatelocationcountersandflags,andcallslxstrtoreadandprocessthecontentsof thestring. Ifthestringisbeingusedtoinitializeacharacterarray,lxstrcallsputbyte,whichineffect simulatesdoinitforeachcharacterread.Ifthestringisusedtoinitializeacharacterpointer,lxstr callsamachinedependentroutine,bycode,whichstashesawayeachcharacter.Thepointertothis stringisthenreturned,andprocessednormallybydoinit. Thenullattheendofthestringistreatedasifitwerereadexplicitlybylxstr. Statements Thefirstpassaddressesfourmainareas;declarations,expressions,initialization,andstatements.Thestatementprocessingisrelativelysimple;mostofitiscarriedoutintheparser directly.Mostofthelogicisconcernedwithallocatinglabelnumbers,definingthelabels,and branchingappropriately.Anexternalsymbol,reached,is1ifastatementcanbereached,0otherwise;thisisusedtodoabitofsimpleflowanalysisastheprogramisbeingparsed,andalsoto avoidgeneratingthesubroutinereturnsequenceifthesubroutinecannot‘‘fallthrough’’thelast statement. Conditionalbranchesarehandledbygeneratinganexpressionnode,CBRANCH,whoseleft descendantistheconditionalexpressionandtherightdescendantisanICONnodecontainingthe internallabelnumbertobebranchedto.Forefficiency,thesemanticsarethatthelabelisgoneto iftheconditionisfalse. Theswitchstatementiscompiledbycollectingthecaseentries,andanindicationasto whetherthereisadefaultcase;aninternallabelnumberisgeneratedforeachofthese,and rememberedinabigarray.Theexpressioncomprisingthevaluetobeswitchedoniscompiled whentheswitchkeywordisencountered,buttheexpressiontreeisheadedbyaspecialnode, FORCE,whichtellsthecodegeneratortoputtheexpressionvalueintoaspecialdistinguished register(thissamemechanismisusedforprocessingthereturnstatement).Whentheendofthe switchblockisreached,thearraycontainingthecasevaluesissorted,andcheckedforduplicate entries(anerror);ifalliscorrect,themachinedependentroutinegenswitchiscalled,withthis arrayoflabelsandvaluesinincreasingorder.Genswitchcanassumethatthevaluetobetested isalreadyintheregisterwhichistheusualintegerreturnvalueregister. Optimization Thereisamachineindependentfile,optim.c,whichcontainsarelativelyshortoptimization routine,optim.Actuallythewordoptimizationissomethingofamisnomer;theresultsarenot optimum,onlyimproved,andtheroutineisinfactnotoptional;itmustbecalledforproperoperationofthecompiler. Optimiscalledafteranexpressiontreeisbuilt,butbeforethecodegeneratoriscalled.The essentialpartofitsjobistocallclocalontheconversionoperators.Onmostmachines,thetreatmentof&isalsoessential:bythistimeintheprocessing,theonlynodewhichisalegaldescendantof&isNAME.(Possibledescendantsof*havebeeneliminatedbybuildtree.)Theaddress ofastaticnameis,almostbydefinition,aconstant,andcanberepresentedbyanICONnodeon mostmachines(providedthattheloaderhasenoughpower).Unfortunately,thisisnotuniversallytrue;onsomemachine,suchastheIBM370,theissueofaddressabilityrearsitsuglyhead; thus,beforeturningaNAMEnodeintoanICONnode,themachinedependentfunctionandable iscalled. Theoptimizationattemptsofoptimarecurrentlyquitelimited.Itisprimarilyconcerned withimprovingthebehaviorofthecompilerwithoperationsoneofwhoseargumentsisaconstant.Inthesimplestcase,theconstantisplacedontherightiftheoperationiscommutative. Thecompileralsomakesalimitedsearchforexpressionssuchas -11- (x+a)+b whereaandbareconstants,andattemptstocombineaandbatcompiletime.Anumberofspecialcasesarealsoexamined;additionsof0andmultiplicationsby1areremoved,althoughthe correctprocessingofthesecasestogetthetypeoftheresultingtreecorrectisdecidedlynontrivial.Insomecases,theadditionormultiplicationmustbereplacedbyaconversionoptokeepthe typesfrombecomingfouledup.Finally,incaseswherearelationaloperationisbeingdone,and oneoperandisaconstant,theoperandsarepermuted,andtheoperatoraltered,ifnecessary,to puttheconstantontheright.Finally,multiplicationsbyapowerof2arechangedtoshifts. Therearedozensofsimilaroptimizationsthatcanbe,andshouldbe,done.Itseemslikely thatthisroutinewillbeexpandedintherelativelynearfuture. MachineDependentStuff Anumberofthefirstpassmachinedependentroutineshavebeendiscussedabove.Ingeneral,theroutinesareshort,andeasytoadaptfrommachinetomachine.Thetwoexceptionsto thisgeneralruleareclocalandthefunctionprologandepiloggenerationroutines,bfcodeand efcode. Clocalhasthejobofrewriting,ifappropriateanddesirable,thenodesconstructedby buildtree.Therearetwomajorareaswherethisisimportant;NAMEnodesandconversionoperations.InthecaseofNAMEnodes,clocalmustrewritetheNAMEnodetoreflecttheactualphysicallocationofthenameinthemachine.Ineffect,theNAMEnodemustbeexamined,thesymboltableentryfound(throughthervalfieldofthenode),and,basedonthestorageclassofthe node,thetreemustberewritten.Automaticvariablesandparametersaretypicallyrewrittenby treatingthereferencetothevariableasastructurereference,offtheregisterwhichholdsthe stackorargumentpointer;thestrefroutineissetuptobecalledinthisway,andtobuildthe appropriatetree.Inthemostgeneralcase,thetreeconsistsofaunary*node,whosedescendant isa+node,withthestackorargumentregisterasleftoperand,andaconstantoffsetasright operand.InthecaseofLABELandinternalstaticnodes,thervalfieldisrewrittentobethenegativeoftheinternallabelnumber;anegativervalfieldistakentobeaninternallabelnumber. Finally,anameofclassREGISTERmustbeconvertedintoaREGnode,andthervalfield replacedbytheregisternumber.Infact,thispartoftheclocalroutineisnearlymachineindependent;onlyformachineswithaddressabilityproblems(IBM370again!)doesithavetobenoticeablydifferent, Theconversionoperatortreatmentisrathertricky.Itisnecessarytohandletheapplication ofconversionoperatorstoconstantsinclocal,inorderthatallconstantexpressionscanhavetheir valuesknownatcompiletime.Inextremecases,thismaymeanthatsomesimulationofthe arithmeticofthetargetmachinemighthavetobedoneinacross-compiler.Inthemostcommon case,conversionsfrompointertopointerdonothing.Forsomemachines,however,conversion frombytepointertoshortorlongpointermightrequireashiftorrotateoperation,whichwould havetobegeneratedhere. Theextensionoftheportablecompilertomachineswherethesizeofapointerdependson itstypewouldbestraightforward,buthasnotyetbeendone. Theothermajormachinedependentissueinvolvesthesubroutineprologandepiloggeneration.Thehardparthereisthedesignofthestackframeandcallingsequence;thisdesignissueis discussedelsewhere.7Theroutinebfcodeiscalledwiththenumberofargumentsthefunctionis definedwith,andanarraycontainingthesymboltableindicesofthedeclaredparameters.Bfcode mustgeneratethecodetoestablishthenewstackframe,savethereturnaddressandprevious stackpointervalueonthestack,andsavewhateverregistersaretobeusedforregistervariables. Thestacksizeandthenumberofregistervariablesisnotknownwhenbfcodeiscalled,sothese numbersmustbereferredtobyassemblerconstants,whicharedefinedwhentheyareknown(usuallyinthesecondpass,afterallregistervariables,automatics,andtemporarieshavebeenseen). Thefinaljobistofindthoseparameterswhichmayhavebeendeclaredregister,andgeneratethe codetoinitializetheregisterwiththevaluepassedonthestack.Onceagain,formostmachines, -12-thegenerallogicofbfcoderemainsthesame,butthecontentsoftheprintfcallsinitwillchange frommachinetomachine.efcodeisrathersimpler,havingjusttogeneratethedefaultreturnat theendofafunction.Thismaybenontrivialinthecaseofafunctionreturningastructureor union,however. Thereseemstobenoreallygoodplacetodiscussstructuresandunions,butthisisasgood aplaceasany.TheClanguagenowsupportsstructureassignment,andthepassingofstructures asargumentstofunctions,andthereceivingofstructuresbackfromfunctions.Thiswasadded ratherlatetoC,andthustotheportablecompiler.Consequently,itfitsinlesswellthanthe olderfeatures.Moreover,mostoftheburdenofmakingthesefeaturesworkisplacedonthe machinedependentcode. Therearebothconceptualandpracticalproblems.Conceptually,thecompilerisstructured aroundtheideathattocomputesomething,youputitintoaregisterandworkonit.Thisnotion causesabitoftroubleonsomemachines(e.g.,machineswith3-addressopcodes),butmatches manymachinesquitewell.Unfortunately,thisnotionbreaksdownwithstructures.Theclosest thatonecancomeistokeeptheaddressesofthestructuresinregisters.Theactualcode sequencesusedtomovestructuresvaryfromthetrivial(amultiplebytemove)tothehorrible(a functioncall),andareverymachinedependent. Thepracticalproblemismorepainful.Whenafunctionreturningastructureiscalled,this functionhastohavesomeplacetoputthestructurevalue.Ifitplacesitonthestack,ithasdifficultypoppingitsstackframe.Ifitplacesthevalueinastatictemporary,theroutinefailstobe reentrant.Themostlogicallyconsistentwayofimplementingthisisforthecallertopassina pointertoaspotwherethecalledfunctionshouldputthevaluebeforereturning.Thisisrelativelystraightforward,althoughabittedious,toimplement,butmeansthatthecallermusthave properlydeclaredthefunctiontype,evenifthevalueisneverused.Onsomemachines,suchas theInterdata8/32,thereturnvaluesimplyoverlaystheargumentregion(whichonthe8/32is partofthecaller’sstackframe).Thecallertakescareofleavingenoughroomifthereturned valueislargerthanthearguments.Thisalsoassumesthatthecallerknowanddeclaresthefunctionproperly. ThePDP-11andtheVAXhavestackhardwarewhichisusedinfunctioncallsandreturns; thismakesitveryinconvenienttouseeitheroftheabovemechanisms.Inthesemachines,astatic areawithinthecalledfunctionisallocated,andthefunctionreturnvalueiscopiedintoiton return;thefunctionreturnstheaddressofthatregion.Thisissimpletoimplement,butisnonreentrant.However,thefunctioncannowbecalledasasubroutinewithoutbeingproperly declared,withoutthedisasterwhichwouldotherwiseensue.Nomatterwhatchoiceistaken,the conventionisthatthefunctionactuallyreturnstheaddressofthereturnstructurevalue. Inbuildingexpressiontrees,theportablecompilertakesabitforgrantedaboutstructures. Itassumesthatfunctionsreturningstructuresactuallyreturnapointertothestructure,andit assumesthatareferencetoastructureisactuallyareferencetoitsaddress.Thestructureassignmentoperatorisrebuiltsothattheleftoperandisthestructurebeingassignedto,buttheright operandistheaddressofthestructurebeingassigned;thismakesiteasiertodealwith a=b=c andsimilarconstructions. Therearefourspecialtreenodesassociatedwiththeseoperations:STASG(structureassignment),STARG(structureargumenttoafunctioncall),andSTCALLandUNARYSTCALL (callsofafunctionwithnonzeroandzeroarguments,respectively).Thesefournodesareunique inthatthesizeandalignmentinformation,whichcanbedeterminedbythetypeforallother objectsinC,mustbeknowntocarryouttheseoperations;specialfieldsaresetasideinthese nodestocontainthisinformation,andspecialintermediatecodeisusedtotransmitthisinformation.

-13-FirstPassSummary Therearemayotherissueswhichhavebeenignoredhere,partlytojustifythetitle‘‘tour’’, andpartiallybecausetheyhaveseemedtocauselittletrouble.Therearesomedebuggingflags whichmaybeturnedon,bygivingthecompiler’sfirstpasstheargument −X[flags] Someofthemoreinterestingflagsare−Xdforthedefiningandfreeingofsymbols,−Xiforinitializationcomments,and−Xbforvariouscommentsaboutthebuildingoftrees.Inmanycases, repeatingtheflagmorethanoncegivesmoreinformation;thus,−Xdddgivesmoreinformation than−Xd.Inthetwopassversionofthecompiler,theflagsshouldnotbesetwhentheoutputis senttothesecondpass,sincethedebuggingoutputandtheintermediatecodebothgoontothe standardoutput. Weturnnowtoconsiderationofthesecondpass. PassTwo Codegenerationisfarlesswellunderstoodthanparsingorlexicalanalysis,andforthisreasonthesecondpassisfarhardertodiscussinafilebyfilemanner.Agreatdealofthedifficulty isinunderstandingtheissuesandthestrategiesemployedtomeetthem.Anyparticularfunction islikelytobereasonablystraightforward. Thus,thispartofthepaperwillconcentrateagooddealonthebroaderaspectsofstrategy inthecodegenerator,andwillnotgettoointimatewiththedetails. Overview. Itisdifficulttoorganizeacodegeneratortobeflexibleenoughtogeneratecodeforalarge numberofmachines,andstillbeefficientforanyoneofthem.Flexibilityisalsoimportantwhen itcomestimetotunethecodegeneratortoimprovetheoutputcodequality.Ontheotherhand, toomuchflexibilitycanleadtosemanticallyincorrectcode,andpotentiallyacombinatorialexplosioninthenumberofcasestobeconsideredinthecompiler. Onegoalofthecodegeneratoristohaveahighdegreeofcorrectness.Itisverydesirableto havethecompilerdetectitsowninabilitytogeneratecorrectcode,ratherthantoproduceincorrectcode.Thisgoalisachievedbyhavingasimplemodelofthejobtobedone(e.g.,anexpressiontree)andasimplemodelofthemachinestate(e.g.,whichregistersarefree).Theactofgeneratinganinstructionperformsatransformationonthetreeandthemachinestate;hopefully,the treeeventuallygetsreducedtoasinglenode.Ifeachoftheseinstruction/transformationpairsis correct,andifthemachinestatemodelreallyrepresentstheactualmachine,andifthetransformationsreducetheinputtreetothedesiredsinglenode,thentheoutputcodewillbecorrect. Formostrealmachines,thereisnodefinitivetheoryofcodegenerationthatencompassesall theCoperators.Thustheselectionofwhichinstruction/transformationstogenerate,andinwhat order,willhaveaheuristicflavor.If,forsomeexpressiontree,notransformationapplies,or,more seriously,iftheheuristicsselectasequenceofinstruction/transformationsthatdonotinfact reducethetree,thecompilerwillreportitsinabilitytogeneratecode,andabort. Amajorpartofthecodegeneratorisconcernedwiththemodelandthetransformations,— mostofthisismachineindependent,ordependsonlyonsimpletables.Theflexibilitycomesfrom theheuristicsthatguidethetransformationsofthetrees,theselectionofsubgoals,andtheorderingofthecomputation. TheMachineModel Themachineisassumedtohaveanumberofregisters,ofatmosttwodifferenttypes:Aand B.Withineachregisterclass,theremaybescratch(temporary)registersanddedicatedregisters (e.g.,registervariables,thestackpointer,etc.).Requeststoallocateandfreeregistersinvolve onlythetemporaryregisters.

-14-Eachoftheregistersinthemachineisgivenanameandanumberinthemac2defsfile;the numbersareusedasindicesintovarioustablesthatdescribetheregisters,sotheyshouldbekept small.Onesuchtableistherstatustableonfilelocal2.c.Thistableisindexedbyregisternumber,andcontainsexpressionsmadeupfrommanifestconstantsdescribingtheregistertypes: SAREGfordedicatedAREG’s,SAREG|STAREGforscratchAREGS’s,andSBREGand SBREG|STBREGsimilarlyforBREG’s.Therearemacrosthataccessthisinformation:isbreg(r) returnstrueifregisternumberrisaBREG,andistreg(r)returnstrueifregisternumberrisa temporaryAREGorBREG.Anothertable,rnames,containstheregisternames;thisisused whenputtingoutassemblercodeanddiagnostics. Theusageofregistersiskepttrackofbyanarraycalledbusy.Busy[r]isthenumberofuses ofregisterrinthecurrenttreebeingprocessed.Theallocationandfreeingofregisterswillbe discussedlateraspartofthecodegenerationalgorithm. GeneralOrganization Asmentionedabove,thesecondpassreadslinesfromtheintermediatefile,copyingthrough totheoutputunchangedanylinesthatbeginwitha‘)’,andmakingnoteoftheinformation aboutstackusageandregisterallocationcontainedonlinesbeginningwith‘]’and‘[’.Theexpressiontrees,whosebeginningisindicatedbyalinebeginningwith‘.’,arereadandrebuiltinto trees.Ifthecompilerisloadedasonepass,theexpressiontreesareimmediatelyavailabletothe codegenerator. Theactualcodegenerationisdonebyahierarchyofroutines.Theroutinedelayisfirst giventhetree;itattemptstodelaysomepostfix++and−−computationsthatmightreasonably bedoneafterthesmokeclears.Italsoattemptstohandlecomma(,)operatorsbycomputingthe leftsideexpressionfirst,andthenrewritingthetreetoeliminatetheoperator.Delaycallscodgen tocontroltheactualcodegenerationprocess.Codgentakesasargumentsapointertotheexpressiontree,andasecondargumentthat,forsocio-historicalreasons,iscalledacookie.Thecookie describesasetofgoalsthatwouldbeacceptableforthecodegeneration:theseareassignedto individualbits,sotheymaybelogicallyor’edtogethertoformalargenumberofpossiblegoals. AmongthepossiblegoalsareFOREFF(computeforsideeffectsonly;don’tworryaboutthe value),INTEMP(computeandstorevalueintoatemporarylocationinmemory),INAREG(computeintoanAregister),INTAREG(computeintoascratchAregister),INBREGandINTBREG similarly,FORCC(computeforconditioncodes),andFORARG(computeitasafunctionargument;e.g.,stackitifappropriate). Codgenfirstcanonicalizesthetreebycallingcanon.Thisroutinelooksforcertaintransformationsthatmightnowbeapplicabletothetree.One,whichisverycommonandverypowerful, istofoldtogetheranindirectionoperator(UNARYMUL)andaregister(REG);inmost machines,thiscombinationisaddressabledirectly,andsoissimilartoaNAMEinitsbehavior. TheUNARYMULandREGarefoldedtogethertomakeanothernodetypecalledOREG.In fact,inmanymachinesitispossibletodirectlyaddressnotjustthecellpointedtobyaregister, butalsocellsdifferingbyaconstantoffsetfromthecellpointedtobytheregister.Canonalso looksforsuchcases,callingthemachinedependentroutinenotofftodecideiftheoffsetisacceptable(forexample,intheIBM370theoffsetmustbebetween0and4095bytes).Anotheroptimizationistoreplacebitfieldoperationsbyshiftsandmasksiftheoperationinvolvesextracting thefield.Finally,amachinedependentroutine,sucomp,iscalledthatcomputestheSethi-Ullman numbersforthetree(seebelow). Afterthetreeiscanonicalized,codgencallstheroutinestorewhosejobistoselectasubtree ofthetreetobecomputedand(usually)storedbeforebeginningthecomputationofthefulltree. Storemustreturnatreethatcanbecomputedwithoutneedforanytemporarystoragelocations. Ineffect,theonlystoreoperationsgeneratedwhileprocessingthesubtreemustbeasaresponse toexplicitassignmentoperatorsinthetree.Thisdivisionofthejobmarksoneofthemoresignificant,andsuccessful,departuresfrommostothercompilers.Itmeansthatthecodegeneratorcan operateundertheassumptionthatthereareenoughregisterstodoitsjob,withoutworrying abouttemporarystorage.Ifastoreintoatemporaryappearsintheoutput,itisalwaysasa -15-directresultoflogicinthestoreroutine;thismakesdebuggingeasier. Oneconsequenceofthisorganizationisthatcodeisnotgeneratedbyatreewalk.Thereare theoreticalresultsthatsupportthisdecision.8Itmaybedesirabletocomputeseveralsubtreesand storethembeforetacklingthewholetree;ifasubtreeistobestored,thisisknownbeforethe codegenerationforthesubtreeisbegun,andthesubtreeiscomputedwhenallscratchregisters areavailable. Thestoreroutinedecideswhatsubtrees,ifany,shouldbestoredbymakinguseofnumbers, calledSethi-Ullmannumbers,thatgive,foreachsubtreeofanexpressiontree,theminimum numberofscratchregistersrequiredtocompilethesubtree,withoutanystoresintotemporaries.9 Thesenumbersarecomputedbythemachine-dependentroutinesucomp,calledbycanon.The basicnotionisthat,knowingtheSethi-Ullmannumbersforthedescendantsofanode,andknow-ingtheoperatorofthenodeandsomeinformationaboutthemachine,theSethi-Ullmannumber ofthenodeitselfcanbecomputed.IftheSethi-Ullmannumberforatreeexceedsthenumberof scratchregistersavailable,somesubtreemustbestored.Unfortunately,thetheorybehindthe Sethi-Ullmannumbersappliesonlytouselesslysimplemachinesandoperators.Fortherichsetof Coperators,andformachineswithasymmetricregisters,registerpairs,differentkindsofregisters,andexceptionalformsofaddressing,thetheorycannotbeapplieddirectly.Thebasicideaof estimationisagoodone,however,andwellworthapplying;theapplication,especiallywhenthe compilercomestobetunedforhighcodequality,goesbeyondtheparkoftheoryintotheswamp ofheuristics.Thistopicwillbetakenupagainlater,whenmoreofthecompilerstructurehas beendescribed. AfterexaminingtheSethi-Ullmannumbers,storeselectsasubtree,ifany,tobestored,and returnsthesubtreeandtheassociatedcookieintheexternalvariablesstotreeandstocook.Ifa subtreehasbeenselected,orifthewholetreeisreadytobeprocessed,theroutineorderiscalled, withatreeandcookie.Ordergeneratescodefortreesthatdonotrequiretemporarylocations. Ordermaymakerecursivecallsonitself,and,insomecases,oncodgen;forexample,whenprocessingtheoperators&&,||,andcomma(‘,’),thathavealefttorightevaluation,itisincorrect forstoreexaminetherightoperandforsubtreestobestored.Inthesecases,orderwillcallcodgen recursivelywhenitispermissibletoworkontherightoperand.Asimilarissueariseswiththe?: operator. Theorderroutineworksbymatchingthecurrenttreewithasetofcodetemplates.Ifa templateisdiscoveredthatwillmatchthecurrenttreeandcookie,theassociatedassemblylanguagestatementorstatementsaregenerated.Thetreeisthenrewritten,asspecifiedbythetemplate,torepresenttheeffectoftheoutputinstruction(s).Ifnotemplatematchisfound,firstan attemptismadetofindamatchwithadifferentcookie;forexample,inordertocomputean expressionwithcookieINTEMP(storeintoatemporarystoragelocation),itisusuallynecessary tocomputetheexpressionintoascratchregisterfirst.Ifallattemptstomatchthetreefail,the heuristicpartofthealgorithmbecomesdominant.Controlistypicallygiventooneofanumber ofmachine-dependentroutinesthatmayinturnrecursivelycallordertoachieveasubgoalofthe computation(forexample,oneoftheargumentsmaybecomputedintoatemporaryregister). Afterthissubgoalhasbeenachieved,theprocessbeginsagainwiththemodifiedtree.Ifthe machine-dependentheuristicsareunabletoreducethetreefurther,anumberofdefaultrewriting rulesmaybeconsideredappropriate.Forexample,iftheleftoperandofa+isascratchregister, the+canbereplacedbya+=operator;thetreemaythenmatchatemplate. Toclosethisintroduction,wewilldiscussthestepsincompilingcodefortheexpression a+=b whereaandbarestaticvariables. Tobeginwith,thewholeexpressiontreeisexaminedwithcookieFOREFF,andnomatchis found.Searchwithothercookiesisequallyfruitless,soanattemptatrewritingismade.Suppose wearedealingwiththeInterdata8/32forthemoment.Itisrecognizedthatthelefthandand righthandsidesofthe+=operatorareaddressable,andinparticularthelefthandsidehasno sideeffects,soitispermissibletorewritethisas -16-a=a+b andthisisdone.Nomatchisfoundonthistreeeither,soamachinedependentrewriteisdone;it isrecognizedthatthelefthandsideoftheassignmentisaddressable,buttherighthandsideis notinaregister,soorderiscalledrecursively,beingaskedtoputtherighthandsideofthe assignmentintoaregister.Thisinvocationofordersearchesthetreeforamatch,andfails.The machinedependentrulefor+noticesthattherighthandoperandisaddressable;itdecidestoput theleftoperandintoascratchregister.Anotherrecursivecalltoorderismade,withthetreeconsistingsolelyoftheleafa,andthecookieaskingthatthevaluebeplacedintoascratchregister. Thisnowmatchesatemplate,andaloadinstructionisemitted.Thenodeconsistingofais rewritteninplacetorepresenttheregisterintowhichaisloaded,andthisthirdcalltoorder returns.Thesecondcalltoordernowfindsthatithasthetree reg+b toconsider.Onceagain,thereisnomatch,butthedefaultrewritingrulerewritesthe+asa+= operator,sincetheleftoperandisascratchregister.Whenthisisdone,thereisamatch:infact, reg+=b simplydescribestheeffectoftheaddinstructiononatypicalmachine.Aftertheaddisemitted, thetreeisrewrittentoconsistmerelyoftheregisternode,sincetheresultoftheaddisnowin theregister.Thisagreeswiththecookiepassedtothesecondinvocationoforder,sothisinvocationterminates,returningtothefirstlevel.Theoriginaltreehasnowbecome a=reg whichmatchesatemplateforthestoreinstruction.Thestoreisoutput,andthetreerewrittento becomejustasingleregisternode.Atthispoint,sincethetoplevelcalltoorderwasinterested onlyinsideeffects,thecalltoorderreturns,andthecodegenerationiscompleted;wehavegeneratedaload,add,andstore,asmighthavebeenexpected. Theeffectofmachinearchitectureonthisisconsiderable.Forexample,ontheHoneywell 6000,themachinedependentheuristicsrecognizethatthereisan‘‘addtostorage’’instruction,so thestrategyisquitedifferent;bisloadedintoaregister,andthenanaddtostorageinstruction generatedtoaddthisregisterintoa.Thetransformations,involvingastheydothesemanticsof C,arelargelymachineindependent.Thedecisionsastowhentousethem,however,arealmost totallymachinedependent. Havinggivenabroadoutlineofthecodegenerationprocess,weshallnextconsidertheheart ofit:thetemplates.Thisleadsnaturallyintodiscussionsoftemplatematchingandregisterallocation,andfinallyadiscussionofthemachinedependentinterfacesandstrategies. TheTemplates Thetemplatesdescribetheeffectofthetargetmachineinstructionsonthemodelofcomputationaroundwhichthecompilerisorganized.Ineffect,eachtemplatehasfivelogicalsections, andrepresentsanassertionoftheform: Ifwehaveasubtreeofagivenshape(1),andwehaveagoal(cookie)orgoalstoachieve (2),andwehavesufficientfreeresources(3),thenwemayemitaninstructionorinstructions(4),andrewritethesubtreeinaparticularmanner(5),andtherewrittentreewill achievethedesiredgoals. Thesefivesectionswillbediscussedinmoredetaillater.First,wegiveanexampleofa template:

-17-ASGPLUS,INAREG, SAREG,TINT, SNAME,TINT, 0,RLEFT, "addAL,AR\n", Thetoplinespecifiestheoperator(+=)andthecookie(computethevalueofthesubtreeintoan AREG).Thesecondandthirdlinesspecifytheleftandrightdescendants,respectively,ofthe+= operator.TheleftdescendantmustbeaREGnode,representinganAregister,andhaveinteger type,whiletherightsidemustbeaNAMEnode,andalsohaveintegertype.Thefourthlinecontainstheresourcerequirements(noscratchregistersortemporariesneeded),andtherewriting rule(replacethesubtreebytheleftdescendant).Finally,thequotedstringonthelastlinerepresentstheoutputtotheassembler:lowercaseletters,tabs,spaces,etc.arecopiedverbatim.tothe output;uppercaseletterstriggervariousmacro-likeexpansions.Thus,ALwouldexpandintothe AddressformoftheLeftoperand—presumablytheregisternumber.Similarly,ARwould expandintothenameoftherightoperand.Theaddinstructionofthelastsectionmightwellbe emittedbythistemplate. Inprinciple,itwouldbepossibletomakeseparatetemplatesforalllegalcombinationsof operators,cookies,types,andshapes.Inpractice,thenumberofcombinationsisverylarge. Thus,aconsiderableamountofmechanismispresenttopermitalargenumberofsubtreestobe matchedbyasingletemplate.Mostoftheshapeandtypespecifiersareindividualbits,andcan belogicallyor’edtogether.Thereareanumberofspecialdescriptorsformatchingclassesofoperators.Thecookiescanalsobecombined.Asanexampleofthekindoftemplatethatreally arisesinpractice,theactualtemplatefortheInterdata8/32thatsubsumestheaboveexampleis: ASGOPSIMP,INAREG|FORCC, SAREG,TINT|TUNSIGNED|TPOINT, SAREG|SNAME|SOREG|SCON,TINT|TUNSIGNED|TPOINT, 0,RLEFT|RESCC, "OIAL,AR\n", Here,OPSIMPrepresentstheoperators+,−,|,&,andˆ .TheOImacrointheoutputstring expandsintotheappropriateIntegerOpcodefortheoperator.Theleftandrightsidescanbe integers,unsigned,orpointertypes.Therightsidecanbe,inadditiontoaname,aregister,a memorylocationwhoseaddressisgivenbyaregisteranddisplacement(OREG),oraconstant. Finally,theseinstructionssettheconditioncodes,andsocanbeusedinconditioncontexts:the cookieandrewritingrulesreflectthis. TheTemplateMatchingAlgorithm. Theheartofthesecondpassisthetemplatematchingalgorithm,intheroutinematch. Matchiscalledwithatreeandacookie;itattemptstomatchthegiventreeagainstsometemplatethatwilltransformitaccordingtooneofthegoalsgiveninthecookie.Ifamatchissuccessful,thetransformationisapplied;expandiscalledtogeneratetheassemblycode,andthen reclaimrewritesthetree,andreclaimstheresources,suchasregisters,thatmighthavebecome freeasaresultofthegeneratedcode. Thispartofthecompilerisamongthemosttimecritical.Thereisaspectrumofimplementationtechniquesavailablefordoingthismatching.Themostnaivealgorithmsimplylooksatthe templatesonebyone.Thiscanbeconsiderablyimproveduponbyrestrictingthesearchforan acceptabletemplate.Itwouldbepossibletodobetterthanthisifthetemplatesweregiventoa separateprogramthatatethemandgeneratedatemplatematchingsubroutine.Thiswouldmake maintenanceofthecompilermuchmorecomplicated,however,sothishasnotbeendone. Thematchingalgorithmisactuallycarriedoutbyrestrictingtherangeinthetablethat mustbesearchedforeachopcode.Thisintroducesanumberofcomplications,however,and needsabitofsympathetichelpbythepersonconstructingthecompilerinordertoobtainbest results.Theexacttuningofthisalgorithmcontinues;itisbesttoconsultthecodeandcomments -18-inmatchforthelatestversion. Inordertomatchatemplatetoatree,itisnecessarytomatchnotonlythecookieandthe opoftheroot,butalsothetypesandshapesoftheleftandrightdescendants(ifany)ofthetree. Aconventionisestablishedherethatiscarriedoutthroughoutthesecondpassofthecompiler.If anoderepresentsaunaryoperator,thesingledescendantisalwaysthe‘‘left’’descendant.Ifa noderepresentsaunaryoperatororaleafnode(nodescendants)the‘‘right’’descendantistaken byconventiontobethenodeitself.Thisenablestemplatestoeasilymatchleavesandconversion operators,forexample,withoutanyadditionalmechanisminthematchingprogram. Thetypematchingisstraightforward;itispossibletospecifyanycombinationofbasic types,generalpointers,andpointerstooneormoreofthebasictypes.Theshapematchingis somewhatmorecomplicated,butstillprettysimple.Templateshaveacollectionofpossible operandshapesonwhichtheopcodemightmatch.Inthesimplestcase,anaddoperationmight beabletoaddtoeitheraregistervariableorascratchregister,andmightbeable(withappropriatehelpfromtheassembler)toaddanintegerconstant(ICON),astaticmemorycell(NAME),or astacklocation(OREG). Itisusuallyattractivetospecifyanumberofsuchshapes,anddistinguishbetweenthem whentheassembleroutputisproduced.Itispossibletodescribetheunionofmanyelementary shapessuchasICON,NAME,OREG,AREGorBREG(bothscratchandregisterforms),etc. Tohandleatleastthesimpleformsofindirection,onecanalsomatchsomemorecomplicated formsoftrees;STARNMandSTARREGcanmatchmorecomplicatedtreesheadedbyanindirectionoperator,andSFLDcanmatchcertaintreesheadedbyaFLDoperator:thesepatternscall machinedependentroutinesthatmatchthepatternsofinterestonagivenmachine.Theshape SWADDmaybeusedtorecognizeNAMEorOREGnodesthatlieonwordboundaries:thismay beofsomeimportanceonword−addressedmachines.Finally,therearesomespecialshapes:these maynotbeusedinconjunctionwiththeothershapes,butmaybedefinedandextendedin machinedependentways.ThespecialshapesSZERO,SONE,andSMONEarepredefinedand matchconstants0,1,and−1,respectively;othersareeasytoaddandmatchbyusingthe machinedependentroutinespecial. Whenatemplatehasbeenfoundthatmatchestherootofthetree,thecookie,andthe shapesandtypesofthedescendants,thereisstillonebartoatotalmatch:thetemplatemaycall forsomeresources(forexample,ascratchregister).Theroutinealloiscalled,anditattemptsto allocatetheresources.Ifitcannot,thematchfails;noresourcesareallocated.Ifsuccessful,the allocatedresourcesaregivennumbers1,2,etc.forlaterreferencewhentheassemblycodeisgenerated.Theroutinesexpandandreclaimarethencalled.Thematchroutinethenreturnsaspecialvalue,MDONE.Ifnomatchwasfound,thevalueMNOPEisreturned;thisisasignaltothe callertotrymorecookievalues,orattemptarewritingrule.Matchisalsousedtoselectrewritingrules,althoughthewayofdoingthisisprettystraightforward.Aspecialcookie,FORREW,is usedtoaskmatchtosearchforarewritingrule.Therewritingrulesarekeyedtovariousopcodes; mostarecarriedoutinorder.Sincethequestionofwhentorewriteisoneofthekeyissuesin codegeneration,itwillbetakenupagainlater. RegisterAllocation. Theregisterallocationroutines,andtheallocationstrategy,playacentralroleinthecorrectnessofthecodegenerationalgorithm.IftherearebugsintheSethi-Ullmancomputationthat causethenumberofneededregisterstobeunderestimated,thecompilermayrunoutofscratch registers;itisessentialthattheallocatorkeeptrackofthoseregistersthatarefreeandbusy,in ordertodetectsuchconditions. Allocationofregisterstakesplaceastheresultofatemplatematch;theroutinealloiscalled withaworddescribingthenumberofAregisters,Bregisters,andtemporarylocationsneeded. Theallocationoftemporarylocationsonthestackisrelativelystraightforward,andwillnotbe furthercovered;thebookkeepingisabittricky,butconceptuallytrivial,andrequestsfortemporaryspaceonthestackwillneverfail.

-19-Registerallocationislessstraightforward.Thetwomajorcomplicationsarepairingand sharing.Inmanymachines,someoperations(suchasmultiplicationanddivision),and/orsome types(suchaslongsordoubleprecision)requireeven/oddpairsofregisters.Operationsofthe firsttypeareexceptionallydifficulttodealwithinthecompiler;infact,theirtheoreticalpropertiesareratherbadaswell.10Thesecondissueisdealtwithrathermoresuccessfully;amachine dependentfunctioncalledszty(t)iscalledthatreturns1or2,dependingonthenumberofAregistersrequiredtoholdanobjectoftypet.Ifsztyreturns2,aneven/oddpairofAregistersis allocatedforeachrequest. Theotherissue,sharing,ismoresubtle,butimportantforgoodcodequality.Whenregistersareallocated,itispossibletoreuseregistersthatholdaddressinformation,andusethemto containthevaluescomputedoraccessed.Forexample,ontheIBM360,ifregister2hasapointer toanintegerinit,wemayloadtheintegerintoregister2itselfbysaying: L2,0(2) Ifregister2hadabytepointer,however,thesequenceforloadingacharacterinvolvesclearingthe targetregisterfirst,andtheninsertingthedesiredcharacter: SR3,3 IC3,0(2) Inthefirstcase,ifregister3wereusedasthetarget,itwouldleadtoalargernumberofregisters usedfortheexpressionthanwererequired;thecompilerwouldgenerateinefficientcode.Onthe otherhand,ifregister2wereusedasthetargetinthesecondcase,thecodewouldsimplybe wrong.Inthefirstcase,register2canbesharedwhileinthesecond,itcannot. Inthespecificationoftheregisterneedsinthetemplates,itispossibletoindicatewhether requiredscratchregistersmaybesharedwithpossibleregistersontheleftortherightofthe inputtree.Inorderthataregisterbeshared,itmustbescratch,anditmustbeusedonlyonce, ontheappropriatesideofthetreebeingcompiled. Thealloroutinethushasabitmoretodothanmeetstheeye;itcallsfreeregtoobtaina freeregisterforeachAandBregisterrequest.Freeregmakesmultiplecallsontheroutineusable todecideifagivenregistercanbeusedtosatisfyagivenneed.Usablecallsshareitiftheregister isbusy,butmightbeshared.Finally,shareitcallsusharetodecideifthedesiredregisterisactuallyintheappropriatesubtree,andcanbeshared. Justtoaddadditionalcomplexity,onsomemachines(suchastheIBM370)itispossibleto have‘‘doubleindexing’’formsofaddressing;thesearerepresentedbyOREGS’swiththebaseand indexregistersencodedintotheregisterfield.Whiletheregisterallocationanddeallocationper seisnotmademoredifficultbythisphenomenon,thecodeitselfissomewhatmorecomplex. Havingallocatedtheregistersandexpandedtheassemblylanguage,itistimetoreclaimthe resources;theroutinereclaimdoesthis.Manyoperationsproducemorethanoneresult.For example,manyarithmeticoperationsmayproduceavalueinaregister,andalsosetthecondition codes.Assignmentoperationsmayleaveresultsbothinaregisterandinmemory.Reclaimis passedthreeparameters;thetreeandcookiethatwerematched,andtherewritingfieldofthe template.Therewritingfieldallowsthespecificationofpossibleresults;thetreeisrewrittento reflecttheresultsoftheoperation.Ifthetreewascomputedforsideeffectsonly(FOREFF),the treeisfreed,andallresourcesinitreclaimed.Ifthetreewascomputedforconditioncodes,the resourcesarealsofreed,andthetreereplacedbyaspecialnodetype,FORCC.Otherwise,the valuemaybefoundintheleftargumentoftheroot,therightargumentoftheroot,oroneofthe temporaryresourcesallocated.Inthesecases,firsttheresourcesofthetree,andthenewlyallocatedresources,arefreed;thentheresourcesneededbytheresultaremadebusyagain.Thefinal resultmustalwaysmatchtheshapeoftheinputcookie;otherwise,thecompilererror‘‘cannot reclaim’’isgenerated.Therearesomemachinedependentwaysofpreferringresultsinregistersor memorywhentherearemultipleresultsmatchingmultiplegoalsinthecookie.

-20-TheMachineDependentInterface Thefilesorder.c,local2.c,andtable.c,aswellastheheaderfilemac2defs,representthe machinedependentportionofthesecondpass.Themachinedependentportioncanberoughly dividedintotwo:theeasyportionandthehardportion.Theeasyportiontellsthecompilerthe namesoftheregisters,andarrangesthatthecompilergeneratetheproperassemblerformats, opcodenames,locationcounters,etc.ThehardportioninvolvestheSethi−Ullmancomputation, therewritingrules,and,tosomeextent,thetemplates.Itishardbecausetherearenorealalgorithmsthatapply;mostofthisportionisbasedonheuristics.Thissectiondiscussestheeasyportion;thenextseveralsectionswilldiscussthehardportion. Ifthecompilerisadaptedfromacompilerforamachineofsimilararchitecture,theeasy partisindeedeasy.Inmac2defs,theregisternumbersaredefined,aswellasvariousparameters forthestackframe,andvariousmacrosthatdescribethemachinearchitecture.Ifdoubleindexingistobepermitted,forexample,thesymbolR2REGSisdefined.Also,anumberofmacros thatareinvolvedinfunctioncallprocessing,especiallyforunusualfunctioncallmechanisms,are definedhere. Inlocal2.c,alargenumberofsimplefunctionsaredefined.Thesedothingssuchaswrite outopcodes,registernames,andaddressformsfortheassembler.Partofthefunctioncallcodeis definedhere;thatisnontrivialtodesign,buttypicallyratherstraightforwardtoimplement. Amongtheeasyroutinesinorder.careroutinesforgeneratingacreatedlabel,definingalabel, andgeneratingtheargumentsofafunctioncall. Theseroutinestendtohavealocaleffect,anddependonafairlystraightforwardwayonthe targetassemblerandthedesigndecisionsalreadymadeaboutthecompiler.Thustheywillnotbe furthertreatedhere. TheRewritingRules Whenatreefailstomatchanytemplate,itbecomesacandidateforrewriting.Beforethe treeisrewritten,themachinedependentroutinenextcookiscalledwiththetreeandthecookie;it suggestsanothercookiethatmightbeabettercandidateforthematchingofthetree.Ifallelse fails,thetemplatesaresearchedwiththecookieFORREW,tolookforarewritingrule.The rewritingrulesareoftwokinds;formostofthecommonoperators,therearemachinedependent rewritingrulesthatmaybeapplied;thesearehandledbymachinedependentfunctionsthatare calledandgiventhetreetobecomputed.Theseroutinesmayrecursivelycallorderorcodgento causecertainsubgoalstobeachieved;iftheyactuallycallforsomealterationofthetree,they return1,andthecodegenerationalgorithmrecanonicalizesandtriesagain.Iftheseroutines choosenottodealwiththetree,thedefaultrewritingrulesareapplied. Theassignmentops,whenrewritten,calltheroutinesetasg.Thisisassumedtorewritethe treeatleasttothepointwheretherearenosideeffectsinthelefthandside.Ifthereisstillno templatematch,adefaultrewritingisdonethatcausesanexpressionsuchas a+=b toberewrittenas a=a+b Thisisausefuldefaultforcertainmixturesofstrangetypes(forexample,whenaisabitfield andbancharacter)thatotherwisemightneedseparatetableentries. Simpleassignment,structureassignment,andallformsofcallsarehandledcompletelyby themachinedependentroutines.Forhistoricalreasons,theroutinesgeneratingthecallsreturn1 onfailure,0onsuccess,unliketheotherroutines. Themachinedependentroutinesetbinhandlesbinaryoperators;ittoomustdomostofthe job.Inparticular,whenitreturns0,itmustdosowiththelefthandsideinatemporaryregister.Thedefaultrewritingruleinthiscaseistoconvertthebinaryoperatorintotheassociated assignmentoperator;sincethelefthandsideisassumedtobeatemporaryregister,thispreserves -21-thesemanticsandoftenallowsaconsiderablesavinginthetemplatetable. Theincrementanddecrementoperatorsmaybedealtwithwiththemachinedependentroutinesetincr.Ifthisroutinechoosesnottodealwiththetree,therewritingrulereplaces x++ by ((x+=1)−1) whichpreservesthesemantics.Onceagain,thisisnottooattractiveforthemostcommoncases, butcangenerateclosetooptimalcodewhenthetypeofxisunusual. Finally,theindirection(UNARYMUL)operatorisalsohandledinaspecialway.The machinedependentroutineoffstarisextremelyimportantfortheefficientgenerationofcode.OffstariscalledwithatreethatisthedirectdescendantofaUNARYMULnode;itsjobistotransformthistreesothatthecombinationofUNARYMULwiththetransformedtreebecomes addressable.Onmostmachines,offstarcansimplycomputethetreeintoanAorBregister, dependingonthearchitecture,andthencanonwillmaketheresultingtreeintoanOREG.On manymachines,offstarcanprofitablychoosetodolessworkthancomputingitsentireargument intoaregister.Forexample,ifthetargetmachinesupportsOREGSwithaconstantoffsetfroma register,andoffstariscalledwithatreeoftheform expr+const whereconstisaconstant,thenoffstarneedonlycomputeexprintotheappropriateformofregister.Onmachinesthatsupportdoubleindexing,offstarmayhaveevenmorechoiceastohowto proceed.Thepropertuningofoffstar,whichisnottypicallytoodifficult,shouldbeoneofthe firsttriesatoptimizationattemptedbythecompilerwriter. TheSethi-UllmanComputation TheheartoftheheuristicsisthecomputationoftheSethi-Ullmannumbers.Thiscomputa-tioniscloselylinkedwiththerewritingrulesandthetemplates.Asmentionedbefore,theSethi-Ullmannumbersareexpectedtoestimatethenumberofscratchregistersneededtocomputethe subtreeswithoutusinganystores.However,theoriginaltheorydoesnotapplytorealmachines. Foronething,thetheoryassumesthatallregistersareinterchangeable.Realmachineshavegeneralpurpose,floatingpoint,andindexregisters,registerpairs,etc.Thetheoryalsodoesnot accountforsideeffects;thisrulesoutvariousformsofpathologythatarisefromassignmentand assignmentops.Conditioncodesarealsoundreamedof.Finally,theinfluenceoftypes,conversions,andthevariousaddressabilityrestrictionsandextensionsofrealmachinesarealsoignored. Nevertheless,fora‘‘useless’’theory,thebasicinsightofSethiandUllmanisamazinglyusefulinarealcompiler.Thenotionthatoneshouldattempttoestimatetheresourceneedsoftrees beforestartingthecodegenerationprovidesanaturalmeansofsplittingthecodegenerationproblem,andprovidesabitofredundancyandselfcheckinginthecompiler.Moreover,ifwritingthe Sethi-Ullmanroutinesishard,describing,writing,anddebuggingthealternative(routinesthat attempttofreeupregistersbystoresintotemporaries‘‘onthefly’’)isevenworse.Nevertheless,it shouldbeclearlyunderstoodthattheseroutinesexistinarealmwherethereisno‘‘right’’wayto writethem;itisanart,therealmofheuristics,and,consequently,amajorsourceofbugsinthe compiler.Often,theearly,crudeversionsoftheseroutinesgivelittletrouble;onlyafterthecompilerisactuallyworkingandthecodequalityisbeingimproveddoseriousproblemhavetobe faced.Havingasimple,regularmachinearchitectureisworthquitealotatthistime. Themajorproblemsarisefromasymmetriesintheregisters:registerpairs,havingdifferent kindsofregisters,andtherelatedproblemofneedingmorethanoneregister(frequentlyapair)to storecertaindatatypes(suchaslongsordoubles).Thereappearstobenogeneralwayoftreatingthisproblem;solutionshavetobefudgedforeachmachinewheretheproblemarises.Onthe Honeywell66,forexample,thereareonlytwogeneralpurposeregisters,soaneedforapairisthe sameastheneedfortworegisters.OntheIBM370,theregisterpair(0,1)isusedtodo -22-multiplicationsanddivisions;registers0and1arenotgenerallyconsideredpartofthescratch registers,andsodonotrequireallocationexplicitly.OntheInterdata8/32,aftermuchconsideration,thedecisionwasmadenottotrytodealwiththeregisterpairissue;operationssuchasmultiplicationanddivisionthatrequiredpairsweresimplyassumedtotakeallofthescratchregisters.Severalweeksofefforthadfailedtoproduceanalgorithmthatseemedtohavemuchchance ofrunningsuccessfullywithoutinordinatedebuggingeffort.Thedifficultyofthisissueshouldnot beminimized;itrepresentsoneofthemainintellectualeffortsinportingthecompiler.Nevertheless,thisproblemhasbeenfudgedwithadegreeofsuccessonnearlyadozenmachines,sothe compilerwritershouldnotabandonhope. TheSethi-Ullmancomputationsinteractwiththerestofthecompilerinanumberofrather subtleways.Asalreadydiscussed,thestoreroutineusestheSethi-Ullmannumberstodecide whichsubtreesaretoodifficulttocomputeinregisters,andmustbestored.Therearealsosubtle interactionsbetweentherewritingroutinesandtheSethi-Ullmannumbers.Supposewehavea treesuchas A−B whereAandBareexpressions;supposefurtherthatBtakestworegisters,andAone.ItispossibletocomputethefullexpressionintworegistersbyfirstcomputingB,andthen,usingthe scratchregisterusedbyB,butnotcontainingtheanswer,computeA.Thesubtractioncanthen bedone,computingtheexpression.(Notethatthisassumesanumberofthings,nottheleastof whichareregister-to-registersubtractionoperatorsandsymmetricregisters.)Ifthemachine dependentroutinesetbin,however,isnotpreparedtorecognizethiscaseandcomputethemore difficultsideoftheexpressionfirst,theSethi-Ullmannumbermustbesettothree.Thus,the Sethi-Ullmannumberforatreeshouldrepresentthecodethatthemachinedependentroutines areactuallywillingtogenerate. Theinteractioncangotheotherway.Ifwetakeanexpressionsuchas *(p+i) wherepisapointerandianinteger,thiscanprobablybedoneinoneregisteronmostmachines. Thus,itsSethi-Ullmannumberwouldprobablybesettoone.Ifdoubleindexingispossibleinthe machine,apossiblewayofcomputingtheexpressionistoloadbothpandiintoregisters,and thenusedoubleindexing.Thiswouldusetwoscratchregisters;insuchacase,itispossiblethat thescratchregistersmightbeunobtainable,ormightmakesomeotherpartofthecomputation runoutofregisters.Theusualsolutionistocauseoffstartoignoreopportunitiesfordouble indexingthatwouldtieupmorescratchregistersthantheSethi-Ullmannumberhadreserved. Insummary,theSethi-Ullmancomputationrepresentsmuchofthecraftsmanshipand artistryinanyapplicationoftheportablecompiler.Itisalsoafrequentsourceofbugs.Algorithmsareavailablethatwillproducenearlyoptimalcodeforspecializedmachines,butunfortunatelymostexistingmachinesarefarremovedfromtheseideals.Thebestwayofproceedingin practiceistostartwithacompilerforasimilarmachinetothetarget,andproceedverycarefully. RegisterAllocation AftertheSethi-Ullmannumbersarecomputed,ordercallsaroutine,rallo,thatdoesregister allocation,ifappropriate.Thisroutinedoesrelativelylittle,ingeneral;thisisespeciallytrueif thetargetmachineisfairlyregular.Thereareafewcaseswhereitisassumedthattheresultofa computationtakesplaceinaparticularregister;switchandfunctionreturnarethetwomajor places.Theexpressiontreehasafield,rall,thatmaybefilledwitharegisternumber;thisis takentobeapreferredregister,andthefirsttemporaryregisterallocatedbyatemplatematch willbethispreferredone,ifitisfree.Ifnot,noparticularactionistaken;thisisjustaheuristic. Ifnoregisterpreferenceispresent,thefieldcontainsNOPREF.Insomecases,theresultmustbe placedinagivenregister,nomatterwhat.Theregisternumberisplacedinrall,andthemask MUSTDOislogicallyor’edinwithit.Inthiscase,ifthesubtreeisrequestedinaregister,and comesbackinaregisterotherthanthedemandedone,itismovedbycallingtheroutinermove.

-23-Ifthetargetregisterforthismoveisbusy,itisacompilererror. Notethatthismechanismistheonlyonethatwillevercausearegister-to-registermove betweenscratchregisters(unlesssuchamoveisburiedinthedepthsofsometemplate).This simplifiesdebugging.Insomecases,thereisaratherstrangeinteractionbetweentheregisterallocationandtheSethi-Ullmannumber;ifthereisanoperatororsituationrequiringaparticularreg-ister,theallocatorandtheSethi-Ullmancomputationmustconspiretoensurethatthetargetreg-isterisnotbeingusedbysomeintermediateresultofsomefar-removedcomputation.Thisis mosteasilydonebymakingthespecialoperationtakeallofthefreeregisters,preventingany otherpartially-computedresultsfromclutteringuptheworks. CompilerBugs Theportablecompilerhasanexcellentrecordofgeneratingcorrectcode.Therequirement forreasonablecooperationbetweentheregisterallocation,Sethi-Ullmancomputation,rewriting rules,andtemplatesbuildsquiteabitofredundancyintothecompilingprocess.Theeffectof thisisthat,inasurprisinglyshorttime,thecompilerwillstartgeneratingcorrectcodeforthose programsthatitcancompile.Thehardpartofthejobthenbecomesfindingandeliminating thosesituationswherethecompilerrefusestocompileaprogrambecauseitknowsitcannotdoit right.Forexample,atemplatemaysimplybemissing;thismayeithergiveacompilererrorof theform‘‘nomatchforop...’’,orcausethecompilertogointoaninfiniteloopapplyingvarious rewritingrules.Thecompilerhasavariable,nrecur,thatissetto0atthebeginningofan expressions,andincrementedatkeyspotsinthecompilationprocess;ifthisparametergetstoo large,thecompilerdecidesthatitisinaloop,andaborts.Loopsarealsocharacteristicof botchesinthemachine-dependentrewritingrules.BadSethi-Ullmancomputationsusuallycause thescratchregisterstorunout;thisoftenmeansthattheSethi-Ullmannumberwasunderesti-mated,sostoredidnotstoresomethingitshouldhave;alternatively,itcanmeanthattherewrit-ingruleswerenotsmartenoughtofindthesequencethatsucompassumedwouldbeused. Thebestapproachwhenacompilererrorisdetectedinvolvesseveralstages.First,tryto getasmallexampleprogramthatstepsonthebug.Second,turnonvariousdebuggingflagsin thecodegenerator,andfollowthetreethroughtheprocessofbeingmatchedandrewritten. Someflagsofinterestare−e,whichprintstheexpressiontree,−r,whichgivesinformationabout theallocationofregisters,−a,whichgivesinformationabouttheperformanceofrallo,and−o, whichgivesinformationaboutthebehavioroforder.Thistechniqueshouldallowmostbugstobe foundrelativelyquickly. Unfortunately,findingthebugisusuallynotenough;itmustalsobefixed!Thedifficulty arisesbecauseafixtotheparticularbugofinteresttendstobreakothercodethatalreadyworks. Regressiontests,teststhatcomparetheperformanceofanewcompileragainsttheperformanceof anolderone,areveryvaluableinpreventingmajorcatastrophes. SummaryandConclusion TheportablecompilerhasbeenausefultoolforprovidingCcapabilityonalargenumberof diversemachines,andfortestinganumberoftheoreticalconstructsinapracticalsetting.Ithas manyblemishes,bothinstyleandfunctionality.Ithasbeenappliedtomanymoremachinesthan firstanticipated,ofamuchwiderrangethanoriginallydreamedof.Itsusehasalsospreadmuch fasterthanexpected,leavingpartsofthecompilerstillsomewhatrawinshape. Onthetheoreticalside,thereissomehopethattheskeletonofthesucomproutinecouldbe generatedformanymachinesdirectlyfromthetemplates;thiswouldgiveaconsiderableboostto theportabilityandcorrectnessofthecompiler,butmightaffecttunabilityandcodequality. Thereisalsoroomformoreoptimization,bothwithinoptimandintheformofaportable‘‘peephole’’optimizer. Onthepractical,developmentside,thecompilercouldprobablybespedupandmade smallerwithoutdoingtoomuchviolencetoitsbasicstructure.Partsofthecompilerdeserveto berewritten;theinitializationcode,registerallocation,andparserareprimecandidates.Itmight -24-bethatdoingsomeoralloftheparsingwitharecursivedescentparsermightsaveenoughspace andtimetobeworthwhile;itwouldcertainlyeasetheproblemofmovingthecompilertoanenvironmentwhereYaccisnotalreadypresent. Finally,Iwouldliketothankthemanypeoplewhohavesympathetically,andevenenthusiastically,helpedmegrapplewithwhathasbeenafrustratingprogramtowrite,test,andinstall. D.M.RitchieandE.N.Pinsonprovidedneededearlyencouragementandphilosophicalguidance; M.E.Lesk,R.Muha,T.G.Peterson,G.Riddle,L.Rosler,R.W.Mitze,B.R.Rowland,S.I. Feldman,andT.B.Londonhaveallcontributedideas,gripes,andall,atonetimeoranother, climbed‘‘intothepits’’withmetohelpdebug.Withouttheirhelpthiseffortwouldhavenot beenpossible;withit,itwasoftenkindoffun.

-25-References 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

-26-