...

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  	b.removePhiArg(ctl, cidx)
   200  
   201  	// Redirect p's outgoing edge to t.
   202  	p.Succs[pi] = Edge{t, len(t.Preds)}
   203  
   204  	// Fix up t to have one more predecessor.
   205  	t.Preds = append(t.Preds, Edge{p, pi})
   206  	for _, v := range t.Values {
   207  		if v.Op != OpPhi {
   208  			continue
   209  		}
   210  		v.AddArg(v.Args[te.i])
   211  	}
   212  
   213  	if nOtherPhi != 0 {
   214  		// Adjust all other phis as necessary.
   215  		// Use a plain for loop instead of range because fixPhi may move phis,
   216  		// thus modifying b.Values.
   217  		for i := 0; i < len(b.Values); i++ {
   218  			phi := b.Values[i]
   219  			if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi {
   220  				continue
   221  			}
   222  			fixPhi(phi, i)
   223  			if phi.Block == b {
   224  				continue
   225  			}
   226  			// phi got moved to a different block with v.moveTo.
   227  			// Adjust phi values in this new block that refer
   228  			// to phi to refer to the corresponding phi arg instead.
   229  			// phi used to be evaluated prior to this block,
   230  			// and now it is evaluated in this block.
   231  			for _, v := range phi.Block.Values {
   232  				if v.Op != OpPhi || v == phi {
   233  					continue
   234  				}
   235  				for j, a := range v.Args {
   236  					if a == phi {
   237  						v.SetArg(j, phi.Args[j])
   238  					}
   239  				}
   240  			}
   241  			if phi.Uses != 0 {
   242  				phielimValue(phi)
   243  			} else {
   244  				phi.reset(OpInvalid)
   245  			}
   246  			i-- // v.moveTo put a new value at index i; reprocess
   247  		}
   248  
   249  		// We may have left behind some phi values with no uses
   250  		// but the wrong number of arguments. Eliminate those.
   251  		for _, v := range b.Values {
   252  			if v.Uses == 0 {
   253  				v.reset(OpInvalid)
   254  			}
   255  		}
   256  	}
   257  
   258  	if len(b.Preds) == 0 {
   259  		// Block is now dead.
   260  		b.Kind = BlockInvalid
   261  	}
   262  
   263  	phielimValue(ctl)
   264  	return true
   265  }
   266  
   267  // shortcircuitPhiPlan returns a function to handle non-ctl phi values in b,
   268  // where b is as described in shortcircuitBlock.
   269  // The returned function accepts a value v
   270  // and the index i of v in v.Block: v.Block.Values[i] == v.
   271  // If the returned function moves v to a different block, it will use v.moveTo.
   272  // cidx is the index in ctl of the ConstBool arg.
   273  // ti is the index in b.Succs of the always taken branch when arriving from p.
   274  // If shortcircuitPhiPlan returns nil, there is no plan available,
   275  // and the CFG modifications must not proceed.
   276  // The returned function assumes that shortcircuitBlock has completed its CFG modifications.
   277  func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) {
   278  	// t is the "taken" branch: the successor we always go to when coming in from p.
   279  	t := b.Succs[ti].b
   280  	// u is the "untaken" branch: the successor we never go to when coming in from p.
   281  	u := b.Succs[1^ti].b
   282  
   283  	// In the following CFG matching, ensure that b's preds are entirely distinct from b's succs.
   284  	// This is probably a stronger condition than required, but this happens extremely rarely,
   285  	// and it makes it easier to avoid getting deceived by pretty ASCII charts. See #44465.
   286  	if p0, p1 := b.Preds[0].b, b.Preds[1].b; p0 == t || p1 == t || p0 == u || p1 == u {
   287  		return nil
   288  	}
   289  
   290  	// Look for some common CFG structures
   291  	// in which the outbound paths from b merge,
   292  	// with no other preds joining them.
   293  	// In these cases, we can reconstruct what the value
   294  	// of any phi in b must be in the successor blocks.
   295  
   296  	if len(t.Preds) == 1 && len(t.Succs) == 1 &&
   297  		len(u.Preds) == 1 && len(u.Succs) == 1 &&
   298  		t.Succs[0].b == u.Succs[0].b && len(t.Succs[0].b.Preds) == 2 {
   299  		// p   q
   300  		//  \ /
   301  		//   b
   302  		//  / \
   303  		// t   u
   304  		//  \ /
   305  		//   m
   306  		//
   307  		// After the CFG modifications, this will look like
   308  		//
   309  		// p   q
   310  		// |  /
   311  		// | b
   312  		// |/ \
   313  		// t   u
   314  		//  \ /
   315  		//   m
   316  		//
   317  		// NB: t.Preds is (b, p), not (p, b).
   318  		m := t.Succs[0].b
   319  		return func(v *Value, i int) {
   320  			// Replace any uses of v in t and u with the value v must have,
   321  			// given that we have arrived at that block.
   322  			// Then move v to m and adjust its value accordingly;
   323  			// this handles all other uses of v.
   324  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   325  			u.replaceUses(v, argQ)
   326  			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
   327  			phi.AddArg2(argQ, argP)
   328  			t.replaceUses(v, phi)
   329  			if v.Uses == 0 {
   330  				return
   331  			}
   332  			v.moveTo(m, i)
   333  			// The phi in m belongs to whichever pred idx corresponds to t.
   334  			if m.Preds[0].b == t {
   335  				v.SetArgs2(phi, argQ)
   336  			} else {
   337  				v.SetArgs2(argQ, phi)
   338  			}
   339  		}
   340  	}
   341  
   342  	if len(t.Preds) == 2 && len(u.Preds) == 1 && len(u.Succs) == 1 && u.Succs[0].b == t {
   343  		// p   q
   344  		//  \ /
   345  		//   b
   346  		//   |\
   347  		//   | u
   348  		//   |/
   349  		//   t
   350  		//
   351  		// After the CFG modifications, this will look like
   352  		//
   353  		//     q
   354  		//    /
   355  		//   b
   356  		//   |\
   357  		// p | u
   358  		//  \|/
   359  		//   t
   360  		//
   361  		// NB: t.Preds is (b or u, b or u, p).
   362  		return func(v *Value, i int) {
   363  			// Replace any uses of v in u. Then move v to t.
   364  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   365  			u.replaceUses(v, argQ)
   366  			v.moveTo(t, i)
   367  			v.SetArgs3(argQ, argQ, argP)
   368  		}
   369  	}
   370  
   371  	if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u {
   372  		// p   q
   373  		//  \ /
   374  		//   b
   375  		//  /|
   376  		// t |
   377  		//  \|
   378  		//   u
   379  		//
   380  		// After the CFG modifications, this will look like
   381  		//
   382  		// p   q
   383  		// |  /
   384  		// | b
   385  		// |/|
   386  		// t |
   387  		//  \|
   388  		//   u
   389  		//
   390  		// NB: t.Preds is (b, p), not (p, b).
   391  		return func(v *Value, i int) {
   392  			// Replace any uses of v in t. Then move v to u.
   393  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   394  			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
   395  			phi.AddArg2(argQ, argP)
   396  			t.replaceUses(v, phi)
   397  			if v.Uses == 0 {
   398  				return
   399  			}
   400  			v.moveTo(u, i)
   401  			v.SetArgs2(argQ, phi)
   402  		}
   403  	}
   404  
   405  	// Look for some common CFG structures
   406  	// in which one outbound path from b exits,
   407  	// with no other preds joining.
   408  	// In these cases, we can reconstruct what the value
   409  	// of any phi in b must be in the path leading to exit,
   410  	// and move the phi to the non-exit path.
   411  
   412  	if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 {
   413  		// p   q
   414  		//  \ /
   415  		//   b
   416  		//  / \
   417  		// t   u
   418  		//
   419  		// where t is an Exit/Ret block.
   420  		//
   421  		// After the CFG modifications, this will look like
   422  		//
   423  		// p   q
   424  		// |  /
   425  		// | b
   426  		// |/ \
   427  		// t   u
   428  		//
   429  		// NB: t.Preds is (b, p), not (p, b).
   430  		return func(v *Value, i int) {
   431  			// Replace any uses of v in t and x. Then move v to u.
   432  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   433  			// If there are no uses of v in t or x, this phi will be unused.
   434  			// That's OK; it's not worth the cost to prevent that.
   435  			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
   436  			phi.AddArg2(argQ, argP)
   437  			t.replaceUses(v, phi)
   438  			if v.Uses == 0 {
   439  				return
   440  			}
   441  			v.moveTo(u, i)
   442  			v.SetArgs1(argQ)
   443  		}
   444  	}
   445  
   446  	if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 {
   447  		// p   q
   448  		//  \ /
   449  		//   b
   450  		//  / \
   451  		// t   u
   452  		//
   453  		// where u is an Exit/Ret block.
   454  		//
   455  		// After the CFG modifications, this will look like
   456  		//
   457  		// p   q
   458  		// |  /
   459  		// | b
   460  		// |/ \
   461  		// t   u
   462  		//
   463  		// NB: t.Preds is (b, p), not (p, b).
   464  		return func(v *Value, i int) {
   465  			// Replace any uses of v in u (and x). Then move v to t.
   466  			argP, argQ := v.Args[cidx], v.Args[1^cidx]
   467  			u.replaceUses(v, argQ)
   468  			v.moveTo(t, i)
   469  			v.SetArgs2(argQ, argP)
   470  		}
   471  	}
   472  
   473  	// TODO: handle more cases; shortcircuit optimizations turn out to be reasonably high impact
   474  	return nil
   475  }
   476  
   477  // replaceUses replaces all uses of old in b with new.
   478  func (b *Block) replaceUses(old, new *Value) {
   479  	for _, v := range b.Values {
   480  		for i, a := range v.Args {
   481  			if a == old {
   482  				v.SetArg(i, new)
   483  			}
   484  		}
   485  	}
   486  	for i, v := range b.ControlValues() {
   487  		if v == old {
   488  			b.ReplaceControl(i, new)
   489  		}
   490  	}
   491  }
   492  
   493  // moveTo moves v to dst, adjusting the appropriate Block.Values slices.
   494  // The caller is responsible for ensuring that this is safe.
   495  // i is the index of v in v.Block.Values.
   496  func (v *Value) moveTo(dst *Block, i int) {
   497  	if dst.Func.scheduled {
   498  		v.Fatalf("moveTo after scheduling")
   499  	}
   500  	src := v.Block
   501  	if src.Values[i] != v {
   502  		v.Fatalf("moveTo bad index %d", v, i)
   503  	}
   504  	if src == dst {
   505  		return
   506  	}
   507  	v.Block = dst
   508  	dst.Values = append(dst.Values, v)
   509  	last := len(src.Values) - 1
   510  	src.Values[i] = src.Values[last]
   511  	src.Values[last] = nil
   512  	src.Values = src.Values[:last]
   513  }
   514  

View as plain text