Subversion Repositories openrisc

/* Conditional constant propagation pass for the GNU compiler.

   Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,

   2010, 2011, 2012 Free Software Foundation, Inc.

   Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>

   Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>

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/>.  */

/* Conditional constant propagation (CCP) is based on the SSA

   propagation engine (tree-ssa-propagate.c).  Constant assignments of

   the form VAR = CST are propagated from the assignments into uses of

   VAR, which in turn may generate new constants.  The simulation uses

   a four level lattice to keep track of constant values associated

   with SSA names.  Given an SSA name V_i, it may take one of the

   following values:

        UNINITIALIZED   ->  the initial state of the value.  This value

                            is replaced with a correct initial value

                            the first time the value is used, so the

                            rest of the pass does not need to care about

                            it.  Using this value simplifies initialization

                            of the pass, and prevents us from needlessly

                            scanning statements that are never reached.

        UNDEFINED       ->  V_i is a local variable whose definition

                            has not been processed yet.  Therefore we

                            don't yet know if its value is a constant

                            or not.

        CONSTANT        ->  V_i has been found to hold a constant

                            value C.

        VARYING         ->  V_i cannot take a constant value, or if it

                            does, it is not possible to determine it

                            at compile time.

   The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:

   1- In ccp_visit_stmt, we are interested in assignments whose RHS

      evaluates into a constant and conditional jumps whose predicate

      evaluates into a boolean true or false.  When an assignment of

      the form V_i = CONST is found, V_i's lattice value is set to

      CONSTANT and CONST is associated with it.  This causes the

      propagation engine to add all the SSA edges coming out the

      assignment into the worklists, so that statements that use V_i

      can be visited.

      If the statement is a conditional with a constant predicate, we

      mark the outgoing edges as executable or not executable

      depending on the predicate's value.  This is then used when

      visiting PHI nodes to know when a PHI argument can be ignored.

   2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the

      same constant C, then the LHS of the PHI is set to C.  This

      evaluation is known as the "meet operation".  Since one of the

      goals of this evaluation is to optimistically return constant

      values as often as possible, it uses two main short cuts:

      - If an argument is flowing in through a non-executable edge, it

        is ignored.  This is useful in cases like this:

                        if (PRED)

                          a_9 = 3;

                        else

                          a_10 = 100;

                        a_11 = PHI (a_9, a_10)

        If PRED is known to always evaluate to false, then we can

        assume that a_11 will always take its value from a_10, meaning

        that instead of consider it VARYING (a_9 and a_10 have

        different values), we can consider it CONSTANT 100.

      - If an argument has an UNDEFINED value, then it does not affect

        the outcome of the meet operation.  If a variable V_i has an

        UNDEFINED value, it means that either its defining statement

        hasn't been visited yet or V_i has no defining statement, in

        which case the original symbol 'V' is being used

        uninitialized.  Since 'V' is a local variable, the compiler

        may assume any initial value for it.

   After propagation, every variable V_i that ends up with a lattice

   value of CONSTANT will have the associated constant value in the

   array CONST_VAL[i].VALUE.  That is fed into substitute_and_fold for

   final substitution and folding.

   References:

     Constant propagation with conditional branches,

     Wegman and Zadeck, ACM TOPLAS 13(2):181-210.

     Building an Optimizing Compiler,

     Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.

     Advanced Compiler Design and Implementation,

     Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "flags.h"

#include "tm_p.h"

#include "basic-block.h"

#include "output.h"

#include "function.h"

#include "tree-pretty-print.h"

#include "gimple-pretty-print.h"

#include "timevar.h"

#include "tree-dump.h"

#include "tree-flow.h"

#include "tree-pass.h"

#include "tree-ssa-propagate.h"

#include "value-prof.h"

#include "langhooks.h"

#include "target.h"

#include "diagnostic-core.h"

#include "dbgcnt.h"

#include "gimple-fold.h"

#include "params.h"

/* Possible lattice values.  */

typedef enum

{

  UNINITIALIZED,

  UNDEFINED,

  CONSTANT,

  VARYING

} ccp_lattice_t;

struct prop_value_d {

    /* Lattice value.  */

    ccp_lattice_t lattice_val;

    /* Propagated value.  */

    tree value;

    /* Mask that applies to the propagated value during CCP.  For

       X with a CONSTANT lattice value X & ~mask == value & ~mask.  */

    double_int mask;

};

