Fix performance degradation introduced by the second expansion feature.

I did this by adding intelligence into the algorithm such that the
second expansion was only actually performed when the prerequisite list
contained at least one "$", so we knew it is actually needed.

Without this we were using up a LOT more memory, since every single
target (even ones never used by make) had their file variables
initialized.  This also used a lot more CPU, since we needed to create
and populate a new variable hash table for every target.

There is one issue remaining with this feature: it leaks memory.  In
pattern_search() we now initialize the file variables for every pattern
target, which allocates a hash table, etc.  However, sometimes we
recursively invoke pattern_search() (for intermediate files) with an
automatic variable (alloca() I believe) as the file.  When that function
returns, obviously, the file variable hash memory is lost.

7 files changed, 117 insertions, 58 deletions

diff --git a/ChangeLog b/ChangeLog
index 03cb071..4d443eb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,30 @@
+2005-04-12  Paul D. Smith  <psmith@gnu.org>
+
+	The second expansion feature causes significant slowdown.  Timing
+	a complex makefile (GCC 4.1) shows a slowdown from .25s to just
+	read the makefile before the feature, to 11+s to do the same
+	operations after the feature.  Additionally, memory usage
+	increased drastically.  To fix this I added some intelligence that
+	avoids the overhead of the second expansion unless it's required.
+
+	* dep.h: Add a new boolean field, need_2nd_expansion.
+
+	* read.c (eval): When creating the struct dep for the target,
+	check if the name contains a "$"; if so set need_2nd_expansion to 1.
+	(record_files): If there's a "%" in a static pattern rule, it gets
+	converted to "$*" so set need_2nd_expansion to 1.
+
+	* file.c (expand_deps): Rework to be more efficient.  Only perform
+	initialize_file_variables(), set_file_variables(), and
+	variable_expand_for_file() if the need_2nd_expansion is set.
+
+	* implicit.c (pattern_search): Default need_2nd_expansion to 0.
+	(pattern_search): Ditto.
+	* main.c (handle_non_switch_argument): Ditto.
+	(main): Ditto.
+	* read.c (read_all_makefiles): Ditto.
+	(eval_makefile): Ditto.
+
 2005-04-07  Paul D. Smith  <psmith@gnu.org>
 
 	* main.c (main) [WINDOWS32]: Export PATH to sub-shells, not Path.
diff --git a/dep.h b/dep.h
index 01c31a3..7e6a853 100644
--- a/dep.h
+++ b/dep.h
@@ -40,6 +40,7 @@ struct dep
     struct file *file;
     unsigned int changed : 8;
     unsigned int ignore_mtime : 1;
+    unsigned int need_2nd_expansion : 1;
   };
 
 
