* [trans-mem] cgraph edges vs function cloning @ 2009-07-23 1:39 Richard Henderson 2009-07-23 17:28 ` Jan Hubicka 0 siblings, 1 reply; 10+ messages in thread From: Richard Henderson @ 2009-07-23 1:39 UTC (permalink / raw) To: jh, gcc 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-23 1:39 [trans-mem] cgraph edges vs function cloning Richard Henderson @ 2009-07-23 17:28 ` Jan Hubicka 2009-07-23 20:59 ` Richard Henderson 2009-07-27 23:08 ` Richard Henderson 0 siblings, 2 replies; 10+ messages in thread From: Jan Hubicka @ 2009-07-23 17:28 UTC (permalink / raw) To: Richard Henderson; +Cc: jh, gcc > 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-23 17:28 ` Jan Hubicka @ 2009-07-23 20:59 ` Richard Henderson 2009-07-27 23:08 ` Richard Henderson 1 sibling, 0 replies; 10+ messages in thread From: Richard Henderson @ 2009-07-23 20:59 UTC (permalink / raw) To: Jan Hubicka; +Cc: Richard Henderson, jh, gcc 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-23 17:28 ` Jan Hubicka 2009-07-23 20:59 ` Richard Henderson @ 2009-07-27 23:08 ` Richard Henderson 2009-07-28 17:16 ` Jan Hubicka 1 sibling, 1 reply; 10+ messages in thread From: Richard Henderson @ 2009-07-27 23:08 UTC (permalink / raw) To: Jan Hubicka; +Cc: jh, gcc > 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-27 23:08 ` Richard Henderson @ 2009-07-28 17:16 ` Jan Hubicka 2009-07-28 17:44 ` Richard Henderson 0 siblings, 1 reply; 10+ messages in thread From: Jan Hubicka @ 2009-07-28 17:16 UTC (permalink / raw) To: Richard Henderson; +Cc: Jan Hubicka, jh, gcc > > 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-28 17:16 ` Jan Hubicka @ 2009-07-28 17:44 ` Richard Henderson 2009-07-28 23:26 ` Richard Henderson 0 siblings, 1 reply; 10+ messages in thread From: Richard Henderson @ 2009-07-28 17:44 UTC (permalink / raw) To: Jan Hubicka; +Cc: jh, gcc 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-28 17:44 ` Richard Henderson @ 2009-07-28 23:26 ` Richard Henderson 2009-07-29 6:43 ` Jan Hubicka 2009-07-29 7:27 ` Martin Jambor 0 siblings, 2 replies; 10+ messages in thread From: Richard Henderson @ 2009-07-28 23:26 UTC (permalink / raw) To: Jan Hubicka; +Cc: jh, gcc 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-28 23:26 ` Richard Henderson @ 2009-07-29 6:43 ` Jan Hubicka 2009-07-29 7:27 ` Martin Jambor 1 sibling, 0 replies; 10+ messages in thread From: Jan Hubicka @ 2009-07-29 6:43 UTC (permalink / raw) To: Richard Henderson; +Cc: Jan Hubicka, jh, gcc > 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~ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-28 23:26 ` Richard Henderson 2009-07-29 6:43 ` Jan Hubicka @ 2009-07-29 7:27 ` Martin Jambor 2009-07-29 16:24 ` Richard Henderson 1 sibling, 1 reply; 10+ messages in thread From: Martin Jambor @ 2009-07-29 7:27 UTC (permalink / raw) To: Richard Henderson; +Cc: Jan Hubicka, jh, gcc 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [trans-mem] cgraph edges vs function cloning 2009-07-29 7:27 ` Martin Jambor @ 2009-07-29 16:24 ` Richard Henderson 0 siblings, 0 replies; 10+ messages in thread From: Richard Henderson @ 2009-07-29 16:24 UTC (permalink / raw) To: gcc; +Cc: GCC Patches [-- 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) ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2009-07-29 16:24 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2009-07-23 1:39 [trans-mem] cgraph edges vs function cloning Richard Henderson 2009-07-23 17:28 ` Jan Hubicka 2009-07-23 20:59 ` Richard Henderson 2009-07-27 23:08 ` Richard Henderson 2009-07-28 17:16 ` Jan Hubicka 2009-07-28 17:44 ` Richard Henderson 2009-07-28 23:26 ` Richard Henderson 2009-07-29 6:43 ` Jan Hubicka 2009-07-29 7:27 ` Martin Jambor 2009-07-29 16:24 ` Richard Henderson
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).