ATourthroughtheUNIX†CCompiler D.M.Ritchie Languages Computing TheIntermediateLanguage Communicationbetweenthetwophasesofthecompilerproperiscarriedoutbymeansofa pairofintermediatefiles.Thesefilesaretreatedashavingidenticalstructure,althoughthesecondfilecontainsonlythecodegeneratedforstrings.Itisconvenienttowritestringsoutseparatelytoreducetheneedformultiplelocationcountersinalaterassemblyphase. Theintermediatelanguageisnotmachine-independent;itsstructureinanumberofways reflectsthefactthatCwasoriginallyaone-passcompilerchoppedintwotoreducethemaximum memoryrequirement.Infact,onlythelatestversionofthecompilerhasacompleteintermediate languageatall.Untilrecently,thefirstphaseofthecompilergeneratedassemblycodeforthose constructionsitcoulddealwith,andpassedexpressionparsetrees,inabsolutebinaryform,tothe secondphaseforcodegeneration.Now,atleast,allinter-phaseinformationispassedinadescrib-ableform,andtherearenoabsolutepointersinvolved,sothecouplingbetweenthephasesisnot sostrong. Theareasinwhichthemachine(andsystem)dependenciesaremostnoticeableare 1.Storageallocationforautomaticvariablesandargumentshasalreadybeenperformed,and nodesforsuchvariablesrefertothembyoffsetfromadisplaypointer.Typeconversion(for example,fromintegertopointer)hasalreadyoccurredusingtheassumptionofbyte addressingand2-bytewords. 2.DatarepresentationssuitabletothePDP-11areassumed;inparticular,floatingpointcon-stantsarepassedasfourwordsinthemachinerepresentation. Asithappens,eachintermediatefileisrepresentedasasequenceofbinarynumberswithout anyexplicitdemarcations.Itconsistsofasequenceofconceptuallines,eachheadedbyanoperator,andpossiblycontainingvariousoperands.Theoperatorsaresmallnumbers;toassistinrecognizingfailureinsynchronization,thehigh-orderbyteofeachoperatorwordisalwaystheoctal number376.Operandsareeither16-bitbinarynumbersorstringsofcharactersrepresenting names.Eachnameisterminatedbyanullcharacter.Thereisnoalignmentrequirementfor numericaloperandsandsothereisnopaddingafteranamestring. Thebinaryrepresentationwaschosentoavoidthenecessityofconvertingtoandfromcharacterformandtominimizethesizeofthefiles.Itwouldbeveryeasytomakeeachoperatoroperand‘line’inthefilebeagenuine,printableline,withthenumbersinoctalordecimal;thisin factwastherepresentationoriginallyused. Theoperatorsfallnaturallyintotwoclasses:thosewhichrepresentpartofanexpression, andallothers.Expressionsaretransmittedinareverse-Polishnotation;astheyarebeingread,a treeisbuiltwhichisisomorphictothetreeconstructedinthefirstphase.Expressionsarepassed asawhole,withnonon-expressionoperatorsintervening.Thereadermaintainsastack;eachleaf oftheexpressiontree(name,constant)ispushedonthestack;eachunaryoperatorreplacesthe topofthestackbyanodewhoseoperandistheoldtop-of-stack;eachbinaryoperatorreplaces thetoppaironthestackwithasingleentry.Whentheexpressioniscompletethereisexactly oneitemonthestack.Followingeachexpressionisaspecialoperatorwhichpassestheunique †UNIXisaTrademarkofBellLaboratories.

-2-previousexpressiontothe‘optimizer’describedbelowandthentothecodegenerator. Hereisthelistofoperatorsnotthemselvespartofexpressions. EOF markstheendofaninputfile. BDATAflagdata... specifiesasequenceofbytestobeassembledasstaticdata.Itisfollowedbypairsofwords; thefirstmemberofthepairisnon-zerotoindicatethatthedatacontinue;azeroflagisnot followedbydataandterminatestheoperator.Thedatabytesoccupythelow-orderpartof aword. WDATAflagdata... specifiesasequenceofwordstobeassembledasstaticdata;itisidenticaltotheBDATA operatorexceptthatentirewords,notjustbytes,arepassed. PROG meansthatsubsequentinformationistobecompiledasprogramtext. DATA meansthatsubsequentinformationistobecompiledasstaticdata. BSS meansthatsubsequentinformationistobecompiledasunitializedstaticdata. SYMDEFname meansthatthesymbolnameisanexternalnamedefinedinthecurrentprogram.Itisproducedforeachexternaldataorfunctiondefinition. CSPACEnamesize indicatesthatthenamereferstoadataareawhosesizeisthespecifiednumberofbytes.It isproducedforexternaldatadefinitionswithoutexplicitinitialization. SSPACEsize indicatesthatsizebytesshouldbesetasidefordatastorage.Itisusedtopadoutshortinitializationsofexternaldataandtoreservespaceforstatic(internal)data.Itwillbeprecededbyanappropriatelabel. EVEN isproducedaftereachexternaldatadefinitionwhosesizeisnotanintegralnumberofwords. Itisnotproducedafterstringsexceptwhentheyinitializeacharacterarray. NLABELname isproducedjustbeforeaBDATAorWDATAinitializingexternaldata,andservesasalabel forthedata. RLABELname isproducedjustbeforeeachfunctiondefinition,andlabelsitsentrypoint.

-3-SNAMEnamenumber isproducedatthestartofeachfunctionforeachstaticvariableorlabeldeclaredtherein. Subsequentusesofthevariablewillbeintermsofthegivennumber.Thecodegenerator usesthisonlytoproduceadebuggingsymboltable. ANAMEnamenumber Likewise,eachautomaticvariable’snameandstackoffsetisspecifiedbythisoperator. Argumentscountasautomatics. RNAMEnamenumber Eachregistervariableissimilarlynamed,withitsregisternumber. SAVEnumber producesaregister-savesequenceatthestartofeachfunction,justafteritslabel(RLA-BEL). SETREGnumber isusedtoindicatethenumberofregistersusedforregistervariables.Itactuallygivesthe registernumberofthelowestfreeregister;itisredundantbecausetheRNAMEoperators couldbecountedinstead. PROFIL isproducedbeforethesavesequenceforfunctionswhentheprofileoptionisturnedon.It producescodetocountthenumberoftimesthefunctioniscalled. SWITdeflablinelabelvalue... isproducedforswitches.Whencontrolflowsintoit,thevaluebeingswitchedonisinthe registerforcedbyRFORCE(below).Theswitchstatementoccurredontheindicatedlineof thesource,andthelabelnumberofthedefaultlocationisdeflab.Thentheoperatorisfollowedbyasequenceoflabel-numberandvaluepairs;thelististerminatedbya0label. LABELnumber generatesaninternallabel.Itisreferredtoelsewhereusingthegivennumber. BRANCHnumber indicatesanunconditionaltransfertotheinternallabelnumbergiven. RETRN producesthereturnsequenceforafunction.Itoccursonlyonce,attheendofeachfunction. EXPRline causestheexpressionjustprecedingtobecompiled.Theargumentisthelinenumberinthe sourcewheretheexpressionoccurred. NAMEclasstypename NAMEclasstypenumber indicatesanameoccurringinanexpression.Thefirstformisusedwhenthenameisexternal;thesecondwhenthenameisautomatic,static,oraregister.Thenthenumberindicatesthestackoffset,thelabelnumber,ortheregisternumberasappropriate.Classand -4-typeencodingisdescribedelsewhere. CONtypevalue transmitsanintegerconstant.Thisandthenexttwooperatorsoccuraspartofexpressions. FCONtype4-word-value transmitsafloatingconstantasfourwordsinPDP-11notation. SFCONtypevalue transmitsafloating-pointconstantwhosevalueiscorrectlyrepresentedbyitshigh-order wordinPDP-11notation. NULL indicatesanullargumentlistofafunctioncallinanexpression;callisabinaryoperator whosesecondoperandistheargumentlist. CBRANCHlabelcond producesaconditionalbranch.Itisanexpressionoperator,andwillbefollowedbyan EXPR.Thebranchtothelabelnumbertakesplaceiftheexpression’struthvalueisthe sameasthatofcond.Thatis,ifcond=1andtheexpressionevaluatestotrue,thebranchis taken. binary-operatortype Therearebinaryoperatorscorrespondingtoeachsuchsource-languageoperator;thetypeof theresultofeachispassedaswell.Someperhaps-unexpectedonesare:COMMA,whichis aright-associativeoperatordesignedtosimplifyright-to-leftevaluationoffunctionargu-ments;prefixandpostfix++and−−,whosesecondoperandistheincrementamount,asa CON;QUESTandCOLON,toexpresstheconditionalexpressionas‘a?(b:c)’;anda sequenceofspecialoperatorsforexpressingrelationsbetweenpointers,incasepointercomparisonisdifferentfromintegercomparison(e.g.unsigned). unary-operatortype Therearealsonumerousunaryoperators.TheseincludeITOF,FTOI,FTOL,LTOF, ITOL,LTOIwhichconvertamongfloating,long,andinteger;JUMPwhichbranchesindirectlythroughalabelexpression;INIT,whichcompilesthevalueofaconstantexpression usedasaninitializer;RFORCE,whichisusedbeforeareturnsequenceoraswitchtoplace avalueinanagreed-uponregister. ExpressionOptimization Eachexpressiontree,asitisreadin,issubjectedtoafairlycomprehensiveanalysis.Thisis performedbytheoptimroutineandanumberofsubroutines;themajorthingsdoneare 1.Modificationsandsimplificationsofthetreesoitsvaluemaybecomputedmoreefficiently andconvenientlybythecodegenerator. 2.Markingeachinteriornodewithanestimateofthenumberofregistersrequiredtoevaluate it.Thisregistercountisneededtoguidethecodegenerationalgorithm. Onethingthatisdefinitelynotdoneisdiscoveryorexploitationofcommonsubexpressions, noristhisdoneanywhereinthecompiler. Thebasicorganizationissimple:adepth-firstscanofthetree.Optimdoesnothingforleaf nodes(exceptforautomatics;seebelow),andcallsunoptimtohandleunaryoperators.For binaryoperators,itcallsitselftoprocesstheoperands,thentreatseachoperatorseparately.One importantcaseiscommutativeandassociativeoperators,whicharehandledbyacommute.

-5-Hereisabriefcatalogofthetransformationscarriedoutbybyoptimitself.Itisnot intendedtobecomplete.Someofthetransformationsaremachine-dependent,althoughtheymay wellbeusefulonmachinesotherthanthePDP-11. 1.Asindicatedinthediscussionofunoptimbelow,theoptimizercancreateanodetypecorrespondingtothelocationaddressedbyaregisterplusaconstantoffset.Sincethisispreciselytheimplementationofautomaticvariablesandarguments,wheretheregisterisfixed byconvention,suchvariablesarechangedtothenewformtosimplifylaterprocessing. 2.Associativeandcommutativeoperatorsareprocessedbythespecialroutineacommute. 3.Afterprocessingbyacommute,thebitwise&operatoristurnedintoanewandnoperator; ‘a&b’becomes‘aandn˜ b’.ThisisdonebecausethePDP-11providesnoandoperator, butonlyandn.Asimilartransformationtakesplacefor‘=&’. 4.Relationalsareturnedaroundsothemorecomplicatedexpressionisontheleft.(Sothat‘2 >f(x)’becomes‘f(x)<2’).Thisimprovescodegenerationsincethealgorithmprefersto havetherightoperandrequirefewerregistersthantheleft. 5.Anexpressionminusaconstantisturnedintotheexpressionplusthenegativeconstant,and theacommuteroutineiscalledtotakeadvantageofthepropertiesofaddition. 6.Operatorswithconstantoperandsareevaluated. 7.Rightshifts(unlessby1)areturnedintoleftshiftswithanegatedrightoperand,sincethe PDP-11lacksageneralright-shiftoperator. 8.Anumberofspecialcasesaresimplified,suchasdivisionormultiplicationby1,andshifts by0. Theunoptimroutineperformsthesamesortofprocessingforunaryoperators. 1.‘*&x’and‘&*x’aresimplifiedto‘x’. 2.Ifrisaregisterandcisaconstantortheaddressofastaticorexternalvariable,the expressions‘*(r+c)’and‘*r’areturnedintoaspecialkindofnamenodewhichexpressesthe nameitselfandtheoffset.Thissimplifiessubsequentprocessingbecausesuchconstructions canappearasthetheaddressofaPDP-11instruction. 3.Whentheunary‘&’operatorisappliedtoanamenodeofthespecialkindjustdiscussed,it isreworkedtomaketheadditionexplicitagain;thisisdonebecausethePDP-11hasno ‘loadaddress’instruction. 4.Constructionslike‘*r++’and‘*−−r’whererisaregisterarediscoveredandmarkedas beingimplementableusingthePDP-11auto-incrementand-decrementmodes. 5.If‘!’isappliedtoarelational,the‘!’isdiscardedandthesenseoftherelationalisreversed. 6.Specialcasesinvolvingreflexiveuseofnegationandcomplementationarediscovered. 7.Operationsapplyingtoconstantsareevaluated. Theacommuteroutine,calledforassociativeandcommutativeoperators,discoversclusters ofthesameoperatoratthetoplevelsofthecurrenttree,andarrangestheminalist:for ‘a+((b+c)+(d+f))’thelistwouldbe‘a,b,c,d,e,f’.Aftereachsubtreeisoptimized,thelistissorted indecreasingdifficultyofcomputation;asmentionedabove,thecodegenerationalgorithmworks bestwhenleftoperandsarethedifficultones.The‘degreeofdifficulty’computedisactuallyfiner thanthemerenumberofregistersrequired;aconstantisconsideredsimplerthantheaddressofa staticorexternal,whichissimplerthanreferencetoavariable.Thismakesiteasytofoldallthe constantstogether,andalsotomergetogetherthesumofaconstantandtheaddressofastatic orexternal(sinceinsuchnodesthereisspaceforan‘offset’value).Therearealsospecialcases, likemultiplicationby1andadditionof0. Aspecialroutineisinvokedtohandlesumsofproducts.Distribisbasedonthefactthatitis bettertocompute‘c1*c2*x+c1*y’as‘c1*(c2*x+y)’andmakesthedivisibilitytestsrequiredto assurethecorrectnessofthetransformation.Thistransformationisrarelypossiblewithcode -6-directlywrittenbytheuser,butitinvariablyoccursasaresultoftheimplementationofmulti-dimensionalarrays. Finally,acommutereconstructsatreefromthelistofexpressionswhichresult. CodeGeneration Thegrandplanforcode-generationisindependentofanyparticularmachine;itdepends largelyonasetoftables.Butthisfactdoesnotnecessarilymakeitveryeasytomodifythecompilertoproducecodeforothermachines,bothbecausethereisagooddealofmachine-dependent structureinthetables,andbecauseinanyeventsuchtablesarenon-trivialtoprepare. Theargumentstothebasiccodegenerationroutinercexprareapointertoatreerepresentinganexpression,thenameofacode-generationtable,andthenumberofaregisterinwhichthe valueoftheexpressionshouldbeplaced.Rcexprreturnsthenumberoftheregisterinwhichthe valueactuallyendedup;itscallermayneedtoproduceamovinstructionifthevaluereallyneeds tobeinthegivenregister.Therearefourcodegenerationtables. Regtabisthebasicone,whichactuallydoesthejobdescribedabove:namely,compilecode whichplacesthevaluerepresentedbytheexpressiontreeinaregister. Cctabisusedwhenthevalueoftheexpressionisnotactuallyneeded,butinsteadthevalue oftheconditioncodesresultingfromevaluationoftheexpression.Thistableisused,forexample, toevaluatetheexpressionafterif.Itisclearlysillytocalculatethevalue(0or1)oftheexpression‘a==b’inthecontext‘if(a==b)...’ Thesptabtableisusedwhenthevalueofanexpressionistobepushedonthestack,for examplewhenitisanactualargument.Forexampleinthefunctioncall‘f(a)’itisabadideato loadaintoaregisterwhichisthenpushedonthestack,whenthereisasingleinstructionwhich doesthejob. Theefftabtableisusedwhenanexpressionistobeevaluatedforitssideeffects,notits value.Thisoccursmostlyforexpressionswhicharestatements,whichhavenovalue.Thusthe codeforthestatement‘a=b’needproduceonlytheapprooriatemovinstruction,andneednot leavethevalueofbinaregister,whileintheexpression‘a+(b=c)’thevalueof‘b=c’will appearinaregister. Allofthetablesbesidesregtabarerathersmall,andhandleonlyarelativelyfewspecial cases.Ifoneofthesesubsidiarytablesdoesnotcontainanentryapplicabletothegivenexpressiontree,rcexprusesregtabtoputthevalueoftheexpressionintoaregisterandthenfixesthings up;nothingneedbedonewhenthetablewasefftab,butatstinstructionisproducedwhenthe tablecalledforwascctab,andamovinstruction,pushingtheregisteronthestack,whenthetable wassptab. Thercexprroutineitselfpicksoffsomespecialcases,thencallscexprtodotherealwork. Cexprtriestofindanentryapplicabletothegiventreeinthegiventable,andreturns−1ifno suchentryisfound,lettingrcexprtryagainwithadifferenttable.Asuccessfulmatchyieldsa stringcontainingbothliteralcharacterswhicharewrittenoutandpseudo-operations,ormacros, whichareexpanded.Beforestudyingthecontentsofthesestringswewillconsiderhowtable entriesarematchedagainsttrees. Recallthatmostnon-leafnodesinanexpressiontreecontainthenameoftheoperator,the typeofthevaluerepresented,andpointerstothesubtrees(operands).Theyalsocontainanestimateofthenumberofregistersrequiredtoevaluatetheexpression,placedtherebytheexpression-optimizerroutines.Theregistercountsareusedtoguidethecodegenerationprocess,which isbasedontheSethi-Ullmanalgorithm. Themaincodegenerationtablesconsistofentrieseachcontaininganoperatornumberand apointertoasubtableforthecorrespondingoperator.Asubtableconsistsofasequenceof entries,eachwithakeydescribingcertainpropertiesoftheoperandsoftheoperatorinvolved; associatedwiththekeyisacodestring.Oncethesubtablecorrespondingtotheoperatoris found,thesubtableissearchedlinearlyuntilakeyisfoundsuchthatthepropertiesdemandedby -7-thekeyarecompatiblewiththeoperandsofthetreenode.Asuccessfulmatchreturnsthecode string;anunsuccessfulsearch,eitherfortheoperatorinthemaintableoracompatblekeyinthe subtable,returnsafailureindication. Thetablesareallcontainedinafilewhichmustbeprocessedtoobtainanassemblylanguageprogram.Thustheyarewritteninaspecial-purposelanguage.Toprovideddefinitenessto thefollowingdiscussion,hereisanexampleofasubtableentry. %n,aw F addA2,R The‘%’indicatesthekey;theinformationfollowing(uptoablankline)specifiesthecodestring. Verybriefly,thisentryisinthesubtablefor‘+’ofregtab;thekeyspecifiesthattheleftoperandis anyinteger,character,orpointerexpression,andtherightoperandisanywordquantitywhichis directlyaddressible(e.g.avariableorconstant).Thecodestringcallsforthegenerationofthe codetocompiletheleft(first)operandintothecurrentregister(‘F’)andthentoproducean‘add’ instructionwhichaddsthesecondoperand(‘A2’)totheregister(‘R’).Allofthenotationwillbe explainedbelow. Onlythreefeaturesoftheoperandsareusedindecidingwhetheramatchhasoccurred. Theyare: 1.Isthetypeoftheoperandcompatiblewiththatdemanded? 2.Isthe‘degreeofdifficulty’(inasensedescribedbelow)compatible? 3.Thetablemaydemandthattheoperandhavea‘*’(indirectionoperator)asitshighest operator. Assuggestedabove,thekeyforasubtableentryisindicatedbya‘%,’andacommaseparatedpairofspecificationsfortheoperands.(Thesecondspecificationisignoredforunary operators).Aspecificationindicatesatyperequirementbyincludingoneofthefollowingletters. Ifnotypeletterispresent,anyinteger,character,orpointeroperandwillsatisfytherequirement (notfloat,double,orlong). bAbyte(character)operandisrequired. wAword(integerorpointer)operandisrequired. fAfloatordoubleoperandisrequired. dAdoubleoperandisrequired. lAlong(32-bitinteger)operandisrequired. Beforediscussingthe‘degreeofdifficulty’specification,thealgorithmhastobeexplained morecompletely.Rcexpr(andcexpr)arecalledwitharegisternumberinwhichtoplacetheir result.Registers0,1,...areusedduringevaluationofexpressions;themaximumregisterwhich canbeusedinthiswaydependsonthenumberofregistervariables,butinanyeventonlyregisters0through4areavailablesincer5isusedasastackframeheaderandr6(sp)andr7(pc)have specialhardwareproperties.Thecodegenerationroutinesassumethatwhencalledwithregister nasargument,theymayusen+1,...(uptothefirstregistervariable)astemporaries.Consider theexpression‘X+Y’,wherebothXandYareexpressions.Asafirstapproximation,thereare threewaysofcompilingcodetoputthisexpressioninregistern. 1.IfYisanaddressiblecell,(recursively)putXintoregisternandaddYtoit. 2.IfYisanexpressionthatcanbecalculatedinkregisters,whereksmallerthanthenumber ofregistersavailable,compileXintoregistern,Yintoregistern+1,andaddregistern+1to n. 3.Otherwise,compileYintoregistern,savetheresultinatemporary(actually,onthestack) compileXintoregistern,thenaddinthetemporary. Thedistinctionbetweencases2and3thereforedependsonwhethertherightoperandcan becompiledinfewerthankregisters,wherekisthenumberoffreeregistersleftafterregisters0 -8-throughnaretaken:0throughn−1arepresumedtocontainalreadycomputedtemporaryresults; nwill,incase2,containthevalueoftheleftoperandwhiletherightisbeingevaluated. Theseconsiderationsshouldmakeclearthespecificationcodesforthedegreeofdifficulty, bearinginmindthatanumberofspecialcasesarealsopresent: zissatisfiedwhentheoperandiszero,sothatspecialcodecanbeproducedforexpressions like‘x=0’. 1issatisfiedwhentheoperandistheconstant1,tooptimizecaseslikeleftandrightshiftby 1,whichcanbedoneefficientlyonthePDP-11. cissatisfiedwhentheoperandisapositive(16-bit)constant;thistakescareofsomespecial casesinlongarithmetic. aissatisfiedwhentheoperandisaddressible;thisoccursnotonlyforvariablesandconstants, butalsoforsomemorecomplicatedconstructions,suchasindirectionthroughasimplevariable,‘*p++’wherepisaregistervariable(becauseofthePDP-11’sauto-incrementaddress mode),and‘*(p+c)’wherepisaregisterandcisaconstant.Precisely,therequirementis thattheoperandreferstoacellwhoseaddresscanbewrittenasasourceordestinationofa PDP-11instruction. eissatisfiedbyanoperandwhosevaluecanbegeneratedinaregisterusingnomorethank registers,wherekisthenumberofregistersleft(notcountingthecurrentregister).The‘e’ standsfor‘easy.’ nissatisfiedbyanyoperand.The‘n’standsfor‘anything.’ Thesedegreesofdifficultyareconsideredtolieinalinearorderingandanyoperandwhich satisfiesanearlier-mentionedrequirementwillsatisfyalaterone.Sincethesubtablesaresearched linearly,ifa‘1’specificationisincluded,almostcertainlya‘z’mustbewrittenfirsttoprevent expressionscontainingtheconstant0tobecompiledasifthe0were1. Finally,akeyspecificationmaycontaina‘*’whichrequirestheoperandtohaveanindirectionasitsleadingoperator.Examplesbelowshouldclarifytheutilityofthisspecification. Nowletusconsiderthecontentsofthecodestringassociatedwitheachsubtableentry. Conventionally,lower-caselettersinthisstringrepresentliteralinformationwhichiscopied directlytotheoutput.Upper-caselettersgenerallyintroducespecificmacro-operations,someof whichmaybefollowedbymodifyinginformation.Thecodestringsinthetablesarewrittenwith tabsandnew-linesusedfreelytosuggestinstructionswhichwillbegenerated;thetable-compiling programcompressestabs(usingthe0200bitofthenextcharacter)andthrowsawaysomeofthe new-lines.Forexamplethemacro‘F’isordinarilywrittenonalinebyitself;butsinceitsexpan-sionwillendwithanew-line,thenew-lineafter‘F’itselfisdispensable.Thisisalltoreducethe sizeofthestoredtables. Thefirstsetofmacro-operationsisconcernedwithcompilingsubtrees.Recallthatthisis donebythecexprroutine.Inthefollowingdiscussionthe‘currentregister’isgenerallytheargumentregistertocexpr;thatis,theplacewheretheresultisdesired.The‘nextregister’isnumberedonehigherthanthecurrentregister.(Thisexplanationisn’tfullytruebecauseofcomplications,describedbelow,involvingoperationswhichrequireeven-oddregisterpairs.) Fcausesarecursivecalltothercexprroutinetocompilecodewhichplacesthevalueofthe first(left)operandoftheoperatorinthecurrentregister. F1generatescodewhichplacesthevalueofthefirstoperandinthenextregister.Itisincorrectlyusediftheremightbenonextregister;thatis,ifthedegreeofdifficultyofthefirst operandisnot‘easy;’ifnot,anotherregistermightnotbeavailable. FSgeneratescodewhichpushesthevalueofthefirstoperandonthestack,bycallingrcexpr specifyingsptabasthetable. Analogously, S,S1,SS compilethesecond(right)operandintothecurrentregister,thenextregister,orontothe -9-stack. Todealwithregisters,thereare Rwhichexpandsintothenameofthecurrentregister. R1whichexpandsintothenameofthenextregister. R+whichexpandsintothethenameofthecurrentregisterplus1.Itwassuggestedabovethat thisisthesameasthenextregister,exceptforcomplications;hereisoneofthem.Long integervariableshave32bitsandrequire2registers;insuchcasesthenextregisteristhe currentregisterplus2.Thecodewouldliketotalkaboutbothhalvesofthelongquantity, soRreferstotheregisterwiththehigh-orderpartandR+tothelow-orderpart. R−Thisisanothercomplication,involvingdivisionandmod.Theseoperationsinvolveapairof registersofwhichtheodd-numberedcontainstheleftoperand.Cexprarrangesthatthecur-rentregisterisodd;theR−notationallowsthecodetorefertothenextlower,even-numberedregister. Torefertoaddressiblequantities,therearethenotations: A1causesgenerationoftheaddressspecifiedbythefirstoperand.Forthistobelegal,the operandmustbeaddressible;itskeymustcontainan‘a’oramorerestrictivespecification. A2correspondinglygeneratestheaddressofthesecondoperandprovidingithasone. Wenowhaveenoughmechanismtoshowacomplete,ifsuboptimal,tableforthe+operator onwordorbyteoperands. %n,z F %n,1 F incR %n,aw F addA2,R %n,e F S1 addR1,R %n,n SS F add(sp)+,R Thefirsttwosequenceshandlesomespecialcases.Actuallyitturnsoutthathandlingaright operandof0isunnecessarysincetheexpression-optimizerthrowsoutaddsof0.Adding1by usingthe‘increment’instructionisdonenext,andthenthecasewheretherightoperandis addressible.Itmustbeawordquantity,sincethePDP-11lacksan‘addbyte’instruction. Finallythecaseswheretherightoperandeithercan,orcannot,bedoneintheavailableregisters aretreated. Thenextmacro-instructionsareconvenientlyintroducedbynoticingthattheabovetableis suitableforsubtractionaswellasaddition,sincenouseismadeofthecommutativityofaddition. Allthatisneededissubstitutionof‘sub’for‘add’and‘dec’for’inc.’Considerablesavingofspace isachievedbyfactoringoutseveralsimilaroperations.

