| blob | 07c077329a3b28adf706e6a6eef5b71b6fed2f03 |
1 /* Transformation Utilities for Loop Vectorization.
2 Copyright (C) 2003,2004,2005,2006 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
49 /* Utility functions for the code transformation. */
52 static tree vect_create_data_ref_ptr
59 static void vect_finish_stmt_generation
66 /* Utility function dealing with loop peeling (not peeling itself). */
67 static void vect_generate_tmps_on_preheader
77 /* Function vect_get_new_vect_var.
79 Returns a name for a new variable. The current naming scheme appends the
80 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
81 the name of vectorizer generated variables, and appends that to NAME if
82 provided. */
84 static tree
86 {
88 tree new_vect_var;
91 {
103 }
107 else
110 /* Mark vector typed variable as a gimple register variable. */
115 }
118 /* Function vect_create_addr_base_for_vector_ref.
120 Create an expression that computes the address of the first memory location
121 that will be accessed for a data reference.
123 Input:
124 STMT: The statement containing the data reference.
125 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
126 OFFSET: Optional. If supplied, it is be added to the initial address.
128 Output:
129 1. Return an SSA_NAME whose value is the address of the memory location of
130 the first vector of the data reference.
131 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
132 these statement(s) which define the returned SSA_NAME.
134 FORNOW: We are only handling array accesses with step 1. */
136 static tree
139 tree offset)
140 {
145 tree vec_stmt;
152 /* Create base_offset */
160 {
162 tree step;
164 /* For interleaved access step we divide STEP by the size of the
165 interleaving group. */
170 else
179 }
181 /* base + base_offset */
183 base_offset);
187 /* addr_expr = addr_base */
199 {
202 }
204 }
207 /* Function vect_create_data_ref_ptr.
209 Create a new pointer to vector type (vp), that points to the first location
210 accessed in the loop by STMT, along with the def-use update chain to
211 appropriately advance the pointer through the loop iterations. Also set
212 aliasing information for the pointer. This vector pointer is used by the
213 callers to this function to create a memory reference expression for vector
214 load/store access.
216 Input:
217 1. STMT: a stmt that references memory. Expected to be of the form
218 GIMPLE_MODIFY_STMT <name, data-ref> or
219 GIMPLE_MODIFY_STMT <data-ref, name>.
220 2. BSI: block_stmt_iterator where new stmts can be added.
221 3. OFFSET (optional): an offset to be added to the initial address accessed
222 by the data-ref in STMT.
223 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
224 pointing to the initial address.
225 5. TYPE: if not NULL indicates the required type of the data-ref
227 Output:
228 1. Declare a new ptr to vector_type, and have it point to the base of the
229 data reference (initial addressed accessed by the data reference).
230 For example, for vector of type V8HI, the following code is generated:
232 v8hi *vp;
233 vp = (v8hi *)initial_address;
235 if OFFSET is not supplied:
236 initial_address = &a[init];
237 if OFFSET is supplied:
238 initial_address = &a[init + OFFSET];
240 Return the initial_address in INITIAL_ADDRESS.
242 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
243 update the pointer in each iteration of the loop.
245 Return the increment stmt that updates the pointer in PTR_INCR.
247 3. Return the pointer. */
249 static tree
254 {
255 tree base_name;
260 tree vect_ptr_type;
261 tree vect_ptr;
262 tree tag;
263 tree new_temp;
264 tree vec_stmt;
267 basic_block new_bb;
268 tree vect_ptr_init;
274 {
287 }
289 /** (1) Create the new vector-pointer variable: **/
292 else
298 /** (2) Add aliasing information to the new vector-pointer:
299 (The points-to info (DR_PTR_INFO) may be defined later.) **/
304 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
305 tag must be created with tag added to its may alias list. */
308 else
313 /** (3) Calculate the initial address the vector-pointer, and set
314 the vector-pointer to point to it before the loop: **/
316 /* Create: (&(base[init_val+offset]) in the loop preheader. */
318 offset);
324 /* Create: p = (vectype *) initial_base */
333 /** (4) Handle the updating of the vector-pointer inside the loop: **/
336 {
337 /* Copy the points-to information if it exists. */
341 }
342 else
343 {
344 block_stmt_iterator incr_bsi;
347 tree incr;
358 /* Copy the points-to information if it exists. */
360 {
363 }
370 }
371 }
374 /* Function bump_vector_ptr
376 Increment a pointer (to a vector type) by vector-size. Connect the new
377 increment stmt to the existing def-use update-chain of the pointer.
379 The pointer def-use update-chain before this function:
380 DATAREF_PTR = phi (p_0, p_2)
381 ....
382 PTR_INCR: p_2 = DATAREF_PTR + step
384 The pointer def-use update-chain after this function:
385 DATAREF_PTR = phi (p_0, p_2)
386 ....
387 NEW_DATAREF_PTR = DATAREF_PTR + vector_size
388 ....
389 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
391 Input:
392 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
393 in the loop.
394 PTR_INCR - the stmt that updates the pointer in each iteration of the loop.
395 The increment amount across iterations is also expected to be
396 vector_size.
397 BSI - location where the new update stmt is to be placed.
398 STMT - the original scalar memory-access stmt that is being vectorized.
400 Output: Return NEW_DATAREF_PTR as illustrated above.
402 */
404 static tree
406 tree stmt)
407 {
414 tree incr_stmt;
415 ssa_op_iter iter;
416 use_operand_p use_p;
417 tree new_dataref_ptr;
425 /* Update the vector-pointer's cross-iteration increment. */
427 {
432 else
434 }
436 /* Copy the points-to information if it exists. */
442 }
445 /* Function vect_create_destination_var.
447 Create a new temporary of type VECTYPE. */
449 static tree
451 {
452 tree vec_dest;
454 tree type;
469 }
472 /* Function vect_init_vector.
474 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
475 the vector elements of VECTOR_VAR. Return the DEF of INIT_STMT. It will be
476 used in the vectorization of STMT. */
478 static tree
480 {
484 tree new_var;
485 tree init_stmt;
486 tree vec_oprnd;
487 edge pe;
488 tree new_temp;
489 basic_block new_bb;
503 {
506 }
510 }
513 /* Function get_initial_def_for_induction
515 Input:
516 STMT - a stmt that performs an induction operation in the loop.
517 IV_PHI - the initial value of the induction variable
519 Output:
520 Return a vector variable, initialized with the first VF values of
521 the induction variable. E.g., for an iv with IV_PHI='X' and
522 evolution S, for a vector of 4 units, we want to return:
523 [X, X + S, X + 2*S, X + 3*S]. */
525 static tree
527 {
535 basic_block new_bb;
536 block_stmt_iterator bsi;
538 tree access_fn;
539 tree new_var;
540 tree new_name;
541 tree init_stmt;
548 tree expr;
554 {
559 {
564 }
567 }
576 /* Create the vector that holds the initial_value of the induction. */
581 {
582 /* Create: new_name = new_name + step_expr */
594 {
597 }
599 }
604 /* Create the vector that holds the step of the induction. */
614 /* Create the following def-use cycle:
615 loop prolog:
616 vec_init = [X, X+S, X+2*S, X+3*S]
617 vec_step = [VF*S, VF*S, VF*S, VF*S]
618 loop:
619 vec_iv = PHI <vec_init, vec_loop>
620 ...
621 STMT
622 ...
623 vec_loop = vec_iv + vec_step; */
625 /* Create the induction-phi that defines the induction-operand. */
633 /* Create the iv update inside the loop */
641 /* Set the arguments of the phi node: */
646 /* In case the vectorization factor (VF) is bigger than the number
647 of elements that we can fit in a vectype (nunits), we have to generate
648 more than one vector stmt - i.e - we need to "unroll" the
649 vector stmt by a factor VF/nunits. For more details see documentation
650 in vectorizable_operation. */
653 {
654 stmt_vec_info prev_stmt_vinfo;
656 /* Create the vector that holds the step of the induction. */
668 {
669 /* vec_i = vec_prev + vec_{step*nunits} */
680 }
681 }
684 {
689 }
693 }
696 /* Function vect_get_vec_def_for_operand.
698 OP is an operand in STMT. This function returns a (vector) def that will be
699 used in the vectorized stmt for STMT.
701 In the case that OP is an SSA_NAME which is defined in the loop, then
702 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
704 In case OP is an invariant or constant, a new stmt that creates a vector def
705 needs to be introduced. */
707 static tree
709 {
710 tree vec_oprnd;
711 tree vec_stmt;
712 tree def_stmt;
719 tree vec_inv;
720 tree vec_cst;
722 tree def;
726 tree vector_type;
729 {
732 }
737 {
739 {
742 }
744 {
747 }
748 }
751 {
752 /* Case 1: operand is a constant. */
754 {
758 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
763 {
765 }
770 }
772 /* Case 2: operand is defined outside the loop - loop invariant. */
774 {
778 /* Create 'vec_inv = {inv,inv,..,inv}' */
783 {
785 }
787 /* FIXME: use build_constructor directly. */
791 }
793 /* Case 3: operand is defined inside the loop. */
795 {
799 /* Get the def from the vectorized stmt. */
805 }
807 /* Case 4: operand is defined by a loop header phi - reduction */
809 {
812 /* Get the def before the loop */
815 }
817 /* Case 5: operand is defined by loop-header phi - induction. */
819 {
822 /* Get the def before the loop */
824 }
828 }
829 }
832 /* Function vect_get_vec_def_for_stmt_copy
834 Return a vector-def for an operand. This function is used when the
835 vectorized stmt to be created (by the caller to this function) is a "copy"
836 created in case the vectorized result cannot fit in one vector, and several
837 copies of the vector-stmt are required. In this case the vector-def is
838 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
839 of the stmt that defines VEC_OPRND.
840 DT is the type of the vector def VEC_OPRND.
842 Context:
843 In case the vectorization factor (VF) is bigger than the number
844 of elements that can fit in a vectype (nunits), we have to generate
845 more than one vector stmt to vectorize the scalar stmt. This situation
846 arises when there are multiple data-types operated upon in the loop; the
847 smallest data-type determines the VF, and as a result, when vectorizing
848 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
849 vector stmt (each computing a vector of 'nunits' results, and together
850 computing 'VF' results in each iteration). This function is called when
851 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
852 which VF=16 and nunits=4, so the number of copies required is 4):
854 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
856 S1: x = load VS1.0: vx.0 = memref0 VS1.1
857 VS1.1: vx.1 = memref1 VS1.2
858 VS1.2: vx.2 = memref2 VS1.3
859 VS1.3: vx.3 = memref3
861 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
862 VSnew.1: vz1 = vx.1 + ... VSnew.2
863 VSnew.2: vz2 = vx.2 + ... VSnew.3
864 VSnew.3: vz3 = vx.3 + ...
866 The vectorization of S1 is explained in vectorizable_load.
867 The vectorization of S2:
868 To create the first vector-stmt out of the 4 copies - VSnew.0 -
869 the function 'vect_get_vec_def_for_operand' is called to
870 get the relevant vector-def for each operand of S2. For operand x it
871 returns the vector-def 'vx.0'.
873 To create the remaining copies of the vector-stmt (VSnew.j), this
874 function is called to get the relevant vector-def for each operand. It is
875 obtained from the respective VS1.j stmt, which is recorded in the
876 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
878 For example, to obtain the vector-def 'vx.1' in order to create the
879 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
880 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
881 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
882 and return its def ('vx.1').
883 Overall, to create the above sequence this function will be called 3 times:
884 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
885 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
886 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
888 static tree
890 {
891 tree vec_stmt_for_operand;
892 stmt_vec_info def_stmt_info;
894 /* Do nothing; can reuse same def. */
908 }
911 /* Function vect_finish_stmt_generation.
913 Insert a new stmt. */
915 static void
918 {
927 {
930 }
932 /* Make sure bsi points to the stmt that is being vectorized. */
935 #ifdef USE_MAPPED_LOCATION
937 #else
939 #endif
940 }
943 #define ADJUST_IN_EPILOG 1
945 /* Function get_initial_def_for_reduction
947 Input:
948 STMT - a stmt that performs a reduction operation in the loop.
949 INIT_VAL - the initial value of the reduction variable
951 Output:
952 SCALAR_DEF - a tree that holds a value to be added to the final result
953 of the reduction (used for "ADJUST_IN_EPILOG" - see below).
954 Return a vector variable, initialized according to the operation that STMT
955 performs. This vector will be used as the initial value of the
956 vector of partial results.
958 Option1 ("ADJUST_IN_EPILOG"): Initialize the vector as follows:
959 add: [0,0,...,0,0]
960 mult: [1,1,...,1,1]
961 min/max: [init_val,init_val,..,init_val,init_val]
962 bit and/or: [init_val,init_val,..,init_val,init_val]
963 and when necessary (e.g. add/mult case) let the caller know
964 that it needs to adjust the result by init_val.
966 Option2: Initialize the vector as follows:
967 add: [0,0,...,0,init_val]
968 mult: [1,1,...,1,init_val]
969 min/max: [init_val,init_val,...,init_val]
970 bit and/or: [init_val,init_val,...,init_val]
971 and no adjustments are needed.
973 For example, for the following code:
975 s = init_val;
976 for (i=0;i<n;i++)
977 s = s + a[i];
979 STMT is 's = s + a[i]', and the reduction variable is 's'.
980 For a vector of 4 units, we want to return either [0,0,0,init_val],
981 or [0,0,0,0] and let the caller know that it needs to adjust
982 the result at the end by 'init_val'.
984 FORNOW: We use the "ADJUST_IN_EPILOG" scheme.
985 TODO: Use some cost-model to estimate which scheme is more profitable.
986 */
988 static tree
990 {
997 tree def;
1001 tree vector_type;
1006 {
1012 else
1015 #ifdef ADJUST_IN_EPILOG
1016 /* All the 'nunits' elements are set to 0. The final result will be
1017 adjusted by 'init_val' at the loop epilog. */
1020 #else
1021 /* 'nunits - 1' elements are set to 0; The last element is set to
1022 'init_val'. No further adjustments at the epilog are needed. */
1025 #endif
1037 }
1043 {
1044 /* Set the last element of the vector. */
1047 }
1053 else
1058 else
1062 }
1065 /* Function vect_create_epilog_for_reduction
1067 Create code at the loop-epilog to finalize the result of a reduction
1068 computation.
1070 VECT_DEF is a vector of partial results.
1071 REDUC_CODE is the tree-code for the epilog reduction.
1072 STMT is the scalar reduction stmt that is being vectorized.
1073 REDUCTION_PHI is the phi-node that carries the reduction computation.
1075 This function:
1076 1. Creates the reduction def-use cycle: sets the arguments for
1077 REDUCTION_PHI:
1078 The loop-entry argument is the vectorized initial-value of the reduction.
1079 The loop-latch argument is VECT_DEF - the vector of partial sums.
1080 2. "Reduces" the vector of partial results VECT_DEF into a single result,
1081 by applying the operation specified by REDUC_CODE if available, or by
1082 other means (whole-vector shifts or a scalar loop).
1083 The function also creates a new phi node at the loop exit to preserve
1084 loop-closed form, as illustrated below.
1086 The flow at the entry to this function:
1088 loop:
1089 vec_def = phi <null, null> # REDUCTION_PHI
1090 VECT_DEF = vector_stmt # vectorized form of STMT
1091 s_loop = scalar_stmt # (scalar) STMT
1092 loop_exit:
1093 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1094 use <s_out0>
1095 use <s_out0>
1097 The above is transformed by this function into:
1099 loop:
1100 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
1101 VECT_DEF = vector_stmt # vectorized form of STMT
1102 s_loop = scalar_stmt # (scalar) STMT
1103 loop_exit:
1104 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1105 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
1106 v_out2 = reduce <v_out1>
1107 s_out3 = extract_field <v_out2, 0>
1108 s_out4 = adjust_result <s_out3>
1109 use <s_out4>
1110 use <s_out4>
1111 */
1113 static void
1116 {
1118 tree vectype;
1122 basic_block exit_bb;
1123 tree scalar_dest;
1124 tree scalar_type;
1125 tree new_phi;
1126 block_stmt_iterator exit_bsi;
1127 tree vec_dest;
1128 tree new_temp;
1129 tree new_name;
1130 tree epilog_stmt;
1134 tree scalar_initial_def;
1135 tree vec_initial_def;
1136 tree orig_name;
1137 imm_use_iterator imm_iter;
1138 use_operand_p use_p;
1140 tree reduction_op;
1141 tree orig_stmt;
1142 tree use_stmt;
1151 /*** 1. Create the reduction def-use cycle ***/
1153 /* 1.1 set the loop-entry arg of the reduction-phi: */
1154 /* For the case of reduction, vect_get_vec_def_for_operand returns
1155 the scalar def before the loop, that defines the initial value
1156 of the reduction variable. */
1161 /* 1.2 set the loop-latch arg for the reduction-phi: */
1165 {
1170 }
1173 /*** 2. Create epilog code
1174 The reduction epilog code operates across the elements of the vector
1175 of partial results computed by the vectorized loop.
1176 The reduction epilog code consists of:
1177 step 1: compute the scalar result in a vector (v_out2)
1178 step 2: extract the scalar result (s_out3) from the vector (v_out2)
1179 step 3: adjust the scalar result (s_out3) if needed.
1181 Step 1 can be accomplished using one the following three schemes:
1182 (scheme 1) using reduc_code, if available.
1183 (scheme 2) using whole-vector shifts, if available.
1184 (scheme 3) using a scalar loop. In this case steps 1+2 above are
1185 combined.
1187 The overall epilog code looks like this:
1189 s_out0 = phi <s_loop> # original EXIT_PHI
1190 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
1191 v_out2 = reduce <v_out1> # step 1
1192 s_out3 = extract_field <v_out2, 0> # step 2
1193 s_out4 = adjust_result <s_out3> # step 3
1195 (step 3 is optional, and step2 1 and 2 may be combined).
1196 Lastly, the uses of s_out0 are replaced by s_out4.
1198 ***/
1200 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
1201 v_out1 = phi <v_loop> */
1208 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
1209 (i.e. when reduc_code is not available) and in the final adjustment code
1210 (if needed). Also get the original scalar reduction variable as
1211 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
1212 represents a reduction pattern), the tree-code and scalar-def are
1213 taken from the original stmt that the pattern-stmt (STMT) replaces.
1214 Otherwise (it is a regular reduction) - the tree-code and scalar-def
1215 are taken from STMT. */
1219 {
1220 /* Regular reduction */
1222 }
1223 else
1224 {
1225 /* Reduction pattern */
1229 }
1237 /* 2.3 Create the reduction code, using one of the three schemes described
1238 above. */
1241 {
1242 /*** Case 1: Create:
1243 v_out2 = reduc_expr <v_out1> */
1256 }
1257 else
1258 {
1264 tree vec_temp;
1268 else
1271 /* Regardless of whether we have a whole vector shift, if we're
1272 emulating the operation via tree-vect-generic, we don't want
1273 to use it. Only the first round of the reduction is likely
1274 to still be profitable via emulation. */
1275 /* ??? It might be better to emit a reduction tree code here, so that
1276 tree-vect-generic can expand the first round via bit tricks. */
1279 else
1280 {
1284 }
1287 {
1288 /*** Case 2: Create:
1289 for (offset = VS/2; offset >= element_size; offset/=2)
1290 {
1291 Create: va' = vec_shift <va, offset>
1292 Create: va = vop <va, va'>
1293 } */
1304 {
1308 vec_dest,
1316 vec_dest,
1322 }
1325 }
1326 else
1327 {
1328 tree rhs;
1330 /*** Case 3: Create:
1331 s = extract_field <v_out2, 0>
1332 for (offset = element_size;
1333 offset < vector_size;
1334 offset += element_size;)
1335 {
1336 Create: s' = extract_field <v_out2, offset>
1337 Create: s = op <s, s'>
1338 } */
1346 bitsize_zero_node);
1357 {
1360 bitpos);
1370 new_scalar_dest,
1375 }
1378 }
1379 }
1381 /* 2.4 Extract the final scalar result. Create:
1382 s_out3 = extract_field <v_out2, bitpos> */
1385 {
1386 tree rhs;
1395 else
1405 }
1407 /* 2.4 Adjust the final result by the initial value of the reduction
1408 variable. (When such adjustment is not needed, then
1409 'scalar_initial_def' is zero).
1411 Create:
1412 s_out4 = scalar_expr <s_out3, scalar_initial_def> */
1415 {
1417 new_scalar_dest,
1422 }
1424 /* 2.6 Replace uses of s_out0 with uses of s_out3 */
1426 /* Find the loop-closed-use at the loop exit of the original scalar result.
1427 (The reduction result is expected to have two immediate uses - one at the
1428 latch block, and one at the loop exit). */
1431 {
1433 {
1436 }
1437 }
1438 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
1440 /* Replace the uses: */
1445 }
1448 /* Function vectorizable_reduction.
1450 Check if STMT performs a reduction operation that can be vectorized.
1451 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1452 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1453 Return FALSE if not a vectorizable STMT, TRUE otherwise.
1455 This function also handles reduction idioms (patterns) that have been
1456 recognized in advance during vect_pattern_recog. In this case, STMT may be
1457 of this form:
1458 X = pattern_expr (arg0, arg1, ..., X)
1459 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
1460 sequence that had been detected and replaced by the pattern-stmt (STMT).
1462 In some cases of reduction patterns, the type of the reduction variable X is
1463 different than the type of the other arguments of STMT.
1464 In such cases, the vectype that is used when transforming STMT into a vector
1465 stmt is different than the vectype that is used to determine the
1466 vectorization factor, because it consists of a different number of elements
1467 than the actual number of elements that are being operated upon in parallel.
1469 For example, consider an accumulation of shorts into an int accumulator.
1470 On some targets it's possible to vectorize this pattern operating on 8
1471 shorts at a time (hence, the vectype for purposes of determining the
1472 vectorization factor should be V8HI); on the other hand, the vectype that
1473 is used to create the vector form is actually V4SI (the type of the result).
1475 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
1476 indicates what is the actual level of parallelism (V8HI in the example), so
1477 that the right vectorization factor would be derived. This vectype
1478 corresponds to the type of arguments to the reduction stmt, and should *NOT*
1479 be used to create the vectorized stmt. The right vectype for the vectorized
1480 stmt is obtained from the type of the result X:
1481 get_vectype_for_scalar_type (TREE_TYPE (X))
1483 This means that, contrary to "regular" reductions (or "regular" stmts in
1484 general), the following equation:
1485 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
1486 does *NOT* necessarily hold for reduction patterns. */
1488 bool
1490 {
1491 tree vec_dest;
1492 tree scalar_dest;
1493 tree op;
1499 tree operation;
1507 tree new_phi;
1508 tree scalar_type;
1510 tree orig_stmt;
1511 stmt_vec_info orig_stmt_info;
1516 stmt_vec_info prev_stmt_info;
1517 tree reduc_def;
1523 /* 1. Is vectorizable reduction? */
1525 /* Not supportable if the reduction variable is used in the loop. */
1532 /* Make sure it was already recognized as a reduction computation. */
1536 /* 2. Has this been recognized as a reduction pattern?
1538 Check if STMT represents a pattern that has been recognized
1539 in earlier analysis stages. For stmts that represent a pattern,
1540 the STMT_VINFO_RELATED_STMT field records the last stmt in
1541 the original sequence that constitutes the pattern. */
1545 {
1550 }
1552 /* 3. Check the operands of the operation. The first operands are defined
1553 inside the loop body. The last operand is the reduction variable,
1554 which is defined by the loop-header-phi. */
1566 /* All uses but the last are expected to be defined in the loop.
1567 The last use is the reduction variable. */
1569 {
1578 }
1587 else
1593 /* 4. Supportable by target? */
1595 /* 4.1. check support for the operation in the loop */
1598 {
1602 }
1605 {
1614 }
1616 /* Worthwhile without SIMD support? */
1620 {
1624 }
1626 /* 4.2. Check support for the epilog operation.
1628 If STMT represents a reduction pattern, then the type of the
1629 reduction variable may be different than the type of the rest
1630 of the arguments. For example, consider the case of accumulation
1631 of shorts into an int accumulator; The original code:
1632 S1: int_a = (int) short_a;
1633 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
1635 was replaced with:
1636 STMT: int_acc = widen_sum <short_a, int_acc>
1638 This means that:
1639 1. The tree-code that is used to create the vector operation in the
1640 epilog code (that reduces the partial results) is not the
1641 tree-code of STMT, but is rather the tree-code of the original
1642 stmt from the pattern that STMT is replacing. I.e, in the example
1643 above we want to use 'widen_sum' in the loop, but 'plus' in the
1644 epilog.
1645 2. The type (mode) we use to check available target support
1646 for the vector operation to be created in the *epilog*, is
1647 determined by the type of the reduction variable (in the example
1648 above we'd check this: plus_optab[vect_int_mode]).
1649 However the type (mode) we use to check available target support
1650 for the vector operation to be created *inside the loop*, is
1651 determined by the type of the other arguments to STMT (in the
1652 example we'd check this: widen_sum_optab[vect_short_mode]).
1654 This is contrary to "regular" reductions, in which the types of all
1655 the arguments are the same as the type of the reduction variable.
1656 For "regular" reductions we can therefore use the same vector type
1657 (and also the same tree-code) when generating the epilog code and
1658 when generating the code inside the loop. */
1661 {
1662 /* This is a reduction pattern: get the vectype from the type of the
1663 reduction variable, and get the tree-code from orig_stmt. */
1667 }
1668 else
1669 {
1670 /* Regular reduction: use the same vectype and tree-code as used for
1671 the vector code inside the loop can be used for the epilog code. */
1673 }
1679 {
1683 }
1685 {
1689 }
1692 {
1695 }
1697 /** Transform. **/
1702 /* Create the destination vector */
1705 /* Create the reduction-phi that defines the reduction-operand. */
1708 /* In case the vectorization factor (VF) is bigger than the number
1709 of elements that we can fit in a vectype (nunits), we have to generate
1710 more than one vector stmt - i.e - we need to "unroll" the
1711 vector stmt by a factor VF/nunits. For more details see documentation
1712 in vectorizable_operation. */
1716 {
1717 /* Handle uses. */
1719 {
1723 {
1726 }
1728 /* Get the vector def for the reduction variable from the phi node */
1730 }
1731 else
1732 {
1738 /* Get the vector def for the reduction variable from the vectorized
1739 reduction operation generated in the previous iteration (j-1) */
1741 }
1743 /* Arguments are ready. create the new vector stmt. */
1747 else
1749 reduc_def);
1757 else
1760 }
1762 /* Finalize the reduction-phi (set it's arguments) and create the
1763 epilog reduction code. */
1766 }
1768 /* Checks if CALL can be vectorized in type VECTYPE. Returns
1769 a function declaration if the target has a vectorized version
1770 of the function, or NULL_TREE if the function cannot be vectorized. */
1772 tree
1774 {
1778 /* We only handle functions that do not read or clobber memory -- i.e.
1779 const or novops ones. */
1790 vectype_in);
1791 }
1793 /* Function vectorizable_call.
1795 Check if STMT performs a function call that can be vectorized.
1796 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1797 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1798 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
1800 bool
1802 {
1803 tree vec_dest;
1804 tree scalar_dest;
1805 tree operation;
1813 call_expr_arg_iterator iter;
1815 /* Is STMT a vectorizable call? */
1826 /* Process function arguments. */
1830 {
1833 /* Bail out if the function has more than two arguments, we
1834 do not have interesting builtin functions to vectorize with
1835 more than two arguments. */
1839 /* We can only handle calls with arguments of the same type. */
1842 {
1846 }
1850 {
1854 }
1855 }
1857 /* No arguments is also not good. */
1866 /* Only handle the case of vectors with the same number of elements.
1867 FIXME: We need a way to handle for example the SSE2 cvtpd2dq
1868 instruction which converts V2DFmode to V4SImode but only
1869 using the lower half of the V4SImode result. */
1873 /* For now, we only vectorize functions if a target specific builtin
1874 is available. TODO -- in some cases, it might be profitable to
1875 insert the calls for pieces of the vector, in order to be able
1876 to vectorize other operations in the loop. */
1879 {
1884 }
1889 {
1892 }
1894 /** Transform. **/
1903 /* Handle def. */
1909 {
1914 /* Build argument list for the vectorized call. */
1915 /* FIXME: Rewrite this so that it doesn't construct a temporary
1916 list. */
1920 {
1925 else
1929 }
1941 else
1944 }
1946 /* The call in STMT might prevent it from being removed in dce. We however
1947 cannot remove it here, due to the way the ssa name it defines is mapped
1948 to the new definition. So just replace rhs of the statement with something
1949 harmless. */
1954 }
1957 /* Function vectorizable_conversion.
1959 Check if STMT performs a conversion operation, that can be vectorized.
1960 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1961 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1962 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
1964 bool
1967 {
1968 tree vec_dest;
1969 tree scalar_dest;
1970 tree operation;
1971 tree op0;
1976 tree new_temp;
1979 tree new_stmt;
1985 tree builtin_decl;
1986 stmt_vec_info prev_stmt_info;
1988 /* Is STMT a vectorizable conversion? */
1996 {
1997 /* FORNOW: not yet supported. */
2001 }
2014 /* Check types of lhs and rhs */
2026 /* FORNOW: need to extend to support short<->float conversions as well. */
2030 /* Bail out if the types are both integral or non-integral */
2035 /* Sanity check: make sure that at least one copy of the vectorized stmt
2036 needs to be generated. */
2041 {
2045 }
2047 /* Supportable by target? */
2049 {
2053 }
2056 {
2059 }
2061 /** Transform. **/
2066 /* Handle def. */
2071 {
2072 tree sym;
2073 ssa_op_iter iter;
2077 else
2080 builtin_decl =
2084 /* Arguments are ready. create the new vector stmt. */
2086 new_stmt);
2091 {
2095 }
2099 else
2102 }
2104 }
2107 /* Function vectorizable_assignment.
2109 Check if STMT performs an assignment (copy) that can be vectorized.
2110 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2111 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2112 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2114 bool
2116 {
2117 tree vec_dest;
2118 tree scalar_dest;
2119 tree op;
2120 tree vec_oprnd;
2124 tree new_temp;
2134 /* Is vectorizable assignment? */
2149 {
2153 }
2156 {
2159 }
2161 /** Transform. **/
2165 /* Handle def. */
2168 /* Handle use. */
2172 /* Arguments are ready. create the new vector stmt. */
2179 }
2182 /* Function vect_min_worthwhile_factor.
2184 For a loop where we could vectorize the operation indicated by CODE,
2185 return the minimum vectorization factor that makes it worthwhile
2186 to use generic vectors. */
2187 static int
2189 {
2191 {
2205 }
2206 }
2209 /* Function vectorizable_operation.
2211 Check if STMT performs a binary or unary operation that can be vectorized.
2212 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2213 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2214 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2216 bool
2218 {
2219 tree vec_dest;
2220 tree scalar_dest;
2221 tree operation;
2229 tree new_temp;
2231 optab optab;
2236 tree new_stmt;
2237 stmt_vec_info prev_stmt_info;
2240 tree vectype_out;
2246 /* Is STMT a vectorizable binary/unary operation? */
2253 {
2254 /* FORNOW: not yet supported. */
2258 }
2276 /* Support only unary or binary operations. */
2279 {
2283 }
2287 {
2291 }
2294 {
2297 {
2301 }
2302 }
2304 /* Supportable by target? */
2306 {
2310 }
2314 {
2323 }
2325 /* Worthwhile without SIMD support? */
2329 {
2333 }
2336 {
2337 /* FORNOW: not yet supported. */
2341 /* Invariant argument is needed for a vector shift
2342 by a scalar shift operand. */
2347 {
2351 }
2352 }
2355 {
2358 }
2360 /** Transform. **/
2365 /* Handle def. */
2368 /* In case the vectorization factor (VF) is bigger than the number
2369 of elements that we can fit in a vectype (nunits), we have to generate
2370 more than one vector stmt - i.e - we need to "unroll" the
2371 vector stmt by a factor VF/nunits. In doing so, we record a pointer
2372 from one copy of the vector stmt to the next, in the field
2373 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
2374 stages to find the correct vector defs to be used when vectorizing
2375 stmts that use the defs of the current stmt. The example below illustrates
2376 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
2377 4 vectorized stmts):
2379 before vectorization:
2380 RELATED_STMT VEC_STMT
2381 S1: x = memref - -
2382 S2: z = x + 1 - -
2384 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
2385 there):
2386 RELATED_STMT VEC_STMT
2387 VS1_0: vx0 = memref0 VS1_1 -
2388 VS1_1: vx1 = memref1 VS1_2 -
2389 VS1_2: vx2 = memref2 VS1_3 -
2390 VS1_3: vx3 = memref3 - -
2391 S1: x = load - VS1_0
2392 S2: z = x + 1 - -
2394 step2: vectorize stmt S2 (done here):
2395 To vectorize stmt S2 we first need to find the relevant vector
2396 def for the first operand 'x'. This is, as usual, obtained from
2397 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
2398 that defines 'x' (S1). This way we find the stmt VS1_0, and the
2399 relevant vector def 'vx0'. Having found 'vx0' we can generate
2400 the vector stmt VS2_0, and as usual, record it in the
2401 STMT_VINFO_VEC_STMT of stmt S2.
2402 When creating the second copy (VS2_1), we obtain the relevant vector
2403 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
2404 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
2405 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
2406 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
2407 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
2408 chain of stmts and pointers:
2409 RELATED_STMT VEC_STMT
2410 VS1_0: vx0 = memref0 VS1_1 -
2411 VS1_1: vx1 = memref1 VS1_2 -
2412 VS1_2: vx2 = memref2 VS1_3 -
2413 VS1_3: vx3 = memref3 - -
2414 S1: x = load - VS1_0
2415 VS2_0: vz0 = vx0 + v1 VS2_1 -
2416 VS2_1: vz1 = vx1 + v1 VS2_2 -
2417 VS2_2: vz2 = vx2 + v1 VS2_3 -
2418 VS2_3: vz3 = vx3 + v1 - -
2419 S2: z = x + 1 - VS2_0 */
2423 {
2424 /* Handle uses. */
2426 {
2429 {
2431 {
2432 /* Vector shl and shr insn patterns can be defined with
2433 scalar operand 2 (shift operand). In this case, use
2434 constant or loop invariant op1 directly, without
2435 extending it to vector mode first. */
2438 {
2442 }
2443 }
2446 }
2447 }
2448 else
2449 {
2453 }
2455 /* Arguments are ready. create the new vector stmt. */
2460 else
2469 else
2472 }
2475 }
2478 /* Function vectorizable_type_demotion
2480 Check if STMT performs a binary or unary operation that involves
2481 type demotion, and if it can be vectorized.
2482 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2483 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2484 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2486 bool
2489 {
2490 tree vec_dest;
2491 tree scalar_dest;
2492 tree operation;
2493 tree op0;
2498 tree new_temp;
2501 tree new_stmt;
2502 stmt_vec_info prev_stmt_info;
2505 tree vectype_out;
2508 tree expr;
2509 tree vectype_in;
2510 tree scalar_type;
2511 optab optab;
2514 /* Is STMT a vectorizable type-demotion operation? */
2522 {
2523 /* FORNOW: not yet supported. */
2527 }
2558 /* Check the operands of the operation. */
2560 {
2564 }
2566 /* Supportable by target? */
2579 {
2582 }
2584 /** Transform. **/
2588 ncopies);
2590 /* Handle def. */
2593 /* In case the vectorization factor (VF) is bigger than the number
2594 of elements that we can fit in a vectype (nunits), we have to generate
2595 more than one vector stmt - i.e - we need to "unroll" the
2596 vector stmt by a factor VF/nunits. */
2599 {
2600 /* Handle uses. */
2602 {
2605 }
2606 else
2607 {
2610 }
2612 /* Arguments are ready. Create the new vector stmt. */
2621 else
2625 }
2629 }
2632 /* Function vect_gen_widened_results_half
2634 Create a vector stmt whose code, type, number of arguments, and result
2635 variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are
2636 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
2637 In the case that CODE is a CALL_EXPR, this means that a call to DECL
2638 needs to be created (DECL is a function-decl of a target-builtin).
2639 STMT is the original scalar stmt that we are vectorizing. */
2641 static tree
2645 tree stmt)
2646 {
2647 tree expr;
2648 tree new_stmt;
2649 tree new_temp;
2650 tree sym;
2651 ssa_op_iter iter;
2653 /* Generate half of the widened result: */
2655 {
2656 /* Target specific support */
2659 else
2661 }
2662 else
2663 {
2664 /* Generic support */
2668 else
2670 }
2677 {
2679 {
2683 }
2684 }
2687 }
2690 /* Function vectorizable_type_promotion
2692 Check if STMT performs a binary or unary operation that involves
2693 type promotion, and if it can be vectorized.
2694 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2695 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2696 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2698 bool
2701 {
2702 tree vec_dest;
2703 tree scalar_dest;
2704 tree operation;
2714 tree new_stmt;
2715 stmt_vec_info prev_stmt_info;
2718 tree vectype_out;
2721 tree vectype_in;
2723 /* Is STMT a vectorizable type-promotion operation? */
2731 {
2732 /* FORNOW: not yet supported. */
2736 }
2765 /* Check the operands of the operation. */
2767 {
2771 }
2775 {
2778 {
2782 }
2783 }
2785 /* Supportable by target? */
2793 {
2796 }
2798 /** Transform. **/
2802 ncopies);
2804 /* Handle def. */
2807 /* In case the vectorization factor (VF) is bigger than the number
2808 of elements that we can fit in a vectype (nunits), we have to generate
2809 more than one vector stmt - i.e - we need to "unroll" the
2810 vector stmt by a factor VF/nunits. */
2814 {
2815 /* Handle uses. */
2817 {
2821 }
2822 else
2823 {
2827 }
2829 /* Arguments are ready. Create the new vector stmt. We are creating
2830 two vector defs because the widened result does not fit in one vector.
2831 The vectorized stmt can be expressed as a call to a taregt builtin,
2832 or a using a tree-code. */
2833 /* Generate first half of the widened result: */
2838 else
2842 /* Generate second half of the widened result: */
2848 }
2852 }
2855 /* Function vect_strided_store_supported.
2857 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
2858 and FALSE otherwise. */
2860 static bool
2862 {
2868 /* Check that the operation is supported. */
2870 vectype);
2872 vectype);
2874 {
2878 }
2881 == CODE_FOR_nothing
2884 {
2888 }
2890 }
2893 /* Function vect_permute_store_chain.
2895 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
2896 a power of 2, generate interleave_high/low stmts to reorder the data
2897 correctly for the stores. Return the final references for stores in
2898 RESULT_CHAIN.
2900 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
2901 The input is 4 vectors each containing 8 elements. We assign a number to each
2902 element, the input sequence is:
2904 1st vec: 0 1 2 3 4 5 6 7
2905 2nd vec: 8 9 10 11 12 13 14 15
2906 3rd vec: 16 17 18 19 20 21 22 23
2907 4th vec: 24 25 26 27 28 29 30 31
2909 The output sequence should be:
2911 1st vec: 0 8 16 24 1 9 17 25
2912 2nd vec: 2 10 18 26 3 11 19 27
2913 3rd vec: 4 12 20 28 5 13 21 30
2914 4th vec: 6 14 22 30 7 15 23 31
2916 i.e., we interleave the contents of the four vectors in their order.
2918 We use interleave_high/low instructions to create such output. The input of
2919 each interleave_high/low operation is two vectors:
2920 1st vec 2nd vec
2921 0 1 2 3 4 5 6 7
2922 the even elements of the result vector are obtained left-to-right from the
2923 high/low elements of the first vector. The odd elements of the result are
2924 obtained left-to-right from the high/low elements of the second vector.
2925 The output of interleave_high will be: 0 4 1 5
2926 and of interleave_low: 2 6 3 7
2929 The permutation is done in log LENGTH stages. In each stage interleave_high
2930 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
2931 where the first argument is taken from the first half of DR_CHAIN and the
2932 second argument from it's second half.
2933 In our example,
2935 I1: interleave_high (1st vec, 3rd vec)
2936 I2: interleave_low (1st vec, 3rd vec)
2937 I3: interleave_high (2nd vec, 4th vec)
2938 I4: interleave_low (2nd vec, 4th vec)
2940 The output for the first stage is:
2942 I1: 0 16 1 17 2 18 3 19
2943 I2: 4 20 5 21 6 22 7 23
2944 I3: 8 24 9 25 10 26 11 27
2945 I4: 12 28 13 29 14 30 15 31
2947 The output of the second stage, i.e. the final result is:
2949 I1: 0 8 16 24 1 9 17 25
2950 I2: 2 10 18 26 3 11 19 27
2951 I3: 4 12 20 28 5 13 21 30
2952 I4: 6 14 22 30 7 15 23 31. */
2954 static bool
2957 tree stmt,
2960 {
2963 tree scalar_dest;
2972 /* Check that the operation is supported. */
2979 {
2981 {
2985 /* Create interleaving stmt:
2986 in the case of big endian:
2987 high = interleave_high (vect1, vect2)
2988 and in the case of little endian:
2989 high = interleave_low (vect1, vect2). */
2997 else
3006 /* Create interleaving stmt:
3007 in the case of big endian:
3008 low = interleave_low (vect1, vect2)
3009 and in the case of little endian:
3010 low = interleave_high (vect1, vect2). */
3018 else
3026 }
3028 }
3030 }
3033 /* Function vectorizable_store.
3035 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
3036 can be vectorized.
3037 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3038 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3039 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3041 bool
3043 {
3044 tree scalar_dest;
3045 tree data_ref;
3046 tree op;
3053 tree dummy;
3055 ssa_op_iter iter;
3056 def_operand_p def_p;
3070 /* Is vectorizable store? */
3083 {
3087 }
3090 /* FORNOW. In some cases can vectorize even if data-type not supported
3091 (e.g. - array initialization with 0). */
3099 {
3103 }
3106 {
3109 }
3111 /** Transform. **/
3117 {
3124 /* We vectorize all the stmts of the interleaving group when we
3125 reach the last stmt in the group. */
3128 {
3131 }
3132 }
3133 else
3134 {
3138 }
3147 /* In case the vectorization factor (VF) is bigger than the number
3148 of elements that we can fit in a vectype (nunits), we have to generate
3149 more than one vector stmt - i.e - we need to "unroll" the
3150 vector stmt by a factor VF/nunits. For more details see documentation in
3151 vect_get_vec_def_for_copy_stmt. */
3153 /* In case of interleaving (non-unit strided access):
3155 S1: &base + 2 = x2
3156 S2: &base = x0
3157 S3: &base + 1 = x1
3158 S4: &base + 3 = x3
3160 We create vectorized stores starting from base address (the access of the
3161 first stmt in the chain (S2 in the above example), when the last store stmt
3162 of the chain (S4) is reached:
3164 VS1: &base = vx2
3165 VS2: &base + vec_size*1 = vx0
3166 VS3: &base + vec_size*2 = vx1
3167 VS4: &base + vec_size*3 = vx3
3169 Then permutation statements are generated:
3171 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
3172 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
3173 ...
3175 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3176 (the order of the data-refs in the output of vect_permute_store_chain
3177 corresponds to the order of scalar stmts in the interleaving chain - see
3178 the documentation of vect_permute_store_chain()).
3180 In case of both multiple types and interleaving, above vector stores and
3181 permutation stmts are created for every copy. The result vector stmts are
3182 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3183 STMT_VINFO_RELATED_STMT for the next copies.
3184 */
3188 {
3189 tree new_stmt;
3190 tree ptr_incr;
3193 {
3194 /* For interleaved stores we collect vectorized defs for all the
3195 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then used
3196 as an input to vect_permute_store_chain(), and OPRNDS as an input
3197 to vect_get_vec_def_for_stmt_copy() for the next copy.
3198 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3199 OPRNDS are of size 1. */
3202 {
3203 /* Since gaps are not supported for interleaved stores, GROUP_SIZE
3204 is the exact number of stmts in the chain. Therefore, NEXT_STMT
3205 can't be NULL_TREE. In case that there is no interleaving,
3206 GROUP_SIZE is 1, and only one iteration of the loop will be
3207 executed. */
3214 }
3218 }
3219 else
3220 {
3221 /* For interleaved stores we created vectorized defs for all the
3222 defs stored in OPRNDS in the previous iteration (previous copy).
3223 DR_CHAIN is then used as an input to vect_permute_store_chain(),
3224 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
3225 next copy.
3226 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3227 OPRNDS are of size 1. */
3229 {
3234 }
3236 }
3239 {
3241 /* Permute. */
3245 }
3249 {
3250 /* For strided stores vectorized defs are interleaved in
3251 vect_permute_store_chain(). */
3256 /* Arguments are ready. Create the new vector stmt. */
3258 vec_oprnd);
3261 /* Set the VDEFs for the vector pointer. If this virtual def
3262 has a use outside the loop and a loop peel is performed
3263 then the def may be renamed by the peel. Mark it for
3264 renaming so the later use will also be renamed. */
3267 {
3268 /* The original store is deleted so the same SSA_NAMEs
3269 can be used. */
3271 {
3274 }
3277 }
3278 else
3279 {
3280 /* Create new names for all the definitions created by COPY and
3281 add replacement mappings for each new name. */
3283 {
3286 }
3289 }
3295 /* Bump the vector pointer. */
3297 }
3298 }
3301 }
3304 /* Function vect_setup_realignment
3306 This function is called when vectorizing an unaligned load using
3307 the dr_unaligned_software_pipeline scheme.
3308 This function generates the following code at the loop prolog:
3310 p = initial_addr;
3311 msq_init = *(floor(p)); # prolog load
3312 realignment_token = call target_builtin;
3313 loop:
3314 msq = phi (msq_init, ---)
3316 The code above sets up a new (vector) pointer, pointing to the first
3317 location accessed by STMT, and a "floor-aligned" load using that pointer.
3318 It also generates code to compute the "realignment-token" (if the relevant
3319 target hook was defined), and creates a phi-node at the loop-header bb
3320 whose arguments are the result of the prolog-load (created by this
3321 function) and the result of a load that takes place in the loop (to be
3322 created by the caller to this function).
3323 The caller to this function uses the phi-result (msq) to create the
3324 realignment code inside the loop, and sets up the missing phi argument,
3325 as follows:
3327 loop:
3328 msq = phi (msq_init, lsq)
3329 lsq = *(floor(p')); # load in loop
3330 result = realign_load (msq, lsq, realignment_token);
3332 Input:
3333 STMT - (scalar) load stmt to be vectorized. This load accesses
3334 a memory location that may be unaligned.
3335 BSI - place where new code is to be inserted.
3337 Output:
3338 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
3339 target hook, if defined.
3340 Return value - the result of the loop-header phi node. */
3342 static tree
3345 {
3352 tree vec_dest;
3353 tree init_addr;
3354 tree inc;
3355 tree ptr;
3356 tree data_ref;
3357 tree new_stmt;
3358 basic_block new_bb;
3359 tree msq_init;
3360 tree new_temp;
3361 tree phi_stmt;
3362 tree msq;
3364 /* 1. Create msq_init = *(floor(p1)) in the loop preheader */
3367 NULL_TREE);
3378 /* 2. Create permutation mask, if required, in loop preheader. */
3380 {
3381 tree builtin_decl;
3388 new_stmt);
3395 /* The result of the CALL_EXPR to this builtin is determined from
3396 the value of the parameter and no global variables are touched
3397 which makes the builtin a "const" function. Requiring the
3398 builtin to have the "const" attribute makes it unnecessary
3399 to call mark_call_clobbered. */
3401 }
3403 /* 3. Create msq = phi <msq_init, lsq> in loop */
3411 }
3414 /* Function vect_strided_load_supported.
3416 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
3417 and FALSE otherwise. */
3419 static bool
3421 {
3429 {
3433 }
3436 {
3440 }
3444 {
3448 }
3451 {
3455 }
3457 }
3460 /* Function vect_permute_load_chain.
3462 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
3463 a power of 2, generate extract_even/odd stmts to reorder the input data
3464 correctly. Return the final references for loads in RESULT_CHAIN.
3466 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
3467 The input is 4 vectors each containing 8 elements. We assign a number to each
3468 element, the input sequence is:
3470 1st vec: 0 1 2 3 4 5 6 7
3471 2nd vec: 8 9 10 11 12 13 14 15
3472 3rd vec: 16 17 18 19 20 21 22 23
3473 4th vec: 24 25 26 27 28 29 30 31
3475 The output sequence should be:
3477 1st vec: 0 4 8 12 16 20 24 28
3478 2nd vec: 1 5 9 13 17 21 25 29
3479 3rd vec: 2 6 10 14 18 22 26 30
3480 4th vec: 3 7 11 15 19 23 27 31
3482 i.e., the first output vector should contain the first elements of each
3483 interleaving group, etc.
3485 We use extract_even/odd instructions to create such output. The input of each
3486 extract_even/odd operation is two vectors
3487 1st vec 2nd vec
3488 0 1 2 3 4 5 6 7
3490 and the output is the vector of extracted even/odd elements. The output of
3491 extract_even will be: 0 2 4 6
3492 and of extract_odd: 1 3 5 7
3495 The permutation is done in log LENGTH stages. In each stage extract_even and
3496 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
3497 order. In our example,
3499 E1: extract_even (1st vec, 2nd vec)
3500 E2: extract_odd (1st vec, 2nd vec)
3501 E3: extract_even (3rd vec, 4th vec)
3502 E4: extract_odd (3rd vec, 4th vec)
3504 The output for the first stage will be:
3506 E1: 0 2 4 6 8 10 12 14
3507 E2: 1 3 5 7 9 11 13 15
3508 E3: 16 18 20 22 24 26 28 30
3509 E4: 17 19 21 23 25 27 29 31
3511 In order to proceed and create the correct sequence for the next stage (or
3512 for the correct output, if the second stage is the last one, as in our
3513 example), we first put the output of extract_even operation and then the
3514 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
3515 The input for the second stage is:
3517 1st vec (E1): 0 2 4 6 8 10 12 14
3518 2nd vec (E3): 16 18 20 22 24 26 28 30
3519 3rd vec (E2): 1 3 5 7 9 11 13 15
3520 4th vec (E4): 17 19 21 23 25 27 29 31
3522 The output of the second stage:
3524 E1: 0 4 8 12 16 20 24 28
3525 E2: 2 6 10 14 18 22 26 30
3526 E3: 1 5 9 13 17 21 25 29
3527 E4: 3 7 11 15 19 23 27 31
3529 And RESULT_CHAIN after reordering:
3531 1st vec (E1): 0 4 8 12 16 20 24 28
3532 2nd vec (E3): 1 5 9 13 17 21 25 29
3533 3rd vec (E2): 2 6 10 14 18 22 26 30
3534 4th vec (E4): 3 7 11 15 19 23 27 31. */
3536 static bool
3539 tree stmt,
3542 {
3548 /* Check that the operation is supported. */
3554 {
3556 {
3560 /* data_ref = permute_even (first_data_ref, second_data_ref); */
3576 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
3590 }
3592 }
3594 }
3597 /* Function vect_transform_strided_load.
3599 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
3600 to perform their permutation and ascribe the result vectorized statements to
3601 the scalar statements.
3602 */
3604 static bool
3607 {
3613 tree tmp_data_ref;
3615 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
3616 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
3617 vectors, that are ready for vector computation. */
3619 /* Permute. */
3623 /* Put a permuted data-ref in the VECTORIZED_STMT field.
3624 Since we scan the chain starting from it's first node, their order
3625 corresponds the order of data-refs in RESULT_CHAIN. */
3629 {
3633 /* Skip the gaps. Loads created for the gaps will be removed by dead
3634 code elimination pass later.
3635 DR_GROUP_GAP is the number of steps in elements from the previous
3636 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
3637 correspond to the gaps.
3638 */
3640 {
3641 gap_count++;
3643 }
3646 {
3648 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
3649 copies, and we put the new vector statement in the first available
3650 RELATED_STMT. */
3653 else
3654 {
3659 {
3662 }
3664 }
3667 /* If NEXT_STMT accesses the same DR as the previous statement,
3668 put the same TMP_DATA_REF as its vectorized statement; otherwise
3669 get the next data-ref from RESULT_CHAIN. */
3672 }
3673 }
3675 }
3678 /* vectorizable_load.
3680 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
3681 can be vectorized.
3682 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3683 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3684 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3686 bool
3688 {
3689 tree scalar_dest;
3692 tree op;
3694 stmt_vec_info prev_stmt_info;
3699 tree new_temp;
3702 tree dummy;
3705 tree ptr_incr;
3715 tree first_stmt;
3717 /* Is vectorizable load? */
3724 {
3725 /* FORNOW: not yet supported. */
3729 }
3749 /* FORNOW. In some cases can vectorize even if data-type not supported
3750 (e.g. - data copies). */
3752 {
3756 }
3758 /* Check if the load is a part of an interleaving chain. */
3760 {
3763 /* Check if interleaving is supported. */
3766 }
3769 {
3772 }
3774 /** Transform. **/
3780 {
3782 /* Check if the chain of loads is already vectorized. */
3784 {
3787 }
3791 }
3792 else
3793 {
3797 }
3803 /* In case the vectorization factor (VF) is bigger than the number
3804 of elements that we can fit in a vectype (nunits), we have to generate
3805 more than one vector stmt - i.e - we need to "unroll" the
3806 vector stmt by a factor VF/nunits. In doing so, we record a pointer
3807 from one copy of the vector stmt to the next, in the field
3808 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3809 stages to find the correct vector defs to be used when vectorizing
3810 stmts that use the defs of the current stmt. The example below illustrates
3811 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3812 4 vectorized stmts):
3814 before vectorization:
3815 RELATED_STMT VEC_STMT
3816 S1: x = memref - -
3817 S2: z = x + 1 - -
3819 step 1: vectorize stmt S1:
3820 We first create the vector stmt VS1_0, and, as usual, record a
3821 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
3822 Next, we create the vector stmt VS1_1, and record a pointer to
3823 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
3824 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
3825 stmts and pointers:
3826 RELATED_STMT VEC_STMT
3827 VS1_0: vx0 = memref0 VS1_1 -
3828 VS1_1: vx1 = memref1 VS1_2 -
3829 VS1_2: vx2 = memref2 VS1_3 -
3830 VS1_3: vx3 = memref3 - -
3831 S1: x = load - VS1_0
3832 S2: z = x + 1 - -
3834 See in documentation in vect_get_vec_def_for_stmt_copy for how the
3835 information we recorded in RELATED_STMT field is used to vectorize
3836 stmt S2. */
3838 /* In case of interleaving (non-unit strided access):
3840 S1: x2 = &base + 2
3841 S2: x0 = &base
3842 S3: x1 = &base + 1
3843 S4: x3 = &base + 3
3845 Vectorized loads are created in the order of memory accesses
3846 starting from the access of the first stmt of the chain:
3848 VS1: vx0 = &base
3849 VS2: vx1 = &base + vec_size*1
3850 VS3: vx3 = &base + vec_size*2
3851 VS4: vx4 = &base + vec_size*3
3853 Then permutation statements are generated:
3855 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
3856 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
3857 ...
3859 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3860 (the order of the data-refs in the output of vect_permute_load_chain
3861 corresponds to the order of scalar stmts in the interleaving chain - see
3862 the documentation of vect_permute_load_chain()).
3863 The generation of permutation stmts and recording them in
3864 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
3866 In case of both multiple types and interleaving, the vector loads and
3867 permutation stmts above are created for every copy. The result vector stmts
3868 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3869 STMT_VINFO_RELATED_STMT for the next copies. */
3871 /* If the data reference is aligned (dr_aligned) or potentially unaligned
3872 on a target that supports unaligned accesses (dr_unaligned_supported)
3873 we generate the following code:
3874 p = initial_addr;
3875 indx = 0;
3876 loop {
3877 p = p + indx * vectype_size;
3878 vec_dest = *(p);
3879 indx = indx + 1;
3880 }
3882 Otherwise, the data reference is potentially unaligned on a target that
3883 does not support unaligned accesses (dr_unaligned_software_pipeline) -
3884 then generate the following code, in which the data in each iteration is
3885 obtained by two vector loads, one from the previous iteration, and one
3886 from the current iteration:
3887 p1 = initial_addr;
3888 msq_init = *(floor(p1))
3889 p2 = initial_addr + VS - 1;
3890 realignment_token = call target_builtin;
3891 indx = 0;
3892 loop {
3893 p2 = p2 + indx * vectype_size
3894 lsq = *(floor(p2))
3895 vec_dest = realign_load (msq, lsq, realignment_token)
3896 indx = indx + 1;
3897 msq = lsq;
3898 } */
3901 {
3905 }
3909 {
3910 /* 1. Create the vector pointer update chain. */
3914 else
3918 {
3919 /* 2. Create the vector-load in the loop. */
3921 {
3927 {
3933 data_ref =
3936 }
3943 }
3946 data_ref);
3953 /* 3. Handle explicit realignment if necessary/supported. */
3955 {
3956 /* Create in loop:
3957 <vec_dest = realign_load (msq, lsq, realignment_token)> */
3962 new_stmt =
3965 new_stmt);
3972 }
3977 }
3980 {
3985 }
3986 else
3987 {
3990 else
3993 }
3994 }
3997 }
4000 /* Function vectorizable_live_operation.
4002 STMT computes a value that is used outside the loop. Check if
4003 it can be supported. */
4005 bool
4009 {
4010 tree operation;
4015 tree op;
4031 /* FORNOW: support only if all uses are invariant. This means
4032 that the scalar operations can remain in place, unvectorized.
4033 The original last scalar value that they compute will be used. */
4036 {
4039 {
4043 }
4047 }
4049 /* No transformation is required for the cases we currently support. */
4051 }
4054 /* Function vect_is_simple_cond.
4056 Input:
4057 LOOP - the loop that is being vectorized.
4058 COND - Condition that is checked for simple use.
4060 Returns whether a COND can be vectorized. Checks whether
4061 condition operands are supportable using vec_is_simple_use. */
4063 static bool
4065 {
4067 tree def;
4077 {
4081 }
4086 {
4090 }
4095 }
4097 /* vectorizable_condition.
4099 Check if STMT is conditional modify expression that can be vectorized.
4100 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4101 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
4102 at BSI.
4104 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4106 bool
4108 {
4117 tree new_temp;
4120 tree def;
4135 {
4136 /* FORNOW: not yet supported. */
4140 }
4157 /* We do not handle two different vector types for the condition
4158 and the values. */
4163 {
4168 }
4174 {
4179 }
4188 {
4191 }
4193 /* Transform */
4195 /* Handle def. */
4199 /* Handle cond expr. */
4200 vec_cond_lhs =
4202 vec_cond_rhs =
4207 /* Arguments are ready. create the new vector stmt. */
4214 vec_cond_expr);
4220 }
4222 /* Function vect_transform_stmt.
4224 Create a vectorized stmt to replace STMT, and insert it at BSI. */
4226 bool
4228 {
4232 tree orig_stmt_in_pattern;
4236 {
4238 {
4273 {
4274 /* In case of interleaving, the whole chain is vectorized when the
4275 last store in the chain is reached. Store stmts before the last
4276 one are skipped, and there vec_stmt_info shouldn't be freed
4277 meanwhile. */
4281 }
4282 else
4299 }
4303 {
4307 {
4310 {
4313 /* STMT was inserted by the vectorizer to replace a
4314 computation idiom. ORIG_STMT_IN_PATTERN is a stmt in the
4315 original sequence that computed this idiom. We need to
4316 record a pointer to VEC_STMT in the stmt_info of
4317 ORIG_STMT_IN_PATTERN. See more details in the
4318 documentation of vect_pattern_recog. */
4321 }
4322 }
4323 }
4324 }
4327 {
4329 {
4338 }
4339 }
4342 }
4345 /* This function builds ni_name = number of iterations loop executes
4346 on the loop preheader. */
4348 static tree
4350 {
4352 edge pe;
4362 {
4365 }
4368 }
4371 /* This function generates the following statements:
4373 ni_name = number of iterations loop executes
4374 ratio = ni_name / vf
4375 ratio_mult_vf_name = ratio * vf
4377 and places them at the loop preheader edge. */
4379 static void
4384 {
4386 edge pe;
4387 basic_block new_bb;
4389 tree var;
4390 tree ratio_name;
4391 tree ratio_mult_vf_name;
4395 tree log_vf;
4399 /* Generate temporary variable that contains
4400 number of iterations loop executes. */
4405 /* Create: ratio = ni >> log2(vf) */
4409 {
4417 }
4419 /* Create: ratio_mult_vf = ratio << log2 (vf). */
4424 {
4433 }
4440 }
4443 /* Function update_vuses_to_preheader.
4445 Input:
4446 STMT - a statement with potential VUSEs.
4447 LOOP - the loop whose preheader will contain STMT.
4449 It's possible to vectorize a loop even though an SSA_NAME from a VUSE
4450 appears to be defined in a VDEF in another statement in a loop.
4451 One such case is when the VUSE is at the dereference of a __restricted__
4452 pointer in a load and the VDEF is at the dereference of a different
4453 __restricted__ pointer in a store. Vectorization may result in
4454 copy_virtual_uses being called to copy the problematic VUSE to a new
4455 statement that is being inserted in the loop preheader. This procedure
4456 is called to change the SSA_NAME in the new statement's VUSE from the
4457 SSA_NAME updated in the loop to the related SSA_NAME available on the
4458 path entering the loop.
4460 When this function is called, we have the following situation:
4462 # vuse <name1>
4463 S1: vload
4464 do {
4465 # name1 = phi < name0 , name2>
4467 # vuse <name1>
4468 S2: vload
4470 # name2 = vdef <name1>
4471 S3: vstore
4473 }while...
4475 Stmt S1 was created in the loop preheader block as part of misaligned-load
4476 handling. This function fixes the name of the vuse of S1 from 'name1' to
4477 'name0'. */
4479 static void
4481 {
4484 ssa_op_iter iter;
4485 use_operand_p use_p;
4488 {
4494 /* For a use before any definitions, def_stmt is a NOP_EXPR. */
4497 {
4498 /* If the block containing the statement defining the SSA_NAME
4499 is in the loop then it's necessary to find the definition
4500 outside the loop using the PHI nodes of the header. */
4501 tree phi;
4505 {
4507 {
4511 }
4512 }
4514 }
4515 }
4516 }
4519 /* Function vect_update_ivs_after_vectorizer.
4521 "Advance" the induction variables of LOOP to the value they should take
4522 after the execution of LOOP. This is currently necessary because the
4523 vectorizer does not handle induction variables that are used after the
4524 loop. Such a situation occurs when the last iterations of LOOP are
4525 peeled, because:
4526 1. We introduced new uses after LOOP for IVs that were not originally used
4527 after LOOP: the IVs of LOOP are now used by an epilog loop.
4528 2. LOOP is going to be vectorized; this means that it will iterate N/VF
4529 times, whereas the loop IVs should be bumped N times.
4531 Input:
4532 - LOOP - a loop that is going to be vectorized. The last few iterations
4533 of LOOP were peeled.
4534 - NITERS - the number of iterations that LOOP executes (before it is
4535 vectorized). i.e, the number of times the ivs should be bumped.
4536 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
4537 coming out from LOOP on which there are uses of the LOOP ivs
4538 (this is the path from LOOP->exit to epilog_loop->preheader).
4540 The new definitions of the ivs are placed in LOOP->exit.
4541 The phi args associated with the edge UPDATE_E in the bb
4542 UPDATE_E->dest are updated accordingly.
4544 Assumption 1: Like the rest of the vectorizer, this function assumes
4545 a single loop exit that has a single predecessor.
4547 Assumption 2: The phi nodes in the LOOP header and in update_bb are
4548 organized in the same order.
4550 Assumption 3: The access function of the ivs is simple enough (see
4551 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
4553 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
4554 coming out of LOOP on which the ivs of LOOP are used (this is the path
4555 that leads to the epilog loop; other paths skip the epilog loop). This
4556 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
4557 needs to have its phis updated.
4558 */
4560 static void
4562 edge update_e)
4563 {
4569 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
4571 /* Make sure there exists a single-predecessor exit bb: */
4577 {
4579 tree evolution_part;
4580 tree init_expr;
4581 tree step_expr;
4583 block_stmt_iterator last_bsi;
4586 {
4589 }
4591 /* Skip virtual phi's. */
4593 {
4597 }
4599 /* Skip reduction phis. */
4601 {
4605 }
4609 evolution_part =
4613 /* FORNOW: We do not support IVs whose evolution function is a polynomial
4614 of degree >= 2 or exponential. */
4624 niters),
4625 step_expr),
4626 init_expr);
4633 /* Insert stmt into exit_bb. */
4638 /* Fix phi expressions in the successor bb. */
4640 }
4641 }
4644 /* Function vect_do_peeling_for_loop_bound
4646 Peel the last iterations of the loop represented by LOOP_VINFO.
4647 The peeled iterations form a new epilog loop. Given that the loop now
4648 iterates NITERS times, the new epilog loop iterates
4649 NITERS % VECTORIZATION_FACTOR times.
4651 The original loop will later be made to iterate
4652 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
4654 static void
4656 {
4660 edge update_e;
4661 basic_block preheader;
4670 /* Generate the following variables on the preheader of original loop:
4672 ni_name = number of iteration the original loop executes
4673 ratio = ni_name / vf
4674 ratio_mult_vf_name = ratio * vf */
4679 /* Threshold for vectorized loop. */
4686 #ifdef ENABLE_CHECKING
4688 #endif
4690 /* A guard that controls whether the new_loop is to be executed or skipped
4691 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
4692 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
4693 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
4694 is on the path where the LOOP IVs are used and need to be updated. */
4699 else
4702 /* Update IVs of original loop as if they were advanced
4703 by ratio_mult_vf_name steps. */
4706 /* After peeling we have to reset scalar evolution analyzer. */
4710 }
4713 /* Function vect_gen_niters_for_prolog_loop
4715 Set the number of iterations for the loop represented by LOOP_VINFO
4716 to the minimum between LOOP_NITERS (the original iteration count of the loop)
4717 and the misalignment of DR - the data reference recorded in
4718 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
4719 this loop, the data reference DR will refer to an aligned location.
4721 The following computation is generated:
4723 If the misalignment of DR is known at compile time:
4724 addr_mis = int mis = DR_MISALIGNMENT (dr);
4725 Else, compute address misalignment in bytes:
4726 addr_mis = addr & (vectype_size - 1)
4728 prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
4730 (elem_size = element type size; an element is the scalar element
4731 whose type is the inner type of the vectype)
4733 For interleaving,
4735 prolog_niters = min ( LOOP_NITERS ,
4736 (VF/group_size - addr_mis/elem_size)&(VF/group_size-1) )
4737 where group_size is the size of the interleaved group.
4738 */
4740 static tree
4742 {
4748 edge pe;
4749 basic_block new_bb;
4759 {
4760 /* For interleaved access element size must be multiplied by the size of
4761 the interleaved group. */
4765 }
4770 {
4778 }
4779 else
4780 {
4782 tree start_addr =
4788 tree elem_size_log =
4792 tree byte_misalign;
4793 tree elem_misalign;
4798 /* Create: byte_misalign = addr & (vectype_size - 1) */
4799 byte_misalign =
4802 /* Create: elem_misalign = byte_misalign / element_size */
4803 elem_misalign =
4806 /* Create: (niters_type) (VF - elem_misalign)&(VF - 1) */
4810 }
4812 /* Create: prolog_loop_niters = min (iters, loop_niters) */
4813 /* If the loop bound is known at compile time we already verified that it is
4814 greater than vf; since the misalignment ('iters') is at most vf, there's
4815 no need to generate the MIN_EXPR in this case. */
4820 {
4823 }
4829 /* Insert stmt on loop preheader edge. */
4831 {
4834 }
4837 }
4840 /* Function vect_update_init_of_dr
4842 NITERS iterations were peeled from LOOP. DR represents a data reference
4843 in LOOP. This function updates the information recorded in DR to
4844 account for the fact that the first NITERS iterations had already been
4845 executed. Specifically, it updates the OFFSET field of DR. */
4847 static void
4849 {
4855 }
4858 /* Function vect_update_inits_of_drs
4860 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
4861 This function updates the information recorded for the data references in
4862 the loop to account for the fact that the first NITERS iterations had
4863 already been executed. Specifically, it updates the initial_condition of the
4864 access_function of all the data_references in the loop. */
4866 static void
4868 {
4878 }
4881 /* Function vect_do_peeling_for_alignment
4883 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
4884 'niters' is set to the misalignment of one of the data references in the
4885 loop, thereby forcing it to refer to an aligned location at the beginning
4886 of the execution of this loop. The data reference for which we are
4887 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
4889 static void
4891 {
4894 tree n_iters;
4905 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
4906 new_loop =
4910 #ifdef ENABLE_CHECKING
4912 #endif
4914 /* Update number of times loop executes. */
4919 /* Update the init conditions of the access functions of all data refs. */
4922 /* After peeling we have to reset scalar evolution analyzer. */
4926 }
4929 /* Function vect_create_cond_for_align_checks.
4931 Create a conditional expression that represents the alignment checks for
4932 all of data references (array element references) whose alignment must be
4933 checked at runtime.
4935 Input:
4936 LOOP_VINFO - two fields of the loop information are used.
4937 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
4938 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
4940 Output:
4941 COND_EXPR_STMT_LIST - statements needed to construct the conditional
4942 expression.
4943 The returned value is the conditional expression to be used in the if
4944 statement that controls which version of the loop gets executed at runtime.
4946 The algorithm makes two assumptions:
4947 1) The number of bytes "n" in a vector is a power of 2.
4948 2) An address "a" is aligned if a%n is zero and that this
4949 test can be done as a&(n-1) == 0. For example, for 16
4950 byte vectors the test is a&0xf == 0. */
4952 static tree
4955 {
4958 tree ref_stmt;
4960 tree mask_cst;
4962 tree psize;
4963 tree int_ptrsize_type;
4967 tree ptrsize_zero;
4969 /* Check that mask is one less than a power of 2, i.e., mask is
4970 all zeros followed by all ones. */
4973 /* CHECKME: what is the best integer or unsigned type to use to hold a
4974 cast from a pointer value? */
4976 int_ptrsize_type
4979 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
4980 of the first vector of the i'th data reference. */
4983 {
4985 tree addr_base;
4989 /* create: addr_tmp = (int)(address_of_first_vector) */
4992 NULL_TREE);
5007 /* The addresses are OR together. */
5010 {
5011 /* create: or_tmp = or_tmp | addr_tmp */
5017 new_or_tmp_name,
5019 or_tmp_name,
5020 addr_tmp_name));
5024 }
5025 else
5032 /* create: and_tmp = or_tmp & mask */
5038 and_tmp_name,
5044 /* Make and_tmp the left operand of the conditional test against zero.
5045 if and_tmp has a nonzero bit then some address is unaligned. */
5049 }
5052 /* Function vect_transform_loop.
5054 The analysis phase has determined that the loop is vectorizable.
5055 Vectorize the loop - created vectorized stmts to replace the scalar
5056 stmts in the loop, and update the loop exit condition. */
5058 void
5060 {
5064 block_stmt_iterator si;
5073 /* If the loop has data references that may or may not be aligned then
5074 two versions of the loop need to be generated, one which is vectorized
5075 and one which isn't. A test is then generated to control which of the
5076 loops is executed. The test checks for the alignment of all of the
5077 data references that may or may not be aligned. */
5080 {
5082 tree cond_expr;
5084 basic_block condition_bb;
5085 block_stmt_iterator cond_exp_bsi;
5086 basic_block merge_bb;
5087 basic_block new_exit_bb;
5099 /** Loop versioning violates an assumption we try to maintain during
5100 vectorization - that the loop exit block has a single predecessor.
5101 After versioning, the exit block of both loop versions is the same
5102 basic block (i.e. it has two predecessors). Just in order to simplify
5103 following transformations in the vectorizer, we fix this situation
5104 here by adding a new (empty) block on the exit-edge of the loop,
5105 with the proper loop-exit phis to maintain loop-closed-form. **/
5115 {
5117 new_exit_bb);
5121 }
5123 /** end loop-exit-fixes after versioning **/
5128 }
5130 /* CHECKME: we wouldn't need this if we called update_ssa once
5131 for all loops. */
5134 /* Peel the loop if there are data refs with unknown alignment.
5135 Only one data ref with unknown store is allowed. */
5140 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5141 compile time constant), or it is a constant that doesn't divide by the
5142 vectorization factor, then an epilog loop needs to be created.
5143 We therefore duplicate the loop: the original loop will be vectorized,
5144 and will compute the first (n/VF) iterations. The second copy of the loop
5145 will remain scalar and will compute the remaining (n%VF) iterations.
5146 (VF is the vectorization factor). */
5152 else
5156 /* 1) Make sure the loop header has exactly two entries
5157 2) Make sure we have a preheader basic block. */
5163 /* FORNOW: the vectorizer supports only loops which body consist
5164 of one basic block (header + empty latch). When the vectorizer will
5165 support more involved loop forms, the order by which the BBs are
5166 traversed need to be reconsidered. */
5169 {
5173 {
5175 stmt_vec_info stmt_info;
5179 {
5182 }
5187 {
5190 }
5197 /* -------- vectorize statement ------------ */
5204 {
5205 stmt_ann_t ann;
5207 {
5208 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
5209 interleaving chain was completed - free all the stores in
5210 the chain. */
5212 tree tmp;
5213 stmt_vec_info next_stmt_info;
5216 {
5218 /* Free the attached stmt_vec_info and remove the stmt. */
5224 }
5227 }
5228 else
5229 {
5230 /* Free the attached stmt_vec_info and remove the stmt. */
5236 }
5237 }
5238 else
5239 {
5241 {
5242 /* This is case of skipped interleaved store. We don't free
5243 its stmt_vec_info. */
5246 }
5247 }
5256 /* The memory tags and pointers in vectorized statements need to
5257 have their SSA forms updated. FIXME, why can't this be delayed
5258 until all the loops have been transformed? */
5263 }