How Are Loops Translated to Assembly?

:information_source: This article is based on Go 1.13.

Loops are powerful concepts in programming and quite easy to handle. However, it has to be translated into basic instructions the computer can understand. The way it is compiled could also impact other components in the standard library. Let’s start by analyzing the range loop.

Loop assembly

A range loop iterates an array, slice, or channel. Here is an example of a function that adds up numbers with looping on the slice:

func main() {
   l := []int{9, 45, 23, 67, 78}
   t := 0

   for _, v := range l {
      t += v
   }

   println(t)
}

The command go tool compile -S main.go dumps the generated assembly code, and here is the output related to the range loop:

0x0041 00065 (main.go:4)   XORL   AX, AX
0x0043 00067 (main.go:4)   XORL   CX, CX

0x0045 00069 (main.go:7)   JMP    82
0x0047 00071 (main.go:7)   MOVQ   ""..autotmp_5+16(SP)(AX*8), DX
0x004c 00076 (main.go:7)   INCQ   AX
0x004f 00079 (main.go:8)   ADDQ   DX, CX
0x0052 00082 (main.go:7)   CMPQ   AX, $5
0x0056 00086 (main.go:7)   JLT    710x0058 00088 (main.go:11)  MOVQ   CX, "".t+8(SP)

I split the instructions in two parts: the initialization and the loop itself. The first two instructions initialize two registers to zero:

0x0041 00065 (main.go:4)   XORL   AX, AX
0x0043 00067 (main.go:4)   XORL   CX, CX

The register AX contains the current position in the loop, while CX contains the value of the variable t . Here is the visual representation with the instructions and general-purpose registers:

The loop starts with an instruction JMP 82 that stands for “ Jump to instruction 82”. This targeted instruction can be identified thanks to the second column:

The next instruction CMPQ AX, $5 stands for “ Compare register AX and the value 5.” It actually subtracts the values of the register DX from AX and stores the result to another register. This value can now be used in the next instruction JLT 71 , which stands for “Jump to instruction 71 if less than 0.” Here is the updated diagram:

If the condition is not satisfied, the program will not jump and continue to the next instruction after the loop.

So, we now have the skeleton of the loop. Here is the loop converted back to Go:

goto end
start:
   ?
end:
   if i < 5 {
      goto start
   }

println(t)

The body of the loop is missing, here are the instructions:

0x0047 00071 (main.go:7)   MOVQ   ""..autotmp_5+16(SP)(AX*8), DX
0x004c 00076 (main.go:7)   INCQ   AX
0x004f 00079 (main.go:8)   ADDQ   DX, CX

The first instruction MOVQ ""..autotmp_5+16(SP)(AX*8), DX stands for “ Move memory from source to destination. ” It is composed by:

• The slice ""..autotmp_5+16(SP) . SP is the stack pointer — our current memory frame — and autotmp_* is an auto-generated variable name.
• An offset of 8 (int is 8 bits on a 64-bit architecture) multiplied by the value of the register AX, current position in the loop.
• A destination represented by the register DX that now contains the current value of the loop.

Then, INCQ stands for “ Increment ” and will increment the current position of the loop:

The last instruction of the loop body is ADDQ DX, CX that stands for “ Add DX into CX. ” We have seen previously that DX contains the current value of the loop, and CX is the register that contains the content of the variable t :

It will loop until the loop counter reaches five. Then, the instruction right after the loop shows the register CX moves its value to t :

0x0058 00088 (main.go:11)   MOVQ   CX, "".t+8(SP)

Here is the diagram at its final state:

We can also finalize the translation of the loop in Go:

func main() {
   l := []int{9, 45, 23, 67, 78}
   t := 0
   i := 0

   var tmp int

   goto end
start:
   tmp = l[i]
   i++
   t += tmp
end:
   if i < 5 {
      goto start
   }

   println(t)
}

Generating the assembly code for this new program will give the exact same output.

Improvements

The way a loop is translated internally could have an impact on other features such as the Go scheduler. Prior to Go 1.10, a loop was compiled like the following code:

func main() {
   l := []int{9, 45, 23, 67, 78}
   t := 0
   i := 0

   var tmp int
   p := uintptr(unsafe.Pointer(&l[0]))

   if i >= 5 {
      goto end
   }
body:
   tmp = *(*int)(unsafe.Pointer(p))
   p += unsafe.Sizeof(l[0])
   i++
   t += tmp
   if i < 5 {
      goto body
   }
end:
   println(t)
}

The problem with this implementation is that the pointer p is past the end of the allocation when i reaches five. That issue makes the loop not easily preemptible since its body is not safe. The optimization of the compilation of the loop makes sure it does not create any past-the-end pointer. This improvement has been made in preparation for a non-cooperative preemption in the Go scheduler. You can find more details about it in the proposal “ Proposal: Non-cooperative goroutine preemption .”