-10-Iisreplacedbyastringfromanothertableindexedbytheoperatorinthenodebeing expanded.Thissecondarytableactuallycontainstwostringsperoperator. I′isreplacedbythesecondstringinthesidetableentryforthecurrentoperator. Thus,giventhattheentriesfor‘+’and‘−’inthesidetable(whichiscalledinstab)are ‘add’and‘inc,’‘sub’and‘dec’respectively,themiddleofoftheaboveadditiontablecanbewritten %n,1 F I’R %n,aw F IA2,R anditwillbesuitableforsubtraction,andseveralotheroperators,aswell. Next,thereisthequestionofcharacterandfloating-pointoperations. B1generatestheletter‘b’ifthefirstoperandisacharacter,‘f’ifitisfloatordouble,andnothingotherwise.Itisusedinacontextlike‘movB1’whichgeneratesa‘mov’,‘movb’,or ‘movf’instructionaccordingtothetypeoftheoperand. B2isjustlikeB1butappliestothesecondoperand. BEgenerates‘b’ifeitheroperandisacharacterandnullotherwise. BFgenerates‘f’ifthetypeoftheoperatornodeitselfisfloatordouble,otherwisenull. Forexample,thereisanentryinefftabforthe‘=’operator %a,aw %ab,a IBEA2,A1 Notefirstthattwokeyspecificationscanbeappliedtothesamecodestring.Next,observethat whenawordisassignedtoabyteortoaword,orawordisassignedtoabyte,asingleinstruction,amovormovbasappropriate,doesthejob.However,whenabyteisassignedtoaword,it mustpassthrougharegistertoimplementthesign-extensionrules: %a,n S IB1R,A1 Next,thereisthequestionofhandlingindirectionproperly.Considertheexpression‘X+ *Y’,whereXandYareexpressions,AssumingthatYismorecomplicatedthanjustavariable, butontheotherhandqualifiesas‘easy’inthecontext,theexpressionwouldbecompiledbyplacingthevalueofXinaregister,thatof*Yinthenextregister,andaddingtheregisters.Itis easytoseethatabetterjobcanbedonebycompilingX,thenY(intothenextregister),andproducingtheinstructionsymbolizedby‘add(R1),R’.Thisschemeavoidsgeneratingtheinstruction ‘mov(R1),R1’requiredactuallytoplacethevalueof*Yinaregister.Arelatedsituationoccurs withtheexpression‘X+*(p+6)’,whichexemplifiesaconstructionfrequentinstructureand arrayreferences.Theadditiontableshownabovewouldproduce [putXinregisterR] movp,R1 add$6,R1 mov(R1),R1 addR1,R whenthebestcodeis -11- [putXinR] movp,R1 add6(R1),R Aswesaidabove,akeyspecificationforacodetableentrymayrequireanoperandtohavean indirectionasitshighestoperator.Tomakeuseoftherequirement,thefollowingmacrosareprovided. F*thefirstoperandmusthavetheform*X.Ifinparticularithastheform*(Y+c),forsome constantc,thencodeisproducedwhichplacesthevalueofYinthecurrentregister.Otherwise,codeisproducedwhichloadsXintothecurrentregister. F1*resemblesF*exceptthatthenextregisterisloaded. S*resemblesF*exceptthatthesecondoperandisloaded. S1*resemblesS*exceptthatthenextregisterisloaded. FS*Thefirstoperandmusthavetheform‘*X’.PushthevalueofXonthestack. SS*resemblesFS*exceptthatitappliestothesecondoperand. Tocapturetheconstantthatmayhavebeenskippedoverintheabovemacros,thereare #1Thefirstoperandmusthavetheform*X;ifinparticularithastheform*(Y+c)forca constant,thentheconstantiswrittenout,otherwiseanullstring. #2isthesameas#1exceptthatthesecondoperandisused. Nowwecanimprovetheadditiontableabove.Justbeforethe‘%n,e’entry,put %n,ew* F S1* add#2(R1),R andjustbeforethe‘%n,n’put %n,nw* SS* F add*(sp)+,R Whenusingthestackingmacrosthereisnoplacetousetheconstantasanindexword,sothat particularspecialcasedoesn’toccur. Theconstantmentionedabovecanactuallybemoregeneralthananumber.Anyquantity acceptabletotheassemblerasanexpressionwilldo,inparticulartheaddressofastaticcell,perhapswithanumericoffset.Ifxisanexternalcharacterarray,theexpression‘x[i+5]=0’will generatethecode movi,r0 clrbx+5(r0) viathetableentry(inthe‘=’partofefftab) %e*,z F I’B1#1(R) Somemachineoperationsplacerestrictionsontheregistersused.Thedivideinstruction,usedto implementthedivideandmodoperations,requiresthedividendtobeplacedintheoddmember ofaneven-oddpair;otherpeculiaritiesofmultiplicationmakeitsimplesttoputthemultiplicand inanodd-numberedregister.Thereisnotheorywhichoptimallyaccountsforthiskindof requirement.Cexprhandlesitbycheckingforamultiply,divide,ormodoperation;inthesecases, itsargumentregisternumberisincrementedbyoneortwosothatitisodd,andiftheoperation wasdivideormod,sothatitisamemberofafreeeven-oddpair.Theroutinewhichdetermines -12-thenumberofregistersrequiredestimates,conservatively,thatatleasttworegistersarerequired foramultiplicationandthreefortheotherpeculiaroperators.Aftertheexpressioniscompiled, theregisterwheretheresultactuallyendedupisreturned.(Divideandmodareactuallythe sameoperationexceptforthelocationoftheresult). Theseoperationsaretheoneswhichcauseresultstoendupinunexpectedplaces,andthis possibilityaddsafurtherlevelofcomplexity.Thesimplestwayofhandlingtheproblemisalways tomovetheresulttotheplacewherethecallerexpectedit,butthiswillproduceunnecessaryregistermovesinmanysimplecases;‘a=b*c’wouldgenerate movb,r1 mulc,r1 movr1,r0 movr0,a Thenextthoughtisusedthepassed-backinformationastowheretheresultlandedtochangethe notionofthecurrentregister.Whilecompilingthe‘=’operationabove,whichcomesfromatable entrylike %a,e S movR,A1 itissufficienttoredefinethemeaningof‘R’afterprocessingthe‘S’whichdoesthemultiply.This techniqueisinfactused;thetablesarewritteninsuchawaythatcorrectcodeisproduced.The troubleisthatthetechniquecannotbeusedingeneral,becauseitinvalidatesthecountofthe numberofregistersrequiredforanexpression.Considerjust‘a*b+X’whereXissomeexpression.Thealgorithmassumesthatthevalueofa*b,oncecomputed,requiresjustoneregister.If therearethreeregistersavailable,andXrequirestworegisterstocompute,thenthisexpression willmatchakeyspecifying‘%n,e’.Ifa*biscomputedandleftinregister1,thenthereare,contrarytoexpectations,nolongertworegistersavailabletocomputeX,butonlyone,andbadcode willbeproduced.Toguardagainstthispossibility,cexprcheckstheresultreturnedbyrecursive callswhichimplementF,Sandtheirrelatives.Iftheresultisnotintheexpectedregister,then thenumberofregistersrequiredbytheotheroperandischecked;ifitcanbedoneusingthoseregisterswhichremainevenaftermakingunavailabletheunexpectedly-occupiedregister,thenthe notionsofthe‘nextregister’andpossiblythe‘currentregister’areredefined.Otherwisearegister-copyinstructionisproduced.Aregister-copyisalsoalwaysproducedwhenthecurrentopera-torisoneofthosewhichhaveodd-evenrequirements. Finally,thereareafewloose-endmacrooperationsandfactsaboutthetables.Theopera-tors: Visusedforlongoperations.Itiswrittenwithanaddresslikeamachineinstruction;it expandsinto‘adc’(addcarry)iftheoperationisanadditiveoperator,‘sbc’(subtractcarry) iftheoperationisasubtractiveoperator,anddisappears,alongwiththerestoftheline, otherwise.Itspurposeistoallowcommontreatmentoflogicaloperations,whichhaveno carries,andadditiveandsubtractiveoperations,whichgeneratecarries. Tgeneratesa‘tst’instructionifthefirstoperandofthetreedoesnotsettheconditioncodes correctly.Itisusedwithdivideandmodoperations,whichrequireasign-extended32-bit operand.Thecodetablefortheoperationscontainsan‘sxt’(sign-extend)instructionto generatethehigh-orderpartofthedividend. Hisanalogoustothe‘F’and‘S’macros,exceptthatitcallsforthegenerationofcodeforthe currenttree(notoneofitsoperands)usingregtab.Itisusedincctabforalltheoperators which,whenexecutednormally,settheconditioncodesproperlyaccordingtotheresult.It preventsa‘tst’instructionfrombeinggeneratedforconstructionslike‘if(a+b)...’since aftercalculationofthevalueof‘a+b’aconditionalbranchcanbewrittenimmediately. Allofthediscussionaboveisintermsofoperatorswithoperands.Leavesoftheexpression tree(variablesandconstants),however,arepeculiarinthattheyhavenooperands.Inorderto -13-regularizethematchingprocess,cexprexaminesitsoperandtodetermineifitisaleaf;ifso,it createsaspecial‘load’operatorwhoseoperandistheleaf,andsubstitutesitfortheargument tree;thisallowsthetableentryforthecreatedoperatortousethe‘A1’notationtoloadtheleaf intoaregister. Purelytosavespaceinthetables,piecesofsubtablescanbelabelledandreferredtolater. Itturnsout,forexample,thatratherlargeportionsofthetheefftabtableforthe‘=’and‘=+’ operatorsareidentical.Thus‘=’hasanentry %[move3:] %a,aw %ab,a IBEA2,A1 whilepartofthe‘=+’tableis %aw,aw %[move3] Labelsarewrittenas‘%[...:]’,beforethekeyspecifications;referencesarewrittenwith‘%[...]’ afterthekey.Peculiaritiesintheimplementationmakeitnecessarythatlabelsappearbeforereferencestothem. Theexampleillustratestheutilityofallowingseparatekeystopointtothesamecode string.Theassignmentcodeworksproperlyifeithertherightoperandisaword,ortheleft operandisabyte;butsincethereisno‘addbyte’instructiontheadditioncodehastobe restrictedtowordoperands. Delayingandreordering Intertwinedwiththecodegenerationroutinesaretwoother,interrelatedprocesses.The first,implementedbyaroutinecalleddelay,isbasedontheobservationthatnaivecodegenerationfortheexpression‘a=b++’wouldproduce movb,r0 incb movr0,a Thepointisthatthetableforpostfix++hastopreservethevalueofbbeforeincrementingit; thegeneralwaytodothisistopreserveitsvalueinaregister.Aclevererschemewouldgenerate movb,a incb Delayiscalledforeachexpressioninputtorcexpr,anditsearchesforpostfix++and−−operators.Ifoneisfoundappliedtoavariable,thetreeispatchedtobypasstheoperatorandcompiledasitstands;thentheincrementordecrementitselfisdone.Theeffectisasif‘a=b;b++’ hadbeenwritten.Inthisexample,ofcourse,theuserhimselfcouldhavedonethesamejob,but morecomplicatedexamplesareeasilyconstructed,forexample‘switch(x++)’.Anessential restrictionisthattheconditioncodesnotberequired.Itwouldbeincorrecttocompile‘if(a++) ...’as tsta inca beq... becausethe‘inc’destroystherequiredsettingoftheconditioncodes. Reorderingisasimilarsortofoptimization.Manycaseswhichitdetectsareusefulmainly withregistervariables.Ifrisaregistervariable,theexpression‘r=x+y’isbestcompiledas -14-movx,r addy,r butthecodestableswouldproduce movx,r0 addy,r0 movr0,r whichisinfactpreferredifrisnotaregister.(Ifrisnotaregister,thetwosequencesarethe samesize,butthesecondisslightlyfaster.)Theschemeistocompiletheexpressionasifithad beenwritten‘r=x;r=+y’.Thereorderroutineiscalledwithapointertoeachtreethatrcexpr isabouttocompile;ifithastherightcharacteristics,the‘r=x’treeisconstructedandpassed recursivelytorcexpr;thentheoriginaltreeismodifiedtoread‘r=+y’andthecallinginstanceof rcexprcompilesthatinstead.Ofcoursethewholebusinessisitselfrecursivesothatmore extendedformsofthesamephenomenonarehandled,like‘r=x+y|z’. Caredoeshavetobetakentoavoid‘optimizing’anexpressionlike‘r=x+r’into‘r=x;r =+r’.Itisrequiredthattherightoperandoftheexpressionontherightofthe‘=’bea’,distinctfromtheregistervariable. Thesecondcasethatreorderhandlesisexpressionsoftheform‘r=X’usedasasubexpression.Again,thecodeoutofthetablesfor‘x=r=y’wouldbe movy,r0 movr0,r movr0,x whereasifrwerearegisteritwouldbebettertoproduce movy,r movr,x Whenreorderdiscoversthataregistervariableisbeingassignedtoinasubexpression,itcalls rcexprrecursivelytocompilethesubexpression,thenfiddlesthetreepassedtoitsothattheregistervariableitselfappearsastheoperandinsteadofthewholesubexpression.Herecarehastobe takentoavoidaninfiniteregress,withrcexprandreordercallingeachotherforevertohandle assignmentstoregisters. Athirdsetofcasestreatedbyreordercomesupwhenanyname,notnecessarilyaregister, occursasaleftoperandofanassignmentoperatorotherthan‘=’orasanoperandofprefix‘++’ or‘−−’.Unlesscondition-codetestsareinvolved,whenasubexpressionlike‘(a=+b)’isseen, theassignmentisperformedandtheargumenttreemodifiedsothataisitsoperand;effectively‘x +(y=+z)’iscompiledas‘y=+z;x+y’.Similarly,prefixincrementanddecrementarepulled outandperformedfirst,thentheremainderoftheexpression. Throughoutcodegeneration,theexpressionoptimizeriscalledwheneverdelayorreorder changetheexpressiontree.Thisallowssomespecialcasestobefoundthatotherwisewouldnot beseen. ANewInput-OutputPackage D.M.Ritchie AnewpackageofIOroutinesisavailableundertheUnixsystem.Itwasdesignedwiththe followinggoalsinmind. 1.ItshouldbesimilarinspirittotheearlierPortableLibrary,and,totheextentpossible,be compatiblewithit.AtthesametimeafewdubiousdesignchoicesinthePortableLibrary willbecorrected. 2.Itmustbeasefficientaspossible,bothintimeandinspace,sothattherewillbenohesitationinusingitnomatterhowcriticaltheapplication.

