uses.go

     1  // Copyright 2025 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 "cmd/compile/internal/ssa"
     8  
     9  // useInfo provides a map from a value to the users of that value.
    10  // We do not keep track of this data in the IR directly, as it is
    11  // expensive to keep updated. But sometimes we need to compute it
    12  // temporarily.
    13  //
    14  // A useInfo is only valid until the next modification of the IR.
    15  //
    16  // Note that block control uses are not reported. (TODO: add
    17  // if needed.)
    18  // Also, index of use is not reported. (TODO: add if needed.)
    19  //
    20  // We keep track of all uses in a single array, and use a
    21  // starts array to tell us where to find the sub-array for
    22  // each value.
    23  //
    24  // For a function with 10 values, we would have:
    25  //
    26  //	starts[0]    starts[1]  starts[2] starts[9]   len(uses)
    27  //	    |            |            |     |            |
    28  //	    v            v            v     v            v
    29  //	    +------------+------------+-...-+------------+
    30  //	    | uses of v0 | uses of v1 | ... | uses of v9 |
    31  //	    +------------+------------+-...-+------------+
    32  //
    33  // We can find all the uses of v by listing all entries
    34  // of uses between starts[v.ID] and starts[v.ID+1].
    35  type useInfo struct {
    36  	starts []int32
    37  	uses   []*ssa.Value
    38  }
    39  
    40  // build useInfo for a function. Result only valid until
    41  // the next modification of f.
    42  func uses(f *ssa.Func) useInfo {
    43  	// Write down number of uses of each value.
    44  	idx := f.Cache.AllocInt32Slice(f.NumValues())
    45  	for _, b := range f.Blocks {
    46  		for _, v := range b.Values {
    47  			idx[v.ID] = v.Uses
    48  		}
    49  	}
    50  
    51  	// Compute cumulative sum of uses up to and
    52  	// including each value ID.
    53  	var cum int32
    54  	for vid, uses := range idx {
    55  		cum += uses
    56  		idx[vid] = cum
    57  	}
    58  
    59  	// Compute uses.
    60  	uses := f.Cache.AllocValueSlice(int(cum))
    61  	for _, b := range f.Blocks {
    62  		for _, v := range b.Values {
    63  			for _, a := range v.Args {
    64  				idx[a.ID]--
    65  				uses[idx[a.ID]] = v
    66  			}
    67  		}
    68  	}
    69  	for _, b := range f.Blocks {
    70  		for _, c := range b.ControlValues() {
    71  			// We don't track block control uses, but
    72  			// we have to decrement idx values here
    73  			// so that the accounting comes out right.
    74  			// Each value will have, at the start of its
    75  			// use list, a bunch of nils that represent
    76  			// the number of Block.Control uses.
    77  			idx[c.ID]--
    78  		}
    79  	}
    80  
    81  	// The loop above decremented each idx entry
    82  	// by the number of uses. It now contains
    83  	// the sum of uses up to, but not including,
    84  	// each value ID.
    85  	return useInfo{starts: idx, uses: uses}
    86  }
    87  
    88  // get returns a list of uses of v.
    89  // Every use in an argument slot is listed (e.g. for
    90  // w=(Add v v), w is listed twice in the uses of v).
    91  // Uses by Block.Controls are not reported.
    92  func (u useInfo) get(v *ssa.Value) []*ssa.Value {
    93  	i := u.starts[v.ID]
    94  	var j int32
    95  	if int(v.ID) < len(u.starts)-1 {
    96  		j = u.starts[v.ID+1]
    97  	} else {
    98  		j = int32(len(u.uses))
    99  	}
   100  	r := u.uses[i:j]
   101  	// skip nil entries from block control uses
   102  	for len(r) > 0 && r[0] == nil {
   103  		r = r[1:]
   104  	}
   105  	return r
   106  }
   107  
   108  func (u useInfo) free(f *ssa.Func) {
   109  	f.Cache.FreeInt32Slice(u.starts)
   110  	f.Cache.FreeValueSlice(u.uses)
   111  }
   112
View as plain text