39356449a317830d4373c5ca977e6d8758e1c175
[Faustine.git] / interpretor / preprocessor / faust-0.9.47mr3 / compiler / parallelize / colorize.cpp
1 /**
2 * @file colorize.cpp
3 * Uses colors to analyze dependencies among sub expressions
4 */
5
6
7 #include "colorize.h"
8 #include "signals.hh"
9
10 using namespace std;
11
12 // static funvtions needed to implement splitDependance
13
14 static int allocateColor(Tree exp); ///< allocate a new unique color for exp
15 static void colorize(Tree exp, int color); ///< add color information to exp and all its subtrees
16 static void uncolorize(Tree exp); ///< remove color information
17 static void listMultiColoredExp(Tree exp, set<Tree>& lst); ///< list multicolored subexpressions of exp
18
19
20
21 /**
22 * Analyze a set of expressions to discover its dependencies that is subexpressions
23 * common to at least two of these expressions
24 * @param exps set of expressions to analyze
25 * @param post resulting set of post expressions
26 * @param pre resulting set of pre expressions
27 */
28 void splitDependance(const set<Tree>& exps, set<Tree>& post, set<Tree>& pre)
29 {
30 set<Tree>::const_iterator e;
31 for (e= exps.begin(); e != exps.end(); e++) {
32 colorize(*e, allocateColor(*e));
33 }
34
35 pre.clear();
36 for (e = exps.begin(); e != exps.end(); e++) {
37 listMultiColoredExp(*e, pre);
38 }
39
40 post.clear();
41 set_difference(exps.begin(), exps.end(), pre.begin(), pre.end(), inserter(post, post.begin()));
42
43 for (e = exps.begin(); e != exps.end(); e++) {
44 uncolorize(*e);
45 }
46 }
47
48 //------------------------------------------- IMPLEMENTATION (level 1)-----------------------------------------------------
49
50 static void addColor(Tree exp, int color); ///< a color to the colors of exp
51 static bool hasColor(Tree exp, int color); ///< true if exp is already colored with color
52 static int colorsCount(Tree exp); ///< returns the number of colors of exp
53 static void clearColors(Tree exp); ///< remove the color property of exp
54
55 /**
56 * Allocate a unique color (an integer) for an expression.
57 * by converting its address into an integer
58 */
59 int allocateColor(Tree exp)
60 {
61 // return int(exp);
62 static map<Tree,int> colorMap;
63 static int nextFreeColor = 1;
64 int& color = colorMap[exp];
65 if (!color)
66 color = nextFreeColor++;
67 return color;
68 }
69
70 /**
71 * Add a color to all the expression tree
72 */
73 void colorize(Tree exp, int color)
74 {
75 if (! hasColor(exp, color)) {
76 addColor(exp, color);
77 vector<Tree> v;
78 int n = getSubSignals(exp, v, false);
79 for (int i=0; i<n; i++) colorize(v[i], color);
80 }
81 }
82
83 /**
84 * Remove the colors of an expression tree
85 */
86 void uncolorize(Tree exp)
87 {
88 if (colorsCount(exp) > 0) {
89 clearColors(exp);
90 vector<Tree> v;
91 int n = getSubSignals(exp, v, false);
92 for (int i=0; i<n; i++) uncolorize(v[i]);
93 }
94 }
95
96 /**
97 * Make a set of the multicolored sub-expressions
98 */
99 void listMultiColoredExp(Tree exp, set<Tree>& lst)
100 {
101 assert(colorsCount(exp) > 0);
102 if (colorsCount(exp) > 1) {
103 // we have found a multicolored expression
104 lst.insert(exp);
105 } else {
106 // it is a monocolored expression
107 // we search its subexpressions
108 vector<Tree> v;
109 int n = getSubSignals(exp, v, false);
110 for (int i=0; i<n; i++) {
111 listMultiColoredExp(v[i], lst);
112 }
113 }
114 }
115
116 //------------------------------------------- IMPLEMENTATION (level 2)-----------------------------------------------------
117
118 Tree COLORPROPERTY = tree(symbol("ColorProperty"));
119
120 /**
121 * set the color-set property of sig
122 * @param sig the signal we want to type
123 * @param t the type of the signal
124 */
125 void setColorProperty(Tree sig, set<int>* colorset)
126 {
127 setProperty(sig, COLORPROPERTY, tree((void*)colorset));
128 }
129
130
131 /**
132 * retrieve the color-set property of sig
133 * @param sig the signal we want to know the color-set property
134 */
135 set<int>* getColorProperty(Tree sig)
136 {
137 Tree tt;
138 if (!getProperty(sig, COLORPROPERTY, tt)) {
139 return 0;
140 } else {
141 return (set<int>*)tree2ptr(tt);
142 }
143 }
144
145
146
147
148 /**
149 * Add a color to the colorset of exp. Create an empty
150 * coloset if needed.
151 * @param sig the signal we want to color
152 * @param color the color used
153 */
154 void addColor(Tree exp, int color)
155 {
156 set<int>* cset = getColorProperty(exp);
157 if (cset == 0) {
158 cset = new set<int>();
159 setColorProperty(exp, cset);
160 }
161 cset->insert(color);
162 }
163
164
165 /**
166 * Test if exp as color in its colorset
167 * @param sig the signal we want to test
168 * @param color the color to test
169 * @return true if color is member of the colorset of sig
170 */
171 bool hasColor(Tree exp, int color)
172 {
173 set<int>* cset = getColorProperty(exp);
174 if (cset==0) {
175 return false;
176 } else {
177 return cset->find(color) != cset->end();
178 }
179 }
180
181
182 /**
183 * Count the number of colors of exp
184 * @param exp the expression we want to count the colors
185 * @return the number of elements in the color set or 0
186 */
187 static int colorsCount(Tree exp)
188 {
189 set<int>* cset = getColorProperty(exp);
190 if (cset==0) {
191 return 0;
192 } else {
193 return cset->size();
194 }
195 }
196
197
198 /**
199 * Count the number of colors of exp
200 * @param exp the expression we want to count the colors
201 * @return the number of elements in the color set or 0
202 */
203 static void clearColors(Tree exp)
204 {
205 set<int>* cset = getColorProperty(exp);
206 if (cset != 0) {
207 cset->clear();
208 }
209 }
210
211