contrib/gcc/tree-vect-analyze.c

44 static loop_vec_info vect_analyze_loop_form (struct loop *);
60 static tree vect_get_loop_niters (struct loop *, tree *);
74    loop. For example, when vectorizing a loop that operates on 4byte elements,
81    in the loop.
83    VF is also the factor by which the loop iterations are strip-mined, e.g.:
84    original loop:
89    vectorized loop:
98   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
100   int nbbs = loop->num_nodes;
140                   fprintf (vect_dump, "not vectorized: vector stmt in loop:");
226    Scan the loop stmts and make sure they are all vectorizable.  */
231   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
233   int nbbs = loop->num_nodes;
267 		fprintf (vect_dump, "not vectorized: value used after loop.");
274 	         in the loop.  */
296 	     - the COND_EXPR which is the loop exit condition
297 	     - any LABEL_EXPRs in the loop
298 	     - computations that are used only for array indexing or loop
358   /* All operations in the loop are either irrelevant (deal with loop
359      control, or dead), or only used outside the loop and can be moved
360      out of the loop (e.g. invariants, inductions).  The loop can be
362      touching this loop.  */
367 		 "All the computation can be taken out of the loop.");
370 		 "not vectorized: redundant loop. no profit to vectorize.");
393         fprintf (vect_dump, "epilog loop required.");
398                      "not vectorized: can't create epilog loop 1.");
401       if (!slpeel_can_duplicate_loop_p (loop, loop->single_exit))
405                      "not vectorized: can't create epilog loop 2.");
462    analyzing the loop (scalar) PHIs; Classify each cycle as one of the
479    Note: the following loop *is* vectorizable:
487               loop: i_2 = PHI (i_0, i_1)
490                     GOTO loop;
502   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
503   basic_block bb = loop->header;
536       access_fn = analyze_scalar_evolution (loop, def);
547       if (vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
557       reduc_stmt = vect_is_simple_reduction (loop, phi);
586   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
623   loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
631       /* Same loop iteration.  */
676    Examine all the data references in the loop, and make sure there do not
773 	 the analysis phase, before deciding to vectorize the loop.  */
810    Compute the misalignment of data references in the loop.
832              zero in the vector loop by the peel.
833    NPEEL - the number of iterations in the peel loop if the misalignment
853      are aligned in the vector loop.  */
880    Return TRUE if all data references in the loop can be
918    a few loop iterations.  Return false otherwise.  */
968    This pass will use loop versioning and loop peeling in order to enhance
969    the alignment of data references in the loop.
972    original loop is to be vectorized; Any other loops that are created by
978    intel uses when given a loop with several memory accesses, is as follows:
980    peeling. Then, either (1) generate a loop in which 'p' is aligned and all
981    other accesses are not necessarily aligned, or (2) use loop versioning to
982    generate one loop in which all accesses are aligned, and another loop in
990    guide us on which access to peel for, whether to use loop versioning, how
998      -- original loop, before alignment analysis:
1010      -- Possibility 1: we do loop versioning:
1012 	for (i=0; i<N; i++){	# loop 1A
1018 	for (i=0; i<N; i++){	# loop 1B
1024      -- Possibility 2: we do loop peeling:
1025      for (i = 0; i < 3; i++){	# (scalar loop, not to be vectorized).
1029      for (i = 3; i < N; i++){	# loop 2A
1034      -- Possibility 3: combination of loop peeling and versioning:
1035      for (i = 0; i < 3; i++){	# (scalar loop, not to be vectorized).
1040 	for (i = 3; i<N; i++){	# loop 3A
1046 	for (i = 3; i<N; i++){	# loop 3B
1080         then see if loop versioning checks can be used to make all data
1103      misaligned store in the loop.
1119   /* Often peeling for alignment will require peeling for loop-bound, which in
1120      turn requires that we know how to adjust the loop ivs after the loop.  */
1132              in the peeled loop (the peeling factor) for use in updating
1236                  references in the loop.  The vectorizer currently supports
1264          of the loop being vectorized.  */
1295    Analyze the alignment of the data-references in the loop.
1339    Analyze the access pattern of all the data references in the loop.
1370   Find all the data references in the loop.
1374    1- vect_analyze_data_refs(loop): call compute_data_dependences_for_loop to
1375       find and analyze all data-refs in the loop and their dependences.
1385   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1394   compute_data_dependences_for_loop (loop, false,
1530    Return true if STMT in loop that is represented by LOOP_VINFO is
1534    - it has uses outside the loop.
1536    - control stmts in the loop (except for the exit condition).
1544   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1553   /* cond stmt other than loop exit cond.  */
1566   /* uses outside the loop.  */
1572 	  if (!flow_bb_inside_loop_p (loop, bb))
1575 		fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
1577 	      /* We expect all such uses to be in the loop exit phis
1578 		 (because of loop closed form)   */
1580 	      gcc_assert (bb == loop->single_exit->dest);
1593    Not all stmts in the loop need to be vectorized. For example:
1602    Stmt 1 and 3 do not need to be vectorized, because loop control and
1611   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1613   unsigned int nbbs = loop->num_nodes;
1633   bb = loop->header;
1678          in the loop, mark the stmt that defines it (DEF_STMT) as
1708 	     by a loop-header-phi. We don't want to mark the phi as live or
1713 	     The rest of the uses of STMT are defined in the loop body. For
1719              value that is used across loop iterations) and irrelevant (since it
1720              is not used inside the loop), it will be vectorized, and therefore
1759           if (!flow_bb_inside_loop_p (loop, bb))
1780    time, an epilog loop will be generated, and the loop induction variables
1782    the epilog loop.  Here we check that the access function of the loop IVs
1783    and the expression that represents the loop bound are simple enough.
1789   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1790   basic_block bb = loop->header;
1793   /* Analyze phi functions of the loop header.  */
1831 	(loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
1846       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
1868    Determine how many iterations the loop is executed.
1871    Return the loop exit condition.  */
1874 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
1881   niters = number_of_iterations_in_loop (loop);
1895   return get_loop_exit_condition (loop);
1902    - it's an inner-most loop
1903    - number of BBs = 2 (which are the loop header and the latch)
1904    - the loop has a pre-header
1905    - the loop has a single entry and exit
1906    - the loop exit condition is simple enough, and the number of iterations
1907      can be analyzed (a countable loop).  */
1910 vect_analyze_loop_form (struct loop *loop)
1919   if (loop->inner)
1922         fprintf (vect_dump, "not vectorized: nested loop.");
1926   if (!loop->single_exit
1927       || loop->num_nodes != 2
1928       || EDGE_COUNT (loop->header->preds) != 2)
1932           if (!loop->single_exit)
1934           else if (loop->num_nodes != 2)
1935             fprintf (vect_dump, "not vectorized: too many BBs in loop.");
1936           else if (EDGE_COUNT (loop->header->preds) != 2)
1943   /* We assume that the loop exit condition is at the end of the loop. i.e,
1944      that the loop is represented as a do-while (with a proper if-guard
1945      before the loop if needed), where the loop header contains all the
1947   if (!empty_block_p (loop->latch)
1948         || phi_nodes (loop->latch))
1951         fprintf (vect_dump, "not vectorized: unexpected loop form.");
1956   if (!single_pred_p (loop->single_exit->dest))
1958       edge e = loop->single_exit;
1968 	    fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
1973   if (empty_block_p (loop->header))
1976         fprintf (vect_dump, "not vectorized: empty loop.");
1980   loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
2003   loop_vinfo = new_loop_vec_info (loop);
2034 vect_analyze_loop (struct loop *loop)
2042   /* Check the CFG characteristics of the loop (nesting, entry/exit, etc.  */
2044   loop_vinfo = vect_analyze_loop_form (loop);
2048 	fprintf (vect_dump, "bad loop form.");
2052   /* Find all data references in the loop (which correspond to vdefs/vuses)
2053      and analyze their evolution in the loop.
2085   /* Analyze the alignment of the data-refs in the loop.
2106   /* Analyze data dependences between the data-refs in the loop.
2118   /* Analyze the access patterns of the data-refs in the loop (consecutive,
2130   /* This pass will decide on using loop versioning and/or loop peeling in
2131      order to enhance the alignment of data references in the loop.  */
2142   /* Scan all the operations in the loop and make sure they are
2149 	fprintf (vect_dump, "bad operation or unsupported loop bound.");