/* 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;
unsigned always_accessed : 1;
} *dref;
-DEF_VEC_P (dref);
-DEF_VEC_ALLOC_P (dref, heap);
/* Type of the chain of the references. */
struct chain *ch1, *ch2;
/* The references in the chain. */
- VEC(dref,heap) *refs;
+ vec<dref> refs;
/* The maximum distance of the reference in the chain from the root. */
unsigned length;
/* The variables used to copy the value throughout iterations. */
- VEC(tree,heap) *vars;
+ vec<tree> vars;
/* Initializers for the variables. */
- VEC(tree,heap) *inits;
+ vec<tree> inits;
/* True if there is a use of a variable with the maximal distance
that comes after the root in the loop. */
unsigned combined : 1;
} *chain_p;
-DEF_VEC_P (chain_p);
-DEF_VEC_ALLOC_P (chain_p, heap);
/* Describes the knowledge about the step of the memory references in
the component. */
struct component
{
/* The references in the component. */
- VEC(dref,heap) *refs;
+ vec<dref> refs;
/* What we know about the step of the references in the component. */
enum ref_step_type comp_step;
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);
fprintf (file, "\n");
}
- if (chain->vars)
+ if (chain->vars.exists ())
{
fprintf (file, " vars");
- FOR_EACH_VEC_ELT (tree, chain->vars, i, var)
+ FOR_EACH_VEC_ELT (chain->vars, i, var)
{
fprintf (file, " ");
print_generic_expr (file, var, TDF_SLIM);
fprintf (file, "\n");
}
- if (chain->inits)
+ if (chain->inits.exists ())
{
fprintf (file, " inits");
- FOR_EACH_VEC_ELT (tree, chain->inits, i, var)
+ FOR_EACH_VEC_ELT (chain->inits, i, var)
{
fprintf (file, " ");
print_generic_expr (file, var, TDF_SLIM);
}
fprintf (file, " references:\n");
- FOR_EACH_VEC_ELT (dref, chain->refs, i, a)
+ FOR_EACH_VEC_ELT (chain->refs, i, a)
dump_dref (file, a);
fprintf (file, "\n");
/* Dumps CHAINS to FILE. */
-extern void dump_chains (FILE *, VEC (chain_p, heap) *);
+extern void dump_chains (FILE *, vec<chain_p> );
void
-dump_chains (FILE *file, VEC (chain_p, heap) *chains)
+dump_chains (FILE *file, vec<chain_p> chains)
{
chain_p chain;
unsigned i;
- FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
+ FOR_EACH_VEC_ELT (chains, i, chain)
dump_chain (file, chain);
}
fprintf (file, "Component%s:\n",
comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
- FOR_EACH_VEC_ELT (dref, comp->refs, i, a)
+ FOR_EACH_VEC_ELT (comp->refs, i, a)
dump_dref (file, a);
fprintf (file, "\n");
}
if (chain == NULL)
return;
- FOR_EACH_VEC_ELT (dref, chain->refs, i, ref)
+ FOR_EACH_VEC_ELT (chain->refs, i, ref)
free (ref);
- VEC_free (dref, heap, chain->refs);
- VEC_free (tree, heap, chain->vars);
- VEC_free (tree, heap, chain->inits);
+ chain->refs.release ();
+ chain->vars.release ();
+ chain->inits.release ();
free (chain);
}
/* Frees CHAINS. */
static void
-release_chains (VEC (chain_p, heap) *chains)
+release_chains (vec<chain_p> chains)
{
unsigned i;
chain_p chain;
- FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
+ FOR_EACH_VEC_ELT (chains, i, chain)
release_chain (chain);
- VEC_free (chain_p, heap, chains);
+ chains.release ();
}
/* Frees a component COMP. */
static void
release_component (struct component *comp)
{
- VEC_free (dref, heap, comp->refs);
+ comp->refs.release ();
free (comp);
}
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)),
last_always_executed_block (struct loop *loop)
{
unsigned i;
- VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+ vec<edge> exits = get_loop_exit_edges (loop);
edge ex;
basic_block last = loop->latch;
- FOR_EACH_VEC_ELT (edge, exits, i, ex)
+ FOR_EACH_VEC_ELT (exits, i, ex)
last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
- VEC_free (edge, heap, exits);
+ exits.release ();
return last;
}
static struct component *
split_data_refs_to_components (struct loop *loop,
- VEC (data_reference_p, heap) *datarefs,
- VEC (ddr_p, heap) *depends)
+ vec<data_reference_p> datarefs,
+ vec<ddr_p> depends)
{
- unsigned i, n = VEC_length (data_reference_p, datarefs);
+ unsigned i, n = datarefs.length ();
unsigned ca, ia, ib, bad;
unsigned *comp_father = XNEWVEC (unsigned, n + 1);
unsigned *comp_size = XNEWVEC (unsigned, n + 1);
dref dataref;
basic_block last_always_executed = last_always_executed_block (loop);
- FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
+ FOR_EACH_VEC_ELT (datarefs, i, dr)
{
if (!DR_REF (dr))
{
comp_father[n] = n;
comp_size[n] = 1;
- FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
+ FOR_EACH_VEC_ELT (datarefs, i, dr)
{
enum ref_step_type dummy;
}
}
- FOR_EACH_VEC_ELT (ddr_p, depends, i, ddr)
+ FOR_EACH_VEC_ELT (depends, i, ddr)
{
- double_int dummy_off;
+ widest_int dummy_off;
if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
continue;
comps = XCNEWVEC (struct component *, n);
bad = component_of (comp_father, n);
- FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
+ FOR_EACH_VEC_ELT (datarefs, i, dr)
{
ia = (unsigned) (size_t) dr->aux;
ca = component_of (comp_father, ia);
if (!comp)
{
comp = XCNEW (struct component);
- comp->refs = VEC_alloc (dref, heap, comp_size[ca]);
+ comp->refs.create (comp_size[ca]);
comps[ca] = comp;
}
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
= dominated_by_p (CDI_DOMINATORS, last_always_executed,
gimple_bb (dataref->stmt));
- dataref->pos = VEC_length (dref, comp->refs);
- VEC_quick_push (dref, comp->refs, dataref);
+ dataref->pos = comp->refs.length ();
+ comp->refs.quick_push (dataref);
}
for (i = 0; i < n; i++)
basic_block ba, bp = loop->header;
bool ok, has_write = false;
- FOR_EACH_VEC_ELT (dref, comp->refs, i, a)
+ FOR_EACH_VEC_ELT (comp->refs, i, a)
{
ba = gimple_bb (a->stmt);
has_write = true;
}
- first = VEC_index (dref, comp->refs, 0);
+ 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; VEC_iterate (dref, comp->refs, i, a); i++)
+ for (i = 1; comp->refs.iterate (i, &a); i++)
{
if (!determine_offset (first->ref, a->ref, &a->offset))
return false;
unsigned i;
*comp = act->next;
- FOR_EACH_VEC_ELT (dref, act->refs, i, ref)
+ FOR_EACH_VEC_ELT (act->refs, i, ref)
free (ref);
release_component (act);
}
{
const dref *const da = (const dref *) a;
const dref *const db = (const dref *) b;
- int offcmp = double_int_scmp ((*da)->offset, (*db)->offset);
+ int offcmp = wi::cmps ((*da)->offset, (*db)->offset);
if (offcmp != 0)
return offcmp;
static inline dref
get_chain_root (chain_p chain)
{
- return VEC_index (dref, chain->refs, 0);
+ return chain->refs[0];
}
/* Adds REF to the chain CHAIN. */
add_ref_to_chain (chain_p chain, dref ref)
{
dref root = get_chain_root (chain);
- double_int dist;
- gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0);
- dist = double_int_sub (ref->offset, root->offset);
- if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0)
+ 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 (double_int_fits_in_uhwi_p (dist));
+ gcc_assert (wi::fits_uhwi_p (dist));
- VEC_safe_push (dref, heap, chain->refs, ref);
+ chain->refs.safe_push (ref);
- ref->distance = double_int_to_uhwi (dist);
+ ref->distance = dist.to_uhwi ();
if (ref->distance >= chain->length)
{
chain->all_always_accessed = true;
- FOR_EACH_VEC_ELT (dref, comp->refs, i, ref)
+ FOR_EACH_VEC_ELT (comp->refs, i, ref)
{
- VEC_safe_push (dref, heap, chain->refs, ref);
+ chain->refs.safe_push (ref);
chain->all_always_accessed &= ref->always_accessed;
}
chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
- VEC_safe_push (dref, heap, chain->refs, ref);
+ chain->refs.safe_push (ref);
chain->all_always_accessed = ref->always_accessed;
ref->distance = 0;
static bool
nontrivial_chain_p (chain_p chain)
{
- return chain != NULL && VEC_length (dref, chain->refs) > 1;
+ return chain != NULL && chain->refs.length () > 1;
}
/* Returns the ssa name that contains the value of REF, or NULL_TREE if there
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 (!double_int_equal_p (off, uhwi_to_double_int (distance)))
+ if (off != distance)
return false;
return true;
nw->distance = ref->distance + 1;
nw->always_accessed = 1;
- FOR_EACH_VEC_ELT (dref, chain->refs, i, aref)
+ FOR_EACH_VEC_ELT (chain->refs, i, aref)
if (aref->distance >= nw->distance)
break;
- VEC_safe_insert (dref, heap, chain->refs, i, nw);
+ chain->refs.safe_insert (i, nw);
if (nw->distance > chain->length)
{
dref ref, root = get_chain_root (chain);
gimple phi;
- FOR_EACH_VEC_ELT (dref, chain->refs, i, ref)
+ FOR_EACH_VEC_ELT (chain->refs, i, ref)
{
phi = find_looparound_phi (loop, ref, root);
if (!phi)
static void
determine_roots_comp (struct loop *loop,
struct component *comp,
- VEC (chain_p, heap) **chains)
+ vec<chain_p> *chains)
{
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)
{
chain = make_invariant_chain (comp);
- VEC_safe_push (chain_p, heap, *chains, chain);
+ chains->safe_push (chain);
return;
}
- VEC_qsort (dref, comp->refs, order_drefs);
+ comp->refs.qsort (order_drefs);
- FOR_EACH_VEC_ELT (dref, comp->refs, i, a)
+ FOR_EACH_VEC_ELT (comp->refs, i, a)
{
if (!chain || DR_IS_WRITE (a->ref)
- || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE),
- double_int_sub (a->offset, last_ofs)) <= 0)
+ || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
{
if (nontrivial_chain_p (chain))
{
add_looparound_copies (loop, chain);
- VEC_safe_push (chain_p, heap, *chains, chain);
+ chains->safe_push (chain);
}
else
release_chain (chain);
if (nontrivial_chain_p (chain))
{
add_looparound_copies (loop, chain);
- VEC_safe_push (chain_p, heap, *chains, chain);
+ chains->safe_push (chain);
}
else
release_chain (chain);
static void
determine_roots (struct loop *loop,
- struct component *comps, VEC (chain_p, heap) **chains)
+ struct component *comps, vec<chain_p> *chains)
{
struct component *comp;
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
return fold_build2 (chain->op, chain->rslt_type, e1, e2);
}
else
- return VEC_index (tree, chain->inits, index);
+ return chain->inits[index];
}
/* Returns a new temporary variable used for the I-th variable carrying
since this is an nonempty chain, reuse_first cannot be true. */
gcc_assert (n > 0 || !reuse_first);
- chain->vars = VEC_alloc (tree, heap, n + 1);
+ chain->vars.create (n + 1);
if (chain->type == CT_COMBINATION)
ref = gimple_assign_lhs (root->stmt);
for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
{
var = predcom_tmp_var (ref, i, tmp_vars);
- VEC_quick_push (tree, chain->vars, var);
+ chain->vars.quick_push (var);
}
if (reuse_first)
- VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0));
+ chain->vars.quick_push (chain->vars[0]);
- FOR_EACH_VEC_ELT (tree, chain->vars, i, var)
- VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL));
+ FOR_EACH_VEC_ELT (chain->vars, i, var)
+ chain->vars[i] = make_ssa_name (var, NULL);
for (i = 0; i < n; i++)
{
- var = VEC_index (tree, chain->vars, i);
- next = VEC_index (tree, chain->vars, i + 1);
+ var = chain->vars[i];
+ next = chain->vars[i + 1];
init = get_init_expr (chain, i);
init = force_gimple_operand (init, &stmts, true, NULL_TREE);
gsi_insert_seq_on_edge_immediate (entry, stmts);
phi = create_phi_node (var, loop->header);
- SSA_NAME_DEF_STMT (var) = phi;
add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
}
initialize_root_vars (loop, chain, tmp_vars);
replace_ref_with (root->stmt,
- VEC_index (tree, chain->vars, chain->length),
+ chain->vars[chain->length],
true, in_lhs);
}
static void
initialize_root_vars_lm (struct loop *loop, dref root, bool written,
- VEC(tree, heap) **vars, VEC(tree, heap) *inits,
+ vec<tree> *vars, vec<tree> inits,
bitmap tmp_vars)
{
unsigned i;
/* Find the initializer for the variable, and check that it cannot
trap. */
- init = VEC_index (tree, inits, 0);
+ init = inits[0];
- *vars = VEC_alloc (tree, heap, written ? 2 : 1);
+ vars->create (written ? 2 : 1);
var = predcom_tmp_var (ref, 0, tmp_vars);
- VEC_quick_push (tree, *vars, var);
+ vars->quick_push (var);
if (written)
- VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0));
+ vars->quick_push ((*vars)[0]);
- FOR_EACH_VEC_ELT (tree, *vars, i, var)
- VEC_replace (tree, *vars, i, make_ssa_name (var, NULL));
+ FOR_EACH_VEC_ELT (*vars, i, var)
+ (*vars)[i] = make_ssa_name (var, NULL);
- var = VEC_index (tree, *vars, 0);
+ var = (*vars)[0];
init = force_gimple_operand (init, &stmts, written, NULL_TREE);
if (stmts)
if (written)
{
- next = VEC_index (tree, *vars, 1);
+ next = (*vars)[1];
phi = create_phi_node (var, loop->header);
- SSA_NAME_DEF_STMT (var) = phi;
add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
}
static void
execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
{
- VEC (tree, heap) *vars;
+ vec<tree> vars;
dref a;
unsigned n_writes = 0, ridx, i;
tree var;
gcc_assert (chain->type == CT_INVARIANT);
gcc_assert (!chain->combined);
- FOR_EACH_VEC_ELT (dref, chain->refs, i, a)
+ FOR_EACH_VEC_ELT (chain->refs, i, a)
if (DR_IS_WRITE (a->ref))
n_writes++;
/* If there are no reads in the loop, there is nothing to do. */
- if (n_writes == VEC_length (dref, chain->refs))
+ if (n_writes == chain->refs.length ())
return;
initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
&vars, chain->inits, tmp_vars);
ridx = 0;
- FOR_EACH_VEC_ELT (dref, chain->refs, i, a)
+ FOR_EACH_VEC_ELT (chain->refs, i, a)
{
bool is_read = DR_IS_READ (a->ref);
n_writes--;
if (n_writes)
{
- var = VEC_index (tree, vars, 0);
+ var = vars[0];
var = make_ssa_name (SSA_NAME_VAR (var), NULL);
- VEC_replace (tree, vars, 0, var);
+ vars[0] = var;
}
else
ridx = 1;
}
- replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
+ replace_ref_with (a->stmt, vars[ridx],
!is_read, !is_read);
}
- VEC_free (tree, heap, vars);
+ vars.release ();
}
/* Returns the single statement in that NAME is used, excepting
{
/* For combined chains, just remove the statements that are used to
compute the values of the expression (except for the root one). */
- for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
+ for (i = 1; chain->refs.iterate (i, &a); i++)
remove_stmt (a->stmt);
}
else
and replace the uses of the original references by these
variables. */
initialize_root (loop, chain, tmp_vars);
- for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
+ for (i = 1; chain->refs.iterate (i, &a); i++)
{
- var = VEC_index (tree, chain->vars, chain->length - a->distance);
+ var = chain->vars[chain->length - a->distance];
replace_ref_with (a->stmt, var, false, false);
}
}
optimized. */
static unsigned
-determine_unroll_factor (VEC (chain_p, heap) *chains)
+determine_unroll_factor (vec<chain_p> chains)
{
chain_p chain;
unsigned factor = 1, af, nfactor, i;
unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
- FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
+ FOR_EACH_VEC_ELT (chains, i, chain)
{
if (chain->type == CT_INVARIANT || chain->combined)
continue;
Uids of the newly created temporary variables are marked in TMP_VARS. */
static void
-execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains,
+execute_pred_commoning (struct loop *loop, vec<chain_p> chains,
bitmap tmp_vars)
{
chain_p chain;
unsigned i;
- FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
+ FOR_EACH_VEC_ELT (chains, i, chain)
{
if (chain->type == CT_INVARIANT)
execute_load_motion (loop, chain, tmp_vars);
phi node, record the ssa name that is defined by it. */
static void
-replace_phis_by_defined_names (VEC (chain_p, heap) *chains)
+replace_phis_by_defined_names (vec<chain_p> chains)
{
chain_p chain;
dref a;
unsigned i, j;
- FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
- FOR_EACH_VEC_ELT (dref, chain->refs, j, a)
+ FOR_EACH_VEC_ELT (chains, i, chain)
+ FOR_EACH_VEC_ELT (chain->refs, j, a)
{
if (gimple_code (a->stmt) == GIMPLE_PHI)
{
NULL, use it to set the stmt field. */
static void
-replace_names_by_phis (VEC (chain_p, heap) *chains)
+replace_names_by_phis (vec<chain_p> chains)
{
chain_p chain;
dref a;
unsigned i, j;
- FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
- FOR_EACH_VEC_ELT (dref, chain->refs, j, a)
+ FOR_EACH_VEC_ELT (chains, i, chain)
+ FOR_EACH_VEC_ELT (chain->refs, j, a)
if (a->stmt == NULL)
{
a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
struct epcc_data
{
- VEC (chain_p, heap) *chains;
+ vec<chain_p> chains;
bitmap tmp_vars;
};
gimple stmt, phi;
imm_use_iterator iter;
- SSA_NAME_VAR (name) = var;
+ replace_ssa_name_symbol (name, var);
while (1)
{
return;
name = PHI_RESULT (phi);
- SSA_NAME_VAR (name) = var;
+ replace_ssa_name_symbol (name, var);
}
}
phi = gsi_stmt (psi);
name = PHI_RESULT (phi);
var = SSA_NAME_VAR (name);
- if (!bitmap_bit_p (tmp_vars, DECL_UID (var)))
+ if (!var || !bitmap_bit_p (tmp_vars, DECL_UID (var)))
continue;
use = PHI_ARG_DEF_FROM_EDGE (phi, e);
gcc_assert (TREE_CODE (use) == SSA_NAME);
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);
if (ch1->length != ch2->length)
return NULL;
- if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
+ if (ch1->refs.length () != ch2->refs.length ())
return NULL;
- for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
- && VEC_iterate (dref, ch2->refs, i, r2)); i++)
+ for (i = 0; (ch1->refs.iterate (i, &r1)
+ && ch2->refs.iterate (i, &r2)); i++)
{
if (r1->distance != r2->distance)
return NULL;
new_chain->rslt_type = rslt_type;
new_chain->length = ch1->length;
- for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
- && VEC_iterate (dref, ch2->refs, i, r2)); i++)
+ for (i = 0; (ch1->refs.iterate (i, &r1)
+ && ch2->refs.iterate (i, &r2)); i++)
{
nw = XCNEW (struct dref_d);
nw->stmt = stmt_combining_refs (r1, r2);
nw->distance = r1->distance;
- VEC_safe_push (dref, heap, new_chain->refs, nw);
+ new_chain->refs.safe_push (nw);
}
new_chain->has_max_use_after = false;
root_stmt = get_chain_root (new_chain)->stmt;
- for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
+ for (i = 1; new_chain->refs.iterate (i, &nw); i++)
{
if (nw->distance == new_chain->length
&& !stmt_dominates_stmt_p (nw->stmt, root_stmt))
/* Try to combine the CHAINS. */
static void
-try_combine_chains (VEC (chain_p, heap) **chains)
+try_combine_chains (vec<chain_p> *chains)
{
unsigned i, j;
chain_p ch1, ch2, cch;
- VEC (chain_p, heap) *worklist = NULL;
+ vec<chain_p> worklist = vNULL;
- FOR_EACH_VEC_ELT (chain_p, *chains, i, ch1)
+ FOR_EACH_VEC_ELT (*chains, i, ch1)
if (chain_can_be_combined_p (ch1))
- VEC_safe_push (chain_p, heap, worklist, ch1);
+ worklist.safe_push (ch1);
- while (!VEC_empty (chain_p, worklist))
+ while (!worklist.is_empty ())
{
- ch1 = VEC_pop (chain_p, worklist);
+ ch1 = worklist.pop ();
if (!chain_can_be_combined_p (ch1))
continue;
- FOR_EACH_VEC_ELT (chain_p, *chains, j, ch2)
+ FOR_EACH_VEC_ELT (*chains, j, ch2)
{
if (!chain_can_be_combined_p (ch2))
continue;
cch = combine_chains (ch1, ch2);
if (cch)
{
- VEC_safe_push (chain_p, heap, worklist, cch);
- VEC_safe_push (chain_p, heap, *chains, cch);
+ worklist.safe_push (cch);
+ chains->safe_push (cch);
break;
}
}
}
+
+ worklist.release ();
}
/* Prepare initializers for CHAIN in LOOP. Returns false if this is
/* Find the initializers for the variables, and check that they cannot
trap. */
- chain->inits = VEC_alloc (tree, heap, n);
+ chain->inits.create (n);
for (i = 0; i < n; i++)
- VEC_quick_push (tree, chain->inits, NULL_TREE);
+ chain->inits.quick_push (NULL_TREE);
/* If we have replaced some looparound phi nodes, use their initializers
instead of creating our own. */
- FOR_EACH_VEC_ELT (dref, chain->refs, i, laref)
+ FOR_EACH_VEC_ELT (chain->refs, i, laref)
{
if (gimple_code (laref->stmt) != GIMPLE_PHI)
continue;
gcc_assert (laref->distance > 0);
- VEC_replace (tree, chain->inits, n - laref->distance,
- PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
+ chain->inits[n - laref->distance]
+ = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
}
for (i = 0; i < n; i++)
{
- if (VEC_index (tree, chain->inits, i) != NULL_TREE)
+ 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);
- VEC_replace (tree, chain->inits, i, init);
+ chain->inits[i] = init;
}
return true;
be used because the initializers might trap. */
static void
-prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
+prepare_initializers (struct loop *loop, vec<chain_p> chains)
{
chain_p chain;
unsigned i;
- for (i = 0; i < VEC_length (chain_p, chains); )
+ for (i = 0; i < chains.length (); )
{
- chain = VEC_index (chain_p, chains, i);
+ chain = chains[i];
if (prepare_initializers_chain (loop, chain))
i++;
else
{
release_chain (chain);
- VEC_unordered_remove (chain_p, chains, i);
+ chains.unordered_remove (i);
}
}
}
static bool
tree_predictive_commoning_loop (struct loop *loop)
{
- VEC (loop_p, heap) *loop_nest;
- VEC (data_reference_p, heap) *datarefs;
- VEC (ddr_p, heap) *dependences;
+ vec<data_reference_p> datarefs;
+ vec<ddr_p> dependences;
struct component *components;
- VEC (chain_p, heap) *chains = NULL;
+ 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 = VEC_alloc (data_reference_p, heap, 10);
- dependences = VEC_alloc (ddr_p, heap, 10);
- loop_nest = VEC_alloc (loop_p, heap, 3);
+ stack_vec<loop_p, 3> loop_nest;
+ dependences.create (10);
+ 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");
- VEC_free (loop_p, heap, loop_nest);
free_data_refs (datarefs);
free_dependence_relations (dependences);
return false;
dump_data_dependence_relations (dump_file, dependences);
components = split_data_refs_to_components (loop, datarefs, dependences);
- VEC_free (loop_p, heap, loop_nest);
+ loop_nest.release ();
free_dependence_relations (dependences);
if (!components)
{
determine_roots (loop, components, &chains);
release_components (components);
- if (!chains)
+ if (!chains.exists ())
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
{
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);
+}
+
+