- updated to 4.1.2-20060530 (rev. 114228)

[packages/gcc.git] / gcc-pr26435-pr20256.patch

*** gcc/gcc/tree-loop-linear.c	(revision 113884)
--- gcc/gcc/tree-loop-linear.c	(working copy)
***************
*** 1,5 ****
  /* Linear Loop transforms
!    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
     Contributed by Daniel Berlin <dberlin@dberlin.org>.
  
  This file is part of GCC.
--- 1,5 ----
  /* Linear Loop transforms
!    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
     Contributed by Daniel Berlin <dberlin@dberlin.org>.
  
  This file is part of GCC.
*************** try_interchange_loops (lambda_trans_matr
*** 243,248 ****
--- 243,249 ----
  void
  linear_transform_loops (struct loops *loops)
  {
+   bool modified = false;
    unsigned int i;
    VEC(tree,heap) *oldivs = NULL;
    VEC(tree,heap) *invariants = NULL;
*************** linear_transform_loops (struct loops *lo
*** 257,263 ****
        lambda_loopnest before, after;
        lambda_trans_matrix trans;
        bool problem = false;
-       bool need_perfect_nest = false;
        /* If it's not a loop nest, we don't want it.
           We also don't handle sibling loops properly, 
           which are loops of the following form:
--- 258,263 ----
*************** linear_transform_loops (struct loops *lo
*** 334,345 ****
  	    fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
  	  continue;
  	}
!       if (!perfect_nest_p (loop_nest))
! 	need_perfect_nest = true;
!       before = gcc_loopnest_to_lambda_loopnest (loops,
! 						loop_nest, &oldivs, 
! 						&invariants,
! 						need_perfect_nest);
        if (!before)
  	continue;
              
--- 334,342 ----
  	    fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
  	  continue;
  	}
! 
!       before = gcc_loopnest_to_lambda_loopnest (loops, loop_nest, &oldivs, 
! 						&invariants);
        if (!before)
  	continue;
              
*************** linear_transform_loops (struct loops *lo
*** 357,362 ****
--- 354,361 ----
  	}
        lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
  				       after, trans);
+       modified = true;
+ 
        if (dump_file)
  	fprintf (dump_file, "Successfully transformed loop.\n");
        free_dependence_relations (dependence_relations);
*************** linear_transform_loops (struct loops *lo
*** 365,369 ****
    VEC_free (tree, heap, oldivs);
    VEC_free (tree, heap, invariants);
    scev_reset ();
!   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
  }
--- 364,370 ----
    VEC_free (tree, heap, oldivs);
    VEC_free (tree, heap, invariants);
    scev_reset ();
! 
!   if (modified)
!     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
  }
*** gcc/gcc/lambda.h	(revision 113884)
--- gcc/gcc/lambda.h	(working copy)
***************
*** 1,5 ****
  /* Lambda matrix and vector interface.
!    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
     Contributed by Daniel Berlin <dberlin@dberlin.org>
  
  This file is part of GCC.
--- 1,5 ----
  /* Lambda matrix and vector interface.
!    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
     Contributed by Daniel Berlin <dberlin@dberlin.org>
  
  This file is part of GCC.
*************** void print_lambda_body_vector (FILE *, l
*** 200,207 ****
  lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
  						 struct loop *,
  						 VEC(tree,heap) **,
! 						 VEC(tree,heap) **,
! 						 bool);
  void lambda_loopnest_to_gcc_loopnest (struct loop *,
  				      VEC(tree,heap) *, VEC(tree,heap) *,
  				      lambda_loopnest, lambda_trans_matrix);
--- 200,206 ----
  lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
  						 struct loop *,
  						 VEC(tree,heap) **,
! 						 VEC(tree,heap) **);
  void lambda_loopnest_to_gcc_loopnest (struct loop *,
  				      VEC(tree,heap) *, VEC(tree,heap) *,
  				      lambda_loopnest, lambda_trans_matrix);
*** gcc/gcc/lambda-code.c	(revision 113884)
--- gcc/gcc/lambda-code.c	(working copy)
***************
*** 1,5 ****
  /*  Loop transformation code generation
!     Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
      Contributed by Daniel Berlin <dberlin@dberlin.org>
  
      This file is part of GCC.
--- 1,5 ----
  /*  Loop transformation code generation
!     Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
      Contributed by Daniel Berlin <dberlin@dberlin.org>
  
      This file is part of GCC.
*************** static lambda_lattice lambda_lattice_new
*** 149,154 ****
--- 149,155 ----
  static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
  
  static tree find_induction_var_from_exit_cond (struct loop *);
+ static bool can_convert_to_perfect_nest (struct loop *);
  
  /* Create a new lambda body vector.  */
  
*************** DEF_VEC_ALLOC_P(lambda_loop,heap);
*** 1498,1511 ****
  
  lambda_loopnest
  gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
! 				 struct loop * loop_nest,
  				 VEC(tree,heap) **inductionvars,
! 				 VEC(tree,heap) **invariants,
! 				 bool need_perfect_nest)
  {
    lambda_loopnest ret = NULL;
!   struct loop *temp;
!   int depth = 0;
    size_t i;
    VEC(lambda_loop,heap) *loops = NULL;
    VEC(tree,heap) *uboundvars = NULL;
--- 1499,1511 ----
  
  lambda_loopnest
  gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
! 				 struct loop *loop_nest,
  				 VEC(tree,heap) **inductionvars,
! 				 VEC(tree,heap) **invariants)
  {
    lambda_loopnest ret = NULL;
!   struct loop *temp = loop_nest;
!   int depth = depth_of_nest (loop_nest);
    size_t i;
    VEC(lambda_loop,heap) *loops = NULL;
    VEC(tree,heap) *uboundvars = NULL;
*************** gcc_loopnest_to_lambda_loopnest (struct 
*** 1513,1521 ****
    VEC(int,heap) *steps = NULL;
    lambda_loop newloop;
    tree inductionvar = NULL;
!   
!   depth = depth_of_nest (loop_nest);
!   temp = loop_nest;
    while (temp)
      {
        newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
--- 1513,1523 ----
    VEC(int,heap) *steps = NULL;
    lambda_loop newloop;
    tree inductionvar = NULL;
!   bool perfect_nest = perfect_nest_p (loop_nest);
! 
!   if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest))
!     goto fail;
! 
    while (temp)
      {
        newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
*************** gcc_loopnest_to_lambda_loopnest (struct 
*** 1523,1534 ****
  					 &lboundvars, &uboundvars,
  					 &steps);
        if (!newloop)
! 	return NULL;
        VEC_safe_push (tree, heap, *inductionvars, inductionvar);
        VEC_safe_push (lambda_loop, heap, loops, newloop);
        temp = temp->inner;
      }
!   if (need_perfect_nest)
      {
        if (!perfect_nestify (currloops, loop_nest, 
  			    lboundvars, uboundvars, steps, *inductionvars))
--- 1525,1538 ----
  					 &lboundvars, &uboundvars,
  					 &steps);
        if (!newloop)
! 	goto fail;
! 
        VEC_safe_push (tree, heap, *inductionvars, inductionvar);
        VEC_safe_push (lambda_loop, heap, loops, newloop);
        temp = temp->inner;
      }
