ctrump/analyzer/loop.c File Reference

ループを解析する More...

#include "ctrump/analyzer/loop.h"
#include "ctrump/analyzer/peel.h"
#include "ctrump/analyzer/deptest.h"
#include "ctrump/common/intmap.h"
#include "ctrump/common/varray.h"
#include "ctrump/common/queue.h"
#include "ctrump/common/mempool.h"
#include "ctrump/common/bitmap.h"
#include "ctrump/common/abort.h"
#include "ctrump/ast/ast.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

Include dependency graph for loop.c:

Go to the source code of this file.

Data Structures
struct	loop_cfg_node
	ループに含まれるBB More...
struct	iv_info
	帰納変数の解析情報 More...
struct	parallel_access_info
	ループ中でのメモリアクセスの情報 More...
struct	add_stack_elem
	加算演算解析スタックの要素 More...
struct	bb_info
	ループ解析で使うBBの情報 More...
struct	analyze_loop_node_info
	ループ解析情報 More...
struct	recog_reduction_info
	縮約演算の解析情報 More...
Defines
#define	zero_bmp   ctrump_bmp_zero
#define	fill_bmp   ctrump_bmp_fill
#define	PARALLEL_ACCESS_PARTIAL   (1<<0)
#define	PARALLEL_ACCESS_OP_ASSIGN   (1<<1)
#define	PARALLEL_ACCESS_INCPTR   (1<<2)
#define	PARALLEL_ACCESS_INVARIANT_PTR   (1<<3)
#define	MAX(a, b)   (((a)>(b))?(a):(b))
	max coffee
#define	append_array_not_invariant(a, arr, ns, ss, ats, ate, alloc)   append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_ARRAY_NOT_INVARIANT,alloc)
#define	append_subscript_not_inductive(a, arr, ns, ss, ats, ate, alloc)   append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_SUBSCRIPT_NOT_INDUCTIVE,alloc)
#define	append_complicated_array(a, arr, ns, ss, ats, ate, alloc)   append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_COMPLICATED_ARRAY,alloc)
Typedefs
typedef void(*	parallel_array_func_t )(struct ctrump_varray *access_info, struct ctrump_var *invariant_var, int num_subscript, struct ctrump_loop_subscript *subscripts, int num_constraint, struct ctrump_loop_subscript_constraint *constraints, int flags, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *alloc)
typedef void(*	parallel_pointer_func_t )(struct ctrump_varray *access_info, struct ctrump_var *inductive_var, struct ctrump_mempool *alloc)
Enumerations
enum	loop_cfg_node_code { LOOP_CFG_NODE_INNER_LOOP, LOOP_CFG_NODE_BB }
	ループに含まれるのBBの種類 More...
enum	parallel_access_type { LOAD, STORE }
Functions
static void	find_invariant (struct ctrump_cfg *cfg, ctrump_bitmap_t invariant, ctrump_bitmap_t use, ctrump_bitmap_t modify)
	ループ不変値を探す
static int	recog_inductive (struct iv_info *recog, struct ctrump_pdg_node *pdg)
	帰納変数かどうかのチェック
static void	find_loop_carry_dependency (ctrump_bitmap_t modified_and_live_after_loop, ctrump_bitmap_t loop_carry_dep, struct ctrump_bb *cond_bb, struct ctrump_bb *next_bb, int num_bb, ctrump_bitmap_t used, ctrump_bitmap_t modify, ctrump_bitmap_t inductive, int num_var)
	ループ繰り越し依存の変数を見つける
static void	find_iv (ctrump_bitmap_t inductive, struct loop_cfg_node *bbs, struct ctrump_loop_cfg_info *loop_cfg, ctrump_bitmap_t is_conditional_bb, int num_bb, int num_var, struct iv_info *iv_recogs, struct ctrump_intmap *var_info_map)
	帰納変数を探す
static struct parallel_access_info *	append_access_info (struct ctrump_varray *access_info, struct ctrump_var *invariant_var, int num_subscript, struct ctrump_loop_subscript *subscripts, int num_constraint, struct ctrump_loop_subscript_constraint *constraints, enum parallel_access_type type, int flags, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *alloc)
static int	check_var_bmp_p (struct ctrump_var *var, ctrump_bitmap_t bmp, struct ctrump_intmap *var_info_map)
	var_info_mapから変数の番号を引いた後、 bmpの中でその番号が示すビットが立っているかどうかをチェック
static void	parallel_store (struct ctrump_varray *access_info, struct ctrump_var *invariant_var, int num_subscript, struct ctrump_loop_subscript *subscripts, int num_constraint, struct ctrump_loop_subscript_constraint *constraints, int flags, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *tmp_alloc)
	メモリストア演算の追加
static void	parallel_load (struct ctrump_varray *access_info, struct ctrump_var *invariant_var, int num_subscript, struct ctrump_loop_subscript *subscripts, int num_constraint, struct ctrump_loop_subscript_constraint *constraints, int flags, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *tmp_alloc)
	メモリロード演算の追加
static void	append_random_access_array (struct ctrump_varray *access, struct ctrump_expr *array, int num_subscript, struct ctrump_subscript *subscripts, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, enum ctrump_random_access_code code, struct ctrump_mempool *alloc)
static void	append_complicated_subscript (struct ctrump_varray *access, struct ctrump_expr *subscript_expr, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *alloc)
static void	append_index_var_not_inductive (struct ctrump_varray *access, struct ctrump_var *var, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *alloc)
static void	append_multiple_scaled_index (struct ctrump_varray *access, struct ctrump_expr *index0, struct ctrump_expr *index1, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *alloc)
static int	analyze_subscript_coef (struct ctrump_expr *e, struct ctrump_expr **next_level_index_expr, struct ctrump_var **coef_var, ctrump_bitmap_t invariant, struct ctrump_intmap *var_info_map)
	添字式から係数を取り出す
static int	single_expr_subscripts_to_loop_subscript (struct ctrump_varray *random_access, struct ctrump_varray *indices, int *constant_offset, struct ctrump_expr *subscript_expr, struct ctrump_expr **next_level_index_ret, struct ctrump_var **coef_var, struct iv_info **iv_level, ctrump_bitmap_t invariant, ctrump_bitmap_t *inductive_bmp, struct ctrump_intmap *var_info_map, int loop_level, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *tmp_alloc)
	式で表現されたひとつの添字式から、真の添字と思われる式を取り出す
static int	expr_subscripts_to_loop_subscript (struct ctrump_varray *random_access, int num_subscript, struct ctrump_subscript *subscripts, int *num_loop_subscript, struct ctrump_loop_subscript **ret_subscripts, int *num_constraint, struct ctrump_loop_subscript_constraint **ret_constraints, int ptr_incr, int ptr_incr_iv_level, int loop_level, struct iv_info **iv_level, struct ctrump_loop_exit **exit_level, ctrump_bitmap_t invariant, ctrump_bitmap_t *inductive_bmp, struct ctrump_intmap *var_info_map, struct ctrump_expr *array, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *tmp_alloc, struct ctrump_mempool *alloc, int *id)
	配列アクセスを見つける a[i + 4][j + 3] => array(a , subscript=[(iv=i, offset=4), (iv=j, offset=3)] )
static void	recog_array_index (parallel_array_func_t parallel_func, struct ctrump_varray *parallel_access, struct ctrump_varray *random_access, struct ctrump_memory_access *memory_access, ctrump_bitmap_t invariant, ctrump_bitmap_t invariant_on_loop_top, ctrump_bitmap_t *inductive, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_intmap *var_info_map, int flags, struct iv_info **iv_level, struct ctrump_loop_exit **exit_level, int loop_level, const struct ctrump_abi *abi, struct ctrump_mempool *tmp_alloc, struct ctrump_mempool *loop_alloc, int *id)
	配列アクセスのインデクスを見つける
