cfganal.h (rev_post_order_and_mark_dfs_back_seme): Declare.

2018-08-27  Richard Biener  <rguenther@suse.de>

	* cfganal.h (rev_post_order_and_mark_dfs_back_seme): Declare.
	* cfganal.c (rev_post_order_and_mark_dfs_back_seme): New function.

	* tree-ssa-sccvn.h (struct vn_pval): New structure.
	(struct vn_nary_op_s): Add unwind_to member.  Add
	predicated_values flag and put result into a union together
	with a linked list of vn_pval.
	(struct vn_ssa_aux): Add name member to make maintaining
	a map of SSA name to vn_ssa_aux possible.  Remove no longer
	needed info, dfsnum, low, visited, on_sccstack, use_processed
	and range_info_anti_range_p members.
	(run_scc_vn, vn_eliminate, free_scc_vn, vn_valueize): Remove.
	(do_rpo_vn, run_rpo_vn, eliminate_with_rpo_vn, free_rpo_vn):
	New functions.
	(vn_valueize): New global.
	(vn_context_bb): Likewise.
	(VN_INFO_RANGE_INFO, VN_INFO_ANTI_RANGE_P, VN_INFO_RANGE_TYPE,
	VN_INFO_PTR_INFO): Remove.
	* tree-ssa-sccvn.c: ... (rewrite)
	(pass_fre::execute): For -O2+ initialize loops and run
	RPO VN in optimistic mode (iterating).  For -O1 and -Og
	run RPO VN in non-optimistic mode.
	* params.def (PARAM_SCCVN_MAX_SCC_SIZE): Remove.
	(PARAM_RPO_VN_MAX_LOOP_DEPTH): Add.
	* doc/invoke.texi (sccvn-max-scc-size): Remove.
	(rpo-vn-max-loop-depth): Document.
	* tree-ssa-alias.c (walk_non_aliased_vuses): Stop walking
	when valuezing the VUSE signals we walked out of the region.
	* tree-ssa-pre.c (phi_translate_1): Ignore predicated values.
	(phi_translate): Set VN context block to use for availability
	lookup.
	(compute_avail): Likewise.
	(pre_valueize): New function.
	(pass_pre::execute): Adjust to the RPO VN API.

	* tree-ssa-loop-ivcanon.c: Include tree-ssa-sccvn.h.
	(propagate_constants_for_unrolling): Remove.
	(tree_unroll_loops_completely): Perform value-numbering
	on the unrolled bodies loop parent.

	* g++.dg/torture/20180705-1.C: New testcase.
	* gcc.dg/tree-ssa/ssa-fre-67.c: Likewise.
	* gcc.dg/tree-ssa/ssa-ccp-14.c: Scan FRE dump.
	* gcc.dg/tree-ssa/ssa-fre-46.c: Use -O2.
	* gcc.dg/tree-ssa/vrp92.c: Disable FRE.
	* gcc.dg/pr83666.c: Drop --param=sccvn-max-scc-size option.
	* gcc.dg/pr85195.c: Likewise.
	* gcc.dg/pr85467.c: Likewise.
	* gcc.dg/torture/pr81790.c: Likewise.

	* gfortran.dg/reassoc_4.f: Change max-completely-peeled-insns
	param to current default.

From-SVN: r263875

1 files changed, 69 insertions, 21 deletions

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 5e973eb..2dce88b 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -677,10 +677,10 @@ get_expr_value_id (pre_expr expr)
   return id;
 }
 
-/* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL.  */
+/* Return a VN valnum (SSA name or constant) for the PRE value-id VAL.  */
 
 static tree
