src/cmd/compile/internal/ssa/rewrite.go

   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 package ssa
   6
   7 import (
   8         "fmt"
   9         "math"
  10 )
  11
  12 func applyRewrite(f *Func, rb func(*Block) bool, rv func(*Value, *Config) bool) {
  13         // repeat rewrites until we find no more rewrites
  14         var curb *Block
  15         var curv *Value
  16         defer func() {
  17                 if curb != nil {
  18                         curb.Fatalf("panic during rewrite of block %s\n", curb.LongString())
  19                 }
  20                 if curv != nil {
  21                         curv.Fatalf("panic during rewrite of value %s\n", curv.LongString())
  22                         // TODO(khr): print source location also
  23                 }
  24         }()
  25         config := f.Config
  26         for {
  27                 change := false
  28                 for _, b := range f.Blocks {
  29                         if b.Kind == BlockDead {
  30                                 continue
  31                         }
  32                         if b.Control != nil && b.Control.Op == OpCopy {
  33                                 for b.Control.Op == OpCopy {
  34                                         b.Control = b.Control.Args[0]
  35                                 }
  36                         }
  37                         curb = b
  38                         if rb(b) {
  39                                 change = true
  40                         }
  41                         curb = nil
  42                         for _, v := range b.Values {
  43                                 // elide any copies generated during rewriting
  44                                 for i, a := range v.Args {
  45                                         if a.Op != OpCopy {
  46                                                 continue
  47                                         }
  48                                         // Rewriting can generate OpCopy loops.
  49                                         // They are harmless (see removePredecessor),
  50                                         // but take care to stop if we find a cycle.
  51                                         slow := a // advances every other iteration
  52                                         var advance bool
  53                                         for a.Op == OpCopy {
  54                                                 a = a.Args[0]
  55                                                 if slow == a {
  56                                                         break
  57                                                 }
  58                                                 if advance {
  59                                                         slow = a
  60                                                 }
  61                                                 advance = !advance
  62                                         }
  63                                         v.Args[i] = a
  64                                 }
  65
  66                                 // apply rewrite function
  67                                 curv = v
  68                                 if rv(v, config) {
  69                                         change = true
  70                                 }
  71                                 curv = nil
  72                         }
  73                 }
  74                 if !change {
  75                         return
  76                 }
  77         }
  78 }
  79
  80 // Common functions called from rewriting rules
  81
  82 func is64BitFloat(t Type) bool {
  83         return t.Size() == 8 && t.IsFloat()
  84 }
  85
  86 func is32BitFloat(t Type) bool {
  87         return t.Size() == 4 && t.IsFloat()
  88 }
  89
  90 func is64BitInt(t Type) bool {
  91         return t.Size() == 8 && t.IsInteger()
  92 }
  93
  94 func is32BitInt(t Type) bool {
  95         return t.Size() == 4 && t.IsInteger()
  96 }
  97
  98 func is16BitInt(t Type) bool {
  99         return t.Size() == 2 && t.IsInteger()
 100 }
 101
 102 func is8BitInt(t Type) bool {
 103         return t.Size() == 1 && t.IsInteger()
 104 }
 105
 106 func isPtr(t Type) bool {
 107         return t.IsPtr()
 108 }
 109
 110 func isSigned(t Type) bool {
 111         return t.IsSigned()
 112 }
 113
 114 func typeSize(t Type) int64 {
 115         return t.Size()
 116 }
 117
 118 // addOff adds two int64 offsets. Fails if wraparound happens.
 119 func addOff(x, y int64) int64 {
 120         z := x + y
 121         // x and y have same sign and z has a different sign => overflow
 122         if x^y >= 0 && x^z < 0 {
 123                 panic(fmt.Sprintf("offset overflow %d %d", x, y))
 124         }
 125         return z
 126 }
 127
 128 // mergeSym merges two symbolic offsets.  There is no real merging of
 129 // offsets, we just pick the non-nil one.
 130 func mergeSym(x, y interface{}) interface{} {
 131         if x == nil {
 132                 return y
 133         }
 134         if y == nil {
 135                 return x
 136         }
 137         panic(fmt.Sprintf("mergeSym with two non-nil syms %s %s", x, y))
 138         return nil
 139 }
 140 func canMergeSym(x, y interface{}) bool {
 141         return x == nil || y == nil
 142 }
 143
 144 func inBounds8(idx, len int64) bool  { return int8(idx) >= 0 && int8(idx) < int8(len) }
 145 func inBounds16(idx, len int64) bool { return int16(idx) >= 0 && int16(idx) < int16(len) }
 146 func inBounds32(idx, len int64) bool { return int32(idx) >= 0 && int32(idx) < int32(len) }
 147 func inBounds64(idx, len int64) bool { return idx >= 0 && idx < len }
 148
 149 // log2 returns logarithm in base of n.
 150 // expects n to be a power of 2.
 151 func log2(n int64) (l int64) {
 152         for n > 1 {
 153                 l++
 154                 n >>= 1
 155         }
 156         return l
 157 }
 158
 159 // isPowerOfTwo reports whether n is a power of 2.
 160 func isPowerOfTwo(n int64) bool {
 161         return n > 0 && n&(n-1) == 0
 162 }
 163
 164 // is32Bit reports whether n can be represented as a signed 32 bit integer.
 165 func is32Bit(n int64) bool {
 166         return n == int64(int32(n))
 167 }
 168
 169 // b2i translates a boolean value to 0 or 1 for assigning to auxInt.
 170 func b2i(b bool) int64 {
 171         if b {
 172                 return 1
 173         }
 174         return 0
 175 }
 176
 177 // f2i is used in the rules for storing a float in AuxInt.
 178 func f2i(f float64) int64 {
 179         return int64(math.Float64bits(f))
 180 }
 181
 182 // DUFFZERO consists of repeated blocks of 4 MOVs + ADD,
 183 // with 4 STOSQs at the very end.
 184 // The trailing STOSQs prevent the need for a DI preadjustment
 185 // for small numbers of words to clear.
 186 // See runtime/mkduff.go.
 187 const (
 188         dzBlocks    = 31 // number of MOV/ADD blocks
 189         dzBlockLen  = 4  // number of clears per block
 190         dzBlockSize = 19 // size of instructions in a single block
 191         dzMovSize   = 4  // size of single MOV instruction w/ offset
 192         dzAddSize   = 4  // size of single ADD instruction
 193         dzDIStep    = 8  // number of bytes cleared by each MOV instruction
 194
 195         dzTailLen  = 4 // number of final STOSQ instructions
 196         dzTailSize = 2 // size of single STOSQ instruction
 197
 198         dzSize = dzBlocks*dzBlockSize + dzTailLen*dzTailSize // total size of DUFFZERO routine
 199 )
 200
 201 func duffStart(size int64) int64 {
 202         x, _ := duff(size)
 203         return x
 204 }
 205 func duffAdj(size int64) int64 {
 206         _, x := duff(size)
 207         return x
 208 }
 209
 210 // duff returns the offset (from duffzero, in bytes) and pointer adjust (in bytes)
 211 // required to use the duffzero mechanism for a block of the given size.
 212 func duff(size int64) (int64, int64) {
 213         if size < 32 || size > 1024 || size%8 != 0 {
 214                 panic("bad duffzero size")
 215         }
 216         // TODO: arch-dependent
 217         off := int64(dzSize)
 218         off -= dzTailLen * dzTailSize
 219         size -= dzTailLen * dzDIStep
 220         q := size / dzDIStep
 221         blocks, singles := q/dzBlockLen, q%dzBlockLen
 222         off -= dzBlockSize * blocks
 223         var adj int64
 224         if singles > 0 {
 225                 off -= dzAddSize + dzMovSize*singles
 226                 adj -= dzDIStep * (dzBlockLen - singles)
 227         }
 228         return off, adj
 229 }