/* Predictive commoning.
- Copyright (C) 2005, 2007 Free Software Foundation, Inc.
-
+ Copyright (C) 2005, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
+
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
<http://www.gnu.org/licenses/>. */
and if needed, we could also take register pressure into account.
Let us demonstrate what is done on an example:
-
+
for (i = 0; i < 100; i++)
{
a[i+2] = a[i] + a[i+1];
making the further transformations simpler. Also, the shorter chains
need the same number of registers, but may require lower unrolling
factor in order to get rid of the copies on the loop latch.
-
+
In our example, we get the following chains (the chain for c is invalid).
a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
with the smallest positive distance to the read. Then, we remove
the references that are not used in any of these chains, discard the
empty groups, and propagate all the links so that they point to the
- single root reference of the chain (adjusting their distance
+ single root reference of the chain (adjusting their distance
appropriately). Some extra care needs to be taken for references with
step 0. In our example (the numbers indicate the distance of the
reuse),
times. The stores to RN (R0) in the copies of the loop body are
periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
be coalesced and the copies can be eliminated.
-
+
TODO -- copy propagation and other optimizations may change the live
ranges of the temporary registers and prevent them from being coalesced;
this may increase the register pressure.
#include "tree-chrec.h"
#include "params.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-pass.h"
#include "tree-affine.h"
#include "tree-inline.h"
references. */
#define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
-
+
/* Data references (or phi nodes that carry data reference values across
loop iterations). */
-typedef struct dref
+typedef struct dref_d
{
/* The reference itself. */
struct data_reference *ref;
struct component *comp_list = NULL, *comp;
dref dataref;
basic_block last_always_executed = last_always_executed_block (loop);
-
+
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
{
if (!DR_REF (dr))
&& (ia == bad || ib == bad
|| !determine_offset (dra, drb, &dummy_off)))
continue;
-
+
merge_comps (comp_father, comp_size, ia, ib);
}
comps[ca] = comp;
}
- dataref = XCNEW (struct dref);
+ dataref = XCNEW (struct dref_d);
dataref->ref = dr;
dataref->stmt = DR_STMT (dr);
dataref->offset = double_int_zero;
/* Returns true if the component COMP satisfies the conditions
described in 2) at the beginning of this file. LOOP is the current
loop. */
-
+
static bool
suitable_component_p (struct loop *loop, struct component *comp)
{
return true;
}
-
+
/* Check the conditions on references inside each of components COMPS,
and remove the unsuitable components from the list. The new list
of components is returned. The conditions are described in 2) at
static void
insert_looparound_copy (chain_p chain, dref ref, gimple phi)
{
- dref nw = XCNEW (struct dref), aref;
+ dref nw = XCNEW (struct dref_d), aref;
unsigned i;
nw->stmt = phi;
unsigned i;
dref a;
chain_p chain = NULL;
+ double_int last_ofs = double_int_zero;
/* Invariants are handled specially. */
if (comp->comp_step == RS_INVARIANT)
for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
{
- if (!chain || !DR_IS_READ (a->ref))
+ if (!chain || !DR_IS_READ (a->ref)
+ || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE),
+ double_int_add (a->offset,
+ double_int_neg (last_ofs))) <= 0)
{
if (nontrivial_chain_p (chain))
- VEC_safe_push (chain_p, heap, *chains, chain);
+ {
+ add_looparound_copies (loop, chain);
+ VEC_safe_push (chain_p, heap, *chains, chain);
+ }
else
release_chain (chain);
chain = make_rooted_chain (a);
+ last_ofs = a->offset;
continue;
}
gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
return;
}
-
+
/* Since the reference is of gimple_reg type, it should only
appear as lhs or rhs of modify statement. */
gcc_assert (is_gimple_assign (stmt));
if (in_lhs)
{
/* We have statement
-
+
OLD = VAL
If OLD is a memory reference, then VAL is gimple_val, and we transform
OLD = VAL
NEW = VAL
- Otherwise, we are replacing a combination chain,
+ Otherwise, we are replacing a combination chain,
VAL is the expression that performs the combination, and OLD is an
SSA name. In this case, we transform the assignment to
else if (!INDIRECT_REF_P (ref))
return unshare_expr (ref);
- if (TREE_CODE (ref) == INDIRECT_REF)
+ if (INDIRECT_REF_P (ref))
{
- ret = build1 (INDIRECT_REF, TREE_TYPE (ref), NULL_TREE);
+ /* Take care for INDIRECT_REF and MISALIGNED_INDIRECT_REF at
+ the same time. */
+ ret = copy_node (ref);
idx = TREE_OPERAND (ref, 0);
idx_p = &TREE_OPERAND (ret, 0);
}
else
return NULL_TREE;
- ok = simple_iv (loop, first_stmt (loop->header), idx, &iv, true);
+ ok = simple_iv (loop, loop, idx, &iv, true);
if (!ok)
return NULL_TREE;
iv.base = expand_simple_operations (iv.base);
void
mark_virtual_ops_for_renaming (gimple stmt)
{
- ssa_op_iter iter;
tree var;
if (gimple_code (stmt) == GIMPLE_PHI)
}
update_stmt (stmt);
-
- FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
- {
- if (TREE_CODE (var) == SSA_NAME)
- var = SSA_NAME_VAR (var);
- mark_sym_for_renaming (var);
- }
-}
-
-/* Calls mark_virtual_ops_for_renaming for all members of LIST. */
-
-static void
-mark_virtual_ops_for_renaming_list (gimple_seq list)
-{
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start (list); !gsi_end_p (gsi); gsi_next (&gsi))
- mark_virtual_ops_for_renaming (gsi_stmt (gsi));
+ if (gimple_vuse (stmt))
+ mark_sym_for_renaming (gimple_vop (cfun));
}
/* Returns a new temporary variable used for the I-th variable carrying
predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
{
tree type = TREE_TYPE (ref);
- tree var = create_tmp_var (type, get_lsm_tmp_name (ref, i));
-
/* We never access the components of the temporary variable in predictive
commoning. */
- if (TREE_CODE (type) == COMPLEX_TYPE
- || TREE_CODE (type) == VECTOR_TYPE)
- DECL_GIMPLE_REG_P (var) = 1;
+ tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
add_referenced_var (var);
bitmap_set_bit (tmp_vars, DECL_UID (var));
}
if (reuse_first)
VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0));
-
+
for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL));
init = force_gimple_operand (init, &stmts, true, NULL_TREE);
if (stmts)
- {
- mark_virtual_ops_for_renaming_list (stmts);
- gsi_insert_seq_on_edge_immediate (entry, stmts);
- }
+ 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);
- add_phi_arg (phi, next, latch);
+ add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
+ add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
}
}
VEC_quick_push (tree, *vars, var);
if (written)
VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0));
-
+
for (i = 0; VEC_iterate (tree, *vars, i, var); i++)
VEC_replace (tree, *vars, i, make_ssa_name (var, NULL));
var = VEC_index (tree, *vars, 0);
-
+
init = force_gimple_operand (init, &stmts, written, NULL_TREE);
if (stmts)
- {
- mark_virtual_ops_for_renaming_list (stmts);
- gsi_insert_seq_on_edge_immediate (entry, stmts);
- }
+ gsi_insert_seq_on_edge_immediate (entry, stmts);
if (written)
{
next = VEC_index (tree, *vars, 1);
phi = create_phi_node (var, loop->header);
SSA_NAME_DEF_STMT (var) = phi;
- add_phi_arg (phi, init, entry);
- add_phi_arg (phi, next, latch);
+ add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
+ add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
}
else
{
for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
if (!DR_IS_READ (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))
return;
else
ridx = 1;
}
-
+
replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
!is_read, !is_read);
}
while (1)
{
gimple_stmt_iterator bsi;
-
+
bsi = gsi_for_stmt (stmt);
name = gimple_assign_lhs (stmt);
else
execute_pred_commoning_chain (loop, chain, tmp_vars);
}
-
+
update_ssa (TODO_update_ssa_only_virtuals);
}
execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
}
-/* Returns true if we can and should unroll LOOP FACTOR times. Number
- of iterations of the loop is returned in NITER. */
-
-static bool
-should_unroll_loop_p (struct loop *loop, unsigned factor,
- struct tree_niter_desc *niter)
-{
- edge exit;
-
- if (factor == 1)
- return false;
-
- /* Check whether unrolling is possible. We only want to unroll loops
- for that we are able to determine number of iterations. We also
- want to split the extra iterations of the loop from its end,
- therefore we require that the loop has precisely one
- exit. */
-
- exit = single_dom_exit (loop);
- if (!exit)
- return false;
-
- if (!number_of_iterations_exit (loop, exit, niter, false))
- return false;
-
- /* And of course, we must be able to duplicate the loop. */
- if (!can_duplicate_loop_p (loop))
- return false;
-
- /* The final loop should be small enough. */
- if (tree_num_loop_insns (loop, &eni_size_weights) * factor
- > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
- return false;
-
- return true;
-}
-
/* Base NAME and all the names in the chain of phi nodes that use it
on variable VAR. The phi nodes are recognized by being in the copies of
the header of the LOOP. */
{
gimple stmt, phi;
imm_use_iterator iter;
- edge e;
SSA_NAME_VAR (name) = var;
if (!phi)
return;
- if (gimple_bb (phi) == loop->header)
- e = loop_latch_edge (loop);
- else
- e = single_pred_edge (gimple_bb (stmt));
-
name = PHI_RESULT (phi);
SSA_NAME_VAR (name) = var;
}
/* Insert the new statement combining NAME1 and NAME2 before S1, and
combine it with the rhs of S1. */
- var = create_tmp_var (type, "predreastmp");
+ var = create_tmp_reg (type, "predreastmp");
add_referenced_var (var);
new_name = make_ssa_name (var, NULL);
new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
- var = create_tmp_var (type, "predreastmp");
+ var = create_tmp_reg (type, "predreastmp");
add_referenced_var (var);
tmp_name = make_ssa_name (var, NULL);
tree rslt_type = NULL_TREE;
if (ch1 == ch2)
- return false;
+ return NULL;
if (ch1->length != ch2->length)
return NULL;
for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
&& VEC_iterate (dref, ch2->refs, i, r2)); i++)
{
- nw = XCNEW (struct dref);
+ nw = XCNEW (struct dref_d);
nw->stmt = stmt_combining_refs (r1, r2);
nw->distance = r1->distance;
}
}
-/* Sets alias information based on data reference DR for REF,
- if necessary. */
-
-static void
-set_alias_info (tree ref, struct data_reference *dr)
-{
- tree var;
- tree tag = DR_SYMBOL_TAG (dr);
-
- gcc_assert (tag != NULL_TREE);
-
- ref = get_base_address (ref);
- if (!ref || !INDIRECT_REF_P (ref))
- return;
-
- var = SSA_NAME_VAR (TREE_OPERAND (ref, 0));
- if (var_ann (var)->symbol_mem_tag)
- return;
-
- if (!MTAG_P (tag))
- new_type_alias (var, tag, ref);
- else
- var_ann (var)->symbol_mem_tag = tag;
-}
-
/* Prepare initializers for CHAIN in LOOP. Returns false if this is
impossible because one of these initializers may trap, true otherwise. */
init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
if (!init)
return false;
-
+
if (!chain->all_always_accessed && tree_could_trap_p (init))
return false;
init = force_gimple_operand (init, &stmts, false, NULL_TREE);
if (stmts)
- {
- mark_virtual_ops_for_renaming_list (stmts);
- gsi_insert_seq_on_edge_immediate (entry, stmts);
- }
- set_alias_info (init, dr);
+ gsi_insert_seq_on_edge_immediate (entry, stmts);
VEC_replace (tree, chain->inits, i, init);
}
that its number of iterations is divisible by the factor. */
unroll_factor = determine_unroll_factor (chains);
scev_reset ();
- unroll = should_unroll_loop_p (loop, unroll_factor, &desc);
+ unroll = (unroll_factor > 1
+ && can_unroll_loop_p (loop, unroll_factor, &desc));
exit = single_dom_exit (loop);
/* Execute the predictive commoning transformations, and possibly unroll the
dta.chains = chains;
dta.tmp_vars = tmp_vars;
-
+
update_ssa (TODO_update_ssa_only_virtuals);
/* Cfg manipulations performed in tree_transform_and_unroll_loop before
OSDN Git Service
