CbC/CbC_gcc: gcc/tree-loop-distribution.c comparison

comparison gcc/tree-loop-distribution.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
 /* Loop distribution.
-Copyright (C) 2006-2017 Free Software Foundation, Inc.
+Copyright (C) 2006-2018 Free Software Foundation, Inc.
 Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
 and Sebastian Pop <sebastian.pop@amd.com>.
 This file is part of GCC.
 2) We only fuse partitions in SCC now.  A better fusion algorithm is
 	desired to minimize loop overhead, maximize parallelism and maximize
 	data reuse.  */
 #include "config.h"
-#define INCLUDE_ALGORITHM /* stable_sort */
 #include "system.h"
 #include "coretypes.h"
 #include "backend.h"
 #include "tree.h"
 #include "gimple.h"
 }
 /* Kind of distributed loop.  */
 enum partition_kind {
-PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
+PKIND_NORMAL,
+/* Partial memset stands for a paritition can be distributed into a loop
+of memset calls, rather than a single memset call.  It's handled just
+like a normal parition, i.e, distributed as separate loop, no memset
+call is generated.
+Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
+loop nest as deep as possible.  As a result, parloop achieves better
+parallelization by parallelizing deeper loop nest.  This hack should
+be unnecessary and removed once distributed memset can be understood
+and analyzed in data reference analysis.  See PR82604 for more.  */
+PKIND_PARTIAL_MEMSET,
+PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
 };
 /* Type of distributed loop.  */
 enum partition_type {
 /* The distributed loop can be executed parallelly.  */
 /* Returns true if the partition can be generated as a builtin.  */
 static bool
 partition_builtin_p (partition *partition)
 {
-return partition->kind != PKIND_NORMAL;
+return partition->kind > PKIND_PARTIAL_MEMSET;
 }
 /* Returns true if the partition contains a reduction.  */
 static bool
 }
 /* Remove stmts not in the PARTITION bitmap.  */
 bbs = get_loop_body_in_dom_order (loop);
