diff --git a/gcc/testsuite/gcc.dg/torture/pr107176.c b/gcc/testsuite/gcc.dg/torture/pr107176.c
new file mode 100644
index 00000000000..c4f7b6d7336
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr107176.c
@@ -0,0 +1,22 @@
+/* { dg-do run } */
+
+__INT32_TYPE__ a;
+__INT64_TYPE__ b;
+static inline __INT64_TYPE__ c(__UINT32_TYPE__ d)
+{
+  return d;
+}
+static inline void e(__INT32_TYPE__ d)
+{
+  a = d;
+}
+int main()
+{
+  b = 0;
+  for (; b < 1; b = c(b - 90) + 90 + 1)
+    ;
+  e(b >> 2);
+  if (a != 1073741824)
+    __builtin_abort();
+  return 0;
+}
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index 8b927094324..7e2a3e98661 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -577,6 +577,51 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar)
   return res;
 }
 
+
+/* Depth first search algorithm.  */
+
+enum t_bool {
+  t_false,
+  t_true,
+  t_dont_know
+};
+
+class scev_dfs
+{
+public:
+  scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_)
+      : loop (loop_), loop_phi_node (phi_), init_cond (init_cond_) {}
+  t_bool get_ev (tree *, tree);
+
+private:
+  t_bool follow_ssa_edge_expr (gimple *, tree, tree *, int);
+  t_bool follow_ssa_edge_binary (gimple *at_stmt,
+				 tree type, tree rhs0, enum tree_code code,
+				 tree rhs1, tree *evolution_of_loop, int limit);
+  t_bool follow_ssa_edge_in_condition_phi_branch (int i,
+						  gphi *condition_phi,
+						  tree *evolution_of_branch,
+						  tree init_cond, int limit);
+  t_bool follow_ssa_edge_in_condition_phi (gphi *condition_phi,
+					   tree *evolution_of_loop, int limit);
+  t_bool follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
+					 tree *evolution_of_loop, int limit);
+  tree add_to_evolution (tree chrec_before, enum tree_code code,
+			 tree to_add, gimple *at_stmt);
+  tree add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt);
+
+  class loop *loop;
+  gphi *loop_phi_node;
+  tree init_cond;
+};
+
+t_bool
+scev_dfs::get_ev (tree *ev_fn, tree arg)
+{
+  *ev_fn = chrec_dont_know;
+  return follow_ssa_edge_expr (loop_phi_node, arg, ev_fn, 0);
+}
+
 /* Helper function for add_to_evolution.  Returns the evolution
    function for an assignment of the form "a = b + c", where "a" and
    "b" are on the strongly connected component.  CHREC_BEFORE is the
@@ -587,12 +632,12 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar)
    evolution the expression TO_ADD, otherwise construct an evolution
    part for this loop.  */
 
-static tree
-add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
-		    gimple *at_stmt)
+tree
+scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
 {
   tree type, left, right;
-  class loop *loop = get_loop (cfun, loop_nb), *chloop;
+  unsigned loop_nb = loop->num;
+  class loop *chloop;
 
   switch (TREE_CODE (chrec_before))
     {
@@ -631,7 +676,7 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
 	  gcc_assert (flow_loop_nested_p (loop, chloop));
 
 	  /* Search the evolution in LOOP_NB.  */
-	  left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
+	  left = add_to_evolution_1 (CHREC_LEFT (chrec_before),
 				     to_add, at_stmt);
 	  right = CHREC_RIGHT (chrec_before);
 	  right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
@@ -646,6 +691,17 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
 
       left = chrec_before;
       right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
+      /* When we add the first evolution we need to replace the symbolic
+	 evolution we've put in when the DFS reached the loop PHI node
+	 with the initial value.  There's only a limited cases of
+	 extra operations ontop of that symbol allowed, namely
+	 sign-conversions we can look through.  For other cases we leave
+	 the symbolic initial condition which causes build_polynomial_chrec
+	 to return chrec_dont_know.  See PR42512, PR66375 and PR107176 for
+	 cases we mishandled before.  */
+      STRIP_NOPS (chrec_before);
+      if (chrec_before == gimple_phi_result (loop_phi_node))
+	left = fold_convert (TREE_TYPE (left), init_cond);
       return build_polynomial_chrec (loop_nb, left, right);
     }
 }
