@@ -134,11 +134,6 @@ AC_ARG_ENABLE(debug-type-canonicalization,
ENABLE_DEBUG_TYPE_CANONICALIZATION=$enableval,
ENABLE_DEBUG_TYPE_CANONICALIZATION=no)
-AC_ARG_ENABLE(debug-ct-propagation,
- AS_HELP_STRING([--enable-debug-ct-propagation=yes|no],
- [enable debugging of canonical type propagation (default is no)]),
- ENABLE_DEBUG_CT_PROPAGATION=$enableval,
- ENABLE_DEBUG_CT_PROPAGATION=no)
AC_ARG_ENABLE(show-type-use-in-abilint,
AS_HELP_STRING([--enable-show-type-use-in-abilint=yes|no],
@@ -611,15 +606,6 @@ fi
AM_CONDITIONAL(ENABLE_DEBUG_TYPE_CANONICALIZATION, test x$ENABLE_DEBUG_TYPE_CANONICALIZATION = xyes)
-if test x$ENABLE_DEBUG_CT_PROPAGATION = xyes; then
- AC_DEFINE([WITH_DEBUG_CT_PROPAGATION],
- 1,
- [compile support of debugging canonical type propagation])
- AC_MSG_NOTICE([support of debugging canonical type propagation is enabled])
-else
- AC_MSG_NOTICE([support of debugging canonical type propagation is disabled])
-fi
-
dnl Check for the dpkg program
if test x$ENABLE_DEB = xauto -o x$ENABLE_DEB = xyes; then
AC_CHECK_PROG(HAS_DPKG, dpkg, yes, no)
@@ -1297,7 +1283,6 @@ AC_MSG_NOTICE([
Enable abilint --show-type-use <type-id> : ${ENABLE_SHOW_TYPE_USE_IN_ABILINT}
Enable self comparison debugging : ${ENABLE_DEBUG_SELF_COMPARISON}
Enable type canonicalization debugging : ${ENABLE_DEBUG_TYPE_CANONICALIZATION}
- Enable propagated canonical type debugging : ${ENABLE_DEBUG_CT_PROPAGATION}
Enable deb support in abipkgdiff : ${ENABLE_DEB}
Enable GNU tar archive support in abipkgdiff : ${ENABLE_TAR}
Enable bash completion : ${ENABLE_BASH_COMPLETION}
@@ -185,12 +185,6 @@ public:
void
canonicalization_is_done(bool);
- bool
- do_on_the_fly_canonicalization() const;
-
- void
- do_on_the_fly_canonicalization(bool f);
-
bool
decl_only_class_equals_definition() const;
@@ -475,23 +475,12 @@ struct type_base::priv
// representation strings here.
interned_string internal_cached_repr_;
interned_string cached_repr_;
- // The next two data members are used while comparing types during
- // canonicalization. They are useful for the "canonical type
- // propagation" (aka on-the-fly-canonicalization) optimization
- // implementation.
-
- // The set of canonical recursive types this type depends on.
- unordered_set<uintptr_t> depends_on_recursive_type_;
- bool canonical_type_propagated_;
- bool propagated_canonical_type_confirmed_;
priv()
: size_in_bits(),
alignment_in_bits(),
canonical_type_index(),
- naked_canonical_type(),
- canonical_type_propagated_(false),
- propagated_canonical_type_confirmed_(false)
+ naked_canonical_type()
{}
priv(size_t s,
@@ -501,140 +490,8 @@ struct type_base::priv
alignment_in_bits(a),
canonical_type_index(),
canonical_type(c),
- naked_canonical_type(c.get()),
- canonical_type_propagated_(false),
- propagated_canonical_type_confirmed_(false)
+ naked_canonical_type(c.get())
{}
-
- /// Test if the current type depends on recursive type comparison.
- ///
- /// A recursive type T is a type T which has a sub-type that is T
- /// (recursively) itself.
- ///
- /// So this function tests if the current type has a recursive
- /// sub-type or is a recursive type itself.
- ///
- /// @return true if the current type depends on a recursive type.
- bool
- depends_on_recursive_type() const
- {return !depends_on_recursive_type_.empty();}
-
- /// Test if the current type depends on a given recursive type.
- ///
- /// A recursive type T is a type T which has a sub-type that is T
- /// (recursively) itself.
- ///
- /// So this function tests if the current type depends on a given
- /// recursive type.
- ///
- /// @param dependant the type we want to test if the current type
- /// depends on.
- ///
- /// @return true if the current type depends on the recursive type
- /// @dependant.
- bool
- depends_on_recursive_type(const type_base* dependant) const
- {
- return
- (depends_on_recursive_type_.find(reinterpret_cast<uintptr_t>(dependant))
- != depends_on_recursive_type_.end());
- }
-
- /// Set the flag that tells if the current type depends on a given
- /// recursive type.
- ///
- /// A recursive type T is a type T which has asub-type that is T
- /// (recursively) itself.
- ///
- /// So this function tests if the current type depends on a
- /// recursive type.
- ///
- /// @param t the recursive type that current type depends on.
- void
- set_depends_on_recursive_type(const type_base * t)
- {depends_on_recursive_type_.insert(reinterpret_cast<uintptr_t>(t));}
-
- /// Unset the flag that tells if the current type depends on a given
- /// recursive type.
- ///
- /// A recursive type T is a type T which has asub-type that is T
- /// (recursively) itself.
- ///
- /// So this function flags the current type as not being dependant
- /// on a given recursive type.
- ///
- ///
- /// @param t the recursive type to consider.
- void
- set_does_not_depend_on_recursive_type(const type_base *t)
- {depends_on_recursive_type_.erase(reinterpret_cast<uintptr_t>(t));}
-
- /// Flag the current type as not being dependant on any recursive type.
- void
- set_does_not_depend_on_recursive_type()
- {depends_on_recursive_type_.clear();}
-
- /// Test if the type carries a canonical type that is the result of
- /// maybe_propagate_canonical_type(), aka, "canonical type
- /// propagation optimization".
- ///
- /// @return true iff the current type carries a canonical type that
- /// is the result of canonical type propagation.
- bool
- canonical_type_propagated()
- {return canonical_type_propagated_;}
-
- /// Set the flag that says if the type carries a canonical type that
- /// is the result of maybe_propagate_canonical_type(), aka,
- /// "canonical type propagation optimization".
- ///
- /// @param f true iff the current type carries a canonical type that
- /// is the result of canonical type propagation.
- void
- set_canonical_type_propagated(bool f)
- {canonical_type_propagated_ = f;}
-
- /// Getter of the property propagated-canonical-type-confirmed.
- ///
- /// If canonical_type_propagated() returns true, then this property
- /// says if the propagated canonical type has been confirmed or not.
- /// If it hasn't been confirmed, then it means it can still
- /// cancelled.
- ///
- /// @return true iff the propagated canonical type has been
- /// confirmed.
- bool
- propagated_canonical_type_confirmed() const
- {return propagated_canonical_type_confirmed_;}
-
- /// Setter of the property propagated-canonical-type-confirmed.
- ///
- /// If canonical_type_propagated() returns true, then this property
- /// says if the propagated canonical type has been confirmed or not.
- /// If it hasn't been confirmed, then it means it can still
- /// cancelled.
- ///
- /// @param f If this is true then the propagated canonical type has
- /// been confirmed.
- void
- set_propagated_canonical_type_confirmed(bool f)
- {propagated_canonical_type_confirmed_ = f;}
-
- /// If the current canonical type was set as the result of the
- /// "canonical type propagation optimization", then clear it.
- bool
- clear_propagated_canonical_type()
- {
- if (canonical_type_propagated_ && !propagated_canonical_type_confirmed_)
- {
- canonical_type.reset();
- naked_canonical_type = nullptr;
- set_canonical_type_propagated(false);
- canonical_type_index = 0;
- return true;
- }
- return false;
- }
}; // end struct type_base::priv
bool
@@ -739,28 +596,9 @@ struct environment::priv
// -------- -------------
// | T_R | R_OP0 | R_OP1 | <-- this goes into right_type_comp_operands_;
//
- // This "stack of operands of the current type comparison, during
- // type canonicalization" is used in the context of the @ref
- // OnTheFlyCanonicalization optimization. It's used to detect if a
- // sub-type of the type being canonicalized depends on a recursive
- // type.
vector<const type_base*> left_type_comp_operands_;
vector<const type_base*> right_type_comp_operands_;
- // Vector of types that protentially received propagated canonical types.
- // If the canonical type propagation is confirmed, the potential
- // canonical types must be promoted as canonical types. Otherwise if
- // the canonical type propagation is cancelled, the canonical types
- // must be cleared.
- pointer_set types_with_non_confirmed_propagated_ct_;
- pointer_set recursive_types_;
-#ifdef WITH_DEBUG_CT_PROPAGATION
- // Set of types which propagated canonical type has been cleared
- // during the "canonical type propagation optimization" phase. Those
- // types are tracked in this set to ensure that they are later
- // canonicalized. This means that at the end of the
- // canonicalization process, this set must be empty.
- mutable pointer_set types_with_cleared_propagated_ct_;
-#endif
+
#ifdef WITH_DEBUG_SELF_COMPARISON
// This is used for debugging purposes.
// When abidw is used with the option --debug-abidiff, some
@@ -782,7 +620,6 @@ struct environment::priv
unordered_map<uintptr_t, string> pointer_type_id_map_;
#endif
bool canonicalization_is_done_;
- bool do_on_the_fly_canonicalization_;
bool decl_only_class_equals_definition_;
bool use_enum_binary_only_equality_;
bool allow_type_comparison_results_caching_;
@@ -810,7 +647,6 @@ struct environment::priv
priv()
: canonicalization_is_done_(),
- do_on_the_fly_canonicalization_(true),
decl_only_class_equals_definition_(false),
use_enum_binary_only_equality_(true),
allow_type_comparison_results_caching_(false),
@@ -907,8 +743,8 @@ struct environment::priv
type_comparison_result_type::const_iterator it =
type_comparison_results_cache_.find
- (std::make_pair(reinterpret_cast<uint64_t>(&first),
- reinterpret_cast<uint64_t>(&second)));
+ (std::make_pair(reinterpret_cast<uint64_t>(&first),
+ reinterpret_cast<uint64_t>(&second)));
if (it == type_comparison_results_cache_.end())
return false;
@@ -966,463 +802,6 @@ struct environment::priv
right_type_comp_operands_.pop_back();
}
- /// Mark all the types that comes after a certain one as NOT being
- /// eligible for the canonical type propagation optimization.
- ///
- /// @param type the type that represents the "marker type". All
- /// types after this one will be marked as being NON-eligible to
- /// the canonical type propagation optimization.
- ///
- /// @param types the set of types to consider. In that vector, all
- /// types that come after @p type are going to be marked as being
- /// non-eligible to the canonical type propagation optimization.
- ///
- /// @return true iff the operation was successful.
- bool
- mark_dependant_types(const type_base* type,
- vector<const type_base*>& types)
- {
- bool found = false;
- for (auto t : types)
- {
- if (!found
- && (reinterpret_cast<uintptr_t>(t)
- == reinterpret_cast<uintptr_t>(type)))
- {
- found = true;
- continue;
- }
- else if (found)
- t->priv_->set_depends_on_recursive_type(type);
- }
- return found;
- }
-
- /// In the stack of the current types being compared (as part of
- /// type canonicalization), mark all the types that comes after a
- /// certain one as NOT being eligible to the canonical type
- /// propagation optimization.
- ///
- /// For a starter, please read about the @ref
- /// OnTheFlyCanonicalization, aka, "canonical type propagation
- /// optimization".
- ///
- /// To implement that optimization, we need, among other things to
- /// maintain stack of the types (and their sub-types) being
- /// currently compared as part of type canonicalization.
- ///
- /// Note that we only consider the type that is the right-hand-side
- /// operand of the comparison because it's that one that is being
- /// canonicalized and thus, that is not yet canonicalized.
- ///
- /// The reason why a type is deemed NON-eligible to the canonical
- /// type propagation optimization is that it "depends" on
- /// recursively present type. Let me explain.
- ///
- /// Suppose we have a type T that has sub-types named ST0 and ST1.
- /// Suppose ST1 itself has a sub-type that is T itself. In this
- /// case, we say that T is a recursive type, because it has T
- /// (itself) as one of its sub-types:
- ///
- /// T
- /// +-- ST0
- /// |
- /// +-- ST1
- /// +
- /// |
- /// +-- T
- ///
- /// ST1 is said to "depend" on T because it has T as a sub-type.
- /// But because T is recursive, then ST1 is said to depend on a
- /// recursive type. Notice however that ST0 does not depend on any
- /// recursive type.
- ///
- /// When we are at the point of comparing the sub-type T of ST1
- /// against its counterpart, the stack of the right-hand-side
- /// operands of the type canonicalization is going to look like
- /// this:
- ///
- /// | T | ST1 |
- ///
- /// We don't add the type T to the stack as we detect that T was
- /// already in there (recursive cycle).
- ///
- /// So, this function will basically mark ST1 as being NON-eligible
- /// to being the target of canonical type propagation.
- ///
- /// @param right the right-hand-side operand of the type comparison.
- ///
- /// @return true iff the operation was successful.
- bool
- mark_dependant_types_compared_until(const type_base* right)
- {
- bool result = false;
-
- result |=
- mark_dependant_types(right,
- right_type_comp_operands_);
- recursive_types_.insert(reinterpret_cast<uintptr_t>(right));
- return result;
- }
-
- /// Test if a type is a recursive one.
- ///
- /// @param t the type to consider.
- ///
- /// @return true iff @p t is recursive.
- bool
- is_recursive_type(const type_base* t)
- {
- return (recursive_types_.find(reinterpret_cast<uintptr_t>(t))
- != recursive_types_.end());
- }
-
-
- /// Unflag a type as being recursive
- ///
- /// @param t the type to unflag
- void
- set_is_not_recursive(const type_base* t)
- {recursive_types_.erase(reinterpret_cast<uintptr_t>(t));}
-
- /// Propagate the canonical type of a type to another one.
- ///
- /// @param src the type to propagate the canonical type from.
- ///
- /// @param dest the type to propagate the canonical type of @p src
- /// to.
- ///
- /// @return bool iff the canonical was propagated.
- bool
- propagate_ct(const type_base& src, const type_base& dest)
- {
- type_base_sptr canonical = src.get_canonical_type();
- ABG_ASSERT(canonical);
- dest.priv_->canonical_type = canonical;
- dest.priv_->naked_canonical_type = canonical.get();
- dest.priv_->set_canonical_type_propagated(true);
- dest.priv_->canonical_type_index = canonical->priv_->canonical_type_index;
-#ifdef WITH_DEBUG_CT_PROPAGATION
- // If dest was previously a type which propagated canonical type
- // has been cleared, let the book-keeping system know.
- erase_type_with_cleared_propagated_canonical_type(&dest);
-#endif
- return true;
- }
-
- /// Mark a set of types that have been the target of canonical type
- /// propagation and that depend on a recursive type as being
- /// permanently canonicalized.
- ///
- /// To understand the sentence above, please read the description of
- /// type canonicalization and especially about the "canonical type
- /// propagation optimization" at @ref OnTheFlyCanonicalization, in
- /// the src/abg-ir.cc file.
- void
- confirm_ct_propagation_for_types_dependant_on(const type_base* dependant_type)
- {
- pointer_set to_remove;
- for (auto i : types_with_non_confirmed_propagated_ct_)
- {
- type_base *t = reinterpret_cast<type_base*>(i);
- t->priv_->set_does_not_depend_on_recursive_type(dependant_type);
- if (!t->priv_->depends_on_recursive_type())
- {
- to_remove.insert(i);
- t->priv_->set_propagated_canonical_type_confirmed(true);
- ABG_ASSERT(t->priv_->canonical_type_propagated_
- && t->priv_->naked_canonical_type);
-#ifdef WITH_DEBUG_SELF_COMPARISON
- check_abixml_canonical_type_propagation_during_self_comp(t);
-#endif
- }
- }
-
- for (auto i : to_remove)
- types_with_non_confirmed_propagated_ct_.erase(i);
- }
-
- /// Mark a type that has been the target of canonical type
- /// propagation as being permanently canonicalized.
- ///
- /// This function also marks the set of types that have been the
- /// target of canonical type propagation and that depend on a
- /// recursive type as being permanently canonicalized.
- ///
- /// To understand the sentence above, please read the description of
- /// type canonicalization and especially about the "canonical type
- /// propagation optimization" at @ref OnTheFlyCanonicalization, in
- /// the src/abg-ir.cc file.
- void
- confirm_ct_propagation(const type_base*t)
- {
- if (!t || t->priv_->propagated_canonical_type_confirmed())
- return;
-
- const environment& env = t->get_environment();
-
- env.priv_->confirm_ct_propagation_for_types_dependant_on(t);
- t->priv_->set_does_not_depend_on_recursive_type();
- env.priv_->remove_from_types_with_non_confirmed_propagated_ct(t);
- env.priv_->set_is_not_recursive(t);
- t->priv_->set_propagated_canonical_type_confirmed(true);
- ABG_ASSERT(t->priv_->canonical_type_propagated_
- && t->priv_->naked_canonical_type);
-#ifdef WITH_DEBUG_SELF_COMPARISON
- check_abixml_canonical_type_propagation_during_self_comp(t);
-#endif
- }
-
- /// Mark all the types that have been the target of canonical type
- /// propagation and that are not yet confirmed as being permanently
- /// canonicalized (aka confirmed).
- ///
- /// To understand the sentence above, please read the description of
- /// type canonicalization and especially about the "canonical type
- /// propagation optimization" at @ref OnTheFlyCanonicalization, in
- /// the src/abg-ir.cc file.
- void
- confirm_ct_propagation()
- {
- for (auto i : types_with_non_confirmed_propagated_ct_)
- {
- type_base *t = reinterpret_cast<type_base*>(i);
- t->priv_->set_does_not_depend_on_recursive_type();
- t->priv_->set_propagated_canonical_type_confirmed(true);
- ABG_ASSERT(t->priv_->canonical_type_propagated_
- && t->priv_->naked_canonical_type);
-#ifdef WITH_DEBUG_SELF_COMPARISON
- check_abixml_canonical_type_propagation_during_self_comp(t);
-#endif
- }
- types_with_non_confirmed_propagated_ct_.clear();
- }
-
-#ifdef WITH_DEBUG_CT_PROPAGATION
- /// Getter for the set of types which propagated canonical type has
- /// been cleared during the "canonical type propagation
- /// optimization" phase. Those types are tracked in this set to
- /// ensure that they are later canonicalized. This means that at
- /// the end of the canonicalization process, this set must be empty.
- ///
- /// @return the set of types which propagated canonical type has
- /// been cleared.
- const pointer_set&
- types_with_cleared_propagated_ct() const
- {return types_with_cleared_propagated_ct_;}
-
- /// Getter for the set of types which propagated canonical type has
- /// been cleared during the "canonical type propagation
- /// optimization" phase. Those types are tracked in this set to
- /// ensure that they are later canonicalized. This means that at
- /// the end of the canonicalization process, this set must be empty.
- ///
- /// @return the set of types which propagated canonical type has
- /// been cleared.
- pointer_set&
- types_with_cleared_propagated_ct()
- {return types_with_cleared_propagated_ct_;}
-
- /// Record a type which propagated canonical type has been cleared
- /// during the "canonical type propagation optimization phase".
- ///
- /// @param t the type to record.
- void
- record_type_with_cleared_propagated_canonical_type(const type_base* t)
- {
- uintptr_t ptr = reinterpret_cast<uintptr_t>(t);
- types_with_cleared_propagated_ct_.insert(ptr);
- }
-
- /// Erase a type (which propagated canonical type has been cleared
- /// during the "canonical type propagation optimization phase") from
- /// the set of types that have been recorded by the invocation of
- /// record_type_with_cleared_propagated_canonical_type()
- ///
- /// @param t the type to erase from the set.
- void
- erase_type_with_cleared_propagated_canonical_type(const type_base* t)
- {
- uintptr_t ptr = reinterpret_cast<uintptr_t>(t);
- types_with_cleared_propagated_ct_.erase(ptr);
- }
-#endif //WITH_DEBUG_CT_PROPAGATION
-
- /// Collect the types that depends on a given "target" type.
- ///
- /// Walk a set of types and if they depend directly or indirectly on
- /// a "target" type, then collect them into a set.
- ///
- /// @param target the target type to consider.
- ///
- /// @param types the types to walk to detect those who depend on @p
- /// target.
- ///
- /// @return true iff one or more type from @p types is found to
- /// depend on @p target.
- bool
- collect_types_that_depends_on(const type_base *target,
- const pointer_set& types,
- pointer_set& collected)
- {
- bool result = false;
- for (const auto i : types)
- {
- // First avoid infinite loop if we've already collected the
- // current type.
- if (collected.find(i) != collected.end())
- continue;
-
- type_base *t = reinterpret_cast<type_base*>(i);
- if (t->priv_->depends_on_recursive_type(target))
- {
- collected.insert(i);
- collect_types_that_depends_on(t, types, collected);
- result = true;
- }
- }
- return result;
- }
-
- /// Reset the canonical type (set it nullptr) of a set of types that
- /// have been the target of canonical type propagation and that
- /// depend on a given recursive type.
- ///
- /// Once the canonical type of a type in that set is reset, the type
- /// is marked as being non-dependant on a recursive type anymore.
- ///
- /// To understand the sentences above, please read the description
- /// of type canonicalization and especially about the "canonical
- /// type propagation optimization" at @ref OnTheFlyCanonicalization,
- /// in the src/abg-ir.cc file.
- ///
- /// @param target if a type which has been subject to the canonical
- /// type propagation optimizationdepends on a this target type, then
- /// cancel its canonical type.
- void
- cancel_ct_propagation_for_types_dependant_on(const type_base* target)
- {
- pointer_set to_remove;
- collect_types_that_depends_on(target,
- types_with_non_confirmed_propagated_ct_,
- to_remove);
-
- for (auto i : to_remove)
- {
- type_base *t = reinterpret_cast<type_base*>(i);
- ABG_ASSERT(t->get_environment().priv_->is_recursive_type(t)
- || t->priv_->depends_on_recursive_type());
- type_base_sptr canonical = t->priv_->canonical_type.lock();
- if (canonical)
- {
- clear_propagated_canonical_type(t);
- t->priv_->set_does_not_depend_on_recursive_type();
- }
- }
-
- for (auto i : to_remove)
- types_with_non_confirmed_propagated_ct_.erase(i);
- }
-
- /// Reset the canonical type (set it nullptr) of a type that has
- /// been the target of canonical type propagation.
- ///
- /// This also resets the propagated canonical type of the set of
- /// types that depends on a given recursive type.
- ///
- /// Once the canonical type of a type in that set is reset, the type
- /// is marked as being non-dependant on a recursive type anymore.
- ///
- /// To understand the sentences above, please read the description
- /// of type canonicalization and especially about the "canonical
- /// type propagation optimization" at @ref OnTheFlyCanonicalization,
- /// in the src/abg-ir.cc file.
- ///
- /// @param target if a type which has been subject to the canonical
- /// type propagation optimizationdepends on a this target type, then
- /// cancel its canonical type.
- void
- cancel_ct_propagation(const type_base* t)
- {
- if (!t)
- return;
-
- const environment& env = t->get_environment();
- env.priv_->cancel_ct_propagation_for_types_dependant_on(t);
- // This cannot carry any tentative canonical type at this
- // point.
- clear_propagated_canonical_type(t);
- // Reset the marking of the type as it no longer carries a
- // tentative canonical type that might be later canceled.
- t->priv_->set_does_not_depend_on_recursive_type();
- env.priv_->remove_from_types_with_non_confirmed_propagated_ct(t);
- env.priv_->clear_type_comparison_results_cache();
- }
-
- /// Clear the propagated canonical type of a given type.
- ///
- /// This function also updates the book-keeping of the set of types
- /// which propagated canonical types have been cleared.
- ///
- /// Please note that at the end of the canonicalization of all the
- /// types in the system, all the types which propagated canonical
- /// type has been cleared must be canonicalized.
- ///
- /// @param t the type to
- void
- clear_propagated_canonical_type(const type_base *t)
- {
- if (t->priv_->clear_propagated_canonical_type())
- {
-#ifdef WITH_DEBUG_CT_PROPAGATION
- // let the book-keeping system know that t has its propagated
- // canonical type cleared.
- record_type_with_cleared_propagated_canonical_type(t)
-#endif
- ;
- }
- }
-
- /// Add a given type to the set of types that have been
- /// non-confirmed subjects of the canonical type propagation
- /// optimization.
- ///
- /// @param t the dependant type to consider.
- void
- add_to_types_with_non_confirmed_propagated_ct(const type_base *t)
- {
- uintptr_t v = reinterpret_cast<uintptr_t>(t);
- types_with_non_confirmed_propagated_ct_.insert(v);
- }
-
- /// Remove a given type from the set of types that have been
- /// non-confirmed subjects of the canonical type propagation
- /// optimization.
- ///
- /// @param dependant the dependant type to consider.
- void
- remove_from_types_with_non_confirmed_propagated_ct(const type_base* dependant)
- {
- uintptr_t i = reinterpret_cast<uintptr_t>(dependant);
- types_with_non_confirmed_propagated_ct_.erase(i);
- }
-
- /// Cancel the propagated canonical types of all the types which
- /// propagated canonical type have not yet been confirmed.
- void
- cancel_all_non_confirmed_propagated_canonical_types()
- {
- vector<uintptr_t> to_erase;
- for (auto i : types_with_non_confirmed_propagated_ct_)
- to_erase.push_back(i);
-
- for (auto i : to_erase)
- {
- type_base *t = reinterpret_cast<type_base*>(i);
- cancel_ct_propagation(t);
- }
- }
-
#ifdef WITH_DEBUG_SELF_COMPARISON
const unordered_map<string, uintptr_t>&
@@ -2102,18 +1481,6 @@ canonicalize_types(const input_iterator& begin,
canonicalize(deref(t));
}
-
-#ifdef WITH_DEBUG_CT_PROPAGATION
- // Then now, make sure that all types -- which propagated canonical
- // type has been cleared -- have been canonicalized. In other
- // words, the set of types which have been recorded because their
- // propagated canonical type has been cleared must be empty.
- const environment& env = deref(begin)->get_environment();
- pointer_set to_canonicalize =
- env.priv_->types_with_cleared_propagated_ct();
-
- ABG_ASSERT(to_canonicalize.empty());
-#endif // WITH_DEBUG_CT_PROPAGATION
}
/// Hash and canonicalize a sequence of types.
@@ -297,8 +297,6 @@ void
pop_composite_type_comparison_operands(const type_base& left,
const type_base& right);
-bool
-mark_dependant_types_compared_until(const type_base &r);
/// Push a pair of operands on the stack of operands of the current
/// type comparison, during type canonicalization.
@@ -338,71 +336,6 @@ pop_composite_type_comparison_operands(const type_base& left,
env.priv_->pop_composite_type_comparison_operands(&left, &right);
}
-/// In the stack of the current types being compared (as part of type
-/// canonicalization), mark all the types that comes after a certain
-/// one as NOT being eligible to the canonical type propagation
-/// optimization.
-///
-/// For a starter, please read about the @ref
-/// OnTheFlyCanonicalization, aka, "canonical type propagation
-/// optimization".
-///
-/// To implement that optimization, we need, among other things to
-/// maintain stack of the types (and their sub-types) being
-/// currently compared as part of type canonicalization.
-///
-/// Note that we only consider the type that is the right-hand-side
-/// operand of the comparison because it's that one that is being
-/// canonicalized and thus, that is not yet canonicalized.
-///
-/// The reason why a type is deemed NON-eligible to the canonical
-/// type propagation optimization is that it "depends" on
-/// recursively present type. Let me explain.
-///
-/// Suppose we have a type T that has sub-types named ST0 and ST1.
-/// Suppose ST1 itself has a sub-type that is T itself. In this
-/// case, we say that T is a recursive type, because it has T
-/// (itself) as one of its sub-types:
-///
-/// T
-/// +-- ST0
-/// |
-/// +-- ST1
-/// +
-/// |
-/// +-- T
-///
-/// ST1 is said to "depend" on T because it has T as a sub-type.
-/// But because T is recursive, then ST1 is said to depend on a
-/// recursive type. Notice however that ST0 does not depend on any
-/// recursive type.
-///
-/// When we are at the point of comparing the sub-type T of ST1
-/// against its counterpart, the stack of the right-hand-side
-/// operands of the type canonicalization is going to look like
-/// this:
-///
-/// | T | ST1 |
-///
-/// We don't add the type T to the stack as we detect that T was
-/// already in there (recursive cycle).
-///
-/// So, this function will basically mark ST1 as being NON-eligible
-/// to being the target of canonical type propagation, by marking ST1
-/// as being dependant on T.
-///
-/// @param right the right-hand-side operand of the type comparison.
-///
-/// @return true iff the operation was successful.
-bool
-mark_dependant_types_compared_until(const type_base &r)
-{
- const environment& env = r.get_environment();
- if (env.do_on_the_fly_canonicalization())
- return env.priv_->mark_dependant_types_compared_until(&r);
- return false;
-}
-
/// Getter of the canonical type index of a given type.
///
/// @param t the type to consider.
@@ -1037,10 +970,7 @@ is_comparison_cycle_detected(const class_decl& l, const class_decl& r)
do \
{ \
if (is_comparison_cycle_detected(l, r)) \
- { \
- mark_dependant_types_compared_until(r); \
- return true; \
- } \
+ return true; \
} \
while(false)
@@ -1121,111 +1051,20 @@ unmark_types_as_being_compared(const class_decl& l, const class_decl &r)
/// The function does the necessary book keeping before returning the
/// result of the comparison of two (sub) types.
///
-/// The book-keeping done is in the following
-/// areas:
-///
-/// * Management of the Canonical Type Propagation optimization
-/// * type comparison cycle detection
+/// The book-keeping done is essentially about type comparison cycle detection.
///
/// @param l the left-hand-side operand of the type comparison
///
/// @param r the right-hand-side operand of the type comparison
///
-/// @param propagate_canonical_type if true, it means the function
-/// performs the @ref OnTheFlyCanonicalization, aka, "canonical type
-/// propagation optimization".
-///
/// @param value the result of the comparison of @p l and @p r.
///
/// @return the value @p value.
template<typename T>
bool
-return_comparison_result(T& l, T& r, bool value,
- bool propagate_canonical_type = true)
+return_comparison_result(T& l, T& r, bool value)
{
- if (propagate_canonical_type && (value == true))
- maybe_propagate_canonical_type(l, r);
-
unmark_types_as_being_compared(l, r);
-
- const environment& env = l.get_environment();
- if (env.do_on_the_fly_canonicalization())
- // We are instructed to perform the "canonical type propagation"
- // optimization, making 'r' to possibly get the canonical type of
- // 'l' if it has one. This mostly means that we are currently
- // canonicalizing the type that contain the subtype provided in
- // the 'r' argument.
- {
- if (value == true
- && (is_type(&r)->priv_->depends_on_recursive_type()
- || env.priv_->is_recursive_type(&r))
- && is_type(&r)->priv_->canonical_type_propagated()
- && !is_type(&r)->priv_->propagated_canonical_type_confirmed()
- && !env.priv_->right_type_comp_operands_.empty())
- {
- // Track the object 'r' for which the propagated canonical
- // type might be re-initialized if the current comparison
- // eventually fails.
- env.priv_->add_to_types_with_non_confirmed_propagated_ct(is_type(&r));
- }
- else if (value == true
- && env.priv_->right_type_comp_operands_.empty()
- && is_type(&r)->priv_->canonical_type_propagated()
- && !is_type(&r)->priv_->propagated_canonical_type_confirmed())
- {
- // The type provided in the 'r' argument is the type that is
- // being canonicalized; 'r' is not a mere subtype being
- // compared, it's the whole type being canonicalized. And
- // its canonicalization has just succeeded.
- //
- // Let's confirm the canonical type resulting from the
- // "canonical type propagation" optimization.
- env.priv_->confirm_ct_propagation(&r);
- }
- else if (value == true
- && is_type(&r)->priv_->canonical_type_propagated()
- && !is_type(&r)->priv_->propagated_canonical_type_confirmed())
- // In any other case, we are not sure if propagated types
- // should be confirmed yet. So let's mark them as such.
- env.priv_->add_to_types_with_non_confirmed_propagated_ct(is_type(&r));
- else if (value == false)
- {
- // The comparison of the current sub-type failed. So all
- // the with non-confirmed propagated types (those in
- // env.prix_->types_with_non_confirmed_propagated_ct_)
- // should see their tentatively propagated canonical type
- // cancelled.
- env.priv_->cancel_all_non_confirmed_propagated_canonical_types();
- }
- }
-
- // If we reached this point with value == true and the stack of
- // types being compared is empty, then it means that the type pair
- // that was at the bottom of the stack is now fully compared.
- //
- // It follows that all types that were target of canonical type
- // propagation can now see their tentative canonical type be
- // confirmed for real.
- if (value == true
- && env.priv_->right_type_comp_operands_.empty()
- && !env.priv_->types_with_non_confirmed_propagated_ct_.empty())
- // So the comparison is completely done and there are some
- // types for which their propagated canonical type is sitll
- // considered not confirmed. As the comparison did yield true, we
- // shall now confirm the propagation for all those types.
- env.priv_->confirm_ct_propagation();
-
-#ifdef WITH_DEBUG_SELF_COMPARISON
- if (value == false && env.priv_->right_type_comp_operands_.empty())
- {
- for (const auto i : env.priv_->types_with_non_confirmed_propagated_ct_)
- {
- type_base *t = reinterpret_cast<type_base*>(i);
- env.priv_->check_abixml_canonical_type_propagation_during_self_comp(t);
- }
- }
-#endif
-
ABG_RETURN(value);
}
@@ -3499,24 +3338,6 @@ void
environment::canonicalization_is_done(bool f)
{priv_->canonicalization_is_done_ = f;}
-/// Getter for the "on-the-fly-canonicalization" flag.
-///
-/// @return true iff @ref OnTheFlyCanonicalization
-/// "on-the-fly-canonicalization" is to be performed during
-/// comparison.
-bool
-environment::do_on_the_fly_canonicalization() const
-{return priv_->do_on_the_fly_canonicalization_;}
-
-/// Setter for the "on-the-fly-canonicalization" flag.
-///
-/// @param f If this is true then @ref OnTheFlyCanonicalization
-/// "on-the-fly-canonicalization" is to be performed during
-/// comparison.
-void
-environment::do_on_the_fly_canonicalization(bool f)
-{priv_->do_on_the_fly_canonicalization_ = f;}
-
/// Getter of the "decl-only-class-equals-definition" flag.
///
/// Usually, a declaration-only class named 'struct foo' compares
@@ -15100,10 +14921,6 @@ global_scope::~global_scope()
{
}
-static bool
-maybe_propagate_canonical_type(const type_base& lhs_type,
- const type_base& rhs_type);
-
/// Test if two types are eligible to the "Linux Kernel Fast Type
/// Comparison Optimization", a.k.a LKFTCO.
///
@@ -15313,11 +15130,7 @@ compare_canonical_type_against_candidate(const type_base& canonical_type,
// resolved to any of the two definitions of struct S.
bool saved_decl_only_class_equals_definition =
env.decl_only_class_equals_definition();
- // Now that we do hash types and use the hash in comparisons, we
- // don't do canonical-type-propagation anymore, at least for now.
- // Let's see how we fare in terms of performance and hope we don't
- // need this optimization moving foward.
- env.do_on_the_fly_canonicalization(false);
+
// Compare types by considering that decl-only classes don't
// equal their definition.
env.decl_only_class_equals_definition(false);
@@ -15331,7 +15144,6 @@ compare_canonical_type_against_candidate(const type_base& canonical_type,
// flags.
env.priv_->clear_type_comparison_results_cache();
env.priv_->allow_type_comparison_results_caching(false);
- env.do_on_the_fly_canonicalization(false);
env.decl_only_class_equals_definition
(saved_decl_only_class_equals_definition);
return equal;
@@ -15884,21 +15696,6 @@ canonicalize(type_base_sptr t, bool do_log, bool show_stats)
if (!t->priv_->canonical_type_index)
t->priv_->canonical_type_index = canonical->priv_->canonical_type_index;
- // So this type is now canonicalized.
- //
- // It means that:
- //
- // 1/ Either the canonical type was not propagated during the
- // comparison of another type that was being canonicalized
- //
- // 2/ Or the canonical type has been propagated during the
- // comparison of another type that was being canonicalized and
- // that propagated canonical type has been confirmed, because
- // it was depending on a recursive type which comparison
- // succeeded.
- ABG_ASSERT(!t->priv_->canonical_type_propagated()
- || t->priv_->propagated_canonical_type_confirmed());
-
if (class_decl_sptr cl = is_class_type(t))
if (type_base_sptr d = is_type(cl->get_earlier_declaration()))
if ((canonical = d->get_canonical_type()))
@@ -15934,18 +15731,6 @@ canonicalize(type_base_sptr t, bool do_log, bool show_stats)
// emitted. This can be the case for the result of the
// function strip_typedef, for instance.
}
-
-#ifdef WITH_DEBUG_CT_PROPAGATION
- // Update the book-keeping of the set of the types which
- // propagated canonical type has been cleared.
- //
- // If this type 't' which has just been canonicalized was
- // previously in the set of types which propagated canonical
- // type has been cleared, then remove it from that set because
- // its canonical type is now computed and definitely set.
- const environment& env = t->get_environment();
- env.priv_->erase_type_with_cleared_propagated_canonical_type(t.get());
-#endif
}
t->on_canonical_type_set();
@@ -24211,9 +23996,8 @@ equals(const class_or_union& l, const class_or_union& r, change_kind* k)
//overload for class_decl and union_decl because this one ( the
//equal overload for class_or_union) is just a sub-routine of these
//two above.
-#define RETURN(value) \
- return return_comparison_result(l, r, value, \
- /*propagate_canonical_type=*/false);
+#define RETURN(value) \
+ return return_comparison_result(l, r, value);
RETURN_TRUE_IF_COMPARISON_CYCLE_DETECTED(l, r);
@@ -24398,135 +24182,6 @@ copy_member_function(const class_or_union_sptr& t, const method_decl* method)
// </class_or_union definitions>
-/// @defgroup OnTheFlyCanonicalization On-the-fly Canonicalization
-/// @{
-///
-/// This optimization is also known as "canonical type propagation".
-///
-/// During the canonicalization of a type T (which doesn't yet have a
-/// canonical type), T is compared structurally (member-wise) against
-/// a type C which already has a canonical type. The comparison
-/// expression is C == T.
-///
-/// During that structural comparison, if a subtype of C (which also
-/// already has a canonical type) is structurally compared to a
-/// subtype of T (which doesn't yet have a canonical type) and if they
-/// are equal, then we can deduce that the canonical type of the
-/// subtype of C is the canonical type of the subtype of C.
-///
-/// Thus, we can canonicalize the sub-type of the T, during the
-/// canonicalization of T itself. That canonicalization of the
-/// sub-type of T is what we call the "on-the-fly canonicalization".
-/// It's on the fly because it happens during a comparison -- which
-/// itself happens during the canonicalization of T.
-///
-/// For now this on-the-fly canonicalization only happens when
-/// comparing @ref class_decl and @ref function_type.
-///
-/// Note however that there is a case when a type is *NOT* eligible to
-/// this canonical type propagation optimization.
-///
-/// The reason why a type is deemed NON-eligible to the canonical type
-/// propagation optimization is that it "depends" on recursively
-/// present type. Let me explain.
-///
-/// Suppose we have a type T that has sub-types named ST0 and ST1.
-/// Suppose ST1 itself has a sub-type that is T itself. In this case,
-/// we say that T is a recursive type, because it has T (itself) as
-/// one of its sub-types:
-///
-/// <PRE>
-/// T
-/// +-- ST0
-/// |
-/// +-- ST1
-/// | +
-/// | |
-/// | +-- T
-/// |
-/// +-- ST2
-/// </PRE>
-///
-/// ST1 is said to "depend" on T because it has T as a sub-type. But
-/// because T is recursive, then ST1 is said to depend on a recursive
-/// type. Notice however that ST0 does not depend on any recursive
-/// type.
-///
-/// Now suppose we are comparing T to a type T' that has the same
-/// structure with sub-types ST0', ST1' and ST2'. During the
-/// comparison of ST1 against ST1', their sub-type T is compared
-/// against T'. Because T (resp. T') is a recursive type that is
-/// already being compared, the comparison of T against T' (as a
-/// subtypes of ST1 and ST1') returns true, meaning they are
-/// considered equal. This is done so that we don't enter an infinite
-/// recursion.
-///
-/// That means ST1 is also deemed equal to ST1'. If we are in the
-/// course of the canonicalization of T' and thus if T (as well as as
-/// all of its sub-types) is already canonicalized, then the canonical
-/// type propagation optimization will make us propagate the canonical
-/// type of ST1 onto ST1'. So the canonical type of ST1' will be
-/// equal to the canonical type of ST1 as a result of that
-/// optmization.
-///
-/// But then, later down the road, when ST2 is compared against ST2',
-/// let's suppose that we find out that they are different. Meaning
-/// that ST2 != ST2'. This means that T != T', i.e, the
-/// canonicalization of T' failed for now. But most importantly, it
-/// means that the propagation of the canonical type of ST1 to ST1'
-/// must now be invalidated. Meaning, ST1' must now be considered as
-/// not having any canonical type.
-///
-/// In other words, during type canonicalization, if ST1' depends on a
-/// recursive type T', its propagated canonical type must be
-/// invalidated (set to nullptr) if T' appears to be different from T,
-/// a.k.a, the canonicalization of T' temporarily failed.
-///
-/// This means that any sub-type that depends on recursive types and
-/// that has been the target of the canonical type propagation
-/// optimization must be tracked. If the dependant recursive type
-/// fails its canonicalization, then the sub-type being compared must
-/// have its propagated canonical type cleared. In other words, its
-/// propagated canonical type must be cancelled.
-///
-/// @}
-
-
-/// If on-the-fly canonicalization is turned on, then this function
-/// sets the canonical type of its second parameter to the canonical
-/// type of the first parameter.
-///
-/// @param lhs_type the type which canonical type to propagate.
-///
-/// @param rhs_type the type which canonical type to set.
-static bool
-maybe_propagate_canonical_type(const type_base& lhs_type,
- const type_base& rhs_type)
-{
- const environment& env = lhs_type.get_environment();
-#if WITH_DEBUG_TYPE_CANONICALIZATION
- if (!env.priv_->use_canonical_type_comparison_)
- return false;
-#endif
-
- if (env.do_on_the_fly_canonicalization())
- if (type_base_sptr canonical_type = lhs_type.get_canonical_type())
- if (!rhs_type.get_canonical_type()
- && (!rhs_type.priv_->canonical_type_index
- || (rhs_type.priv_->canonical_type_index
- == canonical_type->priv_->canonical_type_index)))
- {
-#if WITH_DEBUG_CT_PROPAGATION
- ABG_ASSERT(!rhs_type.priv_->canonical_type_index
- || (rhs_type.priv_->canonical_type_index
- == canonical_type->priv_->canonical_type_index));
-#endif
- if (env.priv_->propagate_ct(lhs_type, rhs_type))
- return true;
- }
- return false;
-}
-
// <class_decl definitions>
static void
@@ -25716,29 +25371,6 @@ method_matches_at_least_one_in_vector(const method_decl_sptr& method,
return false;
}
-/// Cancel the canonical type that was propagated.
-///
-/// If we are in the process of comparing a type for the purpose of
-/// canonicalization, and if that type has been the target of the
-/// canonical type propagation optimization, then clear the propagated
-/// canonical type. See @ref OnTheFlyCanonicalization for more about
-/// the canonical type optimization
-///
-/// @param t the type to consider.
-static bool
-maybe_cancel_propagated_canonical_type(const class_or_union& t)
-{
- const environment& env = t.get_environment();
- if (env.do_on_the_fly_canonicalization())
- if (is_type(&t)->priv_->canonical_type_propagated())
- {
- is_type(&t)->priv_->clear_propagated_canonical_type();
- env.priv_->remove_from_types_with_non_confirmed_propagated_ct(&t);
- return true;
- }
- return false;
-}
-
/// Compares two instances of @ref class_decl.
///
/// If the two intances are different, set a bitfield to give some
@@ -25778,7 +25410,6 @@ equals(const class_decl& l, const class_decl& r, change_kind* k)
static_cast<const class_or_union&>(r),
k));
- bool had_canonical_type = !!r.get_naked_canonical_type();
bool result = true;
if (!equals(static_cast<const class_or_union&>(l),
static_cast<const class_or_union&>(r),
@@ -25789,13 +25420,6 @@ equals(const class_decl& l, const class_decl& r, change_kind* k)
ABG_RETURN(result);
}
- // If comparing the class_or_union 'part' of the type led to
- // canonical type propagation, then cancel that because it's too
- // early to do that at this point. We still need to compare bases
- // virtual members.
- if (!had_canonical_type)
- maybe_cancel_propagated_canonical_type(r);
-
RETURN_TRUE_IF_COMPARISON_CYCLE_DETECTED(l, r);
mark_types_as_being_compared(l, r);