• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
21use 5.006;
22use strict;
23use warnings;
24
25my %DEPS;
26my @CYCLES;
27sub find_all_cycles;
28
29# Read our dependency information.
30while (<>) {
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.
39find_all_cycles();
40
41# Print out the finished cycles, with their dependencies.
42my @output;
43my $cycles_found = 0;
44foreach 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}
76print sort @output;
77
78exit $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
89my %SEEN;
90my %CYCLES;
91sub find_cycles ($@);
92sub found_cycles ($@);
93
94sub 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.
122sub 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.
136sub 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
164sub 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