| blob | f02d912b29f63bc9f027cd2a6aa329e0a62eb626 |
1 /* Transformation Utilities for Loop Vectorization.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
48 /* Utility functions for the code transformation. */
51 static tree vect_create_data_ref_ptr
53 static tree vect_create_addr_base_for_vector_ref
58 static void vect_finish_stmt_generation
64 /* Utility function dealing with loop peeling (not peeling itself). */
65 static void vect_generate_tmps_on_preheader
75 static int
77 {
81 {
99 }
100 }
103 /* Function vect_estimate_min_profitable_iters
105 Return the number of iterations required for the vector version of the
106 loop to be profitable relative to the cost of the scalar version of the
107 loop.
109 TODO: Take profile info into account before making vectorization
110 decisions, if available. */
112 int
114 {
130 slp_instance instance;
132 /* Cost model disabled. */
134 {
138 }
140 /* Requires loop versioning tests to handle misalignment. */
143 {
144 /* FIXME: Make cost depend on complexity of individual check. */
145 vec_outside_cost +=
150 }
153 {
154 /* FIXME: Make cost depend on complexity of individual check. */
155 vec_outside_cost +=
160 }
164 {
166 }
168 /* Count statements in scalar loop. Using this as scalar cost for a single
169 iteration for now.
171 TODO: Add outer loop support.
173 TODO: Consider assigning different costs to different scalar
174 statements. */
176 /* FORNOW. */
181 {
182 block_stmt_iterator si;
187 else
191 {
199 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
200 some of the "outside" costs are generated inside the outer-loop. */
202 }
203 }
205 /* Add additional cost for the peeled instructions in prologue and epilogue
206 loop.
208 FORNOW: If we dont know the value of peel_iters for prologue or epilogue
209 at compile-time - we assume it's vf/2 (the worst would be vf-1).
211 TODO: Build an expression that represents peel_iters for prologue and
212 epilogue to be used in a run-time test. */
217 {
223 /* If peeling for alignment is unknown, loop bound of main loop becomes
224 unknown. */
228 "epilogue peel iters set to vf/2 because "
231 /* If peeled iterations are unknown, count a taken branch and a not taken
232 branch per peeled loop. Even if scalar loop iterations are known,
233 vector iterations are not known since peeled prologue iterations are
234 not known. Hence guards remain the same. */
238 }
239 else
240 {
242 {
249 }
250 else
254 {
258 "epilogue peel iters set to vf/2 because "
261 /* If peeled iterations are known but number of scalar loop
262 iterations are unknown, count a taken branch per peeled loop. */
265 }
266 else
267 {
272 }
273 }
279 /* Allow targets add additional (outside-of-loop) costs. FORNOW, the only
280 information we provide for the target is whether testing against the
281 threshold involves a runtime test. */
283 {
286 /* If the number of iterations is unknown, or the
287 peeling-for-misalignment amount is unknown, we eill have to generate
288 a runtime test to test the loop count against the threshold. */
292 vec_outside_cost +=
297 }
299 /* Add SLP costs. */
302 {
305 }
307 /* Calculate number of iterations required to make the vector version
308 profitable, relative to the loop bodies only. The following condition
309 must hold true: ((SIC*VF)-VIC)*niters > VOC*VF, where
310 SIC = scalar iteration cost, VIC = vector iteration cost,
311 VOC = vector outside cost and VF = vectorization factor. */
314 {
317 else
318 {
328 min_profitable_iters++;
329 }
330 }
331 /* vector version will never be profitable. */
332 else
333 {
336 "is divisible by scalar iteration cost = %d by a factor "
340 }
343 {
346 vec_inside_cost);
348 vec_outside_cost);
351 peel_iters_prologue);
353 peel_iters_epilogue);
355 min_profitable_iters);
356 }
358 min_profitable_iters =
361 /* Because the condition we create is:
362 if (niters <= min_profitable_iters)
363 then skip the vectorized loop. */
364 min_profitable_iters--;
368 min_profitable_iters);
371 }
374 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
375 functions. Design better to avoid maintenance issues. */
377 /* Function vect_model_reduction_cost.
379 Models cost for a reduction operation, including the vector ops
380 generated within the strip-mine loop, the initial definition before
381 the loop, and the epilogue code that must be generated. */
383 static void
386 {
389 optab optab;
390 tree vectype;
391 tree orig_stmt;
392 tree reduction_op;
399 /* Cost of reduction op inside loop. */
412 /* Add in cost for initial definition. */
415 /* Determine cost of epilogue code.
417 We have a reduction operator that will reduce the vector in one statement.
418 Also requires scalar extract. */
421 {
424 else
425 {
427 tree bitsize =
434 /* We have a whole vector shift available. */
438 /* Final reduction via vector shifts and the reduction operator. Also
439 requires scalar extract. */
442 else
443 /* Use extracts and reduction op for final reduction. For N elements,
444 we have N extracts and N-1 reduction ops. */
446 }
447 }
455 }
458 /* Function vect_model_induction_cost.
460 Models cost for induction operations. */
462 static void
464 {
465 /* loop cost for vec_loop. */
467 /* prologue cost for vec_init and vec_step. */
474 }
477 /* Function vect_model_simple_cost.
479 Models cost for simple operations, i.e. those that only emit ncopies of a
480 single op. Right now, this does not account for multiple insns that could
481 be generated for the single vector op. We will handle that shortly. */
483 void
486 {
492 /* FORNOW: Assuming maximum 2 args per stmts. */
494 {
497 }
503 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
506 }
509 /* Function vect_cost_strided_group_size
511 For strided load or store, return the group_size only if it is the first
512 load or store of a group, else return 1. This ensures that group size is
513 only returned once per group. */
515 static int
517 {
524 }
527 /* Function vect_model_store_cost
529 Models cost for stores. In the case of strided accesses, one access
530 has the overhead of the strided access attributed to it. */
532 void
535 {
542 /* Strided access? */
545 /* Not a strided access. */
546 else
549 /* Is this an access in a group of stores, which provide strided access?
550 If so, add in the cost of the permutes. */
552 {
553 /* Uses a high and low interleave operation for each needed permute. */
559 group_size);
561 }
563 /* Costs of the stores. */
570 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
573 }
576 /* Function vect_model_load_cost
578 Models cost for loads. In the case of strided accesses, the last access
579 has the overhead of the strided access attributed to it. Since unaligned
580 accesses are supported for loads, we also account for the costs of the
581 access scheme chosen. */
583 void
586 {
589 tree first_stmt;
593 /* Strided accesses? */
596 {
599 }
600 /* Not a strided access. */
601 else
602 {
605 }
609 /* Is this an access in a group of loads providing strided access?
610 If so, add in the cost of the permutes. */
612 {
613 /* Uses an even and odd extract operations for each needed permute. */
619 group_size);
621 }
623 /* The loads themselves. */
625 {
627 {
634 }
636 {
637 /* Here, we assign an additional cost for the unaligned load. */
645 }
647 {
650 /* FIXME: If the misalignment remains fixed across the iterations of
651 the containing loop, the following cost should be added to the
652 outside costs. */
657 }
659 {
664 /* Unaligned software pipeline has a load of an address, an initial
665 load, and possibly a mask operation to "prime" the loop. However,
666 if this is an access in a group of loads, which provide strided
667 access, then the above cost should only be considered for one
668 access in the group. Inside the loop, there is a load op
669 and a realignment op. */
672 {
676 }
681 }
685 }
691 /* Set the costs either in STMT_INFO or SLP_NODE (if exists). */
694 }
697 /* Function vect_get_new_vect_var.
699 Returns a name for a new variable. The current naming scheme appends the
700 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
701 the name of vectorizer generated variables, and appends that to NAME if
702 provided. */
704 static tree
706 {
708 tree new_vect_var;
711 {
723 }
726 {
730 }
731 else
734 /* Mark vector typed variable as a gimple register variable. */
739 }
742 /* Function vect_create_addr_base_for_vector_ref.
744 Create an expression that computes the address of the first memory location
745 that will be accessed for a data reference.
747 Input:
748 STMT: The statement containing the data reference.
749 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
750 OFFSET: Optional. If supplied, it is be added to the initial address.
751 LOOP: Specify relative to which loop-nest should the address be computed.
752 For example, when the dataref is in an inner-loop nested in an
753 outer-loop that is now being vectorized, LOOP can be either the
754 outer-loop, or the inner-loop. The first memory location accessed
755 by the following dataref ('in' points to short):
757 for (i=0; i<N; i++)
758 for (j=0; j<M; j++)
759 s += in[i+j]
761 is as follows:
762 if LOOP=i_loop: &in (relative to i_loop)
763 if LOOP=j_loop: &in+i*2B (relative to j_loop)
765 Output:
766 1. Return an SSA_NAME whose value is the address of the memory location of
767 the first vector of the data reference.
768 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
769 these statement(s) which define the returned SSA_NAME.
771 FORNOW: We are only handling array accesses with step 1. */
773 static tree
776 tree offset,
778 {
783 tree base_name;
784 tree data_ref_base_var;
785 tree new_base_stmt;
786 tree vec_stmt;
796 {
805 }
807 /* Create data_ref_base */
815 /* Create base_offset */
824 {
833 }
835 /* base + base_offset */
841 /* addr_expr = addr_base */
853 {
856 }
858 }
861 /* Function vect_create_data_ref_ptr.
863 Create a new pointer to vector type (vp), that points to the first location
864 accessed in the loop by STMT, along with the def-use update chain to
865 appropriately advance the pointer through the loop iterations. Also set
866 aliasing information for the pointer. This vector pointer is used by the
867 callers to this function to create a memory reference expression for vector
868 load/store access.
870 Input:
871 1. STMT: a stmt that references memory. Expected to be of the form
872 GIMPLE_MODIFY_STMT <name, data-ref> or
873 GIMPLE_MODIFY_STMT <data-ref, name>.
874 2. AT_LOOP: the loop where the vector memref is to be created.
875 3. OFFSET (optional): an offset to be added to the initial address accessed
876 by the data-ref in STMT.
877 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
878 pointing to the initial address.
879 5. TYPE: if not NULL indicates the required type of the data-ref
881 Output:
882 1. Declare a new ptr to vector_type, and have it point to the base of the
883 data reference (initial addressed accessed by the data reference).
884 For example, for vector of type V8HI, the following code is generated:
886 v8hi *vp;
887 vp = (v8hi *)initial_address;
889 if OFFSET is not supplied:
890 initial_address = &a[init];
891 if OFFSET is supplied:
892 initial_address = &a[init + OFFSET];
894 Return the initial_address in INITIAL_ADDRESS.
896 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
897 update the pointer in each iteration of the loop.
899 Return the increment stmt that updates the pointer in PTR_INCR.
901 3. Set INV_P to true if the access pattern of the data reference in the
902 vectorized loop is invariant. Set it to false otherwise.
904 4. Return the pointer. */
906 static tree
910 {
911 tree base_name;
918 tree vect_ptr_type;
919 tree vect_ptr;
920 tree tag;
921 tree new_temp;
922 tree vec_stmt;
924 edge pe;
925 basic_block new_bb;
926 tree vect_ptr_init;
928 tree vptr;
929 block_stmt_iterator incr_bsi;
932 tree incr;
933 tree step;
935 /* Check the step (evolution) of the load in LOOP, and record
936 whether it's invariant. */
939 else
944 else
947 /* Create an expression for the first address accessed by this load
948 in LOOP. */
952 {
965 }
967 /** (1) Create the new vector-pointer variable: **/
970 else
976 /** (2) Add aliasing information to the new vector-pointer:
977 (The points-to info (DR_PTR_INFO) may be defined later.) **/
982 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
983 tag must be created with tag added to its may alias list. */
986 else
991 /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
992 vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
993 def-use update cycles for the pointer: One relative to the outer-loop
994 (LOOP), which is what steps (3) and (4) below do. The other is relative
995 to the inner-loop (which is the inner-most loop containing the dataref),
996 and this is done be step (5) below.
998 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
999 inner-most loop, and so steps (3),(4) work the same, and step (5) is
1000 redundant. Steps (3),(4) create the following:
1002 vp0 = &base_addr;
1003 LOOP: vp1 = phi(vp0,vp2)
1004 ...
1005 ...
1006 vp2 = vp1 + step
1007 goto LOOP
1009 If there is an inner-loop nested in loop, then step (5) will also be
1010 applied, and an additional update in the inner-loop will be created:
1012 vp0 = &base_addr;
1013 LOOP: vp1 = phi(vp0,vp2)
1014 ...
1015 inner: vp3 = phi(vp1,vp4)
1016 vp4 = vp3 + inner_step
1017 if () goto inner
1018 ...
1019 vp2 = vp1 + step
1020 if () goto LOOP */
1022 /** (3) Calculate the initial address the vector-pointer, and set
1023 the vector-pointer to point to it before the loop: **/
1025 /* Create: (&(base[init_val+offset]) in the loop preheader. */
1034 /* Create: p = (vectype *) initial_base */
1043 /** (4) Handle the updating of the vector-pointer inside the loop.
1044 This is needed when ONLY_INIT is false, and also when AT_LOOP
1045 is the inner-loop nested in LOOP (during outer-loop vectorization).
1046 **/
1049 {
1050 /* Copy the points-to information if it exists. */
1054 }
1055 else
1056 {
1057 /* The step of the vector pointer is the Vector Size. */
1059 /* One exception to the above is when the scalar step of the load in
1060 LOOP is zero. In this case the step here is also zero. */
1074 /* Copy the points-to information if it exists. */
1076 {
1079 }
1086 }
1092 /** (5) Handle the updating of the vector-pointer inside the inner-loop
1093 nested in LOOP, if exists: **/
1097 {
1106 /* Copy the points-to information if it exists. */
1108 {
1111 }
1118 }
1119 else
1121 }
1124 /* Function bump_vector_ptr
1126 Increment a pointer (to a vector type) by vector-size. If requested,
1127 i.e. if PTR-INCR is given, then also connect the new increment stmt
1128 to the existing def-use update-chain of the pointer, by modifying
1129 the PTR_INCR as illustrated below:
1131 The pointer def-use update-chain before this function:
1132 DATAREF_PTR = phi (p_0, p_2)
1133 ....
1134 PTR_INCR: p_2 = DATAREF_PTR + step
1136 The pointer def-use update-chain after this function:
1137 DATAREF_PTR = phi (p_0, p_2)
1138 ....
1139 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1140 ....
1141 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
1143 Input:
1144 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
1145 in the loop.
1146 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
1147 the loop. The increment amount across iterations is expected
1148 to be vector_size.
1149 BSI - location where the new update stmt is to be placed.
1150 STMT - the original scalar memory-access stmt that is being vectorized.
1151 BUMP - optional. The offset by which to bump the pointer. If not given,
1152 the offset is assumed to be vector_size.
1154 Output: Return NEW_DATAREF_PTR as illustrated above.
1156 */
1158 static tree
1161 {
1168 tree incr_stmt;
1169 ssa_op_iter iter;
1170 use_operand_p use_p;
1171 tree new_dataref_ptr;
1183 /* Copy the points-to information if it exists. */
1191 /* Update the vector-pointer's cross-iteration increment. */
1193 {
1198 else
1200 }
1203 }
1206 /* Function vect_create_destination_var.
1208 Create a new temporary of type VECTYPE. */
1210 static tree
1212 {
1213 tree vec_dest;
1215 tree type;
1230 }
1233 /* Function vect_init_vector.
1235 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1236 the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1237 is not NULL. Otherwise, place the initialization at the loop preheader.
1238 Return the DEF of INIT_STMT.
1239 It will be used in the vectorization of STMT. */
1241 static tree
1244 {
1246 tree new_var;
1247 tree init_stmt;
1248 tree vec_oprnd;
1249 edge pe;
1250 tree new_temp;
1251 basic_block new_bb;
1261 else
1262 {
1271 }
1274 {
1277 }
1281 }
1284 /* For constant and loop invariant defs of SLP_NODE this function returns
1285 (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1286 OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1287 stmts. */
1289 static void
1292 {
1298 tree vec_cst;
1301 tree vector_type;
1313 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1314 created vectors. It is greater than 1 if unrolling is performed.
1316 For example, we have two scalar operands, s1 and s2 (e.g., group of
1317 strided accesses of size two), while NUINTS is four (i.e., four scalars
1318 of this type can be packed in a vector). The output vector will contain
1319 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1320 will be 2).
1322 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1323 containing the operands.
1325 For example, NUINTS is four as before, and the group size is 8
1326 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1327 {s5, s6, s7, s8}. */
1333 {
1335 {
1339 else
1342 /* Create 'vect_ = {op0,op1,...,opn}'. */
1345 number_of_places_left_in_vector--;
1348 {
1355 NULL));
1357 }
1358 }
1359 }
1361 /* Since the vectors are created in the reverse order, we should invert
1362 them. */
1365 {
1368 }
1372 /* In case that VF is greater than the unrolling factor needed for the SLP
1373 group of stmts, NUMBER_OF_VECTORS to be created is greater than
1374 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1375 to replicate the vectors. */
1377 {
1380 }
1381 }
1384 /* Get vectorized defintions from SLP_NODE that contains corresponding
1385 vectorized def-stmts. */
1387 static void
1389 {
1390 tree vec_oprnd;
1391 tree vec_def_stmt;
1398 i++)
1399 {
1403 }
1404 }
1407 /* Get vectorized definitions for SLP_NODE.
1408 If the scalar definitions are loop invariants or constants, collect them and
1409 call vect_get_constant_vectors() to create vector stmts.
1410 Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1411 must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1412 vect_get_slp_vect_defs() to retrieve them.
1413 If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1414 the right node. This is used when the second operand must remain scalar. */
1416 static void
1419 {
1422 /* Allocate memory for vectorized defs. */
1426 /* SLP_NODE corresponds either to a group of stores or to a group of
1427 unary/binary operations. We don't call this function for loads. */
1429 /* The defs are already vectorized. */
1431 else
1432 /* Build vectors from scalar defs. */
1437 /* Since we don't call this function with loads, this is a group of
1438 stores. */
1449 /* The defs are already vectorized. */
1451 else
1452 /* Build vectors from scalar defs. */
1454 }
1457 /* Function get_initial_def_for_induction
1459 Input:
1460 STMT - a stmt that performs an induction operation in the loop.
1461 IV_PHI - the initial value of the induction variable
1463 Output:
1464 Return a vector variable, initialized with the first VF values of
1465 the induction variable. E.g., for an iv with IV_PHI='X' and
1466 evolution S, for a vector of 4 units, we want to return:
1467 [X, X + S, X + 2*S, X + 3*S]. */
1469 static tree
1471 {
1480 basic_block new_bb;
1482 tree access_fn;
1483 tree new_var;
1484 tree new_name;
1485 tree init_stmt;
1492 tree expr;
1495 tree stmts;
1496 imm_use_iterator imm_iter;
1497 use_operand_p use_p;
1498 tree exit_phi;
1499 edge latch_e;
1500 tree loop_arg;
1501 block_stmt_iterator si;
1507 /* Find the first insertion point in the BB. */
1512 else
1515 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
1517 {
1520 }
1521 else
1535 /* Create the vector that holds the initial_value of the induction. */
1537 {
1538 /* iv_loop is nested in the loop to be vectorized. init_expr had already
1539 been created during vectorization of previous stmts; We obtain it from
1540 the STMT_VINFO_VEC_STMT of the defining stmt. */
1543 }
1544 else
1545 {
1546 /* iv_loop is the loop to be vectorized. Create:
1547 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
1553 {
1556 }
1561 {
1562 tree tmp;
1564 /* Create: new_name_i = new_name + step_expr */
1574 {
1577 }
1579 }
1580 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
1583 }
1586 /* Create the vector that holds the step of the induction. */
1588 /* iv_loop is nested in the loop to be vectorized. Generate:
1589 vec_step = [S, S, S, S] */
1591 else
1592 {
1593 /* iv_loop is the loop to be vectorized. Generate:
1594 vec_step = [VF*S, VF*S, VF*S, VF*S] */
1597 }
1606 /* Create the following def-use cycle:
1607 loop prolog:
1608 vec_init = ...
1609 vec_step = ...
1610 loop:
1611 vec_iv = PHI <vec_init, vec_loop>
1612 ...
1613 STMT
1614 ...
1615 vec_loop = vec_iv + vec_step; */
1617 /* Create the induction-phi that defines the induction-operand. */
1625 /* Create the iv update inside the loop */
1635 /* Set the arguments of the phi node: */
1640 /* In case that vectorization factor (VF) is bigger than the number
1641 of elements that we can fit in a vectype (nunits), we have to generate
1642 more than one vector stmt - i.e - we need to "unroll" the
1643 vector stmt by a factor VF/nunits. For more details see documentation
1644 in vectorizable_operation. */
1647 {
1648 stmt_vec_info prev_stmt_vinfo;
1649 /* FORNOW. This restriction should be relaxed. */
1652 /* Create the vector that holds the step of the induction. */
1664 {
1665 tree tmp;
1667 /* vec_i = vec_prev + vec_step */
1677 }
1678 }
1681 {
1682 /* Find the loop-closed exit-phi of the induction, and record
1683 the final vector of induction results: */
1686 {
1688 {
1691 }
1692 }
1694 {
1696 /* FORNOW. Currently not supporting the case that an inner-loop induction
1697 is not used in the outer-loop (i.e. only outside the outer-loop). */
1703 {
1706 }
1707 }
1708 }
1712 {
1717 }
1721 }
1724 /* Function vect_get_vec_def_for_operand.
1726 OP is an operand in STMT. This function returns a (vector) def that will be
1727 used in the vectorized stmt for STMT.
1729 In the case that OP is an SSA_NAME which is defined in the loop, then
1730 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1732 In case OP is an invariant or constant, a new stmt that creates a vector def
1733 needs to be introduced. */
1735 static tree
1737 {
1738 tree vec_oprnd;
1739 tree vec_stmt;
1740 tree def_stmt;
1746 tree vec_inv;
1747 tree vec_cst;
1749 tree def;
1753 tree vector_type;
1756 {
1759 }
1764 {
1766 {
1769 }
1771 {
1774 }
1775 }
1778 {
1779 /* Case 1: operand is a constant. */
1781 {
1785 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1790 {
1792 }
1797 }
1799 /* Case 2: operand is defined outside the loop - loop invariant. */
1801 {
1805 /* Create 'vec_inv = {inv,inv,..,inv}' */
1810 {
1812 }
1814 /* FIXME: use build_constructor directly. */
1818 }
1820 /* Case 3: operand is defined inside the loop. */
1822 {
1826 /* Get the def from the vectorized stmt. */
1832 else
1835 }
1837 /* Case 4: operand is defined by a loop header phi - reduction */
1839 {
1845 /* Get the def before the loop */
1848 }
1850 /* Case 5: operand is defined by loop-header phi - induction. */
1852 {
1855 /* Get the def from the vectorized stmt. */
1861 }
1865 }
1866 }
1869 /* Function vect_get_vec_def_for_stmt_copy
1871 Return a vector-def for an operand. This function is used when the
1872 vectorized stmt to be created (by the caller to this function) is a "copy"
1873 created in case the vectorized result cannot fit in one vector, and several
1874 copies of the vector-stmt are required. In this case the vector-def is
1875 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1876 of the stmt that defines VEC_OPRND.
1877 DT is the type of the vector def VEC_OPRND.
1879 Context:
1880 In case the vectorization factor (VF) is bigger than the number
1881 of elements that can fit in a vectype (nunits), we have to generate
1882 more than one vector stmt to vectorize the scalar stmt. This situation
1883 arises when there are multiple data-types operated upon in the loop; the
1884 smallest data-type determines the VF, and as a result, when vectorizing
1885 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1886 vector stmt (each computing a vector of 'nunits' results, and together
1887 computing 'VF' results in each iteration). This function is called when
1888 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1889 which VF=16 and nunits=4, so the number of copies required is 4):
1891 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
1893 S1: x = load VS1.0: vx.0 = memref0 VS1.1
1894 VS1.1: vx.1 = memref1 VS1.2
1895 VS1.2: vx.2 = memref2 VS1.3
1896 VS1.3: vx.3 = memref3
1898 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
1899 VSnew.1: vz1 = vx.1 + ... VSnew.2
1900 VSnew.2: vz2 = vx.2 + ... VSnew.3
1901 VSnew.3: vz3 = vx.3 + ...
1903 The vectorization of S1 is explained in vectorizable_load.
1904 The vectorization of S2:
1905 To create the first vector-stmt out of the 4 copies - VSnew.0 -
1906 the function 'vect_get_vec_def_for_operand' is called to
1907 get the relevant vector-def for each operand of S2. For operand x it
1908 returns the vector-def 'vx.0'.
1910 To create the remaining copies of the vector-stmt (VSnew.j), this
1911 function is called to get the relevant vector-def for each operand. It is
1912 obtained from the respective VS1.j stmt, which is recorded in the
1913 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
1915 For example, to obtain the vector-def 'vx.1' in order to create the
1916 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
1917 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
1918 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
1919 and return its def ('vx.1').
1920 Overall, to create the above sequence this function will be called 3 times:
1921 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
1922 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
1923 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
1925 static tree
1927 {
1928 tree vec_stmt_for_operand;
1929 stmt_vec_info def_stmt_info;
1931 /* Do nothing; can reuse same def. */
1942 }
1945 /* Get vectorized definitions for the operands to create a copy of an original
1946 stmt. See vect_get_vec_def_for_stmt_copy() for details. */
1948 static void
1952 {
1959 {
1963 }
1964 }
1967 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not NULL. */
1969 static void
1972 {
1975 else
1976 {
1977 tree vec_oprnd;
1984 {
1988 }
1989 }
1990 }
1993 /* Function vect_finish_stmt_generation.
1995 Insert a new stmt. */
1997 static void
2000 {
2013 {
2016 }
2018 /* Make sure bsi points to the stmt that is being vectorized. */
2021 #ifdef USE_MAPPED_LOCATION
2023 #else
2025 #endif
2026 }
2029 /* Function get_initial_def_for_reduction
2031 Input:
2032 STMT - a stmt that performs a reduction operation in the loop.
2033 INIT_VAL - the initial value of the reduction variable
2035 Output:
2036 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2037 of the reduction (used for adjusting the epilog - see below).
2038 Return a vector variable, initialized according to the operation that STMT
2039 performs. This vector will be used as the initial value of the
2040 vector of partial results.
2042 Option1 (adjust in epilog): Initialize the vector as follows:
2043 add: [0,0,...,0,0]
2044 mult: [1,1,...,1,1]
2045 min/max: [init_val,init_val,..,init_val,init_val]
2046 bit and/or: [init_val,init_val,..,init_val,init_val]
2047 and when necessary (e.g. add/mult case) let the caller know
2048 that it needs to adjust the result by init_val.
2050 Option2: Initialize the vector as follows:
2051 add: [0,0,...,0,init_val]
2052 mult: [1,1,...,1,init_val]
2053 min/max: [init_val,init_val,...,init_val]
2054 bit and/or: [init_val,init_val,...,init_val]
2055 and no adjustments are needed.
2057 For example, for the following code:
2059 s = init_val;
2060 for (i=0;i<n;i++)
2061 s = s + a[i];
2063 STMT is 's = s + a[i]', and the reduction variable is 's'.
2064 For a vector of 4 units, we want to return either [0,0,0,init_val],
2065 or [0,0,0,0] and let the caller know that it needs to adjust
2066 the result at the end by 'init_val'.
2068 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2069 initialization vector is simpler (same element in all entries).
2070 A cost model should help decide between these two schemes. */
2072 static tree
2074 {
2082 tree vecdef;
2083 tree def_for_init;
2084 tree init_def;
2087 tree vector_type;
2093 else
2099 {
2105 else
2107 /* Create a vector of zeros for init_def. */
2110 else
2126 }
2129 }
2132 /* Function vect_create_epilog_for_reduction
2134 Create code at the loop-epilog to finalize the result of a reduction
2135 computation.
2137 VECT_DEF is a vector of partial results.
2138 REDUC_CODE is the tree-code for the epilog reduction.
2139 STMT is the scalar reduction stmt that is being vectorized.
2140 REDUCTION_PHI is the phi-node that carries the reduction computation.
2142 This function:
2143 1. Creates the reduction def-use cycle: sets the arguments for
2144 REDUCTION_PHI:
2145 The loop-entry argument is the vectorized initial-value of the reduction.
2146 The loop-latch argument is VECT_DEF - the vector of partial sums.
2147 2. "Reduces" the vector of partial results VECT_DEF into a single result,
2148 by applying the operation specified by REDUC_CODE if available, or by
2149 other means (whole-vector shifts or a scalar loop).
2150 The function also creates a new phi node at the loop exit to preserve
2151 loop-closed form, as illustrated below.
2153 The flow at the entry to this function:
2155 loop:
2156 vec_def = phi <null, null> # REDUCTION_PHI
2157 VECT_DEF = vector_stmt # vectorized form of STMT
2158 s_loop = scalar_stmt # (scalar) STMT
2159 loop_exit:
2160 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2161 use <s_out0>
2162 use <s_out0>
2164 The above is transformed by this function into:
2166 loop:
2167 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2168 VECT_DEF = vector_stmt # vectorized form of STMT
2169 s_loop = scalar_stmt # (scalar) STMT
2170 loop_exit:
2171 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2172 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2173 v_out2 = reduce <v_out1>
2174 s_out3 = extract_field <v_out2, 0>
2175 s_out4 = adjust_result <s_out3>
2176 use <s_out4>
2177 use <s_out4>
2178 */
2180 static void
2183 {
2185 tree vectype;
2189 basic_block exit_bb;
2190 tree scalar_dest;
2191 tree scalar_type;
2192 tree new_phi;
2193 block_stmt_iterator exit_bsi;
2194 tree vec_dest;
2196 tree new_name;
2201 tree adjustment_def;
2202 tree vec_initial_def;
2203 tree orig_name;
2204 imm_use_iterator imm_iter;
2205 use_operand_p use_p;
2208 tree orig_stmt;
2209 tree use_stmt;
2217 {
2220 }
2227 /*** 1. Create the reduction def-use cycle ***/
2229 /* 1.1 set the loop-entry arg of the reduction-phi: */
2230 /* For the case of reduction, vect_get_vec_def_for_operand returns
2231 the scalar def before the loop, that defines the initial value
2232 of the reduction variable. */
2237 /* 1.2 set the loop-latch arg for the reduction-phi: */
2241 {
2246 }
2249 /*** 2. Create epilog code
2250 The reduction epilog code operates across the elements of the vector
2251 of partial results computed by the vectorized loop.
2252 The reduction epilog code consists of:
2253 step 1: compute the scalar result in a vector (v_out2)
2254 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2255 step 3: adjust the scalar result (s_out3) if needed.
2257 Step 1 can be accomplished using one the following three schemes:
2258 (scheme 1) using reduc_code, if available.
2259 (scheme 2) using whole-vector shifts, if available.
2260 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2261 combined.
2263 The overall epilog code looks like this:
2265 s_out0 = phi <s_loop> # original EXIT_PHI
2266 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2267 v_out2 = reduce <v_out1> # step 1
2268 s_out3 = extract_field <v_out2, 0> # step 2
2269 s_out4 = adjust_result <s_out3> # step 3
2271 (step 3 is optional, and step2 1 and 2 may be combined).
2272 Lastly, the uses of s_out0 are replaced by s_out4.
2274 ***/
2276 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2277 v_out1 = phi <v_loop> */
2284 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
2285 (i.e. when reduc_code is not available) and in the final adjustment
2286 code (if needed). Also get the original scalar reduction variable as
2287 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
2288 represents a reduction pattern), the tree-code and scalar-def are
2289 taken from the original stmt that the pattern-stmt (STMT) replaces.
2290 Otherwise (it is a regular reduction) - the tree-code and scalar-def
2291 are taken from STMT. */
2295 {
2296 /* Regular reduction */
2298 }
2299 else
2300 {
2301 /* Reduction pattern */
2305 }
2314 /* In case this is a reduction in an inner-loop while vectorizing an outer
2315 loop - we don't need to extract a single scalar result at the end of the
2316 inner-loop. The final vector of partial results will be used in the
2317 vectorized outer-loop, or reduced to a scalar result at the end of the
2318 outer-loop. */
2322 /* 2.3 Create the reduction code, using one of the three schemes described
2323 above. */
2326 {
2327 tree tmp;
2329 /*** Case 1: Create:
2330 v_out2 = reduc_expr <v_out1> */
2343 }
2344 else
2345 {
2351 tree vec_temp;
2355 else
2358 /* Regardless of whether we have a whole vector shift, if we're
2359 emulating the operation via tree-vect-generic, we don't want
2360 to use it. Only the first round of the reduction is likely
2361 to still be profitable via emulation. */
2362 /* ??? It might be better to emit a reduction tree code here, so that
2363 tree-vect-generic can expand the first round via bit tricks. */
2366 else
2367 {
2371 }
2374 {
2375 /*** Case 2: Create:
2376 for (offset = VS/2; offset >= element_size; offset/=2)
2377 {
2378 Create: va' = vec_shift <va, offset>
2379 Create: va = vop <va, va'>
2380 } */
2391 {
2404 }
2407 }
2408 else
2409 {
2410 tree rhs;
2412 /*** Case 3: Create:
2413 s = extract_field <v_out2, 0>
2414 for (offset = element_size;
2415 offset < vector_size;
2416 offset += element_size;)
2417 {
2418 Create: s' = extract_field <v_out2, offset>
2419 Create: s = op <s, s'>
2420 } */
2428 bitsize_zero_node);
2438 {
2439 tree tmp;
2442 bitpos);
2455 }
2458 }
2459 }
2461 /* 2.4 Extract the final scalar result. Create:
2462 s_out3 = extract_field <v_out2, bitpos> */
2465 {
2466 tree rhs;
2476 else
2485 }
2487 vect_finalize_reduction:
2489 /* 2.5 Adjust the final result by the initial value of the reduction
2490 variable. (When such adjustment is not needed, then
2491 'adjustment_def' is zero). For example, if code is PLUS we create:
2492 new_temp = loop_exit_def + adjustment_def */
2495 {
2497 {
2501 }
2502 else
2503 {
2507 }
2512 }
2515 /* 2.6 Handle the loop-exit phi */
2517 /* Replace uses of s_out0 with uses of s_out3:
2518 Find the loop-closed-use at the loop exit of the original scalar result.
2519 (The reduction result is expected to have two immediate uses - one at the
2520 latch block, and one at the loop exit). */
2523 {
2525 {
2528 }
2529 }
2530 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
2534 {
2536 {
2539 /* FORNOW. Currently not supporting the case that an inner-loop reduction
2540 is not used in the outer-loop (but only outside the outer-loop). */
2549 }
2551 /* Replace the uses: */
2556 }
2558 }
2561 /* Function vectorizable_reduction.
2563 Check if STMT performs a reduction operation that can be vectorized.
2564 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2565 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2566 Return FALSE if not a vectorizable STMT, TRUE otherwise.
2568 This function also handles reduction idioms (patterns) that have been
2569 recognized in advance during vect_pattern_recog. In this case, STMT may be
2570 of this form:
2571 X = pattern_expr (arg0, arg1, ..., X)
2572 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2573 sequence that had been detected and replaced by the pattern-stmt (STMT).
2575 In some cases of reduction patterns, the type of the reduction variable X is
2576 different than the type of the other arguments of STMT.
2577 In such cases, the vectype that is used when transforming STMT into a vector
2578 stmt is different than the vectype that is used to determine the
2579 vectorization factor, because it consists of a different number of elements
2580 than the actual number of elements that are being operated upon in parallel.
2582 For example, consider an accumulation of shorts into an int accumulator.
2583 On some targets it's possible to vectorize this pattern operating on 8
2584 shorts at a time (hence, the vectype for purposes of determining the
2585 vectorization factor should be V8HI); on the other hand, the vectype that
2586 is used to create the vector form is actually V4SI (the type of the result).
2588 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2589 indicates what is the actual level of parallelism (V8HI in the example), so
2590 that the right vectorization factor would be derived. This vectype
2591 corresponds to the type of arguments to the reduction stmt, and should *NOT*
2592 be used to create the vectorized stmt. The right vectype for the vectorized
2593 stmt is obtained from the type of the result X:
2594 get_vectype_for_scalar_type (TREE_TYPE (X))
2596 This means that, contrary to "regular" reductions (or "regular" stmts in
2597 general), the following equation:
2598 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2599 does *NOT* necessarily hold for reduction patterns. */
2601 bool
2603 {
2604 tree vec_dest;
2605 tree scalar_dest;
2606 tree op;
2612 tree operation;
2620 tree new_phi;
2621 tree scalar_type;
2623 tree orig_stmt;
2624 stmt_vec_info orig_stmt_info;
2629 stmt_vec_info prev_stmt_info;
2630 tree reduc_def;
2635 {
2637 /* FORNOW. This restriction should be relaxed. */
2639 {
2643 }
2644 }
2648 /* FORNOW: SLP not supported. */
2652 /* 1. Is vectorizable reduction? */
2654 /* Not supportable if the reduction variable is used in the loop. */
2658 /* Reductions that are not used even in an enclosing outer-loop,
2659 are expected to be "live" (used out of the loop). */
2664 /* Make sure it was already recognized as a reduction computation. */
2668 /* 2. Has this been recognized as a reduction pattern?
2670 Check if STMT represents a pattern that has been recognized
2671 in earlier analysis stages. For stmts that represent a pattern,
2672 the STMT_VINFO_RELATED_STMT field records the last stmt in
2673 the original sequence that constitutes the pattern. */
2677 {
2682 }
2684 /* 3. Check the operands of the operation. The first operands are defined
2685 inside the loop body. The last operand is the reduction variable,
2686 which is defined by the loop-header-phi. */
2698 /* All uses but the last are expected to be defined in the loop.
2699 The last use is the reduction variable. */
2701 {
2710 }
2719 else
2725 /* 4. Supportable by target? */
2727 /* 4.1. check support for the operation in the loop */
2730 {
2734 }
2737 {
2746 }
2748 /* Worthwhile without SIMD support? */
2752 {
2756 }
2758 /* 4.2. Check support for the epilog operation.
2760 If STMT represents a reduction pattern, then the type of the
2761 reduction variable may be different than the type of the rest
2762 of the arguments. For example, consider the case of accumulation
2763 of shorts into an int accumulator; The original code:
2764 S1: int_a = (int) short_a;
2765 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
2767 was replaced with:
2768 STMT: int_acc = widen_sum <short_a, int_acc>
2770 This means that:
2771 1. The tree-code that is used to create the vector operation in the
2772 epilog code (that reduces the partial results) is not the
2773 tree-code of STMT, but is rather the tree-code of the original
2774 stmt from the pattern that STMT is replacing. I.e, in the example
2775 above we want to use 'widen_sum' in the loop, but 'plus' in the
2776 epilog.
2777 2. The type (mode) we use to check available target support
2778 for the vector operation to be created in the *epilog*, is
2779 determined by the type of the reduction variable (in the example
2780 above we'd check this: plus_optab[vect_int_mode]).
2781 However the type (mode) we use to check available target support
2782 for the vector operation to be created *inside the loop*, is
2783 determined by the type of the other arguments to STMT (in the
2784 example we'd check this: widen_sum_optab[vect_short_mode]).
2786 This is contrary to "regular" reductions, in which the types of all
2787 the arguments are the same as the type of the reduction variable.
2788 For "regular" reductions we can therefore use the same vector type
2789 (and also the same tree-code) when generating the epilog code and
2790 when generating the code inside the loop. */
2793 {
2794 /* This is a reduction pattern: get the vectype from the type of the
2795 reduction variable, and get the tree-code from orig_stmt. */
2799 }
2800 else
2801 {
2802 /* Regular reduction: use the same vectype and tree-code as used for
2803 the vector code inside the loop can be used for the epilog code. */
2805 }
2811 {
2815 }
2817 {
2821 }
2824 {
2828 }
2830 /** Transform. **/
2835 /* Create the destination vector */
2838 /* Create the reduction-phi that defines the reduction-operand. */
2841 /* In case the vectorization factor (VF) is bigger than the number
2842 of elements that we can fit in a vectype (nunits), we have to generate
2843 more than one vector stmt - i.e - we need to "unroll" the
2844 vector stmt by a factor VF/nunits. For more details see documentation
2845 in vectorizable_operation. */
2849 {
2850 /* Handle uses. */
2852 {
2856 {
2859 }
2861 /* Get the vector def for the reduction variable from the phi node */
2863 }
2864 else
2865 {
2871 /* Get the vector def for the reduction variable from the vectorized
2872 reduction operation generated in the previous iteration (j-1) */
2874 }
2876 /* Arguments are ready. create the new vector stmt. */
2879 else
2881 reduc_def);
2889 else
2892 }
2894 /* Finalize the reduction-phi (set it's arguments) and create the
2895 epilog reduction code. */
2898 }
2900 /* Checks if CALL can be vectorized in type VECTYPE. Returns
2901 a function declaration if the target has a vectorized version
2902 of the function, or NULL_TREE if the function cannot be vectorized. */
2904 tree
2906 {
2910 /* We only handle functions that do not read or clobber memory -- i.e.
2911 const or novops ones. */
2922 vectype_in);
2923 }
2925 /* Function vectorizable_call.
2927 Check if STMT performs a function call that can be vectorized.
2928 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2929 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2930 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2932 bool
2934 {
2935 tree vec_dest;
2936 tree scalar_dest;
2937 tree operation;
2948 tree new_stmt;
2950 call_expr_arg_iterator iter;
2951 tree vargs;
2960 /* FORNOW: SLP not supported. */
2964 /* FORNOW: not yet supported. */
2966 {
2970 }
2972 /* Is STMT a vectorizable call? */
2983 /* Process function arguments. */
2987 {
2988 /* Bail out if the function has more than two arguments, we
2989 do not have interesting builtin functions to vectorize with
2990 more than two arguments. */
2994 /* We can only handle calls with arguments of the same type. */
2997 {
3001 }
3005 {
3009 }
3012 }
3014 /* No arguments is also not good. */
3025 /* FORNOW */
3032 else
3035 /* For now, we only vectorize functions if a target specific builtin
3036 is available. TODO -- in some cases, it might be profitable to
3037 insert the calls for pieces of the vector, in order to be able
3038 to vectorize other operations in the loop. */
3041 {
3046 }
3052 else
3055 /* Sanity check: make sure that at least one copy of the vectorized stmt
3056 needs to be generated. */
3059 /* FORNOW. This restriction should be relaxed. */
3061 {
3065 }
3068 {
3074 }
3076 /** Transform. **/
3081 /* FORNOW. This restriction should be relaxed. */
3083 {
3087 }
3089 /* Handle def. */
3095 {
3098 {
3099 /* Build argument list for the vectorized call. */
3100 /* FIXME: Rewrite this so that it doesn't
3101 construct a temporary list. */
3105 {
3107 vec_oprnd0
3109 else
3110 vec_oprnd0
3116 }
3128 else
3132 }
3138 {
3139 /* Build argument list for the vectorized call. */
3140 /* FIXME: Rewrite this so that it doesn't
3141 construct a temporary list. */
3145 {
3147 {
3148 vec_oprnd0
3150 vec_oprnd1
3152 }
3153 else
3154 {
3155 vec_oprnd0
3157 vec_oprnd1
3159 }
3165 }
3177 else
3181 }
3188 /* No current target implements this case. */
3190 }
3192 /* The call in STMT might prevent it from being removed in dce.
3193 We however cannot remove it here, due to the way the ssa name
3194 it defines is mapped to the new definition. So just replace
3195 rhs of the statement with something harmless. */
3201 }
3204 /* Function vect_gen_widened_results_half
3206 Create a vector stmt whose code, type, number of arguments, and result
3207 variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are
3208 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
3209 In the case that CODE is a CALL_EXPR, this means that a call to DECL
3210 needs to be created (DECL is a function-decl of a target-builtin).
3211 STMT is the original scalar stmt that we are vectorizing. */
3213 static tree
3217 tree stmt)
3218 {
3219 tree expr;
3220 tree new_stmt;
3221 tree new_temp;
3222 tree sym;
3223 ssa_op_iter iter;
3225 /* Generate half of the widened result: */
3227 {
3228 /* Target specific support */
3231 else
3233 }
3234 else
3235 {
3236 /* Generic support */
3240 else
3242 }
3249 {
3251 {
3255 }
3256 }
3259 }
3262 /* Check if STMT performs a conversion operation, that can be vectorized.
3263 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3264 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3265 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3267 bool
3270 {
3271 tree vec_dest;
3272 tree scalar_dest;
3273 tree operation;
3274 tree op0;
3281 tree new_temp;
3285 stmt_vec_info prev_stmt_info;
3290 tree expr;
3292 tree builtin_decl;
3296 tree vop0;
3298 /* Is STMT a vectorizable conversion? */
3307 {
3308 /* FORNOW: not yet supported. */
3312 }
3325 /* Check types of lhs and rhs. */
3340 /* FORNOW */
3347 else
3353 /* Bail out if the types are both integral or non-integral. */
3360 else
3363 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3364 this, so we can safely override NCOPIES with 1 here. */
3368 /* Sanity check: make sure that at least one copy of the vectorized stmt
3369 needs to be generated. */
3372 /* FORNOW. This restriction should be relaxed. */
3374 {
3378 }
3380 /* Check the operands of the operation. */
3382 {
3386 }
3388 /* Supportable by target? */
3398 {
3402 }
3405 {
3407 /* FORNOW: SLP not supported. */
3410 }
3413 {
3416 }
3418 /** Transform. **/
3422 /* Handle def. */
3430 {
3433 {
3434 tree sym;
3435 ssa_op_iter iter;
3439 else
3442 builtin_decl =
3445 {
3448 /* Arguments are ready. create the new vector stmt. */
3454 SSA_OP_ALL_VIRTUALS)
3455 {
3459 }
3462 }
3466 else
3469 }
3473 /* In case the vectorization factor (VF) is bigger than the number
3474 of elements that we can fit in a vectype (nunits), we have to
3475 generate more than one vector stmt - i.e - we need to "unroll"
3476 the vector stmt by a factor VF/nunits. */
3478 {
3481 else
3486 /* Generate first half of the widened result: */
3487 new_stmt
3493 else
3497 /* Generate second half of the widened result: */
3498 new_stmt
3504 }
3508 /* In case the vectorization factor (VF) is bigger than the number
3509 of elements that we can fit in a vectype (nunits), we have to
3510 generate more than one vector stmt - i.e - we need to "unroll"
3511 the vector stmt by a factor VF/nunits. */
3513 {
3514 /* Handle uses. */
3516 {
3519 }
3520 else
3521 {
3524 }
3526 /* Arguments are ready. Create the new vector stmt. */
3535 else
3539 }
3542 }
3545 }
3548 /* Function vectorizable_assignment.
3550 Check if STMT performs an assignment (copy) that can be vectorized.
3551 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3552 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3553 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3555 bool
3557 slp_tree slp_node)
3558 {
3559 tree vec_dest;
3560 tree scalar_dest;
3561 tree op;
3565 tree new_temp;
3572 tree vop;
3584 /* FORNOW: not yet supported. */
3586 {
3590 }
3592 /* Is vectorizable assignment? */
3602 {
3606 }
3609 {
3615 }
3617 /** Transform. **/
3621 /* Handle def. */
3624 /* Handle use. */
3627 /* Arguments are ready. create the new vector stmt. */
3629 {
3638 }
3642 }
3645 /* Function vect_min_worthwhile_factor.
3647 For a loop where we could vectorize the operation indicated by CODE,
3648 return the minimum vectorization factor that makes it worthwhile
3649 to use generic vectors. */
3650 static int
3652 {
3654 {
3668 }
3669 }
3672 /* Function vectorizable_induction
3674 Check if PHI performs an induction computation that can be vectorized.
3675 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3676 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3677 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3679 bool
3682 {
3688 tree vec_def;
3695 /* FORNOW: SLP not supported. */
3702 {
3703 /* FORNOW: not yet supported. */
3707 }
3713 {
3719 }
3721 /** Transform. **/
3729 }
3732 /* Function vectorizable_operation.
3734 Check if STMT performs a binary or unary operation that can be vectorized.
3735 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3736 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3737 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3739 bool
3741 slp_tree slp_node)
3742 {
3743 tree vec_dest;
3744 tree scalar_dest;
3745 tree operation;
3754 tree new_temp;
3756 optab optab;
3762 stmt_vec_info prev_stmt_info;
3765 tree vectype_out;
3771 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3772 this, so we can safely override NCOPIES with 1 here. */
3776 /* FORNOW. This restriction should be relaxed. */
3778 {
3782 }
3790 /* FORNOW: not yet supported. */
3792 {
3796 }
3798 /* Is STMT a vectorizable binary/unary operation? */
3814 /* For pointer addition, we should use the normal plus for
3815 the vector addition. */
3821 /* Support only unary or binary operations. */
3824 {
3828 }
3832 {
3836 }
3839 {
3842 {
3846 }
3847 }
3849 /* Supportable by target? */
3851 {
3855 }
3859 {
3868 }
3870 /* Worthwhile without SIMD support? */
3874 {
3878 }
3881 {
3882 /* FORNOW: not yet supported. */
3886 /* Invariant argument is needed for a vector shift
3887 by a scalar shift operand. */
3892 {
3896 }
3897 }
3900 {
3906 }
3908 /** Transform. **/
3913 /* Handle def. */
3921 /* In case the vectorization factor (VF) is bigger than the number
3922 of elements that we can fit in a vectype (nunits), we have to generate
3923 more than one vector stmt - i.e - we need to "unroll" the
3924 vector stmt by a factor VF/nunits. In doing so, we record a pointer
3925 from one copy of the vector stmt to the next, in the field
3926 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3927 stages to find the correct vector defs to be used when vectorizing
3928 stmts that use the defs of the current stmt. The example below illustrates
3929 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3930 4 vectorized stmts):
3932 before vectorization:
3933 RELATED_STMT VEC_STMT
3934 S1: x = memref - -
3935 S2: z = x + 1 - -
3937 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
3938 there):
3939 RELATED_STMT VEC_STMT
3940 VS1_0: vx0 = memref0 VS1_1 -
3941 VS1_1: vx1 = memref1 VS1_2 -
3942 VS1_2: vx2 = memref2 VS1_3 -
3943 VS1_3: vx3 = memref3 - -
3944 S1: x = load - VS1_0
3945 S2: z = x + 1 - -
3947 step2: vectorize stmt S2 (done here):
3948 To vectorize stmt S2 we first need to find the relevant vector
3949 def for the first operand 'x'. This is, as usual, obtained from
3950 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
3951 that defines 'x' (S1). This way we find the stmt VS1_0, and the
3952 relevant vector def 'vx0'. Having found 'vx0' we can generate
3953 the vector stmt VS2_0, and as usual, record it in the
3954 STMT_VINFO_VEC_STMT of stmt S2.
3955 When creating the second copy (VS2_1), we obtain the relevant vector
3956 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
3957 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
3958 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
3959 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
3960 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
3961 chain of stmts and pointers:
3962 RELATED_STMT VEC_STMT
3963 VS1_0: vx0 = memref0 VS1_1 -
3964 VS1_1: vx1 = memref1 VS1_2 -
3965 VS1_2: vx2 = memref2 VS1_3 -
3966 VS1_3: vx3 = memref3 - -
3967 S1: x = load - VS1_0
3968 VS2_0: vz0 = vx0 + v1 VS2_1 -
3969 VS2_1: vz1 = vx1 + v1 VS2_2 -
3970 VS2_2: vz2 = vx2 + v1 VS2_3 -
3971 VS2_3: vz3 = vx3 + v1 - -
3972 S2: z = x + 1 - VS2_0 */
3976 {
3977 /* Handle uses. */
3979 {
3982 {
3983 /* Vector shl and shr insn patterns can be defined with scalar
3984 operand 2 (shift operand). In this case, use constant or loop
3985 invariant op1 directly, without extending it to vector mode
3986 first. */
3989 {
3994 }
3995 }
3997 /* vec_oprnd is available if operand 1 should be of a scalar-type
3998 (a special case for certain kind of vector shifts); otherwise,
3999 operand 1 should be of a vector type (the usual case). */
4002 slp_node);
4003 else
4005 slp_node);
4006 }
4007 else
4010 /* Arguments are ready. Create the new vector stmt. */
4012 {
4014 {
4018 }
4019 else
4028 }
4032 else
4035 }
4042 }
4045 /* Function vectorizable_type_demotion
4047 Check if STMT performs a binary or unary operation that involves
4048 type demotion, and if it can be vectorized.
4049 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4050 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4051 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4053 bool
4056 {
4057 tree vec_dest;
4058 tree scalar_dest;
4059 tree operation;
4060 tree op0;
4066 tree new_temp;
4069 tree new_stmt;
4070 stmt_vec_info prev_stmt_info;
4073 tree vectype_out;
4076 tree expr;
4077 tree vectype_in;
4085 /* FORNOW: not yet supported. */
4087 {
4091 }
4093 /* Is STMT a vectorizable type-demotion operation? */
4121 /* FORNOW. This restriction should be relaxed. */
4123 {
4127 }
4136 /* Check the operands of the operation. */
4138 {
4142 }
4144 /* Supportable by target? */
4151 {
4157 }
4159 /** Transform. **/
4162 ncopies);
4164 /* Handle def. */
4167 /* In case the vectorization factor (VF) is bigger than the number
4168 of elements that we can fit in a vectype (nunits), we have to generate
4169 more than one vector stmt - i.e - we need to "unroll" the
4170 vector stmt by a factor VF/nunits. */
4173 {
4174 /* Handle uses. */
4176 {
4179 }
4180 else
4181 {
4184 }
4186 /* Arguments are ready. Create the new vector stmt. */
4195 else
4199 }
4203 }
4206 /* Function vectorizable_type_promotion
4208 Check if STMT performs a binary or unary operation that involves
4209 type promotion, and if it can be vectorized.
4210 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4211 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4212 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4214 bool
4217 {
4218 tree vec_dest;
4219 tree scalar_dest;
4220 tree operation;
4231 tree new_stmt;
4232 stmt_vec_info prev_stmt_info;
4235 tree vectype_out;
4238 tree vectype_in;
4246 /* FORNOW: not yet supported. */
4248 {
4252 }
4254 /* Is STMT a vectorizable type-promotion operation? */
4283 /* FORNOW. This restriction should be relaxed. */
4285 {
4289 }
4298 /* Check the operands of the operation. */
4300 {
4304 }
4308 {
4311 {
4315 }
4316 }
4318 /* Supportable by target? */
4326 {
4332 }
4334 /** Transform. **/
4338 ncopies);
4340 /* Handle def. */
4343 /* In case the vectorization factor (VF) is bigger than the number
4344 of elements that we can fit in a vectype (nunits), we have to generate
4345 more than one vector stmt - i.e - we need to "unroll" the
4346 vector stmt by a factor VF/nunits. */
4350 {
4351 /* Handle uses. */
4353 {
4357 }
4358 else
4359 {
4363 }
4365 /* Arguments are ready. Create the new vector stmt. We are creating
4366 two vector defs because the widened result does not fit in one vector.
4367 The vectorized stmt can be expressed as a call to a taregt builtin,
4368 or a using a tree-code. */
4369 /* Generate first half of the widened result: */
4374 else
4378 /* Generate second half of the widened result: */
4384 }
4388 }
4391 /* Function vect_strided_store_supported.
4393 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
4394 and FALSE otherwise. */
4396 static bool
4398 {
4404 /* Check that the operation is supported. */
4406 vectype);
4408 vectype);
4410 {
4414 }
4417 == CODE_FOR_nothing
4420 {
4424 }
4427 }
4430 /* Function vect_permute_store_chain.
4432 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4433 a power of 2, generate interleave_high/low stmts to reorder the data
4434 correctly for the stores. Return the final references for stores in
4435 RESULT_CHAIN.
4437 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4438 The input is 4 vectors each containing 8 elements. We assign a number to each
4439 element, the input sequence is:
4441 1st vec: 0 1 2 3 4 5 6 7
4442 2nd vec: 8 9 10 11 12 13 14 15
4443 3rd vec: 16 17 18 19 20 21 22 23
4444 4th vec: 24 25 26 27 28 29 30 31
4446 The output sequence should be:
4448 1st vec: 0 8 16 24 1 9 17 25
4449 2nd vec: 2 10 18 26 3 11 19 27
4450 3rd vec: 4 12 20 28 5 13 21 30
4451 4th vec: 6 14 22 30 7 15 23 31
4453 i.e., we interleave the contents of the four vectors in their order.
4455 We use interleave_high/low instructions to create such output. The input of
4456 each interleave_high/low operation is two vectors:
4457 1st vec 2nd vec
4458 0 1 2 3 4 5 6 7
4459 the even elements of the result vector are obtained left-to-right from the
4460 high/low elements of the first vector. The odd elements of the result are
4461 obtained left-to-right from the high/low elements of the second vector.
4462 The output of interleave_high will be: 0 4 1 5
4463 and of interleave_low: 2 6 3 7
4466 The permutation is done in log LENGTH stages. In each stage interleave_high
4467 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4468 where the first argument is taken from the first half of DR_CHAIN and the
4469 second argument from it's second half.
4470 In our example,
4472 I1: interleave_high (1st vec, 3rd vec)
4473 I2: interleave_low (1st vec, 3rd vec)
4474 I3: interleave_high (2nd vec, 4th vec)
4475 I4: interleave_low (2nd vec, 4th vec)
4477 The output for the first stage is:
4479 I1: 0 16 1 17 2 18 3 19
4480 I2: 4 20 5 21 6 22 7 23
4481 I3: 8 24 9 25 10 26 11 27
4482 I4: 12 28 13 29 14 30 15 31
4484 The output of the second stage, i.e. the final result is:
4486 I1: 0 8 16 24 1 9 17 25
4487 I2: 2 10 18 26 3 11 19 27
4488 I3: 4 12 20 28 5 13 21 30
4489 I4: 6 14 22 30 7 15 23 31. */
4491 static bool
4494 tree stmt,
4497 {
4509 /* Check that the operation is supported. */
4516 {
4518 {
4522 /* Create interleaving stmt:
4523 in the case of big endian:
4524 high = interleave_high (vect1, vect2)
4525 and in the case of little endian:
4526 high = interleave_low (vect1, vect2). */
4532 else
4540 /* Create interleaving stmt:
4541 in the case of big endian:
4542 low = interleave_low (vect1, vect2)
4543 and in the case of little endian:
4544 low = interleave_high (vect1, vect2). */
4550 else
4557 }
4559 }
4561 }
4564 /* Function vectorizable_store.
4566 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
4567 can be vectorized.
4568 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4569 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4570 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4572 bool
4574 slp_tree slp_node)
4575 {
4576 tree scalar_dest;
4577 tree data_ref;
4578 tree op;
4586 tree dummy;
4602 stmt_vec_info first_stmt_vinfo;
4605 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
4606 this, so we can safely override NCOPIES with 1 here. */
4612 /* FORNOW. This restriction should be relaxed. */
4614 {
4618 }
4627 {
4631 }
4633 /* Is vectorizable store? */
4646 {
4650 }
4653 /* FORNOW. In some cases can vectorize even if data-type not supported
4654 (e.g. - array initialization with 0). */
4662 {
4667 }
4670 {
4675 }
4677 /** Transform. **/
4680 {
4687 /* FORNOW */
4690 /* We vectorize all the stmts of the interleaving group when we
4691 reach the last stmt in the group. */
4695 {
4698 }
4703 /* VEC_NUM is the number of vect stmts to be created for this group. */
4706 else
4708 }
4709 else
4710 {
4715 }
4727 /* In case the vectorization factor (VF) is bigger than the number
4728 of elements that we can fit in a vectype (nunits), we have to generate
4729 more than one vector stmt - i.e - we need to "unroll" the
4730 vector stmt by a factor VF/nunits. For more details see documentation in
4731 vect_get_vec_def_for_copy_stmt. */
4733 /* In case of interleaving (non-unit strided access):
4735 S1: &base + 2 = x2
4736 S2: &base = x0
4737 S3: &base + 1 = x1
4738 S4: &base + 3 = x3
4740 We create vectorized stores starting from base address (the access of the
4741 first stmt in the chain (S2 in the above example), when the last store stmt
4742 of the chain (S4) is reached:
4744 VS1: &base = vx2
4745 VS2: &base + vec_size*1 = vx0
4746 VS3: &base + vec_size*2 = vx1
4747 VS4: &base + vec_size*3 = vx3
4749 Then permutation statements are generated:
4751 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
4752 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
4753 ...
4755 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
4756 (the order of the data-refs in the output of vect_permute_store_chain
4757 corresponds to the order of scalar stmts in the interleaving chain - see
4758 the documentation of vect_permute_store_chain()).
4760 In case of both multiple types and interleaving, above vector stores and
4761 permutation stmts are created for every copy. The result vector stmts are
4762 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
4763 STMT_VINFO_RELATED_STMT for the next copies.
4764 */
4768 {
4769 tree new_stmt;
4770 tree ptr_incr;
4773 {
4775 {
4776 /* Get vectorized arguments for SLP_NODE. */
4780 }
4781 else
4782 {
4783 /* For interleaved stores we collect vectorized defs for all the
4784 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
4785 used as an input to vect_permute_store_chain(), and OPRNDS as
4786 an input to vect_get_vec_def_for_stmt_copy() for the next copy.
4788 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4789 OPRNDS are of size 1. */
4792 {
4793 /* Since gaps are not supported for interleaved stores,
4794 GROUP_SIZE is the exact number of stmts in the chain.
4795 Therefore, NEXT_STMT can't be NULL_TREE. In case that
4796 there is no interleaving, GROUP_SIZE is 1, and only one
4797 iteration of the loop will be executed. */
4802 NULL);
4806 }
4807 }
4812 }
4813 else
4814 {
4815 /* FORNOW SLP doesn't work for multiple types. */
4818 /* For interleaved stores we created vectorized defs for all the
4819 defs stored in OPRNDS in the previous iteration (previous copy).
4820 DR_CHAIN is then used as an input to vect_permute_store_chain(),
4821 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
4822 next copy.
4823 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
4824 OPRNDS are of size 1. */
4826 {
4831 }
4832 dataref_ptr =
4834 }
4837 {
4839 /* Permute. */
4843 }
4847 {
4849 /* Bump the vector pointer. */
4851 NULL_TREE);
4856 /* For strided stores vectorized defs are interleaved in
4857 vect_permute_store_chain(). */
4861 /* Arguments are ready. Create the new vector stmt. */
4868 else
4875 }
4876 }
4879 }
4882 /* Function vect_setup_realignment
4884 This function is called when vectorizing an unaligned load using
4885 the dr_explicit_realign[_optimized] scheme.
4886 This function generates the following code at the loop prolog:
4888 p = initial_addr;
4889 x msq_init = *(floor(p)); # prolog load
4890 realignment_token = call target_builtin;
4891 loop:
4892 x msq = phi (msq_init, ---)
4894 The stmts marked with x are generated only for the case of
4895 dr_explicit_realign_optimized.
4897 The code above sets up a new (vector) pointer, pointing to the first
4898 location accessed by STMT, and a "floor-aligned" load using that pointer.
4899 It also generates code to compute the "realignment-token" (if the relevant
4900 target hook was defined), and creates a phi-node at the loop-header bb
4901 whose arguments are the result of the prolog-load (created by this
4902 function) and the result of a load that takes place in the loop (to be
4903 created by the caller to this function).
4905 For the case of dr_explicit_realign_optimized:
4906 The caller to this function uses the phi-result (msq) to create the
4907 realignment code inside the loop, and sets up the missing phi argument,
4908 as follows:
4909 loop:
4910 msq = phi (msq_init, lsq)
4911 lsq = *(floor(p')); # load in loop
4912 result = realign_load (msq, lsq, realignment_token);
4914 For the case of dr_explicit_realign:
4915 loop:
4916 msq = *(floor(p)); # load in loop
4917 p' = p + (VS-1);
4918 lsq = *(floor(p')); # load in loop
4919 result = realign_load (msq, lsq, realignment_token);
4921 Input:
4922 STMT - (scalar) load stmt to be vectorized. This load accesses
4923 a memory location that may be unaligned.
4924 BSI - place where new code is to be inserted.
4925 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
4926 is used.
4928 Output:
4929 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4930 target hook, if defined.
4931 Return value - the result of the loop-header phi node. */
4933 static tree
4937 tree init_addr,
4939 {
4944 edge pe;
4946 tree vec_dest;
4947 tree inc;
4948 tree ptr;
4949 tree data_ref;
4950 tree new_stmt;
4951 basic_block new_bb;
4953 tree new_temp;
4954 tree phi_stmt;
4966 /* We need to generate three things:
4967 1. the misalignment computation
4968 2. the extra vector load (for the optimized realignment scheme).
4969 3. the phi node for the two vectors from which the realignment is
4970 done (for the optimized realignment scheme).
4971 */
4973 /* 1. Determine where to generate the misalignment computation.
4975 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
4976 calculation will be generated by this function, outside the loop (in the
4977 preheader). Otherwise, INIT_ADDR had already been computed for us by the
4978 caller, inside the loop.
4980 Background: If the misalignment remains fixed throughout the iterations of
4981 the loop, then both realignment schemes are applicable, and also the
4982 misalignment computation can be done outside LOOP. This is because we are
4983 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
4984 are a multiple of VS (the Vector Size), and therefore the misalignment in
4985 different vectorized LOOP iterations is always the same.
4986 The problem arises only if the memory access is in an inner-loop nested
4987 inside LOOP, which is now being vectorized using outer-loop vectorization.
4988 This is the only case when the misalignment of the memory access may not
4989 remain fixed throughout the iterations of the inner-loop (as explained in
4990 detail in vect_supportable_dr_alignment). In this case, not only is the
4991 optimized realignment scheme not applicable, but also the misalignment
4992 computation (and generation of the realignment token that is passed to
4993 REALIGN_LOAD) have to be done inside the loop.
4995 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
4996 or not, which in turn determines if the misalignment is computed inside
4997 the inner-loop, or outside LOOP. */
5000 {
5003 }
5006 /* 2. Determine where to generate the extra vector load.
5008 For the optimized realignment scheme, instead of generating two vector
5009 loads in each iteration, we generate a single extra vector load in the
5010 preheader of the loop, and in each iteration reuse the result of the
5011 vector load from the previous iteration. In case the memory access is in
5012 an inner-loop nested inside LOOP, which is now being vectorized using
5013 outer-loop vectorization, we need to determine whether this initial vector
5014 load should be generated at the preheader of the inner-loop, or can be
5015 generated at the preheader of LOOP. If the memory access has no evolution
5016 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
5017 to be generated inside LOOP (in the preheader of the inner-loop). */
5020 {
5025 }
5026 else
5031 /* 3. For the case of the optimized realignment, create the first vector
5032 load at the loop preheader. */
5035 {
5036 /* Create msq_init = *(floor(p1)) in the loop preheader */
5050 }
5052 /* 4. Create realignment token using a target builtin, if available.
5053 It is done either inside the containing loop, or before LOOP (as
5054 determined above). */
5057 {
5058 tree builtin_decl;
5060 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
5063 else
5064 {
5065 /* Generate the INIT_ADDR computation outside LOOP. */
5071 }
5083 else
5084 {
5085 /* Generate the misalignment computation outside LOOP. */
5089 }
5093 /* The result of the CALL_EXPR to this builtin is determined from
5094 the value of the parameter and no global variables are touched
5095 which makes the builtin a "const" function. Requiring the
5096 builtin to have the "const" attribute makes it unnecessary
5097 to call mark_call_clobbered. */
5099 }
5108 /* 5. Create msq = phi <msq_init, lsq> in loop */
5118 }
5121 /* Function vect_strided_load_supported.
5123 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
5124 and FALSE otherwise. */
5126 static bool
5128 {
5136 {
5140 }
5143 {
5147 }
5151 {
5155 }
5158 {
5162 }
5164 }
5167 /* Function vect_permute_load_chain.
5169 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
5170 a power of 2, generate extract_even/odd stmts to reorder the input data
5171 correctly. Return the final references for loads in RESULT_CHAIN.
5173 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
5174 The input is 4 vectors each containing 8 elements. We assign a number to each
5175 element, the input sequence is:
5177 1st vec: 0 1 2 3 4 5 6 7
5178 2nd vec: 8 9 10 11 12 13 14 15
5179 3rd vec: 16 17 18 19 20 21 22 23
5180 4th vec: 24 25 26 27 28 29 30 31
5182 The output sequence should be:
5184 1st vec: 0 4 8 12 16 20 24 28
5185 2nd vec: 1 5 9 13 17 21 25 29
5186 3rd vec: 2 6 10 14 18 22 26 30
5187 4th vec: 3 7 11 15 19 23 27 31
5189 i.e., the first output vector should contain the first elements of each
5190 interleaving group, etc.
5192 We use extract_even/odd instructions to create such output. The input of each
5193 extract_even/odd operation is two vectors
5194 1st vec 2nd vec
5195 0 1 2 3 4 5 6 7
5197 and the output is the vector of extracted even/odd elements. The output of
5198 extract_even will be: 0 2 4 6
5199 and of extract_odd: 1 3 5 7
5202 The permutation is done in log LENGTH stages. In each stage extract_even and
5203 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
5204 order. In our example,
5206 E1: extract_even (1st vec, 2nd vec)
5207 E2: extract_odd (1st vec, 2nd vec)
5208 E3: extract_even (3rd vec, 4th vec)
5209 E4: extract_odd (3rd vec, 4th vec)
5211 The output for the first stage will be:
5213 E1: 0 2 4 6 8 10 12 14
5214 E2: 1 3 5 7 9 11 13 15
5215 E3: 16 18 20 22 24 26 28 30
5216 E4: 17 19 21 23 25 27 29 31
5218 In order to proceed and create the correct sequence for the next stage (or
5219 for the correct output, if the second stage is the last one, as in our
5220 example), we first put the output of extract_even operation and then the
5221 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
5222 The input for the second stage is:
5224 1st vec (E1): 0 2 4 6 8 10 12 14
5225 2nd vec (E3): 16 18 20 22 24 26 28 30
5226 3rd vec (E2): 1 3 5 7 9 11 13 15
5227 4th vec (E4): 17 19 21 23 25 27 29 31
5229 The output of the second stage:
5231 E1: 0 4 8 12 16 20 24 28
5232 E2: 2 6 10 14 18 22 26 30
5233 E3: 1 5 9 13 17 21 25 29
5234 E4: 3 7 11 15 19 23 27 31
5236 And RESULT_CHAIN after reordering:
5238 1st vec (E1): 0 4 8 12 16 20 24 28
5239 2nd vec (E3): 1 5 9 13 17 21 25 29
5240 3rd vec (E2): 2 6 10 14 18 22 26 30
5241 4th vec (E4): 3 7 11 15 19 23 27 31. */
5243 static bool
5246 tree stmt,
5249 {
5252 tree tmp;
5256 /* Check that the operation is supported. */
5262 {
5264 {
5268 /* data_ref = permute_even (first_data_ref, second_data_ref); */
5284 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
5298 }
5300 }
5302 }
5305 /* Function vect_transform_strided_load.
5307 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
5308 to perform their permutation and ascribe the result vectorized statements to
5309 the scalar statements.
5310 */
5312 static bool
5315 {
5321 tree tmp_data_ref;
5323 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
5324 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
5325 vectors, that are ready for vector computation. */
5327 /* Permute. */
5331 /* Put a permuted data-ref in the VECTORIZED_STMT field.
5332 Since we scan the chain starting from it's first node, their order
5333 corresponds the order of data-refs in RESULT_CHAIN. */
5337 {
5341 /* Skip the gaps. Loads created for the gaps will be removed by dead
5342 code elimination pass later.
5343 DR_GROUP_GAP is the number of steps in elements from the previous
5344 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
5345 correspond to the gaps.
5346 */
5348 {
5349 gap_count++;
5351 }
5354 {
5356 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
5357 copies, and we put the new vector statement in the first available
5358 RELATED_STMT. */
5361 else
5362 {
5367 {
5370 }
5372 }
5375 /* If NEXT_STMT accesses the same DR as the previous statement,
5376 put the same TMP_DATA_REF as its vectorized statement; otherwise
5377 get the next data-ref from RESULT_CHAIN. */
5380 }
5381 }
5383 }
5386 /* vectorizable_load.
5388 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
5389 can be vectorized.
5390 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5391 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
5392 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5394 bool
5396 slp_tree slp_node)
5397 {
5398 tree scalar_dest;
5401 tree op;
5403 stmt_vec_info prev_stmt_info;
5410 tree new_temp;
5413 tree dummy;
5416 tree ptr_incr;
5426 tree first_stmt;
5427 tree scalar_type;
5434 /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
5435 this, so we can safely override NCOPIES with 1 here. */
5441 /* FORNOW. This restriction should be relaxed. */
5443 {
5447 }
5455 /* FORNOW: not yet supported. */
5457 {
5461 }
5463 /* Is vectorizable load? */
5483 /* FORNOW. In some cases can vectorize even if data-type not supported
5484 (e.g. - data copies). */
5486 {
5490 }
5492 /* Check if the load is a part of an interleaving chain. */
5494 {
5496 /* FORNOW */
5499 /* Check if interleaving is supported. */
5503 }
5506 {
5510 }
5515 /** Transform. **/
5518 {
5520 /* Check if the chain of loads is already vectorized. */
5522 {
5525 }
5530 /* VEC_NUM is the number of vect stmts to be created for this group. */
5532 {
5535 }
5536 else
5538 }
5539 else
5540 {
5544 }
5549 /* In case the vectorization factor (VF) is bigger than the number
5550 of elements that we can fit in a vectype (nunits), we have to generate
5551 more than one vector stmt - i.e - we need to "unroll" the
5552 vector stmt by a factor VF/nunits. In doing so, we record a pointer
5553 from one copy of the vector stmt to the next, in the field
5554 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
5555 stages to find the correct vector defs to be used when vectorizing
5556 stmts that use the defs of the current stmt. The example below illustrates
5557 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
5558 4 vectorized stmts):
5560 before vectorization:
5561 RELATED_STMT VEC_STMT
5562 S1: x = memref - -
5563 S2: z = x + 1 - -
5565 step 1: vectorize stmt S1:
5566 We first create the vector stmt VS1_0, and, as usual, record a
5567 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
5568 Next, we create the vector stmt VS1_1, and record a pointer to
5569 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
5570 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
5571 stmts and pointers:
5572 RELATED_STMT VEC_STMT
5573 VS1_0: vx0 = memref0 VS1_1 -
5574 VS1_1: vx1 = memref1 VS1_2 -
5575 VS1_2: vx2 = memref2 VS1_3 -
5576 VS1_3: vx3 = memref3 - -
5577 S1: x = load - VS1_0
5578 S2: z = x + 1 - -
5580 See in documentation in vect_get_vec_def_for_stmt_copy for how the
5581 information we recorded in RELATED_STMT field is used to vectorize
5582 stmt S2. */
5584 /* In case of interleaving (non-unit strided access):
5586 S1: x2 = &base + 2
5587 S2: x0 = &base
5588 S3: x1 = &base + 1
5589 S4: x3 = &base + 3
5591 Vectorized loads are created in the order of memory accesses
5592 starting from the access of the first stmt of the chain:
5594 VS1: vx0 = &base
5595 VS2: vx1 = &base + vec_size*1
5596 VS3: vx3 = &base + vec_size*2
5597 VS4: vx4 = &base + vec_size*3
5599 Then permutation statements are generated:
5601 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
5602 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
5603 ...
5605 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
5606 (the order of the data-refs in the output of vect_permute_load_chain
5607 corresponds to the order of scalar stmts in the interleaving chain - see
5608 the documentation of vect_permute_load_chain()).
5609 The generation of permutation stmts and recording them in
5610 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
5612 In case of both multiple types and interleaving, the vector loads and
5613 permutation stmts above are created for every copy. The result vector stmts
5614 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
5615 STMT_VINFO_RELATED_STMT for the next copies. */
5617 /* If the data reference is aligned (dr_aligned) or potentially unaligned
5618 on a target that supports unaligned accesses (dr_unaligned_supported)
5619 we generate the following code:
5620 p = initial_addr;
5621 indx = 0;
5622 loop {
5623 p = p + indx * vectype_size;
5624 vec_dest = *(p);
5625 indx = indx + 1;
5626 }
5628 Otherwise, the data reference is potentially unaligned on a target that
5629 does not support unaligned accesses (dr_explicit_realign_optimized) -
5630 then generate the following code, in which the data in each iteration is
5631 obtained by two vector loads, one from the previous iteration, and one
5632 from the current iteration:
5633 p1 = initial_addr;
5634 msq_init = *(floor(p1))
5635 p2 = initial_addr + VS - 1;
5636 realignment_token = call target_builtin;
5637 indx = 0;
5638 loop {
5639 p2 = p2 + indx * vectype_size
5640 lsq = *(floor(p2))
5641 vec_dest = realign_load (msq, lsq, realignment_token)
5642 indx = indx + 1;
5643 msq = lsq;
5644 } */
5646 /* If the misalignment remains the same throughout the execution of the
5647 loop, we can create the init_addr and permutation mask at the loop
5648 preheader. Otherwise, it needs to be created inside the loop.
5649 This can only occur when vectorizing memory accesses in the inner-loop
5650 nested within an outer-loop that is being vectorized. */
5654 {
5657 }
5662 {
5667 {
5670 }
5671 }
5672 else
5677 {
5678 /* 1. Create the vector pointer update chain. */
5684 else
5685 dataref_ptr =
5689 {
5692 NULL_TREE);
5694 /* 2. Create the vector-load in the loop. */
5696 {
5702 {
5707 data_ref =
5710 }
5712 {
5719 dr_explicit_realign,
5737 }
5743 }
5751 /* 3. Handle explicit realignment if necessary/supported. Create in
5752 loop: vec_dest = realign_load (msq, lsq, realignment_token) */
5755 {
5761 realignment_token);
5768 {
5772 }
5773 }
5775 /* 4. Handle invariant-load. */
5777 {
5781 {
5786 /* CHECKME: bitpos depends on endianess? */
5792 vec_dest =
5801 /* FIXME: use build_constructor directly. */
5805 }
5806 else
5808 }
5810 /* Collect vector loads and later create their permutation in
5811 vect_transform_strided_load (). */
5815 /* Store vector loads in the corresponding SLP_NODE. */
5818 }
5820 /* FORNOW: SLP with multiple types is unsupported. */
5825 {
5830 }
5831 else
5832 {
5835 else
5838 }
5839 }
5842 }
5845 /* Function vectorizable_live_operation.
5847 STMT computes a value that is used outside the loop. Check if
5848 it can be supported. */
5850 bool
5854 {
5855 tree operation;
5861 tree op;
5876 /* FORNOW. CHECKME. */
5883 /* FORNOW: support only if all uses are invariant. This means
5884 that the scalar operations can remain in place, unvectorized.
5885 The original last scalar value that they compute will be used. */
5888 {
5891 {
5895 }
5899 }
5901 /* No transformation is required for the cases we currently support. */
5903 }
5906 /* Function vect_is_simple_cond.
5908 Input:
5909 LOOP - the loop that is being vectorized.
5910 COND - Condition that is checked for simple use.
5912 Returns whether a COND can be vectorized. Checks whether
5913 condition operands are supportable using vec_is_simple_use. */
5915 static bool
5917 {
5919 tree def;
5929 {
5933 }
5939 {
5943 }
5949 }
5951 /* vectorizable_condition.
5953 Check if STMT is conditional modify expression that can be vectorized.
5954 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5955 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
5956 at BSI.
5958 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5960 bool
5962 {
5971 tree new_temp;
5974 tree def;
5989 /* FORNOW: SLP not supported. */
5993 /* FORNOW: not yet supported. */
5995 {
5999 }
6001 /* Is vectorizable conditional operation? */
6017 /* We do not handle two different vector types for the condition
6018 and the values. */
6023 {
6028 }
6035 {
6040 }
6050 {
6053 }
6055 /* Transform */
6057 /* Handle def. */
6061 /* Handle cond expr. */
6062 vec_cond_lhs =
6064 vec_cond_rhs =
6069 /* Arguments are ready. create the new vector stmt. */
6081 }
6084 /* Function vect_transform_stmt.
6086 Create a vectorized stmt to replace STMT, and insert it at BSI. */
6088 static bool
6090 slp_tree slp_node)
6091 {
6095 tree orig_stmt_in_pattern;
6099 {
6142 {
6143 /* In case of interleaving, the whole chain is vectorized when the
6144 last store in the chain is reached. Store stmts before the last
6145 one are skipped, and there vec_stmt_info shouldn't be freed
6146 meanwhile. */
6150 }
6151 else
6174 {
6178 }
6179 }
6183 {
6186 }
6189 {
6193 {
6195 /* STMT was inserted by the vectorizer to replace a computation idiom.
6196 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
6197 computed this idiom. We need to record a pointer to VEC_STMT in
6198 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
6199 documentation of vect_pattern_recog. */
6201 {
6204 }
6205 }
6206 }
6209 }
6212 /* This function builds ni_name = number of iterations loop executes
6213 on the loop preheader. */
6215 static tree
6217 {
6219 edge pe;
6229 {
6232 }
6235 }
6238 /* This function generates the following statements:
6240 ni_name = number of iterations loop executes
6241 ratio = ni_name / vf
6242 ratio_mult_vf_name = ratio * vf
6244 and places them at the loop preheader edge. */
6246 static void
6251 {
6253 edge pe;
6254 basic_block new_bb;
6256 tree var;
6257 tree ratio_name;
6258 tree ratio_mult_vf_name;
6262 tree log_vf;
6266 /* Generate temporary variable that contains
6267 number of iterations loop executes. */
6272 /* Create: ratio = ni >> log2(vf) */
6276 {
6284 }
6286 /* Create: ratio_mult_vf = ratio << log2 (vf). */
6291 {
6300 }
6307 }
6310 /* Function vect_update_ivs_after_vectorizer.
6312 "Advance" the induction variables of LOOP to the value they should take
6313 after the execution of LOOP. This is currently necessary because the
6314 vectorizer does not handle induction variables that are used after the
6315 loop. Such a situation occurs when the last iterations of LOOP are
6316 peeled, because:
6317 1. We introduced new uses after LOOP for IVs that were not originally used
6318 after LOOP: the IVs of LOOP are now used by an epilog loop.
6319 2. LOOP is going to be vectorized; this means that it will iterate N/VF
6320 times, whereas the loop IVs should be bumped N times.
6322 Input:
6323 - LOOP - a loop that is going to be vectorized. The last few iterations
6324 of LOOP were peeled.
6325 - NITERS - the number of iterations that LOOP executes (before it is
6326 vectorized). i.e, the number of times the ivs should be bumped.
6327 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
6328 coming out from LOOP on which there are uses of the LOOP ivs
6329 (this is the path from LOOP->exit to epilog_loop->preheader).
6331 The new definitions of the ivs are placed in LOOP->exit.
6332 The phi args associated with the edge UPDATE_E in the bb
6333 UPDATE_E->dest are updated accordingly.
6335 Assumption 1: Like the rest of the vectorizer, this function assumes
6336 a single loop exit that has a single predecessor.
6338 Assumption 2: The phi nodes in the LOOP header and in update_bb are
6339 organized in the same order.
6341 Assumption 3: The access function of the ivs is simple enough (see
6342 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
6344 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
6345 coming out of LOOP on which the ivs of LOOP are used (this is the path
6346 that leads to the epilog loop; other paths skip the epilog loop). This
6347 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
6348 needs to have its phis updated.
6349 */
6351 static void
6353 edge update_e)
6354 {
6360 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
6362 /* Make sure there exists a single-predecessor exit bb: */
6368 {
6370 tree evolution_part;
6371 tree init_expr;
6372 tree step_expr;
6374 block_stmt_iterator last_bsi;
6377 {
6380 }
6382 /* Skip virtual phi's. */
6384 {
6388 }
6390 /* Skip reduction phis. */
6392 {
6396 }
6400 evolution_part =
6404 /* FORNOW: We do not support IVs whose evolution function is a polynomial
6405 of degree >= 2 or exponential. */
6414 init_expr,
6418 else
6422 niters),
6423 step_expr),
6424 init_expr);
6435 /* Fix phi expressions in the successor bb. */
6437 }
6438 }
6441 /* Function vect_do_peeling_for_loop_bound
6443 Peel the last iterations of the loop represented by LOOP_VINFO.
6444 The peeled iterations form a new epilog loop. Given that the loop now
6445 iterates NITERS times, the new epilog loop iterates
6446 NITERS % VECTORIZATION_FACTOR times.
6448 The original loop will later be made to iterate
6449 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
6451 static void
6453 {
6457 edge update_e;
6458 basic_block preheader;
6469 /* Generate the following variables on the preheader of original loop:
6471 ni_name = number of iteration the original loop executes
6472 ratio = ni_name / vf
6473 ratio_mult_vf_name = ratio * vf */
6479 /* Analyze cost to set threshhold for vectorized loop. */
6484 /* Use the cost model only if it is more conservative than user specified
6485 threshold. */
6489 && (!min_scalar_loop_bound
6500 th);
6503 #ifdef ENABLE_CHECKING
6505 #endif
6507 /* A guard that controls whether the new_loop is to be executed or skipped
6508 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
6509 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
6510 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
6511 is on the path where the LOOP IVs are used and need to be updated. */
6516 else
6519 /* Update IVs of original loop as if they were advanced
6520 by ratio_mult_vf_name steps. */
6523 /* After peeling we have to reset scalar evolution analyzer. */
6527 }
6530 /* Function vect_gen_niters_for_prolog_loop
6532 Set the number of iterations for the loop represented by LOOP_VINFO
6533 to the minimum between LOOP_NITERS (the original iteration count of the loop)
6534 and the misalignment of DR - the data reference recorded in
6535 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
6536 this loop, the data reference DR will refer to an aligned location.
6538 The following computation is generated:
6540 If the misalignment of DR is known at compile time:
6541 addr_mis = int mis = DR_MISALIGNMENT (dr);
6542 Else, compute address misalignment in bytes:
6543 addr_mis = addr & (vectype_size - 1)
6545 prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
6547 (elem_size = element type size; an element is the scalar element
6548 whose type is the inner type of the vectype)
6550 For interleaving,
6552 prolog_niters = min ( LOOP_NITERS ,
6553 (VF/group_size - addr_mis/elem_size)&(VF/group_size-1) )
6554 where group_size is the size of the interleaved group.
6556 The above formulas assume that VF == number of elements in the vector. This
6557 may not hold when there are multiple-types in the loop.
6558 In this case, for some data-references in the loop the VF does not represent
6559 the number of elements that fit in the vector. Therefore, instead of VF we
6560 use TYPE_VECTOR_SUBPARTS. */
6562 static tree
6564 {
6569 edge pe;
6570 basic_block new_bb;
6581 {
6582 /* For interleaved access element size must be multiplied by the size of
6583 the interleaved group. */
6587 }
6592 {
6600 }
6601 else
6602 {
6610 tree elem_size_log =
6614 tree byte_misalign;
6615 tree elem_misalign;
6620 /* Create: byte_misalign = addr & (vectype_size - 1) */
6621 byte_misalign =
6624 /* Create: elem_misalign = byte_misalign / element_size */
6625 elem_misalign =
6628 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
6632 }
6634 /* Create: prolog_loop_niters = min (iters, loop_niters) */
6635 /* If the loop bound is known at compile time we already verified that it is
6636 greater than vf; since the misalignment ('iters') is at most vf, there's
6637 no need to generate the MIN_EXPR in this case. */
6642 {
6645 }
6651 /* Insert stmt on loop preheader edge. */
6653 {
6656 }
6659 }
6662 /* Function vect_update_init_of_dr
6664 NITERS iterations were peeled from LOOP. DR represents a data reference
6665 in LOOP. This function updates the information recorded in DR to
6666 account for the fact that the first NITERS iterations had already been
6667 executed. Specifically, it updates the OFFSET field of DR. */
6669 static void
6671 {
6677 }
6680 /* Function vect_update_inits_of_drs
6682 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
6683 This function updates the information recorded for the data references in
6684 the loop to account for the fact that the first NITERS iterations had
6685 already been executed. Specifically, it updates the initial_condition of
6686 the access_function of all the data_references in the loop. */
6688 static void
6690 {
6700 }
6703 /* Function vect_do_peeling_for_alignment
6705 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
6706 'niters' is set to the misalignment of one of the data references in the
6707 loop, thereby forcing it to refer to an aligned location at the beginning
6708 of the execution of this loop. The data reference for which we are
6709 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
6711 static void
6713 {
6716 tree n_iters;
6727 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
6728 new_loop =
6732 #ifdef ENABLE_CHECKING
6734 #endif
6736 /* Update number of times loop executes. */
6741 /* Update the init conditions of the access functions of all data refs. */
6744 /* After peeling we have to reset scalar evolution analyzer. */
6748 }
6751 /* Function vect_create_cond_for_align_checks.
6753 Create a conditional expression that represents the alignment checks for
6754 all of data references (array element references) whose alignment must be
6755 checked at runtime.
6757 Input:
6758 LOOP_VINFO - two fields of the loop information are used.
6759 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
6760 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
6762 Output:
6763 COND_EXPR_STMT_LIST - statements needed to construct the conditional
6764 expression.
6765 The returned value is the conditional expression to be used in the if
6766 statement that controls which version of the loop gets executed at runtime.
6768 The algorithm makes two assumptions:
6769 1) The number of bytes "n" in a vector is a power of 2.
6770 2) An address "a" is aligned if a%n is zero and that this
6771 test can be done as a&(n-1) == 0. For example, for 16
6772 byte vectors the test is a&0xf == 0. */
6774 static tree
6777 {
6783 tree mask_cst;
6785 tree psize;
6786 tree int_ptrsize_type;
6790 tree ptrsize_zero;
6792 /* Check that mask is one less than a power of 2, i.e., mask is
6793 all zeros followed by all ones. */
6796 /* CHECKME: what is the best integer or unsigned type to use to hold a
6797 cast from a pointer value? */
6799 int_ptrsize_type
6802 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
6803 of the first vector of the i'th data reference. */
6806 {
6808 tree addr_base;
6812 /* create: addr_tmp = (int)(address_of_first_vector) */
6828 /* The addresses are OR together. */
6831 {
6832 /* create: or_tmp = or_tmp | addr_tmp */
6843 }
6844 else
6851 /* create: and_tmp = or_tmp & mask */
6861 /* Make and_tmp the left operand of the conditional test against zero.
6862 if and_tmp has a nonzero bit then some address is unaligned. */
6866 }
6868 /* Function vect_vfa_segment_size.
6870 Create an expression that computes the size of segment
6871 that will be accessed for a data reference. The functions takes into
6872 account that realignment loads may access one more vector.
6874 Input:
6875 DR: The data reference.
6876 VECT_FACTOR: vectorization factor.
6878 Return an expression whose value is the size of segment which will be
6879 accessed by DR. */
6881 static tree
6883 {
6888 {
6889 tree vector_size = TYPE_SIZE_UNIT
6894 }
6896 }
6898 /* Function vect_create_cond_for_alias_checks.
6900 Create a conditional expression that represents the run-time checks for
6901 overlapping of address ranges represented by a list of data references
6902 relations passed as input.
6904 Input:
6905 COND_EXPR - input conditional expression. New conditions will be chained
6906 with logical and operation.
6907 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
6908 to be checked.
6910 Output:
6911 COND_EXPR - conditional expression.
6912 COND_EXPR_STMT_LIST - statements needed to construct the conditional
6913 expression.
6916 The returned value is the conditional expression to be used in the if
6917 statement that controls which version of the loop gets executed at runtime.
6918 */
6920 static void
6924 {
6928 tree vect_factor =
6931 ddr_p ddr;
6933 tree part_cond_expr;
6935 /* Create expression
6936 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
6937 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
6938 &&
6939 ...
6940 &&
6941 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
6942 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
6948 {
6959 {
6962 }
6968 {
6971 }
6973 addr_base_a =
6976 addr_base_b =
6984 {
6990 }
6993 part_cond_expr =
6997 addr_base_a,
6998 segment_length_a),
6999 addr_base_b),
7002 addr_base_b,
7003 segment_length_b),
7004 addr_base_a));
7009 else
7011 }
7016 }
7018 /* Function vect_loop_versioning.
7020 If the loop has data references that may or may not be aligned or/and
7021 has data reference relations whose independence was not proven then
7022 two versions of the loop need to be generated, one which is vectorized
7023 and one which isn't. A test is then generated to control which of the
7024 loops is executed. The test checks for the alignment of all of the
7025 data references that may or may not be aligned. An additional
7026 sequence of runtime tests is generated for each pairs of DDRs whose
7027 independence was not proven. The vectorized version of loop is
7028 executed only if both alias and alignment tests are passed. */
7030 static void
7032 {
7037 basic_block condition_bb;
7038 block_stmt_iterator cond_exp_bsi;
7039 basic_block merge_bb;
7040 basic_block new_exit_bb;
7044 tree gimplify_stmt_list;
7051 cond_expr =
7057 cond_expr =
7059 cond_expr =
7061 NULL_TREE);
7069 /* Loop versioning violates an assumption we try to maintain during
7070 vectorization - that the loop exit block has a single predecessor.
7071 After versioning, the exit block of both loop versions is the same
7072 basic block (i.e. it has two predecessors). Just in order to simplify
7073 following transformations in the vectorizer, we fix this situation
7074 here by adding a new (empty) block on the exit-edge of the loop,
7075 with the proper loop-exit phis to maintain loop-closed-form. */
7085 {
7087 new_exit_bb);
7091 }
7093 /* End loop-exit-fixes after versioning. */
7097 {
7100 }
7101 }
7103 /* Remove a group of stores (for SLP or interleaving), free their
7104 stmt_vec_info. */
7106 static void
7108 {
7109 stmt_ann_t ann;
7111 tree tmp;
7112 stmt_vec_info next_stmt_info;
7113 block_stmt_iterator next_si;
7116 {
7117 /* Free the attached stmt_vec_info and remove the stmt. */
7126 }
7127 }
7130 /* Vectorize SLP instance tree in postorder. */
7132 static bool
7134 {
7135 tree stmt;
7137 block_stmt_iterator si;
7138 stmt_vec_info stmt_info;
7152 {
7155 }
7160 {
7162 /* If IS_STORE is TRUE, the vectorization of the
7163 interleaving chain was completed - free all the stores in
7164 the chain. */
7166 else
7167 /* FORNOW: SLP originates only from strided stores. */
7171 }
7173 /* FORNOW: SLP originates only from strided stores. */
7175 }
7178 static bool
7180 {
7183 slp_instance instance;
7190 {
7192 /* For each SLP instance calculate number of vector stmts to be created
7193 for the scalar stmts in each node of the SLP tree. Number of vector
7194 elements in one vector iteration is the number of scalar elements in
7195 one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
7196 size. */
7199 /* Schedule the tree of INSTANCE. */
7201 vec_stmts_size);
7206 }
7209 }
7211 /* Function vect_transform_loop.
7213 The analysis phase has determined that the loop is vectorizable.
7214 Vectorize the loop - created vectorized stmts to replace the scalar
7215 stmts in the loop, and update the loop exit condition. */
7217 void
7219 {
7235 /* CHECKME: we wouldn't need this if we called update_ssa once
7236 for all loops. */
7239 /* Peel the loop if there are data refs with unknown alignment.
7240 Only one data ref with unknown store is allowed. */
7245 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
7246 compile time constant), or it is a constant that doesn't divide by the
7247 vectorization factor, then an epilog loop needs to be created.
7248 We therefore duplicate the loop: the original loop will be vectorized,
7249 and will compute the first (n/VF) iterations. The second copy of the loop
7250 will remain scalar and will compute the remaining (n%VF) iterations.
7251 (VF is the vectorization factor). */
7257 else
7261 /* 1) Make sure the loop header has exactly two entries
7262 2) Make sure we have a preheader basic block. */
7268 /* FORNOW: the vectorizer supports only loops which body consist
7269 of one basic block (header + empty latch). When the vectorizer will
7270 support more involved loop forms, the order by which the BBs are
7271 traversed need to be reconsidered. */
7274 {
7276 stmt_vec_info stmt_info;
7277 tree phi;
7280 {
7282 {
7285 }
7300 {
7304 }
7305 }
7308 {
7313 {
7316 }
7320 /* vector stmts created in the outer-loop during vectorization of
7321 stmts in an inner-loop may not have a stmt_info, and do not
7322 need to be vectorized. */
7324 {
7327 }
7331 {
7334 }
7337 nunits =
7342 /* For SLP VF is set according to unrolling factor, and not to
7343 vector size, hence for SLP this print is not valid. */
7346 /* SLP. Schedule all the SLP instances when the first SLP stmt is
7347 reached. */
7349 {
7351 {
7359 /* IS_STORE is true if STMT is a store. Stores cannot be of
7360 hybrid SLP type. They are removed in
7361 vect_schedule_slp_instance and their vinfo is destroyed. */
7363 {
7366 }
7367 }
7369 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
7371 {
7374 }
7375 }
7377 /* -------- vectorize statement ------------ */
7384 {
7385 stmt_ann_t ann;
7387 {
7388 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
7389 interleaving chain was completed - free all the stores in
7390 the chain. */
7392 tree tmp;
7393 stmt_vec_info next_stmt_info;
7396 {
7399 /* Free the attached stmt_vec_info and remove the stmt. */
7406 }
7409 }
7410 else
7411 {
7412 /* Free the attached stmt_vec_info and remove the stmt. */
7418 }
7419 }
7428 /* The memory tags and pointers in vectorized statements need to
7429 have their SSA forms updated. FIXME, why can't this be delayed
7430 until all the loops have been transformed? */
7437 }