ctrump/common/bitmap.h File Reference

ビットマップ処理ルーチン More...

#include <strings.h>
#include <string.h>
#include "ctrump/common/dll.h"

Include dependency graph for bitmap.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines
#define	BITMAP_NUM_BITS   (sizeof(ctrump_bitmap_t)*8U)
	ワードあたりのビット数
#define	BYTESIZE_OF_BITMAP(n)   ((((n)+7U)/8U+sizeof(ctrump_bitmap_bits_t)-1U)&~(sizeof(ctrump_bitmap_bits_t)-1U))
	n bit に必要なバイト数
#define	WORDSIZE_OF_BITMAP(n)   ((((n)+(BITMAP_NUM_BITS-1U))/BITMAP_NUM_BITS))
	n bit に必要なワード数
#define	ctrump_bitmap_all_zero(bmp, nelem)   memset(bmp, 0, BYTESIZE_OF_BITMAP(nelem))
	bitmap を 0 初期化
#define	BMP_P   ctrump_bitmap_p
#define	BMP_SET   ctrump_bitmap_set
Typedefs
typedef unsigned int	ctrump_bitmap_bits_t
typedef ctrump_bitmap_bits_t *	ctrump_bitmap_t
Functions
CTRUMP_EXTDEF void	ctrump_bitmap_or (ctrump_bitmap_t dest, ctrump_bitmap_t src0, ctrump_bitmap_t src1, unsigned int length)
CTRUMP_EXTDEF void	ctrump_bitmap_nor (ctrump_bitmap_t dest, ctrump_bitmap_t src0, ctrump_bitmap_t src1, unsigned int length)
CTRUMP_EXTDEF void	ctrump_bitmap_nand (ctrump_bitmap_t dest, ctrump_bitmap_t src0, ctrump_bitmap_t src1, unsigned int length)
CTRUMP_EXTDEF void	ctrump_bitmap_and (ctrump_bitmap_t dest, ctrump_bitmap_t src0, ctrump_bitmap_t src1, unsigned int length)
CTRUMP_EXTDEF void	ctrump_bitmap_nand_or (ctrump_bitmap_t dest, ctrump_bitmap_t src0, ctrump_bitmap_t src1, ctrump_bitmap_t src2, unsigned int length)
CTRUMP_EXTDEF void	ctrump_bitmap_copy (ctrump_bitmap_t dest, ctrump_bitmap_t src, unsigned int length)
CTRUMP_EXTDEF int	ctrump_bitmap_eq (ctrump_bitmap_t x, ctrump_bitmap_t y, unsigned int length)
CTRUMP_EXTDEF void	ctrump_bitmap_tostr (char *buf, ctrump_bitmap_t x, unsigned int length)
	文字列へ変換する buf はlength以上の長さを持つこと
CTRUMP_EXTDEF int	ctrump_print_bitmap_stderr (ctrump_bitmap_t x, unsigned int length)
	ビットマップの文字列表現をstderrへ出力(デバッグ用)
CTRUMP_EXTDEF int	ctrump_bitmap_popcnt (ctrump_bitmap_t bmp, unsigned int length)
	立っているビットの数を数える
static int	ctrump_bitmap_ffs (ctrump_bitmap_t bmp, unsigned int length)
	最左ビットの位置を返す 全ビットがクリアされている場合は-1を返す
static void	ctrump_bitmap_set (ctrump_bitmap_t bmp, unsigned int idx)
	ビットの設定
static void	ctrump_bitmap_clear (ctrump_bitmap_t bmp, unsigned int idx)
	ビットの消去
static int	ctrump_bitmap_p (ctrump_bitmap_t bmp, unsigned int idx)
	ビットが立っていなければ0、それ以外ならば0以外を返す
static void	ctrump_bitmap_clear_all (ctrump_bitmap_t bmp, unsigned int length)
	全ビット消去
static void	ctrump_bitmap_set_all (ctrump_bitmap_t bmp, unsigned int length)
	全ビット設定
CTRUMP_EXTDEF ctrump_bitmap_t	ctrump_bmp_alloc (unsigned int nbits, struct ctrump_mempool *pool)
	ビットマップを割り当てる
CTRUMP_EXTDEF ctrump_bitmap_t	ctrump_bmp_zero (unsigned int nbits, struct ctrump_mempool *pool)
	0クリアされたビットマップを割り当てる
CTRUMP_EXTDEF ctrump_bitmap_t	ctrump_bmp_fill (unsigned int nbits, struct ctrump_mempool *pool)
	全ビットが立ったビットマップを割り当てる

