| blob | faf3b3ade221fc6f5539846aac105007c792ad61 |
1 /* Transformation Utilities for Loop Vectorization.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
48 /* Utility functions for the code transformation. */
51 static tree vect_create_data_ref_ptr
53 static tree vect_create_addr_base_for_vector_ref
58 static void vect_finish_stmt_generation
64 /* Utility function dealing with loop peeling (not peeling itself). */
65 static void vect_generate_tmps_on_preheader
75 static int
77 {
81 {
99 }
100 }
103 /* Function vect_estimate_min_profitable_iters
105 Return the number of iterations required for the vector version of the
106 loop to be profitable relative to the cost of the scalar version of the
107 loop.
109 TODO: Take profile info into account before making vectorization
110 decisions, if available. */
112 int
114 {
130 slp_instance instance;
132 /* Cost model disabled. */
134 {
138 }
140 /* Requires loop versioning tests to handle misalignment. */
143 {
144 /* FIXME: Make cost depend on complexity of individual check. */
145 vec_outside_cost +=
150 }
153 {
154 /* FIXME: Make cost depend on complexity of individual check. */
155 vec_outside_cost +=
160 }
164 {
166 }
168 /* Count statements in scalar loop. Using this as scalar cost for a single
169 iteration for now.
171 TODO: Add outer loop support.
173 TODO: Consider assigning different costs to different scalar
174 statements. */
176 /* FORNOW. */
181 {
182 block_stmt_iterator si;
187 else
191 {
199 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
200 some of the "outside" costs are generated inside the outer-loop. */
202 }
203 }
205 /* Add additional cost for the peeled instructions in prologue and epilogue
206 loop.
208 FORNOW: If we dont know the value of peel_iters for prologue or epilogue
209 at compile-time - we assume it's vf/2 (the worst would be vf-1).
211 TODO: Build an expression that represents peel_iters for prologue and
212 epilogue to be used in a run-time test. */
217 {
223 /* If peeling for alignment is unknown, loop bound of main loop becomes
224 unknown. */
228 "epilogue peel iters set to vf/2 because "
231 /* If peeled iterations are unknown, count a taken branch and a not taken
232 branch per peeled loop. Even if scalar loop iterations are known,
233 vector iterations are not known since peeled prologue iterations are
234 not known. Hence guards remain the same. */
238 }
239 else
240 {
242 {
249 }
250 else
254 {
258 "epilogue peel iters set to vf/2 because "
261 /* If peeled iterations are known but number of scalar loop
262 iterations are unknown, count a taken branch per peeled loop. */
265 }
266 else
267 {
272 }
273 }
279 /* Allow targets add additional (outside-of-loop) costs. FORNOW, the only
280 information we provide for the target is whether testing against the
281 threshold involves a runtime test. */
283 {
286 /* If the number of iterations is unknown, or the
287 peeling-for-misalignment amount is unknown, we eill have to generate
288 a runtime test to test the loop count against the threshold. */
292 vec_outside_cost +=
297 }
299 /* Add SLP costs. */
302 {
305 }
307 /* Calculate number of iterations required to make the vector version
308 profitable, relative to the loop bodies only. The following condition
309 must hold true: ((SIC*VF)-VIC)*niters > VOC*VF, where
310 SIC = scalar iteration cost, VIC = vector iteration cost,
311 VOC = vector outside cost and VF = vectorization factor. */
314 {
317 else
318 {
328 min_profitable_iters++;
329 }
330 }
331 /* vector version will never be profitable. */
332 else
333 {
336 "is divisible by scalar iteration cost = %d by a factor "
340 }
343 {
346 vec_inside_cost);
348 vec_outside_cost);
351 peel_iters_prologue);
353 peel_iters_epilogue);
355 min_profitable_iters);
356 }
358 min_profitable_iters =
361 /* Because the condition we create is:
362 if (niters <= min_profitable_iters)
363 then skip the vectorized loop. */
364 min_profitable_iters--;
368 min_profitable_iters);
371 }
374 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
375 functions. Design better to avoid maintenance issues. */
377 /* Function vect_model_reduction_cost.
379 Models cost for a reduction operation, including the vector ops
380 generated within the strip-mine loop, the initial definition before
381 the loop, and the epilogue code that must be generated. */
383 static bool
386 {
389 optab optab;
390 tree vectype;
391 tree orig_stmt;
392 tree reduction_op;
399 /* Cost of reduction op inside loop. */
405 {
407 {
410 }
412 }
422 /* Add in cost for initial definition. */
425 /* Determine cost of epilogue code.
427 We have a reduction operator that will reduce the vector in one statement.
428 Also requires scalar extract. */
431 {
434 else
435 {
437 tree bitsize =
444 /* We have a whole vector shift available. */
448 /* Final reduction via vector shifts and the reduction operator. Also
449 requires scalar extract. */
452 else
453 /* Use extracts and reduction op for final reduction. For N elements,
454 we have N extracts and N-1 reduction ops. */
456 }
457 }
467 }
470 /* Function vect_model_induction_cost.
472 Models cost for induction operations. */
474 static void
476 {
477 /* loop cost for vec_loop. */
479 /* prologue cost for vec_init and vec_step. */
486 }
489 /* Function vect_model_simple_cost.
491 Models cost for simple operations, i.e. those that only emit ncopies of a
492 single op. Right now, this does not account for multiple insns that could
493 be generated for the single vector op. We will handle that shortly. */
495 void
498 {
504 /* FORNOW: Assuming maximum 2 args per stmts. */
506 {
509 }
515 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
518 }
521 /* Function vect_cost_strided_group_size
523 For strided load or store, return the group_size only if it is the first
524 load or store of a group, else return 1. This ensures that group size is
525 only returned once per group. */
527 static int
529 {
536 }
539 /* Function vect_model_store_cost
541 Models cost for stores. In the case of strided accesses, one access
542 has the overhead of the strided access attributed to it. */
544 void
547 {
554 /* Strided access? */
557 /* Not a strided access. */
558 else
561 /* Is this an access in a group of stores, which provide strided access?
562 If so, add in the cost of the permutes. */
564 {
565 /* Uses a high and low interleave operation for each needed permute. */
571 group_size);
573 }
575 /* Costs of the stores. */
582 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
585 }
588 /* Function vect_model_load_cost
590 Models cost for loads. In the case of strided accesses, the last access
591 has the overhead of the strided access attributed to it. Since unaligned
592 accesses are supported for loads, we also account for the costs of the
593 access scheme chosen. */
595 void
598 {
601 tree first_stmt;
605 /* Strided accesses? */
608 {
611 }
612 /* Not a strided access. */
613 else
614 {
617 }
621 /* Is this an access in a group of loads providing strided access?
622 If so, add in the cost of the permutes. */
624 {
625 /* Uses an even and odd extract operations for each needed permute. */
631 group_size);
633 }
635 /* The loads themselves. */
637 {
639 {
646 }
648 {
649 /* Here, we assign an additional cost for the unaligned load. */
657 }
659 {
662 /* FIXME: If the misalignment remains fixed across the iterations of
663 the containing loop, the following cost should be added to the
664 outside costs. */
669 }
671 {
676 /* Unaligned software pipeline has a load of an address, an initial
677 load, and possibly a mask operation to "prime" the loop. However,
678 if this is an access in a group of loads, which provide strided
679 access, then the above cost should only be considered for one
680 access in the group. Inside the loop, there is a load op
681 and a realignment op. */
684 {
688 }
693 }
697 }
703 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
706 }
709 /* Function vect_get_new_vect_var.
711 Returns a name for a new variable. The current naming scheme appends the
712 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
713 the name of vectorizer generated variables, and appends that to NAME if
714 provided. */
716 static tree
718 {
720 tree new_vect_var;
723 {
735 }
738 {
742 }
743 else
746 /* Mark vector typed variable as a gimple register variable. */
751 }
754 /* Function vect_create_addr_base_for_vector_ref.
756 Create an expression that computes the address of the first memory location
757 that will be accessed for a data reference.
759 Input:
760 STMT: The statement containing the data reference.
761 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
762 OFFSET: Optional. If supplied, it is be added to the initial address.
763 LOOP: Specify relative to which loop-nest should the address be computed.
764 For example, when the dataref is in an inner-loop nested in an
765 outer-loop that is now being vectorized, LOOP can be either the
766 outer-loop, or the inner-loop. The first memory location accessed
767 by the following dataref ('in' points to short):
769 for (i=0; i<N; i++)
770 for (j=0; j<M; j++)
771 s += in[i+j]
773 is as follows:
774 if LOOP=i_loop: &in (relative to i_loop)
775 if LOOP=j_loop: &in+i*2B (relative to j_loop)
777 Output:
778 1. Return an SSA_NAME whose value is the address of the memory location of
779 the first vector of the data reference.
780 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
781 these statement(s) which define the returned SSA_NAME.
783 FORNOW: We are only handling array accesses with step 1. */
785 static tree
788 tree offset,
790 {
795 tree base_name;
796 tree data_ref_base_var;
797 tree new_base_stmt;
798 tree vec_stmt;
808 {
817 }
819 /* Create data_ref_base */
827 /* Create base_offset */
836 {
845 }
847 /* base + base_offset */
853 /* addr_expr = addr_base */
865 {
868 }
870 }
873 /* Function vect_create_data_ref_ptr.
875 Create a new pointer to vector type (vp), that points to the first location
876 accessed in the loop by STMT, along with the def-use update chain to
877 appropriately advance the pointer through the loop iterations. Also set
878 aliasing information for the pointer. This vector pointer is used by the
879 callers to this function to create a memory reference expression for vector
880 load/store access.
882 Input:
883 1. STMT: a stmt that references memory. Expected to be of the form
884 GIMPLE_MODIFY_STMT <name, data-ref> or
885 GIMPLE_MODIFY_STMT <data-ref, name>.
886 2. AT_LOOP: the loop where the vector memref is to be created.
887 3. OFFSET (optional): an offset to be added to the initial address accessed
888 by the data-ref in STMT.
889 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
890 pointing to the initial address.
891 5. TYPE: if not NULL indicates the required type of the data-ref
893 Output:
894 1. Declare a new ptr to vector_type, and have it point to the base of the
895 data reference (initial addressed accessed by the data reference).
896 For example, for vector of type V8HI, the following code is generated:
898 v8hi *vp;
899 vp = (v8hi *)initial_address;
901 if OFFSET is not supplied:
902 initial_address = &a[init];
903 if OFFSET is supplied:
904 initial_address = &a[init + OFFSET];
906 Return the initial_address in INITIAL_ADDRESS.
908 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
909 update the pointer in each iteration of the loop.
911 Return the increment stmt that updates the pointer in PTR_INCR.
913 3. Set INV_P to true if the access pattern of the data reference in the
914 vectorized loop is invariant. Set it to false otherwise.
916 4. Return the pointer. */
918 static tree
922 {
923 tree base_name;
930 tree vect_ptr_type;
931 tree vect_ptr;
932 tree tag;
933 tree new_temp;
934 tree vec_stmt;
936 edge pe;
937 basic_block new_bb;
938 tree vect_ptr_init;
940 tree vptr;
941 block_stmt_iterator incr_bsi;
944 tree incr;
945 tree step;
947 /* Check the step (evolution) of the load in LOOP, and record
948 whether it's invariant. */
951 else
956 else
959 /* Create an expression for the first address accessed by this load
960 in LOOP. */
964 {
977 }
979 /** (1) Create the new vector-pointer variable: **/
982 else
988 /** (2) Add aliasing information to the new vector-pointer:
989 (The points-to info (DR_PTR_INFO) may be defined later.) **/
994 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
995 tag must be created with tag added to its may alias list. */
998 else
1003 /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
1004 vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
1005 def-use update cycles for the pointer: One relative to the outer-loop
1006 (LOOP), which is what steps (3) and (4) below do. The other is relative
1007 to the inner-loop (which is the inner-most loop containing the dataref),
1008 and this is done be step (5) below.
1010 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
1011 inner-most loop, and so steps (3),(4) work the same, and step (5) is
1012 redundant. Steps (3),(4) create the following:
1014 vp0 = &base_addr;
1015 LOOP: vp1 = phi(vp0,vp2)
1016 ...
1017 ...
1018 vp2 = vp1 + step
1019 goto LOOP
1021 If there is an inner-loop nested in loop, then step (5) will also be
1022 applied, and an additional update in the inner-loop will be created:
1024 vp0 = &base_addr;
1025 LOOP: vp1 = phi(vp0,vp2)
1026 ...
1027 inner: vp3 = phi(vp1,vp4)
1028 vp4 = vp3 + inner_step
1029 if () goto inner
1030 ...
1031 vp2 = vp1 + step
1032 if () goto LOOP */
1034 /** (3) Calculate the initial address the vector-pointer, and set
1035 the vector-pointer to point to it before the loop: **/
1037 /* Create: (&(base[init_val+offset]) in the loop preheader. */
1046 /* Create: p = (vectype *) initial_base */
1055 /** (4) Handle the updating of the vector-pointer inside the loop.
1056 This is needed when ONLY_INIT is false, and also when AT_LOOP
1057 is the inner-loop nested in LOOP (during outer-loop vectorization).
1058 **/
1061 {
1062 /* Copy the points-to information if it exists. */
1066 }
1067 else
1068 {
1069 /* The step of the vector pointer is the Vector Size. */
1071 /* One exception to the above is when the scalar step of the load in
1072 LOOP is zero. In this case the step here is also zero. */
1086 /* Copy the points-to information if it exists. */
1088 {
1091 }
1098 }
1104 /** (5) Handle the updating of the vector-pointer inside the inner-loop
1105 nested in LOOP, if exists: **/
1109 {
1118 /* Copy the points-to information if it exists. */
1120 {
1123 }
1130 }
1131 else
1133 }
1136 /* Function bump_vector_ptr
1138 Increment a pointer (to a vector type) by vector-size. If requested,
1139 i.e. if PTR-INCR is given, then also connect the new increment stmt
1140 to the existing def-use update-chain of the pointer, by modifying
1141 the PTR_INCR as illustrated below:
1143 The pointer def-use update-chain before this function:
1144 DATAREF_PTR = phi (p_0, p_2)
1145 ....
1146 PTR_INCR: p_2 = DATAREF_PTR + step
1148 The pointer def-use update-chain after this function:
1149 DATAREF_PTR = phi (p_0, p_2)
1150 ....
1151 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1152 ....
1153 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
1155 Input:
1156 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
1157 in the loop.
1158 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
1159 the loop. The increment amount across iterations is expected
1160 to be vector_size.
1161 BSI - location where the new update stmt is to be placed.
1162 STMT - the original scalar memory-access stmt that is being vectorized.
1163 BUMP - optional. The offset by which to bump the pointer. If not given,
1164 the offset is assumed to be vector_size.
1166 Output: Return NEW_DATAREF_PTR as illustrated above.
1168 */
1170 static tree
1173 {
1180 tree incr_stmt;
1181 ssa_op_iter iter;
1182 use_operand_p use_p;
1183 tree new_dataref_ptr;
1195 /* Copy the points-to information if it exists. */
1203 /* Update the vector-pointer's cross-iteration increment. */
1205 {
1210 else
1212 }
1215 }
1218 /* Function vect_create_destination_var.
1220 Create a new temporary of type VECTYPE. */
1222 static tree
1224 {
1225 tree vec_dest;
1227 tree type;
1242 }
1245 /* Function vect_init_vector.
1247 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1248 the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1249 is not NULL. Otherwise, place the initialization at the loop preheader.
1250 Return the DEF of INIT_STMT.
1251 It will be used in the vectorization of STMT. */
1253 static tree
1256 {
1258 tree new_var;
1259 tree init_stmt;
1260 tree vec_oprnd;
1261 edge pe;
1262 tree new_temp;
1263 basic_block new_bb;
1273 else
1274 {
1283 }
1286 {
1289 }
1293 }
1296 /* For constant and loop invariant defs of SLP_NODE this function returns
1297 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1298 OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1299 stmts. */
1301 static void
1304 {
1310 tree vec_cst;
1313 tree vector_type;
1326 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1327 created vectors. It is greater than 1 if unrolling is performed.
1329 For example, we have two scalar operands, s1 and s2 (e.g., group of
1330 strided accesses of size two), while NUINTS is four (i.e., four scalars
1331 of this type can be packed in a vector). The output vector will contain
1332 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1333 will be 2).
1335 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1336 containing the operands.
1338 For example, NUINTS is four as before, and the group size is 8
1339 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1340 {s5, s6, s7, s8}. */
1347 {
1349 {
1353 else
1358 /* Create 'vect_ = {op0,op1,...,opn}'. */
1361 number_of_places_left_in_vector--;
1364 {
1371 else
1376 NULL));
1378 }
1379 }
1380 }
1382 /* Since the vectors are created in the reverse order, we should invert
1383 them. */
1386 {
1389 }
1393 /* In case that VF is greater than the unrolling factor needed for the SLP
1394 group of stmts, NUMBER_OF_VECTORS to be created is greater than
1395 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1396 to replicate the vectors. */
1398 {
1401 }
1402 }
1405 /* Get vectorized definitions from SLP_NODE that contains corresponding
1406 vectorized def-stmts. */
1408 static void
1410 {
1411 tree vec_oprnd;
1412 tree vec_def_stmt;
1419 i++)
1420 {
1424 }
1425 }
1428 /* Get vectorized definitions for SLP_NODE.
1429 If the scalar definitions are loop invariants or constants, collect them and
1430 call vect_get_constant_vectors() to create vector stmts.
1431 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1432 must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1433 vect_get_slp_vect_defs() to retrieve them.
1434 If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1435 the right node. This is used when the second operand must remain scalar. */
1437 static void
1440 {
1443 /* Allocate memory for vectorized defs. */
1447 /* SLP_NODE corresponds either to a group of stores or to a group of
1448 unary/binary operations. We don't call this function for loads. */
1450 /* The defs are already vectorized. */
1452 else
1453 /* Build vectors from scalar defs. */
1458 /* Since we don't call this function with loads, this is a group of
1459 stores. */
1470 /* The defs are already vectorized. */
1472 else
1473 /* Build vectors from scalar defs. */
1475 }
1478 /* Function get_initial_def_for_induction
1480 Input:
1481 STMT - a stmt that performs an induction operation in the loop.
1482 IV_PHI - the initial value of the induction variable
1484 Output:
1485 Return a vector variable, initialized with the first VF values of
1486 the induction variable. E.g., for an iv with IV_PHI='X' and
1487 evolution S, for a vector of 4 units, we want to return:
1488 [X, X + S, X + 2*S, X + 3*S]. */
1490 static tree
1492 {
1497 tree vectype;
1501 basic_block new_bb;
1503 tree access_fn;
1504 tree new_var;
1505 tree new_name;
1506 tree init_stmt;
1513 tree expr;
1516 tree stmts;
1517 imm_use_iterator imm_iter;
1518 use_operand_p use_p;
1519 tree exit_phi;
1520 edge latch_e;
1521 tree loop_arg;
1522 block_stmt_iterator si;
1533 /* Find the first insertion point in the BB. */
1538 else
1541 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
1543 {
1546 }
1547 else
1561 /* Create the vector that holds the initial_value of the induction. */
1563 {
1564 /* iv_loop is nested in the loop to be vectorized. init_expr had already
1565 been created during vectorization of previous stmts; We obtain it from
1566 the STMT_VINFO_VEC_STMT of the defining stmt. */
1569 }
1570 else
1571 {
1572 /* iv_loop is the loop to be vectorized. Create:
1573 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
1579 {
1582 }
1587 {
1588 tree tmp;
1590 /* Create: new_name_i = new_name + step_expr */
1600 {
1603 }
1605 }
1606 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
1609 }
1612 /* Create the vector that holds the step of the induction. */
1614 /* iv_loop is nested in the loop to be vectorized. Generate:
1615 vec_step = [S, S, S, S] */
1617 else
1618 {
1619 /* iv_loop is the loop to be vectorized. Generate:
1620 vec_step = [VF*S, VF*S, VF*S, VF*S] */
1623 }
1633 /* Create the following def-use cycle:
1634 loop prolog:
1635 vec_init = ...
1636 vec_step = ...
1637 loop:
1638 vec_iv = PHI <vec_init, vec_loop>
1639 ...
1640 STMT
1641 ...
1642 vec_loop = vec_iv + vec_step; */
1644 /* Create the induction-phi that defines the induction-operand. */
1652 /* Create the iv update inside the loop */
1662 /* Set the arguments of the phi node: */
1667 /* In case that vectorization factor (VF) is bigger than the number
1668 of elements that we can fit in a vectype (nunits), we have to generate
1669 more than one vector stmt - i.e - we need to "unroll" the
1670 vector stmt by a factor VF/nunits. For more details see documentation
1671 in vectorizable_operation. */
1674 {
1675 stmt_vec_info prev_stmt_vinfo;
1676 /* FORNOW. This restriction should be relaxed. */
1679 /* Create the vector that holds the step of the induction. */
1692 {
1693 tree tmp;
1695 /* vec_i = vec_prev + vec_step */
1705 }
1706 }
1709 {
1710 /* Find the loop-closed exit-phi of the induction, and record
1711 the final vector of induction results: */
1714 {
1716 {
1719 }
1720 }
1722 {
1724 /* FORNOW. Currently not supporting the case that an inner-loop induction
1725 is not used in the outer-loop (i.e. only outside the outer-loop). */
1731 {
1734 }
1735 }
1736 }
1740 {
1745 }
1749 }
1752 /* Function vect_get_vec_def_for_operand.
1754 OP is an operand in STMT. This function returns a (vector) def that will be
1755 used in the vectorized stmt for STMT.
1757 In the case that OP is an SSA_NAME which is defined in the loop, then
1758 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1760 In case OP is an invariant or constant, a new stmt that creates a vector def
1761 needs to be introduced. */
1763 static tree
1765 {
1766 tree vec_oprnd;
1767 tree vec_stmt;
1768 tree def_stmt;
1774 tree vec_inv;
1775 tree vec_cst;
1777 tree def;
1781 tree vector_type;
1784 {
1787 }
1792 {
1794 {
1797 }
1799 {
1802 }
1803 }
1806 {
1807 /* Case 1: operand is a constant. */
1809 {
1813 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1818 {
1820 }
1826 }
1828 /* Case 2: operand is defined outside the loop - loop invariant. */
1830 {
1834 /* Create 'vec_inv = {inv,inv,..,inv}' */
1839 {
1841 }
1843 /* FIXME: use build_constructor directly. */
1848 }
1850 /* Case 3: operand is defined inside the loop. */
1852 {
1856 /* Get the def from the vectorized stmt. */
1862 else
1865 }
1867 /* Case 4: operand is defined by a loop header phi - reduction */
1869 {
1875 /* Get the def before the loop */
1878 }
1880 /* Case 5: operand is defined by loop-header phi - induction. */
1882 {
1885 /* Get the def from the vectorized stmt. */
1891 }
1895 }
1896 }
1899 /* Function vect_get_vec_def_for_stmt_copy
1901 Return a vector-def for an operand. This function is used when the
1902 vectorized stmt to be created (by the caller to this function) is a "copy"
1903 created in case the vectorized result cannot fit in one vector, and several
1904 copies of the vector-stmt are required. In this case the vector-def is
1905 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1906 of the stmt that defines VEC_OPRND.
1907 DT is the type of the vector def VEC_OPRND.
1909 Context:
1910 In case the vectorization factor (VF) is bigger than the number
1911 of elements that can fit in a vectype (nunits), we have to generate
1912 more than one vector stmt to vectorize the scalar stmt. This situation
1913 arises when there are multiple data-types operated upon in the loop; the
1914 smallest data-type determines the VF, and as a result, when vectorizing
1915 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1916 vector stmt (each computing a vector of 'nunits' results, and together
1917 computing 'VF' results in each iteration). This function is called when
1918 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1919 which VF=16 and nunits=4, so the number of copies required is 4):
1921 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
1923 S1: x = load VS1.0: vx.0 = memref0 VS1.1
1924 VS1.1: vx.1 = memref1 VS1.2
1925 VS1.2: vx.2 = memref2 VS1.3
1926 VS1.3: vx.3 = memref3
1928 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
1929 VSnew.1: vz1 = vx.1 + ... VSnew.2
1930 VSnew.2: vz2 = vx.2 + ... VSnew.3
1931 VSnew.3: vz3 = vx.3 + ...
1933 The vectorization of S1 is explained in vectorizable_load.
1934 The vectorization of S2:
1935 To create the first vector-stmt out of the 4 copies - VSnew.0 -
1936 the function 'vect_get_vec_def_for_operand' is called to
1937 get the relevant vector-def for each operand of S2. For operand x it
1938 returns the vector-def 'vx.0'.
1940 To create the remaining copies of the vector-stmt (VSnew.j), this
1941 function is called to get the relevant vector-def for each operand. It is
1942 obtained from the respective VS1.j stmt, which is recorded in the
1943 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
1945 For example, to obtain the vector-def 'vx.1' in order to create the
1946 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
1947 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
1948 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
1949 and return its def ('vx.1').
1950 Overall, to create the above sequence this function will be called 3 times:
1951 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
1952 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
1953 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
1955 static tree
1957 {
1958 tree vec_stmt_for_operand;
1959 stmt_vec_info def_stmt_info;
1961 /* Do nothing; can reuse same def. */
1972 }
1975 /* Get vectorized definitions for the operands to create a copy of an original
1976 stmt. See vect_get_vec_def_for_stmt_copy() for details. */
1978 static void
1982 {
1989 {
1993 }
1994 }
1997 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not NULL. */
1999 static void
2002 {
2005 else
2006 {
2007 tree vec_oprnd;
2014 {
2018 }
2019 }
2020 }
2023 /* Function vect_finish_stmt_generation.
2025 Insert a new stmt. */
2027 static void
2030 {
2043 {
2046 }
2048 /* Make sure bsi points to the stmt that is being vectorized. */
2051 #ifdef USE_MAPPED_LOCATION
2053 #else
2055 #endif
2056 }
2059 /* Function get_initial_def_for_reduction
2061 Input:
2062 STMT - a stmt that performs a reduction operation in the loop.
2063 INIT_VAL - the initial value of the reduction variable
2065 Output:
2066 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2067 of the reduction (used for adjusting the epilog - see below).
2068 Return a vector variable, initialized according to the operation that STMT
2069 performs. This vector will be used as the initial value of the
2070 vector of partial results.
2072 Option1 (adjust in epilog): Initialize the vector as follows:
2073 add: [0,0,...,0,0]
2074 mult: [1,1,...,1,1]
2075 min/max: [init_val,init_val,..,init_val,init_val]
2076 bit and/or: [init_val,init_val,..,init_val,init_val]
2077 and when necessary (e.g. add/mult case) let the caller know
2078 that it needs to adjust the result by init_val.
2080 Option2: Initialize the vector as follows:
2081 add: [0,0,...,0,init_val]
2082 mult: [1,1,...,1,init_val]
2083 min/max: [init_val,init_val,...,init_val]
2084 bit and/or: [init_val,init_val,...,init_val]
2085 and no adjustments are needed.
2087 For example, for the following code:
2089 s = init_val;
2090 for (i=0;i<n;i++)
2091 s = s + a[i];
2093 STMT is 's = s + a[i]', and the reduction variable is 's'.
2094 For a vector of 4 units, we want to return either [0,0,0,init_val],
2095 or [0,0,0,0] and let the caller know that it needs to adjust
2096 the result at the end by 'init_val'.
2098 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2099 initialization vector is simpler (same element in all entries).
2100 A cost model should help decide between these two schemes. */
2102 static tree
2104 {
2112 tree vecdef;
2113 tree def_for_init;
2114 tree init_def;
2117 tree vector_type;
2123 else
2129 {
2135 else
2137 /* Create a vector of zeros for init_def. */
2140 else
2157 }
2160 }
2163 /* Function vect_create_epilog_for_reduction
2165 Create code at the loop-epilog to finalize the result of a reduction
2166 computation.
2168 VECT_DEF is a vector of partial results.
2169 REDUC_CODE is the tree-code for the epilog reduction.
2170 STMT is the scalar reduction stmt that is being vectorized.
2171 REDUCTION_PHI is the phi-node that carries the reduction computation.
2173 This function:
2174 1. Creates the reduction def-use cycle: sets the arguments for
2175 REDUCTION_PHI:
2176 The loop-entry argument is the vectorized initial-value of the reduction.
2177 The loop-latch argument is VECT_DEF - the vector of partial sums.
2178 2. "Reduces" the vector of partial results VECT_DEF into a single result,
2179 by applying the operation specified by REDUC_CODE if available, or by
2180 other means (whole-vector shifts or a scalar loop).
2181 The function also creates a new phi node at the loop exit to preserve
2182 loop-closed form, as illustrated below.
2184 The flow at the entry to this function:
2186 loop:
2187 vec_def = phi <null, null> # REDUCTION_PHI
2188 VECT_DEF = vector_stmt # vectorized form of STMT
2189 s_loop = scalar_stmt # (scalar) STMT
2190 loop_exit:
2191 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2192 use <s_out0>
2193 use <s_out0>
2195 The above is transformed by this function into:
2197 loop:
2198 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2199 VECT_DEF = vector_stmt # vectorized form of STMT
2200 s_loop = scalar_stmt # (scalar) STMT
2201 loop_exit:
2202 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2203 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2204 v_out2 = reduce <v_out1>
2205 s_out3 = extract_field <v_out2, 0>
2206 s_out4 = adjust_result <s_out3>
2207 use <s_out4>
2208 use <s_out4>
2209 */
2211 static void
2214 {
2216 tree vectype;
2220 basic_block exit_bb;
2221 tree scalar_dest;
2222 tree scalar_type;
2223 tree new_phi;
2224 block_stmt_iterator exit_bsi;
2225 tree vec_dest;
2227 tree new_name;
2232 tree adjustment_def;
2233 tree vec_initial_def;
2234 tree orig_name;
2235 imm_use_iterator imm_iter;
2236 use_operand_p use_p;
2239 tree orig_stmt;
2240 tree use_stmt;
2248 {
2251 }
2259 /*** 1. Create the reduction def-use cycle ***/
2261 /* 1.1 set the loop-entry arg of the reduction-phi: */
2262 /* For the case of reduction, vect_get_vec_def_for_operand returns
2263 the scalar def before the loop, that defines the initial value
2264 of the reduction variable. */
2269 /* 1.2 set the loop-latch arg for the reduction-phi: */
2273 {
2278 }
2281 /*** 2. Create epilog code
2282 The reduction epilog code operates across the elements of the vector
2283 of partial results computed by the vectorized loop.
2284 The reduction epilog code consists of:
2285 step 1: compute the scalar result in a vector (v_out2)
2286 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2287 step 3: adjust the scalar result (s_out3) if needed.
2289 Step 1 can be accomplished using one the following three schemes:
2290 (scheme 1) using reduc_code, if available.
2291 (scheme 2) using whole-vector shifts, if available.
2292 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2293 combined.
2295 The overall epilog code looks like this:
2297 s_out0 = phi <s_loop> # original EXIT_PHI
2298 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2299 v_out2 = reduce <v_out1> # step 1
2300 s_out3 = extract_field <v_out2, 0> # step 2
2301 s_out4 = adjust_result <s_out3> # step 3
2303 (step 3 is optional, and step2 1 and 2 may be combined).
2304 Lastly, the uses of s_out0 are replaced by s_out4.
2306 ***/
2308 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2309 v_out1 = phi <v_loop> */
2316 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
2317 (i.e. when reduc_code is not available) and in the final adjustment
2318 code (if needed). Also get the original scalar reduction variable as
2319 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
2320 represents a reduction pattern), the tree-code and scalar-def are
2321 taken from the original stmt that the pattern-stmt (STMT) replaces.
2322 Otherwise (it is a regular reduction) - the tree-code and scalar-def
2323 are taken from STMT. */
2327 {
2328 /* Regular reduction */
2330 }
2331 else
2332 {
2333 /* Reduction pattern */
2337 }
2346 /* In case this is a reduction in an inner-loop while vectorizing an outer
2347 loop - we don't need to extract a single scalar result at the end of the
2348 inner-loop. The final vector of partial results will be used in the
2349 vectorized outer-loop, or reduced to a scalar result at the end of the
2350 outer-loop. */
2354 /* 2.3 Create the reduction code, using one of the three schemes described
2355 above. */
2358 {
2359 tree tmp;
2361 /*** Case 1: Create:
2362 v_out2 = reduc_expr <v_out1> */
2375 }
2376 else
2377 {
2383 tree vec_temp;
2387 else
2390 /* Regardless of whether we have a whole vector shift, if we're
2391 emulating the operation via tree-vect-generic, we don't want
2392 to use it. Only the first round of the reduction is likely
2393 to still be profitable via emulation. */
2394 /* ??? It might be better to emit a reduction tree code here, so that
2395 tree-vect-generic can expand the first round via bit tricks. */
2398 else
2399 {
2403 }
2406 {
2407 /*** Case 2: Create:
2408 for (offset = VS/2; offset >= element_size; offset/=2)
2409 {
2410 Create: va' = vec_shift <va, offset>
2411 Create: va = vop <va, va'>
2412 } */
2423 {
2436 }
2439 }
2440 else
2441 {
2442 tree rhs;
2444 /*** Case 3: Create:
2445 s = extract_field <v_out2, 0>
2446 for (offset = element_size;
2447 offset < vector_size;
2448 offset += element_size;)
2449 {
2450 Create: s' = extract_field <v_out2, offset>
2451 Create: s = op <s, s'>
2452 } */
2460 bitsize_zero_node);
2470 {
2471 tree tmp;
2474 bitpos);
2487 }
2490 }
2491 }
2493 /* 2.4 Extract the final scalar result. Create:
2494 s_out3 = extract_field <v_out2, bitpos> */
2497 {
2498 tree rhs;
2508 else
2517 }
2519 vect_finalize_reduction:
2521 /* 2.5 Adjust the final result by the initial value of the reduction
2522 variable. (When such adjustment is not needed, then
2523 'adjustment_def' is zero). For example, if code is PLUS we create:
2524 new_temp = loop_exit_def + adjustment_def */
2527 {
2529 {
2533 }
2534 else
2535 {
2539 }
2544 }
2547 /* 2.6 Handle the loop-exit phi */
2549 /* Replace uses of s_out0 with uses of s_out3:
2550 Find the loop-closed-use at the loop exit of the original scalar result.
2551 (The reduction result is expected to have two immediate uses - one at the
2552 latch block, and one at the loop exit). */
2555 {
2557 {
2560 }
2561 }
2562 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
2566 {
2568 {
2571 /* FORNOW. Currently not supporting the case that an inner-loop reduction
2572 is not used in the outer-loop (but only outside the outer-loop). */
2581 }
2583 /* Replace the uses: */
2588 }
2590 }
2593 /* Function vectorizable_reduction.
2595 Check if STMT performs a reduction operation that can be vectorized.
2596 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2597 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2598 Return FALSE if not a vectorizable STMT, TRUE otherwise.
2600 This function also handles reduction idioms (patterns) that have been
2601 recognized in advance during vect_pattern_recog. In this case, STMT may be
2602 of this form:
2603 X = pattern_expr (arg0, arg1, ..., X)
2604 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2605 sequence that had been detected and replaced by the pattern-stmt (STMT).
2607 In some cases of reduction patterns, the type of the reduction variable X is
2608 different than the type of the other arguments of STMT.
2609 In such cases, the vectype that is used when transforming STMT into a vector
2610 stmt is different than the vectype that is used to determine the
2611 vectorization factor, because it consists of a different number of elements
2612 than the actual number of elements that are being operated upon in parallel.
2614 For example, consider an accumulation of shorts into an int accumulator.
2615 On some targets it's possible to vectorize this pattern operating on 8
2616 shorts at a time (hence, the vectype for purposes of determining the
2617 vectorization factor should be V8HI); on the other hand, the vectype that
2618 is used to create the vector form is actually V4SI (the type of the result).
2620 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2621 indicates what is the actual level of parallelism (V8HI in the example), so
2622 that the right vectorization factor would be derived. This vectype
2623 corresponds to the type of arguments to the reduction stmt, and should *NOT*
2624 be used to create the vectorized stmt. The right vectype for the vectorized
2625 stmt is obtained from the type of the result X:
2626 get_vectype_for_scalar_type (TREE_TYPE (X))
2628 This means that, contrary to "regular" reductions (or "regular" stmts in
2629 general), the following equation:
2630 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2631 does *NOT* necessarily hold for reduction patterns. */
2633 bool
2635 {
2636 tree vec_dest;
2637 tree scalar_dest;
2638 tree op;
2644 tree operation;
2652 tree new_phi;
2653 tree scalar_type;
2655 tree orig_stmt;
2656 stmt_vec_info orig_stmt_info;
2661 stmt_vec_info prev_stmt_info;
2662 tree reduc_def;
2667 {
2669 /* FORNOW. This restriction should be relaxed. */
2671 {
2675 }
2676 }
2680 /* FORNOW: SLP not supported. */
2684 /* 1. Is vectorizable reduction? */
2686 /* Not supportable if the reduction variable is used in the loop. */
2690 /* Reductions that are not used even in an enclosing outer-loop,
2691 are expected to be "live" (used out of the loop). */
2696 /* Make sure it was already recognized as a reduction computation. */
2700 /* 2. Has this been recognized as a reduction pattern?
2702 Check if STMT represents a pattern that has been recognized
2703 in earlier analysis stages. For stmts that represent a pattern,
2704 the STMT_VINFO_RELATED_STMT field records the last stmt in
2705 the original sequence that constitutes the pattern. */
2709 {
2714 }
2716 /* 3. Check the operands of the operation. The first operands are defined
2717 inside the loop body. The last operand is the reduction variable,
2718 which is defined by the loop-header-phi. */
2733 /* All uses but the last are expected to be defined in the loop.
2734 The last use is the reduction variable. */
2736 {
2745 }
2754 else
2760 /* 4. Supportable by target? */
2762 /* 4.1. check support for the operation in the loop */
2765 {
2769 }
2772 {
2781 }
2783 /* Worthwhile without SIMD support? */
2787 {
2791 }
2793 /* 4.2. Check support for the epilog operation.
2795 If STMT represents a reduction pattern, then the type of the
2796 reduction variable may be different than the type of the rest
2797 of the arguments. For example, consider the case of accumulation
2798 of shorts into an int accumulator; The original code:
2799 S1: int_a = (int) short_a;
2800 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
2802 was replaced with:
2803 STMT: int_acc = widen_sum <short_a, int_acc>
2805 This means that:
2806 1. The tree-code that is used to create the vector operation in the
2807 epilog code (that reduces the partial results) is not the
2808 tree-code of STMT, but is rather the tree-code of the original
2809 stmt from the pattern that STMT is replacing. I.e, in the example
2810 above we want to use 'widen_sum' in the loop, but 'plus' in the
2811 epilog.
2812 2. The type (mode) we use to check available target support
2813 for the vector operation to be created in the *epilog*, is
2814 determined by the type of the reduction variable (in the example
2815 above we'd check this: plus_optab[vect_int_mode]).
2816 However the type (mode) we use to check available target support
2817 for the vector operation to be created *inside the loop*, is
2818 determined by the type of the other arguments to STMT (in the
2819 example we'd check this: widen_sum_optab[vect_short_mode]).
2821 This is contrary to "regular" reductions, in which the types of all
2822 the arguments are the same as the type of the reduction variable.
2823 For "regular" reductions we can therefore use the same vector type
2824 (and also the same tree-code) when generating the epilog code and
2825 when generating the code inside the loop. */
2828 {
2829 /* This is a reduction pattern: get the vectype from the type of the
2830 reduction variable, and get the tree-code from orig_stmt. */
2834 {
2836 {
2839 }
2841 }
2844 }
2845 else
2846 {
2847 /* Regular reduction: use the same vectype and tree-code as used for
2848 the vector code inside the loop can be used for the epilog code. */
2850 }
2856 {
2860 }
2862 {
2866 }
2869 {
2874 }
2876 /** Transform. **/
2881 /* Create the destination vector */
2884 /* Create the reduction-phi that defines the reduction-operand. */
2887 /* In case the vectorization factor (VF) is bigger than the number
2888 of elements that we can fit in a vectype (nunits), we have to generate
2889 more than one vector stmt - i.e - we need to "unroll" the
2890 vector stmt by a factor VF/nunits. For more details see documentation
2891 in vectorizable_operation. */
2895 {
2896 /* Handle uses. */
2898 {
2902 {
2905 }
2907 /* Get the vector def for the reduction variable from the phi node */
2909 }
2910 else
2911 {
2917 /* Get the vector def for the reduction variable from the vectorized
2918 reduction operation generated in the previous iteration (j-1) */
2920 }
2922 /* Arguments are ready. create the new vector stmt. */
2925 else
2927 reduc_def);
2935 else
2938 }
2940 /* Finalize the reduction-phi (set it's arguments) and create the
2941 epilog reduction code. */
2944 }
2946 /* Checks if CALL can be vectorized in type VECTYPE. Returns
2947 a function declaration if the target has a vectorized version
2948 of the function, or NULL_TREE if the function cannot be vectorized. */
2950 tree
2952 {
2956 /* We only handle functions that do not read or clobber memory -- i.e.
2957 const or novops ones. */
2968 vectype_in);
2969 }
2971 /* Function vectorizable_call.
2973 Check if STMT performs a function call that can be vectorized.
2974 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2975 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2976 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2978 bool
2980 {
2981 tree vec_dest;
2982 tree scalar_dest;
2983 tree operation;
2994 tree new_stmt;
2996 call_expr_arg_iterator iter;
2997 tree vargs;
3006 /* FORNOW: SLP not supported. */
3010 /* Is STMT a vectorizable call? */
3021 /* Process function arguments. */
3025 {
3026 /* Bail out if the function has more than two arguments, we
3027 do not have interesting builtin functions to vectorize with
3028 more than two arguments. */
3032 /* We can only handle calls with arguments of the same type. */
3035 {
3039 }
3043 {
3047 }
3050 }
3052 /* No arguments is also not good. */
3067 /* FORNOW */
3074 else
3077 /* For now, we only vectorize functions if a target specific builtin
3078 is available. TODO -- in some cases, it might be profitable to
3079 insert the calls for pieces of the vector, in order to be able
3080 to vectorize other operations in the loop. */
3083 {
3088 }
3094 else
3097 /* Sanity check: make sure that at least one copy of the vectorized stmt
3098 needs to be generated. */
3101 /* FORNOW. This restriction should be relaxed. */
3103 {
3107 }
3110 {
3116 }
3118 /** Transform. **/
3123 /* FORNOW. This restriction should be relaxed. */
3125 {
3129 }
3131 /* Handle def. */
3137 {
3140 {
3141 /* Build argument list for the vectorized call. */
3142 /* FIXME: Rewrite this so that it doesn't
3143 construct a temporary list. */
3147 {
3149 vec_oprnd0
3151 else
3152 vec_oprnd0
3158 }
3170 else
3174 }
3180 {
3181 /* Build argument list for the vectorized call. */
3182 /* FIXME: Rewrite this so that it doesn't
3183 construct a temporary list. */
3187 {
3189 {
3190 vec_oprnd0
3192 vec_oprnd1
3194 }
3195 else
3196 {
3197 vec_oprnd0
3199 vec_oprnd1
3201 }
3207 }
3219 else
3223 }
3230 /* No current target implements this case. */
3232 }
3234 /* The call in STMT might prevent it from being removed in dce.
3235 We however cannot remove it here, due to the way the ssa name
3236 it defines is mapped to the new definition. So just replace
3237 rhs of the statement with something harmless. */
3243 }
3246 /* Function vect_gen_widened_results_half
3248 Create a vector stmt whose code, type, number of arguments, and result
3249 variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are
3250 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
3251 In the case that CODE is a CALL_EXPR, this means that a call to DECL
3252 needs to be created (DECL is a function-decl of a target-builtin).
3253 STMT is the original scalar stmt that we are vectorizing. */
3255 static tree
3259 tree stmt)
3260 {
3261 tree expr;
3262 tree new_stmt;
3263 tree new_temp;
3264 tree sym;
3265 ssa_op_iter iter;
3267 /* Generate half of the widened result: */
3269 {
3270 /* Target specific support */
3273 else
3275 }
3276 else
3277 {
3278 /* Generic support */
3282 else
3284 }
3291 {
3293 {
3297 }
3298 }
3301 }
3304 /* Check if STMT performs a conversion operation, that can be vectorized.
3305 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3306 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3307 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3309 bool
3312 {
3313 tree vec_dest;
3314 tree scalar_dest;
3315 tree operation;
3316 tree op0;
3323 tree new_temp;
3327 stmt_vec_info prev_stmt_info;
3332 tree expr;
3334 tree builtin_decl;
3338 tree vop0;
3340 /* Is STMT a vectorizable conversion? */
3359 /* Check types of lhs and rhs. */
3374 /* FORNOW */
3381 else
3387 /* Bail out if the types are both integral or non-integral. */
3394 else
3397 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3398 this, so we can safely override NCOPIES with 1 here. */
3402 /* Sanity check: make sure that at least one copy of the vectorized stmt
3403 needs to be generated. */
3406 /* FORNOW. This restriction should be relaxed. */
3408 {
3412 }
3414 /* Check the operands of the operation. */
3416 {
3420 }
3422 /* Supportable by target? */
3432 {
3436 }
3439 {
3441 /* FORNOW: SLP not supported. */
3444 }
3447 {
3450 }
3452 /** Transform. **/
3456 /* Handle def. */
3464 {
3467 {
3468 tree sym;
3469 ssa_op_iter iter;
3473 else
3476 builtin_decl =
3479 {
3482 /* Arguments are ready. create the new vector stmt. */
3488 SSA_OP_ALL_VIRTUALS)
3489 {
3493 }
3496 }
3500 else
3503 }
3507 /* In case the vectorization factor (VF) is bigger than the number
3508 of elements that we can fit in a vectype (nunits), we have to
3509 generate more than one vector stmt - i.e - we need to "unroll"
3510 the vector stmt by a factor VF/nunits. */
3512 {
3515 else
3520 /* Generate first half of the widened result: */
3521 new_stmt
3527 else
3531 /* Generate second half of the widened result: */
3532 new_stmt
3538 }
3542 /* In case the vectorization factor (VF) is bigger than the number
3543 of elements that we can fit in a vectype (nunits), we have to
3544 generate more than one vector stmt - i.e - we need to "unroll"
3545 the vector stmt by a factor VF/nunits. */
3547 {
3548 /* Handle uses. */
3550 {
3553 }
3554 else
3555 {
3558 }
3560 /* Arguments are ready. Create the new vector stmt. */
3569 else
3573 }
3576 }
3579 }
3582 /* Function vectorizable_assignment.
3584 Check if STMT performs an assignment (copy) that can be vectorized.
3585 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3586 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3587 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3589 bool
3591 slp_tree slp_node)
3592 {
3593 tree vec_dest;
3594 tree scalar_dest;
3595 tree op;
3599 tree new_temp;
3606 tree vop;
3618 /* Is vectorizable assignment? */
3628 {
3632 }
3635 {
3641 }
3643 /** Transform. **/
3647 /* Handle def. */
3650 /* Handle use. */
3653 /* Arguments are ready. create the new vector stmt. */
3655 {
3664 }
3668 }
3671 /* Function vect_min_worthwhile_factor.
3673 For a loop where we could vectorize the operation indicated by CODE,
3674 return the minimum vectorization factor that makes it worthwhile
3675 to use generic vectors. */
3676 static int
3678 {
3680 {
3694 }
3695 }
3698 /* Function vectorizable_induction
3700 Check if PHI performs an induction computation that can be vectorized.
3701 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3702 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3703 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3705 bool
3708 {
3714 tree vec_def;
3721 /* FORNOW: SLP not supported. */
3731 {
3737 }
3739 /** Transform. **/
3747 }
3750 /* Function vectorizable_operation.
3752 Check if STMT performs a binary or unary operation that can be vectorized.
3753 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3754 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3755 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3757 bool
3759 slp_tree slp_node)
3760 {
3761 tree vec_dest;
3762 tree scalar_dest;
3763 tree operation;
3772 tree new_temp;
3774 optab optab;
3780 stmt_vec_info prev_stmt_info;
3783 tree vectype_out;
3791 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3792 this, so we can safely override NCOPIES with 1 here. */
3796 /* FORNOW. This restriction should be relaxed. */
3798 {
3802 }
3810 /* Is STMT a vectorizable binary/unary operation? */
3828 /* For pointer addition, we should use the normal plus for
3829 the vector addition. */
3835 /* Support only unary or binary operations. */
3838 {
3842 }
3846 {
3850 }
3853 {
3856 {
3860 }
3861 }
3863 /* Supportable by target? */
3865 {
3869 }
3873 {
3876 /* Check only during analysis. */
3884 }
3886 /* Worthwhile without SIMD support? Check only during analysis. */
3891 {
3895 }
3898 {
3899 /* FORNOW: not yet supported. */
3903 /* Invariant argument is needed for a vector shift
3904 by a scalar shift operand. */
3907 {
3909 {
3914 }
3917 }
3918 }
3921 {
3927 }
3929 /** Transform. **/
3934 /* Handle def. */
3937 /* Allocate VECs for vector operands. In case of SLP, vector operands are
3938 created in the previous stages of the recursion, so no allocation is
3939 needed, except for the case of shift with scalar shift argument. In that
3940 case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
3941 be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
3942 In case of loop-based vectorization we allocate VECs of size 1. We
3943 allocate VEC_OPRNDS1 only in case of binary operation. */
3945 {
3949 }
3953 /* In case the vectorization factor (VF) is bigger than the number
3954 of elements that we can fit in a vectype (nunits), we have to generate
3955 more than one vector stmt - i.e - we need to "unroll" the
3956 vector stmt by a factor VF/nunits. In doing so, we record a pointer
3957 from one copy of the vector stmt to the next, in the field
3958 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3959 stages to find the correct vector defs to be used when vectorizing
3960 stmts that use the defs of the current stmt. The example below illustrates
3961 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3962 4 vectorized stmts):
3964 before vectorization:
3965 RELATED_STMT VEC_STMT
3966 S1: x = memref - -
3967 S2: z = x + 1 - -
3969 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
3970 there):
3971 RELATED_STMT VEC_STMT
3972 VS1_0: vx0 = memref0 VS1_1 -
3973 VS1_1: vx1 = memref1 VS1_2 -
3974 VS1_2: vx2 = memref2 VS1_3 -
3975 VS1_3: vx3 = memref3 - -
3976 S1: x = load - VS1_0
3977 S2: z = x + 1 - -
3979 step2: vectorize stmt S2 (done here):
3980 To vectorize stmt S2 we first need to find the relevant vector
3981 def for the first operand 'x'. This is, as usual, obtained from
3982 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
3983 that defines 'x' (S1). This way we find the stmt VS1_0, and the
3984 relevant vector def 'vx0'. Having found 'vx0' we can generate
3985 the vector stmt VS2_0, and as usual, record it in the
3986 STMT_VINFO_VEC_STMT of stmt S2.
3987 When creating the second copy (VS2_1), we obtain the relevant vector
3988 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
3989 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
3990 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
3991 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
3992 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
3993 chain of stmts and pointers:
3994 RELATED_STMT VEC_STMT
3995 VS1_0: vx0 = memref0 VS1_1 -
3996 VS1_1: vx1 = memref1 VS1_2 -
3997 VS1_2: vx2 = memref2 VS1_3 -
3998 VS1_3: vx3 = memref3 - -
3999 S1: x = load - VS1_0
4000 VS2_0: vz0 = vx0 + v1 VS2_1 -
4001 VS2_1: vz1 = vx1 + v1 VS2_2 -
4002 VS2_2: vz2 = vx2 + v1 VS2_3 -
4003 VS2_3: vz3 = vx3 + v1 - -
4004 S2: z = x + 1 - VS2_0 */
4008 {
4009 /* Handle uses. */
4011 {
4014 {
4015 /* Vector shl and shr insn patterns can be defined with scalar
4016 operand 2 (shift operand). In this case, use constant or loop
4017 invariant op1 directly, without extending it to vector mode
4018 first. */
4021 {
4027 {
4028 /* Store vec_oprnd1 for every vector stmt to be created
4029 for SLP_NODE. We check during the analysis that all the
4030 shift arguments are the same.
4031 TODO: Allow different constants for different vector
4032 stmts generated for an SLP instance. */
4035 }
4036 }
4037 }
4039 /* vec_oprnd1 is available if operand 1 should be of a scalar-type
4040 (a special case for certain kind of vector shifts); otherwise,
4041 operand 1 should be of a vector type (the usual case). */
4044 slp_node);
4045 else
4047 slp_node);
4048 }
4049 else
4052 /* Arguments are ready. Create the new vector stmt. */
4054 {
4056 {
4060 }
4061 else
4070 }
4074 else
4077 }
4084 }
4087 /* Function vectorizable_type_demotion
4089 Check if STMT performs a binary or unary operation that involves
4090 type demotion, and if it can be vectorized.
4091 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4092 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4093 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4095 bool
4098 {
4099 tree vec_dest;
4100 tree scalar_dest;
4101 tree operation;
4102 tree op0;
4108 tree new_temp;
4111 tree new_stmt;
4112 stmt_vec_info prev_stmt_info;
4115 tree vectype_out;
4118 tree expr;
4119 tree vectype_in;
4127 /* Is STMT a vectorizable type-demotion operation? */
4155 /* FORNOW. This restriction should be relaxed. */
4157 {
4161 }
4170 /* Check the operands of the operation. */
4172 {
4176 }
4178 /* Supportable by target? */
4185 {
4191 }
4193 /** Transform. **/
4196 ncopies);
4198 /* Handle def. */
4201 /* In case the vectorization factor (VF) is bigger than the number
4202 of elements that we can fit in a vectype (nunits), we have to generate
4203 more than one vector stmt - i.e - we need to "unroll" the
4204 vector stmt by a factor VF/nunits. */
4207 {
4208 /* Handle uses. */
4210 {
4213 }
4214 else
4215 {
4218 }
4220 /* Arguments are ready. Create the new vector stmt. */
4229 else
4233 }
4237 }
4240 /* Function vectorizable_type_promotion
4242 Check if STMT performs a binary or unary operation that involves
4243 type promotion, and if it can be vectorized.
4244 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4245 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4246 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4248 bool
4251 {
4252 tree vec_dest;
4253 tree scalar_dest;
4254 tree operation;
4265 tree new_stmt;
4266 stmt_vec_info prev_stmt_info;
4269 tree vectype_out;
4272 tree vectype_in;
4280 /* Is STMT a vectorizable type-promotion operation? */
4309 /* FORNOW. This restriction should be relaxed. */
4311 {
4315 }
4324 /* Check the operands of the operation. */
4326 {
4330 }
4334 {
4337 {
4341 }
4342 }
4344 /* Supportable by target? */
4352 {
4358 }
4360 /** Transform. **/
4364 ncopies);
4366 /* Handle def. */
4369 /* In case the vectorization factor (VF) is bigger than the number
4370 of elements that we can fit in a vectype (nunits), we have to generate
4371 more than one vector stmt - i.e - we need to "unroll" the
4372 vector stmt by a factor VF/nunits. */
4376 {
4377 /* Handle uses. */
4379 {
4383 }
4384 else
4385 {
4389 }
4391 /* Arguments are ready. Create the new vector stmt. We are creating
4392 two vector defs because the widened result does not fit in one vector.
4393 The vectorized stmt can be expressed as a call to a taregt builtin,
4394 or a using a tree-code. */
4395 /* Generate first half of the widened result: */
4400 else
4404 /* Generate second half of the widened result: */
4410 }
4414 }
4417 /* Function vect_strided_store_supported.
4419 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
4420 and FALSE otherwise. */
4422 static bool
4424 {
4430 /* Check that the operation is supported. */
4432 vectype);
4434 vectype);
4436 {
4440 }
4443 == CODE_FOR_nothing
4446 {
4450 }
4453 }
4456 /* Function vect_permute_store_chain.
4458 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4459 a power of 2, generate interleave_high/low stmts to reorder the data
4460 correctly for the stores. Return the final references for stores in
4461 RESULT_CHAIN.
4463 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4464 The input is 4 vectors each containing 8 elements. We assign a number to each
4465 element, the input sequence is:
4467 1st vec: 0 1 2 3 4 5 6 7
4468 2nd vec: 8 9 10 11 12 13 14 15
4469 3rd vec: 16 17 18 19 20 21 22 23
4470 4th vec: 24 25 26 27 28 29 30 31
4472 The output sequence should be:
4474 1st vec: 0 8 16 24 1 9 17 25
4475 2nd vec: 2 10 18 26 3 11 19 27
4476 3rd vec: 4 12 20 28 5 13 21 30
4477 4th vec: 6 14 22 30 7 15 23 31
4479 i.e., we interleave the contents of the four vectors in their order.
4481 We use interleave_high/low instructions to create such output. The input of
4482 each interleave_high/low operation is two vectors:
4483 1st vec 2nd vec
4484 0 1 2 3 4 5 6 7
4485 the even elements of the result vector are obtained left-to-right from the
4486 high/low elements of the first vector. The odd elements of the result are
4487 obtained left-to-right from the high/low elements of the second vector.
4488 The output of interleave_high will be: 0 4 1 5
4489 and of interleave_low: 2 6 3 7
4492 The permutation is done in log LENGTH stages. In each stage interleave_high
4493 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4494 where the first argument is taken from the first half of DR_CHAIN and the
4495 second argument from it's second half.
4496 In our example,
4498 I1: interleave_high (1st vec, 3rd vec)
4499 I2: interleave_low (1st vec, 3rd vec)
4500 I3: interleave_high (2nd vec, 4th vec)
4501 I4: interleave_low (2nd vec, 4th vec)
4503 The output for the first stage is:
4505 I1: 0 16 1 17 2 18 3 19
4506 I2: 4 20 5 21 6 22 7 23
4507 I3: 8 24 9 25 10 26 11 27
4508 I4: 12 28 13 29 14 30 15 31
4510 The output of the second stage, i.e. the final result is:
4512 I1: 0 8 16 24 1 9 17 25
4513 I2: 2 10 18 26 3 11 19 27
4514 I3: 4 12 20 28 5 13 21 30
4515 I4: 6 14 22 30 7 15 23 31. */
4517 static bool
4520 tree stmt,
4523 {
4535 /* Check that the operation is supported. */
4542 {
4544 {
4548 /* Create interleaving stmt:
4549 in the case of big endian:
4550 high = interleave_high (vect1, vect2)
4551 and in the case of little endian:
4552 high = interleave_low (vect1, vect2). */
4558 else
4566 /* Create interleaving stmt:
4567 in the case of big endian:
4568 low = interleave_low (vect1, vect2)
4569 and in the case of little endian:
4570 low = interleave_high (vect1, vect2). */
4576 else
4583 }
4585 }
4587 }
4590 /* Function vectorizable_store.
4592 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
4593 can be vectorized.
4594 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4595 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4596 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4598 bool
4600 slp_tree slp_node)
4601 {
4602 tree scalar_dest;
4603 tree data_ref;
4604 tree op;
4612 tree dummy;
4628 stmt_vec_info first_stmt_vinfo;
4631 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
4632 this, so we can safely override NCOPIES with 1 here. */
4638 /* FORNOW. This restriction should be relaxed. */
4640 {
4644 }
4652 /* Is vectorizable store? */
4665 {
4669 }
4672 /* FORNOW. In some cases can vectorize even if data-type not supported
4673 (e.g. - array initialization with 0). */
4681 {
4689 {
4690 /* STMT is the leader of the group. Check the operands of all the
4691 stmts of the group. */
4694 {
4697 {
4701 }
4703 }
4704 }
4705 }
4708 {
4713 }
4715 /** Transform. **/
4718 {
4724 /* FORNOW */
4727 /* We vectorize all the stmts of the interleaving group when we
4728 reach the last stmt in the group. */
4732 {
4735 }
4740 /* VEC_NUM is the number of vect stmts to be created for this group. */
4743 else
4745 }
4746 else
4747 {
4752 }
4764 /* In case the vectorization factor (VF) is bigger than the number
4765 of elements that we can fit in a vectype (nunits), we have to generate
4766 more than one vector stmt - i.e - we need to "unroll" the
4767 vector stmt by a factor VF/nunits. For more details see documentation in
4768 vect_get_vec_def_for_copy_stmt. */
4770 /* In case of interleaving (non-unit strided access):
4772 S1: &base + 2 = x2
4773 S2: &base = x0
4774 S3: &base + 1 = x1
4775 S4: &base + 3 = x3
4777 We create vectorized stores starting from base address (the access of the
4778 first stmt in the chain (S2 in the above example), when the last store stmt
4779 of the chain (S4) is reached:
4781 VS1: &base = vx2
4782 VS2: &base + vec_size*1 = vx0
4783 VS3: &base + vec_size*2 = vx1
4784 VS4: &base + vec_size*3 = vx3
4786 Then permutation statements are generated:
4788 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
4789 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
4790 ...
4792 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
4793 (the order of the data-refs in the output of vect_permute_store_chain
4794 corresponds to the order of scalar stmts in the interleaving chain - see
4795 the documentation of vect_permute_store_chain()).
4797 In case of both multiple types and interleaving, above vector stores and
4798 permutation stmts are created for every copy. The result vector stmts are
4799 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
4800 STMT_VINFO_RELATED_STMT for the next copies.
4801 */
4805 {
4806 tree new_stmt;
4807 tree ptr_incr;
4810 {
4812 {
4813 /* Get vectorized arguments for SLP_NODE. */
4817 }
4818 else
4819 {
4820 /* For interleaved stores we collect vectorized defs for all the
4821 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
4822 used as an input to vect_permute_store_chain(), and OPRNDS as
4823 an input to vect_get_vec_def_for_stmt_copy() for the next copy.
4825 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4826 OPRNDS are of size 1. */
4829 {
4830 /* Since gaps are not supported for interleaved stores,
4831 GROUP_SIZE is the exact number of stmts in the chain.
4832 Therefore, NEXT_STMT can't be NULL_TREE. In case that
4833 there is no interleaving, GROUP_SIZE is 1, and only one
4834 iteration of the loop will be executed. */
4839 NULL);
4843 }
4844 }
4849 }
4850 else
4851 {
4852 /* FORNOW SLP doesn't work for multiple types. */
4855 /* For interleaved stores we created vectorized defs for all the
4856 defs stored in OPRNDS in the previous iteration (previous copy).
4857 DR_CHAIN is then used as an input to vect_permute_store_chain(),
4858 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
4859 next copy.
4860 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4861 OPRNDS are of size 1. */
4863 {
4869 }
4870 dataref_ptr =
4872 }
4875 {
4877 /* Permute. */
4881 }
4885 {
4887 /* Bump the vector pointer. */
4889 NULL_TREE);
4894 /* For strided stores vectorized defs are interleaved in
4895 vect_permute_store_chain(). */
4899 /* Arguments are ready. Create the new vector stmt. */
4906 else
4913 }
4914 }
4917 }
4920 /* Function vect_setup_realignment
4922 This function is called when vectorizing an unaligned load using
4923 the dr_explicit_realign[_optimized] scheme.
4924 This function generates the following code at the loop prolog:
4926 p = initial_addr;
4927 x msq_init = *(floor(p)); # prolog load
4928 realignment_token = call target_builtin;
4929 loop:
4930 x msq = phi (msq_init, ---)
4932 The stmts marked with x are generated only for the case of
4933 dr_explicit_realign_optimized.
4935 The code above sets up a new (vector) pointer, pointing to the first
4936 location accessed by STMT, and a "floor-aligned" load using that pointer.
4937 It also generates code to compute the "realignment-token" (if the relevant
4938 target hook was defined), and creates a phi-node at the loop-header bb
4939 whose arguments are the result of the prolog-load (created by this
4940 function) and the result of a load that takes place in the loop (to be
4941 created by the caller to this function).
4943 For the case of dr_explicit_realign_optimized:
4944 The caller to this function uses the phi-result (msq) to create the
4945 realignment code inside the loop, and sets up the missing phi argument,
4946 as follows:
4947 loop:
4948 msq = phi (msq_init, lsq)
4949 lsq = *(floor(p')); # load in loop
4950 result = realign_load (msq, lsq, realignment_token);
4952 For the case of dr_explicit_realign:
4953 loop:
4954 msq = *(floor(p)); # load in loop
4955 p' = p + (VS-1);
4956 lsq = *(floor(p')); # load in loop
4957 result = realign_load (msq, lsq, realignment_token);
4959 Input:
4960 STMT - (scalar) load stmt to be vectorized. This load accesses
4961 a memory location that may be unaligned.
4962 BSI - place where new code is to be inserted.
4963 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
4964 is used.
4966 Output:
4967 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4968 target hook, if defined.
4969 Return value - the result of the loop-header phi node. */
4971 static tree
4975 tree init_addr,
4977 {
4982 edge pe;
4984 tree vec_dest;
4985 tree inc;
4986 tree ptr;
4987 tree data_ref;
4988 tree new_stmt;
4989 basic_block new_bb;
4991 tree new_temp;
4992 tree phi_stmt;
5004 /* We need to generate three things:
5005 1. the misalignment computation
5006 2. the extra vector load (for the optimized realignment scheme).
5007 3. the phi node for the two vectors from which the realignment is
5008 done (for the optimized realignment scheme).
5009 */
5011 /* 1. Determine where to generate the misalignment computation.
5013 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
5014 calculation will be generated by this function, outside the loop (in the
5015 preheader). Otherwise, INIT_ADDR had already been computed for us by the
5016 caller, inside the loop.
5018 Background: If the misalignment remains fixed throughout the iterations of
5019 the loop, then both realignment schemes are applicable, and also the
5020 misalignment computation can be done outside LOOP. This is because we are
5021 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
5022 are a multiple of VS (the Vector Size), and therefore the misalignment in
5023 different vectorized LOOP iterations is always the same.
5024 The problem arises only if the memory access is in an inner-loop nested
5025 inside LOOP, which is now being vectorized using outer-loop vectorization.
5026 This is the only case when the misalignment of the memory access may not
5027 remain fixed throughout the iterations of the inner-loop (as explained in
5028 detail in vect_supportable_dr_alignment). In this case, not only is the
5029 optimized realignment scheme not applicable, but also the misalignment
5030 computation (and generation of the realignment token that is passed to
5031 REALIGN_LOAD) have to be done inside the loop.
5033 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
5034 or not, which in turn determines if the misalignment is computed inside
5035 the inner-loop, or outside LOOP. */
5038 {
5041 }
5044 /* 2. Determine where to generate the extra vector load.
5046 For the optimized realignment scheme, instead of generating two vector
5047 loads in each iteration, we generate a single extra vector load in the
5048 preheader of the loop, and in each iteration reuse the result of the
5049 vector load from the previous iteration. In case the memory access is in
5050 an inner-loop nested inside LOOP, which is now being vectorized using
5051 outer-loop vectorization, we need to determine whether this initial vector
5052 load should be generated at the preheader of the inner-loop, or can be
5053 generated at the preheader of LOOP. If the memory access has no evolution
5054 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
5055 to be generated inside LOOP (in the preheader of the inner-loop). */
5058 {
5063 }
5064 else
5069 /* 3. For the case of the optimized realignment, create the first vector
5070 load at the loop preheader. */
5073 {
5074 /* Create msq_init = *(floor(p1)) in the loop preheader */
5088 }
5090 /* 4. Create realignment token using a target builtin, if available.
5091 It is done either inside the containing loop, or before LOOP (as
5092 determined above). */
5095 {
5096 tree builtin_decl;
5098 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
5101 else
5102 {
5103 /* Generate the INIT_ADDR computation outside LOOP. */
5109 }
5121 else
5122 {
5123 /* Generate the misalignment computation outside LOOP. */
5127 }
5131 /* The result of the CALL_EXPR to this builtin is determined from
5132 the value of the parameter and no global variables are touched
5133 which makes the builtin a "const" function. Requiring the
5134 builtin to have the "const" attribute makes it unnecessary
5135 to call mark_call_clobbered. */
5137 }
5146 /* 5. Create msq = phi <msq_init, lsq> in loop */
5156 }
5159 /* Function vect_strided_load_supported.
5161 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
5162 and FALSE otherwise. */
5164 static bool
5166 {
5174 {
5178 }
5181 {
5185 }
5189 {
5193 }
5196 {
5200 }
5202 }
5205 /* Function vect_permute_load_chain.
5207 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
5208 a power of 2, generate extract_even/odd stmts to reorder the input data
5209 correctly. Return the final references for loads in RESULT_CHAIN.
5211 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
5212 The input is 4 vectors each containing 8 elements. We assign a number to each
5213 element, the input sequence is:
5215 1st vec: 0 1 2 3 4 5 6 7
5216 2nd vec: 8 9 10 11 12 13 14 15
5217 3rd vec: 16 17 18 19 20 21 22 23
5218 4th vec: 24 25 26 27 28 29 30 31
5220 The output sequence should be:
5222 1st vec: 0 4 8 12 16 20 24 28
5223 2nd vec: 1 5 9 13 17 21 25 29
5224 3rd vec: 2 6 10 14 18 22 26 30
5225 4th vec: 3 7 11 15 19 23 27 31
5227 i.e., the first output vector should contain the first elements of each
5228 interleaving group, etc.
5230 We use extract_even/odd instructions to create such output. The input of each
5231 extract_even/odd operation is two vectors
5232 1st vec 2nd vec
5233 0 1 2 3 4 5 6 7
5235 and the output is the vector of extracted even/odd elements. The output of
5236 extract_even will be: 0 2 4 6
5237 and of extract_odd: 1 3 5 7
5240 The permutation is done in log LENGTH stages. In each stage extract_even and
5241 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
5242 order. In our example,
5244 E1: extract_even (1st vec, 2nd vec)
5245 E2: extract_odd (1st vec, 2nd vec)
5246 E3: extract_even (3rd vec, 4th vec)
5247 E4: extract_odd (3rd vec, 4th vec)
5249 The output for the first stage will be:
5251 E1: 0 2 4 6 8 10 12 14
5252 E2: 1 3 5 7 9 11 13 15
5253 E3: 16 18 20 22 24 26 28 30
5254 E4: 17 19 21 23 25 27 29 31
5256 In order to proceed and create the correct sequence for the next stage (or
5257 for the correct output, if the second stage is the last one, as in our
5258 example), we first put the output of extract_even operation and then the
5259 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
5260 The input for the second stage is:
5262 1st vec (E1): 0 2 4 6 8 10 12 14
5263 2nd vec (E3): 16 18 20 22 24 26 28 30
5264 3rd vec (E2): 1 3 5 7 9 11 13 15
5265 4th vec (E4): 17 19 21 23 25 27 29 31
5267 The output of the second stage:
5269 E1: 0 4 8 12 16 20 24 28
5270 E2: 2 6 10 14 18 22 26 30
5271 E3: 1 5 9 13 17 21 25 29
5272 E4: 3 7 11 15 19 23 27 31
5274 And RESULT_CHAIN after reordering:
5276 1st vec (E1): 0 4 8 12 16 20 24 28
5277 2nd vec (E3): 1 5 9 13 17 21 25 29
5278 3rd vec (E2): 2 6 10 14 18 22 26 30
5279 4th vec (E4): 3 7 11 15 19 23 27 31. */
5281 static bool
5284 tree stmt,
5287 {
5290 tree tmp;
5294 /* Check that the operation is supported. */
5300 {
5302 {
5306 /* data_ref = permute_even (first_data_ref, second_data_ref); */
5322 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
5336 }
5338 }
5340 }
5343 /* Function vect_transform_strided_load.
5345 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
5346 to perform their permutation and ascribe the result vectorized statements to
5347 the scalar statements.
5348 */
5350 static bool
5353 {
5359 tree tmp_data_ref;
5361 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
5362 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
5363 vectors, that are ready for vector computation. */
5365 /* Permute. */
5369 /* Put a permuted data-ref in the VECTORIZED_STMT field.
5370 Since we scan the chain starting from it's first node, their order
5371 corresponds the order of data-refs in RESULT_CHAIN. */
5375 {
5379 /* Skip the gaps. Loads created for the gaps will be removed by dead
5380 code elimination pass later.
5381 DR_GROUP_GAP is the number of steps in elements from the previous
5382 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
5383 correspond to the gaps.
5384 */
5386 {
5387 gap_count++;
5389 }
5392 {
5394 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
5395 copies, and we put the new vector statement in the first available
5396 RELATED_STMT. */
5399 else
5400 {
5405 {
5408 }
5410 }
5413 /* If NEXT_STMT accesses the same DR as the previous statement,
5414 put the same TMP_DATA_REF as its vectorized statement; otherwise
5415 get the next data-ref from RESULT_CHAIN. */
5418 }
5419 }
5421 }
5424 /* vectorizable_load.
5426 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
5427 can be vectorized.
5428 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5429 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5430 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5432 bool
5434 slp_tree slp_node)
5435 {
5436 tree scalar_dest;
5439 tree op;
5441 stmt_vec_info prev_stmt_info;
5448 tree new_temp;
5451 tree dummy;
5454 tree ptr_incr;
5464 tree first_stmt;
5465 tree scalar_type;
5472 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
5473 this, so we can safely override NCOPIES with 1 here. */
5479 /* FORNOW. This restriction should be relaxed. */
5481 {
5485 }
5493 /* Is vectorizable load? */
5513 /* FORNOW. In some cases can vectorize even if data-type not supported
5514 (e.g. - data copies). */
5516 {
5520 }
5522 /* Check if the load is a part of an interleaving chain. */
5524 {
5526 /* FORNOW */
5529 /* Check if interleaving is supported. */
5533 }
5536 {
5540 }
5545 /** Transform. **/
5548 {
5550 /* Check if the chain of loads is already vectorized. */
5552 {
5555 }
5560 /* VEC_NUM is the number of vect stmts to be created for this group. */
5562 {
5565 }
5566 else
5568 }
5569 else
5570 {
5574 }
5579 /* In case the vectorization factor (VF) is bigger than the number
5580 of elements that we can fit in a vectype (nunits), we have to generate
5581 more than one vector stmt - i.e - we need to "unroll" the
5582 vector stmt by a factor VF/nunits. In doing so, we record a pointer
5583 from one copy of the vector stmt to the next, in the field
5584 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
5585 stages to find the correct vector defs to be used when vectorizing
5586 stmts that use the defs of the current stmt. The example below illustrates
5587 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
5588 4 vectorized stmts):
5590 before vectorization:
5591 RELATED_STMT VEC_STMT
5592 S1: x = memref - -
5593 S2: z = x + 1 - -
5595 step 1: vectorize stmt S1:
5596 We first create the vector stmt VS1_0, and, as usual, record a
5597 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
5598 Next, we create the vector stmt VS1_1, and record a pointer to
5599 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
5600 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
5601 stmts and pointers:
5602 RELATED_STMT VEC_STMT
5603 VS1_0: vx0 = memref0 VS1_1 -
5604 VS1_1: vx1 = memref1 VS1_2 -
5605 VS1_2: vx2 = memref2 VS1_3 -
5606 VS1_3: vx3 = memref3 - -
5607 S1: x = load - VS1_0
5608 S2: z = x + 1 - -
5610 See in documentation in vect_get_vec_def_for_stmt_copy for how the
5611 information we recorded in RELATED_STMT field is used to vectorize
5612 stmt S2. */
5614 /* In case of interleaving (non-unit strided access):
5616 S1: x2 = &base + 2
5617 S2: x0 = &base
5618 S3: x1 = &base + 1
5619 S4: x3 = &base + 3
5621 Vectorized loads are created in the order of memory accesses
5622 starting from the access of the first stmt of the chain:
5624 VS1: vx0 = &base
5625 VS2: vx1 = &base + vec_size*1
5626 VS3: vx3 = &base + vec_size*2
5627 VS4: vx4 = &base + vec_size*3
5629 Then permutation statements are generated:
5631 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
5632 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
5633 ...
5635 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
5636 (the order of the data-refs in the output of vect_permute_load_chain
5637 corresponds to the order of scalar stmts in the interleaving chain - see
5638 the documentation of vect_permute_load_chain()).
5639 The generation of permutation stmts and recording them in
5640 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
5642 In case of both multiple types and interleaving, the vector loads and
5643 permutation stmts above are created for every copy. The result vector stmts
5644 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
5645 STMT_VINFO_RELATED_STMT for the next copies. */
5647 /* If the data reference is aligned (dr_aligned) or potentially unaligned
5648 on a target that supports unaligned accesses (dr_unaligned_supported)
5649 we generate the following code:
5650 p = initial_addr;
5651 indx = 0;
5652 loop {
5653 p = p + indx * vectype_size;
5654 vec_dest = *(p);
5655 indx = indx + 1;
5656 }
5658 Otherwise, the data reference is potentially unaligned on a target that
5659 does not support unaligned accesses (dr_explicit_realign_optimized) -
5660 then generate the following code, in which the data in each iteration is
5661 obtained by two vector loads, one from the previous iteration, and one
5662 from the current iteration:
5663 p1 = initial_addr;
5664 msq_init = *(floor(p1))
5665 p2 = initial_addr + VS - 1;
5666 realignment_token = call target_builtin;
5667 indx = 0;
5668 loop {
5669 p2 = p2 + indx * vectype_size
5670 lsq = *(floor(p2))
5671 vec_dest = realign_load (msq, lsq, realignment_token)
5672 indx = indx + 1;
5673 msq = lsq;
5674 } */
5676 /* If the misalignment remains the same throughout the execution of the
5677 loop, we can create the init_addr and permutation mask at the loop
5678 preheader. Otherwise, it needs to be created inside the loop.
5679 This can only occur when vectorizing memory accesses in the inner-loop
5680 nested within an outer-loop that is being vectorized. */
5684 {
5687 }
5692 {
5697 {
5700 }
5701 }
5702 else
5707 {
5708 /* 1. Create the vector pointer update chain. */
5714 else
5715 dataref_ptr =
5719 {
5722 NULL_TREE);
5724 /* 2. Create the vector-load in the loop. */
5726 {
5732 {
5737 data_ref =
5740 }
5742 {
5749 dr_explicit_realign,
5767 }
5773 }
5781 /* 3. Handle explicit realignment if necessary/supported. Create in
5782 loop: vec_dest = realign_load (msq, lsq, realignment_token) */
5785 {
5791 realignment_token);
5798 {
5802 }
5803 }
5805 /* 4. Handle invariant-load. */
5807 {
5811 {
5816 /* CHECKME: bitpos depends on endianess? */
5822 vec_dest =
5831 /* FIXME: use build_constructor directly. */
5835 }
5836 else
5838 }
5840 /* Collect vector loads and later create their permutation in
5841 vect_transform_strided_load (). */
5845 /* Store vector loads in the corresponding SLP_NODE. */
5848 }
5850 /* FORNOW: SLP with multiple types is unsupported. */
5855 {
5860 }
5861 else
5862 {
5865 else
5868 }
5869 }
5872 }
5875 /* Function vectorizable_live_operation.
5877 STMT computes a value that is used outside the loop. Check if
5878 it can be supported. */
5880 bool
5884 {
5885 tree operation;
5891 tree op;
5906 /* FORNOW. CHECKME. */
5913 /* FORNOW: support only if all uses are invariant. This means
5914 that the scalar operations can remain in place, unvectorized.
5915 The original last scalar value that they compute will be used. */
5918 {
5921 {
5925 }
5929 }
5931 /* No transformation is required for the cases we currently support. */
5933 }
5936 /* Function vect_is_simple_cond.
5938 Input:
5939 LOOP - the loop that is being vectorized.
5940 COND - Condition that is checked for simple use.
5942 Returns whether a COND can be vectorized. Checks whether
5943 condition operands are supportable using vec_is_simple_use. */
5945 static bool
5947 {
5949 tree def;
5959 {
5963 }
5969 {
5973 }
5979 }
5981 /* vectorizable_condition.
5983 Check if STMT is conditional modify expression that can be vectorized.
5984 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5985 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
5986 at BSI.
5988 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5990 bool
5992 {
6001 tree new_temp;
6004 tree def;
6019 /* FORNOW: SLP not supported. */
6023 /* FORNOW: not yet supported. */
6025 {
6029 }
6031 /* Is vectorizable conditional operation? */
6047 /* We do not handle two different vector types for the condition
6048 and the values. */
6053 {
6058 }
6065 {
6070 }
6080 {
6083 }
6085 /* Transform */
6087 /* Handle def. */
6091 /* Handle cond expr. */
6092 vec_cond_lhs =
6094 vec_cond_rhs =
6099 /* Arguments are ready. create the new vector stmt. */
6111 }
6114 /* Function vect_transform_stmt.
6116 Create a vectorized stmt to replace STMT, and insert it at BSI. */
6118 static bool
6120 slp_tree slp_node)
6121 {
6125 tree orig_stmt_in_pattern;
6129 {
6172 {
6173 /* In case of interleaving, the whole chain is vectorized when the
6174 last store in the chain is reached. Store stmts before the last
6175 one are skipped, and there vec_stmt_info shouldn't be freed
6176 meanwhile. */
6180 }
6181 else
6204 {
6208 }
6209 }
6213 {
6216 }
6219 {
6223 {
6225 /* STMT was inserted by the vectorizer to replace a computation idiom.
6226 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
6227 computed this idiom. We need to record a pointer to VEC_STMT in
6228 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
6229 documentation of vect_pattern_recog. */
6231 {
6234 }
6235 }
6236 }
6239 }
6242 /* This function builds ni_name = number of iterations loop executes
6243 on the loop preheader. */
6245 static tree
6247 {
6249 edge pe;
6259 {
6262 }
6265 }
6268 /* This function generates the following statements:
6270 ni_name = number of iterations loop executes
6271 ratio = ni_name / vf
6272 ratio_mult_vf_name = ratio * vf
6274 and places them at the loop preheader edge. */
6276 static void
6281 {
6283 edge pe;
6284 basic_block new_bb;
6286 tree var;
6287 tree ratio_name;
6288 tree ratio_mult_vf_name;
6292 tree log_vf;
6296 /* Generate temporary variable that contains
6297 number of iterations loop executes. */
6302 /* Create: ratio = ni >> log2(vf) */
6306 {
6314 }
6316 /* Create: ratio_mult_vf = ratio << log2 (vf). */
6321 {
6330 }
6337 }
6340 /* Function vect_update_ivs_after_vectorizer.
6342 "Advance" the induction variables of LOOP to the value they should take
6343 after the execution of LOOP. This is currently necessary because the
6344 vectorizer does not handle induction variables that are used after the
6345 loop. Such a situation occurs when the last iterations of LOOP are
6346 peeled, because:
6347 1. We introduced new uses after LOOP for IVs that were not originally used
6348 after LOOP: the IVs of LOOP are now used by an epilog loop.
6349 2. LOOP is going to be vectorized; this means that it will iterate N/VF
6350 times, whereas the loop IVs should be bumped N times.
6352 Input:
6353 - LOOP - a loop that is going to be vectorized. The last few iterations
6354 of LOOP were peeled.
6355 - NITERS - the number of iterations that LOOP executes (before it is
6356 vectorized). i.e, the number of times the ivs should be bumped.
6357 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
6358 coming out from LOOP on which there are uses of the LOOP ivs
6359 (this is the path from LOOP->exit to epilog_loop->preheader).
6361 The new definitions of the ivs are placed in LOOP->exit.
6362 The phi args associated with the edge UPDATE_E in the bb
6363 UPDATE_E->dest are updated accordingly.
6365 Assumption 1: Like the rest of the vectorizer, this function assumes
6366 a single loop exit that has a single predecessor.
6368 Assumption 2: The phi nodes in the LOOP header and in update_bb are
6369 organized in the same order.
6371 Assumption 3: The access function of the ivs is simple enough (see
6372 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
6374 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
6375 coming out of LOOP on which the ivs of LOOP are used (this is the path
6376 that leads to the epilog loop; other paths skip the epilog loop). This
6377 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
6378 needs to have its phis updated.
6379 */
6381 static void
6383 edge update_e)
6384 {
6390 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
6392 /* Make sure there exists a single-predecessor exit bb: */
6398 {
6400 tree evolution_part;
6401 tree init_expr;
6402 tree step_expr;
6404 block_stmt_iterator last_bsi;
6407 {
6410 }
6412 /* Skip virtual phi's. */
6414 {
6418 }
6420 /* Skip reduction phis. */
6422 {
6426 }
6430 evolution_part =
6434 /* FORNOW: We do not support IVs whose evolution function is a polynomial
6435 of degree >= 2 or exponential. */
6444 init_expr,
6448 else
6452 niters),
6453 step_expr),
6454 init_expr);
6465 /* Fix phi expressions in the successor bb. */
6467 }
6468 }
6471 /* Function vect_do_peeling_for_loop_bound
6473 Peel the last iterations of the loop represented by LOOP_VINFO.
6474 The peeled iterations form a new epilog loop. Given that the loop now
6475 iterates NITERS times, the new epilog loop iterates
6476 NITERS % VECTORIZATION_FACTOR times.
6478 The original loop will later be made to iterate
6479 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
6481 static void
6483 {
6487 edge update_e;
6488 basic_block preheader;
6499 /* Generate the following variables on the preheader of original loop:
6501 ni_name = number of iteration the original loop executes
6502 ratio = ni_name / vf
6503 ratio_mult_vf_name = ratio * vf */
6509 /* Analyze cost to set threshhold for vectorized loop. */
6514 /* Use the cost model only if it is more conservative than user specified
6515 threshold. */
6519 && (!min_scalar_loop_bound
6530 th);
6533 #ifdef ENABLE_CHECKING
6535 #endif
6537 /* A guard that controls whether the new_loop is to be executed or skipped
6538 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
6539 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
6540 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
6541 is on the path where the LOOP IVs are used and need to be updated. */
6546 else
6549 /* Update IVs of original loop as if they were advanced
6550 by ratio_mult_vf_name steps. */
6553 /* After peeling we have to reset scalar evolution analyzer. */
6557 }
6560 /* Function vect_gen_niters_for_prolog_loop
6562 Set the number of iterations for the loop represented by LOOP_VINFO
6563 to the minimum between LOOP_NITERS (the original iteration count of the loop)
6564 and the misalignment of DR - the data reference recorded in
6565 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
6566 this loop, the data reference DR will refer to an aligned location.
6568 The following computation is generated:
6570 If the misalignment of DR is known at compile time:
6571 addr_mis = int mis = DR_MISALIGNMENT (dr);
6572 Else, compute address misalignment in bytes:
6573 addr_mis = addr & (vectype_size - 1)
6575 prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
6577 (elem_size = element type size; an element is the scalar element
6578 whose type is the inner type of the vectype)
6580 For interleaving,
6582 prolog_niters = min ( LOOP_NITERS ,
6583 (VF/group_size - addr_mis/elem_size)&(VF/group_size-1) )
6584 where group_size is the size of the interleaved group.
6586 The above formulas assume that VF == number of elements in the vector. This
6587 may not hold when there are multiple-types in the loop.
6588 In this case, for some data-references in the loop the VF does not represent
6589 the number of elements that fit in the vector. Therefore, instead of VF we
6590 use TYPE_VECTOR_SUBPARTS. */
6592 static tree
6594 {
6599 edge pe;
6600 basic_block new_bb;
6611 {
6612 /* For interleaved access element size must be multiplied by the size of
6613 the interleaved group. */
6617 }
6622 {
6630 }
6631 else
6632 {
6640 tree elem_size_log =
6644 tree byte_misalign;
6645 tree elem_misalign;
6650 /* Create: byte_misalign = addr & (vectype_size - 1) */
6651 byte_misalign =
6654 /* Create: elem_misalign = byte_misalign / element_size */
6655 elem_misalign =
6658 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
6662 }
6664 /* Create: prolog_loop_niters = min (iters, loop_niters) */
6665 /* If the loop bound is known at compile time we already verified that it is
6666 greater than vf; since the misalignment ('iters') is at most vf, there's
6667 no need to generate the MIN_EXPR in this case. */
6672 {
6675 }
6681 /* Insert stmt on loop preheader edge. */
6683 {
6686 }
6689 }
6692 /* Function vect_update_init_of_dr
6694 NITERS iterations were peeled from LOOP. DR represents a data reference
6695 in LOOP. This function updates the information recorded in DR to
6696 account for the fact that the first NITERS iterations had already been
6697 executed. Specifically, it updates the OFFSET field of DR. */
6699 static void
6701 {
6707 }
6710 /* Function vect_update_inits_of_drs
6712 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
6713 This function updates the information recorded for the data references in
6714 the loop to account for the fact that the first NITERS iterations had
6715 already been executed. Specifically, it updates the initial_condition of
6716 the access_function of all the data_references in the loop. */
6718 static void
6720 {
6730 }
6733 /* Function vect_do_peeling_for_alignment
6735 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
6736 'niters' is set to the misalignment of one of the data references in the
6737 loop, thereby forcing it to refer to an aligned location at the beginning
6738 of the execution of this loop. The data reference for which we are
6739 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
6741 static void
6743 {
6746 tree n_iters;
6757 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
6758 new_loop =
6762 #ifdef ENABLE_CHECKING
6764 #endif
6766 /* Update number of times loop executes. */
6771 /* Update the init conditions of the access functions of all data refs. */
6774 /* After peeling we have to reset scalar evolution analyzer. */
6778 }
6781 /* Function vect_create_cond_for_align_checks.
6783 Create a conditional expression that represents the alignment checks for
6784 all of data references (array element references) whose alignment must be
6785 checked at runtime.
6787 Input:
6788 LOOP_VINFO - two fields of the loop information are used.
6789 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
6790 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
6792 Output:
6793 COND_EXPR_STMT_LIST - statements needed to construct the conditional
6794 expression.
6795 The returned value is the conditional expression to be used in the if
6796 statement that controls which version of the loop gets executed at runtime.
6798 The algorithm makes two assumptions:
6799 1) The number of bytes "n" in a vector is a power of 2.
6800 2) An address "a" is aligned if a%n is zero and that this
6801 test can be done as a&(n-1) == 0. For example, for 16
6802 byte vectors the test is a&0xf == 0. */
6804 static tree
6807 {
6813 tree mask_cst;
6815 tree psize;
6816 tree int_ptrsize_type;
6820 tree ptrsize_zero;
6822 /* Check that mask is one less than a power of 2, i.e., mask is
6823 all zeros followed by all ones. */
6826 /* CHECKME: what is the best integer or unsigned type to use to hold a
6827 cast from a pointer value? */
6829 int_ptrsize_type
6832 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
6833 of the first vector of the i'th data reference. */
6836 {
6838 tree addr_base;
6842 /* create: addr_tmp = (int)(address_of_first_vector) */
6858 /* The addresses are OR together. */
6861 {
6862 /* create: or_tmp = or_tmp | addr_tmp */
6873 }
6874 else
6881 /* create: and_tmp = or_tmp & mask */
6891 /* Make and_tmp the left operand of the conditional test against zero.
6892 if and_tmp has a nonzero bit then some address is unaligned. */
6896 }
6898 /* Function vect_vfa_segment_size.
6900 Create an expression that computes the size of segment
6901 that will be accessed for a data reference. The functions takes into
6902 account that realignment loads may access one more vector.
6904 Input:
6905 DR: The data reference.
6906 VECT_FACTOR: vectorization factor.
6908 Return an expression whose value is the size of segment which will be
6909 accessed by DR. */
6911 static tree
6913 {
6918 {
6919 tree vector_size = TYPE_SIZE_UNIT
6924 }
6926 }
6928 /* Function vect_create_cond_for_alias_checks.
6930 Create a conditional expression that represents the run-time checks for
6931 overlapping of address ranges represented by a list of data references
6932 relations passed as input.
6934 Input:
6935 COND_EXPR - input conditional expression. New conditions will be chained
6936 with logical and operation.
6937 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
6938 to be checked.
6940 Output:
6941 COND_EXPR - conditional expression.
6942 COND_EXPR_STMT_LIST - statements needed to construct the conditional
6943 expression.
6946 The returned value is the conditional expression to be used in the if
6947 statement that controls which version of the loop gets executed at runtime.
6948 */
6950 static void
6954 {
6958 tree vect_factor =
6961 ddr_p ddr;
6963 tree part_cond_expr;
6965 /* Create expression
6966 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
6967 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
6968 &&
6969 ...
6970 &&
6971 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
6972 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
6978 {
6989 {
6992 }
6998 {
7001 }
7003 addr_base_a =
7006 addr_base_b =
7014 {
7020 }
7023 part_cond_expr =
7027 addr_base_a,
7028 segment_length_a),
7029 addr_base_b),
7032 addr_base_b,
7033 segment_length_b),
7034 addr_base_a));
7039 else
7041 }
7046 }
7048 /* Function vect_loop_versioning.
7050 If the loop has data references that may or may not be aligned or/and
7051 has data reference relations whose independence was not proven then
7052 two versions of the loop need to be generated, one which is vectorized
7053 and one which isn't. A test is then generated to control which of the
7054 loops is executed. The test checks for the alignment of all of the
7055 data references that may or may not be aligned. An additional
7056 sequence of runtime tests is generated for each pairs of DDRs whose
7057 independence was not proven. The vectorized version of loop is
7058 executed only if both alias and alignment tests are passed. */
7060 static void
7062 {
7067 basic_block condition_bb;
7068 block_stmt_iterator cond_exp_bsi;
7069 basic_block merge_bb;
7070 basic_block new_exit_bb;
7074 tree gimplify_stmt_list;
7081 cond_expr =
7087 cond_expr =
7089 cond_expr =
7091 NULL_TREE);
7099 /* Loop versioning violates an assumption we try to maintain during
7100 vectorization - that the loop exit block has a single predecessor.
7101 After versioning, the exit block of both loop versions is the same
7102 basic block (i.e. it has two predecessors). Just in order to simplify
7103 following transformations in the vectorizer, we fix this situation
7104 here by adding a new (empty) block on the exit-edge of the loop,
7105 with the proper loop-exit phis to maintain loop-closed-form. */
7115 {
7117 new_exit_bb);
7121 }
7123 /* End loop-exit-fixes after versioning. */
7127 {
7130 }
7131 }
7133 /* Remove a group of stores (for SLP or interleaving), free their
7134 stmt_vec_info. */
7136 static void
7138 {
7139 stmt_ann_t ann;
7141 tree tmp;
7142 stmt_vec_info next_stmt_info;
7143 block_stmt_iterator next_si;
7146 {
7147 /* Free the attached stmt_vec_info and remove the stmt. */
7156 }
7157 }
7160 /* Vectorize SLP instance tree in postorder. */
7162 static bool
7164 {
7165 tree stmt;
7167 block_stmt_iterator si;
7168 stmt_vec_info stmt_info;
7182 {
7185 }
7190 {
7192 /* If IS_STORE is TRUE, the vectorization of the
7193 interleaving chain was completed - free all the stores in
7194 the chain. */
7196 else
7197 /* FORNOW: SLP originates only from strided stores. */
7201 }
7203 /* FORNOW: SLP originates only from strided stores. */
7205 }
7208 static bool
7210 {
7213 slp_instance instance;
7220 {
7222 /* For each SLP instance calculate number of vector stmts to be created
7223 for the scalar stmts in each node of the SLP tree. Number of vector
7224 elements in one vector iteration is the number of scalar elements in
7225 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
7226 size. */
7229 /* Schedule the tree of INSTANCE. */
7231 vec_stmts_size);
7236 }
7239 }
7241 /* Function vect_transform_loop.
7243 The analysis phase has determined that the loop is vectorizable.
7244 Vectorize the loop - created vectorized stmts to replace the scalar
7245 stmts in the loop, and update the loop exit condition. */
7247 void
7249 {
7265 /* CHECKME: we wouldn't need this if we called update_ssa once
7266 for all loops. */
7269 /* Peel the loop if there are data refs with unknown alignment.
7270 Only one data ref with unknown store is allowed. */
7275 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
7276 compile time constant), or it is a constant that doesn't divide by the
7277 vectorization factor, then an epilog loop needs to be created.
7278 We therefore duplicate the loop: the original loop will be vectorized,
7279 and will compute the first (n/VF) iterations. The second copy of the loop
7280 will remain scalar and will compute the remaining (n%VF) iterations.
7281 (VF is the vectorization factor). */
7287 else
7291 /* 1) Make sure the loop header has exactly two entries
7292 2) Make sure we have a preheader basic block. */
7298 /* FORNOW: the vectorizer supports only loops which body consist
7299 of one basic block (header + empty latch). When the vectorizer will
7300 support more involved loop forms, the order by which the BBs are
7301 traversed need to be reconsidered. */
7304 {
7306 stmt_vec_info stmt_info;
7307 tree phi;
7310 {
7312 {
7315 }
7330 {
7334 }
7335 }
7338 {
7343 {
7346 }
7350 /* vector stmts created in the outer-loop during vectorization of
7351 stmts in an inner-loop may not have a stmt_info, and do not
7352 need to be vectorized. */
7354 {
7357 }
7361 {
7364 }
7367 nunits =
7372 /* For SLP VF is set according to unrolling factor, and not to
7373 vector size, hence for SLP this print is not valid. */
7376 /* SLP. Schedule all the SLP instances when the first SLP stmt is
7377 reached. */
7379 {
7381 {
7389 /* IS_STORE is true if STMT is a store. Stores cannot be of
7390 hybrid SLP type. They are removed in
7391 vect_schedule_slp_instance and their vinfo is destroyed. */
7393 {
7396 }
7397 }
7399 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
7401 {
7404 }
7405 }
7407 /* -------- vectorize statement ------------ */
7414 {
7415 stmt_ann_t ann;
7417 {
7418 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
7419 interleaving chain was completed - free all the stores in
7420 the chain. */
7422 tree tmp;
7423 stmt_vec_info next_stmt_info;
7426 {
7429 /* Free the attached stmt_vec_info and remove the stmt. */
7436 }
7439 }
7440 else
7441 {
7442 /* Free the attached stmt_vec_info and remove the stmt. */
7448 }
7449 }
7458 /* The memory tags and pointers in vectorized statements need to
7459 have their SSA forms updated. FIXME, why can't this be delayed
7460 until all the loops have been transformed? */
7467 }