ctrump/analyzer/deptest.c File Reference

依存性解析 More...

#include "ctrump/ast/ast.h"
#include "ctrump/analyzer/deptest.h"
#include "ctrump/analyzer/loop.h"
#include "ctrump/common/intmap.h"
#include "ctrump/common/abort.h"
#include "ctrump/common/varray.h"
#include <assert.h>

Include dependency graph for deptest.c:

Go to the source code of this file.

Data Structures

struct  distance_vector
 距離ベクトル More...
struct  dependence_info_node
 配列ごとの依存情報 More...
struct  dependence_info
 依存情報 array->subscript->distance vector More...

Defines

#define LOAD   0
#define STORE   1
#define SWAP_INDEX()

Functions

static void append_have_multiple_level (struct ctrump_varray *errors, struct ctrump_loop_memory_access *ma0, struct ctrump_loop_memory_access *ma1, struct ctrump_mempool *tmp_alloc)
 複数レベルの添字でアクセスしてるエラー
static void append_have_multiple_index (struct ctrump_varray *errors, struct ctrump_loop_memory_access *ma, struct ctrump_mempool *tmp_alloc)
 MIVがある.
static void append_have_weak_subscript (struct ctrump_varray *errors, struct ctrump_loop_subscript *sub0, struct ctrump_loop_subscript *sub1, struct ctrump_loop_memory_access *ma0, struct ctrump_loop_memory_access *ma1, struct ctrump_mempool *tmp_alloc)
 weak subscriptがある
static void append_have_complicated_subscript (struct ctrump_varray *errors, struct ctrump_loop_subscript *sub0, struct ctrump_loop_subscript *sub1, struct ctrump_loop_memory_access *ma0, struct ctrump_loop_memory_access *ma1, int sub_index, struct ctrump_mempool *tmp_alloc)
 解析できない添字がある
static int iv_test (struct ctrump_loop_iv *iv0, struct ctrump_loop_iv *iv1)
 ふたつのIVが交差しないことをテスト
static int invariant_test (struct ctrump_var *var0, struct ctrump_var *var1)
 ふたつのinvariantが一致することをテスト
static void strong_siv (struct ctrump_depend_distance *dest, struct ctrump_loop_subscript *x, struct ctrump_loop_subscript *y)
 strong siv の依存があった
static int test_index (struct ctrump_varray *errors, struct ctrump_intmap *array_map, struct ctrump_loop_memory_access *ma, struct ctrump_mempool *tmp_alloc, int load_store)
 依存性テスト
static int get_distance_vector (struct ctrump_loop_info_node *node, struct ctrump_mempool *loop_alloc)
 ループの依存情報を解析し、 距離ベクトルを求める
void ctrump_get_loop_depinfo (struct ctrump_loop_info *loop, int *id, struct ctrump_mempool *loop_alloc)
 ループ依存情報の計算 計算結果は loop->depinfo に格納

Detailed Description

依存性解析

距離ベクトルを求める

まずループ内のメモリストアを辿って、 各配列、添字でストアしている処理求め、dependence_info_nodeを作る

続いてロードを辿って、依存を見つける

Definition in file deptest.c.

Define Documentation

#define LOAD   0

Definition at line 158 of file deptest.c.

Referenced by assign_pdg_node_bb(), classify_memop(), extract_load_store_expr_rval(), get_distance_vector(), parallel_load(), and parallel_store().

#define STORE   1

Definition at line 159 of file deptest.c.

Referenced by assign_pdg_node_bb(), classify_memop(), extract_load_store_assign(), get_distance_vector(), parallel_store(), and test_index().

 
#define SWAP_INDEX (  ) 

Value:

do {                                       \
                        int nt = nl;                            \
                        struct ctrump_loop_index *it = il;      \
                        il = ir;                                \
                        nl = nr;                                \
                        ir = it;                                \
                        nr = nt;                                \
                    } while (0)

Referenced by test_index().

Function Documentation

static void append_have_complicated_subscript ( struct ctrump_varray *  errors,
struct ctrump_loop_subscript *  sub0,
struct ctrump_loop_subscript *  sub1,
struct ctrump_loop_memory_access *  ma0,
struct ctrump_loop_memory_access *  ma1,
int  sub_index,
struct ctrump_mempool *  tmp_alloc 
) [static]

解析できない添字がある

Definition at line 138 of file deptest.c.

