src/cmd/compile/internal/ssa/block.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/internal/src"
   9         "fmt"
  10 )
  11
  12 // Block represents a basic block in the control flow graph of a function.
  13 type Block struct {
  14         // A unique identifier for the block. The system will attempt to allocate
  15         // these IDs densely, but no guarantees.
  16         ID ID
  17
  18         // Source position for block's control operation
  19         Pos src.XPos
  20
  21         // The kind of block this is.
  22         Kind BlockKind
  23
  24         // Likely direction for branches.
  25         // If BranchLikely, Succs[0] is the most likely branch taken.
  26         // If BranchUnlikely, Succs[1] is the most likely branch taken.
  27         // Ignored if len(Succs) < 2.
  28         // Fatal if not BranchUnknown and len(Succs) > 2.
  29         Likely BranchPrediction
  30
  31         // After flagalloc, records whether flags are live at the end of the block.
  32         FlagsLiveAtEnd bool
  33
  34         // Subsequent blocks, if any. The number and order depend on the block kind.
  35         Succs []Edge
  36
  37         // Inverse of successors.
  38         // The order is significant to Phi nodes in the block.
  39         // TODO: predecessors is a pain to maintain. Can we somehow order phi
  40         // arguments by block id and have this field computed explicitly when needed?
  41         Preds []Edge
  42
  43         // A list of values that determine how the block is exited. The number
  44         // and type of control values depends on the Kind of the block. For
  45         // instance, a BlockIf has a single boolean control value and BlockExit
  46         // has a single memory control value.
  47         //
  48         // The ControlValues() method may be used to get a slice with the non-nil
  49         // control values that can be ranged over.
  50         //
  51         // Controls[1] must be nil if Controls[0] is nil.
  52         Controls [2]*Value
  53
  54         // Auxiliary info for the block. Its value depends on the Kind.
  55         Aux    Aux
  56         AuxInt int64
  57
  58         // The unordered set of Values that define the operation of this block.
  59         // After the scheduling pass, this list is ordered.
  60         Values []*Value
  61
  62         // The containing function
  63         Func *Func
  64
  65         // Storage for Succs, Preds and Values.
  66         succstorage [2]Edge
  67         predstorage [4]Edge
  68         valstorage  [9]*Value
  69 }
  70
  71 // Edge represents a CFG edge.
  72 // Example edges for b branching to either c or d.
  73 // (c and d have other predecessors.)
  74 //
  75 //      b.Succs = [{c,3}, {d,1}]
  76 //      c.Preds = [?, ?, ?, {b,0}]
  77 //      d.Preds = [?, {b,1}, ?]
  78 //
  79 // These indexes allow us to edit the CFG in constant time.
  80 // In addition, it informs phi ops in degenerate cases like:
  81 //
  82 //      b:
  83 //         if k then c else c
  84 //      c:
  85 //         v = Phi(x, y)
  86 //
  87 // Then the indexes tell you whether x is chosen from
  88 // the if or else branch from b.
  89 //
  90 //      b.Succs = [{c,0},{c,1}]
  91 //      c.Preds = [{b,0},{b,1}]
  92 //
  93 // means x is chosen if k is true.
  94 type Edge struct {
  95         // block edge goes to (in a Succs list) or from (in a Preds list)
  96         b *Block
  97         // index of reverse edge.  Invariant:
  98         //   e := x.Succs[idx]
  99         //   e.b.Preds[e.i] = Edge{x,idx}
 100         // and similarly for predecessors.
 101         i int
 102 }
 103
 104 func (e Edge) Block() *Block {
 105         return e.b
 106 }
 107 func (e Edge) Index() int {
 108         return e.i
 109 }
 110 func (e Edge) String() string {
 111         return fmt.Sprintf("{%v,%d}", e.b, e.i)
 112 }
 113
 114 // BlockKind is the kind of SSA block.
 115 type BlockKind int16
 116
 117 // short form print
 118 func (b *Block) String() string {
 119         return fmt.Sprintf("b%d", b.ID)
 120 }
 121
 122 // long form print
 123 func (b *Block) LongString() string {
 124         s := b.Kind.String()
 125         if b.Aux != nil {
 126                 s += fmt.Sprintf(" {%s}", b.Aux)
 127         }
 128         if t := b.AuxIntString(); t != "" {
 129                 s += fmt.Sprintf(" [%s]", t)
 130         }
 131         for _, c := range b.ControlValues() {
 132                 s += fmt.Sprintf(" %s", c)
 133         }
 134         if len(b.Succs) > 0 {
 135                 s += " ->"
 136                 for _, c := range b.Succs {
 137                         s += " " + c.b.String()
 138                 }
 139         }
 140         switch b.Likely {
 141         case BranchUnlikely:
 142                 s += " (unlikely)"
 143         case BranchLikely:
 144                 s += " (likely)"
 145         }
 146         return s
 147 }
 148
 149 // NumControls returns the number of non-nil control values the
 150 // block has.
 151 func (b *Block) NumControls() int {
 152         if b.Controls[0] == nil {
 153                 return 0
 154         }
 155         if b.Controls[1] == nil {
 156                 return 1
 157         }
 158         return 2
 159 }
 160
 161 // ControlValues returns a slice containing the non-nil control
 162 // values of the block. The index of each control value will be
 163 // the same as it is in the Controls property and can be used
 164 // in ReplaceControl calls.
 165 func (b *Block) ControlValues() []*Value {
 166         if b.Controls[0] == nil {
 167                 return b.Controls[:0]
 168         }
 169         if b.Controls[1] == nil {
 170                 return b.Controls[:1]
 171         }
 172         return b.Controls[:2]
 173 }
 174
 175 // SetControl removes all existing control values and then adds
 176 // the control value provided. The number of control values after
 177 // a call to SetControl will always be 1.
 178 func (b *Block) SetControl(v *Value) {
 179         b.ResetControls()
 180         b.Controls[0] = v
 181         v.Uses++
 182 }
 183
 184 // ResetControls sets the number of controls for the block to 0.
 185 func (b *Block) ResetControls() {
 186         if b.Controls[0] != nil {
 187                 b.Controls[0].Uses--
 188         }
 189         if b.Controls[1] != nil {
 190                 b.Controls[1].Uses--
 191         }
 192         b.Controls = [2]*Value{} // reset both controls to nil
 193 }
 194
 195 // AddControl appends a control value to the existing list of control values.
 196 func (b *Block) AddControl(v *Value) {
 197         i := b.NumControls()
 198         b.Controls[i] = v // panics if array is full
 199         v.Uses++
 200 }
 201
 202 // ReplaceControl exchanges the existing control value at the index provided
 203 // for the new value. The index must refer to a valid control value.
 204 func (b *Block) ReplaceControl(i int, v *Value) {
 205         b.Controls[i].Uses--
 206         b.Controls[i] = v
 207         v.Uses++
 208 }
 209
 210 // CopyControls replaces the controls for this block with those from the
 211 // provided block. The provided block is not modified.
 212 func (b *Block) CopyControls(from *Block) {
 213         if b == from {
 214                 return
 215         }
 216         b.ResetControls()
 217         for _, c := range from.ControlValues() {
 218                 b.AddControl(c)
 219         }
 220 }
 221
 222 // Reset sets the block to the provided kind and clears all the blocks control
 223 // and auxiliary values. Other properties of the block, such as its successors,
 224 // predecessors and values are left unmodified.
 225 func (b *Block) Reset(kind BlockKind) {
 226         b.Kind = kind
 227         b.ResetControls()
 228         b.Aux = nil
 229         b.AuxInt = 0
 230 }
 231
 232 // resetWithControl resets b and adds control v.
 233 // It is equivalent to b.Reset(kind); b.AddControl(v),
 234 // except that it is one call instead of two and avoids a bounds check.
 235 // It is intended for use by rewrite rules, where this matters.
 236 func (b *Block) resetWithControl(kind BlockKind, v *Value) {
 237         b.Kind = kind
 238         b.ResetControls()
 239         b.Aux = nil
 240         b.AuxInt = 0
 241         b.Controls[0] = v
 242         v.Uses++
 243 }
 244
 245 // resetWithControl2 resets b and adds controls v and w.
 246 // It is equivalent to b.Reset(kind); b.AddControl(v); b.AddControl(w),
 247 // except that it is one call instead of three and avoids two bounds checks.
 248 // It is intended for use by rewrite rules, where this matters.
 249 func (b *Block) resetWithControl2(kind BlockKind, v, w *Value) {
 250         b.Kind = kind
 251         b.ResetControls()
 252         b.Aux = nil
 253         b.AuxInt = 0
 254         b.Controls[0] = v
 255         b.Controls[1] = w
 256         v.Uses++
 257         w.Uses++
 258 }
 259
 260 // truncateValues truncates b.Values at the ith element, zeroing subsequent elements.
 261 // The values in b.Values after i must already have had their args reset,
 262 // to maintain correct value uses counts.
 263 func (b *Block) truncateValues(i int) {
 264         tail := b.Values[i:]
 265         for j := range tail {
 266                 tail[j] = nil
 267         }
 268         b.Values = b.Values[:i]
 269 }
 270
 271 // AddEdgeTo adds an edge from block b to block c.
 272 func (b *Block) AddEdgeTo(c *Block) {
 273         i := len(b.Succs)
 274         j := len(c.Preds)
 275         b.Succs = append(b.Succs, Edge{c, j})
 276         c.Preds = append(c.Preds, Edge{b, i})
 277         b.Func.invalidateCFG()
 278 }
 279
 280 // removePred removes the ith input edge from b.
 281 // It is the responsibility of the caller to remove
 282 // the corresponding successor edge, and adjust any
 283 // phi values by calling b.removePhiArg(v, i).
 284 func (b *Block) removePred(i int) {
 285         n := len(b.Preds) - 1
 286         if i != n {
 287                 e := b.Preds[n]
 288                 b.Preds[i] = e
 289                 // Update the other end of the edge we moved.
 290                 e.b.Succs[e.i].i = i
 291         }
 292         b.Preds[n] = Edge{}
 293         b.Preds = b.Preds[:n]
 294         b.Func.invalidateCFG()
 295 }
 296
 297 // removeSucc removes the ith output edge from b.
 298 // It is the responsibility of the caller to remove
 299 // the corresponding predecessor edge.
 300 func (b *Block) removeSucc(i int) {
 301         n := len(b.Succs) - 1
 302         if i != n {
 303                 e := b.Succs[n]
 304                 b.Succs[i] = e
 305                 // Update the other end of the edge we moved.
 306                 e.b.Preds[e.i].i = i
 307         }
 308         b.Succs[n] = Edge{}
 309         b.Succs = b.Succs[:n]
 310         b.Func.invalidateCFG()
 311 }
 312
 313 func (b *Block) swapSuccessors() {
 314         if len(b.Succs) != 2 {
 315                 b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs))
 316         }
 317         e0 := b.Succs[0]
 318         e1 := b.Succs[1]
 319         b.Succs[0] = e1
 320         b.Succs[1] = e0
 321         e0.b.Preds[e0.i].i = 1
 322         e1.b.Preds[e1.i].i = 0
 323         b.Likely *= -1
 324 }
 325
 326 // removePhiArg removes the ith arg from phi.
 327 // It must be called after calling b.removePred(i) to
 328 // adjust the corresponding phi value of the block:
 329 //
 330 // b.removePred(i)
 331 // for _, v := range b.Values {
 332 //
 333 //      if v.Op != OpPhi {
 334 //          continue
 335 //      }
 336 //      b.removePhiArg(v, i)
 337 //
 338 // }
 339 func (b *Block) removePhiArg(phi *Value, i int) {
 340         n := len(b.Preds)
 341         if numPhiArgs := len(phi.Args); numPhiArgs-1 != n {
 342                 b.Fatalf("inconsistent state, num predecessors: %d, num phi args: %d", n, numPhiArgs)
 343         }
 344         phi.Args[i].Uses--
 345         phi.Args[i] = phi.Args[n]
 346         phi.Args[n] = nil
 347         phi.Args = phi.Args[:n]
 348         phielimValue(phi)
 349 }
 350
 351 // LackingPos indicates whether b is a block whose position should be inherited
 352 // from its successors.  This is true if all the values within it have unreliable positions
 353 // and if it is "plain", meaning that there is no control flow that is also very likely
 354 // to correspond to a well-understood source position.
 355 func (b *Block) LackingPos() bool {
 356         // Non-plain predecessors are If or Defer, which both (1) have two successors,
 357         // which might have different line numbers and (2) correspond to statements
 358         // in the source code that have positions, so this case ought not occur anyway.
 359         if b.Kind != BlockPlain {
 360                 return false
 361         }
 362         if b.Pos != src.NoXPos {
 363                 return false
 364         }
 365         for _, v := range b.Values {
 366                 if v.LackingPos() {
 367                         continue
 368                 }
 369                 return false
 370         }
 371         return true
 372 }
 373
 374 func (b *Block) AuxIntString() string {
 375         switch b.Kind.AuxIntType() {
 376         case "int8":
 377                 return fmt.Sprintf("%v", int8(b.AuxInt))
 378         case "uint8":
 379                 return fmt.Sprintf("%v", uint8(b.AuxInt))
 380         case "": // no aux int type
 381                 return ""
 382         default: // type specified but not implemented - print as int64
 383                 return fmt.Sprintf("%v", b.AuxInt)
 384         }
 385 }
 386
 387 // likelyBranch reports whether block b is the likely branch of all of its predecessors.
 388 func (b *Block) likelyBranch() bool {
 389         if len(b.Preds) == 0 {
 390                 return false
 391         }
 392         for _, e := range b.Preds {
 393                 p := e.b
 394                 if len(p.Succs) == 1 || len(p.Succs) == 2 && (p.Likely == BranchLikely && p.Succs[0].b == b ||
 395                         p.Likely == BranchUnlikely && p.Succs[1].b == b) {
 396                         continue
 397                 }
 398                 return false
 399         }
 400         return true
 401 }
 402
 403 func (b *Block) Logf(msg string, args ...interface{})   { b.Func.Logf(msg, args...) }
 404 func (b *Block) Log() bool                              { return b.Func.Log() }
 405 func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) }
 406
 407 type BranchPrediction int8
 408
 409 const (
 410         BranchUnlikely = BranchPrediction(-1)
 411         BranchUnknown  = BranchPrediction(0)
 412         BranchLikely   = BranchPrediction(+1)
 413 )