[patch] reversing dependency order

[DJ Delorie]

As multi-cpu machines become more and more common, we (specifically,
the gcc team) are running into more and more makefile dependency bugs
that are detected only randomly via parallel makes (make -jN).  In an
effort to force these types of bugs, I added an option to make (diffs
attached) that reverses the order in which dependencies are checked,
hoping that such an option would help us discover cases where we rely
on the order of dependencies instead of coding an explicit dependency.

For example, consider:

    all : a b c

If "b" requires the output of "a", it will happen to work with -j1
even though the b:a dependency is not stated.  However, with -j2 it
will fail.  The new option would build "c", "b", and then "a",
hopefully making hidden errors more obvious.

I have not yet documented this formally as I wanted to defer that
until I knew if this type of option would be acceptable or not.


diff -p3 -r make-3.80-orig/filedef.h make-3.80/filedef.h
*** make-3.80-orig/filedef.h    2002-08-01 09:16:57.000000000 -0400
--- make-3.80/filedef.h 2003-10-02 20:39:56.000000000 -0400
*************** extern void notice_finished_file PARAMS 
*** 113,118 ****
--- 113,120 ----
  extern void init_hash_files PARAMS ((void));
  extern char *build_target_list PARAMS ((char *old_list));
  
+ extern void reverse_deps ();
+ 
  #if FILE_TIMESTAMP_HI_RES
  # define FILE_TIMESTAMP_STAT_MODTIME(fname, st) \
      file_timestamp_cons (fname, (st).st_mtime, (st).st_mtim.ST_MTIM_NSEC)
diff -p3 -r make-3.80-orig/main.c make-3.80/main.c
*** make-3.80-orig/main.c       2002-08-09 21:27:17.000000000 -0400
--- make-3.80/main.c    2003-10-02 22:09:43.000000000 -0400
*************** static int print_usage_flag = 0;
*** 250,255 ****
--- 250,261 ----
  
  int warn_undefined_variables_flag;
  
+ /* If nonzero, reverse the order in which the dependencies of each
+    target are rebuilt.  This is for debugging Makefile
+    dependencies.  */
+ 
+ int reverse_deps_flag;
+ 
  /* If nonzero, always build all targets, regardless of whether
     they appear out of date or not.  */
  
*************** static const char *const usage[] =
*** 325,330 ****
--- 331,338 ----
                                Consider FILE to be infinitely new.\n"),
      N_("\
    --warn-undefined-variables  Warn when an undefined variable is 
referenced.\n"),
+     N_("\
+   --reverse-deps              Reverse the order of dependencies for each 
target.\n"),
      NULL
    };
  
*************** static const struct command_switch switc
*** 385,390 ****
--- 393,400 ----
      { 'W', string, (char *) &new_files, 0, 0, 0, 0, 0, "what-if" },
      { CHAR_MAX+4, flag, (char *) &warn_undefined_variables_flag, 1, 1, 0, 0, 
0,
        "warn-undefined-variables" },
+     { CHAR_MAX+5, flag, (char *) &reverse_deps_flag, 1, 1, 0, 0, 0,
+       "reverse-deps" },
      { '\0', }
    };
  
diff -p3 -r make-3.80-orig/make.h make-3.80/make.h
*** make-3.80-orig/make.h       2002-09-11 12:55:44.000000000 -0400
--- make-3.80/make.h    2003-10-02 23:46:33.000000000 -0400
*************** extern char **environ;
*** 489,495 ****
  extern int just_print_flag, silent_flag, ignore_errors_flag, keep_going_flag;
  extern int print_data_base_flag, question_flag, touch_flag, always_make_flag;
  extern int env_overrides, no_builtin_rules_flag, no_builtin_variables_flag;
! extern int print_version_flag, print_directory_flag;
  extern int warn_undefined_variables_flag, posix_pedantic, not_parallel;
  extern int clock_skew_detected;
  
--- 489,495 ----
  extern int just_print_flag, silent_flag, ignore_errors_flag, keep_going_flag;
  extern int print_data_base_flag, question_flag, touch_flag, always_make_flag;
  extern int env_overrides, no_builtin_rules_flag, no_builtin_variables_flag;
! extern int print_version_flag, print_directory_flag, reverse_deps_flag;
  extern int warn_undefined_variables_flag, posix_pedantic, not_parallel;
  extern int clock_skew_detected;
  
diff -p3 -r make-3.80-orig/remake.c make-3.80/remake.c
*** make-3.80-orig/remake.c     2002-08-07 20:11:19.000000000 -0400
--- make-3.80/remake.c  2003-10-02 23:45:26.000000000 -0400
*************** update_file_1 (file, depth)
*** 348,355 ****
    register FILE_TIMESTAMP this_mtime;
    int noexist, must_make, deps_changed;
    int dep_status = 0;
!   register struct dep *d, *lastd;
    int running = 0;
  
    DBF (DB_VERBOSE, _("Considering target file `%s'.\n"));
  
--- 348,356 ----
    register FILE_TIMESTAMP this_mtime;
    int noexist, must_make, deps_changed;
    int dep_status = 0;
!   register struct dep *d, *lastd, **deplist;
    int running = 0;
+   int depn, depi;
  
    DBF (DB_VERBOSE, _("Considering target file `%s'.\n"));
  
*************** update_file_1 (file, depth)
*** 431,443 ****
    /* Update all non-intermediate files we depend on, if necessary,
       and see whether any of them is more recent than this file.  */
  
!   lastd = 0;
!   d = file->deps;
!   while (d != 0)
      {
        FILE_TIMESTAMP mtime;
        int maybe_make;
  
        check_renamed (d->file);
  
        mtime = file_mtime (d->file);
--- 432,449 ----
    /* Update all non-intermediate files we depend on, if necessary,
       and see whether any of them is more recent than this file.  */
  
!   for (depn=0, d=file->deps; d; depn++, d=d->next);
!   deplist = (struct dep **) malloc (depn * sizeof (struct dep *));
!   for (depi=0, d=file->deps; d; depi++, d=d->next)
!     deplist[depi] = d;
! 
!   for (depi = 0; depi < depn; depi ++)
      {
        FILE_TIMESTAMP mtime;
        int maybe_make;
  
+       d = deplist[reverse_deps_flag ? depn-depi-1 : depi];
+ 
        check_renamed (d->file);
  
        mtime = file_mtime (d->file);
*************** update_file_1 (file, depth)
*** 445,460 ****
  
        if (is_updating (d->file))
        {
          error (NILF, _("Circular %s <- %s dependency dropped."),
                 file->name, d->file->name);
          /* We cannot free D here because our the caller will still have
             a reference to it when we were called recursively via
             check_dep below.  */
!         if (lastd == 0)
            file->deps = d->next;
          else
!           lastd->next = d->next;
!         d = d->next;
          continue;
        }
  
--- 451,468 ----
  
        if (is_updating (d->file))
        {
+         struct dep *d2;
          error (NILF, _("Circular %s <- %s dependency dropped."),
                 file->name, d->file->name);
          /* We cannot free D here because our the caller will still have
             a reference to it when we were called recursively via
             check_dep below.  */
!         if (file->deps == d)
            file->deps = d->next;
          else
!           for (d2=file->deps; d2; d2=d2->next)
!             if (d2->next == d)
!               d2->next = d->next;
          continue;
        }
  
*************** update_file_1 (file, depth)
*** 484,492 ****
  
        if (!running)
        d->changed = file_mtime (d->file) != mtime;
- 
-       lastd = d;
-       d = d->next;
      }
  
    /* Now we know whether this target needs updating.
--- 492,497 ----