| blob | 161e82d3314da6ecb9e59bfa9650a735b50074f1 |
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 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;
426 /* Update the vector-pointer's cross-iteration increment. */
428 {
433 else
435 }
437 /* Copy the points-to information if it exists. */
443 }
446 /* Function vect_create_destination_var.
448 Create a new temporary of type VECTYPE. */
450 static tree
452 {
453 tree vec_dest;
455 tree type;
470 }
473 /* Function vect_init_vector.
475 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
476 the vector elements of VECTOR_VAR. Return the DEF of INIT_STMT. It will be
477 used in the vectorization of STMT. */
479 static tree
481 {
485 tree new_var;
486 tree init_stmt;
487 tree vec_oprnd;
488 edge pe;
489 tree new_temp;
490 basic_block new_bb;
504 {
507 }
511 }
514 /* Function get_initial_def_for_induction
516 Input:
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;
550 tree stmts;
552 block_stmt_iterator si;
558 /* Find the first insertion point in the BB. */
568 /* Create the vector that holds the initial_value of the induction. */
574 {
577 }
582 {
583 tree tmp;
585 /* Create: new_name = new_name + step_expr */
595 {
598 }
600 }
605 /* Create the vector that holds the step of the induction. */
615 /* Create the following def-use cycle:
616 loop prolog:
617 vec_init = [X, X+S, X+2*S, X+3*S]
618 vec_step = [VF*S, VF*S, VF*S, VF*S]
619 loop:
620 vec_iv = PHI <vec_init, vec_loop>
621 ...
622 STMT
623 ...
624 vec_loop = vec_iv + vec_step; */
626 /* Create the induction-phi that defines the induction-operand. */
634 /* Create the iv update inside the loop */
643 /* Set the arguments of the phi node: */
648 /* In case the vectorization factor (VF) is bigger than the number
649 of elements that we can fit in a vectype (nunits), we have to generate
650 more than one vector stmt - i.e - we need to "unroll" the
651 vector stmt by a factor VF/nunits. For more details see documentation
652 in vectorizable_operation. */
655 {
656 stmt_vec_info prev_stmt_vinfo;
658 /* Create the vector that holds the step of the induction. */
670 {
671 tree tmp;
673 /* vec_i = vec_prev + vec_{step*nunits} */
683 }
684 }
687 {
692 }
696 }
699 /* Function vect_get_vec_def_for_operand.
701 OP is an operand in STMT. This function returns a (vector) def that will be
702 used in the vectorized stmt for STMT.
704 In the case that OP is an SSA_NAME which is defined in the loop, then
705 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
707 In case OP is an invariant or constant, a new stmt that creates a vector def
708 needs to be introduced. */
710 static tree
712 {
713 tree vec_oprnd;
714 tree vec_stmt;
715 tree def_stmt;
722 tree vec_inv;
723 tree vec_cst;
725 tree def;
729 tree vector_type;
732 {
735 }
740 {
742 {
745 }
747 {
750 }
751 }
754 {
755 /* Case 1: operand is a constant. */
757 {
761 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
766 {
768 }
773 }
775 /* Case 2: operand is defined outside the loop - loop invariant. */
777 {
781 /* Create 'vec_inv = {inv,inv,..,inv}' */
786 {
788 }
790 /* FIXME: use build_constructor directly. */
794 }
796 /* Case 3: operand is defined inside the loop. */
798 {
802 /* Get the def from the vectorized stmt. */
808 }
810 /* Case 4: operand is defined by a loop header phi - reduction */
812 {
815 /* Get the def before the loop */
818 }
820 /* Case 5: operand is defined by loop-header phi - induction. */
822 {
825 /* Get the def before the loop */
827 }
831 }
832 }
835 /* Function vect_get_vec_def_for_stmt_copy
837 Return a vector-def for an operand. This function is used when the
838 vectorized stmt to be created (by the caller to this function) is a "copy"
839 created in case the vectorized result cannot fit in one vector, and several
840 copies of the vector-stmt are required. In this case the vector-def is
841 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
842 of the stmt that defines VEC_OPRND.
843 DT is the type of the vector def VEC_OPRND.
845 Context:
846 In case the vectorization factor (VF) is bigger than the number
847 of elements that can fit in a vectype (nunits), we have to generate
848 more than one vector stmt to vectorize the scalar stmt. This situation
849 arises when there are multiple data-types operated upon in the loop; the
850 smallest data-type determines the VF, and as a result, when vectorizing
851 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
852 vector stmt (each computing a vector of 'nunits' results, and together
853 computing 'VF' results in each iteration). This function is called when
854 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
855 which VF=16 and nunits=4, so the number of copies required is 4):
857 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
859 S1: x = load VS1.0: vx.0 = memref0 VS1.1
860 VS1.1: vx.1 = memref1 VS1.2
861 VS1.2: vx.2 = memref2 VS1.3
862 VS1.3: vx.3 = memref3
864 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
865 VSnew.1: vz1 = vx.1 + ... VSnew.2
866 VSnew.2: vz2 = vx.2 + ... VSnew.3
867 VSnew.3: vz3 = vx.3 + ...
869 The vectorization of S1 is explained in vectorizable_load.
870 The vectorization of S2:
871 To create the first vector-stmt out of the 4 copies - VSnew.0 -
872 the function 'vect_get_vec_def_for_operand' is called to
873 get the relevant vector-def for each operand of S2. For operand x it
874 returns the vector-def 'vx.0'.
876 To create the remaining copies of the vector-stmt (VSnew.j), this
877 function is called to get the relevant vector-def for each operand. It is
878 obtained from the respective VS1.j stmt, which is recorded in the
879 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
881 For example, to obtain the vector-def 'vx.1' in order to create the
882 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
883 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
884 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
885 and return its def ('vx.1').
886 Overall, to create the above sequence this function will be called 3 times:
887 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
888 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
889 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
891 static tree
893 {
894 tree vec_stmt_for_operand;
895 stmt_vec_info def_stmt_info;
897 /* Do nothing; can reuse same def. */
909 }
912 /* Function vect_finish_stmt_generation.
914 Insert a new stmt. */
916 static void
919 {
928 {
931 }
933 /* Make sure bsi points to the stmt that is being vectorized. */
936 #ifdef USE_MAPPED_LOCATION
938 #else
940 #endif
941 }
944 /* Function get_initial_def_for_reduction
946 Input:
947 STMT - a stmt that performs a reduction operation in the loop.
948 INIT_VAL - the initial value of the reduction variable
950 Output:
951 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
952 of the reduction (used for adjusting the epilog - see below).
953 Return a vector variable, initialized according to the operation that STMT
954 performs. This vector will be used as the initial value of the
955 vector of partial results.
957 Option1 (adjust in epilog): Initialize the vector as follows:
958 add: [0,0,...,0,0]
959 mult: [1,1,...,1,1]
960 min/max: [init_val,init_val,..,init_val,init_val]
961 bit and/or: [init_val,init_val,..,init_val,init_val]
962 and when necessary (e.g. add/mult case) let the caller know
963 that it needs to adjust the result by init_val.
965 Option2: Initialize the vector as follows:
966 add: [0,0,...,0,init_val]
967 mult: [1,1,...,1,init_val]
968 min/max: [init_val,init_val,...,init_val]
969 bit and/or: [init_val,init_val,...,init_val]
970 and no adjustments are needed.
972 For example, for the following code:
974 s = init_val;
975 for (i=0;i<n;i++)
976 s = s + a[i];
978 STMT is 's = s + a[i]', and the reduction variable is 's'.
979 For a vector of 4 units, we want to return either [0,0,0,init_val],
980 or [0,0,0,0] and let the caller know that it needs to adjust
981 the result at the end by 'init_val'.
983 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
984 initialization vector is simpler (same element in all entries).
985 A cost model should help decide between these two schemes. */
987 static tree
989 {
995 tree vecdef;
996 tree def_for_init;
997 tree init_def;
1000 tree vector_type;
1006 {
1011 /* Create a vector of zeros for init_def. */
1014 else
1030 }
1033 }
1036 /* Function vect_create_epilog_for_reduction
1038 Create code at the loop-epilog to finalize the result of a reduction
1039 computation.
1041 VECT_DEF is a vector of partial results.
1042 REDUC_CODE is the tree-code for the epilog reduction.
1043 STMT is the scalar reduction stmt that is being vectorized.
1044 REDUCTION_PHI is the phi-node that carries the reduction computation.
1046 This function:
1047 1. Creates the reduction def-use cycle: sets the arguments for
1048 REDUCTION_PHI:
1049 The loop-entry argument is the vectorized initial-value of the reduction.
1050 The loop-latch argument is VECT_DEF - the vector of partial sums.
1051 2. "Reduces" the vector of partial results VECT_DEF into a single result,
1052 by applying the operation specified by REDUC_CODE if available, or by
1053 other means (whole-vector shifts or a scalar loop).
1054 The function also creates a new phi node at the loop exit to preserve
1055 loop-closed form, as illustrated below.
1057 The flow at the entry to this function:
1059 loop:
1060 vec_def = phi <null, null> # REDUCTION_PHI
1061 VECT_DEF = vector_stmt # vectorized form of STMT
1062 s_loop = scalar_stmt # (scalar) STMT
1063 loop_exit:
1064 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1065 use <s_out0>
1066 use <s_out0>
1068 The above is transformed by this function into:
1070 loop:
1071 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
1072 VECT_DEF = vector_stmt # vectorized form of STMT
1073 s_loop = scalar_stmt # (scalar) STMT
1074 loop_exit:
1075 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1076 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
1077 v_out2 = reduce <v_out1>
1078 s_out3 = extract_field <v_out2, 0>
1079 s_out4 = adjust_result <s_out3>
1080 use <s_out4>
1081 use <s_out4>
1082 */
1084 static void
1087 {
1089 tree vectype;
1093 basic_block exit_bb;
1094 tree scalar_dest;
1095 tree scalar_type;
1096 tree new_phi;
1097 block_stmt_iterator exit_bsi;
1098 tree vec_dest;
1099 tree new_temp;
1100 tree new_name;
1101 tree epilog_stmt;
1105 tree scalar_initial_def;
1106 tree vec_initial_def;
1107 tree orig_name;
1108 imm_use_iterator imm_iter;
1109 use_operand_p use_p;
1111 tree reduction_op;
1112 tree orig_stmt;
1113 tree use_stmt;
1122 /*** 1. Create the reduction def-use cycle ***/
1124 /* 1.1 set the loop-entry arg of the reduction-phi: */
1125 /* For the case of reduction, vect_get_vec_def_for_operand returns
1126 the scalar def before the loop, that defines the initial value
1127 of the reduction variable. */
1132 /* 1.2 set the loop-latch arg for the reduction-phi: */
1136 {
1141 }
1144 /*** 2. Create epilog code
1145 The reduction epilog code operates across the elements of the vector
1146 of partial results computed by the vectorized loop.
1147 The reduction epilog code consists of:
1148 step 1: compute the scalar result in a vector (v_out2)
1149 step 2: extract the scalar result (s_out3) from the vector (v_out2)
1150 step 3: adjust the scalar result (s_out3) if needed.
1152 Step 1 can be accomplished using one the following three schemes:
1153 (scheme 1) using reduc_code, if available.
1154 (scheme 2) using whole-vector shifts, if available.
1155 (scheme 3) using a scalar loop. In this case steps 1+2 above are
1156 combined.
1158 The overall epilog code looks like this:
1160 s_out0 = phi <s_loop> # original EXIT_PHI
1161 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
1162 v_out2 = reduce <v_out1> # step 1
1163 s_out3 = extract_field <v_out2, 0> # step 2
1164 s_out4 = adjust_result <s_out3> # step 3
1166 (step 3 is optional, and step2 1 and 2 may be combined).
1167 Lastly, the uses of s_out0 are replaced by s_out4.
1169 ***/
1171 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
1172 v_out1 = phi <v_loop> */
1179 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
1180 (i.e. when reduc_code is not available) and in the final adjustment
1181 code (if needed). Also get the original scalar reduction variable as
1182 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
1183 represents a reduction pattern), the tree-code and scalar-def are
1184 taken from the original stmt that the pattern-stmt (STMT) replaces.
1185 Otherwise (it is a regular reduction) - the tree-code and scalar-def
1186 are taken from STMT. */
1190 {
1191 /* Regular reduction */
1193 }
1194 else
1195 {
1196 /* Reduction pattern */
1200 }
1208 /* 2.3 Create the reduction code, using one of the three schemes described
1209 above. */
1212 {
1213 tree tmp;
1215 /*** Case 1: Create:
1216 v_out2 = reduc_expr <v_out1> */
1229 }
1230 else
1231 {
1237 tree vec_temp;
1241 else
1244 /* Regardless of whether we have a whole vector shift, if we're
1245 emulating the operation via tree-vect-generic, we don't want
1246 to use it. Only the first round of the reduction is likely
1247 to still be profitable via emulation. */
1248 /* ??? It might be better to emit a reduction tree code here, so that
1249 tree-vect-generic can expand the first round via bit tricks. */
1252 else
1253 {
1257 }
1260 {
1261 /*** Case 2: Create:
1262 for (offset = VS/2; offset >= element_size; offset/=2)
1263 {
1264 Create: va' = vec_shift <va, offset>
1265 Create: va = vop <va, va'>
1266 } */
1277 {
1290 }
1293 }
1294 else
1295 {
1296 tree rhs;
1298 /*** Case 3: Create:
1299 s = extract_field <v_out2, 0>
1300 for (offset = element_size;
1301 offset < vector_size;
1302 offset += element_size;)
1303 {
1304 Create: s' = extract_field <v_out2, offset>
1305 Create: s = op <s, s'>
1306 } */
1314 bitsize_zero_node);
1324 {
1325 tree tmp;
1328 bitpos);
1341 }
1344 }
1345 }
1347 /* 2.4 Extract the final scalar result. Create:
1348 s_out3 = extract_field <v_out2, bitpos> */
1351 {
1352 tree rhs;
1361 else
1370 }
1372 /* 2.4 Adjust the final result by the initial value of the reduction
1373 variable. (When such adjustment is not needed, then
1374 'scalar_initial_def' is zero).
1376 Create:
1377 s_out4 = scalar_expr <s_out3, scalar_initial_def> */
1380 {
1386 }
1388 /* 2.6 Replace uses of s_out0 with uses of s_out3 */
1390 /* Find the loop-closed-use at the loop exit of the original scalar result.
1391 (The reduction result is expected to have two immediate uses - one at the
1392 latch block, and one at the loop exit). */
1395 {
1397 {
1400 }
1401 }
1402 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
1404 /* Replace the uses: */
1409 }
1412 /* Function vectorizable_reduction.
1414 Check if STMT performs a reduction operation that can be vectorized.
1415 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1416 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1417 Return FALSE if not a vectorizable STMT, TRUE otherwise.
1419 This function also handles reduction idioms (patterns) that have been
1420 recognized in advance during vect_pattern_recog. In this case, STMT may be
1421 of this form:
1422 X = pattern_expr (arg0, arg1, ..., X)
1423 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
1424 sequence that had been detected and replaced by the pattern-stmt (STMT).
1426 In some cases of reduction patterns, the type of the reduction variable X is
1427 different than the type of the other arguments of STMT.
1428 In such cases, the vectype that is used when transforming STMT into a vector
1429 stmt is different than the vectype that is used to determine the
1430 vectorization factor, because it consists of a different number of elements
1431 than the actual number of elements that are being operated upon in parallel.
1433 For example, consider an accumulation of shorts into an int accumulator.
1434 On some targets it's possible to vectorize this pattern operating on 8
1435 shorts at a time (hence, the vectype for purposes of determining the
1436 vectorization factor should be V8HI); on the other hand, the vectype that
1437 is used to create the vector form is actually V4SI (the type of the result).
1439 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
1440 indicates what is the actual level of parallelism (V8HI in the example), so
1441 that the right vectorization factor would be derived. This vectype
1442 corresponds to the type of arguments to the reduction stmt, and should *NOT*
1443 be used to create the vectorized stmt. The right vectype for the vectorized
1444 stmt is obtained from the type of the result X:
1445 get_vectype_for_scalar_type (TREE_TYPE (X))
1447 This means that, contrary to "regular" reductions (or "regular" stmts in
1448 general), the following equation:
1449 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
1450 does *NOT* necessarily hold for reduction patterns. */
1452 bool
1454 {
1455 tree vec_dest;
1456 tree scalar_dest;
1457 tree op;
1463 tree operation;
1471 tree new_phi;
1472 tree scalar_type;
1474 tree orig_stmt;
1475 stmt_vec_info orig_stmt_info;
1480 stmt_vec_info prev_stmt_info;
1481 tree reduc_def;
1487 /* 1. Is vectorizable reduction? */
1489 /* Not supportable if the reduction variable is used in the loop. */
1496 /* Make sure it was already recognized as a reduction computation. */
1500 /* 2. Has this been recognized as a reduction pattern?
1502 Check if STMT represents a pattern that has been recognized
1503 in earlier analysis stages. For stmts that represent a pattern,
1504 the STMT_VINFO_RELATED_STMT field records the last stmt in
1505 the original sequence that constitutes the pattern. */
1509 {
1514 }
1516 /* 3. Check the operands of the operation. The first operands are defined
1517 inside the loop body. The last operand is the reduction variable,
1518 which is defined by the loop-header-phi. */
1530 /* All uses but the last are expected to be defined in the loop.
1531 The last use is the reduction variable. */
1533 {
1542 }
1551 else
1557 /* 4. Supportable by target? */
1559 /* 4.1. check support for the operation in the loop */
1562 {
1566 }
1569 {
1578 }
1580 /* Worthwhile without SIMD support? */
1584 {
1588 }
1590 /* 4.2. Check support for the epilog operation.
1592 If STMT represents a reduction pattern, then the type of the
1593 reduction variable may be different than the type of the rest
1594 of the arguments. For example, consider the case of accumulation
1595 of shorts into an int accumulator; The original code:
1596 S1: int_a = (int) short_a;
1597 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
1599 was replaced with:
1600 STMT: int_acc = widen_sum <short_a, int_acc>
1602 This means that:
1603 1. The tree-code that is used to create the vector operation in the
1604 epilog code (that reduces the partial results) is not the
1605 tree-code of STMT, but is rather the tree-code of the original
1606 stmt from the pattern that STMT is replacing. I.e, in the example
1607 above we want to use 'widen_sum' in the loop, but 'plus' in the
1608 epilog.
1609 2. The type (mode) we use to check available target support
1610 for the vector operation to be created in the *epilog*, is
1611 determined by the type of the reduction variable (in the example
1612 above we'd check this: plus_optab[vect_int_mode]).
1613 However the type (mode) we use to check available target support
1614 for the vector operation to be created *inside the loop*, is
1615 determined by the type of the other arguments to STMT (in the
1616 example we'd check this: widen_sum_optab[vect_short_mode]).
1618 This is contrary to "regular" reductions, in which the types of all
1619 the arguments are the same as the type of the reduction variable.
1620 For "regular" reductions we can therefore use the same vector type
1621 (and also the same tree-code) when generating the epilog code and
1622 when generating the code inside the loop. */
1625 {
1626 /* This is a reduction pattern: get the vectype from the type of the
1627 reduction variable, and get the tree-code from orig_stmt. */
1631 }
1632 else
1633 {
1634 /* Regular reduction: use the same vectype and tree-code as used for
1635 the vector code inside the loop can be used for the epilog code. */
1637 }
1643 {
1647 }
1649 {
1653 }
1656 {
1659 }
1661 /** Transform. **/
1666 /* Create the destination vector */
1669 /* Create the reduction-phi that defines the reduction-operand. */
1672 /* In case the vectorization factor (VF) is bigger than the number
1673 of elements that we can fit in a vectype (nunits), we have to generate
1674 more than one vector stmt - i.e - we need to "unroll" the
1675 vector stmt by a factor VF/nunits. For more details see documentation
1676 in vectorizable_operation. */
1680 {
1681 /* Handle uses. */
1683 {
1687 {
1690 }
1692 /* Get the vector def for the reduction variable from the phi node */
1694 }
1695 else
1696 {
1702 /* Get the vector def for the reduction variable from the vectorized
1703 reduction operation generated in the previous iteration (j-1) */
1705 }
1707 /* Arguments are ready. create the new vector stmt. */
1710 else
1712 reduc_def);
1720 else
1723 }
1725 /* Finalize the reduction-phi (set it's arguments) and create the
1726 epilog reduction code. */
1729 }
1731 /* Checks if CALL can be vectorized in type VECTYPE. Returns
1732 a function declaration if the target has a vectorized version
1733 of the function, or NULL_TREE if the function cannot be vectorized. */
1735 tree
1737 {
1741 /* We only handle functions that do not read or clobber memory -- i.e.
1742 const or novops ones. */
1753 vectype_in);
1754 }
1756 /* Function vectorizable_call.
1758 Check if STMT performs a function call that can be vectorized.
1759 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1760 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1761 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
1763 bool
1765 {
1766 tree vec_dest;
1767 tree scalar_dest;
1768 tree operation;
1776 call_expr_arg_iterator iter;
1784 /* FORNOW: not yet supported. */
1786 {
1790 }
1792 /* Is STMT a vectorizable call? */
1803 /* Process function arguments. */
1807 {
1810 /* Bail out if the function has more than two arguments, we
1811 do not have interesting builtin functions to vectorize with
1812 more than two arguments. */
1816 /* We can only handle calls with arguments of the same type. */
1819 {
1823 }
1827 {
1831 }
1832 }
1834 /* No arguments is also not good. */
1843 /* Only handle the case of vectors with the same number of elements.
1844 FIXME: We need a way to handle for example the SSE2 cvtpd2dq
1845 instruction which converts V2DFmode to V4SImode but only
1846 using the lower half of the V4SImode result. */
1850 /* For now, we only vectorize functions if a target specific builtin
1851 is available. TODO -- in some cases, it might be profitable to
1852 insert the calls for pieces of the vector, in order to be able
1853 to vectorize other operations in the loop. */
1856 {
1861 }
1866 {
1869 }
1871 /** Transform. **/
1880 /* Handle def. */
1886 {
1891 /* Build argument list for the vectorized call. */
1892 /* FIXME: Rewrite this so that it doesn't construct a temporary
1893 list. */
1897 {
1902 else
1906 }
1918 else
1921 }
1923 /* The call in STMT might prevent it from being removed in dce. We however
1924 cannot remove it here, due to the way the ssa name it defines is mapped
1925 to the new definition. So just replace rhs of the statement with something
1926 harmless. */
1931 }
1934 /* Function vectorizable_conversion.
1936 Check if STMT performs a conversion operation, that can be vectorized.
1937 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1938 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1939 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
1941 bool
1944 {
1945 tree vec_dest;
1946 tree scalar_dest;
1947 tree operation;
1948 tree op0;
1953 tree new_temp;
1956 tree new_stmt;
1962 tree builtin_decl;
1963 stmt_vec_info prev_stmt_info;
1965 /* Is STMT a vectorizable conversion? */
1974 {
1975 /* FORNOW: not yet supported. */
1979 }
1992 /* Check types of lhs and rhs */
2004 /* FORNOW: need to extend to support short<->float conversions as well. */
2008 /* Bail out if the types are both integral or non-integral */
2013 /* Sanity check: make sure that at least one copy of the vectorized stmt
2014 needs to be generated. */
2019 {
2023 }
2025 /* Supportable by target? */
2027 {
2031 }
2034 {
2037 }
2039 /** Transform. **/
2044 /* Handle def. */
2049 {
2050 tree sym;
2051 ssa_op_iter iter;
2055 else
2058 builtin_decl =
2062 /* Arguments are ready. create the new vector stmt. */
2068 {
2072 }
2076 else
2079 }
2081 }
2084 /* Function vectorizable_assignment.
2086 Check if STMT performs an assignment (copy) that can be vectorized.
2087 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2088 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2089 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2091 bool
2093 {
2094 tree vec_dest;
2095 tree scalar_dest;
2096 tree op;
2097 tree vec_oprnd;
2101 tree new_temp;
2117 /* FORNOW: not yet supported. */
2119 {
2123 }
2125 /* Is vectorizable assignment? */
2135 {
2139 }
2142 {
2145 }
2147 /** Transform. **/
2151 /* Handle def. */
2154 /* Handle use. */
2158 /* Arguments are ready. create the new vector stmt. */
2165 }
2168 /* Function vect_min_worthwhile_factor.
2170 For a loop where we could vectorize the operation indicated by CODE,
2171 return the minimum vectorization factor that makes it worthwhile
2172 to use generic vectors. */
2173 static int
2175 {
2177 {
2191 }
2192 }
2195 /* Function vectorizable_induction
2197 Check if PHI performs an induction computation that can be vectorized.
2198 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
2199 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
2200 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2202 bool
2205 {
2211 tree vec_def;
2221 {
2222 /* FORNOW: not yet supported. */
2226 }
2232 {
2235 }
2237 /** Transform. **/
2245 }
2248 /* Function vectorizable_operation.
2250 Check if STMT performs a binary or unary operation that can be vectorized.
2251 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2252 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2253 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2255 bool
2257 {
2258 tree vec_dest;
2259 tree scalar_dest;
2260 tree operation;
2268 tree new_temp;
2270 optab optab;
2275 tree new_stmt;
2276 stmt_vec_info prev_stmt_info;
2279 tree vectype_out;
2291 /* FORNOW: not yet supported. */
2293 {
2297 }
2299 /* Is STMT a vectorizable binary/unary operation? */
2316 /* Support only unary or binary operations. */
2319 {
2323 }
2327 {
2331 }
2334 {
2337 {
2341 }
2342 }
2344 /* Supportable by target? */
2346 {
2350 }
2354 {
2363 }
2365 /* Worthwhile without SIMD support? */
2369 {
2373 }
2376 {
2377 /* FORNOW: not yet supported. */
2381 /* Invariant argument is needed for a vector shift
2382 by a scalar shift operand. */
2387 {
2391 }
2392 }
2395 {
2398 }
2400 /** Transform. **/
2405 /* Handle def. */
2408 /* In case the vectorization factor (VF) is bigger than the number
2409 of elements that we can fit in a vectype (nunits), we have to generate
2410 more than one vector stmt - i.e - we need to "unroll" the
2411 vector stmt by a factor VF/nunits. In doing so, we record a pointer
2412 from one copy of the vector stmt to the next, in the field
2413 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
2414 stages to find the correct vector defs to be used when vectorizing
2415 stmts that use the defs of the current stmt. The example below illustrates
2416 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
2417 4 vectorized stmts):
2419 before vectorization:
2420 RELATED_STMT VEC_STMT
2421 S1: x = memref - -
2422 S2: z = x + 1 - -
2424 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
2425 there):
2426 RELATED_STMT VEC_STMT
2427 VS1_0: vx0 = memref0 VS1_1 -
2428 VS1_1: vx1 = memref1 VS1_2 -
2429 VS1_2: vx2 = memref2 VS1_3 -
2430 VS1_3: vx3 = memref3 - -
2431 S1: x = load - VS1_0
2432 S2: z = x + 1 - -
2434 step2: vectorize stmt S2 (done here):
2435 To vectorize stmt S2 we first need to find the relevant vector
2436 def for the first operand 'x'. This is, as usual, obtained from
2437 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
2438 that defines 'x' (S1). This way we find the stmt VS1_0, and the
2439 relevant vector def 'vx0'. Having found 'vx0' we can generate
2440 the vector stmt VS2_0, and as usual, record it in the
2441 STMT_VINFO_VEC_STMT of stmt S2.
2442 When creating the second copy (VS2_1), we obtain the relevant vector
2443 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
2444 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
2445 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
2446 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
2447 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
2448 chain of stmts and pointers:
2449 RELATED_STMT VEC_STMT
2450 VS1_0: vx0 = memref0 VS1_1 -
2451 VS1_1: vx1 = memref1 VS1_2 -
2452 VS1_2: vx2 = memref2 VS1_3 -
2453 VS1_3: vx3 = memref3 - -
2454 S1: x = load - VS1_0
2455 VS2_0: vz0 = vx0 + v1 VS2_1 -
2456 VS2_1: vz1 = vx1 + v1 VS2_2 -
2457 VS2_2: vz2 = vx2 + v1 VS2_3 -
2458 VS2_3: vz3 = vx3 + v1 - -
2459 S2: z = x + 1 - VS2_0 */
2463 {
2464 /* Handle uses. */
2466 {
2469 {
2471 {
2472 /* Vector shl and shr insn patterns can be defined with
2473 scalar operand 2 (shift operand). In this case, use
2474 constant or loop invariant op1 directly, without
2475 extending it to vector mode first. */
2478 {
2482 }
2483 }
2486 }
2487 }
2488 else
2489 {
2493 }
2495 /* Arguments are ready. create the new vector stmt. */
2500 else
2509 else
2512 }
2515 }
2518 /* Function vectorizable_type_demotion
2520 Check if STMT performs a binary or unary operation that involves
2521 type demotion, and if it can be vectorized.
2522 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2523 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2524 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2526 bool
2529 {
2530 tree vec_dest;
2531 tree scalar_dest;
2532 tree operation;
2533 tree op0;
2538 tree new_temp;
2541 tree new_stmt;
2542 stmt_vec_info prev_stmt_info;
2545 tree vectype_out;
2548 tree expr;
2549 tree vectype_in;
2550 tree scalar_type;
2551 optab optab;
2560 /* FORNOW: not yet supported. */
2562 {
2566 }
2568 /* Is STMT a vectorizable type-demotion operation? */
2601 /* Check the operands of the operation. */
2603 {
2607 }
2609 /* Supportable by target? */
2622 {
2625 }
2627 /** Transform. **/
2630 ncopies);
2632 /* Handle def. */
2635 /* In case the vectorization factor (VF) is bigger than the number
2636 of elements that we can fit in a vectype (nunits), we have to generate
2637 more than one vector stmt - i.e - we need to "unroll" the
2638 vector stmt by a factor VF/nunits. */
2641 {
2642 /* Handle uses. */
2644 {
2647 }
2648 else
2649 {
2652 }
2654 /* Arguments are ready. Create the new vector stmt. */
2663 else
2667 }
2671 }
2674 /* Function vect_gen_widened_results_half
2676 Create a vector stmt whose code, type, number of arguments, and result
2677 variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are
2678 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
2679 In the case that CODE is a CALL_EXPR, this means that a call to DECL
2680 needs to be created (DECL is a function-decl of a target-builtin).
2681 STMT is the original scalar stmt that we are vectorizing. */
2683 static tree
2687 tree stmt)
2688 {
2689 tree expr;
2690 tree new_stmt;
2691 tree new_temp;
2692 tree sym;
2693 ssa_op_iter iter;
2695 /* Generate half of the widened result: */
2697 {
2698 /* Target specific support */
2701 else
2703 }
2704 else
2705 {
2706 /* Generic support */
2710 else
2712 }
2719 {
2721 {
2725 }
2726 }
2729 }
2732 /* Function vectorizable_type_promotion
2734 Check if STMT performs a binary or unary operation that involves
2735 type promotion, and if it can be vectorized.
2736 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2737 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2738 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2740 bool
2743 {
2744 tree vec_dest;
2745 tree scalar_dest;
2746 tree operation;
2756 tree new_stmt;
2757 stmt_vec_info prev_stmt_info;
2760 tree vectype_out;
2763 tree vectype_in;
2771 /* FORNOW: not yet supported. */
2773 {
2777 }
2779 /* Is STMT a vectorizable type-promotion operation? */
2810 /* Check the operands of the operation. */
2812 {
2816 }
2820 {
2823 {
2827 }
2828 }
2830 /* Supportable by target? */
2838 {
2841 }
2843 /** Transform. **/
2847 ncopies);
2849 /* Handle def. */
2852 /* In case the vectorization factor (VF) is bigger than the number
2853 of elements that we can fit in a vectype (nunits), we have to generate
2854 more than one vector stmt - i.e - we need to "unroll" the
2855 vector stmt by a factor VF/nunits. */
2859 {
2860 /* Handle uses. */
2862 {
2866 }
2867 else
2868 {
2872 }
2874 /* Arguments are ready. Create the new vector stmt. We are creating
2875 two vector defs because the widened result does not fit in one vector.
2876 The vectorized stmt can be expressed as a call to a taregt builtin,
2877 or a using a tree-code. */
2878 /* Generate first half of the widened result: */
2883 else
2887 /* Generate second half of the widened result: */
2893 }
2897 }
2900 /* Function vect_strided_store_supported.
2902 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
2903 and FALSE otherwise. */
2905 static bool
2907 {
2913 /* Check that the operation is supported. */
2915 vectype);
2917 vectype);
2919 {
2923 }
2926 == CODE_FOR_nothing
2929 {
2933 }
2935 }
2938 /* Function vect_permute_store_chain.
2940 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
2941 a power of 2, generate interleave_high/low stmts to reorder the data
2942 correctly for the stores. Return the final references for stores in
2943 RESULT_CHAIN.
2945 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
2946 The input is 4 vectors each containing 8 elements. We assign a number to each
2947 element, the input sequence is:
2949 1st vec: 0 1 2 3 4 5 6 7
2950 2nd vec: 8 9 10 11 12 13 14 15
2951 3rd vec: 16 17 18 19 20 21 22 23
2952 4th vec: 24 25 26 27 28 29 30 31
2954 The output sequence should be:
2956 1st vec: 0 8 16 24 1 9 17 25
2957 2nd vec: 2 10 18 26 3 11 19 27
2958 3rd vec: 4 12 20 28 5 13 21 30
2959 4th vec: 6 14 22 30 7 15 23 31
2961 i.e., we interleave the contents of the four vectors in their order.
2963 We use interleave_high/low instructions to create such output. The input of
2964 each interleave_high/low operation is two vectors:
2965 1st vec 2nd vec
2966 0 1 2 3 4 5 6 7
2967 the even elements of the result vector are obtained left-to-right from the
2968 high/low elements of the first vector. The odd elements of the result are
2969 obtained left-to-right from the high/low elements of the second vector.
2970 The output of interleave_high will be: 0 4 1 5
2971 and of interleave_low: 2 6 3 7
2974 The permutation is done in log LENGTH stages. In each stage interleave_high
2975 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
2976 where the first argument is taken from the first half of DR_CHAIN and the
2977 second argument from it's second half.
2978 In our example,
2980 I1: interleave_high (1st vec, 3rd vec)
2981 I2: interleave_low (1st vec, 3rd vec)
2982 I3: interleave_high (2nd vec, 4th vec)
2983 I4: interleave_low (2nd vec, 4th vec)
2985 The output for the first stage is:
2987 I1: 0 16 1 17 2 18 3 19
2988 I2: 4 20 5 21 6 22 7 23
2989 I3: 8 24 9 25 10 26 11 27
2990 I4: 12 28 13 29 14 30 15 31
2992 The output of the second stage, i.e. the final result is:
2994 I1: 0 8 16 24 1 9 17 25
2995 I2: 2 10 18 26 3 11 19 27
2996 I3: 4 12 20 28 5 13 21 30
2997 I4: 6 14 22 30 7 15 23 31. */
2999 static bool
3002 tree stmt,
3005 {
3017 /* Check that the operation is supported. */
3024 {
3026 {
3030 /* Create interleaving stmt:
3031 in the case of big endian:
3032 high = interleave_high (vect1, vect2)
3033 and in the case of little endian:
3034 high = interleave_low (vect1, vect2). */
3040 else
3048 /* Create interleaving stmt:
3049 in the case of big endian:
3050 low = interleave_low (vect1, vect2)
3051 and in the case of little endian:
3052 low = interleave_high (vect1, vect2). */
3058 else
3065 }
3067 }
3069 }
3072 /* Function vectorizable_store.
3074 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
3075 can be vectorized.
3076 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3077 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3078 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3080 bool
3082 {
3083 tree scalar_dest;
3084 tree data_ref;
3085 tree op;
3092 tree dummy;
3094 ssa_op_iter iter;
3095 def_operand_p def_p;
3116 {
3120 }
3122 /* Is vectorizable store? */
3135 {
3139 }
3142 /* FORNOW. In some cases can vectorize even if data-type not supported
3143 (e.g. - array initialization with 0). */
3151 {
3155 }
3158 {
3161 }
3163 /** Transform. **/
3169 {
3176 /* We vectorize all the stmts of the interleaving group when we
3177 reach the last stmt in the group. */
3180 {
3183 }
3184 }
3185 else
3186 {
3190 }
3199 /* In case the vectorization factor (VF) is bigger than the number
3200 of elements that we can fit in a vectype (nunits), we have to generate
3201 more than one vector stmt - i.e - we need to "unroll" the
3202 vector stmt by a factor VF/nunits. For more details see documentation in
3203 vect_get_vec_def_for_copy_stmt. */
3205 /* In case of interleaving (non-unit strided access):
3207 S1: &base + 2 = x2
3208 S2: &base = x0
3209 S3: &base + 1 = x1
3210 S4: &base + 3 = x3
3212 We create vectorized stores starting from base address (the access of the
3213 first stmt in the chain (S2 in the above example), when the last store stmt
3214 of the chain (S4) is reached:
3216 VS1: &base = vx2
3217 VS2: &base + vec_size*1 = vx0
3218 VS3: &base + vec_size*2 = vx1
3219 VS4: &base + vec_size*3 = vx3
3221 Then permutation statements are generated:
3223 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
3224 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
3225 ...
3227 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3228 (the order of the data-refs in the output of vect_permute_store_chain
3229 corresponds to the order of scalar stmts in the interleaving chain - see
3230 the documentation of vect_permute_store_chain()).
3232 In case of both multiple types and interleaving, above vector stores and
3233 permutation stmts are created for every copy. The result vector stmts are
3234 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3235 STMT_VINFO_RELATED_STMT for the next copies.
3236 */
3240 {
3241 tree new_stmt;
3242 tree ptr_incr;
3245 {
3246 /* For interleaved stores we collect vectorized defs for all the
3247 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then used
3248 as an input to vect_permute_store_chain(), and OPRNDS as an input
3249 to vect_get_vec_def_for_stmt_copy() for the next copy.
3250 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3251 OPRNDS are of size 1. */
3254 {
3255 /* Since gaps are not supported for interleaved stores, GROUP_SIZE
3256 is the exact number of stmts in the chain. Therefore, NEXT_STMT
3257 can't be NULL_TREE. In case that there is no interleaving,
3258 GROUP_SIZE is 1, and only one iteration of the loop will be
3259 executed. */
3266 }
3270 }
3271 else
3272 {
3273 /* For interleaved stores we created vectorized defs for all the
3274 defs stored in OPRNDS in the previous iteration (previous copy).
3275 DR_CHAIN is then used as an input to vect_permute_store_chain(),
3276 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
3277 next copy.
3278 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3279 OPRNDS are of size 1. */
3281 {
3286 }
3288 }
3291 {
3293 /* Permute. */
3297 }
3301 {
3302 /* For strided stores vectorized defs are interleaved in
3303 vect_permute_store_chain(). */
3308 /* Arguments are ready. Create the new vector stmt. */
3312 /* Set the VDEFs for the vector pointer. If this virtual def
3313 has a use outside the loop and a loop peel is performed
3314 then the def may be renamed by the peel. Mark it for
3315 renaming so the later use will also be renamed. */
3318 {
3319 /* The original store is deleted so the same SSA_NAMEs
3320 can be used. */
3322 {
3325 }
3328 }
3329 else
3330 {
3331 /* Create new names for all the definitions created by COPY and
3332 add replacement mappings for each new name. */
3334 {
3337 }
3340 }
3346 /* Bump the vector pointer. */
3348 }
3349 }
3352 }
3355 /* Function vect_setup_realignment
3357 This function is called when vectorizing an unaligned load using
3358 the dr_unaligned_software_pipeline scheme.
3359 This function generates the following code at the loop prolog:
3361 p = initial_addr;
3362 msq_init = *(floor(p)); # prolog load
3363 realignment_token = call target_builtin;
3364 loop:
3365 msq = phi (msq_init, ---)
3367 The code above sets up a new (vector) pointer, pointing to the first
3368 location accessed by STMT, and a "floor-aligned" load using that pointer.
3369 It also generates code to compute the "realignment-token" (if the relevant
3370 target hook was defined), and creates a phi-node at the loop-header bb
3371 whose arguments are the result of the prolog-load (created by this
3372 function) and the result of a load that takes place in the loop (to be
3373 created by the caller to this function).
3374 The caller to this function uses the phi-result (msq) to create the
3375 realignment code inside the loop, and sets up the missing phi argument,
3376 as follows:
3378 loop:
3379 msq = phi (msq_init, lsq)
3380 lsq = *(floor(p')); # load in loop
3381 result = realign_load (msq, lsq, realignment_token);
3383 Input:
3384 STMT - (scalar) load stmt to be vectorized. This load accesses
3385 a memory location that may be unaligned.
3386 BSI - place where new code is to be inserted.
3388 Output:
3389 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
3390 target hook, if defined.
3391 Return value - the result of the loop-header phi node. */
3393 static tree
3396 {
3403 tree vec_dest;
3404 tree init_addr;
3405 tree inc;
3406 tree ptr;
3407 tree data_ref;
3408 tree new_stmt;
3409 basic_block new_bb;
3410 tree msq_init;
3411 tree new_temp;
3412 tree phi_stmt;
3413 tree msq;
3415 /* 1. Create msq_init = *(floor(p1)) in the loop preheader */
3418 NULL_TREE);
3429 /* 2. Create permutation mask, if required, in loop preheader. */
3431 {
3432 tree builtin_decl;
3445 /* The result of the CALL_EXPR to this builtin is determined from
3446 the value of the parameter and no global variables are touched
3447 which makes the builtin a "const" function. Requiring the
3448 builtin to have the "const" attribute makes it unnecessary
3449 to call mark_call_clobbered. */
3451 }
3453 /* 3. Create msq = phi <msq_init, lsq> in loop */
3461 }
3464 /* Function vect_strided_load_supported.
3466 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
3467 and FALSE otherwise. */
3469 static bool
3471 {
3479 {
3483 }
3486 {
3490 }
3494 {
3498 }
3501 {
3505 }
3507 }
3510 /* Function vect_permute_load_chain.
3512 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
3513 a power of 2, generate extract_even/odd stmts to reorder the input data
3514 correctly. Return the final references for loads in RESULT_CHAIN.
3516 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
3517 The input is 4 vectors each containing 8 elements. We assign a number to each
3518 element, the input sequence is:
3520 1st vec: 0 1 2 3 4 5 6 7
3521 2nd vec: 8 9 10 11 12 13 14 15
3522 3rd vec: 16 17 18 19 20 21 22 23
3523 4th vec: 24 25 26 27 28 29 30 31
3525 The output sequence should be:
3527 1st vec: 0 4 8 12 16 20 24 28
3528 2nd vec: 1 5 9 13 17 21 25 29
3529 3rd vec: 2 6 10 14 18 22 26 30
3530 4th vec: 3 7 11 15 19 23 27 31
3532 i.e., the first output vector should contain the first elements of each
3533 interleaving group, etc.
3535 We use extract_even/odd instructions to create such output. The input of each
3536 extract_even/odd operation is two vectors
3537 1st vec 2nd vec
3538 0 1 2 3 4 5 6 7
3540 and the output is the vector of extracted even/odd elements. The output of
3541 extract_even will be: 0 2 4 6
3542 and of extract_odd: 1 3 5 7
3545 The permutation is done in log LENGTH stages. In each stage extract_even and
3546 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
3547 order. In our example,
3549 E1: extract_even (1st vec, 2nd vec)
3550 E2: extract_odd (1st vec, 2nd vec)
3551 E3: extract_even (3rd vec, 4th vec)
3552 E4: extract_odd (3rd vec, 4th vec)
3554 The output for the first stage will be:
3556 E1: 0 2 4 6 8 10 12 14
3557 E2: 1 3 5 7 9 11 13 15
3558 E3: 16 18 20 22 24 26 28 30
3559 E4: 17 19 21 23 25 27 29 31
3561 In order to proceed and create the correct sequence for the next stage (or
3562 for the correct output, if the second stage is the last one, as in our
3563 example), we first put the output of extract_even operation and then the
3564 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
3565 The input for the second stage is:
3567 1st vec (E1): 0 2 4 6 8 10 12 14
3568 2nd vec (E3): 16 18 20 22 24 26 28 30
3569 3rd vec (E2): 1 3 5 7 9 11 13 15
3570 4th vec (E4): 17 19 21 23 25 27 29 31
3572 The output of the second stage:
3574 E1: 0 4 8 12 16 20 24 28
3575 E2: 2 6 10 14 18 22 26 30
3576 E3: 1 5 9 13 17 21 25 29
3577 E4: 3 7 11 15 19 23 27 31
3579 And RESULT_CHAIN after reordering:
3581 1st vec (E1): 0 4 8 12 16 20 24 28
3582 2nd vec (E3): 1 5 9 13 17 21 25 29
3583 3rd vec (E2): 2 6 10 14 18 22 26 30
3584 4th vec (E4): 3 7 11 15 19 23 27 31. */
3586 static bool
3589 tree stmt,
3592 {
3595 tree tmp;
3599 /* Check that the operation is supported. */
3605 {
3607 {
3611 /* data_ref = permute_even (first_data_ref, second_data_ref); */
3627 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
3641 }
3643 }
3645 }
3648 /* Function vect_transform_strided_load.
3650 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
3651 to perform their permutation and ascribe the result vectorized statements to
3652 the scalar statements.
3653 */
3655 static bool
3658 {
3664 tree tmp_data_ref;
3666 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
3667 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
3668 vectors, that are ready for vector computation. */
3670 /* Permute. */
3674 /* Put a permuted data-ref in the VECTORIZED_STMT field.
3675 Since we scan the chain starting from it's first node, their order
3676 corresponds the order of data-refs in RESULT_CHAIN. */
3680 {
3684 /* Skip the gaps. Loads created for the gaps will be removed by dead
3685 code elimination pass later.
3686 DR_GROUP_GAP is the number of steps in elements from the previous
3687 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
3688 correspond to the gaps.
3689 */
3691 {
3692 gap_count++;
3694 }
3697 {
3699 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
3700 copies, and we put the new vector statement in the first available
3701 RELATED_STMT. */
3704 else
3705 {
3710 {
3713 }
3715 }
3718 /* If NEXT_STMT accesses the same DR as the previous statement,
3719 put the same TMP_DATA_REF as its vectorized statement; otherwise
3720 get the next data-ref from RESULT_CHAIN. */
3723 }
3724 }
3726 }
3729 /* vectorizable_load.
3731 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
3732 can be vectorized.
3733 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3734 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3735 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3737 bool
3739 {
3740 tree scalar_dest;
3743 tree op;
3745 stmt_vec_info prev_stmt_info;
3750 tree new_temp;
3753 tree dummy;
3756 tree ptr_incr;
3766 tree first_stmt;
3774 /* FORNOW: not yet supported. */
3776 {
3780 }
3782 /* Is vectorizable load? */
3801 /* FORNOW. In some cases can vectorize even if data-type not supported
3802 (e.g. - data copies). */
3804 {
3808 }
3810 /* Check if the load is a part of an interleaving chain. */
3812 {
3815 /* Check if interleaving is supported. */
3818 }
3821 {
3824 }
3826 /** Transform. **/
3832 {
3834 /* Check if the chain of loads is already vectorized. */
3836 {
3839 }
3843 }
3844 else
3845 {
3849 }
3855 /* In case the vectorization factor (VF) is bigger than the number
3856 of elements that we can fit in a vectype (nunits), we have to generate
3857 more than one vector stmt - i.e - we need to "unroll" the
3858 vector stmt by a factor VF/nunits. In doing so, we record a pointer
3859 from one copy of the vector stmt to the next, in the field
3860 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3861 stages to find the correct vector defs to be used when vectorizing
3862 stmts that use the defs of the current stmt. The example below illustrates
3863 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3864 4 vectorized stmts):
3866 before vectorization:
3867 RELATED_STMT VEC_STMT
3868 S1: x = memref - -
3869 S2: z = x + 1 - -
3871 step 1: vectorize stmt S1:
3872 We first create the vector stmt VS1_0, and, as usual, record a
3873 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
3874 Next, we create the vector stmt VS1_1, and record a pointer to
3875 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
3876 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
3877 stmts and pointers:
3878 RELATED_STMT VEC_STMT
3879 VS1_0: vx0 = memref0 VS1_1 -
3880 VS1_1: vx1 = memref1 VS1_2 -
3881 VS1_2: vx2 = memref2 VS1_3 -
3882 VS1_3: vx3 = memref3 - -
3883 S1: x = load - VS1_0
3884 S2: z = x + 1 - -
3886 See in documentation in vect_get_vec_def_for_stmt_copy for how the
3887 information we recorded in RELATED_STMT field is used to vectorize
3888 stmt S2. */
3890 /* In case of interleaving (non-unit strided access):
3892 S1: x2 = &base + 2
3893 S2: x0 = &base
3894 S3: x1 = &base + 1
3895 S4: x3 = &base + 3
3897 Vectorized loads are created in the order of memory accesses
3898 starting from the access of the first stmt of the chain:
3900 VS1: vx0 = &base
3901 VS2: vx1 = &base + vec_size*1
3902 VS3: vx3 = &base + vec_size*2
3903 VS4: vx4 = &base + vec_size*3
3905 Then permutation statements are generated:
3907 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
3908 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
3909 ...
3911 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3912 (the order of the data-refs in the output of vect_permute_load_chain
3913 corresponds to the order of scalar stmts in the interleaving chain - see
3914 the documentation of vect_permute_load_chain()).
3915 The generation of permutation stmts and recording them in
3916 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
3918 In case of both multiple types and interleaving, the vector loads and
3919 permutation stmts above are created for every copy. The result vector stmts
3920 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3921 STMT_VINFO_RELATED_STMT for the next copies. */
3923 /* If the data reference is aligned (dr_aligned) or potentially unaligned
3924 on a target that supports unaligned accesses (dr_unaligned_supported)
3925 we generate the following code:
3926 p = initial_addr;
3927 indx = 0;
3928 loop {
3929 p = p + indx * vectype_size;
3930 vec_dest = *(p);
3931 indx = indx + 1;
3932 }
3934 Otherwise, the data reference is potentially unaligned on a target that
3935 does not support unaligned accesses (dr_unaligned_software_pipeline) -
3936 then generate the following code, in which the data in each iteration is
3937 obtained by two vector loads, one from the previous iteration, and one
3938 from the current iteration:
3939 p1 = initial_addr;
3940 msq_init = *(floor(p1))
3941 p2 = initial_addr + VS - 1;
3942 realignment_token = call target_builtin;
3943 indx = 0;
3944 loop {
3945 p2 = p2 + indx * vectype_size
3946 lsq = *(floor(p2))
3947 vec_dest = realign_load (msq, lsq, realignment_token)
3948 indx = indx + 1;
3949 msq = lsq;
3950 } */
3953 {
3957 }
3961 {
3962 /* 1. Create the vector pointer update chain. */
3966 else
3970 {
3971 /* 2. Create the vector-load in the loop. */
3973 {
3979 {
3985 data_ref =
3988 }
3995 }
4004 /* 3. Handle explicit realignment if necessary/supported. */
4006 {
4007 /* Create in loop:
4008 <vec_dest = realign_load (msq, lsq, realignment_token)> */
4013 new_stmt =
4022 }
4027 }
4030 {
4035 }
4036 else
4037 {
4040 else
4043 }
4044 }
4047 }
4050 /* Function vectorizable_live_operation.
4052 STMT computes a value that is used outside the loop. Check if
4053 it can be supported. */
4055 bool
4059 {
4060 tree operation;
4065 tree op;
4083 /* FORNOW: support only if all uses are invariant. This means
4084 that the scalar operations can remain in place, unvectorized.
4085 The original last scalar value that they compute will be used. */
4088 {
4091 {
4095 }
4099 }
4101 /* No transformation is required for the cases we currently support. */
4103 }
4106 /* Function vect_is_simple_cond.
4108 Input:
4109 LOOP - the loop that is being vectorized.
4110 COND - Condition that is checked for simple use.
4112 Returns whether a COND can be vectorized. Checks whether
4113 condition operands are supportable using vec_is_simple_use. */
4115 static bool
4117 {
4119 tree def;
4129 {
4133 }
4138 {
4142 }
4147 }
4149 /* vectorizable_condition.
4151 Check if STMT is conditional modify expression that can be vectorized.
4152 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4153 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
4154 at BSI.
4156 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4158 bool
4160 {
4169 tree new_temp;
4172 tree def;
4187 /* FORNOW: not yet supported. */
4189 {
4193 }
4195 /* Is vectorizable conditional operation? */
4211 /* We do not handle two different vector types for the condition
4212 and the values. */
4217 {
4222 }
4228 {
4233 }
4242 {
4245 }
4247 /* Transform */
4249 /* Handle def. */
4253 /* Handle cond expr. */
4254 vec_cond_lhs =
4256 vec_cond_rhs =
4261 /* Arguments are ready. create the new vector stmt. */
4273 }
4275 /* Function vect_transform_stmt.
4277 Create a vectorized stmt to replace STMT, and insert it at BSI. */
4279 bool
4281 {
4285 tree orig_stmt_in_pattern;
4289 {
4329 {
4330 /* In case of interleaving, the whole chain is vectorized when the
4331 last store in the chain is reached. Store stmts before the last
4332 one are skipped, and there vec_stmt_info shouldn't be freed
4333 meanwhile. */
4337 }
4338 else
4358 {
4362 }
4363 }
4367 {
4370 }
4373 {
4377 {
4379 /* STMT was inserted by the vectorizer to replace a computation idiom.
4380 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
4381 computed this idiom. We need to record a pointer to VEC_STMT in
4382 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
4383 documentation of vect_pattern_recog. */
4385 {
4388 }
4389 }
4390 }
4393 }
4396 /* This function builds ni_name = number of iterations loop executes
4397 on the loop preheader. */
4399 static tree
4401 {
4403 edge pe;
4413 {
4416 }
4419 }
4422 /* This function generates the following statements:
4424 ni_name = number of iterations loop executes
4425 ratio = ni_name / vf
4426 ratio_mult_vf_name = ratio * vf
4428 and places them at the loop preheader edge. */
4430 static void
4435 {
4437 edge pe;
4438 basic_block new_bb;
4440 tree var;
4441 tree ratio_name;
4442 tree ratio_mult_vf_name;
4446 tree log_vf;
4450 /* Generate temporary variable that contains
4451 number of iterations loop executes. */
4456 /* Create: ratio = ni >> log2(vf) */
4460 {
4468 }
4470 /* Create: ratio_mult_vf = ratio << log2 (vf). */
4475 {
4484 }
4491 }
4494 /* Function update_vuses_to_preheader.
4496 Input:
4497 STMT - a statement with potential VUSEs.
4498 LOOP - the loop whose preheader will contain STMT.
4500 It's possible to vectorize a loop even though an SSA_NAME from a VUSE
4501 appears to be defined in a VDEF in another statement in a loop.
4502 One such case is when the VUSE is at the dereference of a __restricted__
4503 pointer in a load and the VDEF is at the dereference of a different
4504 __restricted__ pointer in a store. Vectorization may result in
4505 copy_virtual_uses being called to copy the problematic VUSE to a new
4506 statement that is being inserted in the loop preheader. This procedure
4507 is called to change the SSA_NAME in the new statement's VUSE from the
4508 SSA_NAME updated in the loop to the related SSA_NAME available on the
4509 path entering the loop.
4511 When this function is called, we have the following situation:
4513 # vuse <name1>
4514 S1: vload
4515 do {
4516 # name1 = phi < name0 , name2>
4518 # vuse <name1>
4519 S2: vload
4521 # name2 = vdef <name1>
4522 S3: vstore
4524 }while...
4526 Stmt S1 was created in the loop preheader block as part of misaligned-load
4527 handling. This function fixes the name of the vuse of S1 from 'name1' to
4528 'name0'. */
4530 static void
4532 {
4535 ssa_op_iter iter;
4536 use_operand_p use_p;
4539 {
4545 /* For a use before any definitions, def_stmt is a NOP_EXPR. */
4548 {
4549 /* If the block containing the statement defining the SSA_NAME
4550 is in the loop then it's necessary to find the definition
4551 outside the loop using the PHI nodes of the header. */
4552 tree phi;
4556 {
4558 {
4562 }
4563 }
4565 }
4566 }
4567 }
4570 /* Function vect_update_ivs_after_vectorizer.
4572 "Advance" the induction variables of LOOP to the value they should take
4573 after the execution of LOOP. This is currently necessary because the
4574 vectorizer does not handle induction variables that are used after the
4575 loop. Such a situation occurs when the last iterations of LOOP are
4576 peeled, because:
4577 1. We introduced new uses after LOOP for IVs that were not originally used
4578 after LOOP: the IVs of LOOP are now used by an epilog loop.
4579 2. LOOP is going to be vectorized; this means that it will iterate N/VF
4580 times, whereas the loop IVs should be bumped N times.
4582 Input:
4583 - LOOP - a loop that is going to be vectorized. The last few iterations
4584 of LOOP were peeled.
4585 - NITERS - the number of iterations that LOOP executes (before it is
4586 vectorized). i.e, the number of times the ivs should be bumped.
4587 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
4588 coming out from LOOP on which there are uses of the LOOP ivs
4589 (this is the path from LOOP->exit to epilog_loop->preheader).
4591 The new definitions of the ivs are placed in LOOP->exit.
4592 The phi args associated with the edge UPDATE_E in the bb
4593 UPDATE_E->dest are updated accordingly.
4595 Assumption 1: Like the rest of the vectorizer, this function assumes
4596 a single loop exit that has a single predecessor.
4598 Assumption 2: The phi nodes in the LOOP header and in update_bb are
4599 organized in the same order.
4601 Assumption 3: The access function of the ivs is simple enough (see
4602 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
4604 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
4605 coming out of LOOP on which the ivs of LOOP are used (this is the path
4606 that leads to the epilog loop; other paths skip the epilog loop). This
4607 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
4608 needs to have its phis updated.
4609 */
4611 static void
4613 edge update_e)
4614 {
4620 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
4622 /* Make sure there exists a single-predecessor exit bb: */
4628 {
4630 tree evolution_part;
4631 tree init_expr;
4632 tree step_expr;
4634 block_stmt_iterator last_bsi;
4637 {
4640 }
4642 /* Skip virtual phi's. */
4644 {
4648 }
4650 /* Skip reduction phis. */
4652 {
4656 }
4660 evolution_part =
4664 /* FORNOW: We do not support IVs whose evolution function is a polynomial
4665 of degree >= 2 or exponential. */
4675 niters),
4676 step_expr),
4677 init_expr);
4684 /* Insert stmt into exit_bb. */
4689 /* Fix phi expressions in the successor bb. */
4691 }
4692 }
4695 /* Function vect_do_peeling_for_loop_bound
4697 Peel the last iterations of the loop represented by LOOP_VINFO.
4698 The peeled iterations form a new epilog loop. Given that the loop now
4699 iterates NITERS times, the new epilog loop iterates
4700 NITERS % VECTORIZATION_FACTOR times.
4702 The original loop will later be made to iterate
4703 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
4705 static void
4707 {
4711 edge update_e;
4712 basic_block preheader;
4721 /* Generate the following variables on the preheader of original loop:
4723 ni_name = number of iteration the original loop executes
4724 ratio = ni_name / vf
4725 ratio_mult_vf_name = ratio * vf */
4730 /* Threshold for vectorized loop. */
4737 #ifdef ENABLE_CHECKING
4739 #endif
4741 /* A guard that controls whether the new_loop is to be executed or skipped
4742 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
4743 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
4744 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
4745 is on the path where the LOOP IVs are used and need to be updated. */
4750 else
4753 /* Update IVs of original loop as if they were advanced
4754 by ratio_mult_vf_name steps. */
4757 /* After peeling we have to reset scalar evolution analyzer. */
4761 }
4764 /* Function vect_gen_niters_for_prolog_loop
4766 Set the number of iterations for the loop represented by LOOP_VINFO
4767 to the minimum between LOOP_NITERS (the original iteration count of the loop)
4768 and the misalignment of DR - the data reference recorded in
4769 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
4770 this loop, the data reference DR will refer to an aligned location.
4772 The following computation is generated:
4774 If the misalignment of DR is known at compile time:
4775 addr_mis = int mis = DR_MISALIGNMENT (dr);
4776 Else, compute address misalignment in bytes:
4777 addr_mis = addr & (vectype_size - 1)
4779 prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
4781 (elem_size = element type size; an element is the scalar element
4782 whose type is the inner type of the vectype)
4784 For interleaving,
4786 prolog_niters = min ( LOOP_NITERS ,
4787 (VF/group_size - addr_mis/elem_size)&(VF/group_size-1) )
4788 where group_size is the size of the interleaved group.
4789 */
4791 static tree
4793 {
4799 edge pe;
4800 basic_block new_bb;
4810 {
4811 /* For interleaved access element size must be multiplied by the size of
4812 the interleaved group. */
4816 }
4821 {
4829 }
4830 else
4831 {
4833 tree start_addr =
4839 tree elem_size_log =
4843 tree byte_misalign;
4844 tree elem_misalign;
4849 /* Create: byte_misalign = addr & (vectype_size - 1) */
4850 byte_misalign =
4853 /* Create: elem_misalign = byte_misalign / element_size */
4854 elem_misalign =
4857 /* Create: (niters_type) (VF - elem_misalign)&(VF - 1) */
4861 }
4863 /* Create: prolog_loop_niters = min (iters, loop_niters) */
4864 /* If the loop bound is known at compile time we already verified that it is
4865 greater than vf; since the misalignment ('iters') is at most vf, there's
4866 no need to generate the MIN_EXPR in this case. */
4871 {
4874 }
4880 /* Insert stmt on loop preheader edge. */
4882 {
4885 }
4888 }
4891 /* Function vect_update_init_of_dr
4893 NITERS iterations were peeled from LOOP. DR represents a data reference
4894 in LOOP. This function updates the information recorded in DR to
4895 account for the fact that the first NITERS iterations had already been
4896 executed. Specifically, it updates the OFFSET field of DR. */
4898 static void
4900 {
4906 }
4909 /* Function vect_update_inits_of_drs
4911 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
4912 This function updates the information recorded for the data references in
4913 the loop to account for the fact that the first NITERS iterations had
4914 already been executed. Specifically, it updates the initial_condition of the
4915 access_function of all the data_references in the loop. */
4917 static void
4919 {
4929 }
4932 /* Function vect_do_peeling_for_alignment
4934 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
4935 'niters' is set to the misalignment of one of the data references in the
4936 loop, thereby forcing it to refer to an aligned location at the beginning
4937 of the execution of this loop. The data reference for which we are
4938 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
4940 static void
4942 {
4945 tree n_iters;
4956 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
4957 new_loop =
4961 #ifdef ENABLE_CHECKING
4963 #endif
4965 /* Update number of times loop executes. */
4970 /* Update the init conditions of the access functions of all data refs. */
4973 /* After peeling we have to reset scalar evolution analyzer. */
4977 }
4980 /* Function vect_create_cond_for_align_checks.
4982 Create a conditional expression that represents the alignment checks for
4983 all of data references (array element references) whose alignment must be
4984 checked at runtime.
4986 Input:
4987 LOOP_VINFO - two fields of the loop information are used.
4988 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
4989 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
4991 Output:
4992 COND_EXPR_STMT_LIST - statements needed to construct the conditional
4993 expression.
4994 The returned value is the conditional expression to be used in the if
4995 statement that controls which version of the loop gets executed at runtime.
4997 The algorithm makes two assumptions:
4998 1) The number of bytes "n" in a vector is a power of 2.
4999 2) An address "a" is aligned if a%n is zero and that this
5000 test can be done as a&(n-1) == 0. For example, for 16
5001 byte vectors the test is a&0xf == 0. */
5003 static tree
5006 {
5011 tree mask_cst;
5013 tree psize;
5014 tree int_ptrsize_type;
5018 tree ptrsize_zero;
5020 /* Check that mask is one less than a power of 2, i.e., mask is
5021 all zeros followed by all ones. */
5024 /* CHECKME: what is the best integer or unsigned type to use to hold a
5025 cast from a pointer value? */
5027 int_ptrsize_type
5030 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
5031 of the first vector of the i'th data reference. */
5034 {
5036 tree addr_base;
5040 /* create: addr_tmp = (int)(address_of_first_vector) */
5043 NULL_TREE);
5057 /* The addresses are OR together. */
5060 {
5061 /* create: or_tmp = or_tmp | addr_tmp */
5072 }
5073 else
5080 /* create: and_tmp = or_tmp & mask */
5090 /* Make and_tmp the left operand of the conditional test against zero.
5091 if and_tmp has a nonzero bit then some address is unaligned. */
5095 }
5098 /* Function vect_transform_loop.
5100 The analysis phase has determined that the loop is vectorizable.
5101 Vectorize the loop - created vectorized stmts to replace the scalar
5102 stmts in the loop, and update the loop exit condition. */
5104 void
5106 {
5119 /* If the loop has data references that may or may not be aligned then
5120 two versions of the loop need to be generated, one which is vectorized
5121 and one which isn't. A test is then generated to control which of the
5122 loops is executed. The test checks for the alignment of all of the
5123 data references that may or may not be aligned. */
5126 {
5128 tree cond_expr;
5130 basic_block condition_bb;
5131 block_stmt_iterator cond_exp_bsi;
5132 basic_block merge_bb;
5133 basic_block new_exit_bb;
5145 /** Loop versioning violates an assumption we try to maintain during
5146 vectorization - that the loop exit block has a single predecessor.
5147 After versioning, the exit block of both loop versions is the same
5148 basic block (i.e. it has two predecessors). Just in order to simplify
5149 following transformations in the vectorizer, we fix this situation
5150 here by adding a new (empty) block on the exit-edge of the loop,
5151 with the proper loop-exit phis to maintain loop-closed-form. **/
5161 {
5163 new_exit_bb);
5167 }
5169 /** end loop-exit-fixes after versioning **/
5174 }
5176 /* CHECKME: we wouldn't need this if we called update_ssa once
5177 for all loops. */
5180 /* Peel the loop if there are data refs with unknown alignment.
5181 Only one data ref with unknown store is allowed. */
5186 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5187 compile time constant), or it is a constant that doesn't divide by the
5188 vectorization factor, then an epilog loop needs to be created.
5189 We therefore duplicate the loop: the original loop will be vectorized,
5190 and will compute the first (n/VF) iterations. The second copy of the loop
5191 will remain scalar and will compute the remaining (n%VF) iterations.
5192 (VF is the vectorization factor). */
5198 else
5202 /* 1) Make sure the loop header has exactly two entries
5203 2) Make sure we have a preheader basic block. */
5209 /* FORNOW: the vectorizer supports only loops which body consist
5210 of one basic block (header + empty latch). When the vectorizer will
5211 support more involved loop forms, the order by which the BBs are
5212 traversed need to be reconsidered. */
5215 {
5217 stmt_vec_info stmt_info;
5218 tree phi;
5221 {
5223 {
5226 }
5240 {
5244 }
5245 }
5248 {
5253 {
5256 }
5261 {
5264 }
5272 /* -------- vectorize statement ------------ */
5279 {
5280 stmt_ann_t ann;
5282 {
5283 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
5284 interleaving chain was completed - free all the stores in
5285 the chain. */
5287 tree tmp;
5288 stmt_vec_info next_stmt_info;
5291 {
5294 /* Free the attached stmt_vec_info and remove the stmt. */
5301 }
5304 }
5305 else
5306 {
5307 /* Free the attached stmt_vec_info and remove the stmt. */
5313 }
5314 }
5323 /* The memory tags and pointers in vectorized statements need to
5324 have their SSA forms updated. FIXME, why can't this be delayed
5325 until all the loops have been transformed? */
5330 }