cmd/compile: turn nilcheckelim into branchelim #12628

josharian · 2015-09-15T18:12:17Z

nilcheckelim is effective and fast, but only eliminates nil checks. There are other kinds of duplicate branches that it would be nice to also elide.

For example, consider code like:

func f_ssa(e interface{}) int {
  if e.(int) < 0 {
    return -1
  }
  return e.(int) * 2
}

Each of the type assertions will generate a branch to check e's dynamic type, but the subsequent checks are unnecessary, and could be eliminated with very similar logic to nilcheckelim. Code like this, in which an interface is type asserted repeatedly, shows up in the compiler, so it is not theoretical.

I'd expect the souped-up optimization to also handle (silly) code like:

func f_ssa(i int) int {
  var x int
  if i < 3 {
    x += 1
  }
  if i < 3 {
    x += 2
  }
  return x
}

(The compiled code should only have one branch.)

/cc @randall77 @tzneal @dr2chase

josharian · 2016-02-29T03:33:32Z

cc @brtzsnr

navytux · 2017-04-07T07:52:51Z

Current (go version devel +03d1aa6024 Fri Apr 7 04:46:42 2017 +0000 linux/amd64) state is:

func f_ssa(e interface{}) int {
  if e.(int) < 0 { 
    return -1
  }
  return e.(int) * 2 
}

->

TEXT ·f_ssa(SB), $32-24 // s2.go:3
        // MOVQ    (TLS), CX (stack growth prologue)
        // CMPQ    SP, 16(CX)
        // JLS     124
        // SUBQ    $32, SP
        // MOVQ    BP, 24(SP) (BP save)
        // LEAQ    24(SP), BP (BP init)
        // FUNCDATA $0, gclocals·522734ad228da40e2256ba19cf2bc72c(SB) (args)
        FUNCDATA   $1, gclocals·69c1753bd5f81501d95132d08af04464(SB) (locals)
        LEAQ       type.int(SB), AX         // s2.go:4
        MOVQ       e+0(FP), CX
        CMPQ       AX, CX
        JNE        pc96
        MOVQ       e+8(FP), AX
        MOVQ       (AX), AX
        TESTQ      AX, AX
        JGE        pc78
        MOVQ       $-1, _r1+16(FP)          // s2.go:5
        // MOVQ    24(SP), BP (BP restore)
        // ADDQ    $32, SP (SP restore)
        RET
pc78:
        SHLQ       $1, AX                   // s2.go:7          <-- NOTE no second check
        MOVQ       AX, _r1+16(FP)
        // MOVQ    24(SP), BP (BP restore)
        // ADDQ    $32, SP (SP restore)
        RET
pc96:
        // MOVQ    CX, (SP) (stack growth)  // s2.go:4
        // MOVQ    AX, 8(SP)
        // LEAQ    type.interface {}(SB), AX
        // MOVQ    AX, 16(SP)
        // PCDATA  $0, $1
        // CALL    runtime.panicdottypeE(SB)
        // UNDEF
        // NOP
        // PCDATA  $0, $-1                  // s2.go:3
        // CALL    runtime.morestack_noctxt(SB)
        // JMP     0

i.e. the typecheck for return e.(int) * 2 is gone.

func f_ssa(i int) int {
  var x int
  if i < 3 {
    x += 1
  }
  if i < 3 {
    x += 2
  }
  return x
}

->

TEXT ·f_ssa(SB), $0-16 // s3.go:3
        NO_LOCAL_POINTERS
        // FUNCDATA $0, gclocals·f207267fbf96a0178e8758c6e3e0ce28(SB) (args)
        // FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) (no locals)
        MOVQ       i+0(FP), AX    // s3.go:5
        CMPQ       AX, $3
        SETLT      AL
        MOVBLZX    AL, AX         // s3.go:11
        JGE        pc21           // s3.go:8
        ADDQ       $2, AX         // s3.go:9
pc21:
        MOVQ       AX, _r1+8(FP)  // s3.go:11
        RET

only 1 branch but another branch sits implicitly in SETLT: if we change first x += 1 to x += 5 it becomes

TEXT ·f_ssa(SB), $0-16 // s3.go:3
        NO_LOCAL_POINTERS
        // FUNCDATA $0, gclocals·f207267fbf96a0178e8758c6e3e0ce28(SB) (args)
        // FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) (no locals)
        MOVQ       i+0(FP), AX    // s3.go:5
        CMPQ       AX, $3
        JGE        pc30
        MOVQ       $5, AX         // s3.go:6
pc18:
        JGE        pc24           // s3.go:8
        ADDQ       $2, AX         // s3.go:9
pc24:
        MOVQ       AX, _r1+8(FP)  // s3.go:11
        RET