-if (MAY_HAVE_DEBUG_STMTS)
+if (MAY_HAVE_DEBUG_BIND_STMTS)
 for (i = 0; i < loop->num_nodes; i++)
 {
 	basic_block bb = bbs[i];
 	for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
 	  if (!const_with_all_bytes_same (TREE_REALPART (val))
 	      && !const_with_all_bytes_same (TREE_IMAGPART (val)))
 	    return 0;
 	  break;
 	case VECTOR_CST:
-	  unsigned int j;
+	  {
-	  for (j = 0; j < VECTOR_CST_NELTS (val); ++j)
+	    unsigned int count = vector_cst_encoded_nelts (val);
-	    if (const_with_all_bytes_same (VECTOR_CST_ELT (val, j)))
+	    unsigned int j;
-	      break;
+	    for (j = 0; j < count; ++j)
-	  if (j == VECTOR_CST_NELTS (val))
+	      if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val, j)))
-	    return 0;
+		break;
-	  break;
+	    if (j == count)
+	      return 0;
+	    break;
+	  }
 	default:
 	  break;
 	}
 }
 			     partition *partition, bool copy_p)
 {
 switch (partition->kind)
 {
 case PKIND_NORMAL:
+case PKIND_PARTIAL_MEMSET:
 /* Reductions all have to be in the last partition.  */
 gcc_assert (!partition_reduction_p (partition)
 		  || !copy_p);
 generate_loops_for_partition (loop, partition, copy_p);
 return false;
 return true;
 }
 /* Given data reference DR in LOOP_NEST, this function checks the enclosing
 loops from inner to outer to see if loop's step equals to access size at
-each level of loop.  Return true if yes; record access base and size in
+each level of loop.  Return 2 if we can prove this at all level loops;
-BASE and SIZE; save loop's step at each level of loop in STEPS if it is
+record access base and size in BASE and SIZE; save loop's step at each
-not null.  For example:
+level of loop in STEPS if it is not null.  For example:
 int arr[100][100][100];
 for (i = 0; i < 100; i++)       ;steps[2] = 40000
 for (j = 100; j > 0; j--)     ;steps[1] = -400
 	 for (k = 0; k < 100; k++)   ;steps[0] = 4
-	   arr[i][j - 1][k] = 0;     ;base = &arr, size = 4000000.  */
+	   arr[i][j - 1][k] = 0;     ;base = &arr, size = 4000000
-static bool
+Return 1 if we can prove the equality at the innermost loop, but not all
+level loops.  In this case, no information is recorded.
+Return 0 if no equality can be proven at any level loops.  */
+static int
 compute_access_range (loop_p loop_nest, data_reference_p dr, tree *base,
 		      tree *size, vec<tree> *steps = NULL)
 {
 location_t loc = gimple_location (DR_STMT (dr));
 basic_block bb = gimple_bb (DR_STMT (dr));
 struct loop *loop = bb->loop_father;
 tree ref = DR_REF (dr);
 tree access_base = build_fold_addr_expr (ref);
 tree access_size = TYPE_SIZE_UNIT (TREE_TYPE (ref));
+int res = 0;
 do {
 tree scev_fn = analyze_scalar_evolution (loop, access_base);
 if (TREE_CODE (scev_fn) != POLYNOMIAL_CHREC)
-	return false;
+	return res;
 access_base = CHREC_LEFT (scev_fn);
 if (tree_contains_chrecs (access_base, NULL))
-	return false;
+	return res;
 tree scev_step = CHREC_RIGHT (scev_fn);
 /* Only support constant steps.  */
 if (TREE_CODE (scev_step) != INTEGER_CST)
-	return false;
+	return res;
 enum ev_direction access_dir = scev_direction (scev_fn);
 if (access_dir == EV_DIR_UNKNOWN)
-	return false;
+	return res;
 if (steps != NULL)
 	steps->safe_push (scev_step);
 scev_step = fold_convert_loc (loc, sizetype, scev_step);
 	scev_step = fold_build1_loc (loc, NEGATE_EXPR, sizetype, scev_step);
 /* At each level of loop, scev step must equal to access size.  In other
 	 words, DR must access consecutive memory between loop iterations.  */
 if (!operand_equal_p (scev_step, access_size, 0))
-	return false;
+	return res;
+/* Access stride can be computed for data reference at least for the
+	 innermost loop.  */
+res = 1;
 /* Compute DR's execution times in loop.  */
 tree niters = number_of_latch_executions (loop);
 niters = fold_convert_loc (loc, sizetype, niters);
 if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, bb))
 	}
 } while (loop != loop_nest && (loop = loop_outer (loop)) != NULL);
 *base = access_base;
 *size = access_size;
-return true;
+/* Access stride can be computed for data reference at each level loop.  */
+return 2;
 }
 /* Allocate and return builtin struct.  Record information like DST_DR,
 SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct.  */
 if (TREE_CODE (rhs) == SSA_NAME
 && !SSA_NAME_IS_DEFAULT_DEF (rhs)
 && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs))))
 return;
-if (!compute_access_range (loop, dr, &base, &size))
+int res = compute_access_range (loop, dr, &base, &size);
+if (res == 0)
+return;
+if (res == 1)
+{
+partition->kind = PKIND_PARTIAL_MEMSET;
+return;
+}
+poly_uint64 base_offset;
+unsigned HOST_WIDE_INT const_base_offset;
+tree base_base = strip_offset (base, &base_offset);
+if (!base_offset.is_constant (&const_base_offset))
 return;
 struct builtin_info *builtin;
 builtin = alloc_builtin (dr, NULL, base, NULL_TREE, size);
