Subversion Repositories openrisc

/* SSA Dominator optimizations for trees

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

   Free Software Foundation, Inc.

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

#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 "cfgloop.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 "domwalk.h"

#include "real.h"

#include "tree-pass.h"

#include "tree-ssa-propagate.h"

#include "langhooks.h"

#include "params.h"

/* This file implements optimizations on the dominator tree.  */

/* Structure for recording edge equivalences as well as any pending

   edge redirections during the dominator optimizer.

   Computing and storing the edge equivalences instead of creating

   them on-demand can save significant amounts of time, particularly

   for pathological cases involving switch statements.

   These structures live for a single iteration of the dominator

   optimizer in the edge's AUX field.  At the end of an iteration we

   free each of these structures and update the AUX field to point

   to any requested redirection target (the code for updating the

   CFG and SSA graph for edge redirection expects redirection edge

   targets to be in the AUX field for each edge.  */

struct edge_info

{

  /* If this edge creates a simple equivalence, the LHS and RHS of

     the equivalence will be stored here.  */

  tree lhs;

  tree rhs;

  /* Traversing an edge may also indicate one or more particular conditions

     are true or false.  The number of recorded conditions can vary, but

     can be determined by the condition's code.  So we have an array

     and its maximum index rather than use a varray.  */

  tree *cond_equivalences;

  unsigned int max_cond_equivalences;

};

/* Hash table with expressions made available during the renaming process.

   When an assignment of the form X_i = EXPR is found, the statement is

   stored in this table.  If the same expression EXPR is later found on the

   RHS of another statement, it is replaced with X_i (thus performing

   global redundancy elimination).  Similarly as we pass through conditionals

   we record the conditional itself as having either a true or false value

   in this table.  */

static htab_t avail_exprs;

/* Stack of available expressions in AVAIL_EXPRs.  Each block pushes any

   expressions it enters into the hash table along with a marker entry

   (null).  When we finish processing the block, we pop off entries and

   remove the expressions from the global hash table until we hit the

   marker.  */

static VEC(tree,heap) *avail_exprs_stack;

/* Stack of statements we need to rescan during finalization for newly

   exposed variables.

   Statement rescanning must occur after the current block's available

   expressions are removed from AVAIL_EXPRS.  Else we may change the

   hash code for an expression and be unable to find/remove it from

   AVAIL_EXPRS.  */

static VEC(tree,heap) *stmts_to_rescan;

/* Structure for entries in the expression hash table.

   This requires more memory for the hash table entries, but allows us

   to avoid creating silly tree nodes and annotations for conditionals,

   eliminates 2 global hash tables and two block local varrays.

   It also allows us to reduce the number of hash table lookups we

   have to perform in lookup_avail_expr and finally it allows us to

   significantly reduce the number of calls into the hashing routine

   itself.  */

struct expr_hash_elt

{

  /* The value (lhs) of this expression.  */

  tree lhs;

  /* The expression (rhs) we want to record.  */

  tree rhs;

  /* The stmt pointer if this element corresponds to a statement.  */

  tree stmt;

  /* The hash value for RHS/ann.  */

  hashval_t hash;

};

/* Stack of dest,src pairs that need to be restored during finalization.

   A NULL entry is used to mark the end of pairs which need to be

   restored during finalization of this block.  */

static VEC(tree,heap) *const_and_copies_stack;

/* Track whether or not we have changed the control flow graph.  */

static bool cfg_altered;

/* Bitmap of blocks that have had EH statements cleaned.  We should

   remove their dead edges eventually.  */

static bitmap need_eh_cleanup;

/* Statistics for dominator optimizations.  */

struct opt_stats_d

{

  long num_stmts;

  long num_exprs_considered;

  long num_re;

  long num_const_prop;

  long num_copy_prop;

};

static struct opt_stats_d opt_stats;

struct eq_expr_value

{

  tree src;

  tree dst;

};

/* Local functions.  */

static void optimize_stmt (struct dom_walk_data *,

                           basic_block bb,

                           block_stmt_iterator);

static tree lookup_avail_expr (tree, bool);

static hashval_t avail_expr_hash (const void *);

static hashval_t real_avail_expr_hash (const void *);

static int avail_expr_eq (const void *, const void *);