int	ctrump_loop_index_equal (const struct ctrump_loop_index *i1, const struct ctrump_loop_index *i2)
	インデクスが等しいかどうか
int	ctrump_loop_subscript_equal (const struct ctrump_loop_subscript *s1, const struct ctrump_loop_subscript *s2)
	添字が等しいかどうか
int	ctrump_loop_index_hash (const struct ctrump_loop_index *i0)
int	ctrump_loop_subscript_hash (const struct ctrump_loop_subscript *s0)
	ハッシュ値(なるべくユニークになるように努力した値)を返す
static void	append_memory_access (struct ctrump_varray *acc, struct ctrump_ordered_memory_load_store_node *ordered, enum ctrump_load_store_t lscode, struct parallel_access_info *ai, struct ctrump_mempool *tmp_alloc, struct ctrump_mempool *loop_alloc, struct ctrump_intmap *var_info_map, struct iv_info *iv_info, int *id)
static void	classify_memop (struct ctrump_loop_info_node *loop_info_node, struct loop_cfg_node *bbs, ctrump_bitmap_t is_conditional_bb, int num_bb, int all_num_bb_in_cfg, ctrump_bitmap_t invariant, ctrump_bitmap_t invariant_on_loop_top, ctrump_bitmap_t *inductive, int num_var, struct ctrump_intmap *var_info_map, struct iv_info **iv_level, struct ctrump_loop_exit **exit_level, const struct ctrump_abi *abi, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc, int *id)
	メモリアクセスがランダムアクセスかシーケンシャルアクセスかを分類する
static struct bb_info *	alloc_bb_info (struct ctrump_mempool *alloc, struct ctrump_bb *bb)
static int	build_bfs_order (struct ctrump_intmap *ret, struct ctrump_bb *cond_bb, struct ctrump_bb *body_bb, struct loop_cfg_node **bfs_order_ret_ptr, struct ctrump_mempool *tmp_alloc)
	深さ優先探索した順序を作る
static int	get_var_id (struct ctrump_var *var, struct ctrump_intmap *var_info_map)
static int	is_invariant_expr (struct ctrump_expr *expr, ctrump_bitmap_t invariant, struct ctrump_intmap *var_info_map)
	式がループ不変値かどうかをチェックする
static void	recog_exit_cond_cmp (struct ctrump_loop_exit *loop_exit, struct ctrump_expr *lhs, struct ctrump_expr *rhs, ctrump_bitmap_t inductive, ctrump_bitmap_t invariant, struct ctrump_intmap *var_info_map, struct iv_info *iv, enum ctrump_expr_code cmp_op)
	ループ脱出条件を解析する
static void	recog_exit_cond (struct ctrump_loop_exit *loop_exit, struct ctrump_expr *cond_expr, ctrump_bitmap_t inductive, ctrump_bitmap_t invariant, struct ctrump_intmap *var_info_map, struct iv_info *iv_info)
	ループ脱出条件を解析する
static void	init_analyze_loop_node_info (struct analyze_loop_node_info *dest, struct ctrump_cfg *cfg, struct ctrump_loop_info_node *node, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc)
	ループ解析情報の初期化
static int	ctrump_find_iv_node (struct ctrump_loop_info *loop_info, struct ctrump_loop_info_node *loop_info_node, struct analyze_loop_node_info *analyze_info, struct ctrump_cfg *cfg, struct ctrump_intmap *var_info_map, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc, int id)
	IVを探す.
static int	assign_nest_level (struct ctrump_loop_info_node *loop_tree_node, int max_nest_level, int nest_level)
	各loop_info_nodeにネストレベルを割り当てる
static int	analyze_loop_iv (struct ctrump_loop_info *dest, struct ctrump_loop_info_node **dfs_order, int num_node, struct analyze_loop_node_info *analyze_info, struct ctrump_cfg *cfg, struct ctrump_intmap *var_info_map, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc, int id)
	IVを探す.
static void	analyze_memory_access_level (struct ctrump_loop_info *dest, struct ctrump_loop_info_node *loop_tree_node, struct analyze_loop_node_info *analyze_info, struct ctrump_cfg *cfg, struct ctrump_intmap *var_info_map, const struct ctrump_abi *abi, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc, struct iv_info **iv_level, ctrump_bitmap_t *ivbmp_level, ctrump_bitmap_t invariant_on_loop_top, struct ctrump_loop_exit **exit_level, int *id)
	ループ中のメモリアクセスを調べる
static void	analyze_memory_access (struct ctrump_loop_info *dest, struct ctrump_loop_info_node *loop_tree_node, struct analyze_loop_node_info *analyze_info, struct ctrump_cfg *cfg, struct ctrump_intmap *var_info_map, const struct ctrump_abi *abi, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc, int *id)
	ループ中のメモリアクセスを調べる
static int	count_loop_node (struct ctrump_loop_info_node *node, int dfs_order_index)
	ループの個数を数え、DFSで辿ったときの順序を求める
static int	build_dfs_order (struct ctrump_loop_info_node **dfs_order, struct ctrump_loop_info_node *node, int dfs_order_index)
	DFS順のBBの配列をつくる.
static void	init_analyze_info (struct analyze_loop_node_info *info, struct ctrump_loop_info_node **node_dfs_order, int num_node, struct ctrump_cfg *cfg, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc)
	解析情報の初期化
static void	find_loop_entry (struct ctrump_loop_info_node **nodes, int num_node)
	ループ入り口のBBを見つける
static void	iv_canonicalize (struct ctrump_loop_info_node **dfs_order, struct analyze_loop_node_info *info, int num_node)
	未実装
static void	loop_exit_analyze (struct ctrump_loop_info_node **nodes, struct analyze_loop_node_info *info, int num_node, struct ctrump_intmap *var_info_map)
	ループ脱出情報を解析する
static void	merge_reduc_op (ctrump_bitmap_t is_reduc, ctrump_bitmap_t is_initial, struct recog_reduction_info *reduc_list, int var_idx, enum ctrump_reductive_expr_code merge_op, struct ctrump_stmt *at)
	縮約演算をひとつにする いまのところは違う種類の演算が出てくると縮約演算とはみなされない
static void	recog_reduction_domtree (struct ctrump_bb *bb, struct ctrump_bb *exit_bb, struct ctrump_intmap *var_info_map, int num_var, ctrump_bitmap_t is_reduc, ctrump_bitmap_t is_initial, struct recog_reduction_info *reduc_list)
	縮約演算を見つける
static void	recog_reduction (struct ctrump_loop_info_node **loops, int num_loop_node, struct analyze_loop_node_info *info_list, struct ctrump_intmap *var_info_map, struct ctrump_cfg_var_info *var_info_list, int num_var, struct ctrump_mempool *loop_alloc, struct ctrump_mempool *tmp_alloc)
	縮約演算を見つける
int	ctrump_analyze_loop (struct ctrump_loop_info *dest, int *level_depth, struct ctrump_loop_info_node *loop_tree_node, struct ctrump_cfg *cfg, struct ctrump_intmap *var_info_map, const struct ctrump_abi *abi, struct ctrump_mempool *loop_alloc, int id)
	ループを解析する
Variables
static enum ctrump_reductive_expr_code	incr_op_to_reduc_op []

---

Detailed Description

ループを解析する

• ループ中のメモリアクセスを解析する
• ループ回数を解析する
• ループ構造を解析する

ここで使っている言葉の説明

帰納変数(induction variable : iv) : ループ回数 * 定数 + 定数 という形をしている変数 conditional bb : 条件によって実行されたりされなかったりするBB

Definition in file loop.c.

---

Define Documentation

#define append_array_not_invariant	(	a,
		arr,
		ns,
		ss,
		ats,
		ate,
		alloc		)	append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_ARRAY_NOT_INVARIANT,alloc)

