On Wed, Oct 28, 2020 at 06:31:22PM +0800, Chung-Lin Tang wrote:
> > > + for (tree c = clauses; c; c = OMP_CLAUSE_CHAIN (c))
> > > + if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_MAP
> > > + && OMP_CLAUSE_MAP_KIND (c) == GOMP_MAP_FIRSTPRIVATE_POINTER
> > > + && TREE_CODE (TREE_TYPE (OMP_CLAUSE_DECL (c))) != ARRAY_TYPE)
> > > + {
> > > + tree ptr = OMP_CLAUSE_DECL (c);
> > > + bool ptr_mapped = false;
> > > + if (is_target)
> > > + {
> > > + for (tree m = clauses; m; m = OMP_CLAUSE_CHAIN (m))
> > Isn't this O(n^2) in number of clauses? I mean, e.g. for the equality
> > comparisons (but see below) it could be dealt with e.g. using some bitmap
> > with DECL_UIDs.
>
> At this stage, we really don't assume any ordering of the clauses, nor try to
> modify its ordering yet, so the base-pointer map (if it exists) could be any
> where in the list (building some "visited set" isn't really suitable here).
> I don't think this is really that much an issue of concern though.
Many functions try hard to avoid O(n^2) issues, see e.g. all the bitmap
handling in *finish_omp_clauses etc.
One can have tens of thousands of clauses and then the quadraticness will
hit hard. This does a mere OMP_CLAUSE_DECL (c) == ptr comparison, so it
is only about the decls and decls can be very easily handled through
DECL_UID (bitmaps, hash sets/maps/tables).
> +extern void c_omp_adjust_clauses (tree, bool);
So, can you please rename the function to either
c_omp_adjust_target_clauses or c_omp_adjust_mapping_clauses or
c_omp_adjust_map_clauses?
> --- a/gcc/c-family/c-omp.c
> +++ b/gcc/c-family/c-omp.c
> @@ -2579,3 +2579,50 @@ c_omp_map_clause_name (tree clause, bool oacc)
> }
> return omp_clause_code_name[OMP_CLAUSE_CODE (clause)];
> }
> +
> +/* Adjust map clauses after normal clause parsing, mainly to turn specific
> + base-pointer map cases into attach/detach and mark them addressable. */
> +void
> +c_omp_adjust_clauses (tree clauses, bool is_target)
> +{
> + for (tree c = clauses; c; c = OMP_CLAUSE_CHAIN (c))
> + if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_MAP
> + && OMP_CLAUSE_MAP_KIND (c) == GOMP_MAP_FIRSTPRIVATE_POINTER
If this is only meant to handle decls, perhaps there should be
&& DECL_P (OMP_CLAUSE_DECL (c))
?
> + && TREE_CODE (TREE_TYPE (OMP_CLAUSE_DECL (c))) != ARRAY_TYPE)
> + {
> + tree ptr = OMP_CLAUSE_DECL (c);
> + bool ptr_mapped = false;
> + if (is_target)
> + {
> + for (tree m = clauses; m; m = OMP_CLAUSE_CHAIN (m))
> + if (OMP_CLAUSE_CODE (m) == OMP_CLAUSE_MAP
> + && OMP_CLAUSE_DECL (m) == ptr
> + && (OMP_CLAUSE_MAP_KIND (m) == GOMP_MAP_ALLOC
> + || OMP_CLAUSE_MAP_KIND (m) == GOMP_MAP_TO
> + || OMP_CLAUSE_MAP_KIND (m) == GOMP_MAP_FROM
> + || OMP_CLAUSE_MAP_KIND (m) == GOMP_MAP_TOFROM
> + || OMP_CLAUSE_MAP_KIND (m) == GOMP_MAP_ALWAYS_TO
> + || OMP_CLAUSE_MAP_KIND (m) == GOMP_MAP_ALWAYS_FROM
> + || OMP_CLAUSE_MAP_KIND (m) == GOMP_MAP_ALWAYS_TOFROM))
> + {
> + ptr_mapped = true;
> + break;
> + }
What you could e.g. do is have this loop at the start of function, with
&& DECL_P (OMP_CLAUSE_DECL (m))
instead of the == ptr check, and perhaps && POINTER_TYPE_P (TREE_TYPE
(OMP_CLAUSE_DECL (m))) check and set a bit in a bitmap for each such decl,
then in the GOMP_MAP_FIRSTPRIVATE_POINTER loop just check the bitmap.
Or, keep it in the loop like it is above, but populate the bitmap
lazily (upon seeing the first GOMP_MAP_FIRSTPRIVATE_POINTER) and for further
ones just use it.
Jakub
