f9fa2932824f7156cd4439729ac43777836d71fe
[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 <limits>
18 #include <map>
19 #include <memory>
20 #include <vector>
21
22 #include "visitor.hxx"
23 #include "execvisitor.hxx"
24 #include "allexp.hxx"
25 #include "allvar.hxx"
26 #include "calls/CallAnalyzer.hxx"
27 #include "checkers/Checkers.hxx"
28 #include "Chrono.hxx"
29 #include "ForList.hxx"
30 #include "Result.hxx"
31 #include "SymInfo.hxx"
32 #include "Temporary.hxx"
33 #include "TIType.hxx"
34
35 #include "data/DataManager.hxx"
36 #include "data/PolymorphicMacroCache.hxx"
37 #include "gvn/ConstraintManager.hxx"
38 #include "dynlib_ast.h"
39
40 namespace analysis
41 {
42
43 class EXTERN_AST AnalysisVisitor : public ast::Visitor, public Chrono
44 {
45
46 public:
47
48     typedef std::map<symbol::Symbol, SymInfo> MapSymInfo;
49     typedef unordered_map<std::wstring, std::shared_ptr<CallAnalyzer>> MapSymCall;
50     typedef std::vector<Call *> Calls;
51
52 private:
53
54     MapSymInfo symsinfo;
55     Result _result;
56     Temporary temp;
57     Calls allCalls;
58     DataManager dm;
59     PolymorphicMacroCache pmc;
60     ConstraintManager cm;
61
62     std::vector<Result> multipleLHS;
63
64     static MapSymCall symscall;
65     static MapSymCall initCalls();
66
67 public:
68
69     static bool asDouble(ast::Exp & e, double & out);
70     static bool isDoubleConstant(const ast::Exp & e);
71     static bool asDoubleMatrix(ast::Exp & e, types::Double *& data);
72
73     AnalysisVisitor()
74     {
75         start_chrono();
76     }
77
78     virtual ~AnalysisVisitor()
79     {
80         //std::cerr << "delete AnalysisVisitor" << std::endl;
81     }
82
83     inline DataManager & getDM()
84     {
85         return dm;
86     }
87
88     inline GVN & getGVN()
89     {
90         return dm.getGVN();
91     }
92
93     inline PolymorphicMacroCache & getPMC()
94     {
95         return pmc;
96     }
97
98     // Only for debug use
99     inline void print_info()
100     {
101         stop_chrono();
102
103         //std::wcout << getGVN() << std::endl << std::endl; function z=foo(x,y);z=argn(2);endfunction;jit("x=123;y=456;t=foo(x,y)")
104         // function z=foo(x,y);[z,u]=argn(0);endfunction;jit("x=123;y=456;t=foo(x,y)")
105
106         std::wcerr << L"Analysis: " << *static_cast<Chrono *>(this) << std::endl;
107         //std::wcout << temp << std::endl;
108
109         std::wcerr << dm << std::endl;
110
111         std::wcerr << std::endl;
112     }
113
114     inline void finalize()
115     {
116         //dm.finalize(nullptr);
117     }
118
119     inline void setResult(Result & val)
120     {
121         _result = val;
122     }
123
124     inline void setResult(Result && val)
125     {
126         _result = val;
127     }
128
129     inline Result & getResult()
130     {
131         return _result;
132     }
133
134     inline const Temporary & getTemp() const
135     {
136         return temp;
137     }
138
139     inline Temporary & getTemp()
140     {
141         return temp;
142     }
143
144     inline const Calls & getCalls() const
145     {
146         return allCalls;
147     }
148
149     inline std::vector<Result> & getLHSContainer()
150     {
151         return multipleLHS;
152     }
153
154     inline ConstraintManager & getCM()
155     {
156         if (FunctionBlock * fblock = getDM().topFunction())
157         {
158             return fblock->getConstraintManager();
159         }
160         else
161         {
162             return cm;
163         }
164     }
165
166     template<typename T>
167     inline void visitArguments(const std::wstring & name, const unsigned int lhs, const TIType & calltype, ast::CallExp & e, T && args)
168     {
169         std::vector<Result> resargs;
170         std::vector<TIType> vargs;
171         vargs.reserve(args.size());
172         resargs.reserve(args.size());
173
174         for (typename T::const_iterator i = args.begin(), end = args.end(); i != end; ++i)
175         {
176             if ((*i)->getDecorator().res.hasBeenVisited())
177             {
178                 resargs.push_back((*i)->getDecorator().res);
179                 vargs.push_back((*i)->getDecorator().res.getType());
180             }
181             else
182             {
183                 (*i)->accept(*this);
184                 resargs.push_back(getResult());
185                 vargs.push_back(getResult().getType());
186             }
187         }
188
189         const symbol::Symbol & sym = static_cast<ast::SimpleVar &>(e.getName()).getSymbol();
190         int tempId = -1;
191         if (lhs > 1)
192         {
193             std::vector<TIType> types = dm.call(*this, lhs, sym, vargs, &e);
194             multipleLHS.clear();
195             multipleLHS.reserve(types.size());
196             for (const auto & type : types)
197             {
198                 multipleLHS.emplace_back(type);
199             }
200         }
201         else
202         {
203             std::vector<TIType> out = dm.call(*this, lhs, sym, vargs, &e);
204             if (lhs == 1)
205             {
206                 e.getDecorator().res = Result(out[0], tempId);
207                 e.getDecorator().setCall(Call(calltype, name, vargs));
208                 setResult(e.getDecorator().res);
209             }
210         }
211
212
213         /*TIType out = Checkers::check(name, vargs);
214           int tempId = -1;
215
216           if (true || (!out.isscalar() && args.size() == 1 && Checkers::isElementWise(name)))
217           {
218           Result & LR = resargs[0];
219           TIType & LT = vargs[0];
220           if (false && LR.istemp() && LT == out)
221           {
222           tempId = LR.getTempId();
223           }
224           else
225           {
226           tempId = temp.add(out);
227           }
228           }
229
230           e.getDecorator().res = Result(out, tempId);
231           e.getDecorator().setCall(Call(calltype, name, vargs));
232           setResult(e.getDecorator().res);*/
233     }
234
235     inline Info & getSymInfo(const symbol::Symbol & sym)
236     {
237         return dm.getInfo(sym);
238     }
239
240 private:
241
242     inline void pushCall(Call * c)
243     {
244         if (c)
245         {
246             allCalls.push_back(c);
247         }
248     }
249
250     void visit(ast::SimpleVar & e)
251     {
252         symbol::Symbol & sym = e.getSymbol();
253         Info & info = dm.read(sym, &e);
254         e.getDecorator().res = Result(info.type);
255         double val;
256         if (info.asDouble(val))
257         {
258             e.getDecorator().res.setValue(val);
259         }
260         else if (GVN::Value * gvnValue = info.getValue())
261         {
262             e.getDecorator().res.setGVNValue(gvnValue);
263         }
264
265         setResult(e.getDecorator().res);
266     }
267
268     void visit(ast::DollarVar & e)
269     {
270         // nothing to do
271     }
272
273     void visit(ast::ColonVar & e)
274     {
275         // nothing to do
276     }
277
278     void visit(ast::ArrayListVar & e)
279     {
280         const ast::exps_t & vars = e.getVars();
281         for (auto var : vars)
282         {
283             var->accept(*this);
284         }
285     }
286
287     void visit(ast::DoubleExp & e)
288     {
289         e.getDecorator().res = Result(TIType(dm.getGVN(), TIType::DOUBLE));
290         e.getDecorator().res.setValue(e.getValue());
291         setResult(e.getDecorator().res);
292     }
293
294     void visit(ast::BoolExp & e)
295     {
296         e.getDecorator().res = Result(TIType(dm.getGVN(), TIType::BOOLEAN));
297         setResult(e.getDecorator().res);
298     }
299
300     void visit(ast::StringExp & e)
301     {
302         e.getDecorator().res = Result(TIType(dm.getGVN(), TIType::STRING));
303         setResult(e.getDecorator().res);
304     }
305
306     void visit(ast::CommentExp & e)
307     {
308         // ignored
309     }
310
311     void visit(ast::NilExp & e)
312     {
313         // nothing to do
314     }
315
316     void visit(ast::CallExp & e, const unsigned int lhs)
317     {
318         if (e.getName().isSimpleVar())
319         {
320             ast::SimpleVar & var = static_cast<ast::SimpleVar &>(e.getName());
321             symbol::Symbol & sym = var.getSymbol();
322             const std::wstring & name = sym.getName();
323             Info & info = getSymInfo(sym); // that put the sym in the current block !
324
325             // Special analysis cases: size, zeros, ones, ...
326             MapSymCall::iterator it = symscall.find(sym.getName());
327             if (it != symscall.end() && it->second.get()->analyze(*this, lhs, e))
328             {
329                 pushCall(e.getDecorator().getCall());
330                 return;
331             }
332
333             visitArguments(name, lhs, info.type, e, e.getArgs());
334             pushCall(e.getDecorator().getCall());
335         }
336     }
337
338     void visit(ast::CallExp & e)
339     {
340         visit(e, 1);
341     }
342
343     void visit(ast::CellCallExp & e)
344     {
345         visit(static_cast<ast::CallExp &>(e));
346     }
347
348     void visit(ast::OpExp & e)
349     {
350         e.getLeft().accept(*this);
351         Result LR = getResult();
352         e.getRight().accept(*this);
353         Result & RR = getResult();
354         TIType & LT = LR.getType();
355         TIType & RT = RR.getType();
356         TIType resT;
357         int tempId = -1;
358
359         switch (e.getOper())
360         {
361             case ast::OpExp::plus :
362             case ast::OpExp::minus :
363             case ast::OpExp::dottimes :
364             {
365                 // TODO: check if the rules for addition and subtraction are the same
366                 // If a temp is LHS or RHS we could use it again to avoid a malloc
367                 // TODO: It should be ok for element-wise operations (check this assumption)
368                 resT = check_add(dm.getGVN(), LT, RT);
369                 if (resT.isUnknownDims())
370                 {
371                     const bool ret = getCM().check(ConstraintManager::SAMEDIMS, LT.rows.getValue(), LT.cols.getValue(), RT.rows.getValue(), RT.cols.getValue());
372                     if (ret)
373                     {
374                         resT = check_add(dm.getGVN(), LT, RT);
375                     }
376                     else
377                     {
378                         resT = check_add(dm.getGVN(), LT.asUnknownMatrix(), RT.asUnknownMatrix());
379                     }
380                 }
381                 if (!resT.isscalar())
382                 {
383                     if (LR.istemp() && LT == resT)
384                     {
385                         tempId = LR.getTempId();
386                         temp.remove(RT, RR.getTempId());
387                     }
388                     else if (RR.istemp() && RT == resT)
389                     {
390                         tempId = RR.getTempId();
391                         temp.remove(LT, LR.getTempId());
392                     }
393                     else
394                     {
395                         tempId = temp.add(resT);
396                     }
397                 }
398                 break;
399             }
400             case ast::OpExp::times :
401             {
402                 resT = check_times(dm.getGVN(), LT, RT);
403                 if (resT.isUnknownDims())
404                 {
405                     const bool ret = getCM().check(ConstraintManager::EQUAL, LT.cols.getValue(), RT.rows.getValue());
406                     if (ret)
407                     {
408                         resT = check_times(dm.getGVN(), LT, RT);
409                     }
410                     else
411                     {
412                         resT = check_times(dm.getGVN(), LT.asUnknownMatrix(), RT.asUnknownMatrix());
413                     }
414                 }
415                 temp.remove(LT, LR.getTempId());
416                 temp.remove(RT, RR.getTempId());
417                 if (resT.isknown() && !resT.isscalar())
418                 {
419                     tempId = temp.add(resT);
420                 }
421                 break;
422             }
423             case ast::OpExp::rdivide :
424             {
425                 // multiplication is not commutative for matrice pxq
426                 resT = check_times(dm.getGVN(), LT, RT);
427                 temp.remove(LT, LR.getTempId());
428                 temp.remove(RT, RR.getTempId());
429                 if (resT.isknown() && !resT.isscalar())
430                 {
431                     tempId = temp.add(resT);
432                 }
433                 break;
434             }
435             case ast::OpExp::krontimes :
436             {
437                 resT = check_krontimes(dm.getGVN(), LT, RT);
438                 temp.remove(LT, LR.getTempId());
439                 temp.remove(RT, RR.getTempId());
440                 if (resT.isknown() && !resT.isscalar())
441                 {
442                     tempId = temp.add(resT);
443                 }
444                 break;
445             }
446         }
447
448         e.getDecorator().res = Result(resT, tempId);
449         setResult(e.getDecorator().res);
450     }
451
452     void visit(ast::LogicalOpExp & e)
453     {
454         e.getLeft().accept(*this);
455         e.getRight().accept(*this);
456     }
457
458     void visit(ast::AssignExp & e)
459     {
460         /*if (e.left_exp_get().is_simple_var())
461           {
462           ast::SimpleVar & var = static_cast<ast::SimpleVar &>(e.left_exp_get());
463           symbol::Symbol & sym = var.name_get();
464
465           e.right_exp_get().accept(*this);
466           Result & RR = getResult();
467           // Don't remove tmp... temp.remove(RR);
468           var.getDecorator().res = RR;
469
470           set_sym_use(sym, SymInfo::REPLACE);
471           set_sym_type(sym, getResult().get_type());
472           }
473           elseg
474           {
475           // TODO: handle this case
476           }*/
477
478         if (e.getLeftExp().isSimpleVar())
479         {
480             ast::SimpleVar & var = static_cast<ast::SimpleVar &>(e.getLeftExp());
481             symbol::Symbol & sym = var.getSymbol();
482
483             if (e.getRightExp().isSimpleVar())
484             {
485                 // We have a=b (so the data associated to b is shared with a)
486                 symbol::Symbol & symR = static_cast<ast::SimpleVar &>(e.getRightExp()).getSymbol();
487                 dm.share(sym, symR, getSymInfo(symR).getType(), &e);
488             }
489             else
490             {
491                 // We have something like a=expression
492                 if (e.getRightExp().isCallExp())
493                 {
494                     visit(static_cast<ast::CallExp &>(e.getRightExp()), /* LHS */ 1);
495                 }
496                 else
497                 {
498                     e.getRightExp().accept(*this);
499                 }
500                 Result & RR = getResult();
501                 // Don't remove tmp... temp.remove(RR);
502                 var.getDecorator().res = RR;
503                 Info & info = dm.define(sym, RR.getType(), &e);
504                 double value;
505                 if (asDouble(e.getRightExp(), value) || RR.getValue(value))
506                 {
507                     info.setValue(value);
508                 }
509                 if (GVN::Value * gvnValue = RR.getGVNValue())
510                 {
511                     info.setValue(gvnValue);
512                 }
513             }
514         }
515         else if (e.getLeftExp().isCallExp())
516         {
517             // We have something like a(12)=...
518             ast::CallExp & ce = static_cast<ast::CallExp &>(e.getLeftExp());
519             if (ce.getName().isSimpleVar())
520             {
521                 symbol::Symbol & symL = static_cast<ast::SimpleVar &>(ce.getName()).getSymbol();
522                 e.getRightExp().accept(*this);
523                 Result & RR = getResult();
524                 ce.getDecorator().res = RR;
525                 dm.write(symL, RR.getType(), &e);
526             }
527         }
528         else if (e.getLeftExp().isAssignListExp())
529         {
530             ast::AssignListExp & ale = static_cast<ast::AssignListExp &>(e.getLeftExp());
531             if (e.getRightExp().isCallExp())
532             {
533                 const ast::exps_t & exps = ale.getExps();
534                 visit(static_cast<ast::CallExp &>(e.getRightExp()), /* LHS */ exps.size());
535                 std::vector<Result>::iterator j = multipleLHS.begin();
536                 for (const auto exp : exps)
537                 {
538                     // TODO: handle fields...
539                     if (exp->isSimpleVar() && j != multipleLHS.end())
540                     {
541                         ast::SimpleVar & var = *static_cast<ast::SimpleVar *>(exp);
542                         symbol::Symbol & sym = var.getSymbol();
543                         Info & info = dm.define(sym, j->getType(), exp);
544                         double value;
545                         if (j->getValue(value))
546                         {
547                             info.setValue(value);
548                         }
549                         if (GVN::Value * gvnValue = j->getGVNValue())
550                         {
551                             info.setValue(gvnValue);
552                         }
553                         ++j;
554                     }
555                 }
556             }
557         }
558     }
559
560     void visit(ast::IfExp & e)
561     {
562         dm.addBlock(Block::EXCLUSIVE, &e);
563         // TODO: analyze the test, e.g. a=argn(2); if a==1....
564         // When we analyze a macro call, argn(2) is known so we are able to take the good branch and skip the analysis
565         // the others.
566         // There is a lot of code with: rhs=argn(2) or if argn(2)==1 ... then...
567         e.getTest().accept(*this);
568         dm.addBlock(Block::NORMAL, &e.getThen());
569         e.getThen().accept(*this);
570         dm.finalizeBlock();
571         dm.addBlock(Block::NORMAL, e.hasElse() ? &e.getElse() : nullptr);
572         if (e.hasElse())
573         {
574             e.getElse().accept(*this);
575         }
576         dm.finalizeBlock();
577         dm.finalizeBlock();
578     }
579
580     void visit(ast::WhileExp & e)
581     {
582         e.getTest().accept(*this);
583         e.getBody().accept(*this);
584     }
585
586     void visit(ast::ForExp & e)
587     {
588         dm.addBlock(Block::LOOP, &e);
589         e.getVardec().accept(*this);
590         dm.addBlock(Block::NORMAL, &e.getBody());
591         e.getBody().accept(*this);
592
593         if (dm.requiresAnotherTrip())
594         {
595             std::cerr << "Invalid forexp: types or refcount are not the same before and after the loop" << std::endl;
596
597             dm.finalizeBlock();
598             dm.addBlock(Block::NORMAL, &e.getBody());
599             e.getBody().accept(*this);
600         }
601
602         dm.finalizeBlock();
603         dm.finalizeBlock();
604     }
605
606     void visit(ast::BreakExp & e)
607     {
608         // nothing to do
609     }
610
611     void visit(ast::ContinueExp & e)
612     {
613         // nothing to do
614     }
615
616     void visit(ast::TryCatchExp & e)
617     {
618         e.getTry().accept(*this);
619         e.getCatch().accept(*this);
620     }
621
622     void visit(ast::SelectExp & e)
623     {
624         dm.addBlock(Block::EXCLUSIVE, &e);
625         e.getSelect()->accept(*this);
626         ast::exps_t cases = e.getCases();
627         for (auto exp : cases)
628         {
629             dm.addBlock(Block::NORMAL, exp);
630             exp->accept(*this);
631             dm.finalizeBlock();
632         }
633
634         if (e.getDefaultCase())
635         {
636             dm.addBlock(Block::NORMAL, e.getDefaultCase());
637             e.getDefaultCase()->accept(*this);
638             dm.finalizeBlock();
639         }
640         dm.finalizeBlock();
641     }
642
643     void visit(ast::CaseExp & e)
644     {
645         e.getTest()->accept(*this);
646         e.getBody()->accept(*this);
647     }
648
649     void visit(ast::ReturnExp & e)
650     {
651         // Bug with return;
652         //e.exp_get().accept(*this);
653     }
654
655     void visit(ast::FieldExp & e)
656     {
657         // a.b.c <=> (a.b).c where a.b is the head and c is the tail
658
659         //e.head_get()->accept(*this);
660         //e.tail_get()->accept(*this);
661     }
662
663     void visit(ast::NotExp & e)
664     {
665         e.getExp().accept(*this);
666     }
667
668     void visit(ast::TransposeExp & e)
669     {
670         e.getExp().accept(*this);
671         Result & res = getResult();
672         const TIType & type = res.getType();
673         e.getDecorator().res = Result(TIType(dm.getGVN(), type.type, type.cols, type.rows));
674         setResult(e.getDecorator().res);
675     }
676
677     void visit(ast::MatrixExp & e);
678     void visit(ast::MatrixLineExp & e) { }
679
680     void visit(ast::CellExp & e)
681     {
682         visit(static_cast<ast::MatrixExp &>(e));
683     }
684
685     void visit(ast::SeqExp & e)
686     {
687         for (const auto exp : e.getExps())
688         {
689             if (exp->isCallExp())
690             {
691                 visit(*static_cast<ast::CallExp *>(exp), /* LHS */ 0);
692             }
693             else
694             {
695                 exp->accept(*this);
696             }
697         }
698     }
699
700     void visit(ast::ArrayListExp & e)
701     {
702         const ast::exps_t & exps = e.getExps();
703         for (const auto exp : e.getExps())
704         {
705             exp->accept(*this);
706         }
707     }
708
709     void visit(ast::AssignListExp & e)
710     {
711         visit(static_cast<ast::ArrayListExp &>(e));
712     }
713
714     void visit(ast::VarDec & e)
715     {
716         // VarDec is only used in For loop for iterator declaration
717         const symbol::Symbol & sym = e.getSymbol();
718         if (e.getInit().isListExp())
719         {
720             ast::ListExp & le = static_cast<ast::ListExp &>(e.getInit());
721             double start, step, end;
722             if (asDouble(le.getStart(), start) && asDouble(le.getStep(), step) && asDouble(le.getEnd(), end))
723             {
724                 ForList64 fl(start, step, end);
725                 e.setListInfo(fl);
726                 dm.define(sym, fl.getType(), &e).isint = true;
727                 // No need to visit the list (it has been visited just before)
728             }
729             else
730             {
731                 e.setListInfo(ForList64());
732                 le.accept(*this);
733             }
734         }
735     }
736
737     void visit(ast::FunctionDec & e)
738     {
739         /*e.args_get().accept(*this);
740           e.returns_get().accept(*this);
741           e.body_get().accept(*this);*/
742         dm.macrodef(&e);
743     }
744
745     void visit(ast::ListExp & e);
746
747     void visit(ast::OptimizedExp & e)
748     {
749     }
750
751     void visit(ast::DAXPYExp & e)
752     {
753     }
754 };
755
756 } // namespace analysis
757
758 #endif // __ANALYSIS_VISITOR_HXX__