branchelim.go

     1  // Copyright 2017 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  	"cmd/internal/src"
    12  )
    13  
    14  // branchelim tries to eliminate branches by
    15  // generating CondSelect instructions.
    16  //
    17  // Search for basic blocks that look like
    18  //
    19  //	bb0            bb0
    20  //	 | \          /   \
    21  //	 | bb1  or  bb1   bb2    <- trivial if/else blocks
    22  //	 | /          \   /
    23  //	bb2            bb3
    24  //
    25  // where the intermediate blocks are mostly empty (with no side-effects);
    26  // rewrite Phis in the postdominator as CondSelects.
    27  func branchelim(f *ssa.Func) {
    28  	// FIXME: add support for lowering CondSelects on more architectures
    29  	if !f.Config.HaveCondSelect {
    30  		return
    31  	}
    32  
    33  	// Find all the values used in computing the address of any load.
    34  	// Typically these values have operations like AddPtr, Lsh64x64, etc.
    35  	loadAddr := f.NewSparseSet(f.NumValues())
    36  	defer f.RetSparseSet(loadAddr)
    37  	for _, b := range f.Blocks {
    38  		for _, v := range b.Values {
    39  			switch v.Op {
    40  			case ssaop.OpLoad, ssaop.OpAtomicLoad8, ssaop.OpAtomicLoad32, ssaop.OpAtomicLoad64, ssaop.OpAtomicLoadPtr, ssaop.OpAtomicLoadAcq32, ssaop.OpAtomicLoadAcq64:
    41  				loadAddr.Add(v.Args[0].ID)
    42  			case ssaop.OpMove:
    43  				loadAddr.Add(v.Args[1].ID)
    44  			}
    45  		}
    46  	}
    47  	po := f.Postorder()
    48  	for {
    49  		n := loadAddr.Size()
    50  		for _, b := range po {
    51  			for i := len(b.Values) - 1; i >= 0; i-- {
    52  				v := b.Values[i]
    53  				if !loadAddr.Contains(v.ID) {
    54  					continue
    55  				}
    56  				for _, a := range v.Args {
    57  					if a.Type.IsInteger() || a.Type.IsPtr() || a.Type.IsUnsafePtr() {
    58  						loadAddr.Add(a.ID)
    59  					}
    60  				}
    61  			}
    62  		}
    63  		if loadAddr.Size() == n {
    64  			break
    65  		}
    66  	}
    67  
    68  	change := true
    69  	for change {
    70  		change = false
    71  		for _, b := range f.Blocks {
    72  			change = elimIf(f, loadAddr, b) || elimIfElse(f, loadAddr, b) || change
    73  		}
    74  	}
    75  }
    76  
    77  func canCondSelect(v *ssa.Value, arch string, loadAddr *ssa.SparseSet) bool {
    78  	if loadAddr != nil && // prove calls this on some multiplies and doesn't take care of loadAddrs
    79  		loadAddr.Contains(v.ID) {
    80  		// The result of the soon-to-be conditional move is used to compute a load address.
    81  		// We want to avoid generating a conditional move in this case
    82  		// because the load address would now be data-dependent on the condition.
    83  		// Previously it would only be control-dependent on the condition, which is faster
    84  		// if the branch predicts well (or possibly even if it doesn't, if the load will
    85  		// be an expensive cache miss).
    86  		// See issue #26306.
    87  		return false
    88  	}
    89  	if arch == "loong64" {
    90  		// We should not generate conditional moves if neither of the arguments is constant zero,
    91  		// because it requires three instructions (OR, MASKEQZ, MASKNEZ) and will increase the
    92  		// register pressure.
    93  		if !(v.Args[0].IsGenericIntConst() && v.Args[0].AuxInt == 0) &&
    94  			!(v.Args[1].IsGenericIntConst() && v.Args[1].AuxInt == 0) {
    95  			return false
    96  		}
    97  	}
    98  	// For now, stick to simple scalars that fit in registers
    99  	switch {
   100  	case v.Type.Size() > v.Block.Func.Config.RegSize:
   101  		return false
   102  	case v.Type.IsPtrShaped():
   103  		return true
   104  	case v.Type.IsInteger():
   105  		if arch == "amd64" && v.Type.Size() < 2 {
   106  			// amd64 doesn't support CMOV with byte registers
   107  			return false
   108  		}
   109  		return true
   110  	default:
   111  		return false
   112  	}
   113  }
   114  
   115  // floatMinMaxSelOp returns the comparison-select op to use for a float-typed
   116  // phi that implements the min/max branch idiom, or OpInvalid if the phi is not
   117  // such an idiom. trueVal is the phi argument chosen when cond is true, falseVal
   118  // otherwise. The strict forms "a < b ? a : b" (min) and "a < b ? b : a" (max)
   119  // match the Min/Max*FSel ops exactly, including their NaN and signed-zero
   120  // behavior. Those ops lower unconditionally on the supported architectures, so
   121  // there is no risk of an unlowerable value. Greater comparisons are
   122  // canonicalized to Less with swapped operands during SSA building, so only Less
   123  // needs to be matched here.
   124  func floatMinMaxSelOp(cond, trueVal, falseVal *ssa.Value) ssaop.Op {
   125  	switch trueVal.Block.Func.Config.Arch {
   126  	case "amd64", "arm64":
   127  	default:
   128  		return ssaop.OpInvalid
   129  	}
   130  	switch cond.Op {
   131  	case ssaop.OpLess32F, ssaop.OpLess64F:
   132  	default:
   133  		return ssaop.OpInvalid
   134  	}
   135  	min := trueVal == cond.Args[0] && falseVal == cond.Args[1]
   136  	max := trueVal == cond.Args[1] && falseVal == cond.Args[0]
   137  	switch {
   138  	case min && trueVal.Type.Size() == 8:
   139  		return ssaop.OpMin64FSel
   140  	case min && trueVal.Type.Size() == 4:
   141  		return ssaop.OpMin32FSel
   142  	case max && trueVal.Type.Size() == 8:
   143  		return ssaop.OpMax64FSel
   144  	case max && trueVal.Type.Size() == 4:
   145  		return ssaop.OpMax32FSel
   146  	}
   147  	return ssaop.OpInvalid
   148  }
   149  
   150  // canSelectPhi reports whether phi v can be rewritten as a CondSelect or a
   151  // float min/max-select op. cond is the branch condition. When !swap, v.Args[0]
   152  // is chosen when cond is true; otherwise v.Args[1] is chosen.
   153  func canSelectPhi(v *ssa.Value, loadAddr *ssa.SparseSet, cond *ssa.Value, swap bool) bool {
   154  	if canCondSelect(v, v.Block.Func.Config.Arch, loadAddr) {
   155  		return true
   156  	}
   157  	trueVal, falseVal := v.Args[0], v.Args[1]
   158  	if swap {
   159  		trueVal, falseVal = falseVal, trueVal
   160  	}
   161  	return floatMinMaxSelOp(cond, trueVal, falseVal) != ssaop.OpInvalid
   162  }
   163  
   164  // rewritePhiAsSelect rewrites the eligible phi v (see canSelectPhi) into a
   165  // CondSelect or a float min/max-select op. When !swap, v.Args[0] is chosen
   166  // when cond is true; otherwise v.Args[1] is chosen. The arguments are swapped
   167  // first if needed so that Args[0] is the value chosen when cond is true.
   168  func rewritePhiAsSelect(v *ssa.Value, swap bool, cond *ssa.Value) {
   169  	if swap {
   170  		v.Args[0], v.Args[1] = v.Args[1], v.Args[0]
   171  	}
   172  	if op := floatMinMaxSelOp(cond, v.Args[0], v.Args[1]); op != ssaop.OpInvalid {
   173  		v.Op = op
   174  		return
   175  	}
   176  	v.Op = ssaop.OpCondSelect
   177  	v.AddArg(cond)
   178  }
   179  
   180  // elimIf converts the one-way branch starting at dom in f to a conditional move if possible.
   181  // loadAddr is a set of values which are used to compute the address of a load.
   182  // Those values are exempt from CMOV generation.
   183  func elimIf(f *ssa.Func, loadAddr *ssa.SparseSet, dom *ssa.Block) bool {
   184  	// See if dom is an If with one arm that
   185  	// is trivial and succeeded by the other
   186  	// successor of dom.
   187  	if dom.Kind != block.BlockIf || dom.Likely != ssa.BranchUnknown {
   188  		return false
   189  	}
   190  	var simple, post *ssa.Block
   191  	for i := range dom.Succs {
   192  		bb, other := dom.Succs[i].Block(), dom.Succs[i^1].Block()
   193  		if isLeafPlain(bb) && bb.Succs[0].Block() == other {
   194  			simple = bb
   195  			post = other
   196  			break
   197  		}
   198  	}
   199  	if simple == nil || len(post.Preds) != 2 || post == dom {
   200  		return false
   201  	}
   202  
   203  	// We've found our diamond CFG of blocks.
   204  	// Now decide if fusing 'simple' into dom+post
   205  	// looks profitable.
   206  
   207  	// Replace Phi instructions in b with CondSelect instructions
   208  	swap := (post.Preds[0].Block() == dom) != (dom.Succs[0].Block() == post)
   209  
   210  	// Check that there are Phis, and that all of them
   211  	// can be safely rewritten to CondSelect.
   212  	hasphis := false
   213  	for _, v := range post.Values {
   214  		if v.Op == ssaop.OpPhi {
   215  			hasphis = true
   216  			if !canSelectPhi(v, loadAddr, dom.Controls[0], swap) {
   217  				return false
   218  			}
   219  		}
   220  	}
   221  	if !hasphis {
   222  		return false
   223  	}
   224  
   225  	// Pick some upper bound for the number of instructions
   226  	// we'd be willing to execute just to generate a dead
   227  	// argument to CondSelect. In the worst case, this is
   228  	// the number of useless instructions executed.
   229  	const maxfuseinsts = 2
   230  
   231  	if len(simple.Values) > maxfuseinsts || !canSpeculativelyExecute(simple) {
   232  		return false
   233  	}
   234  	for _, v := range post.Values {
   235  		if v.Op != ssaop.OpPhi {
   236  			continue
   237  		}
   238  		rewritePhiAsSelect(v, swap, dom.Controls[0])
   239  	}
   240  
   241  	// Put all of the instructions into 'dom'
   242  	// and update the CFG appropriately.
   243  	dom.Kind = post.Kind
   244  	dom.CopyControls(post)
   245  	dom.Aux = post.Aux
   246  	dom.Succs = append(dom.Succs[:0], post.Succs...)
   247  	for i := range dom.Succs {
   248  		e := dom.Succs[i]
   249  		e.B.Preds[e.I].B = dom
   250  	}
   251  
   252  	// Try really hard to preserve statement marks attached to blocks.
   253  	simplePos := simple.Pos
   254  	postPos := post.Pos
   255  	simpleStmt := simplePos.IsStmt() == src.PosIsStmt
   256  	postStmt := postPos.IsStmt() == src.PosIsStmt
   257  
   258  	for _, v := range simple.Values {
   259  		v.Block = dom
   260  	}
   261  	for _, v := range post.Values {
   262  		v.Block = dom
   263  	}
   264  
   265  	// findBlockPos determines if b contains a stmt-marked value
   266  	// that has the same line number as the Pos for b itself.
   267  	// (i.e. is the position on b actually redundant?)
   268  	findBlockPos := func(b *ssa.Block) bool {
   269  		pos := b.Pos
   270  		for _, v := range b.Values {
   271  			// See if there is a stmt-marked value already that matches simple.Pos (and perhaps post.Pos)
   272  			if pos.SameFileAndLine(v.Pos) && v.Pos.IsStmt() == src.PosIsStmt {
   273  				return true
   274  			}
   275  		}
   276  		return false
   277  	}
   278  	if simpleStmt {
   279  		simpleStmt = !findBlockPos(simple)
   280  		if !simpleStmt && simplePos.SameFileAndLine(postPos) {
   281  			postStmt = false
   282  		}
   283  
   284  	}
   285  	if postStmt {
   286  		postStmt = !findBlockPos(post)
   287  	}
   288  
   289  	// If simpleStmt and/or postStmt are still true, then try harder
   290  	// to find the corresponding statement marks new homes.
   291  
   292  	// setBlockPos determines if b contains a can-be-statement value
   293  	// that has the same line number as the Pos for b itself, and
   294  	// puts a statement mark on it, and returns whether it succeeded
   295  	// in this operation.
   296  	setBlockPos := func(b *ssa.Block) bool {
   297  		pos := b.Pos
   298  		for _, v := range b.Values {
   299  			if pos.SameFileAndLine(v.Pos) && !isPoorStatementOp(v.Op) {
   300  				v.Pos = v.Pos.WithIsStmt()
   301  				return true
   302  			}
   303  		}
   304  		return false
   305  	}
   306  	// If necessary and possible, add a mark to a value in simple
   307  	if simpleStmt {
   308  		if setBlockPos(simple) && simplePos.SameFileAndLine(postPos) {
   309  			postStmt = false
   310  		}
   311  	}
   312  	// If necessary and possible, add a mark to a value in post
   313  	if postStmt {
   314  		postStmt = !setBlockPos(post)
   315  	}
   316  
   317  	// Before giving up (this was added because it helps), try the end of "dom", and if that is not available,
   318  	// try the values in the successor block if it is uncomplicated.
   319  	if postStmt {
   320  		if dom.Pos.IsStmt() != src.PosIsStmt {
   321  			dom.Pos = postPos
   322  		} else {
   323  			// Try the successor block
   324  			if len(dom.Succs) == 1 && len(dom.Succs[0].Block().Preds) == 1 {
   325  				succ := dom.Succs[0].Block()
   326  				for _, v := range succ.Values {
   327  					if isPoorStatementOp(v.Op) {
   328  						continue
   329  					}
   330  					if postPos.SameFileAndLine(v.Pos) {
   331  						v.Pos = v.Pos.WithIsStmt()
   332  					}
   333  					postStmt = false
   334  					break
   335  				}
   336  				// If postStmt still true, tag the block itself if possible
   337  				if postStmt && succ.Pos.IsStmt() != src.PosIsStmt {
   338  					succ.Pos = postPos
   339  				}
   340  			}
   341  		}
   342  	}
   343  
   344  	dom.Values = append(dom.Values, simple.Values...)
   345  	dom.Values = append(dom.Values, post.Values...)
   346  
   347  	// Trash 'post' and 'simple'
   348  	clobberBlock(post)
   349  	clobberBlock(simple)
   350  
   351  	f.InvalidateCFG()
   352  	return true
   353  }
   354  
   355  // is this a BlockPlain with one predecessor?
   356  func isLeafPlain(b *ssa.Block) bool {
   357  	return b.Kind == block.BlockPlain && len(b.Preds) == 1
   358  }
   359  
   360  func clobberBlock(b *ssa.Block) {
   361  	b.Values = nil
   362  	b.Preds = nil
   363  	b.Succs = nil
   364  	b.Aux = nil
   365  	b.ResetControls()
   366  	b.Likely = ssa.BranchUnknown
   367  	b.Kind = block.BlockInvalid
   368  }
   369  
   370  // elimIfElse converts the two-way branch starting at dom in f to a conditional move if possible.
   371  // loadAddr is a set of values which are used to compute the address of a load.
   372  // Those values are exempt from CMOV generation.
   373  func elimIfElse(f *ssa.Func, loadAddr *ssa.SparseSet, b *ssa.Block) bool {
   374  	// See if 'b' ends in an if/else: it should
   375  	// have two successors, both of which are BlockPlain
   376  	// and succeeded by the same block.
   377  	if b.Kind != block.BlockIf || b.Likely != ssa.BranchUnknown {
   378  		return false
   379  	}
   380  	yes, no := b.Succs[0].Block(), b.Succs[1].Block()
   381  	if !isLeafPlain(yes) || len(yes.Values) > 1 || !canSpeculativelyExecute(yes) {
   382  		return false
   383  	}
   384  	if !isLeafPlain(no) || len(no.Values) > 1 || !canSpeculativelyExecute(no) {
   385  		return false
   386  	}
   387  	if b.Succs[0].Block().Succs[0].Block() != b.Succs[1].Block().Succs[0].Block() {
   388  		return false
   389  	}
   390  	// block that postdominates the if/else
   391  	post := b.Succs[0].Block().Succs[0].Block()
   392  	if len(post.Preds) != 2 || post == b {
   393  		return false
   394  	}
   395  	swap := post.Preds[0].Block() != b.Succs[0].Block()
   396  	hasphis := false
   397  	for _, v := range post.Values {
   398  		if v.Op == ssaop.OpPhi {
   399  			hasphis = true
   400  			if !canSelectPhi(v, loadAddr, b.Controls[0], swap) {
   401  				return false
   402  			}
   403  		}
   404  	}
   405  	if !hasphis {
   406  		return false
   407  	}
   408  
   409  	// Don't generate CondSelects if branch is cheaper.
   410  	if !shouldElimIfElse(no, yes, post, f.Config.Arch) {
   411  		return false
   412  	}
   413  
   414  	// now we're committed: rewrite each Phi as a select
   415  	for _, v := range post.Values {
   416  		if v.Op != ssaop.OpPhi {
   417  			continue
   418  		}
   419  		rewritePhiAsSelect(v, swap, b.Controls[0])
   420  	}
   421  
   422  	// Move the contents of all of these
   423  	// blocks into 'b' and update CFG edges accordingly
   424  	b.Kind = post.Kind
   425  	b.CopyControls(post)
   426  	b.Aux = post.Aux
   427  	b.Succs = append(b.Succs[:0], post.Succs...)
   428  	for i := range b.Succs {
   429  		e := b.Succs[i]
   430  		e.B.Preds[e.I].B = b
   431  	}
   432  	for i := range post.Values {
   433  		post.Values[i].Block = b
   434  	}
   435  	for i := range yes.Values {
   436  		yes.Values[i].Block = b
   437  	}
   438  	for i := range no.Values {
   439  		no.Values[i].Block = b
   440  	}
   441  	b.Values = append(b.Values, yes.Values...)
   442  	b.Values = append(b.Values, no.Values...)
   443  	b.Values = append(b.Values, post.Values...)
   444  
   445  	// trash post, yes, and no
   446  	clobberBlock(yes)
   447  	clobberBlock(no)
   448  	clobberBlock(post)
   449  
   450  	f.InvalidateCFG()
   451  	return true
   452  }
   453  
   454  // shouldElimIfElse reports whether estimated cost of eliminating branch
   455  // is lower than threshold.
   456  func shouldElimIfElse(no, yes, post *ssa.Block, arch string) bool {
   457  	switch arch {
   458  	default:
   459  		return true
   460  	case "amd64":
   461  		const maxcost = 2
   462  		phi := 0
   463  		other := 0
   464  		for _, v := range post.Values {
   465  			if v.Op == ssaop.OpPhi {
   466  				// Each phi results in CondSelect, which lowers into CMOV,
   467  				// CMOV has latency >1 on most CPUs.
   468  				phi++
   469  			}
   470  			for _, x := range v.Args {
   471  				if x.Block == no || x.Block == yes {
   472  					other++
   473  				}
   474  			}
   475  		}
   476  		cost := phi * 1
   477  		if phi > 1 {
   478  			// If we have more than 1 phi and some values in post have args
   479  			// in yes or no blocks, we may have to recalculate condition, because
   480  			// those args may clobber flags. For now assume that all operations clobber flags.
   481  			cost += other * 1
   482  		}
   483  		return cost < maxcost
   484  	}
   485  }
   486  
   487  // canSpeculativelyExecute reports whether every value in the block can
   488  // be evaluated without causing any observable side effects (memory
   489  // accesses, panics and so on) except for execution time changes. It
   490  // also ensures that the block does not contain any phis which we can't
   491  // speculatively execute.
   492  // Warning: this function cannot currently detect values that represent
   493  // instructions the execution of which need to be guarded with CPU
   494  // hardware feature checks. See issue #34950.
   495  func canSpeculativelyExecute(b *ssa.Block) bool {
   496  	// don't fuse memory ops, Phi ops, divides (can panic),
   497  	// or anything else with side-effects
   498  	for _, v := range b.Values {
   499  		if v.Op == ssaop.OpPhi || isDivMod(v.Op) || isPtrArithmetic(v.Op) ||
   500  			v.Type.IsMemory() || ssaop.OpcodeTable[v.Op].HasSideEffects {
   501  			return false
   502  		}
   503  
   504  		// Allow inlining markers to be speculatively executed
   505  		// even though they have a memory argument.
   506  		// See issue #74915.
   507  		if v.Op != ssaop.OpInlMark && v.MemoryArg() != nil {
   508  			return false
   509  		}
   510  	}
   511  	return true
   512  }
   513  
   514  func isDivMod(op ssaop.Op) bool {
   515  	switch op {
   516  	case ssaop.OpDiv8, ssaop.OpDiv8u, ssaop.OpDiv16, ssaop.OpDiv16u,
   517  		ssaop.OpDiv32, ssaop.OpDiv32u, ssaop.OpDiv64, ssaop.OpDiv64u, ssaop.OpDiv128u,
   518  		ssaop.OpDiv32F, ssaop.OpDiv64F,
   519  		ssaop.OpMod8, ssaop.OpMod8u, ssaop.OpMod16, ssaop.OpMod16u,
   520  		ssaop.OpMod32, ssaop.OpMod32u, ssaop.OpMod64, ssaop.OpMod64u:
   521  		return true
   522  	default:
   523  		return false
   524  	}
   525  }
   526  
   527  func isPtrArithmetic(op ssaop.Op) bool {
   528  	// Pointer arithmetic can't be speculatively executed because the result
   529  	// may be an invalid pointer (if, for example, the condition is that the
   530  	// base pointer is not nil). See issue 56990.
   531  	switch op {
   532  	case ssaop.OpOffPtr, ssaop.OpAddPtr, ssaop.OpSubPtr:
   533  		return true
   534  	default:
   535  		return false
   536  	}
   537  }
   538
View as plain text