Text file src/cmd/compile/internal/ssa/_gen/generic.rules

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Simplifications that apply to all backend architectures. As an example, this
     6  // Go source code
     7  //
     8  // y := 0 * x
     9  //
    10  // can be translated into y := 0 without losing any information, which saves a
    11  // pointless multiplication instruction. Other .rules files in this directory
    12  // (for example AMD64.rules) contain rules specific to the architecture in the
    13  // filename. The rules here apply to every architecture.
    14  //
    15  // The code for parsing this file lives in rulegen.go; this file generates
    16  // ssa/rewritegeneric.go.
    17  
    18  // values are specified using the following format:
    19  // (op <type> [auxint] {aux} arg0 arg1 ...)
    20  // the type, aux, and auxint fields are optional
    21  // on the matching side
    22  //  - the type, aux, and auxint fields must match if they are specified.
    23  //  - the first occurrence of a variable defines that variable.  Subsequent
    24  //    uses must match (be == to) the first use.
    25  //  - v is defined to be the value matched.
    26  //  - an additional conditional can be provided after the match pattern with "&&".
    27  // on the generated side
    28  //  - the type of the top-level expression is the same as the one on the left-hand side.
    29  //  - the type of any subexpressions must be specified explicitly (or
    30  //    be specified in the op's type field).
    31  //  - auxint will be 0 if not specified.
    32  //  - aux will be nil if not specified.
    33  
    34  // blocks are specified using the following format:
    35  // (kind controlvalue succ0 succ1 ...)
    36  // controlvalue must be "nil" or a value expression
    37  // succ* fields must be variables
    38  // For now, the generated successors must be a permutation of the matched successors.
    39  
    40  // constant folding
    41  (Trunc16to8  (Const16  [c])) => (Const8   [int8(c)])
    42  (Trunc32to8  (Const32  [c])) => (Const8   [int8(c)])
    43  (Trunc32to16 (Const32  [c])) => (Const16  [int16(c)])
    44  (Trunc64to8  (Const64  [c])) => (Const8   [int8(c)])
    45  (Trunc64to16 (Const64  [c])) => (Const16  [int16(c)])
    46  (Trunc64to32 (Const64  [c])) => (Const32  [int32(c)])
    47  (Cvt64Fto32F (Const64F [c])) => (Const32F [float32(c)])
    48  (Cvt32Fto64F (Const32F [c])) => (Const64F [float64(c)])
    49  (Cvt32to32F  (Const32  [c])) => (Const32F [float32(c)])
    50  (Cvt32to64F  (Const32  [c])) => (Const64F [float64(c)])
    51  (Cvt64to32F  (Const64  [c])) => (Const32F [float32(c)])
    52  (Cvt64to64F  (Const64  [c])) => (Const64F [float64(c)])
    53  (Cvt32Fto32  (Const32F [c])) => (Const32  [int32(c)])
    54  (Cvt32Fto64  (Const32F [c])) => (Const64  [int64(c)])
    55  (Cvt64Fto32  (Const64F [c])) => (Const32  [int32(c)])
    56  (Cvt64Fto64  (Const64F [c])) => (Const64  [int64(c)])
    57  (Round32F x:(Const32F)) => x
    58  (Round64F x:(Const64F)) => x
    59  (CvtBoolToUint8 (ConstBool [false])) => (Const8 [0])
    60  (CvtBoolToUint8 (ConstBool [true])) => (Const8 [1])
    61  (BitLen64 (Const64 [c])) && config.PtrSize == 8 => (Const64 [int64(bits.Len64(uint64(c)))])
    62  (BitLen32 (Const32 [c])) && config.PtrSize == 8 => (Const64 [int64(bits.Len32(uint32(c)))])
    63  (BitLen16 (Const16 [c])) && config.PtrSize == 8 => (Const64 [int64(bits.Len16(uint16(c)))])
    64  (BitLen8  (Const8  [c])) && config.PtrSize == 8 => (Const64 [int64(bits.Len8(uint8(c)))])
    65  (BitLen64 (Const64 [c])) && config.PtrSize == 4 => (Const32 [int32(bits.Len64(uint64(c)))])
    66  (BitLen32 (Const32 [c])) && config.PtrSize == 4 => (Const32 [int32(bits.Len32(uint32(c)))])
    67  (BitLen16 (Const16 [c])) && config.PtrSize == 4 => (Const32 [int32(bits.Len16(uint16(c)))])
    68  (BitLen8  (Const8  [c])) && config.PtrSize == 4 => (Const32 [int32(bits.Len8(uint8(c)))])
    69  
    70  (Trunc16to8  (ZeroExt8to16  x)) => x
    71  (Trunc32to8  (ZeroExt8to32  x)) => x
    72  (Trunc32to16 (ZeroExt8to32  x)) => (ZeroExt8to16  x)
    73  (Trunc32to16 (ZeroExt16to32 x)) => x
    74  (Trunc64to8  (ZeroExt8to64  x)) => x
    75  (Trunc64to16 (ZeroExt8to64  x)) => (ZeroExt8to16  x)
    76  (Trunc64to16 (ZeroExt16to64 x)) => x
    77  (Trunc64to32 (ZeroExt8to64  x)) => (ZeroExt8to32  x)
    78  (Trunc64to32 (ZeroExt16to64 x)) => (ZeroExt16to32 x)
    79  (Trunc64to32 (ZeroExt32to64 x)) => x
    80  (Trunc16to8  (SignExt8to16  x)) => x
    81  (Trunc32to8  (SignExt8to32  x)) => x
    82  (Trunc32to16 (SignExt8to32  x)) => (SignExt8to16  x)
    83  (Trunc32to16 (SignExt16to32 x)) => x
    84  (Trunc64to8  (SignExt8to64  x)) => x
    85  (Trunc64to16 (SignExt8to64  x)) => (SignExt8to16  x)
    86  (Trunc64to16 (SignExt16to64 x)) => x
    87  (Trunc64to32 (SignExt8to64  x)) => (SignExt8to32  x)
    88  (Trunc64to32 (SignExt16to64 x)) => (SignExt16to32 x)
    89  (Trunc64to32 (SignExt32to64 x)) => x
    90  
    91  (ZeroExt8to16  (Const8  [c])) => (Const16 [int16( uint8(c))])
    92  (ZeroExt8to32  (Const8  [c])) => (Const32 [int32( uint8(c))])
    93  (ZeroExt8to64  (Const8  [c])) => (Const64 [int64( uint8(c))])
    94  (ZeroExt16to32 (Const16 [c])) => (Const32 [int32(uint16(c))])
    95  (ZeroExt16to64 (Const16 [c])) => (Const64 [int64(uint16(c))])
    96  (ZeroExt32to64 (Const32 [c])) => (Const64 [int64(uint32(c))])
    97  (SignExt8to16  (Const8  [c])) => (Const16 [int16(c)])
    98  (SignExt8to32  (Const8  [c])) => (Const32 [int32(c)])
    99  (SignExt8to64  (Const8  [c])) => (Const64 [int64(c)])
   100  (SignExt16to32 (Const16 [c])) => (Const32 [int32(c)])
   101  (SignExt16to64 (Const16 [c])) => (Const64 [int64(c)])
   102  (SignExt32to64 (Const32 [c])) => (Const64 [int64(c)])
   103  
   104  (Neg8   (Const8   [c])) => (Const8   [-c])
   105  (Neg16  (Const16  [c])) => (Const16  [-c])
   106  (Neg32  (Const32  [c])) => (Const32  [-c])
   107  (Neg64  (Const64  [c])) => (Const64  [-c])
   108  (Neg32F (Const32F [c])) && c != 0 => (Const32F [-c])
   109  (Neg64F (Const64F [c])) && c != 0 => (Const64F [-c])
   110  
   111  (Add8   (Const8 [c])   (Const8 [d]))   => (Const8  [c+d])
   112  (Add16  (Const16 [c])  (Const16 [d]))  => (Const16 [c+d])
   113  (Add32  (Const32 [c])  (Const32 [d]))  => (Const32 [c+d])
   114  (Add64  (Const64 [c])  (Const64 [d]))  => (Const64 [c+d])
   115  (Add32F (Const32F [c]) (Const32F [d])) && c+d == c+d => (Const32F [c+d])
   116  (Add64F (Const64F [c]) (Const64F [d])) && c+d == c+d => (Const64F [c+d])
   117  (AddPtr <t> x (Const64 [c])) => (OffPtr <t> x [c])
   118  (AddPtr <t> x (Const32 [c])) => (OffPtr <t> x [int64(c)])
   119  
   120  (Sub8   (Const8 [c]) (Const8 [d]))     => (Const8 [c-d])
   121  (Sub16  (Const16 [c]) (Const16 [d]))   => (Const16 [c-d])
   122  (Sub32  (Const32 [c]) (Const32 [d]))   => (Const32 [c-d])
   123  (Sub64  (Const64 [c]) (Const64 [d]))   => (Const64 [c-d])
   124  (Sub32F (Const32F [c]) (Const32F [d])) && c-d == c-d => (Const32F [c-d])
   125  (Sub64F (Const64F [c]) (Const64F [d])) && c-d == c-d => (Const64F [c-d])
   126  
   127  (Mul8   (Const8 [c])   (Const8 [d]))   => (Const8  [c*d])
   128  (Mul16  (Const16 [c])  (Const16 [d]))  => (Const16 [c*d])
   129  (Mul32  (Const32 [c])  (Const32 [d]))  => (Const32 [c*d])
   130  (Mul64  (Const64 [c])  (Const64 [d]))  => (Const64 [c*d])
   131  (Mul32F (Const32F [c]) (Const32F [d])) && c*d == c*d => (Const32F [c*d])
   132  (Mul64F (Const64F [c]) (Const64F [d])) && c*d == c*d => (Const64F [c*d])
   133  
   134  (And8   (Const8 [c])   (Const8 [d]))   => (Const8  [c&d])
   135  (And16  (Const16 [c])  (Const16 [d]))  => (Const16 [c&d])
   136  (And32  (Const32 [c])  (Const32 [d]))  => (Const32 [c&d])
   137  (And64  (Const64 [c])  (Const64 [d]))  => (Const64 [c&d])
   138  
   139  (Or8   (Const8 [c])   (Const8 [d]))   => (Const8  [c|d])
   140  (Or16  (Const16 [c])  (Const16 [d]))  => (Const16 [c|d])
   141  (Or32  (Const32 [c])  (Const32 [d]))  => (Const32 [c|d])
   142  (Or64  (Const64 [c])  (Const64 [d]))  => (Const64 [c|d])
   143  
   144  (Xor8   (Const8 [c])   (Const8 [d]))   => (Const8  [c^d])
   145  (Xor16  (Const16 [c])  (Const16 [d]))  => (Const16 [c^d])
   146  (Xor32  (Const32 [c])  (Const32 [d]))  => (Const32 [c^d])
   147  (Xor64  (Const64 [c])  (Const64 [d]))  => (Const64 [c^d])
   148  
   149  (Ctz64 (Const64 [c])) && config.PtrSize == 4 => (Const32 [int32(ntz64(c))])
   150  (Ctz32 (Const32 [c])) && config.PtrSize == 4 => (Const32 [int32(ntz32(c))])
   151  (Ctz16 (Const16 [c])) && config.PtrSize == 4 => (Const32 [int32(ntz16(c))])
   152  (Ctz8  (Const8  [c])) && config.PtrSize == 4 => (Const32 [int32(ntz8(c))])
   153  
   154  (Ctz64 (Const64 [c])) && config.PtrSize == 8 => (Const64 [int64(ntz64(c))])
   155  (Ctz32 (Const32 [c])) && config.PtrSize == 8 => (Const64 [int64(ntz32(c))])
   156  (Ctz16 (Const16 [c])) && config.PtrSize == 8 => (Const64 [int64(ntz16(c))])
   157  (Ctz8  (Const8  [c])) && config.PtrSize == 8 => (Const64 [int64(ntz8(c))])
   158  
   159  (Div8   (Const8  [c])  (Const8  [d])) && d != 0 => (Const8  [c/d])
   160  (Div16  (Const16 [c])  (Const16 [d])) && d != 0 => (Const16 [c/d])
   161  (Div32  (Const32 [c])  (Const32 [d])) && d != 0 => (Const32 [c/d])
   162  (Div64  (Const64 [c])  (Const64 [d])) && d != 0 => (Const64 [c/d])
   163  (Div8u  (Const8  [c])  (Const8  [d])) && d != 0 => (Const8  [int8(uint8(c)/uint8(d))])
   164  (Div16u (Const16 [c])  (Const16 [d])) && d != 0 => (Const16 [int16(uint16(c)/uint16(d))])
   165  (Div32u (Const32 [c])  (Const32 [d])) && d != 0 => (Const32 [int32(uint32(c)/uint32(d))])
   166  (Div64u (Const64 [c])  (Const64 [d])) && d != 0 => (Const64 [int64(uint64(c)/uint64(d))])
   167  (Div32F (Const32F [c]) (Const32F [d])) && c/d == c/d => (Const32F [c/d])
   168  (Div64F (Const64F [c]) (Const64F [d])) && c/d == c/d => (Const64F [c/d])
   169  (Select0 (Div128u (Const64 [0]) lo y)) => (Div64u lo y)
   170  (Select1 (Div128u (Const64 [0]) lo y)) => (Mod64u lo y)
   171  
   172  (Not (ConstBool [c])) => (ConstBool [!c])
   173  
   174  (Floor       (Const64F [c])) => (Const64F [math.Floor(c)])
   175  (Ceil        (Const64F [c])) => (Const64F [math.Ceil(c)])
   176  (Trunc       (Const64F [c])) => (Const64F [math.Trunc(c)])
   177  (RoundToEven (Const64F [c])) => (Const64F [math.RoundToEven(c)])
   178  
   179  // Convert x * 1 to x.
   180  (Mul(8|16|32|64)  (Const(8|16|32|64)  [1]) x) => x
   181  (Select0 (Mul(32|64)uover (Const(32|64) [1]) x)) => x
   182  (Select1 (Mul(32|64)uover (Const(32|64) [1]) x)) => (ConstBool [false])
   183  
   184  // Convert x * -1 to -x.
   185  (Mul(8|16|32|64)  (Const(8|16|32|64)  [-1]) x) => (Neg(8|16|32|64)  x)
   186  
   187  // DeMorgan's Laws
   188  (And(8|16|32|64) <t> (Com(8|16|32|64) x) (Com(8|16|32|64) y)) => (Com(8|16|32|64) (Or(8|16|32|64) <t> x y))
   189  (Or(8|16|32|64) <t> (Com(8|16|32|64) x) (Com(8|16|32|64) y)) => (Com(8|16|32|64) (And(8|16|32|64) <t> x y))
   190  
   191  // Convert multiplication by a power of two to a shift.
   192  (Mul8  <t> n (Const8  [c])) && isPowerOfTwo(c) => (Lsh8x64  <t> n (Const64 <typ.UInt64> [log8(c)]))
   193  (Mul16 <t> n (Const16 [c])) && isPowerOfTwo(c) => (Lsh16x64 <t> n (Const64 <typ.UInt64> [log16(c)]))
   194  (Mul32 <t> n (Const32 [c])) && isPowerOfTwo(c) => (Lsh32x64 <t> n (Const64 <typ.UInt64> [log32(c)]))
   195  (Mul64 <t> n (Const64 [c])) && isPowerOfTwo(c) => (Lsh64x64 <t> n (Const64 <typ.UInt64> [log64(c)]))
   196  (Mul8  <t> n (Const8  [c])) && t.IsSigned() && isPowerOfTwo(-c) => (Neg8  (Lsh8x64  <t> n (Const64 <typ.UInt64> [log8(-c)])))
   197  (Mul16 <t> n (Const16 [c])) && t.IsSigned() && isPowerOfTwo(-c) => (Neg16 (Lsh16x64 <t> n (Const64 <typ.UInt64> [log16(-c)])))
   198  (Mul32 <t> n (Const32 [c])) && t.IsSigned() && isPowerOfTwo(-c) => (Neg32 (Lsh32x64 <t> n (Const64 <typ.UInt64> [log32(-c)])))
   199  (Mul64 <t> n (Const64 [c])) && t.IsSigned() && isPowerOfTwo(-c) => (Neg64 (Lsh64x64 <t> n (Const64 <typ.UInt64> [log64(-c)])))
   200  
   201  (Mod8  (Const8  [c]) (Const8  [d])) && d != 0 => (Const8  [c % d])
   202  (Mod16 (Const16 [c]) (Const16 [d])) && d != 0 => (Const16 [c % d])
   203  (Mod32 (Const32 [c]) (Const32 [d])) && d != 0 => (Const32 [c % d])
   204  (Mod64 (Const64 [c]) (Const64 [d])) && d != 0 => (Const64 [c % d])
   205  
   206  (Mod8u  (Const8 [c])  (Const8  [d])) && d != 0 => (Const8  [int8(uint8(c) % uint8(d))])
   207  (Mod16u (Const16 [c]) (Const16 [d])) && d != 0 => (Const16 [int16(uint16(c) % uint16(d))])
   208  (Mod32u (Const32 [c]) (Const32 [d])) && d != 0 => (Const32 [int32(uint32(c) % uint32(d))])
   209  (Mod64u (Const64 [c]) (Const64 [d])) && d != 0 => (Const64 [int64(uint64(c) % uint64(d))])
   210  
   211  (Lsh64x64  (Const64 [c]) (Const64 [d])) => (Const64 [c << uint64(d)])
   212  (Rsh64x64  (Const64 [c]) (Const64 [d])) => (Const64 [c >> uint64(d)])
   213  (Rsh64Ux64 (Const64 [c]) (Const64 [d])) => (Const64 [int64(uint64(c) >> uint64(d))])
   214  (Lsh32x64  (Const32 [c]) (Const64 [d])) => (Const32 [c << uint64(d)])
   215  (Rsh32x64  (Const32 [c]) (Const64 [d])) => (Const32 [c >> uint64(d)])
   216  (Rsh32Ux64 (Const32 [c]) (Const64 [d])) => (Const32 [int32(uint32(c) >> uint64(d))])
   217  (Lsh16x64  (Const16 [c]) (Const64 [d])) => (Const16 [c << uint64(d)])
   218  (Rsh16x64  (Const16 [c]) (Const64 [d])) => (Const16 [c >> uint64(d)])
   219  (Rsh16Ux64 (Const16 [c]) (Const64 [d])) => (Const16 [int16(uint16(c) >> uint64(d))])
   220  (Lsh8x64   (Const8  [c]) (Const64 [d])) => (Const8  [c << uint64(d)])
   221  (Rsh8x64   (Const8  [c]) (Const64 [d])) => (Const8  [c >> uint64(d)])
   222  (Rsh8Ux64  (Const8  [c]) (Const64 [d])) => (Const8  [int8(uint8(c) >> uint64(d))])
   223  
   224  // Fold IsInBounds when the range of the index cannot exceed the limit.
   225  (IsInBounds (ZeroExt8to32  _) (Const32 [c])) && (1 << 8)  <= c => (ConstBool [true])
   226  (IsInBounds (ZeroExt8to64  _) (Const64 [c])) && (1 << 8)  <= c => (ConstBool [true])
   227  (IsInBounds (ZeroExt16to32 _) (Const32 [c])) && (1 << 16) <= c => (ConstBool [true])
   228  (IsInBounds (ZeroExt16to64 _) (Const64 [c])) && (1 << 16) <= c => (ConstBool [true])
   229  (IsInBounds x x) => (ConstBool [false])
   230  (IsInBounds                (And8  (Const8  [c]) _)  (Const8  [d])) && 0 <= c && c < d => (ConstBool [true])
   231  (IsInBounds (ZeroExt8to16  (And8  (Const8  [c]) _)) (Const16 [d])) && 0 <= c && int16(c) < d => (ConstBool [true])
   232  (IsInBounds (ZeroExt8to32  (And8  (Const8  [c]) _)) (Const32 [d])) && 0 <= c && int32(c) < d => (ConstBool [true])
   233  (IsInBounds (ZeroExt8to64  (And8  (Const8  [c]) _)) (Const64 [d])) && 0 <= c && int64(c) < d => (ConstBool [true])
   234  (IsInBounds                (And16 (Const16 [c]) _)  (Const16 [d])) && 0 <= c && c < d => (ConstBool [true])
   235  (IsInBounds (ZeroExt16to32 (And16 (Const16 [c]) _)) (Const32 [d])) && 0 <= c && int32(c) < d => (ConstBool [true])
   236  (IsInBounds (ZeroExt16to64 (And16 (Const16 [c]) _)) (Const64 [d])) && 0 <= c && int64(c) < d => (ConstBool [true])
   237  (IsInBounds                (And32 (Const32 [c]) _)  (Const32 [d])) && 0 <= c && c < d => (ConstBool [true])
   238  (IsInBounds (ZeroExt32to64 (And32 (Const32 [c]) _)) (Const64 [d])) && 0 <= c && int64(c) < d => (ConstBool [true])
   239  (IsInBounds                (And64 (Const64 [c]) _)  (Const64 [d])) && 0 <= c && c < d => (ConstBool [true])
   240  (IsInBounds (Const32 [c]) (Const32 [d])) => (ConstBool [0 <= c && c < d])
   241  (IsInBounds (Const64 [c]) (Const64 [d])) => (ConstBool [0 <= c && c < d])
   242  // (Mod64u x y) is always between 0 (inclusive) and y (exclusive).
   243  (IsInBounds (Mod32u _ y) y) => (ConstBool [true])
   244  (IsInBounds (Mod64u _ y) y) => (ConstBool [true])
   245  // Right shifting an unsigned number limits its value.
   246  (IsInBounds (ZeroExt8to64  (Rsh8Ux64  _ (Const64 [c]))) (Const64 [d])) && 0 < c && c <  8 && 1<<uint( 8-c)-1 < d => (ConstBool [true])
   247  (IsInBounds (ZeroExt8to32  (Rsh8Ux64  _ (Const64 [c]))) (Const32 [d])) && 0 < c && c <  8 && 1<<uint( 8-c)-1 < d => (ConstBool [true])
   248  (IsInBounds (ZeroExt8to16  (Rsh8Ux64  _ (Const64 [c]))) (Const16 [d])) && 0 < c && c <  8 && 1<<uint( 8-c)-1 < d => (ConstBool [true])
   249  (IsInBounds                (Rsh8Ux64  _ (Const64 [c]))  (Const64 [d])) && 0 < c && c <  8 && 1<<uint( 8-c)-1 < d => (ConstBool [true])
   250  (IsInBounds (ZeroExt16to64 (Rsh16Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 < c && c < 16 && 1<<uint(16-c)-1 < d => (ConstBool [true])
   251  (IsInBounds (ZeroExt16to32 (Rsh16Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 < c && c < 16 && 1<<uint(16-c)-1 < d => (ConstBool [true])
   252  (IsInBounds                (Rsh16Ux64 _ (Const64 [c]))  (Const64 [d])) && 0 < c && c < 16 && 1<<uint(16-c)-1 < d => (ConstBool [true])
   253  (IsInBounds (ZeroExt32to64 (Rsh32Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 < c && c < 32 && 1<<uint(32-c)-1 < d => (ConstBool [true])
   254  (IsInBounds                (Rsh32Ux64 _ (Const64 [c]))  (Const64 [d])) && 0 < c && c < 32 && 1<<uint(32-c)-1 < d => (ConstBool [true])
   255  (IsInBounds                (Rsh64Ux64 _ (Const64 [c]))  (Const64 [d])) && 0 < c && c < 64 && 1<<uint(64-c)-1 < d => (ConstBool [true])
   256  
   257  (IsSliceInBounds x x) => (ConstBool [true])
   258  (IsSliceInBounds (And32 (Const32 [c]) _) (Const32 [d])) && 0 <= c && c <= d => (ConstBool [true])
   259  (IsSliceInBounds (And64 (Const64 [c]) _) (Const64 [d])) && 0 <= c && c <= d => (ConstBool [true])
   260  (IsSliceInBounds (Const32 [0]) _) => (ConstBool [true])
   261  (IsSliceInBounds (Const64 [0]) _) => (ConstBool [true])
   262  (IsSliceInBounds (Const32 [c]) (Const32 [d])) => (ConstBool [0 <= c && c <= d])
   263  (IsSliceInBounds (Const64 [c]) (Const64 [d])) => (ConstBool [0 <= c && c <= d])
   264  (IsSliceInBounds (SliceLen x) (SliceCap x)) => (ConstBool [true])
   265  
   266  (Eq(64|32|16|8) x x) => (ConstBool [true])
   267  (EqB (ConstBool [c]) (ConstBool [d])) => (ConstBool [c == d])
   268  (EqB (ConstBool [false]) x) => (Not x)
   269  (EqB (ConstBool [true]) x) => x
   270  
   271  (Neq(64|32|16|8) x x) => (ConstBool [false])
   272  (NeqB (ConstBool [c]) (ConstBool [d])) => (ConstBool [c != d])
   273  (NeqB (ConstBool [false]) x) => x
   274  (NeqB (ConstBool [true]) x) => (Not x)
   275  (NeqB (Not x) (Not y)) => (NeqB x y)
   276  
   277  (Eq64 (Const64 <t> [c]) (Add64 (Const64 <t> [d]) x)) => (Eq64 (Const64 <t> [c-d]) x)
   278  (Eq32 (Const32 <t> [c]) (Add32 (Const32 <t> [d]) x)) => (Eq32 (Const32 <t> [c-d]) x)
   279  (Eq16 (Const16 <t> [c]) (Add16 (Const16 <t> [d]) x)) => (Eq16 (Const16 <t> [c-d]) x)
   280  (Eq8  (Const8  <t> [c]) (Add8  (Const8  <t> [d]) x)) => (Eq8  (Const8  <t> [c-d]) x)
   281  
   282  (Neq64 (Const64 <t> [c]) (Add64 (Const64 <t> [d]) x)) => (Neq64 (Const64 <t> [c-d]) x)
   283  (Neq32 (Const32 <t> [c]) (Add32 (Const32 <t> [d]) x)) => (Neq32 (Const32 <t> [c-d]) x)
   284  (Neq16 (Const16 <t> [c]) (Add16 (Const16 <t> [d]) x)) => (Neq16 (Const16 <t> [c-d]) x)
   285  (Neq8  (Const8  <t> [c]) (Add8  (Const8  <t> [d]) x)) => (Neq8  (Const8  <t> [c-d]) x)
   286  
   287  // signed integer range: ( c <= x && x (<|<=) d ) -> ( unsigned(x-c) (<|<=) unsigned(d-c) )
   288  (AndB (Leq64 (Const64 [c]) x) ((Less|Leq)64 x (Const64 [d]))) && d >= c => ((Less|Leq)64U (Sub64 <x.Type> x (Const64 <x.Type> [c])) (Const64 <x.Type> [d-c]))
   289  (AndB (Leq32 (Const32 [c]) x) ((Less|Leq)32 x (Const32 [d]))) && d >= c => ((Less|Leq)32U (Sub32 <x.Type> x (Const32 <x.Type> [c])) (Const32 <x.Type> [d-c]))
   290  (AndB (Leq16 (Const16 [c]) x) ((Less|Leq)16 x (Const16 [d]))) && d >= c => ((Less|Leq)16U (Sub16 <x.Type> x (Const16 <x.Type> [c])) (Const16 <x.Type> [d-c]))
   291  (AndB (Leq8  (Const8  [c]) x) ((Less|Leq)8  x (Const8  [d]))) && d >= c => ((Less|Leq)8U  (Sub8  <x.Type> x (Const8  <x.Type> [c])) (Const8  <x.Type> [d-c]))
   292  
   293  // signed integer range: ( c < x && x (<|<=) d ) -> ( unsigned(x-(c+1)) (<|<=) unsigned(d-(c+1)) )
   294  (AndB (Less64 (Const64 [c]) x) ((Less|Leq)64 x (Const64 [d]))) && d >= c+1 && c+1 > c => ((Less|Leq)64U (Sub64 <x.Type> x (Const64 <x.Type> [c+1])) (Const64 <x.Type> [d-c-1]))
   295  (AndB (Less32 (Const32 [c]) x) ((Less|Leq)32 x (Const32 [d]))) && d >= c+1 && c+1 > c => ((Less|Leq)32U (Sub32 <x.Type> x (Const32 <x.Type> [c+1])) (Const32 <x.Type> [d-c-1]))
   296  (AndB (Less16 (Const16 [c]) x) ((Less|Leq)16 x (Const16 [d]))) && d >= c+1 && c+1 > c => ((Less|Leq)16U (Sub16 <x.Type> x (Const16 <x.Type> [c+1])) (Const16 <x.Type> [d-c-1]))
   297  (AndB (Less8  (Const8  [c]) x) ((Less|Leq)8  x (Const8  [d]))) && d >= c+1 && c+1 > c => ((Less|Leq)8U  (Sub8  <x.Type> x (Const8  <x.Type> [c+1])) (Const8  <x.Type> [d-c-1]))
   298  
   299  // unsigned integer range: ( c <= x && x (<|<=) d ) -> ( x-c (<|<=) d-c )
   300  (AndB (Leq64U (Const64 [c]) x) ((Less|Leq)64U x (Const64 [d]))) && uint64(d) >= uint64(c) => ((Less|Leq)64U (Sub64 <x.Type> x (Const64 <x.Type> [c])) (Const64 <x.Type> [d-c]))
   301  (AndB (Leq32U (Const32 [c]) x) ((Less|Leq)32U x (Const32 [d]))) && uint32(d) >= uint32(c) => ((Less|Leq)32U (Sub32 <x.Type> x (Const32 <x.Type> [c])) (Const32 <x.Type> [d-c]))
   302  (AndB (Leq16U (Const16 [c]) x) ((Less|Leq)16U x (Const16 [d]))) && uint16(d) >= uint16(c) => ((Less|Leq)16U (Sub16 <x.Type> x (Const16 <x.Type> [c])) (Const16 <x.Type> [d-c]))
   303  (AndB (Leq8U  (Const8  [c]) x) ((Less|Leq)8U  x (Const8  [d]))) && uint8(d)  >= uint8(c)  => ((Less|Leq)8U  (Sub8  <x.Type> x (Const8  <x.Type> [c])) (Const8  <x.Type> [d-c]))
   304  
   305  // unsigned integer range: ( c < x && x (<|<=) d ) -> ( x-(c+1) (<|<=) d-(c+1) )
   306  (AndB (Less64U (Const64 [c]) x) ((Less|Leq)64U x (Const64 [d]))) && uint64(d) >= uint64(c+1) && uint64(c+1) > uint64(c) => ((Less|Leq)64U (Sub64 <x.Type> x (Const64 <x.Type> [c+1])) (Const64 <x.Type> [d-c-1]))
   307  (AndB (Less32U (Const32 [c]) x) ((Less|Leq)32U x (Const32 [d]))) && uint32(d) >= uint32(c+1) && uint32(c+1) > uint32(c) => ((Less|Leq)32U (Sub32 <x.Type> x (Const32 <x.Type> [c+1])) (Const32 <x.Type> [d-c-1]))
   308  (AndB (Less16U (Const16 [c]) x) ((Less|Leq)16U x (Const16 [d]))) && uint16(d) >= uint16(c+1) && uint16(c+1) > uint16(c) => ((Less|Leq)16U (Sub16 <x.Type> x (Const16 <x.Type> [c+1])) (Const16 <x.Type> [d-c-1]))
   309  (AndB (Less8U  (Const8  [c]) x) ((Less|Leq)8U  x (Const8  [d]))) && uint8(d)  >= uint8(c+1)  && uint8(c+1)  > uint8(c)  => ((Less|Leq)8U  (Sub8  <x.Type> x (Const8  <x.Type> [c+1]))  (Const8  <x.Type> [d-c-1]))
   310  
   311  // signed integer range: ( c (<|<=) x || x < d ) -> ( unsigned(c-d) (<|<=) unsigned(x-d) )
   312  (OrB ((Less|Leq)64 (Const64 [c]) x) (Less64 x (Const64 [d]))) && c >= d => ((Less|Leq)64U (Const64 <x.Type> [c-d]) (Sub64 <x.Type> x (Const64 <x.Type> [d])))
   313  (OrB ((Less|Leq)32 (Const32 [c]) x) (Less32 x (Const32 [d]))) && c >= d => ((Less|Leq)32U (Const32 <x.Type> [c-d]) (Sub32 <x.Type> x (Const32 <x.Type> [d])))
   314  (OrB ((Less|Leq)16 (Const16 [c]) x) (Less16 x (Const16 [d]))) && c >= d => ((Less|Leq)16U (Const16 <x.Type> [c-d]) (Sub16 <x.Type> x (Const16 <x.Type> [d])))
   315  (OrB ((Less|Leq)8  (Const8  [c]) x) (Less8  x (Const8  [d]))) && c >= d => ((Less|Leq)8U  (Const8  <x.Type> [c-d]) (Sub8  <x.Type> x (Const8  <x.Type> [d])))
   316  
   317  // signed integer range: ( c (<|<=) x || x <= d ) -> ( unsigned(c-(d+1)) (<|<=) unsigned(x-(d+1)) )
   318  (OrB ((Less|Leq)64 (Const64 [c]) x) (Leq64 x (Const64 [d]))) && c >= d+1 && d+1 > d => ((Less|Leq)64U (Const64 <x.Type> [c-d-1]) (Sub64 <x.Type> x (Const64 <x.Type> [d+1])))
   319  (OrB ((Less|Leq)32 (Const32 [c]) x) (Leq32 x (Const32 [d]))) && c >= d+1 && d+1 > d => ((Less|Leq)32U (Const32 <x.Type> [c-d-1]) (Sub32 <x.Type> x (Const32 <x.Type> [d+1])))
   320  (OrB ((Less|Leq)16 (Const16 [c]) x) (Leq16 x (Const16 [d]))) && c >= d+1 && d+1 > d => ((Less|Leq)16U (Const16 <x.Type> [c-d-1]) (Sub16 <x.Type> x (Const16 <x.Type> [d+1])))
   321  (OrB ((Less|Leq)8  (Const8  [c]) x) (Leq8  x (Const8  [d]))) && c >= d+1 && d+1 > d => ((Less|Leq)8U  (Const8  <x.Type> [c-d-1]) (Sub8  <x.Type> x (Const8  <x.Type> [d+1])))
   322  
   323  // unsigned integer range: ( c (<|<=) x || x < d ) -> ( c-d (<|<=) x-d )
   324  (OrB ((Less|Leq)64U (Const64 [c]) x) (Less64U x (Const64 [d]))) && uint64(c) >= uint64(d) => ((Less|Leq)64U (Const64 <x.Type> [c-d]) (Sub64 <x.Type> x (Const64 <x.Type> [d])))
   325  (OrB ((Less|Leq)32U (Const32 [c]) x) (Less32U x (Const32 [d]))) && uint32(c) >= uint32(d) => ((Less|Leq)32U (Const32 <x.Type> [c-d]) (Sub32 <x.Type> x (Const32 <x.Type> [d])))
   326  (OrB ((Less|Leq)16U (Const16 [c]) x) (Less16U x (Const16 [d]))) && uint16(c) >= uint16(d) => ((Less|Leq)16U (Const16 <x.Type> [c-d]) (Sub16 <x.Type> x (Const16 <x.Type> [d])))
   327  (OrB ((Less|Leq)8U  (Const8  [c]) x) (Less8U  x (Const8  [d]))) && uint8(c)  >= uint8(d)  => ((Less|Leq)8U  (Const8  <x.Type> [c-d]) (Sub8  <x.Type> x (Const8  <x.Type> [d])))
   328  
   329  // unsigned integer range: ( c (<|<=) x || x <= d ) -> ( c-(d+1) (<|<=) x-(d+1) )
   330  (OrB ((Less|Leq)64U (Const64 [c]) x) (Leq64U x (Const64 [d]))) && uint64(c) >= uint64(d+1) && uint64(d+1) > uint64(d) => ((Less|Leq)64U (Const64 <x.Type> [c-d-1]) (Sub64 <x.Type> x (Const64 <x.Type> [d+1])))
   331  (OrB ((Less|Leq)32U (Const32 [c]) x) (Leq32U x (Const32 [d]))) && uint32(c) >= uint32(d+1) && uint32(d+1) > uint32(d) => ((Less|Leq)32U (Const32 <x.Type> [c-d-1]) (Sub32 <x.Type> x (Const32 <x.Type> [d+1])))
   332  (OrB ((Less|Leq)16U (Const16 [c]) x) (Leq16U x (Const16 [d]))) && uint16(c) >= uint16(d+1) && uint16(d+1) > uint16(d) => ((Less|Leq)16U (Const16 <x.Type> [c-d-1]) (Sub16 <x.Type> x (Const16 <x.Type> [d+1])))
   333  (OrB ((Less|Leq)8U  (Const8  [c]) x) (Leq8U  x (Const8  [d]))) && uint8(c)  >= uint8(d+1)  && uint8(d+1)  > uint8(d)  => ((Less|Leq)8U  (Const8  <x.Type> [c-d-1]) (Sub8  <x.Type> x (Const8  <x.Type> [d+1])))
   334  
   335  // Canonicalize x-const to x+(-const)
   336  (Sub64 x (Const64 <t> [c])) && x.Op != OpConst64 => (Add64 (Const64 <t> [-c]) x)
   337  (Sub32 x (Const32 <t> [c])) && x.Op != OpConst32 => (Add32 (Const32 <t> [-c]) x)
   338  (Sub16 x (Const16 <t> [c])) && x.Op != OpConst16 => (Add16 (Const16 <t> [-c]) x)
   339  (Sub8  x (Const8  <t> [c])) && x.Op != OpConst8  => (Add8  (Const8  <t> [-c]) x)
   340  
   341  // fold negation into comparison operators
   342  (Not (Eq(64|32|16|8|B|Ptr|64F|32F) x y)) => (Neq(64|32|16|8|B|Ptr|64F|32F) x y)
   343  (Not (Neq(64|32|16|8|B|Ptr|64F|32F) x y)) => (Eq(64|32|16|8|B|Ptr|64F|32F) x y)
   344  
   345  (Not (Less(64|32|16|8) x y)) => (Leq(64|32|16|8) y x)
   346  (Not (Less(64|32|16|8)U x y)) => (Leq(64|32|16|8)U y x)
   347  (Not (Leq(64|32|16|8) x y)) => (Less(64|32|16|8) y x)
   348  (Not (Leq(64|32|16|8)U x y)) => (Less(64|32|16|8)U y x)
   349  
   350  // Distribute multiplication c * (d+x) -> c*d + c*x. Useful for:
   351  // a[i].b = ...; a[i+1].b = ...
   352  (Mul64 (Const64 <t> [c]) (Add64 <t> (Const64 <t> [d]) x)) =>
   353    (Add64 (Const64 <t> [c*d]) (Mul64 <t> (Const64 <t> [c]) x))
   354  (Mul32 (Const32 <t> [c]) (Add32 <t> (Const32 <t> [d]) x)) =>
   355    (Add32 (Const32 <t> [c*d]) (Mul32 <t> (Const32 <t> [c]) x))
   356  (Mul16 (Const16 <t> [c]) (Add16 <t> (Const16 <t> [d]) x)) =>
   357    (Add16 (Const16 <t> [c*d]) (Mul16 <t> (Const16 <t> [c]) x))
   358  (Mul8 (Const8 <t> [c]) (Add8 <t> (Const8 <t> [d]) x)) =>
   359    (Add8 (Const8 <t> [c*d]) (Mul8 <t> (Const8 <t> [c]) x))
   360  
   361  // Rewrite x*y ± x*z  to  x*(y±z)
   362  (Add(64|32|16|8) <t> (Mul(64|32|16|8) x y) (Mul(64|32|16|8) x z))
   363  	=> (Mul(64|32|16|8) x (Add(64|32|16|8) <t> y z))
   364  (Sub(64|32|16|8) <t> (Mul(64|32|16|8) x y) (Mul(64|32|16|8) x z))
   365  	=> (Mul(64|32|16|8) x (Sub(64|32|16|8) <t> y z))
   366  
   367  // rewrite shifts of 8/16/32 bit consts into 64 bit consts to reduce
   368  // the number of the other rewrite rules for const shifts
   369  (Lsh64x32  <t> x (Const32 [c])) => (Lsh64x64  x (Const64 <t> [int64(uint32(c))]))
   370  (Lsh64x16  <t> x (Const16 [c])) => (Lsh64x64  x (Const64 <t> [int64(uint16(c))]))
   371  (Lsh64x8   <t> x (Const8  [c])) => (Lsh64x64  x (Const64 <t> [int64(uint8(c))]))
   372  (Rsh64x32  <t> x (Const32 [c])) => (Rsh64x64  x (Const64 <t> [int64(uint32(c))]))
   373  (Rsh64x16  <t> x (Const16 [c])) => (Rsh64x64  x (Const64 <t> [int64(uint16(c))]))
   374  (Rsh64x8   <t> x (Const8  [c])) => (Rsh64x64  x (Const64 <t> [int64(uint8(c))]))
   375  (Rsh64Ux32 <t> x (Const32 [c])) => (Rsh64Ux64 x (Const64 <t> [int64(uint32(c))]))
   376  (Rsh64Ux16 <t> x (Const16 [c])) => (Rsh64Ux64 x (Const64 <t> [int64(uint16(c))]))
   377  (Rsh64Ux8  <t> x (Const8  [c])) => (Rsh64Ux64 x (Const64 <t> [int64(uint8(c))]))
   378  
   379  (Lsh32x32  <t> x (Const32 [c])) => (Lsh32x64  x (Const64 <t> [int64(uint32(c))]))
   380  (Lsh32x16  <t> x (Const16 [c])) => (Lsh32x64  x (Const64 <t> [int64(uint16(c))]))
   381  (Lsh32x8   <t> x (Const8  [c])) => (Lsh32x64  x (Const64 <t> [int64(uint8(c))]))
   382  (Rsh32x32  <t> x (Const32 [c])) => (Rsh32x64  x (Const64 <t> [int64(uint32(c))]))
   383  (Rsh32x16  <t> x (Const16 [c])) => (Rsh32x64  x (Const64 <t> [int64(uint16(c))]))
   384  (Rsh32x8   <t> x (Const8  [c])) => (Rsh32x64  x (Const64 <t> [int64(uint8(c))]))
   385  (Rsh32Ux32 <t> x (Const32 [c])) => (Rsh32Ux64 x (Const64 <t> [int64(uint32(c))]))
   386  (Rsh32Ux16 <t> x (Const16 [c])) => (Rsh32Ux64 x (Const64 <t> [int64(uint16(c))]))
   387  (Rsh32Ux8  <t> x (Const8  [c])) => (Rsh32Ux64 x (Const64 <t> [int64(uint8(c))]))
   388  
   389  (Lsh16x32  <t> x (Const32 [c])) => (Lsh16x64  x (Const64 <t> [int64(uint32(c))]))
   390  (Lsh16x16  <t> x (Const16 [c])) => (Lsh16x64  x (Const64 <t> [int64(uint16(c))]))
   391  (Lsh16x8   <t> x (Const8  [c])) => (Lsh16x64  x (Const64 <t> [int64(uint8(c))]))
   392  (Rsh16x32  <t> x (Const32 [c])) => (Rsh16x64  x (Const64 <t> [int64(uint32(c))]))
   393  (Rsh16x16  <t> x (Const16 [c])) => (Rsh16x64  x (Const64 <t> [int64(uint16(c))]))
   394  (Rsh16x8   <t> x (Const8  [c])) => (Rsh16x64  x (Const64 <t> [int64(uint8(c))]))
   395  (Rsh16Ux32 <t> x (Const32 [c])) => (Rsh16Ux64 x (Const64 <t> [int64(uint32(c))]))
   396  (Rsh16Ux16 <t> x (Const16 [c])) => (Rsh16Ux64 x (Const64 <t> [int64(uint16(c))]))
   397  (Rsh16Ux8  <t> x (Const8  [c])) => (Rsh16Ux64 x (Const64 <t> [int64(uint8(c))]))
   398  
   399  (Lsh8x32  <t> x (Const32 [c])) => (Lsh8x64  x (Const64 <t> [int64(uint32(c))]))
   400  (Lsh8x16  <t> x (Const16 [c])) => (Lsh8x64  x (Const64 <t> [int64(uint16(c))]))
   401  (Lsh8x8   <t> x (Const8  [c])) => (Lsh8x64  x (Const64 <t> [int64(uint8(c))]))
   402  (Rsh8x32  <t> x (Const32 [c])) => (Rsh8x64  x (Const64 <t> [int64(uint32(c))]))
   403  (Rsh8x16  <t> x (Const16 [c])) => (Rsh8x64  x (Const64 <t> [int64(uint16(c))]))
   404  (Rsh8x8   <t> x (Const8  [c])) => (Rsh8x64  x (Const64 <t> [int64(uint8(c))]))
   405  (Rsh8Ux32 <t> x (Const32 [c])) => (Rsh8Ux64 x (Const64 <t> [int64(uint32(c))]))
   406  (Rsh8Ux16 <t> x (Const16 [c])) => (Rsh8Ux64 x (Const64 <t> [int64(uint16(c))]))
   407  (Rsh8Ux8  <t> x (Const8  [c])) => (Rsh8Ux64 x (Const64 <t> [int64(uint8(c))]))
   408  
   409  // shifts by zero
   410  (Lsh(64|32|16|8)x64  x (Const64 [0])) => x
   411  (Rsh(64|32|16|8)x64  x (Const64 [0])) => x
   412  (Rsh(64|32|16|8)Ux64 x (Const64 [0])) => x
   413  
   414  // rotates by multiples of register width
   415  (RotateLeft64 x (Const64 [c])) && c%64 == 0 => x
   416  (RotateLeft32 x (Const32 [c])) && c%32 == 0 => x
   417  (RotateLeft16 x (Const16 [c])) && c%16 == 0 => x
   418  (RotateLeft8  x (Const8 [c]))  && c%8  == 0 => x
   419  
   420  // zero shifted
   421  (Lsh64x(64|32|16|8)  (Const64 [0]) _) => (Const64 [0])
   422  (Rsh64x(64|32|16|8)  (Const64 [0]) _) => (Const64 [0])
   423  (Rsh64Ux(64|32|16|8) (Const64 [0]) _) => (Const64 [0])
   424  (Lsh32x(64|32|16|8)  (Const32 [0]) _) => (Const32 [0])
   425  (Rsh32x(64|32|16|8)  (Const32 [0]) _) => (Const32 [0])
   426  (Rsh32Ux(64|32|16|8) (Const32 [0]) _) => (Const32 [0])
   427  (Lsh16x(64|32|16|8)  (Const16 [0]) _) => (Const16 [0])
   428  (Rsh16x(64|32|16|8)  (Const16 [0]) _) => (Const16 [0])
   429  (Rsh16Ux(64|32|16|8) (Const16 [0]) _) => (Const16 [0])
   430  (Lsh8x(64|32|16|8)   (Const8  [0]) _) => (Const8  [0])
   431  (Rsh8x(64|32|16|8)   (Const8  [0]) _) => (Const8  [0])
   432  (Rsh8Ux(64|32|16|8)  (Const8  [0]) _) => (Const8  [0])
   433  
   434  // large left shifts of all values, and right shifts of unsigned values
   435  ((Lsh64|Rsh64U)x64  _ (Const64 [c])) && uint64(c) >= 64 => (Const64 [0])
   436  ((Lsh32|Rsh32U)x64  _ (Const64 [c])) && uint64(c) >= 32 => (Const32 [0])
   437  ((Lsh16|Rsh16U)x64  _ (Const64 [c])) && uint64(c) >= 16 => (Const16 [0])
   438  ((Lsh8|Rsh8U)x64    _ (Const64 [c])) && uint64(c) >= 8  => (Const8  [0])
   439  
   440  // combine const shifts
   441  (Lsh64x64 <t> (Lsh64x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Lsh64x64 x (Const64 <t> [c+d]))
   442  (Lsh32x64 <t> (Lsh32x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Lsh32x64 x (Const64 <t> [c+d]))
   443  (Lsh16x64 <t> (Lsh16x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Lsh16x64 x (Const64 <t> [c+d]))
   444  (Lsh8x64  <t> (Lsh8x64  x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Lsh8x64  x (Const64 <t> [c+d]))
   445  
   446  (Rsh64x64 <t> (Rsh64x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh64x64 x (Const64 <t> [c+d]))
   447  (Rsh32x64 <t> (Rsh32x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh32x64 x (Const64 <t> [c+d]))
   448  (Rsh16x64 <t> (Rsh16x64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh16x64 x (Const64 <t> [c+d]))
   449  (Rsh8x64  <t> (Rsh8x64  x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh8x64  x (Const64 <t> [c+d]))
   450  
   451  (Rsh64Ux64 <t> (Rsh64Ux64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh64Ux64 x (Const64 <t> [c+d]))
   452  (Rsh32Ux64 <t> (Rsh32Ux64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh32Ux64 x (Const64 <t> [c+d]))
   453  (Rsh16Ux64 <t> (Rsh16Ux64 x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh16Ux64 x (Const64 <t> [c+d]))
   454  (Rsh8Ux64  <t> (Rsh8Ux64  x (Const64 [c])) (Const64 [d])) && !uaddOvf(c,d) => (Rsh8Ux64  x (Const64 <t> [c+d]))
   455  
   456  // Remove signed right shift before an unsigned right shift that extracts the sign bit.
   457  (Rsh8Ux64  (Rsh8x64  x _) (Const64 <t> [7] )) => (Rsh8Ux64  x (Const64 <t> [7] ))
   458  (Rsh16Ux64 (Rsh16x64 x _) (Const64 <t> [15])) => (Rsh16Ux64 x (Const64 <t> [15]))
   459  (Rsh32Ux64 (Rsh32x64 x _) (Const64 <t> [31])) => (Rsh32Ux64 x (Const64 <t> [31]))
   460  (Rsh64Ux64 (Rsh64x64 x _) (Const64 <t> [63])) => (Rsh64Ux64 x (Const64 <t> [63]))
   461  
   462  // Convert x>>c<<c to x&^(1<<c-1)
   463  (Lsh64x64 i:(Rsh(64|64U)x64  x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 64 && i.Uses == 1 => (And64 x (Const64 <v.Type> [int64(-1) << c]))
   464  (Lsh32x64 i:(Rsh(32|32U)x64  x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 32 && i.Uses == 1 => (And32 x (Const32 <v.Type> [int32(-1) << c]))
   465  (Lsh16x64 i:(Rsh(16|16U)x64  x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 16 && i.Uses == 1 => (And16 x (Const16 <v.Type> [int16(-1) << c]))
   466  (Lsh8x64  i:(Rsh(8|8U)x64    x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 8  && i.Uses == 1 => (And8  x (Const8  <v.Type> [int8(-1)  << c]))
   467  // similarly for x<<c>>c
   468  (Rsh64Ux64 i:(Lsh64x64 x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 64 && i.Uses == 1 => (And64 x (Const64 <v.Type> [int64(^uint64(0)>>c)]))
   469  (Rsh32Ux64 i:(Lsh32x64 x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 32 && i.Uses == 1 => (And32 x (Const32 <v.Type> [int32(^uint32(0)>>c)]))
   470  (Rsh16Ux64 i:(Lsh16x64 x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 16 && i.Uses == 1 => (And16 x (Const16 <v.Type> [int16(^uint16(0)>>c)]))
   471  (Rsh8Ux64  i:(Lsh8x64  x (Const64 [c])) (Const64 [c])) && c >= 0 && c < 8  && i.Uses == 1 => (And8  x (Const8  <v.Type> [int8 (^uint8 (0)>>c)]))
   472  
   473  // ((x >> c1) << c2) >> c3
   474  (Rsh(64|32|16|8)Ux64 (Lsh(64|32|16|8)x64 (Rsh(64|32|16|8)Ux64 x (Const64 [c1])) (Const64 [c2])) (Const64 [c3]))
   475    && uint64(c1) >= uint64(c2) && uint64(c3) >= uint64(c2) && !uaddOvf(c1-c2, c3)
   476    => (Rsh(64|32|16|8)Ux64 x (Const64 <typ.UInt64> [c1-c2+c3]))
   477  
   478  // ((x << c1) >> c2) << c3
   479  (Lsh(64|32|16|8)x64 (Rsh(64|32|16|8)Ux64 (Lsh(64|32|16|8)x64 x (Const64 [c1])) (Const64 [c2])) (Const64 [c3]))
   480    && uint64(c1) >= uint64(c2) && uint64(c3) >= uint64(c2) && !uaddOvf(c1-c2, c3)
   481    => (Lsh(64|32|16|8)x64 x (Const64 <typ.UInt64> [c1-c2+c3]))
   482  
   483  // (x >> c) & uppermask = 0
   484  (And64 (Const64 [m]) (Rsh64Ux64 _ (Const64 [c]))) && c >= int64(64-ntz64(m)) => (Const64 [0])
   485  (And32 (Const32 [m]) (Rsh32Ux64 _ (Const64 [c]))) && c >= int64(32-ntz32(m)) => (Const32 [0])
   486  (And16 (Const16 [m]) (Rsh16Ux64 _ (Const64 [c]))) && c >= int64(16-ntz16(m)) => (Const16 [0])
   487  (And8  (Const8  [m]) (Rsh8Ux64  _ (Const64 [c]))) && c >= int64(8-ntz8(m))  => (Const8  [0])
   488  
   489  // (x << c) & lowermask = 0
   490  (And64 (Const64 [m]) (Lsh64x64  _ (Const64 [c]))) && c >= int64(64-nlz64(m)) => (Const64 [0])
   491  (And32 (Const32 [m]) (Lsh32x64  _ (Const64 [c]))) && c >= int64(32-nlz32(m)) => (Const32 [0])
   492  (And16 (Const16 [m]) (Lsh16x64  _ (Const64 [c]))) && c >= int64(16-nlz16(m)) => (Const16 [0])
   493  (And8  (Const8  [m]) (Lsh8x64   _ (Const64 [c]))) && c >= int64(8-nlz8(m))  => (Const8  [0])
   494  
   495  // replace shifts with zero extensions
   496  (Rsh16Ux64 (Lsh16x64 x (Const64  [8])) (Const64  [8])) => (ZeroExt8to16  (Trunc16to8  <typ.UInt8>  x))
   497  (Rsh32Ux64 (Lsh32x64 x (Const64 [24])) (Const64 [24])) => (ZeroExt8to32  (Trunc32to8  <typ.UInt8>  x))
   498  (Rsh64Ux64 (Lsh64x64 x (Const64 [56])) (Const64 [56])) => (ZeroExt8to64  (Trunc64to8  <typ.UInt8>  x))
   499  (Rsh32Ux64 (Lsh32x64 x (Const64 [16])) (Const64 [16])) => (ZeroExt16to32 (Trunc32to16 <typ.UInt16> x))
   500  (Rsh64Ux64 (Lsh64x64 x (Const64 [48])) (Const64 [48])) => (ZeroExt16to64 (Trunc64to16 <typ.UInt16> x))
   501  (Rsh64Ux64 (Lsh64x64 x (Const64 [32])) (Const64 [32])) => (ZeroExt32to64 (Trunc64to32 <typ.UInt32> x))
   502  
   503  // replace shifts with sign extensions
   504  (Rsh16x64 (Lsh16x64 x (Const64  [8])) (Const64  [8])) => (SignExt8to16  (Trunc16to8  <typ.Int8>  x))
   505  (Rsh32x64 (Lsh32x64 x (Const64 [24])) (Const64 [24])) => (SignExt8to32  (Trunc32to8  <typ.Int8>  x))
   506  (Rsh64x64 (Lsh64x64 x (Const64 [56])) (Const64 [56])) => (SignExt8to64  (Trunc64to8  <typ.Int8>  x))
   507  (Rsh32x64 (Lsh32x64 x (Const64 [16])) (Const64 [16])) => (SignExt16to32 (Trunc32to16 <typ.Int16> x))
   508  (Rsh64x64 (Lsh64x64 x (Const64 [48])) (Const64 [48])) => (SignExt16to64 (Trunc64to16 <typ.Int16> x))
   509  (Rsh64x64 (Lsh64x64 x (Const64 [32])) (Const64 [32])) => (SignExt32to64 (Trunc64to32 <typ.Int32> x))
   510  
   511  // ((x >> c) & d) << e
   512  (Lsh64x64 (And64 (Rsh(64|64U)x64 <t> x (Const64 <t2> [c])) (Const64 [d])) (Const64 [e])) && c >= e => (And64 (Rsh(64|64U)x64 <t> x (Const64 <t2> [c-e])) (Const64 <t> [d<<e]))
   513  (Lsh32x64 (And32 (Rsh(32|32U)x64 <t> x (Const64 <t2> [c])) (Const32 [d])) (Const64 [e])) && c >= e => (And32 (Rsh(32|32U)x64 <t> x (Const64 <t2> [c-e])) (Const32 <t> [d<<e]))
   514  (Lsh16x64 (And16 (Rsh(16|16U)x64 <t> x (Const64 <t2> [c])) (Const16 [d])) (Const64 [e])) && c >= e => (And16 (Rsh(16|16U)x64 <t> x (Const64 <t2> [c-e])) (Const16 <t> [d<<e]))
   515  (Lsh8x64  (And8  (Rsh(8|8U)x64   <t> x (Const64 <t2> [c])) (Const8  [d])) (Const64 [e])) && c >= e => (And8  (Rsh(8|8U)x64   <t> x (Const64 <t2> [c-e])) (Const8  <t> [d<<e]))
   516  (Lsh64x64 (And64 (Rsh(64|64U)x64 <t> x (Const64 <t2> [c])) (Const64 [d])) (Const64 [e])) && c < e =>  (And64 (Lsh64x64 <t> x (Const64 <t2> [e-c])) (Const64 <t> [d<<e]))
   517  (Lsh32x64 (And32 (Rsh(32|32U)x64 <t> x (Const64 <t2> [c])) (Const32 [d])) (Const64 [e])) && c < e =>  (And32 (Lsh32x64 <t> x (Const64 <t2> [e-c])) (Const32 <t> [d<<e]))
   518  (Lsh16x64 (And16 (Rsh(16|16U)x64 <t> x (Const64 <t2> [c])) (Const16 [d])) (Const64 [e])) && c < e =>  (And16 (Lsh16x64 <t> x (Const64 <t2> [e-c])) (Const16 <t> [d<<e]))
   519  (Lsh8x64  (And8  (Rsh(8|8U)x64   <t> x (Const64 <t2> [c])) (Const8  [d])) (Const64 [e])) && c < e =>  (And8  (Lsh8x64  <t> x (Const64 <t2> [e-c])) (Const8  <t> [d<<e]))
   520  
   521  // constant comparisons
   522  (Eq(64|32|16|8)   (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) => (ConstBool [c == d])
   523  (Neq(64|32|16|8)  (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) => (ConstBool [c != d])
   524  (Less(64|32|16|8) (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) => (ConstBool [c < d])
   525  (Leq(64|32|16|8)  (Const(64|32|16|8) [c]) (Const(64|32|16|8) [d])) => (ConstBool [c <= d])
   526  
   527  (Less64U (Const64 [c]) (Const64 [d])) => (ConstBool [uint64(c) < uint64(d)])
   528  (Less32U (Const32 [c]) (Const32 [d])) => (ConstBool [uint32(c) < uint32(d)])
   529  (Less16U (Const16 [c]) (Const16 [d])) => (ConstBool [uint16(c) < uint16(d)])
   530  (Less8U  (Const8  [c]) (Const8  [d])) => (ConstBool [ uint8(c) <  uint8(d)])
   531  
   532  (Leq64U (Const64 [c]) (Const64 [d])) => (ConstBool [uint64(c) <= uint64(d)])
   533  (Leq32U (Const32 [c]) (Const32 [d])) => (ConstBool [uint32(c) <= uint32(d)])
   534  (Leq16U (Const16 [c]) (Const16 [d])) => (ConstBool [uint16(c) <= uint16(d)])
   535  (Leq8U  (Const8  [c]) (Const8  [d])) => (ConstBool [ uint8(c) <=  uint8(d)])
   536  
   537  (Leq8  (Const8  [0]) (And8  _ (Const8  [c]))) && c >= 0 => (ConstBool [true])
   538  (Leq16 (Const16 [0]) (And16 _ (Const16 [c]))) && c >= 0 => (ConstBool [true])
   539  (Leq32 (Const32 [0]) (And32 _ (Const32 [c]))) && c >= 0 => (ConstBool [true])
   540  (Leq64 (Const64 [0]) (And64 _ (Const64 [c]))) && c >= 0 => (ConstBool [true])
   541  
   542  (Leq8  (Const8  [0]) (Rsh8Ux64  _ (Const64 [c]))) && c > 0 => (ConstBool [true])
   543  (Leq16 (Const16 [0]) (Rsh16Ux64 _ (Const64 [c]))) && c > 0 => (ConstBool [true])
   544  (Leq32 (Const32 [0]) (Rsh32Ux64 _ (Const64 [c]))) && c > 0 => (ConstBool [true])
   545  (Leq64 (Const64 [0]) (Rsh64Ux64 _ (Const64 [c]))) && c > 0 => (ConstBool [true])
   546  
   547  // prefer equalities with zero
   548  (Less(64|32|16|8) (Const(64|32|16|8) <t> [0]) x) && isNonNegative(x) => (Neq(64|32|16|8) (Const(64|32|16|8) <t> [0]) x)
   549  (Less(64|32|16|8) x (Const(64|32|16|8) <t> [1])) && isNonNegative(x) => (Eq(64|32|16|8) (Const(64|32|16|8) <t> [0]) x)
   550  (Less(64|32|16|8)U x (Const(64|32|16|8) <t> [1])) => (Eq(64|32|16|8) (Const(64|32|16|8) <t> [0]) x)
   551  (Leq(64|32|16|8)U (Const(64|32|16|8) <t> [1]) x) => (Neq(64|32|16|8) (Const(64|32|16|8) <t> [0]) x)
   552  
   553  // prefer comparisons with zero
   554  (Less(64|32|16|8) x (Const(64|32|16|8) <t> [1])) => (Leq(64|32|16|8) x (Const(64|32|16|8) <t> [0]))
   555  (Leq(64|32|16|8) x (Const(64|32|16|8) <t> [-1])) => (Less(64|32|16|8) x (Const(64|32|16|8) <t> [0]))
   556  (Leq(64|32|16|8) (Const(64|32|16|8) <t> [1]) x) => (Less(64|32|16|8) (Const(64|32|16|8) <t> [0]) x)
   557  (Less(64|32|16|8) (Const(64|32|16|8) <t> [-1]) x) => (Leq(64|32|16|8) (Const(64|32|16|8) <t> [0]) x)
   558  
   559  // constant floating point comparisons
   560  (Eq32F   (Const32F [c]) (Const32F [d])) => (ConstBool [c == d])
   561  (Eq64F   (Const64F [c]) (Const64F [d])) => (ConstBool [c == d])
   562  (Neq32F  (Const32F [c]) (Const32F [d])) => (ConstBool [c != d])
   563  (Neq64F  (Const64F [c]) (Const64F [d])) => (ConstBool [c != d])
   564  (Less32F (Const32F [c]) (Const32F [d])) => (ConstBool [c < d])
   565  (Less64F (Const64F [c]) (Const64F [d])) => (ConstBool [c < d])
   566  (Leq32F  (Const32F [c]) (Const32F [d])) => (ConstBool [c <= d])
   567  (Leq64F  (Const64F [c]) (Const64F [d])) => (ConstBool [c <= d])
   568  
   569  // simplifications
   570  (Or(64|32|16|8) x x) => x
   571  (Or(64|32|16|8) (Const(64|32|16|8)  [0]) x) => x
   572  (Or(64|32|16|8) (Const(64|32|16|8) [-1]) _) => (Const(64|32|16|8) [-1])
   573  (Or(64|32|16|8) (Com(64|32|16|8)     x)  x) => (Const(64|32|16|8) [-1])
   574  
   575  (And(64|32|16|8) x x) => x
   576  (And(64|32|16|8) (Const(64|32|16|8) [-1]) x) => x
   577  (And(64|32|16|8) (Const(64|32|16|8)  [0]) _) => (Const(64|32|16|8) [0])
   578  (And(64|32|16|8) (Com(64|32|16|8)     x)  x) => (Const(64|32|16|8) [0])
   579  
   580  (Xor(64|32|16|8) x x) => (Const(64|32|16|8) [0])
   581  (Xor(64|32|16|8) (Const(64|32|16|8) [0]) x) => x
   582  (Xor(64|32|16|8) (Com(64|32|16|8)    x)  x) => (Const(64|32|16|8) [-1])
   583  
   584  (Add(64|32|16|8) (Const(64|32|16|8) [0]) x) => x
   585  (Sub(64|32|16|8) x x) => (Const(64|32|16|8) [0])
   586  (Mul(64|32|16|8) (Const(64|32|16|8) [0]) _) => (Const(64|32|16|8) [0])
   587  (Select0 (Mul(64|32)uover (Const(64|32) [0]) x)) => (Const(64|32) [0])
   588  (Select1 (Mul(64|32)uover (Const(64|32) [0]) x)) => (ConstBool [false])
   589  
   590  (Com(64|32|16|8) (Com(64|32|16|8)  x)) => x
   591  (Com(64|32|16|8) (Const(64|32|16|8) [c])) => (Const(64|32|16|8) [^c])
   592  
   593  (Neg(64|32|16|8) (Sub(64|32|16|8) x y)) => (Sub(64|32|16|8) y x)
   594  (Add(64|32|16|8) x (Neg(64|32|16|8) y)) => (Sub(64|32|16|8) x y)
   595  
   596  (Xor(64|32|16|8) (Const(64|32|16|8) [-1]) x) => (Com(64|32|16|8) x)
   597  
   598  (Sub(64|32|16|8) (Neg(64|32|16|8) x) (Com(64|32|16|8) x)) => (Const(64|32|16|8) [1])
   599  (Sub(64|32|16|8) (Com(64|32|16|8) x) (Neg(64|32|16|8) x)) => (Const(64|32|16|8) [-1])
   600  (Add(64|32|16|8) (Com(64|32|16|8) x)                  x)  => (Const(64|32|16|8) [-1])
   601  
   602  // Simplification when involving common integer
   603  // (t + x) - (t + y) == x - y
   604  // (t + x) - (y + t) == x - y
   605  // (x + t) - (y + t) == x - y
   606  // (x + t) - (t + y) == x - y
   607  // (x - t) + (t + y) == x + y
   608  // (x - t) + (y + t) == x + y
   609  (Sub(64|32|16|8) (Add(64|32|16|8) t x) (Add(64|32|16|8) t y)) => (Sub(64|32|16|8) x y)
   610  (Add(64|32|16|8) (Sub(64|32|16|8) x t) (Add(64|32|16|8) t y)) => (Add(64|32|16|8) x y)
   611  
   612  // ^(x-1) == ^x+1 == -x
   613  (Add(64|32|16|8) (Const(64|32|16|8) [1]) (Com(64|32|16|8) x)) => (Neg(64|32|16|8) x)
   614  (Com(64|32|16|8) (Add(64|32|16|8) (Const(64|32|16|8) [-1]) x)) => (Neg(64|32|16|8) x)
   615  
   616  // -(-x) == x
   617  (Neg(64|32|16|8) (Neg(64|32|16|8) x)) => x
   618  
   619  // -^x == x+1
   620  (Neg(64|32|16|8) <t> (Com(64|32|16|8) x)) => (Add(64|32|16|8) (Const(64|32|16|8) <t> [1]) x)
   621  
   622  (And(64|32|16|8) x (And(64|32|16|8) x y)) => (And(64|32|16|8) x y)
   623  (Or(64|32|16|8) x (Or(64|32|16|8) x y)) => (Or(64|32|16|8) x y)
   624  (Xor(64|32|16|8) x (Xor(64|32|16|8) x y)) => y
   625  
   626  // Fold comparisons with numeric bounds
   627  (Less(64|32|16|8)U _ (Const(64|32|16|8) [0]))  => (ConstBool [false])
   628  (Leq(64|32|16|8)U (Const(64|32|16|8) [0]) _)   => (ConstBool [true])
   629  (Less(64|32|16|8)U (Const(64|32|16|8) [-1]) _) => (ConstBool [false])
   630  (Leq(64|32|16|8)U _ (Const(64|32|16|8) [-1]))  => (ConstBool [true])
   631  (Less64 _ (Const64 [math.MinInt64])) => (ConstBool [false])
   632  (Less32 _ (Const32 [math.MinInt32])) => (ConstBool [false])
   633  (Less16 _ (Const16 [math.MinInt16])) => (ConstBool [false])
   634  (Less8  _ (Const8  [math.MinInt8 ])) => (ConstBool [false])
   635  (Leq64 (Const64 [math.MinInt64]) _)  => (ConstBool [true])
   636  (Leq32 (Const32 [math.MinInt32]) _)  => (ConstBool [true])
   637  (Leq16 (Const16 [math.MinInt16]) _)  => (ConstBool [true])
   638  (Leq8  (Const8  [math.MinInt8 ]) _)  => (ConstBool [true])
   639  (Less64 (Const64 [math.MaxInt64]) _) => (ConstBool [false])
   640  (Less32 (Const32 [math.MaxInt32]) _) => (ConstBool [false])
   641  (Less16 (Const16 [math.MaxInt16]) _) => (ConstBool [false])
   642  (Less8  (Const8  [math.MaxInt8 ]) _) => (ConstBool [false])
   643  (Leq64 _ (Const64 [math.MaxInt64]))  => (ConstBool [true])
   644  (Leq32 _ (Const32 [math.MaxInt32]))  => (ConstBool [true])
   645  (Leq16 _ (Const16 [math.MaxInt16]))  => (ConstBool [true])
   646  (Leq8  _ (Const8  [math.MaxInt8 ]))  => (ConstBool [true])
   647  
   648  // Canonicalize <= on numeric bounds and < near numeric bounds to ==
   649  (Leq(64|32|16|8)U x c:(Const(64|32|16|8) [0]))     => (Eq(64|32|16|8) x c)
   650  (Leq(64|32|16|8)U c:(Const(64|32|16|8) [-1]) x)    => (Eq(64|32|16|8) x c)
   651  (Less(64|32|16|8)U x (Const(64|32|16|8) <t> [1]))  => (Eq(64|32|16|8) x (Const(64|32|16|8) <t> [0]))
   652  (Less(64|32|16|8)U (Const(64|32|16|8) <t> [-2]) x) => (Eq(64|32|16|8) x (Const(64|32|16|8) <t> [-1]))
   653  (Leq64 x c:(Const64 [math.MinInt64])) => (Eq64 x c)
   654  (Leq32 x c:(Const32 [math.MinInt32])) => (Eq32 x c)
   655  (Leq16 x c:(Const16 [math.MinInt16])) => (Eq16 x c)
   656  (Leq8  x c:(Const8  [math.MinInt8 ])) => (Eq8  x c)
   657  (Leq64 c:(Const64 [math.MaxInt64]) x) => (Eq64 x c)
   658  (Leq32 c:(Const32 [math.MaxInt32]) x) => (Eq32 x c)
   659  (Leq16 c:(Const16 [math.MaxInt16]) x) => (Eq16 x c)
   660  (Leq8  c:(Const8  [math.MaxInt8 ]) x) => (Eq8  x c)
   661  (Less64 x (Const64 <t> [math.MinInt64+1])) => (Eq64 x (Const64 <t> [math.MinInt64]))
   662  (Less32 x (Const32 <t> [math.MinInt32+1])) => (Eq32 x (Const32 <t> [math.MinInt32]))
   663  (Less16 x (Const16 <t> [math.MinInt16+1])) => (Eq16 x (Const16 <t> [math.MinInt16]))
   664  (Less8  x (Const8  <t> [math.MinInt8 +1])) => (Eq8  x (Const8  <t> [math.MinInt8 ]))
   665  (Less64 (Const64 <t> [math.MaxInt64-1]) x) => (Eq64 x (Const64 <t> [math.MaxInt64]))
   666  (Less32 (Const32 <t> [math.MaxInt32-1]) x) => (Eq32 x (Const32 <t> [math.MaxInt32]))
   667  (Less16 (Const16 <t> [math.MaxInt16-1]) x) => (Eq16 x (Const16 <t> [math.MaxInt16]))
   668  (Less8  (Const8  <t> [math.MaxInt8 -1]) x) => (Eq8  x (Const8  <t> [math.MaxInt8 ]))
   669  
   670  // Ands clear bits. Ors set bits.
   671  // If a subsequent Or will set all the bits
   672  // that an And cleared, we can skip the And.
   673  // This happens in bitmasking code like:
   674  //   x &^= 3 << shift // clear two old bits
   675  //   x  |= v << shift // set two new bits
   676  // when shift is a small constant and v ends up a constant 3.
   677  (Or8  (And8  x (Const8  [c2])) (Const8  <t> [c1])) && ^(c1 | c2) == 0 => (Or8  (Const8  <t> [c1]) x)
   678  (Or16 (And16 x (Const16 [c2])) (Const16 <t> [c1])) && ^(c1 | c2) == 0 => (Or16 (Const16 <t> [c1]) x)
   679  (Or32 (And32 x (Const32 [c2])) (Const32 <t> [c1])) && ^(c1 | c2) == 0 => (Or32 (Const32 <t> [c1]) x)
   680  (Or64 (And64 x (Const64 [c2])) (Const64 <t> [c1])) && ^(c1 | c2) == 0 => (Or64 (Const64 <t> [c1]) x)
   681  
   682  (Trunc64to8  (And64 (Const64 [y]) x)) && y&0xFF == 0xFF => (Trunc64to8 x)
   683  (Trunc64to16 (And64 (Const64 [y]) x)) && y&0xFFFF == 0xFFFF => (Trunc64to16 x)
   684  (Trunc64to32 (And64 (Const64 [y]) x)) && y&0xFFFFFFFF == 0xFFFFFFFF => (Trunc64to32 x)
   685  (Trunc32to8  (And32 (Const32 [y]) x)) && y&0xFF == 0xFF => (Trunc32to8 x)
   686  (Trunc32to16 (And32 (Const32 [y]) x)) && y&0xFFFF == 0xFFFF => (Trunc32to16 x)
   687  (Trunc16to8  (And16 (Const16 [y]) x)) && y&0xFF == 0xFF => (Trunc16to8 x)
   688  
   689  (ZeroExt8to64  (Trunc64to8  x:(Rsh64Ux64 _ (Const64 [s])))) && s >= 56 => x
   690  (ZeroExt16to64 (Trunc64to16 x:(Rsh64Ux64 _ (Const64 [s])))) && s >= 48 => x
   691  (ZeroExt32to64 (Trunc64to32 x:(Rsh64Ux64 _ (Const64 [s])))) && s >= 32 => x
   692  (ZeroExt8to32  (Trunc32to8  x:(Rsh32Ux64 _ (Const64 [s])))) && s >= 24 => x
   693  (ZeroExt16to32 (Trunc32to16 x:(Rsh32Ux64 _ (Const64 [s])))) && s >= 16 => x
   694  (ZeroExt8to16  (Trunc16to8  x:(Rsh16Ux64 _ (Const64 [s])))) && s >= 8 => x
   695  
   696  (SignExt8to64  (Trunc64to8  x:(Rsh64x64 _ (Const64 [s])))) && s >= 56 => x
   697  (SignExt16to64 (Trunc64to16 x:(Rsh64x64 _ (Const64 [s])))) && s >= 48 => x
   698  (SignExt32to64 (Trunc64to32 x:(Rsh64x64 _ (Const64 [s])))) && s >= 32 => x
   699  (SignExt8to32  (Trunc32to8  x:(Rsh32x64 _ (Const64 [s])))) && s >= 24 => x
   700  (SignExt16to32 (Trunc32to16 x:(Rsh32x64 _ (Const64 [s])))) && s >= 16 => x
   701  (SignExt8to16  (Trunc16to8  x:(Rsh16x64 _ (Const64 [s])))) && s >= 8 => x
   702  
   703  (Slicemask (Const32 [x])) && x > 0 => (Const32 [-1])
   704  (Slicemask (Const32 [0]))          => (Const32 [0])
   705  (Slicemask (Const64 [x])) && x > 0 => (Const64 [-1])
   706  (Slicemask (Const64 [0]))          => (Const64 [0])
   707  
   708  // simplifications often used for lengths.  e.g. len(s[i:i+5])==5
   709  (Sub(64|32|16|8) (Add(64|32|16|8) x y) x) => y
   710  (Sub(64|32|16|8) (Add(64|32|16|8) x y) y) => x
   711  (Sub(64|32|16|8) (Sub(64|32|16|8) x y) x) => (Neg(64|32|16|8) y)
   712  (Sub(64|32|16|8) x (Add(64|32|16|8) x y)) => (Neg(64|32|16|8) y)
   713  (Add(64|32|16|8) x (Sub(64|32|16|8) y x)) => y
   714  (Add(64|32|16|8) x (Add(64|32|16|8) y (Sub(64|32|16|8) z x))) => (Add(64|32|16|8) y z)
   715  
   716  // basic phi simplifications
   717  (Phi (Const8  [c]) (Const8  [c])) => (Const8  [c])
   718  (Phi (Const16 [c]) (Const16 [c])) => (Const16 [c])
   719  (Phi (Const32 [c]) (Const32 [c])) => (Const32 [c])
   720  (Phi (Const64 [c]) (Const64 [c])) => (Const64 [c])
   721  
   722  // slice and interface comparisons
   723  // The frontend ensures that we can only compare against nil,
   724  // so we need only compare the first word (interface type or slice ptr).
   725  (EqInter x y)  => (EqPtr  (ITab x) (ITab y))
   726  (NeqInter x y) => (NeqPtr (ITab x) (ITab y))
   727  (EqSlice x y)  => (EqPtr  (SlicePtr x) (SlicePtr y))
   728  (NeqSlice x y) => (NeqPtr (SlicePtr x) (SlicePtr y))
   729  
   730  // Load of store of same address, with compatibly typed value and same size
   731  (Load <t1> p1 (Store {t2} p2 x _))
   732  	&& isSamePtr(p1, p2)
   733  	&& t1.Compare(x.Type) == types.CMPeq
   734  	&& t1.Size() == t2.Size()
   735  	=> x
   736  (Load <t1> p1 (Store {t2} p2 _ (Store {t3} p3 x _)))
   737  	&& isSamePtr(p1, p3)
   738  	&& t1.Compare(x.Type) == types.CMPeq
   739  	&& t1.Size() == t2.Size()
   740  	&& disjoint(p3, t3.Size(), p2, t2.Size())
   741  	=> x
   742  (Load <t1> p1 (Store {t2} p2 _ (Store {t3} p3 _ (Store {t4} p4 x _))))
   743  	&& isSamePtr(p1, p4)
   744  	&& t1.Compare(x.Type) == types.CMPeq
   745  	&& t1.Size() == t2.Size()
   746  	&& disjoint(p4, t4.Size(), p2, t2.Size())
   747  	&& disjoint(p4, t4.Size(), p3, t3.Size())
   748  	=> x
   749  (Load <t1> p1 (Store {t2} p2 _ (Store {t3} p3 _ (Store {t4} p4 _ (Store {t5} p5 x _)))))
   750  	&& isSamePtr(p1, p5)
   751  	&& t1.Compare(x.Type) == types.CMPeq
   752  	&& t1.Size() == t2.Size()
   753  	&& disjoint(p5, t5.Size(), p2, t2.Size())
   754  	&& disjoint(p5, t5.Size(), p3, t3.Size())
   755  	&& disjoint(p5, t5.Size(), p4, t4.Size())
   756  	=> x
   757  
   758  // Pass constants through math.Float{32,64}bits and math.Float{32,64}frombits
   759  (Load <t1> p1 (Store {t2} p2 (Const64  [x]) _)) && isSamePtr(p1,p2) && t2.Size() == 8 && is64BitFloat(t1) && !math.IsNaN(math.Float64frombits(uint64(x))) => (Const64F [math.Float64frombits(uint64(x))])
   760  (Load <t1> p1 (Store {t2} p2 (Const32  [x]) _)) && isSamePtr(p1,p2) && t2.Size() == 4 && is32BitFloat(t1) && !math.IsNaN(float64(math.Float32frombits(uint32(x)))) => (Const32F [math.Float32frombits(uint32(x))])
   761  (Load <t1> p1 (Store {t2} p2 (Const64F [x]) _)) && isSamePtr(p1,p2) && t2.Size() == 8 && is64BitInt(t1)   => (Const64  [int64(math.Float64bits(x))])
   762  (Load <t1> p1 (Store {t2} p2 (Const32F [x]) _)) && isSamePtr(p1,p2) && t2.Size() == 4 && is32BitInt(t1)   => (Const32  [int32(math.Float32bits(x))])
   763  
   764  // Float Loads up to Zeros so they can be constant folded.
   765  (Load <t1> op:(OffPtr [o1] p1)
   766  	(Store {t2} p2 _
   767  		mem:(Zero [n] p3 _)))
   768  	&& o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p3)
   769  	&& CanSSA(t1)
   770  	&& disjoint(op, t1.Size(), p2, t2.Size())
   771  	=> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p3) mem)
   772  (Load <t1> op:(OffPtr [o1] p1)
   773  	(Store {t2} p2 _
   774  		(Store {t3} p3 _
   775  			mem:(Zero [n] p4 _))))
   776  	&& o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p4)
   777  	&& CanSSA(t1)
   778  	&& disjoint(op, t1.Size(), p2, t2.Size())
   779  	&& disjoint(op, t1.Size(), p3, t3.Size())
   780  	=> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p4) mem)
   781  (Load <t1> op:(OffPtr [o1] p1)
   782  	(Store {t2} p2 _
   783  		(Store {t3} p3 _
   784  			(Store {t4} p4 _
   785  				mem:(Zero [n] p5 _)))))
   786  	&& o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p5)
   787  	&& CanSSA(t1)
   788  	&& disjoint(op, t1.Size(), p2, t2.Size())
   789  	&& disjoint(op, t1.Size(), p3, t3.Size())
   790  	&& disjoint(op, t1.Size(), p4, t4.Size())
   791  	=> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p5) mem)
   792  (Load <t1> op:(OffPtr [o1] p1)
   793  	(Store {t2} p2 _
   794  		(Store {t3} p3 _
   795  			(Store {t4} p4 _
   796  				(Store {t5} p5 _
   797  					mem:(Zero [n] p6 _))))))
   798  	&& o1 >= 0 && o1+t1.Size() <= n && isSamePtr(p1, p6)
   799  	&& CanSSA(t1)
   800  	&& disjoint(op, t1.Size(), p2, t2.Size())
   801  	&& disjoint(op, t1.Size(), p3, t3.Size())
   802  	&& disjoint(op, t1.Size(), p4, t4.Size())
   803  	&& disjoint(op, t1.Size(), p5, t5.Size())
   804  	=> @mem.Block (Load <t1> (OffPtr <op.Type> [o1] p6) mem)
   805  
   806  // Zero to Load forwarding.
   807  (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
   808  	&& t1.IsBoolean()
   809  	&& isSamePtr(p1, p2)
   810  	&& n >= o + 1
   811  	=> (ConstBool [false])
   812  (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
   813  	&& is8BitInt(t1)
   814  	&& isSamePtr(p1, p2)
   815  	&& n >= o + 1
   816  	=> (Const8 [0])
   817  (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
   818  	&& is16BitInt(t1)
   819  	&& isSamePtr(p1, p2)
   820  	&& n >= o + 2
   821  	=> (Const16 [0])
   822  (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
   823  	&& is32BitInt(t1)
   824  	&& isSamePtr(p1, p2)
   825  	&& n >= o + 4
   826  	=> (Const32 [0])
   827  (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
   828  	&& is64BitInt(t1)
   829  	&& isSamePtr(p1, p2)
   830  	&& n >= o + 8
   831  	=> (Const64 [0])
   832  (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
   833  	&& is32BitFloat(t1)
   834  	&& isSamePtr(p1, p2)
   835  	&& n >= o + 4
   836  	=> (Const32F [0])
   837  (Load <t1> (OffPtr [o] p1) (Zero [n] p2 _))
   838  	&& is64BitFloat(t1)
   839  	&& isSamePtr(p1, p2)
   840  	&& n >= o + 8
   841  	=> (Const64F [0])
   842  
   843  // Eliminate stores of values that have just been loaded from the same location.
   844  // We also handle the common case where there are some intermediate stores.
   845  (Store {t1} p1 (Load <t2> p2 mem) mem)
   846  	&& isSamePtr(p1, p2)
   847  	&& t2.Size() == t1.Size()
   848  	=> mem
   849  (Store {t1} p1 (Load <t2> p2 oldmem) mem:(Store {t3} p3 _ oldmem))
   850  	&& isSamePtr(p1, p2)
   851  	&& t2.Size() == t1.Size()
   852  	&& disjoint(p1, t1.Size(), p3, t3.Size())
   853  	=> mem
   854  (Store {t1} p1 (Load <t2> p2 oldmem) mem:(Store {t3} p3 _ (Store {t4} p4 _ oldmem)))
   855  	&& isSamePtr(p1, p2)
   856  	&& t2.Size() == t1.Size()
   857  	&& disjoint(p1, t1.Size(), p3, t3.Size())
   858  	&& disjoint(p1, t1.Size(), p4, t4.Size())
   859  	=> mem
   860  (Store {t1} p1 (Load <t2> p2 oldmem) mem:(Store {t3} p3 _ (Store {t4} p4 _ (Store {t5} p5 _ oldmem))))
   861  	&& isSamePtr(p1, p2)
   862  	&& t2.Size() == t1.Size()
   863  	&& disjoint(p1, t1.Size(), p3, t3.Size())
   864  	&& disjoint(p1, t1.Size(), p4, t4.Size())
   865  	&& disjoint(p1, t1.Size(), p5, t5.Size())
   866  	=> mem
   867  
   868  // Don't Store zeros to cleared variables.
   869  (Store {t} (OffPtr [o] p1) x mem:(Zero [n] p2 _))
   870  	&& isConstZero(x)
   871  	&& o >= 0 && t.Size() + o <= n && isSamePtr(p1, p2)
   872  	=> mem
   873  (Store {t1} op:(OffPtr [o1] p1) x mem:(Store {t2} p2 _ (Zero [n] p3 _)))
   874  	&& isConstZero(x)
   875  	&& o1 >= 0 && t1.Size() + o1 <= n && isSamePtr(p1, p3)
   876  	&& disjoint(op, t1.Size(), p2, t2.Size())
   877  	=> mem
   878  (Store {t1} op:(OffPtr [o1] p1) x mem:(Store {t2} p2 _ (Store {t3} p3 _ (Zero [n] p4 _))))
   879  	&& isConstZero(x)
   880  	&& o1 >= 0 && t1.Size() + o1 <= n && isSamePtr(p1, p4)
   881  	&& disjoint(op, t1.Size(), p2, t2.Size())
   882  	&& disjoint(op, t1.Size(), p3, t3.Size())
   883  	=> mem
   884  (Store {t1} op:(OffPtr [o1] p1) x mem:(Store {t2} p2 _ (Store {t3} p3 _ (Store {t4} p4 _ (Zero [n] p5 _)))))
   885  	&& isConstZero(x)
   886  	&& o1 >= 0 && t1.Size() + o1 <= n && isSamePtr(p1, p5)
   887  	&& disjoint(op, t1.Size(), p2, t2.Size())
   888  	&& disjoint(op, t1.Size(), p3, t3.Size())
   889  	&& disjoint(op, t1.Size(), p4, t4.Size())
   890  	=> mem
   891  
   892  // Collapse OffPtr
   893  (OffPtr (OffPtr p [y]) [x]) => (OffPtr p [x+y])
   894  (OffPtr p [0]) && v.Type.Compare(p.Type) == types.CMPeq => p
   895  
   896  // indexing operations
   897  // Note: bounds check has already been done
   898  (PtrIndex <t> ptr idx) && config.PtrSize == 4 && is32Bit(t.Elem().Size()) => (AddPtr ptr (Mul32 <typ.Int> idx (Const32 <typ.Int> [int32(t.Elem().Size())])))
   899  (PtrIndex <t> ptr idx) && config.PtrSize == 8 => (AddPtr ptr (Mul64 <typ.Int> idx (Const64 <typ.Int> [t.Elem().Size()])))
   900  
   901  // struct operations
   902  (StructSelect [i] x:(StructMake ___)) => x.Args[i]
   903  (Load <t> _ _) && t.IsStruct() && CanSSA(t) => rewriteStructLoad(v)
   904  (Store _ (StructMake ___) _) => rewriteStructStore(v)
   905  
   906  (StructSelect [i] x:(Load <t> ptr mem)) && !CanSSA(t) =>
   907    @x.Block (Load <v.Type> (OffPtr <v.Type.PtrTo()> [t.FieldOff(int(i))] ptr) mem)
   908  
   909  // Putting struct{*byte} and similar into direct interfaces.
   910  (IMake _typ (StructMake val)) => (IMake _typ val)
   911  (StructSelect [0] (IData x)) => (IData x)
   912  
   913  // un-SSAable values use mem->mem copies
   914  (Store {t} dst (Load src mem) mem) && !CanSSA(t) =>
   915  	(Move {t} [t.Size()] dst src mem)
   916  (Store {t} dst (Load src mem) (VarDef {x} mem)) && !CanSSA(t) =>
   917  	(Move {t} [t.Size()] dst src (VarDef {x} mem))
   918  
   919  // array ops
   920  (ArraySelect (ArrayMake1 x)) => x
   921  
   922  (Load <t> _ _) && t.IsArray() && t.NumElem() == 0 =>
   923    (ArrayMake0)
   924  
   925  (Load <t> ptr mem) && t.IsArray() && t.NumElem() == 1 && CanSSA(t) =>
   926    (ArrayMake1 (Load <t.Elem()> ptr mem))
   927  
   928  (Store _ (ArrayMake0) mem) => mem
   929  (Store dst (ArrayMake1 e) mem) => (Store {e.Type} dst e mem)
   930  
   931  // Putting [1]*byte and similar into direct interfaces.
   932  (IMake _typ (ArrayMake1 val)) => (IMake _typ val)
   933  (ArraySelect [0] (IData x)) => (IData x)
   934  
   935  // string ops
   936  // Decomposing StringMake and lowering of StringPtr and StringLen
   937  // happens in a later pass, dec, so that these operations are available
   938  // to other passes for optimizations.
   939  (StringPtr (StringMake (Addr <t> {s} base) _)) => (Addr <t> {s} base)
   940  (StringLen (StringMake _ (Const64 <t> [c]))) => (Const64 <t> [c])
   941  (ConstString {str}) && config.PtrSize == 4 && str == "" =>
   942    (StringMake (ConstNil) (Const32 <typ.Int> [0]))
   943  (ConstString {str}) && config.PtrSize == 8 && str == "" =>
   944    (StringMake (ConstNil) (Const64 <typ.Int> [0]))
   945  (ConstString {str}) && config.PtrSize == 4 && str != "" =>
   946    (StringMake
   947      (Addr <typ.BytePtr> {fe.StringData(str)}
   948        (SB))
   949      (Const32 <typ.Int> [int32(len(str))]))
   950  (ConstString {str}) && config.PtrSize == 8 && str != "" =>
   951    (StringMake
   952      (Addr <typ.BytePtr> {fe.StringData(str)}
   953        (SB))
   954      (Const64 <typ.Int> [int64(len(str))]))
   955  
   956  // slice ops
   957  // Only a few slice rules are provided here.  See dec.rules for
   958  // a more comprehensive set.
   959  (SliceLen (SliceMake _ (Const64 <t> [c]) _)) => (Const64 <t> [c])
   960  (SliceCap (SliceMake _ _ (Const64 <t> [c]))) => (Const64 <t> [c])
   961  (SliceLen (SliceMake _ (Const32 <t> [c]) _)) => (Const32 <t> [c])
   962  (SliceCap (SliceMake _ _ (Const32 <t> [c]))) => (Const32 <t> [c])
   963  (SlicePtr (SliceMake (SlicePtr x) _ _)) => (SlicePtr x)
   964  (SliceLen (SliceMake _ (SliceLen x) _)) => (SliceLen x)
   965  (SliceCap (SliceMake _ _ (SliceCap x))) => (SliceCap x)
   966  (SliceCap (SliceMake _ _ (SliceLen x))) => (SliceLen x)
   967  (ConstSlice) && config.PtrSize == 4 =>
   968    (SliceMake
   969      (ConstNil <v.Type.Elem().PtrTo()>)
   970      (Const32 <typ.Int> [0])
   971      (Const32 <typ.Int> [0]))
   972  (ConstSlice) && config.PtrSize == 8 =>
   973    (SliceMake
   974      (ConstNil <v.Type.Elem().PtrTo()>)
   975      (Const64 <typ.Int> [0])
   976      (Const64 <typ.Int> [0]))
   977  
   978  // interface ops
   979  (ConstInterface) =>
   980    (IMake
   981      (ConstNil <typ.Uintptr>)
   982      (ConstNil <typ.BytePtr>))
   983  
   984  (NilCheck ptr:(GetG mem) mem) => ptr
   985  
   986  (If (Not cond) yes no) => (If cond no yes)
   987  (If (ConstBool [c]) yes no) && c => (First yes no)
   988  (If (ConstBool [c]) yes no) && !c => (First no yes)
   989  
   990  (Phi <t> nx:(Not x) ny:(Not y)) && nx.Uses == 1 && ny.Uses == 1 => (Not (Phi <t> x y))
   991  
   992  // Get rid of Convert ops for pointer arithmetic on unsafe.Pointer.
   993  (Convert (Add(64|32) (Convert ptr mem) off) mem) => (AddPtr ptr off)
   994  (Convert (Convert ptr mem) mem) => ptr
   995  // Note: it is important that the target rewrite is ptr+(off1+off2), not (ptr+off1)+off2.
   996  // We must ensure that no intermediate computations are invalid pointers.
   997  (Convert a:(Add(64|32) (Add(64|32) (Convert ptr mem) off1) off2) mem) => (AddPtr ptr (Add(64|32) <a.Type> off1 off2))
   998  
   999  // strength reduction of divide by a constant.
  1000  // See ../magic.go for a detailed description of these algorithms.
  1001  
  1002  // Unsigned divide by power of 2.  Strength reduce to a shift.
  1003  (Div8u  n (Const8  [c])) && isPowerOfTwo(c) => (Rsh8Ux64  n (Const64 <typ.UInt64> [log8(c)]))
  1004  (Div16u n (Const16 [c])) && isPowerOfTwo(c) => (Rsh16Ux64 n (Const64 <typ.UInt64> [log16(c)]))
  1005  (Div32u n (Const32 [c])) && isPowerOfTwo(c) => (Rsh32Ux64 n (Const64 <typ.UInt64> [log32(c)]))
  1006  (Div64u n (Const64 [c])) && isPowerOfTwo(c) => (Rsh64Ux64 n (Const64 <typ.UInt64> [log64(c)]))
  1007  (Div64u n (Const64 [-1<<63]))                 => (Rsh64Ux64 n (Const64 <typ.UInt64> [63]))
  1008  
  1009  // Signed non-negative divide by power of 2.
  1010  (Div8  n (Const8  [c])) && isNonNegative(n) && isPowerOfTwo(c) => (Rsh8Ux64  n (Const64 <typ.UInt64> [log8(c)]))
  1011  (Div16 n (Const16 [c])) && isNonNegative(n) && isPowerOfTwo(c) => (Rsh16Ux64 n (Const64 <typ.UInt64> [log16(c)]))
  1012  (Div32 n (Const32 [c])) && isNonNegative(n) && isPowerOfTwo(c) => (Rsh32Ux64 n (Const64 <typ.UInt64> [log32(c)]))
  1013  (Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c) => (Rsh64Ux64 n (Const64 <typ.UInt64> [log64(c)]))
  1014  (Div64 n (Const64 [-1<<63])) && isNonNegative(n)                 => (Const64 [0])
  1015  
  1016  // Unsigned divide, not a power of 2.  Strength reduce to a multiply.
  1017  // For 8-bit divides, we just do a direct 9-bit by 8-bit multiply.
  1018  (Div8u x (Const8 [c])) && umagicOK8(c) =>
  1019    (Trunc32to8
  1020      (Rsh32Ux64 <typ.UInt32>
  1021        (Mul32 <typ.UInt32>
  1022          (Const32 <typ.UInt32> [int32(1<<8+umagic8(c).m)])
  1023          (ZeroExt8to32 x))
  1024        (Const64 <typ.UInt64> [8+umagic8(c).s])))
  1025  
  1026  // For 16-bit divides on 64-bit machines, we do a direct 17-bit by 16-bit multiply.
  1027  (Div16u x (Const16 [c])) && umagicOK16(c) && config.RegSize == 8 =>
  1028    (Trunc64to16
  1029      (Rsh64Ux64 <typ.UInt64>
  1030        (Mul64 <typ.UInt64>
  1031          (Const64 <typ.UInt64> [int64(1<<16+umagic16(c).m)])
  1032          (ZeroExt16to64 x))
  1033        (Const64 <typ.UInt64> [16+umagic16(c).s])))
  1034  
  1035  // For 16-bit divides on 32-bit machines
  1036  (Div16u x (Const16 [c])) && umagicOK16(c) && config.RegSize == 4 && umagic16(c).m&1 == 0 =>
  1037    (Trunc32to16
  1038      (Rsh32Ux64 <typ.UInt32>
  1039        (Mul32 <typ.UInt32>
  1040          (Const32 <typ.UInt32> [int32(1<<15+umagic16(c).m/2)])
  1041          (ZeroExt16to32 x))
  1042        (Const64 <typ.UInt64> [16+umagic16(c).s-1])))
  1043  (Div16u x (Const16 [c])) && umagicOK16(c) && config.RegSize == 4 && c&1 == 0 =>
  1044    (Trunc32to16
  1045      (Rsh32Ux64 <typ.UInt32>
  1046        (Mul32 <typ.UInt32>
  1047          (Const32 <typ.UInt32> [int32(1<<15+(umagic16(c).m+1)/2)])
  1048          (Rsh32Ux64 <typ.UInt32> (ZeroExt16to32 x) (Const64 <typ.UInt64> [1])))
  1049        (Const64 <typ.UInt64> [16+umagic16(c).s-2])))
  1050  (Div16u x (Const16 [c])) && umagicOK16(c) && config.RegSize == 4 && config.useAvg =>
  1051    (Trunc32to16
  1052      (Rsh32Ux64 <typ.UInt32>
  1053        (Avg32u
  1054          (Lsh32x64 <typ.UInt32> (ZeroExt16to32 x) (Const64 <typ.UInt64> [16]))
  1055          (Mul32 <typ.UInt32>
  1056            (Const32 <typ.UInt32> [int32(umagic16(c).m)])
  1057            (ZeroExt16to32 x)))
  1058        (Const64 <typ.UInt64> [16+umagic16(c).s-1])))
  1059  
  1060  // For 32-bit divides on 32-bit machines
  1061  (Div32u x (Const32 [c])) && umagicOK32(c) && config.RegSize == 4 && umagic32(c).m&1 == 0 && config.useHmul =>
  1062    (Rsh32Ux64 <typ.UInt32>
  1063      (Hmul32u <typ.UInt32>
  1064        (Const32 <typ.UInt32> [int32(1<<31+umagic32(c).m/2)])
  1065        x)
  1066      (Const64 <typ.UInt64> [umagic32(c).s-1]))
  1067  (Div32u x (Const32 [c])) && umagicOK32(c) && config.RegSize == 4 && c&1 == 0 && config.useHmul =>
  1068    (Rsh32Ux64 <typ.UInt32>
  1069      (Hmul32u <typ.UInt32>
  1070        (Const32 <typ.UInt32> [int32(1<<31+(umagic32(c).m+1)/2)])
  1071        (Rsh32Ux64 <typ.UInt32> x (Const64 <typ.UInt64> [1])))
  1072      (Const64 <typ.UInt64> [umagic32(c).s-2]))
  1073  (Div32u x (Const32 [c])) && umagicOK32(c) && config.RegSize == 4 && config.useAvg && config.useHmul =>
  1074    (Rsh32Ux64 <typ.UInt32>
  1075      (Avg32u
  1076        x
  1077        (Hmul32u <typ.UInt32>
  1078          (Const32 <typ.UInt32> [int32(umagic32(c).m)])
  1079          x))
  1080      (Const64 <typ.UInt64> [umagic32(c).s-1]))
  1081  
  1082  // For 32-bit divides on 64-bit machines
  1083  // We'll use a regular (non-hi) multiply for this case.
  1084  (Div32u x (Const32 [c])) && umagicOK32(c) && config.RegSize == 8 && umagic32(c).m&1 == 0 =>
  1085    (Trunc64to32
  1086      (Rsh64Ux64 <typ.UInt64>
  1087        (Mul64 <typ.UInt64>
  1088          (Const64 <typ.UInt64> [int64(1<<31+umagic32(c).m/2)])
  1089          (ZeroExt32to64 x))
  1090        (Const64 <typ.UInt64> [32+umagic32(c).s-1])))
  1091  (Div32u x (Const32 [c])) && umagicOK32(c) && config.RegSize == 8 && c&1 == 0 =>
  1092    (Trunc64to32
  1093      (Rsh64Ux64 <typ.UInt64>
  1094        (Mul64 <typ.UInt64>
  1095          (Const64 <typ.UInt64> [int64(1<<31+(umagic32(c).m+1)/2)])
  1096          (Rsh64Ux64 <typ.UInt64> (ZeroExt32to64 x) (Const64 <typ.UInt64> [1])))
  1097        (Const64 <typ.UInt64> [32+umagic32(c).s-2])))
  1098  (Div32u x (Const32 [c])) && umagicOK32(c) && config.RegSize == 8 && config.useAvg =>
  1099    (Trunc64to32
  1100      (Rsh64Ux64 <typ.UInt64>
  1101        (Avg64u
  1102          (Lsh64x64 <typ.UInt64> (ZeroExt32to64 x) (Const64 <typ.UInt64> [32]))
  1103          (Mul64 <typ.UInt64>
  1104            (Const64 <typ.UInt32> [int64(umagic32(c).m)])
  1105            (ZeroExt32to64 x)))
  1106        (Const64 <typ.UInt64> [32+umagic32(c).s-1])))
  1107  
  1108  // For unsigned 64-bit divides on 32-bit machines,
  1109  // if the constant fits in 16 bits (so that the last term
  1110  // fits in 32 bits), convert to three 32-bit divides by a constant.
  1111  //
  1112  // If 1<<32 = Q * c + R
  1113  // and    x = hi << 32 + lo
  1114  //
  1115  // Then x = (hi/c*c + hi%c) << 32 + lo
  1116  //        = hi/c*c<<32 + hi%c<<32 + lo
  1117  //        = hi/c*c<<32 + (hi%c)*(Q*c+R) + lo/c*c + lo%c
  1118  //        = hi/c*c<<32 + (hi%c)*Q*c + lo/c*c + (hi%c*R+lo%c)
  1119  // and x / c = (hi/c)<<32 + (hi%c)*Q + lo/c + (hi%c*R+lo%c)/c
  1120  (Div64u x (Const64 [c])) && c > 0 && c <= 0xFFFF && umagicOK32(int32(c)) && config.RegSize == 4 && config.useHmul =>
  1121    (Add64
  1122      (Add64 <typ.UInt64>
  1123        (Add64 <typ.UInt64>
  1124          (Lsh64x64 <typ.UInt64>
  1125            (ZeroExt32to64
  1126              (Div32u <typ.UInt32>
  1127                (Trunc64to32 <typ.UInt32> (Rsh64Ux64 <typ.UInt64> x (Const64 <typ.UInt64> [32])))
  1128                (Const32 <typ.UInt32> [int32(c)])))
  1129            (Const64 <typ.UInt64> [32]))
  1130          (ZeroExt32to64 (Div32u <typ.UInt32> (Trunc64to32 <typ.UInt32> x) (Const32 <typ.UInt32> [int32(c)]))))
  1131        (Mul64 <typ.UInt64>
  1132          (ZeroExt32to64 <typ.UInt64>
  1133            (Mod32u <typ.UInt32>
  1134              (Trunc64to32 <typ.UInt32> (Rsh64Ux64 <typ.UInt64> x (Const64 <typ.UInt64> [32])))
  1135              (Const32 <typ.UInt32> [int32(c)])))
  1136          (Const64 <typ.UInt64> [int64((1<<32)/c)])))
  1137        (ZeroExt32to64
  1138          (Div32u <typ.UInt32>
  1139            (Add32 <typ.UInt32>
  1140              (Mod32u <typ.UInt32> (Trunc64to32 <typ.UInt32> x) (Const32 <typ.UInt32> [int32(c)]))
  1141              (Mul32 <typ.UInt32>
  1142                (Mod32u <typ.UInt32>
  1143                  (Trunc64to32 <typ.UInt32> (Rsh64Ux64 <typ.UInt64> x (Const64 <typ.UInt64> [32])))
  1144                  (Const32 <typ.UInt32> [int32(c)]))
  1145                (Const32 <typ.UInt32> [int32((1<<32)%c)])))
  1146            (Const32 <typ.UInt32> [int32(c)]))))
  1147  
  1148  // For 64-bit divides on 64-bit machines
  1149  // (64-bit divides on 32-bit machines are lowered to a runtime call by the walk pass.)
  1150  (Div64u x (Const64 [c])) && umagicOK64(c) && config.RegSize == 8 && umagic64(c).m&1 == 0 && config.useHmul =>
  1151    (Rsh64Ux64 <typ.UInt64>
  1152      (Hmul64u <typ.UInt64>
  1153        (Const64 <typ.UInt64> [int64(1<<63+umagic64(c).m/2)])
  1154        x)
  1155      (Const64 <typ.UInt64> [umagic64(c).s-1]))
  1156  (Div64u x (Const64 [c])) && umagicOK64(c) && config.RegSize == 8 && c&1 == 0 && config.useHmul =>
  1157    (Rsh64Ux64 <typ.UInt64>
  1158      (Hmul64u <typ.UInt64>
  1159        (Const64 <typ.UInt64> [int64(1<<63+(umagic64(c).m+1)/2)])
  1160        (Rsh64Ux64 <typ.UInt64> x (Const64 <typ.UInt64> [1])))
  1161      (Const64 <typ.UInt64> [umagic64(c).s-2]))
  1162  (Div64u x (Const64 [c])) && umagicOK64(c) && config.RegSize == 8 && config.useAvg && config.useHmul =>
  1163    (Rsh64Ux64 <typ.UInt64>
  1164      (Avg64u
  1165        x
  1166        (Hmul64u <typ.UInt64>
  1167          (Const64 <typ.UInt64> [int64(umagic64(c).m)])
  1168          x))
  1169      (Const64 <typ.UInt64> [umagic64(c).s-1]))
  1170  
  1171  // Signed divide by a negative constant.  Rewrite to divide by a positive constant.
  1172  (Div8  <t> n (Const8  [c])) && c < 0 && c != -1<<7  => (Neg8  (Div8  <t> n (Const8  <t> [-c])))
  1173  (Div16 <t> n (Const16 [c])) && c < 0 && c != -1<<15 => (Neg16 (Div16 <t> n (Const16 <t> [-c])))
  1174  (Div32 <t> n (Const32 [c])) && c < 0 && c != -1<<31 => (Neg32 (Div32 <t> n (Const32 <t> [-c])))
  1175  (Div64 <t> n (Const64 [c])) && c < 0 && c != -1<<63 => (Neg64 (Div64 <t> n (Const64 <t> [-c])))
  1176  
  1177  // Dividing by the most-negative number.  Result is always 0 except
  1178  // if the input is also the most-negative number.
  1179  // We can detect that using the sign bit of x & -x.
  1180  (Div8  <t> x (Const8  [-1<<7 ])) => (Rsh8Ux64  (And8  <t> x (Neg8  <t> x)) (Const64 <typ.UInt64> [7 ]))
  1181  (Div16 <t> x (Const16 [-1<<15])) => (Rsh16Ux64 (And16 <t> x (Neg16 <t> x)) (Const64 <typ.UInt64> [15]))
  1182  (Div32 <t> x (Const32 [-1<<31])) => (Rsh32Ux64 (And32 <t> x (Neg32 <t> x)) (Const64 <typ.UInt64> [31]))
  1183  (Div64 <t> x (Const64 [-1<<63])) => (Rsh64Ux64 (And64 <t> x (Neg64 <t> x)) (Const64 <typ.UInt64> [63]))
  1184  
  1185  // Signed divide by power of 2.
  1186  // n / c =       n >> log(c) if n >= 0
  1187  //       = (n+c-1) >> log(c) if n < 0
  1188  // We conditionally add c-1 by adding n>>63>>(64-log(c)) (first shift signed, second shift unsigned).
  1189  (Div8  <t> n (Const8  [c])) && isPowerOfTwo(c) =>
  1190    (Rsh8x64
  1191      (Add8  <t> n (Rsh8Ux64  <t> (Rsh8x64  <t> n (Const64 <typ.UInt64> [ 7])) (Const64 <typ.UInt64> [int64( 8-log8(c))])))
  1192      (Const64 <typ.UInt64> [int64(log8(c))]))
  1193  (Div16 <t> n (Const16 [c])) && isPowerOfTwo(c) =>
  1194    (Rsh16x64
  1195      (Add16 <t> n (Rsh16Ux64 <t> (Rsh16x64 <t> n (Const64 <typ.UInt64> [15])) (Const64 <typ.UInt64> [int64(16-log16(c))])))
  1196      (Const64 <typ.UInt64> [int64(log16(c))]))
  1197  (Div32 <t> n (Const32 [c])) && isPowerOfTwo(c) =>
  1198    (Rsh32x64
  1199      (Add32 <t> n (Rsh32Ux64 <t> (Rsh32x64 <t> n (Const64 <typ.UInt64> [31])) (Const64 <typ.UInt64> [int64(32-log32(c))])))
  1200      (Const64 <typ.UInt64> [int64(log32(c))]))
  1201  (Div64 <t> n (Const64 [c])) && isPowerOfTwo(c) =>
  1202    (Rsh64x64
  1203      (Add64 <t> n (Rsh64Ux64 <t> (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) (Const64 <typ.UInt64> [int64(64-log64(c))])))
  1204      (Const64 <typ.UInt64> [int64(log64(c))]))
  1205  
  1206  // Signed divide, not a power of 2.  Strength reduce to a multiply.
  1207  (Div8 <t> x (Const8 [c])) && smagicOK8(c) =>
  1208    (Sub8 <t>
  1209      (Rsh32x64 <t>
  1210        (Mul32 <typ.UInt32>
  1211          (Const32 <typ.UInt32> [int32(smagic8(c).m)])
  1212          (SignExt8to32 x))
  1213        (Const64 <typ.UInt64> [8+smagic8(c).s]))
  1214      (Rsh32x64 <t>
  1215        (SignExt8to32 x)
  1216        (Const64 <typ.UInt64> [31])))
  1217  (Div16 <t> x (Const16 [c])) && smagicOK16(c) =>
  1218    (Sub16 <t>
  1219      (Rsh32x64 <t>
  1220        (Mul32 <typ.UInt32>
  1221          (Const32 <typ.UInt32> [int32(smagic16(c).m)])
  1222          (SignExt16to32 x))
  1223        (Const64 <typ.UInt64> [16+smagic16(c).s]))
  1224      (Rsh32x64 <t>
  1225        (SignExt16to32 x)
  1226        (Const64 <typ.UInt64> [31])))
  1227  (Div32 <t> x (Const32 [c])) && smagicOK32(c) && config.RegSize == 8 =>
  1228    (Sub32 <t>
  1229      (Rsh64x64 <t>
  1230        (Mul64 <typ.UInt64>
  1231          (Const64 <typ.UInt64> [int64(smagic32(c).m)])
  1232          (SignExt32to64 x))
  1233        (Const64 <typ.UInt64> [32+smagic32(c).s]))
  1234      (Rsh64x64 <t>
  1235        (SignExt32to64 x)
  1236        (Const64 <typ.UInt64> [63])))
  1237  (Div32 <t> x (Const32 [c])) && smagicOK32(c) && config.RegSize == 4 && smagic32(c).m&1 == 0 && config.useHmul =>
  1238    (Sub32 <t>
  1239      (Rsh32x64 <t>
  1240        (Hmul32 <t>
  1241          (Const32 <typ.UInt32> [int32(smagic32(c).m/2)])
  1242          x)
  1243        (Const64 <typ.UInt64> [smagic32(c).s-1]))
  1244      (Rsh32x64 <t>
  1245        x
  1246        (Const64 <typ.UInt64> [31])))
  1247  (Div32 <t> x (Const32 [c])) && smagicOK32(c) && config.RegSize == 4 && smagic32(c).m&1 != 0 && config.useHmul =>
  1248    (Sub32 <t>
  1249      (Rsh32x64 <t>
  1250        (Add32 <t>
  1251          (Hmul32 <t>
  1252            (Const32 <typ.UInt32> [int32(smagic32(c).m)])
  1253            x)
  1254          x)
  1255        (Const64 <typ.UInt64> [smagic32(c).s]))
  1256      (Rsh32x64 <t>
  1257        x
  1258        (Const64 <typ.UInt64> [31])))
  1259  (Div64 <t> x (Const64 [c])) && smagicOK64(c) && smagic64(c).m&1 == 0 && config.useHmul =>
  1260    (Sub64 <t>
  1261      (Rsh64x64 <t>
  1262        (Hmul64 <t>
  1263          (Const64 <typ.UInt64> [int64(smagic64(c).m/2)])
  1264          x)
  1265        (Const64 <typ.UInt64> [smagic64(c).s-1]))
  1266      (Rsh64x64 <t>
  1267        x
  1268        (Const64 <typ.UInt64> [63])))
  1269  (Div64 <t> x (Const64 [c])) && smagicOK64(c) && smagic64(c).m&1 != 0 && config.useHmul =>
  1270    (Sub64 <t>
  1271      (Rsh64x64 <t>
  1272        (Add64 <t>
  1273          (Hmul64 <t>
  1274            (Const64 <typ.UInt64> [int64(smagic64(c).m)])
  1275            x)
  1276          x)
  1277        (Const64 <typ.UInt64> [smagic64(c).s]))
  1278      (Rsh64x64 <t>
  1279        x
  1280        (Const64 <typ.UInt64> [63])))
  1281  
  1282  // Unsigned mod by power of 2 constant.
  1283  (Mod8u  <t> n (Const8  [c])) && isPowerOfTwo(c) => (And8  n (Const8  <t> [c-1]))
  1284  (Mod16u <t> n (Const16 [c])) && isPowerOfTwo(c) => (And16 n (Const16 <t> [c-1]))
  1285  (Mod32u <t> n (Const32 [c])) && isPowerOfTwo(c) => (And32 n (Const32 <t> [c-1]))
  1286  (Mod64u <t> n (Const64 [c])) && isPowerOfTwo(c) => (And64 n (Const64 <t> [c-1]))
  1287  (Mod64u <t> n (Const64 [-1<<63]))                 => (And64 n (Const64 <t> [1<<63-1]))
  1288  
  1289  // Signed non-negative mod by power of 2 constant.
  1290  (Mod8  <t> n (Const8  [c])) && isNonNegative(n) && isPowerOfTwo(c) => (And8  n (Const8  <t> [c-1]))
  1291  (Mod16 <t> n (Const16 [c])) && isNonNegative(n) && isPowerOfTwo(c) => (And16 n (Const16 <t> [c-1]))
  1292  (Mod32 <t> n (Const32 [c])) && isNonNegative(n) && isPowerOfTwo(c) => (And32 n (Const32 <t> [c-1]))
  1293  (Mod64 <t> n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo(c) => (And64 n (Const64 <t> [c-1]))
  1294  (Mod64 n (Const64 [-1<<63])) && isNonNegative(n)                   => n
  1295  
  1296  // Signed mod by negative constant.
  1297  (Mod8  <t> n (Const8  [c])) && c < 0 && c != -1<<7  => (Mod8  <t> n (Const8  <t> [-c]))
  1298  (Mod16 <t> n (Const16 [c])) && c < 0 && c != -1<<15 => (Mod16 <t> n (Const16 <t> [-c]))
  1299  (Mod32 <t> n (Const32 [c])) && c < 0 && c != -1<<31 => (Mod32 <t> n (Const32 <t> [-c]))
  1300  (Mod64 <t> n (Const64 [c])) && c < 0 && c != -1<<63 => (Mod64 <t> n (Const64 <t> [-c]))
  1301  
  1302  // All other mods by constants, do A%B = A-(A/B*B).
  1303  // This implements % with two * and a bunch of ancillary ops.
  1304  // One of the * is free if the user's code also computes A/B.
  1305  (Mod8   <t> x (Const8  [c])) && x.Op != OpConst8  && (c > 0 || c == -1<<7)
  1306    => (Sub8  x (Mul8  <t> (Div8   <t> x (Const8  <t> [c])) (Const8  <t> [c])))
  1307  (Mod16  <t> x (Const16 [c])) && x.Op != OpConst16 && (c > 0 || c == -1<<15)
  1308    => (Sub16 x (Mul16 <t> (Div16  <t> x (Const16 <t> [c])) (Const16 <t> [c])))
  1309  (Mod32  <t> x (Const32 [c])) && x.Op != OpConst32 && (c > 0 || c == -1<<31)
  1310    => (Sub32 x (Mul32 <t> (Div32  <t> x (Const32 <t> [c])) (Const32 <t> [c])))
  1311  (Mod64  <t> x (Const64 [c])) && x.Op != OpConst64 && (c > 0 || c == -1<<63)
  1312    => (Sub64 x (Mul64 <t> (Div64  <t> x (Const64 <t> [c])) (Const64 <t> [c])))
  1313  (Mod8u  <t> x (Const8  [c])) && x.Op != OpConst8  && c > 0 && umagicOK8( c)
  1314    => (Sub8  x (Mul8  <t> (Div8u  <t> x (Const8  <t> [c])) (Const8  <t> [c])))
  1315  (Mod16u <t> x (Const16 [c])) && x.Op != OpConst16 && c > 0 && umagicOK16(c)
  1316    => (Sub16 x (Mul16 <t> (Div16u <t> x (Const16 <t> [c])) (Const16 <t> [c])))
  1317  (Mod32u <t> x (Const32 [c])) && x.Op != OpConst32 && c > 0 && umagicOK32(c)
  1318    => (Sub32 x (Mul32 <t> (Div32u <t> x (Const32 <t> [c])) (Const32 <t> [c])))
  1319  (Mod64u <t> x (Const64 [c])) && x.Op != OpConst64 && c > 0 && umagicOK64(c)
  1320    => (Sub64 x (Mul64 <t> (Div64u <t> x (Const64 <t> [c])) (Const64 <t> [c])))
  1321  
  1322  // For architectures without rotates on less than 32-bits, promote these checks to 32-bit.
  1323  (Eq8 (Mod8u x (Const8  [c])) (Const8 [0])) && x.Op != OpConst8 && udivisibleOK8(c) && !hasSmallRotate(config) =>
  1324  	(Eq32 (Mod32u <typ.UInt32> (ZeroExt8to32 <typ.UInt32> x) (Const32 <typ.UInt32> [int32(uint8(c))])) (Const32 <typ.UInt32> [0]))
  1325  (Eq16 (Mod16u x (Const16  [c])) (Const16 [0])) && x.Op != OpConst16 && udivisibleOK16(c) && !hasSmallRotate(config) =>
  1326  	(Eq32 (Mod32u <typ.UInt32> (ZeroExt16to32 <typ.UInt32> x) (Const32 <typ.UInt32> [int32(uint16(c))])) (Const32 <typ.UInt32> [0]))
  1327  (Eq8 (Mod8 x (Const8  [c])) (Const8 [0])) && x.Op != OpConst8 && sdivisibleOK8(c) && !hasSmallRotate(config) =>
  1328  	(Eq32 (Mod32 <typ.Int32> (SignExt8to32 <typ.Int32> x) (Const32 <typ.Int32> [int32(c)])) (Const32 <typ.Int32> [0]))
  1329  (Eq16 (Mod16 x (Const16  [c])) (Const16 [0])) && x.Op != OpConst16 && sdivisibleOK16(c) && !hasSmallRotate(config) =>
  1330  	(Eq32 (Mod32 <typ.Int32> (SignExt16to32 <typ.Int32> x) (Const32 <typ.Int32> [int32(c)])) (Const32 <typ.Int32> [0]))
  1331  
  1332  // Divisibility checks x%c == 0 convert to multiply and rotate.
  1333  // Note, x%c == 0 is rewritten as x == c*(x/c) during the opt pass
  1334  // where (x/c) is performed using multiplication with magic constants.
  1335  // To rewrite x%c == 0 requires pattern matching the rewritten expression
  1336  // and checking that the division by the same constant wasn't already calculated.
  1337  // This check is made by counting uses of the magic constant multiplication.
  1338  // Note that if there were an intermediate opt pass, this rule could be applied
  1339  // directly on the Div op and magic division rewrites could be delayed to late opt.
  1340  
  1341  // Unsigned divisibility checks convert to multiply and rotate.
  1342  (Eq8 x (Mul8 (Const8 [c])
  1343    (Trunc32to8
  1344      (Rsh32Ux64
  1345        mul:(Mul32
  1346          (Const32 [m])
  1347          (ZeroExt8to32 x))
  1348        (Const64 [s])))
  1349  	)
  1350  )
  1351    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1352    && m == int32(1<<8+umagic8(c).m) && s == 8+umagic8(c).s
  1353    && x.Op != OpConst8 && udivisibleOK8(c)
  1354   => (Leq8U
  1355  			(RotateLeft8 <typ.UInt8>
  1356  				(Mul8 <typ.UInt8>
  1357  					(Const8 <typ.UInt8> [int8(udivisible8(c).m)])
  1358  					x)
  1359  				(Const8 <typ.UInt8> [int8(8-udivisible8(c).k)])
  1360  				)
  1361  			(Const8 <typ.UInt8> [int8(udivisible8(c).max)])
  1362  		)
  1363  
  1364  (Eq16 x (Mul16 (Const16 [c])
  1365    (Trunc64to16
  1366      (Rsh64Ux64
  1367        mul:(Mul64
  1368          (Const64 [m])
  1369          (ZeroExt16to64 x))
  1370        (Const64 [s])))
  1371  	)
  1372  )
  1373    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1374    && m == int64(1<<16+umagic16(c).m) && s == 16+umagic16(c).s
  1375    && x.Op != OpConst16 && udivisibleOK16(c)
  1376   => (Leq16U
  1377  			(RotateLeft16 <typ.UInt16>
  1378  				(Mul16 <typ.UInt16>
  1379  					(Const16 <typ.UInt16> [int16(udivisible16(c).m)])
  1380  					x)
  1381  				(Const16 <typ.UInt16> [int16(16-udivisible16(c).k)])
  1382  				)
  1383  			(Const16 <typ.UInt16> [int16(udivisible16(c).max)])
  1384  		)
  1385  
  1386  (Eq16 x (Mul16 (Const16 [c])
  1387    (Trunc32to16
  1388      (Rsh32Ux64
  1389        mul:(Mul32
  1390          (Const32 [m])
  1391          (ZeroExt16to32 x))
  1392        (Const64 [s])))
  1393  	)
  1394  )
  1395    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1396    && m == int32(1<<15+umagic16(c).m/2) && s == 16+umagic16(c).s-1
  1397    && x.Op != OpConst16 && udivisibleOK16(c)
  1398   => (Leq16U
  1399  			(RotateLeft16 <typ.UInt16>
  1400  				(Mul16 <typ.UInt16>
  1401  					(Const16 <typ.UInt16> [int16(udivisible16(c).m)])
  1402  					x)
  1403  				(Const16 <typ.UInt16> [int16(16-udivisible16(c).k)])
  1404  				)
  1405  			(Const16 <typ.UInt16> [int16(udivisible16(c).max)])
  1406  		)
  1407  
  1408  (Eq16 x (Mul16 (Const16 [c])
  1409    (Trunc32to16
  1410      (Rsh32Ux64
  1411        mul:(Mul32
  1412          (Const32 [m])
  1413          (Rsh32Ux64 (ZeroExt16to32 x) (Const64 [1])))
  1414        (Const64 [s])))
  1415  	)
  1416  )
  1417    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1418    && m == int32(1<<15+(umagic16(c).m+1)/2) && s == 16+umagic16(c).s-2
  1419    && x.Op != OpConst16 && udivisibleOK16(c)
  1420   => (Leq16U
  1421  			(RotateLeft16 <typ.UInt16>
  1422  				(Mul16 <typ.UInt16>
  1423  					(Const16 <typ.UInt16> [int16(udivisible16(c).m)])
  1424  					x)
  1425  				(Const16 <typ.UInt16> [int16(16-udivisible16(c).k)])
  1426  				)
  1427  			(Const16 <typ.UInt16> [int16(udivisible16(c).max)])
  1428  		)
  1429  
  1430  (Eq16 x (Mul16 (Const16 [c])
  1431    (Trunc32to16
  1432      (Rsh32Ux64
  1433        (Avg32u
  1434          (Lsh32x64 (ZeroExt16to32 x) (Const64 [16]))
  1435          mul:(Mul32
  1436            (Const32 [m])
  1437            (ZeroExt16to32 x)))
  1438        (Const64 [s])))
  1439  	)
  1440  )
  1441    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1442    && m == int32(umagic16(c).m) && s == 16+umagic16(c).s-1
  1443    && x.Op != OpConst16 && udivisibleOK16(c)
  1444   => (Leq16U
  1445  			(RotateLeft16 <typ.UInt16>
  1446  				(Mul16 <typ.UInt16>
  1447  					(Const16 <typ.UInt16> [int16(udivisible16(c).m)])
  1448  					x)
  1449  				(Const16 <typ.UInt16> [int16(16-udivisible16(c).k)])
  1450  				)
  1451  			(Const16 <typ.UInt16> [int16(udivisible16(c).max)])
  1452  		)
  1453  
  1454  (Eq32 x (Mul32 (Const32 [c])
  1455  	(Rsh32Ux64
  1456  		mul:(Hmul32u
  1457  			(Const32 [m])
  1458  			x)
  1459  		(Const64 [s]))
  1460  	)
  1461  )
  1462    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1463    && m == int32(1<<31+umagic32(c).m/2) && s == umagic32(c).s-1
  1464  	&& x.Op != OpConst32 && udivisibleOK32(c)
  1465   => (Leq32U
  1466  			(RotateLeft32 <typ.UInt32>
  1467  				(Mul32 <typ.UInt32>
  1468  					(Const32 <typ.UInt32> [int32(udivisible32(c).m)])
  1469  					x)
  1470  				(Const32 <typ.UInt32> [int32(32-udivisible32(c).k)])
  1471  				)
  1472  			(Const32 <typ.UInt32> [int32(udivisible32(c).max)])
  1473  		)
  1474  
  1475  (Eq32 x (Mul32 (Const32 [c])
  1476    (Rsh32Ux64
  1477      mul:(Hmul32u
  1478        (Const32 <typ.UInt32> [m])
  1479        (Rsh32Ux64 x (Const64 [1])))
  1480      (Const64 [s]))
  1481  	)
  1482  )
  1483    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1484    && m == int32(1<<31+(umagic32(c).m+1)/2) && s == umagic32(c).s-2
  1485  	&& x.Op != OpConst32 && udivisibleOK32(c)
  1486   => (Leq32U
  1487  			(RotateLeft32 <typ.UInt32>
  1488  				(Mul32 <typ.UInt32>
  1489  					(Const32 <typ.UInt32> [int32(udivisible32(c).m)])
  1490  					x)
  1491  				(Const32 <typ.UInt32> [int32(32-udivisible32(c).k)])
  1492  				)
  1493  			(Const32 <typ.UInt32> [int32(udivisible32(c).max)])
  1494  		)
  1495  
  1496  (Eq32 x (Mul32 (Const32 [c])
  1497    (Rsh32Ux64
  1498      (Avg32u
  1499        x
  1500        mul:(Hmul32u
  1501          (Const32 [m])
  1502          x))
  1503      (Const64 [s]))
  1504  	)
  1505  )
  1506    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1507    && m == int32(umagic32(c).m) && s == umagic32(c).s-1
  1508  	&& x.Op != OpConst32 && udivisibleOK32(c)
  1509   => (Leq32U
  1510  			(RotateLeft32 <typ.UInt32>
  1511  				(Mul32 <typ.UInt32>
  1512  					(Const32 <typ.UInt32> [int32(udivisible32(c).m)])
  1513  					x)
  1514  				(Const32 <typ.UInt32> [int32(32-udivisible32(c).k)])
  1515  				)
  1516  			(Const32 <typ.UInt32> [int32(udivisible32(c).max)])
  1517  		)
  1518  
  1519  (Eq32 x (Mul32 (Const32 [c])
  1520    (Trunc64to32
  1521      (Rsh64Ux64
  1522        mul:(Mul64
  1523          (Const64 [m])
  1524          (ZeroExt32to64 x))
  1525        (Const64 [s])))
  1526  	)
  1527  )
  1528    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1529    && m == int64(1<<31+umagic32(c).m/2) && s == 32+umagic32(c).s-1
  1530  	&& x.Op != OpConst32 && udivisibleOK32(c)
  1531   => (Leq32U
  1532  			(RotateLeft32 <typ.UInt32>
  1533  				(Mul32 <typ.UInt32>
  1534  					(Const32 <typ.UInt32> [int32(udivisible32(c).m)])
  1535  					x)
  1536  				(Const32 <typ.UInt32> [int32(32-udivisible32(c).k)])
  1537  				)
  1538  			(Const32 <typ.UInt32> [int32(udivisible32(c).max)])
  1539  		)
  1540  
  1541  (Eq32 x (Mul32 (Const32 [c])
  1542    (Trunc64to32
  1543      (Rsh64Ux64
  1544        mul:(Mul64
  1545          (Const64 [m])
  1546          (Rsh64Ux64 (ZeroExt32to64 x) (Const64 [1])))
  1547        (Const64 [s])))
  1548  	)
  1549  )
  1550    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1551    && m == int64(1<<31+(umagic32(c).m+1)/2) && s == 32+umagic32(c).s-2
  1552  	&& x.Op != OpConst32 && udivisibleOK32(c)
  1553   => (Leq32U
  1554  			(RotateLeft32 <typ.UInt32>
  1555  				(Mul32 <typ.UInt32>
  1556  					(Const32 <typ.UInt32> [int32(udivisible32(c).m)])
  1557  					x)
  1558  				(Const32 <typ.UInt32> [int32(32-udivisible32(c).k)])
  1559  				)
  1560  			(Const32 <typ.UInt32> [int32(udivisible32(c).max)])
  1561  		)
  1562  
  1563  (Eq32 x (Mul32 (Const32 [c])
  1564    (Trunc64to32
  1565      (Rsh64Ux64
  1566        (Avg64u
  1567          (Lsh64x64 (ZeroExt32to64 x) (Const64 [32]))
  1568          mul:(Mul64
  1569            (Const64 [m])
  1570            (ZeroExt32to64 x)))
  1571        (Const64 [s])))
  1572  	)
  1573  )
  1574    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1575    && m == int64(umagic32(c).m) && s == 32+umagic32(c).s-1
  1576  	&& x.Op != OpConst32 && udivisibleOK32(c)
  1577   => (Leq32U
  1578  			(RotateLeft32 <typ.UInt32>
  1579  				(Mul32 <typ.UInt32>
  1580  					(Const32 <typ.UInt32> [int32(udivisible32(c).m)])
  1581  					x)
  1582  				(Const32 <typ.UInt32> [int32(32-udivisible32(c).k)])
  1583  				)
  1584  			(Const32 <typ.UInt32> [int32(udivisible32(c).max)])
  1585  		)
  1586  
  1587  (Eq64 x (Mul64 (Const64 [c])
  1588  	(Rsh64Ux64
  1589  		mul:(Hmul64u
  1590  			(Const64 [m])
  1591  			x)
  1592  		(Const64 [s]))
  1593  	)
  1594  ) && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1595    && m == int64(1<<63+umagic64(c).m/2) && s == umagic64(c).s-1
  1596    && x.Op != OpConst64 && udivisibleOK64(c)
  1597   => (Leq64U
  1598  			(RotateLeft64 <typ.UInt64>
  1599  				(Mul64 <typ.UInt64>
  1600  					(Const64 <typ.UInt64> [int64(udivisible64(c).m)])
  1601  					x)
  1602  				(Const64 <typ.UInt64> [64-udivisible64(c).k])
  1603  				)
  1604  			(Const64 <typ.UInt64> [int64(udivisible64(c).max)])
  1605  		)
  1606  (Eq64 x (Mul64 (Const64 [c])
  1607  	(Rsh64Ux64
  1608  		mul:(Hmul64u
  1609  			(Const64 [m])
  1610  			(Rsh64Ux64 x (Const64 [1])))
  1611  		(Const64 [s]))
  1612  	)
  1613  ) && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1614    && m == int64(1<<63+(umagic64(c).m+1)/2) && s == umagic64(c).s-2
  1615    && x.Op != OpConst64 && udivisibleOK64(c)
  1616   => (Leq64U
  1617  			(RotateLeft64 <typ.UInt64>
  1618  				(Mul64 <typ.UInt64>
  1619  					(Const64 <typ.UInt64> [int64(udivisible64(c).m)])
  1620  					x)
  1621  				(Const64 <typ.UInt64> [64-udivisible64(c).k])
  1622  				)
  1623  			(Const64 <typ.UInt64> [int64(udivisible64(c).max)])
  1624  		)
  1625  (Eq64 x (Mul64 (Const64 [c])
  1626  	(Rsh64Ux64
  1627  		(Avg64u
  1628  			x
  1629  			mul:(Hmul64u
  1630  				(Const64 [m])
  1631  				x))
  1632  		(Const64 [s]))
  1633  	)
  1634  ) && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1635    && m == int64(umagic64(c).m) && s == umagic64(c).s-1
  1636    && x.Op != OpConst64 && udivisibleOK64(c)
  1637   => (Leq64U
  1638  			(RotateLeft64 <typ.UInt64>
  1639  				(Mul64 <typ.UInt64>
  1640  					(Const64 <typ.UInt64> [int64(udivisible64(c).m)])
  1641  					x)
  1642  				(Const64 <typ.UInt64> [64-udivisible64(c).k])
  1643  				)
  1644  			(Const64 <typ.UInt64> [int64(udivisible64(c).max)])
  1645  		)
  1646  
  1647  // Signed divisibility checks convert to multiply, add and rotate.
  1648  (Eq8 x (Mul8 (Const8 [c])
  1649    (Sub8
  1650      (Rsh32x64
  1651        mul:(Mul32
  1652          (Const32 [m])
  1653          (SignExt8to32 x))
  1654        (Const64 [s]))
  1655      (Rsh32x64
  1656        (SignExt8to32 x)
  1657        (Const64 [31])))
  1658  	)
  1659  )
  1660    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1661    && m == int32(smagic8(c).m) && s == 8+smagic8(c).s
  1662  	&& x.Op != OpConst8 && sdivisibleOK8(c)
  1663   => (Leq8U
  1664  			(RotateLeft8 <typ.UInt8>
  1665  				(Add8 <typ.UInt8>
  1666  					(Mul8 <typ.UInt8>
  1667  						(Const8 <typ.UInt8> [int8(sdivisible8(c).m)])
  1668  						x)
  1669  					(Const8 <typ.UInt8> [int8(sdivisible8(c).a)])
  1670  				)
  1671  				(Const8 <typ.UInt8> [int8(8-sdivisible8(c).k)])
  1672  			)
  1673  			(Const8 <typ.UInt8> [int8(sdivisible8(c).max)])
  1674  		)
  1675  
  1676  (Eq16 x (Mul16 (Const16 [c])
  1677    (Sub16
  1678      (Rsh32x64
  1679        mul:(Mul32
  1680          (Const32 [m])
  1681          (SignExt16to32 x))
  1682        (Const64 [s]))
  1683      (Rsh32x64
  1684        (SignExt16to32 x)
  1685        (Const64 [31])))
  1686  	)
  1687  )
  1688    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1689    && m == int32(smagic16(c).m) && s == 16+smagic16(c).s
  1690  	&& x.Op != OpConst16 && sdivisibleOK16(c)
  1691   => (Leq16U
  1692  			(RotateLeft16 <typ.UInt16>
  1693  				(Add16 <typ.UInt16>
  1694  					(Mul16 <typ.UInt16>
  1695  						(Const16 <typ.UInt16> [int16(sdivisible16(c).m)])
  1696  						x)
  1697  					(Const16 <typ.UInt16> [int16(sdivisible16(c).a)])
  1698  				)
  1699  				(Const16 <typ.UInt16> [int16(16-sdivisible16(c).k)])
  1700  			)
  1701  			(Const16 <typ.UInt16> [int16(sdivisible16(c).max)])
  1702  		)
  1703  
  1704  (Eq32 x (Mul32 (Const32 [c])
  1705    (Sub32
  1706      (Rsh64x64
  1707        mul:(Mul64
  1708          (Const64 [m])
  1709          (SignExt32to64 x))
  1710        (Const64 [s]))
  1711      (Rsh64x64
  1712        (SignExt32to64 x)
  1713        (Const64 [63])))
  1714  	)
  1715  )
  1716    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1717    && m == int64(smagic32(c).m) && s == 32+smagic32(c).s
  1718  	&& x.Op != OpConst32 && sdivisibleOK32(c)
  1719   => (Leq32U
  1720  			(RotateLeft32 <typ.UInt32>
  1721  				(Add32 <typ.UInt32>
  1722  					(Mul32 <typ.UInt32>
  1723  						(Const32 <typ.UInt32> [int32(sdivisible32(c).m)])
  1724  						x)
  1725  					(Const32 <typ.UInt32> [int32(sdivisible32(c).a)])
  1726  				)
  1727  				(Const32 <typ.UInt32> [int32(32-sdivisible32(c).k)])
  1728  			)
  1729  			(Const32 <typ.UInt32> [int32(sdivisible32(c).max)])
  1730  		)
  1731  
  1732  (Eq32 x (Mul32 (Const32 [c])
  1733    (Sub32
  1734      (Rsh32x64
  1735        mul:(Hmul32
  1736          (Const32 [m])
  1737          x)
  1738        (Const64 [s]))
  1739      (Rsh32x64
  1740        x
  1741        (Const64 [31])))
  1742  	)
  1743  )
  1744    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1745    && m == int32(smagic32(c).m/2) && s == smagic32(c).s-1
  1746  	&& x.Op != OpConst32 && sdivisibleOK32(c)
  1747   => (Leq32U
  1748  			(RotateLeft32 <typ.UInt32>
  1749  				(Add32 <typ.UInt32>
  1750  					(Mul32 <typ.UInt32>
  1751  						(Const32 <typ.UInt32> [int32(sdivisible32(c).m)])
  1752  						x)
  1753  					(Const32 <typ.UInt32> [int32(sdivisible32(c).a)])
  1754  				)
  1755  				(Const32 <typ.UInt32> [int32(32-sdivisible32(c).k)])
  1756  			)
  1757  			(Const32 <typ.UInt32> [int32(sdivisible32(c).max)])
  1758  		)
  1759  
  1760  (Eq32 x (Mul32 (Const32 [c])
  1761    (Sub32
  1762      (Rsh32x64
  1763        (Add32
  1764          mul:(Hmul32
  1765            (Const32 [m])
  1766            x)
  1767          x)
  1768        (Const64 [s]))
  1769      (Rsh32x64
  1770        x
  1771        (Const64 [31])))
  1772  	)
  1773  )
  1774    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1775    && m == int32(smagic32(c).m) && s == smagic32(c).s
  1776  	&& x.Op != OpConst32 && sdivisibleOK32(c)
  1777   => (Leq32U
  1778  			(RotateLeft32 <typ.UInt32>
  1779  				(Add32 <typ.UInt32>
  1780  					(Mul32 <typ.UInt32>
  1781  						(Const32 <typ.UInt32> [int32(sdivisible32(c).m)])
  1782  						x)
  1783  					(Const32 <typ.UInt32> [int32(sdivisible32(c).a)])
  1784  				)
  1785  				(Const32 <typ.UInt32> [int32(32-sdivisible32(c).k)])
  1786  			)
  1787  			(Const32 <typ.UInt32> [int32(sdivisible32(c).max)])
  1788  		)
  1789  
  1790  (Eq64 x (Mul64 (Const64 [c])
  1791    (Sub64
  1792      (Rsh64x64
  1793        mul:(Hmul64
  1794          (Const64 [m])
  1795          x)
  1796        (Const64 [s]))
  1797      (Rsh64x64
  1798        x
  1799        (Const64 [63])))
  1800  	)
  1801  )
  1802    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1803    && m == int64(smagic64(c).m/2) && s == smagic64(c).s-1
  1804  	&& x.Op != OpConst64 && sdivisibleOK64(c)
  1805   => (Leq64U
  1806  			(RotateLeft64 <typ.UInt64>
  1807  				(Add64 <typ.UInt64>
  1808  					(Mul64 <typ.UInt64>
  1809  						(Const64 <typ.UInt64> [int64(sdivisible64(c).m)])
  1810  						x)
  1811  					(Const64 <typ.UInt64> [int64(sdivisible64(c).a)])
  1812  				)
  1813  				(Const64 <typ.UInt64> [64-sdivisible64(c).k])
  1814  			)
  1815  			(Const64 <typ.UInt64> [int64(sdivisible64(c).max)])
  1816  		)
  1817  
  1818  (Eq64 x (Mul64 (Const64 [c])
  1819    (Sub64
  1820      (Rsh64x64
  1821        (Add64
  1822          mul:(Hmul64
  1823            (Const64 [m])
  1824            x)
  1825          x)
  1826        (Const64 [s]))
  1827      (Rsh64x64
  1828        x
  1829        (Const64 [63])))
  1830  	)
  1831  )
  1832    && v.Block.Func.pass.name != "opt" && mul.Uses == 1
  1833    && m == int64(smagic64(c).m) && s == smagic64(c).s
  1834  	&& x.Op != OpConst64 && sdivisibleOK64(c)
  1835   => (Leq64U
  1836  			(RotateLeft64 <typ.UInt64>
  1837  				(Add64 <typ.UInt64>
  1838  					(Mul64 <typ.UInt64>
  1839  						(Const64 <typ.UInt64> [int64(sdivisible64(c).m)])
  1840  						x)
  1841  					(Const64 <typ.UInt64> [int64(sdivisible64(c).a)])
  1842  				)
  1843  				(Const64 <typ.UInt64> [64-sdivisible64(c).k])
  1844  			)
  1845  			(Const64 <typ.UInt64> [int64(sdivisible64(c).max)])
  1846  		)
  1847  
  1848  // Divisibility check for signed integers for power of two constant are simple mask.
  1849  // However, we must match against the rewritten n%c == 0 -> n - c*(n/c) == 0 -> n == c*(n/c)
  1850  // where n/c contains fixup code to handle signed n.
  1851  ((Eq8|Neq8) n (Lsh8x64
  1852    (Rsh8x64
  1853      (Add8  <t> n (Rsh8Ux64  <t> (Rsh8x64  <t> n (Const64 <typ.UInt64> [ 7])) (Const64 <typ.UInt64> [kbar])))
  1854      (Const64 <typ.UInt64> [k]))
  1855  	(Const64 <typ.UInt64> [k]))
  1856  ) && k > 0 && k < 7 && kbar == 8 - k
  1857    => ((Eq8|Neq8) (And8 <t> n (Const8 <t> [1<<uint(k)-1])) (Const8 <t> [0]))
  1858  
  1859  ((Eq16|Neq16) n (Lsh16x64
  1860    (Rsh16x64
  1861      (Add16 <t> n (Rsh16Ux64 <t> (Rsh16x64 <t> n (Const64 <typ.UInt64> [15])) (Const64 <typ.UInt64> [kbar])))
  1862      (Const64 <typ.UInt64> [k]))
  1863  	(Const64 <typ.UInt64> [k]))
  1864  ) && k > 0 && k < 15 && kbar == 16 - k
  1865    => ((Eq16|Neq16) (And16 <t> n (Const16 <t> [1<<uint(k)-1])) (Const16 <t> [0]))
  1866  
  1867  ((Eq32|Neq32) n (Lsh32x64
  1868    (Rsh32x64
  1869      (Add32 <t> n (Rsh32Ux64 <t> (Rsh32x64 <t> n (Const64 <typ.UInt64> [31])) (Const64 <typ.UInt64> [kbar])))
  1870      (Const64 <typ.UInt64> [k]))
  1871  	(Const64 <typ.UInt64> [k]))
  1872  ) && k > 0 && k < 31 && kbar == 32 - k
  1873    => ((Eq32|Neq32) (And32 <t> n (Const32 <t> [1<<uint(k)-1])) (Const32 <t> [0]))
  1874  
  1875  ((Eq64|Neq64) n (Lsh64x64
  1876    (Rsh64x64
  1877      (Add64 <t> n (Rsh64Ux64 <t> (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) (Const64 <typ.UInt64> [kbar])))
  1878      (Const64 <typ.UInt64> [k]))
  1879  	(Const64 <typ.UInt64> [k]))
  1880  ) && k > 0 && k < 63 && kbar == 64 - k
  1881    => ((Eq64|Neq64) (And64 <t> n (Const64 <t> [1<<uint(k)-1])) (Const64 <t> [0]))
  1882  
  1883  (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)
  1884  (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)
  1885  
  1886  // Optimize bitsets
  1887  (Eq8 (And8 <t> x (Const8 <t> [y])) (Const8 <t> [y])) && oneBit8(y)
  1888    => (Neq8 (And8 <t> x (Const8 <t> [y])) (Const8 <t> [0]))
  1889  (Eq16 (And16 <t> x (Const16 <t> [y])) (Const16 <t> [y])) && oneBit16(y)
  1890    => (Neq16 (And16 <t> x (Const16 <t> [y])) (Const16 <t> [0]))
  1891  (Eq32 (And32 <t> x (Const32 <t> [y])) (Const32 <t> [y])) && oneBit32(y)
  1892    => (Neq32 (And32 <t> x (Const32 <t> [y])) (Const32 <t> [0]))
  1893  (Eq64 (And64 <t> x (Const64 <t> [y])) (Const64 <t> [y])) && oneBit64(y)
  1894    => (Neq64 (And64 <t> x (Const64 <t> [y])) (Const64 <t> [0]))
  1895  (Neq8 (And8 <t> x (Const8 <t> [y])) (Const8 <t> [y])) && oneBit8(y)
  1896    => (Eq8 (And8 <t> x (Const8 <t> [y])) (Const8 <t> [0]))
  1897  (Neq16 (And16 <t> x (Const16 <t> [y])) (Const16 <t> [y])) && oneBit16(y)
  1898    => (Eq16 (And16 <t> x (Const16 <t> [y])) (Const16 <t> [0]))
  1899  (Neq32 (And32 <t> x (Const32 <t> [y])) (Const32 <t> [y])) && oneBit32(y)
  1900    => (Eq32 (And32 <t> x (Const32 <t> [y])) (Const32 <t> [0]))
  1901  (Neq64 (And64 <t> x (Const64 <t> [y])) (Const64 <t> [y])) && oneBit64(y)
  1902    => (Eq64 (And64 <t> x (Const64 <t> [y])) (Const64 <t> [0]))
  1903  
  1904  // Reassociate expressions involving
  1905  // constants such that constants come first,
  1906  // exposing obvious constant-folding opportunities.
  1907  // Reassociate (op (op y C) x) to (op C (op x y)) or similar, where C
  1908  // is constant, which pushes constants to the outside
  1909  // of the expression. At that point, any constant-folding
  1910  // opportunities should be obvious.
  1911  // Note: don't include AddPtr here! In order to maintain the
  1912  // invariant that pointers must stay within the pointed-to object,
  1913  // we can't pull part of a pointer computation above the AddPtr.
  1914  // See issue 37881.
  1915  // Note: we don't need to handle any (x-C) cases because we already rewrite
  1916  // (x-C) to (x+(-C)).
  1917  
  1918  // x + (C + z) -> C + (x + z)
  1919  (Add64 (Add64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (Add64 i (Add64 <t> z x))
  1920  (Add32 (Add32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (Add32 i (Add32 <t> z x))
  1921  (Add16 (Add16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (Add16 i (Add16 <t> z x))
  1922  (Add8  (Add8  i:(Const8  <t>) z) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Add8  i (Add8  <t> z x))
  1923  
  1924  // x + (C - z) -> C + (x - z)
  1925  (Add64 (Sub64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (Add64 i (Sub64 <t> x z))
  1926  (Add32 (Sub32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (Add32 i (Sub32 <t> x z))
  1927  (Add16 (Sub16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (Add16 i (Sub16 <t> x z))
  1928  (Add8  (Sub8  i:(Const8  <t>) z) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Add8  i (Sub8  <t> x z))
  1929  
  1930  // x - (C - z) -> x + (z - C) -> (x + z) - C
  1931  (Sub64 x (Sub64 i:(Const64 <t>) z)) && (z.Op != OpConst64 && x.Op != OpConst64) => (Sub64 (Add64 <t> x z) i)
  1932  (Sub32 x (Sub32 i:(Const32 <t>) z)) && (z.Op != OpConst32 && x.Op != OpConst32) => (Sub32 (Add32 <t> x z) i)
  1933  (Sub16 x (Sub16 i:(Const16 <t>) z)) && (z.Op != OpConst16 && x.Op != OpConst16) => (Sub16 (Add16 <t> x z) i)
  1934  (Sub8  x (Sub8  i:(Const8  <t>) z)) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Sub8  (Add8  <t> x z) i)
  1935  
  1936  // x - (z + C) -> x + (-z - C) -> (x - z) - C
  1937  (Sub64 x (Add64 z i:(Const64 <t>))) && (z.Op != OpConst64 && x.Op != OpConst64) => (Sub64 (Sub64 <t> x z) i)
  1938  (Sub32 x (Add32 z i:(Const32 <t>))) && (z.Op != OpConst32 && x.Op != OpConst32) => (Sub32 (Sub32 <t> x z) i)
  1939  (Sub16 x (Add16 z i:(Const16 <t>))) && (z.Op != OpConst16 && x.Op != OpConst16) => (Sub16 (Sub16 <t> x z) i)
  1940  (Sub8  x (Add8  z i:(Const8  <t>))) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Sub8 (Sub8  <t> x z) i)
  1941  
  1942  // (C - z) - x -> C - (z + x)
  1943  (Sub64 (Sub64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (Sub64 i (Add64 <t> z x))
  1944  (Sub32 (Sub32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (Sub32 i (Add32 <t> z x))
  1945  (Sub16 (Sub16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (Sub16 i (Add16 <t> z x))
  1946  (Sub8  (Sub8  i:(Const8  <t>) z) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Sub8  i (Add8  <t> z x))
  1947  
  1948  // (z + C) -x -> C + (z - x)
  1949  (Sub64 (Add64 z i:(Const64 <t>)) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (Add64 i (Sub64 <t> z x))
  1950  (Sub32 (Add32 z i:(Const32 <t>)) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (Add32 i (Sub32 <t> z x))
  1951  (Sub16 (Add16 z i:(Const16 <t>)) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (Add16 i (Sub16 <t> z x))
  1952  (Sub8  (Add8  z i:(Const8  <t>)) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Add8  i (Sub8  <t> z x))
  1953  
  1954  // x & (C & z) -> C & (x & z)
  1955  (And64 (And64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (And64 i (And64 <t> z x))
  1956  (And32 (And32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (And32 i (And32 <t> z x))
  1957  (And16 (And16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (And16 i (And16 <t> z x))
  1958  (And8  (And8  i:(Const8  <t>) z) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (And8  i (And8  <t> z x))
  1959  
  1960  // x | (C | z) -> C | (x | z)
  1961  (Or64 (Or64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (Or64 i (Or64 <t> z x))
  1962  (Or32 (Or32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (Or32 i (Or32 <t> z x))
  1963  (Or16 (Or16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (Or16 i (Or16 <t> z x))
  1964  (Or8  (Or8  i:(Const8  <t>) z) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Or8  i (Or8  <t> z x))
  1965  
  1966  // x ^ (C ^ z) -> C ^ (x ^ z)
  1967  (Xor64 (Xor64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (Xor64 i (Xor64 <t> z x))
  1968  (Xor32 (Xor32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (Xor32 i (Xor32 <t> z x))
  1969  (Xor16 (Xor16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (Xor16 i (Xor16 <t> z x))
  1970  (Xor8  (Xor8  i:(Const8  <t>) z) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Xor8  i (Xor8  <t> z x))
  1971  
  1972  // x * (D * z) = D * (x * z)
  1973  (Mul64 (Mul64 i:(Const64 <t>) z) x) && (z.Op != OpConst64 && x.Op != OpConst64) => (Mul64 i (Mul64 <t> x z))
  1974  (Mul32 (Mul32 i:(Const32 <t>) z) x) && (z.Op != OpConst32 && x.Op != OpConst32) => (Mul32 i (Mul32 <t> x z))
  1975  (Mul16 (Mul16 i:(Const16 <t>) z) x) && (z.Op != OpConst16 && x.Op != OpConst16) => (Mul16 i (Mul16 <t> x z))
  1976  (Mul8  (Mul8  i:(Const8  <t>) z) x) && (z.Op != OpConst8  && x.Op != OpConst8)  => (Mul8  i (Mul8  <t> x z))
  1977  
  1978  // C + (D + x) -> (C + D) + x
  1979  (Add64 (Const64 <t> [c]) (Add64 (Const64 <t> [d]) x)) => (Add64 (Const64 <t> [c+d]) x)
  1980  (Add32 (Const32 <t> [c]) (Add32 (Const32 <t> [d]) x)) => (Add32 (Const32 <t> [c+d]) x)
  1981  (Add16 (Const16 <t> [c]) (Add16 (Const16 <t> [d]) x)) => (Add16 (Const16 <t> [c+d]) x)
  1982  (Add8  (Const8  <t> [c]) (Add8  (Const8  <t> [d]) x)) => (Add8  (Const8  <t> [c+d]) x)
  1983  
  1984  // C + (D - x) -> (C + D) - x
  1985  (Add64 (Const64 <t> [c]) (Sub64 (Const64 <t> [d]) x)) => (Sub64 (Const64 <t> [c+d]) x)
  1986  (Add32 (Const32 <t> [c]) (Sub32 (Const32 <t> [d]) x)) => (Sub32 (Const32 <t> [c+d]) x)
  1987  (Add16 (Const16 <t> [c]) (Sub16 (Const16 <t> [d]) x)) => (Sub16 (Const16 <t> [c+d]) x)
  1988  (Add8  (Const8  <t> [c]) (Sub8  (Const8  <t> [d]) x)) => (Sub8  (Const8  <t> [c+d]) x)
  1989  
  1990  // C - (D - x) -> (C - D) + x
  1991  (Sub64 (Const64 <t> [c]) (Sub64 (Const64 <t> [d]) x)) => (Add64 (Const64 <t> [c-d]) x)
  1992  (Sub32 (Const32 <t> [c]) (Sub32 (Const32 <t> [d]) x)) => (Add32 (Const32 <t> [c-d]) x)
  1993  (Sub16 (Const16 <t> [c]) (Sub16 (Const16 <t> [d]) x)) => (Add16 (Const16 <t> [c-d]) x)
  1994  (Sub8  (Const8  <t> [c]) (Sub8  (Const8  <t> [d]) x)) => (Add8  (Const8  <t> [c-d]) x)
  1995  
  1996  // C - (D + x) -> (C - D) - x
  1997  (Sub64 (Const64 <t> [c]) (Add64 (Const64 <t> [d]) x)) => (Sub64 (Const64 <t> [c-d]) x)
  1998  (Sub32 (Const32 <t> [c]) (Add32 (Const32 <t> [d]) x)) => (Sub32 (Const32 <t> [c-d]) x)
  1999  (Sub16 (Const16 <t> [c]) (Add16 (Const16 <t> [d]) x)) => (Sub16 (Const16 <t> [c-d]) x)
  2000  (Sub8  (Const8  <t> [c]) (Add8  (Const8  <t> [d]) x)) => (Sub8  (Const8  <t> [c-d]) x)
  2001  
  2002  // C & (D & x) -> (C & D) & x
  2003  (And64 (Const64 <t> [c]) (And64 (Const64 <t> [d]) x)) => (And64 (Const64 <t> [c&d]) x)
  2004  (And32 (Const32 <t> [c]) (And32 (Const32 <t> [d]) x)) => (And32 (Const32 <t> [c&d]) x)
  2005  (And16 (Const16 <t> [c]) (And16 (Const16 <t> [d]) x)) => (And16 (Const16 <t> [c&d]) x)
  2006  (And8  (Const8  <t> [c]) (And8  (Const8  <t> [d]) x)) => (And8  (Const8  <t> [c&d]) x)
  2007  
  2008  // C | (D | x) -> (C | D) | x
  2009  (Or64 (Const64 <t> [c]) (Or64 (Const64 <t> [d]) x)) => (Or64 (Const64 <t> [c|d]) x)
  2010  (Or32 (Const32 <t> [c]) (Or32 (Const32 <t> [d]) x)) => (Or32 (Const32 <t> [c|d]) x)
  2011  (Or16 (Const16 <t> [c]) (Or16 (Const16 <t> [d]) x)) => (Or16 (Const16 <t> [c|d]) x)
  2012  (Or8  (Const8  <t> [c]) (Or8  (Const8  <t> [d]) x)) => (Or8  (Const8  <t> [c|d]) x)
  2013  
  2014  // C ^ (D ^ x) -> (C ^ D) ^ x
  2015  (Xor64 (Const64 <t> [c]) (Xor64 (Const64 <t> [d]) x)) => (Xor64 (Const64 <t> [c^d]) x)
  2016  (Xor32 (Const32 <t> [c]) (Xor32 (Const32 <t> [d]) x)) => (Xor32 (Const32 <t> [c^d]) x)
  2017  (Xor16 (Const16 <t> [c]) (Xor16 (Const16 <t> [d]) x)) => (Xor16 (Const16 <t> [c^d]) x)
  2018  (Xor8  (Const8  <t> [c]) (Xor8  (Const8  <t> [d]) x)) => (Xor8  (Const8  <t> [c^d]) x)
  2019  
  2020  // C * (D * x) = (C * D) * x
  2021  (Mul64 (Const64 <t> [c]) (Mul64 (Const64 <t> [d]) x)) => (Mul64 (Const64 <t> [c*d]) x)
  2022  (Mul32 (Const32 <t> [c]) (Mul32 (Const32 <t> [d]) x)) => (Mul32 (Const32 <t> [c*d]) x)
  2023  (Mul16 (Const16 <t> [c]) (Mul16 (Const16 <t> [d]) x)) => (Mul16 (Const16 <t> [c*d]) x)
  2024  (Mul8  (Const8  <t> [c]) (Mul8  (Const8  <t> [d]) x)) => (Mul8  (Const8  <t> [c*d]) x)
  2025  
  2026  // floating point optimizations
  2027  (Mul(32|64)F x (Const(32|64)F [1])) => x
  2028  (Mul32F x (Const32F [-1])) => (Neg32F x)
  2029  (Mul64F x (Const64F [-1])) => (Neg64F x)
  2030  (Mul32F x (Const32F [2])) => (Add32F x x)
  2031  (Mul64F x (Const64F [2])) => (Add64F x x)
  2032  
  2033  (Div32F x (Const32F <t> [c])) && reciprocalExact32(c) => (Mul32F x (Const32F <t> [1/c]))
  2034  (Div64F x (Const64F <t> [c])) && reciprocalExact64(c) => (Mul64F x (Const64F <t> [1/c]))
  2035  
  2036  // rewrite single-precision sqrt expression "float32(math.Sqrt(float64(x)))"
  2037  (Cvt64Fto32F sqrt0:(Sqrt (Cvt32Fto64F x))) && sqrt0.Uses==1 => (Sqrt32 x)
  2038  
  2039  (Sqrt (Const64F [c])) && !math.IsNaN(math.Sqrt(c)) => (Const64F [math.Sqrt(c)])
  2040  
  2041  // for rewriting results of some late-expanded rewrites (below)
  2042  (SelectN [0] (MakeResult x ___)) => x
  2043  (SelectN [1] (MakeResult x y ___)) => y
  2044  (SelectN [2] (MakeResult x y z ___)) => z
  2045  
  2046  // for late-expanded calls, recognize newobject and remove zeroing and nilchecks
  2047  (Zero (SelectN [0] call:(StaticLECall _ _)) mem:(SelectN [1] call))
  2048  	&& isSameCall(call.Aux, "runtime.newobject")
  2049  	=> mem
  2050  
  2051  (Store (SelectN [0] call:(StaticLECall _ _)) x mem:(SelectN [1] call))
  2052  	&& isConstZero(x)
  2053  	&& isSameCall(call.Aux, "runtime.newobject")
  2054  	=> mem
  2055  
  2056  (Store (OffPtr (SelectN [0] call:(StaticLECall _ _))) x mem:(SelectN [1] call))
  2057  	&& isConstZero(x)
  2058  	&& isSameCall(call.Aux, "runtime.newobject")
  2059  	=> mem
  2060  
  2061  (NilCheck ptr:(SelectN [0] call:(StaticLECall _ _)) _)
  2062  	&& isSameCall(call.Aux, "runtime.newobject")
  2063  	&& warnRule(fe.Debug_checknil(), v, "removed nil check")
  2064  	=> ptr
  2065  
  2066  (NilCheck ptr:(OffPtr (SelectN [0] call:(StaticLECall _ _))) _)
  2067  	&& isSameCall(call.Aux, "runtime.newobject")
  2068  	&& warnRule(fe.Debug_checknil(), v, "removed nil check")
  2069  	=> ptr
  2070  
  2071  // Addresses of globals are always non-nil.
  2072  (NilCheck          ptr:(Addr {_} (SB))    _) => ptr
  2073  (NilCheck ptr:(Convert (Addr {_} (SB)) _) _) => ptr
  2074  
  2075  // Addresses of locals are always non-nil.
  2076  (NilCheck ptr:(LocalAddr _ _) _)
  2077  	&& warnRule(fe.Debug_checknil(), v, "removed nil check")
  2078  	=> ptr
  2079  
  2080  // Nil checks of nil checks are redundant.
  2081  // See comment at the end of https://go-review.googlesource.com/c/go/+/537775.
  2082  (NilCheck ptr:(NilCheck _ _) _ ) => ptr
  2083  
  2084  // for late-expanded calls, recognize memequal applied to a single constant byte
  2085  // Support is limited by 1, 2, 4, 8 byte sizes
  2086  (StaticLECall {callAux} sptr (Addr {scon} (SB)) (Const64 [1]) mem)
  2087    && isSameCall(callAux, "runtime.memequal")
  2088    && symIsRO(scon)
  2089    => (MakeResult (Eq8 (Load <typ.Int8> sptr mem) (Const8 <typ.Int8> [int8(read8(scon,0))])) mem)
  2090  
  2091  (StaticLECall {callAux} (Addr {scon} (SB)) sptr (Const64 [1]) mem)
  2092    && isSameCall(callAux, "runtime.memequal")
  2093    && symIsRO(scon)
  2094    => (MakeResult (Eq8 (Load <typ.Int8> sptr mem) (Const8 <typ.Int8> [int8(read8(scon,0))])) mem)
  2095  
  2096  (StaticLECall {callAux} sptr (Addr {scon} (SB)) (Const64 [2]) mem)
  2097    && isSameCall(callAux, "runtime.memequal")
  2098    && symIsRO(scon)
  2099    && canLoadUnaligned(config)
  2100    => (MakeResult (Eq16 (Load <typ.Int16> sptr mem) (Const16 <typ.Int16> [int16(read16(scon,0,config.ctxt.Arch.ByteOrder))])) mem)
  2101  
  2102  (StaticLECall {callAux} (Addr {scon} (SB)) sptr (Const64 [2]) mem)
  2103    && isSameCall(callAux, "runtime.memequal")
  2104    && symIsRO(scon)
  2105    && canLoadUnaligned(config)
  2106    => (MakeResult (Eq16 (Load <typ.Int16> sptr mem) (Const16 <typ.Int16> [int16(read16(scon,0,config.ctxt.Arch.ByteOrder))])) mem)
  2107  
  2108  (StaticLECall {callAux} sptr (Addr {scon} (SB)) (Const64 [4]) mem)
  2109    && isSameCall(callAux, "runtime.memequal")
  2110    && symIsRO(scon)
  2111    && canLoadUnaligned(config)
  2112    => (MakeResult (Eq32 (Load <typ.Int32> sptr mem) (Const32 <typ.Int32> [int32(read32(scon,0,config.ctxt.Arch.ByteOrder))])) mem)
  2113  
  2114  (StaticLECall {callAux} (Addr {scon} (SB)) sptr (Const64 [4]) mem)
  2115    && isSameCall(callAux, "runtime.memequal")
  2116    && symIsRO(scon)
  2117    && canLoadUnaligned(config)
  2118    => (MakeResult (Eq32 (Load <typ.Int32> sptr mem) (Const32 <typ.Int32> [int32(read32(scon,0,config.ctxt.Arch.ByteOrder))])) mem)
  2119  
  2120  (StaticLECall {callAux} sptr (Addr {scon} (SB)) (Const64 [8]) mem)
  2121    && isSameCall(callAux, "runtime.memequal")
  2122    && symIsRO(scon)
  2123    && canLoadUnaligned(config) && config.PtrSize == 8
  2124    => (MakeResult (Eq64 (Load <typ.Int64> sptr mem) (Const64 <typ.Int64> [int64(read64(scon,0,config.ctxt.Arch.ByteOrder))])) mem)
  2125  
  2126  (StaticLECall {callAux} (Addr {scon} (SB)) sptr (Const64 [8]) mem)
  2127    && isSameCall(callAux, "runtime.memequal")
  2128    && symIsRO(scon)
  2129    && canLoadUnaligned(config) && config.PtrSize == 8
  2130    => (MakeResult (Eq64 (Load <typ.Int64> sptr mem) (Const64 <typ.Int64> [int64(read64(scon,0,config.ctxt.Arch.ByteOrder))])) mem)
  2131  
  2132  (StaticLECall {callAux} _ _ (Const64 [0]) mem)
  2133    && isSameCall(callAux, "runtime.memequal")
  2134    => (MakeResult (ConstBool <typ.Bool> [true]) mem)
  2135  
  2136  (Static(Call|LECall) {callAux} p q _ mem)
  2137    && isSameCall(callAux, "runtime.memequal")
  2138    && isSamePtr(p, q)
  2139    => (MakeResult (ConstBool <typ.Bool> [true]) mem)
  2140  
  2141  // Turn known-size calls to memclrNoHeapPointers into a Zero.
  2142  // Note that we are using types.Types[types.TUINT8] instead of sptr.Type.Elem() - see issue 55122 and CL 431496 for more details.
  2143  (SelectN [0] call:(StaticCall {sym} sptr (Const(64|32) [c]) mem))
  2144    && isInlinableMemclr(config, int64(c))
  2145    && isSameCall(sym, "runtime.memclrNoHeapPointers")
  2146    && call.Uses == 1
  2147    && clobber(call)
  2148    => (Zero {types.Types[types.TUINT8]} [int64(c)] sptr mem)
  2149  
  2150  // Recognise make([]T, 0) and replace it with a pointer to the zerobase
  2151  (StaticLECall {callAux} _ (Const(64|32) [0]) (Const(64|32) [0]) mem)
  2152  	&& isSameCall(callAux, "runtime.makeslice")
  2153  	=> (MakeResult (Addr <v.Type.FieldType(0)> {ir.Syms.Zerobase} (SB)) mem)
  2154  
  2155  // Evaluate constant address comparisons.
  2156  (EqPtr  x x) => (ConstBool [true])
  2157  (NeqPtr x x) => (ConstBool [false])
  2158  (EqPtr  (Addr {x} _) (Addr {y} _)) => (ConstBool [x == y])
  2159  (EqPtr  (Addr {x} _) (OffPtr [o] (Addr {y} _))) => (ConstBool [x == y && o == 0])
  2160  (EqPtr  (OffPtr [o1] (Addr {x} _)) (OffPtr [o2] (Addr {y} _))) => (ConstBool [x == y && o1 == o2])
  2161  (NeqPtr (Addr {x} _) (Addr {y} _)) => (ConstBool [x != y])
  2162  (NeqPtr (Addr {x} _) (OffPtr [o] (Addr {y} _))) => (ConstBool [x != y || o != 0])
  2163  (NeqPtr (OffPtr [o1] (Addr {x} _)) (OffPtr [o2] (Addr {y} _))) => (ConstBool [x != y || o1 != o2])
  2164  (EqPtr  (LocalAddr {x} _ _) (LocalAddr {y} _ _)) => (ConstBool [x == y])
  2165  (EqPtr  (LocalAddr {x} _ _) (OffPtr [o] (LocalAddr {y} _ _))) => (ConstBool [x == y && o == 0])
  2166  (EqPtr  (OffPtr [o1] (LocalAddr {x} _ _)) (OffPtr [o2] (LocalAddr {y} _ _))) => (ConstBool [x == y && o1 == o2])
  2167  (NeqPtr (LocalAddr {x} _ _) (LocalAddr {y} _ _)) => (ConstBool [x != y])
  2168  (NeqPtr (LocalAddr {x} _ _) (OffPtr [o] (LocalAddr {y} _ _))) => (ConstBool [x != y || o != 0])
  2169  (NeqPtr (OffPtr [o1] (LocalAddr {x} _ _)) (OffPtr [o2] (LocalAddr {y} _ _))) => (ConstBool [x != y || o1 != o2])
  2170  (EqPtr  (OffPtr [o1] p1) p2) && isSamePtr(p1, p2) => (ConstBool [o1 == 0])
  2171  (NeqPtr (OffPtr [o1] p1) p2) && isSamePtr(p1, p2) => (ConstBool [o1 != 0])
  2172  (EqPtr  (OffPtr [o1] p1) (OffPtr [o2] p2)) && isSamePtr(p1, p2) => (ConstBool [o1 == o2])
  2173  (NeqPtr (OffPtr [o1] p1) (OffPtr [o2] p2)) && isSamePtr(p1, p2) => (ConstBool [o1 != o2])
  2174  (EqPtr  (Const(32|64) [c]) (Const(32|64) [d])) => (ConstBool [c == d])
  2175  (NeqPtr (Const(32|64) [c]) (Const(32|64) [d])) => (ConstBool [c != d])
  2176  (EqPtr  (Convert (Addr {x} _) _) (Addr {y} _)) => (ConstBool [x==y])
  2177  (NeqPtr (Convert (Addr {x} _) _) (Addr {y} _)) => (ConstBool [x!=y])
  2178  
  2179  (EqPtr  (LocalAddr _ _) (Addr _)) => (ConstBool [false])
  2180  (EqPtr  (OffPtr (LocalAddr _ _)) (Addr _)) => (ConstBool [false])
  2181  (EqPtr  (LocalAddr _ _) (OffPtr (Addr _))) => (ConstBool [false])
  2182  (EqPtr  (OffPtr (LocalAddr _ _)) (OffPtr (Addr _))) => (ConstBool [false])
  2183  (NeqPtr (LocalAddr _ _) (Addr _)) => (ConstBool [true])
  2184  (NeqPtr (OffPtr (LocalAddr _ _)) (Addr _)) => (ConstBool [true])
  2185  (NeqPtr (LocalAddr _ _) (OffPtr (Addr _))) => (ConstBool [true])
  2186  (NeqPtr (OffPtr (LocalAddr _ _)) (OffPtr (Addr _))) => (ConstBool [true])
  2187  
  2188  // Simplify address comparisons.
  2189  (EqPtr  (AddPtr p1 o1) p2) && isSamePtr(p1, p2) => (Not (IsNonNil o1))
  2190  (NeqPtr (AddPtr p1 o1) p2) && isSamePtr(p1, p2) => (IsNonNil o1)
  2191  (EqPtr  (Const(32|64) [0]) p) => (Not (IsNonNil p))
  2192  (NeqPtr (Const(32|64) [0]) p) => (IsNonNil p)
  2193  (EqPtr  (ConstNil) p) => (Not (IsNonNil p))
  2194  (NeqPtr (ConstNil) p) => (IsNonNil p)
  2195  
  2196  // Evaluate constant user nil checks.
  2197  (IsNonNil (ConstNil)) => (ConstBool [false])
  2198  (IsNonNil (Const(32|64) [c])) => (ConstBool [c != 0])
  2199  (IsNonNil          (Addr _)   ) => (ConstBool [true])
  2200  (IsNonNil (Convert (Addr _) _)) => (ConstBool [true])
  2201  (IsNonNil (LocalAddr _ _)) => (ConstBool [true])
  2202  
  2203  // Inline small or disjoint runtime.memmove calls with constant length.
  2204  // See the comment in op Move in genericOps.go for discussion of the type.
  2205  //
  2206  // Note that we've lost any knowledge of the type and alignment requirements
  2207  // of the source and destination. We only know the size, and that the type
  2208  // contains no pointers.
  2209  // The type of the move is not necessarily v.Args[0].Type().Elem()!
  2210  // See issue 55122 for details.
  2211  //
  2212  // Because expand calls runs after prove, constants useful to this pattern may not appear.
  2213  // Both versions need to exist; the memory and register variants.
  2214  //
  2215  // Match post-expansion calls, memory version.
  2216  (SelectN [0] call:(StaticCall {sym} s1:(Store _ (Const(64|32) [sz]) s2:(Store  _ src s3:(Store {t} _ dst mem)))))
  2217  	&& sz >= 0
  2218  	&& isSameCall(sym, "runtime.memmove")
  2219  	&& s1.Uses == 1 && s2.Uses == 1 && s3.Uses == 1
  2220  	&& isInlinableMemmove(dst, src, int64(sz), config)
  2221  	&& clobber(s1, s2, s3, call)
  2222  	=> (Move {types.Types[types.TUINT8]} [int64(sz)] dst src mem)
  2223  
  2224  // Match post-expansion calls, register version.
  2225  (SelectN [0] call:(StaticCall {sym} dst src (Const(64|32) [sz]) mem))
  2226  	&& sz >= 0
  2227  	&& call.Uses == 1 // this will exclude all calls with results
  2228  	&& isSameCall(sym, "runtime.memmove")
  2229  	&& isInlinableMemmove(dst, src, int64(sz), config)
  2230  	&& clobber(call)
  2231  	=> (Move {types.Types[types.TUINT8]} [int64(sz)] dst src mem)
  2232  
  2233  // Match pre-expansion calls.
  2234  (SelectN [0] call:(StaticLECall {sym} dst src (Const(64|32) [sz]) mem))
  2235  	&& sz >= 0
  2236  	&& call.Uses == 1 // this will exclude all calls with results
  2237  	&& isSameCall(sym, "runtime.memmove")
  2238  	&& isInlinableMemmove(dst, src, int64(sz), config)
  2239  	&& clobber(call)
  2240  	=> (Move {types.Types[types.TUINT8]} [int64(sz)] dst src mem)
  2241  
  2242  // De-virtualize late-expanded interface calls into late-expanded static calls.
  2243  (InterLECall [argsize] {auxCall} (Addr {fn} (SB)) ___) => devirtLECall(v, fn.(*obj.LSym))
  2244  
  2245  // Move and Zero optimizations.
  2246  // Move source and destination may overlap.
  2247  
  2248  // Convert Moves into Zeros when the source is known to be zeros.
  2249  (Move {t} [n] dst1 src mem:(Zero {t} [n] dst2 _)) && isSamePtr(src, dst2)
  2250  	=> (Zero {t} [n] dst1 mem)
  2251  (Move {t} [n] dst1 src mem:(VarDef (Zero {t} [n] dst0 _))) && isSamePtr(src, dst0)
  2252  	=> (Zero {t} [n] dst1 mem)
  2253  (Move {t} [n] dst (Addr {sym} (SB)) mem) && symIsROZero(sym) => (Zero {t} [n] dst mem)
  2254  
  2255  // Don't Store to variables that are about to be overwritten by Move/Zero.
  2256  (Zero {t1} [n] p1 store:(Store {t2} (OffPtr [o2] p2) _ mem))
  2257  	&& isSamePtr(p1, p2) && store.Uses == 1
  2258  	&& n >= o2 + t2.Size()
  2259  	&& clobber(store)
  2260  	=> (Zero {t1} [n] p1 mem)
  2261  (Move {t1} [n] dst1 src1 store:(Store {t2} op:(OffPtr [o2] dst2) _ mem))
  2262  	&& isSamePtr(dst1, dst2) && store.Uses == 1
  2263  	&& n >= o2 + t2.Size()
  2264  	&& disjoint(src1, n, op, t2.Size())
  2265  	&& clobber(store)
  2266  	=> (Move {t1} [n] dst1 src1 mem)
  2267  
  2268  // Don't Move to variables that are immediately completely overwritten.
  2269  (Zero {t} [n] dst1 move:(Move {t} [n] dst2 _ mem))
  2270  	&& move.Uses == 1
  2271  	&& isSamePtr(dst1, dst2)
  2272  	&& clobber(move)
  2273  	=> (Zero {t} [n] dst1 mem)
  2274  (Move {t} [n] dst1 src1 move:(Move {t} [n] dst2 _ mem))
  2275  	&& move.Uses == 1
  2276  	&& isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
  2277  	&& clobber(move)
  2278  	=> (Move {t} [n] dst1 src1 mem)
  2279  (Zero {t} [n] dst1 vardef:(VarDef {x} move:(Move {t} [n] dst2 _ mem)))
  2280  	&& move.Uses == 1 && vardef.Uses == 1
  2281  	&& isSamePtr(dst1, dst2)
  2282  	&& clobber(move, vardef)
  2283  	=> (Zero {t} [n] dst1 (VarDef {x} mem))
  2284  (Move {t} [n] dst1 src1 vardef:(VarDef {x} move:(Move {t} [n] dst2 _ mem)))
  2285  	&& move.Uses == 1 && vardef.Uses == 1
  2286  	&& isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
  2287  	&& clobber(move, vardef)
  2288  	=> (Move {t} [n] dst1 src1 (VarDef {x} mem))
  2289  (Store {t1} op1:(OffPtr [o1] p1) d1
  2290  	m2:(Store {t2} op2:(OffPtr [0] p2) d2
  2291  		m3:(Move [n] p3 _ mem)))
  2292  	&& m2.Uses == 1 && m3.Uses == 1
  2293  	&& o1 == t2.Size()
  2294  	&& n == t2.Size() + t1.Size()
  2295  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3)
  2296  	&& clobber(m2, m3)
  2297  	=> (Store {t1} op1 d1 (Store {t2} op2 d2 mem))
  2298  (Store {t1} op1:(OffPtr [o1] p1) d1
  2299  	m2:(Store {t2} op2:(OffPtr [o2] p2) d2
  2300  		m3:(Store {t3} op3:(OffPtr [0] p3) d3
  2301  			m4:(Move [n] p4 _ mem))))
  2302  	&& m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1
  2303  	&& o2 == t3.Size()
  2304  	&& o1-o2 == t2.Size()
  2305  	&& n == t3.Size() + t2.Size() + t1.Size()
  2306  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
  2307  	&& clobber(m2, m3, m4)
  2308  	=> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 mem)))
  2309  (Store {t1} op1:(OffPtr [o1] p1) d1
  2310  	m2:(Store {t2} op2:(OffPtr [o2] p2) d2
  2311  		m3:(Store {t3} op3:(OffPtr [o3] p3) d3
  2312  			m4:(Store {t4} op4:(OffPtr [0] p4) d4
  2313  				m5:(Move [n] p5 _ mem)))))
  2314  	&& m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1 && m5.Uses == 1
  2315  	&& o3 == t4.Size()
  2316  	&& o2-o3 == t3.Size()
  2317  	&& o1-o2 == t2.Size()
  2318  	&& n == t4.Size() + t3.Size() + t2.Size() + t1.Size()
  2319  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
  2320  	&& clobber(m2, m3, m4, m5)
  2321  	=> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 (Store {t4} op4 d4 mem))))
  2322  
  2323  // Don't Zero variables that are immediately completely overwritten
  2324  // before being accessed.
  2325  (Move {t} [n] dst1 src1 zero:(Zero {t} [n] dst2 mem))
  2326  	&& zero.Uses == 1
  2327  	&& isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
  2328  	&& clobber(zero)
  2329  	=> (Move {t} [n] dst1 src1 mem)
  2330  (Move {t} [n] dst1 src1 vardef:(VarDef {x} zero:(Zero {t} [n] dst2 mem)))
  2331  	&& zero.Uses == 1 && vardef.Uses == 1
  2332  	&& isSamePtr(dst1, dst2) && disjoint(src1, n, dst2, n)
  2333  	&& clobber(zero, vardef)
  2334  	=> (Move {t} [n] dst1 src1 (VarDef {x} mem))
  2335  (Store {t1} op1:(OffPtr [o1] p1) d1
  2336  	m2:(Store {t2} op2:(OffPtr [0] p2) d2
  2337  		m3:(Zero [n] p3 mem)))
  2338  	&& m2.Uses == 1 && m3.Uses == 1
  2339  	&& o1 == t2.Size()
  2340  	&& n == t2.Size() + t1.Size()
  2341  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3)
  2342  	&& clobber(m2, m3)
  2343  	=> (Store {t1} op1 d1 (Store {t2} op2 d2 mem))
  2344  (Store {t1} op1:(OffPtr [o1] p1) d1
  2345  	m2:(Store {t2} op2:(OffPtr [o2] p2) d2
  2346  		m3:(Store {t3} op3:(OffPtr [0] p3) d3
  2347  			m4:(Zero [n] p4 mem))))
  2348  	&& m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1
  2349  	&& o2 == t3.Size()
  2350  	&& o1-o2 == t2.Size()
  2351  	&& n == t3.Size() + t2.Size() + t1.Size()
  2352  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
  2353  	&& clobber(m2, m3, m4)
  2354  	=> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 mem)))
  2355  (Store {t1} op1:(OffPtr [o1] p1) d1
  2356  	m2:(Store {t2} op2:(OffPtr [o2] p2) d2
  2357  		m3:(Store {t3} op3:(OffPtr [o3] p3) d3
  2358  			m4:(Store {t4} op4:(OffPtr [0] p4) d4
  2359  				m5:(Zero [n] p5 mem)))))
  2360  	&& m2.Uses == 1 && m3.Uses == 1 && m4.Uses == 1 && m5.Uses == 1
  2361  	&& o3 == t4.Size()
  2362  	&& o2-o3 == t3.Size()
  2363  	&& o1-o2 == t2.Size()
  2364  	&& n == t4.Size() + t3.Size() + t2.Size() + t1.Size()
  2365  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
  2366  	&& clobber(m2, m3, m4, m5)
  2367  	=> (Store {t1} op1 d1 (Store {t2} op2 d2 (Store {t3} op3 d3 (Store {t4} op4 d4 mem))))
  2368  
  2369  // Don't Move from memory if the values are likely to already be
  2370  // in registers.
  2371  (Move {t1} [n] dst p1
  2372  	mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2373  		(Store {t3} op3:(OffPtr <tt3> [0] p3) d2 _)))
  2374  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3)
  2375  	&& t2.Alignment() <= t1.Alignment()
  2376  	&& t3.Alignment() <= t1.Alignment()
  2377  	&& registerizable(b, t2)
  2378  	&& registerizable(b, t3)
  2379  	&& o2 == t3.Size()
  2380  	&& n == t2.Size() + t3.Size()
  2381  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2382  		(Store {t3} (OffPtr <tt3> [0] dst) d2 mem))
  2383  (Move {t1} [n] dst p1
  2384  	mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2385  		(Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
  2386  			(Store {t4} op4:(OffPtr <tt4> [0] p4) d3 _))))
  2387  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
  2388  	&& t2.Alignment() <= t1.Alignment()
  2389  	&& t3.Alignment() <= t1.Alignment()
  2390  	&& t4.Alignment() <= t1.Alignment()
  2391  	&& registerizable(b, t2)
  2392  	&& registerizable(b, t3)
  2393  	&& registerizable(b, t4)
  2394  	&& o3 == t4.Size()
  2395  	&& o2-o3 == t3.Size()
  2396  	&& n == t2.Size() + t3.Size() + t4.Size()
  2397  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2398  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2399  			(Store {t4} (OffPtr <tt4> [0] dst) d3 mem)))
  2400  (Move {t1} [n] dst p1
  2401  	mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2402  		(Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
  2403  			(Store {t4} op4:(OffPtr <tt4> [o4] p4) d3
  2404  				(Store {t5} op5:(OffPtr <tt5> [0] p5) d4 _)))))
  2405  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
  2406  	&& t2.Alignment() <= t1.Alignment()
  2407  	&& t3.Alignment() <= t1.Alignment()
  2408  	&& t4.Alignment() <= t1.Alignment()
  2409  	&& t5.Alignment() <= t1.Alignment()
  2410  	&& registerizable(b, t2)
  2411  	&& registerizable(b, t3)
  2412  	&& registerizable(b, t4)
  2413  	&& registerizable(b, t5)
  2414  	&& o4 == t5.Size()
  2415  	&& o3-o4 == t4.Size()
  2416  	&& o2-o3 == t3.Size()
  2417  	&& n == t2.Size() + t3.Size() + t4.Size() + t5.Size()
  2418  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2419  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2420  			(Store {t4} (OffPtr <tt4> [o4] dst) d3
  2421  				(Store {t5} (OffPtr <tt5> [0] dst) d4 mem))))
  2422  
  2423  // Same thing but with VarDef in the middle.
  2424  (Move {t1} [n] dst p1
  2425  	mem:(VarDef
  2426  		(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2427  			(Store {t3} op3:(OffPtr <tt3> [0] p3) d2 _))))
  2428  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3)
  2429  	&& t2.Alignment() <= t1.Alignment()
  2430  	&& t3.Alignment() <= t1.Alignment()
  2431  	&& registerizable(b, t2)
  2432  	&& registerizable(b, t3)
  2433  	&& o2 == t3.Size()
  2434  	&& n == t2.Size() + t3.Size()
  2435  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2436  		(Store {t3} (OffPtr <tt3> [0] dst) d2 mem))
  2437  (Move {t1} [n] dst p1
  2438  	mem:(VarDef
  2439  		(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2440  			(Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
  2441  				(Store {t4} op4:(OffPtr <tt4> [0] p4) d3 _)))))
  2442  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
  2443  	&& t2.Alignment() <= t1.Alignment()
  2444  	&& t3.Alignment() <= t1.Alignment()
  2445  	&& t4.Alignment() <= t1.Alignment()
  2446  	&& registerizable(b, t2)
  2447  	&& registerizable(b, t3)
  2448  	&& registerizable(b, t4)
  2449  	&& o3 == t4.Size()
  2450  	&& o2-o3 == t3.Size()
  2451  	&& n == t2.Size() + t3.Size() + t4.Size()
  2452  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2453  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2454  			(Store {t4} (OffPtr <tt4> [0] dst) d3 mem)))
  2455  (Move {t1} [n] dst p1
  2456  	mem:(VarDef
  2457  		(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2458  			(Store {t3} op3:(OffPtr <tt3> [o3] p3) d2
  2459  				(Store {t4} op4:(OffPtr <tt4> [o4] p4) d3
  2460  					(Store {t5} op5:(OffPtr <tt5> [0] p5) d4 _))))))
  2461  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
  2462  	&& t2.Alignment() <= t1.Alignment()
  2463  	&& t3.Alignment() <= t1.Alignment()
  2464  	&& t4.Alignment() <= t1.Alignment()
  2465  	&& t5.Alignment() <= t1.Alignment()
  2466  	&& registerizable(b, t2)
  2467  	&& registerizable(b, t3)
  2468  	&& registerizable(b, t4)
  2469  	&& registerizable(b, t5)
  2470  	&& o4 == t5.Size()
  2471  	&& o3-o4 == t4.Size()
  2472  	&& o2-o3 == t3.Size()
  2473  	&& n == t2.Size() + t3.Size() + t4.Size() + t5.Size()
  2474  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2475  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2476  			(Store {t4} (OffPtr <tt4> [o4] dst) d3
  2477  				(Store {t5} (OffPtr <tt5> [0] dst) d4 mem))))
  2478  
  2479  // Prefer to Zero and Store than to Move.
  2480  (Move {t1} [n] dst p1
  2481  	mem:(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2482  		(Zero {t3} [n] p3 _)))
  2483  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3)
  2484  	&& t2.Alignment() <= t1.Alignment()
  2485  	&& t3.Alignment() <= t1.Alignment()
  2486  	&& registerizable(b, t2)
  2487  	&& n >= o2 + t2.Size()
  2488  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2489  		(Zero {t1} [n] dst mem))
  2490  (Move {t1} [n] dst p1
  2491  	mem:(Store {t2} (OffPtr <tt2> [o2] p2) d1
  2492  		(Store {t3} (OffPtr <tt3> [o3] p3) d2
  2493  			(Zero {t4} [n] p4 _))))
  2494  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
  2495  	&& t2.Alignment() <= t1.Alignment()
  2496  	&& t3.Alignment() <= t1.Alignment()
  2497  	&& t4.Alignment() <= t1.Alignment()
  2498  	&& registerizable(b, t2)
  2499  	&& registerizable(b, t3)
  2500  	&& n >= o2 + t2.Size()
  2501  	&& n >= o3 + t3.Size()
  2502  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2503  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2504  			(Zero {t1} [n] dst mem)))
  2505  (Move {t1} [n] dst p1
  2506  	mem:(Store {t2} (OffPtr <tt2> [o2] p2) d1
  2507  		(Store {t3} (OffPtr <tt3> [o3] p3) d2
  2508  			(Store {t4} (OffPtr <tt4> [o4] p4) d3
  2509  				(Zero {t5} [n] p5 _)))))
  2510  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
  2511  	&& t2.Alignment() <= t1.Alignment()
  2512  	&& t3.Alignment() <= t1.Alignment()
  2513  	&& t4.Alignment() <= t1.Alignment()
  2514  	&& t5.Alignment() <= t1.Alignment()
  2515  	&& registerizable(b, t2)
  2516  	&& registerizable(b, t3)
  2517  	&& registerizable(b, t4)
  2518  	&& n >= o2 + t2.Size()
  2519  	&& n >= o3 + t3.Size()
  2520  	&& n >= o4 + t4.Size()
  2521  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2522  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2523  			(Store {t4} (OffPtr <tt4> [o4] dst) d3
  2524  				(Zero {t1} [n] dst mem))))
  2525  (Move {t1} [n] dst p1
  2526  	mem:(Store {t2} (OffPtr <tt2> [o2] p2) d1
  2527  		(Store {t3} (OffPtr <tt3> [o3] p3) d2
  2528  			(Store {t4} (OffPtr <tt4> [o4] p4) d3
  2529  				(Store {t5} (OffPtr <tt5> [o5] p5) d4
  2530  					(Zero {t6} [n] p6 _))))))
  2531  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5) && isSamePtr(p5, p6)
  2532  	&& t2.Alignment() <= t1.Alignment()
  2533  	&& t3.Alignment() <= t1.Alignment()
  2534  	&& t4.Alignment() <= t1.Alignment()
  2535  	&& t5.Alignment() <= t1.Alignment()
  2536  	&& t6.Alignment() <= t1.Alignment()
  2537  	&& registerizable(b, t2)
  2538  	&& registerizable(b, t3)
  2539  	&& registerizable(b, t4)
  2540  	&& registerizable(b, t5)
  2541  	&& n >= o2 + t2.Size()
  2542  	&& n >= o3 + t3.Size()
  2543  	&& n >= o4 + t4.Size()
  2544  	&& n >= o5 + t5.Size()
  2545  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2546  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2547  			(Store {t4} (OffPtr <tt4> [o4] dst) d3
  2548  				(Store {t5} (OffPtr <tt5> [o5] dst) d4
  2549  					(Zero {t1} [n] dst mem)))))
  2550  (Move {t1} [n] dst p1
  2551  	mem:(VarDef
  2552  		(Store {t2} op2:(OffPtr <tt2> [o2] p2) d1
  2553  			(Zero {t3} [n] p3 _))))
  2554  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3)
  2555  	&& t2.Alignment() <= t1.Alignment()
  2556  	&& t3.Alignment() <= t1.Alignment()
  2557  	&& registerizable(b, t2)
  2558  	&& n >= o2 + t2.Size()
  2559  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2560  		(Zero {t1} [n] dst mem))
  2561  (Move {t1} [n] dst p1
  2562  	mem:(VarDef
  2563  		(Store {t2} (OffPtr <tt2> [o2] p2) d1
  2564  			(Store {t3} (OffPtr <tt3> [o3] p3) d2
  2565  				(Zero {t4} [n] p4 _)))))
  2566  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4)
  2567  	&& t2.Alignment() <= t1.Alignment()
  2568  	&& t3.Alignment() <= t1.Alignment()
  2569  	&& t4.Alignment() <= t1.Alignment()
  2570  	&& registerizable(b, t2)
  2571  	&& registerizable(b, t3)
  2572  	&& n >= o2 + t2.Size()
  2573  	&& n >= o3 + t3.Size()
  2574  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2575  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2576  			(Zero {t1} [n] dst mem)))
  2577  (Move {t1} [n] dst p1
  2578  	mem:(VarDef
  2579  		(Store {t2} (OffPtr <tt2> [o2] p2) d1
  2580  			(Store {t3} (OffPtr <tt3> [o3] p3) d2
  2581  				(Store {t4} (OffPtr <tt4> [o4] p4) d3
  2582  					(Zero {t5} [n] p5 _))))))
  2583  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5)
  2584  	&& t2.Alignment() <= t1.Alignment()
  2585  	&& t3.Alignment() <= t1.Alignment()
  2586  	&& t4.Alignment() <= t1.Alignment()
  2587  	&& t5.Alignment() <= t1.Alignment()
  2588  	&& registerizable(b, t2)
  2589  	&& registerizable(b, t3)
  2590  	&& registerizable(b, t4)
  2591  	&& n >= o2 + t2.Size()
  2592  	&& n >= o3 + t3.Size()
  2593  	&& n >= o4 + t4.Size()
  2594  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2595  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2596  			(Store {t4} (OffPtr <tt4> [o4] dst) d3
  2597  				(Zero {t1} [n] dst mem))))
  2598  (Move {t1} [n] dst p1
  2599  	mem:(VarDef
  2600  		(Store {t2} (OffPtr <tt2> [o2] p2) d1
  2601  			(Store {t3} (OffPtr <tt3> [o3] p3) d2
  2602  				(Store {t4} (OffPtr <tt4> [o4] p4) d3
  2603  					(Store {t5} (OffPtr <tt5> [o5] p5) d4
  2604  						(Zero {t6} [n] p6 _)))))))
  2605  	&& isSamePtr(p1, p2) && isSamePtr(p2, p3) && isSamePtr(p3, p4) && isSamePtr(p4, p5) && isSamePtr(p5, p6)
  2606  	&& t2.Alignment() <= t1.Alignment()
  2607  	&& t3.Alignment() <= t1.Alignment()
  2608  	&& t4.Alignment() <= t1.Alignment()
  2609  	&& t5.Alignment() <= t1.Alignment()
  2610  	&& t6.Alignment() <= t1.Alignment()
  2611  	&& registerizable(b, t2)
  2612  	&& registerizable(b, t3)
  2613  	&& registerizable(b, t4)
  2614  	&& registerizable(b, t5)
  2615  	&& n >= o2 + t2.Size()
  2616  	&& n >= o3 + t3.Size()
  2617  	&& n >= o4 + t4.Size()
  2618  	&& n >= o5 + t5.Size()
  2619  	=> (Store {t2} (OffPtr <tt2> [o2] dst) d1
  2620  		(Store {t3} (OffPtr <tt3> [o3] dst) d2
  2621  			(Store {t4} (OffPtr <tt4> [o4] dst) d3
  2622  				(Store {t5} (OffPtr <tt5> [o5] dst) d4
  2623  					(Zero {t1} [n] dst mem)))))
  2624  
  2625  (SelectN [0] call:(StaticLECall {sym} a x)) && needRaceCleanup(sym, call) && clobber(call) => x
  2626  (SelectN [0] call:(StaticLECall {sym} x)) && needRaceCleanup(sym, call) && clobber(call) => x
  2627  
  2628  // When rewriting append to growslice, we use as the new length the result of
  2629  // growslice so that we don't have to spill/restore the new length around the growslice call.
  2630  // The exception here is that if the new length is a constant, avoiding spilling it
  2631  // is pointless and its constantness is sometimes useful for subsequent optimizations.
  2632  // See issue 56440.
  2633  // Note there are 2 rules here, one for the pre-decomposed []T result and one for
  2634  // the post-decomposed (*T,int,int) result. (The latter is generated after call expansion.)
  2635  (SliceLen (SelectN [0] (StaticLECall {sym} _ newLen:(Const(64|32)) _ _ _ _))) && isSameCall(sym, "runtime.growslice") => newLen
  2636  (SelectN [1] (StaticCall {sym} _ newLen:(Const(64|32)) _ _ _ _)) && v.Type.IsInteger() && isSameCall(sym, "runtime.growslice") => newLen
  2637  
  2638  // Collapse moving A -> B -> C into just A -> C.
  2639  // Later passes (deadstore, elim unread auto) will remove the A -> B move, if possible.
  2640  // This happens most commonly when B is an autotmp inserted earlier
  2641  // during compilation to ensure correctness.
  2642  // Take care that overlapping moves are preserved.
  2643  // Restrict this optimization to the stack, to avoid duplicating loads from the heap;
  2644  // see CL 145208 for discussion.
  2645  (Move {t1} [s] dst tmp1 midmem:(Move {t2} [s] tmp2 src _))
  2646  	&& t1.Compare(t2) == types.CMPeq
  2647  	&& isSamePtr(tmp1, tmp2)
  2648  	&& isStackPtr(src) && !isVolatile(src)
  2649  	&& disjoint(src, s, tmp2, s)
  2650  	&& (disjoint(src, s, dst, s) || isInlinableMemmove(dst, src, s, config))
  2651  	=> (Move {t1} [s] dst src midmem)
  2652  
  2653  // Same, but for large types that require VarDefs.
  2654  (Move {t1} [s] dst tmp1 midmem:(VarDef (Move {t2} [s] tmp2 src _)))
  2655  	&& t1.Compare(t2) == types.CMPeq
  2656  	&& isSamePtr(tmp1, tmp2)
  2657  	&& isStackPtr(src) && !isVolatile(src)
  2658  	&& disjoint(src, s, tmp2, s)
  2659  	&& (disjoint(src, s, dst, s) || isInlinableMemmove(dst, src, s, config))
  2660  	=> (Move {t1} [s] dst src midmem)
  2661  
  2662  // Don't zero the same bits twice.
  2663  (Zero {t} [s] dst1 zero:(Zero {t} [s] dst2 _)) && isSamePtr(dst1, dst2) => zero
  2664  (Zero {t} [s] dst1 vardef:(VarDef (Zero {t} [s] dst2 _))) && isSamePtr(dst1, dst2) => vardef
  2665  
  2666  // Elide self-moves. This only happens rarely (e.g test/fixedbugs/bug277.go).
  2667  // However, this rule is needed to prevent the previous rule from looping forever in such cases.
  2668  (Move dst src mem) && isSamePtr(dst, src) => mem
  2669  
  2670  // Constant rotate detection.
  2671  ((Add64|Or64|Xor64) (Lsh64x64 x z:(Const64 <t> [c])) (Rsh64Ux64 x (Const64 [d]))) && c < 64 && d == 64-c && canRotate(config, 64) => (RotateLeft64 x z)
  2672  ((Add32|Or32|Xor32) (Lsh32x64 x z:(Const64 <t> [c])) (Rsh32Ux64 x (Const64 [d]))) && c < 32 && d == 32-c && canRotate(config, 32) => (RotateLeft32 x z)
  2673  ((Add16|Or16|Xor16) (Lsh16x64 x z:(Const64 <t> [c])) (Rsh16Ux64 x (Const64 [d]))) && c < 16 && d == 16-c && canRotate(config, 16) => (RotateLeft16 x z)
  2674  ((Add8|Or8|Xor8) (Lsh8x64 x z:(Const64 <t> [c])) (Rsh8Ux64 x (Const64 [d]))) && c < 8 && d == 8-c && canRotate(config, 8) => (RotateLeft8 x z)
  2675  
  2676  // Non-constant rotate detection.
  2677  // We use shiftIsBounded to make sure that neither of the shifts are >64.
  2678  // Note: these rules are subtle when the shift amounts are 0/64, as Go shifts
  2679  // are different from most native shifts. But it works out.
  2680  ((Add64|Or64|Xor64) left:(Lsh64x64 x y) right:(Rsh64Ux64 x (Sub64 (Const64 [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x y)
  2681  ((Add64|Or64|Xor64) left:(Lsh64x32 x y) right:(Rsh64Ux32 x (Sub32 (Const32 [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x y)
  2682  ((Add64|Or64|Xor64) left:(Lsh64x16 x y) right:(Rsh64Ux16 x (Sub16 (Const16 [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x y)
  2683  ((Add64|Or64|Xor64) left:(Lsh64x8  x y) right:(Rsh64Ux8  x (Sub8  (Const8  [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x y)
  2684  
  2685  ((Add64|Or64|Xor64) right:(Rsh64Ux64 x y) left:(Lsh64x64 x z:(Sub64 (Const64 [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x z)
  2686  ((Add64|Or64|Xor64) right:(Rsh64Ux32 x y) left:(Lsh64x32 x z:(Sub32 (Const32 [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x z)
  2687  ((Add64|Or64|Xor64) right:(Rsh64Ux16 x y) left:(Lsh64x16 x z:(Sub16 (Const16 [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x z)
  2688  ((Add64|Or64|Xor64) right:(Rsh64Ux8  x y) left:(Lsh64x8  x z:(Sub8  (Const8  [64]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 64) => (RotateLeft64 x z)
  2689  
  2690  ((Add32|Or32|Xor32) left:(Lsh32x64 x y) right:(Rsh32Ux64 x (Sub64 (Const64 [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x y)
  2691  ((Add32|Or32|Xor32) left:(Lsh32x32 x y) right:(Rsh32Ux32 x (Sub32 (Const32 [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x y)
  2692  ((Add32|Or32|Xor32) left:(Lsh32x16 x y) right:(Rsh32Ux16 x (Sub16 (Const16 [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x y)
  2693  ((Add32|Or32|Xor32) left:(Lsh32x8  x y) right:(Rsh32Ux8  x (Sub8  (Const8  [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x y)
  2694  
  2695  ((Add32|Or32|Xor32) right:(Rsh32Ux64 x y) left:(Lsh32x64 x z:(Sub64 (Const64 [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x z)
  2696  ((Add32|Or32|Xor32) right:(Rsh32Ux32 x y) left:(Lsh32x32 x z:(Sub32 (Const32 [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x z)
  2697  ((Add32|Or32|Xor32) right:(Rsh32Ux16 x y) left:(Lsh32x16 x z:(Sub16 (Const16 [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x z)
  2698  ((Add32|Or32|Xor32) right:(Rsh32Ux8  x y) left:(Lsh32x8  x z:(Sub8  (Const8  [32]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 32) => (RotateLeft32 x z)
  2699  
  2700  ((Add16|Or16|Xor16) left:(Lsh16x64 x y) right:(Rsh16Ux64 x (Sub64 (Const64 [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x y)
  2701  ((Add16|Or16|Xor16) left:(Lsh16x32 x y) right:(Rsh16Ux32 x (Sub32 (Const32 [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x y)
  2702  ((Add16|Or16|Xor16) left:(Lsh16x16 x y) right:(Rsh16Ux16 x (Sub16 (Const16 [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x y)
  2703  ((Add16|Or16|Xor16) left:(Lsh16x8  x y) right:(Rsh16Ux8  x (Sub8  (Const8  [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x y)
  2704  
  2705  ((Add16|Or16|Xor16) right:(Rsh16Ux64 x y) left:(Lsh16x64 x z:(Sub64 (Const64 [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x z)
  2706  ((Add16|Or16|Xor16) right:(Rsh16Ux32 x y) left:(Lsh16x32 x z:(Sub32 (Const32 [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x z)
  2707  ((Add16|Or16|Xor16) right:(Rsh16Ux16 x y) left:(Lsh16x16 x z:(Sub16 (Const16 [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x z)
  2708  ((Add16|Or16|Xor16) right:(Rsh16Ux8  x y) left:(Lsh16x8  x z:(Sub8  (Const8  [16]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 16) => (RotateLeft16 x z)
  2709  
  2710  ((Add8|Or8|Xor8) left:(Lsh8x64 x y) right:(Rsh8Ux64 x (Sub64 (Const64 [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x y)
  2711  ((Add8|Or8|Xor8) left:(Lsh8x32 x y) right:(Rsh8Ux32 x (Sub32 (Const32 [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x y)
  2712  ((Add8|Or8|Xor8) left:(Lsh8x16 x y) right:(Rsh8Ux16 x (Sub16 (Const16 [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x y)
  2713  ((Add8|Or8|Xor8) left:(Lsh8x8  x y) right:(Rsh8Ux8  x (Sub8  (Const8  [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x y)
  2714  
  2715  ((Add8|Or8|Xor8) right:(Rsh8Ux64 x y) left:(Lsh8x64 x z:(Sub64 (Const64 [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x z)
  2716  ((Add8|Or8|Xor8) right:(Rsh8Ux32 x y) left:(Lsh8x32 x z:(Sub32 (Const32 [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x z)
  2717  ((Add8|Or8|Xor8) right:(Rsh8Ux16 x y) left:(Lsh8x16 x z:(Sub16 (Const16 [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x z)
  2718  ((Add8|Or8|Xor8) right:(Rsh8Ux8  x y) left:(Lsh8x8  x z:(Sub8  (Const8  [8]) y))) && (shiftIsBounded(left) || shiftIsBounded(right)) && canRotate(config, 8) => (RotateLeft8 x z)
  2719  
  2720  // Rotating by y&c, with c a mask that doesn't change the bottom bits, is the same as rotating by y.
  2721  (RotateLeft64 x (And(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&63 == 63 => (RotateLeft64 x y)
  2722  (RotateLeft32 x (And(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&31 == 31 => (RotateLeft32 x y)
  2723  (RotateLeft16 x (And(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&15 == 15 => (RotateLeft16 x y)
  2724  (RotateLeft8  x (And(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&7  == 7  => (RotateLeft8  x y)
  2725  
  2726  // Rotating by -(y&c), with c a mask that doesn't change the bottom bits, is the same as rotating by -y.
  2727  (RotateLeft64 x (Neg(64|32|16|8) (And(64|32|16|8) y (Const(64|32|16|8) [c])))) && c&63 == 63 => (RotateLeft64 x (Neg(64|32|16|8) <y.Type> y))
  2728  (RotateLeft32 x (Neg(64|32|16|8) (And(64|32|16|8) y (Const(64|32|16|8) [c])))) && c&31 == 31 => (RotateLeft32 x (Neg(64|32|16|8) <y.Type> y))
  2729  (RotateLeft16 x (Neg(64|32|16|8) (And(64|32|16|8) y (Const(64|32|16|8) [c])))) && c&15 == 15 => (RotateLeft16 x (Neg(64|32|16|8) <y.Type> y))
  2730  (RotateLeft8  x (Neg(64|32|16|8) (And(64|32|16|8) y (Const(64|32|16|8) [c])))) && c&7  == 7  => (RotateLeft8  x (Neg(64|32|16|8) <y.Type> y))
  2731  
  2732  // Rotating by y+c, with c a multiple of the value width, is the same as rotating by y.
  2733  (RotateLeft64 x (Add(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&63 == 0 => (RotateLeft64 x y)
  2734  (RotateLeft32 x (Add(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&31 == 0 => (RotateLeft32 x y)
  2735  (RotateLeft16 x (Add(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&15 == 0 => (RotateLeft16 x y)
  2736  (RotateLeft8  x (Add(64|32|16|8) y (Const(64|32|16|8) [c]))) && c&7  == 0 => (RotateLeft8  x y)
  2737  
  2738  // Rotating by c-y, with c a multiple of the value width, is the same as rotating by -y.
  2739  (RotateLeft64 x (Sub(64|32|16|8) (Const(64|32|16|8) [c]) y)) && c&63 == 0 => (RotateLeft64 x (Neg(64|32|16|8) <y.Type> y))
  2740  (RotateLeft32 x (Sub(64|32|16|8) (Const(64|32|16|8) [c]) y)) && c&31 == 0 => (RotateLeft32 x (Neg(64|32|16|8) <y.Type> y))
  2741  (RotateLeft16 x (Sub(64|32|16|8) (Const(64|32|16|8) [c]) y)) && c&15 == 0 => (RotateLeft16 x (Neg(64|32|16|8) <y.Type> y))
  2742  (RotateLeft8  x (Sub(64|32|16|8) (Const(64|32|16|8) [c]) y)) && c&7  == 0 => (RotateLeft8  x (Neg(64|32|16|8) <y.Type> y))
  2743  
  2744  // Ensure we don't do Const64 rotates in a 32-bit system.
  2745  (RotateLeft64 x (Const64 <t> [c])) && config.PtrSize == 4 => (RotateLeft64 x (Const32 <t> [int32(c)]))
  2746  (RotateLeft32 x (Const64 <t> [c])) && config.PtrSize == 4 => (RotateLeft32 x (Const32 <t> [int32(c)]))
  2747  (RotateLeft16 x (Const64 <t> [c])) && config.PtrSize == 4 => (RotateLeft16 x (Const32 <t> [int32(c)]))
  2748  (RotateLeft8  x (Const64 <t> [c])) && config.PtrSize == 4 => (RotateLeft8  x (Const32 <t> [int32(c)]))
  2749  
  2750  // Rotating by c, then by d, is the same as rotating by c+d.
  2751  // We're trading a rotate for an add, which seems generally a good choice. It is especially good when c and d are constants.
  2752  // This rule is a bit tricky as c and d might be different widths. We handle only cases where they are the same width.
  2753  (RotateLeft(64|32|16|8) (RotateLeft(64|32|16|8) x c) d) && c.Type.Size() == 8 && d.Type.Size() == 8 => (RotateLeft(64|32|16|8) x (Add64 <c.Type> c d))
  2754  (RotateLeft(64|32|16|8) (RotateLeft(64|32|16|8) x c) d) && c.Type.Size() == 4 && d.Type.Size() == 4 => (RotateLeft(64|32|16|8) x (Add32 <c.Type> c d))
  2755  (RotateLeft(64|32|16|8) (RotateLeft(64|32|16|8) x c) d) && c.Type.Size() == 2 && d.Type.Size() == 2 => (RotateLeft(64|32|16|8) x (Add16 <c.Type> c d))
  2756  (RotateLeft(64|32|16|8) (RotateLeft(64|32|16|8) x c) d) && c.Type.Size() == 1 && d.Type.Size() == 1 => (RotateLeft(64|32|16|8) x (Add8  <c.Type> c d))
  2757  
  2758  // Loading constant values from dictionaries and itabs.
  2759  (Load <t> (OffPtr [off]                       (Addr {s} sb)       ) _) && t.IsUintptr() && isFixedSym(s, off) => (Addr {fixedSym(b.Func, s, off)} sb)
  2760  (Load <t> (OffPtr [off]              (Convert (Addr {s} sb) _)    ) _) && t.IsUintptr() && isFixedSym(s, off) => (Addr {fixedSym(b.Func, s, off)} sb)
  2761  (Load <t> (OffPtr [off] (ITab (IMake          (Addr {s} sb)    _))) _) && t.IsUintptr() && isFixedSym(s, off) => (Addr {fixedSym(b.Func, s, off)} sb)
  2762  (Load <t> (OffPtr [off] (ITab (IMake (Convert (Addr {s} sb) _) _))) _) && t.IsUintptr() && isFixedSym(s, off) => (Addr {fixedSym(b.Func, s, off)} sb)
  2763  
  2764  // Loading constant values from runtime._type.hash.
  2765  (Load <t> (OffPtr [off]                       (Addr {sym} _)       ) _) && t.IsInteger() && t.Size() == 4 && isFixed32(config, sym, off) => (Const32 [fixed32(config, sym, off)])
  2766  (Load <t> (OffPtr [off]              (Convert (Addr {sym} _) _)    ) _) && t.IsInteger() && t.Size() == 4 && isFixed32(config, sym, off) => (Const32 [fixed32(config, sym, off)])
  2767  (Load <t> (OffPtr [off] (ITab (IMake          (Addr {sym} _)    _))) _) && t.IsInteger() && t.Size() == 4 && isFixed32(config, sym, off) => (Const32 [fixed32(config, sym, off)])
  2768  (Load <t> (OffPtr [off] (ITab (IMake (Convert (Addr {sym} _) _) _))) _) && t.IsInteger() && t.Size() == 4 && isFixed32(config, sym, off) => (Const32 [fixed32(config, sym, off)])
  2769  
  2770  // Calling cmpstring a second time with the same arguments in the
  2771  // same memory state can reuse the results of the first call.
  2772  // See issue 61725.
  2773  // Note that this could pretty easily generalize to any pure function.
  2774  (SelectN [0] (StaticLECall {f} x y (SelectN [1] c:(StaticLECall {g} x y mem))))
  2775    && isSameCall(f, "runtime.cmpstring")
  2776    && isSameCall(g, "runtime.cmpstring")
  2777  => @c.Block (SelectN [0] <typ.Int> c)
  2778  
  2779  // If we don't use the result of cmpstring, might as well not call it.
  2780  // Note that this could pretty easily generalize to any pure function.
  2781  (SelectN [1] c:(StaticLECall {f} _ _ mem)) && c.Uses == 1 && isSameCall(f, "runtime.cmpstring") && clobber(c) => mem
  2782  
  2783  // We can easily compute the result of efaceeq if
  2784  // we know the underlying type is pointer-ish.
  2785  (StaticLECall {f} typ_ x y mem)
  2786  	&& isSameCall(f, "runtime.efaceeq")
  2787  	&& isDirectType(typ_)
  2788  	&& clobber(v)
  2789  	=> (MakeResult (EqPtr x y) mem)
  2790  
  2791  // We can easily compute the result of ifaceeq if
  2792  // we know the underlying type is pointer-ish.
  2793  (StaticLECall {f} itab x y mem)
  2794  	&& isSameCall(f, "runtime.ifaceeq")
  2795  	&& isDirectIface(itab)
  2796  	&& clobber(v)
  2797  	=> (MakeResult (EqPtr x y) mem)
  2798  
  2799  // If we use the result of slicebytetostring in a map lookup operation,
  2800  // then we don't need to actually do the []byte->string conversion.
  2801  // We can just use the ptr/len of the byte slice directly as a (temporary) string.
  2802  //
  2803  // Note that this does not handle some obscure cases like
  2804  // m[[2]string{string(b1), string(b2)}]. There is code in ../walk/order.go
  2805  // which handles some of those cases.
  2806  (StaticLECall {f} [argsize] typ_ map_ key:(SelectN [0] sbts:(StaticLECall {g} _ ptr len mem)) m:(SelectN [1] sbts))
  2807    &&    (isSameCall(f, "runtime.mapaccess1_faststr")
  2808        || isSameCall(f, "runtime.mapaccess2_faststr")
  2809        || isSameCall(f, "runtime.mapdelete_faststr"))
  2810    && isSameCall(g, "runtime.slicebytetostring")
  2811    && key.Uses == 1
  2812    && sbts.Uses == 2
  2813    && resetCopy(m, mem)
  2814    && clobber(sbts)
  2815    && clobber(key)
  2816  => (StaticLECall {f} [argsize] typ_ map_ (StringMake <typ.String> ptr len) mem)
  2817  

View as plain text