[patch, RFC] Fix PR23821: DOM and VRP creating harder to optimize code

["Sebastian Pop" <sebpop at gmail dot com>]

Hi,

Symbolic propagation is causing problems downstream in the loop
optimizers.  In PR23821, this is because both VRP and DOM would
produce a code that is hard to analyze.  This patch analyzes the code
before and after a symbolic propagation, and discards those
substitutions that degrade the accuracy of the analysis.

I will wait for comments on the approach before sending this patch
to regstrap.

-- 
Sebastian
AMD - GNU Tools

	* tree-scalar-evolution.c (analyze_scalar_evolution): Fix comment.
	(scev_initialized, scev_initialized_p): New.
	(scev_initialize, scev_finalize): Set scev_initialized.
	* tree-scalar-evolution.h (scev_initialized_p): Declare.
	* tree-ssa-dom.c: Include tree-scalar-evolution.h.
	(tree_ssa_dominator_optimize): Call scev_initialize and scev_finalize.
	* tree-ssa-copy.c: Include cfgloop.h, tree-chrec.h, tree-scalar-evolution.h.
	(scrambled_scev_p): New.
	(propagate_value): Revert symbolic substitutions that degrade the
	information extracted by analyze_scalar_evolution.
	(scev_init_p): New.
	(init_copy_prop): Call scev_initialize.
	(fini_copy_prop): Call scev_finalize.
	* Makefile.in (tree-ssa-copy.o): Depend on CFGLOOP_H, SCEV_H.
	(tree-ssa-dom.o): Depend on SCEV_H.

Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c	(revision 131471)
+++ tree-scalar-evolution.c	(working copy)
@@ -1801,10 +1801,9 @@ analyze_scalar_evolution_1 (struct loop 
    determine the evolution function of the variable, use the following
    calls:
    
-   unsigned loop_nb = loop_containing_stmt (stmt)->num;
-   tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
-   tree chrec_instantiated = instantiate_parameters 
-   (loop_nb, chrec_with_symbols);
+   struct loop *loop = loop_containing_stmt (stmt);
+   tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
+   tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
 */
 
 tree 
@@ -2584,6 +2583,16 @@ initialize_scalar_evolutions_analyzer (v
     }
 }
 
+static bool scev_initialized = false;
+
+/* Return true if scev's data structures are initialized.  */
+
+bool
+scev_initialized_p (void)
+{
+  return scev_initialized;
+}
+
 /* Initialize the analysis of scalar evolutions for LOOPS.  */
 
 void
@@ -2606,6 +2615,8 @@ scev_initialize (void)
     {
       loop->nb_iterations = NULL_TREE;
     }
+
+  scev_initialized = true;
 }
 
 /* Clean the scalar evolution analysis cache, but preserve the cached
@@ -2725,6 +2736,7 @@ scev_finalize (void)
   htab_delete (scalar_evolution_info);
   BITMAP_FREE (already_instantiated);
   scalar_evolution_info = NULL;
+  scev_initialized = false;
 }
 
 /* Replace ssa names for that scev can prove they are constant by the
@@ -2869,6 +2881,7 @@ scev_const_prop (void)
 	  update_stmt (ass);
 	}
     }
+
   return 0;
 }
 
Index: tree-scalar-evolution.h
===================================================================
--- tree-scalar-evolution.h	(revision 131471)
+++ tree-scalar-evolution.h	(working copy)
@@ -25,6 +25,7 @@ extern tree number_of_latch_executions (
 extern tree number_of_exit_cond_executions (struct loop *);
 extern tree get_loop_exit_condition (const struct loop *);
 
+extern bool scev_initialized_p (void);
 extern void scev_initialize (void);
 extern void scev_reset (void);
 extern void scev_reset_except_niters (void);
Index: tree-ssa-dom.c
===================================================================
--- tree-ssa-dom.c	(revision 131471)
+++ tree-ssa-dom.c	(working copy)
@@ -37,6 +37,7 @@ along with GCC; see the file COPYING3.  
 #include "timevar.h"
 #include "tree-dump.h"
 #include "tree-flow.h"
+#include "tree-scalar-evolution.h"
 #include "domwalk.h"
 #include "real.h"
 #include "tree-pass.h"
@@ -288,7 +289,14 @@ tree_ssa_dominator_optimize (void)
   mark_dfs_back_edges ();
       
   /* Recursively walk the dominator tree optimizing statements.  */
