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

comparison gcc/tree-predcom.c @ 132:d34655255c78

update gcc-8.2

author	mir3636
date	Thu, 25 Oct 2018 10:21:07 +0900
parents	84e7813d76e9
children	1830386684a0

comparison

equal deleted inserted replaced

-:e108057fa461
+:d34655255c78
 /* Predictive commoning.
-Copyright (C) 2005-2017 Free Software Foundation, Inc.
+Copyright (C) 2005-2018 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
 a[n] = 2;
 a[n+1] = 2;
 The interesting part is this can be viewed either as general store motion
 or general dead store elimination in either intra/inter-iterations way.
+With trivial effort, we also support load inside Store-Store chains if the
+load is dominated by a store statement in the same iteration of loop.  You
+can see this as a restricted Store-Mixed-Load-Store chain.
 TODO: For now, we don't support store-store chains in multi-exit loops.  We
 force to not unroll in case of store-store chain even if other chains might
 ask for unroll.
 tree type = TREE_TYPE (DR_OFFSET (dr));
 aff_tree delta;
 tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset,
 				  &name_expansions);
-aff_combination_const (&delta, type, wi::to_widest (DR_INIT (dr)));
+aff_combination_const (&delta, type, wi::to_poly_widest (DR_INIT (dr)));
 aff_combination_add (offset, &delta);
 }
 /* Determines number of iterations of the innermost enclosing loop before B
 refers to exactly the same location as A and stores it to OFF.  If A and
 returns false, otherwise returns true.  Both A and B are assumed to
 satisfy suitable_reference_p.  */
 static bool
 determine_offset (struct data_reference *a, struct data_reference *b,
-		  widest_int *off)
+		  poly_widest_int *off)
 {
 aff_tree diff, baseb, step;
 tree typea, typeb;
 /* Check that both the references access the location in the same type.  */
 	}
 }
 FOR_EACH_VEC_ELT (depends, i, ddr)
 {
-widest_int dummy_off;
+poly_widest_int dummy_off;
 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 	continue;
 dra = DDR_A (ddr);
 dataref->always_accessed
 	      = dominated_by_p (CDI_DOMINATORS, last_always_executed,
 				gimple_bb (dataref->stmt));
 dataref->pos = comp->refs.length ();
 comp->refs.quick_push (dataref);
-if (DR_IS_READ (dr))
-	comp->eliminate_store_p = false;
 }
 for (i = 0; i < n; i++)
 {
 comp = comps[i];
 gcc_assert (ok);
 first->offset = 0;
 for (i = 1; comp->refs.iterate (i, &a); i++)
 {
-if (!determine_offset (first->ref, a->ref, &a->offset))
+/* Polynomial offsets are no use, since we need to know the
+	 gap between iteration numbers at compile time.  */
+poly_widest_int offset;
+if (!determine_offset (first->ref, a->ref, &offset)
+	  || !offset.is_constant (&a->offset))
 	return false;
 enum ref_step_type a_step;
 gcc_checking_assert (suitable_reference_p (a->ref, &a_step)
 			   && a_step == comp->comp_step);
 return offcmp;
 return (*da)->pos - (*db)->pos;
 }
+/* Compares two drefs A and B by their position.  Callback for qsort.  */
+static int
+order_drefs_by_pos (const void *a, const void *b)
+{
+const dref *const da = (const dref *) a;
+const dref *const db = (const dref *) b;
+return (*da)->pos - (*db)->pos;
+}
 /* Returns root of the CHAIN.  */
 static inline dref
 get_chain_root (chain_p chain)
 {
 return chain->refs[0];
 }
-/* Given CHAIN, returns the last ref at DISTANCE, or NULL if it doesn't
+/* Given CHAIN, returns the last write ref at DISTANCE, or NULL if it doesn't
 exist.  */
 static inline dref
-get_chain_last_ref_at (chain_p chain, unsigned distance)
+get_chain_last_write_at (chain_p chain, unsigned distance)
 {
-unsigned i;
+for (unsigned i = chain->refs.length (); i > 0; i--)
+if (DR_IS_WRITE (chain->refs[i - 1]->ref)
-for (i = chain->refs.length (); i > 0; i--)
+	&& distance == chain->refs[i - 1]->distance)
-if (distance == chain->refs[i - 1]->distance)
+return chain->refs[i - 1];
-break;
+return NULL;
-return (i > 0) ? chain->refs[i - 1] : NULL;
+}
+/* Given CHAIN, returns the last write ref with the same distance before load
+at index LOAD_IDX, or NULL if it doesn't exist.  */
+static inline dref
+get_chain_last_write_before_load (chain_p chain, unsigned load_idx)
+{
+gcc_assert (load_idx < chain->refs.length ());
+unsigned distance = chain->refs[load_idx]->distance;
+for (unsigned i = load_idx; i > 0; i--)
+if (DR_IS_WRITE (chain->refs[i - 1]->ref)
+	&& distance == chain->refs[i - 1]->distance)
+return chain->refs[i - 1];
+return NULL;
 }
 /* Adds REF to the chain CHAIN.  */
 static void
 {
 dref root = get_chain_root (chain);
 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 (wi::fits_uhwi_p (dist));
 chain->refs.safe_push (ref);
 ref->distance = dist.to_uhwi ();
 if (ref->distance >= chain->length)
 {
 chain->length = ref->distance;
 chain->has_max_use_after = false;
 }
+/* Promote this chain to CT_STORE_STORE if it has multiple stores.  */
+if (DR_IS_WRITE (ref->ref))
+chain->type = CT_STORE_STORE;
 /* Don't set the flag for store-store chain since there is no use.  */
 if (chain->type != CT_STORE_STORE
 && ref->distance == chain->length
 && ref->pos > root->pos)
 static bool
 valid_initializer_p (struct data_reference *ref,
 		     unsigned distance, struct data_reference *root)
 {
 aff_tree diff, base, step;
-widest_int off;
+poly_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))
 return false;
 tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
 				  &step, &name_expansions);
 if (!aff_combination_constant_multiple_p (&diff, &step, &off))
 return false;
