Source file src/cmd/compile/internal/ssacompile/mem2reg.go

     1  // Copyright 2026 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  // This file contains the mem2reg pass.
     8  // mem2reg promotes memory operations to register operations.
     9  // This is a classic compiler optimization that can significantly
    10  // improve the performance of generated code by reducing the number
    11  // of memory accesses.
    12  //
    13  // The algorithm identifies memory stores (OpStore) to stack slots
    14  // that are followed by loads (OpLoad) from the same stack slot,
    15  // with no intervening stores to that slot. The loads are then
    16  // replaced with the value that was stored.
    17  
    18  import (
    19  	"cmd/compile/internal/base"
    20  	"cmd/compile/internal/ir"
    21  	"cmd/compile/internal/ssa"
    22  	"cmd/compile/internal/ssa/ssaop"
    23  	"cmd/compile/internal/types"
    24  	"internal/buildcfg"
    25  	"slices"
    26  )
    27  
    28  type useType int
    29  
    30  const (
    31  	useLoad   useType = 1 << iota // used as the address to load from
    32  	useStore                      // used as the address to store to
    33  	useOffset                     // pointer arithmetic (OpOffPtr)
    34  	useCopy                       // uses propagated through a copy
    35  	useZero                       // used in OpZero
    36  	useMove                       // used in OpMove
    37  	useOther                      // includes escaping uses and OpPtrIndex
    38  )
    39  
    40  // useTable wraps the shared reverse-use table (see uses.go) so that
    41  // queries about values created after the table was built - their IDs
    42  // are out of range - report no uses instead of panicking. The mem2reg
    43  // and decomposeAddr passes ask about such values after their rewrites.
    44  type useTable struct {
    45  	useInfo
    46  }
    47  
    48  // of returns the uses of v recorded in u, or nil if v postdates the table.
    49  func (u *useTable) of(v *ssa.Value) []*ssa.Value {
    50  	if int(v.ID) >= len(u.starts) {
    51  		return nil
    52  	}
    53  	return u.get(v)
    54  }
    55  
    56  // classifyUses analyzes how a pointer is used and returns a bitmask of use types.
    57  func classifyUses(v *ssa.Value, uses *useTable) useType {
    58  	q := []*ssa.Value{v}
    59  	var u useType
    60  	for len(q) > 0 {
    61  		curr := q[len(q)-1]
    62  		q = q[:len(q)-1]
    63  		for _, use := range uses.of(curr) {
    64  			switch use.Op {
    65  			case ssaop.OpCopy:
    66  				u |= useCopy
    67  				q = append(q, use)
    68  			case ssaop.OpOffPtr:
    69  				u |= useOffset
    70  				q = append(q, use)
    71  			case ssaop.OpLoad:
    72  				u |= useLoad
    73  			case ssaop.OpStore:
    74  				if curr == use.Args[1] {
    75  					// Storing the address as value.
    76  					u |= useOther
    77  				} else {
    78  					u |= useStore
    79  				}
    80  			case ssaop.OpZero:
    81  				u |= useZero
    82  			case ssaop.OpMove:
    83  				u |= useMove
    84  			default:
    85  				// TODO: handle more cases?
    86  				// e.g. AddPtr, SubPtr, PtrIndex, NilCheck, EqPtr, NeqPtr
    87  				u |= useOther
    88  			}
    89  		}
    90  	}
    91  	return u
    92  }
    93  
    94  // variableDemographic summarizes how the address of an auto variable is
    95  // used, over all LocalAddr uses of that variable.
    96  type variableDemographic struct {
    97  	// ls is true when the address of this variable is only used by Load
    98  	// and Store, and no VarLive is applied on the name.
    99  	ls bool
   100  	// lszmco is true when the address of this variable is only used by
   101  	// Load, Store, Zero, Move, Copy and OffPtr, and no VarLive is
   102  	// applied on the name.
   103  	lszmco  bool
   104  	varDefs []*ssa.Value // All the VarDefs on this name.
   105  }
   106  
   107  // variableDemographics analyzes f and returns the variable demographics data of f.
   108  //
   109  //	demographics is the map from names to their demographics.
   110  //	localAddrs is the LocalAddr ssa values of the names in demographics.
   111  //	u tracks the uses of the values in f (see uses.go); it is nil, and
   112  //	nothing is allocated, when the function has no candidate variables.
   113  //
   114  // The caller must free u (u.free(f)) when non-nil.
   115  func variableDemographics(f *ssa.Func) (
   116  	demographics map[ssa.Aux]*variableDemographic,
   117  	localAddrs []*ssa.Value,
   118  	u *useTable) {
   119  	// Fast path: most functions have no candidate LocalAddr at all, and
   120  	// for them the pass chain has nothing to do. Detect that with a scan
   121  	// that allocates nothing, so those functions pay (almost) nothing.
   122  	found := false
   123  	for _, b := range f.Blocks {
   124  		for _, c := range b.ControlValues() {
   125  			if c.Op == ssaop.OpOffPtr || c.Op == ssaop.OpLocalAddr {
   126  				f.Fatalf("unexpected pointer value in block control")
   127  			}
   128  		}
   129  		for _, v := range b.Values {
   130  			if v.Op == ssaop.OpLocalAddr {
   131  				if n := v.Aux.(*ir.Name); n.Class == ir.PAUTO || isABIInternalParam(f, n) {
   132  					found = true
   133  					break
   134  				}
   135  			}
   136  		}
   137  		if found {
   138  			break
   139  		}
   140  	}
   141  	if !found {
   142  		return nil, nil, nil
   143  	}
   144  
   145  	// Build the reverse-use table using the shared cache-backed
   146  	// infrastructure from uses.go.
   147  	u = &useTable{uses(f)}
   148  	varLives := map[ssa.Aux]bool{}
   149  	demographics = make(map[ssa.Aux]*variableDemographic)
   150  	for _, b := range f.Blocks {
   151  		for _, v := range b.Values {
   152  			switch v.Op {
   153  			case ssaop.OpVarLive:
   154  				varLives[v.Aux] = true
   155  			case ssaop.OpVarDef:
   156  				d := demographics[v.Aux]
   157  				if d == nil {
   158  					d = &variableDemographic{ls: true, lszmco: true}
   159  					demographics[v.Aux] = d
   160  				}
   161  				d.varDefs = append(d.varDefs, v)
   162  			}
   163  		}
   164  	}
   165  	// Compute the use pattern of variables and the memory access demographic patterns.
   166  	for _, b := range f.Blocks {
   167  		for _, v := range b.Values {
   168  			if v.Op == ssaop.OpLocalAddr {
   169  				if n := v.Aux.(*ir.Name); n.Class == ir.PAUTO || isABIInternalParam(f, n) {
   170  					ut := classifyUses(v, u)
   171  					d := demographics[n]
   172  					if d == nil {
   173  						d = &variableDemographic{ls: true, lszmco: true}
   174  						demographics[n] = d
   175  					}
   176  					if ut&^(useLoad|useStore) != 0 {
   177  						d.ls = false
   178  					}
   179  					if ut&useOther != 0 {
   180  						d.lszmco = false
   181  					}
   182  					localAddrs = append(localAddrs, v)
   183  				}
   184  			}
   185  		}
   186  	}
   187  	// Names that have a VarLive applied are expected by the runtime to stay
   188  	// in memory (e.g. to be kept alive across a call for the GC), so they do
   189  	// not qualify for promotion.
   190  	for n := range varLives {
   191  		if d := demographics[n]; d != nil {
   192  			d.ls = false
   193  			d.lszmco = false
   194  		}
   195  	}
   196  	return
   197  }
   198  
   199  var reinterpretOpMap = map[[2]types.Kind]ssaop.Op{
   200  	{types.TUINT32, types.TFLOAT32}: ssaop.OpI32AsF32,
   201  	{types.TINT32, types.TFLOAT32}:  ssaop.OpI32AsF32,
   202  	{types.TFLOAT32, types.TUINT32}: ssaop.OpF32AsI32,
   203  	{types.TFLOAT32, types.TINT32}:  ssaop.OpF32AsI32,
   204  	{types.TUINT64, types.TFLOAT64}: ssaop.OpI64AsF64,
   205  	{types.TINT64, types.TFLOAT64}:  ssaop.OpI64AsF64,
   206  	{types.TFLOAT64, types.TUINT64}: ssaop.OpF64AsI64,
   207  	{types.TFLOAT64, types.TINT64}:  ssaop.OpF64AsI64,
   208  }
   209  
   210  // reinterpretOp returns a t1 => t2 reinterpret op if available in [reinterpretOpMap].
   211  // Otherwise it returns OpInvalid.
   212  func reinterpretOp(t1, t2 *types.Type) ssaop.Op {
   213  	if buildcfg.GOARCH != "amd64" {
   214  		// Currently only amd64 has the proper lowering rules for these ops.
   215  		return ssaop.OpInvalid
   216  	}
   217  	if op, ok := reinterpretOpMap[[2]types.Kind{t1.Kind(), t2.Kind()}]; ok {
   218  		return op
   219  	}
   220  
   221  	return ssaop.OpInvalid
   222  }
   223  
   224  // copyCompatibleType reports whether a value of type t1 can directly stand in
   225  // for a value of type t2 (same size and compatible representation).
   226  func copyCompatibleType(t1, t2 *types.Type) bool {
   227  	if t1.Size() != t2.Size() {
   228  		return false
   229  	}
   230  	if t1.IsInteger() {
   231  		return t2.IsInteger()
   232  	}
   233  	if ssa.IsPtr(t1) {
   234  		return ssa.IsPtr(t2)
   235  	}
   236  	if t1.IsSIMD() {
   237  		// SIMD vector types of the same size share a representation,
   238  		// e.g. the generic vec128 that SIMD ops produce and archsimd.Int8x16.
   239  		return t2.IsSIMD()
   240  	}
   241  	return t1.Compare(t2) == types.CMPeq
   242  }
   243  
   244  // sortLoadStores sorts loadStores (Loads and Stores in block bb) into
   245  // program order, i.e. the order given by bb's store chain. This is needed
   246  // because there is no guarantee of their order in b.Values before the
   247  // schedule pass.
   248  //
   249  // memoryOrders is a per-block cache, populated on demand:
   250  // memoryOrders[b.ID][v.ID] is the position of the memory value v in b's
   251  // store chain, in even increments. Position 0 is the memory coming into
   252  // the block (InitMem, a memory Phi, or any memory defined outside bb);
   253  // each memory-producing value in bb (a Store, but also any other memory
   254  // generator such as a call) gets the position of its memory arg plus
   255  // two. A Load sorts at the position of its memory arg plus one - odd,
   256  // so after the value that produced that memory and before whatever
   257  // consumes it, which orders Stores before Loads of their output memory
   258  // with a plain integer comparison.
   259  func sortLoadStores(bb *ssa.Block, loadStores []*ssa.Value, memoryOrders map[ssa.ID]map[ssa.ID]int) []*ssa.Value {
   260  	memOrder, ok := memoryOrders[bb.ID]
   261  	if !ok {
   262  		memOrder = make(map[ssa.ID]int)
   263  		var computeDepth func(v *ssa.Value) int
   264  		computeDepth = func(v *ssa.Value) int {
   265  			if d, ok := memOrder[v.ID]; ok {
   266  				return d
   267  			}
   268  			// Starting point
   269  			if v.Block != bb || v.Op == ssaop.OpInitMem || v.Op == ssaop.OpPhi {
   270  				memOrder[v.ID] = 0
   271  				return 0
   272  			}
   273  			// Search backwards
   274  			d := computeDepth(v.MemoryArg()) + 2
   275  			memOrder[v.ID] = d
   276  			return d
   277  		}
   278  		for _, v := range bb.Values {
   279  			if v.Type.IsMemory() {
   280  				computeDepth(v)
   281  			}
   282  		}
   283  		memoryOrders[bb.ID] = memOrder
   284  	}
   285  	key := func(v *ssa.Value) int {
   286  		if v.Op == ssaop.OpLoad {
   287  			return memOrder[v.MemoryArg().ID] + 1
   288  		}
   289  		return memOrder[v.ID]
   290  	}
   291  	slices.SortFunc(loadStores, func(a, b *ssa.Value) int {
   292  		return key(a) - key(b)
   293  	})
   294  	return loadStores
   295  }
   296  
   297  func mem2reg(f *ssa.Func) {
   298  	changed := false
   299  	if base.Flag.N != 0 {
   300  		return
   301  	}
   302  	st := f.NewStats("mem2reg")
   303  
   304  	// Get demographics
   305  	demographics, localAddrs, uses := variableDemographics(f)
   306  	if uses == nil {
   307  		// No candidate variables; nothing to do.
   308  		return
   309  	}
   310  	defer uses.free(f)
   311  	memoryOrders := make(map[ssa.ID]map[ssa.ID]int)
   312  
   313  	// First, we need to group all LocalAddr/Addrs that point to the same variable name
   314  	// varGrouped[n] = all localAddrs that have n as their Aux field and have only load and stores.
   315  	varGrouped := make(map[*ir.Name][]*ssa.Value)
   316  	for _, v := range localAddrs {
   317  		// TODO: mem2reg currently only supports load and stores on the LocalAddr directly.
   318  		// However as a small step further it could also handle copy-derived addresses:
   319  		// OffPtr [0] LocalAddr
   320  		// Copy    LocalAddr
   321  		if d, ok := demographics[v.Aux]; !ok || !d.ls {
   322  			continue
   323  		}
   324  		n := v.Aux.(*ir.Name)
   325  		if n.Class != ir.PAUTO {
   326  			// Not handling params right now.
   327  			continue
   328  		}
   329  		varGrouped[n] = append(varGrouped[n], v)
   330  	}
   331  	namesOrdered := []*ir.Name{}
   332  	for n, vag := range varGrouped {
   333  		namesOrdered = append(namesOrdered, n)
   334  		slices.SortFunc(vag, func(a, b *ssa.Value) int { return int(a.ID - b.ID) })
   335  	}
   336  	slices.SortFunc(namesOrdered, func(a, b *ir.Name) int {
   337  		return int(varGrouped[a][0].ID - varGrouped[b][0].ID)
   338  	})
   339  	// Utility functions
   340  	removeStore := func(v *ssa.Value) {
   341  		changed = true
   342  		v.SetArgs1(v.MemoryArg())
   343  		v.Aux = nil
   344  		v.AuxInt = 0
   345  		v.Op = ssaop.OpCopy
   346  	}
   347  	// Mem2reg promotes memory accesses to ssa values, and these values originally come
   348  	// from named local variables. Let's keep this information to help the register allocator
   349  	// spilling. Like ssagen's state.addNamedValue, compiler-generated temporaries
   350  	// are not tracked.
   351  	addNamedValue := func(n *ir.Name, v *ssa.Value) {
   352  		if ir.IsAutoTmp(n) {
   353  			return
   354  		}
   355  		loc := ssa.LocalSlot{N: n, Type: n.Type(), Off: 0}
   356  		values, ok := f.NamedValues[loc]
   357  		if !ok {
   358  			f.Names = append(f.Names, loc)
   359  		}
   360  		f.NamedValues[loc] = append(values, v)
   361  	}
   362  	type loadCandidate struct {
   363  		l *ssa.Value // The load
   364  		v *ssa.Value // The value to replace the load
   365  		// if v needs to be reinterpreted to match l's type, the op required. OpInvalid otherwise.
   366  		// if l.Type != v.Type, this op must not be OpInvalid.
   367  		reinterpret ssaop.Op
   368  	}
   369  	replaceLoad := func(n *ir.Name, lc loadCandidate) {
   370  		changed = true
   371  		if lc.reinterpret == ssaop.OpInvalid {
   372  			if !copyCompatibleType(lc.l.Type, lc.v.Type) {
   373  				f.Fatalf("mem2reg: load is being replaced by a value of an incompatible type")
   374  			}
   375  			lc.l.SetArgs1(lc.v)
   376  		} else {
   377  			// TODO: if we want to be more cautious, check that the reinterpret op will
   378  			// actually make the type right.
   379  			lc.l.SetArgs1(lc.l.Block.NewValue1(lc.l.Pos, lc.reinterpret, lc.l.Type, lc.v))
   380  		}
   381  		lc.l.Aux = nil
   382  		lc.l.AuxInt = 0
   383  		lc.l.Op = ssaop.OpCopy
   384  		// lc.v is a stored value or a phi, both already named when recorded.
   385  		addNamedValue(n, lc.l)
   386  	}
   387  	// Now we should start the promotion
   388  	// Simple case one - all uses of v is within the same block.
   389  	storeCands := []*ssa.Value{}   // These stores are to be overwritten
   390  	loadCands := []loadCandidate{} // These loads are to be overwritten
   391  	vaUses := []*ssa.Value{}
   392  NextVar:
   393  	for _, n := range namesOrdered {
   394  		vag := varGrouped[n]
   395  		var block *ssa.Block
   396  		for _, va := range vag {
   397  			// Walk through all uses of v and check if they are within the same block
   398  			for _, use := range uses.of(va) {
   399  				if block == nil {
   400  					block = use.Block
   401  				}
   402  				if use.Block != block {
   403  					// Across control flow, needs DF and Phi.
   404  					continue NextVar
   405  				}
   406  			}
   407  		}
   408  		// The uses are all within the same block and are loads/stores.
   409  		storeCands = storeCands[:0]
   410  		loadCands = loadCands[:0]
   411  		vaUses = vaUses[:0]
   412  		for _, va := range vag {
   413  			vaUses = append(vaUses, uses.of(va)...)
   414  		}
   415  		vaUses = sortLoadStores(block, vaUses, memoryOrders)
   416  		var curV *ssa.Value // The current value of n.
   417  		for _, v := range vaUses {
   418  			switch v.Op {
   419  			case ssaop.OpLoad:
   420  				if curV == nil {
   421  					f.Fatalf("mem2reg sees a load from an auto variable before any store")
   422  				}
   423  				reinter := ssaop.OpInvalid
   424  				if !copyCompatibleType(v.Type, curV.Type) {
   425  					reinter = reinterpretOp(curV.Type, v.Type)
   426  					if reinter == ssaop.OpInvalid {
   427  						// Not something we can optimize, bailout the variable and
   428  						// continue to the next variable.
   429  						st.Record("incompatible types in single block case", 1)
   430  						delete(varGrouped, n)
   431  						continue NextVar
   432  					}
   433  				}
   434  				loadCands = append(loadCands, loadCandidate{
   435  					l:           v,
   436  					v:           curV,
   437  					reinterpret: reinter,
   438  				})
   439  			case ssaop.OpStore:
   440  				curV = v.Args[1]
   441  				storeCands = append(storeCands, v)
   442  			default:
   443  				f.Fatalf("should only has load or store uses")
   444  			}
   445  		}
   446  		// Do the replacement.
   447  		for _, v := range storeCands {
   448  			// Remove the stores, keeping the stored values named.
   449  			addNamedValue(n, v.Args[1])
   450  			removeStore(v)
   451  		}
   452  		for _, v := range demographics[n].varDefs {
   453  			// Also remove the VarDefs.
   454  			removeStore(v)
   455  		}
   456  		for _, lc := range loadCands {
   457  			// Replace the loads with the corresponding value.
   458  			replaceLoad(n, lc)
   459  		}
   460  		// The variable no longer has a memory footprint: all its loads, stores
   461  		// and VarDefs are gone, so its address is no longer taken anywhere.
   462  		// Unset its addrtaken flag.
   463  		n.SetAddrtaken(false)
   464  		// This var is done, remove it from varGrouped.
   465  		if f.Pass.Debug > 1 {
   466  			f.Warnl(n.Pos(), "promoted %v in single block case", n)
   467  		}
   468  		delete(varGrouped, n)
   469  		st.Record("promoted variable in single block case", 1)
   470  	}
   471  
   472  	if len(varGrouped) == 0 {
   473  		if changed {
   474  			deadcode(f)
   475  		}
   476  		return
   477  	}
   478  	// Cross-block promotion. The remaining variables have uses spanning
   479  	// multiple blocks, so promotion needs phi insertion. To keep deciding
   480  	// whether a variable can be promoted separate from performing the
   481  	// promotion, this proceeds in four phases; the first two only read
   482  	// the function, and the last two mutate it, so a variable rejected
   483  	// during deciding leaves no trace in the SSA:
   484  	//
   485  	// 1. Placement. For each variable n, collect the blocks that store
   486  	// to n and compute the iterated dominance frontier of that set
   487  	// (f.IterDomFrontierPlus): the blocks that need a phi for n. A
   488  	// variable whose def-block or phi-block count exceeds
   489  	// crossBlockBudget is dropped here.
   490  	//
   491  	// 2. Deciding. A renaming walk (renameWalk below) over the CFG
   492  	// simulates promotion without mutating the function: phis from
   493  	// phase 1 exist only as a sentinel value, and every Load is checked
   494  	// against the type of its reaching definition. A variable with an
   495  	// incompatible load lands in badNames and is dropped.
   496  	//
   497  	// 3. Phi creation. For the surviving variables, create the phis
   498  	// decided in phase 1 (with no arguments yet).
   499  	//
   500  	// 4. Applying. The same renaming walk, now over the real phis,
   501  	// records the phi arguments along each edge, the loads to replace
   502  	// and the stores to remove, and finalization applies them. Phis
   503  	// placed at blocks no definition reaches stay argument-less and
   504  	// unreferenced; the deadcode pass at the end of mem2reg removes
   505  	// them.
   506  
   507  	// crossBlockBudget caps both the number of def blocks and the number
   508  	// of phi insertions one variable may require.
   509  	// Tunable for experiments via -d=ssa/mem2reg/@crossblockbudget=<n>.
   510  	crossBlockBudget := f.Pass.Val("crossblockbudget", 20)
   511  
   512  	// Phase 1: placement.
   513  	phiBlocksByName := map[*ir.Name][]*ssa.Block{}
   514  	{
   515  		var seeds []*ssa.Block
   516  		seen := map[*ssa.Block]struct{}{}
   517  	PlacementLoop:
   518  		for _, n := range namesOrdered {
   519  			vag, ok := varGrouped[n]
   520  			if !ok {
   521  				continue
   522  			}
   523  			seeds = seeds[:0]
   524  			clear(seen)
   525  			for _, va := range vag {
   526  				for _, use := range uses.of(va) {
   527  					if use.Op != ssaop.OpStore {
   528  						continue
   529  					}
   530  					if _, dup := seen[use.Block]; dup {
   531  						continue
   532  					}
   533  					seen[use.Block] = struct{}{}
   534  					seeds = append(seeds, use.Block)
   535  					if int64(len(seeds)) >= crossBlockBudget {
   536  						// Too many def blocks, bail out.
   537  						st.Record("too many def blocks", 1)
   538  						delete(varGrouped, n)
   539  						continue PlacementLoop
   540  					}
   541  				}
   542  			}
   543  			// Sort for determinism: use-list order depends on the order
   544  			// defs were discovered, and phi placement order affects
   545  			// assigned ssa.Value IDs, which leak into compiler output.
   546  			slices.SortFunc(seeds, func(a, b *ssa.Block) int { return int(a.ID - b.ID) })
   547  			var phiBlocks []*ssa.Block
   548  			for y := range f.IterDomFrontierPlus(slices.Values(seeds)) {
   549  				if int64(len(phiBlocks)) >= crossBlockBudget {
   550  					// Too many phis, bail out.
   551  					st.Record("too many cascading def blocks", 1)
   552  					delete(varGrouped, n)
   553  					continue PlacementLoop
   554  				}
   555  				phiBlocks = append(phiBlocks, y)
   556  			}
   557  			phiBlocksByName[n] = phiBlocks
   558  		}
   559  	}
   560  
   561  	// virtualPhi stands in for a not-yet-created phi during the deciding
   562  	// walk. It must never be used as a real SSA value; its reaching type
   563  	// is the variable's own type.
   564  	virtualPhi := &ssa.Value{}
   565  
   566  	// changeLogEnt records the reaching definition of a variable right
   567  	// before a walk step overwrote it, so backtracking can restore it.
   568  	type changeLogEnt struct {
   569  		name      *ir.Name
   570  		valBefore *ssa.Value
   571  	}
   572  	// These names have access patterns that are not ok; they are decided
   573  	// against in phase 2 and skipped everywhere after.
   574  	badNames := map[*ir.Name]struct{}{}
   575  
   576  	// renameWalk is the renaming DFS shared by the deciding and applying
   577  	// phases. It traverses the CFG from the entry block; incomingV[n]
   578  	// tracks the reaching definition of n. On each Store to n the
   579  	// previous reaching definition is pushed onto a change log and
   580  	// overwritten with the stored value; when backtracking, the log is
   581  	// rewound to restore incomingV to the state at the branch point.
   582  	// At each block, phiAt(b, n) reports the phi for n in b (real, or
   583  	// virtualPhi while deciding, or nil): it becomes the new reaching
   584  	// definition, and onPhiArg records the value flowing in along the
   585  	// traversed edge. Loads are passed to onLoad with their reaching
   586  	// definition, and Stores to onStore before they become the new
   587  	// reaching definition; both report whether the walk should keep
   588  	// tracking the variable (false when they just decided against it).
   589  	renameWalk := func(
   590  		phiAt func(b *ssa.Block, n *ir.Name) *ssa.Value,
   591  		onPhiArg func(n *ir.Name, phi *ssa.Value, predIdx int, v *ssa.Value),
   592  		onLoad func(n *ir.Name, use, incoming *ssa.Value) bool,
   593  		onStore func(n *ir.Name, use *ssa.Value) bool,
   594  	) {
   595  		incomingV := map[*ir.Name]*ssa.Value{}
   596  		changeLog := []changeLogEnt{}
   597  		type work struct {
   598  			// e is the currently traversed edge; its predecessor index
   599  			// identifies the phi argument slot, its target the block.
   600  			e ssa.Edge
   601  			// changeLogSnapShot is the length of changeLog right after
   602  			// processing this work.
   603  			changeLogSnapShot int
   604  		}
   605  		worklist := []work{{ssa.Edge{B: f.Entry, I: -1}, 0}} // DFS list
   606  		visited := map[*ssa.Block]struct{}{}
   607  		for len(worklist) > 0 {
   608  			curWork := worklist[len(worklist)-1]
   609  			worklist = worklist[:len(worklist)-1]
   610  			// Undo changes until we reach the right snapshot.
   611  			for len(changeLog) > curWork.changeLogSnapShot {
   612  				curLog := changeLog[len(changeLog)-1]
   613  				changeLog = changeLog[:len(changeLog)-1]
   614  				incomingV[curLog.name] = curLog.valBefore
   615  			}
   616  			curB := curWork.e.B
   617  			// Process phis.
   618  			for _, n := range namesOrdered {
   619  				if _, ok := varGrouped[n]; !ok {
   620  					continue
   621  				}
   622  				if _, bad := badNames[n]; bad {
   623  					continue
   624  				}
   625  				phi := phiAt(curB, n)
   626  				if phi == nil {
   627  					continue
   628  				}
   629  				if curWork.e.I == -1 {
   630  					f.Fatalf("phi placed at entry in mem2reg")
   631  				}
   632  				if iV := incomingV[n]; iV != nil {
   633  					// At most one phi per name per block, so no need to
   634  					// check the status of type compatibility
   635  					onPhiArg(n, phi, curWork.e.I, iV)
   636  				}
   637  				changeLog = append(changeLog, changeLogEnt{n, incomingV[n]})
   638  				incomingV[n] = phi
   639  			}
   640  			// Process block values.
   641  			if _, ok := visited[curB]; ok {
   642  				continue
   643  			}
   644  			visited[curB] = struct{}{}
   645  		NameLoop:
   646  			for _, n := range namesOrdered {
   647  				vag, ok := varGrouped[n]
   648  				if !ok {
   649  					continue
   650  				}
   651  				if _, bad := badNames[n]; bad {
   652  					continue
   653  				}
   654  				vaUses := []*ssa.Value{}
   655  				for _, va := range vag {
   656  					for _, u := range uses.of(va) {
   657  						if u.Block == curB {
   658  							vaUses = append(vaUses, u)
   659  						}
   660  					}
   661  				}
   662  				vaUses = sortLoadStores(curB, vaUses, memoryOrders)
   663  				for _, use := range vaUses {
   664  					switch use.Op {
   665  					case ssaop.OpLoad:
   666  						if !onLoad(n, use, incomingV[n]) {
   667  							continue NameLoop
   668  						}
   669  					case ssaop.OpStore:
   670  						val := use.Args[1]
   671  						if !onStore(n, use) {
   672  							continue NameLoop
   673  						}
   674  						changeLog = append(changeLog, changeLogEnt{n, incomingV[n]})
   675  						incomingV[n] = val
   676  					default:
   677  						f.Fatalf("should not have uses other than load and store")
   678  					}
   679  				}
   680  			}
   681  			for _, e := range curB.Succs {
   682  				worklist = append(worklist, work{e, len(changeLog)})
   683  			}
   684  		}
   685  	}
   686  
   687  	// Phase 2: deciding. No mutation; phis exist only as virtualPhi.
   688  	{
   689  		phiBlockSet := map[*ir.Name]map[*ssa.Block]struct{}{}
   690  		for n, bs := range phiBlocksByName {
   691  			m := make(map[*ssa.Block]struct{}, len(bs))
   692  			for _, b := range bs {
   693  				m[b] = struct{}{}
   694  			}
   695  			phiBlockSet[n] = m
   696  		}
   697  		renameWalk(
   698  			// phiAt
   699  			func(b *ssa.Block, n *ir.Name) *ssa.Value {
   700  				if _, ok := phiBlockSet[n][b]; ok {
   701  					return virtualPhi
   702  				}
   703  				return nil
   704  			},
   705  			// onPhiArg
   706  			func(n *ir.Name, phi *ssa.Value, predIdx int, v *ssa.Value) {
   707  				t := v.Type
   708  				if v == virtualPhi {
   709  					t = n.Type()
   710  				}
   711  				if !copyCompatibleType(n.Type(), t) {
   712  					st.Record("incompatible phi and arg types in cross block cases", 1)
   713  					badNames[n] = struct{}{}
   714  				}
   715  			},
   716  			// onLoad
   717  			func(n *ir.Name, use, incoming *ssa.Value) bool {
   718  				if incoming == nil {
   719  					f.Fatalf("no incoming value for a load in mem2reg")
   720  				}
   721  				t := incoming.Type
   722  				if incoming == virtualPhi {
   723  					t = n.Type()
   724  				}
   725  				if !copyCompatibleType(use.Type, t) {
   726  					st.Record("incompatible types in cross block cases", 1)
   727  					badNames[n] = struct{}{}
   728  					return false
   729  				}
   730  				return true
   731  			},
   732  			// onStore
   733  			func(n *ir.Name, use *ssa.Value) bool {
   734  				if !copyCompatibleType(use.Args[1].Type, n.Type()) {
   735  					st.Record("incompatible store types in cross block cases", 1)
   736  					badNames[n] = struct{}{}
   737  					return false
   738  				}
   739  				return true
   740  			},
   741  		)
   742  	}
   743  
   744  	// Phase 3: create the phis for the surviving variables.
   745  	phiToName := map[*ssa.Value]*ir.Name{}
   746  	// newPhisByBlockByName[b.ID] = phis inserted in block b, keyed by name.
   747  	newPhisByBlockByName := make([]map[*ir.Name]*ssa.Value, f.NumBlocks())
   748  	for _, n := range namesOrdered {
   749  		if _, ok := varGrouped[n]; !ok {
   750  			continue
   751  		}
   752  		if _, bad := badNames[n]; bad {
   753  			continue
   754  		}
   755  		for _, y := range phiBlocksByName[n] {
   756  			if newPhisByBlockByName[y.ID] == nil {
   757  				newPhisByBlockByName[y.ID] = make(map[*ir.Name]*ssa.Value)
   758  			}
   759  			p := y.NewValue0(y.Pos, ssaop.OpPhi, n.Type())
   760  			changed = true
   761  			phiToName[p] = n
   762  			newPhisByBlockByName[y.ID][n] = p
   763  			for range len(y.Preds) {
   764  				// Use virtualPhi as a placeholder.
   765  				p.AddArg(virtualPhi)
   766  			}
   767  			addNamedValue(n, p)
   768  		}
   769  	}
   770  
   771  	// Phase 4: applying. The walk cannot fail anymore; record the
   772  	// rewrites and finalize.
   773  	renameWalk(
   774  		// phiAt
   775  		func(b *ssa.Block, n *ir.Name) *ssa.Value {
   776  			if m := newPhisByBlockByName[b.ID]; m != nil {
   777  				return m[n] // nil if b has no phi for n
   778  			}
   779  			return nil
   780  		},
   781  		// onPhiArg
   782  		func(n *ir.Name, phi *ssa.Value, predIdx int, v *ssa.Value) {
   783  			if !copyCompatibleType(n.Type(), v.Type) {
   784  				f.Fatalf("phi of %v decided promotable but has incompatible type", n)
   785  			}
   786  			phi.SetArg(predIdx, v)
   787  		},
   788  		// onLoad
   789  		func(n *ir.Name, use, incoming *ssa.Value) bool {
   790  			if incoming == nil {
   791  				f.Fatalf("no incoming value for a load in mem2reg")
   792  			}
   793  			if !copyCompatibleType(use.Type, incoming.Type) {
   794  				f.Fatalf("load of %v decided promotable but has incompatible type", n)
   795  			}
   796  			replaceLoad(n, loadCandidate{
   797  				l:           use,
   798  				v:           incoming,
   799  				reinterpret: ssaop.OpInvalid,
   800  			})
   801  			return true
   802  		},
   803  		// onStore
   804  		func(n *ir.Name, use *ssa.Value) bool {
   805  			val := use.Args[1]
   806  			if !copyCompatibleType(val.Type, n.Type()) {
   807  				f.Fatalf("store of %v decided promotable but has incompatible type", n)
   808  			}
   809  			removeStore(use)
   810  			addNamedValue(n, val)
   811  			return true
   812  		},
   813  	)
   814  	// The promoted variables' loads and stores are gone. Remove their VarDefs
   815  	// too, so that they no longer have any memory footprint, and unset their
   816  	// addrtaken flag, as their address is no longer taken anywhere.
   817  	// Iterate in namesOrdered order (not over the demographics map) to keep
   818  	// the debug output deterministic.
   819  	for _, n := range namesOrdered {
   820  		if _, ok := varGrouped[n]; !ok {
   821  			continue
   822  		}
   823  		if _, bad := badNames[n]; bad {
   824  			continue
   825  		}
   826  		n.SetAddrtaken(false)
   827  		for _, v := range demographics[n].varDefs {
   828  			// Remove the VarDefs.
   829  			removeStore(v)
   830  		}
   831  		// Also record the statistics for the names promoted
   832  		if f.Pass.Debug > 1 {
   833  			f.Warnl(n.Pos(), "promoted %v in cross block case", n)
   834  		}
   835  		st.Record("promoted variable in cross block cases", 1)
   836  	}
   837  
   838  	if changed {
   839  		deadcode(f)
   840  	}
   841  
   842  	// Sanity check, although deadcode might fatal away earlier if this happens?
   843  	if virtualPhi.Uses != 0 {
   844  		f.Fatalf("some new phis have incomplete arg lists")
   845  	}
   846  }
   847  

View as plain text