cmd/compile: suboptimal constant propagation #59399

y1yang0 · 2023-04-03T13:24:13Z

Hi, go compiler combines many passes(e.g. prove,deadcode,opt,phielim,etc) to achieve an effect similar to conditional constant propagation, but it cannot discover some constant facts:

func tt(a int, b int, c int) int {
	i := 1
	done := 0
	for i > 0 && done != 1 {
		if i == 1 {
			done = 1
		} else {
			i = i + 1
		}
	}
	return i
}

Which generates an unnecessary loop
--go

00000 (4) TEXT main.tt(SB), ABIInternal
00001 (4) FUNCDATA $0, gclocals·g2BeySu+wFnoycgXfElmcg==(SB)
00002 (4) FUNCDATA $1, gclocals·g2BeySu+wFnoycgXfElmcg==(SB)
00003 (4) FUNCDATA $5, main.tt.arginfo1(SB)
00004 (4) FUNCDATA $6, main.tt.argliveinfo(SB)
b1
00005 (4) PCDATA $3, $1
v16
00006 (4) MOVL $1, AX
v17
00007 (4) XORL CX, CX
v24
00008 (+7) TESTQ AX, AX
b2
00009 (7) JLE 18
v27
00010 (7) CMPQ CX, $1
b6
00011 (7) JEQ 18
v31
00012 (+8) CMPQ AX, $1
b3
00013 (8) JNE 16
v19
00014 (8) MOVL $1, CX
b9
00015 (7) JMP 8
v21
00016 (+11) INCQ AX
b10
00017 (11) JMP 8
b5
00018 (+14) RET
00019 (?) END

--cpp

sccp(int):
        mov     eax, 1
        ret

--Java

[Verified Entry Point]
  # {method} {0x00007fb9b4400878} 'test6' '()I' in 'Test'
  #           [sp+0x20]  (sp of caller)
 ;; N1: #	out( B1 ) <- in( B1 )  Freq: 1
 ;; B1: #	out( N1 ) <- BLOCK HEAD IS JUNK  Freq: 1
  0x00007fb9f8b2c2a0:   mov    %eax,-0x18000(%rsp)
  0x00007fb9f8b2c2a7:   push   %rbp
  0x00007fb9f8b2c2a8:   sub    $0x10,%rsp
  0x00007fb9f8b2c2ac:   cmpl   $0x0,0x20(%r15)
  0x00007fb9f8b2c2b4:   jne    0x00007fb9f8b2c2f2           ;*synchronization entry
                                                            ; - Test::test6@-1 (line 93)
  ;;;;;;;ok
  0x00007fb9f8b2c2ba:   mov    $0x1,%eax                    ;*goto {reexecute=0 rethrow=0 return_oop=0}
                                                            ; - Test::test6@20 (line 97)
  0x00007fb9f8b2c2bf:   mov    0x3c0(%r15),%r10             ; ImmutableOopMap {}
                                                            ;*goto {reexecute=1 rethrow=0 return_oop=0}
                                                            ; - (reexecute) Test::test6@20 (line 97)
  0x00007fb9f8b2c2c6:   test   %eax,(%r10)                  ;*goto {reexecute=0 rethrow=0 return_oop=0}
                                                            ; - Test::test6@20 (line 97)
                                                            ;   {poll}
  0x00007fb9f8b2c2c9:   add    $0x10,%rsp
  0x00007fb9f8b2c2cd:   pop    %rbp
  0x00007fb9f8b2c2ce:   cmp    0x3b8(%r15),%rsp             ;   {poll_return}
  0x00007fb9f8b2c2d5:   ja     0x00007fb9f8b2c2dc
  0x00007fb9f8b2c2db:   retq

I propose to add sparse conditional constant propagation early in optimization pass. sccp optimistically assumes that all SSA values are initially Top and then propagates constant facts only along reachable control flow paths. In this way, sccp can discover optimization opportunities that cannot be found by just applying constant folding and constant propagation and dead code elimination separately. sccp uses three level lattice for SSA value, each value is evaluated at most twice due to lower, resulting in a fast convergence speed of the algorithm. I have prepared a preliminary POC for it. I believe many duplicate or case-oriented phases can be cleaned up after applying this optimization. Do you think the go language community would welcome such capability? Thanks for your comments.

The text was updated successfully, but these errors were encountered:

mknyszek · 2023-04-03T14:54:50Z

Which version of the Go toolchain are you using?

mknyszek · 2023-04-03T14:55:05Z

CC @golang/compiler

thanm · 2023-04-03T15:02:20Z

It would be nice if you could benchmark your new optimization to see what the performance impacts are, similarly what the cost is in terms of compile time. Thanks.

dr2chase · 2023-04-03T19:15:38Z

For what it's worth, I am running a quick (bent) benchmark on this, will certainly be done by tomorrow AM.

