[libgomp, openacc, openmp, PR83046] Prune removed funcs from offload table

[libgomp, openacc, openmp, PR83046] Prune removed funcs from offload table

[Tom de Vries]

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

Hi,

Consider this openmp example:
...
/* { dg-do link } */

#define N 100

int
main ()
{
   int a[N];
   int i, x;
   int c;

   c = 1;
#pragma omp target
   for (i = 0; i < 100; i++)
     a[i] = 0;

   if (c)
     __builtin_unreachable ();

#pragma omp target
   for (i = 0; i < 100; i++)
     a[i] = 1;

   return 0;
}
...

At ompexp, there are two offloaded functions, main._omp_fn.0 and 
main._omp_fn.1:
...
   <bb 2> :
   c = 1;
   ...
   __builtin_GOMP_target_ext (-1, main._omp_fn.0, 2, &.omp_data_arr.2,
                              &.omp_data_sizes.3, &.omp_data_kinds.4,
                              0, 0B, &.omp_target_args.9);
   ...
   if (c != 0)
     goto <bb 3>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 3> :
   __builtin_unreachable ();

  <bb 4> :
   ...
   __builtin_GOMP_target_ext (-1, main._omp_fn.1, 2, &.omp_data_arr.5,
                              &.omp_data_sizes.6, &.omp_data_kinds.7, 0,
                              0B, &.omp_target_args.8);
...

But after cpp1, the reference to main._omp_fn.1 in main is removed:
...
   __builtin_GOMP_target_ext (-1, main._omp_fn.0, 2, &.omp_data_arr.2,
                              &.omp_data_sizes.3, &.omp_data_kinds.4,
                              0, 0B, &.omp_target_args.9);
   __builtin_unreachable ();
...
Consequently, during free-fnsummary, the cgraph_node for main._omp_fn.1 
is removed.

However, the main._omp_fn.1 function is still present in the offload 
table offload_funcs.  This causes an ICE in lto1 when we're trying 
access the cgraph_node* for main._omp_fn.1, which is NULL:
....
lto1: internal compiler error: Segmentation fault
0xab73cf crash_signal
         gcc/toplev.c:325
0x94f694 cgraph_node::mark_force_output()
         gcc/cgraph.h:3140
0x94dfda input_offload_tables(bool)
         gcc/lto-cgraph.c:1940
0x5aa19f read_cgraph_and_symbols
         gcc/lto/lto.c:2872
0x5aa19f lto_main()
         gcc/lto/lto.c:3323
...

The ICE can be triggered for both openmp and openacc.

This patch fixes the ICE by removing entries from offload_funcs that no 
longer have corresponding cgraph_nodes.

Bootstrapped and reg-tested on x86_64.
Build and reg-tested on x86_64 with nvptx accelerator.

OK for trunk?

Thanks,
- Tom

