Assembly Language - cs.colostate.edu

Assembly Language - cs.colostate.edu

Chapter 10 Memory Model for Program Execution Original slides by Chris Wilcox, Modified by Phil Sharp Colorado State University 1 How do we allocate memory during the execution of a program? Programs need memory for code and data instructions, global, local, and dynamically allocated variables, etc. Modern programming practices encourage many (reusable) functions, callable from anywhere. Function may be called multiple times before first call returns Some memory can be statically allocated, since the size and type is

known at compile time. (global variables) Some memory must be allocated dynamically, size and type is unknown at compile time. (dynamically allocated memory, i.e. malloc) 2 Why is memory allocation important? To do useful work all programs must be able to store data. There are not enough registers to store everything that is required in a register. Passing stucts by value Dynamic (heap) allocation is slower that static allocation so not ideal for all memory storage. Static allocation of memory resources is inflexible and can be inefficient. 3 What do we care about? Fast program execution Efficient memory usage Avoid memory fragmentation Maintain data locality

Allow recursive calls Support parallel execution Minimize resource allocation Memory shouldnt be allocated for functions that are not executed. 4 Consider the following code: int i = 10; int main(){ int a = 5; int b = 20; int c = foo(a, b); } int foo(int x, int y){ int z; z = x + y; return z; } What needs to be stored? Code, parameters, locals, globals, return values 5 Storage Requirements

Code must be stored in memory so that we can execute the function. The return address must be stored so that control can be returned to the caller. Parameters must be sent from the caller to the callee Return values must be sent from the callee to the caller Local variables for the function must be stored somewhere, is one copy enough? 6

Possible Solution: Mixed Code and Data Function implementation: foo foo_rv foo_ra foo_paramx foo_paramy foo_localz foo_begin BR foo_begin .BLKW 1 .BLKW 1 .BLKW 1 .BLKW 1 .BLKW 1 ST R7, foo_ra LD R7, foo_ra RET ; ; ;

; ; ; ; skip over save locations return value return address x parameter y parameter z local save return ; restore return Construct data section by appending foo_ 7 Possible Solution: Mixed Code and Data Calling sequence ST R1, foo_paramx ST R2, foo_paramy JSR foo LD R3, foo_rv

; ; ; ; R1 has x R2 has y Function call R3 = return value Code generation is relatively simple. Few instructions are spent moving data. 8 Possible Solution: Mixed Code and Data Advantages: Code and data are close together Conceptually easy to understand Minimizes register usage for variables

Data persists through life of program Disadvantages: Cannot handle recursion or parallel execution Code is vulnerable to self-modification Consumes resource for inactive functions 9 Possible Solution: Separate Code and Data Data Storage: ;memory location x4000 foo_rv .BLKW 1 ; foo return value foo_ra .BLKW 1 ; foo return address foo_paramx .BLKW 1 ; foo x parameter foo_paramy .BLKW 1 ; foo y parameter foo_localz .BLKW 1 ; foo z local bar_rv .BLKW 1

; bar return value bar_ra .BLKW 1 ; bar return address bar_paramw .BLKW 1 ; bar w parameter Code for foo() and bar() are somewhere else say x3000 Function call code is similar to mixed solution Why might this not be the case 10 Possible Solution: Separate Code and Data Advantages: Code can be marked read only - Because code is separated from data in memory Conceptually easy to understand Early Fortran used this scheme

Data persists through life of program Disadvantages: Cannot handle recursion or parallel execution Consumes resource for inactive functions 11 Real Solution: Execution Stack Instructions are stored in code segment Global data is stored in data segment Statically allocated memory uses stack Dynamically allocated memory uses heap Code Data Heap Stack Code segment is write protected Data segment for initialized and uninitialized globals Heap can be fragmented Stack size is usually limited Stack can grow either direction (usual

convention is down) 12 Stacks A LIFO (last-in first-out) Abstract Data Type. The first thing you put in is the last thing you take out. The last thing you put in is the first thing you take out. Abstract Data Type (ADT): A data type that is defied by its behavior. The user of the ADT does not need to know how the behavior is achieved. Other examples: Lists, Queues, Heaps, Sets, Maps, etc Two main operations: PUSH: add an item to the stack POP: remove an item from the stack Stacks are used in many areas of Computer Science ex. Compilers, Graph/Tree traversals, PDA 10-13 A Physical Stack Coin rest in the arm of an automobile Initial State 1995

1996 1998 1982 1995 1998 1982 1995 After One Push After Three More Pushes After One Pop First quarter out is the last quarter in. 10-14 A Software Implementation Data items don't move in memory, just our idea about there the TOP of the stack is.

