/* Thread edges through blocks and update the control flow and SSA graphs.
   Copyright (C) 2004 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 2, 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 COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#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 "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "tree-pass.h"

/* Given a block B, update the CFG and SSA graph to reflect redirecting
   one or more in-edges to B to instead reach the destination of an
   out-edge from B while preserving any side effects in B.

   i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
   side effects of executing B.

     1. Make a copy of B (including its outgoing edges and statements).  Call
	the copy B'.  Note B' has no incoming edges or PHIs at this time.

     2. Remove the control statement at the end of B' and all outgoing edges
	except B'->C.

     3. Add a new argument to each PHI in C with the same value as the existing
	argument associated with edge B->C.  Associate the new PHI arguments
	with the edge B'->C.

     4. For each PHI in B, find or create a PHI in B' with an identical
	PHI_RESULT.  Add an argument to the PHI in B' which has the same
	value as the PHI in B associated with the edge A->B.  Associate
	the new argument in the PHI in B' with the edge A->B.

     5. Change the edge A->B to A->B'.

	5a. This automatically deletes any PHI arguments associated with the
	    edge A->B in B.

	5b. This automatically associates each new argument added in step 4
	    with the edge A->B'.

     6. Repeat for other incoming edges into B.

     7. Put the duplicated resources in B and all the B' blocks into SSA form.

   Note that block duplication can be minimized by first collecting the
   the set of unique destination blocks that the incoming edges should
   be threaded to.  Block duplication can be further minimized by using 
   B instead of creating B' for one destination if all edges into B are
   going to be threaded to a successor of B.  */


/* Main data structure recording information regarding B's duplicate
   blocks.  */

struct redirection_data
{
  /* A duplicate of B with the trailing control statement removed and which
     targets a single successor of B.  */
  basic_block dup_block;

  /* An outgoing edge from B.  DUP_BLOCK will have OUTGOING_EDGE->dest as
     its single successor.  */
  edge outgoing_edge;
};

/* Main data structure to hold information for duplicates of BB.  */
static varray_type redirection_data;

/* For each PHI node in BB, find or create a PHI node in NEW_BB for the
   same PHI_RESULT.  Add an argument to the PHI node in NEW_BB which
   corresponds to the same PHI argument associated with edge E in BB.  */

static void
copy_phis_to_block (basic_block new_bb, basic_block bb, edge e)
{
  tree phi, arg;

  /* Walk over every PHI in BB.  */
  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
    {
      tree new_phi;

      /* First try to find a PHI node in NEW_BB which has the same
         PHI_RESULT as the PHI from BB we are currently processing.  */
      for (new_phi = phi_nodes (new_bb); new_phi;
	   new_phi = PHI_CHAIN (new_phi))
	if (PHI_RESULT (new_phi) == PHI_RESULT (phi))
	  break;

      /* If we did not find a suitable PHI in NEW_BB, create one.  */
      if (!new_phi)
	new_phi = create_phi_node (PHI_RESULT (phi), new_bb);

      /* Extract the argument corresponding to E from the current PHI
         node in BB.  */
      arg = PHI_ARG_DEF_TREE (phi, phi_arg_from_edge (phi, e));

      /* Now add that same argument to the new PHI node in block NEW_BB.  */
      add_phi_arg (&new_phi, arg, e);
    }
}

/* Remove the last statement in block BB if it is a control statement
   Also remove all outgoing edges except the edge which reaches DEST_BB.
   If DEST_BB is NULL, then remove all outgoing edges.  */

static void
remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
{
  block_stmt_iterator bsi;
  edge e;
  edge_iterator ei;

  bsi = bsi_last (bb);

  /* If the duplicate ends with a control statement, then remove it.

     Note that if we are duplicating the template block rather than the
     original basic block, then the duplicate might not have any real
     statements in it.  */
  if (!bsi_end_p (bsi)
      && bsi_stmt (bsi)
      && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR
	  || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR))
    bsi_remove (&bsi);

  for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
    {
      if (e->dest != dest_bb)
	ssa_remove_edge (e);
      else
	ei_next (&ei);
    }
}

/* Create a duplicate of BB which only reaches the destination of the edge
   stored in RD.  Record the duplicate block in RD.  */

