diff options
author | Trevor Saunders <tbsaunde+gcc@tbsaunde.org> | 2015-02-08 09:22:28 -0500 |
---|---|---|
committer | Trevor Saunders <tbsaunde+gcc@tbsaunde.org> | 2015-04-09 19:57:14 -0400 |
commit | 4f8953b6684459714538e47696797e3b02dfe428 (patch) | |
tree | ebb4c8dbf1bdaa10be85e4042cd782b936f52a62 /gcc/bitvec.h | |
parent | 4aed2663603411f5bb768f5c84d1a872a5bb281c (diff) | |
download | gcc-tbsaunde/bitvec.tar.gz |
add bitvec and use sometbsaunde/bitvec
gcc/
2015-04-08 Trevor Saunders <tbsaunde@tbsaunde.org>
* bitvec.h: New file.
* bitvec.c: New file.
* Makefile.in (OBJS-libcommon): Add bitvec.o.
* alias.c, cfganal.c, cfgbuild.c, cfgbuild.h, cfgexpand.c, cfghooks.c,
cfghooks.h, cfgloop.c, cfgloopmanip.c, cfgloopmanip.h, cfgrtl.c,
config/spu/spu.c, cp/vtable-class-hierarchy.c, cse.c, dce.c,
df-core.c, dse.c, except.c, except.h, function.c, graph.c,
graphite-sese-to-poly.c, ira-lives.c, loop-unroll.c, lower-subreg.c,
lra-lives.c, lra.c, modulo-sched.c, recog.c, regcprop.c, reload1.c,
sched-int.h, sched-rgn.c, sel-sched-ir.c, sel-sched.c,
store-motion.c, tree-eh.c, tree-into-ssa.c, tree-outof-ssa.c,
tree-ssa-dce.c, tree-ssa-live.c, tree-ssa-loop-im.c,
tree-ssa-loop-ivcanon.c, tree-ssa-loop-manip.c,
tree-ssa-loop-manip.h, tree-ssa-pre.c, tree-ssa-propagate.c,
tree-ssa-reassoc.c, tree-ssa-structalias.c, tree-stdarg.c,
tree-vect-slp.c, tree-vrp.c, var-tracking.c: Use bitvec instead
of sbitmap.
Diffstat (limited to 'gcc/bitvec.h')
-rw-r--r-- | gcc/bitvec.h | 194 |
1 files changed, 194 insertions, 0 deletions
diff --git a/gcc/bitvec.h b/gcc/bitvec.h new file mode 100644 index 00000000000..ff34158ef7e --- /dev/null +++ b/gcc/bitvec.h @@ -0,0 +1,194 @@ + + +#ifndef BITVEC_H_ +#define BITVEC_H_ + +#include "vec.h" + +class stack_bitvec; + +class bitvec +{ +private: + typedef uint64_t elt_type; + static const uint8_t bits_per_elt = 64; + +public: + + bitvec () {} + explicit bitvec (size_t elts) + { m_bits.safe_grow_cleared (needed_elts (elts)); } + + struct bit_ref + { + bit_ref (uint64_t *word, uint8_t bit) : m_word (word), m_bit (bit) {} + + operator bool() const { return *m_word & (((uint64_t) 1) << m_bit); } + bit_ref &operator= (bool b) + { + if (b) + *m_word |= ((uint64_t) 1) << m_bit; + else + *m_word &= ~(((uint64_t) 1) << m_bit); + + return *this; + } + +private: + uint64_t *m_word; + uint8_t m_bit; + }; + + bool + operator[] (size_t elt) const + { return m_bits[word (elt)] & bit_mask (elt); } + bit_ref operator[] (size_t elt) + { return bit_ref (&m_bits[word (elt)], elt % bits_per_elt); } + + bitvec & + operator|= (const bitvec &other) + { + if (other.m_bits.length () > m_bits.length ()) + m_bits.safe_grow_cleared (other.m_bits.length ()); + + for (size_t i = 0; i < other.m_bits.length (); i++) + m_bits[i] |= other.m_bits[i]; + + return *this; + } + + bool + operator== (const bitvec &other) const + { + if (m_bits.length () != other.m_bits.length ()) + return false; + + for (size_t i = 0; i < m_bits.length (); i++) + if (m_bits[i] != other.m_bits[i]) + return false; + + return true; + } + + size_t begin () const { return 0; } + size_t end () const { return m_bits.length () * bits_per_elt; } + + size_t size () const { return m_bits.length (); } + + ssize_t first_set_bit () const; + bool any_set_bits () const { return first_set_bit () >= 0; } + + bitvec (const bitvec &other) : m_bits (other.m_bits) {} + + void clear_and_release () { m_bits.truncate (0); } + + void clear () + { + memset (m_bits.address (), 0, sizeof (uint64_t) * m_bits.length ()); + } + + void set () + { + for (size_t i = 0; i < m_bits.length (); i++) + m_bits[i] = ~(uint64_t) 0; + } + + void + grow (size_t bits) + { + m_bits.safe_grow_cleared (needed_elts (bits)); + } + + void dump (FILE *) const; + +protected: + static size_t word (size_t elt) { return elt / bits_per_elt; } + static size_t bit_mask (size_t elt) { return ((uint64_t) 1) << (elt % bits_per_elt); } + static size_t + needed_elts (size_t bits) + { + return (bits + bits_per_elt - 1) / bits_per_elt; + } + + void copy (const bitvec &other) { m_bits = other.m_bits; } + + friend stack_bitvec operator| (const bitvec &, const bitvec &); + + auto_vec<uint64_t, 0> m_bits; +}; + +class stack_bitvec : public bitvec +{ +public: + stack_bitvec () { init (); } + + explicit stack_bitvec (size_t bits) + { + if (needed_elts (bits) <= inline_elts) + { + m_auto.embedded_init (inline_elts, 0, 1); + m_bits.m_vec = &m_auto; + } + + m_bits.safe_grow_cleared (needed_elts (bits)); + } + + stack_bitvec (const stack_bitvec &other) : bitvec () + { + init (); + copy (other); + } + + stack_bitvec (const bitvec &other) + { + init (); + copy (other); + } + + stack_bitvec & + operator= (const bitvec &other) + { + clear_and_release (); + init (); + copy (other); + return *this; + } + + stack_bitvec & + operator= (const stack_bitvec &other) + { + clear_and_release (); + init (); + copy (other); + return *this; + } + +private: + static const uint8_t inline_elts = 4; + + void + init () + { + m_auto.embedded_init (inline_elts, 0, 1); + m_bits.m_vec = &m_auto; + } + + vec<uint64_t, va_heap, vl_embed> m_auto; + uint64_t m_data[inline_elts - 1]; +}; + +inline stack_bitvec +operator| (const bitvec &a, const bitvec &b) +{ + stack_bitvec both (a); + size_t len2 = b.m_bits.length (); + if (len2 > both.m_bits.length ()) + both.m_bits.safe_grow_cleared (len2); + + for (size_t i = 0; i < len2; i++) + both.m_bits[i] |= b.m_bits[i]; + + return both; + } + +#endif |