编译原理-全动态内存管理.ppt

1、Compiler Theory Fall 2003 Jianhui Yue,Chapter 7,Dynamic Memory Parameter Passing Mechanisms Instructor Jianhui Yue Software College SCU ,Compiler Theory Fall 2003 Jianhui Yue,Limitations of Stack-Based Environment,If a reference to a local variable in a procedure can be returned to the caller, the r

2、esult will be dangling reference. When the procedure is exited, the activation record will be deallocated from the stack. addr = dangle() causes addr to point to an unsafe location. Such program is erroneous in C. (No compiler will give an error message),int *dangle() int x; return ,Compiler Theory

3、Fall 2003 Jianhui Yue,Limitations of Stack-Based Environment (cont),C prohibits local procedures. Functional programming languages (LISP, ML) Functions must be able to be locally defined Passed as parameters Returned as results. Stack-based runtime environment is inadequate for these languages.,Comp

4、iler Theory Fall 2003 Jianhui Yue,Fully Dynamic Environment,It can deallocate activation records only when all references to them have disappeared. Activation records can be dynamically freed at arbitrary times during execution. Fully dynamic environment is more complicated. Tracking the references

5、during execution. Finding and deallocating inaccessible areas of memory at arbitrary times during execution (garbage collection).,Compiler Theory Fall 2003 Jianhui Yue,Activation Records,The basic structure of an activation record remains the same: Space for parameters and local variables. Control a

6、nd access links. The exited activation record remains in memory, to be deallocated at some later time. The entire additional complexity can be encapsulated in a memory manager that replaces the runtime stack operations with more general allocation and deallocation routines.,Compiler Theory Fall 2003

7、 Jianhui Yue,Object-Oriented Languages,OO languages require special mechanisms in the runtime environment to implement their added features: Objects Methods Inheritance Dynamic binding OO languages vary in their requirements for the runtime environment: C+ retains the stack-based environment of C, n

8、o automatic dynamic memory management Smalltalk requires fully dynamic environment similar to LISP,Compiler Theory Fall 2003 Jianhui Yue,Implementation of Objects,Keep a complete description of the class structure in memory during execution. Maintain the inheritance by the superclass pointers. Keep

9、pointers to all methods. Each object keeps: Fields for instance variables A pointer to its defining class All methods (local and inherited) are found through it. Instance variables have predictable offsets. Methods do not. They are maintained in a symbol table structure with lookup capabilities.,Com

10、piler Theory Fall 2003 Jianhui Yue,Implementation of Objects (cont),An alternative approach is to compute a list of code pointers for methods of each class, and store this in (static) memory as a virtual function table. It can be arranged so that each method has a predictable offset. Each object con

11、tains a pointer to the appropriate virtual function table. It is the method of choice for C+.,Compiler Theory Fall 2003 Jianhui Yue,Example 7.8,class A public: double x, y; void f(); virtual void g(); ; class B: public A public: double z; void f(); virtual void h(); ;,A:g,A:g,B:h,Object A,Object B,C

12、ompiler Theory Fall 2003 Jianhui Yue,Heap,The data structure that handles pointer allocation and deallocation is called heap. Heap is usually allocated as a linear block of memory in a way that it can grow, while interfering as little as possible with the stack. Heap provides to operation Allocate T

13、akes size parameter Return a pointer to a block of memory of the correct size or null if none exists. Free Takes a pointer to an allocated block of memory Marks it as being free Must be able to find the size of the block.,Compiler Theory Fall 2003 Jianhui Yue,Heap Implementation,Use circular linked

14、list of free blocks. Two drawbacks: Free operation cannot tell whether its pointer is pointing at a block of memory that was previously allocated by malloc. Need to coalesce blocks to the adjacent free blocks. The result is a free block of the maximal size. This needs to be done to avoid the fragmen

