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: unnecessary bounds check #29872

Open
marigonzes opened this issue Jan 22, 2019 · 25 comments

Comments

@marigonzes
Copy link

commented Jan 22, 2019

What did you do?

I compiled the following program to see its assembly code: https://godbolt.org/z/OcRvPE

What did you expect to see?

I expected the access to the slice to not be bounds checked

What did you see instead?

A bounds check was generated by the Go compiler

@bradfitz

This comment has been minimized.

Copy link
Member

commented Jan 22, 2019

Please use the issue template.

You don't specify what version of Go, for one, or which compiler.

@bradfitz

This comment has been minimized.

Copy link
Member

commented Jan 22, 2019

Oh, I see your link goes to a site where "gc (tip)" is selected. But it's faster for us if you put all the relevant information in the bug. And conventionally we share play.golang.org code snippets. But in this case you can just inline the code:

package test

func test(slc []byte, i uint) {
	if len(slc) >= 3 {
		_ = slc[i%3]
	}
}

/cc @randall77 @aclements

@marigonzes

This comment has been minimized.

Copy link
Author

commented Jan 22, 2019

Sorry, @bradfitz. I just assumed that you were familiar with Godbolt and, as you found out, the version is displayed there. But I'll take note for future reference.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Jan 22, 2019

I think this would just involve adding a new case for unsigned remainder to the prove pass.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Jan 22, 2019

cc @rasky

@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 4, 2019

@randall77 Where should I look at in the source to fix this?

I see the current behavior convert the Mod64u to a Sub64, so prove failed.

If I assigned i = <any non negative number> before if, prove success, as it sees Const64.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Apr 4, 2019

True, that makes it trickier. We'd either have to recognize the results of the div->mul lowering (generic.rules:1161), or push the div->mul lowering later. Both seem challenging.

@rasky

This comment has been minimized.

Copy link
Member

commented Apr 4, 2019

Maybe we should split div reduction out of generic into its own pass that runs late. It sounds something that later passes aren't dependent upon, and it tends to make code harder to analyze for everybody.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Apr 4, 2019

cc also @zdjones

@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 5, 2019

@randall77 @rasky how to make new rules applied?

I tried removing rule at line 1161, rebuild, then run ssa dump, Mod64u is still converted to Sub64 ... If it were not I did it wrong, then there's something hidden beside that rule.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Apr 5, 2019

@cuonglm : You need to regenerate the Go code from the rules.
See the README in src/cmd/compile/internal/ssa/gen/README.

@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 5, 2019

@randall77 yes, I re-gererated already, forgot to mention that. git diff show that the rule was removed.

git diff
diff --git a/src/cmd/compile/internal/ssa/gen/generic.rules b/src/cmd/compile/internal/ssa/gen/generic.rules
index aac7438e0a..921ed67b44 100644
--- a/src/cmd/compile/internal/ssa/gen/generic.rules
+++ b/src/cmd/compile/internal/ssa/gen/generic.rules
@@ -1158,8 +1158,6 @@
   -> (Sub16 x (Mul16 <t> (Div16u <t> x (Const16 <t> [c])) (Const16 <t> [c])))
 (Mod32u <t> x (Const32 [c])) && x.Op != OpConst32 && c > 0 && umagicOK(32,c)
   -> (Sub32 x (Mul32 <t> (Div32u <t> x (Const32 <t> [c])) (Const32 <t> [c])))
-(Mod64u <t> x (Const64 [c])) && x.Op != OpConst64 && c > 0 && umagicOK(64,c)
-  -> (Sub64 x (Mul64 <t> (Div64u <t> x (Const64 <t> [c])) (Const64 <t> [c])))
 
 (Eq(8|16|32|64)  s:(Sub(8|16|32|64) x y) (Const(8|16|32|64) [0])) && s.Uses == 1 -> (Eq(8|16|32|64)  x y)
 (Neq(8|16|32|64) s:(Sub(8|16|32|64) x y) (Const(8|16|32|64) [0])) && s.Uses == 1 -> (Neq(8|16|32|64) x y)
diff --git a/src/cmd/compile/internal/ssa/rewritegeneric.go b/src/cmd/compile/internal/ssa/rewritegeneric.go
index 7bb446cf35..9d505a6092 100644
--- a/src/cmd/compile/internal/ssa/rewritegeneric.go
+++ b/src/cmd/compile/internal/ssa/rewritegeneric.go
@@ -15381,36 +15381,6 @@ func rewriteValuegeneric_OpMod64u_0(v *Value) bool {
                v.AddArg(v0)
                return true
        }
