Subversion Repositories openrisc

/* Lower complex number operations to scalar operations.

   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010

   Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it

under the terms of the GNU General Public License as published by the

Free Software Foundation; either version 3, or (at your option) any

later version.

GCC is distributed in the hope that it will be useful, but WITHOUT

ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "flags.h"

#include "tree-flow.h"

#include "gimple.h"

#include "tree-iterator.h"

#include "tree-pass.h"

#include "tree-ssa-propagate.h"

/* For each complex ssa name, a lattice value.  We're interested in finding

   out whether a complex number is degenerate in some way, having only real

   or only complex parts.  */

enum

{

  UNINITIALIZED = 0,

  ONLY_REAL = 1,

  ONLY_IMAG = 2,

  VARYING = 3

};

/* The type complex_lattice_t holds combinations of the above

   constants.  */

typedef int complex_lattice_t;

#define PAIR(a, b)  ((a) << 2 | (b))

DEF_VEC_I(complex_lattice_t);

DEF_VEC_ALLOC_I(complex_lattice_t, heap);

static VEC(complex_lattice_t, heap) *complex_lattice_values;

/* For each complex variable, a pair of variables for the components exists in

   the hashtable.  */

static htab_t complex_variable_components;

/* For each complex SSA_NAME, a pair of ssa names for the components.  */

static VEC(tree, heap) *complex_ssa_name_components;

/* Lookup UID in the complex_variable_components hashtable and return the

   associated tree.  */

static tree

cvc_lookup (unsigned int uid)

{

  struct int_tree_map *h, in;

  in.uid = uid;

  h = (struct int_tree_map *) htab_find_with_hash (complex_variable_components, &in, uid);

  return h ? h->to : NULL;

}

/* Insert the pair UID, TO into the complex_variable_components hashtable.  */

static void

cvc_insert (unsigned int uid, tree to)

{

  struct int_tree_map *h;

  void **loc;

  h = XNEW (struct int_tree_map);

  h->uid = uid;

  h->to = to;

  loc = htab_find_slot_with_hash (complex_variable_components, h,

                                  uid, INSERT);

  *(struct int_tree_map **) loc = h;

}

/* Return true if T is not a zero constant.  In the case of real values,

   we're only interested in +0.0.  */

static int

some_nonzerop (tree t)

{

  int zerop = false;

  /* Operations with real or imaginary part of a complex number zero

     cannot be treated the same as operations with a real or imaginary

     operand if we care about the signs of zeros in the result.  */

  if (TREE_CODE (t) == REAL_CST && !flag_signed_zeros)

    zerop = REAL_VALUES_IDENTICAL (TREE_REAL_CST (t), dconst0);

  else if (TREE_CODE (t) == FIXED_CST)

    zerop = fixed_zerop (t);

  else if (TREE_CODE (t) == INTEGER_CST)

    zerop = integer_zerop (t);

  return !zerop;

}

/* Compute a lattice value from the components of a complex type REAL

   and IMAG.  */

static complex_lattice_t

find_lattice_value_parts (tree real, tree imag)

{

  int r, i;

  complex_lattice_t ret;

  r = some_nonzerop (real);

  i = some_nonzerop (imag);

  ret = r * ONLY_REAL + i * ONLY_IMAG;

  /* ??? On occasion we could do better than mapping 0+0i to real, but we

     certainly don't want to leave it UNINITIALIZED, which eventually gets

     mapped to VARYING.  */

  if (ret == UNINITIALIZED)

    ret = ONLY_REAL;

  return ret;

}

/* Compute a lattice value from gimple_val T.  */

static complex_lattice_t

find_lattice_value (tree t)

{

  tree real, imag;

  switch (TREE_CODE (t))

    {

    case SSA_NAME:

      return VEC_index (complex_lattice_t, complex_lattice_values,

                        SSA_NAME_VERSION (t));

    case COMPLEX_CST:

      real = TREE_REALPART (t);

      imag = TREE_IMAGPART (t);

      break;

    default:

      gcc_unreachable ();

    }

  return find_lattice_value_parts (real, imag);

}

/* Determine if LHS is something for which we're interested in seeing

   simulation results.  */

static bool

is_complex_reg (tree lhs)

{

  return TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE && is_gimple_reg (lhs);

}

/* Mark the incoming parameters to the function as VARYING.  */

static void

init_parameter_lattice_values (void)