References ctrump_loop_dependence_have_complicated_subscript::access0, ctrump_loop_dependence_have_complicated_subscript::access1, ctrump_loop_dependence_analyze_error::code, CTRUMP_LOOP_DEPENDENCE_ANALYZE_HAVE_COMPLICATED_SUBSCRIPT, ctrump_loop_dependence_analyze_error::have_complicated_subscript, ctrump_loop_dependence_have_complicated_subscript::sub0, ctrump_loop_dependence_have_complicated_subscript::sub1, ctrump_loop_dependence_have_complicated_subscript::sub_index, ctrump_loop_dependence_analyze_error::u, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by test_index().

static void append_have_multiple_index ( struct ctrump_varray *  errors,
struct ctrump_loop_memory_access *  ma,
struct ctrump_mempool *  tmp_alloc 
) [static]

MIVがある.

Definition at line 100 of file deptest.c.

References ctrump_loop_dependence_have_multiple_index::access, ctrump_loop_dependence_analyze_error::code, CTRUMP_LOOP_DEPENDENCE_ANALYZE_HAVE_MULTIPLE_INDEX, ctrump_loop_dependence_analyze_error::have_miv, ctrump_loop_dependence_analyze_error::u, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by test_index().

static void append_have_multiple_level ( struct ctrump_varray *  errors,
struct ctrump_loop_memory_access *  ma0,
struct ctrump_loop_memory_access *  ma1,
struct ctrump_mempool *  tmp_alloc 
) [static]

複数レベルの添字でアクセスしてるエラー

Definition at line 82 of file deptest.c.

References ctrump_loop_dependence_have_multiple_level::access0, ctrump_loop_dependence_have_multiple_level::access1, ctrump_loop_dependence_analyze_error::code, CTRUMP_LOOP_DEPENDENCE_ANALYZE_HAVE_MULTIPLE_LEVEL, ctrump_loop_dependence_analyze_error::have_multi_level, ctrump_loop_dependence_analyze_error::u, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by test_index().

static void append_have_weak_subscript ( struct ctrump_varray *  errors,
struct ctrump_loop_subscript *  sub0,
struct ctrump_loop_subscript *  sub1,
struct ctrump_loop_memory_access *  ma0,
struct ctrump_loop_memory_access *  ma1,
struct ctrump_mempool *  tmp_alloc 
) [static]

weak subscriptがある

Definition at line 116 of file deptest.c.

References ctrump_loop_dependence_have_weak_subscript::access0, ctrump_loop_dependence_have_weak_subscript::access1, ctrump_loop_dependence_analyze_error::code, CTRUMP_LOOP_DEPENDENCE_ANALYZE_HAVE_WEAK_SUBSCRIPT, ctrump_loop_dependence_analyze_error::have_weak, ctrump_loop_dependence_have_weak_subscript::sub0, ctrump_loop_dependence_have_weak_subscript::sub1, ctrump_loop_dependence_analyze_error::u, VA_LAST_PTR, and VA_NEWELEM_P.

Referenced by test_index().

void ctrump_get_loop_depinfo ( struct ctrump_loop_info *  loop,
int *  id,
struct ctrump_mempool *  loop_alloc 
)

ループ依存情報の計算 計算結果は loop->depinfo に格納

Definition at line 573 of file deptest.c.

References get_distance_vector(), and ctrump_loop_info::root.

Referenced by ctrump_analyze_loop().

static int get_distance_vector ( struct ctrump_loop_info_node *  node,
struct ctrump_mempool *  loop_alloc 
) [static]

ループの依存情報を解析し、 距離ベクトルを求める

Definition at line 452 of file deptest.c.

References ctrump_dependence_vector_set::accesses, ctrump_loop_memory_access::array, ctrump_dependence_vector_set::array_var, ctrump_loop_info_node::children, ctrump_loop_depinfo::code, ctrump_intmap_init_pool(), ctrump_intmap_iterator_begin(), ctrump_intmap_iterator_next(), CTRUMP_LOOP_DEPINFO, CTRUMP_LOOP_DEPINFO_ANALYZE_ERROR, CTRUMP_LOOP_DEPINFO_HAVE_ERROR_INNER, ctrump_mempool_alloc, ctrump_mempool_destroy(), ctrump_mempool_init(), ctrump_varray_copy(), ctrump_varray_init_pool(), ctrump_loop_depinfo::dep_vector, ctrump_loop_info_node::depinfo, ctrump_dependence_vector_set::distance_vectors, dependence_info_node::distance_vectors, ctrump_varray::elements, ctrump_loop_depinfo::error, ctrump_loop_dependence_analyze_error_list::errors, dependence_info_node::first_occur, distance_vector::load, ctrump_loop_memory_access_pair::load, LOAD, ctrump_varray::nelem, dependence_info::nodes, ctrump_loop_info_node::num_child, ctrump_loop_dependence_analyze_error_list::num_error, ctrump_loop_info_node::num_parallel_load, ctrump_loop_info_node::num_parallel_store, ctrump_dependence_vector_set::num_subscript, ctrump_loop_memory_access::num_subscript, ctrump_loop_dependence::num_vec_set, ctrump_dependence_vector_set::num_vector, ctrump_loop_info_node::parallel_loads, ctrump_loop_info_node::parallel_stores, distance_vector::store, ctrump_loop_memory_access_pair::store, STORE, test_index(), ctrump_loop_depinfo::u, ctrump_intmap_bucket::val, ctrump_loop_array::var, distance_vector::vector, and ctrump_loop_dependence::vectors.

