Cache and Assembly help

[CJPowell27]

Hey guys I'm trying to study for my final (that totally isn't tomorrow) and ran into two problems  on our practice final that I'm not entirely sure how to get the answers provided.

Cache Problem: 

Spoiler

Switch in assembly Problem: for this problem I know what most of the assembly does, but I am not sure how to get the correct case numbers and their order.

Spoiler

 

[Mira Yurizaki]

I can't confirm if this is true in a general way of speaking since there's only one problem and answer set, but:

• The (S, E, B, m) notation means
  • S: How many items in a set (8 entries)
  • E: How many sets there are (2 sets)
  • B: How many blocks (or bytes) per entry (4 bytes)
  • m: Memory address size (13-bits)
• Block offset is calculated by taking the address you want to look up, dividing it by B, then using the remainder
  • 0x37A = 890, 890/4 = 222 with remainder 2.
• Set index is taken by multiplying S by B to get the number of bytes per set. Divide address by this and take the remainder. Using the remainder, divide it by B and round down to the nearest whole number.
  • 8 * 4 = 32. 890/32 = 27 remainder 26. 26 / 4 = 6.5.
• Cache tag looks like it's taking 8-bits from the most significant bit. 0x37A is 0 0011 0111 1010 (added an extra 0 because it's a 13-bit address space). Taking the first 8 bits from the most significant bit gets 0001 1011 = 0x1B
• It's a miss because the entry doesn't exist for that address.
• The last question is a miss because it wasn't a hit.

Regarding the switch in assembly, switch-case statements are often compiled in a way that somewhere else in the code there's what's called a jump table. All you do to jump to the appropriate case is get the value like an array in the jump table based on the value being tested in the switch statement, then used that value to make the appropriate jump.

 

So here's the source again with my comments

switcher:
    movq %rdi,%rax      ; Puts the value being tested in a register RAX
    subq $30,%rax       ; Subtracts 30 from it (probably a optimization)
    cmpq $4,%rax        ; Does a compare, which is really RAX - 4
    ja .L5              ; If RAX > 4, jump to L5
    jmp *.L7(,%rax,8)   ; Otherwise jump to one of the labels based on the 
                        ; jump table defined in L7 using the value of RAX
.L2
    movq $2,%rax        ; Move 2 to RAX
    jmp .L6             ; jump to L6
.L3
    movq $3,%rax        ; Move 3 to RAX
    jmp .L6             ; jump to L6
.L4
    movq $4,%rax        ; Move 4 to RAX
    jmp .L6             ; jump to L6
.L5
    movq $0,%rax        ; Move 0 to RAX
.L6
    retq                ; Return
.L7:
                        ; L7 is the jump table
    .long .L2           ; Value is 30 (RAX = 0 when accessing this)
    .long .L3           ; Value is 31 (RAX = 1 when accessing this)
    .long .L4           ; Value is 32 (RAX = 2 when accessing this)
    .long .L3           ; Value is 33 (RAX = 3 when accessing this)
    .long .L2           ; Value is 34 (RAX = 4 when accessing this)

EDIT: To further explain the line jmp *.L7(,%rax,8), the asterisk is saying the value defined in .L7(,%rax,8) is a pointer. The mess .L7(,%rax,8) is saying start at the address where .L7 points to, then offset by the value of RAX times 8. So if .L7 were address 0x0008000, then this expression is basically "jump to the value found at address 0x0008000 + (RAX * 8)"

 

The .long .L# declarations are declaring there's a long value in there. The value is the address where those labels are at. A .long in x64 (which I'm getting hints at this is what the assembly is for) is an 8-byte value, hence the multiply by 8.

 

 

Edited December 6, 2017 by M.Yurizaki