pc30:
        MOVQ       $0, AX         // s3.go:3
        JMP        pc18           // s3.go:5

i.e. still 2 branches.

navytux · 2017-04-07T08:46:13Z

Let me add that the second case is actually not silly and shows up in practice when the first check is in another function that gets inlined.

For example consider BTree lookup code - it needs to compare keys while doing the lookup and take decisions where to go next depending on comparision result. E.g. github.com/cznic/b allows to define such comparision function dynamically:

https://github.com/cznic/b/blob/aaaa43c9/btree.go#L52
https://github.com/cznic/b/blob/aaaa43c9/btree.go#L93

but some of us generate code from it which calls comparision function directly:

https://lab.nexedi.com/kirr/neoppod/blob/7c87537a/t/neo/storage/fs1/fsb/gen-fsbtree#L23

func oidCmp(a, b zodb.Oid) int {       // zodb.Oid is uint64
	if a < b {
		return -1
	} else if a > b {
		return +1
	} else {
		return 0
	}
}

(https://lab.nexedi.com/kirr/neoppod/blob/7c87537a/t/neo/storage/fs1/fsb/cmp.go)

The comparision is then used e.g. like this:

			switch cmp := oidCmp(k, mk); {
			case cmp > 0:
				l = m + 1
			case cmp == 0:
				return m, true
			default:
				h = m - 1
			}

(https://lab.nexedi.com/kirr/neoppod/blob/7c87537a/t/neo/storage/fs1/fsb/fsbtree.go#L360)

so inside oidCmp k and mk are already compared and case cmp > 0 can directly use case k > mk but it does not happen even though oidCmp is inlined.

This BTree lookup code shows at top of profiles for some workloads...

A simplified check for this issue is below:

package xxx

func zzz2(x, y int) int {
        var cmp int
        if x < y {
                cmp = -1
        } else {
                cmp = +1
        }

        if cmp < 0 {
                return x - y
        } else {
                return x + y
        }
}

which gets compiled to

TEXT ·zzz2(SB), $0-24 // switch2.go:3
        NO_LOCAL_POINTERS
        // FUNCDATA $0, gclocals·54241e171da8af6ae173d69da0236748(SB) (args)
        // FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) (no locals)
        MOVQ       x+0(FP), AX  // switch2.go:5
        MOVQ       y+8(FP), CX
        CMPQ       AX, CX
        JGE        pc45
        MOVQ       $-1, DX      // switch2.go:6         <-- NOTE cmp = -1
pc22:
        TESTQ      DX, DX       // switch2.go:11        <--
        JGE        pc36         //                      <-- NOTE if cmp < 0
        SUBQ       CX, AX       // switch2.go:12
        MOVQ       AX, _r2+16(FP)
        RET
pc36:
        ADDQ       CX, AX       // switch2.go:14
        MOVQ       AX, _r2+16(FP)
        RET
pc45:
        MOVQ       $1, DX       // switch2.go:8         <-- NOTE cmp = +1
        JMP        pc22         // switch2.go:5

This seems to be very related to #17862

Thanks beforehand,
Kirill

/cc @dsnet, @cznic

josharian · 2017-05-18T19:56:34Z

Too late for 1.9.

rsc added this to the dev.ssa milestone Oct 23, 2015

bradfitz modified the milestones: dev.ssa, Go1.7 Mar 2, 2016

This was referenced Mar 31, 2016

cmd/compile: unnecessary branching #15031

Open

cmd/compile: weird double-jump in code generation #15090

Closed

ianlancetaylor changed the title ~~cmd/compile/ssa: turn nilcheckelim into branchelim~~ cmd/compile: turn nilcheckelim into branchelim May 16, 2016

rsc modified the milestones: Go1.8, Go1.7 May 17, 2016

quentinmit added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 11, 2016

rsc modified the milestones: Go1.9, Go1.8 Oct 21, 2016

josharian added the Performance label May 18, 2017

josharian modified the milestones: Go1.10, Go1.9 May 18, 2017

bradfitz modified the milestones: Go1.10, Go1.11 Nov 28, 2017

bradfitz modified the milestones: Go1.11, Unplanned May 18, 2018

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: turn nilcheckelim into branchelim #12628

cmd/compile: turn nilcheckelim into branchelim #12628

josharian commented Sep 15, 2015

josharian commented Feb 29, 2016

navytux commented Apr 7, 2017

navytux commented Apr 7, 2017

josharian commented May 18, 2017

cmd/compile: turn nilcheckelim into branchelim #12628

cmd/compile: turn nilcheckelim into branchelim #12628

Comments

josharian commented Sep 15, 2015

josharian commented Feb 29, 2016

navytux commented Apr 7, 2017

navytux commented Apr 7, 2017

josharian commented May 18, 2017