[patch][PR52640] Fix quadratic behavior with many referenced extern functions

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

Hello,

The test case for this bug triggeres O(extern_delcs**2) behavior
because value_member traverses the pending_assemble_externals list
from start to end for every new extern decl.

The solution I've picked, is to add a pointer set, and while there I
made pending_assemble_externals a VEC instead of a TREE_LIST. I've
also added a FIXME to clarify that this whole situation of having
places calling assemble_external is not desirable.

On gcc110, the test case compiles in ~4s with the patch, and ~24s
without. If I add LIM5(Y) and LIM5(Z), the compile time is ~15s with
the patch, and ~372s without the patch. I am not sure what is
reasonable for this kind of test case, but on a smaller machine the
test case will probably blow up if I add those two extra LIM5s.

Anyway. Bootstrapped&tested on powerpc64-unknown-linux-gnu.
OK for trunk?
OK for all open release branches too?

Ciao!
Steven

gcc/
	* varasm.c (pending_assemble_externals): Make a VEC.
	(pending_assemble_externals_set): New pointer set.
	(process_pending_assemble_externals): Traverse the VEC instead
	of the TREE_LIST. Destroy the pointer set.
	(assemble_external): See if decl is in pending_assemble_externals_set,
	and add it to pending_assemble_externals if necessary.
	(init_varasm_once): Allocate pending_assemble_externals and
	pending_assemble_externals_set.

testsuite/
	* gcc.c-torture/compile/limits-externdecl.c: New test for PR62640.

Attachment: PR52640.diff.txt
Description: Text document