Patchwork New switch optimization pass (PR tree-optimization/54742)

login
register
mail settings
Submitter Steve Ellcey
Date May 15, 2013, 6:28 p.m.
Message ID <1368642493.16206.34.camel@ubuntu-sellcey>
Download mbox | patch
Permalink /patch/244151/
State New
Headers show

Comments

Steve Ellcey - May 15, 2013, 6:28 p.m.
On Wed, 2013-05-15 at 10:44 +0200, Richard Biener wrote:

> Indeed.  I'd rather have a flag to the SESE copier that tells it the region
> is SEME and in that case make it not update dominators but leave that
> to the caller (which means, recompute them).  It seems the code already
> handles ME regions if the other exits are "not important" (we don't have
> to insert/update PHI nodes in those exit blocks), so it may be that there
> are even more constraints on those unimportant exits due to the
> iterative dominator update - I think that the entry block of the region
> needs to dominate all exit destinations, otherwise get_dominated_by_region
> is not working correctly.  In your case one exit is a back-edge?  We should
> be able to add checking to the code to verify unimportant edges are
> unimportant "enough".
> 
> I'm sure Zdenek knows the limitations best.
> 
> Richard.

Here is a patch that adds a flag to gimple_duplicate_sese_region to tell
it whether or not to update the dominator information.  I had to add the
same flag to copy_bbs to make it all work.  How does this look?  I
tested it with a bootstrap and test on x86 (with my optimization
enabled) and got no regressions.

2013-05-15  Steve Ellcey  <sellcey@imgtec.com>

	* cfghooks.c (copy_bbs): Add update_dominance argument.
	* cfghooks.h (copy_bbs): Update prototype.
	* tree-cfg.c (gimple_duplicate_sese_region):
	Add update_dominance argument.
	* tree-flow.h (gimple_duplicate_sese_region): Update prototype.
	* tree-ssa-loop-ch.c (copy_loop_headers): Update
	gimple_duplicate_sese_region call.
	* tree-vect-loop-manip.c (slpeel_tree_duplicate_loop_to_edge_cfg):
	Update copy_bbs call.
	* cfgloopmanip.c (duplicate_loop_to_header_edge): Ditto.
	* trans-mem.c (ipa_uninstrument_transaction): Ditto.
Jeff Law - May 16, 2013, 3:38 a.m.
On 05/15/2013 12:28 PM, Steve Ellcey wrote:
> Here is a patch that adds a flag to gimple_duplicate_sese_region to tell
> it whether or not to update the dominator information.  I had to add the
> same flag to copy_bbs to make it all work.  How does this look?  I
> tested it with a bootstrap and test on x86 (with my optimization
> enabled) and got no regressions.
>
> 2013-05-15  Steve Ellcey  <sellcey@imgtec.com>
>
> 	* cfghooks.c (copy_bbs): Add update_dominance argument.
> 	* cfghooks.h (copy_bbs): Update prototype.
> 	* tree-cfg.c (gimple_duplicate_sese_region):
> 	Add update_dominance argument.
> 	* tree-flow.h (gimple_duplicate_sese_region): Update prototype.
> 	* tree-ssa-loop-ch.c (copy_loop_headers): Update
> 	gimple_duplicate_sese_region call.
> 	* tree-vect-loop-manip.c (slpeel_tree_duplicate_loop_to_edge_cfg):
> 	Update copy_bbs call.
> 	* cfgloopmanip.c (duplicate_loop_to_header_edge): Ditto.
> 	* trans-mem.c (ipa_uninstrument_transaction): Ditto.
So I'd change gimple_duplicate_sese_region to gimple_duplicate_seme 
region per comments from others.

Where you document UPDATE_DOMINANCE, I'd add something like: When 
UPDATE_DOMINANCE is true, it is assumed that duplicating the region (or 
copying the blocks for copy_bbs) may change the dominator tree in ways 
that are not suitable for an incremental update and the caller is 
responsible for destroying and recomputing the dominator tree.

