• Operation Bitmap Kill

Operation Bitmap Kill

Bitmaps have significant overhead, even though they are convenient and memory saving for large bitmaps. So when the maximum length of a bitmap is limited, most times it should be replaced by HARD_REG_SET (example case of a 10x improvement) or sbitmap.h. If the bitmap is too big or unlimited in size, and it is frequently accessed, then it should be measured against ebitmap.h which is better complexity-wise.

Here are the top callers (metric: instruction count).

• bitmap_set_bit()

 24,429,975  < df-problems.c:df_lr_bb_local_compute (655453x) [cc1]
 21,970,496  < df-problems.c:df_note_compute (523663x) [cc1]
 14,396,313  < df-core.c:df_worklist_dataflow (267369x) [cc1]
 13,288,854  < cprop.c:execute_rtl_cprop (360315x) [cc1]
  7,848,373  < df-problems.c:df_simulate_uses (203834x) [cc1]
  7,598,703  < df-problems.c:df_md_bb_local_compute_process_def (187700x) [cc1]
  6,929,971  < regstat.c:regstat_compute_ri (165537x) [cc1]
  6,822,138  < df-core.c:df_analyze (94869x) [cc1]
  5,934,612  < tree-ssa-pre.c:bitmap_insert_into_set_1 (108702x) [cc1]
  5,672,777  < df-problems.c:df_rd_bb_local_compute_process_def (139324x) [cc1]
  5,628,958  < tree-ssa-structalias.c:solve_constraints (121730x) [cc1]
  4,618,742  < df-problems.c:df_live_bb_local_compute (114507x) [cc1]
  4,181,210  < fwprop.c:process_defs (115778x) [cc1]
  3,776,914  < tree-ssa-pre.c:bitmap_value_insert_into_set (84700x) [cc1]
  3,661,421  < df-core.c:df_set_bb_dirty (98292x) [cc1]
  3,382,085  < dce.c:fast_dce (59222x) [cc1]
  3,062,477  < df-problems.c:df_simulate_initialize_backwards (87460x) [cc1]
  2,997,223  < ira.c:rest_of_handle_ira (64646x) [cc1]
  2,862,254  < tree-into-ssa.c:mark_block_for_update (79070x) [cc1]
  2,753,084  < tree-ssa-structalias.c:add_implicit_graph_edge.isra.36 (47145x) [cc1]
  2,490,857  < df-problems.c:df_simulate_find_noclobber_defs (65733x) [cc1]
  2,370,648  < tree-ssa-structalias.c:add_graph_edge.isra.37 (51905x) [cc1]
  2,096,000  < sched-deps.c:deps_analyze_insn (57640x) [cc1]
  2,025,582  < dse.c:record_store (30002x) [cc1]
  2,025,077  < sched-deps.c:sched_analyze_insn (56915x) [cc1]
  1,747,854  < tree-ssa-structalias.c:add_pred_graph_edge.isra.35 (28343x) [cc1]
  1,705,572  < tree-ssa-alias.c:walk_aliased_vdefs_1.constprop.17'2 (26475x) [cc1]
  1,636,697  < cfganal.c:compute_dominance_frontiers (33121x) [cc1]
  1,290,320  < tree-ssa-alias.c:walk_aliased_vdefs_1.constprop.17 (27453x) [cc1]
  1,285,474  < df-problems.c:df_rd_simulate_one_insn (24628x) [cc1]
  1,274,578  < dse.c:scan_stores_nospill (34726x) [cc1]
  1,152,411  < reload1.c:count_pseudo (25315x) [cc1]
  1,090,593  < sched-deps.c:haifa_note_reg_use (23137x) [cc1]
  1,047,310  < tree-ssa-pre.c:bitmap_set_subtract (21550x) [cc1]
  1,041,562  < regstat.c:regstat_compute_calls_crossed (29388x) [cc1]
  1,037,942  < tree-into-ssa.c:set_def_block.isra.40 (22507x) [cc1]
  1,029,821  < dse.c:rest_of_handle_dse (28184x) [cc1]