Definition at line 454 of file loop.c.

Referenced by recog_array_index().

#define append_complicated_array	(	a,
		arr,
		ns,
		ss,
		ats,
		ate,
		alloc		)	append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_COMPLICATED_ARRAY,alloc)

Definition at line 458 of file loop.c.

Referenced by recog_array_index().

#define append_subscript_not_inductive	(	a,
		arr,
		ns,
		ss,
		ats,
		ate,
		alloc		)	append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_SUBSCRIPT_NOT_INDUCTIVE,alloc)

Definition at line 456 of file loop.c.

#define fill_bmp   ctrump_bmp_fill

Definition at line 59 of file loop.c.

#define MAX	(	a,
		b		)	(((a)>(b))?(a):(b))

max coffee

Definition at line 381 of file loop.c.

#define PARALLEL_ACCESS_INCPTR   (1<<2)

Definition at line 304 of file loop.c.

#define PARALLEL_ACCESS_INVARIANT_PTR   (1<<3)

Definition at line 305 of file loop.c.

#define PARALLEL_ACCESS_OP_ASSIGN   (1<<1)

Definition at line 303 of file loop.c.

Referenced by classify_memop(), and parallel_store().

#define PARALLEL_ACCESS_PARTIAL   (1<<0)

Definition at line 302 of file loop.c.

Referenced by classify_memop(), and parallel_store().

#define zero_bmp   ctrump_bmp_zero

Definition at line 58 of file loop.c.

---

Typedef Documentation

typedef void(* parallel_array_func_t)(struct ctrump_varray *access_info, struct ctrump_var *invariant_var, int num_subscript, struct ctrump_loop_subscript *subscripts, int num_constraint, struct ctrump_loop_subscript_constraint *constraints, int flags, struct ctrump_stmt *at_stmt, struct ctrump_expr *at_expr, struct ctrump_mempool *alloc)

Definition at line 1008 of file loop.c.

typedef void(* parallel_pointer_func_t)(struct ctrump_varray *access_info, struct ctrump_var *inductive_var, struct ctrump_mempool *alloc)

Definition at line 1241 of file loop.c.

---

Enumeration Type Documentation

enum loop_cfg_node_code

ループに含まれるのBBの種類

Enumerator:

LOOP_CFG_NODE_INNER_LOOP	内側のループの先頭BB
LOOP_CFG_NODE_BB	普通のBB

Definition at line 64 of file loop.c.

enum parallel_access_type

Enumerator:

LOAD
STORE

Definition at line 297 of file loop.c.

---

Function Documentation

static struct bb_info* alloc_bb_info	(	struct ctrump_mempool *	alloc,
		struct ctrump_bb *	bb
	)			[static, read]

Definition at line 1466 of file loop.c.

References bb_info::bb, and ctrump_mempool_alloc.

Referenced by build_bfs_order().

static int analyze_loop_iv	(	struct ctrump_loop_info *	dest,
		struct ctrump_loop_info_node **	dfs_order,
		int	num_node,
		struct analyze_loop_node_info *	analyze_info,
		struct ctrump_cfg *	cfg,
		struct ctrump_intmap *	var_info_map,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc,
		int	id
	)			[static]

IVを探す.

Definition at line 1880 of file loop.c.

References ctrump_find_iv_node().

Referenced by ctrump_analyze_loop().

static void analyze_memory_access	(	struct ctrump_loop_info *	dest,
		struct ctrump_loop_info_node *	loop_tree_node,
		struct analyze_loop_node_info *	analyze_info,
		struct ctrump_cfg *	cfg,
		struct ctrump_intmap *	var_info_map,
		const struct ctrump_abi *	abi,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc,
		int *	id
	)			[static]

ループ中のメモリアクセスを調べる

Definition at line 1955 of file loop.c.

References analyze_memory_access_level(), ctrump_loop_info_node::invariant_var, OffloadSpe::iv_level, and ctrump_loop_info::nest_level.

Referenced by ctrump_analyze_loop().

static void analyze_memory_access_level	(	struct ctrump_loop_info *	dest,
		struct ctrump_loop_info_node *	loop_tree_node,
		struct analyze_loop_node_info *	analyze_info,
		struct ctrump_cfg *	cfg,
		struct ctrump_intmap *	var_info_map,
		const struct ctrump_abi *	abi,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc,
		struct iv_info **	iv_level,
		ctrump_bitmap_t *	ivbmp_level,
		ctrump_bitmap_t	invariant_on_loop_top,
		struct ctrump_loop_exit **	exit_level,
		int *	id
	)			[static]

ループ中のメモリアクセスを調べる

Definition at line 1907 of file loop.c.

References analyze_loop_node_info::bfs_order, ctrump_loop_info_node::children, classify_memop(), ctrump_loop_info_node::dfs_order, ctrump_loop_info_node::exit_info, ctrump_loop_info_node::inductive_var, ctrump_loop_info_node::invariant_var, analyze_loop_node_info::is_conditional_bb, analyze_loop_node_info::iv_info, ctrump_loop_info_node::nest_level, ctrump_cfg::num_bb, analyze_loop_node_info::num_bb, ctrump_loop_info_node::num_child, and ctrump_cfg::num_var.

Referenced by analyze_memory_access().

static int analyze_subscript_coef	(	struct ctrump_expr *	e,
		struct ctrump_expr **	next_level_index_expr,
		struct ctrump_var **	coef_var,
		ctrump_bitmap_t	invariant,
		struct ctrump_intmap *	var_info_map
	)			[static]

添字式から係数を取り出す

Definition at line 523 of file loop.c.

References ctrump_expr::binary, ctrump_expr::code, ctrump_bitmap_p(), CTRUMP_EXPR_BIN_MUL, CTRUMP_EXPR_VARREF, ctrump_intmap_lookup(), ctrump_peel_paren(), ctrump_var::id, ctrump_cfg_var_info::index, ctrump_binary_expr::lhs, ctrump_binary_expr::rhs, rhs, ctrump_expr::u, ctrump_varref_expr::var, and ctrump_expr::varref.

Referenced by single_expr_subscripts_to_loop_subscript().

static struct parallel_access_info* append_access_info	(	struct ctrump_varray *	access_info,
		struct ctrump_var *	invariant_var,
		int	num_subscript,
		struct ctrump_loop_subscript *	subscripts,
		int	num_constraint,
		struct ctrump_loop_subscript_constraint *	constraints,
		enum parallel_access_type	type,
		int	flags,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	alloc
	)			[static, read]

Returns:

access info if found NULL if not found

Note:

if not found append new info as type

Definition at line 332 of file loop.c.

References parallel_access_info::at_expr, parallel_access_info::at_stmt, parallel_access_info::constraints, ctrump_varray::elements, parallel_access_info::flags, parallel_access_info::invariant, parallel_access_info::num_constraint, parallel_access_info::num_subscript, parallel_access_info::subscripts, parallel_access_info::type, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by parallel_load(), and parallel_store().

static void append_complicated_subscript	(	struct ctrump_varray *	access,
		struct ctrump_expr *	subscript_expr,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	alloc
	)			[static]

Definition at line 462 of file loop.c.

References ctrump_random_access::access_at_expr, ctrump_random_access::access_at_stmt, ctrump_random_access::code, ctrump_random_access::complicated_subscript, CTRUMP_RANDOM_ACCESS_COMPLICATED_SUBSCRIPT, ctrump_random_access::u, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by single_expr_subscripts_to_loop_subscript().

static void append_index_var_not_inductive	(	struct ctrump_varray *	access,
		struct ctrump_var *	var,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	alloc
	)			[static]

Definition at line 480 of file loop.c.

