| blob | 97366336b7bc6790a86b02f4f0e88011cf50c5f1 |
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. */
50 slp_tree);
52 static tree vect_create_data_ref_ptr
54 static tree vect_create_addr_base_for_vector_ref
59 static void vect_finish_stmt_generation
62 static void vect_create_epilog_for_reduction
66 /* Utility function dealing with loop peeling (not peeling itself). */
67 static void vect_generate_tmps_on_preheader
77 static int
79 {
83 {
101 }
102 }
105 /* Function vect_estimate_min_profitable_iters
107 Return the number of iterations required for the vector version of the
108 loop to be profitable relative to the cost of the scalar version of the
109 loop.
111 TODO: Take profile info into account before making vectorization
112 decisions, if available. */
114 int
116 {
134 slp_instance instance;
136 /* Cost model disabled. */
138 {
142 }
144 /* If the number of iterations is unknown, or the
145 peeling-for-misalignment amount is unknown, we will have to generate
146 a runtime test to test the loop count against the threshold. */
151 /* Requires loop versioning tests to handle misalignment. */
154 {
155 /* FIXME: Make cost depend on complexity of individual check. */
156 vec_outside_cost +=
161 }
164 {
165 /* FIXME: Make cost depend on complexity of individual check. */
166 vec_outside_cost +=
171 }
175 {
177 }
179 /* Count statements in scalar loop. Using this as scalar cost for a single
180 iteration for now.
182 TODO: Add outer loop support.
184 TODO: Consider assigning different costs to different scalar
185 statements. */
187 /* FORNOW. */
192 {
193 gimple_stmt_iterator si;
198 else
202 {
205 /* Skip stmts that are not vectorized inside the loop. */
212 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
213 some of the "outside" costs are generated inside the outer-loop. */
215 }
216 }
218 /* Add additional cost for the peeled instructions in prologue and epilogue
219 loop.
221 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
222 at compile-time - we assume it's vf/2 (the worst would be vf-1).
224 TODO: Build an expression that represents peel_iters for prologue and
225 epilogue to be used in a run-time test. */
228 {
234 /* If peeling for alignment is unknown, loop bound of main loop becomes
235 unknown. */
239 "epilogue peel iters set to vf/2 because "
242 /* If peeled iterations are unknown, count a taken branch and a not taken
243 branch per peeled loop. Even if scalar loop iterations are known,
244 vector iterations are not known since peeled prologue iterations are
245 not known. Hence guards remain the same. */
249 }
250 else
251 {
253 {
260 }
261 else
265 {
269 "epilogue peel iters set to vf/2 because "
272 /* If peeled iterations are known but number of scalar loop
273 iterations are unknown, count a taken branch per peeled loop. */
276 }
277 else
278 {
283 }
284 }
290 /* FORNOW: The scalar outside cost is incremented in one of the
291 following ways:
293 1. The vectorizer checks for alignment and aliasing and generates
294 a condition that allows dynamic vectorization. A cost model
295 check is ANDED with the versioning condition. Hence scalar code
296 path now has the added cost of the versioning check.
298 if (cost > th & versioning_check)
299 jmp to vector code
301 Hence run-time scalar is incremented by not-taken branch cost.
303 2. The vectorizer then checks if a prologue is required. If the
304 cost model check was not done before during versioning, it has to
305 be done before the prologue check.
307 if (cost <= th)
308 prologue = scalar_iters
309 if (prologue == 0)
310 jmp to vector code
311 else
312 execute prologue
313 if (prologue == num_iters)
314 go to exit
316 Hence the run-time scalar cost is incremented by a taken branch,
317 plus a not-taken branch, plus a taken branch cost.
319 3. The vectorizer then checks if an epilogue is required. If the
320 cost model check was not done before during prologue check, it
321 has to be done with the epilogue check.
323 if (prologue == 0)
324 jmp to vector code
325 else
326 execute prologue
327 if (prologue == num_iters)
328 go to exit
329 vector code:
330 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
331 jmp to epilogue
333 Hence the run-time scalar cost should be incremented by 2 taken
334 branches.
336 TODO: The back end may reorder the BBS's differently and reverse
337 conditions/branch directions. Change the estimates below to
338 something more reasonable. */
341 {
342 /* Cost model check occurs at versioning. */
346 else
347 {
348 /* Cost model occurs at prologue generation. */
352 /* Cost model check occurs at epilogue generation. */
353 else
355 }
356 }
358 /* Add SLP costs. */
361 {
364 }
366 /* Calculate number of iterations required to make the vector version
367 profitable, relative to the loop bodies only. The following condition
368 must hold true:
369 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
370 where
371 SIC = scalar iteration cost, VIC = vector iteration cost,
372 VOC = vector outside cost, VF = vectorization factor,
373 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
374 SOC = scalar outside cost for run time cost model check. */
377 {
380 else
381 {
391 min_profitable_iters++;
392 }
393 }
394 /* vector version will never be profitable. */
395 else
396 {
399 "is divisible by scalar iteration cost = %d by a factor "
403 }
406 {
409 vec_inside_cost);
411 vec_outside_cost);
413 scalar_single_iter_cost);
416 peel_iters_prologue);
418 peel_iters_epilogue);
420 min_profitable_iters);
421 }
423 min_profitable_iters =
426 /* Because the condition we create is:
427 if (niters <= min_profitable_iters)
428 then skip the vectorized loop. */
429 min_profitable_iters--;
433 min_profitable_iters);
436 }
439 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
440 functions. Design better to avoid maintenance issues. */
442 /* Function vect_model_reduction_cost.
444 Models cost for a reduction operation, including the vector ops
445 generated within the strip-mine loop, the initial definition before
446 the loop, and the epilogue code that must be generated. */
448 static bool
451 {
454 optab optab;
455 tree vectype;
457 tree reduction_op;
463 /* Cost of reduction op inside loop. */
469 {
482 }
486 {
488 {
491 }
493 }
503 /* Add in cost for initial definition. */
506 /* Determine cost of epilogue code.
508 We have a reduction operator that will reduce the vector in one statement.
509 Also requires scalar extract. */
512 {
515 else
516 {
518 tree bitsize =
525 /* We have a whole vector shift available. */
529 /* Final reduction via vector shifts and the reduction operator. Also
530 requires scalar extract. */
533 else
534 /* Use extracts and reduction op for final reduction. For N elements,
535 we have N extracts and N-1 reduction ops. */
537 }
538 }
548 }
551 /* Function vect_model_induction_cost.
553 Models cost for induction operations. */
555 static void
557 {
558 /* loop cost for vec_loop. */
560 /* prologue cost for vec_init and vec_step. */
567 }
570 /* Function vect_model_simple_cost.
572 Models cost for simple operations, i.e. those that only emit ncopies of a
573 single op. Right now, this does not account for multiple insns that could
574 be generated for the single vector op. We will handle that shortly. */
576 void
579 {
583 /* The SLP costs were already calculated during SLP tree build. */
589 /* FORNOW: Assuming maximum 2 args per stmts. */
591 {
594 }
600 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
603 }
606 /* Function vect_cost_strided_group_size
608 For strided load or store, return the group_size only if it is the first
609 load or store of a group, else return 1. This ensures that group size is
610 only returned once per group. */
612 static int
614 {
621 }
624 /* Function vect_model_store_cost
626 Models cost for stores. In the case of strided accesses, one access
627 has the overhead of the strided access attributed to it. */
629 void
632 {
636 /* The SLP costs were already calculated during SLP tree build. */
643 /* Strided access? */
646 /* Not a strided access. */
647 else
650 /* Is this an access in a group of stores, which provide strided access?
651 If so, add in the cost of the permutes. */
653 {
654 /* Uses a high and low interleave operation for each needed permute. */
660 group_size);
662 }
664 /* Costs of the stores. */
671 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
674 }
677 /* Function vect_model_load_cost
679 Models cost for loads. In the case of strided accesses, the last access
680 has the overhead of the strided access attributed to it. Since unaligned
681 accesses are supported for loads, we also account for the costs of the
682 access scheme chosen. */
684 void
687 {
690 gimple first_stmt;
694 /* The SLP costs were already calculated during SLP tree build. */
698 /* Strided accesses? */
701 {
704 }
705 /* Not a strided access. */
706 else
707 {
710 }
714 /* Is this an access in a group of loads providing strided access?
715 If so, add in the cost of the permutes. */
717 {
718 /* Uses an even and odd extract operations for each needed permute. */
724 group_size);
726 }
728 /* The loads themselves. */
730 {
732 {
739 }
741 {
742 /* Here, we assign an additional cost for the unaligned load. */
750 }
752 {
755 /* FIXME: If the misalignment remains fixed across the iterations of
756 the containing loop, the following cost should be added to the
757 outside costs. */
762 }
764 {
769 /* Unaligned software pipeline has a load of an address, an initial
770 load, and possibly a mask operation to "prime" the loop. However,
771 if this is an access in a group of loads, which provide strided
772 access, then the above cost should only be considered for one
773 access in the group. Inside the loop, there is a load op
774 and a realignment op. */
777 {
781 }
786 }
790 }
796 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
799 }
802 /* Function vect_get_new_vect_var.
804 Returns a name for a new variable. The current naming scheme appends the
805 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
806 the name of vectorizer generated variables, and appends that to NAME if
807 provided. */
809 static tree
811 {
813 tree new_vect_var;
816 {
828 }
831 {
835 }
836 else
839 /* Mark vector typed variable as a gimple register variable. */
844 }
847 /* Function vect_create_addr_base_for_vector_ref.
849 Create an expression that computes the address of the first memory location
850 that will be accessed for a data reference.
852 Input:
853 STMT: The statement containing the data reference.
854 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
855 OFFSET: Optional. If supplied, it is be added to the initial address.
856 LOOP: Specify relative to which loop-nest should the address be computed.
857 For example, when the dataref is in an inner-loop nested in an
858 outer-loop that is now being vectorized, LOOP can be either the
859 outer-loop, or the inner-loop. The first memory location accessed
860 by the following dataref ('in' points to short):
862 for (i=0; i<N; i++)
863 for (j=0; j<M; j++)
864 s += in[i+j]
866 is as follows:
867 if LOOP=i_loop: &in (relative to i_loop)
868 if LOOP=j_loop: &in+i*2B (relative to j_loop)
870 Output:
871 1. Return an SSA_NAME whose value is the address of the memory location of
872 the first vector of the data reference.
873 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
874 these statement(s) which define the returned SSA_NAME.
876 FORNOW: We are only handling array accesses with step 1. */
878 static tree
881 tree offset,
883 {
888 tree base_name;
889 tree data_ref_base_var;
890 tree vec_stmt;
892 tree dest;
901 {
910 }
912 /* Create data_ref_base */
917 data_ref_base_var);
920 /* Create base_offset */
929 {
938 }
940 /* base + base_offset */
946 /* addr_expr = addr_base */
958 {
961 }
963 }
966 /* Function vect_create_data_ref_ptr.
968 Create a new pointer to vector type (vp), that points to the first location
969 accessed in the loop by STMT, along with the def-use update chain to
970 appropriately advance the pointer through the loop iterations. Also set
971 aliasing information for the pointer. This vector pointer is used by the
972 callers to this function to create a memory reference expression for vector
973 load/store access.
975 Input:
976 1. STMT: a stmt that references memory. Expected to be of the form
977 GIMPLE_ASSIGN <name, data-ref> or
978 GIMPLE_ASSIGN <data-ref, name>.
979 2. AT_LOOP: the loop where the vector memref is to be created.
980 3. OFFSET (optional): an offset to be added to the initial address accessed
981 by the data-ref in STMT.
982 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
983 pointing to the initial address.
985 Output:
986 1. Declare a new ptr to vector_type, and have it point to the base of the
987 data reference (initial addressed accessed by the data reference).
988 For example, for vector of type V8HI, the following code is generated:
990 v8hi *vp;
991 vp = (v8hi *)initial_address;
993 if OFFSET is not supplied:
994 initial_address = &a[init];
995 if OFFSET is supplied:
996 initial_address = &a[init + OFFSET];
998 Return the initial_address in INITIAL_ADDRESS.
1000 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
1001 update the pointer in each iteration of the loop.
1003 Return the increment stmt that updates the pointer in PTR_INCR.
1005 3. Set INV_P to true if the access pattern of the data reference in the
1006 vectorized loop is invariant. Set it to false otherwise.
1008 4. Return the pointer. */
1010 static tree
1014 {
1015 tree base_name;
1022 tree vect_ptr_type;
1023 tree vect_ptr;
1024 tree tag;
1025 tree new_temp;
1026 gimple vec_stmt;
1028 edge pe;
1029 basic_block new_bb;
1030 tree vect_ptr_init;
1032 tree vptr;
1033 gimple_stmt_iterator incr_gsi;
1036 gimple incr;
1037 tree step;
1039 /* Check the step (evolution) of the load in LOOP, and record
1040 whether it's invariant. */
1043 else
1048 else
1051 /* Create an expression for the first address accessed by this load
1052 in LOOP. */
1056 {
1069 }
1071 /** (1) Create the new vector-pointer variable: **/
1078 /** (2) Add aliasing information to the new vector-pointer:
1079 (The points-to info (DR_PTR_INFO) may be defined later.) **/
1084 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
1085 tag must be created with tag added to its may alias list. */
1088 else
1091 /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
1092 vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
1093 def-use update cycles for the pointer: One relative to the outer-loop
1094 (LOOP), which is what steps (3) and (4) below do. The other is relative
1095 to the inner-loop (which is the inner-most loop containing the dataref),
1096 and this is done be step (5) below.
1098 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
1099 inner-most loop, and so steps (3),(4) work the same, and step (5) is
1100 redundant. Steps (3),(4) create the following:
1102 vp0 = &base_addr;
1103 LOOP: vp1 = phi(vp0,vp2)
1104 ...
1105 ...
1106 vp2 = vp1 + step
1107 goto LOOP
1109 If there is an inner-loop nested in loop, then step (5) will also be
1110 applied, and an additional update in the inner-loop will be created:
1112 vp0 = &base_addr;
1113 LOOP: vp1 = phi(vp0,vp2)
1114 ...
1115 inner: vp3 = phi(vp1,vp4)
1116 vp4 = vp3 + inner_step
1117 if () goto inner
1118 ...
1119 vp2 = vp1 + step
1120 if () goto LOOP */
1122 /** (3) Calculate the initial address the vector-pointer, and set
1123 the vector-pointer to point to it before the loop: **/
1125 /* Create: (&(base[init_val+offset]) in the loop preheader. */
1131 {
1134 }
1138 /* Create: p = (vectype *) initial_base */
1147 /** (4) Handle the updating of the vector-pointer inside the loop.
1148 This is needed when ONLY_INIT is false, and also when AT_LOOP
1149 is the inner-loop nested in LOOP (during outer-loop vectorization).
1150 **/
1153 {
1154 /* Copy the points-to information if it exists. */
1158 }
1159 else
1160 {
1161 /* The step of the vector pointer is the Vector Size. */
1163 /* One exception to the above is when the scalar step of the load in
1164 LOOP is zero. In this case the step here is also zero. */
1177 /* Copy the points-to information if it exists. */
1179 {
1182 }
1189 }
1195 /** (5) Handle the updating of the vector-pointer inside the inner-loop
1196 nested in LOOP, if exists: **/
1200 {
1209 /* Copy the points-to information if it exists. */
1211 {
1214 }
1221 }
1222 else
1224 }
1227 /* Function bump_vector_ptr
1229 Increment a pointer (to a vector type) by vector-size. If requested,
1230 i.e. if PTR-INCR is given, then also connect the new increment stmt
1231 to the existing def-use update-chain of the pointer, by modifying
1232 the PTR_INCR as illustrated below:
1234 The pointer def-use update-chain before this function:
1235 DATAREF_PTR = phi (p_0, p_2)
1236 ....
1237 PTR_INCR: p_2 = DATAREF_PTR + step
1239 The pointer def-use update-chain after this function:
1240 DATAREF_PTR = phi (p_0, p_2)
1241 ....
1242 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1243 ....
1244 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
1246 Input:
1247 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
1248 in the loop.
1249 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
1250 the loop. The increment amount across iterations is expected
1251 to be vector_size.
1252 BSI - location where the new update stmt is to be placed.
1253 STMT - the original scalar memory-access stmt that is being vectorized.
1254 BUMP - optional. The offset by which to bump the pointer. If not given,
1255 the offset is assumed to be vector_size.
1257 Output: Return NEW_DATAREF_PTR as illustrated above.
1259 */
1261 static tree
1264 {
1270 gimple incr_stmt;
1271 ssa_op_iter iter;
1272 use_operand_p use_p;
1273 tree new_dataref_ptr;
1284 /* Copy the points-to information if it exists. */
1292 /* Update the vector-pointer's cross-iteration increment. */
1294 {
1299 else
1301 }
1304 }
1307 /* Function vect_create_destination_var.
1309 Create a new temporary of type VECTYPE. */
1311 static tree
1313 {
1314 tree vec_dest;
1316 tree type;
1331 }
1334 /* Function vect_init_vector.
1336 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1337 the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1338 is not NULL. Otherwise, place the initialization at the loop preheader.
1339 Return the DEF of INIT_STMT.
1340 It will be used in the vectorization of STMT. */
1342 static tree
1345 {
1347 tree new_var;
1348 gimple init_stmt;
1349 tree vec_oprnd;
1350 edge pe;
1351 tree new_temp;
1352 basic_block new_bb;
1362 else
1363 {
1372 }
1375 {
1378 }
1382 }
1385 /* For constant and loop invariant defs of SLP_NODE this function returns
1386 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1387 OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1388 stmts. */
1390 static void
1393 {
1399 tree vec_cst;
1402 tree vector_type;
1415 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1416 created vectors. It is greater than 1 if unrolling is performed.
1418 For example, we have two scalar operands, s1 and s2 (e.g., group of
1419 strided accesses of size two), while NUNITS is four (i.e., four scalars
1420 of this type can be packed in a vector). The output vector will contain
1421 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1422 will be 2).
1424 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1425 containing the operands.
1427 For example, NUNITS is four as before, and the group size is 8
1428 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1429 {s5, s6, s7, s8}. */
1436 {
1438 {
1441 else
1446 /* Create 'vect_ = {op0,op1,...,opn}'. */
1449 number_of_places_left_in_vector--;
1452 {
1459 else
1464 NULL));
1466 }
1467 }
1468 }
1470 /* Since the vectors are created in the reverse order, we should invert
1471 them. */
1474 {
1477 }
1481 /* In case that VF is greater than the unrolling factor needed for the SLP
1482 group of stmts, NUMBER_OF_VECTORS to be created is greater than
1483 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1484 to replicate the vectors. */
1486 {
1489 }
1490 }
1493 /* Get vectorized definitions from SLP_NODE that contains corresponding
1494 vectorized def-stmts. */
1496 static void
1498 {
1499 tree vec_oprnd;
1500 gimple vec_def_stmt;
1507 i++)
1508 {
1512 }
1513 }
1516 /* Get vectorized definitions for SLP_NODE.
1517 If the scalar definitions are loop invariants or constants, collect them and
1518 call vect_get_constant_vectors() to create vector stmts.
1519 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1520 must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1521 vect_get_slp_vect_defs() to retrieve them.
1522 If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1523 the right node. This is used when the second operand must remain scalar. */
1525 static void
1528 {
1529 gimple first_stmt;
1533 /* The number of vector defs is determined by the number of vector statements
1534 in the node from which we get those statements. */
1537 else
1540 /* Allocate memory for vectorized defs. */
1543 /* SLP_NODE corresponds either to a group of stores or to a group of
1544 unary/binary operations. We don't call this function for loads. */
1546 /* The defs are already vectorized. */
1548 else
1549 /* Build vectors from scalar defs. */
1554 /* Since we don't call this function with loads, this is a group of
1555 stores. */
1562 /* The number of vector defs is determined by the number of vector statements
1563 in the node from which we get those statements. */
1566 else
1572 /* The defs are already vectorized. */
1574 else
1575 /* Build vectors from scalar defs. */
1577 }
1580 /* Function get_initial_def_for_induction
1582 Input:
1583 STMT - a stmt that performs an induction operation in the loop.
1584 IV_PHI - the initial value of the induction variable
1586 Output:
1587 Return a vector variable, initialized with the first VF values of
1588 the induction variable. E.g., for an iv with IV_PHI='X' and
1589 evolution S, for a vector of 4 units, we want to return:
1590 [X, X + S, X + 2*S, X + 3*S]. */
1592 static tree
1594 {
1599 tree vectype;
1603 basic_block new_bb;
1605 tree access_fn;
1606 tree new_var;
1607 tree new_name;
1615 tree expr;
1619 imm_use_iterator imm_iter;
1620 use_operand_p use_p;
1621 gimple exit_phi;
1622 edge latch_e;
1623 tree loop_arg;
1624 gimple_stmt_iterator si;
1635 /* Find the first insertion point in the BB. */
1640 else
1643 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
1645 {
1648 }
1649 else
1663 /* Create the vector that holds the initial_value of the induction. */
1665 {
1666 /* iv_loop is nested in the loop to be vectorized. init_expr had already
1667 been created during vectorization of previous stmts; We obtain it from
1668 the STMT_VINFO_VEC_STMT of the defining stmt. */
1671 }
1672 else
1673 {
1674 /* iv_loop is the loop to be vectorized. Create:
1675 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
1681 {
1684 }
1689 {
1690 /* Create: new_name_i = new_name + step_expr */
1702 {
1705 }
1707 }
1708 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
1711 }
1714 /* Create the vector that holds the step of the induction. */
1716 /* iv_loop is nested in the loop to be vectorized. Generate:
1717 vec_step = [S, S, S, S] */
1719 else
1720 {
1721 /* iv_loop is the loop to be vectorized. Generate:
1722 vec_step = [VF*S, VF*S, VF*S, VF*S] */
1725 }
1735 /* Create the following def-use cycle:
1736 loop prolog:
1737 vec_init = ...
1738 vec_step = ...
1739 loop:
1740 vec_iv = PHI <vec_init, vec_loop>
1741 ...
1742 STMT
1743 ...
1744 vec_loop = vec_iv + vec_step; */
1746 /* Create the induction-phi that defines the induction-operand. */
1754 /* Create the iv update inside the loop */
1762 /* Set the arguments of the phi node: */
1767 /* In case that vectorization factor (VF) is bigger than the number
1768 of elements that we can fit in a vectype (nunits), we have to generate
1769 more than one vector stmt - i.e - we need to "unroll" the
1770 vector stmt by a factor VF/nunits. For more details see documentation
1771 in vectorizable_operation. */
1774 {
1775 stmt_vec_info prev_stmt_vinfo;
1776 /* FORNOW. This restriction should be relaxed. */
1779 /* Create the vector that holds the step of the induction. */
1792 {
1793 /* vec_i = vec_prev + vec_step */
1804 }
1805 }
1808 {
1809 /* Find the loop-closed exit-phi of the induction, and record
1810 the final vector of induction results: */
1813 {
1815 {
1818 }
1819 }
1821 {
1823 /* FORNOW. Currently not supporting the case that an inner-loop induction
1824 is not used in the outer-loop (i.e. only outside the outer-loop). */
1830 {
1833 }
1834 }
1835 }
1839 {
1844 }
1848 }
1851 /* Function vect_get_vec_def_for_operand.
1853 OP is an operand in STMT. This function returns a (vector) def that will be
1854 used in the vectorized stmt for STMT.
1856 In the case that OP is an SSA_NAME which is defined in the loop, then
1857 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1859 In case OP is an invariant or constant, a new stmt that creates a vector def
1860 needs to be introduced. */
1862 static tree
1864 {
1865 tree vec_oprnd;
1866 gimple vec_stmt;
1867 gimple def_stmt;
1873 tree vec_inv;
1874 tree vec_cst;
1876 tree def;
1880 tree vector_type;
1883 {
1886 }
1891 {
1893 {
1896 }
1898 {
1901 }
1902 }
1905 {
1906 /* Case 1: operand is a constant. */
1908 {
1912 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1917 {
1919 }
1925 }
1927 /* Case 2: operand is defined outside the loop - loop invariant. */
1929 {
1933 /* Create 'vec_inv = {inv,inv,..,inv}' */
1938 {
1940 }
1942 /* FIXME: use build_constructor directly. */
1947 }
1949 /* Case 3: operand is defined inside the loop. */
1951 {
1955 /* Get the def from the vectorized stmt. */
1963 else
1966 }
1968 /* Case 4: operand is defined by a loop header phi - reduction */
1970 {
1976 /* Get the def before the loop */
1979 }
1981 /* Case 5: operand is defined by loop-header phi - induction. */
1983 {
1986 /* Get the def from the vectorized stmt. */
1992 }
1996 }
1997 }
2000 /* Function vect_get_vec_def_for_stmt_copy
2002 Return a vector-def for an operand. This function is used when the
2003 vectorized stmt to be created (by the caller to this function) is a "copy"
2004 created in case the vectorized result cannot fit in one vector, and several
2005 copies of the vector-stmt are required. In this case the vector-def is
2006 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
2007 of the stmt that defines VEC_OPRND.
2008 DT is the type of the vector def VEC_OPRND.
2010 Context:
2011 In case the vectorization factor (VF) is bigger than the number
2012 of elements that can fit in a vectype (nunits), we have to generate
2013 more than one vector stmt to vectorize the scalar stmt. This situation
2014 arises when there are multiple data-types operated upon in the loop; the
2015 smallest data-type determines the VF, and as a result, when vectorizing
2016 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
2017 vector stmt (each computing a vector of 'nunits' results, and together
2018 computing 'VF' results in each iteration). This function is called when
2019 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
2020 which VF=16 and nunits=4, so the number of copies required is 4):
2022 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
2024 S1: x = load VS1.0: vx.0 = memref0 VS1.1
2025 VS1.1: vx.1 = memref1 VS1.2
2026 VS1.2: vx.2 = memref2 VS1.3
2027 VS1.3: vx.3 = memref3
2029 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
2030 VSnew.1: vz1 = vx.1 + ... VSnew.2
2031 VSnew.2: vz2 = vx.2 + ... VSnew.3
2032 VSnew.3: vz3 = vx.3 + ...
2034 The vectorization of S1 is explained in vectorizable_load.
2035 The vectorization of S2:
2036 To create the first vector-stmt out of the 4 copies - VSnew.0 -
2037 the function 'vect_get_vec_def_for_operand' is called to
2038 get the relevant vector-def for each operand of S2. For operand x it
2039 returns the vector-def 'vx.0'.
2041 To create the remaining copies of the vector-stmt (VSnew.j), this
2042 function is called to get the relevant vector-def for each operand. It is
2043 obtained from the respective VS1.j stmt, which is recorded in the
2044 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
2046 For example, to obtain the vector-def 'vx.1' in order to create the
2047 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
2048 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
2049 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
2050 and return its def ('vx.1').
2051 Overall, to create the above sequence this function will be called 3 times:
2052 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
2053 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
2054 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
2056 static tree
2058 {
2059 gimple vec_stmt_for_operand;
2060 stmt_vec_info def_stmt_info;
2062 /* Do nothing; can reuse same def. */
2074 else
2077 }
2080 /* Get vectorized definitions for the operands to create a copy of an original
2081 stmt. See vect_get_vec_def_for_stmt_copy() for details. */
2083 static void
2087 {
2094 {
2098 }
2099 }
2102 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not NULL. */
2104 static void
2107 slp_tree slp_node)
2108 {
2111 else
2112 {
2113 tree vec_oprnd;
2120 {
2124 }
2125 }
2126 }
2129 /* Function vect_finish_stmt_generation.
2131 Insert a new stmt. */
2133 static void
2136 {
2148 {
2151 }
2153 /* Make sure gsi points to the stmt that is being vectorized. */
2157 }
2160 /* Function get_initial_def_for_reduction
2162 Input:
2163 STMT - a stmt that performs a reduction operation in the loop.
2164 INIT_VAL - the initial value of the reduction variable
2166 Output:
2167 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2168 of the reduction (used for adjusting the epilog - see below).
2169 Return a vector variable, initialized according to the operation that STMT
2170 performs. This vector will be used as the initial value of the
2171 vector of partial results.
2173 Option1 (adjust in epilog): Initialize the vector as follows:
2174 add: [0,0,...,0,0]
2175 mult: [1,1,...,1,1]
2176 min/max: [init_val,init_val,..,init_val,init_val]
2177 bit and/or: [init_val,init_val,..,init_val,init_val]
2178 and when necessary (e.g. add/mult case) let the caller know
2179 that it needs to adjust the result by init_val.
2181 Option2: Initialize the vector as follows:
2182 add: [0,0,...,0,init_val]
2183 mult: [1,1,...,1,init_val]
2184 min/max: [init_val,init_val,...,init_val]
2185 bit and/or: [init_val,init_val,...,init_val]
2186 and no adjustments are needed.
2188 For example, for the following code:
2190 s = init_val;
2191 for (i=0;i<n;i++)
2192 s = s + a[i];
2194 STMT is 's = s + a[i]', and the reduction variable is 's'.
2195 For a vector of 4 units, we want to return either [0,0,0,init_val],
2196 or [0,0,0,0] and let the caller know that it needs to adjust
2197 the result at the end by 'init_val'.
2199 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2200 initialization vector is simpler (same element in all entries).
2201 A cost model should help decide between these two schemes. */
2203 static tree
2205 {
2213 tree vecdef;
2214 tree def_for_init;
2215 tree init_def;
2218 tree vector_type;
2224 else
2230 {
2236 else
2238 /* Create a vector of zeros for init_def. */
2241 else
2258 }
2261 }
2264 /* Function vect_create_epilog_for_reduction
2266 Create code at the loop-epilog to finalize the result of a reduction
2267 computation.
2269 VECT_DEF is a vector of partial results.
2270 REDUC_CODE is the tree-code for the epilog reduction.
2271 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
2272 number of elements that we can fit in a vectype (nunits). In this case
2273 we have to generate more than one vector stmt - i.e - we need to "unroll"
2274 the vector stmt by a factor VF/nunits. For more details see documentation
2275 in vectorizable_operation.
2276 STMT is the scalar reduction stmt that is being vectorized.
2277 REDUCTION_PHI is the phi-node that carries the reduction computation.
2279 This function:
2280 1. Creates the reduction def-use cycle: sets the arguments for
2281 REDUCTION_PHI:
2282 The loop-entry argument is the vectorized initial-value of the reduction.
2283 The loop-latch argument is VECT_DEF - the vector of partial sums.
2284 2. "Reduces" the vector of partial results VECT_DEF into a single result,
2285 by applying the operation specified by REDUC_CODE if available, or by
2286 other means (whole-vector shifts or a scalar loop).
2287 The function also creates a new phi node at the loop exit to preserve
2288 loop-closed form, as illustrated below.
2290 The flow at the entry to this function:
2292 loop:
2293 vec_def = phi <null, null> # REDUCTION_PHI
2294 VECT_DEF = vector_stmt # vectorized form of STMT
2295 s_loop = scalar_stmt # (scalar) STMT
2296 loop_exit:
2297 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2298 use <s_out0>
2299 use <s_out0>
2301 The above is transformed by this function into:
2303 loop:
2304 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2305 VECT_DEF = vector_stmt # vectorized form of STMT
2306 s_loop = scalar_stmt # (scalar) STMT
2307 loop_exit:
2308 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2309 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2310 v_out2 = reduce <v_out1>
2311 s_out3 = extract_field <v_out2, 0>
2312 s_out4 = adjust_result <s_out3>
2313 use <s_out4>
2314 use <s_out4>
2315 */
2317 static void
2321 gimple reduction_phi)
2322 {
2324 stmt_vec_info prev_phi_info;
2325 tree vectype;
2329 basic_block exit_bb;
2330 tree scalar_dest;
2331 tree scalar_type;
2333 gimple_stmt_iterator exit_gsi;
2334 tree vec_dest;
2336 tree new_name;
2339 gimple exit_phi;
2342 tree adjustment_def;
2344 tree orig_name;
2345 imm_use_iterator imm_iter;
2346 use_operand_p use_p;
2349 gimple orig_stmt;
2350 gimple use_stmt;
2357 {
2360 }
2363 {
2376 }
2382 /*** 1. Create the reduction def-use cycle ***/
2384 /* For the case of reduction, vect_get_vec_def_for_operand returns
2385 the scalar def before the loop, that defines the initial value
2386 of the reduction variable. */
2393 {
2394 /* 1.1 set the loop-entry arg of the reduction-phi: */
2397 /* 1.2 set the loop-latch arg for the reduction-phi: */
2403 {
2408 }
2411 }
2413 /*** 2. Create epilog code
2414 The reduction epilog code operates across the elements of the vector
2415 of partial results computed by the vectorized loop.
2416 The reduction epilog code consists of:
2417 step 1: compute the scalar result in a vector (v_out2)
2418 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2419 step 3: adjust the scalar result (s_out3) if needed.
2421 Step 1 can be accomplished using one the following three schemes:
2422 (scheme 1) using reduc_code, if available.
2423 (scheme 2) using whole-vector shifts, if available.
2424 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2425 combined.
2427 The overall epilog code looks like this:
2429 s_out0 = phi <s_loop> # original EXIT_PHI
2430 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2431 v_out2 = reduce <v_out1> # step 1
2432 s_out3 = extract_field <v_out2, 0> # step 2
2433 s_out4 = adjust_result <s_out3> # step 3
2435 (step 3 is optional, and steps 1 and 2 may be combined).
2436 Lastly, the uses of s_out0 are replaced by s_out4.
2438 ***/
2440 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2441 v_out1 = phi <v_loop> */
2447 {
2452 else
2453 {
2456 }
2459 }
2462 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
2463 (i.e. when reduc_code is not available) and in the final adjustment
2464 code (if needed). Also get the original scalar reduction variable as
2465 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
2466 represents a reduction pattern), the tree-code and scalar-def are
2467 taken from the original stmt that the pattern-stmt (STMT) replaces.
2468 Otherwise (it is a regular reduction) - the tree-code and scalar-def
2469 are taken from STMT. */
2473 {
2474 /* Regular reduction */
2476 }
2477 else
2478 {
2479 /* Reduction pattern */
2483 }
2492 /* In case this is a reduction in an inner-loop while vectorizing an outer
2493 loop - we don't need to extract a single scalar result at the end of the
2494 inner-loop. The final vector of partial results will be used in the
2495 vectorized outer-loop, or reduced to a scalar result at the end of the
2496 outer-loop. */
2500 /* FORNOW */
2503 /* 2.3 Create the reduction code, using one of the three schemes described
2504 above. */
2507 {
2508 tree tmp;
2510 /*** Case 1: Create:
2511 v_out2 = reduc_expr <v_out1> */
2524 }
2525 else
2526 {
2532 tree vec_temp;
2536 else
2539 /* Regardless of whether we have a whole vector shift, if we're
2540 emulating the operation via tree-vect-generic, we don't want
2541 to use it. Only the first round of the reduction is likely
2542 to still be profitable via emulation. */
2543 /* ??? It might be better to emit a reduction tree code here, so that
2544 tree-vect-generic can expand the first round via bit tricks. */
2547 else
2548 {
2552 }
2555 {
2556 /*** Case 2: Create:
2557 for (offset = VS/2; offset >= element_size; offset/=2)
2558 {
2559 Create: va' = vec_shift <va, offset>
2560 Create: va = vop <va, va'>
2561 } */
2572 {
2585 }
2588 }
2589 else
2590 {
2591 tree rhs;
2593 /*** Case 3: Create:
2594 s = extract_field <v_out2, 0>
2595 for (offset = element_size;
2596 offset < vector_size;
2597 offset += element_size;)
2598 {
2599 Create: s' = extract_field <v_out2, offset>
2600 Create: s = op <s, s'>
2601 } */
2609 bitsize_zero_node);
2618 {
2621 bitpos);
2629 new_scalar_dest,
2634 }
2637 }
2638 }
2640 /* 2.4 Extract the final scalar result. Create:
2641 s_out3 = extract_field <v_out2, bitpos> */
2644 {
2645 tree rhs;
2655 else
2663 }
2665 vect_finalize_reduction:
2667 /* 2.5 Adjust the final result by the initial value of the reduction
2668 variable. (When such adjustment is not needed, then
2669 'adjustment_def' is zero). For example, if code is PLUS we create:
2670 new_temp = loop_exit_def + adjustment_def */
2673 {
2675 {
2679 }
2680 else
2681 {
2685 }
2691 }
2694 /* 2.6 Handle the loop-exit phi */
2696 /* Replace uses of s_out0 with uses of s_out3:
2697 Find the loop-closed-use at the loop exit of the original scalar result.
2698 (The reduction result is expected to have two immediate uses - one at the
2699 latch block, and one at the loop exit). */
2702 {
2704 {
2707 }
2708 }
2709 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
2713 {
2715 {
2718 /* FORNOW. Currently not supporting the case that an inner-loop
2719 reduction is not used in the outer-loop (but only outside the
2720 outer-loop). */
2732 }
2734 /* Replace the uses: */
2739 }
2741 }
2744 /* Function vectorizable_reduction.
2746 Check if STMT performs a reduction operation that can be vectorized.
2747 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2748 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2749 Return FALSE if not a vectorizable STMT, TRUE otherwise.
2751 This function also handles reduction idioms (patterns) that have been
2752 recognized in advance during vect_pattern_recog. In this case, STMT may be
2753 of this form:
2754 X = pattern_expr (arg0, arg1, ..., X)
2755 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2756 sequence that had been detected and replaced by the pattern-stmt (STMT).
2758 In some cases of reduction patterns, the type of the reduction variable X is
2759 different than the type of the other arguments of STMT.
2760 In such cases, the vectype that is used when transforming STMT into a vector
2761 stmt is different than the vectype that is used to determine the
2762 vectorization factor, because it consists of a different number of elements
2763 than the actual number of elements that are being operated upon in parallel.
2765 For example, consider an accumulation of shorts into an int accumulator.
2766 On some targets it's possible to vectorize this pattern operating on 8
2767 shorts at a time (hence, the vectype for purposes of determining the
2768 vectorization factor should be V8HI); on the other hand, the vectype that
2769 is used to create the vector form is actually V4SI (the type of the result).
2771 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2772 indicates what is the actual level of parallelism (V8HI in the example), so
2773 that the right vectorization factor would be derived. This vectype
2774 corresponds to the type of arguments to the reduction stmt, and should *NOT*
2775 be used to create the vectorized stmt. The right vectype for the vectorized
2776 stmt is obtained from the type of the result X:
2777 get_vectype_for_scalar_type (TREE_TYPE (X))
2779 This means that, contrary to "regular" reductions (or "regular" stmts in
2780 general), the following equation:
2781 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2782 does *NOT* necessarily hold for reduction patterns. */
2784 bool
2787 {
2788 tree vec_dest;
2789 tree scalar_dest;
2800 tree def;
2801 gimple def_stmt;
2804 tree scalar_type;
2806 gimple orig_stmt;
2807 stmt_vec_info orig_stmt_info;
2816 tree reduc_def;
2826 /* FORNOW: SLP not supported. */
2830 /* 1. Is vectorizable reduction? */
2832 /* Not supportable if the reduction variable is used in the loop. */
2836 /* Reductions that are not used even in an enclosing outer-loop,
2837 are expected to be "live" (used out of the loop). */
2842 /* Make sure it was already recognized as a reduction computation. */
2846 /* 2. Has this been recognized as a reduction pattern?
2848 Check if STMT represents a pattern that has been recognized
2849 in earlier analysis stages. For stmts that represent a pattern,
2850 the STMT_VINFO_RELATED_STMT field records the last stmt in
2851 the original sequence that constitutes the pattern. */
2855 {
2860 }
2862 /* 3. Check the operands of the operation. The first operands are defined
2863 inside the loop body. The last operand is the reduction variable,
2864 which is defined by the loop-header-phi. */
2868 /* Flatten RHS */
2870 {
2874 {
2880 }
2881 else
2898 }
2906 /* All uses but the last are expected to be defined in the loop.
2907 The last use is the reduction variable. */
2909 {
2918 }
2926 else
2932 /* 4. Supportable by target? */
2934 /* 4.1. check support for the operation in the loop */
2937 {
2941 }
2944 {
2953 }
2955 /* Worthwhile without SIMD support? */
2959 {
2963 }
2965 /* 4.2. Check support for the epilog operation.
2967 If STMT represents a reduction pattern, then the type of the
2968 reduction variable may be different than the type of the rest
2969 of the arguments. For example, consider the case of accumulation
2970 of shorts into an int accumulator; The original code:
2971 S1: int_a = (int) short_a;
2972 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
2974 was replaced with:
2975 STMT: int_acc = widen_sum <short_a, int_acc>
2977 This means that:
2978 1. The tree-code that is used to create the vector operation in the
2979 epilog code (that reduces the partial results) is not the
2980 tree-code of STMT, but is rather the tree-code of the original
2981 stmt from the pattern that STMT is replacing. I.e, in the example
2982 above we want to use 'widen_sum' in the loop, but 'plus' in the
2983 epilog.
2984 2. The type (mode) we use to check available target support
2985 for the vector operation to be created in the *epilog*, is
2986 determined by the type of the reduction variable (in the example
2987 above we'd check this: plus_optab[vect_int_mode]).
2988 However the type (mode) we use to check available target support
2989 for the vector operation to be created *inside the loop*, is
2990 determined by the type of the other arguments to STMT (in the
2991 example we'd check this: widen_sum_optab[vect_short_mode]).
2993 This is contrary to "regular" reductions, in which the types of all
2994 the arguments are the same as the type of the reduction variable.
2995 For "regular" reductions we can therefore use the same vector type
2996 (and also the same tree-code) when generating the epilog code and
2997 when generating the code inside the loop. */
3000 {
3001 /* This is a reduction pattern: get the vectype from the type of the
3002 reduction variable, and get the tree-code from orig_stmt. */
3006 {
3008 {
3011 }
3013 }
3016 }
3017 else
3018 {
3019 /* Regular reduction: use the same vectype and tree-code as used for
3020 the vector code inside the loop can be used for the epilog code. */
3022 }
3028 {
3032 }
3034 {
3038 }
3041 {
3046 }
3048 /** Transform. **/
3053 /* Create the destination vector */
3056 /* In case the vectorization factor (VF) is bigger than the number
3057 of elements that we can fit in a vectype (nunits), we have to generate
3058 more than one vector stmt - i.e - we need to "unroll" the
3059 vector stmt by a factor VF/nunits. For more details see documentation
3060 in vectorizable_operation. */
3062 /* If the reduction is used in an outer loop we need to generate
3063 VF intermediate results, like so (e.g. for ncopies=2):
3064 r0 = phi (init, r0)
3065 r1 = phi (init, r1)
3066 r0 = x0 + r0;
3067 r1 = x1 + r1;
3068 (i.e. we generate VF results in 2 registers).
3069 In this case we have a separate def-use cycle for each copy, and therefore
3070 for each copy we get the vector def for the reduction variable from the
3071 respective phi node created for this copy.
3073 Otherwise (the reduction is unused in the loop nest), we can combine
3074 together intermediate results, like so (e.g. for ncopies=2):
3075 r = phi (init, r)
3076 r = x0 + r;
3077 r = x1 + r;
3078 (i.e. we generate VF/2 results in a single register).
3079 In this case for each copy we get the vector def for the reduction variable
3080 from the vectorized reduction operation generated in the previous iteration.
3081 */
3084 {
3087 }
3088 else
3094 {
3096 {
3097 /* Create the reduction-phi that defines the reduction-operand. */
3100 }
3102 /* Handle uses. */
3104 {
3107 {
3109 }
3111 /* Get the vector def for the reduction variable from the phi node */
3114 }
3115 else
3116 {
3124 else
3128 }
3130 /* Arguments are ready. create the new vector stmt. */
3133 else
3135 reduc_def);
3143 else
3147 }
3149 /* Finalize the reduction-phi (set its arguments) and create the
3150 epilog reduction code. */
3156 }
3158 /* Checks if CALL can be vectorized in type VECTYPE. Returns
3159 a function declaration if the target has a vectorized version
3160 of the function, or NULL_TREE if the function cannot be vectorized. */
3162 tree
3164 {
3168 /* We only handle functions that do not read or clobber memory -- i.e.
3169 const or novops ones. */
3180 vectype_in);
3181 }
3183 /* Function vectorizable_call.
3185 Check if STMT performs a function call that can be vectorized.
3186 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3187 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3188 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3190 bool
3192 {
3193 tree vec_dest;
3194 tree scalar_dest;
3203 gimple def_stmt;
3205 gimple new_stmt;
3217 /* FORNOW: SLP not supported. */
3221 /* Is STMT a vectorizable call? */
3228 /* Process function arguments. */
3232 /* Bail out if the function has more than two arguments, we
3233 do not have interesting builtin functions to vectorize with
3234 more than two arguments. No arguments is also not good. */
3239 {
3242 /* We can only handle calls with arguments of the same type. */
3245 {
3249 }
3253 {
3257 }
3258 }
3271 /* FORNOW */
3278 else
3281 /* For now, we only vectorize functions if a target specific builtin
3282 is available. TODO -- in some cases, it might be profitable to
3283 insert the calls for pieces of the vector, in order to be able
3284 to vectorize other operations in the loop. */
3287 {
3292 }
3298 else
3301 /* Sanity check: make sure that at least one copy of the vectorized stmt
3302 needs to be generated. */
3306 {
3312 }
3314 /** Transform. **/
3319 /* Handle def. */
3325 {
3328 {
3329 /* Build argument list for the vectorized call. */
3332 else
3336 {
3339 vec_oprnd0
3341 else
3342 vec_oprnd0
3346 }
3356 else
3360 }
3366 {
3367 /* Build argument list for the vectorized call. */
3370 else
3374 {
3377 {
3378 vec_oprnd0
3380 vec_oprnd1
3382 }
3383 else
3384 {
3385 vec_oprnd0
3387 vec_oprnd1
3389 }
3393 }
3403 else
3407 }
3414 /* No current target implements this case. */
3416 }
3420 /* The call in STMT might prevent it from being removed in dce.
3421 We however cannot remove it here, due to the way the ssa name
3422 it defines is mapped to the new definition. So just replace
3423 rhs of the statement with something harmless. */
3435 }
3438 /* Function vect_gen_widened_results_half
3440 Create a vector stmt whose code, type, number of arguments, and result
3441 variable are CODE, OP_TYPE, and VEC_DEST, and its arguments are
3442 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
3443 In the case that CODE is a CALL_EXPR, this means that a call to DECL
3444 needs to be created (DECL is a function-decl of a target-builtin).
3445 STMT is the original scalar stmt that we are vectorizing. */
3447 static gimple
3449 tree decl,
3452 gimple stmt)
3453 {
3454 gimple new_stmt;
3455 tree new_temp;
3456 tree sym;
3457 ssa_op_iter iter;
3459 /* Generate half of the widened result: */
3461 {
3462 /* Target specific support */
3465 else
3469 }
3470 else
3471 {
3472 /* Generic support */
3477 vec_oprnd1);
3480 }
3484 {
3486 {
3490 }
3491 }
3494 }
3497 /* Check if STMT performs a conversion operation, that can be vectorized.
3498 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3499 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3500 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3502 bool
3505 {
3506 tree vec_dest;
3507 tree scalar_dest;
3508 tree op0;
3514 tree new_temp;
3515 tree def;
3516 gimple def_stmt;
3519 stmt_vec_info prev_stmt_info;
3524 tree expr;
3526 tree builtin_decl;
3530 tree vop0;
3531 tree integral_type;
3535 /* Is STMT a vectorizable conversion? */
3553 /* Check types of lhs and rhs. */
3568 /* FORNOW */
3575 else
3581 /* Bail out if the types are both integral or non-integral. */
3590 else
3593 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3594 this, so we can safely override NCOPIES with 1 here. */
3598 /* Sanity check: make sure that at least one copy of the vectorized stmt
3599 needs to be generated. */
3602 /* Check the operands of the operation. */
3604 {
3608 }
3610 /* Supportable by target? */
3621 {
3625 }
3628 {
3630 /* FORNOW: SLP not supported. */
3633 }
3636 {
3639 }
3641 /** Transform. **/
3645 /* Handle def. */
3653 {
3656 {
3657 tree sym;
3658 ssa_op_iter iter;
3662 else
3665 builtin_decl =
3668 {
3669 /* Arguments are ready. create the new vector stmt. */
3675 SSA_OP_ALL_VIRTUALS)
3676 {
3680 }
3683 }
3687 else
3690 }
3694 /* In case the vectorization factor (VF) is bigger than the number
3695 of elements that we can fit in a vectype (nunits), we have to
3696 generate more than one vector stmt - i.e - we need to "unroll"
3697 the vector stmt by a factor VF/nunits. */
3699 {
3702 else
3707 /* Generate first half of the widened result: */
3708 new_stmt
3714 else
3718 /* Generate second half of the widened result: */
3719 new_stmt
3725 }
3729 /* In case the vectorization factor (VF) is bigger than the number
3730 of elements that we can fit in a vectype (nunits), we have to
3731 generate more than one vector stmt - i.e - we need to "unroll"
3732 the vector stmt by a factor VF/nunits. */
3734 {
3735 /* Handle uses. */
3737 {
3740 }
3741 else
3742 {
3745 }
3747 /* Arguments are ready. Create the new vector stmt. */
3750 vec_oprnd1);
3757 else
3761 }
3764 }
3770 }
3773 /* Function vectorizable_assignment.
3775 Check if STMT performs an assignment (copy) that can be vectorized.
3776 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3777 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3778 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3780 bool
3783 {
3784 tree vec_dest;
3785 tree scalar_dest;
3786 tree op;
3790 tree new_temp;
3791 tree def;
3792 gimple def_stmt;
3798 tree vop;
3800 /* Multiple types in SLP are handled by creating the appropriate number of
3801 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
3802 case of SLP. */
3805 else
3818 /* Is vectorizable assignment? */
3829 else
3833 {
3837 }
3840 {
3846 }
3848 /** Transform. **/
3852 /* Handle def. */
3855 /* Handle use. */
3858 /* Arguments are ready. create the new vector stmt. */
3860 {
3869 }
3873 }
3876 /* Function vect_min_worthwhile_factor.
3878 For a loop where we could vectorize the operation indicated by CODE,
3879 return the minimum vectorization factor that makes it worthwhile
3880 to use generic vectors. */
3881 static int
3883 {
3885 {
3899 }
3900 }
3903 /* Function vectorizable_induction
3905 Check if PHI performs an induction computation that can be vectorized.
3906 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3907 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3908 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3910 bool
3913 {
3920 tree vec_def;
3923 /* FORNOW. This restriction should be relaxed. */
3925 {
3929 }
3934 /* FORNOW: SLP not supported. */
3944 {
3950 }
3952 /** Transform. **/
3960 }
3963 /* Function vectorizable_operation.
3965 Check if STMT performs a binary or unary operation that can be vectorized.
3966 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3967 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3968 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3970 bool
3973 {
3974 tree vec_dest;
3975 tree scalar_dest;
3983 tree new_temp;
3985 optab optab;
3988 tree def;
3989 gimple def_stmt;
3992 stmt_vec_info prev_stmt_info;
3995 tree vectype_out;
4004 /* Multiple types in SLP are handled by creating the appropriate number of
4005 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4006 case of SLP. */
4009 else
4020 /* Is STMT a vectorizable binary/unary operation? */
4037 /* For pointer addition, we should use the normal plus for
4038 the vector addition. */
4042 /* Support only unary or binary operations. */
4045 {
4049 }
4053 {
4057 }
4060 {
4063 {
4067 }
4068 }
4070 /* If this is a shift/rotate, determine whether the shift amount is a vector,
4071 or scalar. If the shift/rotate amount is a vector, use the vector/vector
4072 shift optabs. */
4075 {
4078 /* vector shifted by vector */
4080 {
4084 }
4086 /* See if the machine has a vector shifted by scalar insn and if not
4087 then see if it has a vector shifted by vector insn */
4089 {
4094 {
4098 }
4099 else
4100 {
4103 && optab
4107 }
4108 }
4110 else
4111 {
4115 }
4116 }
4117 else
4120 /* Supportable by target? */
4122 {
4126 }
4130 {
4133 /* Check only during analysis. */
4141 }
4143 /* Worthwhile without SIMD support? Check only during analysis. */
4148 {
4152 }
4155 {
4161 }
4163 /** Transform. **/
4168 /* Handle def. */
4171 /* Allocate VECs for vector operands. In case of SLP, vector operands are
4172 created in the previous stages of the recursion, so no allocation is
4173 needed, except for the case of shift with scalar shift argument. In that
4174 case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
4175 be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
4176 In case of loop-based vectorization we allocate VECs of size 1. We
4177 allocate VEC_OPRNDS1 only in case of binary operation. */
4179 {
4183 }
4187 /* In case the vectorization factor (VF) is bigger than the number
4188 of elements that we can fit in a vectype (nunits), we have to generate
4189 more than one vector stmt - i.e - we need to "unroll" the
4190 vector stmt by a factor VF/nunits. In doing so, we record a pointer
4191 from one copy of the vector stmt to the next, in the field
4192 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
4193 stages to find the correct vector defs to be used when vectorizing
4194 stmts that use the defs of the current stmt. The example below illustrates
4195 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
4196 4 vectorized stmts):
4198 before vectorization:
4199 RELATED_STMT VEC_STMT
4200 S1: x = memref - -
4201 S2: z = x + 1 - -
4203 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
4204 there):
4205 RELATED_STMT VEC_STMT
4206 VS1_0: vx0 = memref0 VS1_1 -
4207 VS1_1: vx1 = memref1 VS1_2 -
4208 VS1_2: vx2 = memref2 VS1_3 -
4209 VS1_3: vx3 = memref3 - -
4210 S1: x = load - VS1_0
4211 S2: z = x + 1 - -
4213 step2: vectorize stmt S2 (done here):
4214 To vectorize stmt S2 we first need to find the relevant vector
4215 def for the first operand 'x'. This is, as usual, obtained from
4216 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
4217 that defines 'x' (S1). This way we find the stmt VS1_0, and the
4218 relevant vector def 'vx0'. Having found 'vx0' we can generate
4219 the vector stmt VS2_0, and as usual, record it in the
4220 STMT_VINFO_VEC_STMT of stmt S2.
4221 When creating the second copy (VS2_1), we obtain the relevant vector
4222 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
4223 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
4224 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
4225 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
4226 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
4227 chain of stmts and pointers:
4228 RELATED_STMT VEC_STMT
4229 VS1_0: vx0 = memref0 VS1_1 -
4230 VS1_1: vx1 = memref1 VS1_2 -
4231 VS1_2: vx2 = memref2 VS1_3 -
4232 VS1_3: vx3 = memref3 - -
4233 S1: x = load - VS1_0
4234 VS2_0: vz0 = vx0 + v1 VS2_1 -
4235 VS2_1: vz1 = vx1 + v1 VS2_2 -
4236 VS2_2: vz2 = vx2 + v1 VS2_3 -
4237 VS2_3: vz3 = vx3 + v1 - -
4238 S2: z = x + 1 - VS2_0 */
4242 {
4243 /* Handle uses. */
4245 {
4247 {
4248 /* Vector shl and shr insn patterns can be defined with scalar
4249 operand 2 (shift operand). In this case, use constant or loop
4250 invariant op1 directly, without extending it to vector mode
4251 first. */
4254 {
4260 {
4261 /* Store vec_oprnd1 for every vector stmt to be created
4262 for SLP_NODE. We check during the analysis that all the
4263 shift arguments are the same.
4264 TODO: Allow different constants for different vector
4265 stmts generated for an SLP instance. */
4268 }
4269 }
4270 }
4272 /* vec_oprnd1 is available if operand 1 should be of a scalar-type
4273 (a special case for certain kind of vector shifts); otherwise,
4274 operand 1 should be of a vector type (the usual case). */
4277 slp_node);
4278 else
4280 slp_node);
4281 }
4282 else
4285 /* Arguments are ready. Create the new vector stmt. */
4287 {
4296 }
4303 else
4306 }
4313 }
4316 /* Get vectorized definitions for loop-based vectorization. For the first
4317 operand we call vect_get_vec_def_for_operand() (with OPRND containing
4318 scalar operand), and for the rest we get a copy with
4319 vect_get_vec_def_for_stmt_copy() using the previous vector definition
4320 (stored in OPRND). See vect_get_vec_def_for_stmt_copy() for details.
4321 The vectors are collected into VEC_OPRNDS. */
4323 static void
4326 {
4327 tree vec_oprnd;
4329 /* Get first vector operand. */
4330 /* All the vector operands except the very first one (that is scalar oprnd)
4331 are stmt copies. */
4334 else
4339 /* Get second vector operand. */
4345 /* For conversion in multiple steps, continue to get operands
4346 recursively. */
4349 }
4352 /* Create vectorized demotion statements for vector operands from VEC_OPRNDS.
4353 For multi-step conversions store the resulting vectors and call the function
4354 recursively. */
4356 static void
4363 {
4366 gimple new_stmt;
4372 {
4373 /* Create demotion operation. */
4382 /* Store the resulting vector for next recursive call. */
4384 else
4385 {
4386 /* This is the last step of the conversion sequence. Store the
4387 vectors in SLP_NODE or in vector info of the scalar statement
4388 (or in STMT_VINFO_RELATED_STMT chain). */
4391 else
4392 {
4395 else
4399 }
4400 }
4401 }
4403 /* For multi-step demotion operations we first generate demotion operations
4404 from the source type to the intermediate types, and then combine the
4405 results (stored in VEC_OPRNDS) in demotion operation to the destination
4406 type. */
4408 {
4409 /* At each level of recursion we have have of the operands we had at the
4410 previous level. */
4415 }
4416 }
4419 /* Function vectorizable_type_demotion
4421 Check if STMT performs a binary or unary operation that involves
4422 type demotion, and if it can be vectorized.
4423 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4424 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4425 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4427 bool
4430 {
4431 tree vec_dest;
4432 tree scalar_dest;
4433 tree op0;
4437 tree def;
4438 gimple def_stmt;
4440 stmt_vec_info prev_stmt_info;
4443 tree vectype_out;
4446 tree vectype_in;
4458 /* Is STMT a vectorizable type-demotion operation? */
4483 /* Multiple types in SLP are handled by creating the appropriate number of
4484 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4485 case of SLP. */
4488 else
4500 /* Check the operands of the operation. */
4502 {
4506 }
4508 /* Supportable by target? */
4516 {
4522 }
4524 /** Transform. **/
4527 ncopies);
4529 /* In case of multi-step demotion, we first generate demotion operations to
4530 the intermediate types, and then from that types to the final one.
4531 We create vector destinations for the intermediate type (TYPES) received
4532 from supportable_narrowing_operation, and store them in the correct order
4533 for future use in vect_create_vectorized_demotion_stmts(). */
4536 else
4543 {
4546 {
4548 intermediate_type);
4550 }
4551 }
4553 /* In case the vectorization factor (VF) is bigger than the number
4554 of elements that we can fit in a vectype (nunits), we have to generate
4555 more than one vector stmt - i.e - we need to "unroll" the
4556 vector stmt by a factor VF/nunits. */
4560 {
4561 /* Handle uses. */
4564 else
4565 {
4571 }
4573 /* Arguments are ready. Create the new vector stmts. */
4579 }
4588 }
4591 /* Create vectorized promotion statements for vector operands from VEC_OPRNDS0
4592 and VEC_OPRNDS1 (for binary operations). For multi-step conversions store
4593 the resulting vectors and call the function recursively. */
4595 static void
4605 {
4616 {
4619 else
4622 /* Generate the two halves of promotion operation. */
4628 {
4631 }
4632 else
4633 {
4636 }
4639 {
4640 /* Store the results for the recursive call. */
4643 }
4644 else
4645 {
4646 /* Last step of promotion sequience - store the results. */
4648 {
4651 }
4652 else
4653 {
4656 else
4662 }
4663 }
4664 }
4667 {
4668 /* For multi-step promotion operation we first generate we call the
4669 function recurcively for every stage. We start from the input type,
4670 create promotion operations to the intermediate types, and then
4671 create promotions to the output type. */
4678 prev_stmt_info);
4679 }
4680 }
4683 /* Function vectorizable_type_promotion
4685 Check if STMT performs a binary or unary operation that involves
4686 type promotion, and if it can be vectorized.
4687 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4688 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4689 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4691 bool
4694 {
4695 tree vec_dest;
4696 tree scalar_dest;
4704 tree def;
4705 gimple def_stmt;
4707 stmt_vec_info prev_stmt_info;
4710 tree vectype_out;
4713 tree vectype_in;
4725 /* Is STMT a vectorizable type-promotion operation? */
4751 /* Multiple types in SLP are handled by creating the appropriate number of
4752 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
4753 case of SLP. */
4756 else
4768 /* Check the operands of the operation. */
4770 {
4774 }
4778 {
4781 {
4785 }
4786 }
4788 /* Supportable by target? */
4794 /* Binary widening operation can only be supported directly by the
4795 architecture. */
4801 {
4807 }
4809 /** Transform. **/
4813 ncopies);
4815 /* Handle def. */
4816 /* In case of multi-step promotion, we first generate promotion operations
4817 to the intermediate types, and then from that types to the final one.
4818 We store vector destination in VEC_DSTS in the correct order for
4819 recursive creation of promotion operations in
4820 vect_create_vectorized_promotion_stmts(). Vector destinations are created
4821 according to TYPES recieved from supportable_widening_operation(). */
4824 else
4831 {
4834 {
4836 intermediate_type);
4838 }
4839 }
4842 {
4847 }
4849 /* In case the vectorization factor (VF) is bigger than the number
4850 of elements that we can fit in a vectype (nunits), we have to generate
4851 more than one vector stmt - i.e - we need to "unroll" the
4852 vector stmt by a factor VF/nunits. */
4856 {
4857 /* Handle uses. */
4859 {
4862 else
4863 {
4867 {
4870 }
4871 }
4872 }
4873 else
4874 {
4878 {
4881 }
4882 }
4884 /* Arguments are ready. Create the new vector stmts. */
4888 tmp_vec_dsts,
4892 }
4902 }
4905 /* Function vect_strided_store_supported.
4907 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
4908 and FALSE otherwise. */
4910 static bool
4912 {
4918 /* Check that the operation is supported. */
4924 {
4928 }
4931 == CODE_FOR_nothing
4934 {
4938 }
4941 }
4944 /* Function vect_permute_store_chain.
4946 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4947 a power of 2, generate interleave_high/low stmts to reorder the data
4948 correctly for the stores. Return the final references for stores in
4949 RESULT_CHAIN.
4951 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4952 The input is 4 vectors each containing 8 elements. We assign a number to each
4953 element, the input sequence is:
4955 1st vec: 0 1 2 3 4 5 6 7
4956 2nd vec: 8 9 10 11 12 13 14 15
4957 3rd vec: 16 17 18 19 20 21 22 23
4958 4th vec: 24 25 26 27 28 29 30 31
4960 The output sequence should be:
4962 1st vec: 0 8 16 24 1 9 17 25
4963 2nd vec: 2 10 18 26 3 11 19 27
4964 3rd vec: 4 12 20 28 5 13 21 30
4965 4th vec: 6 14 22 30 7 15 23 31
4967 i.e., we interleave the contents of the four vectors in their order.
4969 We use interleave_high/low instructions to create such output. The input of
4970 each interleave_high/low operation is two vectors:
4971 1st vec 2nd vec
4972 0 1 2 3 4 5 6 7
4973 the even elements of the result vector are obtained left-to-right from the
4974 high/low elements of the first vector. The odd elements of the result are
4975 obtained left-to-right from the high/low elements of the second vector.
4976 The output of interleave_high will be: 0 4 1 5
4977 and of interleave_low: 2 6 3 7
4980 The permutation is done in log LENGTH stages. In each stage interleave_high
4981 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4982 where the first argument is taken from the first half of DR_CHAIN and the
4983 second argument from it's second half.
4984 In our example,
4986 I1: interleave_high (1st vec, 3rd vec)
4987 I2: interleave_low (1st vec, 3rd vec)
4988 I3: interleave_high (2nd vec, 4th vec)
4989 I4: interleave_low (2nd vec, 4th vec)
4991 The output for the first stage is:
4993 I1: 0 16 1 17 2 18 3 19
4994 I2: 4 20 5 21 6 22 7 23
4995 I3: 8 24 9 25 10 26 11 27
4996 I4: 12 28 13 29 14 30 15 31
4998 The output of the second stage, i.e. the final result is:
5000 I1: 0 8 16 24 1 9 17 25
5001 I2: 2 10 18 26 3 11 19 27
5002 I3: 4 12 20 28 5 13 21 30
5003 I4: 6 14 22 30 7 15 23 31. */
5005 static bool
5008 gimple stmt,
5011 {
5013 gimple perm_stmt;
5015 tree scalar_dest;
5022 /* Check that the operation is supported. */
5029 {
5031 {
5035 /* Create interleaving stmt:
5036 in the case of big endian:
5037 high = interleave_high (vect1, vect2)
5038 and in the case of little endian:
5039 high = interleave_low (vect1, vect2). */
5044 {
5047 }
5048 else
5049 {
5052 }
5060 /* Create interleaving stmt:
5061 in the case of big endian:
5062 low = interleave_low (vect1, vect2)
5063 and in the case of little endian:
5064 low = interleave_high (vect1, vect2). */
5074 }
5076 }
5078 }
5081 /* Function vectorizable_store.
5083 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
5084 can be vectorized.
5085 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5086 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5087 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5089 bool
5091 slp_tree slp_node)
5092 {
5093 tree scalar_dest;
5094 tree data_ref;
5095 tree op;
5103 tree dummy;
5105 tree def;
5106 gimple def_stmt;
5120 stmt_vec_info first_stmt_vinfo;
5123 /* Multiple types in SLP are handled by creating the appropriate number of
5124 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
5125 case of SLP. */
5128 else
5133 /* FORNOW. This restriction should be relaxed. */
5135 {
5139 }
5147 /* Is vectorizable store? */
5161 {
5165 }
5167 /* If accesses through a pointer to vectype do not alias the original
5168 memory reference we have a problem. */
5172 {
5176 }
5179 {
5183 }
5186 /* FORNOW. In some cases can vectorize even if data-type not supported
5187 (e.g. - array initialization with 0). */
5195 {
5203 {
5204 /* STMT is the leader of the group. Check the operands of all the
5205 stmts of the group. */
5208 {
5212 {
5216 }
5218 }
5219 }
5220 }
5223 {
5227 }
5229 /** Transform. **/
5232 {
5238 /* FORNOW */
5241 /* We vectorize all the stmts of the interleaving group when we
5242 reach the last stmt in the group. */
5246 {
5249 }
5254 /* VEC_NUM is the number of vect stmts to be created for this group. */
5257 else
5259 }
5260 else
5261 {
5266 }
5278 /* In case the vectorization factor (VF) is bigger than the number
5279 of elements that we can fit in a vectype (nunits), we have to generate
5280 more than one vector stmt - i.e - we need to "unroll" the
5281 vector stmt by a factor VF/nunits. For more details see documentation in
5282 vect_get_vec_def_for_copy_stmt. */
5284 /* In case of interleaving (non-unit strided access):
5286 S1: &base + 2 = x2
5287 S2: &base = x0
5288 S3: &base + 1 = x1
5289 S4: &base + 3 = x3
5291 We create vectorized stores starting from base address (the access of the
5292 first stmt in the chain (S2 in the above example), when the last store stmt
5293 of the chain (S4) is reached:
5295 VS1: &base = vx2
5296 VS2: &base + vec_size*1 = vx0
5297 VS3: &base + vec_size*2 = vx1
5298 VS4: &base + vec_size*3 = vx3
5300 Then permutation statements are generated:
5302 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
5303 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
5304 ...
5306 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
5307 (the order of the data-refs in the output of vect_permute_store_chain
5308 corresponds to the order of scalar stmts in the interleaving chain - see
5309 the documentation of vect_permute_store_chain()).
5311 In case of both multiple types and interleaving, above vector stores and
5312 permutation stmts are created for every copy. The result vector stmts are
5313 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
5314 STMT_VINFO_RELATED_STMT for the next copies.
5315 */
5319 {
5320 gimple new_stmt;
5321 gimple ptr_incr;
5324 {
5326 {
5327 /* Get vectorized arguments for SLP_NODE. */
5331 }
5332 else
5333 {
5334 /* For interleaved stores we collect vectorized defs for all the
5335 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
5336 used as an input to vect_permute_store_chain(), and OPRNDS as
5337 an input to vect_get_vec_def_for_stmt_copy() for the next copy.
5339 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
5340 OPRNDS are of size 1. */
5343 {
5344 /* Since gaps are not supported for interleaved stores,
5345 GROUP_SIZE is the exact number of stmts in the chain.
5346 Therefore, NEXT_STMT can't be NULL_TREE. In case that
5347 there is no interleaving, GROUP_SIZE is 1, and only one
5348 iteration of the loop will be executed. */
5354 NULL);
5358 }
5359 }
5365 }
5366 else
5367 {
5368 /* For interleaved stores we created vectorized defs for all the
5369 defs stored in OPRNDS in the previous iteration (previous copy).
5370 DR_CHAIN is then used as an input to vect_permute_store_chain(),
5371 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
5372 next copy.
5373 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
5374 OPRNDS are of size 1. */
5376 {
5382 }
5383 dataref_ptr =
5385 }
5388 {
5390 /* Permute. */
5394 }
5398 {
5400 /* Bump the vector pointer. */
5402 NULL_TREE);
5407 /* For strided stores vectorized defs are interleaved in
5408 vect_permute_store_chain(). */
5412 /* Arguments are ready. Create the new vector stmt. */
5422 else
5429 }
5430 }
5438 }
5441 /* Function vect_setup_realignment
5443 This function is called when vectorizing an unaligned load using
5444 the dr_explicit_realign[_optimized] scheme.
5445 This function generates the following code at the loop prolog:
5447 p = initial_addr;
5448 x msq_init = *(floor(p)); # prolog load
5449 realignment_token = call target_builtin;
5450 loop:
5451 x msq = phi (msq_init, ---)
5453 The stmts marked with x are generated only for the case of
5454 dr_explicit_realign_optimized.
5456 The code above sets up a new (vector) pointer, pointing to the first
5457 location accessed by STMT, and a "floor-aligned" load using that pointer.
5458 It also generates code to compute the "realignment-token" (if the relevant
5459 target hook was defined), and creates a phi-node at the loop-header bb
5460 whose arguments are the result of the prolog-load (created by this
5461 function) and the result of a load that takes place in the loop (to be
5462 created by the caller to this function).
5464 For the case of dr_explicit_realign_optimized:
5465 The caller to this function uses the phi-result (msq) to create the
5466 realignment code inside the loop, and sets up the missing phi argument,
5467 as follows:
5468 loop:
5469 msq = phi (msq_init, lsq)
5470 lsq = *(floor(p')); # load in loop
5471 result = realign_load (msq, lsq, realignment_token);
5473 For the case of dr_explicit_realign:
5474 loop:
5475 msq = *(floor(p)); # load in loop
5476 p' = p + (VS-1);
5477 lsq = *(floor(p')); # load in loop
5478 result = realign_load (msq, lsq, realignment_token);
5480 Input:
5481 STMT - (scalar) load stmt to be vectorized. This load accesses
5482 a memory location that may be unaligned.
5483 BSI - place where new code is to be inserted.
5484 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
5485 is used.
5487 Output:
5488 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
5489 target hook, if defined.
5490 Return value - the result of the loop-header phi node. */
5492 static tree
5496 tree init_addr,
5498 {
5503 edge pe;
5505 tree vec_dest;
5506 gimple inc;
5507 tree ptr;
5508 tree data_ref;
5509 gimple new_stmt;
5510 basic_block new_bb;
5512 tree new_temp;
5513 gimple phi_stmt;
5525 /* We need to generate three things:
5526 1. the misalignment computation
5527 2. the extra vector load (for the optimized realignment scheme).
5528 3. the phi node for the two vectors from which the realignment is
5529 done (for the optimized realignment scheme).
5530 */
5532 /* 1. Determine where to generate the misalignment computation.
5534 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
5535 calculation will be generated by this function, outside the loop (in the
5536 preheader). Otherwise, INIT_ADDR had already been computed for us by the
5537 caller, inside the loop.
5539 Background: If the misalignment remains fixed throughout the iterations of
5540 the loop, then both realignment schemes are applicable, and also the
5541 misalignment computation can be done outside LOOP. This is because we are
5542 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
5543 are a multiple of VS (the Vector Size), and therefore the misalignment in
5544 different vectorized LOOP iterations is always the same.
5545 The problem arises only if the memory access is in an inner-loop nested
5546 inside LOOP, which is now being vectorized using outer-loop vectorization.
5547 This is the only case when the misalignment of the memory access may not
5548 remain fixed throughout the iterations of the inner-loop (as explained in
5549 detail in vect_supportable_dr_alignment). In this case, not only is the
5550 optimized realignment scheme not applicable, but also the misalignment
5551 computation (and generation of the realignment token that is passed to
5552 REALIGN_LOAD) have to be done inside the loop.
5554 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
5555 or not, which in turn determines if the misalignment is computed inside
5556 the inner-loop, or outside LOOP. */
5559 {
5562 }
5565 /* 2. Determine where to generate the extra vector load.
5567 For the optimized realignment scheme, instead of generating two vector
5568 loads in each iteration, we generate a single extra vector load in the
5569 preheader of the loop, and in each iteration reuse the result of the
5570 vector load from the previous iteration. In case the memory access is in
5571 an inner-loop nested inside LOOP, which is now being vectorized using
5572 outer-loop vectorization, we need to determine whether this initial vector
5573 load should be generated at the preheader of the inner-loop, or can be
5574 generated at the preheader of LOOP. If the memory access has no evolution
5575 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
5576 to be generated inside LOOP (in the preheader of the inner-loop). */
5579 {
5584 }
5585 else
5590 /* 3. For the case of the optimized realignment, create the first vector
5591 load at the loop preheader. */
5594 {
5595 /* Create msq_init = *(floor(p1)) in the loop preheader */
5610 }
5612 /* 4. Create realignment token using a target builtin, if available.
5613 It is done either inside the containing loop, or before LOOP (as
5614 determined above). */
5617 {
5618 tree builtin_decl;
5620 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
5623 else
5624 {
5625 /* Generate the INIT_ADDR computation outside LOOP. */
5631 }
5635 vec_dest =
5643 else
5644 {
5645 /* Generate the misalignment computation outside LOOP. */
5649 }
5653 /* The result of the CALL_EXPR to this builtin is determined from
5654 the value of the parameter and no global variables are touched
5655 which makes the builtin a "const" function. Requiring the
5656 builtin to have the "const" attribute makes it unnecessary
5657 to call mark_call_clobbered. */
5659 }
5668 /* 5. Create msq = phi <msq_init, lsq> in loop */
5678 }
5681 /* Function vect_strided_load_supported.
5683 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
5684 and FALSE otherwise. */
5686 static bool
5688 {
5695 optab_default);
5697 {
5701 }
5704 {
5708 }
5711 optab_default);
5713 {
5717 }
5720 {
5724 }
5726 }
5729 /* Function vect_permute_load_chain.
5731 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
5732 a power of 2, generate extract_even/odd stmts to reorder the input data
5733 correctly. Return the final references for loads in RESULT_CHAIN.
5735 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
5736 The input is 4 vectors each containing 8 elements. We assign a number to each
5737 element, the input sequence is:
5739 1st vec: 0 1 2 3 4 5 6 7
5740 2nd vec: 8 9 10 11 12 13 14 15
5741 3rd vec: 16 17 18 19 20 21 22 23
5742 4th vec: 24 25 26 27 28 29 30 31
5744 The output sequence should be:
5746 1st vec: 0 4 8 12 16 20 24 28
5747 2nd vec: 1 5 9 13 17 21 25 29
5748 3rd vec: 2 6 10 14 18 22 26 30
5749 4th vec: 3 7 11 15 19 23 27 31
5751 i.e., the first output vector should contain the first elements of each
5752 interleaving group, etc.
5754 We use extract_even/odd instructions to create such output. The input of each
5755 extract_even/odd operation is two vectors
5756 1st vec 2nd vec
5757 0 1 2 3 4 5 6 7
5759 and the output is the vector of extracted even/odd elements. The output of
5760 extract_even will be: 0 2 4 6
5761 and of extract_odd: 1 3 5 7
5764 The permutation is done in log LENGTH stages. In each stage extract_even and
5765 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
5766 order. In our example,
5768 E1: extract_even (1st vec, 2nd vec)
5769 E2: extract_odd (1st vec, 2nd vec)
5770 E3: extract_even (3rd vec, 4th vec)
5771 E4: extract_odd (3rd vec, 4th vec)
5773 The output for the first stage will be:
5775 E1: 0 2 4 6 8 10 12 14
5776 E2: 1 3 5 7 9 11 13 15
5777 E3: 16 18 20 22 24 26 28 30
5778 E4: 17 19 21 23 25 27 29 31
5780 In order to proceed and create the correct sequence for the next stage (or
5781 for the correct output, if the second stage is the last one, as in our
5782 example), we first put the output of extract_even operation and then the
5783 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
5784 The input for the second stage is:
5786 1st vec (E1): 0 2 4 6 8 10 12 14
5787 2nd vec (E3): 16 18 20 22 24 26 28 30
5788 3rd vec (E2): 1 3 5 7 9 11 13 15
5789 4th vec (E4): 17 19 21 23 25 27 29 31
5791 The output of the second stage:
5793 E1: 0 4 8 12 16 20 24 28
5794 E2: 2 6 10 14 18 22 26 30
5795 E3: 1 5 9 13 17 21 25 29
5796 E4: 3 7 11 15 19 23 27 31
5798 And RESULT_CHAIN after reordering:
5800 1st vec (E1): 0 4 8 12 16 20 24 28
5801 2nd vec (E3): 1 5 9 13 17 21 25 29
5802 3rd vec (E2): 2 6 10 14 18 22 26 30
5803 4th vec (E4): 3 7 11 15 19 23 27 31. */
5805 static bool
5808 gimple stmt,
5811 {
5813 gimple perm_stmt;
5818 /* Check that the operation is supported. */
5824 {
5826 {
5830 /* data_ref = permute_even (first_data_ref, second_data_ref); */
5837 second_vect);
5846 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
5853 second_vect);
5860 }
5862 }
5864 }
5867 /* Function vect_transform_strided_load.
5869 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
5870 to perform their permutation and ascribe the result vectorized statements to
5871 the scalar statements.
5872 */
5874 static bool
5877 {
5883 tree tmp_data_ref;
5885 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
5886 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
5887 vectors, that are ready for vector computation. */
5889 /* Permute. */
5893 /* Put a permuted data-ref in the VECTORIZED_STMT field.
5894 Since we scan the chain starting from it's first node, their order
5895 corresponds the order of data-refs in RESULT_CHAIN. */
5899 {
5903 /* Skip the gaps. Loads created for the gaps will be removed by dead
5904 code elimination pass later. No need to check for the first stmt in
5905 the group, since it always exists.
5906 DR_GROUP_GAP is the number of steps in elements from the previous
5907 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
5908 correspond to the gaps.
5909 */
5912 {
5913 gap_count++;
5915 }
5918 {
5920 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
5921 copies, and we put the new vector statement in the first available
5922 RELATED_STMT. */
5925 else
5926 {
5927 gimple prev_stmt =
5929 gimple rel_stmt =
5932 {
5935 }
5937 }
5940 /* If NEXT_STMT accesses the same DR as the previous statement,
5941 put the same TMP_DATA_REF as its vectorized statement; otherwise
5942 get the next data-ref from RESULT_CHAIN. */
5945 }
5946 }
5950 }
5953 /* vectorizable_load.
5955 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
5956 can be vectorized.
5957 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5958 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5959 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5961 bool
5963 slp_tree slp_node)
5964 {
5965 tree scalar_dest;
5969 stmt_vec_info prev_stmt_info;
5976 tree new_temp;
5979 tree dummy;
5982 gimple ptr_incr;
5992 gimple first_stmt;
5993 tree scalar_type;
6001 /* Multiple types in SLP are handled by creating the appropriate number of
6002 vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
6003 case of SLP. */
6006 else
6011 /* FORNOW. This restriction should be relaxed. */
6013 {
6017 }
6025 /* Is vectorizable load? */
6045 /* FORNOW. In some cases can vectorize even if data-type not supported
6046 (e.g. - data copies). */
6048 {
6052 }
6054 /* If accesses through a pointer to vectype do not alias the original
6055 memory reference we have a problem. */
6059 {
6063 }
6065 /* Check if the load is a part of an interleaving chain. */
6067 {
6069 /* FORNOW */
6072 /* Check if interleaving is supported. */
6076 }
6079 {
6083 }
6088 /** Transform. **/
6091 {
6093 /* Check if the chain of loads is already vectorized. */
6095 {
6098 }
6102 /* VEC_NUM is the number of vect stmts to be created for this group. */
6104 {
6107 }
6108 else
6112 }
6113 else
6114 {
6118 }
6123 /* In case the vectorization factor (VF) is bigger than the number
6124 of elements that we can fit in a vectype (nunits), we have to generate
6125 more than one vector stmt - i.e - we need to "unroll" the
6126 vector stmt by a factor VF/nunits. In doing so, we record a pointer
6127 from one copy of the vector stmt to the next, in the field
6128 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
6129 stages to find the correct vector defs to be used when vectorizing
6130 stmts that use the defs of the current stmt. The example below illustrates
6131 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
6132 4 vectorized stmts):
6134 before vectorization:
6135 RELATED_STMT VEC_STMT
6136 S1: x = memref - -
6137 S2: z = x + 1 - -
6139 step 1: vectorize stmt S1:
6140 We first create the vector stmt VS1_0, and, as usual, record a
6141 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
6142 Next, we create the vector stmt VS1_1, and record a pointer to
6143 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
6144 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
6145 stmts and pointers:
6146 RELATED_STMT VEC_STMT
6147 VS1_0: vx0 = memref0 VS1_1 -
6148 VS1_1: vx1 = memref1 VS1_2 -
6149 VS1_2: vx2 = memref2 VS1_3 -
6150 VS1_3: vx3 = memref3 - -
6151 S1: x = load - VS1_0
6152 S2: z = x + 1 - -
6154 See in documentation in vect_get_vec_def_for_stmt_copy for how the
6155 information we recorded in RELATED_STMT field is used to vectorize
6156 stmt S2. */
6158 /* In case of interleaving (non-unit strided access):
6160 S1: x2 = &base + 2
6161 S2: x0 = &base
6162 S3: x1 = &base + 1
6163 S4: x3 = &base + 3
6165 Vectorized loads are created in the order of memory accesses
6166 starting from the access of the first stmt of the chain:
6168 VS1: vx0 = &base
6169 VS2: vx1 = &base + vec_size*1
6170 VS3: vx3 = &base + vec_size*2
6171 VS4: vx4 = &base + vec_size*3
6173 Then permutation statements are generated:
6175 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
6176 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
6177 ...
6179 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
6180 (the order of the data-refs in the output of vect_permute_load_chain
6181 corresponds to the order of scalar stmts in the interleaving chain - see
6182 the documentation of vect_permute_load_chain()).
6183 The generation of permutation stmts and recording them in
6184 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
6186 In case of both multiple types and interleaving, the vector loads and
6187 permutation stmts above are created for every copy. The result vector stmts
6188 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
6189 STMT_VINFO_RELATED_STMT for the next copies. */
6191 /* If the data reference is aligned (dr_aligned) or potentially unaligned
6192 on a target that supports unaligned accesses (dr_unaligned_supported)
6193 we generate the following code:
6194 p = initial_addr;
6195 indx = 0;
6196 loop {
6197 p = p + indx * vectype_size;
6198 vec_dest = *(p);
6199 indx = indx + 1;
6200 }
6202 Otherwise, the data reference is potentially unaligned on a target that
6203 does not support unaligned accesses (dr_explicit_realign_optimized) -
6204 then generate the following code, in which the data in each iteration is
6205 obtained by two vector loads, one from the previous iteration, and one
6206 from the current iteration:
6207 p1 = initial_addr;
6208 msq_init = *(floor(p1))
6209 p2 = initial_addr + VS - 1;
6210 realignment_token = call target_builtin;
6211 indx = 0;
6212 loop {
6213 p2 = p2 + indx * vectype_size
6214 lsq = *(floor(p2))
6215 vec_dest = realign_load (msq, lsq, realignment_token)
6216 indx = indx + 1;
6217 msq = lsq;
6218 } */
6220 /* If the misalignment remains the same throughout the execution of the
6221 loop, we can create the init_addr and permutation mask at the loop
6222 preheader. Otherwise, it needs to be created inside the loop.
6223 This can only occur when vectorizing memory accesses in the inner-loop
6224 nested within an outer-loop that is being vectorized. */
6229 {
6232 }
6237 {
6242 {
6245 }
6246 }
6247 else
6252 {
6253 /* 1. Create the vector pointer update chain. */
6259 else
6260 dataref_ptr =
6264 {
6267 NULL_TREE);
6269 /* 2. Create the vector-load in the loop. */
6271 {
6277 {
6282 data_ref =
6285 }
6287 {
6294 dr_explicit_realign,
6312 }
6318 }
6326 /* 3. Handle explicit realignment if necessary/supported. Create in
6327 loop: vec_dest = realign_load (msq, lsq, realignment_token) */
6330 {
6331 tree tmp;
6338 realignment_token);
6345 {
6350 }
6351 }
6353 /* 4. Handle invariant-load. */
6355 {
6359 {
6364 /* CHECKME: bitpos depends on endianess? */
6368 vec_dest =
6377 /* FIXME: use build_constructor directly. */
6381 }
6382 else
6384 }
6386 /* Collect vector loads and later create their permutation in
6387 vect_transform_strided_load (). */
6391 /* Store vector loads in the corresponding SLP_NODE. */
6394 }
6400 {
6406 }
6407 else
6408 {
6411 else
6414 }
6415 }
6421 }
6424 /* Function vectorizable_live_operation.
6426 STMT computes a value that is used outside the loop. Check if
6427 it can be supported. */
6429 bool
6433 {
6439 tree op;
6440 tree def;
6441 gimple def_stmt;
6457 /* FORNOW. CHECKME. */
6467 /* FORNOW: support only if all uses are invariant. This means
6468 that the scalar operations can remain in place, unvectorized.
6469 The original last scalar value that they compute will be used. */
6472 {
6475 else
6478 {
6482 }
6486 }
6488 /* No transformation is required for the cases we currently support. */
6490 }
6493 /* Function vect_is_simple_cond.
6495 Input:
6496 LOOP - the loop that is being vectorized.
6497 COND - Condition that is checked for simple use.
6499 Returns whether a COND can be vectorized. Checks whether
6500 condition operands are supportable using vec_is_simple_use. */
6502 static bool
6504 {
6506 tree def;
6516 {
6520 }
6526 {
6530 }
6536 }
6538 /* vectorizable_condition.
6540 Check if STMT is conditional modify expression that can be vectorized.
6541 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
6542 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
6543 at BSI.
6545 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6547 bool
6550 {
6559 tree new_temp;
6562 tree def;
6578 /* FORNOW: SLP not supported. */
6582 /* FORNOW: not yet supported. */
6584 {
6588 }
6590 /* Is vectorizable conditional operation? */
6608 /* We do not handle two different vector types for the condition
6609 and the values. */
6614 {
6619 }
6626 {
6631 }
6641 {
6644 }
6646 /* Transform */
6648 /* Handle def. */
6652 /* Handle cond expr. */
6653 vec_cond_lhs =
6655 vec_cond_rhs =
6660 /* Arguments are ready. Create the new vector stmt. */
6672 }
6675 /* Function vect_transform_stmt.
6677 Create a vectorized stmt to replace STMT, and insert it at BSI. */
6679 static bool
6682 {
6686 gimple orig_stmt_in_pattern;
6690 {
6731 {
6732 /* In case of interleaving, the whole chain is vectorized when the
6733 last store in the chain is reached. Store stmts before the last
6734 one are skipped, and there vec_stmt_info shouldn't be freed
6735 meanwhile. */
6739 }
6740 else
6763 {
6767 }
6768 }
6772 {
6775 }
6778 {
6782 {
6784 /* STMT was inserted by the vectorizer to replace a computation idiom.
6785 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
6786 computed this idiom. We need to record a pointer to VEC_STMT in
6787 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
6788 documentation of vect_pattern_recog. */
6790 {
6793 }
6794 }
6795 }
6798 }
6801 /* This function builds ni_name = number of iterations loop executes
6802 on the loop preheader. */
6804 static tree
6806 {
6809 edge pe;
6819 {
6822 }
6825 }
6828 /* This function generates the following statements:
6830 ni_name = number of iterations loop executes
6831 ratio = ni_name / vf
6832 ratio_mult_vf_name = ratio * vf
6834 and places them at the loop preheader edge. */
6836 static void
6841 {
6843 edge pe;
6844 basic_block new_bb;
6845 gimple_seq stmts;
6846 tree ni_name;
6847 tree var;
6848 tree ratio_name;
6849 tree ratio_mult_vf_name;
6853 tree log_vf;
6857 /* Generate temporary variable that contains
6858 number of iterations loop executes. */
6863 /* Create: ratio = ni >> log2(vf) */
6867 {
6876 }
6878 /* Create: ratio_mult_vf = ratio << log2 (vf). */
6883 {
6893 }
6900 }
6903 /* Function vect_update_ivs_after_vectorizer.
6905 "Advance" the induction variables of LOOP to the value they should take
6906 after the execution of LOOP. This is currently necessary because the
6907 vectorizer does not handle induction variables that are used after the
6908 loop. Such a situation occurs when the last iterations of LOOP are
6909 peeled, because:
6910 1. We introduced new uses after LOOP for IVs that were not originally used
6911 after LOOP: the IVs of LOOP are now used by an epilog loop.
6912 2. LOOP is going to be vectorized; this means that it will iterate N/VF
6913 times, whereas the loop IVs should be bumped N times.
6915 Input:
6916 - LOOP - a loop that is going to be vectorized. The last few iterations
6917 of LOOP were peeled.
6918 - NITERS - the number of iterations that LOOP executes (before it is
6919 vectorized). i.e, the number of times the ivs should be bumped.
6920 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
6921 coming out from LOOP on which there are uses of the LOOP ivs
6922 (this is the path from LOOP->exit to epilog_loop->preheader).
6924 The new definitions of the ivs are placed in LOOP->exit.
6925 The phi args associated with the edge UPDATE_E in the bb
6926 UPDATE_E->dest are updated accordingly.
6928 Assumption 1: Like the rest of the vectorizer, this function assumes
6929 a single loop exit that has a single predecessor.
6931 Assumption 2: The phi nodes in the LOOP header and in update_bb are
6932 organized in the same order.
6934 Assumption 3: The access function of the ivs is simple enough (see
6935 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
6937 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
6938 coming out of LOOP on which the ivs of LOOP are used (this is the path
6939 that leads to the epilog loop; other paths skip the epilog loop). This
6940 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
6941 needs to have its phis updated.
6942 */
6944 static void
6946 edge update_e)
6947 {
6954 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
6956 /* Make sure there exists a single-predecessor exit bb: */
6962 {
6964 tree evolution_part;
6965 tree init_expr;
6966 tree step_expr;
6968 gimple_stmt_iterator last_gsi;
6973 {
6976 }
6978 /* Skip virtual phi's. */
6980 {
6984 }
6986 /* Skip reduction phis. */
6988 {
6992 }
6996 evolution_part =
7000 /* FORNOW: We do not support IVs whose evolution function is a polynomial
7001 of degree >= 2 or exponential. */
7010 init_expr,
7014 else
7018 niters),
7019 step_expr),
7020 init_expr);
7031 /* Fix phi expressions in the successor bb. */
7033 }
7034 }
7036 /* Return the more conservative threshold between the
7037 min_profitable_iters returned by the cost model and the user
7038 specified threshold, if provided. */
7040 static unsigned int
7043 {
7050 /* Use the cost model only if it is more conservative than user specified
7051 threshold. */
7054 && (!min_scalar_loop_bound
7062 }
7064 /* Function vect_do_peeling_for_loop_bound
7066 Peel the last iterations of the loop represented by LOOP_VINFO.
7067 The peeled iterations form a new epilog loop. Given that the loop now
7068 iterates NITERS times, the new epilog loop iterates
7069 NITERS % VECTORIZATION_FACTOR times.
7071 The original loop will later be made to iterate
7072 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
7074 static void
7076 {
7080 edge update_e;
7081 basic_block preheader;
7092 /* Generate the following variables on the preheader of original loop:
7094 ni_name = number of iteration the original loop executes
7095 ratio = ni_name / vf
7096 ratio_mult_vf_name = ratio * vf */
7102 /* If cost model check not done during versioning and
7103 peeling for alignment. */
7107 {
7110 /* Get profitability threshold for vectorized loop. */
7114 min_profitable_iters);
7115 }
7122 #ifdef ENABLE_CHECKING
7124 #endif
7126 /* A guard that controls whether the new_loop is to be executed or skipped
7127 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
7128 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
7129 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
7130 is on the path where the LOOP IVs are used and need to be updated. */
7135 else
7138 /* Update IVs of original loop as if they were advanced
7139 by ratio_mult_vf_name steps. */
7142 /* After peeling we have to reset scalar evolution analyzer. */
7146 }
7149 /* Function vect_gen_niters_for_prolog_loop
7151 Set the number of iterations for the loop represented by LOOP_VINFO
7152 to the minimum between LOOP_NITERS (the original iteration count of the loop)
7153 and the misalignment of DR - the data reference recorded in
7154 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
7155 this loop, the data reference DR will refer to an aligned location.
7157 The following computation is generated:
7159 If the misalignment of DR is known at compile time:
7160 addr_mis = int mis = DR_MISALIGNMENT (dr);
7161 Else, compute address misalignment in bytes:
7162 addr_mis = addr & (vectype_size - 1)
7164 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
7166 (elem_size = element type size; an element is the scalar element whose type
7167 is the inner type of the vectype)
7169 When the step of the data-ref in the loop is not 1 (as in interleaved data
7170 and SLP), the number of iterations of the prolog must be divided by the step
7171 (which is equal to the size of interleaved group).
7173 The above formulas assume that VF == number of elements in the vector. This
7174 may not hold when there are multiple-types in the loop.
7175 In this case, for some data-references in the loop the VF does not represent
7176 the number of elements that fit in the vector. Therefore, instead of VF we
7177 use TYPE_VECTOR_SUBPARTS. */
7179 static tree
7181 {
7184 tree var;
7185 gimple_seq stmts;
7187 edge pe;
7188 basic_block new_bb;
7204 {
7213 }
7214 else
7215 {
7223 tree elem_size_log =
7227 tree byte_misalign;
7228 tree elem_misalign;
7233 /* Create: byte_misalign = addr & (vectype_size - 1) */
7234 byte_misalign =
7237 /* Create: elem_misalign = byte_misalign / element_size */
7238 elem_misalign =
7241 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
7245 }
7247 /* Create: prolog_loop_niters = min (iters, loop_niters) */
7248 /* If the loop bound is known at compile time we already verified that it is
7249 greater than vf; since the misalignment ('iters') is at most vf, there's
7250 no need to generate the MIN_EXPR in this case. */
7255 {
7258 }
7265 /* Insert stmt on loop preheader edge. */
7267 {
7270 }
7273 }
7276 /* Function vect_update_init_of_dr
7278 NITERS iterations were peeled from LOOP. DR represents a data reference
7279 in LOOP. This function updates the information recorded in DR to
7280 account for the fact that the first NITERS iterations had already been
7281 executed. Specifically, it updates the OFFSET field of DR. */
7283 static void
7285 {
7291 }
7294 /* Function vect_update_inits_of_drs
7296 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
7297 This function updates the information recorded for the data references in
7298 the loop to account for the fact that the first NITERS iterations had
7299 already been executed. Specifically, it updates the initial_condition of
7300 the access_function of all the data_references in the loop. */
7302 static void
7304 {
7314 }
7317 /* Function vect_do_peeling_for_alignment
7319 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
7320 'niters' is set to the misalignment of one of the data references in the
7321 loop, thereby forcing it to refer to an aligned location at the beginning
7322 of the execution of this loop. The data reference for which we are
7323 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
7325 static void
7327 {
7330 tree n_iters;
7345 /* If cost model check not done during versioning. */
7348 {
7351 /* Get profitability threshold for vectorized loop. */
7355 min_profitable_iters);
7356 }
7358 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
7359 new_loop =
7365 #ifdef ENABLE_CHECKING
7367 #endif
7369 /* Update number of times loop executes. */
7374 /* Update the init conditions of the access functions of all data refs. */
7377 /* After peeling we have to reset scalar evolution analyzer. */
7381 }
7384 /* Function vect_create_cond_for_align_checks.
7386 Create a conditional expression that represents the alignment checks for
7387 all of data references (array element references) whose alignment must be
7388 checked at runtime.
7390 Input:
7391 COND_EXPR - input conditional expression. New conditions will be chained
7392 with logical AND operation.
7393 LOOP_VINFO - two fields of the loop information are used.
7394 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
7395 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
7397 Output:
7398 COND_EXPR_STMT_LIST - statements needed to construct the conditional
7399 expression.
7400 The returned value is the conditional expression to be used in the if
7401 statement that controls which version of the loop gets executed at runtime.
7403 The algorithm makes two assumptions:
7404 1) The number of bytes "n" in a vector is a power of 2.
7405 2) An address "a" is aligned if a%n is zero and that this
7406 test can be done as a&(n-1) == 0. For example, for 16
7407 byte vectors the test is a&0xf == 0. */
7409 static void
7413 {
7417 gimple ref_stmt;
7419 tree mask_cst;
7421 tree psize;
7422 tree int_ptrsize_type;
7426 gimple and_stmt;
7427 tree ptrsize_zero;
7428 tree part_cond_expr;
7430 /* Check that mask is one less than a power of 2, i.e., mask is
7431 all zeros followed by all ones. */
7434 /* CHECKME: what is the best integer or unsigned type to use to hold a
7435 cast from a pointer value? */
7437 int_ptrsize_type
7440 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
7441 of the first vector of the i'th data reference. */
7444 {
7446 tree addr_base;
7451 /* create: addr_tmp = (int)(address_of_first_vector) */
7452 addr_base =
7466 /* The addresses are OR together. */
7469 {
7470 /* create: or_tmp = or_tmp | addr_tmp */
7476 new_or_tmp_name,
7481 }
7482 else
7489 /* create: and_tmp = or_tmp & mask */
7499 /* Make and_tmp the left operand of the conditional test against zero.
7500 if and_tmp has a nonzero bit then some address is unaligned. */
7507 else
7509 }
7511 /* Function vect_vfa_segment_size.
7513 Create an expression that computes the size of segment
7514 that will be accessed for a data reference. The functions takes into
7515 account that realignment loads may access one more vector.
7517 Input:
7518 DR: The data reference.
7519 VECT_FACTOR: vectorization factor.
7521 Return an expression whose value is the size of segment which will be
7522 accessed by DR. */
7524 static tree
7526 {
7531 {
7532 tree vector_size = TYPE_SIZE_UNIT
7537 }
7539 }
7541 /* Function vect_create_cond_for_alias_checks.
7543 Create a conditional expression that represents the run-time checks for
7544 overlapping of address ranges represented by a list of data references
7545 relations passed as input.
7547 Input:
7548 COND_EXPR - input conditional expression. New conditions will be chained
7549 with logical AND operation.
7550 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
7551 to be checked.
7553 Output:
7554 COND_EXPR - conditional expression.
7555 COND_EXPR_STMT_LIST - statements needed to construct the conditional
7556 expression.
7559 The returned value is the conditional expression to be used in the if
7560 statement that controls which version of the loop gets executed at runtime.
7561 */
7563 static void
7567 {
7571 tree vect_factor =
7574 ddr_p ddr;
7576 tree part_cond_expr;
7578 /* Create expression
7579 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
7580 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
7581 &&
7582 ...
7583 &&
7584 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
7585 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
7591 {
7602 {
7605 }
7611 {
7614 }
7616 addr_base_a =
7619 addr_base_b =
7627 {
7633 }
7636 part_cond_expr =
7640 addr_base_a,
7641 segment_length_a),
7642 addr_base_b),
7645 addr_base_b,
7646 segment_length_b),
7647 addr_base_a));
7652 else
7654 }
7659 }
7661 /* Function vect_loop_versioning.
7663 If the loop has data references that may or may not be aligned or/and
7664 has data reference relations whose independence was not proven then
7665 two versions of the loop need to be generated, one which is vectorized
7666 and one which isn't. A test is then generated to control which of the
7667 loops is executed. The test checks for the alignment of all of the
7668 data references that may or may not be aligned. An additional
7669 sequence of runtime tests is generated for each pairs of DDRs whose
7670 independence was not proven. The vectorized version of loop is
7671 executed only if both alias and alignment tests are passed.
7673 The test generated to check which version of loop is executed
7674 is modified to also check for profitability as indicated by the
7675 cost model initially. */
7677 static void
7679 {
7684 basic_block condition_bb;
7686 basic_block merge_bb;
7687 basic_block new_exit_bb;
7690 tree arg;
7697 /* Get profitability threshold for vectorized loop. */
7701 min_profitable_iters);
7703 cond_expr =
7718 cond_expr =
7720 cond_expr =
7729 /* Loop versioning violates an assumption we try to maintain during
7730 vectorization - that the loop exit block has a single predecessor.
7731 After versioning, the exit block of both loop versions is the same
7732 basic block (i.e. it has two predecessors). Just in order to simplify
7733 following transformations in the vectorizer, we fix this situation
7734 here by adding a new (empty) block on the exit-edge of the loop,
7735 with the proper loop-exit phis to maintain loop-closed-form. */
7744 {
7747 new_exit_bb);
7751 }
7753 /* End loop-exit-fixes after versioning. */
7757 {
7760 }
7761 }
7763 /* Remove a group of stores (for SLP or interleaving), free their
7764 stmt_vec_info. */
7766 static void
7768 {
7770 gimple tmp;
7771 gimple_stmt_iterator next_si;
7774 {
7775 /* Free the attached stmt_vec_info and remove the stmt. */
7781 }
7782 }
7785 /* Vectorize SLP instance tree in postorder. */
7787 static bool
7790 {
7791 gimple stmt;
7793 gimple_stmt_iterator si;
7794 stmt_vec_info stmt_info;
7796 tree vectype;
7802 vectorization_factor);
7804 vectorization_factor);
7808 /* VECTYPE is the type of the destination. */
7813 /* For each SLP instance calculate number of vector stmts to be created
7814 for the scalar stmts in each node of the SLP tree. Number of vector
7815 elements in one vector iteration is the number of scalar elements in
7816 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
7817 size. */
7824 {
7827 }
7832 {
7834 /* If IS_STORE is TRUE, the vectorization of the
7835 interleaving chain was completed - free all the stores in
7836 the chain. */
7838 else
7839 /* FORNOW: SLP originates only from strided stores. */
7843 }
7845 /* FORNOW: SLP originates only from strided stores. */
7847 }
7850 static bool
7852 {
7855 slp_instance instance;
7860 {
7861 /* Schedule the tree of INSTANCE. */
7863 instance,
7869 }
7872 }
7874 /* Function vect_transform_loop.
7876 The analysis phase has determined that the loop is vectorizable.
7877 Vectorize the loop - created vectorized stmts to replace the scalar
7878 stmts in the loop, and update the loop exit condition. */
7880 void
7882 {
7886 gimple_stmt_iterator si;
7901 /* CHECKME: we wouldn't need this if we called update_ssa once
7902 for all loops. */
7905 /* Peel the loop if there are data refs with unknown alignment.
7906 Only one data ref with unknown store is allowed. */
7911 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
7912 compile time constant), or it is a constant that doesn't divide by the
7913 vectorization factor, then an epilog loop needs to be created.
7914 We therefore duplicate the loop: the original loop will be vectorized,
7915 and will compute the first (n/VF) iterations. The second copy of the loop
7916 will remain scalar and will compute the remaining (n%VF) iterations.
7917 (VF is the vectorization factor). */
7923 else
7927 /* 1) Make sure the loop header has exactly two entries
7928 2) Make sure we have a preheader basic block. */
7934 /* FORNOW: the vectorizer supports only loops which body consist
7935 of one basic block (header + empty latch). When the vectorizer will
7936 support more involved loop forms, the order by which the BBs are
7937 traversed need to be reconsidered. */
7940 {
7942 stmt_vec_info stmt_info;
7943 gimple phi;
7946 {
7949 {
7952 }
7967 {
7971 }
7972 }
7975 {
7980 {
7983 }
7987 /* vector stmts created in the outer-loop during vectorization of
7988 stmts in an inner-loop may not have a stmt_info, and do not
7989 need to be vectorized. */
7991 {
7994 }
7998 {
8001 }
8004 nunits =
8009 /* For SLP VF is set according to unrolling factor, and not to
8010 vector size, hence for SLP this print is not valid. */
8013 /* SLP. Schedule all the SLP instances when the first SLP stmt is
8014 reached. */
8016 {
8018 {
8026 /* IS_STORE is true if STMT is a store. Stores cannot be of
8027 hybrid SLP type. They are removed in
8028 vect_schedule_slp_instance and their vinfo is destroyed. */
8030 {
8033 }
8034 }
8036 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
8038 {
8041 }
8042 }
8044 /* -------- vectorize statement ------------ */
8051 {
8053 {
8054 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
8055 interleaving chain was completed - free all the stores in
8056 the chain. */
8060 }
8061 else
8062 {
8063 /* Free the attached stmt_vec_info and remove the stmt. */
8067 }
8068 }
8077 /* The memory tags and pointers in vectorized statements need to
8078 have their SSA forms updated. FIXME, why can't this be delayed
8079 until all the loops have been transformed? */
8086 }