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  // Overlaps returns true if here is any overlap between i and i2.
    71  func (i Interval) Overlaps(i2 Interval) bool {
    72  	return (min(i.en, i2.en) - max(i.st, i2.st)) > 0
    73  }
    74  
    75  // adjacent returns true if the start of one interval is equal to the
    76  // end of another interval (e.g. they represent consecutive ranges).
    77  func (i1 Interval) adjacent(i2 Interval) bool {
    78  	return i1.en == i2.st || i2.en == i1.st
    79  }
    80  
    81  // MergeInto merges interval i2 into i1. This version happens to
    82  // require that the two intervals either overlap or are adjacent.
    83  func (i1 *Interval) MergeInto(i2 Interval) error {
    84  	if !i1.Overlaps(i2) && !i1.adjacent(i2) {
    85  		return fmt.Errorf("merge method invoked on non-overlapping/non-adjacent")
    86  	}
    87  	i1.st = min(i1.st, i2.st)
    88  	i1.en = max(i1.en, i2.en)
    89  	return nil
    90  }
    91  
    92  // IntervalsBuilder is a helper for constructing intervals based on
    93  // live dataflow sets for a series of BBs where we're making a
    94  // backwards pass over each BB looking for uses and kills. The
    95  // expected use case is:
    96  //
    97  //   - invoke MakeIntervalsBuilder to create a new object "b"
    98  //   - series of calls to b.Live/b.Kill based on a backwards reverse layout
    99  //     order scan over instructions
   100  //   - invoke b.Finish() to produce final set
   101  //
   102  // See the Live method comment for an IR example.
   103  type IntervalsBuilder struct {
   104  	s Intervals
   105  	// index of last instruction visited plus 1
   106  	lidx int
   107  }
   108  
   109  func (c *IntervalsBuilder) last() int {
   110  	return c.lidx - 1
   111  }
   112  
   113  func (c *IntervalsBuilder) setLast(x int) {
   114  	c.lidx = x + 1
   115  }
   116  
   117  func (c *IntervalsBuilder) Finish() (Intervals, error) {
   118  	// Reverse intervals list and check.
   119  	slices.Reverse(c.s)
   120  	if err := check(c.s); err != nil {
   121  		return Intervals{}, err
   122  	}
   123  	r := c.s
   124  	return r, nil
   125  }
   126  
   127  // Live method should be invoked on instruction at position p if instr
   128  // contains an upwards-exposed use of a resource. See the example in
   129  // the comment at the beginning of this file for an example.
   130  func (c *IntervalsBuilder) Live(pos int) error {
   131  	if pos < 0 {
   132  		return fmt.Errorf("bad pos, negative")
   133  	}
   134  	if c.last() == -1 {
   135  		c.setLast(pos)
   136  		if debugtrace {
   137  			fmt.Fprintf(os.Stderr, "=-= begin lifetime at pos=%d\n", pos)
   138  		}
   139  		c.s = append(c.s, Interval{st: pos, en: pos + 1})
   140  		return nil
   141  	}
   142  	if pos >= c.last() {
   143  		return fmt.Errorf("pos not decreasing")
   144  	}
   145  	// extend lifetime across this pos
   146  	c.s[len(c.s)-1].st = pos
   147  	c.setLast(pos)
   148  	return nil
   149  }
   150  
   151  // Kill method should be invoked on instruction at position p if instr
   152  // should be treated as having a kill (lifetime end) for the
   153  // resource. See the example in the comment at the beginning of this
   154  // file for an example. Note that if we see a kill at position K for a
   155  // resource currently live since J, this will result in a lifetime
   156  // segment of [K+1,J+1), the assumption being that the first live
   157  // instruction will be the one after the kill position, not the kill
   158  // position itself.
   159  func (c *IntervalsBuilder) Kill(pos int) error {
   160  	if pos < 0 {
   161  		return fmt.Errorf("bad pos, negative")
   162  	}
   163  	if c.last() == -1 {
   164  		return nil
   165  	}
   166  	if pos >= c.last() {
   167  		return fmt.Errorf("pos not decreasing")
   168  	}
   169  	c.s[len(c.s)-1].st = pos + 1
   170  	// terminate lifetime
   171  	c.setLast(-1)
   172  	if debugtrace {
   173  		fmt.Fprintf(os.Stderr, "=-= term lifetime at pos=%d\n", pos)
   174  	}
   175  	return nil
   176  }
   177  
   178  // check examines the intervals in "is" to try to find internal
   179  // inconsistencies or problems.
   180  func check(is Intervals) error {
   181  	for i := 0; i < len(is); i++ {
   182  		st := is[i].st
   183  		en := is[i].en
   184  		if en <= st {
   185  			return fmt.Errorf("bad range elem %d:%d, en<=st", st, en)
   186  		}
   187  		if i == 0 {
   188  			continue
   189  		}
   190  		// check for badly ordered starts
   191  		pst := is[i-1].st
   192  		pen := is[i-1].en
   193  		if pst >= st {
   194  			return fmt.Errorf("range start not ordered %d:%d less than prev %d:%d", st, en,
   195  				pst, pen)
   196  		}
   197  		// check end of last range against start of this range
   198  		if pen > st {
   199  			return fmt.Errorf("bad range elem %d:%d overlaps prev %d:%d", st, en,
   200  				pst, pen)
   201  		}
   202  	}
   203  	return nil
   204  }
   205  
   206  func (is *Intervals) String() string {
   207  	var sb strings.Builder
   208  	for i := range *is {
   209  		if i != 0 {
   210  			sb.WriteString(" ")
   211  		}
   212  		sb.WriteString((*is)[i].String())
   213  	}
   214  	return sb.String()
   215  }
   216  
   217  // intWithIdx holds an interval i and an index pairIndex storing i's
   218  // position (either 0 or 1) within some previously specified interval
   219  // pair <I1,I2>; a pairIndex of -1 is used to signal "end of
   220  // iteration". Used for Intervals operations, not expected to be
   221  // exported.
   222  type intWithIdx struct {
   223  	i         Interval
   224  	pairIndex int
   225  }
   226  
   227  func (iwi intWithIdx) done() bool {
   228  	return iwi.pairIndex == -1
   229  }
   230  
   231  // pairVisitor provides a way to visit (iterate through) each interval
   232  // within a pair of Intervals in order of increasing start time. Expected
   233  // usage model:
   234  //
   235  //	func example(i1, i2 Intervals) {
   236  //	  var pairVisitor pv
   237  //	  cur := pv.init(i1, i2);
   238  //	  for !cur.done() {
   239  //	     fmt.Printf("interval %s from i%d", cur.i.String(), cur.pairIndex+1)
   240  //	     cur = pv.nxt()
   241  //	  }
   242  //	}
   243  //
   244  // Used internally for Intervals operations, not expected to be exported.
   245  type pairVisitor struct {
   246  	cur    intWithIdx
   247  	i1pos  int
   248  	i2pos  int
   249  	i1, i2 Intervals
   250  }
   251  
   252  // init initializes a pairVisitor for the specified pair of intervals
   253  // i1 and i2 and returns an intWithIdx object that points to the first
   254  // interval by start position within i1/i2.
   255  func (pv *pairVisitor) init(i1, i2 Intervals) intWithIdx {
   256  	pv.i1, pv.i2 = i1, i2
   257  	pv.cur = pv.sel()
   258  	return pv.cur
   259  }
   260  
   261  // nxt advances the pairVisitor to the next interval by starting
   262  // position within the pair, returning an intWithIdx that describes
   263  // the interval.
   264  func (pv *pairVisitor) nxt() intWithIdx {
   265  	if pv.cur.pairIndex == 0 {
   266  		pv.i1pos++
   267  	} else {
   268  		pv.i2pos++
   269  	}
   270  	pv.cur = pv.sel()
   271  	return pv.cur
   272  }
   273  
   274  // sel is a helper function used by 'init' and 'nxt' above; it selects
   275  // the earlier of the two intervals at the current positions within i1
   276  // and i2, or a degenerate (pairIndex -1) intWithIdx if we have no
   277  // more intervals to visit.
   278  func (pv *pairVisitor) sel() intWithIdx {
   279  	var c1, c2 intWithIdx
   280  	if pv.i1pos >= len(pv.i1) {
   281  		c1.pairIndex = -1
   282  	} else {
   283  		c1 = intWithIdx{i: pv.i1[pv.i1pos], pairIndex: 0}
   284  	}
   285  	if pv.i2pos >= len(pv.i2) {
   286  		c2.pairIndex = -1
   287  	} else {
   288  		c2 = intWithIdx{i: pv.i2[pv.i2pos], pairIndex: 1}
   289  	}
   290  	if c1.pairIndex == -1 {
   291  		return c2
   292  	}
   293  	if c2.pairIndex == -1 {
   294  		return c1
   295  	}
   296  	if c1.i.st <= c2.i.st {
   297  		return c1
   298  	}
   299  	return c2
   300  }
   301  
   302  // Overlaps returns whether any of the component ranges in is overlaps
   303  // with some range in is2.
   304  func (is Intervals) Overlaps(is2 Intervals) bool {
   305  	// check for empty intervals
   306  	if len(is) == 0 || len(is2) == 0 {
   307  		return false
   308  	}
   309  	li := len(is)
   310  	li2 := len(is2)
   311  	// check for completely disjoint ranges
   312  	if is[li-1].en <= is2[0].st ||
   313  		is[0].st >= is2[li2-1].en {
   314  		return false
   315  	}
   316  	// walk the combined sets of intervals and check for piecewise
   317  	// overlap.
   318  	var pv pairVisitor
   319  	first := pv.init(is, is2)
   320  	for {
   321  		second := pv.nxt()
   322  		if second.done() {
   323  			break
   324  		}
   325  		if first.pairIndex == second.pairIndex {
   326  			first = second
   327  			continue
   328  		}
   329  		if first.i.Overlaps(second.i) {
   330  			return true
   331  		}
   332  		first = second
   333  	}
   334  	return false
   335  }
   336  
   337  // Merge combines the intervals from "is" and "is2" and returns
   338  // a new Intervals object containing all combined ranges from the
   339  // two inputs.
   340  func (is Intervals) Merge(is2 Intervals) Intervals {
   341  	if len(is) == 0 {
   342  		return is2
   343  	} else if len(is2) == 0 {
   344  		return is
   345  	}
   346  	// walk the combined set of intervals and merge them together.
   347  	var ret Intervals
   348  	var pv pairVisitor
   349  	cur := pv.init(is, is2)
   350  	for {
   351  		second := pv.nxt()
   352  		if second.done() {
   353  			break
   354  		}
   355  
   356  		// Check for overlap between cur and second. If no overlap
   357  		// then add cur to result and move on.
   358  		if !cur.i.Overlaps(second.i) && !cur.i.adjacent(second.i) {
   359  			ret = append(ret, cur.i)
   360  			cur = second
   361  			continue
   362  		}
   363  		// cur overlaps with second; merge second into cur
   364  		cur.i.MergeInto(second.i)
   365  	}
   366  	ret = append(ret, cur.i)
   367  	return ret
   368  }
   369
View as plain text