X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fmatrix-reorg.c;fp=gcc%2Fmatrix-reorg.c;h=d916f70266cc419b1673703133b673bf70a35236;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/matrix-reorg.c b/gcc/matrix-reorg.c new file mode 100644 index 00000000..d916f702 --- /dev/null +++ b/gcc/matrix-reorg.c @@ -0,0 +1,2430 @@ +/* Matrix layout transformations. + Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc. + Contributed by Razya Ladelsky + Originally written by Revital Eres and Mustafa Hagog. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +/* + Matrix flattening optimization tries to replace a N-dimensional + matrix with its equivalent M-dimensional matrix, where M < N. + This first implementation focuses on global matrices defined dynamically. + + When N==1, we actually flatten the whole matrix. + For instance consider a two-dimensional array a [dim1] [dim2]. + The code for allocating space for it usually looks like: + + a = (int **) malloc(dim1 * sizeof(int *)); + for (i=0; i ; ** is amount to malloc; precomputed ** + T4 = malloc (T3); + T5 = (struct_type *) T4; + orig_var = T5; + + The following struct fields allow us to collect all the necessary data from + the gimplified program. The comments in the struct below are all based + on the gimple example above. */ + +struct malloc_call_data +{ + gimple call_stmt; /* Tree for "T4 = malloc (T3);" */ + tree size_var; /* Var decl for T3. */ + tree malloc_size; /* Tree for "", the rhs assigned to T3. */ +}; + +static tree can_calculate_expr_before_stmt (tree, sbitmap); +static tree can_calculate_stmt_before_stmt (gimple, sbitmap); + +/* The front end of the compiler, when parsing statements of the form: + + var = (type_cast) malloc (sizeof (type)); + + always converts this single statement into the following statements + (GIMPLE form): + + T.1 = sizeof (type); + T.2 = malloc (T.1); + T.3 = (type_cast) T.2; + var = T.3; + + Since we need to create new malloc statements and modify the original + statements somewhat, we need to find all four of the above statements. + Currently record_call_1 (called for building cgraph edges) finds and + records the statements containing the actual call to malloc, but we + need to find the rest of the variables/statements on our own. That + is what the following function does. */ +static void +collect_data_for_malloc_call (gimple stmt, struct malloc_call_data *m_data) +{ + tree size_var = NULL; + tree malloc_fn_decl; + tree arg1; + + gcc_assert (is_gimple_call (stmt)); + + malloc_fn_decl = gimple_call_fndecl (stmt); + if (malloc_fn_decl == NULL + || DECL_FUNCTION_CODE (malloc_fn_decl) != BUILT_IN_MALLOC) + return; + + arg1 = gimple_call_arg (stmt, 0); + size_var = arg1; + + m_data->call_stmt = stmt; + m_data->size_var = size_var; + if (TREE_CODE (size_var) != VAR_DECL) + m_data->malloc_size = size_var; + else + m_data->malloc_size = NULL_TREE; +} + +/* Information about matrix access site. + For example: if an access site of matrix arr is arr[i][j] + the ACCESS_SITE_INFO structure will have the address + of arr as its stmt. The INDEX_INFO will hold information about the + initial address and index of each dimension. */ +struct access_site_info +{ + /* The statement (INDIRECT_REF or POINTER_PLUS_EXPR). */ + gimple stmt; + + /* In case of POINTER_PLUS_EXPR, what is the offset. */ + tree offset; + + /* The index which created the offset. */ + tree index; + + /* The indirection level of this statement. */ + int level; + + /* TRUE for allocation site FALSE for access site. */ + bool is_alloc; + + /* The function containing the access site. */ + tree function_decl; + + /* This access is iterated in the inner most loop */ + bool iterated_by_inner_most_loop_p; +}; + +typedef struct access_site_info *access_site_info_p; +DEF_VEC_P (access_site_info_p); +DEF_VEC_ALLOC_P (access_site_info_p, heap); + +/* Information about matrix to flatten. */ +struct matrix_info +{ + /* Decl tree of this matrix. */ + tree decl; + /* Number of dimensions; number + of "*" in the type declaration. */ + int num_dims; + + /* Minimum indirection level that escapes, 0 means that + the whole matrix escapes, k means that dimensions + 0 to ACTUAL_DIM - k escapes. */ + int min_indirect_level_escape; + + gimple min_indirect_level_escape_stmt; + + /* Hold the allocation site for each level (dimension). + We can use NUM_DIMS as the upper bound and allocate the array + once with this number of elements and no need to use realloc and + MAX_MALLOCED_LEVEL. */ + gimple *malloc_for_level; + + int max_malloced_level; + + /* Is the matrix transposed. */ + bool is_transposed_p; + + /* The location of the allocation sites (they must be in one + function). */ + tree allocation_function_decl; + + /* The calls to free for each level of indirection. */ + struct free_info + { + gimple stmt; + tree func; + } *free_stmts; + + /* An array which holds for each dimension its size. where + dimension 0 is the outer most (one that contains all the others). + */ + tree *dimension_size; + + /* An array which holds for each dimension it's original size + (before transposing and flattening take place). */ + tree *dimension_size_orig; + + /* An array which holds for each dimension the size of the type of + of elements accessed in that level (in bytes). */ + HOST_WIDE_INT *dimension_type_size; + + int dimension_type_size_len; + + /* An array collecting the count of accesses for each dimension. */ + gcov_type *dim_hot_level; + + /* An array of the accesses to be flattened. + elements are of type "struct access_site_info *". */ + VEC (access_site_info_p, heap) * access_l; + + /* A map of how the dimensions will be organized at the end of + the analyses. */ + int *dim_map; +}; + +/* In each phi node we want to record the indirection level we have when we + get to the phi node. Usually we will have phi nodes with more than two + arguments, then we must assure that all of them get to the phi node with + the same indirection level, otherwise it's not safe to do the flattening. + So we record the information regarding the indirection level each time we + get to the phi node in this hash table. */ + +struct matrix_access_phi_node +{ + gimple phi; + int indirection_level; +}; + +/* We use this structure to find if the SSA variable is accessed inside the + tree and record the tree containing it. */ + +struct ssa_acc_in_tree +{ + /* The variable whose accesses in the tree we are looking for. */ + tree ssa_var; + /* The tree and code inside it the ssa_var is accessed, currently + it could be an INDIRECT_REF or CALL_EXPR. */ + enum tree_code t_code; + tree t_tree; + /* The place in the containing tree. */ + tree *tp; + tree second_op; + bool var_found; +}; + +static void analyze_matrix_accesses (struct matrix_info *, tree, int, bool, + sbitmap, bool); +static int transform_allocation_sites (void **, void *); +static int transform_access_sites (void **, void *); +static int analyze_transpose (void **, void *); +static int dump_matrix_reorg_analysis (void **, void *); + +static bool check_transpose_p; + +/* Hash function used for the phi nodes. */ + +static hashval_t +mat_acc_phi_hash (const void *p) +{ + const struct matrix_access_phi_node *const ma_phi = + (const struct matrix_access_phi_node *) p; + + return htab_hash_pointer (ma_phi->phi); +} + +/* Equality means phi node pointers are the same. */ + +static int +mat_acc_phi_eq (const void *p1, const void *p2) +{ + const struct matrix_access_phi_node *const phi1 = + (const struct matrix_access_phi_node *) p1; + const struct matrix_access_phi_node *const phi2 = + (const struct matrix_access_phi_node *) p2; + + if (phi1->phi == phi2->phi) + return 1; + + return 0; +} + +/* Hold the PHI nodes we visit during the traversal for escaping + analysis. */ +static htab_t htab_mat_acc_phi_nodes = NULL; + +/* This hash-table holds the information about the matrices we are + going to handle. */ +static htab_t matrices_to_reorg = NULL; + +/* Return a hash for MTT, which is really a "matrix_info *". */ +static hashval_t +mtt_info_hash (const void *mtt) +{ + return htab_hash_pointer (((const struct matrix_info *) mtt)->decl); +} + +/* Return true if MTT1 and MTT2 (which are really both of type + "matrix_info *") refer to the same decl. */ +static int +mtt_info_eq (const void *mtt1, const void *mtt2) +{ + const struct matrix_info *const i1 = (const struct matrix_info *) mtt1; + const struct matrix_info *const i2 = (const struct matrix_info *) mtt2; + + if (i1->decl == i2->decl) + return true; + + return false; +} + +/* Return false if STMT may contain a vector expression. + In this situation, all matrices should not be flattened. */ +static bool +may_flatten_matrices_1 (gimple stmt) +{ + tree t; + + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + if (!gimple_assign_cast_p (stmt)) + return true; + + t = gimple_assign_rhs1 (stmt); + while (CONVERT_EXPR_P (t)) + { + if (TREE_TYPE (t) && POINTER_TYPE_P (TREE_TYPE (t))) + { + tree pointee; + + pointee = TREE_TYPE (t); + while (POINTER_TYPE_P (pointee)) + pointee = TREE_TYPE (pointee); + if (TREE_CODE (pointee) == VECTOR_TYPE) + { + if (dump_file) + fprintf (dump_file, + "Found vector type, don't flatten matrix\n"); + return false; + } + } + t = TREE_OPERAND (t, 0); + } + break; + case GIMPLE_ASM: + /* Asm code could contain vector operations. */ + return false; + break; + default: + break; + } + return true; +} + +/* Return false if there are hand-written vectors in the program. + We disable the flattening in such a case. */ +static bool +may_flatten_matrices (struct cgraph_node *node) +{ + tree decl; + struct function *func; + basic_block bb; + gimple_stmt_iterator gsi; + + decl = node->decl; + if (node->analyzed) + { + func = DECL_STRUCT_FUNCTION (decl); + FOR_EACH_BB_FN (bb, func) + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + if (!may_flatten_matrices_1 (gsi_stmt (gsi))) + return false; + } + return true; +} + +/* Given a VAR_DECL, check its type to determine whether it is + a definition of a dynamic allocated matrix and therefore is + a suitable candidate for the matrix flattening optimization. + Return NULL if VAR_DECL is not such decl. Otherwise, allocate + a MATRIX_INFO structure, fill it with the relevant information + and return a pointer to it. + TODO: handle also statically defined arrays. */ +static struct matrix_info * +analyze_matrix_decl (tree var_decl) +{ + struct matrix_info *m_node, tmpmi, *mi; + tree var_type; + int dim_num = 0; + + gcc_assert (matrices_to_reorg); + + if (TREE_CODE (var_decl) == PARM_DECL) + var_type = DECL_ARG_TYPE (var_decl); + else if (TREE_CODE (var_decl) == VAR_DECL) + var_type = TREE_TYPE (var_decl); + else + return NULL; + + if (!POINTER_TYPE_P (var_type)) + return NULL; + + while (POINTER_TYPE_P (var_type)) + { + var_type = TREE_TYPE (var_type); + dim_num++; + } + + if (dim_num <= 1) + return NULL; + + if (!COMPLETE_TYPE_P (var_type) + || TREE_CODE (TYPE_SIZE_UNIT (var_type)) != INTEGER_CST) + return NULL; + + /* Check to see if this pointer is already in there. */ + tmpmi.decl = var_decl; + mi = (struct matrix_info *) htab_find (matrices_to_reorg, &tmpmi); + + if (mi) + return NULL; + + /* Record the matrix. */ + + m_node = (struct matrix_info *) xcalloc (1, sizeof (struct matrix_info)); + m_node->decl = var_decl; + m_node->num_dims = dim_num; + m_node->free_stmts + = (struct free_info *) xcalloc (dim_num, sizeof (struct free_info)); + + /* Init min_indirect_level_escape to -1 to indicate that no escape + analysis has been done yet. */ + m_node->min_indirect_level_escape = -1; + m_node->is_transposed_p = false; + + return m_node; +} + +/* Free matrix E. */ +static void +mat_free (void *e) +{ + struct matrix_info *mat = (struct matrix_info *) e; + + if (!mat) + return; + + if (mat->free_stmts) + free (mat->free_stmts); + if (mat->dim_hot_level) + free (mat->dim_hot_level); + if (mat->malloc_for_level) + free (mat->malloc_for_level); +} + +/* Find all potential matrices. + TODO: currently we handle only multidimensional + dynamically allocated arrays. */ +static void +find_matrices_decl (void) +{ + struct matrix_info *tmp; + PTR *slot; + struct varpool_node *vnode; + + gcc_assert (matrices_to_reorg); + + /* For every global variable in the program: + Check to see if it's of a candidate type and record it. */ + for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed) + { + tree var_decl = vnode->decl; + + if (!var_decl || TREE_CODE (var_decl) != VAR_DECL) + continue; + + if (matrices_to_reorg) + if ((tmp = analyze_matrix_decl (var_decl))) + { + if (!TREE_ADDRESSABLE (var_decl)) + { + slot = htab_find_slot (matrices_to_reorg, tmp, INSERT); + *slot = tmp; + } + } + } + return; +} + +/* Mark that the matrix MI escapes at level L. */ +static void +mark_min_matrix_escape_level (struct matrix_info *mi, int l, gimple s) +{ + if (mi->min_indirect_level_escape == -1 + || (mi->min_indirect_level_escape > l)) + { + mi->min_indirect_level_escape = l; + mi->min_indirect_level_escape_stmt = s; + } +} + +/* Find if the SSA variable is accessed inside the + tree and record the tree containing it. + The only relevant uses are the case of SSA_NAME, or SSA inside + INDIRECT_REF, PLUS_EXPR, POINTER_PLUS_EXPR, MULT_EXPR. */ +static void +ssa_accessed_in_tree (tree t, struct ssa_acc_in_tree *a) +{ + a->t_code = TREE_CODE (t); + switch (a->t_code) + { + case SSA_NAME: + if (t == a->ssa_var) + a->var_found = true; + break; + case INDIRECT_REF: + if (SSA_VAR_P (TREE_OPERAND (t, 0)) + && TREE_OPERAND (t, 0) == a->ssa_var) + a->var_found = true; + break; + default: + break; + } +} + +/* Find if the SSA variable is accessed on the right hand side of + gimple call STMT. */ + +static void +ssa_accessed_in_call_rhs (gimple stmt, struct ssa_acc_in_tree *a) +{ + tree decl; + tree arg; + size_t i; + + a->t_code = CALL_EXPR; + for (i = 0; i < gimple_call_num_args (stmt); i++) + { + arg = gimple_call_arg (stmt, i); + if (arg == a->ssa_var) + { + a->var_found = true; + decl = gimple_call_fndecl (stmt); + a->t_tree = decl; + break; + } + } +} + +/* Find if the SSA variable is accessed on the right hand side of + gimple assign STMT. */ + +static void +ssa_accessed_in_assign_rhs (gimple stmt, struct ssa_acc_in_tree *a) +{ + + a->t_code = gimple_assign_rhs_code (stmt); + switch (a->t_code) + { + tree op1, op2; + + case SSA_NAME: + case INDIRECT_REF: + CASE_CONVERT: + case VIEW_CONVERT_EXPR: + ssa_accessed_in_tree (gimple_assign_rhs1 (stmt), a); + break; + case POINTER_PLUS_EXPR: + case PLUS_EXPR: + case MULT_EXPR: + op1 = gimple_assign_rhs1 (stmt); + op2 = gimple_assign_rhs2 (stmt); + + if (op1 == a->ssa_var) + { + a->var_found = true; + a->second_op = op2; + } + else if (op2 == a->ssa_var) + { + a->var_found = true; + a->second_op = op1; + } + break; + default: + break; + } +} + +/* Record the access/allocation site information for matrix MI so we can + handle it later in transformation. */ +static void +record_access_alloc_site_info (struct matrix_info *mi, gimple stmt, tree offset, + tree index, int level, bool is_alloc) +{ + struct access_site_info *acc_info; + + if (!mi->access_l) + mi->access_l = VEC_alloc (access_site_info_p, heap, 100); + + acc_info + = (struct access_site_info *) + xcalloc (1, sizeof (struct access_site_info)); + acc_info->stmt = stmt; + acc_info->offset = offset; + acc_info->index = index; + acc_info->function_decl = current_function_decl; + acc_info->level = level; + acc_info->is_alloc = is_alloc; + + VEC_safe_push (access_site_info_p, heap, mi->access_l, acc_info); + +} + +/* Record the malloc as the allocation site of the given LEVEL. But + first we Make sure that all the size parameters passed to malloc in + all the allocation sites could be pre-calculated before the call to + the malloc of level 0 (the main malloc call). */ +static void +add_allocation_site (struct matrix_info *mi, gimple stmt, int level) +{ + struct malloc_call_data mcd; + + /* Make sure that the allocation sites are in the same function. */ + if (!mi->allocation_function_decl) + mi->allocation_function_decl = current_function_decl; + else if (mi->allocation_function_decl != current_function_decl) + { + int min_malloc_level; + + gcc_assert (mi->malloc_for_level); + + /* Find the minimum malloc level that already has been seen; + we known its allocation function must be + MI->allocation_function_decl since it's different than + CURRENT_FUNCTION_DECL then the escaping level should be + MIN (LEVEL, MIN_MALLOC_LEVEL) - 1 , and the allocation function + must be set accordingly. */ + for (min_malloc_level = 0; + min_malloc_level < mi->max_malloced_level + && mi->malloc_for_level[min_malloc_level]; min_malloc_level++); + if (level < min_malloc_level) + { + mi->allocation_function_decl = current_function_decl; + mark_min_matrix_escape_level (mi, min_malloc_level, stmt); + } + else + { + mark_min_matrix_escape_level (mi, level, stmt); + /* cannot be that (level == min_malloc_level) + we would have returned earlier. */ + return; + } + } + + /* Find the correct malloc information. */ + collect_data_for_malloc_call (stmt, &mcd); + + /* We accept only calls to malloc function; we do not accept + calls like calloc and realloc. */ + if (!mi->malloc_for_level) + { + mi->malloc_for_level = XCNEWVEC (gimple, level + 1); + mi->max_malloced_level = level + 1; + } + else if (mi->max_malloced_level <= level) + { + mi->malloc_for_level + = XRESIZEVEC (gimple, mi->malloc_for_level, level + 1); + + /* Zero the newly allocated items. */ + memset (&(mi->malloc_for_level[mi->max_malloced_level + 1]), + 0, (level - mi->max_malloced_level) * sizeof (tree)); + + mi->max_malloced_level = level + 1; + } + mi->malloc_for_level[level] = stmt; +} + +/* Given an assignment statement STMT that we know that its + left-hand-side is the matrix MI variable, we traverse the immediate + uses backwards until we get to a malloc site. We make sure that + there is one and only one malloc site that sets this variable. When + we are performing the flattening we generate a new variable that + will hold the size for each dimension; each malloc that allocates a + dimension has the size parameter; we use that parameter to + initialize the dimension size variable so we can use it later in + the address calculations. LEVEL is the dimension we're inspecting. + Return if STMT is related to an allocation site. */ + +static void +analyze_matrix_allocation_site (struct matrix_info *mi, gimple stmt, + int level, sbitmap visited) +{ + if (gimple_assign_copy_p (stmt) || gimple_assign_cast_p (stmt)) + { + tree rhs = gimple_assign_rhs1 (stmt); + + if (TREE_CODE (rhs) == SSA_NAME) + { + gimple def = SSA_NAME_DEF_STMT (rhs); + + analyze_matrix_allocation_site (mi, def, level, visited); + return; + } + /* If we are back to the original matrix variable then we + are sure that this is analyzed as an access site. */ + else if (rhs == mi->decl) + return; + } + /* A result of call to malloc. */ + else if (is_gimple_call (stmt)) + { + int call_flags = gimple_call_flags (stmt); + + if (!(call_flags & ECF_MALLOC)) + { + mark_min_matrix_escape_level (mi, level, stmt); + return; + } + else + { + tree malloc_fn_decl; + const char *malloc_fname; + + malloc_fn_decl = gimple_call_fndecl (stmt); + if (malloc_fn_decl == NULL_TREE) + { + mark_min_matrix_escape_level (mi, level, stmt); + return; + } + malloc_fname = IDENTIFIER_POINTER (DECL_NAME (malloc_fn_decl)); + if (DECL_FUNCTION_CODE (malloc_fn_decl) != BUILT_IN_MALLOC) + { + if (dump_file) + fprintf (dump_file, + "Matrix %s is an argument to function %s\n", + get_name (mi->decl), get_name (malloc_fn_decl)); + mark_min_matrix_escape_level (mi, level, stmt); + return; + } + } + /* This is a call to malloc of level 'level'. + mi->max_malloced_level-1 == level means that we've + seen a malloc statement of level 'level' before. + If the statement is not the same one that we've + seen before, then there's another malloc statement + for the same level, which means that we need to mark + it escaping. */ + if (mi->malloc_for_level + && mi->max_malloced_level-1 == level + && mi->malloc_for_level[level] != stmt) + { + mark_min_matrix_escape_level (mi, level, stmt); + return; + } + else + add_allocation_site (mi, stmt, level); + return; + } + /* Looks like we don't know what is happening in this + statement so be in the safe side and mark it as escaping. */ + mark_min_matrix_escape_level (mi, level, stmt); +} + +/* The transposing decision making. + In order to to calculate the profitability of transposing, we collect two + types of information regarding the accesses: + 1. profiling information used to express the hotness of an access, that + is how often the matrix is accessed by this access site (count of the + access site). + 2. which dimension in the access site is iterated by the inner + most loop containing this access. + + The matrix will have a calculated value of weighted hotness for each + dimension. + Intuitively the hotness level of a dimension is a function of how + many times it was the most frequently accessed dimension in the + highly executed access sites of this matrix. + + As computed by following equation: + m n + __ __ + \ \ dim_hot_level[i] += + /_ /_ + j i + acc[j]->dim[i]->iter_by_inner_loop * count(j) + + Where n is the number of dims and m is the number of the matrix + access sites. acc[j]->dim[i]->iter_by_inner_loop is 1 if acc[j] + iterates over dim[i] in innermost loop, and is 0 otherwise. + + The organization of the new matrix should be according to the + hotness of each dimension. The hotness of the dimension implies + the locality of the elements.*/ +static int +analyze_transpose (void **slot, void *data ATTRIBUTE_UNUSED) +{ + struct matrix_info *mi = (struct matrix_info *) *slot; + int min_escape_l = mi->min_indirect_level_escape; + struct loop *loop; + affine_iv iv; + struct access_site_info *acc_info; + int i; + + if (min_escape_l < 2 || !mi->access_l) + { + if (mi->access_l) + { + for (i = 0; + VEC_iterate (access_site_info_p, mi->access_l, i, acc_info); + i++) + free (acc_info); + VEC_free (access_site_info_p, heap, mi->access_l); + + } + return 1; + } + if (!mi->dim_hot_level) + mi->dim_hot_level = + (gcov_type *) xcalloc (min_escape_l, sizeof (gcov_type)); + + + for (i = 0; VEC_iterate (access_site_info_p, mi->access_l, i, acc_info); + i++) + { + if (gimple_assign_rhs_code (acc_info->stmt) == POINTER_PLUS_EXPR + && acc_info->level < min_escape_l) + { + loop = loop_containing_stmt (acc_info->stmt); + if (!loop || loop->inner) + { + free (acc_info); + continue; + } + if (simple_iv (loop, loop, acc_info->offset, &iv, true)) + { + if (iv.step != NULL) + { + HOST_WIDE_INT istep; + + istep = int_cst_value (iv.step); + if (istep != 0) + { + acc_info->iterated_by_inner_most_loop_p = 1; + mi->dim_hot_level[acc_info->level] += + gimple_bb (acc_info->stmt)->count; + } + + } + } + } + free (acc_info); + } + VEC_free (access_site_info_p, heap, mi->access_l); + + return 1; +} + +/* Find the index which defines the OFFSET from base. + We walk from use to def until we find how the offset was defined. */ +static tree +get_index_from_offset (tree offset, gimple def_stmt) +{ + tree op1, op2, index; + + if (gimple_code (def_stmt) == GIMPLE_PHI) + return NULL; + if ((gimple_assign_copy_p (def_stmt) || gimple_assign_cast_p (def_stmt)) + && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME) + return get_index_from_offset (offset, + SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt))); + else if (is_gimple_assign (def_stmt) + && gimple_assign_rhs_code (def_stmt) == MULT_EXPR) + { + op1 = gimple_assign_rhs1 (def_stmt); + op2 = gimple_assign_rhs2 (def_stmt); + if (TREE_CODE (op1) != INTEGER_CST && TREE_CODE (op2) != INTEGER_CST) + return NULL; + index = (TREE_CODE (op1) == INTEGER_CST) ? op2 : op1; + return index; + } + else + return NULL_TREE; +} + +/* update MI->dimension_type_size[CURRENT_INDIRECT_LEVEL] with the size + of the type related to the SSA_VAR, or the type related to the + lhs of STMT, in the case that it is an INDIRECT_REF. */ +static void +update_type_size (struct matrix_info *mi, gimple stmt, tree ssa_var, + int current_indirect_level) +{ + tree lhs; + HOST_WIDE_INT type_size; + + /* Update type according to the type of the INDIRECT_REF expr. */ + if (is_gimple_assign (stmt) + && TREE_CODE (gimple_assign_lhs (stmt)) == INDIRECT_REF) + { + lhs = gimple_assign_lhs (stmt); + gcc_assert (POINTER_TYPE_P + (TREE_TYPE (SSA_NAME_VAR (TREE_OPERAND (lhs, 0))))); + type_size = + int_size_in_bytes (TREE_TYPE + (TREE_TYPE + (SSA_NAME_VAR (TREE_OPERAND (lhs, 0))))); + } + else + type_size = int_size_in_bytes (TREE_TYPE (ssa_var)); + + /* Record the size of elements accessed (as a whole) + in the current indirection level (dimension). If the size of + elements is not known at compile time, mark it as escaping. */ + if (type_size <= 0) + mark_min_matrix_escape_level (mi, current_indirect_level, stmt); + else + { + int l = current_indirect_level; + + if (!mi->dimension_type_size) + { + mi->dimension_type_size + = (HOST_WIDE_INT *) xcalloc (l + 1, sizeof (HOST_WIDE_INT)); + mi->dimension_type_size_len = l + 1; + } + else if (mi->dimension_type_size_len < l + 1) + { + mi->dimension_type_size + = (HOST_WIDE_INT *) xrealloc (mi->dimension_type_size, + (l + 1) * sizeof (HOST_WIDE_INT)); + memset (&mi->dimension_type_size[mi->dimension_type_size_len], + 0, (l + 1 - mi->dimension_type_size_len) + * sizeof (HOST_WIDE_INT)); + mi->dimension_type_size_len = l + 1; + } + /* Make sure all the accesses in the same level have the same size + of the type. */ + if (!mi->dimension_type_size[l]) + mi->dimension_type_size[l] = type_size; + else if (mi->dimension_type_size[l] != type_size) + mark_min_matrix_escape_level (mi, l, stmt); + } +} + +/* USE_STMT represents a GIMPLE_CALL, where one of the arguments is the + ssa var that we want to check because it came from some use of matrix + MI. CURRENT_INDIRECT_LEVEL is the indirection level we reached so + far. */ + +static int +analyze_accesses_for_call_stmt (struct matrix_info *mi, tree ssa_var, + gimple use_stmt, int current_indirect_level) +{ + tree fndecl = gimple_call_fndecl (use_stmt); + + if (gimple_call_lhs (use_stmt)) + { + tree lhs = gimple_call_lhs (use_stmt); + struct ssa_acc_in_tree lhs_acc, rhs_acc; + + memset (&lhs_acc, 0, sizeof (lhs_acc)); + memset (&rhs_acc, 0, sizeof (rhs_acc)); + + lhs_acc.ssa_var = ssa_var; + lhs_acc.t_code = ERROR_MARK; + ssa_accessed_in_tree (lhs, &lhs_acc); + rhs_acc.ssa_var = ssa_var; + rhs_acc.t_code = ERROR_MARK; + ssa_accessed_in_call_rhs (use_stmt, &rhs_acc); + + /* The SSA must be either in the left side or in the right side, + to understand what is happening. + In case the SSA_NAME is found in both sides we should be escaping + at this level because in this case we cannot calculate the + address correctly. */ + if ((lhs_acc.var_found && rhs_acc.var_found + && lhs_acc.t_code == INDIRECT_REF) + || (!rhs_acc.var_found && !lhs_acc.var_found)) + { + mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt); + return current_indirect_level; + } + gcc_assert (!rhs_acc.var_found || !lhs_acc.var_found); + + /* If we are storing to the matrix at some level, then mark it as + escaping at that level. */ + if (lhs_acc.var_found) + { + int l = current_indirect_level + 1; + + gcc_assert (lhs_acc.t_code == INDIRECT_REF); + mark_min_matrix_escape_level (mi, l, use_stmt); + return current_indirect_level; + } + } + + if (fndecl) + { + if (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_FREE) + { + if (dump_file) + fprintf (dump_file, + "Matrix %s: Function call %s, level %d escapes.\n", + get_name (mi->decl), get_name (fndecl), + current_indirect_level); + mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt); + } + else if (mi->free_stmts[current_indirect_level].stmt != NULL + && mi->free_stmts[current_indirect_level].stmt != use_stmt) + mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt); + else + { + /*Record the free statements so we can delete them + later. */ + int l = current_indirect_level; + + mi->free_stmts[l].stmt = use_stmt; + mi->free_stmts[l].func = current_function_decl; + } + } + return current_indirect_level; +} + +/* USE_STMT represents a phi node of the ssa var that we want to + check because it came from some use of matrix + MI. + We check all the escaping levels that get to the PHI node + and make sure they are all the same escaping; + if not (which is rare) we let the escaping level be the + minimum level that gets into that PHI because starting from + that level we cannot expect the behavior of the indirections. + CURRENT_INDIRECT_LEVEL is the indirection level we reached so far. */ + +static void +analyze_accesses_for_phi_node (struct matrix_info *mi, gimple use_stmt, + int current_indirect_level, sbitmap visited, + bool record_accesses) +{ + + struct matrix_access_phi_node tmp_maphi, *maphi, **pmaphi; + + tmp_maphi.phi = use_stmt; + if ((maphi = (struct matrix_access_phi_node *) + htab_find (htab_mat_acc_phi_nodes, &tmp_maphi))) + { + if (maphi->indirection_level == current_indirect_level) + return; + else + { + int level = MIN (maphi->indirection_level, + current_indirect_level); + size_t j; + gimple stmt = NULL; + + maphi->indirection_level = level; + for (j = 0; j < gimple_phi_num_args (use_stmt); j++) + { + tree def = PHI_ARG_DEF (use_stmt, j); + + if (gimple_code (SSA_NAME_DEF_STMT (def)) != GIMPLE_PHI) + stmt = SSA_NAME_DEF_STMT (def); + } + mark_min_matrix_escape_level (mi, level, stmt); + } + return; + } + maphi = (struct matrix_access_phi_node *) + xcalloc (1, sizeof (struct matrix_access_phi_node)); + maphi->phi = use_stmt; + maphi->indirection_level = current_indirect_level; + + /* Insert to hash table. */ + pmaphi = (struct matrix_access_phi_node **) + htab_find_slot (htab_mat_acc_phi_nodes, maphi, INSERT); + gcc_assert (pmaphi); + *pmaphi = maphi; + + if (!TEST_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt)))) + { + SET_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt))); + analyze_matrix_accesses (mi, PHI_RESULT (use_stmt), + current_indirect_level, false, visited, + record_accesses); + RESET_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt))); + } +} + +/* USE_STMT represents an assign statement (the rhs or lhs include + the ssa var that we want to check because it came from some use of matrix + MI. CURRENT_INDIRECT_LEVEL is the indirection level we reached so far. */ + +static int +analyze_accesses_for_assign_stmt (struct matrix_info *mi, tree ssa_var, + gimple use_stmt, int current_indirect_level, + bool last_op, sbitmap visited, + bool record_accesses) +{ + tree lhs = gimple_get_lhs (use_stmt); + struct ssa_acc_in_tree lhs_acc, rhs_acc; + + memset (&lhs_acc, 0, sizeof (lhs_acc)); + memset (&rhs_acc, 0, sizeof (rhs_acc)); + + lhs_acc.ssa_var = ssa_var; + lhs_acc.t_code = ERROR_MARK; + ssa_accessed_in_tree (lhs, &lhs_acc); + rhs_acc.ssa_var = ssa_var; + rhs_acc.t_code = ERROR_MARK; + ssa_accessed_in_assign_rhs (use_stmt, &rhs_acc); + + /* The SSA must be either in the left side or in the right side, + to understand what is happening. + In case the SSA_NAME is found in both sides we should be escaping + at this level because in this case we cannot calculate the + address correctly. */ + if ((lhs_acc.var_found && rhs_acc.var_found + && lhs_acc.t_code == INDIRECT_REF) + || (!rhs_acc.var_found && !lhs_acc.var_found)) + { + mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt); + return current_indirect_level; + } + gcc_assert (!rhs_acc.var_found || !lhs_acc.var_found); + + /* If we are storing to the matrix at some level, then mark it as + escaping at that level. */ + if (lhs_acc.var_found) + { + int l = current_indirect_level + 1; + + gcc_assert (lhs_acc.t_code == INDIRECT_REF); + + if (!(gimple_assign_copy_p (use_stmt) + || gimple_assign_cast_p (use_stmt)) + || (TREE_CODE (gimple_assign_rhs1 (use_stmt)) != SSA_NAME)) + mark_min_matrix_escape_level (mi, l, use_stmt); + else + { + gimple def_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (use_stmt)); + analyze_matrix_allocation_site (mi, def_stmt, l, visited); + if (record_accesses) + record_access_alloc_site_info (mi, use_stmt, NULL_TREE, + NULL_TREE, l, true); + update_type_size (mi, use_stmt, NULL, l); + } + return current_indirect_level; + } + /* Now, check the right-hand-side, to see how the SSA variable + is used. */ + if (rhs_acc.var_found) + { + if (rhs_acc.t_code != INDIRECT_REF + && rhs_acc.t_code != POINTER_PLUS_EXPR && rhs_acc.t_code != SSA_NAME) + { + mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt); + return current_indirect_level; + } + /* If the access in the RHS has an indirection increase the + indirection level. */ + if (rhs_acc.t_code == INDIRECT_REF) + { + if (record_accesses) + record_access_alloc_site_info (mi, use_stmt, NULL_TREE, + NULL_TREE, + current_indirect_level, true); + current_indirect_level += 1; + } + else if (rhs_acc.t_code == POINTER_PLUS_EXPR) + { + gcc_assert (rhs_acc.second_op); + if (last_op) + /* Currently we support only one PLUS expression on the + SSA_NAME that holds the base address of the current + indirection level; to support more general case there + is a need to hold a stack of expressions and regenerate + the calculation later. */ + mark_min_matrix_escape_level (mi, current_indirect_level, + use_stmt); + else + { + tree index; + tree op1, op2; + + op1 = gimple_assign_rhs1 (use_stmt); + op2 = gimple_assign_rhs2 (use_stmt); + + op2 = (op1 == ssa_var) ? op2 : op1; + if (TREE_CODE (op2) == INTEGER_CST) + index = + build_int_cst (TREE_TYPE (op1), + TREE_INT_CST_LOW (op2) / + int_size_in_bytes (TREE_TYPE (op1))); + else + { + index = + get_index_from_offset (op2, SSA_NAME_DEF_STMT (op2)); + if (index == NULL_TREE) + { + mark_min_matrix_escape_level (mi, + current_indirect_level, + use_stmt); + return current_indirect_level; + } + } + if (record_accesses) + record_access_alloc_site_info (mi, use_stmt, op2, + index, + current_indirect_level, false); + } + } + /* If we are storing this level of indirection mark it as + escaping. */ + if (lhs_acc.t_code == INDIRECT_REF || TREE_CODE (lhs) != SSA_NAME) + { + int l = current_indirect_level; + + /* One exception is when we are storing to the matrix + variable itself; this is the case of malloc, we must make + sure that it's the one and only one call to malloc so + we call analyze_matrix_allocation_site to check + this out. */ + if (TREE_CODE (lhs) != VAR_DECL || lhs != mi->decl) + mark_min_matrix_escape_level (mi, current_indirect_level, + use_stmt); + else + { + /* Also update the escaping level. */ + analyze_matrix_allocation_site (mi, use_stmt, l, visited); + if (record_accesses) + record_access_alloc_site_info (mi, use_stmt, NULL_TREE, + NULL_TREE, l, true); + } + } + else + { + /* We are placing it in an SSA, follow that SSA. */ + analyze_matrix_accesses (mi, lhs, + current_indirect_level, + rhs_acc.t_code == POINTER_PLUS_EXPR, + visited, record_accesses); + } + } + return current_indirect_level; +} + +/* Given a SSA_VAR (coming from a use statement of the matrix MI), + follow its uses and level of indirection and find out the minimum + indirection level it escapes in (the highest dimension) and the maximum + level it is accessed in (this will be the actual dimension of the + matrix). The information is accumulated in MI. + We look at the immediate uses, if one escapes we finish; if not, + we make a recursive call for each one of the immediate uses of the + resulting SSA name. */ +static void +analyze_matrix_accesses (struct matrix_info *mi, tree ssa_var, + int current_indirect_level, bool last_op, + sbitmap visited, bool record_accesses) +{ + imm_use_iterator imm_iter; + use_operand_p use_p; + + update_type_size (mi, SSA_NAME_DEF_STMT (ssa_var), ssa_var, + current_indirect_level); + + /* We don't go beyond the escaping level when we are performing the + flattening. NOTE: we keep the last indirection level that doesn't + escape. */ + if (mi->min_indirect_level_escape > -1 + && mi->min_indirect_level_escape <= current_indirect_level) + return; + +/* Now go over the uses of the SSA_NAME and check how it is used in + each one of them. We are mainly looking for the pattern INDIRECT_REF, + then a POINTER_PLUS_EXPR, then INDIRECT_REF etc. while in between there could + be any number of copies and casts. */ + gcc_assert (TREE_CODE (ssa_var) == SSA_NAME); + + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ssa_var) + { + gimple use_stmt = USE_STMT (use_p); + if (gimple_code (use_stmt) == GIMPLE_PHI) + /* We check all the escaping levels that get to the PHI node + and make sure they are all the same escaping; + if not (which is rare) we let the escaping level be the + minimum level that gets into that PHI because starting from + that level we cannot expect the behavior of the indirections. */ + + analyze_accesses_for_phi_node (mi, use_stmt, current_indirect_level, + visited, record_accesses); + + else if (is_gimple_call (use_stmt)) + analyze_accesses_for_call_stmt (mi, ssa_var, use_stmt, + current_indirect_level); + else if (is_gimple_assign (use_stmt)) + current_indirect_level = + analyze_accesses_for_assign_stmt (mi, ssa_var, use_stmt, + current_indirect_level, last_op, + visited, record_accesses); + } +} + +typedef struct +{ + tree fn; + gimple stmt; +} check_var_data; + +/* A walk_tree function to go over the VAR_DECL, PARM_DECL nodes of + the malloc size expression and check that those aren't changed + over the function. */ +static tree +check_var_notmodified_p (tree * tp, int *walk_subtrees, void *data) +{ + basic_block bb; + tree t = *tp; + check_var_data *callback_data = (check_var_data*) data; + tree fn = callback_data->fn; + gimple_stmt_iterator gsi; + gimple stmt; + + if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != PARM_DECL) + return NULL_TREE; + + FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (fn)) + { + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + stmt = gsi_stmt (gsi); + if (!is_gimple_assign (stmt) && !is_gimple_call (stmt)) + continue; + if (gimple_get_lhs (stmt) == t) + { + callback_data->stmt = stmt; + return t; + } + } + } + *walk_subtrees = 1; + return NULL_TREE; +} + +/* Go backwards in the use-def chains and find out the expression + represented by the possible SSA name in STMT, until it is composed + of only VAR_DECL, PARM_DECL and INT_CST. In case of phi nodes + we make sure that all the arguments represent the same subexpression, + otherwise we fail. */ + +static tree +can_calculate_stmt_before_stmt (gimple stmt, sbitmap visited) +{ + tree op1, op2, res; + enum tree_code code; + + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + code = gimple_assign_rhs_code (stmt); + op1 = gimple_assign_rhs1 (stmt); + + switch (code) + { + case POINTER_PLUS_EXPR: + case PLUS_EXPR: + case MINUS_EXPR: + case MULT_EXPR: + + op2 = gimple_assign_rhs2 (stmt); + op1 = can_calculate_expr_before_stmt (op1, visited); + if (!op1) + return NULL_TREE; + op2 = can_calculate_expr_before_stmt (op2, visited); + if (op2) + return fold_build2 (code, gimple_expr_type (stmt), op1, op2); + return NULL_TREE; + + CASE_CONVERT: + res = can_calculate_expr_before_stmt (op1, visited); + if (res != NULL_TREE) + return build1 (code, gimple_expr_type (stmt), res); + else + return NULL_TREE; + + default: + if (gimple_assign_single_p (stmt)) + return can_calculate_expr_before_stmt (op1, visited); + else + return NULL_TREE; + } + + case GIMPLE_PHI: + { + size_t j; + + res = NULL_TREE; + /* Make sure all the arguments represent the same value. */ + for (j = 0; j < gimple_phi_num_args (stmt); j++) + { + tree new_res; + tree def = PHI_ARG_DEF (stmt, j); + + new_res = can_calculate_expr_before_stmt (def, visited); + if (res == NULL_TREE) + res = new_res; + else if (!new_res || !expressions_equal_p (res, new_res)) + return NULL_TREE; + } + return res; + } + + default: + return NULL_TREE; + } +} + +/* Go backwards in the use-def chains and find out the expression + represented by the possible SSA name in EXPR, until it is composed + of only VAR_DECL, PARM_DECL and INT_CST. In case of phi nodes + we make sure that all the arguments represent the same subexpression, + otherwise we fail. */ +static tree +can_calculate_expr_before_stmt (tree expr, sbitmap visited) +{ + gimple def_stmt; + tree res; + + switch (TREE_CODE (expr)) + { + case SSA_NAME: + /* Case of loop, we don't know to represent this expression. */ + if (TEST_BIT (visited, SSA_NAME_VERSION (expr))) + return NULL_TREE; + + SET_BIT (visited, SSA_NAME_VERSION (expr)); + def_stmt = SSA_NAME_DEF_STMT (expr); + res = can_calculate_stmt_before_stmt (def_stmt, visited); + RESET_BIT (visited, SSA_NAME_VERSION (expr)); + return res; + case VAR_DECL: + case PARM_DECL: + case INTEGER_CST: + return expr; + + default: + return NULL_TREE; + } +} + +/* There should be only one allocation function for the dimensions + that don't escape. Here we check the allocation sites in this + function. We must make sure that all the dimensions are allocated + using malloc and that the malloc size parameter expression could be + pre-calculated before the call to the malloc of dimension 0. + + Given a candidate matrix for flattening -- MI -- check if it's + appropriate for flattening -- we analyze the allocation + sites that we recorded in the previous analysis. The result of the + analysis is a level of indirection (matrix dimension) in which the + flattening is safe. We check the following conditions: + 1. There is only one allocation site for each dimension. + 2. The allocation sites of all the dimensions are in the same + function. + (The above two are being taken care of during the analysis when + we check the allocation site). + 3. All the dimensions that we flatten are allocated at once; thus + the total size must be known before the allocation of the + dimension 0 (top level) -- we must make sure we represent the + size of the allocation as an expression of global parameters or + constants and that those doesn't change over the function. */ + +static int +check_allocation_function (void **slot, void *data ATTRIBUTE_UNUSED) +{ + int level; + gimple_stmt_iterator gsi; + basic_block bb_level_0; + struct matrix_info *mi = (struct matrix_info *) *slot; + sbitmap visited; + + if (!mi->malloc_for_level) + return 1; + + visited = sbitmap_alloc (num_ssa_names); + + /* Do nothing if the current function is not the allocation + function of MI. */ + if (mi->allocation_function_decl != current_function_decl + /* We aren't in the main allocation function yet. */ + || !mi->malloc_for_level[0]) + return 1; + + for (level = 1; level < mi->max_malloced_level; level++) + if (!mi->malloc_for_level[level]) + break; + + mark_min_matrix_escape_level (mi, level, NULL); + + gsi = gsi_for_stmt (mi->malloc_for_level[0]); + bb_level_0 = gsi.bb; + + /* Check if the expression of the size passed to malloc could be + pre-calculated before the malloc of level 0. */ + for (level = 1; level < mi->min_indirect_level_escape; level++) + { + gimple call_stmt; + tree size; + struct malloc_call_data mcd = {NULL, NULL_TREE, NULL_TREE}; + + call_stmt = mi->malloc_for_level[level]; + + /* Find the correct malloc information. */ + collect_data_for_malloc_call (call_stmt, &mcd); + + /* No need to check anticipation for constants. */ + if (TREE_CODE (mcd.size_var) == INTEGER_CST) + { + if (!mi->dimension_size) + { + mi->dimension_size = + (tree *) xcalloc (mi->min_indirect_level_escape, + sizeof (tree)); + mi->dimension_size_orig = + (tree *) xcalloc (mi->min_indirect_level_escape, + sizeof (tree)); + } + mi->dimension_size[level] = mcd.size_var; + mi->dimension_size_orig[level] = mcd.size_var; + continue; + } + /* ??? Here we should also add the way to calculate the size + expression not only know that it is anticipated. */ + sbitmap_zero (visited); + size = can_calculate_expr_before_stmt (mcd.size_var, visited); + if (size == NULL_TREE) + { + mark_min_matrix_escape_level (mi, level, call_stmt); + if (dump_file) + fprintf (dump_file, + "Matrix %s: Cannot calculate the size of allocation, escaping at level %d\n", + get_name (mi->decl), level); + break; + } + if (!mi->dimension_size) + { + mi->dimension_size = + (tree *) xcalloc (mi->min_indirect_level_escape, sizeof (tree)); + mi->dimension_size_orig = + (tree *) xcalloc (mi->min_indirect_level_escape, sizeof (tree)); + } + mi->dimension_size[level] = size; + mi->dimension_size_orig[level] = size; + } + + /* We don't need those anymore. */ + for (level = mi->min_indirect_level_escape; + level < mi->max_malloced_level; level++) + mi->malloc_for_level[level] = NULL; + return 1; +} + +/* Track all access and allocation sites. */ +static void +find_sites_in_func (bool record) +{ + sbitmap visited_stmts_1; + + gimple_stmt_iterator gsi; + gimple stmt; + basic_block bb; + struct matrix_info tmpmi, *mi; + + visited_stmts_1 = sbitmap_alloc (num_ssa_names); + + FOR_EACH_BB (bb) + { + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + tree lhs; + + stmt = gsi_stmt (gsi); + lhs = gimple_get_lhs (stmt); + if (lhs != NULL_TREE + && TREE_CODE (lhs) == VAR_DECL) + { + tmpmi.decl = lhs; + if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg, + &tmpmi))) + { + sbitmap_zero (visited_stmts_1); + analyze_matrix_allocation_site (mi, stmt, 0, visited_stmts_1); + } + } + if (is_gimple_assign (stmt) + && gimple_assign_single_p (stmt) + && TREE_CODE (lhs) == SSA_NAME + && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL) + { + tmpmi.decl = gimple_assign_rhs1 (stmt); + if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg, + &tmpmi))) + { + sbitmap_zero (visited_stmts_1); + analyze_matrix_accesses (mi, lhs, 0, + false, visited_stmts_1, record); + } + } + } + } + sbitmap_free (visited_stmts_1); +} + +/* Traverse the use-def chains to see if there are matrices that + are passed through pointers and we cannot know how they are accessed. + For each SSA-name defined by a global variable of our interest, + we traverse the use-def chains of the SSA and follow the indirections, + and record in what level of indirection the use of the variable + escapes. A use of a pointer escapes when it is passed to a function, + stored into memory or assigned (except in malloc and free calls). */ + +static void +record_all_accesses_in_func (void) +{ + unsigned i; + sbitmap visited_stmts_1; + + visited_stmts_1 = sbitmap_alloc (num_ssa_names); + + for (i = 0; i < num_ssa_names; i++) + { + struct matrix_info tmpmi, *mi; + tree ssa_var = ssa_name (i); + tree rhs, lhs; + + if (!ssa_var + || !is_gimple_assign (SSA_NAME_DEF_STMT (ssa_var)) + || !gimple_assign_single_p (SSA_NAME_DEF_STMT (ssa_var))) + continue; + rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ssa_var)); + lhs = gimple_assign_lhs (SSA_NAME_DEF_STMT (ssa_var)); + if (TREE_CODE (rhs) != VAR_DECL && TREE_CODE (lhs) != VAR_DECL) + continue; + + /* If the RHS is a matrix that we want to analyze, follow the def-use + chain for this SSA_VAR and check for escapes or apply the + flattening. */ + tmpmi.decl = rhs; + if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg, &tmpmi))) + { + /* This variable will track the visited PHI nodes, so we can limit + its size to the maximum number of SSA names. */ + sbitmap_zero (visited_stmts_1); + analyze_matrix_accesses (mi, ssa_var, + 0, false, visited_stmts_1, true); + + } + } + sbitmap_free (visited_stmts_1); +} + +/* Used when we want to convert the expression: RESULT = something * + ORIG to RESULT = something * NEW_VAL. If ORIG and NEW_VAL are power + of 2, shift operations can be done, else division and + multiplication. */ + +static tree +compute_offset (HOST_WIDE_INT orig, HOST_WIDE_INT new_val, tree result) +{ + + int x, y; + tree result1, ratio, log, orig_tree, new_tree; + + x = exact_log2 (orig); + y = exact_log2 (new_val); + + if (x != -1 && y != -1) + { + if (x == y) + return result; + else if (x > y) + { + log = build_int_cst (TREE_TYPE (result), x - y); + result1 = + fold_build2 (LSHIFT_EXPR, TREE_TYPE (result), result, log); + return result1; + } + log = build_int_cst (TREE_TYPE (result), y - x); + result1 = fold_build2 (RSHIFT_EXPR, TREE_TYPE (result), result, log); + + return result1; + } + orig_tree = build_int_cst (TREE_TYPE (result), orig); + new_tree = build_int_cst (TREE_TYPE (result), new_val); + ratio = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (result), result, orig_tree); + result1 = fold_build2 (MULT_EXPR, TREE_TYPE (result), ratio, new_tree); + + return result1; +} + + +/* We know that we are allowed to perform matrix flattening (according to the + escape analysis), so we traverse the use-def chains of the SSA vars + defined by the global variables pointing to the matrices of our interest. + in each use of the SSA we calculate the offset from the base address + according to the following equation: + + a[I1][I2]...[Ik] , where D1..Dk is the length of each dimension and the + escaping level is m <= k, and a' is the new allocated matrix, + will be translated to : + + b[I(m+1)]...[Ik] + + where + b = a' + I1*D2...*Dm + I2*D3...Dm + ... + Im + */ + +static int +transform_access_sites (void **slot, void *data ATTRIBUTE_UNUSED) +{ + gimple_stmt_iterator gsi; + struct matrix_info *mi = (struct matrix_info *) *slot; + int min_escape_l = mi->min_indirect_level_escape; + struct access_site_info *acc_info; + enum tree_code code; + int i; + + if (min_escape_l < 2 || !mi->access_l) + return 1; + for (i = 0; VEC_iterate (access_site_info_p, mi->access_l, i, acc_info); + i++) + { + /* This is possible because we collect the access sites before + we determine the final minimum indirection level. */ + if (acc_info->level >= min_escape_l) + { + free (acc_info); + continue; + } + if (acc_info->is_alloc) + { + if (acc_info->level >= 0 && gimple_bb (acc_info->stmt)) + { + ssa_op_iter iter; + tree def; + gimple stmt = acc_info->stmt; + tree lhs; + + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) + mark_sym_for_renaming (SSA_NAME_VAR (def)); + gsi = gsi_for_stmt (stmt); + gcc_assert (is_gimple_assign (acc_info->stmt)); + lhs = gimple_assign_lhs (acc_info->stmt); + if (TREE_CODE (lhs) == SSA_NAME + && acc_info->level < min_escape_l - 1) + { + imm_use_iterator imm_iter; + use_operand_p use_p; + gimple use_stmt; + + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs) + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + { + tree rhs, tmp; + gimple new_stmt; + + gcc_assert (gimple_assign_rhs_code (acc_info->stmt) + == INDIRECT_REF); + /* Emit convert statement to convert to type of use. */ + tmp = create_tmp_var (TREE_TYPE (lhs), "new"); + add_referenced_var (tmp); + rhs = gimple_assign_rhs1 (acc_info->stmt); + new_stmt = gimple_build_assign (tmp, + TREE_OPERAND (rhs, 0)); + tmp = make_ssa_name (tmp, new_stmt); + gimple_assign_set_lhs (new_stmt, tmp); + gsi = gsi_for_stmt (acc_info->stmt); + gsi_insert_after (&gsi, new_stmt, GSI_SAME_STMT); + SET_USE (use_p, tmp); + } + } + if (acc_info->level < min_escape_l - 1) + gsi_remove (&gsi, true); + } + free (acc_info); + continue; + } + code = gimple_assign_rhs_code (acc_info->stmt); + if (code == INDIRECT_REF + && acc_info->level < min_escape_l - 1) + { + /* Replace the INDIRECT_REF with NOP (cast) usually we are casting + from "pointer to type" to "type". */ + tree t = + build1 (NOP_EXPR, TREE_TYPE (gimple_assign_rhs1 (acc_info->stmt)), + TREE_OPERAND (gimple_assign_rhs1 (acc_info->stmt), 0)); + gimple_assign_set_rhs_code (acc_info->stmt, NOP_EXPR); + gimple_assign_set_rhs1 (acc_info->stmt, t); + } + else if (code == POINTER_PLUS_EXPR + && acc_info->level < (min_escape_l)) + { + imm_use_iterator imm_iter; + use_operand_p use_p; + + tree offset; + int k = acc_info->level; + tree num_elements, total_elements; + tree tmp1; + tree d_size = mi->dimension_size[k]; + + /* We already make sure in the analysis that the first operand + is the base and the second is the offset. */ + offset = acc_info->offset; + if (mi->dim_map[k] == min_escape_l - 1) + { + if (!check_transpose_p || mi->is_transposed_p == false) + tmp1 = offset; + else + { + tree new_offset; + tree d_type_size, d_type_size_k; + + d_type_size = size_int (mi->dimension_type_size[min_escape_l]); + d_type_size_k = size_int (mi->dimension_type_size[k + 1]); + + new_offset = + compute_offset (mi->dimension_type_size[min_escape_l], + mi->dimension_type_size[k + 1], offset); + + total_elements = new_offset; + if (new_offset != offset) + { + gsi = gsi_for_stmt (acc_info->stmt); + tmp1 = force_gimple_operand_gsi (&gsi, total_elements, + true, NULL, + true, GSI_SAME_STMT); + } + else + tmp1 = offset; + } + } + else + { + d_size = mi->dimension_size[mi->dim_map[k] + 1]; + num_elements = + fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, acc_info->index), + fold_convert (sizetype, d_size)); + add_referenced_var (d_size); + gsi = gsi_for_stmt (acc_info->stmt); + tmp1 = force_gimple_operand_gsi (&gsi, num_elements, true, + NULL, true, GSI_SAME_STMT); + } + /* Replace the offset if needed. */ + if (tmp1 != offset) + { + if (TREE_CODE (offset) == SSA_NAME) + { + gimple use_stmt; + + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, offset) + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + if (use_stmt == acc_info->stmt) + SET_USE (use_p, tmp1); + } + else + { + gcc_assert (TREE_CODE (offset) == INTEGER_CST); + gimple_assign_set_rhs2 (acc_info->stmt, tmp1); + update_stmt (acc_info->stmt); + } + } + } + /* ??? meanwhile this happens because we record the same access + site more than once; we should be using a hash table to + avoid this and insert the STMT of the access site only + once. + else + gcc_unreachable (); */ + free (acc_info); + } + VEC_free (access_site_info_p, heap, mi->access_l); + + update_ssa (TODO_update_ssa); +#ifdef ENABLE_CHECKING + verify_ssa (true); +#endif + return 1; +} + +/* Sort A array of counts. Arrange DIM_MAP to reflect the new order. */ + +static void +sort_dim_hot_level (gcov_type * a, int *dim_map, int n) +{ + int i, j, tmp1; + gcov_type tmp; + + for (i = 0; i < n - 1; i++) + { + for (j = 0; j < n - 1 - i; j++) + { + if (a[j + 1] < a[j]) + { + tmp = a[j]; /* swap a[j] and a[j+1] */ + a[j] = a[j + 1]; + a[j + 1] = tmp; + tmp1 = dim_map[j]; + dim_map[j] = dim_map[j + 1]; + dim_map[j + 1] = tmp1; + } + } + } +} + +/* Replace multiple mallocs (one for each dimension) to one malloc + with the size of DIM1*DIM2*...*DIMN*size_of_element + Make sure that we hold the size in the malloc site inside a + new global variable; this way we ensure that the size doesn't + change and it is accessible from all the other functions that + uses the matrix. Also, the original calls to free are deleted, + and replaced by a new call to free the flattened matrix. */ + +static int +transform_allocation_sites (void **slot, void *data ATTRIBUTE_UNUSED) +{ + int i; + struct matrix_info *mi; + tree type, oldfn, prev_dim_size; + gimple call_stmt_0, use_stmt; + struct cgraph_node *c_node; + struct cgraph_edge *e; + gimple_stmt_iterator gsi; + struct malloc_call_data mcd = {NULL, NULL_TREE, NULL_TREE}; + HOST_WIDE_INT element_size; + + imm_use_iterator imm_iter; + use_operand_p use_p; + tree old_size_0, tmp; + int min_escape_l; + int id; + + mi = (struct matrix_info *) *slot; + + min_escape_l = mi->min_indirect_level_escape; + + if (!mi->malloc_for_level) + mi->min_indirect_level_escape = 0; + + if (mi->min_indirect_level_escape < 2) + return 1; + + mi->dim_map = (int *) xcalloc (mi->min_indirect_level_escape, sizeof (int)); + for (i = 0; i < mi->min_indirect_level_escape; i++) + mi->dim_map[i] = i; + if (check_transpose_p) + { + int i; + + if (dump_file) + { + fprintf (dump_file, "Matrix %s:\n", get_name (mi->decl)); + for (i = 0; i < min_escape_l; i++) + { + fprintf (dump_file, "dim %d before sort ", i); + if (mi->dim_hot_level) + fprintf (dump_file, + "count is " HOST_WIDEST_INT_PRINT_DEC " \n", + mi->dim_hot_level[i]); + } + } + sort_dim_hot_level (mi->dim_hot_level, mi->dim_map, + mi->min_indirect_level_escape); + if (dump_file) + for (i = 0; i < min_escape_l; i++) + { + fprintf (dump_file, "dim %d after sort\n", i); + if (mi->dim_hot_level) + fprintf (dump_file, "count is " HOST_WIDE_INT_PRINT_DEC + " \n", (HOST_WIDE_INT) mi->dim_hot_level[i]); + } + for (i = 0; i < mi->min_indirect_level_escape; i++) + { + if (dump_file) + fprintf (dump_file, "dim_map[%d] after sort %d\n", i, + mi->dim_map[i]); + if (mi->dim_map[i] != i) + { + if (dump_file) + fprintf (dump_file, + "Transposed dimensions: dim %d is now dim %d\n", + mi->dim_map[i], i); + mi->is_transposed_p = true; + } + } + } + else + { + for (i = 0; i < mi->min_indirect_level_escape; i++) + mi->dim_map[i] = i; + } + /* Call statement of allocation site of level 0. */ + call_stmt_0 = mi->malloc_for_level[0]; + + /* Finds the correct malloc information. */ + collect_data_for_malloc_call (call_stmt_0, &mcd); + + mi->dimension_size[0] = mcd.size_var; + mi->dimension_size_orig[0] = mcd.size_var; + /* Make sure that the variables in the size expression for + all the dimensions (above level 0) aren't modified in + the allocation function. */ + for (i = 1; i < mi->min_indirect_level_escape; i++) + { + tree t; + check_var_data data; + + /* mi->dimension_size must contain the expression of the size calculated + in check_allocation_function. */ + gcc_assert (mi->dimension_size[i]); + + data.fn = mi->allocation_function_decl; + data.stmt = NULL; + t = walk_tree_without_duplicates (&(mi->dimension_size[i]), + check_var_notmodified_p, + &data); + if (t != NULL_TREE) + { + mark_min_matrix_escape_level (mi, i, data.stmt); + break; + } + } + + if (mi->min_indirect_level_escape < 2) + return 1; + + /* Since we should make sure that the size expression is available + before the call to malloc of level 0. */ + gsi = gsi_for_stmt (call_stmt_0); + + /* Find out the size of each dimension by looking at the malloc + sites and create a global variable to hold it. + We add the assignment to the global before the malloc of level 0. */ + + /* To be able to produce gimple temporaries. */ + oldfn = current_function_decl; + current_function_decl = mi->allocation_function_decl; + push_cfun (DECL_STRUCT_FUNCTION (mi->allocation_function_decl)); + + /* Set the dimension sizes as follows: + DIM_SIZE[i] = DIM_SIZE[n] * ... * DIM_SIZE[i] + where n is the maximum non escaping level. */ + element_size = mi->dimension_type_size[mi->min_indirect_level_escape]; + prev_dim_size = NULL_TREE; + + for (i = mi->min_indirect_level_escape - 1; i >= 0; i--) + { + tree dim_size, dim_var; + gimple stmt; + tree d_type_size; + + /* Now put the size expression in a global variable and initialize it to + the size expression before the malloc of level 0. */ + dim_var = + add_new_static_var (TREE_TYPE + (mi->dimension_size_orig[mi->dim_map[i]])); + type = TREE_TYPE (mi->dimension_size_orig[mi->dim_map[i]]); + + /* DIM_SIZE = MALLOC_SIZE_PARAM / TYPE_SIZE. */ + /* Find which dim ID becomes dim I. */ + for (id = 0; id < mi->min_indirect_level_escape; id++) + if (mi->dim_map[id] == i) + break; + d_type_size = + build_int_cst (type, mi->dimension_type_size[id + 1]); + if (!prev_dim_size) + prev_dim_size = build_int_cst (type, element_size); + if (!check_transpose_p && i == mi->min_indirect_level_escape - 1) + { + dim_size = mi->dimension_size_orig[id]; + } + else + { + dim_size = + fold_build2 (TRUNC_DIV_EXPR, type, mi->dimension_size_orig[id], + d_type_size); + + dim_size = fold_build2 (MULT_EXPR, type, dim_size, prev_dim_size); + } + dim_size = force_gimple_operand_gsi (&gsi, dim_size, true, NULL, + true, GSI_SAME_STMT); + /* GLOBAL_HOLDING_THE_SIZE = DIM_SIZE. */ + stmt = gimple_build_assign (dim_var, dim_size); + mark_symbols_for_renaming (stmt); + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + + prev_dim_size = mi->dimension_size[i] = dim_var; + } + update_ssa (TODO_update_ssa); + /* Replace the malloc size argument in the malloc of level 0 to be + the size of all the dimensions. */ + c_node = cgraph_node (mi->allocation_function_decl); + old_size_0 = gimple_call_arg (call_stmt_0, 0); + tmp = force_gimple_operand_gsi (&gsi, mi->dimension_size[0], true, + NULL, true, GSI_SAME_STMT); + if (TREE_CODE (old_size_0) == SSA_NAME) + { + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_size_0) + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + if (use_stmt == call_stmt_0) + SET_USE (use_p, tmp); + } + /* When deleting the calls to malloc we need also to remove the edge from + the call graph to keep it consistent. Notice that cgraph_edge may + create a new node in the call graph if there is no node for the given + declaration; this shouldn't be the case but currently there is no way to + check this outside of "cgraph.c". */ + for (i = 1; i < mi->min_indirect_level_escape; i++) + { + gimple_stmt_iterator gsi; + gimple use_stmt1 = NULL; + + gimple call_stmt = mi->malloc_for_level[i]; + gcc_assert (is_gimple_call (call_stmt)); + e = cgraph_edge (c_node, call_stmt); + gcc_assert (e); + cgraph_remove_edge (e); + gsi = gsi_for_stmt (call_stmt); + /* Remove the call stmt. */ + gsi_remove (&gsi, true); + /* remove the type cast stmt. */ + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, + gimple_call_lhs (call_stmt)) + { + use_stmt1 = use_stmt; + gsi = gsi_for_stmt (use_stmt); + gsi_remove (&gsi, true); + } + /* Remove the assignment of the allocated area. */ + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, + gimple_get_lhs (use_stmt1)) + { + gsi = gsi_for_stmt (use_stmt); + gsi_remove (&gsi, true); + } + } + update_ssa (TODO_update_ssa); +#ifdef ENABLE_CHECKING + verify_ssa (true); +#endif + /* Delete the calls to free. */ + for (i = 1; i < mi->min_indirect_level_escape; i++) + { + gimple_stmt_iterator gsi; + + /* ??? wonder why this case is possible but we failed on it once. */ + if (!mi->free_stmts[i].stmt) + continue; + + c_node = cgraph_node (mi->free_stmts[i].func); + gcc_assert (is_gimple_call (mi->free_stmts[i].stmt)); + e = cgraph_edge (c_node, mi->free_stmts[i].stmt); + gcc_assert (e); + cgraph_remove_edge (e); + current_function_decl = mi->free_stmts[i].func; + set_cfun (DECL_STRUCT_FUNCTION (mi->free_stmts[i].func)); + gsi = gsi_for_stmt (mi->free_stmts[i].stmt); + gsi_remove (&gsi, true); + } + /* Return to the previous situation. */ + current_function_decl = oldfn; + pop_cfun (); + return 1; + +} + + +/* Print out the results of the escape analysis. */ +static int +dump_matrix_reorg_analysis (void **slot, void *data ATTRIBUTE_UNUSED) +{ + struct matrix_info *mi = (struct matrix_info *) *slot; + + if (!dump_file) + return 1; + fprintf (dump_file, "Matrix \"%s\"; Escaping Level: %d, Num Dims: %d,", + get_name (mi->decl), mi->min_indirect_level_escape, mi->num_dims); + fprintf (dump_file, " Malloc Dims: %d, ", mi->max_malloced_level); + fprintf (dump_file, "\n"); + if (mi->min_indirect_level_escape >= 2) + fprintf (dump_file, "Flattened %d dimensions \n", + mi->min_indirect_level_escape); + return 1; +} + +/* Perform matrix flattening. */ + +static unsigned int +matrix_reorg (void) +{ + struct cgraph_node *node; + + if (profile_info) + check_transpose_p = true; + else + check_transpose_p = false; + /* If there are hand written vectors, we skip this optimization. */ + for (node = cgraph_nodes; node; node = node->next) + if (!may_flatten_matrices (node)) + return 0; + matrices_to_reorg = htab_create (37, mtt_info_hash, mtt_info_eq, mat_free); + /* Find and record all potential matrices in the program. */ + find_matrices_decl (); + /* Analyze the accesses of the matrices (escaping analysis). */ + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed) + { + tree temp_fn; + + temp_fn = current_function_decl; + current_function_decl = node->decl; + push_cfun (DECL_STRUCT_FUNCTION (node->decl)); + bitmap_obstack_initialize (NULL); + gimple_register_cfg_hooks (); + + if (!gimple_in_ssa_p (cfun)) + { + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + pop_cfun (); + current_function_decl = temp_fn; + bitmap_obstack_release (NULL); + + return 0; + } + +#ifdef ENABLE_CHECKING + verify_flow_info (); +#endif + + if (!matrices_to_reorg) + { + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + pop_cfun (); + current_function_decl = temp_fn; + bitmap_obstack_release (NULL); + + return 0; + } + + /* Create htap for phi nodes. */ + htab_mat_acc_phi_nodes = htab_create (37, mat_acc_phi_hash, + mat_acc_phi_eq, free); + if (!check_transpose_p) + find_sites_in_func (false); + else + { + find_sites_in_func (true); + loop_optimizer_init (LOOPS_NORMAL); + if (current_loops) + scev_initialize (); + htab_traverse (matrices_to_reorg, analyze_transpose, NULL); + if (current_loops) + { + scev_finalize (); + loop_optimizer_finalize (); + current_loops = NULL; + } + } + /* If the current function is the allocation function for any of + the matrices we check its allocation and the escaping level. */ + htab_traverse (matrices_to_reorg, check_allocation_function, NULL); + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + pop_cfun (); + current_function_decl = temp_fn; + bitmap_obstack_release (NULL); + } + htab_traverse (matrices_to_reorg, transform_allocation_sites, NULL); + /* Now transform the accesses. */ + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed) + { + /* Remember that allocation sites have been handled. */ + tree temp_fn; + + temp_fn = current_function_decl; + current_function_decl = node->decl; + push_cfun (DECL_STRUCT_FUNCTION (node->decl)); + bitmap_obstack_initialize (NULL); + gimple_register_cfg_hooks (); + record_all_accesses_in_func (); + htab_traverse (matrices_to_reorg, transform_access_sites, NULL); + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + pop_cfun (); + current_function_decl = temp_fn; + bitmap_obstack_release (NULL); + } + htab_traverse (matrices_to_reorg, dump_matrix_reorg_analysis, NULL); + + current_function_decl = NULL; + set_cfun (NULL); + matrices_to_reorg = NULL; + return 0; +} + + +/* The condition for matrix flattening to be performed. */ +static bool +gate_matrix_reorg (void) +{ + return flag_ipa_matrix_reorg && flag_whole_program; +} + +struct simple_ipa_opt_pass pass_ipa_matrix_reorg = +{ + { + SIMPLE_IPA_PASS, + "matrix-reorg", /* name */ + gate_matrix_reorg, /* gate */ + matrix_reorg, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + 0, /* properties_required */ + PROP_trees, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_cgraph | TODO_dump_func /* todo_flags_finish */ + } +}; +