390CS 536 Spring 2008©Type Checking ReturnsIt is useful to arrange that a staticfield named currentMethod willalways point to the methodDeclNodeof the method we are currentlychecking.Type checking steps:1. IfreturnVal is a null node, checkthatcurrentMethod.returnTypeis Void.2. If returnVal (an expr) is not nullthen check that returnVal’s kindis scalar and returnVal’s type iscurrentMethod.returnType.returnNodeexpr tree391CS 536 Spring 2008©Type Checking MethodDeclarationsType checking steps:1. Create a new symbol table entrym, with type = typeNode.typeand kind = Method.2. Check thatidentNode.idname isnot already in the symbol table;if it isn’t, enterm usingidentNode.idname.3. Create a new scope in thesymbol table.4. SetcurrentMethod = thismethodDeclNode.methodDeclNodeidentNodetypeNodeargs treedecls treestmts tree392CS 536 Spring 2008©5. Type check the args subtree.6. Build a list of the symbol tablenodes corresponding to the argssubtree; store it in m.7. Type check thedecls subtree.8. Type check thestmts subtree.9. Close the current scope at thetop of the symbol table.393CS 536 Spring 2008©Type Checking Method CallsWe consider calls of procedures in astatement. Calls of functions in anexpression are very similar.Type checking steps:1. Check thatidentNode.idname isdeclared in the symbol table. Itstype should beVoid and kindshould beMethod.2. Type check theargs subtree.3. Build a list of the expressionnodes found in the args subtree.callNodeidentNodeargs tree394CS 536 Spring 2008©4. Get the list of parametersymbols declared for themethod (stored in the method’ssymbol table entry).5. Check that the arguments listand the parameter symbols listboth have the same length.6. Compare each argument nodewith its correspondingparameter symbol:(a) Both should have the sametype.(b) AVariable, Value, orScalarParm kind in an argumentnode matches aScalarParmparameter. An Array orArrayParm kind in an argumentnode matches anArrayParmparameter.395CS 536 Spring 2008©Reading AssignmentRead Chapter 9 of Crafting aCompiler, 2nd Edition.396CS 536 Spring 2008©Virtual Memory & Run-TimeMemory OrganizationThe compiler decides how dataand instructions are placed inmemory.It uses an address space providedby the hardware and operatingsystem.This address space is usuallyvirtual—the hardware andoperating system mapinstruction-level addresses to“actual” memory addresses.Virtual memory allows:• Multiple processes to run inprivate, protected address spaces.• Paging can be used to extendaddress ranges beyond actualmemory limits.397CS 536 Spring 2008©Run-Time Data StructuresStatic StructuresFor static structures, a fixedaddress is used throughoutexecution.This is the oldest and simplestmemory organization.In current compilers, it is usedfor:• Program code (often read-only &sharable).• Data literals (often read-only &sharable).• Global variables.• Static variables.398CS 536 Spring 2008©Stack AllocationModern programming languagesallow recursion, which requiresdynamic allocation.Each recursive call allocates a newcopy of a routine’s local variables.The number of local dataallocations required duringprogram execution is not knownat compile-time.To implement recursion, all thedata space required for a methodis treated as a distinct data areathat is called a frame or activationrecord.Local data, within a frame, isaccessible only while asubprogram is active.399CS 536 Spring 2008©In mainstream languages like C,C++ and Java, subprograms mustreturn in a stack-like manner—themost recently called subprogramwill be the first to return.A frame is pushed onto a run-timestack when a method is called(activated).When it returns, the frame ispopped from the stack, freeingthe routine’s local data.As an example, consider thefollowing C subprogram:p(int a) {double b;double c[10];b = c[a] * 2.51;}400CS 536 Spring 2008©Procedure p requires space for theparameter a as well as the localvariables b and c.It also needs space for controlinformation, such as the returnaddress.The compiler records the spacerequirements of a method.The offset of each data itemrelative to the beginning of theframe is stored in the symboltable.The total amount of spaceneeded, and thus the size of theframe, is also recorded.Assume p’s control informationrequires 8 bytes (this size isusually the same for all methods).Assume parameter a requires 4bytes, local variable b requires 8401CS 536 Spring 2008©bytes, and local array c requires80 bytes.Many machines require that wordand doubleword data be aligned,so it is common to pad a frame sothat its size is a multiple of 4 or 8bytes.This guarantees that at all timesthe top of the stack is properlyaligned.402CS 536 Spring 2008©Here is p’s frame:Within p, each local data object isaddressed by its offset relative tothe start of the frame.This offset is a fixed constant,determined at compile-time.We normally store the start of theframe in a register, so each pieceof data can be addressed as a(Register, Offset) pair, which is astandard addressing mode inalmost all computer architectures.Control InformationSpace for aSpace for bSpace for cPaddingOffset = 0Offset = 8Offset = 12Offset = 20Total size= 104403CS 536 Spring 2008©For example, if register R pointsto the beginning of p’s frame,variable b can be addressed as(R,12), with 12 actually beingadded to the contents of R at run-time, as memory addresses areevaluated.Normally, the literal 2.51 ofprocedure p is not stored in p’sframe because the values of localdata that are stored in a framedisappear with it at the end of acall.It is easier and more efficient toallocate literals in a static area,often called a literal pool orconstant pool. Java uses aconstant pool to store literals,type, method and interfaceinformation as well as class andfield names.404CS 536 Spring 2008©Accessing Frames at Run-TimeDuring execution there can bemany frames on the stack. When aprocedure A calls a procedure B,aframe for B’s local variables ispushed on the stack, covering A’sframe. A’s frame can’t be poppedoff because A will resumeexecution after B returns.For recursive routines there canbe hundreds or even thousands offrames on the stack. All framesbut the topmost representsuspended subroutines, waitingfor a call to return.The topmost frame is active; it isimportant to be able to access itdirectly.The active frame is at the top ofthe stack, so the stack top405CS 536 Spring 2008©register could be used to accessit.The