#include "config.h"#include "system.h"#include "coretypes.h"#include "obstack.h"#include "ggc.h"#include "bitmap.h"#include "hash-table.h"#include "vec.h"#include "gt-bitmap.h"
Data Structures | |
| struct | bitmap_descriptor_d |
| struct | loc |
| struct | bitmap_desc_hasher |
| struct | output_info |
Macros | |
| #define | __alignof__(type) 0 |
Typedefs | |
| typedef struct bitmap_descriptor_d * | bitmap_descriptor |
| typedef struct bitmap_descriptor_d * | const_bitmap_descriptor |
Variables | |
| static int | next_bitmap_desc_id = 0 |
| static vec< bitmap_descriptor > | bitmap_descriptors |
| static hash_table < bitmap_desc_hasher > | bitmap_desc_hash |
| bitmap_element | bitmap_zero_bits |
| bitmap_obstack | bitmap_default_obstack |
| static int | bitmap_default_obstack_depth |
| static bitmap_element * | bitmap_ggc_free |
| static const unsigned char | popcount_table [] |
Macro Definition Documentation
| #define __alignof__ | ( | type | ) | 0 |
Referenced by bitmap_clear().
Typedef Documentation
| typedef struct bitmap_descriptor_d* bitmap_descriptor |
| typedef struct bitmap_descriptor_d* const_bitmap_descriptor |
Function Documentation
| void bitmap_and | ( | ) |
DST = A & B.
Matching elts, generate A & B.
Ensure that dst->current is valid.
References bitmap_element_free(), BITMAP_ELEMENT_WORDS, bitmap_elt_clear_from(), bitmap_element_def::bits, changed, bitmap_head_def::current, bitmap_head_def::first, gcc_checking_assert, bitmap_element_def::indx, bitmap_head_def::indx, and bitmap_element_def::next.
Referenced by df_live_reset().
| bool bitmap_and_compl | ( | ) |
DST = A & ~B
Matching elts, generate A & ~B.
Ensure that dst->current is valid.
Referenced by compute_out().
| bool bitmap_and_compl_into | ( | ) |
A &= ~B. Returns true if A changes
Matching elts, generate A &= ~B.
References bitmap_element_allocate(), bitmap_element_link(), and bitmap_element_def::indx.
Referenced by df_simulate_one_insn_forwards(), dse_step2_init(), dse_step2_nospill(), ref_indep_loop_p_2(), and same_succ_flush_bb().
| bool bitmap_and_into | ( | ) |
A &= B. Return true if A changed.
Matching elts, generate A &= B.
References BITMAP_ELEMENT_WORDS, bitmap_elt_insert_after(), bitmap_element_def::bits, changed, and bitmap_element_def::indx.
Referenced by get_stored_val(), and union_static_var_sets().
| int bitmap_bit_p | ( | ) |
Return whether a bit is set within a bitmap.
References BITMAP_ELEMENT_WORDS, bitmap_popcount(), bitmap_element_def::bits, count, bitmap_head_def::first, and bitmap_element_def::next.
| void bitmap_clear | ( | ) |
Clear a bitmap by freeing the linked list.
References __alignof__.
Referenced by bitmap_elt_insert_after(), bitmap_ior(), bitmap_ones(), build_and_add_sum(), check_argument_store(), compute_available(), decide_peel_simple(), determine_common_wider_type(), df_chain_bottom_dump(), df_chain_insn_bottom_dump(), df_chain_remove_problem(), df_get_eh_block_artificial_uses(), df_insn_rescan_debug_internal(), df_live_reset(), df_live_verify_solution_end(), df_lr_alloc(), df_lr_free_bb_info(), df_lr_local_compute(), df_mark_reg(), df_set_bb_dirty(), dse_confluence_0(), fast_dce(), find_refs_for_sm(), find_src_set_src(), flow_dfs_compute_reverse_init(), gate_ud_dce(), insert_store(), live_track_process_use(), lra_set_used_insn_alternative_by_uid(), lra_setup_reg_renumber(), make_edges(), mem_move_p(), need_ssa_update_p(), new_live_track(), same_succ_flush_bb(), scan_stores_nospill(), sccvn_valnum_from_value_id(), set_var_live_on_entry(), setup_try_hard_regno_pseudos(), and vect_slp_rearrange_stmts().
| bool bitmap_clear_bit | ( | ) |
Clear a single bit in a bitmap. Return true if the bit changed.
If we cleared the entire word, free up the element.
References bitmap_element_def::bits.
Referenced by add_pred_graph_edge(), add_to_partition_kill_list(), assign_by_spills(), bitmap_set_new(), bitmap_set_subtract(), check_all_array_refs(), check_array_bounds(), dead_debug_add(), df_mark_solutions_dirty(), df_ref_chain_delete(), df_set_unused_notes_for_mw(), find_src_set_src(), init_lives(), insert_insn_start_basic_block(), mark_nonreg_stores_2(), one_pre_gcse_pass(), register_edge_assert_for(), regstat_get_setjmp_crosses(), same_succ_flush_bb(), setup_reg_equiv(), unite_pointer_equivalences(), and vop_phi().
| void bitmap_clear_range | ( | ) |
Clear COUNT bits from START in HEAD.
If bitmap_find_bit returns zero, the current is the closest block to the result. If the current is less than first index, find the next one. Otherwise, just set elt to be current.
Get rid of the entire elt and go to the next one.
Going to have to knock out some bits in this elt.
The first bit to turn off is somewhere inside this
elt. This mask should have 1s in all bits >= start position.
The first bit to turn off is below this start of this elt.
The last bit to turn off is beyond this elt.
The last bit to turn off is inside to this elt.
The last mask should have 1s below the end bit.
Check to see if there are any bits left.
Referenced by df_rd_bb_local_compute_process_def(), and pt_solution_set_var().
| void bitmap_compl_and_into | ( | ) |
A = ~A & B.
A is before B. Remove A
B is before A. Copy B.
Matching elts, generate A = ~A & B.
References bitmap_element_def::bits.
| void bitmap_copy | ( | ) |
Copy a bitmap to another bitmap.
Copy elements in forward direction one at a time.
Here we have a special case of bitmap_element_link, for the case
where we know the links are being entered in sequence.
References BITMAP_ELEMENT_ALL_BITS, bitmap_head_def::current, bitmap_head_def::descriptor_id, bitmap_head_def::first, bitmap_element_def::indx, bitmap_head_def::indx, bitmap_element_def::next, NULL, and bitmap_element_def::prev.
Referenced by add_label_notes(), btr_def_live_range(), compute_builtin_object_size(), compute_dominance_frontiers_1(), delete_update_ssa(), df_chain_remove_problem(), df_get_eh_block_artificial_uses(), df_insn_rescan_debug_internal(), df_live_finalize(), df_live_verify_solution_end(), df_lr_free(), df_lr_local_compute(), df_md_alloc(), df_set_bb_dirty(), df_simulate_fixup_sets(), tm_memop_hasher::equal(), find_insn_before_first_wild_read(), find_occr_in_bb(), gate_ud_dce(), migrate_btr_def(), regstat_get_setjmp_crosses(), and scan_reads_spill().
| unsigned long bitmap_count_bits | ( | ) |
Count the number of bits set in the bitmap, and return it.
|
static |
|
inlinestatic |
Add ELEM to the appropriate freelist.
References bitmap_ggc_free, and bitmap_element_def::prev.
|
static |
Referenced by bitmap_and_compl_into(), and bitmap_elt_insert_after().
|
inlinestatic |
Allocate a bitmap element. The bits are cleared, but nothing else is.
Use up the inner list first before looking at the next
element of the outer list.
Inner list was just a singleton.
Use up the inner list first before looking at the next
element of the outer list. Inner list was just a singleton.
|
static |
Referenced by bitmap_and().
|
inlinestatic |
Free a bitmap element. Since these are allocated off the bitmap_obstack, "free" actually means "put onto the freelist".
Since the first thing we try is to insert before current, make current the next entry in preference to the previous.
References bitmap_head_def::current, bitmap_element_def::indx, and bitmap_head_def::indx.
|
static |
Referenced by bitmap_and_compl_into().
|
inlinestatic |
Link the bitmap element into the current bitmap linked list.
If this is the first and only element, set it in.
If this index is less than that of the current element, it goes someplace before the current element.
Otherwise, it must go someplace after the current element.
Set up so this is the first element searched.
|
static |
|
inlinestatic |
Return nonzero if all bits in an element are zero.
|
static |
Referenced by bitmap_and().
| void bitmap_elt_clear_from | ( | ) |
Remove ELT and all following elements from bitmap HEAD.
Put the entire list onto the free list in one operation.
References bitmap_head_def::current, bitmap_element_def::indx, and bitmap_head_def::indx.
|
inlinestatic |
Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap had already been changed; the new value of CHANGED is returned.
References BITMAP_ELEMENT_WORDS, bitmap_elt_insert_after(), bitmap_element_def::bits, and bitmap_element_def::indx.
|
static |
Referenced by bitmap_and_into(), and bitmap_elt_copy().
|
static |
Insert a new uninitialized element into bitmap HEAD after element ELT. If ELT is NULL, insert the element at the start. Return the new element.
References bitmap_clear(), bitmap_element_allocate(), bitmap_element_def::bits, bitmap_head_def::current, bitmap_head_def::first, bitmap_element_def::indx, bitmap_head_def::indx, bitmap_element_def::next, and bitmap_element_def::prev.
|
inlinestatic |
Insert an element corresponding to A_ELT | B_ELT after DST_PREV, overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap had already been changed; the new value of CHANGED is returned.
Matching elts, generate A | B.
Copy a single element.
Referenced by bitmap_intersect_p().
| bool bitmap_equal_p | ( | ) |
Return true if two bitmaps are identical. We do not bother with a check for pointer equality, as that never occurs in practice.
References BITMAP_ELEMENT_WORDS, bitmap_element_def::bits, bitmap_element_def::indx, and bitmap_element_def::next.
Referenced by df_get_eh_block_artificial_uses(), df_live_free(), df_live_verify_solution_end(), df_record_entry_block_defs(), and union_static_var_sets().
|
static |
|
inlinestatic |
Find a bitmap element that would hold a bitmap's bit. Update the `current' field even if we can't find an element that would hold the bitmap's bit to make eventual allocation faster.
This bitmap has more than one element, and we're going to look through the elements list. Count that as a search.
INDX is beyond head->indx. Search from head->current forward.
INDX is less than head->indx and closer to head->indx than to 0. Search from head->current backward.
INDX is less than head->indx and closer to 0 than to head->indx. Search from head->first forward.
`element' is the nearest to the one we want. If it's not the one we want, the one we want doesn't exist.
| unsigned bitmap_first_set_bit | ( | ) |
Return the bit number of the first set bit in the bitmap. The bitmap must be non-empty.
Binary search for the first set bit.
Referenced by build_and_add_sum(), build_succ_graph(), prepare_block_for_update(), and update_dep_bb().
| bitmap bitmap_gc_alloc_stat | ( | ) |
Create a new GCd bitmap.
| hashval_t bitmap_hash | ( | ) |
Compute hash of bitmap (for purposes of hashing).
Referenced by do_complex_constraint(), and update_dep_bb().
| bool bitmap_intersect_compl_p | ( | ) |
Return true if A AND NOT B is not empty.
| bool bitmap_intersect_p | ( | ) |
Return true if A AND B is not empty.
References bitmap_elt_ior(), bitmap_element_def::indx, and bitmap_element_def::next.
| bool bitmap_ior | ( | ) |
DST = A | B. Return true if DST changes.
References bitmap_clear().
Referenced by equiv_class_lookup_or_add(), and prune_expressions().
| bool bitmap_ior_and_compl | ( | ) |
DST = A | (FROM1 & ~FROM2). Return true if DST changes.
Special cases. We don't bother checking for bitmap_equal_p (b, kill).
Referenced by compute_available(), and compute_kill().
| bool bitmap_ior_and_compl_into | ( | ) |
A |= (FROM1 & ~FROM2). Return true if A changes.
References bitmap_head_def::current, bitmap_head_def::first, HOST_PTR_PRINTF, bitmap_head_def::indx, and bitmap_element_def::next.
| bool bitmap_ior_and_into | ( | ) |
A |= (B & C). Return true if A changes.
Find a common item of B and C.
Now find a place to insert AND_ELT.
If A lagged behind B/C, we advanced it so loop once more.
| bool bitmap_ior_into | ( | ) |
A |= B. Return true if A changes.
If A lags behind B, just advance it.
Referenced by add_scope_conflicts_1(), assign_by_spills(), df_grow_insn_info(), df_live_bb_local_compute(), do_sd_constraint(), dse_step2_init(), dse_step2_nospill(), dump_tm_memopt_sets(), equiv_class_lookup_or_add(), free_topo_info(), equiv_class_hasher::hash(), kill_expr(), ref_indep_loop_p_2(), remove_pseudos(), scan_reads_nospill(), set_incoming_from_chain(), set_var_live_on_entry(), spill_pseudos(), tm_memopt_accumulate_memops(), and vrp_operand_equal_p().
| unsigned bitmap_last_set_bit | ( | ) |
Return the bit number of the first set bit in the bitmap. The bitmap must be non-empty.
Hopefully this is a twos-complement host...
| bitmap bitmap_obstack_alloc_stat | ( | ) |
Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create it on the default bitmap obstack.
| void bitmap_obstack_free | ( | ) |
Release an obstack allocated bitmap.
| void bitmap_obstack_initialize | ( | ) |
Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize the default bitmap obstack.
References bitmap_default_obstack, bitmap_obstack::elements, gcc_assert, bitmap_obstack::heads, NULL, and bitmap_obstack::obstack.
Referenced by df_rd_alloc(), find_uses_to_rename(), mark_artificial_uses(), split_live_ranges_for_shrink_wrap(), and update_lives().
| void bitmap_obstack_release | ( | ) |
Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, release the default bitmap obstack.
Referenced by tm_region_init_1().
|
static |
Just do this the table way for now
References bitmap_element_def::bits.
Referenced by bitmap_bit_p().
| DEBUG_FUNCTION void bitmap_print | ( | FILE * | file, |
| const_bitmap | head, | ||
| const char * | prefix, | ||
| const char * | suffix | ||
| ) |
Function to print out the contents of a bitmap. Unlike debug_bitmap_file, it does not print anything but the bits.
Referenced by df_clear_flags(), and dse_step3().
| void bitmap_register | ( | ) |
Register new bitmap.
References bitmap_descriptor_d::allocated, bitmap_descriptor_d::current, bitmap_head_def::descriptor_id, and bitmap_descriptor_d::peak.
| bool bitmap_set_bit | ( | ) |
Set a single bit in a bitmap. Return true if the bit changed.
| void bitmap_set_range | ( | ) |
Set COUNT bits from START in HEAD.
If bitmap_find_bit returns zero, the current is the closest block to the result. Otherwise, just use bitmap_element_allocate to ensure ELT is set; in the loop below, ELT == NULL means "insert at the end of the bitmap".
The first bit to turn on is somewhere inside this
elt. This mask should have 1s in all bits >= start position.
The first bit to turn on is below this start of this elt.
The last bit to turn on is beyond this elt.
The last bit to turn on is inside to this elt.
The last mask should have 1s below the end bit.
Referenced by df_rd_bb_local_compute_process_def(), dump_insn_info(), and insert_save().
| bool bitmap_single_bit_set_p | ( | ) |
Return true if the bitmap has a single bit set. Otherwise return false.
As there are no completely empty bitmap elements, a second one means we have more than one bit set.
| void bitmap_xor | ( | ) |
DST = A ^ B
Matching elts, generate A ^ B.
Copy a single element.
Ensure that dst->current is valid.
| void bitmap_xor_into | ( | ) |
A ^= B
Copy b_elt.
Matching elts, generate A ^= B.
| DEBUG_FUNCTION void debug | ( | ) |
| DEBUG_FUNCTION void debug_bitmap | ( | ) |
Function to be called from the debugger to print the contents of a bitmap.
| DEBUG_FUNCTION void debug_bitmap_file | ( | ) |
Debugging function to print out the contents of a bitmap.
| void dump_bitmap_statistics | ( | void | ) |
Output per-bitmap memory usage statistics.
|
static |
For given file and line, return descriptor, create new if needed.
| int print_statistics | ( | ) |
Called via hash_table::traverse. Output bitmap descriptor pointed out by SLOT and update statistics.
|
static |
Account the overhead.
Variable Documentation
| bitmap_obstack bitmap_default_obstack |
Referenced by bitmap_obstack_initialize(), df_chain_remove_problem(), and record_operand_use().
|
static |
|
static |
Hashtable mapping bitmap names to descriptors.
|
static |
Vector mapping descriptor ids to descriptors.
|
static |
Referenced by bitmap_elem_to_freelist().
| bitmap_element bitmap_zero_bits |
Global data
|
static |
Next available unique id number for bitmap desciptors.
|
static |
Table of number of set bits in a character, indexed by value of char.