References ctrump_random_access::access_at_expr, ctrump_random_access::access_at_stmt, ctrump_random_access::code, CTRUMP_RANDOM_ACCESS_INDEX_VAR_NOT_INDUCTIVE, ctrump_random_access::index_var_not_inductive, ctrump_random_access::u, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by single_expr_subscripts_to_loop_subscript().

static void append_memory_access	(	struct ctrump_varray *	acc,
		struct ctrump_ordered_memory_load_store_node *	ordered,
		enum ctrump_load_store_t	lscode,
		struct parallel_access_info *	ai,
		struct ctrump_mempool *	tmp_alloc,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_intmap *	var_info_map,
		struct iv_info *	iv_info,
		int *	id
	)			[static]

Definition at line 1246 of file loop.c.

References ctrump_loop_memory_access::array, parallel_access_info::at_expr, ctrump_loop_memory_access::at_expr, parallel_access_info::at_stmt, ctrump_loop_memory_access::at_stmt, ctrump_ordered_memory_load_store_node::code, parallel_access_info::constraints, ctrump_loop_memory_access::constraints, ctrump_loop_memory_access::id, parallel_access_info::invariant, ctrump_varray::nelem, parallel_access_info::num_constraint, ctrump_loop_memory_access::num_constraint, parallel_access_info::num_subscript, ctrump_loop_memory_access::num_subscript, ctrump_ordered_memory_load_store_node::op_index, parallel_access_info::subscripts, ctrump_loop_memory_access::subscripts, VA_LAST_PTR, VA_NEWELEM_P, and ctrump_loop_array::var.

Referenced by classify_memop().

static void append_multiple_scaled_index	(	struct ctrump_varray *	access,
		struct ctrump_expr *	index0,
		struct ctrump_expr *	index1,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	alloc
	)			[static]

Definition at line 499 of file loop.c.

References ctrump_random_access::access_at_expr, ctrump_random_access::access_at_stmt, ctrump_random_access::code, CTRUMP_RANDOM_ACCESS_MULTIPLE_SCALED_INDEX, ctrump_random_access_multiple_scaled_index::index0, ctrump_random_access_multiple_scaled_index::index1, ctrump_random_access::multiple_scaled_index, ctrump_random_access::u, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by single_expr_subscripts_to_loop_subscript().

static void append_random_access_array	(	struct ctrump_varray *	access,
		struct ctrump_expr *	array,
		int	num_subscript,
		struct ctrump_subscript *	subscripts,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		enum ctrump_random_access_code	code,
		struct ctrump_mempool *	alloc
	)			[static]

Definition at line 433 of file loop.c.

References ctrump_random_access::access_at_expr, ctrump_random_access::access_at_stmt, ctrump_random_access::arr_not_invariant, ctrump_array_access::array, ctrump_random_access::code, ctrump_array_access::num_subscript, ctrump_array_access::subscripts, ctrump_random_access::u, VA_LAST_PTR, and VA_NEWELEM_P.

static int assign_nest_level	(	struct ctrump_loop_info_node *	loop_tree_node,
		int	max_nest_level,
		int	nest_level
	)			[static]

各loop_info_nodeにネストレベルを割り当てる

Definition at line 1855 of file loop.c.

References ctrump_loop_info_node::children, ctrump_loop_info_node::nest_level, ctrump_loop_info_node::num_child, and ctrump_loop_info_node::parent.

Referenced by ctrump_analyze_loop().

static int build_bfs_order	(	struct ctrump_intmap *	ret,
		struct ctrump_bb *	cond_bb,
		struct ctrump_bb *	body_bb,
		struct loop_cfg_node **	bfs_order_ret_ptr,
		struct ctrump_mempool *	tmp_alloc
	)			[static]

深さ優先探索した順序を作る

Returns:

number of bb

Definition at line 1481 of file loop.c.

References alloc_bb_info(), loop_cfg_node::bb, bb_info::bb, ctrump_loop_cfg_info::break_bb, loop_cfg_node::code, CTRUMP_BB_IS_LOOP_ENTRY, ctrump_intmap_free(), ctrump_intmap_init(), ctrump_intmap_lookup_add(), ctrump_intmap_resize_pool(), ctrump_mempool_alloc, ctrump_queue_destroy(), ctrump_queue_init(), ctrump_varray_discard(), ctrump_varray_init(), ctrump_varray::elements, ctrump_bb::id, bb_info::index, loop_cfg_node::loop, ctrump_bb::loop_belong_to, LOOP_CFG_NODE_BB, LOOP_CFG_NODE_INNER_LOOP, ctrump_loop_cfg_info::loop_info_node, ctrump_varray::nelem, ctrump_bb::num_succs, QUEUE_POP, QUEUE_PUSH, ctrump_bb::succs, ctrump_loop_cfg_info::u, loop_cfg_node::u, VA_PUSH, and ctrump_intmap_bucket::val.

Referenced by init_analyze_loop_node_info().

static int build_dfs_order	(	struct ctrump_loop_info_node **	dfs_order,
		struct ctrump_loop_info_node *	node,
		int	dfs_order_index
	)			[static]

DFS順のBBの配列をつくる.

Definition at line 1998 of file loop.c.

References ctrump_loop_info_node::children, and ctrump_loop_info_node::num_child.

Referenced by ctrump_analyze_loop().

static int check_var_bmp_p	(	struct ctrump_var *	var,
		ctrump_bitmap_t	bmp,
		struct ctrump_intmap *	var_info_map
	)			[static]

var_info_mapから変数の番号を引いた後、 bmpの中でその番号が示すビットが立っているかどうかをチェック

Definition at line 367 of file loop.c.

References ctrump_bitmap_p(), ctrump_intmap_lookup(), ctrump_var::id, and ctrump_cfg_var_info::index.

Referenced by recog_array_index().

static void classify_memop	(	struct ctrump_loop_info_node *	loop_info_node,
		struct loop_cfg_node *	bbs,
		ctrump_bitmap_t	is_conditional_bb,
		int	num_bb,
		int	all_num_bb_in_cfg,
		ctrump_bitmap_t	invariant,
		ctrump_bitmap_t	invariant_on_loop_top,
		ctrump_bitmap_t *	inductive,
		int	num_var,
		struct ctrump_intmap *	var_info_map,
		struct iv_info **	iv_level,
		struct ctrump_loop_exit **	exit_level,
		const struct ctrump_abi *	abi,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc,
		int *	id
	)			[static]

メモリアクセスがランダムアクセスかシーケンシャルアクセスかを分類する

Definition at line 1281 of file loop.c.

References append_memory_access(), ctrump_memory_access::at_expr, ctrump_memory_access::at_stmt, ctrump_loop_cfg_info::break_bb, ctrump_loop_info_node::cfg_info, ctrump_ordered_memory_load_store_node::code, ctrump_loop_cfg_info::cond_bb, ctrump_bitmap_p(), ctrump_bitmap_set(), CTRUMP_MEMORY_ACCESS_PARTIAL, CTRUMP_MEMORY_LOAD, CTRUMP_MEMORY_STORE, ctrump_mempool_alloc, ctrump_mempool_destroy(), ctrump_mempool_init(), ctrump_varray_copy(), ctrump_varray_init_pool(), ctrump_bb::dfs, ctrump_varray::elements, ctrump_memory_access::flags, ctrump_bb::id_in_cfg, IS_BIN_OP_ASSIGN, LOAD, ctrump_bb::load_store, ctrump_bb::loop_belong_to, ctrump_memory_store::mem_access, ctrump_memory_load::mem_access, ctrump_load_store_set::mem_loads, ctrump_load_store_set::mem_stores, ctrump_varray::nelem, ctrump_loop_info_node::nest_level, ctrump_bb::num_dfs, ctrump_load_store_set::num_memop, ctrump_loop_info_node::num_ordered_loadstore, ctrump_loop_info_node::num_parallel_load, ctrump_loop_info_node::num_parallel_store, ctrump_loop_info_node::num_random_access, ctrump_bb::num_succs, ctrump_ordered_memory_load_store_node::op_index, ctrump_load_store_set::ordered_load_store, ctrump_loop_info_node::ordered_loadstore, PARALLEL_ACCESS_OP_ASSIGN, PARALLEL_ACCESS_PARTIAL, parallel_load(), ctrump_loop_info_node::parallel_loads, parallel_store(), ctrump_loop_info_node::parallel_stores, ctrump_loop_info_node::random_accesses, recog_array_index(), STORE, ctrump_memory_store::store_op, ctrump_bb::succs, parallel_access_info::type, VA_LAST_PTR, VA_NEWELEM_P, and zero_bmp.