static void htab_statistics (FILE *, htab_t);

static void record_cond (tree, tree);

static void record_const_or_copy (tree, tree);

static void record_equality (tree, tree);

static void record_equivalences_from_phis (basic_block);

static void record_equivalences_from_incoming_edge (basic_block);

static bool eliminate_redundant_computations (tree);

static void record_equivalences_from_stmt (tree, int, stmt_ann_t);

static void dom_thread_across_edge (struct dom_walk_data *, edge);

static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);

static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);

static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);

static void remove_local_expressions_from_table (void);

static void restore_vars_to_original_value (void);

static edge single_incoming_edge_ignoring_loop_edges (basic_block);

/* Allocate an EDGE_INFO for edge E and attach it to E.

   Return the new EDGE_INFO structure.  */

static struct edge_info *

allocate_edge_info (edge e)

{

  struct edge_info *edge_info;

  edge_info = XCNEW (struct edge_info);

  e->aux = edge_info;

  return edge_info;

}

/* Free all EDGE_INFO structures associated with edges in the CFG.

   If a particular edge can be threaded, copy the redirection

   target from the EDGE_INFO structure into the edge's AUX field

   as required by code to update the CFG and SSA graph for

   jump threading.  */

static void

free_all_edge_infos (void)

{

  basic_block bb;

  edge_iterator ei;

  edge e;

  FOR_EACH_BB (bb)

    {

      FOR_EACH_EDGE (e, ei, bb->preds)

        {

         struct edge_info *edge_info = (struct edge_info *) e->aux;

          if (edge_info)

            {

              if (edge_info->cond_equivalences)

                free (edge_info->cond_equivalences);

              free (edge_info);

              e->aux = NULL;

            }

        }

    }

}

/* Jump threading, redundancy elimination and const/copy propagation.

   This pass may expose new symbols that need to be renamed into SSA.  For

   every new symbol exposed, its corresponding bit will be set in

   VARS_TO_RENAME.  */

static unsigned int

tree_ssa_dominator_optimize (void)

{

  struct dom_walk_data walk_data;

  unsigned int i;

  struct loops loops_info;

  memset (&opt_stats, 0, sizeof (opt_stats));

  /* Create our hash tables.  */

  avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);

  avail_exprs_stack = VEC_alloc (tree, heap, 20);

  const_and_copies_stack = VEC_alloc (tree, heap, 20);

  stmts_to_rescan = VEC_alloc (tree, heap, 20);

  need_eh_cleanup = BITMAP_ALLOC (NULL);

  /* Setup callbacks for the generic dominator tree walker.  */

  walk_data.walk_stmts_backward = false;

  walk_data.dom_direction = CDI_DOMINATORS;

  walk_data.initialize_block_local_data = NULL;

  walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;

  walk_data.before_dom_children_walk_stmts = optimize_stmt;

  walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;

  walk_data.after_dom_children_before_stmts = NULL;

  walk_data.after_dom_children_walk_stmts = NULL;

  walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;

  /* Right now we only attach a dummy COND_EXPR to the global data pointer.

     When we attach more stuff we'll need to fill this out with a real

     structure.  */

  walk_data.global_data = NULL;

  walk_data.block_local_data_size = 0;

  walk_data.interesting_blocks = NULL;

  /* Now initialize the dominator walker.  */

  init_walk_dominator_tree (&walk_data);

  calculate_dominance_info (CDI_DOMINATORS);

  /* We need to know which edges exit loops so that we can

     aggressively thread through loop headers to an exit

     edge.  */

  flow_loops_find (&loops_info);

  mark_loop_exit_edges (&loops_info);

  flow_loops_free (&loops_info);

  /* Clean up the CFG so that any forwarder blocks created by loop

     canonicalization are removed.  */

  cleanup_tree_cfg ();

  calculate_dominance_info (CDI_DOMINATORS);

  /* We need accurate information regarding back edges in the CFG

     for jump threading.  */

  mark_dfs_back_edges ();

  /* Recursively walk the dominator tree optimizing statements.  */

  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);

  {

    block_stmt_iterator bsi;

    basic_block bb;

    FOR_EACH_BB (bb)

      {

        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))

          update_stmt_if_modified (bsi_stmt (bsi));

      }

  }

  /* If we exposed any new variables, go ahead and put them into

     SSA form now, before we handle jump threading.  This simplifies

     interactions between rewriting of _DECL nodes into SSA form

     and rewriting SSA_NAME nodes into SSA form after block

     duplication and CFG manipulation.  */

  update_ssa (TODO_update_ssa);

  free_all_edge_infos ();

  /* Thread jumps, creating duplicate blocks as needed.  */

  cfg_altered |= thread_through_all_blocks ();

  /* Removal of statements may make some EH edges dead.  Purge

     such edges from the CFG as needed.  */

  if (!bitmap_empty_p (need_eh_cleanup))

    {

      cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);

      bitmap_zero (need_eh_cleanup);

    }

  if (cfg_altered)

    free_dominance_info (CDI_DOMINATORS);

  /* Finally, remove everything except invariants in SSA_NAME_VALUE.

     Long term we will be able to let everything in SSA_NAME_VALUE

     persist.  However, for now, we know this is the safe thing to do.  */

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

   {

      tree name = ssa_name (i);

      tree value;

      if (!name)

        continue;

      value = SSA_NAME_VALUE (name);

      if (value && !is_gimple_min_invariant (value))

        SSA_NAME_VALUE (name) = NULL;

    }

  /* Debugging dumps.  */

  if (dump_file && (dump_flags & TDF_STATS))

    dump_dominator_optimization_stats (dump_file);

  /* Delete our main hashtable.  */

  htab_delete (avail_exprs);

  /* And finalize the dominator walker.  */

  fini_walk_dominator_tree (&walk_data);

  /* Free asserted bitmaps and stacks.  */

  BITMAP_FREE (need_eh_cleanup);

  VEC_free (tree, heap, avail_exprs_stack);

  VEC_free (tree, heap, const_and_copies_stack);

  VEC_free (tree, heap, stmts_to_rescan);

  return 0;

}