15、tation.,Compiler Theory Fall 2003 Jianhui Yue,Improved Heap Implementation,1 Tow improvements ( more robust , self-coalescing blocks ) Bookkeeping information : Header (next : pointer to the next block in the list , usedsize , freesize ) Free space pointer :memptr ( point to the block hold free spac

16、e ),header,Compiler Theory Fall 2003 Jianhui Yue,malloc and free operation on heap,memptr,memptr,a,b,c,a : initialized b: 3 times malloc operations c free one block,memptr,Compiler Theory Fall 2003 Jianhui Yue,malloc ( nbytes), Header *p ,*newp; unsigned nunits; nunits= ( nbytes+sizeof(Header)-1)/si

17、zeof(Header ) + 1; /* initiate the first header */ /* search the list with the first fit , the p points to the first fit block */ newp=p+p-s.usedsized ; newp -used= nunits; newp -s.freesize=p-s.freesize-nunits; newp-s.next=p-s.next; p-s.freesize=0; p-s.next=newp; memptr=newp; return (void *) (newp+1

18、); ,Compiler Theory Fall 2003 Jianhui Yue,free ( void *ap ), Header *bp,*p,*prev; bp= (Header *) ap 1; /* search the list to find the block containing ap */ prev-s.freesize+=p-s.usedsize+p-s.freesize; prev-s.next=p-s.next; memptr=prev; ,Compiler Theory Fall 2003 Jianhui Yue,Automatic Management of H

19、eap,The programmer uses the explicit management on the heap using manually malloc( ) and free( ). In the fully dynamic runtime environment, the heap should be managed automatically. malloc can be automatically scheduled at each procedure call. free cannot be automatically scheduled on exit Activatio

20、n records must persist until all references to them have disappeared.,Compiler Theory Fall 2003 Jianhui Yue,Mark and Sweep,The standard technique is mark and sweep garbage collection. No memory is freed until the call to malloc fails. Follow all pointer recursively and mark each block of storage rea

21、ched. Sweep linearly through the memory, return unmarked blocks to free memory. Memory compaction by moving all the allocated space to one end of the heap Drawbacks Extra storage for marks Delay in processing (minutes) due to multiple passes.,Compiler Theory Fall 2003 Jianhui Yue,Parameter Passing M

22、echanisms,Parameters correspond the to locations in the activation record, which are filled with parameter values (arguments). To the called procedure, a parameter represents a pure formal value. It serves to establish a location in the activation record, where the procedure can find the value of th

23、e parameter.,Compiler Theory Fall 2003 Jianhui Yue,Common Parameter Passing Mechanisms,Pass by value Pass by reference Pass by value-result Pass by name (delayed evaluation),Compiler Theory Fall 2003 Jianhui Yue,Parameter Evaluation Order,In most situations, the order in which arguments are evaluate

24、d is unimportant. Any evaluation order will produce the same result. It is not true in general. f(+x, x) A standard evaluation order may be specified By the language definition By a compiler writer (different implementations) C compilers typically evaluate their arguments from right to left.,Compile

25、r Theory Fall 2003 Jianhui Yue,Pass by Value,This is the only parameter passing mechanism available in C. The parameters in the body of the procedure are replaced by the values of the arguments. In C, value parameters are viewed as initialized local variables. Changes to them never cause any nonloca

26、l changes.,void inc2(int x) +x; +x; /* incorrect */,void inc2(int* x) +x; +x; /* correct */,inc2(,Compiler Theory Fall 2003 Jianhui Yue,Pass by Reference,Pass by reference passes the location of the variable, so that the parameter becomes an alias for the argument. Any changes made to parameter occu

27、r to the argument as well. This is the only parameter passing in FORTRAN77.,void inc2(int /* correct */,inc2(y);,Compiler Theory Fall 2003 Jianhui Yue,Pass by Reference (cont),The compiler must Compute the address of the argument Store it in the local activation record Turn local accesses to a refer

28、ence parameter into indirect accesses No copy of the passed value is made. This is significant when the parameter is a large structure.,Compiler Theory Fall 2003 Jianhui Yue,Pass by Value-Result,Similar to pass by reference. No actual alias is established The value of the argument is copied and used in the procedure On exit the final value of the parameter is copied back out to the location of the argument. This method is known as copy-in, copy-out or copy-restore.,void p(int x, int y) +x; +y; main () int a=1; p