@@ -116,6 +116,12 @@ 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],
['enable abilint --show-type-use'(default is no)]),
@@ -434,6 +440,15 @@ 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)
@@ -1063,6 +1078,7 @@ 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}
@@ -537,6 +537,10 @@ typedef unordered_set<const type_or_decl_base*,
/// value is a @ref type_base_wptr.
typedef unordered_map<string, type_base_wptr> string_type_base_wptr_map_type;
+/// A convenience typedef for a map which key is a string and which
+/// value is a @ref type_base_sptr.
+typedef unordered_map<string, type_base_sptr> string_type_base_sptr_map_type;
+
/// A convenience typedef for a map which key is an @ref
/// interned_string and which value is a @ref type_base_wptr.
typedef unordered_map<interned_string, type_base_wptr, hash_interned_string>
@@ -131,7 +131,7 @@ class reader : public elf_based_reader
/// A map associating CTF type ids with libabigail IR types. This
/// is used to reuse already generated types.
- unordered_map<string,type_base_sptr> types_map;
+ string_type_base_sptr_map_type types_map;
/// A set associating unknown CTF type ids
std::set<ctf_id_t> unknown_types_set;
@@ -203,8 +203,10 @@ public:
void
canonicalize_all_types(void)
{
- for (auto t = types_map.begin(); t != types_map.end(); t++)
- canonicalize (t->second);
+ canonicalize_types
+ (types_map.begin(), types_map.end(),
+ [](const string_type_base_sptr_map_type::const_iterator& i)
+ {return i->second;});
}
/// Constructor.
@@ -4591,37 +4591,10 @@ public:
}
if (!types_to_canonicalize().empty())
- {
- tools_utils::timer single_type_cn_timer;
- size_t total = types_to_canonicalize().size();
- if (do_log())
- cerr << total << " Types to canonicalize\n";
- size_t i = 1;
- for (vector<type_base_sptr>::const_iterator it =
- types_to_canonicalize().begin();
- it != types_to_canonicalize().end();
- ++it, ++i)
- {
- if (do_log())
- {
- cerr << "canonicalizing type "
- << get_pretty_representation(*it, false)
- << " [" << i << "/" << total << "]";
- if (corpus_sptr c = corpus())
- cerr << "@" << c->get_path();
- cerr << " ...";
- single_type_cn_timer.start();
- }
- canonicalize(*it);
- if (do_log())
- {
- single_type_cn_timer.stop();
- cerr << "DONE:"
- << single_type_cn_timer
- << "\n";
- }
- }
- }
+ canonicalize_types(types_to_canonicalize().begin(),
+ types_to_canonicalize().end(),
+ [](const vector<type_base_sptr>::const_iterator& i)
+ {return *i;});
if (do_log())
{
@@ -337,7 +337,7 @@ struct type_base::priv
/// If the current canonical type was set as the result of the
/// "canonical type propagation optimization", then clear it.
- void
+ bool
clear_propagated_canonical_type()
{
if (canonical_type_propagated_ && !propagated_canonical_type_confirmed_)
@@ -345,7 +345,9 @@ struct type_base::priv
canonical_type.reset();
naked_canonical_type = nullptr;
set_canonical_type_propagated(false);
+ return true;
}
+ return false;
}
}; // end struct type_base::priv
@@ -458,6 +460,14 @@ struct environment::priv
// 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
@@ -794,6 +804,11 @@ struct environment::priv
dest.priv_->canonical_type = canonical;
dest.priv_->naked_canonical_type = canonical.get();
dest.priv_->set_canonical_type_propagated(true);
+#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;
}
@@ -874,6 +889,56 @@ struct environment::priv
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
@@ -941,7 +1006,7 @@ struct environment::priv
type_base_sptr canonical = t->priv_->canonical_type.lock();
if (canonical)
{
- t->priv_->clear_propagated_canonical_type();
+ clear_propagated_canonical_type(t);
t->priv_->set_does_not_depend_on_recursive_type();
}
}
@@ -980,9 +1045,7 @@ struct environment::priv
{
// This cannot carry any tentative canonical type at this
// point.
- if (t->priv_->canonical_type_propagated()
- && !t->priv_->propagated_canonical_type_confirmed())
- t->priv_->clear_propagated_canonical_type();
+ clear_propagated_canonical_type(t);
// Reset the marking of the type as it no longer carries a
// tentative canonical type that might be later cancelled.
t->priv_->set_does_not_depend_on_recursive_type();
@@ -990,6 +1053,30 @@ struct environment::priv
}
}
+ /// 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.
@@ -1092,6 +1179,64 @@ struct environment::priv
#endif
};// end struct environment::priv
+/// Compute the canonical type for all the IR types of the system.
+///
+/// After invoking this function, the time it takes to compare two
+/// types of the IR is equivalent to the time it takes to compare
+/// their pointer value. That is faster than performing a structural
+/// (A.K.A. member-wise) comparison.
+///
+/// Note that this function performs some sanity checks after* the
+/// canonicalization process. It ensures that at the end of the
+/// canonicalization process, all types have been canonicalized. This
+/// is important because the canonicalization algorithm sometimes
+/// clears some canonical types after having speculatively set them
+/// for performance purposes. At the end of the process however, all
+/// types must be canonicalized, and this function detects violations
+/// of that assertion.
+///
+/// @tparam input_iterator the type of the input iterator of the @p
+/// beging and @p end.
+///
+/// @tparam deref_lambda a lambda function which takes in parameter
+/// the input iterator of type @p input_iterator and dereferences it
+/// to return the type to canonicalize.
+///
+/// @param begin an iterator pointing to the first type of the set of types
+/// to canonicalize.
+///
+/// @param end an iterator pointing to the end (after the last type) of
+/// the set of types to canonicalize.
+///
+/// @param deref a lambda function that knows how to dereference the
+/// iterator @p begin to return the type to canonicalize.
+template<typename input_iterator,
+ typename deref_lambda>
+void
+canonicalize_types(const input_iterator& begin,
+ const input_iterator& end,
+ deref_lambda deref)
+{
+ if (begin == end)
+ return;
+
+ // First, let's compute the canonical type of this type.
+ for (auto t = begin; t != end; ++t)
+ 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
+}
+
// <class_or_union::priv definitions>
struct class_or_union::priv
{
@@ -14564,37 +14564,50 @@ canonicalize(type_base_sptr t)
}
if (canonical)
- if (decl_base_sptr d = is_decl_slow(canonical))
- {
- scope_decl *scope = d->get_scope();
- // Add the canonical type to the set of canonical types
- // belonging to its scope.
- if (scope)
- {
- if (is_type(scope))
- // The scope in question is itself a type (e.g, a class
- // or union). Let's call that type ST. We want to add
- // 'canonical' to the set of canonical types belonging
- // to ST.
- if (type_base_sptr c = is_type(scope)->get_canonical_type())
- // We want to add 'canonical' to set of canonical
- // types belonging to the canonical type of ST. That
- // way, just looking at the canonical type of ST is
- // enough to get the types that belong to the scope of
- // the class of equivalence of ST.
- scope = is_scope_decl(is_decl(c)).get();
- scope->get_canonical_types().insert(canonical);
- }
- // else, if the type doesn't have a scope, it's not meant to be
- // emitted. This can be the case for the result of the
- // function strip_typedef, for instance.
- }
+ {
+ if (decl_base_sptr d = is_decl_slow(canonical))
+ {
+ scope_decl *scope = d->get_scope();
+ // Add the canonical type to the set of canonical types
+ // belonging to its scope.
+ if (scope)
+ {
+ if (is_type(scope))
+ // The scope in question is itself a type (e.g, a class
+ // or union). Let's call that type ST. We want to add
+ // 'canonical' to the set of canonical types belonging
+ // to ST.
+ if (type_base_sptr c = is_type(scope)->get_canonical_type())
+ // We want to add 'canonical' to set of canonical
+ // types belonging to the canonical type of ST. That
+ // way, just looking at the canonical type of ST is
+ // enough to get the types that belong to the scope of
+ // the class of equivalence of ST.
+ scope = is_scope_decl(is_decl(c)).get();
+ scope->get_canonical_types().insert(canonical);
+ }
+ // else, if the type doesn't have a scope, it's not meant to be
+ // 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();
return canonical;
}
-
/// Set the definition of this declaration-only @ref decl_base.
///
/// @param d the new definition to set.