/* Predictive commoning.
- Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2005-2013 Free Software Foundation, Inc.
This file is part of GCC.
#include "tree.h"
#include "tm_p.h"
#include "cfgloop.h"
-#include "tree-flow.h"
+#include "gimple.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "gimple-ssa.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-ssa-loop-ivopts.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
+#include "tree-into-ssa.h"
+#include "expr.h"
+#include "tree-dfa.h"
+#include "tree-ssa.h"
#include "ggc.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "tree-affine.h"
#include "tree-inline.h"
+#include "wide-int-print.h"
/* The maximum number of iterations between the considered memory
references. */
unsigned distance;
/* Number of iterations offset from the first reference in the component. */
- double_int offset;
+ widest_int offset;
/* Number of the reference in a component, in dominance ordering. */
unsigned pos;
DR_IS_READ (ref->ref) ? "" : ", write");
fprintf (file, " offset ");
- dump_double_int (file, ref->offset, false);
+ print_decs (ref->offset, file);
fprintf (file, "\n");
fprintf (file, " distance %u\n", ref->distance);
tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset,
&name_expansions);
- aff_combination_const (&delta, type, tree_to_double_int (DR_INIT (dr)));
+ aff_combination_const (&delta, type, wi::to_widest (DR_INIT (dr)));
aff_combination_add (offset, &delta);
}
static bool
determine_offset (struct data_reference *a, struct data_reference *b,
- double_int *off)
+ widest_int *off)
{
aff_tree diff, baseb, step;
tree typea, typeb;
{
/* If the references have loop invariant address, check that they access
exactly the same location. */
- *off = double_int_zero;
+ *off = 0;
return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
&& operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
}
is a multiple of step. */
aff_combination_dr_offset (a, &diff);
aff_combination_dr_offset (b, &baseb);
- aff_combination_scale (&baseb, double_int_minus_one);
+ aff_combination_scale (&baseb, -1);
aff_combination_add (&diff, &baseb);
tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
FOR_EACH_VEC_ELT (depends, i, ddr)
{
- double_int dummy_off;
+ widest_int dummy_off;
if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
continue;
dataref = XCNEW (struct dref_d);
dataref->ref = dr;
dataref->stmt = DR_STMT (dr);
- dataref->offset = double_int_zero;
+ dataref->offset = 0;
dataref->distance = 0;
dataref->always_accessed
first = comp->refs[0];
ok = suitable_reference_p (first->ref, &comp->comp_step);
gcc_assert (ok);
- first->offset = double_int_zero;
+ first->offset = 0;
for (i = 1; comp->refs.iterate (i, &a); i++)
{
{
const dref *const da = (const dref *) a;
const dref *const db = (const dref *) b;
- int offcmp = (*da)->offset.scmp ((*db)->offset);
+ int offcmp = wi::cmps ((*da)->offset, (*db)->offset);
if (offcmp != 0)
return offcmp;
add_ref_to_chain (chain_p chain, dref ref)
{
dref root = get_chain_root (chain);
- double_int dist;
- gcc_assert (root->offset.sle (ref->offset));
- dist = ref->offset - root->offset;
- if (double_int::from_uhwi (MAX_DISTANCE).ule (dist))
+ gcc_assert (wi::les_p (root->offset, ref->offset));
+ widest_int dist = ref->offset - root->offset;
+ if (wi::leu_p (MAX_DISTANCE, dist))
{
free (ref);
return;
}
- gcc_assert (dist.fits_uhwi ());
+ gcc_assert (wi::fits_uhwi_p (dist));
chain->refs.safe_push (ref);
unsigned distance, struct data_reference *root)
{
aff_tree diff, base, step;
- double_int off;
+ widest_int off;
/* Both REF and ROOT must be accessing the same object. */
if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
-DISTANCE-th iteration. */
aff_combination_dr_offset (root, &diff);
aff_combination_dr_offset (ref, &base);
- aff_combination_scale (&base, double_int_minus_one);
+ aff_combination_scale (&base, -1);
aff_combination_add (&diff, &base);
tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
if (!aff_combination_constant_multiple_p (&diff, &step, &off))
return false;
- if (off != double_int::from_uhwi (distance))
+ if (off != distance)
return false;
return true;
unsigned i;
dref a;
chain_p chain = NULL;
- double_int last_ofs = double_int_zero;
+ widest_int last_ofs = 0;
/* Invariants are handled specially. */
if (comp->comp_step == RS_INVARIANT)
FOR_EACH_VEC_ELT (comp->refs, i, a)
{
if (!chain || DR_IS_WRITE (a->ref)
- || double_int::from_uhwi (MAX_DISTANCE).ule (a->offset - last_ofs))
+ || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
{
if (nontrivial_chain_p (chain))
{
gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
}
-/* Returns the reference to the address of REF in the ITER-th iteration of
- LOOP, or NULL if we fail to determine it (ITER may be negative). We
- try to preserve the original shape of the reference (not rewrite it
- as an indirect ref to the address), to make tree_could_trap_p in
- prepare_initializers_chain return false more often. */
+/* Returns a memory reference to DR in the ITER-th iteration of
+ the loop it was analyzed in. Append init stmts to STMTS. */
-static tree
-ref_at_iteration (struct loop *loop, tree ref, int iter)
+static tree
+ref_at_iteration (data_reference_p dr, int iter, gimple_seq *stmts)
{
- tree idx, *idx_p, type, val, op0 = NULL_TREE, ret;
- affine_iv iv;
- bool ok;
-
- if (handled_component_p (ref))
- {
- op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter);
- if (!op0)
- return NULL_TREE;
- }
- else if (!INDIRECT_REF_P (ref)
- && TREE_CODE (ref) != MEM_REF)
- return unshare_expr (ref);
-
- if (TREE_CODE (ref) == MEM_REF)
- {
- ret = unshare_expr (ref);
- idx = TREE_OPERAND (ref, 0);
- idx_p = &TREE_OPERAND (ret, 0);
- }
- else if (TREE_CODE (ref) == COMPONENT_REF)
- {
- /* Check that the offset is loop invariant. */
- if (TREE_OPERAND (ref, 2)
- && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
- return NULL_TREE;
-
- return build3 (COMPONENT_REF, TREE_TYPE (ref), op0,
- unshare_expr (TREE_OPERAND (ref, 1)),
- unshare_expr (TREE_OPERAND (ref, 2)));
- }
- else if (TREE_CODE (ref) == ARRAY_REF)
- {
- /* Check that the lower bound and the step are loop invariant. */
- if (TREE_OPERAND (ref, 2)
- && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
- return NULL_TREE;
- if (TREE_OPERAND (ref, 3)
- && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3)))
- return NULL_TREE;
-
- ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE,
- unshare_expr (TREE_OPERAND (ref, 2)),
- unshare_expr (TREE_OPERAND (ref, 3)));
- idx = TREE_OPERAND (ref, 1);
- idx_p = &TREE_OPERAND (ret, 1);
- }
+ tree off = DR_OFFSET (dr);
+ tree coff = DR_INIT (dr);
+ if (iter == 0)
+ ;
+ else if (TREE_CODE (DR_STEP (dr)) == INTEGER_CST)
+ coff = size_binop (PLUS_EXPR, coff,
+ size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
else
- return NULL_TREE;
-
- ok = simple_iv (loop, loop, idx, &iv, true);
- if (!ok)
- return NULL_TREE;
- iv.base = expand_simple_operations (iv.base);
- if (integer_zerop (iv.step))
- *idx_p = unshare_expr (iv.base);
- else
- {
- type = TREE_TYPE (iv.base);
- if (POINTER_TYPE_P (type))
- {
- val = fold_build2 (MULT_EXPR, sizetype, iv.step,
- size_int (iter));
- val = fold_build_pointer_plus (iv.base, val);
- }
- else
- {
- val = fold_build2 (MULT_EXPR, type, iv.step,
- build_int_cst_type (type, iter));
- val = fold_build2 (PLUS_EXPR, type, iv.base, val);
- }
- *idx_p = unshare_expr (val);
+ off = size_binop (PLUS_EXPR, off,
+ size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
+ tree addr = fold_build_pointer_plus (DR_BASE_ADDRESS (dr), off);
+ addr = force_gimple_operand_1 (addr, stmts, is_gimple_mem_ref_addr,
+ NULL_TREE);
+ tree alias_ptr = fold_convert (reference_alias_ptr_type (DR_REF (dr)), coff);
+ /* While data-ref analysis punts on bit offsets it still handles
+ bitfield accesses at byte boundaries. Cope with that. Note that
+ we cannot simply re-apply the outer COMPONENT_REF because the
+ byte-granular portion of it is already applied via DR_INIT and
+ DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
+ start at offset zero. */
+ if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
+ && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
+ {
+ tree field = TREE_OPERAND (DR_REF (dr), 1);
+ return build3 (BIT_FIELD_REF, TREE_TYPE (DR_REF (dr)),
+ build2 (MEM_REF, DECL_BIT_FIELD_TYPE (field),
+ addr, alias_ptr),
+ DECL_SIZE (field), bitsize_zero_node);
}
-
- return ret;
+ else
+ return fold_build2 (MEM_REF, TREE_TYPE (DR_REF (dr)), addr, alias_ptr);
}
/* Get the initialization expression for the INDEX-th temporary variable
stmt = find_common_use_stmt (&name1, &name2);
- if (!stmt)
+ if (!stmt
+ /* A simple post-dominance check - make sure the combination
+ is executed under the same condition as the references. */
+ || (gimple_bb (stmt) != gimple_bb (r1->stmt)
+ && gimple_bb (stmt) != gimple_bb (r2->stmt)))
return false;
acode = gimple_assign_rhs_code (stmt);
{
unsigned i, j;
chain_p ch1, ch2, cch;
- vec<chain_p> worklist = vec<chain_p>();
+ vec<chain_p> worklist = vNULL;
FOR_EACH_VEC_ELT (*chains, i, ch1)
if (chain_can_be_combined_p (ch1))
if (chain->inits[i] != NULL_TREE)
continue;
- init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
- if (!init)
- return false;
-
+ init = ref_at_iteration (dr, (int) i - n, &stmts);
if (!chain->all_always_accessed && tree_could_trap_p (init))
return false;
- init = force_gimple_operand (init, &stmts, false, NULL_TREE);
if (stmts)
gsi_insert_seq_on_edge_immediate (entry, stmts);
static bool
tree_predictive_commoning_loop (struct loop *loop)
{
- vec<loop_p> loop_nest;
vec<data_reference_p> datarefs;
vec<ddr_p> dependences;
struct component *components;
- vec<chain_p> chains = vec<chain_p>();
+ vec<chain_p> chains = vNULL;
unsigned unroll_factor;
struct tree_niter_desc desc;
bool unroll = false;
/* Find the data references and split them into components according to their
dependence relations. */
- datarefs.create (10);
+ stack_vec<loop_p, 3> loop_nest;
dependences.create (10);
- loop_nest.create (3);
+ datarefs.create (10);
if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
&dependences))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Cannot analyze data dependencies\n");
- loop_nest.release ();
free_data_refs (datarefs);
free_dependence_relations (dependences);
return false;
{
bool unrolled = false;
struct loop *loop;
- loop_iterator li;
unsigned ret = 0;
initialize_original_copy_tables ();
- FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
+ FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
if (optimize_loop_for_speed_p (loop))
{
unrolled |= tree_predictive_commoning_loop (loop);
return ret;
}
+
+/* Predictive commoning Pass. */
+
+static unsigned
+run_tree_predictive_commoning (void)
+{
+ if (!current_loops)
+ return 0;
+
+ return tree_predictive_commoning ();
+}
+
+static bool
+gate_tree_predictive_commoning (void)
+{
+ return flag_predictive_commoning != 0;
+}
+
+namespace {
+
+const pass_data pass_data_predcom =
+{
+ GIMPLE_PASS, /* type */
+ "pcom", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_PREDCOM, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa_only_virtuals, /* todo_flags_finish */
+};
+
+class pass_predcom : public gimple_opt_pass
+{
+public:
+ pass_predcom (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_predcom, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ bool gate () { return gate_tree_predictive_commoning (); }
+ unsigned int execute () { return run_tree_predictive_commoning (); }
+
+}; // class pass_predcom
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_predcom (gcc::context *ctxt)
+{
+ return new pass_predcom (ctxt);
+}
+
+
projects / thirdparty / gcc.git / blobdiff