CS

 61C:    
Great  Ideas  in  Computer  Architecture    
Intro  to  Assembly  Language,  MIPS  Intro  
Instructors:  
Krste  Asanovic  &  Vladimir  Stojanovic  
h>p://inst.eecs.Berkeley.edu/~cs61c/sp15  

1  
 Levels  of  RepresentaIon/
InterpretaIon  
High  Level  Language   temp  =  v[k];  
v[k]  =  v[k+1];  
Program  (e.g.,  C)   v[k+1]  =  temp;  
Compiler  
lw      $t0,  0($2)   Anything  can  be  represented  
Assembly    Language   lw      $t1,  4($2)   as  a  number,    
Program  (e.g.,  MIPS)   sw      $t1,  0($2)  
sw      $t0,  4($2)   i.e.,  data  or  instrucIons  
Assembler  
0000 1001 1100 0110 1010 1111 0101 1000
Machine    Language   1010 1111 0101 1000 0000 1001 1100 0110
Program  (MIPS)   1100 0110 1010 1111 0101 1000 0000 1001
0101 1000 0000 1001 1100 0110 1010 1111 !
Machine  
Interpreta4on  
Hardware  Architecture  DescripCon  
(e.g.,  block  diagrams)    
Architecture  
Implementa4on  

Logic  Circuit  DescripCon  

(Circuit  SchemaCc  Diagrams)   2  
 Assembly  Language  
•  Basic  job  of  a  CPU:  execute  lots  of  instruc8ons.  
•  InstrucIons  are  the  primiIve  operaIons  that  the  
CPU  may  execute.  
•  Different  CPUs  implement  different  sets  of  
instrucIons.    The  set  of  instrucIons  a  parIcular  
CPU  implements  is  an    
Instruc8on  Set  Architecture  (ISA).  
– Examples:  ARM,  Intel  x86,  MIPS,  RISC-­‐V,  IBM/
Motorola  PowerPC  (old  Mac),  Intel  IA64,  ...  
3  
 InstrucIon  Set  Architectures  
•  Early  trend  was  to  add  more  and  more  instrucIons  
to  new  CPUs  to  do  elaborate  operaIons  
– VAX  architecture  had  an  instrucIon  to  mulIply  
polynomials!  

•  RISC  philosophy  (Cocke  IBM,  Pa>erson,  Hennessy,  

1980s)  –    
Reduced  InstrucIon  Set  CompuIng  
– Keep  the  instrucIon  set  small  and  simple,  makes  it  
easier  to  build  fast  hardware.  
– Let  sodware  do  complicated  operaIons  by  composing  
simpler  ones.  
4  
 MIPS  Architecture  
•  MIPS  –  semiconductor  company  that  built  one  of  
the  first  commercial  RISC  architectures  
•  We  will  study  the  MIPS  architecture  in  some  detail  
in  this  class  (also  used  in  upper  division  courses  CS  
152,  162,  164)  
•  Why  MIPS  instead  of  Intel  x86?  
– MIPS  is  simple,  elegant.    Don’t  want  to  get  bogged  
down  in  gri>y  details.  
– MIPS  widely  used  in  embedded  apps,  x86  li>le  used  in  
embedded,  and  more  embedded  computers  than  PCs  
5  
 Assembly  Variables:  Registers  
•  Unlike  HLL  like  C  or  Java,  assembly  cannot  use  
variables  
– Why  not?  Keep  Hardware  Simple  
•  Assembly  Operands  are  registers  
– Limited  number  of  special  locaIons  built  directly  
into  the  hardware  
– OperaIons  can  only  be  performed  on  these!  
•  Benefit:  Since  registers  are  directly  in  
hardware,  they  are  very  fast    
(faster  than  1  ns  -­‐  light  travels  30cm  in  1  ns!!!    )  

6  
 Number  of  MIPS  Registers  
