Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: suboptimal constant propagation #59399

Closed
y1yang0 opened this issue Apr 3, 2023 · 8 comments
Closed

cmd/compile: suboptimal constant propagation #59399

y1yang0 opened this issue Apr 3, 2023 · 8 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@y1yang0
Copy link
Contributor

y1yang0 commented Apr 3, 2023

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.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Apr 3, 2023
@mknyszek mknyszek added this to the Backlog milestone Apr 3, 2023
@mknyszek
Copy link
Contributor

mknyszek commented Apr 3, 2023

Which version of the Go toolchain are you using?

@mknyszek
Copy link
Contributor

mknyszek commented Apr 3, 2023

CC @golang/compiler

@mknyszek 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
@thanm
Copy link
Contributor

thanm commented Apr 3, 2023

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
Copy link
Contributor

dr2chase commented Apr 3, 2023

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

@y1yang0
Copy link
Contributor Author

y1yang0 commented Apr 4, 2023

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.

y1yang0 added a commit to y1yang0/go that referenced this issue Apr 11, 2023
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
y1yang0 added a commit to y1yang0/go that referenced this issue Apr 12, 2023
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
y1yang0 added a commit to y1yang0/go that referenced this issue Apr 12, 2023
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
Copy link
Contributor

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

@merykitty
Copy link

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.

y1yang0 added a commit to y1yang0/go that referenced this issue May 18, 2023
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 pushed a commit that referenced this issue May 24, 2023
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>
y1yang0 added a commit to y1yang0/go that referenced this issue May 27, 2023
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
y1yang0 added a commit to y1yang0/go that referenced this issue Aug 31, 2023
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 pushed a commit that referenced this issue Sep 12, 2023
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>
@seankhliao seankhliao removed the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Sep 18, 2023
@mknyszek
Copy link
Contributor

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Development

No branches or pull requests

7 participants