GCC Bugzilla Bug 31863

        We tried to move from gcc-4.0 to gcc-4.1 and now we have problem - our
        project fails to compile with optimization. We use a lot of templates,
        particulary, Loki::TypeList.
        Please see attached test.cc. It compiles with g++-4.0 using ~180Mb of
        memory, but with g++-4.1 it eats ~1.5Gb and then say that it can't
        allocate memory:

        jk@jk:~/tmp/gcc% g++-4.1 -O2 -g test.cc

        cc1plus: out of memory allocating 2098751636 bytes after a total of
        11571200 bytes
        jk@jk:~/tmp/gcc%

        It compiles well without optimization.

        This bug report has been sent to Debian BTS, #411234

Environment:
System: Linux jk 2.6.18-4-686 #1 SMP Mon Mar 26 17:17:36 UTC 2007 i686
GNU/Linux
Architecture: i686
host: i486-pc-linux-gnu
build: i486-pc-linux-gnu
target: i486-pc-linux-gnu
configured with: ../src/configure -v
--enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr
--enable-shared --with-system-zlib --libexecdir=/usr/lib
--without-included-gettext --enable-threads=posix --enable-nls
--program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu
--enable-libstdcxx-debug --enable-mpfr --with-tune=i686
--enable-checking=release i486-linux-gnu

How-To-Repeat:

test.cc:

namespace Loki
{
    class NullType {};
    template <class T, class U>
    struct Typelist
    {
       typedef T Head;
       typedef U Tail;
    };



    namespace TL
    {
        template
        <
                typename T1 = NullType, typename T2 = NullType, typename T3 =
NullType,
                typename T4 = NullType, typename T5 = NullType, typename T6 =
NullType,
                typename T7 = NullType, typename T8 = NullType, typename T9 =
NullType,
                typename T10 = NullType, typename T11 = NullType, typename T12
= NullType,
                typename T13 = NullType, typename T14 = NullType, typename T15
= NullType,
                typename T16 = NullType, typename T17 = NullType, typename T18
= NullType,
                typename T19 = NullType, typename T20 = NullType, typename T21
= NullType,
                typename T22 = NullType, typename T23 = NullType, typename T24
= NullType,
                typename T25 = NullType, typename T26 = NullType, typename T27
= NullType,
                typename T28 = NullType, typename T29 = NullType, typename T30
= NullType,
                typename T31 = NullType, typename T32 = NullType, typename T33
= NullType,
                typename T34 = NullType, typename T35 = NullType, typename T36
= NullType,
                typename T37 = NullType, typename T38 = NullType, typename T39
= NullType,
                typename T40 = NullType
        >
        struct MakeTypelist
        {
        private:
            typedef typename MakeTypelist
            <
                T2 , T3 , T4 ,
                T5 , T6 , T7 ,
                T8 , T9 , T10,
                T11, T12, T13,
                T14, T15, T16,
                T17, T18, T19,
                T20, T21, T22,
                T23, T24, T25,
                T26, T27, T28,
                T29, T30, T31,
                T32, T33, T34,
                T35, T36, T37,
                T38, T39, T40
            >
            ::Result TailResult;

        public:
            typedef Typelist<T1, TailResult> Result;
        };

        template<>
        struct MakeTypelist<>
        {
            typedef NullType Result;
        };

    }
}
template <class Key>
class Factory;

template <class Key, bool iW>
struct Context
{
    typedef Key KeyType;
    enum
    {
        isWrite = iW
    };
};

namespace detail
{

template <class Key, bool isWrite>
class CreatorUnitBaseImpl
{
public:
    typedef Context<Key, isWrite> Context;
private:
    typedef void*(CreatorUnitBaseImpl::*CreateFun)(Context&, unsigned&, const
Key&);
    CreateFun createFun_;

protected:
    virtual void* createUninitialized () = 0;
    template <class Value>
    void* createImpl (Context& ctx, unsigned& ver, const Key& k)
    {
        return createUninitialized();
    }
private:
    CreatorUnitBaseImpl();
public:
    template <class Value>
    CreatorUnitBaseImpl (Value*) :
        createFun_( &CreatorUnitBaseImpl::template createImpl<Value> )
    {
    }

    virtual ~CreatorUnitBaseImpl () {}

    CreatorUnitBaseImpl(const CreatorUnitBaseImpl& s)
        : createFun_(s.createFun_)
    {
    }

