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