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