•  Drawback:  Since  registers  are  in  hardware,  
there  are  a  predetermined  number  of  them  
– SoluIon:  MIPS  code  must  be  very  carefully  put  
together  to  efficiently  use  registers  
•  32  registers  in  MIPS  
– Why  32?  Smaller  is  faster,  but  too  small  is  bad.  
Goldilocks  problem.  
•  Each  MIPS  register  is  32  bits  wide  
– Groups  of  32  bits  called  a  word  in  MIPS  

7  
 Names  of  MIPS  Registers  
•  Registers  are  numbered  from  0  to  31  
•  Each  register  can  be  referred  to  by  number  or  name  
•  Number  references:  
–$0,  $1,  $2,  …  $30,  $31  
• For  now:  
–  $16  -­‐  $23è  $s0  -­‐  $s7    (correspond  to  C  variables)  
–  $8  -­‐  $15  è  $t0  -­‐  $t7  (correspond  to  temporary  variables)  
–  Later  will  explain  other  16  register  names  
•  In  general,  use  names  to  make  your  code  more  
readable  

8  
 C,  Java  variables  vs.  registers  
•  In  C  (and  most  High  Level  Languages)  variables  
declared  first  and  given  a  type  
• Example:      int fahr, celsius;
! ! !char a, b, c, d, e;!
•  Each  variable  can  ONLY  represent  a  value  of  
the  type  it  was  declared  as    
(cannot  mix  and  match  int  and  char  variables).  
•  In  Assembly  Language,  registers  have  no  type;  
operaIon  determines  how  register  contents  are  
treated  
9  
 AddiIon  and  SubtracIon  of  Integers  
•  AddiIon  in  Assembly  
– Example:      add !$s0,$s1,$s2 (in  MIPS)  
– Equivalent  to:        a  =  b  +  c          (in  C)  
       where    C  variables  ⇔  MIPS  registers  are:  
     a  ⇔  $s0,  b  ⇔  $s1,  c  ⇔  $s2    
•  SubtracIon  in  Assembly  
– Example:      sub !$s3,$s4,$s5 (in  MIPS)  
– Equivalent  to:        d  =  e  -­‐  f          (in  C)  
       where    C  variables  ⇔  MIPS  registers  are:  
                         d  ⇔  $s3,  e  ⇔  $s4,  f  ⇔  $s5    

10  
 AddiIon  and  SubtracIon  of  Integers  
Example  1  
•  How  to  do  the  following  C  statement?  
 a  =  b  +  c  +  d  -­‐  e;  
•  Break  into  mulIple  instrucIons  
add $t0, $s1, $s2 # temp = b + c!
add $t0, $t0, $s3 # temp = temp + d!
sub $s0, $t0, $s4 # a = temp - e!
   
•  A  single  line  of  C  may  break  up  into  several  lines  of  
MIPS.  
•  NoIce  the  use  of  temporary  registers  –  don’t  want  to  
modify  the  variable  registers  $s!
•  Everything  ader  the  hash  mark  on  each  line  is  ignored  
(comments)  
11  
 Immediates  
•  Immediates  are  numerical  constants.  
•  They  appear  oden  in  code,  so  there  are  special  
instrucIons  for  them.  
•  Add  Immediate:  
   addi $s0,$s1,-10    (in  MIPS)  
           f  =  g  -­‐  10        (in  C)  
where  MIPS  registers  $s0,$s1  are  associated  with  
C  variables  f,  g    
•  Syntax  similar  to  add  instrucIon,  except  that  
last  argument  is  a  number  instead  of  a  register.  
add $s0,$s1,$zero  (in  MIPS)  
         f  =  g                    (in  C)   12  
 Overflow in Arithmetic
• Reminder: Overflow occurs when there
is a “mistake” in arithmetic due to the
limited precision in computers.
• Example (4-bit unsigned numbers):
! ! ! 15 ! ! 1111
! ! !+ 3 ! ! + 0011
! ! ! 18 ! ! 10010
• But we don’t have room for 5-bit
solution, so the solution would be 0010,
which is +2, and “wrong”.
13  
 Overflow handling in MIPS