• bitmap_clear_bit()

 19,613,570  < df-problems.c:df_note_compute (918703x) [cc1]
 15,510,792  < df-problems.c:df_simulate_defs (719329x) [cc1]
  9,857,602  < df-problems.c:df_lr_bb_local_compute (464693x) [cc1]
  6,661,969  < df-core.c:df_worklist_dataflow (136883x) [cc1]
  2,214,753  < df-problems.c:df_md_bb_local_compute_process_def (151739x) [cc1]
  1,594,983  < regstat.c:regstat_compute_ri (50406x) [cc1]
  1,544,597  < ira.c:rest_of_handle_ira (71558x) [cc1]
  1,218,974  < tree-ssa-structalias.c:solve_constraints (58852x) [cc1]
    850,928  < tree-ssa-pre.c:bitmap_value_replace_in_set (25037x) [cc1]
    745,960  < regstat.c:regstat_compute_calls_crossed (15276x) [cc1]
    682,599  < cselib.c:cselib_expand_value_rtx_1'2 (12533x) [cc1]
    517,161  < df-problems.c:df_simulate_one_insn_forwards (16068x) [cc1]
    429,005  < tree-ssa-ter.c:finished_with_expr (5270x) [cc1]
    428,508  < df-scan.c:df_insn_rescan (65612x) [cc1]
    421,367  < df-scan.c:df_insn_delete (62816x) [cc1]
    407,525  < fwprop.c:process_defs (35961x) [cc1]
    367,946  < predict.c:propagate_freq (6550x) [cc1]
    250,091  < tree-cfgcleanup.c:cleanup_tree_cfg (7609x) [cc1]
    239,948  < tree-ssa-pre.c:bitmap_remove_from_set (8056x) [cc1]
    129,179  < dse.c:scan_reads_nospill.isra.23 (12758x) [cc1]
    118,560  < ira.c:mark_elimination (4560x) [cc1]
    107,506  < df-scan.c:df_notes_rescan (12038x) [cc1]
    102,728  < tree-ssa-coalesce.c:coalesce_ssa_name (1802x) [cc1]
    101,621  < tree-ssa-pre.c:bitmap_set_and (2843x) [cc1]

• bitmap_bit_p()

 11,242,029  < df-problems.c:df_note_compute (577362x) [cc1]
  4,490,508  < df-scan.c:df_insn_refs_collect (355212x) [cc1]
  4,014,269  < df-problems.c:df_rd_bb_local_compute_process_def (271800x) [cc1]
  3,601,496  < df-problems.c:df_create_unused_note (199333x) [cc1]
  3,229,621  < tree-into-ssa.c:symbol_marked_for_renaming (174143x) [cc1]
  2,718,081  < dce.c:fast_dce (161229x) [cc1]
  2,627,601  < tree-ssa-sccvn.c:value_id_constant_p (178813x) [cc1]
  2,262,938  < tree-ssa-pre.c:sorted_array_from_bitmap_set (58724x) [cc1]
  2,248,827  < tree-ssa-structalias.c:find_equivalent_node (123426x) [cc1]
  1,918,700  < reginfo.c:invalid_mode_change_p (183853x) [cc1]
  1,901,717  < fwprop.c:process_uses (127843x) [cc1]
  1,288,275  < reload1.c:count_pseudo (76940x) [cc1]
  1,189,860  < tree-ssa-pre.c:bitmap_set_contains_value (62284x) [cc1]
  1,145,870  < df-core.c:df_compact_blocks (105374x) [cc1]
  1,083,173  < tree-into-ssa.c:rewrite_update_enter_block (61694x) [cc1]
  1,065,843  < regstat.c:regstat_compute_ri (59018x) [cc1]
    866,995  < df-problems.c:df_md_bb_local_compute_process_def (151739x) [cc1]
    828,409  < tree-ssa.c:maybe_optimize_var (75630x) [cc1]
    738,575  < ira-color.c:assign_hard_reg (42043x) [cc1]
    579,619  < tree-into-ssa.c:prepare_block_for_update'2 (19580x) [cc1]
    498,964  < cprop.c:reg_not_set_p.isra.13 (31287x) [cc1]
    428,816  < df-core.c:df_prune_to_subcfg (10544x) [cc1]
    419,303  < ira.c:rest_of_handle_ira (21820x) [cc1]
    341,601  < tree-ssa-pre.c:valid_in_sets (16735x) [cc1]
    336,316  < init-regs.c:rest_of_handle_initialize_regs (23256x) [cc1]
    323,755  < cprop.c:reg_available_p.isra.12 (20042x) [cc1]
    299,753  < dominance.c:calc_idoms (42164x) [cc1]
    295,239  < tree-into-ssa.c:insert_phi_nodes_for (16828x) [cc1]
    280,358  < tree-ssa-structalias.c:solve_constraints (17425x) [cc1]
    228,083  < tree-into-ssa.c:mark_def_sites_block (13582x) [cc1]
    226,967  < tree-into-ssa.c:mark_def_interesting (13351x) [cc1]
    192,398  < ssaexpand.h:gimple_expand_cfg (9307x)
    190,695  < dce.c:prescan_insns_for_dce (38139x) [cc1]
    188,620  < combine.c:get_last_value_validate'2 (10590x) [cc1]
    185,049  < df-core.c:df_get_bb_dirty (23461x) [cc1]
    158,689  < df-problems.c:df_md_local_compute (4130x) [cc1]