Changes in Traverse and execute CRC function v2: - Added support of traversing all paths of the function. - Added functions to check statement type and execute some expressions.

Changes in CRC detection v2:
  - Added and changed comments to clarify the behavior of crc detection pass.
  - Ended all sentences with '.'.
  - Added static member cond_true_is_checked_for_bit_one.
  - Changed get_return_value_size function name to set_return_value_size.
  - Don't print return value size in set_return_value_size function.
  - Call execute_function after detecting CRC-like function

4 files changed, 304 insertions, 66 deletions

diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc
index faed3efb1e1..33404f0f7ea 100644
--- a/gcc/gimple-crc-optimization.cc
+++ b/gcc/gimple-crc-optimization.cc
@@ -34,7 +34,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-range.h"
 #include "tree-scalar-evolution.h"
 #include "hwint.h"
-#include "gimple-pretty-print.h
+#include "symb-execute-all-paths.h"
 
 class crc_optimization {
  private:
@@ -156,7 +156,7 @@ class crc_optimization {
 
   /* Get the return value size of the function
      and assign to return_size member.  */
-  void get_return_value_size (function *fun);
+  void set_return_value_size (function *fun);
 
   /* This function checks whether calculated crc value
      (maybe modified) is returned.
@@ -203,13 +203,13 @@ crc_optimization::print_crc_information ()
   if (dump_file)
     {
       fprintf (dump_file,
-	       "Loop iteration number is %ld."
-	       "\nReturn size is %ld\n.",
+	       "Loop iteration number is %ld.\n"
+	       "Return size is %ld.\n",
 	       loop_iteration_number, return_size);
       if (is_left_shift)
-	fprintf (dump_file, "Bit forward\n");
+	fprintf (dump_file, "Bit forward.\n");
       else
-	fprintf (dump_file, "Bit reversed\n");
+	fprintf (dump_file, "Bit reversed.\n");
     }
 }
 
@@ -233,8 +233,6 @@ crc_optimization::returned_value_depends_on_crc (tree lhs)
   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
     {
       gimple *stmt = USE_STMT (use_p);
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	print_gimple_stmt (dump_file, stmt, 0);
       if (gimple_visited_p (stmt))
 	return false;
 
@@ -258,15 +256,13 @@ crc_optimization::returned_value_depends_on_crc (tree lhs)
    and assign to return_size member.  */
 
 void
-crc_optimization::get_return_value_size (function *fun)
+crc_optimization::set_return_value_size (function *fun)
 {
   return_size = 0;
   tree tree_return_value_size = DECL_SIZE (DECL_RESULT (fun->decl));
   if (tree_fits_uhwi_p (tree_return_value_size))
     {
       return_size = tree_to_uhwi (tree_return_value_size);
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "Return size is %ld\n", return_size);
     }
 }
 
@@ -416,7 +412,7 @@ crc_optimization::crc_cond_and_shift (const basic_block &pred_bb,
   if ((cond_true_is_checked_for_bit_one (cond) && true_edge->dest == xor_bb))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "Xor is done on true branch\n");
+	fprintf (dump_file, "Xor is done on true branch.\n");
 
       xor_opposite_block = false_edge->dest;
     }
@@ -424,7 +420,7 @@ crc_optimization::crc_cond_and_shift (const basic_block &pred_bb,
 	   && false_edge->dest == xor_bb)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "Xor is done on false branch\n");
+	fprintf (dump_file, "Xor is done on false branch.\n");
 
       xor_opposite_block = true_edge->dest;
     }
@@ -432,7 +428,7 @@ crc_optimization::crc_cond_and_shift (const basic_block &pred_bb,
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
-		 "Xor is done if MSB/LSB is not one, not crc\n");
+		 "Xor is done if MSB/LSB is not one, not crc.\n");
 
       return false;
     }
@@ -500,7 +496,7 @@ crc_optimization::can_not_be_shift_of_crc (gimple *assign_stmt,
 		  if (dump_file && (dump_flags & TDF_DETAILS))
 		    fprintf (dump_file,
 			     "Already there is one shift "
-			     "on the path to xor. not crc\n");
+			     "on the path to xor, not crc.\n");
 
 		  clean_xor_maybe_crc = false;
 		  return true;