{

  tree parm, ssa_name;

  for (parm = DECL_ARGUMENTS (cfun->decl); parm ; parm = DECL_CHAIN (parm))

    if (is_complex_reg (parm)

        && var_ann (parm) != NULL

        && (ssa_name = gimple_default_def (cfun, parm)) != NULL_TREE)

      VEC_replace (complex_lattice_t, complex_lattice_values,

                   SSA_NAME_VERSION (ssa_name), VARYING);

}

/* Initialize simulation state for each statement.  Return false if we

   found no statements we want to simulate, and thus there's nothing

   for the entire pass to do.  */

static bool

init_dont_simulate_again (void)

{

  basic_block bb;

  gimple_stmt_iterator gsi;

  gimple phi;

  bool saw_a_complex_op = false;

  FOR_EACH_BB (bb)

    {

      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))

        {

          phi = gsi_stmt (gsi);

          prop_set_simulate_again (phi,

                                   is_complex_reg (gimple_phi_result (phi)));

        }

      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))

        {

          gimple stmt;

          tree op0, op1;

          bool sim_again_p;

          stmt = gsi_stmt (gsi);

          op0 = op1 = NULL_TREE;

          /* Most control-altering statements must be initially

             simulated, else we won't cover the entire cfg.  */

          sim_again_p = stmt_ends_bb_p (stmt);

          switch (gimple_code (stmt))

            {

            case GIMPLE_CALL:

              if (gimple_call_lhs (stmt))

                sim_again_p = is_complex_reg (gimple_call_lhs (stmt));

              break;

            case GIMPLE_ASSIGN:

              sim_again_p = is_complex_reg (gimple_assign_lhs (stmt));

              if (gimple_assign_rhs_code (stmt) == REALPART_EXPR

                  || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR)

                op0 = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);

              else

                op0 = gimple_assign_rhs1 (stmt);

              if (gimple_num_ops (stmt) > 2)

                op1 = gimple_assign_rhs2 (stmt);

              break;

            case GIMPLE_COND:

              op0 = gimple_cond_lhs (stmt);

              op1 = gimple_cond_rhs (stmt);

              break;

            default:

              break;

            }

          if (op0 || op1)

            switch (gimple_expr_code (stmt))

              {

              case EQ_EXPR:

              case NE_EXPR:

              case PLUS_EXPR:

              case MINUS_EXPR:

              case MULT_EXPR:

              case TRUNC_DIV_EXPR:

              case CEIL_DIV_EXPR:

              case FLOOR_DIV_EXPR:

              case ROUND_DIV_EXPR:

              case RDIV_EXPR:

                if (TREE_CODE (TREE_TYPE (op0)) == COMPLEX_TYPE

                    || TREE_CODE (TREE_TYPE (op1)) == COMPLEX_TYPE)

                  saw_a_complex_op = true;

                break;

              case NEGATE_EXPR:

              case CONJ_EXPR:

                if (TREE_CODE (TREE_TYPE (op0)) == COMPLEX_TYPE)

                  saw_a_complex_op = true;

                break;

              case REALPART_EXPR:

              case IMAGPART_EXPR:

                /* The total store transformation performed during

                  gimplification creates such uninitialized loads

                  and we need to lower the statement to be able

                  to fix things up.  */

                if (TREE_CODE (op0) == SSA_NAME

                    && ssa_undefined_value_p (op0))

                  saw_a_complex_op = true;

                break;

              default:

                break;

              }

          prop_set_simulate_again (stmt, sim_again_p);

        }

    }

  return saw_a_complex_op;

}

/* Evaluate statement STMT against the complex lattice defined above.  */

static enum ssa_prop_result

complex_visit_stmt (gimple stmt, edge *taken_edge_p ATTRIBUTE_UNUSED,

                    tree *result_p)

