Computer Organization and Design: Chapter 2

undefined
 
C
h
a
p
t
e
r
 
2
 
Instructions: Language
of the Computer
undefined
 
S
h
i
f
t
 
O
p
e
r
a
t
i
o
n
s
 
shamt: how many positions to shift
Shift left logical
Shift left and fill with 0 bits
LSL 
by 
i
 bits multiplies by 2
i
Shift right logical
Shift right and fill with 0 bits
LSR 
by 
i
 bits divides by 2
i
 (unsigned only)
 
2
undefined
 
A
N
D
 
O
p
e
r
a
t
i
o
n
s
 
Useful to mask bits in a word
Select some bits, clear others to 0
 
AND X9,X10,X11
00000000 00000000 00000000 00000000 00000000 00000000 00001101 11000000
 
X10
 
X11
 
X9
00000000 00000000 00000000 00000000 00000000 00000000 00111100 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00001100 00000000
 
3
undefined
 
O
R
 
O
p
e
r
a
t
i
o
n
s
 
Useful to include bits in a word
Set some bits to 1, leave others unchanged
 
OR X9,X10,X11
00000000 00000000 00000000 00000000 00000000 00000000 00001101 11000000
 
X10
 
X11
 
X9
00000000 00000000 00000000 00000000 00000000 00000000 00111100 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00111101 11000000
 
4
undefined
 
E
O
R
 
O
p
e
r
a
t
i
o
n
s
 
Differencing operation
create a 0 when bits are the same and a 1 if
they are different
the equivalent to NOT is an EOR 111…111
 
EOR X9,X10,X12  // NOT operation
00000000 00000000 00000000 00000000 00000000 00000000 00001101  11000000
 
X10
 
X12
 
X9
11111111    11111111  11111111   11111111   11111111   11111111   11111111   11111111
11111111    11111111  11111111   11111111   11111111   11111111   11110010  00111111
 
5
undefined
 
C
o
n
d
i
t
i
o
n
a
l
 
O
p
e
r
a
t
i
o
n
s
 
Branch to a labeled instruction if a condition is
true
Otherwise, continue sequentially
 
CBZ register, L1
if (register == 0) branch to instruction labeled L1;
Compare and branch if zero
 
CBNZ register, L1
if (register != 0) branch to instruction labeled L1;
Compare and branch if not zero
B L1
branch unconditionally to instruction labeled L1;
 
6
undefined
 
C
o
m
p
i
l
i
n
g
 
I
f
 
S
t
a
t
e
m
e
n
t
s
 
C code:
 
if (i==j) f = g+h;
else f = g-h;
f, g, … in X22, X23, …
Compiled LEGv8 code:
 
SUB X9,X22,X23 // 
X9 = i − j
 
CBNZ X9,Else 
// 
go to Else if i ≠ j (X9 ≠ 0)
 
ADD X19,X20,X21 
// 
f = g + h (skipped if i ≠ j)
 
B Exit // 
go to Exit
Else:
 
SUB X9,X22,x23 
// 
f = g −h
Exit: …
Assembler calculates addresses
 
7
undefined
 
C
o
m
p
i
l
i
n
g
 
L
o
o
p
 
S
t
a
t
e
m
e
n
t
s
 
C code:
 
while (save[i] == k) i += 1;
i in x22, k in x24, address of save in x25
Compiled LEGv8 code:
 
Loop: LSL
 
X10,X22,#3 
// Temp reg X10 = i * 8
      ADD    X10,X10,X25 
