interpreter/preprocessor/faust-0.9.47mr3/compiler/normalize/aterm.cpp

   1 #include "aterm.hh"
   2 #include "ppsig.hh"
   3 //static void collectMulTerms (Tree& coef, map<Tree,int>& M, Tree t, bool invflag=false);
   4
   5 #undef TRACE
   6
   7 using namespace std;
   8
   9 typedef map<Tree,mterm> SM;
  10
  11 aterm::aterm ()
  12 {}
  13
  14
  15 /**
  16  * create a aterm from a tree expression
  17  */
  18 aterm::aterm (Tree t)
  19 {
  20         #ifdef TRACE
  21         cerr << "aterm::aterm (" << ppsig(t)<< ")" << endl;
  22         #endif
  23         *this += t;
  24         #ifdef TRACE
  25     cerr << "aterm::aterm (" << ppsig(t)<< ") : -> " << *this << endl;
  26         #endif
  27 }
  28
  29
  30 /**
  31  * Add two terms trying to simplify the result
  32  */
  33 static Tree simplifyingAdd(Tree t1, Tree t2)
  34 {
  35         assert(t1!=0);
  36         assert(t2!=0);
  37
  38         if (isNum(t1) && isNum(t2)) {
  39                 return addNums(t1,t2);
  40
  41         } else if (isZero(t1)) {
  42                 return t2;
  43
  44         } else if (isZero(t2)) {
  45                 return t1;
  46
  47         } else if (t1 <= t2) {
  48                 return sigAdd(t1, t2);
  49
  50         } else {
  51                 return sigAdd(t2, t1);
  52         }
  53 }
  54
  55 /**
  56  * return the corresponding normalized expression tree
  57  */
  58
  59 Tree aterm::normalizedTree() const
  60 {
  61         // store positive and negative tems by order and sign
  62         // positive terms are stored in P[]
  63         // negative terms are inverted (made positive) and stored in N[]
  64         Tree P[4], N[4];
  65
  66         // prepare
  67         for (int order = 0; order < 4; order++)         P[order] = N[order] = tree(0);
  68
  69         // sum by order and sign
  70         for (SM::const_iterator p = fSig2MTerms.begin(); p != fSig2MTerms.end(); p++) {
  71                 const mterm& m = p->second;
  72                 if (m.isNegative()) {
  73                         Tree t = m.normalizedTree(false, true);
  74                         int order = getSigOrder(t);
  75                         N[order] = simplifyingAdd(N[order],t);
  76                 } else {
  77                         Tree t = m.normalizedTree();
  78                         int order = getSigOrder(t);
  79                         P[order] = simplifyingAdd(P[order],t);
  80                 }
  81         }
  82
  83         // combine sums
  84         Tree SUM = tree(0);
  85         for (int order = 0; order < 4; order++) {
  86                 if (!isZero(P[order]))  {
  87                         SUM = simplifyingAdd(SUM,P[order]);
  88                 }
  89                 if (!isZero(N[order]))  {       // we have to substract
  90                         if (isZero(SUM) && (order < 3)) {
  91                                 // we postpone substraction
  92                                 N[order+1] = simplifyingAdd(N[order], N[order+1]);
  93                         } else {
  94                                 SUM = sigSub(SUM, N[order]);
  95                         }
  96                 }
  97         }
  98
  99         assert(SUM);
 100         return SUM;
 101 }
 102
 103
 104 /**
 105  * print an aterm in a human readable format
 106  */
 107 ostream& aterm::print(ostream& dst) const
 108 {
 109     if (fSig2MTerms.empty()) {
 110         dst << "AZERO";
 111     } else {
 112         const char* sep = "";
 113         for (SM::const_iterator p = fSig2MTerms.begin(); p != fSig2MTerms.end(); p++) {
 114                 dst << sep << p->second;
 115                 sep = " + ";
 116         }
 117     }
 118
 119         return dst;
 120 }
 121
 122
 123 /**
 124  * Add in place an additive expression tree Go down t recursively looking
 125  * for additions and substractions
 126  */
 127 const aterm& aterm::operator += (Tree t)
 128 {
 129         int             op;
 130         Tree    x,y;
 131
 132         assert(t!=0);
 133
 134         if (isSigBinOp(t, &op, x, y) && (op == kAdd)) {
 135                 *this += x;
 136                 *this += y;
 137
 138         } else if (isSigBinOp(t, &op, x, y) && (op == kSub)) {
 139                 *this += x;
 140                 *this -= y;
 141
 142         } else {
 143                 mterm m(t);
 144                 *this += m;
 145         }
 146     return *this;
 147 }
 148
 149
 150 /**
 151  * Substract in place an additive expression tree Go down t recursively looking
 152  * for additions and substractions
 153  */
 154 const aterm& aterm::operator -= (Tree t)
 155 {
 156         int             op;
 157         Tree    x,y;
 158
 159         assert(t!=0);
 160
 161         if (isSigBinOp(t, &op, x, y) && (op == kAdd)) {
 162                 *this -= x;
 163                 *this -= y;
 164
 165         } else if (isSigBinOp(t, &op, x, y) && (op == kSub)) {
 166                 *this -= x;
 167                 *this += y;
 168
 169         } else {
 170                 mterm m(t);
 171                 *this -= m;
 172         }
 173     return *this;
 174 }
 175
 176
 177 /**
 178  * Add in place an mterm
 179  */
 180 const aterm& aterm::operator += (const mterm& m)
 181 {
 182         #ifdef TRACE
 183     cerr << *this << " aterm::+= " << m << endl;
 184         #endif
 185         Tree sig = m.signatureTree();
 186         #ifdef TRACE
 187     cerr << "signature " << *sig << endl;
 188         #endif
 189         SM::const_iterator p = fSig2MTerms.find(sig);
 190         if (p == fSig2MTerms.end()) {
 191                 // its a new mterm
 192                 fSig2MTerms.insert(make_pair(sig,m));
 193         } else {
 194                 fSig2MTerms[sig] += m;
 195         }
 196         return *this;
 197 }
 198
 199
 200 /**
 201  * Substract in place an mterm
 202  */
 203 const aterm& aterm::operator -= (const mterm& m)
 204 {
 205     //cerr << *this << " aterm::-= " << m << endl;
 206         Tree sig = m.signatureTree();
 207     //cerr << "signature " << *sig << endl;
 208         SM::const_iterator p = fSig2MTerms.find(sig);
 209         if (p == fSig2MTerms.end()) {
 210                 // its a new mterm
 211                 fSig2MTerms.insert(make_pair(sig,m*mterm(-1)));
 212         } else {
 213                 fSig2MTerms[sig] -= m;
 214         }
 215         return *this;
 216 }
 217
 218 mterm aterm::greatestDivisor() const
 219 {
 220         int maxComplexity = 0;
 221         mterm maxGCD(1);
 222
 223         for (SM::const_iterator p1 = fSig2MTerms.begin(); p1 != fSig2MTerms.end(); p1++) {
 224                 for (SM::const_iterator p2 = p1; p2 != fSig2MTerms.end(); p2++) {
 225                         if (p2 != p1) {
 226                                 mterm g = gcd(p1->second,p2->second);
 227                                 if (g.complexity()>maxComplexity) {
 228                                         maxComplexity = g.complexity();
 229                                         maxGCD = g;
 230                                 }
 231                         }
 232                 }
 233         }
 234         //cerr << "greatestDivisor of " << *this << " is " << maxGCD << endl;
 235         return maxGCD;
 236 }
 237
 238 /**
 239  * reorganize the aterm by factorizing d
 240  */
 241 aterm aterm::factorize(const mterm& d)
 242 {
 243         //cerr << "factorize : " << *this << " with " << d << endl;
 244         aterm A;
 245         aterm Q;
 246
 247         // separate the multiple of m from the others
 248         for (SM::const_iterator p1 = fSig2MTerms.begin(); p1 != fSig2MTerms.end(); p1++) {
 249                 mterm t = p1->second;
 250                 if (t.hasDivisor(d)) {
 251                         mterm q = t/d;
 252                         //cerr << "q = " << q << endl;
 253                         Q += q;
 254                         //cerr << "step Q = " << Q << endl;
 255                 } else {
 256                         A += t;
 257                         //cerr << "step A = " << A << endl;
 258                 }
 259         }
 260
 261         // combines the two parts
 262         //cerr << "d.normalizedTree() " << ppsig(d.normalizedTree()) << endl;
 263         //cerr << "Q.normalizedTree() " << ppsig(Q.normalizedTree()) << endl;
 264         //Tree tt = sigMul(d.normalizedTree(), Q.normalizedTree());
 265         //cerr << "tt " << *tt << endl;
 266
 267         //Tree ttt = sigAdd(
 268         A += sigMul(d.normalizedTree(), Q.normalizedTree());
 269         //cerr << "Final A = " << A << endl;
 270         //cerr << "Final Tree " << *(A.normalizedTree()) << endl;
 271         return A;
 272 }
 273
 274
 275