-if (off != distance)
+if (maybe_ne (off, distance))
 return false;
 return true;
 }
 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
 loop enclosing PHI).  */
 memset (&init_dr, 0, sizeof (struct data_reference));
 DR_REF (&init_dr) = init_ref;
 DR_STMT (&init_dr) = phi;
-if (!dr_analyze_innermost (&DR_INNERMOST (&init_dr), init_ref, loop))
+if (!dr_analyze_innermost (&DR_INNERMOST (&init_dr), init_ref, loop,
+			     init_stmt))
 return NULL;
 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
 return NULL;
 return;
 }
 /* Trivial component.  */
 if (comp->refs.length () <= 1)
-return;
+{
+if (comp->refs.length () == 1)
+	{
+	  free (comp->refs[0]);
+	  comp->refs.truncate (0);
+	}
+return;
+}
 comp->refs.qsort (order_drefs);
+/* For Store-Store chain, we only support load if it is dominated by a
+store statement in the same iteration of loop.  */
+if (comp->eliminate_store_p)
+for (a = NULL, i = 0; i < comp->refs.length (); i++)
+{
+	if (DR_IS_WRITE (comp->refs[i]->ref))
+	  a = comp->refs[i];
+	else if (a == NULL || a->offset != comp->refs[i]->offset)
+	  {
+	    /* If there is load that is not dominated by a store in the
+	       same iteration of loop, clear the flag so no Store-Store
+	       chain is generated for this component.  */
+	    comp->eliminate_store_p = false;
+	    break;
+	  }
+}
+/* Determine roots and create chains for components.  */
 FOR_EACH_VEC_ELT (comp->refs, i, a)
 {
 if (!chain
+	  || (chain->type == CT_LOAD && DR_IS_WRITE (a->ref))
 	  || (!comp->eliminate_store_p && DR_IS_WRITE (a->ref))
 	  || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
 	{
 	  if (nontrivial_chain_p (chain))
 	    {
 	      chains->safe_push (chain);
 	    }
 	  else
 	    release_chain (chain);
-	  if (DR_IS_READ (a->ref))
+	  /* Determine type of the chain.  If the root reference is a load,
-	    type = CT_LOAD;
+	     this can only be a CT_LOAD chain; other chains are intialized
-	  else
+	     to CT_STORE_LOAD and might be promoted to CT_STORE_STORE when
-	    type = comp->eliminate_store_p ? CT_STORE_STORE : CT_STORE_LOAD;
+	     new reference is added.  */
+	  type = DR_IS_READ (a->ref) ? CT_LOAD : CT_STORE_LOAD;
 	  chain = make_rooted_chain (a, type);
 	  last_ofs = a->offset;
 	  continue;
 	}
 /* Check stores in chain for elimination if they only store loop invariant
 values.  */
 for (unsigned i = 0; i < chain->length; i++)
 {
-dref a = get_chain_last_ref_at (chain, i);
+dref a = get_chain_last_write_at (chain, i);
 if (a == NULL)
 	continue;
 gimple *def_stmt, *stmt = a->stmt;
 if (!gimple_assign_single_p (stmt))
 chain->vars.safe_grow_cleared (n);
 /* Initialize root value for eliminated stores at each distance.  */
 for (i = 0; i < n; i++)
 {
-dref a = get_chain_last_ref_at (chain, i);
+dref a = get_chain_last_write_at (chain, i);
 if (a == NULL)
 	continue;
 var = gimple_assign_rhs1 (a->stmt);
 chain->vars[a->distance] = var;
 init = get_init_expr (chain, i);
 if (init == NULL_TREE)
 	{
 	  /* Root value is rhs operand of the store to be eliminated if
 	     it isn't loaded from memory before loop.  */
-	  dref a = get_chain_last_ref_at (chain, i);
+	  dref a = get_chain_last_write_at (chain, i);
 	  val = gimple_assign_rhs1 (a->stmt);
 	  if (TREE_CLOBBER_P (val))
-	    val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (var));
+	    {
+	      val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (var));
+	      gimple_assign_set_rhs1 (a->stmt, val);
+	    }
 	  vtemps[n - i - 1] = val;
 	}
 else
 	{
 static void
 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
 			      bitmap tmp_vars)
 {
-unsigned i, n;
+unsigned i;
 dref a;
 tree var;
 bool in_lhs;
 if (chain->combined)
 	     be eliminated, because there is no following killing store.
 	     We need to generate these stores after loop.  */
 	  finalize_eliminated_stores (loop, chain);
 	}
-/* Eliminate the stores killed by following store.  */
+bool last_store_p = true;
-n = chain->refs.length ();
+for (i = chain->refs.length (); i > 0; i--)
-for (i = 0; i < n - 1; i++)
+	{
-	remove_stmt (chain->refs[i]->stmt);
+	  a = chain->refs[i - 1];
+	  /* Preserve the last store of the chain.  Eliminate other stores
+	     which are killed by the last one.  */
+	  if (DR_IS_WRITE (a->ref))
+	    {
+	      if (last_store_p)
+		last_store_p = false;
+	      else
+		remove_stmt (a->stmt);
+	      continue;
+	    }
+	  /* Any load in Store-Store chain must be dominated by a previous
+	     store, we replace the load reference with rhs of the store.  */
+	  dref b = get_chain_last_write_before_load (chain, i - 1);
+	  gcc_assert (b != NULL);
+	  var = gimple_assign_rhs1 (b->stmt);
+	  replace_ref_with (a->stmt, var, false, false);
+	}
 }
 else
 {
 /* For non-combined chains, set up the variables that hold its value.  */
 initialize_root_vars (loop, chain, tmp_vars);
 update_stmt (stmt);
 }
 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
-are combined in a single statement, and returns this statement.  Note the
+are combined in a single statement, and returns this statement.  */
-statement is inserted before INSERT_BEFORE if it's not NULL.  */
 static gimple *
-reassociate_to_the_same_stmt (tree name1, tree name2, gimple *insert_before)
+reassociate_to_the_same_stmt (tree name1, tree name2)
 {
 gimple *stmt1, *stmt2, *root1, *root2, *s1, *s2;
 gassign *new_stmt, *tmp_stmt;
 tree new_name, tmp_name, var, r1, r2;
 unsigned dist1, dist2;
 /* Insert the new statement combining NAME1 and NAME2 before S1, and
 combine it with the rhs of S1.  */
 var = create_tmp_reg (type, "predreastmp");
 new_name = make_ssa_name (var);
 new_stmt = gimple_build_assign (new_name, code, name1, name2);
-if (insert_before && stmt_dominates_stmt_p (insert_before, s1))
-bsi = gsi_for_stmt (insert_before);
-else
-bsi = gsi_for_stmt (s1);
-gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
 var = create_tmp_reg (type, "predreastmp");
 tmp_name = make_ssa_name (var);
 /* Rhs of S1 may now be either a binary expression with operation
 bsi = gsi_for_stmt (s1);
 gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
 s1 = gsi_stmt (bsi);
 update_stmt (s1);
+gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
 gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
 return new_stmt;
 }
 /* Returns the statement that combines references R1 and R2.  In case R1
 and R2 are not used in the same statement, but they are used with an
 associative and commutative operation in the same expression, reassociate
-the expression so that they are used in the same statement.  The combined
+the expression so that they are used in the same statement.  */
-statement is inserted before INSERT_BEFORE if it's not NULL.  */
 static gimple *
-stmt_combining_refs (dref r1, dref r2, gimple *insert_before)
+stmt_combining_refs (dref r1, dref r2)
 {
 gimple *stmt1, *stmt2;
 tree name1 = name_for_ref (r1);
 tree name2 = name_for_ref (r2);
 stmt1 = find_use_stmt (&name1);
 stmt2 = find_use_stmt (&name2);
 if (stmt1 == stmt2)
 return stmt1;
-return reassociate_to_the_same_stmt (name1, name2, insert_before);
+return reassociate_to_the_same_stmt (name1, name2);
 }
 /* Tries to combine chains CH1 and CH2 together.  If this succeeds, the
 description of the new chain is returned, otherwise we return NULL.  */
 {
 dref r1, r2, nw;
 enum tree_code op = ERROR_MARK;
 bool swap = false;
 chain_p new_chain;
-int i, j, num;
+unsigned i;
-gimple *root_stmt;
 tree rslt_type = NULL_TREE;
 if (ch1 == ch2)
 return NULL;
 if (ch1->length != ch2->length)
 	return NULL;
 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
 	return NULL;
 }
-ch1->combined = true;
-ch2->combined = true;
 if (swap)
 std::swap (ch1, ch2);
 new_chain = XCNEW (struct chain);
 new_chain->ch1 = ch1;
 new_chain->ch2 = ch2;
 new_chain->rslt_type = rslt_type;
 new_chain->length = ch1->length;
-gimple *insert = NULL;
+for (i = 0; (ch1->refs.iterate (i, &r1)
-num = ch1->refs.length ();
+	       && ch2->refs.iterate (i, &r2)); i++)
-i = (new_chain->length == 0) ? num - 1 : 0;
+{
-j = (new_chain->length == 0) ? -1 : 1;
-/* For ZERO length chain, process refs in reverse order so that dominant
-position is ready when it comes to the root ref.
-For non-ZERO length chain, process refs in order.  See PR79663.  */
-for (; num > 0; num--, i += j)
-{
-r1 = ch1->refs[i];
-r2 = ch2->refs[i];
 nw = XCNEW (struct dref_d);
+nw->stmt = stmt_combining_refs (r1, r2);
 nw->distance = r1->distance;
-/* For ZERO length chain, insert combined stmt of root ref at dominant
-	 position.  */
-nw->stmt = stmt_combining_refs (r1, r2, i == 0 ? insert : NULL);
-/* For ZERO length chain, record dominant position where combined stmt
-	 of root ref should be inserted.  In this case, though all root refs
-	 dominate following ones, it's possible that combined stmt doesn't.
-	 See PR70754.  */
-if (new_chain->length == 0
-	  && (insert == NULL || stmt_dominates_stmt_p (nw->stmt, insert)))
-	insert = nw->stmt;
 new_chain->refs.safe_push (nw);
 }
-if (new_chain->length == 0)
-{
+ch1->combined = true;
-/* Restore the order for ZERO length chain's refs.  */
+ch2->combined = true;
-num = new_chain->refs.length () >> 1;
-for (i = 0, j = new_chain->refs.length () - 1; i < num; i++, j--)
-	std::swap (new_chain->refs[i], new_chain->refs[j]);
-/* For ZERO length chain, has_max_use_after must be true since root
-	 combined stmt must dominates others.  */
-new_chain->has_max_use_after = true;
-return new_chain;
-}
-new_chain->has_max_use_after = false;
-root_stmt = get_chain_root (new_chain)->stmt;
-for (i = 1; new_chain->refs.iterate (i, &nw); i++)
-{
-if (nw->distance == new_chain->length
-	  && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
-	{
-	  new_chain->has_max_use_after = true;
-	  break;
-	}
-}
 return new_chain;
 }
-/* Try to combine the CHAINS.  */
+/* Recursively update position information of all offspring chains to ROOT
+chain's position information.  */
 static void
-try_combine_chains (vec<chain_p> *chains)
+update_pos_for_combined_chains (chain_p root)
+{
+chain_p ch1 = root->ch1, ch2 = root->ch2;
+dref ref, ref1, ref2;
+for (unsigned j = 0; (root->refs.iterate (j, &ref)
+			&& ch1->refs.iterate (j, &ref1)
+			&& ch2->refs.iterate (j, &ref2)); ++j)
+ref1->pos = ref2->pos = ref->pos;
+if (ch1->type == CT_COMBINATION)
+update_pos_for_combined_chains (ch1);
+if (ch2->type == CT_COMBINATION)
+update_pos_for_combined_chains (ch2);
+}
+/* Returns true if statement S1 dominates statement S2.  */
+static bool
+pcom_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
+{
+basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+if (!bb1 || s1 == s2)
+return true;
+if (bb1 == bb2)
+return gimple_uid (s1) < gimple_uid (s2);
+return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
+}
+/* Try to combine the CHAINS in LOOP.  */
+static void
+try_combine_chains (struct loop *loop, vec<chain_p> *chains)
 {
 unsigned i, j;
 chain_p ch1, ch2, cch;
 auto_vec<chain_p> worklist;
+bool combined_p = false;
 FOR_EACH_VEC_ELT (*chains, i, ch1)
 if (chain_can_be_combined_p (ch1))
 worklist.safe_push (ch1);
 	  cch = combine_chains (ch1, ch2);
 	  if (cch)
 	    {
 	      worklist.safe_push (cch);
 	      chains->safe_push (cch);
+	      combined_p = true;
+	      break;
+	    }
+	}
+}
+if (!combined_p)
+return;
+/* Setup UID for all statements in dominance order.  */
+basic_block *bbs = get_loop_body (loop);
+renumber_gimple_stmt_uids_in_blocks (bbs, loop->num_nodes);
+free (bbs);
+/* Re-association in combined chains may generate statements different to
+order of references of the original chain.  We need to keep references
+of combined chain in dominance order so that all uses will be inserted
+after definitions.  Note:
+A) This is necessary for all combined chains.
+B) This is only necessary for ZERO distance references because other
+	  references inherit value from loop carried PHIs.
+We first update position information for all combined chains.  */
+dref ref;
+for (i = 0; chains->iterate (i, &ch1); ++i)
+{
+if (ch1->type != CT_COMBINATION || ch1->combined)
+	continue;
+for (j = 0; ch1->refs.iterate (j, &ref); ++j)
+	ref->pos = gimple_uid (ref->stmt);
+update_pos_for_combined_chains (ch1);
+}
+/* Then sort references according to newly updated position information.  */
+for (i = 0; chains->iterate (i, &ch1); ++i)
+{
+if (ch1->type != CT_COMBINATION && !ch1->combined)
+	continue;
+/* Find the first reference with non-ZERO distance.  */
+if (ch1->length == 0)
+	j = ch1->refs.length();
+else
+	{
+	  for (j = 0; ch1->refs.iterate (j, &ref); ++j)
+	    if (ref->distance != 0)
+	      break;
+	}
+/* Sort all ZERO distance references by position.  */
+qsort (&ch1->refs[0], j, sizeof (ch1->refs[0]), order_drefs_by_pos);
+if (ch1->combined)
+	continue;
+/* For ZERO length chain, has_max_use_after must be true since root
+	 combined stmt must dominates others.  */
+if (ch1->length == 0)
+	{
+	  ch1->has_max_use_after = true;
+	  continue;
+	}
+/* Check if there is use at max distance after root for combined chains
+	 and set flag accordingly.  */
+ch1->has_max_use_after = false;
+gimple *root_stmt = get_chain_root (ch1)->stmt;
+for (j = 1; ch1->refs.iterate (j, &ref); ++j)
+	{
+	  if (ref->distance == ch1->length
+	      && !pcom_stmt_dominates_stmt_p (ref->stmt, root_stmt))
+	    {
+	      ch1->has_max_use_after = true;
 	      break;
 	    }
 	}
 }
 }
 }
 prepare_initializers (loop, chains);
 loop_closed_ssa = prepare_finalizers (loop, chains);
 /* Try to combine the chains that are always worked with together.  */
-try_combine_chains (&chains);
+try_combine_chains (loop, &chains);
 insert_init_seqs (loop, chains);
 if (dump_file && (dump_flags & TDF_DETAILS))
 {

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-predcom.c @ 132:d34655255c78