@@ -512,7 +508,7 @@ crc_optimization::can_not_be_shift_of_crc (gimple *assign_stmt,
 	      shift_after_xor = assign_stmt;
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file,
-			 "Found shift1 after xor\n");
+			 "Found shift1 after xor.\n");
 	    }
 	  return false;
 	}
@@ -520,7 +516,7 @@ crc_optimization::can_not_be_shift_of_crc (gimple *assign_stmt,
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    fprintf (dump_file,
-		     "Found shift, but not with 1, not crc\n");
+		     "Found shift, but not with 1, not crc.\n");
 	  clean_xor_maybe_crc = false;
 	  return true;
 	}
@@ -534,7 +530,7 @@ crc_optimization::can_not_be_shift_of_crc (gimple *assign_stmt,
 	fprintf (dump_file,
 		 "\nStmt with following operation "
 		 "code %s between xor and shift, "
-		 "may not be crc \n", get_tree_code_name (stmt_code));
+		 "may not be crc.\n", get_tree_code_name (stmt_code));
 
       return true;
     }
@@ -577,7 +573,7 @@ crc_optimization::get_dep (tree name,
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
-		 "Phi's definition IS NOT in loop header\n");
+		 "Phi's definition IS NOT in loop header.\n");
 
       if (check_dependency == &crc_optimization::check_def_stmt_for_xor)
 	clean_xor_maybe_crc = false;
@@ -619,14 +615,14 @@ crc_optimization::check_def_stmt_for_xor (tree dep)
       if (first_phi_for_crc)
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    fprintf (dump_file, "Set second phi\n");
+	    fprintf (dump_file, "Set second phi.\n");
 
 	  second_phi_for_crc = def_stmt;
 	}
       else
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    fprintf (dump_file, "Set first phi\n");
+	    fprintf (dump_file, "Set first phi.\n");
 
 	  first_phi_for_crc = def_stmt;
 	}
@@ -693,7 +689,7 @@ crc_optimization::xor_calculates_crc (function *fun, class loop *crc_loop,
   if (!shift_before_xor)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "No shift before xor\n");
+	fprintf (dump_file, "No shift before xor.\n");
 
       set_all_statements_not_visited (fun);
       find_shift_after_xor (crc_loop, crc_var);