-builtin->dst_base_base = strip_offset (builtin->dst_base,
+builtin->dst_base_base = base_base;
-					 &builtin->dst_base_offset);
+builtin->dst_base_offset = const_base_offset;
 partition->builtin = builtin;
 partition->kind = PKIND_MEMSET;
 }
 /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
 		       data_reference_p dst_dr, data_reference_p src_dr)
 {
 tree base, size, src_base, src_size;
 auto_vec<tree> dst_steps, src_steps;
-/* Compute access range of both load and store.  They much have the same
+/* Compute access range of both load and store.  */
-access size.  */
+int res = compute_access_range (loop, dst_dr, &base, &size, &dst_steps);
-if (!compute_access_range (loop, dst_dr, &base, &size, &dst_steps)
+if (res != 2)
-|| !compute_access_range (loop, src_dr, &src_base, &src_size, &src_steps)
+return;
-|| !operand_equal_p (size, src_size, 0))
+res = compute_access_range (loop, src_dr, &src_base, &src_size, &src_steps);
+if (res != 2)
+return;
+/* They much have the same access size.  */
+if (!operand_equal_p (size, src_size, 0))
 return;
 /* Load and store in loop nest must access memory in the same way, i.e,
 their must have the same steps in each loop of the nest.  */
 if (dst_steps.length () != src_steps.length ())
 	      /* Known dependences can still be unordered througout the
 		 iteration space, see gcc.dg/tree-ssa/ldist-16.c.  */
 	      if (DDR_NUM_DIST_VECTS (ddr) != 1)
 		this_dir = 2;
 	      /* If the overlap is exact preserve stmt order.  */
-	      else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1))
+	      else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0),
+					    DDR_NB_LOOPS (ddr)))
 		;
 	      /* Else as the distance vector is lexicographic positive swap
 		 the dependence direction.  */
 	      else
 		this_dir = -this_dir;
 for (i = 0; i < num_sccs; ++i)
 	{
 	  for (j = 0; partitions->iterate (j, &first); ++j)
 	    if (pg->vertices[j].component == i)
 	      break;
+	  bool same_type = true, all_builtins = partition_builtin_p (first);
 	  for (++j; partitions->iterate (j, &partition); ++j)
 	    {
 	      if (pg->vertices[j].component != i)
 		continue;
-	      /* Note we Merge partitions of parallel type on purpose, though
-		 the result partition is sequential.  The reason is vectorizer
-		 can do more accurate runtime alias check in this case.  Also
-		 it results in more conservative distribution.  */
 	      if (first->type != partition->type)
 		{
-		  bitmap_clear_bit (sccs_to_merge, i);
+		  same_type = false;
 		  break;
 		}
+	      all_builtins &= partition_builtin_p (partition);
 	    }
+	  /* Merge SCC if all partitions in SCC have the same type, though the
+	     result partition is sequential, because vectorizer can do better
+	     runtime alias check.  One expecption is all partitions in SCC are
+	     builtins.  */
+	  if (!same_type || all_builtins)
+	    bitmap_clear_bit (sccs_to_merge, i);
 	}
 /* Initialize callback data for traversing.  */
 cbdata.sccs_to_merge = sccs_to_merge;
 cbdata.alias_ddrs = alias_ddrs;
 will be accessed by DR in NITERS iterations.  */
 static tree
 data_ref_segment_size (struct data_reference *dr, tree niters)
 {
-tree segment_length;
+niters = size_binop (MINUS_EXPR,
+		       fold_convert (sizetype, niters),
-if (integer_zerop (DR_STEP (dr)))
+		       size_one_node);
-segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
+return size_binop (MULT_EXPR,
-else
+		     fold_convert (sizetype, DR_STEP (dr)),
-segment_length = size_binop (MULT_EXPR,
+		     fold_convert (sizetype, niters));
-				 fold_convert (sizetype, DR_STEP (dr)),
-				 fold_convert (sizetype, niters));
-return segment_length;
 }
 /* Return true if LOOP's latch is dominated by statement for data reference
 DR.  */
 if (latch_dominated_by_data_ref (loop, dr_b))
 	seg_length_b = data_ref_segment_size (dr_b, niters_plus_one);
 else
 	seg_length_b = data_ref_segment_size (dr_b, niters);
+unsigned HOST_WIDE_INT access_size_a
+	= tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a))));
+unsigned HOST_WIDE_INT access_size_b
+	= tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b))));
+unsigned int align_a = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a)));
+unsigned int align_b = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b)));
 dr_with_seg_len_pair_t dr_with_seg_len_pair
