tree-ssa-loop-ivopts.c: New file.

	* tree-ssa-loop-ivopts.c: New file.
	* Makefile.in (tree-ssa-loop-ivopts.c): Add.
	* cfgloop.h (target_avail_regs, target_res_regs, target_small_cost,
	target_pres_cost, target_spill_cost): Declare.
	* cfgloopanal.c (avail_regs, res_regs, small_cost, pres_cost,
	spill_cost): Renamed to ...
	(target_avail_regs, target_res_regs, target_small_cost,
	target_pres_cost, target_spill_cost): ... and exported.
	(init_set_costs, global_cost_for_size): Work with renamed variables.
	* common.opt (flag_ivopts): New flag.
	* expr.c (expand_expr_real_1): Handle SSA_NAME case.  Handle
	REF_ORIGINAL.
	* gimplify.c (struct gimplify_ctx): Add into_ssa field.
	(internal_get_tmp_var, gimplify_modify_expr, gimplify_expr): Support
	generating SSA form.
	(force_gimple_operand): New function.
	* timevar.def (TV_TREE_LOOP_IVOPTS): New timevar.
	* tree-cfg.c (stmt_bsi): New function.
	* params.def (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND,
	PARAM_IV_MAX_CONSIDERED_USES): New.
	* tree-flow.h (stmt_bsi, tree_ssa_iv_optimize, split_loop_exit_edge,
	bsi_insert_on_edge_immediate_loop. standard_iv_increment_position,
	ip_end_pos, ip_normal_pos, force_gimple_operand): Declare.
	* tree-gimple.c (is_gimple_formal_tmp_var): Accept ssa names.
	* tree-nested.c (build_addr): Export.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_iv_optimize.
	* tree-pass.h (pass_iv_optimize): Declare.
	* tree-ssa-loop-im.c (for_each_index): Handle REALPART_EXPR and
	IMAGPART_EXPR.
	* tree-ssa-loop-manip.c (create_iv): Force the base to be acceptable
	as a phi node argument.
	(split_loop_exit_edge, bsi_insert_on_edge_immediate_loop,
	ip_end_pos, ip_normal_pos, standard_iv_increment_position): New
	functions.
	* tree-ssa-loop-niter.c (zero_p, unsigned_type_for): Export.
	* tree-ssa-loop.c (tree_ssa_loop_ivopts, gate_tree_ssa_loop_ivopts,
	pass_iv_optimize): New pass.
	* tree-ssa-operands.c (get_indirect_ref_operands): Handle REF_ORIGINAL.
	* tree-ssanames.c (release_ssa_name): Allow calling with var = NULL.
	* tree.c (build_int_cst_type, cst_and_fits_in_hwi): New functions.
	* tree.h (REF_ORIGINAL): New macro.
	(build_int_cst_type, unsigned_type_for, zero_p,
	cst_and_fits_in_hwi, build_addr): Declare.
	* doc/invoke.texi (-fivopts): Document.
	(PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND,
	PARAM_IV_MAX_CONSIDERED_USES): Document.
	* doc/passes.texi: Document induction variable optimizations pass.

	* gcc.dg/tree-ssa/loop-2.c: New test.
	* gcc.dg/tree-ssa/loop-3.c: New test.
	* gcc.dg/tree-ssa/loop-4.c: New test.
	* gcc.dg/tree-ssa/loop-5.c: New test.

From-SVN: r87100

1 files changed, 119 insertions, 2 deletions

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index edb821d..51e29fd 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -50,7 +50,7 @@ create_iv (tree base, tree step, tree var, struct loop *loop,
 	   block_stmt_iterator *incr_pos, bool after,
 	   tree *var_before, tree *var_after)
 {
-  tree stmt, initial, step1;
+  tree stmt, initial, step1, stmts;
   tree vb, va;
   enum tree_code incr_op = PLUS_EXPR;
 
@@ -100,7 +100,13 @@ create_iv (tree base, tree step, tree var, struct loop *loop,
   else
     bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
 
-  initial = base;
+  initial = force_gimple_operand (base, &stmts, true, var);
+  if (stmts)
+    {
+      edge pe = loop_preheader_edge (loop);
+
+      bsi_insert_on_edge_immediate_loop (pe, stmts);
+    }
 
   stmt = create_phi_node (vb, loop->header);
   SSA_NAME_DEF_STMT (vb) = stmt;
@@ -382,3 +388,114 @@ verify_loop_closed_ssa (void)
 	check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
     }
 }
+
+/* Split loop exit edge EXIT.  The things are a bit complicated by a need to
+   preserve the loop closed ssa form.  */
+
+void
+split_loop_exit_edge (edge exit)
+{
+  basic_block dest = exit->dest;
+  basic_block bb = loop_split_edge_with (exit, NULL);
+  tree phi, new_phi, new_name;
+  use_operand_p op_p;
+
+  for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
+    {
+      op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, bb->succ);
+
+      new_name = duplicate_ssa_name (USE_FROM_PTR (op_p), NULL);
+      new_phi = create_phi_node (new_name, bb);
+      SSA_NAME_DEF_STMT (new_name) = new_phi;
+      add_phi_arg (&new_phi, USE_FROM_PTR (op_p), exit);
+      SET_USE (op_p, new_name);
+    }
+}
+
+/* Insert statement STMT to the edge E and update the loop structures.
+   Returns the newly created block (if any).  */
+
+basic_block
+bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
+{
+  basic_block src, dest, new_bb;
+  struct loop *loop_c;
+
+  src = e->src;
+  dest = e->dest;
+
+  loop_c = find_common_loop (src->loop_father, dest->loop_father);
+
+  new_bb = bsi_insert_on_edge_immediate (e, stmt);
+
+  if (!new_bb)
+    return NULL;
+
+  add_bb_to_loop (new_bb, loop_c);
+  if (dest->loop_father->latch == src)
+    dest->loop_father->latch = new_bb;
+
+  return new_bb;
+}
+
+/* Returns the basic block in that statements should be emitted for induction
+   variables incremented at the end of the LOOP.  */
+
+basic_block
+ip_end_pos (struct loop *loop)
+{
+  return loop->latch;
+}
+
+/* Returns the basic block in that statements should be emitted for induction
+   variables incremented just before exit condition of a LOOP.  */
+
+basic_block
+ip_normal_pos (struct loop *loop)
+{
+  tree last;
+  basic_block bb;
+  edge exit;
+
+  if (loop->latch->pred->pred_next)
+    return NULL;
+
+  bb = loop->latch->pred->src;
+  last = last_stmt (bb);
+  if (TREE_CODE (last) != COND_EXPR)
+    return NULL;
+
+  exit = bb->succ;
+  if (exit->dest == loop->latch)
+    exit = exit->succ_next;
+
+  if (flow_bb_inside_loop_p (loop, exit->dest))
+    return NULL;
+
+  return bb;
+}
+
+/* Stores the standard position for induction variable increment in LOOP
+   (just before the exit condition if it is available and latch block is empty,
+   end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
+   the increment should be inserted after *BSI.  */
+
+void
+standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
+				bool *insert_after)
+{
+  basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
+  tree last = last_stmt (latch);
+
+  if (!bb
+      || (last && TREE_CODE (last) != LABEL_EXPR))
+    {
+      *bsi = bsi_last (latch);
+      *insert_after = true;
+    }
+  else
+    {
+      *bsi = bsi_last (bb);
+      *insert_after = false;
+    }
+}