Transcript Shift Instructions - CS Course Webpages

Computer Architecture
CSCE 350
Rabi Mahapatra
Spring 2015
Overview
• Logical Instructions
• Shifts
Bitwise Operations
• Up until now, we’ve done arithmetic (add, sub,addi ),
memory access (lw and sw), and branches and jumps.
• All of these instructions view contents of register as a
single quantity (such as a signed or unsigned integer)
° New Perspective: View contents of register as 32 bits
rather than as a single 32-bit number
• Since registers are composed of 32 bits, we may want
to access individual bits (or groups of bits) rather than
the whole.
• Introduce two new classes of instructions:
• Logical Operators
• Shift Instructions
Logical Operators
• Two basic logical operators:
• AND: outputs 1 only if both inputs are 1
• OR: outputs 1 if at least one input is 1
Logical Operators
• Two basic logical operators:
– AND: outputs 1 only if both inputs are 1
– OR: outputs 1 if at least one input is 1
• Truth Table: standard table listing all possible combinations
of inputs and resultant output for each
• Truth Table for AND and OR
A
B
0
0
0
1
1
0
1
1
AND
OR
Logical Operators
• Instruction Names:
• and, or: Both of these expect the third
argument to be a register
• andi, ori: Both of these expect the third
argument to be an immediate
• MIPS Logical Operators are all bitwise, meaning
that bit 0 of the output is produced by the
respective bit 0’s of the inputs, bit 1 by the bit 1’s,
etc.
Uses for Logical Operators
• Note that ANDing a bit with 0 produces a 0 at the output while
ANDing a bit with 1 produces the original bit.
• This can be used to create a mask.
• Example:
1011 0110 1010 0100 0011 1101 1001 1010
0000 0000 0000 0000 0000 1111 1111 1111
• The result of ANDing these two is:
0000 0000 0000 0000 0000 1101 1001 1010
• The second bit string in the example is called a mask. It is used to
isolate the rightmost 12 bits of the first bit string by masking out
the rest of the string (e.g. setting it to all 0s).
Uses for Logical Operators
• Thus, the and operator can be used to set certain portions of a bit
string to 0s, while leaving the rest alone.
• In particular, if the first bitstring in the above example were in
$t0, then the following instruction would mask it:
andi
$t0,$t0,0xFFF
• Similarly, note that ORing a bit with 1 produces a 1 at the output
while ORing a bit with 0 produces the original bit.
• This can be used to force certain bits of a string to 1s.
• For example, if $t0 contains 0x12345678, then after this
instruction:
ori $t0, $t0, 0xFFFF
• $t0 contains 0x1234FFFF (e.g. the high-order 16 bits are
untouched, while the low-order 16 bits are forced to 1s).
Shift Instructions (1/3)
• Move (shift) all the bits in a word to the left or right
by a number of bits.
• Example: shift right by 8 bits
0001 0010 0011 0100 0101 0110 0111 1000
0000 0000 0001 0010 0011 0100 0101 0110
 Example: shift left by 8 bits
0001 0010 0011 0100 0101 0110 0111 1000
0011 0100 0101 0110 0111 1000 0000 0000
Shift Instructions (2/3)
• Shift Instruction Syntax:
1 2,3,4
• where
1) operation name
2) register that will
receive value
3) first operand
(register)
4) shift amount (constant
<= 32)
MIPS shift instructions:
1. sll (shift left logical):
shifts left and fills emptied
bits with 0s
2. srl (shift right logical):
shifts right and fills
emptied bits with 0s
3. sra (shift right
arithmetic): shifts right
and fills emptied bits by
sign extending
Shift Instructions (3/3)
• Example: shift right arith (sra) by 8 bits
0001 0010 0011 0100 0101 0110 0111 1000
0000 0000 0001 0010 0011 0100 0101 0110
 Example: shift right arith (sra) by 8 bits
