fix library path
[scilab.git] / scilab / modules / ast / includes / analysis / AnalysisVisitor.hxx
1 /*
2  *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3  *  Copyright (C) 2014 - Scilab Enterprises - Calixte DENIZET
4  *
5  *  This file must be used under the terms of the CeCILL.
6  *  This source file is licensed as described in the file COPYING, which
7  *  you should have received as part of this distribution.  The terms
8  *  are also available at
9  *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
10  *
11  */
12
13 #ifndef __ANALYSIS_VISITOR_HXX__
14 #define __ANALYSIS_VISITOR_HXX__
15
16 #include <algorithm>
17 #include <chrono>
18 #include <limits>
19 #include <map>
20 #include <memory>
21
22 #include "visitor.hxx"
23 #include "allexp.hxx"
24 #include "allvar.hxx"
25 #include "Checkers.hxx"
26 #include "ForList.hxx"
27 #include "Result.hxx"
28 #include "SymInfo.hxx"
29 #include "execvisitor.hxx"
30
31 namespace analysis
32 {
33
34 class AnalysisVisitor : public ast::Visitor
35 {
36
37 public:
38
39     typedef std::map<symbol::Symbol, SymInfo> MapSymInfo;
40
41 private:
42
43     MapSymInfo symsinfo;
44     Result _result;
45     unsigned int scalars_tmp[TIType::COUNT][2];
46     unsigned int arrays_tmp[TIType::COUNT][2];
47
48     std::chrono::steady_clock::time_point start;
49     std::chrono::steady_clock::time_point end;
50
51 public:
52
53     AnalysisVisitor()
54     {
55         start_chrono();
56         std::fill(&scalars_tmp[0][0], &scalars_tmp[0][0] + TIType::COUNT * 2, 0);
57         std::fill(&arrays_tmp[0][0], &arrays_tmp[0][0] + TIType::COUNT * 2, 0);
58     }
59
60     const MapSymInfo & get_infos() const
61     {
62         return symsinfo;
63     }
64
65     // Only for debug use
66     inline void print_info()
67     {
68         stop_chrono();
69         std::wcout << L"Analysis duration: " << get_duration() << L" s" << std::endl;
70
71         std::wcout << L"Temporary scalars:" << std::endl;
72         for (unsigned int i = 0; i < TIType::COUNT; ++i)
73         {
74             if (scalars_tmp[i][0] || scalars_tmp[i][1])
75             {
76                 std::wcout << TIType((TIType::Type)i) << ": " << scalars_tmp[i][0] << L" and " << scalars_tmp[i][1] << std::endl;
77             }
78         }
79
80         std::wcout << std::endl;
81
82         std::wcout << L"Temporary arrays:" << std::endl;
83         for (unsigned int i = 0; i < TIType::COUNT; ++i)
84         {
85             if (arrays_tmp[i][0] || arrays_tmp[i][1])
86             {
87                 std::wcout << TIType((TIType::Type)i) << ": " << arrays_tmp[i][0] << L" and " << arrays_tmp[i][1] << std::endl;
88             }
89         }
90
91         std::wcout << std::endl;
92
93         for (MapSymInfo::const_iterator i = symsinfo.begin(), end = symsinfo.end(); i != end; ++i)
94         {
95             std::wcout << i->first.getName() << L" -> " << i->second << std::endl;
96         }
97
98         std::wcout << std::endl;
99     }
100
101     void start_chrono()
102     {
103         start = std::chrono::steady_clock::now();
104     }
105
106     void stop_chrono()
107     {
108         end = std::chrono::steady_clock::now();
109     }
110
111     double get_duration() const
112     {
113         return (double)std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-9;
114     }
115
116 private:
117
118     inline void add_tmp(const TIType & t, const int n = 1, const bool scalar = false)
119     {
120         if (scalar)
121         {
122             scalars_tmp[t.type][0] += n;
123             if (n > 0 && scalars_tmp[t.type][0] > scalars_tmp[t.type][1])
124             {
125                 scalars_tmp[t.type][1] = scalars_tmp[t.type][0];
126             }
127         }
128         else
129         {
130             arrays_tmp[t.type][0] += n;
131             if (n > 0 && arrays_tmp[t.type][0] > arrays_tmp[t.type][1])
132             {
133                 arrays_tmp[t.type][1] = arrays_tmp[t.type][0];
134             }
135         }
136     }
137
138     inline TIType get_ti(const symbol::Symbol & sym)
139     {
140         MapSymInfo::const_iterator i = symsinfo.find(sym);
141         if (i != symsinfo.end())
142         {
143             return i->second.current_type;
144         }
145
146         types::InternalType * pIT = symbol::Context::getInstance()->get(sym);
147         TIType t;
148         if (pIT && pIT->isGenericType())
149         {
150             TIType::Type type;
151             types::GenericType * pGT = static_cast<types::GenericType *>(pIT);
152             switch (pIT->getType())
153             {
154                 case types::InternalType::ScilabInt8 :
155                     type = TIType::Type::INT8;
156                     break;
157                 case types::InternalType::ScilabUInt8 :
158                     type = TIType::Type::UINT8;
159                     break;
160                 case types::InternalType::ScilabInt16 :
161                     type = TIType::Type::INT16;
162                     break;
163                 case types::InternalType::ScilabUInt16 :
164                     type = TIType::Type::UINT16;
165                     break;
166                 case types::InternalType::ScilabInt32 :
167                     type = TIType::Type::INT32;
168                     break;
169                 case types::InternalType::ScilabUInt32 :
170                     type = TIType::Type::UINT32;
171                     break;
172                 case types::InternalType::ScilabInt64 :
173                     type = TIType::Type::INT64;
174                     break;
175                 case types::InternalType::ScilabUInt64 :
176                     type = TIType::Type::UINT64;
177                     break;
178                 case types::InternalType::ScilabString :
179                     type = TIType::Type::STRING;
180                     break;
181                 case types::InternalType::ScilabDouble :
182                 {
183                     types::Double * pDbl = static_cast<types::Double *>(pGT);
184                     if (pDbl->isEmpty())
185                     {
186                         type = TIType::Type::EMPTY;
187                     }
188                     else if (pDbl->isComplex())
189                     {
190                         type = TIType::Type::COMPLEX;
191                     }
192                     else
193                     {
194                         type = TIType::Type::DOUBLE;
195                     }
196                     break;
197                 }
198                 case types::InternalType::ScilabBool :
199                     type = TIType::Type::BOOLEAN;
200                     break;
201                 case types::InternalType::ScilabPolynom :
202                     type = TIType::Type::POLYNOMIAL;
203                     break;
204                 case types::InternalType::ScilabSparse :
205                     type = TIType::Type::SPARSE;
206                     break;
207                 default :
208                     type = TIType::Type::UNKNOWN;
209             }
210
211             t = TIType(type, pGT->getRows(), pGT->getCols());
212         }
213         else
214         {
215             t = TIType();
216         }
217
218         SymInfo si;
219         si.current_type = t;
220         symsinfo.emplace(sym, si);
221
222         return t;
223     }
224
225     inline void set_sym_use(const symbol::Symbol & sym, SymInfo::Kind k)
226     {
227         MapSymInfo::iterator i = symsinfo.find(sym);
228         if (i != symsinfo.end())
229         {
230             i->second.set(k);
231         }
232         else
233         {
234             symsinfo.emplace(sym, k);
235         }
236     }
237
238     inline void set_sym_use(const symbol::Symbol & sym, SymInfo::Kind k1, SymInfo::Kind k2)
239     {
240         MapSymInfo::iterator i = symsinfo.find(sym);
241         if (i != symsinfo.end())
242         {
243             i->second.set(k1, k2);
244         }
245         else
246         {
247             symsinfo.emplace(sym, SymInfo(k1, k2));
248         }
249     }
250
251     inline void set_sym_type(const symbol::Symbol & sym, const TIType & t)
252     {
253         MapSymInfo::iterator i = symsinfo.find(sym);
254         if (i != symsinfo.end())
255         {
256             i->second.current_type = t;
257         }
258         else
259         {
260             SymInfo si;
261             si.current_type = t;
262             symsinfo.emplace(sym, si);
263         }
264     }
265
266     inline void setResult(Result & val)
267     {
268         _result = val;
269     }
270
271     inline void setResult(Result && val)
272     {
273         _result = val;
274     }
275
276     inline Result & getResult()
277     {
278         return _result;
279     }
280
281     void visit(ast::SimpleVar & e)
282     {
283         symbol::Symbol & sym = e.getSymbol();
284         TIType typ = get_ti(sym);
285         e.getDecorator().res = Result(typ, false, false);
286         setResult(e.getDecorator().res);
287         set_sym_use(e.getSymbol(), SymInfo::READ);
288     }
289
290     void visit(ast::DollarVar & e)
291     {
292         // nothing to do
293     }
294
295     void visit(ast::ColonVar & e)
296     {
297         // nothing to do
298     }
299
300     void visit(ast::ArrayListVar & e)
301     {
302         const ast::exps_t vars = e.getVars();
303         for (ast::exps_t::const_iterator i = vars.begin(), end = vars.end(); i != end ; ++i)
304         {
305             (*i)->accept(*this);
306         }
307     }
308
309     void visit(ast::DoubleExp & e)
310     {
311         e.getDecorator().res = Result(TIType(TIType::DOUBLE, 1, 1), false, true);
312         setResult(e.getDecorator().res);
313     }
314
315     void visit(ast::BoolExp & e)
316     {
317         e.getDecorator().res = Result(TIType(TIType::BOOLEAN, 1, 1), false, true);
318         setResult(e.getDecorator().res);
319     }
320
321     void visit(ast::StringExp & e)
322     {
323         e.getDecorator().res = Result(TIType(TIType::STRING, 1, 1), false, true);
324         setResult(e.getDecorator().res);
325     }
326
327     void visit(ast::CommentExp & e)
328     {
329         // ignored
330     }
331
332     void visit(ast::NilExp & e)
333     {
334         // nothing to do
335     }
336
337     void visit(ast::CallExp & e)
338     {
339         e.getName().accept(*this);
340         const ast::exps_t args = e.getArgs();
341         for (ast::exps_t::const_iterator i = args.begin(), end = args.end(); i != end; ++i)
342         {
343             (*i)->accept(*this);
344         }
345     }
346
347     void visit(ast::CellCallExp & e)
348     {
349         visit(static_cast<ast::CallExp &>(e));
350     }
351
352     void visit(ast::OpExp & e)
353     {
354         e.getLeft().accept(*this);
355         Result LR = getResult();
356         e.getRight().accept(*this);
357         Result & RR = getResult();
358         const TIType & LType = LR.getType();
359         const TIType & RType = RR.getType();
360         TIType resT;
361         bool allocTmp = false;
362
363         // We can released the temp vars
364         if (LR.isTemp())
365         {
366             add_tmp(LType, -1);
367         }
368         if (RR.isTemp())
369         {
370             add_tmp(RType, -1);
371         }
372
373         //if left and right are constant, result is constant too
374         if (e.getLeft().getDecorator().res.isConstant() && e.getRight().getDecorator().res.isConstant())
375         {
376             if (execAndReplace(e))
377             {
378                 return;
379             }
380         }
381
382         switch (e.getOper())
383         {
384             case ast::OpExp::plus :
385             {
386                 if (replaceDAXPY(e))
387                 {
388                     return;
389                 }
390                 //continue in generic case
391             }
392             case ast::OpExp::minus :
393             case ast::OpExp::dottimes :
394             {
395                 // TODO: check if the rules for addition and subtraction are the same
396                 resT = check_add(LType, RType);
397                 break;
398             }
399             case ast::OpExp::times :
400             {
401                 // multiplication is not commutative for matrice pxq
402                 resT = check_times(LType, RType);
403                 break;
404             }
405         }
406
407         if (resT.isknown() && !resT.isscalar())
408         {
409             // result is a matrix so we need a tmp
410             add_tmp(resT.type, 1);
411             allocTmp = true;
412         }
413
414         e.getDecorator().res = Result(resT, allocTmp, false);
415         setResult(e.getDecorator().res);
416     }
417
418     void visit(ast::LogicalOpExp & e)
419     {
420         e.getLeft().accept(*this);
421         e.getRight().accept(*this);
422     }
423
424     void visit(ast::AssignExp & e)
425     {
426         if (e.getLeftExp().isSimpleVar())
427         {
428             ast::SimpleVar & var = static_cast<ast::SimpleVar &>(e.getLeftExp());
429             symbol::Symbol & sym = var.getSymbol();
430
431             e.getRightExp().accept(*this);
432             var.getDecorator().res = getResult();
433
434             set_sym_use(sym, SymInfo::REPLACE);
435             set_sym_type(sym, getResult().getType());
436         }
437         else
438         {
439             // TODO: handle this case
440         }
441     }
442
443     void visit(ast::IfExp & e)
444     {
445         e.getTest().accept(*this);
446         e.getThen().accept(*this);
447         if (e.hasElse())
448         {
449             e.getElse().accept(*this);
450         }
451     }
452
453     void visit(ast::WhileExp & e)
454     {
455         e.getTest().accept(*this);
456         e.getBody().accept(*this);
457     }
458
459     void visit(ast::ForExp & e)
460     {
461         e.getVardec().accept(*this);
462         e.getBody().accept(*this);
463
464         MapSymInfo::const_iterator it = symsinfo.find(e.getVardec().getAs<ast::VarDec>()->getSymbol());
465         if (it->second.read)
466         {
467             e.getVardec().getAs<ast::VarDec>()->getListInfo().setReadInLoop(true);
468         }
469     }
470
471     void visit(ast::BreakExp & e)
472     {
473         // nothing to do
474     }
475
476     void visit(ast::ContinueExp & e)
477     {
478         // nothing to do
479     }
480
481     void visit(ast::TryCatchExp & e)
482     {
483         e.getTry().accept(*this);
484         e.getCatch().accept(*this);
485     }
486
487     void visit(ast::SelectExp & e)
488     {
489         e.getSelect()->accept(*this);
490         ast::exps_t* cases = e.getCases();
491         for (ast::exps_t::const_iterator i = cases->begin(), end = cases->end(); i != end; ++i)
492         {
493             (*i)->accept(*this);
494         }
495         delete cases;
496
497         e.getDefaultCase()->accept(*this);
498     }
499
500     void visit(ast::CaseExp & e)
501     {
502         e.getTest()->accept(*this);
503         e.getBody()->accept(*this);
504     }
505
506     void visit(ast::ReturnExp & e)
507     {
508         e.getExp().accept(*this);
509     }
510
511     void visit(ast::FieldExp & e)
512     {
513         // a.b.c <=> (a.b).c where a.b is the head and c is the tail
514
515         //e.getHead()->accept(*this);
516         //e.getTail()->accept(*this);
517     }
518
519     void visit(ast::NotExp & e)
520     {
521         e.getExp().accept(*this);
522     }
523
524     void visit(ast::TransposeExp & e)
525     {
526         e.getExp().accept(*this);
527     }
528
529     void visit(ast::MatrixExp & e)
530     {
531         const ast::exps_t lines = e.getLines();
532         bool constant = true;
533         for (ast::exps_t::const_iterator i = lines.begin(), itEnd = lines.end(); i != itEnd; ++i)
534         {
535             (*i)->accept(*this);
536             if ((*i)->getDecorator().res.isConstant() == false)
537             {
538                 constant = false;
539             }
540         }
541
542         if (constant)
543         {
544             execAndReplace(e);
545         }
546     }
547
548     void visit(ast::MatrixLineExp & e)
549     {
550         const ast::exps_t columns = e.getColumns();
551         bool constant = true;
552         for (ast::exps_t::const_iterator i = columns.begin(), itEnd = columns.end(); i != itEnd; ++i)
553         {
554             (*i)->accept(*this);
555             if ((*i)->getDecorator().res.isConstant() == false)
556             {
557                 constant = false;
558             }
559         }
560
561         e.getDecorator().res = Result(e.getDecorator().res.getType(), e.getDecorator().res.isTemp(), constant);
562
563     }
564
565     void visit(ast::CellExp & e)
566     {
567         visit(static_cast<ast::MatrixExp &>(e));
568     }
569
570     void visit(ast::SeqExp & e)
571     {
572         const ast::exps_t exps = e.getExps();
573         for (ast::exps_t::const_iterator i = exps.begin(), itEnd = exps.end(); i != itEnd; ++i)
574         {
575             (*i)->accept(*this);
576         }
577     }
578
579     void visit(ast::ArrayListExp & e)
580     {
581         const ast::exps_t exps = e.getExps();
582         for (ast::exps_t::const_iterator i = exps.begin(), itEnd = exps.end(); i != itEnd; ++i)
583         {
584             (*i)->accept(*this);
585         }
586     }
587
588     void visit(ast::AssignListExp & e)
589     {
590         visit(static_cast<ast::ArrayListExp &>(e));
591     }
592
593     void visit(ast::VarDec & e)
594     {
595         // VarDec is only used in For loop for iterator declaration
596         symbol::Symbol & sym = e.getSymbol();
597         if (e.getInit().isListExp())
598         {
599             ast::ListExp & le = static_cast<ast::ListExp &>(e.getInit());
600             if (le.getStart().isDoubleExp() && le.getStep().isDoubleExp() && le.getEnd().isDoubleExp())
601             {
602                 ForList64 fl(static_cast<const ast::DoubleExp &>(le.getStart()).getValue(),
603                              static_cast<const ast::DoubleExp &>(le.getStep()).getValue(),
604                              static_cast<const ast::DoubleExp &>(le.getEnd()).getValue());
605                 e.setListInfo(fl);
606                 set_sym_use(sym, SymInfo::REPLACE, SymInfo::FOR_IT);
607                 set_sym_type(sym, fl.getType());
608                 // No need to visit the list (it has been visited just before)
609             }
610             else
611             {
612                 e.setListInfo(ForList64());
613                 le.accept(*this);
614             }
615         }
616     }
617
618     void visit(ast::FunctionDec & e)
619     {
620         e.getArgs().accept(*this);
621         e.getReturns().accept(*this);
622         e.getBody().accept(*this);
623     }
624
625     void visit(ast::ListExp & e)
626     {
627         double start = std::numeric_limits<double>::quiet_NaN();
628         double step = std::numeric_limits<double>::quiet_NaN();
629         double end = std::numeric_limits<double>::quiet_NaN();
630
631         if (e.getStart().isDoubleExp())
632         {
633             start = static_cast<const ast::DoubleExp &>(e.getStart()).getValue();
634         }
635
636         if (e.getStep().isDoubleExp())
637         {
638             step = static_cast<ast::DoubleExp &>(e.getStep()).getValue();
639         }
640
641         if (e.getEnd().isDoubleExp())
642         {
643             end = static_cast<ast::DoubleExp &>(e.getEnd()).getValue();
644         }
645
646         const_cast<ast::ListExp &>(e).setValues(start, step, end);
647     }
648
649     /* optimized */
650     void visit(ast::OptimizedExp & e)
651     {
652         //gné ??? Oo
653     }
654
655     void visit(ast::DAXPYExp & e)
656     {
657         //gné ??? Oo
658     }
659
660     bool replaceDAXPY(ast::OpExp& e)
661     {
662         bool ret = false;
663
664         if (e.getOper() == ast::OpExp::plus)
665         {
666             ast::Exp& le = e.getLeft();
667             ast::Exp& re = e.getRight();
668             ast::Exp* a = NULL;
669             ast::Exp* x = NULL;
670             ast::Exp* y = NULL;
671
672             // a * x(i,j) + y(i,j) or y(i,j) + a * x(i,j)
673
674             if (le.isOpExp() && le.getAs<ast::OpExp>()->getOper() == ast::OpExp::dottimes)
675             {
676                 ast::OpExp* dt = le.getAs<ast::OpExp>();
677                 y = &le;
678                 a = &dt->getLeft();
679                 x = &dt->getRight();
680             }
681             else if (re.isOpExp() && re.getAs<ast::OpExp>()->getOper() == ast::OpExp::dottimes)
682             {
683                 ast::OpExp* rt = re.getAs<ast::OpExp>();
684                 y = &re;
685                 a = &rt->getLeft();
686                 x = &rt->getRight();
687             }
688
689             if (a && x && y)
690             {
691                 //checks dimensions of x and y
692                 ast::Exp* exp = new ast::DAXPYExp(e.getLocation(), *a, *x, *y);
693                 exp->setVerbose(e.isVerbose());
694                 exp->getDecorator().res = e.getDecorator().res;
695                 e.replace(exp);
696                 ret = true;
697             }
698         }
699         return ret;
700     }
701
702     bool execAndReplace(ast::Exp& e)
703     {
704         //exec operation and substitute exp by result
705         ast::ExecVisitor exec;
706
707         try
708         {
709             e.accept(exec);
710             InternalType* result = exec.getResult();
711             ast::Exp* exp = result->getExp(e.getLocation());
712             if (exp)
713             {
714                 exp->setVerbose(e.isVerbose());
715                 e.replace(exp);
716                 exp->getDecorator().res = Result(e.getDecorator().res.getType(), e.getDecorator().res.isTemp(), true);
717                 setResult(exp->getDecorator().res);
718                 return true;
719             }
720         }
721         catch (const ast::ScilabException& /*se*/)
722         {
723             //nothing to do, stop optimization phase and continue.
724             std::cout << "optimization failed !" << std::endl;
725         }
726
727         return false;
728     }
729 };
730
731 } // namespace analysis
732
733 #endif // __ANALYSIS_VISITOR_HXX__