    CreatorUnitBaseImpl& operator=(const CreatorUnitBaseImpl& s)
    {
        createFun_ = s.createFun_;
        return *this;
    }
    void* create (Context& ctx, unsigned& ver, const Key& k)
    {
        return (this->*createFun_)(ctx, ver, k);
    }
};

template <class Key>
class Creator : protected CreatorUnitBaseImpl<Key, true>, protected
CreatorUnitBaseImpl<Key, false>
{
public:
    typedef void* (*CreatorFun) ();

private:
    CreatorFun fun_;
protected:
    virtual void* createUninitialized ()
    {
        if (fun_)
            return (*fun_)();
        return 0;
    }
private:
    Creator ();
public:
    template <class Value>
    Creator (CreatorFun f, Value*) :
        CreatorUnitBaseImpl<Key, true>((Value*)0),
        CreatorUnitBaseImpl<Key, false>((Value*)0),
        fun_(f)
    {
    }

    Creator(const Creator& s) :
        CreatorUnitBaseImpl<Key, true>(s),
        CreatorUnitBaseImpl<Key, false>(s),
        fun_(s.fun_)
    {

    }

    Creator& operator=(const Creator& s)
    {
        CreatorUnitBaseImpl<Key, true>::operator=(s);
        CreatorUnitBaseImpl<Key, false>::operator=(s);
        fun_ = s.fun_;
        return *this;
    }

    virtual ~Creator ()
    {
    }

    template <class Context>
    void* createObject (Context& ctx, unsigned& ver, const Key& k)
    {
        void* r = CreatorUnitBaseImpl<Key, Context::isWrite>::create(ctx, ver,
k);
        return r;
    }
};

}

template <class Key>
class Factory
{
public:
    typedef Key KeyType;
    typedef void* (*CreatorFun) ();
    typedef detail::Creator<Key> Creator;
public:
    Factory () {}
    ~Factory () {}

    template <class Value>
    bool registerCreator (const Key& k, CreatorFun fun)
    {
        return true;
    }
    template <class Context>
    void* createObject (const Key& k, Context& ctx, unsigned& ver)
    {
        return 0;
    }
};

template <class Key, class Base, Key key>
struct ClassSpec
{
    typedef Key KeyType;
    typedef Base BaseType;
    enum {KeyValue = key};
};

template <class Key, class T>
class Serializer;

template <class Key, class Base, Key key>
class Serializer<Key, ClassSpec <Key, Base, key> >
    : public virtual Factory<Key>
{
    typedef Key KeyType;
    typedef Base BaseType;
    enum {KeyValue = key};
    typedef Factory<Key> Inherited;
    typedef Serializer<Key, ClassSpec< Key, Base, key > > SelfType;

    static void* create ()
    {
        return (void*) (new BaseType);
    }
public:
    Serializer()
    {
        Inherited::template registerCreator<BaseType>(
                KeyValue,
                &SelfType::create);
    }
};

template <class Key, class Head>
class Serializer<Key, Loki::Typelist<Head, Loki::NullType> >:
    public Serializer<Key, Head>
{
};

template <class Key, class Head, class Tail>
class Serializer<Key, Loki::Typelist<Head, Tail> >:
    public virtual Serializer<Key, Head>,
    public virtual Serializer<Key, Tail>
{
};

template <class Key>
class Serializer<Key, Loki::NullType> : public virtual Factory<Key>
{
};




typedef unsigned KeyType;



typedef Factory<KeyType> FactoryType;

typedef KeyType Key;

struct A001
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 1; }
    static const char* className () {return "A001";}
};

struct A002
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 2; }
    static const char* className () {return "A002";}
};

struct A003
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 3; }
    static const char* className () {return "A003";}
};

struct A004
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 4; }
    static const char* className () {return "A004";}
};

struct A005
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 5; }
    static const char* className () {return "A005";}
};

struct A006
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 6; }
    static const char* className () {return "A006";}
};

struct A007
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 7; }
    static const char* className () {return "A007";}
};

struct A008
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 8; }
    static const char* className () {return "A008";}
};

struct A009
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 9; }
    static const char* className () {return "A009";}
};

struct A010
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 10; }
    static const char* className () {return "A010";}
};

struct A011
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 11; }
    static const char* className () {return "A011";}
};

struct A012
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 12; }
    static const char* className () {return "A012";}
};

struct A013
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 13; }
    static const char* className () {return "A013";}
};

struct A014
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 14; }
    static const char* className () {return "A014";}
};

struct A015
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 15; }
    static const char* className () {return "A015";}
};

struct A016
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 16; }
    static const char* className () {return "A016";}
};

struct A017
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 17; }
    static const char* className () {return "A017";}
};

struct A018
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 18; }
    static const char* className () {return "A018";}
};

