Flashcards
Week 6
Cards in this deck (47)
- 1Compilation patternsseveral high level programming constructs
There is a standard way to translate each to low level form
The low level statements correspond closely to assembly instructions - 2Compilation patterns Follow the patterns!Helps you understand precisely what high level language constructs mean
Leads to good comments that make the program more readable
The approach scales up to large programs
It is essentially how real compilers work
Saves time because, quicker to catch errors - 3Changeable partsboolean and integer expressions, stateme
- 4Fixed partsgoto, if-then-goto
- 5Labelshave to be different every time, but the structure of the fixed parts never changes
- 6Can you gain efficiency by violating the patternIf the loop executes a million times it saves at most one jump instruction!
• The code is longer, which can make it slower (e.g. because of cache)
• When you do this in a large program it becomes incomprehensible
• Aim for readability and correctness - 7Comments• Initial comments to identify the program, author, date, etc
• Early comments to say what the program does
• High level algorithm (in comments)
• Translation to low level algorithm (in comments)
• Translation to assembly language (with comments)
– Every low level statement appears as a comment in assembly code
• Write the comments first!
– Avoid write assembly code until appears to work and then add comments - 8Why is goto controversial?Unstructured goto leads to complicated code
This has given the goto statement a bad reputation
The compilation patterns provide a safe and systematic way to introduce goto into a program
Goto elimination
– Theorem: every program using goto can be expressed without goto, using while and if-then-else - 9RecordsA record contains several fields: access a field with the dot (.) operator
Some programming languages call it a tuple or struct - 10Defining records non pointer; The record x
x
x_fieldA data 3 ; offset 0 from x
x_fieldB data 4 ; offset 1 from x
x_fieldC data 5 ; offset 2 from x - 11PointersAn alternative way to find the data is to make a pointer to it
– A pointer is an address - 12The & operatorThe & operator gives the address of its operand
– p := x puts the value of x into p
– p := &x puts the address of x into p (the address of x is called a pointer
to x, and we say “p points at x”) - 13The * operatorThe * operator follows a pointer and gives whatever it points to
– *p is an expression whose value is whatever p points to
– y := p stores p into y, so y is also now a pointer to x
– y := *p follows the pointer p, gets the value (which is x) and stores it in y - 14We have now seen two ways to use lea– To load a constant into a register: lea R1,42[R0] ; R1 := 42
– To create a pointer: lea R2,x[R0] ; R2 := &x
– lea can do more… - 15And there are several ways to use load– To load a variable into a register: load R3,x[R0] ; R3 := x
– To access an array element: load R4,a[R5] ; R4 := a[R5]
– To follow a pointer: load R6,0[R7] ; R6 := *R7 - 16Following a pointer to the address of x gives xlea R4,x[R0] ; R4 := &x
load R5,0[R4] ; R5 := *(&x) = x
load R6,x[R0] ; R6 := x - 17Why are pointers helpful?• We can write a block of code that accesses variables through pointers
– Example: a record
• We can reuse it by executing it with the pointer set to point to different data
– Example: an array of records
• Later, we'll see additional benefits of using pointers… - 18Access a record using a pointer; Set x as the current record by making R3 point to it
lea R3,x[R0] ; R3 := &x
; Perform the calculation on the record that R3 points to
load R1,1[R3] ; R1 := (*R3).fieldB
load R2,2[R3] ; R2 := (*R3).fieldC
add R1,R1,R2 ; R1 := (*R3).fieldB + (*R3).fieldC
store R1,0[R3] ; *R3.fieldA := (*R3).fieldB + (*R3).fieldC - 19Many operations cannot be performed directly by a user program because– Main reason: the user could violate system security
– Some operations are difficult to program
– The code would need to change when OS is updated - 20Requests to the Operating System• The program requests the operating system to perform them
– Executing a trap instruction, for example trap R1,R2,R3
• A trap is a jump to the Operating System
– And you don't have to give the address to jump to
• We use pointers to tell the operating system what to do - 21Typical OS requestsThe type of request is a number, placed in R1, and operands are in R2, R3
• Typical requests
– Terminate execution of the program
– Read from a file
– Write to a file
– Allocate a block of memory - 22why compiled programs run only on one operating systemThe specific codes used to make a request are defined by the operating system, not by the hardware
- 23Termination• A program cannot stop the machine
– It requests the operating system to terminate it
• The operating system then removes the program from its tables of running programs, and reclaims any resources dedicated to the program
• In Sigma16, you request termination by trap R0,R0,R0 - 24Character strings: pointer to array of characters• A string like “The cat in the hat” is represented as an array of characters
• Each element of the array contains one character
• If you are writing a string to output, the last character of the string should be a “newline character” - 25Write operation on Sigma16– trap R1,R2,R3
– R1: 2 is the code that indicates a write request
– R2: address of first character of string to write
– R3: length of string (the last word should be newline character)
– See example program Write.asm.txt in Sigma16 - 26Procedures: reusable codeOften there is a sequence of instructions that comes up again and again
We don't want to keep repeating the code
– It's tedious
– It wastes space (all those instructions require memory!)
• Goal: write it once and reuse the same instructions many times - 27Procedure• Write the code one time: the block of code is called a procedure (or
subroutine, function)
• Put the instructions somewhere, but not in the main flow of instructions
• Give the block of code a label
• Every time you need to perform this computation, call it
• When it finishes, the procedure needs to return - 28Call and return– So, each call jumps to the same place, the address of the first instruction
of the procedure
– But the calls come from different places
– Therefore, the procedure must finish by returning to different places - 29The jump-and-link instruction• When the main program calls the procedure, it needs to remember where
the call came from
• This is the purpose of the jal instruction (jump and link)
• jal R5,dowork[R0]
– A pointer to the next instruction after the jal (the return address) is
loaded into the destination register (e.g. R5)
– When dowork finishes, the machine jumps to the return address in R5 - 30Jumping• All jump instructions (jump, jal, jumplt, etc) refer to effective addresses
jump loop[R0] ; goto loop
jump 0[R6] ; goto instruction whose address is in R6
jump const[R2] ; goto instruction whose address is const+R2 - 31Implementing call and return• To call a procedure dowork: jal R13,dowork[R0]
– The address of the instruction after the jal is placed in R13
– The program jumps to the effective address, and the procedure starts
executing
• To return when the procedure has finished: jump 0[R13]
– The effective address is 0 + the address of the instruction after the jal
– The program jumps there and the main program resumes - 32Parameter passage• There are several different conventions for passing arguments to a
procedure, and passing the result back
• What is important is that the caller and the procedure agree on how the
information is passed between them
• If there is a small number of arguments, the caller may put them in registers
before calling the procedure
• If there are many arguments, the caller…
– Builds an array of adjacent memory locations, puts the arguments into
the array, and passes the address of the array in a register - 33A simple convention: the arguments and result are passed in...R1
- 34FunctionsA function is a procedure that
– Receives a parameter (a word of data) from the caller
– Calculates a result
– Passes the result back to the caller when it returns - 35pure function• A pure function is a function that doesn't do anything else
– It doesn't change any global variables, or do any input/output - 36What if a procedure calls another procedure?• Limitations of basic call
– If the procedure modifies any registers, it may destroy data belonging to
the caller
– If the procedure calls another procedure, it can't use R13 again
• Each procedure would need a dedicated register for its return
address, limiting the program to a small number of procedures
– It doesn't allow a procedure to call itself (this is called recursion) - 37Saving stateCalling a procedure creates new information
– The return address
– Whatever values the procedure loads into the registers
• We need to save the caller's state so the procedure won't destroy it - 38Saving registers• Most procedures need to use several registers
• It's nearly impossible to do anything without using some registers!
• The procedure should save the registers it will use by copying them into
memory (with store instructions)
• Before returning the procedure should restore the registers by copying their
values back from memory (with load instructions) - 39Where can the registers be saved?• Two approaches
– Allocate fixed variables in memory to save the registers into (simple but
doesn't allow recursion)
– Use a stack in memory, and push the data onto the stack (this is the best
approach and is used by most programming languages) - 40Caller saves• Caller saves (used occasionally)
– Before calling a procedure, the caller saves the registers, so all its
essential data is in memory
– After the procedure returns, the caller does whatever loads are needed
– Used by functional programming languages, e.g. Haskell, Erlang - 41Callee saves• Callee saves (usually the preferred solution)
- The caller keeps data in registers, and assumes that the procedure won't change it
– Just before starting, the procedure saves the registers it needs to use into memory
– Just before returning, the procedure restores the registers by loading the data from memory
– Used by imperative programming languages, e.g. C/C++, Java, Python - 42Stacks• A stack is a container
• Initially it is empty
• You can push a value onto the stack: this is now sitting on the top of the stack
• You can pop the stack: this removes the most recently pushed value and
returns it
• A stack allows access only to the top value, so you cannot access anything
below the top
• We can save procedure return addresses on a stack because return always
needs the most recently saved return address - 43The call stack Central technique for– Preserving data during a procedure call
– Holding most of your variables - 44The call stack• It has several names (these are all the same thing)
– call stack
– execution stack
– “The stack”
• It's important!
– Most programming languages use it
– Computers are designed to support it
– Often referred to (Stack Overflow web site, etc.) - 45Stack framesThe stack frame contains
– A pointer to the previous stack frame (this is required to make the pop work)
– The return address (saved value of R13)
– The saved registers (so the procedure can use the registers without
destroying information)
– Local variables (so the procedure can have some memory of its own to use) - 46Stack frames logitics• The call stack maintains complete information of all procedure calls and returns
• Every call of a procedure pushes a stack frame
• When the procedure returns, its stack frame is popped (removed) from the stack
• We assume that R14 contains the address of the current (top) stack frame - 47Implementing the call stack• Dedicate R14 to the stack pointer
– This is a programming convention, not a hardware feature
• When the program is started, R14 will be set to point to an empty stack
• When a procedure is called, the saved state will be pushed onto the stack
• When a procedure returns, it pops the stack and restores the state
• The program should never modify R14 apart from the push and pop
Information
- Description
- Computer Science Flashcards on Week 6, created by Isaac Gilbert on 16/02/2022.
- Created by
- Isaac Gilbert
- Views
- 1
- Rating