•  Some  languages  detect  overflow  (Ada),    
some  don’t  (most  C  implementaIons)  
•  MIPS  soluIon  is  2  kinds  of  arithmeIc  instrucIons:  
–  These  cause  overflow  to  be  detected  
•  add  (add)  
•  add  immediate  (addi)    
•  subtract  (sub)  
–  These  do  not  cause  overflow  detecIon    
•  add  unsigned  (addu)  
•  add  immediate  unsigned  (addiu)    
•  subtract  unsigned  (subu)  
•  Compiler  selects  appropriate  arithmeIc  
–  MIPS  C  compilers  produce  addu,  addiu,  subu  

14  
 Data  Transfer:  
Load  from  and  Store  to  memory  
Memory  
Processor   Input  
Enable?  
Read/Write  
Control  

Program  
Datapath  
Address  
PC   Bytes  
Write  Data    =  
  Store  to  
Registers  
  memory  
ArithmeIc  &  Logic  Unit   Read  Data  =   Data  
Output  
(ALU)   Load  from  
memory  

Processor-­‐Memory  Interface   I/O-­‐Memory  Interfaces  

15  
 Memory  Addresses  are  in  Bytes  
• Lots  of  data  is  smaller  than  32  bits,  but  rarely  
smaller  than  8  bits  –  works  fine  if  everything  is  a  
mulIple  of  8  bits   Addr  of  lowest  byte  in  
word  is  addr  of  word  
• 8  bit  chunk  is  called  a  byte  
 (1  word  =  4  bytes)   …   …  …  …   …  
• Memory  addresses  are  really   12   13  3  14   15  
in  bytes,  not  words   8   9   2  10   11  
• Word  addresses  are  4  bytes     4   5   1   6   7  
apart     0   1   0   2   3  
– Word  address  is  same  as  address  of  ledmost  byte  
(i.e.  Big-­‐endian)     16  
 Transfer  from  Memory  to  Register  
• C  code  
int A[100];
   g = h + A[3];

• Using  Load  Word  (lw)  in  MIPS:  

lw $t0,12($s3) #  Temp  reg  $t0  gets  A[3]  
add $s1,$s2,$t0 #  g  =  h  +  A[3]  

Note:      $s3  –  base  register  (pointer)  

       12  –  offset  in  bytes  
Offset  must  be  a  constant  known  at  assembly  Ime  

17  
 Transfer  from  Register  to  Memory  
• C  code  
int A[100];
   A[10] = h + A[3];

• Using  Store  Word  (sw)  in  MIPS:  

lw $t0,12($s3) #  Temp  reg  $t0  gets  A[3]  
add $t0,$s2,$t0 #  Temp  reg  $t0  gets  h  +  A[3]  
 sw! $t0, 40($s3) #  A[10]  =  h  +  A[3]  

Note:      $s3  –  base  register  (pointer)  

       12,40  –  offsets  in  bytes  
 
$s3+12  and  $s3+40  must  be  mulIples  of  4  
18  
 Loading and Storing bytes
•  In  addiIon  to  word  data  transfers    
(lw,  sw),  MIPS  has  byte  data  transfers:  
–  load  byte:  lb!
–  store  byte:  sb!
•  Same  format  as  lw,  sw!
•  E.g.,    lb $s0, 3($s1)!
– contents  of  memory  locaIon  with  address  =  sum  
of  “3”  +  contents  of  register  $s1  is  copied  to  the  low  
byte  posiIon  of  register  $s0.  
$s0:   xxxx xxxx xxxx xxxx xxxx xxxx! x!zzz zzzz!
byte
…is copied to “sign-extend” loaded
This bit 19  
 Speed  of  Registers  vs.  Memory  
• Given  that    
– Registers:  32  words  (128  Bytes)  
– Memory:  Billions  of  bytes  (2  GB  to  8  GB  on  laptop)  
• and  the  RISC  principle  is…  
– Smaller  is  faster  
• How  much  faster  are  registers  than  memory??  
• About  100-­‐500  Imes  faster!  
– in  terms  of  latency  of  one  access  