struct A019
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 19; }
    static const char* className () {return "A019";}
};

struct A020
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 20; }
    static const char* className () {return "A020";}
};

struct A021
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 21; }
    static const char* className () {return "A021";}
};

struct A022
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 22; }
    static const char* className () {return "A022";}
};

struct A023
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 23; }
    static const char* className () {return "A023";}
};

struct A024
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 24; }
    static const char* className () {return "A024";}
};

struct A025
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 25; }
    static const char* className () {return "A025";}
};

struct A026
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 26; }
    static const char* className () {return "A026";}
};

struct A027
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 27; }
    static const char* className () {return "A027";}
};

struct A028
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 28; }
    static const char* className () {return "A028";}
};

struct A029
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 29; }
    static const char* className () {return "A029";}
};

struct A030
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 30; }
    static const char* className () {return "A030";}
};

struct A031
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 31; }
    static const char* className () {return "A031";}
};

struct A032
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 32; }
    static const char* className () {return "A032";}
};

struct A033
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 33; }
    static const char* className () {return "A033";}
};

struct A034
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 34; }
    static const char* className () {return "A034";}
};

struct A035
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 35; }
    static const char* className () {return "A035";}
};

struct A036
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 36; }
    static const char* className () {return "A036";}
};

struct A037
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 37; }
    static const char* className () {return "A037";}
};

struct A038
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 38; }
    static const char* className () {return "A038";}
};

struct A039
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 39; }
    static const char* className () {return "A039";}
};

struct A040
{
    template <class Context>
    bool serialize(Context& ctx, unsigned& ver)
    {
        return true;
    }
    static Key classId() { return 40; }
    static const char* className () {return "A040";}
};

Factory<Key>& getInstance()
{
    static Serializer<Key,
        Loki::TL::MakeTypelist<
            ClassSpec<Key, A001, 1>,
            ClassSpec<Key, A002, 2>,
            ClassSpec<Key, A003, 3>,
            ClassSpec<Key, A004, 4>,
            ClassSpec<Key, A005, 5>,
            ClassSpec<Key, A006, 6>,
            ClassSpec<Key, A007, 7>,
            ClassSpec<Key, A008, 8>,
            ClassSpec<Key, A009, 9>,
            ClassSpec<Key, A010, 10>,
            ClassSpec<Key, A011, 11>,
            ClassSpec<Key, A012, 12>,
            ClassSpec<Key, A013, 13>,
            ClassSpec<Key, A014, 14>,
            ClassSpec<Key, A015, 15>,
            ClassSpec<Key, A016, 16>,
            ClassSpec<Key, A017, 17>,
            ClassSpec<Key, A018, 18>,
            ClassSpec<Key, A019, 19>,
            ClassSpec<Key, A020, 20>,
            ClassSpec<Key, A021, 21>,
            ClassSpec<Key, A022, 22>,
            ClassSpec<Key, A023, 23>,
            ClassSpec<Key, A024, 24>,
            ClassSpec<Key, A025, 25>,
            ClassSpec<Key, A026, 26>,
            ClassSpec<Key, A027, 27>,
            ClassSpec<Key, A028, 28>,
            ClassSpec<Key, A029, 29>,
            ClassSpec<Key, A030, 30>,
            ClassSpec<Key, A031, 31>,
            ClassSpec<Key, A032, 32>,
            ClassSpec<Key, A033, 33>,
            ClassSpec<Key, A034, 34>,
            ClassSpec<Key, A035, 35>,
            ClassSpec<Key, A036, 36>,
            ClassSpec<Key, A037, 37>,
            ClassSpec<Key, A038, 38>,
            ClassSpec<Key, A039, 39>,
            ClassSpec<Key, A040, 40>
        >::Result
    > instance;
    return instance;
}

int main ()
{
    return 0;
}

Created an attachment (id=13530) [edit]
testcase

This is related to PR29433, but still unresolved.

Until I killed cc1plus we have (mainline):

samples  %        symbol name
50115    28.3000  push_fields_onto_fieldstack
12370     6.9853  bitpos_of_field
10174     5.7453  tree_low_cst
8825      4.9835  host_integerp
5204      2.9387  walk_tree
3666      2.0702  pointer_set_insert
2434      1.3745  cp_walk_subtrees
2199      1.2418  comptypes
2039      1.1514  ggc_alloc_stat

which suspiciously hints at aliasing...!?  Need to go for a bigger machine...

cc1plus: out of memory allocating 18888764584 bytes after a total of 16482304
bytes

so this actually killed even the 16GB box.

Danny, push_fields_onto_fieldstack is going crazy on this.

