39356449a317830d4373c5ca977e6d8758e1c175
3 * Uses colors to analyze dependencies among sub expressions
12 // static funvtions needed to implement splitDependance
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
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
28 void splitDependance(const set
<Tree
>& exps
, set
<Tree
>& post
, set
<Tree
>& pre
)
30 set
<Tree
>::const_iterator e
;
31 for (e
= exps
.begin(); e
!= exps
.end(); e
++) {
32 colorize(*e
, allocateColor(*e
));
36 for (e
= exps
.begin(); e
!= exps
.end(); e
++) {
37 listMultiColoredExp(*e
, pre
);
41 set_difference(exps
.begin(), exps
.end(), pre
.begin(), pre
.end(), inserter(post
, post
.begin()));
43 for (e
= exps
.begin(); e
!= exps
.end(); e
++) {
48 //------------------------------------------- IMPLEMENTATION (level 1)-----------------------------------------------------
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
56 * Allocate a unique color (an integer) for an expression.
57 * by converting its address into an integer
59 int allocateColor(Tree exp
)
62 static map
<Tree
,int> colorMap
;
63 static int nextFreeColor
= 1;
64 int& color
= colorMap
[exp
];
66 color
= nextFreeColor
++;
71 * Add a color to all the expression tree
73 void colorize(Tree exp
, int color
)
75 if (! hasColor(exp
, color
)) {
78 int n
= getSubSignals(exp
, v
, false);
79 for (int i
=0; i
<n
; i
++) colorize(v
[i
], color
);
84 * Remove the colors of an expression tree
86 void uncolorize(Tree exp
)
88 if (colorsCount(exp
) > 0) {
91 int n
= getSubSignals(exp
, v
, false);
92 for (int i
=0; i
<n
; i
++) uncolorize(v
[i
]);
97 * Make a set of the multicolored sub-expressions
99 void listMultiColoredExp(Tree exp
, set
<Tree
>& lst
)
101 assert(colorsCount(exp
) > 0);
102 if (colorsCount(exp
) > 1) {
103 // we have found a multicolored expression
106 // it is a monocolored expression
107 // we search its subexpressions
109 int n
= getSubSignals(exp
, v
, false);
110 for (int i
=0; i
<n
; i
++) {
111 listMultiColoredExp(v
[i
], lst
);
116 //------------------------------------------- IMPLEMENTATION (level 2)-----------------------------------------------------
118 Tree COLORPROPERTY
= tree(symbol("ColorProperty"));
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
125 void setColorProperty(Tree sig
, set
<int>* colorset
)
127 setProperty(sig
, COLORPROPERTY
, tree((void*)colorset
));
132 * retrieve the color-set property of sig
133 * @param sig the signal we want to know the color-set property
135 set
<int>* getColorProperty(Tree sig
)
138 if (!getProperty(sig
, COLORPROPERTY
, tt
)) {
141 return (set
<int>*)tree2ptr(tt
);
149 * Add a color to the colorset of exp. Create an empty
151 * @param sig the signal we want to color
152 * @param color the color used
154 void addColor(Tree exp
, int color
)
156 set
<int>* cset
= getColorProperty(exp
);
158 cset
= new set
<int>();
159 setColorProperty(exp
, cset
);
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
171 bool hasColor(Tree exp
, int color
)
173 set
<int>* cset
= getColorProperty(exp
);
177 return cset
->find(color
) != cset
->end();
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
187 static int colorsCount(Tree exp
)
189 set
<int>* cset
= getColorProperty(exp
);
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
203 static void clearColors(Tree exp
)
205 set
<int>* cset
= getColorProperty(exp
);