static bool

gate_dominator (void)

{

  return flag_tree_dom != 0;

}

struct tree_opt_pass pass_dominator =

{

  "dom",                                /* name */

  gate_dominator,                       /* gate */

  tree_ssa_dominator_optimize,          /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                     /* static_pass_number */

  TV_TREE_SSA_DOMINATOR_OPTS,           /* tv_id */

  PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */

  0,                                     /* properties_provided */

  PROP_smt_usage,                       /* properties_destroyed */

  0,                                     /* todo_flags_start */

  TODO_dump_func

    | TODO_update_ssa

    | TODO_cleanup_cfg

    | TODO_verify_ssa

    | TODO_update_smt_usage,            /* todo_flags_finish */

};

/* Given a stmt CONDSTMT containing a COND_EXPR, canonicalize the

   COND_EXPR into a canonical form.  */

static void

canonicalize_comparison (tree condstmt)

{

  tree cond = COND_EXPR_COND (condstmt);

  tree op0;

  tree op1;

  enum tree_code code = TREE_CODE (cond);

  if (!COMPARISON_CLASS_P (cond))

    return;

  op0 = TREE_OPERAND (cond, 0);

  op1 = TREE_OPERAND (cond, 1);

  /* If it would be profitable to swap the operands, then do so to

     canonicalize the statement, enabling better optimization.

     By placing canonicalization of such expressions here we

     transparently keep statements in canonical form, even

     when the statement is modified.  */

  if (tree_swap_operands_p (op0, op1, false))

    {

      /* For relationals we need to swap the operands

         and change the code.  */

      if (code == LT_EXPR

          || code == GT_EXPR

          || code == LE_EXPR

          || code == GE_EXPR)

        {

          TREE_SET_CODE (cond, swap_tree_comparison (code));

          swap_tree_operands (condstmt,

                              &TREE_OPERAND (cond, 0),

                              &TREE_OPERAND (cond, 1));

          /* If one operand was in the operand cache, but the other is

             not, because it is a constant, this is a case that the

             internal updating code of swap_tree_operands can't handle

             properly.  */

          if (TREE_CODE_CLASS (TREE_CODE (op0))

              != TREE_CODE_CLASS (TREE_CODE (op1)))

            update_stmt (condstmt);

        }

    }

}

