[RFC] Remove kludge in commit_edge_insertions

[RFC] Remove kludge in commit_edge_insertions

[Eric Botcazou]

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

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.


-- 
Eric Botcazou

[-- Attachment #2: p.diff --]
[-- Type: text/x-diff, Size: 7962 bytes --]

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);
 }
 \f
 
@@ -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,

Re: [RFC] Remove kludge in commit_edge_insertions

[Jeff Law]

-----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-----

Re: [RFC] Remove kludge in commit_edge_insertions

[Steven Bosscher]

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

Re: [RFC] Remove kludge in commit_edge_insertions

[Jeff Law]

-----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-----

Re: [RFC] Remove kludge in commit_edge_insertions

[Steven Bosscher]

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

Re: [RFC] Remove kludge in commit_edge_insertions

[Steven Bosscher]

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

Re: [RFC] Remove kludge in commit_edge_insertions

[Jeff Law]

-----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-----

Re: [RFC] Remove kludge in commit_edge_insertions

[Jeff Law]

-----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-----

Re: [RFC] Remove kludge in commit_edge_insertions

[Eric Botcazou]

> 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).

-- 
Eric Botcazou

Re: [RFC] Remove kludge in commit_edge_insertions

[Eric Botcazou]

> 	* 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.

-- 
Eric Botcazou