Note the interesting debuggable testcase is if you remove from getInstance()
all
template params from ClassSpec<Key, A020, 21> on.  Around that one you'll
clearly
see exponential behavior in memory use ;)

4.2 (RC2, 20070430) also explodes (OOM) with the test case, using -O2.  
whereas 4.0.1 (powerpc-apple-darwin8) peaks out at 280 MB (cc1plus), which is
reasonable and typical. 
Flag as 4.1/4.2/4.3 regression?

Well, 4.0 didn't have struct aliasing, so yes.  Though it's unlikely to be
fixed
for 4.1.x.

Each one of thousands of temporary variables ends up with 12000 fields.

Hi!

Is there any progress with this bug?
We are waiting impatiently for fix!

Subject: Re:  [4.1/4.2/4.3 Regression] g++-4.1: out of memory
 with -O1/-O2

On Tue, 18 Sep 2007, alexander at kogan dot nnov dot ru wrote:
> ------- Comment #10 from alexander at kogan dot nnov dot ru  2007-09-18 04:58 -------
> Hi!
> 
> Is there any progress with this bug?
> We are waiting impatiently for fix!

I have one fix in this are in the queue, but it does unfortunately
not completely solve this problem.

What do u mean 'not completely'?
Can I try this fix?

Subject: Re:  [4.1/4.2/4.3 Regression] g++-4.1:
 out of memory with -O1/-O2

On Tue, 18 Sep 2007, alexander at kogan dot nnov dot ru wrote:

> ------- Comment #12 from alexander at kogan dot nnov dot ru  2007-09-18 09:07 -------
> What do u mean 'not completely'?
> Can I try this fix?

I mean there is a memleak that I plugged, but memory usage is still
exponential in the number of template parameters.

Ok. Do you mean the attached test doesn't work even with this fix? But are
there plans to eliminate this problem completely?

Subject: Re:  [4.1/4.2/4.3 Regression] g++-4.1:
 out of memory with -O1/-O2

On Tue, 18 Sep 2007, alexander at kogan dot nnov dot ru wrote:

> ------- Comment #14 from alexander at kogan dot nnov dot ru  2007-09-18 09:55 -------
> Ok. Do you mean the attached test doesn't work even with this fix? But are
> there plans to eliminate this problem completely?

The testcase doesn't work with the fix.

Subject: Bug 31863

Author: rguenth
Date: Tue Sep 18 11:22:47 2007
New Revision: 128573

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=128573
Log:
2007-09-18  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/31863
        * tree-ssa-structalias.c (create_variable_info_for): Always
        free the fieldstack.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-structalias.c

Note that the double virtual inheritance in the Serializer template creates the
exponential behavior.  You can fix this at the source level by instead
doing

template <class Key, class Head>
class Serializer<Key, Loki::Typelist<Head, Loki::NullType> >:
    public virtual Serializer<Key, Head>
{
};

template <class Key, class Head, class Tail>
class Serializer<Key, Loki::Typelist<Head, Tail> >:
    public virtual Serializer<Key, Head>,
    public Serializer<Key, Tail>
{
};

template <class Key>
class Serializer<Key, Loki::NullType> : public virtual Factory<Key>
{
};

which also makes more sense(?).  Back to marking this as possibly a C++
frontend bug - though I'm inclined to close this bug as INVALID.

Thank you very much for this workaround. Really we do not need virtual
inheritance there, we need only virtual inheritance from Factory. In this case
it works!

I believe that empty base optimization doesn't work for virtual inheritance.
Whether this is a GCC specific problem or a general fact I don't know.

So this bug was worked around -- but can this be fixed properly for GCC 4.3? 
Richi, is this just another example of the SFT problems reported in other PRs?

Well, the many SFTs don't help the situation for sure.  But we can't do
anything
for 4.3 here, as only after walking all the fields in push_fields_to_fieldstack
we figure out we better not generate SFTs here.  Which is too late.

But yes, I suppose I can simply early exit from that function now that we
always punt if the number of fields is too large.

Subject: Bug 31863

Author: rguenth
Date: Tue Jan  8 21:35:25 2008
New Revision: 131405

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131405
Log:
2008-01-08  Richard Guenther  <rguenther@suse.de>

        PR middle-end/31863
        * tree-ssa-structalias.c (push_fields_onto_fieldstack): Bail
        out early if the result will be unused.

        * g++.dg/torture/pr31863.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/torture/pr31863.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-structalias.c

Fixed on the trunk.

Closing 4.1 branch.

Closing 4.2 branch, fixed in 4.3.