source: sources/src/process_dependency.cc @ 56

Last change on this file since 56 was 52, checked in by meunier, 12 years ago

Code formatting in all source files.

File size: 10.1 KB
Line 
1/*------------------------------------------------------------\
2  |                                                             |
3  | Tool    :                  systemcass                       |
4  |                                                             |
5  | File    :                  process_dependancy.cc            |
6  |                                                             |
7  | Author  :                 Buchmann Richard                  |
8  |                                                             |
9  | Date    :                   21_09_2004                      |
10  |                                                             |
11  \------------------------------------------------------------*/
12
13/*
14 * This file is part of the Disydent Project
15 * Copyright (C) Laboratoire LIP6 - Département ASIM
16 * Universite Pierre et Marie Curie
17 *
18 * Home page          : http://www-asim.lip6.fr/disydent
19 * E-mail             : mailto:richard.buchmann@lip6.fr
20 *
21 * This library is free software; you  can redistribute it and/or modify it
22 * under the terms  of the GNU Library General Public  License as published
23 * by the Free Software Foundation; either version 2 of the License, or (at
24 * your option) any later version.
25 *
26 * Disydent is distributed  in the hope  that it  will be
27 * useful, but WITHOUT  ANY WARRANTY; without even the  implied warranty of
28 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
29 * Public License for more details.
30 *
31 * You should have received a copy  of the GNU General Public License along
32 * with the GNU C Library; see the  file COPYING. If not, write to the Free
33 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
34 */
35
36#include <set>
37#include <iostream>
38#include <fstream>
39
40#include "assert.h"
41#include "process_dependency.h"
42#include "methodprocess_dependency.h"
43#include "simplify_string.h"
44#include "sc_fwd.h"
45#include "sc_module.h"
46#include "sc_ver.h"
47
48#ifdef HAVE_CONFIG_H
49#include "config.h"
50#endif
51
52using namespace std;
53
54namespace sc_core {
55
56bool ProcessDependency::operator < (const ProcessDependency &a) const {
57    if (a.source < source) {
58        return false;
59    }
60    if (a.destination < destination) {
61        return false;
62    }
63    return true;
64}
65
66
67static void dot_write (ofstream & o, const ProcessDependencyGraph & g) {
68    string s;
69    ProcessDependencyGraph::const_iterator it;
70    for (it = g.begin (); it != g.end (); ++it) {
71        string name;
72        name = it->source->module->name();
73        name += "_";
74        name += it->source->name;
75        o << simplify_name(name.c_str(),s);
76        o << " -> ";
77        name = it->destination->module->name();
78        name += "_";
79        name += it->destination->name;
80        o << simplify_name(name.c_str(),s);
81        o << "\n";
82    }
83}
84
85
86static void dot_write(ofstream &o, const ProcessDependencyList &l) {
87    const method_process_t * old = NULL;
88    string s;
89    ProcessDependencyList::const_iterator it;
90    for (it = l.begin (); it != l.end (); ++it) {
91        const method_process_t * current = *it;
92        if (old) {
93            string name;
94            name = old->module->name();
95            name += "_";
96            name += old->name;
97            o << simplify_name(name.c_str(),s);
98            o << " -> ";
99            name = current->module->name();
100            name += "_";
101            name += current->name;
102            o << simplify_name(name.c_str(),s);
103            o << "\n";
104        }
105        old = current;
106    }
107}
108
109
110bool ProcessDependencyGraph2dot(const char * name, const ProcessDependencyGraph& g) {
111    if (!name) {
112        return false;
113    }
114    string filename;
115    filename =  name;
116    filename += ".dot";
117    ofstream o;
118    o.open (filename.c_str(),ios::out | ios::trunc);
119    if (o.is_open () == false) {
120        return false;
121    }
122    o << "// Ordered process list\n"
123        "// Generated by "
124        << sc_version () << "\n";
125    o << "strict digraph " << name << " {\n";
126    dot_write (o,g);
127    o << "}\n";
128    o.close ();
129    if (dump_stage) {
130        cerr << "Port Dependency Graph written into '" 
131             << filename << "'.\n";
132    }
133    return true;
134}
135
136
137bool ProcessDependencyList2dot(const char * name, const ProcessDependencyList& l) {
138    if (!name) {
139        return false;
140    }
141    string filename;
142    filename =  name;
143    filename += ".dot";
144    ofstream o;
145    o.open (filename.c_str(),ios::out | ios::trunc);
146    if (o.is_open () == false) {
147        return false;
148    }
149    o << "// Ordered process list\n"
150        "// Generated by "
151        << sc_version () << "\n";
152    o << "digraph " << name << " {\n";
153    dot_write (o,l);
154    o << "}\n";
155    o.close ();
156    return true;
157}
158
159
160static bool is_leef(const SignalDependencyGraph & g, const equi_t * e) {
161    SignalDependencyGraph::const_iterator it;
162    for (it = g.begin(); it != g.end(); ++it) {
163        if (it->source == e) {
164            return false;
165        }
166    }
167    return true;
168}
169
170
171static bool has_all_leef(const SignalDependencyGraph & sig, const method_process_t * m) {
172    SignalDependencyGraph::const_iterator sig_it;
173    for (sig_it = sig.begin(); sig_it != sig.end(); ++sig_it) {
174        if ((sig_it->method == m) && (!is_leef (sig, sig_it->destination))) {
175            return false;
176        }
177    }
178    return true;
179}
180
181
182static const method_process_t * get_best_process(const SignalDependencyGraph & sig) {
183    SignalDependencyGraph::const_iterator sig_it;
184    for (sig_it = sig.begin(); sig_it != sig.end(); ++sig_it) {
185        if (has_all_leef(sig, sig_it->method)) {
186            return sig_it->method;
187        }
188    }
189    return NULL;
190}
191
192
193/*
194 *   Remove signals
195 */
196static void remove_leefs (SignalDependencyGraph  & g, const method_process_t & m) {
197    SignalDependencyGraph::iterator it;
198    it = g.begin();
199    while (it != g.end()) {
200        const method_process_t * cur_m = it->method;
201        if ((cur_m == &m) && (is_leef (g,it->destination))) {
202            SignalDependencyGraph::iterator x = it++;
203            g.erase (x);
204        }
205        else {
206            ++it;
207        }
208    }
209}
210
211
212#if defined(UNUSED)
213static void print_signals (ostream & o,
214        const SignalDependencyGraph & sig,
215        const method_process_t * method,
216        bool source) {
217    int count = 0;
218    SignalDependencyGraph::const_iterator it;
219    for (it = sig.begin(); it != sig.end(); ++it) {
220        const SignalDependency & dep = *it;
221        const method_process_t * cur_m = dep.method;
222        if (cur_m == method) {
223            const equi_t * e = (source) ? dep.source : dep.destination;
224            o << ((count++)?",":"") << get_name (*e);
225        }
226    }
227}
228#endif
229
230
231static void print_leef_list (SignalDependencyGraph & sig) {
232    typedef map<const equi_t *, const method_process_t *> table_t;
233    table_t table;
234
235    // For each arrow, add destination node into table
236    SignalDependencyGraph::const_iterator sig_it;
237    for (sig_it = sig.begin(); sig_it != sig.end(); ++sig_it) {
238        const SignalDependency sd = *sig_it;
239        const equi_t * equi = sd.destination;
240        const method_process_t * method = sd.method;
241        table[equi] = method;
242    }
243
244    // For each arrow, remove source node into table
245    for (sig_it = sig.begin(); sig_it != sig.end(); ++sig_it) {
246        const SignalDependency sd = *sig_it;
247        const equi_t * e = sd.source;
248        table_t::const_iterator tab_it = table.find(e);
249        if (tab_it != table.end()) {
250            table.erase(e);
251        }
252    }
253
254    typedef multimap<const method_process_t *, const equi_t *> table2_t;
255    typedef pair<const method_process_t *, const equi_t *> table2_pair_t;
256    table2_t table2;
257
258    // Build table2
259    table_t::const_iterator it;
260    for (it = table.begin(); it != table.end(); ++it) {
261        const method_process_t * method = it->second;
262        const equi_t * equi = it->first;
263        table2_pair_t pair = table2_pair_t(method,equi);
264        table2.insert(pair);
265    }
266
267    // Print leef list
268    cerr << "Please split following methods :";
269    table2_t::const_iterator low_it = table2.begin();
270    table2_t::const_iterator up_it;
271    while (low_it != table2.end()) {
272        const method_process_t * method = low_it->first;
273        const char * method_name = method->name;
274        const sc_module * module = method->module;
275        const char * module_name = module->name();
276        cerr << "\n\t - " << module_name << "::" << method_name;
277        cerr << "() to evaluate '";
278        int count = 0;
279        up_it = table2.upper_bound(low_it->first);
280        table2_t::const_iterator it2;
281        for (it2 = low_it; it2 != up_it; ++it2) {
282            const equi_t * equi = it2->second;
283            const char * signal_name = get_name(*equi);
284            cerr << ((count++) ? ",":"") << signal_name;
285        }
286        cerr << "' signal(s) separetly";
287        low_it = up_it;
288    }
289    cerr << "\n";
290}
291
292
293static void help2resolve(SignalDependencyGraph & sig) {
294    print_leef_list(sig);
295    MethodProcessDependencyGraph2dot ("methodprocess_graph", sig);
296    cerr << "Please look at 'methodprocess_graph.dot' "
297        "to know how to get ride of circular dependencies.\n";
298    if (dump_all_graph) {
299        SignalDependencyGraph2dot ("reduced_signal_graph", sig);
300    }
301}
302
303
304ProcessDependencyList * MakeProcessDependencyList(const SignalDependencyGraph & _sig_g) {
305    if (dump_stage) {
306        cerr << "Making process dependency list...\n";
307    }
308    ProcessDependencyList * mod_l = new ProcessDependencyList();
309    SignalDependencyGraph sig_g = _sig_g;
310    while (!sig_g.empty()) {
311        const method_process_t * process = get_best_process(sig_g);
312        if (process == NULL)
313        {
314            cerr << "Internal Error : Unable to select the best process to schedule.\n";
315            help2resolve(sig_g);
316            exit (31032005); // 197
317        }
318        mod_l->push_front(process);
319        if (dump_stage) {
320            cerr << "Process found : " << *process << "\n";
321        }
322        remove_leefs (sig_g, * process);
323    }
324    return mod_l;
325}
326
327} // end of sc_core namespace
328
329/*
330# Local Variables:
331# tab-width: 4;
332# c-basic-offset: 4;
333# c-file-offsets:((innamespace . 0)(inline-open . 0));
334# indent-tabs-mode: nil;
335# End:
336#
337# vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
338*/
339
340
Note: See TracBrowser for help on using the repository browser.