src/cmd/compile/internal/liveness/intervals.go - go - Git at Google

 // Copyright 2024 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package liveness

 // This file defines an "Intervals" helper type that stores a
 // sorted sequence of disjoint ranges or intervals. An Intervals
 // example: { [0,5) [9-12) [100,101) }, which corresponds to the
 // numbers 0-4, 9-11, and 100. Once an Intervals object is created, it
 // can be tested to see if it has any overlap with another Intervals
 // object, or it can be merged with another Intervals object to form a
 // union of the two.
 //
 // The intended use case for this helper is in describing object or
 // variable lifetime ranges within a linearized program representation
 // where each IR instruction has a slot or index. Example:
 //
 //          b1:
 //  0        VarDef abc
 //  1        memset(abc,0)
 //  2        VarDef xyz
 //  3        memset(xyz,0)
 //  4        abc.f1 = 2
 //  5        xyz.f3 = 9
 //  6        if q goto B4
 //  7 B3:    z = xyz.x
 //  8        goto B5
 //  9 B4:    z = abc.x
 //           // fallthrough
 // 10 B5:    z++
 //
 // To describe the lifetime of the variables above we might use these
 // intervals:
 //
 //    "abc"   [1,7), [9,10)
 //    "xyz"   [3,8)
 //
 // Clients can construct an Intervals object from a given IR sequence
 // using the "IntervalsBuilder" helper abstraction (one builder per
 // candidate variable), by making a
 // backwards sweep and invoking the Live/Kill methods to note the
 // starts and end of a given lifetime. For the example above, we would
 // expect to see this sequence of calls to Live/Kill:
 //
 //    abc:  Live(9), Kill(8), Live(6), Kill(0)
 //    xyz:  Live(8), Kill(2)

 import (
 	"fmt"
 	"os"
 	"strings"
 )

 const debugtrace = false

 // Interval hols the range [st,en).
 type Interval struct {
 	st, en int
 }

 // Intervals is a sequence of sorted, disjoint intervals.
 type Intervals []Interval

 func (i Interval) String() string {
 	return fmt.Sprintf("[%d,%d)", i.st, i.en)
 }

 // TEMPORARY until bootstrap version catches up.
 func imin(i, j int) int {
 	if i < j {
 		return i
 	}
 	return j
 }

 // TEMPORARY until bootstrap version catches up.
 func imax(i, j int) int {
 	if i > j {
 		return i
 	}
 	return j
 }

 // Overlaps returns true if here is any overlap between i and i2.
 func (i Interval) Overlaps(i2 Interval) bool {
 	return (imin(i.en, i2.en) - imax(i.st, i2.st)) > 0
 }

 // adjacent returns true if the start of one interval is equal to the
 // end of another interval (e.g. they represent consecutive ranges).
 func (i1 Interval) adjacent(i2 Interval) bool {
 	return i1.en == i2.st || i2.en == i1.st
 }

 // MergeInto merges interval i2 into i1. This version happens to
 // require that the two intervals either overlap or are adjacent.
 func (i1 *Interval) MergeInto(i2 Interval) error {
 	if !i1.Overlaps(i2) && !i1.adjacent(i2) {
 		return fmt.Errorf("merge method invoked on non-overlapping/non-adjacent")
 	}
 	i1.st = imin(i1.st, i2.st)
 	i1.en = imax(i1.en, i2.en)
 	return nil
 }

 // IntervalsBuilder is a helper for constructing intervals based on
 // live dataflow sets for a series of BBs where we're making a
 // backwards pass over each BB looking for uses and kills. The
 // expected use case is:
 //
 //   - invoke MakeIntervalsBuilder to create a new object "b"
 //   - series of calls to b.Live/b.Kill based on a backwards reverse layout
 //     order scan over instructions
 //   - invoke b.Finish() to produce final set
 //
 // See the Live method comment for an IR example.
 type IntervalsBuilder struct {
 	s Intervals
 	// index of last instruction visited plus 1
 	lidx int
 }

 func (c *IntervalsBuilder) last() int {
 	return c.lidx - 1
 }

 func (c *IntervalsBuilder) setLast(x int) {
 	c.lidx = x + 1
 }

 func (c *IntervalsBuilder) Finish() (Intervals, error) {
 	// Reverse intervals list and check.
 	// FIXME: replace with slices.Reverse once the
 	// bootstrap version supports it.
 	for i, j := 0, len(c.s)-1; i < j; i, j = i+1, j-1 {
 		c.s[i], c.s[j] = c.s[j], c.s[i]
 	}
 	if err := check(c.s); err != nil {
 		return Intervals{}, err
 	}
 	r := c.s
 	return r, nil
 }

 // Live method should be invoked on instruction at position p if instr
 // contains an upwards-exposed use of a resource. See the example in
 // the comment at the beginning of this file for an example.
 func (c *IntervalsBuilder) Live(pos int) error {
 	if pos < 0 {
 		return fmt.Errorf("bad pos, negative")
 	}
 	if c.last() == -1 {
 		c.setLast(pos)
 		if debugtrace {
 			fmt.Fprintf(os.Stderr, "=-= begin lifetime at pos=%d\n", pos)
 		}
 		c.s = append(c.s, Interval{st: pos, en: pos + 1})
 		return nil
 	}
 	if pos >= c.last() {
 		return fmt.Errorf("pos not decreasing")
 	}
 	// extend lifetime across this pos
 	c.s[len(c.s)-1].st = pos
 	c.setLast(pos)
 	return nil
 }

 // Kill method should be invoked on instruction at position p if instr
 // should be treated as as having a kill (lifetime end) for the
 // resource. See the example in the comment at the beginning of this
 // file for an example. Note that if we see a kill at position K for a
 // resource currently live since J, this will result in a lifetime
 // segment of [K+1,J+1), the assumption being that the first live
 // instruction will be the one after the kill position, not the kill
 // position itself.
 func (c *IntervalsBuilder) Kill(pos int) error {
 	if pos < 0 {
 		return fmt.Errorf("bad pos, negative")
 	}
 	if c.last() == -1 {
 		return nil
 	}
 	if pos >= c.last() {
 		return fmt.Errorf("pos not decreasing")
 	}
 	c.s[len(c.s)-1].st = pos + 1
 	// terminate lifetime
 	c.setLast(-1)
 	if debugtrace {
 		fmt.Fprintf(os.Stderr, "=-= term lifetime at pos=%d\n", pos)
 	}
 	return nil
 }

 // check examines the intervals in "is" to try to find internal
 // inconsistencies or problems.
 func check(is Intervals) error {
 	for i := 0; i < len(is); i++ {
 		st := is[i].st
 		en := is[i].en
 		if en <= st {
 			return fmt.Errorf("bad range elem %d:%d, en<=st", st, en)
 		}
 		if i == 0 {
 			continue
 		}
 		// check for badly ordered starts
 		pst := is[i-1].st
 		pen := is[i-1].en
 		if pst >= st {
 			return fmt.Errorf("range start not ordered %d:%d less than prev %d:%d", st, en,
 				pst, pen)
 		}
 		// check end of last range against start of this range
 		if pen > st {
 			return fmt.Errorf("bad range elem %d:%d overlaps prev %d:%d", st, en,
 				pst, pen)
 		}
 	}
 	return nil
 }

 func (is *Intervals) String() string {
 	var sb strings.Builder
 	for i := range *is {
 		if i != 0 {
 			sb.WriteString(" ")
 		}
 		sb.WriteString((*is)[i].String())
 	}
 	return sb.String()
 }

 // intWithIdx holds an interval i and an index pairIndex storing i's
 // position (either 0 or 1) within some previously specified interval
 // pair <I1,I2>; a pairIndex of -1 is used to signal "end of
 // iteration". Used for Intervals operations, not expected to be
 // exported.
 type intWithIdx struct {
 	i         Interval
 	pairIndex int
 }

 func (iwi intWithIdx) done() bool {
 	return iwi.pairIndex == -1
 }

 // pairVisitor provides a way to visit (iterate through) each interval
 // within a pair of Intervals in order of increasing start time. Expected
 // usage model:
 //
 //	func example(i1, i2 Intervals) {
 //	  var pairVisitor pv
 //	  cur := pv.init(i1, i2);
 //	  for !cur.done() {
 //	     fmt.Printf("interval %s from i%d", cur.i.String(), cur.pairIndex+1)
 //	     cur = pv.nxt()
 //	  }
 //	}
 //
 // Used internally for Intervals operations, not expected to be exported.
 type pairVisitor struct {
 	cur    intWithIdx
 	i1pos  int
 	i2pos  int
 	i1, i2 Intervals
 }

 // init initializes a pairVisitor for the specified pair of intervals
 // i1 and i2 and returns an intWithIdx object that points to the first
 // interval by start position within i1/i2.
 func (pv *pairVisitor) init(i1, i2 Intervals) intWithIdx {
 	pv.i1, pv.i2 = i1, i2
 	pv.cur = pv.sel()
 	return pv.cur
 }

 // nxt advances the pairVisitor to the next interval by starting
 // position within the pair, returning an intWithIdx that describes
 // the interval.
 func (pv *pairVisitor) nxt() intWithIdx {
 	if pv.cur.pairIndex == 0 {
 		pv.i1pos++
 	} else {
 		pv.i2pos++
 	}
 	pv.cur = pv.sel()
 	return pv.cur
 }

 // sel is a helper function used by 'init' and 'nxt' above; it selects
 // the earlier of the two intervals at the current positions within i1
 // and i2, or a degenerate (pairIndex -1) intWithIdx if we have no
 // more intervals to visit.
 func (pv *pairVisitor) sel() intWithIdx {
 	var c1, c2 intWithIdx
 	if pv.i1pos >= len(pv.i1) {
 		c1.pairIndex = -1
 	} else {
 		c1 = intWithIdx{i: pv.i1[pv.i1pos], pairIndex: 0}
 	}
 	if pv.i2pos >= len(pv.i2) {
 		c2.pairIndex = -1
 	} else {
 		c2 = intWithIdx{i: pv.i2[pv.i2pos], pairIndex: 1}
 	}
 	if c1.pairIndex == -1 {
 		return c2
 	}
 	if c2.pairIndex == -1 {
 		return c1
 	}
 	if c1.i.st <= c2.i.st {
 		return c1
 	}
 	return c2
 }

 // Overlaps returns whether any of the component ranges in is overlaps
 // with some range in is2.
 func (is Intervals) Overlaps(is2 Intervals) bool {
 	// check for empty intervals
 	if len(is) == 0 || len(is2) == 0 {
 		return false
 	}
 	li := len(is)
 	li2 := len(is2)
 	// check for completely disjoint ranges
 	if is[li-1].en <= is2[0].st ||
 		is[0].st >= is2[li2-1].en {
 		return false
 	}
 	// walk the combined sets of intervals and check for piecewise
 	// overlap.
 	var pv pairVisitor
 	first := pv.init(is, is2)
 	for {
 		second := pv.nxt()
 		if second.done() {
 			break
 		}
 		if first.pairIndex == second.pairIndex {
 			first = second
 			continue
 		}
 		if first.i.Overlaps(second.i) {
 			return true
 		}
 		first = second
 	}
 	return false
 }

 // Merge combines the intervals from "is" and "is2" and returns
 // a new Intervals object containing all combined ranges from the
 // two inputs.
 func (is Intervals) Merge(is2 Intervals) Intervals {
 	if len(is) == 0 {
 		return is2
 	} else if len(is2) == 0 {
 		return is
 	}
 	// walk the combined set of intervals and merge them together.
 	var ret Intervals
 	var pv pairVisitor
 	cur := pv.init(is, is2)
 	for {
 		second := pv.nxt()
 		if second.done() {
 			break
 		}

 		// Check for overlap between cur and second. If no overlap
 		// then add cur to result and move on.
 		if !cur.i.Overlaps(second.i) && !cur.i.adjacent(second.i) {
 			ret = append(ret, cur.i)
 			cur = second
 			continue
 		}
 		// cur overlaps with second; merge second into cur
 		cur.i.MergeInto(second.i)
 	}
 	ret = append(ret, cur.i)
 	return ret
 }
	// Copyright 2024 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package liveness

	// This file defines an "Intervals" helper type that stores a
	// sorted sequence of disjoint ranges or intervals. An Intervals
	// example: { [0,5) [9-12) [100,101) }, which corresponds to the
	// numbers 0-4, 9-11, and 100. Once an Intervals object is created, it
	// can be tested to see if it has any overlap with another Intervals
	// object, or it can be merged with another Intervals object to form a
	// union of the two.
	//
	// The intended use case for this helper is in describing object or
	// variable lifetime ranges within a linearized program representation
	// where each IR instruction has a slot or index. Example:
	//
	// b1:
	// 0 VarDef abc
	// 1 memset(abc,0)
	// 2 VarDef xyz
	// 3 memset(xyz,0)
	// 4 abc.f1 = 2
	// 5 xyz.f3 = 9
	// 6 if q goto B4
	// 7 B3: z = xyz.x
	// 8 goto B5
	// 9 B4: z = abc.x
	// // fallthrough
	// 10 B5: z++
	//
	// To describe the lifetime of the variables above we might use these
	// intervals:
	//
	// "abc" [1,7), [9,10)
	// "xyz" [3,8)
	//
	// Clients can construct an Intervals object from a given IR sequence
	// using the "IntervalsBuilder" helper abstraction (one builder per
	// candidate variable), by making a
	// backwards sweep and invoking the Live/Kill methods to note the
	// starts and end of a given lifetime. For the example above, we would
	// expect to see this sequence of calls to Live/Kill:
	//
	// abc: Live(9), Kill(8), Live(6), Kill(0)
	// xyz: Live(8), Kill(2)

	import (
	"fmt"
	"os"
	"strings"
	)

	const debugtrace = false

	// Interval hols the range [st,en).
	type Interval struct {
	st, en int
	}

	// Intervals is a sequence of sorted, disjoint intervals.
	type Intervals []Interval

	func (i Interval) String() string {
	return fmt.Sprintf("[%d,%d)", i.st, i.en)
	}

	// TEMPORARY until bootstrap version catches up.
	func imin(i, j int) int {
	if i < j {
	return i
	}
	return j
	}

	// TEMPORARY until bootstrap version catches up.
	func imax(i, j int) int {
	if i > j {
	return i
	}
	return j
	}

	// Overlaps returns true if here is any overlap between i and i2.
	func (i Interval) Overlaps(i2 Interval) bool {
	return (imin(i.en, i2.en) - imax(i.st, i2.st)) > 0
	}

	// adjacent returns true if the start of one interval is equal to the
	// end of another interval (e.g. they represent consecutive ranges).
	func (i1 Interval) adjacent(i2 Interval) bool {
	return i1.en == i2.st \|\| i2.en == i1.st
	}

	// MergeInto merges interval i2 into i1. This version happens to
	// require that the two intervals either overlap or are adjacent.
	func (i1 *Interval) MergeInto(i2 Interval) error {
	if !i1.Overlaps(i2) && !i1.adjacent(i2) {
	return fmt.Errorf("merge method invoked on non-overlapping/non-adjacent")
	}
	i1.st = imin(i1.st, i2.st)
	i1.en = imax(i1.en, i2.en)
	return nil
	}

	// IntervalsBuilder is a helper for constructing intervals based on
	// live dataflow sets for a series of BBs where we're making a
	// backwards pass over each BB looking for uses and kills. The
	// expected use case is:
	//
	// - invoke MakeIntervalsBuilder to create a new object "b"
	// - series of calls to b.Live/b.Kill based on a backwards reverse layout
	// order scan over instructions
	// - invoke b.Finish() to produce final set
	//
	// See the Live method comment for an IR example.
	type IntervalsBuilder struct {
	s Intervals
	// index of last instruction visited plus 1
	lidx int
	}

	func (c *IntervalsBuilder) last() int {
	return c.lidx - 1
	}

	func (c *IntervalsBuilder) setLast(x int) {
	c.lidx = x + 1
	}

	func (c *IntervalsBuilder) Finish() (Intervals, error) {
	// Reverse intervals list and check.
	// FIXME: replace with slices.Reverse once the
	// bootstrap version supports it.
	for i, j := 0, len(c.s)-1; i < j; i, j = i+1, j-1 {
	c.s[i], c.s[j] = c.s[j], c.s[i]
	}
	if err := check(c.s); err != nil {
	return Intervals{}, err
	}
	r := c.s
	return r, nil
	}

	// Live method should be invoked on instruction at position p if instr
	// contains an upwards-exposed use of a resource. See the example in
	// the comment at the beginning of this file for an example.
	func (c *IntervalsBuilder) Live(pos int) error {
	if pos < 0 {
	return fmt.Errorf("bad pos, negative")
	}
	if c.last() == -1 {
	c.setLast(pos)
	if debugtrace {
	fmt.Fprintf(os.Stderr, "=-= begin lifetime at pos=%d\n", pos)
	}
	c.s = append(c.s, Interval{st: pos, en: pos + 1})
	return nil
	}
	if pos >= c.last() {
	return fmt.Errorf("pos not decreasing")
	}
	// extend lifetime across this pos
	c.s[len(c.s)-1].st = pos
	c.setLast(pos)
	return nil
	}

	// Kill method should be invoked on instruction at position p if instr
	// should be treated as as having a kill (lifetime end) for the
	// resource. See the example in the comment at the beginning of this
	// file for an example. Note that if we see a kill at position K for a
	// resource currently live since J, this will result in a lifetime
	// segment of [K+1,J+1), the assumption being that the first live
	// instruction will be the one after the kill position, not the kill
	// position itself.
	func (c *IntervalsBuilder) Kill(pos int) error {
	if pos < 0 {
	return fmt.Errorf("bad pos, negative")
	}
	if c.last() == -1 {
	return nil
	}
	if pos >= c.last() {
	return fmt.Errorf("pos not decreasing")
	}
	c.s[len(c.s)-1].st = pos + 1
	// terminate lifetime
	c.setLast(-1)
	if debugtrace {
	fmt.Fprintf(os.Stderr, "=-= term lifetime at pos=%d\n", pos)
	}
	return nil
	}

	// check examines the intervals in "is" to try to find internal
	// inconsistencies or problems.
	func check(is Intervals) error {
	for i := 0; i < len(is); i++ {
	st := is[i].st
	en := is[i].en
	if en <= st {
	return fmt.Errorf("bad range elem %d:%d, en<=st", st, en)
	}
	if i == 0 {
	continue
	}
	// check for badly ordered starts
	pst := is[i-1].st
	pen := is[i-1].en
	if pst >= st {
	return fmt.Errorf("range start not ordered %d:%d less than prev %d:%d", st, en,
	pst, pen)
	}
	// check end of last range against start of this range
	if pen > st {
	return fmt.Errorf("bad range elem %d:%d overlaps prev %d:%d", st, en,
	pst, pen)
	}
	}
	return nil
	}

	func (is *Intervals) String() string {
	var sb strings.Builder
	for i := range *is {
	if i != 0 {
	sb.WriteString(" ")
	}
	sb.WriteString((*is)[i].String())
	}
	return sb.String()
	}

	// intWithIdx holds an interval i and an index pairIndex storing i's
	// position (either 0 or 1) within some previously specified interval
	// pair <I1,I2>; a pairIndex of -1 is used to signal "end of
	// iteration". Used for Intervals operations, not expected to be
	// exported.
	type intWithIdx struct {
	i Interval
	pairIndex int
	}

	func (iwi intWithIdx) done() bool {
	return iwi.pairIndex == -1
	}

	// pairVisitor provides a way to visit (iterate through) each interval
	// within a pair of Intervals in order of increasing start time. Expected
	// usage model:
	//
	// func example(i1, i2 Intervals) {
	// var pairVisitor pv
	// cur := pv.init(i1, i2);
	// for !cur.done() {
	// fmt.Printf("interval %s from i%d", cur.i.String(), cur.pairIndex+1)
	// cur = pv.nxt()
	// }
	// }
	//
	// Used internally for Intervals operations, not expected to be exported.
	type pairVisitor struct {
	cur intWithIdx
	i1pos int
	i2pos int
	i1, i2 Intervals
	}

	// init initializes a pairVisitor for the specified pair of intervals
	// i1 and i2 and returns an intWithIdx object that points to the first
	// interval by start position within i1/i2.
	func (pv *pairVisitor) init(i1, i2 Intervals) intWithIdx {
	pv.i1, pv.i2 = i1, i2
	pv.cur = pv.sel()
	return pv.cur
	}

	// nxt advances the pairVisitor to the next interval by starting
	// position within the pair, returning an intWithIdx that describes
	// the interval.
	func (pv *pairVisitor) nxt() intWithIdx {
	if pv.cur.pairIndex == 0 {
	pv.i1pos++
	} else {
	pv.i2pos++
	}
	pv.cur = pv.sel()
	return pv.cur
	}

	// sel is a helper function used by 'init' and 'nxt' above; it selects
	// the earlier of the two intervals at the current positions within i1
	// and i2, or a degenerate (pairIndex -1) intWithIdx if we have no
	// more intervals to visit.
	func (pv *pairVisitor) sel() intWithIdx {
	var c1, c2 intWithIdx
	if pv.i1pos >= len(pv.i1) {
	c1.pairIndex = -1
	} else {
	c1 = intWithIdx{i: pv.i1[pv.i1pos], pairIndex: 0}
	}
	if pv.i2pos >= len(pv.i2) {
	c2.pairIndex = -1
	} else {
	c2 = intWithIdx{i: pv.i2[pv.i2pos], pairIndex: 1}
	}
	if c1.pairIndex == -1 {
	return c2
	}
	if c2.pairIndex == -1 {
	return c1
	}
	if c1.i.st <= c2.i.st {
	return c1
	}
	return c2
	}

	// Overlaps returns whether any of the component ranges in is overlaps
	// with some range in is2.
	func (is Intervals) Overlaps(is2 Intervals) bool {
	// check for empty intervals
	if len(is) == 0 \|\| len(is2) == 0 {
	return false
	}
	li := len(is)
	li2 := len(is2)
	// check for completely disjoint ranges
	if is[li-1].en <= is2[0].st \|\|
	is[0].st >= is2[li2-1].en {
	return false
	}
	// walk the combined sets of intervals and check for piecewise
	// overlap.
	var pv pairVisitor
	first := pv.init(is, is2)
	for {
	second := pv.nxt()
	if second.done() {
	break
	}
	if first.pairIndex == second.pairIndex {
	first = second
	continue
	}
	if first.i.Overlaps(second.i) {
	return true
	}
	first = second
	}
	return false
	}

	// Merge combines the intervals from "is" and "is2" and returns
	// a new Intervals object containing all combined ranges from the
	// two inputs.
	func (is Intervals) Merge(is2 Intervals) Intervals {
	if len(is) == 0 {
	return is2
	} else if len(is2) == 0 {
	return is
	}
	// walk the combined set of intervals and merge them together.
	var ret Intervals
	var pv pairVisitor
	cur := pv.init(is, is2)
	for {
	second := pv.nxt()
	if second.done() {
	break
	}

	// Check for overlap between cur and second. If no overlap
	// then add cur to result and move on.
	if !cur.i.Overlaps(second.i) && !cur.i.adjacent(second.i) {
	ret = append(ret, cur.i)
	cur = second
	continue
	}
	// cur overlaps with second; merge second into cur
	cur.i.MergeInto(second.i)
	}
	ret = append(ret, cur.i)
	return ret
	}