Bug 55442 - G++ uses up all my RAM when compiling a constexpr with exponential call graph
Summary: G++ uses up all my RAM when compiling a constexpr with exponential call graph
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 4.8.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-11-22 16:28 UTC by David Fendrich
Modified: 2015-10-23 06:44 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2012-11-22 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description David Fendrich 2012-11-22 16:28:26 UTC
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?
Comment 1 Jan Hubicka 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