source: sources/src/process_dependency.cc @ 26

Last change on this file since 26 was 1, checked in by buchmann, 17 years ago

Initial import from CVS repository

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