1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2018 GRAME, Centre National de Creation Musicale
5 ---------------------------------------------------------------------
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 ************************************************************************
20 ************************************************************************/
21
22 #include <set>
23
24 #include "graphSorting.hh"
25
26 #ifdef WIN32
27 #pragma warning(disable : 4800)
28 #endif
29
30 /**
31 * Set the order of a loop and place it to appropriate set.
32 */
setOrder(Loop * l,int order,lgraph & V)33 static void setOrder(Loop* l, int order, lgraph& V)
34 {
35 faustassert(l);
36 V.resize(order + 1);
37 if (l->fOrder >= 0) {
38 V[l->fOrder].erase(l);
39 }
40 l->fOrder = order;
41 V[order].insert(l);
42 }
43
44 /**
45 * Set the order of T1's loops and collect there sons into T2.
46 */
setLevel(int order,const lset & T1,lset & T2,lgraph & V)47 static void setLevel(int order, const lset& T1, lset& T2, lgraph& V)
48 {
49 for (lset::const_iterator p = T1.begin(); p != T1.end(); p++) {
50 setOrder(*p, order, V);
51 T2.insert((*p)->fBackwardLoopDependencies.begin(), (*p)->fBackwardLoopDependencies.end());
52 }
53 }
54
resetOrder(Loop * l,set<Loop * > & visited)55 static void resetOrder(Loop* l, set<Loop*>& visited)
56 {
57 // Not yet visited...
58 if (visited.find(l) == visited.end()) {
59 visited.insert(l);
60 l->fOrder = -1;
61 for (lset::const_iterator p = l->fBackwardLoopDependencies.begin(); p != l->fBackwardLoopDependencies.end();
62 p++) {
63 resetOrder(*p, visited);
64 }
65 }
66 }
67
68 /**
69 * Topological sort of an acyclic graph of loops. The loops
70 * are collect in an lgraph : a vector of sets of loops.
71 */
sortGraph(Loop * root,lgraph & V)72 void sortGraph(Loop* root, lgraph& V)
73 {
74 faustassert(root);
75 set<Loop*> visited;
76 resetOrder(root, visited);
77
78 lset T1, T2;
79 T1.insert(root);
80 int level = 0;
81 V.clear();
82
83 do {
84 setLevel(level, T1, T2, V);
85 T1 = T2;
86 T2.clear();
87 level++;
88 } while (T1.size() > 0);
89
90 // Erase empty levels
91 lgraph::iterator p = V.begin();
92 while (p != V.end()) {
93 if ((*p).size() == 1 && (*(*p).begin())->isEmpty()) {
94 p = V.erase(p);
95 } else {
96 p++;
97 }
98 }
99 }
100