Do not allocate huge array in output_in_order.

Message ID ba246671-eb9c-5c77-8a1c-d7d857883a00@suse.cz
State New
Headers show
Series
  • Do not allocate huge array in output_in_order.
Related show

Commit Message

Martin Liška July 30, 2020, 8:02 a.m.
We noticed that when analyzing LTRANS memory peak that happens right
after the start:
https://gist.github.com/marxin/223890df4d8d8e490b6b2918b77dacad

In case of chrome, we have symtab->order == 200M, so we allocate
16B * 200M = 3.2GB.

Patch can bootstrap on x86_64-linux-gnu and survives regression tests.

Ready to be installed?
Thanks,
Martin

gcc/ChangeLog:

	* cgraph.h: Remove leading empty lines.
	* cgraphunit.c (enum cgraph_order_sort_kind): Remove
	ORDER_UNDEFINED.
	(struct cgraph_order_sort): Add constructors.
	(cgraph_order_sort::process): New.
	(cgraph_order_cmp): New.
	(output_in_order): Simplify and push nodes to vector.
---
  gcc/cgraph.h     |   2 -
  gcc/cgraphunit.c | 158 +++++++++++++++++++++++++----------------------
  2 files changed, 85 insertions(+), 75 deletions(-)

-- 
2.27.0

Comments

Jan Hubicka July 31, 2020, 9:37 a.m. | #1
> We noticed that when analyzing LTRANS memory peak that happens right

> after the start:

> https://gist.github.com/marxin/223890df4d8d8e490b6b2918b77dacad

> 

> In case of chrome, we have symtab->order == 200M, so we allocate

> 16B * 200M = 3.2GB.


200M is very large number even for overall number of symbols (and close
to overflow), so I guess we want to start adding overflow checks and
turn some stuff to 64bit...

There are many unnecesary orders assigned, so I will take care of this
first.
> 

> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.

> 

> Ready to be installed?

> Thanks,

> Martin

> 

> gcc/ChangeLog:

> 

> 	* cgraph.h: Remove leading empty lines.

> 	* cgraphunit.c (enum cgraph_order_sort_kind): Remove

> 	ORDER_UNDEFINED.

> 	(struct cgraph_order_sort): Add constructors.

> 	(cgraph_order_sort::process): New.

> 	(cgraph_order_cmp): New.

> 	(output_in_order): Simplify and push nodes to vector.


OK

Honza

Patch