[-- Attachment #2: 0001-Prune-removed-funcs-from-offload-table.patch --]
[-- Type: text/x-patch, Size: 2367 bytes --]

Prune removed funcs from offload table

2017-12-27  Tom de Vries  <tom@codesourcery.com>

	PR libgomp/83046
	* lto-cgraph.c (output_offload_tables): Remove offload_funcs entries
	that no longer have a corresponding cgraph_node.

	* testsuite/libgomp.oacc-c-c++-common/pr83046.c: New test.
	* testsuite/libgomp.c-c++-common/pr83046.c: New test.

---
 gcc/lto-cgraph.c                                   | 10 +++++++++
 libgomp/testsuite/libgomp.c-c++-common/pr83046.c   | 25 ++++++++++++++++++++++
 .../testsuite/libgomp.oacc-c-c++-common/pr83046.c  | 25 ++++++++++++++++++++++
 3 files changed, 60 insertions(+)

diff --git a/gcc/lto-cgraph.c b/gcc/lto-cgraph.c
index ed3df15b143..6bef2d974a6 100644
--- a/gcc/lto-cgraph.c
+++ b/gcc/lto-cgraph.c
@@ -1111,6 +1111,16 @@ output_offload_tables (void)
   struct lto_simple_output_block *ob
     = lto_create_simple_output_block (LTO_section_offload_table);
 
+  for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
+    {
+      if (!cgraph_node::get ((*offload_funcs)[i]))
+	{
+	  offload_funcs->ordered_remove (i);
+	  continue;
+	}
+      i++;
+    }
+
   for (unsigned i = 0; i < vec_safe_length (offload_funcs); i++)
     {
       streamer_write_enum (ob->main_stream, LTO_symtab_tags,
diff --git a/libgomp/testsuite/libgomp.c-c++-common/pr83046.c b/libgomp/testsuite/libgomp.c-c++-common/pr83046.c
new file mode 100644
index 00000000000..90dcb704fb3
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c-c++-common/pr83046.c
@@ -0,0 +1,25 @@
+/* { dg-do link } */
+
+#define N 100
+
+int
+main ()
+{
+  int a[N];
+  int i, x;
+  int c;
+
+  c = 1;
+#pragma omp target
+  for (i = 0; i < 100; i++)
+    a[i] = 0;
+
+  if (c)
+    __builtin_unreachable ();
+
+#pragma omp target
+  for (i = 0; i < 100; i++)
+    a[i] = 1;
+
+  return 0;
+}
diff --git a/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c b/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c
new file mode 100644
index 00000000000..a2a085c5fb2
--- /dev/null
+++ b/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c
@@ -0,0 +1,25 @@
+/* { dg-do link } */
+
+#define N 100
+
+int
+main ()
+{
+  int a[N];
+  int i, x;
+  int c;
+
+  c = 1;
+#pragma acc parallel loop
+  for (i = 0; i < 100; i++)
+    a[i] = 0;
+
+  if (c)
+    __builtin_unreachable ();
+
+#pragma acc parallel loop
+  for (i = 0; i < 100; i++)
+    a[i] = 1;
+
+  return 0;
+}

Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from offload table

[Jakub Jelinek]

On Thu, Dec 28, 2017 at 04:53:29PM +0100, Tom de Vries wrote:
> --- a/gcc/lto-cgraph.c
> +++ b/gcc/lto-cgraph.c
> @@ -1111,6 +1111,16 @@ output_offload_tables (void)
>    struct lto_simple_output_block *ob
>      = lto_create_simple_output_block (LTO_section_offload_table);
>  
> +  for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
> +    {
> +      if (!cgraph_node::get ((*offload_funcs)[i]))
> +	{
> +	  offload_funcs->ordered_remove (i);
> +	  continue;
> +	}
> +      i++;
> +    }

This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
Can't you instead just have 2 IVs, one for where we read the vector elt and
one for where we write it if the 2 are different, then truncate the vector
if needed at the end?

Another thing, I think you can safely remove elts from the vector (== from
the host and offloading target arrays) only when !flag_lto, because we rely
on the two arrays being the same.  So you can't remove elts only on the host
and not on the device, or vice versa.  The output_offload_tables function
has:
  /* In WHOPR mode during the WPA stage the joint offload tables need to be
     streamed to one partition only.  That's why we free offload_funcs and
     offload_vars after the first call of output_offload_tables.  */
  if (flag_wpa)
    {
      vec_free (offload_funcs);
      vec_free (offload_vars);
    }
so at least with flag_wpa, if we remove anything in there, it won't be
reflected by the other tables.  So, can we do something different in case
we can't easily remove stuff from the vector anymore?  Either store some
placeholder in the tables (dunno if NULL would work or what), or instead
ensure corresponding functions can't be removed?

	Jakub

Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from offload table

[Jakub Jelinek]

On Thu, Dec 28, 2017 at 05:06:57PM +0100, Jakub Jelinek wrote:
> This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
> Can't you instead just have 2 IVs, one for where we read the vector elt and
> one for where we write it if the 2 are different, then truncate the vector
> if needed at the end?
> 
> Another thing, I think you can safely remove elts from the vector (== from
> the host and offloading target arrays) only when !flag_lto, because we rely
> on the two arrays being the same.  So you can't remove elts only on the host
> and not on the device, or vice versa.  The output_offload_tables function
> has:
>   /* In WHOPR mode during the WPA stage the joint offload tables need to be
>      streamed to one partition only.  That's why we free offload_funcs and
>      offload_vars after the first call of output_offload_tables.  */
>   if (flag_wpa)
>     {
>       vec_free (offload_funcs);
>       vec_free (offload_vars);
>     }
> so at least with flag_wpa, if we remove anything in there, it won't be
> reflected by the other tables.  So, can we do something different in case
> we can't easily remove stuff from the vector anymore?  Either store some
> placeholder in the tables (dunno if NULL would work or what), or instead
> ensure corresponding functions can't be removed?

Maybe this removal if (!flag_lto) could be done earlier, e.g. at the
beginning of lto_output, and for nodes we keep around in the table
past that point set DECL_PRESERVE_P to 1 on the fndecl, so that we then
stream that flag.

	Jakub

Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from offload table

[Tom de Vries]

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

On 12/28/2017 05:14 PM, Jakub Jelinek wrote:
> On Thu, Dec 28, 2017 at 05:06:57PM +0100, Jakub Jelinek wrote:
>> This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
>> Can't you instead just have 2 IVs, one for where we read the vector elt and
>> one for where we write it if the 2 are different, then truncate the vector
>> if needed at the end?
>>

Done.

>> Another thing, I think you can safely remove elts from the vector (== from
>> the host and offloading target arrays) only when !flag_lto, because we rely
>> on the two arrays being the same.

I now mark the offload_funcs with DECL_PRESERVE_P in expand_omp_target 
if flag_lto, so AFAIU the removal should not happen anymore for flag_lto.

>>  So you can't remove elts only on the host
>> and not on the device, or vice versa.  The output_offload_tables function
>> has:
>>    /* In WHOPR mode during the WPA stage the joint offload tables need to be
>>       streamed to one partition only.  That's why we free offload_funcs and
>>       offload_vars after the first call of output_offload_tables.  */
>>    if (flag_wpa)
>>      {
>>        vec_free (offload_funcs);
>>        vec_free (offload_vars);
>>      }
>> so at least with flag_wpa, if we remove anything in there, it won't be
>> reflected by the other tables.  So, can we do something different in case
>> we can't easily remove stuff from the vector anymore?  Either store some
>> placeholder in the tables (dunno if NULL would work or what), 

I've tried NULL, that didn't work.

>> or instead
>> ensure corresponding functions can't be removed?
> 

That's the approach I've chosen, as described above.

> Maybe this removal if (!flag_lto) could be done earlier, e.g. at the
> beginning of lto_output, and for nodes we keep around in the table
> past that point set DECL_PRESERVE_P to 1 on the fndecl, so that we then
> stream that flag.

Done.

Bootstrapped and reg-tested on x86_64.
Build and reg-tested for x86_64 with nvptx accelerator.

OK for trunk?

Thanks,
- Tom

[-- Attachment #2: 0001-Prune-removed-funcs-from-offload-table.patch --]
[-- Type: text/x-patch, Size: 3792 bytes --]

Prune removed funcs from offload table

2017-12-27  Tom de Vries  <tom@codesourcery.com>

	PR libgomp/83046
	* omp-expand.c (expand_omp_target): If flag_lto, mark offload_funcs with
	DECL_PRESERVE_P.
	* lto-streamer-out.c (lto_output): Remove offload_funcs entries
	that no longer have a corresponding cgraph_node.  If !flag_lto, mark the
	remaining ones as DECL_PRESERVE_P.

	* testsuite/libgomp.oacc-c-c++-common/pr83046.c: New test.
	* testsuite/libgomp.c-c++-common/pr83046.c: New test.

---
 gcc/lto-streamer-out.c                             | 26 ++++++++++++++++++++++
 gcc/omp-expand.c                                   |  6 ++++-
 libgomp/testsuite/libgomp.c-c++-common/pr83046.c   | 25 +++++++++++++++++++++
 .../testsuite/libgomp.oacc-c-c++-common/pr83046.c  | 25 +++++++++++++++++++++
 4 files changed, 81 insertions(+), 1 deletion(-)

diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index ba29bd0..c38e389 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "builtins.h"
 #include "gomp-constants.h"
 #include "debug.h"
+#include "omp-offload.h"
 
 
 static void lto_write_tree (struct output_block*, tree, bool);
@@ -2355,6 +2356,31 @@ lto_output (void)
   int i, n_nodes;
   lto_symtab_encoder_t encoder = lto_get_out_decl_state ()->symtab_node_encoder;
 
+  bool truncated_p = false;
+  unsigned int write_index = 0;
+  for (unsigned read_index = 0; read_index < vec_safe_length (offload_funcs);
+       read_index++)
+    {
+      tree fn_decl = (*offload_funcs)[read_index];
+      bool remove_p = cgraph_node::get (fn_decl) == NULL;
+      if (remove_p)
+	{
+	  truncated_p = true;
+	  continue;
+	}
+
+      if (write_index != read_index)
+	(*offload_funcs)[write_index] = (*offload_funcs)[read_index];
+
+      write_index++;
+    }
+  if (truncated_p)
+    offload_funcs->truncate (write_index);
+
+  if (!flag_lto)
+    for (unsigned i = 0; i < vec_safe_length (offload_funcs); i++)
+      DECL_PRESERVE_P ((*offload_funcs)[i]) = 1;
+
   if (flag_checking)
     output = lto_bitmap_alloc ();
 
diff --git a/gcc/omp-expand.c b/gcc/omp-expand.c
index 0248833..59237ff 100644
--- a/gcc/omp-expand.c
+++ b/gcc/omp-expand.c
@@ -7058,7 +7058,11 @@ expand_omp_target (struct omp_region *region)
 
       /* Add the new function to the offload table.  */
       if (ENABLE_OFFLOADING)
-	vec_safe_push (offload_funcs, child_fn);
+	{
+	  if (flag_lto)
+	    DECL_PRESERVE_P (child_fn) = 1;
+	  vec_safe_push (offload_funcs, child_fn);
+	}
 
       bool need_asm = DECL_ASSEMBLER_NAME_SET_P (current_function_decl)
 		      && !DECL_ASSEMBLER_NAME_SET_P (child_fn);
diff --git a/libgomp/testsuite/libgomp.c-c++-common/pr83046.c b/libgomp/testsuite/libgomp.c-c++-common/pr83046.c
new file mode 100644
index 0000000..90dcb70
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c-c++-common/pr83046.c
@@ -0,0 +1,25 @@
+/* { dg-do link } */
+
+#define N 100
+
+int
+main ()
+{
+  int a[N];
+  int i, x;
+  int c;
+
+  c = 1;
+#pragma omp target
+  for (i = 0; i < 100; i++)
+    a[i] = 0;
+
+  if (c)
+    __builtin_unreachable ();
+
+#pragma omp target
+  for (i = 0; i < 100; i++)
+    a[i] = 1;
+
+  return 0;
+}
diff --git a/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c b/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c
new file mode 100644
index 0000000..a2a085c
--- /dev/null
+++ b/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c
@@ -0,0 +1,25 @@
+/* { dg-do link } */
+
+#define N 100
+
+int
+main ()
+{
+  int a[N];
+  int i, x;
+  int c;
+
+  c = 1;
+#pragma acc parallel loop
+  for (i = 0; i < 100; i++)
+    a[i] = 0;
+
+  if (c)
+    __builtin_unreachable ();
+
+#pragma acc parallel loop
+  for (i = 0; i < 100; i++)
+    a[i] = 1;
+
+  return 0;
+}

[RFC] Add vec::ordered_remove_if

[Tom de Vries]

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

[ was: Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from 
offload table ]

On 12/28/2017 05:06 PM, Jakub Jelinek wrote:
> On Thu, Dec 28, 2017 at 04:53:29PM +0100, Tom de Vries wrote:
>> --- a/gcc/lto-cgraph.c
>> +++ b/gcc/lto-cgraph.c
>> @@ -1111,6 +1111,16 @@ output_offload_tables (void)
>>     struct lto_simple_output_block *ob
>>       = lto_create_simple_output_block (LTO_section_offload_table);
>>   
>> +  for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
>> +    {
>> +      if (!cgraph_node::get ((*offload_funcs)[i]))
>> +	{
>> +	  offload_funcs->ordered_remove (i);
>> +	  continue;
>> +	}
>> +      i++;
>> +    }

> This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
> Can't you instead just have 2 IVs, one for where we read the vector elt and
> one for where we write it if the 2 are different, then truncate the vector
> if needed at the end?

I wonder if it makes sense to add this function to the vec interface.

Any comments?

Thanks,
- Tom

[-- Attachment #2: 0001-Add-vec-ordered_remove_if.patch --]
[-- Type: text/x-patch, Size: 3239 bytes --]

Add vec::ordered_remove_if

---
 gcc/vec.c | 21 +++++++++++++++++++++
 gcc/vec.h | 39 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 60 insertions(+)

diff --git a/gcc/vec.c b/gcc/vec.c
index 9a80f34..91e2464 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -403,6 +403,26 @@ test_ordered_remove ()
   ASSERT_EQ (9, v.length ());
 }
 
+static bool
+remove_5_7_p (const int &a)
+{
+  return a == 5 || a == 7;
+}
+
+/* Verify that vec::ordered_remove_if works correctly.  */
+
+static void
+test_ordered_remove_if (void)
+{
+  auto_vec <int> v;
+  safe_push_range (v, 0, 10);
+  v.ordered_remove_if (remove_5_7_p);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (8, v[6]);
+  ASSERT_EQ (8, v.length ());
+}
+
 /* Verify that vec::unordered_remove works correctly.  */
 
 static void
@@ -464,6 +484,7 @@ vec_c_tests ()
   test_pop ();
   test_safe_insert ();
   test_ordered_remove ();
+  test_ordered_remove_if ();
   test_unordered_remove ();
   test_block_remove ();
   test_qsort ();
diff --git a/gcc/vec.h b/gcc/vec.h
index f55a41f..857e4f4 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -571,6 +571,7 @@ public:
   void truncate (unsigned);
   void quick_insert (unsigned, const T &);
   void ordered_remove (unsigned);
+  void ordered_remove_if (bool (*) (const T &));
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
@@ -1013,6 +1014,31 @@ vec<T, A, vl_embed>::ordered_remove (unsigned ix)
 }
 
 
+/* Remove all elements from this vector for which REMOVE_ELEM_P (elem) holds.
+   Ordering of remaining elements is preserved.  This is an an O(N)
+   operation.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::ordered_remove_if (bool (*remove_elem_p) (const T &))
+{
+  unsigned int n = length ();
+  unsigned int write_index = 0;
+  for (unsigned int read_index = 0; read_index < n; ++read_index)
+    {
+      bool remove_p = remove_elem_p (read_index);
+      if (remove_p)
+	continue;
+
+      if (read_index != write_index)
+	m_vecdata[write_index] = m_vecdata[read_index];
+
+      write_index++;
+    }
+  truncate (write_index);
+}
+
+
 /* Remove an element from the IXth position of this vector.  Ordering of
    remaining elements is destroyed.  This is an O(1) operation.  */
 
@@ -1334,6 +1360,7 @@ public:
   void quick_insert (unsigned, const T &);
   void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
   void ordered_remove (unsigned);
+  void ordered_remove_if (bool (*) (const T &));
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
@@ -1779,6 +1806,18 @@ vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
 }
 
 
+/* Remove all elements from this vector for which REMOVE_ELEM_P (elem) holds.
+   Ordering of remaining elements is preserved.  This is an an O(N)
+   operation.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::ordered_remove_if (bool (*remove_elem_p) (const T &))
+{
+  m_vec->ordered_remove_if (remove_elem_p);
+}
+
+
 /* Remove an element from the IXth position of this vector.  Ordering
    of remaining elements is destroyed.  This is an O(1) operation.  */
 

Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from offload table

[Jakub Jelinek]

On Fri, Dec 29, 2017 at 02:07:49PM +0100, Tom de Vries wrote:
> --- a/gcc/lto-streamer-out.c
> +++ b/gcc/lto-streamer-out.c
> @@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "builtins.h"
>  #include "gomp-constants.h"
>  #include "debug.h"
> +#include "omp-offload.h"
>  
>  
>  static void lto_write_tree (struct output_block*, tree, bool);
> @@ -2355,6 +2356,31 @@ lto_output (void)
>    int i, n_nodes;
>    lto_symtab_encoder_t encoder = lto_get_out_decl_state ()->symtab_node_encoder;
>  
> +  bool truncated_p = false;

I don't think you need this var.

> +  unsigned int write_index = 0;
> +  for (unsigned read_index = 0; read_index < vec_safe_length (offload_funcs);
> +       read_index++)
> +    {
> +      tree fn_decl = (*offload_funcs)[read_index];
> +      bool remove_p = cgraph_node::get (fn_decl) == NULL;
> +      if (remove_p)
> +	{
> +	  truncated_p = true;
> +	  continue;
> +	}
> +
> +      if (write_index != read_index)
> +	(*offload_funcs)[write_index] = (*offload_funcs)[read_index];
> +
> +      write_index++;
> +    }
> +  if (truncated_p)
> +    offload_funcs->truncate (write_index);

Either you truncate unconditionally, truncate is extremely cheap operation,
or if you really wanted to guard it, you could just do
  if (read_index != write_index)

> +
> +  if (!flag_lto)
> +    for (unsigned i = 0; i < vec_safe_length (offload_funcs); i++)
> +      DECL_PRESERVE_P ((*offload_funcs)[i]) = 1;

Can you please do this inside of the above loop, you have fn_decl already
there, just do it after the
      if (remove_p)
	continue;
And, I think you can do it unconditionally at that point, or, can you use
in_lto_p instead of flag_lto?  flag_lto is set even during the -flto
compilation of the sources before LTO is streamed, there is no need to
pessimize that code, we can still remove it, we just can't remove anything
after we've streamed LTO bytecode (for either the host or offloading
targets).

> @@ -7058,7 +7058,11 @@ expand_omp_target (struct omp_region *region)
>  
>        /* Add the new function to the offload table.  */
>        if (ENABLE_OFFLOADING)
> -	vec_safe_push (offload_funcs, child_fn);
> +	{
> +	  if (flag_lto)
> +	    DECL_PRESERVE_P (child_fn) = 1;

And use if (in_lto_p) here too.

Ok for trunk with those changes.

	Jakub

Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from offload table

[Tom de Vries]

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

On 12/30/2017 10:54 AM, Jakub Jelinek wrote:
> On Fri, Dec 29, 2017 at 02:07:49PM +0100, Tom de Vries wrote:
>> --- a/gcc/lto-streamer-out.c
>> +++ b/gcc/lto-streamer-out.c
>> @@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.  If not see
>>   #include "builtins.h"
>>   #include "gomp-constants.h"
>>   #include "debug.h"
>> +#include "omp-offload.h"
>>   
>>   
>>   static void lto_write_tree (struct output_block*, tree, bool);
>> @@ -2355,6 +2356,31 @@ lto_output (void)
>>     int i, n_nodes;
>>     lto_symtab_encoder_t encoder = lto_get_out_decl_state ()->symtab_node_encoder;
>>   
>> +  bool truncated_p = false;
> 
> I don't think you need this var.
> 

Removed.

>> +  unsigned int write_index = 0;
>> +  for (unsigned read_index = 0; read_index < vec_safe_length (offload_funcs);
>> +       read_index++)
>> +    {
>> +      tree fn_decl = (*offload_funcs)[read_index];
>> +      bool remove_p = cgraph_node::get (fn_decl) == NULL;
>> +      if (remove_p)
>> +	{
>> +	  truncated_p = true;
>> +	  continue;
>> +	}
>> +
>> +      if (write_index != read_index)
>> +	(*offload_funcs)[write_index] = (*offload_funcs)[read_index];
>> +
>> +      write_index++;
>> +    }
>> +  if (truncated_p)
>> +    offload_funcs->truncate (write_index);
> 
> Either you truncate unconditionally, truncate is extremely cheap operation,
> or if you really wanted to guard it, you could just do
>    if (read_index != write_index)
> 

My concern was not the cost, but offload_funcs == NULL.

I've fixed this now by moving the code into a separate function and 
using the offload_funcs == NULL as early exit test.

>> +
>> +  if (!flag_lto)
>> +    for (unsigned i = 0; i < vec_safe_length (offload_funcs); i++)
>> +      DECL_PRESERVE_P ((*offload_funcs)[i]) = 1;
> 
> Can you please do this inside of the above loop, you have fn_decl already
> there, just do it after the
>        if (remove_p)
> 	continue;

Done.

> And, I think you can do it unconditionally at that point, 

Done. [ I wonder though if we can use in_lto_p as early exit test as well. ]

> or, can you use
> in_lto_p instead of flag_lto?  flag_lto is set even during the -flto
> compilation of the sources before LTO is streamed, there is no need to
> pessimize that code, we can still remove it, we just can't remove anything
> after we've streamed LTO bytecode (for either the host or offloading
> targets).
> 
>> @@ -7058,7 +7058,11 @@ expand_omp_target (struct omp_region *region)
>>   
>>         /* Add the new function to the offload table.  */
>>         if (ENABLE_OFFLOADING)
>> -	vec_safe_push (offload_funcs, child_fn);
>> +	{
>> +	  if (flag_lto)
>> +	    DECL_PRESERVE_P (child_fn) = 1;
> 
> And use if (in_lto_p) here too.
> 

Done.

> Ok for trunk with those changes.

Will commit after another round of testing.

Thanks,
- Tom

[-- Attachment #2: 0004-Prune-removed-funcs-from-offload-table.patch --]
[-- Type: text/x-patch, Size: 4065 bytes --]

Prune removed funcs from offload table

2017-12-27  Tom de Vries  <tom@codesourcery.com>

	PR libgomp/83046
	* omp-expand.c (expand_omp_target): If in_lto_p, mark offload_funcs with
	DECL_PRESERVE_P.
	* lto-streamer-out.c (prune_offload_funcs): New function.  Remove
	offload_funcs entries that no longer have a corresponding cgraph_node.
	Mark the remaining ones as DECL_PRESERVE_P.
	(output_lto): Call prune_offload_funcs.

	* testsuite/libgomp.oacc-c-c++-common/pr83046.c: New test.
	* testsuite/libgomp.c-c++-common/pr83046.c: New test.

---
 gcc/lto-streamer-out.c                             | 32 ++++++++++++++++++++++
 gcc/omp-expand.c                                   |  6 +++-
 libgomp/testsuite/libgomp.c-c++-common/pr83046.c   | 25 +++++++++++++++++
 .../testsuite/libgomp.oacc-c-c++-common/pr83046.c  | 25 +++++++++++++++++
 4 files changed, 87 insertions(+), 1 deletion(-)

diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index ba29bd088e6..ef170838fc0 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "builtins.h"
 #include "gomp-constants.h"
 #include "debug.h"
+#include "omp-offload.h"
 
 
 static void lto_write_tree (struct output_block*, tree, bool);
@@ -2345,6 +2346,35 @@ wrap_refs (tree *tp, int *ws, void *)
   return NULL_TREE;
 }
 
+/* Remove functions that are no longer used from offload_funcs, and mark the
+   remaining ones with DECL_PRESERVE_P.  */
+
+static void
+prune_offload_funcs (void)
+{
+  if (!offload_funcs)
+    return;
+
+  unsigned int write_index = 0;
+  for (unsigned read_index = 0; read_index < vec_safe_length (offload_funcs);
+       read_index++)
+    {
+      tree fn_decl = (*offload_funcs)[read_index];
+      bool remove_p = cgraph_node::get (fn_decl) == NULL;
+      if (remove_p)
+	continue;
+
+      DECL_PRESERVE_P (fn_decl) = 1;
+
+      if (write_index != read_index)
+	(*offload_funcs)[write_index] = (*offload_funcs)[read_index];
+
+      write_index++;
+    }
+
+  offload_funcs->truncate (write_index);
+}
+
 /* Main entry point from the pass manager.  */
 
 void
@@ -2355,6 +2385,8 @@ lto_output (void)
   int i, n_nodes;
   lto_symtab_encoder_t encoder = lto_get_out_decl_state ()->symtab_node_encoder;
 
+  prune_offload_funcs ();
+
   if (flag_checking)
     output = lto_bitmap_alloc ();
 
diff --git a/gcc/omp-expand.c b/gcc/omp-expand.c
index 02488339b40..663711b3aa4 100644
--- a/gcc/omp-expand.c
+++ b/gcc/omp-expand.c
@@ -7058,7 +7058,11 @@ expand_omp_target (struct omp_region *region)
 
       /* Add the new function to the offload table.  */
       if (ENABLE_OFFLOADING)
-	vec_safe_push (offload_funcs, child_fn);
+	{
+	  if (in_lto_p)
+	    DECL_PRESERVE_P (child_fn) = 1;
+	  vec_safe_push (offload_funcs, child_fn);
+	}
 
       bool need_asm = DECL_ASSEMBLER_NAME_SET_P (current_function_decl)
 		      && !DECL_ASSEMBLER_NAME_SET_P (child_fn);
diff --git a/libgomp/testsuite/libgomp.c-c++-common/pr83046.c b/libgomp/testsuite/libgomp.c-c++-common/pr83046.c
new file mode 100644
index 00000000000..90dcb704fb3
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c-c++-common/pr83046.c
@@ -0,0 +1,25 @@
+/* { dg-do link } */
+
+#define N 100
+
+int
+main ()
+{
+  int a[N];
+  int i, x;
+  int c;
+
+  c = 1;
+#pragma omp target
+  for (i = 0; i < 100; i++)
+    a[i] = 0;
+
+  if (c)
+    __builtin_unreachable ();
+
+#pragma omp target
+  for (i = 0; i < 100; i++)
+    a[i] = 1;
+
+  return 0;
+}
diff --git a/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c b/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c
new file mode 100644
index 00000000000..a2a085c5fb2
--- /dev/null
+++ b/libgomp/testsuite/libgomp.oacc-c-c++-common/pr83046.c
@@ -0,0 +1,25 @@
+/* { dg-do link } */
+
+#define N 100
+
+int
+main ()
+{
+  int a[N];
+  int i, x;
+  int c;
+
+  c = 1;
+#pragma acc parallel loop
+  for (i = 0; i < 100; i++)
+    a[i] = 0;
+
+  if (c)
+    __builtin_unreachable ();
+
+#pragma acc parallel loop
+  for (i = 0; i < 100; i++)
+    a[i] = 1;
+
+  return 0;
+}

Re: [RFC] Add vec::ordered_remove_if

[Richard Biener]

On Fri, Dec 29, 2017 at 2:55 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> [ was: Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from
> offload table ]
>
> On 12/28/2017 05:06 PM, Jakub Jelinek wrote:
>>
>> On Thu, Dec 28, 2017 at 04:53:29PM +0100, Tom de Vries wrote:
>>>
>>> --- a/gcc/lto-cgraph.c
>>> +++ b/gcc/lto-cgraph.c
>>> @@ -1111,6 +1111,16 @@ output_offload_tables (void)
>>>     struct lto_simple_output_block *ob
>>>       = lto_create_simple_output_block (LTO_section_offload_table);
>>>   +  for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
>>> +    {
>>> +      if (!cgraph_node::get ((*offload_funcs)[i]))
>>> +       {
>>> +         offload_funcs->ordered_remove (i);
>>> +         continue;
>>> +       }
>>> +      i++;
>>> +    }
>
>
>> This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
>> Can't you instead just have 2 IVs, one for where we read the vector elt
>> and
>> one for where we write it if the 2 are different, then truncate the vector
>> if needed at the end?
>
>
> I wonder if it makes sense to add this function to the vec interface.
>
> Any comments?

Hmm.  We do have quite some cases in the tree doing this kind of
operation - can you try finding one or two and see if it fits?

If we only could use lambdas here...

Oh, and I somehow miss a start/end index for operating on a vector part?

Richard.

> Thanks,
> - Tom

[PATCH] Add VEC_ORDERED_REMOVE_IF

[Tom de Vries]

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

[ was: Re: [RFC] Add vec::ordered_remove_if ]

On 01/02/2018 03:08 PM, Richard Biener wrote:
> On Fri, Dec 29, 2017 at 2:55 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> [ was: Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from
>> offload table ]
>>
>> On 12/28/2017 05:06 PM, Jakub Jelinek wrote:
>>>
>>> On Thu, Dec 28, 2017 at 04:53:29PM +0100, Tom de Vries wrote:
>>>>
>>>> --- a/gcc/lto-cgraph.c
>>>> +++ b/gcc/lto-cgraph.c
>>>> @@ -1111,6 +1111,16 @@ output_offload_tables (void)
>>>>      struct lto_simple_output_block *ob
>>>>        = lto_create_simple_output_block (LTO_section_offload_table);
>>>>    +  for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
>>>> +    {
>>>> +      if (!cgraph_node::get ((*offload_funcs)[i]))
>>>> +       {
>>>> +         offload_funcs->ordered_remove (i);
>>>> +         continue;
>>>> +       }
>>>> +      i++;
>>>> +    }
>>
>>
>>> This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
>>> Can't you instead just have 2 IVs, one for where we read the vector elt
>>> and
>>> one for where we write it if the 2 are different, then truncate the vector
>>> if needed at the end?
>>
>>
>> I wonder if it makes sense to add this function to the vec interface.
>>
>> Any comments?
> 
> Hmm.  We do have quite some cases in the tree doing this kind of
> operation - can you try finding one or two and see if it fits?
> 

Done.

[ I wonder though whether skipping element 0 in connect_traces is 
intentional or not. ]

> If we only could use lambdas here...
> 

I found having to write a separate function cumbersome, so I rewrote the 
function into macros VEC_ORDERED_REMOVE_IF and 
VEC_ORDERED_REMOVE_IF_FROM_TO, which gives a syntax somewhat similar to 
a lambda.

> Oh, and I somehow miss a start/end index for operating on a vector part?
> 

Done.

Bootstrapped and reg-tested on x86_64.

OK for trunk?

Thanks,
- Tom

[-- Attachment #2: 0001-Add-VEC_ORDERED_REMOVE_IF.patch --]
[-- Type: text/x-patch, Size: 7448 bytes --]

Add VEC_ORDERED_REMOVE_IF

2018-01-03  Tom de Vries  <tom@codesourcery.com>

	* vec.h	(VEC_ORDERED_REMOVE_IF, VEC_ORDERED_REMOVE_IF_FROM_TO): Define.
	* vec.c (test_ordered_remove_if): New function.
	(vec_c_tests): Call test_ordered_remove_if.
	* dwarf2cfi.c (connect_traces): Use VEC_ORDERED_REMOVE_IF_FROM_TO.
	* lto-streamer-out.c (prune_offload_funcs): Use VEC_ORDERED_REMOVE_IF.
	* tree-vect-patterns.c (vect_pattern_recog_1): Use
	VEC_ORDERED_REMOVE_IF.

---
 gcc/dwarf2cfi.c          | 19 +++++++------------
 gcc/lto-streamer-out.c   | 26 ++++++++------------------
 gcc/tree-vect-patterns.c | 10 ++++++----
 gcc/vec.c                | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 gcc/vec.h                | 34 ++++++++++++++++++++++++++++++++++
 5 files changed, 101 insertions(+), 34 deletions(-)

diff --git a/gcc/dwarf2cfi.c b/gcc/dwarf2cfi.c
index 7a70639..7732ab2 100644
--- a/gcc/dwarf2cfi.c
+++ b/gcc/dwarf2cfi.c
@@ -2703,7 +2703,7 @@ before_next_cfi_note (rtx_insn *start)
 static void
 connect_traces (void)
 {
-  unsigned i, n = trace_info.length ();
+  unsigned i, n;
   dw_trace_info *prev_ti, *ti;
 
   /* ??? Ideally, we should have both queued and processed every trace.
@@ -2714,20 +2714,15 @@ connect_traces (void)
      these are not "real" instructions, and should not be considered.
      This could be generically useful for tablejump data as well.  */
   /* Remove all unprocessed traces from the list.  */
-  for (i = n - 1; i > 0; --i)
-    {
-      ti = &trace_info[i];
-      if (ti->beg_row == NULL)
-	{
-	  trace_info.ordered_remove (i);
-	  n -= 1;
-	}
-      else
-	gcc_assert (ti->end_row != NULL);
-    }
+  unsigned ix, ix2;
+  VEC_ORDERED_REMOVE_IF_FROM_TO (trace_info, ix, ix2, ti, 1,
+				 trace_info.length (), ti->beg_row == NULL);
+  FOR_EACH_VEC_ELT (trace_info, ix, ti)
+    gcc_assert (ti->end_row != NULL);
 
   /* Work from the end back to the beginning.  This lets us easily insert
      remember/restore_state notes in the correct order wrt other notes.  */
+  n = trace_info.length ();
   prev_ti = &trace_info[n - 1];
   for (i = n - 1; i > 0; --i)
     {
diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index ef17083..b0993c7 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -2355,24 +2355,14 @@ prune_offload_funcs (void)
   if (!offload_funcs)
     return;
 
-  unsigned int write_index = 0;
-  for (unsigned read_index = 0; read_index < vec_safe_length (offload_funcs);
-       read_index++)
-    {
-      tree fn_decl = (*offload_funcs)[read_index];
-      bool remove_p = cgraph_node::get (fn_decl) == NULL;
-      if (remove_p)
-	continue;
-
-      DECL_PRESERVE_P (fn_decl) = 1;
-
-      if (write_index != read_index)
-	(*offload_funcs)[write_index] = (*offload_funcs)[read_index];
-
-      write_index++;
-    }
-
-  offload_funcs->truncate (write_index);
+  unsigned ix, ix2;
+  tree *elem_ptr;
+  VEC_ORDERED_REMOVE_IF (*offload_funcs, ix, ix2, elem_ptr,
+			 cgraph_node::get (*elem_ptr) == NULL);
+
+  tree fn_decl;
+  FOR_EACH_VEC_ELT (*offload_funcs, ix, fn_decl)
+    DECL_PRESERVE_P (fn_decl) = 1;
 }
 
 /* Main entry point from the pass manager.  */
diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
index a2c6293..2a5d056 100644
--- a/gcc/tree-vect-patterns.c
+++ b/gcc/tree-vect-patterns.c
@@ -4165,7 +4165,6 @@ vect_pattern_recog_1 (vect_recog_func *recog_func,
   tree type_in, type_out;
   enum tree_code code;
   int i;
-  gimple *next;
 
   stmts_to_replace->truncate (0);
   stmts_to_replace->quick_push (stmt);
@@ -4232,9 +4231,12 @@ vect_pattern_recog_1 (vect_recog_func *recog_func,
   /* Patterns cannot be vectorized using SLP, because they change the order of
      computation.  */
   if (loop_vinfo)
-    FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
-      if (next == stmt)
-        LOOP_VINFO_REDUCTIONS (loop_vinfo).ordered_remove (i);
+    {
+      unsigned ix, ix2;
+      gimple **elem_ptr;
+      VEC_ORDERED_REMOVE_IF (LOOP_VINFO_REDUCTIONS (loop_vinfo), ix, ix2,
+			     elem_ptr, *elem_ptr == stmt);
+    }
 
   /* It is possible that additional pattern stmts are created and inserted in
      STMTS_TO_REPLACE.  We create a stmt_info for each of them, and mark the
diff --git a/gcc/vec.c b/gcc/vec.c
index 9a80f34..eb382f5 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -403,6 +403,51 @@ test_ordered_remove ()
   ASSERT_EQ (9, v.length ());
 }
 
+/* Verify that vec::ordered_remove_if works correctly.  */
+
+static void
+test_ordered_remove_if (void)
+{
+  auto_vec <int> v;
+  safe_push_range (v, 0, 10);
+  unsigned ix, ix2;
+  int *elem_ptr;
+  VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr,
+			 *elem_ptr == 5 || *elem_ptr == 7);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (8, v[6]);
+  ASSERT_EQ (8, v.length ());
+
+  v.truncate (0);
+  safe_push_range (v, 0, 10);
+  VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 6,
+				 *elem_ptr == 5 || *elem_ptr == 7);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (7, v[6]);
+  ASSERT_EQ (9, v.length ());
+
+  v.truncate (0);
+  safe_push_range (v, 0, 10);
+  VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 5,
+				 *elem_ptr == 5 || *elem_ptr == 7);
+  VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 8, 10,
+				 *elem_ptr == 5 || *elem_ptr == 7);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (5, v[5]);
+  ASSERT_EQ (6, v[6]);
+  ASSERT_EQ (10, v.length ());
+
+  v.truncate (0);
+  safe_push_range (v, 0, 10);
+  VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (7, v[6]);
+  ASSERT_EQ (9, v.length ());
+}
+
 /* Verify that vec::unordered_remove works correctly.  */
 
 static void
@@ -464,6 +509,7 @@ vec_c_tests ()
   test_pop ();
   test_safe_insert ();
   test_ordered_remove ();
+  test_ordered_remove_if ();
   test_unordered_remove ();
   test_block_remove ();
   test_qsort ();
diff --git a/gcc/vec.h b/gcc/vec.h
index f55a41f..dd914f8 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -1013,6 +1013,40 @@ vec<T, A, vl_embed>::ordered_remove (unsigned ix)
 }
 
 
+/* Remove elements in [START, END) from VEC for which COND holds.  Ordering of
+   remaining elements is preserved.  This is an an O(N) operation.  */
+
+#define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index,	\
+				      elem_ptr, start, end, cond)	\
+  {									\
+    gcc_assert ((end) <= (vec).length ());				\
+    for (read_index = write_index = (start); read_index < (end);	\
+	 ++read_index)							\
+      {									\
+	elem_ptr = &(vec)[read_index];					\
+	bool remove_p = (cond);						\
+	if (remove_p)							\
+	  continue;							\
+									\
+	if (read_index != write_index)					\
+	  (vec)[write_index] = (vec)[read_index];			\
+									\
+	write_index++;							\
+      }									\
+									\
+    if (read_index - write_index > 0)					\
+      (vec).block_remove (write_index, read_index - write_index);	\
+  }
+
+
+/* Remove elements from VEC for which COND holds.  Ordering of remaining
+   elements is preserved.  This is an an O(N) operation.  */
+
+#define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr,	\
+			      cond)					\
+  VEC_ORDERED_REMOVE_IF_FROM_TO (vec, read_index, write_index,		\
+				 elem_ptr, 0, (vec).length (), cond)
+
 /* Remove an element from the IXth position of this vector.  Ordering of
    remaining elements is destroyed.  This is an O(1) operation.  */
 