-15-3.Itmustbesimpletouse,andalsofreeofthemagicnumbersandmysteriouscallstheuseof whichmarstheunderstandabilityandportabilityofmanyprogramsusingolderpackages. 4.Theinterfaceprovidedshouldbeapplicableonallmachines,whetherornottheprograms whichimplementitaredirectlyportabletoothersystems,ortomachinesotherthanthe PDP11runningaversionofUnix. ItisintendedthatthispackagereplacethePortableLibrary.Althoughitisnotdirectly compatible,asdiscussedbelow,itissufficientlysimilarthatasetofrelativelysmall,inexpensive adaptorroutinesexistwhichmakeitappearidenticaltothecurrentPortableLibraryexceptin someveryobscuredetails. ThemostcrucialdifferencebetweenthispackageandthePortableLibraryisthatthecurrentofferingnamesstreamsintermsofpointersratherthanbytheintegersknownas‘filedescriptors.’Thus,forexample,theroutinewhichopensanamedfilereturnsapointertoacertain structureratherthananumber;theroutinewhichreadsanopenfiletakesasanargumentthe pointerreturnedfromtheopencall. GeneralUsage Eachprogramusingthelibrarymusthavetheline #include<stdio.h> whichdefinescertainmacrosandvariables.Thelibrarycontainingtheroutinesis ‘/usr/lib/libS.a,’sothecommandtocompileis cc...−lS Allnamesintheincludefileintendedonlyforinternalusebeginwithanunderscore‘’toreduce thepossibilityofcollisionwithausername.Thenamesintendedtobevisibleoutsidethepackageare stdinThenameofthestandardinputfile stdoutThenameofthestandardoutputfile stderrThenameofthestandarderrorfile EOFisactually−1,andisthevaluereturnedbythereadroutinesonend-of-fileorerror. NULLisanotationforthenullpointer,returnedbypointer-valuedfunctionstoindicatean error FILEexpandsto‘structiob’andisausefulshorthandwhendeclaringpointerstostreams. BUFSIZisanumber(viz.512)ofthesizesuitableforanIObuffersuppliedbytheuser.See setbuf,below. getc,getchar,putc,putchar,feof,ferror,fileno aredefinedasmacros.Theiractionsaredescribedbelow;theyarementionedhereto pointoutthatitisnotpossibletoredeclarethemandthattheyarenotactuallyfunctions;thus,forexample,theymaynothavebreakpointssetonthem. Theroutinesinthispackage,likethecurrentPortableLibrary,offertheconvenienceofautomaticbufferallocationandoutputflushingwhereappropriate.Absent,however,isthefacilityof changingthedefaultinputandoutputstreamsbyassigningto‘cin’and‘cout.’Thenames ‘stdin,’stdout,’and‘stderr’areineffectconstantsandmaynotbeassignedto. Calls Theroutinesinthelibraryareinnearlyone-to-onecorrespondencewiththoseinthePortable Library.Inseveralcasesthenamehasbeenchanged.Thisisanattempttoreduceconfusion.If theattemptisjudgedtofailthenamesmaybemadeidenticaleventhoughtheargumentsmaybe different.TheorderofthislistgenerallyfollowstheorderusedinthePortableLibrarydocument.