---

Detailed Description

ビットマップ処理ルーチン

各ビットマップは、ワード中の各ビットで表現される ビットマップ列の長さがワード長より短かい場合、余ったビットの値は未定義。

ffs, popcount, eq は余ったビットの値に影響を受けない

Definition in file bitmap.h.

---

Define Documentation

#define BITMAP_NUM_BITS   (sizeof(ctrump_bitmap_t)*8U)

ワードあたりのビット数

Definition at line 57 of file bitmap.h.

Referenced by clear_unused_bit(), and ctrump_bitmap_ffs().

#define BMP_P   ctrump_bitmap_p

Definition at line 205 of file bitmap.h.

Referenced by build_cfg_stmt(), dfs_order(), and recog_exit_cond_cmp().

#define BMP_SET   ctrump_bitmap_set

Definition at line 206 of file bitmap.h.

Referenced by dfs_order().

#define BYTESIZE_OF_BITMAP

(

n

)

((((n)+7U)/8U+sizeof(ctrump_bitmap_bits_t)-1U)&~(sizeof(ctrump_bitmap_bits_t)-1U))

n bit に必要なバイト数

Definition at line 60 of file bitmap.h.

Referenced by ctrump_bmp_alloc(), ctrump_bmp_fill(), and ctrump_bmp_zero().

#define ctrump_bitmap_all_zero	(	bmp,
		nelem		)	memset(bmp, 0, BYTESIZE_OF_BITMAP(nelem))

bitmap を 0 初期化

Definition at line 66 of file bitmap.h.

#define WORDSIZE_OF_BITMAP

(

n

)

((((n)+(BITMAP_NUM_BITS-1U))/BITMAP_NUM_BITS))

n bit に必要なワード数

Definition at line 63 of file bitmap.h.

Referenced by ctrump_bitmap_clear_all(), ctrump_bitmap_copy(), ctrump_bitmap_eq(), ctrump_bitmap_ffs(), ctrump_bitmap_popcnt(), ctrump_bitmap_set_all(), ctrump_bmp_fill(), and ctrump_bmp_zero().

---

Typedef Documentation

typedef unsigned int ctrump_bitmap_bits_t

Definition at line 52 of file bitmap.h.

typedef ctrump_bitmap_bits_t* ctrump_bitmap_t

Definition at line 54 of file bitmap.h.

---

Function Documentation

CTRUMP_EXTDEF void ctrump_bitmap_and	(	ctrump_bitmap_t	dest,
		ctrump_bitmap_t	src0,
		ctrump_bitmap_t	src1,
		unsigned int	length
	)

Referenced by find_loop_carry_dependency(), and recog_reduction().

static void ctrump_bitmap_clear	(	ctrump_bitmap_t	bmp,
		unsigned int	idx
	)			[inline, static]

ビットの消去

Definition at line 158 of file bitmap.h.

Referenced by find_iv(), insert_phi(), merge_reduc_op(), recog_reduction(), and recog_reduction_domtree().

static void ctrump_bitmap_clear_all	(	ctrump_bitmap_t	bmp,
		unsigned int	length
	)			[inline, static]

全ビット消去

Definition at line 182 of file bitmap.h.

References WORDSIZE_OF_BITMAP.

CTRUMP_EXTDEF void ctrump_bitmap_copy	(	ctrump_bitmap_t	dest,
		ctrump_bitmap_t	src,
		unsigned int	length
	)

Definition at line 70 of file bitmap.c.

References WORDSIZE_OF_BITMAP.

Referenced by calc_df(), ctrump_find_iv_node(), and insert_phi().

CTRUMP_EXTDEF int ctrump_bitmap_eq	(	ctrump_bitmap_t	x,
		ctrump_bitmap_t	y,
		unsigned int	length
	)

Definition at line 112 of file bitmap.c.

References WORDSIZE_OF_BITMAP.

Referenced by calc_df().

static int ctrump_bitmap_ffs	(	ctrump_bitmap_t	bmp,
		unsigned int	length
	)			[inline, static]

最左ビットの位置を返す 全ビットがクリアされている場合は-1を返す

Definition at line 127 of file bitmap.h.

References BITMAP_NUM_BITS, and WORDSIZE_OF_BITMAP.

Referenced by insert_phi(), and recog_reduction().

CTRUMP_EXTDEF void ctrump_bitmap_nand	(	ctrump_bitmap_t	dest,
		ctrump_bitmap_t	src0,
		ctrump_bitmap_t	src1,
		unsigned int	length
	)

