[Bug c++/66962] New: [concepts] overloaded function causing memory blow-up and ICE

[Bug c++/66962] New: [concepts] overloaded function causing memory blow-up and ICE

[eric.niebler at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

            Bug ID: 66962
           Summary: [concepts] overloaded function causing memory blow-up
                    and ICE
           Product: gcc
           Version: c++-concepts
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: eric.niebler at gmail dot com
  Target Milestone: ---

Created attachment 36028
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36028&action=edit
preprocessed source

Compile with: g++ -std=gnu++1z -c iterator.i.cpp

Result:
g++: internal compiler error: Segmentation fault (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

It seems to have something to do with the iter_swap2 definition. Commenting out
those two functions makes the compile complete successfully (although IMO it
takes longer than it should, so we're probably already in trouble).

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[eric.niebler at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #3 from Eric Niebler <eric.niebler at gmail dot com> ---
I can't make sense of that error, or understand why you get that and I don't.
You tried the command line I gave above, with the latest concept-gcc built from
source?

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #4 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
(In reply to Eric Niebler from comment #3)
> I can't make sense of that error, or understand why you get that and I
> don't. You tried the command line I gave above, with the latest concept-gcc
> built from source?

Yes. But it looks like you use i686-pc-cygwin and I'm running Linux.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[Casey at Carter dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #5 from Casey Carter <Casey at Carter dot net> ---
(In reply to Markus Trippelsdorf from comment #2)
> /usr/local/gcc-concepts/include/c++/6.0.0/initializer_list:47:11: fatal
> error: definition of std::initializer_list does not match #include
> <initializer_list>

This is because the definition of std::initializer_list in the preprocessed
source doesn't agree with your compiler's - or mine - notion of what
std::initializer_list should be.

We need a more recent test case.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[eric.niebler at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

Eric Niebler <eric.niebler at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #36028|0                           |1
        is obsolete|                            |

--- Comment #6 from Eric Niebler <eric.niebler at gmail dot com> ---
Created attachment 36043
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36043&action=edit
regenerate the test case

Regenerate the test case. Hopefully this is better.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[Casey at Carter dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #7 from Casey Carter <Casey at Carter dot net> ---
Created attachment 36044
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36044&action=edit
Manually flattened test case

Doesn't include the contents of any system headers.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-07-23
     Ever confirmed|0                           |1

--- Comment #8 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Casey Carter from comment #5)
> (In reply to Markus Trippelsdorf from comment #2)
> > /usr/local/gcc-concepts/include/c++/6.0.0/initializer_list:47:11: fatal
> > error: definition of std::initializer_list does not match #include
> > <initializer_list>
> 
> This is because the definition of std::initializer_list in the preprocessed
> source doesn't agree with your compiler's - or mine - notion of what
> std::initializer_list should be.

The issue is just 32-bit vs 64-bit size_t.  I'm able to reproduce the bug with
the original testcase using the -m32 flag.

The testcase in comment #7 has different requirements on iter_swap2, so it
doesn't run into this bug.  It was crashing because my recent patch needed an
additional NULL check, which I have now added.

The problem in Eric's testcases seems to be that decompose_assumptions is
consuming an extreme amount of memory, I think because left_disjunction causes
the process to have quadratic complexity.  So I think we need an algorithmic
change here.  Andrew?

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #10 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
Here is a somewhat reduced testcase:

markus@x4 tmp % cat foo.ii
namespace std {
template <typename> struct remove_cv;
template <typename> struct is_reference;
template <typename> void declval();
template <typename> struct is_constructible;
template <typename> struct is_nothrow_constructible;
template <typename _Tp> using remove_cv_t = typename remove_cv<_Tp>::type;
namespace meta {
template <typename> struct Trans_NS_extension_apply_list;
template <typename T> using _t = typename T::type;
namespace ext {
template <class> void ImplicitlyConvertibleTo();
}
template <class> void Assignable();
namespace ext {
template <class T, class... Args> int ConstructibleObject = requires { T{}; };
template <class T, class... Args>
concept int BindableReference =
    std::is_reference<T>::value &&std::is_constructible<T>::value;
template <class T, class... Args> concept bool Constructible() {
  return ext::ConstructibleObject<T> || ext::BindableReference<T, Args...>;
}
template <class T> concept bool DefaultConstructible() {
  return Constructible<T>() && requires { new T[0]; };
}
template <class T> concept bool MoveConstructible() {
  return Constructible<T>() && ext::ImplicitlyConvertibleTo<T>;
}
template <class T> concept bool Movable() {
  return MoveConstructible<T>() && Assignable<T &&>;
}
namespace detail {
template <class, class> int Swappable_ = requires { 0; };
template <class T, class U> int Swappable();
template <class T> concept int Dereferencable = requires{{0}};
}
template <detail::Dereferencable R> using RvalueReferenceType = decltype(0);
namespace detail {
template <class T> int IsValueType;
template <class> struct value_type;
template <class T>
requires detail::IsValueType<
    meta::_t<value_type<std::remove_cv_t<T>>>> using ValueType =
    meta::_t<value_type<std::remove_cv_t<T>>>;
template <class I> concept bool Readable() {
  return Movable<I>() && DefaultConstructible<I>() &&
         detail::Dereferencable<const I> && requires{{0}};
}
template <class Out, class T> concept bool MoveWritable() {
  return Movable<Out>() && DefaultConstructible<Out>() &&
         detail::Dereferencable<Out>;
}
template <class In, class Out> concept bool IndirectlyMovable() {
  return Readable<In>() && Movable<ValueType<In>>() &&
         Constructible<ValueType<In>>() &&
         MoveWritable<Out, RvalueReferenceType<In>>() &&
         MoveWritable<Out, ValueType<In>>();
}
IndirectlyMovable { In, Out }
int is_nothrow_indirectly_movable_v =
    is_nothrow_constructible<ValueType<In>>::value;
template <Readable R1, Readable R2>
    requires IndirectlyMovable<R1, R2>() &&
    IndirectlyMovable<R2, R1>() void iter_swap2();
}
}
}
}

markus@x4 tmp % ulimit -v 3000000 && g++ -std=gnu++1z -c foo.ii
virtual memory exhausted: Cannot allocate memory

Perf shows:

  17.64%  cc1plus  libc-2.21.90.so    [.] _int_malloc                           
  13.55%  cc1plus  cc1plus            [.] decompose_assumptions                 
  13.06%  cc1plus  libc-2.21.90.so    [.] malloc_consolidate                    
  11.61%  cc1plus  libc-2.21.90.so    [.] _int_free                             
   7.68%  cc1plus  cc1plus            [.] gt_ggc_mx_lang_tree_node              
   6.87%  cc1plus  [kernel.kallsyms]  [k] clear_page                            
   5.91%  cc1plus  libc-2.21.90.so    [.] malloc                                
   4.51%  cc1plus  cc1plus            [.] ggc_set_mark                          
   3.90%  cc1plus  libc-2.21.90.so    [.] free                                  
   2.61%  cc1plus  libc-2.21.90.so    [.] memset

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[eric.niebler at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #11 from Eric Niebler <eric.niebler at gmail dot com> ---
Removing the disjunction in the Constructible concept causes memory usage and
compile time to drop to zero. The word from Andrew is that this is simply a
quadratic algorithm. It is unknown whether a non-quadratic algorithm that
handles disjunctions exists. Given that, I think we simply need to avoid
concepts with disjunctions in STL2. :-(

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #12 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
This paper claims O(e log d) for size e and alternation depth d:
http://www.win.tue.nl/~jfg/articles/CSR-04-13.pdf

But I'm not sure if it is applicable.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[andrew.n.sutton at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #14 from Andrew Sutton <andrew.n.sutton at gmail dot com> ---
Created attachment 36054
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36054&action=edit
Optimize constraint decomposition by contraction

The problem isn't strictly related to decomposition -- it's normalization prior
to decomposition that's causing the problems. Whenever you have a disjunction
in a low-level concept, that OR can be instantiated into the normalized
constraints many, many times. I think I measured 20 times in the reduced
example. I think there's actually worst case 2^N growth in the space required
to solve the problem.

Currently, we might accumulate a term list during decomposition like so:

P || Q, P || Q, P, R, P || Q

And then recursively decompose each term in that list. Each || turns into a new
branch, here, eventually generating 8 different term lists, none of which are
semantically different than any other. They're just permutations of terms.

The patch helps reduce the space by disallowing duplicate expressions to be
added to a term list during decomposition. So instead of generating the term
list above, we just have:

P || Q, P, R

Only one branch required.

There is still complexity induced by the use of disjunctions. This manages it a
little better. It could be further improved by making the term list into a term
set by way of hashing or ordering.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #15 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Eric Niebler from comment #9)
> Jason, is there anything I can do in my code to avoid the quadratic
> explosion while we wait for Andrew to fix the bug?

In concepts, !(A && B) is not equivalent to !A || !B because the former is a
single predicate, while the latter is a disjunction.

So, converting A || B to !(!A && !B) will avoid the explosion at the cost of
limiting subsumption.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #16 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Jason Merrill from comment #15)
> So, converting A || B to !(!A && !B) will avoid the explosion at the cost of
> limiting subsumption.

Or even !!(A || B).

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #17 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Andrew Sutton from comment #14)
> Created attachment 36054 [details]
> 
> There is still complexity induced by the use of disjunctions. This manages
> it a little better. It could be further improved by making the term list
> into a term set by way of hashing or ordering.

This seems like a definite improvement, though I agree that we will want to
move to a set.  I was waiting for you to check it in; perhaps you were also
waiting for me to do it?  I'll go ahead and apply it now.

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

--- Comment #18 from Jason Merrill <jason at gcc dot gnu.org> ---
Author: jason
Date: Tue Aug  4 15:38:29 2015
New Revision: 226583

URL: https://gcc.gnu.org/viewcvs?rev=226583&root=gcc&view=rev
Log:
        PR c++/66962
        * logic.cc (term_list::insert): Avoid adding duplicate terms.

Added:
    branches/c++-concepts/gcc/testsuite/g++.dg/concepts/disjunction1.C
Modified:
    branches/c++-concepts/ChangeLog.concepts
    branches/c++-concepts/gcc/cp/logic.cc

[Bug c++/66962] [concepts] overloaded function causing memory blow-up and ICE

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #19 from Jason Merrill <jason at gcc dot gnu.org> ---
Fixed.