.config/coc/extensions/coc-go-data/tools/pkg/mod/honnef.co/go/tools@v0.0.1-2020.1.5/ir/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 ir
   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.gaps = -1
  25         for _, succ := range b.Succs {
  26                 if succ.gaps == 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.gaps temporarily as the mark bit.
  38         for _, b := range f.Blocks {
  39                 b.gaps = white
  40         }
  41         markReachable(f.Blocks[0])
  42         // In SSI form, we need the exit to be reachable for correct
  43         // post-dominance information. In original form, however, we
  44         // cannot unconditionally mark it reachable because we won't
  45         // be adding fake edges, and this breaks the calculation of
  46         // dominance information.
  47         markReachable(f.Exit)
  48         for i, b := range f.Blocks {
  49                 if b.gaps == white {
  50                         for _, c := range b.Succs {
  51                                 if c.gaps == black {
  52                                         c.removePred(b) // delete white->black edge
  53                                 }
  54                         }
  55                         if debugBlockOpt {
  56                                 fmt.Fprintln(os.Stderr, "unreachable", b)
  57                         }
  58                         f.Blocks[i] = nil // delete b
  59                 }
  60         }
  61         f.removeNilBlocks()
  62 }
  63
  64 // jumpThreading attempts to apply simple jump-threading to block b,
  65 // in which a->b->c become a->c if b is just a Jump.
  66 // The result is true if the optimization was applied.
  67 //
  68 func jumpThreading(f *Function, b *BasicBlock) bool {
  69         if b.Index == 0 {
  70                 return false // don't apply to entry block
  71         }
  72         if b.Instrs == nil {
  73                 return false
  74         }
  75         for _, pred := range b.Preds {
  76                 switch pred.Control().(type) {
  77                 case *ConstantSwitch:
  78                         // don't optimize away the head blocks of switch statements
  79                         return false
  80                 }
  81         }
  82         if _, ok := b.Instrs[0].(*Jump); !ok {
  83                 return false // not just a jump
  84         }
  85         c := b.Succs[0]
  86         if c == b {
  87                 return false // don't apply to degenerate jump-to-self.
  88         }
  89         if c.hasPhi() {
  90                 return false // not sound without more effort
  91         }
  92         for j, a := range b.Preds {
  93                 a.replaceSucc(b, c)
  94
  95                 // If a now has two edges to c, replace its degenerate If by Jump.
  96                 if len(a.Succs) == 2 && a.Succs[0] == c && a.Succs[1] == c {
  97                         jump := new(Jump)
  98                         jump.setBlock(a)
  99                         a.Instrs[len(a.Instrs)-1] = jump
 100                         a.Succs = a.Succs[:1]
 101                         c.removePred(b)
 102                 } else {
 103                         if j == 0 {
 104                                 c.replacePred(b, a)
 105                         } else {
 106                                 c.Preds = append(c.Preds, a)
 107                         }
 108                 }
 109
 110                 if debugBlockOpt {
 111                         fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c)
 112                 }
 113         }
 114         f.Blocks[b.Index] = nil // delete b
 115         return true
 116 }
 117
 118 // fuseBlocks attempts to apply the block fusion optimization to block
 119 // a, in which a->b becomes ab if len(a.Succs)==len(b.Preds)==1.
 120 // The result is true if the optimization was applied.
 121 //
 122 func fuseBlocks(f *Function, a *BasicBlock) bool {
 123         if len(a.Succs) != 1 {
 124                 return false
 125         }
 126         if a.Succs[0] == f.Exit {
 127                 return false
 128         }
 129         b := a.Succs[0]
 130         if len(b.Preds) != 1 {
 131                 return false
 132         }
 133         if _, ok := a.Instrs[len(a.Instrs)-1].(*Panic); ok {
 134                 // panics aren't simple jumps, they have side effects.
 135                 return false
 136         }
 137
 138         // Degenerate &&/|| ops may result in a straight-line CFG
 139         // containing φ-nodes. (Ideally we'd replace such them with
 140         // their sole operand but that requires Referrers, built later.)
 141         if b.hasPhi() {
 142                 return false // not sound without further effort
 143         }
 144
 145         // Eliminate jump at end of A, then copy all of B across.
 146         a.Instrs = append(a.Instrs[:len(a.Instrs)-1], b.Instrs...)
 147         for _, instr := range b.Instrs {
 148                 instr.setBlock(a)
 149         }
 150
 151         // A inherits B's successors
 152         a.Succs = append(a.succs2[:0], b.Succs...)
 153
 154         // Fix up Preds links of all successors of B.
 155         for _, c := range b.Succs {
 156                 c.replacePred(b, a)
 157         }
 158
 159         if debugBlockOpt {
 160                 fmt.Fprintln(os.Stderr, "fuseBlocks", a, b)
 161         }
 162
 163         f.Blocks[b.Index] = nil // delete b
 164         return true
 165 }
 166
 167 // optimizeBlocks() performs some simple block optimizations on a
 168 // completed function: dead block elimination, block fusion, jump
 169 // threading.
 170 //
 171 func optimizeBlocks(f *Function) {
 172         if debugBlockOpt {
 173                 f.WriteTo(os.Stderr)
 174                 mustSanityCheck(f, nil)
 175         }
 176
 177         deleteUnreachableBlocks(f)
 178
 179         // Loop until no further progress.
 180         changed := true
 181         for changed {
 182                 changed = false
 183
 184                 if debugBlockOpt {
 185                         f.WriteTo(os.Stderr)
 186                         mustSanityCheck(f, nil)
 187                 }
 188
 189                 for _, b := range f.Blocks {
 190                         // f.Blocks will temporarily contain nils to indicate
 191                         // deleted blocks; we remove them at the end.
 192                         if b == nil {
 193                                 continue
 194                         }
 195
 196                         // Fuse blocks.  b->c becomes bc.
 197                         if fuseBlocks(f, b) {
 198                                 changed = true
 199                         }
 200
 201                         // a->b->c becomes a->c if b contains only a Jump.
 202                         if jumpThreading(f, b) {
 203                                 changed = true
 204                                 continue // (b was disconnected)
 205                         }
 206                 }
 207         }
 208         f.removeNilBlocks()
 209 }