Limit AA walking in IPA summary generation

2019-01-20  Martin Jambor  <mjambor@suse.cz>

	PR ipa/87615
	* ipa-prop.h (struct ipa_func_body_info): Replaced field aa_walked
	with aa_walk_budget.
	* cgraph.h (ipa_polymorphic_call_context::get_dynamic_type): Add
	aa_walk_budget_p parameter.
	* ipa-fnsummary.c (unmodified_parm_1): New parameter fbi.  Limit AA
	walk.  Updated all callers.
	(unmodified_parm): New parameter fbi, pass it to unmodified_parm_1.
	(eliminated_by_inlining_prob): New parameter fbi, pass it on to
	unmodified_parm.
	(will_be_nonconstant_expr_predicate): New parameter fbi, removed
	parameter info.  Extract info from fbi.  Pass fbi to recursive calls
	and to unmodified_parm.
	(phi_result_unknown_predicate): New parameter fbi, removed parameter
	info, updated call to will_be_nonconstant_expr_predicate.
	(param_change_prob): New parameter fbi, limit AA walking.
	(analyze_function_body): Initialize aa_walk_budget in fbi.  Update
	calls to various above functions.
	* ipa-polymorphic-call.c (get_dynamic_type): Add aa_walk_budget_p
	parameter.  Use it to limit AA walking.
	* ipa-prop.c (detect_type_change_from_memory_writes): New parameter
	fbi, limit AA walk.
	(detect_type_change): New parameter fbi, pass it on to
	detect_type_change_from_memory_writes.
	(detect_type_change_ssa): Likewise.
	(aa_overwalked): Removed.
	(parm_preserved_before_stmt_p): Assume fbi is never NULL, stream line
	accordingly, adjust to the neew AA limiting scheme.
	(parm_ref_data_preserved_p): Likewise.
	(ipa_compute_jump_functions_for_edge): Adjust call to
	get_dynamic_type.
	(ipa_analyze_call_uses): Likewise.
	(ipa_analyze_virtual_call_uses): Pass fbi to detect_type_change_ssa.
	(ipa_analyze_node): Initialize aa_walk_budget.
	(ipcp_transform_function): Likewise.
	* tree-ssa-sccvn.c (eliminate_dom_walker::eliminate_stmt): Update call
	to get_dynamic_type.

From-SVN: r268107

7 files changed, 194 insertions, 122 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 01d4e7e..6ce35e0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,43 @@
+2019-01-20  Martin Jambor  <mjambor@suse.cz>
+
+	PR ipa/87615
+	* ipa-prop.h (struct ipa_func_body_info): Replaced field aa_walked
+	with aa_walk_budget.
+	* cgraph.h (ipa_polymorphic_call_context::get_dynamic_type): Add
+	aa_walk_budget_p parameter.
+	* ipa-fnsummary.c (unmodified_parm_1): New parameter fbi.  Limit AA
+	walk.  Updated all callers.
+	(unmodified_parm): New parameter fbi, pass it to unmodified_parm_1.
+	(eliminated_by_inlining_prob): New parameter fbi, pass it on to
+	unmodified_parm.
+	(will_be_nonconstant_expr_predicate): New parameter fbi, removed
+	parameter info.  Extract info from fbi.  Pass fbi to recursive calls
+	and to unmodified_parm.
+	(phi_result_unknown_predicate): New parameter fbi, removed parameter
+	info, updated call to will_be_nonconstant_expr_predicate.
+	(param_change_prob): New parameter fbi, limit AA walking.
+	(analyze_function_body): Initialize aa_walk_budget in fbi.  Update
+	calls to various above functions.
+	* ipa-polymorphic-call.c (get_dynamic_type): Add aa_walk_budget_p
+	parameter.  Use it to limit AA walking.
+	* ipa-prop.c (detect_type_change_from_memory_writes): New parameter
+	fbi, limit AA walk.
+	(detect_type_change): New parameter fbi, pass it on to
+	detect_type_change_from_memory_writes.
+	(detect_type_change_ssa): Likewise.
+	(aa_overwalked): Removed.
+	(parm_preserved_before_stmt_p): Assume fbi is never NULL, stream line
+	accordingly, adjust to the neew AA limiting scheme.
+	(parm_ref_data_preserved_p): Likewise.
+	(ipa_compute_jump_functions_for_edge): Adjust call to
+	get_dynamic_type.
+	(ipa_analyze_call_uses): Likewise.
+	(ipa_analyze_virtual_call_uses): Pass fbi to detect_type_change_ssa.
+	(ipa_analyze_node): Initialize aa_walk_budget.
+	(ipcp_transform_function): Likewise.
+	* tree-ssa-sccvn.c (eliminate_dom_walker::eliminate_stmt): Update call
+	to get_dynamic_type.
+
 2019-01-19  Jakub Jelinek  <jakub@redhat.com>
 
 	* config/aarch64/aarch64.c (aarch64_stack_protect_guard): Move
