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: optimize division for positive integers #36159

Closed
rillig opened this issue Dec 16, 2019 · 7 comments
Closed

cmd/compile: optimize division for positive integers #36159

rillig opened this issue Dec 16, 2019 · 7 comments

Comments

@rillig
Copy link
Contributor

@rillig rillig commented Dec 16, 2019

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

go version go1.13.1 windows/amd64

Does this issue reproduce with the latest release?

yes

What did you do?

func Indent(width int) string {
	const tabsAndSpaces = "\t\t\t\t\t\t\t\t\t       "
	middle := len(tabsAndSpaces) - 7
	if width >= 0 && width <= 8*middle+7 {
		start := middle - width/8
		end := middle + width%8
		return tabsAndSpaces[start:end]
	}
	return strings.Repeat("\t", width/8) + "       "[:width%8]
}

What did you expect to see?

Since the variable width has bounds checks and is thus guaranteed to be positive, the generated code omits the extra instructions for negative numbers.

In general, I prefer to write arithmetic expressions in my code instead of bit manipulations because the expressions width/8 and width%8 pair up nicely. In contrast, width>>3 and width&7 requires more thought.

What did you see instead?

  util.go:7   MOVQ BX, SI				
  util.go:7   SARQ $0x3f, BX				
  util.go:7   SHRQ $0x3d, BX				
  util.go:7   ADDQ SI, BX				
  util.go:7   SARQ $0x3, BX				
  util.go:8   MOVQ BX, DI				
  util.go:8   SHLQ $0x3, BX				
  util.go:8   SUBQ BX, SI				
  util.go:8   LEAQ 0x9(SI), CX			

The SARQ and SHRQ are not necessary here.

@randall77 randall77 added this to the Unplanned milestone Dec 16, 2019
@josharian
Copy link
Contributor

@josharian josharian commented Dec 16, 2019

@bmkessler
Copy link
Contributor

@bmkessler bmkessler commented Dec 20, 2019

This looks to be a limitation with prove results not being available to rewrite rules, since there are rewrite rules to handle this case:

(Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c)            -> (Rsh64Ux64 n (Const64 <typ.UInt64> [log2(c)]))
(Mod64 <t> n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c)            -> (And64 n (Const64 <t> [c-1]))

But the implementation of isNonNegative really only handles constants and a few special operations like len/cap.

// isNonNegative reports whether v is known to be greater or equal to zero.
func isNonNegative(v *Value) bool {
	switch v.Op {
	case OpConst64:
		return v.AuxInt >= 0

	case OpConst32:
		return int32(v.AuxInt) >= 0

	case OpStringLen, OpSliceLen, OpSliceCap,
		OpZeroExt8to64, OpZeroExt16to64, OpZeroExt32to64:
		return true

	case OpRsh64Ux64:
		by := v.Args[1]
		return by.Op == OpConst64 && by.AuxInt > 0

	case OpRsh64x64:
		return isNonNegative(v.Args[0])
	}
	return false
}

The division could be handled if the factsTable version of isNonNegative were available.

// isNonNegative reports whether v is known to be non-negative.
func (ft *factsTable) isNonNegative(v *Value) bool

Unfortunately, the first opt pass happens before prove even has a chance to deduce the numerator is non-negative, so the generic rule has already fired.

// Signed divide by power of 2.
// n / c =       n >> log(c) if n >= 0
//       = (n+c-1) >> log(c) if n < 0
// We conditionally add c-1 by adding n>>63>>(64-log(c)) (first shift signed, second shift unsigned).
(Div64 <t> n (Const64 [c])) && isPowerOfTwo(c) ->
  (Rsh64x64
    (Add64 <t> n (Rsh64Ux64 <t> (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) (Const64 <typ.UInt64> [64-log2(c)])))
    (Const64 <typ.UInt64> [log2(c)]))

Currently, the prove pass only removes redundant BlockIf branches, but I don't see any reason why it shouldn't be able to make other simplifications as well. In this case, it could use the knowledge that ft.isNonNegative(n) to simplify (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) -> 0 and equivalent for 32/16/8, that should eliminate all the unnecessary division fixups for constant division I believe after late opt does some further simplification. Note that there are other closely related rewrites that would be available to prove such as zeroing right shifts of known to be small numbers, (RshU64x64 n [c]) is 0 whenever 0 <= n < 1<<c.

@gopherbot
Copy link

@gopherbot gopherbot commented Dec 20, 2019

Change https://golang.org/cl/212277 mentions this issue: cmd/compile: in prove, zero right shifts of positive int by #bits - 1

@zdjones
Copy link
Contributor

@zdjones zdjones commented Dec 20, 2019

I beleive the CL above fixes this issue.

@zdjones
Copy link
Contributor

@zdjones zdjones commented Jan 24, 2020

using ft.isNonNegative(n) to simplify (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) -> 0

(Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) && ft.isNonNegative(n) -> 0
Is that just a specific instance of the more general calse you've listed later?

(RshU64x64 n [c]) && 0 <= n < 1<<c -> 0

@bmkessler
Copy link
Contributor

@bmkessler bmkessler commented Feb 25, 2020

Yes, that is just a special case where all positive int64 are automatically less than 1<<63, so the second condition is not needed.

@gopherbot
Copy link

@gopherbot gopherbot commented May 7, 2020

Change https://golang.org/cl/232857 mentions this issue: cmd/compile: in prove, zero right shifts of positive int by #bits - 1

@gopherbot gopherbot closed this in 2cb10d4 May 11, 2020
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
7 participants
You can’t perform that action at this time.