This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH GCC][01/13]Introduce internal function IFN_LOOP_DIST_ALIAS


On Wed, Jun 28, 2017 at 8:29 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Jun 27, 2017 at 6:46 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Tue, Jun 27, 2017 at 3:59 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On June 27, 2017 4:27:17 PM GMT+02:00, "Bin.Cheng" <amker.cheng@gmail.com> wrote:
>>>>On Tue, Jun 27, 2017 at 1:58 PM, Richard Biener
>>>><richard.guenther@gmail.com> wrote:
>>>>> On Fri, Jun 23, 2017 at 12:10 PM, Bin.Cheng <amker.cheng@gmail.com>
>>>>wrote:
>>>>>> On Mon, Jun 12, 2017 at 6:02 PM, Bin Cheng <Bin.Cheng@arm.com>
>>>>wrote:
>>>>>>> Hi,
>>>>>>> I was asked by upstream to split the loop distribution patch into
>>>>small ones.
>>>>>>> It is hard because data structure and algorithm are closely coupled
>>>>together.
>>>>>>> Anyway, this is the patch series with smaller patches.  Basically I
>>>>tried to
>>>>>>> separate data structure and bug-fix changes apart with one as the
>>>>main patch.
>>>>>>> Note I only made necessary code refactoring in order to separate
>>>>patch, apart
>>>>>>> from that, there is no change against the last version.
>>>>>>>
>>>>>>> This is the first patch introducing new internal function
>>>>IFN_LOOP_DIST_ALIAS.
>>>>>>> GCC will distribute loops under condition of this function call.
>>>>>>>
>>>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>>> Hi,
>>>>>> I need to update this patch fixing an issue in
>>>>>> vect_loop_dist_alias_call.  The previous patch fails to find some
>>>>>> IFN_LOOP_DIST_ALIAS calls.
>>>>>>
>>>>>> Bootstrap and test in series.  Is it OK?
>>>>>
>>>>> So I wonder if we really need to track ldist_alias_id or if we can do
>>>>sth
>>>>Yes, it is needed because otherwise we probably falsely trying to
>>>>search for IFN_LOOP_DIST_ALIAS for a normal (not from distribution)
>>>>loop.
>>>>
>>>>> more "general", like tracking a copy_of or origin and then directly
>>>>> go to nearest_common_dominator (loop->header, copy_of->header)
>>>>> to find the controlling condition?
>>>>I tend to not record any pointer in loop structure, it can easily go
>>>>dangling for a across passes data structure.
>>>
>>> I didn't mean to record a pointer, just rename your field and make it more general.  The common dominator thing shod still work, no?
>> I might not be following.  If we record the original loop->num in the
>> renamed field, nearest_common_dominator can't work because we don't
>> have basic blocks to start the call?  The original loop could be
>> eliminated at several points, for example, instantly after
>> distribution, or folded in vectorizer for other loops distributed from
>> the original loop.
>> BTW, setting the copy_of/origin field in loop_version is not enough
>> for this use case, all generated loops (actually, except the versioned
>> loop) from distribution need to be set.
>
> Of course it would need to be set for all distributed loops.
>
> I'm not sure "loop vanishes" is the case to optimize for though.  If the loop
> is still available then origin->header should work as BB.  If not then can't
> we conclude, for the purpose of IFN_LOOP_DIST_ALIAS, that the whole
> region must be dead?  We still have to identify it of course, but it means
> we can fold stray IFN_LOOP_DIST_ALIAS calls left over after vectorization
> to whatever we like?
>
>>>
>>> As far as memory usage
>>>>is concerned.  I actually don't need a whole integer to record the
>>>>loop num.  I can simply restrict number of distributions in one
>>>>function to at most 256, and record such id in a char field in struct
>>>>loop?  Does this sounds better?
>>>
>>> As said, tracking loop origin sounds useful anyway so I'd rather add and use that somehow.
>> To be honest, I don't know.  the current field works like a unique
>> index of distribution operation.  The original loop could be destroyed
>> at different points thus no longer exists, this makes the recorded
>> copy_of/origin less meaningful?
>
> I think we talked about prologue and epilogue loops to be easier identifiable
> as so (and as to what "main" loop).  So lets say we have one "origin" field
> and accompaning flags "origin_is_loop_dist_alias_version",
> "origin_is_main_loop_of_prologue", etc.?  I can't think of the case where
> origin would be two things at the same time (you can always walk up
> the origin tree).
Hi,
Here is the updated patch working in this way.  There is still one
problem with this method.  Considering one distributed loop is
if-converted later, the orig loop for if-converted distributed loop is
different.  Though we can update orig_loop_num, it's inaccurate and
one consequence is we need to walk up dominance tree till entry_block.
Note if orig_loop_num is not shared, we can stop once basic block goes
beyond outer loop.
I didn't introduce flags in this patch, which can be done along with
solving the above problem.

