tree-optimization/26854 - slow bitmap operations

With the compiler.i testcase from the PR one can see bitmap_set_bit
very high in the profile, originating from SSA update and alias
stmt walking.  For SSA update mark_block_for_update essentially
performs redundant bitmap_set_bits and is called via
insert_updated_phi_nodes_for as

      EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
...
          mark_block_for_update (bb);
          FOR_EACH_EDGE (e, ei, bb->preds)
            if (e->src->index >= 0)
              mark_block_for_update (e->src);

which is quite random in the access pattern and runs into the
O(n) case of the linked list bitmap representation.  Switching
blocks_to_update to tree view around insert_updated_phi_nodes_for
improves SSA update time from

 tree SSA incremental               :   4.26 (  3%)

to

 tree SSA incremental               :   2.98 (  2%)

Likewise the visited bitmap allocated by the alias walker benefits
from using the tree view in case of large CFGs and we see an
improvement from

 alias stmt walking                 :  10.53 (  9%)

to

 alias stmt walking                 :   4.05 (  4%)

	PR tree-optimization/26854
	* tree-into-ssa.cc (update_ssa): Turn blocks_to_update to tree
	view around insert_updated_phi_nodes_for.
	* tree-ssa-alias.cc (maybe_skip_until): Allocate visited bitmap
	in tree view.
	(walk_aliased_vdefs_1): Likewise.

0 files changed, 0 insertions, 0 deletions