Control Flow

• Flow of control:

  • sequence of instruction executions performed by a program

• Every program execution can be described by such a linear sequence

Loops

• In Java:

   
  xxxxxxxxxx
  9
  1
  public static Foo {
  2
    static int s = 0;
  3
    static int i i;
  4
    static int a[] = new int [] {2, 4, 6, 8, 10, ..., 20};
  5
    static void foo() {
  6
        for (i = 0; i < 10; i++)
  7
          s += a[i];
  8
    }
  9
  }
  

• In C:

   
  xxxxxxxxxx
  7
  1
  int s = 0;
  2
  int i;
  3
  int a[] = {2, 4, 6, 8, 10, 12, 14, 16 ...};
  4
  void foo() {
  5
      for (i = 0; i < 10; i++)
  6
        s += a[i];
  7
  }
  

  alternatively: i < sizeof(a) / sizeof(a[0]);

Loops Using Pointer Arithmetic

• Keep a pointer (instead of index) at current location:

   
  xxxxxxxxxx
  8
  1
  int s = 0;
  2
  int *p;
  3
  int a[] = {2, 4, 6, 8, 10, ...};
  4
  void foo() {
  5
      p = a;
  6
      while (p < a + 10)
  7
        s += *p++;
  8
  }
  

Index vs Pointer Arithmetic

• Trade-off:

  • Pointers require less assembly indexed computation
  • Indexes (usually) make code easier to understand

• Copying an array using array syntax:

   
  xxxxxxxxxx
  4
  1
  void intcpy(int *s, int *d, int n){
  2
    for (int i = 0; i< n; i++)
  3
      d[i] = s[i];
  4
  }
  

• Copying an array using pointer arithmetic:

   
  xxxxxxxxxx
  4
  1
  void intcpy(int *s, int *d, int n){
  2
      while(n--)
  3
        *d++ = *s++;
  4
  }
  

Implementing Loops in Assembly

 
xxxxxxxxxx
7
1
int s = 0;
2
int i;
3
int a[] = {2, 4, 6, ..., 12};
4
void foo() {
5
    for (i = 0; i < 10; i++)
6
      s += a[i];
7
}

• Can we implement this loop with existing ISA?

Loop Unrolling

• This vcode is equivalent ("unrolled" version)

   
  xxxxxxxxxx
  8
  1
  int s = 0;
  2
  int a [] = {2, 4, 6, 8, 10,...}
  3
  void foo() {
  4
    s += a[0];
  5
    s += a[1];
  6
    ...
  7
    s += a[9];
  8
  }
  

• Can we generalize this technique?

  • Unrolling only works if number of iterations is staticcaly known

Dissecting A Loop: GOTO

 
xxxxxxxxxx
2
1
for (i = 0; i < 10; i++)
2
  s += a[i];

• Can be translated to:

   
  xxxxxxxxxx
  6
  1
          i = 0;
  2
  loop:   goto end_loop if not (i < 10)
  3
          s += [ai];
  4
          i++;
  5
          goto loop
  6
  end_loop:
  

Control Flow in the Machine

• Program Counter (PC)

  • special CPU register that stores address of next instruction to execute

• For sequential instructions, PC is updated in fetch

  • incremented by 2 or 6 depending on instruction size

• So, to implement a goto, all we need is to change the PC

Extending the ISA: Control Flow

loop: goto end_loop if not (i<10)

• New instruction: conditional jump

  • go to
    if
  • PC $\leftarrow$
    if

• Options for evaluating condition

  • Unconditional (always jump)

  • Conditional based on register value

    • common in RISC, used in SM213

  • Conditional based on result of last ALU instruction

    • used in Intel-based (x86/x86-64) architecture

Jump Instruction Size

• Problem: memory addresses are big

  • so, instructions that go to specific instructions are big
  • control-flow instruction are common

• Jumps usually move a short distance (forward or backward)

  • e.g., loops, if statements

• Solution: relative addressing

  • instead of specifying the address to jump, specify the offset from current instruction

    • use current value of PC as base addresss
    • remember PC has already updated in fetch

  • must be signed number (can jump backward)

  • jumps using relative addresses are called branches

