CbC/CbC_gcc: gcc/graphite-scop-detection.c comparison

comparison gcc/graphite-scop-detection.c @ 131:84e7813d76e9

gcc-8.2

author	mir3636
date	Thu, 25 Oct 2018 07:37:49 +0900
parents	04ced10e8804
children	1830386684a0

comparison

equal deleted inserted replaced

-:04ced10e8804
+:84e7813d76e9
 /* Detection of Static Control Parts (SCoP) for Graphite.
-Copyright (C) 2009-2017 Free Software Foundation, Inc.
+Copyright (C) 2009-2018 Free Software Foundation, Inc.
 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
 Tobias Grosser <grosser@fim.uni-passau.de>.
 This file is part of GCC.
 } dp;
 #define DEBUG_PRINT(args) do \
 {								\
 if (dump_file && (dump_flags & TDF_DETAILS)) { args; }	\
-} while (0);
+} while (0)
 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
 different colors.  If there are not enough colors, paint the
 remaining SCoPs in gray.
 /* Return an sese_l around the LOOP.  */
 sese_l get_sese (loop_p loop);
-/* Return the closest dominator with a single entry edge.  In case of a
-back-loop the back-edge is not counted.  */
-static edge get_nearest_dom_with_single_entry (basic_block dom);
-/* Return the closest post-dominator with a single exit edge.  In case of a
-back-loop the back-edge is not counted.  */
-static edge get_nearest_pdom_with_single_exit (basic_block dom);
 /* Merge scops at same loop depth and returns the new sese.
 Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
 sese_l merge_sese (sese_l first, sese_l second) const;
 if (!loop)
 return invalid_sese;
 edge scop_begin = loop_preheader_edge (loop);
 edge scop_end = single_exit (loop);
-if (!scop_end || (scop_end->flags & EDGE_COMPLEX))
+if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
 return invalid_sese;
-/* Include the BB with the loop-closed SSA PHI nodes.
-canonicalize_loop_closed_ssa makes sure that is in proper shape.  */
-if (! single_pred_p (scop_end->dest)
-|| ! single_succ_p (scop_end->dest)
-|| ! sese_trivially_empty_bb_p (scop_end->dest))
-gcc_unreachable ();
-scop_end = single_succ_edge (scop_end->dest);
 return sese_l (scop_begin, scop_end);