// X10 = address of save[i]
      LDUR   X9,[X10,#0] 
// Temp reg X9 = save[i]
      SUB    X11,X9,X24 
// X11 = save[i] − k
      CBNZ   X11,Exit 
// go to Exit if save[i] ≠ k(X11 ≠ 0)
        ADDI   X22,X22,#1 
// i = i + 1
      B      Loop 
// go to Loop
Exit: …
 
8
undefined
 
B
a
s
i
c
 
B
l
o
c
k
s
 
A basic block is a sequence of instructions
with
No embedded branches (except at end)
No branch targets (except at beginning)
 
A compiler identifies basic
blocks for optimization
An advanced processor
can accelerate execution
of basic blocks
 
9
undefined
 
M
o
r
e
 
C
o
n
d
i
t
i
o
n
a
l
 
O
p
e
r
a
t
i
o
n
s
 
Condition codes, set from arithmetic instruction with S-
suffix (ADDS, ADDIS, ANDS, ANDIS, SUBS, SUBIS)
negative (N):  result had 1 in MSB
zero (Z):  result was 0
overlow (V):  result overflowed
carry (C):  result had carryout from MSB
Use subtract (A-B) to set flags, then conditionally branch:
 
10
10
undefined
 
C
o
n
d
i
t
i
o
n
a
l
 
b
r
a
n
c
h
e
s
 
LEGv8 includes four branches to complete the testing of
the individual condition code bits:
Branch on minus (B.MI): N=1;
Branch on plus (B.PL): N=0;
Branch on overflow set (B.VS): V=1;
Branch on overflow clear (B.VC): V=0.
An alternative to condition codes:
have instructions that compare two registers and then branch
based on the result.
compare two registers and set a third register to a result
indicating the success of the comparison, which a subsequent
conditional branch instruction then tests to see if register is non-
zero (condition is true) or zero (condition is false).
Conditional branches in MIPS follow the latter approach
 
11
11
undefined
 
C
o
n
d
i
t
i
o
n
a
l
 
E
x
a
m
p
l
e
 
if (a > b) a += 1;
a in X22, b in X23
 
  SUBS X9,X22,X23  // use subtract to make comparison
  B.LTE Exit               // conditional branch
  ADDI X22,X22,#1
Exit:
 
12
12
undefined
 
S
i
g
n
e
d
 
v
s
.
 
U
n
s
i
g
n
e
d
 
Signed comparison
Unsigned comparison
Example
X22 = 
1111 1111 1111 1111 1111 1111 1111 1111
X23 = 
0000 0000 0000 0000 0000 0000 0000 0001
X22 < X23 # signed
–1 < +1
X22 > X23 # unsigned
+4,294,967,295 > +1
 
13
13
undefined
 
P
r
o
c
e
d
u
r
e
 
C
a
l
l
i
n
g
 
Steps required
1.
Place parameters in registers X0 to X7
2.
Transfer control to procedure
3.
Acquire storage for procedure
4.
Perform procedure’s operations
5.
Place result in register for caller
6.
Return to place of call (address in X30)
§2.8 Supporting Procedures in Computer Hardware
 
14
14
undefined
 
P
r
o
c
e
d
u
r
e
 
C
a
l
l
 
I
n
s
t
r
u
c
t
i
o
n
s
 
Procedure call: branch-and-link instruction
 
BL ProcedureLabel
Address of following instruction put in LR (X30)
Jumps to target address
Procedure return: branch register instruction
 
BR LR
Copies LR (X30) to program counter
Can also be used for computed jumps
e.g., for case/switch statements
Program Counter (PC): register containing the
address of the current instruction
BL
 saves PC+4 in register LR
 
15
15
undefined
 
L
e
a
f
 
P
r
o
c
e
d
u
r
e
 
E
x
a
m
p
l
e
 
C code:
 
long long int leaf_example (long long int
g, long long int h, long long int i, long
long int j)
{ long long int f;
  f = (g + h) - (i + j);
  return f;
}
Arguments g, …, j in X0, …, X3
f in X19 (hence, need to save $s0 on stack)
 
16
16
undefined
 
L
o
c
a
l
 
D
a
t
a
 
o
n
 
t
h
e
 
S
t
a
c
k
 
17
17
undefined
 
LEGv8 code:
 
leaf_example:
 
SUBI SP,SP,#24
 
STUR X10,[SP,#16]
 
STUR X9,[SP,#8]
 
STUR X19,[SP,#0]
 
ADD X9,X0,X1
 
ADD X10,X2,X3
 
SUB X19,X9,X10
 
ADD X0,X19,XZR
 
LDUR X10,[SP,#16]
 
LDUR X9,[SP,#8]
 
LDUR X19,[SP,#0]
 
ADDI SP,SP,#24
 
BR LR
 
L
e
a
f
 
P
r
o
c
e
d
u
r
e
 
E
x
a
m
p
l
e
 
Save X10, X9, X19 on stack
 
X9 = g + h
 
X10 = i + j
 
f = X9 – X10
 
copy f to return register
 
Resore X10, X9, X19 from stack
 
Return to caller
 
18
18
undefined
 
R
e
g
i
s
t
e
r
 
U
s
a
g
e
 
X9 to X17:  temporary registers
Not preserved by the callee
 
X19 to X28:  saved registers
If used, the callee saves and restores them
 
Two stores and two loads can be dropped
from the code.
Still must save and restore X19
 
19
19
undefined
 
N
o
n
-
L
e
a
f
 
P
r
o
c
e
d
u
r
e
s
 
Procedures that call other procedures
For nested call, caller needs to save on the
stack:
Its return address
Any arguments and temporaries needed after
the call
Restore from the stack after the call
 
20
20
undefined
 
N
o
n
-
L
e
a
f
 
P
r
o
c
e
d
u
r
e
 
E
x
a
m
p
l
e
 
C code:
 
int fact (int n)
{
  if (n < 1) return f;
  else return n * fact(n - 1);
}
 
Argument n in X0
Result in X1
 
21
21
undefined
 
LEGv8 code:
 
fact:
 
SUBI SP,SP,#16
 
STUR LR,[SP,#8]
 
       
// save the return address
 
STUR X0,[SP,#0]
           
// save the argument n
 
SUBIS XZR,X0,#1
 
B.GE L1
 
ADDI X1,XZR,#1
 
ADDI SP,SP,#16
 
BR LR
L1: SUBI X0,X0,#1
 
BL fact
 
LDUR X0,[SP,#0]
 
LDUR LR,[SP,#8]
 
ADDI SP,SP,#16
 
MUL X1,X0,X1
 
BR LR
 
L
e
a
f
 
P
r
o
c
e
d
u
r
e
 
E
x
a
m
p
l
e
 
Save return address and n on stack
 
test for n < 1
 
Else, set return value to 1
 
n = n - 1
 
if n >= 1, go to L1
 
call fact(n-1)
 
Pop stack, don’t bother restoring values
 
Return
 
Restore caller’s n
 
Restore caller’s return address
 
Pop stack
 
return n * fact(n-1)
 
return
 
22
22

								

								

								

										

												
Slide Note

												
The University of Adelaide, School of Computer Science
Chapter 2 — Instructions: Language of the Computer

										

								


								
						

							
						


							

								

									
										
Embed
									
									
										
Share
									

									
									
									

								

								
							


							

							 
 							 
 							 
						  


							
							

								
This content discusses shift operations, AND operations, OR operations, EOR operations, and conditional operations in computer organization and design. It covers topics such as shifting logical operations, masking bits, including bits, differencing operations, and conditional branching instructions, providing a comprehensive overview of the hardware/software interface.


								
    
																		
  •   Computer Organization
    • 
																	
  •    Hardware
    • 
																	
  •    Software Interface
    • 
																	
  •    Shift Operations
    • 
																	
  •    Logical Operations
    • 
																

								

								

									

										auriol
										

											 auriol Follow
											

										

									

									
Uploaded on Aug 05, 2024 | 0 Views

								

								


								

									
Download Presentation

									
								

								
Please find below an Image/Link to download the presentation.

								
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.


									
									

									


										 
										 
										 
										 

									

									

									

								
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

								

									 
									
Download Presentation
								

								
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.


								

									
 E N D 

								


							
Presentation Transcript

							

							
  1. COMPUTER ORGANIZATIONAND DESIGN The Hardware/Software Interface Chapter 2 Chapter 2 Instructions: Language  of the Computer
    2. 
            
            
            
  2. Shift Operations opcode Rm shamt Rn Rd 11 bits 5 bits 6 bits 5 bits 5 bits     shamt: how many positions to shift      Shift left logical     Shift left and fill with 0 bits     LSL by i bits multiplies by 2i     Shift right logical     Shift right and fill with 0 bits     LSR by i bits divides by 2i (unsigned only) 2
    3. 
            
            
            
  3. AND Operations     Useful to mask bits in a word     Select some bits, clear others to 0  AND X9,X10,X11 X10 00000000 00000000 00000000 00000000 00000000 00000000 00001101 11000000 X11 00000000 00000000 00000000 00000000 00000000 00000000 00111100 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00001100 00000000 X9 3
    4. 
            
            
            
  4. OR Operations     Useful to include bits in a word     Set some bits to 1, leave others unchanged  OR X9,X10,X11 X10 00000000 00000000 00000000 00000000 00000000 00000000 00001101 11000000 X11 00000000 00000000 00000000 00000000 00000000 00000000 00111100 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00111101 11000000 X9 4
    5. 
            
            
            
  5. EOR Operations     Differencing operation     create a 0 when bits are the same and a 1 if  they are different      the equivalent to NOT is an EOR 111   111      EOR X9,X10,X12  // NOT operation 00000000 00000000 00000000 00000000 00000000 00000000 00001101  11000000 X10 X12 11111111    11111111  11111111   11111111   11111111   11111111   11111111   11111111 11111111    11111111  11111111   11111111   11111111   11111111   11110010  00111111 X9 5
    6. 
            
            
            
  6. Conditional Operations     Branch to a labeled instruction if a condition is  true     Otherwise, continue sequentially     CBZ register, L1     if (register == 0) branch to instruction labeled L1;     Compare and branch if zero     CBNZ register, L1     if (register != 0) branch to instruction labeled L1;     Compare and branch if not zero     B L1     branch unconditionally to instruction labeled L1; 6
    7. 
            
            
            
  7. Compiling If Statements     C code:  if (i==j) f = g+h; else f = g-h;     f, g,     in X22, X23,         Compiled LEGv8 code:  SUB X9,X22,X23 // X9 = i     j  CBNZ X9,Else // go to Else if i     j (X9     0)  ADD X19,X20,X21 // f = g + h (skipped if i     j)  B Exit // go to Exit Else: SUB X9,X22,x23 // f = g    h  Exit:     Assembler calculates addresses 7
    8. 
            
            
            
  8. Compiling Loop Statements     C code:  while (save[i] == k) i += 1;     i in x22, k in x24, address of save in x25     Compiled LEGv8 code: Loop: LSL  X10,X22,#3 // Temp reg X10 = i * 8       ADD    X10,X10,X25 // X10 = address of save[i]       LDUR   X9,[X10,#0] // Temp reg X9 = save[i]        SUB    X11,X9,X24 // X11 = save[i]     k       CBNZ   X11,Exit // go to Exit if save[i]     k(X11     0)         ADDI   X22,X22,#1 // i = i + 1       B      Loop // go to Loop Exit:     8
    9. 
            
            
            
  9. Basic Blocks     A basic block is a sequence of instructions  with     No embedded branches (except at end)     No branch targets (except at beginning)     A compiler identifies basic  blocks for optimization     An advanced processor  can accelerate execution  of basic blocks 9
    10. 
            
            
            
  10. More Conditional Operations     Condition codes, set from arithmetic instruction with S- suffix (ADDS, ADDIS, ANDS, ANDIS, SUBS, SUBIS)     negative (N):  result had 1 in MSB     zero (Z):  result was 0     overlow (V):  result overflowed     carry (C):  result had carryout from MSB     Use subtract (A-B) to set flags, then conditionally branch: 10
    11. 
            
            
            
  11. Conditional branches     LEGv8 includes four branches to complete the testing of  the individual condition code bits:     Branch on minus (B.MI): N=1;     Branch on plus (B.PL): N=0;     Branch on overflow set (B.VS): V=1;     Branch on overflow clear (B.VC): V=0.     An alternative to condition codes:      have instructions that compare two registers and then branch  based on the result.      compare two registers and set a third register to a result  indicating the success of the comparison, which a subsequent  conditional branch instruction then tests to see if register is non- zero (condition is true) or zero (condition is false).      Conditional branches in MIPS follow the latter approach 11
    12. 
            
            
            
  12. Conditional Example     if (a > b) a += 1;     a in X22, b in X23   SUBS X9,X22,X23  // use subtract to make comparison   B.LTE Exit               // conditional branch   ADDI X22,X22,#1 Exit: 12
    13. 
            
            
            
  13. Signed vs. Unsigned     Signed comparison     Unsigned comparison     Example     X22 = 1111 1111 1111 1111 1111 1111 1111 1111     X23 = 0000 0000 0000 0000 0000 0000 0000 0001     X22 < X23 # signed        1 < +1     X22 > X23 # unsigned     +4,294,967,295 > +1 13
    14. 
            
            
            
  14. 2.8 Supporting Procedures in Computer Hardware Procedure Calling Steps required 1. Place parameters in registers X0 to X7 2. Transfer control to procedure 3. Acquire storage for procedure 4. Perform procedure   s operations 5. Place result in register for caller 6. Return to place of call (address in X30)     14
    15. 
            
            
            
  15. Procedure Call Instructions     Procedure call: branch-and-link instruction  BL ProcedureLabel     Address of following instruction put in LR (X30)     Jumps to target address     Procedure return: branch register instruction  BR LR     Copies LR (X30) to program counter     Can also be used for computed jumps     e.g., for case/switch statements     Program Counter (PC): register containing the  address of the current instruction      BL saves PC+4 in register LR  15
    16. 
            
            
            
  16. Leaf Procedure Example     C code:  long long int leaf_example (long long int  g, long long int h, long long int i, long  long int j) { long long int f;   f = (g + h) - (i + j);   return f; }     Arguments g,    , j in X0,    , X3     f in X19 (hence, need to save $s0 on stack) 16
    17. 
            
            
            
  17. Local Data on the Stack 17
    18. 
            
            
            
  18. Leaf Procedure Example     LEGv8 code:  leaf_example:  SUBI SP,SP,#24  STUR X10,[SP,#16]  STUR X9,[SP,#8]  STUR X19,[SP,#0]  ADD X9,X0,X1  ADD X10,X2,X3  SUB X19,X9,X10  ADD X0,X19,XZR  LDUR X10,[SP,#16]  LDUR X9,[SP,#8]  LDUR X19,[SP,#0]  ADDI SP,SP,#24  BR LR Save X10, X9, X19 on stack X9 = g + h X10 = i + j f = X9     X10 copy f to return register Resore X10, X9, X19 from stack Return to caller 18
    19. 
            
            
            
  19. Register Usage     X9 to X17:  temporary registers     Not preserved by the callee     X19 to X28:  saved registers     If used, the callee saves and restores them     Two stores and two loads can be dropped  from the code.      Still must save and restore X19 19
    20. 
            
            
            
  20. Non-Leaf Procedures     Procedures that call other procedures     For nested call, caller needs to save on the  stack:     Its return address     Any arguments and temporaries needed after  the call     Restore from the stack after the call 20
    21. 
            
            
            
  21. Non-Leaf Procedure Example     C code:  int fact (int n) {    if (n < 1) return f;   else return n * fact(n - 1); }     Argument n in X0     Result in X1 21
    22. 
            
            
            
  22. Leaf Procedure Example     LEGv8 code: fact: SUBI SP,SP,#16 STUR LR,[SP,#8]  STUR X0,[SP,#0]           // save the argument n SUBIS XZR,X0,#1 B.GE L1 ADDI X1,XZR,#1 ADDI SP,SP,#16 BR LR L1: SUBI X0,X0,#1 BL fact LDUR X0,[SP,#0] LDUR LR,[SP,#8] ADDI SP,SP,#16 MUL X1,X0,X1 BR LR Save return address and n on stack // save the return address test for n < 1 if n >= 1, go to L1 Else, set return value to 1 Pop stack, don   t bother restoring values Return n = n - 1 call fact(n-1) Restore caller   s n Restore caller   s return address Pop stack return n * fact(n-1) return 22
    23. 
            
            
            
						

						

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              Computer Organization and Architecture
            

            

              
Computer Organization and Architecture

              
alexei

            

          

        
      


     

      

        
          

            

              The World of Computer Graphics in CSE452
            

            

              
The World of Computer Graphics in CSE452

              
kian

            

          

        
      


     

      

        
          

            

              Overview of Computer Hardware Components and Software Functions
            

            

              
Overview of Computer Hardware Components and Software Functions

              
ainhoa

            

          

        
      


     

      

        
          

            

              Computer Systems: Components and Organization
            

            

              
Computer Systems: Components and Organization

              
mungo

            

          

        
      


     

      

        
          

            

              Basic Computer Organization and Design - Timing and Control
            

            

              
Basic Computer Organization and Design - Timing and Control

              
emilie

            

          

        
      


     

      

        
          

            

              Computer Architecture and Organization
            

            

              
Computer Architecture and Organization

              
jovanni

            

          

        
      


     

      

        
          

            

              Computer System and Organization
            

            

              
Computer System and Organization

              
katniss

            

          

        
      


     

      

        
          

            

              Application of Computer in Economics Course: DE-403(ii) with Dr. Sanatan Nayak
            

            

              
Application of Computer in Economics Course: DE-403(ii) with Dr. Sanatan Nayak

              
brooklyn

            

          

        
      


     

      

        
          

            

              Computer Science Department Information and Courses Offered
            

            

              
Computer Science Department Information and Courses Offered

              
suki

            

          

        
      


     

      

        
          

            

              Computer Systems and Components
            

            

              
Computer Systems and Components

              
otto

            

          

        
      


     

      

        
          

            

              Anatomy of a Computer System: Hardware Components and Functions
            

            

              
Anatomy of a Computer System: Hardware Components and Functions

              
alaiya

            

          

        
      


     

      

        
          

            

              Computer Processing Systems
            

            

              
Computer Processing Systems

              
klay

            

          

        
      


     

      

        
          

            

              Software Engineering Design Principles and Concepts
            

            

              
Software Engineering Design Principles and Concepts

              
hanna

            

          

        
      


     

      

        
          

            

              Evolution of Algorithms and Computer Science Through History
            

            

              
Evolution of Algorithms and Computer Science Through History

              
irvin

            

          

        
      


     

      

        
          

            

              Trends in Computer Organization and Architecture
            

            

              
Trends in Computer Organization and Architecture

              
dina

            

          

        
      


     

      

        
          

            

              Computer Organization and Hardware Components
            

            

              
Computer Organization and Hardware Components

              
kase

            

          

        
      


     

      

        
          

            

              Overview of Computer Input and Output Devices
            

            

              
Overview of Computer Input and Output Devices

              
brennan

            

          

        
      


     

      

        
          

            

              Computer Graphics: An Overview
            

            

              
Computer Graphics: An Overview

              
blas_r

            

          

        
      


     

      

        
          

            

              Computer Crimes and Prevention Strategies
            

            

              
Computer Crimes and Prevention Strategies

              
annaluc

            

          

        
      


     

      

        
          

            

              Comprehensive Guide to System Design Components and Techniques
            

            

              
Comprehensive Guide to System Design Components and Techniques

              
khlo845

            

          

        
      


     

      

        
          

            

              Computer Organization: Instruction Set Architecture and Interrupts
            

            

              
Computer Organization: Instruction Set Architecture and Interrupts

              
hilliker_b

            

          

        
      


     

      

        
          

            

              Software Architectural Design in Computer-Based Systems
            

            

              
Software Architectural Design in Computer-Based Systems

              
zenner_d

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#