-sccvn_valnum_from_value_id (unsigned int val)
+vn_valnum_from_value_id (unsigned int val)
 {
   bitmap_iterator bi;
   unsigned int i;
@@ -1308,9 +1308,9 @@ get_representative_for (const pre_expr e, basic_block b = NULL)
      ???  We should be able to re-use this when we insert the statement
      to compute it.  */
   name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
-  VN_INFO_GET (name)->value_id = value_id;
+  VN_INFO (name)->value_id = value_id;
   VN_INFO (name)->valnum = valnum ? valnum : name;
-  /* ???  For now mark this SSA name for release by SCCVN.  */
+  /* ???  For now mark this SSA name for release by VN.  */
   VN_INFO (name)->needs_insertion = true;
   add_to_value (value_id, get_or_alloc_expr_for_name (name));
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1404,7 +1404,22 @@ phi_translate_1 (bitmap_set_t dest,
 			constant = find_leader_in_sets (value_id, dest,
 							AVAIL_OUT (pred));
 			if (constant)
-			  return constant;
+			  {
+			    if (dump_file && (dump_flags & TDF_DETAILS))
+			      {
+				fprintf (dump_file, "simplifying ");
+				print_pre_expr (dump_file, expr);
+				fprintf (dump_file, " translated %d -> %d to ",
+					 phiblock->index, pred->index);
+				PRE_EXPR_NARY (expr) = newnary;
+				print_pre_expr (dump_file, expr);
+				PRE_EXPR_NARY (expr) = nary;
+				fprintf (dump_file, " to ");
+				print_pre_expr (dump_file, constant);
+				fprintf (dump_file, "\n");
+			      }
+			    return constant;
+			  }
 		      }
 		  }
 		else
@@ -1426,7 +1441,7 @@ phi_translate_1 (bitmap_set_t dest,
 	    expr = pre_expr_pool.allocate ();
 	    expr->kind = NARY;
 	    expr->id = 0;
-	    if (nary)
+	    if (nary && !nary->predicated_values)
 	      {
 		PRE_EXPR_NARY (expr) = nary;
 		new_val_id = nary->value_id;
@@ -1664,7 +1679,10 @@ phi_translate (bitmap_set_t dest, pre_expr expr,
     }
 
   /* Translate.  */
+  basic_block saved_valueize_bb = vn_context_bb;
+  vn_context_bb = e->src;
   phitrans = phi_translate_1 (dest, expr, set1, set2, e);
+  vn_context_bb = saved_valueize_bb;
 
   if (slot)
     {
@@ -2923,7 +2941,7 @@ create_expression_by_pieces (basic_block block, pre_expr expr,
 
 	  if (forcedname != folded)
 	    {
-	      VN_INFO_GET (forcedname)->valnum = forcedname;
+	      VN_INFO (forcedname)->valnum = forcedname;
 	      VN_INFO (forcedname)->value_id = get_next_value_id ();
 	      nameexpr = get_or_alloc_expr_for_name (forcedname);
 	      add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
@@ -2949,8 +2967,8 @@ create_expression_by_pieces (basic_block block, pre_expr expr,
      the expression may have been represented.  There is no harm in replacing
      here.  */
   value_id = get_expr_value_id (expr);
-  VN_INFO_GET (name)->value_id = value_id;
-  VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id);
+  VN_INFO (name)->value_id = value_id;
+  VN_INFO (name)->valnum = vn_valnum_from_value_id (value_id);
   if (VN_INFO (name)->valnum == NULL_TREE)
     VN_INFO (name)->valnum = name;
   gcc_assert (VN_INFO (name)->valnum != NULL_TREE);
@@ -3055,8 +3073,8 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
   temp = make_temp_ssa_name (type, NULL, "prephitmp");
   phi = create_phi_node (temp, block);
 
-  VN_INFO_GET (temp)->value_id = val;
-  VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val);
+  VN_INFO (temp)->value_id = val;
+  VN_INFO (temp)->valnum = vn_valnum_from_value_id (val);
   if (VN_INFO (temp)->valnum == NULL_TREE)
     VN_INFO (temp)->valnum = temp;
   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
@@ -3300,8 +3318,8 @@ do_pre_regular_insertion (basic_block block, basic_block dom)
 	      gimple_stmt_iterator gsi = gsi_after_labels (block);
 	      gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
 
-	      VN_INFO_GET (temp)->value_id = val;
-	      VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val);
+	      VN_INFO (temp)->value_id = val;
+	      VN_INFO (temp)->valnum = vn_valnum_from_value_id (val);
 	      if (VN_INFO (temp)->valnum == NULL_TREE)
 		VN_INFO (temp)->valnum = temp;
 	      bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
@@ -3742,6 +3760,7 @@ compute_avail (void)
 
       /* Pick a block from the worklist.  */
       block = worklist[--sp];
+      vn_context_bb = block;
 
       /* Initially, the set of available values in BLOCK is that of
 	 its immediate dominator.  */
@@ -4043,6 +4062,7 @@ compute_avail (void)
 	   son = next_dom_son (CDI_DOMINATORS, son))
 	worklist[sp++] = son;
     }
+  vn_context_bb = NULL;
 
   free (worklist);
 }