-}
-/* Return the closest dominator with a single entry edge.  */
-edge
-scop_detection::get_nearest_dom_with_single_entry (basic_block dom)
-{
-if (!dom->preds)
-return NULL;
-/* If any of the dominators has two predecessors but one of them is a back
-edge, then that basic block also qualifies as a dominator with single
-entry.  */
-if (dom->preds->length () == 2)
-{
-/* If e1->src dominates e2->src then e1->src will also dominate dom.  */
-edge e1 = (*dom->preds)[0];
-edge e2 = (*dom->preds)[1];
-loop_p l = dom->loop_father;
-loop_p l1 = e1->src->loop_father;
-loop_p l2 = e2->src->loop_father;
-if (l != l1 && l == l2
-	  && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
-	return e1;
-if (l != l2 && l == l1
-	  && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src))
-	return e2;
-}
-while (dom->preds->length () != 1)
-{
-if (dom->preds->length () < 1)
-	return NULL;
-dom = get_immediate_dominator (CDI_DOMINATORS, dom);
-if (!dom->preds)
-	return NULL;
-}
-return (*dom->preds)[0];
-}
-/* Return the closest post-dominator with a single exit edge.  In case of a
-back-loop the back-edge is not counted.  */
-edge
-scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom)
-{
-if (!pdom->succs)
-return NULL;
-/* If any of the post-dominators has two successors but one of them is a back
-edge, then that basic block also qualifies as a post-dominator with single
-exit. */
-if (pdom->succs->length () == 2)
-{
-/* If e1->dest post-dominates e2->dest then e1->dest will also
-	 post-dominate pdom.  */
-edge e1 = (*pdom->succs)[0];
-edge e2 = (*pdom->succs)[1];
-loop_p l = pdom->loop_father;
-loop_p l1 = e1->dest->loop_father;
-loop_p l2 = e2->dest->loop_father;
-if (l != l1 && l == l2
-	  && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
-	return e1;
-if (l != l2 && l == l1
-	  && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
-	return e2;
-}
-while (pdom->succs->length () != 1)
-{
-if (pdom->succs->length () < 1)
-	return NULL;
-pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom);
-if (!pdom->succs)
-	return NULL;
-}
-return (*pdom->succs)[0];
 }
 /* Merge scops at same loop depth and returns the new sese.
 Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
 DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
 	       print_sese (dump_file, first);
 	       dp << "[scop-detection] try merging sese s2: ";
 	       print_sese (dump_file, second));
-/* Assumption: Both the sese's should be at the same loop depth or one scop
+auto_bitmap worklist, in_sese_region;
-should subsume the other like in case of nested loops.  */
+bitmap_set_bit (worklist, get_entry_bb (first)->index);
+bitmap_set_bit (worklist, get_exit_bb (first)->index);
-/* Find the common dominators for entry,
+bitmap_set_bit (worklist, get_entry_bb (second)->index);
-and common post-dominators for the exit.  */
+bitmap_set_bit (worklist, get_exit_bb (second)->index);
-basic_block dom = nearest_common_dominator (CDI_DOMINATORS,
+edge entry = NULL, exit = NULL;
-					      get_entry_bb (first),
-					      get_entry_bb (second));
+/* We can optimize the case of adding a loop entry dest or exit
+src to the worklist (for single-exit loops) by skipping
-edge entry = get_nearest_dom_with_single_entry (dom);
+directly to the exit dest / entry src.  in_sese_region
+doesn't have to cover all blocks in the region but merely
-if (!entry || (entry->flags & EDGE_IRREDUCIBLE_LOOP))
+its border it acts more like a visited bitmap.  */
-return invalid_sese;
+do
+{
-basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS,
+int index = bitmap_first_set_bit (worklist);
-					       get_exit_bb (first),
+bitmap_clear_bit (worklist, index);
-					       get_exit_bb (second));
+basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
-pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom);
+edge_iterator ei;
+edge e;
-edge exit = get_nearest_pdom_with_single_exit (pdom);
+/* With fake exit edges we can end up with no possible exit.  */
-if (!exit || (exit->flags & EDGE_IRREDUCIBLE_LOOP))
+if (index == EXIT_BLOCK)
-return invalid_sese;
+	{
+	  DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
+	  return invalid_sese;
+	}
+bitmap_set_bit (in_sese_region, bb->index);
+basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
+FOR_EACH_EDGE (e, ei, bb->preds)
+	if (e->src == dom
+	    && (! entry
+		|| dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
+	  {
+	    if (entry
+		&& ! bitmap_bit_p (in_sese_region, entry->src->index))
+	      bitmap_set_bit (worklist, entry->src->index);
+	    entry = e;
+	  }
+	else if (! bitmap_bit_p (in_sese_region, e->src->index))
+	  bitmap_set_bit (worklist, e->src->index);
+basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
+FOR_EACH_EDGE (e, ei, bb->succs)
+	if (e->dest == pdom
+	    && (! exit
+		|| dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
+	  {
+	    if (exit
+		&& ! bitmap_bit_p (in_sese_region, exit->dest->index))
+	      bitmap_set_bit (worklist, exit->dest->index);
+	    exit = e;
+	  }
+	else if (! bitmap_bit_p (in_sese_region, e->dest->index))
+	  bitmap_set_bit (worklist, e->dest->index);
+}
+while (! bitmap_empty_p (worklist));
 sese_l combined (entry, exit);
-DEBUG_PRINT (dp << "[scop-detection] checking combined sese: ";
-	       print_sese (dump_file, combined));
-/* FIXME: We could iterate to find the dom which dominates pdom, and pdom
-which post-dominates dom, until it stabilizes.  Also, ENTRY->SRC and
-EXIT->DEST should be in the same loop nest.  */
-if (!dominated_by_p (CDI_DOMINATORS, pdom, dom)
-|| loop_depth (entry->src->loop_father)
-	 != loop_depth (exit->dest->loop_father))
-return invalid_sese;
-/* For now we just bail out when there is a loop exit in the region
-that is not also the exit of the region.  We could enlarge the
-region to cover the loop that region exits to.  See PR79977.  */
-if (loop_outer (entry->src->loop_father))
-{
-vec<edge> exits = get_loop_exit_edges (entry->src->loop_father);
-for (unsigned i = 0; i < exits.length (); ++i)
-	{
-	  if (exits[i] != exit
-	      && bb_in_region (exits[i]->src, entry->dest, exit->src))
-	    {
-	      DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
-	      exits.release ();
-	      return invalid_sese;
-	    }
-	}
-exits.release ();
-}
-/* For now we just want to bail out when exit does not post-dominate entry.
-TODO: We might just add a basic_block at the exit to make exit
-post-dominate entry (the entire region).  */
-if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
-		       get_exit_bb (combined))
-|| !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
-			  get_entry_bb (combined)))
-{
-DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
-return invalid_sese;
-}
 DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
 return combined;
 }
 void
 scop_detection::add_scop (sese_l s)
 {
 gcc_assert (s);
+/* If the exit edge is fake discard the SCoP for now as we're removing the
+fake edges again after analysis.  */
+if (s.exit->flags & EDGE_FAKE)
+{
+DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
+		   print_sese (dump_file, s));
+return;
+}
+/* Include the BB with the loop-closed SSA PHI nodes, we need this
+block in the region for code-generating out-of-SSA copies.
+canonicalize_loop_closed_ssa makes sure that is in proper shape.  */
+if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
+&& loop_exit_edge_p (s.exit->src->loop_father, s.exit))
+{
+gcc_assert (single_pred_p (s.exit->dest)
+		  && single_succ_p (s.exit->dest)
+		  && sese_trivially_empty_bb_p (s.exit->dest));
+s.exit = single_succ_edge (s.exit->dest);
+}
 /* Do not add scops with only one loop.  */
 if (region_has_one_loop (s))
 {
 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
 		   print_sese (dump_file, s));
 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 	   !gsi_end_p (gsi); gsi_next (&gsi))
 	if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
 	  return true;
