On Fri, 6 Nov 2020, Jason Merrill wrote:
> On 11/2/20 9:03 AM, Patrick Palka wrote:
> > On Tue, 27 Oct 2020, Patrick Palka wrote:
> >
> > > The adoption of P2104 means we can memoize the result of satisfaction
> > > indefinitely and no longer have to clear the satisfaction caches on
> > > various events that would affect satisfaction. To that end, this patch
> > > removes clear_satisfaction_cache and adjusts its callers appropriately.
> > >
> > > This provides a massive reduction in compile time and memory use in some
> > > cases. For example, on the libstdc++ test std/ranges/adaptor/join.cc,
> > > compile time and memory usage drops nearly 75%, from 7.5s/770MB to
> > > 2s/230MB, with a --enable-checking=release compiler.
> > >
> > > [ This patch depends on
> > >
> > > c++: Check constraints only for candidate conversion functions.
> > >
> > > Without it, many of the libstdc++ range adaptor tests fail due to
> > > us now indefinitely memoizing a bogus satisfaction result caused by
> > > checking the constraints of a conversion function when we weren't
> > > supposed to, which led to a "use of foo_view::end() before deduction
> > > of auto" SFINAE error. This went unnoticed without this patch because
> > > by the time we needed this satisfaction result again, we had cleared
> > > the satisfaction cache and finished deducing the return type of
> > > foo_view::end(), so on subsequent tries we computed the correct
> > > satisfaction result. ]
> >
> > With the library-side workaround r11-4584 for the range adaptor test
> > failures now committed, the mentioned frontend patch about candidate
> > conversion functions is no longer a prerequisite (and was not we want
> > anyway).
> >
> > >
> > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
> > > trunk (pending approval of the prerequisite patch)? Also tested on
> > > cmcstl2 and range-v3.
> >
> > Now successfully bootstrapped and regtested on top of r11-4584, and also
> > tested on cmcstl2 and range-v3. Does this look OK for trunk?
>
> For me, this patch broke the view.join test in cmcstl2. Are you not seeing
> that?
Yes, cmcstl2's join_view suffers from the exact same issue that the
libstdc++ join_view (and many other views) had before the library-side
fix r11-4584. (They are defined very similarly.)
In short, the satisfaction value of range<join_view> inadvertently
depends on itself. We don't fall into an infinite loop only because
this circular dependence is through return type deduction of
join_view::begin, and this part of the dependence chain breaks the
infinite loop via a "use of foo before deduction of auto" SFINAE error.
We used to invalidate the cache shortly thereafter, but no longer, so
the bogus satisfaction value is now observable.
The following rough patch can be used to get a better sense of what's
going on. It inserts a dummy satisfaction value into the satisfaction
cache when evaluating an atom for the first atom, and verifies
via a gcc_assert that we don't try retrieving the satisfaction value of
this atom while its being evaluated. The view.join test of cmcstl2
trips over this assert. (Diagnosing when the satisfaction value of an
atom depends on itself is on my TODO list after the rest of the caching
optimizations are in. Getting good diagnostics for this is a little
tricky.)
-- >8 --
diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index c871a8ab86a..0f7663b9a7a 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -2312,6 +2312,9 @@ static GTY((deletable)) hash_table<sat_hasher> *sat_cache;
/* Cache the result of constraint_satisfaction_value. */
static GTY((deletable)) hash_map<tree, tree> *decl_satisfied_cache;
+static void
+save_satisfaction (tree constr, tree args, tree result);
+
static tree
get_satisfaction (tree constr, tree args)
{
@@ -2320,9 +2323,19 @@ get_satisfaction (tree constr, tree args)
sat_entry elt = { constr, args, NULL_TREE };
sat_entry* found = sat_cache->find (&elt);
if (found)
- return found->result;
+ {
+ /* If this assert fails, then the satisfaction value of an atom
+ recursively depends on itself. */
+ gcc_assert (found->result);
+ return found->result;
+ }
else
- return NULL_TREE;
+ {
+ /* Mark that this atom is being evaluated by setting its
+ result to NULL_TREE. */
+ save_satisfaction (constr, args, NULL_TREE);
+ return NULL_TREE;
+ }
}
static void
