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_infoalloc_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,
 )     (((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

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

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

Definition at line 64 of file loop.c.

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

int ctrump_loop_index_hash ( const struct ctrump_loop_index i0  ) 

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

int ctrump_loop_subscript_hash ( const struct ctrump_loop_subscript s  ) 

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]

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]

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

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]

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]

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]

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]

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]

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]

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


Generated on Tue Mar 31 20:19:24 2009 for ctrump by  doxygen 1.5.6