3 # Program: find-cycles.pl
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.
9 # Syntax: find-cycles.pl < LibDeps.txt > FinalLibDeps.txt
11 # Input: cycmem1: cycmem2 dep1 dep2
12 # cycmem2: cycmem1 dep3 dep4
15 # Output: cycmem1 cycmem2: dep1 dep2 dep3 dep4
18 # This file was written by Eric Kidd, and is placed into the public domain.
29 # Read our dependency information.
32 my ($module, $dependency_str) = /^([^:]*): ?(.*)$/;
33 die "Malformed data: $_" unless defined $dependency_str;
34 my @dependencies = split(/ /, $dependency_str);
35 $DEPS{$module} = \@dependencies;
38 # Partition our raw dependencies into sets of cyclically-connected nodes.
41 # Print out the finished cycles, with their dependencies.
44 foreach my $cycle (@CYCLES) {
45 my @modules = sort keys %{$cycle};
47 # Merge the dependencies of all modules in this cycle.
49 foreach my $module (@modules) {
50 @dependencies{@{$DEPS{$module}}} = 1;
53 # Prune the known cyclic dependencies.
54 foreach my $module (@modules) {
55 delete $dependencies{$module};
58 # Warn about possible linker problems.
59 my @archives = grep(/\.a$/, @modules);
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 print STDERR "find-cycles.pl: Some linkers may have problems.\n";
65 push @modules, @archives; # WORKAROUND: Duplicate *.a files. Ick.
68 # Add to our output. (@modules is already as sorted as we need it to be.)
69 push @output, (join(' ', @modules) . ': ' .
70 join(' ', sort keys %dependencies) . "\n");
74 ### FIXME: reenable this after 1.8.
78 #==========================================================================
79 # Depedency Cycle Support
80 #==========================================================================
81 # For now, we have cycles in our dependency graph. Ideally, each cycle
82 # would be collapsed down to a single *.a file, saving us all this work.
84 # To understand this code, you'll need a working knowledge of Perl 5,
85 # and possibly some quality time with 'man perlref'.
90 sub found_cycles ($@);
93 # Find all multi-item cycles.
94 my @modules = sort keys %DEPS;
95 foreach my $module (@modules) { find_cycles($module); }
97 # Build fake one-item "cycles" for the remaining modules, so we can
98 # treat them uniformly.
99 foreach my $module (@modules) {
100 unless (defined $CYCLES{$module}) {
101 my %cycle = ($module, 1);
102 $CYCLES{$module} = \%cycle;
106 # Find all our unique cycles. We have to do this the hard way because
107 # we apparently can't store hash references as hash keys without making
110 foreach my $cycle (values %CYCLES) {
111 unless ($seen{$cycle}) {
113 push @CYCLES, $cycle;
118 # Walk through our graph depth-first (keeping a trail in @path), and report
119 # any cycles we find.
120 sub find_cycles ($@) {
121 my ($module, @path) = @_;
122 if (str_in_list($module, @path)) {
123 found_cycle($module, @path);
125 return if defined $SEEN{$module};
127 foreach my $dep (@{$DEPS{$module}}) {
128 find_cycles($dep, @path, $module);
133 # Give a cycle, attempt to merge it with pre-existing cycle data.
134 sub found_cycle ($@) {
135 my ($module, @path) = @_;
137 # Pop any modules which aren't part of our cycle.
138 while ($path[0] ne $module) { shift @path; }
139 #print join("->", @path, $module) . "\n";
141 # Collect the modules in our cycle into a hash.
143 foreach my $item (@path) {
145 if (defined $CYCLES{$item}) {
146 # Looks like we intersect with an existing cycle, so merge
148 foreach my $old_item (keys %{$CYCLES{$item}}) {
149 $cycle{$old_item} = 1;
154 # Update our global cycle table.
155 my $cycle_ref = \%cycle;
156 foreach my $item (keys %cycle) {
157 $CYCLES{$item} = $cycle_ref;
159 #print join(":", sort keys %cycle) . "\n";
162 sub str_in_list ($@) {
163 my ($str, @list) = @_;
164 foreach my $item (@list) {
165 return 1 if ($item eq $str);