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

Jump to bottom

cmd/compile: unnecessary shift-check #48213

Open
JAicewizard opened this issue Sep 6, 2021 · 2 comments
Open

cmd/compile: unnecessary shift-check #48213

JAicewizard opened this issue Sep 6, 2021 · 2 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
Unplanned

Comments

@JAicewizard
Copy link

What version of Go are you using (go version)?

$ go version
1.17.0

Does this issue reproduce with the latest release?

yes

What did you do?

See https://go.godbolt.org/z/o5PqscasE for code.
On line 11/12 panics when endreg, is bigger than 29.
On line 15 it is checked that h is negative.
On line 16 there is a branch that panics on negative -h.

This might make sense if h could be -128, but it cant because of the check on line 11.

What did you expect to see?

I expected the go compiler to combine these checks and to avoid the extra branch+2 instructions.

What did you see instead?

Out of the assembly I gather that the go compiler fails to link line 15 with 16.
The gc also check the same thing twice, it also fails to see that h < 0 is the same as -h >= 0.

https://go.godbolt.org/z/hsMnMa1W1 does what I expect, and the gc manages to proof that -h is less than 0x1f, but more importantly also that -h is non-negative.
@ALTree ALTree added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance labels Sep 6, 2021
@ALTree ALTree added this to the Unplanned milestone Sep 6, 2021
@ALTree ALTree changed the title cmd/compile: unnecesary shift-check cmd/compile: unnecessary shift-check Sep 6, 2021
@JAicewizard
Copy link
Author

another example:
https://godbolt.org/z/Ge9887jEr

@JAicewizard
Copy link
Author

Ive been investigating this second example.

Posit32es2.Int64 method(Posit32es2) func() int64
  b1:
    v1 = InitMem <mem>
    v6 = Arg <Posit32es2> {a} (a[Posit32es2])
    v8 = Const64 <int64> [0]
    v9 = StructSelect <uint32> [0] v6
    v10 = Const64 <uint> [2]
    v11 = Lsh32x64 <uint32> [false] v9 v10
    v12 = Const32 <uint32> [-2147483648]
    v13 = Or32 <uint32> v11 v12 (afracP1[uint32])
    v16 = Const32 <int32> [0]
    v17 = Less32 <bool> v9 v16
    v26 = Const32 <int32> [-1]
    If v17 -> b3 b2
  b2: <- b1
    v31 = MakeResult <int64,mem> v8 v1
    Ret v31
  b3: <- b1
    v19 = Neg32 <int32> v9
    v21 = Add32 <int32> v26 v19 (sft[int32])
    v23 = Leq32 <bool> v16 v21
    If v23 -> b4 b5 (likely)
  b4: <- b3
    v27 = Rsh32Ux32 <uint32> [false] v13 v21 (ret[uint32])
    v28 = ZeroExt32to64 <int64> v27
    v29 = MakeResult <int64,mem> v28 v1
    Ret v29
  b5: <- b3
    v25 = StaticLECall <mem> {AuxCall{runtime.panicshift}} v1
    Exit v25

at b5 it has a proof tree as follows:

           extra
          /    \
        32      9
       /  \\  //  \
 {empty}   8/16   {empty}

It fails to utilize the intermediary values.

I added have a small patch that enables the compiler to add more data to the prove DAG, its very specific ATM but could be more general:
https://github.com/JAicewizard/go/tree/add_backwards_checks_ssa.

This adds checks in the SSA pass where if the first argument to a conditional is a 0 constant, and the second happens to be inverted from another variable that happened to already be compared to 0, it adds the knowlege that the inverted value it is </> than 0 (and only for 32 bits, and when its the 3rd block :P). This could be added for more constants, and in more advanced transformations.

I dont know how to actually run benchmarks in the gc, I get a bunch of "cannot access internal package" errors.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
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
Milestone
Unplanned
Development

No branches or pull requests
3 participants
@ALTree @gopherbot @JAicewizard