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: possible prove pass bug #67625

Open
randall77 opened this issue May 23, 2024 · 4 comments
Open

cmd/compile: possible prove pass bug #67625

randall77 opened this issue May 23, 2024 · 4 comments
Assignees
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.
Milestone

Comments

@randall77
Copy link
Contributor

randall77 commented May 23, 2024

func gcd(a, b uint32) uint32 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

This doesn't actually compile to incorrect code yet, but it gets close.

The crux of the problem is that we have the rule that, given r := a%b, we can derive r < b (in the unsigned domain). Which at first looks reasonable. But reading it "backwards" causes trouble: r < b => b > r => b > 0 => b != 0. But that's the loop condition, implying that we don't actually need to do the loop test.

The implication above can only really be relied upon after the modulo operation runs (and thus panics, if b==0). Fortunately for us that's how the current compiler happens to use this information. But it isn't scoped to "after" in the current prove pass, so it is something of a ticking time bomb.

Filing for my own use for later. I'm rewriting some of this code.

@randall77 randall77 added this to the Go1.24 milestone May 23, 2024
@randall77 randall77 self-assigned this May 23, 2024
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label May 23, 2024
@Jorropo
Copy link
Member

Jorropo commented May 24, 2024

But it isn't scoped to "after" in the current prove pass, so it is something of a ticking time bomb.

I'm missing why this is a problem, the front-end generate zero-checks branches proving b:

func gcd(a, b uint32) uint32 {
	for b != 0 {
		if b == 0 { runtime.panicdivide() }
		// at this point we already proved b != 0
		a, b = b, a%b
	}
	return a
}

When I wrote that code I assumed it was UB to call Mod(64|32|16|8)u with a zero divisor and should be impossible unless there is a frontend bug.

But that's the loop condition, implying that we don't actually need to do the loop test.

Isn't the loop condition r != 0 ?
image

if (Phi .Entry(b) .Loop(b_r)) != 0 { goto .Loop }

What am I missing here ?

@randall77
Copy link
Contributor Author

I think the missing piece is that the rule that says r < b (which implies b != 0) applies across the entire function. Including before the loop even starts. So the fact that the loop condition even gets tested, instead of just assumed always true, is just an accident of missed optimization.

@Jorropo
Copy link
Member

Jorropo commented May 24, 2024

Hum, I wasn't aware it could backprop inferences like this, I thought this would only be applied during DFS.
This looks like this needs to ran during the scan stage while doing DFS instead of ahead. Are you gonna send a fix ?

@randall77
Copy link
Contributor Author

Yes, I think the right fix is to apply/remove it during DFS, at the point of the modulo (or maybe the block after? I'm not sure).
I think the first step though is to actually find a program that fails because of this. I ran into it after doing some pretty extensive modifications, so I'm not sure if it is actually triggerable currently.

I plan on revamping much of this pass for 1.24, so if there isn't a demonstrable bug, it can just wait and may become obsolete.

@mknyszek mknyszek added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label May 29, 2024
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.
Projects
Status: In Progress
Development

No branches or pull requests

4 participants