static void
create_block_for_threading (basic_block bb, struct redirection_data *rd)
{
  /* We can use the generic block duplication code and simply remove
     the stuff we do not need.  */
  rd->dup_block = duplicate_block (bb, NULL);

  /* Zero out the profile, since the block is unreachable for now.  */
  rd->dup_block->frequency = 0;
  rd->dup_block->count = 0;

  /* The call to duplicate_block will copy everything, including the
     useless COND_EXPR or SWITCH_EXPR at the end of BB.  We just remove
     the useless COND_EXPR or SWITCH_EXPR here rather than having a
     specialized block copier.  We also remove all outgoing edges
     from the duplicate block.  The appropriate edge will be created
     later.  */
  remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL);
}

/* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
   is reached via one or more specific incoming edges, we know which
   outgoing edge from BB will be traversed.

   We want to redirect those incoming edges to the target of the 
   appropriate outgoing edge.  Doing so avoids a conditional branch
   and may expose new optimization opportunities.  Note that we have
   to update dominator tree and SSA graph after such changes.

   The key to keeping the SSA graph update manageable is to duplicate
   the side effects occurring in BB so that those side effects still
   occur on the paths which bypass BB after redirecting edges.

   We accomplish this by creating duplicates of BB and arranging for
   the duplicates to unconditionally pass control to one specific
   successor of BB.  We then revector the incoming edges into BB to
   the appropriate duplicate of BB.

   BB and its duplicates will have assignments to the same set of
   SSA_NAMEs.  Right now, we just call into rewrite_ssa_into_ssa
   to update the SSA graph for those names.

   We are also going to experiment with a true incremental update
   scheme for the duplicated resources.  One of the interesting
   properties we can exploit here is that all the resources set
   in BB will have the same IDFS, so we have one IDFS computation
   per block with incoming threaded edges, which can lower the
   cost of the true incremental update algorithm.  */

