.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/ssa/blockopt.go

   1 // Copyright 2013 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 // Simple block optimizations to simplify the control flow graph.
   8
   9 // TODO(adonovan): opt: instead of creating several "unreachable" blocks
  10 // per function in the Builder, reuse a single one (e.g. at Blocks[1])
  11 // to reduce garbage.
  12
  13 import (
  14         "fmt"
  15         "os"
  16 )
  17
  18 // If true, perform sanity checking and show progress at each
  19 // successive iteration of optimizeBlocks.  Very verbose.
  20 const debugBlockOpt = false
  21
  22 // markReachable sets Index=-1 for all blocks reachable from b.
  23 func markReachable(b *BasicBlock) {
  24         b.Index = -1
  25         for _, succ := range b.Succs {
  26                 if succ.Index == 0 {
  27                         markReachable(succ)
  28                 }
  29         }
  30 }
  31
  32 // deleteUnreachableBlocks marks all reachable blocks of f and
  33 // eliminates (nils) all others, including possibly cyclic subgraphs.
  34 //
  35 func deleteUnreachableBlocks(f *Function) {
  36         const white, black = 0, -1
  37         // We borrow b.Index temporarily as the mark bit.
  38         for _, b := range f.Blocks {
  39                 b.Index = white
  40         }
  41         markReachable(f.Blocks[0])
  42         if f.Recover != nil {
  43                 markReachable(f.Recover)
  44         }
  45         for i, b := range f.Blocks {
  46                 if b.Index == white {
  47                         for _, c := range b.Succs {
  48                                 if c.Index == black {
  49                                         c.removePred(b) // delete white->black edge
  50                                 }
  51                         }
  52                         if debugBlockOpt {
  53                                 fmt.Fprintln(os.Stderr, "unreachable", b)
  54                         }
  55                         f.Blocks[i] = nil // delete b
  56                 }
  57         }
  58         f.removeNilBlocks()
  59 }
  60
  61 // jumpThreading attempts to apply simple jump-threading to block b,
  62 // in which a->b->c become a->c if b is just a Jump.
  63 // The result is true if the optimization was applied.
  64 //
  65 func jumpThreading(f *Function, b *BasicBlock) bool {
  66         if b.Index == 0 {
  67                 return false // don't apply to entry block
  68         }
  69         if b.Instrs == nil {
  70                 return false
  71         }
  72         if _, ok := b.Instrs[0].(*Jump); !ok {
  73                 return false // not just a jump
  74         }
  75         c := b.Succs[0]
  76         if c == b {
  77                 return false // don't apply to degenerate jump-to-self.
  78         }
  79         if c.hasPhi() {
  80                 return false // not sound without more effort
  81         }
  82         for j, a := range b.Preds {
  83                 a.replaceSucc(b, c)
  84
  85                 // If a now has two edges to c, replace its degenerate If by Jump.
  86                 if len(a.Succs) == 2 && a.Succs[0] == c && a.Succs[1] == c {
  87                         jump := new(Jump)
  88                         jump.setBlock(a)
  89                         a.Instrs[len(a.Instrs)-1] = jump
  90                         a.Succs = a.Succs[:1]
  91                         c.removePred(b)
  92                 } else {
  93                         if j == 0 {
  94                                 c.replacePred(b, a)
  95                         } else {
  96                                 c.Preds = append(c.Preds, a)
  97                         }
  98                 }
  99
 100                 if debugBlockOpt {
 101                         fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c)
 102                 }
 103         }
 104         f.Blocks[b.Index] = nil // delete b
 105         return true
 106 }
 107
 108 // fuseBlocks attempts to apply the block fusion optimization to block
 109 // a, in which a->b becomes ab if len(a.Succs)==len(b.Preds)==1.
 110 // The result is true if the optimization was applied.
 111 //
 112 func fuseBlocks(f *Function, a *BasicBlock) bool {
 113         if len(a.Succs) != 1 {
 114                 return false
 115         }
 116         b := a.Succs[0]
 117         if len(b.Preds) != 1 {
 118                 return false
 119         }
 120
 121         // Degenerate &&/|| ops may result in a straight-line CFG
 122         // containing φ-nodes. (Ideally we'd replace such them with
 123         // their sole operand but that requires Referrers, built later.)
 124         if b.hasPhi() {
 125                 return false // not sound without further effort
 126         }
 127
 128         // Eliminate jump at end of A, then copy all of B across.
 129         a.Instrs = append(a.Instrs[:len(a.Instrs)-1], b.Instrs...)
 130         for _, instr := range b.Instrs {
 131                 instr.setBlock(a)
 132         }
 133
 134         // A inherits B's successors
 135         a.Succs = append(a.succs2[:0], b.Succs...)
 136
 137         // Fix up Preds links of all successors of B.
 138         for _, c := range b.Succs {
 139                 c.replacePred(b, a)
 140         }
 141
 142         if debugBlockOpt {
 143                 fmt.Fprintln(os.Stderr, "fuseBlocks", a, b)
 144         }
 145
 146         f.Blocks[b.Index] = nil // delete b
 147         return true
 148 }
 149
 150 // optimizeBlocks() performs some simple block optimizations on a
 151 // completed function: dead block elimination, block fusion, jump
 152 // threading.
 153 //
 154 func optimizeBlocks(f *Function) {
 155         deleteUnreachableBlocks(f)
 156
 157         // Loop until no further progress.
 158         changed := true
 159         for changed {
 160                 changed = false
 161
 162                 if debugBlockOpt {
 163                         f.WriteTo(os.Stderr)
 164                         mustSanityCheck(f, nil)
 165                 }
 166
 167                 for _, b := range f.Blocks {
 168                         // f.Blocks will temporarily contain nils to indicate
 169                         // deleted blocks; we remove them at the end.
 170                         if b == nil {
 171                                 continue
 172                         }
 173
 174                         // Fuse blocks.  b->c becomes bc.
 175                         if fuseBlocks(f, b) {
 176                                 changed = true
 177                         }
 178
 179                         // a->b->c becomes a->c if b contains only a Jump.
 180                         if jumpThreading(f, b) {
 181                                 changed = true
 182                                 continue // (b was disconnected)
 183                         }
 184                 }
 185         }
 186         f.removeNilBlocks()
 187 }