Re: [PATCH] PR/7344, O(n^2) branch prediction

[tm <tm at mail dot kloo dot net>]

On Sat, 7 Sep 2002, Brad Lucier wrote:

> I just checked the statement counts in predict.c.gcov, and, indeed, your
> patch reduces them.  It's just that there are other O(N^2) loops in
> predict.c, and the one you killed wasn't the main one for CPU time.
> 
> The gcov files from a few weeks back for this file are at
> 
> http://www.math.purdue.edu/~lucier/gcovs.tgz
> 
> and the gcov files from yesterday's source plus your patch on the same
> file are at
> 
> http://www.math.purdue.edu/~lucier/tm-gcovs.tgz
> 
> Brad
> 

This testcase runs out of memory on my system after about 20 seconds.

It runs out of memory because:

(xgdb) print n_basic_blocks
$2 = 17902

...and then this code is executed in cfgbuild.c:

	  /* If this is a computed jump, then mark it as reaching
	     everything on the label_value_list and forced_labels
list.  */
	  else if (computed_jump_p (insn))
	    {
	      current_function_has_computed_jump = 1;

	      for (x = label_value_list; x; x = XEXP (x, 1))
		make_label_edge (edge_cache, bb, XEXP (x, 0),
EDGE_ABNORMAL);

	      for (x = forced_labels; x; x = XEXP (x, 1))
		make_label_edge (edge_cache, bb, XEXP (x, 0),
EDGE_ABNORMAL);
	   }

so it attempts to create 17,902 edges and runs out of memory.

I'm guessing we need to handle computed gotos better; maybe we can mark it
as reaching "everything" without having to create thousands of edges?
Maybe a special edge type or something?

Toshi