Hmm, not terribly happy with that wording, but that gives you an idea of 
what I'm after.  When would someone set UPDATE_DOMINANCE to true and 
what are their responsibilities when they do so.

Approved with the name change and a better comment for UPDATE_DOMINANCE.

Jeff
Richard Guenther - May 16, 2013, 8:58 a.m.
On Thu, May 16, 2013 at 5:38 AM, Jeff Law <law@redhat.com> wrote:
> On 05/15/2013 12:28 PM, Steve Ellcey wrote:
>>
>> Here is a patch that adds a flag to gimple_duplicate_sese_region to tell
>> it whether or not to update the dominator information.  I had to add the
>> same flag to copy_bbs to make it all work.  How does this look?  I
>> tested it with a bootstrap and test on x86 (with my optimization
>> enabled) and got no regressions.
>>
>> 2013-05-15  Steve Ellcey  <sellcey@imgtec.com>
>>
>>         * cfghooks.c (copy_bbs): Add update_dominance argument.
>>         * cfghooks.h (copy_bbs): Update prototype.
>>         * tree-cfg.c (gimple_duplicate_sese_region):
>>         Add update_dominance argument.
>>         * tree-flow.h (gimple_duplicate_sese_region): Update prototype.
>>         * tree-ssa-loop-ch.c (copy_loop_headers): Update
>>         gimple_duplicate_sese_region call.
>>         * tree-vect-loop-manip.c (slpeel_tree_duplicate_loop_to_edge_cfg):
>>         Update copy_bbs call.
>>         * cfgloopmanip.c (duplicate_loop_to_header_edge): Ditto.
>>         * trans-mem.c (ipa_uninstrument_transaction): Ditto.
>
> So I'd change gimple_duplicate_sese_region to gimple_duplicate_seme region
> per comments from others.
>
> Where you document UPDATE_DOMINANCE, I'd add something like: When
> UPDATE_DOMINANCE is true, it is assumed that duplicating the region (or
> copying the blocks for copy_bbs) may change the dominator tree in ways that
> are not suitable for an incremental update and the caller is responsible for
> destroying and recomputing the dominator tree.
>
> Hmm, not terribly happy with that wording, but that gives you an idea of
> what I'm after.  When would someone set UPDATE_DOMINANCE to true and what
> are their responsibilities when they do so.
>
> Approved with the name change and a better comment for UPDATE_DOMINANCE.

Btw, the function does _not_ handle arbitrary SEME regions - it only handles
a single exit correctly and assumes no (SSA) data flows across the others.
So I'd rather not rename it.

Richard.

> Jeff
>
Steve Ellcey - May 16, 2013, 5:10 p.m.
On Thu, 2013-05-16 at 10:58 +0200, Richard Biener wrote:

> >
> > Hmm, not terribly happy with that wording, but that gives you an idea of
> > what I'm after.  When would someone set UPDATE_DOMINANCE to true and what
> > are their responsibilities when they do so.
> >
> > Approved with the name change and a better comment for UPDATE_DOMINANCE.
> 
> Btw, the function does _not_ handle arbitrary SEME regions - it only handles
> a single exit correctly and assumes no (SSA) data flows across the others.
> So I'd rather not rename it.
> 
> Richard.
> 
> > Jeff

I went ahead and checked in the change with the comment updates that
Jeff wanted but left the name of the function as is.

Steve Ellcey
sellcey@imgtec.com
Jeff Law - May 16, 2013, 5:35 p.m.
On 05/16/2013 11:10 AM, Steve Ellcey wrote:
> On Thu, 2013-05-16 at 10:58 +0200, Richard Biener wrote:
>
>>>
>>> Hmm, not terribly happy with that wording, but that gives you an idea of
>>> what I'm after.  When would someone set UPDATE_DOMINANCE to true and what
>>> are their responsibilities when they do so.
>>>
>>> Approved with the name change and a better comment for UPDATE_DOMINANCE.
>>
>> Btw, the function does _not_ handle arbitrary SEME regions - it only handles
>> a single exit correctly and assumes no (SSA) data flows across the others.
>> So I'd rather not rename it.
>>
>> Richard.
>>
>>> Jeff
>
> I went ahead and checked in the change with the comment updates that
> Jeff wanted but left the name of the function as is.
Ok.  Thanks.

