gcc/tree-complex.c

   1 /* Lower complex number and vector operations to scalar operations.
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tree.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "expr.h"
  28 #include "insn-codes.h"
  29 #include "diagnostic.h"
  30 #include "optabs.h"
  31 #include "machmode.h"
  32 #include "langhooks.h"
  33 #include "tree-flow.h"
  34 #include "tree-gimple.h"
  35 #include "tree-iterator.h"
  36 #include "tree-pass.h"
  37 #include "flags.h"
  38 #include "ggc.h"
  39
  40
  41 /* Extract the real or imaginary part of a complex variable or constant.
  42    Make sure that it's a proper gimple_val and gimplify it if not.
  43    Emit any new code before BSI.  */
  44
  45 static tree
  46 extract_component (block_stmt_iterator *bsi, tree t, bool imagpart_p)
  47 {
  48   tree ret, inner_type;
  49
  50   inner_type = TREE_TYPE (TREE_TYPE (t));
  51   switch (TREE_CODE (t))
  52     {
  53     case COMPLEX_CST:
  54       ret = (imagpart_p ? TREE_IMAGPART (t) : TREE_REALPART (t));
  55       break;
  56
  57     case COMPLEX_EXPR:
  58       ret = TREE_OPERAND (t, imagpart_p);
  59       break;
  60
  61     case VAR_DECL:
  62     case PARM_DECL:
  63       ret = build1 ((imagpart_p ? IMAGPART_EXPR : REALPART_EXPR),
  64                     inner_type, t);
  65       break;
  66
  67     default:
  68       gcc_unreachable ();
  69     }
  70
  71   return gimplify_val (bsi, inner_type, ret);
  72 }
  73
  74 /* Update an assignment to a complex variable in place.  */
  75
  76 static void
  77 update_complex_assignment (block_stmt_iterator *bsi, tree r, tree i)
  78 {
  79   tree stmt = bsi_stmt (*bsi);
  80   tree type;
  81
  82   if (TREE_CODE (stmt) == RETURN_EXPR)
  83     stmt = TREE_OPERAND (stmt, 0);
  84
  85   type = TREE_TYPE (TREE_OPERAND (stmt, 1));
  86   TREE_OPERAND (stmt, 1) = build (COMPLEX_EXPR, type, r, i);
  87   mark_stmt_modified (stmt);
  88 }
  89
  90 /* Expand complex addition to scalars:
  91         a + b = (ar + br) + i(ai + bi)
  92         a - b = (ar - br) + i(ai + bi)
  93 */
  94
  95 static void
  96 expand_complex_addition (block_stmt_iterator *bsi, tree inner_type,
  97                          tree ar, tree ai, tree br, tree bi,
  98                          enum tree_code code)
  99 {
 100   tree rr, ri;
 101
 102   rr = gimplify_build2 (bsi, code, inner_type, ar, br);
 103   ri = gimplify_build2 (bsi, code, inner_type, ai, bi);
 104
 105   update_complex_assignment (bsi, rr, ri);
 106 }
 107
 108 /* Expand a complex multiplication or division to a libcall to the c99
 109    compliant routines.  */
 110
 111 static void
 112 expand_complex_libcall (block_stmt_iterator *bsi, tree ar, tree ai,
 113                         tree br, tree bi, enum tree_code code)
 114 {
 115   enum machine_mode mode;
 116   enum built_in_function bcode;
 117   tree args, fn, stmt, type;
 118
 119   args = tree_cons (NULL, bi, NULL);
 120   args = tree_cons (NULL, br, args);
 121   args = tree_cons (NULL, ai, args);
 122   args = tree_cons (NULL, ar, args);
 123
 124   stmt = bsi_stmt (*bsi);
 125   type = TREE_TYPE (TREE_OPERAND (stmt, 1));
 126
 127   mode = TYPE_MODE (type);
 128   gcc_assert (GET_MODE_CLASS (mode) == MODE_COMPLEX_FLOAT);
 129   if (code == MULT_EXPR)
 130     bcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
 131   else if (code == RDIV_EXPR)
 132     bcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
 133   else
 134     gcc_unreachable ();
 135   fn = built_in_decls[bcode];
 136
 137   TREE_OPERAND (stmt, 1)
 138     = build3 (CALL_EXPR, type, build_fold_addr_expr (fn), args, NULL);
 139   update_stmt (stmt);
 140 }
 141
 142 /* Expand complex multiplication to scalars:
 143         a * b = (ar*br - ai*bi) + i(ar*bi + br*ai)
 144 */
 145
 146 static void
 147 expand_complex_multiplication (block_stmt_iterator *bsi, tree inner_type,
 148                                tree ar, tree ai, tree br, tree bi)
 149 {
 150   tree t1, t2, t3, t4, rr, ri;
 151
 152   if (flag_complex_method == 2 && SCALAR_FLOAT_TYPE_P (inner_type))
 153     {
 154       expand_complex_libcall (bsi, ar, ai, br, bi, MULT_EXPR);
 155       return;
 156     }
 157
 158   t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ar, br);
 159   t2 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ai, bi);
 160   t3 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ar, bi);
 161
 162   /* Avoid expanding redundant multiplication for the common
 163      case of squaring a complex number.  */
 164   if (ar == br && ai == bi)
 165     t4 = t3;
 166   else
 167     t4 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ai, br);
 168
 169   rr = gimplify_build2 (bsi, MINUS_EXPR, inner_type, t1, t2);
 170   ri = gimplify_build2 (bsi, PLUS_EXPR, inner_type, t3, t4);
 171
 172   update_complex_assignment (bsi, rr, ri);
 173 }
 174
 175 /* Expand complex division to scalars, straightforward algorithm.
 176         a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
 177             t = br*br + bi*bi
 178 */
 179
 180 static void
 181 expand_complex_div_straight (block_stmt_iterator *bsi, tree inner_type,
 182                              tree ar, tree ai, tree br, tree bi,
 183                              enum tree_code code)
 184 {
 185   tree rr, ri, div, t1, t2, t3;
 186
 187   t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, br, br);
 188   t2 = gimplify_build2 (bsi, MULT_EXPR, inner_type, bi, bi);
 189   div = gimplify_build2 (bsi, PLUS_EXPR, inner_type, t1, t2);
 190
 191   t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ar, br);
 192   t2 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ai, bi);
 193   t3 = gimplify_build2 (bsi, PLUS_EXPR, inner_type, t1, t2);
 194   rr = gimplify_build2 (bsi, code, inner_type, t3, div);
 195
 196   t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ai, br);
 197   t2 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ar, bi);
 198   t3 = gimplify_build2 (bsi, MINUS_EXPR, inner_type, t1, t2);
 199   ri = gimplify_build2 (bsi, code, inner_type, t3, div);
 200
 201   update_complex_assignment (bsi, rr, ri);
 202 }
 203
 204 /* Expand complex division to scalars, modified algorithm to minimize
 205    overflow with wide input ranges.  */
 206
 207 static void
 208 expand_complex_div_wide (block_stmt_iterator *bsi, tree inner_type,
 209                          tree ar, tree ai, tree br, tree bi,
 210                          enum tree_code code)
 211 {
 212   tree rr, ri, ratio, div, t1, t2, tr, ti, cond;
 213   basic_block bb_cond, bb_true, bb_false, bb_join;
 214
 215   /* Examine |br| < |bi|, and branch.  */
 216   t1 = gimplify_build1 (bsi, ABS_EXPR, inner_type, br);
 217   t2 = gimplify_build1 (bsi, ABS_EXPR, inner_type, bi);
 218   cond = fold (build (LT_EXPR, boolean_type_node, t1, t2));
 219   STRIP_NOPS (cond);
 220
 221   bb_cond = bb_true = bb_false = bb_join = NULL;
 222   rr = ri = tr = ti = NULL;
 223   if (!TREE_CONSTANT (cond))
 224     {
 225       edge e;
 226
 227       cond = build (COND_EXPR, void_type_node, cond, NULL, NULL);
 228       bsi_insert_before (bsi, cond, BSI_SAME_STMT);
 229
 230       /* Split the original block, and create the TRUE and FALSE blocks.  */
 231       e = split_block (bsi->bb, cond);
 232       bb_cond = e->src;
 233       bb_join = e->dest;
 234       bb_true = create_empty_bb (bb_cond);
 235       bb_false = create_empty_bb (bb_true);
 236
 237       t1 = build (GOTO_EXPR, void_type_node, tree_block_label (bb_true));
 238       t2 = build (GOTO_EXPR, void_type_node, tree_block_label (bb_false));
 239       COND_EXPR_THEN (cond) = t1;
 240       COND_EXPR_ELSE (cond) = t2;
 241
 242       /* Wire the blocks together.  */
 243       e->flags = EDGE_TRUE_VALUE;
 244       redirect_edge_succ (e, bb_true);
 245       make_edge (bb_cond, bb_false, EDGE_FALSE_VALUE);
 246       make_edge (bb_true, bb_join, EDGE_FALLTHRU);
 247       make_edge (bb_false, bb_join, EDGE_FALLTHRU);
 248
 249       /* Update dominance info.  Note that bb_join's data was
 250          updated by split_block.  */
 251       if (dom_info_available_p (CDI_DOMINATORS))
 252         {
 253           set_immediate_dominator (CDI_DOMINATORS, bb_true, bb_cond);
 254           set_immediate_dominator (CDI_DOMINATORS, bb_false, bb_cond);
 255         }
 256
 257       rr = make_rename_temp (inner_type, NULL);
 258       ri = make_rename_temp (inner_type, NULL);
 259     }
 260
 261   /* In the TRUE branch, we compute
 262       ratio = br/bi;
 263       div = (br * ratio) + bi;
 264       tr = (ar * ratio) + ai;
 265       ti = (ai * ratio) - ar;
 266       tr = tr / div;
 267       ti = ti / div;  */
 268   if (bb_true || integer_nonzerop (cond))
 269     {
 270       if (bb_true)
 271         {
 272           *bsi = bsi_last (bb_true);
 273           bsi_insert_after (bsi, build_empty_stmt (), BSI_NEW_STMT);
 274         }
 275
 276       ratio = gimplify_build2 (bsi, code, inner_type, br, bi);
 277
 278       t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, br, ratio);
 279       div = gimplify_build2 (bsi, PLUS_EXPR, inner_type, t1, bi);
 280
 281       t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ar, ratio);
 282       tr = gimplify_build2 (bsi, PLUS_EXPR, inner_type, t1, ai);
 283
 284       t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ai, ratio);
 285       ti = gimplify_build2 (bsi, MINUS_EXPR, inner_type, t1, ar);
 286
 287       tr = gimplify_build2 (bsi, code, inner_type, tr, div);
 288       ti = gimplify_build2 (bsi, code, inner_type, ti, div);
 289
 290      if (bb_true)
 291        {
 292          t1 = build (MODIFY_EXPR, inner_type, rr, tr);
 293          bsi_insert_before (bsi, t1, BSI_SAME_STMT);
 294          t1 = build (MODIFY_EXPR, inner_type, ri, ti);
 295          bsi_insert_before (bsi, t1, BSI_SAME_STMT);
 296          bsi_remove (bsi);
 297        }
 298     }
 299
 300   /* In the FALSE branch, we compute
 301       ratio = d/c;
 302       divisor = (d * ratio) + c;
 303       tr = (b * ratio) + a;
 304       ti = b - (a * ratio);
 305       tr = tr / div;
 306       ti = ti / div;  */
 307   if (bb_false || integer_zerop (cond))
 308     {
 309       if (bb_false)
 310         {
 311           *bsi = bsi_last (bb_false);
 312           bsi_insert_after (bsi, build_empty_stmt (), BSI_NEW_STMT);
 313         }
 314
 315       ratio = gimplify_build2 (bsi, code, inner_type, bi, br);
 316
 317       t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, bi, ratio);
 318       div = gimplify_build2 (bsi, PLUS_EXPR, inner_type, t1, br);
 319
 320       t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ai, ratio);
 321       tr = gimplify_build2 (bsi, PLUS_EXPR, inner_type, t1, ar);
 322
 323       t1 = gimplify_build2 (bsi, MULT_EXPR, inner_type, ar, ratio);
 324       ti = gimplify_build2 (bsi, MINUS_EXPR, inner_type, ai, t1);
 325
 326       tr = gimplify_build2 (bsi, code, inner_type, tr, div);
 327       ti = gimplify_build2 (bsi, code, inner_type, ti, div);
 328
 329      if (bb_false)
 330        {
 331          t1 = build (MODIFY_EXPR, inner_type, rr, tr);
 332          bsi_insert_before (bsi, t1, BSI_SAME_STMT);
 333          t1 = build (MODIFY_EXPR, inner_type, ri, ti);
 334          bsi_insert_before (bsi, t1, BSI_SAME_STMT);
 335          bsi_remove (bsi);
 336        }
 337     }
 338
 339   if (bb_join)
 340     *bsi = bsi_start (bb_join);
 341   else
 342     rr = tr, ri = ti;
 343
 344   update_complex_assignment (bsi, rr, ri);
 345 }
 346
 347 /* Expand complex division to scalars.  */
 348
 349 static void
 350 expand_complex_division (block_stmt_iterator *bsi, tree inner_type,
 351                          tree ar, tree ai, tree br, tree bi,
 352                          enum tree_code code)
 353 {
 354   switch (flag_complex_method)
 355     {
 356     case 0:
 357       /* straightforward implementation of complex divide acceptable.  */
 358       expand_complex_div_straight (bsi, inner_type, ar, ai, br, bi, code);
 359       break;
 360
 361     case 2:
 362       if (SCALAR_FLOAT_TYPE_P (inner_type))
 363         {
 364           expand_complex_libcall (bsi, ar, ai, br, bi, code);
 365           return;
 366         }
 367       /* FALLTHRU */
 368
 369     case 1:
 370       /* wide ranges of inputs must work for complex divide.  */
 371       expand_complex_div_wide (bsi, inner_type, ar, ai, br, bi, code);
 372       break;
 373
 374     default:
 375       gcc_unreachable ();
 376     }
 377 }
 378
 379 /* Expand complex negation to scalars:
 380         -a = (-ar) + i(-ai)
 381 */
 382
 383 static void
 384 expand_complex_negation (block_stmt_iterator *bsi, tree inner_type,
 385                          tree ar, tree ai)
 386 {
 387   tree rr, ri;
 388
 389   rr = gimplify_build1 (bsi, NEGATE_EXPR, inner_type, ar);
 390   ri = gimplify_build1 (bsi, NEGATE_EXPR, inner_type, ai);
 391
 392   update_complex_assignment (bsi, rr, ri);
 393 }
 394
 395 /* Expand complex conjugate to scalars:
 396         ~a = (ar) + i(-ai)
 397 */
 398
 399 static void
 400 expand_complex_conjugate (block_stmt_iterator *bsi, tree inner_type,
 401                           tree ar, tree ai)
 402 {
 403   tree ri;
 404
 405   ri = gimplify_build1 (bsi, NEGATE_EXPR, inner_type, ai);
 406
 407   update_complex_assignment (bsi, ar, ri);
 408 }
 409
 410 /* Expand complex comparison (EQ or NE only).  */
 411
 412 static void
 413 expand_complex_comparison (block_stmt_iterator *bsi, tree ar, tree ai,
 414                            tree br, tree bi, enum tree_code code)
 415 {
 416   tree cr, ci, cc, stmt, expr, type;
 417
 418   cr = gimplify_build2 (bsi, code, boolean_type_node, ar, br);
 419   ci = gimplify_build2 (bsi, code, boolean_type_node, ai, bi);
 420   cc = gimplify_build2 (bsi,
 421                         (code == EQ_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR),
 422                         boolean_type_node, cr, ci);
 423
 424   stmt = expr = bsi_stmt (*bsi);
 425
 426   switch (TREE_CODE (stmt))
 427     {
 428     case RETURN_EXPR:
 429       expr = TREE_OPERAND (stmt, 0);
 430       /* FALLTHRU */
 431     case MODIFY_EXPR:
 432       type = TREE_TYPE (TREE_OPERAND (expr, 1));
 433       TREE_OPERAND (expr, 1) = fold_convert (type, cc);
 434       break;
 435     case COND_EXPR:
 436       TREE_OPERAND (stmt, 0) = cc;
 437       break;
 438     default:
 439       gcc_unreachable ();
 440     }
 441
 442   mark_stmt_modified (stmt);
 443 }
 444
 445 /* Process one statement.  If we identify a complex operation, expand it.  */
 446
 447 static void
 448 expand_complex_operations_1 (block_stmt_iterator *bsi)
 449 {
 450   tree stmt = bsi_stmt (*bsi);
 451   tree rhs, type, inner_type;
 452   tree ac, ar, ai, bc, br, bi;
 453   enum tree_code code;
 454
 455   switch (TREE_CODE (stmt))
 456     {
 457     case RETURN_EXPR:
 458       stmt = TREE_OPERAND (stmt, 0);
 459       if (!stmt)
 460         return;
 461       if (TREE_CODE (stmt) != MODIFY_EXPR)
 462         return;
 463       /* FALLTHRU */
 464
 465     case MODIFY_EXPR:
 466       rhs = TREE_OPERAND (stmt, 1);
 467       break;
 468
 469     case COND_EXPR:
 470       rhs = TREE_OPERAND (stmt, 0);
 471       break;
 472
 473     default:
 474       return;
 475     }
 476
 477   type = TREE_TYPE (rhs);
 478   code = TREE_CODE (rhs);
 479
 480   /* Initial filter for operations we handle.  */
 481   switch (code)
 482     {
 483     case PLUS_EXPR:
 484     case MINUS_EXPR:
 485     case MULT_EXPR:
 486     case TRUNC_DIV_EXPR:
 487     case CEIL_DIV_EXPR:
 488     case FLOOR_DIV_EXPR:
 489     case ROUND_DIV_EXPR:
 490     case RDIV_EXPR:
 491     case NEGATE_EXPR:
 492     case CONJ_EXPR:
 493       if (TREE_CODE (type) != COMPLEX_TYPE)
 494         return;
 495       inner_type = TREE_TYPE (type);
 496       break;
 497
 498     case EQ_EXPR:
 499     case NE_EXPR:
 500       inner_type = TREE_TYPE (TREE_OPERAND (rhs, 1));
 501       if (TREE_CODE (inner_type) != COMPLEX_TYPE)
 502         return;
 503       break;
 504
 505     default:
 506       return;
 507     }
 508
 509   /* Extract the components of the two complex values.  Make sure and
 510      handle the common case of the same value used twice specially.  */
 511   ac = TREE_OPERAND (rhs, 0);
 512   ar = extract_component (bsi, ac, 0);
 513   ai = extract_component (bsi, ac, 1);
 514
 515   if (TREE_CODE_CLASS (code) == tcc_unary)
 516     bc = br = bi = NULL;
 517   else
 518     {
 519       bc = TREE_OPERAND (rhs, 1);
 520       if (ac == bc)
 521         br = ar, bi = ai;
 522       else
 523         {
 524           br = extract_component (bsi, bc, 0);
 525           bi = extract_component (bsi, bc, 1);
 526         }
 527     }
 528
 529   switch (code)
 530     {
 531     case PLUS_EXPR:
 532     case MINUS_EXPR:
 533       expand_complex_addition (bsi, inner_type, ar, ai, br, bi, code);
 534       break;
 535
 536     case MULT_EXPR:
 537       expand_complex_multiplication (bsi, inner_type, ar, ai, br, bi);
 538       break;
 539
 540     case TRUNC_DIV_EXPR:
 541     case CEIL_DIV_EXPR:
 542     case FLOOR_DIV_EXPR:
 543     case ROUND_DIV_EXPR:
 544     case RDIV_EXPR:
 545       expand_complex_division (bsi, inner_type, ar, ai, br, bi, code);
 546       break;
 547
 548     case NEGATE_EXPR:
 549       expand_complex_negation (bsi, inner_type, ar, ai);
 550       break;
 551
 552     case CONJ_EXPR:
 553       expand_complex_conjugate (bsi, inner_type, ar, ai);
 554       break;
 555
 556     case EQ_EXPR:
 557     case NE_EXPR:
 558       expand_complex_comparison (bsi, ar, ai, br, bi, code);
 559       break;
 560
 561     default:
 562       gcc_unreachable ();
 563     }
 564   update_stmt_if_modified (stmt);
 565 }
 566 \f
 567 /* Build a constant of type TYPE, made of VALUE's bits replicated
 568    every TYPE_SIZE (INNER_TYPE) bits to fit TYPE's precision.  */
 569 static tree
 570 build_replicated_const (tree type, tree inner_type, HOST_WIDE_INT value)
 571 {
 572   int width = tree_low_cst (TYPE_SIZE (inner_type), 1);
 573   int n = HOST_BITS_PER_WIDE_INT / width;
 574   unsigned HOST_WIDE_INT low, high, mask;
 575   tree ret;
 576
 577   gcc_assert (n);
 578
 579   if (width == HOST_BITS_PER_WIDE_INT)
 580     low = value;
 581   else
 582     {
 583       mask = ((HOST_WIDE_INT)1 << width) - 1;
 584       low = (unsigned HOST_WIDE_INT) ~0 / mask * (value & mask);
 585     }
 586
 587   if (TYPE_PRECISION (type) < HOST_BITS_PER_WIDE_INT)
 588     low &= ((HOST_WIDE_INT)1 << TYPE_PRECISION (type)) - 1, high = 0;
 589   else if (TYPE_PRECISION (type) == HOST_BITS_PER_WIDE_INT)
 590     high = 0;
 591   else if (TYPE_PRECISION (type) == 2 * HOST_BITS_PER_WIDE_INT)
 592     high = low;
 593   else
 594     gcc_unreachable ();
 595
 596   ret = build_int_cst_wide (type, low, high);
 597   return ret;
 598 }
 599
 600 static GTY(()) tree vector_inner_type;
 601 static GTY(()) tree vector_last_type;
 602 static GTY(()) int vector_last_nunits;
 603
 604 /* Return a suitable vector types made of SUBPARTS units each of mode
 605    "word_mode" (the global variable).  */
 606 static tree
 607 build_word_mode_vector_type (int nunits)
 608 {
 609   if (!vector_inner_type)
 610     vector_inner_type = lang_hooks.types.type_for_mode (word_mode, 1);
 611   else if (vector_last_nunits == nunits)
 612     {
 613       gcc_assert (TREE_CODE (vector_last_type) == VECTOR_TYPE);
 614       return vector_last_type;
 615     }
 616
 617   /* We build a new type, but we canonicalize it nevertheless,
 618      because it still saves some memory.  */
 619   vector_last_nunits = nunits;
 620   vector_last_type = type_hash_canon (nunits,
 621                                       build_vector_type (vector_inner_type,
 622                                                          nunits));
 623   return vector_last_type;
 624 }
 625
 626 typedef tree (*elem_op_func) (block_stmt_iterator *,
 627                               tree, tree, tree, tree, tree, enum tree_code);
 628
 629 static inline tree
 630 tree_vec_extract (block_stmt_iterator *bsi, tree type,
 631                   tree t, tree bitsize, tree bitpos)
 632 {
 633   if (bitpos)
 634     return gimplify_build3 (bsi, BIT_FIELD_REF, type, t, bitsize, bitpos);
 635   else
 636     return gimplify_build1 (bsi, VIEW_CONVERT_EXPR, type, t);
 637 }
 638
 639 static tree
 640 do_unop (block_stmt_iterator *bsi, tree inner_type, tree a,
 641          tree b ATTRIBUTE_UNUSED, tree bitpos, tree bitsize,
 642          enum tree_code code)
 643 {
 644   a = tree_vec_extract (bsi, inner_type, a, bitsize, bitpos);
 645   return gimplify_build1 (bsi, code, inner_type, a);
 646 }
 647
 648 static tree
 649 do_binop (block_stmt_iterator *bsi, tree inner_type, tree a, tree b,
 650           tree bitpos, tree bitsize, enum tree_code code)
 651 {
 652   a = tree_vec_extract (bsi, inner_type, a, bitsize, bitpos);
 653   b = tree_vec_extract (bsi, inner_type, b, bitsize, bitpos);
 654   return gimplify_build2 (bsi, code, inner_type, a, b);
 655 }
 656
 657 /* Expand vector addition to scalars.  This does bit twiddling
 658    in order to increase parallelism:
 659
 660    a + b = (((int) a & 0x7f7f7f7f) + ((int) b & 0x7f7f7f7f)) ^
 661            (a ^ b) & 0x80808080
 662
 663    a - b =  (((int) a | 0x80808080) - ((int) b & 0x7f7f7f7f)) ^
 664             (a ^ ~b) & 0x80808080
 665
 666    -b = (0x80808080 - ((int) b & 0x7f7f7f7f)) ^ (~b & 0x80808080)
 667
 668    This optimization should be done only if 4 vector items or more
 669    fit into a word.  */
 670 static tree
 671 do_plus_minus (block_stmt_iterator *bsi, tree word_type, tree a, tree b,
 672                tree bitpos ATTRIBUTE_UNUSED, tree bitsize ATTRIBUTE_UNUSED,
 673                enum tree_code code)
 674 {
 675   tree inner_type = TREE_TYPE (TREE_TYPE (a));
 676   unsigned HOST_WIDE_INT max;
 677   tree low_bits, high_bits, a_low, b_low, result_low, signs;
 678
 679   max = GET_MODE_MASK (TYPE_MODE (inner_type));
 680   low_bits = build_replicated_const (word_type, inner_type, max >> 1);
 681   high_bits = build_replicated_const (word_type, inner_type, max & ~(max >> 1));
 682
 683   a = tree_vec_extract (bsi, word_type, a, bitsize, bitpos);
 684   b = tree_vec_extract (bsi, word_type, b, bitsize, bitpos);
 685
 686   signs = gimplify_build2 (bsi, BIT_XOR_EXPR, word_type, a, b);
 687   b_low = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, b, low_bits);
 688   if (code == PLUS_EXPR)
 689     a_low = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, a, low_bits);
 690   else
 691     {
 692       a_low = gimplify_build2 (bsi, BIT_IOR_EXPR, word_type, a, high_bits);
 693       signs = gimplify_build1 (bsi, BIT_NOT_EXPR, word_type, signs);
 694     }
 695
 696   signs = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, signs, high_bits);
 697   result_low = gimplify_build2 (bsi, code, word_type, a_low, b_low);
 698   return gimplify_build2 (bsi, BIT_XOR_EXPR, word_type, result_low, signs);
 699 }
 700
 701 static tree
 702 do_negate (block_stmt_iterator *bsi, tree word_type, tree b,
 703            tree unused ATTRIBUTE_UNUSED, tree bitpos ATTRIBUTE_UNUSED,
 704            tree bitsize ATTRIBUTE_UNUSED,
 705            enum tree_code code ATTRIBUTE_UNUSED)
 706 {
 707   tree inner_type = TREE_TYPE (TREE_TYPE (b));
 708   HOST_WIDE_INT max;
 709   tree low_bits, high_bits, b_low, result_low, signs;
 710
 711   max = GET_MODE_MASK (TYPE_MODE (inner_type));
 712   low_bits = build_replicated_const (word_type, inner_type, max >> 1);
 713   high_bits = build_replicated_const (word_type, inner_type, max & ~(max >> 1));
 714
 715   b = tree_vec_extract (bsi, word_type, b, bitsize, bitpos);
 716
 717   b_low = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, b, low_bits);
 718   signs = gimplify_build1 (bsi, BIT_NOT_EXPR, word_type, b);
 719   signs = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, signs, high_bits);
 720   result_low = gimplify_build2 (bsi, MINUS_EXPR, word_type, high_bits, b_low);
 721   return gimplify_build2 (bsi, BIT_XOR_EXPR, word_type, result_low, signs);
 722 }
 723
 724 /* Expand a vector operation to scalars, by using many operations
 725    whose type is the vector type's inner type.  */
 726 static tree
 727 expand_vector_piecewise (block_stmt_iterator *bsi, elem_op_func f,
 728                          tree type, tree inner_type,
 729                          tree a, tree b, enum tree_code code)
 730 {
 731   tree head, *chain = &head;
 732   tree part_width = TYPE_SIZE (inner_type);
 733   tree index = bitsize_int (0);
 734   int nunits = TYPE_VECTOR_SUBPARTS (type);
 735   int delta = tree_low_cst (part_width, 1)
 736               / tree_low_cst (TYPE_SIZE (TREE_TYPE (type)), 1);
 737   int i;
 738
 739   for (i = 0; i < nunits;
 740        i += delta, index = int_const_binop (PLUS_EXPR, index, part_width, 0))
 741     {
 742       tree result = f (bsi, inner_type, a, b, index, part_width, code);
 743       *chain = tree_cons (NULL_TREE, result, NULL_TREE);
 744       chain = &TREE_CHAIN (*chain);
 745     }
 746
 747   return build1 (CONSTRUCTOR, type, head);
 748 }
 749
 750 /* Expand a vector operation to scalars with the freedom to use
 751    a scalar integer type, or to use a different size for the items
 752    in the vector type.  */
 753 static tree
 754 expand_vector_parallel (block_stmt_iterator *bsi, elem_op_func f, tree type,
 755                         tree a, tree b,
 756                         enum tree_code code)
 757 {
 758   tree result, compute_type;
 759   enum machine_mode mode;
 760   int n_words = tree_low_cst (TYPE_SIZE_UNIT (type), 1) / UNITS_PER_WORD;
 761
 762   /* We have three strategies.  If the type is already correct, just do
 763      the operation an element at a time.  Else, if the vector is wider than
 764      one word, do it a word at a time; finally, if the vector is smaller
 765      than one word, do it as a scalar.  */
 766   if (TYPE_MODE (TREE_TYPE (type)) == word_mode)
 767      return expand_vector_piecewise (bsi, f,
 768                                      type, TREE_TYPE (type),
 769                                      a, b, code);
 770   else if (n_words > 1)
 771     {
 772       tree word_type = build_word_mode_vector_type (n_words);
 773       result = expand_vector_piecewise (bsi, f,
 774                                         word_type, TREE_TYPE (word_type),
 775                                         a, b, code);
 776       result = gimplify_val (bsi, word_type, result);
 777     }
 778   else
 779     {
 780       /* Use a single scalar operation with a mode no wider than word_mode.  */
 781       mode = mode_for_size (tree_low_cst (TYPE_SIZE (type), 1), MODE_INT, 0);
 782       compute_type = lang_hooks.types.type_for_mode (mode, 1);
 783       result = f (bsi, compute_type, a, b, NULL_TREE, NULL_TREE, code);
 784     }
 785
 786   return build1 (VIEW_CONVERT_EXPR, type, result);
 787 }
 788
 789 /* Expand a vector operation to scalars; for integer types we can use
 790    special bit twiddling tricks to do the sums a word at a time, using
 791    function F_PARALLEL instead of F.  These tricks are done only if
 792    they can process at least four items, that is, only if the vector
 793    holds at least four items and if a word can hold four items.  */
 794 static tree
 795 expand_vector_addition (block_stmt_iterator *bsi,
 796                         elem_op_func f, elem_op_func f_parallel,
 797                         tree type, tree a, tree b, enum tree_code code)
 798 {
 799   int parts_per_word = UNITS_PER_WORD
 800                        / tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (type)), 1);
 801
 802   if (INTEGRAL_TYPE_P (TREE_TYPE (type))
 803       && parts_per_word >= 4
 804       && TYPE_VECTOR_SUBPARTS (type) >= 4)
 805     return expand_vector_parallel (bsi, f_parallel,
 806                                    type, a, b, code);
 807   else
 808     return expand_vector_piecewise (bsi, f,
 809                                     type, TREE_TYPE (type),
 810                                     a, b, code);
 811 }
 812
 813 /* Return a type for the widest vector mode whose components are of mode
 814    INNER_MODE, or NULL_TREE if none is found.  */
 815 static tree
 816 type_for_widest_vector_mode (enum machine_mode inner_mode, optab op)
 817 {
 818   enum machine_mode best_mode = VOIDmode, mode;
 819   int best_nunits = 0;
 820
 821   if (GET_MODE_CLASS (inner_mode) == MODE_FLOAT)
 822     mode = MIN_MODE_VECTOR_FLOAT;
 823   else
 824     mode = MIN_MODE_VECTOR_INT;
 825
 826   for (; mode != VOIDmode; mode = GET_MODE_WIDER_MODE (mode))
 827     if (GET_MODE_INNER (mode) == inner_mode
 828         && GET_MODE_NUNITS (mode) > best_nunits
 829         && op->handlers[mode].insn_code != CODE_FOR_nothing)
 830       best_mode = mode, best_nunits = GET_MODE_NUNITS (mode);
 831
 832   if (best_mode == VOIDmode)
 833     return NULL_TREE;
 834   else
 835     return lang_hooks.types.type_for_mode (best_mode, 1);
 836 }
 837
 838 /* Process one statement.  If we identify a vector operation, expand it.  */
 839
 840 static void
 841 expand_vector_operations_1 (block_stmt_iterator *bsi)
 842 {
 843   tree stmt = bsi_stmt (*bsi);
 844   tree *p_rhs, rhs, type, compute_type;
 845   enum tree_code code;
 846   enum machine_mode compute_mode;
 847   optab op;
 848
 849   switch (TREE_CODE (stmt))
 850     {
 851     case RETURN_EXPR:
 852       stmt = TREE_OPERAND (stmt, 0);
 853       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
 854         return;
 855
 856       /* FALLTHRU */
 857
 858     case MODIFY_EXPR:
 859       p_rhs = &TREE_OPERAND (stmt, 1);
 860       rhs = *p_rhs;
 861       break;
 862
 863     default:
 864       return;
 865     }
 866
 867   type = TREE_TYPE (rhs);
 868   if (TREE_CODE (type) != VECTOR_TYPE)
 869     return;
 870
 871   code = TREE_CODE (rhs);
 872   if (TREE_CODE_CLASS (code) != tcc_unary
 873       && TREE_CODE_CLASS (code) != tcc_binary)
 874     return;
 875
 876   if (code == NOP_EXPR || code == VIEW_CONVERT_EXPR)
 877     return;
 878
 879   gcc_assert (code != CONVERT_EXPR);
 880   op = optab_for_tree_code (code, type);
 881
 882   /* Optabs will try converting a negation into a subtraction, so
 883      look for it as well.  TODO: negation of floating-point vectors
 884      might be turned into an exclusive OR toggling the sign bit.  */
 885   if (op == NULL
 886       && code == NEGATE_EXPR
 887       && INTEGRAL_TYPE_P (TREE_TYPE (type)))
 888     op = optab_for_tree_code (MINUS_EXPR, type);
 889
 890   /* For very wide vectors, try using a smaller vector mode.  */
 891   compute_type = type;
 892   if (TYPE_MODE (type) == BLKmode && op)
 893     {
 894       tree vector_compute_type
 895         = type_for_widest_vector_mode (TYPE_MODE (TREE_TYPE (type)), op);
 896       if (vector_compute_type != NULL_TREE)
 897         compute_type = vector_compute_type;
 898     }
 899
 900   compute_mode = TYPE_MODE (compute_type);
 901
 902   /* If we are breaking a BLKmode vector into smaller pieces,
 903      type_for_widest_vector_mode has already looked into the optab,
 904      so skip these checks.  */
 905   if (compute_type == type)
 906     {
 907       if ((GET_MODE_CLASS (compute_mode) == MODE_VECTOR_INT
 908            || GET_MODE_CLASS (compute_mode) == MODE_VECTOR_FLOAT)
 909           && op != NULL
 910           && op->handlers[compute_mode].insn_code != CODE_FOR_nothing)
 911         return;
 912       else
 913         {
 914           /* There is no operation in hardware, so fall back to scalars.  */
 915           compute_type = TREE_TYPE (type);
 916           compute_mode = TYPE_MODE (compute_type);
 917         }
 918     }
 919
 920   /* If the compute mode is not a vector mode (hence we are decomposing
 921      a BLKmode vector to smaller, hardware-supported vectors), we may
 922      want to expand the operations in parallel.  */
 923   if (GET_MODE_CLASS (compute_mode) != MODE_VECTOR_INT
 924       && GET_MODE_CLASS (compute_mode) != MODE_VECTOR_FLOAT)
 925     switch (code)
 926       {
 927       case PLUS_EXPR:
 928       case MINUS_EXPR:
 929         if (TYPE_TRAP_SIGNED (type))
 930           break;
 931
 932         *p_rhs = expand_vector_addition (bsi, do_binop, do_plus_minus, type,
 933                                          TREE_OPERAND (rhs, 0),
 934                                          TREE_OPERAND (rhs, 1), code);
 935         mark_stmt_modified (bsi_stmt (*bsi));
 936         return;
 937
 938       case NEGATE_EXPR:
 939         if (TYPE_TRAP_SIGNED (type))
 940           break;
 941
 942         *p_rhs = expand_vector_addition (bsi, do_unop, do_negate, type,
 943                                          TREE_OPERAND (rhs, 0),
 944                                          NULL_TREE, code);
 945         mark_stmt_modified (bsi_stmt (*bsi));
 946         return;
 947
 948       case BIT_AND_EXPR:
 949       case BIT_IOR_EXPR:
 950       case BIT_XOR_EXPR:
 951         *p_rhs = expand_vector_parallel (bsi, do_binop, type,
 952                                          TREE_OPERAND (rhs, 0),
 953                                          TREE_OPERAND (rhs, 1), code);
 954         mark_stmt_modified (bsi_stmt (*bsi));
 955         return;
 956
 957       case BIT_NOT_EXPR:
 958         *p_rhs = expand_vector_parallel (bsi, do_unop, type,
 959                                          TREE_OPERAND (rhs, 0),
 960                                          NULL_TREE, code);
 961         mark_stmt_modified (bsi_stmt (*bsi));
 962         return;
 963
 964       default:
 965         break;
 966       }
 967
 968   if (TREE_CODE_CLASS (code) == tcc_unary)
 969     *p_rhs = expand_vector_piecewise (bsi, do_unop, type, compute_type,
 970                                       TREE_OPERAND (rhs, 0),
 971                                       NULL_TREE, code);
 972   else
 973     *p_rhs = expand_vector_piecewise (bsi, do_binop, type, compute_type,
 974                                       TREE_OPERAND (rhs, 0),
 975                                       TREE_OPERAND (rhs, 1), code);
 976
 977   mark_stmt_modified (bsi_stmt (*bsi));
 978 }
 979 \f
 980 static void
 981 expand_vector_operations (void)
 982 {
 983   block_stmt_iterator bsi;
 984   basic_block bb;
 985
 986   FOR_EACH_BB (bb)
 987     {
 988       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 989         expand_vector_operations_1 (&bsi);
 990     }
 991 }
 992
 993 static void
 994 tree_lower_operations (void)
 995 {
 996   int old_last_basic_block = last_basic_block;
 997   block_stmt_iterator bsi;
 998   basic_block bb;
 999
1000   FOR_EACH_BB (bb)
1001     {
1002       if (bb->index >= old_last_basic_block)
1003         continue;
1004       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1005         {
1006           expand_complex_operations_1 (&bsi);
1007           expand_vector_operations_1 (&bsi);
1008         }
1009     }
1010 }
1011
1012
1013 struct tree_opt_pass pass_lower_vector_ssa =
1014 {
1015   "vector",                             /* name */
1016   NULL,                                 /* gate */
1017   expand_vector_operations,             /* execute */
1018   NULL,                                 /* sub */
1019   NULL,                                 /* next */
1020   0,                                    /* static_pass_number */
1021   0,                                    /* tv_id */
1022   PROP_cfg,                             /* properties_required */
1023   0,                                    /* properties_provided */
1024   0,                                    /* properties_destroyed */
1025   0,                                    /* todo_flags_start */
1026   TODO_dump_func | TODO_update_ssa      /* todo_flags_finish */
1027     | TODO_ggc_collect | TODO_verify_ssa
1028     | TODO_verify_stmts | TODO_verify_flow,
1029   0                                     /* letter */
1030 };
1031
1032 struct tree_opt_pass pass_pre_expand =
1033 {
1034   "oplower",                            /* name */
1035   0,                                    /* gate */
1036   tree_lower_operations,                /* execute */
1037   NULL,                                 /* sub */
1038   NULL,                                 /* next */
1039   0,                                    /* static_pass_number */
1040   0,                                    /* tv_id */
1041   PROP_cfg,                             /* properties_required */
1042   0,                                    /* properties_provided */
1043   0,                                    /* properties_destroyed */
1044   0,                                    /* todo_flags_start */
1045   TODO_dump_func | TODO_ggc_collect
1046     | TODO_verify_stmts,                /* todo_flags_finish */
1047   0                                     /* letter */
1048 };
1049
1050 #include "gt-tree-complex.h"