typedef struct prop_value_d prop_value_t;

/* Array of propagated constant values.  After propagation,

   CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If

   the constant is held in an SSA name representing a memory store

   (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual

   memory reference used to store (i.e., the LHS of the assignment

   doing the store).  */

static prop_value_t *const_val;

static void canonicalize_float_value (prop_value_t *);

static bool ccp_fold_stmt (gimple_stmt_iterator *);

/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX.  */

static void

dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)

{

  switch (val.lattice_val)

    {

    case UNINITIALIZED:

      fprintf (outf, "%sUNINITIALIZED", prefix);

      break;

    case UNDEFINED:

      fprintf (outf, "%sUNDEFINED", prefix);

      break;

    case VARYING:

      fprintf (outf, "%sVARYING", prefix);

      break;

    case CONSTANT:

      fprintf (outf, "%sCONSTANT ", prefix);

      if (TREE_CODE (val.value) != INTEGER_CST

          || double_int_zero_p (val.mask))

        print_generic_expr (outf, val.value, dump_flags);

      else

        {

          double_int cval = double_int_and_not (tree_to_double_int (val.value),

                                                val.mask);

          fprintf (outf, "%sCONSTANT " HOST_WIDE_INT_PRINT_DOUBLE_HEX,

                   prefix, cval.high, cval.low);

          fprintf (outf, " (" HOST_WIDE_INT_PRINT_DOUBLE_HEX ")",

                   val.mask.high, val.mask.low);

        }

      break;

    default:

      gcc_unreachable ();

    }

}

/* Print lattice value VAL to stderr.  */

void debug_lattice_value (prop_value_t val);

DEBUG_FUNCTION void

debug_lattice_value (prop_value_t val)

{

  dump_lattice_value (stderr, "", val);

  fprintf (stderr, "\n");

}

/* Compute a default value for variable VAR and store it in the

   CONST_VAL array.  The following rules are used to get default

   values:

   1- Global and static variables that are declared constant are

      considered CONSTANT.

   2- Any other value is considered UNDEFINED.  This is useful when

      considering PHI nodes.  PHI arguments that are undefined do not

      change the constant value of the PHI node, which allows for more

      constants to be propagated.

   3- Variables defined by statements other than assignments and PHI

      nodes are considered VARYING.

   4- Initial values of variables that are not GIMPLE registers are

      considered VARYING.  */

static prop_value_t

get_default_value (tree var)

{

  tree sym = SSA_NAME_VAR (var);

  prop_value_t val = { UNINITIALIZED, NULL_TREE, { 0, 0 } };

  gimple stmt;

  stmt = SSA_NAME_DEF_STMT (var);

  if (gimple_nop_p (stmt))

    {

      /* Variables defined by an empty statement are those used

         before being initialized.  If VAR is a local variable, we

         can assume initially that it is UNDEFINED, otherwise we must

         consider it VARYING.  */

      if (is_gimple_reg (sym)

          && TREE_CODE (sym) == VAR_DECL)

        val.lattice_val = UNDEFINED;

      else

        {

          val.lattice_val = VARYING;

          val.mask = double_int_minus_one;

        }

    }

  else if (is_gimple_assign (stmt)

           /* Value-returning GIMPLE_CALL statements assign to

              a variable, and are treated similarly to GIMPLE_ASSIGN.  */

           || (is_gimple_call (stmt)

               && gimple_call_lhs (stmt) != NULL_TREE)

           || gimple_code (stmt) == GIMPLE_PHI)

    {

      tree cst;

      if (gimple_assign_single_p (stmt)

          && DECL_P (gimple_assign_rhs1 (stmt))

          && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))

        {

          val.lattice_val = CONSTANT;

          val.value = cst;

        }

      else

        /* Any other variable defined by an assignment or a PHI node

           is considered UNDEFINED.  */

        val.lattice_val = UNDEFINED;

    }

  else

    {

      /* Otherwise, VAR will never take on a constant value.  */

      val.lattice_val = VARYING;

      val.mask = double_int_minus_one;

    }

  return val;

}

/* Get the constant value associated with variable VAR.  */

static inline prop_value_t *

get_value (tree var)

{

  prop_value_t *val;

  if (const_val == NULL)

    return NULL;

  val = &const_val[SSA_NAME_VERSION (var)];

  if (val->lattice_val == UNINITIALIZED)

    *val = get_default_value (var);

  canonicalize_float_value (val);

  return val;

}