diff --git a/file.c b/file.c
index 1c34ff4..9f9ddb5 100644
--- a/file.c
+++ b/file.c
@@ -418,28 +418,40 @@ set_intermediate (const void *item)
 static void
 expand_deps (struct file *f)
 {
-  register struct dep *d, *d1;
+  struct dep *d, *d1;
   struct dep *new = 0;
   struct dep *old = f->deps;
   unsigned int last_dep_has_cmds = f->updating;
+  int initialized = 0;
 
   f->updating = 0;
   f->deps = 0;
 
-  /* We are going to do second expansion so initialize file
-     variables for the file. */
-  initialize_file_variables (f, 0);
-
   for (d = old; d != 0; d = d->next)
     {
       if (d->name != 0)
         {
           char *p;
-          struct dep **d_ptr;
 
-          set_file_variables (f);
+          /* If we need a second expansion on these, set up the file
+             variables, etc.  It takes a lot of extra memory and processing
+             to do this, so only do it if it's needed.  */
+          if (! d->need_2nd_expansion)
+            p = d->name;
+          else
+            {
+              /* We are going to do second expansion so initialize file
+                 variables for the file. */
+              if (!initialized)
+                {
+                  initialize_file_variables (f, 0);
+                  initialized = 1;
+                }
 
-          p = variable_expand_for_file (d->name, f);
+              set_file_variables (f);
+
+              p = variable_expand_for_file (d->name, f);
+            }
 
           /* Parse the dependencies.  */
           new = (struct dep *)
@@ -452,8 +464,8 @@ expand_deps (struct file *f)
               /* Files that follow '|' are special prerequisites that
                  need only exist in order to satisfy the dependency.
                  Their modification times are irrelevant.  */
+              struct dep **d_ptr;
 
-              struct dep *d;
               for (d_ptr = &new; *d_ptr; d_ptr = &(*d_ptr)->next)
                 ;
               ++p;
@@ -463,8 +475,8 @@ expand_deps (struct file *f)
                   parse_file_seq (&p, '\0', sizeof (struct dep), 1),
                   sizeof (struct dep));
 
-              for (d = *d_ptr; d != 0; d = d->next)
-                d->ignore_mtime = 1;
+              for (d1 = *d_ptr; d1 != 0; d1 = d1->next)
+                d1->ignore_mtime = 1;
             }
 
           /* Enter them as files. */
@@ -476,6 +488,7 @@ expand_deps (struct file *f)
               else
                 free (d1->name);
               d1->name = 0;
+              d1->need_2nd_expansion = 0;
             }
 
           /* Add newly parsed deps to f->deps. If this is the last
@@ -492,15 +505,17 @@ expand_deps (struct file *f)
             {
               if (d->next == 0 && last_dep_has_cmds)
                 {
+                  struct dep **d_ptr;
                   for (d_ptr = &new; *d_ptr; d_ptr = &(*d_ptr)->next)
-                        ;
+                    ;
 
                   *d_ptr = f->deps;
                   f->deps = new;
                 }
               else
                 {
-                  for (d_ptr = &(f->deps); *d_ptr; d_ptr = &(*d_ptr)->next)
+                  struct dep **d_ptr;
+                  for (d_ptr = &f->deps; *d_ptr; d_ptr = &(*d_ptr)->next)
                     ;
 
                   *d_ptr = new;
@@ -509,7 +524,7 @@ expand_deps (struct file *f)
         }
     }
 
-  free_ns_chain ((struct nameseq*)old);
+  free_ns_chain ((struct nameseq *) old);
 }
 
 /* For each dependency of each file, make the `struct dep' point
@@ -521,12 +536,12 @@ expand_deps (struct file *f)
 void
 snap_deps (void)
 {
-  register struct file *f;
-  register struct file *f2;
-  register struct dep *d;
-  register struct file **file_slot_0;
-  register struct file **file_slot;
-  register struct file **file_end;
+  struct file *f;
+  struct file *f2;
+  struct dep *d;
+  struct file **file_slot_0;
+  struct file **file_slot;
+  struct file **file_end;
 
   /* Perform second expansion and enter each dependency
      name as a file. */