/* Initialize local stacks for this optimizer and record equivalences

   upon entry to BB.  Equivalences can come from the edge traversed to

   reach BB or they may come from PHI nodes at the start of BB.  */

static void

dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,

                          basic_block bb)

{

  if (dump_file && (dump_flags & TDF_DETAILS))

    fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);

  /* Push a marker on the stacks of local information so that we know how

     far to unwind when we finalize this block.  */

  VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);

  VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);

  record_equivalences_from_incoming_edge (bb);

  /* PHI nodes can create equivalences too.  */

  record_equivalences_from_phis (bb);

}

/* Given an expression EXPR (a relational expression or a statement),

   initialize the hash table element pointed to by ELEMENT.  */

static void

initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)

{

  /* Hash table elements may be based on conditional expressions or statements.

     For the former case, we have no annotation and we want to hash the

     conditional expression.  In the latter case we have an annotation and

     we want to record the expression the statement evaluates.  */

  if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)

    {

      element->stmt = NULL;

      element->rhs = expr;

    }

  else if (TREE_CODE (expr) == COND_EXPR)

    {

      element->stmt = expr;

      element->rhs = COND_EXPR_COND (expr);

    }

  else if (TREE_CODE (expr) == SWITCH_EXPR)

    {

      element->stmt = expr;

      element->rhs = SWITCH_COND (expr);

    }

  else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))

    {

      element->stmt = expr;

      element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);

    }

  else if (TREE_CODE (expr) == GOTO_EXPR)

    {

      element->stmt = expr;

      element->rhs = GOTO_DESTINATION (expr);

    }

  else

    {

      element->stmt = expr;

      element->rhs = TREE_OPERAND (expr, 1);

    }

  element->lhs = lhs;

  element->hash = avail_expr_hash (element);

}

/* Remove all the expressions in LOCALS from TABLE, stopping when there are

   LIMIT entries left in LOCALs.  */

static void

remove_local_expressions_from_table (void)

{

  /* Remove all the expressions made available in this block.  */

  while (VEC_length (tree, avail_exprs_stack) > 0)

    {

      struct expr_hash_elt element;

      tree expr = VEC_pop (tree, avail_exprs_stack);

      if (expr == NULL_TREE)

        break;

      initialize_hash_element (expr, NULL, &element);

      htab_remove_elt_with_hash (avail_exprs, &element, element.hash);

    }

}

/* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore

   CONST_AND_COPIES to its original state, stopping when we hit a

   NULL marker.  */

static void

restore_vars_to_original_value (void)

{

  while (VEC_length (tree, const_and_copies_stack) > 0)

    {

      tree prev_value, dest;

      dest = VEC_pop (tree, const_and_copies_stack);

      if (dest == NULL)

        break;

      prev_value = VEC_pop (tree, const_and_copies_stack);

      SSA_NAME_VALUE (dest) =  prev_value;

    }

}

/* A trivial wrapper so that we can present the generic jump

   threading code with a simple API for simplifying statements.  */

static tree

simplify_stmt_for_jump_threading (tree stmt, tree within_stmt ATTRIBUTE_UNUSED)

{

  return lookup_avail_expr (stmt, false);

}

/* Wrapper for common code to attempt to thread an edge.  For example,

   it handles lazily building the dummy condition and the bookkeeping

   when jump threading is successful.  */

static void

dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)

{

  /* If we don't already have a dummy condition, build it now.  */

  if (! walk_data->global_data)

    {

      tree dummy_cond = build2 (NE_EXPR, boolean_type_node,

                                integer_zero_node, integer_zero_node);

      dummy_cond = build3 (COND_EXPR, void_type_node, dummy_cond, NULL, NULL);

      walk_data->global_data = dummy_cond;

    }

  thread_across_edge (walk_data->global_data, e, false,

                      &const_and_copies_stack,

                      simplify_stmt_for_jump_threading);

}

/* We have finished processing the dominator children of BB, perform

   any finalization actions in preparation for leaving this node in

   the dominator tree.  */

static void

dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)

