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 } 171