Referenced by analyze_memory_access_level().

static int count_loop_node	(	struct ctrump_loop_info_node *	node,
		int	dfs_order_index
	)			[static]

ループの個数を数え、DFSで辿ったときの順序を求める

Definition at line 1981 of file loop.c.

References ctrump_loop_info_node::children, ctrump_loop_info_node::dfs_order, and ctrump_loop_info_node::num_child.

Referenced by ctrump_analyze_loop().

int ctrump_analyze_loop	(	struct ctrump_loop_info *	dest,
		int *	level_depth,
		struct ctrump_loop_info_node *	loop_tree_node,
		struct ctrump_cfg *	cfg,
		struct ctrump_intmap *	var_info_map,
		const struct ctrump_abi *	abi,
		struct ctrump_mempool *	loop_alloc,
		int	id
	)

ループを解析する

Note:

loop should not be complicated loop.

Returns:

next id

Parameters:

dest	出力先
level_depth	最内ループの深さ
loop_tree_node	ループツリーのルート
cfg	このループを含む関数のCFG
var_info_map	id->変数情報マップ
abi	ABI
loop_alloc	このループをアロケートするプール

Definition at line 2256 of file loop.c.

References analyze_loop_iv(), analyze_memory_access(), assign_nest_level(), build_dfs_order(), count_loop_node(), ctrump_get_loop_depinfo(), ctrump_mempool_alloc, ctrump_mempool_destroy(), ctrump_mempool_init(), dfs_order(), find_loop_entry(), init_analyze_info(), iv_canonicalize(), loop_exit_analyze(), ctrump_cfg::num_var, recog_reduction(), and ctrump_cfg::var_info.

Referenced by build_loop_tree_func().

static int ctrump_find_iv_node	(	struct ctrump_loop_info *	loop_info,
		struct ctrump_loop_info_node *	loop_info_node,
		struct analyze_loop_node_info *	analyze_info,
		struct ctrump_cfg *	cfg,
		struct ctrump_intmap *	var_info_map,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc,
		int	id
	)			[static]

IVを探す.

Definition at line 1794 of file loop.c.

References analyze_loop_node_info::bfs_order, ctrump_loop_cfg_info::break_bb, ctrump_loop_info_node::carry_dep, ctrump_loop_info_node::cfg_info, ctrump_loop_cfg_info::cond_bb, ctrump_bitmap_copy(), find_invariant(), find_iv(), find_loop_carry_dependency(), ctrump_loop_info_node::inductive_var, ctrump_loop_info_node::invariant_var, analyze_loop_node_info::is_conditional_bb, analyze_loop_node_info::iv_info, ctrump_loop_info_node::modified_and_live_after_loop, ctrump_loop_info_node::modify, analyze_loop_node_info::num_bb, ctrump_loop_info_node::num_var, ctrump_cfg::num_var, analyze_loop_node_info::tmp_bmp, ctrump_loop_info_node::use, and zero_bmp.

Referenced by analyze_loop_iv().

int ctrump_loop_index_equal	(	const struct ctrump_loop_index *	i1,
		const struct ctrump_loop_index *	i2
	)

インデクスが等しいかどうか

Parameters:

	i1	インデクス
	i2	インデクス

Returns:

等しい場合は1 それ以外0

Definition at line 1109 of file loop.c.

References ctrump_loop_index::code, CTRUMP_LOOP_INDEX_INDUCTIVE, CTRUMP_LOOP_INDEX_INVARIANT, CTRUMP_LOOP_INDEX_POINTER_INC, ctrump_loop_index::flags, ctrump_loop_pointer_inc::incr, ctrump_loop_index::invariant, ctrump_loop_index::iv, ctrump_loop_pointer_inc::iv_level, ctrump_loop_index::ptrinc, ctrump_loop_index::u, and ctrump_loop_iv::var.

Referenced by ctrump_loop_subscript_equal(), and loop_index_equal().

int ctrump_loop_index_hash

(

const struct ctrump_loop_index *

i0

)

Definition at line 1178 of file loop.c.

References ctrump_loop_index::code, CTRUMP_LOOP_INDEX_INDUCTIVE, CTRUMP_LOOP_INDEX_INVARIANT, CTRUMP_LOOP_INDEX_POINTER_INC, ctrump_unreachable, ctrump_symbol::hashval, ctrump_loop_pointer_inc::incr, ctrump_loop_index::invariant, ctrump_loop_index::iv, ctrump_loop_pointer_inc::iv_level, ctrump_var::name, ctrump_loop_index::ptrinc, ctrump_loop_index::u, and ctrump_loop_iv::var.

Referenced by ctrump_loop_subscript_hash().

int ctrump_loop_subscript_equal	(	const struct ctrump_loop_subscript *	s1,
		const struct ctrump_loop_subscript *	s2
	)

添字が等しいかどうか

Parameters:

	s1	添字
	s2	添字

Returns:

等しい場合は1 それ以外0

Definition at line 1137 of file loop.c.

References ctrump_loop_subscript::code, ctrump_loop_index_equal(), CTRUMP_LOOP_SUBSCRIPT_COEF_ARRAYSIZE, CTRUMP_LOOP_SUBSCRIPT_COEF_CONSTANT, CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE, CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL, CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL, ctrump_loop_subscript::indices, ctrump_loop_subscript_record_member::member_name, ctrump_loop_subscript::num_index, ctrump_loop_subscript::offset, ctrump_loop_subscript::ctrump_loop_subscript_scale::record_member, and ctrump_loop_subscript::u.

Referenced by loop_subscript_equal().

int ctrump_loop_subscript_hash

(

const struct ctrump_loop_subscript *

s

)

ハッシュ値(なるべくユニークになるように努力した値)を返す

Parameters:

s

添字

Returns:

等しい場合は1 それ以外0

Definition at line 1195 of file loop.c.

References ctrump_loop_subscript::ctrump_loop_subscript_scale::array_size_coef, ctrump_loop_subscript::code, ctrump_loop_index_hash(), CTRUMP_LOOP_SUBSCRIPT_COEF_ARRAYSIZE, CTRUMP_LOOP_SUBSCRIPT_COEF_CONSTANT, CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE, CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL, CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL, ctrump_symbol::hashval, ctrump_texpr::id, ctrump_loop_subscript::indices, ctrump_loop_subscript::ctrump_loop_subscript_scale::load_record, ctrump_loop_subscript_load_record::load_type, ctrump_loop_subscript_record_member::member_name, ctrump_var::name, ctrump_loop_subscript::num_index, ctrump_loop_subscript::offset, ctrump_loop_subscript::ctrump_loop_subscript_scale::record_member, ctrump_loop_subscript::ctrump_loop_subscript_scale::scale_array_coef, and ctrump_loop_subscript::u.

Referenced by loop_subscript_hash().

