From 2bba75411e14cdf1ee67f4ee965665cf6c6c6ea7 Mon Sep 17 00:00:00 2001 From: Martin Jambor Date: Tue, 2 May 2017 14:49:55 +0200 Subject: [PATCH] [PR 78687] Set SRA grp_write lazily 2017-05-02 Martin Jambor PR tree-optimization/78687 * tree-sra.c (access): New field parent. (process_subtree_disqualification): New function. (disqualify_candidate): Call it. (build_accesses_from_assign): Reset write flag if creating an assighnment link. (build_access_subtree): Fill in parent field and also prpagate down grp_write flag. (create_artificial_child_access): New parameter set_grp_write, set grp_write to its value. (propagate_subaccesses_across_link): Also propagate grp_write flag values. (propagate_all_subaccesses): Push the closest parent back to work queue if add_access_to_work_queue returned true. testsuite/ * g++.dg/tree-ssa/pr78687.C: New test. From-SVN: r247497 --- gcc/ChangeLog | 17 + gcc/testsuite/ChangeLog | 5 + gcc/testsuite/g++.dg/tree-ssa/pr78687.C | 483 ++++++++++++++++++++++++ gcc/tree-sra.c | 91 ++++- 4 files changed, 583 insertions(+), 13 deletions(-) create mode 100644 gcc/testsuite/g++.dg/tree-ssa/pr78687.C diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 194dbe22b12..22c7c61e1f5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,20 @@ +2017-05-02 Martin Jambor + + PR tree-optimization/78687 + * tree-sra.c (access): New field parent. + (process_subtree_disqualification): New function. + (disqualify_candidate): Call it. + (build_accesses_from_assign): Reset write flag if creating an + assighnment link. + (build_access_subtree): Fill in parent field and also prpagate + down grp_write flag. + (create_artificial_child_access): New parameter set_grp_write, set + grp_write to its value. + (propagate_subaccesses_across_link): Also propagate grp_write flag + values. + (propagate_all_subaccesses): Push the closest parent back to work + queue if add_access_to_work_queue returned true. + 2017-05-02 Richard Biener * common.opt (fstrict-overflow): Alias negative to fwrapv. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 31020af78bf..81ecd07d6de 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2017-05-02 Martin Jambor + + PR tree-optimization/78687 + * g++.dg/tree-ssa/pr78687.C: New test. + 2017-05-02 Richard Biener * c-c++-common/Wlogical-op-1.c: Add -fwrapv to restore previous diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr78687.C b/gcc/testsuite/g++.dg/tree-ssa/pr78687.C new file mode 100644 index 00000000000..698458f0e9a --- /dev/null +++ b/gcc/testsuite/g++.dg/tree-ssa/pr78687.C @@ -0,0 +1,483 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -std=gnu++14 -fdump-tree-sra" } */ + +#include + +#define EGGS_CXX11_CONSTEXPR constexpr +#define EGGS_CXX11_STATIC_CONSTEXPR static constexpr +#define EGGS_CXX14_CONSTEXPR constexpr +#define EGGS_CXX11_NOEXCEPT noexcept + +namespace eggs { namespace variants { namespace detail +{ + struct empty + { + EGGS_CXX11_CONSTEXPR bool operator==(empty) const { return true; } + EGGS_CXX11_CONSTEXPR bool operator<(empty) const { return false; } + }; + + template + struct identity + { + using type = T; + }; + + template + struct index + { + EGGS_CXX11_STATIC_CONSTEXPR std::size_t value = I; + }; + + template + struct pack + { + using type = pack; + EGGS_CXX11_STATIC_CONSTEXPR std::size_t size = sizeof...(Ts); + }; + + template + struct pack_c + { + using type = pack_c; + EGGS_CXX11_STATIC_CONSTEXPR std::size_t size = sizeof...(Vs); + }; + + /////////////////////////////////////////////////////////////////////////// + template + struct _make_index_pack_twice; + + template + struct _make_index_pack_twice< + pack_c + , false + > : pack_c + {}; + + template + struct _make_index_pack_twice< + pack_c + , true + > : pack_c + {}; + + template + struct _make_index_pack + : _make_index_pack_twice< + typename _make_index_pack::type + , N % 2 != 0 + > + {}; + + template <> + struct _make_index_pack<1> + : pack_c + {}; + + template <> + struct _make_index_pack<0> + : pack_c + {}; + + template + using make_index_pack = typename _make_index_pack::type; + + template + struct _index_pack; + + template + struct _index_pack> + : _make_index_pack + {}; + + template + using index_pack = typename _index_pack::type; + + /////////////////////////////////////////////////////////////////////////// + template + struct all_of; + + template + struct all_of> + : std::integral_constant< + bool + , std::is_same< + pack_c + , pack_c // true... + >::value + > + {}; + + template + struct all_of> + : all_of> + {}; + + template + struct any_of; + + template + struct any_of> + : std::integral_constant< + bool + , !all_of>::value + > + {}; + + template + struct any_of> + : any_of> + {}; + + /////////////////////////////////////////////////////////////////////////// + template + struct _indexed {}; + + template > + struct _indexer; + + template + struct _indexer, pack_c> + : _indexed... + {}; + + empty _at_index(...); + + template + identity _at_index(_indexed const&); + + template + struct at_index + : decltype(_at_index(_indexer{})) + {}; + + empty _index_of(...); + + template + index _index_of(_indexed const&); + + template + struct index_of + : decltype(_index_of(_indexer{})) + {}; +}}} + +namespace eggs { namespace variants { namespace detail +{ + template + struct _union; + + /////////////////////////////////////////////////////////////////////////// + template + struct _union, IsTriviallyDestructible> + {}; + + template + struct _union, true> + { + EGGS_CXX11_STATIC_CONSTEXPR std::size_t size = 1 + sizeof...(Ts); + + template + EGGS_CXX11_CONSTEXPR _union(index<0>, Args&&... args) + : _head(std::forward(args)...) + {} + + template + EGGS_CXX11_CONSTEXPR _union(index, Args&&... args) + : _tail(index{}, std::forward(args)...) + {} + + EGGS_CXX14_CONSTEXPR void* target() EGGS_CXX11_NOEXCEPT + { + return &_target; + } + + EGGS_CXX11_CONSTEXPR void const* target() const EGGS_CXX11_NOEXCEPT + { + return &_target; + } + + EGGS_CXX14_CONSTEXPR T& get(index<0>) EGGS_CXX11_NOEXCEPT + { + return this->_head; + } + + EGGS_CXX11_CONSTEXPR T const& get(index<0>) const EGGS_CXX11_NOEXCEPT + { + return this->_head; + } + + template < + std::size_t I + , typename U = typename at_index>::type + > + EGGS_CXX14_CONSTEXPR U& get(index) EGGS_CXX11_NOEXCEPT + { + return this->_tail.get(index{}); + } + + template < + std::size_t I + , typename U = typename at_index>::type + > + EGGS_CXX11_CONSTEXPR U const& get(index) const EGGS_CXX11_NOEXCEPT + { + return this->_tail.get(index{}); + } + + private: + union + { + char _target; + T _head; + _union, true> _tail; + }; + }; + + /////////////////////////////////////////////////////////////////////////// + template + struct _storage; + + template + struct _storage, true, true> + : _union< + pack + , all_of...>>::value + > + { + using base_type = _union< + pack + , all_of...>>::value + >; + + EGGS_CXX11_CONSTEXPR _storage() EGGS_CXX11_NOEXCEPT + : base_type{index<0>{}} + , _which{0} + {} + + _storage(_storage const& rhs) = default; + _storage(_storage&& rhs) = default; + + template + EGGS_CXX11_CONSTEXPR _storage(index which, Args&&... args) + : base_type{which, std::forward(args)...} + , _which{I} + {} + + _storage& operator=(_storage const& rhs) = default; + _storage& operator=(_storage&& rhs) = default; + + EGGS_CXX11_CONSTEXPR std::size_t which() const + { + return _which; + } + + using base_type::target; + using base_type::get; + + protected: + std::size_t _which; + }; + + template + using storage = _storage< + pack + , all_of...>>::value + , all_of...>>::value + >; +}}} + +namespace eggs { namespace variants +{ + template + class variant; + + namespace detail + { + /////////////////////////////////////////////////////////////////////// + namespace _best_match + { + template + struct overloads + {}; + + template + struct overloads, I> + : overloads, I + 1> + { + using fun_ptr = index(*)(T); + operator fun_ptr(); + }; + + template + auto _invoke(F&&, T&&) + -> decltype(std::declval()(std::declval())); + + struct _fallback {}; + + _fallback _invoke(...); + + template < + typename T, typename U + , typename R = decltype(_best_match::_invoke( + std::declval(), std::declval())) + > + struct result_of : R + {}; + + template + struct result_of + {}; + } + + template + struct index_of_best_match + : _best_match::result_of<_best_match::overloads, U> + {}; + + } + + template + class variant + { + + public: + EGGS_CXX11_CONSTEXPR variant() EGGS_CXX11_NOEXCEPT = delete; + + variant(variant const& rhs) = default; + + variant(variant&& rhs) = default; + + template < + typename U + , typename Enable = typename std::enable_if::type, variant + >::value>::type + , std::size_t I = detail::index_of_best_match< + U&&, detail::pack>::value + , typename T = typename detail::at_index< + I, detail::pack>::type + > + EGGS_CXX11_CONSTEXPR variant(U&& v) + noexcept( + std::is_nothrow_constructible::value) + : _storage{detail::index{}, std::forward(v)} + {} + + ~variant() = default; + variant& operator=(variant const& rhs) = delete; + + private: + detail::storage _storage; + }; +}} + +template +struct ref_proxy : Base +{ + using Base::Base; + + ref_proxy() + : Base() + { + } + + ref_proxy(Base ptr) + : Base(std::move(ptr)) + { + } +}; + +template +struct inplace_ref +{ + explicit inplace_ref(T inner) + : inner_(inner) + { + } + + T inner_; +}; + +template +struct variant_ref +{ + variant_ref() = delete; + + explicit variant_ref(eggs::variants::variant t) + : inner_storage_(t) + { + } + + template + variant_ref(ref_proxy ptr) + : inner_storage_(ptr.inner_storage_) + {} + +private: + eggs::variants::variant inner_storage_; +}; + +struct option_1 +{ + void *a, *b, *c, *d, *e; +}; + +struct option_2 +{ +}; + +using option_ref = variant_ref; + + +struct qual_option +{ + qual_option(ref_proxy type, int quals) + : type_(type) + , quals_(quals) + { + } + + explicit qual_option(ref_proxy type) + : qual_option(type, 0) + { + } + + ref_proxy type_; + int quals_; +}; + +inline ref_proxy make_object_1() +{ + return ref_proxy(option_2()); +} + +inline ref_proxy make_object_2() +{ + return make_object_1(); +} + +inline inplace_ref make_object_3(ref_proxy&& a0) +{ + return inplace_ref(qual_option(a0)); +} + +inline ref_proxy > make_object_4(ref_proxy&& a0) +{ + return make_object_3(std::move(a0)); +} + + +ref_proxy > f() __attribute__((noinline)); + +ref_proxy > f() +{ + return make_object_4(make_object_2()); +} + +int main(int argc, char* argv[]) +{ + for (;;) + f(); +} + +/* { dg-final { scan-tree-dump "Removing load:.*ptr;" "sra" } } */ diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c index 0334d061507..1606573aead 100644 --- a/gcc/tree-sra.c +++ b/gcc/tree-sra.c @@ -158,6 +158,10 @@ struct access the representative. */ struct access *group_representative; + /* After access tree has been constructed, this points to the parent of the + current access, if there is one. NULL for roots. */ + struct access *parent; + /* If this access has any children (in terms of the definition above), this points to the first one. */ struct access *first_child; @@ -690,6 +694,19 @@ static bool constant_decl_p (tree decl) return VAR_P (decl) && DECL_IN_CONSTANT_POOL (decl); } + +/* Mark LHS of assign links out of ACCESS and its children as written to. */ + +static void +process_subtree_disqualification (struct access *access) +{ + struct access *child; + for (struct assign_link *link = access->first_link; link; link = link->next) + link->lacc->grp_write = true; + for (child = access->first_child; child; child = child->next_sibling) + process_subtree_disqualification (child); +} + /* Remove DECL from candidates for SRA and write REASON to the dump file if there is one. */ static void @@ -706,6 +723,13 @@ disqualify_candidate (tree decl, const char *reason) print_generic_expr (dump_file, decl, 0); fprintf (dump_file, " - %s\n", reason); } + + struct access *access = get_first_repr_for_decl (decl); + while (access) + { + process_subtree_disqualification (access); + access = access->next_grp; + } } /* Return true iff the type contains a field or an element which does not allow @@ -1338,8 +1362,10 @@ build_accesses_from_assign (gimple *stmt) link->lacc = lacc; link->racc = racc; - add_link_to_rhs (racc, link); + /* Let's delay marking the areas as written until propagation of accesses + across link. */ + lacc->write = false; } return lacc || racc; @@ -2252,6 +2278,8 @@ build_access_subtree (struct access **access) else last_child->next_sibling = *access; last_child = *access; + (*access)->parent = root; + (*access)->grp_write |= root->grp_write; if (!build_access_subtree (access)) return false; @@ -2495,13 +2523,15 @@ child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset, /* Create a new child access of PARENT, with all properties just like MODEL except for its offset and with its grp_write false and grp_read true. - Return the new access or NULL if it cannot be created. Note that this access - is created long after all splicing and sorting, it's not located in any - access vector and is automatically a representative of its group. */ + Return the new access or NULL if it cannot be created. Note that this + access is created long after all splicing and sorting, it's not located in + any access vector and is automatically a representative of its group. Set + the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */ static struct access * create_artificial_child_access (struct access *parent, struct access *model, - HOST_WIDE_INT new_offset) + HOST_WIDE_INT new_offset, + bool set_grp_write) { struct access **child; tree expr = parent->base; @@ -2523,7 +2553,7 @@ create_artificial_child_access (struct access *parent, struct access *model, access->offset = new_offset; access->size = model->size; access->type = model->type; - access->grp_write = true; + access->grp_write = set_grp_write; access->grp_read = false; access->reverse = model->reverse; @@ -2549,10 +2579,23 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) HOST_WIDE_INT norm_delta = lacc->offset - racc->offset; bool ret = false; + /* IF the LHS is still not marked as being written to, we only need to do so + if the RHS at this level actually was. */ + if (!lacc->grp_write && + (racc->grp_write || TREE_CODE (racc->base) == PARM_DECL)) + { + lacc->grp_write = true; + ret = true; + } + if (is_gimple_reg_type (lacc->type) || lacc->grp_unscalarizable_region || racc->grp_unscalarizable_region) - return false; + { + ret |= !lacc->grp_write; + lacc->grp_write = true; + return ret; + } if (is_gimple_reg_type (racc->type)) { @@ -2572,7 +2615,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) lacc->grp_no_warning = true; } } - return false; + return ret; } for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling) @@ -2581,23 +2624,37 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) HOST_WIDE_INT norm_offset = rchild->offset + norm_delta; if (rchild->grp_unscalarizable_region) - continue; + { + lacc->grp_write = true; + continue; + } if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size, &new_acc)) { if (new_acc) { + if (!new_acc->grp_write + && (lacc->grp_write || rchild->grp_write)) + { + new_acc ->grp_write = true; + ret = true; + } + rchild->grp_hint = 1; new_acc->grp_hint |= new_acc->grp_read; if (rchild->first_child) ret |= propagate_subaccesses_across_link (new_acc, rchild); } + else + lacc->grp_write = true; continue; } rchild->grp_hint = 1; - new_acc = create_artificial_child_access (lacc, rchild, norm_offset); + new_acc = create_artificial_child_access (lacc, rchild, norm_offset, + lacc->grp_write + || rchild->grp_write); if (new_acc) { ret = true; @@ -2628,9 +2685,17 @@ propagate_all_subaccesses (void) if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base))) continue; lacc = lacc->group_representative; - if (propagate_subaccesses_across_link (lacc, racc) - && lacc->first_link) - add_access_to_work_queue (lacc); + if (propagate_subaccesses_across_link (lacc, racc)) + do + { + if (lacc->first_link) + { + add_access_to_work_queue (lacc); + break; + } + lacc = lacc->parent; + } + while (lacc); } } } -- 2.30.2