Re: [PATCH] Add VEC_ORDERED_REMOVE_IF

[Tom de Vries]

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

On 01/10/2018 07:03 PM, Bernhard Reutner-Fischer wrote:
> On 5 January 2018 22:06:10 CET, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> [ was: Re: [RFC] Add vec::ordered_remove_if ]
> 
> Tom,
> 
> s/an an/an/g
> 

Fixed.

Also:
- added '()' around more macro args in VEC_ORDERED_REMOVE_IF
- added PR number ( https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83786 )

OK for trunk?

Thanks,
- Tom

[-- Attachment #2: 0001-Add-VEC_ORDERED_REMOVE_IF.patch --]
[-- Type: text/x-patch, Size: 7462 bytes --]

Add VEC_ORDERED_REMOVE_IF

2018-01-03  Tom de Vries  <tom@codesourcery.com>

	PR other/83786
	* vec.h	(VEC_ORDERED_REMOVE_IF, VEC_ORDERED_REMOVE_IF_FROM_TO): Define.
	* vec.c (test_ordered_remove_if): New function.
	(vec_c_tests): Call test_ordered_remove_if.
	* dwarf2cfi.c (connect_traces): Use VEC_ORDERED_REMOVE_IF_FROM_TO.
	* lto-streamer-out.c (prune_offload_funcs): Use VEC_ORDERED_REMOVE_IF.
	* tree-vect-patterns.c (vect_pattern_recog_1): Use
	VEC_ORDERED_REMOVE_IF.

---
 gcc/dwarf2cfi.c          | 19 +++++++------------
 gcc/lto-streamer-out.c   | 26 ++++++++------------------
 gcc/tree-vect-patterns.c | 10 ++++++----
 gcc/vec.c                | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 gcc/vec.h                | 34 ++++++++++++++++++++++++++++++++++
 5 files changed, 101 insertions(+), 34 deletions(-)

diff --git a/gcc/dwarf2cfi.c b/gcc/dwarf2cfi.c
index 7a70639..7732ab2 100644
--- a/gcc/dwarf2cfi.c
+++ b/gcc/dwarf2cfi.c
@@ -2703,7 +2703,7 @@ before_next_cfi_note (rtx_insn *start)
 static void
 connect_traces (void)
 {
-  unsigned i, n = trace_info.length ();
+  unsigned i, n;
   dw_trace_info *prev_ti, *ti;
 
   /* ??? Ideally, we should have both queued and processed every trace.
@@ -2714,20 +2714,15 @@ connect_traces (void)
      these are not "real" instructions, and should not be considered.
      This could be generically useful for tablejump data as well.  */
   /* Remove all unprocessed traces from the list.  */
-  for (i = n - 1; i > 0; --i)
-    {
-      ti = &trace_info[i];
-      if (ti->beg_row == NULL)
-	{
-	  trace_info.ordered_remove (i);
-	  n -= 1;
-	}
-      else
-	gcc_assert (ti->end_row != NULL);
-    }
+  unsigned ix, ix2;
+  VEC_ORDERED_REMOVE_IF_FROM_TO (trace_info, ix, ix2, ti, 1,
+				 trace_info.length (), ti->beg_row == NULL);
+  FOR_EACH_VEC_ELT (trace_info, ix, ti)
+    gcc_assert (ti->end_row != NULL);
 
   /* Work from the end back to the beginning.  This lets us easily insert
      remember/restore_state notes in the correct order wrt other notes.  */
+  n = trace_info.length ();
   prev_ti = &trace_info[n - 1];
   for (i = n - 1; i > 0; --i)
     {
diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index ef17083..b0993c7 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -2355,24 +2355,14 @@ prune_offload_funcs (void)
   if (!offload_funcs)
     return;
 
-  unsigned int write_index = 0;
-  for (unsigned read_index = 0; read_index < vec_safe_length (offload_funcs);
-       read_index++)
-    {
-      tree fn_decl = (*offload_funcs)[read_index];
-      bool remove_p = cgraph_node::get (fn_decl) == NULL;
-      if (remove_p)
-	continue;
-
-      DECL_PRESERVE_P (fn_decl) = 1;
-
-      if (write_index != read_index)
-	(*offload_funcs)[write_index] = (*offload_funcs)[read_index];
-
-      write_index++;
-    }
-
-  offload_funcs->truncate (write_index);
+  unsigned ix, ix2;
+  tree *elem_ptr;
+  VEC_ORDERED_REMOVE_IF (*offload_funcs, ix, ix2, elem_ptr,
+			 cgraph_node::get (*elem_ptr) == NULL);
+
+  tree fn_decl;
+  FOR_EACH_VEC_ELT (*offload_funcs, ix, fn_decl)
+    DECL_PRESERVE_P (fn_decl) = 1;
 }
 
 /* Main entry point from the pass manager.  */
diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
index a2c6293..2a5d056 100644
--- a/gcc/tree-vect-patterns.c
+++ b/gcc/tree-vect-patterns.c
@@ -4165,7 +4165,6 @@ vect_pattern_recog_1 (vect_recog_func *recog_func,
   tree type_in, type_out;
   enum tree_code code;
   int i;
-  gimple *next;
 
   stmts_to_replace->truncate (0);
   stmts_to_replace->quick_push (stmt);
@@ -4232,9 +4231,12 @@ vect_pattern_recog_1 (vect_recog_func *recog_func,
   /* Patterns cannot be vectorized using SLP, because they change the order of
      computation.  */
   if (loop_vinfo)
-    FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
-      if (next == stmt)
-        LOOP_VINFO_REDUCTIONS (loop_vinfo).ordered_remove (i);
+    {
+      unsigned ix, ix2;
+      gimple **elem_ptr;
+      VEC_ORDERED_REMOVE_IF (LOOP_VINFO_REDUCTIONS (loop_vinfo), ix, ix2,
+			     elem_ptr, *elem_ptr == stmt);
+    }
 
   /* It is possible that additional pattern stmts are created and inserted in
      STMTS_TO_REPLACE.  We create a stmt_info for each of them, and mark the
diff --git a/gcc/vec.c b/gcc/vec.c
index 9a80f34..eb382f5 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -403,6 +403,51 @@ test_ordered_remove ()
   ASSERT_EQ (9, v.length ());
 }
 
+/* Verify that vec::ordered_remove_if works correctly.  */
+
+static void
+test_ordered_remove_if (void)
+{
+  auto_vec <int> v;
+  safe_push_range (v, 0, 10);
+  unsigned ix, ix2;
+  int *elem_ptr;
+  VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr,
+			 *elem_ptr == 5 || *elem_ptr == 7);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (8, v[6]);
+  ASSERT_EQ (8, v.length ());
+
+  v.truncate (0);
+  safe_push_range (v, 0, 10);
+  VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 6,
+				 *elem_ptr == 5 || *elem_ptr == 7);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (7, v[6]);
+  ASSERT_EQ (9, v.length ());
+
+  v.truncate (0);
+  safe_push_range (v, 0, 10);
+  VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 5,
+				 *elem_ptr == 5 || *elem_ptr == 7);
+  VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 8, 10,
+				 *elem_ptr == 5 || *elem_ptr == 7);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (5, v[5]);
+  ASSERT_EQ (6, v[6]);
+  ASSERT_EQ (10, v.length ());
+
+  v.truncate (0);
+  safe_push_range (v, 0, 10);
+  VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5);
+  ASSERT_EQ (4, v[4]);
+  ASSERT_EQ (6, v[5]);
+  ASSERT_EQ (7, v[6]);
+  ASSERT_EQ (9, v.length ());
+}
+
 /* Verify that vec::unordered_remove works correctly.  */
 
 static void