-	  (dr_with_seg_len (dr_a, seg_length_a),
+	(dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a),
-	   dr_with_seg_len (dr_b, seg_length_b));
+	 dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b));
 /* Canonicalize pairs by sorting the two DR members.  */
 if (comp_res > 0)
 	std::swap (dr_with_seg_len_pair.first, dr_with_seg_len_pair.second);
 /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
 checks and version LOOP under condition of these runtime alias checks.  */
 static void
-version_loop_by_alias_check (struct loop *loop, vec<ddr_p> *alias_ddrs)
+version_loop_by_alias_check (vec<struct partition *> *partitions,
+			     struct loop *loop, vec<ddr_p> *alias_ddrs)
 {
 profile_probability prob;
 basic_block cond_bb;
 struct loop *nloop;
 tree lhs, arg0, cond_expr = NULL_TREE;
 create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr);
 cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts,
 				      is_gimple_val, NULL_TREE);
 /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS.  */
-if (flag_tree_loop_vectorize)
+bool cancelable_p = flag_tree_loop_vectorize;
-{
+if (cancelable_p)
-/* Generate internal function call for loop distribution alias check.  */
+{
+unsigned i = 0;
+struct partition *partition;
+for (; partitions->iterate (i, &partition); ++i)
+	if (!partition_builtin_p (partition))
+	  break;
+/* If all partitions are builtins, distributing it would be profitable and
+	we don't want to cancel the runtime alias checks.  */
+if (i == partitions->length ())
+	cancelable_p = false;
+}
+/* Generate internal function call for loop distribution alias check if the
+runtime alias check should be cancelable.  */
+if (cancelable_p)
+{
 call_stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS,
 					      2, NULL_TREE, cond_expr);
 lhs = make_ssa_name (boolean_type_node);
 gimple_call_set_lhs (call_stmt, lhs);
 }
 return (alias_ddrs->length () > 0);
 }
 /* Compare base offset of builtin mem* partitions P1 and P2.  */
-static bool
+static int
-offset_cmp (struct partition *p1, struct partition *p2)
+offset_cmp (const void *vp1, const void *vp2)
 {
-gcc_assert (p1 != NULL && p1->builtin != NULL);
+struct partition *p1 = *(struct partition *const *) vp1;
-gcc_assert (p2 != NULL && p2->builtin != NULL);
+struct partition *p2 = *(struct partition *const *) vp2;
-return p1->builtin->dst_base_offset < p2->builtin->dst_base_offset;
+unsigned HOST_WIDE_INT o1 = p1->builtin->dst_base_offset;
+unsigned HOST_WIDE_INT o2 = p2->builtin->dst_base_offset;
+return (o2 < o1) - (o1 < o2);
 }
 /* Fuse adjacent memset builtin PARTITIONS if possible.  This is a special
 case optimization transforming below code:
 static void
 fuse_memset_builtins (vec<struct partition *> *partitions)
 {
 unsigned i, j;
 struct partition *part1, *part2;
+tree rhs1, rhs2;
 for (i = 0; partitions->iterate (i, &part1);)
 {
 if (part1->kind != PKIND_MEMSET)
 	{
 	{
 	  if (part2->kind != PKIND_MEMSET
 	      || !operand_equal_p (part1->builtin->dst_base_base,
 				   part2->builtin->dst_base_base, 0))
 	    break;
+	  /* Memset calls setting different values can't be merged.  */
+	  rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
+	  rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
+	  if (!operand_equal_p (rhs1, rhs2, 0))
+	    break;
 	}
 /* Stable sort is required in order to avoid breaking dependence.  */
-std::stable_sort (&(*partitions)[i],
+gcc_stablesort (&(*partitions)[i], j - i, sizeof (*partitions)[i],
-			&(*partitions)[i] + j - i, offset_cmp);
+		      offset_cmp);
 /* Continue with next partition.  */
 i = j;
 }
 /* Merge all consecutive memset builtin partitions.  */
 			       part2->builtin->dst_base_base, 0))
 	{
 	  i++;
 	  continue;
 	}
