1 /************************************************************************
2  ************************************************************************
3     FAUST compiler
4     Copyright (C) 2003-2018 GRAME, Centre National de Creation Musicale
5     ---------------------------------------------------------------------
6     This program is free software; you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation; either version 2 of the License, or
9     (at your option) any later version.
10 
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15 
16     You should have received a copy of the GNU General Public License
17     along with this program; if not, write to the Free Software
18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19  ************************************************************************
20  ************************************************************************/
21 
22 #ifndef _FUNCTION_BUILDER_H
23 #define _FUNCTION_BUILDER_H
24 
25 using namespace std;
26 
27 #include <string.h>
28 #include <algorithm>
29 #include <iostream>
30 #include <list>
31 #include <map>
32 #include <sstream>
33 #include <stack>
34 #include <string>
35 #include <vector>
36 
37 #include "exception.hh"
38 #include "global.hh"
39 #include "instructions.hh"
40 
41 /*
42     void compute(int count, float** inputs, float** ouputs)
43     {
44         int toto = ....  (local var outside the loop)
45 
46         loop (....count....)
47         {
48             toto: use of var outside the loop
49 
50             field: kStruct variable
51 
52             float titi = ....  (local var inside the loop)
53             loop_code
54         }
55     }
56 
57     ==> local var outside the loop : function parameter
58     ==> var insided the loop : stay the same
59     ==> "count" of the loop : function parameter
60     ==> field: kStruct variable : stay the same
61     ==> global variables : stay the same
62 
63     void extracted_loop(int toto, int count, .....)
64     {
65         loop (....count....)
66         {
67             toto: use of var from paramater list
68 
69             field: kStruct variable
70 
71             float titi = ....  (local var inside the loop)
72             loop_code
73         }
74     }
75 
76     void extracted_loop(int count, float** inputs, float** ouputs)
77     {
78         call_loop(toto, count, ....)
79     }
80 
81 */
82 
83 struct Loop2FunctionBuider : public DispatchVisitor {
84     // Variable management
85     map<string, Address::AccessType> fLocalVarTable;
86     list<string>                     fAddedVarTable;
87 
88     // Function definition creation
89     list<NamedTyped*> fArgsTypeList;
90     DeclareFunInst*   fFunctionDef;
91 
92     // Function call creation
93     list<ValueInst*> fArgsValueList;
94     DropInst*        fFunctionCall;
95 
createParameterLoop2FunctionBuider96     void createParameter(Address* address)
97     {
98         switch (address->getAccess()) {
99             case Address::kStack:
100             case Address::kLoop: {
101                 string name = address->getName();
102                 if (fLocalVarTable.find(name) == fLocalVarTable.end()) {
103                     if (find(fAddedVarTable.begin(), fAddedVarTable.end(), name) ==
104                         fAddedVarTable.end()) {  // First encounter
105 
106                         // Be sure variable is defined
107                         // cerr << "createParameter kStack " << name << endl;
108                         faustassert(gGlobal->gVarTypeTable.find(name) != gGlobal->gVarTypeTable.end());
109 
110                         // Local in the enclosing context, becomes a fun parameter
111                         BasicCloneVisitor cloner;
112                         fArgsTypeList.push_back(
113                             InstBuilder::genNamedTyped(name, gGlobal->gVarTypeTable[name]->clone(&cloner)));
114 
115                         // It becomes a value in the fun-call argument list
116                         fArgsValueList.push_back(InstBuilder::genLoadStackVar(name));
117 
118                         // Variable added in parameter list
119                         fAddedVarTable.push_back(name);
120                     }
121 
122                 } else {
123                     // Loop own local, nothing to do
124                 }
125                 break;
126             }
127 
128             case Address::kFunArgs: {
129                 string name = address->getName();
130                 if (find(fAddedVarTable.begin(), fAddedVarTable.end(), name) ==
131                     fAddedVarTable.end()) {  // First encounter
132 
133                     // Be sure variable is defined
134                     // cerr << "createParameter kFunArgs " << name << endl;
135                     faustassert(gGlobal->gVarTypeTable.find(name) != gGlobal->gVarTypeTable.end());
136 
137                     // Parameter in the enclosing function, becomes a fun parameter
138                     BasicCloneVisitor cloner;
139                     fArgsTypeList.push_back(
140                         InstBuilder::genNamedTyped(name, gGlobal->gVarTypeTable[name]->clone(&cloner)));
141 
142                     // It becomes a value in the fun-call argument list : keep it's kFunArgs status
143                     fArgsValueList.push_back(InstBuilder::genLoadFunArgsVar(name));
144 
145                     // Variable added in parameter list
146                     fAddedVarTable.push_back(name);
147                 }
148                 break;
149             }
150 
151             case Address::kStruct:
152             case Address::kStaticStruct:
153             case Address::kGlobal:
154                 // Nothing to do
155                 break;
156 
157             case Address::kLink:
158                 faustassert(false);
159                 break;
160 
161             default:
162                 break;
163         }
164     }
165 
visitLoop2FunctionBuider166     virtual void visit(DeclareVarInst* inst)
167     {
168         DispatchVisitor::visit(inst);
169         Address::AccessType access = inst->fAddress->getAccess();
170 
171         if (access == Address::kStack || access == Address::kLoop) {
172             // Keep local variables in the loop
173             fLocalVarTable[inst->fAddress->getName()] = access;
174         }
175     }
176 
visitLoop2FunctionBuider177     virtual void visit(LoadVarInst* inst)
178     {
179         DispatchVisitor::visit(inst);
180         createParameter(inst->fAddress);
181     }
182 
visitLoop2FunctionBuider183     virtual void visit(LoadVarAddressInst* inst) {}
184 
visitLoop2FunctionBuider185     virtual void visit(StoreVarInst* inst)
186     {
187         DispatchVisitor::visit(inst);
188         createParameter(inst->fAddress);
189     }
190 
Loop2FunctionBuiderLoop2FunctionBuider191     Loop2FunctionBuider(const string& fun_name, BlockInst* block, bool add_object = false)
192     {
193         // This prepare fArgsTypeList and fArgsValueList
194         block->accept(this);
195 
196         // Change the status of all variables used in function parameter list
197         struct LoopCloneVisitor : public BasicCloneVisitor {
198             list<string>& fAddedVarTable;
199 
200             LoopCloneVisitor(list<string>& table) : fAddedVarTable(table) {}
201 
202             virtual Address* visit(NamedAddress* address)
203             {
204                 if (find(fAddedVarTable.begin(), fAddedVarTable.end(), address->fName) != fAddedVarTable.end()) {
205                     return InstBuilder::genNamedAddress(address->fName, Address::kFunArgs);
206                 } else {
207                     return BasicCloneVisitor::visit(address);
208                 }
209             }
210         };
211 
212         // Put loop in new function
213         LoopCloneVisitor cloner(fAddedVarTable);
214         BlockInst*       function_code = static_cast<BlockInst*>(block->clone(&cloner));
215 
216         // Add a Ret (void) instruction (needed in LLVM backend)
217         function_code->pushBackInst(InstBuilder::genRetInst());
218 
219         // Add "dsp" arg in function prototype and in parameter list
220         if (add_object) {
221             fArgsTypeList.push_front(InstBuilder::genNamedTyped("dsp", InstBuilder::genBasicTyped(Typed::kObj_ptr)));
222             fArgsValueList.push_front(InstBuilder::genLoadFunArgsVar("dsp"));
223         }
224 
225         // Create function
226         fFunctionDef = InstBuilder::genVoidFunction(fun_name, fArgsTypeList, function_code);
227 
228         // Create function call
229         fFunctionCall = InstBuilder::genDropInst(InstBuilder::genFunCallInst(fun_name, fArgsValueList));
230     }
231 };
232 
233 /*
234 Constant propagation :
235 
236 1) changer des variables en constantes dans le code initial
237 2) cloner le code avec ConstantPropagationCloneVisitor
238 */
239 
240 struct ConstantPropagationBuilder : public BasicCloneVisitor {
241     map<string, ValueInst*> fValueTable;
242 
visitConstantPropagationBuilder243     virtual ValueInst* visit(BinopInst* inst)
244     {
245         ValueInst* val1 = inst->fInst1->clone(this);
246         ValueInst* val2 = inst->fInst2->clone(this);
247 
248         FloatNumInst* float1 = dynamic_cast<FloatNumInst*>(val1);
249         FloatNumInst* float2 = dynamic_cast<FloatNumInst*>(val2);
250 
251         // TODO
252         Int32NumInst* int1 = dynamic_cast<Int32NumInst*>(val1);
253         Int32NumInst* int2 = dynamic_cast<Int32NumInst*>(val2);
254 
255         // if (float1) float1->dump();
256         // if (float2) float2->dump();
257 
258         if (float1 && float2) {
259             switch (inst->fOpcode) {
260                 case kAdd:
261                     return InstBuilder::genFloatNumInst(float1->fNum + float2->fNum);
262                 case kSub:
263                     return InstBuilder::genFloatNumInst(float1->fNum - float2->fNum);
264                 case kMul:
265                     return InstBuilder::genFloatNumInst(float1->fNum * float2->fNum);
266                 case kDiv:
267                     return InstBuilder::genFloatNumInst(float1->fNum / float2->fNum);
268                 default:
269                     return 0;
270             }
271 
272         } else if (int1 && int2) {
273             faustassert(false);
274             return 0;
275         } else {
276             return InstBuilder::genBinopInst(inst->fOpcode, val1, val2);
277         }
278     }
279 
visitConstantPropagationBuilder280     virtual ValueInst* visit(CastInst* inst)
281     {
282         ValueInst*    val1   = inst->fInst->clone(this);
283         FloatNumInst* float1 = dynamic_cast<FloatNumInst*>(val1);
284         Int32NumInst* int1   = dynamic_cast<Int32NumInst*>(val1);
285 
286         if (inst->fType->getType() == Typed::kFloat) {
287             return (float1) ? float1 : InstBuilder::genFloatNumInst(float(int1->fNum));
288         } else if (inst->fType->getType() == Typed::kInt32) {
289             return (int1) ? int1 : InstBuilder::genInt32NumInst(int(float1->fNum));
290         } else {
291             faustassert(false);
292             return 0;
293         }
294     }
295 
visitConstantPropagationBuilder296     virtual ValueInst* visit(FunCallInst* inst)
297     {
298         list<ValueInst*>                 cloned;
299         list<ValueInst*>::const_iterator it;
300         for (it = inst->fArgs.begin(); it != inst->fArgs.end(); it++) {
301             cloned.push_back((*it)->clone(this));
302         }
303         // TODO : si toute la liste des values sont des nombres, alors effectuer le calcul
304         return InstBuilder::genFunCallInst(inst->fName, cloned, inst->fMethod);
305     }
306 
visitConstantPropagationBuilder307     virtual ValueInst* visit(Select2Inst* inst)
308     {
309         ValueInst*    val1   = inst->fCond->clone(this);
310         FloatNumInst* float1 = dynamic_cast<FloatNumInst*>(val1);
311         Int32NumInst* int1   = dynamic_cast<Int32NumInst*>(val1);
312 
313         if (float1) {
314             return (float1->fNum > 0.f) ? inst->fThen->clone(this) : inst->fElse->clone(this);
315         } else if (int1) {
316             return (int1->fNum > 0) ? inst->fThen->clone(this) : inst->fElse->clone(this);
317         } else {
318             return InstBuilder::genSelect2Inst(val1, inst->fThen->clone(this), inst->fElse->clone(this));
319         }
320     }
321 
visitConstantPropagationBuilder322     virtual StatementInst* visit(DeclareVarInst* inst)
323     {
324         ValueInst*    val1   = inst->fValue->clone(this);
325         FloatNumInst* float1 = dynamic_cast<FloatNumInst*>(val1);
326         Int32NumInst* int1   = dynamic_cast<Int32NumInst*>(val1);
327         string        name   = inst->fAddress->getName();
328 
329         if (float1) {
330             // float1->dump();
331             // Creates a "link" so that corresponding load see the real value
332             fValueTable[name] = float1;
333             return InstBuilder::genDropInst();
334         } else if (int1) {
335             // Creates a "link" so that corresponding load see the real value
336             fValueTable[name] = int1;
337             return InstBuilder::genDropInst();
338         } else {
339             BasicCloneVisitor cloner;
340             return InstBuilder::genDeclareVarInst(inst->fAddress->clone(&cloner), inst->fType->clone(&cloner), val1);
341         }
342     }
343 
visitConstantPropagationBuilder344     virtual ValueInst* visit(LoadVarInst* inst)
345     {
346         string name = inst->fAddress->getName();
347         if (fValueTable.find(name) != fValueTable.end()) {
348             return fValueTable[name];
349         } else {
350             BasicCloneVisitor cloner;
351             return InstBuilder::genLoadVarInst(inst->fAddress->clone(&cloner));
352         }
353     }
354 
visitConstantPropagationBuilder355     virtual StatementInst* visit(StoreVarInst* inst)
356     {
357         ValueInst*    val1   = inst->fValue->clone(this);
358         FloatNumInst* float1 = dynamic_cast<FloatNumInst*>(val1);
359         Int32NumInst* int1   = dynamic_cast<Int32NumInst*>(val1);
360         string        name   = inst->fAddress->getName();
361 
362         if (float1) {
363             // float1->dump();
364             // Creates a "link" so that corresponding load see the real value
365             fValueTable[name] = float1;
366             return InstBuilder::genDropInst();
367         } else if (int1) {
368             // Creates a "link" so that corresponding load see the real value
369             fValueTable[name] = int1;
370             return InstBuilder::genDropInst();
371         } else {
372             BasicCloneVisitor cloner;
373             return InstBuilder::genStoreVarInst(inst->fAddress->clone(&cloner), val1);
374         }
375     }
376 };
377 
378 #endif
379