1 /* Analysis Utilities for Loop Vectorization. 2 Copyright (C) 2006-2018 Free Software Foundation, Inc. 3 Contributed by Dorit Nuzman <dorit@il.ibm.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 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. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "rtl.h" 26 #include "tree.h" 27 #include "gimple.h" 28 #include "ssa.h" 29 #include "expmed.h" 30 #include "optabs-tree.h" 31 #include "insn-config.h" 32 #include "recog.h" /* FIXME: for insn_data */ 33 #include "fold-const.h" 34 #include "stor-layout.h" 35 #include "tree-eh.h" 36 #include "gimplify.h" 37 #include "gimple-iterator.h" 38 #include "cfgloop.h" 39 #include "tree-vectorizer.h" 40 #include "dumpfile.h" 41 #include "builtins.h" 42 #include "internal-fn.h" 43 #include "case-cfn-macros.h" 44 #include "fold-const-call.h" 45 #include "attribs.h" 46 #include "cgraph.h" 47 #include "omp-simd-clone.h" 48 49 /* Pattern recognition functions */ 50 static gimple *vect_recog_widen_sum_pattern (vec<gimple *> *, tree *, 51 tree *); 52 static gimple *vect_recog_widen_mult_pattern (vec<gimple *> *, tree *, 53 tree *); 54 static gimple *vect_recog_dot_prod_pattern (vec<gimple *> *, tree *, 55 tree *); 56 static gimple *vect_recog_sad_pattern (vec<gimple *> *, tree *, 57 tree *); 58 static gimple *vect_recog_pow_pattern (vec<gimple *> *, tree *, tree *); 59 static gimple *vect_recog_over_widening_pattern (vec<gimple *> *, tree *, 60 tree *); 61 static gimple *vect_recog_widen_shift_pattern (vec<gimple *> *, 62 tree *, tree *); 63 static gimple *vect_recog_rotate_pattern (vec<gimple *> *, tree *, tree *); 64 static gimple *vect_recog_vector_vector_shift_pattern (vec<gimple *> *, 65 tree *, tree *); 66 static gimple *vect_recog_divmod_pattern (vec<gimple *> *, 67 tree *, tree *); 68 69 static gimple *vect_recog_mult_pattern (vec<gimple *> *, 70 tree *, tree *); 71 72 static gimple *vect_recog_mixed_size_cond_pattern (vec<gimple *> *, 73 tree *, tree *); 74 static gimple *vect_recog_bool_pattern (vec<gimple *> *, tree *, tree *); 75 static gimple *vect_recog_mask_conversion_pattern (vec<gimple *> *, tree *, tree *); 76 static gimple *vect_recog_gather_scatter_pattern (vec<gimple *> *, tree *, 77 tree *); 78 79 struct vect_recog_func 80 { 81 vect_recog_func_ptr fn; 82 const char *name; 83 }; 84 85 /* Note that ordering matters - the first pattern matching on a stmt 86 is taken which means usually the more complex one needs to preceed 87 the less comples onex (widen_sum only after dot_prod or sad for example). */ 88 static vect_recog_func vect_vect_recog_func_ptrs[NUM_PATTERNS] = { 89 { vect_recog_widen_mult_pattern, "widen_mult" }, 90 { vect_recog_dot_prod_pattern, "dot_prod" }, 91 { vect_recog_sad_pattern, "sad" }, 92 { vect_recog_widen_sum_pattern, "widen_sum" }, 93 { vect_recog_pow_pattern, "pow" }, 94 { vect_recog_widen_shift_pattern, "widen_shift" }, 95 { vect_recog_over_widening_pattern, "over_widening" }, 96 { vect_recog_rotate_pattern, "rotate" }, 97 { vect_recog_vector_vector_shift_pattern, "vector_vector_shift" }, 98 { vect_recog_divmod_pattern, "divmod" }, 99 { vect_recog_mult_pattern, "mult" }, 100 { vect_recog_mixed_size_cond_pattern, "mixed_size_cond" }, 101 { vect_recog_bool_pattern, "bool" }, 102 /* This must come before mask conversion, and includes the parts 103 of mask conversion that are needed for gather and scatter 104 internal functions. */ 105 { vect_recog_gather_scatter_pattern, "gather_scatter" }, 106 { vect_recog_mask_conversion_pattern, "mask_conversion" } 107 }; 108 109 static inline void 110 append_pattern_def_seq (stmt_vec_info stmt_info, gimple *stmt) 111 { 112 gimple_seq_add_stmt_without_update (&STMT_VINFO_PATTERN_DEF_SEQ (stmt_info), 113 stmt); 114 } 115 116 static inline void 117 new_pattern_def_seq (stmt_vec_info stmt_info, gimple *stmt) 118 { 119 STMT_VINFO_PATTERN_DEF_SEQ (stmt_info) = NULL; 120 append_pattern_def_seq (stmt_info, stmt); 121 } 122 123 /* Check whether STMT2 is in the same loop or basic block as STMT1. 124 Which of the two applies depends on whether we're currently doing 125 loop-based or basic-block-based vectorization, as determined by 126 the vinfo_for_stmt for STMT1 (which must be defined). 127 128 If this returns true, vinfo_for_stmt for STMT2 is guaranteed 129 to be defined as well. */ 130 131 static bool 132 vect_same_loop_or_bb_p (gimple *stmt1, gimple *stmt2) 133 { 134 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt1); 135 return vect_stmt_in_region_p (stmt_vinfo->vinfo, stmt2); 136 } 137 138 /* If the LHS of DEF_STMT has a single use, and that statement is 139 in the same loop or basic block, return it. */ 140 141 static gimple * 142 vect_single_imm_use (gimple *def_stmt) 143 { 144 tree lhs = gimple_assign_lhs (def_stmt); 145 use_operand_p use_p; 146 gimple *use_stmt; 147 148 if (!single_imm_use (lhs, &use_p, &use_stmt)) 149 return NULL; 150 151 if (!vect_same_loop_or_bb_p (def_stmt, use_stmt)) 152 return NULL; 153 154 return use_stmt; 155 } 156 157 /* Check whether NAME, an ssa-name used in USE_STMT, 158 is a result of a type promotion, such that: 159 DEF_STMT: NAME = NOP (name0) 160 If CHECK_SIGN is TRUE, check that either both types are signed or both are 161 unsigned. */ 162 163 static bool 164 type_conversion_p (tree name, gimple *use_stmt, bool check_sign, 165 tree *orig_type, gimple **def_stmt, bool *promotion) 166 { 167 gimple *dummy_gimple; 168 stmt_vec_info stmt_vinfo; 169 tree type = TREE_TYPE (name); 170 tree oprnd0; 171 enum vect_def_type dt; 172 173 stmt_vinfo = vinfo_for_stmt (use_stmt); 174 if (!vect_is_simple_use (name, stmt_vinfo->vinfo, def_stmt, &dt)) 175 return false; 176 177 if (dt != vect_internal_def 178 && dt != vect_external_def && dt != vect_constant_def) 179 return false; 180 181 if (!*def_stmt) 182 return false; 183 184 if (dt == vect_internal_def) 185 { 186 stmt_vec_info def_vinfo = vinfo_for_stmt (*def_stmt); 187 if (STMT_VINFO_IN_PATTERN_P (def_vinfo)) 188 return false; 189 } 190 191 if (!is_gimple_assign (*def_stmt)) 192 return false; 193 194 if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (*def_stmt))) 195 return false; 196 197 oprnd0 = gimple_assign_rhs1 (*def_stmt); 198 199 *orig_type = TREE_TYPE (oprnd0); 200 if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*orig_type) 201 || ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*orig_type)) && check_sign)) 202 return false; 203 204 if (TYPE_PRECISION (type) >= (TYPE_PRECISION (*orig_type) * 2)) 205 *promotion = true; 206 else 207 *promotion = false; 208 209 if (!vect_is_simple_use (oprnd0, stmt_vinfo->vinfo, &dummy_gimple, &dt)) 210 return false; 211 212 return true; 213 } 214 215 /* Helper to return a new temporary for pattern of TYPE for STMT. If STMT 216 is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */ 217 218 static tree 219 vect_recog_temp_ssa_var (tree type, gimple *stmt) 220 { 221 return make_temp_ssa_name (type, stmt, "patt"); 222 } 223 224 /* Return true if STMT_VINFO describes a reduction for which reassociation 225 is allowed. If STMT_INFO is part of a group, assume that it's part of 226 a reduction chain and optimistically assume that all statements 227 except the last allow reassociation. */ 228 229 static bool 230 vect_reassociating_reduction_p (stmt_vec_info stmt_vinfo) 231 { 232 return (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def 233 ? STMT_VINFO_REDUC_TYPE (stmt_vinfo) != FOLD_LEFT_REDUCTION 234 : GROUP_FIRST_ELEMENT (stmt_vinfo) != NULL); 235 } 236 237 /* Function vect_recog_dot_prod_pattern 238 239 Try to find the following pattern: 240 241 type x_t, y_t; 242 TYPE1 prod; 243 TYPE2 sum = init; 244 loop: 245 sum_0 = phi <init, sum_1> 246 S1 x_t = ... 247 S2 y_t = ... 248 S3 x_T = (TYPE1) x_t; 249 S4 y_T = (TYPE1) y_t; 250 S5 prod = x_T * y_T; 251 [S6 prod = (TYPE2) prod; #optional] 252 S7 sum_1 = prod + sum_0; 253 254 where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the 255 same size of 'TYPE1' or bigger. This is a special case of a reduction 256 computation. 257 258 Input: 259 260 * STMTS: Contains a stmt from which the pattern search begins. In the 261 example, when this function is called with S7, the pattern {S3,S4,S5,S6,S7} 262 will be detected. 263 264 Output: 265 266 * TYPE_IN: The type of the input arguments to the pattern. 267 268 * TYPE_OUT: The type of the output of this pattern. 269 270 * Return value: A new stmt that will be used to replace the sequence of 271 stmts that constitute the pattern. In this case it will be: 272 WIDEN_DOT_PRODUCT <x_t, y_t, sum_0> 273 274 Note: The dot-prod idiom is a widening reduction pattern that is 275 vectorized without preserving all the intermediate results. It 276 produces only N/2 (widened) results (by summing up pairs of 277 intermediate results) rather than all N results. Therefore, we 278 cannot allow this pattern when we want to get all the results and in 279 the correct order (as is the case when this computation is in an 280 inner-loop nested in an outer-loop that us being vectorized). */ 281 282 static gimple * 283 vect_recog_dot_prod_pattern (vec<gimple *> *stmts, tree *type_in, 284 tree *type_out) 285 { 286 gimple *stmt, *last_stmt = (*stmts)[0]; 287 tree oprnd0, oprnd1; 288 tree oprnd00, oprnd01; 289 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 290 tree type, half_type; 291 gimple *pattern_stmt; 292 tree prod_type; 293 loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo); 294 struct loop *loop; 295 tree var; 296 bool promotion; 297 298 if (!loop_info) 299 return NULL; 300 301 loop = LOOP_VINFO_LOOP (loop_info); 302 303 /* We don't allow changing the order of the computation in the inner-loop 304 when doing outer-loop vectorization. */ 305 if (loop && nested_in_vect_loop_p (loop, last_stmt)) 306 return NULL; 307 308 if (!is_gimple_assign (last_stmt)) 309 return NULL; 310 311 type = gimple_expr_type (last_stmt); 312 313 /* Look for the following pattern 314 DX = (TYPE1) X; 315 DY = (TYPE1) Y; 316 DPROD = DX * DY; 317 DDPROD = (TYPE2) DPROD; 318 sum_1 = DDPROD + sum_0; 319 In which 320 - DX is double the size of X 321 - DY is double the size of Y 322 - DX, DY, DPROD all have the same type 323 - sum is the same size of DPROD or bigger 324 - sum has been recognized as a reduction variable. 325 326 This is equivalent to: 327 DPROD = X w* Y; #widen mult 328 sum_1 = DPROD w+ sum_0; #widen summation 329 or 330 DPROD = X w* Y; #widen mult 331 sum_1 = DPROD + sum_0; #summation 332 */ 333 334 /* Starting from LAST_STMT, follow the defs of its uses in search 335 of the above pattern. */ 336 337 if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR) 338 return NULL; 339 340 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 341 { 342 /* Has been detected as widening-summation? */ 343 344 stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); 345 type = gimple_expr_type (stmt); 346 if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR) 347 return NULL; 348 oprnd0 = gimple_assign_rhs1 (stmt); 349 oprnd1 = gimple_assign_rhs2 (stmt); 350 half_type = TREE_TYPE (oprnd0); 351 } 352 else 353 { 354 gimple *def_stmt; 355 356 if (!vect_reassociating_reduction_p (stmt_vinfo)) 357 return NULL; 358 oprnd0 = gimple_assign_rhs1 (last_stmt); 359 oprnd1 = gimple_assign_rhs2 (last_stmt); 360 if (!types_compatible_p (TREE_TYPE (oprnd0), type) 361 || !types_compatible_p (TREE_TYPE (oprnd1), type)) 362 return NULL; 363 stmt = last_stmt; 364 365 if (type_conversion_p (oprnd0, stmt, true, &half_type, &def_stmt, 366 &promotion) 367 && promotion) 368 { 369 stmt = def_stmt; 370 oprnd0 = gimple_assign_rhs1 (stmt); 371 } 372 else 373 half_type = type; 374 } 375 376 /* So far so good. Since last_stmt was detected as a (summation) reduction, 377 we know that oprnd1 is the reduction variable (defined by a loop-header 378 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body. 379 Left to check that oprnd0 is defined by a (widen_)mult_expr */ 380 if (TREE_CODE (oprnd0) != SSA_NAME) 381 return NULL; 382 383 prod_type = half_type; 384 stmt = SSA_NAME_DEF_STMT (oprnd0); 385 386 /* It could not be the dot_prod pattern if the stmt is outside the loop. */ 387 if (!gimple_bb (stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (stmt))) 388 return NULL; 389 390 /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi 391 inside the loop (in case we are analyzing an outer-loop). */ 392 if (!is_gimple_assign (stmt)) 393 return NULL; 394 stmt_vinfo = vinfo_for_stmt (stmt); 395 gcc_assert (stmt_vinfo); 396 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def) 397 return NULL; 398 if (gimple_assign_rhs_code (stmt) != MULT_EXPR) 399 return NULL; 400 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 401 { 402 /* Has been detected as a widening multiplication? */ 403 404 stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); 405 if (gimple_assign_rhs_code (stmt) != WIDEN_MULT_EXPR) 406 return NULL; 407 stmt_vinfo = vinfo_for_stmt (stmt); 408 gcc_assert (stmt_vinfo); 409 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_internal_def); 410 oprnd00 = gimple_assign_rhs1 (stmt); 411 oprnd01 = gimple_assign_rhs2 (stmt); 412 STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (last_stmt)) 413 = STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo); 414 } 415 else 416 { 417 tree half_type0, half_type1; 418 gimple *def_stmt; 419 tree oprnd0, oprnd1; 420 421 oprnd0 = gimple_assign_rhs1 (stmt); 422 oprnd1 = gimple_assign_rhs2 (stmt); 423 if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type) 424 || !types_compatible_p (TREE_TYPE (oprnd1), prod_type)) 425 return NULL; 426 if (!type_conversion_p (oprnd0, stmt, true, &half_type0, &def_stmt, 427 &promotion) 428 || !promotion) 429 return NULL; 430 oprnd00 = gimple_assign_rhs1 (def_stmt); 431 if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt, 432 &promotion) 433 || !promotion) 434 return NULL; 435 oprnd01 = gimple_assign_rhs1 (def_stmt); 436 if (!types_compatible_p (half_type0, half_type1)) 437 return NULL; 438 if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2) 439 return NULL; 440 } 441 442 half_type = TREE_TYPE (oprnd00); 443 *type_in = half_type; 444 *type_out = type; 445 446 /* Pattern detected. Create a stmt to be used to replace the pattern: */ 447 var = vect_recog_temp_ssa_var (type, NULL); 448 pattern_stmt = gimple_build_assign (var, DOT_PROD_EXPR, 449 oprnd00, oprnd01, oprnd1); 450 451 if (dump_enabled_p ()) 452 { 453 dump_printf_loc (MSG_NOTE, vect_location, 454 "vect_recog_dot_prod_pattern: detected: "); 455 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 456 } 457 458 return pattern_stmt; 459 } 460 461 462 /* Function vect_recog_sad_pattern 463 464 Try to find the following Sum of Absolute Difference (SAD) pattern: 465 466 type x_t, y_t; 467 signed TYPE1 diff, abs_diff; 468 TYPE2 sum = init; 469 loop: 470 sum_0 = phi <init, sum_1> 471 S1 x_t = ... 472 S2 y_t = ... 473 S3 x_T = (TYPE1) x_t; 474 S4 y_T = (TYPE1) y_t; 475 S5 diff = x_T - y_T; 476 S6 abs_diff = ABS_EXPR <diff>; 477 [S7 abs_diff = (TYPE2) abs_diff; #optional] 478 S8 sum_1 = abs_diff + sum_0; 479 480 where 'TYPE1' is at least double the size of type 'type', and 'TYPE2' is the 481 same size of 'TYPE1' or bigger. This is a special case of a reduction 482 computation. 483 484 Input: 485 486 * STMTS: Contains a stmt from which the pattern search begins. In the 487 example, when this function is called with S8, the pattern 488 {S3,S4,S5,S6,S7,S8} will be detected. 489 490 Output: 491 492 * TYPE_IN: The type of the input arguments to the pattern. 493 494 * TYPE_OUT: The type of the output of this pattern. 495 496 * Return value: A new stmt that will be used to replace the sequence of 497 stmts that constitute the pattern. In this case it will be: 498 SAD_EXPR <x_t, y_t, sum_0> 499 */ 500 501 static gimple * 502 vect_recog_sad_pattern (vec<gimple *> *stmts, tree *type_in, 503 tree *type_out) 504 { 505 gimple *last_stmt = (*stmts)[0]; 506 tree sad_oprnd0, sad_oprnd1; 507 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 508 tree half_type; 509 loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo); 510 struct loop *loop; 511 bool promotion; 512 513 if (!loop_info) 514 return NULL; 515 516 loop = LOOP_VINFO_LOOP (loop_info); 517 518 /* We don't allow changing the order of the computation in the inner-loop 519 when doing outer-loop vectorization. */ 520 if (loop && nested_in_vect_loop_p (loop, last_stmt)) 521 return NULL; 522 523 if (!is_gimple_assign (last_stmt)) 524 return NULL; 525 526 tree sum_type = gimple_expr_type (last_stmt); 527 528 /* Look for the following pattern 529 DX = (TYPE1) X; 530 DY = (TYPE1) Y; 531 DDIFF = DX - DY; 532 DAD = ABS_EXPR <DDIFF>; 533 DDPROD = (TYPE2) DPROD; 534 sum_1 = DAD + sum_0; 535 In which 536 - DX is at least double the size of X 537 - DY is at least double the size of Y 538 - DX, DY, DDIFF, DAD all have the same type 539 - sum is the same size of DAD or bigger 540 - sum has been recognized as a reduction variable. 541 542 This is equivalent to: 543 DDIFF = X w- Y; #widen sub 544 DAD = ABS_EXPR <DDIFF>; 545 sum_1 = DAD w+ sum_0; #widen summation 546 or 547 DDIFF = X w- Y; #widen sub 548 DAD = ABS_EXPR <DDIFF>; 549 sum_1 = DAD + sum_0; #summation 550 */ 551 552 /* Starting from LAST_STMT, follow the defs of its uses in search 553 of the above pattern. */ 554 555 if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR) 556 return NULL; 557 558 tree plus_oprnd0, plus_oprnd1; 559 560 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 561 { 562 /* Has been detected as widening-summation? */ 563 564 gimple *stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); 565 sum_type = gimple_expr_type (stmt); 566 if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR) 567 return NULL; 568 plus_oprnd0 = gimple_assign_rhs1 (stmt); 569 plus_oprnd1 = gimple_assign_rhs2 (stmt); 570 half_type = TREE_TYPE (plus_oprnd0); 571 } 572 else 573 { 574 gimple *def_stmt; 575 576 if (!vect_reassociating_reduction_p (stmt_vinfo)) 577 return NULL; 578 plus_oprnd0 = gimple_assign_rhs1 (last_stmt); 579 plus_oprnd1 = gimple_assign_rhs2 (last_stmt); 580 if (!types_compatible_p (TREE_TYPE (plus_oprnd0), sum_type) 581 || !types_compatible_p (TREE_TYPE (plus_oprnd1), sum_type)) 582 return NULL; 583 584 /* The type conversion could be promotion, demotion, 585 or just signed -> unsigned. */ 586 if (type_conversion_p (plus_oprnd0, last_stmt, false, 587 &half_type, &def_stmt, &promotion)) 588 plus_oprnd0 = gimple_assign_rhs1 (def_stmt); 589 else 590 half_type = sum_type; 591 } 592 593 /* So far so good. Since last_stmt was detected as a (summation) reduction, 594 we know that plus_oprnd1 is the reduction variable (defined by a loop-header 595 phi), and plus_oprnd0 is an ssa-name defined by a stmt in the loop body. 596 Then check that plus_oprnd0 is defined by an abs_expr. */ 597 598 if (TREE_CODE (plus_oprnd0) != SSA_NAME) 599 return NULL; 600 601 tree abs_type = half_type; 602 gimple *abs_stmt = SSA_NAME_DEF_STMT (plus_oprnd0); 603 604 /* It could not be the sad pattern if the abs_stmt is outside the loop. */ 605 if (!gimple_bb (abs_stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (abs_stmt))) 606 return NULL; 607 608 /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi 609 inside the loop (in case we are analyzing an outer-loop). */ 610 if (!is_gimple_assign (abs_stmt)) 611 return NULL; 612 613 stmt_vec_info abs_stmt_vinfo = vinfo_for_stmt (abs_stmt); 614 gcc_assert (abs_stmt_vinfo); 615 if (STMT_VINFO_DEF_TYPE (abs_stmt_vinfo) != vect_internal_def) 616 return NULL; 617 if (gimple_assign_rhs_code (abs_stmt) != ABS_EXPR) 618 return NULL; 619 620 tree abs_oprnd = gimple_assign_rhs1 (abs_stmt); 621 if (!types_compatible_p (TREE_TYPE (abs_oprnd), abs_type)) 622 return NULL; 623 if (TYPE_UNSIGNED (abs_type)) 624 return NULL; 625 626 /* We then detect if the operand of abs_expr is defined by a minus_expr. */ 627 628 if (TREE_CODE (abs_oprnd) != SSA_NAME) 629 return NULL; 630 631 gimple *diff_stmt = SSA_NAME_DEF_STMT (abs_oprnd); 632 633 /* It could not be the sad pattern if the diff_stmt is outside the loop. */ 634 if (!gimple_bb (diff_stmt) 635 || !flow_bb_inside_loop_p (loop, gimple_bb (diff_stmt))) 636 return NULL; 637 638 /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi 639 inside the loop (in case we are analyzing an outer-loop). */ 640 if (!is_gimple_assign (diff_stmt)) 641 return NULL; 642 643 stmt_vec_info diff_stmt_vinfo = vinfo_for_stmt (diff_stmt); 644 gcc_assert (diff_stmt_vinfo); 645 if (STMT_VINFO_DEF_TYPE (diff_stmt_vinfo) != vect_internal_def) 646 return NULL; 647 if (gimple_assign_rhs_code (diff_stmt) != MINUS_EXPR) 648 return NULL; 649 650 tree half_type0, half_type1; 651 gimple *def_stmt; 652 653 tree minus_oprnd0 = gimple_assign_rhs1 (diff_stmt); 654 tree minus_oprnd1 = gimple_assign_rhs2 (diff_stmt); 655 656 if (!types_compatible_p (TREE_TYPE (minus_oprnd0), abs_type) 657 || !types_compatible_p (TREE_TYPE (minus_oprnd1), abs_type)) 658 return NULL; 659 if (!type_conversion_p (minus_oprnd0, diff_stmt, false, 660 &half_type0, &def_stmt, &promotion) 661 || !promotion) 662 return NULL; 663 sad_oprnd0 = gimple_assign_rhs1 (def_stmt); 664 665 if (!type_conversion_p (minus_oprnd1, diff_stmt, false, 666 &half_type1, &def_stmt, &promotion) 667 || !promotion) 668 return NULL; 669 sad_oprnd1 = gimple_assign_rhs1 (def_stmt); 670 671 if (!types_compatible_p (half_type0, half_type1)) 672 return NULL; 673 if (TYPE_PRECISION (abs_type) < TYPE_PRECISION (half_type0) * 2 674 || TYPE_PRECISION (sum_type) < TYPE_PRECISION (half_type0) * 2) 675 return NULL; 676 677 *type_in = TREE_TYPE (sad_oprnd0); 678 *type_out = sum_type; 679 680 /* Pattern detected. Create a stmt to be used to replace the pattern: */ 681 tree var = vect_recog_temp_ssa_var (sum_type, NULL); 682 gimple *pattern_stmt = gimple_build_assign (var, SAD_EXPR, sad_oprnd0, 683 sad_oprnd1, plus_oprnd1); 684 685 if (dump_enabled_p ()) 686 { 687 dump_printf_loc (MSG_NOTE, vect_location, 688 "vect_recog_sad_pattern: detected: "); 689 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 690 } 691 692 return pattern_stmt; 693 } 694 695 696 /* Handle widening operation by a constant. At the moment we support MULT_EXPR 697 and LSHIFT_EXPR. 698 699 For MULT_EXPR we check that CONST_OPRND fits HALF_TYPE, and for LSHIFT_EXPR 700 we check that CONST_OPRND is less or equal to the size of HALF_TYPE. 701 702 Otherwise, if the type of the result (TYPE) is at least 4 times bigger than 703 HALF_TYPE, and there is an intermediate type (2 times smaller than TYPE) 704 that satisfies the above restrictions, we can perform a widening opeartion 705 from the intermediate type to TYPE and replace a_T = (TYPE) a_t; 706 with a_it = (interm_type) a_t; Store such operation in *WSTMT. */ 707 708 static bool 709 vect_handle_widen_op_by_const (gimple *stmt, enum tree_code code, 710 tree const_oprnd, tree *oprnd, 711 gimple **wstmt, tree type, 712 tree *half_type, gimple *def_stmt) 713 { 714 tree new_type, new_oprnd; 715 716 if (code != MULT_EXPR && code != LSHIFT_EXPR) 717 return false; 718 719 if (((code == MULT_EXPR && int_fits_type_p (const_oprnd, *half_type)) 720 || (code == LSHIFT_EXPR 721 && compare_tree_int (const_oprnd, TYPE_PRECISION (*half_type)) 722 != 1)) 723 && TYPE_PRECISION (type) == (TYPE_PRECISION (*half_type) * 2)) 724 { 725 /* CONST_OPRND is a constant of HALF_TYPE. */ 726 *oprnd = gimple_assign_rhs1 (def_stmt); 727 return true; 728 } 729 730 if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4)) 731 return false; 732 733 if (!vect_same_loop_or_bb_p (stmt, def_stmt)) 734 return false; 735 736 /* TYPE is 4 times bigger than HALF_TYPE, try widening operation for 737 a type 2 times bigger than HALF_TYPE. */ 738 new_type = build_nonstandard_integer_type (TYPE_PRECISION (type) / 2, 739 TYPE_UNSIGNED (type)); 740 if ((code == MULT_EXPR && !int_fits_type_p (const_oprnd, new_type)) 741 || (code == LSHIFT_EXPR 742 && compare_tree_int (const_oprnd, TYPE_PRECISION (new_type)) == 1)) 743 return false; 744 745 /* Use NEW_TYPE for widening operation and create a_T = (NEW_TYPE) a_t; */ 746 *oprnd = gimple_assign_rhs1 (def_stmt); 747 new_oprnd = make_ssa_name (new_type); 748 *wstmt = gimple_build_assign (new_oprnd, NOP_EXPR, *oprnd); 749 *oprnd = new_oprnd; 750 751 *half_type = new_type; 752 return true; 753 } 754 755 756 /* Function vect_recog_widen_mult_pattern 757 758 Try to find the following pattern: 759 760 type1 a_t; 761 type2 b_t; 762 TYPE a_T, b_T, prod_T; 763 764 S1 a_t = ; 765 S2 b_t = ; 766 S3 a_T = (TYPE) a_t; 767 S4 b_T = (TYPE) b_t; 768 S5 prod_T = a_T * b_T; 769 770 where type 'TYPE' is at least double the size of type 'type1' and 'type2'. 771 772 Also detect unsigned cases: 773 774 unsigned type1 a_t; 775 unsigned type2 b_t; 776 unsigned TYPE u_prod_T; 777 TYPE a_T, b_T, prod_T; 778 779 S1 a_t = ; 780 S2 b_t = ; 781 S3 a_T = (TYPE) a_t; 782 S4 b_T = (TYPE) b_t; 783 S5 prod_T = a_T * b_T; 784 S6 u_prod_T = (unsigned TYPE) prod_T; 785 786 and multiplication by constants: 787 788 type a_t; 789 TYPE a_T, prod_T; 790 791 S1 a_t = ; 792 S3 a_T = (TYPE) a_t; 793 S5 prod_T = a_T * CONST; 794 795 A special case of multiplication by constants is when 'TYPE' is 4 times 796 bigger than 'type', but CONST fits an intermediate type 2 times smaller 797 than 'TYPE'. In that case we create an additional pattern stmt for S3 798 to create a variable of the intermediate type, and perform widen-mult 799 on the intermediate type as well: 800 801 type a_t; 802 interm_type a_it; 803 TYPE a_T, prod_T, prod_T'; 804 805 S1 a_t = ; 806 S3 a_T = (TYPE) a_t; 807 '--> a_it = (interm_type) a_t; 808 S5 prod_T = a_T * CONST; 809 '--> prod_T' = a_it w* CONST; 810 811 Input/Output: 812 813 * STMTS: Contains a stmt from which the pattern search begins. In the 814 example, when this function is called with S5, the pattern {S3,S4,S5,(S6)} 815 is detected. In case of unsigned widen-mult, the original stmt (S5) is 816 replaced with S6 in STMTS. In case of multiplication by a constant 817 of an intermediate type (the last case above), STMTS also contains S3 818 (inserted before S5). 819 820 Output: 821 822 * TYPE_IN: The type of the input arguments to the pattern. 823 824 * TYPE_OUT: The type of the output of this pattern. 825 826 * Return value: A new stmt that will be used to replace the sequence of 827 stmts that constitute the pattern. In this case it will be: 828 WIDEN_MULT <a_t, b_t> 829 If the result of WIDEN_MULT needs to be converted to a larger type, the 830 returned stmt will be this type conversion stmt. 831 */ 832 833 static gimple * 834 vect_recog_widen_mult_pattern (vec<gimple *> *stmts, 835 tree *type_in, tree *type_out) 836 { 837 gimple *last_stmt = stmts->pop (); 838 gimple *def_stmt0, *def_stmt1; 839 tree oprnd0, oprnd1; 840 tree type, half_type0, half_type1; 841 gimple *new_stmt = NULL, *pattern_stmt = NULL; 842 tree vectype, vecitype; 843 tree var; 844 enum tree_code dummy_code; 845 int dummy_int; 846 vec<tree> dummy_vec; 847 bool op1_ok; 848 bool promotion; 849 850 if (!is_gimple_assign (last_stmt)) 851 return NULL; 852 853 type = gimple_expr_type (last_stmt); 854 855 /* Starting from LAST_STMT, follow the defs of its uses in search 856 of the above pattern. */ 857 858 if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR) 859 return NULL; 860 861 oprnd0 = gimple_assign_rhs1 (last_stmt); 862 oprnd1 = gimple_assign_rhs2 (last_stmt); 863 if (!types_compatible_p (TREE_TYPE (oprnd0), type) 864 || !types_compatible_p (TREE_TYPE (oprnd1), type)) 865 return NULL; 866 867 /* Check argument 0. */ 868 if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0, 869 &promotion) 870 || !promotion) 871 return NULL; 872 /* Check argument 1. */ 873 op1_ok = type_conversion_p (oprnd1, last_stmt, false, &half_type1, 874 &def_stmt1, &promotion); 875 876 if (op1_ok && promotion) 877 { 878 oprnd0 = gimple_assign_rhs1 (def_stmt0); 879 oprnd1 = gimple_assign_rhs1 (def_stmt1); 880 } 881 else 882 { 883 if (TREE_CODE (oprnd1) == INTEGER_CST 884 && TREE_CODE (half_type0) == INTEGER_TYPE 885 && vect_handle_widen_op_by_const (last_stmt, MULT_EXPR, oprnd1, 886 &oprnd0, &new_stmt, type, 887 &half_type0, def_stmt0)) 888 { 889 half_type1 = half_type0; 890 oprnd1 = fold_convert (half_type1, oprnd1); 891 } 892 else 893 return NULL; 894 } 895 896 /* If the two arguments have different sizes, convert the one with 897 the smaller type into the larger type. */ 898 if (TYPE_PRECISION (half_type0) != TYPE_PRECISION (half_type1)) 899 { 900 /* If we already used up the single-stmt slot give up. */ 901 if (new_stmt) 902 return NULL; 903 904 tree* oprnd = NULL; 905 gimple *def_stmt = NULL; 906 907 if (TYPE_PRECISION (half_type0) < TYPE_PRECISION (half_type1)) 908 { 909 def_stmt = def_stmt0; 910 half_type0 = half_type1; 911 oprnd = &oprnd0; 912 } 913 else 914 { 915 def_stmt = def_stmt1; 916 half_type1 = half_type0; 917 oprnd = &oprnd1; 918 } 919 920 tree old_oprnd = gimple_assign_rhs1 (def_stmt); 921 tree new_oprnd = make_ssa_name (half_type0); 922 new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, old_oprnd); 923 *oprnd = new_oprnd; 924 } 925 926 /* Handle unsigned case. Look for 927 S6 u_prod_T = (unsigned TYPE) prod_T; 928 Use unsigned TYPE as the type for WIDEN_MULT_EXPR. */ 929 if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0)) 930 { 931 gimple *use_stmt; 932 tree use_lhs; 933 tree use_type; 934 935 if (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (half_type1)) 936 return NULL; 937 938 use_stmt = vect_single_imm_use (last_stmt); 939 if (!use_stmt || !is_gimple_assign (use_stmt) 940 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))) 941 return NULL; 942 943 use_lhs = gimple_assign_lhs (use_stmt); 944 use_type = TREE_TYPE (use_lhs); 945 if (!INTEGRAL_TYPE_P (use_type) 946 || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type)) 947 || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type))) 948 return NULL; 949 950 type = use_type; 951 last_stmt = use_stmt; 952 } 953 954 if (!types_compatible_p (half_type0, half_type1)) 955 return NULL; 956 957 /* If TYPE is more than twice larger than HALF_TYPE, we use WIDEN_MULT 958 to get an intermediate result of type ITYPE. In this case we need 959 to build a statement to convert this intermediate result to type TYPE. */ 960 tree itype = type; 961 if (TYPE_PRECISION (type) > TYPE_PRECISION (half_type0) * 2) 962 itype = build_nonstandard_integer_type 963 (GET_MODE_BITSIZE (SCALAR_TYPE_MODE (half_type0)) * 2, 964 TYPE_UNSIGNED (type)); 965 966 /* Pattern detected. */ 967 if (dump_enabled_p ()) 968 dump_printf_loc (MSG_NOTE, vect_location, 969 "vect_recog_widen_mult_pattern: detected:\n"); 970 971 /* Check target support */ 972 vectype = get_vectype_for_scalar_type (half_type0); 973 vecitype = get_vectype_for_scalar_type (itype); 974 if (!vectype 975 || !vecitype 976 || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt, 977 vecitype, vectype, 978 &dummy_code, &dummy_code, 979 &dummy_int, &dummy_vec)) 980 return NULL; 981 982 *type_in = vectype; 983 *type_out = get_vectype_for_scalar_type (type); 984 985 /* Pattern supported. Create a stmt to be used to replace the pattern: */ 986 var = vect_recog_temp_ssa_var (itype, NULL); 987 pattern_stmt = gimple_build_assign (var, WIDEN_MULT_EXPR, oprnd0, oprnd1); 988 989 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 990 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL; 991 992 /* If the original two operands have different sizes, we may need to convert 993 the smaller one into the larget type. If this is the case, at this point 994 the new stmt is already built. */ 995 if (new_stmt) 996 { 997 append_pattern_def_seq (stmt_vinfo, new_stmt); 998 stmt_vec_info new_stmt_info 999 = new_stmt_vec_info (new_stmt, stmt_vinfo->vinfo); 1000 set_vinfo_for_stmt (new_stmt, new_stmt_info); 1001 STMT_VINFO_VECTYPE (new_stmt_info) = vectype; 1002 } 1003 1004 /* If ITYPE is not TYPE, we need to build a type convertion stmt to convert 1005 the result of the widen-mult operation into type TYPE. */ 1006 if (itype != type) 1007 { 1008 append_pattern_def_seq (stmt_vinfo, pattern_stmt); 1009 stmt_vec_info pattern_stmt_info 1010 = new_stmt_vec_info (pattern_stmt, stmt_vinfo->vinfo); 1011 set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info); 1012 STMT_VINFO_VECTYPE (pattern_stmt_info) = vecitype; 1013 pattern_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL), 1014 NOP_EXPR, 1015 gimple_assign_lhs (pattern_stmt)); 1016 } 1017 1018 if (dump_enabled_p ()) 1019 dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0); 1020 1021 stmts->safe_push (last_stmt); 1022 return pattern_stmt; 1023 } 1024 1025 1026 /* Function vect_recog_pow_pattern 1027 1028 Try to find the following pattern: 1029 1030 x = POW (y, N); 1031 1032 with POW being one of pow, powf, powi, powif and N being 1033 either 2 or 0.5. 1034 1035 Input: 1036 1037 * LAST_STMT: A stmt from which the pattern search begins. 1038 1039 Output: 1040 1041 * TYPE_IN: The type of the input arguments to the pattern. 1042 1043 * TYPE_OUT: The type of the output of this pattern. 1044 1045 * Return value: A new stmt that will be used to replace the sequence of 1046 stmts that constitute the pattern. In this case it will be: 1047 x = x * x 1048 or 1049 x = sqrt (x) 1050 */ 1051 1052 static gimple * 1053 vect_recog_pow_pattern (vec<gimple *> *stmts, tree *type_in, 1054 tree *type_out) 1055 { 1056 gimple *last_stmt = (*stmts)[0]; 1057 tree base, exp; 1058 gimple *stmt; 1059 tree var; 1060 1061 if (!is_gimple_call (last_stmt) || gimple_call_lhs (last_stmt) == NULL) 1062 return NULL; 1063 1064 switch (gimple_call_combined_fn (last_stmt)) 1065 { 1066 CASE_CFN_POW: 1067 CASE_CFN_POWI: 1068 break; 1069 1070 default: 1071 return NULL; 1072 } 1073 1074 base = gimple_call_arg (last_stmt, 0); 1075 exp = gimple_call_arg (last_stmt, 1); 1076 if (TREE_CODE (exp) != REAL_CST 1077 && TREE_CODE (exp) != INTEGER_CST) 1078 { 1079 if (flag_unsafe_math_optimizations 1080 && TREE_CODE (base) == REAL_CST 1081 && !gimple_call_internal_p (last_stmt)) 1082 { 1083 combined_fn log_cfn; 1084 built_in_function exp_bfn; 1085 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (last_stmt))) 1086 { 1087 case BUILT_IN_POW: 1088 log_cfn = CFN_BUILT_IN_LOG; 1089 exp_bfn = BUILT_IN_EXP; 1090 break; 1091 case BUILT_IN_POWF: 1092 log_cfn = CFN_BUILT_IN_LOGF; 1093 exp_bfn = BUILT_IN_EXPF; 1094 break; 1095 case BUILT_IN_POWL: 1096 log_cfn = CFN_BUILT_IN_LOGL; 1097 exp_bfn = BUILT_IN_EXPL; 1098 break; 1099 default: 1100 return NULL; 1101 } 1102 tree logc = fold_const_call (log_cfn, TREE_TYPE (base), base); 1103 tree exp_decl = builtin_decl_implicit (exp_bfn); 1104 /* Optimize pow (C, x) as exp (log (C) * x). Normally match.pd 1105 does that, but if C is a power of 2, we want to use 1106 exp2 (log2 (C) * x) in the non-vectorized version, but for 1107 vectorization we don't have vectorized exp2. */ 1108 if (logc 1109 && TREE_CODE (logc) == REAL_CST 1110 && exp_decl 1111 && lookup_attribute ("omp declare simd", 1112 DECL_ATTRIBUTES (exp_decl))) 1113 { 1114 cgraph_node *node = cgraph_node::get_create (exp_decl); 1115 if (node->simd_clones == NULL) 1116 { 1117 if (targetm.simd_clone.compute_vecsize_and_simdlen == NULL 1118 || node->definition) 1119 return NULL; 1120 expand_simd_clones (node); 1121 if (node->simd_clones == NULL) 1122 return NULL; 1123 } 1124 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 1125 tree def = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL); 1126 gimple *g = gimple_build_assign (def, MULT_EXPR, exp, logc); 1127 new_pattern_def_seq (stmt_vinfo, g); 1128 *type_in = TREE_TYPE (base); 1129 *type_out = NULL_TREE; 1130 tree res = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL); 1131 g = gimple_build_call (exp_decl, 1, def); 1132 gimple_call_set_lhs (g, res); 1133 return g; 1134 } 1135 } 1136 1137 return NULL; 1138 } 1139 1140 /* We now have a pow or powi builtin function call with a constant 1141 exponent. */ 1142 1143 *type_out = NULL_TREE; 1144 1145 /* Catch squaring. */ 1146 if ((tree_fits_shwi_p (exp) 1147 && tree_to_shwi (exp) == 2) 1148 || (TREE_CODE (exp) == REAL_CST 1149 && real_equal (&TREE_REAL_CST (exp), &dconst2))) 1150 { 1151 *type_in = TREE_TYPE (base); 1152 1153 var = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL); 1154 stmt = gimple_build_assign (var, MULT_EXPR, base, base); 1155 return stmt; 1156 } 1157 1158 /* Catch square root. */ 1159 if (TREE_CODE (exp) == REAL_CST 1160 && real_equal (&TREE_REAL_CST (exp), &dconsthalf)) 1161 { 1162 *type_in = get_vectype_for_scalar_type (TREE_TYPE (base)); 1163 if (*type_in 1164 && direct_internal_fn_supported_p (IFN_SQRT, *type_in, 1165 OPTIMIZE_FOR_SPEED)) 1166 { 1167 gcall *stmt = gimple_build_call_internal (IFN_SQRT, 1, base); 1168 var = vect_recog_temp_ssa_var (TREE_TYPE (base), stmt); 1169 gimple_call_set_lhs (stmt, var); 1170 gimple_call_set_nothrow (stmt, true); 1171 return stmt; 1172 } 1173 } 1174 1175 return NULL; 1176 } 1177 1178 1179 /* Function vect_recog_widen_sum_pattern 1180 1181 Try to find the following pattern: 1182 1183 type x_t; 1184 TYPE x_T, sum = init; 1185 loop: 1186 sum_0 = phi <init, sum_1> 1187 S1 x_t = *p; 1188 S2 x_T = (TYPE) x_t; 1189 S3 sum_1 = x_T + sum_0; 1190 1191 where type 'TYPE' is at least double the size of type 'type', i.e - we're 1192 summing elements of type 'type' into an accumulator of type 'TYPE'. This is 1193 a special case of a reduction computation. 1194 1195 Input: 1196 1197 * LAST_STMT: A stmt from which the pattern search begins. In the example, 1198 when this function is called with S3, the pattern {S2,S3} will be detected. 1199 1200 Output: 1201 1202 * TYPE_IN: The type of the input arguments to the pattern. 1203 1204 * TYPE_OUT: The type of the output of this pattern. 1205 1206 * Return value: A new stmt that will be used to replace the sequence of 1207 stmts that constitute the pattern. In this case it will be: 1208 WIDEN_SUM <x_t, sum_0> 1209 1210 Note: The widening-sum idiom is a widening reduction pattern that is 1211 vectorized without preserving all the intermediate results. It 1212 produces only N/2 (widened) results (by summing up pairs of 1213 intermediate results) rather than all N results. Therefore, we 1214 cannot allow this pattern when we want to get all the results and in 1215 the correct order (as is the case when this computation is in an 1216 inner-loop nested in an outer-loop that us being vectorized). */ 1217 1218 static gimple * 1219 vect_recog_widen_sum_pattern (vec<gimple *> *stmts, tree *type_in, 1220 tree *type_out) 1221 { 1222 gimple *stmt, *last_stmt = (*stmts)[0]; 1223 tree oprnd0, oprnd1; 1224 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 1225 tree type, half_type; 1226 gimple *pattern_stmt; 1227 loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo); 1228 struct loop *loop; 1229 tree var; 1230 bool promotion; 1231 1232 if (!loop_info) 1233 return NULL; 1234 1235 loop = LOOP_VINFO_LOOP (loop_info); 1236 1237 /* We don't allow changing the order of the computation in the inner-loop 1238 when doing outer-loop vectorization. */ 1239 if (loop && nested_in_vect_loop_p (loop, last_stmt)) 1240 return NULL; 1241 1242 if (!is_gimple_assign (last_stmt)) 1243 return NULL; 1244 1245 type = gimple_expr_type (last_stmt); 1246 1247 /* Look for the following pattern 1248 DX = (TYPE) X; 1249 sum_1 = DX + sum_0; 1250 In which DX is at least double the size of X, and sum_1 has been 1251 recognized as a reduction variable. 1252 */ 1253 1254 /* Starting from LAST_STMT, follow the defs of its uses in search 1255 of the above pattern. */ 1256 1257 if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR) 1258 return NULL; 1259 1260 if (!vect_reassociating_reduction_p (stmt_vinfo)) 1261 return NULL; 1262 1263 oprnd0 = gimple_assign_rhs1 (last_stmt); 1264 oprnd1 = gimple_assign_rhs2 (last_stmt); 1265 if (!types_compatible_p (TREE_TYPE (oprnd0), type) 1266 || !types_compatible_p (TREE_TYPE (oprnd1), type)) 1267 return NULL; 1268 1269 /* So far so good. Since last_stmt was detected as a (summation) reduction, 1270 we know that oprnd1 is the reduction variable (defined by a loop-header 1271 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body. 1272 Left to check that oprnd0 is defined by a cast from type 'type' to type 1273 'TYPE'. */ 1274 1275 if (!type_conversion_p (oprnd0, last_stmt, true, &half_type, &stmt, 1276 &promotion) 1277 || !promotion) 1278 return NULL; 1279 1280 oprnd0 = gimple_assign_rhs1 (stmt); 1281 *type_in = half_type; 1282 *type_out = type; 1283 1284 /* Pattern detected. Create a stmt to be used to replace the pattern: */ 1285 var = vect_recog_temp_ssa_var (type, NULL); 1286 pattern_stmt = gimple_build_assign (var, WIDEN_SUM_EXPR, oprnd0, oprnd1); 1287 1288 if (dump_enabled_p ()) 1289 { 1290 dump_printf_loc (MSG_NOTE, vect_location, 1291 "vect_recog_widen_sum_pattern: detected: "); 1292 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 1293 } 1294 1295 return pattern_stmt; 1296 } 1297 1298 1299 /* Return TRUE if the operation in STMT can be performed on a smaller type. 1300 1301 Input: 1302 STMT - a statement to check. 1303 DEF - we support operations with two operands, one of which is constant. 1304 The other operand can be defined by a demotion operation, or by a 1305 previous statement in a sequence of over-promoted operations. In the 1306 later case DEF is used to replace that operand. (It is defined by a 1307 pattern statement we created for the previous statement in the 1308 sequence). 1309 1310 Input/output: 1311 NEW_TYPE - Output: a smaller type that we are trying to use. Input: if not 1312 NULL, it's the type of DEF. 1313 STMTS - additional pattern statements. If a pattern statement (type 1314 conversion) is created in this function, its original statement is 1315 added to STMTS. 1316 1317 Output: 1318 OP0, OP1 - if the operation fits a smaller type, OP0 and OP1 are the new 1319 operands to use in the new pattern statement for STMT (will be created 1320 in vect_recog_over_widening_pattern ()). 1321 NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern 1322 statements for STMT: the first one is a type promotion and the second 1323 one is the operation itself. We return the type promotion statement 1324 in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_SEQ of 1325 the second pattern statement. */ 1326 1327 static bool 1328 vect_operation_fits_smaller_type (gimple *stmt, tree def, tree *new_type, 1329 tree *op0, tree *op1, gimple **new_def_stmt, 1330 vec<gimple *> *stmts) 1331 { 1332 enum tree_code code; 1333 tree const_oprnd, oprnd; 1334 tree interm_type = NULL_TREE, half_type, new_oprnd, type; 1335 gimple *def_stmt, *new_stmt; 1336 bool first = false; 1337 bool promotion; 1338 1339 *op0 = NULL_TREE; 1340 *op1 = NULL_TREE; 1341 *new_def_stmt = NULL; 1342 1343 if (!is_gimple_assign (stmt)) 1344 return false; 1345 1346 code = gimple_assign_rhs_code (stmt); 1347 if (code != LSHIFT_EXPR && code != RSHIFT_EXPR 1348 && code != BIT_IOR_EXPR && code != BIT_XOR_EXPR && code != BIT_AND_EXPR) 1349 return false; 1350 1351 oprnd = gimple_assign_rhs1 (stmt); 1352 const_oprnd = gimple_assign_rhs2 (stmt); 1353 type = gimple_expr_type (stmt); 1354 1355 if (TREE_CODE (oprnd) != SSA_NAME 1356 || TREE_CODE (const_oprnd) != INTEGER_CST) 1357 return false; 1358 1359 /* If oprnd has other uses besides that in stmt we cannot mark it 1360 as being part of a pattern only. */ 1361 if (!has_single_use (oprnd)) 1362 return false; 1363 1364 /* If we are in the middle of a sequence, we use DEF from a previous 1365 statement. Otherwise, OPRND has to be a result of type promotion. */ 1366 if (*new_type) 1367 { 1368 half_type = *new_type; 1369 oprnd = def; 1370 } 1371 else 1372 { 1373 first = true; 1374 if (!type_conversion_p (oprnd, stmt, false, &half_type, &def_stmt, 1375 &promotion) 1376 || !promotion 1377 || !vect_same_loop_or_bb_p (stmt, def_stmt)) 1378 return false; 1379 } 1380 1381 /* Can we perform the operation on a smaller type? */ 1382 switch (code) 1383 { 1384 case BIT_IOR_EXPR: 1385 case BIT_XOR_EXPR: 1386 case BIT_AND_EXPR: 1387 if (!int_fits_type_p (const_oprnd, half_type)) 1388 { 1389 /* HALF_TYPE is not enough. Try a bigger type if possible. */ 1390 if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4)) 1391 return false; 1392 1393 interm_type = build_nonstandard_integer_type ( 1394 TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type)); 1395 if (!int_fits_type_p (const_oprnd, interm_type)) 1396 return false; 1397 } 1398 1399 break; 1400 1401 case LSHIFT_EXPR: 1402 /* Try intermediate type - HALF_TYPE is not enough for sure. */ 1403 if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4)) 1404 return false; 1405 1406 /* Check that HALF_TYPE size + shift amount <= INTERM_TYPE size. 1407 (e.g., if the original value was char, the shift amount is at most 8 1408 if we want to use short). */ 1409 if (compare_tree_int (const_oprnd, TYPE_PRECISION (half_type)) == 1) 1410 return false; 1411 1412 interm_type = build_nonstandard_integer_type ( 1413 TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type)); 1414 1415 if (!vect_supportable_shift (code, interm_type)) 1416 return false; 1417 1418 break; 1419 1420 case RSHIFT_EXPR: 1421 if (vect_supportable_shift (code, half_type)) 1422 break; 1423 1424 /* Try intermediate type - HALF_TYPE is not supported. */ 1425 if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4)) 1426 return false; 1427 1428 interm_type = build_nonstandard_integer_type ( 1429 TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type)); 1430 1431 if (!vect_supportable_shift (code, interm_type)) 1432 return false; 1433 1434 break; 1435 1436 default: 1437 gcc_unreachable (); 1438 } 1439 1440 /* There are four possible cases: 1441 1. OPRND is defined by a type promotion (in that case FIRST is TRUE, it's 1442 the first statement in the sequence) 1443 a. The original, HALF_TYPE, is not enough - we replace the promotion 1444 from HALF_TYPE to TYPE with a promotion to INTERM_TYPE. 1445 b. HALF_TYPE is sufficient, OPRND is set as the RHS of the original 1446 promotion. 1447 2. OPRND is defined by a pattern statement we created. 1448 a. Its type is not sufficient for the operation, we create a new stmt: 1449 a type conversion for OPRND from HALF_TYPE to INTERM_TYPE. We store 1450 this statement in NEW_DEF_STMT, and it is later put in 1451 STMT_VINFO_PATTERN_DEF_SEQ of the pattern statement for STMT. 1452 b. OPRND is good to use in the new statement. */ 1453 if (first) 1454 { 1455 if (interm_type) 1456 { 1457 /* Replace the original type conversion HALF_TYPE->TYPE with 1458 HALF_TYPE->INTERM_TYPE. */ 1459 if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt))) 1460 { 1461 new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)); 1462 /* Check if the already created pattern stmt is what we need. */ 1463 if (!is_gimple_assign (new_stmt) 1464 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (new_stmt)) 1465 || TREE_TYPE (gimple_assign_lhs (new_stmt)) != interm_type) 1466 return false; 1467 1468 stmts->safe_push (def_stmt); 1469 oprnd = gimple_assign_lhs (new_stmt); 1470 } 1471 else 1472 { 1473 /* Create NEW_OPRND = (INTERM_TYPE) OPRND. */ 1474 oprnd = gimple_assign_rhs1 (def_stmt); 1475 new_oprnd = make_ssa_name (interm_type); 1476 new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, oprnd); 1477 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt; 1478 stmts->safe_push (def_stmt); 1479 oprnd = new_oprnd; 1480 } 1481 } 1482 else 1483 { 1484 /* Retrieve the operand before the type promotion. */ 1485 oprnd = gimple_assign_rhs1 (def_stmt); 1486 } 1487 } 1488 else 1489 { 1490 if (interm_type) 1491 { 1492 /* Create a type conversion HALF_TYPE->INTERM_TYPE. */ 1493 new_oprnd = make_ssa_name (interm_type); 1494 new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, oprnd); 1495 oprnd = new_oprnd; 1496 *new_def_stmt = new_stmt; 1497 } 1498 1499 /* Otherwise, OPRND is already set. */ 1500 } 1501 1502 if (interm_type) 1503 *new_type = interm_type; 1504 else 1505 *new_type = half_type; 1506 1507 *op0 = oprnd; 1508 *op1 = fold_convert (*new_type, const_oprnd); 1509 1510 return true; 1511 } 1512 1513 1514 /* Try to find a statement or a sequence of statements that can be performed 1515 on a smaller type: 1516 1517 type x_t; 1518 TYPE x_T, res0_T, res1_T; 1519 loop: 1520 S1 x_t = *p; 1521 S2 x_T = (TYPE) x_t; 1522 S3 res0_T = op (x_T, C0); 1523 S4 res1_T = op (res0_T, C1); 1524 S5 ... = () res1_T; - type demotion 1525 1526 where type 'TYPE' is at least double the size of type 'type', C0 and C1 are 1527 constants. 1528 Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either 1529 be 'type' or some intermediate type. For now, we expect S5 to be a type 1530 demotion operation. We also check that S3 and S4 have only one use. */ 1531 1532 static gimple * 1533 vect_recog_over_widening_pattern (vec<gimple *> *stmts, 1534 tree *type_in, tree *type_out) 1535 { 1536 gimple *stmt = stmts->pop (); 1537 gimple *pattern_stmt = NULL, *new_def_stmt, *prev_stmt = NULL, 1538 *use_stmt = NULL; 1539 tree op0, op1, vectype = NULL_TREE, use_lhs, use_type; 1540 tree var = NULL_TREE, new_type = NULL_TREE, new_oprnd; 1541 bool first; 1542 tree type = NULL; 1543 1544 first = true; 1545 while (1) 1546 { 1547 if (!vinfo_for_stmt (stmt) 1548 || STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (stmt))) 1549 return NULL; 1550 1551 new_def_stmt = NULL; 1552 if (!vect_operation_fits_smaller_type (stmt, var, &new_type, 1553 &op0, &op1, &new_def_stmt, 1554 stmts)) 1555 { 1556 if (first) 1557 return NULL; 1558 else 1559 break; 1560 } 1561 1562 /* STMT can be performed on a smaller type. Check its uses. */ 1563 use_stmt = vect_single_imm_use (stmt); 1564 if (!use_stmt || !is_gimple_assign (use_stmt)) 1565 return NULL; 1566 1567 /* Create pattern statement for STMT. */ 1568 vectype = get_vectype_for_scalar_type (new_type); 1569 if (!vectype) 1570 return NULL; 1571 1572 /* We want to collect all the statements for which we create pattern 1573 statetments, except for the case when the last statement in the 1574 sequence doesn't have a corresponding pattern statement. In such 1575 case we associate the last pattern statement with the last statement 1576 in the sequence. Therefore, we only add the original statement to 1577 the list if we know that it is not the last. */ 1578 if (prev_stmt) 1579 stmts->safe_push (prev_stmt); 1580 1581 var = vect_recog_temp_ssa_var (new_type, NULL); 1582 pattern_stmt 1583 = gimple_build_assign (var, gimple_assign_rhs_code (stmt), op0, op1); 1584 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt; 1585 new_pattern_def_seq (vinfo_for_stmt (stmt), new_def_stmt); 1586 1587 if (dump_enabled_p ()) 1588 { 1589 dump_printf_loc (MSG_NOTE, vect_location, 1590 "created pattern stmt: "); 1591 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 1592 } 1593 1594 type = gimple_expr_type (stmt); 1595 prev_stmt = stmt; 1596 stmt = use_stmt; 1597 1598 first = false; 1599 } 1600 1601 /* We got a sequence. We expect it to end with a type demotion operation. 1602 Otherwise, we quit (for now). There are three possible cases: the 1603 conversion is to NEW_TYPE (we don't do anything), the conversion is to 1604 a type bigger than NEW_TYPE and/or the signedness of USE_TYPE and 1605 NEW_TYPE differs (we create a new conversion statement). */ 1606 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))) 1607 { 1608 use_lhs = gimple_assign_lhs (use_stmt); 1609 use_type = TREE_TYPE (use_lhs); 1610 /* Support only type demotion or signedess change. */ 1611 if (!INTEGRAL_TYPE_P (use_type) 1612 || TYPE_PRECISION (type) <= TYPE_PRECISION (use_type)) 1613 return NULL; 1614 1615 /* Check that NEW_TYPE is not bigger than the conversion result. */ 1616 if (TYPE_PRECISION (new_type) > TYPE_PRECISION (use_type)) 1617 return NULL; 1618 1619 if (TYPE_UNSIGNED (new_type) != TYPE_UNSIGNED (use_type) 1620 || TYPE_PRECISION (new_type) != TYPE_PRECISION (use_type)) 1621 { 1622 /* Create NEW_TYPE->USE_TYPE conversion. */ 1623 new_oprnd = make_ssa_name (use_type); 1624 pattern_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, var); 1625 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt)) = pattern_stmt; 1626 1627 *type_in = get_vectype_for_scalar_type (new_type); 1628 *type_out = get_vectype_for_scalar_type (use_type); 1629 1630 /* We created a pattern statement for the last statement in the 1631 sequence, so we don't need to associate it with the pattern 1632 statement created for PREV_STMT. Therefore, we add PREV_STMT 1633 to the list in order to mark it later in vect_pattern_recog_1. */ 1634 if (prev_stmt) 1635 stmts->safe_push (prev_stmt); 1636 } 1637 else 1638 { 1639 if (prev_stmt) 1640 STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (use_stmt)) 1641 = STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (prev_stmt)); 1642 1643 *type_in = vectype; 1644 *type_out = NULL_TREE; 1645 } 1646 1647 stmts->safe_push (use_stmt); 1648 } 1649 else 1650 /* TODO: support general case, create a conversion to the correct type. */ 1651 return NULL; 1652 1653 /* Pattern detected. */ 1654 if (dump_enabled_p ()) 1655 { 1656 dump_printf_loc (MSG_NOTE, vect_location, 1657 "vect_recog_over_widening_pattern: detected: "); 1658 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 1659 } 1660 1661 return pattern_stmt; 1662 } 1663 1664 /* Detect widening shift pattern: 1665 1666 type a_t; 1667 TYPE a_T, res_T; 1668 1669 S1 a_t = ; 1670 S2 a_T = (TYPE) a_t; 1671 S3 res_T = a_T << CONST; 1672 1673 where type 'TYPE' is at least double the size of type 'type'. 1674 1675 Also detect cases where the shift result is immediately converted 1676 to another type 'result_type' that is no larger in size than 'TYPE'. 1677 In those cases we perform a widen-shift that directly results in 1678 'result_type', to avoid a possible over-widening situation: 1679 1680 type a_t; 1681 TYPE a_T, res_T; 1682 result_type res_result; 1683 1684 S1 a_t = ; 1685 S2 a_T = (TYPE) a_t; 1686 S3 res_T = a_T << CONST; 1687 S4 res_result = (result_type) res_T; 1688 '--> res_result' = a_t w<< CONST; 1689 1690 And a case when 'TYPE' is 4 times bigger than 'type'. In that case we 1691 create an additional pattern stmt for S2 to create a variable of an 1692 intermediate type, and perform widen-shift on the intermediate type: 1693 1694 type a_t; 1695 interm_type a_it; 1696 TYPE a_T, res_T, res_T'; 1697 1698 S1 a_t = ; 1699 S2 a_T = (TYPE) a_t; 1700 '--> a_it = (interm_type) a_t; 1701 S3 res_T = a_T << CONST; 1702 '--> res_T' = a_it <<* CONST; 1703 1704 Input/Output: 1705 1706 * STMTS: Contains a stmt from which the pattern search begins. 1707 In case of unsigned widen-shift, the original stmt (S3) is replaced with S4 1708 in STMTS. When an intermediate type is used and a pattern statement is 1709 created for S2, we also put S2 here (before S3). 1710 1711 Output: 1712 1713 * TYPE_IN: The type of the input arguments to the pattern. 1714 1715 * TYPE_OUT: The type of the output of this pattern. 1716 1717 * Return value: A new stmt that will be used to replace the sequence of 1718 stmts that constitute the pattern. In this case it will be: 1719 WIDEN_LSHIFT_EXPR <a_t, CONST>. */ 1720 1721 static gimple * 1722 vect_recog_widen_shift_pattern (vec<gimple *> *stmts, 1723 tree *type_in, tree *type_out) 1724 { 1725 gimple *last_stmt = stmts->pop (); 1726 gimple *def_stmt0; 1727 tree oprnd0, oprnd1; 1728 tree type, half_type0; 1729 gimple *pattern_stmt; 1730 tree vectype, vectype_out = NULL_TREE; 1731 tree var; 1732 enum tree_code dummy_code; 1733 int dummy_int; 1734 vec<tree> dummy_vec; 1735 gimple *use_stmt; 1736 bool promotion; 1737 1738 if (!is_gimple_assign (last_stmt) || !vinfo_for_stmt (last_stmt)) 1739 return NULL; 1740 1741 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt))) 1742 return NULL; 1743 1744 if (gimple_assign_rhs_code (last_stmt) != LSHIFT_EXPR) 1745 return NULL; 1746 1747 oprnd0 = gimple_assign_rhs1 (last_stmt); 1748 oprnd1 = gimple_assign_rhs2 (last_stmt); 1749 if (TREE_CODE (oprnd0) != SSA_NAME || TREE_CODE (oprnd1) != INTEGER_CST) 1750 return NULL; 1751 1752 /* Check operand 0: it has to be defined by a type promotion. */ 1753 if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0, 1754 &promotion) 1755 || !promotion) 1756 return NULL; 1757 1758 /* Check operand 1: has to be positive. We check that it fits the type 1759 in vect_handle_widen_op_by_const (). */ 1760 if (tree_int_cst_compare (oprnd1, size_zero_node) <= 0) 1761 return NULL; 1762 1763 oprnd0 = gimple_assign_rhs1 (def_stmt0); 1764 type = gimple_expr_type (last_stmt); 1765 1766 /* Check for subsequent conversion to another type. */ 1767 use_stmt = vect_single_imm_use (last_stmt); 1768 if (use_stmt && is_gimple_assign (use_stmt) 1769 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)) 1770 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt))) 1771 { 1772 tree use_lhs = gimple_assign_lhs (use_stmt); 1773 tree use_type = TREE_TYPE (use_lhs); 1774 1775 if (INTEGRAL_TYPE_P (use_type) 1776 && TYPE_PRECISION (use_type) <= TYPE_PRECISION (type)) 1777 { 1778 last_stmt = use_stmt; 1779 type = use_type; 1780 } 1781 } 1782 1783 /* Check if this a widening operation. */ 1784 gimple *wstmt = NULL; 1785 if (!vect_handle_widen_op_by_const (last_stmt, LSHIFT_EXPR, oprnd1, 1786 &oprnd0, &wstmt, 1787 type, &half_type0, def_stmt0)) 1788 return NULL; 1789 1790 /* Pattern detected. */ 1791 if (dump_enabled_p ()) 1792 dump_printf_loc (MSG_NOTE, vect_location, 1793 "vect_recog_widen_shift_pattern: detected:\n"); 1794 1795 /* Check target support. */ 1796 vectype = get_vectype_for_scalar_type (half_type0); 1797 vectype_out = get_vectype_for_scalar_type (type); 1798 1799 if (!vectype 1800 || !vectype_out 1801 || !supportable_widening_operation (WIDEN_LSHIFT_EXPR, last_stmt, 1802 vectype_out, vectype, 1803 &dummy_code, &dummy_code, 1804 &dummy_int, &dummy_vec)) 1805 return NULL; 1806 1807 *type_in = vectype; 1808 *type_out = vectype_out; 1809 1810 /* Pattern supported. Create a stmt to be used to replace the pattern. */ 1811 var = vect_recog_temp_ssa_var (type, NULL); 1812 pattern_stmt 1813 = gimple_build_assign (var, WIDEN_LSHIFT_EXPR, oprnd0, oprnd1); 1814 if (wstmt) 1815 { 1816 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 1817 new_pattern_def_seq (stmt_vinfo, wstmt); 1818 stmt_vec_info new_stmt_info 1819 = new_stmt_vec_info (wstmt, stmt_vinfo->vinfo); 1820 set_vinfo_for_stmt (wstmt, new_stmt_info); 1821 STMT_VINFO_VECTYPE (new_stmt_info) = vectype; 1822 } 1823 1824 if (dump_enabled_p ()) 1825 dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0); 1826 1827 stmts->safe_push (last_stmt); 1828 return pattern_stmt; 1829 } 1830 1831 /* Detect a rotate pattern wouldn't be otherwise vectorized: 1832 1833 type a_t, b_t, c_t; 1834 1835 S0 a_t = b_t r<< c_t; 1836 1837 Input/Output: 1838 1839 * STMTS: Contains a stmt from which the pattern search begins, 1840 i.e. the shift/rotate stmt. The original stmt (S0) is replaced 1841 with a sequence: 1842 1843 S1 d_t = -c_t; 1844 S2 e_t = d_t & (B - 1); 1845 S3 f_t = b_t << c_t; 1846 S4 g_t = b_t >> e_t; 1847 S0 a_t = f_t | g_t; 1848 1849 where B is element bitsize of type. 1850 1851 Output: 1852 1853 * TYPE_IN: The type of the input arguments to the pattern. 1854 1855 * TYPE_OUT: The type of the output of this pattern. 1856 1857 * Return value: A new stmt that will be used to replace the rotate 1858 S0 stmt. */ 1859 1860 static gimple * 1861 vect_recog_rotate_pattern (vec<gimple *> *stmts, tree *type_in, tree *type_out) 1862 { 1863 gimple *last_stmt = stmts->pop (); 1864 tree oprnd0, oprnd1, lhs, var, var1, var2, vectype, type, stype, def, def2; 1865 gimple *pattern_stmt, *def_stmt; 1866 enum tree_code rhs_code; 1867 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 1868 vec_info *vinfo = stmt_vinfo->vinfo; 1869 enum vect_def_type dt; 1870 optab optab1, optab2; 1871 edge ext_def = NULL; 1872 1873 if (!is_gimple_assign (last_stmt)) 1874 return NULL; 1875 1876 rhs_code = gimple_assign_rhs_code (last_stmt); 1877 switch (rhs_code) 1878 { 1879 case LROTATE_EXPR: 1880 case RROTATE_EXPR: 1881 break; 1882 default: 1883 return NULL; 1884 } 1885 1886 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 1887 return NULL; 1888 1889 lhs = gimple_assign_lhs (last_stmt); 1890 oprnd0 = gimple_assign_rhs1 (last_stmt); 1891 type = TREE_TYPE (oprnd0); 1892 oprnd1 = gimple_assign_rhs2 (last_stmt); 1893 if (TREE_CODE (oprnd0) != SSA_NAME 1894 || TYPE_PRECISION (TREE_TYPE (lhs)) != TYPE_PRECISION (type) 1895 || !INTEGRAL_TYPE_P (type) 1896 || !TYPE_UNSIGNED (type)) 1897 return NULL; 1898 1899 if (!vect_is_simple_use (oprnd1, vinfo, &def_stmt, &dt)) 1900 return NULL; 1901 1902 if (dt != vect_internal_def 1903 && dt != vect_constant_def 1904 && dt != vect_external_def) 1905 return NULL; 1906 1907 vectype = get_vectype_for_scalar_type (type); 1908 if (vectype == NULL_TREE) 1909 return NULL; 1910 1911 /* If vector/vector or vector/scalar rotate is supported by the target, 1912 don't do anything here. */ 1913 optab1 = optab_for_tree_code (rhs_code, vectype, optab_vector); 1914 if (optab1 1915 && optab_handler (optab1, TYPE_MODE (vectype)) != CODE_FOR_nothing) 1916 return NULL; 1917 1918 if (is_a <bb_vec_info> (vinfo) || dt != vect_internal_def) 1919 { 1920 optab2 = optab_for_tree_code (rhs_code, vectype, optab_scalar); 1921 if (optab2 1922 && optab_handler (optab2, TYPE_MODE (vectype)) != CODE_FOR_nothing) 1923 return NULL; 1924 } 1925 1926 /* If vector/vector or vector/scalar shifts aren't supported by the target, 1927 don't do anything here either. */ 1928 optab1 = optab_for_tree_code (LSHIFT_EXPR, vectype, optab_vector); 1929 optab2 = optab_for_tree_code (RSHIFT_EXPR, vectype, optab_vector); 1930 if (!optab1 1931 || optab_handler (optab1, TYPE_MODE (vectype)) == CODE_FOR_nothing 1932 || !optab2 1933 || optab_handler (optab2, TYPE_MODE (vectype)) == CODE_FOR_nothing) 1934 { 1935 if (! is_a <bb_vec_info> (vinfo) && dt == vect_internal_def) 1936 return NULL; 1937 optab1 = optab_for_tree_code (LSHIFT_EXPR, vectype, optab_scalar); 1938 optab2 = optab_for_tree_code (RSHIFT_EXPR, vectype, optab_scalar); 1939 if (!optab1 1940 || optab_handler (optab1, TYPE_MODE (vectype)) == CODE_FOR_nothing 1941 || !optab2 1942 || optab_handler (optab2, TYPE_MODE (vectype)) == CODE_FOR_nothing) 1943 return NULL; 1944 } 1945 1946 *type_in = vectype; 1947 *type_out = vectype; 1948 if (*type_in == NULL_TREE) 1949 return NULL; 1950 1951 if (dt == vect_external_def 1952 && TREE_CODE (oprnd1) == SSA_NAME 1953 && is_a <loop_vec_info> (vinfo)) 1954 { 1955 struct loop *loop = as_a <loop_vec_info> (vinfo)->loop; 1956 ext_def = loop_preheader_edge (loop); 1957 if (!SSA_NAME_IS_DEFAULT_DEF (oprnd1)) 1958 { 1959 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (oprnd1)); 1960 if (bb == NULL 1961 || !dominated_by_p (CDI_DOMINATORS, ext_def->dest, bb)) 1962 ext_def = NULL; 1963 } 1964 } 1965 1966 def = NULL_TREE; 1967 scalar_int_mode mode = SCALAR_INT_TYPE_MODE (type); 1968 if (TREE_CODE (oprnd1) == INTEGER_CST 1969 || TYPE_MODE (TREE_TYPE (oprnd1)) == mode) 1970 def = oprnd1; 1971 else if (def_stmt && gimple_assign_cast_p (def_stmt)) 1972 { 1973 tree rhs1 = gimple_assign_rhs1 (def_stmt); 1974 if (TYPE_MODE (TREE_TYPE (rhs1)) == mode 1975 && TYPE_PRECISION (TREE_TYPE (rhs1)) 1976 == TYPE_PRECISION (type)) 1977 def = rhs1; 1978 } 1979 1980 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL; 1981 if (def == NULL_TREE) 1982 { 1983 def = vect_recog_temp_ssa_var (type, NULL); 1984 def_stmt = gimple_build_assign (def, NOP_EXPR, oprnd1); 1985 if (ext_def) 1986 { 1987 basic_block new_bb 1988 = gsi_insert_on_edge_immediate (ext_def, def_stmt); 1989 gcc_assert (!new_bb); 1990 } 1991 else 1992 append_pattern_def_seq (stmt_vinfo, def_stmt); 1993 } 1994 stype = TREE_TYPE (def); 1995 scalar_int_mode smode = SCALAR_INT_TYPE_MODE (stype); 1996 1997 if (TREE_CODE (def) == INTEGER_CST) 1998 { 1999 if (!tree_fits_uhwi_p (def) 2000 || tree_to_uhwi (def) >= GET_MODE_PRECISION (mode) 2001 || integer_zerop (def)) 2002 return NULL; 2003 def2 = build_int_cst (stype, 2004 GET_MODE_PRECISION (mode) - tree_to_uhwi (def)); 2005 } 2006 else 2007 { 2008 tree vecstype = get_vectype_for_scalar_type (stype); 2009 stmt_vec_info def_stmt_vinfo; 2010 2011 if (vecstype == NULL_TREE) 2012 return NULL; 2013 def2 = vect_recog_temp_ssa_var (stype, NULL); 2014 def_stmt = gimple_build_assign (def2, NEGATE_EXPR, def); 2015 if (ext_def) 2016 { 2017 basic_block new_bb 2018 = gsi_insert_on_edge_immediate (ext_def, def_stmt); 2019 gcc_assert (!new_bb); 2020 } 2021 else 2022 { 2023 def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo); 2024 set_vinfo_for_stmt (def_stmt, def_stmt_vinfo); 2025 STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype; 2026 append_pattern_def_seq (stmt_vinfo, def_stmt); 2027 } 2028 2029 def2 = vect_recog_temp_ssa_var (stype, NULL); 2030 tree mask = build_int_cst (stype, GET_MODE_PRECISION (smode) - 1); 2031 def_stmt = gimple_build_assign (def2, BIT_AND_EXPR, 2032 gimple_assign_lhs (def_stmt), mask); 2033 if (ext_def) 2034 { 2035 basic_block new_bb 2036 = gsi_insert_on_edge_immediate (ext_def, def_stmt); 2037 gcc_assert (!new_bb); 2038 } 2039 else 2040 { 2041 def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo); 2042 set_vinfo_for_stmt (def_stmt, def_stmt_vinfo); 2043 STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype; 2044 append_pattern_def_seq (stmt_vinfo, def_stmt); 2045 } 2046 } 2047 2048 var1 = vect_recog_temp_ssa_var (type, NULL); 2049 def_stmt = gimple_build_assign (var1, rhs_code == LROTATE_EXPR 2050 ? LSHIFT_EXPR : RSHIFT_EXPR, 2051 oprnd0, def); 2052 append_pattern_def_seq (stmt_vinfo, def_stmt); 2053 2054 var2 = vect_recog_temp_ssa_var (type, NULL); 2055 def_stmt = gimple_build_assign (var2, rhs_code == LROTATE_EXPR 2056 ? RSHIFT_EXPR : LSHIFT_EXPR, 2057 oprnd0, def2); 2058 append_pattern_def_seq (stmt_vinfo, def_stmt); 2059 2060 /* Pattern detected. */ 2061 if (dump_enabled_p ()) 2062 dump_printf_loc (MSG_NOTE, vect_location, 2063 "vect_recog_rotate_pattern: detected:\n"); 2064 2065 /* Pattern supported. Create a stmt to be used to replace the pattern. */ 2066 var = vect_recog_temp_ssa_var (type, NULL); 2067 pattern_stmt = gimple_build_assign (var, BIT_IOR_EXPR, var1, var2); 2068 2069 if (dump_enabled_p ()) 2070 dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0); 2071 2072 stmts->safe_push (last_stmt); 2073 return pattern_stmt; 2074 } 2075 2076 /* Detect a vector by vector shift pattern that wouldn't be otherwise 2077 vectorized: 2078 2079 type a_t; 2080 TYPE b_T, res_T; 2081 2082 S1 a_t = ; 2083 S2 b_T = ; 2084 S3 res_T = b_T op a_t; 2085 2086 where type 'TYPE' is a type with different size than 'type', 2087 and op is <<, >> or rotate. 2088 2089 Also detect cases: 2090 2091 type a_t; 2092 TYPE b_T, c_T, res_T; 2093 2094 S0 c_T = ; 2095 S1 a_t = (type) c_T; 2096 S2 b_T = ; 2097 S3 res_T = b_T op a_t; 2098 2099 Input/Output: 2100 2101 * STMTS: Contains a stmt from which the pattern search begins, 2102 i.e. the shift/rotate stmt. The original stmt (S3) is replaced 2103 with a shift/rotate which has same type on both operands, in the 2104 second case just b_T op c_T, in the first case with added cast 2105 from a_t to c_T in STMT_VINFO_PATTERN_DEF_SEQ. 2106 2107 Output: 2108 2109 * TYPE_IN: The type of the input arguments to the pattern. 2110 2111 * TYPE_OUT: The type of the output of this pattern. 2112 2113 * Return value: A new stmt that will be used to replace the shift/rotate 2114 S3 stmt. */ 2115 2116 static gimple * 2117 vect_recog_vector_vector_shift_pattern (vec<gimple *> *stmts, 2118 tree *type_in, tree *type_out) 2119 { 2120 gimple *last_stmt = stmts->pop (); 2121 tree oprnd0, oprnd1, lhs, var; 2122 gimple *pattern_stmt, *def_stmt; 2123 enum tree_code rhs_code; 2124 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 2125 vec_info *vinfo = stmt_vinfo->vinfo; 2126 enum vect_def_type dt; 2127 2128 if (!is_gimple_assign (last_stmt)) 2129 return NULL; 2130 2131 rhs_code = gimple_assign_rhs_code (last_stmt); 2132 switch (rhs_code) 2133 { 2134 case LSHIFT_EXPR: 2135 case RSHIFT_EXPR: 2136 case LROTATE_EXPR: 2137 case RROTATE_EXPR: 2138 break; 2139 default: 2140 return NULL; 2141 } 2142 2143 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 2144 return NULL; 2145 2146 lhs = gimple_assign_lhs (last_stmt); 2147 oprnd0 = gimple_assign_rhs1 (last_stmt); 2148 oprnd1 = gimple_assign_rhs2 (last_stmt); 2149 if (TREE_CODE (oprnd0) != SSA_NAME 2150 || TREE_CODE (oprnd1) != SSA_NAME 2151 || TYPE_MODE (TREE_TYPE (oprnd0)) == TYPE_MODE (TREE_TYPE (oprnd1)) 2152 || !type_has_mode_precision_p (TREE_TYPE (oprnd1)) 2153 || TYPE_PRECISION (TREE_TYPE (lhs)) 2154 != TYPE_PRECISION (TREE_TYPE (oprnd0))) 2155 return NULL; 2156 2157 if (!vect_is_simple_use (oprnd1, vinfo, &def_stmt, &dt)) 2158 return NULL; 2159 2160 if (dt != vect_internal_def) 2161 return NULL; 2162 2163 *type_in = get_vectype_for_scalar_type (TREE_TYPE (oprnd0)); 2164 *type_out = *type_in; 2165 if (*type_in == NULL_TREE) 2166 return NULL; 2167 2168 tree def = NULL_TREE; 2169 stmt_vec_info def_vinfo = vinfo_for_stmt (def_stmt); 2170 if (!STMT_VINFO_IN_PATTERN_P (def_vinfo) && gimple_assign_cast_p (def_stmt)) 2171 { 2172 tree rhs1 = gimple_assign_rhs1 (def_stmt); 2173 if (TYPE_MODE (TREE_TYPE (rhs1)) == TYPE_MODE (TREE_TYPE (oprnd0)) 2174 && TYPE_PRECISION (TREE_TYPE (rhs1)) 2175 == TYPE_PRECISION (TREE_TYPE (oprnd0))) 2176 { 2177 if (TYPE_PRECISION (TREE_TYPE (oprnd1)) 2178 >= TYPE_PRECISION (TREE_TYPE (rhs1))) 2179 def = rhs1; 2180 else 2181 { 2182 tree mask 2183 = build_low_bits_mask (TREE_TYPE (rhs1), 2184 TYPE_PRECISION (TREE_TYPE (oprnd1))); 2185 def = vect_recog_temp_ssa_var (TREE_TYPE (rhs1), NULL); 2186 def_stmt = gimple_build_assign (def, BIT_AND_EXPR, rhs1, mask); 2187 new_pattern_def_seq (stmt_vinfo, def_stmt); 2188 } 2189 } 2190 } 2191 2192 if (def == NULL_TREE) 2193 { 2194 def = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL); 2195 def_stmt = gimple_build_assign (def, NOP_EXPR, oprnd1); 2196 new_pattern_def_seq (stmt_vinfo, def_stmt); 2197 } 2198 2199 /* Pattern detected. */ 2200 if (dump_enabled_p ()) 2201 dump_printf_loc (MSG_NOTE, vect_location, 2202 "vect_recog_vector_vector_shift_pattern: detected:\n"); 2203 2204 /* Pattern supported. Create a stmt to be used to replace the pattern. */ 2205 var = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL); 2206 pattern_stmt = gimple_build_assign (var, rhs_code, oprnd0, def); 2207 2208 if (dump_enabled_p ()) 2209 dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0); 2210 2211 stmts->safe_push (last_stmt); 2212 return pattern_stmt; 2213 } 2214 2215 /* Return true iff the target has a vector optab implementing the operation 2216 CODE on type VECTYPE. */ 2217 2218 static bool 2219 target_has_vecop_for_code (tree_code code, tree vectype) 2220 { 2221 optab voptab = optab_for_tree_code (code, vectype, optab_vector); 2222 return voptab 2223 && optab_handler (voptab, TYPE_MODE (vectype)) != CODE_FOR_nothing; 2224 } 2225 2226 /* Verify that the target has optabs of VECTYPE to perform all the steps 2227 needed by the multiplication-by-immediate synthesis algorithm described by 2228 ALG and VAR. If SYNTH_SHIFT_P is true ensure that vector addition is 2229 present. Return true iff the target supports all the steps. */ 2230 2231 static bool 2232 target_supports_mult_synth_alg (struct algorithm *alg, mult_variant var, 2233 tree vectype, bool synth_shift_p) 2234 { 2235 if (alg->op[0] != alg_zero && alg->op[0] != alg_m) 2236 return false; 2237 2238 bool supports_vminus = target_has_vecop_for_code (MINUS_EXPR, vectype); 2239 bool supports_vplus = target_has_vecop_for_code (PLUS_EXPR, vectype); 2240 2241 if (var == negate_variant 2242 && !target_has_vecop_for_code (NEGATE_EXPR, vectype)) 2243 return false; 2244 2245 /* If we must synthesize shifts with additions make sure that vector 2246 addition is available. */ 2247 if ((var == add_variant || synth_shift_p) && !supports_vplus) 2248 return false; 2249 2250 for (int i = 1; i < alg->ops; i++) 2251 { 2252 switch (alg->op[i]) 2253 { 2254 case alg_shift: 2255 break; 2256 case alg_add_t_m2: 2257 case alg_add_t2_m: 2258 case alg_add_factor: 2259 if (!supports_vplus) 2260 return false; 2261 break; 2262 case alg_sub_t_m2: 2263 case alg_sub_t2_m: 2264 case alg_sub_factor: 2265 if (!supports_vminus) 2266 return false; 2267 break; 2268 case alg_unknown: 2269 case alg_m: 2270 case alg_zero: 2271 case alg_impossible: 2272 return false; 2273 default: 2274 gcc_unreachable (); 2275 } 2276 } 2277 2278 return true; 2279 } 2280 2281 /* Synthesize a left shift of OP by AMNT bits using a series of additions and 2282 putting the final result in DEST. Append all statements but the last into 2283 VINFO. Return the last statement. */ 2284 2285 static gimple * 2286 synth_lshift_by_additions (tree dest, tree op, HOST_WIDE_INT amnt, 2287 stmt_vec_info vinfo) 2288 { 2289 HOST_WIDE_INT i; 2290 tree itype = TREE_TYPE (op); 2291 tree prev_res = op; 2292 gcc_assert (amnt >= 0); 2293 for (i = 0; i < amnt; i++) 2294 { 2295 tree tmp_var = (i < amnt - 1) ? vect_recog_temp_ssa_var (itype, NULL) 2296 : dest; 2297 gimple *stmt 2298 = gimple_build_assign (tmp_var, PLUS_EXPR, prev_res, prev_res); 2299 prev_res = tmp_var; 2300 if (i < amnt - 1) 2301 append_pattern_def_seq (vinfo, stmt); 2302 else 2303 return stmt; 2304 } 2305 gcc_unreachable (); 2306 return NULL; 2307 } 2308 2309 /* Helper for vect_synth_mult_by_constant. Apply a binary operation 2310 CODE to operands OP1 and OP2, creating a new temporary SSA var in 2311 the process if necessary. Append the resulting assignment statements 2312 to the sequence in STMT_VINFO. Return the SSA variable that holds the 2313 result of the binary operation. If SYNTH_SHIFT_P is true synthesize 2314 left shifts using additions. */ 2315 2316 static tree 2317 apply_binop_and_append_stmt (tree_code code, tree op1, tree op2, 2318 stmt_vec_info stmt_vinfo, bool synth_shift_p) 2319 { 2320 if (integer_zerop (op2) 2321 && (code == LSHIFT_EXPR 2322 || code == PLUS_EXPR)) 2323 { 2324 gcc_assert (TREE_CODE (op1) == SSA_NAME); 2325 return op1; 2326 } 2327 2328 gimple *stmt; 2329 tree itype = TREE_TYPE (op1); 2330 tree tmp_var = vect_recog_temp_ssa_var (itype, NULL); 2331 2332 if (code == LSHIFT_EXPR 2333 && synth_shift_p) 2334 { 2335 stmt = synth_lshift_by_additions (tmp_var, op1, TREE_INT_CST_LOW (op2), 2336 stmt_vinfo); 2337 append_pattern_def_seq (stmt_vinfo, stmt); 2338 return tmp_var; 2339 } 2340 2341 stmt = gimple_build_assign (tmp_var, code, op1, op2); 2342 append_pattern_def_seq (stmt_vinfo, stmt); 2343 return tmp_var; 2344 } 2345 2346 /* Synthesize a multiplication of OP by an INTEGER_CST VAL using shifts 2347 and simple arithmetic operations to be vectorized. Record the statements 2348 produced in STMT_VINFO and return the last statement in the sequence or 2349 NULL if it's not possible to synthesize such a multiplication. 2350 This function mirrors the behavior of expand_mult_const in expmed.c but 2351 works on tree-ssa form. */ 2352 2353 static gimple * 2354 vect_synth_mult_by_constant (tree op, tree val, 2355 stmt_vec_info stmt_vinfo) 2356 { 2357 tree itype = TREE_TYPE (op); 2358 machine_mode mode = TYPE_MODE (itype); 2359 struct algorithm alg; 2360 mult_variant variant; 2361 if (!tree_fits_shwi_p (val)) 2362 return NULL; 2363 2364 /* Multiplication synthesis by shifts, adds and subs can introduce 2365 signed overflow where the original operation didn't. Perform the 2366 operations on an unsigned type and cast back to avoid this. 2367 In the future we may want to relax this for synthesis algorithms 2368 that we can prove do not cause unexpected overflow. */ 2369 bool cast_to_unsigned_p = !TYPE_OVERFLOW_WRAPS (itype); 2370 2371 tree multtype = cast_to_unsigned_p ? unsigned_type_for (itype) : itype; 2372 2373 /* Targets that don't support vector shifts but support vector additions 2374 can synthesize shifts that way. */ 2375 bool synth_shift_p = !vect_supportable_shift (LSHIFT_EXPR, multtype); 2376 2377 HOST_WIDE_INT hwval = tree_to_shwi (val); 2378 /* Use MAX_COST here as we don't want to limit the sequence on rtx costs. 2379 The vectorizer's benefit analysis will decide whether it's beneficial 2380 to do this. */ 2381 bool possible = choose_mult_variant (mode, hwval, &alg, 2382 &variant, MAX_COST); 2383 if (!possible) 2384 return NULL; 2385 2386 tree vectype = get_vectype_for_scalar_type (multtype); 2387 2388 if (!vectype 2389 || !target_supports_mult_synth_alg (&alg, variant, 2390 vectype, synth_shift_p)) 2391 return NULL; 2392 2393 tree accumulator; 2394 2395 /* Clear out the sequence of statements so we can populate it below. */ 2396 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL; 2397 gimple *stmt = NULL; 2398 2399 if (cast_to_unsigned_p) 2400 { 2401 tree tmp_op = vect_recog_temp_ssa_var (multtype, NULL); 2402 stmt = gimple_build_assign (tmp_op, CONVERT_EXPR, op); 2403 append_pattern_def_seq (stmt_vinfo, stmt); 2404 op = tmp_op; 2405 } 2406 2407 if (alg.op[0] == alg_zero) 2408 accumulator = build_int_cst (multtype, 0); 2409 else 2410 accumulator = op; 2411 2412 bool needs_fixup = (variant == negate_variant) 2413 || (variant == add_variant); 2414 2415 for (int i = 1; i < alg.ops; i++) 2416 { 2417 tree shft_log = build_int_cst (multtype, alg.log[i]); 2418 tree accum_tmp = vect_recog_temp_ssa_var (multtype, NULL); 2419 tree tmp_var = NULL_TREE; 2420 2421 switch (alg.op[i]) 2422 { 2423 case alg_shift: 2424 if (synth_shift_p) 2425 stmt 2426 = synth_lshift_by_additions (accum_tmp, accumulator, alg.log[i], 2427 stmt_vinfo); 2428 else 2429 stmt = gimple_build_assign (accum_tmp, LSHIFT_EXPR, accumulator, 2430 shft_log); 2431 break; 2432 case alg_add_t_m2: 2433 tmp_var 2434 = apply_binop_and_append_stmt (LSHIFT_EXPR, op, shft_log, 2435 stmt_vinfo, synth_shift_p); 2436 stmt = gimple_build_assign (accum_tmp, PLUS_EXPR, accumulator, 2437 tmp_var); 2438 break; 2439 case alg_sub_t_m2: 2440 tmp_var = apply_binop_and_append_stmt (LSHIFT_EXPR, op, 2441 shft_log, stmt_vinfo, 2442 synth_shift_p); 2443 /* In some algorithms the first step involves zeroing the 2444 accumulator. If subtracting from such an accumulator 2445 just emit the negation directly. */ 2446 if (integer_zerop (accumulator)) 2447 stmt = gimple_build_assign (accum_tmp, NEGATE_EXPR, tmp_var); 2448 else 2449 stmt = gimple_build_assign (accum_tmp, MINUS_EXPR, accumulator, 2450 tmp_var); 2451 break; 2452 case alg_add_t2_m: 2453 tmp_var 2454 = apply_binop_and_append_stmt (LSHIFT_EXPR, accumulator, shft_log, 2455 stmt_vinfo, synth_shift_p); 2456 stmt = gimple_build_assign (accum_tmp, PLUS_EXPR, tmp_var, op); 2457 break; 2458 case alg_sub_t2_m: 2459 tmp_var 2460 = apply_binop_and_append_stmt (LSHIFT_EXPR, accumulator, shft_log, 2461 stmt_vinfo, synth_shift_p); 2462 stmt = gimple_build_assign (accum_tmp, MINUS_EXPR, tmp_var, op); 2463 break; 2464 case alg_add_factor: 2465 tmp_var 2466 = apply_binop_and_append_stmt (LSHIFT_EXPR, accumulator, shft_log, 2467 stmt_vinfo, synth_shift_p); 2468 stmt = gimple_build_assign (accum_tmp, PLUS_EXPR, accumulator, 2469 tmp_var); 2470 break; 2471 case alg_sub_factor: 2472 tmp_var 2473 = apply_binop_and_append_stmt (LSHIFT_EXPR, accumulator, shft_log, 2474 stmt_vinfo, synth_shift_p); 2475 stmt = gimple_build_assign (accum_tmp, MINUS_EXPR, tmp_var, 2476 accumulator); 2477 break; 2478 default: 2479 gcc_unreachable (); 2480 } 2481 /* We don't want to append the last stmt in the sequence to stmt_vinfo 2482 but rather return it directly. */ 2483 2484 if ((i < alg.ops - 1) || needs_fixup || cast_to_unsigned_p) 2485 append_pattern_def_seq (stmt_vinfo, stmt); 2486 accumulator = accum_tmp; 2487 } 2488 if (variant == negate_variant) 2489 { 2490 tree accum_tmp = vect_recog_temp_ssa_var (multtype, NULL); 2491 stmt = gimple_build_assign (accum_tmp, NEGATE_EXPR, accumulator); 2492 accumulator = accum_tmp; 2493 if (cast_to_unsigned_p) 2494 append_pattern_def_seq (stmt_vinfo, stmt); 2495 } 2496 else if (variant == add_variant) 2497 { 2498 tree accum_tmp = vect_recog_temp_ssa_var (multtype, NULL); 2499 stmt = gimple_build_assign (accum_tmp, PLUS_EXPR, accumulator, op); 2500 accumulator = accum_tmp; 2501 if (cast_to_unsigned_p) 2502 append_pattern_def_seq (stmt_vinfo, stmt); 2503 } 2504 /* Move back to a signed if needed. */ 2505 if (cast_to_unsigned_p) 2506 { 2507 tree accum_tmp = vect_recog_temp_ssa_var (itype, NULL); 2508 stmt = gimple_build_assign (accum_tmp, CONVERT_EXPR, accumulator); 2509 } 2510 2511 return stmt; 2512 } 2513 2514 /* Detect multiplication by constant and convert it into a sequence of 2515 shifts and additions, subtractions, negations. We reuse the 2516 choose_mult_variant algorithms from expmed.c 2517 2518 Input/Output: 2519 2520 STMTS: Contains a stmt from which the pattern search begins, 2521 i.e. the mult stmt. 2522 2523 Output: 2524 2525 * TYPE_IN: The type of the input arguments to the pattern. 2526 2527 * TYPE_OUT: The type of the output of this pattern. 2528 2529 * Return value: A new stmt that will be used to replace 2530 the multiplication. */ 2531 2532 static gimple * 2533 vect_recog_mult_pattern (vec<gimple *> *stmts, 2534 tree *type_in, tree *type_out) 2535 { 2536 gimple *last_stmt = stmts->pop (); 2537 tree oprnd0, oprnd1, vectype, itype; 2538 gimple *pattern_stmt; 2539 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 2540 2541 if (!is_gimple_assign (last_stmt)) 2542 return NULL; 2543 2544 if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR) 2545 return NULL; 2546 2547 oprnd0 = gimple_assign_rhs1 (last_stmt); 2548 oprnd1 = gimple_assign_rhs2 (last_stmt); 2549 itype = TREE_TYPE (oprnd0); 2550 2551 if (TREE_CODE (oprnd0) != SSA_NAME 2552 || TREE_CODE (oprnd1) != INTEGER_CST 2553 || !INTEGRAL_TYPE_P (itype) 2554 || !type_has_mode_precision_p (itype)) 2555 return NULL; 2556 2557 vectype = get_vectype_for_scalar_type (itype); 2558 if (vectype == NULL_TREE) 2559 return NULL; 2560 2561 /* If the target can handle vectorized multiplication natively, 2562 don't attempt to optimize this. */ 2563 optab mul_optab = optab_for_tree_code (MULT_EXPR, vectype, optab_default); 2564 if (mul_optab != unknown_optab) 2565 { 2566 machine_mode vec_mode = TYPE_MODE (vectype); 2567 int icode = (int) optab_handler (mul_optab, vec_mode); 2568 if (icode != CODE_FOR_nothing) 2569 return NULL; 2570 } 2571 2572 pattern_stmt = vect_synth_mult_by_constant (oprnd0, oprnd1, stmt_vinfo); 2573 if (!pattern_stmt) 2574 return NULL; 2575 2576 /* Pattern detected. */ 2577 if (dump_enabled_p ()) 2578 dump_printf_loc (MSG_NOTE, vect_location, 2579 "vect_recog_mult_pattern: detected:\n"); 2580 2581 if (dump_enabled_p ()) 2582 dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, 2583 pattern_stmt,0); 2584 2585 stmts->safe_push (last_stmt); 2586 *type_in = vectype; 2587 *type_out = vectype; 2588 2589 return pattern_stmt; 2590 } 2591 2592 /* Detect a signed division by a constant that wouldn't be 2593 otherwise vectorized: 2594 2595 type a_t, b_t; 2596 2597 S1 a_t = b_t / N; 2598 2599 where type 'type' is an integral type and N is a constant. 2600 2601 Similarly handle modulo by a constant: 2602 2603 S4 a_t = b_t % N; 2604 2605 Input/Output: 2606 2607 * STMTS: Contains a stmt from which the pattern search begins, 2608 i.e. the division stmt. S1 is replaced by if N is a power 2609 of two constant and type is signed: 2610 S3 y_t = b_t < 0 ? N - 1 : 0; 2611 S2 x_t = b_t + y_t; 2612 S1' a_t = x_t >> log2 (N); 2613 2614 S4 is replaced if N is a power of two constant and 2615 type is signed by (where *_T temporaries have unsigned type): 2616 S9 y_T = b_t < 0 ? -1U : 0U; 2617 S8 z_T = y_T >> (sizeof (type_t) * CHAR_BIT - log2 (N)); 2618 S7 z_t = (type) z_T; 2619 S6 w_t = b_t + z_t; 2620 S5 x_t = w_t & (N - 1); 2621 S4' a_t = x_t - z_t; 2622 2623 Output: 2624 2625 * TYPE_IN: The type of the input arguments to the pattern. 2626 2627 * TYPE_OUT: The type of the output of this pattern. 2628 2629 * Return value: A new stmt that will be used to replace the division 2630 S1 or modulo S4 stmt. */ 2631 2632 static gimple * 2633 vect_recog_divmod_pattern (vec<gimple *> *stmts, 2634 tree *type_in, tree *type_out) 2635 { 2636 gimple *last_stmt = stmts->pop (); 2637 tree oprnd0, oprnd1, vectype, itype, cond; 2638 gimple *pattern_stmt, *def_stmt; 2639 enum tree_code rhs_code; 2640 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 2641 vec_info *vinfo = stmt_vinfo->vinfo; 2642 optab optab; 2643 tree q; 2644 int dummy_int, prec; 2645 stmt_vec_info def_stmt_vinfo; 2646 2647 if (!is_gimple_assign (last_stmt)) 2648 return NULL; 2649 2650 rhs_code = gimple_assign_rhs_code (last_stmt); 2651 switch (rhs_code) 2652 { 2653 case TRUNC_DIV_EXPR: 2654 case TRUNC_MOD_EXPR: 2655 break; 2656 default: 2657 return NULL; 2658 } 2659 2660 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 2661 return NULL; 2662 2663 oprnd0 = gimple_assign_rhs1 (last_stmt); 2664 oprnd1 = gimple_assign_rhs2 (last_stmt); 2665 itype = TREE_TYPE (oprnd0); 2666 if (TREE_CODE (oprnd0) != SSA_NAME 2667 || TREE_CODE (oprnd1) != INTEGER_CST 2668 || TREE_CODE (itype) != INTEGER_TYPE 2669 || !type_has_mode_precision_p (itype)) 2670 return NULL; 2671 2672 scalar_int_mode itype_mode = SCALAR_INT_TYPE_MODE (itype); 2673 vectype = get_vectype_for_scalar_type (itype); 2674 if (vectype == NULL_TREE) 2675 return NULL; 2676 2677 /* If the target can handle vectorized division or modulo natively, 2678 don't attempt to optimize this. */ 2679 optab = optab_for_tree_code (rhs_code, vectype, optab_default); 2680 if (optab != unknown_optab) 2681 { 2682 machine_mode vec_mode = TYPE_MODE (vectype); 2683 int icode = (int) optab_handler (optab, vec_mode); 2684 if (icode != CODE_FOR_nothing) 2685 return NULL; 2686 } 2687 2688 prec = TYPE_PRECISION (itype); 2689 if (integer_pow2p (oprnd1)) 2690 { 2691 if (TYPE_UNSIGNED (itype) || tree_int_cst_sgn (oprnd1) != 1) 2692 return NULL; 2693 2694 /* Pattern detected. */ 2695 if (dump_enabled_p ()) 2696 dump_printf_loc (MSG_NOTE, vect_location, 2697 "vect_recog_divmod_pattern: detected:\n"); 2698 2699 cond = build2 (LT_EXPR, boolean_type_node, oprnd0, 2700 build_int_cst (itype, 0)); 2701 if (rhs_code == TRUNC_DIV_EXPR) 2702 { 2703 tree var = vect_recog_temp_ssa_var (itype, NULL); 2704 tree shift; 2705 def_stmt 2706 = gimple_build_assign (var, COND_EXPR, cond, 2707 fold_build2 (MINUS_EXPR, itype, oprnd1, 2708 build_int_cst (itype, 1)), 2709 build_int_cst (itype, 0)); 2710 new_pattern_def_seq (stmt_vinfo, def_stmt); 2711 var = vect_recog_temp_ssa_var (itype, NULL); 2712 def_stmt 2713 = gimple_build_assign (var, PLUS_EXPR, oprnd0, 2714 gimple_assign_lhs (def_stmt)); 2715 append_pattern_def_seq (stmt_vinfo, def_stmt); 2716 2717 shift = build_int_cst (itype, tree_log2 (oprnd1)); 2718 pattern_stmt 2719 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 2720 RSHIFT_EXPR, var, shift); 2721 } 2722 else 2723 { 2724 tree signmask; 2725 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL; 2726 if (compare_tree_int (oprnd1, 2) == 0) 2727 { 2728 signmask = vect_recog_temp_ssa_var (itype, NULL); 2729 def_stmt = gimple_build_assign (signmask, COND_EXPR, cond, 2730 build_int_cst (itype, 1), 2731 build_int_cst (itype, 0)); 2732 append_pattern_def_seq (stmt_vinfo, def_stmt); 2733 } 2734 else 2735 { 2736 tree utype 2737 = build_nonstandard_integer_type (prec, 1); 2738 tree vecutype = get_vectype_for_scalar_type (utype); 2739 tree shift 2740 = build_int_cst (utype, GET_MODE_BITSIZE (itype_mode) 2741 - tree_log2 (oprnd1)); 2742 tree var = vect_recog_temp_ssa_var (utype, NULL); 2743 2744 def_stmt = gimple_build_assign (var, COND_EXPR, cond, 2745 build_int_cst (utype, -1), 2746 build_int_cst (utype, 0)); 2747 def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo); 2748 set_vinfo_for_stmt (def_stmt, def_stmt_vinfo); 2749 STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype; 2750 append_pattern_def_seq (stmt_vinfo, def_stmt); 2751 var = vect_recog_temp_ssa_var (utype, NULL); 2752 def_stmt = gimple_build_assign (var, RSHIFT_EXPR, 2753 gimple_assign_lhs (def_stmt), 2754 shift); 2755 def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo); 2756 set_vinfo_for_stmt (def_stmt, def_stmt_vinfo); 2757 STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype; 2758 append_pattern_def_seq (stmt_vinfo, def_stmt); 2759 signmask = vect_recog_temp_ssa_var (itype, NULL); 2760 def_stmt 2761 = gimple_build_assign (signmask, NOP_EXPR, var); 2762 append_pattern_def_seq (stmt_vinfo, def_stmt); 2763 } 2764 def_stmt 2765 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 2766 PLUS_EXPR, oprnd0, signmask); 2767 append_pattern_def_seq (stmt_vinfo, def_stmt); 2768 def_stmt 2769 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 2770 BIT_AND_EXPR, gimple_assign_lhs (def_stmt), 2771 fold_build2 (MINUS_EXPR, itype, oprnd1, 2772 build_int_cst (itype, 1))); 2773 append_pattern_def_seq (stmt_vinfo, def_stmt); 2774 2775 pattern_stmt 2776 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 2777 MINUS_EXPR, gimple_assign_lhs (def_stmt), 2778 signmask); 2779 } 2780 2781 if (dump_enabled_p ()) 2782 dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 2783 0); 2784 2785 stmts->safe_push (last_stmt); 2786 2787 *type_in = vectype; 2788 *type_out = vectype; 2789 return pattern_stmt; 2790 } 2791 2792 if (prec > HOST_BITS_PER_WIDE_INT 2793 || integer_zerop (oprnd1)) 2794 return NULL; 2795 2796 if (!can_mult_highpart_p (TYPE_MODE (vectype), TYPE_UNSIGNED (itype))) 2797 return NULL; 2798 2799 STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL; 2800 2801 if (TYPE_UNSIGNED (itype)) 2802 { 2803 unsigned HOST_WIDE_INT mh, ml; 2804 int pre_shift, post_shift; 2805 unsigned HOST_WIDE_INT d = (TREE_INT_CST_LOW (oprnd1) 2806 & GET_MODE_MASK (itype_mode)); 2807 tree t1, t2, t3, t4; 2808 2809 if (d >= (HOST_WIDE_INT_1U << (prec - 1))) 2810 /* FIXME: Can transform this into oprnd0 >= oprnd1 ? 1 : 0. */ 2811 return NULL; 2812 2813 /* Find a suitable multiplier and right shift count 2814 instead of multiplying with D. */ 2815 mh = choose_multiplier (d, prec, prec, &ml, &post_shift, &dummy_int); 2816 2817 /* If the suggested multiplier is more than SIZE bits, we can do better 2818 for even divisors, using an initial right shift. */ 2819 if (mh != 0 && (d & 1) == 0) 2820 { 2821 pre_shift = ctz_or_zero (d); 2822 mh = choose_multiplier (d >> pre_shift, prec, prec - pre_shift, 2823 &ml, &post_shift, &dummy_int); 2824 gcc_assert (!mh); 2825 } 2826 else 2827 pre_shift = 0; 2828 2829 if (mh != 0) 2830 { 2831 if (post_shift - 1 >= prec) 2832 return NULL; 2833 2834 /* t1 = oprnd0 h* ml; 2835 t2 = oprnd0 - t1; 2836 t3 = t2 >> 1; 2837 t4 = t1 + t3; 2838 q = t4 >> (post_shift - 1); */ 2839 t1 = vect_recog_temp_ssa_var (itype, NULL); 2840 def_stmt = gimple_build_assign (t1, MULT_HIGHPART_EXPR, oprnd0, 2841 build_int_cst (itype, ml)); 2842 append_pattern_def_seq (stmt_vinfo, def_stmt); 2843 2844 t2 = vect_recog_temp_ssa_var (itype, NULL); 2845 def_stmt 2846 = gimple_build_assign (t2, MINUS_EXPR, oprnd0, t1); 2847 append_pattern_def_seq (stmt_vinfo, def_stmt); 2848 2849 t3 = vect_recog_temp_ssa_var (itype, NULL); 2850 def_stmt 2851 = gimple_build_assign (t3, RSHIFT_EXPR, t2, integer_one_node); 2852 append_pattern_def_seq (stmt_vinfo, def_stmt); 2853 2854 t4 = vect_recog_temp_ssa_var (itype, NULL); 2855 def_stmt 2856 = gimple_build_assign (t4, PLUS_EXPR, t1, t3); 2857 2858 if (post_shift != 1) 2859 { 2860 append_pattern_def_seq (stmt_vinfo, def_stmt); 2861 2862 q = vect_recog_temp_ssa_var (itype, NULL); 2863 pattern_stmt 2864 = gimple_build_assign (q, RSHIFT_EXPR, t4, 2865 build_int_cst (itype, post_shift - 1)); 2866 } 2867 else 2868 { 2869 q = t4; 2870 pattern_stmt = def_stmt; 2871 } 2872 } 2873 else 2874 { 2875 if (pre_shift >= prec || post_shift >= prec) 2876 return NULL; 2877 2878 /* t1 = oprnd0 >> pre_shift; 2879 t2 = t1 h* ml; 2880 q = t2 >> post_shift; */ 2881 if (pre_shift) 2882 { 2883 t1 = vect_recog_temp_ssa_var (itype, NULL); 2884 def_stmt 2885 = gimple_build_assign (t1, RSHIFT_EXPR, oprnd0, 2886 build_int_cst (NULL, pre_shift)); 2887 append_pattern_def_seq (stmt_vinfo, def_stmt); 2888 } 2889 else 2890 t1 = oprnd0; 2891 2892 t2 = vect_recog_temp_ssa_var (itype, NULL); 2893 def_stmt = gimple_build_assign (t2, MULT_HIGHPART_EXPR, t1, 2894 build_int_cst (itype, ml)); 2895 2896 if (post_shift) 2897 { 2898 append_pattern_def_seq (stmt_vinfo, def_stmt); 2899 2900 q = vect_recog_temp_ssa_var (itype, NULL); 2901 def_stmt 2902 = gimple_build_assign (q, RSHIFT_EXPR, t2, 2903 build_int_cst (itype, post_shift)); 2904 } 2905 else 2906 q = t2; 2907 2908 pattern_stmt = def_stmt; 2909 } 2910 } 2911 else 2912 { 2913 unsigned HOST_WIDE_INT ml; 2914 int post_shift; 2915 HOST_WIDE_INT d = TREE_INT_CST_LOW (oprnd1); 2916 unsigned HOST_WIDE_INT abs_d; 2917 bool add = false; 2918 tree t1, t2, t3, t4; 2919 2920 /* Give up for -1. */ 2921 if (d == -1) 2922 return NULL; 2923 2924 /* Since d might be INT_MIN, we have to cast to 2925 unsigned HOST_WIDE_INT before negating to avoid 2926 undefined signed overflow. */ 2927 abs_d = (d >= 0 2928 ? (unsigned HOST_WIDE_INT) d 2929 : - (unsigned HOST_WIDE_INT) d); 2930 2931 /* n rem d = n rem -d */ 2932 if (rhs_code == TRUNC_MOD_EXPR && d < 0) 2933 { 2934 d = abs_d; 2935 oprnd1 = build_int_cst (itype, abs_d); 2936 } 2937 else if (HOST_BITS_PER_WIDE_INT >= prec 2938 && abs_d == HOST_WIDE_INT_1U << (prec - 1)) 2939 /* This case is not handled correctly below. */ 2940 return NULL; 2941 2942 choose_multiplier (abs_d, prec, prec - 1, &ml, &post_shift, &dummy_int); 2943 if (ml >= HOST_WIDE_INT_1U << (prec - 1)) 2944 { 2945 add = true; 2946 ml |= HOST_WIDE_INT_M1U << (prec - 1); 2947 } 2948 if (post_shift >= prec) 2949 return NULL; 2950 2951 /* t1 = oprnd0 h* ml; */ 2952 t1 = vect_recog_temp_ssa_var (itype, NULL); 2953 def_stmt = gimple_build_assign (t1, MULT_HIGHPART_EXPR, oprnd0, 2954 build_int_cst (itype, ml)); 2955 2956 if (add) 2957 { 2958 /* t2 = t1 + oprnd0; */ 2959 append_pattern_def_seq (stmt_vinfo, def_stmt); 2960 t2 = vect_recog_temp_ssa_var (itype, NULL); 2961 def_stmt = gimple_build_assign (t2, PLUS_EXPR, t1, oprnd0); 2962 } 2963 else 2964 t2 = t1; 2965 2966 if (post_shift) 2967 { 2968 /* t3 = t2 >> post_shift; */ 2969 append_pattern_def_seq (stmt_vinfo, def_stmt); 2970 t3 = vect_recog_temp_ssa_var (itype, NULL); 2971 def_stmt = gimple_build_assign (t3, RSHIFT_EXPR, t2, 2972 build_int_cst (itype, post_shift)); 2973 } 2974 else 2975 t3 = t2; 2976 2977 wide_int oprnd0_min, oprnd0_max; 2978 int msb = 1; 2979 if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE) 2980 { 2981 if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype))) 2982 msb = 0; 2983 else if (wi::neg_p (oprnd0_max, TYPE_SIGN (itype))) 2984 msb = -1; 2985 } 2986 2987 if (msb == 0 && d >= 0) 2988 { 2989 /* q = t3; */ 2990 q = t3; 2991 pattern_stmt = def_stmt; 2992 } 2993 else 2994 { 2995 /* t4 = oprnd0 >> (prec - 1); 2996 or if we know from VRP that oprnd0 >= 0 2997 t4 = 0; 2998 or if we know from VRP that oprnd0 < 0 2999 t4 = -1; */ 3000 append_pattern_def_seq (stmt_vinfo, def_stmt); 3001 t4 = vect_recog_temp_ssa_var (itype, NULL); 3002 if (msb != 1) 3003 def_stmt = gimple_build_assign (t4, INTEGER_CST, 3004 build_int_cst (itype, msb)); 3005 else 3006 def_stmt = gimple_build_assign (t4, RSHIFT_EXPR, oprnd0, 3007 build_int_cst (itype, prec - 1)); 3008 append_pattern_def_seq (stmt_vinfo, def_stmt); 3009 3010 /* q = t3 - t4; or q = t4 - t3; */ 3011 q = vect_recog_temp_ssa_var (itype, NULL); 3012 pattern_stmt = gimple_build_assign (q, MINUS_EXPR, d < 0 ? t4 : t3, 3013 d < 0 ? t3 : t4); 3014 } 3015 } 3016 3017 if (rhs_code == TRUNC_MOD_EXPR) 3018 { 3019 tree r, t1; 3020 3021 /* We divided. Now finish by: 3022 t1 = q * oprnd1; 3023 r = oprnd0 - t1; */ 3024 append_pattern_def_seq (stmt_vinfo, pattern_stmt); 3025 3026 t1 = vect_recog_temp_ssa_var (itype, NULL); 3027 def_stmt = gimple_build_assign (t1, MULT_EXPR, q, oprnd1); 3028 append_pattern_def_seq (stmt_vinfo, def_stmt); 3029 3030 r = vect_recog_temp_ssa_var (itype, NULL); 3031 pattern_stmt = gimple_build_assign (r, MINUS_EXPR, oprnd0, t1); 3032 } 3033 3034 /* Pattern detected. */ 3035 if (dump_enabled_p ()) 3036 { 3037 dump_printf_loc (MSG_NOTE, vect_location, 3038 "vect_recog_divmod_pattern: detected: "); 3039 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 3040 } 3041 3042 stmts->safe_push (last_stmt); 3043 3044 *type_in = vectype; 3045 *type_out = vectype; 3046 return pattern_stmt; 3047 } 3048 3049 /* Function vect_recog_mixed_size_cond_pattern 3050 3051 Try to find the following pattern: 3052 3053 type x_t, y_t; 3054 TYPE a_T, b_T, c_T; 3055 loop: 3056 S1 a_T = x_t CMP y_t ? b_T : c_T; 3057 3058 where type 'TYPE' is an integral type which has different size 3059 from 'type'. b_T and c_T are either constants (and if 'TYPE' is wider 3060 than 'type', the constants need to fit into an integer type 3061 with the same width as 'type') or results of conversion from 'type'. 3062 3063 Input: 3064 3065 * LAST_STMT: A stmt from which the pattern search begins. 3066 3067 Output: 3068 3069 * TYPE_IN: The type of the input arguments to the pattern. 3070 3071 * TYPE_OUT: The type of the output of this pattern. 3072 3073 * Return value: A new stmt that will be used to replace the pattern. 3074 Additionally a def_stmt is added. 3075 3076 a_it = x_t CMP y_t ? b_it : c_it; 3077 a_T = (TYPE) a_it; */ 3078 3079 static gimple * 3080 vect_recog_mixed_size_cond_pattern (vec<gimple *> *stmts, tree *type_in, 3081 tree *type_out) 3082 { 3083 gimple *last_stmt = (*stmts)[0]; 3084 tree cond_expr, then_clause, else_clause; 3085 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt), def_stmt_info; 3086 tree type, vectype, comp_vectype, itype = NULL_TREE, vecitype; 3087 gimple *pattern_stmt, *def_stmt; 3088 vec_info *vinfo = stmt_vinfo->vinfo; 3089 tree orig_type0 = NULL_TREE, orig_type1 = NULL_TREE; 3090 gimple *def_stmt0 = NULL, *def_stmt1 = NULL; 3091 bool promotion; 3092 tree comp_scalar_type; 3093 3094 if (!is_gimple_assign (last_stmt) 3095 || gimple_assign_rhs_code (last_stmt) != COND_EXPR 3096 || STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def) 3097 return NULL; 3098 3099 cond_expr = gimple_assign_rhs1 (last_stmt); 3100 then_clause = gimple_assign_rhs2 (last_stmt); 3101 else_clause = gimple_assign_rhs3 (last_stmt); 3102 3103 if (!COMPARISON_CLASS_P (cond_expr)) 3104 return NULL; 3105 3106 comp_scalar_type = TREE_TYPE (TREE_OPERAND (cond_expr, 0)); 3107 comp_vectype = get_vectype_for_scalar_type (comp_scalar_type); 3108 if (comp_vectype == NULL_TREE) 3109 return NULL; 3110 3111 type = gimple_expr_type (last_stmt); 3112 if (types_compatible_p (type, comp_scalar_type) 3113 || ((TREE_CODE (then_clause) != INTEGER_CST 3114 || TREE_CODE (else_clause) != INTEGER_CST) 3115 && !INTEGRAL_TYPE_P (comp_scalar_type)) 3116 || !INTEGRAL_TYPE_P (type)) 3117 return NULL; 3118 3119 if ((TREE_CODE (then_clause) != INTEGER_CST 3120 && !type_conversion_p (then_clause, last_stmt, false, &orig_type0, 3121 &def_stmt0, &promotion)) 3122 || (TREE_CODE (else_clause) != INTEGER_CST 3123 && !type_conversion_p (else_clause, last_stmt, false, &orig_type1, 3124 &def_stmt1, &promotion))) 3125 return NULL; 3126 3127 if (orig_type0 && orig_type1 3128 && !types_compatible_p (orig_type0, orig_type1)) 3129 return NULL; 3130 3131 if (orig_type0) 3132 { 3133 if (!types_compatible_p (orig_type0, comp_scalar_type)) 3134 return NULL; 3135 then_clause = gimple_assign_rhs1 (def_stmt0); 3136 itype = orig_type0; 3137 } 3138 3139 if (orig_type1) 3140 { 3141 if (!types_compatible_p (orig_type1, comp_scalar_type)) 3142 return NULL; 3143 else_clause = gimple_assign_rhs1 (def_stmt1); 3144 itype = orig_type1; 3145 } 3146 3147 3148 HOST_WIDE_INT cmp_mode_size 3149 = GET_MODE_UNIT_BITSIZE (TYPE_MODE (comp_vectype)); 3150 3151 scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type); 3152 if (GET_MODE_BITSIZE (type_mode) == cmp_mode_size) 3153 return NULL; 3154 3155 vectype = get_vectype_for_scalar_type (type); 3156 if (vectype == NULL_TREE) 3157 return NULL; 3158 3159 if (expand_vec_cond_expr_p (vectype, comp_vectype, TREE_CODE (cond_expr))) 3160 return NULL; 3161 3162 if (itype == NULL_TREE) 3163 itype = build_nonstandard_integer_type (cmp_mode_size, 3164 TYPE_UNSIGNED (type)); 3165 3166 if (itype == NULL_TREE 3167 || GET_MODE_BITSIZE (SCALAR_TYPE_MODE (itype)) != cmp_mode_size) 3168 return NULL; 3169 3170 vecitype = get_vectype_for_scalar_type (itype); 3171 if (vecitype == NULL_TREE) 3172 return NULL; 3173 3174 if (!expand_vec_cond_expr_p (vecitype, comp_vectype, TREE_CODE (cond_expr))) 3175 return NULL; 3176 3177 if (GET_MODE_BITSIZE (type_mode) > cmp_mode_size) 3178 { 3179 if ((TREE_CODE (then_clause) == INTEGER_CST 3180 && !int_fits_type_p (then_clause, itype)) 3181 || (TREE_CODE (else_clause) == INTEGER_CST 3182 && !int_fits_type_p (else_clause, itype))) 3183 return NULL; 3184 } 3185 3186 def_stmt = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 3187 COND_EXPR, unshare_expr (cond_expr), 3188 fold_convert (itype, then_clause), 3189 fold_convert (itype, else_clause)); 3190 pattern_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL), 3191 NOP_EXPR, gimple_assign_lhs (def_stmt)); 3192 3193 new_pattern_def_seq (stmt_vinfo, def_stmt); 3194 def_stmt_info = new_stmt_vec_info (def_stmt, vinfo); 3195 set_vinfo_for_stmt (def_stmt, def_stmt_info); 3196 STMT_VINFO_VECTYPE (def_stmt_info) = vecitype; 3197 *type_in = vecitype; 3198 *type_out = vectype; 3199 3200 if (dump_enabled_p ()) 3201 dump_printf_loc (MSG_NOTE, vect_location, 3202 "vect_recog_mixed_size_cond_pattern: detected:\n"); 3203 3204 return pattern_stmt; 3205 } 3206 3207 3208 /* Helper function of vect_recog_bool_pattern. Called recursively, return 3209 true if bool VAR can and should be optimized that way. Assume it shouldn't 3210 in case it's a result of a comparison which can be directly vectorized into 3211 a vector comparison. Fills in STMTS with all stmts visited during the 3212 walk. */ 3213 3214 static bool 3215 check_bool_pattern (tree var, vec_info *vinfo, hash_set<gimple *> &stmts) 3216 { 3217 gimple *def_stmt; 3218 enum vect_def_type dt; 3219 tree rhs1; 3220 enum tree_code rhs_code; 3221 3222 if (!vect_is_simple_use (var, vinfo, &def_stmt, &dt)) 3223 return false; 3224 3225 if (dt != vect_internal_def) 3226 return false; 3227 3228 if (!is_gimple_assign (def_stmt)) 3229 return false; 3230 3231 if (stmts.contains (def_stmt)) 3232 return true; 3233 3234 rhs1 = gimple_assign_rhs1 (def_stmt); 3235 rhs_code = gimple_assign_rhs_code (def_stmt); 3236 switch (rhs_code) 3237 { 3238 case SSA_NAME: 3239 if (! check_bool_pattern (rhs1, vinfo, stmts)) 3240 return false; 3241 break; 3242 3243 CASE_CONVERT: 3244 if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (rhs1))) 3245 return false; 3246 if (! check_bool_pattern (rhs1, vinfo, stmts)) 3247 return false; 3248 break; 3249 3250 case BIT_NOT_EXPR: 3251 if (! check_bool_pattern (rhs1, vinfo, stmts)) 3252 return false; 3253 break; 3254 3255 case BIT_AND_EXPR: 3256 case BIT_IOR_EXPR: 3257 case BIT_XOR_EXPR: 3258 if (! check_bool_pattern (rhs1, vinfo, stmts) 3259 || ! check_bool_pattern (gimple_assign_rhs2 (def_stmt), vinfo, stmts)) 3260 return false; 3261 break; 3262 3263 default: 3264 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison) 3265 { 3266 tree vecitype, comp_vectype; 3267 3268 /* If the comparison can throw, then is_gimple_condexpr will be 3269 false and we can't make a COND_EXPR/VEC_COND_EXPR out of it. */ 3270 if (stmt_could_throw_p (def_stmt)) 3271 return false; 3272 3273 comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1)); 3274 if (comp_vectype == NULL_TREE) 3275 return false; 3276 3277 tree mask_type = get_mask_type_for_scalar_type (TREE_TYPE (rhs1)); 3278 if (mask_type 3279 && expand_vec_cmp_expr_p (comp_vectype, mask_type, rhs_code)) 3280 return false; 3281 3282 if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE) 3283 { 3284 scalar_mode mode = SCALAR_TYPE_MODE (TREE_TYPE (rhs1)); 3285 tree itype 3286 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1); 3287 vecitype = get_vectype_for_scalar_type (itype); 3288 if (vecitype == NULL_TREE) 3289 return false; 3290 } 3291 else 3292 vecitype = comp_vectype; 3293 if (! expand_vec_cond_expr_p (vecitype, comp_vectype, rhs_code)) 3294 return false; 3295 } 3296 else 3297 return false; 3298 break; 3299 } 3300 3301 bool res = stmts.add (def_stmt); 3302 /* We can't end up recursing when just visiting SSA defs but not PHIs. */ 3303 gcc_assert (!res); 3304 3305 return true; 3306 } 3307 3308 3309 /* Helper function of adjust_bool_pattern. Add a cast to TYPE to a previous 3310 stmt (SSA_NAME_DEF_STMT of VAR) adding a cast to STMT_INFOs 3311 pattern sequence. */ 3312 3313 static tree 3314 adjust_bool_pattern_cast (tree type, tree var, stmt_vec_info stmt_info) 3315 { 3316 gimple *cast_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL), 3317 NOP_EXPR, var); 3318 stmt_vec_info patt_vinfo = new_stmt_vec_info (cast_stmt, stmt_info->vinfo); 3319 set_vinfo_for_stmt (cast_stmt, patt_vinfo); 3320 STMT_VINFO_VECTYPE (patt_vinfo) = get_vectype_for_scalar_type (type); 3321 append_pattern_def_seq (stmt_info, cast_stmt); 3322 return gimple_assign_lhs (cast_stmt); 3323 } 3324 3325 /* Helper function of vect_recog_bool_pattern. Do the actual transformations. 3326 VAR is an SSA_NAME that should be transformed from bool to a wider integer 3327 type, OUT_TYPE is the desired final integer type of the whole pattern. 3328 STMT_INFO is the info of the pattern root and is where pattern stmts should 3329 be associated with. DEFS is a map of pattern defs. */ 3330 3331 static void 3332 adjust_bool_pattern (tree var, tree out_type, 3333 stmt_vec_info stmt_info, hash_map <tree, tree> &defs) 3334 { 3335 gimple *stmt = SSA_NAME_DEF_STMT (var); 3336 enum tree_code rhs_code, def_rhs_code; 3337 tree itype, cond_expr, rhs1, rhs2, irhs1, irhs2; 3338 location_t loc; 3339 gimple *pattern_stmt, *def_stmt; 3340 tree trueval = NULL_TREE; 3341 3342 rhs1 = gimple_assign_rhs1 (stmt); 3343 rhs2 = gimple_assign_rhs2 (stmt); 3344 rhs_code = gimple_assign_rhs_code (stmt); 3345 loc = gimple_location (stmt); 3346 switch (rhs_code) 3347 { 3348 case SSA_NAME: 3349 CASE_CONVERT: 3350 irhs1 = *defs.get (rhs1); 3351 itype = TREE_TYPE (irhs1); 3352 pattern_stmt 3353 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 3354 SSA_NAME, irhs1); 3355 break; 3356 3357 case BIT_NOT_EXPR: 3358 irhs1 = *defs.get (rhs1); 3359 itype = TREE_TYPE (irhs1); 3360 pattern_stmt 3361 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 3362 BIT_XOR_EXPR, irhs1, build_int_cst (itype, 1)); 3363 break; 3364 3365 case BIT_AND_EXPR: 3366 /* Try to optimize x = y & (a < b ? 1 : 0); into 3367 x = (a < b ? y : 0); 3368 3369 E.g. for: 3370 bool a_b, b_b, c_b; 3371 TYPE d_T; 3372 3373 S1 a_b = x1 CMP1 y1; 3374 S2 b_b = x2 CMP2 y2; 3375 S3 c_b = a_b & b_b; 3376 S4 d_T = (TYPE) c_b; 3377 3378 we would normally emit: 3379 3380 S1' a_T = x1 CMP1 y1 ? 1 : 0; 3381 S2' b_T = x2 CMP2 y2 ? 1 : 0; 3382 S3' c_T = a_T & b_T; 3383 S4' d_T = c_T; 3384 3385 but we can save one stmt by using the 3386 result of one of the COND_EXPRs in the other COND_EXPR and leave 3387 BIT_AND_EXPR stmt out: 3388 3389 S1' a_T = x1 CMP1 y1 ? 1 : 0; 3390 S3' c_T = x2 CMP2 y2 ? a_T : 0; 3391 S4' f_T = c_T; 3392 3393 At least when VEC_COND_EXPR is implemented using masks 3394 cond ? 1 : 0 is as expensive as cond ? var : 0, in both cases it 3395 computes the comparison masks and ands it, in one case with 3396 all ones vector, in the other case with a vector register. 3397 Don't do this for BIT_IOR_EXPR, because cond ? 1 : var; is 3398 often more expensive. */ 3399 def_stmt = SSA_NAME_DEF_STMT (rhs2); 3400 def_rhs_code = gimple_assign_rhs_code (def_stmt); 3401 if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison) 3402 { 3403 irhs1 = *defs.get (rhs1); 3404 tree def_rhs1 = gimple_assign_rhs1 (def_stmt); 3405 if (TYPE_PRECISION (TREE_TYPE (irhs1)) 3406 == GET_MODE_BITSIZE (SCALAR_TYPE_MODE (TREE_TYPE (def_rhs1)))) 3407 { 3408 rhs_code = def_rhs_code; 3409 rhs1 = def_rhs1; 3410 rhs2 = gimple_assign_rhs2 (def_stmt); 3411 trueval = irhs1; 3412 goto do_compare; 3413 } 3414 else 3415 irhs2 = *defs.get (rhs2); 3416 goto and_ior_xor; 3417 } 3418 def_stmt = SSA_NAME_DEF_STMT (rhs1); 3419 def_rhs_code = gimple_assign_rhs_code (def_stmt); 3420 if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison) 3421 { 3422 irhs2 = *defs.get (rhs2); 3423 tree def_rhs1 = gimple_assign_rhs1 (def_stmt); 3424 if (TYPE_PRECISION (TREE_TYPE (irhs2)) 3425 == GET_MODE_BITSIZE (SCALAR_TYPE_MODE (TREE_TYPE (def_rhs1)))) 3426 { 3427 rhs_code = def_rhs_code; 3428 rhs1 = def_rhs1; 3429 rhs2 = gimple_assign_rhs2 (def_stmt); 3430 trueval = irhs2; 3431 goto do_compare; 3432 } 3433 else 3434 irhs1 = *defs.get (rhs1); 3435 goto and_ior_xor; 3436 } 3437 /* FALLTHRU */ 3438 case BIT_IOR_EXPR: 3439 case BIT_XOR_EXPR: 3440 irhs1 = *defs.get (rhs1); 3441 irhs2 = *defs.get (rhs2); 3442 and_ior_xor: 3443 if (TYPE_PRECISION (TREE_TYPE (irhs1)) 3444 != TYPE_PRECISION (TREE_TYPE (irhs2))) 3445 { 3446 int prec1 = TYPE_PRECISION (TREE_TYPE (irhs1)); 3447 int prec2 = TYPE_PRECISION (TREE_TYPE (irhs2)); 3448 int out_prec = TYPE_PRECISION (out_type); 3449 if (absu_hwi (out_prec - prec1) < absu_hwi (out_prec - prec2)) 3450 irhs2 = adjust_bool_pattern_cast (TREE_TYPE (irhs1), irhs2, 3451 stmt_info); 3452 else if (absu_hwi (out_prec - prec1) > absu_hwi (out_prec - prec2)) 3453 irhs1 = adjust_bool_pattern_cast (TREE_TYPE (irhs2), irhs1, 3454 stmt_info); 3455 else 3456 { 3457 irhs1 = adjust_bool_pattern_cast (out_type, irhs1, stmt_info); 3458 irhs2 = adjust_bool_pattern_cast (out_type, irhs2, stmt_info); 3459 } 3460 } 3461 itype = TREE_TYPE (irhs1); 3462 pattern_stmt 3463 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 3464 rhs_code, irhs1, irhs2); 3465 break; 3466 3467 default: 3468 do_compare: 3469 gcc_assert (TREE_CODE_CLASS (rhs_code) == tcc_comparison); 3470 if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE 3471 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)) 3472 || maybe_ne (TYPE_PRECISION (TREE_TYPE (rhs1)), 3473 GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1))))) 3474 { 3475 scalar_mode mode = SCALAR_TYPE_MODE (TREE_TYPE (rhs1)); 3476 itype 3477 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1); 3478 } 3479 else 3480 itype = TREE_TYPE (rhs1); 3481 cond_expr = build2_loc (loc, rhs_code, itype, rhs1, rhs2); 3482 if (trueval == NULL_TREE) 3483 trueval = build_int_cst (itype, 1); 3484 else 3485 gcc_checking_assert (useless_type_conversion_p (itype, 3486 TREE_TYPE (trueval))); 3487 pattern_stmt 3488 = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL), 3489 COND_EXPR, cond_expr, trueval, 3490 build_int_cst (itype, 0)); 3491 break; 3492 } 3493 3494 gimple_set_location (pattern_stmt, loc); 3495 /* ??? Why does vect_mark_pattern_stmts set the vector type on all 3496 pattern def seq stmts instead of just letting auto-detection do 3497 its work? */ 3498 stmt_vec_info patt_vinfo = new_stmt_vec_info (pattern_stmt, stmt_info->vinfo); 3499 set_vinfo_for_stmt (pattern_stmt, patt_vinfo); 3500 STMT_VINFO_VECTYPE (patt_vinfo) = get_vectype_for_scalar_type (itype); 3501 append_pattern_def_seq (stmt_info, pattern_stmt); 3502 defs.put (var, gimple_assign_lhs (pattern_stmt)); 3503 } 3504 3505 /* Comparison function to qsort a vector of gimple stmts after UID. */ 3506 3507 static int 3508 sort_after_uid (const void *p1, const void *p2) 3509 { 3510 const gimple *stmt1 = *(const gimple * const *)p1; 3511 const gimple *stmt2 = *(const gimple * const *)p2; 3512 return gimple_uid (stmt1) - gimple_uid (stmt2); 3513 } 3514 3515 /* Create pattern stmts for all stmts participating in the bool pattern 3516 specified by BOOL_STMT_SET and its root STMT with the desired type 3517 OUT_TYPE. Return the def of the pattern root. */ 3518 3519 static tree 3520 adjust_bool_stmts (hash_set <gimple *> &bool_stmt_set, 3521 tree out_type, gimple *stmt) 3522 { 3523 /* Gather original stmts in the bool pattern in their order of appearance 3524 in the IL. */ 3525 auto_vec<gimple *> bool_stmts (bool_stmt_set.elements ()); 3526 for (hash_set <gimple *>::iterator i = bool_stmt_set.begin (); 3527 i != bool_stmt_set.end (); ++i) 3528 bool_stmts.quick_push (*i); 3529 bool_stmts.qsort (sort_after_uid); 3530 3531 /* Now process them in that order, producing pattern stmts. */ 3532 hash_map <tree, tree> defs; 3533 for (unsigned i = 0; i < bool_stmts.length (); ++i) 3534 adjust_bool_pattern (gimple_assign_lhs (bool_stmts[i]), 3535 out_type, vinfo_for_stmt (stmt), defs); 3536 3537 /* Pop the last pattern seq stmt and install it as pattern root for STMT. */ 3538 gimple *pattern_stmt 3539 = gimple_seq_last_stmt (STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (stmt))); 3540 return gimple_assign_lhs (pattern_stmt); 3541 } 3542 3543 /* Helper for search_type_for_mask. */ 3544 3545 static tree 3546 search_type_for_mask_1 (tree var, vec_info *vinfo, 3547 hash_map<gimple *, tree> &cache) 3548 { 3549 gimple *def_stmt; 3550 enum vect_def_type dt; 3551 tree rhs1; 3552 enum tree_code rhs_code; 3553 tree res = NULL_TREE, res2; 3554 3555 if (TREE_CODE (var) != SSA_NAME) 3556 return NULL_TREE; 3557 3558 if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (var))) 3559 return NULL_TREE; 3560 3561 if (!vect_is_simple_use (var, vinfo, &def_stmt, &dt)) 3562 return NULL_TREE; 3563 3564 if (dt != vect_internal_def) 3565 return NULL_TREE; 3566 3567 if (!is_gimple_assign (def_stmt)) 3568 return NULL_TREE; 3569 3570 tree *c = cache.get (def_stmt); 3571 if (c) 3572 return *c; 3573 3574 rhs_code = gimple_assign_rhs_code (def_stmt); 3575 rhs1 = gimple_assign_rhs1 (def_stmt); 3576 3577 switch (rhs_code) 3578 { 3579 case SSA_NAME: 3580 case BIT_NOT_EXPR: 3581 CASE_CONVERT: 3582 res = search_type_for_mask_1 (rhs1, vinfo, cache); 3583 break; 3584 3585 case BIT_AND_EXPR: 3586 case BIT_IOR_EXPR: 3587 case BIT_XOR_EXPR: 3588 res = search_type_for_mask_1 (rhs1, vinfo, cache); 3589 res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt), vinfo, 3590 cache); 3591 if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2))) 3592 res = res2; 3593 break; 3594 3595 default: 3596 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison) 3597 { 3598 tree comp_vectype, mask_type; 3599 3600 if (VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (rhs1))) 3601 { 3602 res = search_type_for_mask_1 (rhs1, vinfo, cache); 3603 res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt), 3604 vinfo, cache); 3605 if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2))) 3606 res = res2; 3607 break; 3608 } 3609 3610 comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1)); 3611 if (comp_vectype == NULL_TREE) 3612 { 3613 res = NULL_TREE; 3614 break; 3615 } 3616 3617 mask_type = get_mask_type_for_scalar_type (TREE_TYPE (rhs1)); 3618 if (!mask_type 3619 || !expand_vec_cmp_expr_p (comp_vectype, mask_type, rhs_code)) 3620 { 3621 res = NULL_TREE; 3622 break; 3623 } 3624 3625 if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE 3626 || !TYPE_UNSIGNED (TREE_TYPE (rhs1))) 3627 { 3628 scalar_mode mode = SCALAR_TYPE_MODE (TREE_TYPE (rhs1)); 3629 res = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1); 3630 } 3631 else 3632 res = TREE_TYPE (rhs1); 3633 } 3634 } 3635 3636 cache.put (def_stmt, res); 3637 return res; 3638 } 3639 3640 /* Return the proper type for converting bool VAR into 3641 an integer value or NULL_TREE if no such type exists. 3642 The type is chosen so that converted value has the 3643 same number of elements as VAR's vector type. */ 3644 3645 static tree 3646 search_type_for_mask (tree var, vec_info *vinfo) 3647 { 3648 hash_map<gimple *, tree> cache; 3649 return search_type_for_mask_1 (var, vinfo, cache); 3650 } 3651 3652 /* Function vect_recog_bool_pattern 3653 3654 Try to find pattern like following: 3655 3656 bool a_b, b_b, c_b, d_b, e_b; 3657 TYPE f_T; 3658 loop: 3659 S1 a_b = x1 CMP1 y1; 3660 S2 b_b = x2 CMP2 y2; 3661 S3 c_b = a_b & b_b; 3662 S4 d_b = x3 CMP3 y3; 3663 S5 e_b = c_b | d_b; 3664 S6 f_T = (TYPE) e_b; 3665 3666 where type 'TYPE' is an integral type. Or a similar pattern 3667 ending in 3668 3669 S6 f_Y = e_b ? r_Y : s_Y; 3670 3671 as results from if-conversion of a complex condition. 3672 3673 Input: 3674 3675 * LAST_STMT: A stmt at the end from which the pattern 3676 search begins, i.e. cast of a bool to 3677 an integer type. 3678 3679 Output: 3680 3681 * TYPE_IN: The type of the input arguments to the pattern. 3682 3683 * TYPE_OUT: The type of the output of this pattern. 3684 3685 * Return value: A new stmt that will be used to replace the pattern. 3686 3687 Assuming size of TYPE is the same as size of all comparisons 3688 (otherwise some casts would be added where needed), the above 3689 sequence we create related pattern stmts: 3690 S1' a_T = x1 CMP1 y1 ? 1 : 0; 3691 S3' c_T = x2 CMP2 y2 ? a_T : 0; 3692 S4' d_T = x3 CMP3 y3 ? 1 : 0; 3693 S5' e_T = c_T | d_T; 3694 S6' f_T = e_T; 3695 3696 Instead of the above S3' we could emit: 3697 S2' b_T = x2 CMP2 y2 ? 1 : 0; 3698 S3' c_T = a_T | b_T; 3699 but the above is more efficient. */ 3700 3701 static gimple * 3702 vect_recog_bool_pattern (vec<gimple *> *stmts, tree *type_in, 3703 tree *type_out) 3704 { 3705 gimple *last_stmt = stmts->pop (); 3706 enum tree_code rhs_code; 3707 tree var, lhs, rhs, vectype; 3708 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 3709 stmt_vec_info new_stmt_info; 3710 vec_info *vinfo = stmt_vinfo->vinfo; 3711 gimple *pattern_stmt; 3712 3713 if (!is_gimple_assign (last_stmt)) 3714 return NULL; 3715 3716 var = gimple_assign_rhs1 (last_stmt); 3717 lhs = gimple_assign_lhs (last_stmt); 3718 3719 if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (var))) 3720 return NULL; 3721 3722 hash_set<gimple *> bool_stmts; 3723 3724 rhs_code = gimple_assign_rhs_code (last_stmt); 3725 if (CONVERT_EXPR_CODE_P (rhs_code)) 3726 { 3727 if (! INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 3728 || TYPE_PRECISION (TREE_TYPE (lhs)) == 1) 3729 return NULL; 3730 vectype = get_vectype_for_scalar_type (TREE_TYPE (lhs)); 3731 if (vectype == NULL_TREE) 3732 return NULL; 3733 3734 if (check_bool_pattern (var, vinfo, bool_stmts)) 3735 { 3736 rhs = adjust_bool_stmts (bool_stmts, TREE_TYPE (lhs), last_stmt); 3737 lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL); 3738 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 3739 pattern_stmt = gimple_build_assign (lhs, SSA_NAME, rhs); 3740 else 3741 pattern_stmt 3742 = gimple_build_assign (lhs, NOP_EXPR, rhs); 3743 } 3744 else 3745 { 3746 tree type = search_type_for_mask (var, vinfo); 3747 tree cst0, cst1, tmp; 3748 3749 if (!type) 3750 return NULL; 3751 3752 /* We may directly use cond with narrowed type to avoid 3753 multiple cond exprs with following result packing and 3754 perform single cond with packed mask instead. In case 3755 of widening we better make cond first and then extract 3756 results. */ 3757 if (TYPE_MODE (type) == TYPE_MODE (TREE_TYPE (lhs))) 3758 type = TREE_TYPE (lhs); 3759 3760 cst0 = build_int_cst (type, 0); 3761 cst1 = build_int_cst (type, 1); 3762 tmp = vect_recog_temp_ssa_var (type, NULL); 3763 pattern_stmt = gimple_build_assign (tmp, COND_EXPR, var, cst1, cst0); 3764 3765 if (!useless_type_conversion_p (type, TREE_TYPE (lhs))) 3766 { 3767 tree new_vectype = get_vectype_for_scalar_type (type); 3768 new_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo); 3769 set_vinfo_for_stmt (pattern_stmt, new_stmt_info); 3770 STMT_VINFO_VECTYPE (new_stmt_info) = new_vectype; 3771 new_pattern_def_seq (stmt_vinfo, pattern_stmt); 3772 3773 lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL); 3774 pattern_stmt = gimple_build_assign (lhs, CONVERT_EXPR, tmp); 3775 } 3776 } 3777 3778 *type_out = vectype; 3779 *type_in = vectype; 3780 stmts->safe_push (last_stmt); 3781 if (dump_enabled_p ()) 3782 dump_printf_loc (MSG_NOTE, vect_location, 3783 "vect_recog_bool_pattern: detected:\n"); 3784 3785 return pattern_stmt; 3786 } 3787 else if (rhs_code == COND_EXPR 3788 && TREE_CODE (var) == SSA_NAME) 3789 { 3790 vectype = get_vectype_for_scalar_type (TREE_TYPE (lhs)); 3791 if (vectype == NULL_TREE) 3792 return NULL; 3793 3794 /* Build a scalar type for the boolean result that when 3795 vectorized matches the vector type of the result in 3796 size and number of elements. */ 3797 unsigned prec 3798 = vector_element_size (tree_to_poly_uint64 (TYPE_SIZE (vectype)), 3799 TYPE_VECTOR_SUBPARTS (vectype)); 3800 3801 tree type 3802 = build_nonstandard_integer_type (prec, 3803 TYPE_UNSIGNED (TREE_TYPE (var))); 3804 if (get_vectype_for_scalar_type (type) == NULL_TREE) 3805 return NULL; 3806 3807 if (!check_bool_pattern (var, vinfo, bool_stmts)) 3808 return NULL; 3809 3810 rhs = adjust_bool_stmts (bool_stmts, type, last_stmt); 3811 3812 lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL); 3813 pattern_stmt 3814 = gimple_build_assign (lhs, COND_EXPR, 3815 build2 (NE_EXPR, boolean_type_node, 3816 rhs, build_int_cst (type, 0)), 3817 gimple_assign_rhs2 (last_stmt), 3818 gimple_assign_rhs3 (last_stmt)); 3819 *type_out = vectype; 3820 *type_in = vectype; 3821 stmts->safe_push (last_stmt); 3822 if (dump_enabled_p ()) 3823 dump_printf_loc (MSG_NOTE, vect_location, 3824 "vect_recog_bool_pattern: detected:\n"); 3825 3826 return pattern_stmt; 3827 } 3828 else if (rhs_code == SSA_NAME 3829 && STMT_VINFO_DATA_REF (stmt_vinfo)) 3830 { 3831 stmt_vec_info pattern_stmt_info; 3832 vectype = STMT_VINFO_VECTYPE (stmt_vinfo); 3833 gcc_assert (vectype != NULL_TREE); 3834 if (!VECTOR_MODE_P (TYPE_MODE (vectype))) 3835 return NULL; 3836 3837 if (check_bool_pattern (var, vinfo, bool_stmts)) 3838 rhs = adjust_bool_stmts (bool_stmts, TREE_TYPE (vectype), last_stmt); 3839 else 3840 { 3841 tree type = search_type_for_mask (var, vinfo); 3842 tree cst0, cst1, new_vectype; 3843 3844 if (!type) 3845 return NULL; 3846 3847 if (TYPE_MODE (type) == TYPE_MODE (TREE_TYPE (vectype))) 3848 type = TREE_TYPE (vectype); 3849 3850 cst0 = build_int_cst (type, 0); 3851 cst1 = build_int_cst (type, 1); 3852 new_vectype = get_vectype_for_scalar_type (type); 3853 3854 rhs = vect_recog_temp_ssa_var (type, NULL); 3855 pattern_stmt = gimple_build_assign (rhs, COND_EXPR, var, cst1, cst0); 3856 3857 pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo); 3858 set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info); 3859 STMT_VINFO_VECTYPE (pattern_stmt_info) = new_vectype; 3860 append_pattern_def_seq (stmt_vinfo, pattern_stmt); 3861 } 3862 3863 lhs = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vectype), lhs); 3864 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 3865 { 3866 tree rhs2 = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL); 3867 gimple *cast_stmt = gimple_build_assign (rhs2, NOP_EXPR, rhs); 3868 append_pattern_def_seq (stmt_vinfo, cast_stmt); 3869 rhs = rhs2; 3870 } 3871 pattern_stmt = gimple_build_assign (lhs, SSA_NAME, rhs); 3872 pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo); 3873 set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info); 3874 STMT_VINFO_DATA_REF (pattern_stmt_info) 3875 = STMT_VINFO_DATA_REF (stmt_vinfo); 3876 STMT_VINFO_DR_WRT_VEC_LOOP (pattern_stmt_info) 3877 = STMT_VINFO_DR_WRT_VEC_LOOP (stmt_vinfo); 3878 DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo)) = pattern_stmt; 3879 *type_out = vectype; 3880 *type_in = vectype; 3881 stmts->safe_push (last_stmt); 3882 if (dump_enabled_p ()) 3883 dump_printf_loc (MSG_NOTE, vect_location, 3884 "vect_recog_bool_pattern: detected:\n"); 3885 return pattern_stmt; 3886 } 3887 else 3888 return NULL; 3889 } 3890 3891 3892 /* A helper for vect_recog_mask_conversion_pattern. Build 3893 conversion of MASK to a type suitable for masking VECTYPE. 3894 Built statement gets required vectype and is appended to 3895 a pattern sequence of STMT_VINFO. 3896 3897 Return converted mask. */ 3898 3899 static tree 3900 build_mask_conversion (tree mask, tree vectype, stmt_vec_info stmt_vinfo, 3901 vec_info *vinfo) 3902 { 3903 gimple *stmt; 3904 tree masktype, tmp; 3905 stmt_vec_info new_stmt_info; 3906 3907 masktype = build_same_sized_truth_vector_type (vectype); 3908 tmp = vect_recog_temp_ssa_var (TREE_TYPE (masktype), NULL); 3909 stmt = gimple_build_assign (tmp, CONVERT_EXPR, mask); 3910 new_stmt_info = new_stmt_vec_info (stmt, vinfo); 3911 set_vinfo_for_stmt (stmt, new_stmt_info); 3912 STMT_VINFO_VECTYPE (new_stmt_info) = masktype; 3913 append_pattern_def_seq (stmt_vinfo, stmt); 3914 3915 return tmp; 3916 } 3917 3918 3919 /* Function vect_recog_mask_conversion_pattern 3920 3921 Try to find statements which require boolean type 3922 converison. Additional conversion statements are 3923 added to handle such cases. For example: 3924 3925 bool m_1, m_2, m_3; 3926 int i_4, i_5; 3927 double d_6, d_7; 3928 char c_1, c_2, c_3; 3929 3930 S1 m_1 = i_4 > i_5; 3931 S2 m_2 = d_6 < d_7; 3932 S3 m_3 = m_1 & m_2; 3933 S4 c_1 = m_3 ? c_2 : c_3; 3934 3935 Will be transformed into: 3936 3937 S1 m_1 = i_4 > i_5; 3938 S2 m_2 = d_6 < d_7; 3939 S3'' m_2' = (_Bool[bitsize=32])m_2 3940 S3' m_3' = m_1 & m_2'; 3941 S4'' m_3'' = (_Bool[bitsize=8])m_3' 3942 S4' c_1' = m_3'' ? c_2 : c_3; */ 3943 3944 static gimple * 3945 vect_recog_mask_conversion_pattern (vec<gimple *> *stmts, tree *type_in, 3946 tree *type_out) 3947 { 3948 gimple *last_stmt = stmts->pop (); 3949 enum tree_code rhs_code; 3950 tree lhs = NULL_TREE, rhs1, rhs2, tmp, rhs1_type, rhs2_type; 3951 tree vectype1, vectype2; 3952 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 3953 stmt_vec_info pattern_stmt_info; 3954 vec_info *vinfo = stmt_vinfo->vinfo; 3955 3956 /* Check for MASK_LOAD ans MASK_STORE calls requiring mask conversion. */ 3957 if (is_gimple_call (last_stmt) 3958 && gimple_call_internal_p (last_stmt) 3959 && (gimple_call_internal_fn (last_stmt) == IFN_MASK_STORE 3960 || gimple_call_internal_fn (last_stmt) == IFN_MASK_LOAD)) 3961 { 3962 gcall *pattern_stmt; 3963 bool load = (gimple_call_internal_fn (last_stmt) == IFN_MASK_LOAD); 3964 3965 if (load) 3966 { 3967 lhs = gimple_call_lhs (last_stmt); 3968 vectype1 = get_vectype_for_scalar_type (TREE_TYPE (lhs)); 3969 } 3970 else 3971 { 3972 rhs2 = gimple_call_arg (last_stmt, 3); 3973 vectype1 = get_vectype_for_scalar_type (TREE_TYPE (rhs2)); 3974 } 3975 3976 rhs1 = gimple_call_arg (last_stmt, 2); 3977 rhs1_type = search_type_for_mask (rhs1, vinfo); 3978 if (!rhs1_type) 3979 return NULL; 3980 vectype2 = get_mask_type_for_scalar_type (rhs1_type); 3981 3982 if (!vectype1 || !vectype2 3983 || known_eq (TYPE_VECTOR_SUBPARTS (vectype1), 3984 TYPE_VECTOR_SUBPARTS (vectype2))) 3985 return NULL; 3986 3987 tmp = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo); 3988 3989 if (load) 3990 { 3991 lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL); 3992 pattern_stmt 3993 = gimple_build_call_internal (IFN_MASK_LOAD, 3, 3994 gimple_call_arg (last_stmt, 0), 3995 gimple_call_arg (last_stmt, 1), 3996 tmp); 3997 gimple_call_set_lhs (pattern_stmt, lhs); 3998 } 3999 else 4000 pattern_stmt 4001 = gimple_build_call_internal (IFN_MASK_STORE, 4, 4002 gimple_call_arg (last_stmt, 0), 4003 gimple_call_arg (last_stmt, 1), 4004 tmp, 4005 gimple_call_arg (last_stmt, 3)); 4006 4007 gimple_call_set_nothrow (pattern_stmt, true); 4008 4009 pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo); 4010 set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info); 4011 STMT_VINFO_DATA_REF (pattern_stmt_info) 4012 = STMT_VINFO_DATA_REF (stmt_vinfo); 4013 STMT_VINFO_DR_WRT_VEC_LOOP (pattern_stmt_info) 4014 = STMT_VINFO_DR_WRT_VEC_LOOP (stmt_vinfo); 4015 DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo)) = pattern_stmt; 4016 4017 *type_out = vectype1; 4018 *type_in = vectype1; 4019 stmts->safe_push (last_stmt); 4020 if (dump_enabled_p ()) 4021 dump_printf_loc (MSG_NOTE, vect_location, 4022 "vect_recog_mask_conversion_pattern: detected:\n"); 4023 4024 return pattern_stmt; 4025 } 4026 4027 if (!is_gimple_assign (last_stmt)) 4028 return NULL; 4029 4030 gimple *pattern_stmt; 4031 lhs = gimple_assign_lhs (last_stmt); 4032 rhs1 = gimple_assign_rhs1 (last_stmt); 4033 rhs_code = gimple_assign_rhs_code (last_stmt); 4034 4035 /* Check for cond expression requiring mask conversion. */ 4036 if (rhs_code == COND_EXPR) 4037 { 4038 /* vect_recog_mixed_size_cond_pattern could apply. 4039 Do nothing then. */ 4040 if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 4041 return NULL; 4042 4043 vectype1 = get_vectype_for_scalar_type (TREE_TYPE (lhs)); 4044 4045 if (TREE_CODE (rhs1) == SSA_NAME) 4046 { 4047 rhs1_type = search_type_for_mask (rhs1, vinfo); 4048 if (!rhs1_type) 4049 return NULL; 4050 } 4051 else if (COMPARISON_CLASS_P (rhs1)) 4052 { 4053 /* Check whether we're comparing scalar booleans and (if so) 4054 whether a better mask type exists than the mask associated 4055 with boolean-sized elements. This avoids unnecessary packs 4056 and unpacks if the booleans are set from comparisons of 4057 wider types. E.g. in: 4058 4059 int x1, x2, x3, x4, y1, y1; 4060 ... 4061 bool b1 = (x1 == x2); 4062 bool b2 = (x3 == x4); 4063 ... = b1 == b2 ? y1 : y2; 4064 4065 it is better for b1 and b2 to use the mask type associated 4066 with int elements rather bool (byte) elements. */ 4067 rhs1_type = search_type_for_mask (TREE_OPERAND (rhs1, 0), vinfo); 4068 if (!rhs1_type) 4069 rhs1_type = TREE_TYPE (TREE_OPERAND (rhs1, 0)); 4070 } 4071 else 4072 return NULL; 4073 4074 vectype2 = get_mask_type_for_scalar_type (rhs1_type); 4075 4076 if (!vectype1 || !vectype2) 4077 return NULL; 4078 4079 /* Continue if a conversion is needed. Also continue if we have 4080 a comparison whose vector type would normally be different from 4081 VECTYPE2 when considered in isolation. In that case we'll 4082 replace the comparison with an SSA name (so that we can record 4083 its vector type) and behave as though the comparison was an SSA 4084 name from the outset. */ 4085 if (known_eq (TYPE_VECTOR_SUBPARTS (vectype1), 4086 TYPE_VECTOR_SUBPARTS (vectype2)) 4087 && (TREE_CODE (rhs1) == SSA_NAME 4088 || rhs1_type == TREE_TYPE (TREE_OPERAND (rhs1, 0)))) 4089 return NULL; 4090 4091 /* If rhs1 is invariant and we can promote it leave the COND_EXPR 4092 in place, we can handle it in vectorizable_condition. This avoids 4093 unnecessary promotion stmts and increased vectorization factor. */ 4094 if (COMPARISON_CLASS_P (rhs1) 4095 && INTEGRAL_TYPE_P (rhs1_type) 4096 && known_le (TYPE_VECTOR_SUBPARTS (vectype1), 4097 TYPE_VECTOR_SUBPARTS (vectype2))) 4098 { 4099 gimple *dummy; 4100 enum vect_def_type dt; 4101 if (vect_is_simple_use (TREE_OPERAND (rhs1, 0), stmt_vinfo->vinfo, 4102 &dummy, &dt) 4103 && dt == vect_external_def 4104 && vect_is_simple_use (TREE_OPERAND (rhs1, 1), stmt_vinfo->vinfo, 4105 &dummy, &dt) 4106 && (dt == vect_external_def 4107 || dt == vect_constant_def)) 4108 { 4109 tree wide_scalar_type = build_nonstandard_integer_type 4110 (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (vectype1))), 4111 TYPE_UNSIGNED (rhs1_type)); 4112 tree vectype3 = get_vectype_for_scalar_type (wide_scalar_type); 4113 if (expand_vec_cond_expr_p (vectype1, vectype3, TREE_CODE (rhs1))) 4114 return NULL; 4115 } 4116 } 4117 4118 /* If rhs1 is a comparison we need to move it into a 4119 separate statement. */ 4120 if (TREE_CODE (rhs1) != SSA_NAME) 4121 { 4122 tmp = vect_recog_temp_ssa_var (TREE_TYPE (rhs1), NULL); 4123 pattern_stmt = gimple_build_assign (tmp, rhs1); 4124 rhs1 = tmp; 4125 4126 pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo); 4127 set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info); 4128 STMT_VINFO_VECTYPE (pattern_stmt_info) = vectype2; 4129 append_pattern_def_seq (stmt_vinfo, pattern_stmt); 4130 } 4131 4132 if (maybe_ne (TYPE_VECTOR_SUBPARTS (vectype1), 4133 TYPE_VECTOR_SUBPARTS (vectype2))) 4134 tmp = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo); 4135 else 4136 tmp = rhs1; 4137 4138 lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL); 4139 pattern_stmt = gimple_build_assign (lhs, COND_EXPR, tmp, 4140 gimple_assign_rhs2 (last_stmt), 4141 gimple_assign_rhs3 (last_stmt)); 4142 4143 *type_out = vectype1; 4144 *type_in = vectype1; 4145 stmts->safe_push (last_stmt); 4146 if (dump_enabled_p ()) 4147 dump_printf_loc (MSG_NOTE, vect_location, 4148 "vect_recog_mask_conversion_pattern: detected:\n"); 4149 4150 return pattern_stmt; 4151 } 4152 4153 /* Now check for binary boolean operations requiring conversion for 4154 one of operands. */ 4155 if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (lhs))) 4156 return NULL; 4157 4158 if (rhs_code != BIT_IOR_EXPR 4159 && rhs_code != BIT_XOR_EXPR 4160 && rhs_code != BIT_AND_EXPR 4161 && TREE_CODE_CLASS (rhs_code) != tcc_comparison) 4162 return NULL; 4163 4164 rhs2 = gimple_assign_rhs2 (last_stmt); 4165 4166 rhs1_type = search_type_for_mask (rhs1, vinfo); 4167 rhs2_type = search_type_for_mask (rhs2, vinfo); 4168 4169 if (!rhs1_type || !rhs2_type 4170 || TYPE_PRECISION (rhs1_type) == TYPE_PRECISION (rhs2_type)) 4171 return NULL; 4172 4173 if (TYPE_PRECISION (rhs1_type) < TYPE_PRECISION (rhs2_type)) 4174 { 4175 vectype1 = get_mask_type_for_scalar_type (rhs1_type); 4176 if (!vectype1) 4177 return NULL; 4178 rhs2 = build_mask_conversion (rhs2, vectype1, stmt_vinfo, vinfo); 4179 } 4180 else 4181 { 4182 vectype1 = get_mask_type_for_scalar_type (rhs2_type); 4183 if (!vectype1) 4184 return NULL; 4185 rhs1 = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo); 4186 } 4187 4188 lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL); 4189 pattern_stmt = gimple_build_assign (lhs, rhs_code, rhs1, rhs2); 4190 4191 *type_out = vectype1; 4192 *type_in = vectype1; 4193 stmts->safe_push (last_stmt); 4194 if (dump_enabled_p ()) 4195 dump_printf_loc (MSG_NOTE, vect_location, 4196 "vect_recog_mask_conversion_pattern: detected:\n"); 4197 4198 return pattern_stmt; 4199 } 4200 4201 /* STMT is a load or store. If the load or store is conditional, return 4202 the boolean condition under which it occurs, otherwise return null. */ 4203 4204 static tree 4205 vect_get_load_store_mask (gimple *stmt) 4206 { 4207 if (gassign *def_assign = dyn_cast <gassign *> (stmt)) 4208 { 4209 gcc_assert (gimple_assign_single_p (def_assign)); 4210 return NULL_TREE; 4211 } 4212 4213 if (gcall *def_call = dyn_cast <gcall *> (stmt)) 4214 { 4215 internal_fn ifn = gimple_call_internal_fn (def_call); 4216 int mask_index = internal_fn_mask_index (ifn); 4217 return gimple_call_arg (def_call, mask_index); 4218 } 4219 4220 gcc_unreachable (); 4221 } 4222 4223 /* Return the scalar offset type that an internal gather/scatter function 4224 should use. GS_INFO describes the gather/scatter operation. */ 4225 4226 static tree 4227 vect_get_gather_scatter_offset_type (gather_scatter_info *gs_info) 4228 { 4229 tree offset_type = TREE_TYPE (gs_info->offset); 4230 unsigned int element_bits = tree_to_uhwi (TYPE_SIZE (gs_info->element_type)); 4231 4232 /* Enforced by vect_check_gather_scatter. */ 4233 unsigned int offset_bits = TYPE_PRECISION (offset_type); 4234 gcc_assert (element_bits >= offset_bits); 4235 4236 /* If the offset is narrower than the elements, extend it according 4237 to its sign. */ 4238 if (element_bits > offset_bits) 4239 return build_nonstandard_integer_type (element_bits, 4240 TYPE_UNSIGNED (offset_type)); 4241 4242 return offset_type; 4243 } 4244 4245 /* Return MASK if MASK is suitable for masking an operation on vectors 4246 of type VECTYPE, otherwise convert it into such a form and return 4247 the result. Associate any conversion statements with STMT_INFO's 4248 pattern. */ 4249 4250 static tree 4251 vect_convert_mask_for_vectype (tree mask, tree vectype, 4252 stmt_vec_info stmt_info, vec_info *vinfo) 4253 { 4254 tree mask_type = search_type_for_mask (mask, vinfo); 4255 if (mask_type) 4256 { 4257 tree mask_vectype = get_mask_type_for_scalar_type (mask_type); 4258 if (mask_vectype 4259 && maybe_ne (TYPE_VECTOR_SUBPARTS (vectype), 4260 TYPE_VECTOR_SUBPARTS (mask_vectype))) 4261 mask = build_mask_conversion (mask, vectype, stmt_info, vinfo); 4262 } 4263 return mask; 4264 } 4265 4266 /* Return the equivalent of: 4267 4268 fold_convert (TYPE, VALUE) 4269 4270 with the expectation that the operation will be vectorized. 4271 If new statements are needed, add them as pattern statements 4272 to STMT_INFO. */ 4273 4274 static tree 4275 vect_add_conversion_to_patterm (tree type, tree value, 4276 stmt_vec_info stmt_info, 4277 vec_info *vinfo) 4278 { 4279 if (useless_type_conversion_p (type, TREE_TYPE (value))) 4280 return value; 4281 4282 tree new_value = vect_recog_temp_ssa_var (type, NULL); 4283 gassign *conversion = gimple_build_assign (new_value, CONVERT_EXPR, value); 4284 stmt_vec_info new_stmt_info = new_stmt_vec_info (conversion, vinfo); 4285 set_vinfo_for_stmt (conversion, new_stmt_info); 4286 STMT_VINFO_VECTYPE (new_stmt_info) = get_vectype_for_scalar_type (type); 4287 append_pattern_def_seq (stmt_info, conversion); 4288 return new_value; 4289 } 4290 4291 /* Try to convert STMT into a call to a gather load or scatter store 4292 internal function. Return the final statement on success and set 4293 *TYPE_IN and *TYPE_OUT to the vector type being loaded or stored. 4294 4295 This function only handles gathers and scatters that were recognized 4296 as such from the outset (indicated by STMT_VINFO_GATHER_SCATTER_P). */ 4297 4298 static gimple * 4299 vect_try_gather_scatter_pattern (gimple *stmt, stmt_vec_info last_stmt_info, 4300 tree *type_in, tree *type_out) 4301 { 4302 /* Currently we only support this for loop vectorization. */ 4303 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 4304 loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (stmt_info->vinfo); 4305 if (!loop_vinfo) 4306 return NULL; 4307 4308 /* Make sure that we're looking at a gather load or scatter store. */ 4309 data_reference *dr = STMT_VINFO_DATA_REF (stmt_info); 4310 if (!dr || !STMT_VINFO_GATHER_SCATTER_P (stmt_info)) 4311 return NULL; 4312 4313 /* Get the boolean that controls whether the load or store happens. 4314 This is null if the operation is unconditional. */ 4315 tree mask = vect_get_load_store_mask (stmt); 4316 4317 /* Make sure that the target supports an appropriate internal 4318 function for the gather/scatter operation. */ 4319 gather_scatter_info gs_info; 4320 if (!vect_check_gather_scatter (stmt, loop_vinfo, &gs_info) 4321 || gs_info.decl) 4322 return NULL; 4323 4324 /* Convert the mask to the right form. */ 4325 tree gs_vectype = get_vectype_for_scalar_type (gs_info.element_type); 4326 if (mask) 4327 mask = vect_convert_mask_for_vectype (mask, gs_vectype, last_stmt_info, 4328 loop_vinfo); 4329 4330 /* Get the invariant base and non-invariant offset, converting the 4331 latter to the same width as the vector elements. */ 4332 tree base = gs_info.base; 4333 tree offset_type = vect_get_gather_scatter_offset_type (&gs_info); 4334 tree offset = vect_add_conversion_to_patterm (offset_type, gs_info.offset, 4335 last_stmt_info, loop_vinfo); 4336 4337 /* Build the new pattern statement. */ 4338 tree scale = size_int (gs_info.scale); 4339 gcall *pattern_stmt; 4340 if (DR_IS_READ (dr)) 4341 { 4342 if (mask != NULL) 4343 pattern_stmt = gimple_build_call_internal (gs_info.ifn, 4, base, 4344 offset, scale, mask); 4345 else 4346 pattern_stmt = gimple_build_call_internal (gs_info.ifn, 3, base, 4347 offset, scale); 4348 tree load_lhs = vect_recog_temp_ssa_var (gs_info.element_type, NULL); 4349 gimple_call_set_lhs (pattern_stmt, load_lhs); 4350 } 4351 else 4352 { 4353 tree rhs = vect_get_store_rhs (stmt); 4354 if (mask != NULL) 4355 pattern_stmt = gimple_build_call_internal (IFN_MASK_SCATTER_STORE, 5, 4356 base, offset, scale, rhs, 4357 mask); 4358 else 4359 pattern_stmt = gimple_build_call_internal (IFN_SCATTER_STORE, 4, 4360 base, offset, scale, rhs); 4361 } 4362 gimple_call_set_nothrow (pattern_stmt, true); 4363 4364 /* Copy across relevant vectorization info and associate DR with the 4365 new pattern statement instead of the original statement. */ 4366 stmt_vec_info pattern_stmt_info = new_stmt_vec_info (pattern_stmt, 4367 loop_vinfo); 4368 set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info); 4369 STMT_VINFO_DATA_REF (pattern_stmt_info) = dr; 4370 STMT_VINFO_DR_WRT_VEC_LOOP (pattern_stmt_info) 4371 = STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info); 4372 STMT_VINFO_GATHER_SCATTER_P (pattern_stmt_info) 4373 = STMT_VINFO_GATHER_SCATTER_P (stmt_info); 4374 DR_STMT (dr) = pattern_stmt; 4375 4376 tree vectype = STMT_VINFO_VECTYPE (stmt_info); 4377 *type_out = vectype; 4378 *type_in = vectype; 4379 4380 if (dump_enabled_p ()) 4381 dump_printf_loc (MSG_NOTE, vect_location, 4382 "gather/scatter pattern detected:\n"); 4383 4384 return pattern_stmt; 4385 } 4386 4387 /* Pattern wrapper around vect_try_gather_scatter_pattern. */ 4388 4389 static gimple * 4390 vect_recog_gather_scatter_pattern (vec<gimple *> *stmts, tree *type_in, 4391 tree *type_out) 4392 { 4393 gimple *last_stmt = stmts->pop (); 4394 stmt_vec_info last_stmt_info = vinfo_for_stmt (last_stmt); 4395 gimple *pattern_stmt = vect_try_gather_scatter_pattern (last_stmt, 4396 last_stmt_info, 4397 type_in, type_out); 4398 if (pattern_stmt) 4399 stmts->safe_push (last_stmt); 4400 return pattern_stmt; 4401 } 4402 4403 /* Mark statements that are involved in a pattern. */ 4404 4405 static inline void 4406 vect_mark_pattern_stmts (gimple *orig_stmt, gimple *pattern_stmt, 4407 tree pattern_vectype) 4408 { 4409 stmt_vec_info pattern_stmt_info, def_stmt_info; 4410 stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt); 4411 vec_info *vinfo = orig_stmt_info->vinfo; 4412 gimple *def_stmt; 4413 4414 pattern_stmt_info = vinfo_for_stmt (pattern_stmt); 4415 if (pattern_stmt_info == NULL) 4416 { 4417 pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo); 4418 set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info); 4419 } 4420 gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt)); 4421 4422 STMT_VINFO_RELATED_STMT (pattern_stmt_info) = orig_stmt; 4423 STMT_VINFO_DEF_TYPE (pattern_stmt_info) 4424 = STMT_VINFO_DEF_TYPE (orig_stmt_info); 4425 STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype; 4426 STMT_VINFO_IN_PATTERN_P (orig_stmt_info) = true; 4427 STMT_VINFO_RELATED_STMT (orig_stmt_info) = pattern_stmt; 4428 STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info) 4429 = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info); 4430 if (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info)) 4431 { 4432 gimple_stmt_iterator si; 4433 for (si = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info)); 4434 !gsi_end_p (si); gsi_next (&si)) 4435 { 4436 def_stmt = gsi_stmt (si); 4437 def_stmt_info = vinfo_for_stmt (def_stmt); 4438 if (def_stmt_info == NULL) 4439 { 4440 def_stmt_info = new_stmt_vec_info (def_stmt, vinfo); 4441 set_vinfo_for_stmt (def_stmt, def_stmt_info); 4442 } 4443 gimple_set_bb (def_stmt, gimple_bb (orig_stmt)); 4444 STMT_VINFO_RELATED_STMT (def_stmt_info) = orig_stmt; 4445 STMT_VINFO_DEF_TYPE (def_stmt_info) = vect_internal_def; 4446 if (STMT_VINFO_VECTYPE (def_stmt_info) == NULL_TREE) 4447 STMT_VINFO_VECTYPE (def_stmt_info) = pattern_vectype; 4448 } 4449 } 4450 } 4451 4452 /* Function vect_pattern_recog_1 4453 4454 Input: 4455 PATTERN_RECOG_FUNC: A pointer to a function that detects a certain 4456 computation pattern. 4457 STMT: A stmt from which the pattern search should start. 4458 4459 If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an 4460 expression that computes the same functionality and can be used to 4461 replace the sequence of stmts that are involved in the pattern. 4462 4463 Output: 4464 This function checks if the expression returned by PATTERN_RECOG_FUNC is 4465 supported in vector form by the target. We use 'TYPE_IN' to obtain the 4466 relevant vector type. If 'TYPE_IN' is already a vector type, then this 4467 indicates that target support had already been checked by PATTERN_RECOG_FUNC. 4468 If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits 4469 to the available target pattern. 4470 4471 This function also does some bookkeeping, as explained in the documentation 4472 for vect_recog_pattern. */ 4473 4474 static bool 4475 vect_pattern_recog_1 (vect_recog_func *recog_func, 4476 gimple_stmt_iterator si, 4477 vec<gimple *> *stmts_to_replace) 4478 { 4479 gimple *stmt = gsi_stmt (si), *pattern_stmt; 4480 stmt_vec_info stmt_info; 4481 loop_vec_info loop_vinfo; 4482 tree pattern_vectype; 4483 tree type_in, type_out; 4484 enum tree_code code; 4485 int i; 4486 gimple *next; 4487 4488 stmts_to_replace->truncate (0); 4489 stmts_to_replace->quick_push (stmt); 4490 pattern_stmt = recog_func->fn (stmts_to_replace, &type_in, &type_out); 4491 if (!pattern_stmt) 4492 return false; 4493 4494 stmt = stmts_to_replace->last (); 4495 stmt_info = vinfo_for_stmt (stmt); 4496 loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info); 4497 4498 if (VECTOR_BOOLEAN_TYPE_P (type_in) 4499 || VECTOR_TYPE_P (type_in)) 4500 { 4501 /* No need to check target support (already checked by the pattern 4502 recognition function). */ 4503 pattern_vectype = type_out ? type_out : type_in; 4504 } 4505 else 4506 { 4507 /* Check target support */ 4508 type_in = get_vectype_for_scalar_type (type_in); 4509 if (!type_in) 4510 return false; 4511 if (type_out) 4512 type_out = get_vectype_for_scalar_type (type_out); 4513 else 4514 type_out = type_in; 4515 if (!type_out) 4516 return false; 4517 pattern_vectype = type_out; 4518 4519 if (is_gimple_assign (pattern_stmt)) 4520 { 4521 enum insn_code icode; 4522 code = gimple_assign_rhs_code (pattern_stmt); 4523 optab optab = optab_for_tree_code (code, type_in, optab_default); 4524 machine_mode vec_mode = TYPE_MODE (type_in); 4525 if (!optab 4526 || (icode = optab_handler (optab, vec_mode)) == CODE_FOR_nothing 4527 || (insn_data[icode].operand[0].mode != TYPE_MODE (type_out))) 4528 return false; 4529 } 4530 else 4531 gcc_assert (is_gimple_call (pattern_stmt)); 4532 } 4533 4534 /* Found a vectorizable pattern. */ 4535 if (dump_enabled_p ()) 4536 { 4537 dump_printf_loc (MSG_NOTE, vect_location, 4538 "%s pattern recognized: ", recog_func->name); 4539 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 4540 } 4541 4542 /* Mark the stmts that are involved in the pattern. */ 4543 vect_mark_pattern_stmts (stmt, pattern_stmt, pattern_vectype); 4544 4545 /* Patterns cannot be vectorized using SLP, because they change the order of 4546 computation. */ 4547 if (loop_vinfo) 4548 FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next) 4549 if (next == stmt) 4550 LOOP_VINFO_REDUCTIONS (loop_vinfo).ordered_remove (i); 4551 4552 /* It is possible that additional pattern stmts are created and inserted in 4553 STMTS_TO_REPLACE. We create a stmt_info for each of them, and mark the 4554 relevant statements. */ 4555 for (i = 0; stmts_to_replace->iterate (i, &stmt) 4556 && (unsigned) i < (stmts_to_replace->length () - 1); 4557 i++) 4558 { 4559 stmt_info = vinfo_for_stmt (stmt); 4560 pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info); 4561 if (dump_enabled_p ()) 4562 { 4563 dump_printf_loc (MSG_NOTE, vect_location, 4564 "additional pattern stmt: "); 4565 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0); 4566 } 4567 4568 vect_mark_pattern_stmts (stmt, pattern_stmt, NULL_TREE); 4569 } 4570 4571 return true; 4572 } 4573 4574 4575 /* Function vect_pattern_recog 4576 4577 Input: 4578 LOOP_VINFO - a struct_loop_info of a loop in which we want to look for 4579 computation idioms. 4580 4581 Output - for each computation idiom that is detected we create a new stmt 4582 that provides the same functionality and that can be vectorized. We 4583 also record some information in the struct_stmt_info of the relevant 4584 stmts, as explained below: 4585 4586 At the entry to this function we have the following stmts, with the 4587 following initial value in the STMT_VINFO fields: 4588 4589 stmt in_pattern_p related_stmt vec_stmt 4590 S1: a_i = .... - - - 4591 S2: a_2 = ..use(a_i).. - - - 4592 S3: a_1 = ..use(a_2).. - - - 4593 S4: a_0 = ..use(a_1).. - - - 4594 S5: ... = ..use(a_0).. - - - 4595 4596 Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be 4597 represented by a single stmt. We then: 4598 - create a new stmt S6 equivalent to the pattern (the stmt is not 4599 inserted into the code) 4600 - fill in the STMT_VINFO fields as follows: 4601 4602 in_pattern_p related_stmt vec_stmt 4603 S1: a_i = .... - - - 4604 S2: a_2 = ..use(a_i).. - - - 4605 S3: a_1 = ..use(a_2).. - - - 4606 S4: a_0 = ..use(a_1).. true S6 - 4607 '---> S6: a_new = .... - S4 - 4608 S5: ... = ..use(a_0).. - - - 4609 4610 (the last stmt in the pattern (S4) and the new pattern stmt (S6) point 4611 to each other through the RELATED_STMT field). 4612 4613 S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead 4614 of S4 because it will replace all its uses. Stmts {S1,S2,S3} will 4615 remain irrelevant unless used by stmts other than S4. 4616 4617 If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3} 4618 (because they are marked as irrelevant). It will vectorize S6, and record 4619 a pointer to the new vector stmt VS6 from S6 (as usual). 4620 S4 will be skipped, and S5 will be vectorized as usual: 4621 4622 in_pattern_p related_stmt vec_stmt 4623 S1: a_i = .... - - - 4624 S2: a_2 = ..use(a_i).. - - - 4625 S3: a_1 = ..use(a_2).. - - - 4626 > VS6: va_new = .... - - - 4627 S4: a_0 = ..use(a_1).. true S6 VS6 4628 '---> S6: a_new = .... - S4 VS6 4629 > VS5: ... = ..vuse(va_new).. - - - 4630 S5: ... = ..use(a_0).. - - - 4631 4632 DCE could then get rid of {S1,S2,S3,S4,S5} (if their defs are not used 4633 elsewhere), and we'll end up with: 4634 4635 VS6: va_new = .... 4636 VS5: ... = ..vuse(va_new).. 4637 4638 In case of more than one pattern statements, e.g., widen-mult with 4639 intermediate type: 4640 4641 S1 a_t = ; 4642 S2 a_T = (TYPE) a_t; 4643 '--> S3: a_it = (interm_type) a_t; 4644 S4 prod_T = a_T * CONST; 4645 '--> S5: prod_T' = a_it w* CONST; 4646 4647 there may be other users of a_T outside the pattern. In that case S2 will 4648 be marked as relevant (as well as S3), and both S2 and S3 will be analyzed 4649 and vectorized. The vector stmt VS2 will be recorded in S2, and VS3 will 4650 be recorded in S3. */ 4651 4652 void 4653 vect_pattern_recog (vec_info *vinfo) 4654 { 4655 struct loop *loop; 4656 basic_block *bbs; 4657 unsigned int nbbs; 4658 gimple_stmt_iterator si; 4659 unsigned int i, j; 4660 auto_vec<gimple *, 1> stmts_to_replace; 4661 gimple *stmt; 4662 4663 if (dump_enabled_p ()) 4664 dump_printf_loc (MSG_NOTE, vect_location, 4665 "=== vect_pattern_recog ===\n"); 4666 4667 if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo)) 4668 { 4669 loop = LOOP_VINFO_LOOP (loop_vinfo); 4670 bbs = LOOP_VINFO_BBS (loop_vinfo); 4671 nbbs = loop->num_nodes; 4672 4673 /* Scan through the loop stmts, applying the pattern recognition 4674 functions starting at each stmt visited: */ 4675 for (i = 0; i < nbbs; i++) 4676 { 4677 basic_block bb = bbs[i]; 4678 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 4679 { 4680 /* Scan over all generic vect_recog_xxx_pattern functions. */ 4681 for (j = 0; j < NUM_PATTERNS; j++) 4682 if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si, 4683 &stmts_to_replace)) 4684 break; 4685 } 4686 } 4687 } 4688 else 4689 { 4690 bb_vec_info bb_vinfo = as_a <bb_vec_info> (vinfo); 4691 for (si = bb_vinfo->region_begin; 4692 gsi_stmt (si) != gsi_stmt (bb_vinfo->region_end); gsi_next (&si)) 4693 { 4694 if ((stmt = gsi_stmt (si)) 4695 && vinfo_for_stmt (stmt) 4696 && !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt))) 4697 continue; 4698 4699 /* Scan over all generic vect_recog_xxx_pattern functions. */ 4700 for (j = 0; j < NUM_PATTERNS; j++) 4701 if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si, 4702 &stmts_to_replace)) 4703 break; 4704 } 4705 } 4706 } 4707