TOP ////// ////// #12 ////// ////// #5 #5 ////// ////// #31 #31 //////

#18 #18 #18 ////// ////// ////// x4000 Initial State TOP R6 TOP ////// x3FFF After One Push

R6 x3FFC R6 After Three More Pushes #12 TOP R6 x3FFE After Two Pops By convention, R6 holds the Top of Stack (TOS) pointer. 10-15 How does the Execution Stack work? First In, Last Out (FILO) data structure PUSH adds data, POP removes data Stack grows and shrinks as data is added and removed

Stack grows downward in memory Function calls allocate space on the stack Known as stack frames Returning from a function cleans up by freeing the stack frame Done simply by changing the value in R6 Corresponds nicely to nested function calls By looking at the entire stack in memory it is possible to see the history of function calls that lead to the current function Useful for debugging 16 Execution / Run Time Stack Each rectangle corresponds to one stack frame, which is the stack space allocated to a particular invocation of a function main() calls foo(5,6) foo() calls bar(A) bar() calls baz(7) baz() calls baz(6)

baz(6) baz(7) bar(A) foo(5,6) main() 17 What has to happen in a function call Caller passes arguments to Callee Caller invokes subroutine (JSR). Callee allocates space for return value. Callee executes function code. Callee stores result into return value space. Callee returns (JMP R7). Caller loads return value.

Parameters, return value, return address, and locals are stored on the stack. The order above determines the responsibility and order of stack operations. 18 Stack Frame / Activation Record A stack frame or activation record holds the memory required for a function call: Locals Return Address Return Value Parameters Stack frame below this frame contains the function that called this function. Stack frame above this frame contains the functions called from this function. Caller pushes parameters. Callee allocates space for the return value, saves the return address,

allocates/frees local variables, and stores the return value. 19 Stack Pointers We will need a variable to store the stack pointer (SP), LC3 assembly uses R6. Stack execution is ubiquitous, so hardware can have a special register to hold the stack pointer, sometimes even specific instructions. Problem: stack pointer is difficult to use to access data, since it moves around constantly. Solution: allocate another variable called a frame pointer (FP), for stack frame, uses R5. Frame pointer points to the same location for duration of the function Where should frame pointer point? Our convention sets it to point to the first local variable. 20 Execution Stack Definition: A stack frame or activation record is the memory required for a function call:

Locals Return Address Frame Pointer Return Value Parameters Locals are accessed by negative offsets from frame pointer. Parameters and return value are accessed by positive offsets. Most offsets are small, this explains LDR/STR implementation. Base register stores pointer, signed offset accesses both directions. 21 Frame Pointer In the previous solutions, the compiler/assembly programmer allocated parameters and locals in fixed memory locations. Using an execution stack means parameters and locals are constantly moving around. The frame pointer solves this problem by using fixed offsets instead of addresses.

The assembler can generate code using offsets, without knowing where the stack frame will reside. Frame pointer needs to be saved and restored around function calls. How about the stack pointer? 22 Nested Calls baz(7) Locals are accessed by negative offsets from frame pointer. bar(A) foo(5,6) Parameters and return value are accessed by positive offsets. main() Most offsets are small, this explains LDR/STR implementation. Base register stores pointer, signed offset accesses both directions. baz(7) FP(baz) bar(A)

FP(bar) foo(5,6) FP(foo) main() Execution Stack Advantages: Code can be marked read only Conceptually easy to understand Supports recursion and parallel execution No resources for inactive functions Good data locality, no fragmenting Minimizes register usage

Disadvantages: More memory than static allocation 24 POP and PUSH POP and PUSH: pseudo-instructions that have the following semantics. PUSH Rx ADD R6,R6,#-1 STR Rx,R6,#0 ; Decrement SP ; Store value LDR Rx,R6,#0 ADD R6,R6,#1 ; Load value ; Increment SP POP Rx 25 Summary of LC-3 Function Call

Implementation 1. Caller pushes arguments (last to first). 2. Caller invokes subroutine (JSR). 3. Callee allocates return value, pushes R7 and R5. 4. Callee sets up new R5; allocates space for local variables. 5. Callee executes function code. 6. Callee stores result into return value slot.

7. Callee pops local vars, pops R5, pops R7. 8. Callee returns (JMP R7). 9. Caller loads return value and pops arguments. 10. Caller resumes computation Detailed Example int A = 5; int B = 20; int C; int main(){ C = FOO(A, B); } int FOO(int x, int y){ int temp; temp = x + y; return temp;

} 27 Detailed Example Main program to illustrate stack convention: MAIN .ORIG x3000 LD R6,STACK LD R0, B PUSH R0 LD R1, A PUSH R1 JSR FOO LDR R0,R6,#0 ADD R6,R6,#3 ST R0, C HALT ; ; ; ;

