[trans-mem] cgraph edges vs function cloning

[trans-mem] cgraph edges vs function cloning

[Richard Henderson]

Could I convince you to have a look at the transactional-memory branch 
test libitm/testsuite/libitm.c++/eh-1.C?  I'm getting

z.c:36:1: error: edge void f1()->void* __cxa_allocate_exception(long 
unsigned int) has no corresponding call_stmt
D.2114_4 = __cxa_allocate_exception (4);

z.c:36:1: error: edge void f1()->void __cxa_throw(void*, void*, void 
(*)(void*)) has no corresponding call_stmt
__cxa_throw (D.2114_4, &_ZTIi, 0B);

void f1()/10(-1) @0x7ffff2d75500 availability:available 32 time, 10 
benefit 14 size, 1 benefit reachable body finalized
   called by: void f2()/1 (1.00 per call) (can throw external)
   calls: void _ITM_cxa_throw(void*, void*, void (*)(void*))/12 (1.00 
per call) (can throw external) void* _ITM_cxa_allocate_exception(long 
unsigned int)/11 (1.00 per call) void* __cxa_allocate_exception(long 
unsigned int)/8 (1.00 per call) void __cxa_throw(void*, void*, void 
(*)(void*))/9 (1.00 per call) (can throw external)
z.c:36:1: internal compiler error: verify_cgraph_node failed

This happens because cgraph_copy_node_for_versioning duplicated all of 
the callee edges from the original function, and 
tree_function_versioning created new edges when copying the body of the 
function instead of updating the edges we duplicated.

Frankly, the unholy mess of edge update options has me stumped.  I have 
no idea what's going on in this area.  Why bother with any of it anyway? 
  Why not just always create all new callee edges when instantiating the 
new body?


r~

Re: [trans-mem] cgraph edges vs function cloning

[Jan Hubicka]

> Could I convince you to have a look at the transactional-memory branch 
> test libitm/testsuite/libitm.c++/eh-1.C?  I'm getting
> 
> z.c:36:1: error: edge void f1()->void* __cxa_allocate_exception(long 
> unsigned int) has no corresponding call_stmt
> D.2114_4 = __cxa_allocate_exception (4);
> 
> z.c:36:1: error: edge void f1()->void __cxa_throw(void*, void*, void 
> (*)(void*)) has no corresponding call_stmt
> __cxa_throw (D.2114_4, &_ZTIi, 0B);
> 
> void f1()/10(-1) @0x7ffff2d75500 availability:available 32 time, 10 
> benefit 14 size, 1 benefit reachable body finalized
>   called by: void f2()/1 (1.00 per call) (can throw external)
>   calls: void _ITM_cxa_throw(void*, void*, void (*)(void*))/12 (1.00 
> per call) (can throw external) void* _ITM_cxa_allocate_exception(long 
> unsigned int)/11 (1.00 per call) void* __cxa_allocate_exception(long 
> unsigned int)/8 (1.00 per call) void __cxa_throw(void*, void*, void 
> (*)(void*))/9 (1.00 per call) (can throw external)
> z.c:36:1: internal compiler error: verify_cgraph_node failed
> 
> This happens because cgraph_copy_node_for_versioning duplicated all of 
> the callee edges from the original function, and 
> tree_function_versioning created new edges when copying the body of the 
> function instead of updating the edges we duplicated.
> 
> Frankly, the unholy mess of edge update options has me stumped.  I have 
> no idea what's going on in this area.  Why bother with any of it anyway? 
>  Why not just always create all new callee edges when instantiating the 
> new body?

Well, while doing main IPA passes, we need to preserve information
attached to edges, so we want to copy them and not create all of them
from scratch.

So the basic idea is to duplicate all the edges with old statement and
when new statements are created, tree_function_versioning should update
the call_stmt and create new edges only when new call really appears (it
is possible when we do constant propagation or such).

When you are not copying the whole function body, you will need to
remove those edges that are outside region being duplicated, perhaps
that is the problem?

I will try to look into this.
Honza
> 
> 
> r~