20  
How  many  hours  h  on  Homework  0?  

A:  0  ≤  h  <  5  
B:  5  ≤  h  <  10  
C:  10  ≤  h  <  15  
D:  15  ≤  h  <  20  
E:  20  ≤  h  

21  
 Clickers/Peer Instruction
We want to translate *x = *y +1 into MIPS
(x, y pointers stored in: $s0 $s1)

A: !addi $s0,$s1,1!
!
B: !lw $s0,1($s1)!
! !sw $s1,0($s0)!
!
C: !lw $t0,0($s1)!
! !addi $t0,$t0,1!
! !sw $t0,0($s0)!
!
!
D: !sw $t0,0($s1)!
! addi $t0,$t0, 1!
! !lw $t0,0($s0)!
!
E: !lw $s0,1($t0)!
!sw $s1,0($t0)!
22  
 MIPS  Logical  InstrucIons  
•  Useful  to  operate  on  fields  of  bits  within  a  word    
−  e.g.,  characters  within  a  word  (8  bits)  
•  OperaIons  to  pack  /unpack  bits  into  words  
•  Called  logical  opera8ons  
Logical C Java MIPS
operations operators operators instructions
Bit-by-bit AND & & and
Bit-by-bit OR | | or
Bit-by-bit NOT ~ ~ not
Shift left << << sll
Shift right >> >>> srl
23  
 Logic Shifting
•  Shid  Led:  sll $s1,$s2,2  #s1=s2<<2  
–  Store  in  $s1  the  value  from  $s2  shided  2  bits  to  the  
led  (they  fall  off  end),  inserIng  0’s  on  right;  <<  in  C.  
Before:    0000  0002hex  
0000  0000  0000  0000  0000  0000  0000  0010two  
   Ader:        0000  0008hex  
   0000  0000  0000  0000  0000  0000  0000  1000two  
What  arithmeIc  effect  does  shid  led  have?  
 
•  Shid  Right:  srl  is  opposite  shid;  >>  

24  
 ArithmeIc  Shiding  
• Shid  right  arithmeIc  moves  n  bits  to  the  right  
(insert  high  order  sign  bit  into  empty  bits)  
• For  example,  if  register  $s0  contained  
1111  1111  1111  1111  1111  1111  1110  0111two=  -­‐25ten  
• If  executed  sra  $s0,  $s0,  4,  result  is:  
 1111  1111  1111  1111  1111  1111  1111  1110two=  -­‐2ten  
• Unfortunately,  this  is  NOT  same  as  dividing  by  2n  
− Fails  for  odd  negaIve  numbers  
− C  arithmeIc  semanIcs  is  that  division  should  round  towards  0  
  25  
 Computer  Decision  Making  
• Based  on  computaIon,  do  something  different  
• In  programming  languages:  if-­‐statement  

• MIPS:  if-­‐statement  instrucIon  is  

     beq register1,register2,L1
 means:  go  to  statement  labeled  L1    
if  (value  in  register1)  ==  (value  in  register2)  
 ….otherwise,  go  to  next  statement  
• beq  stands  for  branch  if  equal  
• Other  instrucIon:  bne  for  branch  if  not  equal  
26  
 Types  of  Branches  
• Branch  –  change  of  control  flow  

• CondiConal  Branch  –  change  control  flow  

depending  on  outcome  of  comparison  
– branch  if  equal  (beq)  or  branch  if  not  equal  (bne)  

• UncondiConal  Branch  –  always  branch  

– a  MIPS  instrucIon  for  this:  jump  (j)  
  27  
 Example  if  Statement  
• Assuming  translaIons  below,  compile  if  block  
 f  →  $s0    g  →  $s1      h  →  $s2  
 i  →  $s3  j  →  $s4