static int expr_subscripts_to_loop_subscript	(	struct ctrump_varray *	random_access,
		int	num_subscript,
		struct ctrump_subscript *	subscripts,
		int *	num_loop_subscript,
		struct ctrump_loop_subscript **	ret_subscripts,
		int *	num_constraint,
		struct ctrump_loop_subscript_constraint **	ret_constraints,
		int	ptr_incr,
		int	ptr_incr_iv_level,
		int	loop_level,
		struct iv_info **	iv_level,
		struct ctrump_loop_exit **	exit_level,
		ctrump_bitmap_t	invariant,
		ctrump_bitmap_t *	inductive_bmp,
		struct ctrump_intmap *	var_info_map,
		struct ctrump_expr *	array,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	tmp_alloc,
		struct ctrump_mempool *	alloc,
		int *	id
	)			[static]

配列アクセスを見つける a[i + 4][j + 3] => array(a , subscript=[(iv=i, offset=4), (iv=j, offset=3)] )

Definition at line 740 of file loop.c.

References ctrump_subscript_nd::array_coef, ctrump_loop_index::code, ctrump_loop_subscript::code, ctrump_subscript_nd::code, ctrump_subscript_coef_array::coef, CTRUMP_LOOP_INDEX_POINTER_INC, CTRUMP_LOOP_SUBSCRIPT_COEF_ARRAYSIZE, CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE, CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL, CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL, ctrump_mempool_alloc, ctrump_peel_paren(), CTRUMP_SUBSCRIPT_COEF_ARRAY, CTRUMP_SUBSCRIPT_LOAD_RECORD, CTRUMP_SUBSCRIPT_RECORD_MEMBER, CTRUMP_SUBSCRIPT_RECORD_MEMBER_TERMINAL, CTRUMP_SUBSCRIPT_TERMINAL, ctrump_unreachable, ctrump_varray_copy(), ctrump_varray_discard(), ctrump_varray_init(), ctrump_varray::elements, ctrump_subscript_coef_load_record::expr, ctrump_subscript_terminal::expr, ctrump_subscript_coef_array::expr, ctrump_loop_index::flags, ctrump_loop_subscript::id, ctrump_loop_pointer_inc::incr, ctrump_loop_subscript::indices, ctrump_loop_pointer_inc::iv_level, ctrump_subscript_nd::load_record, ctrump_subscript_coef_load_record::load_type, ctrump_subscript_terminal::load_type, ctrump_subscript_record_member_terminal::load_type, ctrump_loop_subscript_record_member_terminal::load_type, ctrump_subscript_record_member_terminal::member_name, ctrump_loop_subscript_record_member_terminal::member_name, ctrump_subscript_record_member::member_name, ctrump_loop_subscript_record_member::member_name, ctrump_subscript::nd_subscripts, ctrump_varray::nelem, ctrump_loop_subscript::num_index, ctrump_subscript::num_nd_subscript, ctrump_loop_subscript::offset, ctrump_loop_index::ptrinc, ctrump_subscript_nd::record_member, ctrump_loop_subscript::ctrump_loop_subscript_scale::record_member, ctrump_subscript_nd::record_member_terminal, ctrump_loop_subscript::ctrump_loop_subscript_scale::record_member_terminal, ctrump_subscript_record_member_terminal::record_type, ctrump_loop_subscript_record_member_terminal::record_type, ctrump_subscript_record_member::record_type, ctrump_loop_subscript_record_member::record_type, single_expr_subscripts_to_loop_subscript(), ctrump_subscript_nd::terminal, ctrump_loop_index::u, ctrump_subscript_nd::u, ctrump_loop_subscript::u, VA_LAST_PTR, and VA_NEWELEM.

Referenced by recog_array_index().

static void find_invariant	(	struct ctrump_cfg *	cfg,
		ctrump_bitmap_t	invariant,
		ctrump_bitmap_t	use,
		ctrump_bitmap_t	modify
	)			[static]

ループ不変値を探す

Note:

グローバル変数の扱いどうするか

Definition at line 85 of file loop.c.

References ctrump_bitmap_nand(), ctrump_cfg::num_var, and ctrump_bb::num_var.

Referenced by ctrump_find_iv_node().

static void find_iv	(	ctrump_bitmap_t	inductive,
		struct loop_cfg_node *	bbs,
		struct ctrump_loop_cfg_info *	loop_cfg,
		ctrump_bitmap_t	is_conditional_bb,
		int	num_bb,
		int	num_var,
		struct iv_info *	iv_recogs,
		struct ctrump_intmap *	var_info_map
	)			[static]

帰納変数を探す

Parameters:

	inductive	[out] 帰納変数を示すビットマップ
	bb	BBの配列
	loop_cfg	今のループの情報
	is_conditional_bb	conditional bb を示すビットマップ
	num_bb	BBの数
	num_var	変数の数
	iv_recogs	IVの情報
	var_info_map	var id から変数情報を引いてくるマップ

Definition at line 202 of file loop.c.

References loop_cfg_node::bb, loop_cfg_node::code, ctrump_loop_cfg_info::cond_bb, ctrump_bitmap_clear(), ctrump_bitmap_nand(), ctrump_bitmap_p(), ctrump_bitmap_set(), ctrump_intmap_lookup(), ctrump_var::id, ctrump_cfg_var_info::index, ctrump_bb::kill, ctrump_bb::load_store, loop_cfg_node::loop, LOOP_CFG_NODE_BB, LOOP_CFG_NODE_INNER_LOOP, ctrump_loop_cfg_info::loop_pred, ctrump_loop_info_node::modify, ctrump_var_store::new_val, ctrump_phi_node::nodes, ctrump_bb::num_phi, ctrump_bb::num_preds, ctrump_load_store_set::num_store, ctrump_bb::phi_nodes, ctrump_bb::preds, iv_info::reach_at_loop_entry, recog_inductive(), ctrump_load_store_set::stores, loop_cfg_node::u, ctrump_var_store::var, and ctrump_phi_node::var_index.

Referenced by ctrump_find_iv_node().

static void find_loop_carry_dependency	(	ctrump_bitmap_t	modified_and_live_after_loop,
		ctrump_bitmap_t	loop_carry_dep,
		struct ctrump_bb *	cond_bb,
		struct ctrump_bb *	next_bb,
		int	num_bb,
		ctrump_bitmap_t	used,
		ctrump_bitmap_t	modify,
		ctrump_bitmap_t	inductive,
		int	num_var
	)			[static]

ループ繰り越し依存の変数を見つける

Definition at line 151 of file loop.c.

References ctrump_bitmap_and(), ctrump_bitmap_nand(), ctrump_bitmap_nand_or(), ctrump_bb::kill, ctrump_bb::live, and ctrump_bb::use.

Referenced by ctrump_find_iv_node().

static void find_loop_entry	(	struct ctrump_loop_info_node **	nodes,
		int	num_node
	)			[static]

ループ入り口のBBを見つける

Definition at line 2034 of file loop.c.

References ctrump_loop_info_node::cfg_info, ctrump_loop_cfg_info::cond_bb, ctrump_bb::dfs, ctrump_bb::num_dfs, ctrump_bb::num_preds, and ctrump_bb::preds.

Referenced by ctrump_analyze_loop().

static int get_var_id	(	struct ctrump_var *	var,
		struct ctrump_intmap *	var_info_map
	)			[static]

Definition at line 1581 of file loop.c.

References ctrump_intmap_lookup(), ctrump_var::id, and ctrump_cfg_var_info::index.

Referenced by is_invariant_expr(), and recog_exit_cond_cmp().

static void init_analyze_info	(	struct analyze_loop_node_info *	info,
		struct ctrump_loop_info_node **	node_dfs_order,
		int	num_node,
		struct ctrump_cfg *	cfg,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc
	)			[static]

解析情報の初期化

Definition at line 2015 of file loop.c.

References init_analyze_loop_node_info().

Referenced by ctrump_analyze_loop().