Re: [trans-mem] cgraph edges vs function cloning

[Richard Henderson]

On 07/23/2009 10:28 AM, Jan Hubicka wrote:
> When you are not copying the whole function body, you will need to
> remove those edges that are outside region being duplicated, perhaps
> that is the problem?

Nope, I'm copying the whole body and adjusting it afterward.


r~

Re: [trans-mem] cgraph edges vs function cloning

[Richard Henderson]

>               struct cgraph_edge *edge = cgraph_edge (id->src_node, orig_stmt);
POINT_A
>               int flags;
>
>               switch (id->transform_call_graph_edges)
>                 {
>               case CB_CGE_DUPLICATE:
>                 if (edge)
>                   cgraph_clone_edge (edge, id->dst_node, stmt,
>                                            REG_BR_PROB_BASE, 1,
>                                            edge->frequency, true);
>                 break;
>
>               case CB_CGE_MOVE_CLONES:
>                 cgraph_set_call_stmt_including_clones (id->dst_node, orig_stmt, stmt);
>                 break;
>
>               case CB_CGE_MOVE:
>                 if (edge)
>                   cgraph_set_call_stmt (edge, stmt);
POINT_B
>                 break;
>
>               default:
>                 gcc_unreachable ();
>                 }
>
>             edge = cgraph_edge (id->src_node, orig_stmt);
POINT_C
>             /* Constant propagation on argument done during inlining
>                may create new direct call.  Produce an edge for it.  */
>             if ((!edge
>                  || (edge->indirect_call
>                      && id->transform_call_graph_edges == CB_CGE_MOVE_CLONES))
>                 && is_gimple_call (stmt)
>                 && (fn = gimple_call_fndecl (stmt)) != NULL)
POINT_D

This code cannot possibly work.

We begin by looking up the edge at POINT_A.
We then move the edge at POINT_B.
We then look up the edge *again* at POINT_C.
Ought we be surprised when we do not find the edge at POINT_D?

After POINT_D, we "fix" the missing edge by creating a new one, which of 
course is a duplicate, which then of course leads to verification failure.

I think POINT_B is additionally buggy in that we've just corrupted
the cgraph node for the source function when we wanted to change the 
destination function.  I believe we should have done

   case CB_CGE_MOVE:
     edge = cgraph_edge (id->dst_node, orig_stmt);
     cgraph_set_call_stmt (edge, stmt);
     // Possibly fix up indirect->direct call here.

Although, frankly I think it would be easiest to *only* create edges 
here.  There ought to be no problem doing the cgraph_clone_edge here
instead of in cgraph_copy_node_for_versioning.  That would still 
preserve all of the information you wanted that's attached to the edges.

Thoughts?


r~

Re: [trans-mem] cgraph edges vs function cloning

[Jan Hubicka]

> >              struct cgraph_edge *edge = cgraph_edge (id->src_node, 
> >              orig_stmt);
> POINT_A
> >              int flags;
> >
> >              switch (id->transform_call_graph_edges)
> >                {
> >              case CB_CGE_DUPLICATE:
> >                if (edge)
> >                  cgraph_clone_edge (edge, id->dst_node, stmt,
> >                                           REG_BR_PROB_BASE, 1,
> >                                           edge->frequency, true);
> >                break;
> >
> >              case CB_CGE_MOVE_CLONES:
> >                cgraph_set_call_stmt_including_clones (id->dst_node, 
> >                orig_stmt, stmt);
> >                break;
> >
> >              case CB_CGE_MOVE:
> >                if (edge)
> >                  cgraph_set_call_stmt (edge, stmt);
> POINT_B
> >                break;
> >
> >              default:
> >                gcc_unreachable ();
> >                }
> >
> >            edge = cgraph_edge (id->src_node, orig_stmt);
> POINT_C
> >            /* Constant propagation on argument done during inlining
> >               may create new direct call.  Produce an edge for it.  */
> >            if ((!edge
> >                 || (edge->indirect_call
> >                     && id->transform_call_graph_edges == 
> >                     CB_CGE_MOVE_CLONES))
> >                && is_gimple_call (stmt)
> >                && (fn = gimple_call_fndecl (stmt)) != NULL)
> POINT_D
> 
> This code cannot possibly work.
> 
> We begin by looking up the edge at POINT_A.
> We then move the edge at POINT_B.
> We then look up the edge *again* at POINT_C.
> Ought we be surprised when we do not find the edge at POINT_D?
> 
> After POINT_D, we "fix" the missing edge by creating a new one, which of 
> course is a duplicate, which then of course leads to verification failure.
> 
> I think POINT_B is additionally buggy in that we've just corrupted
> the cgraph node for the source function when we wanted to change the 
> destination function.  I believe we should have done
> 
>   case CB_CGE_MOVE:
>     edge = cgraph_edge (id->dst_node, orig_stmt);
>     cgraph_set_call_stmt (edge, stmt);
>     // Possibly fix up indirect->direct call here.