1001 0010 0011 0100 0101 0110 0111 1000
1111 1111 1001 0010 0011 0100 0101 0110
Uses for Shift Instructions (1/4)
• Suppose we want to isolate byte 0
(rightmost 8 bits) of a word in $t0. Simply
use:
andi
$t0,$t0,0xFF
• Suppose we want to isolate byte 1 (bit 15
to bit 8) of a word in $t0. We can use:
andi
$t0,$t0,0xFF00
but then we still need to shift to the right
by 8 bits...
Uses for Shift Instructions (2/4)
• Could use instead:
sll $t0,$t0,16
srl $t0,$t0,24
t0
0001 0010 0011 0100 0101 0110 0111 1000
After sll
0101 0110 0111 1000 0000 0000 0000 0000
After srl
0000 0000 0000 0000 0000 0000 0101 0110
Uses for Shift Instructions (3/4)
• In binary:
Multiplying by 2 is same as shifting left by 1:
112 x 102 = 1102
10102 x 102 = 101002
Multiplying by 4 is same as shifting left by 2:
112 x 1002 = 11002
10102 x 1002 = 1010002
Multiplying by 2n is same as shifting left by n
Uses for Shift Instructions (4/4)
• Since shifting maybe faster than multiplication, a
good compiler usually notices when C code
multiplies by a power of 2 and compiles it to a
shift instruction:
a *= 8; (in C)
would compile to:
sll
$s0,$s0,3 (in MIPS)
• Likewise, shift right to divide by powers of 2
• remember to use sra
The Story so far…
• We introduced numerous MIPS assembly
language instructions.
• We are now familiar with registers and
register usage conventions.
• We know how to use system calls, basic I/O
• We have learned how the stack works
• What is missing?
Practice! Practice! Practice!
What Next?
• We need a more detailed knowledge about
the instruction formats to fully appreciate
certain restrictions.
• The functional interface is easy to
understand, since it is basically familiar
procedural programming
• We need to understand how the computer
interprets the instruction, so that we can
transition to the discussion of the MIPS
hardware architecture
Machine Language
What does
that mean?
• Machine language level programming means
that we have to provide the bit encodings for
the instructions
• For example, add $t0, $s1, $s2 represents
the 32bit string
• 00000010001100100100000000100000
• Assembly language mnemonics usually
translate into one instruction
• We also have pseudo-instructions that
translate into several instructions
Instruction Word Formats
• Register format
op-code
rs
6
rt
5
rd
5
shamt
5
funct
5
6
• Immediate format
op-code
rs
6
rt
5
immediate value
5
16
• Jump format
op-code
6
26 bit current segment address
26
Register Format (R-Format)
• Register format
op-code
6
•
•
•
•
•
•
rs
rt
5
rd
5
shamt
5
5
op: basic operation of instruction
funct: variant of instruction
rs: first register source operand
rt: second register source operand
rd: register destination operand
shamt: shift amount
funct
6
Watson, the case is clear…
• add $t0, $s1, $s2
• 00000010001100100100000000100000
op-code
6
rs
rt
5
rd
5
shamt
5
5
funct
6
• 000000 10001 10010 01000 00000 100000
• Operation and function field tell the computer to
perform an addition
• 000000 10001 10010 01000 00000 100000
• registers $17, $18 and $8
Registers
Number
Value
Name
0
$zero
1
$at
2
$v0
3
$v1
4
$a0
5
$a1
6
$a2
7
$a3
8
$t0
9
$t1
10
$t2
11
$t3
12
$t4
13
$t5
14
$t6
15
$t7
16
$s0
17
$s1
18
$s2
19
$s3
20
$s4
21
$s5
22
$s6
23
$s7
24
$t8
return values
from functions
pass parameters
to functions
$t0-$t7 are caller saved
registers –
use these registers
in functions
$s0-$s7 are callee-saved
registers – use these
registers for values
that must be maintained
across function calls.
Watson, the case is clear…
• add $t0, $s1, $s2
• 00000010001100100100000000100000
op-code
6
rs
rt
5
rd
5
shamt
5
5
funct
6
• 000000 10001 10010 01000 00000 100000
• source registers $s1=$17 and $s2=$18 and target
register $t0=$8
R-Format Example
• Register format
•
•
•
•
•
0
17
18
8
6
5
5
5
0
5
(op, funct)=(0,32): add
rs=17: first source operand is $s1
rt=18: second source operand is $s2
Rd=8: register destination is $t0
add $t0, $s1, $s2
32
6
Immediate Format (I-Format)
Immediate format
•
•
•
•
op
rs
6
5
rt
immediate value
5
16
op determines the instruction (op <> 0)
rs is the source register
rt is the destination register
16bit immediate value
I-Format Example
Immediate format
•
•
•
•
•
8
29
29
4
6
5
5
16
op=8 means addi
rs=29 means source register is $sp
rt=29 means $sp is destination register
immediate value = 4
addi $sp, $sp, 4
Problem
• The MIPS assembly language has the
command andi, an immediate bit-wise and
operation
• We can say li $s0, 0xCDEF1234 to load
register $s0 with the content 0xCDEF1234
• Why is this strange?
• In the immediate format, you can only load 16
bits, but the constant is 32 bits!
Pseudo-Instructions
• li $s0, 0xCDEF1234 is a pseudo-instruction
• It is a convenient shorthand for
lui $at, 0xCDEF
ori $s0, $at, 0x1234
• The register $at is used here by the
assembler; this is the reason why you should
not use this register.
Puzzle
• How can we swap the content of two
registers, say $s0 and $s1, without
accessing other registers or memory?
• Solution:
xor $s0, $s0, $s1
xor $s1, $s0, $s1
xor $s0, $s0, $s1
MIPS Addressing Modes
•
•
•
•
Immediate addressing
Register addressing
Base displacement addressing
PC-relative addressing
• address is the sum of the PC and a constant in the
instruction
• Pseudo-direct addressing
• jump address is 26bits of instruction
concatenated with upper bits of PC
1. Immediate addressing
op
rs
rt
Immediate
2. Register addressing
op
rs
rt
rd
...
funct
Registers
Register
3. Base addressing
op
rs
rt
Memory
Address
+
Register
Byte
Halfword
4. PC-relative addressing
op
rs
rt
Memory
Address
PC
+
Word
5. Pseudodirect addressing
op
Address
PC
Memory
Word
Word
Addressing Modes
• Register Addressing
• add $s1, $s2, $s3
• $s1 = $s2 + $s3
• Immediate Addressing
• addi $s1, $s2, 100
• $s1 = $s2 + 100
Addressing Modes
• Base addressing
• lw $s1, 100($s2)
• $s1 = Memory[$s2+100]
• PC-relative branch
• beq $s1, $s2, 25
• if ($s1 == $s2) goto PC + 4 + 100
Addressing Modes
• Pseudo-direct addressing
• j 1000
• goto 1000
• concatenate 26bit address with upper bits
of the PC