Re: [pretty-ipa] Enable IPA nothrow discovery

[Jan Hubicka <hubicka at ucw dot cz>]

> On Tue, Apr 14, 2009 at 10:54 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> Patch truncated?
> >
> > Indeed it is.
> > The patch caused quite noticeable improvements on pretty-ipa tramp3d
> > tonight. ?I will first re-check that there is nothing obviously wrong.
> > I would not expect it to help that much on largely acyclic control flow
> > so either there are more cycles in tramp3d that I tought, or local pure
> > const is unnecesarily conservative or IPA pure const produce wrong code.
> > I would expect last case to show in testsuite, we have plenty of
> > throwing tests there.
> 
> I suggest to make loop_nest a unsigned short and swap
> inline_failed (4 bytes(!)) and count (8 bytes) and move uid right
> after count.

Good point :). Now when inline_failed is no longer a pointer, we can
sequeeze space out there.  I will do that once other cgraph changes are
merged.

Thanks,
Honza
> 
> Richard.
> 
> 
> > Honza
> >
> > ? ? ? ?* cgraph.c (cgraph_make_edge, dump_cgraph_node, cgraph_set_call_stmt):
> > ? ? ? ?Set nothrow flag.
> > ? ? ? ?* cgraph.h (struct function): Reduce loop_nest to 30 bits; add
> > ? ? ? ?can_throw_external flag.
> > ? ? ? ?* ipa-reference.c (ipa_utils_reduced_inorder): Update call.
> > ? ? ? ?* ipa-pure-const.c (ignore_edge): New function.
> > ? ? ? ?(propagate): Compute order for NOTHROW computation; set NOTHROWs
> > ? ? ? ?only over can_throw_external edges.
> > ? ? ? ?(local_pure_const): Add nothrow flag.
> > ? ? ? ?* ipa-utils.c (searchc): Add ignore_edge callback.
> > ? ? ? ?(ipa_utils_reduced_inorder): Add ignore_edge callback.
> > ? ? ? ?* ipa-utils.h (ipa_utils_reduced_inorder): Update prototype.
> > ? ? ? ?(set_nothrow_function_flags): Update cgraph.
> > ? ? ? ?* tree-cfg.c (verify_stmt): Relax nothrow checking when in IPA mode.
> > Index: cgraph.c
> > ===================================================================
> > --- cgraph.c ? ?(revision 146003)
> > +++ cgraph.c ? ?(working copy)
> > @@ -639,6 +639,7 @@
> > ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? htab_hash_pointer (e->call_stmt));
> > ? ? }
> > ? e->call_stmt = new_stmt;
> > + ?e->can_throw_external = stmt_can_throw_external (new_stmt);
> > ? if (e->caller->call_site_hash)
> > ? ? {
> > ? ? ? void **slot;
> > @@ -667,7 +668,6 @@
> > ? ? for (node = orig->clones; node != orig;)
> > ? ? ? {
> > ? ? ? ?struct cgraph_edge *edge = cgraph_edge (node, old_stmt);
> > -
> > ? ? ? ?if (edge)
> > ? ? ? ? ?cgraph_set_call_stmt (edge, new_stmt);
> > ? ? ? ?if (node->clones)
> > @@ -774,6 +774,7 @@
> > ? edge->caller = caller;
> > ? edge->callee = callee;
> > ? edge->call_stmt = call_stmt;
> > + ?edge->can_throw_external = stmt_can_throw_external (call_stmt);
> > ? edge->prev_caller = NULL;
> > ? edge->next_caller = callee->callers;
> > ? if (callee->callers)
> > @@ -1386,6 +1387,8 @@
> > ? ? ? ?fprintf(f, "(inlined) ");
> > ? ? ? if (edge->indirect_call)
> > ? ? ? ?fprintf(f, "(indirect) ");
> > + ? ? ?if (edge->can_throw_external)
> > + ? ? ? fprintf(f, "(can throw external) ");
> > ? ? }
> >
> > ? fprintf (f, "\n ?calls: ");
> > Index: cgraph.h
> > ===================================================================
> > --- cgraph.h ? ?(revision 146003)
> > +++ cgraph.h ? ?(working copy)
> > @@ -248,9 +248,11 @@
> > ? ? ?per function call. ?The range is 0 to CGRAPH_FREQ_MAX. ?*/
> > ? int frequency;
> > ? /* Depth of loop nest, 1 means no loop nest. ?*/
> > - ?unsigned int loop_nest : 31;
> > + ?unsigned int loop_nest : 30;
> > ? /* Whether this edge describes a call that was originally indirect. ?*/
> > ? unsigned int indirect_call : 1;
> > + ?/* Can this call throw externally? ?*/
> > + ?unsigned int can_throw_external : 1;
> > ? /* Unique id of the edge. ?*/
> > ? int uid;
> > ?};
> > Index: ipa-reference.c
> > ===================================================================
> > --- ipa-reference.c ? ? (revision 146003)
> > +++ ipa-reference.c ? ? (working copy)
> > @@ -1020,7 +1020,7 @@
> > ? struct cgraph_node *w;
> > ? struct cgraph_node **order =
> > ? ? XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
> > - ?int order_pos = ipa_utils_reduced_inorder (order, false, true);
> > + ?int order_pos = ipa_utils_reduced_inorder (order, false, true, NULL);
> > ? int i;
> >
> > ? cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
> > @@ -1031,7 +1031,7 @@
> > ? ? ?the global information. ?All the nodes within a cycle will have
> > ? ? ?the same info so we collapse cycles first. ?Then we can do the
> > ? ? ?propagation in one pass from the leaves to the roots. ?*/
> > - ?order_pos = ipa_utils_reduced_inorder (order, true, true);
> > + ?order_pos = ipa_utils_reduced_inorder (order, true, true, NULL);
> > ? if (dump_file)
> > ? ? ipa_utils_print_order(dump_file, "reduced", order, order_pos);
> >
> > Index: ipa-pure-const.c
> > ===================================================================
> > --- ipa-pure-const.c ? ?(revision 146003)
> > +++ ipa-pure-const.c ? ?(working copy)
> > @@ -671,6 +671,12 @@
> > ? visited_nodes = NULL;
> > ?}
> >
> > +static bool
> > +ignore_edge (struct cgraph_edge *e)
> > +{
> > + ?return (!e->can_throw_external);
> > +}
> > +
> > ?/* Produce the global information by preforming a transitive closure
> > ? ?on the local information that was produced by generate_summary.
> > ? ?Note that there is no function_transform pass since this only
> > @@ -690,7 +696,7 @@
> > ? cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
> > ? cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
> > ? cgraph_remove_node_removal_hook (node_removal_hook_holder);
> > - ?order_pos = ipa_utils_reduced_inorder (order, true, false);
> > + ?order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
> > ? if (dump_file)
> > ? ? {
> > ? ? ? dump_cgraph (dump_file);
> > @@ -705,7 +711,6 @@
> > ? ? {
> > ? ? ? enum pure_const_state_e pure_const_state = IPA_CONST;
> > ? ? ? bool looping = false;
> > - ? ? ?bool can_throw = false;
> > ? ? ? int count = 0;
> > ? ? ? node = order[i];
> >
> > @@ -718,13 +723,10 @@
> > ? ? ? ? ?if (pure_const_state < w_l->pure_const_state)
> > ? ? ? ? ? ?pure_const_state = w_l->pure_const_state;
> >
> > - ? ? ? ? if (w_l->can_throw)
> > - ? ? ? ? ? can_throw = true;
> > ? ? ? ? ?if (w_l->looping)
> > ? ? ? ? ? ?looping = true;
> >
> > - ? ? ? ? if (pure_const_state == IPA_NEITHER
> > - ? ? ? ? ? ? && can_throw)
> > + ? ? ? ? if (pure_const_state == IPA_NEITHER)
> > ? ? ? ? ? ?break;
> >
> > ? ? ? ? ?count++;
> > @@ -741,16 +743,10 @@
> > ? ? ? ? ? ? ? ? ?funct_state y_l = get_function_state (y);
> > ? ? ? ? ? ? ? ? ?if (pure_const_state < y_l->pure_const_state)
> > ? ? ? ? ? ? ? ? ? ?pure_const_state = y_l->pure_const_state;
> > - ? ? ? ? ? ? ? ? if (pure_const_state == IPA_NEITHER
> > - ? ? ? ? ? ? ? ? ? ? && can_throw)
> > + ? ? ? ? ? ? ? ? if (pure_const_state == IPA_NEITHER)
> > ? ? ? ? ? ? ? ? ? ?break;
> > ? ? ? ? ? ? ? ? ?if (y_l->looping)
> > ? ? ? ? ? ? ? ? ? ?looping = true;
> > - ? ? ? ? ? ? ? ? if (y_l->can_throw && !TREE_NOTHROW (w->decl)
> > - ? ? ? ? ? ? ? ? ? ? /* FIXME: We should check that the throw can get external.
> > - ? ? ? ? ? ? ? ? ? ? ? ?We also should handle only loops formed by can throw external
> > - ? ? ? ? ? ? ? ? ? ? ? ?edges. ?*/)
> > - ? ? ? ? ? ? ? ? ? can_throw = true;
> > ? ? ? ? ? ? ? ?}
> > ? ? ? ? ? ?}
> > ? ? ? ? ?w_info = (struct ipa_dfs_info *) w->aux;
> > @@ -800,12 +796,80 @@
> > ? ? ? ? ? ?default:
> > ? ? ? ? ? ? ?break;
> > ? ? ? ? ? ?}
> > + ? ? ? ? w_info = (struct ipa_dfs_info *) w->aux;
> > + ? ? ? ? w = w_info->next_cycle;
> > + ? ? ? }
> > + ? ?}
> > +
> > + ?/* Cleanup. */
> > + ?for (node = cgraph_nodes; node; node = node->next)
> > + ? ?{
> > + ? ? ?/* Get rid of the aux information. ?*/
> > + ? ? ?if (node->aux)
> > + ? ? ? {
> > + ? ? ? ? w_info = (struct ipa_dfs_info *) node->aux;
> > + ? ? ? ? free (node->aux);
> > + ? ? ? ? node->aux = NULL;
> > + ? ? ? }
> > + ? ?}
> > + ?order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
> > + ?if (dump_file)
> > + ? ?{
> > + ? ? ?dump_cgraph (dump_file);
> > + ? ? ?ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
> > + ? ?}
> > + ?/* Propagate the local information thru the call graph to produce
> > + ? ? the global information. ?All the nodes within a cycle will have
> > + ? ? the same info so we collapse cycles first. ?Then we can do the
> > + ? ? propagation in one pass from the leaves to the roots. ?*/
> > + ?for (i = 0; i < order_pos; i++ )
> > + ? ?{
> > + ? ? ?bool can_throw = false;
> > + ? ? ?node = order[i];
> > +
> > + ? ? ?/* Find the worst state for any node in the cycle. ?*/
> > + ? ? ?w = node;
> > + ? ? ?while (w)
> > + ? ? ? {
> > + ? ? ? ? struct cgraph_edge *e;
> > + ? ? ? ? funct_state w_l = get_function_state (w);
> > +
> > + ? ? ? ? if (w_l->can_throw)
> > + ? ? ? ? ? can_throw = true;
> > +
> > + ? ? ? ? if (can_throw)
> > + ? ? ? ? ? break;
> > +
> > + ? ? ? ? for (e = w->callees; e; e = e->next_callee)
> > + ? ? ? ? ? {
> > + ? ? ? ? ? ? struct cgraph_node *y = e->callee;
> > +
> > + ? ? ? ? ? ? if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
> > + ? ? ? ? ? ? ? {
> > + ? ? ? ? ? ? ? ? funct_state y_l = get_function_state (y);
> > +
> > + ? ? ? ? ? ? ? ? if (can_throw)
> > + ? ? ? ? ? ? ? ? ? break;
> > + ? ? ? ? ? ? ? ? if (y_l->can_throw && !TREE_NOTHROW (w->decl)
> > + ? ? ? ? ? ? ? ? ? ? && e->can_throw_external)
> > + ? ? ? ? ? ? ? ? ? can_throw = true;
> > + ? ? ? ? ? ? ? }
> > + ? ? ? ? ? }
> > + ? ? ? ? w_info = (struct ipa_dfs_info *) w->aux;
> > + ? ? ? ? w = w_info->next_cycle;
> > + ? ? ? }
> > +
> > + ? ? ?/* Copy back the region's pure_const_state which is shared by
> > + ? ? ? ?all nodes in the region. ?*/
> > + ? ? ?w = node;
> > + ? ? ?while (w)
> > + ? ? ? {
> > ? ? ? ? ?if (!can_throw && !TREE_NOTHROW (w->decl))
> > ? ? ? ? ? ?{
> > - ? ? ? ? ? ? /* FIXME: TREE_NOTHROW is not set because passmanager will execute
> > - ? ? ? ? ? ? ? ?verify_ssa and verify_cfg on every function. ?Before fixup_cfg is done,
> > - ? ? ? ? ? ? ? ?those functions are going to have NOTHROW calls in EH regions reulting
> > - ? ? ? ? ? ? ? ?in ICE. ?*/
> > + ? ? ? ? ? ? struct cgraph_edge *e;
> > + ? ? ? ? ? ? TREE_NOTHROW (w->decl) = true;
> > + ? ? ? ? ? ? for (e = w->callers; e; e = e->next_caller)
> > + ? ? ? ? ? ? ? e->can_throw_external = false;
> > ? ? ? ? ? ? ?if (dump_file)
> > ? ? ? ? ? ? ? ?fprintf (dump_file, "Function found to be nothrow: %s\n",
> > ? ? ? ? ? ? ? ? ? ? ? ? cgraph_node_name (w));
> > @@ -952,7 +1016,12 @@
> > ? ? }
> > ? if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
> > ? ? {
> > - ? ? ?TREE_NOTHROW (current_function_decl) = 1;
> > + ? ? ?struct cgraph_edge *e;
> > +
> > + ? ? ?TREE_NOTHROW (current_function_decl) = true;
> > + ? ? ?for (e = cgraph_node (current_function_decl)->callers;
> > + ? ? ? ? ? e; e = e->next_caller)
> > + ? ? ? e->can_throw_external = false;
> > ? ? ? changed = true;
> > ? ? ? if (dump_file)
> > ? ? ? ?fprintf (dump_file, "Function found to be nothrow: %s\n",
> > Index: ipa-utils.c
> > ===================================================================
> > --- ipa-utils.c (revision 146003)
> > +++ ipa-utils.c (working copy)
> > @@ -81,7 +81,8 @@
> > ? ?searching from. ?*/
> >
> > ?static void
> > -searchc (struct searchc_env* env, struct cgraph_node *v)
> > +searchc (struct searchc_env* env, struct cgraph_node *v,
> > + ? ? ? ?bool (*ignore_edge) (struct cgraph_edge *))
> > ?{
> > ? struct cgraph_edge *edge;
> > ? struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
> > @@ -101,12 +102,15 @@
> > ? ? ? struct ipa_dfs_info * w_info;
> > ? ? ? struct cgraph_node *w = edge->callee;
> >
> > + ? ? ?if (ignore_edge && ignore_edge (edge))
> > + ? ? ? ?continue;
> > +
> > ? ? ? if (w->aux && cgraph_function_body_availability (edge->callee) > AVAIL_OVERWRITABLE)
> > ? ? ? ?{
> > ? ? ? ? ?w_info = (struct ipa_dfs_info *) w->aux;
> > ? ? ? ? ?if (w_info->new_node)
> > ? ? ? ? ? ?{
> > - ? ? ? ? ? ? searchc (env, w);
> > + ? ? ? ? ? ? searchc (env, w, ignore_edge);
> > ? ? ? ? ? ? ?v_info->low_link =
> > ? ? ? ? ? ? ? ?(v_info->low_link < w_info->low_link) ?
> > ? ? ? ? ? ? ? ?v_info->low_link : w_info->low_link;
> > @@ -152,7 +156,8 @@
> >
> > ?int
> > ?ipa_utils_reduced_inorder (struct cgraph_node **order,
> > - ? ? ? ? ? ? ? ? ? ? ? ? ?bool reduce, bool allow_overwritable)
> > + ? ? ? ? ? ? ? ? ? ? ? ? ?bool reduce, bool allow_overwritable,
> > + ? ? ? ? ? ? ? ? ? ? ? ? ?bool (*ignore_edge) (struct cgraph_edge *))
> > ?{
> > ? struct cgraph_node *node;
> > ? struct searchc_env env;
> > @@ -193,7 +198,7 @@
> > ? while (result)
> > ? ? {
> > ? ? ? node = (struct cgraph_node *)result->value;
> > - ? ? ?searchc (&env, node);
> > + ? ? ?searchc (&env, node, ignore_edge);
> > ? ? ? result = splay_tree_min (env.nodes_marked_new);
> > ? ? }
> > ? splay_tree_delete (env.nodes_marked_new);
> > Index: ipa-utils.h
> > ===================================================================
> > --- ipa-utils.h (revision 146003)
> > +++ ipa-utils.h (working copy)
> > @@ -39,7 +39,8 @@
> >
> > ?/* In ipa-utils.c ?*/
> > ?void ipa_utils_print_order (FILE*, const char *, struct cgraph_node**, int);
> > -int ipa_utils_reduced_inorder (struct cgraph_node **, bool, bool);
> > +int ipa_utils_reduced_inorder (struct cgraph_node **, bool, bool,
> > + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?bool (*ignore_edge) (struct cgraph_edge *));
> > ?tree get_base_var (tree);
> >
> >
> > Index: except.c
> > ===================================================================
> > --- except.c ? ?(revision 146003)
> > +++ except.c ? ?(working copy)
> > @@ -3548,7 +3550,13 @@
> > ? if (crtl->nothrow
> > ? ? ? && (cgraph_function_body_availability (cgraph_node (current_function_decl))
> > ? ? ? ? ? >= AVAIL_AVAILABLE))
> > - ? ?TREE_NOTHROW (current_function_decl) = 1;
> > + ? ?{
> > + ? ? ?struct cgraph_node *node = cgraph_node (current_function_decl);
> > + ? ? ?struct cgraph_edge *e;
> > + ? ? ?for (e = node->callers; e; e = e->next_caller)
> > + ? ? ? ?e->can_throw_external = false;
> > + ? ? ?TREE_NOTHROW (current_function_decl) = 1;
> > + ? ?}
> > ? return 0;
> > ?}
> >
> > Index: tree-cfg.c
> > ===================================================================
> > --- tree-cfg.c ?(revision 146003)
> > +++ tree-cfg.c ?(working copy)
> > @@ -4097,7 +4097,10 @@
> > ? ? ?to match. ?*/
> > ? if (lookup_stmt_eh_region (stmt) >= 0)
> > ? ? {
> > - ? ? ?if (!stmt_could_throw_p (stmt))
> > + ? ? ?/* During IPA passes, ipa-pure-const sets nothrow flags on calls
> > + ? ? ? ? and they are updated on statements only after fixup_cfg
> > + ? ? ? ?is executed at beggining of expansion stage. ?*/
> > + ? ? ?if (!stmt_could_throw_p (stmt) && cgraph_state != CGRAPH_STATE_IPA_SSA)
> > ? ? ? ?{
> > ? ? ? ? ?error ("statement marked for throw, but doesn%'t");
> > ? ? ? ? ?goto fail;
> >