3.1 Subroutines
CSU11022 – Introduction to Computing II
Dr / School of Computer Science and Statistics
Copyright By PowCoder代写 加微信 powcoder
Subroutines
Programs can be decomposed into blocks of instructions, each performing some well-defined task
compute xy
find the length of a NULL-terminated string convert a string from UPPER CASE to lower case play a sound
We would like to avoid repeating the same set of operations throughout our programs
write the instructions to perform some specific task once
invoke the set of instructions many times to perform the same task
Methods in the Java world!
Functions or Procedures elsewhere
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – UPPER CASE
address = string1;
ch = byte[address];
while (ch != NULL) {
if (ch ≥ ‘a’ && char ≤ ‘z’) {
ch = char & 0xFFFFFFDF;
byte[address] = ch;
address = address + 1;
char = byte[address] ;
address = string2;
Repetition!
Repetition!
ch = byte[address];
while (ch != NULL) {
if (ch ≥ ‘a’ && char ≤ ‘z’) {
ch = ch & 0xFFFFFFDF;
byte[address] = ch;
address = address + 1;
ch = byte[address];
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – UPPER CASE
// UPPER CASE
void upr (address)
ch = byte[address];
while (ch != NULL) {
byte[address] = ch;
Define upr(…)
if (ch ≥ ‘a’ && char ≤ ‘z’) {
ch = ch & 0xFFFFFFDF;
address = address + 1;
ch = byte[address] ;
address = string1;
upr(address);
Invoke upr(…) twice
address = string2;
upr(address);
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – UPPER CASE
// UPPER CASE
void upr (address)
ch = byte[address];
while (ch != NULL) {
upr(string1);
upr(string2);
if (ch ≥ ‘a’ && char ≤ ‘z’) {
Define upr(…)
ch = ch & 0xFFFFFFDF;
byte[address] = ch;
address = address + 1;
ch = byte[address] ;
Invoke upr(…) twice
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Call / Return Example
address = string1;
void upr (address)
ch = byte[address]
while (ch != NULL) {
upr(address);
if (ch ≥ ‘a’ && ch ≤ ‘z’) {
address = string2;
upr(address);
ch = ch & 0xFFFFFFDF;
byte[address] = ch;
How do we know
whether to branch back
address = address + 1;
ch = byte[address];
to A or B ?
Branching to a subroutine: branch to the address (or label) of the first instruction in the subroutine (simple flow control … easy!)
Returning from a subroutine: must have remembered the address that we originally branched from (return address, A or B in the example above)
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Invoking the UPR subroutine
@ Program to convert two strings to UPPERCASE
@ Assume the first string starts at the address in R1
@ Assume the second string starts at the address in R2
MOV R0, R1 @ copy address of first string into R0
BL upr @ invoke upr subroutine
MOV R0, R2 @ copy address of second string into R0
BL upr @ invoke upr subroutine (again)
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Implementing the UPRCASE subroutine
@ upr subroutine
@ Converts a NULL-terminated string to upper case
@ Parameters:
@ R0: string start address
LDRB R4, [R0], #1 @ char = byte[address++]
CMP R4, #0 @ while ( char != 0 )
BEQ .LeWhUpr @ {
CMP R4, #’a’ @ if (char >= ‘a’
BLO .LeIfLwr @ &&
CMP R4, #’z’ @ char <= 'z')
BHI .LeIfLwr @ {
BIC R4, #0x00000020 @ char = char AND NOT 0x00000020
STRB R4, [R0, #-1] @ byte[address - 1] = char
.LeIfLwr: @ }
B .LwhUpr @ }
.LeWhUpr: @
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
3.2 Subroutines - Unintended Side Effects
CSU11022 – Introduction to Computing II
Dr / School of Computer Science and Statistics
What’s wrong with this program?
BL subroutine1 @ invoke subroutine1
@ subroutine1
subroutine1:
ADD R0, R1, R2 @ do something
BL subroutine2 @ call subroutine2
ADD R3, R4, R5 @ do something else
BX LR @ return from subroutine1
@ subroutine2
subroutine2:
BX LR @ just return from subroutine2
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Saving the Link Register
Save the contents of the link register on the system stack at the start of every subroutine
Restore the contents of the link register immediately before returning from every subroutine
@ subroutine1
subroutine1:
ADD R0, R1, R2 @ do something
BL subroutine2 @ call subroutine2
ADD R3, R4, R5 @ do something else
BX LR @ return from subroutine1
Implement this fix now in the sideeffects1 example from the CSU1102x GitLab repository. Verify that the fix works.
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Saving the Link Register
More efficiently, we could restore the saved LR to the PC, avoiding the need for the BX instruction (preferred)
@ subroutine1
subroutine1:
ADD R0, R1, R2 @ do something
BL subroutine2 @ call subroutine2
ADD R3, R4, R5 @ do something else
Implement this fix now in the sideeffects1 example from the CSU1102x GitLab repository. Verify that the fix works.
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
What’s wrong with this program?
Imagine we are using our upr subroutine again ...
@ upr subroutine
@ Converts a NULL-terminated string to upper case
@ Parameters:
@ R0: string start address
LDRB R4, [R0], #1 @ char = byte[address++]
CMP R4, #0 @ while ( char != 0 )
BEQ .LeWhUpr @ {
CMP R4, #'a' @ if (char >= ‘a’
BLO .LeIfLwr @ &&
CMP R4, #’z’ @ char <= 'z')
BHI .LeIfLwr @ {
BIC R4, #0x00000020 @ char = char AND NOT 0x00000020
STRB R4, [R0, #-1] @ byte[address - 1] = char
.LeIfLwr: @ }
B .LwhUpr @ }
.LeWhUpr: @
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
What’s wrong with this program?
... and then use the upr subroutine to convert two strings to UPPER CASE but this time our second string starts at an address in R4 ...
@ Program to convert two strings to UPPERCASE
@ Assume the first string starts at the address in R1
@ Assume the second string starts at the address in R4
MOV R0, R1 @ copy address of first string into R0
BL upr @ invoke upr subroutine
MOV R0, R4 @ copy address of second string into R0
BL upr @ invoke upr subroutine (again)
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Unintended Side Effects
We want (need?) to be able to write subroutines in isolation, independently from the rest of our program
When designing and writing subroutines, clearly and precisely define what effect the subroutine has
Effects outside this definition should be considered unintended and should be hidden by the subroutine
In general, subroutines should save the contents of the registers they use at the start of the subroutine and should restore the saved contents before returning
SOLUTION: PUSH register contents on the stack at the start of a subroutine, POP them off at the end
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Hiding Unintended Side Effects
{R0, R4, LR}
@ upr subroutine
@ Converts a NULL-terminated string to upper case
@ Parameters:
@ R0: string start address
LDRB R4, [R0], #1 @ char = byte[address++]
CMP R4, #0 @ while ( char != 0 )
BEQ .LeWhUpr @ {
CMP R4, #'a' @ if (char >= ‘a’
BLO .LeIfLwr @ &&
CMP R4, #’z’ @ char <= 'z')
BHI .LeIfLwr @ {
BIC R4, #0x00000020 @ char = char AND NOT 0x00000020
STRB R4, [R0, #-1] @ byte[address - 1] = char
.LeIfLwr: @ }
B .LwhUpr @ }
.LeWhUpr: @
{R0, R4, PC}
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
3.3 Subroutines - Parameter Passing
CSU11022 – Introduction to Computing II
Dr / School of Computer Science and Statistics
Passing Parameters
Information must be passed to a subroutine using a fixed and well defined interface, known to both the subroutine and calling programs
upr subroutine had single address parameter
address = string1;
upr(address);
address = string2;
upr(address);
upr(address)
Simplest way to pass parameters to a subroutine is to use well defined registers, e.g. for upr subroutine, use R0 for the address of the string
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – fill
Design and write an ARM Assembly Language subroutine that fills a sequence of words in memory with the same 32-bit value
Pseudo-code solution
fill (address, length, value)
3 parameters
address length value
start address in memory number of words to store value to store
count = 0;
while (count < length)
word[address] = value;
address = address + 4;
count = count + 1;
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – fill subroutine
@ fill subroutine
@ Fills a contiguous sequence of words in memory with the same value
@ Parameters:
@ R0: address – address of first word to be filled
@ R1: length – number of words to be filled
@ R2: value – value to store in each word
PUSH {R0-R2,R4,LR}
MOV R4, #0 @ count = 0;
CMP R4, R1 @ while (count < length)
BHS .LeWhFill @ {
STR R2, [R0, R4, LSL #2] @ word[address+(count*4)] = value;
ADD R4, #1 @ count = count + 1;
B .LwhFill @ }
.LeWhFill: @
POP {R0-R2,R4,PC}
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
In high level languages, the interface is defined by the programmer and the compiler implements and enforces it
In assembly language, the interface must be defined, implemented and enforced by the programmer
ARM Architecture Procedure Call Standard (AAPCS) is a technical document that dictates how a high-level language interface should be implemented in ARM Assembly Language (or machine code!!)
Enforcing the standard in your programs is your job!!
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Simplified Subroutine Interface Guidelines
(based on AAPCS)
Registers Use
Passing parameters to subroutines – avoid using for other variables – corruptible (not saved/restored on stack)
R4 ... R12
Local variables within subroutines – preserved (saved/ restored on stack)
Stack Pointer – preserved through proper use
Link Register – corrupted through subroutine call
Program Counter
Adhering to these guidelines will make it easier to write large programs with many subroutines
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – fill revisited
Based on these guidelines, we could re-write fill (note that I was already adhering to the guidelines for passing parameters but I didn’t need to save R0 or R1!!)
@ fill subroutine
@ Fills a contiguous sequence of words in memory with the same value
@ Parameters:
@ R0: address – address of first word to be filled
@ R1: length – number of words to be filled
@ R2: value – value to store in each word
PUSH {R4,LR}
MOV R4, #0 @ count = 0;
CMP R4, R1 @ while (count < length)
BHS .LeWhFill @ {
STR R2, [R0, R4, LSL #2] @ word[address+(count*4)] = value;
ADD R4, #1 @ count = count + 1;
B .LwhFill @ }
.LeWhFill: @
POP {R4,PC}
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – calling fill
Recall the fill interface ... this is all we need to invoke fill
Note that we only need to know the interface.
We don’t need to know how fill is implemented!
To invoke fill assuming R5 contains the start address, R9 the length to fill and
@ fill subroutine
@ Fills a contiguous sequence of words in memory with the same value
@ Parameters:
@ R0: address – address of first word to be filled
@ R1: length – number of words to be filled
@ R2: value – value to store in each word
R8 the value to fill memory with ...
BL fill @ invoke fill
move parameters into place Invoke subroutine
MOV R0, R5 @ address parameter
MOV R1, R9 @ length parameter
MOV R2, R8 @ value parameter
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – count1s
Design and write an ARM Assembly Language subroutine that counts the number of set bits in a word
@ count1s subroutine
@ Counts the number of set bits (1s) in a word
@ Parameters:
@ R0: wordval – word in which 1s will be counted
@ R0: count of set bits (1s) in wordval
PUSH {R4, LR} @ save registers
MOV R4, R0 @ copy wordval parameter to local variable
MOV R0, #0 @ count = 0;
.LwhCount1s:
CMP R4, #0 @ while (wordval != 0)
BEQ .LeWhCount1s @ {
MOVS R4, R4, LSR #1 @ wordval = wordval >> 1; (update carry)
ADC R0, R0, #0 @ count = count + 0 + carry;
B .LwhCount1s @ }
.LeWhCount1s:
POP {R4, PC} @ restore registers
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Interface Guidelines for Return Values
Use R0 for returning values from subroutines
Registers Use
Passing parameters to subroutines or returning values from subroutines – avoid using for other variables – corruptible
R4 … R12
(not saved/restored on stack)
Local variables within subroutines – preserved (saved/
restored on stack)
Stack Pointer – preserved through proper use
Link Register – corrupted through subroutine call
Program Counter
R0 used to pass wordval parameter and return result value from count1s subroutine (an implementation decision – real AAPCS compilers would also do this!)
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – count1s
Recall the count1s interface
@ count1s subroutine
@ Counts the number of set bits (1s) in a word
@ Parameters:
@ R0: wordval – word in which 1s will be counted
@ R0: count of set bits (1s) in wordval
Note again that we only need to know the interface … we don’t need to know how count1s is implemented
Call count1s, assuming R7 contains the word value to be passed to count1s
MOV R0, R7 @ prepare the parameter
BL count1s @ call count1s
ADD R5, R5, R0 @ do something useful with the result
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Unintended Side Effects – Summary
Good practice to save …
any registers used for local variables (R4 … R12) the link register (LR / R14)
(and optionally, registers used for parameters) but not registers used for return values
… on the system stack at the start of every subroutine
Restore exactly the same saved registers at the end of every subroutine
Avoids unintended side effects and simplifies subroutine interface design
Remember: a subroutine must pop off everything that was pushed on to the stack before it returns
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
3.4 Subroutines – Recursion
CSU11022 – Introduction to Computing II
Dr / School of Computer Science and Statistics
Subroutines can invoke themselves – recursion
Example: Design, write and test a subroutine to compute xn
1 ifn=0 x ifn=1
x. x2 (n−1)/2 ()
ifniseven ifnisodd
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x5 =x×x×x×x×x
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x5 =x×(x×x)×(x×x)
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x5 = x × (x × x)2
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x5 = x × (x2)2
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x5 = x1+(2×2)
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Subroutines can invoke themselves – recursion
Example: Design, write and test a subroutine to compute xn
1 ifn=0 x ifn=1
x. x2 (n−1)/2 ()
ifniseven ifnisodd
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x9 = x × (x2)(9−1)/2
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x9 = x × (x2)4
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x9 = x × ((x2)2)4/2
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
x9 = x × ((x2)2)2
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – power
power (x, n) {
if (n == 0) {
result = 1; }
else if (n == 1)
result = x;
else if (n & 1 == 0) // n is even
result = power (x * x, n >> 1);
else // n is odd
result = x * power (x * x, n >> 1)
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – power (1)
@ power subroutine
@ Computes x^n
@ Parameters:
@ R0: x @ R1: n
PUSH {R4-R6,LR} @ save registers
MOV R4, R0 @ Move parameters to local registers
MOV R5, R1 @ Doing this makes managing registers in subroutines
@ *much* simpler. When we call a subroutine from the
@ body of this subroutine, the parameter registers
@ (R0-R3) will already be free for us to use because
@ we have moved the original parameters to other
@ registers.
Trinity College Dublin, The University of Dublin © / Trinity College Dublin 2015–2022
Example – power (2)
CMP R5, #0 @ if (
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com