diff --git a/gcc/cgraph.h b/gcc/cgraph.h
index bb23183..75d4cec 100644
--- a/gcc/cgraph.h
+++ b/gcc/cgraph.h
@@ -1557,7 +1557,7 @@ public:
 
   /* Look for vtable stores or constructor calls to work out dynamic type
      of memory location.  */
-  bool get_dynamic_type (tree, tree, tree, gimple *);
+  bool get_dynamic_type (tree, tree, tree, gimple *, unsigned *);
 
   /* Make context non-speculative.  */
   void clear_speculation ();
diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index dbb95b0..535b3f2 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -941,7 +941,8 @@ mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
    PARM_DECL) will be stored to *SIZE_P in that case too.  */
 
 static tree
-unmodified_parm_1 (gimple *stmt, tree op, HOST_WIDE_INT *size_p)
+unmodified_parm_1 (ipa_func_body_info *fbi, gimple *stmt, tree op,
+		   HOST_WIDE_INT *size_p)
 {
   /* SSA_NAME referring to parm default def?  */
   if (TREE_CODE (op) == SSA_NAME
@@ -959,8 +960,14 @@ unmodified_parm_1 (gimple *stmt, tree op, HOST_WIDE_INT *size_p)
 
       ao_ref refd;
       ao_ref_init (&refd, op);
-      walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
-			  NULL);
+      int walked = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
+				       mark_modified, &modified, NULL, NULL,
+				       fbi->aa_walk_budget + 1);
+      if (walked < 0)
+	{
+	  fbi->aa_walk_budget = 0;
+	  return NULL_TREE;
+	}
       if (!modified)
 	{
 	  if (size_p)
@@ -977,16 +984,17 @@ unmodified_parm_1 (gimple *stmt, tree op, HOST_WIDE_INT *size_p)
    stored to *SIZE_P in that case too.  */
 
 static tree
-unmodified_parm (gimple *stmt, tree op, HOST_WIDE_INT *size_p)
+unmodified_parm (ipa_func_body_info *fbi, gimple *stmt, tree op,
+		 HOST_WIDE_INT *size_p)
 {
-  tree res = unmodified_parm_1 (stmt, op, size_p);
+  tree res = unmodified_parm_1 (fbi, stmt, op, size_p);
   if (res)
     return res;
 
   if (TREE_CODE (op) == SSA_NAME
       && !SSA_NAME_IS_DEFAULT_DEF (op)
       && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
-    return unmodified_parm (SSA_NAME_DEF_STMT (op),
+    return unmodified_parm (fbi, SSA_NAME_DEF_STMT (op),
 			    gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op)),
 			    size_p);
   return NULL_TREE;
@@ -1005,7 +1013,7 @@ unmodified_parm_or_parm_agg_item (struct ipa_func_body_info *fbi,
 				  HOST_WIDE_INT *size_p,
 				  struct agg_position_info *aggpos)
 {
-  tree res = unmodified_parm_1 (stmt, op, size_p);
+  tree res = unmodified_parm_1 (fbi, stmt, op, size_p);
 
   gcc_checking_assert (aggpos);
   if (res)
@@ -1044,7 +1052,7 @@ unmodified_parm_or_parm_agg_item (struct ipa_func_body_info *fbi,
    penalty wrappers.  */
 
 static int
-eliminated_by_inlining_prob (gimple *stmt)
+eliminated_by_inlining_prob (ipa_func_body_info *fbi, gimple *stmt)
 {
   enum gimple_code code = gimple_code (stmt);
   enum tree_code rhs_code;
@@ -1084,7 +1092,7 @@ eliminated_by_inlining_prob (gimple *stmt)
 	    inner_lhs = lhs;
 
 	  /* Reads of parameter are expected to be free.  */
-	  if (unmodified_parm (stmt, inner_rhs, NULL))
+	  if (unmodified_parm (fbi, stmt, inner_rhs, NULL))
 	    rhs_free = true;
 	  /* Match expressions of form &this->field. Those will most likely
 	     combine with something upstream after inlining.  */
@@ -1094,7 +1102,8 @@ eliminated_by_inlining_prob (gimple *stmt)
 	      if (TREE_CODE (op) == PARM_DECL)
 		rhs_free = true;
 	      else if (TREE_CODE (op) == MEM_REF
-		       && unmodified_parm (stmt, TREE_OPERAND (op, 0), NULL))
+		       && unmodified_parm (fbi, stmt, TREE_OPERAND (op, 0),
+					   NULL))
 		rhs_free = true;
 	    }
 
@@ -1107,7 +1116,7 @@ eliminated_by_inlining_prob (gimple *stmt)
 	  /* Reads of parameters passed by reference
 	     expected to be free (i.e. optimized out after inlining).  */
 	  if (TREE_CODE (inner_rhs) == MEM_REF
-	      && unmodified_parm (stmt, TREE_OPERAND (inner_rhs, 0), NULL))
+	      && unmodified_parm (fbi, stmt, TREE_OPERAND (inner_rhs, 0), NULL))
 	    rhs_free = true;
 
 	  /* Copying parameter passed by reference into gimple register is
@@ -1148,7 +1157,8 @@ eliminated_by_inlining_prob (gimple *stmt)
 	  if (TREE_CODE (inner_lhs) == PARM_DECL
 	      || TREE_CODE (inner_lhs) == RESULT_DECL
 	      || (TREE_CODE (inner_lhs) == MEM_REF
-		  && (unmodified_parm (stmt, TREE_OPERAND (inner_lhs, 0), NULL)
+		  && (unmodified_parm (fbi, stmt, TREE_OPERAND (inner_lhs, 0),
+				       NULL)
 		      || (TREE_CODE (TREE_OPERAND (inner_lhs, 0)) == SSA_NAME
 			  && SSA_NAME_VAR (TREE_OPERAND (inner_lhs, 0))
 			  && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
@@ -1396,7 +1406,7 @@ compute_bb_predicates (struct ipa_func_body_info *fbi,
    a compile time constant.  */
 
 static predicate
-will_be_nonconstant_expr_predicate (struct ipa_node_params *info,
+will_be_nonconstant_expr_predicate (ipa_func_body_info *fbi,
 				    struct ipa_fn_summary *summary,
 				    tree expr,
 				    vec<predicate> nonconstant_names)
@@ -1408,8 +1418,8 @@ will_be_nonconstant_expr_predicate (struct ipa_node_params *info,
   while (UNARY_CLASS_P (expr))
     expr = TREE_OPERAND (expr, 0);
 
-  parm = unmodified_parm (NULL, expr, &size);
-  if (parm && (index = ipa_get_param_decl_index (info, parm)) >= 0)
+  parm = unmodified_parm (fbi, NULL, expr, &size);
+  if (parm && (index = ipa_get_param_decl_index (fbi->info, parm)) >= 0)
     return add_condition (summary, index, size, NULL, predicate::changed,
 			  NULL_TREE);
   if (is_gimple_min_invariant (expr))
@@ -1418,34 +1428,36 @@ will_be_nonconstant_expr_predicate (struct ipa_node_params *info,
     return nonconstant_names[SSA_NAME_VERSION (expr)];
   if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
     {
-      predicate p1 = will_be_nonconstant_expr_predicate
-	(info, summary, TREE_OPERAND (expr, 0),
-	 nonconstant_names);
+      predicate p1
+	= will_be_nonconstant_expr_predicate (fbi, summary,
+					      TREE_OPERAND (expr, 0),
+					      nonconstant_names);
       if (p1 == true)
 	return p1;
 
-      predicate p2;
-      p2 = will_be_nonconstant_expr_predicate (info, summary,
-					       TREE_OPERAND (expr, 1),
-					       nonconstant_names);
+      predicate p2
+	= will_be_nonconstant_expr_predicate (fbi, summary,
+					      TREE_OPERAND (expr, 1),
+					      nonconstant_names);
       return p1.or_with (summary->conds, p2);
     }
   else if (TREE_CODE (expr) == COND_EXPR)
     {
-      predicate p1 = will_be_nonconstant_expr_predicate
-	(info, summary, TREE_OPERAND (expr, 0),
-	 nonconstant_names);
+      predicate p1
+	= will_be_nonconstant_expr_predicate (fbi, summary,
+					      TREE_OPERAND (expr, 0),
+					      nonconstant_names);
       if (p1 == true)
 	return p1;
 
-      predicate p2;
-      p2 = will_be_nonconstant_expr_predicate (info, summary,
-					       TREE_OPERAND (expr, 1),
-					       nonconstant_names);
+      predicate p2
+	= will_be_nonconstant_expr_predicate (fbi, summary,
+					      TREE_OPERAND (expr, 1),
+					      nonconstant_names);
       if (p2 == true)
 	return p2;
       p1 = p1.or_with (summary->conds, p2);
-      p2 = will_be_nonconstant_expr_predicate (info, summary,
+      p2 = will_be_nonconstant_expr_predicate (fbi, summary,
 					       TREE_OPERAND (expr, 2),
 					       nonconstant_names);
       return p2.or_with (summary->conds, p1);
@@ -1511,7 +1523,7 @@ will_be_nonconstant_predicate (struct ipa_func_body_info *fbi,
      adding conditionals.  */
   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     {
-      tree parm = unmodified_parm (stmt, use, NULL);
+      tree parm = unmodified_parm (fbi, stmt, use, NULL);
       /* For arguments we can build a condition.  */
       if (parm && ipa_get_param_decl_index (fbi->info, parm) >= 0)
 	continue;
@@ -1533,7 +1545,7 @@ will_be_nonconstant_predicate (struct ipa_func_body_info *fbi,
   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     {
       HOST_WIDE_INT size;
-      tree parm = unmodified_parm (stmt, use, &size);
+      tree parm = unmodified_parm (fbi, stmt, use, &size);
       int index;
 
       if (parm && (index = ipa_get_param_decl_index (fbi->info, parm)) >= 0)
@@ -1620,7 +1632,7 @@ record_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
    ought to be REG_BR_PROB_BASE / estimated_iters.  */
 
 static int
-param_change_prob (gimple *stmt, int i)
+param_change_prob (ipa_func_body_info *fbi, gimple *stmt, int i)
 {
   tree op = gimple_call_arg (stmt, i);
   basic_block bb = gimple_bb (stmt);
@@ -1680,12 +1692,18 @@ param_change_prob (gimple *stmt, int i)
       info.op = op;
       info.stmt = stmt;
       info.bb_set = BITMAP_ALLOC (NULL);
-      walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info,
-			  NULL);
-      if (bitmap_bit_p (info.bb_set, bb->index))
+      int walked
+	= walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info,
+			      NULL, NULL, fbi->aa_walk_budget);
+      if (walked < 0 || bitmap_bit_p (info.bb_set, bb->index))
 	{
 	  if (dump_file)
-	    fprintf (dump_file, "     Set in same BB as used.\n");
+	    {
+	      if (walked < 0)
+		fprintf (dump_file, "     Ran out of AA walking budget.\n");
+	      else
+		fprintf (dump_file, "     Set in same BB as used.\n");
+	    }
 	  BITMAP_FREE (info.bb_set);
 	  return REG_BR_PROB_BASE;
 	}
@@ -1719,7 +1737,7 @@ param_change_prob (gimple *stmt, int i)
    return true and store the pointer the predicate in *P.  */
 
 static bool
-phi_result_unknown_predicate (struct ipa_node_params *info,
+phi_result_unknown_predicate (ipa_func_body_info *fbi,
 			      ipa_fn_summary *summary, basic_block bb,
 			      predicate *p,
 			      vec<predicate> nonconstant_names)
@@ -1764,7 +1782,7 @@ phi_result_unknown_predicate (struct ipa_node_params *info,
       || !is_gimple_ip_invariant (gimple_cond_rhs (stmt)))
     return false;
 
-  *p = will_be_nonconstant_expr_predicate (info, summary,
+  *p = will_be_nonconstant_expr_predicate (fbi, summary,
 					   gimple_cond_lhs (stmt),
 					   nonconstant_names);
   if (*p == true)
@@ -2018,7 +2036,9 @@ analyze_function_body (struct cgraph_node *node, bool early)
 	  fbi.info = IPA_NODE_REF (node);
 	  fbi.bb_infos = vNULL;
 	  fbi.bb_infos.safe_grow_cleared (last_basic_block_for_fn (cfun));
-	  fbi.param_count = count_formal_params(node->decl);
+	  fbi.param_count = count_formal_params (node->decl);
+	  fbi.aa_walk_budget = PARAM_VALUE (PARAM_IPA_MAX_AA_STEPS);
+
 	  nonconstant_names.safe_grow_cleared
 	    (SSANAMES (my_function)->length ());
 	}
@@ -2083,7 +2103,7 @@ analyze_function_body (struct cgraph_node *node, bool early)
 	       gsi_next (&bsi))
 	    {
 	      if (first_phi
-		  && !phi_result_unknown_predicate (fbi.info, info, bb,
+		  && !phi_result_unknown_predicate (&fbi, info, bb,
 						    &phi_predicate,
 						    nonconstant_names))
 		break;
@@ -2173,7 +2193,7 @@ analyze_function_body (struct cgraph_node *node, bool early)
 		    es->param.safe_grow_cleared (count);
 		  for (i = 0; i < count; i++)
 		    {
-		      int prob = param_change_prob (stmt, i);
+		      int prob = param_change_prob (&fbi, stmt, i);
 		      gcc_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
 		      es->param[i].change_prob = prob;
 		    }
@@ -2209,7 +2229,7 @@ analyze_function_body (struct cgraph_node *node, bool early)
 	    {
 	      sreal final_time = (sreal)this_time * freq;
 
-	      prob = eliminated_by_inlining_prob (stmt);
+	      prob = eliminated_by_inlining_prob (&fbi, stmt);
 	      if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file,
 			 "\t\t50%% will be eliminated by inlining\n");
@@ -2286,7 +2306,7 @@ analyze_function_body (struct cgraph_node *node, bool early)
 		&& !is_gimple_min_invariant (niter_desc.niter))
 	    {
 	      predicate will_be_nonconstant
-		= will_be_nonconstant_expr_predicate (fbi.info, info,
+		= will_be_nonconstant_expr_predicate (&fbi, info,
 						      niter_desc.niter,
 						      nonconstant_names);
 	      if (will_be_nonconstant != true)
@@ -2331,8 +2351,7 @@ analyze_function_body (struct cgraph_node *node, bool early)
 		    continue;
 
 		  predicate will_be_nonconstant
-		    = will_be_nonconstant_expr_predicate (fbi.info, info,
-							  iv.step,
+		    = will_be_nonconstant_expr_predicate (&fbi, info, iv.step,
 							  nonconstant_names);
 		  if (will_be_nonconstant != true)
 		    will_be_nonconstant = bb_predicate & will_be_nonconstant;
diff --git a/gcc/ipa-polymorphic-call.c b/gcc/ipa-polymorphic-call.c
index b93bf55..75d8ebc 100644
--- a/gcc/ipa-polymorphic-call.c
+++ b/gcc/ipa-polymorphic-call.c
@@ -1554,13 +1554,18 @@ check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
 
    We do not include this analysis in the context analysis itself, because
    it needs memory SSA to be fully built and the walk may be expensive.
-   So it is not suitable for use withing fold_stmt and similar uses.  */
+   So it is not suitable for use withing fold_stmt and similar uses.
+
+   AA_WALK_BUDGET_P, if not NULL, is how statements we should allow
+   walk_aliased_vdefs to examine.  The value should be decremented by the
+   number of stetements we examined or set to zero if exhausted.  */
 
 bool
 ipa_polymorphic_call_context::get_dynamic_type (tree instance,
 						tree otr_object,
 						tree otr_type,
-						gimple *call)
+						gimple *call,
+						unsigned *aa_walk_budget_p)
 {
   struct type_change_info tci;
   ao_ref ao;
@@ -1723,8 +1728,13 @@ ipa_polymorphic_call_context::get_dynamic_type (tree instance,
   tci.speculative = 0;
   tci.seen_unanalyzed_store = false;
 
-  walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
-		      &tci, NULL, &function_entry_reached);
+  unsigned aa_walk_budget = 0;
+  if (aa_walk_budget_p)
+    aa_walk_budget = *aa_walk_budget_p + 1;
+
+  int walked
+   = walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
+			 &tci, NULL, &function_entry_reached, aa_walk_budget);
 
   /* If we did not find any type changing statements, we may still drop
      maybe_in_construction flag if the context already have outer type. 
@@ -1772,6 +1782,16 @@ ipa_polymorphic_call_context::get_dynamic_type (tree instance,
      only if there was dyanmic type store that may affect given variable
      (seen_unanalyzed_store)  */
 
+  if (walked < 0)
+    {
+      if (dump_file)
+	fprintf (dump_file, "  AA walk budget exhausted.\n");
+      *aa_walk_budget_p = 0;
+      return false;
+    }
+  else if (aa_walk_budget_p)
+    *aa_walk_budget_p -= walked;
+
   if (!tci.type_maybe_changed
       || (outer_type
 	  && !dynamic
diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
index 6830f8d..40ab130 100644
--- a/gcc/ipa-prop.c
+++ b/gcc/ipa-prop.c
@@ -746,13 +746,13 @@ param_type_may_change_p (tree function, tree arg, gimple *call)
    that does the heavy work which is usually unnecesary.  */
 
 static bool
-detect_type_change_from_memory_writes (tree arg, tree base, tree comp_type,
-				       gcall *call, struct ipa_jump_func *jfunc,
+detect_type_change_from_memory_writes (ipa_func_body_info *fbi, tree arg,
+				       tree base, tree comp_type, gcall *call,
+				       struct ipa_jump_func *jfunc,
 				       HOST_WIDE_INT offset)
 {
   struct prop_type_change_info tci;
   ao_ref ao;
-  bool entry_reached = false;
 
   gcc_checking_assert (DECL_P (arg)
 		       || TREE_CODE (arg) == MEM_REF
@@ -780,9 +780,11 @@ detect_type_change_from_memory_writes (tree arg, tree base, tree comp_type,
   tci.object = get_base_address (arg);
   tci.type_maybe_changed = false;
 
-  walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
-		      &tci, NULL, &entry_reached);
-  if (!tci.type_maybe_changed)
+  int walked
+    = walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
+			  &tci, NULL, NULL, fbi->aa_walk_budget + 1);
+
+  if (walked >= 0 && !tci.type_maybe_changed)
     return false;
 
   ipa_set_jf_unknown (jfunc);
@@ -796,8 +798,9 @@ detect_type_change_from_memory_writes (tree arg, tree base, tree comp_type,
    returned by get_ref_base_and_extent, as is the offset.  */
 
 static bool
-detect_type_change (tree arg, tree base, tree comp_type, gcall *call,
-		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+detect_type_change (ipa_func_body_info *fbi, tree arg, tree base,
+		    tree comp_type, gcall *call, struct ipa_jump_func *jfunc,
+		    HOST_WIDE_INT offset)
 {
   if (!flag_devirtualize)
     return false;
@@ -807,7 +810,7 @@ detect_type_change (tree arg, tree base, tree comp_type, gcall *call,
 				   TREE_OPERAND (base, 0),
 				   call))
     return false;
-  return detect_type_change_from_memory_writes (arg, base, comp_type,
+  return detect_type_change_from_memory_writes (fbi, arg, base, comp_type,
 						call, jfunc, offset);
 }
 
@@ -816,7 +819,7 @@ detect_type_change (tree arg, tree base, tree comp_type, gcall *call,
    be zero).  */
 
 static bool
-detect_type_change_ssa (tree arg, tree comp_type,
+detect_type_change_ssa (ipa_func_body_info *fbi, tree arg, tree comp_type,
 			gcall *call, struct ipa_jump_func *jfunc)
 {
   gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
@@ -830,7 +833,7 @@ detect_type_change_ssa (tree arg, tree comp_type,
   arg = build2 (MEM_REF, ptr_type_node, arg,
 		build_int_cst (ptr_type_node, 0));
 
-  return detect_type_change_from_memory_writes (arg, arg, comp_type,
+  return detect_type_change_from_memory_writes (fbi, arg, arg, comp_type,
 						call, jfunc, 0);
 }
 
@@ -846,16 +849,6 @@ mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
   return true;
 }
 
-/* Return true if we have already walked so many statements in AA that we
-   should really just start giving up.  */
-
-static bool
-aa_overwalked (struct ipa_func_body_info *fbi)
-{
-  gcc_checking_assert (fbi);
-  return fbi->aa_walked > (unsigned) PARAM_VALUE (PARAM_IPA_MAX_AA_STEPS);
-}
-
 /* Find the nearest valid aa status for parameter specified by INDEX that
    dominates BB.  */
 
@@ -922,28 +915,24 @@ parm_preserved_before_stmt_p (struct ipa_func_body_info *fbi, int index,
   if (TREE_READONLY (base))
     return true;
 
-  /* FIXME: FBI can be NULL if we are being called from outside
-     ipa_node_analysis or ipcp_transform_function, which currently happens
-     during inlining analysis.  It would be great to extend fbi's lifetime and
-     always have it.  Currently, we are just not afraid of too much walking in
-     that case.  */
-  if (fbi)
-    {
-      if (aa_overwalked (fbi))
-	return false;
-      paa = parm_bb_aa_status_for_bb (fbi, gimple_bb (stmt), index);
-      if (paa->parm_modified)
-	return false;
-    }
-  else
-    paa = NULL;
+  gcc_checking_assert (fbi);
+  paa = parm_bb_aa_status_for_bb (fbi, gimple_bb (stmt), index);
+  if (paa->parm_modified)
+    return false;
 
   gcc_checking_assert (gimple_vuse (stmt) != NULL_TREE);
   ao_ref_init (&refd, parm_load);
   int walked = walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified,
-				   &modified, NULL);
-  if (fbi)
-    fbi->aa_walked += walked;
+				   &modified, NULL, NULL,
+				   fbi->aa_walk_budget + 1);
+  if (walked < 0)
+    {
+      modified = true;
+      if (fbi)
+	fbi->aa_walk_budget = 0;
+    }
+  else if (fbi)
+    fbi->aa_walk_budget -= walked;
   if (paa && modified)
     paa->parm_modified = true;
   return !modified;
@@ -988,29 +977,24 @@ parm_ref_data_preserved_p (struct ipa_func_body_info *fbi,
   bool modified = false;
   ao_ref refd;
 
-  /* FIXME: FBI can be NULL if we are being called from outside
-     ipa_node_analysis or ipcp_transform_function, which currently happens
-     during inlining analysis.  It would be great to extend fbi's lifetime and
-     always have it.  Currently, we are just not afraid of too much walking in
-     that case.  */
-  if (fbi)
-    {
-      if (aa_overwalked (fbi))
-	return false;
-      paa = parm_bb_aa_status_for_bb (fbi, gimple_bb (stmt), index);
-      if (paa->ref_modified)
-	return false;
-    }
-  else
-    paa = NULL;
+  gcc_checking_assert (fbi);
+  paa = parm_bb_aa_status_for_bb (fbi, gimple_bb (stmt), index);
+  if (paa->ref_modified)
+    return false;
 
   gcc_checking_assert (gimple_vuse (stmt));
   ao_ref_init (&refd, ref);
   int walked = walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified,
-				   &modified, NULL);
-  if (fbi)
-    fbi->aa_walked += walked;
-  if (paa && modified)
+				   &modified, NULL, NULL,
+				   fbi->aa_walk_budget + 1);
+  if (walked < 0)
+    {
+      modified = true;
+      fbi->aa_walk_budget = 0;
+    }
+  else
+    fbi->aa_walk_budget -= walked;
+  if (modified)
     paa->ref_modified = true;
   return !modified;
 }
@@ -1030,8 +1014,7 @@ parm_ref_data_pass_through_p (struct ipa_func_body_info *fbi, int index,
      function because it is not goin to use it.  But do not cache the result
      either.  Also, no such calculations for non-pointers.  */
   if (!gimple_vuse (call)
-      || !POINTER_TYPE_P (TREE_TYPE (parm))
-      || aa_overwalked (fbi))
+      || !POINTER_TYPE_P (TREE_TYPE (parm)))
     return false;
 
   struct ipa_param_aa_status *paa = parm_bb_aa_status_for_bb (fbi,
@@ -1042,8 +1025,15 @@ parm_ref_data_pass_through_p (struct ipa_func_body_info *fbi, int index,
 
   ao_ref_init_from_ptr_and_size (&refd, parm, NULL_TREE);
   int walked = walk_aliased_vdefs (&refd, gimple_vuse (call), mark_modified,
-				   &modified, NULL);
-  fbi->aa_walked += walked;
+				   &modified, NULL, NULL,
+				   fbi->aa_walk_budget + 1);
+  if (walked < 0)
+    {
+      fbi->aa_walk_budget = 0;
+      modified = true;
+    }
+  else
+    fbi->aa_walk_budget -= walked;
   if (modified)
     paa->pt_modified = true;
   return !modified;
@@ -1851,7 +1841,8 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	  struct ipa_polymorphic_call_context context (cs->caller->decl,
 						       arg, cs->call_stmt,
 						       &instance);
-	  context.get_dynamic_type (instance, arg, NULL, cs->call_stmt);
+	  context.get_dynamic_type (instance, arg, NULL, cs->call_stmt,
+				    &fbi->aa_walk_budget);
 	  *ipa_get_ith_polymorhic_call_context (args, n) = context;
 	  if (!context.useless_p ())
 	    useful_context = true;
@@ -2324,7 +2315,7 @@ ipa_analyze_virtual_call_uses (struct ipa_func_body_info *fbi,
       anc_offset = 0;
       index = ipa_get_param_decl_index (info, SSA_NAME_VAR (obj));
       gcc_assert (index >= 0);
-      if (detect_type_change_ssa (obj, obj_type_ref_class (target),
+      if (detect_type_change_ssa (fbi, obj, obj_type_ref_class (target),
 				  call, &jfunc))
 	return;
     }
@@ -2340,7 +2331,7 @@ ipa_analyze_virtual_call_uses (struct ipa_func_body_info *fbi,
       index = ipa_get_param_decl_index (info,
 					SSA_NAME_VAR (TREE_OPERAND (expr, 0)));
       gcc_assert (index >= 0);
-      if (detect_type_change (obj, expr, obj_type_ref_class (target),
+      if (detect_type_change (fbi, obj, expr, obj_type_ref_class (target),
 			      call, &jfunc, anc_offset))
 	return;
     }
@@ -2388,7 +2379,8 @@ ipa_analyze_call_uses (struct ipa_func_body_info *fbi, gcall *call)
       cs->indirect_info->vptr_changed
 	= !context.get_dynamic_type (instance,
 				     OBJ_TYPE_REF_OBJECT (target),
-				     obj_type_ref_class (target), call);
+				     obj_type_ref_class (target), call,
+				     &fbi->aa_walk_budget);
       cs->indirect_info->context = context;
     }
 
@@ -2588,7 +2580,7 @@ ipa_analyze_node (struct cgraph_node *node)
   fbi.bb_infos = vNULL;
   fbi.bb_infos.safe_grow_cleared (last_basic_block_for_fn (cfun));
   fbi.param_count = ipa_get_param_count (info);
-  fbi.aa_walked = 0;
+  fbi.aa_walk_budget = PARAM_VALUE (PARAM_IPA_MAX_AA_STEPS);
 
   for (struct cgraph_edge *cs = node->callees; cs; cs = cs->next_callee)
     {
@@ -5157,7 +5149,7 @@ ipcp_transform_function (struct cgraph_node *node)
   fbi.bb_infos = vNULL;
   fbi.bb_infos.safe_grow_cleared (last_basic_block_for_fn (cfun));
   fbi.param_count = param_count;
-  fbi.aa_walked = 0;
+  fbi.aa_walk_budget = PARAM_VALUE (PARAM_IPA_MAX_AA_STEPS);
 
   vec_safe_grow_cleared (descriptors, param_count);
   ipa_populate_param_decls (node, *descriptors);
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index 6d1f7ea..7257a6d 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -428,8 +428,9 @@ struct ipa_func_body_info
   /* Number of parameters.  */
   int param_count;
 
-  /* Number of statements already walked by when analyzing this function.  */
-  unsigned int aa_walked;
+  /* Number of statements we are still allowed to walked by when analyzing this
+     function.  */
+  unsigned int aa_walk_budget;
 };
 
 /* ipa_node_params access functions.  Please use these to access fields that
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index ff54a66..7e8e05e 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -5275,7 +5275,7 @@ eliminate_dom_walker::eliminate_stmt (basic_block b, gimple_stmt_iterator *gsi)
 	  ipa_polymorphic_call_context context (current_function_decl,
 						fn, stmt, &instance);
 	  context.get_dynamic_type (instance, OBJ_TYPE_REF_OBJECT (fn),
-				    otr_type, stmt);
+				    otr_type, stmt, NULL);
 	  bool final;
 	  vec <cgraph_node *> targets
 	      = possible_polymorphic_call_targets (obj_type_ref_class (fn),