From patchwork Sat Nov 13 17:28:58 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 47617 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8D38B385800D for ; Sat, 13 Nov 2021 17:29:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8D38B385800D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1636824573; bh=ckoAaiyQsEa8YiNe0+ydCWdmgF89xqqQSjhdP0r1QZc=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=MtsdE++DwuRATajZsxnzc25NR3ZufdJYlU12uEfE309U2q9G9Wfuz4x19dKdtzKmH Hwz/q4XlsIqORY5wFGvX5DYbC1fevIKG32XAbduNlN+2Xj0v9oRytD6DLc4Hwb1m9u FrVqwCWNlKFP8VEcMS7mJmd+TDeUNtV9NBvXJZPU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id E32F63858410 for ; Sat, 13 Nov 2021 17:28:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E32F63858410 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id D9040280941; Sat, 13 Nov 2021 18:28:58 +0100 (CET) Date: Sat, 13 Nov 2021 18:28:58 +0100 To: gcc-patches@gcc.gnu.org Subject: Cleanup modref_access_node Message-ID: <20211113172858.GF13726@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, GIT_PATCH_0, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Jan Hubicka via Gcc-patches From: Jan Hubicka Reply-To: Jan Hubicka Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Hi, this patch moves member functions of modref_access_node from ipa-modref-tree.h to ipa-modref-tree.c since they become long and not fitting for inlines anyway. I also cleaned up the interface by making static insert method (which handles inserting accesses into a vector and optimizing them) which makes it possible to hide most of the interface handling interval merging private. Honza gcc/ChangeLog: * ipa-modref-tree.h (struct modref_access_node): Move longer member functions to ipa-modref-tree.c (modref_ref_node::try_merge_with): Turn into modreef_acces_node member function. * ipa-modref-tree.c (modref_access_node::contains): Move here from ipa-modref-tree.h. (modref_access_node::update): Likewise. (modref_access_node::merge): Likewise. (modref_access_node::closer_pair_p): Likewise. (modref_access_node::forced_merge): Likewise. (modref_access_node::update2): Likewise. (modref_access_node::combined_offsets): Likewise. (modref_access_node::try_merge_with): Likewise. (modref_access_node::insert): Likewise. diff --git a/gcc/ipa-modref-tree.c b/gcc/ipa-modref-tree.c index d0ee487f9fa..e363c506a09 100644 --- a/gcc/ipa-modref-tree.c +++ b/gcc/ipa-modref-tree.c @@ -28,6 +28,541 @@ along with GCC; see the file COPYING3. If not see #if CHECKING_P +/* Return true if both accesses are the same. */ +bool +modref_access_node::operator == (modref_access_node &a) const +{ + if (parm_index != a.parm_index) + return false; + if (parm_index != MODREF_UNKNOWN_PARM) + { + if (parm_offset_known != a.parm_offset_known) + return false; + if (parm_offset_known + && !known_eq (parm_offset, a.parm_offset)) + return false; + } + if (range_info_useful_p () != a.range_info_useful_p ()) + return false; + if (range_info_useful_p () + && (!known_eq (a.offset, offset) + || !known_eq (a.size, size) + || !known_eq (a.max_size, max_size))) + return false; + return true; +} + +/* Return true A is a subaccess. */ +bool +modref_access_node::contains (const modref_access_node &a) const +{ + poly_int64 aoffset_adj = 0; + if (parm_index != MODREF_UNKNOWN_PARM) + { + if (parm_index != a.parm_index) + return false; + if (parm_offset_known) + { + if (!a.parm_offset_known) + return false; + /* Accesses are never below parm_offset, so look + for smaller offset. + If access ranges are known still allow merging + when bit offsets comparsion passes. */ + if (!known_le (parm_offset, a.parm_offset) + && !range_info_useful_p ()) + return false; + /* We allow negative aoffset_adj here in case + there is an useful range. This is because adding + a.offset may result in non-ngative offset again. + Ubsan fails on val << LOG_BITS_PER_UNIT where val + is negative. */ + aoffset_adj = (a.parm_offset - parm_offset) + * BITS_PER_UNIT; + } + } + if (range_info_useful_p ()) + { + if (!a.range_info_useful_p ()) + return false; + /* Sizes of stores are used to check that object is big enough + to fit the store, so smaller or unknown sotre is more general + than large store. */ + if (known_size_p (size) + && (!known_size_p (a.size) + || !known_le (size, a.size))) + return false; + if (known_size_p (max_size)) + return known_subrange_p (a.offset + aoffset_adj, + a.max_size, offset, max_size); + else + return known_le (offset, a.offset + aoffset_adj); + } + return true; +} + +/* Update access range to new parameters. + If RECORD_ADJUSTMENTS is true, record number of changes in the access + and if threshold is exceeded start dropping precision + so only constantly many updates are possible. This makes dataflow + to converge. */ +void +modref_access_node::update (poly_int64 parm_offset1, + poly_int64 offset1, poly_int64 size1, + poly_int64 max_size1, bool record_adjustments) +{ + if (known_eq (parm_offset, parm_offset1) + && known_eq (offset, offset1) + && known_eq (size, size1) + && known_eq (max_size, max_size1)) + return; + if (!record_adjustments + || (++adjustments) < param_modref_max_adjustments) + { + parm_offset = parm_offset1; + offset = offset1; + size = size1; + max_size = max_size1; + } + else + { + if (dump_file) + fprintf (dump_file, + "--param param=modref-max-adjustments limit reached:"); + if (!known_eq (parm_offset, parm_offset1)) + { + if (dump_file) + fprintf (dump_file, " parm_offset cleared"); + parm_offset_known = false; + } + if (!known_eq (size, size1)) + { + size = -1; + if (dump_file) + fprintf (dump_file, " size cleared"); + } + if (!known_eq (max_size, max_size1)) + { + max_size = -1; + if (dump_file) + fprintf (dump_file, " max_size cleared"); + } + if (!known_eq (offset, offset1)) + { + offset = 0; + if (dump_file) + fprintf (dump_file, " offset cleared"); + } + if (dump_file) + fprintf (dump_file, "\n"); + } +} + +/* Merge in access A if it is possible to do without losing + precision. Return true if successful. + If RECORD_ADJUSTMENTs is true, remember how many interval + was prolonged and punt when there are too many. */ +bool +modref_access_node::merge (const modref_access_node &a, + bool record_adjustments) +{ + poly_int64 offset1 = 0; + poly_int64 aoffset1 = 0; + poly_int64 new_parm_offset = 0; + + /* We assume that containment was tested earlier. */ + gcc_checking_assert (!contains (a) && !a.contains (*this)); + if (parm_index != MODREF_UNKNOWN_PARM) + { + if (parm_index != a.parm_index) + return false; + if (parm_offset_known) + { + if (!a.parm_offset_known) + return false; + if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1)) + return false; + } + } + /* See if we can merge ranges. */ + if (range_info_useful_p ()) + { + /* In this case we have containment that should be + handled earlier. */ + gcc_checking_assert (a.range_info_useful_p ()); + + /* If a.size is less specified than size, merge only + if intervals are otherwise equivalent. */ + if (known_size_p (size) + && (!known_size_p (a.size) || known_lt (a.size, size))) + { + if (((known_size_p (max_size) || known_size_p (a.max_size)) + && !known_eq (max_size, a.max_size)) + || !known_eq (offset1, aoffset1)) + return false; + update (new_parm_offset, offset1, a.size, max_size, + record_adjustments); + return true; + } + /* If sizes are same, we can extend the interval. */ + if ((known_size_p (size) || known_size_p (a.size)) + && !known_eq (size, a.size)) + return false; + if (known_le (offset1, aoffset1)) + { + if (!known_size_p (max_size) + || known_ge (offset1 + max_size, aoffset1)) + { + update2 (new_parm_offset, offset1, size, max_size, + aoffset1, a.size, a.max_size, + record_adjustments); + return true; + } + } + else if (known_le (aoffset1, offset1)) + { + if (!known_size_p (a.max_size) + || known_ge (aoffset1 + a.max_size, offset1)) + { + update2 (new_parm_offset, offset1, size, max_size, + aoffset1, a.size, a.max_size, + record_adjustments); + return true; + } + } + return false; + } + update (new_parm_offset, offset1, + size, max_size, record_adjustments); + return true; +} + +/* Return true if A1 and B1 can be merged with lower information + less than A2 and B2. + Assume that no containment or lossless merging is possible. */ +bool +modref_access_node::closer_pair_p (const modref_access_node &a1, + const modref_access_node &b1, + const modref_access_node &a2, + const modref_access_node &b2) +{ + /* Merging different parm indexes comes to complete loss + of range info. */ + if (a1.parm_index != b1.parm_index) + return false; + if (a2.parm_index != b2.parm_index) + return true; + /* If parm is known and parm indexes are the same we should + already have containment. */ + gcc_checking_assert (a1.parm_offset_known && b1.parm_offset_known); + gcc_checking_assert (a2.parm_offset_known && b2.parm_offset_known); + + /* First normalize offsets for parm offsets. */ + poly_int64 new_parm_offset, offseta1, offsetb1, offseta2, offsetb2; + if (!a1.combined_offsets (b1, &new_parm_offset, &offseta1, &offsetb1) + || !a2.combined_offsets (b2, &new_parm_offset, &offseta2, &offsetb2)) + gcc_unreachable (); + + + /* Now compute distnace of the intervals. */ + poly_int64 dist1, dist2; + if (known_le (offseta1, offsetb1)) + { + if (!known_size_p (a1.max_size)) + dist1 = 0; + else + dist1 = offsetb1 - offseta1 - a1.max_size; + } + else + { + if (!known_size_p (b1.max_size)) + dist1 = 0; + else + dist1 = offseta1 - offsetb1 - b1.max_size; + } + if (known_le (offseta2, offsetb2)) + { + if (!known_size_p (a2.max_size)) + dist2 = 0; + else + dist2 = offsetb2 - offseta2 - a2.max_size; + } + else + { + if (!known_size_p (b2.max_size)) + dist2 = 0; + else + dist2 = offseta2 - offsetb2 - b2.max_size; + } + /* It may happen that intervals overlap in case size + is different. Preffer the overlap to non-overlap. */ + if (known_lt (dist1, 0) && known_ge (dist2, 0)) + return true; + if (known_lt (dist2, 0) && known_ge (dist1, 0)) + return false; + if (known_lt (dist1, 0)) + /* If both overlaps minimize overlap. */ + return known_le (dist2, dist1); + else + /* If both are disjoint look for smaller distance. */ + return known_le (dist1, dist2); +} + +/* Merge in access A while losing precision. */ +void +modref_access_node::forced_merge (const modref_access_node &a, + bool record_adjustments) +{ + if (parm_index != a.parm_index) + { + gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM); + parm_index = MODREF_UNKNOWN_PARM; + return; + } + + /* We assume that containment and lossless merging + was tested earlier. */ + gcc_checking_assert (!contains (a) && !a.contains (*this) + && !merge (a, record_adjustments)); + gcc_checking_assert (parm_offset_known && a.parm_offset_known); + + poly_int64 new_parm_offset, offset1, aoffset1; + if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1)) + { + parm_offset_known = false; + return; + } + gcc_checking_assert (range_info_useful_p () + && a.range_info_useful_p ()); + if (record_adjustments) + adjustments += a.adjustments; + update2 (new_parm_offset, + offset1, size, max_size, + aoffset1, a.size, a.max_size, + record_adjustments); +} + +/* Merge two ranges both starting at parm_offset1 and update THIS + with result. */ +void +modref_access_node::update2 (poly_int64 parm_offset1, + poly_int64 offset1, poly_int64 size1, + poly_int64 max_size1, + poly_int64 offset2, poly_int64 size2, + poly_int64 max_size2, + bool record_adjustments) +{ + poly_int64 new_size = size1; + + if (!known_size_p (size2) + || known_le (size2, size1)) + new_size = size2; + else + gcc_checking_assert (known_le (size1, size2)); + + if (known_le (offset1, offset2)) + ; + else if (known_le (offset2, offset1)) + { + std::swap (offset1, offset2); + std::swap (max_size1, max_size2); + } + else + gcc_unreachable (); + + poly_int64 new_max_size; + + if (!known_size_p (max_size1)) + new_max_size = max_size1; + else if (!known_size_p (max_size2)) + new_max_size = max_size2; + else + { + new_max_size = max_size2 + offset2 - offset1; + if (known_le (new_max_size, max_size1)) + new_max_size = max_size1; + } + + update (parm_offset1, offset1, + new_size, new_max_size, record_adjustments); +} + +/* Given access nodes THIS and A, return true if they + can be done with common parm_offsets. In this case + return parm offset in new_parm_offset, new_offset + which is start of range in THIS and new_aoffset that + is start of range in A. */ +bool +modref_access_node::combined_offsets (const modref_access_node &a, + poly_int64 *new_parm_offset, + poly_int64 *new_offset, + poly_int64 *new_aoffset) const +{ + gcc_checking_assert (parm_offset_known && a.parm_offset_known); + if (known_le (a.parm_offset, parm_offset)) + { + *new_offset = offset + + ((parm_offset - a.parm_offset) + << LOG2_BITS_PER_UNIT); + *new_aoffset = a.offset; + *new_parm_offset = a.parm_offset; + return true; + } + else if (known_le (parm_offset, a.parm_offset)) + { + *new_aoffset = a.offset + + ((a.parm_offset - parm_offset) + << LOG2_BITS_PER_UNIT); + *new_offset = offset; + *new_parm_offset = parm_offset; + return true; + } + else + return false; +} + +/* Try to optimize the access ACCESSES list after entry INDEX was modified. */ +void +modref_access_node::try_merge_with (vec *&accesses, + size_t index) +{ + size_t i; + + for (i = 0; i < accesses->length ();) + if (i != index) + { + bool found = false, restart = false; + modref_access_node *a = &(*accesses)[i]; + modref_access_node *n = &(*accesses)[index]; + + if (n->contains (*a)) + found = true; + if (!found && n->merge (*a, false)) + found = restart = true; + gcc_checking_assert (found || !a->merge (*n, false)); + if (found) + { + accesses->unordered_remove (i); + if (index == accesses->length ()) + { + index = i; + i++; + } + if (restart) + i = 0; + } + else + i++; + } + else + i++; +} + +/* Insert access with OFFSET and SIZE. + Collapse tree if it has more than MAX_ACCESSES entries. + If RECORD_ADJUSTMENTs is true avoid too many interval extensions. + Return true if record was changed. + + Reutrn 0 if nothing changed, 1 if insert was successful and -1 + if entries should be collapsed. */ +int +modref_access_node::insert (vec *&accesses, + modref_access_node a, size_t max_accesses, + bool record_adjustments) +{ + size_t i, j; + modref_access_node *a2; + + /* Verify that list does not contain redundant accesses. */ + if (flag_checking) + { + size_t i, i2; + modref_access_node *a, *a2; + + FOR_EACH_VEC_SAFE_ELT (accesses, i, a) + { + FOR_EACH_VEC_SAFE_ELT (accesses, i2, a2) + if (i != i2) + gcc_assert (!a->contains (*a2)); + } + } + + FOR_EACH_VEC_SAFE_ELT (accesses, i, a2) + { + if (a2->contains (a)) + return 0; + if (a.contains (*a2)) + { + a.adjustments = 0; + a2->parm_index = a.parm_index; + a2->parm_offset_known = a.parm_offset_known; + a2->update (a.parm_offset, a.offset, a.size, a.max_size, + record_adjustments); + modref_access_node::try_merge_with (accesses, i); + return 1; + } + if (a2->merge (a, record_adjustments)) + { + modref_access_node::try_merge_with (accesses, i); + return 1; + } + gcc_checking_assert (!(a == *a2)); + } + + /* If this base->ref pair has too many accesses stored, we will clear + all accesses and bail out. */ + if (accesses && accesses->length () >= max_accesses) + { + if (max_accesses < 2) + return -1; + /* Find least harmful merge and perform it. */ + int best1 = -1, best2 = -1; + FOR_EACH_VEC_SAFE_ELT (accesses, i, a2) + { + for (j = i + 1; j < accesses->length (); j++) + if (best1 < 0 + || modref_access_node::closer_pair_p + (*a2, (*accesses)[j], + (*accesses)[best1], + best2 < 0 ? a : (*accesses)[best2])) + { + best1 = i; + best2 = j; + } + if (modref_access_node::closer_pair_p + (*a2, a, + (*accesses)[best1], + best2 < 0 ? a : (*accesses)[best2])) + { + best1 = i; + best2 = -1; + } + } + (*accesses)[best1].forced_merge (best2 < 0 ? a : (*accesses)[best2], + record_adjustments); + /* Check that merging indeed merged ranges. */ + gcc_checking_assert ((*accesses)[best1].contains + (best2 < 0 ? a : (*accesses)[best2])); + if (!(*accesses)[best1].useful_p ()) + return -1; + if (dump_file && best2 >= 0) + fprintf (dump_file, + "--param param=modref-max-accesses limit reached;" + " merging %i and %i\n", best1, best2); + else if (dump_file) + fprintf (dump_file, + "--param param=modref-max-accesses limit reached;" + " merging with %i\n", best1); + modref_access_node::try_merge_with (accesses, best1); + if (best2 >= 0) + insert (accesses, a, max_accesses, record_adjustments); + return 1; + } + a.adjustments = 0; + vec_safe_push (accesses, a); + return 1; +} + namespace selftest { static void diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h index 3e213b23d79..b35cf3a4aed 100644 --- a/gcc/ipa-modref-tree.h +++ b/gcc/ipa-modref-tree.h @@ -57,7 +57,6 @@ enum modref_special_parms { /* Memory access. */ struct GTY(()) modref_access_node { - /* Access range information (in bits). */ poly_int64 offset; poly_int64 size; @@ -88,380 +87,28 @@ struct GTY(()) modref_access_node || known_ge (offset, 0)); } /* Return true if both accesses are the same. */ - bool operator == (modref_access_node &a) const - { - if (parm_index != a.parm_index) - return false; - if (parm_index != MODREF_UNKNOWN_PARM) - { - if (parm_offset_known != a.parm_offset_known) - return false; - if (parm_offset_known - && !known_eq (parm_offset, a.parm_offset)) - return false; - } - if (range_info_useful_p () != a.range_info_useful_p ()) - return false; - if (range_info_useful_p () - && (!known_eq (a.offset, offset) - || !known_eq (a.size, size) - || !known_eq (a.max_size, max_size))) - return false; - return true; - } - /* Return true A is a subaccess. */ - bool contains (const modref_access_node &a) const - { - poly_int64 aoffset_adj = 0; - if (parm_index != MODREF_UNKNOWN_PARM) - { - if (parm_index != a.parm_index) - return false; - if (parm_offset_known) - { - if (!a.parm_offset_known) - return false; - /* Accesses are never below parm_offset, so look - for smaller offset. - If access ranges are known still allow merging - when bit offsets comparsion passes. */ - if (!known_le (parm_offset, a.parm_offset) - && !range_info_useful_p ()) - return false; - /* We allow negative aoffset_adj here in case - there is an useful range. This is because adding - a.offset may result in non-ngative offset again. - Ubsan fails on val << LOG_BITS_PER_UNIT where val - is negative. */ - aoffset_adj = (a.parm_offset - parm_offset) - * BITS_PER_UNIT; - } - } - if (range_info_useful_p ()) - { - if (!a.range_info_useful_p ()) - return false; - /* Sizes of stores are used to check that object is big enough - to fit the store, so smaller or unknown sotre is more general - than large store. */ - if (known_size_p (size) - && (!known_size_p (a.size) - || !known_le (size, a.size))) - return false; - if (known_size_p (max_size)) - return known_subrange_p (a.offset + aoffset_adj, - a.max_size, offset, max_size); - else - return known_le (offset, a.offset + aoffset_adj); - } - return true; - } - /* Update access range to new parameters. - If RECORD_ADJUSTMENTS is true, record number of changes in the access - and if threshold is exceeded start dropping precision - so only constantly many updates are possible. This makes dataflow - to converge. */ - void update (poly_int64 parm_offset1, - poly_int64 offset1, poly_int64 size1, poly_int64 max_size1, - bool record_adjustments) - { - if (known_eq (parm_offset, parm_offset1) - && known_eq (offset, offset1) - && known_eq (size, size1) - && known_eq (max_size, max_size1)) - return; - if (!record_adjustments - || (++adjustments) < param_modref_max_adjustments) - { - parm_offset = parm_offset1; - offset = offset1; - size = size1; - max_size = max_size1; - } - else - { - if (dump_file) - fprintf (dump_file, - "--param param=modref-max-adjustments limit reached:"); - if (!known_eq (parm_offset, parm_offset1)) - { - if (dump_file) - fprintf (dump_file, " parm_offset cleared"); - parm_offset_known = false; - } - if (!known_eq (size, size1)) - { - size = -1; - if (dump_file) - fprintf (dump_file, " size cleared"); - } - if (!known_eq (max_size, max_size1)) - { - max_size = -1; - if (dump_file) - fprintf (dump_file, " max_size cleared"); - } - if (!known_eq (offset, offset1)) - { - offset = 0; - if (dump_file) - fprintf (dump_file, " offset cleared"); - } - if (dump_file) - fprintf (dump_file, "\n"); - } - } - /* Merge in access A if it is possible to do without losing - precision. Return true if successful. - If RECORD_ADJUSTMENTs is true, remember how many interval - was prolonged and punt when there are too many. */ - bool merge (const modref_access_node &a, bool record_adjustments) - { - poly_int64 offset1 = 0; - poly_int64 aoffset1 = 0; - poly_int64 new_parm_offset = 0; - - /* We assume that containment was tested earlier. */ - gcc_checking_assert (!contains (a) && !a.contains (*this)); - if (parm_index != MODREF_UNKNOWN_PARM) - { - if (parm_index != a.parm_index) - return false; - if (parm_offset_known) - { - if (!a.parm_offset_known) - return false; - if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1)) - return false; - } - } - /* See if we can merge ranges. */ - if (range_info_useful_p ()) - { - /* In this case we have containment that should be - handled earlier. */ - gcc_checking_assert (a.range_info_useful_p ()); - - /* If a.size is less specified than size, merge only - if intervals are otherwise equivalent. */ - if (known_size_p (size) - && (!known_size_p (a.size) || known_lt (a.size, size))) - { - if (((known_size_p (max_size) || known_size_p (a.max_size)) - && !known_eq (max_size, a.max_size)) - || !known_eq (offset1, aoffset1)) - return false; - update (new_parm_offset, offset1, a.size, max_size, - record_adjustments); - return true; - } - /* If sizes are same, we can extend the interval. */ - if ((known_size_p (size) || known_size_p (a.size)) - && !known_eq (size, a.size)) - return false; - if (known_le (offset1, aoffset1)) - { - if (!known_size_p (max_size) - || known_ge (offset1 + max_size, aoffset1)) - { - update2 (new_parm_offset, offset1, size, max_size, - aoffset1, a.size, a.max_size, - record_adjustments); - return true; - } - } - else if (known_le (aoffset1, offset1)) - { - if (!known_size_p (a.max_size) - || known_ge (aoffset1 + a.max_size, offset1)) - { - update2 (new_parm_offset, offset1, size, max_size, - aoffset1, a.size, a.max_size, - record_adjustments); - return true; - } - } - return false; - } - update (new_parm_offset, offset1, - size, max_size, record_adjustments); - return true; - } - /* Return true if A1 and B1 can be merged with lower informatoin - less than A2 and B2. - Assume that no containment or lossless merging is possible. */ - static bool closer_pair_p (const modref_access_node &a1, - const modref_access_node &b1, - const modref_access_node &a2, - const modref_access_node &b2) - { - /* Merging different parm indexes comes to complete loss - of range info. */ - if (a1.parm_index != b1.parm_index) - return false; - if (a2.parm_index != b2.parm_index) - return true; - /* If parm is known and parm indexes are the same we should - already have containment. */ - gcc_checking_assert (a1.parm_offset_known && b1.parm_offset_known); - gcc_checking_assert (a2.parm_offset_known && b2.parm_offset_known); - - /* First normalize offsets for parm offsets. */ - poly_int64 new_parm_offset, offseta1, offsetb1, offseta2, offsetb2; - if (!a1.combined_offsets (b1, &new_parm_offset, &offseta1, &offsetb1) - || !a2.combined_offsets (b2, &new_parm_offset, &offseta2, &offsetb2)) - gcc_unreachable (); - - - /* Now compute distnace of the intervals. */ - poly_int64 dist1, dist2; - if (known_le (offseta1, offsetb1)) - { - if (!known_size_p (a1.max_size)) - dist1 = 0; - else - dist1 = offsetb1 - offseta1 - a1.max_size; - } - else - { - if (!known_size_p (b1.max_size)) - dist1 = 0; - else - dist1 = offseta1 - offsetb1 - b1.max_size; - } - if (known_le (offseta2, offsetb2)) - { - if (!known_size_p (a2.max_size)) - dist2 = 0; - else - dist2 = offsetb2 - offseta2 - a2.max_size; - } - else - { - if (!known_size_p (b2.max_size)) - dist2 = 0; - else - dist2 = offseta2 - offsetb2 - b2.max_size; - } - /* It may happen that intervals overlap in case size - is different. Preffer the overlap to non-overlap. */ - if (known_lt (dist1, 0) && known_ge (dist2, 0)) - return true; - if (known_lt (dist2, 0) && known_ge (dist1, 0)) - return false; - if (known_lt (dist1, 0)) - /* If both overlaps minimize overlap. */ - return known_le (dist2, dist1); - else - /* If both are disjoint look for smaller distance. */ - return known_le (dist1, dist2); - } - - /* Merge in access A while losing precision. */ - void forced_merge (const modref_access_node &a, bool record_adjustments) - { - if (parm_index != a.parm_index) - { - gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM); - parm_index = MODREF_UNKNOWN_PARM; - return; - } - - /* We assume that containment and lossless merging - was tested earlier. */ - gcc_checking_assert (!contains (a) && !a.contains (*this) - && !merge (a, record_adjustments)); - gcc_checking_assert (parm_offset_known && a.parm_offset_known); - - poly_int64 new_parm_offset, offset1, aoffset1; - if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1)) - { - parm_offset_known = false; - return; - } - gcc_checking_assert (range_info_useful_p () - && a.range_info_useful_p ()); - if (record_adjustments) - adjustments += a.adjustments; - update2 (new_parm_offset, - offset1, size, max_size, - aoffset1, a.size, a.max_size, - record_adjustments); - } + bool operator == (modref_access_node &a) const; + /* Insert A into ACCESSES. Limit size of vector to MAX_ACCESSES and if + RECORD_ADJUSTMENT is true keep track of adjustment counts. + Return 0 if nothing changed, 1 is insertion suceeded and -1 if + failed. */ + static int insert (vec *&accesses, + modref_access_node a, size_t max_accesses, + bool record_adjustments); private: - /* Merge two ranges both starting at parm_offset1 and update THIS - with result. */ - void update2 (poly_int64 parm_offset1, - poly_int64 offset1, poly_int64 size1, poly_int64 max_size1, - poly_int64 offset2, poly_int64 size2, poly_int64 max_size2, - bool record_adjustments) - { - poly_int64 new_size = size1; - - if (!known_size_p (size2) - || known_le (size2, size1)) - new_size = size2; - else - gcc_checking_assert (known_le (size1, size2)); - - if (known_le (offset1, offset2)) - ; - else if (known_le (offset2, offset1)) - { - std::swap (offset1, offset2); - std::swap (max_size1, max_size2); - } - else - gcc_unreachable (); - - poly_int64 new_max_size; - - if (!known_size_p (max_size1)) - new_max_size = max_size1; - else if (!known_size_p (max_size2)) - new_max_size = max_size2; - else - { - new_max_size = max_size2 + offset2 - offset1; - if (known_le (new_max_size, max_size1)) - new_max_size = max_size1; - } - - update (parm_offset1, offset1, - new_size, new_max_size, record_adjustments); - } - /* Given access nodes THIS and A, return true if they - can be done with common parm_offsets. In this case - return parm offset in new_parm_offset, new_offset - which is start of range in THIS and new_aoffset that - is start of range in A. */ - bool combined_offsets (const modref_access_node &a, - poly_int64 *new_parm_offset, - poly_int64 *new_offset, - poly_int64 *new_aoffset) const - { - gcc_checking_assert (parm_offset_known && a.parm_offset_known); - if (known_le (a.parm_offset, parm_offset)) - { - *new_offset = offset - + ((parm_offset - a.parm_offset) - << LOG2_BITS_PER_UNIT); - *new_aoffset = a.offset; - *new_parm_offset = a.parm_offset; - return true; - } - else if (known_le (parm_offset, a.parm_offset)) - { - *new_aoffset = a.offset - + ((a.parm_offset - parm_offset) - << LOG2_BITS_PER_UNIT); - *new_offset = offset; - *new_parm_offset = parm_offset; - return true; - } - else - return false; - } + bool contains (const modref_access_node &) const; + void update (poly_int64, poly_int64, poly_int64, poly_int64, bool); + bool merge (const modref_access_node &, bool); + static bool closer_pair_p (const modref_access_node &, + const modref_access_node &, + const modref_access_node &, + const modref_access_node &); + void forced_merge (const modref_access_node &, bool); + void update2 (poly_int64, poly_int64, poly_int64, poly_int64, + poly_int64, poly_int64, poly_int64, bool); + bool combined_offsets (const modref_access_node &, + poly_int64 *, poly_int64 *, poly_int64 *) const; + static void try_merge_with (vec *&, size_t); }; /* Access node specifying no useful info. */ @@ -489,20 +136,6 @@ struct GTY((user)) modref_ref_node every_access = true; } - /* Verify that list does not contain redundant accesses. */ - void verify () - { - size_t i, i2; - modref_access_node *a, *a2; - - FOR_EACH_VEC_SAFE_ELT (accesses, i, a) - { - FOR_EACH_VEC_SAFE_ELT (accesses, i2, a2) - if (i != i2) - gcc_assert (!a->contains (*a2)); - } - } - /* Insert access with OFFSET and SIZE. Collapse tree if it has more than MAX_ACCESSES entries. If RECORD_ADJUSTMENTs is true avoid too many interval extensions. @@ -514,18 +147,12 @@ struct GTY((user)) modref_ref_node if (every_access) return false; - /* Otherwise, insert a node for the ref of the access under the base. */ - size_t i, j; - modref_access_node *a2; - /* Only the following kind of paramters needs to be tracked. We do not track return slots because they are seen as a direct store in the caller. */ gcc_checking_assert (a.parm_index >= 0 || a.parm_index == MODREF_STATIC_CHAIN_PARM || a.parm_index == MODREF_UNKNOWN_PARM); - if (flag_checking) - verify (); if (!a.useful_p ()) { @@ -537,130 +164,17 @@ struct GTY((user)) modref_ref_node return false; } - FOR_EACH_VEC_SAFE_ELT (accesses, i, a2) - { - if (a2->contains (a)) - return false; - if (a.contains (*a2)) - { - a.adjustments = 0; - a2->parm_index = a.parm_index; - a2->parm_offset_known = a.parm_offset_known; - a2->update (a.parm_offset, a.offset, a.size, a.max_size, - record_adjustments); - try_merge_with (i); - return true; - } - if (a2->merge (a, record_adjustments)) - { - try_merge_with (i); - return true; - } - gcc_checking_assert (!(a == *a2)); - } - - /* If this base->ref pair has too many accesses stored, we will clear - all accesses and bail out. */ - if (accesses && accesses->length () >= max_accesses) + int ret = modref_access_node::insert (accesses, a, max_accesses, + record_adjustments); + if (ret == -1) { - if (max_accesses < 2) - { - collapse (); - if (dump_file) - fprintf (dump_file, - "--param param=modref-max-accesses limit reached;" - " collapsing\n"); - return true; - } - /* Find least harmful merge and perform it. */ - int best1 = -1, best2 = -1; - FOR_EACH_VEC_SAFE_ELT (accesses, i, a2) - { - for (j = i + 1; j < accesses->length (); j++) - if (best1 < 0 - || modref_access_node::closer_pair_p - (*a2, (*accesses)[j], - (*accesses)[best1], - best2 < 0 ? a : (*accesses)[best2])) - { - best1 = i; - best2 = j; - } - if (modref_access_node::closer_pair_p - (*a2, a, - (*accesses)[best1], - best2 < 0 ? a : (*accesses)[best2])) - { - best1 = i; - best2 = -1; - } - } - (*accesses)[best1].forced_merge (best2 < 0 ? a : (*accesses)[best2], - record_adjustments); - /* Check that merging indeed merged ranges. */ - gcc_checking_assert ((*accesses)[best1].contains - (best2 < 0 ? a : (*accesses)[best2])); - if (!(*accesses)[best1].useful_p ()) - { - collapse (); - if (dump_file) - fprintf (dump_file, - "--param param=modref-max-accesses limit reached;" - " collapsing\n"); - return true; - } - if (dump_file && best2 >= 0) - fprintf (dump_file, - "--param param=modref-max-accesses limit reached;" - " merging %i and %i\n", best1, best2); - else if (dump_file) + if (dump_file) fprintf (dump_file, "--param param=modref-max-accesses limit reached;" - " merging with %i\n", best1); - try_merge_with (best1); - if (best2 >= 0) - insert_access (a, max_accesses, record_adjustments); - return 1; + " collapsing\n"); + collapse (); } - a.adjustments = 0; - vec_safe_push (accesses, a); - return true; - } -private: - /* Try to optimize the access list after entry INDEX was modified. */ - void - try_merge_with (size_t index) - { - size_t i; - - for (i = 0; i < accesses->length ();) - if (i != index) - { - bool found = false, restart = false; - modref_access_node *a = &(*accesses)[i]; - modref_access_node *n = &(*accesses)[index]; - - if (n->contains (*a)) - found = true; - if (!found && n->merge (*a, false)) - found = restart = true; - gcc_checking_assert (found || !a->merge (*n, false)); - if (found) - { - accesses->unordered_remove (i); - if (index == accesses->length ()) - { - index = i; - i++; - } - if (restart) - i = 0; - } - else - i++; - } - else - i++; + return ret != 0; } };