static void init_analyze_loop_node_info	(	struct analyze_loop_node_info *	dest,
		struct ctrump_cfg *	cfg,
		struct ctrump_loop_info_node *	node,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc
	)			[static]

ループ解析情報の初期化

Definition at line 1710 of file loop.c.

References loop_cfg_node::bb, analyze_loop_node_info::bfs_order, ctrump_loop_cfg_info::body_start_bb, build_bfs_order(), ctrump_loop_info_node::cfg_info, ctrump_loop_cfg_info::code, loop_cfg_node::code, ctrump_loop_cfg_info::cond_bb, ctrump_bitmap_or(), ctrump_bitmap_set(), CTRUMP_LOOP, ctrump_mempool_alloc, ctrump_bb::dfs, iv_info::incr, analyze_loop_node_info::is_conditional_bb, analyze_loop_node_info::iv_info, ctrump_bb::kill, loop_cfg_node::loop, ctrump_bb::loop_belong_to, LOOP_CFG_NODE_BB, LOOP_CFG_NODE_INNER_LOOP, ctrump_loop_cfg_info::loop_info_node, ctrump_loop_info_node::modify, analyze_loop_node_info::num_bb, ctrump_bb::num_dfs, ctrump_cfg::num_var, analyze_loop_node_info::tmp_bmp, ctrump_loop_cfg_info::u, loop_cfg_node::u, ctrump_bb::use, ctrump_loop_info_node::use, and zero_bmp.

Referenced by init_analyze_info().

static int is_invariant_expr	(	struct ctrump_expr *	expr,
		ctrump_bitmap_t	invariant,
		struct ctrump_intmap *	var_info_map
	)			[static]

式がループ不変値かどうかをチェックする

Definition at line 1595 of file loop.c.

References ctrump_expr::binary, ctrump_expr::code, ctrump_bitmap_p(), CTRUMP_CASE_BIN_ARITH_EXPR, CTRUMP_CASE_BIN_LOG_EXPR, CTRUMP_CASE_CONSTANT_TERM, CTRUMP_EXPR_VARREF, get_var_id(), ctrump_binary_expr::lhs, ctrump_binary_expr::rhs, ctrump_expr::u, ctrump_varref_expr::var, and ctrump_expr::varref.

Referenced by recog_exit_cond_cmp().

static void iv_canonicalize	(	struct ctrump_loop_info_node **	dfs_order,
		struct analyze_loop_node_info *	info,
		int	num_node
	)			[static]

未実装

Definition at line 2070 of file loop.c.

Referenced by ctrump_analyze_loop().

static void loop_exit_analyze	(	struct ctrump_loop_info_node **	nodes,
		struct analyze_loop_node_info *	info,
		int	num_node,
		struct ctrump_intmap *	var_info_map
	)			[static]

ループ脱出情報を解析する

Definition at line 2088 of file loop.c.

References ctrump_loop_info_node::cfg_info, ctrump_loop_cfg_info::exit_cond, ctrump_loop_info_node::exit_info, ctrump_loop_info_node::inductive_var, ctrump_loop_info_node::invariant_var, analyze_loop_node_info::iv_info, and recog_exit_cond().

Referenced by ctrump_analyze_loop().

static void merge_reduc_op	(	ctrump_bitmap_t	is_reduc,
		ctrump_bitmap_t	is_initial,
		struct recog_reduction_info *	reduc_list,
		int	var_idx,
		enum ctrump_reductive_expr_code	merge_op,
		struct ctrump_stmt *	at
	)			[static]

縮約演算をひとつにする いまのところは違う種類の演算が出てくると縮約演算とはみなされない

Definition at line 2117 of file loop.c.

References recog_reduction_info::at, ctrump_stmt::code, recog_reduction_info::code, ctrump_bitmap_clear(), and ctrump_bitmap_p().

Referenced by recog_reduction_domtree().

static void parallel_load	(	struct ctrump_varray *	access_info,
		struct ctrump_var *	invariant_var,
		int	num_subscript,
		struct ctrump_loop_subscript *	subscripts,
		int	num_constraint,
		struct ctrump_loop_subscript_constraint *	constraints,
		int	flags,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	tmp_alloc
	)			[static]

メモリロード演算の追加

Definition at line 415 of file loop.c.

References append_access_info(), and LOAD.

Referenced by classify_memop().

static void parallel_store	(	struct ctrump_varray *	access_info,
		struct ctrump_var *	invariant_var,
		int	num_subscript,
		struct ctrump_loop_subscript *	subscripts,
		int	num_constraint,
		struct ctrump_loop_subscript_constraint *	constraints,
		int	flags,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	tmp_alloc
	)			[static]

メモリストア演算の追加

Definition at line 387 of file loop.c.

References append_access_info(), LOAD, PARALLEL_ACCESS_OP_ASSIGN, PARALLEL_ACCESS_PARTIAL, and STORE.

Referenced by classify_memop().

static void recog_array_index	(	parallel_array_func_t	parallel_func,
		struct ctrump_varray *	parallel_access,
		struct ctrump_varray *	random_access,
		struct ctrump_memory_access *	memory_access,
		ctrump_bitmap_t	invariant,
		ctrump_bitmap_t	invariant_on_loop_top,
		ctrump_bitmap_t *	inductive,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_intmap *	var_info_map,
		int	flags,
		struct iv_info **	iv_level,
		struct ctrump_loop_exit **	exit_level,
		int	loop_level,
		const struct ctrump_abi *	abi,
		struct ctrump_mempool *	tmp_alloc,
		struct ctrump_mempool *	loop_alloc,
		int *	id
	)			[static]

配列アクセスのインデクスを見つける

Definition at line 1023 of file loop.c.

References append_array_not_invariant, append_complicated_array, ctrump_memory_access::array, check_var_bmp_p(), ctrump_expr::code, ctrump_bitmap_p(), CTRUMP_EXPR_VARREF, ctrump_intmap_lookup(), ctrump_peel_cast_to_pointer_from_array(), expr_subscripts_to_loop_subscript(), ctrump_var::id, iv_info::incr, ctrump_cfg_var_info::index, ctrump_memory_access::num_subscript, ctrump_memory_access::subscripts, ctrump_expr::u, ctrump_varref_expr::var, and ctrump_expr::varref.

Referenced by classify_memop().

static void recog_exit_cond	(	struct ctrump_loop_exit *	loop_exit,
		struct ctrump_expr *	cond_expr,
		ctrump_bitmap_t	inductive,
		ctrump_bitmap_t	invariant,
		struct ctrump_intmap *	var_info_map,
		struct iv_info *	iv_info
	)			[static]

ループ脱出条件を解析する

Definition at line 1671 of file loop.c.

References ctrump_expr::binary, ctrump_loop_exit::code, ctrump_expr::code, CTRUMP_EXPR_BIN_EQ, CTRUMP_EXPR_BIN_GE, CTRUMP_EXPR_BIN_GT, CTRUMP_EXPR_BIN_LE, CTRUMP_EXPR_BIN_LT, CTRUMP_LOOP_COUNT_UNPREDICTABLE, ctrump_binary_expr::lhs, recog_exit_cond_cmp(), ctrump_binary_expr::rhs, and ctrump_expr::u.

Referenced by loop_exit_analyze().

static void recog_exit_cond_cmp	(	struct ctrump_loop_exit *	loop_exit,
		struct ctrump_expr *	lhs,
		struct ctrump_expr *	rhs,
		ctrump_bitmap_t	inductive,
		ctrump_bitmap_t	invariant,
		struct ctrump_intmap *	var_info_map,
		struct iv_info *	iv,
		enum ctrump_expr_code	cmp_op
	)			[static]

ループ脱出条件を解析する

Definition at line 1625 of file loop.c.