@@ -464,6 +509,7 @@ vec_c_tests ()
   test_pop ();
   test_safe_insert ();
   test_ordered_remove ();
+  test_ordered_remove_if ();
   test_unordered_remove ();
   test_block_remove ();
   test_qsort ();
diff --git a/gcc/vec.h b/gcc/vec.h
index f55a41f..bdff305c 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -1013,6 +1013,40 @@ vec<T, A, vl_embed>::ordered_remove (unsigned ix)
 }
 
 
+/* Remove elements in [START, END) from VEC for which COND holds.  Ordering of
+   remaining elements is preserved.  This is an O(N) operation.  */
+
+#define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index,	\
+				      elem_ptr, start, end, cond)	\
+  {									\
+    gcc_assert ((end) <= (vec).length ());				\
+    for (read_index = write_index = (start); read_index < (end);	\
+	 ++read_index)							\
+      {									\
+	elem_ptr = &(vec)[read_index];					\
+	bool remove_p = (cond);						\
+	if (remove_p)							\
+	  continue;							\
+									\
+	if (read_index != write_index)					\
+	  (vec)[write_index] = (vec)[read_index];			\
+									\
+	write_index++;							\
+      }									\
+									\
+    if (read_index - write_index > 0)					\
+      (vec).block_remove (write_index, read_index - write_index);	\
+  }
+
+
+/* Remove elements from VEC for which COND holds.  Ordering of remaining
+   elements is preserved.  This is an O(N) operation.  */
+
+#define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr,	\
+			      cond)					\
+  VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index,	\
+				 elem_ptr, 0, (vec).length (), (cond))
+
 /* Remove an element from the IXth position of this vector.  Ordering of
    remaining elements is destroyed.  This is an O(1) operation.  */
 