{

  tree last;

  /* If we have an outgoing edge to a block with multiple incoming and

     outgoing edges, then we may be able to thread the edge.  ie, we

     may be able to statically determine which of the outgoing edges

     will be traversed when the incoming edge from BB is traversed.  */

  if (single_succ_p (bb)

      && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0

      && potentially_threadable_block (single_succ (bb)))

    {

      dom_thread_across_edge (walk_data, single_succ_edge (bb));

    }

  else if ((last = last_stmt (bb))

           && TREE_CODE (last) == COND_EXPR

           && (COMPARISON_CLASS_P (COND_EXPR_COND (last))

               || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)

           && EDGE_COUNT (bb->succs) == 2

           && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0

           && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)

    {

      edge true_edge, false_edge;

      extract_true_false_edges_from_block (bb, &true_edge, &false_edge);

      /* Only try to thread the edge if it reaches a target block with

         more than one predecessor and more than one successor.  */

      if (potentially_threadable_block (true_edge->dest))

        {

          struct edge_info *edge_info;

          unsigned int i;

          /* Push a marker onto the available expression stack so that we

             unwind any expressions related to the TRUE arm before processing

             the false arm below.  */

          VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);

          VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);

          edge_info = (struct edge_info *) true_edge->aux;

          /* If we have info associated with this edge, record it into

             our equivalency tables.  */

          if (edge_info)

            {

              tree *cond_equivalences = edge_info->cond_equivalences;

              tree lhs = edge_info->lhs;

              tree rhs = edge_info->rhs;

              /* If we have a simple NAME = VALUE equivalency record it.  */

              if (lhs && TREE_CODE (lhs) == SSA_NAME)

                record_const_or_copy (lhs, rhs);

              /* If we have 0 = COND or 1 = COND equivalences, record them

                 into our expression hash tables.  */

              if (cond_equivalences)

                for (i = 0; i < edge_info->max_cond_equivalences; i += 2)

                  {

                    tree expr = cond_equivalences[i];

                    tree value = cond_equivalences[i + 1];

                    record_cond (expr, value);

                  }

            }

          dom_thread_across_edge (walk_data, true_edge);

          /* And restore the various tables to their state before

             we threaded this edge.  */

          remove_local_expressions_from_table ();

        }

      /* Similarly for the ELSE arm.  */

      if (potentially_threadable_block (false_edge->dest))

        {

          struct edge_info *edge_info;

          unsigned int i;

          VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);

          edge_info = (struct edge_info *) false_edge->aux;

          /* If we have info associated with this edge, record it into

             our equivalency tables.  */

          if (edge_info)

            {

              tree *cond_equivalences = edge_info->cond_equivalences;

              tree lhs = edge_info->lhs;

              tree rhs = edge_info->rhs;

              /* If we have a simple NAME = VALUE equivalency record it.  */

              if (lhs && TREE_CODE (lhs) == SSA_NAME)

                record_const_or_copy (lhs, rhs);

              /* If we have 0 = COND or 1 = COND equivalences, record them

                 into our expression hash tables.  */

              if (cond_equivalences)

                for (i = 0; i < edge_info->max_cond_equivalences; i += 2)

                  {

                    tree expr = cond_equivalences[i];

                    tree value = cond_equivalences[i + 1];

                    record_cond (expr, value);

                  }

            }

          /* Now thread the edge.  */

          dom_thread_across_edge (walk_data, false_edge);

          /* No need to remove local expressions from our tables

             or restore vars to their original value as that will

             be done immediately below.  */

        }

    }

  remove_local_expressions_from_table ();

  restore_vars_to_original_value ();

  /* If we queued any statements to rescan in this block, then

     go ahead and rescan them now.  */

  while (VEC_length (tree, stmts_to_rescan) > 0)

    {

      tree stmt = VEC_last (tree, stmts_to_rescan);

      basic_block stmt_bb = bb_for_stmt (stmt);

      if (stmt_bb != bb)

        break;

      VEC_pop (tree, stmts_to_rescan);

      mark_new_vars_to_rename (stmt);

    }

}

/* PHI nodes can create equivalences too.

   Ignoring any alternatives which are the same as the result, if

   all the alternatives are equal, then the PHI node creates an

   equivalence.  */

static void

record_equivalences_from_phis (basic_block bb)

{

  tree phi;

  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))

    {

      tree lhs = PHI_RESULT (phi);

      tree rhs = NULL;

      int i;

      for (i = 0; i < PHI_NUM_ARGS (phi); i++)

        {