References BMP_P, ctrump_loop_count_pred_info::bound, ctrump_loop_count_pred_info::cmp_op, ctrump_loop_exit::code, ctrump_expr::code, CTRUMP_EXPR_VARREF, CTRUMP_LOOP_COUNT_PREDICTABLE, CTRUMP_LOOP_COUNT_UNPREDICTABLE, get_var_id(), iv_info::incr, ctrump_loop_count_pred_info::incr, ctrump_loop_count_pred_info::inductive, is_invariant_expr(), ctrump_loop_count_pred_info::iv_loop_entry_value, ctrump_loop_exit::pred, iv_info::reach_at_loop_entry, ctrump_loop_exit::u, ctrump_expr::u, ctrump_varref_expr::var, and ctrump_expr::varref.

Referenced by recog_exit_cond().

static int recog_inductive	(	struct iv_info *	recog,
		struct ctrump_pdg_node *	pdg
	)			[static]

帰納変数かどうかのチェック

Parameters:

	recog	現在のその変数の解析情報
	pdg	到達している定義

Returns:

帰納変数なら1、それ以外は0

Definition at line 116 of file loop.c.

References ctrump_pdg_node::code, ctrump_ast_fold_const_sint(), CTRUMP_PDG_INC, CTRUMP_PDG_VALUE_INCREMENTAL, CTRUMP_PDG_VALUE_REDUCTION, CTRUMP_REDUCTIVE_ADD, ctrump_pdg_node::incr, iv_info::incr, ctrump_pdg_incremental_expr::op, ctrump_pdg_reductive_expr::op, ctrump_pdg_node::reduction, ctrump_pdg_node::u, and ctrump_pdg_reductive_expr::value.

Referenced by find_iv().

static void recog_reduction	(	struct ctrump_loop_info_node **	loops,
		int	num_loop_node,
		struct analyze_loop_node_info *	info_list,
		struct ctrump_intmap *	var_info_map,
		struct ctrump_cfg_var_info *	var_info_list,
		int	num_var,
		struct ctrump_mempool *	loop_alloc,
		struct ctrump_mempool *	tmp_alloc
	)			[static]

縮約演算を見つける

Definition at line 2203 of file loop.c.

References recog_reduction_info::at, ctrump_loop_reduction::at, ctrump_loop_cfg_info::break_bb, ctrump_loop_info_node::carry_dep, ctrump_loop_info_node::cfg_info, recog_reduction_info::code, ctrump_loop_cfg_info::cond_bb, ctrump_bitmap_and(), ctrump_bitmap_clear(), ctrump_bitmap_ffs(), ctrump_bitmap_nand(), ctrump_bitmap_popcnt(), ctrump_bitmap_set_all(), ctrump_bmp_alloc(), ctrump_mempool_alloc, ctrump_loop_info_node::modified_and_live_after_loop, ctrump_loop_info_node::num_reduc_op, ctrump_loop_reduction::op, recog_reduction_domtree(), ctrump_loop_info_node::reductions, ctrump_cfg_var_info::var, and ctrump_loop_reduction::var.

Referenced by ctrump_analyze_loop().

static void recog_reduction_domtree	(	struct ctrump_bb *	bb,
		struct ctrump_bb *	exit_bb,
		struct ctrump_intmap *	var_info_map,
		int	num_var,
		ctrump_bitmap_t	is_reduc,
		ctrump_bitmap_t	is_initial,
		struct recog_reduction_info *	reduc_list
	)			[static]

縮約演算を見つける

Definition at line 2149 of file loop.c.

References ctrump_pdg_node::at, ctrump_pdg_node::code, ctrump_bitmap_clear(), ctrump_intmap_lookup(), CTRUMP_PDG_VALUE_INCREMENTAL, CTRUMP_PDG_VALUE_REDUCTION, ctrump_bb::dom_children, ctrump_var::id, ctrump_pdg_node::incr, incr_op_to_reduc_op, ctrump_cfg_var_info::index, ctrump_bb::load_store, merge_reduc_op(), ctrump_var_store::new_val, ctrump_bb::num_dom_children, ctrump_load_store_set::num_store, ctrump_pdg_incremental_expr::op, ctrump_pdg_reductive_expr::op, ctrump_pdg_node::reduction, ctrump_load_store_set::stores, ctrump_pdg_node::u, ctrump_var_store::var, and OffloadSpe::var.

Referenced by recog_reduction().

static int single_expr_subscripts_to_loop_subscript	(	struct ctrump_varray *	random_access,
		struct ctrump_varray *	indices,
		int *	constant_offset,
		struct ctrump_expr *	subscript_expr,
		struct ctrump_expr **	next_level_index_ret,
		struct ctrump_var **	coef_var,
		struct iv_info **	iv_level,
		ctrump_bitmap_t	invariant,
		ctrump_bitmap_t *	inductive_bmp,
		struct ctrump_intmap *	var_info_map,
		int	loop_level,
		struct ctrump_stmt *	at_stmt,
		struct ctrump_expr *	at_expr,
		struct ctrump_mempool *	tmp_alloc
	)			[static]

式で表現されたひとつの添字式から、真の添字と思われる式を取り出す

C ではa[width * y + x] のような式が書かれることが多いが、 (*(a + width*y +x) のようなのも多い…未対応) その場合にどれが添字かを判定しないといけない。

C の規格として、x > width の場合でも正しく動くのが当然であるので、 これを添字と判断する根拠は何も無いのだが、 一般的なコードにだけ対応するとして、 induction variable * invariant + induction variable の形の式が添字にあった場合、[y][x] の添字であるとして解析する

本来なら、ここでxの範囲を解析するか、 width > x の制約を見つけるかしてすべきだが未実装

Definition at line 594 of file loop.c.

References analyze_subscript_coef(), append_complicated_subscript(), append_index_var_not_inductive(), append_multiple_scaled_index(), ctrump_expr::binary, ctrump_loop_index::code, ctrump_expr::code, ctrump_ast_fold_const_offset_sint(), ctrump_bitmap_p(), CTRUMP_EXPR_BIN_ADD, CTRUMP_EXPR_BIN_SUB, CTRUMP_EXPR_VARREF, ctrump_intmap_lookup(), CTRUMP_LOOP_INDEX_INDUCTIVE, CTRUMP_LOOP_INDEX_INVARIANT, CTRUMP_LOOP_INDEX_NEGATIVE, ctrump_peel_paren(), ctrump_varray_init(), add_stack_elem::e, ctrump_loop_index::flags, ctrump_var::id, ctrump_loop_iv::incr, iv_info::incr, ctrump_cfg_var_info::index, ctrump_loop_index::invariant, add_stack_elem::is_sign, ctrump_loop_index::iv, ctrump_loop_iv::iv_level, ctrump_binary_expr::lhs, ctrump_varray::nelem, iv_info::reach_at_loop_entry, ctrump_loop_iv::reach_at_loop_entry, ctrump_binary_expr::rhs, ctrump_loop_index::u, ctrump_expr::u, VA_LAST_PTR, VA_NEWELEM, VA_POP, VA_PUSH, ctrump_loop_iv::var, ctrump_cfg_var_info::var, ctrump_varref_expr::var, OffloadSpe::var, and ctrump_expr::varref.

Referenced by expr_subscripts_to_loop_subscript().

---

Variable Documentation

enum ctrump_reductive_expr_code incr_op_to_reduc_op[] [static]

Initial value:

 {
    [CTRUMP_PDG_INC] = CTRUMP_REDUCTIVE_ADD,
    [CTRUMP_PDG_DEC] = CTRUMP_REDUCTIVE_SUB,
    [CTRUMP_PDG_FINC] = CTRUMP_REDUCTIVE_FADD,
    [CTRUMP_PDG_FDEC] = CTRUMP_REDUCTIVE_FSUB,
}

Definition at line 2138 of file loop.c.

Referenced by recog_reduction_domtree().