if (i == j) bne $s3,$s4,Exit
f = g + h; add $s0,$s1,$s2
Exit:
• May  need  to  negate  branch  condiIon  
28  
 Example  if-­‐else  Statement  
• Assuming  translaIons  below,  compile  
 f  →  $s0    g  →  $s1      h  →  $s2  
 i  →  $s3  j  →  $s4
if (i == j) bne $s3,$s4,Else
f = g + h; add $s0,$s1,$s2
else j Exit
f = g – h; Else: sub $s0,$s1,$s2
Exit:
29  
 Administrivia  

• Hopefully  everyone  turned-­‐in  HW0  

• HW1  due  11:59:59pm  Sunday  2/8  

30  
 In  the  News  
MIPS  steers  spacecrad  to  Pluto  
• 4  MIPS  R3000  32bit  CPUs  
– Command  and  Data  
handling  
– Guidance  and  Control  

• Launched  2006,  first  pics  

in  July  2015  

http://www.electronicsweekly.com/news/military-aerospace-
electronics/mips-steers-spacecraft-pluto-2015-01/!
31  
!
 Inequalities in MIPS
•  UnIl  now,  we’ve  only  tested  equaliIes    
(==  and  !=  in  C).    General  programs  need  to  test  <  and  >  
as  well.  
•  Introduce  MIPS  Inequality  InstrucIon:  
 “Set  on  Less  Than”  
 Syntax:                  slt reg1,reg2,reg3!
 Meaning:    if  (reg2  <  reg3)    
           reg1  =  1;    
         else  reg1  =  0;    
 “set”  means  “change  to  1”,    
 “reset”  means  “change  to  0”.   32  
 Inequalities in MIPS Cont.
•  How  do  we  use  this?  Compile  by  hand:  
 if  (g  <  h)  goto  Less;  #g:$s0,  h:$s1  

•  Answer:  compiled  MIPS  code…  

 slt $t0,$s0,$s1  #  $t0  =  1  if  g<h    
 bne $t0,$zero,Less    #  if  $t0!=0  goto  Less  
 
•  Register  $zero  always  contains  the  value  0,  so  bne  and  beq  
oden  use  it  for  comparison  ader  an  slt  instrucIon  

•  sltu  treats  registers  as  unsigned  

33  
 Immediates in Inequalities
• slti an immediate version of slt to
test against constants
Loop: !. . .

slti $t0,$s0,1 # $t0 = 1 if

# $s0<1
beq $t0,$zero,Loop # goto Loop
!# if $t0==0
! ! ! ! ! ! ! !# (if ($s0>=1))

34  
 Loops in C/Assembly
•  Simple  loop  in  C;            A[]  is  an  array  of  ints  
   do  {  g  =  g  +  A[i];  
                 i  =  i  +  j;  
   }  while  (i  !=  h);  
•  Use  this  mapping:    g,      h,      i,      j,  &A[0]  
                     $s1,  $s2,  $s3,  $s4,  $s5  

Loop: sll $t1,$s3,2 # $t1= 4*i

! addu $t1,$t1,$s5 # $t1=addr A+4i
lw $t1,0($t1) # $t1=A[i]
add $s1,$s1,$t1 # g=g+A[i]
addu $s3,$s3,$s4 # i=i+j
bne $s3,$s2,Loop # goto Loop
# if i!=h
35  
 And  In  Conclusion  …  
• Computer  words  and  vocabulary  are  called  instrucIons  
and  instrucIon  set  respecIvely  
• MIPS  is  example  RISC  instrucIon  set  in  this  class  
• Rigid  format:  1  operaIon,  2  source  operands,  1  
desInaIon  
– add,sub,mul,div,and,or,sll,srl,sra!
– lw,sw,lb,sb  to  move  data  to/from  registers  from/to  
memory  
– beq, bne, j, slt, slti  for  decision/flow  control  
• Simple  mappings  from  arithmeIc  expressions,  array  
access,  if-­‐then-­‐else  in  C  to  MIPS  instrucIons  
36