Comments on 8g compiler output

[Ben Bullock]

Recently there was some discussion about the relative speed of Go
versus Java, so I thought I'd look at the compiler output of the
program (this is the solution for the Project Euler problem four as
posted by Rio and me two days ago). Here is part of the Go code:

First line here is line 30 of bkb.go:

func isPalindrome(a int) bool {
getdigits := a;
maxdigits := 0;
var digits [6] int;
for i := 0; i < 6; i++ {
digits[i] = getdigits % 10;
getdigits /= 10;
if getdigits == 0 {
break;
}
maxdigits++;
}
for i := 0; i <= maxdigits/2; i++ {
if digits[i] != digits[maxdigits - i] {
return false;
}
}
return true;
}

--------------- end of Go code

At the bottom of the message is the assembly language output by the
compiler. I noticed that there is one very obvious optimization, this
code seems to contain six completely unnecessary JMP statements which
could be eliminated simply by concatenating things like

X JMP Y

Y JMP Z

Z ...

into

X JMP Z

Also, this was what made me suggest the /% because of the repeated
IDIVL.

I also have some questions about this compiler output which I couldn't
solve by Googling. First of all, what are the repeated

INT $3

in here? It seems to be something to do with a debugger, from what I
can work out.

Secondly, what is JCS? I can't find any documentation for this, and I
am struggling with the Go assembler source code so I couldn't work out
what it is.

Here is the assembler output I get, with comments added:

--- prog list "isPalindrome" ---
0227 (bkb.go:47) TEXT isPalindrome+0(SB),$64-8
0228 (bkb.go:31) MOVL a+0(FP),BX
0229 (bkb.go:31) MOVL BX,getdigits+-4(SP)
0230 (bkb.go:32) MOVL $0,SI
0231 (bkb.go:33) MOVL $0,AX
0232 (bkb.go:33) LEAL digits+-32(SP),DI
0233 (bkb.go:33) MOVL $6,CX
0234 (bkb.go:33) REP ,
0235 (bkb.go:33) STOSL ,
0236 (bkb.go:34) MOVL $0,CX
0237 (bkb.go:34) JMP ,240

# This line can only be reached by a jump to 238, because of the
# previous JMP. However it then immediately jumps to 297.

0238 (bkb.go:34) JMP ,297
0239 (bkb.go:34) INCL ,CX
0240 (bkb.go:34) MOVL CX,.noname+-44(SP)
0241 (bkb.go:34) CMPL .noname+-44(SP),$6
0242 (bkb.go:34) JGE ,238
0243 (bkb.go:35) MOVL AX,.noname+-48(SP)
0244 (bkb.go:35) MOVL DX,.noname+-52(SP)
0245 (bkb.go:35) MOVL getdigits+-4(SP),BX
0246 (bkb.go:35) MOVL BX,.noname+-56(SP)
0247 (bkb.go:35) MOVL $10,.noname+-60(SP)
0248 (bkb.go:35) MOVL .noname+-60(SP),BX
0249 (bkb.go:35) MOVL .noname+-56(SP),AX
0250 (bkb.go:35) CDQ ,

# One IDIVL, with the quotient discarded.

0251 (bkb.go:35) IDIVL BX,
0252 (bkb.go:35) MOVL DX,.noname+-44(SP)
0253 (bkb.go:35) MOVL .noname+-52(SP),DX
0254 (bkb.go:35) MOVL .noname+-48(SP),AX
0255 (bkb.go:35) LEAL digits+-32(SP),BX
0256 (bkb.go:35) MOVL BX,.noname+-52(SP)
0257 (bkb.go:35) MOVL .noname+-52(SP),BX
0258 (bkb.go:35) MOVL CX,.noname+-52(SP)
0259 (bkb.go:35) MOVL .noname+-52(SP),BP
0260 (bkb.go:35) CMPL BP,$6
0261 (bkb.go:35) JCS ,263
0262 (bkb.go:35) INT $3,
0263 (bkb.go:35) LEAL (BX)(BP*4),BX
0264 (bkb.go:35) MOVL BX,.noname+-48(SP)
0265 (bkb.go:35) MOVL .noname+-48(SP),BX
0266 (bkb.go:35) MOVL .noname+-44(SP),BP
0267 (bkb.go:35) MOVL BP,(BX)
0268 (bkb.go:36) LEAL getdigits+-4(SP),BX
0269 (bkb.go:36) MOVL BX,.noname+-44(SP)
0270 (bkb.go:36) MOVL .noname+-44(SP),BX
0271 (bkb.go:36) MOVL $10,.noname+-44(SP)
0272 (bkb.go:36) MOVL AX,.noname+-52(SP)
0273 (bkb.go:36) MOVL DX,.noname+-56(SP)
0274 (bkb.go:36) MOVL (BX),BP
0275 (bkb.go:36) MOVL BP,.noname+-60(SP)
0276 (bkb.go:36) MOVL .noname+-44(SP),BP
0277 (bkb.go:36) MOVL BP,.noname+-64(SP)
0278 (bkb.go:36) MOVL .noname+-64(SP),BP
0279 (bkb.go:36) MOVL .noname+-60(SP),AX
0280 (bkb.go:36) CDQ ,

# Another IDIVL, same operation, with the other register discarded.

0281 (bkb.go:36) IDIVL BP,
0282 (bkb.go:36) MOVL AX,.noname+-48(SP)
0283 (bkb.go:36) MOVL .noname+-56(SP),DX
0284 (bkb.go:36) MOVL .noname+-52(SP),AX
0285 (bkb.go:36) MOVL .noname+-48(SP),BP
0286 (bkb.go:36) MOVL BP,(BX)
0287 (bkb.go:37) JMP ,289

# Similar to above, this JMP can only be reached by another JMP, so it
# could be eliminated entirely.