@@ -746,14 +742,14 @@ crc_optimization::is_loop_of_crc_calculation (class loop *func_loop)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
-		 "Loop iteration number is chrec_dont_know\n");
+		 "Loop iteration number is chrec_dont_know.\n");
 
     }
   else if (tree_fits_uhwi_p (n_inters))
     {
       loop_iteration_number = tree_to_uhwi (n_inters);
       if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "Loop iteration number is %ld\n",
+	fprintf (dump_file, "Loop iteration number is %ld.\n",
 		 loop_iteration_number);
 
       if (!(loop_iteration_number == 7 || loop_iteration_number == 15
@@ -775,7 +771,7 @@ bool
 crc_optimization::function_may_calculate_crc (function *fun)
 {
   if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "\nExamining %s function\n",
+    fprintf (dump_file, "\nExamining %s function.\n",
 	     function_name (fun));
 
   if (number_of_loops (fun) <= 1)
@@ -810,11 +806,11 @@ crc_optimization::function_may_calculate_crc (function *fun)
 		  if (dump_file && (dump_flags & TDF_DETAILS))
 		    fprintf (dump_file,
 			     "Found xor, "
-			     "checking whether it is for crc calculation\n");
+			     "checking whether it is for crc calculation.\n");
 
 		  if (xor_calculates_crc (fun, loop, stmt))
 		    {
-		      get_return_value_size (fun);
+		      set_return_value_size (fun);
 		      print_crc_information ();
 		      return true;
 		    }
@@ -828,7 +824,11 @@ crc_optimization::function_may_calculate_crc (function *fun)
 unsigned int
 crc_optimization::execute (function *fun)
 {
-  function_may_calculate_crc (fun);
+  if (function_may_calculate_crc (fun))
+  {
+    crc_symb_execution symb_exec;
+    symb_exec.execute_function (fun);
+  }
   return 0;
 }
 
diff --git a/gcc/sym-exec/state.h b/gcc/sym-exec/state.h
index 7959123e72b..c9a0e5fd8e0 100644
--- a/gcc/sym-exec/state.h
+++ b/gcc/sym-exec/state.h
@@ -27,6 +27,7 @@
 #include "hash-map.h"
 #include "hash-set.h"
 #include "expression.h"
+#include "expression-is-a-helper.h"
 
 /* Stores states of variables' values on bit-level.  */
 
diff --git a/gcc/symb-execute-all-paths.cc b/gcc/symb-execute-all-paths.cc
index 117d27367c5..35564670067 100644
--- a/gcc/symb-execute-all-paths.cc
+++ b/gcc/symb-execute-all-paths.cc
@@ -36,54 +36,250 @@ along with GCC; see the file COPYING3.  If not see
 #include "hwint.h"
 #include "gimple-pretty-print.h"
 #include "function.h"
+#include "cfganal.h"
 
-void get_function_local_ssa_vars (function *fun)
+/* This function assigns symbolic values to the arguments of the fun.
+   (Not complete).  */
+void
+crc_symb_execution::make_symbolic_func_args_and_sizes (function *fun,
+						       State *initial_state)
 {
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Making symbolic function's following arguments:\n");
+  /* Get size and name of function's arguments.  */
+  for (tree arg = DECL_ARGUMENTS (fun->decl); arg; arg = DECL_CHAIN (arg))
+    {
+      /* If the argument has a name and the size is integer
+	 print that information.  */
+      if (TREE_CODE (DECL_SIZE (arg)) == INTEGER_CST && DECL_NAME (arg))
+	{
+	  unsigned HOST_WIDE_INT
+	  size = tree_to_uhwi (DECL_SIZE (arg));
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "%s : %lu; ",
+		     IDENTIFIER_POINTER (DECL_NAME (arg)), size);
+	  /* Add argument with its size to the state
+	     and assign symbolic value.  */
+	  initial_state->make_symbolic (arg, size);
+	}
+      else if (dump_file)
+	fprintf (dump_file, "Argument not const or no name.\n");
+    }
+}
+
+/* Add declared ssa variables to the state.  */
+void
+crc_symb_execution::add_function_local_ssa_vars (function *fun,
+						 State *initial_state)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\nAdding following ssa name declarations: \n");
   unsigned ix;
   tree name;
-  // get ssa names of the function, yet print sizes and names
+  /* Get ssa names of the function, yet print sizes and names.  */
   FOR_EACH_SSA_NAME (ix, name, fun)
-    {
-      if (TREE_CODE (TREE_TYPE (name)) == INTEGER_TYPE)
       {
-	if (TYPE_UNSIGNED (TREE_TYPE (name)))
+	if (dump_file && (dump_flags & TDF_DETAILS))
+	  {
+	    print_generic_expr (dump_file, name, dump_flags);
+	  }
+	unsigned HOST_WIDE_INT
+	size;
+	if (TREE_CODE (TREE_TYPE (name)) == INTEGER_TYPE)
+	  {
+	    if (TYPE_UNSIGNED (TREE_TYPE (name)))
+	      {
+		// We need this info for symb execution.
+		if (dump_file && (dump_flags & TDF_DETAILS))
+		  fprintf (dump_file,
+			   " unsigned,");
+	      }
+	    size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (name)));
+	    if (dump_file && (dump_flags & TDF_DETAILS))
+	      fprintf (dump_file, " size is %lu.\n", size);
+	  }
+	else if (TREE_CODE (TREE_TYPE (name)) == POINTER_TYPE)
+	  {
+	    size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (name)));
+
+	    if (dump_file && (dump_flags & TDF_DETAILS))
+	      fprintf (dump_file, " pointer type, size is %lu.\n", size);
+	  }
+	else
+	  continue;
+
+	/* Add ssa variable with its size to the state.  */
+	initial_state->decl_var (name, size);
+      }
+}
+
+/* Calculate value of the rhs operation and assign to lhs variable.  */
+void
+crc_symb_execution::execute_assign_statement (const gassign *gs)
+{
+  enum tree_code rhs_code = gimple_assign_rhs_code (gs);
+  tree lhs = gimple_assign_lhs (gs);
+  State *current_state = states.last ();
+  if (gimple_num_ops (gs) == 2 && rhs_code == BIT_NOT_EXPR)
+    {
+      tree op1 = gimple_assign_rhs1 (gs);
+      // current_state->do_complement (op1, lhs);
+    }
+  else if (gimple_num_ops (gs) == 3)
+    {
+      tree op1 = gimple_assign_rhs1 (gs);
+      tree op2 = gimple_assign_rhs2 (gs);
+      switch (rhs_code)
 	{
-	  if (dump_file)
-	    fprintf (dump_file,
-		   "unsigned "); //we need this info in symb execution
+	  case LSHIFT_EXPR:
+	    // current_state->do_shift_left (op1, op2, lhs);
+	    break;
+	  case RSHIFT_EXPR:
+	    // current_state->do_shift_right (op1, op2, lhs);
+	    break;
+	  case BIT_AND_EXPR:
+	    // current_state->do_and (op1, op2, lhs);
+	    break;
+	  case BIT_IOR_EXPR:
+	   // current_state->do_or (op1, op2, lhs);
+	    break;
+	  case BIT_XOR_EXPR:
+	   // current_state->do_xor (op1, op2, lhs);
+	    break;
+	  case PLUS_EXPR:
+	   // current_state->do_add (op1, op2, lhs);
+	    break;
+	  case MINUS_EXPR:
+	   // current_state->do_sub (op1, op2, lhs);
+	    break;
+	  case MULT_EXPR:
+	    // current_state->do_mul (op1, op2, lhs);
+	    break;
+	  default:
+	    if (dump_file)
+	      fprintf (dump_file,
+		       "Warning, encountered unsupported binary operation, "
+		       "while executing assign statement!\n");
+	  break;
 	}
-	if (dump_file)
-	  fprintf (dump_file, " size is %ld ",
-		 tree_to_shwi (TYPE_SIZE (TREE_TYPE (name))));
-      } else if (TREE_CODE (TREE_TYPE (name)) == POINTER_TYPE)
-      {
-	if (dump_file)
-	  fprintf (stderr, "pointer type size is %ld ",
-		 tree_to_shwi (TYPE_SIZE (TREE_TYPE (name))));
-      } else
-	continue;
-     if (dump_file)
-     {
-       print_generic_expr (dump_file, name, dump_flags);
-       fprintf (dump_file, "\n");
-     }
+    }
+  else
+    {
+      if (dump_file)
+	fprintf (dump_file,
+		 "Warning, encountered unsupported ternary operation, "
+		 "while executing assign statement!\n");
     }
 }
 
