Source file src/pkg/cmd/compile/internal/gc/bv.go

     1	// Copyright 2013 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 gc
     6	
     7	const (
     8		wordBits  = 32
     9		wordMask  = wordBits - 1
    10		wordShift = 5
    11	)
    12	
    13	// A bvec is a bit vector.
    14	type bvec struct {
    15		n int32    // number of bits in vector
    16		b []uint32 // words holding bits
    17	}
    18	
    19	func bvalloc(n int32) bvec {
    20		nword := (n + wordBits - 1) / wordBits
    21		return bvec{n, make([]uint32, nword)}
    22	}
    23	
    24	type bulkBvec struct {
    25		words []uint32
    26		nbit  int32
    27		nword int32
    28	}
    29	
    30	func bvbulkalloc(nbit int32, count int32) bulkBvec {
    31		nword := (nbit + wordBits - 1) / wordBits
    32		size := int64(nword) * int64(count)
    33		if int64(int32(size*4)) != size*4 {
    34			Fatalf("bvbulkalloc too big: nbit=%d count=%d nword=%d size=%d", nbit, count, nword, size)
    35		}
    36		return bulkBvec{
    37			words: make([]uint32, size),
    38			nbit:  nbit,
    39			nword: nword,
    40		}
    41	}
    42	
    43	func (b *bulkBvec) next() bvec {
    44		out := bvec{b.nbit, b.words[:b.nword]}
    45		b.words = b.words[b.nword:]
    46		return out
    47	}
    48	
    49	func (bv1 bvec) Eq(bv2 bvec) bool {
    50		if bv1.n != bv2.n {
    51			Fatalf("bvequal: lengths %d and %d are not equal", bv1.n, bv2.n)
    52		}
    53		for i, x := range bv1.b {
    54			if x != bv2.b[i] {
    55				return false
    56			}
    57		}
    58		return true
    59	}
    60	
    61	func (dst bvec) Copy(src bvec) {
    62		copy(dst.b, src.b)
    63	}
    64	
    65	func (bv bvec) Get(i int32) bool {
    66		if i < 0 || i >= bv.n {
    67			Fatalf("bvget: index %d is out of bounds with length %d\n", i, bv.n)
    68		}
    69		mask := uint32(1 << uint(i%wordBits))
    70		return bv.b[i>>wordShift]&mask != 0
    71	}
    72	
    73	func (bv bvec) Set(i int32) {
    74		if i < 0 || i >= bv.n {
    75			Fatalf("bvset: index %d is out of bounds with length %d\n", i, bv.n)
    76		}
    77		mask := uint32(1 << uint(i%wordBits))
    78		bv.b[i/wordBits] |= mask
    79	}
    80	
    81	func (bv bvec) Unset(i int32) {
    82		if i < 0 || i >= bv.n {
    83			Fatalf("bvunset: index %d is out of bounds with length %d\n", i, bv.n)
    84		}
    85		mask := uint32(1 << uint(i%wordBits))
    86		bv.b[i/wordBits] &^= mask
    87	}
    88	
    89	// bvnext returns the smallest index >= i for which bvget(bv, i) == 1.
    90	// If there is no such index, bvnext returns -1.
    91	func (bv bvec) Next(i int32) int32 {
    92		if i >= bv.n {
    93			return -1
    94		}
    95	
    96		// Jump i ahead to next word with bits.
    97		if bv.b[i>>wordShift]>>uint(i&wordMask) == 0 {
    98			i &^= wordMask
    99			i += wordBits
   100			for i < bv.n && bv.b[i>>wordShift] == 0 {
   101				i += wordBits
   102			}
   103		}
   104	
   105		if i >= bv.n {
   106			return -1
   107		}
   108	
   109		// Find 1 bit.
   110		w := bv.b[i>>wordShift] >> uint(i&wordMask)
   111	
   112		for w&1 == 0 {
   113			w >>= 1
   114			i++
   115		}
   116	
   117		return i
   118	}
   119	
   120	// Len returns the minimum number of bits required to represent bv.
   121	// The result is 0 if no bits are set in bv.
   122	func (bv bvec) Len() int32 {
   123		for wi := len(bv.b) - 1; wi >= 0; wi-- {
   124			if w := bv.b[wi]; w != 0 {
   125				for i := wordBits - 1; i >= 0; i-- {
   126					if w>>uint(i) != 0 {
   127						return int32(wi)*wordBits + int32(i) + 1
   128					}
   129				}
   130			}
   131		}
   132		return 0
   133	}
   134	
   135	func (bv bvec) IsEmpty() bool {
   136		for _, x := range bv.b {
   137			if x != 0 {
   138				return false
   139			}
   140		}
   141		return true
   142	}
   143	
   144	func (bv bvec) Not() {
   145		for i, x := range bv.b {
   146			bv.b[i] = ^x
   147		}
   148	}
   149	
   150	// union
   151	func (dst bvec) Or(src1, src2 bvec) {
   152		if len(src1.b) == 0 {
   153			return
   154		}
   155		_, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop
   156	
   157		for i, x := range src1.b {
   158			dst.b[i] = x | src2.b[i]
   159		}
   160	}
   161	
   162	// intersection
   163	func (dst bvec) And(src1, src2 bvec) {
   164		if len(src1.b) == 0 {
   165			return
   166		}
   167		_, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop
   168	
   169		for i, x := range src1.b {
   170			dst.b[i] = x & src2.b[i]
   171		}
   172	}
   173	
   174	// difference
   175	func (dst bvec) AndNot(src1, src2 bvec) {
   176		if len(src1.b) == 0 {
   177			return
   178		}
   179		_, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop
   180	
   181		for i, x := range src1.b {
   182			dst.b[i] = x &^ src2.b[i]
   183		}
   184	}
   185	
   186	func (bv bvec) String() string {
   187		s := make([]byte, 2+bv.n)
   188		copy(s, "#*")
   189		for i := int32(0); i < bv.n; i++ {
   190			ch := byte('0')
   191			if bv.Get(i) {
   192				ch = '1'
   193			}
   194			s[2+i] = ch
   195		}
   196		return string(s)
   197	}
   198	
   199	func (bv bvec) Clear() {
   200		for i := range bv.b {
   201			bv.b[i] = 0
   202		}
   203	}
   204	
   205	// FNV-1 hash function constants.
   206	const (
   207		H0 = 2166136261
   208		Hp = 16777619
   209	)
   210	
   211	func hashbitmap(h uint32, bv bvec) uint32 {
   212		n := int((bv.n + 31) / 32)
   213		for i := 0; i < n; i++ {
   214			w := bv.b[i]
   215			h = (h * Hp) ^ (w & 0xff)
   216			h = (h * Hp) ^ ((w >> 8) & 0xff)
   217			h = (h * Hp) ^ ((w >> 16) & 0xff)
   218			h = (h * Hp) ^ ((w >> 24) & 0xff)
   219		}
   220	
   221		return h
   222	}
   223	
   224	// bvecSet is a set of bvecs, in initial insertion order.
   225	type bvecSet struct {
   226		index []int  // hash -> uniq index. -1 indicates empty slot.
   227		uniq  []bvec // unique bvecs, in insertion order
   228	}
   229	
   230	func (m *bvecSet) grow() {
   231		// Allocate new index.
   232		n := len(m.index) * 2
   233		if n == 0 {
   234			n = 32
   235		}
   236		newIndex := make([]int, n)
   237		for i := range newIndex {
   238			newIndex[i] = -1
   239		}
   240	
   241		// Rehash into newIndex.
   242		for i, bv := range m.uniq {
   243			h := hashbitmap(H0, bv) % uint32(len(newIndex))
   244			for {
   245				j := newIndex[h]
   246				if j < 0 {
   247					newIndex[h] = i
   248					break
   249				}
   250				h++
   251				if h == uint32(len(newIndex)) {
   252					h = 0
   253				}
   254			}
   255		}
   256		m.index = newIndex
   257	}
   258	
   259	// add adds bv to the set and returns its index in m.extractUniqe.
   260	// The caller must not modify bv after this.
   261	func (m *bvecSet) add(bv bvec) int {
   262		if len(m.uniq)*4 >= len(m.index) {
   263			m.grow()
   264		}
   265	
   266		index := m.index
   267		h := hashbitmap(H0, bv) % uint32(len(index))
   268		for {
   269			j := index[h]
   270			if j < 0 {
   271				// New bvec.
   272				index[h] = len(m.uniq)
   273				m.uniq = append(m.uniq, bv)
   274				return len(m.uniq) - 1
   275			}
   276			jlive := m.uniq[j]
   277			if bv.Eq(jlive) {
   278				// Existing bvec.
   279				return j
   280			}
   281	
   282			h++
   283			if h == uint32(len(index)) {
   284				h = 0
   285			}
   286		}
   287	}
   288	
   289	// extractUniqe returns this slice of unique bit vectors in m, as
   290	// indexed by the result of bvecSet.add.
   291	func (m *bvecSet) extractUniqe() []bvec {
   292		return m.uniq
   293	}
   294	

View as plain text