y1yang0 · 2023-04-04T01:24:07Z

Which version of the Go toolchain are you using?

This can be observed in the latest build.

It would be nice if you could benchmark your new optimization to see what the performance impacts are, similarly what the cost is in terms of compile time.

For what it's worth, I am running a quick (bent) benchmark on this,

Sorry but the preliminary POC is incomplete, it does data flow analysis only, it did not utilize the collected constant facts for further optimization, and the analysis process was also incomplete. Specifically, it only targeted a few nodes such as OpAdd64 and OpLess64 and BlockDefer is omitted at present. I will implement the missing parts later and provide both runtime/compile benchmark results in new CL.

sparse conditional constant propagation can discover optimization opportunities that cannot be found by just combining constant folding and constant propagation and dead code elimination separately. Updates golang#59399

gopherbot · 2023-04-12T14:04:28Z

Change https://go.dev/cl/483875 mentions this issue: cmd/compile: sparse conditional constant propagation

merykitty · 2023-04-13T04:09:26Z

Because it only discovers the constant, the loop itself still exists. We need to identify and remove empty counted loops in loopopts.

This loop is

for done := 0; done != 1; done = 1 {}

Which does not seem to be a counted loop, I don't see an easy way to eliminate it without actually peeling the loop.

I think you may want to rerun the benchmarks on Linux as they seem so different in results from other platforms while the opt is platform-independent.

sparse conditional constant propagation can discover optimization opportunities that cannot be found by just combining constant folding and constant propagation and dead code elimination separately. Updates golang#59399

sparse conditional constant propagation can discover optimization opportunities that cannot be found by just combining constant folding and constant propagation and dead code elimination separately. Updates #59399 Change-Id: Ia954e906480654a6f0cc065d75b5912f96f36b2e GitHub-Last-Rev: 90fc02d GitHub-Pull-Request: #59575 Reviewed-on: https://go-review.googlesource.com/c/go/+/483875 Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Michael Pratt <mpratt@google.com> Run-TryBot: Keith Randall <khr@golang.org>

sparse conditional constant propagation can discover optimization opportunities that cannot be found by just combining constant folding and constant propagation and dead code elimination separately. Updates golang#59399

sparse conditional constant propagation can discover optimization opportunities that cannot be found by just combining constant folding and constant propagation and dead code elimination separately. This is a re-submit of PR#59575, which fix a broken dominance relationship caught by ssacheck Updates #59399 Change-Id: I57482dee38f8e80a610aed4f64295e60c38b7a47 GitHub-Last-Rev: 830016f GitHub-Pull-Request: #60469 Reviewed-on: https://go-review.googlesource.com/c/go/+/498795 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Heschi Kreinick <heschi@google.com> Reviewed-by: Keith Randall <khr@golang.org>

mknyszek · 2023-09-20T20:27:11Z

Closed this because in triage it seemed like there was nothing left to do here. Please comment if you disagree. Thanks!

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Apr 3, 2023

mknyszek added the Performance label Apr 3, 2023

mknyszek added this to the Backlog milestone Apr 3, 2023

mknyszek added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. labels Apr 3, 2023

y1yang0 mentioned this issue Apr 12, 2023

cmd/compile: sparse conditional constant propagation #59575

Closed

y1yang0 mentioned this issue May 27, 2023

cmd/compile: sparse conditional constant propagation #60469

Closed

thanm mentioned this issue May 30, 2023

Go compiler and runtime meeting notes #43930

Open

seankhliao removed the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Sep 18, 2023

mauri870 mentioned this issue Sep 19, 2023

cmd/compile: miscompilation of simple arithmetic program targeting darwin/arm64 #62723

Closed

mknyszek closed this as completed Sep 20, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: suboptimal constant propagation #59399

cmd/compile: suboptimal constant propagation #59399

y1yang0 commented Apr 3, 2023 •

edited

mknyszek commented Apr 3, 2023

mknyszek commented Apr 3, 2023

thanm commented Apr 3, 2023

dr2chase commented Apr 3, 2023

y1yang0 commented Apr 4, 2023 •

edited

gopherbot commented Apr 12, 2023

merykitty commented Apr 13, 2023

mknyszek commented Sep 20, 2023

cmd/compile: suboptimal constant propagation #59399

cmd/compile: suboptimal constant propagation #59399

Comments

y1yang0 commented Apr 3, 2023 • edited

mknyszek commented Apr 3, 2023

mknyszek commented Apr 3, 2023

thanm commented Apr 3, 2023

dr2chase commented Apr 3, 2023

y1yang0 commented Apr 4, 2023 • edited

gopherbot commented Apr 12, 2023

merykitty commented Apr 13, 2023

mknyszek commented Sep 20, 2023

y1yang0 commented Apr 3, 2023 •

edited

y1yang0 commented Apr 4, 2023 •

edited