gcc/tree-complex.c

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