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

   1 // Copyright 2016 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         "cmd/internal/src"
   9         "fmt"
  10 )
  11
  12 // writebarrier expands write barrier ops (StoreWB, MoveWB, etc.) into
  13 // branches and runtime calls, like
  14 //
  15 // if writeBarrier.enabled {
  16 //   writebarrierptr(ptr, val)
  17 // } else {
  18 //   *ptr = val
  19 // }
  20 //
  21 // If ptr is an address of a stack slot, write barrier will be removed
  22 // and a normal store will be used.
  23 // A sequence of WB stores for many pointer fields of a single type will
  24 // be emitted together, with a single branch.
  25 //
  26 // Expanding WB ops introduces new control flows, and we would need to
  27 // split a block into two if there were values after WB ops, which would
  28 // require scheduling the values. To avoid this complexity, when building
  29 // SSA, we make sure that WB ops are always at the end of a block. We do
  30 // this before fuse as it may merge blocks. It also helps to reduce
  31 // number of blocks as fuse merges blocks introduced in this phase.
  32 func writebarrier(f *Func) {
  33         var sb, sp, wbaddr *Value
  34         var writebarrierptr, typedmemmove, typedmemclr interface{} // *gc.Sym
  35         var storeWBs, others []*Value
  36         var wbs *sparseSet
  37         for _, b := range f.Blocks { // range loop is safe since the blocks we added contain no WB stores
  38         valueLoop:
  39                 for i, v := range b.Values {
  40                         switch v.Op {
  41                         case OpStoreWB, OpMoveWB, OpMoveWBVolatile, OpZeroWB:
  42                                 if IsStackAddr(v.Args[0]) {
  43                                         switch v.Op {
  44                                         case OpStoreWB:
  45                                                 v.Op = OpStore
  46                                         case OpMoveWB, OpMoveWBVolatile:
  47                                                 v.Op = OpMove
  48                                                 v.Aux = nil
  49                                         case OpZeroWB:
  50                                                 v.Op = OpZero
  51                                                 v.Aux = nil
  52                                         }
  53                                         continue
  54                                 }
  55
  56                                 if wbaddr == nil {
  57                                         // initalize global values for write barrier test and calls
  58                                         // find SB and SP values in entry block
  59                                         initln := f.Entry.Pos
  60                                         for _, v := range f.Entry.Values {
  61                                                 if v.Op == OpSB {
  62                                                         sb = v
  63                                                 }
  64                                                 if v.Op == OpSP {
  65                                                         sp = v
  66                                                 }
  67                                         }
  68                                         if sb == nil {
  69                                                 sb = f.Entry.NewValue0(initln, OpSB, f.Config.fe.TypeUintptr())
  70                                         }
  71                                         if sp == nil {
  72                                                 sp = f.Entry.NewValue0(initln, OpSP, f.Config.fe.TypeUintptr())
  73                                         }
  74                                         wbsym := &ExternSymbol{Typ: f.Config.fe.TypeBool(), Sym: f.Config.fe.Syslook("writeBarrier").(fmt.Stringer)}
  75                                         wbaddr = f.Entry.NewValue1A(initln, OpAddr, f.Config.fe.TypeUInt32().PtrTo(), wbsym, sb)
  76                                         writebarrierptr = f.Config.fe.Syslook("writebarrierptr")
  77                                         typedmemmove = f.Config.fe.Syslook("typedmemmove")
  78                                         typedmemclr = f.Config.fe.Syslook("typedmemclr")
  79
  80                                         wbs = f.newSparseSet(f.NumValues())
  81                                         defer f.retSparseSet(wbs)
  82                                 }
  83
  84                                 pos := v.Pos
  85
  86                                 // there may be a sequence of WB stores in the current block. find them.
  87                                 storeWBs = storeWBs[:0]
  88                                 others = others[:0]
  89                                 wbs.clear()
  90                                 for _, w := range b.Values[i:] {
  91                                         if w.Op == OpStoreWB || w.Op == OpMoveWB || w.Op == OpMoveWBVolatile || w.Op == OpZeroWB {
  92                                                 storeWBs = append(storeWBs, w)
  93                                                 wbs.add(w.ID)
  94                                         } else {
  95                                                 others = append(others, w)
  96                                         }
  97                                 }
  98
  99                                 // make sure that no value in this block depends on WB stores
 100                                 for _, w := range b.Values {
 101                                         if w.Op == OpStoreWB || w.Op == OpMoveWB || w.Op == OpMoveWBVolatile || w.Op == OpZeroWB {
 102                                                 continue
 103                                         }
 104                                         for _, a := range w.Args {
 105                                                 if wbs.contains(a.ID) {
 106                                                         f.Fatalf("value %v depends on WB store %v in the same block %v", w, a, b)
 107                                                 }
 108                                         }
 109                                 }
 110
 111                                 // find the memory before the WB stores
 112                                 // this memory is not a WB store but it is used in a WB store.
 113                                 var mem *Value
 114                                 for _, w := range storeWBs {
 115                                         a := w.Args[len(w.Args)-1]
 116                                         if wbs.contains(a.ID) {
 117                                                 continue
 118                                         }
 119                                         if mem != nil {
 120                                                 b.Fatalf("two stores live simultaneously: %s, %s", mem, a)
 121                                         }
 122                                         mem = a
 123                                 }
 124
 125                                 b.Values = append(b.Values[:i], others...) // move WB ops out of this block
 126
 127                                 bThen := f.NewBlock(BlockPlain)
 128                                 bElse := f.NewBlock(BlockPlain)
 129                                 bEnd := f.NewBlock(b.Kind)
 130                                 bThen.Pos = pos
 131                                 bElse.Pos = pos
 132                                 bEnd.Pos = pos
 133
 134                                 // set up control flow for end block
 135                                 bEnd.SetControl(b.Control)
 136                                 bEnd.Likely = b.Likely
 137                                 for _, e := range b.Succs {
 138                                         bEnd.Succs = append(bEnd.Succs, e)
 139                                         e.b.Preds[e.i].b = bEnd
 140                                 }
 141
 142                                 // set up control flow for write barrier test
 143                                 // load word, test word, avoiding partial register write from load byte.
 144                                 flag := b.NewValue2(pos, OpLoad, f.Config.fe.TypeUInt32(), wbaddr, mem)
 145                                 const0 := f.ConstInt32(pos, f.Config.fe.TypeUInt32(), 0)
 146                                 flag = b.NewValue2(pos, OpNeq32, f.Config.fe.TypeBool(), flag, const0)
 147                                 b.Kind = BlockIf
 148                                 b.SetControl(flag)
 149                                 b.Likely = BranchUnlikely
 150                                 b.Succs = b.Succs[:0]
 151                                 b.AddEdgeTo(bThen)
 152                                 b.AddEdgeTo(bElse)
 153                                 bThen.AddEdgeTo(bEnd)
 154                                 bElse.AddEdgeTo(bEnd)
 155
 156                                 memThen := mem
 157                                 memElse := mem
 158                                 for _, w := range storeWBs {
 159                                         var val *Value
 160                                         ptr := w.Args[0]
 161                                         siz := w.AuxInt
 162                                         typ := w.Aux // only non-nil for MoveWB, MoveWBVolatile, ZeroWB
 163
 164                                         var op Op
 165                                         var fn interface{} // *gc.Sym
 166                                         switch w.Op {
 167                                         case OpStoreWB:
 168                                                 op = OpStore
 169                                                 fn = writebarrierptr
 170                                                 val = w.Args[1]
 171                                         case OpMoveWB, OpMoveWBVolatile:
 172                                                 op = OpMove
 173                                                 fn = typedmemmove
 174                                                 val = w.Args[1]
 175                                         case OpZeroWB:
 176                                                 op = OpZero
 177                                                 fn = typedmemclr
 178                                         }
 179
 180                                         // then block: emit write barrier call
 181                                         memThen = wbcall(pos, bThen, fn, typ, ptr, val, memThen, sp, sb, w.Op == OpMoveWBVolatile)
 182
 183                                         // else block: normal store
 184                                         if op == OpZero {
 185                                                 memElse = bElse.NewValue2I(pos, op, TypeMem, siz, ptr, memElse)
 186                                         } else {
 187                                                 memElse = bElse.NewValue3I(pos, op, TypeMem, siz, ptr, val, memElse)
 188                                         }
 189                                 }
 190
 191                                 // merge memory
 192                                 // Splice memory Phi into the last memory of the original sequence,
 193                                 // which may be used in subsequent blocks. Other memories in the
 194                                 // sequence must be dead after this block since there can be only
 195                                 // one memory live.
 196                                 last := storeWBs[0]
 197                                 if len(storeWBs) > 1 {
 198                                         // find the last store
 199                                         last = nil
 200                                         wbs.clear() // we reuse wbs to record WB stores that is used in another WB store
 201                                         for _, w := range storeWBs {
 202                                                 wbs.add(w.Args[len(w.Args)-1].ID)
 203                                         }
 204                                         for _, w := range storeWBs {
 205                                                 if wbs.contains(w.ID) {
 206                                                         continue
 207                                                 }
 208                                                 if last != nil {
 209                                                         b.Fatalf("two stores live simultaneously: %s, %s", last, w)
 210                                                 }
 211                                                 last = w
 212                                         }
 213                                 }
 214                                 bEnd.Values = append(bEnd.Values, last)
 215                                 last.Block = bEnd
 216                                 last.reset(OpPhi)
 217                                 last.Type = TypeMem
 218                                 last.AddArg(memThen)
 219                                 last.AddArg(memElse)
 220                                 for _, w := range storeWBs {
 221                                         if w != last {
 222                                                 w.resetArgs()
 223                                         }
 224                                 }
 225                                 for _, w := range storeWBs {
 226                                         if w != last {
 227                                                 f.freeValue(w)
 228                                         }
 229                                 }
 230
 231                                 if f.Config.fe.Debug_wb() {
 232                                         f.Config.Warnl(pos, "write barrier")
 233                                 }
 234
 235                                 break valueLoop
 236                         }
 237                 }
 238         }
 239 }
 240
 241 // wbcall emits write barrier runtime call in b, returns memory.
 242 // if valIsVolatile, it moves val into temp space before making the call.
 243 func wbcall(pos src.XPos, b *Block, fn interface{}, typ interface{}, ptr, val, mem, sp, sb *Value, valIsVolatile bool) *Value {
 244         config := b.Func.Config
 245
 246         var tmp GCNode
 247         if valIsVolatile {
 248                 // Copy to temp location if the source is volatile (will be clobbered by
 249                 // a function call). Marshaling the args to typedmemmove might clobber the
 250                 // value we're trying to move.
 251                 t := val.Type.ElemType()
 252                 tmp = config.fe.Auto(t)
 253                 aux := &AutoSymbol{Typ: t, Node: tmp}
 254                 mem = b.NewValue1A(pos, OpVarDef, TypeMem, tmp, mem)
 255                 tmpaddr := b.NewValue1A(pos, OpAddr, t.PtrTo(), aux, sp)
 256                 siz := MakeSizeAndAlign(t.Size(), t.Alignment()).Int64()
 257                 mem = b.NewValue3I(pos, OpMove, TypeMem, siz, tmpaddr, val, mem)
 258                 val = tmpaddr
 259         }
 260
 261         // put arguments on stack
 262         off := config.ctxt.FixedFrameSize()
 263
 264         if typ != nil { // for typedmemmove
 265                 taddr := b.NewValue1A(pos, OpAddr, config.fe.TypeUintptr(), typ, sb)
 266                 off = round(off, taddr.Type.Alignment())
 267                 arg := b.NewValue1I(pos, OpOffPtr, taddr.Type.PtrTo(), off, sp)
 268                 mem = b.NewValue3I(pos, OpStore, TypeMem, ptr.Type.Size(), arg, taddr, mem)
 269                 off += taddr.Type.Size()
 270         }
 271
 272         off = round(off, ptr.Type.Alignment())
 273         arg := b.NewValue1I(pos, OpOffPtr, ptr.Type.PtrTo(), off, sp)
 274         mem = b.NewValue3I(pos, OpStore, TypeMem, ptr.Type.Size(), arg, ptr, mem)
 275         off += ptr.Type.Size()
 276
 277         if val != nil {
 278                 off = round(off, val.Type.Alignment())
 279                 arg = b.NewValue1I(pos, OpOffPtr, val.Type.PtrTo(), off, sp)
 280                 mem = b.NewValue3I(pos, OpStore, TypeMem, val.Type.Size(), arg, val, mem)
 281                 off += val.Type.Size()
 282         }
 283         off = round(off, config.PtrSize)
 284
 285         // issue call
 286         mem = b.NewValue1A(pos, OpStaticCall, TypeMem, fn, mem)
 287         mem.AuxInt = off - config.ctxt.FixedFrameSize()
 288
 289         if valIsVolatile {
 290                 mem = b.NewValue1A(pos, OpVarKill, TypeMem, tmp, mem) // mark temp dead
 291         }
 292
 293         return mem
 294 }
 295
 296 // round to a multiple of r, r is a power of 2
 297 func round(o int64, r int64) int64 {
 298         return (o + r - 1) &^ (r - 1)
 299 }
 300
 301 // IsStackAddr returns whether v is known to be an address of a stack slot
 302 func IsStackAddr(v *Value) bool {
 303         for v.Op == OpOffPtr || v.Op == OpAddPtr || v.Op == OpPtrIndex || v.Op == OpCopy {
 304                 v = v.Args[0]
 305         }
 306         switch v.Op {
 307         case OpSP:
 308                 return true
 309         case OpAddr:
 310                 return v.Args[0].Op == OpSP
 311         }
 312         return false
 313 }