-if (bb != exit_bb)
+for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
-	for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
+	   dom;
-	     dom;
+	   dom = next_dom_son (CDI_DOMINATORS, dom))
-	     dom = next_dom_son (CDI_DOMINATORS, dom))
+	if (dom != scop.exit->dest)
 	  worklist.safe_push (dom);
 }
 /* Go through all loops and check that they are still valid in the combined
 scop.  */
 We try to analyze the data references in a loop contained in the SCOP.  */
 bool
 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
 {
-edge nest = scop.entry;;
+edge nest = scop.entry;
 loop_p loop = loop_containing_stmt (stmt);
 if (!loop_in_sese_p (loop, scop))
 loop = NULL;
 auto_vec<data_reference_p> drs;
 	return true;
 }
 case GIMPLE_ASSIGN:
 case GIMPLE_CALL:
-return true;
+{
+	tree op, lhs = gimple_get_lhs (stmt);
+	ssa_op_iter i;
+	/* If we are not going to instantiate the stmt do not require
+	   its operands to be instantiatable at this point.  */
+	if (lhs
+	    && TREE_CODE (lhs) == SSA_NAME
+	    && scev_analyzable_p (lhs, scop))
+	  return true;
+	/* Verify that if we can analyze operands at their def site we
+	   also can represent them when analyzed at their uses.  */
+	FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
+	  if (scev_analyzable_p (op, scop)
+	      && chrec_contains_undetermined
+		   (scalar_evolution_in_region (scop, bb->loop_father, op)))
+	    {
+	      DEBUG_PRINT (dp << "[scop-detection-fail] "
+			   << "Graphite cannot code-gen stmt:\n";
+			   print_gimple_stmt (dump_file, stmt, 0,
+					      TDF_VOPS | TDF_MEMSYMS));
+	      return false;
+	    }
+	return true;
+}
 default:
 /* These nodes cut a new scope.  */
 DEBUG_PRINT (
 	  dp << "[scop-detection-fail] "
 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
 scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
 /* Find parameters in conditional statements.  */
 gimple *stmt;
-loop_p loop = GBB_BB (gbb)->loop_father;
 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
 {
+loop_p loop = gimple_bb (stmt)->loop_father;
 tree lhs = scalar_evolution_in_region (region->region, loop,
 					     gimple_cond_lhs (stmt));
 tree rhs = scalar_evolution_in_region (region->region, loop,
 					     gimple_cond_rhs (stmt));
+gcc_assert (!chrec_contains_undetermined (lhs)
+		  && !chrec_contains_undetermined (rhs));
 scan_tree_for_params (region, lhs);
 scan_tree_for_params (region, rhs);
 }
 }
 auto_vec<gimple *, 3> conditions, cases;
 scop_p scop;
 };
 }
 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