{

  complex_lattice_t new_l, old_l, op1_l, op2_l;

  unsigned int ver;

  tree lhs;

  lhs = gimple_get_lhs (stmt);

  /* Skip anything but GIMPLE_ASSIGN and GIMPLE_CALL with a lhs.  */

  if (!lhs)

    return SSA_PROP_VARYING;

  /* These conditions should be satisfied due to the initial filter

     set up in init_dont_simulate_again.  */

  gcc_assert (TREE_CODE (lhs) == SSA_NAME);

  gcc_assert (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE);

  *result_p = lhs;

  ver = SSA_NAME_VERSION (lhs);

  old_l = VEC_index (complex_lattice_t, complex_lattice_values, ver);

  switch (gimple_expr_code (stmt))

    {

    case SSA_NAME:

    case COMPLEX_CST:

      new_l = find_lattice_value (gimple_assign_rhs1 (stmt));

      break;

    case COMPLEX_EXPR:

      new_l = find_lattice_value_parts (gimple_assign_rhs1 (stmt),

                                        gimple_assign_rhs2 (stmt));

      break;

    case PLUS_EXPR:

    case MINUS_EXPR:

      op1_l = find_lattice_value (gimple_assign_rhs1 (stmt));

      op2_l = find_lattice_value (gimple_assign_rhs2 (stmt));

      /* We've set up the lattice values such that IOR neatly

         models addition.  */

      new_l = op1_l | op2_l;

      break;

    case MULT_EXPR:

    case RDIV_EXPR:

    case TRUNC_DIV_EXPR:

    case CEIL_DIV_EXPR:

    case FLOOR_DIV_EXPR:

    case ROUND_DIV_EXPR:

      op1_l = find_lattice_value (gimple_assign_rhs1 (stmt));

      op2_l = find_lattice_value (gimple_assign_rhs2 (stmt));

      /* Obviously, if either varies, so does the result.  */

      if (op1_l == VARYING || op2_l == VARYING)

        new_l = VARYING;

      /* Don't prematurely promote variables if we've not yet seen

         their inputs.  */

      else if (op1_l == UNINITIALIZED)

        new_l = op2_l;

      else if (op2_l == UNINITIALIZED)

        new_l = op1_l;

      else

        {

          /* At this point both numbers have only one component. If the

             numbers are of opposite kind, the result is imaginary,

             otherwise the result is real. The add/subtract translates

             the real/imag from/to 0/1; the ^ performs the comparison.  */

          new_l = ((op1_l - ONLY_REAL) ^ (op2_l - ONLY_REAL)) + ONLY_REAL;

          /* Don't allow the lattice value to flip-flop indefinitely.  */

          new_l |= old_l;

        }

      break;

    case NEGATE_EXPR:

    case CONJ_EXPR:

      new_l = find_lattice_value (gimple_assign_rhs1 (stmt));

      break;

    default:

      new_l = VARYING;

      break;

    }

  /* If nothing changed this round, let the propagator know.  */

  if (new_l == old_l)

    return SSA_PROP_NOT_INTERESTING;

  VEC_replace (complex_lattice_t, complex_lattice_values, ver, new_l);

  return new_l == VARYING ? SSA_PROP_VARYING : SSA_PROP_INTERESTING;

}

/* Evaluate a PHI node against the complex lattice defined above.  */

static enum ssa_prop_result

complex_visit_phi (gimple phi)

{

  complex_lattice_t new_l, old_l;

  unsigned int ver;

  tree lhs;

  int i;

  lhs = gimple_phi_result (phi);

  /* This condition should be satisfied due to the initial filter

     set up in init_dont_simulate_again.  */

  gcc_assert (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE);

  /* We've set up the lattice values such that IOR neatly models PHI meet.  */

  new_l = UNINITIALIZED;

  for (i = gimple_phi_num_args (phi) - 1; i >= 0; --i)

    new_l |= find_lattice_value (gimple_phi_arg_def (phi, i));

  ver = SSA_NAME_VERSION (lhs);

  old_l = VEC_index (complex_lattice_t, complex_lattice_values, ver);

  if (new_l == old_l)

    return SSA_PROP_NOT_INTERESTING;

  VEC_replace (complex_lattice_t, complex_lattice_values, ver, new_l);

  return new_l == VARYING ? SSA_PROP_VARYING : SSA_PROP_INTERESTING;

}

/* Create one backing variable for a complex component of ORIG.  */

static tree

create_one_component_var (tree type, tree orig, const char *prefix,

                          const char *suffix, enum tree_code code)

{

  tree r = create_tmp_var (type, prefix);

  add_referenced_var (r);

  DECL_SOURCE_LOCATION (r) = DECL_SOURCE_LOCATION (orig);

  DECL_ARTIFICIAL (r) = 1;

  if (DECL_NAME (orig) && !DECL_IGNORED_P (orig))

    {

      const char *name = IDENTIFIER_POINTER (DECL_NAME (orig));

      DECL_NAME (r) = get_identifier (ACONCAT ((name, suffix, NULL)));

      SET_DECL_DEBUG_EXPR (r, build1 (code, type, orig));

      DECL_DEBUG_EXPR_IS_FROM (r) = 1;

      DECL_IGNORED_P (r) = 0;

      TREE_NO_WARNING (r) = TREE_NO_WARNING (orig);

    }

  else

    {

      DECL_IGNORED_P (r) = 1;

      TREE_NO_WARNING (r) = 1;

    }

  return r;

}