@@ -784,9 +840,9 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
 
 */
 
-static tree
-add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
-		  tree to_add, gimple *at_stmt)
+tree
+scev_dfs::add_to_evolution (tree chrec_before, enum tree_code code,
+			    tree to_add, gimple *at_stmt)
 {
   tree type = chrec_type (to_add);
   tree res = NULL_TREE;
@@ -803,7 +859,7 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
   if (dump_file && (dump_flags & TDF_SCEV))
     {
       fprintf (dump_file, "(add_to_evolution \n");
-      fprintf (dump_file, "  (loop_nb = %d)\n", loop_nb);
+      fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
       fprintf (dump_file, "  (chrec_before = ");
       print_generic_expr (dump_file, chrec_before);
       fprintf (dump_file, ")\n  (to_add = ");
@@ -816,7 +872,7 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
 				  ? build_real (type, dconstm1)
 				  : build_int_cst_type (type, -1));
 
-  res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
+  res = add_to_evolution_1 (chrec_before, to_add, at_stmt);
 
   if (dump_file && (dump_flags & TDF_SCEV))
     {
@@ -828,64 +884,14 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
   return res;
 }
 
-
-
-/* This section selects the loops that will be good candidates for the
-   scalar evolution analysis.  For the moment, greedily select all the
-   loop nests we could analyze.  */
-
-/* For a loop with a single exit edge, return the COND_EXPR that
-   guards the exit edge.  If the expression is too difficult to
-   analyze, then give up.  */
-
-gcond *
-get_loop_exit_condition (const class loop *loop)
-{
-  gcond *res = NULL;
-  edge exit_edge = single_exit (loop);
-
-  if (dump_file && (dump_flags & TDF_SCEV))
-    fprintf (dump_file, "(get_loop_exit_condition \n  ");
-
-  if (exit_edge)
-    {
-      gimple *stmt;
-
-      stmt = last_stmt (exit_edge->src);
-      if (gcond *cond_stmt = safe_dyn_cast <gcond *> (stmt))
-	res = cond_stmt;
-    }
-
-  if (dump_file && (dump_flags & TDF_SCEV))
-    {
-      print_gimple_stmt (dump_file, res, 0);
-      fprintf (dump_file, ")\n");
-    }
-
-  return res;
-}
-
-
-/* Depth first search algorithm.  */
-
-enum t_bool {
-  t_false,
-  t_true,
-  t_dont_know
-};
-
-
-static t_bool follow_ssa_edge_expr (class loop *loop, gimple *, tree, gphi *,
-				    tree *, int);
 
 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
    Return true if the strongly connected component has been found.  */
 
-static t_bool
-follow_ssa_edge_binary (class loop *loop, gimple *at_stmt,
-			tree type, tree rhs0, enum tree_code code, tree rhs1,
-			gphi *halting_phi, tree *evolution_of_loop,
-			int limit)
+t_bool
+scev_dfs::follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0,
+				  enum tree_code code, tree rhs1,
+				  tree *evolution_of_loop, int limit)
 {
   t_bool res = t_false;
   tree evol;
@@ -907,23 +913,18 @@ follow_ssa_edge_binary (class loop *loop, gimple *at_stmt,
 	      limit++;
 
 	      evol = *evolution_of_loop;
-	      evol = add_to_evolution
-		  (loop->num,
-		   chrec_convert (type, evol, at_stmt),
-		   code, rhs1, at_stmt);
-	      res = follow_ssa_edge_expr
-		(loop, at_stmt, rhs0, halting_phi, &evol, limit);
+	      res = follow_ssa_edge_expr (at_stmt, rhs0, &evol, limit);
 	      if (res == t_true)
-		*evolution_of_loop = evol;
+		*evolution_of_loop = add_to_evolution
+		    (chrec_convert (type, evol, at_stmt), code, rhs1, at_stmt);
 	      else if (res == t_false)
 		{
-		  *evolution_of_loop = add_to_evolution
-		      (loop->num,
-		       chrec_convert (type, *evolution_of_loop, at_stmt),
-		       code, rhs0, at_stmt);
 		  res = follow_ssa_edge_expr
-		    (loop, at_stmt, rhs1, halting_phi,
-		     evolution_of_loop, limit);
+		    (at_stmt, rhs1, evolution_of_loop, limit);
+		  if (res == t_true)
+		    *evolution_of_loop = add_to_evolution
+			(chrec_convert (type, *evolution_of_loop, at_stmt),
+			 code, rhs0, at_stmt);
 		}
 	    }
 
@@ -935,13 +936,11 @@ follow_ssa_edge_binary (class loop *loop, gimple *at_stmt,
 	{
 	  /* Match an assignment under the form:
 	     "a = ... + c".  */
-	  *evolution_of_loop = add_to_evolution
-	      (loop->num, chrec_convert (type, *evolution_of_loop,
-					 at_stmt),
-	       code, rhs0, at_stmt);
-	  res = follow_ssa_edge_expr
-	    (loop, at_stmt, rhs1, halting_phi,
-	     evolution_of_loop, limit);
+	  res = follow_ssa_edge_expr (at_stmt, rhs1, evolution_of_loop, limit);
+	  if (res == t_true)
+	    *evolution_of_loop = add_to_evolution
+		(chrec_convert (type, *evolution_of_loop, at_stmt),
+		 code, rhs0, at_stmt);
 	}
 
       else
@@ -989,13 +988,11 @@ backedge_phi_arg_p (gphi *phi, int i)
    true if the strongly connected component has been found following
    this path.  */
 
-static inline t_bool
-follow_ssa_edge_in_condition_phi_branch (int i,
-					 class loop *loop,
-					 gphi *condition_phi,
-					 gphi *halting_phi,
-					 tree *evolution_of_branch,
-					 tree init_cond, int limit)
+t_bool
+scev_dfs::follow_ssa_edge_in_condition_phi_branch (int i,
+						   gphi *condition_phi,
+						   tree *evolution_of_branch,
+						   tree init_cond, int limit)
 {
   tree branch = PHI_ARG_DEF (condition_phi, i);
   *evolution_of_branch = chrec_dont_know;
@@ -1008,7 +1005,7 @@ follow_ssa_edge_in_condition_phi_branch (int i,
   if (TREE_CODE (branch) == SSA_NAME)
     {
       *evolution_of_branch = init_cond;
-      return follow_ssa_edge_expr (loop, condition_phi, branch, halting_phi,
+      return follow_ssa_edge_expr (condition_phi, branch,
 				   evolution_of_branch, limit);
     }
 
@@ -1025,17 +1022,14 @@ follow_ssa_edge_in_condition_phi_branch (int i,
 /* This function merges the branches of a condition-phi-node in a
    loop.  */
 
-static t_bool
-follow_ssa_edge_in_condition_phi (class loop *loop,
-				  gphi *condition_phi,
-				  gphi *halting_phi,
-				  tree *evolution_of_loop, int limit)
+t_bool
+scev_dfs::follow_ssa_edge_in_condition_phi (gphi *condition_phi,
+					    tree *evolution_of_loop, int limit)
 {
   int i, n;
   tree init = *evolution_of_loop;
   tree evolution_of_branch;
-  t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
-							halting_phi,
+  t_bool res = follow_ssa_edge_in_condition_phi_branch (0, condition_phi,
 							&evolution_of_branch,
 							init, limit);
   if (res == t_false || res == t_dont_know)
@@ -1053,8 +1047,7 @@ follow_ssa_edge_in_condition_phi (class loop *loop,
 
       /* Increase the limit by the PHI argument number to avoid exponential
 	 time and memory complexity.  */
-      res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
-						     halting_phi,
+      res = follow_ssa_edge_in_condition_phi_branch (i, condition_phi,
 						     &evolution_of_branch,
 						     init, limit + i);
       if (res == t_false || res == t_dont_know)
@@ -1072,11 +1065,9 @@ follow_ssa_edge_in_condition_phi (class loop *loop,
    it follows the edges in the parent loop.  The inner loop is
    considered as a single statement.  */
 
-static t_bool
-follow_ssa_edge_inner_loop_phi (class loop *outer_loop,
-				gphi *loop_phi_node,
-				gphi *halting_phi,
-				tree *evolution_of_loop, int limit)
+t_bool
+scev_dfs::follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
+					  tree *evolution_of_loop, int limit)
 {
   class loop *loop = loop_containing_stmt (loop_phi_node);
   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
@@ -1096,9 +1087,8 @@ follow_ssa_edge_inner_loop_phi (class loop *outer_loop,
 	  /* Follow the edges that exit the inner loop.  */
 	  bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
 	  if (!flow_bb_inside_loop_p (loop, bb))
-	    res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
-					arg, halting_phi,
-					evolution_of_loop, limit);
+	    res = follow_ssa_edge_expr (loop_phi_node,
+					arg, evolution_of_loop, limit);
 	  if (res == t_true)
 	    break;
 	}
@@ -1112,18 +1102,17 @@ follow_ssa_edge_inner_loop_phi (class loop *outer_loop,
 
   /* Otherwise, compute the overall effect of the inner loop.  */
   ev = compute_overall_effect_of_inner_loop (loop, ev);
-  return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
-			       evolution_of_loop, limit);
+  return follow_ssa_edge_expr (loop_phi_node, ev, evolution_of_loop, limit);
 }
 
 /* Follow the ssa edge into the expression EXPR.
    Return true if the strongly connected component has been found.  */
 
-static t_bool
-follow_ssa_edge_expr (class loop *loop, gimple *at_stmt, tree expr,
-		      gphi *halting_phi, tree *evolution_of_loop,
-		      int limit)
+t_bool
+scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
+				tree *evolution_of_loop, int limit)
 {
+  gphi *halting_phi = loop_phi_node;
   enum tree_code code;
   tree type, rhs0, rhs1 = NULL_TREE;
 
@@ -1161,14 +1150,17 @@ tail_recurse:
 	       record their evolutions.  Finally, merge the collected
 	       information and set the approximation to the main
 	       variable.  */
-	    return follow_ssa_edge_in_condition_phi
-		(loop, phi, halting_phi, evolution_of_loop, limit);
+	    return follow_ssa_edge_in_condition_phi (phi, evolution_of_loop,
+						     limit);
 
 	  /* When the analyzed phi is the halting_phi, the
 	     depth-first search is over: we have found a path from
 	     the halting_phi to itself in the loop.  */
 	  if (phi == halting_phi)
-	    return t_true;
+	    {
+	      *evolution_of_loop = expr;
+	      return t_true;
+	    }
 
 	  /* Otherwise, the evolution of the HALTING_PHI depends
 	     on the evolution of another loop-phi-node, i.e. the
@@ -1179,9 +1171,8 @@ tail_recurse:
 
 	  /* Inner loop.  */
 	  if (flow_loop_nested_p (loop, def_loop))
-	    return follow_ssa_edge_inner_loop_phi
-		(loop, phi, halting_phi, evolution_of_loop,
-		 limit + 1);
+	    return follow_ssa_edge_inner_loop_phi (phi, evolution_of_loop,
+						   limit + 1);
 
 	  /* Outer loop.  */
 	  return t_false;
@@ -1239,7 +1230,7 @@ tail_recurse:
     CASE_CONVERT:
       {
 	/* This assignment is under the form "a_1 = (cast) rhs.  */
-	t_bool res = follow_ssa_edge_expr (loop, at_stmt, rhs0, halting_phi,
+	t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
 					   evolution_of_loop, limit);
 	*evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
 	return res;
@@ -1268,18 +1259,18 @@ tail_recurse:
 	  && (TREE_CODE (rhs1) != SSA_NAME || code == MINUS_EXPR))
 	{
 	  /* Match an assignment under the form:
-	     "a = b +- ...".
-	     Use tail-recursion for the simple case.  */
-	  *evolution_of_loop = add_to_evolution
-	      (loop->num, chrec_convert (type, *evolution_of_loop,
-					 at_stmt),
-	       code, rhs1, at_stmt);
-	  expr = rhs0;
-	  goto tail_recurse;
+	     "a = b +- ...".  */
+	  t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
+					     evolution_of_loop, limit);
+	  if (res == t_true)
+	    *evolution_of_loop = add_to_evolution
+		(chrec_convert (type, *evolution_of_loop, at_stmt),
+		 code, rhs1, at_stmt);
+	  return res;
 	}
       /* Else search for the SCC in both rhs0 and rhs1.  */
-      return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
-				     halting_phi, evolution_of_loop, limit);
+      return follow_ssa_edge_binary (at_stmt, type, rhs0, code, rhs1,
+				     evolution_of_loop, limit);
 
     case ASSERT_EXPR:
       /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
@@ -1291,6 +1282,42 @@ tail_recurse:
       return t_false;
     }
 }
+
+
+/* This section selects the loops that will be good candidates for the
+   scalar evolution analysis.  For the moment, greedily select all the
+   loop nests we could analyze.  */
+
+/* For a loop with a single exit edge, return the COND_EXPR that
+   guards the exit edge.  If the expression is too difficult to
+   analyze, then give up.  */
+
+gcond *
+get_loop_exit_condition (const class loop *loop)
+{
+  gcond *res = NULL;
+  edge exit_edge = single_exit (loop);
+
+  if (dump_file && (dump_flags & TDF_SCEV))
+    fprintf (dump_file, "(get_loop_exit_condition \n  ");
+
+  if (exit_edge)
+    {
+      gimple *stmt;
+
+      stmt = last_stmt (exit_edge->src);
+      if (gcond *cond_stmt = safe_dyn_cast <gcond *> (stmt))
+	res = cond_stmt;
+    }
+
+  if (dump_file && (dump_flags & TDF_SCEV))
+    {
+      print_gimple_stmt (dump_file, res, 0);
+      fprintf (dump_file, ")\n");
+    }
+
+  return res;
+}
 
 
 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
@@ -1381,7 +1408,7 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
   for (i = 0; i < n; i++)
     {
       tree arg = PHI_ARG_DEF (loop_phi_node, i);
-      tree ev_fn;
+      tree ev_fn = chrec_dont_know;
       t_bool res;
 
       /* Select the edges that enter the loop body.  */
@@ -1394,9 +1421,8 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
 	  bool val = false;
 
 	  /* Pass in the initial condition to the follow edge function.  */
-	  ev_fn = init_cond;
-	  res = follow_ssa_edge_expr (loop, loop_phi_node, arg,
-				      loop_phi_node, &ev_fn, 0);
+	  scev_dfs dfs (loop, loop_phi_node, init_cond);
+	  res = dfs.get_ev (&ev_fn, arg);
 
 	  /* If ev_fn has no evolution in the inner loop, and the
 	     init_cond is not equal to ev_fn, then we have an
@@ -1551,7 +1577,6 @@ analyze_initial_condition (gphi *loop_phi_node)
 static tree
 interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
 {
-  tree res;
   class loop *phi_loop = loop_containing_stmt (loop_phi_node);
   tree init_cond;
 
@@ -1559,26 +1584,7 @@ interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
 
   /* Otherwise really interpret the loop phi.  */
   init_cond = analyze_initial_condition (loop_phi_node);
-  res = analyze_evolution_in_loop (loop_phi_node, init_cond);
-
-  /* Verify we maintained the correct initial condition throughout
-     possible conversions in the SSA chain.  */
-  if (res != chrec_dont_know)
-    {
-      tree new_init = res;
-      if (CONVERT_EXPR_P (res)
-	  && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
-	new_init = fold_convert (TREE_TYPE (res),
-				 CHREC_LEFT (TREE_OPERAND (res, 0)));
-      else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
-	new_init = CHREC_LEFT (res);
-      STRIP_USELESS_TYPE_CONVERSION (new_init);
-      if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
-	  || !operand_equal_p (init_cond, new_init, 0))
-	return chrec_dont_know;
-    }
-
-  return res;
+  return analyze_evolution_in_loop (loop_phi_node, init_cond);
 }
 
 /* This function merges the branches of a condition-phi-node,