Yes, this looks fine.  It looks like bug I formery introduced when
moving code for new clones.
> 
> Although, frankly I think it would be easiest to *only* create edges 
> here.  There ought to be no problem doing the cgraph_clone_edge here
> instead of in cgraph_copy_node_for_versioning.  That would still 
> preserve all of the information you wanted that's attached to the edges.
> 
> Thoughts?

There is code in cgraph_copy_node_for_versioning that redirect callers
in the list to new location.  Since clonning might render some code
unreachable and remove edges, this can lead to ICE.  But since this
was formely invented for IPA-CP, that is now using virtual clones,
perhaps we can simply drop this functionality unless you need it in your
branch?

Honza
> 
> 
> r~

Re: [trans-mem] cgraph edges vs function cloning

[Richard Henderson]

On 07/28/2009 10:16 AM, Jan Hubicka wrote:
> There is code in cgraph_copy_node_for_versioning that redirect callers
> in the list to new location.  Since clonning might render some code
> unreachable and remove edges, this can lead to ICE.  But since this
> was formely invented for IPA-CP, that is now using virtual clones,
> perhaps we can simply drop this functionality unless you need it in your
> branch?

I need nothing complicated from cgraph.  An exact duplicate
of the original function is perfect.

After getting that duplicate, I'll walk through it and make
some localized code changes which are just a tad more complicated
than simple symbol substitution.  After optimization is where
the bulk (but not all) of the changes for TM are applied.

I guess I'll poke at cleaning this up today.  I've got to
familiarize myself with how virtual clones work...


r~

Re: [trans-mem] cgraph edges vs function cloning

[Richard Henderson]

On 07/28/2009 10:44 AM, Richard Henderson wrote:
> I guess I'll poke at cleaning this up today. I've got to
> familiarize myself with how virtual clones work...

The virtual clones that ipa-cp makes seems to be easy.

My thought here is that since (virtual) clones don't
have actual bodies (and when they acquire bodies they
cease to be clones), then there's no reason for them
to have callee edges at all.  If you want the list of
callees for a clone, you look at node->clone_of->callees.
In this way, when we materialize a clone, we don't have
to go looking for (and updating) edges, we just create
them as we copy the statements.

What I don't understand is how the inliner uses clones.
Can you explain this?


r~

Re: [trans-mem] cgraph edges vs function cloning

[Jan Hubicka]

> On 07/28/2009 10:44 AM, Richard Henderson wrote:
> >I guess I'll poke at cleaning this up today. I've got to
> >familiarize myself with how virtual clones work...
> 
> The virtual clones that ipa-cp makes seems to be easy.
> 
> My thought here is that since (virtual) clones don't
> have actual bodies (and when they acquire bodies they
> cease to be clones), then there's no reason for them
> to have callee edges at all.  If you want the list of
> callees for a clone, you look at node->clone_of->callees.
> In this way, when we materialize a clone, we don't have
> to go looking for (and updating) edges, we just create
> them as we copy the statements.

This is not quite true, you can take function, clone it
and then clone one of callees.  Now one call to callee might need to
point to original, while other to the clone. To represent this and
similar transforms you need different set of edges for each clone.

Also the goal is to make clones appear as much as real functions as
possible for the optimizations, so they don't need to deal with too many
special cases.
> 
> What I don't understand is how the inliner uses clones.
> Can you explain this?

We don't apply inlining decisions at the time inliner decide inline A to
B.  Instead inline clone A is created and B's edge to A is redirected to this
clone to represent that later we will duplicate the body and inline it
into the function.

Also concerning your code, please note that clonning never created
identical copies, we had some problems here with saving for inlining.
Since we in general leave statements unfolded in various occasions and
inliner folds on handling some codes, we sometimes end up rendering part
of functions unreachable and removing it etc. even when not doing any
non-trivial substitutions.

Honza
> 
> 
> r~

Re: [trans-mem] cgraph edges vs function cloning

[Martin Jambor]

Hi,

On Tue, Jul 28, 2009 at 04:26:12PM -0700, Richard Henderson wrote:
> On 07/28/2009 10:44 AM, Richard Henderson wrote:
> >I guess I'll poke at cleaning this up today. I've got to
> >familiarize myself with how virtual clones work...
> 
> The virtual clones that ipa-cp makes seems to be easy.
> 
> My thought here is that since (virtual) clones don't
> have actual bodies (and when they acquire bodies they
> cease to be clones), then there's no reason for them
> to have callee edges at all. 

That is not really true.  Consider the following example:

static void a (int i)
{
  DO_SOMETHING_WITH_I (i);
}

void b (int i)  /* Not static! */
{
  a (i);
}

void c (void)
{
  b (2);
}

After ipa-cp (even today), we might end up with a call graph where c
would call b.clone.0 which in turn would call a.clone.1, while the
original b would still call the original a.

Moreover, I have an ipa-cp improvemant patch that removes callee edges
of virtual clones if it can prove that they are never called after a
constant is substituted into a parameter, like in the example below:

int f(int i)
{
  if (i == 0)
    {
      call_some_nasty_function(...);
    }
  ...
}

int g() {return f(1);}

Martin

Re: [trans-mem] cgraph edges vs function cloning

[Richard Henderson]

