CbC/CbC_gcc: gcc/tree-ssa-dce.c comparison

comparison gcc/tree-ssa-dce.c @ 63:b7f97abdc517 gcc-4.6-20100522

update gcc from gcc-4.5.0 to gcc-4.6

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Mon, 24 May 2010 12:47:05 +0900
parents	77e2b8dfacca
children	f6334be47118

comparison

equal deleted inserted replaced

-:3c8a44c06a95
+:b7f97abdc517
 /* Dead code elimination pass for the GNU compiler.
-Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
+Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
 Free Software Foundation, Inc.
 Contributed by Ben Elliston <bje@redhat.com>
 and Andrew MacLeod <amacleod@redhat.com>
 Adapted to use control dependence by Steven Bosscher, SUSE Labs.
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
-#include "ggc.h"
-/* These RTL headers are needed for basic-block.h.  */
-#include "rtl.h"
-#include "tm_p.h"
-#include "hard-reg-set.h"
-#include "obstack.h"
-#include "basic-block.h"
 #include "tree.h"
 #include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
+#include "basic-block.h"
 #include "tree-flow.h"
 #include "gimple.h"
 #include "tree-dump.h"
 #include "tree-pass.h"
 #include "timevar.h"
 }
 /* Make corresponding control dependent edges necessary.  We only
 have to do this once for each basic block, so we clear the bitmap
-after we're done.  */
+after we're done.
+When IGNORE_SELF it true, ignore BB from the list of control dependences.  */
 static void
-mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
+mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el, bool ignore_self)
 {
 bitmap_iterator bi;
 unsigned edge_number;
+bool skipped = false;
 gcc_assert (bb != EXIT_BLOCK_PTR);
 if (bb == ENTRY_BLOCK_PTR)
 return;
 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
 {
 gimple stmt;
 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
+if (ignore_self && cd_bb == bb)
+	{
+	  skipped = true;
+	  continue;
+	}
 if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 	continue;
 SET_BIT (last_stmt_necessary, cd_bb->index);
 SET_BIT (bb_contains_live_stmts, cd_bb->index);
 stmt = last_stmt (cd_bb);
 if (stmt && is_ctrl_stmt (stmt))
 	mark_stmt_necessary (stmt, true);
 }
+if (!skipped)
+SET_BIT (visited_control_parents, bb->index);
 }
 /* Find obviously necessary statements.  These are things like most function
 calls, and stores to file level variables.
 		  && (e->flags & EDGE_IRREDUCIBLE_LOOP))
 		{
 	          if (dump_file)
 	            fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
 		    	     e->src->index, e->dest->index);
-		  mark_control_dependent_edges_necessary (e->dest, el);
+		  mark_control_dependent_edges_necessary (e->dest, el, false);
 		}
 	  }
 FOR_EACH_LOOP (li, loop, 0)
 	if (!finite_loop_p (loop))
 	  {
 	    if (dump_file)
 	      fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
-	    mark_control_dependent_edges_necessary (loop->latch, el);
+	    mark_control_dependent_edges_necessary (loop->latch, el, false);
 	  }
 scev_finalize ();
 }
 }
 	     containing STMT is control dependent on, but only if we haven't
 	     already done so.  */
 	  basic_block bb = gimple_bb (stmt);
 	  if (bb != ENTRY_BLOCK_PTR
 	      && ! TEST_BIT (visited_control_parents, bb->index))
-	    {
+	    mark_control_dependent_edges_necessary (bb, el, false);
-	      SET_BIT (visited_control_parents, bb->index);
-	      mark_control_dependent_edges_necessary (bb, el);
-	    }
 	}
 if (gimple_code (stmt) == GIMPLE_PHI
 	  /* We do not process virtual PHI nodes nor do we track their
 	     necessity.  */
 	      tree arg = PHI_ARG_DEF (stmt, k);
 	      if (TREE_CODE (arg) == SSA_NAME)
 		mark_operand_necessary (arg);
 	    }