>
> Vanishing origins could also be cleared btw, or we can make the new origin
> the origin of the vanishing origin...
Yes, I did this in distribution patch, so that dominance walking
routine can be simplified.

Bootstrap and test.  Is it OK?

Thanks,
bin

2017-06-27  Bin Cheng  <bin.cheng@arm.com>

* cfgloop.h (struct loop): Add comment.  New field orig_loop_num.
* cfgloopmanip.c (lv_adjust_loop_entry_edge): Comment change.
* internal-fn.c (expand_LOOP_DIST_ALIAS): New function.
* internal-fn.def (LOOP_DIST_ALIAS): New.
* tree-vectorizer.c (fold_loop_vectorized_call): Rename to ...
(fold_loop_internal_call): ... this.
(vect_loop_dist_alias_call): New function.
(set_uid_loop_bbs): Call fold_loop_internal_call.
(vectorize_loops): Fold IFN_LOOP_VECTORIZED and IFN_LOOP_DIST_ALIAS
internal calls.
From 8c3631f383a53653a40bd30c1133ca03f9cc6973 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Wed, 7 Jun 2017 13:04:03 +0100
Subject: [PATCH 01/13] ifn_loop_dist_alias-20170621.txt

---
 gcc/cfgloop.h         | 13 +++++++-
 gcc/cfgloopmanip.c    |  3 +-
 gcc/internal-fn.c     |  8 +++++
 gcc/internal-fn.def   |  1 +
 gcc/tree-vectorizer.c | 89 +++++++++++++++++++++++++++++++++++++++++++++------
 5 files changed, 103 insertions(+), 11 deletions(-)

diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index a8bec1d..e7ffa23 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -114,7 +114,8 @@ struct GTY ((chain_next ("%h.next"))) control_iv {
 
 /* Structure to hold information for each natural loop.  */
 struct GTY ((chain_next ("%h.next"))) loop {
-  /* Index into loops array.  */
+  /* Index into loops array.  Note indices will never be reused after loop
+     is destroyed.  */
   int num;
 
   /* Number of loop insns.  */
@@ -225,6 +226,16 @@ struct GTY ((chain_next ("%h.next"))) loop {
      builtins.  */
   tree simduid;
 
+  /* In loop optimization, it's common to generate loops from the original
+     loop.  This field records the index of the original loop which can be
+     used to track the original loop from newly generated loops.  This can
+     be done by calling function get_loop (cfun, orig_loop_num).  Note the
+     original loop could be destroyed for various reasons thus no longer
+     exists, as a result, function call to get_loop returns NULL pointer.
+     In this case, this field should not be used and needs to be cleared
+     whenever possible.  */
+  int orig_loop_num;
+
   /* Upper bound on number of iterations of a loop.  */
   struct nb_iter_bound *bounds;
 
diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index d764ab9..adb2f65 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -1653,7 +1653,8 @@ force_single_succ_latches (void)
 
   THEN_PROB is the probability of then branch of the condition.
   ELSE_PROB is the probability of else branch. Note that they may be both
-  REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED.  */
+  REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED or
+  IFN_LOOP_DIST_ALIAS.  */
 
 static basic_block
 lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head,
diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c
index 75fe027..96e40cb 100644
--- a/gcc/internal-fn.c
+++ b/gcc/internal-fn.c
@@ -2250,6 +2250,14 @@ expand_LOOP_VECTORIZED (internal_fn, gcall *)
   gcc_unreachable ();
 }
 
+/* This should get folded in tree-vectorizer.c.  */
+
+static void
+expand_LOOP_DIST_ALIAS (internal_fn, gcall *)
+{
+  gcc_unreachable ();
+}
+
 /* Expand MASK_LOAD call STMT using optab OPTAB.  */
 
 static void
diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def
index e162d81..79c19fb 100644
--- a/gcc/internal-fn.def
+++ b/gcc/internal-fn.def
@@ -158,6 +158,7 @@ DEF_INTERNAL_FN (GOMP_SIMD_LAST_LANE, ECF_CONST | ECF_LEAF | ECF_NOTHROW, NULL)
 DEF_INTERNAL_FN (GOMP_SIMD_ORDERED_START, ECF_LEAF | ECF_NOTHROW, NULL)
 DEF_INTERNAL_FN (GOMP_SIMD_ORDERED_END, ECF_LEAF | ECF_NOTHROW, NULL)
 DEF_INTERNAL_FN (LOOP_VECTORIZED, ECF_NOVOPS | ECF_LEAF | ECF_NOTHROW, NULL)
+DEF_INTERNAL_FN (LOOP_DIST_ALIAS, ECF_NOVOPS | ECF_LEAF | ECF_NOTHROW, NULL)
 DEF_INTERNAL_FN (ANNOTATE,  ECF_CONST | ECF_LEAF | ECF_NOTHROW, NULL)
 DEF_INTERNAL_FN (UBSAN_NULL, ECF_LEAF | ECF_NOTHROW, ".R.")
 DEF_INTERNAL_FN (UBSAN_BOUNDS, ECF_LEAF | ECF_NOTHROW, NULL)
diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c
index 0d62c82..33a1f58 100644
--- a/gcc/tree-vectorizer.c
+++ b/gcc/tree-vectorizer.c
@@ -448,11 +448,11 @@ vect_loop_vectorized_call (struct loop *loop)
   return NULL;
 }
 
-/* Fold LOOP_VECTORIZED internal call G to VALUE and
-   update any immediate uses of it's LHS.  */
+/* Fold loop internal call G like IFN_LOOP_VECTORIZED/IFN_LOOP_DIST_ALIAS
+   to VALUE and update any immediate uses of it's LHS.  */
 
 static void
-fold_loop_vectorized_call (gimple *g, tree value)
+fold_loop_internal_call (gimple *g, tree value)
 {
   tree lhs = gimple_call_lhs (g);
   use_operand_p use_p;
@@ -469,6 +469,60 @@ fold_loop_vectorized_call (gimple *g, tree value)
     }
 }
 
