[Bug c++/55442] New: G++ uses up all my RAM when compiling a constexpr with exponential call graph

[Bug c++/55442] New: G++ uses up all my RAM when compiling a constexpr with exponential call graph

[david at aitellu dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55442

             Bug #: 55442
           Summary: G++ uses up all my RAM when compiling a constexpr with
                    exponential call graph
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: david@aitellu.com


I have compiled the following program on GCC 4.7.2 and the latest 4.8, using
Ubuntu 12.10 with Linux kernel 3.5.0:

const int MAXD = 24;

constexpr int count(int n, int depth=1){
  return depth == MAXD ? n + 1: count(count(n, depth + 1), depth + 1) + 1;
}

#include<iostream>

int main(){
  constexpr int i = count(0);
  std::cout << i << std::endl;
}

Both versions of GCC will use over 3.3 gig RAM in about 30 seconds. For each
step I increase MAXD, the RAM usage will double until my computer swaps or the
kernel kills the process.

It will never reach a recursion depth of more than 24, but the call graph is
sort of a binary tree, so it will visit 2^MAXD - 1 nodes. Since the recursion
is so shallow, it should not have to use any memory. Clang 3.1 compiles it
without using "any" memory.

Before posting this report, I asked on Stackoverflow, where it was suggested I
report it here.

My guess is that this has something to do with unlimited memoization?

[Bug c++/55442] G++ uses up all my RAM when compiling a constexpr with exponential call graph

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55442

Jan Hubicka <hubicka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-11-22
                 CC|                            |hubicka at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #1 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-11-22 17:01:08 UTC ---
This seems to be frontend issue
We spend a lot of time in
#102 0x000000000069ea86 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7676
#103 0x000000000069f869 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:6789
#104 0x000000000069f6ab in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7793
#105 0x000000000069f1b5 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7697
#106 0x00000000006a5b5f in cxx_eval_call_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) () at ../../gcc/cp/semantics.c:6676
#107 0x000000000069ea86 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7676
#108 0x00000000006a55b1 in cxx_eval_call_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) () at ../../gcc/cp/semantics.c:6489
#109 0x000000000069ea86 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7676
#110 0x000000000069f869 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:6789
#111 0x000000000069f6ab in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7793
#112 0x000000000069f1b5 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7697
#113 0x00000000006a5b5f in cxx_eval_call_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) () at ../../gcc/cp/semantics.c:6676
#114 0x000000000069ea86 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7676
#115 0x000000000069f869 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:6789
#116 0x000000000069f6ab in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7793
#117 0x000000000069f1b5 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7697
#118 0x00000000006a5b5f in cxx_eval_call_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) () at ../../gcc/cp/semantics.c:6676
#119 0x000000000069ea86 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7676
#120 0x000000000069f869 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:6789
#121 0x000000000069f6ab in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7793
#122 0x000000000069f1b5 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7697
#123 0x00000000006a5b5f in cxx_eval_call_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) () at ../../gcc/cp/semantics.c:6676
#124 0x000000000069ea86 in cxx_eval_constant_expression(constexpr_call const*,
tree_node*, bool, bool, bool*) [clone .part.62] () at
../../gcc/cp/semantics.c:7676
#125 0x00000000006a1c1d in cxx_eval_outermost_constant_expr(tree_node*, bool)
() at ../../gcc/cp/semantics.c:7976
#126 0x00000000006a2104 in maybe_constant_value(tree_node*) () at
../../gcc/cp/semantics.c:8080
#127 0x00000000006a2259 in maybe_constant_init(tree_node*) () at
../../gcc/cp/semantics.c:8097
#128 0x00000000005ba0f8 in store_init_value(tree_node*, tree_node*,
vec<tree_node*, va_gc, vl_embed>**, int) () at ../../gcc/cp/typeck2.c:717
#129 0x000000000053cca1 in check_initializer(tree_node*, tree_node*, int,
vec<tree_node*, va_gc, vl_embed>**) () at ../../gcc/cp/decl.c:5715
#130 0x000000000054f816 in cp_finish_decl(tree_node*, tree_node*, bool,
tree_node*, int) () at ../../gcc/cp/decl.c:6323
#131 0x0000000000628f44 in cp_parser_init_declarator(cp_parser*,
cp_decl_specifier_seq*, vec<deferred_access_check, va_gc, vl_embed>*, bool,
bool, int, bool*, tree_node**) ()
    at ../../gcc/cp/parser.c:16006