Referenced by ctrump_get_loop_depinfo().

static int invariant_test ( struct ctrump_var *  var0,
struct ctrump_var *  var1 
) [static]

ふたつのinvariantが一致することをテスト

Definition at line 178 of file deptest.c.

Referenced by test_index().

static int iv_test ( struct ctrump_loop_iv *  iv0,
struct ctrump_loop_iv *  iv1 
) [static]

ふたつのIVが交差しないことをテスト

Definition at line 165 of file deptest.c.

References ctrump_loop_iv::incr, and ctrump_loop_iv::iv_level.

Referenced by test_index().

static void strong_siv ( struct ctrump_depend_distance *  dest,
struct ctrump_loop_subscript *  x,
struct ctrump_loop_subscript *  y 
) [static]

strong siv の依存があった

Definition at line 190 of file deptest.c.

References ctrump_depend_distance::code, CTRUMP_DEPEND_DISTANCE_STRONG_SIV, ctrump_depend_distance_strong_siv::distance, ctrump_depend_distance_strong_siv::index0, ctrump_depend_distance_strong_siv::index1, ctrump_loop_subscript::indices, ctrump_loop_subscript::offset, ctrump_depend_distance::strong_siv, and ctrump_depend_distance::u.

Referenced by test_index().

static int test_index ( struct ctrump_varray *  errors,
struct ctrump_intmap *  array_map,
struct ctrump_loop_memory_access *  ma,
struct ctrump_mempool *  tmp_alloc,
int  load_store 
) [static]

依存性テスト

Definition at line 204 of file deptest.c.

References append_have_complicated_subscript(), append_have_multiple_index(), append_have_multiple_level(), append_have_weak_subscript(), ctrump_loop_memory_access::array, ctrump_depend_distance::code, ctrump_loop_subscript::code, CTRUMP_DEPEND_DISTANCE_CONSTANT_ZIV, CTRUMP_DEPEND_DISTANCE_INVARIANT_ZIV, CTRUMP_DEPEND_DISTANCE_MEMBER_NAME_ZIV, ctrump_intmap_lookup_add(), ctrump_intmap_lookup_bucket(), CTRUMP_LOOP_INDEX_INDUCTIVE, CTRUMP_LOOP_INDEX_INVARIANT, CTRUMP_LOOP_INDEX_POINTER_INC, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER, CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL, ctrump_mempool_alloc, ctrump_varray_init_pool(), dependence_info_node::distance_vectors, ctrump_varray::elements, dependence_info_node::first_occur, ctrump_var::id, ctrump_loop_subscript::indices, ctrump_depend_distance::invariant, ctrump_loop_index::invariant, invariant_test(), ctrump_loop_index::iv, iv_test(), distance_vector::load, ctrump_loop_subscript_record_member_terminal::member_name, ctrump_depend_distance_member_name_ziv::member_name, ctrump_depend_distance::member_name, ctrump_loop_subscript_record_member::member_name, ctrump_varray::nelem, dependence_info::nodes, ctrump_loop_subscript::num_index, ctrump_loop_memory_access::num_subscript, ctrump_loop_subscript::offset, ctrump_loop_subscript::ctrump_loop_subscript_scale::record_member, ctrump_loop_subscript::ctrump_loop_subscript_scale::record_member_terminal, distance_vector::store, STORE, strong_siv(), ctrump_loop_memory_access::subscripts, SWAP_INDEX, ctrump_loop_index::u, ctrump_depend_distance::u, ctrump_loop_subscript::u, VA_LAST_PTR, VA_NEWELEM_P, VA_PUSH_P, ctrump_intmap_bucket::val, ctrump_depend_distance_invariant_ziv::var, ctrump_loop_array::var, and distance_vector::vector.

Referenced by get_distance_vector().

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