-: dom_walker (direction, false, bb_to_rpo), scop (scop)
+: dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
 {
 }
 /* Call-back for dom_walk executed before visiting the dominated
 blocks.  */
 						 loop, nb_iters);
 	  scan_tree_for_params (region, nb_iters);
 	}
 }
-gcond *stmt = single_pred_cond_non_loop_exit (bb);
+if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
-if (stmt)
 {
 edge e = single_pred_edge (bb);
+/* Make sure the condition is in the region and thus was verified
-conditions.safe_push (stmt);
+to be handled.  */
+if (e != region->region.entry)
-if (e->flags & EDGE_TRUE_VALUE)
+	{
-	cases.safe_push (stmt);
+	  conditions.safe_push (stmt);
-else
+	  if (e->flags & EDGE_TRUE_VALUE)
-	cases.safe_push (NULL);
+	    cases.safe_push (stmt);
+	  else
+	    cases.safe_push (NULL);
+	}
 }
 scop->scop_info->bbs.safe_push (bb);
 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
 if (!bb_in_sese_p (bb, scop->scop_info->region))
 return;
 if (single_pred_cond_non_loop_exit (bb))
 {
-conditions.pop ();
+edge e = single_pred_edge (bb);
-cases.pop ();
+if (e != scop->scop_info->region.entry)
+	{
+	  conditions.pop ();
+	  cases.pop ();
+	}
 }
 }
 /* Compute sth like an execution order, dominator order with first executing
 edges that stay inside the current loop, delaying processing exit edges.  */
-static vec<unsigned> order;
+static int *bb_to_rpo;
-static void
-get_order (scop_p scop, basic_block bb, vec<unsigned> *order, unsigned *dfs_num)
-{
-if (! bb_in_sese_p (bb, scop->scop_info->region))
-return;
-(*order)[bb->index] = (*dfs_num)++;
-for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
-son;
-son = next_dom_son (CDI_DOMINATORS, son))
-if (flow_bb_inside_loop_p (bb->loop_father, son))
-get_order (scop, son, order, dfs_num);
-for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
-son;
-son = next_dom_son (CDI_DOMINATORS, son))
-if (! flow_bb_inside_loop_p (bb->loop_father, son))
-get_order (scop, son, order, dfs_num);
-}
 /* Helper for qsort, sorting after order above.  */
 static int
 cmp_pbbs (const void *pa, const void *pb)
 {
 poly_bb_p bb1 = *((const poly_bb_p *)pa);
 poly_bb_p bb2 = *((const poly_bb_p *)pb);
-if (order[bb1->black_box->bb->index] < order[bb2->black_box->bb->index])
+if (bb_to_rpo[bb1->black_box->bb->index]
+< bb_to_rpo[bb2->black_box->bb->index])
 return -1;
-else if (order[bb1->black_box->bb->index] > order[bb2->black_box->bb->index])
+else if (bb_to_rpo[bb1->black_box->bb->index]
+	   > bb_to_rpo[bb2->black_box->bb->index])
 return 1;
 else
 return 0;
 }
 vec<sese_l> scops_l = sb.get_scops ();
 /* Domwalk needs a bb to RPO mapping.  Compute it once here.  */
 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
-int *bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
+bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
 for (int i = 0; i < postorder_num; ++i)
 bb_to_rpo[postorder[i]] = i;
 free (postorder);
 int i;
 scop_p scop = new_scop (s->entry, s->exit);
 /* Record all basic blocks and their conditions in REGION.  */
 gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
-/* domwalk does not fulfil our code-generations constraints on the
+/* Sort pbbs after execution order for initial schedule generation.  */
-order of pbb which is to produce sth like execution order, delaying
-	 exection of loop exit edges.  So compute such order and sort after
-	 that.  */
-order.create (last_basic_block_for_fn (cfun));
-order.quick_grow (last_basic_block_for_fn (cfun));
-unsigned dfs_num = 0;
-get_order (scop, s->entry->dest, &order, &dfs_num);
 scop->pbbs.qsort (cmp_pbbs);
-order.release ();
 if (! build_alias_set (scop))
 	{
 	  DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
 	  free_scop (scop);
 scops->safe_push (scop);
 }
 free (bb_to_rpo);
+bb_to_rpo = NULL;
 DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
 }
 #endif /* HAVE_isl */

Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-scop-detection.c @ 131:84e7813d76e9