Subversion Repositories openrisc

/* Conditional constant propagation pass for the GNU compiler.

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

   2010 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.

   Constant propagation in stores and loads (STORE-CCP)

   ----------------------------------------------------

   While CCP has all the logic to propagate constants in GIMPLE

   registers, it is missing the ability to associate constants with

   stores and loads (i.e., pointer dereferences, structures and

   global/aliased variables).  We don't keep loads and stores in

   SSA, but we do build a factored use-def web for them (in the

   virtual operands).

   For instance, consider the following code fragment:

          struct A a;

          const int B = 42;

          void foo (int i)

          {

            if (i > 10)

              a.a = 42;

            else

              {

                a.b = 21;

                a.a = a.b + 21;

              }

            if (a.a != B)

              never_executed ();

          }

   We should be able to deduce that the predicate 'a.a != B' is always

   false.  To achieve this, we associate constant values to the SSA

   names in the VDEF operands for each store.  Additionally,

   since we also glob partial loads/stores with the base symbol, we

   also keep track of the memory reference where the constant value

   was stored (in the MEM_REF field of PROP_VALUE_T).  For instance,

        # a_5 = VDEF <a_4>

        a.a = 2;

        # VUSE <a_5>

        x_3 = a.b;

   In the example above, CCP will associate value '2' with 'a_5', but

   it would be wrong to replace the load from 'a.b' with '2', because

   '2' had been stored into a.a.

   Note that the initial value of virtual operands is VARYING, not

   UNDEFINED.  Consider, for instance global variables:

        int A;

        foo (int i)

        {

          if (i_3 > 10)

            A_4 = 3;

          # A_5 = PHI (A_4, A_2);

          # VUSE <A_5>

          A.0_6 = A;

          return A.0_6;

        }

   The value of A_2 cannot be assumed to be UNDEFINED, as it may have

   been defined outside of foo.  If we were to assume it UNDEFINED, we

   would erroneously optimize the above into 'return 3;'.

   Though STORE-CCP is not too expensive, it does have to do more work

   than regular CCP, so it is only enabled at -O2.  Both regular CCP

   and STORE-CCP use the exact same algorithm.  The only distinction

   is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is

   set to true.  This affects the evaluation of statements and PHI

   nodes.

   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 "rtl.h"

#include "tm_p.h"

#include "ggc.h"

#include "basic-block.h"

#include "output.h"

#include "expr.h"

#include "function.h"

#include "diagnostic.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 "toplev.h"

#include "dbgcnt.h"

/* Possible lattice values.  */

typedef enum

{

  UNINITIALIZED,

  UNDEFINED,

  CONSTANT,

  VARYING

} ccp_lattice_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);

      print_generic_expr (outf, val.value, dump_flags);

      break;

    default:

      gcc_unreachable ();

    }

}

/* Print lattice value VAL to stderr.  */

void debug_lattice_value (prop_value_t val);

void

debug_lattice_value (prop_value_t val)

{

  dump_lattice_value (stderr, "", val);

  fprintf (stderr, "\n");

}

/* If SYM is a constant variable with known value, return the value.

   NULL_TREE is returned otherwise.  */

tree

get_symbol_constant_value (tree sym)

{

  if (TREE_STATIC (sym)

      && (TREE_READONLY (sym)

          || TREE_CODE (sym) == CONST_DECL))

    {

      tree val = DECL_INITIAL (sym);

      if (val)

        {

          STRIP_NOPS (val);

          if (is_gimple_min_invariant (val))

            {

              if (TREE_CODE (val) == ADDR_EXPR)

                {

                  tree base = get_base_address (TREE_OPERAND (val, 0));

                  if (base && TREE_CODE (base) == VAR_DECL)

                    {

                      TREE_ADDRESSABLE (base) = 1;

                      if (gimple_referenced_vars (cfun))

                        add_referenced_var (base);

                    }

                }

              return val;

            }

        }

      /* Variables declared 'const' without an initializer

         have zero as the initializer if they may not be

         overridden at link or run time.  */

      if (!val

          && !DECL_EXTERNAL (sym)

          && targetm.binds_local_p (sym)

          && (INTEGRAL_TYPE_P (TREE_TYPE (sym))

               || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))

        return fold_convert (TREE_TYPE (sym), integer_zero_node);

    }

  return NULL_TREE;

}