static void
thread_block (basic_block bb)
{
  /* E is an incoming edge into BB that we may or may not want to
     redirect to a duplicate of BB.  */
  edge e;
  edge_iterator ei;
  basic_block template_block;

  /* ALL indicates whether or not all incoming edges into BB should
     be threaded to a duplicate of BB.  */
  bool all = true;

  unsigned int i;

  VARRAY_GENERIC_PTR_INIT (redirection_data, 2, "redirection data");

  /* Look at each incoming edge into BB.  Record each unique outgoing
     edge that we want to thread an incoming edge to.  Also note if
     all incoming edges are threaded or not.  */
  FOR_EACH_EDGE (e, ei, bb->preds)
    {
      if (!e->aux)
	{
	  all = false;
	}
      else
	{
	  unsigned int i;

	  /* See if we can find an entry for the destination of this
	     threaded edge that has already been recorded.  */
	  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
	    {
	      struct redirection_data *rd;
	      edge e2;

	      rd = VARRAY_GENERIC_PTR (redirection_data, i);
	      e2 = e->aux;

	      if (e2->dest == rd->outgoing_edge->dest)
		break;
	    }

	  /* If the loop did not terminate early, then we have a new
	     destination for the incoming threaded edges.  Record it.  */
	  if (i == VARRAY_ACTIVE_SIZE (redirection_data))
	    {
	      struct redirection_data *rd;

	      rd = ggc_alloc_cleared (sizeof (struct redirection_data));
	      rd->outgoing_edge = e->aux;
	      VARRAY_PUSH_GENERIC_PTR (redirection_data, rd);
	    }
	}
    }

  /* Now create duplicates of BB.  Note that if all incoming edges are
     threaded, then BB is going to become unreachable.  In that case
     we use BB for one of the duplicates rather than wasting memory
     duplicating BB.  Thus the odd starting condition for the loop.

     Note that for a block with a high outgoing degree we can waste
     a lot of time and memory creating and destroying useless edges.

     So we first duplicate BB and remove the control structure at the
     tail of the duplicate as well as all outgoing edges from the
     duplicate.  We then use that duplicate block as a template for
     the rest of the duplicates.  */
  template_block = NULL;
  for (i = (all ? 1 : 0); i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
    {
      struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);

      if (template_block == NULL)
	{
	  create_block_for_threading (bb, rd);
	  template_block = rd->dup_block;
	}
      else
	{
	  create_block_for_threading (template_block, rd);
	}
    }

  /* Now created up edges from the duplicate blocks to their new
     destinations.  Doing this as a separate loop after block creation
     allows us to avoid creating lots of useless edges.  */
  for (i = (all ? 1 : 0); i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
    {
      struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
      tree phi;
      edge e;

      e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU);

      /* If there are any PHI nodes at the destination of the outgoing edge
	 from the duplicate block, then we will need to add a new argument
	 to them.  The argument should have the same value as the argument
	 associated with the outgoing edge stored in RD.  */
      for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
	{
	  int indx = phi_arg_from_edge (phi, rd->outgoing_edge);
	  add_phi_arg (&phi, PHI_ARG_DEF_TREE (phi, indx), e);
	}
    }

  /* The loop above created the duplicate blocks (and the statements
     within the duplicate blocks).  This loop creates PHI nodes for the
     duplicated blocks and redirects the incoming edges into BB to reach
     the duplicates of BB.

     Note that redirecting the edge will change e->pred_next, so we have
     to hold e->pred_next in a temporary. 

     If this turns out to be a performance problem, then we could create
     a list of incoming edges associated with each entry in 
     REDIRECTION_DATA and walk over that list of edges instead.  */
  for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
    {
      edge new_dest = e->aux;

      /* E was not threaded, then there is nothing to do.  */
      if (!new_dest)
	{
	  ei_next (&ei);
	  continue;
	}

      /* Go ahead and clear E->aux.  It's not needed anymore and failure
         to clear it will cause all kinds of unpleasant problems later.  */
      e->aux = NULL;

      /* We know E is an edge we want to thread.  Find the entry associated
         with E's new destination in the REDIRECTION_DATA array.  */
      for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
	{
	  struct redirection_data *rd;

	  rd = VARRAY_GENERIC_PTR (redirection_data, i);

	  /* We have found the right entry if the outgoing edge in this
	     entry matches E's new destination.  Note that if we have not
	     created a duplicate block (rd->dup_block is NULL), then we
	     are going to re-use BB as a duplicate and we do not need
	     to create PHI nodes or redirect the edge.  */
	  if (rd->outgoing_edge == new_dest && rd->dup_block)
	    {
	      edge e2;
	      copy_phis_to_block (rd->dup_block, bb, e);

	      if (dump_file && (dump_flags & TDF_DETAILS))
		fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
			 e->src->index, e->dest->index, rd->dup_block->index);

	      e2 = redirect_edge_and_branch (e, rd->dup_block);
	      PENDING_STMT (e2) = NULL;

	      if ((dump_file && (dump_flags & TDF_DETAILS))
		  && e->src != e2->src)
	      fprintf (dump_file, "    basic block %d created\n",
		       e2->src->index);
	      break;
	    }
	}
    }

  /* If all the incoming edges where threaded, then we used BB as one
     of the duplicate blocks.  We need to fixup BB in that case so that
     it no longer has a COND_EXPR or SWITCH_EXPR and reaches one destination
     unconditionally.  */
  if (all)
    {
      struct redirection_data *rd;

      rd = VARRAY_GENERIC_PTR (redirection_data, 0);

      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
		 EDGE_PRED (bb, 0)->src->index, bb->index,
		 EDGE_SUCC (bb, 0)->dest->index);

      remove_ctrl_stmt_and_useless_edges (bb, rd->outgoing_edge->dest);
      EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
      EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
    }

  /* Done with this block.  Clear REDIRECTION_DATA.  */
  VARRAY_CLEAR (redirection_data);
}

/* Walk through all blocks and thread incoming edges to the block's 
   destinations as requested.  This is the only entry point into this
   file.

   Blocks which have one or more incoming edges have INCOMING_EDGE_THREADED
   set in the block's annotation.
   this routine.

   Each edge that should be threaded has the new destination edge stored in
   the original edge's AUX field.

   This routine (or one of its callees) will clear INCOMING_EDGE_THREADED
   in the block annotations and the AUX field in the edges.

   It is the caller's responsibility to fix the dominance information
   and rewrite duplicated SSA_NAMEs back into SSA form.

   Returns true if one or more edges were threaded, false otherwise.   */

bool
thread_through_all_blocks (void)
{
  basic_block bb;
  bool retval = false;

  FOR_EACH_BB (bb)
    {
      if (bb_ann (bb)->incoming_edge_threaded)
	{
	  thread_block (bb);
	  retval = true;
	  bb_ann (bb)->incoming_edge_threaded = false;
	}
    }
  return retval;
}