On Mon, May 06, 2019 at 04:17:01PM +0200, Richard Biener wrote:
> > > +/* Data structure for compute_live_vars* functions. */
> > >
> > > +struct compute_live_vars_data {
> > > + /* Vector of bitmaps for live vars at the end of basic blocks,
> > > + indexed by bb->index. ACTIVE[ENTRY_BLOCK] must be empty bitmap,
> > > + ACTIVE[EXIT_BLOCK] is used for STOP_AFTER. */
> > > + vec<bitmap_head> active;
> > > + /* Work bitmap of currently live variables. */
> > > + bitmap work;
> > > + /* Bitmap of interesting variables. Variables with uids not in this
> > > + bitmap are not tracked. */
> > > + bitmap vars;
> > > +};
>
> How dense are the bitmaps? Storage requirement will be quadratic
> so eventually using a sparseset for 'vars' and using the sparseset
> index for the bitmaps will improve things?
I don't see sparsesets ever used for DECL_UIDs, there is not even an
accessor for next_decl_uid which could be used outside of tree.c and I'm
afraid it could be huge.
The patch has a bitmap for testing if a DECL_UID is interesting to the
algorithm or not, so perhaps we could replace that bitmap with a
hash_map <unsigned, unsigned> that would map the interesting DECL_UIDs to
a sequential number or -1 and then perhaps use sbitmaps instead of bitmaps?
Jakub