@@ -4133,6 +4153,34 @@ public:
 
 }; // class pass_pre
 
+/* Valueization hook for RPO VN when we are calling back to it
+   at ANTIC compute time.  */
+
+static tree
+pre_valueize (tree name)
+{
+  if (TREE_CODE (name) == SSA_NAME)
+    {
+      tree tem = VN_INFO (name)->valnum;
+      if (tem != VN_TOP && tem != name)
+	{
+	  if (TREE_CODE (tem) != SSA_NAME
+	      || SSA_NAME_IS_DEFAULT_DEF (tem))
+	    return tem;
+	  /* We create temporary SSA names for representatives that
+	     do not have a definition (yet) but are not default defs either
+	     assume they are fine to use.  */
+	  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem));
+	  if (! def_bb
+	      || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
+	    return tem;
+	  /* ??? Now we could look for a leader.  Ideally we'd somehow
+	     expose RPO VN leaders and get rid of AVAIL_OUT as well...  */
+	}
+    }
+  return name;
+}
+
 unsigned int
 pass_pre::execute (function *fun)
 {
@@ -4141,16 +4189,18 @@ pass_pre::execute (function *fun)
   do_partial_partial =
     flag_tree_partial_pre && optimize_function_for_speed_p (fun);
 
-  /* This has to happen before SCCVN runs because
+  /* This has to happen before VN runs because
      loop_optimizer_init may create new phis, etc.  */
   loop_optimizer_init (LOOPS_NORMAL);
   split_critical_edges ();
   scev_initialize ();
 
-  run_scc_vn (VN_WALK);
+  run_rpo_vn (VN_WALK);
 
   init_pre ();
 
+  vn_valueize = pre_valueize;
+
   /* Insert can get quite slow on an incredibly large number of basic
      blocks due to some quadratic behavior.  Until this behavior is
      fixed, don't run it when he have an incredibly large number of
@@ -4179,8 +4229,9 @@ pass_pre::execute (function *fun)
   statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
   statistics_counter_event (fun, "New PHIs", pre_stats.phis);
 
-  /* Remove all the redundant expressions.  */
-  todo |= vn_eliminate (inserted_exprs);
+  todo |= eliminate_with_rpo_vn (inserted_exprs);
+
+  vn_valueize = NULL;
 
   /* Because we don't follow exactly the standard PRE algorithm, and decide not
      to insert PHI nodes sometimes, and because value numbering of casts isn't
@@ -4193,9 +4244,6 @@ pass_pre::execute (function *fun)
   scev_finalize ();
   loop_optimizer_finalize ();
 
-  /* Restore SSA info before tail-merging as that resets it as well.  */
-  scc_vn_restore_ssa_info ();
-
   /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
      case we can merge the block with the remaining predecessor of the block.
      It should either:
@@ -4205,7 +4253,7 @@ pass_pre::execute (function *fun)
      - share the cfg cleanup with fini_pre.  */
   todo |= tail_merge_optimize (todo);
 
-  free_scc_vn ();
+  free_rpo_vn ();
 
   /* Tail merging invalidates the virtual SSA web, together with
      cfg-cleanup opportunities exposed by PRE this will wreck the