SSA-backend rules / ordering

[shawn....@oracle.com]

Greetings,

I have a mystery I've been trying to figure out for a new Go SSA backend I'm working on.

Given these rules:

(Const64  [val]) -> (MOVDconst [val])
(Rsh64x64  x (MOVDconst [c])) && uint64(c) < 64 -> (SRAconst x [c])
(Rsh64x64 x y) -> (SRAmax x <y.Type> y [63])

This:

b2: <- b1 b4                                                                                 
v17 = Phi <int> v9 v33
...
b4: <- b2     
...
v80 = Const64 <int> [63]
...
v79 = Rsh64x64 <int> v17 v80
...

Becomes this:

v79 = SRAmax <int> [63] v17 v80

However, I expected:

v79 = SRAconst <int> [63] v17

I discovered that if I altered the rules (for Rsh64x64) to use Const64 directly, it then worked as expected:

(Const64  [val]) -> (MOVDconst [val])
(Rsh64x64  x (Const64 [c])) && uint64(c) < 64 -> (SRAconst x [c])
(Rsh64x64 x y) -> (SRAmax x <y.Type> y [63])

->

v79 = SRAconst <int> [63] v17

In what order are the generated rules evaluated?  Does the order matter?  Is there any documentation for writing an SSA backend other than the other backends (which are mostly uncommented)?

Thanks,
-Shawn

[Josh Bleecher Snyder]

Generates rules match initially by (outermost) op; within those, they
go by order in the .rules file. See the comments at the top of
cmd/compile/internal/ssa/gen/rulegen.go and
cmd/compile/internal/ssa/generic.rules. See also some discussion at
https://github.com/golang/go/issues/19013.

-josh

[Keith Randall]

I would encourage you not to rely on the ordering of application of rules.  This can sometimes mean using additional rules to make sure that ordering doesn't matter.

For your particular case, there's a simpler solution.  Don't write optimization rules using the machine-independent rules.  First lower the ops, then do optimizations on the lowered form.  In your case, I would do:

(Const64  [val]) -> (MOVDconst [val])

(Rsh64x64 x y) -> (SRAmax x <y.Type> y [63])

Then

(SRAmax [max]  x (MOVDconst [c])) && uint64(c) < uint64(max) -> (SRAconst x [c])

It might take multiple rewrites to get the final result, but there's no ordering issue.

--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Shawn Walker-Salas]

On 06/13/17 02:46 PM, Keith Randall wrote:
> I would encourage you not to rely on the ordering of application of
> rules. This can sometimes mean using additional rules to make sure that
> ordering doesn't matter.
>
> For your particular case, there's a simpler solution. Don't write
> optimization rules using the machine-independent rules. First lower the
> ops, then do optimizations on the lowered form. In your case, I would do:
>
> (Const64 [val]) -> (MOVDconst [val])
> (Rsh64x64 x y) -> (SRAmax x <y.Type> y [63])
>
> Then
>
> (SRAmax [max] x (MOVDconst [c])) && uint64(c) < uint64(max) ->
> (SRAconst x [c])
>
> It might take multiple rewrites to get the final result, but there's no
> ordering issue.

I was going by what ARM64 does:

(Rsh64x64 x (MOVDconst [c])) && uint64(c) < 64 -> (SRAconst x [c])

(Rsh64x64 x y) -> (SRA x (CSELULT <y.Type> y (Const64 <y.Type> [63])
(CMPconst [64] y)))

(Const64 [val]) -> (MOVDconst [val])

...and was puzzled as to why I got a very different result for the same
thing.

https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/gen/ARM64.rules

So what you say makes sense, but is still mysterious to me.

-Shawn

[Keith Randall]

ARM64 probably shouldn't do that.  I'm sure it exhibits the same behavior that you're seeing.

[Shawn Walker-Salas]

On 06/13/17 02:58 PM, Keith Randall wrote:
> ARM64 probably shouldn't do that. I'm sure it exhibits the same
> behavior that you're seeing.

It doesn't, which is why I was very puzzled :-)

I suspected ordering as a result of that, then was trying to figure out
how ordering was determined.

-Shawn

[Keith Randall]

See https://github.com/golang/go/issues/20663 .  On further inspection ARM64 always ends up working correctly.  But there is a circuitous rewrite path that gets us there.

[Shawn Walker-Salas]

On 06/13/17 03:08 PM, Keith Randall wrote:
> See https://github.com/golang/go/issues/20663 . On further inspection
> ARM64 always ends up working correctly. But there is a circuitous
> rewrite path that gets us there.

Now it makes sense.

Thanks,
-Shawn