jeff

Patch

diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
index 22b962b..18af38b 100644
--- a/gcc/cfghooks.c
+++ b/gcc/cfghooks.c
@@ -1287,7 +1287,8 @@  end:
    function assigns bbs into loops (copy of basic block bb is assigned to
    bb->loop_father->copy loop, so this must be set up correctly in advance)
    and updates dominators locally (LOOPS structure that contains the information
-   about dominators is passed to enable this).
+   about dominators is passed to enable this) if update_dominance is set to
+   true.
 
    BASE is the superloop to that basic block belongs; if its header or latch
    is copied, we do not set the new blocks as header or latch.
@@ -1301,7 +1302,7 @@  end:
 void
 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
 	  edge *edges, unsigned num_edges, edge *new_edges,
-	  struct loop *base, basic_block after)
+	  struct loop *base, basic_block after, bool update_dominance)
 {
   unsigned i, j;
   basic_block bb, new_bb, dom_bb;
@@ -1327,16 +1328,19 @@  copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
     }
 
   /* Set dominators.  */
-  for (i = 0; i < n; i++)
+  if (update_dominance)
     {
-      bb = bbs[i];
-      new_bb = new_bbs[i];
-
-      dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
-      if (dom_bb->flags & BB_DUPLICATED)
+      for (i = 0; i < n; i++)
 	{
-	  dom_bb = get_bb_copy (dom_bb);
-	  set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
+	  bb = bbs[i];
+	  new_bb = new_bbs[i];
+
+	  dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+	  if (dom_bb->flags & BB_DUPLICATED)
+	    {
+	      dom_bb = get_bb_copy (dom_bb);
+	      set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
+	    }
 	}
     }
 
diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h
index bff0a0c..ec595a5 100644
--- a/gcc/cfghooks.h
+++ b/gcc/cfghooks.h
@@ -201,7 +201,7 @@  extern void lv_add_condition_to_bb (basic_block, basic_block, basic_block,
 extern bool can_copy_bbs_p (basic_block *, unsigned);
 extern void copy_bbs (basic_block *, unsigned, basic_block *,
 		      edge *, unsigned, edge *, struct loop *,
-		      basic_block);
+		      basic_block, bool);
 
 void account_profile_record (struct profile_record *, int);
 
diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 9581677..bc87755 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -1300,7 +1300,7 @@  duplicate_loop_to_header_edge (struct loop *loop, edge e,
 
       /* Copy bbs.  */
       copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
-		place_after);
+		place_after, true);
       place_after = new_spec_edges[SE_LATCH]->src;
 
       if (flags & DLTHE_RECORD_COPY_NUMBER)
diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c
index 5cb8286..c66278c 100644
--- a/gcc/trans-mem.c
+++ b/gcc/trans-mem.c
@@ -3978,7 +3978,8 @@  ipa_uninstrument_transaction (struct tm_region *region,
   int n = queue.length ();
   basic_block *new_bbs = XNEWVEC (basic_block, n);
 
-  copy_bbs (queue.address (), n, new_bbs, NULL, 0, NULL, NULL, transaction_bb);
+  copy_bbs (queue.address (), n, new_bbs, NULL, 0, NULL, NULL, transaction_bb,
+	    true);
   edge e = make_edge (transaction_bb, new_bbs[0], EDGE_TM_UNINSTRUMENTED);
   add_phi_args_after_copy (new_bbs, n, e);
 
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index a08a737..d492903 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -5686,16 +5686,17 @@  add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
    inside region is live over the other exit edges of the region.  All entry
    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
    to the duplicate of the region.  Dominance and loop information is
-   updated, but not the SSA web.  The new basic blocks are stored to
-   REGION_COPY in the same order as they had in REGION, provided that
-   REGION_COPY is not NULL.
+   updated if update_dominance is true, but not the SSA web.  The new basic
+   blocks are stored to REGION_COPY in the same order as they had in REGION,
+   provided that REGION_COPY is not NULL.
    The function returns false if it is unable to copy the region,
    true otherwise.  */
 
 bool
 gimple_duplicate_sese_region (edge entry, edge exit,
 			    basic_block *region, unsigned n_region,
-			    basic_block *region_copy)
+			    basic_block *region_copy,
+			    bool update_dominance)
 {
   unsigned i;
   bool free_region_copy = false, copying_header = false;
@@ -5749,12 +5750,15 @@  gimple_duplicate_sese_region (edge entry, edge exit,
       free_region_copy = true;
     }
 
-  /* Record blocks outside the region that are dominated by something
-     inside.  */
-  doms.create (0);
   initialize_original_copy_tables ();
 
-  doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
+  /* Record blocks outside the region that are dominated by something
+     inside.  */
+  if (update_dominance)
+    {
+      doms.create (0);
+      doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
+    }
 
   if (entry->dest->count)
     {
@@ -5778,7 +5782,7 @@  gimple_duplicate_sese_region (edge entry, edge exit,
     }
 
   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
-	    split_edge_bb_loc (entry));
+	    split_edge_bb_loc (entry), update_dominance);
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
@@ -5809,10 +5813,13 @@  gimple_duplicate_sese_region (edge entry, edge exit,
      for entry block and its copy.  Anything that is outside of the
      region, but was dominated by something inside needs recounting as
      well.  */
-  set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
-  doms.safe_push (get_bb_original (entry->dest));
-  iterate_fix_dominators (CDI_DOMINATORS, doms, false);
-  doms.release ();
+  if (update_dominance)
+    {
+      set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
+      doms.safe_push (get_bb_original (entry->dest));
+      iterate_fix_dominators (CDI_DOMINATORS, doms, false);
+      doms.release ();
+    }
 
   /* Add the other PHI node arguments.  */
   add_phi_args_after_copy (region_copy, n_region, NULL);
@@ -5944,7 +5951,7 @@  gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNU
     }
 
   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
-	    split_edge_bb_loc (exit));
+	    split_edge_bb_loc (exit), true);
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 01fe363..24fcfbf 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -395,7 +395,7 @@  extern void verify_gimple_in_cfg (struct function *);
 extern tree gimple_block_label (basic_block);
 extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
 extern bool gimple_duplicate_sese_region (edge, edge, basic_block *, unsigned,
-					basic_block *);
+					basic_block *, bool);
 extern bool gimple_duplicate_sese_tail (edge, edge, basic_block *, unsigned,
 				      basic_block *);
 extern void gather_blocks_in_sese_region (basic_block entry, basic_block exit,
diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c
index a1d0299..ff17c7e 100644
--- a/gcc/tree-ssa-loop-ch.c
+++ b/gcc/tree-ssa-loop-ch.c
@@ -197,7 +197,8 @@  copy_loop_headers (void)
       entry = loop_preheader_edge (loop);
 
       propagate_threaded_block_debug_into (exit->dest, entry->dest);
-      if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
+      if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
+					 true))
 	{
 	  fprintf (dump_file, "Duplication failed.\n");
 	  continue;
diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c
index bff5c22..d1a1f06 100644
--- a/gcc/tree-vect-loop-manip.c
+++ b/gcc/tree-vect-loop-manip.c
@@ -735,7 +735,7 @@  slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
 
   copy_bbs (bbs, loop->num_nodes + 1, new_bbs,
 	    &exit, 1, &new_exit, NULL,
-	    e->src);
+	    e->src, true);
   basic_block new_preheader = new_bbs[loop->num_nodes];
 
   add_phi_args_after_copy (new_bbs, loop->num_nodes + 1, NULL);