| blob | a25960b58ec4c77c2c530bcebb667111c46d95ea |
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 */
929 {
938 }
940 /* base + base_offset */
946 /* addr_expr = addr_base */
958 {
961 }
963 }
966 /* Function vect_create_data_ref_ptr.
968 Create a new pointer to vector type (vp), that points to the first location
969 accessed in the loop by STMT, along with the def-use update chain to
970 appropriately advance the pointer through the loop iterations. Also set
971 aliasing information for the pointer. This vector pointer is used by the
972 callers to this function to create a memory reference expression for vector
973 load/store access.
975 Input:
976 1. STMT: a stmt that references memory. Expected to be of the form
977 GIMPLE_ASSIGN <name, data-ref> or
978 GIMPLE_ASSIGN <data-ref, name>.
979 2. AT_LOOP: the loop where the vector memref is to be created.
980 3. OFFSET (optional): an offset to be added to the initial address accessed
981 by the data-ref in STMT.
982 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
983 pointing to the initial address.
984 5. TYPE: if not NULL indicates the required type of the data-ref.
986 Output:
987 1. Declare a new ptr to vector_type, and have it point to the base of the
988 data reference (initial addressed accessed by the data reference).
989 For example, for vector of type V8HI, the following code is generated:
991 v8hi *vp;
992 vp = (v8hi *)initial_address;
994 if OFFSET is not supplied:
995 initial_address = &a[init];
996 if OFFSET is supplied:
997 initial_address = &a[init + OFFSET];
999 Return the initial_address in INITIAL_ADDRESS.
1001 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
1002 update the pointer in each iteration of the loop.
1004 Return the increment stmt that updates the pointer in PTR_INCR.
1006 3. Set INV_P to true if the access pattern of the data reference in the
1007 vectorized loop is invariant. Set it to false otherwise.
1009 4. Return the pointer. */
1011 static tree
1015 {
1016 tree base_name;
1023 tree vect_ptr_type;
1024 tree vect_ptr;
1025 tree tag;
1026 tree new_temp;
1027 gimple vec_stmt;
1029 edge pe;
1030 basic_block new_bb;
1031 tree vect_ptr_init;
1033 tree vptr;
1034 gimple_stmt_iterator incr_gsi;
1037 gimple incr;
1038 tree step;
1040 /* Check the step (evolution) of the load in LOOP, and record
1041 whether it's invariant. */
1044 else
1049 else
1052 /* Create an expression for the first address accessed by this load
1053 in LOOP. */
1057 {
1070 }
1072 /** (1) Create the new vector-pointer variable: **/
1075 else
1082 /** (2) Add aliasing information to the new vector-pointer:
1083 (The points-to info (DR_PTR_INFO) may be defined later.) **/
1088 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
1089 tag must be created with tag added to its may alias list. */
1092 else
1095 /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
1096 vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
1097 def-use update cycles for the pointer: One relative to the outer-loop
1098 (LOOP), which is what steps (3) and (4) below do. The other is relative
1099 to the inner-loop (which is the inner-most loop containing the dataref),
1100 and this is done be step (5) below.
1102 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
1103 inner-most loop, and so steps (3),(4) work the same, and step (5) is
1104 redundant. Steps (3),(4) create the following:
1106 vp0 = &base_addr;
1107 LOOP: vp1 = phi(vp0,vp2)
1108 ...
1109 ...
1110 vp2 = vp1 + step
1111 goto LOOP
1113 If there is an inner-loop nested in loop, then step (5) will also be
1114 applied, and an additional update in the inner-loop will be created:
1116 vp0 = &base_addr;
1117 LOOP: vp1 = phi(vp0,vp2)
1118 ...
1119 inner: vp3 = phi(vp1,vp4)
1120 vp4 = vp3 + inner_step
1121 if () goto inner
1122 ...
1123 vp2 = vp1 + step
1124 if () goto LOOP */
1126 /** (3) Calculate the initial address the vector-pointer, and set
1127 the vector-pointer to point to it before the loop: **/
1129 /* Create: (&(base[init_val+offset]) in the loop preheader. */
1135 {
1138 }
1142 /* Create: p = (vectype *) initial_base */
1151 /** (4) Handle the updating of the vector-pointer inside the loop.
1152 This is needed when ONLY_INIT is false, and also when AT_LOOP
1153 is the inner-loop nested in LOOP (during outer-loop vectorization).
1154 **/
1157 {
1158 /* Copy the points-to information if it exists. */
1162 }
1163 else
1164 {
1165 /* The step of the vector pointer is the Vector Size. */
1167 /* One exception to the above is when the scalar step of the load in
1168 LOOP is zero. In this case the step here is also zero. */
1181 /* Copy the points-to information if it exists. */
1183 {
1186 }
1193 }
1199 /** (5) Handle the updating of the vector-pointer inside the inner-loop
1200 nested in LOOP, if exists: **/
1204 {
1213 /* Copy the points-to information if it exists. */
1215 {
1218 }
1225 }
1226 else
1228 }
1231 /* Function bump_vector_ptr
1233 Increment a pointer (to a vector type) by vector-size. If requested,
1234 i.e. if PTR-INCR is given, then also connect the new increment stmt
1235 to the existing def-use update-chain of the pointer, by modifying
1236 the PTR_INCR as illustrated below:
1238 The pointer def-use update-chain before this function:
1239 DATAREF_PTR = phi (p_0, p_2)
1240 ....
1241 PTR_INCR: p_2 = DATAREF_PTR + step
1243 The pointer def-use update-chain after this function:
1244 DATAREF_PTR = phi (p_0, p_2)
1245 ....
1246 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1247 ....
1248 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
1250 Input:
1251 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
1252 in the loop.
1253 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
1254 the loop. The increment amount across iterations is expected
1255 to be vector_size.
1256 BSI - location where the new update stmt is to be placed.
1257 STMT - the original scalar memory-access stmt that is being vectorized.
1258 BUMP - optional. The offset by which to bump the pointer. If not given,
1259 the offset is assumed to be vector_size.
1261 Output: Return NEW_DATAREF_PTR as illustrated above.
1263 */
1265 static tree
1268 {
1274 gimple incr_stmt;
1275 ssa_op_iter iter;
1276 use_operand_p use_p;
1277 tree new_dataref_ptr;
1288 /* Copy the points-to information if it exists. */
1296 /* Update the vector-pointer's cross-iteration increment. */
1298 {
1303 else
1305 }
1308 }
1311 /* Function vect_create_destination_var.
1313 Create a new temporary of type VECTYPE. */
1315 static tree
1317 {
1318 tree vec_dest;
1320 tree type;
1335 }
1338 /* Function vect_init_vector.
1340 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1341 the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1342 is not NULL. Otherwise, place the initialization at the loop preheader.
1343 Return the DEF of INIT_STMT.
1344 It will be used in the vectorization of STMT. */
1346 static tree
1349 {
1351 tree new_var;
1352 gimple init_stmt;
1353 tree vec_oprnd;
1354 edge pe;
1355 tree new_temp;
1356 basic_block new_bb;
1366 else
1367 {
1376 }
1379 {
1382 }
1386 }
1389 /* For constant and loop invariant defs of SLP_NODE this function returns
1390 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1391 OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1392 stmts. NUMBER_OF_VECTORS is the number of vector defs to create. */
1394 static void
1397 {
1403 tree vec_cst;
1406 tree vector_type;
1418 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1419 created vectors. It is greater than 1 if unrolling is performed.
1421 For example, we have two scalar operands, s1 and s2 (e.g., group of
1422 strided accesses of size two), while NUNITS is four (i.e., four scalars
1423 of this type can be packed in a vector). The output vector will contain
1424 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1425 will be 2).
1427 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1428 containing the operands.
1430 For example, NUNITS is four as before, and the group size is 8
1431 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1432 {s5, s6, s7, s8}. */
1439 {
1441 {
1444 else
1449 /* Create 'vect_ = {op0,op1,...,opn}'. */
1452 number_of_places_left_in_vector--;
1455 {
1462 else
1467 NULL));
1469 }
1470 }
1471 }
1473 /* Since the vectors are created in the reverse order, we should invert
1474 them. */
1477 {
1480 }
1484 /* In case that VF is greater than the unrolling factor needed for the SLP
1485 group of stmts, NUMBER_OF_VECTORS to be created is greater than
1486 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1487 to replicate the vectors. */
1489 {
1492 }
1493 }
1496 /* Get vectorized definitions from SLP_NODE that contains corresponding
1497 vectorized def-stmts. */
1499 static void
1501 {
1502 tree vec_oprnd;
1503 gimple vec_def_stmt;
1510 i++)
1511 {
1515 }
1516 }
1519 /* Get vectorized definitions for SLP_NODE.
1520 If the scalar definitions are loop invariants or constants, collect them and
1521 call vect_get_constant_vectors() to create vector stmts.
1522 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1523 must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1524 vect_get_slp_vect_defs() to retrieve them.
1525 If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1526 the right node. This is used when the second operand must remain scalar. */
1528 static void
1531 {
1532 gimple first_stmt;
1538 /* The number of vector defs is determined by the number of vector statements
1539 in the node from which we get those statements. */
1542 else
1543 {
1545 /* Number of vector stmts was calculated according to LHS in
1546 vect_schedule_slp_instance(), fix it by replacing LHS with RHS, if
1547 necessary. See vect_get_smallest_scalar_type() for details. */
1551 {
1554 }
1555 }
1557 /* Allocate memory for vectorized defs. */
1560 /* SLP_NODE corresponds either to a group of stores or to a group of
1561 unary/binary operations. We don't call this function for loads. */
1563 /* The defs are already vectorized. */
1565 else
1566 /* Build vectors from scalar defs. */
1570 /* Since we don't call this function with loads, this is a group of
1571 stores. */
1578 /* The number of vector defs is determined by the number of vector statements
1579 in the node from which we get those statements. */
1582 else
1588 /* The defs are already vectorized. */
1590 else
1591 /* Build vectors from scalar defs. */
1593 }
1596 /* Function get_initial_def_for_induction
1598 Input:
1599 STMT - a stmt that performs an induction operation in the loop.
1600 IV_PHI - the initial value of the induction variable
1602 Output:
1603 Return a vector variable, initialized with the first VF values of
1604 the induction variable. E.g., for an iv with IV_PHI='X' and
1605 evolution S, for a vector of 4 units, we want to return:
1606 [X, X + S, X + 2*S, X + 3*S]. */
1608 static tree
1610 {
1615 tree vectype;
1619 basic_block new_bb;
1621 tree access_fn;
1622 tree new_var;
1623 tree new_name;
1631 tree expr;
1635 imm_use_iterator imm_iter;
1636 use_operand_p use_p;
1637 gimple exit_phi;
1638 edge latch_e;
1639 tree loop_arg;
1640 gimple_stmt_iterator si;
1651 /* Find the first insertion point in the BB. */
1656 else
1659 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
1661 {
1664 }
1665 else
1679 /* Create the vector that holds the initial_value of the induction. */
1681 {
1682 /* iv_loop is nested in the loop to be vectorized. init_expr had already
1683 been created during vectorization of previous stmts; We obtain it from
1684 the STMT_VINFO_VEC_STMT of the defining stmt. */
1687 }
1688 else
1689 {
1690 /* iv_loop is the loop to be vectorized. Create:
1691 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
1697 {
1700 }
1705 {
1706 /* Create: new_name_i = new_name + step_expr */
1718 {
1721 }
1723 }
1724 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
1727 }
1730 /* Create the vector that holds the step of the induction. */
1732 /* iv_loop is nested in the loop to be vectorized. Generate:
1733 vec_step = [S, S, S, S] */
1735 else
1736 {
1737 /* iv_loop is the loop to be vectorized. Generate:
1738 vec_step = [VF*S, VF*S, VF*S, VF*S] */
1741 }
1751 /* Create the following def-use cycle:
1752 loop prolog:
1753 vec_init = ...
1754 vec_step = ...
1755 loop:
1756 vec_iv = PHI <vec_init, vec_loop>
1757 ...
1758 STMT
1759 ...
1760 vec_loop = vec_iv + vec_step; */
1762 /* Create the induction-phi that defines the induction-operand. */
1770 /* Create the iv update inside the loop */
1778 /* Set the arguments of the phi node: */
1783 /* In case that vectorization factor (VF) is bigger than the number
1784 of elements that we can fit in a vectype (nunits), we have to generate
1785 more than one vector stmt - i.e - we need to "unroll" the
1786 vector stmt by a factor VF/nunits. For more details see documentation
1787 in vectorizable_operation. */
1790 {
1791 stmt_vec_info prev_stmt_vinfo;
1792 /* FORNOW. This restriction should be relaxed. */
1795 /* Create the vector that holds the step of the induction. */
1808 {
1809 /* vec_i = vec_prev + vec_step */
1820 }
1821 }
1824 {
1825 /* Find the loop-closed exit-phi of the induction, and record
1826 the final vector of induction results: */
1829 {
1831 {
1834 }
1835 }
1837 {
1839 /* FORNOW. Currently not supporting the case that an inner-loop induction
1840 is not used in the outer-loop (i.e. only outside the outer-loop). */
1846 {
1849 }
1850 }
1851 }
1855 {
1860 }
1864 }
1867 /* Function vect_get_vec_def_for_operand.
1869 OP is an operand in STMT. This function returns a (vector) def that will be
1870 used in the vectorized stmt for STMT.
1872 In the case that OP is an SSA_NAME which is defined in the loop, then
1873 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1875 In case OP is an invariant or constant, a new stmt that creates a vector def
1876 needs to be introduced. */
1878 static tree
1880 {
1881 tree vec_oprnd;
1882 gimple vec_stmt;
1883 gimple def_stmt;
1889 tree vec_inv;
1890 tree vec_cst;
1892 tree def;
1896 tree vector_type;
1899 {
1902 }
1907 {
1909 {
1912 }
1914 {
1917 }
1918 }
1921 {
1922 /* Case 1: operand is a constant. */
1924 {
1928 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1933 {
1935 }
1941 }
1943 /* Case 2: operand is defined outside the loop - loop invariant. */
1945 {
1949 /* Create 'vec_inv = {inv,inv,..,inv}' */
1954 {
1956 }
1958 /* FIXME: use build_constructor directly. */
1963 }
1965 /* Case 3: operand is defined inside the loop. */
1967 {
1971 /* Get the def from the vectorized stmt. */
1979 else
1982 }
1984 /* Case 4: operand is defined by a loop header phi - reduction */
1986 {
1992 /* Get the def before the loop */
1995 }
1997 /* Case 5: operand is defined by loop-header phi - induction. */
1999 {
2002 /* Get the def from the vectorized stmt. */
2008 }
2012 }
2013 }
2016 /* Function vect_get_vec_def_for_stmt_copy
2018 Return a vector-def for an operand. This function is used when the
2019 vectorized stmt to be created (by the caller to this function) is a "copy"
2020 created in case the vectorized result cannot fit in one vector, and several
2021 copies of the vector-stmt are required. In this case the vector-def is
2022 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
2023 of the stmt that defines VEC_OPRND.
2024 DT is the type of the vector def VEC_OPRND.
2026 Context:
2027 In case the vectorization factor (VF) is bigger than the number
2028 of elements that can fit in a vectype (nunits), we have to generate
2029 more than one vector stmt to vectorize the scalar stmt. This situation
2030 arises when there are multiple data-types operated upon in the loop; the
2031 smallest data-type determines the VF, and as a result, when vectorizing
2032 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
2033 vector stmt (each computing a vector of 'nunits' results, and together
2034 computing 'VF' results in each iteration). This function is called when
2035 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
2036 which VF=16 and nunits=4, so the number of copies required is 4):
2038 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
2040 S1: x = load VS1.0: vx.0 = memref0 VS1.1
2041 VS1.1: vx.1 = memref1 VS1.2
2042 VS1.2: vx.2 = memref2 VS1.3
2043 VS1.3: vx.3 = memref3
2045 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
2046 VSnew.1: vz1 = vx.1 + ... VSnew.2
2047 VSnew.2: vz2 = vx.2 + ... VSnew.3
2048 VSnew.3: vz3 = vx.3 + ...
2050 The vectorization of S1 is explained in vectorizable_load.
2051 The vectorization of S2:
2052 To create the first vector-stmt out of the 4 copies - VSnew.0 -
2053 the function 'vect_get_vec_def_for_operand' is called to
2054 get the relevant vector-def for each operand of S2. For operand x it
2055 returns the vector-def 'vx.0'.
2057 To create the remaining copies of the vector-stmt (VSnew.j), this
2058 function is called to get the relevant vector-def for each operand. It is
2059 obtained from the respective VS1.j stmt, which is recorded in the
2060 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
2062 For example, to obtain the vector-def 'vx.1' in order to create the
2063 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
2064 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
2065 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
2066 and return its def ('vx.1').
2067 Overall, to create the above sequence this function will be called 3 times:
2068 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
2069 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
2070 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
2072 static tree
2074 {
2075 gimple vec_stmt_for_operand;
2076 stmt_vec_info def_stmt_info;
2078 /* Do nothing; can reuse same def. */
2090 else
2093 }
2096 /* Get vectorized definitions for the operands to create a copy of an original
2097 stmt. See vect_get_vec_def_for_stmt_copy() for details. */
2099 static void
2103 {
2110 {
2114 }
2115 }
2118 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not NULL. */
2120 static void
2123 slp_tree slp_node)
2124 {
2127 else
2128 {
2129 tree vec_oprnd;
2136 {
2140 }
2141 }
2142 }
2145 /* Function vect_finish_stmt_generation.
2147 Insert a new stmt. */
2149 static void
2152 {
2164 {
2167 }
2169 /* Make sure gsi points to the stmt that is being vectorized. */
2173 }
2176 /* Function get_initial_def_for_reduction
2178 Input:
2179 STMT - a stmt that performs a reduction operation in the loop.
2180 INIT_VAL - the initial value of the reduction variable
2182 Output:
2183 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2184 of the reduction (used for adjusting the epilog - see below).
2185 Return a vector variable, initialized according to the operation that STMT
2186 performs. This vector will be used as the initial value of the
2187 vector of partial results.
2189 Option1 (adjust in epilog): Initialize the vector as follows:
2190 add: [0,0,...,0,0]
2191 mult: [1,1,...,1,1]
2192 min/max: [init_val,init_val,..,init_val,init_val]
2193 bit and/or: [init_val,init_val,..,init_val,init_val]
2194 and when necessary (e.g. add/mult case) let the caller know
2195 that it needs to adjust the result by init_val.
2197 Option2: Initialize the vector as follows:
2198 add: [0,0,...,0,init_val]
2199 mult: [1,1,...,1,init_val]
2200 min/max: [init_val,init_val,...,init_val]
2201 bit and/or: [init_val,init_val,...,init_val]
2202 and no adjustments are needed.
2204 For example, for the following code:
2206 s = init_val;
2207 for (i=0;i<n;i++)
2208 s = s + a[i];
2210 STMT is 's = s + a[i]', and the reduction variable is 's'.
2211 For a vector of 4 units, we want to return either [0,0,0,init_val],
2212 or [0,0,0,0] and let the caller know that it needs to adjust
2213 the result at the end by 'init_val'.
2215 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2216 initialization vector is simpler (same element in all entries).
2217 A cost model should help decide between these two schemes. */
2219 static tree
2221 {
2229 tree vecdef;
2230 tree def_for_init;
2231 tree init_def;
2234 tree vector_type;
2240 else
2246 {
2252 else
2254 /* Create a vector of zeros for init_def. */
2257 else
2274 }
2277 }
2280 /* Function vect_create_epilog_for_reduction
2282 Create code at the loop-epilog to finalize the result of a reduction
2283 computation.
2285 VECT_DEF is a vector of partial results.
2286 REDUC_CODE is the tree-code for the epilog reduction.
2287 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
2288 number of elements that we can fit in a vectype (nunits). In this case
2289 we have to generate more than one vector stmt - i.e - we need to "unroll"
2290 the vector stmt by a factor VF/nunits. For more details see documentation
2291 in vectorizable_operation.
2292 STMT is the scalar reduction stmt that is being vectorized.
2293 REDUCTION_PHI is the phi-node that carries the reduction computation.
2295 This function:
2296 1. Creates the reduction def-use cycle: sets the arguments for
2297 REDUCTION_PHI:
2298 The loop-entry argument is the vectorized initial-value of the reduction.
2299 The loop-latch argument is VECT_DEF - the vector of partial sums.
2300 2. "Reduces" the vector of partial results VECT_DEF into a single result,
2301 by applying the operation specified by REDUC_CODE if available, or by
2302 other means (whole-vector shifts or a scalar loop).
2303 The function also creates a new phi node at the loop exit to preserve
2304 loop-closed form, as illustrated below.
2306 The flow at the entry to this function:
2308 loop:
2309 vec_def = phi <null, null> # REDUCTION_PHI
2310 VECT_DEF = vector_stmt # vectorized form of STMT
2311 s_loop = scalar_stmt # (scalar) STMT
2312 loop_exit:
2313 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2314 use <s_out0>
2315 use <s_out0>
2317 The above is transformed by this function into:
2319 loop:
2320 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2321 VECT_DEF = vector_stmt # vectorized form of STMT
2322 s_loop = scalar_stmt # (scalar) STMT
2323 loop_exit:
2324 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2325 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2326 v_out2 = reduce <v_out1>
2327 s_out3 = extract_field <v_out2, 0>
2328 s_out4 = adjust_result <s_out3>
2329 use <s_out4>
2330 use <s_out4>
2331 */
2333 static void
2337 gimple reduction_phi)
2338 {
2340 stmt_vec_info prev_phi_info;
2341 tree vectype;
2345 basic_block exit_bb;
2346 tree scalar_dest;
2347 tree scalar_type;
2349 gimple_stmt_iterator exit_gsi;
2350 tree vec_dest;
2352 tree new_name;
2355 gimple exit_phi;
2358 tree adjustment_def;
2360 tree orig_name;
2361 imm_use_iterator imm_iter;
2362 use_operand_p use_p;
2365 gimple orig_stmt;
2366 gimple use_stmt;
2373 {
2376 }
2379 {
2392 }
2398 /*** 1. Create the reduction def-use cycle ***/
2400 /* For the case of reduction, vect_get_vec_def_for_operand returns
2401 the scalar def before the loop, that defines the initial value
2402 of the reduction variable. */
2409 {
2410 /* 1.1 set the loop-entry arg of the reduction-phi: */
2413 /* 1.2 set the loop-latch arg for the reduction-phi: */
2419 {
2424 }
2427 }
2429 /*** 2. Create epilog code
2430 The reduction epilog code operates across the elements of the vector
2431 of partial results computed by the vectorized loop.
2432 The reduction epilog code consists of:
2433 step 1: compute the scalar result in a vector (v_out2)
2434 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2435 step 3: adjust the scalar result (s_out3) if needed.
2437 Step 1 can be accomplished using one the following three schemes:
2438 (scheme 1) using reduc_code, if available.
2439 (scheme 2) using whole-vector shifts, if available.
2440 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2441 combined.
2443 The overall epilog code looks like this:
2445 s_out0 = phi <s_loop> # original EXIT_PHI
2446 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2447 v_out2 = reduce <v_out1> # step 1
2448 s_out3 = extract_field <v_out2, 0> # step 2
2449 s_out4 = adjust_result <s_out3> # step 3
2451 (step 3 is optional, and steps 1 and 2 may be combined).
2452 Lastly, the uses of s_out0 are replaced by s_out4.
2454 ***/
2456 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2457 v_out1 = phi <v_loop> */
2463 {
2468 else
2469 {
2472 }
2475 }
2478 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
2479 (i.e. when reduc_code is not available) and in the final adjustment
2480 code (if needed). Also get the original scalar reduction variable as
2481 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
2482 represents a reduction pattern), the tree-code and scalar-def are
2483 taken from the original stmt that the pattern-stmt (STMT) replaces.
2484 Otherwise (it is a regular reduction) - the tree-code and scalar-def
2485 are taken from STMT. */
2489 {
2490 /* Regular reduction */
2492 }
2493 else
2494 {
2495 /* Reduction pattern */
2499 }
2508 /* In case this is a reduction in an inner-loop while vectorizing an outer
2509 loop - we don't need to extract a single scalar result at the end of the
2510 inner-loop. The final vector of partial results will be used in the
2511 vectorized outer-loop, or reduced to a scalar result at the end of the
2512 outer-loop. */
2516 /* FORNOW */
2519 /* 2.3 Create the reduction code, using one of the three schemes described
2520 above. */
2523 {
2524 tree tmp;
2526 /*** Case 1: Create:
2527 v_out2 = reduc_expr <v_out1> */
2540 }
2541 else
2542 {
2548 tree vec_temp;
2552 else
2555 /* Regardless of whether we have a whole vector shift, if we're
2556 emulating the operation via tree-vect-generic, we don't want
2557 to use it. Only the first round of the reduction is likely
2558 to still be profitable via emulation. */
2559 /* ??? It might be better to emit a reduction tree code here, so that
2560 tree-vect-generic can expand the first round via bit tricks. */
2563 else
2564 {
2568 }
2571 {
2572 /*** Case 2: Create:
2573 for (offset = VS/2; offset >= element_size; offset/=2)
2574 {
2575 Create: va' = vec_shift <va, offset>
2576 Create: va = vop <va, va'>
2577 } */
2588 {
2601 }
2604 }
2605 else
2606 {
2607 tree rhs;
2609 /*** Case 3: Create:
2610 s = extract_field <v_out2, 0>
2611 for (offset = element_size;
2612 offset < vector_size;
2613 offset += element_size;)
2614 {
2615 Create: s' = extract_field <v_out2, offset>
2616 Create: s = op <s, s'>
2617 } */
2625 bitsize_zero_node);
2634 {
2637 bitpos);
2645 new_scalar_dest,
2650 }
2653 }
2654 }
2656 /* 2.4 Extract the final scalar result. Create:
2657 s_out3 = extract_field <v_out2, bitpos> */
2660 {
2661 tree rhs;
2671 else
2679 }
2681 vect_finalize_reduction:
2683 /* 2.5 Adjust the final result by the initial value of the reduction
2684 variable. (When such adjustment is not needed, then
2685 'adjustment_def' is zero). For example, if code is PLUS we create:
2686 new_temp = loop_exit_def + adjustment_def */
2689 {
2691 {
2695 }
2696 else
2697 {
2701 }
2707 }
2710 /* 2.6 Handle the loop-exit phi */
2712 /* Replace uses of s_out0 with uses of s_out3:
2713 Find the loop-closed-use at the loop exit of the original scalar result.
2714 (The reduction result is expected to have two immediate uses - one at the
2715 latch block, and one at the loop exit). */
2718 {
2720 {
2723 }
2724 }
2725 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
2729 {
2731 {
2734 /* FORNOW. Currently not supporting the case that an inner-loop
2735 reduction is not used in the outer-loop (but only outside the
2736 outer-loop). */
2748 }
2750 /* Replace the uses: */
2755 }
2757 }
2760 /* Function vectorizable_reduction.
2762 Check if STMT performs a reduction operation that can be vectorized.
2763 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2764 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2765 Return FALSE if not a vectorizable STMT, TRUE otherwise.
2767 This function also handles reduction idioms (patterns) that have been
2768 recognized in advance during vect_pattern_recog. In this case, STMT may be
2769 of this form:
2770 X = pattern_expr (arg0, arg1, ..., X)
2771 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2772 sequence that had been detected and replaced by the pattern-stmt (STMT).
2774 In some cases of reduction patterns, the type of the reduction variable X is
2775 different than the type of the other arguments of STMT.
2776 In such cases, the vectype that is used when transforming STMT into a vector
2777 stmt is different than the vectype that is used to determine the
2778 vectorization factor, because it consists of a different number of elements
2779 than the actual number of elements that are being operated upon in parallel.
2781 For example, consider an accumulation of shorts into an int accumulator.
2782 On some targets it's possible to vectorize this pattern operating on 8
2783 shorts at a time (hence, the vectype for purposes of determining the
2784 vectorization factor should be V8HI); on the other hand, the vectype that
2785 is used to create the vector form is actually V4SI (the type of the result).
2787 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2788 indicates what is the actual level of parallelism (V8HI in the example), so
2789 that the right vectorization factor would be derived. This vectype
2790 corresponds to the type of arguments to the reduction stmt, and should *NOT*
2791 be used to create the vectorized stmt. The right vectype for the vectorized
2792 stmt is obtained from the type of the result X:
2793 get_vectype_for_scalar_type (TREE_TYPE (X))
2795 This means that, contrary to "regular" reductions (or "regular" stmts in
2796 general), the following equation:
2797 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2798 does *NOT* necessarily hold for reduction patterns. */
2800 bool
2803 {
2804 tree vec_dest;
2805 tree scalar_dest;
2816 tree def;
2817 gimple def_stmt;
2820 tree scalar_type;
2822 gimple orig_stmt;
2823 stmt_vec_info orig_stmt_info;
2832 tree reduc_def;
2842 /* FORNOW: SLP not supported. */
2846 /* 1. Is vectorizable reduction? */
2848 /* Not supportable if the reduction variable is used in the loop. */
2852 /* Reductions that are not used even in an enclosing outer-loop,
2853 are expected to be "live" (used out of the loop). */
2858 /* Make sure it was already recognized as a reduction computation. */
2862 /* 2. Has this been recognized as a reduction pattern?
2864 Check if STMT represents a pattern that has been recognized
2865 in earlier analysis stages. For stmts that represent a pattern,
2866 the STMT_VINFO_RELATED_STMT field records the last stmt in
2867 the original sequence that constitutes the pattern. */
2871 {
2876 }
2878 /* 3. Check the operands of the operation. The first operands are defined
2879 inside the loop body. The last operand is the reduction variable,
2880 which is defined by the loop-header-phi. */
2884 /* Flatten RHS */
2886 {
2890 {
2896 }
2897 else
2914 }
2922 /* All uses but the last are expected to be defined in the loop.
2923 The last use is the reduction variable. */
2925 {
2934 }
2942 else
2948 /* 4. Supportable by target? */
2950 /* 4.1. check support for the operation in the loop */
2953 {
2957 }
2960 {
2969 }
2971 /* Worthwhile without SIMD support? */
2975 {
2979 }
2981 /* 4.2. Check support for the epilog operation.
2983 If STMT represents a reduction pattern, then the type of the
2984 reduction variable may be different than the type of the rest
2985 of the arguments. For example, consider the case of accumulation
2986 of shorts into an int accumulator; The original code:
2987 S1: int_a = (int) short_a;
2988 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
2990 was replaced with:
2991 STMT: int_acc = widen_sum <short_a, int_acc>
2993 This means that:
2994 1. The tree-code that is used to create the vector operation in the
2995 epilog code (that reduces the partial results) is not the
2996 tree-code of STMT, but is rather the tree-code of the original
2997 stmt from the pattern that STMT is replacing. I.e, in the example
2998 above we want to use 'widen_sum' in the loop, but 'plus' in the
2999 epilog.
3000 2. The type (mode) we use to check available target support
3001 for the vector operation to be created in the *epilog*, is
3002 determined by the type of the reduction variable (in the example
3003 above we'd check this: plus_optab[vect_int_mode]).
3004 However the type (mode) we use to check available target support
3005 for the vector operation to be created *inside the loop*, is
3006 determined by the type of the other arguments to STMT (in the
3007 example we'd check this: widen_sum_optab[vect_short_mode]).
3009 This is contrary to "regular" reductions, in which the types of all
3010 the arguments are the same as the type of the reduction variable.
3011 For "regular" reductions we can therefore use the same vector type
3012 (and also the same tree-code) when generating the epilog code and
3013 when generating the code inside the loop. */
3016 {
3017 /* This is a reduction pattern: get the vectype from the type of the
3018 reduction variable, and get the tree-code from orig_stmt. */
3022 {
3024 {
3027 }
3029 }
3032 }
3033 else
3034 {
3035 /* Regular reduction: use the same vectype and tree-code as used for
3036 the vector code inside the loop can be used for the epilog code. */
3038 }
3044 {
3048 }
3050 {
3054 }
3057 {
3062 }
3064 /** Transform. **/
3069 /* Create the destination vector */
3072 /* In case the vectorization factor (VF) is bigger than the number
3073 of elements that we can fit in a vectype (nunits), we have to generate
3074 more than one vector stmt - i.e - we need to "unroll" the
3075 vector stmt by a factor VF/nunits. For more details see documentation
3076 in vectorizable_operation. */
3078 /* If the reduction is used in an outer loop we need to generate
3079 VF intermediate results, like so (e.g. for ncopies=2):
3080 r0 = phi (init, r0)
3081 r1 = phi (init, r1)
3082 r0 = x0 + r0;
3083 r1 = x1 + r1;
3084 (i.e. we generate VF results in 2 registers).
3085 In this case we have a separate def-use cycle for each copy, and therefore
3086 for each copy we get the vector def for the reduction variable from the
3087 respective phi node created for this copy.
3089 Otherwise (the reduction is unused in the loop nest), we can combine
3090 together intermediate results, like so (e.g. for ncopies=2):
3091 r = phi (init, r)
3092 r = x0 + r;
3093 r = x1 + r;
3094 (i.e. we generate VF/2 results in a single register).
3095 In this case for each copy we get the vector def for the reduction variable
3096 from the vectorized reduction operation generated in the previous iteration.
3097 */
3100 {
3103 }
3104 else
3110 {
3112 {
3113 /* Create the reduction-phi that defines the reduction-operand. */
3116 }
3118 /* Handle uses. */
3120 {
3123 {
3125 }
3127 /* Get the vector def for the reduction variable from the phi node */
3130 }
3131 else
3132 {
3140 else
3144 }
3146 /* Arguments are ready. create the new vector stmt. */
3149 else
3151 reduc_def);
3159 else
3163 }
3165 /* Finalize the reduction-phi (set its arguments) and create the
3166 epilog reduction code. */
3172 }
3174 /* Checks if CALL can be vectorized in type VECTYPE. Returns
3175 a function declaration if the target has a vectorized version
3176 of the function, or NULL_TREE if the function cannot be vectorized. */
3178 tree
3180 {
3184 /* We only handle functions that do not read or clobber memory -- i.e.
3185 const or novops ones. */
3196 vectype_in);
3197 }
3199 /* Function vectorizable_call.
3201 Check if STMT performs a function call that can be vectorized.
3202 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3203 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3204 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3206 bool
3208 {
3209 tree vec_dest;
3210 tree scalar_dest;
3219 gimple def_stmt;
3221 gimple new_stmt;
3233 /* FORNOW: SLP not supported. */
3237 /* Is STMT a vectorizable call? */
3244 /* Process function arguments. */
3248 /* Bail out if the function has more than two arguments, we
3249 do not have interesting builtin functions to vectorize with
3250 more than two arguments. No arguments is also not good. */
3255 {
3258 /* We can only handle calls with arguments of the same type. */
3261 {
3265 }
3269 {
3273 }
3274 }
3287 /* FORNOW */
3294 else
3297 /* For now, we only vectorize functions if a target specific builtin
3298 is available. TODO -- in some cases, it might be profitable to
3299 insert the calls for pieces of the vector, in order to be able
3300 to vectorize other operations in the loop. */
3303 {
3308 }
3314 else
3317 /* Sanity check: make sure that at least one copy of the vectorized stmt
3318 needs to be generated. */
3322 {
3328 }
3330 /** Transform. **/
3335 /* Handle def. */
3341 {
3344 {
3345 /* Build argument list for the vectorized call. */
3348 else
3352 {
3355 vec_oprnd0
3357 else
3358 vec_oprnd0
3362 }
3372 else
3376 }
3382 {
3383 /* Build argument list for the vectorized call. */
3386 else
3390 {
3393 {
3394 vec_oprnd0
3396 vec_oprnd1
3398 }
3399 else
3400 {
3401 vec_oprnd0
3403 vec_oprnd1
3405 }
3409 }
3419 else
3423 }
3430 /* No current target implements this case. */
3432 }
3436 /* The call in STMT might prevent it from being removed in dce.
3437 We however cannot remove it here, due to the way the ssa name
3438 it defines is mapped to the new definition. So just replace
3439 rhs of the statement with something harmless. */
3451 }
3454 /* Function vect_gen_widened_results_half
3456 Create a vector stmt whose code, type, number of arguments, and result
3457 variable are CODE, OP_TYPE, and VEC_DEST, and its arguments are
3458 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
3459 In the case that CODE is a CALL_EXPR, this means that a call to DECL
3460 needs to be created (DECL is a function-decl of a target-builtin).
3461 STMT is the original scalar stmt that we are vectorizing. */
3463 static gimple
3465 tree decl,
3468 gimple stmt)
3469 {
3470 gimple new_stmt;
3471 tree new_temp;
3472 tree sym;
3473 ssa_op_iter iter;
3475 /* Generate half of the widened result: */
3477 {
3478 /* Target specific support */
3481 else
3485 }
3486 else
3487 {
3488 /* Generic support */
3493 vec_oprnd1);
3496 }
3500 {
3502 {
3506 }
3507 }
3510 }
3513 /* Check if STMT performs a conversion operation, that can be vectorized.
3514 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3515 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3516 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3518 bool
3521 {
3522 tree vec_dest;
3523 tree scalar_dest;
3524 tree op0;
3530 tree new_temp;
3531 tree def;
3532 gimple def_stmt;
3535 stmt_vec_info prev_stmt_info;
3540 tree expr;
3542 tree builtin_decl;
3546 tree vop0;
3547 tree integral_type;
3551 /* Is STMT a vectorizable conversion? */
3569 /* Check types of lhs and rhs. */
3584 /* FORNOW */
3591 else
3597 /* Bail out if the types are both integral or non-integral. */
3606 else
3609 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3610 this, so we can safely override NCOPIES with 1 here. */
3614 /* Sanity check: make sure that at least one copy of the vectorized stmt
3615 needs to be generated. */
3618 /* Check the operands of the operation. */
3620 {
3624 }
3626 /* Supportable by target? */
3637 {
3641 }
3644 {
3646 /* FORNOW: SLP not supported. */
3649 }
3652 {
3655 }
3657 /** Transform. **/
3661 /* Handle def. */
3669 {
3672 {
3673 tree sym;
3674 ssa_op_iter iter;
3678 else
3681 builtin_decl =
3684 {
3685 /* Arguments are ready. create the new vector stmt. */
3691 SSA_OP_ALL_VIRTUALS)
3692 {
3696 }
3699 }
3703 else
3706 }
3710 /* In case the vectorization factor (VF) is bigger than the number
3711 of elements that we can fit in a vectype (nunits), we have to
3712 generate more than one vector stmt - i.e - we need to "unroll"
3713 the vector stmt by a factor VF/nunits. */
3715 {
3718 else
3723 /* Generate first half of the widened result: */
3724 new_stmt
3730 else
3734 /* Generate second half of the widened result: */
3735 new_stmt
3741 }
3745 /* In case the vectorization factor (VF) is bigger than the number
3746 of elements that we can fit in a vectype (nunits), we have to
3747 generate more than one vector stmt - i.e - we need to "unroll"
3748 the vector stmt by a factor VF/nunits. */
3750 {
3751 /* Handle uses. */
3753 {
3756 }
3757 else
3758 {
3761 }
3763 /* Arguments are ready. Create the new vector stmt. */
3766 vec_oprnd1);
3773 else
3777 }
3780 }
3786 }
3789 /* Function vectorizable_assignment.
3791 Check if STMT performs an assignment (copy) that can be vectorized.
3792 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3793 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3794 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3796 bool
3799 {
3800 tree vec_dest;
3801 tree scalar_dest;
3802 tree op;
3806 tree new_temp;
3807 tree def;
3808 gimple def_stmt;
3814 tree vop;
3816 /* Multiple types in SLP are handled by creating the appropriate number of
3817 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
3818 case of SLP. */
3821 else
3834 /* Is vectorizable assignment? */
3845 else
3849 {
3853 }
3856 {
3862 }
3864 /** Transform. **/
3868 /* Handle def. */
3871 /* Handle use. */
3874 /* Arguments are ready. create the new vector stmt. */
3876 {
3885 }
3889 }
3892 /* Function vect_min_worthwhile_factor.
3894 For a loop where we could vectorize the operation indicated by CODE,
3895 return the minimum vectorization factor that makes it worthwhile
3896 to use generic vectors. */
3897 static int
3899 {
3901 {
3915 }
3916 }
3919 /* Function vectorizable_induction
3921 Check if PHI performs an induction computation that can be vectorized.
3922 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3923 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3924 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3926 bool
3929 {
3936 tree vec_def;
3939 /* FORNOW. This restriction should be relaxed. */
3941 {
3945 }
3950 /* FORNOW: SLP not supported. */
3960 {
3966 }
3968 /** Transform. **/
3976 }
3979 /* Function vectorizable_operation.
3981 Check if STMT performs a binary or unary operation that can be vectorized.
3982 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3983 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3984 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3986 bool
3989 {
3990 tree vec_dest;
3991 tree scalar_dest;
3999 tree new_temp;
4001 optab optab;
4004 tree def;
4005 gimple def_stmt;
4008 stmt_vec_info prev_stmt_info;
4011 tree vectype_out;
4020 /* Multiple types in SLP are handled by creating the appropriate number of
4021 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4022 case of SLP. */
4025 else
4036 /* Is STMT a vectorizable binary/unary operation? */
4053 /* For pointer addition, we should use the normal plus for
4054 the vector addition. */
4058 /* Support only unary or binary operations. */
4061 {
4065 }
4069 {
4073 }
4076 {
4079 {
4083 }
4084 }
4086 /* If this is a shift/rotate, determine whether the shift amount is a vector,
4087 or scalar. If the shift/rotate amount is a vector, use the vector/vector
4088 shift optabs. */
4091 {
4094 /* vector shifted by vector */
4096 {
4100 }
4102 /* See if the machine has a vector shifted by scalar insn and if not
4103 then see if it has a vector shifted by vector insn */
4105 {
4110 {
4114 }
4115 else
4116 {
4119 && optab
4123 }
4124 }
4126 else
4127 {
4131 }
4132 }
4133 else
4136 /* Supportable by target? */
4138 {
4142 }
4146 {
4149 /* Check only during analysis. */
4157 }
4159 /* Worthwhile without SIMD support? Check only during analysis. */
4164 {
4168 }
4171 {
4177 }
4179 /** Transform. **/
4184 /* Handle def. */
4187 /* Allocate VECs for vector operands. In case of SLP, vector operands are
4188 created in the previous stages of the recursion, so no allocation is
4189 needed, except for the case of shift with scalar shift argument. In that
4190 case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
4191 be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
4192 In case of loop-based vectorization we allocate VECs of size 1. We
4193 allocate VEC_OPRNDS1 only in case of binary operation. */
4195 {
4199 }
4203 /* In case the vectorization factor (VF) is bigger than the number
4204 of elements that we can fit in a vectype (nunits), we have to generate
4205 more than one vector stmt - i.e - we need to "unroll" the
4206 vector stmt by a factor VF/nunits. In doing so, we record a pointer
4207 from one copy of the vector stmt to the next, in the field
4208 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
4209 stages to find the correct vector defs to be used when vectorizing
4210 stmts that use the defs of the current stmt. The example below illustrates
4211 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
4212 4 vectorized stmts):
4214 before vectorization:
4215 RELATED_STMT VEC_STMT
4216 S1: x = memref - -
4217 S2: z = x + 1 - -
4219 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
4220 there):
4221 RELATED_STMT VEC_STMT
4222 VS1_0: vx0 = memref0 VS1_1 -
4223 VS1_1: vx1 = memref1 VS1_2 -
4224 VS1_2: vx2 = memref2 VS1_3 -
4225 VS1_3: vx3 = memref3 - -
4226 S1: x = load - VS1_0
4227 S2: z = x + 1 - -
4229 step2: vectorize stmt S2 (done here):
4230 To vectorize stmt S2 we first need to find the relevant vector
4231 def for the first operand 'x'. This is, as usual, obtained from
4232 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
4233 that defines 'x' (S1). This way we find the stmt VS1_0, and the
4234 relevant vector def 'vx0'. Having found 'vx0' we can generate
4235 the vector stmt VS2_0, and as usual, record it in the
4236 STMT_VINFO_VEC_STMT of stmt S2.
4237 When creating the second copy (VS2_1), we obtain the relevant vector
4238 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
4239 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
4240 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
4241 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
4242 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
4243 chain of stmts and pointers:
4244 RELATED_STMT VEC_STMT
4245 VS1_0: vx0 = memref0 VS1_1 -
4246 VS1_1: vx1 = memref1 VS1_2 -
4247 VS1_2: vx2 = memref2 VS1_3 -
4248 VS1_3: vx3 = memref3 - -
4249 S1: x = load - VS1_0
4250 VS2_0: vz0 = vx0 + v1 VS2_1 -
4251 VS2_1: vz1 = vx1 + v1 VS2_2 -
4252 VS2_2: vz2 = vx2 + v1 VS2_3 -
4253 VS2_3: vz3 = vx3 + v1 - -
4254 S2: z = x + 1 - VS2_0 */
4258 {
4259 /* Handle uses. */
4261 {
4263 {
4264 /* Vector shl and shr insn patterns can be defined with scalar
4265 operand 2 (shift operand). In this case, use constant or loop
4266 invariant op1 directly, without extending it to vector mode
4267 first. */
4270 {
4276 {
4277 /* Store vec_oprnd1 for every vector stmt to be created
4278 for SLP_NODE. We check during the analysis that all the
4279 shift arguments are the same.
4280 TODO: Allow different constants for different vector
4281 stmts generated for an SLP instance. */
4284 }
4285 }
4286 }
4288 /* vec_oprnd1 is available if operand 1 should be of a scalar-type
4289 (a special case for certain kind of vector shifts); otherwise,
4290 operand 1 should be of a vector type (the usual case). */
4293 slp_node);
4294 else
4296 slp_node);
4297 }
4298 else
4301 /* Arguments are ready. Create the new vector stmt. */
4303 {
4312 }
4319 else
4322 }
4329 }
4332 /* Get vectorized definitions for loop-based vectorization. For the first
4333 operand we call vect_get_vec_def_for_operand() (with OPRND containing
4334 scalar operand), and for the rest we get a copy with
4335 vect_get_vec_def_for_stmt_copy() using the previous vector definition
4336 (stored in OPRND). See vect_get_vec_def_for_stmt_copy() for details.
4337 The vectors are collected into VEC_OPRNDS. */
4339 static void
4342 {
4343 tree vec_oprnd;
4345 /* Get first vector operand. */
4346 /* All the vector operands except the very first one (that is scalar oprnd)
4347 are stmt copies. */
4350 else
4355 /* Get second vector operand. */
4361 /* For conversion in multiple steps, continue to get operands
4362 recursively. */
4365 }
4368 /* Create vectorized demotion statements for vector operands from VEC_OPRNDS.
4369 For multi-step conversions store the resulting vectors and call the function
4370 recursively. */
4372 static void
4379 {
4382 gimple new_stmt;
4388 {
4389 /* Create demotion operation. */
4398 /* Store the resulting vector for next recursive call. */
4400 else
4401 {
4402 /* This is the last step of the conversion sequence. Store the
4403 vectors in SLP_NODE or in vector info of the scalar statement
4404 (or in STMT_VINFO_RELATED_STMT chain). */
4407 else
4408 {
4411 else
4415 }
4416 }
4417 }
4419 /* For multi-step demotion operations we first generate demotion operations
4420 from the source type to the intermediate types, and then combine the
4421 results (stored in VEC_OPRNDS) in demotion operation to the destination
4422 type. */
4424 {
4425 /* At each level of recursion we have have of the operands we had at the
4426 previous level. */
4431 }
4432 }
4435 /* Function vectorizable_type_demotion
4437 Check if STMT performs a binary or unary operation that involves
4438 type demotion, and if it can be vectorized.
4439 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4440 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4441 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4443 bool
4446 {
4447 tree vec_dest;
4448 tree scalar_dest;
4449 tree op0;
4453 tree def;
4454 gimple def_stmt;
4456 stmt_vec_info prev_stmt_info;
4459 tree vectype_out;
4462 tree vectype_in;
4474 /* Is STMT a vectorizable type-demotion operation? */
4499 /* Multiple types in SLP are handled by creating the appropriate number of
4500 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4501 case of SLP. */
4504 else
4516 /* Check the operands of the operation. */
4518 {
4522 }
4524 /* Supportable by target? */
4532 {
4538 }
4540 /** Transform. **/
4543 ncopies);
4545 /* In case of multi-step demotion, we first generate demotion operations to
4546 the intermediate types, and then from that types to the final one.
4547 We create vector destinations for the intermediate type (TYPES) received
4548 from supportable_narrowing_operation, and store them in the correct order
4549 for future use in vect_create_vectorized_demotion_stmts(). */
4552 else
4559 {
4562 {
4564 intermediate_type);
4566 }
4567 }
4569 /* In case the vectorization factor (VF) is bigger than the number
4570 of elements that we can fit in a vectype (nunits), we have to generate
4571 more than one vector stmt - i.e - we need to "unroll" the
4572 vector stmt by a factor VF/nunits. */
4576 {
4577 /* Handle uses. */
4580 else
4581 {
4587 }
4589 /* Arguments are ready. Create the new vector stmts. */
4595 }
4604 }
4607 /* Create vectorized promotion statements for vector operands from VEC_OPRNDS0
4608 and VEC_OPRNDS1 (for binary operations). For multi-step conversions store
4609 the resulting vectors and call the function recursively. */
4611 static void
4621 {
4632 {
4635 else
4638 /* Generate the two halves of promotion operation. */
4644 {
4647 }
4648 else
4649 {
4652 }
4655 {
4656 /* Store the results for the recursive call. */
4659 }
4660 else
4661 {
4662 /* Last step of promotion sequience - store the results. */
4664 {
4667 }
4668 else
4669 {
4672 else
4678 }
4679 }
4680 }
4683 {
4684 /* For multi-step promotion operation we first generate we call the
4685 function recurcively for every stage. We start from the input type,
4686 create promotion operations to the intermediate types, and then
4687 create promotions to the output type. */
4694 prev_stmt_info);
4695 }
4696 }
4699 /* Function vectorizable_type_promotion
4701 Check if STMT performs a binary or unary operation that involves
4702 type promotion, and if it can be vectorized.
4703 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4704 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4705 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4707 bool
4710 {
4711 tree vec_dest;
4712 tree scalar_dest;
4720 tree def;
4721 gimple def_stmt;
4723 stmt_vec_info prev_stmt_info;
4726 tree vectype_out;
4729 tree vectype_in;
4741 /* Is STMT a vectorizable type-promotion operation? */
4767 /* Multiple types in SLP are handled by creating the appropriate number of
4768 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4769 case of SLP. */
4772 else
4784 /* Check the operands of the operation. */
4786 {
4790 }
4794 {
4797 {
4801 }
4802 }
4804 /* Supportable by target? */
4810 /* Binary widening operation can only be supported directly by the
4811 architecture. */
4817 {
4823 }
4825 /** Transform. **/
4829 ncopies);
4831 /* Handle def. */
4832 /* In case of multi-step promotion, we first generate promotion operations
4833 to the intermediate types, and then from that types to the final one.
4834 We store vector destination in VEC_DSTS in the correct order for
4835 recursive creation of promotion operations in
4836 vect_create_vectorized_promotion_stmts(). Vector destinations are created
4837 according to TYPES recieved from supportable_widening_operation(). */
4840 else
4847 {
4850 {
4852 intermediate_type);
4854 }
4855 }
4858 {
4863 }
4865 /* In case the vectorization factor (VF) is bigger than the number
4866 of elements that we can fit in a vectype (nunits), we have to generate
4867 more than one vector stmt - i.e - we need to "unroll" the
4868 vector stmt by a factor VF/nunits. */
4872 {
4873 /* Handle uses. */
4875 {
4878 else
4879 {
4883 {
4886 }
4887 }
4888 }
4889 else
4890 {
4894 {
4897 }
4898 }
4900 /* Arguments are ready. Create the new vector stmts. */
4904 tmp_vec_dsts,
4908 }
4918 }
4921 /* Function vect_strided_store_supported.
4923 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
4924 and FALSE otherwise. */
4926 static bool
4928 {
4934 /* Check that the operation is supported. */
4940 {
4944 }
4947 == CODE_FOR_nothing
4950 {
4954 }
4957 }
4960 /* Function vect_permute_store_chain.
4962 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4963 a power of 2, generate interleave_high/low stmts to reorder the data
4964 correctly for the stores. Return the final references for stores in
4965 RESULT_CHAIN.
4967 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4968 The input is 4 vectors each containing 8 elements. We assign a number to each
4969 element, the input sequence is:
4971 1st vec: 0 1 2 3 4 5 6 7
4972 2nd vec: 8 9 10 11 12 13 14 15
4973 3rd vec: 16 17 18 19 20 21 22 23
4974 4th vec: 24 25 26 27 28 29 30 31
4976 The output sequence should be:
4978 1st vec: 0 8 16 24 1 9 17 25
4979 2nd vec: 2 10 18 26 3 11 19 27
4980 3rd vec: 4 12 20 28 5 13 21 30
4981 4th vec: 6 14 22 30 7 15 23 31
4983 i.e., we interleave the contents of the four vectors in their order.
4985 We use interleave_high/low instructions to create such output. The input of
4986 each interleave_high/low operation is two vectors:
4987 1st vec 2nd vec
4988 0 1 2 3 4 5 6 7
4989 the even elements of the result vector are obtained left-to-right from the
4990 high/low elements of the first vector. The odd elements of the result are
4991 obtained left-to-right from the high/low elements of the second vector.
4992 The output of interleave_high will be: 0 4 1 5
4993 and of interleave_low: 2 6 3 7
4996 The permutation is done in log LENGTH stages. In each stage interleave_high
4997 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4998 where the first argument is taken from the first half of DR_CHAIN and the
4999 second argument from it's second half.
5000 In our example,
5002 I1: interleave_high (1st vec, 3rd vec)
5003 I2: interleave_low (1st vec, 3rd vec)
5004 I3: interleave_high (2nd vec, 4th vec)
5005 I4: interleave_low (2nd vec, 4th vec)
5007 The output for the first stage is:
5009 I1: 0 16 1 17 2 18 3 19
5010 I2: 4 20 5 21 6 22 7 23
5011 I3: 8 24 9 25 10 26 11 27
5012 I4: 12 28 13 29 14 30 15 31
5014 The output of the second stage, i.e. the final result is:
5016 I1: 0 8 16 24 1 9 17 25
5017 I2: 2 10 18 26 3 11 19 27
5018 I3: 4 12 20 28 5 13 21 30
5019 I4: 6 14 22 30 7 15 23 31. */
5021 static bool
5024 gimple stmt,
5027 {
5029 gimple perm_stmt;
5031 tree scalar_dest;
5038 /* Check that the operation is supported. */
5045 {
5047 {
5051 /* Create interleaving stmt:
5052 in the case of big endian:
5053 high = interleave_high (vect1, vect2)
5054 and in the case of little endian:
5055 high = interleave_low (vect1, vect2). */
5060 {
5063 }
5064 else
5065 {
5068 }
5076 /* Create interleaving stmt:
5077 in the case of big endian:
5078 low = interleave_low (vect1, vect2)
5079 and in the case of little endian:
5080 low = interleave_high (vect1, vect2). */
5090 }
5092 }
5094 }
5097 /* Function vectorizable_store.
5099 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
5100 can be vectorized.
5101 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5102 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5103 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5105 bool
5107 slp_tree slp_node)
5108 {
5109 tree scalar_dest;
5110 tree data_ref;
5111 tree op;
5119 tree dummy;
5121 tree def;
5122 gimple def_stmt;
5136 stmt_vec_info first_stmt_vinfo;
5139 /* Multiple types in SLP are handled by creating the appropriate number of
5140 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
5141 case of SLP. */
5144 else
5149 /* FORNOW. This restriction should be relaxed. */
5151 {
5155 }
5163 /* Is vectorizable store? */
5177 {
5181 }
5183 /* If accesses through a pointer to vectype do not alias the original
5184 memory reference we have a problem. */
5188 {
5192 }
5195 {
5199 }
5202 /* FORNOW. In some cases can vectorize even if data-type not supported
5203 (e.g. - array initialization with 0). */
5211 {
5219 {
5220 /* STMT is the leader of the group. Check the operands of all the
5221 stmts of the group. */
5224 {
5228 {
5232 }
5234 }
5235 }
5236 }
5239 {
5243 }
5245 /** Transform. **/
5248 {
5254 /* FORNOW */
5257 /* We vectorize all the stmts of the interleaving group when we
5258 reach the last stmt in the group. */
5262 {
5265 }
5270 /* VEC_NUM is the number of vect stmts to be created for this group. */
5273 else
5275 }
5276 else
5277 {
5282 }
5294 /* In case the vectorization factor (VF) is bigger than the number
5295 of elements that we can fit in a vectype (nunits), we have to generate
5296 more than one vector stmt - i.e - we need to "unroll" the
5297 vector stmt by a factor VF/nunits. For more details see documentation in
5298 vect_get_vec_def_for_copy_stmt. */
5300 /* In case of interleaving (non-unit strided access):
5302 S1: &base + 2 = x2
5303 S2: &base = x0
5304 S3: &base + 1 = x1
5305 S4: &base + 3 = x3
5307 We create vectorized stores starting from base address (the access of the
5308 first stmt in the chain (S2 in the above example), when the last store stmt
5309 of the chain (S4) is reached:
5311 VS1: &base = vx2
5312 VS2: &base + vec_size*1 = vx0
5313 VS3: &base + vec_size*2 = vx1
5314 VS4: &base + vec_size*3 = vx3
5316 Then permutation statements are generated:
5318 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
5319 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
5320 ...
5322 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
5323 (the order of the data-refs in the output of vect_permute_store_chain
5324 corresponds to the order of scalar stmts in the interleaving chain - see
5325 the documentation of vect_permute_store_chain()).
5327 In case of both multiple types and interleaving, above vector stores and
5328 permutation stmts are created for every copy. The result vector stmts are
5329 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
5330 STMT_VINFO_RELATED_STMT for the next copies.
5331 */
5335 {
5336 gimple new_stmt;
5337 gimple ptr_incr;
5340 {
5342 {
5343 /* Get vectorized arguments for SLP_NODE. */
5347 }
5348 else
5349 {
5350 /* For interleaved stores we collect vectorized defs for all the
5351 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
5352 used as an input to vect_permute_store_chain(), and OPRNDS as
5353 an input to vect_get_vec_def_for_stmt_copy() for the next copy.
5355 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
5356 OPRNDS are of size 1. */
5359 {
5360 /* Since gaps are not supported for interleaved stores,
5361 GROUP_SIZE is the exact number of stmts in the chain.
5362 Therefore, NEXT_STMT can't be NULL_TREE. In case that
5363 there is no interleaving, GROUP_SIZE is 1, and only one
5364 iteration of the loop will be executed. */
5370 NULL);
5374 }
5375 }
5381 }
5382 else
5383 {
5384 /* For interleaved stores we created vectorized defs for all the
5385 defs stored in OPRNDS in the previous iteration (previous copy).
5386 DR_CHAIN is then used as an input to vect_permute_store_chain(),
5387 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
5388 next copy.
5389 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
5390 OPRNDS are of size 1. */
5392 {
5398 }
5399 dataref_ptr =
5401 }
5404 {
5406 /* Permute. */
5410 }
5414 {
5416 /* Bump the vector pointer. */
5418 NULL_TREE);
5423 /* For strided stores vectorized defs are interleaved in
5424 vect_permute_store_chain(). */
5428 /* Arguments are ready. Create the new vector stmt. */
5438 else
5445 }
5446 }
5454 }
5457 /* Function vect_setup_realignment
5459 This function is called when vectorizing an unaligned load using
5460 the dr_explicit_realign[_optimized] scheme.
5461 This function generates the following code at the loop prolog:
5463 p = initial_addr;
5464 x msq_init = *(floor(p)); # prolog load
5465 realignment_token = call target_builtin;
5466 loop:
5467 x msq = phi (msq_init, ---)
5469 The stmts marked with x are generated only for the case of
5470 dr_explicit_realign_optimized.
5472 The code above sets up a new (vector) pointer, pointing to the first
5473 location accessed by STMT, and a "floor-aligned" load using that pointer.
5474 It also generates code to compute the "realignment-token" (if the relevant
5475 target hook was defined), and creates a phi-node at the loop-header bb
5476 whose arguments are the result of the prolog-load (created by this
5477 function) and the result of a load that takes place in the loop (to be
5478 created by the caller to this function).
5480 For the case of dr_explicit_realign_optimized:
5481 The caller to this function uses the phi-result (msq) to create the
5482 realignment code inside the loop, and sets up the missing phi argument,
5483 as follows:
5484 loop:
5485 msq = phi (msq_init, lsq)
5486 lsq = *(floor(p')); # load in loop
5487 result = realign_load (msq, lsq, realignment_token);
5489 For the case of dr_explicit_realign:
5490 loop:
5491 msq = *(floor(p)); # load in loop
5492 p' = p + (VS-1);
5493 lsq = *(floor(p')); # load in loop
5494 result = realign_load (msq, lsq, realignment_token);
5496 Input:
5497 STMT - (scalar) load stmt to be vectorized. This load accesses
5498 a memory location that may be unaligned.
5499 BSI - place where new code is to be inserted.
5500 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
5501 is used.
5503 Output:
5504 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
5505 target hook, if defined.
5506 Return value - the result of the loop-header phi node. */
5508 static tree
5512 tree init_addr,
5514 {
5519 edge pe;
5521 tree vec_dest;
5522 gimple inc;
5523 tree ptr;
5524 tree data_ref;
5525 gimple new_stmt;
5526 basic_block new_bb;
5528 tree new_temp;
5529 gimple phi_stmt;
5541 /* We need to generate three things:
5542 1. the misalignment computation
5543 2. the extra vector load (for the optimized realignment scheme).
5544 3. the phi node for the two vectors from which the realignment is
5545 done (for the optimized realignment scheme).
5546 */
5548 /* 1. Determine where to generate the misalignment computation.
5550 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
5551 calculation will be generated by this function, outside the loop (in the
5552 preheader). Otherwise, INIT_ADDR had already been computed for us by the
5553 caller, inside the loop.
5555 Background: If the misalignment remains fixed throughout the iterations of
5556 the loop, then both realignment schemes are applicable, and also the
5557 misalignment computation can be done outside LOOP. This is because we are
5558 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
5559 are a multiple of VS (the Vector Size), and therefore the misalignment in
5560 different vectorized LOOP iterations is always the same.
5561 The problem arises only if the memory access is in an inner-loop nested
5562 inside LOOP, which is now being vectorized using outer-loop vectorization.
5563 This is the only case when the misalignment of the memory access may not
5564 remain fixed throughout the iterations of the inner-loop (as explained in
5565 detail in vect_supportable_dr_alignment). In this case, not only is the
5566 optimized realignment scheme not applicable, but also the misalignment
5567 computation (and generation of the realignment token that is passed to
5568 REALIGN_LOAD) have to be done inside the loop.
5570 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
5571 or not, which in turn determines if the misalignment is computed inside
5572 the inner-loop, or outside LOOP. */
5575 {
5578 }
5581 /* 2. Determine where to generate the extra vector load.
5583 For the optimized realignment scheme, instead of generating two vector
5584 loads in each iteration, we generate a single extra vector load in the
5585 preheader of the loop, and in each iteration reuse the result of the
5586 vector load from the previous iteration. In case the memory access is in
5587 an inner-loop nested inside LOOP, which is now being vectorized using
5588 outer-loop vectorization, we need to determine whether this initial vector
5589 load should be generated at the preheader of the inner-loop, or can be
5590 generated at the preheader of LOOP. If the memory access has no evolution
5591 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
5592 to be generated inside LOOP (in the preheader of the inner-loop). */
5595 {
5600 }
5601 else
5606 /* 3. For the case of the optimized realignment, create the first vector
5607 load at the loop preheader. */
5610 {
5611 /* Create msq_init = *(floor(p1)) in the loop preheader */
5626 }
5628 /* 4. Create realignment token using a target builtin, if available.
5629 It is done either inside the containing loop, or before LOOP (as
5630 determined above). */
5633 {
5634 tree builtin_decl;
5636 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
5639 else
5640 {
5641 /* Generate the INIT_ADDR computation outside LOOP. */
5647 }
5651 vec_dest =
5659 else
5660 {
5661 /* Generate the misalignment computation outside LOOP. */
5665 }
5669 /* The result of the CALL_EXPR to this builtin is determined from
5670 the value of the parameter and no global variables are touched
5671 which makes the builtin a "const" function. Requiring the
5672 builtin to have the "const" attribute makes it unnecessary
5673 to call mark_call_clobbered. */
5675 }
5684 /* 5. Create msq = phi <msq_init, lsq> in loop */
5694 }
5697 /* Function vect_strided_load_supported.
5699 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
5700 and FALSE otherwise. */
5702 static bool
5704 {
5711 optab_default);
5713 {
5717 }
5720 {
5724 }
5727 optab_default);
5729 {
5733 }
5736 {
5740 }
5742 }
5745 /* Function vect_permute_load_chain.
5747 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
5748 a power of 2, generate extract_even/odd stmts to reorder the input data
5749 correctly. Return the final references for loads in RESULT_CHAIN.
5751 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
5752 The input is 4 vectors each containing 8 elements. We assign a number to each
5753 element, the input sequence is:
5755 1st vec: 0 1 2 3 4 5 6 7
5756 2nd vec: 8 9 10 11 12 13 14 15
5757 3rd vec: 16 17 18 19 20 21 22 23
5758 4th vec: 24 25 26 27 28 29 30 31
5760 The output sequence should be:
5762 1st vec: 0 4 8 12 16 20 24 28
5763 2nd vec: 1 5 9 13 17 21 25 29
5764 3rd vec: 2 6 10 14 18 22 26 30
5765 4th vec: 3 7 11 15 19 23 27 31
5767 i.e., the first output vector should contain the first elements of each
5768 interleaving group, etc.
5770 We use extract_even/odd instructions to create such output. The input of each
5771 extract_even/odd operation is two vectors
5772 1st vec 2nd vec
5773 0 1 2 3 4 5 6 7
5775 and the output is the vector of extracted even/odd elements. The output of
5776 extract_even will be: 0 2 4 6
5777 and of extract_odd: 1 3 5 7
5780 The permutation is done in log LENGTH stages. In each stage extract_even and
5781 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
5782 order. In our example,
5784 E1: extract_even (1st vec, 2nd vec)
5785 E2: extract_odd (1st vec, 2nd vec)
5786 E3: extract_even (3rd vec, 4th vec)
5787 E4: extract_odd (3rd vec, 4th vec)
5789 The output for the first stage will be:
5791 E1: 0 2 4 6 8 10 12 14
5792 E2: 1 3 5 7 9 11 13 15
5793 E3: 16 18 20 22 24 26 28 30
5794 E4: 17 19 21 23 25 27 29 31
5796 In order to proceed and create the correct sequence for the next stage (or
5797 for the correct output, if the second stage is the last one, as in our
5798 example), we first put the output of extract_even operation and then the
5799 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
5800 The input for the second stage is:
5802 1st vec (E1): 0 2 4 6 8 10 12 14
5803 2nd vec (E3): 16 18 20 22 24 26 28 30
5804 3rd vec (E2): 1 3 5 7 9 11 13 15
5805 4th vec (E4): 17 19 21 23 25 27 29 31
5807 The output of the second stage:
5809 E1: 0 4 8 12 16 20 24 28
5810 E2: 2 6 10 14 18 22 26 30
5811 E3: 1 5 9 13 17 21 25 29
5812 E4: 3 7 11 15 19 23 27 31
5814 And RESULT_CHAIN after reordering:
5816 1st vec (E1): 0 4 8 12 16 20 24 28
5817 2nd vec (E3): 1 5 9 13 17 21 25 29
5818 3rd vec (E2): 2 6 10 14 18 22 26 30
5819 4th vec (E4): 3 7 11 15 19 23 27 31. */
5821 static bool
5824 gimple stmt,
5827 {
5829 gimple perm_stmt;
5834 /* Check that the operation is supported. */
5840 {
5842 {
5846 /* data_ref = permute_even (first_data_ref, second_data_ref); */
5853 second_vect);
5862 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
5869 second_vect);
5876 }
5878 }
5880 }
5883 /* Function vect_transform_strided_load.
5885 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
5886 to perform their permutation and ascribe the result vectorized statements to
5887 the scalar statements.
5888 */
5890 static bool
5893 {
5899 tree tmp_data_ref;
5901 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
5902 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
5903 vectors, that are ready for vector computation. */
5905 /* Permute. */
5909 /* Put a permuted data-ref in the VECTORIZED_STMT field.
5910 Since we scan the chain starting from it's first node, their order
5911 corresponds the order of data-refs in RESULT_CHAIN. */
5915 {
5919 /* Skip the gaps. Loads created for the gaps will be removed by dead
5920 code elimination pass later. No need to check for the first stmt in
5921 the group, since it always exists.
5922 DR_GROUP_GAP is the number of steps in elements from the previous
5923 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
5924 correspond to the gaps.
5925 */
5928 {
5929 gap_count++;
5931 }
5934 {
5936 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
5937 copies, and we put the new vector statement in the first available
5938 RELATED_STMT. */
5941 else
5942 {
5943 gimple prev_stmt =
5945 gimple rel_stmt =
5948 {
5951 }
5953 }
5956 /* If NEXT_STMT accesses the same DR as the previous statement,
5957 put the same TMP_DATA_REF as its vectorized statement; otherwise
5958 get the next data-ref from RESULT_CHAIN. */
5961 }
5962 }
5966 }
5969 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
5970 building a vector of type MASK_TYPE from it) and two input vectors placed in
5971 DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
5972 shifting by STRIDE elements of DR_CHAIN for every copy.
5973 (STRIDE is the number of vectorized stmts for NODE divided by the number of
5974 copies).
5975 VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
5976 the created stmts must be inserted. */
5987 {
5990 stmt_vec_info next_stmt_info;
5993 tree sym;
5994 ssa_op_iter iter;
5997 /* Create a vector mask. */
6000 t);
6009 /* Initialize the vect stmts of NODE to properly insert the generated
6010 stmts later. */
6017 {
6021 /* Build argument list for the vectorized call. */
6028 /* Generate the permute statement. */
6034 {
6038 }
6040 /* Store the vector statement in NODE. */
6046 }
6048 /* Mark the scalar stmt as vectorized. */
6051 }
6054 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
6055 return in CURRENT_MASK_ELEMENT its equivalent in target specific
6056 representation. Check that the mask is valid and return FALSE if not.
6057 Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
6058 the next vector, i.e., the current first vector is not needed. */
6060 static bool
6065 {
6071 /* Convert to target specific representation. */
6073 /* Adjust the value in case it's a mask for second and third vectors. */
6079 /* We have only one input vector to permute but the mask accesses values in
6080 the next vector as well. */
6082 {
6084 {
6087 }
6090 }
6092 /* The mask requires the next vector. */
6094 {
6096 {
6097 /* We either need the first vector too or have already moved to the
6098 next vector. In both cases, this permutation needs three
6099 vectors. */
6101 {
6105 }
6108 }
6110 /* We move to the next vector, dropping the first one and working with
6111 the second and the third - we need to adjust the values of the mask
6112 accordingly. */
6120 }
6124 /* This was the last element of this mask. Start a new one. */
6126 {
6130 }
6133 }
6136 /* Generate vector permute statements from a list of loads in DR_CHAIN.
6137 If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
6138 permute statements for SLP_NODE_INSTANCE. */
6139 bool
6143 {
6147 slp_tree node;
6149 gimple next_scalar_stmt;
6157 {
6159 {
6162 }
6165 }
6170 {
6172 {
6175 }
6178 }
6187 /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
6188 unrolling factor. */
6194 /* Number of copies is determined by the final vectorization factor
6195 relatively to SLP_NODE_INSTANCE unrolling factor. */
6198 /* Generate permutation masks for every NODE. Number of masks for each NODE
6199 is equal to GROUP_SIZE.
6200 E.g., we have a group of three nodes with three loads from the same
6201 location in each node, and the vector size is 4. I.e., we have a
6202 a0b0c0a1b1c1... sequence and we need to create the following vectors:
6203 for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
6204 for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
6205 ...
6207 The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9} (in target
6208 scpecific type, e.g., in bytes for Altivec.
6209 The last mask is illegal since we assume two operands for permute
6210 operation, and the mask element values can't be outside that range. Hence,
6211 the last mask must be converted into {2,5,5,5}.
6212 For the first two permutations we need the first and the second input
6213 vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
6214 we need the second and the third vectors: {b1,c1,a2,b2} and
6215 {c2,a3,b3,c3}. */
6220 i++)
6221 {
6229 else
6233 {
6235 {
6238 {
6245 }
6248 {
6251 {
6253 {
6256 }
6265 vect_stmts_counter++);
6266 }
6267 }
6268 }
6269 }
6270 }
6274 }
6276 /* vectorizable_load.
6278 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
6279 can be vectorized.
6280 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
6281 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
6282 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6284 bool
6287 {
6288 tree scalar_dest;
6292 stmt_vec_info prev_stmt_info;
6299 tree new_temp;
6302 tree dummy;
6305 gimple ptr_incr;
6315 gimple first_stmt;
6316 tree scalar_type;
6325 /* Multiple types in SLP are handled by creating the appropriate number of
6326 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
6327 case of SLP. */
6330 else
6335 /* FORNOW. This restriction should be relaxed. */
6337 {
6341 }
6352 /* Is vectorizable load? */
6372 /* FORNOW. In some cases can vectorize even if data-type not supported
6373 (e.g. - data copies). */
6375 {
6379 }
6381 /* If accesses through a pointer to vectype do not alias the original
6382 memory reference we have a problem. */
6386 {
6390 }
6392 /* Check if the load is a part of an interleaving chain. */
6394 {
6396 /* FORNOW */
6399 /* Check if interleaving is supported. */
6403 }
6406 {
6410 }
6415 /** Transform. **/
6418 {
6420 /* Check if the chain of loads is already vectorized. */
6422 {
6425 }
6429 /* VEC_NUM is the number of vect stmts to be created for this group. */
6431 {
6434 }
6435 else
6439 }
6440 else
6441 {
6445 }
6450 /* In case the vectorization factor (VF) is bigger than the number
6451 of elements that we can fit in a vectype (nunits), we have to generate
6452 more than one vector stmt - i.e - we need to "unroll" the
6453 vector stmt by a factor VF/nunits. In doing so, we record a pointer
6454 from one copy of the vector stmt to the next, in the field
6455 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
6456 stages to find the correct vector defs to be used when vectorizing
6457 stmts that use the defs of the current stmt. The example below illustrates
6458 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
6459 4 vectorized stmts):
6461 before vectorization:
6462 RELATED_STMT VEC_STMT
6463 S1: x = memref - -
6464 S2: z = x + 1 - -
6466 step 1: vectorize stmt S1:
6467 We first create the vector stmt VS1_0, and, as usual, record a
6468 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
6469 Next, we create the vector stmt VS1_1, and record a pointer to
6470 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
6471 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
6472 stmts and pointers:
6473 RELATED_STMT VEC_STMT
6474 VS1_0: vx0 = memref0 VS1_1 -
6475 VS1_1: vx1 = memref1 VS1_2 -
6476 VS1_2: vx2 = memref2 VS1_3 -
6477 VS1_3: vx3 = memref3 - -
6478 S1: x = load - VS1_0
6479 S2: z = x + 1 - -
6481 See in documentation in vect_get_vec_def_for_stmt_copy for how the
6482 information we recorded in RELATED_STMT field is used to vectorize
6483 stmt S2. */
6485 /* In case of interleaving (non-unit strided access):
6487 S1: x2 = &base + 2
6488 S2: x0 = &base
6489 S3: x1 = &base + 1
6490 S4: x3 = &base + 3
6492 Vectorized loads are created in the order of memory accesses
6493 starting from the access of the first stmt of the chain:
6495 VS1: vx0 = &base
6496 VS2: vx1 = &base + vec_size*1
6497 VS3: vx3 = &base + vec_size*2
6498 VS4: vx4 = &base + vec_size*3
6500 Then permutation statements are generated:
6502 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
6503 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
6504 ...
6506 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
6507 (the order of the data-refs in the output of vect_permute_load_chain
6508 corresponds to the order of scalar stmts in the interleaving chain - see
6509 the documentation of vect_permute_load_chain()).
6510 The generation of permutation stmts and recording them in
6511 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
6513 In case of both multiple types and interleaving, the vector loads and
6514 permutation stmts above are created for every copy. The result vector stmts
6515 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
6516 STMT_VINFO_RELATED_STMT for the next copies. */
6518 /* If the data reference is aligned (dr_aligned) or potentially unaligned
6519 on a target that supports unaligned accesses (dr_unaligned_supported)
6520 we generate the following code:
6521 p = initial_addr;
6522 indx = 0;
6523 loop {
6524 p = p + indx * vectype_size;
6525 vec_dest = *(p);
6526 indx = indx + 1;
6527 }
6529 Otherwise, the data reference is potentially unaligned on a target that
6530 does not support unaligned accesses (dr_explicit_realign_optimized) -
6531 then generate the following code, in which the data in each iteration is
6532 obtained by two vector loads, one from the previous iteration, and one
6533 from the current iteration:
6534 p1 = initial_addr;
6535 msq_init = *(floor(p1))
6536 p2 = initial_addr + VS - 1;
6537 realignment_token = call target_builtin;
6538 indx = 0;
6539 loop {
6540 p2 = p2 + indx * vectype_size
6541 lsq = *(floor(p2))
6542 vec_dest = realign_load (msq, lsq, realignment_token)
6543 indx = indx + 1;
6544 msq = lsq;
6545 } */
6547 /* If the misalignment remains the same throughout the execution of the
6548 loop, we can create the init_addr and permutation mask at the loop
6549 preheader. Otherwise, it needs to be created inside the loop.
6550 This can only occur when vectorizing memory accesses in the inner-loop
6551 nested within an outer-loop that is being vectorized. */
6556 {
6559 }
6564 {
6569 {
6572 }
6573 }
6574 else
6579 {
6580 /* 1. Create the vector pointer update chain. */
6586 else
6587 dataref_ptr =
6591 {
6594 NULL_TREE);
6596 /* 2. Create the vector-load in the loop. */
6598 {
6604 {
6609 data_ref =
6612 }
6614 {
6621 dr_explicit_realign,
6639 }
6645 }
6653 /* 3. Handle explicit realignment if necessary/supported. Create in
6654 loop: vec_dest = realign_load (msq, lsq, realignment_token) */
6657 {
6658 tree tmp;
6665 realignment_token);
6672 {
6677 }
6678 }
6680 /* 4. Handle invariant-load. */
6682 {
6686 {
6691 /* CHECKME: bitpos depends on endianess? */
6695 vec_dest =
6704 /* FIXME: use build_constructor directly. */
6708 }
6709 else
6711 }
6713 /* Collect vector loads and later create their permutation in
6714 vect_transform_strided_load (). */
6718 /* Store vector loads in the corresponding SLP_NODE. */
6721 }
6727 {
6731 {
6734 }
6735 }
6736 else
6737 {
6739 {
6746 }
6747 else
6748 {
6751 else
6754 }
6755 }
6756 }
6762 }
6765 /* Function vectorizable_live_operation.
6767 STMT computes a value that is used outside the loop. Check if
6768 it can be supported. */
6770 bool
6774 {
6780 tree op;
6781 tree def;
6782 gimple def_stmt;
6798 /* FORNOW. CHECKME. */
6808 /* FORNOW: support only if all uses are invariant. This means
6809 that the scalar operations can remain in place, unvectorized.
6810 The original last scalar value that they compute will be used. */
6813 {
6816 else
6819 {
6823 }
6827 }
6829 /* No transformation is required for the cases we currently support. */
6831 }
6834 /* Function vect_is_simple_cond.
6836 Input:
6837 LOOP - the loop that is being vectorized.
6838 COND - Condition that is checked for simple use.
6840 Returns whether a COND can be vectorized. Checks whether
6841 condition operands are supportable using vec_is_simple_use. */
6843 static bool
6845 {
6847 tree def;
6857 {
6861 }
6867 {
6871 }
6877 }
6879 /* vectorizable_condition.
6881 Check if STMT is conditional modify expression that can be vectorized.
6882 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
6883 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
6884 at BSI.
6886 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6888 bool
6891 {
6900 tree new_temp;
6903 tree def;
6919 /* FORNOW: SLP not supported. */
6923 /* FORNOW: not yet supported. */
6925 {
6929 }
6931 /* Is vectorizable conditional operation? */
6949 /* We do not handle two different vector types for the condition
6950 and the values. */
6955 {
6960 }
6967 {
6972 }
6982 {
6985 }
6987 /* Transform */
6989 /* Handle def. */
6993 /* Handle cond expr. */
6994 vec_cond_lhs =
6996 vec_cond_rhs =
7001 /* Arguments are ready. Create the new vector stmt. */
7013 }
7016 /* Function vect_transform_stmt.
7018 Create a vectorized stmt to replace STMT, and insert it at BSI. */
7020 static bool
7023 slp_instance slp_node_instance)
7024 {
7028 gimple orig_stmt_in_pattern;
7032 {
7066 slp_node_instance);
7074 {
7075 /* In case of interleaving, the whole chain is vectorized when the
7076 last store in the chain is reached. Store stmts before the last
7077 one are skipped, and there vec_stmt_info shouldn't be freed
7078 meanwhile. */
7082 }
7083 else
7106 {
7110 }
7111 }
7115 {
7118 }
7121 {
7125 {
7127 /* STMT was inserted by the vectorizer to replace a computation idiom.
7128 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
7129 computed this idiom. We need to record a pointer to VEC_STMT in
7130 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
7131 documentation of vect_pattern_recog. */
7133 {
7136 }
7137 }
7138 }
7141 }
7144 /* This function builds ni_name = number of iterations loop executes
7145 on the loop preheader. */
7147 static tree
7149 {
7152 edge pe;
7162 {
7165 }
7168 }
7171 /* This function generates the following statements:
7173 ni_name = number of iterations loop executes
7174 ratio = ni_name / vf
7175 ratio_mult_vf_name = ratio * vf
7177 and places them at the loop preheader edge. */
7179 static void
7184 {
7186 edge pe;
7187 basic_block new_bb;
7188 gimple_seq stmts;
7189 tree ni_name;
7190 tree var;
7191 tree ratio_name;
7192 tree ratio_mult_vf_name;
7196 tree log_vf;
7200 /* Generate temporary variable that contains
7201 number of iterations loop executes. */
7206 /* Create: ratio = ni >> log2(vf) */
7210 {
7219 }
7221 /* Create: ratio_mult_vf = ratio << log2 (vf). */
7226 {
7236 }
7243 }
7246 /* Function vect_update_ivs_after_vectorizer.
7248 "Advance" the induction variables of LOOP to the value they should take
7249 after the execution of LOOP. This is currently necessary because the
7250 vectorizer does not handle induction variables that are used after the
7251 loop. Such a situation occurs when the last iterations of LOOP are
7252 peeled, because:
7253 1. We introduced new uses after LOOP for IVs that were not originally used
7254 after LOOP: the IVs of LOOP are now used by an epilog loop.
7255 2. LOOP is going to be vectorized; this means that it will iterate N/VF
7256 times, whereas the loop IVs should be bumped N times.
7258 Input:
7259 - LOOP - a loop that is going to be vectorized. The last few iterations
7260 of LOOP were peeled.
7261 - NITERS - the number of iterations that LOOP executes (before it is
7262 vectorized). i.e, the number of times the ivs should be bumped.
7263 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
7264 coming out from LOOP on which there are uses of the LOOP ivs
7265 (this is the path from LOOP->exit to epilog_loop->preheader).
7267 The new definitions of the ivs are placed in LOOP->exit.
7268 The phi args associated with the edge UPDATE_E in the bb
7269 UPDATE_E->dest are updated accordingly.
7271 Assumption 1: Like the rest of the vectorizer, this function assumes
7272 a single loop exit that has a single predecessor.
7274 Assumption 2: The phi nodes in the LOOP header and in update_bb are
7275 organized in the same order.
7277 Assumption 3: The access function of the ivs is simple enough (see
7278 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
7280 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
7281 coming out of LOOP on which the ivs of LOOP are used (this is the path
7282 that leads to the epilog loop; other paths skip the epilog loop). This
7283 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
7284 needs to have its phis updated.
7285 */
7287 static void
7289 edge update_e)
7290 {
7297 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
7299 /* Make sure there exists a single-predecessor exit bb: */
7305 {
7307 tree evolution_part;
7308 tree init_expr;
7309 tree step_expr;
7311 gimple_stmt_iterator last_gsi;
7316 {
7319 }
7321 /* Skip virtual phi's. */
7323 {
7327 }
7329 /* Skip reduction phis. */
7331 {
7335 }
7340 evolution_part =
7344 /* FORNOW: We do not support IVs whose evolution function is a polynomial
7345 of degree >= 2 or exponential. */
7354 init_expr,
7358 else
7362 niters),
7363 step_expr),
7364 init_expr);
7375 /* Fix phi expressions in the successor bb. */
7377 }
7378 }
7380 /* Return the more conservative threshold between the
7381 min_profitable_iters returned by the cost model and the user
7382 specified threshold, if provided. */
7384 static unsigned int
7387 {
7394 /* Use the cost model only if it is more conservative than user specified
7395 threshold. */
7398 && (!min_scalar_loop_bound
7406 }
7408 /* Function vect_do_peeling_for_loop_bound
7410 Peel the last iterations of the loop represented by LOOP_VINFO.
7411 The peeled iterations form a new epilog loop. Given that the loop now
7412 iterates NITERS times, the new epilog loop iterates
7413 NITERS % VECTORIZATION_FACTOR times.
7415 The original loop will later be made to iterate
7416 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
7418 static void
7420 {
7424 edge update_e;
7425 basic_block preheader;
7436 /* Generate the following variables on the preheader of original loop:
7438 ni_name = number of iteration the original loop executes
7439 ratio = ni_name / vf
7440 ratio_mult_vf_name = ratio * vf */
7446 /* If cost model check not done during versioning and
7447 peeling for alignment. */
7451 {
7454 /* Get profitability threshold for vectorized loop. */
7458 min_profitable_iters);
7459 }
7466 #ifdef ENABLE_CHECKING
7468 #endif
7470 /* A guard that controls whether the new_loop is to be executed or skipped
7471 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
7472 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
7473 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
7474 is on the path where the LOOP IVs are used and need to be updated. */
7479 else
7482 /* Update IVs of original loop as if they were advanced
7483 by ratio_mult_vf_name steps. */
7486 /* After peeling we have to reset scalar evolution analyzer. */
7490 }
7493 /* Function vect_gen_niters_for_prolog_loop
7495 Set the number of iterations for the loop represented by LOOP_VINFO
7496 to the minimum between LOOP_NITERS (the original iteration count of the loop)
7497 and the misalignment of DR - the data reference recorded in
7498 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
7499 this loop, the data reference DR will refer to an aligned location.
7501 The following computation is generated:
7503 If the misalignment of DR is known at compile time:
7504 addr_mis = int mis = DR_MISALIGNMENT (dr);
7505 Else, compute address misalignment in bytes:
7506 addr_mis = addr & (vectype_size - 1)
7508 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
7510 (elem_size = element type size; an element is the scalar element whose type
7511 is the inner type of the vectype)
7513 When the step of the data-ref in the loop is not 1 (as in interleaved data
7514 and SLP), the number of iterations of the prolog must be divided by the step
7515 (which is equal to the size of interleaved group).
7517 The above formulas assume that VF == number of elements in the vector. This
7518 may not hold when there are multiple-types in the loop.
7519 In this case, for some data-references in the loop the VF does not represent
7520 the number of elements that fit in the vector. Therefore, instead of VF we
7521 use TYPE_VECTOR_SUBPARTS. */
7523 static tree
7525 {
7528 tree var;
7529 gimple_seq stmts;
7531 edge pe;
7532 basic_block new_bb;
7548 {
7557 }
7558 else
7559 {
7567 tree elem_size_log =
7571 tree byte_misalign;
7572 tree elem_misalign;
7577 /* Create: byte_misalign = addr & (vectype_size - 1) */
7578 byte_misalign =
7581 /* Create: elem_misalign = byte_misalign / element_size */
7582 elem_misalign =
7585 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
7589 }
7591 /* Create: prolog_loop_niters = min (iters, loop_niters) */
7592 /* If the loop bound is known at compile time we already verified that it is
7593 greater than vf; since the misalignment ('iters') is at most vf, there's
7594 no need to generate the MIN_EXPR in this case. */
7599 {
7602 }
7609 /* Insert stmt on loop preheader edge. */
7611 {
7614 }
7617 }
7620 /* Function vect_update_init_of_dr
7622 NITERS iterations were peeled from LOOP. DR represents a data reference
7623 in LOOP. This function updates the information recorded in DR to
7624 account for the fact that the first NITERS iterations had already been
7625 executed. Specifically, it updates the OFFSET field of DR. */
7627 static void
7629 {
7635 }
7638 /* Function vect_update_inits_of_drs
7640 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
7641 This function updates the information recorded for the data references in
7642 the loop to account for the fact that the first NITERS iterations had
7643 already been executed. Specifically, it updates the initial_condition of
7644 the access_function of all the data_references in the loop. */
7646 static void
7648 {
7658 }
7661 /* Function vect_do_peeling_for_alignment
7663 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
7664 'niters' is set to the misalignment of one of the data references in the
7665 loop, thereby forcing it to refer to an aligned location at the beginning
7666 of the execution of this loop. The data reference for which we are
7667 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
7669 static void
7671 {
7674 tree n_iters;
7689 /* If cost model check not done during versioning. */
7692 {
7695 /* Get profitability threshold for vectorized loop. */
7699 min_profitable_iters);
7700 }
7702 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
7703 new_loop =
7709 #ifdef ENABLE_CHECKING
7711 #endif
7713 /* Update number of times loop executes. */
7718 /* Update the init conditions of the access functions of all data refs. */
7721 /* After peeling we have to reset scalar evolution analyzer. */
7725 }
7728 /* Function vect_create_cond_for_align_checks.
7730 Create a conditional expression that represents the alignment checks for
7731 all of data references (array element references) whose alignment must be
7732 checked at runtime.
7734 Input:
7735 COND_EXPR - input conditional expression. New conditions will be chained
7736 with logical AND operation.
7737 LOOP_VINFO - two fields of the loop information are used.
7738 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
7739 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
7741 Output:
7742 COND_EXPR_STMT_LIST - statements needed to construct the conditional
7743 expression.
7744 The returned value is the conditional expression to be used in the if
7745 statement that controls which version of the loop gets executed at runtime.
7747 The algorithm makes two assumptions:
7748 1) The number of bytes "n" in a vector is a power of 2.
7749 2) An address "a" is aligned if a%n is zero and that this
7750 test can be done as a&(n-1) == 0. For example, for 16
7751 byte vectors the test is a&0xf == 0. */
7753 static void
7757 {
7761 gimple ref_stmt;
7763 tree mask_cst;
7765 tree psize;
7766 tree int_ptrsize_type;
7770 gimple and_stmt;
7771 tree ptrsize_zero;
7772 tree part_cond_expr;
7774 /* Check that mask is one less than a power of 2, i.e., mask is
7775 all zeros followed by all ones. */
7778 /* CHECKME: what is the best integer or unsigned type to use to hold a
7779 cast from a pointer value? */
7781 int_ptrsize_type
7784 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
7785 of the first vector of the i'th data reference. */
7788 {
7790 tree addr_base;
7795 /* create: addr_tmp = (int)(address_of_first_vector) */
7796 addr_base =
7811 /* The addresses are OR together. */
7814 {
7815 /* create: or_tmp = or_tmp | addr_tmp */
7821 new_or_tmp_name,
7826 }
7827 else
7834 /* create: and_tmp = or_tmp & mask */
7844 /* Make and_tmp the left operand of the conditional test against zero.
7845 if and_tmp has a nonzero bit then some address is unaligned. */
7852 else
7854 }
7856 /* Function vect_vfa_segment_size.
7858 Create an expression that computes the size of segment
7859 that will be accessed for a data reference. The functions takes into
7860 account that realignment loads may access one more vector.
7862 Input:
7863 DR: The data reference.
7864 VECT_FACTOR: vectorization factor.
7866 Return an expression whose value is the size of segment which will be
7867 accessed by DR. */
7869 static tree
7871 {
7876 {
7877 tree vector_size = TYPE_SIZE_UNIT
7882 }
7884 }
7886 /* Function vect_create_cond_for_alias_checks.
7888 Create a conditional expression that represents the run-time checks for
7889 overlapping of address ranges represented by a list of data references
7890 relations passed as input.
7892 Input:
7893 COND_EXPR - input conditional expression. New conditions will be chained
7894 with logical AND operation.
7895 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
7896 to be checked.
7898 Output:
7899 COND_EXPR - conditional expression.
7900 COND_EXPR_STMT_LIST - statements needed to construct the conditional
7901 expression.
7904 The returned value is the conditional expression to be used in the if
7905 statement that controls which version of the loop gets executed at runtime.
7906 */
7908 static void
7912 {
7916 tree vect_factor =
7919 ddr_p ddr;
7921 tree part_cond_expr;
7923 /* Create expression
7924 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
7925 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
7926 &&
7927 ...
7928 &&
7929 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
7930 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
7936 {
7947 {
7950 }
7956 {
7959 }
7961 addr_base_a =
7964 addr_base_b =
7972 {
7978 }
7981 part_cond_expr =
7985 addr_base_a,
7986 segment_length_a),
7987 addr_base_b),
7990 addr_base_b,
7991 segment_length_b),
7992 addr_base_a));
7997 else
7999 }
8004 }
8006 /* Function vect_loop_versioning.
8008 If the loop has data references that may or may not be aligned or/and
8009 has data reference relations whose independence was not proven then
8010 two versions of the loop need to be generated, one which is vectorized
8011 and one which isn't. A test is then generated to control which of the
8012 loops is executed. The test checks for the alignment of all of the
8013 data references that may or may not be aligned. An additional
8014 sequence of runtime tests is generated for each pairs of DDRs whose
8015 independence was not proven. The vectorized version of loop is
8016 executed only if both alias and alignment tests are passed.
8018 The test generated to check which version of loop is executed
8019 is modified to also check for profitability as indicated by the
8020 cost model initially. */
8022 static void
8024 {
8029 basic_block condition_bb;
8031 basic_block merge_bb;
8032 basic_block new_exit_bb;
8035 tree arg;
8042 /* Get profitability threshold for vectorized loop. */
8046 min_profitable_iters);
8048 cond_expr =
8063 cond_expr =
8065 cond_expr =
8074 /* Loop versioning violates an assumption we try to maintain during
8075 vectorization - that the loop exit block has a single predecessor.
8076 After versioning, the exit block of both loop versions is the same
8077 basic block (i.e. it has two predecessors). Just in order to simplify
8078 following transformations in the vectorizer, we fix this situation
8079 here by adding a new (empty) block on the exit-edge of the loop,
8080 with the proper loop-exit phis to maintain loop-closed-form. */
8089 {
8092 new_exit_bb);
8096 }
8098 /* End loop-exit-fixes after versioning. */
8102 {
8105 }
8106 }
8108 /* Remove a group of stores (for SLP or interleaving), free their
8109 stmt_vec_info. */
8111 static void
8113 {
8115 gimple tmp;
8116 gimple_stmt_iterator next_si;
8119 {
8120 /* Free the attached stmt_vec_info and remove the stmt. */
8126 }
8127 }
8130 /* Vectorize SLP instance tree in postorder. */
8132 static bool
8135 {
8136 gimple stmt;
8138 gimple_stmt_iterator si;
8139 stmt_vec_info stmt_info;
8141 tree vectype;
8143 slp_tree loads_node;
8149 vectorization_factor);
8151 vectorization_factor);
8155 /* VECTYPE is the type of the destination. */
8160 /* For each SLP instance calculate number of vector stmts to be created
8161 for the scalar stmts in each node of the SLP tree. Number of vector
8162 elements in one vector iteration is the number of scalar elements in
8163 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
8164 size. */
8167 /* In case of load permutation we have to allocate vectorized statements for
8168 all the nodes that participate in that permutation. */
8170 {
8173 i++)
8174 {
8176 {
8178 vec_stmts_size);
8180 }
8181 }
8182 }
8185 {
8188 }
8191 {
8194 }
8199 {
8201 /* If IS_STORE is TRUE, the vectorization of the
8202 interleaving chain was completed - free all the stores in
8203 the chain. */
8205 else
8206 /* FORNOW: SLP originates only from strided stores. */
8210 }
8212 /* FORNOW: SLP originates only from strided stores. */
8214 }
8217 static bool
8219 {
8222 slp_instance instance;
8227 {
8228 /* Schedule the tree of INSTANCE. */
8230 instance,
8236 }
8239 }
8241 /* Function vect_transform_loop.
8243 The analysis phase has determined that the loop is vectorizable.
8244 Vectorize the loop - created vectorized stmts to replace the scalar
8245 stmts in the loop, and update the loop exit condition. */
8247 void
8249 {
8253 gimple_stmt_iterator si;
8268 /* CHECKME: we wouldn't need this if we called update_ssa once
8269 for all loops. */
8272 /* Peel the loop if there are data refs with unknown alignment.
8273 Only one data ref with unknown store is allowed. */
8278 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
8279 compile time constant), or it is a constant that doesn't divide by the
8280 vectorization factor, then an epilog loop needs to be created.
8281 We therefore duplicate the loop: the original loop will be vectorized,
8282 and will compute the first (n/VF) iterations. The second copy of the loop
8283 will remain scalar and will compute the remaining (n%VF) iterations.
8284 (VF is the vectorization factor). */
8290 else
8294 /* 1) Make sure the loop header has exactly two entries
8295 2) Make sure we have a preheader basic block. */
8301 /* FORNOW: the vectorizer supports only loops which body consist
8302 of one basic block (header + empty latch). When the vectorizer will
8303 support more involved loop forms, the order by which the BBs are
8304 traversed need to be reconsidered. */
8307 {
8309 stmt_vec_info stmt_info;
8310 gimple phi;
8313 {
8316 {
8319 }
8334 {
8338 }
8339 }
8342 {
8347 {
8350 }
8354 /* vector stmts created in the outer-loop during vectorization of
8355 stmts in an inner-loop may not have a stmt_info, and do not
8356 need to be vectorized. */
8358 {
8361 }
8365 {
8368 }
8371 nunits =
8376 /* For SLP VF is set according to unrolling factor, and not to
8377 vector size, hence for SLP this print is not valid. */
8380 /* SLP. Schedule all the SLP instances when the first SLP stmt is
8381 reached. */
8383 {
8385 {
8393 /* IS_STORE is true if STMT is a store. Stores cannot be of
8394 hybrid SLP type. They are removed in
8395 vect_schedule_slp_instance and their vinfo is destroyed. */
8397 {
8400 }
8401 }
8403 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
8405 {
8408 }
8409 }
8411 /* -------- vectorize statement ------------ */
8418 {
8420 {
8421 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
8422 interleaving chain was completed - free all the stores in
8423 the chain. */
8427 }
8428 else
8429 {
8430 /* Free the attached stmt_vec_info and remove the stmt. */
8434 }
8435 }
8444 /* The memory tags and pointers in vectorized statements need to
8445 have their SSA forms updated. FIXME, why can't this be delayed
8446 until all the loops have been transformed? */
8453 }