gcc/tree-complex.c

   1 /* Lower complex number 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
 567 static void
 568 tree_lower_complex (void)
 569 {
 570   int old_last_basic_block = last_basic_block;
 571   block_stmt_iterator bsi;
 572   basic_block bb;
 573
 574   FOR_EACH_BB (bb)
 575     {
 576       if (bb->index >= old_last_basic_block)
 577         continue;
 578       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 579         expand_complex_operations_1 (&bsi);
 580     }
 581 }
 582
 583
 584 struct tree_opt_pass pass_lower_complex =
 585 {
 586   "cplxlower",                          /* name */
 587   0,                                    /* gate */
 588   tree_lower_complex,                   /* execute */
 589   NULL,                                 /* sub */
 590   NULL,                                 /* next */
 591   0,                                    /* static_pass_number */
 592   0,                                    /* tv_id */
 593   PROP_cfg,                             /* properties_required */
 594   0,                                    /* properties_provided */
 595   0,                                    /* properties_destroyed */
 596   0,                                    /* todo_flags_start */
 597   TODO_dump_func | TODO_ggc_collect
 598     | TODO_verify_stmts,                /* todo_flags_finish */
 599   0                                     /* letter */
 600 };