gcc/tree-complex.c

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