PATCH implement line-map cache

[Per Bothner <per at bothner dot com>]

The attached patch implements a simple cache for linemap_lookup.
In the current compiler it doesn't make any difference, since
linemap_lookup is not called very often.  However, if we're going
to replace location_t by the fileline typedef in line-map.h (as I've
submitted some unfinished patches for), then it is likely to get
called a lot more.

So there is probably no point in checking this into the 3.4 trunk,
but I would like to check it into the tree-ssa branch.  Unless I
hear objections, that is what I will do.
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/


2003-11-28  Per Bothner  <pbothner@apple.com>

	Implement a cache for linemap_lookup.
	* line-map.h (struct_line_maps):  Add cache field.
	* line-map.c (linemap_init):  Zero cache field.
	(linemap_add):  Set cache field to offset of newly allocated map.
	(linemap_lookup):  Use and set cache field.

Index: line-map.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/line-map.h,v
retrieving revision 1.15
diff -u -p -r1.15 line-map.h
--- line-map.h	19 Aug 2003 21:04:38 -0000	1.15
+++ line-map.h	28 Nov 2003 17:44:22 -0000
@@ -60,6 +60,8 @@ struct line_maps
   unsigned int allocated;
   unsigned int used;
 
+  unsigned int cache;
+
   /* The most recently listed include stack, if any, starts with
      LAST_LISTED as the topmost including file.  -1 indicates nothing
      has been listed yet.  */
Index: line-map.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/line-map.c,v
retrieving revision 1.15
diff -u -p -r1.15 line-map.c
--- line-map.c	30 Jul 2003 06:43:33 -0000	1.15
+++ line-map.c	28 Nov 2003 17:44:22 -0000
@@ -32,12 +32,13 @@ static void trace_include (const struct 
 void
 linemap_init (struct line_maps *set)
 {
-  set->maps = 0;
+  set->maps = NULL;
   set->allocated = 0;
   set->used = 0;
   set->last_listed = -1;
   set->trace_includes = false;
   set->depth = 0;
+  set->cache = 0;
 }
 
 /* Free a line map set.  */
@@ -89,7 +90,7 @@ linemap_add (struct line_maps *set, enum
       set->maps = xrealloc (set->maps, set->allocated * sizeof (struct line_map));
     }
 
-  map = &set->maps[set->used++];
+  map = &set->maps[set->used];
 
   if (to_file && *to_file == '\0')
     to_file = "<stdin>";
@@ -108,7 +109,6 @@ linemap_add (struct line_maps *set, enum
 	  if (to_file == NULL)
 	    {
 	      set->depth--;
-	      set->used--;
 	      return NULL;
 	    }
 	  error = true;
@@ -141,6 +141,7 @@ linemap_add (struct line_maps *set, enum
   map->from_line = from_line;
   map->to_file = to_file;
   map->to_line = to_line;
+  set->cache = set->used++;
 
   if (reason == LC_ENTER)
     {
@@ -168,10 +169,24 @@ linemap_add (struct line_maps *set, enum
 const struct line_map *
 linemap_lookup (struct line_maps *set, unsigned int line)
 {
-  unsigned int md, mn = 0, mx = set->used;
+  unsigned int md, mn, mx;
+  const struct line_map *cached;
 
-  if (mx == 0)
-    abort ();
+  mn = set->cache;
+  mx = set->used;
+  
+  cached = &set->maps[mn];
+  /* We should get a segfault if no line_maps have been added yet. */
+  if (line >= cached->from_line)
+    {
+      if (mn + 1 == mx || line < cached[1].from_line)
+	return cached;
+    }
+  else
+    {
+      mx = mn;
+      mn = 0;
+    }
 
   while (mx - mn > 1)
     {
@@ -182,6 +197,7 @@ linemap_lookup (struct line_maps *set, u
 	mn = md;
     }
 
+  set->cache = mn;
   return &set->maps[mn];
 }