• Assembly still specifies actual address / label

  • converted to offset by assembler

Jump Instruction Example

 
xxxxxxxxxx
5
1
1000: goto 1008
2
1002: ...
3
1004: ...
4
1006: ...
5
1008: ...

• Option 1: absolute addressing (jump)

  X— 00001008

• Option 2: relative addressing (branch)

  Y-03

  PC after fetch is 1002, so offset is 6 Since offset is always even, we can divide by 2

New ISA Instructions

• So, we need the following instructions:

  • at least one PC-relative jump (branch)

  • at least one absolute jump

  • some form of conditional jumps

    • make these relative (why?)

  • New instructions:

    

Converting a Loop

 
xxxxxxxxxx
6
1
        i = 0;
2
loop:   goto end_loop if (i - 10 == 0)
3
        s += a[i];
4
        i++;
5
        goto loop
6
end_loop:

 
xxxxxxxxxx
15
1
        ld $0, r0
2
        ld $a, r1
3
        ld $s, 42
4
        ld (r2), r2
5
        ld $-10, r4
6
loop:   mov r0, r5
7
        add r4, r5
8
        beq r5, end_loop
9
        ld (r1, r0, 4), r3
10
        add r3, r2
11
        inc r0
12
        br loop
13
end_loop: ld $2, r1
14
        st r2, (r1)
15
        st r0, 4(r1)

-

Implementing Conditionals

• In Java or C:

  if (<condition>) <then-statements> else <else-statements>

• Pseudo-code using goto:

   
  xxxxxxxxxx
  6
  1
          c = not <condition>
  2
          goto then if (c == 0)
  3
  else:   <else-statements>
  4
          goto end_if
  5
  then:   <then-statements>
  6
  end_loop:
  

Static Procedure Calls

• In Java:

 
xxxxxxxxxx
10
1
public class A {
2
    public static void ping () {
3
        
4
    }
5
}
6
public class Foo {
7
    public static void foo() {
8
        A.ping();
9
    }
10
}

• Method: subroutine with a name, arguments and a local scope

• Method invocation: causes the method to run with:

  • Values bound to arguments
  • Possible result bound to the invocation

Static Procedure Calls

• In C:

 
xxxxxxxxxx
4
1
void ping () {}
2
void foo () {
3
    A.ping ();
4
}

• Procedure/function: subroutine with a name, arguments and local scope

  • Function usually restircted to the ones with return value

• Procedure call causes the procedure to run with:

  • Values bound to arguments
  • Possible result bound to the invocation

Control Flow in Procedure Calls

 
xxxxxxxxxx
3
1
void foo () {
2
  ping();
3
}

 
xxxxxxxxxx
1
1
void ping () {}

• Caller: goto ping (jump)

  • Callee: do whatever ping does
  • Callee: return to ???

• Caller: continue executing

• Question: return is a jump, but to where?

  • Static or dynamic?

Implementing Procedure Return

• Return address is:

  • The address the procedure jumps to when it completes

  • The address of the instruction following the call that caused the run

  • A dynamic property of the program

    • A function may be called from different locations

• Questions

  • How does the procedure know the return address?
  • How does it jump to a dynamic address?

• Only the caller knows the address

  • So the caller must save it before it makes the call

  • Convention: caller will save the return address in r[6]

    • There is a problem here, more on this later

  • We need a new instruction to read the PC

    • We'll call it gpc

• Jumping back to return address

  • We need a new isntruction to jump to dynamic address

New ISA Instructions

• New requirements

  • Read the value of PC
  • Jump to a dytnmiacally determined target address

• New instructions:

Control Flow in Procedure Calls

 
xxxxxxxxxx
3
1
void foo() {
2
  ping();
3
}

 
xxxxxxxxxx
1
1
void ping () {}

 
xxxxxxxxxx
5
1
foo:    gpc $6, r6      # r6 = pc of instruction after jump
2
        j   ping        # goto ping
3
​
4
ping:   ...
5
        j   (r6)        # return