| blob | 5fdbbe122be422fcdb7d6a34e694fc04ddcf4055 |
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_estimate_min_profitable_iters
79 Return the number of iterations required for the vector version of the
80 loop to be profitable relative to the cost of the scalar version of the
81 loop.
83 TODO: Take profile info into account before making vectorization
84 decisions, if available. */
86 int
88 {
101 /* Cost model disabled. */
103 {
107 }
109 /* Requires loop versioning tests to handle misalignment.
110 FIXME: Make cost depend on number of stmts in may_misalign list. */
113 {
118 }
120 /* Requires a prologue loop when peeling to handle misalignment. Add cost of
121 two guards, one for the peeled loop and one for the vector loop. */
125 {
130 }
132 /* Requires an epilogue loop to finish up remaining iterations after vector
133 loop. Add cost of two guards, one for the peeled loop and one for the
134 vector loop. */
139 {
144 }
146 /* Count statements in scalar loop. Using this as scalar cost for a single
147 iteration for now.
149 TODO: Add outer loop support.
151 TODO: Consider assigning different costs to different scalar
152 statements. */
155 {
156 block_stmt_iterator si;
160 {
166 scalar_single_iter_cost++;
169 }
170 }
172 /* Add additional cost for the peeled instructions in prologue and epilogue
173 loop.
175 FORNOW: If we dont know the value of peel_iters for prologue or epilogue
176 at compile-time - we assume the worst.
178 TODO: Build an expression that represents peel_iters for prologue and
179 epilogue to be used in a run-time test. */
184 {
190 /* If peeling for alignment is unknown, loop bound of main loop becomes
191 unknown. */
195 "epilogue peel iters set conservatively because "
197 }
198 else
199 {
201 {
205 "epilogue peel iters set conservatively because "
207 }
208 else
209 peel_iters_epilogue =
212 }
217 /* Calculate number of iterations required to make the vector version
218 profitable, relative to the loop bodies only. The following condition
219 must hold true: ((SIC*VF)-VIC)*niters > VOC*VF, where
220 SIC = scalar iteration cost, VIC = vector iteration cost,
221 VOC = vector outside cost and VF = vectorization factor. */
224 {
227 else
228 {
236 min_profitable_iters++;
237 }
238 }
239 /* vector version will never be profitable. */
240 else
241 {
244 "is divisible by scalar iteration cost = %d by a factor "
248 }
251 {
254 vec_inside_cost);
256 vec_outside_cost);
259 peel_iters_prologue);
261 peel_iters_epilogue);
263 min_profitable_iters);
266 }
269 }
272 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
273 functions. Design better to avoid maintenance issues. */
275 /* Function vect_model_reduction_cost.
277 Models cost for a reduction operation, including the vector ops
278 generated within the strip-mine loop, the initial definition before
279 the loop, and the epilogue code that must be generated. */
281 static void
284 {
287 optab optab;
288 tree vectype;
289 tree orig_stmt;
290 tree reduction_op;
295 /* Cost of reduction op inside loop. */
308 /* Add in cost for initial definition. */
311 /* Determine cost of epilogue code.
313 We have a reduction operator that will reduce the vector in one statement.
314 Also requires scalar extract. */
318 else
319 {
321 tree bitsize =
328 /* We have a whole vector shift available. */
331 /* Final reduction via vector shifts and the reduction operator. Also
332 requires scalar extract. */
334 else
335 /* Use extracts and reduction op for final reduction. For N elements,
336 we have N extracts and N-1 reduction ops. */
338 }
346 }
349 /* Function vect_model_induction_cost.
351 Models cost for induction operations. */
353 static void
355 {
356 /* loop cost for vec_loop. */
358 /* prologue cost for vec_init and vec_step. */
365 }
368 /* Function vect_model_simple_cost.
370 Models cost for simple operations, i.e. those that only emit ncopies of a
371 single op. Right now, this does not account for multiple insns that could
372 be generated for the single vector op. We will handle that shortly. */
374 static void
376 {
383 }
386 /* Function vect_cost_strided_group_size
388 For strided load or store, return the group_size only if it is the first
389 load or store of a group, else return 1. This ensures that group size is
390 only returned once per group. */
392 static int
394 {
401 }
404 /* Function vect_model_store_cost
406 Models cost for stores. In the case of strided accesses, one access
407 has the overhead of the strided access attributed to it. */
409 static void
411 {
415 /* Strided access? */
418 /* Not a strided access. */
419 else
422 /* Is this an access in a group of stores, which provide strided access?
423 If so, add in the cost of the permutes. */
425 {
426 /* Uses a high and low interleave operation for each needed permute. */
432 group_size);
434 }
436 /* Costs of the stores. */
445 }
448 /* Function vect_model_load_cost
450 Models cost for loads. In the case of strided accesses, the last access
451 has the overhead of the strided access attributed to it. Since unaligned
452 accesses are supported for loads, we also account for the costs of the
453 access scheme chosen. */
455 static void
458 {
462 tree first_stmt;
465 /* Strided accesses? */
468 {
471 }
472 /* Not a strided access. */
473 else
474 {
477 }
481 /* Is this an access in a group of loads providing strided access?
482 If so, add in the cost of the permutes. */
484 {
485 /* Uses an even and odd extract operations for each needed permute. */
491 group_size);
493 }
495 /* The loads themselves. */
497 {
499 {
506 }
508 {
509 /* Here, we assign an additional cost for the unaligned load. */
517 }
519 {
526 /* Unaligned software pipeline has a load of an address, an initial
527 load, and possibly a mask operation to "prime" the loop. However,
528 if this is an access in a group of loads, which provide strided
529 access, then the above cost should only be considered for one
530 access in the group. Inside the loop, there is a load op
531 and a realignment op. */
534 {
538 }
545 }
549 }
558 }
561 /* Function vect_get_new_vect_var.
563 Returns a name for a new variable. The current naming scheme appends the
564 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
565 the name of vectorizer generated variables, and appends that to NAME if
566 provided. */
568 static tree
570 {
572 tree new_vect_var;
575 {
587 }
591 else
594 /* Mark vector typed variable as a gimple register variable. */
599 }
602 /* Function vect_create_addr_base_for_vector_ref.
604 Create an expression that computes the address of the first memory location
605 that will be accessed for a data reference.
607 Input:
608 STMT: The statement containing the data reference.
609 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
610 OFFSET: Optional. If supplied, it is be added to the initial address.
612 Output:
613 1. Return an SSA_NAME whose value is the address of the memory location of
614 the first vector of the data reference.
615 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
616 these statement(s) which define the returned SSA_NAME.
618 FORNOW: We are only handling array accesses with step 1. */
620 static tree
623 tree offset)
624 {
629 tree vec_stmt;
636 /* Create base_offset */
645 {
647 tree step;
649 /* For interleaved access step we divide STEP by the size of the
650 interleaving group. */
655 else
664 }
666 /* base + base_offset */
668 base_offset);
672 /* addr_expr = addr_base */
684 {
687 }
689 }
692 /* Function vect_create_data_ref_ptr.
694 Create a new pointer to vector type (vp), that points to the first location
695 accessed in the loop by STMT, along with the def-use update chain to
696 appropriately advance the pointer through the loop iterations. Also set
697 aliasing information for the pointer. This vector pointer is used by the
698 callers to this function to create a memory reference expression for vector
699 load/store access.
701 Input:
702 1. STMT: a stmt that references memory. Expected to be of the form
703 GIMPLE_MODIFY_STMT <name, data-ref> or
704 GIMPLE_MODIFY_STMT <data-ref, name>.
705 2. BSI: block_stmt_iterator where new stmts can be added.
706 3. OFFSET (optional): an offset to be added to the initial address accessed
707 by the data-ref in STMT.
708 4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
709 pointing to the initial address.
710 5. TYPE: if not NULL indicates the required type of the data-ref
712 Output:
713 1. Declare a new ptr to vector_type, and have it point to the base of the
714 data reference (initial addressed accessed by the data reference).
715 For example, for vector of type V8HI, the following code is generated:
717 v8hi *vp;
718 vp = (v8hi *)initial_address;
720 if OFFSET is not supplied:
721 initial_address = &a[init];
722 if OFFSET is supplied:
723 initial_address = &a[init + OFFSET];
725 Return the initial_address in INITIAL_ADDRESS.
727 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
728 update the pointer in each iteration of the loop.
730 Return the increment stmt that updates the pointer in PTR_INCR.
732 3. Return the pointer. */
734 static tree
739 {
740 tree base_name;
745 tree vect_ptr_type;
746 tree vect_ptr;
747 tree tag;
748 tree new_temp;
749 tree vec_stmt;
752 basic_block new_bb;
753 tree vect_ptr_init;
759 {
772 }
774 /** (1) Create the new vector-pointer variable: **/
777 else
783 /** (2) Add aliasing information to the new vector-pointer:
784 (The points-to info (DR_PTR_INFO) may be defined later.) **/
789 /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
790 tag must be created with tag added to its may alias list. */
793 else
798 /** (3) Calculate the initial address the vector-pointer, and set
799 the vector-pointer to point to it before the loop: **/
801 /* Create: (&(base[init_val+offset]) in the loop preheader. */
803 offset);
809 /* Create: p = (vectype *) initial_base */
818 /** (4) Handle the updating of the vector-pointer inside the loop: **/
821 {
822 /* Copy the points-to information if it exists. */
826 }
827 else
828 {
829 block_stmt_iterator incr_bsi;
832 tree incr;
843 /* Copy the points-to information if it exists. */
845 {
848 }
855 }
856 }
859 /* Function bump_vector_ptr
861 Increment a pointer (to a vector type) by vector-size. Connect the new
862 increment stmt to the existing def-use update-chain of the pointer.
864 The pointer def-use update-chain before this function:
865 DATAREF_PTR = phi (p_0, p_2)
866 ....
867 PTR_INCR: p_2 = DATAREF_PTR + step
869 The pointer def-use update-chain after this function:
870 DATAREF_PTR = phi (p_0, p_2)
871 ....
872 NEW_DATAREF_PTR = DATAREF_PTR + vector_size
873 ....
874 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
876 Input:
877 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
878 in the loop.
879 PTR_INCR - the stmt that updates the pointer in each iteration of the loop.
880 The increment amount across iterations is also expected to be
881 vector_size.
882 BSI - location where the new update stmt is to be placed.
883 STMT - the original scalar memory-access stmt that is being vectorized.
885 Output: Return NEW_DATAREF_PTR as illustrated above.
887 */
889 static tree
891 tree stmt)
892 {
899 tree incr_stmt;
900 ssa_op_iter iter;
901 use_operand_p use_p;
902 tree new_dataref_ptr;
911 /* Update the vector-pointer's cross-iteration increment. */
913 {
918 else
920 }
922 /* Copy the points-to information if it exists. */
928 }
931 /* Function vect_create_destination_var.
933 Create a new temporary of type VECTYPE. */
935 static tree
937 {
938 tree vec_dest;
940 tree type;
955 }
958 /* Function vect_init_vector.
960 Insert a new stmt (INIT_STMT) that initializes a new vector variable with
961 the vector elements of VECTOR_VAR. Return the DEF of INIT_STMT. It will be
962 used in the vectorization of STMT. */
964 static tree
966 {
970 tree new_var;
971 tree init_stmt;
972 tree vec_oprnd;
973 edge pe;
974 tree new_temp;
975 basic_block new_bb;
989 {
992 }
996 }
999 /* Function get_initial_def_for_induction
1001 Input:
1002 IV_PHI - the initial value of the induction variable
1004 Output:
1005 Return a vector variable, initialized with the first VF values of
1006 the induction variable. E.g., for an iv with IV_PHI='X' and
1007 evolution S, for a vector of 4 units, we want to return:
1008 [X, X + S, X + 2*S, X + 3*S]. */
1010 static tree
1012 {
1020 basic_block new_bb;
1021 block_stmt_iterator bsi;
1023 tree access_fn;
1024 tree new_var;
1025 tree new_name;
1026 tree init_stmt;
1033 tree expr;
1035 tree stmts;
1037 block_stmt_iterator si;
1043 /* Find the first insertion point in the BB. */
1053 /* Create the vector that holds the initial_value of the induction. */
1059 {
1062 }
1067 {
1068 tree tmp;
1070 /* Create: new_name = new_name + step_expr */
1080 {
1083 }
1085 }
1090 /* Create the vector that holds the step of the induction. */
1100 /* Create the following def-use cycle:
1101 loop prolog:
1102 vec_init = [X, X+S, X+2*S, X+3*S]
1103 vec_step = [VF*S, VF*S, VF*S, VF*S]
1104 loop:
1105 vec_iv = PHI <vec_init, vec_loop>
1106 ...
1107 STMT
1108 ...
1109 vec_loop = vec_iv + vec_step; */
1111 /* Create the induction-phi that defines the induction-operand. */
1119 /* Create the iv update inside the loop */
1128 /* Set the arguments of the phi node: */
1133 /* In case the vectorization factor (VF) is bigger than the number
1134 of elements that we can fit in a vectype (nunits), we have to generate
1135 more than one vector stmt - i.e - we need to "unroll" the
1136 vector stmt by a factor VF/nunits. For more details see documentation
1137 in vectorizable_operation. */
1140 {
1141 stmt_vec_info prev_stmt_vinfo;
1143 /* Create the vector that holds the step of the induction. */
1155 {
1156 tree tmp;
1158 /* vec_i = vec_prev + vec_{step*nunits} */
1168 }
1169 }
1172 {
1177 }
1181 }
1184 /* Function vect_get_vec_def_for_operand.
1186 OP is an operand in STMT. This function returns a (vector) def that will be
1187 used in the vectorized stmt for STMT.
1189 In the case that OP is an SSA_NAME which is defined in the loop, then
1190 STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1192 In case OP is an invariant or constant, a new stmt that creates a vector def
1193 needs to be introduced. */
1195 static tree
1197 {
1198 tree vec_oprnd;
1199 tree vec_stmt;
1200 tree def_stmt;
1207 tree vec_inv;
1208 tree vec_cst;
1210 tree def;
1214 tree vector_type;
1217 {
1220 }
1225 {
1227 {
1230 }
1232 {
1235 }
1236 }
1239 {
1240 /* Case 1: operand is a constant. */
1242 {
1246 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1251 {
1253 }
1258 }
1260 /* Case 2: operand is defined outside the loop - loop invariant. */
1262 {
1266 /* Create 'vec_inv = {inv,inv,..,inv}' */
1271 {
1273 }
1275 /* FIXME: use build_constructor directly. */
1279 }
1281 /* Case 3: operand is defined inside the loop. */
1283 {
1287 /* Get the def from the vectorized stmt. */
1293 }
1295 /* Case 4: operand is defined by a loop header phi - reduction */
1297 {
1300 /* Get the def before the loop */
1303 }
1305 /* Case 5: operand is defined by loop-header phi - induction. */
1307 {
1310 /* Get the def before the loop */
1312 }
1316 }
1317 }
1320 /* Function vect_get_vec_def_for_stmt_copy
1322 Return a vector-def for an operand. This function is used when the
1323 vectorized stmt to be created (by the caller to this function) is a "copy"
1324 created in case the vectorized result cannot fit in one vector, and several
1325 copies of the vector-stmt are required. In this case the vector-def is
1326 retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1327 of the stmt that defines VEC_OPRND.
1328 DT is the type of the vector def VEC_OPRND.
1330 Context:
1331 In case the vectorization factor (VF) is bigger than the number
1332 of elements that can fit in a vectype (nunits), we have to generate
1333 more than one vector stmt to vectorize the scalar stmt. This situation
1334 arises when there are multiple data-types operated upon in the loop; the
1335 smallest data-type determines the VF, and as a result, when vectorizing
1336 stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1337 vector stmt (each computing a vector of 'nunits' results, and together
1338 computing 'VF' results in each iteration). This function is called when
1339 vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1340 which VF=16 and nunits=4, so the number of copies required is 4):
1342 scalar stmt: vectorized into: STMT_VINFO_RELATED_STMT
1344 S1: x = load VS1.0: vx.0 = memref0 VS1.1
1345 VS1.1: vx.1 = memref1 VS1.2
1346 VS1.2: vx.2 = memref2 VS1.3
1347 VS1.3: vx.3 = memref3
1349 S2: z = x + ... VSnew.0: vz0 = vx.0 + ... VSnew.1
1350 VSnew.1: vz1 = vx.1 + ... VSnew.2
1351 VSnew.2: vz2 = vx.2 + ... VSnew.3
1352 VSnew.3: vz3 = vx.3 + ...
1354 The vectorization of S1 is explained in vectorizable_load.
1355 The vectorization of S2:
1356 To create the first vector-stmt out of the 4 copies - VSnew.0 -
1357 the function 'vect_get_vec_def_for_operand' is called to
1358 get the relevant vector-def for each operand of S2. For operand x it
1359 returns the vector-def 'vx.0'.
1361 To create the remaining copies of the vector-stmt (VSnew.j), this
1362 function is called to get the relevant vector-def for each operand. It is
1363 obtained from the respective VS1.j stmt, which is recorded in the
1364 STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
1366 For example, to obtain the vector-def 'vx.1' in order to create the
1367 vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
1368 Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
1369 STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
1370 and return its def ('vx.1').
1371 Overall, to create the above sequence this function will be called 3 times:
1372 vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
1373 vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
1374 vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2); */
1376 static tree
1378 {
1379 tree vec_stmt_for_operand;
1380 stmt_vec_info def_stmt_info;
1382 /* Do nothing; can reuse same def. */
1394 }
1397 /* Function vect_finish_stmt_generation.
1399 Insert a new stmt. */
1401 static void
1404 {
1413 {
1416 }
1418 /* Make sure bsi points to the stmt that is being vectorized. */
1421 #ifdef USE_MAPPED_LOCATION
1423 #else
1425 #endif
1426 }
1429 /* Function get_initial_def_for_reduction
1431 Input:
1432 STMT - a stmt that performs a reduction operation in the loop.
1433 INIT_VAL - the initial value of the reduction variable
1435 Output:
1436 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
1437 of the reduction (used for adjusting the epilog - see below).
1438 Return a vector variable, initialized according to the operation that STMT
1439 performs. This vector will be used as the initial value of the
1440 vector of partial results.
1442 Option1 (adjust in epilog): Initialize the vector as follows:
1443 add: [0,0,...,0,0]
1444 mult: [1,1,...,1,1]
1445 min/max: [init_val,init_val,..,init_val,init_val]
1446 bit and/or: [init_val,init_val,..,init_val,init_val]
1447 and when necessary (e.g. add/mult case) let the caller know
1448 that it needs to adjust the result by init_val.
1450 Option2: Initialize the vector as follows:
1451 add: [0,0,...,0,init_val]
1452 mult: [1,1,...,1,init_val]
1453 min/max: [init_val,init_val,...,init_val]
1454 bit and/or: [init_val,init_val,...,init_val]
1455 and no adjustments are needed.
1457 For example, for the following code:
1459 s = init_val;
1460 for (i=0;i<n;i++)
1461 s = s + a[i];
1463 STMT is 's = s + a[i]', and the reduction variable is 's'.
1464 For a vector of 4 units, we want to return either [0,0,0,init_val],
1465 or [0,0,0,0] and let the caller know that it needs to adjust
1466 the result at the end by 'init_val'.
1468 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
1469 initialization vector is simpler (same element in all entries).
1470 A cost model should help decide between these two schemes. */
1472 static tree
1474 {
1480 tree vecdef;
1481 tree def_for_init;
1482 tree init_def;
1485 tree vector_type;
1491 {
1496 /* Create a vector of zeros for init_def. */
1499 else
1515 }
1518 }
1521 /* Function vect_create_epilog_for_reduction
1523 Create code at the loop-epilog to finalize the result of a reduction
1524 computation.
1526 VECT_DEF is a vector of partial results.
1527 REDUC_CODE is the tree-code for the epilog reduction.
1528 STMT is the scalar reduction stmt that is being vectorized.
1529 REDUCTION_PHI is the phi-node that carries the reduction computation.
1531 This function:
1532 1. Creates the reduction def-use cycle: sets the arguments for
1533 REDUCTION_PHI:
1534 The loop-entry argument is the vectorized initial-value of the reduction.
1535 The loop-latch argument is VECT_DEF - the vector of partial sums.
1536 2. "Reduces" the vector of partial results VECT_DEF into a single result,
1537 by applying the operation specified by REDUC_CODE if available, or by
1538 other means (whole-vector shifts or a scalar loop).
1539 The function also creates a new phi node at the loop exit to preserve
1540 loop-closed form, as illustrated below.
1542 The flow at the entry to this function:
1544 loop:
1545 vec_def = phi <null, null> # REDUCTION_PHI
1546 VECT_DEF = vector_stmt # vectorized form of STMT
1547 s_loop = scalar_stmt # (scalar) STMT
1548 loop_exit:
1549 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1550 use <s_out0>
1551 use <s_out0>
1553 The above is transformed by this function into:
1555 loop:
1556 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
1557 VECT_DEF = vector_stmt # vectorized form of STMT
1558 s_loop = scalar_stmt # (scalar) STMT
1559 loop_exit:
1560 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
1561 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
1562 v_out2 = reduce <v_out1>
1563 s_out3 = extract_field <v_out2, 0>
1564 s_out4 = adjust_result <s_out3>
1565 use <s_out4>
1566 use <s_out4>
1567 */
1569 static void
1572 {
1574 tree vectype;
1578 basic_block exit_bb;
1579 tree scalar_dest;
1580 tree scalar_type;
1581 tree new_phi;
1582 block_stmt_iterator exit_bsi;
1583 tree vec_dest;
1584 tree new_temp;
1585 tree new_name;
1586 tree epilog_stmt;
1590 tree scalar_initial_def;
1591 tree vec_initial_def;
1592 tree orig_name;
1593 imm_use_iterator imm_iter;
1594 use_operand_p use_p;
1596 tree reduction_op;
1597 tree orig_stmt;
1598 tree use_stmt;
1607 /*** 1. Create the reduction def-use cycle ***/
1609 /* 1.1 set the loop-entry arg of the reduction-phi: */
1610 /* For the case of reduction, vect_get_vec_def_for_operand returns
1611 the scalar def before the loop, that defines the initial value
1612 of the reduction variable. */
1617 /* 1.2 set the loop-latch arg for the reduction-phi: */
1621 {
1626 }
1629 /*** 2. Create epilog code
1630 The reduction epilog code operates across the elements of the vector
1631 of partial results computed by the vectorized loop.
1632 The reduction epilog code consists of:
1633 step 1: compute the scalar result in a vector (v_out2)
1634 step 2: extract the scalar result (s_out3) from the vector (v_out2)
1635 step 3: adjust the scalar result (s_out3) if needed.
1637 Step 1 can be accomplished using one the following three schemes:
1638 (scheme 1) using reduc_code, if available.
1639 (scheme 2) using whole-vector shifts, if available.
1640 (scheme 3) using a scalar loop. In this case steps 1+2 above are
1641 combined.
1643 The overall epilog code looks like this:
1645 s_out0 = phi <s_loop> # original EXIT_PHI
1646 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
1647 v_out2 = reduce <v_out1> # step 1
1648 s_out3 = extract_field <v_out2, 0> # step 2
1649 s_out4 = adjust_result <s_out3> # step 3
1651 (step 3 is optional, and step2 1 and 2 may be combined).
1652 Lastly, the uses of s_out0 are replaced by s_out4.
1654 ***/
1656 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
1657 v_out1 = phi <v_loop> */
1664 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
1665 (i.e. when reduc_code is not available) and in the final adjustment
1666 code (if needed). Also get the original scalar reduction variable as
1667 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
1668 represents a reduction pattern), the tree-code and scalar-def are
1669 taken from the original stmt that the pattern-stmt (STMT) replaces.
1670 Otherwise (it is a regular reduction) - the tree-code and scalar-def
1671 are taken from STMT. */
1675 {
1676 /* Regular reduction */
1678 }
1679 else
1680 {
1681 /* Reduction pattern */
1685 }
1693 /* 2.3 Create the reduction code, using one of the three schemes described
1694 above. */
1697 {
1698 tree tmp;
1700 /*** Case 1: Create:
1701 v_out2 = reduc_expr <v_out1> */
1714 }
1715 else
1716 {
1722 tree vec_temp;
1726 else
1729 /* Regardless of whether we have a whole vector shift, if we're
1730 emulating the operation via tree-vect-generic, we don't want
1731 to use it. Only the first round of the reduction is likely
1732 to still be profitable via emulation. */
1733 /* ??? It might be better to emit a reduction tree code here, so that
1734 tree-vect-generic can expand the first round via bit tricks. */
1737 else
1738 {
1742 }
1745 {
1746 /*** Case 2: Create:
1747 for (offset = VS/2; offset >= element_size; offset/=2)
1748 {
1749 Create: va' = vec_shift <va, offset>
1750 Create: va = vop <va, va'>
1751 } */
1762 {
1775 }
1778 }
1779 else
1780 {
1781 tree rhs;
1783 /*** Case 3: Create:
1784 s = extract_field <v_out2, 0>
1785 for (offset = element_size;
1786 offset < vector_size;
1787 offset += element_size;)
1788 {
1789 Create: s' = extract_field <v_out2, offset>
1790 Create: s = op <s, s'>
1791 } */
1799 bitsize_zero_node);
1809 {
1810 tree tmp;
1813 bitpos);
1826 }
1829 }
1830 }
1832 /* 2.4 Extract the final scalar result. Create:
1833 s_out3 = extract_field <v_out2, bitpos> */
1836 {
1837 tree rhs;
1846 else
1855 }
1857 /* 2.4 Adjust the final result by the initial value of the reduction
1858 variable. (When such adjustment is not needed, then
1859 'scalar_initial_def' is zero).
1861 Create:
1862 s_out4 = scalar_expr <s_out3, scalar_initial_def> */
1865 {
1871 }
1873 /* 2.6 Replace uses of s_out0 with uses of s_out3 */
1875 /* Find the loop-closed-use at the loop exit of the original scalar result.
1876 (The reduction result is expected to have two immediate uses - one at the
1877 latch block, and one at the loop exit). */
1880 {
1882 {
1885 }
1886 }
1887 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
1889 /* Replace the uses: */
1894 }
1897 /* Function vectorizable_reduction.
1899 Check if STMT performs a reduction operation that can be vectorized.
1900 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1901 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1902 Return FALSE if not a vectorizable STMT, TRUE otherwise.
1904 This function also handles reduction idioms (patterns) that have been
1905 recognized in advance during vect_pattern_recog. In this case, STMT may be
1906 of this form:
1907 X = pattern_expr (arg0, arg1, ..., X)
1908 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
1909 sequence that had been detected and replaced by the pattern-stmt (STMT).
1911 In some cases of reduction patterns, the type of the reduction variable X is
1912 different than the type of the other arguments of STMT.
1913 In such cases, the vectype that is used when transforming STMT into a vector
1914 stmt is different than the vectype that is used to determine the
1915 vectorization factor, because it consists of a different number of elements
1916 than the actual number of elements that are being operated upon in parallel.
1918 For example, consider an accumulation of shorts into an int accumulator.
1919 On some targets it's possible to vectorize this pattern operating on 8
1920 shorts at a time (hence, the vectype for purposes of determining the
1921 vectorization factor should be V8HI); on the other hand, the vectype that
1922 is used to create the vector form is actually V4SI (the type of the result).
1924 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
1925 indicates what is the actual level of parallelism (V8HI in the example), so
1926 that the right vectorization factor would be derived. This vectype
1927 corresponds to the type of arguments to the reduction stmt, and should *NOT*
1928 be used to create the vectorized stmt. The right vectype for the vectorized
1929 stmt is obtained from the type of the result X:
1930 get_vectype_for_scalar_type (TREE_TYPE (X))
1932 This means that, contrary to "regular" reductions (or "regular" stmts in
1933 general), the following equation:
1934 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
1935 does *NOT* necessarily hold for reduction patterns. */
1937 bool
1939 {
1940 tree vec_dest;
1941 tree scalar_dest;
1942 tree op;
1948 tree operation;
1956 tree new_phi;
1957 tree scalar_type;
1959 tree orig_stmt;
1960 stmt_vec_info orig_stmt_info;
1965 stmt_vec_info prev_stmt_info;
1966 tree reduc_def;
1972 /* 1. Is vectorizable reduction? */
1974 /* Not supportable if the reduction variable is used in the loop. */
1981 /* Make sure it was already recognized as a reduction computation. */
1985 /* 2. Has this been recognized as a reduction pattern?
1987 Check if STMT represents a pattern that has been recognized
1988 in earlier analysis stages. For stmts that represent a pattern,
1989 the STMT_VINFO_RELATED_STMT field records the last stmt in
1990 the original sequence that constitutes the pattern. */
1994 {
1999 }
2001 /* 3. Check the operands of the operation. The first operands are defined
2002 inside the loop body. The last operand is the reduction variable,
2003 which is defined by the loop-header-phi. */
2015 /* All uses but the last are expected to be defined in the loop.
2016 The last use is the reduction variable. */
2018 {
2027 }
2036 else
2042 /* 4. Supportable by target? */
2044 /* 4.1. check support for the operation in the loop */
2047 {
2051 }
2054 {
2063 }
2065 /* Worthwhile without SIMD support? */
2069 {
2073 }
2075 /* 4.2. Check support for the epilog operation.
2077 If STMT represents a reduction pattern, then the type of the
2078 reduction variable may be different than the type of the rest
2079 of the arguments. For example, consider the case of accumulation
2080 of shorts into an int accumulator; The original code:
2081 S1: int_a = (int) short_a;
2082 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
2084 was replaced with:
2085 STMT: int_acc = widen_sum <short_a, int_acc>
2087 This means that:
2088 1. The tree-code that is used to create the vector operation in the
2089 epilog code (that reduces the partial results) is not the
2090 tree-code of STMT, but is rather the tree-code of the original
2091 stmt from the pattern that STMT is replacing. I.e, in the example
2092 above we want to use 'widen_sum' in the loop, but 'plus' in the
2093 epilog.
2094 2. The type (mode) we use to check available target support
2095 for the vector operation to be created in the *epilog*, is
2096 determined by the type of the reduction variable (in the example
2097 above we'd check this: plus_optab[vect_int_mode]).
2098 However the type (mode) we use to check available target support
2099 for the vector operation to be created *inside the loop*, is
2100 determined by the type of the other arguments to STMT (in the
2101 example we'd check this: widen_sum_optab[vect_short_mode]).
2103 This is contrary to "regular" reductions, in which the types of all
2104 the arguments are the same as the type of the reduction variable.
2105 For "regular" reductions we can therefore use the same vector type
2106 (and also the same tree-code) when generating the epilog code and
2107 when generating the code inside the loop. */
2110 {
2111 /* This is a reduction pattern: get the vectype from the type of the
2112 reduction variable, and get the tree-code from orig_stmt. */
2116 }
2117 else
2118 {
2119 /* Regular reduction: use the same vectype and tree-code as used for
2120 the vector code inside the loop can be used for the epilog code. */
2122 }
2128 {
2132 }
2134 {
2138 }
2141 {
2145 }
2147 /** Transform. **/
2152 /* Create the destination vector */
2155 /* Create the reduction-phi that defines the reduction-operand. */
2158 /* In case the vectorization factor (VF) is bigger than the number
2159 of elements that we can fit in a vectype (nunits), we have to generate
2160 more than one vector stmt - i.e - we need to "unroll" the
2161 vector stmt by a factor VF/nunits. For more details see documentation
2162 in vectorizable_operation. */
2166 {
2167 /* Handle uses. */
2169 {
2173 {
2176 }
2178 /* Get the vector def for the reduction variable from the phi node */
2180 }
2181 else
2182 {
2188 /* Get the vector def for the reduction variable from the vectorized
2189 reduction operation generated in the previous iteration (j-1) */
2191 }
2193 /* Arguments are ready. create the new vector stmt. */
2196 else
2198 reduc_def);
2206 else
2209 }
2211 /* Finalize the reduction-phi (set it's arguments) and create the
2212 epilog reduction code. */
2215 }
2217 /* Checks if CALL can be vectorized in type VECTYPE. Returns
2218 a function declaration if the target has a vectorized version
2219 of the function, or NULL_TREE if the function cannot be vectorized. */
2221 tree
2223 {
2227 /* We only handle functions that do not read or clobber memory -- i.e.
2228 const or novops ones. */
2239 vectype_in);
2240 }
2242 /* Function vectorizable_call.
2244 Check if STMT performs a function call that can be vectorized.
2245 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2246 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2247 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2249 bool
2251 {
2252 tree vec_dest;
2253 tree scalar_dest;
2254 tree operation;
2264 tree new_stmt;
2266 call_expr_arg_iterator iter;
2267 tree vargs;
2276 /* FORNOW: not yet supported. */
2278 {
2282 }
2284 /* Is STMT a vectorizable call? */
2295 /* Process function arguments. */
2299 {
2300 /* Bail out if the function has more than two arguments, we
2301 do not have interesting builtin functions to vectorize with
2302 more than two arguments. */
2306 /* We can only handle calls with arguments of the same type. */
2309 {
2313 }
2317 {
2321 }
2324 }
2326 /* No arguments is also not good. */
2337 /* FORNOW */
2344 else
2347 /* For now, we only vectorize functions if a target specific builtin
2348 is available. TODO -- in some cases, it might be profitable to
2349 insert the calls for pieces of the vector, in order to be able
2350 to vectorize other operations in the loop. */
2353 {
2358 }
2364 else
2367 /* Sanity check: make sure that at least one copy of the vectorized stmt
2368 needs to be generated. */
2372 {
2378 }
2380 /** Transform. **/
2385 /* Handle def. */
2391 {
2394 {
2395 /* Build argument list for the vectorized call. */
2396 /* FIXME: Rewrite this so that it doesn't
2397 construct a temporary list. */
2401 {
2403 vec_oprnd0
2405 else
2406 vec_oprnd0
2412 }
2424 else
2428 }
2434 {
2435 /* Build argument list for the vectorized call. */
2436 /* FIXME: Rewrite this so that it doesn't
2437 construct a temporary list. */
2441 {
2443 {
2444 vec_oprnd0
2446 vec_oprnd1
2448 }
2449 else
2450 {
2451 vec_oprnd0
2453 vec_oprnd1
2455 }
2461 }
2473 else
2477 }
2484 /* No current target implements this case. */
2486 }
2488 /* The call in STMT might prevent it from being removed in dce.
2489 We however cannot remove it here, due to the way the ssa name
2490 it defines is mapped to the new definition. So just replace
2491 rhs of the statement with something harmless. */
2497 }
2500 /* Function vect_gen_widened_results_half
2502 Create a vector stmt whose code, type, number of arguments, and result
2503 variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are
2504 VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
2505 In the case that CODE is a CALL_EXPR, this means that a call to DECL
2506 needs to be created (DECL is a function-decl of a target-builtin).
2507 STMT is the original scalar stmt that we are vectorizing. */
2509 static tree
2513 tree stmt)
2514 {
2515 tree expr;
2516 tree new_stmt;
2517 tree new_temp;
2518 tree sym;
2519 ssa_op_iter iter;
2521 /* Generate half of the widened result: */
2523 {
2524 /* Target specific support */
2527 else
2529 }
2530 else
2531 {
2532 /* Generic support */
2536 else
2538 }
2545 {
2547 {
2551 }
2552 }
2555 }
2558 /* Function vectorizable_conversion.
2560 Check if STMT performs a conversion operation, that can be vectorized.
2561 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2562 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2563 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2565 bool
2568 {
2569 tree vec_dest;
2570 tree scalar_dest;
2571 tree operation;
2572 tree op0;
2578 tree new_temp;
2581 tree new_stmt;
2582 stmt_vec_info prev_stmt_info;
2587 tree expr;
2589 tree builtin_decl;
2592 /* Is STMT a vectorizable conversion? */
2601 {
2602 /* FORNOW: not yet supported. */
2606 }
2619 /* Check types of lhs and rhs */
2630 /* FORNOW */
2637 else
2643 /* Bail out if the types are both integral or non-integral */
2650 else
2653 /* Sanity check: make sure that at least one copy of the vectorized stmt
2654 needs to be generated. */
2657 /* Check the operands of the operation. */
2659 {
2663 }
2665 /* Supportable by target? */
2675 {
2679 }
2685 {
2688 }
2690 /** Transform. **/
2694 /* Handle def. */
2699 {
2702 {
2703 tree sym;
2704 ssa_op_iter iter;
2708 else
2711 builtin_decl =
2715 /* Arguments are ready. create the new vector stmt. */
2721 {
2725 }
2729 else
2732 }
2736 /* In case the vectorization factor (VF) is bigger than the number
2737 of elements that we can fit in a vectype (nunits), we have to
2738 generate more than one vector stmt - i.e - we need to "unroll"
2739 the vector stmt by a factor VF/nunits. */
2741 {
2744 else
2749 /* Generate first half of the widened result: */
2750 new_stmt
2756 else
2760 /* Generate second half of the widened result: */
2761 new_stmt
2767 }
2771 /* In case the vectorization factor (VF) is bigger than the number
2772 of elements that we can fit in a vectype (nunits), we have to
2773 generate more than one vector stmt - i.e - we need to "unroll"
2774 the vector stmt by a factor VF/nunits. */
2776 {
2777 /* Handle uses. */
2779 {
2782 }
2783 else
2784 {
2787 }
2789 /* Arguments are ready. Create the new vector stmt. */
2798 else
2802 }
2805 }
2807 }
2810 /* Function vectorizable_assignment.
2812 Check if STMT performs an assignment (copy) that can be vectorized.
2813 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2814 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2815 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2817 bool
2819 {
2820 tree vec_dest;
2821 tree scalar_dest;
2822 tree op;
2823 tree vec_oprnd;
2827 tree new_temp;
2843 /* FORNOW: not yet supported. */
2845 {
2849 }
2851 /* Is vectorizable assignment? */
2861 {
2865 }
2868 {
2874 }
2876 /** Transform. **/
2880 /* Handle def. */
2883 /* Handle use. */
2887 /* Arguments are ready. create the new vector stmt. */
2894 }
2897 /* Function vect_min_worthwhile_factor.
2899 For a loop where we could vectorize the operation indicated by CODE,
2900 return the minimum vectorization factor that makes it worthwhile
2901 to use generic vectors. */
2902 static int
2904 {
2906 {
2920 }
2921 }
2924 /* Function vectorizable_induction
2926 Check if PHI performs an induction computation that can be vectorized.
2927 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
2928 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
2929 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2931 bool
2934 {
2940 tree vec_def;
2950 {
2951 /* FORNOW: not yet supported. */
2955 }
2961 {
2967 }
2969 /** Transform. **/
2977 }
2980 /* Function vectorizable_operation.
2982 Check if STMT performs a binary or unary operation that can be vectorized.
2983 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2984 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2985 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
2987 bool
2989 {
2990 tree vec_dest;
2991 tree scalar_dest;
2992 tree operation;
3000 tree new_temp;
3002 optab optab;
3007 tree new_stmt;
3008 stmt_vec_info prev_stmt_info;
3011 tree vectype_out;
3023 /* FORNOW: not yet supported. */
3025 {
3029 }
3031 /* Is STMT a vectorizable binary/unary operation? */
3047 /* For pointer addition, we should use the normal plus for
3048 the vector addition. */
3054 /* Support only unary or binary operations. */
3057 {
3061 }
3065 {
3069 }
3072 {
3075 {
3079 }
3080 }
3082 /* Supportable by target? */
3084 {
3088 }
3092 {
3101 }
3103 /* Worthwhile without SIMD support? */
3107 {
3111 }
3114 {
3115 /* FORNOW: not yet supported. */
3119 /* Invariant argument is needed for a vector shift
3120 by a scalar shift operand. */
3125 {
3129 }
3130 }
3133 {
3139 }
3141 /** Transform. **/
3146 /* Handle def. */
3149 /* In case the vectorization factor (VF) is bigger than the number
3150 of elements that we can fit in a vectype (nunits), we have to generate
3151 more than one vector stmt - i.e - we need to "unroll" the
3152 vector stmt by a factor VF/nunits. In doing so, we record a pointer
3153 from one copy of the vector stmt to the next, in the field
3154 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3155 stages to find the correct vector defs to be used when vectorizing
3156 stmts that use the defs of the current stmt. The example below illustrates
3157 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3158 4 vectorized stmts):
3160 before vectorization:
3161 RELATED_STMT VEC_STMT
3162 S1: x = memref - -
3163 S2: z = x + 1 - -
3165 step 1: vectorize stmt S1 (done in vectorizable_load. See more details
3166 there):
3167 RELATED_STMT VEC_STMT
3168 VS1_0: vx0 = memref0 VS1_1 -
3169 VS1_1: vx1 = memref1 VS1_2 -
3170 VS1_2: vx2 = memref2 VS1_3 -
3171 VS1_3: vx3 = memref3 - -
3172 S1: x = load - VS1_0
3173 S2: z = x + 1 - -
3175 step2: vectorize stmt S2 (done here):
3176 To vectorize stmt S2 we first need to find the relevant vector
3177 def for the first operand 'x'. This is, as usual, obtained from
3178 the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
3179 that defines 'x' (S1). This way we find the stmt VS1_0, and the
3180 relevant vector def 'vx0'. Having found 'vx0' we can generate
3181 the vector stmt VS2_0, and as usual, record it in the
3182 STMT_VINFO_VEC_STMT of stmt S2.
3183 When creating the second copy (VS2_1), we obtain the relevant vector
3184 def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
3185 stmt VS1_0. This way we find the stmt VS1_1 and the relevant
3186 vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
3187 pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
3188 Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
3189 chain of stmts and pointers:
3190 RELATED_STMT VEC_STMT
3191 VS1_0: vx0 = memref0 VS1_1 -
3192 VS1_1: vx1 = memref1 VS1_2 -
3193 VS1_2: vx2 = memref2 VS1_3 -
3194 VS1_3: vx3 = memref3 - -
3195 S1: x = load - VS1_0
3196 VS2_0: vz0 = vx0 + v1 VS2_1 -
3197 VS2_1: vz1 = vx1 + v1 VS2_2 -
3198 VS2_2: vz2 = vx2 + v1 VS2_3 -
3199 VS2_3: vz3 = vx3 + v1 - -
3200 S2: z = x + 1 - VS2_0 */
3204 {
3205 /* Handle uses. */
3207 {
3210 {
3212 {
3213 /* Vector shl and shr insn patterns can be defined with
3214 scalar operand 2 (shift operand). In this case, use
3215 constant or loop invariant op1 directly, without
3216 extending it to vector mode first. */
3219 {
3223 }
3224 }
3227 }
3228 }
3229 else
3230 {
3234 }
3236 /* Arguments are ready. create the new vector stmt. */
3241 else
3250 else
3253 }
3256 }
3259 /* Function vectorizable_type_demotion
3261 Check if STMT performs a binary or unary operation that involves
3262 type demotion, and if it can be vectorized.
3263 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3264 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3265 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3267 bool
3270 {
3271 tree vec_dest;
3272 tree scalar_dest;
3273 tree operation;
3274 tree op0;
3279 tree new_temp;
3282 tree new_stmt;
3283 stmt_vec_info prev_stmt_info;
3286 tree vectype_out;
3289 tree expr;
3290 tree vectype_in;
3298 /* FORNOW: not yet supported. */
3300 {
3304 }
3306 /* Is STMT a vectorizable type-demotion operation? */
3338 /* Check the operands of the operation. */
3340 {
3344 }
3346 /* Supportable by target? */
3353 {
3359 }
3361 /** Transform. **/
3364 ncopies);
3366 /* Handle def. */
3369 /* In case the vectorization factor (VF) is bigger than the number
3370 of elements that we can fit in a vectype (nunits), we have to generate
3371 more than one vector stmt - i.e - we need to "unroll" the
3372 vector stmt by a factor VF/nunits. */
3375 {
3376 /* Handle uses. */
3378 {
3381 }
3382 else
3383 {
3386 }
3388 /* Arguments are ready. Create the new vector stmt. */
3397 else
3401 }
3405 }
3408 /* Function vectorizable_type_promotion
3410 Check if STMT performs a binary or unary operation that involves
3411 type promotion, and if it can be vectorized.
3412 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3413 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3414 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3416 bool
3419 {
3420 tree vec_dest;
3421 tree scalar_dest;
3422 tree operation;
3432 tree new_stmt;
3433 stmt_vec_info prev_stmt_info;
3436 tree vectype_out;
3439 tree vectype_in;
3447 /* FORNOW: not yet supported. */
3449 {
3453 }
3455 /* Is STMT a vectorizable type-promotion operation? */
3488 /* Check the operands of the operation. */
3490 {
3494 }
3498 {
3501 {
3505 }
3506 }
3508 /* Supportable by target? */
3516 {
3522 }
3524 /** Transform. **/
3528 ncopies);
3530 /* Handle def. */
3533 /* In case the vectorization factor (VF) is bigger than the number
3534 of elements that we can fit in a vectype (nunits), we have to generate
3535 more than one vector stmt - i.e - we need to "unroll" the
3536 vector stmt by a factor VF/nunits. */
3540 {
3541 /* Handle uses. */
3543 {
3547 }
3548 else
3549 {
3553 }
3555 /* Arguments are ready. Create the new vector stmt. We are creating
3556 two vector defs because the widened result does not fit in one vector.
3557 The vectorized stmt can be expressed as a call to a taregt builtin,
3558 or a using a tree-code. */
3559 /* Generate first half of the widened result: */
3564 else
3568 /* Generate second half of the widened result: */
3574 }
3578 }
3581 /* Function vect_strided_store_supported.
3583 Returns TRUE is INTERLEAVE_HIGH and INTERLEAVE_LOW operations are supported,
3584 and FALSE otherwise. */
3586 static bool
3588 {
3594 /* Check that the operation is supported. */
3596 vectype);
3598 vectype);
3600 {
3604 }
3607 == CODE_FOR_nothing
3610 {
3614 }
3616 }
3619 /* Function vect_permute_store_chain.
3621 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
3622 a power of 2, generate interleave_high/low stmts to reorder the data
3623 correctly for the stores. Return the final references for stores in
3624 RESULT_CHAIN.
3626 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
3627 The input is 4 vectors each containing 8 elements. We assign a number to each
3628 element, the input sequence is:
3630 1st vec: 0 1 2 3 4 5 6 7
3631 2nd vec: 8 9 10 11 12 13 14 15
3632 3rd vec: 16 17 18 19 20 21 22 23
3633 4th vec: 24 25 26 27 28 29 30 31
3635 The output sequence should be:
3637 1st vec: 0 8 16 24 1 9 17 25
3638 2nd vec: 2 10 18 26 3 11 19 27
3639 3rd vec: 4 12 20 28 5 13 21 30
3640 4th vec: 6 14 22 30 7 15 23 31
3642 i.e., we interleave the contents of the four vectors in their order.
3644 We use interleave_high/low instructions to create such output. The input of
3645 each interleave_high/low operation is two vectors:
3646 1st vec 2nd vec
3647 0 1 2 3 4 5 6 7
3648 the even elements of the result vector are obtained left-to-right from the
3649 high/low elements of the first vector. The odd elements of the result are
3650 obtained left-to-right from the high/low elements of the second vector.
3651 The output of interleave_high will be: 0 4 1 5
3652 and of interleave_low: 2 6 3 7
3655 The permutation is done in log LENGTH stages. In each stage interleave_high
3656 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
3657 where the first argument is taken from the first half of DR_CHAIN and the
3658 second argument from it's second half.
3659 In our example,
3661 I1: interleave_high (1st vec, 3rd vec)
3662 I2: interleave_low (1st vec, 3rd vec)
3663 I3: interleave_high (2nd vec, 4th vec)
3664 I4: interleave_low (2nd vec, 4th vec)
3666 The output for the first stage is:
3668 I1: 0 16 1 17 2 18 3 19
3669 I2: 4 20 5 21 6 22 7 23
3670 I3: 8 24 9 25 10 26 11 27
3671 I4: 12 28 13 29 14 30 15 31
3673 The output of the second stage, i.e. the final result is:
3675 I1: 0 8 16 24 1 9 17 25
3676 I2: 2 10 18 26 3 11 19 27
3677 I3: 4 12 20 28 5 13 21 30
3678 I4: 6 14 22 30 7 15 23 31. */
3680 static bool
3683 tree stmt,
3686 {
3698 /* Check that the operation is supported. */
3705 {
3707 {
3711 /* Create interleaving stmt:
3712 in the case of big endian:
3713 high = interleave_high (vect1, vect2)
3714 and in the case of little endian:
3715 high = interleave_low (vect1, vect2). */
3721 else
3729 /* Create interleaving stmt:
3730 in the case of big endian:
3731 low = interleave_low (vect1, vect2)
3732 and in the case of little endian:
3733 low = interleave_high (vect1, vect2). */
3739 else
3746 }
3748 }
3750 }
3753 /* Function vectorizable_store.
3755 Check if STMT defines a non scalar data-ref (array/pointer/structure) that
3756 can be vectorized.
3757 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3758 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3759 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3761 bool
3763 {
3764 tree scalar_dest;
3765 tree data_ref;
3766 tree op;
3773 tree dummy;
3775 ssa_op_iter iter;
3776 def_operand_p def_p;
3797 {
3801 }
3803 /* Is vectorizable store? */
3816 {
3820 }
3823 /* FORNOW. In some cases can vectorize even if data-type not supported
3824 (e.g. - array initialization with 0). */
3832 {
3836 }
3839 {
3843 }
3845 /** Transform. **/
3848 {
3855 /* We vectorize all the stmts of the interleaving group when we
3856 reach the last stmt in the group. */
3859 {
3862 }
3863 }
3864 else
3865 {
3869 }
3881 /* In case the vectorization factor (VF) is bigger than the number
3882 of elements that we can fit in a vectype (nunits), we have to generate
3883 more than one vector stmt - i.e - we need to "unroll" the
3884 vector stmt by a factor VF/nunits. For more details see documentation in
3885 vect_get_vec_def_for_copy_stmt. */
3887 /* In case of interleaving (non-unit strided access):
3889 S1: &base + 2 = x2
3890 S2: &base = x0
3891 S3: &base + 1 = x1
3892 S4: &base + 3 = x3
3894 We create vectorized stores starting from base address (the access of the
3895 first stmt in the chain (S2 in the above example), when the last store stmt
3896 of the chain (S4) is reached:
3898 VS1: &base = vx2
3899 VS2: &base + vec_size*1 = vx0
3900 VS3: &base + vec_size*2 = vx1
3901 VS4: &base + vec_size*3 = vx3
3903 Then permutation statements are generated:
3905 VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
3906 VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
3907 ...
3909 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3910 (the order of the data-refs in the output of vect_permute_store_chain
3911 corresponds to the order of scalar stmts in the interleaving chain - see
3912 the documentation of vect_permute_store_chain()).
3914 In case of both multiple types and interleaving, above vector stores and
3915 permutation stmts are created for every copy. The result vector stmts are
3916 put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3917 STMT_VINFO_RELATED_STMT for the next copies.
3918 */
3922 {
3923 tree new_stmt;
3924 tree ptr_incr;
3927 {
3928 /* For interleaved stores we collect vectorized defs for all the
3929 stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then used
3930 as an input to vect_permute_store_chain(), and OPRNDS as an input
3931 to vect_get_vec_def_for_stmt_copy() for the next copy.
3932 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3933 OPRNDS are of size 1. */
3936 {
3937 /* Since gaps are not supported for interleaved stores, GROUP_SIZE
3938 is the exact number of stmts in the chain. Therefore, NEXT_STMT
3939 can't be NULL_TREE. In case that there is no interleaving,
3940 GROUP_SIZE is 1, and only one iteration of the loop will be
3941 executed. */
3948 }
3952 }
3953 else
3954 {
3955 /* For interleaved stores we created vectorized defs for all the
3956 defs stored in OPRNDS in the previous iteration (previous copy).
3957 DR_CHAIN is then used as an input to vect_permute_store_chain(),
3958 and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
3959 next copy.
3960 If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3961 OPRNDS are of size 1. */
3963 {
3968 }
3970 }
3973 {
3975 /* Permute. */
3979 }
3983 {
3984 /* For strided stores vectorized defs are interleaved in
3985 vect_permute_store_chain(). */
3990 /* Arguments are ready. Create the new vector stmt. */
3994 /* Set the VDEFs for the vector pointer. If this virtual def
3995 has a use outside the loop and a loop peel is performed
3996 then the def may be renamed by the peel. Mark it for
3997 renaming so the later use will also be renamed. */
4000 {
4001 /* The original store is deleted so the same SSA_NAMEs
4002 can be used. */
4004 {
4007 }
4010 }
4011 else
4012 {
4013 /* Create new names for all the definitions created by COPY and
4014 add replacement mappings for each new name. */
4016 {
4019 }
4022 }
4028 /* Bump the vector pointer. */
4030 }
4031 }
4034 }
4037 /* Function vect_setup_realignment
4039 This function is called when vectorizing an unaligned load using
4040 the dr_unaligned_software_pipeline scheme.
4041 This function generates the following code at the loop prolog:
4043 p = initial_addr;
4044 msq_init = *(floor(p)); # prolog load
4045 realignment_token = call target_builtin;
4046 loop:
4047 msq = phi (msq_init, ---)
4049 The code above sets up a new (vector) pointer, pointing to the first
4050 location accessed by STMT, and a "floor-aligned" load using that pointer.
4051 It also generates code to compute the "realignment-token" (if the relevant
4052 target hook was defined), and creates a phi-node at the loop-header bb
4053 whose arguments are the result of the prolog-load (created by this
4054 function) and the result of a load that takes place in the loop (to be
4055 created by the caller to this function).
4056 The caller to this function uses the phi-result (msq) to create the
4057 realignment code inside the loop, and sets up the missing phi argument,
4058 as follows:
4060 loop:
4061 msq = phi (msq_init, lsq)
4062 lsq = *(floor(p')); # load in loop
4063 result = realign_load (msq, lsq, realignment_token);
4065 Input:
4066 STMT - (scalar) load stmt to be vectorized. This load accesses
4067 a memory location that may be unaligned.
4068 BSI - place where new code is to be inserted.
4070 Output:
4071 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4072 target hook, if defined.
4073 Return value - the result of the loop-header phi node. */
4075 static tree
4078 {
4085 tree vec_dest;
4086 tree init_addr;
4087 tree inc;
4088 tree ptr;
4089 tree data_ref;
4090 tree new_stmt;
4091 basic_block new_bb;
4092 tree msq_init;
4093 tree new_temp;
4094 tree phi_stmt;
4095 tree msq;
4097 /* 1. Create msq_init = *(floor(p1)) in the loop preheader */
4100 NULL_TREE);
4111 /* 2. Create permutation mask, if required, in loop preheader. */
4113 {
4114 tree builtin_decl;
4127 /* The result of the CALL_EXPR to this builtin is determined from
4128 the value of the parameter and no global variables are touched
4129 which makes the builtin a "const" function. Requiring the
4130 builtin to have the "const" attribute makes it unnecessary
4131 to call mark_call_clobbered. */
4133 }
4135 /* 3. Create msq = phi <msq_init, lsq> in loop */
4143 }
4146 /* Function vect_strided_load_supported.
4148 Returns TRUE is EXTRACT_EVEN and EXTRACT_ODD operations are supported,
4149 and FALSE otherwise. */
4151 static bool
4153 {
4161 {
4165 }
4168 {
4172 }
4176 {
4180 }
4183 {
4187 }
4189 }
4192 /* Function vect_permute_load_chain.
4194 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
4195 a power of 2, generate extract_even/odd stmts to reorder the input data
4196 correctly. Return the final references for loads in RESULT_CHAIN.
4198 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4199 The input is 4 vectors each containing 8 elements. We assign a number to each
4200 element, the input sequence is:
4202 1st vec: 0 1 2 3 4 5 6 7
4203 2nd vec: 8 9 10 11 12 13 14 15
4204 3rd vec: 16 17 18 19 20 21 22 23
4205 4th vec: 24 25 26 27 28 29 30 31
4207 The output sequence should be:
4209 1st vec: 0 4 8 12 16 20 24 28
4210 2nd vec: 1 5 9 13 17 21 25 29
4211 3rd vec: 2 6 10 14 18 22 26 30
4212 4th vec: 3 7 11 15 19 23 27 31
4214 i.e., the first output vector should contain the first elements of each
4215 interleaving group, etc.
4217 We use extract_even/odd instructions to create such output. The input of each
4218 extract_even/odd operation is two vectors
4219 1st vec 2nd vec
4220 0 1 2 3 4 5 6 7
4222 and the output is the vector of extracted even/odd elements. The output of
4223 extract_even will be: 0 2 4 6
4224 and of extract_odd: 1 3 5 7
4227 The permutation is done in log LENGTH stages. In each stage extract_even and
4228 extract_odd stmts are created for each pair of vectors in DR_CHAIN in their
4229 order. In our example,
4231 E1: extract_even (1st vec, 2nd vec)
4232 E2: extract_odd (1st vec, 2nd vec)
4233 E3: extract_even (3rd vec, 4th vec)
4234 E4: extract_odd (3rd vec, 4th vec)
4236 The output for the first stage will be:
4238 E1: 0 2 4 6 8 10 12 14
4239 E2: 1 3 5 7 9 11 13 15
4240 E3: 16 18 20 22 24 26 28 30
4241 E4: 17 19 21 23 25 27 29 31
4243 In order to proceed and create the correct sequence for the next stage (or
4244 for the correct output, if the second stage is the last one, as in our
4245 example), we first put the output of extract_even operation and then the
4246 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
4247 The input for the second stage is:
4249 1st vec (E1): 0 2 4 6 8 10 12 14
4250 2nd vec (E3): 16 18 20 22 24 26 28 30
4251 3rd vec (E2): 1 3 5 7 9 11 13 15
4252 4th vec (E4): 17 19 21 23 25 27 29 31
4254 The output of the second stage:
4256 E1: 0 4 8 12 16 20 24 28
4257 E2: 2 6 10 14 18 22 26 30
4258 E3: 1 5 9 13 17 21 25 29
4259 E4: 3 7 11 15 19 23 27 31
4261 And RESULT_CHAIN after reordering:
4263 1st vec (E1): 0 4 8 12 16 20 24 28
4264 2nd vec (E3): 1 5 9 13 17 21 25 29
4265 3rd vec (E2): 2 6 10 14 18 22 26 30
4266 4th vec (E4): 3 7 11 15 19 23 27 31. */
4268 static bool
4271 tree stmt,
4274 {
4277 tree tmp;
4281 /* Check that the operation is supported. */
4287 {
4289 {
4293 /* data_ref = permute_even (first_data_ref, second_data_ref); */
4309 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
4323 }
4325 }
4327 }
4330 /* Function vect_transform_strided_load.
4332 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
4333 to perform their permutation and ascribe the result vectorized statements to
4334 the scalar statements.
4335 */
4337 static bool
4340 {
4346 tree tmp_data_ref;
4348 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
4349 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
4350 vectors, that are ready for vector computation. */
4352 /* Permute. */
4356 /* Put a permuted data-ref in the VECTORIZED_STMT field.
4357 Since we scan the chain starting from it's first node, their order
4358 corresponds the order of data-refs in RESULT_CHAIN. */
4362 {
4366 /* Skip the gaps. Loads created for the gaps will be removed by dead
4367 code elimination pass later.
4368 DR_GROUP_GAP is the number of steps in elements from the previous
4369 access (if there is no gap DR_GROUP_GAP is 1). We skip loads that
4370 correspond to the gaps.
4371 */
4373 {
4374 gap_count++;
4376 }
4379 {
4381 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
4382 copies, and we put the new vector statement in the first available
4383 RELATED_STMT. */
4386 else
4387 {
4392 {
4395 }
4397 }
4400 /* If NEXT_STMT accesses the same DR as the previous statement,
4401 put the same TMP_DATA_REF as its vectorized statement; otherwise
4402 get the next data-ref from RESULT_CHAIN. */
4405 }
4406 }
4408 }
4411 /* vectorizable_load.
4413 Check if STMT reads a non scalar data-ref (array/pointer/structure) that
4414 can be vectorized.
4415 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4416 stmt to replace it, put it in VEC_STMT, and insert it at BSI.
4417 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4419 bool
4421 {
4422 tree scalar_dest;
4425 tree op;
4427 stmt_vec_info prev_stmt_info;
4432 tree new_temp;
4435 tree dummy;
4438 tree ptr_incr;
4448 tree first_stmt;
4456 /* FORNOW: not yet supported. */
4458 {
4462 }
4464 /* Is vectorizable load? */
4483 /* FORNOW. In some cases can vectorize even if data-type not supported
4484 (e.g. - data copies). */
4486 {
4490 }
4492 /* Check if the load is a part of an interleaving chain. */
4494 {
4497 /* Check if interleaving is supported. */
4500 }
4503 {
4507 }
4512 /** Transform. **/
4515 {
4517 /* Check if the chain of loads is already vectorized. */
4519 {
4522 }
4526 }
4527 else
4528 {
4532 }
4538 /* In case the vectorization factor (VF) is bigger than the number
4539 of elements that we can fit in a vectype (nunits), we have to generate
4540 more than one vector stmt - i.e - we need to "unroll" the
4541 vector stmt by a factor VF/nunits. In doing so, we record a pointer
4542 from one copy of the vector stmt to the next, in the field
4543 STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
4544 stages to find the correct vector defs to be used when vectorizing
4545 stmts that use the defs of the current stmt. The example below illustrates
4546 the vectorization process when VF=16 and nunits=4 (i.e - we need to create
4547 4 vectorized stmts):
4549 before vectorization:
4550 RELATED_STMT VEC_STMT
4551 S1: x = memref - -
4552 S2: z = x + 1 - -
4554 step 1: vectorize stmt S1:
4555 We first create the vector stmt VS1_0, and, as usual, record a
4556 pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
4557 Next, we create the vector stmt VS1_1, and record a pointer to
4558 it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
4559 Similarly, for VS1_2 and VS1_3. This is the resulting chain of
4560 stmts and pointers:
4561 RELATED_STMT VEC_STMT
4562 VS1_0: vx0 = memref0 VS1_1 -
4563 VS1_1: vx1 = memref1 VS1_2 -
4564 VS1_2: vx2 = memref2 VS1_3 -
4565 VS1_3: vx3 = memref3 - -
4566 S1: x = load - VS1_0
4567 S2: z = x + 1 - -
4569 See in documentation in vect_get_vec_def_for_stmt_copy for how the
4570 information we recorded in RELATED_STMT field is used to vectorize
4571 stmt S2. */
4573 /* In case of interleaving (non-unit strided access):
4575 S1: x2 = &base + 2
4576 S2: x0 = &base
4577 S3: x1 = &base + 1
4578 S4: x3 = &base + 3
4580 Vectorized loads are created in the order of memory accesses
4581 starting from the access of the first stmt of the chain:
4583 VS1: vx0 = &base
4584 VS2: vx1 = &base + vec_size*1
4585 VS3: vx3 = &base + vec_size*2
4586 VS4: vx4 = &base + vec_size*3
4588 Then permutation statements are generated:
4590 VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
4591 VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
4592 ...
4594 And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
4595 (the order of the data-refs in the output of vect_permute_load_chain
4596 corresponds to the order of scalar stmts in the interleaving chain - see
4597 the documentation of vect_permute_load_chain()).
4598 The generation of permutation stmts and recording them in
4599 STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
4601 In case of both multiple types and interleaving, the vector loads and
4602 permutation stmts above are created for every copy. The result vector stmts
4603 are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
4604 STMT_VINFO_RELATED_STMT for the next copies. */
4606 /* If the data reference is aligned (dr_aligned) or potentially unaligned
4607 on a target that supports unaligned accesses (dr_unaligned_supported)
4608 we generate the following code:
4609 p = initial_addr;
4610 indx = 0;
4611 loop {
4612 p = p + indx * vectype_size;
4613 vec_dest = *(p);
4614 indx = indx + 1;
4615 }
4617 Otherwise, the data reference is potentially unaligned on a target that
4618 does not support unaligned accesses (dr_unaligned_software_pipeline) -
4619 then generate the following code, in which the data in each iteration is
4620 obtained by two vector loads, one from the previous iteration, and one
4621 from the current iteration:
4622 p1 = initial_addr;
4623 msq_init = *(floor(p1))
4624 p2 = initial_addr + VS - 1;
4625 realignment_token = call target_builtin;
4626 indx = 0;
4627 loop {
4628 p2 = p2 + indx * vectype_size
4629 lsq = *(floor(p2))
4630 vec_dest = realign_load (msq, lsq, realignment_token)
4631 indx = indx + 1;
4632 msq = lsq;
4633 } */
4636 {
4640 }
4644 {
4645 /* 1. Create the vector pointer update chain. */
4649 else
4653 {
4654 /* 2. Create the vector-load in the loop. */
4656 {
4662 {
4668 data_ref =
4671 }
4678 }
4687 /* 3. Handle explicit realignment if necessary/supported. */
4689 {
4690 /* Create in loop:
4691 <vec_dest = realign_load (msq, lsq, realignment_token)> */
4696 new_stmt =
4705 }
4710 }
4713 {
4718 }
4719 else
4720 {
4723 else
4726 }
4727 }
4730 }
4733 /* Function vectorizable_live_operation.
4735 STMT computes a value that is used outside the loop. Check if
4736 it can be supported. */
4738 bool
4742 {
4743 tree operation;
4748 tree op;
4766 /* FORNOW: support only if all uses are invariant. This means
4767 that the scalar operations can remain in place, unvectorized.
4768 The original last scalar value that they compute will be used. */
4771 {
4774 {
4778 }
4782 }
4784 /* No transformation is required for the cases we currently support. */
4786 }
4789 /* Function vect_is_simple_cond.
4791 Input:
4792 LOOP - the loop that is being vectorized.
4793 COND - Condition that is checked for simple use.
4795 Returns whether a COND can be vectorized. Checks whether
4796 condition operands are supportable using vec_is_simple_use. */
4798 static bool
4800 {
4802 tree def;
4812 {
4816 }
4821 {
4825 }
4830 }
4832 /* vectorizable_condition.
4834 Check if STMT is conditional modify expression that can be vectorized.
4835 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4836 stmt using VEC_COND_EXPR to replace it, put it in VEC_STMT, and insert it
4837 at BSI.
4839 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4841 bool
4843 {
4852 tree new_temp;
4855 tree def;
4870 /* FORNOW: not yet supported. */
4872 {
4876 }
4878 /* Is vectorizable conditional operation? */
4894 /* We do not handle two different vector types for the condition
4895 and the values. */
4900 {
4905 }
4911 {
4916 }
4925 {
4928 }
4930 /* Transform */
4932 /* Handle def. */
4936 /* Handle cond expr. */
4937 vec_cond_lhs =
4939 vec_cond_rhs =
4944 /* Arguments are ready. create the new vector stmt. */
4956 }
4958 /* Function vect_transform_stmt.
4960 Create a vectorized stmt to replace STMT, and insert it at BSI. */
4962 bool
4964 {
4968 tree orig_stmt_in_pattern;
4972 {
5012 {
5013 /* In case of interleaving, the whole chain is vectorized when the
5014 last store in the chain is reached. Store stmts before the last
5015 one are skipped, and there vec_stmt_info shouldn't be freed
5016 meanwhile. */
5020 }
5021 else
5041 {
5045 }
5046 }
5050 {
5053 }
5056 {
5060 {
5062 /* STMT was inserted by the vectorizer to replace a computation idiom.
5063 ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
5064 computed this idiom. We need to record a pointer to VEC_STMT in
5065 the stmt_info of ORIG_STMT_IN_PATTERN. See more details in the
5066 documentation of vect_pattern_recog. */
5068 {
5071 }
5072 }
5073 }
5076 }
5079 /* This function builds ni_name = number of iterations loop executes
5080 on the loop preheader. */
5082 static tree
5084 {
5086 edge pe;
5096 {
5099 }
5102 }
5105 /* This function generates the following statements:
5107 ni_name = number of iterations loop executes
5108 ratio = ni_name / vf
5109 ratio_mult_vf_name = ratio * vf
5111 and places them at the loop preheader edge. */
5113 static void
5118 {
5120 edge pe;
5121 basic_block new_bb;
5123 tree var;
5124 tree ratio_name;
5125 tree ratio_mult_vf_name;
5129 tree log_vf;
5133 /* Generate temporary variable that contains
5134 number of iterations loop executes. */
5139 /* Create: ratio = ni >> log2(vf) */
5143 {
5151 }
5153 /* Create: ratio_mult_vf = ratio << log2 (vf). */
5158 {
5167 }
5174 }
5177 /* Function update_vuses_to_preheader.
5179 Input:
5180 STMT - a statement with potential VUSEs.
5181 LOOP - the loop whose preheader will contain STMT.
5183 It's possible to vectorize a loop even though an SSA_NAME from a VUSE
5184 appears to be defined in a VDEF in another statement in a loop.
5185 One such case is when the VUSE is at the dereference of a __restricted__
5186 pointer in a load and the VDEF is at the dereference of a different
5187 __restricted__ pointer in a store. Vectorization may result in
5188 copy_virtual_uses being called to copy the problematic VUSE to a new
5189 statement that is being inserted in the loop preheader. This procedure
5190 is called to change the SSA_NAME in the new statement's VUSE from the
5191 SSA_NAME updated in the loop to the related SSA_NAME available on the
5192 path entering the loop.
5194 When this function is called, we have the following situation:
5196 # vuse <name1>
5197 S1: vload
5198 do {
5199 # name1 = phi < name0 , name2>
5201 # vuse <name1>
5202 S2: vload
5204 # name2 = vdef <name1>
5205 S3: vstore
5207 }while...
5209 Stmt S1 was created in the loop preheader block as part of misaligned-load
5210 handling. This function fixes the name of the vuse of S1 from 'name1' to
5211 'name0'. */
5213 static void
5215 {
5218 ssa_op_iter iter;
5219 use_operand_p use_p;
5222 {
5228 /* For a use before any definitions, def_stmt is a NOP_EXPR. */
5231 {
5232 /* If the block containing the statement defining the SSA_NAME
5233 is in the loop then it's necessary to find the definition
5234 outside the loop using the PHI nodes of the header. */
5235 tree phi;
5239 {
5241 {
5245 }
5246 }
5248 }
5249 }
5250 }
5253 /* Function vect_update_ivs_after_vectorizer.
5255 "Advance" the induction variables of LOOP to the value they should take
5256 after the execution of LOOP. This is currently necessary because the
5257 vectorizer does not handle induction variables that are used after the
5258 loop. Such a situation occurs when the last iterations of LOOP are
5259 peeled, because:
5260 1. We introduced new uses after LOOP for IVs that were not originally used
5261 after LOOP: the IVs of LOOP are now used by an epilog loop.
5262 2. LOOP is going to be vectorized; this means that it will iterate N/VF
5263 times, whereas the loop IVs should be bumped N times.
5265 Input:
5266 - LOOP - a loop that is going to be vectorized. The last few iterations
5267 of LOOP were peeled.
5268 - NITERS - the number of iterations that LOOP executes (before it is
5269 vectorized). i.e, the number of times the ivs should be bumped.
5270 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
5271 coming out from LOOP on which there are uses of the LOOP ivs
5272 (this is the path from LOOP->exit to epilog_loop->preheader).
5274 The new definitions of the ivs are placed in LOOP->exit.
5275 The phi args associated with the edge UPDATE_E in the bb
5276 UPDATE_E->dest are updated accordingly.
5278 Assumption 1: Like the rest of the vectorizer, this function assumes
5279 a single loop exit that has a single predecessor.
5281 Assumption 2: The phi nodes in the LOOP header and in update_bb are
5282 organized in the same order.
5284 Assumption 3: The access function of the ivs is simple enough (see
5285 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
5287 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
5288 coming out of LOOP on which the ivs of LOOP are used (this is the path
5289 that leads to the epilog loop; other paths skip the epilog loop). This
5290 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
5291 needs to have its phis updated.
5292 */
5294 static void
5296 edge update_e)
5297 {
5303 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
5305 /* Make sure there exists a single-predecessor exit bb: */
5311 {
5313 tree evolution_part;
5314 tree init_expr;
5315 tree step_expr;
5317 block_stmt_iterator last_bsi;
5320 {
5323 }
5325 /* Skip virtual phi's. */
5327 {
5331 }
5333 /* Skip reduction phis. */
5335 {
5339 }
5343 evolution_part =
5347 /* FORNOW: We do not support IVs whose evolution function is a polynomial
5348 of degree >= 2 or exponential. */
5357 init_expr,
5361 else
5365 niters),
5366 step_expr),
5367 init_expr);
5376 /* Insert stmt into exit_bb. */
5381 /* Fix phi expressions in the successor bb. */
5383 }
5384 }
5387 /* Function vect_do_peeling_for_loop_bound
5389 Peel the last iterations of the loop represented by LOOP_VINFO.
5390 The peeled iterations form a new epilog loop. Given that the loop now
5391 iterates NITERS times, the new epilog loop iterates
5392 NITERS % VECTORIZATION_FACTOR times.
5394 The original loop will later be made to iterate
5395 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). */
5397 static void
5399 {
5403 edge update_e;
5404 basic_block preheader;
5415 /* Generate the following variables on the preheader of original loop:
5417 ni_name = number of iteration the original loop executes
5418 ratio = ni_name / vf
5419 ratio_mult_vf_name = ratio * vf */
5425 /* Analyze cost to set threshhold for vectorized loop. */
5431 /* Use the cost model only if it is more conservative than user specified
5432 threshold. */
5436 && (!min_scalar_loop_bound
5445 th);
5448 #ifdef ENABLE_CHECKING
5450 #endif
5452 /* A guard that controls whether the new_loop is to be executed or skipped
5453 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
5454 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
5455 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
5456 is on the path where the LOOP IVs are used and need to be updated. */
5461 else
5464 /* Update IVs of original loop as if they were advanced
5465 by ratio_mult_vf_name steps. */
5468 /* After peeling we have to reset scalar evolution analyzer. */
5472 }
5475 /* Function vect_gen_niters_for_prolog_loop
5477 Set the number of iterations for the loop represented by LOOP_VINFO
5478 to the minimum between LOOP_NITERS (the original iteration count of the loop)
5479 and the misalignment of DR - the data reference recorded in
5480 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
5481 this loop, the data reference DR will refer to an aligned location.
5483 The following computation is generated:
5485 If the misalignment of DR is known at compile time:
5486 addr_mis = int mis = DR_MISALIGNMENT (dr);
5487 Else, compute address misalignment in bytes:
5488 addr_mis = addr & (vectype_size - 1)
5490 prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
5492 (elem_size = element type size; an element is the scalar element
5493 whose type is the inner type of the vectype)
5495 For interleaving,
5497 prolog_niters = min ( LOOP_NITERS ,
5498 (VF/group_size - addr_mis/elem_size)&(VF/group_size-1) )
5499 where group_size is the size of the interleaved group.
5501 The above formulas assume that VF == number of elements in the vector. This
5502 may not hold when there are multiple-types in the loop.
5503 In this case, for some data-references in the loop the VF does not represent
5504 the number of elements that fit in the vector. Therefore, instead of VF we
5505 use TYPE_VECTOR_SUBPARTS. */
5507 static tree
5509 {
5514 edge pe;
5515 basic_block new_bb;
5526 {
5527 /* For interleaved access element size must be multiplied by the size of
5528 the interleaved group. */
5532 }
5537 {
5545 }
5546 else
5547 {
5549 tree start_addr =
5555 tree elem_size_log =
5559 tree byte_misalign;
5560 tree elem_misalign;
5565 /* Create: byte_misalign = addr & (vectype_size - 1) */
5566 byte_misalign =
5569 /* Create: elem_misalign = byte_misalign / element_size */
5570 elem_misalign =
5573 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
5577 }
5579 /* Create: prolog_loop_niters = min (iters, loop_niters) */
5580 /* If the loop bound is known at compile time we already verified that it is
5581 greater than vf; since the misalignment ('iters') is at most vf, there's
5582 no need to generate the MIN_EXPR in this case. */
5587 {
5590 }
5596 /* Insert stmt on loop preheader edge. */
5598 {
5601 }
5604 }
5607 /* Function vect_update_init_of_dr
5609 NITERS iterations were peeled from LOOP. DR represents a data reference
5610 in LOOP. This function updates the information recorded in DR to
5611 account for the fact that the first NITERS iterations had already been
5612 executed. Specifically, it updates the OFFSET field of DR. */
5614 static void
5616 {
5622 }
5625 /* Function vect_update_inits_of_drs
5627 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
5628 This function updates the information recorded for the data references in
5629 the loop to account for the fact that the first NITERS iterations had
5630 already been executed. Specifically, it updates the initial_condition of
5631 the access_function of all the data_references in the loop. */
5633 static void
5635 {
5645 }
5648 /* Function vect_do_peeling_for_alignment
5650 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
5651 'niters' is set to the misalignment of one of the data references in the
5652 loop, thereby forcing it to refer to an aligned location at the beginning
5653 of the execution of this loop. The data reference for which we are
5654 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
5656 static void
5658 {
5661 tree n_iters;
5672 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
5673 new_loop =
5677 #ifdef ENABLE_CHECKING
5679 #endif
5681 /* Update number of times loop executes. */
5686 /* Update the init conditions of the access functions of all data refs. */
5689 /* After peeling we have to reset scalar evolution analyzer. */
5693 }
5696 /* Function vect_create_cond_for_align_checks.
5698 Create a conditional expression that represents the alignment checks for
5699 all of data references (array element references) whose alignment must be
5700 checked at runtime.
5702 Input:
5703 LOOP_VINFO - two fields of the loop information are used.
5704 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
5705 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
5707 Output:
5708 COND_EXPR_STMT_LIST - statements needed to construct the conditional
5709 expression.
5710 The returned value is the conditional expression to be used in the if
5711 statement that controls which version of the loop gets executed at runtime.
5713 The algorithm makes two assumptions:
5714 1) The number of bytes "n" in a vector is a power of 2.
5715 2) An address "a" is aligned if a%n is zero and that this
5716 test can be done as a&(n-1) == 0. For example, for 16
5717 byte vectors the test is a&0xf == 0. */
5719 static tree
5722 {
5727 tree mask_cst;
5729 tree psize;
5730 tree int_ptrsize_type;
5734 tree ptrsize_zero;
5736 /* Check that mask is one less than a power of 2, i.e., mask is
5737 all zeros followed by all ones. */
5740 /* CHECKME: what is the best integer or unsigned type to use to hold a
5741 cast from a pointer value? */
5743 int_ptrsize_type
5746 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
5747 of the first vector of the i'th data reference. */
5750 {
5752 tree addr_base;
5756 /* create: addr_tmp = (int)(address_of_first_vector) */
5759 NULL_TREE);
5773 /* The addresses are OR together. */
5776 {
5777 /* create: or_tmp = or_tmp | addr_tmp */
5788 }
5789 else
5796 /* create: and_tmp = or_tmp & mask */
5806 /* Make and_tmp the left operand of the conditional test against zero.
5807 if and_tmp has a nonzero bit then some address is unaligned. */
5811 }
5814 /* Function vect_transform_loop.
5816 The analysis phase has determined that the loop is vectorizable.
5817 Vectorize the loop - created vectorized stmts to replace the scalar
5818 stmts in the loop, and update the loop exit condition. */
5820 void
5822 {
5835 /* If the loop has data references that may or may not be aligned then
5836 two versions of the loop need to be generated, one which is vectorized
5837 and one which isn't. A test is then generated to control which of the
5838 loops is executed. The test checks for the alignment of all of the
5839 data references that may or may not be aligned. */
5842 {
5844 tree cond_expr;
5846 basic_block condition_bb;
5847 block_stmt_iterator cond_exp_bsi;
5848 basic_block merge_bb;
5849 basic_block new_exit_bb;
5861 /** Loop versioning violates an assumption we try to maintain during
5862 vectorization - that the loop exit block has a single predecessor.
5863 After versioning, the exit block of both loop versions is the same
5864 basic block (i.e. it has two predecessors). Just in order to simplify
5865 following transformations in the vectorizer, we fix this situation
5866 here by adding a new (empty) block on the exit-edge of the loop,
5867 with the proper loop-exit phis to maintain loop-closed-form. **/
5877 {
5879 new_exit_bb);
5883 }
5885 /** end loop-exit-fixes after versioning **/
5890 }
5892 /* CHECKME: we wouldn't need this if we called update_ssa once
5893 for all loops. */
5896 /* Peel the loop if there are data refs with unknown alignment.
5897 Only one data ref with unknown store is allowed. */
5902 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5903 compile time constant), or it is a constant that doesn't divide by the
5904 vectorization factor, then an epilog loop needs to be created.
5905 We therefore duplicate the loop: the original loop will be vectorized,
5906 and will compute the first (n/VF) iterations. The second copy of the loop
5907 will remain scalar and will compute the remaining (n%VF) iterations.
5908 (VF is the vectorization factor). */
5914 else
5918 /* 1) Make sure the loop header has exactly two entries
5919 2) Make sure we have a preheader basic block. */
5925 /* FORNOW: the vectorizer supports only loops which body consist
5926 of one basic block (header + empty latch). When the vectorizer will
5927 support more involved loop forms, the order by which the BBs are
5928 traversed need to be reconsidered. */
5931 {
5933 stmt_vec_info stmt_info;
5934 tree phi;
5937 {
5939 {
5942 }
5956 {
5960 }
5961 }
5964 {
5969 {
5972 }
5977 {
5980 }
5988 /* -------- vectorize statement ------------ */
5995 {
5996 stmt_ann_t ann;
5998 {
5999 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
6000 interleaving chain was completed - free all the stores in
6001 the chain. */
6003 tree tmp;
6004 stmt_vec_info next_stmt_info;
6007 {
6010 /* Free the attached stmt_vec_info and remove the stmt. */
6017 }
6020 }
6021 else
6022 {
6023 /* Free the attached stmt_vec_info and remove the stmt. */
6029 }
6030 }
6039 /* The memory tags and pointers in vectorized statements need to
6040 have their SSA forms updated. FIXME, why can't this be delayed
6041 until all the loops have been transformed? */
6046 }