-tree rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
+rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
-tree rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
+rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
 int bytev1 = const_with_all_bytes_same (rhs1);
 int bytev2 = const_with_all_bytes_same (rhs2);
 /* Only merge memset partitions of the same value.  */
 if (bytev1 != bytev2 || bytev1 == -1)
 	{
 if (partitions->length () == 1
 || alias_ddrs->length () > 0)
 return;
-unsigned num_builtin = 0, num_normal = 0;
+unsigned num_builtin = 0, num_normal = 0, num_partial_memset = 0;
 bool same_type_p = true;
 enum partition_type type = ((*partitions)[0])->type;
 for (i = 0; partitions->iterate (i, &partition); ++i)
 {
 same_type_p &= (type == partition->type);
-if (partition->kind != PKIND_NORMAL)
+if (partition_builtin_p (partition))
-	num_builtin++;
+	{
-else
+	  num_builtin++;
-	num_normal++;
+	  continue;
+	}
+num_normal++;
+if (partition->kind == PKIND_PARTIAL_MEMSET)
+	num_partial_memset++;
 }
 /* Don't distribute current loop into too many loops given we don't have
 memory stream cost model.  Be even more conservative in case of loop
 nest distribution.  */
-if ((same_type_p && num_builtin == 0)
+if ((same_type_p && num_builtin == 0
+&& (loop->inner == NULL || num_normal != 2 || num_partial_memset != 1))
 || (loop->inner != NULL
 	  && i >= NUM_PARTITION_THRESHOLD && num_normal > 1)
 || (loop->inner == NULL
 	  && i >= NUM_PARTITION_THRESHOLD && num_normal > num_builtin))
 {
 /* Apply our simple cost model - fuse partitions with similar
 memory accesses.  */
 for (i = 0; partitions.iterate (i, &into); ++i)
 {
 bool changed = false;
-if (partition_builtin_p (into))
+if (partition_builtin_p (into) || into->kind == PKIND_PARTIAL_MEMSET)
 	continue;
 for (int j = i + 1;
 	   partitions.iterate (j, &partition); ++j)
 	{
 	  if (share_memory_accesses (rdg, into, partition))
 nbp = 0;
 goto ldist_done;
 }
 if (version_for_distribution_p (&partitions, &alias_ddrs))
-version_loop_by_alias_check (loop, &alias_ddrs);
+version_loop_by_alias_check (&partitions, loop, &alias_ddrs);
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 fprintf (dump_file,
 	       "distribute loop <%d> into partitions:\n", loop->num);
 prepare_perfect_loop_nest (struct loop *loop)
 {
 struct loop *outer = loop_outer (loop);
 tree niters = number_of_latch_executions (loop);
-/* TODO: We only support the innermost 2-level loop nest distribution
+/* TODO: We only support the innermost 3-level loop nest distribution
 because of compilation time issue for now.  This should be relaxed
-in the future.  */
+in the future.  Note we only allow 3-level loop nest distribution
-while (loop->inner == NULL
+when parallelizing loops.  */
+while ((loop->inner == NULL
+	  || (loop->inner->inner == NULL && flag_tree_parallelize_loops > 1))
 	 && loop_outer (outer)
 	 && outer->inner == loop && loop->next == NULL
 	 && single_exit (outer)
 	 && optimize_loop_for_speed_p (outer)
 	 && !chrec_contains_symbols_defined_in_loop (niters, outer->num)
 	  auto_vec<gimple *> work_list;
 	  if (!find_seed_stmts_for_distribution (loop, &work_list))
 	    break;
 	  const char *str = loop->inner ? " nest" : "";
-	  location_t loc = find_loop_location (loop);
+	  dump_user_location_t loc = find_loop_location (loop);
 	  if (!cd)
 	    {
 	      calculate_dominance_info (CDI_DOMINATORS);
 	      calculate_dominance_info (CDI_POST_DOMINATORS);
 	      cd = new control_dependences ();
 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 }
 checking_verify_loop_structure ();
-return 0;
+return changed ? TODO_cleanup_cfg : 0;
 }
 } // anon namespace
 gimple_opt_pass *

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-loop-distribution.c @ 132:d34655255c78