0288 (bkb.go:37) JMP ,295
0289 (bkb.go:37) MOVL getdigits+-4(SP),BX
0290 (bkb.go:37) MOVL BX,.noname+-44(SP)
0291 (bkb.go:37) CMPL .noname+-44(SP),$0
0292 (bkb.go:37) JNE ,288
0293 (bkb.go:38) JMP ,238

# Similar to above, this JMP can only be reached by another JMP, so it
# could be eliminated entirely.

0294 (bkb.go:37) JMP ,295
0295 (bkb.go:40) INCL ,SI
0296 (bkb.go:34) JMP ,239
0297 (bkb.go:42) MOVL $0,CX
0298 (bkb.go:42) JMP ,301

# Similar to above, this JMP can only be reached by another JMP, so it
# could be eliminated entirely.

0299 (bkb.go:42) JMP ,352
0300 (bkb.go:42) INCL ,CX
0301 (bkb.go:42) MOVL AX,.noname+-48(SP)
0302 (bkb.go:42) MOVL DX,.noname+-52(SP)
0303 (bkb.go:42) MOVL SI,.noname+-56(SP)
0304 (bkb.go:42) MOVL $2,.noname+-60(SP)
0305 (bkb.go:42) MOVL .noname+-60(SP),BX
0306 (bkb.go:42) MOVL .noname+-56(SP),AX
0307 (bkb.go:42) CDQ ,
0308 (bkb.go:42) IDIVL BX,
0309 (bkb.go:42) MOVL AX,.noname+-44(SP)
0310 (bkb.go:42) MOVL .noname+-52(SP),DX
0311 (bkb.go:42) MOVL .noname+-48(SP),AX
0312 (bkb.go:42) MOVL CX,.noname+-48(SP)
0313 (bkb.go:42) MOVL .noname+-48(SP),BX
0314 (bkb.go:42) CMPL .noname+-44(SP),BX
0315 (bkb.go:42) JLT ,299
0316 (bkb.go:43) JMP ,318

# Similar to above, this JMP can only be reached by another JMP, so it
# could be eliminated entirely.

0317 (bkb.go:43) JMP ,351
0318 (bkb.go:43) LEAL digits+-32(SP),BX
0319 (bkb.go:43) MOVL BX,.noname+-52(SP)
0320 (bkb.go:43) MOVL .noname+-52(SP),BX
0321 (bkb.go:43) MOVL CX,.noname+-52(SP)
0322 (bkb.go:43) MOVL .noname+-52(SP),BP
0323 (bkb.go:43) CMPL BP,$6
0324 (bkb.go:43) JCS ,326
0325 (bkb.go:43) INT $3,
0326 (bkb.go:43) LEAL (BX)(BP*4),BX
0327 (bkb.go:43) MOVL BX,.noname+-48(SP)
0328 (bkb.go:43) MOVL .noname+-48(SP),BX
0329 (bkb.go:43) MOVL (BX),BP
0330 (bkb.go:43) MOVL BP,.noname+-44(SP)
0331 (bkb.go:43) MOVL SI,.noname+-60(SP)
0332 (bkb.go:43) MOVL .noname+-60(SP),BX
0333 (bkb.go:43) SUBL CX,BX
0334 (bkb.go:43) MOVL BX,.noname+-56(SP)
0335 (bkb.go:43) MOVL .noname+-56(SP),BX
0336 (bkb.go:43) LEAL digits+-32(SP),BP
0337 (bkb.go:43) CMPL BX,$6

# I spent about thirty minutes Googling and reading source code trying
# to work out what JCS is, but have failed so far.

0338 (bkb.go:43) JCS ,340
0339 (bkb.go:43) INT $3,
0340 (bkb.go:43) LEAL (BP)(BX*4),BP
0341 (bkb.go:43) MOVL BP,.noname+-52(SP)
0342 (bkb.go:43) MOVL .noname+-52(SP),BX
0343 (bkb.go:43) MOVL (BX),BP
0344 (bkb.go:43) MOVL BP,.noname+-48(SP)
0345 (bkb.go:43) MOVL .noname+-48(SP),BX
0346 (bkb.go:43) CMPL .noname+-44(SP),BX
0347 (bkb.go:43) JEQ ,317
0348 (bkb.go:44) MOVB $0,.noname+4(FP)
0349 (bkb.go:44) RET ,

# The following JMP could be replaced by NOP:

0350 (bkb.go:43) JMP ,351
0351 (bkb.go:42) JMP ,300
0352 (bkb.go:47) MOVB $1,.noname+4(FP)
0353 (bkb.go:47) RET ,

This line seems to be unreached:

0354 (bkb.go:47) CALL ,runtime.throwreturn+0(SB)
0355 (bkb.go:47) RET ,

[Russ Cox]

If you examine the output of 8l -a bkb.8,
you should find that the unnecessary JMPs are
all gone. The compiler lets the linker be in
charge of laying out code.

The INT $3 are leftover debugging from I don't
know when (oops). Those lines are supposed
to say CALL throwindex(SB), which would report
an array index out of range error. But even the
INT $3 will cause a nice stack trace, so it doesn't
matter too much.

JCS (and JCC) are the way that the 8g tool suite
spells the Intel instructions JC and JNC. The
S and C suffixes are "set" and "clear".

Thus the sequence:

0260 (bkb.go:35) CMPL BP,$6
0261 (bkb.go:35) JCS ,263
0262 (bkb.go:35) INT $3,
0263 (bkb.go:35) LEAL (BX)(BP*4),BX

is doing an array bounds check before indexing
into the array.

The IDIVL instructions shouldn't even be there.
The 6g compiler knows how to rewrite them as
multiplications, but 8g doesn't have that code yet.

Russ