gcc/tree-complex.c

   1 /* Lower complex operations to scalar operations.
   2    Copyright (C) 2004 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 "tree-flow.h"
  27 #include "tree-simple.h"
  28 #include "tree-iterator.h"
  29 #include "tree-pass.h"
  30 #include "flags.h"
  31
  32
  33 /* Build a temporary.  Make sure and register it to be renamed.  */
  34
  35 static tree
  36 make_temp (tree type)
  37 {
  38   tree t = create_tmp_var (type, NULL);
  39   add_referenced_tmp_var (t);
  40   bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
  41   return t;
  42 }
  43
  44 /* Force EXP to be a gimple_val.  */
  45
  46 static tree
  47 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
  48 {
  49   tree t, new_stmt, orig_stmt;
  50
  51   if (is_gimple_val (exp))
  52     return exp;
  53
  54   t = make_temp (type);
  55   new_stmt = build (MODIFY_EXPR, type, t, exp);
  56
  57   orig_stmt = bsi_stmt (*bsi);
  58   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
  59   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
  60
  61   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
  62
  63   return t;
  64 }
  65
  66 /* Extract the real or imaginary part of a complex variable or constant.
  67    Make sure that it's a proper gimple_val and gimplify it if not.
  68    Emit any new code before BSI.  */
  69
  70 static tree
  71 extract_component (block_stmt_iterator *bsi, tree t, bool imagpart_p)
  72 {
  73   tree ret, inner_type;
  74
  75   inner_type = TREE_TYPE (TREE_TYPE (t));
  76   switch (TREE_CODE (t))
  77     {
  78     case COMPLEX_CST:
  79       ret = (imagpart_p ? TREE_IMAGPART (t) : TREE_REALPART (t));
  80       break;
  81
  82     case COMPLEX_EXPR:
  83       ret = TREE_OPERAND (t, imagpart_p);
  84       break;
  85
  86     case VAR_DECL:
  87     case PARM_DECL:
  88       ret = build1 ((imagpart_p ? IMAGPART_EXPR : REALPART_EXPR),
  89                     inner_type, t);
  90       break;
  91
  92     default:
  93       abort ();
  94     }
  95
  96   return gimplify_val (bsi, inner_type, ret);
  97 }
  98
  99 /* Build a binary operation and gimplify it.  Emit code before BSI.
 100    Return the gimple_val holding the result.  */
 101
 102 static tree
 103 do_binop (block_stmt_iterator *bsi, enum tree_code code,
 104           tree type, tree a, tree b)
 105 {
 106   tree ret;
 107
 108   ret = fold (build (code, type, a, b));
 109   STRIP_NOPS (ret);
 110
 111   return gimplify_val (bsi, type, ret);
 112 }
 113
 114 /* Build a unary operation and gimplify it.  Emit code before BSI.
 115    Return the gimple_val holding the result.  */
 116
 117 static tree
 118 do_unop (block_stmt_iterator *bsi, enum tree_code code, tree type, tree a)
 119 {
 120   tree ret;
 121
 122   ret = fold (build1 (code, type, a));
 123   STRIP_NOPS (ret);
 124
 125   return gimplify_val (bsi, type, ret);
 126 }
 127
 128 /* Update an assignment to a complex variable in place.  */
 129
 130 static void
 131 update_complex_assignment (block_stmt_iterator *bsi, tree r, tree i)
 132 {
 133   tree stmt = bsi_stmt (*bsi);
 134   tree type;
 135
 136   modify_stmt (stmt);
 137   if (TREE_CODE (stmt) == RETURN_EXPR)
 138     stmt = TREE_OPERAND (stmt, 0);
 139
 140   type = TREE_TYPE (TREE_OPERAND (stmt, 1));
 141   TREE_OPERAND (stmt, 1) = build (COMPLEX_EXPR, type, r, i);
 142 }
 143
 144 /* Expand complex addition to scalars:
 145         a + b = (ar + br) + i(ai + bi)
 146         a - b = (ar - br) + i(ai + bi)
 147 */
 148
 149 static void
 150 expand_complex_addition (block_stmt_iterator *bsi, tree inner_type,
 151                          tree ar, tree ai, tree br, tree bi,
 152                          enum tree_code code)
 153 {
 154   tree rr, ri;
 155
 156   rr = do_binop (bsi, code, inner_type, ar, br);
 157   ri = do_binop (bsi, code, inner_type, ai, bi);
 158
 159   update_complex_assignment (bsi, rr, ri);
 160 }
 161
 162 /* Expand complex multiplication to scalars:
 163         a * b = (ar*br - ai*bi) + i(ar*bi + br*ai)
 164 */
 165
 166 static void
 167 expand_complex_multiplication (block_stmt_iterator *bsi, tree inner_type,
 168                                tree ar, tree ai, tree br, tree bi)
 169 {
 170   tree t1, t2, t3, t4, rr, ri;
 171
 172   t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br);
 173   t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi);
 174   t3 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi);
 175
 176   /* Avoid expanding redundant multiplication for the common
 177      case of squaring a complex number.  */
 178   if (ar == br && ai == bi)
 179     t4 = t3;
 180   else
 181     t4 = do_binop (bsi, MULT_EXPR, inner_type, ai, br);
 182
 183   rr = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2);
 184   ri = do_binop (bsi, PLUS_EXPR, inner_type, t3, t4);
 185
 186   update_complex_assignment (bsi, rr, ri);
 187 }
 188
 189 /* Expand complex division to scalars, straightforward algorithm.
 190         a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
 191             t = br*br + bi*bi
 192 */
 193
 194 static void
 195 expand_complex_div_straight (block_stmt_iterator *bsi, tree inner_type,
 196                              tree ar, tree ai, tree br, tree bi,
 197                              enum tree_code code)
 198 {
 199   tree rr, ri, div, t1, t2, t3;
 200
 201   t1 = do_binop (bsi, MULT_EXPR, inner_type, br, br);
 202   t2 = do_binop (bsi, MULT_EXPR, inner_type, bi, bi);
 203   div = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2);
 204
 205   t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br);
 206   t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi);
 207   t3 = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2);
 208   rr = do_binop (bsi, code, inner_type, t3, div);
 209
 210   t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, br);
 211   t2 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi);
 212   t3 = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2);
 213   ri = do_binop (bsi, code, inner_type, t3, div);
 214
 215   update_complex_assignment (bsi, rr, ri);
 216 }
 217
 218 /* Expand complex division to scalars, modified algorithm to minimize
 219    overflow with wide input ranges.  */
 220
 221 static void
 222 expand_complex_div_wide (block_stmt_iterator *bsi, tree inner_type,
 223                          tree ar, tree ai, tree br, tree bi,
 224                          enum tree_code code)
 225 {
 226   tree rr, ri, ratio, div, t1, t2, min, max, cond;
 227
 228   /* Examine |br| < |bi|, and branch.  */
 229   t1 = do_unop (bsi, ABS_EXPR, inner_type, br);
 230   t2 = do_unop (bsi, ABS_EXPR, inner_type, bi);
 231   cond = fold (build (LT_EXPR, boolean_type_node, t1, t2));
 232   STRIP_NOPS (cond);
 233
 234   if (TREE_CONSTANT (cond))
 235     {
 236       if (integer_zerop (cond))
 237         min = bi, max = br;
 238       else
 239         min = br, max = bi;
 240     }
 241   else
 242     {
 243       basic_block bb_cond, bb_true, bb_false, bb_join;
 244       tree l1, l2, l3;
 245       edge e;
 246
 247       l1 = create_artificial_label ();
 248       t1 = build (GOTO_EXPR, void_type_node, l1);
 249       l2 = create_artificial_label ();
 250       t2 = build (GOTO_EXPR, void_type_node, l2);
 251       cond = build (COND_EXPR, void_type_node, cond, t1, t2);
 252       bsi_insert_before (bsi, cond, BSI_SAME_STMT);
 253
 254       min = make_temp (inner_type);
 255       max = make_temp (inner_type);
 256       l3 = create_artificial_label ();
 257
 258       /* Split the original block, and create the TRUE and FALSE blocks.  */
 259       e = split_block (bsi->bb, cond);
 260       bb_cond = e->src;
 261       bb_join = e->dest;
 262       bb_true = create_empty_bb (bb_cond);
 263       bb_false = create_empty_bb (bb_true);
 264
 265       /* Wire the blocks together.  */
 266       e->flags = EDGE_TRUE_VALUE;
 267       redirect_edge_succ (e, bb_true);
 268       make_edge (bb_cond, bb_false, EDGE_FALSE_VALUE);
 269       make_edge (bb_true, bb_join, 0);
 270       make_edge (bb_false, bb_join, 0);
 271
 272       /* Update dominance info.  Note that bb_join's data was
 273          updated by split_block.  */
 274       if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
 275         {
 276           set_immediate_dominator (CDI_DOMINATORS, bb_true, bb_cond);
 277           set_immediate_dominator (CDI_DOMINATORS, bb_false, bb_cond);
 278         }
 279
 280       /* Compute min and max for TRUE block.  */
 281       *bsi = bsi_start (bb_true);
 282       t1 = build (LABEL_EXPR, void_type_node, l1);
 283       bsi_insert_after (bsi, t1, BSI_NEW_STMT);
 284       t1 = build (MODIFY_EXPR, inner_type, min, br);
 285       bsi_insert_after (bsi, t1, BSI_NEW_STMT);
 286       t1 = build (MODIFY_EXPR, inner_type, max, bi);
 287       bsi_insert_after (bsi, t1, BSI_NEW_STMT);
 288
 289       /* Compute min and max for FALSE block.  */
 290       *bsi = bsi_start (bb_false);
 291       t1 = build (LABEL_EXPR, void_type_node, l2);
 292       bsi_insert_after (bsi, t1, BSI_NEW_STMT);
 293       t1 = build (MODIFY_EXPR, inner_type, min, bi);
 294       bsi_insert_after (bsi, t1, BSI_NEW_STMT);
 295       t1 = build (MODIFY_EXPR, inner_type, max, br);
 296       bsi_insert_after (bsi, t1, BSI_NEW_STMT);
 297
 298       /* Insert the join label into the tail of the original block.  */
 299       *bsi = bsi_start (bb_join);
 300       t1 = build (LABEL_EXPR, void_type_node, l3);
 301       bsi_insert_before (bsi, t1, BSI_SAME_STMT);
 302     }
 303
 304   /* Now we have MIN(|br|, |bi|) and MAX(|br|, |bi|).  We now use the
 305      ratio min/max to scale both the dividend and divisor.  */
 306   ratio = do_binop (bsi, code, inner_type, min, max);
 307
 308   /* Calculate the divisor: min*ratio + max.  */
 309   t1 = do_binop (bsi, MULT_EXPR, inner_type, min, ratio);
 310   div = do_binop (bsi, PLUS_EXPR, inner_type, t1, max);
 311
 312   /* Result is now ((ar + ai*ratio)/div) + i((ai - ar*ratio)/div). */
 313   t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, ratio);
 314   t2 = do_binop (bsi, PLUS_EXPR, inner_type, ar, t1);
 315   rr = do_binop (bsi, code, inner_type, t2, div);
 316
 317   t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, ratio);
 318   t2 = do_binop (bsi, MINUS_EXPR, inner_type, ai, t1);
 319   ri = do_binop (bsi, code, inner_type, t2, div);
 320
 321   update_complex_assignment (bsi, rr, ri);
 322 }
 323
 324 /* Expand complex division to scalars.  */
 325
 326 static void
 327 expand_complex_division (block_stmt_iterator *bsi, tree inner_type,
 328                          tree ar, tree ai, tree br, tree bi,
 329                          enum tree_code code)
 330 {
 331   switch (flag_complex_divide_method)
 332     {
 333     case 0:
 334       /* straightforward implementation of complex divide acceptable.  */
 335       expand_complex_div_straight (bsi, inner_type, ar, ai, br, bi, code);
 336       break;
 337     case 1:
 338       /* wide ranges of inputs must work for complex divide.  */
 339       expand_complex_div_wide (bsi, inner_type, ar, ai, br, bi, code);
 340       break;
 341     default:
 342       /* C99-like requirements for complex divide (not yet implemented).  */
 343       abort ();
 344     }
 345 }
 346
 347 /* Expand complex negation to scalars:
 348         -a = (-ar) + i(-ai)
 349 */
 350
 351 static void
 352 expand_complex_negation (block_stmt_iterator *bsi, tree inner_type,
 353                          tree ar, tree ai)
 354 {
 355   tree rr, ri;
 356
 357   rr = do_unop (bsi, NEGATE_EXPR, inner_type, ar);
 358   ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai);
 359
 360   update_complex_assignment (bsi, rr, ri);
 361 }
 362
 363 /* Expand complex conjugate to scalars:
 364         ~a = (ar) + i(-ai)
 365 */
 366
 367 static void
 368 expand_complex_conjugate (block_stmt_iterator *bsi, tree inner_type,
 369                           tree ar, tree ai)
 370 {
 371   tree ri;
 372
 373   ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai);
 374
 375   update_complex_assignment (bsi, ar, ri);
 376 }
 377
 378 /* Expand complex comparison (EQ or NE only).  */
 379
 380 static void
 381 expand_complex_comparison (block_stmt_iterator *bsi, tree ar, tree ai,
 382                            tree br, tree bi, enum tree_code code)
 383 {
 384   tree cr, ci, cc, stmt, type;
 385
 386   cr = do_binop (bsi, code, boolean_type_node, ar, br);
 387   ci = do_binop (bsi, code, boolean_type_node, ai, bi);
 388   cc = do_binop (bsi, (code == EQ_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR),
 389                  boolean_type_node, cr, ci);
 390
 391   stmt = bsi_stmt (*bsi);
 392   modify_stmt (stmt);
 393
 394   switch (TREE_CODE (stmt))
 395     {
 396     case RETURN_EXPR:
 397       stmt = TREE_OPERAND (stmt, 0);
 398       /* FALLTHRU */
 399     case MODIFY_EXPR:
 400       type = TREE_TYPE (TREE_OPERAND (stmt, 1));
 401       TREE_OPERAND (stmt, 1) = convert (type, cc);
 402       break;
 403     case COND_EXPR:
 404       TREE_OPERAND (stmt, 0) = cc;
 405       break;
 406     default:
 407       abort ();
 408     }
 409 }
 410
 411 /* Process one statement.  If we identify a complex operation, expand it.  */
 412
 413 static void
 414 expand_complex_operations_1 (block_stmt_iterator *bsi)
 415 {
 416   tree stmt = bsi_stmt (*bsi);
 417   tree rhs, type, inner_type;
 418   tree ac, ar, ai, bc, br, bi;
 419   enum tree_code code;
 420
 421   switch (TREE_CODE (stmt))
 422     {
 423     case RETURN_EXPR:
 424       stmt = TREE_OPERAND (stmt, 0);
 425       if (!stmt)
 426         return;
 427       if (TREE_CODE (stmt) != MODIFY_EXPR)
 428         return;
 429       /* FALLTHRU */
 430
 431     case MODIFY_EXPR:
 432       rhs = TREE_OPERAND (stmt, 1);
 433       break;
 434
 435     case COND_EXPR:
 436       rhs = TREE_OPERAND (stmt, 0);
 437       break;
 438
 439     default:
 440       return;
 441     }
 442
 443   type = TREE_TYPE (rhs);
 444   code = TREE_CODE (rhs);
 445
 446   /* Initial filter for operations we handle.  */
 447   switch (code)
 448     {
 449     case PLUS_EXPR:
 450     case MINUS_EXPR:
 451     case MULT_EXPR:
 452     case TRUNC_DIV_EXPR:
 453     case CEIL_DIV_EXPR:
 454     case FLOOR_DIV_EXPR:
 455     case ROUND_DIV_EXPR:
 456     case RDIV_EXPR:
 457     case NEGATE_EXPR:
 458     case CONJ_EXPR:
 459       if (TREE_CODE (type) != COMPLEX_TYPE)
 460         return;
 461       inner_type = TREE_TYPE (type);
 462       break;
 463
 464     case EQ_EXPR:
 465     case NE_EXPR:
 466       inner_type = TREE_TYPE (TREE_OPERAND (rhs, 1));
 467       if (TREE_CODE (inner_type) != COMPLEX_TYPE)
 468         return;
 469       break;
 470
 471     default:
 472       return;
 473     }
 474
 475   /* Extract the components of the two complex values.  Make sure and
 476      handle the common case of the same value used twice specially.  */
 477   ac = TREE_OPERAND (rhs, 0);
 478   ar = extract_component (bsi, ac, 0);
 479   ai = extract_component (bsi, ac, 1);
 480
 481   if (TREE_CODE_CLASS (code) == '1')
 482     bc = br = bi = NULL;
 483   else
 484     {
 485       bc = TREE_OPERAND (rhs, 1);
 486       if (ac == bc)
 487         br = ar, bi = ai;
 488       else
 489         {
 490           br = extract_component (bsi, bc, 0);
 491           bi = extract_component (bsi, bc, 1);
 492         }
 493     }
 494
 495   switch (code)
 496     {
 497     case PLUS_EXPR:
 498     case MINUS_EXPR:
 499       expand_complex_addition (bsi, inner_type, ar, ai, br, bi, code);
 500       break;
 501
 502     case MULT_EXPR:
 503       expand_complex_multiplication (bsi, inner_type, ar, ai, br, bi);
 504       break;
 505
 506     case TRUNC_DIV_EXPR:
 507     case CEIL_DIV_EXPR:
 508     case FLOOR_DIV_EXPR:
 509     case ROUND_DIV_EXPR:
 510     case RDIV_EXPR:
 511       expand_complex_division (bsi, inner_type, ar, ai, br, bi, code);
 512       break;
 513
 514     case NEGATE_EXPR:
 515       expand_complex_negation (bsi, inner_type, ar, ai);
 516       break;
 517
 518     case CONJ_EXPR:
 519       expand_complex_conjugate (bsi, inner_type, ar, ai);
 520       break;
 521
 522     case EQ_EXPR:
 523     case NE_EXPR:
 524       expand_complex_comparison (bsi, ar, ai, br, bi, code);
 525       break;
 526
 527     default:
 528       abort ();
 529     }
 530 }
 531
 532 /* Main loop to process each statement.  */
 533 /* ??? Could use dominator bits to propagate from complex_expr at the
 534    same time.  This might reveal more constants, particularly in cases
 535    such as (complex = complex op scalar).  This may not be relevant
 536    after SRA and subsequent cleanups.  Proof of this would be if we
 537    verify that the code generated by expand_complex_div_wide is
 538    simplified properly to straight-line code.  */
 539
 540 static void
 541 expand_complex_operations (void)
 542 {
 543   int old_last_basic_block = last_basic_block;
 544   block_stmt_iterator bsi;
 545   basic_block bb;
 546
 547   FOR_EACH_BB (bb)
 548     {
 549       if (bb->index >= old_last_basic_block)
 550         continue;
 551       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 552         expand_complex_operations_1 (&bsi);
 553     }
 554 }
 555
 556 struct tree_opt_pass pass_lower_complex =
 557 {
 558   "complex",                            /* name */
 559   NULL,                                 /* gate */
 560   expand_complex_operations,            /* execute */
 561   NULL,                                 /* sub */
 562   NULL,                                 /* next */
 563   0,                                    /* static_pass_number */
 564   0,                                    /* tv_id */
 565   PROP_cfg,                             /* properties_required */
 566   0,                                    /* properties_provided */
 567   0,                                    /* properties_destroyed */
 568   0,                                    /* todo_flags_start */
 569   TODO_dump_func | TODO_rename_vars
 570     | TODO_ggc_collect | TODO_verify_ssa
 571     | TODO_verify_stmts | TODO_verify_flow /* todo_flags_finish */
 572 };