+	  /* For PHI operands it matters from where the control flow arrives
+	     to the BB.  Consider the following example:
+	     a=exp1;
+	     b=exp2;
+	     if (test)
+		;
+	     else
+		;
+	     c=PHI(a,b)
+	     We need to mark control dependence of the empty basic blocks, since they
+	     contains computation of PHI operands.
+	     Doing so is too restrictive in the case the predecestor block is in
+	     the loop. Consider:
+	      if (b)
+		{
+		  int i;
+		  for (i = 0; i<1000; ++i)
+		    ;
+		  j = 0;
+		}
+	      return j;
+	     There is PHI for J in the BB containing return statement.
+	     In this case the control dependence of predecestor block (that is
+	     within the empty loop) also contains the block determining number
+	     of iterations of the block that would prevent removing of empty
+	     loop in this case.
+	     This scenario can be avoided by splitting critical edges.
+	     To save the critical edge splitting pass we identify how the control
+	     dependence would look like if the edge was split.
+	     Consider the modified CFG created from current CFG by splitting
+	     edge B->C.  In the postdominance tree of modified CFG, C' is
+	     always child of C.  There are two cases how chlids of C' can look
+	     like:
+		1) C' is leaf
+		   In this case the only basic block C' is control dependent on is B.
+		2) C' has single child that is B
+		   In this case control dependence of C' is same as control
+		   dependence of B in original CFG except for block B itself.
+		   (since C' postdominate B in modified CFG)
+	     Now how to decide what case happens?  There are two basic options:
+		a) C postdominate B.  Then C immediately postdominate B and
+		   case 2 happens iff there is no other way from B to C except
+		   the edge B->C.
+		   There is other way from B to C iff there is succesor of B that
+		   is not postdominated by B.  Testing this condition is somewhat
+		   expensive, because we need to iterate all succesors of B.
+		   We are safe to assume that this does not happen: we will mark B
+		   as needed when processing the other path from B to C that is
+		   conrol dependent on B and marking control dependencies of B
+		   itself is harmless because they will be processed anyway after
+		   processing control statement in B.
+		b) C does not postdominate B.  Always case 1 happens since there is
+		   path from C to exit that does not go through B and thus also C'.  */
 	  if (aggressive && !degenerate_phi_p (stmt))
 	    {
 	      for (k = 0; k < gimple_phi_num_args (stmt); k++)
 		{
 		  basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
-		  if (arg_bb != ENTRY_BLOCK_PTR
-		      && ! TEST_BIT (visited_control_parents, arg_bb->index))
+		  if (gimple_bb (stmt)
+		      != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
 		    {
-		      SET_BIT (visited_control_parents, arg_bb->index);
+		      if (!TEST_BIT (last_stmt_necessary, arg_bb->index))
-		      mark_control_dependent_edges_necessary (arg_bb, el);
+			{
+			  gimple stmt2;
+			  SET_BIT (last_stmt_necessary, arg_bb->index);
+			  SET_BIT (bb_contains_live_stmts, arg_bb->index);
+			  stmt2 = last_stmt (arg_bb);
+			  if (stmt2 && is_ctrl_stmt (stmt2))
+			    mark_stmt_necessary (stmt2, true);
+			}
 		    }
+		  else if (arg_bb != ENTRY_BLOCK_PTR
+		           && ! TEST_BIT (visited_control_parents, arg_bb->index))
+		    mark_control_dependent_edges_necessary (arg_bb, el, true);
 		}
 	    }
 	}
 else
 	{
 gsi_next (&gsi);
 }
 return something_changed;
 }
-/* Find first live post dominator of BB.  */
-static basic_block
-get_live_post_dom (basic_block bb)
-{
-basic_block post_dom_bb;
-/* The post dominance info has to be up-to-date.  */
-gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
-/* Get the immediate post dominator of bb.  */
-post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
-/* And look for first live one.  */
-while (post_dom_bb != EXIT_BLOCK_PTR
-	 && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index))
-post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb);
-return post_dom_bb;
-}
 /* Forward edge E to respective POST_DOM_BB and update PHIs.  */
 static edge
 forward_edge_to_pdom (edge e, basic_block post_dom_bb)
 {
 /* If edge was already around, no updating is neccesary.  */
 if (e2 != e)
 return e2;
-if (phi_nodes (post_dom_bb))
+if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
 {
 /* We are sure that for every live PHI we are seeing control dependent BB.
-This means that we can look up the end of control dependent path leading
+This means that we can pick any edge to duplicate PHI args from.  */
-to the PHI itself.  */
 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
-	if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
+	if (e2 != e)
 	  break;
 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
 	{
 	  gimple phi = gsi_stmt (gsi);
 	  tree op;
 	  source_location locus;
-	  /* Dead PHI do not imply control dependency.  */
+	  /* PHIs for virtuals have no control dependency relation on them.
-if (!gimple_plf (phi, STMT_NECESSARY)
+	     We are lost here and must force renaming of the symbol.  */
-	      && is_gimple_reg (gimple_phi_result (phi)))
-	    {
-	      gsi_next (&gsi);
-	      continue;
-	    }
-	  if (gimple_phi_arg_def (phi, e->dest_idx))
-	    {
-	      gsi_next (&gsi);
-	      continue;
-	    }
-	  /* We didn't find edge to update.  This can happen for PHIs on virtuals
-	     since there is no control dependency relation on them.  We are lost
-	     here and must force renaming of the symbol.  */
 	  if (!is_gimple_reg (gimple_phi_result (phi)))
 	    {
 	      mark_virtual_phi_result_for_renaming (phi);
 	      remove_phi_node (&gsi, true);
 	      continue;
 	    }
-	  if (!e2)
+	  /* Dead PHI do not imply control dependency.  */
+if (!gimple_plf (phi, STMT_NECESSARY))
 	    {
-	      op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0);
+	      gsi_next (&gsi);
-	      locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0);
+	      continue;
 	    }
-	  else
-	    {
+	  op = gimple_phi_arg_def (phi, e2->dest_idx);
-	      op = gimple_phi_arg_def (phi, e2->dest_idx);
+	  locus = gimple_phi_arg_location (phi, e2->dest_idx);
-	      locus = gimple_phi_arg_location (phi, e2->dest_idx);
-	    }
 	  add_phi_arg (phi, op, e, locus);
-	  gcc_assert (e2 || degenerate_phi_p (phi));
+	  /* The resulting PHI if not dead can only be degenerate.  */
+	  gcc_assert (degenerate_phi_p (phi));
 	  gsi_next (&gsi);
 	}
 }
 return e;
 }
 {
 basic_block post_dom_bb;
 edge e, e2;
 edge_iterator ei;
-post_dom_bb = get_live_post_dom (bb);
+post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 e = find_edge (bb, post_dom_bb);
 /* If edge is already there, try to use it.  This avoids need to update
 PHI nodes.  Also watch for cases where post dominator does not exists

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-dce.c @ 63:b7f97abdc517 gcc-4.6-20100522