+/* If LOOP has been versioned during loop distribution, return the gurading
+   internal call.  */
+
+static gimple *
+vect_loop_dist_alias_call (struct loop *loop)
+{
+  basic_block bb;
+  basic_block entry;
+  struct loop *outer, *orig;
+  gimple_stmt_iterator gsi;
+  gimple *g;
+
+  if (loop->orig_loop_num == 0)
+    return NULL;
+
+  orig = get_loop (cfun, loop->orig_loop_num);
+  if (orig == NULL)
+    {
+      /* The original loop is somehow destroyed.  Clear the information.  */
+      loop->orig_loop_num = 0;
+      return NULL;
+    }
+
+  if (loop != orig)
+    bb = nearest_common_dominator (CDI_DOMINATORS, loop->header, orig->header);
+  else
+    bb = loop_preheader_edge (loop)->src;
+
+  outer = bb->loop_father;
+  entry = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+
+  /* Look upward in dominance tree.  */
+  for (; bb != entry && flow_bb_inside_loop_p (outer, bb);
+       bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+    {
+      g = last_stmt (bb);
+      if (g == NULL || gimple_code (g) != GIMPLE_COND)
+	continue;
+
+      gsi = gsi_for_stmt (g);
+      gsi_prev (&gsi);
+      if (gsi_end_p (gsi))
+	continue;
+
+      g = gsi_stmt (gsi);
+      /* The guarding internal function call must have the same distribution
+	 alias id.  */
+      if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS)
+	  && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->orig_loop_num))
+	return g;
+    }
+  return NULL;
+}
+
 /* Set the uids of all the statements in basic blocks inside loop
    represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
    call guarding the loop which has been if converted.  */
@@ -494,7 +548,7 @@ set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call)
 	{
 	  arg = gimple_call_arg (g, 0);
 	  get_loop (cfun, tree_to_shwi (arg))->dont_vectorize = true;
-	  fold_loop_vectorized_call (g, boolean_false_node);
+	  fold_loop_internal_call (g, boolean_false_node);
 	}
     }
   bbs = get_loop_body (scalar_loop);
@@ -595,7 +649,7 @@ vectorize_loops (void)
     else
       {
 	loop_vec_info loop_vinfo, orig_loop_vinfo;
-	gimple *loop_vectorized_call;
+	gimple *loop_vectorized_call, *loop_dist_alias_call;
        try_vectorize:
 	if (!((flag_tree_loop_vectorize
 	       && optimize_loop_nest_for_speed_p (loop))
@@ -603,6 +657,7 @@ vectorize_loops (void)
 	  continue;
 	orig_loop_vinfo = NULL;
 	loop_vectorized_call = vect_loop_vectorized_call (loop);
+	loop_dist_alias_call = vect_loop_dist_alias_call (loop);
        vectorize_epilogue:
 	vect_location = find_loop_location (loop);
         if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION
@@ -652,8 +707,8 @@ vectorize_loops (void)
 		  {
 		    dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
 				     "basic block vectorized\n");
-		    fold_loop_vectorized_call (loop_vectorized_call,
-					       boolean_true_node);
+		    fold_loop_internal_call (loop_vectorized_call,
+					     boolean_true_node);
 		    loop_vectorized_call = NULL;
 		    ret |= TODO_cleanup_cfg;
 		  }
@@ -706,10 +761,17 @@ vectorize_loops (void)
 
 	if (loop_vectorized_call)
 	  {
-	    fold_loop_vectorized_call (loop_vectorized_call, boolean_true_node);
+	    fold_loop_internal_call (loop_vectorized_call, boolean_true_node);
 	    loop_vectorized_call = NULL;
 	    ret |= TODO_cleanup_cfg;
 	  }
+	if (loop_dist_alias_call)
+	  {
+	    tree value = gimple_call_arg (loop_dist_alias_call, 1);
+	    fold_loop_internal_call (loop_dist_alias_call, value);
+	    loop_dist_alias_call = NULL;
+	    ret |= TODO_cleanup_cfg;
+	  }
 
 	if (new_loop)
 	  {
@@ -741,7 +803,16 @@ vectorize_loops (void)
 	    gimple *g = vect_loop_vectorized_call (loop);
 	    if (g)
 	      {
-		fold_loop_vectorized_call (g, boolean_false_node);
+		fold_loop_internal_call (g, boolean_false_node);
+		ret |= TODO_cleanup_cfg;
+		g = NULL;
+	      }
+	    else
+	      g = vect_loop_dist_alias_call (loop);
+
+	    if (g)
+	      {
+		fold_loop_internal_call (g, boolean_false_node);
 		ret |= TODO_cleanup_cfg;
 	      }
 	  }
-- 
1.9.1


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]