Wandering Thoughts archives

2019-06-09

Go recognizes and specially compiles some but not all infinite loops

A while back, for my own reasons, I wrote an 'eatcpu' program to simply eat some number of CPUs worth of CPU time (by default, all of the CPUs on the machine). I wrote it in Go, because I wanted a straightforward program and life is too short to deal with threading in C. The code that uses CPU is simply:

func spinner() {
        var i int
        for {
                i++
        }
}

At the time I described this as a simple integer CPU soaker, since the code endlessly increments an int. Recently, to make my life more convenient, I decided to put it up on Github, and as part of that I decided that I wanted to actually know what it was doing; specifically I wanted to know if it actually was all running in CPU registers or if Go was actually loading and storing from memory all of the time. I did this in the straightforward way of running 'go tool compile -S' (after some research) and then reading the assembly. It took me some time to understand what I was reading and believe in it, because here is the entire assembly that spinner() compiles down to:

0x0000 00000 (eatcpu.go:27)     JMP     0
0x0000 eb fe

(The second line is the actual bytes of object code.)

Go 1.12.5 had recognized that I had an infinite loop with no outside effects and had compiled it down to nothing more than that. Instead of endless integer addition, I had an endless JMP, which was probably using almost none of the CPU's circuitry (certainly it doesn't need to use the integer ALU).

The Go compiler is clever enough to recognize that a variation of this is still an infinite loop:

func spinner2() int {
        var i int
        for {
                i++
        }
        return i
}

This too compiles down to 'JMP 0', since it can never exit the for loop to return anything.

However, the Go compiler does not recognize impossible situations as being infinite loops. For example, we can write the following:

func spinner3() uint {
        var i uint
        for ; i >= 0 ; {
                i++
        }
        return i
}

Since i is an unsigned integer, the for condition is always true and the loop will never exit. However, Go 1.12.5 compiles it to actual arithmetic and looping code, instead of just a 'JMP 0'. The core of the assembly code is:

0x0000  XORL    AX, AX
0x0002  JMP     7
0x0004  INCQ    AX
0x0007  TESTQ   AX, AX
0x000a  JCC     4
0x000c  MOVQ    AX, "".~r0+8(SP)
0x0011  RET

(The odd structure is because of how plain for loops are compiled. The exit check is relocated to the bottom of the loop, and then on initial loop entry, at 0x0002, we skip over the loop body to start by evaluating the exit check.)

If I'm understanding the likely generated x86 assembly correctly, this will trivially never exit; TESTQ likely compiles to some version of TEST, which unconditionally clears CF (the carry flag), and JCC jumps if the carry flag is clear.

(The Go assembler's JCC is apparently x86's JAE, per here, and per this x86 JUMP quick reference, JAE jumps if CF is clear. Since I had to find all of that and follow things through, I'm writing it down.)

On the whole, I think both situations are reasonable. Compiling infinite for loops to straight JMPs is perfectly reasonable, since they do get used in real Go code, and so is eliminating operations that have no side effects; put them together and spinner() turns into 'JMP 0'. On the other hand, the unsigned int comparison in spinner3() should never happen in real, non-buggy code, so it's probably fine for the optimizer to not recognize that it's always true and thus that this creates an infinite loop with no outside effects.

(There is little point to spending effort on optimizing buggy code.)

PS: I don't know if there's already a Go code checker that looks for unsigned-related errors like the comparison in spinner3(), but if there isn't there is probably room for one.

programming/GoInfiniteLoopOptimization written at 21:56:40; Add Comment


Page tools: See As Normal.
Search:
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.