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
mariecurried opened this issue Jan 22, 2019 · 25 comments
Open

cmd/compile: unnecessary bounds check #29872

mariecurried opened this issue Jan 22, 2019 · 25 comments
Labels
help wanted NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@mariecurried
Copy link

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

Please use the issue template.

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

@bradfitz bradfitz added the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Jan 22, 2019
@bradfitz
Copy link
Contributor

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

@bradfitz bradfitz added Performance help wanted NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. labels Jan 22, 2019
@bradfitz bradfitz added this to the Go1.13 milestone Jan 22, 2019
@mariecurried
Copy link
Author

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

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

@josharian
Copy link
Contributor

cc @rasky

@cuonglm
Copy link
Member

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

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

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

cc also @zdjones

@cuonglm
Copy link
Member

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

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

@cuonglm
Copy link
Member

cuonglm 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
Copy link
Member

cuonglm commented Apr 5, 2019

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

@cuonglm
Copy link
Member

cuonglm commented Apr 5, 2019

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

@randall77
Copy link
Contributor

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

cuonglm commented Apr 22, 2019

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

@randall77
Copy link
Contributor

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

@cuonglm
Copy link
Member

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

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

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

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

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

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

josharian 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
Copy link
Member

cuonglm 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted 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

8 participants