#132 0x00000000006297bf in cp_parser_simple_declaration(cp_parser*, bool,
tree_node**) () at ../../gcc/cp/parser.c:10546
#133 0x000000000062b668 in cp_parser_block_declaration(cp_parser*, bool) () at
../../gcc/cp/parser.c:10427
#134 0x000000000062c731 in cp_parser_declaration_statement(cp_parser*) () at
../../gcc/cp/parser.c:10071
#135 0x0000000000614e18 in cp_parser_statement(cp_parser*, tree_node*, bool,
bool*) () at ../../gcc/cp/parser.c:8846
#136 0x00000000006160bf in cp_parser_statement_seq_opt(cp_parser*, tree_node*)
() at ../../gcc/cp/parser.c:9118
#137 0x0000000000616207 in cp_parser_compound_statement(cp_parser*, tree_node*,
bool, bool) () at ../../gcc/cp/parser.c:9072
#138 0x0000000000627714 in
cp_parser_ctor_initializer_opt_and_function_body(cp_parser*, bool) () at
../../gcc/cp/parser.c:17648
#139 0x00000000006287d0 in
cp_parser_function_definition_after_declarator(cp_parser*, bool) () at
../../gcc/cp/parser.c:21641
#140 0x00000000006293af in cp_parser_init_declarator(cp_parser*,
cp_decl_specifier_seq*, vec<deferred_access_check, va_gc, vl_embed>*, bool,
bool, int, bool*, tree_node**) ()
    at ../../gcc/cp/parser.c:21562
#141 0x00000000006297bf in cp_parser_simple_declaration(cp_parser*, bool,
tree_node**) () at ../../gcc/cp/parser.c:10546
#142 0x000000000062b668 in cp_parser_block_declaration(cp_parser*, bool) () at
../../gcc/cp/parser.c:10427
#143 0x00000000006344ec in cp_parser_declaration(cp_parser*) () at
../../gcc/cp/parser.c:10324
#144 0x000000000063311e in cp_parser_declaration_seq_opt(cp_parser*) () at
../../gcc/cp/parser.c:10210
#145 0x0000000000634a63 in c_parse_file() () at ../../gcc/cp/parser.c:3792
#146 0x000000000073b465 in c_common_parse_file() ()

 phase setup             :   0.01 ( 0%) usr   0.01 ( 0%) sys   0.02 ( 0%) wall 
  1304 kB ( 0%) ggc
 phase parsing           :  80.67 (78%) usr   1.94 (97%) sys  82.60 (78%) wall
3423352 kB (100%) ggc
 phase opt and generate  :  23.22 (22%) usr   0.05 ( 3%) sys  23.27 (22%) wall 
   365 kB ( 0%) ggc
 |name lookup            :   0.09 ( 0%) usr   0.01 ( 0%) sys   0.08 ( 0%) wall 
  1038 kB ( 0%) ggc
 |overload resolution    :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
   151 kB ( 0%) ggc
 garbage collection      :  46.47 (45%) usr   0.05 ( 3%) sys  46.51 (44%) wall 
     0 kB ( 0%) ggc
 callgraph optimization  :   0.06 ( 0%) usr   0.00 ( 0%) sys   0.07 ( 0%) wall 
    19 kB ( 0%) ggc
 ipa inlining heuristics :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
    45 kB ( 0%) ggc
 preprocessing           :   0.00 ( 0%) usr   0.02 ( 1%) sys   0.03 ( 0%) wall 
   316 kB ( 0%) ggc
 parser (global)         :   0.11 ( 0%) usr   0.04 ( 2%) sys   0.12 ( 0%) wall 
  6727 kB ( 0%) ggc
 parser struct body      :   0.08 ( 0%) usr   0.00 ( 0%) sys   0.08 ( 0%) wall 
  2707 kB ( 0%) ggc
 parser enumerator list  :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall 
   110 kB ( 0%) ggc
 parser function body    :  57.05 (55%) usr   1.85 (92%) sys  58.88 (56%) wall
3408859 kB (100%) ggc
 parser inl. func. body  :   0.01 ( 0%) usr   0.01 ( 0%) sys   0.02 ( 0%) wall 
   296 kB ( 0%) ggc
 parser inl. meth. body  :   0.02 ( 0%) usr   0.01 ( 0%) sys   0.06 ( 0%) wall 
  1090 kB ( 0%) ggc
 template instantiation  :   0.05 ( 0%) usr   0.01 ( 1%) sys   0.07 ( 0%) wall 
  3273 kB ( 0%) ggc
 integration             :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall 
    11 kB ( 0%) ggc
 tree operand scan       :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
    19 kB ( 0%) ggc
 tree FRE                :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall 
     5 kB ( 0%) ggc
 scheduling 2            :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
     2 kB ( 0%) ggc
 TOTAL                 : 103.90             2.00           105.89           
3425092 kB