CbC/CbC_gcc: gcc/tree-predcom.c comparison

comparison gcc/tree-predcom.c @ 55:77e2b8dfacca gcc-4.4.5

update it from 4.4.3 to 4.5.0

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 23:39:51 +0900
parents	a06113de4d67
children	b7f97abdc517

comparison

equal deleted inserted replaced

-:c156f1bd5cd9
+:77e2b8dfacca
 /* Predictive commoning.
-Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
+Copyright (C) 2005, 2007, 2008, 2009 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/>.  */
 /* This file implements the predictive commoning optimization.  Predictive
 incorporate data dependence analysis to detect the opportunities, perform
 loop unrolling to avoid copies together with renaming immediately,
 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];
 b[10] = b[10] + i;
 c[i] = c[99 - i];
 chains whose head is the write whose values are used by the reads in
 the same chain.  The chains are then processed independently,
 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}
 b[10]{read,+0}, b[10]{write,+0}
 d[i + 1]{read,+0}, d[i]{write,+1}
 together with the distance of this reuse.  I.e. we take the last
 reference before it with distance 0, or the last of the references
 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
 appropriately).  Some extra care needs to be taken for references with
 step 0.  In our example (the numbers indicate the distance of the
 reuse),
 a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
 (N + 1) for each root reference (N for references for that we avoided
 creating RN).  If F and the loop is small enough, loop is unrolled F
 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.
 In our case, F = 2 and the (main loop of the) result is
 /* The maximum number of iterations between the considered memory
 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;
 /* The statement in that the reference appears.  */
 struct data_reference *dr, *dra, *drb;
 struct data_dependence_relation *ddr;
 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))
 	{
 	  /* A fake reference for call or asm_expr that may clobber memory;
 /* If both A and B are reads, we may ignore unsuitable dependences.  */
 if (DR_IS_READ (dra) && DR_IS_READ (drb)
 	  && (ia == bad || ib == bad
 	      || !determine_offset (dra, drb, &dummy_off)))
 	continue;
 merge_comps (comp_father, comp_size, ia, ib);
 }
 comps = XCNEWVEC (struct component *, n);
 bad = component_of (comp_father, n);
 	  comp = XCNEW (struct component);
 	  comp->refs = VEC_alloc (dref, heap, comp_size[ca]);
 	  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;
 dataref->distance = 0;
 }
 /* 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)
 {
 unsigned i;
 dref a, first;
 if (has_write && comp->comp_step == RS_ANY)
 return false;
 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
 the beginning of this file.  LOOP is the current loop.  */
 /* Adds a reference for the looparound copy of REF in PHI to CHAIN.  */
 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;
 nw->distance = ref->distance + 1;
 nw->always_accessed = 1;
 /* Turn the phi node into GIMPLE_ASSIGN.  */
 new_stmt = gimple_build_assign (val, new_tree);
 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));
 bsi = gsi_for_stmt (stmt);
 }
 if (in_lhs)
 {
 /* We have statement
 	 OLD = VAL
 	 If OLD is a memory reference, then VAL is gimple_val, and we transform
 	 this to
 	 OLD = VAL
 	 NEW = VAL
 	 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
 	 OLD = VAL
 	 NEW = OLD
 /* Marks all virtual operands of statement STMT for renaming.  */
 void
 mark_virtual_ops_for_renaming (gimple stmt)
 {
-ssa_op_iter iter;
 tree var;
 if (gimple_code (stmt) == GIMPLE_PHI)
 {
 var = PHI_RESULT (stmt);
 mark_sym_for_renaming (var);
 return;
 }
 update_stmt (stmt);
+if (gimple_vuse (stmt))
-FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
+mark_sym_for_renaming (gimple_vop (cfun));
-{
-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));
 }
 /* Returns a new temporary variable used for the I-th variable carrying
 value of REF.  The variable's uid is marked in TMP_VARS.  */
 var = predcom_tmp_var (ref, i, tmp_vars);
 VEC_quick_push (tree, chain->vars, 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));
 for (i = 0; i < n; i++)
 {
 next = VEC_index (tree, chain->vars, i + 1);
 init = get_init_expr (chain, i);
 init = force_gimple_operand (init, &stmts, true, NULL_TREE);
 if (stmts)
-	{
+	gsi_insert_seq_on_edge_immediate (entry, stmts);
-	  mark_virtual_ops_for_renaming_list (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, init, entry, UNKNOWN_LOCATION);
-add_phi_arg (phi, next, latch);
+add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
 }
 }
 /* Create the variables and initialization statement for root of chain
 CHAIN.  Uids of the newly created temporary variables are marked
 *vars = VEC_alloc (tree, heap, written ? 2 : 1);
 var = predcom_tmp_var (ref, 0, tmp_vars);
 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)
-{
+gsi_insert_seq_on_edge_immediate (entry, stmts);
-mark_virtual_ops_for_renaming_list (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, init, entry, UNKNOWN_LOCATION);
-add_phi_arg (phi, next, latch);
+add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
 }
 else
 {
 gimple init_stmt = gimple_build_assign (var, init);
 mark_virtual_ops_for_renaming (init_stmt);
 gcc_assert (chain->type == CT_INVARIANT);
 gcc_assert (!chain->combined);
 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;
 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
 	      VEC_replace (tree, vars, 0, var);
 	    }
 	  else
 	    ridx = 1;
 	}
 replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
 			!is_read, !is_read);
 }
 VEC_free (tree, heap, vars);
 }
 while (1)
 {
 gimple_stmt_iterator bsi;
 bsi = gsi_for_stmt (stmt);
 name = gimple_assign_lhs (stmt);
 gcc_assert (TREE_CODE (name) == SSA_NAME);
 if (chain->type == CT_INVARIANT)
 	execute_load_motion (loop, chain, tmp_vars);
 else
 	execute_pred_commoning_chain (loop, chain, tmp_vars);
 }
 update_ssa (TODO_update_ssa_only_virtuals);
 }
 /* For each reference in CHAINS, if its defining statement is
 phi node, record the ssa name that is defined by it.  */
 /* Restore phi nodes that were replaced by ssa names before
 tree_transform_and_unroll_loop (see detailed description in
 tree_predictive_commoning_loop).  */
 replace_names_by_phis (dta->chains);
 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.  */
 new_chain->length = ch1->length;
 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;
 VEC_safe_push (dref, heap, new_chain->refs, nw);
 }
 	    }
 	}
 }
 }
-/* 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.  */
 static bool
 prepare_initializers_chain (struct loop *loop, chain_p chain)
 	continue;
 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)
-	{
+	gsi_insert_seq_on_edge_immediate (entry, stmts);
-	  mark_virtual_ops_for_renaming_list (stmts);
-	  gsi_insert_seq_on_edge_immediate (entry, stmts);
-	}
-set_alias_info (init, dr);
 VEC_replace (tree, chain->inits, i, init);
 }
 return true;
 /* Determine the unroll factor, and if the loop should be unrolled, ensure
 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
 loop.  */
 if (unroll)
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
 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
 	 execute_pred_commoning_cbck is called may cause phi nodes to be
 	 reallocated, which is a problem since CHAINS may point to these

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-predcom.c @ 55:77e2b8dfacca gcc-4.4.5