/* 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 };

  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) != PARM_DECL)

        val.lattice_val = UNDEFINED;

      else

        val.lattice_val = VARYING;

    }

  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;

    }

  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;

}

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

}

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

    }

}

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

{

  prop_value_t *old_val = get_value (var);

  canonicalize_float_value (&new_val);

  /* Lattice transitions must always be monotonically increasing in

     value.  If *OLD_VAL and NEW_VAL are the same, return false to

     inform the caller that this was a non-transition.  */

  gcc_assert (old_val->lattice_val < new_val.lattice_val

              || (old_val->lattice_val == new_val.lattice_val

                  && ((!old_val->value && !new_val.value)

                      || operand_equal_p (old_val->value, new_val.value, 0))));

  if (old_val->lattice_val != new_val.lattice_val)

    {

      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 != UNDEFINED);

      return true;

    }

  return false;

}

/* 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 VARYING even if there were CONSTANT operands.  */

  if (has_undefined_operand)

    return VARYING;

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

     phi nodes, since we do not know which edges are executable yet,

     except for phi nodes for virtual operands when we do not do store ccp.  */

  FOR_EACH_BB (bb)

    {

      gimple_stmt_iterator i;

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

        {

          gimple phi = gsi_stmt (i);

          if (!is_gimple_reg (gimple_phi_result (phi)))

            prop_set_simulate_again (phi, false);

          else

            prop_set_simulate_again (phi, true);

        }

    }

}

/* Debug count support. Reset the values of ssa names

   VARYING when the total number ssa names analyzed is

   beyond the debug count specified.  */

static void

do_dbg_cnt (void)

{

  unsigned i;

  for (i = 0; i < num_ssa_names; i++)

    {

      if (!dbg_cnt (ccp))

        {

          const_val[i].lattice_val = VARYING;

          const_val[i].value = NULL_TREE;

        }

    }

}

/* Do final substitution of propagated values, cleanup the flowgraph and

   free allocated storage.

   Return TRUE when something was optimized.  */

static bool

ccp_finalize (void)

{

  bool something_changed;

  do_dbg_cnt ();

  /* Perform substitutions based on the known constant values.  */

  something_changed = substitute_and_fold (const_val, ccp_fold_stmt, true);

  free (const_val);

  const_val = NULL;

  return something_changed;;

}

/* Compute the meet operator between *VAL1 and *VAL2.  Store the result

   in VAL1.

                any  M UNDEFINED   = any

                any  M VARYING     = VARYING

                Ci   M Cj          = Ci         if (i == j)

                Ci   M Cj          = VARYING    if (i != j)

   */

static void

ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)

{

  if (val1->lattice_val == UNDEFINED)

    {

      /* UNDEFINED M any = any   */

      *val1 = *val2;

    }

  else if (val2->lattice_val == UNDEFINED)

    {

      /* any M UNDEFINED = any

         Nothing to do.  VAL1 already contains the value we want.  */

      ;

    }

  else if (val1->lattice_val == VARYING

           || val2->lattice_val == VARYING)

    {

      /* any M VARYING = VARYING.  */

      val1->lattice_val = VARYING;

      val1->value = NULL_TREE;

    }

  else if (val1->lattice_val == CONSTANT

           && val2->lattice_val == CONSTANT

           && simple_cst_equal (val1->value, val2->value) == 1)

    {

      /* Ci M Cj = Ci           if (i == j)

         Ci M Cj = VARYING      if (i != j)

         If these two values come from memory stores, make sure that

         they come from the same memory reference.  */

      val1->lattice_val = CONSTANT;

      val1->value = val1->value;

    }