gcc/tree-complex.c

   1 /* Lower complex number operations to scalar operations.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "real.h"
  28 #include "flags.h"
  29 #include "tree-flow.h"
  30 #include "gimple.h"
  31 #include "tree-iterator.h"
  32 #include "tree-pass.h"
  33 #include "tree-ssa-propagate.h"
  34 #include "diagnostic.h"
  35
  36
  37 /* For each complex ssa name, a lattice value.  We're interested in finding
  38    out whether a complex number is degenerate in some way, having only real
  39    or only complex parts.  */
  40
  41 enum
  42 {
  43   UNINITIALIZED = 0,
  44   ONLY_REAL = 1,
  45   ONLY_IMAG = 2,
  46   VARYING = 3
  47 };
  48
  49 /* The type complex_lattice_t holds combinations of the above
  50    constants.  */
  51 typedef int complex_lattice_t;
  52
  53 #define PAIR(a, b)  ((a) << 2 | (b))
  54
  55 DEF_VEC_I(complex_lattice_t);
  56 DEF_VEC_ALLOC_I(complex_lattice_t, heap);
  57
  58 static VEC(complex_lattice_t, heap) *complex_lattice_values;
  59
  60 /* For each complex variable, a pair of variables for the components exists in
  61    the hashtable.  */
  62 static htab_t complex_variable_components;
  63
  64 /* For each complex SSA_NAME, a pair of ssa names for the components.  */
  65 static VEC(tree, heap) *complex_ssa_name_components;
  66
  67 /* Lookup UID in the complex_variable_components hashtable and return the
  68    associated tree.  */
  69 static tree
  70 cvc_lookup (unsigned int uid)
  71 {
  72   struct int_tree_map *h, in;
  73   in.uid = uid;
  74   h = (struct int_tree_map *) htab_find_with_hash (complex_variable_components, &in, uid);
  75   return h ? h->to : NULL;
  76 }
  77
  78 /* Insert the pair UID, TO into the complex_variable_components hashtable.  */
  79
  80 static void
  81 cvc_insert (unsigned int uid, tree to)
  82 {
  83   struct int_tree_map *h;
  84   void **loc;
  85
  86   h = XNEW (struct int_tree_map);
  87   h->uid = uid;
  88   h->to = to;
  89   loc = htab_find_slot_with_hash (complex_variable_components, h,
  90                                   uid, INSERT);
  91   *(struct int_tree_map **) loc = h;
  92 }
  93
  94 /* Return true if T is not a zero constant.  In the case of real values,
  95    we're only interested in +0.0.  */
  96
  97 static int
  98 some_nonzerop (tree t)
  99 {
 100   int zerop = false;
 101
 102   /* Operations with real or imaginary part of a complex number zero
 103      cannot be treated the same as operations with a real or imaginary
 104      operand if we care about the signs of zeros in the result.  */
 105   if (TREE_CODE (t) == REAL_CST && !flag_signed_zeros)
 106     zerop = REAL_VALUES_IDENTICAL (TREE_REAL_CST (t), dconst0);
 107   else if (TREE_CODE (t) == FIXED_CST)
 108     zerop = fixed_zerop (t);
 109   else if (TREE_CODE (t) == INTEGER_CST)
 110     zerop = integer_zerop (t);
 111
 112   return !zerop;
 113 }
 114
 115
 116 /* Compute a lattice value from the components of a complex type REAL
 117    and IMAG.  */
 118
 119 static complex_lattice_t
 120 find_lattice_value_parts (tree real, tree imag)
 121 {
 122   int r, i;
 123   complex_lattice_t ret;
 124
 125   r = some_nonzerop (real);
 126   i = some_nonzerop (imag);
 127   ret = r * ONLY_REAL + i * ONLY_IMAG;
 128
 129   /* ??? On occasion we could do better than mapping 0+0i to real, but we
 130      certainly don't want to leave it UNINITIALIZED, which eventually gets
 131      mapped to VARYING.  */
 132   if (ret == UNINITIALIZED)
 133     ret = ONLY_REAL;
 134
 135   return ret;
 136 }
 137
 138
 139 /* Compute a lattice value from gimple_val T.  */
 140
 141 static complex_lattice_t
 142 find_lattice_value (tree t)
 143 {
 144   tree real, imag;
 145
 146   switch (TREE_CODE (t))
 147     {
 148     case SSA_NAME:
 149       return VEC_index (complex_lattice_t, complex_lattice_values,
 150                         SSA_NAME_VERSION (t));
 151
 152     case COMPLEX_CST:
 153       real = TREE_REALPART (t);
 154       imag = TREE_IMAGPART (t);
 155       break;
 156
 157     default:
 158       gcc_unreachable ();
 159     }
 160
 161   return find_lattice_value_parts (real, imag);
 162 }
 163
 164 /* Determine if LHS is something for which we're interested in seeing
 165    simulation results.  */
 166
 167 static bool
 168 is_complex_reg (tree lhs)
 169 {
 170   return TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE && is_gimple_reg (lhs);
 171 }
 172
 173 /* Mark the incoming parameters to the function as VARYING.  */
 174
 175 static void
 176 init_parameter_lattice_values (void)
 177 {
 178   tree parm, ssa_name;
 179
 180   for (parm = DECL_ARGUMENTS (cfun->decl); parm ; parm = TREE_CHAIN (parm))
 181     if (is_complex_reg (parm)
 182         && var_ann (parm) != NULL
 183         && (ssa_name = gimple_default_def (cfun, parm)) != NULL_TREE)
 184       VEC_replace (complex_lattice_t, complex_lattice_values,
 185                    SSA_NAME_VERSION (ssa_name), VARYING);
 186 }
 187
 188 /* Initialize simulation state for each statement.  Return false if we
 189    found no statements we want to simulate, and thus there's nothing
 190    for the entire pass to do.  */
 191
 192 static bool
 193 init_dont_simulate_again (void)
 194 {
 195   basic_block bb;
 196   gimple_stmt_iterator gsi;
 197   gimple phi;
 198   bool saw_a_complex_op = false;
 199
 200   FOR_EACH_BB (bb)
 201     {
 202       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 203         {
 204           phi = gsi_stmt (gsi);
 205           prop_set_simulate_again (phi,
 206                                    is_complex_reg (gimple_phi_result (phi)));
 207         }
 208
 209       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 210         {
 211           gimple stmt;
 212           tree op0, op1;
 213           bool sim_again_p;
 214
 215           stmt = gsi_stmt (gsi);
 216           op0 = op1 = NULL_TREE;
 217
 218           /* Most control-altering statements must be initially
 219              simulated, else we won't cover the entire cfg.  */
 220           sim_again_p = stmt_ends_bb_p (stmt);
 221
 222           switch (gimple_code (stmt))
 223             {
 224             case GIMPLE_CALL:
 225               if (gimple_call_lhs (stmt))
 226                 sim_again_p = is_complex_reg (gimple_call_lhs (stmt));
 227               break;
 228
 229             case GIMPLE_ASSIGN:
 230               sim_again_p = is_complex_reg (gimple_assign_lhs (stmt));
 231               if (gimple_assign_rhs_code (stmt) == REALPART_EXPR
 232                   || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR)
 233                 op0 = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
 234               else
 235                 op0 = gimple_assign_rhs1 (stmt);
 236               if (gimple_num_ops (stmt) > 2)
 237                 op1 = gimple_assign_rhs2 (stmt);
 238               break;
 239
 240             case GIMPLE_COND:
 241               op0 = gimple_cond_lhs (stmt);
 242               op1 = gimple_cond_rhs (stmt);
 243               break;
 244
 245             default:
 246               break;
 247             }
 248
 249           if (op0 || op1)
 250             switch (gimple_expr_code (stmt))
 251               {
 252               case EQ_EXPR:
 253               case NE_EXPR:
 254               case PLUS_EXPR:
 255               case MINUS_EXPR:
 256               case MULT_EXPR:
 257               case TRUNC_DIV_EXPR:
 258               case CEIL_DIV_EXPR:
 259               case FLOOR_DIV_EXPR:
 260               case ROUND_DIV_EXPR:
 261               case RDIV_EXPR:
 262                 if (TREE_CODE (TREE_TYPE (op0)) == COMPLEX_TYPE
 263                     || TREE_CODE (TREE_TYPE (op1)) == COMPLEX_TYPE)
 264                   saw_a_complex_op = true;
 265                 break;
 266
 267               case NEGATE_EXPR:
 268               case CONJ_EXPR:
 269                 if (TREE_CODE (TREE_TYPE (op0)) == COMPLEX_TYPE)
 270                   saw_a_complex_op = true;
 271                 break;
 272
 273               case REALPART_EXPR:
 274               case IMAGPART_EXPR:
 275                 /* The total store transformation performed during
 276                   gimplification creates such uninitialized loads
 277                   and we need to lower the statement to be able
 278                   to fix things up.  */
 279                 if (TREE_CODE (op0) == SSA_NAME
 280                     && ssa_undefined_value_p (op0))
 281                   saw_a_complex_op = true;
 282                 break;
 283
 284               default:
 285                 break;
 286               }
 287
 288           prop_set_simulate_again (stmt, sim_again_p);
 289         }
 290     }
 291
 292   return saw_a_complex_op;
 293 }
 294
 295
 296 /* Evaluate statement STMT against the complex lattice defined above.  */
 297
 298 static enum ssa_prop_result
 299 complex_visit_stmt (gimple stmt, edge *taken_edge_p ATTRIBUTE_UNUSED,
 300                     tree *result_p)
 301 {
 302   complex_lattice_t new_l, old_l, op1_l, op2_l;
 303   unsigned int ver;
 304   tree lhs;
 305
 306   lhs = gimple_get_lhs (stmt);
 307   /* Skip anything but GIMPLE_ASSIGN and GIMPLE_CALL with a lhs.  */
 308   if (!lhs)
 309     return SSA_PROP_VARYING;
 310
 311   /* These conditions should be satisfied due to the initial filter
 312      set up in init_dont_simulate_again.  */
 313   gcc_assert (TREE_CODE (lhs) == SSA_NAME);
 314   gcc_assert (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE);
 315
 316   *result_p = lhs;
 317   ver = SSA_NAME_VERSION (lhs);
 318   old_l = VEC_index (complex_lattice_t, complex_lattice_values, ver);
 319
 320   switch (gimple_expr_code (stmt))
 321     {
 322     case SSA_NAME:
 323     case COMPLEX_CST:
 324       new_l = find_lattice_value (gimple_assign_rhs1 (stmt));
 325       break;
 326
 327     case COMPLEX_EXPR:
 328       new_l = find_lattice_value_parts (gimple_assign_rhs1 (stmt),
 329                                         gimple_assign_rhs2 (stmt));
 330       break;
 331
 332     case PLUS_EXPR:
 333     case MINUS_EXPR:
 334       op1_l = find_lattice_value (gimple_assign_rhs1 (stmt));
 335       op2_l = find_lattice_value (gimple_assign_rhs2 (stmt));
 336
 337       /* We've set up the lattice values such that IOR neatly
 338          models addition.  */
 339       new_l = op1_l | op2_l;
 340       break;
 341
 342     case MULT_EXPR:
 343     case RDIV_EXPR:
 344     case TRUNC_DIV_EXPR:
 345     case CEIL_DIV_EXPR:
 346     case FLOOR_DIV_EXPR:
 347     case ROUND_DIV_EXPR:
 348       op1_l = find_lattice_value (gimple_assign_rhs1 (stmt));
 349       op2_l = find_lattice_value (gimple_assign_rhs2 (stmt));
 350
 351       /* Obviously, if either varies, so does the result.  */
 352       if (op1_l == VARYING || op2_l == VARYING)
 353         new_l = VARYING;
 354       /* Don't prematurely promote variables if we've not yet seen
 355          their inputs.  */
 356       else if (op1_l == UNINITIALIZED)
 357         new_l = op2_l;
 358       else if (op2_l == UNINITIALIZED)
 359         new_l = op1_l;
 360       else
 361         {
 362           /* At this point both numbers have only one component. If the
 363              numbers are of opposite kind, the result is imaginary,
 364              otherwise the result is real. The add/subtract translates
 365              the real/imag from/to 0/1; the ^ performs the comparison.  */
 366           new_l = ((op1_l - ONLY_REAL) ^ (op2_l - ONLY_REAL)) + ONLY_REAL;
 367
 368           /* Don't allow the lattice value to flip-flop indefinitely.  */
 369           new_l |= old_l;
 370         }
 371       break;
 372
 373     case NEGATE_EXPR:
 374     case CONJ_EXPR:
 375       new_l = find_lattice_value (gimple_assign_rhs1 (stmt));
 376       break;
 377
 378     default:
 379       new_l = VARYING;
 380       break;
 381     }
 382
 383   /* If nothing changed this round, let the propagator know.  */
 384   if (new_l == old_l)
 385     return SSA_PROP_NOT_INTERESTING;
 386
 387   VEC_replace (complex_lattice_t, complex_lattice_values, ver, new_l);
 388   return new_l == VARYING ? SSA_PROP_VARYING : SSA_PROP_INTERESTING;
 389 }
 390
 391 /* Evaluate a PHI node against the complex lattice defined above.  */
 392
 393 static enum ssa_prop_result
 394 complex_visit_phi (gimple phi)
 395 {
 396   complex_lattice_t new_l, old_l;
 397   unsigned int ver;
 398   tree lhs;
 399   int i;
 400
 401   lhs = gimple_phi_result (phi);
 402
 403   /* This condition should be satisfied due to the initial filter
 404      set up in init_dont_simulate_again.  */
 405   gcc_assert (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE);
 406
 407   /* We've set up the lattice values such that IOR neatly models PHI meet.  */
 408   new_l = UNINITIALIZED;
 409   for (i = gimple_phi_num_args (phi) - 1; i >= 0; --i)
 410     new_l |= find_lattice_value (gimple_phi_arg_def (phi, i));
 411
 412   ver = SSA_NAME_VERSION (lhs);
 413   old_l = VEC_index (complex_lattice_t, complex_lattice_values, ver);
 414
 415   if (new_l == old_l)
 416     return SSA_PROP_NOT_INTERESTING;
 417
 418   VEC_replace (complex_lattice_t, complex_lattice_values, ver, new_l);
 419   return new_l == VARYING ? SSA_PROP_VARYING : SSA_PROP_INTERESTING;
 420 }
 421
 422 /* Create one backing variable for a complex component of ORIG.  */
 423
 424 static tree
 425 create_one_component_var (tree type, tree orig, const char *prefix,
 426                           const char *suffix, enum tree_code code)
 427 {
 428   tree r = create_tmp_var (type, prefix);
 429   add_referenced_var (r);
 430
 431   DECL_SOURCE_LOCATION (r) = DECL_SOURCE_LOCATION (orig);
 432   DECL_ARTIFICIAL (r) = 1;
 433
 434   if (DECL_NAME (orig) && !DECL_IGNORED_P (orig))
 435     {
 436       const char *name = IDENTIFIER_POINTER (DECL_NAME (orig));
 437       tree inner_type;
 438
 439       DECL_NAME (r) = get_identifier (ACONCAT ((name, suffix, NULL)));
 440
 441       inner_type = TREE_TYPE (TREE_TYPE (orig));
 442       SET_DECL_DEBUG_EXPR (r, build1 (code, type, orig));
 443       DECL_DEBUG_EXPR_IS_FROM (r) = 1;
 444       DECL_IGNORED_P (r) = 0;
 445       TREE_NO_WARNING (r) = TREE_NO_WARNING (orig);
 446     }
 447   else
 448     {
 449       DECL_IGNORED_P (r) = 1;
 450       TREE_NO_WARNING (r) = 1;
 451     }
 452
 453   return r;
 454 }
 455
 456 /* Retrieve a value for a complex component of VAR.  */
 457
 458 static tree
 459 get_component_var (tree var, bool imag_p)
 460 {
 461   size_t decl_index = DECL_UID (var) * 2 + imag_p;
 462   tree ret = cvc_lookup (decl_index);
 463
 464   if (ret == NULL)
 465     {
 466       ret = create_one_component_var (TREE_TYPE (TREE_TYPE (var)), var,
 467                                       imag_p ? "CI" : "CR",
 468                                       imag_p ? "$imag" : "$real",
 469                                       imag_p ? IMAGPART_EXPR : REALPART_EXPR);
 470       cvc_insert (decl_index, ret);
 471     }
 472
 473   return ret;
 474 }
 475
 476 /* Retrieve a value for a complex component of SSA_NAME.  */
 477
 478 static tree
 479 get_component_ssa_name (tree ssa_name, bool imag_p)
 480 {
 481   complex_lattice_t lattice = find_lattice_value (ssa_name);
 482   size_t ssa_name_index;
 483   tree ret;
 484
 485   if (lattice == (imag_p ? ONLY_REAL : ONLY_IMAG))
 486     {
 487       tree inner_type = TREE_TYPE (TREE_TYPE (ssa_name));
 488       if (SCALAR_FLOAT_TYPE_P (inner_type))
 489         return build_real (inner_type, dconst0);
 490       else
 491         return build_int_cst (inner_type, 0);
 492     }
 493
 494   ssa_name_index = SSA_NAME_VERSION (ssa_name) * 2 + imag_p;
 495   ret = VEC_index (tree, complex_ssa_name_components, ssa_name_index);
 496   if (ret == NULL)
 497     {
 498       ret = get_component_var (SSA_NAME_VAR (ssa_name), imag_p);
 499       ret = make_ssa_name (ret, NULL);
 500
 501       /* Copy some properties from the original.  In particular, whether it
 502          is used in an abnormal phi, and whether it's uninitialized.  */
 503       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ret)
 504         = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name);
 505       if (TREE_CODE (SSA_NAME_VAR (ssa_name)) == VAR_DECL
 506           && gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name)))
 507         {
 508           SSA_NAME_DEF_STMT (ret) = SSA_NAME_DEF_STMT (ssa_name);
 509           set_default_def (SSA_NAME_VAR (ret), ret);
 510         }
 511
 512       VEC_replace (tree, complex_ssa_name_components, ssa_name_index, ret);
 513     }
 514
 515   return ret;
 516 }
 517
 518 /* Set a value for a complex component of SSA_NAME, return a
 519    gimple_seq of stuff that needs doing.  */
 520
 521 static gimple_seq
 522 set_component_ssa_name (tree ssa_name, bool imag_p, tree value)
 523 {
 524   complex_lattice_t lattice = find_lattice_value (ssa_name);
 525   size_t ssa_name_index;
 526   tree comp;
 527   gimple last;
 528   gimple_seq list;
 529
 530   /* We know the value must be zero, else there's a bug in our lattice
 531      analysis.  But the value may well be a variable known to contain
 532      zero.  We should be safe ignoring it.  */
 533   if (lattice == (imag_p ? ONLY_REAL : ONLY_IMAG))
 534     return NULL;
 535
 536   /* If we've already assigned an SSA_NAME to this component, then this
 537      means that our walk of the basic blocks found a use before the set.
 538      This is fine.  Now we should create an initialization for the value
 539      we created earlier.  */
 540   ssa_name_index = SSA_NAME_VERSION (ssa_name) * 2 + imag_p;
 541   comp = VEC_index (tree, complex_ssa_name_components, ssa_name_index);
 542   if (comp)
 543     ;
 544
 545   /* If we've nothing assigned, and the value we're given is already stable,
 546      then install that as the value for this SSA_NAME.  This preemptively
 547      copy-propagates the value, which avoids unnecessary memory allocation.  */
 548   else if (is_gimple_min_invariant (value)
 549            && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 550     {
 551       VEC_replace (tree, complex_ssa_name_components, ssa_name_index, value);
 552       return NULL;
 553     }
 554   else if (TREE_CODE (value) == SSA_NAME
 555            && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 556     {
 557       /* Replace an anonymous base value with the variable from cvc_lookup.
 558          This should result in better debug info.  */
 559       if (DECL_IGNORED_P (SSA_NAME_VAR (value))
 560           && !DECL_IGNORED_P (SSA_NAME_VAR (ssa_name)))
 561         {
 562           comp = get_component_var (SSA_NAME_VAR (ssa_name), imag_p);
 563           replace_ssa_name_symbol (value, comp);
 564         }
 565
 566       VEC_replace (tree, complex_ssa_name_components, ssa_name_index, value);
 567       return NULL;
 568     }
 569
 570   /* Finally, we need to stabilize the result by installing the value into
 571      a new ssa name.  */
 572   else
 573     comp = get_component_ssa_name (ssa_name, imag_p);
 574
 575   /* Do all the work to assign VALUE to COMP.  */
 576   list = NULL;
 577   value = force_gimple_operand (value, &list, false, NULL);
 578   last =  gimple_build_assign (comp, value);
 579   gimple_seq_add_stmt (&list, last);
 580   gcc_assert (SSA_NAME_DEF_STMT (comp) == last);
 581
 582   return list;
 583 }
 584
 585 /* Extract the real or imaginary part of a complex variable or constant.
 586    Make sure that it's a proper gimple_val and gimplify it if not.
 587    Emit any new code before gsi.  */
 588
 589 static tree
 590 extract_component (gimple_stmt_iterator *gsi, tree t, bool imagpart_p,
 591                    bool gimple_p)
 592 {
 593   switch (TREE_CODE (t))
 594     {
 595     case COMPLEX_CST:
 596       return imagpart_p ? TREE_IMAGPART (t) : TREE_REALPART (t);
 597
 598     case COMPLEX_EXPR:
 599       gcc_unreachable ();
 600
 601     case VAR_DECL:
 602     case RESULT_DECL:
 603     case PARM_DECL:
 604     case INDIRECT_REF:
 605     case COMPONENT_REF:
 606     case ARRAY_REF:
 607     case VIEW_CONVERT_EXPR:
 608       {
 609         tree inner_type = TREE_TYPE (TREE_TYPE (t));
 610
 611         t = build1 ((imagpart_p ? IMAGPART_EXPR : REALPART_EXPR),
 612                     inner_type, unshare_expr (t));
 613
 614         if (gimple_p)
 615           t = force_gimple_operand_gsi (gsi, t, true, NULL, true,
 616                                         GSI_SAME_STMT);
 617
 618         return t;
 619       }
 620
 621     case SSA_NAME:
 622       return get_component_ssa_name (t, imagpart_p);
 623
 624     default:
 625       gcc_unreachable ();
 626     }
 627 }
 628
 629 /* Update the complex components of the ssa name on the lhs of STMT.  */
 630
 631 static void
 632 update_complex_components (gimple_stmt_iterator *gsi, gimple stmt, tree r,
 633                            tree i)
 634 {
 635   tree lhs;
 636   gimple_seq list;
 637
 638   lhs = gimple_get_lhs (stmt);
 639
 640   list = set_component_ssa_name (lhs, false, r);
 641   if (list)
 642     gsi_insert_seq_after (gsi, list, GSI_CONTINUE_LINKING);
 643
 644   list = set_component_ssa_name (lhs, true, i);
 645   if (list)
 646     gsi_insert_seq_after (gsi, list, GSI_CONTINUE_LINKING);
 647 }
 648
 649 static void
 650 update_complex_components_on_edge (edge e, tree lhs, tree r, tree i)
 651 {
 652   gimple_seq list;
 653
 654   list = set_component_ssa_name (lhs, false, r);
 655   if (list)
 656     gsi_insert_seq_on_edge (e, list);
 657
 658   list = set_component_ssa_name (lhs, true, i);
 659   if (list)
 660     gsi_insert_seq_on_edge (e, list);
 661 }
 662
 663
 664 /* Update an assignment to a complex variable in place.  */
 665
 666 static void
 667 update_complex_assignment (gimple_stmt_iterator *gsi, tree r, tree i)
 668 {
 669   gimple_stmt_iterator orig_si = *gsi;
 670
 671   if (gimple_in_ssa_p (cfun))
 672     update_complex_components (gsi, gsi_stmt (*gsi), r, i);
 673
 674   gimple_assign_set_rhs_with_ops (&orig_si, COMPLEX_EXPR, r, i);
 675   update_stmt (gsi_stmt (orig_si));
 676 }
 677
 678
 679 /* Generate code at the entry point of the function to initialize the
 680    component variables for a complex parameter.  */
 681
 682 static void
 683 update_parameter_components (void)
 684 {
 685   edge entry_edge = single_succ_edge (ENTRY_BLOCK_PTR);
 686   tree parm;
 687
 688   for (parm = DECL_ARGUMENTS (cfun->decl); parm ; parm = TREE_CHAIN (parm))
 689     {
 690       tree type = TREE_TYPE (parm);
 691       tree ssa_name, r, i;
 692
 693       if (TREE_CODE (type) != COMPLEX_TYPE || !is_gimple_reg (parm))
 694         continue;
 695
 696       type = TREE_TYPE (type);
 697       ssa_name = gimple_default_def (cfun, parm);
 698       if (!ssa_name)
 699         continue;
 700
 701       r = build1 (REALPART_EXPR, type, ssa_name);
 702       i = build1 (IMAGPART_EXPR, type, ssa_name);
 703       update_complex_components_on_edge (entry_edge, ssa_name, r, i);
 704     }
 705 }
 706
 707 /* Generate code to set the component variables of a complex variable
 708    to match the PHI statements in block BB.  */
 709
 710 static void
 711 update_phi_components (basic_block bb)
 712 {
 713   gimple_stmt_iterator gsi;
 714
 715   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 716     {
 717       gimple phi = gsi_stmt (gsi);
 718
 719       if (is_complex_reg (gimple_phi_result (phi)))
 720         {
 721           tree lr, li;
 722           gimple pr = NULL, pi = NULL;
 723           unsigned int i, n;
 724
 725           lr = get_component_ssa_name (gimple_phi_result (phi), false);
 726           if (TREE_CODE (lr) == SSA_NAME)
 727             {
 728               pr = create_phi_node (lr, bb);
 729               SSA_NAME_DEF_STMT (lr) = pr;
 730             }
 731
 732           li = get_component_ssa_name (gimple_phi_result (phi), true);
 733           if (TREE_CODE (li) == SSA_NAME)
 734             {
 735               pi = create_phi_node (li, bb);
 736               SSA_NAME_DEF_STMT (li) = pi;
 737             }
 738
 739           for (i = 0, n = gimple_phi_num_args (phi); i < n; ++i)
 740             {
 741               tree comp, arg = gimple_phi_arg_def (phi, i);
 742               if (pr)
 743                 {
 744                   comp = extract_component (NULL, arg, false, false);
 745                   SET_PHI_ARG_DEF (pr, i, comp);
 746                 }
 747               if (pi)
 748                 {
 749                   comp = extract_component (NULL, arg, true, false);
 750                   SET_PHI_ARG_DEF (pi, i, comp);
 751                 }
 752             }
 753         }
 754     }
 755 }
 756
 757 /* Expand a complex move to scalars.  */
 758
 759 static void
 760 expand_complex_move (gimple_stmt_iterator *gsi, tree type)
 761 {
 762   tree inner_type = TREE_TYPE (type);
 763   tree r, i, lhs, rhs;
 764   gimple stmt = gsi_stmt (*gsi);
 765
 766   if (is_gimple_assign (stmt))
 767     {
 768       lhs = gimple_assign_lhs (stmt);
 769       if (gimple_num_ops (stmt) == 2)
 770         rhs = gimple_assign_rhs1 (stmt);
 771       else
 772         rhs = NULL_TREE;
 773     }
 774   else if (is_gimple_call (stmt))
 775     {
 776       lhs = gimple_call_lhs (stmt);
 777       rhs = NULL_TREE;
 778     }
 779   else
 780     gcc_unreachable ();
 781
 782   if (TREE_CODE (lhs) == SSA_NAME)
 783     {
 784       if (is_ctrl_altering_stmt (stmt))
 785         {
 786           edge_iterator ei;
 787           edge e;
 788
 789           /* The value is not assigned on the exception edges, so we need not
 790              concern ourselves there.  We do need to update on the fallthru
 791              edge.  Find it.  */
 792           FOR_EACH_EDGE (e, ei, gsi_bb (*gsi)->succs)
 793             if (e->flags & EDGE_FALLTHRU)
 794               goto found_fallthru;
 795           gcc_unreachable ();
 796         found_fallthru:
 797
 798           r = build1 (REALPART_EXPR, inner_type, lhs);
 799           i = build1 (IMAGPART_EXPR, inner_type, lhs);
 800           update_complex_components_on_edge (e, lhs, r, i);
 801         }
 802       else if (is_gimple_call (stmt)
 803                || gimple_has_side_effects (stmt)
 804                || gimple_assign_rhs_code (stmt) == PAREN_EXPR)
 805         {
 806           r = build1 (REALPART_EXPR, inner_type, lhs);
 807           i = build1 (IMAGPART_EXPR, inner_type, lhs);
 808           update_complex_components (gsi, stmt, r, i);
 809         }
 810       else
 811         {
 812           if (gimple_assign_rhs_code (stmt) != COMPLEX_EXPR)
 813             {
 814               r = extract_component (gsi, rhs, 0, true);
 815               i = extract_component (gsi, rhs, 1, true);
 816             }
 817           else
 818             {
 819               r = gimple_assign_rhs1 (stmt);
 820               i = gimple_assign_rhs2 (stmt);
 821             }
 822           update_complex_assignment (gsi, r, i);
 823         }
 824     }
 825   else if (rhs && TREE_CODE (rhs) == SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
 826     {
 827       tree x;
 828       gimple t;
 829
 830       r = extract_component (gsi, rhs, 0, false);
 831       i = extract_component (gsi, rhs, 1, false);
 832
 833       x = build1 (REALPART_EXPR, inner_type, unshare_expr (lhs));
 834       t = gimple_build_assign (x, r);
 835       gsi_insert_before (gsi, t, GSI_SAME_STMT);
 836
 837       if (stmt == gsi_stmt (*gsi))
 838         {
 839           x = build1 (IMAGPART_EXPR, inner_type, unshare_expr (lhs));
 840           gimple_assign_set_lhs (stmt, x);
 841           gimple_assign_set_rhs1 (stmt, i);
 842         }
 843       else
 844         {
 845           x = build1 (IMAGPART_EXPR, inner_type, unshare_expr (lhs));
 846           t = gimple_build_assign (x, i);
 847           gsi_insert_before (gsi, t, GSI_SAME_STMT);
 848
 849           stmt = gsi_stmt (*gsi);
 850           gcc_assert (gimple_code (stmt) == GIMPLE_RETURN);
 851           gimple_return_set_retval (stmt, lhs);
 852         }
 853
 854       update_stmt (stmt);
 855     }
 856 }
 857
 858 /* Expand complex addition to scalars:
 859         a + b = (ar + br) + i(ai + bi)
 860         a - b = (ar - br) + i(ai + bi)
 861 */
 862
 863 static void
 864 expand_complex_addition (gimple_stmt_iterator *gsi, tree inner_type,
 865                          tree ar, tree ai, tree br, tree bi,
 866                          enum tree_code code,
 867                          complex_lattice_t al, complex_lattice_t bl)
 868 {
 869   tree rr, ri;
 870
 871   switch (PAIR (al, bl))
 872     {
 873     case PAIR (ONLY_REAL, ONLY_REAL):
 874       rr = gimplify_build2 (gsi, code, inner_type, ar, br);
 875       ri = ai;
 876       break;
 877
 878     case PAIR (ONLY_REAL, ONLY_IMAG):
 879       rr = ar;
 880       if (code == MINUS_EXPR)
 881         ri = gimplify_build2 (gsi, MINUS_EXPR, inner_type, ai, bi);
 882       else
 883         ri = bi;
 884       break;
 885
 886     case PAIR (ONLY_IMAG, ONLY_REAL):
 887       if (code == MINUS_EXPR)
 888         rr = gimplify_build2 (gsi, MINUS_EXPR, inner_type, ar, br);
 889       else
 890         rr = br;
 891       ri = ai;
 892       break;
 893
 894     case PAIR (ONLY_IMAG, ONLY_IMAG):
 895       rr = ar;
 896       ri = gimplify_build2 (gsi, code, inner_type, ai, bi);
 897       break;
 898
 899     case PAIR (VARYING, ONLY_REAL):
 900       rr = gimplify_build2 (gsi, code, inner_type, ar, br);
 901       ri = ai;
 902       break;
 903
 904     case PAIR (VARYING, ONLY_IMAG):
 905       rr = ar;
 906       ri = gimplify_build2 (gsi, code, inner_type, ai, bi);
 907       break;
 908
 909     case PAIR (ONLY_REAL, VARYING):
 910       if (code == MINUS_EXPR)
 911         goto general;
 912       rr = gimplify_build2 (gsi, code, inner_type, ar, br);
 913       ri = bi;
 914       break;
 915
 916     case PAIR (ONLY_IMAG, VARYING):
 917       if (code == MINUS_EXPR)
 918         goto general;
 919       rr = br;
 920       ri = gimplify_build2 (gsi, code, inner_type, ai, bi);
 921       break;
 922
 923     case PAIR (VARYING, VARYING):
 924     general:
 925       rr = gimplify_build2 (gsi, code, inner_type, ar, br);
 926       ri = gimplify_build2 (gsi, code, inner_type, ai, bi);
 927       break;
 928
 929     default:
 930       gcc_unreachable ();
 931     }
 932
 933   update_complex_assignment (gsi, rr, ri);
 934 }
 935
 936 /* Expand a complex multiplication or division to a libcall to the c99
 937    compliant routines.  */
 938
 939 static void
 940 expand_complex_libcall (gimple_stmt_iterator *gsi, tree ar, tree ai,
 941                         tree br, tree bi, enum tree_code code)
 942 {
 943   enum machine_mode mode;
 944   enum built_in_function bcode;
 945   tree fn, type, lhs;
 946   gimple old_stmt, stmt;
 947
 948   old_stmt = gsi_stmt (*gsi);
 949   lhs = gimple_assign_lhs (old_stmt);
 950   type = TREE_TYPE (lhs);
 951
 952   mode = TYPE_MODE (type);
 953   gcc_assert (GET_MODE_CLASS (mode) == MODE_COMPLEX_FLOAT);
 954
 955   if (code == MULT_EXPR)
 956     bcode = ((enum built_in_function)
 957              (BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT));
 958   else if (code == RDIV_EXPR)
 959     bcode = ((enum built_in_function)
 960              (BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT));
 961   else
 962     gcc_unreachable ();
 963   fn = built_in_decls[bcode];
 964
 965   stmt = gimple_build_call (fn, 4, ar, ai, br, bi);
 966   gimple_call_set_lhs (stmt, lhs);
 967   update_stmt (stmt);
 968   gsi_replace (gsi, stmt, false);
 969
 970   if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
 971     gimple_purge_dead_eh_edges (gsi_bb (*gsi));
 972
 973   if (gimple_in_ssa_p (cfun))
 974     {
 975       type = TREE_TYPE (type);
 976       update_complex_components (gsi, stmt,
 977                                  build1 (REALPART_EXPR, type, lhs),
 978                                  build1 (IMAGPART_EXPR, type, lhs));
 979       SSA_NAME_DEF_STMT (lhs) = stmt;
 980     }
 981 }
 982
 983 /* Expand complex multiplication to scalars:
 984         a * b = (ar*br - ai*bi) + i(ar*bi + br*ai)
 985 */
 986
 987 static void
 988 expand_complex_multiplication (gimple_stmt_iterator *gsi, tree inner_type,
 989                                tree ar, tree ai, tree br, tree bi,
 990                                complex_lattice_t al, complex_lattice_t bl)
 991 {
 992   tree rr, ri;
 993
 994   if (al < bl)
 995     {
 996       complex_lattice_t tl;
 997       rr = ar, ar = br, br = rr;
 998       ri = ai, ai = bi, bi = ri;
 999       tl = al, al = bl, bl = tl;
1000     }
1001
1002   switch (PAIR (al, bl))
1003     {
1004     case PAIR (ONLY_REAL, ONLY_REAL):
1005       rr = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, br);
1006       ri = ai;
1007       break;
1008
1009     case PAIR (ONLY_IMAG, ONLY_REAL):
1010       rr = ar;
1011       if (TREE_CODE (ai) == REAL_CST
1012           && REAL_VALUES_IDENTICAL (TREE_REAL_CST (ai), dconst1))
1013         ri = br;
1014       else
1015         ri = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, br);
1016       break;
1017
1018     case PAIR (ONLY_IMAG, ONLY_IMAG):
1019       rr = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, bi);
1020       rr = gimplify_build1 (gsi, NEGATE_EXPR, inner_type, rr);
1021       ri = ar;
1022       break;
1023
1024     case PAIR (VARYING, ONLY_REAL):
1025       rr = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, br);
1026       ri = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, br);
1027       break;
1028
1029     case PAIR (VARYING, ONLY_IMAG):
1030       rr = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, bi);
1031       rr = gimplify_build1 (gsi, NEGATE_EXPR, inner_type, rr);
1032       ri = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, bi);
1033       break;
1034
1035     case PAIR (VARYING, VARYING):
1036       if (flag_complex_method == 2 && SCALAR_FLOAT_TYPE_P (inner_type))
1037         {
1038           expand_complex_libcall (gsi, ar, ai, br, bi, MULT_EXPR);
1039           return;
1040         }
1041       else
1042         {
1043           tree t1, t2, t3, t4;
1044
1045           t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, br);
1046           t2 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, bi);
1047           t3 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, bi);
1048
1049           /* Avoid expanding redundant multiplication for the common
1050              case of squaring a complex number.  */
1051           if (ar == br && ai == bi)
1052             t4 = t3;
1053           else
1054             t4 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, br);
1055
1056           rr = gimplify_build2 (gsi, MINUS_EXPR, inner_type, t1, t2);
1057           ri = gimplify_build2 (gsi, PLUS_EXPR, inner_type, t3, t4);
1058         }
1059       break;
1060
1061     default:
1062       gcc_unreachable ();
1063     }
1064
1065   update_complex_assignment (gsi, rr, ri);
1066 }
1067
1068 /* Keep this algorithm in sync with fold-const.c:const_binop().
1069
1070    Expand complex division to scalars, straightforward algorithm.
1071         a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
1072             t = br*br + bi*bi
1073 */
1074
1075 static void
1076 expand_complex_div_straight (gimple_stmt_iterator *gsi, tree inner_type,
1077                              tree ar, tree ai, tree br, tree bi,
1078                              enum tree_code code)
1079 {
1080   tree rr, ri, div, t1, t2, t3;
1081
1082   t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, br, br);
1083   t2 = gimplify_build2 (gsi, MULT_EXPR, inner_type, bi, bi);
1084   div = gimplify_build2 (gsi, PLUS_EXPR, inner_type, t1, t2);
1085
1086   t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, br);
1087   t2 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, bi);
1088   t3 = gimplify_build2 (gsi, PLUS_EXPR, inner_type, t1, t2);
1089   rr = gimplify_build2 (gsi, code, inner_type, t3, div);
1090
1091   t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, br);
1092   t2 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, bi);
1093   t3 = gimplify_build2 (gsi, MINUS_EXPR, inner_type, t1, t2);
1094   ri = gimplify_build2 (gsi, code, inner_type, t3, div);
1095
1096   update_complex_assignment (gsi, rr, ri);
1097 }
1098
1099 /* Keep this algorithm in sync with fold-const.c:const_binop().
1100
1101    Expand complex division to scalars, modified algorithm to minimize
1102    overflow with wide input ranges.  */
1103
1104 static void
1105 expand_complex_div_wide (gimple_stmt_iterator *gsi, tree inner_type,
1106                          tree ar, tree ai, tree br, tree bi,
1107                          enum tree_code code)
1108 {
1109   tree rr, ri, ratio, div, t1, t2, tr, ti, compare;
1110   basic_block bb_cond, bb_true, bb_false, bb_join;
1111   gimple stmt;
1112
1113   /* Examine |br| < |bi|, and branch.  */
1114   t1 = gimplify_build1 (gsi, ABS_EXPR, inner_type, br);
1115   t2 = gimplify_build1 (gsi, ABS_EXPR, inner_type, bi);
1116   compare = fold_build2_loc (gimple_location (gsi_stmt (*gsi)),
1117                          LT_EXPR, boolean_type_node, t1, t2);
1118   STRIP_NOPS (compare);
1119
1120   bb_cond = bb_true = bb_false = bb_join = NULL;
1121   rr = ri = tr = ti = NULL;
1122   if (!TREE_CONSTANT (compare))
1123     {
1124       edge e;
1125       gimple stmt;
1126       tree cond, tmp;
1127
1128       tmp = create_tmp_var (boolean_type_node, NULL);
1129       stmt = gimple_build_assign (tmp, compare);
1130       if (gimple_in_ssa_p (cfun))
1131         {
1132           tmp = make_ssa_name (tmp,  stmt);
1133           gimple_assign_set_lhs (stmt, tmp);
1134         }
1135
1136       gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1137
1138       cond = fold_build2_loc (gimple_location (stmt),
1139                           EQ_EXPR, boolean_type_node, tmp, boolean_true_node);
1140       stmt = gimple_build_cond_from_tree (cond, NULL_TREE, NULL_TREE);
1141       gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1142
1143       /* Split the original block, and create the TRUE and FALSE blocks.  */
1144       e = split_block (gsi_bb (*gsi), stmt);
1145       bb_cond = e->src;
1146       bb_join = e->dest;
1147       bb_true = create_empty_bb (bb_cond);
1148       bb_false = create_empty_bb (bb_true);
1149
1150       /* Wire the blocks together.  */
1151       e->flags = EDGE_TRUE_VALUE;
1152       redirect_edge_succ (e, bb_true);
1153       make_edge (bb_cond, bb_false, EDGE_FALSE_VALUE);
1154       make_edge (bb_true, bb_join, EDGE_FALLTHRU);
1155       make_edge (bb_false, bb_join, EDGE_FALLTHRU);
1156
1157       /* Update dominance info.  Note that bb_join's data was
1158          updated by split_block.  */
1159       if (dom_info_available_p (CDI_DOMINATORS))
1160         {
1161           set_immediate_dominator (CDI_DOMINATORS, bb_true, bb_cond);
1162           set_immediate_dominator (CDI_DOMINATORS, bb_false, bb_cond);
1163         }
1164
1165       rr = make_rename_temp (inner_type, NULL);
1166       ri = make_rename_temp (inner_type, NULL);
1167     }
1168
1169   /* In the TRUE branch, we compute
1170       ratio = br/bi;
1171       div = (br * ratio) + bi;
1172       tr = (ar * ratio) + ai;
1173       ti = (ai * ratio) - ar;
1174       tr = tr / div;
1175       ti = ti / div;  */
1176   if (bb_true || integer_nonzerop (compare))
1177     {
1178       if (bb_true)
1179         {
1180           *gsi = gsi_last_bb (bb_true);
1181           gsi_insert_after (gsi, gimple_build_nop (), GSI_NEW_STMT);
1182         }
1183
1184       ratio = gimplify_build2 (gsi, code, inner_type, br, bi);
1185
1186       t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, br, ratio);
1187       div = gimplify_build2 (gsi, PLUS_EXPR, inner_type, t1, bi);
1188
1189       t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, ratio);
1190       tr = gimplify_build2 (gsi, PLUS_EXPR, inner_type, t1, ai);
1191
1192       t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, ratio);
1193       ti = gimplify_build2 (gsi, MINUS_EXPR, inner_type, t1, ar);
1194
1195       tr = gimplify_build2 (gsi, code, inner_type, tr, div);
1196       ti = gimplify_build2 (gsi, code, inner_type, ti, div);
1197
1198      if (bb_true)
1199        {
1200          stmt = gimple_build_assign (rr, tr);
1201          gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1202          stmt = gimple_build_assign (ri, ti);
1203          gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1204          gsi_remove (gsi, true);
1205        }
1206     }
1207
1208   /* In the FALSE branch, we compute
1209       ratio = d/c;
1210       divisor = (d * ratio) + c;
1211       tr = (b * ratio) + a;
1212       ti = b - (a * ratio);
1213       tr = tr / div;
1214       ti = ti / div;  */
1215   if (bb_false || integer_zerop (compare))
1216     {
1217       if (bb_false)
1218         {
1219           *gsi = gsi_last_bb (bb_false);
1220           gsi_insert_after (gsi, gimple_build_nop (), GSI_NEW_STMT);
1221         }
1222
1223       ratio = gimplify_build2 (gsi, code, inner_type, bi, br);
1224
1225       t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, bi, ratio);
1226       div = gimplify_build2 (gsi, PLUS_EXPR, inner_type, t1, br);
1227
1228       t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ai, ratio);
1229       tr = gimplify_build2 (gsi, PLUS_EXPR, inner_type, t1, ar);
1230
1231       t1 = gimplify_build2 (gsi, MULT_EXPR, inner_type, ar, ratio);
1232       ti = gimplify_build2 (gsi, MINUS_EXPR, inner_type, ai, t1);
1233
1234       tr = gimplify_build2 (gsi, code, inner_type, tr, div);
1235       ti = gimplify_build2 (gsi, code, inner_type, ti, div);
1236
1237      if (bb_false)
1238        {
1239          stmt = gimple_build_assign (rr, tr);
1240          gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1241          stmt = gimple_build_assign (ri, ti);
1242          gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1243          gsi_remove (gsi, true);
1244        }
1245     }
1246
1247   if (bb_join)
1248     *gsi = gsi_start_bb (bb_join);
1249   else
1250     rr = tr, ri = ti;
1251
1252   update_complex_assignment (gsi, rr, ri);
1253 }
1254
1255 /* Expand complex division to scalars.  */
1256
1257 static void
1258 expand_complex_division (gimple_stmt_iterator *gsi, tree inner_type,
1259                          tree ar, tree ai, tree br, tree bi,
1260                          enum tree_code code,
1261                          complex_lattice_t al, complex_lattice_t bl)
1262 {
1263   tree rr, ri;
1264
1265   switch (PAIR (al, bl))
1266     {
1267     case PAIR (ONLY_REAL, ONLY_REAL):
1268       rr = gimplify_build2 (gsi, code, inner_type, ar, br);
1269       ri = ai;
1270       break;
1271
1272     case PAIR (ONLY_REAL, ONLY_IMAG):
1273       rr = ai;
1274       ri = gimplify_build2 (gsi, code, inner_type, ar, bi);
1275       ri = gimplify_build1 (gsi, NEGATE_EXPR, inner_type, ri);
1276       break;
1277
1278     case PAIR (ONLY_IMAG, ONLY_REAL):
1279       rr = ar;
1280       ri = gimplify_build2 (gsi, code, inner_type, ai, br);
1281       break;
1282
1283     case PAIR (ONLY_IMAG, ONLY_IMAG):
1284       rr = gimplify_build2 (gsi, code, inner_type, ai, bi);
1285       ri = ar;
1286       break;
1287
1288     case PAIR (VARYING, ONLY_REAL):
1289       rr = gimplify_build2 (gsi, code, inner_type, ar, br);
1290       ri = gimplify_build2 (gsi, code, inner_type, ai, br);
1291       break;
1292
1293     case PAIR (VARYING, ONLY_IMAG):
1294       rr = gimplify_build2 (gsi, code, inner_type, ai, bi);
1295       ri = gimplify_build2 (gsi, code, inner_type, ar, bi);
1296       ri = gimplify_build1 (gsi, NEGATE_EXPR, inner_type, ri);
1297
1298     case PAIR (ONLY_REAL, VARYING):
1299     case PAIR (ONLY_IMAG, VARYING):
1300     case PAIR (VARYING, VARYING):
1301       switch (flag_complex_method)
1302         {
1303         case 0:
1304           /* straightforward implementation of complex divide acceptable.  */
1305           expand_complex_div_straight (gsi, inner_type, ar, ai, br, bi, code);
1306           break;
1307
1308         case 2:
1309           if (SCALAR_FLOAT_TYPE_P (inner_type))
1310             {
1311               expand_complex_libcall (gsi, ar, ai, br, bi, code);
1312               break;
1313             }
1314           /* FALLTHRU */
1315
1316         case 1:
1317           /* wide ranges of inputs must work for complex divide.  */
1318           expand_complex_div_wide (gsi, inner_type, ar, ai, br, bi, code);
1319           break;
1320
1321         default:
1322           gcc_unreachable ();
1323         }
1324       return;
1325
1326     default:
1327       gcc_unreachable ();
1328     }
1329
1330   update_complex_assignment (gsi, rr, ri);
1331 }
1332
1333 /* Expand complex negation to scalars:
1334         -a = (-ar) + i(-ai)
1335 */
1336
1337 static void
1338 expand_complex_negation (gimple_stmt_iterator *gsi, tree inner_type,
1339                          tree ar, tree ai)
1340 {
1341   tree rr, ri;
1342
1343   rr = gimplify_build1 (gsi, NEGATE_EXPR, inner_type, ar);
1344   ri = gimplify_build1 (gsi, NEGATE_EXPR, inner_type, ai);
1345
1346   update_complex_assignment (gsi, rr, ri);
1347 }
1348
1349 /* Expand complex conjugate to scalars:
1350         ~a = (ar) + i(-ai)
1351 */
1352
1353 static void
1354 expand_complex_conjugate (gimple_stmt_iterator *gsi, tree inner_type,
1355                           tree ar, tree ai)
1356 {
1357   tree ri;
1358
1359   ri = gimplify_build1 (gsi, NEGATE_EXPR, inner_type, ai);
1360
1361   update_complex_assignment (gsi, ar, ri);
1362 }
1363
1364 /* Expand complex comparison (EQ or NE only).  */
1365
1366 static void
1367 expand_complex_comparison (gimple_stmt_iterator *gsi, tree ar, tree ai,
1368                            tree br, tree bi, enum tree_code code)
1369 {
1370   tree cr, ci, cc, type;
1371   gimple stmt;
1372
1373   cr = gimplify_build2 (gsi, code, boolean_type_node, ar, br);
1374   ci = gimplify_build2 (gsi, code, boolean_type_node, ai, bi);
1375   cc = gimplify_build2 (gsi,
1376                         (code == EQ_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR),
1377                         boolean_type_node, cr, ci);
1378
1379   stmt = gsi_stmt (*gsi);
1380
1381   switch (gimple_code (stmt))
1382     {
1383     case GIMPLE_RETURN:
1384       type = TREE_TYPE (gimple_return_retval (stmt));
1385       gimple_return_set_retval (stmt, fold_convert (type, cc));
1386       break;
1387
1388     case GIMPLE_ASSIGN:
1389       type = TREE_TYPE (gimple_assign_lhs (stmt));
1390       gimple_assign_set_rhs_from_tree (gsi, fold_convert (type, cc));
1391       stmt = gsi_stmt (*gsi);
1392       break;
1393
1394     case GIMPLE_COND:
1395       gimple_cond_set_code (stmt, EQ_EXPR);
1396       gimple_cond_set_lhs (stmt, cc);
1397       gimple_cond_set_rhs (stmt, boolean_true_node);
1398       break;
1399
1400     default:
1401       gcc_unreachable ();
1402     }
1403
1404   update_stmt (stmt);
1405 }
1406
1407
1408 /* Process one statement.  If we identify a complex operation, expand it.  */
1409
1410 static void
1411 expand_complex_operations_1 (gimple_stmt_iterator *gsi)
1412 {
1413   gimple stmt = gsi_stmt (*gsi);
1414   tree type, inner_type, lhs;
1415   tree ac, ar, ai, bc, br, bi;
1416   complex_lattice_t al, bl;
1417   enum tree_code code;
1418
1419   lhs = gimple_get_lhs (stmt);
1420   if (!lhs && gimple_code (stmt) != GIMPLE_COND)
1421     return;
1422
1423   type = TREE_TYPE (gimple_op (stmt, 0));
1424   code = gimple_expr_code (stmt);
1425
1426   /* Initial filter for operations we handle.  */
1427   switch (code)
1428     {
1429     case PLUS_EXPR:
1430     case MINUS_EXPR:
1431     case MULT_EXPR:
1432     case TRUNC_DIV_EXPR:
1433     case CEIL_DIV_EXPR:
1434     case FLOOR_DIV_EXPR:
1435     case ROUND_DIV_EXPR:
1436     case RDIV_EXPR:
1437     case NEGATE_EXPR:
1438     case CONJ_EXPR:
1439       if (TREE_CODE (type) != COMPLEX_TYPE)
1440         return;
1441       inner_type = TREE_TYPE (type);
1442       break;
1443
1444     case EQ_EXPR:
1445     case NE_EXPR:
1446       /* Note, both GIMPLE_ASSIGN and GIMPLE_COND may have an EQ_EXPR
1447          subocde, so we need to access the operands using gimple_op.  */
1448       inner_type = TREE_TYPE (gimple_op (stmt, 1));
1449       if (TREE_CODE (inner_type) != COMPLEX_TYPE)
1450         return;
1451       break;
1452
1453     default:
1454       {
1455         tree rhs;
1456
1457         /* GIMPLE_COND may also fallthru here, but we do not need to
1458            do anything with it.  */
1459         if (gimple_code (stmt) == GIMPLE_COND)
1460           return;
1461
1462         if (TREE_CODE (type) == COMPLEX_TYPE)
1463           expand_complex_move (gsi, type);
1464         else if (is_gimple_assign (stmt)
1465                  && (gimple_assign_rhs_code (stmt) == REALPART_EXPR
1466                      || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR)
1467                  && TREE_CODE (lhs) == SSA_NAME)
1468           {
1469             rhs = gimple_assign_rhs1 (stmt);
1470             rhs = extract_component (gsi, TREE_OPERAND (rhs, 0),
1471                                      gimple_assign_rhs_code (stmt)
1472                                        == IMAGPART_EXPR,
1473                                      false);
1474             gimple_assign_set_rhs_from_tree (gsi, rhs);
1475             stmt = gsi_stmt (*gsi);
1476             update_stmt (stmt);
1477           }
1478       }
1479       return;
1480     }
1481
1482   /* Extract the components of the two complex values.  Make sure and
1483      handle the common case of the same value used twice specially.  */
1484   if (is_gimple_assign (stmt))
1485     {
1486       ac = gimple_assign_rhs1 (stmt);
1487       bc = (gimple_num_ops (stmt) > 2) ? gimple_assign_rhs2 (stmt) : NULL;
1488     }
1489   /* GIMPLE_CALL can not get here.  */
1490   else
1491     {
1492       ac = gimple_cond_lhs (stmt);
1493       bc = gimple_cond_rhs (stmt);
1494     }
1495
1496   ar = extract_component (gsi, ac, false, true);
1497   ai = extract_component (gsi, ac, true, true);
1498
1499   if (ac == bc)
1500     br = ar, bi = ai;
1501   else if (bc)
1502     {
1503       br = extract_component (gsi, bc, 0, true);
1504       bi = extract_component (gsi, bc, 1, true);
1505     }
1506   else
1507     br = bi = NULL_TREE;
1508
1509   if (gimple_in_ssa_p (cfun))
1510     {
1511       al = find_lattice_value (ac);
1512       if (al == UNINITIALIZED)
1513         al = VARYING;
1514
1515       if (TREE_CODE_CLASS (code) == tcc_unary)
1516         bl = UNINITIALIZED;
1517       else if (ac == bc)
1518         bl = al;
1519       else
1520         {
1521           bl = find_lattice_value (bc);
1522           if (bl == UNINITIALIZED)
1523             bl = VARYING;
1524         }
1525     }
1526   else
1527     al = bl = VARYING;
1528
1529   switch (code)
1530     {
1531     case PLUS_EXPR:
1532     case MINUS_EXPR:
1533       expand_complex_addition (gsi, inner_type, ar, ai, br, bi, code, al, bl);
1534       break;
1535
1536     case MULT_EXPR:
1537       expand_complex_multiplication (gsi, inner_type, ar, ai, br, bi, al, bl);
1538       break;
1539
1540     case TRUNC_DIV_EXPR:
1541     case CEIL_DIV_EXPR:
1542     case FLOOR_DIV_EXPR:
1543     case ROUND_DIV_EXPR:
1544     case RDIV_EXPR:
1545       expand_complex_division (gsi, inner_type, ar, ai, br, bi, code, al, bl);
1546       break;
1547
1548     case NEGATE_EXPR:
1549       expand_complex_negation (gsi, inner_type, ar, ai);
1550       break;
1551
1552     case CONJ_EXPR:
1553       expand_complex_conjugate (gsi, inner_type, ar, ai);
1554       break;
1555
1556     case EQ_EXPR:
1557     case NE_EXPR:
1558       expand_complex_comparison (gsi, ar, ai, br, bi, code);
1559       break;
1560
1561     default:
1562       gcc_unreachable ();
1563     }
1564 }
1565
1566 \f
1567 /* Entry point for complex operation lowering during optimization.  */
1568
1569 static unsigned int
1570 tree_lower_complex (void)
1571 {
1572   int old_last_basic_block;
1573   gimple_stmt_iterator gsi;
1574   basic_block bb;
1575
1576   if (!init_dont_simulate_again ())
1577     return 0;
1578
1579   complex_lattice_values = VEC_alloc (complex_lattice_t, heap, num_ssa_names);
1580   VEC_safe_grow_cleared (complex_lattice_t, heap,
1581                          complex_lattice_values, num_ssa_names);
1582
1583   init_parameter_lattice_values ();
1584   ssa_propagate (complex_visit_stmt, complex_visit_phi);
1585
1586   complex_variable_components = htab_create (10,  int_tree_map_hash,
1587                                              int_tree_map_eq, free);
1588
1589   complex_ssa_name_components = VEC_alloc (tree, heap, 2*num_ssa_names);
1590   VEC_safe_grow_cleared (tree, heap, complex_ssa_name_components,
1591                          2 * num_ssa_names);
1592
1593   update_parameter_components ();
1594
1595   /* ??? Ideally we'd traverse the blocks in breadth-first order.  */
1596   old_last_basic_block = last_basic_block;
1597   FOR_EACH_BB (bb)
1598     {
1599       if (bb->index >= old_last_basic_block)
1600         continue;
1601
1602       update_phi_components (bb);
1603       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1604         expand_complex_operations_1 (&gsi);
1605     }
1606
1607   gsi_commit_edge_inserts ();
1608
1609   htab_delete (complex_variable_components);
1610   VEC_free (tree, heap, complex_ssa_name_components);
1611   VEC_free (complex_lattice_t, heap, complex_lattice_values);
1612   return 0;
1613 }
1614
1615 struct gimple_opt_pass pass_lower_complex =
1616 {
1617  {
1618   GIMPLE_PASS,
1619   "cplxlower",                          /* name */
1620   0,                                    /* gate */
1621   tree_lower_complex,                   /* execute */
1622   NULL,                                 /* sub */
1623   NULL,                                 /* next */
1624   0,                                    /* static_pass_number */
1625   TV_NONE,                              /* tv_id */
1626   PROP_ssa,                             /* properties_required */
1627   0,                                    /* properties_provided */
1628   0,                                    /* properties_destroyed */
1629   0,                                    /* todo_flags_start */
1630   TODO_dump_func
1631     | TODO_ggc_collect
1632     | TODO_update_ssa
1633     | TODO_verify_stmts                 /* todo_flags_finish */
1634  }
1635 };
1636
1637 \f
1638 /* Entry point for complex operation lowering without optimization.  */
1639
1640 static unsigned int
1641 tree_lower_complex_O0 (void)
1642 {
1643   int old_last_basic_block = last_basic_block;
1644   gimple_stmt_iterator gsi;
1645   basic_block bb;
1646
1647   FOR_EACH_BB (bb)
1648     {
1649       if (bb->index >= old_last_basic_block)
1650         continue;
1651
1652       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1653         expand_complex_operations_1 (&gsi);
1654     }
1655   return 0;
1656 }
1657
1658 static bool
1659 gate_no_optimization (void)
1660 {
1661   /* With errors, normal optimization passes are not run.  If we don't
1662      lower complex operations at all, rtl expansion will abort.  */
1663   return optimize == 0 || sorrycount || errorcount;
1664 }
1665
1666 struct gimple_opt_pass pass_lower_complex_O0 =
1667 {
1668  {
1669   GIMPLE_PASS,
1670   "cplxlower0",                         /* name */
1671   gate_no_optimization,                 /* gate */
1672   tree_lower_complex_O0,                /* execute */
1673   NULL,                                 /* sub */
1674   NULL,                                 /* next */
1675   0,                                    /* static_pass_number */
1676   TV_NONE,                              /* tv_id */
1677   PROP_cfg,                             /* properties_required */
1678   0,                                    /* properties_provided */
1679   0,                                    /* properties_destroyed */
1680   0,                                    /* todo_flags_start */
1681   TODO_dump_func | TODO_ggc_collect
1682     | TODO_verify_stmts,                /* todo_flags_finish */
1683  }
1684 };