Merge branch 'master' of https://scm.cri.ensmp.fr/git/Faustine
[Faustine.git] / interpretor / 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