[-- Attachment #1: Type: text/plain, Size: 320 bytes --]

On 07/29/2009 12:28 AM, Martin Jambor wrote:
> That is not really true.

Whee.  I guess I really didn't understand what was going on.

At present I'm testing the following minimal patch to fix
the double lookup problem I mentioned.  It's uglier than
it ought to be because of incorrect indentation in the
original.


r~

[-- Attachment #2: zz --]
[-- Type: text/plain, Size: 4301 bytes --]

--- tree-inline.c	(revision 150180)
+++ tree-inline.c	(local)
@@ -1496,67 +1496,69 @@ copy_bb (copy_body_data *id, basic_block
 	     callgraph edges and update or duplicate them.  */
 	  if (is_gimple_call (stmt))
 	    {
-	      struct cgraph_edge *edge = cgraph_edge (id->src_node, orig_stmt);
+	      struct cgraph_edge *edge;
 	      int flags;
 
 	      switch (id->transform_call_graph_edges)
 		{
-	      case CB_CGE_DUPLICATE:
-	        if (edge)
-		  cgraph_clone_edge (edge, id->dst_node, stmt,
-					   REG_BR_PROB_BASE, 1,
-					   edge->frequency, true);
-		break;
-
-	      case CB_CGE_MOVE_CLONES:
-		cgraph_set_call_stmt_including_clones (id->dst_node, orig_stmt, stmt);
-		break;
-
-	      case CB_CGE_MOVE:
-	        if (edge)
-		  cgraph_set_call_stmt (edge, stmt);
-		break;
+		case CB_CGE_DUPLICATE:
+		  edge = cgraph_edge (id->src_node, orig_stmt);
+		  if (edge)
+		    edge = cgraph_clone_edge (edge, id->dst_node, stmt,
+					      REG_BR_PROB_BASE, 1,
+					      edge->frequency, true);
+		  break;
+
+		case CB_CGE_MOVE_CLONES:
+		  cgraph_set_call_stmt_including_clones (id->dst_node,
+							 orig_stmt, stmt);
+		  edge = cgraph_edge (id->dst_node, stmt);
+		  break;
+
+		case CB_CGE_MOVE:
+		  edge = cgraph_edge (id->dst_node, orig_stmt);
+		  if (edge)
+		    cgraph_set_call_stmt (edge, stmt);
+		  break;
 
-	      default:
-		gcc_unreachable ();
+		default:
+		  gcc_unreachable ();
 		}
 
-	    edge = cgraph_edge (id->src_node, orig_stmt);
-	    /* Constant propagation on argument done during inlining
-	       may create new direct call.  Produce an edge for it.  */
-	    if ((!edge 
-		 || (edge->indirect_call
-		     && id->transform_call_graph_edges == CB_CGE_MOVE_CLONES))
-		&& is_gimple_call (stmt)
-		&& (fn = gimple_call_fndecl (stmt)) != NULL)
-	      {
-		struct cgraph_node *dest = cgraph_node (fn);
+	      /* Constant propagation on argument done during inlining
+		 may create new direct call.  Produce an edge for it.  */
+	      if ((!edge 
+		   || (edge->indirect_call
+		       && id->transform_call_graph_edges == CB_CGE_MOVE_CLONES))
+		  && is_gimple_call (stmt)
+		  && (fn = gimple_call_fndecl (stmt)) != NULL)
+		{
+		  struct cgraph_node *dest = cgraph_node (fn);
 
-		/* We have missing edge in the callgraph.  This can happen in one case
-		   where previous inlining turned indirect call into direct call by
-		   constant propagating arguments.  In all other cases we hit a bug
-		   (incorrect node sharing is most common reason for missing edges.  */
-		gcc_assert (dest->needed || !dest->analyzed);
-		if (id->transform_call_graph_edges == CB_CGE_MOVE_CLONES)
-		  cgraph_create_edge_including_clones (id->dst_node, dest, stmt,
-						       bb->count,
-						       compute_call_stmt_bb_frequency (id->dst_node->decl, bb),
-						       bb->loop_depth,
-						       CIF_ORIGINALLY_INDIRECT_CALL);
-		else
-		  cgraph_create_edge (id->dst_node, dest, stmt,
-				      bb->count, CGRAPH_FREQ_BASE,
-				      bb->loop_depth)->inline_failed
-		    = CIF_ORIGINALLY_INDIRECT_CALL;
-		if (dump_file)
-		  {
-		     fprintf (dump_file, "Created new direct edge to %s",
-			      cgraph_node_name (dest));
-		  }
-	      }
+		  /* We have missing edge in the callgraph.  This can happen
+		     when previous inlining turned an indirect call into a
+		     direct call by constant propagating arguments.  In all
+		     other cases we hit a bug (incorrect node sharing is the
+		     most common reason for missing edges).  */
+		  gcc_assert (dest->needed || !dest->analyzed);
+		  if (id->transform_call_graph_edges == CB_CGE_MOVE_CLONES)
+		    cgraph_create_edge_including_clones
+		      (id->dst_node, dest, stmt, bb->count,
+		       compute_call_stmt_bb_frequency (id->dst_node->decl, bb),
+		       bb->loop_depth, CIF_ORIGINALLY_INDIRECT_CALL);
+		  else
+		    cgraph_create_edge (id->dst_node, dest, stmt,
+					bb->count, CGRAPH_FREQ_BASE,
+					bb->loop_depth)->inline_failed
+		      = CIF_ORIGINALLY_INDIRECT_CALL;
+		  if (dump_file)
+		    {
+		      fprintf (dump_file, "Created new direct edge to %s",
+			       cgraph_node_name (dest));
+		    }
+		}
 
 	      flags = gimple_call_flags (stmt);
-
 	      if (flags & ECF_MAY_BE_ALLOCA)
 		cfun->calls_alloca = true;
 	      if (flags & ECF_RETURNS_TWICE)