/* Return the constant tree value associated with VAR.  */

static inline tree

get_constant_value (tree var)

{

  prop_value_t *val;

  if (TREE_CODE (var) != SSA_NAME)

    {

      if (is_gimple_min_invariant (var))

        return var;

      return NULL_TREE;

    }

  val = get_value (var);

  if (val

      && val->lattice_val == CONSTANT

      && (TREE_CODE (val->value) != INTEGER_CST

          || double_int_zero_p (val->mask)))

    return val->value;

  return NULL_TREE;

}

/* Sets the value associated with VAR to VARYING.  */

static inline void

set_value_varying (tree var)

{

  prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];

  val->lattice_val = VARYING;

  val->value = NULL_TREE;

  val->mask = double_int_minus_one;

}

/* For float types, modify the value of VAL to make ccp work correctly

   for non-standard values (-0, NaN):

   If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.

   If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.

     This is to fix the following problem (see PR 29921): Suppose we have

     x = 0.0 * y

     and we set value of y to NaN.  This causes value of x to be set to NaN.

     When we later determine that y is in fact VARYING, fold uses the fact

     that HONOR_NANS is false, and we try to change the value of x to 0,

     causing an ICE.  With HONOR_NANS being false, the real appearance of

     NaN would cause undefined behavior, though, so claiming that y (and x)

     are UNDEFINED initially is correct.  */

static void

canonicalize_float_value (prop_value_t *val)

{

  enum machine_mode mode;

  tree type;

  REAL_VALUE_TYPE d;

  if (val->lattice_val != CONSTANT

      || TREE_CODE (val->value) != REAL_CST)

    return;

  d = TREE_REAL_CST (val->value);

  type = TREE_TYPE (val->value);

  mode = TYPE_MODE (type);

  if (!HONOR_SIGNED_ZEROS (mode)

      && REAL_VALUE_MINUS_ZERO (d))

    {

      val->value = build_real (type, dconst0);

      return;

    }

  if (!HONOR_NANS (mode)

      && REAL_VALUE_ISNAN (d))

    {

      val->lattice_val = UNDEFINED;

      val->value = NULL;

      return;

    }

}

/* Return whether the lattice transition is valid.  */

static bool

valid_lattice_transition (prop_value_t old_val, prop_value_t new_val)

{

  /* Lattice transitions must always be monotonically increasing in

     value.  */

  if (old_val.lattice_val < new_val.lattice_val)

    return true;

  if (old_val.lattice_val != new_val.lattice_val)

    return false;

  if (!old_val.value && !new_val.value)

    return true;

  /* Now both lattice values are CONSTANT.  */

  /* Allow transitioning from &x to &x & ~3.  */

  if (TREE_CODE (old_val.value) != INTEGER_CST

      && TREE_CODE (new_val.value) == INTEGER_CST)

    return true;

  /* Bit-lattices have to agree in the still valid bits.  */

  if (TREE_CODE (old_val.value) == INTEGER_CST

      && TREE_CODE (new_val.value) == INTEGER_CST)

    return double_int_equal_p

                (double_int_and_not (tree_to_double_int (old_val.value),

                                     new_val.mask),

                 double_int_and_not (tree_to_double_int (new_val.value),

                                     new_val.mask));

  /* Otherwise constant values have to agree.  */

  return operand_equal_p (old_val.value, new_val.value, 0);

}

/* Set the value for variable VAR to NEW_VAL.  Return true if the new

   value is different from VAR's previous value.  */

static bool

set_lattice_value (tree var, prop_value_t new_val)

