intervals.go

     1  // Copyright 2024 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 liveness
     6  
     7  // This file defines an "Intervals" helper type that stores a
     8  // sorted sequence of disjoint ranges or intervals. An Intervals
     9  // example: { [0,5) [9-12) [100,101) }, which corresponds to the
    10  // numbers 0-4, 9-11, and 100. Once an Intervals object is created, it
    11  // can be tested to see if it has any overlap with another Intervals
    12  // object, or it can be merged with another Intervals object to form a
    13  // union of the two.
    14  //
    15  // The intended use case for this helper is in describing object or
    16  // variable lifetime ranges within a linearized program representation
    17  // where each IR instruction has a slot or index. Example:
    18  //
    19  //          b1:
    20  //  0        VarDef abc
    21  //  1        memset(abc,0)
    22  //  2        VarDef xyz
    23  //  3        memset(xyz,0)
    24  //  4        abc.f1 = 2
    25  //  5        xyz.f3 = 9
    26  //  6        if q goto B4
    27  //  7 B3:    z = xyz.x
    28  //  8        goto B5
    29  //  9 B4:    z = abc.x
    30  //           // fallthrough
    31  // 10 B5:    z++
    32  //
    33  // To describe the lifetime of the variables above we might use these
    34  // intervals:
    35  //
    36  //    "abc"   [1,7), [9,10)
    37  //    "xyz"   [3,8)
    38  //
    39  // Clients can construct an Intervals object from a given IR sequence
    40  // using the "IntervalsBuilder" helper abstraction (one builder per
    41  // candidate variable), by making a
    42  // backwards sweep and invoking the Live/Kill methods to note the
    43  // starts and end of a given lifetime. For the example above, we would
    44  // expect to see this sequence of calls to Live/Kill:
    45  //
    46  //    abc:  Live(9), Kill(8), Live(6), Kill(0)
    47  //    xyz:  Live(8), Kill(2)
    48  
    49  import (
    50  	"fmt"
    51  	"os"
    52  	"slices"
    53  	"strings"
    54  )
    55  
    56  const debugtrace = false
    57  
    58  // Interval hols the range [st,en).
    59  type Interval struct {
    60  	st, en int
    61  }
    62  
    63  // Intervals is a sequence of sorted, disjoint intervals.
    64  type Intervals []Interval
    65  
    66  func (i Interval) String() string {
    67  	return fmt.Sprintf("[%d,%d)", i.st, i.en)
    68  }
    69  
    70  // TEMPORARY until bootstrap version catches up.
    71  func imin(i, j int) int {
    72  	if i < j {
    73  		return i
    74  	}
    75  	return j
    76  }
    77  
    78  // TEMPORARY until bootstrap version catches up.
    79  func imax(i, j int) int {
    80  	if i > j {
    81  		return i
    82  	}
    83  	return j
    84  }
    85  
    86  // Overlaps returns true if here is any overlap between i and i2.
    87  func (i Interval) Overlaps(i2 Interval) bool {
    88  	return (imin(i.en, i2.en) - imax(i.st, i2.st)) > 0
    89  }
    90  
    91  // adjacent returns true if the start of one interval is equal to the
    92  // end of another interval (e.g. they represent consecutive ranges).
    93  func (i1 Interval) adjacent(i2 Interval) bool {
    94  	return i1.en == i2.st || i2.en == i1.st
    95  }
    96  
    97  // MergeInto merges interval i2 into i1. This version happens to
    98  // require that the two intervals either overlap or are adjacent.
    99  func (i1 *Interval) MergeInto(i2 Interval) error {
   100  	if !i1.Overlaps(i2) && !i1.adjacent(i2) {
   101  		return fmt.Errorf("merge method invoked on non-overlapping/non-adjacent")
   102  	}
   103  	i1.st = imin(i1.st, i2.st)
   104  	i1.en = imax(i1.en, i2.en)
   105  	return nil
   106  }
   107  
   108  // IntervalsBuilder is a helper for constructing intervals based on
   109  // live dataflow sets for a series of BBs where we're making a
   110  // backwards pass over each BB looking for uses and kills. The
   111  // expected use case is:
   112  //
   113  //   - invoke MakeIntervalsBuilder to create a new object "b"
   114  //   - series of calls to b.Live/b.Kill based on a backwards reverse layout
   115  //     order scan over instructions
   116  //   - invoke b.Finish() to produce final set
   117  //
   118  // See the Live method comment for an IR example.
   119  type IntervalsBuilder struct {
   120  	s Intervals
   121  	// index of last instruction visited plus 1
   122  	lidx int
   123  }
   124  
   125  func (c *IntervalsBuilder) last() int {
   126  	return c.lidx - 1
   127  }
   128  
   129  func (c *IntervalsBuilder) setLast(x int) {
   130  	c.lidx = x + 1
   131  }
   132  
   133  func (c *IntervalsBuilder) Finish() (Intervals, error) {
   134  	// Reverse intervals list and check.
   135  	slices.Reverse(c.s)
   136  	if err := check(c.s); err != nil {
   137  		return Intervals{}, err
   138  	}
   139  	r := c.s
   140  	return r, nil
   141  }
   142  
   143  // Live method should be invoked on instruction at position p if instr
   144  // contains an upwards-exposed use of a resource. See the example in
   145  // the comment at the beginning of this file for an example.
   146  func (c *IntervalsBuilder) Live(pos int) error {
   147  	if pos < 0 {
   148  		return fmt.Errorf("bad pos, negative")
   149  	}
   150  	if c.last() == -1 {
   151  		c.setLast(pos)
   152  		if debugtrace {
   153  			fmt.Fprintf(os.Stderr, "=-= begin lifetime at pos=%d\n", pos)
   154  		}
   155  		c.s = append(c.s, Interval{st: pos, en: pos + 1})
   156  		return nil
   157  	}
   158  	if pos >= c.last() {
   159  		return fmt.Errorf("pos not decreasing")
   160  	}
   161  	// extend lifetime across this pos
   162  	c.s[len(c.s)-1].st = pos
   163  	c.setLast(pos)
   164  	return nil
   165  }
   166  
   167  // Kill method should be invoked on instruction at position p if instr
   168  // should be treated as having a kill (lifetime end) for the
   169  // resource. See the example in the comment at the beginning of this
   170  // file for an example. Note that if we see a kill at position K for a
   171  // resource currently live since J, this will result in a lifetime
   172  // segment of [K+1,J+1), the assumption being that the first live
   173  // instruction will be the one after the kill position, not the kill
   174  // position itself.
   175  func (c *IntervalsBuilder) Kill(pos int) error {
   176  	if pos < 0 {
   177  		return fmt.Errorf("bad pos, negative")
   178  	}
   179  	if c.last() == -1 {
   180  		return nil
   181  	}
   182  	if pos >= c.last() {
   183  		return fmt.Errorf("pos not decreasing")
   184  	}
   185  	c.s[len(c.s)-1].st = pos + 1
   186  	// terminate lifetime
   187  	c.setLast(-1)
   188  	if debugtrace {
   189  		fmt.Fprintf(os.Stderr, "=-= term lifetime at pos=%d\n", pos)
   190  	}
   191  	return nil
   192  }
   193  
   194  // check examines the intervals in "is" to try to find internal
   195  // inconsistencies or problems.
   196  func check(is Intervals) error {
   197  	for i := 0; i < len(is); i++ {
   198  		st := is[i].st
   199  		en := is[i].en
   200  		if en <= st {
   201  			return fmt.Errorf("bad range elem %d:%d, en<=st", st, en)
   202  		}
   203  		if i == 0 {
   204  			continue
   205  		}
   206  		// check for badly ordered starts
   207  		pst := is[i-1].st
   208  		pen := is[i-1].en
   209  		if pst >= st {
   210  			return fmt.Errorf("range start not ordered %d:%d less than prev %d:%d", st, en,
   211  				pst, pen)
   212  		}
   213  		// check end of last range against start of this range
   214  		if pen > st {
   215  			return fmt.Errorf("bad range elem %d:%d overlaps prev %d:%d", st, en,
   216  				pst, pen)
   217  		}
   218  	}
   219  	return nil
   220  }
   221  
   222  func (is *Intervals) String() string {
   223  	var sb strings.Builder
   224  	for i := range *is {
   225  		if i != 0 {
   226  			sb.WriteString(" ")
   227  		}
   228  		sb.WriteString((*is)[i].String())
   229  	}
   230  	return sb.String()
   231  }
   232  
   233  // intWithIdx holds an interval i and an index pairIndex storing i's
   234  // position (either 0 or 1) within some previously specified interval
   235  // pair <I1,I2>; a pairIndex of -1 is used to signal "end of
   236  // iteration". Used for Intervals operations, not expected to be
   237  // exported.
   238  type intWithIdx struct {
   239  	i         Interval
   240  	pairIndex int
   241  }
   242  
   243  func (iwi intWithIdx) done() bool {
   244  	return iwi.pairIndex == -1
   245  }
   246  
   247  // pairVisitor provides a way to visit (iterate through) each interval
   248  // within a pair of Intervals in order of increasing start time. Expected
   249  // usage model:
   250  //
   251  //	func example(i1, i2 Intervals) {
   252  //	  var pairVisitor pv
   253  //	  cur := pv.init(i1, i2);
   254  //	  for !cur.done() {
   255  //	     fmt.Printf("interval %s from i%d", cur.i.String(), cur.pairIndex+1)
   256  //	     cur = pv.nxt()
   257  //	  }
   258  //	}
   259  //
   260  // Used internally for Intervals operations, not expected to be exported.
   261  type pairVisitor struct {
   262  	cur    intWithIdx
   263  	i1pos  int
   264  	i2pos  int
   265  	i1, i2 Intervals
   266  }
   267  
   268  // init initializes a pairVisitor for the specified pair of intervals
   269  // i1 and i2 and returns an intWithIdx object that points to the first
   270  // interval by start position within i1/i2.
   271  func (pv *pairVisitor) init(i1, i2 Intervals) intWithIdx {
   272  	pv.i1, pv.i2 = i1, i2
   273  	pv.cur = pv.sel()
   274  	return pv.cur
   275  }
   276  
   277  // nxt advances the pairVisitor to the next interval by starting
   278  // position within the pair, returning an intWithIdx that describes
   279  // the interval.
   280  func (pv *pairVisitor) nxt() intWithIdx {
   281  	if pv.cur.pairIndex == 0 {
   282  		pv.i1pos++
   283  	} else {
   284  		pv.i2pos++
   285  	}
   286  	pv.cur = pv.sel()
   287  	return pv.cur
   288  }
   289  
   290  // sel is a helper function used by 'init' and 'nxt' above; it selects
   291  // the earlier of the two intervals at the current positions within i1
   292  // and i2, or a degenerate (pairIndex -1) intWithIdx if we have no
   293  // more intervals to visit.
   294  func (pv *pairVisitor) sel() intWithIdx {
   295  	var c1, c2 intWithIdx
   296  	if pv.i1pos >= len(pv.i1) {
   297  		c1.pairIndex = -1
   298  	} else {
   299  		c1 = intWithIdx{i: pv.i1[pv.i1pos], pairIndex: 0}
   300  	}
   301  	if pv.i2pos >= len(pv.i2) {
   302  		c2.pairIndex = -1
   303  	} else {
   304  		c2 = intWithIdx{i: pv.i2[pv.i2pos], pairIndex: 1}
   305  	}
   306  	if c1.pairIndex == -1 {
   307  		return c2
   308  	}
   309  	if c2.pairIndex == -1 {
   310  		return c1
   311  	}
   312  	if c1.i.st <= c2.i.st {
   313  		return c1
   314  	}
   315  	return c2
   316  }
   317  
   318  // Overlaps returns whether any of the component ranges in is overlaps
   319  // with some range in is2.
   320  func (is Intervals) Overlaps(is2 Intervals) bool {
   321  	// check for empty intervals
   322  	if len(is) == 0 || len(is2) == 0 {
   323  		return false
   324  	}
   325  	li := len(is)
   326  	li2 := len(is2)
   327  	// check for completely disjoint ranges
   328  	if is[li-1].en <= is2[0].st ||
   329  		is[0].st >= is2[li2-1].en {
   330  		return false
   331  	}
   332  	// walk the combined sets of intervals and check for piecewise
   333  	// overlap.
   334  	var pv pairVisitor
   335  	first := pv.init(is, is2)
   336  	for {
   337  		second := pv.nxt()
   338  		if second.done() {
   339  			break
   340  		}
   341  		if first.pairIndex == second.pairIndex {
   342  			first = second
   343  			continue
   344  		}
   345  		if first.i.Overlaps(second.i) {
   346  			return true
   347  		}
   348  		first = second
   349  	}
   350  	return false
   351  }
   352  
   353  // Merge combines the intervals from "is" and "is2" and returns
   354  // a new Intervals object containing all combined ranges from the
   355  // two inputs.
   356  func (is Intervals) Merge(is2 Intervals) Intervals {
   357  	if len(is) == 0 {
   358  		return is2
   359  	} else if len(is2) == 0 {
   360  		return is
   361  	}
   362  	// walk the combined set of intervals and merge them together.
   363  	var ret Intervals
   364  	var pv pairVisitor
   365  	cur := pv.init(is, is2)
   366  	for {
   367  		second := pv.nxt()
   368  		if second.done() {
   369  			break
   370  		}
   371  
   372  		// Check for overlap between cur and second. If no overlap
   373  		// then add cur to result and move on.
   374  		if !cur.i.Overlaps(second.i) && !cur.i.adjacent(second.i) {
   375  			ret = append(ret, cur.i)
   376  			cur = second
   377  			continue
   378  		}
   379  		// cur overlaps with second; merge second into cur
   380  		cur.i.MergeInto(second.i)
   381  	}
   382  	ret = append(ret, cur.i)
   383  	return ret
   384  }
   385
View as plain text