gcc/gcc/tree-parloops.c

62 #include "tree-ssa-loop-ivopts.h"
63 #include "tree-ssa-loop-manip.h"
64 #include "tree-ssa-loop-niter.h"
65 #include "tree-ssa-loop.h"
83    The implementation is straightforward -- for each loop we test whether its
91    -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
92       variable and that the exit test is at the start of the loop body
95       by storing the values incoming to the parallelized loop to a structure
103       ensure that cross-loop dependences are obeyed).
203 /* Minimal number of iterations of a loop that should be executed in each
208    reduction in the current loop.  */
217 				   of the reduction variable when existing the loop. */
218   tree initial_value;		/* The initial value of the reduction var before entering the loop.  */
358    matrix T is legal when applied to a loop nest with a set of
387      know that it is no worth looking at this loop nest: give up.  */
430 loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
439     fprintf (dump_file, "Considering loop %d\n", loop->num);
440     if (!loop->inner)
441       fprintf (dump_file, "loop is innermost\n");
443       fprintf (dump_file, "loop NOT innermost\n");
446   /* Check for problems with dependences.  If the loop can be reversed,
451   if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
486 loop_has_blocks_with_irreducible_flag (struct loop *loop)
489   basic_block *bbs = get_loop_body_in_dom_order (loop);
492   for (i = 0; i < loop->num_nodes; i++)
579    the loop described in DATA.  */
582 initialize_reductions (reduction_info **slot, struct loop *loop)
616   e = loop_preheader_edge (loop);
621 	   (reduc->reduc_phi, loop_preheader_edge (loop)), init);
683 	 loop.  */
1048 create_phi_for_local_result (reduction_info **slot, struct loop *loop)
1058      should be stored.  It is the destination of the loop exit.
1060   store_bb = FALLTHRU_EDGE (loop->latch)->dest;
1062   /* STORE_BB has two predecessors.  One coming from  the loop
1063      (the reduction's result is computed at the loop),
1064      and another coming from a block preceding the loop,
1067   if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
1076 	       FALLTHRU_EDGE (loop->latch), locus);
1149 create_call_for_reduction (struct loop *loop,
1153   reduction_list->traverse <struct loop *, create_phi_for_local_result> (loop);
1155   ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
1270    the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1295    pointer `new' is intentionally not initialized (the loop will be split to a
1351      possible (all of those that were dealt with in the loop above),
1379          loop carried and external variables in the loop).  */
1440    a parallelized loop.  */
1493    exit of the loop.  NIT is the number of iterations of the loop
1496    TODO: the common case is that latch of the loop is empty and immediately
1497    follows the loop exit.  In this case, it would be better not to copy the
1498    body of the loop, but only move the entry of the loop directly before the
1499    exit check and increase the number of iterations of the loop by one.
1504 transform_to_exit_first_loop (struct loop *loop,
1511   edge exit = single_dom_exit (loop), hpred;
1518   split_block_after_labels (loop->header);
1519   orig_header = single_succ (loop->header);
1520   hpred = single_succ_edge (loop->header);
1526   /* Make sure that we have phi nodes on exit for all loop header phis
1528   for (gphi_iterator gsi = gsi_start_phis (loop->header);
1547   bbs = get_loop_body_in_dom_order (loop);
1552   ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1560      out of the loop is the control variable.  */
1561   exit = single_dom_exit (loop);
1577          variable when exiting the loop.  */
1618 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1634   bb = loop_preheader_edge (loop)->src;
1663   bb = split_loop_exit_edge (single_dom_exit (loop));
1670   gcc_assert (loop->header == single_dom_exit (loop)->src);
1671   cond_stmt = as_a <gcond *> (last_stmt (loop->header));
1676   cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1678   SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1680   cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1682   gsi = gsi_last_nondebug_bb (loop->latch);
1687   for_bb = split_edge (loop_preheader_edge (loop));
1688   ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1689   extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1690   gcc_assert (exit == single_dom_exit (loop));
1693   single_succ_edge (loop->latch)->flags = 0;
1694   end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1706       def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
1708 						 loop_preheader_edge (loop));
1711       def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
1712       locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
1739   gsi = gsi_last_bb (loop->latch);
1765 gen_parallel_loop (struct loop *loop,
1782      loop
1802      store all local loop-invariant variables used in body of the loop to DATA.
1814      loop
1827   /* Create two versions of the loop -- in the old one, we know that the
1829      loop that will be split to loop_fn, the new one will be used for the
1846     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1848   if (loop->inner)
1864     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1871 	gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1876   /* We assume that the loop usually iterates a lot.  */
1878   loop_version (loop, many_iterations_cond, NULL,
1884   canonicalize_loop_ivs (loop, &nit, true);
1886   /* Ensure that the exit condition is the first statement in the loop.  */
1887   transform_to_exit_first_loop (loop, reduction_list, nit);
1891     reduction_list->traverse <struct loop *, initialize_reductions> (loop);
1893   /* Eliminate the references to local variables from the loop.  */
1894   gcc_assert (single_exit (loop));
1895   entry = loop_preheader_edge (loop);
1896   exit = single_dom_exit (loop);
1899   /* In the old loop, move all variables non-local to the loop to a structure
1900      and back, and create separate decls for the variables used in loop.  */
1906   cond_stmt = last_stmt (loop->header);
1909   create_parallel_loop (loop, create_loop_fn (loc), arg_struct,
1912     create_call_for_reduction (loop, reduction_list, &clsn_data);
1916   /* Cancel the loop (it is simpler to do it here rather than to teach the
1918   cancel_loop_tree (loop);
1920   /* Free loop bound estimations that could contain references to
1922   FOR_EACH_LOOP (loop, 0)
1923     free_numbers_of_iterations_estimates_loop (loop);
1929 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1932   basic_block *bbs = get_loop_body_in_dom_order (loop);
1936   for (i = 0; i < loop->num_nodes; i++)
1990 gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list)
1995   simple_loop_info = vect_analyze_loop_form (loop);
1997   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2007       if (!simple_iv (loop, loop, res, &iv, true)
2028 try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
2030   edge exit = single_dom_exit (loop);
2035      defined inside loop outside of it, unless the values are invariants of
2036      the loop.  */
2037   if (!number_of_iterations_exit (loop, exit, niter, false))
2051 try_create_reduction_list (loop_p loop,
2054   edge exit = single_dom_exit (loop);
2059   gather_scalar_reductions (loop, reduction_list);
2079 	      fprintf (dump_file, " used outside loop\n");
2094 		  && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
2118   /* The iterations of the loop may communicate only through bivs whose
2120   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2126       if (!virtual_operand_p (def) && !simple_iv (loop, loop, def, &iv, true))
2146    primitives.  Returns true if some loop was parallelized, false
2154   struct loop *loop;
2170   FOR_EACH_LOOP (loop, 0)
2175         fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
2176 	if (loop->inner)
2177 	  fprintf (dump_file, "loop %d is not innermost\n",loop->num);
2179 	  fprintf (dump_file, "loop %d is innermost\n",loop->num);
2184       if (flag_loop_parallelize_all && !loop->can_be_parallel)
2187 	   fprintf (dump_file, "loop is not parallel according to graphite\n");
2191       if (!single_dom_exit (loop))
2195 	  fprintf (dump_file, "loop is !single_dom_exit\n");
2200       if (/* And of course, the loop must be parallelizable.  */
2201 	  !can_duplicate_loop_p (loop)
2202 	  || loop_has_blocks_with_irreducible_flag (loop)
2203 	  || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
2205 	  || loop_has_vector_phi_nodes (loop))
2208       estimated = estimated_stmt_executions_int (loop);
2210 	estimated = max_stmt_executions_int (loop);
2217 	      || optimize_loop_nest_for_size_p (loop)))
2220       if (!try_get_loop_niter (loop, &niter_desc))
2223       if (!try_create_reduction_list (loop, &reduction_list))
2227 	  && !loop_parallel_p (loop, &parloop_obstack))
2233 	if (loop->inner)
2234 	  fprintf (dump_file, "parallelizing outer loop %d\n",loop->header->index);
2236 	  fprintf (dump_file, "parallelizing inner loop %d\n",loop->header->index);
2237 	loop_loc = find_loop_location (loop);
2242       gen_parallel_loop (loop, &reduction_list,