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

Comments

@JAicewizard
Copy link

@JAicewizard JAicewizard commented Sep 6, 2021

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

@JAicewizard JAicewizard commented Sep 12, 2021

@JAicewizard
Copy link
Author

@JAicewizard JAicewizard commented Sep 12, 2021

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants