| // Copyright 2013 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 | |
| import "cmd/compile/internal/bitvec" | |
| // FNV-1 hash function constants. | |
| const ( | |
| h0 = 2166136261 | |
| hp = 16777619 | |
| ) | |
| // bvecSet is a set of bvecs, in initial insertion order. | |
| type bvecSet struct { | |
| index []int // hash -> uniq index. -1 indicates empty slot. | |
| uniq []bitvec.BitVec // unique bvecs, in insertion order | |
| } | |
| func (m *bvecSet) grow() { | |
| // Allocate new index. | |
| n := len(m.index) * 2 | |
| if n == 0 { | |
| n = 32 | |
| } | |
| newIndex := make([]int, n) | |
| for i := range newIndex { | |
| newIndex[i] = -1 | |
| } | |
| // Rehash into newIndex. | |
| for i, bv := range m.uniq { | |
| h := hashbitmap(h0, bv) % uint32(len(newIndex)) | |
| for { | |
| j := newIndex[h] | |
| if j < 0 { | |
| newIndex[h] = i | |
| break | |
| } | |
| h++ | |
| if h == uint32(len(newIndex)) { | |
| h = 0 | |
| } | |
| } | |
| } | |
| m.index = newIndex | |
| } | |
| // add adds bv to the set and returns its index in m.extractUnique. | |
| // The caller must not modify bv after this. | |
| func (m *bvecSet) add(bv bitvec.BitVec) int { | |
| if len(m.uniq)*4 >= len(m.index) { | |
| m.grow() | |
| } | |
| index := m.index | |
| h := hashbitmap(h0, bv) % uint32(len(index)) | |
| for { | |
| j := index[h] | |
| if j < 0 { | |
| // New bvec. | |
| index[h] = len(m.uniq) | |
| m.uniq = append(m.uniq, bv) | |
| return len(m.uniq) - 1 | |
| } | |
| jlive := m.uniq[j] | |
| if bv.Eq(jlive) { | |
| // Existing bvec. | |
| return j | |
| } | |
| h++ | |
| if h == uint32(len(index)) { | |
| h = 0 | |
| } | |
| } | |
| } | |
| // extractUnique returns this slice of unique bit vectors in m, as | |
| // indexed by the result of bvecSet.add. | |
| func (m *bvecSet) extractUnique() []bitvec.BitVec { | |
| return m.uniq | |
| } | |
| func hashbitmap(h uint32, bv bitvec.BitVec) uint32 { | |
| n := int((bv.N + 31) / 32) | |
| for i := 0; i < n; i++ { | |
| w := bv.B[i] | |
| h = (h * hp) ^ (w & 0xff) | |
| h = (h * hp) ^ ((w >> 8) & 0xff) | |
| h = (h * hp) ^ ((w >> 16) & 0xff) | |
| h = (h * hp) ^ ((w >> 24) & 0xff) | |
| } | |
| return h | |
| } |