tools/llvm-config/find-cycles.pl

   1 #!/usr/bin/perl
   2 #
   3 # Program:  find-cycles.pl
   4 #
   5 # Synopsis: Given a list of possibly cyclic dependencies, merge all the
   6 #           cycles.  This makes it possible to topologically sort the
   7 #           dependencies between different parts of LLVM.
   8 #
   9 # Syntax:   find-cycles.pl < LibDeps.txt > FinalLibDeps.txt
  10 #
  11 # Input:    cycmem1: cycmem2 dep1 dep2
  12 #           cycmem2: cycmem1 dep3 dep4
  13 #           boring: dep4
  14 #
  15 # Output:   cycmem1 cycmem2: dep1 dep2 dep3 dep4
  16 #           boring: dep4
  17 #
  18 # This file was written by Eric Kidd, and is placed into the public domain.
  19 #
  20
  21 use 5.006;
  22 use strict;
  23 use warnings;
  24
  25 my %DEPS;
  26 my @CYCLES;
  27 sub find_all_cycles;
  28
  29 # Read our dependency information.
  30 while (<>) {
  31     chomp;
  32     my ($module, $dependency_str) = /^\s*([^:]+):\s*(.*)\s*$/;
  33     die "Malformed data: $_" unless defined $dependency_str;
  34     my @dependencies = split(/ /, $dependency_str);
  35     $DEPS{$module} = \@dependencies;
  36 }
  37
  38 # Partition our raw dependencies into sets of cyclically-connected nodes.
  39 find_all_cycles();
  40
  41 # Print out the finished cycles, with their dependencies.
  42 my @output;
  43 my $cycles_found = 0;
  44 foreach my $cycle (@CYCLES) {
  45     my @modules = sort keys %{$cycle};
  46
  47     # Merge the dependencies of all modules in this cycle.
  48     my %dependencies;
  49     foreach my $module (@modules) {
  50         @dependencies{@{$DEPS{$module}}} = 1;
  51     }
  52
  53     # Prune the known cyclic dependencies.
  54     foreach my $module (@modules) {
  55         delete $dependencies{$module};
  56     }
  57
  58     # Warn about possible linker problems.
  59     my @archives = grep(/\.a$/, @modules);
  60     if (@archives > 1) {
  61         $cycles_found = $cycles_found + 1;
  62         print STDERR "find-cycles.pl: Circular dependency between *.a files:\n";
  63         print STDERR "find-cycles.pl:   ", join(' ', @archives), "\n";
  64         push @modules, @archives; # WORKAROUND: Duplicate *.a files. Ick.
  65     } elsif (@modules > 1) {
  66         $cycles_found = $cycles_found + 1;
  67         print STDERR "find-cycles.pl: Circular dependency between *.o files:\n";
  68         print STDERR "find-cycles.pl:   ", join(' ', @modules), "\n";
  69         push @modules, @modules; # WORKAROUND: Duplicate *.o files. Ick.
  70     }
  71
  72     # Add to our output.  (@modules is already as sorted as we need it to be.)
  73     push @output, (join(' ', @modules) . ': ' .
  74                    join(' ', sort keys %dependencies) . "\n");
  75 }
  76 print sort @output;
  77
  78 exit $cycles_found;
  79
  80 #==========================================================================
  81 #  Depedency Cycle Support
  82 #==========================================================================
  83 #  For now, we have cycles in our dependency graph.  Ideally, each cycle
  84 #  would be collapsed down to a single *.a file, saving us all this work.
  85 #
  86 #  To understand this code, you'll need a working knowledge of Perl 5,
  87 #  and possibly some quality time with 'man perlref'.
  88
  89 my %SEEN;
  90 my %CYCLES;
  91 sub find_cycles ($@);
  92 sub found_cycles ($@);
  93
  94 sub find_all_cycles {
  95     # Find all multi-item cycles.
  96     my @modules = sort keys %DEPS;
  97     foreach my $module (@modules) { find_cycles($module); }
  98
  99     # Build fake one-item "cycles" for the remaining modules, so we can
 100     # treat them uniformly.
 101     foreach my $module (@modules) {
 102         unless (defined $CYCLES{$module}) {
 103             my %cycle = ($module, 1);
 104             $CYCLES{$module} = \%cycle;
 105         }
 106     }
 107
 108     # Find all our unique cycles.  We have to do this the hard way because
 109     # we apparently can't store hash references as hash keys without making
 110     # 'strict refs' sad.
 111     my %seen;
 112     foreach my $cycle (values %CYCLES) {
 113         unless ($seen{$cycle}) {
 114             $seen{$cycle} = 1;
 115             push @CYCLES, $cycle;
 116         }
 117     }
 118 }
 119
 120 # Walk through our graph depth-first (keeping a trail in @path), and report
 121 # any cycles we find.
 122 sub find_cycles ($@) {
 123     my ($module, @path) = @_;
 124     if (str_in_list($module, @path)) {
 125         found_cycle($module, @path);
 126     } else {
 127         return if defined $SEEN{$module};
 128         $SEEN{$module} = 1;
 129         foreach my $dep (@{$DEPS{$module}}) {
 130             find_cycles($dep, @path, $module);
 131         }
 132     }
 133 }
 134
 135 # Give a cycle, attempt to merge it with pre-existing cycle data.
 136 sub found_cycle ($@) {
 137     my ($module, @path) = @_;
 138
 139     # Pop any modules which aren't part of our cycle.
 140     while ($path[0] ne $module) { shift @path; }
 141     #print join("->", @path, $module) . "\n";
 142
 143     # Collect the modules in our cycle into a hash.
 144     my %cycle;
 145     foreach my $item (@path) {
 146         $cycle{$item} = 1;
 147         if (defined $CYCLES{$item}) {
 148             # Looks like we intersect with an existing cycle, so merge
 149             # all those in, too.
 150             foreach my $old_item (keys %{$CYCLES{$item}}) {
 151                 $cycle{$old_item} = 1;
 152             }
 153         }
 154     }
 155
 156     # Update our global cycle table.
 157     my $cycle_ref = \%cycle;
 158     foreach my $item (keys %cycle) {
 159         $CYCLES{$item} = $cycle_ref;
 160     }
 161     #print join(":", sort keys %cycle) . "\n";
 162 }
 163
 164 sub str_in_list ($@) {
 165     my ($str, @list) = @_;
 166     foreach my $item (@list) {
 167         return 1 if ($item eq $str);
 168     }
 169     return 0;
 170 }