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