rewrite.go

     1  // Copyright 2015 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  	"fmt"
     9  	"math"
    10  
    11  	"cmd/compile/internal/ssa"
    12  	"cmd/compile/internal/ssa/ssaop"
    13  	"cmd/internal/src"
    14  )
    15  
    16  // deadcode indicates whether rewrite should try to remove any values that become dead.
    17  func applyRewrite(f *ssa.Func, rb ssa.BlockRewriter, rv ssa.ValueRewriter, deadcode ssa.DeadValueChoice) {
    18  	// repeat rewrites until we find no more rewrites
    19  	pendingLines := f.CachedLineStarts // Holds statement boundaries that need to be moved to a new value/block
    20  	pendingLines.Clear()
    21  	debug := f.Pass.Debug
    22  	if debug > 1 {
    23  		fmt.Printf("%s: rewriting for %s\n", f.Pass.Name, f.Name)
    24  	}
    25  	// if the number of rewrite iterations reaches itersLimit we will
    26  	// at that point turn on cycle detection. Instead of a fixed limit,
    27  	// size the limit according to func size to allow for cases such
    28  	// as the one in issue #66773.
    29  	itersLimit := f.NumBlocks()
    30  	if itersLimit < 20 {
    31  		itersLimit = 20
    32  	}
    33  	var iters int
    34  	var states map[string]bool
    35  	for {
    36  		if debug > 1 {
    37  			fmt.Printf("%s: iter %d\n", f.Pass.Name, iters)
    38  		}
    39  		change := false
    40  		deadChange := false
    41  		for _, b := range f.Blocks {
    42  			var b0 *ssa.Block
    43  			if debug > 1 {
    44  				fmt.Printf("%s: start block\n", f.Pass.Name)
    45  				b0 = new(ssa.Block)
    46  				*b0 = *b
    47  				b0.Succs = append([]ssa.Edge{}, b.Succs...) // make a new copy, not aliasing
    48  			}
    49  			for i, c := range b.ControlValues() {
    50  				for c.Op == ssaop.OpCopy {
    51  					c = c.Args[0]
    52  					b.ReplaceControl(i, c)
    53  				}
    54  			}
    55  			if rb(b) {
    56  				change = true
    57  				if debug > 1 {
    58  					fmt.Printf("rewriting %s  ->  %s\n", b0.LongString(), b.LongString())
    59  				}
    60  			}
    61  			for j, v := range b.Values {
    62  				if debug > 1 {
    63  					fmt.Printf("%s: consider %v\n", f.Pass.Name, v.LongString())
    64  				}
    65  				var v0 *ssa.Value
    66  				if debug > 1 {
    67  					v0 = new(ssa.Value)
    68  					*v0 = *v
    69  					v0.Args = append([]*ssa.Value{}, v.Args...) // make a new copy, not aliasing
    70  				}
    71  				if v.Uses == 0 && v.Removeable() {
    72  					if v.Op != ssaop.OpInvalid && deadcode == ssa.RemoveDeadValues {
    73  						// Reset any values that are now unused, so that we decrement
    74  						// the use count of all of its arguments.
    75  						// Not quite a deadcode pass, because it does not handle cycles.
    76  						// But it should help Uses==1 rules to fire.
    77  						v.Reset(ssaop.OpInvalid)
    78  						deadChange = true
    79  					}
    80  					// No point rewriting values which aren't used.
    81  					continue
    82  				}
    83  
    84  				vchange := ssa.PhiElimValue(v)
    85  				if vchange && debug > 1 {
    86  					fmt.Printf("rewriting %s  ->  %s\n", v0.LongString(), v.LongString())
    87  				}
    88  
    89  				// Eliminate copy inputs.
    90  				// If any copy input becomes unused, mark it
    91  				// as invalid and discard its argument. Repeat
    92  				// recursively on the discarded argument.
    93  				// This phase helps remove phantom "dead copy" uses
    94  				// of a value so that a x.Uses==1 rule condition
    95  				// fires reliably.
    96  				for i, a := range v.Args {
    97  					if a.Op != ssaop.OpCopy {
    98  						continue
    99  					}
   100  					aa := copySource(a)
   101  					v.SetArg(i, aa)
   102  					// If a, a copy, has a line boundary indicator, attempt to find a new value
   103  					// to hold it.  The first candidate is the value that will replace a (aa),
   104  					// if it shares the same block and line and is eligible.
   105  					// The second option is v, which has a as an input.  Because aa is earlier in
   106  					// the data flow, it is the better choice.
   107  					if a.Pos.IsStmt() == src.PosIsStmt {
   108  						if aa.Block == a.Block && aa.Pos.Line() == a.Pos.Line() && aa.Pos.IsStmt() != src.PosNotStmt {
   109  							aa.Pos = aa.Pos.WithIsStmt()
   110  						} else if v.Block == a.Block && v.Pos.Line() == a.Pos.Line() && v.Pos.IsStmt() != src.PosNotStmt {
   111  							v.Pos = v.Pos.WithIsStmt()
   112  						} else {
   113  							// Record the lost line and look for a new home after all rewrites are complete.
   114  							// TODO: it's possible (in FOR loops, in particular) for statement boundaries for the same
   115  							// line to appear in more than one block, but only one block is stored, so if both end
   116  							// up here, then one will be lost.
   117  							pendingLines.Set(a.Pos, int32(a.Block.ID))
   118  						}
   119  						a.Pos = a.Pos.WithNotStmt()
   120  					}
   121  					vchange = true
   122  					for a.Uses == 0 {
   123  						b := a.Args[0]
   124  						a.Reset(ssaop.OpInvalid)
   125  						a = b
   126  					}
   127  				}
   128  				if vchange && debug > 1 {
   129  					fmt.Printf("rewriting %s  ->  %s\n", v0.LongString(), v.LongString())
   130  				}
   131  
   132  				// apply rewrite function
   133  				if rv(v) {
   134  					vchange = true
   135  					// If value changed to a poor choice for a statement boundary, move the boundary
   136  					if v.Pos.IsStmt() == src.PosIsStmt {
   137  						if k := nextGoodStatementIndex(v, j, b); k != j {
   138  							v.Pos = v.Pos.WithNotStmt()
   139  							b.Values[k].Pos = b.Values[k].Pos.WithIsStmt()
   140  						}
   141  					}
   142  				}
   143  
   144  				change = change || vchange
   145  				if vchange && debug > 1 {
   146  					fmt.Printf("rewriting %s  ->  %s\n", v0.LongString(), v.LongString())
   147  				}
   148  			}
   149  		}
   150  		if !change && !deadChange {
   151  			break
   152  		}
   153  		iters++
   154  		if (iters > itersLimit || debug >= 2) && change {
   155  			// We've done a suspiciously large number of rewrites (or we're in debug mode).
   156  			// As of Sep 2021, 90% of rewrites complete in 4 iterations or fewer
   157  			// and the maximum value encountered during make.bash is 12.
   158  			// Start checking for cycles. (This is too expensive to do routinely.)
   159  			// Note: we avoid this path for deadChange-only iterations, to fix #51639.
   160  			if states == nil {
   161  				states = make(map[string]bool)
   162  			}
   163  			h := f.RewriteHash()
   164  			if _, ok := states[h]; ok {
   165  				// We've found a cycle.
   166  				// To diagnose it, set debug to 2 and start again,
   167  				// so that we'll print all rules applied until we complete another cycle.
   168  				// If debug is already >= 2, we've already done that, so it's time to crash.
   169  				if debug < 2 {
   170  					debug = 2
   171  					states = make(map[string]bool)
   172  				} else {
   173  					f.Fatalf("rewrite cycle detected")
   174  				}
   175  			}
   176  			states[h] = true
   177  		}
   178  	}
   179  	// remove clobbered values
   180  	for _, b := range f.Blocks {
   181  		j := 0
   182  		for i, v := range b.Values {
   183  			vl := v.Pos
   184  			if v.Op == ssaop.OpInvalid {
   185  				if v.Pos.IsStmt() == src.PosIsStmt {
   186  					pendingLines.Set(vl, int32(b.ID))
   187  				}
   188  				f.FreeValue(v)
   189  				continue
   190  			}
   191  			if v.Pos.IsStmt() != src.PosNotStmt && !ssa.NotStmtBoundary(v.Op) {
   192  				if pl, ok := pendingLines.Get(vl); ok && pl == int32(b.ID) {
   193  					pendingLines.Remove(vl)
   194  					v.Pos = v.Pos.WithIsStmt()
   195  				}
   196  			}
   197  			if i != j {
   198  				b.Values[j] = v
   199  			}
   200  			j++
   201  		}
   202  		if pl, ok := pendingLines.Get(b.Pos); ok && pl == int32(b.ID) {
   203  			b.Pos = b.Pos.WithIsStmt()
   204  			pendingLines.Remove(b.Pos)
   205  		}
   206  		b.TruncateValues(j)
   207  	}
   208  }
   209  
   210  // truncate64Fto32F converts a float64 value to a float32 preserving the bit pattern
   211  // of the mantissa. It will panic if the truncation results in lost information.
   212  func truncate64Fto32F(f float64) float32 {
   213  	if !isExactFloat32(f) {
   214  		panic("truncate64Fto32F: truncation is not exact")
   215  	}
   216  	if !math.IsNaN(f) {
   217  		return float32(f)
   218  	}
   219  	// NaN bit patterns aren't necessarily preserved across conversion
   220  	// instructions so we need to do the conversion manually.
   221  	b := math.Float64bits(f)
   222  	m := b & ((1 << 52) - 1) // mantissa (a.k.a. significand)
   223  	//          | sign                  | exponent   | mantissa       |
   224  	r := uint32(((b >> 32) & (1 << 31)) | 0x7f800000 | (m >> (52 - 23)))
   225  	return math.Float32frombits(r)
   226  }
   227  
   228  // auxTo32F decodes a float32 from the AuxInt value provided.
   229  func auxTo32F(i int64) float32 {
   230  	return truncate64Fto32F(math.Float64frombits(uint64(i)))
   231  }
   232  
   233  // mergePoint finds a block among a's blocks which dominates b and is itself
   234  // dominated by all of a's blocks. Returns nil if it can't find one.
   235  // Might return nil even if one does exist.
   236  func mergePoint(b *ssa.Block, a ...*ssa.Value) *ssa.Block {
   237  	// Walk backward from b looking for one of the a's blocks.
   238  
   239  	// Max distance
   240  	d := 100
   241  
   242  	for d > 0 {
   243  		for _, x := range a {
   244  			if b == x.Block {
   245  				goto found
   246  			}
   247  		}
   248  		if len(b.Preds) > 1 {
   249  			// Don't know which way to go back. Abort.
   250  			return nil
   251  		}
   252  		b = b.Preds[0].B
   253  		d--
   254  	}
   255  	return nil // too far away
   256  found:
   257  	// At this point, r is the first value in a that we find by walking backwards.
   258  	// if we return anything, r will be it.
   259  	r := b
   260  
   261  	// Keep going, counting the other a's that we find. They must all dominate r.
   262  	na := 0
   263  	for d > 0 {
   264  		for _, x := range a {
   265  			if b == x.Block {
   266  				na++
   267  			}
   268  		}
   269  		if na == len(a) {
   270  			// Found all of a in a backwards walk. We can return r.
   271  			return r
   272  		}
   273  		if len(b.Preds) > 1 {
   274  			return nil
   275  		}
   276  		b = b.Preds[0].B
   277  		d--
   278  
   279  	}
   280  	return nil // too far away
   281  }
   282  
   283  // encodes condition code and NZCV flags into result.
   284  func arm64ConditionalParamsAuxInt(cond ssaop.Op, nzcv uint8) ssa.Arm64ConditionalParams {
   285  	if cond < ssaop.OpARM64Equal || cond > ssaop.OpARM64GreaterEqualU {
   286  		panic("Wrong conditional operation")
   287  	}
   288  	if nzcv&0x0f != nzcv {
   289  		panic("Wrong value of NZCV flag")
   290  	}
   291  	return ssa.Arm64ConditionalParams{Cond: cond, NzcvVal: nzcv, ConstVal: 0, Ind: false}
   292  }
   293  
   294  // encodes condition code, NZCV flags and constant value into auxint.
   295  func arm64ConditionalParamsAuxIntWithValue(cond ssaop.Op, nzcv uint8, value uint8) ssa.Arm64ConditionalParams {
   296  	if value&0x1f != value {
   297  		panic("Wrong value of constant")
   298  	}
   299  	params := arm64ConditionalParamsAuxInt(cond, nzcv)
   300  	params.ConstVal = value
   301  	params.Ind = true
   302  	return params
   303  }
   304
View as plain text