fuse_branchredirect.go

     1  // Copyright 2021 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  // fuseBranchRedirect checks for a CFG in which the outbound branch
     8  // of an If block can be derived from its predecessor If block, in
     9  // some such cases, we can redirect the predecessor If block to the
    10  // corresponding successor block directly. For example:
    11  // p:
    12  //   v11 = Less64 <bool> v10 v8
    13  //   If v11 goto b else u
    14  // b: <- p ...
    15  //   v17 = Leq64 <bool> v10 v8
    16  //   If v17 goto s else o
    17  // We can redirect p to s directly.
    18  //
    19  // The implementation here borrows the framework of the prove pass.
    20  // 1, Traverse all blocks of function f to find If blocks.
    21  // 2,   For any If block b, traverse all its predecessors to find If blocks.
    22  // 3,     For any If block predecessor p, update relationship p->b.
    23  // 4,     Traverse all successors of b.
    24  // 5,       For any successor s of b, try to update relationship b->s, if a
    25  //          contradiction is found then redirect p to another successor of b.
    26  func fuseBranchRedirect(f *Func) bool {
    27  	ft := newFactsTable(f)
    28  	ft.checkpoint()
    29  
    30  	changed := false
    31  	for i := len(f.Blocks) - 1; i >= 0; i-- {
    32  		b := f.Blocks[i]
    33  		if b.Kind != BlockIf {
    34  			continue
    35  		}
    36  		// b is either empty or only contains the control value.
    37  		// TODO: if b contains only OpCopy or OpNot related to b.Controls,
    38  		// such as Copy(Not(Copy(Less64(v1, v2)))), perhaps it can be optimized.
    39  		bCtl := b.Controls[0]
    40  		if bCtl.Block != b && len(b.Values) != 0 || (len(b.Values) != 1 || bCtl.Uses != 1) && bCtl.Block == b {
    41  			continue
    42  		}
    43  
    44  		for k := 0; k < len(b.Preds); k++ {
    45  			pk := b.Preds[k]
    46  			p := pk.b
    47  			if p.Kind != BlockIf || p == b {
    48  				continue
    49  			}
    50  			pbranch := positive
    51  			if pk.i == 1 {
    52  				pbranch = negative
    53  			}
    54  			ft.checkpoint()
    55  			// Assume branch p->b is taken.
    56  			addBranchRestrictions(ft, p, pbranch)
    57  			// Check if any outgoing branch is unreachable based on the above condition.
    58  			parent := b
    59  			for j, bbranch := range [...]branch{positive, negative} {
    60  				ft.checkpoint()
    61  				// Try to update relationship b->child, and check if the contradiction occurs.
    62  				addBranchRestrictions(ft, parent, bbranch)
    63  				unsat := ft.unsat
    64  				ft.restore()
    65  				if !unsat {
    66  					continue
    67  				}
    68  				// This branch is impossible,so redirect p directly to another branch.
    69  				out := 1 ^ j
    70  				child := parent.Succs[out].b
    71  				if child == b {
    72  					continue
    73  				}
    74  				b.removePred(k)
    75  				p.Succs[pk.i] = Edge{child, len(child.Preds)}
    76  				// Fix up Phi value in b to have one less argument.
    77  				for _, v := range b.Values {
    78  					if v.Op != OpPhi {
    79  						continue
    80  					}
    81  					b.removePhiArg(v, k)
    82  					phielimValue(v)
    83  				}
    84  				// Fix up child to have one more predecessor.
    85  				child.Preds = append(child.Preds, Edge{p, pk.i})
    86  				ai := b.Succs[out].i
    87  				for _, v := range child.Values {
    88  					if v.Op != OpPhi {
    89  						continue
    90  					}
    91  					v.AddArg(v.Args[ai])
    92  				}
    93  				if b.Func.pass.debug > 0 {
    94  					b.Func.Warnl(b.Controls[0].Pos, "Redirect %s based on %s", b.Controls[0].Op, p.Controls[0].Op)
    95  				}
    96  				changed = true
    97  				k--
    98  				break
    99  			}
   100  			ft.restore()
   101  		}
   102  		if len(b.Preds) == 0 && b != f.Entry {
   103  			// Block is now dead.
   104  			b.Kind = BlockInvalid
   105  		}
   106  	}
   107  	ft.restore()
   108  	ft.cleanup(f)
   109  	return changed
   110  }
   111
View as plain text