| blob | 18c22e7eac7a0133a737162719d380248bae2f0c |
1 /* Transformation Utilities for Loop Vectorization.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
48 /* Utility functions for the code transformation. */
52 static tree vect_create_data_ref_ptr
54 static tree vect_create_addr_base_for_vector_ref
59 static void vect_finish_stmt_generation
62 static void vect_create_epilog_for_reduction
66 /* Utility function dealing with loop peeling (not peeling itself). */
67 static void vect_generate_tmps_on_preheader
77 static int
79 {
83 {
101 }
102 }
105 /* Function vect_estimate_min_profitable_iters
107 Return the number of iterations required for the vector version of the
108 loop to be profitable relative to the cost of the scalar version of the
109 loop.
111 TODO: Take profile info into account before making vectorization
112 decisions, if available. */
114 int
116 {
134 slp_instance instance;
136 /* Cost model disabled. */
138 {
142 }
144 /* If the number of iterations is unknown, or the
145 peeling-for-misalignment amount is unknown, we will have to generate
146 a runtime test to test the loop count against the threshold. */
151 /* Requires loop versioning tests to handle misalignment. */
154 {
155 /* FIXME: Make cost depend on complexity of individual check. */
156 vec_outside_cost +=
161 }
164 {
165 /* FIXME: Make cost depend on complexity of individual check. */
166 vec_outside_cost +=
171 }
175 {
177 }
179 /* Count statements in scalar loop. Using this as scalar cost for a single
180 iteration for now.
182 TODO: Add outer loop support.
184 TODO: Consider assigning different costs to different scalar
185 statements. */
187 /* FORNOW. */
192 {
193 gimple_stmt_iterator si;
198 else
202 {
205 /* Skip stmts that are not vectorized inside the loop. */
212 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
213 some of the "outside" costs are generated inside the outer-loop. */
215 }
216 }
218 /* Add additional cost for the peeled instructions in prologue and epilogue
219 loop.
221 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
222 at compile-time - we assume it's vf/2 (the worst would be vf-1).
224 TODO: Build an expression that represents peel_iters for prologue and
225 epilogue to be used in a run-time test. */
228 {
234 /* If peeling for alignment is unknown, loop bound of main loop becomes
235 unknown. */
239 "epilogue peel iters set to vf/2 because "
242 /* If peeled iterations are unknown, count a taken branch and a not taken
243 branch per peeled loop. Even if scalar loop iterations are known,
244 vector iterations are not known since peeled prologue iterations are
245 not known. Hence guards remain the same. */
249 }
250 else
251 {
253 {
260 }
261 else
265 {
269 "epilogue peel iters set to vf/2 because "
272 /* If peeled iterations are known but number of scalar loop
273 iterations are unknown, count a taken branch per peeled loop. */
276 }
277 else
278 {
283 }
284 }
290 /* FORNOW: The scalar outside cost is incremented in one of the
291 following ways:
293 1. The vectorizer checks for alignment and aliasing and generates
294 a condition that allows dynamic vectorization. A cost model
295 check is ANDED with the versioning condition. Hence scalar code
296 path now has the added cost of the versioning check.
298 if (cost > th & versioning_check)
299 jmp to vector code
301 Hence run-time scalar is incremented by not-taken branch cost.
303 2. The vectorizer then checks if a prologue is required. If the
304 cost model check was not done before during versioning, it has to
305 be done before the prologue check.
307 if (cost <= th)
308 prologue = scalar_iters
309 if (prologue == 0)
310 jmp to vector code
311 else
312 execute prologue
313 if (prologue == num_iters)
314 go to exit
316 Hence the run-time scalar cost is incremented by a taken branch,
317 plus a not-taken branch, plus a taken branch cost.
319 3. The vectorizer then checks if an epilogue is required. If the
320 cost model check was not done before during prologue check, it
321 has to be done with the epilogue check.
323 if (prologue == 0)
324 jmp to vector code
325 else
326 execute prologue
327 if (prologue == num_iters)
328 go to exit
329 vector code:
330 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
331 jmp to epilogue
333 Hence the run-time scalar cost should be incremented by 2 taken
334 branches.
336 TODO: The back end may reorder the BBS's differently and reverse
337 conditions/branch directions. Change the estimates below to
338 something more reasonable. */
341 {
342 /* Cost model check occurs at versioning. */
346 else
347 {
348 /* Cost model occurs at prologue generation. */
352 /* Cost model check occurs at epilogue generation. */
353 else
355 }
356 }
358 /* Add SLP costs. */
361 {
364 }
366 /* Calculate number of iterations required to make the vector version
367 profitable, relative to the loop bodies only. The following condition
368 must hold true:
369 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
370 where
371 SIC = scalar iteration cost, VIC = vector iteration cost,
372 VOC = vector outside cost, VF = vectorization factor,
373 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
374 SOC = scalar outside cost for run time cost model check. */
377 {
380 else
381 {
391 min_profitable_iters++;
392 }
393 }
394 /* vector version will never be profitable. */
395 else
396 {
399 "is divisible by scalar iteration cost = %d by a factor "
403 }
406 {
409 vec_inside_cost);
411 vec_outside_cost);
413 scalar_single_iter_cost);
416 peel_iters_prologue);
418 peel_iters_epilogue);
420 min_profitable_iters);
421 }
423 min_profitable_iters =
426 /* Because the condition we create is:
427 if (niters <= min_profitable_iters)
428 then skip the vectorized loop. */
429 min_profitable_iters--;
433 min_profitable_iters);
436 }
439 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
440 functions. Design better to avoid maintenance issues. */
442 /* Function vect_model_reduction_cost.
444 Models cost for a reduction operation, including the vector ops
445 generated within the strip-mine loop, the initial definition before
446 the loop, and the epilogue code that must be generated. */
448 static bool
451 {
454 optab optab;
455 tree vectype;
457 tree reduction_op;
463 /* Cost of reduction op inside loop. */
469 {
482 }
486 {
488 {
491 }
493 }
503 /* Add in cost for initial definition. */
506 /* Determine cost of epilogue code.
508 We have a reduction operator that will reduce the vector in one statement.
509 Also requires scalar extract. */
512 {
515 else
516 {
518 tree bitsize =
525 /* We have a whole vector shift available. */
529 /* Final reduction via vector shifts and the reduction operator. Also
530 requires scalar extract. */
533 else
534 /* Use extracts and reduction op for final reduction. For N elements,
535 we have N extracts and N-1 reduction ops. */
537 }
538 }
548 }
551 /* Function vect_model_induction_cost.
553 Models cost for induction operations. */
555 static void
557 {
558 /* loop cost for vec_loop. */
560 /* prologue cost for vec_init and vec_step. */
567 }
570 /* Function vect_model_simple_cost.
572 Models cost for simple operations, i.e. those that only emit ncopies of a
573 single op. Right now, this does not account for multiple insns that could
574 be generated for the single vector op. We will handle that shortly. */
576 void
579 {
583 /* The SLP costs were already calculated during SLP tree build. */
589 /* FORNOW: Assuming maximum 2 args per stmts. */
591 {
594 }
600 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
603 }
606 /* Function vect_cost_strided_group_size
608 For strided load or store, return the group_size only if it is the first
609 load or store of a group, else return 1. This ensures that group size is
610 only returned once per group. */
612 static int
614 {
621 }
624 /* Function vect_model_store_cost
626 Models cost for stores. In the case of strided accesses, one access
627 has the overhead of the strided access attributed to it. */
629 void
632 {
636 /* The SLP costs were already calculated during SLP tree build. */
643 /* Strided access? */
646 /* Not a strided access. */
647 else
650 /* Is this an access in a group of stores, which provide strided access?
651 If so, add in the cost of the permutes. */
653 {
654 /* Uses a high and low interleave operation for each needed permute. */
660 group_size);
662 }
664 /* Costs of the stores. */
671 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
674 }
677 /* Function vect_model_load_cost
679 Models cost for loads. In the case of strided accesses, the last access
680 has the overhead of the strided access attributed to it. Since unaligned
681 accesses are supported for loads, we also account for the costs of the
682 access scheme chosen. */
684 void
687 {
690 gimple first_stmt;
694 /* The SLP costs were already calculated during SLP tree build. */
698 /* Strided accesses? */
701 {
704 }
705 /* Not a strided access. */
706 else
707 {
710 }
714 /* Is this an access in a group of loads providing strided access?
715 If so, add in the cost of the permutes. */
717 {
718 /* Uses an even and odd extract operations for each needed permute. */
724 group_size);
726 }
728 /* The loads themselves. */
730 {
732 {
739 }
741 {
742 /* Here, we assign an additional cost for the unaligned load. */
750 }
752 {
755 /* FIXME: If the misalignment remains fixed across the iterations of
756 the containing loop, the following cost should be added to the
757 outside costs. */
762 }
764 {
769 /* Unaligned software pipeline has a load of an address, an initial
770 load, and possibly a mask operation to "prime" the loop. However,
771 if this is an access in a group of loads, which provide strided
772 access, then the above cost should only be considered for one
773 access in the group. Inside the loop, there is a load op
774 and a realignment op. */
777 {
781 }
786 }
790 }
796 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
799 }
802 /* Function vect_get_new_vect_var.
804 Returns a name for a new variable. The current naming scheme appends the
805 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
806 the name of vectorizer generated variables, and appends that to NAME if
807 provided. */
809 static tree
811 {
813 tree new_vect_var;
816 {
828 }
831 {
835 }
836 else
839 /* Mark vector typed variable as a gimple register variable. */
844 }
847 /* Function vect_create_addr_base_for_vector_ref.
849 Create an expression that computes the address of the first memory location
850 that will be accessed for a data reference.
852 Input:
853 STMT: The statement containing the data reference.
854 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
855 OFFSET: Optional. If supplied, it is be added to the initial address.
856 LOOP: Specify relative to which loop-nest should the address be computed.
857 For example, when the dataref is in an inner-loop nested in an
858 outer-loop that is now being vectorized, LOOP can be either the
859 outer-loop, or the inner-loop. The first memory location accessed
860 by the following dataref ('in' points to short):
862 for (i=0; i<N; i++)
863 for (j=0; j<M; j++)
864 s += in[i+j]
866 is as follows:
867 if LOOP=i_loop: &in (relative to i_loop)
868 if LOOP=j_loop: &in+i*2B (relative to j_loop)
870 Output:
871 1. Return an SSA_NAME whose value is the address of the memory location of
872 the first vector of the data reference.
873 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
874 these statement(s) which define the returned SSA_NAME.
876 FORNOW: We are only handling array accesses with step 1. */
878 static tree
881 tree offset,
883 {
888 tree base_name;
889 tree data_ref_base_var;
890 tree vec_stmt;
892 tree dest;
901 {
910 }
912 /* Create data_ref_base */
917 data_ref_base_var);
920 /* Create base_offset */
930 {
940 }
942 /* base + base_offset */
948 /* addr_expr = addr_base */
960 {
963 }
965 }
968 /* Function vect_create_data_ref_ptr.
970 Create a new pointer to vector type (vp), that points to the first location
971 accessed in the loop by STMT, along with the def-use update chain to
972 appropriately advance the pointer through the loop iterations. Also set
973 aliasing information for the pointer. This vector pointer is used by the
974 callers to this function to create a memory reference expression for vector
975 load/store access.
977 Input:
978 1. STMT: a stmt that references memory. Expected to be of the form
979 GIMPLE_ASSIGN <name, data-ref> or
980 GIMPLE_ASSIGN <data-ref, name>.
981 2. AT_LOOP: the loop where the vector memref is to be created.
982 3. OFFSET (optional): an offset to be added to the initial address accessed
983 by the data-ref in STMT.
984 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
985 pointing to the initial address.
986 5. TYPE: if not NULL indicates the required type of the data-ref.
988 Output:
989 1. Declare a new ptr to vector_type, and have it point to the base of the
990 data reference (initial addressed accessed by the data reference).
991 For example, for vector of type V8HI, the following code is generated:
993 v8hi *vp;
994 vp = (v8hi *)initial_address;
996 if OFFSET is not supplied:
997 initial_address = &a[init];
998 if OFFSET is supplied:
999 initial_address = &a[init + OFFSET];
1001 Return the initial_address in INITIAL_ADDRESS.
1003 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
1004 update the pointer in each iteration of the loop.
1006 Return the increment stmt that updates the pointer in PTR_INCR.
1008 3. Set INV_P to true if the access pattern of the data reference in the
1009 vectorized loop is invariant. Set it to false otherwise.
1011 4. Return the pointer. */
1013 static tree
1017 {
1018 tree base_name;
1025 tree vect_ptr_type;
1026 tree vect_ptr;
1027 tree tag;
1028 tree new_temp;
1029 gimple vec_stmt;
1031 edge pe;
1032 basic_block new_bb;
1033 tree vect_ptr_init;
1035 tree vptr;
1036 gimple_stmt_iterator incr_gsi;
1039 gimple incr;
1040 tree step;
1042 /* Check the step (evolution) of the load in LOOP, and record
1043 whether it's invariant. */
1046 else
1051 else
1054 /* Create an expression for the first address accessed by this load
1055 in LOOP. */
1059 {
1072 }
1074 /** (1) Create the new vector-pointer variable: **/
1077 else
1087 {
1091 }
1095 /** (2) Add aliasing information to the new vector-pointer:
1096 (The points-to info (DR_PTR_INFO) may be defined later.) **/
1101 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
1102 tag must be created with tag added to its may alias list. */
1105 else
1108 /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
1109 vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
1110 def-use update cycles for the pointer: One relative to the outer-loop
1111 (LOOP), which is what steps (3) and (4) below do. The other is relative
1112 to the inner-loop (which is the inner-most loop containing the dataref),
1113 and this is done be step (5) below.
1115 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
1116 inner-most loop, and so steps (3),(4) work the same, and step (5) is
1117 redundant. Steps (3),(4) create the following:
1119 vp0 = &base_addr;
1120 LOOP: vp1 = phi(vp0,vp2)
1121 ...
1122 ...
1123 vp2 = vp1 + step
1124 goto LOOP
1126 If there is an inner-loop nested in loop, then step (5) will also be
1127 applied, and an additional update in the inner-loop will be created:
1129 vp0 = &base_addr;
1130 LOOP: vp1 = phi(vp0,vp2)
1131 ...
1132 inner: vp3 = phi(vp1,vp4)
1133 vp4 = vp3 + inner_step
1134 if () goto inner
1135 ...
1136 vp2 = vp1 + step
1137 if () goto LOOP */
1139 /** (3) Calculate the initial address the vector-pointer, and set
1140 the vector-pointer to point to it before the loop: **/
1142 /* Create: (&(base[init_val+offset]) in the loop preheader. */
1148 {
1151 }
1155 /* Create: p = (vectype *) initial_base */
1164 /** (4) Handle the updating of the vector-pointer inside the loop.
1165 This is needed when ONLY_INIT is false, and also when AT_LOOP
1166 is the inner-loop nested in LOOP (during outer-loop vectorization).
1167 **/
1170 {
1171 /* Copy the points-to information if it exists. */
1175 }
1176 else
1177 {
1178 /* The step of the vector pointer is the Vector Size. */
1180 /* One exception to the above is when the scalar step of the load in
1181 LOOP is zero. In this case the step here is also zero. */
1194 /* Copy the points-to information if it exists. */
1196 {
1199 }
1206 }
1212 /** (5) Handle the updating of the vector-pointer inside the inner-loop
1213 nested in LOOP, if exists: **/
1217 {
1226 /* Copy the points-to information if it exists. */
1228 {
1231 }
1238 }
1239 else
1241 }
1244 /* Function bump_vector_ptr
1246 Increment a pointer (to a vector type) by vector-size. If requested,
1247 i.e. if PTR-INCR is given, then also connect the new increment stmt
1248 to the existing def-use update-chain of the pointer, by modifying
1249 the PTR_INCR as illustrated below:
1251 The pointer def-use update-chain before this function:
1252 DATAREF_PTR = phi (p_0, p_2)
1253 ....
1254 PTR_INCR: p_2 = DATAREF_PTR + step
1256 The pointer def-use update-chain after this function:
1257 DATAREF_PTR = phi (p_0, p_2)
1258 ....
1259 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1260 ....
1261 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
1263 Input:
1264 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
1265 in the loop.
1266 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
1267 the loop. The increment amount across iterations is expected
1268 to be vector_size.
1269 BSI - location where the new update stmt is to be placed.
1270 STMT - the original scalar memory-access stmt that is being vectorized.
1271 BUMP - optional. The offset by which to bump the pointer. If not given,
1272 the offset is assumed to be vector_size.
1274 Output: Return NEW_DATAREF_PTR as illustrated above.
1276 */
1278 static tree
1281 {
1287 gimple incr_stmt;
1288 ssa_op_iter iter;
1289 use_operand_p use_p;
1290 tree new_dataref_ptr;
1301 /* Copy the points-to information if it exists. */
1309 /* Update the vector-pointer's cross-iteration increment. */
1311 {
1316 else
1318 }
1321 }
1324 /* Function vect_create_destination_var.
1326 Create a new temporary of type VECTYPE. */
1328 static tree
1330 {
1331 tree vec_dest;
1333 tree type;
1348 }
1351 /* Function vect_init_vector.
1353 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1354 the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1355 is not NULL. Otherwise, place the initialization at the loop preheader.
1356 Return the DEF of INIT_STMT.
1357 It will be used in the vectorization of STMT. */
1359 static tree
1362 {
1364 tree new_var;
1365 gimple init_stmt;
1366 tree vec_oprnd;
1367 edge pe;
1368 tree new_temp;
1369 basic_block new_bb;
1379 else
1380 {
1389 }
1392 {
1395 }
1399 }
1402 /* For constant and loop invariant defs of SLP_NODE this function returns
1403 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1404 OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1405 stmts. NUMBER_OF_VECTORS is the number of vector defs to create. */
1407 static void
1410 {
1416 tree vec_cst;
1419 tree vector_type;
1428 {
1431 }
1432 else
1433 {
1436 }
1439 {
1442 }
1443 else
1444 {
1448 }
1452 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1453 created vectors. It is greater than 1 if unrolling is performed.
1455 For example, we have two scalar operands, s1 and s2 (e.g., group of
1456 strided accesses of size two), while NUNITS is four (i.e., four scalars
1457 of this type can be packed in a vector). The output vector will contain
1458 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1459 will be 2).
1461 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1462 containing the operands.
1464 For example, NUNITS is four as before, and the group size is 8
1465 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1466 {s5, s6, s7, s8}. */
1472 {
1474 {
1477 else
1480 /* Create 'vect_ = {op0,op1,...,opn}'. */
1483 number_of_places_left_in_vector--;
1486 {
1491 else
1496 }
1497 }
1498 }
1500 /* Since the vectors are created in the reverse order, we should invert
1501 them. */
1504 {
1507 }
1511 /* In case that VF is greater than the unrolling factor needed for the SLP
1512 group of stmts, NUMBER_OF_VECTORS to be created is greater than
1513 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1514 to replicate the vectors. */
1516 {
1519 }
1520 }
1523 /* Get vectorized definitions from SLP_NODE that contains corresponding
1524 vectorized def-stmts. */
1526 static void
1528 {
1529 tree vec_oprnd;
1530 gimple vec_def_stmt;
1537 i++)
1538 {
1542 }
1543 }
1546 /* Get vectorized definitions for SLP_NODE.
1547 If the scalar definitions are loop invariants or constants, collect them and
1548 call vect_get_constant_vectors() to create vector stmts.
1549 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1550 must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1551 vect_get_slp_vect_defs() to retrieve them.
1552 If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1553 the right node. This is used when the second operand must remain scalar. */
1555 static void
1558 {
1559 gimple first_stmt;
1565 /* The number of vector defs is determined by the number of vector statements
1566 in the node from which we get those statements. */
1569 else
1570 {
1572 /* Number of vector stmts was calculated according to LHS in
1573 vect_schedule_slp_instance(), fix it by replacing LHS with RHS, if
1574 necessary. See vect_get_smallest_scalar_type() for details. */
1578 {
1581 }
1582 }
1584 /* Allocate memory for vectorized defs. */
1587 /* SLP_NODE corresponds either to a group of stores or to a group of
1588 unary/binary operations. We don't call this function for loads. */
1590 /* The defs are already vectorized. */
1592 else
1593 /* Build vectors from scalar defs. */
1597 /* Since we don't call this function with loads, this is a group of
1598 stores. */
1605 /* The number of vector defs is determined by the number of vector statements
1606 in the node from which we get those statements. */
1609 else
1615 /* The defs are already vectorized. */
1617 else
1618 /* Build vectors from scalar defs. */
1620 }
1623 /* Function get_initial_def_for_induction
1625 Input:
1626 STMT - a stmt that performs an induction operation in the loop.
1627 IV_PHI - the initial value of the induction variable
1629 Output:
1630 Return a vector variable, initialized with the first VF values of
1631 the induction variable. E.g., for an iv with IV_PHI='X' and
1632 evolution S, for a vector of 4 units, we want to return:
1633 [X, X + S, X + 2*S, X + 3*S]. */
1635 static tree
1637 {
1642 tree vectype;
1646 basic_block new_bb;
1648 tree access_fn;
1649 tree new_var;
1650 tree new_name;
1658 tree expr;
1662 imm_use_iterator imm_iter;
1663 use_operand_p use_p;
1664 gimple exit_phi;
1665 edge latch_e;
1666 tree loop_arg;
1667 gimple_stmt_iterator si;
1678 /* Find the first insertion point in the BB. */
1683 else
1686 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
1688 {
1691 }
1692 else
1706 /* Create the vector that holds the initial_value of the induction. */
1708 {
1709 /* iv_loop is nested in the loop to be vectorized. init_expr had already
1710 been created during vectorization of previous stmts; We obtain it from
1711 the STMT_VINFO_VEC_STMT of the defining stmt. */
1714 }
1715 else
1716 {
1717 /* iv_loop is the loop to be vectorized. Create:
1718 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
1724 {
1727 }
1732 {
1733 /* Create: new_name_i = new_name + step_expr */
1745 {
1748 }
1750 }
1751 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
1754 }
1757 /* Create the vector that holds the step of the induction. */
1759 /* iv_loop is nested in the loop to be vectorized. Generate:
1760 vec_step = [S, S, S, S] */
1762 else
1763 {
1764 /* iv_loop is the loop to be vectorized. Generate:
1765 vec_step = [VF*S, VF*S, VF*S, VF*S] */
1768 }
1778 /* Create the following def-use cycle:
1779 loop prolog:
1780 vec_init = ...
1781 vec_step = ...
1782 loop:
1783 vec_iv = PHI <vec_init, vec_loop>
1784 ...
1785 STMT
1786 ...
1787 vec_loop = vec_iv + vec_step; */
1789 /* Create the induction-phi that defines the induction-operand. */
1797 /* Create the iv update inside the loop */
1805 /* Set the arguments of the phi node: */
1810 /* In case that vectorization factor (VF) is bigger than the number
1811 of elements that we can fit in a vectype (nunits), we have to generate
1812 more than one vector stmt - i.e - we need to "unroll" the
1813 vector stmt by a factor VF/nunits. For more details see documentation
1814 in vectorizable_operation. */
1817 {
1818 stmt_vec_info prev_stmt_vinfo;
1819 /* FORNOW. This restriction should be relaxed. */
1822 /* Create the vector that holds the step of the induction. */
1835 {
1836 /* vec_i = vec_prev + vec_step */
1847 }
1848 }
1851 {
1852 /* Find the loop-closed exit-phi of the induction, and record
1853 the final vector of induction results: */
1856 {
1858 {
1861 }
1862 }
1864 {
1866 /* FORNOW. Currently not supporting the case that an inner-loop induction
1867 is not used in the outer-loop (i.e. only outside the outer-loop). */
1873 {
1876 }
1877 }
1878 }
1882 {
1887 }
1891 }
1894 /* Function vect_get_vec_def_for_operand.
1896 OP is an operand in STMT. This function returns a (vector) def that will be
1897 used in the vectorized stmt for STMT.
1899 In the case that OP is an SSA_NAME which is defined in the loop, then
1900 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1902 In case OP is an invariant or constant, a new stmt that creates a vector def
1903 needs to be introduced. */
1905 static tree
1907 {
1908 tree vec_oprnd;
1909 gimple vec_stmt;
1910 gimple def_stmt;
1916 tree vec_inv;
1917 tree vec_cst;
1919 tree def;
1923 tree vector_type;
1926 {
1929 }
1934 {
1936 {
1939 }
1941 {
1944 }
1945 }
1948 {
1949 /* Case 1: operand is a constant. */
1951 {
1955 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1960 {
1962 }
1965 }
1967 /* Case 2: operand is defined outside the loop - loop invariant. */
1969 {
1977 /* Create 'vec_inv = {inv,inv,..,inv}' */
1982 {
1984 }
1986 /* FIXME: use build_constructor directly. */
1989 }
1991 /* Case 3: operand is defined inside the loop. */
1993 {
1997 /* Get the def from the vectorized stmt. */
2005 else
2008 }
2010 /* Case 4: operand is defined by a loop header phi - reduction */
2012 {
2018 /* Get the def before the loop */
2021 }
2023 /* Case 5: operand is defined by loop-header phi - induction. */
2025 {
2028 /* Get the def from the vectorized stmt. */
2034 }
2038 }
2039 }
2042 /* Function vect_get_vec_def_for_stmt_copy
2044 Return a vector-def for an operand. This function is used when the
2045 vectorized stmt to be created (by the caller to this function) is a "copy"
2046 created in case the vectorized result cannot fit in one vector, and several
2047 copies of the vector-stmt are required. In this case the vector-def is
2048 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
2049 of the stmt that defines VEC_OPRND.
2050 DT is the type of the vector def VEC_OPRND.
2052 Context:
2053 In case the vectorization factor (VF) is bigger than the number
2054 of elements that can fit in a vectype (nunits), we have to generate
2055 more than one vector stmt to vectorize the scalar stmt. This situation
2056 arises when there are multiple data-types operated upon in the loop; the
2057 smallest data-type determines the VF, and as a result, when vectorizing
2058 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
2059 vector stmt (each computing a vector of 'nunits' results, and together
2060 computing 'VF' results in each iteration). This function is called when
2061 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
2062 which VF=16 and nunits=4, so the number of copies required is 4):
2064 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
2066 S1: x = load VS1.0: vx.0 = memref0 VS1.1
2067 VS1.1: vx.1 = memref1 VS1.2
2068 VS1.2: vx.2 = memref2 VS1.3
2069 VS1.3: vx.3 = memref3
2071 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
2072 VSnew.1: vz1 = vx.1 + ... VSnew.2
2073 VSnew.2: vz2 = vx.2 + ... VSnew.3
2074 VSnew.3: vz3 = vx.3 + ...
2076 The vectorization of S1 is explained in vectorizable_load.
2077 The vectorization of S2:
2078 To create the first vector-stmt out of the 4 copies - VSnew.0 -
2079 the function 'vect_get_vec_def_for_operand' is called to
2080 get the relevant vector-def for each operand of S2. For operand x it
2081 returns the vector-def 'vx.0'.
2083 To create the remaining copies of the vector-stmt (VSnew.j), this
2084 function is called to get the relevant vector-def for each operand. It is
2085 obtained from the respective VS1.j stmt, which is recorded in the
2086 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
2088 For example, to obtain the vector-def 'vx.1' in order to create the
2089 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
2090 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
2091 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
2092 and return its def ('vx.1').
2093 Overall, to create the above sequence this function will be called 3 times:
2094 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
2095 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
2096 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
2098 static tree
2100 {
2101 gimple vec_stmt_for_operand;
2102 stmt_vec_info def_stmt_info;
2104 /* Do nothing; can reuse same def. */
2116 else
2119 }
2122 /* Get vectorized definitions for the operands to create a copy of an original
2123 stmt. See vect_get_vec_def_for_stmt_copy() for details. */
2125 static void
2129 {
2136 {
2140 }
2141 }
2144 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not NULL. */
2146 static void
2149 slp_tree slp_node)
2150 {
2153 else
2154 {
2155 tree vec_oprnd;
2162 {
2166 }
2167 }
2168 }
2171 /* Function vect_finish_stmt_generation.
2173 Insert a new stmt. */
2175 static void
2178 {
2189 {
2192 }
2195 }
2198 /* Function get_initial_def_for_reduction
2200 Input:
2201 STMT - a stmt that performs a reduction operation in the loop.
2202 INIT_VAL - the initial value of the reduction variable
2204 Output:
2205 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2206 of the reduction (used for adjusting the epilog - see below).
2207 Return a vector variable, initialized according to the operation that STMT
2208 performs. This vector will be used as the initial value of the
2209 vector of partial results.
2211 Option1 (adjust in epilog): Initialize the vector as follows:
2212 add: [0,0,...,0,0]
2213 mult: [1,1,...,1,1]
2214 min/max: [init_val,init_val,..,init_val,init_val]
2215 bit and/or: [init_val,init_val,..,init_val,init_val]
2216 and when necessary (e.g. add/mult case) let the caller know
2217 that it needs to adjust the result by init_val.
2219 Option2: Initialize the vector as follows:
2220 add: [0,0,...,0,init_val]
2221 mult: [1,1,...,1,init_val]
2222 min/max: [init_val,init_val,...,init_val]
2223 bit and/or: [init_val,init_val,...,init_val]
2224 and no adjustments are needed.
2226 For example, for the following code:
2228 s = init_val;
2229 for (i=0;i<n;i++)
2230 s = s + a[i];
2232 STMT is 's = s + a[i]', and the reduction variable is 's'.
2233 For a vector of 4 units, we want to return either [0,0,0,init_val],
2234 or [0,0,0,0] and let the caller know that it needs to adjust
2235 the result at the end by 'init_val'.
2237 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2238 initialization vector is simpler (same element in all entries).
2239 A cost model should help decide between these two schemes. */
2241 static tree
2243 {
2252 tree vecdef;
2253 tree def_for_init;
2254 tree init_def;
2262 else
2268 {
2274 else
2276 /* Create a vector of zeros for init_def. */
2279 else
2295 }
2298 }
2301 /* Function vect_create_epilog_for_reduction
2303 Create code at the loop-epilog to finalize the result of a reduction
2304 computation.
2306 VECT_DEF is a vector of partial results.
2307 REDUC_CODE is the tree-code for the epilog reduction.
2308 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
2309 number of elements that we can fit in a vectype (nunits). In this case
2310 we have to generate more than one vector stmt - i.e - we need to "unroll"
2311 the vector stmt by a factor VF/nunits. For more details see documentation
2312 in vectorizable_operation.
2313 STMT is the scalar reduction stmt that is being vectorized.
2314 REDUCTION_PHI is the phi-node that carries the reduction computation.
2316 This function:
2317 1. Creates the reduction def-use cycle: sets the arguments for
2318 REDUCTION_PHI:
2319 The loop-entry argument is the vectorized initial-value of the reduction.
2320 The loop-latch argument is VECT_DEF - the vector of partial sums.
2321 2. "Reduces" the vector of partial results VECT_DEF into a single result,
2322 by applying the operation specified by REDUC_CODE if available, or by
2323 other means (whole-vector shifts or a scalar loop).
2324 The function also creates a new phi node at the loop exit to preserve
2325 loop-closed form, as illustrated below.
2327 The flow at the entry to this function:
2329 loop:
2330 vec_def = phi <null, null> # REDUCTION_PHI
2331 VECT_DEF = vector_stmt # vectorized form of STMT
2332 s_loop = scalar_stmt # (scalar) STMT
2333 loop_exit:
2334 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2335 use <s_out0>
2336 use <s_out0>
2338 The above is transformed by this function into:
2340 loop:
2341 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2342 VECT_DEF = vector_stmt # vectorized form of STMT
2343 s_loop = scalar_stmt # (scalar) STMT
2344 loop_exit:
2345 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2346 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2347 v_out2 = reduce <v_out1>
2348 s_out3 = extract_field <v_out2, 0>
2349 s_out4 = adjust_result <s_out3>
2350 use <s_out4>
2351 use <s_out4>
2352 */
2354 static void
2358 gimple reduction_phi)
2359 {
2361 stmt_vec_info prev_phi_info;
2362 tree vectype;
2366 basic_block exit_bb;
2367 tree scalar_dest;
2368 tree scalar_type;
2370 gimple_stmt_iterator exit_gsi;
2371 tree vec_dest;
2373 tree new_name;
2376 gimple exit_phi;
2379 tree adjustment_def;
2381 tree orig_name;
2382 imm_use_iterator imm_iter;
2383 use_operand_p use_p;
2386 gimple orig_stmt;
2387 gimple use_stmt;
2394 {
2397 }
2400 {
2413 }
2419 /*** 1. Create the reduction def-use cycle ***/
2421 /* For the case of reduction, vect_get_vec_def_for_operand returns
2422 the scalar def before the loop, that defines the initial value
2423 of the reduction variable. */
2430 {
2431 /* 1.1 set the loop-entry arg of the reduction-phi: */
2434 /* 1.2 set the loop-latch arg for the reduction-phi: */
2440 {
2445 }
2448 }
2450 /*** 2. Create epilog code
2451 The reduction epilog code operates across the elements of the vector
2452 of partial results computed by the vectorized loop.
2453 The reduction epilog code consists of:
2454 step 1: compute the scalar result in a vector (v_out2)
2455 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2456 step 3: adjust the scalar result (s_out3) if needed.
2458 Step 1 can be accomplished using one the following three schemes:
2459 (scheme 1) using reduc_code, if available.
2460 (scheme 2) using whole-vector shifts, if available.
2461 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2462 combined.
2464 The overall epilog code looks like this:
2466 s_out0 = phi <s_loop> # original EXIT_PHI
2467 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2468 v_out2 = reduce <v_out1> # step 1
2469 s_out3 = extract_field <v_out2, 0> # step 2
2470 s_out4 = adjust_result <s_out3> # step 3
2472 (step 3 is optional, and steps 1 and 2 may be combined).
2473 Lastly, the uses of s_out0 are replaced by s_out4.
2475 ***/
2477 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2478 v_out1 = phi <v_loop> */
2484 {
2489 else
2490 {
2493 }
2496 }
2499 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
2500 (i.e. when reduc_code is not available) and in the final adjustment
2501 code (if needed). Also get the original scalar reduction variable as
2502 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
2503 represents a reduction pattern), the tree-code and scalar-def are
2504 taken from the original stmt that the pattern-stmt (STMT) replaces.
2505 Otherwise (it is a regular reduction) - the tree-code and scalar-def
2506 are taken from STMT. */
2510 {
2511 /* Regular reduction */
2513 }
2514 else
2515 {
2516 /* Reduction pattern */
2520 }
2529 /* In case this is a reduction in an inner-loop while vectorizing an outer
2530 loop - we don't need to extract a single scalar result at the end of the
2531 inner-loop. The final vector of partial results will be used in the
2532 vectorized outer-loop, or reduced to a scalar result at the end of the
2533 outer-loop. */
2537 /* FORNOW */
2540 /* 2.3 Create the reduction code, using one of the three schemes described
2541 above. */
2544 {
2545 tree tmp;
2547 /*** Case 1: Create:
2548 v_out2 = reduc_expr <v_out1> */
2561 }
2562 else
2563 {
2569 tree vec_temp;
2573 else
2576 /* Regardless of whether we have a whole vector shift, if we're
2577 emulating the operation via tree-vect-generic, we don't want
2578 to use it. Only the first round of the reduction is likely
2579 to still be profitable via emulation. */
2580 /* ??? It might be better to emit a reduction tree code here, so that
2581 tree-vect-generic can expand the first round via bit tricks. */
2584 else
2585 {
2589 }
2592 {
2593 /*** Case 2: Create:
2594 for (offset = VS/2; offset >= element_size; offset/=2)
2595 {
2596 Create: va' = vec_shift <va, offset>
2597 Create: va = vop <va, va'>
2598 } */
2609 {
2622 }
2625 }
2626 else
2627 {
2628 tree rhs;
2630 /*** Case 3: Create:
2631 s = extract_field <v_out2, 0>
2632 for (offset = element_size;
2633 offset < vector_size;
2634 offset += element_size;)
2635 {
2636 Create: s' = extract_field <v_out2, offset>
2637 Create: s = op <s, s'>
2638 } */
2646 bitsize_zero_node);
2655 {
2658 bitpos);
2666 new_scalar_dest,
2671 }
2674 }
2675 }
2677 /* 2.4 Extract the final scalar result. Create:
2678 s_out3 = extract_field <v_out2, bitpos> */
2681 {
2682 tree rhs;
2692 else
2700 }
2702 vect_finalize_reduction:
2704 /* 2.5 Adjust the final result by the initial value of the reduction
2705 variable. (When such adjustment is not needed, then
2706 'adjustment_def' is zero). For example, if code is PLUS we create:
2707 new_temp = loop_exit_def + adjustment_def */
2710 {
2712 {
2716 }
2717 else
2718 {
2722 }
2728 }
2731 /* 2.6 Handle the loop-exit phi */
2733 /* Replace uses of s_out0 with uses of s_out3:
2734 Find the loop-closed-use at the loop exit of the original scalar result.
2735 (The reduction result is expected to have two immediate uses - one at the
2736 latch block, and one at the loop exit). */
2739 {
2741 {
2744 }
2745 }
2746 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
2750 {
2752 {
2755 /* FORNOW. Currently not supporting the case that an inner-loop
2756 reduction is not used in the outer-loop (but only outside the
2757 outer-loop). */
2769 }
2771 /* Replace the uses: */
2776 }
2778 }
2781 /* Function vectorizable_reduction.
2783 Check if STMT performs a reduction operation that can be vectorized.
2784 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2785 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2786 Return FALSE if not a vectorizable STMT, TRUE otherwise.
2788 This function also handles reduction idioms (patterns) that have been
2789 recognized in advance during vect_pattern_recog. In this case, STMT may be
2790 of this form:
2791 X = pattern_expr (arg0, arg1, ..., X)
2792 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2793 sequence that had been detected and replaced by the pattern-stmt (STMT).
2795 In some cases of reduction patterns, the type of the reduction variable X is
2796 different than the type of the other arguments of STMT.
2797 In such cases, the vectype that is used when transforming STMT into a vector
2798 stmt is different than the vectype that is used to determine the
2799 vectorization factor, because it consists of a different number of elements
2800 than the actual number of elements that are being operated upon in parallel.
2802 For example, consider an accumulation of shorts into an int accumulator.
2803 On some targets it's possible to vectorize this pattern operating on 8
2804 shorts at a time (hence, the vectype for purposes of determining the
2805 vectorization factor should be V8HI); on the other hand, the vectype that
2806 is used to create the vector form is actually V4SI (the type of the result).
2808 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2809 indicates what is the actual level of parallelism (V8HI in the example), so
2810 that the right vectorization factor would be derived. This vectype
2811 corresponds to the type of arguments to the reduction stmt, and should *NOT*
2812 be used to create the vectorized stmt. The right vectype for the vectorized
2813 stmt is obtained from the type of the result X:
2814 get_vectype_for_scalar_type (TREE_TYPE (X))
2816 This means that, contrary to "regular" reductions (or "regular" stmts in
2817 general), the following equation:
2818 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2819 does *NOT* necessarily hold for reduction patterns. */
2821 bool
2824 {
2825 tree vec_dest;
2826 tree scalar_dest;
2837 tree def;
2838 gimple def_stmt;
2841 tree scalar_type;
2843 gimple orig_stmt;
2844 stmt_vec_info orig_stmt_info;
2853 tree reduc_def;
2863 /* FORNOW: SLP not supported. */
2867 /* 1. Is vectorizable reduction? */
2869 /* Not supportable if the reduction variable is used in the loop. */
2873 /* Reductions that are not used even in an enclosing outer-loop,
2874 are expected to be "live" (used out of the loop). */
2879 /* Make sure it was already recognized as a reduction computation. */
2883 /* 2. Has this been recognized as a reduction pattern?
2885 Check if STMT represents a pattern that has been recognized
2886 in earlier analysis stages. For stmts that represent a pattern,
2887 the STMT_VINFO_RELATED_STMT field records the last stmt in
2888 the original sequence that constitutes the pattern. */
2892 {
2897 }
2899 /* 3. Check the operands of the operation. The first operands are defined
2900 inside the loop body. The last operand is the reduction variable,
2901 which is defined by the loop-header-phi. */
2905 /* Flatten RHS */
2907 {
2911 {
2917 }
2918 else
2935 }
2943 /* All uses but the last are expected to be defined in the loop.
2944 The last use is the reduction variable. */
2946 {
2955 }
2963 else
2969 /* 4. Supportable by target? */
2971 /* 4.1. check support for the operation in the loop */
2974 {
2978 }
2981 {
2990 }
2992 /* Worthwhile without SIMD support? */
2996 {
3000 }
3002 /* 4.2. Check support for the epilog operation.
3004 If STMT represents a reduction pattern, then the type of the
3005 reduction variable may be different than the type of the rest
3006 of the arguments. For example, consider the case of accumulation
3007 of shorts into an int accumulator; The original code:
3008 S1: int_a = (int) short_a;
3009 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
3011 was replaced with:
3012 STMT: int_acc = widen_sum <short_a, int_acc>
3014 This means that:
3015 1. The tree-code that is used to create the vector operation in the
3016 epilog code (that reduces the partial results) is not the
3017 tree-code of STMT, but is rather the tree-code of the original
3018 stmt from the pattern that STMT is replacing. I.e, in the example
3019 above we want to use 'widen_sum' in the loop, but 'plus' in the
3020 epilog.
3021 2. The type (mode) we use to check available target support
3022 for the vector operation to be created in the *epilog*, is
3023 determined by the type of the reduction variable (in the example
3024 above we'd check this: plus_optab[vect_int_mode]).
3025 However the type (mode) we use to check available target support
3026 for the vector operation to be created *inside the loop*, is
3027 determined by the type of the other arguments to STMT (in the
3028 example we'd check this: widen_sum_optab[vect_short_mode]).
3030 This is contrary to "regular" reductions, in which the types of all
3031 the arguments are the same as the type of the reduction variable.
3032 For "regular" reductions we can therefore use the same vector type
3033 (and also the same tree-code) when generating the epilog code and
3034 when generating the code inside the loop. */
3037 {
3038 /* This is a reduction pattern: get the vectype from the type of the
3039 reduction variable, and get the tree-code from orig_stmt. */
3043 {
3045 {
3048 }
3050 }
3053 }
3054 else
3055 {
3056 /* Regular reduction: use the same vectype and tree-code as used for
3057 the vector code inside the loop can be used for the epilog code. */
3059 }
3065 {
3069 }
3071 {
3075 }
3078 {
3083 }
3085 /** Transform. **/
3090 /* Create the destination vector */
3093 /* In case the vectorization factor (VF) is bigger than the number
3094 of elements that we can fit in a vectype (nunits), we have to generate
3095 more than one vector stmt - i.e - we need to "unroll" the
3096 vector stmt by a factor VF/nunits. For more details see documentation
3097 in vectorizable_operation. */
3099 /* If the reduction is used in an outer loop we need to generate
3100 VF intermediate results, like so (e.g. for ncopies=2):
3101 r0 = phi (init, r0)
3102 r1 = phi (init, r1)
3103 r0 = x0 + r0;
3104 r1 = x1 + r1;
3105 (i.e. we generate VF results in 2 registers).
3106 In this case we have a separate def-use cycle for each copy, and therefore
3107 for each copy we get the vector def for the reduction variable from the
3108 respective phi node created for this copy.
3110 Otherwise (the reduction is unused in the loop nest), we can combine
3111 together intermediate results, like so (e.g. for ncopies=2):
3112 r = phi (init, r)
3113 r = x0 + r;
3114 r = x1 + r;
3115 (i.e. we generate VF/2 results in a single register).
3116 In this case for each copy we get the vector def for the reduction variable
3117 from the vectorized reduction operation generated in the previous iteration.
3118 */
3121 {
3124 }
3125 else
3131 {
3133 {
3134 /* Create the reduction-phi that defines the reduction-operand. */
3137 }
3139 /* Handle uses. */
3141 {
3144 {
3146 }
3148 /* Get the vector def for the reduction variable from the phi node */
3151 }
3152 else
3153 {
3161 else
3165 }
3167 /* Arguments are ready. create the new vector stmt. */
3170 else
3172 reduc_def);
3180 else
3184 }
3186 /* Finalize the reduction-phi (set its arguments) and create the
3187 epilog reduction code. */
3193 }
3195 /* Checks if CALL can be vectorized in type VECTYPE. Returns
3196 a function declaration if the target has a vectorized version
3197 of the function, or NULL_TREE if the function cannot be vectorized. */
3199 tree
3201 {
3205 /* We only handle functions that do not read or clobber memory -- i.e.
3206 const or novops ones. */
3217 vectype_in);
3218 }
3220 /* Function vectorizable_call.
3222 Check if STMT performs a function call that can be vectorized.
3223 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3224 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3225 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3227 bool
3229 {
3230 tree vec_dest;
3231 tree scalar_dest;
3240 gimple def_stmt;
3242 gimple new_stmt;
3254 /* FORNOW: SLP not supported. */
3258 /* Is STMT a vectorizable call? */
3265 /* Process function arguments. */
3269 /* Bail out if the function has more than two arguments, we
3270 do not have interesting builtin functions to vectorize with
3271 more than two arguments. No arguments is also not good. */
3276 {
3279 /* We can only handle calls with arguments of the same type. */
3282 {
3286 }
3290 {
3294 }
3295 }
3308 /* FORNOW */
3315 else
3318 /* For now, we only vectorize functions if a target specific builtin
3319 is available. TODO -- in some cases, it might be profitable to
3320 insert the calls for pieces of the vector, in order to be able
3321 to vectorize other operations in the loop. */
3324 {
3329 }
3335 else
3338 /* Sanity check: make sure that at least one copy of the vectorized stmt
3339 needs to be generated. */
3343 {
3349 }
3351 /** Transform. **/
3356 /* Handle def. */
3362 {
3365 {
3366 /* Build argument list for the vectorized call. */
3369 else
3373 {
3376 vec_oprnd0
3378 else
3379 vec_oprnd0
3383 }
3393 else
3397 }
3403 {
3404 /* Build argument list for the vectorized call. */
3407 else
3411 {
3414 {
3415 vec_oprnd0
3417 vec_oprnd1
3419 }
3420 else
3421 {
3422 vec_oprnd0
3424 vec_oprnd1
3426 }
3430 }
3440 else
3444 }
3451 /* No current target implements this case. */
3453 }
3457 /* The call in STMT might prevent it from being removed in dce.
3458 We however cannot remove it here, due to the way the ssa name
3459 it defines is mapped to the new definition. So just replace
3460 rhs of the statement with something harmless. */
3472 }
3475 /* Function vect_gen_widened_results_half
3477 Create a vector stmt whose code, type, number of arguments, and result
3478 variable are CODE, OP_TYPE, and VEC_DEST, and its arguments are
3479 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
3480 In the case that CODE is a CALL_EXPR, this means that a call to DECL
3481 needs to be created (DECL is a function-decl of a target-builtin).
3482 STMT is the original scalar stmt that we are vectorizing. */
3484 static gimple
3486 tree decl,
3489 gimple stmt)
3490 {
3491 gimple new_stmt;
3492 tree new_temp;
3493 tree sym;
3494 ssa_op_iter iter;
3496 /* Generate half of the widened result: */
3498 {
3499 /* Target specific support */
3502 else
3506 }
3507 else
3508 {
3509 /* Generic support */
3514 vec_oprnd1);
3517 }
3521 {
3523 {
3527 }
3528 }
3531 }
3534 /* Check if STMT performs a conversion operation, that can be vectorized.
3535 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3536 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3537 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3539 bool
3542 {
3543 tree vec_dest;
3544 tree scalar_dest;
3545 tree op0;
3551 tree new_temp;
3552 tree def;
3553 gimple def_stmt;
3556 stmt_vec_info prev_stmt_info;
3561 tree expr;
3563 tree builtin_decl;
3567 tree vop0;
3568 tree integral_type;
3572 /* Is STMT a vectorizable conversion? */
3590 /* Check types of lhs and rhs. */
3605 /* FORNOW */
3612 else
3618 /* Bail out if the types are both integral or non-integral. */
3627 else
3630 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3631 this, so we can safely override NCOPIES with 1 here. */
3635 /* Sanity check: make sure that at least one copy of the vectorized stmt
3636 needs to be generated. */
3639 /* Check the operands of the operation. */
3641 {
3645 }
3647 /* Supportable by target? */
3658 {
3662 }
3665 {
3667 /* FORNOW: SLP not supported. */
3670 }
3673 {
3676 }
3678 /** Transform. **/
3682 /* Handle def. */
3690 {
3693 {
3694 tree sym;
3695 ssa_op_iter iter;
3699 else
3702 builtin_decl =
3705 {
3706 /* Arguments are ready. create the new vector stmt. */
3712 SSA_OP_ALL_VIRTUALS)
3713 {
3717 }
3720 }
3724 else
3727 }
3731 /* In case the vectorization factor (VF) is bigger than the number
3732 of elements that we can fit in a vectype (nunits), we have to
3733 generate more than one vector stmt - i.e - we need to "unroll"
3734 the vector stmt by a factor VF/nunits. */
3736 {
3739 else
3744 /* Generate first half of the widened result: */
3745 new_stmt
3751 else
3755 /* Generate second half of the widened result: */
3756 new_stmt
3762 }
3766 /* In case the vectorization factor (VF) is bigger than the number
3767 of elements that we can fit in a vectype (nunits), we have to
3768 generate more than one vector stmt - i.e - we need to "unroll"
3769 the vector stmt by a factor VF/nunits. */
3771 {
3772 /* Handle uses. */
3774 {
3777 }
3778 else
3779 {
3782 }
3784 /* Arguments are ready. Create the new vector stmt. */
3787 vec_oprnd1);
3794 else
3798 }
3801 }
3807 }
3810 /* Function vectorizable_assignment.
3812 Check if STMT performs an assignment (copy) that can be vectorized.
3813 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3814 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3815 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3817 bool
3820 {
3821 tree vec_dest;
3822 tree scalar_dest;
3823 tree op;
3827 tree new_temp;
3828 tree def;
3829 gimple def_stmt;
3835 tree vop;
3837 /* Multiple types in SLP are handled by creating the appropriate number of
3838 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
3839 case of SLP. */
3842 else
3855 /* Is vectorizable assignment? */
3866 else
3870 {
3874 }
3877 {
3883 }
3885 /** Transform. **/
3889 /* Handle def. */
3892 /* Handle use. */
3895 /* Arguments are ready. create the new vector stmt. */
3897 {
3906 }
3910 }
3913 /* Function vect_min_worthwhile_factor.
3915 For a loop where we could vectorize the operation indicated by CODE,
3916 return the minimum vectorization factor that makes it worthwhile
3917 to use generic vectors. */
3918 static int
3920 {
3922 {
3936 }
3937 }
3940 /* Function vectorizable_induction
3942 Check if PHI performs an induction computation that can be vectorized.
3943 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3944 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3945 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3947 bool
3950 {
3957 tree vec_def;
3960 /* FORNOW. This restriction should be relaxed. */
3962 {
3966 }
3971 /* FORNOW: SLP not supported. */
3981 {
3987 }
3989 /** Transform. **/
3997 }
4000 /* Function vectorizable_operation.
4002 Check if STMT performs a binary or unary operation that can be vectorized.
4003 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4004 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4005 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4007 bool
4010 {
4011 tree vec_dest;
4012 tree scalar_dest;
4020 tree new_temp;
4022 optab optab;
4025 tree def;
4026 gimple def_stmt;
4029 stmt_vec_info prev_stmt_info;
4032 tree vectype_out;
4041 /* Multiple types in SLP are handled by creating the appropriate number of
4042 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4043 case of SLP. */
4046 else
4057 /* Is STMT a vectorizable binary/unary operation? */
4074 /* For pointer addition, we should use the normal plus for
4075 the vector addition. */
4079 /* Support only unary or binary operations. */
4082 {
4086 }
4090 {
4094 }
4097 {
4100 {
4104 }
4105 }
4107 /* If this is a shift/rotate, determine whether the shift amount is a vector,
4108 or scalar. If the shift/rotate amount is a vector, use the vector/vector
4109 shift optabs. */
4112 {
4115 /* vector shifted by vector */
4117 {
4121 }
4123 /* See if the machine has a vector shifted by scalar insn and if not
4124 then see if it has a vector shifted by vector insn */
4126 {
4131 {
4135 }
4136 else
4137 {
4140 && optab
4144 }
4145 }
4147 else
4148 {
4152 }
4153 }
4154 else
4157 /* Supportable by target? */
4159 {
4163 }
4167 {
4170 /* Check only during analysis. */
4178 }
4180 /* Worthwhile without SIMD support? Check only during analysis. */
4185 {
4189 }
4192 {
4198 }
4200 /** Transform. **/
4205 /* Handle def. */
4208 /* Allocate VECs for vector operands. In case of SLP, vector operands are
4209 created in the previous stages of the recursion, so no allocation is
4210 needed, except for the case of shift with scalar shift argument. In that
4211 case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
4212 be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
4213 In case of loop-based vectorization we allocate VECs of size 1. We
4214 allocate VEC_OPRNDS1 only in case of binary operation. */
4216 {
4220 }
4224 /* In case the vectorization factor (VF) is bigger than the number
4225 of elements that we can fit in a vectype (nunits), we have to generate
4226 more than one vector stmt - i.e - we need to "unroll" the
4227 vector stmt by a factor VF/nunits. In doing so, we record a pointer
4228 from one copy of the vector stmt to the next, in the field
4229 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
4230 stages to find the correct vector defs to be used when vectorizing
4231 stmts that use the defs of the current stmt. The example below illustrates
4232 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
4233 4 vectorized stmts):
4235 before vectorization:
4236 RELATED_STMT VEC_STMT
4237 S1: x = memref - -
4238 S2: z = x + 1 - -
4240 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
4241 there):
4242 RELATED_STMT VEC_STMT
4243 VS1_0: vx0 = memref0 VS1_1 -
4244 VS1_1: vx1 = memref1 VS1_2 -
4245 VS1_2: vx2 = memref2 VS1_3 -
4246 VS1_3: vx3 = memref3 - -
4247 S1: x = load - VS1_0
4248 S2: z = x + 1 - -
4250 step2: vectorize stmt S2 (done here):
4251 To vectorize stmt S2 we first need to find the relevant vector
4252 def for the first operand 'x'. This is, as usual, obtained from
4253 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
4254 that defines 'x' (S1). This way we find the stmt VS1_0, and the
4255 relevant vector def 'vx0'. Having found 'vx0' we can generate
4256 the vector stmt VS2_0, and as usual, record it in the
4257 STMT_VINFO_VEC_STMT of stmt S2.
4258 When creating the second copy (VS2_1), we obtain the relevant vector
4259 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
4260 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
4261 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
4262 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
4263 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
4264 chain of stmts and pointers:
4265 RELATED_STMT VEC_STMT
4266 VS1_0: vx0 = memref0 VS1_1 -
4267 VS1_1: vx1 = memref1 VS1_2 -
4268 VS1_2: vx2 = memref2 VS1_3 -
4269 VS1_3: vx3 = memref3 - -
4270 S1: x = load - VS1_0
4271 VS2_0: vz0 = vx0 + v1 VS2_1 -
4272 VS2_1: vz1 = vx1 + v1 VS2_2 -
4273 VS2_2: vz2 = vx2 + v1 VS2_3 -
4274 VS2_3: vz3 = vx3 + v1 - -
4275 S2: z = x + 1 - VS2_0 */
4279 {
4280 /* Handle uses. */
4282 {
4284 {
4285 /* Vector shl and shr insn patterns can be defined with scalar
4286 operand 2 (shift operand). In this case, use constant or loop
4287 invariant op1 directly, without extending it to vector mode
4288 first. */
4291 {
4297 {
4298 /* Store vec_oprnd1 for every vector stmt to be created
4299 for SLP_NODE. We check during the analysis that all the
4300 shift arguments are the same.
4301 TODO: Allow different constants for different vector
4302 stmts generated for an SLP instance. */
4305 }
4306 }
4307 }
4309 /* vec_oprnd1 is available if operand 1 should be of a scalar-type
4310 (a special case for certain kind of vector shifts); otherwise,
4311 operand 1 should be of a vector type (the usual case). */
4314 slp_node);
4315 else
4317 slp_node);
4318 }
4319 else
4322 /* Arguments are ready. Create the new vector stmt. */
4324 {
4333 }
4340 else
4343 }
4350 }
4353 /* Get vectorized definitions for loop-based vectorization. For the first
4354 operand we call vect_get_vec_def_for_operand() (with OPRND containing
4355 scalar operand), and for the rest we get a copy with
4356 vect_get_vec_def_for_stmt_copy() using the previous vector definition
4357 (stored in OPRND). See vect_get_vec_def_for_stmt_copy() for details.
4358 The vectors are collected into VEC_OPRNDS. */
4360 static void
4363 {
4364 tree vec_oprnd;
4366 /* Get first vector operand. */
4367 /* All the vector operands except the very first one (that is scalar oprnd)
4368 are stmt copies. */
4371 else
4376 /* Get second vector operand. */
4382 /* For conversion in multiple steps, continue to get operands
4383 recursively. */
4386 }
4389 /* Create vectorized demotion statements for vector operands from VEC_OPRNDS.
4390 For multi-step conversions store the resulting vectors and call the function
4391 recursively. */
4393 static void
4400 {
4403 gimple new_stmt;
4409 {
4410 /* Create demotion operation. */
4419 /* Store the resulting vector for next recursive call. */
4421 else
4422 {
4423 /* This is the last step of the conversion sequence. Store the
4424 vectors in SLP_NODE or in vector info of the scalar statement
4425 (or in STMT_VINFO_RELATED_STMT chain). */
4428 else
4429 {
4432 else
4436 }
4437 }
4438 }
4440 /* For multi-step demotion operations we first generate demotion operations
4441 from the source type to the intermediate types, and then combine the
4442 results (stored in VEC_OPRNDS) in demotion operation to the destination
4443 type. */
4445 {
4446 /* At each level of recursion we have have of the operands we had at the
4447 previous level. */
4452 }
4453 }
4456 /* Function vectorizable_type_demotion
4458 Check if STMT performs a binary or unary operation that involves
4459 type demotion, and if it can be vectorized.
4460 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4461 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4462 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4464 bool
4467 {
4468 tree vec_dest;
4469 tree scalar_dest;
4470 tree op0;
4474 tree def;
4475 gimple def_stmt;
4477 stmt_vec_info prev_stmt_info;
4480 tree vectype_out;
4483 tree vectype_in;
4495 /* Is STMT a vectorizable type-demotion operation? */
4520 /* Multiple types in SLP are handled by creating the appropriate number of
4521 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4522 case of SLP. */
4525 else
4537 /* Check the operands of the operation. */
4539 {
4543 }
4545 /* Supportable by target? */
4553 {
4559 }
4561 /** Transform. **/
4564 ncopies);
4566 /* In case of multi-step demotion, we first generate demotion operations to
4567 the intermediate types, and then from that types to the final one.
4568 We create vector destinations for the intermediate type (TYPES) received
4569 from supportable_narrowing_operation, and store them in the correct order
4570 for future use in vect_create_vectorized_demotion_stmts(). */
4573 else
4580 {
4583 {
4585 intermediate_type);
4587 }
4588 }
4590 /* In case the vectorization factor (VF) is bigger than the number
4591 of elements that we can fit in a vectype (nunits), we have to generate
4592 more than one vector stmt - i.e - we need to "unroll" the
4593 vector stmt by a factor VF/nunits. */
4597 {
4598 /* Handle uses. */
4601 else
4602 {
4608 }
4610 /* Arguments are ready. Create the new vector stmts. */
4616 }
4625 }
4628 /* Create vectorized promotion statements for vector operands from VEC_OPRNDS0
4629 and VEC_OPRNDS1 (for binary operations). For multi-step conversions store
4630 the resulting vectors and call the function recursively. */
4632 static void
4642 {
4653 {
4656 else
4659 /* Generate the two halves of promotion operation. */
4665 {
4668 }
4669 else
4670 {
4673 }
4676 {
4677 /* Store the results for the recursive call. */
4680 }
4681 else
4682 {
4683 /* Last step of promotion sequience - store the results. */
4685 {
4688 }
4689 else
4690 {
4693 else
4699 }
4700 }
4701 }
4704 {
4705 /* For multi-step promotion operation we first generate we call the
4706 function recurcively for every stage. We start from the input type,
4707 create promotion operations to the intermediate types, and then
4708 create promotions to the output type. */
4715 prev_stmt_info);
4716 }
4717 }
4720 /* Function vectorizable_type_promotion
4722 Check if STMT performs a binary or unary operation that involves
4723 type promotion, and if it can be vectorized.
4724 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4725 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4726 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4728 bool
4731 {
4732 tree vec_dest;
4733 tree scalar_dest;
4741 tree def;
4742 gimple def_stmt;
4744 stmt_vec_info prev_stmt_info;
4747 tree vectype_out;
4750 tree vectype_in;
4762 /* Is STMT a vectorizable type-promotion operation? */
4788 /* Multiple types in SLP are handled by creating the appropriate number of
4789 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4790 case of SLP. */
4793 else
4805 /* Check the operands of the operation. */
4807 {
4811 }
4815 {
4818 {
4822 }
4823 }
4825 /* Supportable by target? */
4831 /* Binary widening operation can only be supported directly by the
4832 architecture. */
4838 {
4844 }
4846 /** Transform. **/
4850 ncopies);
4852 /* Handle def. */
4853 /* In case of multi-step promotion, we first generate promotion operations
4854 to the intermediate types, and then from that types to the final one.
4855 We store vector destination in VEC_DSTS in the correct order for
4856 recursive creation of promotion operations in
4857 vect_create_vectorized_promotion_stmts(). Vector destinations are created
4858 according to TYPES recieved from supportable_widening_operation(). */
4861 else
4868 {
4871 {
4873 intermediate_type);
4875 }
4876 }
4879 {
4884 }
4886 /* In case the vectorization factor (VF) is bigger than the number
4887 of elements that we can fit in a vectype (nunits), we have to generate
4888 more than one vector stmt - i.e - we need to "unroll" the
4889 vector stmt by a factor VF/nunits. */
4893 {
4894 /* Handle uses. */
4896 {
4899 else
4900 {
4904 {
4907 }
4908 }
4909 }
4910 else
4911 {
4915 {
4918 }
4919 }
4921 /* Arguments are ready. Create the new vector stmts. */
4925 tmp_vec_dsts,
4929 }
4939 }
4942 /* Function vect_strided_store_supported.
4944 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
4945 and FALSE otherwise. */
4947 static bool
4949 {
4955 /* Check that the operation is supported. */
4961 {
4965 }
4968 == CODE_FOR_nothing
4971 {
4975 }
4978 }
4981 /* Function vect_permute_store_chain.
4983 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4984 a power of 2, generate interleave_high/low stmts to reorder the data
4985 correctly for the stores. Return the final references for stores in
4986 RESULT_CHAIN.
4988 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4989 The input is 4 vectors each containing 8 elements. We assign a number to each
4990 element, the input sequence is:
4992 1st vec: 0 1 2 3 4 5 6 7
4993 2nd vec: 8 9 10 11 12 13 14 15
4994 3rd vec: 16 17 18 19 20 21 22 23
4995 4th vec: 24 25 26 27 28 29 30 31
4997 The output sequence should be:
4999 1st vec: 0 8 16 24 1 9 17 25
5000 2nd vec: 2 10 18 26 3 11 19 27
5001 3rd vec: 4 12 20 28 5 13 21 30
5002 4th vec: 6 14 22 30 7 15 23 31
5004 i.e., we interleave the contents of the four vectors in their order.
5006 We use interleave_high/low instructions to create such output. The input of
5007 each interleave_high/low operation is two vectors:
5008 1st vec 2nd vec
5009 0 1 2 3 4 5 6 7
5010 the even elements of the result vector are obtained left-to-right from the
5011 high/low elements of the first vector. The odd elements of the result are
5012 obtained left-to-right from the high/low elements of the second vector.
5013 The output of interleave_high will be: 0 4 1 5
5014 and of interleave_low: 2 6 3 7
5017 The permutation is done in log LENGTH stages. In each stage interleave_high
5018 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
5019 where the first argument is taken from the first half of DR_CHAIN and the
5020 second argument from it's second half.
5021 In our example,
5023 I1: interleave_high (1st vec, 3rd vec)
5024 I2: interleave_low (1st vec, 3rd vec)
5025 I3: interleave_high (2nd vec, 4th vec)
5026 I4: interleave_low (2nd vec, 4th vec)
5028 The output for the first stage is:
5030 I1: 0 16 1 17 2 18 3 19
5031 I2: 4 20 5 21 6 22 7 23
5032 I3: 8 24 9 25 10 26 11 27
5033 I4: 12 28 13 29 14 30 15 31
5035 The output of the second stage, i.e. the final result is:
5037 I1: 0 8 16 24 1 9 17 25
5038 I2: 2 10 18 26 3 11 19 27
5039 I3: 4 12 20 28 5 13 21 30
5040 I4: 6 14 22 30 7 15 23 31. */
5042 static bool
5045 gimple stmt,
5048 {
5050 gimple perm_stmt;
5052 tree scalar_dest;
5059 /* Check that the operation is supported. */
5066 {
5068 {
5072 /* Create interleaving stmt:
5073 in the case of big endian:
5074 high = interleave_high (vect1, vect2)
5075 and in the case of little endian:
5076 high = interleave_low (vect1, vect2). */
5081 {
5084 }
5085 else
5086 {
5089 }
5097 /* Create interleaving stmt:
5098 in the case of big endian:
5099 low = interleave_low (vect1, vect2)
5100 and in the case of little endian:
5101 low = interleave_high (vect1, vect2). */
5111 }
5113 }
5115 }
5118 /* Function vectorizable_store.
5120 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
5121 can be vectorized.
5122 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5123 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5124 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5126 bool
5128 slp_tree slp_node)
5129 {
5130 tree scalar_dest;
5131 tree data_ref;
5132 tree op;
5140 tree dummy;
5142 tree def;
5143 gimple def_stmt;
5157 stmt_vec_info first_stmt_vinfo;
5160 /* Multiple types in SLP are handled by creating the appropriate number of
5161 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
5162 case of SLP. */
5165 else
5170 /* FORNOW. This restriction should be relaxed. */
5172 {
5176 }
5184 /* Is vectorizable store? */
5198 {
5202 }
5204 /* The scalar rhs type needs to be trivially convertible to the vector
5205 component type. This should always be the case. */
5207 {
5211 }
5214 /* FORNOW. In some cases can vectorize even if data-type not supported
5215 (e.g. - array initialization with 0). */
5223 {
5231 {
5232 /* STMT is the leader of the group. Check the operands of all the
5233 stmts of the group. */
5236 {
5240 {
5244 }
5246 }
5247 }
5248 }
5251 {
5255 }
5257 /** Transform. **/
5260 {
5266 /* FORNOW */
5269 /* We vectorize all the stmts of the interleaving group when we
5270 reach the last stmt in the group. */
5274 {
5277 }
5282 /* VEC_NUM is the number of vect stmts to be created for this group. */
5285 else
5287 }
5288 else
5289 {
5294 }
5306 /* In case the vectorization factor (VF) is bigger than the number
5307 of elements that we can fit in a vectype (nunits), we have to generate
5308 more than one vector stmt - i.e - we need to "unroll" the
5309 vector stmt by a factor VF/nunits. For more details see documentation in
5310 vect_get_vec_def_for_copy_stmt. */
5312 /* In case of interleaving (non-unit strided access):
5314 S1: &base + 2 = x2
5315 S2: &base = x0
5316 S3: &base + 1 = x1
5317 S4: &base + 3 = x3
5319 We create vectorized stores starting from base address (the access of the
5320 first stmt in the chain (S2 in the above example), when the last store stmt
5321 of the chain (S4) is reached:
5323 VS1: &base = vx2
5324 VS2: &base + vec_size*1 = vx0
5325 VS3: &base + vec_size*2 = vx1
5326 VS4: &base + vec_size*3 = vx3
5328 Then permutation statements are generated:
5330 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
5331 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
5332 ...
5334 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
5335 (the order of the data-refs in the output of vect_permute_store_chain
5336 corresponds to the order of scalar stmts in the interleaving chain - see
5337 the documentation of vect_permute_store_chain()).
5339 In case of both multiple types and interleaving, above vector stores and
5340 permutation stmts are created for every copy. The result vector stmts are
5341 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
5342 STMT_VINFO_RELATED_STMT for the next copies.
5343 */
5347 {
5348 gimple new_stmt;
5349 gimple ptr_incr;
5352 {
5354 {
5355 /* Get vectorized arguments for SLP_NODE. */
5359 }
5360 else
5361 {
5362 /* For interleaved stores we collect vectorized defs for all the
5363 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
5364 used as an input to vect_permute_store_chain(), and OPRNDS as
5365 an input to vect_get_vec_def_for_stmt_copy() for the next copy.
5367 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
5368 OPRNDS are of size 1. */
5371 {
5372 /* Since gaps are not supported for interleaved stores,
5373 GROUP_SIZE is the exact number of stmts in the chain.
5374 Therefore, NEXT_STMT can't be NULL_TREE. In case that
5375 there is no interleaving, GROUP_SIZE is 1, and only one
5376 iteration of the loop will be executed. */
5382 NULL);
5386 }
5387 }
5389 /* We should have catched mismatched types earlier. */
5396 }
5397 else
5398 {
5399 /* For interleaved stores we created vectorized defs for all the
5400 defs stored in OPRNDS in the previous iteration (previous copy).
5401 DR_CHAIN is then used as an input to vect_permute_store_chain(),
5402 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
5403 next copy.
5404 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
5405 OPRNDS are of size 1. */
5407 {
5413 }
5414 dataref_ptr =
5416 }
5419 {
5421 /* Permute. */
5425 }
5429 {
5431 /* Bump the vector pointer. */
5433 NULL_TREE);
5438 /* For strided stores vectorized defs are interleaved in
5439 vect_permute_store_chain(). */
5444 /* Arguments are ready. Create the new vector stmt. */
5454 else
5461 }
5462 }
5470 }
5473 /* Function vect_setup_realignment
5475 This function is called when vectorizing an unaligned load using
5476 the dr_explicit_realign[_optimized] scheme.
5477 This function generates the following code at the loop prolog:
5479 p = initial_addr;
5480 x msq_init = *(floor(p)); # prolog load
5481 realignment_token = call target_builtin;
5482 loop:
5483 x msq = phi (msq_init, ---)
5485 The stmts marked with x are generated only for the case of
5486 dr_explicit_realign_optimized.
5488 The code above sets up a new (vector) pointer, pointing to the first
5489 location accessed by STMT, and a "floor-aligned" load using that pointer.
5490 It also generates code to compute the "realignment-token" (if the relevant
5491 target hook was defined), and creates a phi-node at the loop-header bb
5492 whose arguments are the result of the prolog-load (created by this
5493 function) and the result of a load that takes place in the loop (to be
5494 created by the caller to this function).
5496 For the case of dr_explicit_realign_optimized:
5497 The caller to this function uses the phi-result (msq) to create the
5498 realignment code inside the loop, and sets up the missing phi argument,
5499 as follows:
5500 loop:
5501 msq = phi (msq_init, lsq)
5502 lsq = *(floor(p')); # load in loop
5503 result = realign_load (msq, lsq, realignment_token);
5505 For the case of dr_explicit_realign:
5506 loop:
5507 msq = *(floor(p)); # load in loop
5508 p' = p + (VS-1);
5509 lsq = *(floor(p')); # load in loop
5510 result = realign_load (msq, lsq, realignment_token);
5512 Input:
5513 STMT - (scalar) load stmt to be vectorized. This load accesses
5514 a memory location that may be unaligned.
5515 BSI - place where new code is to be inserted.
5516 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
5517 is used.
5519 Output:
5520 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
5521 target hook, if defined.
5522 Return value - the result of the loop-header phi node. */
5524 static tree
5528 tree init_addr,
5530 {
5535 edge pe;
5537 tree vec_dest;
5538 gimple inc;
5539 tree ptr;
5540 tree data_ref;
5541 gimple new_stmt;
5542 basic_block new_bb;
5544 tree new_temp;
5545 gimple phi_stmt;
5557 /* We need to generate three things:
5558 1. the misalignment computation
5559 2. the extra vector load (for the optimized realignment scheme).
5560 3. the phi node for the two vectors from which the realignment is
5561 done (for the optimized realignment scheme).
5562 */
5564 /* 1. Determine where to generate the misalignment computation.
5566 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
5567 calculation will be generated by this function, outside the loop (in the
5568 preheader). Otherwise, INIT_ADDR had already been computed for us by the
5569 caller, inside the loop.
5571 Background: If the misalignment remains fixed throughout the iterations of
5572 the loop, then both realignment schemes are applicable, and also the
5573 misalignment computation can be done outside LOOP. This is because we are
5574 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
5575 are a multiple of VS (the Vector Size), and therefore the misalignment in
5576 different vectorized LOOP iterations is always the same.
5577 The problem arises only if the memory access is in an inner-loop nested
5578 inside LOOP, which is now being vectorized using outer-loop vectorization.
5579 This is the only case when the misalignment of the memory access may not
5580 remain fixed throughout the iterations of the inner-loop (as explained in
5581 detail in vect_supportable_dr_alignment). In this case, not only is the
5582 optimized realignment scheme not applicable, but also the misalignment
5583 computation (and generation of the realignment token that is passed to
5584 REALIGN_LOAD) have to be done inside the loop.
5586 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
5587 or not, which in turn determines if the misalignment is computed inside
5588 the inner-loop, or outside LOOP. */
5591 {
5594 }
5597 /* 2. Determine where to generate the extra vector load.
5599 For the optimized realignment scheme, instead of generating two vector
5600 loads in each iteration, we generate a single extra vector load in the
5601 preheader of the loop, and in each iteration reuse the result of the
5602 vector load from the previous iteration. In case the memory access is in
5603 an inner-loop nested inside LOOP, which is now being vectorized using
5604 outer-loop vectorization, we need to determine whether this initial vector
5605 load should be generated at the preheader of the inner-loop, or can be
5606 generated at the preheader of LOOP. If the memory access has no evolution
5607 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
5608 to be generated inside LOOP (in the preheader of the inner-loop). */
5611 {
5616 }
5617 else
5622 /* 3. For the case of the optimized realignment, create the first vector
5623 load at the loop preheader. */
5626 {
5627 /* Create msq_init = *(floor(p1)) in the loop preheader */
5642 }
5644 /* 4. Create realignment token using a target builtin, if available.
5645 It is done either inside the containing loop, or before LOOP (as
5646 determined above). */
5649 {
5650 tree builtin_decl;
5652 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
5655 else
5656 {
5657 /* Generate the INIT_ADDR computation outside LOOP. */
5663 }
5667 vec_dest =
5675 else
5676 {
5677 /* Generate the misalignment computation outside LOOP. */
5681 }
5685 /* The result of the CALL_EXPR to this builtin is determined from
5686 the value of the parameter and no global variables are touched
5687 which makes the builtin a "const" function. Requiring the
5688 builtin to have the "const" attribute makes it unnecessary
5689 to call mark_call_clobbered. */
5691 }
5700 /* 5. Create msq = phi <msq_init, lsq> in loop */
5710 }
5713 /* Function vect_strided_load_supported.
5715 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
5716 and FALSE otherwise. */
5718 static bool
5720 {
5727 optab_default);
5729 {
5733 }
5736 {
5740 }
5743 optab_default);
5745 {
5749 }
5752 {
5756 }
5758 }
5761 /* Function vect_permute_load_chain.
5763 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
5764 a power of 2, generate extract_even/odd stmts to reorder the input data
5765 correctly. Return the final references for loads in RESULT_CHAIN.
5767 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
5768 The input is 4 vectors each containing 8 elements. We assign a number to each
5769 element, the input sequence is:
5771 1st vec: 0 1 2 3 4 5 6 7
5772 2nd vec: 8 9 10 11 12 13 14 15
5773 3rd vec: 16 17 18 19 20 21 22 23
5774 4th vec: 24 25 26 27 28 29 30 31
5776 The output sequence should be:
5778 1st vec: 0 4 8 12 16 20 24 28
5779 2nd vec: 1 5 9 13 17 21 25 29
5780 3rd vec: 2 6 10 14 18 22 26 30
5781 4th vec: 3 7 11 15 19 23 27 31
5783 i.e., the first output vector should contain the first elements of each
5784 interleaving group, etc.
5786 We use extract_even/odd instructions to create such output. The input of each
5787 extract_even/odd operation is two vectors
5788 1st vec 2nd vec
5789 0 1 2 3 4 5 6 7
5791 and the output is the vector of extracted even/odd elements. The output of
5792 extract_even will be: 0 2 4 6
5793 and of extract_odd: 1 3 5 7
5796 The permutation is done in log LENGTH stages. In each stage extract_even and
5797 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
5798 order. In our example,
5800 E1: extract_even (1st vec, 2nd vec)
5801 E2: extract_odd (1st vec, 2nd vec)
5802 E3: extract_even (3rd vec, 4th vec)
5803 E4: extract_odd (3rd vec, 4th vec)
5805 The output for the first stage will be:
5807 E1: 0 2 4 6 8 10 12 14
5808 E2: 1 3 5 7 9 11 13 15
5809 E3: 16 18 20 22 24 26 28 30
5810 E4: 17 19 21 23 25 27 29 31
5812 In order to proceed and create the correct sequence for the next stage (or
5813 for the correct output, if the second stage is the last one, as in our
5814 example), we first put the output of extract_even operation and then the
5815 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
5816 The input for the second stage is:
5818 1st vec (E1): 0 2 4 6 8 10 12 14
5819 2nd vec (E3): 16 18 20 22 24 26 28 30
5820 3rd vec (E2): 1 3 5 7 9 11 13 15
5821 4th vec (E4): 17 19 21 23 25 27 29 31
5823 The output of the second stage:
5825 E1: 0 4 8 12 16 20 24 28
5826 E2: 2 6 10 14 18 22 26 30
5827 E3: 1 5 9 13 17 21 25 29
5828 E4: 3 7 11 15 19 23 27 31
5830 And RESULT_CHAIN after reordering:
5832 1st vec (E1): 0 4 8 12 16 20 24 28
5833 2nd vec (E3): 1 5 9 13 17 21 25 29
5834 3rd vec (E2): 2 6 10 14 18 22 26 30
5835 4th vec (E4): 3 7 11 15 19 23 27 31. */
5837 static bool
5840 gimple stmt,
5843 {
5845 gimple perm_stmt;
5850 /* Check that the operation is supported. */
5856 {
5858 {
5862 /* data_ref = permute_even (first_data_ref, second_data_ref); */
5869 second_vect);
5878 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
5885 second_vect);
5892 }
5894 }
5896 }
5899 /* Function vect_transform_strided_load.
5901 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
5902 to perform their permutation and ascribe the result vectorized statements to
5903 the scalar statements.
5904 */
5906 static bool
5909 {
5915 tree tmp_data_ref;
5917 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
5918 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
5919 vectors, that are ready for vector computation. */
5921 /* Permute. */
5925 /* Put a permuted data-ref in the VECTORIZED_STMT field.
5926 Since we scan the chain starting from it's first node, their order
5927 corresponds the order of data-refs in RESULT_CHAIN. */
5931 {
5935 /* Skip the gaps. Loads created for the gaps will be removed by dead
5936 code elimination pass later. No need to check for the first stmt in
5937 the group, since it always exists.
5938 DR_GROUP_GAP is the number of steps in elements from the previous
5939 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
5940 correspond to the gaps.
5941 */
5944 {
5945 gap_count++;
5947 }
5950 {
5952 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
5953 copies, and we put the new vector statement in the first available
5954 RELATED_STMT. */
5957 else
5958 {
5960 {
5961 gimple prev_stmt =
5963 gimple rel_stmt =
5966 {
5968 rel_stmt =
5970 }
5973 new_stmt;
5974 }
5975 }
5979 /* If NEXT_STMT accesses the same DR as the previous statement,
5980 put the same TMP_DATA_REF as its vectorized statement; otherwise
5981 get the next data-ref from RESULT_CHAIN. */
5984 }
5985 }
5989 }
5992 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
5993 building a vector of type MASK_TYPE from it) and two input vectors placed in
5994 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
5995 shifting by STRIDE elements of DR_CHAIN for every copy.
5996 (STRIDE is the number of vectorized stmts for NODE divided by the number of
5997 copies).
5998 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
5999 the created stmts must be inserted. */
6010 {
6013 stmt_vec_info next_stmt_info;
6016 tree sym;
6017 ssa_op_iter iter;
6020 /* Create a vector mask. */
6023 t);
6031 /* Initialize the vect stmts of NODE to properly insert the generated
6032 stmts later. */
6039 {
6043 /* Build argument list for the vectorized call. */
6050 /* Generate the permute statement. */
6056 {
6060 }
6062 /* Store the vector statement in NODE. */
6068 }
6070 /* Mark the scalar stmt as vectorized. */
6073 }
6076 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
6077 return in CURRENT_MASK_ELEMENT its equivalent in target specific
6078 representation. Check that the mask is valid and return FALSE if not.
6079 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
6080 the next vector, i.e., the current first vector is not needed. */
6082 static bool
6087 {
6093 /* Convert to target specific representation. */
6095 /* Adjust the value in case it's a mask for second and third vectors. */
6101 /* We have only one input vector to permute but the mask accesses values in
6102 the next vector as well. */
6104 {
6106 {
6109 }
6112 }
6114 /* The mask requires the next vector. */
6116 {
6118 {
6119 /* We either need the first vector too or have already moved to the
6120 next vector. In both cases, this permutation needs three
6121 vectors. */
6123 {
6127 }
6130 }
6132 /* We move to the next vector, dropping the first one and working with
6133 the second and the third - we need to adjust the values of the mask
6134 accordingly. */
6142 }
6146 /* This was the last element of this mask. Start a new one. */
6148 {
6152 }
6155 }
6158 /* Generate vector permute statements from a list of loads in DR_CHAIN.
6159 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
6160 permute statements for SLP_NODE_INSTANCE. */
6161 bool
6165 {
6169 slp_tree node;
6171 gimple next_scalar_stmt;
6179 {
6181 {
6184 }
6187 }
6192 {
6194 {
6197 }
6200 }
6209 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
6210 unrolling factor. */
6216 /* Number of copies is determined by the final vectorization factor
6217 relatively to SLP_NODE_INSTANCE unrolling factor. */
6220 /* Generate permutation masks for every NODE. Number of masks for each NODE
6221 is equal to GROUP_SIZE.
6222 E.g., we have a group of three nodes with three loads from the same
6223 location in each node, and the vector size is 4. I.e., we have a
6224 a0b0c0a1b1c1... sequence and we need to create the following vectors:
6225 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
6226 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
6227 ...
6229 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9} (in target
6230 scpecific type, e.g., in bytes for Altivec.
6231 The last mask is illegal since we assume two operands for permute
6232 operation, and the mask element values can't be outside that range. Hence,
6233 the last mask must be converted into {2,5,5,5}.
6234 For the first two permutations we need the first and the second input
6235 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
6236 we need the second and the third vectors: {b1,c1,a2,b2} and
6237 {c2,a3,b3,c3}. */
6242 i++)
6243 {
6251 else
6255 {
6257 {
6260 {
6267 }
6270 {
6273 {
6275 {
6278 }
6287 vect_stmts_counter++);
6288 }
6289 }
6290 }
6291 }
6292 }
6296 }
6298 /* vectorizable_load.
6300 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
6301 can be vectorized.
6302 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
6303 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
6304 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6306 bool
6309 {
6310 tree scalar_dest;
6314 stmt_vec_info prev_stmt_info;
6321 tree new_temp;
6324 tree dummy;
6327 gimple ptr_incr;
6337 gimple first_stmt;
6338 tree scalar_type;
6347 /* Multiple types in SLP are handled by creating the appropriate number of
6348 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
6349 case of SLP. */
6352 else
6357 /* FORNOW. This restriction should be relaxed. */
6359 {
6363 }
6374 /* Is vectorizable load? */
6394 /* FORNOW. In some cases can vectorize even if data-type not supported
6395 (e.g. - data copies). */
6397 {
6401 }
6403 /* The vector component type needs to be trivially convertible to the
6404 scalar lhs. This should always be the case. */
6406 {
6410 }
6412 /* Check if the load is a part of an interleaving chain. */
6414 {
6416 /* FORNOW */
6419 /* Check if interleaving is supported. */
6423 }
6426 {
6430 }
6435 /** Transform. **/
6438 {
6440 /* Check if the chain of loads is already vectorized. */
6442 {
6445 }
6449 /* VEC_NUM is the number of vect stmts to be created for this group. */
6451 {
6454 }
6455 else
6459 }
6460 else
6461 {
6465 }
6470 /* In case the vectorization factor (VF) is bigger than the number
6471 of elements that we can fit in a vectype (nunits), we have to generate
6472 more than one vector stmt - i.e - we need to "unroll" the
6473 vector stmt by a factor VF/nunits. In doing so, we record a pointer
6474 from one copy of the vector stmt to the next, in the field
6475 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
6476 stages to find the correct vector defs to be used when vectorizing
6477 stmts that use the defs of the current stmt. The example below illustrates
6478 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
6479 4 vectorized stmts):
6481 before vectorization:
6482 RELATED_STMT VEC_STMT
6483 S1: x = memref - -
6484 S2: z = x + 1 - -
6486 step 1: vectorize stmt S1:
6487 We first create the vector stmt VS1_0, and, as usual, record a
6488 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
6489 Next, we create the vector stmt VS1_1, and record a pointer to
6490 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
6491 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
6492 stmts and pointers:
6493 RELATED_STMT VEC_STMT
6494 VS1_0: vx0 = memref0 VS1_1 -
6495 VS1_1: vx1 = memref1 VS1_2 -
6496 VS1_2: vx2 = memref2 VS1_3 -
6497 VS1_3: vx3 = memref3 - -
6498 S1: x = load - VS1_0
6499 S2: z = x + 1 - -
6501 See in documentation in vect_get_vec_def_for_stmt_copy for how the
6502 information we recorded in RELATED_STMT field is used to vectorize
6503 stmt S2. */
6505 /* In case of interleaving (non-unit strided access):
6507 S1: x2 = &base + 2
6508 S2: x0 = &base
6509 S3: x1 = &base + 1
6510 S4: x3 = &base + 3
6512 Vectorized loads are created in the order of memory accesses
6513 starting from the access of the first stmt of the chain:
6515 VS1: vx0 = &base
6516 VS2: vx1 = &base + vec_size*1
6517 VS3: vx3 = &base + vec_size*2
6518 VS4: vx4 = &base + vec_size*3
6520 Then permutation statements are generated:
6522 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
6523 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
6524 ...
6526 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
6527 (the order of the data-refs in the output of vect_permute_load_chain
6528 corresponds to the order of scalar stmts in the interleaving chain - see
6529 the documentation of vect_permute_load_chain()).
6530 The generation of permutation stmts and recording them in
6531 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
6533 In case of both multiple types and interleaving, the vector loads and
6534 permutation stmts above are created for every copy. The result vector stmts
6535 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
6536 STMT_VINFO_RELATED_STMT for the next copies. */
6538 /* If the data reference is aligned (dr_aligned) or potentially unaligned
6539 on a target that supports unaligned accesses (dr_unaligned_supported)
6540 we generate the following code:
6541 p = initial_addr;
6542 indx = 0;
6543 loop {
6544 p = p + indx * vectype_size;
6545 vec_dest = *(p);
6546 indx = indx + 1;
6547 }
6549 Otherwise, the data reference is potentially unaligned on a target that
6550 does not support unaligned accesses (dr_explicit_realign_optimized) -
6551 then generate the following code, in which the data in each iteration is
6552 obtained by two vector loads, one from the previous iteration, and one
6553 from the current iteration:
6554 p1 = initial_addr;
6555 msq_init = *(floor(p1))
6556 p2 = initial_addr + VS - 1;
6557 realignment_token = call target_builtin;
6558 indx = 0;
6559 loop {
6560 p2 = p2 + indx * vectype_size
6561 lsq = *(floor(p2))
6562 vec_dest = realign_load (msq, lsq, realignment_token)
6563 indx = indx + 1;
6564 msq = lsq;
6565 } */
6567 /* If the misalignment remains the same throughout the execution of the
6568 loop, we can create the init_addr and permutation mask at the loop
6569 preheader. Otherwise, it needs to be created inside the loop.
6570 This can only occur when vectorizing memory accesses in the inner-loop
6571 nested within an outer-loop that is being vectorized. */
6576 {
6579 }
6584 {
6589 {
6592 }
6593 }
6594 else
6599 {
6600 /* 1. Create the vector pointer update chain. */
6606 else
6607 dataref_ptr =
6611 {
6614 NULL_TREE);
6616 /* 2. Create the vector-load in the loop. */
6618 {
6624 {
6629 data_ref =
6632 }
6634 {
6641 dr_explicit_realign,
6659 }
6665 }
6673 /* 3. Handle explicit realignment if necessary/supported. Create in
6674 loop: vec_dest = realign_load (msq, lsq, realignment_token) */
6677 {
6678 tree tmp;
6685 realignment_token);
6692 {
6697 }
6698 }
6700 /* 4. Handle invariant-load. */
6702 {
6706 {
6711 /* CHECKME: bitpos depends on endianess? */
6715 vec_dest =
6724 /* FIXME: use build_constructor directly. */
6728 }
6729 else
6731 }
6733 /* Collect vector loads and later create their permutation in
6734 vect_transform_strided_load (). */
6738 /* Store vector loads in the corresponding SLP_NODE. */
6741 }
6747 {
6751 {
6754 }
6755 }
6756 else
6757 {
6759 {
6766 }
6767 else
6768 {
6771 else
6774 }
6775 }
6776 }
6782 }
6785 /* Function vectorizable_live_operation.
6787 STMT computes a value that is used outside the loop. Check if
6788 it can be supported. */
6790 bool
6794 {
6800 tree op;
6801 tree def;
6802 gimple def_stmt;
6818 /* FORNOW. CHECKME. */
6828 /* FORNOW: support only if all uses are invariant. This means
6829 that the scalar operations can remain in place, unvectorized.
6830 The original last scalar value that they compute will be used. */
6833 {
6836 else
6839 {
6843 }
6847 }
6849 /* No transformation is required for the cases we currently support. */
6851 }
6854 /* Function vect_is_simple_cond.
6856 Input:
6857 LOOP - the loop that is being vectorized.
6858 COND - Condition that is checked for simple use.
6860 Returns whether a COND can be vectorized. Checks whether
6861 condition operands are supportable using vec_is_simple_use. */
6863 static bool
6865 {
6867 tree def;
6877 {
6881 }
6887 {
6891 }
6897 }
6899 /* vectorizable_condition.
6901 Check if STMT is conditional modify expression that can be vectorized.
6902 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
6903 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
6904 at BSI.
6906 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6908 bool
6911 {
6920 tree new_temp;
6923 tree def;
6939 /* FORNOW: SLP not supported. */
6943 /* FORNOW: not yet supported. */
6945 {
6949 }
6951 /* Is vectorizable conditional operation? */
6969 /* We do not handle two different vector types for the condition
6970 and the values. */
6975 {
6980 }
6987 {
6992 }
7002 {
7005 }
7007 /* Transform */
7009 /* Handle def. */
7013 /* Handle cond expr. */
7014 vec_cond_lhs =
7016 vec_cond_rhs =
7021 /* Arguments are ready. Create the new vector stmt. */
7033 }
7036 /* Function vect_transform_stmt.
7038 Create a vectorized stmt to replace STMT, and insert it at BSI. */
7040 static bool
7043 slp_instance slp_node_instance)
7044 {
7048 gimple orig_stmt_in_pattern;
7052 {
7086 slp_node_instance);
7094 {
7095 /* In case of interleaving, the whole chain is vectorized when the
7096 last store in the chain is reached. Store stmts before the last
7097 one are skipped, and there vec_stmt_info shouldn't be freed
7098 meanwhile. */
7102 }
7103 else
7126 {
7130 }
7131 }
7135 {
7138 }
7141 {
7145 {
7147 /* STMT was inserted by the vectorizer to replace a computation idiom.
7148 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
7149 computed this idiom. We need to record a pointer to VEC_STMT in
7150 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
7151 documentation of vect_pattern_recog. */
7153 {
7156 }
7157 }
7158 }
7161 }
7164 /* This function builds ni_name = number of iterations loop executes
7165 on the loop preheader. */
7167 static tree
7169 {
7172 edge pe;
7182 {
7185 }
7188 }
7191 /* This function generates the following statements:
7193 ni_name = number of iterations loop executes
7194 ratio = ni_name / vf
7195 ratio_mult_vf_name = ratio * vf
7197 and places them at the loop preheader edge. */
7199 static void
7204 {
7206 edge pe;
7207 basic_block new_bb;
7208 gimple_seq stmts;
7209 tree ni_name;
7210 tree var;
7211 tree ratio_name;
7212 tree ratio_mult_vf_name;
7216 tree log_vf;
7220 /* Generate temporary variable that contains
7221 number of iterations loop executes. */
7226 /* Create: ratio = ni >> log2(vf) */
7230 {
7239 }
7241 /* Create: ratio_mult_vf = ratio << log2 (vf). */
7246 {
7256 }
7263 }
7266 /* Function vect_update_ivs_after_vectorizer.
7268 "Advance" the induction variables of LOOP to the value they should take
7269 after the execution of LOOP. This is currently necessary because the
7270 vectorizer does not handle induction variables that are used after the
7271 loop. Such a situation occurs when the last iterations of LOOP are
7272 peeled, because:
7273 1. We introduced new uses after LOOP for IVs that were not originally used
7274 after LOOP: the IVs of LOOP are now used by an epilog loop.
7275 2. LOOP is going to be vectorized; this means that it will iterate N/VF
7276 times, whereas the loop IVs should be bumped N times.
7278 Input:
7279 - LOOP - a loop that is going to be vectorized. The last few iterations
7280 of LOOP were peeled.
7281 - NITERS - the number of iterations that LOOP executes (before it is
7282 vectorized). i.e, the number of times the ivs should be bumped.
7283 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
7284 coming out from LOOP on which there are uses of the LOOP ivs
7285 (this is the path from LOOP->exit to epilog_loop->preheader).
7287 The new definitions of the ivs are placed in LOOP->exit.
7288 The phi args associated with the edge UPDATE_E in the bb
7289 UPDATE_E->dest are updated accordingly.
7291 Assumption 1: Like the rest of the vectorizer, this function assumes
7292 a single loop exit that has a single predecessor.
7294 Assumption 2: The phi nodes in the LOOP header and in update_bb are
7295 organized in the same order.
7297 Assumption 3: The access function of the ivs is simple enough (see
7298 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
7300 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
7301 coming out of LOOP on which the ivs of LOOP are used (this is the path
7302 that leads to the epilog loop; other paths skip the epilog loop). This
7303 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
7304 needs to have its phis updated.
7305 */
7307 static void
7309 edge update_e)
7310 {
7317 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
7319 /* Make sure there exists a single-predecessor exit bb: */
7325 {
7327 tree evolution_part;
7328 tree init_expr;
7329 tree step_expr;
7331 gimple_stmt_iterator last_gsi;
7336 {
7339 }
7341 /* Skip virtual phi's. */
7343 {
7347 }
7349 /* Skip reduction phis. */
7351 {
7355 }
7360 evolution_part =
7364 /* FORNOW: We do not support IVs whose evolution function is a polynomial
7365 of degree >= 2 or exponential. */
7374 init_expr,
7378 else
7382 niters),
7383 step_expr),
7384 init_expr);
7395 /* Fix phi expressions in the successor bb. */
7397 }
7398 }
7400 /* Return the more conservative threshold between the
7401 min_profitable_iters returned by the cost model and the user
7402 specified threshold, if provided. */
7404 static unsigned int
7407 {
7414 /* Use the cost model only if it is more conservative than user specified
7415 threshold. */
7418 && (!min_scalar_loop_bound
7426 }
7428 /* Function vect_do_peeling_for_loop_bound
7430 Peel the last iterations of the loop represented by LOOP_VINFO.
7431 The peeled iterations form a new epilog loop. Given that the loop now
7432 iterates NITERS times, the new epilog loop iterates
7433 NITERS % VECTORIZATION_FACTOR times.
7435 The original loop will later be made to iterate
7436 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
7438 static void
7440 {
7444 edge update_e;
7445 basic_block preheader;
7456 /* Generate the following variables on the preheader of original loop:
7458 ni_name = number of iteration the original loop executes
7459 ratio = ni_name / vf
7460 ratio_mult_vf_name = ratio * vf */
7466 /* If cost model check not done during versioning and
7467 peeling for alignment. */
7471 {
7474 /* Get profitability threshold for vectorized loop. */
7478 min_profitable_iters);
7479 }
7486 #ifdef ENABLE_CHECKING
7488 #endif
7490 /* A guard that controls whether the new_loop is to be executed or skipped
7491 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
7492 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
7493 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
7494 is on the path where the LOOP IVs are used and need to be updated. */
7499 else
7502 /* Update IVs of original loop as if they were advanced
7503 by ratio_mult_vf_name steps. */
7506 /* After peeling we have to reset scalar evolution analyzer. */
7510 }
7513 /* Function vect_gen_niters_for_prolog_loop
7515 Set the number of iterations for the loop represented by LOOP_VINFO
7516 to the minimum between LOOP_NITERS (the original iteration count of the loop)
7517 and the misalignment of DR - the data reference recorded in
7518 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
7519 this loop, the data reference DR will refer to an aligned location.
7521 The following computation is generated:
7523 If the misalignment of DR is known at compile time:
7524 addr_mis = int mis = DR_MISALIGNMENT (dr);
7525 Else, compute address misalignment in bytes:
7526 addr_mis = addr & (vectype_size - 1)
7528 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
7530 (elem_size = element type size; an element is the scalar element whose type
7531 is the inner type of the vectype)
7533 When the step of the data-ref in the loop is not 1 (as in interleaved data
7534 and SLP), the number of iterations of the prolog must be divided by the step
7535 (which is equal to the size of interleaved group).
7537 The above formulas assume that VF == number of elements in the vector. This
7538 may not hold when there are multiple-types in the loop.
7539 In this case, for some data-references in the loop the VF does not represent
7540 the number of elements that fit in the vector. Therefore, instead of VF we
7541 use TYPE_VECTOR_SUBPARTS. */
7543 static tree
7545 {
7548 tree var;
7549 gimple_seq stmts;
7551 edge pe;
7552 basic_block new_bb;
7568 {
7577 }
7578 else
7579 {
7587 tree elem_size_log =
7591 tree byte_misalign;
7592 tree elem_misalign;
7597 /* Create: byte_misalign = addr & (vectype_size - 1) */
7598 byte_misalign =
7601 /* Create: elem_misalign = byte_misalign / element_size */
7602 elem_misalign =
7605 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
7609 }
7611 /* Create: prolog_loop_niters = min (iters, loop_niters) */
7612 /* If the loop bound is known at compile time we already verified that it is
7613 greater than vf; since the misalignment ('iters') is at most vf, there's
7614 no need to generate the MIN_EXPR in this case. */
7619 {
7622 }
7629 /* Insert stmt on loop preheader edge. */
7631 {
7634 }
7637 }
7640 /* Function vect_update_init_of_dr
7642 NITERS iterations were peeled from LOOP. DR represents a data reference
7643 in LOOP. This function updates the information recorded in DR to
7644 account for the fact that the first NITERS iterations had already been
7645 executed. Specifically, it updates the OFFSET field of DR. */
7647 static void
7649 {
7657 }
7660 /* Function vect_update_inits_of_drs
7662 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
7663 This function updates the information recorded for the data references in
7664 the loop to account for the fact that the first NITERS iterations had
7665 already been executed. Specifically, it updates the initial_condition of
7666 the access_function of all the data_references in the loop. */
7668 static void
7670 {
7680 }
7683 /* Function vect_do_peeling_for_alignment
7685 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
7686 'niters' is set to the misalignment of one of the data references in the
7687 loop, thereby forcing it to refer to an aligned location at the beginning
7688 of the execution of this loop. The data reference for which we are
7689 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
7691 static void
7693 {
7696 tree n_iters;
7711 /* If cost model check not done during versioning. */
7714 {
7717 /* Get profitability threshold for vectorized loop. */
7721 min_profitable_iters);
7722 }
7724 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
7725 new_loop =
7731 #ifdef ENABLE_CHECKING
7733 #endif
7735 /* Update number of times loop executes. */
7740 /* Update the init conditions of the access functions of all data refs. */
7743 /* After peeling we have to reset scalar evolution analyzer. */
7747 }
7750 /* Function vect_create_cond_for_align_checks.
7752 Create a conditional expression that represents the alignment checks for
7753 all of data references (array element references) whose alignment must be
7754 checked at runtime.
7756 Input:
7757 COND_EXPR - input conditional expression. New conditions will be chained
7758 with logical AND operation.
7759 LOOP_VINFO - two fields of the loop information are used.
7760 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
7761 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
7763 Output:
7764 COND_EXPR_STMT_LIST - statements needed to construct the conditional
7765 expression.
7766 The returned value is the conditional expression to be used in the if
7767 statement that controls which version of the loop gets executed at runtime.
7769 The algorithm makes two assumptions:
7770 1) The number of bytes "n" in a vector is a power of 2.
7771 2) An address "a" is aligned if a%n is zero and that this
7772 test can be done as a&(n-1) == 0. For example, for 16
7773 byte vectors the test is a&0xf == 0. */
7775 static void
7779 {
7783 gimple ref_stmt;
7785 tree mask_cst;
7787 tree psize;
7788 tree int_ptrsize_type;
7792 gimple and_stmt;
7793 tree ptrsize_zero;
7794 tree part_cond_expr;
7796 /* Check that mask is one less than a power of 2, i.e., mask is
7797 all zeros followed by all ones. */
7800 /* CHECKME: what is the best integer or unsigned type to use to hold a
7801 cast from a pointer value? */
7803 int_ptrsize_type
7806 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
7807 of the first vector of the i'th data reference. */
7810 {
7812 tree addr_base;
7817 /* create: addr_tmp = (int)(address_of_first_vector) */
7818 addr_base =
7833 /* The addresses are OR together. */
7836 {
7837 /* create: or_tmp = or_tmp | addr_tmp */
7843 new_or_tmp_name,
7848 }
7849 else
7856 /* create: and_tmp = or_tmp & mask */
7866 /* Make and_tmp the left operand of the conditional test against zero.
7867 if and_tmp has a nonzero bit then some address is unaligned. */
7874 else
7876 }
7878 /* Function vect_vfa_segment_size.
7880 Create an expression that computes the size of segment
7881 that will be accessed for a data reference. The functions takes into
7882 account that realignment loads may access one more vector.
7884 Input:
7885 DR: The data reference.
7886 VECT_FACTOR: vectorization factor.
7888 Return an expression whose value is the size of segment which will be
7889 accessed by DR. */
7891 static tree
7893 {
7898 {
7899 tree vector_size = TYPE_SIZE_UNIT
7904 }
7906 }
7908 /* Function vect_create_cond_for_alias_checks.
7910 Create a conditional expression that represents the run-time checks for
7911 overlapping of address ranges represented by a list of data references
7912 relations passed as input.
7914 Input:
7915 COND_EXPR - input conditional expression. New conditions will be chained
7916 with logical AND operation.
7917 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
7918 to be checked.
7920 Output:
7921 COND_EXPR - conditional expression.
7922 COND_EXPR_STMT_LIST - statements needed to construct the conditional
7923 expression.
7926 The returned value is the conditional expression to be used in the if
7927 statement that controls which version of the loop gets executed at runtime.
7928 */
7930 static void
7934 {
7938 tree vect_factor =
7941 ddr_p ddr;
7943 tree part_cond_expr;
7945 /* Create expression
7946 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
7947 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
7948 &&
7949 ...
7950 &&
7951 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
7952 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
7958 {
7969 {
7972 }
7978 {
7981 }
7983 addr_base_a =
7986 addr_base_b =
7994 {
8000 }
8003 part_cond_expr =
8007 addr_base_a,
8008 segment_length_a),
8009 addr_base_b),
8012 addr_base_b,
8013 segment_length_b),
8014 addr_base_a));
8019 else
8021 }
8026 }
8028 /* Function vect_loop_versioning.
8030 If the loop has data references that may or may not be aligned or/and
8031 has data reference relations whose independence was not proven then
8032 two versions of the loop need to be generated, one which is vectorized
8033 and one which isn't. A test is then generated to control which of the
8034 loops is executed. The test checks for the alignment of all of the
8035 data references that may or may not be aligned. An additional
8036 sequence of runtime tests is generated for each pairs of DDRs whose
8037 independence was not proven. The vectorized version of loop is
8038 executed only if both alias and alignment tests are passed.
8040 The test generated to check which version of loop is executed
8041 is modified to also check for profitability as indicated by the
8042 cost model initially. */
8044 static void
8046 {
8051 basic_block condition_bb;
8053 basic_block merge_bb;
8054 basic_block new_exit_bb;
8057 tree arg;
8064 /* Get profitability threshold for vectorized loop. */
8068 min_profitable_iters);
8070 cond_expr =
8085 cond_expr =
8087 cond_expr =
8096 /* Loop versioning violates an assumption we try to maintain during
8097 vectorization - that the loop exit block has a single predecessor.
8098 After versioning, the exit block of both loop versions is the same
8099 basic block (i.e. it has two predecessors). Just in order to simplify
8100 following transformations in the vectorizer, we fix this situation
8101 here by adding a new (empty) block on the exit-edge of the loop,
8102 with the proper loop-exit phis to maintain loop-closed-form. */
8111 {
8114 new_exit_bb);
8118 }
8120 /* End loop-exit-fixes after versioning. */
8124 {
8127 }
8128 }
8130 /* Remove a group of stores (for SLP or interleaving), free their
8131 stmt_vec_info. */
8133 static void
8135 {
8137 gimple tmp;
8138 gimple_stmt_iterator next_si;
8141 {
8142 /* Free the attached stmt_vec_info and remove the stmt. */
8148 }
8149 }
8152 /* Vectorize SLP instance tree in postorder. */
8154 static bool
8157 {
8158 gimple stmt;
8160 gimple_stmt_iterator si;
8161 stmt_vec_info stmt_info;
8163 tree vectype;
8165 slp_tree loads_node;
8171 vectorization_factor);
8173 vectorization_factor);
8178 /* VECTYPE is the type of the destination. */
8183 /* For each SLP instance calculate number of vector stmts to be created
8184 for the scalar stmts in each node of the SLP tree. Number of vector
8185 elements in one vector iteration is the number of scalar elements in
8186 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
8187 size. */
8190 /* In case of load permutation we have to allocate vectorized statements for
8191 all the nodes that participate in that permutation. */
8193 {
8196 i++)
8197 {
8199 {
8201 vec_stmts_size);
8203 }
8204 }
8205 }
8208 {
8211 }
8214 {
8217 }
8219 /* Loads should be inserted before the first load. */
8224 else
8229 {
8231 /* If IS_STORE is TRUE, the vectorization of the
8232 interleaving chain was completed - free all the stores in
8233 the chain. */
8235 else
8236 /* FORNOW: SLP originates only from strided stores. */
8240 }
8242 /* FORNOW: SLP originates only from strided stores. */
8244 }
8247 static bool
8249 {
8252 slp_instance instance;
8257 {
8258 /* Schedule the tree of INSTANCE. */
8265 }
8268 }
8270 /* Function vect_transform_loop.
8272 The analysis phase has determined that the loop is vectorizable.
8273 Vectorize the loop - created vectorized stmts to replace the scalar
8274 stmts in the loop, and update the loop exit condition. */
8276 void
8278 {
8282 gimple_stmt_iterator si;
8297 /* CHECKME: we wouldn't need this if we called update_ssa once
8298 for all loops. */
8301 /* Peel the loop if there are data refs with unknown alignment.
8302 Only one data ref with unknown store is allowed. */
8307 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
8308 compile time constant), or it is a constant that doesn't divide by the
8309 vectorization factor, then an epilog loop needs to be created.
8310 We therefore duplicate the loop: the original loop will be vectorized,
8311 and will compute the first (n/VF) iterations. The second copy of the loop
8312 will remain scalar and will compute the remaining (n%VF) iterations.
8313 (VF is the vectorization factor). */
8319 else
8323 /* 1) Make sure the loop header has exactly two entries
8324 2) Make sure we have a preheader basic block. */
8330 /* FORNOW: the vectorizer supports only loops which body consist
8331 of one basic block (header + empty latch). When the vectorizer will
8332 support more involved loop forms, the order by which the BBs are
8333 traversed need to be reconsidered. */
8336 {
8338 stmt_vec_info stmt_info;
8339 gimple phi;
8342 {
8345 {
8348 }
8363 {
8367 }
8368 }
8371 {
8376 {
8379 }
8383 /* vector stmts created in the outer-loop during vectorization of
8384 stmts in an inner-loop may not have a stmt_info, and do not
8385 need to be vectorized. */
8387 {
8390 }
8394 {
8397 }
8400 nunits =
8405 /* For SLP VF is set according to unrolling factor, and not to
8406 vector size, hence for SLP this print is not valid. */
8409 /* SLP. Schedule all the SLP instances when the first SLP stmt is
8410 reached. */
8412 {
8414 {
8422 /* IS_STORE is true if STMT is a store. Stores cannot be of
8423 hybrid SLP type. They are removed in
8424 vect_schedule_slp_instance and their vinfo is destroyed. */
8426 {
8429 }
8430 }
8432 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
8434 {
8437 }
8438 }
8440 /* -------- vectorize statement ------------ */
8447 {
8449 {
8450 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
8451 interleaving chain was completed - free all the stores in
8452 the chain. */
8456 }
8457 else
8458 {
8459 /* Free the attached stmt_vec_info and remove the stmt. */
8463 }
8464 }
8473 /* The memory tags and pointers in vectorized statements need to
8474 have their SSA forms updated. FIXME, why can't this be delayed
8475 until all the loops have been transformed? */
8482 }