Black Lives Matter. Support the Equal Justice Initiative.

Source file src/cmd/compile/internal/ssa/shortcircuit.go

Documentation: cmd/compile/internal/ssa

     1  // Copyright 2016 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  // Shortcircuit finds situations where branch directions
     8  // are always correlated and rewrites the CFG to take
     9  // advantage of that fact.
    10  // This optimization is useful for compiling && and || expressions.
    11  func shortcircuit(f *Func) {
    12  	// Step 1: Replace a phi arg with a constant if that arg
    13  	// is the control value of a preceding If block.
    14  	// b1:
    15  	//    If a goto b2 else b3
    16  	// b2: <- b1 ...
    17  	//    x = phi(a, ...)
    18  	//
    19  	// We can replace the "a" in the phi with the constant true.
    20  	var ct, cf *Value
    21  	for _, b := range f.Blocks {
    22  		for _, v := range b.Values {
    23  			if v.Op != OpPhi {
    24  				continue
    25  			}
    26  			if !v.Type.IsBoolean() {
    27  				continue
    28  			}
    29  			for i, a := range v.Args {
    30  				e := b.Preds[i]
    31  				p := e.b
    32  				if p.Kind != BlockIf {
    33  					continue
    34  				}
    35  				if p.Controls[0] != a {
    36  					continue
    37  				}
    38  				if e.i == 0 {
    39  					if ct == nil {
    40  						ct = f.ConstBool(f.Config.Types.Bool, true)
    41  					}
    42  					v.SetArg(i, ct)
    43  				} else {
    44  					if cf == nil {
    45  						cf = f.ConstBool(f.Config.Types.Bool, false)
    46  					}
    47  					v.SetArg(i, cf)
    48  				}
    49  			}
    50  		}
    51  	}
    52  
    53  	// Step 2: Redirect control flow around known branches.
    54  	// p:
    55  	//   ... goto b ...
    56  	// b: <- p ...
    57  	//   v = phi(true, ...)
    58  	//   if v goto t else u
    59  	// We can redirect p to go directly to t instead of b.
    60  	// (If v is not live after b).
    61  	fuse(f, fuseTypePlain|fuseTypeShortCircuit)
    62  }
    63  
    64  // shortcircuitBlock checks for a CFG in which an If block
    65  // has as its control value a Phi that has a ConstBool arg.
    66  // In some such cases, we can rewrite the CFG into a flatter form.
    67  //
    68  // (1) Look for a CFG of the form
    69  //
    70  //   p   other pred(s)
    71  //    \ /
    72  //     b
    73  //    / \
    74  //   t   other succ
    75  //
    76  // in which b is an If block containing a single phi value with a single use (b's Control),
    77  // which has a ConstBool arg.
    78  // p is the predecessor corresponding to the argument slot in which the ConstBool is found.
    79  // t is the successor corresponding to the value of the ConstBool arg.
    80  //
    81  // Rewrite this into
    82  //
    83  //   p   other pred(s)
    84  //   |  /
    85  //   | b
    86  //   |/ \
    87  //   t   u
    88  //
    89  // and remove the appropriate phi arg(s).
    90  //
    91  // (2) Look for a CFG of the form
    92  //
    93  //   p   q
    94  //    \ /
    95  //     b
    96  //    / \
    97  //   t   u
    98  //
    99  // in which b is as described in (1).
   100  // However, b may also contain other phi values.
   101  // The CFG will be modified as described in (1).
   102  // However, in order to handle those other phi values,
   103  // for each other phi value w, we must be able to eliminate w from b.
   104  // We can do that though a combination of moving w to a different block
   105  // and rewriting uses of w to use a different value instead.
   106  // See shortcircuitPhiPlan for details.
   107  func shortcircuitBlock(b *Block) bool {
   108  	if b.Kind != BlockIf {
   109  		return false
   110  	}
   111  	// Look for control values of the form Copy(Not(Copy(Phi(const, ...)))).
   112  	// Those must be the only values in the b, and they each must be used only by b.
   113  	// Track the negations so that we can swap successors as needed later.
   114  	ctl := b.Controls[0]
   115  	nval := 1 // the control value
   116  	var swap int64
   117  	for ctl.Uses == 1 && ctl.Block == b && (ctl.Op == OpCopy || ctl.Op == OpNot) {
   118  		if ctl.Op == OpNot {
   119  			swap = 1 ^ swap
   120  		}
   121  		ctl = ctl.Args[0]
   122  		nval++ // wrapper around control value
   123  	}
   124  	if ctl.Op != OpPhi || ctl.Block != b || ctl.Uses != 1 {
   125  		return false
   126  	}
   127  	nOtherPhi := 0
   128  	for _, w := range b.Values {
   129  		if w.Op == OpPhi && w != ctl {
   130  			nOtherPhi++
   131  		}
   132  	}
   133  	if nOtherPhi > 0 && len(b.Preds) != 2 {
   134  		// We rely on b having exactly two preds in shortcircuitPhiPlan
   135  		// to reason about the values of phis.
   136  		return false
   137  	}
   138  	if len(b.Values) != nval+nOtherPhi {
   139  		return false
   140  	}
   141  	if nOtherPhi > 0 {
   142  		// Check for any phi which is the argument of another phi.
   143  		// These cases are tricky, as substitutions done by replaceUses
   144  		// are no longer trivial to do in any ordering. See issue 45175.
   145  		m := make(map[*Value]bool, 1+nOtherPhi)
   146  		for _, v := range b.Values {
   147  			if v.Op == OpPhi {
   148  				m[v] = true
   149  			}
   150  		}
   151  		for v := range m {
   152  			for _, a := range v.Args {
   153  				if a != v && m[a] {
   154  					return false
   155  				}
   156  			}
   157  		}
   158  	}
   159  
   160  	// Locate index of first const phi arg.
   161  	cidx := -1
   162  	for i, a := range ctl.Args {
   163  		if a.Op == OpConstBool {
   164  			cidx = i
   165  			break
   166  		}
   167  	}
   168  	if cidx == -1 {
   169  		return false
   170  	}
   171  
   172  	// p is the predecessor corresponding to cidx.
   173  	pe := b.Preds[cidx]
   174  	p := pe.b
   175  	pi := pe.i
   176  
   177  	// t is the "taken" branch: the successor we always go to when coming in from p.
   178  	ti := 1 ^ ctl.Args[cidx].AuxInt ^ swap
   179  	te := b.Succs[ti]
   180  	t := te.b
   181  	if p == b || t == b {
   182  		// This is an infinite loop; we can't remove it. See issue 33903.
   183  		return false
   184  	}
   185  
   186  	var fixPhi func(*Value, int)
   187  	if nOtherPhi > 0 {
   188  		fixPhi = shortcircuitPhiPlan(b, ctl, cidx, ti)
   189  		if fixPhi == nil {
   190  			return false
   191  		}
   192  	}
   193  
   194  	// We're committed. Update CFG and Phis.
   195  	// If you modify this section, update shortcircuitPhiPlan corresponding.
   196  
   197  	// Remove b's incoming edge from p.
   198  	b.removePred(cidx)
   199  	n := len(b.Preds)
   200  	ctl.Args[cidx].Uses--
   201  	ctl.Args[cidx] = ctl.Args[n]
   202  	ctl.Args[n] = nil
   203  	ctl.Args = ctl.Args[:n]
   204  
   205  	// Redirect p's outgoing edge to t.
   206  	p.Succs[pi] = Edge{t, len(t.Preds)}
   207  
   208  	// Fix up t to have one more predecessor.
   209  	t.Preds = append(t.Preds, Edge{p, pi})
   210  	for _, v := range t.Values {
   211  		if v.Op != OpPhi {
   212  			continue
   213  		}
   214  		v.AddArg(v.Args[te.i])
   215  	}
   216  
   217  	if nOtherPhi != 0 {
   218  		// Adjust all other phis as necessary.
   219  		// Use a plain for loop instead of range because fixPhi may move phis,
   220  		// thus modifying b.Values.
   221  		for i := 0; i < len(b.Values); i++ {
   222  			phi := b.Values[i]
   223  			if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi {
   224  				continue
   225  			}
   226  			fixPhi(phi, i)
   227  			if phi.Block == b {
   228  				continue
   229  			}
   230  			// phi got moved to a different block with v.moveTo.
   231  			// Adjust phi values in this new block that refer
   232  			// to phi to refer to the corresponding phi arg instead.
   233  			// phi used to be evaluated prior to this block,
   234  			// and now it is evaluated in this block.
   235  			for _, v := range phi.Block.Values {
   236  				if v.Op != OpPhi || v == phi {
   237  					continue
   238  				}
   239  				for j, a := range v.Args {
   240  					if a == phi {
   241  						v.SetArg(j, phi.Args[j])
   242  					}
   243  				}
   244  			}
   245  			if phi.Uses != 0 {
   246  				phielimValue(phi)
   247  			} else {
   248  				phi.reset(OpInvalid)
   249  			}
   250  			i-- // v.moveTo put a new value at index i; reprocess
   251  		}
   252  
   253  		// We may have left behind some phi values with no uses
   254  		// but the wrong number of arguments. Eliminate those.
   255  		for _, v := range b.Values {
   256  			if v.Uses == 0 {
   257  				v.reset(OpInvalid)
   258  			}
   259  		}
   260  	}
   261  
   262  	if len(b.Preds) == 0 {
   263  		// Block is now dead.
   264  		b.Kind = BlockInvalid
   265  	}
   266  
   267  	phielimValue(ctl)
   268  	return true
   269  }
   270  
   271  // shortcircuitPhiPlan returns a function to handle non-ctl phi values in b,
   272  // where b is as described in shortcircuitBlock.
   273  // The returned function accepts a value v
   274  // and the index i of v in v.Block: v.Block.Values[i] == v.
   275  // If the returned function moves v to a different block, it will use v.moveTo.
   276  // cidx is the index in ctl of the ConstBool arg.
   277  // ti is the index in b.Succs of the always taken branch when arriving from p.
   278  // If shortcircuitPhiPlan returns nil, there is no plan available,
   279  // and the CFG modifications must not proceed.
   280  // The returned function assumes that shortcircuitBlock has completed its CFG modifications.
   281  func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) {
   282  	// t is the "taken" branch: the successor we always go to when coming in from p.
   283  	t := b.Succs[ti].b
   284  	// u is the "untaken" branch: the successor we never go to when coming in from p.
   285  	u := b.Succs[1^ti].b
   286  
   287  	// Look for some common CFG structures
   288  	// in which the outbound paths from b merge,
   289  	// with no other preds joining them.
   290  	// In these cases, we can reconstruct what the value
   291  	// of any phi in b must be in the successor blocks.
   292  
   293  	if len(t.Preds) == 1 && len(t.Succs) == 1 &&
   294  		len(u.Preds) == 1 && len(u.Succs) == 1 &&
   295  		t.Succs[0].b == u.Succs[0].b && len(t.Succs[0].b.Preds) == 2 {
   296  		// p   q
   297  		//  \ /
   298  		//   b
   299  		//  / \
   300  		// t   u
   301  		//  \ /
   302  		//   m
   303  		//
   304  		// After the CFG modifications, this will look like
   305  		//
   306  		// p   q
   307  		// |  /
   308  		// | b
   309  		// |/ \
   310  		// t   u
   311  		//  \ /
   312  		//   m
   313  		//
   314  		// NB: t.Preds is (b, p), not (p, b).
   315  		m := t.Succs[0].b
   316  		return func(v *Value, i int) {
   317  			// Replace any uses of v in t and u with the value v must have,
   318  			// given that we have arrived at that block.
   319  			// Then move v to m and adjust its value accordingly;
   320  			// this handles all other uses of v.
   321  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   322  			u.replaceUses(v, argQ)
   323  			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
   324  			phi.AddArg2(argQ, argP)
   325  			t.replaceUses(v, phi)
   326  			if v.Uses == 0 {
   327  				return
   328  			}
   329  			v.moveTo(m, i)
   330  			// The phi in m belongs to whichever pred idx corresponds to t.
   331  			if m.Preds[0].b == t {
   332  				v.SetArgs2(phi, argQ)
   333  			} else {
   334  				v.SetArgs2(argQ, phi)
   335  			}
   336  		}
   337  	}
   338  
   339  	if len(t.Preds) == 2 && len(u.Preds) == 1 && len(u.Succs) == 1 && u.Succs[0].b == t {
   340  		// p   q
   341  		//  \ /
   342  		//   b
   343  		//   |\
   344  		//   | u
   345  		//   |/
   346  		//   t
   347  		//
   348  		// After the CFG modifications, this will look like
   349  		//
   350  		//     q
   351  		//    /
   352  		//   b
   353  		//   |\
   354  		// p | u
   355  		//  \|/
   356  		//   t
   357  		//
   358  		// NB: t.Preds is (b or u, b or u, p).
   359  		return func(v *Value, i int) {
   360  			// Replace any uses of v in u. Then move v to t.
   361  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   362  			u.replaceUses(v, argQ)
   363  			v.moveTo(t, i)
   364  			v.SetArgs3(argQ, argQ, argP)
   365  		}
   366  	}
   367  
   368  	if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u {
   369  		// p   q
   370  		//  \ /
   371  		//   b
   372  		//  /|
   373  		// t |
   374  		//  \|
   375  		//   u
   376  		//
   377  		// After the CFG modifications, this will look like
   378  		//
   379  		// p   q
   380  		// |  /
   381  		// | b
   382  		// |/|
   383  		// t |
   384  		//  \|
   385  		//   u
   386  		//
   387  		// NB: t.Preds is (b, p), not (p, b).
   388  		return func(v *Value, i int) {
   389  			// Replace any uses of v in t. Then move v to u.
   390  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   391  			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
   392  			phi.AddArg2(argQ, argP)
   393  			t.replaceUses(v, phi)
   394  			if v.Uses == 0 {
   395  				return
   396  			}
   397  			v.moveTo(u, i)
   398  			v.SetArgs2(argQ, phi)
   399  		}
   400  	}
   401  
   402  	// Look for some common CFG structures
   403  	// in which one outbound path from b exits,
   404  	// with no other preds joining.
   405  	// In these cases, we can reconstruct what the value
   406  	// of any phi in b must be in the path leading to exit,
   407  	// and move the phi to the non-exit path.
   408  
   409  	if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 {
   410  		// p   q
   411  		//  \ /
   412  		//   b
   413  		//  / \
   414  		// t   u
   415  		//
   416  		// where t is an Exit/Ret block.
   417  		//
   418  		// After the CFG modifications, this will look like
   419  		//
   420  		// p   q
   421  		// |  /
   422  		// | b
   423  		// |/ \
   424  		// t   u
   425  		//
   426  		// NB: t.Preds is (b, p), not (p, b).
   427  		return func(v *Value, i int) {
   428  			// Replace any uses of v in t and x. Then move v to u.
   429  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   430  			// If there are no uses of v in t or x, this phi will be unused.
   431  			// That's OK; it's not worth the cost to prevent that.
   432  			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
   433  			phi.AddArg2(argQ, argP)
   434  			t.replaceUses(v, phi)
   435  			if v.Uses == 0 {
   436  				return
   437  			}
   438  			v.moveTo(u, i)
   439  			v.SetArgs1(argQ)
   440  		}
   441  	}
   442  
   443  	if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 {
   444  		// p   q
   445  		//  \ /
   446  		//   b
   447  		//  / \
   448  		// t   u
   449  		//
   450  		// where u is an Exit/Ret block.
   451  		//
   452  		// After the CFG modifications, this will look like
   453  		//
   454  		// p   q
   455  		// |  /
   456  		// | b
   457  		// |/ \
   458  		// t   u
   459  		//
   460  		// NB: t.Preds is (b, p), not (p, b).
   461  		return func(v *Value, i int) {
   462  			// Replace any uses of v in u (and x). Then move v to t.
   463  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   464  			u.replaceUses(v, argQ)
   465  			v.moveTo(t, i)
   466  			v.SetArgs2(argQ, argP)
   467  		}
   468  	}
   469  
   470  	// TODO: handle more cases; shortcircuit optimizations turn out to be reasonably high impact
   471  	return nil
   472  }
   473  
   474  // replaceUses replaces all uses of old in b with new.
   475  func (b *Block) replaceUses(old, new *Value) {
   476  	for _, v := range b.Values {
   477  		for i, a := range v.Args {
   478  			if a == old {
   479  				v.SetArg(i, new)
   480  			}
   481  		}
   482  	}
   483  	for i, v := range b.ControlValues() {
   484  		if v == old {
   485  			b.ReplaceControl(i, new)
   486  		}
   487  	}
   488  }
   489  
   490  // moveTo moves v to dst, adjusting the appropriate Block.Values slices.
   491  // The caller is responsible for ensuring that this is safe.
   492  // i is the index of v in v.Block.Values.
   493  func (v *Value) moveTo(dst *Block, i int) {
   494  	if dst.Func.scheduled {
   495  		v.Fatalf("moveTo after scheduling")
   496  	}
   497  	src := v.Block
   498  	if src.Values[i] != v {
   499  		v.Fatalf("moveTo bad index %d", v, i)
   500  	}
   501  	if src == dst {
   502  		return
   503  	}
   504  	v.Block = dst
   505  	dst.Values = append(dst.Values, v)
   506  	last := len(src.Values) - 1
   507  	src.Values[i] = src.Values[last]
   508  	src.Values[last] = nil
   509  	src.Values = src.Values[:last]
   510  }
   511  

View as plain text