diff options
Diffstat (limited to 'gcc/tree-ssa-loop-memset.c')
| -rw-r--r-- | gcc/tree-ssa-loop-memset.c | 733 |
1 files changed, 733 insertions, 0 deletions
diff --git a/gcc/tree-ssa-loop-memset.c b/gcc/tree-ssa-loop-memset.c new file mode 100644 index 00000000000..b3dbd154e20 --- /dev/null +++ b/gcc/tree-ssa-loop-memset.c @@ -0,0 +1,733 @@ +/* APPLE LOCAL begin loops-to-memset (ENTIRE FILE!) */ +/* Loops to memset. + Copyright (C) 2004 Free Software Foundation, Inc. + Contributed by Andrew Pinski <apinski@apple.com>. + + 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 2, 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 COPYING. If not, write to the Free + Software Foundation, 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "ggc.h" +#include "tree.h" +#include "rtl.h" +#include "tm_p.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "output.h" +#include "diagnostic.h" +#include "tree-flow.h" +#include "tree-dump.h" +#include "timevar.h" +#include "cfgloop.h" +#include "domwalk.h" +#include "params.h" +#include "tree-pass.h" +#include "flags.h" +#include "tree-data-ref.h" +#include "tree-scalar-evolution.h" +#include "tree-chrec.h" +#include "tree-vectorizer.h" + +static bool memset_debug_stats (struct loop *loop); +static bool memset_debug_details (struct loop *loop); + +/* Function memset_analyze_data_refs. + + Find all the data references in the loop. + + Handle INDIRECT_REFs and one dimensional ARRAY_REFs + which base is really an array (not a pointer). + + This is different from vect_analyze_data_refs in tree-vectorizer.c as + we handle unaligned data stores and we only handle data stores. */ + +static bool +memset_analyze_data_refs (loop_vec_info loop_vinfo) +{ + struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); + basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo); + int nbbs = loop->num_nodes; + block_stmt_iterator si; + int j; + struct data_reference *dr; + + if (memset_debug_details (NULL)) + fprintf (dump_file, "\n<<memset_analyze_data_refs>>\n"); + + for (j = 0; j < nbbs; j++) + { + basic_block bb = bbs[j]; + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) + { + tree stmt = bsi_stmt (si); + stmt_vec_info stmt_info = vinfo_for_stmt (stmt); + v_may_def_optype v_may_defs = STMT_V_MAY_DEF_OPS (stmt); + v_must_def_optype v_must_defs = STMT_V_MUST_DEF_OPS (stmt); + vuse_optype vuses = STMT_VUSE_OPS (stmt); + varray_type *datarefs = NULL; + int nvuses, nv_may_defs, nv_must_defs; + tree memref = NULL; + tree array_base; + tree symbl; + + /* Assumption: there exists a data-ref in stmt, if and only if + it has vuses/vdefs. */ + + if (!vuses && !v_may_defs && !v_must_defs) + continue; + + nvuses = NUM_VUSES (vuses); + nv_may_defs = NUM_V_MAY_DEFS (v_may_defs); + nv_must_defs = NUM_V_MUST_DEFS (v_must_defs); + + if (nvuses && (nv_may_defs || nv_must_defs)) + { + if (memset_debug_details (NULL)) + { + fprintf (dump_file, "unexpected vdefs and vuses in stmt: "); + print_generic_expr (dump_file, stmt, TDF_SLIM); + } + return false; + } + + if (TREE_CODE (stmt) != MODIFY_EXPR) + { + if (memset_debug_details (NULL)) + { + fprintf (dump_file, "unexpected vops in stmt: "); + print_generic_expr (dump_file, stmt, TDF_SLIM); + } + return false; + } + + if (vuses) + { + if (memset_debug_details (NULL)) + { + fprintf (dump_file, "Memory access in the loop: "); + print_generic_expr (dump_file, stmt, TDF_SLIM); + } + return false; + } + else /* vdefs */ + { + memref = TREE_OPERAND (stmt, 0); + datarefs = &(LOOP_VINFO_DATAREF_WRITES (loop_vinfo)); + } + + if (TREE_CODE (memref) == INDIRECT_REF) + { + /* MERGE FIXME */ + abort (); + /* dr = vect_analyze_pointer_ref_access (memref, stmt, false); */ + if (! dr) + return false; + symbl = DR_BASE_NAME (dr); + } + else if (TREE_CODE (memref) == ARRAY_REF) + { + tree base; + array_base = TREE_OPERAND (memref, 0); + + if (TREE_CODE (array_base) == ARRAY_REF) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + { + fprintf (dump_file, + "not vectorized: multi-dimensional array."); + print_generic_expr (dump_file, stmt, TDF_SLIM); + } + return false; + } + + dr = analyze_array (stmt, memref, false); + + /* Find the relevant symbol for aliasing purposes. */ + base = DR_BASE_NAME (dr); + switch (TREE_CODE (base)) + { + case VAR_DECL: + symbl = base; + break; + default: + if (memset_debug_stats (loop) + || memset_debug_details (loop)) + { + fprintf (dump_file, + "not transformed: unhandled struct/class field access "); + print_generic_expr (dump_file, stmt, TDF_SLIM); + } + return false; + } /* switch */ + } + else + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + { + fprintf (dump_file, "not transformed: unhandled data ref: "); + print_generic_expr (dump_file, stmt, TDF_SLIM); + } + return false; + } + + /* Find and record the memtag assigned to this data-ref. */ + if (TREE_CODE (symbl) == VAR_DECL + || (TREE_CODE (symbl) == COMPONENT_REF + && TREE_CODE (TREE_OPERAND (symbl, 0)) == VAR_DECL)) + STMT_VINFO_MEMTAG (stmt_info) = symbl; + else if (TREE_CODE (symbl) == SSA_NAME) + { + tree tag; + symbl = SSA_NAME_VAR (symbl); + tag = get_var_ann (symbl)->type_mem_tag; + if (!tag) + { + tree ptr = TREE_OPERAND (memref, 0); + if (TREE_CODE (ptr) == SSA_NAME) + tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag; + } + if (!tag) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, "not vectorized: no memtag for ref."); + return false; + } + STMT_VINFO_MEMTAG (stmt_info) = tag; + } + else + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + { + fprintf (dump_file, "not vectorized: unsupported data-ref: "); + print_generic_expr (dump_file, memref, TDF_SLIM); + } + return false; + } + + VARRAY_PUSH_GENERIC_PTR (*datarefs, dr); + STMT_VINFO_DATA_REF (stmt_info) = dr; + } + } + + return true; +} + +/* Function memset_analyze_loop_with_symbolic_num_of_iters. + + In case the number of iterations that LOOP iterates in unknown at compile + time, an epilog loop will be generated, and the loop induction variables + (IVs) will be "advanced" to the value they are supposed to take just before + the epilog loop. Here we check that the access function of the loop IVs + and the expression that represents the loop bound are simple enough. + These restrictions will be relxed in the future. */ + +static bool +memset_analyze_loop_with_symbolic_num_of_iters (tree niters, + struct loop *loop) +{ + basic_block bb = loop->header; + tree phi; + + if (memset_debug_details (NULL)) + fprintf (dump_file, + "\n<<memset_analyze_loop_with_symbolic_num_of_iters>>\n"); + + if (chrec_contains_undetermined (niters)) + { + if (memset_debug_details (NULL)) + fprintf (dump_file, "Infinite number of iterations."); + return false; + } + + if (!niters) + { + if (memset_debug_details (NULL)) + fprintf (dump_file, "niters is NULL pointer."); + return false; + } + + if (memset_debug_details (NULL)) + { + fprintf (dump_file, "Symbolic number of iterations is "); + print_generic_expr (dump_file, niters, TDF_DETAILS); + } + + /* Analyze phi functions of the loop header. */ + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + tree access_fn = NULL; + tree evolution_part; + + if (memset_debug_details (NULL)) + { + fprintf (dump_file, "Analyze phi: "); + print_generic_expr (dump_file, phi, TDF_SLIM); + } + + /* Skip virtual phi's. The data dependences that are associated with + virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */ + + if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) + { + if (memset_debug_details (NULL)) + fprintf (dump_file, "virtual phi. skip."); + continue; + } + + /* Analyze the evolution function. */ + + access_fn = instantiate_parameters + (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); + + if (!access_fn) + { + if (memset_debug_details (NULL)) + fprintf (dump_file, "No Access function."); + return false; + } + + if (memset_debug_details (NULL)) + { + fprintf (dump_file, "Access function of PHI: "); + print_generic_expr (dump_file, access_fn, TDF_SLIM); + } + + evolution_part = evolution_part_in_loop_num (access_fn, loop->num); + + if (evolution_part == NULL_TREE) + return false; + + /* FORNOW: We do not transform initial conditions of IVs + which evolution functions are a polynomial of degree >= 2. */ + + if (tree_is_chrec (evolution_part)) + return false; + } + + return true; +} + + +/* Function debug_loop_details. + + For memset debug dumps. */ + +static bool +memset_debug_details (struct loop *loop) +{ + basic_block bb; + block_stmt_iterator si; + tree node = NULL_TREE; + + if (!dump_file || !(dump_flags & TDF_DETAILS)) + return false; + + if (!loop) + { + fprintf (dump_file, "\n"); + return true; + } + + if (!loop->header) + return false; + + bb = loop->header; + + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) + { + node = bsi_stmt (si); + if (node && EXPR_P (node) && EXPR_LOCUS (node)) + break; + } + + if (node && EXPR_P (node) && EXPR_LOCUS (node) + && EXPR_FILENAME (node) && EXPR_LINENO (node)) + { + fprintf (dump_file, "\nloop at %s:%d: ", + EXPR_FILENAME (node), EXPR_LINENO (node)); + return true; + } + + return false; +} + +/* Function debug_loop_stats. + + For vectorization statistics dumps. */ + +static bool +memset_debug_stats (struct loop *loop) +{ + basic_block bb; + block_stmt_iterator si; + tree node = NULL_TREE; + + if (!dump_file || !(dump_flags & TDF_STATS)) + return false; + + if (!loop) + { + fprintf (dump_file, "\n"); + return true; + } + + if (!loop->header) + return false; + + bb = loop->header; + + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) + { + node = bsi_stmt (si); + if (node && EXPR_P (node) && EXPR_LOCUS (node)) + break; + } + + if (node && EXPR_P (node) && EXPR_LOCUS (node) + && EXPR_FILENAME (node) && EXPR_LINENO (node)) + { + fprintf (dump_file, "\nloop at %s:%d: ", + EXPR_FILENAME (node), EXPR_LINENO (node)); + return true; + } + + return false; +} + +/* Function memset_analyze_loop_form. + + Verify the following restrictions: + - it's an inner-most loop + - number of BBs = 2 (which are the loop header and the latch) + - the loop has a pre-header + - the loop has a single entry and exit + - the loop exit condition is simple enough, and the number of iterations + can be analyzed (a countable loop). + + This differs from vect_analyze_loop_form by we handle non constant + interations. */ + +static loop_vec_info +memset_analyze_loop_form (struct loop *loop) +{ + loop_vec_info loop_vinfo; + tree loop_cond; + tree number_of_iterations = NULL_TREE; + + if (memset_debug_details (loop)) + fprintf (dump_file, "\n<<memset_analyze_loop_form>>\n"); + + if (loop->level > 1 /* FORNOW: inner-most loop */ + || loop->num_exits > 1 || loop->num_entries > 1 || loop->num_nodes != 2 + || !loop->pre_header || !loop->header || !loop->latch) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + { + fprintf (dump_file, "not vectorized: bad loop form.\n"); + if (loop->level > 1) + fprintf (dump_file, "nested loop.\n"); + else if (loop->num_exits > 1 || loop->num_entries > 1) + fprintf (dump_file, "multiple entries or exits.\n"); + else if (loop->num_nodes != 2 || !loop->header || !loop->latch) + fprintf (dump_file, "too many BBs in loop.\n"); + else if (!loop->pre_header) + fprintf (dump_file, "no pre-header BB for loop.\n"); + } + + return NULL; + } + + /* We assume that the loop exit condition is at the end of the loop. i.e, + that the loop is represented as a do-while (with a proper if-guard + before the loop if needed), where the loop header contains all the + executable statements, and the latch is empty. */ + if (!empty_block_p (loop->latch)) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, "not vectorized: unexpectd loop form."); + return NULL; + } + + if (empty_block_p (loop->header)) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, "not transformed: empty loop."); + return NULL; + } + + loop_cond = vect_get_loop_niters (loop, &number_of_iterations); + if (!loop_cond) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, "not vectorized: complicated exit condition.\n"); + return NULL; + } + + if (!number_of_iterations) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, + "not vectorized: number of iterations cannot be computed."); + return NULL; + } + + loop_vinfo = new_loop_vec_info (loop); + LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations; + + if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)) + { + if (memset_debug_details (NULL)) + fprintf (dump_file, "loop bound unknown."); + + /* Unknown loop bound. */ + if (!memset_analyze_loop_with_symbolic_num_of_iters (number_of_iterations, + loop)) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, "not transformed: can't determine loop bound.\n"); + return NULL; + } + else + { + /* We need only one loop entry for unknown loop bound support. */ + if (loop->num_entries != 1 || !loop->pre_header) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, + "not transformed: more than one loop entry."); + return NULL; + } + } + } + else if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0) + { + if (memset_debug_stats (loop) || memset_debug_details (loop)) + fprintf (dump_file, "not transformed: number of iterations = 0.\n"); + return NULL; + } + + LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond; + + return loop_vinfo; +} + +/* Mark all the variables in V_MAY_DEF or V_MUST_DEF operands for STMT for + renaming. This becomes necessary when we modify all of a non-scalar. */ + +static void +mark_all_v_defs (tree stmt) +{ + tree sym; + ssa_op_iter iter; + + get_stmt_operands (stmt); + + FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_VIRTUAL_DEFS) + { + if (TREE_CODE (sym) == SSA_NAME) + sym = SSA_NAME_VAR (sym); + bitmap_set_bit (vars_to_rename, var_ann (sym)->uid); + } +} + + +/* This is the main entry point for the transformation. */ +void +tree_ssa_memset (struct loops *loops) +{ + unsigned i; + + for (i = 1; i < loops->num; i++) + { + struct loop *loop = loops->parray[i]; + loop_vec_info vectorizer_info; + varray_type writes; + struct data_reference *drw; + tree access_chrec; + tree noi; + + if (!loop) + continue; + + flow_loop_scan (loop, LOOP_ALL); + vectorizer_info = memset_analyze_loop_form (loop); + if (!vectorizer_info) + continue; + + if (!memset_analyze_data_refs (vectorizer_info)) + { + if (memset_debug_details (loop)) + fprintf (dump_file, "bad data references."); + destroy_loop_vec_info (vectorizer_info); + continue; + } + + writes = LOOP_VINFO_DATAREF_WRITES (vectorizer_info); + + /* TODO: handle more than data write. */ + if (VARRAY_ACTIVE_SIZE (writes) != 1) + { + if (memset_debug_details (loop)) + fprintf (dump_file, "no or more than one store."); + destroy_loop_vec_info (vectorizer_info); + continue; + } + + drw = VARRAY_GENERIC_PTR (writes, 0); + + /* TODO: handle multi-dimension arrays. */ + if (DR_NUM_DIMENSIONS (drw) != 1) + { + if (memset_debug_details (loop)) + fprintf (dump_file, "cannot handle multiple dimension array."); + destroy_loop_vec_info (vectorizer_info); + continue; + } + + if (TREE_CODE (TREE_OPERAND (DR_STMT (drw), 1)) != INTEGER_CST) + { + if (memset_debug_details (loop)) + fprintf (dump_file, "non constant store value."); + destroy_loop_vec_info (vectorizer_info); + continue; + } + + /* TODO: handle other than zero values in types + where the unit size is greater than one. */ + if (!integer_zerop (TREE_OPERAND (DR_STMT (drw), 1)) + && !integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drw))))) + { + if (memset_debug_details (loop)) + fprintf (dump_file, "cannot handle other zero value for types of other than char (for now)."); + destroy_loop_vec_info (vectorizer_info); + continue; + } + + access_chrec = DR_ACCESS_FN (drw, 0); + + noi = LOOP_VINFO_NITERS (vectorizer_info); + + /* Build the memset call. */ + { + tree array = DR_BASE_NAME (drw); + tree value = TREE_OPERAND (DR_STMT (drw), 1); + tree function = implicit_built_in_decls[BUILT_IN_MEMSET]; + tree args = NULL_TREE; + block_stmt_iterator bsi = bsi_last (loop->pre_header); + tree array_1 = make_rename_temp (ptr_type_node, NULL); + tree temp, stmt, var; + tree ni_name; + + stmt = DR_STMT (drw); + + /* Remove the array access stmt. */ + { + block_stmt_iterator access_bsi; + /* Mark the MAY_DEF as needed to be renamed. */ + mark_all_v_defs (stmt); + access_bsi = bsi_for_stmt (stmt); + bsi_remove (&access_bsi); + } + + if (TREE_CODE (TREE_TYPE (array)) == ARRAY_TYPE) + { + tree type = TREE_TYPE (TREE_TYPE (array)); + tree base = array; + + while (TREE_CODE (base) == REALPART_EXPR + || TREE_CODE (base) == IMAGPART_EXPR + || handled_component_p (base)) + base = TREE_OPERAND (base, 0); + + if (DECL_P (base)) + TREE_ADDRESSABLE (base) = 1; + + array = build4 (ARRAY_REF, type, array, size_zero_node, + NULL_TREE, NULL_TREE); + array = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (array)), + array); + } + + { + tree start = CHREC_LEFT (access_chrec); + tree size_mult; + tree array_var; + start = fold_convert (TREE_TYPE (array), start); + size_mult = fold_convert (TREE_TYPE (array), + TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (array)))); + array = fold (build2 (PLUS_EXPR, + TREE_TYPE (array), + array, + fold (build2 (MULT_EXPR, + TREE_TYPE (array), + start, + size_mult)))); + array_var = create_tmp_var (TREE_TYPE (array), "tmp"); + add_referenced_tmp_var (array_var); + array = force_gimple_operand (array, &stmt, false, array_var); + + if (stmt) + bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING); + } + + var = create_tmp_var (size_type_node, "tmp"); + add_referenced_tmp_var (var); + + noi = fold (build2 (MULT_EXPR, TREE_TYPE (noi), noi, + fold_convert (TREE_TYPE (noi), + TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (array)))))); + + stmt = NULL_TREE; + ni_name = force_gimple_operand (noi, &stmt, false, var); + + if (stmt) + bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING); + + temp = build2 (MODIFY_EXPR, void_type_node, array_1, + array); + + bsi_insert_after (&bsi, temp, BSI_CONTINUE_LINKING); + + args = tree_cons (NULL, ni_name, args); + args = tree_cons (NULL, fold_convert (integer_type_node, value), args); + args = tree_cons (NULL, array_1, args); + + temp = build_function_call_expr (function, args); + + bsi_insert_after (&bsi, temp, BSI_CONTINUE_LINKING); + } + + destroy_loop_vec_info (vectorizer_info); + + } + + rewrite_into_ssa (false); + if (!bitmap_empty_p (vars_to_rename)) + { + /* The rewrite of ssa names may cause violation of loop closed ssa + form invariants. TODO -- avoid these rewrites completely. + Information in virtual phi nodes is sufficient for it. */ + rewrite_into_loop_closed_ssa (); + } + bitmap_clear (vars_to_rename); +} + +/* APPLE LOCAL end loops-to-memset (ENTIRE FILE!) */ |