; ; ; ; ; init stack pointer load second operand PUSH second operand load first operand PUSH first operand call function POP return value unwind stack store result 28 Detailed Example A SP B

Stack before JSR instruction 29 Detailed Example Function code to illustrate stack convention: FOO ADD R6,R6,#-1 PUSH R7 PUSH R5 ADD R5,R6,#-1 ; ; ; ; alloc return value PUSH return address PUSH frame pointer FP = SP-1 ADD LDR LDR ADD

STR ; ; ; ; ; alloc local variable load first operand / A load second operand / B add operands store local variable R6,R6,#-1 R2,R5,#4 R3,R5,#5 R4,R3,R2 R4,R5,#0 30 Detailed Example FP[0]

FP[1] FP[2] FP[3] FP[4] FP[5] Local Variable / temp FP Frame Pointer Return Address Return Value First Operand / A Second Operand / B Stack during body of FUNCTION 31 Detailed Example Function code to illustrate stack convention: FOO ; stack STR ADD POP

POP RET A B C STACK exit code R4,R5,#3 R6,R5,#1 R5 R7 .FILL #5 .FILL #20 .BLKW 1 .FILL x4000 ; ; ; ; ; store return value

SP = FP+1 POP frame pointer POP return address return ; first operand ; second operand ; result ; stack address 32 Stack Execution Summary of memory model: We have discussed the stack model for execution of C programs, and along the way we have shown how a compiler might generate code for function calls. P7 Write a recursive function in C, then implement the same function in assembly code, managing memory using the stack model. 33 Summary of LC-3 Function Call

Implementation 1. Caller pushes arguments (last to first). 2. Caller invokes subroutine (JSR). 3. Callee allocates return value, pushes R7 and R5. 4. Callee sets up new R5; allocates space for local variables. 5. Callee executes function code. 6. Callee stores result into return value slot.

7. Callee pops local vars, pops R5, pops R7. 8. Callee returns (JMP R7). 9. Caller loads return value and pops arguments. 10. Caller resumes computation

Recently Viewed Presentations

  • PowerPoint Presentation

    PowerPoint Presentation

    Division by One Digit Divisors Allegra James and Larry Wershbale Media Design and Production ISTC 665 What are you doing when you divide? When you divide, you are trying to split something into equally numbered groups Take these 16 apples:...
  • Eye Witnesses to Peace 1918-20: Primary Sources from LSE Archives

    Eye Witnesses to Peace 1918-20: Primary Sources from LSE Archives

    Eye Witness to Peace 1918-20: Primary Sources from LSE Archives. The resource is linked to sections on the League of Nations in the Giving Peace a Chance: From the League of Nations to Greenham Common exhibition at LSE Library 4...
  • Transcultural Guidelines for Health Care Providers

    Transcultural Guidelines for Health Care Providers

    Knowledge of various cultural characteristics. Application of cultural knowledge & understanding in the health care setting. Ethnocentrism. Even though we understand that everyone is different, we still tend to subconsciously believe that our culture & religion is the right one....
  • The Scientific Method

    The Scientific Method

    The Scientific Method
  • Read about TBEAR (research) Use TBEAR as  A

    Read about TBEAR (research) Use TBEAR as A

    The acronym is as follows: T = topic sentence, B = bridge to evidence, E = evidence, A = analysis, R = return to topic. After taking notes on the paragraph structure and literary device focused on for the week,...
  • MARCH 24TH, 2011 STARFISH DISSECTION PREP Starfish Main

    MARCH 24TH, 2011 STARFISH DISSECTION PREP Starfish Main

    EXTERNAL ANATOMY. Arms - locomotion, capturing preyCentral Disc - site of main organsSieve Plate (Madreporite) - filtered water intakeTube Feet - Used for gripping, moving, huntingSkin Gills (Dermal Branchiae) - diffusion of oxygen and carbon dioxidePedicellariae - miniature pincer stalksAmbulacral...
  • PowerPoint Presentation

    PowerPoint Presentation

    28His breath is like a rushing torrent, rising up to the neck. ... Suddenly a great company of the heavenly host appeared with the angel, praising Elohim and saying, "Glory to Elohim in the highest, and on earth peace to...
  • 1 1 NET 311 INFORMATION SECURITY Networks and

    1 1 NET 311 INFORMATION SECURITY Networks and

    Step 1: Create 16 subkeys, each of which is 48-bits long. 28-Feb-17. Networks and Communication Department. We now form the keys K n, for 1<=n<=16, by applying the following permutation table to each of the concatenated pairs C n D...