tree-vect-patterns.c revision 169690
1236628Sgnn/* Analysis Utilities for Loop Vectorization. 2236628Sgnn Copyright (C) 2006 Free Software Foundation, Inc. 3236628Sgnn Contributed by Dorit Nuzman <dorit@il.ibm.com> 4236628Sgnn 5236628SgnnThis file is part of GCC. 6236628Sgnn 7236628SgnnGCC is free software; you can redistribute it and/or modify it under 8236628Sgnnthe terms of the GNU General Public License as published by the Free 9236628SgnnSoftware Foundation; either version 2, or (at your option) any later 10236628Sgnnversion. 11236628Sgnn 12236628SgnnGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13236628SgnnWARRANTY; without even the implied warranty of MERCHANTABILITY or 14236628SgnnFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15236628Sgnnfor more details. 16236628Sgnn 17236628SgnnYou should have received a copy of the GNU General Public License 18236628Sgnnalong with GCC; see the file COPYING. If not, write to the Free 19236628SgnnSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20236628Sgnn02110-1301, USA. */ 21333617Sdteske 22333617Sdteske#include "config.h" 23236628Sgnn#include "system.h" 24236628Sgnn#include "coretypes.h" 25236628Sgnn#include "tm.h" 26236628Sgnn#include "ggc.h" 27236628Sgnn#include "tree.h" 28236628Sgnn 29236628Sgnn#include "target.h" 30286420Smarkj#include "basic-block.h" 31248846Sgnn#include "diagnostic.h" 32248846Sgnn#include "tree-flow.h" 33236628Sgnn#include "tree-dump.h" 34333617Sdteske#include "timevar.h" 35333617Sdteske#include "cfgloop.h" 36333617Sdteske#include "expr.h" 37333617Sdteske#include "optabs.h" 38333617Sdteske#include "params.h" 39333617Sdteske#include "tree-data-ref.h" 40333617Sdteske#include "tree-vectorizer.h" 41236628Sgnn#include "recog.h" 42236628Sgnn#include "toplev.h" 43236628Sgnn 44238366Sgnn/* Function prototypes */ 45333617Sdteskestatic void vect_pattern_recog_1 46333617Sdteske (tree (* ) (tree, tree *, tree *), block_stmt_iterator); 47333617Sdteskestatic bool widened_name_p (tree, tree, tree *, tree *); 48333617Sdteske 49333617Sdteske/* Pattern recognition functions */ 50333617Sdteskestatic tree vect_recog_widen_sum_pattern (tree, tree *, tree *); 51333617Sdteskestatic tree vect_recog_widen_mult_pattern (tree, tree *, tree *); 52236628Sgnnstatic tree vect_recog_dot_prod_pattern (tree, tree *, tree *); 53236628Sgnnstatic vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = { 54238366Sgnn vect_recog_widen_mult_pattern, 55333617Sdteske vect_recog_widen_sum_pattern, 56333617Sdteske vect_recog_dot_prod_pattern}; 57333617Sdteske 58333617Sdteske 59333617Sdteske/* Function widened_name_p 60333617Sdteske 61333617Sdteske Check whether NAME, an ssa-name used in USE_STMT, 62333617Sdteske is a result of a type-promotion, such that: 63333617Sdteske DEF_STMT: NAME = NOP (name0) 64333617Sdteske where the type of name0 (HALF_TYPE) is smaller than the type of NAME. 65333617Sdteske*/ 66238366Sgnn 67236628Sgnnstatic bool 68236628Sgnnwidened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt) 69238366Sgnn{ 70333617Sdteske tree dummy; 71333617Sdteske loop_vec_info loop_vinfo; 72333617Sdteske stmt_vec_info stmt_vinfo; 73333617Sdteske tree expr; 74333617Sdteske tree type = TREE_TYPE (name); 75333617Sdteske tree oprnd0; 76333617Sdteske enum vect_def_type dt; 77333617Sdteske tree def; 78333617Sdteske 79236628Sgnn stmt_vinfo = vinfo_for_stmt (use_stmt); 80236628Sgnn loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo); 81236628Sgnn 82236628Sgnn if (!vect_is_simple_use (name, loop_vinfo, def_stmt, &def, &dt)) 83236628Sgnn return false; 84236628Sgnn 85236628Sgnn if (dt != vect_loop_def 86236628Sgnn && dt != vect_invariant_def && dt != vect_constant_def) 87236628Sgnn return false; 88236628Sgnn 89236628Sgnn if (! *def_stmt) 90236628Sgnn return false; 91236628Sgnn 92236628Sgnn if (TREE_CODE (*def_stmt) != MODIFY_EXPR) 93236628Sgnn return false; 94236628Sgnn 95236628Sgnn expr = TREE_OPERAND (*def_stmt, 1); 96236628Sgnn if (TREE_CODE (expr) != NOP_EXPR) 97236628Sgnn return false; 98236628Sgnn 99236628Sgnn oprnd0 = TREE_OPERAND (expr, 0); 100236628Sgnn 101236628Sgnn *half_type = TREE_TYPE (oprnd0); 102236628Sgnn if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type) 103236628Sgnn || (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type)) 104236628Sgnn || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2))) 105236628Sgnn return false; 106236628Sgnn 107236628Sgnn if (!vect_is_simple_use (oprnd0, loop_vinfo, &dummy, &dummy, &dt)) 108236628Sgnn return false; 109236628Sgnn 110236628Sgnn if (dt != vect_invariant_def && dt != vect_constant_def 111236628Sgnn && dt != vect_loop_def) 112236628Sgnn return false; 113236628Sgnn 114236628Sgnn return true; 115333617Sdteske} 116333617Sdteske 117333617Sdteske 118333617Sdteske/* Function vect_recog_dot_prod_pattern 119333617Sdteske 120333617Sdteske Try to find the following pattern: 121333617Sdteske 122333617Sdteske type x_t, y_t; 123333617Sdteske TYPE1 prod; 124333617Sdteske TYPE2 sum = init; 125333617Sdteske loop: 126333617Sdteske sum_0 = phi <init, sum_1> 127333617Sdteske S1 x_t = ... 128333617Sdteske S2 y_t = ... 129333617Sdteske S3 x_T = (TYPE1) x_t; 130333617Sdteske S4 y_T = (TYPE1) y_t; 131333617Sdteske S5 prod = x_T * y_T; 132333617Sdteske [S6 prod = (TYPE2) prod; #optional] 133333617Sdteske S7 sum_1 = prod + sum_0; 134333617Sdteske 135333617Sdteske where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the 136333617Sdteske same size of 'TYPE1' or bigger. This is a special case of a reduction 137236628Sgnn computation. 138333617Sdteske 139333617Sdteske Input: 140333617Sdteske 141333617Sdteske * LAST_STMT: A stmt from which the pattern search begins. In the example, 142333617Sdteske when this function is called with S7, the pattern {S3,S4,S5,S6,S7} will be 143333617Sdteske detected. 144333617Sdteske 145333617Sdteske Output: 146333617Sdteske 147333617Sdteske * TYPE_IN: The type of the input arguments to the pattern. 148333617Sdteske 149333617Sdteske * TYPE_OUT: The type of the output of this pattern. 150333617Sdteske 151333617Sdteske * Return value: A new stmt that will be used to replace the sequence of 152333617Sdteske stmts that constitute the pattern. In this case it will be: 153333617Sdteske WIDEN_DOT_PRODUCT <x_t, y_t, sum_0> 154333617Sdteske*/ 155333617Sdteske 156333617Sdteskestatic tree 157333617Sdteskevect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) 158333617Sdteske{ 159333617Sdteske tree stmt, expr; 160333617Sdteske tree oprnd0, oprnd1; 161333617Sdteske tree oprnd00, oprnd01; 162333617Sdteske stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 163333617Sdteske tree type, half_type; 164333617Sdteske tree pattern_expr; 165333617Sdteske tree prod_type; 166333617Sdteske 167333617Sdteske if (TREE_CODE (last_stmt) != MODIFY_EXPR) 168333617Sdteske return NULL; 169333617Sdteske 170333617Sdteske expr = TREE_OPERAND (last_stmt, 1); 171333617Sdteske type = TREE_TYPE (expr); 172333617Sdteske 173333617Sdteske /* Look for the following pattern 174333617Sdteske DX = (TYPE1) X; 175333617Sdteske DY = (TYPE1) Y; 176333617Sdteske DPROD = DX * DY; 177333617Sdteske DDPROD = (TYPE2) DPROD; 178333617Sdteske sum_1 = DDPROD + sum_0; 179333617Sdteske In which 180333617Sdteske - DX is double the size of X 181333617Sdteske - DY is double the size of Y 182333617Sdteske - DX, DY, DPROD all have the same type 183333617Sdteske - sum is the same size of DPROD or bigger 184333617Sdteske - sum has been recognized as a reduction variable. 185333617Sdteske 186333617Sdteske This is equivalent to: 187333617Sdteske DPROD = X w* Y; #widen mult 188333617Sdteske sum_1 = DPROD w+ sum_0; #widen summation 189333617Sdteske or 190333617Sdteske DPROD = X w* Y; #widen mult 191333617Sdteske sum_1 = DPROD + sum_0; #summation 192333617Sdteske */ 193333617Sdteske 194333617Sdteske /* Starting from LAST_STMT, follow the defs of its uses in search 195333617Sdteske of the above pattern. */ 196333617Sdteske 197333617Sdteske if (TREE_CODE (expr) != PLUS_EXPR) 198333617Sdteske return NULL; 199333617Sdteske 200333617Sdteske if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 201333617Sdteske { 202333617Sdteske /* Has been detected as widening-summation? */ 203333617Sdteske 204333617Sdteske stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); 205333617Sdteske expr = TREE_OPERAND (stmt, 1); 206333617Sdteske type = TREE_TYPE (expr); 207333617Sdteske if (TREE_CODE (expr) != WIDEN_SUM_EXPR) 208333617Sdteske return NULL; 209333617Sdteske oprnd0 = TREE_OPERAND (expr, 0); 210333617Sdteske oprnd1 = TREE_OPERAND (expr, 1); 211333617Sdteske half_type = TREE_TYPE (oprnd0); 212333617Sdteske } 213333617Sdteske else 214333617Sdteske { 215333617Sdteske tree def_stmt; 216333617Sdteske 217333617Sdteske if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def) 218333617Sdteske return NULL; 219333617Sdteske oprnd0 = TREE_OPERAND (expr, 0); 220333617Sdteske oprnd1 = TREE_OPERAND (expr, 1); 221333617Sdteske if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type) 222333617Sdteske || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type)) 223333617Sdteske return NULL; 224333617Sdteske stmt = last_stmt; 225333617Sdteske 226333617Sdteske if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt)) 227333617Sdteske { 228333617Sdteske stmt = def_stmt; 229333617Sdteske expr = TREE_OPERAND (stmt, 1); 230333617Sdteske oprnd0 = TREE_OPERAND (expr, 0); 231333617Sdteske } 232333617Sdteske else 233333617Sdteske half_type = type; 234333617Sdteske } 235333617Sdteske 236333617Sdteske /* So far so good. Since last_stmt was detected as a (summation) reduction, 237333617Sdteske we know that oprnd1 is the reduction variable (defined by a loop-header 238333617Sdteske phi), and oprnd0 is an ssa-name defined by a stmt in the loop body. 239333617Sdteske Left to check that oprnd0 is defined by a (widen_)mult_expr */ 240333617Sdteske 241333617Sdteske prod_type = half_type; 242333617Sdteske stmt = SSA_NAME_DEF_STMT (oprnd0); 243333617Sdteske gcc_assert (stmt); 244333617Sdteske stmt_vinfo = vinfo_for_stmt (stmt); 245333617Sdteske gcc_assert (stmt_vinfo); 246333617Sdteske if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_loop_def) 247333617Sdteske return NULL; 248333617Sdteske expr = TREE_OPERAND (stmt, 1); 249333617Sdteske if (TREE_CODE (expr) != MULT_EXPR) 250333617Sdteske return NULL; 251333617Sdteske if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) 252333617Sdteske { 253333617Sdteske /* Has been detected as a widening multiplication? */ 254333617Sdteske 255333617Sdteske stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); 256333617Sdteske expr = TREE_OPERAND (stmt, 1); 257333617Sdteske if (TREE_CODE (expr) != WIDEN_MULT_EXPR) 258333617Sdteske return NULL; 259333617Sdteske stmt_vinfo = vinfo_for_stmt (stmt); 260333617Sdteske gcc_assert (stmt_vinfo); 261333617Sdteske gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def); 262 oprnd00 = TREE_OPERAND (expr, 0); 263 oprnd01 = TREE_OPERAND (expr, 1); 264 } 265 else 266 { 267 tree half_type0, half_type1; 268 tree def_stmt; 269 tree oprnd0, oprnd1; 270 271 oprnd0 = TREE_OPERAND (expr, 0); 272 oprnd1 = TREE_OPERAND (expr, 1); 273 if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) 274 != TYPE_MAIN_VARIANT (prod_type) 275 || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) 276 != TYPE_MAIN_VARIANT (prod_type)) 277 return NULL; 278 if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt)) 279 return NULL; 280 oprnd00 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); 281 if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt)) 282 return NULL; 283 oprnd01 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); 284 if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1)) 285 return NULL; 286 if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2) 287 return NULL; 288 } 289 290 half_type = TREE_TYPE (oprnd00); 291 *type_in = half_type; 292 *type_out = type; 293 294 /* Pattern detected. Create a stmt to be used to replace the pattern: */ 295 pattern_expr = build3 (DOT_PROD_EXPR, type, oprnd00, oprnd01, oprnd1); 296 if (vect_print_dump_info (REPORT_DETAILS)) 297 { 298 fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: "); 299 print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); 300 } 301 return pattern_expr; 302} 303 304 305/* Function vect_recog_widen_mult_pattern 306 307 Try to find the following pattern: 308 309 type a_t, b_t; 310 TYPE a_T, b_T, prod_T; 311 312 S1 a_t = ; 313 S2 b_t = ; 314 S3 a_T = (TYPE) a_t; 315 S4 b_T = (TYPE) b_t; 316 S5 prod_T = a_T * b_T; 317 318 where type 'TYPE' is at least double the size of type 'type'. 319 320 Input: 321 322 * LAST_STMT: A stmt from which the pattern search begins. In the example, 323 when this function is called with S5, the pattern {S3,S4,S5} is be detected. 324 325 Output: 326 327 * TYPE_IN: The type of the input arguments to the pattern. 328 329 * TYPE_OUT: The type of the output of this pattern. 330 331 * Return value: A new stmt that will be used to replace the sequence of 332 stmts that constitute the pattern. In this case it will be: 333 WIDEN_MULT <a_t, b_t> 334*/ 335 336static tree 337vect_recog_widen_mult_pattern (tree last_stmt ATTRIBUTE_UNUSED, 338 tree *type_in ATTRIBUTE_UNUSED, 339 tree *type_out ATTRIBUTE_UNUSED) 340{ 341 /* Yet to be implemented. */ 342 return NULL; 343} 344 345 346/* Function vect_recog_widen_sum_pattern 347 348 Try to find the following pattern: 349 350 type x_t; 351 TYPE x_T, sum = init; 352 loop: 353 sum_0 = phi <init, sum_1> 354 S1 x_t = *p; 355 S2 x_T = (TYPE) x_t; 356 S3 sum_1 = x_T + sum_0; 357 358 where type 'TYPE' is at least double the size of type 'type', i.e - we're 359 summing elements of type 'type' into an accumulator of type 'TYPE'. This is 360 a special case of a reduction computation. 361 362 Input: 363 364 * LAST_STMT: A stmt from which the pattern search begins. In the example, 365 when this function is called with S3, the pattern {S2,S3} will be detected. 366 367 Output: 368 369 * TYPE_IN: The type of the input arguments to the pattern. 370 371 * TYPE_OUT: The type of the output of this pattern. 372 373 * Return value: A new stmt that will be used to replace the sequence of 374 stmts that constitute the pattern. In this case it will be: 375 WIDEN_SUM <x_t, sum_0> 376*/ 377 378static tree 379vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out) 380{ 381 tree stmt, expr; 382 tree oprnd0, oprnd1; 383 stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); 384 tree type, half_type; 385 tree pattern_expr; 386 387 if (TREE_CODE (last_stmt) != MODIFY_EXPR) 388 return NULL; 389 390 expr = TREE_OPERAND (last_stmt, 1); 391 type = TREE_TYPE (expr); 392 393 /* Look for the following pattern 394 DX = (TYPE) X; 395 sum_1 = DX + sum_0; 396 In which DX is at least double the size of X, and sum_1 has been 397 recognized as a reduction variable. 398 */ 399 400 /* Starting from LAST_STMT, follow the defs of its uses in search 401 of the above pattern. */ 402 403 if (TREE_CODE (expr) != PLUS_EXPR) 404 return NULL; 405 406 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def) 407 return NULL; 408 409 oprnd0 = TREE_OPERAND (expr, 0); 410 oprnd1 = TREE_OPERAND (expr, 1); 411 if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type) 412 || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type)) 413 return NULL; 414 415 /* So far so good. Since last_stmt was detected as a (summation) reduction, 416 we know that oprnd1 is the reduction variable (defined by a loop-header 417 phi), and oprnd0 is an ssa-name defined by a stmt in the loop body. 418 Left to check that oprnd0 is defined by a cast from type 'type' to type 419 'TYPE'. */ 420 421 if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt)) 422 return NULL; 423 424 oprnd0 = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0); 425 *type_in = half_type; 426 *type_out = type; 427 428 /* Pattern detected. Create a stmt to be used to replace the pattern: */ 429 pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1); 430 if (vect_print_dump_info (REPORT_DETAILS)) 431 { 432 fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: "); 433 print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); 434 } 435 return pattern_expr; 436} 437 438 439/* Function vect_pattern_recog_1 440 441 Input: 442 PATTERN_RECOG_FUNC: A pointer to a function that detects a certain 443 computation pattern. 444 STMT: A stmt from which the pattern search should start. 445 446 If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an 447 expression that computes the same functionality and can be used to 448 replace the sequence of stmts that are involved in the pattern. 449 450 Output: 451 This function checks if the expression returned by PATTERN_RECOG_FUNC is 452 supported in vector form by the target. We use 'TYPE_IN' to obtain the 453 relevant vector type. If 'TYPE_IN' is already a vector type, then this 454 indicates that target support had already been checked by PATTERN_RECOG_FUNC. 455 If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits 456 to the available target pattern. 457 458 This function also does some bookkeeping, as explained in the documentation 459 for vect_recog_pattern. */ 460 461static void 462vect_pattern_recog_1 ( 463 tree (* vect_recog_func) (tree, tree *, tree *), 464 block_stmt_iterator si) 465{ 466 tree stmt = bsi_stmt (si); 467 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 468 stmt_vec_info pattern_stmt_info; 469 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info); 470 tree pattern_expr; 471 tree pattern_vectype; 472 tree type_in, type_out; 473 tree pattern_type; 474 enum tree_code code; 475 tree var, var_name; 476 stmt_ann_t ann; 477 478 pattern_expr = (* vect_recog_func) (stmt, &type_in, &type_out); 479 if (!pattern_expr) 480 return; 481 482 if (VECTOR_MODE_P (TYPE_MODE (type_in))) 483 { 484 /* No need to check target support (already checked by the pattern 485 recognition function). */ 486 pattern_vectype = type_in; 487 } 488 else 489 { 490 enum tree_code vec_mode; 491 enum insn_code icode; 492 optab optab; 493 494 /* Check target support */ 495 pattern_vectype = get_vectype_for_scalar_type (type_in); 496 optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype); 497 vec_mode = TYPE_MODE (pattern_vectype); 498 if (!optab 499 || (icode = optab->handlers[(int) vec_mode].insn_code) == 500 CODE_FOR_nothing 501 || (type_out 502 && (insn_data[icode].operand[0].mode != 503 TYPE_MODE (get_vectype_for_scalar_type (type_out))))) 504 return; 505 } 506 507 /* Found a vectorizable pattern. */ 508 if (vect_print_dump_info (REPORT_DETAILS)) 509 { 510 fprintf (vect_dump, "pattern recognized: "); 511 print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); 512 } 513 514 /* Mark the stmts that are involved in the pattern, 515 create a new stmt to express the pattern and insert it. */ 516 code = TREE_CODE (pattern_expr); 517 pattern_type = TREE_TYPE (pattern_expr); 518 var = create_tmp_var (pattern_type, "patt"); 519 add_referenced_var (var); 520 var_name = make_ssa_name (var, NULL_TREE); 521 pattern_expr = build2 (MODIFY_EXPR, void_type_node, var_name, pattern_expr); 522 SSA_NAME_DEF_STMT (var_name) = pattern_expr; 523 bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT); 524 ann = stmt_ann (pattern_expr); 525 set_stmt_info (ann, new_stmt_vec_info (pattern_expr, loop_vinfo)); 526 pattern_stmt_info = vinfo_for_stmt (pattern_expr); 527 528 STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt; 529 STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info); 530 STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype; 531 STMT_VINFO_IN_PATTERN_P (stmt_info) = true; 532 STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr; 533 534 return; 535} 536 537 538/* Function vect_pattern_recog 539 540 Input: 541 LOOP_VINFO - a struct_loop_info of a loop in which we want to look for 542 computation idioms. 543 544 Output - for each computation idiom that is detected we insert a new stmt 545 that provides the same functionality and that can be vectorized. We 546 also record some information in the struct_stmt_info of the relevant 547 stmts, as explained below: 548 549 At the entry to this function we have the following stmts, with the 550 following initial value in the STMT_VINFO fields: 551 552 stmt in_pattern_p related_stmt vec_stmt 553 S1: a_i = .... - - - 554 S2: a_2 = ..use(a_i).. - - - 555 S3: a_1 = ..use(a_2).. - - - 556 S4: a_0 = ..use(a_1).. - - - 557 S5: ... = ..use(a_0).. - - - 558 559 Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be 560 represented by a single stmt. We then: 561 - create a new stmt S6 that will replace the pattern. 562 - insert the new stmt S6 before the last stmt in the pattern 563 - fill in the STMT_VINFO fields as follows: 564 565 in_pattern_p related_stmt vec_stmt 566 S1: a_i = .... - - - 567 S2: a_2 = ..use(a_i).. - - - 568 S3: a_1 = ..use(a_2).. - - - 569 > S6: a_new = .... - S4 - 570 S4: a_0 = ..use(a_1).. true S6 - 571 S5: ... = ..use(a_0).. - - - 572 573 (the last stmt in the pattern (S4) and the new pattern stmt (S6) point 574 to each other through the RELATED_STMT field). 575 576 S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead 577 of S4 because it will replace all its uses. Stmts {S1,S2,S3} will 578 remain irrelevant unless used by stmts other than S4. 579 580 If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3} 581 (because they are marked as irrelevant). It will vectorize S6, and record 582 a pointer to the new vector stmt VS6 both from S6 (as usual), and also 583 from S4. We do that so that when we get to vectorizing stmts that use the 584 def of S4 (like S5 that uses a_0), we'll know where to take the relevant 585 vector-def from. S4 will be skipped, and S5 will be vectorized as usual: 586 587 in_pattern_p related_stmt vec_stmt 588 S1: a_i = .... - - - 589 S2: a_2 = ..use(a_i).. - - - 590 S3: a_1 = ..use(a_2).. - - - 591 > VS6: va_new = .... - - - 592 S6: a_new = .... - S4 VS6 593 S4: a_0 = ..use(a_1).. true S6 VS6 594 > VS5: ... = ..vuse(va_new).. - - - 595 S5: ... = ..use(a_0).. - - - 596 597 DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used 598 elsewhere), and we'll end up with: 599 600 VS6: va_new = .... 601 VS5: ... = ..vuse(va_new).. 602 603 If vectorization does not succeed, DCE will clean S6 away (its def is 604 not used), and we'll end up with the original sequence. 605*/ 606 607void 608vect_pattern_recog (loop_vec_info loop_vinfo) 609{ 610 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 611 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo); 612 unsigned int nbbs = loop->num_nodes; 613 block_stmt_iterator si; 614 tree stmt; 615 unsigned int i, j; 616 tree (* vect_recog_func_ptr) (tree, tree *, tree *); 617 618 if (vect_print_dump_info (REPORT_DETAILS)) 619 fprintf (vect_dump, "=== vect_pattern_recog ==="); 620 621 /* Scan through the loop stmts, applying the pattern recognition 622 functions starting at each stmt visited: */ 623 for (i = 0; i < nbbs; i++) 624 { 625 basic_block bb = bbs[i]; 626 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 627 { 628 stmt = bsi_stmt (si); 629 630 /* Scan over all generic vect_recog_xxx_pattern functions. */ 631 for (j = 0; j < NUM_PATTERNS; j++) 632 { 633 vect_recog_func_ptr = vect_vect_recog_func_ptrs[j]; 634 vect_pattern_recog_1 (vect_recog_func_ptr, si); 635 } 636 } 637 } 638} 639