Bug 17707

Summary:	[4.0 Regression] O(N^2) in cgraph_reset_static_var_maps
Product:	gcc	Reporter:	Serge Belyshev <belyshev>
Component:	tree-optimization	Assignee:	Not yet assigned to anyone <unassigned>
Status:	RESOLVED FIXED
Severity:	normal	CC:	gcc-bugs, pinskia
Priority:	P2	Keywords:	compile-time-hog
Version:	4.0.0
Target Milestone:	4.0.0
Host:		Target:
Build:		Known to work:
Known to fail:		Last reconfirmed:	2004-09-28 11:37:05
Bug Depends on:
Bug Blocks:	15678, 17278

Description Serge Belyshev 2004-09-28 08:06:13 UTC

This testcase (from bug 15678) shows quadratic time in cgraph_reset_static_var_maps:

#define F0(a) void a(){}
#define F1(a) F0(a##0) F0(a##1) F0(a##2) F0(a##3) F0(a##4) F0(a##5) F0(a##6)
#define F2(a) F1(a##0) F1(a##1) F1(a##2) F1(a##3) F1(a##4) F1(a##5) F1(a##6)
#define F3(a) F2(a##0) F2(a##1) F2(a##2) F2(a##3) F2(a##4) F2(a##5) F2(a##6)
#define F4(a) F3(a##0) F3(a##1) F3(a##2) F3(a##3) F3(a##4) F3(a##5) F3(a##6)
#define F5(a) F4(a##0)/*F4(a##1) F4(a##2) F3(a##3) F3(a##4) F3(a##5) F3(a##6)*/

F5(f)

Comment 1 Serge Belyshev 2004-09-28 09:43:17 UTC

(In reply to comment #0)

> #define F5(a) F4(a##0)/*F4(a##1) F4(a##2) F3(a##3) F3(a##4) F3(a##5) F3(a##6)*/
  	  			   	   ^^      ^^       ^^      ^^
					   these should be F4

Comment 2 Andrew Pinski 2004-09-28 11:37:04 UTC

Confirmed, I think I know where the problem is, I will look into it later today.

Comment 3 Andrew Pinski 2004-10-25 23:22:37 UTC

The code has been removed for 4.0.