source: branches/with_autoconf/src/process_dependency.cc

Last change on this file was 8, checked in by nipo, 16 years ago

Checkin autotools magic

File size: 10.2 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#include "assert.h"
40#include "process_dependency.h"
41#include "methodprocess_dependency.h"
42#include "simplify_string.h"
43#include "sc_fwd.h"
44#include "sc_module.h"
45#include "sc_ver.h"
46#ifdef HAVE_CONFIG_H
47#include "config.h"
48#endif
49
50using namespace std;
51
52namespace sc_core {
53
54bool 
55ProcessDependency::operator < (const ProcessDependency &a) const
56{
57        if (a.source < source)
58                return false;
59        if (a.destination < destination)
60                return false;
61        return true;
62}
63
64static
65void
66dot_write (ofstream &o,
67           const ProcessDependencyGraph &g)
68{
69        string s;
70        ProcessDependencyGraph::const_iterator it;
71        for (it = g.begin (); it != g.end (); ++it)
72        {
73                string name;
74                name = it->source->module->name();
75                name += "_";
76                name += it->source->name;
77                o << simplify_name(name.c_str(),s);
78                o       << " -> ";
79                name = it->destination->module->name();
80                name += "_";
81                name += it->destination->name;
82                o << simplify_name(name.c_str(),s);
83          o << "\n";
84        }
85}
86
87static
88void
89dot_write (ofstream &o, 
90           const ProcessDependencyList &l)
91{
92        const method_process_t *old = NULL;
93        string s;
94        ProcessDependencyList::const_iterator it;
95        for (it = l.begin (); it != l.end (); ++it)
96        {
97                const method_process_t *current = *it;
98                if (old)
99                {
100                        string name;
101                        name = old->module->name();
102                        name += "_";
103                        name += old->name;
104                        o << simplify_name(name.c_str(),s);
105                        o       << " -> ";
106                        name = current->module->name();
107                        name += "_";
108                        name += current->name;
109                        o << simplify_name(name.c_str(),s);
110                  o << "\n";
111                }
112                old = current;
113        }
114}
115
116bool
117ProcessDependencyGraph2dot (const char *name,
118                            const ProcessDependencyGraph& g)
119{
120        if (!name)
121                return false;
122        string filename;
123        filename =  name;
124        filename += ".dot";
125        ofstream o;
126  o.open (filename.c_str(),ios::out | ios::trunc);
127        if (o.is_open () == false)
128                return false;
129        o << "// Ordered process list\n"
130             "// Generated by "
131          << sc_version () << "\n";
132        o << "strict digraph " << name << " {\n";
133        dot_write (o,g);
134        o << "}\n";
135        o.close ();
136  if (dump_stage)
137    cerr << "Port Dependency Graph written into '" 
138         << filename << "'.\n";
139        return true;
140}
141
142bool
143ProcessDependencyList2dot (const char *name,
144                          const ProcessDependencyList& l)
145{
146        if (!name)
147                return false;
148        string filename;
149        filename =  name;
150        filename += ".dot";
151        ofstream o;
152  o.open (filename.c_str(),ios::out | ios::trunc);
153        if (o.is_open () == false)
154                return false;
155        o << "// Ordered process list\n"
156       "// Generated by "
157    << sc_version () << "\n";
158        o << "digraph " << name << " {\n";
159        dot_write (o,l);
160        o << "}\n";
161        o.close ();
162        return true;
163}
164
165#if 0
166ProcessDependencyGraph*
167sc_core::MakeProcessDependencyGraph (const SignalDependencyGraph& g)
168{
169  if (dump_stage)
170          cerr << "Making module dependency graph...\n";
171
172        ProcessDependencyGraph *mod_g = new ProcessDependencyGraph ();
173        SignalDependencyGraph::const_iterator it;
174        for (it = g.begin(); it != g.end(); ++it)
175        {
176                ProcessDependency s;
177                s.destination = it->method;
178          SignalDependencyGraph::const_iterator it2;
179                for (it2 = g.begin(); it2 != g.end(); ++it2)
180          {
181                        if (it2->source == it->destination)
182                        {
183                        s.source = it2->method;
184            mod_g->insert(s);
185                        }
186                }
187        }
188        return mod_g;
189}
190
191static
192const method_process_t*
193get_method (const equi_t &e, const SignalDependencyGraph &sig)
194{
195        SignalDependencyGraph::const_iterator it;
196        for (it = sig.begin (); it != sig.end (); ++it)
197        {
198                if (it->destination == &e)
199                        return it->method;
200        }
201        return NULL;
202}
203#endif
204
205
206static
207bool
208is_leef (const SignalDependencyGraph &g,
209         const equi_t                *e)
210{
211        SignalDependencyGraph::const_iterator it;
212        for (it = g.begin (); it != g.end (); ++it)
213  {
214    if (it->source == e)
215      return false;
216  }
217  return true;
218}
219
220static
221bool
222has_all_leef (const SignalDependencyGraph &sig,
223              const method_process_t      *m)
224{
225        SignalDependencyGraph::const_iterator sig_it;
226        for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
227    if ((sig_it->method == m) 
228       && (!is_leef (sig, sig_it->destination)))
229      return false;
230  return true;
231}
232
233static
234const method_process_t*
235get_best_process (const SignalDependencyGraph &sig)
236{
237        SignalDependencyGraph::const_iterator sig_it;
238        for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
239  {
240    if (has_all_leef (sig, sig_it->method)) 
241      return sig_it->method;
242  }
243  return NULL;
244}
245
246/*
247 *   Remove signals
248 */
249static
250void
251remove_leefs (SignalDependencyGraph  &g,
252             const method_process_t &m)
253{
254        SignalDependencyGraph::iterator it;
255        it = g.begin (); 
256  while (it != g.end ())
257  {
258    const method_process_t *cur_m = it->method;
259    if ((cur_m == &m) && (is_leef (g,it->destination)))
260    {
261      SignalDependencyGraph::iterator x = it++;
262      g.erase (x);
263    }
264    else
265      ++it;
266  }     
267}
268
269#if defined(UNUSED)
270static
271void
272print_signals (ostream                      &o,
273               const SignalDependencyGraph  &sig,
274               const method_process_t       *method,
275               bool                          source)
276{
277  int count = 0;
278        SignalDependencyGraph::const_iterator it;
279        for (it = sig.begin (); it != sig.end (); ++it)
280  {
281    const SignalDependency &dep   = *it;
282    const method_process_t *cur_m = dep.method;
283    if (cur_m == method)
284    {
285      const equi_t *e = (source)?dep.source:dep.destination;
286      o << ((count++)?",":"") << get_name (*e);
287    }
288  }     
289}
290#endif
291
292static
293void
294print_leef_list (SignalDependencyGraph &sig)
295{
296  typedef map<const equi_t *, const method_process_t *> table_t;
297  table_t table;
298 
299  // For each arrow, add destination node into table
300        SignalDependencyGraph::const_iterator sig_it;
301        for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
302  {
303    const SignalDependency  sd     = *sig_it;
304    const equi_t           *equi   = sd.destination;
305          const method_process_t *method = sd.method;
306    table[equi] = method;
307  }
308 
309  // For each arrow, remove source node into table
310        for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
311  {
312    const SignalDependency  sd = *sig_it;
313    const equi_t           *= sd.source;
314    table_t::const_iterator tab_it = table.find (e);
315    if (tab_it != table.end ())
316      table.erase (e);
317  }
318
319  typedef multimap<const method_process_t *, const equi_t *> table2_t;
320  typedef pair<const method_process_t *, const equi_t *> table2_pair_t;
321  table2_t table2;
322
323  // Build table2
324  table_t::const_iterator it;
325  for (it = table.begin(); it != table.end(); ++it)
326  {
327    const method_process_t *method = it->second;
328    const equi_t           *equi   = it->first;
329    table2_pair_t           pair   = table2_pair_t(method,equi);
330    table2.insert(pair);
331  }
332
333  // Print leef list
334  cerr << "Please split following methods :";
335  table2_t::const_iterator low_it = table2.begin();
336  table2_t::const_iterator up_it;
337  while (low_it != table2.end ())
338  {
339    const method_process_t *method      = low_it->first;
340    const char             *method_name = method->name;
341    const sc_module        *module      = method->module;
342    const char             *module_name = module->name();
343    cerr << "\n\t - " << module_name << "::" << method_name;
344    cerr << "() to evaluate '";
345    int   count = 0;
346    up_it = table2.upper_bound(low_it->first);
347    table2_t::const_iterator it2;
348    for (it2 = low_it; it2 != up_it; ++it2)
349    {
350      const equi_t *equi         = it2->second;
351      const char   *signal_name  = get_name (*equi);
352      cerr << ((count++)?",":"") << signal_name;
353    }
354    cerr << "' signal(s) separetly";
355    low_it = up_it;
356  }
357  cerr << "\n";
358}
359
360static
361void
362help2resolve (SignalDependencyGraph &sig)
363{
364  print_leef_list (sig);
365  MethodProcessDependencyGraph2dot ("methodprocess_graph", sig);
366  cerr << "Please look at 'methodprocess_graph.dot' "
367          "to know how to get ride of circular dependencies.\n";
368  if (dump_all_graph)
369  {
370    SignalDependencyGraph2dot ("reduced_signal_graph", sig);
371  }
372}
373
374ProcessDependencyList* 
375MakeProcessDependencyList  (const SignalDependencyGraph  & _sig_g)
376{
377  if (dump_stage)
378    cerr << "Making process dependency list...\n";
379        ProcessDependencyList *mod_l = new ProcessDependencyList ();
380        SignalDependencyGraph sig_g = _sig_g;
381        while (!sig_g.empty ())
382        {
383                const method_process_t *process = get_best_process (sig_g);
384#if 1
385    if (process == NULL)
386    {
387      cerr << "Internal Error : Unable to select the best process to schedule.\n";
388      help2resolve (sig_g);
389      exit (31032005); // 197
390    }
391#endif
392          mod_l->push_front(process);
393#if 0
394                cerr << "Process found : " << *process << "\n";
395#endif
396                remove_leefs (sig_g, *process);
397        }
398        return mod_l;
399}
400
401} // end of sc_core namespace
402
Note: See TracBrowser for help on using the repository browser.