{

  /* We can deal with old UNINITIALIZED values just fine here.  */

  prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];

  canonicalize_float_value (&new_val);

  /* We have to be careful to not go up the bitwise lattice

     represented by the mask.

     ???  This doesn't seem to be the best place to enforce this.  */

  if (new_val.lattice_val == CONSTANT

      && old_val->lattice_val == CONSTANT

      && TREE_CODE (new_val.value) == INTEGER_CST

      && TREE_CODE (old_val->value) == INTEGER_CST)

    {

      double_int diff;

      diff = double_int_xor (tree_to_double_int (new_val.value),

                             tree_to_double_int (old_val->value));

      new_val.mask = double_int_ior (new_val.mask,

                                     double_int_ior (old_val->mask, diff));

    }

  gcc_assert (valid_lattice_transition (*old_val, new_val));

  /* If *OLD_VAL and NEW_VAL are the same, return false to inform the

     caller that this was a non-transition.  */

  if (old_val->lattice_val != new_val.lattice_val

      || (new_val.lattice_val == CONSTANT

          && TREE_CODE (new_val.value) == INTEGER_CST

          && (TREE_CODE (old_val->value) != INTEGER_CST

              || !double_int_equal_p (new_val.mask, old_val->mask))))

    {

      /* ???  We would like to delay creation of INTEGER_CSTs from

         partially constants here.  */

      if (dump_file && (dump_flags & TDF_DETAILS))

        {

          dump_lattice_value (dump_file, "Lattice value changed to ", new_val);

          fprintf (dump_file, ".  Adding SSA edges to worklist.\n");

        }

      *old_val = new_val;

      gcc_assert (new_val.lattice_val != UNINITIALIZED);

      return true;

    }

  return false;

}

static prop_value_t get_value_for_expr (tree, bool);

static prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);

static void bit_value_binop_1 (enum tree_code, tree, double_int *, double_int *,

                               tree, double_int, double_int,

                               tree, double_int, double_int);

/* Return a double_int that can be used for bitwise simplifications

   from VAL.  */

static double_int

value_to_double_int (prop_value_t val)

{

  if (val.value

      && TREE_CODE (val.value) == INTEGER_CST)

    return tree_to_double_int (val.value);

  else

    return double_int_zero;

}

/* Return the value for the address expression EXPR based on alignment

   information.  */

static prop_value_t

get_value_from_alignment (tree expr)

{

  tree type = TREE_TYPE (expr);

  prop_value_t val;

  unsigned HOST_WIDE_INT bitpos;

  unsigned int align;

  gcc_assert (TREE_CODE (expr) == ADDR_EXPR);

  align = get_object_alignment_1 (TREE_OPERAND (expr, 0), &bitpos);

  val.mask

    = double_int_and_not (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)

                          ? double_int_mask (TYPE_PRECISION (type))

                          : double_int_minus_one,

                          uhwi_to_double_int (align / BITS_PER_UNIT - 1));

  val.lattice_val = double_int_minus_one_p (val.mask) ? VARYING : CONSTANT;

  if (val.lattice_val == CONSTANT)

    val.value

      = double_int_to_tree (type, uhwi_to_double_int (bitpos / BITS_PER_UNIT));

  else

    val.value = NULL_TREE;

  return val;

}

/* Return the value for the tree operand EXPR.  If FOR_BITS_P is true

   return constant bits extracted from alignment information for

   invariant addresses.  */

static prop_value_t

get_value_for_expr (tree expr, bool for_bits_p)

{

  prop_value_t val;

  if (TREE_CODE (expr) == SSA_NAME)

    {

      val = *get_value (expr);

      if (for_bits_p

          && val.lattice_val == CONSTANT

          && TREE_CODE (val.value) == ADDR_EXPR)

        val = get_value_from_alignment (val.value);

    }

  else if (is_gimple_min_invariant (expr)

           && (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR))

    {

      val.lattice_val = CONSTANT;

      val.value = expr;

      val.mask = double_int_zero;

      canonicalize_float_value (&val);

    }

  else if (TREE_CODE (expr) == ADDR_EXPR)

    val = get_value_from_alignment (expr);

  else

    {

      val.lattice_val = VARYING;

      val.mask = double_int_minus_one;

      val.value = NULL_TREE;

    }

  return val;

}

/* Return the likely CCP lattice value for STMT.

   If STMT has no operands, then return CONSTANT.

   Else if undefinedness of operands of STMT cause its value to be

   undefined, then return UNDEFINED.

   Else if any operands of STMT are constants, then return CONSTANT.

   Else return VARYING.  */

static ccp_lattice_t

likely_value (gimple stmt)