-void make_symbolic_function_arguments_and_sizes (function *fun)
+/* Execute gimple statements of BB.
+   Keeping values of variables in the state.  */
+void
+crc_symb_execution::execute_bb_gimple_statements (basic_block bb)
 {
-  // Get size and name of function's arguments
-  for (tree arg = DECL_ARGUMENTS (fun->decl); arg; arg = DECL_CHAIN (arg))
-  {
-    if (TREE_CODE (DECL_SIZE (arg)) == INTEGER_CST && DECL_NAME (arg))
+  for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
+       !gsi_end_p (bsi); gsi_next (&bsi))
     {
-      if (dump_file)
-	fprintf (dump_file, "%s : %ld ",
-		 IDENTIFIER_POINTER (DECL_NAME (arg)),
-		 tree_to_shwi (DECL_SIZE (arg)));
-    } else
-      if (dump_file)
-	fprintf (dump_file, "Argument not const or no name");
-  }
+      gimple *gs = gsi_stmt (bsi);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Executing following statement:\n");
+	  print_gimple_stmt (dump_file, gs, dump_flags);
+	}
+      switch (gimple_code (gs))
+	{
+	  case GIMPLE_ASSIGN:
+	    execute_assign_statement (as_a<const gassign *> (gs));
+	  break;
+	  case GIMPLE_COND:
+	    //TODO: Examine condition.  Fork state if needed and keep condition.
+	    break;
+	  case GIMPLE_RETURN:
+	    break;
+	  default:
+	    if (dump_file)
+	      fprintf (dump_file,
+		       "Warning, encountered unsupported statement, "
+		       "while executing gimple statements!\n");
+	  break;
+	}
+    }
+}
+
+/* Assign values of phi instruction to its result.
+   Keep updated values in the state.  */
+void
+crc_symb_execution::execute_bb_phi_statements (basic_block bb)
+{
+  for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+       gsi_next (&gsi))
+    {
+      gphi *phi_stmt = gsi.phi ();
+      //TODO: assign value to the result of phi.
+    }
 }
 
