| blob | 1fa786da0b9618add6b5af571dc7420d43960317 |
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. */
51 static tree vect_create_data_ref_ptr
53 static tree vect_create_addr_base_for_vector_ref
58 static void vect_finish_stmt_generation
64 /* Utility function dealing with loop peeling (not peeling itself). */
65 static void vect_generate_tmps_on_preheader
75 static int
77 {
81 {
99 }
100 }
103 /* Function vect_estimate_min_profitable_iters
105 Return the number of iterations required for the vector version of the
106 loop to be profitable relative to the cost of the scalar version of the
107 loop.
109 TODO: Take profile info into account before making vectorization
110 decisions, if available. */
112 int
114 {
132 slp_instance instance;
134 /* Cost model disabled. */
136 {
140 }
142 /* If the number of iterations is unknown, or the
143 peeling-for-misalignment amount is unknown, we will have to generate
144 a runtime test to test the loop count against the threshold. */
149 /* Requires loop versioning tests to handle misalignment. */
152 {
153 /* FIXME: Make cost depend on complexity of individual check. */
154 vec_outside_cost +=
159 }
162 {
163 /* FIXME: Make cost depend on complexity of individual check. */
164 vec_outside_cost +=
169 }
173 {
175 }
177 /* Count statements in scalar loop. Using this as scalar cost for a single
178 iteration for now.
180 TODO: Add outer loop support.
182 TODO: Consider assigning different costs to different scalar
183 statements. */
185 /* FORNOW. */
190 {
191 block_stmt_iterator si;
196 else
200 {
203 /* Skip stmts that are not vectorized inside the loop. */
210 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
211 some of the "outside" costs are generated inside the outer-loop. */
213 }
214 }
216 /* Add additional cost for the peeled instructions in prologue and epilogue
217 loop.
219 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
220 at compile-time - we assume it's vf/2 (the worst would be vf-1).
222 TODO: Build an expression that represents peel_iters for prologue and
223 epilogue to be used in a run-time test. */
226 {
232 /* If peeling for alignment is unknown, loop bound of main loop becomes
233 unknown. */
237 "epilogue peel iters set to vf/2 because "
240 /* If peeled iterations are unknown, count a taken branch and a not taken
241 branch per peeled loop. Even if scalar loop iterations are known,
242 vector iterations are not known since peeled prologue iterations are
243 not known. Hence guards remain the same. */
247 }
248 else
249 {
251 {
258 }
259 else
263 {
267 "epilogue peel iters set to vf/2 because "
270 /* If peeled iterations are known but number of scalar loop
271 iterations are unknown, count a taken branch per peeled loop. */
274 }
275 else
276 {
281 }
282 }
288 /* FORNOW: The scalar outside cost is incremented in one of the
289 following ways:
291 1. The vectorizer checks for alignment and aliasing and generates
292 a condition that allows dynamic vectorization. A cost model
293 check is ANDED with the versioning condition. Hence scalar code
294 path now has the added cost of the versioning check.
296 if (cost > th & versioning_check)
297 jmp to vector code
299 Hence run-time scalar is incremented by not-taken branch cost.
301 2. The vectorizer then checks if a prologue is required. If the
302 cost model check was not done before during versioning, it has to
303 be done before the prologue check.
305 if (cost <= th)
306 prologue = scalar_iters
307 if (prologue == 0)
308 jmp to vector code
309 else
310 execute prologue
311 if (prologue == num_iters)
312 go to exit
314 Hence the run-time scalar cost is incremented by a taken branch,
315 plus a not-taken branch, plus a taken branch cost.
317 3. The vectorizer then checks if an epilogue is required. If the
318 cost model check was not done before during prologue check, it
319 has to be done with the epilogue check.
321 if (prologue == 0)
322 jmp to vector code
323 else
324 execute prologue
325 if (prologue == num_iters)
326 go to exit
327 vector code:
328 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
329 jmp to epilogue
331 Hence the run-time scalar cost should be incremented by 2 taken
332 branches.
334 TODO: The back end may reorder the BBS's differently and reverse
335 conditions/branch directions. Change the estimates below to
336 something more reasonable. */
339 {
340 /* Cost model check occurs at versioning. */
344 else
345 {
346 /* Cost model occurs at prologue generation. */
350 /* Cost model check occurs at epilogue generation. */
351 else
353 }
354 }
356 /* Add SLP costs. */
359 {
362 }
364 /* Calculate number of iterations required to make the vector version
365 profitable, relative to the loop bodies only. The following condition
366 must hold true:
367 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
368 where
369 SIC = scalar iteration cost, VIC = vector iteration cost,
370 VOC = vector outside cost, VF = vectorization factor,
371 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
372 SOC = scalar outside cost for run time cost model check. */
375 {
378 else
379 {
389 min_profitable_iters++;
390 }
391 }
392 /* vector version will never be profitable. */
393 else
394 {
397 "is divisible by scalar iteration cost = %d by a factor "
401 }
404 {
407 vec_inside_cost);
409 vec_outside_cost);
411 scalar_single_iter_cost);
414 peel_iters_prologue);
416 peel_iters_epilogue);
418 min_profitable_iters);
419 }
421 min_profitable_iters =
424 /* Because the condition we create is:
425 if (niters <= min_profitable_iters)
426 then skip the vectorized loop. */
427 min_profitable_iters--;
431 min_profitable_iters);
434 }
437 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
438 functions. Design better to avoid maintenance issues. */
440 /* Function vect_model_reduction_cost.
442 Models cost for a reduction operation, including the vector ops
443 generated within the strip-mine loop, the initial definition before
444 the loop, and the epilogue code that must be generated. */
446 static bool
449 {
452 optab optab;
453 tree vectype;
454 tree orig_stmt;
455 tree reduction_op;
462 /* Cost of reduction op inside loop. */
468 {
470 {
473 }
475 }
485 /* Add in cost for initial definition. */
488 /* Determine cost of epilogue code.
490 We have a reduction operator that will reduce the vector in one statement.
491 Also requires scalar extract. */
494 {
497 else
498 {
500 tree bitsize =
507 /* We have a whole vector shift available. */
511 /* Final reduction via vector shifts and the reduction operator. Also
512 requires scalar extract. */
515 else
516 /* Use extracts and reduction op for final reduction. For N elements,
517 we have N extracts and N-1 reduction ops. */
519 }
520 }
530 }
533 /* Function vect_model_induction_cost.
535 Models cost for induction operations. */
537 static void
539 {
540 /* loop cost for vec_loop. */
542 /* prologue cost for vec_init and vec_step. */
549 }
552 /* Function vect_model_simple_cost.
554 Models cost for simple operations, i.e. those that only emit ncopies of a
555 single op. Right now, this does not account for multiple insns that could
556 be generated for the single vector op. We will handle that shortly. */
558 void
561 {
567 /* FORNOW: Assuming maximum 2 args per stmts. */
569 {
572 }
578 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
581 }
584 /* Function vect_cost_strided_group_size
586 For strided load or store, return the group_size only if it is the first
587 load or store of a group, else return 1. This ensures that group size is
588 only returned once per group. */
590 static int
592 {
599 }
602 /* Function vect_model_store_cost
604 Models cost for stores. In the case of strided accesses, one access
605 has the overhead of the strided access attributed to it. */
607 void
610 {
617 /* Strided access? */
620 /* Not a strided access. */
621 else
624 /* Is this an access in a group of stores, which provide strided access?
625 If so, add in the cost of the permutes. */
627 {
628 /* Uses a high and low interleave operation for each needed permute. */
634 group_size);
636 }
638 /* Costs of the stores. */
645 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
648 }
651 /* Function vect_model_load_cost
653 Models cost for loads. In the case of strided accesses, the last access
654 has the overhead of the strided access attributed to it. Since unaligned
655 accesses are supported for loads, we also account for the costs of the
656 access scheme chosen. */
658 void
661 {
664 tree first_stmt;
668 /* Strided accesses? */
671 {
674 }
675 /* Not a strided access. */
676 else
677 {
680 }
684 /* Is this an access in a group of loads providing strided access?
685 If so, add in the cost of the permutes. */
687 {
688 /* Uses an even and odd extract operations for each needed permute. */
694 group_size);
696 }
698 /* The loads themselves. */
700 {
702 {
709 }
711 {
712 /* Here, we assign an additional cost for the unaligned load. */
720 }
722 {
725 /* FIXME: If the misalignment remains fixed across the iterations of
726 the containing loop, the following cost should be added to the
727 outside costs. */
732 }
734 {
739 /* Unaligned software pipeline has a load of an address, an initial
740 load, and possibly a mask operation to "prime" the loop. However,
741 if this is an access in a group of loads, which provide strided
742 access, then the above cost should only be considered for one
743 access in the group. Inside the loop, there is a load op
744 and a realignment op. */
747 {
751 }
756 }
760 }
766 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
769 }
772 /* Function vect_get_new_vect_var.
774 Returns a name for a new variable. The current naming scheme appends the
775 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
776 the name of vectorizer generated variables, and appends that to NAME if
777 provided. */
779 static tree
781 {
783 tree new_vect_var;
786 {
798 }
801 {
805 }
806 else
809 /* Mark vector typed variable as a gimple register variable. */
814 }
817 /* Function vect_create_addr_base_for_vector_ref.
819 Create an expression that computes the address of the first memory location
820 that will be accessed for a data reference.
822 Input:
823 STMT: The statement containing the data reference.
824 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
825 OFFSET: Optional. If supplied, it is be added to the initial address.
826 LOOP: Specify relative to which loop-nest should the address be computed.
827 For example, when the dataref is in an inner-loop nested in an
828 outer-loop that is now being vectorized, LOOP can be either the
829 outer-loop, or the inner-loop. The first memory location accessed
830 by the following dataref ('in' points to short):
832 for (i=0; i<N; i++)
833 for (j=0; j<M; j++)
834 s += in[i+j]
836 is as follows:
837 if LOOP=i_loop: &in (relative to i_loop)
838 if LOOP=j_loop: &in+i*2B (relative to j_loop)
840 Output:
841 1. Return an SSA_NAME whose value is the address of the memory location of
842 the first vector of the data reference.
843 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
844 these statement(s) which define the returned SSA_NAME.
846 FORNOW: We are only handling array accesses with step 1. */
848 static tree
851 tree offset,
853 {
858 tree base_name;
859 tree data_ref_base_var;
860 tree new_base_stmt;
861 tree vec_stmt;
871 {
880 }
882 /* Create data_ref_base */
890 /* Create base_offset */
899 {
908 }
910 /* base + base_offset */
916 /* addr_expr = addr_base */
928 {
931 }
933 }
936 /* Function vect_create_data_ref_ptr.
938 Create a new pointer to vector type (vp), that points to the first location
939 accessed in the loop by STMT, along with the def-use update chain to
940 appropriately advance the pointer through the loop iterations. Also set
941 aliasing information for the pointer. This vector pointer is used by the
942 callers to this function to create a memory reference expression for vector
943 load/store access.
945 Input:
946 1. STMT: a stmt that references memory. Expected to be of the form
947 GIMPLE_MODIFY_STMT <name, data-ref> or
948 GIMPLE_MODIFY_STMT <data-ref, name>.
949 2. AT_LOOP: the loop where the vector memref is to be created.
950 3. OFFSET (optional): an offset to be added to the initial address accessed
951 by the data-ref in STMT.
952 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
953 pointing to the initial address.
955 Output:
956 1. Declare a new ptr to vector_type, and have it point to the base of the
957 data reference (initial addressed accessed by the data reference).
958 For example, for vector of type V8HI, the following code is generated:
960 v8hi *vp;
961 vp = (v8hi *)initial_address;
963 if OFFSET is not supplied:
964 initial_address = &a[init];
965 if OFFSET is supplied:
966 initial_address = &a[init + OFFSET];
968 Return the initial_address in INITIAL_ADDRESS.
970 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
971 update the pointer in each iteration of the loop.
973 Return the increment stmt that updates the pointer in PTR_INCR.
975 3. Set INV_P to true if the access pattern of the data reference in the
976 vectorized loop is invariant. Set it to false otherwise.
978 4. Return the pointer. */
980 static tree
984 {
985 tree base_name;
992 tree vect_ptr_type;
993 tree vect_ptr;
994 tree tag;
995 tree new_temp;
996 tree vec_stmt;
998 edge pe;
999 basic_block new_bb;
1000 tree vect_ptr_init;
1002 tree vptr;
1003 block_stmt_iterator incr_bsi;
1006 tree incr;
1007 tree step;
1009 /* Check the step (evolution) of the load in LOOP, and record
1010 whether it's invariant. */
1013 else
1018 else
1021 /* Create an expression for the first address accessed by this load
1022 in LOOP. */
1026 {
1039 }
1041 /** (1) Create the new vector-pointer variable: **/
1048 /** (2) Add aliasing information to the new vector-pointer:
1049 (The points-to info (DR_PTR_INFO) may be defined later.) **/
1054 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
1055 tag must be created with tag added to its may alias list. */
1058 else
1061 /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
1062 vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
1063 def-use update cycles for the pointer: One relative to the outer-loop
1064 (LOOP), which is what steps (3) and (4) below do. The other is relative
1065 to the inner-loop (which is the inner-most loop containing the dataref),
1066 and this is done be step (5) below.
1068 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
1069 inner-most loop, and so steps (3),(4) work the same, and step (5) is
1070 redundant. Steps (3),(4) create the following:
1072 vp0 = &base_addr;
1073 LOOP: vp1 = phi(vp0,vp2)
1074 ...
1075 ...
1076 vp2 = vp1 + step
1077 goto LOOP
1079 If there is an inner-loop nested in loop, then step (5) will also be
1080 applied, and an additional update in the inner-loop will be created:
1082 vp0 = &base_addr;
1083 LOOP: vp1 = phi(vp0,vp2)
1084 ...
1085 inner: vp3 = phi(vp1,vp4)
1086 vp4 = vp3 + inner_step
1087 if () goto inner
1088 ...
1089 vp2 = vp1 + step
1090 if () goto LOOP */
1092 /** (3) Calculate the initial address the vector-pointer, and set
1093 the vector-pointer to point to it before the loop: **/
1095 /* Create: (&(base[init_val+offset]) in the loop preheader. */
1101 {
1104 }
1108 /* Create: p = (vectype *) initial_base */
1117 /** (4) Handle the updating of the vector-pointer inside the loop.
1118 This is needed when ONLY_INIT is false, and also when AT_LOOP
1119 is the inner-loop nested in LOOP (during outer-loop vectorization).
1120 **/
1123 {
1124 /* Copy the points-to information if it exists. */
1128 }
1129 else
1130 {
1131 /* The step of the vector pointer is the Vector Size. */
1133 /* One exception to the above is when the scalar step of the load in
1134 LOOP is zero. In this case the step here is also zero. */
1148 /* Copy the points-to information if it exists. */
1150 {
1153 }
1160 }
1166 /** (5) Handle the updating of the vector-pointer inside the inner-loop
1167 nested in LOOP, if exists: **/
1171 {
1180 /* Copy the points-to information if it exists. */
1182 {
1185 }
1192 }
1193 else
1195 }
1198 /* Function bump_vector_ptr
1200 Increment a pointer (to a vector type) by vector-size. If requested,
1201 i.e. if PTR-INCR is given, then also connect the new increment stmt
1202 to the existing def-use update-chain of the pointer, by modifying
1203 the PTR_INCR as illustrated below:
1205 The pointer def-use update-chain before this function:
1206 DATAREF_PTR = phi (p_0, p_2)
1207 ....
1208 PTR_INCR: p_2 = DATAREF_PTR + step
1210 The pointer def-use update-chain after this function:
1211 DATAREF_PTR = phi (p_0, p_2)
1212 ....
1213 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1214 ....
1215 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
1217 Input:
1218 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
1219 in the loop.
1220 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
1221 the loop. The increment amount across iterations is expected
1222 to be vector_size.
1223 BSI - location where the new update stmt is to be placed.
1224 STMT - the original scalar memory-access stmt that is being vectorized.
1225 BUMP - optional. The offset by which to bump the pointer. If not given,
1226 the offset is assumed to be vector_size.
1228 Output: Return NEW_DATAREF_PTR as illustrated above.
1230 */
1232 static tree
1235 {
1242 tree incr_stmt;
1243 ssa_op_iter iter;
1244 use_operand_p use_p;
1245 tree new_dataref_ptr;
1257 /* Copy the points-to information if it exists. */
1265 /* Update the vector-pointer's cross-iteration increment. */
1267 {
1272 else
1274 }
1277 }
1280 /* Function vect_create_destination_var.
1282 Create a new temporary of type VECTYPE. */
1284 static tree
1286 {
1287 tree vec_dest;
1289 tree type;
1304 }
1307 /* Function vect_init_vector.
1309 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1310 the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1311 is not NULL. Otherwise, place the initialization at the loop preheader.
1312 Return the DEF of INIT_STMT.
1313 It will be used in the vectorization of STMT. */
1315 static tree
1318 {
1320 tree new_var;
1321 tree init_stmt;
1322 tree vec_oprnd;
1323 edge pe;
1324 tree new_temp;
1325 basic_block new_bb;
1335 else
1336 {
1345 }
1348 {
1351 }
1355 }
1358 /* For constant and loop invariant defs of SLP_NODE this function returns
1359 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1360 OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1361 stmts. */
1363 static void
1366 {
1372 tree vec_cst;
1375 tree vector_type;
1388 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1389 created vectors. It is greater than 1 if unrolling is performed.
1391 For example, we have two scalar operands, s1 and s2 (e.g., group of
1392 strided accesses of size two), while NUNITS is four (i.e., four scalars
1393 of this type can be packed in a vector). The output vector will contain
1394 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1395 will be 2).
1397 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1398 containing the operands.
1400 For example, NUNITS is four as before, and the group size is 8
1401 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1402 {s5, s6, s7, s8}. */
1409 {
1411 {
1415 else
1420 /* Create 'vect_ = {op0,op1,...,opn}'. */
1423 number_of_places_left_in_vector--;
1426 {
1433 else
1438 NULL));
1440 }
1441 }
1442 }
1444 /* Since the vectors are created in the reverse order, we should invert
1445 them. */
1448 {
1451 }
1455 /* In case that VF is greater than the unrolling factor needed for the SLP
1456 group of stmts, NUMBER_OF_VECTORS to be created is greater than
1457 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1458 to replicate the vectors. */
1460 {
1463 }
1464 }
1467 /* Get vectorized definitions from SLP_NODE that contains corresponding
1468 vectorized def-stmts. */
1470 static void
1472 {
1473 tree vec_oprnd;
1474 tree vec_def_stmt;
1481 i++)
1482 {
1486 }
1487 }
1490 /* Get vectorized definitions for SLP_NODE.
1491 If the scalar definitions are loop invariants or constants, collect them and
1492 call vect_get_constant_vectors() to create vector stmts.
1493 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1494 must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1495 vect_get_slp_vect_defs() to retrieve them.
1496 If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1497 the right node. This is used when the second operand must remain scalar. */
1499 static void
1502 {
1505 /* Allocate memory for vectorized defs. */
1509 /* SLP_NODE corresponds either to a group of stores or to a group of
1510 unary/binary operations. We don't call this function for loads. */
1512 /* The defs are already vectorized. */
1514 else
1515 /* Build vectors from scalar defs. */
1520 /* Since we don't call this function with loads, this is a group of
1521 stores. */
1532 /* The defs are already vectorized. */
1534 else
1535 /* Build vectors from scalar defs. */
1537 }
1540 /* Function get_initial_def_for_induction
1542 Input:
1543 STMT - a stmt that performs an induction operation in the loop.
1544 IV_PHI - the initial value of the induction variable
1546 Output:
1547 Return a vector variable, initialized with the first VF values of
1548 the induction variable. E.g., for an iv with IV_PHI='X' and
1549 evolution S, for a vector of 4 units, we want to return:
1550 [X, X + S, X + 2*S, X + 3*S]. */
1552 static tree
1554 {
1559 tree vectype;
1563 basic_block new_bb;
1565 tree access_fn;
1566 tree new_var;
1567 tree new_name;
1568 tree init_stmt;
1575 tree expr;
1578 tree stmts;
1579 imm_use_iterator imm_iter;
1580 use_operand_p use_p;
1581 tree exit_phi;
1582 edge latch_e;
1583 tree loop_arg;
1584 block_stmt_iterator si;
1595 /* Find the first insertion point in the BB. */
1600 else
1603 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
1605 {
1608 }
1609 else
1623 /* Create the vector that holds the initial_value of the induction. */
1625 {
1626 /* iv_loop is nested in the loop to be vectorized. init_expr had already
1627 been created during vectorization of previous stmts; We obtain it from
1628 the STMT_VINFO_VEC_STMT of the defining stmt. */
1631 }
1632 else
1633 {
1634 /* iv_loop is the loop to be vectorized. Create:
1635 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
1641 {
1644 }
1649 {
1650 tree tmp;
1652 /* Create: new_name_i = new_name + step_expr */
1662 {
1665 }
1667 }
1668 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
1671 }
1674 /* Create the vector that holds the step of the induction. */
1676 /* iv_loop is nested in the loop to be vectorized. Generate:
1677 vec_step = [S, S, S, S] */
1679 else
1680 {
1681 /* iv_loop is the loop to be vectorized. Generate:
1682 vec_step = [VF*S, VF*S, VF*S, VF*S] */
1685 }
1695 /* Create the following def-use cycle:
1696 loop prolog:
1697 vec_init = ...
1698 vec_step = ...
1699 loop:
1700 vec_iv = PHI <vec_init, vec_loop>
1701 ...
1702 STMT
1703 ...
1704 vec_loop = vec_iv + vec_step; */
1706 /* Create the induction-phi that defines the induction-operand. */
1714 /* Create the iv update inside the loop */
1724 /* Set the arguments of the phi node: */
1729 /* In case that vectorization factor (VF) is bigger than the number
1730 of elements that we can fit in a vectype (nunits), we have to generate
1731 more than one vector stmt - i.e - we need to "unroll" the
1732 vector stmt by a factor VF/nunits. For more details see documentation
1733 in vectorizable_operation. */
1736 {
1737 stmt_vec_info prev_stmt_vinfo;
1738 /* FORNOW. This restriction should be relaxed. */
1741 /* Create the vector that holds the step of the induction. */
1754 {
1755 tree tmp;
1757 /* vec_i = vec_prev + vec_step */
1767 }
1768 }
1771 {
1772 /* Find the loop-closed exit-phi of the induction, and record
1773 the final vector of induction results: */
1776 {
1778 {
1781 }
1782 }
1784 {
1786 /* FORNOW. Currently not supporting the case that an inner-loop induction
1787 is not used in the outer-loop (i.e. only outside the outer-loop). */
1793 {
1796 }
1797 }
1798 }
1802 {
1807 }
1811 }
1814 /* Function vect_get_vec_def_for_operand.
1816 OP is an operand in STMT. This function returns a (vector) def that will be
1817 used in the vectorized stmt for STMT.
1819 In the case that OP is an SSA_NAME which is defined in the loop, then
1820 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1822 In case OP is an invariant or constant, a new stmt that creates a vector def
1823 needs to be introduced. */
1825 static tree
1827 {
1828 tree vec_oprnd;
1829 tree vec_stmt;
1830 tree def_stmt;
1836 tree vec_inv;
1837 tree vec_cst;
1839 tree def;
1843 tree vector_type;
1846 {
1849 }
1854 {
1856 {
1859 }
1861 {
1864 }
1865 }
1868 {
1869 /* Case 1: operand is a constant. */
1871 {
1875 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1880 {
1882 }
1888 }
1890 /* Case 2: operand is defined outside the loop - loop invariant. */
1892 {
1896 /* Create 'vec_inv = {inv,inv,..,inv}' */
1901 {
1903 }
1905 /* FIXME: use build_constructor directly. */
1910 }
1912 /* Case 3: operand is defined inside the loop. */
1914 {
1918 /* Get the def from the vectorized stmt. */
1924 else
1927 }
1929 /* Case 4: operand is defined by a loop header phi - reduction */
1931 {
1937 /* Get the def before the loop */
1940 }
1942 /* Case 5: operand is defined by loop-header phi - induction. */
1944 {
1947 /* Get the def from the vectorized stmt. */
1953 }
1957 }
1958 }
1961 /* Function vect_get_vec_def_for_stmt_copy
1963 Return a vector-def for an operand. This function is used when the
1964 vectorized stmt to be created (by the caller to this function) is a "copy"
1965 created in case the vectorized result cannot fit in one vector, and several
1966 copies of the vector-stmt are required. In this case the vector-def is
1967 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1968 of the stmt that defines VEC_OPRND.
1969 DT is the type of the vector def VEC_OPRND.
1971 Context:
1972 In case the vectorization factor (VF) is bigger than the number
1973 of elements that can fit in a vectype (nunits), we have to generate
1974 more than one vector stmt to vectorize the scalar stmt. This situation
1975 arises when there are multiple data-types operated upon in the loop; the
1976 smallest data-type determines the VF, and as a result, when vectorizing
1977 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1978 vector stmt (each computing a vector of 'nunits' results, and together
1979 computing 'VF' results in each iteration). This function is called when
1980 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1981 which VF=16 and nunits=4, so the number of copies required is 4):
1983 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
1985 S1: x = load VS1.0: vx.0 = memref0 VS1.1
1986 VS1.1: vx.1 = memref1 VS1.2
1987 VS1.2: vx.2 = memref2 VS1.3
1988 VS1.3: vx.3 = memref3
1990 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
1991 VSnew.1: vz1 = vx.1 + ... VSnew.2
1992 VSnew.2: vz2 = vx.2 + ... VSnew.3
1993 VSnew.3: vz3 = vx.3 + ...
1995 The vectorization of S1 is explained in vectorizable_load.
1996 The vectorization of S2:
1997 To create the first vector-stmt out of the 4 copies - VSnew.0 -
1998 the function 'vect_get_vec_def_for_operand' is called to
1999 get the relevant vector-def for each operand of S2. For operand x it
2000 returns the vector-def 'vx.0'.
2002 To create the remaining copies of the vector-stmt (VSnew.j), this
2003 function is called to get the relevant vector-def for each operand. It is
2004 obtained from the respective VS1.j stmt, which is recorded in the
2005 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
2007 For example, to obtain the vector-def 'vx.1' in order to create the
2008 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
2009 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
2010 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
2011 and return its def ('vx.1').
2012 Overall, to create the above sequence this function will be called 3 times:
2013 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
2014 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
2015 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
2017 static tree
2019 {
2020 tree vec_stmt_for_operand;
2021 stmt_vec_info def_stmt_info;
2023 /* Do nothing; can reuse same def. */
2034 }
2037 /* Get vectorized definitions for the operands to create a copy of an original
2038 stmt. See vect_get_vec_def_for_stmt_copy() for details. */
2040 static void
2044 {
2051 {
2055 }
2056 }
2059 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not NULL. */
2061 static void
2064 {
2067 else
2068 {
2069 tree vec_oprnd;
2076 {
2080 }
2081 }
2082 }
2085 /* Function vect_finish_stmt_generation.
2087 Insert a new stmt. */
2089 static void
2092 {
2105 {
2108 }
2110 /* Make sure bsi points to the stmt that is being vectorized. */
2114 }
2117 /* Function get_initial_def_for_reduction
2119 Input:
2120 STMT - a stmt that performs a reduction operation in the loop.
2121 INIT_VAL - the initial value of the reduction variable
2123 Output:
2124 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2125 of the reduction (used for adjusting the epilog - see below).
2126 Return a vector variable, initialized according to the operation that STMT
2127 performs. This vector will be used as the initial value of the
2128 vector of partial results.
2130 Option1 (adjust in epilog): Initialize the vector as follows:
2131 add: [0,0,...,0,0]
2132 mult: [1,1,...,1,1]
2133 min/max: [init_val,init_val,..,init_val,init_val]
2134 bit and/or: [init_val,init_val,..,init_val,init_val]
2135 and when necessary (e.g. add/mult case) let the caller know
2136 that it needs to adjust the result by init_val.
2138 Option2: Initialize the vector as follows:
2139 add: [0,0,...,0,init_val]
2140 mult: [1,1,...,1,init_val]
2141 min/max: [init_val,init_val,...,init_val]
2142 bit and/or: [init_val,init_val,...,init_val]
2143 and no adjustments are needed.
2145 For example, for the following code:
2147 s = init_val;
2148 for (i=0;i<n;i++)
2149 s = s + a[i];
2151 STMT is 's = s + a[i]', and the reduction variable is 's'.
2152 For a vector of 4 units, we want to return either [0,0,0,init_val],
2153 or [0,0,0,0] and let the caller know that it needs to adjust
2154 the result at the end by 'init_val'.
2156 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2157 initialization vector is simpler (same element in all entries).
2158 A cost model should help decide between these two schemes. */
2160 static tree
2162 {
2170 tree vecdef;
2171 tree def_for_init;
2172 tree init_def;
2175 tree vector_type;
2181 else
2187 {
2193 else
2195 /* Create a vector of zeros for init_def. */
2198 else
2215 }
2218 }
2221 /* Function vect_create_epilog_for_reduction
2223 Create code at the loop-epilog to finalize the result of a reduction
2224 computation.
2226 VECT_DEF is a vector of partial results.
2227 REDUC_CODE is the tree-code for the epilog reduction.
2228 STMT is the scalar reduction stmt that is being vectorized.
2229 REDUCTION_PHI is the phi-node that carries the reduction computation.
2231 This function:
2232 1. Creates the reduction def-use cycle: sets the arguments for
2233 REDUCTION_PHI:
2234 The loop-entry argument is the vectorized initial-value of the reduction.
2235 The loop-latch argument is VECT_DEF - the vector of partial sums.
2236 2. "Reduces" the vector of partial results VECT_DEF into a single result,
2237 by applying the operation specified by REDUC_CODE if available, or by
2238 other means (whole-vector shifts or a scalar loop).
2239 The function also creates a new phi node at the loop exit to preserve
2240 loop-closed form, as illustrated below.
2242 The flow at the entry to this function:
2244 loop:
2245 vec_def = phi <null, null> # REDUCTION_PHI
2246 VECT_DEF = vector_stmt # vectorized form of STMT
2247 s_loop = scalar_stmt # (scalar) STMT
2248 loop_exit:
2249 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2250 use <s_out0>
2251 use <s_out0>
2253 The above is transformed by this function into:
2255 loop:
2256 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2257 VECT_DEF = vector_stmt # vectorized form of STMT
2258 s_loop = scalar_stmt # (scalar) STMT
2259 loop_exit:
2260 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2261 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2262 v_out2 = reduce <v_out1>
2263 s_out3 = extract_field <v_out2, 0>
2264 s_out4 = adjust_result <s_out3>
2265 use <s_out4>
2266 use <s_out4>
2267 */
2269 static void
2272 {
2274 tree vectype;
2278 basic_block exit_bb;
2279 tree scalar_dest;
2280 tree scalar_type;
2281 tree new_phi;
2282 block_stmt_iterator exit_bsi;
2283 tree vec_dest;
2285 tree new_name;
2290 tree adjustment_def;
2291 tree vec_initial_def;
2292 tree orig_name;
2293 imm_use_iterator imm_iter;
2294 use_operand_p use_p;
2297 tree orig_stmt;
2298 tree use_stmt;
2306 {
2309 }
2317 /*** 1. Create the reduction def-use cycle ***/
2319 /* 1.1 set the loop-entry arg of the reduction-phi: */
2320 /* For the case of reduction, vect_get_vec_def_for_operand returns
2321 the scalar def before the loop, that defines the initial value
2322 of the reduction variable. */
2327 /* 1.2 set the loop-latch arg for the reduction-phi: */
2331 {
2336 }
2339 /*** 2. Create epilog code
2340 The reduction epilog code operates across the elements of the vector
2341 of partial results computed by the vectorized loop.
2342 The reduction epilog code consists of:
2343 step 1: compute the scalar result in a vector (v_out2)
2344 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2345 step 3: adjust the scalar result (s_out3) if needed.
2347 Step 1 can be accomplished using one the following three schemes:
2348 (scheme 1) using reduc_code, if available.
2349 (scheme 2) using whole-vector shifts, if available.
2350 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2351 combined.
2353 The overall epilog code looks like this:
2355 s_out0 = phi <s_loop> # original EXIT_PHI
2356 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2357 v_out2 = reduce <v_out1> # step 1
2358 s_out3 = extract_field <v_out2, 0> # step 2
2359 s_out4 = adjust_result <s_out3> # step 3
2361 (step 3 is optional, and step2 1 and 2 may be combined).
2362 Lastly, the uses of s_out0 are replaced by s_out4.
2364 ***/
2366 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2367 v_out1 = phi <v_loop> */
2374 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
2375 (i.e. when reduc_code is not available) and in the final adjustment
2376 code (if needed). Also get the original scalar reduction variable as
2377 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
2378 represents a reduction pattern), the tree-code and scalar-def are
2379 taken from the original stmt that the pattern-stmt (STMT) replaces.
2380 Otherwise (it is a regular reduction) - the tree-code and scalar-def
2381 are taken from STMT. */
2385 {
2386 /* Regular reduction */
2388 }
2389 else
2390 {
2391 /* Reduction pattern */
2395 }
2404 /* In case this is a reduction in an inner-loop while vectorizing an outer
2405 loop - we don't need to extract a single scalar result at the end of the
2406 inner-loop. The final vector of partial results will be used in the
2407 vectorized outer-loop, or reduced to a scalar result at the end of the
2408 outer-loop. */
2412 /* 2.3 Create the reduction code, using one of the three schemes described
2413 above. */
2416 {
2417 tree tmp;
2419 /*** Case 1: Create:
2420 v_out2 = reduc_expr <v_out1> */
2433 }
2434 else
2435 {
2441 tree vec_temp;
2445 else
2448 /* Regardless of whether we have a whole vector shift, if we're
2449 emulating the operation via tree-vect-generic, we don't want
2450 to use it. Only the first round of the reduction is likely
2451 to still be profitable via emulation. */
2452 /* ??? It might be better to emit a reduction tree code here, so that
2453 tree-vect-generic can expand the first round via bit tricks. */
2456 else
2457 {
2461 }
2464 {
2465 /*** Case 2: Create:
2466 for (offset = VS/2; offset >= element_size; offset/=2)
2467 {
2468 Create: va' = vec_shift <va, offset>
2469 Create: va = vop <va, va'>
2470 } */
2481 {
2494 }
2497 }
2498 else
2499 {
2500 tree rhs;
2502 /*** Case 3: Create:
2503 s = extract_field <v_out2, 0>
2504 for (offset = element_size;
2505 offset < vector_size;
2506 offset += element_size;)
2507 {
2508 Create: s' = extract_field <v_out2, offset>
2509 Create: s = op <s, s'>
2510 } */
2518 bitsize_zero_node);
2527 {
2528 tree tmp;
2531 bitpos);
2543 }
2546 }
2547 }
2549 /* 2.4 Extract the final scalar result. Create:
2550 s_out3 = extract_field <v_out2, bitpos> */
2553 {
2554 tree rhs;
2564 else
2572 }
2574 vect_finalize_reduction:
2576 /* 2.5 Adjust the final result by the initial value of the reduction
2577 variable. (When such adjustment is not needed, then
2578 'adjustment_def' is zero). For example, if code is PLUS we create:
2579 new_temp = loop_exit_def + adjustment_def */
2582 {
2584 {
2588 }
2589 else
2590 {
2594 }
2599 }
2602 /* 2.6 Handle the loop-exit phi */
2604 /* Replace uses of s_out0 with uses of s_out3:
2605 Find the loop-closed-use at the loop exit of the original scalar result.
2606 (The reduction result is expected to have two immediate uses - one at the
2607 latch block, and one at the loop exit). */
2610 {
2612 {
2615 }
2616 }
2617 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
2621 {
2623 {
2626 /* FORNOW. Currently not supporting the case that an inner-loop reduction
2627 is not used in the outer-loop (but only outside the outer-loop). */
2636 }
2638 /* Replace the uses: */
2643 }
2645 }
2648 /* Function vectorizable_reduction.
2650 Check if STMT performs a reduction operation that can be vectorized.
2651 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2652 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2653 Return FALSE if not a vectorizable STMT, TRUE otherwise.
2655 This function also handles reduction idioms (patterns) that have been
2656 recognized in advance during vect_pattern_recog. In this case, STMT may be
2657 of this form:
2658 X = pattern_expr (arg0, arg1, ..., X)
2659 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2660 sequence that had been detected and replaced by the pattern-stmt (STMT).
2662 In some cases of reduction patterns, the type of the reduction variable X is
2663 different than the type of the other arguments of STMT.
2664 In such cases, the vectype that is used when transforming STMT into a vector
2665 stmt is different than the vectype that is used to determine the
2666 vectorization factor, because it consists of a different number of elements
2667 than the actual number of elements that are being operated upon in parallel.
2669 For example, consider an accumulation of shorts into an int accumulator.
2670 On some targets it's possible to vectorize this pattern operating on 8
2671 shorts at a time (hence, the vectype for purposes of determining the
2672 vectorization factor should be V8HI); on the other hand, the vectype that
2673 is used to create the vector form is actually V4SI (the type of the result).
2675 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2676 indicates what is the actual level of parallelism (V8HI in the example), so
2677 that the right vectorization factor would be derived. This vectype
2678 corresponds to the type of arguments to the reduction stmt, and should *NOT*
2679 be used to create the vectorized stmt. The right vectype for the vectorized
2680 stmt is obtained from the type of the result X:
2681 get_vectype_for_scalar_type (TREE_TYPE (X))
2683 This means that, contrary to "regular" reductions (or "regular" stmts in
2684 general), the following equation:
2685 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2686 does *NOT* necessarily hold for reduction patterns. */
2688 bool
2690 {
2691 tree vec_dest;
2692 tree scalar_dest;
2693 tree op;
2699 tree operation;
2707 tree new_phi;
2708 tree scalar_type;
2710 tree orig_stmt;
2711 stmt_vec_info orig_stmt_info;
2716 stmt_vec_info prev_stmt_info;
2717 tree reduc_def;
2722 {
2724 /* FORNOW. This restriction should be relaxed. */
2726 {
2730 }
2731 }
2735 /* FORNOW: SLP not supported. */
2739 /* 1. Is vectorizable reduction? */
2741 /* Not supportable if the reduction variable is used in the loop. */
2745 /* Reductions that are not used even in an enclosing outer-loop,
2746 are expected to be "live" (used out of the loop). */
2751 /* Make sure it was already recognized as a reduction computation. */
2755 /* 2. Has this been recognized as a reduction pattern?
2757 Check if STMT represents a pattern that has been recognized
2758 in earlier analysis stages. For stmts that represent a pattern,
2759 the STMT_VINFO_RELATED_STMT field records the last stmt in
2760 the original sequence that constitutes the pattern. */
2764 {
2769 }
2771 /* 3. Check the operands of the operation. The first operands are defined
2772 inside the loop body. The last operand is the reduction variable,
2773 which is defined by the loop-header-phi. */
2788 /* All uses but the last are expected to be defined in the loop.
2789 The last use is the reduction variable. */
2791 {
2800 }
2809 else
2815 /* 4. Supportable by target? */
2817 /* 4.1. check support for the operation in the loop */
2820 {
2824 }
2827 {
2836 }
2838 /* Worthwhile without SIMD support? */
2842 {
2846 }
2848 /* 4.2. Check support for the epilog operation.
2850 If STMT represents a reduction pattern, then the type of the
2851 reduction variable may be different than the type of the rest
2852 of the arguments. For example, consider the case of accumulation
2853 of shorts into an int accumulator; The original code:
2854 S1: int_a = (int) short_a;
2855 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
2857 was replaced with:
2858 STMT: int_acc = widen_sum <short_a, int_acc>
2860 This means that:
2861 1. The tree-code that is used to create the vector operation in the
2862 epilog code (that reduces the partial results) is not the
2863 tree-code of STMT, but is rather the tree-code of the original
2864 stmt from the pattern that STMT is replacing. I.e, in the example
2865 above we want to use 'widen_sum' in the loop, but 'plus' in the
2866 epilog.
2867 2. The type (mode) we use to check available target support
2868 for the vector operation to be created in the *epilog*, is
2869 determined by the type of the reduction variable (in the example
2870 above we'd check this: plus_optab[vect_int_mode]).
2871 However the type (mode) we use to check available target support
2872 for the vector operation to be created *inside the loop*, is
2873 determined by the type of the other arguments to STMT (in the
2874 example we'd check this: widen_sum_optab[vect_short_mode]).
2876 This is contrary to "regular" reductions, in which the types of all
2877 the arguments are the same as the type of the reduction variable.
2878 For "regular" reductions we can therefore use the same vector type
2879 (and also the same tree-code) when generating the epilog code and
2880 when generating the code inside the loop. */
2883 {
2884 /* This is a reduction pattern: get the vectype from the type of the
2885 reduction variable, and get the tree-code from orig_stmt. */
2889 {
2891 {
2894 }
2896 }
2899 }
2900 else
2901 {
2902 /* Regular reduction: use the same vectype and tree-code as used for
2903 the vector code inside the loop can be used for the epilog code. */
2905 }
2911 {
2915 }
2917 {
2921 }
2924 {
2929 }
2931 /** Transform. **/
2936 /* Create the destination vector */
2939 /* Create the reduction-phi that defines the reduction-operand. */
2942 /* In case the vectorization factor (VF) is bigger than the number
2943 of elements that we can fit in a vectype (nunits), we have to generate
2944 more than one vector stmt - i.e - we need to "unroll" the
2945 vector stmt by a factor VF/nunits. For more details see documentation
2946 in vectorizable_operation. */
2950 {
2951 /* Handle uses. */
2953 {
2957 {
2960 }
2962 /* Get the vector def for the reduction variable from the phi node */
2964 }
2965 else
2966 {
2972 /* Get the vector def for the reduction variable from the vectorized
2973 reduction operation generated in the previous iteration (j-1) */
2975 }
2977 /* Arguments are ready. create the new vector stmt. */
2980 else
2982 reduc_def);
2990 else
2993 }
2995 /* Finalize the reduction-phi (set it's arguments) and create the
2996 epilog reduction code. */
2999 }
3001 /* Checks if CALL can be vectorized in type VECTYPE. Returns
3002 a function declaration if the target has a vectorized version
3003 of the function, or NULL_TREE if the function cannot be vectorized. */
3005 tree
3007 {
3011 /* We only handle functions that do not read or clobber memory -- i.e.
3012 const or novops ones. */
3023 vectype_in);
3024 }
3026 /* Function vectorizable_call.
3028 Check if STMT performs a function call that can be vectorized.
3029 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3030 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3031 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3033 bool
3035 {
3036 tree vec_dest;
3037 tree scalar_dest;
3038 tree operation;
3049 tree new_stmt;
3051 call_expr_arg_iterator iter;
3052 tree vargs;
3061 /* FORNOW: SLP not supported. */
3065 /* Is STMT a vectorizable call? */
3076 /* Process function arguments. */
3080 {
3081 /* Bail out if the function has more than two arguments, we
3082 do not have interesting builtin functions to vectorize with
3083 more than two arguments. */
3087 /* We can only handle calls with arguments of the same type. */
3090 {
3094 }
3098 {
3102 }
3105 }
3107 /* No arguments is also not good. */
3122 /* FORNOW */
3129 else
3132 /* For now, we only vectorize functions if a target specific builtin
3133 is available. TODO -- in some cases, it might be profitable to
3134 insert the calls for pieces of the vector, in order to be able
3135 to vectorize other operations in the loop. */
3138 {
3143 }
3149 else
3152 /* Sanity check: make sure that at least one copy of the vectorized stmt
3153 needs to be generated. */
3156 /* FORNOW. This restriction should be relaxed. */
3158 {
3162 }
3165 {
3171 }
3173 /** Transform. **/
3178 /* FORNOW. This restriction should be relaxed. */
3180 {
3184 }
3186 /* Handle def. */
3192 {
3195 {
3196 /* Build argument list for the vectorized call. */
3197 /* FIXME: Rewrite this so that it doesn't
3198 construct a temporary list. */
3202 {
3204 vec_oprnd0
3206 else
3207 vec_oprnd0
3213 }
3225 else
3229 }
3235 {
3236 /* Build argument list for the vectorized call. */
3237 /* FIXME: Rewrite this so that it doesn't
3238 construct a temporary list. */
3242 {
3244 {
3245 vec_oprnd0
3247 vec_oprnd1
3249 }
3250 else
3251 {
3252 vec_oprnd0
3254 vec_oprnd1
3256 }
3262 }
3274 else
3278 }
3285 /* No current target implements this case. */
3287 }
3289 /* The call in STMT might prevent it from being removed in dce.
3290 We however cannot remove it here, due to the way the ssa name
3291 it defines is mapped to the new definition. So just replace
3292 rhs of the statement with something harmless. */
3298 }
3301 /* Function vect_gen_widened_results_half
3303 Create a vector stmt whose code, type, number of arguments, and result
3304 variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are
3305 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
3306 In the case that CODE is a CALL_EXPR, this means that a call to DECL
3307 needs to be created (DECL is a function-decl of a target-builtin).
3308 STMT is the original scalar stmt that we are vectorizing. */
3310 static tree
3314 tree stmt)
3315 {
3316 tree expr;
3317 tree new_stmt;
3318 tree new_temp;
3319 tree sym;
3320 ssa_op_iter iter;
3322 /* Generate half of the widened result: */
3324 {
3325 /* Target specific support */
3328 else
3330 }
3331 else
3332 {
3333 /* Generic support */
3337 else
3339 }
3346 {
3348 {
3352 }
3353 }
3356 }
3359 /* Check if STMT performs a conversion operation, that can be vectorized.
3360 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3361 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3362 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3364 bool
3367 {
3368 tree vec_dest;
3369 tree scalar_dest;
3370 tree operation;
3371 tree op0;
3378 tree new_temp;
3382 stmt_vec_info prev_stmt_info;
3387 tree expr;
3389 tree builtin_decl;
3393 tree vop0;
3395 /* Is STMT a vectorizable conversion? */
3414 /* Check types of lhs and rhs. */
3429 /* FORNOW */
3436 else
3442 /* Bail out if the types are both integral or non-integral. */
3449 else
3452 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3453 this, so we can safely override NCOPIES with 1 here. */
3457 /* Sanity check: make sure that at least one copy of the vectorized stmt
3458 needs to be generated. */
3461 /* FORNOW. This restriction should be relaxed. */
3463 {
3467 }
3469 /* Check the operands of the operation. */
3471 {
3475 }
3477 /* Supportable by target? */
3487 {
3491 }
3494 {
3496 /* FORNOW: SLP not supported. */
3499 }
3502 {
3505 }
3507 /** Transform. **/
3511 /* Handle def. */
3519 {
3522 {
3523 tree sym;
3524 ssa_op_iter iter;
3528 else
3531 builtin_decl =
3534 {
3537 /* Arguments are ready. create the new vector stmt. */
3543 SSA_OP_ALL_VIRTUALS)
3544 {
3548 }
3551 }
3555 else
3558 }
3562 /* In case the vectorization factor (VF) is bigger than the number
3563 of elements that we can fit in a vectype (nunits), we have to
3564 generate more than one vector stmt - i.e - we need to "unroll"
3565 the vector stmt by a factor VF/nunits. */
3567 {
3570 else
3575 /* Generate first half of the widened result: */
3576 new_stmt
3582 else
3586 /* Generate second half of the widened result: */
3587 new_stmt
3593 }
3597 /* In case the vectorization factor (VF) is bigger than the number
3598 of elements that we can fit in a vectype (nunits), we have to
3599 generate more than one vector stmt - i.e - we need to "unroll"
3600 the vector stmt by a factor VF/nunits. */
3602 {
3603 /* Handle uses. */
3605 {
3608 }
3609 else
3610 {
3613 }
3615 /* Arguments are ready. Create the new vector stmt. */
3624 else
3628 }
3631 }
3637 }
3640 /* Function vectorizable_assignment.
3642 Check if STMT performs an assignment (copy) that can be vectorized.
3643 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3644 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3645 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3647 bool
3649 slp_tree slp_node)
3650 {
3651 tree vec_dest;
3652 tree scalar_dest;
3653 tree op;
3657 tree new_temp;
3664 tree vop;
3666 /* FORNOW: SLP with multiple types is not supported. The SLP analysis
3667 verifies this, so we can safely override NCOPIES with 1 here. */
3681 /* Is vectorizable assignment? */
3691 {
3695 }
3698 {
3704 }
3706 /** Transform. **/
3710 /* Handle def. */
3713 /* Handle use. */
3716 /* Arguments are ready. create the new vector stmt. */
3718 {
3727 }
3731 }
3734 /* Function vect_min_worthwhile_factor.
3736 For a loop where we could vectorize the operation indicated by CODE,
3737 return the minimum vectorization factor that makes it worthwhile
3738 to use generic vectors. */
3739 static int
3741 {
3743 {
3757 }
3758 }
3761 /* Function vectorizable_induction
3763 Check if PHI performs an induction computation that can be vectorized.
3764 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3765 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3766 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3768 bool
3771 {
3777 tree vec_def;
3784 /* FORNOW: SLP not supported. */
3794 {
3800 }
3802 /** Transform. **/
3810 }
3813 /* Function vectorizable_operation.
3815 Check if STMT performs a binary or unary operation that can be vectorized.
3816 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3817 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3818 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3820 bool
3822 slp_tree slp_node)
3823 {
3824 tree vec_dest;
3825 tree scalar_dest;
3826 tree operation;
3835 tree new_temp;
3837 optab optab;
3843 stmt_vec_info prev_stmt_info;
3846 tree vectype_out;
3855 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3856 this, so we can safely override NCOPIES with 1 here. */
3860 /* FORNOW. This restriction should be relaxed. */
3862 {
3866 }
3874 /* Is STMT a vectorizable binary/unary operation? */
3892 /* For pointer addition, we should use the normal plus for
3893 the vector addition. */
3897 /* Support only unary or binary operations. */
3900 {
3904 }
3908 {
3912 }
3915 {
3918 {
3922 }
3923 }
3925 /* If this is a shift/rotate, determine whether the shift amount is a vector,
3926 or scalar. If the shift/rotate amount is a vector, use the vector/vector
3927 shift optabs. */
3930 {
3933 /* vector shifted by vector */
3935 {
3939 }
3941 /* See if the machine has a vector shifted by scalar insn and if not
3942 then see if it has a vector shifted by vector insn */
3944 {
3949 {
3953 }
3954 else
3955 {
3958 && optab
3962 }
3963 }
3965 else
3966 {
3970 }
3971 }
3972 else
3975 /* Supportable by target? */
3977 {
3981 }
3985 {
3988 /* Check only during analysis. */
3996 }
3998 /* Worthwhile without SIMD support? Check only during analysis. */
4003 {
4007 }
4010 {
4016 }
4018 /** Transform. **/
4023 /* Handle def. */
4026 /* Allocate VECs for vector operands. In case of SLP, vector operands are
4027 created in the previous stages of the recursion, so no allocation is
4028 needed, except for the case of shift with scalar shift argument. In that
4029 case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
4030 be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
4031 In case of loop-based vectorization we allocate VECs of size 1. We
4032 allocate VEC_OPRNDS1 only in case of binary operation. */
4034 {
4038 }
4042 /* In case the vectorization factor (VF) is bigger than the number
4043 of elements that we can fit in a vectype (nunits), we have to generate
4044 more than one vector stmt - i.e - we need to "unroll" the
4045 vector stmt by a factor VF/nunits. In doing so, we record a pointer
4046 from one copy of the vector stmt to the next, in the field
4047 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
4048 stages to find the correct vector defs to be used when vectorizing
4049 stmts that use the defs of the current stmt. The example below illustrates
4050 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
4051 4 vectorized stmts):
4053 before vectorization:
4054 RELATED_STMT VEC_STMT
4055 S1: x = memref - -
4056 S2: z = x + 1 - -
4058 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
4059 there):
4060 RELATED_STMT VEC_STMT
4061 VS1_0: vx0 = memref0 VS1_1 -
4062 VS1_1: vx1 = memref1 VS1_2 -
4063 VS1_2: vx2 = memref2 VS1_3 -
4064 VS1_3: vx3 = memref3 - -
4065 S1: x = load - VS1_0
4066 S2: z = x + 1 - -
4068 step2: vectorize stmt S2 (done here):
4069 To vectorize stmt S2 we first need to find the relevant vector
4070 def for the first operand 'x'. This is, as usual, obtained from
4071 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
4072 that defines 'x' (S1). This way we find the stmt VS1_0, and the
4073 relevant vector def 'vx0'. Having found 'vx0' we can generate
4074 the vector stmt VS2_0, and as usual, record it in the
4075 STMT_VINFO_VEC_STMT of stmt S2.
4076 When creating the second copy (VS2_1), we obtain the relevant vector
4077 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
4078 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
4079 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
4080 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
4081 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
4082 chain of stmts and pointers:
4083 RELATED_STMT VEC_STMT
4084 VS1_0: vx0 = memref0 VS1_1 -
4085 VS1_1: vx1 = memref1 VS1_2 -
4086 VS1_2: vx2 = memref2 VS1_3 -
4087 VS1_3: vx3 = memref3 - -
4088 S1: x = load - VS1_0
4089 VS2_0: vz0 = vx0 + v1 VS2_1 -
4090 VS2_1: vz1 = vx1 + v1 VS2_2 -
4091 VS2_2: vz2 = vx2 + v1 VS2_3 -
4092 VS2_3: vz3 = vx3 + v1 - -
4093 S2: z = x + 1 - VS2_0 */
4097 {
4098 /* Handle uses. */
4100 {
4102 {
4103 /* Vector shl and shr insn patterns can be defined with scalar
4104 operand 2 (shift operand). In this case, use constant or loop
4105 invariant op1 directly, without extending it to vector mode
4106 first. */
4109 {
4115 {
4116 /* Store vec_oprnd1 for every vector stmt to be created
4117 for SLP_NODE. We check during the analysis that all the
4118 shift arguments are the same.
4119 TODO: Allow different constants for different vector
4120 stmts generated for an SLP instance. */
4123 }
4124 }
4125 }
4127 /* vec_oprnd1 is available if operand 1 should be of a scalar-type
4128 (a special case for certain kind of vector shifts); otherwise,
4129 operand 1 should be of a vector type (the usual case). */
4132 slp_node);
4133 else
4135 slp_node);
4136 }
4137 else
4140 /* Arguments are ready. Create the new vector stmt. */
4142 {
4144 {
4148 }
4149 else
4158 }
4162 else
4165 }
4172 }
4175 /* Function vectorizable_type_demotion
4177 Check if STMT performs a binary or unary operation that involves
4178 type demotion, and if it can be vectorized.
4179 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4180 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4181 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4183 bool
4186 {
4187 tree vec_dest;
4188 tree scalar_dest;
4189 tree operation;
4190 tree op0;
4196 tree new_temp;
4199 tree new_stmt;
4200 stmt_vec_info prev_stmt_info;
4203 tree vectype_out;
4206 tree expr;
4207 tree vectype_in;
4215 /* Is STMT a vectorizable type-demotion operation? */
4243 /* FORNOW. This restriction should be relaxed. */
4245 {
4249 }
4258 /* Check the operands of the operation. */
4260 {
4264 }
4266 /* Supportable by target? */
4273 {
4279 }
4281 /** Transform. **/
4284 ncopies);
4286 /* Handle def. */
4289 /* In case the vectorization factor (VF) is bigger than the number
4290 of elements that we can fit in a vectype (nunits), we have to generate
4291 more than one vector stmt - i.e - we need to "unroll" the
4292 vector stmt by a factor VF/nunits. */
4295 {
4296 /* Handle uses. */
4298 {
4301 }
4302 else
4303 {
4306 }
4308 /* Arguments are ready. Create the new vector stmt. */
4317 else
4321 }
4325 }
4328 /* Function vectorizable_type_promotion
4330 Check if STMT performs a binary or unary operation that involves
4331 type promotion, and if it can be vectorized.
4332 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4333 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4334 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4336 bool
4339 {
4340 tree vec_dest;
4341 tree scalar_dest;
4342 tree operation;
4353 tree new_stmt;
4354 stmt_vec_info prev_stmt_info;
4357 tree vectype_out;
4360 tree vectype_in;
4368 /* Is STMT a vectorizable type-promotion operation? */
4397 /* FORNOW. This restriction should be relaxed. */
4399 {
4403 }
4412 /* Check the operands of the operation. */
4414 {
4418 }
4422 {
4425 {
4429 }
4430 }
4432 /* Supportable by target? */
4440 {
4446 }
4448 /** Transform. **/
4452 ncopies);
4454 /* Handle def. */
4457 /* In case the vectorization factor (VF) is bigger than the number
4458 of elements that we can fit in a vectype (nunits), we have to generate
4459 more than one vector stmt - i.e - we need to "unroll" the
4460 vector stmt by a factor VF/nunits. */
4464 {
4465 /* Handle uses. */
4467 {
4471 }
4472 else
4473 {
4477 }
4479 /* Arguments are ready. Create the new vector stmt. We are creating
4480 two vector defs because the widened result does not fit in one vector.
4481 The vectorized stmt can be expressed as a call to a target builtin,
4482 or a using a tree-code. */
4483 /* Generate first half of the widened result: */
4488 else
4492 /* Generate second half of the widened result: */
4498 }
4502 }
4505 /* Function vect_strided_store_supported.
4507 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
4508 and FALSE otherwise. */
4510 static bool
4512 {
4518 /* Check that the operation is supported. */
4524 {
4528 }
4531 == CODE_FOR_nothing
4534 {
4538 }
4541 }
4544 /* Function vect_permute_store_chain.
4546 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4547 a power of 2, generate interleave_high/low stmts to reorder the data
4548 correctly for the stores. Return the final references for stores in
4549 RESULT_CHAIN.
4551 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4552 The input is 4 vectors each containing 8 elements. We assign a number to each
4553 element, the input sequence is:
4555 1st vec: 0 1 2 3 4 5 6 7
4556 2nd vec: 8 9 10 11 12 13 14 15
4557 3rd vec: 16 17 18 19 20 21 22 23
4558 4th vec: 24 25 26 27 28 29 30 31
4560 The output sequence should be:
4562 1st vec: 0 8 16 24 1 9 17 25
4563 2nd vec: 2 10 18 26 3 11 19 27
4564 3rd vec: 4 12 20 28 5 13 21 30
4565 4th vec: 6 14 22 30 7 15 23 31
4567 i.e., we interleave the contents of the four vectors in their order.
4569 We use interleave_high/low instructions to create such output. The input of
4570 each interleave_high/low operation is two vectors:
4571 1st vec 2nd vec
4572 0 1 2 3 4 5 6 7
4573 the even elements of the result vector are obtained left-to-right from the
4574 high/low elements of the first vector. The odd elements of the result are
4575 obtained left-to-right from the high/low elements of the second vector.
4576 The output of interleave_high will be: 0 4 1 5
4577 and of interleave_low: 2 6 3 7
4580 The permutation is done in log LENGTH stages. In each stage interleave_high
4581 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4582 where the first argument is taken from the first half of DR_CHAIN and the
4583 second argument from it's second half.
4584 In our example,
4586 I1: interleave_high (1st vec, 3rd vec)
4587 I2: interleave_low (1st vec, 3rd vec)
4588 I3: interleave_high (2nd vec, 4th vec)
4589 I4: interleave_low (2nd vec, 4th vec)
4591 The output for the first stage is:
4593 I1: 0 16 1 17 2 18 3 19
4594 I2: 4 20 5 21 6 22 7 23
4595 I3: 8 24 9 25 10 26 11 27
4596 I4: 12 28 13 29 14 30 15 31
4598 The output of the second stage, i.e. the final result is:
4600 I1: 0 8 16 24 1 9 17 25
4601 I2: 2 10 18 26 3 11 19 27
4602 I3: 4 12 20 28 5 13 21 30
4603 I4: 6 14 22 30 7 15 23 31. */
4605 static bool
4608 tree stmt,
4611 {
4620 /* Check that the operation is supported. */
4627 {
4629 {
4633 /* Create interleaving stmt:
4634 in the case of big endian:
4635 high = interleave_high (vect1, vect2)
4636 and in the case of little endian:
4637 high = interleave_low (vect1, vect2). */
4643 else
4651 /* Create interleaving stmt:
4652 in the case of big endian:
4653 low = interleave_low (vect1, vect2)
4654 and in the case of little endian:
4655 low = interleave_high (vect1, vect2). */
4661 else
4668 }
4670 }
4672 }
4675 /* Function vectorizable_store.
4677 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
4678 can be vectorized.
4679 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4680 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4681 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4683 bool
4685 slp_tree slp_node)
4686 {
4687 tree scalar_dest;
4688 tree data_ref;
4689 tree op;
4697 tree dummy;
4713 stmt_vec_info first_stmt_vinfo;
4716 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
4717 this, so we can safely override NCOPIES with 1 here. */
4723 /* FORNOW. This restriction should be relaxed. */
4725 {
4729 }
4737 /* Is vectorizable store? */
4750 {
4754 }
4756 /* If accesses through a pointer to vectype do not alias the original
4757 memory reference we have a problem. */
4761 {
4765 }
4768 {
4772 }
4775 /* FORNOW. In some cases can vectorize even if data-type not supported
4776 (e.g. - array initialization with 0). */
4784 {
4792 {
4793 /* STMT is the leader of the group. Check the operands of all the
4794 stmts of the group. */
4797 {
4800 {
4804 }
4806 }
4807 }
4808 }
4811 {
4816 }
4818 /** Transform. **/
4821 {
4827 /* FORNOW */
4830 /* We vectorize all the stmts of the interleaving group when we
4831 reach the last stmt in the group. */
4835 {
4838 }
4843 /* VEC_NUM is the number of vect stmts to be created for this group. */
4846 else
4848 }
4849 else
4850 {
4855 }
4867 /* In case the vectorization factor (VF) is bigger than the number
4868 of elements that we can fit in a vectype (nunits), we have to generate
4869 more than one vector stmt - i.e - we need to "unroll" the
4870 vector stmt by a factor VF/nunits. For more details see documentation in
4871 vect_get_vec_def_for_copy_stmt. */
4873 /* In case of interleaving (non-unit strided access):
4875 S1: &base + 2 = x2
4876 S2: &base = x0
4877 S3: &base + 1 = x1
4878 S4: &base + 3 = x3
4880 We create vectorized stores starting from base address (the access of the
4881 first stmt in the chain (S2 in the above example), when the last store stmt
4882 of the chain (S4) is reached:
4884 VS1: &base = vx2
4885 VS2: &base + vec_size*1 = vx0
4886 VS3: &base + vec_size*2 = vx1
4887 VS4: &base + vec_size*3 = vx3
4889 Then permutation statements are generated:
4891 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
4892 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
4893 ...
4895 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
4896 (the order of the data-refs in the output of vect_permute_store_chain
4897 corresponds to the order of scalar stmts in the interleaving chain - see
4898 the documentation of vect_permute_store_chain()).
4900 In case of both multiple types and interleaving, above vector stores and
4901 permutation stmts are created for every copy. The result vector stmts are
4902 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
4903 STMT_VINFO_RELATED_STMT for the next copies.
4904 */
4908 {
4909 tree new_stmt;
4910 tree ptr_incr;
4913 {
4915 {
4916 /* Get vectorized arguments for SLP_NODE. */
4920 }
4921 else
4922 {
4923 /* For interleaved stores we collect vectorized defs for all the
4924 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
4925 used as an input to vect_permute_store_chain(), and OPRNDS as
4926 an input to vect_get_vec_def_for_stmt_copy() for the next copy.
4928 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4929 OPRNDS are of size 1. */
4932 {
4933 /* Since gaps are not supported for interleaved stores,
4934 GROUP_SIZE is the exact number of stmts in the chain.
4935 Therefore, NEXT_STMT can't be NULL_TREE. In case that
4936 there is no interleaving, GROUP_SIZE is 1, and only one
4937 iteration of the loop will be executed. */
4942 NULL);
4946 }
4947 }
4953 }
4954 else
4955 {
4956 /* FORNOW SLP doesn't work for multiple types. */
4959 /* For interleaved stores we created vectorized defs for all the
4960 defs stored in OPRNDS in the previous iteration (previous copy).
4961 DR_CHAIN is then used as an input to vect_permute_store_chain(),
4962 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
4963 next copy.
4964 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4965 OPRNDS are of size 1. */
4967 {
4973 }
4974 dataref_ptr =
4976 }
4979 {
4981 /* Permute. */
4985 }
4989 {
4991 /* Bump the vector pointer. */
4993 NULL_TREE);
4998 /* For strided stores vectorized defs are interleaved in
4999 vect_permute_store_chain(). */
5003 /* Arguments are ready. Create the new vector stmt. */
5010 else
5017 }
5018 }
5026 }
5029 /* Function vect_setup_realignment
5031 This function is called when vectorizing an unaligned load using
5032 the dr_explicit_realign[_optimized] scheme.
5033 This function generates the following code at the loop prolog:
5035 p = initial_addr;
5036 x msq_init = *(floor(p)); # prolog load
5037 realignment_token = call target_builtin;
5038 loop:
5039 x msq = phi (msq_init, ---)
5041 The stmts marked with x are generated only for the case of
5042 dr_explicit_realign_optimized.
5044 The code above sets up a new (vector) pointer, pointing to the first
5045 location accessed by STMT, and a "floor-aligned" load using that pointer.
5046 It also generates code to compute the "realignment-token" (if the relevant
5047 target hook was defined), and creates a phi-node at the loop-header bb
5048 whose arguments are the result of the prolog-load (created by this
5049 function) and the result of a load that takes place in the loop (to be
5050 created by the caller to this function).
5052 For the case of dr_explicit_realign_optimized:
5053 The caller to this function uses the phi-result (msq) to create the
5054 realignment code inside the loop, and sets up the missing phi argument,
5055 as follows:
5056 loop:
5057 msq = phi (msq_init, lsq)
5058 lsq = *(floor(p')); # load in loop
5059 result = realign_load (msq, lsq, realignment_token);
5061 For the case of dr_explicit_realign:
5062 loop:
5063 msq = *(floor(p)); # load in loop
5064 p' = p + (VS-1);
5065 lsq = *(floor(p')); # load in loop
5066 result = realign_load (msq, lsq, realignment_token);
5068 Input:
5069 STMT - (scalar) load stmt to be vectorized. This load accesses
5070 a memory location that may be unaligned.
5071 BSI - place where new code is to be inserted.
5072 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
5073 is used.
5075 Output:
5076 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
5077 target hook, if defined.
5078 Return value - the result of the loop-header phi node. */
5080 static tree
5084 tree init_addr,
5086 {
5091 edge pe;
5093 tree vec_dest;
5094 tree inc;
5095 tree ptr;
5096 tree data_ref;
5097 tree new_stmt;
5098 basic_block new_bb;
5100 tree new_temp;
5101 tree phi_stmt;
5113 /* We need to generate three things:
5114 1. the misalignment computation
5115 2. the extra vector load (for the optimized realignment scheme).
5116 3. the phi node for the two vectors from which the realignment is
5117 done (for the optimized realignment scheme).
5118 */
5120 /* 1. Determine where to generate the misalignment computation.
5122 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
5123 calculation will be generated by this function, outside the loop (in the
5124 preheader). Otherwise, INIT_ADDR had already been computed for us by the
5125 caller, inside the loop.
5127 Background: If the misalignment remains fixed throughout the iterations of
5128 the loop, then both realignment schemes are applicable, and also the
5129 misalignment computation can be done outside LOOP. This is because we are
5130 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
5131 are a multiple of VS (the Vector Size), and therefore the misalignment in
5132 different vectorized LOOP iterations is always the same.
5133 The problem arises only if the memory access is in an inner-loop nested
5134 inside LOOP, which is now being vectorized using outer-loop vectorization.
5135 This is the only case when the misalignment of the memory access may not
5136 remain fixed throughout the iterations of the inner-loop (as explained in
5137 detail in vect_supportable_dr_alignment). In this case, not only is the
5138 optimized realignment scheme not applicable, but also the misalignment
5139 computation (and generation of the realignment token that is passed to
5140 REALIGN_LOAD) have to be done inside the loop.
5142 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
5143 or not, which in turn determines if the misalignment is computed inside
5144 the inner-loop, or outside LOOP. */
5147 {
5150 }
5153 /* 2. Determine where to generate the extra vector load.
5155 For the optimized realignment scheme, instead of generating two vector
5156 loads in each iteration, we generate a single extra vector load in the
5157 preheader of the loop, and in each iteration reuse the result of the
5158 vector load from the previous iteration. In case the memory access is in
5159 an inner-loop nested inside LOOP, which is now being vectorized using
5160 outer-loop vectorization, we need to determine whether this initial vector
5161 load should be generated at the preheader of the inner-loop, or can be
5162 generated at the preheader of LOOP. If the memory access has no evolution
5163 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
5164 to be generated inside LOOP (in the preheader of the inner-loop). */
5167 {
5172 }
5173 else
5178 /* 3. For the case of the optimized realignment, create the first vector
5179 load at the loop preheader. */
5182 {
5183 /* Create msq_init = *(floor(p1)) in the loop preheader */
5198 }
5200 /* 4. Create realignment token using a target builtin, if available.
5201 It is done either inside the containing loop, or before LOOP (as
5202 determined above). */
5205 {
5206 tree builtin_decl;
5208 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
5211 else
5212 {
5213 /* Generate the INIT_ADDR computation outside LOOP. */
5219 }
5231 else
5232 {
5233 /* Generate the misalignment computation outside LOOP. */
5237 }
5241 /* The result of the CALL_EXPR to this builtin is determined from
5242 the value of the parameter and no global variables are touched
5243 which makes the builtin a "const" function. Requiring the
5244 builtin to have the "const" attribute makes it unnecessary
5245 to call mark_call_clobbered. */
5247 }
5256 /* 5. Create msq = phi <msq_init, lsq> in loop */
5266 }
5269 /* Function vect_strided_load_supported.
5271 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
5272 and FALSE otherwise. */
5274 static bool
5276 {
5283 optab_default);
5285 {
5289 }
5292 {
5296 }
5299 optab_default);
5301 {
5305 }
5308 {
5312 }
5314 }
5317 /* Function vect_permute_load_chain.
5319 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
5320 a power of 2, generate extract_even/odd stmts to reorder the input data
5321 correctly. Return the final references for loads in RESULT_CHAIN.
5323 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
5324 The input is 4 vectors each containing 8 elements. We assign a number to each
5325 element, the input sequence is:
5327 1st vec: 0 1 2 3 4 5 6 7
5328 2nd vec: 8 9 10 11 12 13 14 15
5329 3rd vec: 16 17 18 19 20 21 22 23
5330 4th vec: 24 25 26 27 28 29 30 31
5332 The output sequence should be:
5334 1st vec: 0 4 8 12 16 20 24 28
5335 2nd vec: 1 5 9 13 17 21 25 29
5336 3rd vec: 2 6 10 14 18 22 26 30
5337 4th vec: 3 7 11 15 19 23 27 31
5339 i.e., the first output vector should contain the first elements of each
5340 interleaving group, etc.
5342 We use extract_even/odd instructions to create such output. The input of each
5343 extract_even/odd operation is two vectors
5344 1st vec 2nd vec
5345 0 1 2 3 4 5 6 7
5347 and the output is the vector of extracted even/odd elements. The output of
5348 extract_even will be: 0 2 4 6
5349 and of extract_odd: 1 3 5 7
5352 The permutation is done in log LENGTH stages. In each stage extract_even and
5353 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
5354 order. In our example,
5356 E1: extract_even (1st vec, 2nd vec)
5357 E2: extract_odd (1st vec, 2nd vec)
5358 E3: extract_even (3rd vec, 4th vec)
5359 E4: extract_odd (3rd vec, 4th vec)
5361 The output for the first stage will be:
5363 E1: 0 2 4 6 8 10 12 14
5364 E2: 1 3 5 7 9 11 13 15
5365 E3: 16 18 20 22 24 26 28 30
5366 E4: 17 19 21 23 25 27 29 31
5368 In order to proceed and create the correct sequence for the next stage (or
5369 for the correct output, if the second stage is the last one, as in our
5370 example), we first put the output of extract_even operation and then the
5371 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
5372 The input for the second stage is:
5374 1st vec (E1): 0 2 4 6 8 10 12 14
5375 2nd vec (E3): 16 18 20 22 24 26 28 30
5376 3rd vec (E2): 1 3 5 7 9 11 13 15
5377 4th vec (E4): 17 19 21 23 25 27 29 31
5379 The output of the second stage:
5381 E1: 0 4 8 12 16 20 24 28
5382 E2: 2 6 10 14 18 22 26 30
5383 E3: 1 5 9 13 17 21 25 29
5384 E4: 3 7 11 15 19 23 27 31
5386 And RESULT_CHAIN after reordering:
5388 1st vec (E1): 0 4 8 12 16 20 24 28
5389 2nd vec (E3): 1 5 9 13 17 21 25 29
5390 3rd vec (E2): 2 6 10 14 18 22 26 30
5391 4th vec (E4): 3 7 11 15 19 23 27 31. */
5393 static bool
5396 tree stmt,
5399 {
5402 tree tmp;
5406 /* Check that the operation is supported. */
5412 {
5414 {
5418 /* data_ref = permute_even (first_data_ref, second_data_ref); */
5434 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
5448 }
5450 }
5452 }
5455 /* Function vect_transform_strided_load.
5457 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
5458 to perform their permutation and ascribe the result vectorized statements to
5459 the scalar statements.
5460 */
5462 static bool
5465 {
5471 tree tmp_data_ref;
5473 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
5474 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
5475 vectors, that are ready for vector computation. */
5477 /* Permute. */
5481 /* Put a permuted data-ref in the VECTORIZED_STMT field.
5482 Since we scan the chain starting from it's first node, their order
5483 corresponds the order of data-refs in RESULT_CHAIN. */
5487 {
5491 /* Skip the gaps. Loads created for the gaps will be removed by dead
5492 code elimination pass later. No need to check for the first stmt in
5493 the group, since it always exists.
5494 DR_GROUP_GAP is the number of steps in elements from the previous
5495 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
5496 correspond to the gaps.
5497 */
5500 {
5501 gap_count++;
5503 }
5506 {
5508 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
5509 copies, and we put the new vector statement in the first available
5510 RELATED_STMT. */
5513 else
5514 {
5519 {
5522 }
5524 }
5527 /* If NEXT_STMT accesses the same DR as the previous statement,
5528 put the same TMP_DATA_REF as its vectorized statement; otherwise
5529 get the next data-ref from RESULT_CHAIN. */
5532 }
5533 }
5537 }
5540 /* vectorizable_load.
5542 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
5543 can be vectorized.
5544 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5545 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5546 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5548 bool
5550 slp_tree slp_node)
5551 {
5552 tree scalar_dest;
5555 tree op;
5557 stmt_vec_info prev_stmt_info;
5564 tree new_temp;
5567 tree dummy;
5570 tree ptr_incr;
5580 tree first_stmt;
5581 tree scalar_type;
5588 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
5589 this, so we can safely override NCOPIES with 1 here. */
5595 /* FORNOW. This restriction should be relaxed. */
5597 {
5601 }
5609 /* Is vectorizable load? */
5629 /* FORNOW. In some cases can vectorize even if data-type not supported
5630 (e.g. - data copies). */
5632 {
5636 }
5638 /* If accesses through a pointer to vectype do not alias the original
5639 memory reference we have a problem. */
5643 {
5647 }
5649 /* Check if the load is a part of an interleaving chain. */
5651 {
5653 /* FORNOW */
5656 /* Check if interleaving is supported. */
5660 }
5663 {
5667 }
5672 /** Transform. **/
5675 {
5677 /* Check if the chain of loads is already vectorized. */
5679 {
5682 }
5687 /* VEC_NUM is the number of vect stmts to be created for this group. */
5689 {
5692 }
5693 else
5695 }
5696 else
5697 {
5701 }
5706 /* In case the vectorization factor (VF) is bigger than the number
5707 of elements that we can fit in a vectype (nunits), we have to generate
5708 more than one vector stmt - i.e - we need to "unroll" the
5709 vector stmt by a factor VF/nunits. In doing so, we record a pointer
5710 from one copy of the vector stmt to the next, in the field
5711 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
5712 stages to find the correct vector defs to be used when vectorizing
5713 stmts that use the defs of the current stmt. The example below illustrates
5714 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
5715 4 vectorized stmts):
5717 before vectorization:
5718 RELATED_STMT VEC_STMT
5719 S1: x = memref - -
5720 S2: z = x + 1 - -
5722 step 1: vectorize stmt S1:
5723 We first create the vector stmt VS1_0, and, as usual, record a
5724 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
5725 Next, we create the vector stmt VS1_1, and record a pointer to
5726 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
5727 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
5728 stmts and pointers:
5729 RELATED_STMT VEC_STMT
5730 VS1_0: vx0 = memref0 VS1_1 -
5731 VS1_1: vx1 = memref1 VS1_2 -
5732 VS1_2: vx2 = memref2 VS1_3 -
5733 VS1_3: vx3 = memref3 - -
5734 S1: x = load - VS1_0
5735 S2: z = x + 1 - -
5737 See in documentation in vect_get_vec_def_for_stmt_copy for how the
5738 information we recorded in RELATED_STMT field is used to vectorize
5739 stmt S2. */
5741 /* In case of interleaving (non-unit strided access):
5743 S1: x2 = &base + 2
5744 S2: x0 = &base
5745 S3: x1 = &base + 1
5746 S4: x3 = &base + 3
5748 Vectorized loads are created in the order of memory accesses
5749 starting from the access of the first stmt of the chain:
5751 VS1: vx0 = &base
5752 VS2: vx1 = &base + vec_size*1
5753 VS3: vx3 = &base + vec_size*2
5754 VS4: vx4 = &base + vec_size*3
5756 Then permutation statements are generated:
5758 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
5759 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
5760 ...
5762 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
5763 (the order of the data-refs in the output of vect_permute_load_chain
5764 corresponds to the order of scalar stmts in the interleaving chain - see
5765 the documentation of vect_permute_load_chain()).
5766 The generation of permutation stmts and recording them in
5767 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
5769 In case of both multiple types and interleaving, the vector loads and
5770 permutation stmts above are created for every copy. The result vector stmts
5771 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
5772 STMT_VINFO_RELATED_STMT for the next copies. */
5774 /* If the data reference is aligned (dr_aligned) or potentially unaligned
5775 on a target that supports unaligned accesses (dr_unaligned_supported)
5776 we generate the following code:
5777 p = initial_addr;
5778 indx = 0;
5779 loop {
5780 p = p + indx * vectype_size;
5781 vec_dest = *(p);
5782 indx = indx + 1;
5783 }
5785 Otherwise, the data reference is potentially unaligned on a target that
5786 does not support unaligned accesses (dr_explicit_realign_optimized) -
5787 then generate the following code, in which the data in each iteration is
5788 obtained by two vector loads, one from the previous iteration, and one
5789 from the current iteration:
5790 p1 = initial_addr;
5791 msq_init = *(floor(p1))
5792 p2 = initial_addr + VS - 1;
5793 realignment_token = call target_builtin;
5794 indx = 0;
5795 loop {
5796 p2 = p2 + indx * vectype_size
5797 lsq = *(floor(p2))
5798 vec_dest = realign_load (msq, lsq, realignment_token)
5799 indx = indx + 1;
5800 msq = lsq;
5801 } */
5803 /* If the misalignment remains the same throughout the execution of the
5804 loop, we can create the init_addr and permutation mask at the loop
5805 preheader. Otherwise, it needs to be created inside the loop.
5806 This can only occur when vectorizing memory accesses in the inner-loop
5807 nested within an outer-loop that is being vectorized. */
5812 {
5815 }
5820 {
5825 {
5828 }
5829 }
5830 else
5835 {
5836 /* 1. Create the vector pointer update chain. */
5842 else
5843 dataref_ptr =
5847 {
5850 NULL_TREE);
5852 /* 2. Create the vector-load in the loop. */
5854 {
5860 {
5865 data_ref =
5868 }
5870 {
5877 dr_explicit_realign,
5895 }
5901 }
5909 /* 3. Handle explicit realignment if necessary/supported. Create in
5910 loop: vec_dest = realign_load (msq, lsq, realignment_token) */
5913 {
5919 realignment_token);
5926 {
5930 }
5931 }
5933 /* 4. Handle invariant-load. */
5935 {
5939 {
5944 /* CHECKME: bitpos depends on endianess? */
5948 vec_dest =
5957 /* FIXME: use build_constructor directly. */
5961 }
5962 else
5964 }
5966 /* Collect vector loads and later create their permutation in
5967 vect_transform_strided_load (). */
5971 /* Store vector loads in the corresponding SLP_NODE. */
5974 }
5976 /* FORNOW: SLP with multiple types is unsupported. */
5981 {
5987 }
5988 else
5989 {
5992 else
5995 }
5996 }
6002 }
6005 /* Function vectorizable_live_operation.
6007 STMT computes a value that is used outside the loop. Check if
6008 it can be supported. */
6010 bool
6014 {
6015 tree operation;
6021 tree op;
6036 /* FORNOW. CHECKME. */
6043 /* FORNOW: support only if all uses are invariant. This means
6044 that the scalar operations can remain in place, unvectorized.
6045 The original last scalar value that they compute will be used. */
6048 {
6051 {
6055 }
6059 }
6061 /* No transformation is required for the cases we currently support. */
6063 }
6066 /* Function vect_is_simple_cond.
6068 Input:
6069 LOOP - the loop that is being vectorized.
6070 COND - Condition that is checked for simple use.
6072 Returns whether a COND can be vectorized. Checks whether
6073 condition operands are supportable using vec_is_simple_use. */
6075 static bool
6077 {
6079 tree def;
6089 {
6093 }
6099 {
6103 }
6109 }
6111 /* vectorizable_condition.
6113 Check if STMT is conditional modify expression that can be vectorized.
6114 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
6115 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
6116 at BSI.
6118 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6120 bool
6122 {
6131 tree new_temp;
6134 tree def;
6149 /* FORNOW: SLP not supported. */
6153 /* FORNOW: not yet supported. */
6155 {
6159 }
6161 /* Is vectorizable conditional operation? */
6177 /* We do not handle two different vector types for the condition
6178 and the values. */
6183 {
6188 }
6195 {
6200 }
6210 {
6213 }
6215 /* Transform */
6217 /* Handle def. */
6221 /* Handle cond expr. */
6222 vec_cond_lhs =
6224 vec_cond_rhs =
6229 /* Arguments are ready. Create the new vector stmt. */
6241 }
6244 /* Function vect_transform_stmt.
6246 Create a vectorized stmt to replace STMT, and insert it at BSI. */
6248 static bool
6250 slp_tree slp_node)
6251 {
6255 tree orig_stmt_in_pattern;
6259 {
6302 {
6303 /* In case of interleaving, the whole chain is vectorized when the
6304 last store in the chain is reached. Store stmts before the last
6305 one are skipped, and there vec_stmt_info shouldn't be freed
6306 meanwhile. */
6310 }
6311 else
6334 {
6338 }
6339 }
6343 {
6346 }
6349 {
6353 {
6355 /* STMT was inserted by the vectorizer to replace a computation idiom.
6356 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
6357 computed this idiom. We need to record a pointer to VEC_STMT in
6358 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
6359 documentation of vect_pattern_recog. */
6361 {
6364 }
6365 }
6366 }
6369 }
6372 /* This function builds ni_name = number of iterations loop executes
6373 on the loop preheader. */
6375 static tree
6377 {
6379 edge pe;
6389 {
6392 }
6395 }
6398 /* This function generates the following statements:
6400 ni_name = number of iterations loop executes
6401 ratio = ni_name / vf
6402 ratio_mult_vf_name = ratio * vf
6404 and places them at the loop preheader edge. */
6406 static void
6411 {
6413 edge pe;
6414 basic_block new_bb;
6416 tree var;
6417 tree ratio_name;
6418 tree ratio_mult_vf_name;
6422 tree log_vf;
6426 /* Generate temporary variable that contains
6427 number of iterations loop executes. */
6432 /* Create: ratio = ni >> log2(vf) */
6436 {
6444 }
6446 /* Create: ratio_mult_vf = ratio << log2 (vf). */
6451 {
6460 }
6467 }
6470 /* Function vect_update_ivs_after_vectorizer.
6472 "Advance" the induction variables of LOOP to the value they should take
6473 after the execution of LOOP. This is currently necessary because the
6474 vectorizer does not handle induction variables that are used after the
6475 loop. Such a situation occurs when the last iterations of LOOP are
6476 peeled, because:
6477 1. We introduced new uses after LOOP for IVs that were not originally used
6478 after LOOP: the IVs of LOOP are now used by an epilog loop.
6479 2. LOOP is going to be vectorized; this means that it will iterate N/VF
6480 times, whereas the loop IVs should be bumped N times.
6482 Input:
6483 - LOOP - a loop that is going to be vectorized. The last few iterations
6484 of LOOP were peeled.
6485 - NITERS - the number of iterations that LOOP executes (before it is
6486 vectorized). i.e, the number of times the ivs should be bumped.
6487 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
6488 coming out from LOOP on which there are uses of the LOOP ivs
6489 (this is the path from LOOP->exit to epilog_loop->preheader).
6491 The new definitions of the ivs are placed in LOOP->exit.
6492 The phi args associated with the edge UPDATE_E in the bb
6493 UPDATE_E->dest are updated accordingly.
6495 Assumption 1: Like the rest of the vectorizer, this function assumes
6496 a single loop exit that has a single predecessor.
6498 Assumption 2: The phi nodes in the LOOP header and in update_bb are
6499 organized in the same order.
6501 Assumption 3: The access function of the ivs is simple enough (see
6502 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
6504 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
6505 coming out of LOOP on which the ivs of LOOP are used (this is the path
6506 that leads to the epilog loop; other paths skip the epilog loop). This
6507 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
6508 needs to have its phis updated.
6509 */
6511 static void
6513 edge update_e)
6514 {
6520 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
6522 /* Make sure there exists a single-predecessor exit bb: */
6528 {
6530 tree evolution_part;
6531 tree init_expr;
6532 tree step_expr;
6534 block_stmt_iterator last_bsi;
6537 {
6540 }
6542 /* Skip virtual phi's. */
6544 {
6548 }
6550 /* Skip reduction phis. */
6552 {
6556 }
6560 evolution_part =
6564 /* FORNOW: We do not support IVs whose evolution function is a polynomial
6565 of degree >= 2 or exponential. */
6574 init_expr,
6578 else
6582 niters),
6583 step_expr),
6584 init_expr);
6595 /* Fix phi expressions in the successor bb. */
6597 }
6598 }
6600 /* Return the more conservative threshold between the
6601 min_profitable_iters returned by the cost model and the user
6602 specified threshold, if provided. */
6604 static unsigned int
6607 {
6614 /* Use the cost model only if it is more conservative than user specified
6615 threshold. */
6618 && (!min_scalar_loop_bound
6626 }
6628 /* Function vect_do_peeling_for_loop_bound
6630 Peel the last iterations of the loop represented by LOOP_VINFO.
6631 The peeled iterations form a new epilog loop. Given that the loop now
6632 iterates NITERS times, the new epilog loop iterates
6633 NITERS % VECTORIZATION_FACTOR times.
6635 The original loop will later be made to iterate
6636 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
6638 static void
6640 {
6644 edge update_e;
6645 basic_block preheader;
6656 /* Generate the following variables on the preheader of original loop:
6658 ni_name = number of iteration the original loop executes
6659 ratio = ni_name / vf
6660 ratio_mult_vf_name = ratio * vf */
6666 /* If cost model check not done during versioning and
6667 peeling for alignment. */
6671 {
6674 /* Get profitability threshold for vectorized loop. */
6678 min_profitable_iters);
6679 }
6686 #ifdef ENABLE_CHECKING
6688 #endif
6690 /* A guard that controls whether the new_loop is to be executed or skipped
6691 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
6692 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
6693 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
6694 is on the path where the LOOP IVs are used and need to be updated. */
6699 else
6702 /* Update IVs of original loop as if they were advanced
6703 by ratio_mult_vf_name steps. */
6706 /* After peeling we have to reset scalar evolution analyzer. */
6710 }
6713 /* Function vect_gen_niters_for_prolog_loop
6715 Set the number of iterations for the loop represented by LOOP_VINFO
6716 to the minimum between LOOP_NITERS (the original iteration count of the loop)
6717 and the misalignment of DR - the data reference recorded in
6718 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
6719 this loop, the data reference DR will refer to an aligned location.
6721 The following computation is generated:
6723 If the misalignment of DR is known at compile time:
6724 addr_mis = int mis = DR_MISALIGNMENT (dr);
6725 Else, compute address misalignment in bytes:
6726 addr_mis = addr & (vectype_size - 1)
6728 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
6730 (elem_size = element type size; an element is the scalar element whose type
6731 is the inner type of the vectype)
6733 When the step of the data-ref in the loop is not 1 (as in interleaved data
6734 and SLP), the number of iterations of the prolog must be divided by the step
6735 (which is equal to the size of interleaved group).
6737 The above formulas assume that VF == number of elements in the vector. This
6738 may not hold when there are multiple-types in the loop.
6739 In this case, for some data-references in the loop the VF does not represent
6740 the number of elements that fit in the vector. Therefore, instead of VF we
6741 use TYPE_VECTOR_SUBPARTS. */
6743 static tree
6745 {
6750 edge pe;
6751 basic_block new_bb;
6767 {
6776 }
6777 else
6778 {
6786 tree elem_size_log =
6790 tree byte_misalign;
6791 tree elem_misalign;
6796 /* Create: byte_misalign = addr & (vectype_size - 1) */
6797 byte_misalign =
6800 /* Create: elem_misalign = byte_misalign / element_size */
6801 elem_misalign =
6804 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
6808 }
6810 /* Create: prolog_loop_niters = min (iters, loop_niters) */
6811 /* If the loop bound is known at compile time we already verified that it is
6812 greater than vf; since the misalignment ('iters') is at most vf, there's
6813 no need to generate the MIN_EXPR in this case. */
6818 {
6821 }
6827 /* Insert stmt on loop preheader edge. */
6829 {
6832 }
6835 }
6838 /* Function vect_update_init_of_dr
6840 NITERS iterations were peeled from LOOP. DR represents a data reference
6841 in LOOP. This function updates the information recorded in DR to
6842 account for the fact that the first NITERS iterations had already been
6843 executed. Specifically, it updates the OFFSET field of DR. */
6845 static void
6847 {
6853 }
6856 /* Function vect_update_inits_of_drs
6858 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
6859 This function updates the information recorded for the data references in
6860 the loop to account for the fact that the first NITERS iterations had
6861 already been executed. Specifically, it updates the initial_condition of
6862 the access_function of all the data_references in the loop. */
6864 static void
6866 {
6876 }
6879 /* Function vect_do_peeling_for_alignment
6881 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
6882 'niters' is set to the misalignment of one of the data references in the
6883 loop, thereby forcing it to refer to an aligned location at the beginning
6884 of the execution of this loop. The data reference for which we are
6885 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
6887 static void
6889 {
6892 tree n_iters;
6907 /* If cost model check not done during versioning. */
6910 {
6913 /* Get profitability threshold for vectorized loop. */
6917 min_profitable_iters);
6918 }
6920 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
6921 new_loop =
6927 #ifdef ENABLE_CHECKING
6929 #endif
6931 /* Update number of times loop executes. */
6936 /* Update the init conditions of the access functions of all data refs. */
6939 /* After peeling we have to reset scalar evolution analyzer. */
6943 }
6946 /* Function vect_create_cond_for_align_checks.
6948 Create a conditional expression that represents the alignment checks for
6949 all of data references (array element references) whose alignment must be
6950 checked at runtime.
6952 Input:
6953 COND_EXPR - input conditional expression. New conditions will be chained
6954 with logical AND operation.
6955 LOOP_VINFO - two fields of the loop information are used.
6956 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
6957 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
6959 Output:
6960 COND_EXPR_STMT_LIST - statements needed to construct the conditional
6961 expression.
6962 The returned value is the conditional expression to be used in the if
6963 statement that controls which version of the loop gets executed at runtime.
6965 The algorithm makes two assumptions:
6966 1) The number of bytes "n" in a vector is a power of 2.
6967 2) An address "a" is aligned if a%n is zero and that this
6968 test can be done as a&(n-1) == 0. For example, for 16
6969 byte vectors the test is a&0xf == 0. */
6971 static void
6975 {
6981 tree mask_cst;
6983 tree psize;
6984 tree int_ptrsize_type;
6988 tree ptrsize_zero;
6989 tree part_cond_expr;
6991 /* Check that mask is one less than a power of 2, i.e., mask is
6992 all zeros followed by all ones. */
6995 /* CHECKME: what is the best integer or unsigned type to use to hold a
6996 cast from a pointer value? */
6998 int_ptrsize_type
7001 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
7002 of the first vector of the i'th data reference. */
7005 {
7007 tree addr_base;
7011 /* create: addr_tmp = (int)(address_of_first_vector) */
7027 /* The addresses are OR together. */
7030 {
7031 /* create: or_tmp = or_tmp | addr_tmp */
7042 }
7043 else
7050 /* create: and_tmp = or_tmp & mask */
7060 /* Make and_tmp the left operand of the conditional test against zero.
7061 if and_tmp has a nonzero bit then some address is unaligned. */
7068 else
7070 }
7072 /* Function vect_vfa_segment_size.
7074 Create an expression that computes the size of segment
7075 that will be accessed for a data reference. The functions takes into
7076 account that realignment loads may access one more vector.
7078 Input:
7079 DR: The data reference.
7080 VECT_FACTOR: vectorization factor.
7082 Return an expression whose value is the size of segment which will be
7083 accessed by DR. */
7085 static tree
7087 {
7092 {
7093 tree vector_size = TYPE_SIZE_UNIT
7098 }
7100 }
7102 /* Function vect_create_cond_for_alias_checks.
7104 Create a conditional expression that represents the run-time checks for
7105 overlapping of address ranges represented by a list of data references
7106 relations passed as input.
7108 Input:
7109 COND_EXPR - input conditional expression. New conditions will be chained
7110 with logical AND operation.
7111 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
7112 to be checked.
7114 Output:
7115 COND_EXPR - conditional expression.
7116 COND_EXPR_STMT_LIST - statements needed to construct the conditional
7117 expression.
7120 The returned value is the conditional expression to be used in the if
7121 statement that controls which version of the loop gets executed at runtime.
7122 */
7124 static void
7128 {
7132 tree vect_factor =
7135 ddr_p ddr;
7137 tree part_cond_expr;
7139 /* Create expression
7140 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
7141 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
7142 &&
7143 ...
7144 &&
7145 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
7146 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
7152 {
7163 {
7166 }
7172 {
7175 }
7177 addr_base_a =
7180 addr_base_b =
7188 {
7194 }
7197 part_cond_expr =
7201 addr_base_a,
7202 segment_length_a),
7203 addr_base_b),
7206 addr_base_b,
7207 segment_length_b),
7208 addr_base_a));
7213 else
7215 }
7220 }
7222 /* Function vect_loop_versioning.
7224 If the loop has data references that may or may not be aligned or/and
7225 has data reference relations whose independence was not proven then
7226 two versions of the loop need to be generated, one which is vectorized
7227 and one which isn't. A test is then generated to control which of the
7228 loops is executed. The test checks for the alignment of all of the
7229 data references that may or may not be aligned. An additional
7230 sequence of runtime tests is generated for each pairs of DDRs whose
7231 independence was not proven. The vectorized version of loop is
7232 executed only if both alias and alignment tests are passed.
7234 The test generated to check which version of loop is executed
7235 is modified to also check for profitability as indicated by the
7236 cost model initially. */
7238 static void
7240 {
7245 basic_block condition_bb;
7246 block_stmt_iterator cond_exp_bsi;
7247 basic_block merge_bb;
7248 basic_block new_exit_bb;
7252 tree gimplify_stmt_list;
7257 /* Get profitability threshold for vectorized loop. */
7261 min_profitable_iters);
7263 cond_expr =
7278 cond_expr =
7280 cond_expr =
7282 NULL_TREE);
7290 /* Loop versioning violates an assumption we try to maintain during
7291 vectorization - that the loop exit block has a single predecessor.
7292 After versioning, the exit block of both loop versions is the same
7293 basic block (i.e. it has two predecessors). Just in order to simplify
7294 following transformations in the vectorizer, we fix this situation
7295 here by adding a new (empty) block on the exit-edge of the loop,
7296 with the proper loop-exit phis to maintain loop-closed-form. */
7306 {
7308 new_exit_bb);
7312 }
7314 /* End loop-exit-fixes after versioning. */
7318 {
7321 }
7322 }
7324 /* Remove a group of stores (for SLP or interleaving), free their
7325 stmt_vec_info. */
7327 static void
7329 {
7331 tree tmp;
7332 block_stmt_iterator next_si;
7335 {
7336 /* Free the attached stmt_vec_info and remove the stmt. */
7342 }
7343 }
7346 /* Vectorize SLP instance tree in postorder. */
7348 static bool
7350 {
7351 tree stmt;
7353 block_stmt_iterator si;
7354 stmt_vec_info stmt_info;
7368 {
7371 }
7376 {
7378 /* If IS_STORE is TRUE, the vectorization of the
7379 interleaving chain was completed - free all the stores in
7380 the chain. */
7382 else
7383 /* FORNOW: SLP originates only from strided stores. */
7387 }
7389 /* FORNOW: SLP originates only from strided stores. */
7391 }
7394 static bool
7396 {
7399 slp_instance instance;
7406 {
7408 /* For each SLP instance calculate number of vector stmts to be created
7409 for the scalar stmts in each node of the SLP tree. Number of vector
7410 elements in one vector iteration is the number of scalar elements in
7411 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
7412 size. */
7415 /* Schedule the tree of INSTANCE. */
7417 vec_stmts_size);
7422 }
7425 }
7427 /* Function vect_transform_loop.
7429 The analysis phase has determined that the loop is vectorizable.
7430 Vectorize the loop - created vectorized stmts to replace the scalar
7431 stmts in the loop, and update the loop exit condition. */
7433 void
7435 {
7439 block_stmt_iterator si;
7454 /* CHECKME: we wouldn't need this if we called update_ssa once
7455 for all loops. */
7458 /* Peel the loop if there are data refs with unknown alignment.
7459 Only one data ref with unknown store is allowed. */
7464 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
7465 compile time constant), or it is a constant that doesn't divide by the
7466 vectorization factor, then an epilog loop needs to be created.
7467 We therefore duplicate the loop: the original loop will be vectorized,
7468 and will compute the first (n/VF) iterations. The second copy of the loop
7469 will remain scalar and will compute the remaining (n%VF) iterations.
7470 (VF is the vectorization factor). */
7476 else
7480 /* 1) Make sure the loop header has exactly two entries
7481 2) Make sure we have a preheader basic block. */
7487 /* FORNOW: the vectorizer supports only loops which body consist
7488 of one basic block (header + empty latch). When the vectorizer will
7489 support more involved loop forms, the order by which the BBs are
7490 traversed need to be reconsidered. */
7493 {
7495 stmt_vec_info stmt_info;
7496 tree phi;
7499 {
7501 {
7504 }
7519 {
7523 }
7524 }
7527 {
7532 {
7535 }
7539 /* vector stmts created in the outer-loop during vectorization of
7540 stmts in an inner-loop may not have a stmt_info, and do not
7541 need to be vectorized. */
7543 {
7546 }
7550 {
7553 }
7556 nunits =
7561 /* For SLP VF is set according to unrolling factor, and not to
7562 vector size, hence for SLP this print is not valid. */
7565 /* SLP. Schedule all the SLP instances when the first SLP stmt is
7566 reached. */
7568 {
7570 {
7578 /* IS_STORE is true if STMT is a store. Stores cannot be of
7579 hybrid SLP type. They are removed in
7580 vect_schedule_slp_instance and their vinfo is destroyed. */
7582 {
7585 }
7586 }
7588 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
7590 {
7593 }
7594 }
7596 /* -------- vectorize statement ------------ */
7603 {
7605 {
7606 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
7607 interleaving chain was completed - free all the stores in
7608 the chain. */
7612 }
7613 else
7614 {
7615 /* Free the attached stmt_vec_info and remove the stmt. */
7619 }
7620 }
7629 /* The memory tags and pointers in vectorized statements need to
7630 have their SSA forms updated. FIXME, why can't this be delayed
7631 until all the loops have been transformed? */
7638 }