interpretor/faust-0.9.47mr3/compiler/parallelize/loop.cpp

   1 #include "loop.hh"
   2 extern bool gVectorSwitch;
   3 extern bool gOpenMPSwitch;
   4 extern bool gOpenMPLoop;
   5
   6 using namespace std;
   7
   8 /**
   9  * Print n tabs (for indentation purpose)
  10  * @param n number of tabs to print
  11  * @param fout output stream
  12  */
  13 static void tab (int n, ostream& fout)
  14 {
  15     fout << '\n';
  16     while (n--) fout << '\t';
  17 }
  18
  19
  20 /**
  21  * Print a list of lines
  22  * @param n number of tabs of indentation
  23  * @param lines list of lines to be printed
  24  * @param fout output stream
  25  */
  26 static void printlines (int n, list<string>& lines, ostream& fout)
  27 {
  28     list<string>::iterator s;
  29     for (s = lines.begin(); s != lines.end(); s++) {
  30         tab(n, fout); fout << *s;
  31     }
  32 }
  33
  34
  35 /**
  36  * Create a recursive loop
  37  * @param recsymbol the recursive symbol defined in this loop
  38  * @param encl the enclosing loop
  39  * @param size the number of iterations of the loop
  40  */
  41 Loop::Loop(Tree recsymbol, Loop* encl, const string& size)
  42         : fIsRecursive(true), fRecSymbolSet(singleton(recsymbol)), fEnclosingLoop(encl), fSize(size), fOrder(-1), fIndex(-1), fUseCount(0), fPrinted(0)
  43 {}
  44
  45
  46 /**
  47  * Create a non recursive loop
  48  * @param encl the enclosing loop
  49  * @param size the number of iterations of the loop
  50  */
  51 Loop::Loop(Loop* encl, const string& size)
  52         : fIsRecursive(false), fRecSymbolSet(nil), fEnclosingLoop(encl), fSize(size), fOrder(-1), fIndex(-1), fUseCount(0), fPrinted(0)
  53 {}
  54
  55
  56 /**
  57  * A loop with recursive dependencies can't be run alone.
  58  * It must be included into another loop.
  59  * returns true is this loop has recursive dependencies
  60  * and must be included in an enclosing loop
  61  */
  62
  63 bool Loop::hasRecDependencyIn(Tree S)
  64 {
  65     Loop* l = this;
  66     while ( l && isNil(setIntersection(l->fRecSymbolSet,S)) ) l=l->fEnclosingLoop;
  67     return l != 0;
  68 }
  69
  70 /**
  71  * Test if a loop is empty that is if it contains no lines of code).
  72  * @return true if the loop is empty
  73  */
  74 bool Loop::isEmpty()
  75 {
  76     return fPreCode.empty() && fExecCode.empty() && fPostCode.empty() && (fExtraLoops.begin()==fExtraLoops.end());
  77 }
  78
  79 /**
  80  * Add a line of pre code  (begin of the loop)
  81  */
  82 void Loop::addPreCode (const string& str)
  83 {
  84    // cerr << this << "->addExecCode " << str << endl;
  85     fPreCode.push_back(str);
  86 }
  87
  88 /**
  89  * Add a line of exec code
  90  */
  91 void Loop::addExecCode (const string& str)
  92 {
  93    // cerr << this << "->addExecCode " << str << endl;
  94     fExecCode.push_back(str);
  95 }
  96
  97
  98 /**
  99  * Add a line of post exec code (end of the loop)
 100  */
 101 void Loop::addPostCode (const string& str)
 102 {
 103    // cerr << this << "->addPostCode " << str << endl;
 104     fPostCode.push_front(str);
 105 }
 106
 107
 108 /**
 109  * Absorb a loop by copying its recursive dependencies, its loop dependencies
 110  * and its lines of exec and post exec code.
 111  * @param l the Loop to be absorbed
 112  */
 113 void Loop::absorb (Loop* l)
 114 {
 115     // the loops must have the same number of iterations
 116     assert(fSize == l->fSize);
 117     fRecSymbolSet = setUnion(fRecSymbolSet, l->fRecSymbolSet);
 118
 119     // update loop dependencies by adding those from the absorbed loop
 120     fBackwardLoopDependencies.insert(l->fBackwardLoopDependencies.begin(), l->fBackwardLoopDependencies.end());
 121
 122     // add the line of code of the absorbed loop
 123     fPreCode.insert(fPreCode.end(), l->fPreCode.begin(), l->fPreCode.end());
 124     fExecCode.insert(fExecCode.end(), l->fExecCode.begin(), l->fExecCode.end());
 125     fPostCode.insert(fPostCode.begin(), l->fPostCode.begin(), l->fPostCode.end());
 126 }
 127
 128
 129 /**
 130  * Print a loop (unless it is empty)
 131  * @param n number of tabs of indentation
 132  * @param fout output stream
 133  */
 134 void Loop::println(int n, ostream& fout)
 135 {
 136     for (list<Loop*>::const_iterator s = fExtraLoops.begin(); s != fExtraLoops.end(); s++) {
 137         (*s)->println(n, fout);
 138     }
 139
 140     if (fPreCode.size()+fExecCode.size()+fPostCode.size() > 0) {
 141 /*        if (gVectorSwitch) {
 142             tab(n,fout);
 143             fout << ((fIsRecursive) ? "// recursive loop" : "// vectorizable loop");
 144         }*/
 145
 146         tab(n,fout); fout << "// LOOP " << this ;
 147         if (fPreCode.size()>0) {
 148             tab(n,fout); fout << "// pre processing";
 149             printlines(n, fPreCode, fout);
 150         }
 151
 152         tab(n,fout); fout << "// exec code";
 153         tab(n,fout); fout << "for (int i=0; i<" << fSize << "; i++) {";
 154         printlines(n+1, fExecCode, fout);
 155         tab(n,fout); fout << "}";
 156
 157         if (fPostCode.size()>0) {
 158             tab(n,fout); fout << "// post processing";
 159             printlines(n, fPostCode, fout);
 160         }
 161         tab(n,fout);
 162     }
 163 }
 164
 165
 166 /**
 167  * Print a parallel loop (unless it is empty). Should be called only for loop
 168  * without pre and post processing
 169  * @param n number of tabs of indentation
 170  * @param fout output stream
 171  */
 172 void Loop::printParLoopln(int n, ostream& fout)
 173 {
 174     for (list<Loop*>::const_iterator s = fExtraLoops.begin(); s != fExtraLoops.end(); s++) {
 175         tab(n,fout); fout << "#pragma omp single";
 176         tab(n,fout); fout << "{";
 177         (*s)->println(n+1, fout);
 178         tab(n,fout); fout << "}";
 179     }
 180
 181     if (fPreCode.size()+fExecCode.size()+fPostCode.size() > 0) {
 182
 183         tab(n,fout); fout << "// LOOP " << this ;
 184         if (fPreCode.size()>0) {
 185             tab(n,fout); fout << "#pragma omp single";
 186             tab(n,fout); fout << "{";
 187             tab(n+1,fout); fout << "// pre processing";
 188             printlines(n+1, fPreCode, fout);
 189             tab(n,fout); fout << "}";
 190         }
 191
 192         tab(n,fout); fout << "// exec code";
 193         tab(n,fout); fout << "#pragma omp for";
 194         tab(n,fout); fout << "for (int i=0; i<" << fSize << "; i++) {";
 195         printlines(n+1, fExecCode, fout);
 196         tab(n,fout); fout << "}";
 197
 198         if (fPostCode.size()>0) {
 199             tab(n,fout); fout << "#pragma omp single";
 200             tab(n,fout); fout << "{";
 201             tab(n+1,fout); fout << "// post processing";
 202             printlines(n+1, fPostCode, fout);
 203             tab(n,fout); fout << "}";
 204         }
 205         tab(n,fout);
 206     }
 207 }
 208
 209 /**
 210  * Print a single loop (unless it is empty)
 211  * @param n number of tabs of indentation
 212  * @param fout output stream
 213  */
 214 void Loop::printoneln(int n, ostream& fout)
 215 {
 216     if (fPreCode.size()+fExecCode.size()+fPostCode.size() > 0) {
 217 /*        if (gVectorSwitch) {
 218             tab(n,fout);
 219             fout << ((fIsRecursive) ? "// recursive loop" : "// vectorizable loop");
 220         }*/
 221
 222         tab(n,fout); fout << "for (int i=0; i<" << fSize << "; i++) {";
 223         if (fPreCode.size()>0) {
 224             tab(n+1,fout); fout << "// pre processing";
 225             printlines(n+1, fPreCode, fout);
 226         }
 227         printlines(n+1, fExecCode, fout);
 228         if (fPostCode.size()>0) {
 229             tab(n+1,fout); fout << "// post processing";
 230             printlines(n+1, fPostCode, fout);
 231         }
 232         tab(n,fout); fout << "}";
 233     }
 234 }
 235
 236 //-------------------------------------------------------
 237 void Loop::concat(Loop* l)
 238 {
 239         assert(l->fUseCount == 1);
 240         assert(fBackwardLoopDependencies.size() == 1);
 241         assert((*fBackwardLoopDependencies.begin()) == l);
 242
 243         fExtraLoops.push_front(l);
 244         fBackwardLoopDependencies = l->fBackwardLoopDependencies;
 245 }