/* Retrieve a value for a complex component of VAR.  */

static tree

get_component_var (tree var, bool imag_p)

{

  size_t decl_index = DECL_UID (var) * 2 + imag_p;

  tree ret = cvc_lookup (decl_index);

  if (ret == NULL)

    {

      ret = create_one_component_var (TREE_TYPE (TREE_TYPE (var)), var,

                                      imag_p ? "CI" : "CR",

                                      imag_p ? "$imag" : "$real",

                                      imag_p ? IMAGPART_EXPR : REALPART_EXPR);

      cvc_insert (decl_index, ret);

    }

  return ret;

}

/* Retrieve a value for a complex component of SSA_NAME.  */

static tree

get_component_ssa_name (tree ssa_name, bool imag_p)

{

  complex_lattice_t lattice = find_lattice_value (ssa_name);

  size_t ssa_name_index;

  tree ret;

  if (lattice == (imag_p ? ONLY_REAL : ONLY_IMAG))

    {

      tree inner_type = TREE_TYPE (TREE_TYPE (ssa_name));

      if (SCALAR_FLOAT_TYPE_P (inner_type))

        return build_real (inner_type, dconst0);

      else

        return build_int_cst (inner_type, 0);

    }

  ssa_name_index = SSA_NAME_VERSION (ssa_name) * 2 + imag_p;

  ret = VEC_index (tree, complex_ssa_name_components, ssa_name_index);

  if (ret == NULL)

    {

      ret = get_component_var (SSA_NAME_VAR (ssa_name), imag_p);

      ret = make_ssa_name (ret, NULL);

      /* Copy some properties from the original.  In particular, whether it

         is used in an abnormal phi, and whether it's uninitialized.  */

      SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ret)

        = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name);

      if (TREE_CODE (SSA_NAME_VAR (ssa_name)) == VAR_DECL

          && gimple_nop_p (SSA_NAME_DEF_STMT (ssa_name)))

        {

          SSA_NAME_DEF_STMT (ret) = SSA_NAME_DEF_STMT (ssa_name);

          set_default_def (SSA_NAME_VAR (ret), ret);

        }

      VEC_replace (tree, complex_ssa_name_components, ssa_name_index, ret);

    }

  return ret;

}

/* Set a value for a complex component of SSA_NAME, return a

   gimple_seq of stuff that needs doing.  */

static gimple_seq

set_component_ssa_name (tree ssa_name, bool imag_p, tree value)

{

  complex_lattice_t lattice = find_lattice_value (ssa_name);

  size_t ssa_name_index;

  tree comp;

  gimple last;

  gimple_seq list;

  /* We know the value must be zero, else there's a bug in our lattice

     analysis.  But the value may well be a variable known to contain

     zero.  We should be safe ignoring it.  */

  if (lattice == (imag_p ? ONLY_REAL : ONLY_IMAG))

    return NULL;

  /* If we've already assigned an SSA_NAME to this component, then this

     means that our walk of the basic blocks found a use before the set.

     This is fine.  Now we should create an initialization for the value

     we created earlier.  */

  ssa_name_index = SSA_NAME_VERSION (ssa_name) * 2 + imag_p;

  comp = VEC_index (tree, complex_ssa_name_components, ssa_name_index);

  if (comp)

    ;

  /* If we've nothing assigned, and the value we're given is already stable,

     then install that as the value for this SSA_NAME.  This preemptively

     copy-propagates the value, which avoids unnecessary memory allocation.  */

  else if (is_gimple_min_invariant (value)

           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))

    {

      VEC_replace (tree, complex_ssa_name_components, ssa_name_index, value);

      return NULL;

    }

  else if (TREE_CODE (value) == SSA_NAME

           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))

    {

      /* Replace an anonymous base value with the variable from cvc_lookup.

         This should result in better debug info.  */

      if (DECL_IGNORED_P (SSA_NAME_VAR (value))

          && !DECL_IGNORED_P (SSA_NAME_VAR (ssa_name)))

        {

          comp = get_component_var (SSA_NAME_VAR (ssa_name), imag_p);

          replace_ssa_name_symbol (value, comp);

        }

      VEC_replace (tree, complex_ssa_name_components, ssa_name_index, value);

      return NULL;

    }

  /* Finally, we need to stabilize the result by installing the value into

     a new ssa name.  */

  else

    comp = get_component_ssa_name (ssa_name, imag_p);

  /* Do all the work to assign VALUE to COMP.  */

  list = NULL;

  value = force_gimple_operand (value, &list, false, NULL);

  last =  gimple_build_assign (comp, value);

  gimple_seq_add_stmt (&list, last);

  gcc_assert (SSA_NAME_DEF_STMT (comp) == last);

  return list;

}

