Introduction to Computer Systems Machine-Level Representation of Programs

Machine-Level Representation of Programs

Introduction

x86 Processors

Definitions


Program Encodings

Programming Model

Types of Operations

Compiling


long plus(long x, long y);

void sumstore(long x, long y, long *dest)
{
    long t = plus(x, y);
    *dest = t;
}

Compiler translates C code to Assembly code


sumstore:
    pushq  %rbx
    movq   %rdx, %rbx
    call   plus
    movq   %rax, (%rbx)
    popq   %rbx
    ret

Assembler then creates the Machine Code


0x53 0x48 0x89 0xd3 0xe8
0xf2 0xff 0xff 0xff 0x48
0x89 0x03 0x5b 0xc3

Objdump


Data Formats

Basic Formats (not types!)

Assembly Instruction Suffixes

Registers

Integer Registers

Operand Types

Example:

Store t where dest points


long *dest = t;

move quad word to memory


movq %rax, (%rbx)

Raw bytes:


0x40059e: 48 89 03

Key:


%rax = t
%rbx = dest
M[%rbx] = *dest


Data Transfer

C Swap Function:


void swap(long *xp, long *yp)
{
    long t0 = *xp;
    long t1 = *yp;
    *xp = t1;
    *yp = t0;
}

Assembly:


swap:
    movq (%rdi), %rax
    movq (%rsi), %rdx
    movq %rdx, (%rdi)
    movq %rax, (%rsi)
    ret

Stack operations


Arithmetic and Logical

Two Operand Operations

One Operand Instructions

Load Effective Address

Example:


long times12(long x)
{
    return x * 12;
}

Assembly:


leaq (%rdi,%rdi,2), %rax    # t <- x+x*2
salq $2, %rax                # return t<<2


Control Transfer

Condition Codes

Reading Condition Codes

Example:


int gt (long x, long y)
{
    return x > y;
}

Assembly:


cmpq    %rsi, %rdi    # compare x and y
setq    %al            #
movzbl  %al, %eax    #
ret

Branching

Goto Code

If-Else


long absdiff (long x, long y)
{
    long result:

    if (x > y)
        result = x - y;

    else
        resilt = y - x

    return result
}

asbdiff:
    cmpq  %rsi, %rdi  # x, y
    jle   .L4
    movq  %rdi, %rax
    subq  %rsi, %rax
    ret
.L4                   # x <= y
    movq  %rsi, %rax
    subq  %rdi, %rax
    ret

Using goto in C


long absdiff_j (long x, long y)
{
    long result;
    int ntest = x <= y;

    if(ntest) goto Else;
    result =  x - y;
    goto Done;
Else:
    result = y - x;
Done:
    return result;
}

Do-While


long pcount_do(unsigned long x)
{
    long result = 0
}

While


while (test)
{

}

    goto test
loop:

test:

Switch


long switch_eg (long x)
{
    switch(x)
    {
        case 1:
            //execute
            break;
        case 2:
            //execute
            break;
        case ...:
           //...
        default:
            break;
    }
}

switch_eg:
    movq   %rdx, %rcx
    compq  $6, %rdi        # %rdi = x > $6?
    ja     .L8
    jmp    *.L4(,%rdi, 8)  # indirect

# Jump Table:
.section .rodata
    .align 8
.L4:
    .quad   .L8  # x = 0
    .quad   .L3  # x = 1
    .quad   .L5  # x = 2
    .quad   .L9  # x = 3
    .quad   .L8  # x = 4
    .quad   .L7  # x = 5
    .quad   .L7  # x = 6
Case 1

switch(x)
{
    case 1: /* .L3 */
        w = y * z;
        break;
}

.L3:
    movq   %rsi, %rax #y
    imulq  %rdx, ...
    ...
Case 2 & 3

long w = 1;
switch(x)
{
    case 2: /* .L5 */
        w = y / z;
        /* Fall Through */
    case 3: /* .L9 */
        w += z;
        break
}

.L5:
    movq   %rsi, %rax
    cqto
    idivq   %rcx
    jmp    .L6

.L6:
    ...
Case 5, 6, and Default

switch(x)
{
    case 5:
    case 6: /* Both get .L7 */
        w -= z;
    default:
        w = 2;
}

.L7: