[patch] Fix PR27745 loop-linear code gen

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

Hi,

the problem in pr27745 is that perfect nestify is duplicating too much
code, and is infinitely looping over a same statement that is copied
again and again:

        pretmp.24_42 = pretmp.24_9 + -101;
	[...]
        D.1266_29 = pretmp.24_42;
        D.1267_30 = D.1265_28 + pretmp.24_42;

is transformed to the following code:

        pretmp.24_50 = pretmp.24_9 + -101;
        pretmp.24_49 = pretmp.24_9 + -101;
        D.1266_29 = pretmp.24_50;
        D.1267_30 = D.1265_28 + pretmp.24_49;

The same statement is duplicated with different names the number of
imm_uses times!  By the way, why are the uses of a SSA_NAME called
immediate uses?  Is that they are the uses of the same declaration,
i.e. scalar dependences with a distance 1, in contrast to transitive
scalar dependences?

The solution is to not copy the statements but instead move them to
the inner loop.  This transformation is safe because if there are
other statements in the outer loop that use the variables defined by
the moved statements, they are either also moved in the inner loop, or
moved to the next loop.  If the other uses cannot be moved from the
outer loop, can_convert_to_perfect_nest should return false.

Bootstrapped and tested on amd64-linux.  Okay for trunk?

Sebastian

	* lambda-code.c (perfect_nestify): Don't copy statements
	in the inner loop: move them to the inner loop header.

Index: lambda-code.c
===================================================================
*** lambda-code.c	(revision 114040)
--- lambda-code.c	(working copy)
*************** perfect_nestify (struct loops *loops,
*** 2506,2555 ****
  
  	  if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
  	    {
! 	      for (bsi = bsi_last (bbs[i]); !bsi_end_p (bsi);)
  		{ 
- 		  use_operand_p use_p;
- 		  imm_use_iterator imm_iter;
- 		  tree imm_stmt;
  		  tree stmt = bsi_stmt (bsi);
  
  		  if (stmt == exit_condition
  		      || not_interesting_stmt (stmt)
  		      || stmt_is_bumper_for_loop (loop, stmt))
  		    {
! 		      if (!bsi_end_p (bsi))
! 			bsi_prev (&bsi);
  		      continue;
  		    }
! 		  
! 		  /* Make copies of this statement to put it back next
! 		     to its uses.  */
! 		  FOR_EACH_IMM_USE_STMT (imm_stmt, imm_iter, 
! 					 TREE_OPERAND (stmt, 0))
! 		    {
! 		      if (!exit_phi_for_loop_p (loop->inner, imm_stmt))
! 			{
! 			  block_stmt_iterator tobsi;
! 			  tree newname;
! 			  tree newstmt;
! 			 
! 			  newstmt  = unshare_expr (stmt);
! 			  tobsi = bsi_after_labels (bb_for_stmt (imm_stmt));
! 			  newname = TREE_OPERAND (newstmt, 0);
! 			  newname = SSA_NAME_VAR (newname);
! 			  newname = make_ssa_name (newname, newstmt);
! 			  TREE_OPERAND (newstmt, 0) = newname;
! 
! 			  FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
! 			    SET_USE (use_p, newname);
! 
! 			  bsi_insert_before (&tobsi, newstmt, BSI_SAME_STMT);
! 			  update_stmt (newstmt);
! 			  update_stmt (imm_stmt);
! 			} 
! 		    }
! 		  if (!bsi_end_p (bsi))
! 		    bsi_prev (&bsi);			  
  		}
  	    }
  	  else
--- 2506,2527 ----
  
  	  if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
  	    {
! 	      block_stmt_iterator header_bsi 
! 		= bsi_after_labels (loop->inner->header);
! 
! 	      for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
  		{ 
  		  tree stmt = bsi_stmt (bsi);
  
  		  if (stmt == exit_condition
  		      || not_interesting_stmt (stmt)
  		      || stmt_is_bumper_for_loop (loop, stmt))
  		    {
! 		      bsi_next (&bsi);
  		      continue;
  		    }
! 
! 		  bsi_move_before (&bsi, &header_bsi);
  		}
  	    }
  	  else