| Message ID | 201104042307.56517.ebotcazou@adacore.com |
|---|---|
| State | New |
| Headers | show |
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/04/11 15:07, Eric Botcazou wrote: > commit_edge_insertions contains this kludge: > > /* In the old rtl CFG API, it was OK to insert control flow on an > edge, apparently? In cfglayout mode, this will *not* work, and > the caller is responsible for making sure that control flow is > valid at all times. */ > if (current_ir_type () == IR_RTL_CFGLAYOUT) > return; > > blocks = sbitmap_alloc (last_basic_block); > sbitmap_zero (blocks); > FOR_EACH_BB (bb) > if (bb->aux) > { > SET_BIT (blocks, bb->index); > /* Check for forgotten bb->aux values before commit_edge_insertions > call. */ > gcc_assert (bb->aux == &bb->aux); > bb->aux = NULL; > } > find_many_sub_basic_blocks (blocks); > sbitmap_free (blocks); > > > At least on x86/x86-64, there is apparently only one case where control flow > insns are inserted on edges: when the prologue is inserted on the entry edge. > Once this is accounted for, the above kludge can be removed, provided that the > force_nonfallthru RTL routine is enhanced to preserve the loop nest structure. > The result is the attached patch, bootstrapped/regtested on x86 and x86-64. > > I'll be testing it on IA-64 and SPARC over the next few days if there is an > agreement that this is a progress. What about when we have a PHI, which we eliminate by inserting insns on edges and those insns actually form a loop? You can see an example of this in PR48389. I'm not terribly familiar with any of this cfg code these days, so there may be a reason why this isn't going to be a problem that I'm not aware of. I just happened to be looking at 48389 and remembered your RFC. jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJNnJpYAAoJEBRtltQi2kC7QawH/3pVtwugDPR8H6Ai8CyyZSWX jm+sMFFQulccWt6KRA6OzGcYYiU+NCXCJCtqHTl5XWqStxzipOHKhKkJFX7qEfaL eRcxdfV4a9YU6LrIZxzBN3AirW6G1kc6OVjvJLxbkMLtrlGOGbdviyUczdiPD+mS oa+ece+ALigr9vEVQ5ezd6ggnD5mMprrciV+sJdZOk8dExV8RNqvAz2dnBEtkeV2 khwXVe/PL+aBDokLr8gGcCYfJosYF+1zg1MUgugB2k8JrLibZDQjbfJKiowM03bp GXPDhJRyEIE8voy4dqBEvAt5pzbptkktaNIMC95m5oXyiFDf/thEAkJqKuKjYZg= =aajv -----END PGP SIGNATURE-----
On Wed, Apr 6, 2011 at 6:52 PM, Jeff Law <law@redhat.com> wrote: > What about when we have a PHI, which we eliminate by inserting insns on > edges and those insns actually form a loop? You can see an example of > this in PR48389. AFAIU the patch doesn't change behavior for the GIMPLE CFG. It only affects RTL. Ciao! Steven
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/06/11 12:01, Steven Bosscher wrote: > On Wed, Apr 6, 2011 at 6:52 PM, Jeff Law <law@redhat.com> wrote: >> What about when we have a PHI, which we eliminate by inserting insns on >> edges and those insns actually form a loop? You can see an example of >> this in PR48389. > > AFAIU the patch doesn't change behavior for the GIMPLE CFG. It only affects RTL. But the elimination of the PHI results in creating RTL that is inserted on a CFG edge. jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJNnK3cAAoJEBRtltQi2kC7WnkH/j3hIBoW9htzfDJSXHYtpyGG PVYIjWQnml/+PlHH06faECfnZtNlqR/Tcin4mbtnoJnlpvP3xTN2ioL3ehgWerq8 015DhflYYkhrsPTY4DkkirY4jv4hTvjgq1no2X3BMKAVD8EkYoGlOPLhK/XqnBCs gtRJhYbo5lJ16vh9qrVhAdMNCF/wvw13JHhXdSHcVC++7qFoiysFko/7hpggqES1 edonxv0o6m52/EitbGMXUcyJvPyX4DT54Pp+KjBU9VCIuv6SldUTBzJLoi+Vcrpo skpfCMgG7uTd6aEb31SDL5/sduzIP1Nbn21GZXQme0kLLK+sIXhGdi6FlYuAcNM= =mMZB -----END PGP SIGNATURE-----
On Wed, Apr 6, 2011 at 8:15 PM, Jeff Law <law@redhat.com> wrote: >> AFAIU the patch doesn't change behavior for the GIMPLE CFG. It only affects RTL. > But the elimination of the PHI results in creating RTL that is inserted > on a CFG edge. Yes, but gimple_expand_cfg() calls find_many_sub_basic_blocks(), and that should be enough, no?? /me goes back to trying to understand this code :-) Ciao! Steven
On Wed, Apr 6, 2011 at 8:37 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote: > On Wed, Apr 6, 2011 at 8:15 PM, Jeff Law <law@redhat.com> wrote: > >>> AFAIU the patch doesn't change behavior for the GIMPLE CFG. It only affects RTL. >> But the elimination of the PHI results in creating RTL that is inserted >> on a CFG edge. > > Yes, but gimple_expand_cfg() calls find_many_sub_basic_blocks(), and > that should be enough, no?? > > /me goes back to trying to understand this code :-) Could you please add an explanation to the PR about how that PHI results in a loop on an edge? My fantasy is not big enough to visualize any case where that can happen! Ciao! Steven
> What about when we have a PHI, which we eliminate by inserting insns on > edges and those insns actually form a loop? You can see an example of > this in PR48389. Interesting case, thanks. I think it's simply a matter of defining the API: does commit_edge_insertions need to fix up the CFG or is it the responsibility of the caller? Given that it cannot do so in CFG layout mode, I think that it makes sense not to do it in CFG RTL mode either. My testing apparently shows that only of one of the callers needs to be adjusted. Note that gimple_expand_cfg already knows that it must fix up the CFG, this won't change anything for it (and it doesn't call commit_edge_insertions).
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/06/11 12:37, Steven Bosscher wrote: > On Wed, Apr 6, 2011 at 8:15 PM, Jeff Law <law@redhat.com> wrote: > >>> AFAIU the patch doesn't change behavior for the GIMPLE CFG. It only affects RTL. >> But the elimination of the PHI results in creating RTL that is inserted >> on a CFG edge. > > Yes, but gimple_expand_cfg() calls find_many_sub_basic_blocks(), and > that should be enough, no?? Maybe -- as I originally mentioned, I really don't know this code at all. Ironically, the PR I referenced aborts in find_many_sub_basic_blocks code because the control flow insn insn inserted on the edge doesn't gets its JUMP_LABEL initialized. jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJNnLenAAoJEBRtltQi2kC7B/AIAJAT7Ur5ipNsv5oP9JDlXShM cEQ9ucPHOl+R6wH21bL4Zv2heUT/kwuk0HUSwafkWvPivZCT10Ak1DJRi89mMBc9 CmBwPnuBYMnUaJTXBTfeXIaUsCBiUhghf2t5b5a3/lF38T488Z9Rtff3E0/FemC6 XxgKWVFLOuwCGWfO4tHr3I9U0lHp4pHkjRlfkDurygS5aq91WYsBAL7M6ZhyNxme rSBFiEkiCmPvH0JEgbUkRidQrRdAiKETZ8ajKIE7N7w8APl1MpaYJ5BbAHXUwyLO CyKRmUlMBHE4gCKNNnKWB6D5UhYFRFb1S6jgnI956MPuqkt4r/aDo1TD3cdLM0A= =zocz -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/06/11 12:39, Steven Bosscher wrote: > On Wed, Apr 6, 2011 at 8:37 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote: >> On Wed, Apr 6, 2011 at 8:15 PM, Jeff Law <law@redhat.com> wrote: >> >>>> AFAIU the patch doesn't change behavior for the GIMPLE CFG. It only affects RTL. >>> But the elimination of the PHI results in creating RTL that is inserted >>> on a CFG edge. >> >> Yes, but gimple_expand_cfg() calls find_many_sub_basic_blocks(), and >> that should be enough, no?? >> >> /me goes back to trying to understand this code :-) > > Could you please add an explanation to the PR about how that PHI > results in a loop on an edge? My fantasy is not big enough to > visualize any case where that can happen! Presumably it's the vector initialization. THere's a fair amount of backend goop that comes into play. Peek at expand_set_or_movmem_via_loop. jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJNnL/yAAoJEBRtltQi2kC7LfoH/jWh+8b77bjuLQnVyBrB8Naj UWOPmPQHzs6DT1THXz8ef+pS3Bvuhbm+RxnHWhUTJQ9qBYwCf2oXzZDgytadfGo7 PKEtRpJTe4z7dwTGvp6UUX16TEI29OLHeNyyiDdEQ2ryCHJaSYB1MC8PEANilaHW uYAvTOkLbk6ORjx06pleVGy0IJW1UwLeQoJ2ggZvvmPZz8NghAWuvdfVkoX409wo vjOJ/EnDI603zKazh8yLI0c1K+jZNjnqqlxM8kC3GSt1lJt0LSO5vKW47H0E4zf0 rXhfj5WTiNJ0b0QjGGreIbKjUT8HLPjTJe3gurqgS25R2NtWCv9zxkYFu7sCGPo= =2tG9 -----END PGP SIGNATURE-----
> * basic-block.h (force_nonfallthru): Move to... > * cfghooks.h (struct cfg_hooks): Add force_nonfallthru hook. > (force_nonfallthru): ...here. > * cfghooks.c (force_nonfallthru): New function. > * cfgrtl.c (force_nonfallthru): Rename into... > (rtl_force_nonfallthru): ...this. > (commit_one_edge_insertion): Do not set AUX field. > (commit_edge_insertions): Do not discover new basic blocks. > (rtl_cfg_hooks): Add rtl_force_nonfallthru. > (cfg_layout_rtl_cfg_hooks): Likewise. > * function.c (thread_prologue_and_epilogue_insns): Remove bogus > ATTRIBUTE_UNUSED. Discover new basic blocks in the prologue insns. > * tree-cfg.c (gimple_cfg_hooks): Add NULL for force_nonfallthru. Installed after bootstrapping/regtesting on SPARC/Solaris, SPARC64/Solaris, IA-64/Linux and re-bootstrapping/regtesting on x86-64/Linux.
Index: cfghooks.c =================================================================== --- cfghooks.c (revision 171942) +++ cfghooks.c (working copy) @@ -398,8 +398,7 @@ redirect_edge_and_branch_force (edge e, rescan_loop_exit (e, false, true); ret = cfg_hooks->redirect_edge_and_branch_force (e, dest); - if (ret != NULL - && dom_info_available_p (CDI_DOMINATORS)) + if (ret != NULL && dom_info_available_p (CDI_DOMINATORS)) set_immediate_dominator (CDI_DOMINATORS, ret, src); if (current_loops != NULL) @@ -820,6 +819,8 @@ make_forwarder_block (basic_block bb, bo return fallthru; } +/* Try to make the edge fallthru. */ + void tidy_fallthru_edge (edge e) { @@ -874,6 +875,42 @@ tidy_fallthru_edges (void) } } +/* Edge E is assumed to be fallthru edge. Emit needed jump instruction + (and possibly create new basic block) to make edge non-fallthru. + Return newly created BB or NULL if none. */ + +basic_block +force_nonfallthru (edge e) +{ + basic_block ret, src = e->src, dest = e->dest; + struct loop *loop; + + if (!cfg_hooks->force_nonfallthru) + internal_error ("%s does not support force_nonfallthru", + cfg_hooks->name); + + if (current_loops != NULL) + rescan_loop_exit (e, false, true); + + ret = cfg_hooks->force_nonfallthru (e); + if (ret != NULL && dom_info_available_p (CDI_DOMINATORS)) + set_immediate_dominator (CDI_DOMINATORS, ret, src); + + if (current_loops != NULL) + { + if (ret != NULL) + { + loop = find_common_loop (single_pred (ret)->loop_father, + single_succ (ret)->loop_father); + add_bb_to_loop (ret, loop); + } + else if (find_edge (src, dest) == e) + rescan_loop_exit (e, true, false); + } + + return ret; +} + /* Returns true if we can duplicate basic block BB. */ bool Index: cfghooks.h =================================================================== --- cfghooks.h (revision 171942) +++ cfghooks.h (working copy) @@ -85,9 +85,12 @@ struct cfg_hooks basic_block (*split_edge) (edge); void (*make_forwarder_block) (edge); - /* Tries to make the edge fallthru. */ + /* Try to make the edge fallthru. */ void (*tidy_fallthru_edge) (edge); + /* Make the edge non-fallthru. */ + basic_block (*force_nonfallthru) (edge); + /* Say whether a block ends with a call, possibly followed by some other code that must stay with the call. */ bool (*block_ends_with_call_p) (basic_block); @@ -156,6 +159,7 @@ extern bool can_merge_blocks_p (basic_bl extern void merge_blocks (basic_block, basic_block); extern edge make_forwarder_block (basic_block, bool (*)(edge), void (*) (basic_block)); +extern basic_block force_nonfallthru (edge); extern void tidy_fallthru_edge (edge); extern void tidy_fallthru_edges (void); extern void predict_edge (edge e, enum br_predictor predictor, int probability); Index: function.c =================================================================== --- function.c (revision 171942) +++ function.c (working copy) @@ -5282,8 +5282,7 @@ thread_prologue_and_epilogue_insns (void { bool inserted; rtx seq ATTRIBUTE_UNUSED, epilogue_end ATTRIBUTE_UNUSED; - edge entry_edge ATTRIBUTE_UNUSED; - edge e; + edge entry_edge, e; edge_iterator ei; rtl_profile_for_bb (ENTRY_BLOCK_PTR); @@ -5315,10 +5314,6 @@ thread_prologue_and_epilogue_insns (void record_insns (seq, NULL, &prologue_insn_hash); set_insn_locators (seq, prologue_locator); - /* This relies on the fact that committing the edge insertion - will look for basic blocks within the inserted instructions, - which in turn relies on the fact that we are not in CFG - layout mode here. */ insert_insn_on_edge (seq, entry_edge); inserted = true; #endif @@ -5541,13 +5536,23 @@ thread_prologue_and_epilogue_insns (void cur_bb->aux = cur_bb->next_bb; cfg_layout_finalize (); } + epilogue_done: default_rtl_profile (); if (inserted) { + sbitmap blocks; + commit_edge_insertions (); + /* Look for basic blocks within the prologue insns. */ + blocks = sbitmap_alloc (last_basic_block); + sbitmap_zero (blocks); + SET_BIT (blocks, entry_edge->dest->index); + find_many_sub_basic_blocks (blocks); + sbitmap_free (blocks); + /* The epilogue insns we inserted may cause the exit edge to no longer be fallthru. */ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) Index: basic-block.h =================================================================== --- basic-block.h (revision 171942) +++ basic-block.h (working copy) @@ -794,7 +794,6 @@ extern void flow_nodes_print (const char extern void flow_edge_list_print (const char *, const edge *, int, FILE *); /* In cfgrtl.c */ -extern basic_block force_nonfallthru (edge); extern rtx block_label (basic_block); extern bool purge_all_dead_edges (void); extern bool purge_dead_edges (basic_block); Index: tree-cfg.c =================================================================== --- tree-cfg.c (revision 171942) +++ tree-cfg.c (working copy) @@ -7135,6 +7135,7 @@ struct cfg_hooks gimple_cfg_hooks = { gimple_split_edge, /* split_edge */ gimple_make_forwarder_block, /* make_forward_block */ NULL, /* tidy_fallthru_edge */ + NULL, /* force_nonfallthru */ gimple_block_ends_with_call_p,/* block_ends_with_call_p */ gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */ gimple_flow_call_edges_add, /* flow_call_edges_add */ Index: cfgrtl.c =================================================================== --- cfgrtl.c (revision 171942) +++ cfgrtl.c (working copy) @@ -1279,8 +1279,8 @@ force_nonfallthru_and_redirect (edge e, (and possibly create new basic block) to make edge non-fallthru. Return newly created BB or NULL if none. */ -basic_block -force_nonfallthru (edge e) +static basic_block +rtl_force_nonfallthru (edge e) { return force_nonfallthru_and_redirect (e, e->dest); } @@ -1566,10 +1566,6 @@ commit_one_edge_insertion (edge e) } else gcc_assert (!JUMP_P (last)); - - /* Mark the basic block for find_many_sub_basic_blocks. */ - if (current_ir_type () != IR_RTL_CFGLAYOUT) - bb->aux = &bb->aux; } /* Update the CFG for all queued instructions. */ @@ -1578,8 +1574,6 @@ void commit_edge_insertions (void) { basic_block bb; - sbitmap blocks; - bool changed = false; #ifdef ENABLE_CHECKING verify_flow_info (); @@ -1592,35 +1586,8 @@ commit_edge_insertions (void) FOR_EACH_EDGE (e, ei, bb->succs) if (e->insns.r) - { - changed = true; - commit_one_edge_insertion (e); - } + commit_one_edge_insertion (e); } - - if (!changed) - return; - - /* In the old rtl CFG API, it was OK to insert control flow on an - edge, apparently? In cfglayout mode, this will *not* work, and - the caller is responsible for making sure that control flow is - valid at all times. */ - if (current_ir_type () == IR_RTL_CFGLAYOUT) - return; - - blocks = sbitmap_alloc (last_basic_block); - sbitmap_zero (blocks); - FOR_EACH_BB (bb) - if (bb->aux) - { - SET_BIT (blocks, bb->index); - /* Check for forgotten bb->aux values before commit_edge_insertions - call. */ - gcc_assert (bb->aux == &bb->aux); - bb->aux = NULL; - } - find_many_sub_basic_blocks (blocks); - sbitmap_free (blocks); } @@ -3233,6 +3200,7 @@ struct cfg_hooks rtl_cfg_hooks = { rtl_split_edge, rtl_make_forwarder_block, rtl_tidy_fallthru_edge, + rtl_force_nonfallthru, rtl_block_ends_with_call_p, rtl_block_ends_with_condjump_p, rtl_flow_call_edges_add, @@ -3276,7 +3244,8 @@ struct cfg_hooks cfg_layout_rtl_cfg_hook cfg_layout_duplicate_bb, cfg_layout_split_edge, rtl_make_forwarder_block, - NULL, + NULL, /* tidy_fallthru_edge */ + rtl_force_nonfallthru, rtl_block_ends_with_call_p, rtl_block_ends_with_condjump_p, rtl_flow_call_edges_add,
commit_edge_insertions contains this kludge: /* In the old rtl CFG API, it was OK to insert control flow on an edge, apparently? In cfglayout mode, this will *not* work, and the caller is responsible for making sure that control flow is valid at all times. */ if (current_ir_type () == IR_RTL_CFGLAYOUT) return; blocks = sbitmap_alloc (last_basic_block); sbitmap_zero (blocks); FOR_EACH_BB (bb) if (bb->aux) { SET_BIT (blocks, bb->index); /* Check for forgotten bb->aux values before commit_edge_insertions call. */ gcc_assert (bb->aux == &bb->aux); bb->aux = NULL; } find_many_sub_basic_blocks (blocks); sbitmap_free (blocks); At least on x86/x86-64, there is apparently only one case where control flow insns are inserted on edges: when the prologue is inserted on the entry edge. Once this is accounted for, the above kludge can be removed, provided that the force_nonfallthru RTL routine is enhanced to preserve the loop nest structure. The result is the attached patch, bootstrapped/regtested on x86 and x86-64. I'll be testing it on IA-64 and SPARC over the next few days if there is an agreement that this is a progress. * basic-block.h (force_nonfallthru): Move to... * cfghooks.h (struct cfg_hooks): Add force_nonfallthru hook. (force_nonfallthru): ...here. * cfghooks.c (force_nonfallthru): New function. * cfgrtl.c (force_nonfallthru): Rename into... (rtl_force_nonfallthru): ...this. (commit_one_edge_insertion): Do not set AUX field. (commit_edge_insertions): Do not discover new basic blocks. (rtl_cfg_hooks): Add rtl_force_nonfallthru. (cfg_layout_rtl_cfg_hooks): Likewise. * function.c (thread_prologue_and_epilogue_insns): Remove bogus ATTRIBUTE_UNUSED. Discover new basic blocks in the prologue insns. * tree-cfg.c (gimple_cfg_hooks): Add NULL for force_nonfallthru.