-  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+  if (!scev_initialized_p ())
+    {
+      scev_initialize ();
+      walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+      scev_finalize ();
+    }
+  else
+    walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 
   {
     block_stmt_iterator bsi;
Index: tree-ssa-copy.c
===================================================================
--- tree-ssa-copy.c	(revision 131471)
+++ tree-ssa-copy.c	(working copy)
@@ -34,6 +34,9 @@ along with GCC; see the file COPYING3.  
 #include "timevar.h"
 #include "tree-dump.h"
 #include "tree-flow.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
 #include "tree-pass.h"
 #include "tree-ssa-propagate.h"
 #include "langhooks.h"
@@ -319,6 +322,20 @@ replace_exp_1 (use_operand_p op_p, tree 
     SET_USE (op_p, unsave_expr_now (val));
 }
 
+/* Return true when SCEV1 is different than SCEV0.  */
+
+static bool
+scrambled_scev_p (tree scev0, tree scev1)
+{
+  if (scev0 == scev1)
+    return false;
+
+  if (scev1 == chrec_dont_know
+      && scev0 != chrec_dont_know)
+    return true;
+
+  return false;
+}
 
 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
    into the operand pointed to by OP_P.
@@ -329,7 +346,29 @@ replace_exp_1 (use_operand_p op_p, tree 
 void
 propagate_value (use_operand_p op_p, tree val)
 {
-  replace_exp_1 (op_p, val, true);
+  tree stmt = USE_STMT (op_p);
+
+  if (current_loops
+      && TREE_CODE (val) == SSA_NAME
+      && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+    {
+      tree op = USE_FROM_PTR (op_p);
+      tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+      struct loop *loop = loop_containing_stmt (stmt);
+      tree scev0 = resolve_mixers (loop, analyze_scalar_evolution (loop, rhs));
+      tree scev1;
+
+      replace_exp_1 (op_p, val, true);
+
+      /* Ensure that the induction variables are not scrambled by this
+	 propagation: see PR23821.  If they are scrambled, revert the
+	 transform by propagating the initial value.  */
+      scev1 = resolve_mixers (loop, analyze_scalar_evolution (loop, rhs));
+      if (scrambled_scev_p (scev0, scev1))
+	replace_exp_1 (op_p, op, true);
+    }
+  else
+    replace_exp_1 (op_p, val, true);
 }
 
 
@@ -839,6 +878,7 @@ copy_prop_visit_phi_node (tree phi)
   return retval;
 }
 
+static bool scev_init_p = false;
 
 /* Initialize structures used for copy propagation.   PHIS_ONLY is true
    if we should only consider PHI nodes as generating copy propagation
@@ -849,6 +889,10 @@ init_copy_prop (void)
 {
   basic_block bb;
 
+  scev_init_p = scev_initialized_p ();
+  if (!scev_init_p)
+    scev_initialize ();
+
   copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
 
   cached_last_copy_of = XCNEWVEC (tree, num_ssa_names);
@@ -929,6 +973,9 @@ fini_copy_prop (void)
 
   substitute_and_fold (tmp, false);
 
+  if (!scev_init_p)
+    scev_finalize ();
+
   free (cached_last_copy_of);
   free (copy_of);
   free (tmp);
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 131471)
+++ Makefile.in	(working copy)
@@ -2027,7 +2027,8 @@ tree-nrv.o : tree-nrv.c $(CONFIG_H) $(SY
 tree-ssa-copy.o : tree-ssa-copy.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h $(DIAGNOSTIC_H) \
    $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
-   $(BASIC_BLOCK_H) tree-pass.h langhooks.h tree-ssa-propagate.h $(FLAGS_H)
+   $(BASIC_BLOCK_H) tree-pass.h langhooks.h tree-ssa-propagate.h $(FLAGS_H) \
+   $(CFGLOOP_H) $(SCEV_H)
 tree-ssa-propagate.o : tree-ssa-propagate.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h \
    $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \
@@ -2037,7 +2038,7 @@ tree-ssa-dom.o : tree-ssa-dom.c $(TREE_F
    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h $(DIAGNOSTIC_H) \
    $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
    $(BASIC_BLOCK_H) domwalk.h tree-pass.h $(FLAGS_H) langhooks.h \
-   tree-ssa-propagate.h $(CFGLOOP_H) $(PARAMS_H) $(REAL_H)
+   tree-ssa-propagate.h $(CFGLOOP_H) $(PARAMS_H) $(REAL_H) $(SCEV_H)
 tree-ssa-uncprop.o : tree-ssa-uncprop.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h \
    $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \