| blob | 00cc8c342185c40022b15b43d11945f606d4ed9c |
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 {
129 /* Cost model disabled. */
131 {
135 }
137 /* Requires loop versioning tests to handle misalignment.
138 FIXME: Make cost depend on number of stmts in may_misalign list. */
141 {
146 }
148 /* Count statements in scalar loop. Using this as scalar cost for a single
149 iteration for now.
151 TODO: Add outer loop support.
153 TODO: Consider assigning different costs to different scalar
154 statements. */
156 /* FORNOW. */
161 {
162 block_stmt_iterator si;
167 else
171 {
179 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
180 some of the "outside" costs are generated inside the outer-loop. */
182 }
183 }
185 /* Add additional cost for the peeled instructions in prologue and epilogue
186 loop.
188 FORNOW: If we dont know the value of peel_iters for prologue or epilogue
189 at compile-time - we assume it's (vf-1)/2 (the worst would be vf-1).
191 TODO: Build an expression that represents peel_iters for prologue and
192 epilogue to be used in a run-time test. */
197 {
203 /* If peeling for alignment is unknown, loop bound of main loop becomes
204 unknown. */
208 "epilogue peel iters set to (vf-1)/2 because "
210 }
211 else
212 {
214 {
221 }
222 else
226 {
230 "epilogue peel iters set to (vf-1)/2 because "
232 }
233 else
234 {
239 }
240 }
242 /* Requires a prologue loop when peeling to handle misalignment. Add cost of
243 two guards, one for the peeled loop and one for the vector loop. */
246 {
251 }
253 /* Requires an epilogue loop to finish up remaining iterations after vector
254 loop. Add cost of two guards, one for the peeled loop and one for the
255 vector loop. */
260 {
265 }
270 /* Allow targets add additional (outside-of-loop) costs. FORNOW, the only
271 information we provide for the target is whether testing against the
272 threshold involves a runtime test. */
274 {
277 /* If the number of iterations is unknown, or the
278 peeling-for-misalignment amount is unknown, we eill have to generate
279 a runtime test to test the loop count against the threshold. */
283 vec_outside_cost +=
288 }
290 /* Calculate number of iterations required to make the vector version
291 profitable, relative to the loop bodies only. The following condition
292 must hold true: ((SIC*VF)-VIC)*niters > VOC*VF, where
293 SIC = scalar iteration cost, VIC = vector iteration cost,
294 VOC = vector outside cost and VF = vectorization factor. */
297 {
300 else
301 {
309 min_profitable_iters++;
310 }
311 }
312 /* vector version will never be profitable. */
313 else
314 {
317 "is divisible by scalar iteration cost = %d by a factor "
321 }
324 {
327 vec_inside_cost);
329 vec_outside_cost);
332 peel_iters_prologue);
334 peel_iters_epilogue);
336 min_profitable_iters);
339 }
341 min_profitable_iters =
344 /* Because the condition we create is:
345 if (niters <= min_profitable_iters)
346 then skip the vectorized loop. */
347 min_profitable_iters--;
349 }
352 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
353 functions. Design better to avoid maintenance issues. */
355 /* Function vect_model_reduction_cost.
357 Models cost for a reduction operation, including the vector ops
358 generated within the strip-mine loop, the initial definition before
359 the loop, and the epilogue code that must be generated. */
361 static void
364 {
367 optab optab;
368 tree vectype;
369 tree orig_stmt;
370 tree reduction_op;
377 /* Cost of reduction op inside loop. */
390 /* Add in cost for initial definition. */
393 /* Determine cost of epilogue code.
395 We have a reduction operator that will reduce the vector in one statement.
396 Also requires scalar extract. */
399 {
402 else
403 {
405 tree bitsize =
412 /* We have a whole vector shift available. */
416 /* Final reduction via vector shifts and the reduction operator. Also
417 requires scalar extract. */
420 else
421 /* Use extracts and reduction op for final reduction. For N elements,
422 we have N extracts and N-1 reduction ops. */
424 }
425 }
433 }
436 /* Function vect_model_induction_cost.
438 Models cost for induction operations. */
440 static void
442 {
443 /* loop cost for vec_loop. */
445 /* prologue cost for vec_init and vec_step. */
452 }
455 /* Function vect_model_simple_cost.
457 Models cost for simple operations, i.e. those that only emit ncopies of a
458 single op. Right now, this does not account for multiple insns that could
459 be generated for the single vector op. We will handle that shortly. */
461 static void
463 {
468 /* FORNOW: Assuming maximum 2 args per stmts. */
470 {
473 }
479 }
482 /* Function vect_cost_strided_group_size
484 For strided load or store, return the group_size only if it is the first
485 load or store of a group, else return 1. This ensures that group size is
486 only returned once per group. */
488 static int
490 {
497 }
500 /* Function vect_model_store_cost
502 Models cost for stores. In the case of strided accesses, one access
503 has the overhead of the strided access attributed to it. */
505 static void
507 {
514 /* Strided access? */
517 /* Not a strided access. */
518 else
521 /* Is this an access in a group of stores, which provide strided access?
522 If so, add in the cost of the permutes. */
524 {
525 /* Uses a high and low interleave operation for each needed permute. */
531 group_size);
533 }
535 /* Costs of the stores. */
544 }
547 /* Function vect_model_load_cost
549 Models cost for loads. In the case of strided accesses, the last access
550 has the overhead of the strided access attributed to it. Since unaligned
551 accesses are supported for loads, we also account for the costs of the
552 access scheme chosen. */
554 static void
557 {
561 tree first_stmt;
564 /* Strided accesses? */
567 {
570 }
571 /* Not a strided access. */
572 else
573 {
576 }
580 /* Is this an access in a group of loads providing strided access?
581 If so, add in the cost of the permutes. */
583 {
584 /* Uses an even and odd extract operations for each needed permute. */
590 group_size);
592 }
594 /* The loads themselves. */
596 {
598 {
605 }
607 {
608 /* Here, we assign an additional cost for the unaligned load. */
616 }
618 {
621 /* FIXME: If the misalignment remains fixed across the iterations of
622 the containing loop, the following cost should be added to the
623 outside costs. */
628 }
630 {
637 /* Unaligned software pipeline has a load of an address, an initial
638 load, and possibly a mask operation to "prime" the loop. However,
639 if this is an access in a group of loads, which provide strided
640 access, then the above cost should only be considered for one
641 access in the group. Inside the loop, there is a load op
642 and a realignment op. */
645 {
649 }
656 }
660 }
669 }
672 /* Function vect_get_new_vect_var.
674 Returns a name for a new variable. The current naming scheme appends the
675 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
676 the name of vectorizer generated variables, and appends that to NAME if
677 provided. */
679 static tree
681 {
683 tree new_vect_var;
686 {
698 }
701 {
705 }
706 else
709 /* Mark vector typed variable as a gimple register variable. */
714 }
717 /* Function vect_create_addr_base_for_vector_ref.
719 Create an expression that computes the address of the first memory location
720 that will be accessed for a data reference.
722 Input:
723 STMT: The statement containing the data reference.
724 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
725 OFFSET: Optional. If supplied, it is be added to the initial address.
726 LOOP: Specify relative to which loop-nest should the address be computed.
727 For example, when the dataref is in an inner-loop nested in an
728 outer-loop that is now being vectorized, LOOP can be either the
729 outer-loop, or the inner-loop. The first memory location accessed
730 by the following dataref ('in' points to short):
732 for (i=0; i<N; i++)
733 for (j=0; j<M; j++)
734 s += in[i+j]
736 is as follows:
737 if LOOP=i_loop: &in (relative to i_loop)
738 if LOOP=j_loop: &in+i*2B (relative to j_loop)
740 Output:
741 1. Return an SSA_NAME whose value is the address of the memory location of
742 the first vector of the data reference.
743 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
744 these statement(s) which define the returned SSA_NAME.
746 FORNOW: We are only handling array accesses with step 1. */
748 static tree
751 tree offset,
753 {
758 tree base_name;
759 tree data_ref_base_var;
760 tree new_base_stmt;
761 tree vec_stmt;
771 {
780 }
782 /* Create data_ref_base */
790 /* Create base_offset */
799 {
808 }
810 /* base + base_offset */
816 /* addr_expr = addr_base */
828 {
831 }
833 }
836 /* Function vect_create_data_ref_ptr.
838 Create a new pointer to vector type (vp), that points to the first location
839 accessed in the loop by STMT, along with the def-use update chain to
840 appropriately advance the pointer through the loop iterations. Also set
841 aliasing information for the pointer. This vector pointer is used by the
842 callers to this function to create a memory reference expression for vector
843 load/store access.
845 Input:
846 1. STMT: a stmt that references memory. Expected to be of the form
847 GIMPLE_MODIFY_STMT <name, data-ref> or
848 GIMPLE_MODIFY_STMT <data-ref, name>.
849 2. AT_LOOP: the loop where the vector memref is to be created.
850 3. OFFSET (optional): an offset to be added to the initial address accessed
851 by the data-ref in STMT.
852 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
853 pointing to the initial address.
854 5. TYPE: if not NULL indicates the required type of the data-ref
856 Output:
857 1. Declare a new ptr to vector_type, and have it point to the base of the
858 data reference (initial addressed accessed by the data reference).
859 For example, for vector of type V8HI, the following code is generated:
861 v8hi *vp;
862 vp = (v8hi *)initial_address;
864 if OFFSET is not supplied:
865 initial_address = &a[init];
866 if OFFSET is supplied:
867 initial_address = &a[init + OFFSET];
869 Return the initial_address in INITIAL_ADDRESS.
871 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
872 update the pointer in each iteration of the loop.
874 Return the increment stmt that updates the pointer in PTR_INCR.
876 3. Set INV_P to true if the access pattern of the data reference in the
877 vectorized loop is invariant. Set it to false otherwise.
879 4. Return the pointer. */
881 static tree
885 {
886 tree base_name;
893 tree vect_ptr_type;
894 tree vect_ptr;
895 tree tag;
896 tree new_temp;
897 tree vec_stmt;
899 edge pe;
900 basic_block new_bb;
901 tree vect_ptr_init;
903 tree vptr;
904 block_stmt_iterator incr_bsi;
907 tree incr;
908 tree step;
910 /* Check the step (evolution) of the load in LOOP, and record
911 whether it's invariant. */
914 else
919 else
922 /* Create an expression for the first address accessed by this load
923 in LOOP. */
927 {
940 }
942 /** (1) Create the new vector-pointer variable: **/
945 else
951 /** (2) Add aliasing information to the new vector-pointer:
952 (The points-to info (DR_PTR_INFO) may be defined later.) **/
957 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
958 tag must be created with tag added to its may alias list. */
961 else
966 /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
967 vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
968 def-use update cycles for the pointer: One relative to the outer-loop
969 (LOOP), which is what steps (3) and (4) below do. The other is relative
970 to the inner-loop (which is the inner-most loop containing the dataref),
971 and this is done be step (5) below.
973 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
974 inner-most loop, and so steps (3),(4) work the same, and step (5) is
975 redundant. Steps (3),(4) create the following:
977 vp0 = &base_addr;
978 LOOP: vp1 = phi(vp0,vp2)
979 ...
980 ...
981 vp2 = vp1 + step
982 goto LOOP
984 If there is an inner-loop nested in loop, then step (5) will also be
985 applied, and an additional update in the inner-loop will be created:
987 vp0 = &base_addr;
988 LOOP: vp1 = phi(vp0,vp2)
989 ...
990 inner: vp3 = phi(vp1,vp4)
991 vp4 = vp3 + inner_step
992 if () goto inner
993 ...
994 vp2 = vp1 + step
995 if () goto LOOP */
997 /** (3) Calculate the initial address the vector-pointer, and set
998 the vector-pointer to point to it before the loop: **/
1000 /* Create: (&(base[init_val+offset]) in the loop preheader. */
1009 /* Create: p = (vectype *) initial_base */
1018 /** (4) Handle the updating of the vector-pointer inside the loop.
1019 This is needed when ONLY_INIT is false, and also when AT_LOOP
1020 is the inner-loop nested in LOOP (during outer-loop vectorization).
1021 **/
1024 {
1025 /* Copy the points-to information if it exists. */
1029 }
1030 else
1031 {
1032 /* The step of the vector pointer is the Vector Size. */
1034 /* One exception to the above is when the scalar step of the load in
1035 LOOP is zero. In this case the step here is also zero. */
1049 /* Copy the points-to information if it exists. */
1051 {
1054 }
1061 }
1067 /** (5) Handle the updating of the vector-pointer inside the inner-loop
1068 nested in LOOP, if exists: **/
1072 {
1081 /* Copy the points-to information if it exists. */
1083 {
1086 }
1093 }
1094 else
1096 }
1099 /* Function bump_vector_ptr
1101 Increment a pointer (to a vector type) by vector-size. If requested,
1102 i.e. if PTR-INCR is given, then also connect the new increment stmt
1103 to the existing def-use update-chain of the pointer, by modifying
1104 the PTR_INCR as illustrated below:
1106 The pointer def-use update-chain before this function:
1107 DATAREF_PTR = phi (p_0, p_2)
1108 ....
1109 PTR_INCR: p_2 = DATAREF_PTR + step
1111 The pointer def-use update-chain after this function:
1112 DATAREF_PTR = phi (p_0, p_2)
1113 ....
1114 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1115 ....
1116 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
1118 Input:
1119 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
1120 in the loop.
1121 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
1122 the loop. The increment amount across iterations is expected
1123 to be vector_size.
1124 BSI - location where the new update stmt is to be placed.
1125 STMT - the original scalar memory-access stmt that is being vectorized.
1126 BUMP - optional. The offset by which to bump the pointer. If not given,
1127 the offset is assumed to be vector_size.
1129 Output: Return NEW_DATAREF_PTR as illustrated above.
1131 */
1133 static tree
1136 {
1143 tree incr_stmt;
1144 ssa_op_iter iter;
1145 use_operand_p use_p;
1146 tree new_dataref_ptr;
1158 /* Copy the points-to information if it exists. */
1166 /* Update the vector-pointer's cross-iteration increment. */
1168 {
1173 else
1175 }
1178 }
1181 /* Function vect_create_destination_var.
1183 Create a new temporary of type VECTYPE. */
1185 static tree
1187 {
1188 tree vec_dest;
1190 tree type;
1205 }
1208 /* Function vect_init_vector.
1210 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1211 the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1212 is not NULL. Otherwise, place the initialization at the loop preheader.
1213 Return the DEF of INIT_STMT.
1214 It will be used in the vectorization of STMT. */
1216 static tree
1219 {
1221 tree new_var;
1222 tree init_stmt;
1223 tree vec_oprnd;
1224 edge pe;
1225 tree new_temp;
1226 basic_block new_bb;
1236 else
1237 {
1246 }
1249 {
1252 }
1256 }
1259 /* Function get_initial_def_for_induction
1261 Input:
1262 STMT - a stmt that performs an induction operation in the loop.
1263 IV_PHI - the initial value of the induction variable
1265 Output:
1266 Return a vector variable, initialized with the first VF values of
1267 the induction variable. E.g., for an iv with IV_PHI='X' and
1268 evolution S, for a vector of 4 units, we want to return:
1269 [X, X + S, X + 2*S, X + 3*S]. */
1271 static tree
1273 {
1282 basic_block new_bb;
1284 tree access_fn;
1285 tree new_var;
1286 tree new_name;
1287 tree init_stmt;
1294 tree expr;
1297 tree stmts;
1298 imm_use_iterator imm_iter;
1299 use_operand_p use_p;
1300 tree exit_phi;
1301 edge latch_e;
1302 tree loop_arg;
1303 block_stmt_iterator si;
1309 /* Find the first insertion point in the BB. */
1314 else
1317 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
1319 {
1322 }
1323 else
1337 /* Create the vector that holds the initial_value of the induction. */
1339 {
1340 /* iv_loop is nested in the loop to be vectorized. init_expr had already
1341 been created during vectorization of previous stmts; We obtain it from
1342 the STMT_VINFO_VEC_STMT of the defining stmt. */
1345 }
1346 else
1347 {
1348 /* iv_loop is the loop to be vectorized. Create:
1349 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
1355 {
1358 }
1363 {
1364 tree tmp;
1366 /* Create: new_name_i = new_name + step_expr */
1376 {
1379 }
1381 }
1382 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
1385 }
1388 /* Create the vector that holds the step of the induction. */
1390 /* iv_loop is nested in the loop to be vectorized. Generate:
1391 vec_step = [S, S, S, S] */
1393 else
1394 {
1395 /* iv_loop is the loop to be vectorized. Generate:
1396 vec_step = [VF*S, VF*S, VF*S, VF*S] */
1399 }
1408 /* Create the following def-use cycle:
1409 loop prolog:
1410 vec_init = ...
1411 vec_step = ...
1412 loop:
1413 vec_iv = PHI <vec_init, vec_loop>
1414 ...
1415 STMT
1416 ...
1417 vec_loop = vec_iv + vec_step; */
1419 /* Create the induction-phi that defines the induction-operand. */
1427 /* Create the iv update inside the loop */
1437 /* Set the arguments of the phi node: */
1442 /* In case that vectorization factor (VF) is bigger than the number
1443 of elements that we can fit in a vectype (nunits), we have to generate
1444 more than one vector stmt - i.e - we need to "unroll" the
1445 vector stmt by a factor VF/nunits. For more details see documentation
1446 in vectorizable_operation. */
1449 {
1450 stmt_vec_info prev_stmt_vinfo;
1451 /* FORNOW. This restriction should be relaxed. */
1454 /* Create the vector that holds the step of the induction. */
1466 {
1467 tree tmp;
1469 /* vec_i = vec_prev + vec_step */
1479 }
1480 }
1483 {
1484 /* Find the loop-closed exit-phi of the induction, and record
1485 the final vector of induction results: */
1488 {
1490 {
1493 }
1494 }
1496 {
1498 /* FORNOW. Currently not supporting the case that an inner-loop induction
1499 is not used in the outer-loop (i.e. only outside the outer-loop). */
1505 {
1508 }
1509 }
1510 }
1514 {
1519 }
1523 }
1526 /* Function vect_get_vec_def_for_operand.
1528 OP is an operand in STMT. This function returns a (vector) def that will be
1529 used in the vectorized stmt for STMT.
1531 In the case that OP is an SSA_NAME which is defined in the loop, then
1532 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1534 In case OP is an invariant or constant, a new stmt that creates a vector def
1535 needs to be introduced. */
1537 static tree
1539 {
1540 tree vec_oprnd;
1541 tree vec_stmt;
1542 tree def_stmt;
1548 tree vec_inv;
1549 tree vec_cst;
1551 tree def;
1555 tree vector_type;
1558 {
1561 }
1566 {
1568 {
1571 }
1573 {
1576 }
1577 }
1580 {
1581 /* Case 1: operand is a constant. */
1583 {
1587 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1592 {
1594 }
1599 }
1601 /* Case 2: operand is defined outside the loop - loop invariant. */
1603 {
1607 /* Create 'vec_inv = {inv,inv,..,inv}' */
1612 {
1614 }
1616 /* FIXME: use build_constructor directly. */
1620 }
1622 /* Case 3: operand is defined inside the loop. */
1624 {
1628 /* Get the def from the vectorized stmt. */
1634 else
1637 }
1639 /* Case 4: operand is defined by a loop header phi - reduction */
1641 {
1647 /* Get the def before the loop */
1650 }
1652 /* Case 5: operand is defined by loop-header phi - induction. */
1654 {
1657 /* Get the def from the vectorized stmt. */
1663 }
1667 }
1668 }
1671 /* Function vect_get_vec_def_for_stmt_copy
1673 Return a vector-def for an operand. This function is used when the
1674 vectorized stmt to be created (by the caller to this function) is a "copy"
1675 created in case the vectorized result cannot fit in one vector, and several
1676 copies of the vector-stmt are required. In this case the vector-def is
1677 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1678 of the stmt that defines VEC_OPRND.
1679 DT is the type of the vector def VEC_OPRND.
1681 Context:
1682 In case the vectorization factor (VF) is bigger than the number
1683 of elements that can fit in a vectype (nunits), we have to generate
1684 more than one vector stmt to vectorize the scalar stmt. This situation
1685 arises when there are multiple data-types operated upon in the loop; the
1686 smallest data-type determines the VF, and as a result, when vectorizing
1687 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1688 vector stmt (each computing a vector of 'nunits' results, and together
1689 computing 'VF' results in each iteration). This function is called when
1690 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1691 which VF=16 and nunits=4, so the number of copies required is 4):
1693 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
1695 S1: x = load VS1.0: vx.0 = memref0 VS1.1
1696 VS1.1: vx.1 = memref1 VS1.2
1697 VS1.2: vx.2 = memref2 VS1.3
1698 VS1.3: vx.3 = memref3
1700 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
1701 VSnew.1: vz1 = vx.1 + ... VSnew.2
1702 VSnew.2: vz2 = vx.2 + ... VSnew.3
1703 VSnew.3: vz3 = vx.3 + ...
1705 The vectorization of S1 is explained in vectorizable_load.
1706 The vectorization of S2:
1707 To create the first vector-stmt out of the 4 copies - VSnew.0 -
1708 the function 'vect_get_vec_def_for_operand' is called to
1709 get the relevant vector-def for each operand of S2. For operand x it
1710 returns the vector-def 'vx.0'.
1712 To create the remaining copies of the vector-stmt (VSnew.j), this
1713 function is called to get the relevant vector-def for each operand. It is
1714 obtained from the respective VS1.j stmt, which is recorded in the
1715 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
1717 For example, to obtain the vector-def 'vx.1' in order to create the
1718 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
1719 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
1720 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
1721 and return its def ('vx.1').
1722 Overall, to create the above sequence this function will be called 3 times:
1723 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
1724 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
1725 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
1727 static tree
1729 {
1730 tree vec_stmt_for_operand;
1731 stmt_vec_info def_stmt_info;
1733 /* Do nothing; can reuse same def. */
1744 }
1747 /* Function vect_finish_stmt_generation.
1749 Insert a new stmt. */
1751 static void
1754 {
1767 {
1770 }
1772 /* Make sure bsi points to the stmt that is being vectorized. */
1775 #ifdef USE_MAPPED_LOCATION
1777 #else
1779 #endif
1780 }
1783 /* Function get_initial_def_for_reduction
1785 Input:
1786 STMT - a stmt that performs a reduction operation in the loop.
1787 INIT_VAL - the initial value of the reduction variable
1789 Output:
1790 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
1791 of the reduction (used for adjusting the epilog - see below).
1792 Return a vector variable, initialized according to the operation that STMT
1793 performs. This vector will be used as the initial value of the
1794 vector of partial results.
1796 Option1 (adjust in epilog): Initialize the vector as follows:
1797 add: [0,0,...,0,0]
1798 mult: [1,1,...,1,1]
1799 min/max: [init_val,init_val,..,init_val,init_val]
1800 bit and/or: [init_val,init_val,..,init_val,init_val]
1801 and when necessary (e.g. add/mult case) let the caller know
1802 that it needs to adjust the result by init_val.
1804 Option2: Initialize the vector as follows:
1805 add: [0,0,...,0,init_val]
1806 mult: [1,1,...,1,init_val]
1807 min/max: [init_val,init_val,...,init_val]
1808 bit and/or: [init_val,init_val,...,init_val]
1809 and no adjustments are needed.
1811 For example, for the following code:
1813 s = init_val;
1814 for (i=0;i<n;i++)
1815 s = s + a[i];
1817 STMT is 's = s + a[i]', and the reduction variable is 's'.
1818 For a vector of 4 units, we want to return either [0,0,0,init_val],
1819 or [0,0,0,0] and let the caller know that it needs to adjust
1820 the result at the end by 'init_val'.
1822 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
1823 initialization vector is simpler (same element in all entries).
1824 A cost model should help decide between these two schemes. */
1826 static tree
1828 {
1836 tree vecdef;
1837 tree def_for_init;
1838 tree init_def;
1841 tree vector_type;
1847 else
1853 {
1859 else
1861 /* Create a vector of zeros for init_def. */
1864 else
1880 }
1883 }
1886 /* Function vect_create_epilog_for_reduction
1888 Create code at the loop-epilog to finalize the result of a reduction
1889 computation.
1891 VECT_DEF is a vector of partial results.
1892 REDUC_CODE is the tree-code for the epilog reduction.
1893 STMT is the scalar reduction stmt that is being vectorized.
1894 REDUCTION_PHI is the phi-node that carries the reduction computation.
1896 This function:
1897 1. Creates the reduction def-use cycle: sets the arguments for
1898 REDUCTION_PHI:
1899 The loop-entry argument is the vectorized initial-value of the reduction.
1900 The loop-latch argument is VECT_DEF - the vector of partial sums.
1901 2. "Reduces" the vector of partial results VECT_DEF into a single result,
1902 by applying the operation specified by REDUC_CODE if available, or by
1903 other means (whole-vector shifts or a scalar loop).
1904 The function also creates a new phi node at the loop exit to preserve
1905 loop-closed form, as illustrated below.
1907 The flow at the entry to this function:
1909 loop:
1910 vec_def = phi <null, null> # REDUCTION_PHI
1911 VECT_DEF = vector_stmt # vectorized form of STMT
1912 s_loop = scalar_stmt # (scalar) STMT
1913 loop_exit:
1914 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1915 use <s_out0>
1916 use <s_out0>
1918 The above is transformed by this function into:
1920 loop:
1921 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
1922 VECT_DEF = vector_stmt # vectorized form of STMT
1923 s_loop = scalar_stmt # (scalar) STMT
1924 loop_exit:
1925 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1926 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
1927 v_out2 = reduce <v_out1>
1928 s_out3 = extract_field <v_out2, 0>
1929 s_out4 = adjust_result <s_out3>
1930 use <s_out4>
1931 use <s_out4>
1932 */
1934 static void
1937 {
1939 tree vectype;
1943 basic_block exit_bb;
1944 tree scalar_dest;
1945 tree scalar_type;
1946 tree new_phi;
1947 block_stmt_iterator exit_bsi;
1948 tree vec_dest;
1950 tree new_name;
1955 tree adjustment_def;
1956 tree vec_initial_def;
1957 tree orig_name;
1958 imm_use_iterator imm_iter;
1959 use_operand_p use_p;
1962 tree orig_stmt;
1963 tree use_stmt;
1969 {
1972 }
1979 /*** 1. Create the reduction def-use cycle ***/
1981 /* 1.1 set the loop-entry arg of the reduction-phi: */
1982 /* For the case of reduction, vect_get_vec_def_for_operand returns
1983 the scalar def before the loop, that defines the initial value
1984 of the reduction variable. */
1989 /* 1.2 set the loop-latch arg for the reduction-phi: */
1993 {
1998 }
2001 /*** 2. Create epilog code
2002 The reduction epilog code operates across the elements of the vector
2003 of partial results computed by the vectorized loop.
2004 The reduction epilog code consists of:
2005 step 1: compute the scalar result in a vector (v_out2)
2006 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2007 step 3: adjust the scalar result (s_out3) if needed.
2009 Step 1 can be accomplished using one the following three schemes:
2010 (scheme 1) using reduc_code, if available.
2011 (scheme 2) using whole-vector shifts, if available.
2012 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2013 combined.
2015 The overall epilog code looks like this:
2017 s_out0 = phi <s_loop> # original EXIT_PHI
2018 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2019 v_out2 = reduce <v_out1> # step 1
2020 s_out3 = extract_field <v_out2, 0> # step 2
2021 s_out4 = adjust_result <s_out3> # step 3
2023 (step 3 is optional, and step2 1 and 2 may be combined).
2024 Lastly, the uses of s_out0 are replaced by s_out4.
2026 ***/
2028 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2029 v_out1 = phi <v_loop> */
2036 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
2037 (i.e. when reduc_code is not available) and in the final adjustment
2038 code (if needed). Also get the original scalar reduction variable as
2039 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
2040 represents a reduction pattern), the tree-code and scalar-def are
2041 taken from the original stmt that the pattern-stmt (STMT) replaces.
2042 Otherwise (it is a regular reduction) - the tree-code and scalar-def
2043 are taken from STMT. */
2047 {
2048 /* Regular reduction */
2050 }
2051 else
2052 {
2053 /* Reduction pattern */
2057 }
2066 /* In case this is a reduction in an inner-loop while vectorizing an outer
2067 loop - we don't need to extract a single scalar result at the end of the
2068 inner-loop. The final vector of partial results will be used in the
2069 vectorized outer-loop, or reduced to a scalar result at the end of the
2070 outer-loop. */
2074 /* 2.3 Create the reduction code, using one of the three schemes described
2075 above. */
2078 {
2079 tree tmp;
2081 /*** Case 1: Create:
2082 v_out2 = reduc_expr <v_out1> */
2095 }
2096 else
2097 {
2103 tree vec_temp;
2107 else
2110 /* Regardless of whether we have a whole vector shift, if we're
2111 emulating the operation via tree-vect-generic, we don't want
2112 to use it. Only the first round of the reduction is likely
2113 to still be profitable via emulation. */
2114 /* ??? It might be better to emit a reduction tree code here, so that
2115 tree-vect-generic can expand the first round via bit tricks. */
2118 else
2119 {
2123 }
2126 {
2127 /*** Case 2: Create:
2128 for (offset = VS/2; offset >= element_size; offset/=2)
2129 {
2130 Create: va' = vec_shift <va, offset>
2131 Create: va = vop <va, va'>
2132 } */
2143 {
2156 }
2159 }
2160 else
2161 {
2162 tree rhs;
2164 /*** Case 3: Create:
2165 s = extract_field <v_out2, 0>
2166 for (offset = element_size;
2167 offset < vector_size;
2168 offset += element_size;)
2169 {
2170 Create: s' = extract_field <v_out2, offset>
2171 Create: s = op <s, s'>
2172 } */
2180 bitsize_zero_node);
2190 {
2191 tree tmp;
2194 bitpos);
2207 }
2210 }
2211 }
2213 /* 2.4 Extract the final scalar result. Create:
2214 s_out3 = extract_field <v_out2, bitpos> */
2217 {
2218 tree rhs;
2228 else
2237 }
2239 vect_finalize_reduction:
2241 /* 2.5 Adjust the final result by the initial value of the reduction
2242 variable. (When such adjustment is not needed, then
2243 'adjustment_def' is zero). For example, if code is PLUS we create:
2244 new_temp = loop_exit_def + adjustment_def */
2247 {
2249 {
2253 }
2254 else
2255 {
2259 }
2263 #if 0
2265 #else
2267 #endif
2268 }
2271 /* 2.6 Handle the loop-exit phi */
2273 /* Replace uses of s_out0 with uses of s_out3:
2274 Find the loop-closed-use at the loop exit of the original scalar result.
2275 (The reduction result is expected to have two immediate uses - one at the
2276 latch block, and one at the loop exit). */
2279 {
2281 {
2284 }
2285 }
2286 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
2290 {
2293 /* FORNOW. Currently not supporting the case that an inner-loop reduction
2294 is not used in the outer-loop (but only outside the outer-loop). */
2304 {
2307 }
2309 }
2311 /* Replace the uses: */
2316 }
2319 /* Function vectorizable_reduction.
2321 Check if STMT performs a reduction operation that can be vectorized.
2322 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2323 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2324 Return FALSE if not a vectorizable STMT, TRUE otherwise.
2326 This function also handles reduction idioms (patterns) that have been
2327 recognized in advance during vect_pattern_recog. In this case, STMT may be
2328 of this form:
2329 X = pattern_expr (arg0, arg1, ..., X)
2330 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2331 sequence that had been detected and replaced by the pattern-stmt (STMT).
2333 In some cases of reduction patterns, the type of the reduction variable X is
2334 different than the type of the other arguments of STMT.
2335 In such cases, the vectype that is used when transforming STMT into a vector
2336 stmt is different than the vectype that is used to determine the
2337 vectorization factor, because it consists of a different number of elements
2338 than the actual number of elements that are being operated upon in parallel.
2340 For example, consider an accumulation of shorts into an int accumulator.
2341 On some targets it's possible to vectorize this pattern operating on 8
2342 shorts at a time (hence, the vectype for purposes of determining the
2343 vectorization factor should be V8HI); on the other hand, the vectype that
2344 is used to create the vector form is actually V4SI (the type of the result).
2346 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2347 indicates what is the actual level of parallelism (V8HI in the example), so
2348 that the right vectorization factor would be derived. This vectype
2349 corresponds to the type of arguments to the reduction stmt, and should *NOT*
2350 be used to create the vectorized stmt. The right vectype for the vectorized
2351 stmt is obtained from the type of the result X:
2352 get_vectype_for_scalar_type (TREE_TYPE (X))
2354 This means that, contrary to "regular" reductions (or "regular" stmts in
2355 general), the following equation:
2356 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2357 does *NOT* necessarily hold for reduction patterns. */
2359 bool
2361 {
2362 tree vec_dest;
2363 tree scalar_dest;
2364 tree op;
2370 tree operation;
2378 tree new_phi;
2379 tree scalar_type;
2381 tree orig_stmt;
2382 stmt_vec_info orig_stmt_info;
2387 stmt_vec_info prev_stmt_info;
2388 tree reduc_def;
2393 {
2395 /* FORNOW. This restriction should be relaxed. */
2397 {
2401 }
2402 }
2406 /* 1. Is vectorizable reduction? */
2408 /* Not supportable if the reduction variable is used in the loop. */
2412 /* Reductions that are not used even in an enclosing outer-loop,
2413 are expected to be "live" (used out of the loop). */
2418 /* Make sure it was already recognized as a reduction computation. */
2422 /* 2. Has this been recognized as a reduction pattern?
2424 Check if STMT represents a pattern that has been recognized
2425 in earlier analysis stages. For stmts that represent a pattern,
2426 the STMT_VINFO_RELATED_STMT field records the last stmt in
2427 the original sequence that constitutes the pattern. */
2431 {
2436 }
2438 /* 3. Check the operands of the operation. The first operands are defined
2439 inside the loop body. The last operand is the reduction variable,
2440 which is defined by the loop-header-phi. */
2452 /* All uses but the last are expected to be defined in the loop.
2453 The last use is the reduction variable. */
2455 {
2464 }
2473 else
2479 /* 4. Supportable by target? */
2481 /* 4.1. check support for the operation in the loop */
2484 {
2488 }
2491 {
2500 }
2502 /* Worthwhile without SIMD support? */
2506 {
2510 }
2512 /* 4.2. Check support for the epilog operation.
2514 If STMT represents a reduction pattern, then the type of the
2515 reduction variable may be different than the type of the rest
2516 of the arguments. For example, consider the case of accumulation
2517 of shorts into an int accumulator; The original code:
2518 S1: int_a = (int) short_a;
2519 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
2521 was replaced with:
2522 STMT: int_acc = widen_sum <short_a, int_acc>
2524 This means that:
2525 1. The tree-code that is used to create the vector operation in the
2526 epilog code (that reduces the partial results) is not the
2527 tree-code of STMT, but is rather the tree-code of the original
2528 stmt from the pattern that STMT is replacing. I.e, in the example
2529 above we want to use 'widen_sum' in the loop, but 'plus' in the
2530 epilog.
2531 2. The type (mode) we use to check available target support
2532 for the vector operation to be created in the *epilog*, is
2533 determined by the type of the reduction variable (in the example
2534 above we'd check this: plus_optab[vect_int_mode]).
2535 However the type (mode) we use to check available target support
2536 for the vector operation to be created *inside the loop*, is
2537 determined by the type of the other arguments to STMT (in the
2538 example we'd check this: widen_sum_optab[vect_short_mode]).
2540 This is contrary to "regular" reductions, in which the types of all
2541 the arguments are the same as the type of the reduction variable.
2542 For "regular" reductions we can therefore use the same vector type
2543 (and also the same tree-code) when generating the epilog code and
2544 when generating the code inside the loop. */
2547 {
2548 /* This is a reduction pattern: get the vectype from the type of the
2549 reduction variable, and get the tree-code from orig_stmt. */
2553 }
2554 else
2555 {
2556 /* Regular reduction: use the same vectype and tree-code as used for
2557 the vector code inside the loop can be used for the epilog code. */
2559 }
2565 {
2569 }
2571 {
2575 }
2578 {
2582 }
2584 /** Transform. **/
2589 /* Create the destination vector */
2592 /* Create the reduction-phi that defines the reduction-operand. */
2595 /* In case the vectorization factor (VF) is bigger than the number
2596 of elements that we can fit in a vectype (nunits), we have to generate
2597 more than one vector stmt - i.e - we need to "unroll" the
2598 vector stmt by a factor VF/nunits. For more details see documentation
2599 in vectorizable_operation. */
2603 {
2604 /* Handle uses. */
2606 {
2610 {
2613 }
2615 /* Get the vector def for the reduction variable from the phi node */
2617 }
2618 else
2619 {
2625 /* Get the vector def for the reduction variable from the vectorized
2626 reduction operation generated in the previous iteration (j-1) */
2628 }
2630 /* Arguments are ready. create the new vector stmt. */
2633 else
2635 reduc_def);
2643 else
2646 }
2648 /* Finalize the reduction-phi (set it's arguments) and create the
2649 epilog reduction code. */
2652 }
2654 /* Checks if CALL can be vectorized in type VECTYPE. Returns
2655 a function declaration if the target has a vectorized version
2656 of the function, or NULL_TREE if the function cannot be vectorized. */
2658 tree
2660 {
2664 /* We only handle functions that do not read or clobber memory -- i.e.
2665 const or novops ones. */
2676 vectype_in);
2677 }
2679 /* Function vectorizable_call.
2681 Check if STMT performs a function call that can be vectorized.
2682 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2683 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2684 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2686 bool
2688 {
2689 tree vec_dest;
2690 tree scalar_dest;
2691 tree operation;
2702 tree new_stmt;
2704 call_expr_arg_iterator iter;
2705 tree vargs;
2714 /* FORNOW: not yet supported. */
2716 {
2720 }
2722 /* Is STMT a vectorizable call? */
2733 /* Process function arguments. */
2737 {
2738 /* Bail out if the function has more than two arguments, we
2739 do not have interesting builtin functions to vectorize with
2740 more than two arguments. */
2744 /* We can only handle calls with arguments of the same type. */
2747 {
2751 }
2755 {
2759 }
2762 }
2764 /* No arguments is also not good. */
2775 /* FORNOW */
2782 else
2785 /* For now, we only vectorize functions if a target specific builtin
2786 is available. TODO -- in some cases, it might be profitable to
2787 insert the calls for pieces of the vector, in order to be able
2788 to vectorize other operations in the loop. */
2791 {
2796 }
2802 else
2805 /* Sanity check: make sure that at least one copy of the vectorized stmt
2806 needs to be generated. */
2809 /* FORNOW. This restriction should be relaxed. */
2811 {
2815 }
2818 {
2824 }
2826 /** Transform. **/
2831 /* FORNOW. This restriction should be relaxed. */
2833 {
2837 }
2839 /* Handle def. */
2845 {
2848 {
2849 /* Build argument list for the vectorized call. */
2850 /* FIXME: Rewrite this so that it doesn't
2851 construct a temporary list. */
2855 {
2857 vec_oprnd0
2859 else
2860 vec_oprnd0
2866 }
2878 else
2882 }
2888 {
2889 /* Build argument list for the vectorized call. */
2890 /* FIXME: Rewrite this so that it doesn't
2891 construct a temporary list. */
2895 {
2897 {
2898 vec_oprnd0
2900 vec_oprnd1
2902 }
2903 else
2904 {
2905 vec_oprnd0
2907 vec_oprnd1
2909 }
2915 }
2927 else
2931 }
2938 /* No current target implements this case. */
2940 }
2942 /* The call in STMT might prevent it from being removed in dce.
2943 We however cannot remove it here, due to the way the ssa name
2944 it defines is mapped to the new definition. So just replace
2945 rhs of the statement with something harmless. */
2951 }
2954 /* Function vect_gen_widened_results_half
2956 Create a vector stmt whose code, type, number of arguments, and result
2957 variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are
2958 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
2959 In the case that CODE is a CALL_EXPR, this means that a call to DECL
2960 needs to be created (DECL is a function-decl of a target-builtin).
2961 STMT is the original scalar stmt that we are vectorizing. */
2963 static tree
2967 tree stmt)
2968 {
2969 tree expr;
2970 tree new_stmt;
2971 tree new_temp;
2972 tree sym;
2973 ssa_op_iter iter;
2975 /* Generate half of the widened result: */
2977 {
2978 /* Target specific support */
2981 else
2983 }
2984 else
2985 {
2986 /* Generic support */
2990 else
2992 }
2999 {
3001 {
3005 }
3006 }
3009 }
3012 /* Function vectorizable_conversion.
3014 Check if STMT performs a conversion operation, that can be vectorized.
3015 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3016 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3017 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3019 bool
3022 {
3023 tree vec_dest;
3024 tree scalar_dest;
3025 tree operation;
3026 tree op0;
3033 tree new_temp;
3036 tree new_stmt;
3037 stmt_vec_info prev_stmt_info;
3042 tree expr;
3044 tree builtin_decl;
3047 /* Is STMT a vectorizable conversion? */
3056 {
3057 /* FORNOW: not yet supported. */
3061 }
3074 /* Check types of lhs and rhs */
3085 /* FORNOW */
3092 else
3098 /* Bail out if the types are both integral or non-integral */
3105 else
3108 /* Sanity check: make sure that at least one copy of the vectorized stmt
3109 needs to be generated. */
3112 /* FORNOW. This restriction should be relaxed. */
3114 {
3118 }
3120 /* Check the operands of the operation. */
3122 {
3126 }
3128 /* Supportable by target? */
3138 {
3142 }
3148 {
3151 }
3153 /** Transform. **/
3157 /* Handle def. */
3162 {
3165 {
3166 tree sym;
3167 ssa_op_iter iter;
3171 else
3174 builtin_decl =
3178 /* Arguments are ready. create the new vector stmt. */
3184 {
3188 }
3192 else
3195 }
3199 /* In case the vectorization factor (VF) is bigger than the number
3200 of elements that we can fit in a vectype (nunits), we have to
3201 generate more than one vector stmt - i.e - we need to "unroll"
3202 the vector stmt by a factor VF/nunits. */
3204 {
3207 else
3212 /* Generate first half of the widened result: */
3213 new_stmt
3219 else
3223 /* Generate second half of the widened result: */
3224 new_stmt
3230 }
3234 /* In case the vectorization factor (VF) is bigger than the number
3235 of elements that we can fit in a vectype (nunits), we have to
3236 generate more than one vector stmt - i.e - we need to "unroll"
3237 the vector stmt by a factor VF/nunits. */
3239 {
3240 /* Handle uses. */
3242 {
3245 }
3246 else
3247 {
3250 }
3252 /* Arguments are ready. Create the new vector stmt. */
3261 else
3265 }
3268 }
3270 }
3273 /* Function vectorizable_assignment.
3275 Check if STMT performs an assignment (copy) that can be vectorized.
3276 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3277 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3278 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3280 bool
3282 {
3283 tree vec_dest;
3284 tree scalar_dest;
3285 tree op;
3286 tree vec_oprnd;
3290 tree new_temp;
3306 /* FORNOW: not yet supported. */
3308 {
3312 }
3314 /* Is vectorizable assignment? */
3324 {
3328 }
3331 {
3337 }
3339 /** Transform. **/
3343 /* Handle def. */
3346 /* Handle use. */
3350 /* Arguments are ready. create the new vector stmt. */
3357 }
3360 /* Function vect_min_worthwhile_factor.
3362 For a loop where we could vectorize the operation indicated by CODE,
3363 return the minimum vectorization factor that makes it worthwhile
3364 to use generic vectors. */
3365 static int
3367 {
3369 {
3383 }
3384 }
3387 /* Function vectorizable_induction
3389 Check if PHI performs an induction computation that can be vectorized.
3390 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3391 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3392 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3394 bool
3397 {
3403 tree vec_def;
3413 {
3414 /* FORNOW: not yet supported. */
3418 }
3424 {
3430 }
3432 /** Transform. **/
3440 }
3443 /* Function vectorizable_operation.
3445 Check if STMT performs a binary or unary operation that can be vectorized.
3446 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3447 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3448 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3450 bool
3452 {
3453 tree vec_dest;
3454 tree scalar_dest;
3455 tree operation;
3464 tree new_temp;
3466 optab optab;
3471 tree new_stmt;
3472 stmt_vec_info prev_stmt_info;
3475 tree vectype_out;
3480 /* FORNOW. This restriction should be relaxed. */
3482 {
3486 }
3494 /* FORNOW: not yet supported. */
3496 {
3500 }
3502 /* Is STMT a vectorizable binary/unary operation? */
3518 /* For pointer addition, we should use the normal plus for
3519 the vector addition. */
3525 /* Support only unary or binary operations. */
3528 {
3532 }
3536 {
3540 }
3543 {
3546 {
3550 }
3551 }
3553 /* Supportable by target? */
3555 {
3559 }
3563 {
3572 }
3574 /* Worthwhile without SIMD support? */
3578 {
3582 }
3585 {
3586 /* FORNOW: not yet supported. */
3590 /* Invariant argument is needed for a vector shift
3591 by a scalar shift operand. */
3596 {
3600 }
3601 }
3604 {
3610 }
3612 /** Transform. **/
3617 /* Handle def. */
3620 /* In case the vectorization factor (VF) is bigger than the number
3621 of elements that we can fit in a vectype (nunits), we have to generate
3622 more than one vector stmt - i.e - we need to "unroll" the
3623 vector stmt by a factor VF/nunits. In doing so, we record a pointer
3624 from one copy of the vector stmt to the next, in the field
3625 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3626 stages to find the correct vector defs to be used when vectorizing
3627 stmts that use the defs of the current stmt. The example below illustrates
3628 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3629 4 vectorized stmts):
3631 before vectorization:
3632 RELATED_STMT VEC_STMT
3633 S1: x = memref - -
3634 S2: z = x + 1 - -
3636 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
3637 there):
3638 RELATED_STMT VEC_STMT
3639 VS1_0: vx0 = memref0 VS1_1 -
3640 VS1_1: vx1 = memref1 VS1_2 -
3641 VS1_2: vx2 = memref2 VS1_3 -
3642 VS1_3: vx3 = memref3 - -
3643 S1: x = load - VS1_0
3644 S2: z = x + 1 - -
3646 step2: vectorize stmt S2 (done here):
3647 To vectorize stmt S2 we first need to find the relevant vector
3648 def for the first operand 'x'. This is, as usual, obtained from
3649 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
3650 that defines 'x' (S1). This way we find the stmt VS1_0, and the
3651 relevant vector def 'vx0'. Having found 'vx0' we can generate
3652 the vector stmt VS2_0, and as usual, record it in the
3653 STMT_VINFO_VEC_STMT of stmt S2.
3654 When creating the second copy (VS2_1), we obtain the relevant vector
3655 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
3656 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
3657 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
3658 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
3659 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
3660 chain of stmts and pointers:
3661 RELATED_STMT VEC_STMT
3662 VS1_0: vx0 = memref0 VS1_1 -
3663 VS1_1: vx1 = memref1 VS1_2 -
3664 VS1_2: vx2 = memref2 VS1_3 -
3665 VS1_3: vx3 = memref3 - -
3666 S1: x = load - VS1_0
3667 VS2_0: vz0 = vx0 + v1 VS2_1 -
3668 VS2_1: vz1 = vx1 + v1 VS2_2 -
3669 VS2_2: vz2 = vx2 + v1 VS2_3 -
3670 VS2_3: vz3 = vx3 + v1 - -
3671 S2: z = x + 1 - VS2_0 */
3675 {
3676 /* Handle uses. */
3678 {
3681 {
3683 {
3684 /* Vector shl and shr insn patterns can be defined with
3685 scalar operand 2 (shift operand). In this case, use
3686 constant or loop invariant op1 directly, without
3687 extending it to vector mode first. */
3690 {
3694 }
3695 }
3698 }
3699 }
3700 else
3701 {
3705 }
3707 /* Arguments are ready. create the new vector stmt. */
3712 else
3721 else
3724 }
3727 }
3730 /* Function vectorizable_type_demotion
3732 Check if STMT performs a binary or unary operation that involves
3733 type demotion, and if it can be vectorized.
3734 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3735 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3736 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3738 bool
3741 {
3742 tree vec_dest;
3743 tree scalar_dest;
3744 tree operation;
3745 tree op0;
3751 tree new_temp;
3754 tree new_stmt;
3755 stmt_vec_info prev_stmt_info;
3758 tree vectype_out;
3761 tree expr;
3762 tree vectype_in;
3770 /* FORNOW: not yet supported. */
3772 {
3776 }
3778 /* Is STMT a vectorizable type-demotion operation? */
3802 /* FORNOW. This restriction should be relaxed. */
3804 {
3808 }
3817 /* Check the operands of the operation. */
3819 {
3823 }
3825 /* Supportable by target? */
3832 {
3838 }
3840 /** Transform. **/
3843 ncopies);
3845 /* Handle def. */
3848 /* In case the vectorization factor (VF) is bigger than the number
3849 of elements that we can fit in a vectype (nunits), we have to generate
3850 more than one vector stmt - i.e - we need to "unroll" the
3851 vector stmt by a factor VF/nunits. */
3854 {
3855 /* Handle uses. */
3857 {
3860 }
3861 else
3862 {
3865 }
3867 /* Arguments are ready. Create the new vector stmt. */
3876 else
3880 }
3884 }
3887 /* Function vectorizable_type_promotion
3889 Check if STMT performs a binary or unary operation that involves
3890 type promotion, and if it can be vectorized.
3891 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3892 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3893 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3895 bool
3898 {
3899 tree vec_dest;
3900 tree scalar_dest;
3901 tree operation;
3912 tree new_stmt;
3913 stmt_vec_info prev_stmt_info;
3916 tree vectype_out;
3919 tree vectype_in;
3927 /* FORNOW: not yet supported. */
3929 {
3933 }
3935 /* Is STMT a vectorizable type-promotion operation? */
3960 /* FORNOW. This restriction should be relaxed. */
3962 {
3966 }
3975 /* Check the operands of the operation. */
3977 {
3981 }
3985 {
3988 {
3992 }
3993 }
3995 /* Supportable by target? */
4003 {
4009 }
4011 /** Transform. **/
4015 ncopies);
4017 /* Handle def. */
4020 /* In case the vectorization factor (VF) is bigger than the number
4021 of elements that we can fit in a vectype (nunits), we have to generate
4022 more than one vector stmt - i.e - we need to "unroll" the
4023 vector stmt by a factor VF/nunits. */
4027 {
4028 /* Handle uses. */
4030 {
4034 }
4035 else
4036 {
4040 }
4042 /* Arguments are ready. Create the new vector stmt. We are creating
4043 two vector defs because the widened result does not fit in one vector.
4044 The vectorized stmt can be expressed as a call to a taregt builtin,
4045 or a using a tree-code. */
4046 /* Generate first half of the widened result: */
4051 else
4055 /* Generate second half of the widened result: */
4061 }
4065 }
4068 /* Function vect_strided_store_supported.
4070 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
4071 and FALSE otherwise. */
4073 static bool
4075 {
4081 /* Check that the operation is supported. */
4083 vectype);
4085 vectype);
4087 {
4091 }
4094 == CODE_FOR_nothing
4097 {
4101 }
4103 }
4106 /* Function vect_permute_store_chain.
4108 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4109 a power of 2, generate interleave_high/low stmts to reorder the data
4110 correctly for the stores. Return the final references for stores in
4111 RESULT_CHAIN.
4113 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4114 The input is 4 vectors each containing 8 elements. We assign a number to each
4115 element, the input sequence is:
4117 1st vec: 0 1 2 3 4 5 6 7
4118 2nd vec: 8 9 10 11 12 13 14 15
4119 3rd vec: 16 17 18 19 20 21 22 23
4120 4th vec: 24 25 26 27 28 29 30 31
4122 The output sequence should be:
4124 1st vec: 0 8 16 24 1 9 17 25
4125 2nd vec: 2 10 18 26 3 11 19 27
4126 3rd vec: 4 12 20 28 5 13 21 30
4127 4th vec: 6 14 22 30 7 15 23 31
4129 i.e., we interleave the contents of the four vectors in their order.
4131 We use interleave_high/low instructions to create such output. The input of
4132 each interleave_high/low operation is two vectors:
4133 1st vec 2nd vec
4134 0 1 2 3 4 5 6 7
4135 the even elements of the result vector are obtained left-to-right from the
4136 high/low elements of the first vector. The odd elements of the result are
4137 obtained left-to-right from the high/low elements of the second vector.
4138 The output of interleave_high will be: 0 4 1 5
4139 and of interleave_low: 2 6 3 7
4142 The permutation is done in log LENGTH stages. In each stage interleave_high
4143 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4144 where the first argument is taken from the first half of DR_CHAIN and the
4145 second argument from it's second half.
4146 In our example,
4148 I1: interleave_high (1st vec, 3rd vec)
4149 I2: interleave_low (1st vec, 3rd vec)
4150 I3: interleave_high (2nd vec, 4th vec)
4151 I4: interleave_low (2nd vec, 4th vec)
4153 The output for the first stage is:
4155 I1: 0 16 1 17 2 18 3 19
4156 I2: 4 20 5 21 6 22 7 23
4157 I3: 8 24 9 25 10 26 11 27
4158 I4: 12 28 13 29 14 30 15 31
4160 The output of the second stage, i.e. the final result is:
4162 I1: 0 8 16 24 1 9 17 25
4163 I2: 2 10 18 26 3 11 19 27
4164 I3: 4 12 20 28 5 13 21 30
4165 I4: 6 14 22 30 7 15 23 31. */
4167 static bool
4170 tree stmt,
4173 {
4185 /* Check that the operation is supported. */
4192 {
4194 {
4198 /* Create interleaving stmt:
4199 in the case of big endian:
4200 high = interleave_high (vect1, vect2)
4201 and in the case of little endian:
4202 high = interleave_low (vect1, vect2). */
4208 else
4216 /* Create interleaving stmt:
4217 in the case of big endian:
4218 low = interleave_low (vect1, vect2)
4219 and in the case of little endian:
4220 low = interleave_high (vect1, vect2). */
4226 else
4233 }
4235 }
4237 }
4240 /* Function vectorizable_store.
4242 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
4243 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
4250 {
4251 tree scalar_dest;
4252 tree data_ref;
4253 tree op;
4261 tree dummy;
4278 /* FORNOW. This restriction should be relaxed. */
4280 {
4284 }
4293 {
4297 }
4299 /* Is vectorizable store? */
4312 {
4316 }
4319 /* FORNOW. In some cases can vectorize even if data-type not supported
4320 (e.g. - array initialization with 0). */
4328 {
4332 }
4335 {
4339 }
4341 /** Transform. **/
4344 {
4351 /* FORNOW */
4354 /* We vectorize all the stmts of the interleaving group when we
4355 reach the last stmt in the group. */
4358 {
4361 }
4362 }
4363 else
4364 {
4368 }
4380 /* In case the vectorization factor (VF) is bigger than the number
4381 of elements that we can fit in a vectype (nunits), we have to generate
4382 more than one vector stmt - i.e - we need to "unroll" the
4383 vector stmt by a factor VF/nunits. For more details see documentation in
4384 vect_get_vec_def_for_copy_stmt. */
4386 /* In case of interleaving (non-unit strided access):
4388 S1: &base + 2 = x2
4389 S2: &base = x0
4390 S3: &base + 1 = x1
4391 S4: &base + 3 = x3
4393 We create vectorized stores starting from base address (the access of the
4394 first stmt in the chain (S2 in the above example), when the last store stmt
4395 of the chain (S4) is reached:
4397 VS1: &base = vx2
4398 VS2: &base + vec_size*1 = vx0
4399 VS3: &base + vec_size*2 = vx1
4400 VS4: &base + vec_size*3 = vx3
4402 Then permutation statements are generated:
4404 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
4405 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
4406 ...
4408 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
4409 (the order of the data-refs in the output of vect_permute_store_chain
4410 corresponds to the order of scalar stmts in the interleaving chain - see
4411 the documentation of vect_permute_store_chain()).
4413 In case of both multiple types and interleaving, above vector stores and
4414 permutation stmts are created for every copy. The result vector stmts are
4415 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
4416 STMT_VINFO_RELATED_STMT for the next copies.
4417 */
4421 {
4422 tree new_stmt;
4423 tree ptr_incr;
4426 {
4427 /* For interleaved stores we collect vectorized defs for all the
4428 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then used
4429 as an input to vect_permute_store_chain(), and OPRNDS as an input
4430 to vect_get_vec_def_for_stmt_copy() for the next copy.
4431 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4432 OPRNDS are of size 1. */
4435 {
4436 /* Since gaps are not supported for interleaved stores, GROUP_SIZE
4437 is the exact number of stmts in the chain. Therefore, NEXT_STMT
4438 can't be NULL_TREE. In case that there is no interleaving,
4439 GROUP_SIZE is 1, and only one iteration of the loop will be
4440 executed. */
4447 }
4452 }
4453 else
4454 {
4455 /* For interleaved stores we created vectorized defs for all the
4456 defs stored in OPRNDS in the previous iteration (previous copy).
4457 DR_CHAIN is then used as an input to vect_permute_store_chain(),
4458 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
4459 next copy.
4460 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4461 OPRNDS are of size 1. */
4463 {
4468 }
4469 dataref_ptr =
4471 }
4474 {
4476 /* Permute. */
4480 }
4484 {
4485 /* For strided stores vectorized defs are interleaved in
4486 vect_permute_store_chain(). */
4491 /* Arguments are ready. Create the new vector stmt. */
4498 else
4505 /* Bump the vector pointer. */
4506 dataref_ptr =
4508 }
4509 }
4512 }
4515 /* Function vect_setup_realignment
4517 This function is called when vectorizing an unaligned load using
4518 the dr_explicit_realign[_optimized] scheme.
4519 This function generates the following code at the loop prolog:
4521 p = initial_addr;
4522 x msq_init = *(floor(p)); # prolog load
4523 realignment_token = call target_builtin;
4524 loop:
4525 x msq = phi (msq_init, ---)
4527 The stmts marked with x are generated only for the case of
4528 dr_explicit_realign_optimized.
4530 The code above sets up a new (vector) pointer, pointing to the first
4531 location accessed by STMT, and a "floor-aligned" load using that pointer.
4532 It also generates code to compute the "realignment-token" (if the relevant
4533 target hook was defined), and creates a phi-node at the loop-header bb
4534 whose arguments are the result of the prolog-load (created by this
4535 function) and the result of a load that takes place in the loop (to be
4536 created by the caller to this function).
4538 For the case of dr_explicit_realign_optimized:
4539 The caller to this function uses the phi-result (msq) to create the
4540 realignment code inside the loop, and sets up the missing phi argument,
4541 as follows:
4542 loop:
4543 msq = phi (msq_init, lsq)
4544 lsq = *(floor(p')); # load in loop
4545 result = realign_load (msq, lsq, realignment_token);
4547 For the case of dr_explicit_realign:
4548 loop:
4549 msq = *(floor(p)); # load in loop
4550 p' = p + (VS-1);
4551 lsq = *(floor(p')); # load in loop
4552 result = realign_load (msq, lsq, realignment_token);
4554 Input:
4555 STMT - (scalar) load stmt to be vectorized. This load accesses
4556 a memory location that may be unaligned.
4557 BSI - place where new code is to be inserted.
4558 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
4559 is used.
4561 Output:
4562 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4563 target hook, if defined.
4564 Return value - the result of the loop-header phi node. */
4566 static tree
4570 tree init_addr,
4572 {
4577 edge pe;
4579 tree vec_dest;
4580 tree inc;
4581 tree ptr;
4582 tree data_ref;
4583 tree new_stmt;
4584 basic_block new_bb;
4586 tree new_temp;
4587 tree phi_stmt;
4599 /* We need to generate three things:
4600 1. the misalignment computation
4601 2. the extra vector load (for the optimized realignment scheme).
4602 3. the phi node for the two vectors from which the realignment is
4603 done (for the optimized realignment scheme).
4604 */
4606 /* 1. Determine where to generate the misalignment computation.
4608 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
4609 calculation will be generated by this function, outside the loop (in the
4610 preheader). Otherwise, INIT_ADDR had already been computed for us by the
4611 caller, inside the loop.
4613 Background: If the misalignment remains fixed throughout the iterations of
4614 the loop, then both realignment schemes are applicable, and also the
4615 misalignment computation can be done outside LOOP. This is because we are
4616 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
4617 are a multiple of VS (the Vector Size), and therefore the misalignment in
4618 different vectorized LOOP iterations is always the same.
4619 The problem arises only if the memory access is in an inner-loop nested
4620 inside LOOP, which is now being vectorized using outer-loop vectorization.
4621 This is the only case when the misalignment of the memory access may not
4622 remain fixed thtoughout the iterations of the inner-loop (as exaplained in
4623 detail in vect_supportable_dr_alignment). In this case, not only is the
4624 optimized realignment scheme not applicable, but also the misalignment
4625 computation (and generation of the realignment token that is passed to
4626 REALIGN_LOAD) have to be done inside the loop.
4628 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
4629 or not, which in turn determines if the misalignment is computed inside
4630 the inner-loop, or outside LOOP. */
4633 {
4636 }
4639 /* 2. Determine where to generate the extra vector load.
4641 For the optimized realignment scheme, instead of generating two vector
4642 loads in each iteration, we generate a single extra vector load in the
4643 preheader of the loop, and in each iteration reuse the result of the
4644 vector load from the previous iteration. In case the memory access is in
4645 an inner-loop nested inside LOOP, which is now being vectorized using
4646 outer-loop vectorization, we need to determine whether this initial vector
4647 load should be generated at the preheader of the inner-loop, or can be
4648 generated at the preheader of LOOP. If the memory access has no evolution
4649 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
4650 to be generated inside LOOP (in the preheader of the inner-loop). */
4653 {
4658 }
4659 else
4664 /* 3. For the case of the optimized realignment, create the first vector
4665 load at the loop preheader. */
4668 {
4669 /* Create msq_init = *(floor(p1)) in the loop preheader */
4683 }
4685 /* 4. Create realignment token using a target builtin, if available.
4686 It is done either inside the containing loop, or before LOOP (as
4687 determined above). */
4690 {
4691 tree builtin_decl;
4693 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
4696 else
4697 {
4698 /* Generate the INIT_ADDR computation outside LOOP. */
4704 }
4716 else
4717 {
4718 /* Generate the misalignment computation outside LOOP. */
4722 }
4726 /* The result of the CALL_EXPR to this builtin is determined from
4727 the value of the parameter and no global variables are touched
4728 which makes the builtin a "const" function. Requiring the
4729 builtin to have the "const" attribute makes it unnecessary
4730 to call mark_call_clobbered. */
4732 }
4741 /* 5. Create msq = phi <msq_init, lsq> in loop */
4751 }
4754 /* Function vect_strided_load_supported.
4756 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
4757 and FALSE otherwise. */
4759 static bool
4761 {
4769 {
4773 }
4776 {
4780 }
4784 {
4788 }
4791 {
4795 }
4797 }
4800 /* Function vect_permute_load_chain.
4802 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
4803 a power of 2, generate extract_even/odd stmts to reorder the input data
4804 correctly. Return the final references for loads in RESULT_CHAIN.
4806 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4807 The input is 4 vectors each containing 8 elements. We assign a number to each
4808 element, the input sequence is:
4810 1st vec: 0 1 2 3 4 5 6 7
4811 2nd vec: 8 9 10 11 12 13 14 15
4812 3rd vec: 16 17 18 19 20 21 22 23
4813 4th vec: 24 25 26 27 28 29 30 31
4815 The output sequence should be:
4817 1st vec: 0 4 8 12 16 20 24 28
4818 2nd vec: 1 5 9 13 17 21 25 29
4819 3rd vec: 2 6 10 14 18 22 26 30
4820 4th vec: 3 7 11 15 19 23 27 31
4822 i.e., the first output vector should contain the first elements of each
4823 interleaving group, etc.
4825 We use extract_even/odd instructions to create such output. The input of each
4826 extract_even/odd operation is two vectors
4827 1st vec 2nd vec
4828 0 1 2 3 4 5 6 7
4830 and the output is the vector of extracted even/odd elements. The output of
4831 extract_even will be: 0 2 4 6
4832 and of extract_odd: 1 3 5 7
4835 The permutation is done in log LENGTH stages. In each stage extract_even and
4836 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
4837 order. In our example,
4839 E1: extract_even (1st vec, 2nd vec)
4840 E2: extract_odd (1st vec, 2nd vec)
4841 E3: extract_even (3rd vec, 4th vec)
4842 E4: extract_odd (3rd vec, 4th vec)
4844 The output for the first stage will be:
4846 E1: 0 2 4 6 8 10 12 14
4847 E2: 1 3 5 7 9 11 13 15
4848 E3: 16 18 20 22 24 26 28 30
4849 E4: 17 19 21 23 25 27 29 31
4851 In order to proceed and create the correct sequence for the next stage (or
4852 for the correct output, if the second stage is the last one, as in our
4853 example), we first put the output of extract_even operation and then the
4854 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
4855 The input for the second stage is:
4857 1st vec (E1): 0 2 4 6 8 10 12 14
4858 2nd vec (E3): 16 18 20 22 24 26 28 30
4859 3rd vec (E2): 1 3 5 7 9 11 13 15
4860 4th vec (E4): 17 19 21 23 25 27 29 31
4862 The output of the second stage:
4864 E1: 0 4 8 12 16 20 24 28
4865 E2: 2 6 10 14 18 22 26 30
4866 E3: 1 5 9 13 17 21 25 29
4867 E4: 3 7 11 15 19 23 27 31
4869 And RESULT_CHAIN after reordering:
4871 1st vec (E1): 0 4 8 12 16 20 24 28
4872 2nd vec (E3): 1 5 9 13 17 21 25 29
4873 3rd vec (E2): 2 6 10 14 18 22 26 30
4874 4th vec (E4): 3 7 11 15 19 23 27 31. */
4876 static bool
4879 tree stmt,
4882 {
4885 tree tmp;
4889 /* Check that the operation is supported. */
4895 {
4897 {
4901 /* data_ref = permute_even (first_data_ref, second_data_ref); */
4917 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
4931 }
4933 }
4935 }
4938 /* Function vect_transform_strided_load.
4940 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
4941 to perform their permutation and ascribe the result vectorized statements to
4942 the scalar statements.
4943 */
4945 static bool
4948 {
4954 tree tmp_data_ref;
4956 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
4957 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
4958 vectors, that are ready for vector computation. */
4960 /* Permute. */
4964 /* Put a permuted data-ref in the VECTORIZED_STMT field.
4965 Since we scan the chain starting from it's first node, their order
4966 corresponds the order of data-refs in RESULT_CHAIN. */
4970 {
4974 /* Skip the gaps. Loads created for the gaps will be removed by dead
4975 code elimination pass later.
4976 DR_GROUP_GAP is the number of steps in elements from the previous
4977 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
4978 correspond to the gaps.
4979 */
4981 {
4982 gap_count++;
4984 }
4987 {
4989 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
4990 copies, and we put the new vector statement in the first available
4991 RELATED_STMT. */
4994 else
4995 {
5000 {
5003 }
5005 }
5008 /* If NEXT_STMT accesses the same DR as the previous statement,
5009 put the same TMP_DATA_REF as its vectorized statement; otherwise
5010 get the next data-ref from RESULT_CHAIN. */
5013 }
5014 }
5016 }
5019 /* vectorizable_load.
5021 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
5022 can be vectorized.
5023 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5024 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5025 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5027 bool
5029 {
5030 tree scalar_dest;
5033 tree op;
5035 stmt_vec_info prev_stmt_info;
5042 tree new_temp;
5045 tree dummy;
5048 tree ptr_incr;
5058 tree first_stmt;
5059 tree scalar_type;
5066 /* FORNOW. This restriction should be relaxed. */
5068 {
5072 }
5080 /* FORNOW: not yet supported. */
5082 {
5086 }
5088 /* Is vectorizable load? */
5108 /* FORNOW. In some cases can vectorize even if data-type not supported
5109 (e.g. - data copies). */
5111 {
5115 }
5117 /* Check if the load is a part of an interleaving chain. */
5119 {
5121 /* FORNOW */
5124 /* Check if interleaving is supported. */
5127 }
5130 {
5134 }
5139 /** Transform. **/
5142 {
5144 /* Check if the chain of loads is already vectorized. */
5146 {
5149 }
5153 }
5154 else
5155 {
5159 }
5164 /* In case the vectorization factor (VF) is bigger than the number
5165 of elements that we can fit in a vectype (nunits), we have to generate
5166 more than one vector stmt - i.e - we need to "unroll" the
5167 vector stmt by a factor VF/nunits. In doing so, we record a pointer
5168 from one copy of the vector stmt to the next, in the field
5169 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
5170 stages to find the correct vector defs to be used when vectorizing
5171 stmts that use the defs of the current stmt. The example below illustrates
5172 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
5173 4 vectorized stmts):
5175 before vectorization:
5176 RELATED_STMT VEC_STMT
5177 S1: x = memref - -
5178 S2: z = x + 1 - -
5180 step 1: vectorize stmt S1:
5181 We first create the vector stmt VS1_0, and, as usual, record a
5182 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
5183 Next, we create the vector stmt VS1_1, and record a pointer to
5184 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
5185 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
5186 stmts and pointers:
5187 RELATED_STMT VEC_STMT
5188 VS1_0: vx0 = memref0 VS1_1 -
5189 VS1_1: vx1 = memref1 VS1_2 -
5190 VS1_2: vx2 = memref2 VS1_3 -
5191 VS1_3: vx3 = memref3 - -
5192 S1: x = load - VS1_0
5193 S2: z = x + 1 - -
5195 See in documentation in vect_get_vec_def_for_stmt_copy for how the
5196 information we recorded in RELATED_STMT field is used to vectorize
5197 stmt S2. */
5199 /* In case of interleaving (non-unit strided access):
5201 S1: x2 = &base + 2
5202 S2: x0 = &base
5203 S3: x1 = &base + 1
5204 S4: x3 = &base + 3
5206 Vectorized loads are created in the order of memory accesses
5207 starting from the access of the first stmt of the chain:
5209 VS1: vx0 = &base
5210 VS2: vx1 = &base + vec_size*1
5211 VS3: vx3 = &base + vec_size*2
5212 VS4: vx4 = &base + vec_size*3
5214 Then permutation statements are generated:
5216 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
5217 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
5218 ...
5220 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
5221 (the order of the data-refs in the output of vect_permute_load_chain
5222 corresponds to the order of scalar stmts in the interleaving chain - see
5223 the documentation of vect_permute_load_chain()).
5224 The generation of permutation stmts and recording them in
5225 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
5227 In case of both multiple types and interleaving, the vector loads and
5228 permutation stmts above are created for every copy. The result vector stmts
5229 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
5230 STMT_VINFO_RELATED_STMT for the next copies. */
5232 /* If the data reference is aligned (dr_aligned) or potentially unaligned
5233 on a target that supports unaligned accesses (dr_unaligned_supported)
5234 we generate the following code:
5235 p = initial_addr;
5236 indx = 0;
5237 loop {
5238 p = p + indx * vectype_size;
5239 vec_dest = *(p);
5240 indx = indx + 1;
5241 }
5243 Otherwise, the data reference is potentially unaligned on a target that
5244 does not support unaligned accesses (dr_explicit_realign_optimized) -
5245 then generate the following code, in which the data in each iteration is
5246 obtained by two vector loads, one from the previous iteration, and one
5247 from the current iteration:
5248 p1 = initial_addr;
5249 msq_init = *(floor(p1))
5250 p2 = initial_addr + VS - 1;
5251 realignment_token = call target_builtin;
5252 indx = 0;
5253 loop {
5254 p2 = p2 + indx * vectype_size
5255 lsq = *(floor(p2))
5256 vec_dest = realign_load (msq, lsq, realignment_token)
5257 indx = indx + 1;
5258 msq = lsq;
5259 } */
5261 /* If the misalignment remains the same throughout the execution of the
5262 loop, we can create the init_addr and permutation mask at the loop
5263 preheader. Otherwise, it needs to be created inside the loop.
5264 This can only occur when vectorizing memory accesses in the inner-loop
5265 nested within an outer-loop that is being vectorized. */
5269 {
5272 }
5277 {
5282 {
5285 }
5286 }
5287 else
5292 {
5293 /* 1. Create the vector pointer update chain. */
5299 else
5300 dataref_ptr =
5304 {
5305 /* 2. Create the vector-load in the loop. */
5307 {
5313 {
5318 data_ref =
5321 }
5323 {
5330 dr_explicit_realign,
5348 }
5354 }
5362 /* 3. Handle explicit realignment if necessary/supported. Create in
5363 loop: vec_dest = realign_load (msq, lsq, realignment_token) */
5366 {
5372 realignment_token);
5379 {
5383 }
5384 }
5386 /* 4. Handle invariant-load. */
5388 {
5392 {
5397 /* CHECKME: bitpos depends on endianess? */
5403 vec_dest =
5412 /* FIXME: use build_constructor directly. */
5416 }
5417 else
5419 }
5424 dataref_ptr =
5426 }
5429 {
5434 }
5435 else
5436 {
5439 else
5442 }
5443 }
5446 }
5449 /* Function vectorizable_live_operation.
5451 STMT computes a value that is used outside the loop. Check if
5452 it can be supported. */
5454 bool
5458 {
5459 tree operation;
5465 tree op;
5480 /* FORNOW. CHECKME. */
5487 /* FORNOW: support only if all uses are invariant. This means
5488 that the scalar operations can remain in place, unvectorized.
5489 The original last scalar value that they compute will be used. */
5492 {
5495 {
5499 }
5503 }
5505 /* No transformation is required for the cases we currently support. */
5507 }
5510 /* Function vect_is_simple_cond.
5512 Input:
5513 LOOP - the loop that is being vectorized.
5514 COND - Condition that is checked for simple use.
5516 Returns whether a COND can be vectorized. Checks whether
5517 condition operands are supportable using vec_is_simple_use. */
5519 static bool
5521 {
5523 tree def;
5533 {
5537 }
5543 {
5547 }
5553 }
5555 /* vectorizable_condition.
5557 Check if STMT is conditional modify expression that can be vectorized.
5558 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5559 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
5560 at BSI.
5562 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5564 bool
5566 {
5575 tree new_temp;
5578 tree def;
5593 /* FORNOW: not yet supported. */
5595 {
5599 }
5601 /* Is vectorizable conditional operation? */
5617 /* We do not handle two different vector types for the condition
5618 and the values. */
5623 {
5628 }
5635 {
5640 }
5650 {
5653 }
5655 /* Transform */
5657 /* Handle def. */
5661 /* Handle cond expr. */
5662 vec_cond_lhs =
5664 vec_cond_rhs =
5669 /* Arguments are ready. create the new vector stmt. */
5681 }
5683 /* Function vect_transform_stmt.
5685 Create a vectorized stmt to replace STMT, and insert it at BSI. */
5687 bool
5689 {
5693 tree orig_stmt_in_pattern;
5697 {
5737 {
5738 /* In case of interleaving, the whole chain is vectorized when the
5739 last store in the chain is reached. Store stmts before the last
5740 one are skipped, and there vec_stmt_info shouldn't be freed
5741 meanwhile. */
5745 }
5746 else
5766 {
5770 }
5771 }
5775 {
5778 }
5781 {
5785 {
5787 /* STMT was inserted by the vectorizer to replace a computation idiom.
5788 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
5789 computed this idiom. We need to record a pointer to VEC_STMT in
5790 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
5791 documentation of vect_pattern_recog. */
5793 {
5796 }
5797 }
5798 }
5801 }
5804 /* This function builds ni_name = number of iterations loop executes
5805 on the loop preheader. */
5807 static tree
5809 {
5811 edge pe;
5821 {
5824 }
5827 }
5830 /* This function generates the following statements:
5832 ni_name = number of iterations loop executes
5833 ratio = ni_name / vf
5834 ratio_mult_vf_name = ratio * vf
5836 and places them at the loop preheader edge. */
5838 static void
5843 {
5845 edge pe;
5846 basic_block new_bb;
5848 tree var;
5849 tree ratio_name;
5850 tree ratio_mult_vf_name;
5854 tree log_vf;
5858 /* Generate temporary variable that contains
5859 number of iterations loop executes. */
5864 /* Create: ratio = ni >> log2(vf) */
5868 {
5876 }
5878 /* Create: ratio_mult_vf = ratio << log2 (vf). */
5883 {
5892 }
5899 }
5902 /* Function vect_update_ivs_after_vectorizer.
5904 "Advance" the induction variables of LOOP to the value they should take
5905 after the execution of LOOP. This is currently necessary because the
5906 vectorizer does not handle induction variables that are used after the
5907 loop. Such a situation occurs when the last iterations of LOOP are
5908 peeled, because:
5909 1. We introduced new uses after LOOP for IVs that were not originally used
5910 after LOOP: the IVs of LOOP are now used by an epilog loop.
5911 2. LOOP is going to be vectorized; this means that it will iterate N/VF
5912 times, whereas the loop IVs should be bumped N times.
5914 Input:
5915 - LOOP - a loop that is going to be vectorized. The last few iterations
5916 of LOOP were peeled.
5917 - NITERS - the number of iterations that LOOP executes (before it is
5918 vectorized). i.e, the number of times the ivs should be bumped.
5919 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
5920 coming out from LOOP on which there are uses of the LOOP ivs
5921 (this is the path from LOOP->exit to epilog_loop->preheader).
5923 The new definitions of the ivs are placed in LOOP->exit.
5924 The phi args associated with the edge UPDATE_E in the bb
5925 UPDATE_E->dest are updated accordingly.
5927 Assumption 1: Like the rest of the vectorizer, this function assumes
5928 a single loop exit that has a single predecessor.
5930 Assumption 2: The phi nodes in the LOOP header and in update_bb are
5931 organized in the same order.
5933 Assumption 3: The access function of the ivs is simple enough (see
5934 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
5936 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
5937 coming out of LOOP on which the ivs of LOOP are used (this is the path
5938 that leads to the epilog loop; other paths skip the epilog loop). This
5939 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
5940 needs to have its phis updated.
5941 */
5943 static void
5945 edge update_e)
5946 {
5952 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
5954 /* Make sure there exists a single-predecessor exit bb: */
5960 {
5962 tree evolution_part;
5963 tree init_expr;
5964 tree step_expr;
5966 block_stmt_iterator last_bsi;
5969 {
5972 }
5974 /* Skip virtual phi's. */
5976 {
5980 }
5982 /* Skip reduction phis. */
5984 {
5988 }
5992 evolution_part =
5996 /* FORNOW: We do not support IVs whose evolution function is a polynomial
5997 of degree >= 2 or exponential. */
6006 init_expr,
6010 else
6014 niters),
6015 step_expr),
6016 init_expr);
6027 /* Fix phi expressions in the successor bb. */
6029 }
6030 }
6033 /* Function vect_do_peeling_for_loop_bound
6035 Peel the last iterations of the loop represented by LOOP_VINFO.
6036 The peeled iterations form a new epilog loop. Given that the loop now
6037 iterates NITERS times, the new epilog loop iterates
6038 NITERS % VECTORIZATION_FACTOR times.
6040 The original loop will later be made to iterate
6041 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
6043 static void
6045 {
6049 edge update_e;
6050 basic_block preheader;
6061 /* Generate the following variables on the preheader of original loop:
6063 ni_name = number of iteration the original loop executes
6064 ratio = ni_name / vf
6065 ratio_mult_vf_name = ratio * vf */
6071 /* Analyze cost to set threshhold for vectorized loop. */
6076 /* Use the cost model only if it is more conservative than user specified
6077 threshold. */
6081 && (!min_scalar_loop_bound
6092 th);
6095 #ifdef ENABLE_CHECKING
6097 #endif
6099 /* A guard that controls whether the new_loop is to be executed or skipped
6100 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
6101 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
6102 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
6103 is on the path where the LOOP IVs are used and need to be updated. */
6108 else
6111 /* Update IVs of original loop as if they were advanced
6112 by ratio_mult_vf_name steps. */
6115 /* After peeling we have to reset scalar evolution analyzer. */
6119 }
6122 /* Function vect_gen_niters_for_prolog_loop
6124 Set the number of iterations for the loop represented by LOOP_VINFO
6125 to the minimum between LOOP_NITERS (the original iteration count of the loop)
6126 and the misalignment of DR - the data reference recorded in
6127 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
6128 this loop, the data reference DR will refer to an aligned location.
6130 The following computation is generated:
6132 If the misalignment of DR is known at compile time:
6133 addr_mis = int mis = DR_MISALIGNMENT (dr);
6134 Else, compute address misalignment in bytes:
6135 addr_mis = addr & (vectype_size - 1)
6137 prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
6139 (elem_size = element type size; an element is the scalar element
6140 whose type is the inner type of the vectype)
6142 For interleaving,
6144 prolog_niters = min ( LOOP_NITERS ,
6145 (VF/group_size - addr_mis/elem_size)&(VF/group_size-1) )
6146 where group_size is the size of the interleaved group.
6148 The above formulas assume that VF == number of elements in the vector. This
6149 may not hold when there are multiple-types in the loop.
6150 In this case, for some data-references in the loop the VF does not represent
6151 the number of elements that fit in the vector. Therefore, instead of VF we
6152 use TYPE_VECTOR_SUBPARTS. */
6154 static tree
6156 {
6161 edge pe;
6162 basic_block new_bb;
6173 {
6174 /* For interleaved access element size must be multiplied by the size of
6175 the interleaved group. */
6179 }
6184 {
6192 }
6193 else
6194 {
6202 tree elem_size_log =
6206 tree byte_misalign;
6207 tree elem_misalign;
6212 /* Create: byte_misalign = addr & (vectype_size - 1) */
6213 byte_misalign =
6216 /* Create: elem_misalign = byte_misalign / element_size */
6217 elem_misalign =
6220 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
6224 }
6226 /* Create: prolog_loop_niters = min (iters, loop_niters) */
6227 /* If the loop bound is known at compile time we already verified that it is
6228 greater than vf; since the misalignment ('iters') is at most vf, there's
6229 no need to generate the MIN_EXPR in this case. */
6234 {
6237 }
6243 /* Insert stmt on loop preheader edge. */
6245 {
6248 }
6251 }
6254 /* Function vect_update_init_of_dr
6256 NITERS iterations were peeled from LOOP. DR represents a data reference
6257 in LOOP. This function updates the information recorded in DR to
6258 account for the fact that the first NITERS iterations had already been
6259 executed. Specifically, it updates the OFFSET field of DR. */
6261 static void
6263 {
6269 }
6272 /* Function vect_update_inits_of_drs
6274 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
6275 This function updates the information recorded for the data references in
6276 the loop to account for the fact that the first NITERS iterations had
6277 already been executed. Specifically, it updates the initial_condition of
6278 the access_function of all the data_references in the loop. */
6280 static void
6282 {
6292 }
6295 /* Function vect_do_peeling_for_alignment
6297 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
6298 'niters' is set to the misalignment of one of the data references in the
6299 loop, thereby forcing it to refer to an aligned location at the beginning
6300 of the execution of this loop. The data reference for which we are
6301 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
6303 static void
6305 {
6308 tree n_iters;
6319 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
6320 new_loop =
6324 #ifdef ENABLE_CHECKING
6326 #endif
6328 /* Update number of times loop executes. */
6333 /* Update the init conditions of the access functions of all data refs. */
6336 /* After peeling we have to reset scalar evolution analyzer. */
6340 }
6343 /* Function vect_create_cond_for_align_checks.
6345 Create a conditional expression that represents the alignment checks for
6346 all of data references (array element references) whose alignment must be
6347 checked at runtime.
6349 Input:
6350 LOOP_VINFO - two fields of the loop information are used.
6351 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
6352 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
6354 Output:
6355 COND_EXPR_STMT_LIST - statements needed to construct the conditional
6356 expression.
6357 The returned value is the conditional expression to be used in the if
6358 statement that controls which version of the loop gets executed at runtime.
6360 The algorithm makes two assumptions:
6361 1) The number of bytes "n" in a vector is a power of 2.
6362 2) An address "a" is aligned if a%n is zero and that this
6363 test can be done as a&(n-1) == 0. For example, for 16
6364 byte vectors the test is a&0xf == 0. */
6366 static tree
6369 {
6375 tree mask_cst;
6377 tree psize;
6378 tree int_ptrsize_type;
6382 tree ptrsize_zero;
6384 /* Check that mask is one less than a power of 2, i.e., mask is
6385 all zeros followed by all ones. */
6388 /* CHECKME: what is the best integer or unsigned type to use to hold a
6389 cast from a pointer value? */
6391 int_ptrsize_type
6394 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
6395 of the first vector of the i'th data reference. */
6398 {
6400 tree addr_base;
6404 /* create: addr_tmp = (int)(address_of_first_vector) */
6420 /* The addresses are OR together. */
6423 {
6424 /* create: or_tmp = or_tmp | addr_tmp */
6435 }
6436 else
6443 /* create: and_tmp = or_tmp & mask */
6453 /* Make and_tmp the left operand of the conditional test against zero.
6454 if and_tmp has a nonzero bit then some address is unaligned. */
6458 }
6460 /* Function vect_vfa_segment_size.
6462 Create an expression that computes the size of segment
6463 that will be accessed for a data reference. The functions takes into
6464 account that realignment loads may access one more vector.
6466 Input:
6467 DR: The data reference.
6468 VECT_FACTOR: vectorization factor.
6470 Return an exrpession whose value is the size of segment which will be
6471 accessed by DR. */
6473 static tree
6475 {
6476 tree segment_length;
6479 {
6480 tree vector_size =
6485 segment_length =
6489 vect_factor),
6490 vector_size));
6491 }
6492 else
6493 {
6494 segment_length =
6497 vect_factor));
6498 }
6501 }
6503 /* Function vect_create_cond_for_alias_checks.
6505 Create a conditional expression that represents the run-time checks for
6506 overlapping of address ranges represented by a list of data references
6507 relations passed as input.
6509 Input:
6510 COND_EXPR - input conditional expression. New conditions will be chained
6511 with logical and operation.
6512 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
6513 to be checked.
6515 Output:
6516 COND_EXPR - conditional expression.
6517 COND_EXPR_STMT_LIST - statements needed to construct the conditional
6518 expression.
6519 The returned value is the conditional expression to be used in the if
6520 statement that controls which version of the loop gets executed at runtime.
6521 */
6523 static void
6527 {
6531 tree vect_factor =
6534 ddr_p ddr;
6536 tree part_cond_expr;
6538 /* Create expression
6539 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
6540 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
6541 &&
6542 ...
6543 &&
6544 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
6545 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
6551 {
6555 tree addr_base_a =
6558 tree addr_base_b =
6566 {
6572 }
6575 part_cond_expr =
6579 addr_base_a,
6580 segment_length_a),
6581 addr_base_b),
6584 addr_base_b,
6585 segment_length_b),
6586 addr_base_a));
6591 else
6593 }
6598 }
6600 /* Function vect_transform_loop.
6602 The analysis phase has determined that the loop is vectorizable.
6603 Vectorize the loop - created vectorized stmts to replace the scalar
6604 stmts in the loop, and update the loop exit condition. */
6606 void
6608 {
6621 /* If the loop has data references that may or may not be aligned or/and
6622 has data reference relations whose independence was not proven then
6623 two versions of the loop need to be generated, one which is vectorized
6624 and one which isn't. A test is then generated to control which of the
6625 loops is executed. The test checks for the alignment of all of the
6626 data references that may or may not be aligned. An additional
6627 sequence of runtime tests is generated for each pairs of DDRs whose
6628 independence was not proven. The vectorized version of loop is
6629 executed only if both alias and alignment tests are passed. */
6633 {
6637 basic_block condition_bb;
6638 block_stmt_iterator cond_exp_bsi;
6639 basic_block merge_bb;
6640 basic_block new_exit_bb;
6644 tree gimplify_stmt_list;
6647 cond_expr =
6654 cond_expr =
6656 cond_expr =
6658 NULL_TREE);
6666 /** Loop versioning violates an assumption we try to maintain during
6667 vectorization - that the loop exit block has a single predecessor.
6668 After versioning, the exit block of both loop versions is the same
6669 basic block (i.e. it has two predecessors). Just in order to simplify
6670 following transformations in the vectorizer, we fix this situation
6671 here by adding a new (empty) block on the exit-edge of the loop,
6672 with the proper loop-exit phis to maintain loop-closed-form. **/
6682 {
6684 new_exit_bb);
6688 }
6690 /** end loop-exit-fixes after versioning **/
6695 }
6697 /* CHECKME: we wouldn't need this if we called update_ssa once
6698 for all loops. */
6701 /* Peel the loop if there are data refs with unknown alignment.
6702 Only one data ref with unknown store is allowed. */
6707 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
6708 compile time constant), or it is a constant that doesn't divide by the
6709 vectorization factor, then an epilog loop needs to be created.
6710 We therefore duplicate the loop: the original loop will be vectorized,
6711 and will compute the first (n/VF) iterations. The second copy of the loop
6712 will remain scalar and will compute the remaining (n%VF) iterations.
6713 (VF is the vectorization factor). */
6719 else
6723 /* 1) Make sure the loop header has exactly two entries
6724 2) Make sure we have a preheader basic block. */
6730 /* FORNOW: the vectorizer supports only loops which body consist
6731 of one basic block (header + empty latch). When the vectorizer will
6732 support more involved loop forms, the order by which the BBs are
6733 traversed need to be reconsidered. */
6736 {
6738 stmt_vec_info stmt_info;
6739 tree phi;
6742 {
6744 {
6747 }
6761 {
6765 }
6766 }
6769 {
6774 {
6777 }
6781 /* vector stmts created in the outer-loop during vectorization of
6782 stmts in an inner-loop may not have a stmt_info, and do not
6783 need to be vectorized. */
6785 {
6788 }
6792 {
6795 }
6803 /* -------- vectorize statement ------------ */
6810 {
6811 stmt_ann_t ann;
6813 {
6814 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
6815 interleaving chain was completed - free all the stores in
6816 the chain. */
6818 tree tmp;
6819 stmt_vec_info next_stmt_info;
6822 {
6825 /* Free the attached stmt_vec_info and remove the stmt. */
6832 }
6835 }
6836 else
6837 {
6838 /* Free the attached stmt_vec_info and remove the stmt. */
6844 }
6845 }
6854 /* The memory tags and pointers in vectorized statements need to
6855 have their SSA forms updated. FIXME, why can't this be delayed
6856 until all the loops have been transformed? */
6863 }