GCC Middle and Back End API Reference
bitmap.c File Reference
#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"
Include dependency graph for bitmap.c:

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

Functions

static bitmap_descriptor get_bitmap_descriptor ()
void bitmap_register ()
static void register_overhead ()
static void bitmap_elem_to_freelist (bitmap, bitmap_element *)
static void bitmap_element_free (bitmap, bitmap_element *)
static bitmap_elementbitmap_element_allocate (bitmap)
static int bitmap_element_zerop (const bitmap_element *)
static void bitmap_element_link (bitmap, bitmap_element *)
static bitmap_elementbitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int)
static void bitmap_elt_clear_from (bitmap, bitmap_element *)
static bitmap_elementbitmap_find_bit (bitmap, unsigned int)
static void bitmap_elem_to_freelist ()
static void bitmap_element_free ()
static bitmap_elementbitmap_element_allocate ()
void bitmap_elt_clear_from ()
void bitmap_clear ()
void bitmap_obstack_initialize ()
void bitmap_obstack_release ()
bitmap bitmap_obstack_alloc_stat ()
bitmap bitmap_gc_alloc_stat ()
void bitmap_obstack_free ()
static int bitmap_element_zerop ()
static void bitmap_element_link ()
static bitmap_elementbitmap_elt_insert_after ()
void bitmap_copy ()
static bitmap_elementbitmap_find_bit ()
bool bitmap_clear_bit ()
bool bitmap_set_bit ()
int bitmap_bit_p ()
static unsigned long bitmap_popcount ()
unsigned long bitmap_count_bits ()
bool bitmap_single_bit_set_p ()
unsigned bitmap_first_set_bit ()
unsigned bitmap_last_set_bit ()
void bitmap_and ()
bool bitmap_and_into ()
static bool bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, const bitmap_element *src_elt, bool changed)
bool bitmap_and_compl ()
bool bitmap_and_compl_into ()
void bitmap_set_range ()
void bitmap_clear_range ()
void bitmap_compl_and_into ()
static bool bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, const bitmap_element *a_elt, const bitmap_element *b_elt, bool changed)
bool bitmap_ior ()
bool bitmap_ior_into ()
void bitmap_xor ()
void bitmap_xor_into ()
bool bitmap_equal_p ()
bool bitmap_intersect_p ()
bool bitmap_intersect_compl_p ()
bool bitmap_ior_and_compl ()
bool bitmap_ior_and_compl_into ()
bool bitmap_ior_and_into ()
hashval_t bitmap_hash ()
DEBUG_FUNCTION void debug_bitmap_file ()
DEBUG_FUNCTION void debug_bitmap ()
DEBUG_FUNCTION void bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
int print_statistics ()
void dump_bitmap_statistics ()
DEBUG_FUNCTION void debug ()

Variables

static int next_bitmap_desc_id = 0
static vec< bitmap_descriptorbitmap_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_elementbitmap_ggc_free
static const unsigned char popcount_table []

Macro Definition Documentation

#define __alignof__ (   type)    0

Referenced by bitmap_clear().


Typedef Documentation


Function Documentation

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 ( )
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.

unsigned long bitmap_count_bits ( )

Count the number of bits set in the bitmap, and return it.

static void bitmap_elem_to_freelist ( bitmap  ,
bitmap_element  
)
static
static void bitmap_elem_to_freelist ( )
inlinestatic

Add ELEM to the appropriate freelist.

References bitmap_ggc_free, and bitmap_element_def::prev.

static bitmap_element* bitmap_element_allocate ( bitmap  )
static
static bitmap_element* bitmap_element_allocate ( )
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 void bitmap_element_free ( bitmap  ,
bitmap_element  
)
static

Referenced by bitmap_and().

static void bitmap_element_free ( )
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 void bitmap_element_link ( bitmap  ,
bitmap_element  
)
static

Referenced by bitmap_and_compl_into().

static void bitmap_element_link ( )
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 int bitmap_element_zerop ( const bitmap_element )
static
static int bitmap_element_zerop ( )
inlinestatic

Return nonzero if all bits in an element are zero.

static void bitmap_elt_clear_from ( bitmap  ,
bitmap_element  
)
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.

static bool bitmap_elt_copy ( bitmap  dst,
bitmap_element dst_elt,
bitmap_element dst_prev,
const bitmap_element src_elt,
bool  changed 
)
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 bitmap_element* bitmap_elt_insert_after ( bitmap  ,
bitmap_element ,
unsigned  int 
)
static

Referenced by bitmap_and_into(), and bitmap_elt_copy().

static bitmap_element* bitmap_elt_insert_after ( )
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.

static bool bitmap_elt_ior ( bitmap  dst,
bitmap_element dst_elt,
bitmap_element dst_prev,
const bitmap_element a_elt,
const bitmap_element b_elt,
bool  changed 
)
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 bitmap_element* bitmap_find_bit ( bitmap  ,
unsigned  int 
)
static
static bitmap_element* bitmap_find_bit ( )
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.   
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 unsigned long bitmap_popcount ( )
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().

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 bitmap_descriptor get_bitmap_descriptor ( )
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 void register_overhead ( )
static

Account the overhead.


Variable Documentation

int bitmap_default_obstack_depth
static
hash_table<bitmap_desc_hasher> bitmap_desc_hash
static

Hashtable mapping bitmap names to descriptors.

vec<bitmap_descriptor> bitmap_descriptors
static

Vector mapping descriptor ids to descriptors.

bitmap_element* bitmap_ggc_free
static

Referenced by bitmap_elem_to_freelist().

bitmap_element bitmap_zero_bits

Global data

int next_bitmap_desc_id = 0
static

Next available unique id number for bitmap desciptors.

const unsigned char popcount_table[]
static
Initial value:
{
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
}

Table of number of set bits in a character, indexed by value of char.