Re: [PATCH] Add VEC_ORDERED_REMOVE_IF

[Jeff Law]

On 01/11/2018 06:03 AM, Tom de Vries wrote:
> On 01/10/2018 07:03 PM, Bernhard Reutner-Fischer wrote:
>> On 5 January 2018 22:06:10 CET, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>
>>> [ was: Re: [RFC] Add vec::ordered_remove_if ]
>>
>> Tom,
>>
>> s/an an/an/g
>>
> 
> Fixed.
> 
> Also:
> - added '()' around more macro args in VEC_ORDERED_REMOVE_IF
> - added PR number ( https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83786 )
> 
> OK for trunk?
> 
> Thanks,
> - Tom
> 
> 0001-Add-VEC_ORDERED_REMOVE_IF.patch
> 
> 
> Add VEC_ORDERED_REMOVE_IF
> 
> 2018-01-03  Tom de Vries  <tom@codesourcery.com>
> 
> 	PR other/83786
> 	* vec.h	(VEC_ORDERED_REMOVE_IF, VEC_ORDERED_REMOVE_IF_FROM_TO): Define.
> 	* vec.c (test_ordered_remove_if): New function.
> 	(vec_c_tests): Call test_ordered_remove_if.
> 	* dwarf2cfi.c (connect_traces): Use VEC_ORDERED_REMOVE_IF_FROM_TO.
> 	* lto-streamer-out.c (prune_offload_funcs): Use VEC_ORDERED_REMOVE_IF.
> 	* tree-vect-patterns.c (vect_pattern_recog_1): Use
> 	VEC_ORDERED_REMOVE_IF.
OK.
jeff