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