+/* Execute all statements of BB.
+   Keeping values of variables in the state.  */
+void
+crc_symb_execution::execute_bb_statements (basic_block bb)
+{
+  execute_bb_phi_statements (bb);
+  execute_bb_gimple_statements (bb);
+}
+
+/* Traverse function fun's all paths from the first basic block to the last.
+   Each time iterate loops only once.
+   Symbolically execute statements of each path.  */
+void
+crc_symb_execution::traverse_function (function *fun)
+{
+  /* TODO: Check whether back_edges can be determined by BB index,
+     if so, no need of EDGE_DFS_BACK flag.  */
+  mark_dfs_back_edges (fun);
+
+  /* Allocate stack for back-tracking up CFG.  */
+  auto_vec<basic_block, 20> stack (n_basic_blocks_for_fn (fun) + 1);
+
+  /* Push the first block into the stack.  */
+  stack.quick_push (ENTRY_BLOCK_PTR_FOR_FN (fun));
+
+  while (!stack.is_empty ())
+    {
+      /* Look at the block on the top of the stack.  */
+      basic_block bb = stack.last ();
+      stack.pop ();
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "\nExecuting BB <%d>\n", bb->index);
+
+      /* Symbolically execute statements.  */
+      execute_bb_statements (bb);
+
+      /* Add each successor block of the current block to the stack,
+       * despite the one connected with back edge.  */
+      edge e;
+      edge_iterator ei;
+      FOR_EACH_EDGE (e, ei, bb->succs) if (!(e->flags & EDGE_DFS_BACK))
+	  stack.quick_push (e->dest);
+    }
+}
+
+void
+crc_symb_execution::execute_function (function *fun)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\nExecuting CRC-like function.\n");
+
+  /* Create initial state and push into the vector of states.  */
+  states.quick_push (new State);
+  State *initial_state = states.last ();
+
+  make_symbolic_func_args_and_sizes (fun, initial_state);
+
+  /* Add declared variables to the state.  */
+  add_function_local_ssa_vars (fun, initial_state);
+
+  /* Execute function's statements, keeping a state for each path.  */
+  traverse_function (fun);
+}
diff --git a/gcc/symb-execute-all-paths.h b/gcc/symb-execute-all-paths.h
index 88e72d52cdf..0fe42894eba 100644
--- a/gcc/symb-execute-all-paths.h
+++ b/gcc/symb-execute-all-paths.h
@@ -37,9 +37,50 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "hwint.h"
 #include "function.h"
+#include "sym-exec/state.h"
 
-void get_function_local_ssa_vars (function *);
+class crc_symb_execution {
 
-void make_symbolic_function_arguments_and_sizes (function *);
+ private:
+  /* A vector of states to keep the state of each executed path.  */
+  vec<State*> states;
+
+/* Assign symbolic values to the arguments of the function
+   and keep in the state.  */
+  static void make_symbolic_func_args_and_sizes (function *, State *);
+
+  /* Add declared ssa variables to the state.  */
+  static void add_function_local_ssa_vars (function *fun, State *initial_state);
+
+  void execute_assign_statement (const gassign *);
+
+  /* Execute gimple statements of the basic block.
+   Keeping values of variables in the state.  */
+  void execute_bb_gimple_statements (basic_block);
+
+  /* Assign values of phi instruction to its result.
+   Keep updated values in the state.  */
+  void execute_bb_phi_statements (basic_block);
+
+  /* Execute all statements of the basic block.
+    Keeping values of variables in the state.  */
+  void execute_bb_statements (basic_block);
+
+/* Traverse function fun's all paths from the first basic block to the last.
+   Each time iterate loops only once.
+   Symbolically execute statements of each path.  */
+  void traverse_function (function *);
+
+ public:
+  void execute_function (function *);
+
+  crc_symb_execution ()
+  {
+    /* Reserve memory for the vector.
+       Actually, if the function is calculating one CRC, there may be 2 states.
+       Just in case allocate more memory.  */
+    states.create (4);
+  }
+};
 
 #endif //GCC_EXECUTE_ALL_PATHS_H