-16-FILE*fopen(filename,type) Fopenopensthefileand,ifneeded,allocatesabufferforit.Filenameisacharacterstringspecifyingthename.Typeisacharacterstring(notasinglecharacter).Itmaybe‘"r",’‘"w",’or ‘"a"’toindicateintenttoread,write,orappend.Thevaluereturnedisafilepointer.Ifitisnull theattempttoopenfailed. intgetc(ioptr) returnsthenextcharacterfromthestreamnamedbyioptr,whichisapointertoafilesuchas returnedbyfopen,orthenamestdin.TheintegerEOFisreturnedonend-of-fileorwhenanerror occurs.Thenullcharacterisalegalcharacter. putc(c,ioptr) Putcwritesthecharactercontheoutputstreamnamedbyioptr,whichisavaluereturnedfrom fopenorperhapsstdoutorstderr.Thecharacterisreturnedasvalue,butEOFisreturnedon error. fclose(ioptr) Thefilecorrespondingtoioptrisclosedafteranybuffersareemptied.Abufferallocatedbythe IOsystemisfreed.Fcloseisautomaticonnormalterminationoftheprogram. fflush(ioptr) Anybufferedinformationonthe(output)streamnamedbyioptriswrittenout.Outputfilesare normallybufferedifandonlyiftheyarenotdirectedtotheterminal,butstderrisunbuffered unlesssetbufisused. exit(errcode) Exitterminatestheprocessandreturnsitsargumentasstatustotheparent.Thisisaspecial versionoftheroutinewhichcallsfflushforeachoutputfile.Toterminatewithoutflushing,use exit. feof(ioptr) returnsnon-zerowhenend-of-filehasoccurredonthespecifiedinputstream. ferror(ioptr) returnsnon-zerowhenanerrorhasoccurredwhilereadingorwritingthenamedstream.The errorindicationlastsuntilthefilehasbeenclosed. getchar() isidenticalto‘getc(stdin)’. putchar(c) isidenticalto‘putc(c,stdout)’. char*gets(s) readscharactersuptoanew-linefromthestandardinput.Thenew-linecharacterisreplacedby anullcharacter.Itistheuser’sresponsibilitytomakesurethatthecharacterarraysislarge enough.Getsreturnsitsargument,ornullifend-of-fileorerroroccurred. char*fgets(s,n,ioptr) readsuptoncharactersfromthestreamioptrintothecharacterpointers.Thereadterminates withanew-linecharacter.Thenew-linecharacterisplacedinthebufferfollowedbyanull pointer.Thefirstargument,oranullpointeriferrororend-of-fileoccurred,isreturned.

-17-puts(s) writesthenull-terminatedstring(characterarray)sonthestandardoutput.Anew-lineis appended.Novalueisreturned. fputs(s,ioptr) writesthenull-terminatedstring(characterarray)onthestreams.Nonew-lineisappended.No valueisreturned. ungetc(c,ioptr) Theargumentcharactercispushedbackontheinputstreamnamedbyioptr.Onlyonecharactermaybepushedback. printf(format,a1,...) fprintf(ioptr,format,a1,...) sprintf(s,format,a1,...) Printfwritesonthestandardoutput.Fprintfwritesonthenamedoutputstream.Sprintfputs charactersinthecharacterarray(string)namedbys.Thespecificationsareasusual. scanf(format,a1,...) fscanf(ioptr,format,a1,...) sscanf(s,format,a1,...) Scanfreadsfromthestandardinput.Fscanfreadsfromthenamedinputstream.Sscanfreads fromthecharacterstringsuppliedass.ThespecificationsareidenticaltothoseofthePortable Library. fread(ptr,sizeof(*ptr),nitems,ioptr) writesnitemsofdatabeginningatptronfileioptr.ItbehavesidenticallytothePortable Library’scread.NoadvancenotificationthatbinaryIOisbeingdoneisrequired;when,for portabilityreasons,itbecomesrequired,itwillbedonebyaddinganadditionalcharactertothe mode-stringonthefopencall. fwrite(ptr,sizeof(*ptr),nitems,ioptr) Likefread,butintheotherdirection. rewind(ioptr) rewindsthestreamnamedbyioptr.Itisnotveryusefulexceptoninput,sincearewoundoutput fileisstillopenonlyforoutput. system(string) atof(s) tmpnam(s) abort(code)