diff --git a/implicit.c b/implicit.c
index 338a29f..67f0559 100644
--- a/implicit.c
+++ b/implicit.c
@@ -509,19 +509,19 @@ pattern_search (struct file *file, int archive,
                     break; /* No more words */
 
                   /* If the dependency name has %, substitute the stem.
-                     Watch out, we are going to do something very smart
-                     here. If we just replace % with the stem value,
-                     later, when we do the second expansion, we will
-                     re-expand this stem value once again. This is not
-                     good especially if you have certain characters in
-                     your setm (like $).
+                     Watch out, we are going to do something tricky here. If
+                     we just replace % with the stem value, later, when we do
+                     the second expansion, we will re-expand this stem value
+                     once again. This is not good especially if you have
+                     certain characters in your setm (like $).
 
-                     Instead, we will replace % with $* and allow the
-                     second expansion to take care of it for us. This
-                     way (since $* is a simple variable) there won't
-                     be additional re-expansion of the stem.*/
+                     Instead, we will replace % with $* and allow the second
+                     expansion to take care of it for us. This way (since $*
+                     is a simple variable) there won't be additional
+                     re-expansion of the stem.  */
 
-                  for (p2 = p; p2 < p + len && *p2 != '%'; ++p2);
+                  for (p2 = p; p2 < p + len && *p2 != '%'; ++p2)
+                    ;
 
                   if (p2 < p + len)
                     {
@@ -836,6 +836,7 @@ pattern_search (struct file *file, int archive,
 
       dep = (struct dep *) xmalloc (sizeof (struct dep));
       dep->ignore_mtime = d->ignore_mtime;
+      dep->need_2nd_expansion = 0;
       s = d->name; /* Hijacking the name. */
       d->name = 0;
       if (recursions == 0)
@@ -908,6 +909,7 @@ pattern_search (struct file *file, int archive,
 	  struct dep *new = (struct dep *) xmalloc (sizeof (struct dep));
 	  /* GKM FIMXE: handle '|' here too */
 	  new->ignore_mtime = 0;
+	  new->need_2nd_expansion = 0;
 	  new->name = p = (char *) xmalloc (rule->lens[i] + fullstemlen + 1);
 	  bcopy (rule->targets[i], p,
 		 rule->suffixes[i] - rule->targets[i] - 1);
diff --git a/main.c b/main.c
index 014c41f..b99bf27 100644
--- a/main.c
+++ b/main.c
@@ -2125,6 +2125,7 @@ main (int argc, char **argv, char **envp)
             goals->next = 0;
             goals->name = 0;
             goals->ignore_mtime = 0;
+            goals->need_2nd_expansion = 0;
             goals->file = default_goal_file;
           }
       }
@@ -2290,6 +2291,7 @@ handle_non_switch_argument (char *arg, int env)
       lastgoal->name = 0;
       lastgoal->file = f;
       lastgoal->ignore_mtime = 0;
+      lastgoal->need_2nd_expansion = 0;
 
       {
         /* Add this target name to the MAKECMDGOALS variable. */
diff --git a/read.c b/read.c
index 15455b8..fb62ca6 100644
--- a/read.c
+++ b/read.c
@@ -253,6 +253,7 @@ read_all_makefiles (char **makefiles)
 	      d->file = enter_file (*p);
 	      d->file->dontcare = 1;
               d->ignore_mtime = 0;
+              d->need_2nd_expansion = 0;
 	      /* Tell update_goal_chain to bail out as soon as this file is
 		 made, and main not to die if we can't make this file.  */
 	      d->changed = RM_DONTCARE;
@@ -372,6 +373,7 @@ eval_makefile (char *filename, int flags)
   filename = deps->file->name;
   deps->changed = flags;
   deps->ignore_mtime = 0;
+  deps->need_2nd_expansion = 0;
   if (flags & RM_DONTCARE)
     deps->file->dontcare = 1;
 
@@ -1167,9 +1169,21 @@ eval (struct ebuffer *ebuf, int set_default)
 
         if (beg <= end && *beg != '\0')
           {
+            char *top;
+            const char *fromp = beg;
+
+            /* Make a copy of the dependency string.  Note if we find '$'.  */
             deps = (struct dep*) xmalloc (sizeof (struct dep));
             deps->next = 0;
-            deps->name = savestring (beg, end - beg + 1);
+            deps->name = top = (char *) xmalloc (end - beg + 2);
+            deps->need_2nd_expansion = 0;
+            while (fromp <= end)
+              {
+                if (*fromp == '$')
+                  deps->need_2nd_expansion = 1;
+                *(top++) = *(fromp++);
+              }
+            *top = '\0';
             deps->file = 0;
           }
         else
@@ -1194,11 +1208,10 @@ eval (struct ebuffer *ebuf, int set_default)
             commands[commands_idx++] = '\n';
           }
 
-        /* Determine if this target should be made default. We used
-           to do this in record_files() but because of the delayed
-           target recording and because preprocessor directives are
-           legal in target's commands it is too late. Consider this
-           fragment for example:
+        /* Determine if this target should be made default. We used to do
+           this in record_files() but because of the delayed target recording
+           and because preprocessor directives are legal in target's commands
+           it is too late. Consider this fragment for example:
 
            foo:
 
@@ -1206,10 +1219,10 @@ eval (struct ebuffer *ebuf, int set_default)
               ...
            endif
 
-           Because the target is not recorded until after ifeq
-           directive is evaluated the .DEFAULT_TARGET does not
-           contain foo yet as one would expect. Because of this
-           we have to move some of the logic here. */
+           Because the target is not recorded until after ifeq directive is
+           evaluated the .DEFAULT_TARGET does not contain foo yet as one
+           would expect. Because of this we have to move some of the logic
+           here.  */
 
         if (**default_target_name == '\0' && set_default)
           {
@@ -1232,7 +1245,7 @@ eval (struct ebuffer *ebuf, int set_default)
 #ifdef HAVE_DOS_PATHS
                     && strchr (name, '\\') == 0
 #endif
-                )
+                    )
                   continue;
 
 
@@ -1895,7 +1908,7 @@ record_files (struct nameseq *filenames, char *pattern, char *pattern_percent,
 
       /* If there are multiple filenames, copy the chain DEPS
 	 for all but the last one.  It is not safe for the same deps
-	 to go in more than one place in the data base.  */
+	 to go in more than one place in the database.  */
       this = nextf != 0 ? copy_dep_chain (deps) : deps;
 
       if (pattern != 0)
@@ -1912,22 +1925,20 @@ record_files (struct nameseq *filenames, char *pattern, char *pattern_percent,
 	      this = 0;
 	    }
 	  else
-	    {
-	      /* We use subst_expand to do the work of translating
-		 % to $* in the dependency line.  */
+            /* We use subst_expand to do the work of translating % to $* in
+               the dependency line.  */
 
-              if (this != 0 && find_percent (this->name) != 0)
-                {
-                  char *o;
-                  char *buffer = variable_expand ("");
+            if (this != 0 && find_percent (this->name) != 0)
+              {
+                char *o;
+                char *buffer = variable_expand ("");
 
-                  o = subst_expand (buffer, this->name, "%", "$*",
-                                    1, 2, 0);
+                o = subst_expand (buffer, this->name, "%", "$*", 1, 2, 0);
 
-		  free (this->name);
-		  this->name = savestring (buffer, o - buffer);
-		}
-	    }
+                free (this->name);
+                this->name = savestring (buffer, o - buffer);
+                this->need_2nd_expansion = 1;
+              }
 	}
 
       if (!two_colon)
@@ -2009,7 +2020,7 @@ record_files (struct nameseq *filenames, char *pattern, char *pattern_percent,
                       /* This is the rule without commands. Put its
                          dependencies at the end but before dependencies
                          from the rule with commands (if any). This way
-                         everyhting appears in makefile order.  */
+                         everything appears in makefile order.  */
 
                       if (f->cmds != 0)
                         {
@@ -2026,7 +2037,7 @@ record_files (struct nameseq *filenames, char *pattern, char *pattern_percent,
               /* This is a hack. I need a way to communicate to snap_deps()
                  that the last dependency line in this file came with commands
                  (so that logic in snap_deps() can put it in front and all
-                 this $< -logic works). I cannot's simply rely oon file->cmds
+                 this $< -logic works). I cannot simply rely on file->cmds
                  being not 0 because of the cases like the following:
 
                  foo: bar
diff --git a/rule.c b/rule.c
index dd0ebcb..152e7e6 100644
--- a/rule.c
+++ b/rule.c
@@ -206,6 +206,7 @@ convert_suffix_rule (char *target, char *source, struct commands *cmds)
       deps->next = 0;
       deps->name = depname;
       deps->ignore_mtime = 0;
+      deps->need_2nd_expansion = 0;
     }
 
   create_pattern_rule (names, percents, 0, deps, cmds, 0);