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