-18-intss() cfree(ptr) wdleng() areavailablewithspecificationsidenticaltothosedescribedforthePortableLibrary. char*calloc(n,sizeof(object)) returnsnullwhennospaceisavailable.Thespaceisguaranteedtobe0. ftoa isnotimplementedbutthereareplausiblealternatives. nargs() isnotimplemented. getw(ioptr) returnsthenextwordfromtheinputstreamnamedbyioptr.EOFisreturnedonend-of-fileor error,butsincethisaperfectlygoodintegerfeofandferrorshouldbeused. putw(w,ioptr) writestheintegerwonthenamedoutputstream. setbuf(ioptr,buf) SetbufmaybeusedafterastreamhasbeenopenedbutbeforeIOhasstarted.Ifbufisnull,the streamwillbeunbuffered.Otherwisethebuffersuppliedwillbeused.Itisacharacterarrayof sufficientsize: charbuf[BUFSIZ]; fileno(ioptr) returnstheintegerfiledescriptorassociatedwiththefile. Severaladditionalroutinesareavailable. fseek(ioptr,offset,ptrname) Thelocationofthenextbyteinthestreamnamedbyioptrisadjusted.Offsetisalonginteger. Ifptrnameis0,theoffsetismeasuredfromthebeginningofthefile;ifptrnameis1,theoffsetis measuredfromthecurrentreadorwritepointer;ifptrnameis2,theoffsetismeasuredfromthe endofthefile.Theroutineaccountsproperlyforanybuffering. longftell(iop) Thebyteoffset,measuredfromthebeginningofthefile,associatedwiththenamedstreamis returned.Anybufferingisproperlyaccountedfor. getpw(uid,buf) ThepasswordfileissearchedforthegivenintegeruserID.Ifanappropriatelineisfound,itis copiedintothecharacterarraybuf,and0isreturned.Ifnolineisfoundcorrespondingtothe userIDthen1isreturned. strcat(s1,s2) S1ands2arecharacterpointers.Theend(nullbyte)ofthes1stringisfoundands2iscopiedto -19-s1startingthere.Thespacepointedtobys1mustbelargeenough. strcmp(s1,s2) Thecharacterstringss1ands2arecompared.Theresultispositive,zero,ornegativeaccording ass1isgreaterthan,equalto,orlessthans2inASCIIcollatingsequence. strcpy(s1,s2) Thenull-terminatedcharacterstrings2iscopiedtothelocationpointedtobys1. strlen(s) Thenumberofbytesinsuptoanullbyteisreturned.Sisacharacterpointer. gcvt(num,ndig,buf) Numisafloatingordoublequantity.NdigsignificantdigitsareconvertedtoASCIIandplaced intothecharacterarraybuf.TheconversionisinFortraneorfstyle,whicheveryieldstheshorter string.Insignificanttrailingzerosareeliminated.ctour:nroff-mgs-Tdvi*>ctour.dvi CChanges 1.Longintegers Thecompilerimplements32-bitintegers.Theassociatedtypekeywordis‘long’.Thewordcan actratherlikeanadjectiveinthat‘longint’meansa32-bitintegerand‘longfloat’meansthe sameas‘double.’Butplain‘long’isalonginteger.Essentiallyalloperationsonlongsareimplementedexceptthatassignment-typeoperatorsdonothavevalues,sol1+(l2=+l3)won’twork. Neitherwilll1=l2=0. Longconstantsarewrittenwithaterminating‘l’or‘L’.E.g."123L"or"0177777777L"or "0X56789abcdL".Thelatterisahexconstant,whichcouldalsohavebeenshort;itismarkedby startingwith"0X".Everyfixeddecimalconstantlargerthan32767istakentobelong,andso areoctalorhexconstantslargerthan0177777(0Xffff,or0xFFFFifyoulike).Awarningisgiven insuchacasesincethisisactuallyanincompatibilitywiththeoldercompiler.Wheretheconstantisjustusedasaninitializerorassignedtosomethingitdoesn’tmatter.Ifitispassedtoa subroutinethentheroutinewillnotgetwhatitexpected. Whenashortandalongintegerareoperandsofanarithmeticoperator,theshortisconvertedto long(withsignextension).Thisistruealsowhenashortisassignedtoalong.Whenalongis assignedtoashortintegeritistruncatedatthehighorderendwithnonoticeofpossiblelossof significantdigits.Thisistrueaswellwhenalongisaddedtoapointer(whichincludesitsusage asasubscript).Theconversionrulesforexpressionsinvolvingdoublesandfloatsmixedwith longsarethesameasthoseforshortintegers,mutatismutandis. Apointtonoteisthatconstantexpressionsinvolvinglongsarenotevaluatedatcompiletime, andmaynotbeusedwhereconstantsareexpected.Thus longx{5000L*5000L}; isillegal; longx{5000*5000}; islegalbutwrongbecausethehigh-orderpartislost;butboth longx25000000L; -20-and longx25.e6; arecorrectandhavethesamemeaningbecausethedoubleconstantisconvertedtolongatcompiletime. 2.Unsignedintegers Anewfundamentaldatatypewithkeyword‘unsigned,’isavailable.Itmaybeusedalone: unsignedu; orasanadjectivewith‘int’ unsignedintu; withthesamemeaning.Therearenotyet(orpossiblyever)unsignedlongsorchars.Themeaningofanunsignedvariableisthatofanintegermodulo2ˆ n,wherenis16onthePDP-11.All operatorswhoseoperandsareunsignedproduceresultsconsistentwiththisinterpretationexcept divisionandremainderwherethedivisorislargerthan32767;thentheresultisincorrect.The dividendinanunsigneddivisionmayhoweverhaveanyvalue(i.e.upto65535)withcorrect results.Rightshiftsofunsignedquantitiesareguaranteedtobelogicalshifts. Whenanordinaryintegerandanunsignedintegerarecombinedthentheordinaryintegeris mappedintoanintegermod2ˆ 16andtheresultisunsigned.Thus,forexample‘u=-1’resultsin assigning65535tou.Thisismathematicallyreasonable,andalsohappenstoinvolvenorun-time overhead. Whenanunsignedintegerisassignedtoaplaininteger,an(undiagnosed)overflowoccurswhen theunsignedintegerexceeds2ˆ 15-1. Itisintendedthatunsignedintegersbeusedincontextswherepreviouslycharacterpointerswere used(artificiallyandnonportably)torepresentunsignedintegers. 3.Blockstructure. Asequenceofdeclarationsmaynowappearatthebeginningofanycompoundstatementin{}. Thevariablesdeclaredtherebyarelocaltothecompoundstatement.Anydeclarationsofthe samenameexistingbeforetheblockwasenteredarepusheddownforthedurationoftheblock. Justasinfunctions,asbefore,autovariablesdisappearandlosetheirvalueswhentheblockis left;staticvariablesretaintheirvalues.Alsoaccordingtothesamerulesasforthedeclarations previouslyallowedatthestartoffunctions,ifnostorageclassismentionedinadeclarationthe defaultisautomatic. Implementationofinner-blockdeclarationsissuchthatthereisnorun-timecostassociatedwith usingthem. 4.Initialization(part1) Thiscompilerproperlyhandlesinitializationofstructuressotheconstruction struct{charname[8];chartype;floatval;}x {"abc",’a’,123.4}; -21-compilescorrectly.Inparticularitisrecognizedthatthestringissupposedtofillan8-character array,the‘a’goesintoacharacter,andthatthe123.4mustberoundedandplacedinasingleprecisioncell.Structuresofarrays,arraysofstructures,andthelikeallwork;amoreformal descriptionofwhatisdonefollows. <initializer>::=<element> <element>::=<expression>|<element>,<element>| {<element>}|{<element>,} Anelementisanexpressionoracomma-separatedsequenceofelementspossiblyenclosedin braces.Inabrace-enclosedsequence,acommaisoptionalafterthelastelement.Thisvery ambiguousdefinitionisparsedasdescribedbelow."Expression"mustofcoursebeaconstant expressionwithinthepreviousmeaningoftheAct. Aninitializerforanon-structuredscalarisanelementwithexactlyoneexpressioninit. An"aggregate"isastructureoranarray.Iftheinitializerforanaggregatebeginswithaleft brace,thenthesucceedingcomma-separatedsequenceofelementsinitializethemembersofthe aggregate.Itiserroneousforthenumberofmembersinthesequencetoexceedthenumberof elementsintheaggregate.Ifthesequencehastoofewmemberstheaggregateispadded. Iftheinitializerforanaggregatedoesnotbeginwithaleftbrace,thenthemembersoftheaggregateareinitializedwithsuccessiveelementsfromthesucceedingcomma-separatedsequence.If thesequenceterminatesbeforetheaggregateisfilledtheaggregateispadded. The"toplevel"initializeristheobjectwhichinitializesanexternalobjectitself,asopposedto oneofitsmembers.Thetoplevelinitializerforanaggregatemustbeginwithaleftbrace. Ifthetop-levelobjectbeinginitializedisanarrayandifitssizeisomittedinthedeclaration,e.g. "inta[]",thenthesizeiscalculatedfromthenumberofelementswhichinitializedit. Shortofcompleteassimilationofthisdescription,therearetwosimpleapproachestotheinitializationofcomplicatedobjects.First,observethatitisalwayslegaltoinitializeanyobjectwitha comma-separatedsequenceofexpressions.Themembersofeverystructureandarrayarestored inaspecifiedorder,sotheexpressionswhichinitializethesemembersmayifdesiredbelaidoutin arowtosuccessively,andrecursively,initializethemembers. Alternatively,thesequencesofexpressionswhichinitializearraysorstructuresmayuniformlybe enclosedinbraces. 5.Initialization(part2) Declarations,whetherexternal,attheheadoffunctions,orininnerblocksmayhaveinitializationswhosesyntaxisthesameaspreviousexternaldeclarationswithinitializations.Theonly restrictionsarethatautomaticstructuresandarraysmaynotbeinitialized(theycan’tbe assignedeither);nor,forthemomentatleast,mayexternalvariableswhendeclaredinsideafunction. Thedeclarationsandinitializationsshouldbethoughtofasoccurringinlexicalordersothatforwardreferencesininitializationsareunlikelytowork.E.g., {intaa; intbc; -22-intc5; ... } Hereaisinitializedbyitself(anditsvalueisthusundefined);bisinitializedwiththeoldvalueof c(whichiseitherundefinedoranycdeclaredinanouterblock). 6.Bitfields Adeclaratorinsideastructuremayhavetheform <declarator>:<constant> whichspecifiesthattheobjectdeclaredisstoredinafieldthenumberofbitsinwhichisspecified bytheconstant.Ifseveralsuchthingsarestackedupnexttoeachotherthenthecompilerallocatesthefieldsfromrighttoleft,goingtothenextwordwhenthenewfieldwillnotfit.The declaratormayalsohavetheform :<constant> whichallocatesanunnamedfieldtosimplifyaccuratemodellingofthingslikehardwareformats wherethereareunusedfields.Finally, :0 meanstoforcethenextfieldtostartonawordboundary. Thetypesofbitfieldscanbeonly"int"or"char".Theonlydifferencebetweenthetwoisinthe alignmentandlengthrestrictions:nointfieldcanbelongerthan16bits,noranycharlongerthan 8bits.Ifacharfieldwillnotfitintothecurrentcharacter,thenitismoveduptothenextcharacterboundary. Bothintandcharfieldsaretakentobeunsigned(non-negative)integers. Bit-fieldvariablesarenotquitefull-classcitizens.Althoughmostoperatorscanbeappliedto them,includingassignmentoperators,theydonothaveaddresses(i.e.therearenobitpointers) sotheunary&operatorcannotbeappliedtothem.Foressentiallythisreasonthereareno arraysofbitfieldvariables. Therearethreetwoesintheimplementation:addition(=+)appliedtofieldscanresultinan overflowintothenextfield;itisnotpossibletoinitializebitfields. 7.Macropreprocessor Theproprocessorhandles‘define’statementswithformalarguments.Theline #definemacro(a1,...,an)...a1...an... isrecognizedbythepresenceofaleftparenthesisfollowingthedefinedname.Whentheform macro(b1,...,bn) isrecognizedinnormalCprogramtext,itisreplacedbythedefinition,withthecorrespondingbi actualargumentstringsubstitutedforthecorrespondingaiformalarguments.Bothactualand -23-formalargumentsareseparatedbycommasnotincludedinparentheses;theformalarguments havethesyntaxofnames. Macroexpansionsarenolongersurroundedbyspaces.Linesinwhichareplacementhastaken placearerescanneduntilnomacrosremain. Thepreprocessorhasarudimentaryconditionalfacility.Alineoftheform #ifdefname isignoredif‘name’isdefinedtothepreprocessor(i.e.wasthesubjectofa‘define’line).Ifname isnotdefinedthenalllinesthroughalineoftheform #endif areignored.Acorrespondingformis #ifndefname ... #endif whichignorestheinterveninglinesunless‘name’isdefined.Thename‘unix’ispredefinedand replacedbyitselftoaidwritersofCprogramswhichareexpectedtobetransportedtoother machineswithCcompilers. Inconnectionwiththis,thereisanewoptiontothecccommand: cc-Dname whichcauses‘name’tobedefinedtothepreprocessor(andreplacedbyitself).Thiscanbeused togetherwithconditionalpreprocessorstatementstoselectvariantversionsofaprogramatcompiletime. Theprevioustwofacilities(macroswitharguments,conditionalcompilation)wereactuallyavailableinthe6thEditionsystem,butundocumented.Newinthisreleaseofthecccommandisthe abilitytonest‘include’files.Preprocessorincludelinesmayhavethenewform #include<file> wheretheanglebracketsreplacedoublequotes.Inthiscase,thefilenameisprependedwitha standardprefix,namely‘/usr/include’.Inisintendedthatcommonly-usedincludefilesbeplaced inthisdirectory;theconventionreducesthedependenceonsystem-specificnamingconventions. Thestandardprefixcanbereplacedbythecccommandoption‘-I’: cc-Iotherdirectory 8.Registers Aformalargumentmaybegiventhestorageclass‘register.’Whenthisoccursthesavesequence copiesitfromtheplacethecallerleftitintoafastregister;allusualrestrictionsonitsusearethe sameasforordinaryregistervariables. Nowanyvariableinsideafunctionmaybedeclared‘register;’ifthetypeisunsuitable,orifthere aremorethanthreeregisterdeclarations,thenthecompilermakesit‘auto’instead.The -24-restrictionthatthe&operatormaynotbeappliedtoaregisterremains. 9.Modedeclarations Adeclarationoftheform typedeftype-specifierdeclarator; makesthenamegiveninthedeclaratorintotheequivalentofakeywordspecifyingthetypewhich thenamewouldhaveinanordinarydeclaration.Thus typedefint*iptr; makes‘iptr’usableindeclarationsofpointerstointegers;subsequentlythedeclarations iptrip; int*ip; wouldmeanthesamething.Typenamesintroducedinthiswayobeythesamescoperulesas ordinaryvariables.Thefacilityisnew,experimental,andprobablybuggy. 10.Restrictions Thecompilerissomewhatstickieraboutsomeconstructionsthatusedtobeaccepted. Onedifferenceisthatexternaldeclarationsmadeinsidefunctionsarerememberedtotheendof thefile,thatisevenpasttheendofthefunction.Themostfrequentproblemthatthiscausesis thatimplicitdeclarationofafunctionasanintegerinoneroutine,andsubsequentexplicitdeclarationofitasanothertype,isnotallowed.Thisturnedouttoaffectseveralsourceprogramsdistributedwiththesystem. Itisnowrequiredthatallforwardreferencestolabelsinsideafunctionbethesubjectofa‘goto.’ Thishasturnedouttoaffectmainlypeoplewhopassalabeltotheroutine‘setexit.’Infacta routineissupposedtobepassedhere,andwhyalabelworkedIdonotknow. Ingeneralthiscompilermakesitmoredifficulttouselabelvariables.Thinkofthisasacontributiontostructuredprogramming. Thecompilernowchecksmultipledeclarationsofthesamenamemorecarefullyforconsistency. Itusedtobepossibletodeclarethesamenametobeapointertodifferentstructures;thisis caught.Sotooaredeclarationsofthesamearrayashavingdifferentsizes.Theexceptionisthat arraydeclarationswithemptybracketsmaybeusedinconjunctionwithadeclarationwitha specifiedsize.Thus inta[];inta[50]; isacceptable(ineitherorder). Anexternalarrayallofwhosedefinitionsinvolveemptybracketsisdiagnosedas‘undefined’by theloader;itusedtobetakenashaving1element.