Referenced by find_invariant(), find_iv(), find_loop_carry_dependency(), and recog_reduction().

CTRUMP_EXTDEF void ctrump_bitmap_nand_or	(	ctrump_bitmap_t	dest,
		ctrump_bitmap_t	src0,
		ctrump_bitmap_t	src1,
		ctrump_bitmap_t	src2,
		unsigned int	length
	)

Referenced by calc_df(), and find_loop_carry_dependency().

CTRUMP_EXTDEF void ctrump_bitmap_nor	(	ctrump_bitmap_t	dest,
		ctrump_bitmap_t	src0,
		ctrump_bitmap_t	src1,
		unsigned int	length
	)

CTRUMP_EXTDEF void ctrump_bitmap_or	(	ctrump_bitmap_t	dest,
		ctrump_bitmap_t	src0,
		ctrump_bitmap_t	src1,
		unsigned int	length
	)

Referenced by calc_df(), and init_analyze_loop_node_info().

static int ctrump_bitmap_p	(	ctrump_bitmap_t	bmp,
		unsigned int	idx
	)			[inline, static]

ビットが立っていなければ0、それ以外ならば0以外を返す

Definition at line 170 of file bitmap.h.

Referenced by analyze_subscript_coef(), bitmap_item(), bitmap_str(), check_var_bmp_p(), classify_memop(), ctrump_bitmap_tostr(), extract_load_store_expr_rval(), find_iv(), insert_phi(), is_invariant_expr(), merge_reduc_op(), recog_array_index(), and single_expr_subscripts_to_loop_subscript().

CTRUMP_EXTDEF int ctrump_bitmap_popcnt	(	ctrump_bitmap_t	bmp,
		unsigned int	length
	)

立っているビットの数を数える

Definition at line 205 of file bitmap.c.

References clear_unused_bit(), and WORDSIZE_OF_BITMAP.

Referenced by bitmap_pop(), insert_phi(), and recog_reduction().

static void ctrump_bitmap_set	(	ctrump_bitmap_t	bmp,
		unsigned int	idx
	)			[inline, static]

ビットの設定

Definition at line 146 of file bitmap.h.

Referenced by add_var_store(), build_cfg(), build_label_ref(), classify_memop(), extract_load_store_assign(), extract_load_store_expr_rval(), find_iv(), init_analyze_loop_node_info(), and insert_phi().

static void ctrump_bitmap_set_all	(	ctrump_bitmap_t	bmp,
		unsigned int	length
	)			[inline, static]

全ビット設定

Definition at line 195 of file bitmap.h.

References WORDSIZE_OF_BITMAP.

Referenced by recog_reduction().

CTRUMP_EXTDEF void ctrump_bitmap_tostr	(	char *	buf,
		ctrump_bitmap_t	x,
		unsigned int	length
	)

文字列へ変換する buf はlength以上の長さを持つこと

Definition at line 137 of file bitmap.c.

References ctrump_bitmap_p().

Referenced by ctrump_print_bitmap_stderr().

CTRUMP_EXTDEF ctrump_bitmap_t ctrump_bmp_alloc	(	unsigned int	nbits,
		struct ctrump_mempool *	pool
	)

ビットマップを割り当てる

Definition at line 197 of file bitmap.c.

References BYTESIZE_OF_BITMAP, and ctrump_mempool_alloc.

Referenced by recog_reduction().

CTRUMP_EXTDEF ctrump_bitmap_t ctrump_bmp_fill	(	unsigned int	nbits,
		struct ctrump_mempool *	pool
	)

全ビットが立ったビットマップを割り当てる

Definition at line 181 of file bitmap.c.

References BYTESIZE_OF_BITMAP, ctrump_mempool_alloc, and WORDSIZE_OF_BITMAP.

CTRUMP_EXTDEF ctrump_bitmap_t ctrump_bmp_zero	(	unsigned int	nbits,
		struct ctrump_mempool *	pool
	)

0クリアされたビットマップを割り当てる

Definition at line 165 of file bitmap.c.

References BYTESIZE_OF_BITMAP, ctrump_mempool_alloc, and WORDSIZE_OF_BITMAP.

CTRUMP_EXTDEF int ctrump_print_bitmap_stderr	(	ctrump_bitmap_t	x,
		unsigned int	length
	)

ビットマップの文字列表現をstderrへ出力(デバッグ用)

Definition at line 152 of file bitmap.c.

References ctrump_bitmap_tostr().