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