{

  bool has_constant_operand, has_undefined_operand, all_undefined_operands;

  tree use;

  ssa_op_iter iter;

  unsigned i;

  enum gimple_code code = gimple_code (stmt);

  /* This function appears to be called only for assignments, calls,

     conditionals, and switches, due to the logic in visit_stmt.  */

  gcc_assert (code == GIMPLE_ASSIGN

              || code == GIMPLE_CALL

              || code == GIMPLE_COND

              || code == GIMPLE_SWITCH);

  /* If the statement has volatile operands, it won't fold to a

     constant value.  */

  if (gimple_has_volatile_ops (stmt))

    return VARYING;

  /* Arrive here for more complex cases.  */

  has_constant_operand = false;

  has_undefined_operand = false;

  all_undefined_operands = true;

  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)

    {

      prop_value_t *val = get_value (use);

      if (val->lattice_val == UNDEFINED)

        has_undefined_operand = true;

      else

        all_undefined_operands = false;

      if (val->lattice_val == CONSTANT)

        has_constant_operand = true;

    }

  /* There may be constants in regular rhs operands.  For calls we

     have to ignore lhs, fndecl and static chain, otherwise only

     the lhs.  */

  for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);

       i < gimple_num_ops (stmt); ++i)

    {

      tree op = gimple_op (stmt, i);

      if (!op || TREE_CODE (op) == SSA_NAME)

        continue;

      if (is_gimple_min_invariant (op))

        has_constant_operand = true;

    }

  if (has_constant_operand)

    all_undefined_operands = false;

  /* If the operation combines operands like COMPLEX_EXPR make sure to

     not mark the result UNDEFINED if only one part of the result is

     undefined.  */

  if (has_undefined_operand && all_undefined_operands)

    return UNDEFINED;

  else if (code == GIMPLE_ASSIGN && has_undefined_operand)

    {

      switch (gimple_assign_rhs_code (stmt))

        {

        /* Unary operators are handled with all_undefined_operands.  */

        case PLUS_EXPR:

        case MINUS_EXPR:

        case POINTER_PLUS_EXPR:

          /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.

             Not bitwise operators, one VARYING operand may specify the

             result completely.  Not logical operators for the same reason.

             Not COMPLEX_EXPR as one VARYING operand makes the result partly

             not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because

             the undefined operand may be promoted.  */

          return UNDEFINED;

        default:

          ;

        }

    }

  /* If there was an UNDEFINED operand but the result may be not UNDEFINED

     fall back to CONSTANT.  During iteration UNDEFINED may still drop

     to CONSTANT.  */

  if (has_undefined_operand)

    return CONSTANT;

  /* We do not consider virtual operands here -- load from read-only

     memory may have only VARYING virtual operands, but still be

     constant.  */

  if (has_constant_operand

      || gimple_references_memory_p (stmt))

    return CONSTANT;

  return VARYING;

}

/* Returns true if STMT cannot be constant.  */

static bool

surely_varying_stmt_p (gimple stmt)

{

  /* If the statement has operands that we cannot handle, it cannot be

     constant.  */

  if (gimple_has_volatile_ops (stmt))

    return true;

  /* If it is a call and does not return a value or is not a

     builtin and not an indirect call, it is varying.  */

  if (is_gimple_call (stmt))

    {

      tree fndecl;

      if (!gimple_call_lhs (stmt)

          || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE

              && !DECL_BUILT_IN (fndecl)))

        return true;

    }

  /* Any other store operation is not interesting.  */

  else if (gimple_vdef (stmt))

    return true;

  /* Anything other than assignments and conditional jumps are not

     interesting for CCP.  */

  if (gimple_code (stmt) != GIMPLE_ASSIGN

      && gimple_code (stmt) != GIMPLE_COND

      && gimple_code (stmt) != GIMPLE_SWITCH

      && gimple_code (stmt) != GIMPLE_CALL)

    return true;

  return false;

}

/* Initialize local data structures for CCP.  */

static void

ccp_initialize (void)

{

  basic_block bb;

  const_val = XCNEWVEC (prop_value_t, num_ssa_names);

  /* Initialize simulation flags for PHI nodes and statements.  */

  FOR_EACH_BB (bb)

    {

      gimple_stmt_iterator i;

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

        {

          gimple stmt = gsi_stmt (i);

          bool is_varying;

          /* If the statement is a control insn, then we do not

             want to avoid simulating the statement once.  Failure

             to do so means that those edges will never get added.  */

          if (stmt_ends_bb_p (stmt))

            is_varying = false;

          else

            is_varying = surely_varying_stmt_p (stmt);

          if (is_varying)

            {

              tree def;

              ssa_op_iter iter;

              /* If the statement will not produce a constant, mark

                 all its outputs VARYING.  */

              FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)

                set_value_varying (def);

            }

          prop_set_simulate_again (stmt, !is_varying);

        }

    }

  /* Now process PHI nodes.  We never clear the simulate_again flag on