-       // match: (Mod64u <t> x (Const64 [c]))
-       // cond: x.Op != OpConst64 && c > 0 && umagicOK(64,c)
-       // result: (Sub64 x (Mul64 <t> (Div64u <t> x (Const64 <t> [c])) (Const64 <t> [c])))
-       for {
-               t := v.Type
-               _ = v.Args[1]
-               x := v.Args[0]
-               v_1 := v.Args[1]
-               if v_1.Op != OpConst64 {
-                       break
-               }
-               c := v_1.AuxInt
-               if !(x.Op != OpConst64 && c > 0 && umagicOK(64, c)) {
-                       break
-               }
-               v.reset(OpSub64)
-               v.AddArg(x)
-               v0 := b.NewValue0(v.Pos, OpMul64, t)
-               v1 := b.NewValue0(v.Pos, OpDiv64u, t)
-               v1.AddArg(x)
-               v2 := b.NewValue0(v.Pos, OpConst64, t)
-               v2.AuxInt = c
-               v1.AddArg(v2)
-               v0.AddArg(v1)
-               v3 := b.NewValue0(v.Pos, OpConst64, t)
-               v3.AuxInt = c
-               v0.AddArg(v3)
-               v.AddArg(v0)
-               return true
-       }
        return false
 }
 func rewriteValuegeneric_OpMod8_0(v *Value) bool {
@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 5, 2019

@randall77 ah, nevermind, it's browser cache issue.

@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 5, 2019

@randall77 but even with that rule removed, bound check is still added.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Apr 5, 2019

Well, yes, with that rule removed, The Mod64U should now appear unmolested to the prove pass. You'd then need to add to the prove pass facts about the result of Mod64U.

@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

@randall77 so base on rasky's comment above, is it ok to split div reduction to its own pass?

@randall77

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

I'd rather not have a whole new pass just for div.
Can we move div reduction to be part of late opt?

@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

Can we move div reduction to be part of late opt?

I see opt and late opt use the same function opt. It seems to be hard without break current function signature, or using a global variable to toggle apply div reduction for it.

Also, for clarification, is IsInBounds will be applied in prove pass?

@randall77

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

I see opt and late opt use the same function opt. It seems to be hard without break current function signature, or using a global variable to toggle apply div reduction for it.

They use the same rule file, yes. But you can condition the rules on the pass. I thought we had an example of this already, but apparently not. I think just adding && v.Block.Func.pass.name == "..." would do it.

Also, for clarification, is IsInBounds will be applied in prove pass?

Yes, most of the bounds check removal happens in the prove pass.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

I thought we had an example of this already, but apparently not.

This is https://go-review.googlesource.com/c/go/+/129379, which is on hold because it was part of an effort to move some BCE from walk.go to SSA, and I never finished the project. I can dust off and complete that particular CL, though, if that would be helpful. Also, @bmkessler's modulus changes may do something similar. (https://go-review.googlesource.com/c/go/+/168037?)

@zdjones

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

I can dust off and complete that particular CL, though, if that would be helpful

@josharian I think your CL would leave the mod in place, then could the IsInBounds be removed with (no need for prove)?

(IsInBounds (Mod32u _ x) y) && x <= y -> (ConstBool [1])
(IsInBounds (Mod64u _ x) y) && x <= y -> (ConstBool [1])

Also, won't some of the other Mod rules still trigger whenever the constant is a power of two?
(Mod32u <t> n (Const32 [c])) && isPowerOfTwo(c&0xffffffff) -> (And32 n (Const32 <t> [(c&0xffffffff)-1]))
If those are also not needed by passes between opt and lateopt, they could also be skipped and then removed by the above rule? I'll try, but would love a sanity check first.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

Yes, some of the IsInBounds could be removed during the rewrite rules. I started on this in (e.g.) https://go-review.googlesource.com/c/go/+/129383 and https://go-review.googlesource.com/c/go/+/129380. You might also want something like https://go-review.googlesource.com/c/go/+/129384 so that you can easily add tests.

(At that point, you're well on your way to taking over my efforts to delete func bounded from walk.go, which I would be delighted by. See also the other CLs linked in the "Relation chain" from any of those CLs.)

Also, won't some of the other Mod rules still trigger whenever the constant is a power of two?

Yes, but boundedness and And are easy to reason about in a way that magic division is not; we should just add additional rules to remove IsInBounds based on bit masks. I believe some of the CLs linked above do some of that.

@zdjones

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

Yeah, when I first saw this issue, I started trying to reason my way back through the reduced mod...and abandoned that idea pretty quickly.

Is there any preference in using a rewrite rule vs the prove pass (i.e. due to differences in performance, complexity/maintenance, etc.)?

@josharian

This comment has been minimized.

Copy link
Contributor

commented Apr 22, 2019

IMO, for simple things adding them to the rewrite pass is preferable, since it provides the opportunity for other rewrite rules to keep working on the simplified form. And rules are pretty easy to read and maintain.

@cuonglm

This comment has been minimized.

Copy link
Contributor

commented Apr 23, 2019

@zdjones

I think your CL would leave the mod in place, then could the IsInBounds be removed with (no need for prove)?

I tried but the bounds check is still there. I think we have to add some thing to fact table, like @randall77 said in comment above.

@randall77 randall77 modified the milestones: Go1.13, Go1.14 Jun 4, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
7 participants
You can’t perform that action at this time.