! 
!   if (!perfect_nest)
      {
        if (!perfect_nestify (currloops, loop_nest, 
  			    lboundvars, uboundvars, steps, *inductionvars))
*************** gcc_loopnest_to_lambda_loopnest (struct 
*** 1542,1550 ****
--- 1546,1557 ----
  	fprintf (dump_file,
  		 "Successfully converted loop nest to perfect loop nest.\n");
      }
+ 
    ret = lambda_loopnest_new (depth, 2 * depth);
+ 
    for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
      LN_LOOPS (ret)[i] = newloop;
+ 
   fail:
    VEC_free (lambda_loop, heap, loops);
    VEC_free (tree, heap, uboundvars);
*************** replace_uses_equiv_to_x_with_y (struct l
*** 2156,2168 ****
      {
        tree use = USE_FROM_PTR (use_p);
        tree step = NULL_TREE;
!       tree access_fn = NULL_TREE;
!       
!       
!       access_fn = instantiate_parameters
! 	(loop, analyze_scalar_evolution (loop, use));
!       if (access_fn != NULL_TREE && access_fn != chrec_dont_know)
! 	step = evolution_part_in_loop_num (access_fn, loop->num);
        if ((step && step != chrec_dont_know 
  	   && TREE_CODE (step) == INTEGER_CST
  	   && int_cst_value (step) == xstep)
--- 2163,2174 ----
      {
        tree use = USE_FROM_PTR (use_p);
        tree step = NULL_TREE;
!       tree scev = instantiate_parameters (loop,
! 					  analyze_scalar_evolution (loop, use));
! 
!       if (scev != NULL_TREE && scev != chrec_dont_know)
! 	step = evolution_part_in_loop_num (scev, loop->num);
! 
        if ((step && step != chrec_dont_know 
  	   && TREE_CODE (step) == INTEGER_CST
  	   && int_cst_value (step) == xstep)
*************** replace_uses_equiv_to_x_with_y (struct l
*** 2171,2192 ****
      }
  }
  
- /* Return TRUE if STMT uses tree OP in it's uses.  */
- 
- static bool
- stmt_uses_op (tree stmt, tree op)
- {
-   ssa_op_iter iter;
-   tree use;
- 
-   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
-     {
-       if (use == op)
- 	return true;
-     }
-   return false;
- }
- 
  /* Return true if STMT is an exit PHI for LOOP */
  
  static bool
--- 2177,2182 ----
*************** can_put_in_inner_loop (struct loop *inne
*** 2236,2250 ****
    
  }
  
  
! /* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect
!    one.  LOOPIVS is a vector of induction variables, one per loop.  
!    ATM, we only handle imperfect nests of depth 2, where all of the statements
!    occur after the inner loop.  */
  
  static bool
! can_convert_to_perfect_nest (struct loop *loop,
! 			     VEC(tree,heap) *loopivs)
  {
    basic_block *bbs;
    tree exit_condition, phi;
--- 2226,2264 ----
    
  }
  
+ /* Return true if STMT can be put *after* the inner loop of LOOP.  */
+ 
+ static bool
+ can_put_after_inner_loop (struct loop *loop, tree stmt)
+ {
+   imm_use_iterator imm_iter;
+   use_operand_p use_p;
+ 
+   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+     return false;
+   
+   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0))
+     {
+       if (!exit_phi_for_loop_p (loop, USE_STMT (use_p)))
+ 	{
+ 	  basic_block immbb = bb_for_stmt (USE_STMT (use_p));
+ 	  
+ 	  if (!dominated_by_p (CDI_DOMINATORS,
+ 			       immbb,
+ 			       loop->inner->header)
+ 	      && !can_put_in_inner_loop (loop->inner, stmt))
+ 	    return false;
+ 	}
+     }
+   return true;
+ }
  
! /* Return TRUE if LOOP is an imperfect nest that we can convert to a
!    perfect one.  At the moment, we only handle imperfect nests of
!    depth 2, where all of the statements occur after the inner loop.  */
  
  static bool
! can_convert_to_perfect_nest (struct loop *loop)
  {
    basic_block *bbs;
    tree exit_condition, phi;
*************** can_convert_to_perfect_nest (struct loop
*** 2264,2282 ****
  	{
  	  for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
  	    { 
- 	      size_t j;
  	      tree stmt = bsi_stmt (bsi);
! 	      tree iv;
! 	      
  	      if (stmt == exit_condition
  		  || not_interesting_stmt (stmt)
  		  || stmt_is_bumper_for_loop (loop, stmt))
  		continue;
! 	      /* If the statement uses inner loop ivs, we == screwed.  */
! 	      for (j = 1; VEC_iterate (tree, loopivs, j, iv); j++)
! 		if (stmt_uses_op (stmt, iv))
! 		  goto fail;
! 	      
  	      /* If this is a simple operation like a cast that is invariant
  		 in the inner loop, only used there, and we can place it
  		 there, then it's not going to hurt us.
--- 2278,2290 ----
  	{
  	  for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
  	    { 
  	      tree stmt = bsi_stmt (bsi);
! 
  	      if (stmt == exit_condition
  		  || not_interesting_stmt (stmt)
  		  || stmt_is_bumper_for_loop (loop, stmt))
  		continue;
! 
  	      /* If this is a simple operation like a cast that is invariant
  		 in the inner loop, only used there, and we can place it
  		 there, then it's not going to hurt us.
*************** can_convert_to_perfect_nest (struct loop
*** 2286,2295 ****
  		 theory that we are going to gain a lot more by interchanging
  		 the loop than we are by leaving some invariant code there for
  		 some other pass to clean up.  */
! 	      if (TREE_CODE (stmt) == MODIFY_EXPR
! 		  && is_gimple_cast (TREE_OPERAND (stmt, 1))
! 		  && can_put_in_inner_loop (loop->inner, stmt))
! 		continue;
  
  	      /* Otherwise, if the bb of a statement we care about isn't
  		 dominated by the header of the inner loop, then we can't
--- 2294,2358 ----
  		 theory that we are going to gain a lot more by interchanging
  		 the loop than we are by leaving some invariant code there for
  		 some other pass to clean up.  */
! 	      if (TREE_CODE (stmt) == MODIFY_EXPR)
! 		{
! 		  use_operand_p use_a, use_b;
! 		  imm_use_iterator imm_iter;
! 		  ssa_op_iter op_iter, op_iter1;
! 		  tree op0 = TREE_OPERAND (stmt, 0);
! 		  tree scev = instantiate_parameters
! 		    (loop, analyze_scalar_evolution (loop, op0));
! 
! 		  /* If the IV is simple, it can be duplicated.  */
! 		  if (!automatically_generated_chrec_p (scev))
! 		    {
! 		      tree step = evolution_part_in_loop_num (scev, loop->num);
! 		      if (step && step != chrec_dont_know 
! 			  && TREE_CODE (step) == INTEGER_CST)
! 			continue;
! 		    }
! 
! 		  /* The statement should not define a variable used
! 		     in the inner loop.  */
! 		  if (TREE_CODE (op0) == SSA_NAME)
! 		    FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
! 		      if (bb_for_stmt (USE_STMT (use_a))->loop_father
! 			  == loop->inner)
! 			goto fail;
! 
! 		  FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
! 		    {
! 		      tree node, op = USE_FROM_PTR (use_a);
! 
! 		      /* The variables should not be used in both loops.  */
! 		      FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
! 		      if (bb_for_stmt (USE_STMT (use_b))->loop_father
! 			  == loop->inner)
! 			goto fail;
! 
! 		      /* The statement should not use the value of a
! 			 scalar that was modified in the loop.  */
! 		      node = SSA_NAME_DEF_STMT (op);
! 		      if (TREE_CODE (node) == PHI_NODE)
! 			FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
! 			  {
! 			    tree arg = USE_FROM_PTR (use_b);
! 
! 			    if (TREE_CODE (arg) == SSA_NAME)
! 			      {
! 				tree arg_stmt = SSA_NAME_DEF_STMT (arg);
! 
! 				if (bb_for_stmt (arg_stmt)->loop_father
! 				    == loop->inner)
! 				  goto fail;
! 			      }
! 			  }
! 		    }
! 
! 		  if (can_put_in_inner_loop (loop->inner, stmt)
! 		      || can_put_after_inner_loop (loop, stmt))
! 		    continue;
! 		}
  
  	      /* Otherwise, if the bb of a statement we care about isn't
  		 dominated by the header of the inner loop, then we can't
*************** perfect_nestify (struct loops *loops,
*** 2379,2392 ****
    tree stmt;
    tree oldivvar, ivvar, ivvarinced;
    VEC(tree,heap) *phis = NULL;
! 
!   if (!can_convert_to_perfect_nest (loop, loopivs))
!     return false;
! 
!   /* Create the new loop */
! 
    olddest = loop->single_exit->dest;
!   preheaderbb =  loop_split_edge_with (loop->single_exit, NULL);
    headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
    
    /* Push the exit phi nodes that we are moving.  */
--- 2442,2451 ----
    tree stmt;
    tree oldivvar, ivvar, ivvarinced;
    VEC(tree,heap) *phis = NULL;
!   
!   /* Create the new loop.  */
    olddest = loop->single_exit->dest;
!   preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
    headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
    
    /* Push the exit phi nodes that we are moving.  */
*************** perfect_nestify (struct loops *loops,
*** 2552,2561 ****
  		      continue;
  		    }
  		  
! 		  replace_uses_equiv_to_x_with_y (loop, stmt, 
! 						  oldivvar,  
! 						  VEC_index (int, steps, 0),
! 						  ivvar);
  		  bsi_move_before (&bsi, &tobsi);
  		  
  		  /* If the statement has any virtual operands, they may
--- 2611,2619 ----
  		      continue;
  		    }
  		  
! 		  replace_uses_equiv_to_x_with_y 
! 		    (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar);
! 
  		  bsi_move_before (&bsi, &tobsi);
  		  
  		  /* If the statement has any virtual operands, they may