diff --git a/gcc/cgraph.h b/gcc/cgraph.h
index cfae6e91da9..0211f08964f 100644
--- a/gcc/cgraph.h
+++ b/gcc/cgraph.h
@@ -2171,8 +2171,6 @@  private:
  /* Every top level asm statement is put into a asm_node.  */
  
  struct GTY(()) asm_node {
-
-
    /* Next asm node.  */
    asm_node *next;
    /* String for this asm node.  */
diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c
index ea9a34bda6f..0a95eb93ce2 100644
--- a/gcc/cgraphunit.c
+++ b/gcc/cgraphunit.c
@@ -2492,7 +2492,6 @@  expand_all_functions (void)
  
  enum cgraph_order_sort_kind
  {
-  ORDER_UNDEFINED = 0,
    ORDER_FUNCTION,
    ORDER_VAR,
    ORDER_VAR_UNDEF,
@@ -2501,6 +2500,30 @@  enum cgraph_order_sort_kind
  
  struct cgraph_order_sort
  {
+  /* Construct from a cgraph_node.  */
+  cgraph_order_sort (cgraph_node *node)
+  : kind (ORDER_FUNCTION), order (node->order)
+  {
+    u.f = node;
+  }
+
+  /* Construct from a varpool_node.  */
+  cgraph_order_sort (varpool_node *node)
+  : kind (node->definition ? ORDER_VAR : ORDER_VAR_UNDEF), order (node->order)
+  {
+    u.v = node;
+  }
+
+  /* Construct from a asm_node.  */
+  cgraph_order_sort (asm_node *node)
+  : kind (ORDER_ASM), order (node->order)
+  {
+    u.a = node;
+  }
+
+  /* Assembly cgraph_order_sort based on its type.  */
+  void process ();
+
    enum cgraph_order_sort_kind kind;
    union
    {
@@ -2508,8 +2531,45 @@  struct cgraph_order_sort
      varpool_node *v;
      asm_node *a;
    } u;
+  int order;
  };
  
+/* Assembly cgraph_order_sort based on its type.  */
+
+void
+cgraph_order_sort::process ()
+{
+  switch (kind)
+    {
+    case ORDER_FUNCTION:
+      u.f->process = 0;
+      u.f->expand ();
+      break;
+    case ORDER_VAR:
+      u.v->assemble_decl ();
+      break;
+    case ORDER_VAR_UNDEF:
+      assemble_undefined_decl (u.v->decl);
+      break;
+    case ORDER_ASM:
+      assemble_asm (u.a->asm_str);
+      break;
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Compare cgraph_order_sort by order.  */
+
+static int
+cgraph_order_cmp (const void *a_p, const void *b_p)
+{
+  const cgraph_order_sort *nodea = (const cgraph_order_sort *)a_p;
+  const cgraph_order_sort *nodeb = (const cgraph_order_sort *)b_p;
+
+  return nodea->order - nodeb->order;
+}
+
  /* Output all functions, variables, and asm statements in the order
     according to their order fields, which is the order in which they
     appeared in the file.  This implements -fno-toplevel-reorder.  In
@@ -2519,89 +2579,41 @@  struct cgraph_order_sort
  static void
  output_in_order (void)
  {
-  int max;
-  cgraph_order_sort *nodes;
    int i;
-  cgraph_node *pf;
-  varpool_node *pv;
-  asm_node *pa;
-  max = symtab->order;
-  nodes = XCNEWVEC (cgraph_order_sort, max);
+  cgraph_node *cnode;
+  varpool_node *vnode;
+  asm_node *anode;
+  auto_vec<cgraph_order_sort> nodes;
+  cgraph_order_sort *node;
  
-  FOR_EACH_DEFINED_FUNCTION (pf)
-    {
-      if (pf->process && !pf->thunk.thunk_p && !pf->alias)
-	{
-	  if (!pf->no_reorder)
-	    continue;
-	  i = pf->order;
-	  gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
-	  nodes[i].kind = ORDER_FUNCTION;
-	  nodes[i].u.f = pf;
-	}
-    }
+  FOR_EACH_DEFINED_FUNCTION (cnode)
+    if (cnode->process && !cnode->thunk.thunk_p
+	&& !cnode->alias && cnode->no_reorder)
+      nodes.safe_push (cgraph_order_sort (cnode));
  
    /* There is a similar loop in symbol_table::output_variables.
       Please keep them in sync.  */
-  FOR_EACH_VARIABLE (pv)
-    {
-      if (!pv->no_reorder)
-	continue;
-      if (DECL_HARD_REGISTER (pv->decl)
-	  || DECL_HAS_VALUE_EXPR_P (pv->decl))
-	continue;
-      i = pv->order;
-      gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
-      nodes[i].kind = pv->definition ? ORDER_VAR : ORDER_VAR_UNDEF;
-      nodes[i].u.v = pv;
-    }
-
-  for (pa = symtab->first_asm_symbol (); pa; pa = pa->next)
-    {
-      i = pa->order;
-      gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
-      nodes[i].kind = ORDER_ASM;
-      nodes[i].u.a = pa;
-    }
-
-  /* In toplevel reorder mode we output all statics; mark them as needed.  */
-
-  for (i = 0; i < max; ++i)
-    if (nodes[i].kind == ORDER_VAR)
-      nodes[i].u.v->finalize_named_section_flags ();
-
-  for (i = 0; i < max; ++i)
-    {
-      switch (nodes[i].kind)
-	{
-	case ORDER_FUNCTION:
-	  nodes[i].u.f->process = 0;
-	  nodes[i].u.f->expand ();
-	  break;
+  FOR_EACH_VARIABLE (vnode)
+    if (vnode->no_reorder
+	&& !DECL_HARD_REGISTER (vnode->decl)
+	&& !DECL_HAS_VALUE_EXPR_P (vnode->decl))
+      nodes.safe_push (cgraph_order_sort (vnode));
  
-	case ORDER_VAR:
-	  nodes[i].u.v->assemble_decl ();
-	  break;
+  for (anode = symtab->first_asm_symbol (); anode; anode = anode->next)
+    nodes.safe_push (cgraph_order_sort (anode));
  
-	case ORDER_VAR_UNDEF:
-	  assemble_undefined_decl (nodes[i].u.v->decl);
-	  break;
+  /* Sort nodes by order.  */
+  nodes.qsort (cgraph_order_cmp);
  
-	case ORDER_ASM:
-	  assemble_asm (nodes[i].u.a->asm_str);
-	  break;
-
-	case ORDER_UNDEFINED:
-	  break;
+  /* In toplevel reorder mode we output all statics; mark them as needed.  */
+  FOR_EACH_VEC_ELT (nodes, i, node)
+    if (node->kind == ORDER_VAR)
+      node->u.v->finalize_named_section_flags ();
  
-	default:
-	  gcc_unreachable ();
-	}
-    }
+  FOR_EACH_VEC_ELT (nodes, i, node)
+    node->process ();
  
    symtab->clear_asm_symbols ();
-
-  free (nodes);
  }
  
  static void