src/cmd/compile/internal/ssa/deadstore.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         "cmd/compile/internal/ir"
   9         "cmd/compile/internal/types"
  10 )
  11
  12 // dse does dead-store elimination on the Function.
  13 // Dead stores are those which are unconditionally followed by
  14 // another store to the same location, with no intervening load.
  15 // This implementation only works within a basic block. TODO: use something more global.
  16 func dse(f *Func) {
  17         var stores []*Value
  18         loadUse := f.newSparseSet(f.NumValues())
  19         defer f.retSparseSet(loadUse)
  20         storeUse := f.newSparseSet(f.NumValues())
  21         defer f.retSparseSet(storeUse)
  22         shadowed := f.newSparseMap(f.NumValues())
  23         defer f.retSparseMap(shadowed)
  24         for _, b := range f.Blocks {
  25                 // Find all the stores in this block. Categorize their uses:
  26                 //  loadUse contains stores which are used by a subsequent load.
  27                 //  storeUse contains stores which are used by a subsequent store.
  28                 loadUse.clear()
  29                 storeUse.clear()
  30                 stores = stores[:0]
  31                 for _, v := range b.Values {
  32                         if v.Op == OpPhi {
  33                                 // Ignore phis - they will always be first and can't be eliminated
  34                                 continue
  35                         }
  36                         if v.Type.IsMemory() {
  37                                 stores = append(stores, v)
  38                                 for _, a := range v.Args {
  39                                         if a.Block == b && a.Type.IsMemory() {
  40                                                 storeUse.add(a.ID)
  41                                                 if v.Op != OpStore && v.Op != OpZero && v.Op != OpVarDef {
  42                                                         // CALL, DUFFCOPY, etc. are both
  43                                                         // reads and writes.
  44                                                         loadUse.add(a.ID)
  45                                                 }
  46                                         }
  47                                 }
  48                         } else {
  49                                 for _, a := range v.Args {
  50                                         if a.Block == b && a.Type.IsMemory() {
  51                                                 loadUse.add(a.ID)
  52                                         }
  53                                 }
  54                         }
  55                 }
  56                 if len(stores) == 0 {
  57                         continue
  58                 }
  59
  60                 // find last store in the block
  61                 var last *Value
  62                 for _, v := range stores {
  63                         if storeUse.contains(v.ID) {
  64                                 continue
  65                         }
  66                         if last != nil {
  67                                 b.Fatalf("two final stores - simultaneous live stores %s %s", last.LongString(), v.LongString())
  68                         }
  69                         last = v
  70                 }
  71                 if last == nil {
  72                         b.Fatalf("no last store found - cycle?")
  73                 }
  74
  75                 // Walk backwards looking for dead stores. Keep track of shadowed addresses.
  76                 // A "shadowed address" is a pointer, offset, and size describing a memory region that
  77                 // is known to be written. We keep track of shadowed addresses in the shadowed map,
  78                 // mapping the ID of the address to a shadowRange where future writes will happen.
  79                 // Since we're walking backwards, writes to a shadowed region are useless,
  80                 // as they will be immediately overwritten.
  81                 shadowed.clear()
  82                 v := last
  83
  84         walkloop:
  85                 if loadUse.contains(v.ID) {
  86                         // Someone might be reading this memory state.
  87                         // Clear all shadowed addresses.
  88                         shadowed.clear()
  89                 }
  90                 if v.Op == OpStore || v.Op == OpZero {
  91                         ptr := v.Args[0]
  92                         var off int64
  93                         for ptr.Op == OpOffPtr { // Walk to base pointer
  94                                 off += ptr.AuxInt
  95                                 ptr = ptr.Args[0]
  96                         }
  97                         var sz int64
  98                         if v.Op == OpStore {
  99                                 sz = v.Aux.(*types.Type).Size()
 100                         } else { // OpZero
 101                                 sz = v.AuxInt
 102                         }
 103                         sr := shadowRange(shadowed.get(ptr.ID))
 104                         if sr.contains(off, off+sz) {
 105                                 // Modify the store/zero into a copy of the memory state,
 106                                 // effectively eliding the store operation.
 107                                 if v.Op == OpStore {
 108                                         // store addr value mem
 109                                         v.SetArgs1(v.Args[2])
 110                                 } else {
 111                                         // zero addr mem
 112                                         v.SetArgs1(v.Args[1])
 113                                 }
 114                                 v.Aux = nil
 115                                 v.AuxInt = 0
 116                                 v.Op = OpCopy
 117                         } else {
 118                                 // Extend shadowed region.
 119                                 shadowed.set(ptr.ID, int32(sr.merge(off, off+sz)))
 120                         }
 121                 }
 122                 // walk to previous store
 123                 if v.Op == OpPhi {
 124                         // At start of block.  Move on to next block.
 125                         // The memory phi, if it exists, is always
 126                         // the first logical store in the block.
 127                         // (Even if it isn't the first in the current b.Values order.)
 128                         continue
 129                 }
 130                 for _, a := range v.Args {
 131                         if a.Block == b && a.Type.IsMemory() {
 132                                 v = a
 133                                 goto walkloop
 134                         }
 135                 }
 136         }
 137 }
 138
 139 // A shadowRange encodes a set of byte offsets [lo():hi()] from
 140 // a given pointer that will be written to later in the block.
 141 // A zero shadowRange encodes an empty shadowed range (and so
 142 // does a -1 shadowRange, which is what sparsemap.get returns
 143 // on a failed lookup).
 144 type shadowRange int32
 145
 146 func (sr shadowRange) lo() int64 {
 147         return int64(sr & 0xffff)
 148 }
 149 func (sr shadowRange) hi() int64 {
 150         return int64((sr >> 16) & 0xffff)
 151 }
 152
 153 // contains reports whether [lo:hi] is completely within sr.
 154 func (sr shadowRange) contains(lo, hi int64) bool {
 155         return lo >= sr.lo() && hi <= sr.hi()
 156 }
 157
 158 // merge returns the union of sr and [lo:hi].
 159 // merge is allowed to return something smaller than the union.
 160 func (sr shadowRange) merge(lo, hi int64) shadowRange {
 161         if lo < 0 || hi > 0xffff {
 162                 // Ignore offsets that are too large or small.
 163                 return sr
 164         }
 165         if sr.lo() == sr.hi() {
 166                 // Old range is empty - use new one.
 167                 return shadowRange(lo + hi<<16)
 168         }
 169         if hi < sr.lo() || lo > sr.hi() {
 170                 // The two regions don't overlap or abut, so we would
 171                 // have to keep track of multiple disjoint ranges.
 172                 // Because we can only keep one, keep the larger one.
 173                 if sr.hi()-sr.lo() >= hi-lo {
 174                         return sr
 175                 }
 176                 return shadowRange(lo + hi<<16)
 177         }
 178         // Regions overlap or abut - compute the union.
 179         return shadowRange(min(lo, sr.lo()) + max(hi, sr.hi())<<16)
 180 }
 181
 182 // elimDeadAutosGeneric deletes autos that are never accessed. To achieve this
 183 // we track the operations that the address of each auto reaches and if it only
 184 // reaches stores then we delete all the stores. The other operations will then
 185 // be eliminated by the dead code elimination pass.
 186 func elimDeadAutosGeneric(f *Func) {
 187         addr := make(map[*Value]*ir.Name) // values that the address of the auto reaches
 188         elim := make(map[*Value]*ir.Name) // values that could be eliminated if the auto is
 189         var used ir.NameSet               // used autos that must be kept
 190
 191         // visit the value and report whether any of the maps are updated
 192         visit := func(v *Value) (changed bool) {
 193                 args := v.Args
 194                 switch v.Op {
 195                 case OpAddr, OpLocalAddr:
 196                         // Propagate the address if it points to an auto.
 197                         n, ok := v.Aux.(*ir.Name)
 198                         if !ok || n.Class != ir.PAUTO {
 199                                 return
 200                         }
 201                         if addr[v] == nil {
 202                                 addr[v] = n
 203                                 changed = true
 204                         }
 205                         return
 206                 case OpVarDef:
 207                         // v should be eliminated if we eliminate the auto.
 208                         n, ok := v.Aux.(*ir.Name)
 209                         if !ok || n.Class != ir.PAUTO {
 210                                 return
 211                         }
 212                         if elim[v] == nil {
 213                                 elim[v] = n
 214                                 changed = true
 215                         }
 216                         return
 217                 case OpVarLive:
 218                         // Don't delete the auto if it needs to be kept alive.
 219
 220                         // We depend on this check to keep the autotmp stack slots
 221                         // for open-coded defers from being removed (since they
 222                         // may not be used by the inline code, but will be used by
 223                         // panic processing).
 224                         n, ok := v.Aux.(*ir.Name)
 225                         if !ok || n.Class != ir.PAUTO {
 226                                 return
 227                         }
 228                         if !used.Has(n) {
 229                                 used.Add(n)
 230                                 changed = true
 231                         }
 232                         return
 233                 case OpStore, OpMove, OpZero:
 234                         // v should be eliminated if we eliminate the auto.
 235                         n, ok := addr[args[0]]
 236                         if ok && elim[v] == nil {
 237                                 elim[v] = n
 238                                 changed = true
 239                         }
 240                         // Other args might hold pointers to autos.
 241                         args = args[1:]
 242                 }
 243
 244                 // The code below assumes that we have handled all the ops
 245                 // with sym effects already. Sanity check that here.
 246                 // Ignore Args since they can't be autos.
 247                 if v.Op.SymEffect() != SymNone && v.Op != OpArg {
 248                         panic("unhandled op with sym effect")
 249                 }
 250
 251                 if v.Uses == 0 && v.Op != OpNilCheck && !v.Op.IsCall() && !v.Op.HasSideEffects() || len(args) == 0 {
 252                         // Nil check has no use, but we need to keep it.
 253                         // Also keep calls and values that have side effects.
 254                         return
 255                 }
 256
 257                 // If the address of the auto reaches a memory or control
 258                 // operation not covered above then we probably need to keep it.
 259                 // We also need to keep autos if they reach Phis (issue #26153).
 260                 if v.Type.IsMemory() || v.Type.IsFlags() || v.Op == OpPhi || v.MemoryArg() != nil {
 261                         for _, a := range args {
 262                                 if n, ok := addr[a]; ok {
 263                                         if !used.Has(n) {
 264                                                 used.Add(n)
 265                                                 changed = true
 266                                         }
 267                                 }
 268                         }
 269                         return
 270                 }
 271
 272                 // Propagate any auto addresses through v.
 273                 var node *ir.Name
 274                 for _, a := range args {
 275                         if n, ok := addr[a]; ok && !used.Has(n) {
 276                                 if node == nil {
 277                                         node = n
 278                                 } else if node != n {
 279                                         // Most of the time we only see one pointer
 280                                         // reaching an op, but some ops can take
 281                                         // multiple pointers (e.g. NeqPtr, Phi etc.).
 282                                         // This is rare, so just propagate the first
 283                                         // value to keep things simple.
 284                                         used.Add(n)
 285                                         changed = true
 286                                 }
 287                         }
 288                 }
 289                 if node == nil {
 290                         return
 291                 }
 292                 if addr[v] == nil {
 293                         // The address of an auto reaches this op.
 294                         addr[v] = node
 295                         changed = true
 296                         return
 297                 }
 298                 if addr[v] != node {
 299                         // This doesn't happen in practice, but catch it just in case.
 300                         used.Add(node)
 301                         changed = true
 302                 }
 303                 return
 304         }
 305
 306         iterations := 0
 307         for {
 308                 if iterations == 4 {
 309                         // give up
 310                         return
 311                 }
 312                 iterations++
 313                 changed := false
 314                 for _, b := range f.Blocks {
 315                         for _, v := range b.Values {
 316                                 changed = visit(v) || changed
 317                         }
 318                         // keep the auto if its address reaches a control value
 319                         for _, c := range b.ControlValues() {
 320                                 if n, ok := addr[c]; ok && !used.Has(n) {
 321                                         used.Add(n)
 322                                         changed = true
 323                                 }
 324                         }
 325                 }
 326                 if !changed {
 327                         break
 328                 }
 329         }
 330
 331         // Eliminate stores to unread autos.
 332         for v, n := range elim {
 333                 if used.Has(n) {
 334                         continue
 335                 }
 336                 // replace with OpCopy
 337                 v.SetArgs1(v.MemoryArg())
 338                 v.Aux = nil
 339                 v.AuxInt = 0
 340                 v.Op = OpCopy
 341         }
 342 }
 343
 344 // elimUnreadAutos deletes stores (and associated bookkeeping ops VarDef and VarKill)
 345 // to autos that are never read from.
 346 func elimUnreadAutos(f *Func) {
 347         // Loop over all ops that affect autos taking note of which
 348         // autos we need and also stores that we might be able to
 349         // eliminate.
 350         var seen ir.NameSet
 351         var stores []*Value
 352         for _, b := range f.Blocks {
 353                 for _, v := range b.Values {
 354                         n, ok := v.Aux.(*ir.Name)
 355                         if !ok {
 356                                 continue
 357                         }
 358                         if n.Class != ir.PAUTO {
 359                                 continue
 360                         }
 361
 362                         effect := v.Op.SymEffect()
 363                         switch effect {
 364                         case SymNone, SymWrite:
 365                                 // If we haven't seen the auto yet
 366                                 // then this might be a store we can
 367                                 // eliminate.
 368                                 if !seen.Has(n) {
 369                                         stores = append(stores, v)
 370                                 }
 371                         default:
 372                                 // Assume the auto is needed (loaded,
 373                                 // has its address taken, etc.).
 374                                 // Note we have to check the uses
 375                                 // because dead loads haven't been
 376                                 // eliminated yet.
 377                                 if v.Uses > 0 {
 378                                         seen.Add(n)
 379                                 }
 380                         }
 381                 }
 382         }
 383
 384         // Eliminate stores to unread autos.
 385         for _, store := range stores {
 386                 n, _ := store.Aux.(*ir.Name)
 387                 if seen.Has(n) {
 388                         continue
 389                 }
 390
 391                 // replace store with OpCopy
 392                 store.SetArgs1(store.MemoryArg())
 393                 store.Aux = nil
 394                 store.AuxInt = 0
 395                 store.Op = OpCopy
 396         }
 397 }