/* Extract the real or imaginary part of a complex variable or constant.

   Make sure that it's a proper gimple_val and gimplify it if not.

   Emit any new code before gsi.  */

static tree

extract_component (gimple_stmt_iterator *gsi, tree t, bool imagpart_p,

                   bool gimple_p)

{

  switch (TREE_CODE (t))

    {

    case COMPLEX_CST:

      return imagpart_p ? TREE_IMAGPART (t) : TREE_REALPART (t);

    case COMPLEX_EXPR:

      gcc_unreachable ();

    case VAR_DECL:

    case RESULT_DECL:

    case PARM_DECL:

    case COMPONENT_REF:

    case ARRAY_REF:

    case VIEW_CONVERT_EXPR:

    case MEM_REF:

      {

        tree inner_type = TREE_TYPE (TREE_TYPE (t));

        t = build1 ((imagpart_p ? IMAGPART_EXPR : REALPART_EXPR),

                    inner_type, unshare_expr (t));

        if (gimple_p)

          t = force_gimple_operand_gsi (gsi, t, true, NULL, true,

                                        GSI_SAME_STMT);

        return t;

      }

    case SSA_NAME:

      return get_component_ssa_name (t, imagpart_p);

    default:

      gcc_unreachable ();

    }

}

/* Update the complex components of the ssa name on the lhs of STMT.  */

static void

update_complex_components (gimple_stmt_iterator *gsi, gimple stmt, tree r,

                           tree i)

{

  tree lhs;

  gimple_seq list;

  lhs = gimple_get_lhs (stmt);

  list = set_component_ssa_name (lhs, false, r);

  if (list)

    gsi_insert_seq_after (gsi, list, GSI_CONTINUE_LINKING);

  list = set_component_ssa_name (lhs, true, i);

  if (list)

    gsi_insert_seq_after (gsi, list, GSI_CONTINUE_LINKING);

}

static void

update_complex_components_on_edge (edge e, tree lhs, tree r, tree i)

{

  gimple_seq list;

  list = set_component_ssa_name (lhs, false, r);

  if (list)

    gsi_insert_seq_on_edge (e, list);

  list = set_component_ssa_name (lhs, true, i);

  if (list)

    gsi_insert_seq_on_edge (e, list);

}

/* Update an assignment to a complex variable in place.  */

static void

update_complex_assignment (gimple_stmt_iterator *gsi, tree r, tree i)

{

  gimple_stmt_iterator orig_si = *gsi;

  gimple stmt;

  if (gimple_in_ssa_p (cfun))

    update_complex_components (gsi, gsi_stmt (*gsi), r, i);

  gimple_assign_set_rhs_with_ops (&orig_si, COMPLEX_EXPR, r, i);

  stmt = gsi_stmt (orig_si);

  update_stmt (stmt);

  if (maybe_clean_eh_stmt (stmt))

    gimple_purge_dead_eh_edges (gimple_bb (stmt));

}

/* Generate code at the entry point of the function to initialize the

   component variables for a complex parameter.  */

static void

update_parameter_components (void)

{

  edge entry_edge = single_succ_edge (ENTRY_BLOCK_PTR);

  tree parm;

  for (parm = DECL_ARGUMENTS (cfun->decl); parm ; parm = DECL_CHAIN (parm))

    {

      tree type = TREE_TYPE (parm);

      tree ssa_name, r, i;

      if (TREE_CODE (type) != COMPLEX_TYPE || !is_gimple_reg (parm))

        continue;

      type = TREE_TYPE (type);

      ssa_name = gimple_default_def (cfun, parm);

      if (!ssa_name)

        continue;

      r = build1 (REALPART_EXPR, type, ssa_name);

      i = build1 (IMAGPART_EXPR, type, ssa_name);

      update_complex_components_on_edge (entry_edge, ssa_name, r, i);

    }

}

/* Generate code to set the component variables of a complex variable

   to match the PHI statements in block BB.  */