Analysis: replace constant in Result by a C++ union
[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         Result & res = e.getDecorator().setResult(info.type);
255         res.setConstant(info.getConstant());
256         setResult(res);
257     }
258
259     void visit(ast::DollarVar & e)
260     {
261         // nothing to do
262     }
263
264     void visit(ast::ColonVar & e)
265     {
266         // nothing to do
267     }
268
269     void visit(ast::ArrayListVar & e)
270     {
271         const ast::exps_t & vars = e.getVars();
272         for (auto var : vars)
273         {
274             var->accept(*this);
275         }
276     }
277
278     void visit(ast::DoubleExp & e)
279     {
280         Result & res = e.getDecorator().setResult(TIType(dm.getGVN(), TIType::DOUBLE));
281         res.getConstant().set(e.getValue());
282         setResult(res);
283     }
284
285     void visit(ast::BoolExp & e)
286     {
287         Result & res = e.getDecorator().setResult(TIType(dm.getGVN(), TIType::BOOLEAN));
288         res.getConstant().set(e.getValue());
289         setResult(res);
290     }
291
292     void visit(ast::StringExp & e)
293     {
294         Result & res = e.getDecorator().setResult(TIType(dm.getGVN(), TIType::STRING));
295         res.getConstant().set(&e.getValue());
296         setResult(res);
297     }
298
299     void visit(ast::CommentExp & e)
300     {
301         // ignored
302     }
303
304     void visit(ast::NilExp & e)
305     {
306         // nothing to do
307     }
308
309     void visit(ast::CallExp & e, const unsigned int lhs)
310     {
311         if (e.getName().isSimpleVar())
312         {
313             ast::SimpleVar & var = static_cast<ast::SimpleVar &>(e.getName());
314             symbol::Symbol & sym = var.getSymbol();
315             const std::wstring & name = sym.getName();
316             Info & info = getSymInfo(sym); // that put the sym in the current block !
317
318             // Special analysis cases: size, zeros, ones, ...
319             MapSymCall::iterator it = symscall.find(sym.getName());
320             if (it != symscall.end() && it->second.get()->analyze(*this, lhs, e))
321             {
322                 pushCall(e.getDecorator().getCall());
323                 return;
324             }
325
326             visitArguments(name, lhs, info.type, e, e.getArgs());
327             pushCall(e.getDecorator().getCall());
328         }
329     }
330
331     void visit(ast::CallExp & e)
332     {
333         visit(e, 1);
334     }
335
336     void visit(ast::CellCallExp & e)
337     {
338         visit(static_cast<ast::CallExp &>(e));
339     }
340
341     void visit(ast::OpExp & e)
342     {
343         e.getLeft().accept(*this);
344         Result LR = getResult();
345         e.getRight().accept(*this);
346         Result & RR = getResult();
347         TIType & LT = LR.getType();
348         TIType & RT = RR.getType();
349         TIType resT;
350         int tempId = -1;
351
352         switch (e.getOper())
353         {
354             case ast::OpExp::plus :
355             case ast::OpExp::minus :
356             case ast::OpExp::dottimes :
357             {
358                 // TODO: check if the rules for addition and subtraction are the same
359                 // If a temp is LHS or RHS we could use it again to avoid a malloc
360                 // TODO: It should be ok for element-wise operations (check this assumption)
361                 resT = check_add(dm.getGVN(), LT, RT);
362                 if (resT.isUnknownDims())
363                 {
364                     const bool ret = getCM().check(ConstraintManager::SAMEDIMS, LT.rows.getValue(), LT.cols.getValue(), RT.rows.getValue(), RT.cols.getValue());
365                     if (ret)
366                     {
367                         resT = check_add(dm.getGVN(), LT, RT);
368                     }
369                     else
370                     {
371                         resT = check_add(dm.getGVN(), LT.asUnknownMatrix(), RT.asUnknownMatrix());
372                     }
373                 }
374                 if (!resT.isscalar())
375                 {
376                     if (LR.istemp() && LT == resT)
377                     {
378                         tempId = LR.getTempId();
379                         temp.remove(RT, RR.getTempId());
380                     }
381                     else if (RR.istemp() && RT == resT)
382                     {
383                         tempId = RR.getTempId();
384                         temp.remove(LT, LR.getTempId());
385                     }
386                     else
387                     {
388                         tempId = temp.add(resT);
389                     }
390                 }
391                 break;
392             }
393             case ast::OpExp::times :
394             {
395                 resT = check_times(dm.getGVN(), LT, RT);
396                 if (resT.isUnknownDims())
397                 {
398                     const bool ret = getCM().check(ConstraintManager::EQUAL, LT.cols.getValue(), RT.rows.getValue());
399                     if (ret)
400                     {
401                         resT = check_times(dm.getGVN(), LT, RT);
402                     }
403                     else
404                     {
405                         resT = check_times(dm.getGVN(), LT.asUnknownMatrix(), RT.asUnknownMatrix());
406                     }
407                 }
408                 temp.remove(LT, LR.getTempId());
409                 temp.remove(RT, RR.getTempId());
410                 if (resT.isknown() && !resT.isscalar())
411                 {
412                     tempId = temp.add(resT);
413                 }
414                 break;
415             }
416             case ast::OpExp::rdivide :
417             {
418                 // multiplication is not commutative for matrice pxq
419                 resT = check_times(dm.getGVN(), LT, RT);
420                 temp.remove(LT, LR.getTempId());
421                 temp.remove(RT, RR.getTempId());
422                 if (resT.isknown() && !resT.isscalar())
423                 {
424                     tempId = temp.add(resT);
425                 }
426                 break;
427             }
428             case ast::OpExp::krontimes :
429             {
430                 resT = check_krontimes(dm.getGVN(), LT, RT);
431                 temp.remove(LT, LR.getTempId());
432                 temp.remove(RT, RR.getTempId());
433                 if (resT.isknown() && !resT.isscalar())
434                 {
435                     tempId = temp.add(resT);
436                 }
437                 break;
438             }
439         }
440
441         e.getDecorator().res = Result(resT, tempId);
442         setResult(e.getDecorator().res);
443     }
444
445     void visit(ast::LogicalOpExp & e)
446     {
447         e.getLeft().accept(*this);
448         e.getRight().accept(*this);
449     }
450
451     void visit(ast::AssignExp & e)
452     {
453         /*if (e.left_exp_get().is_simple_var())
454           {
455           ast::SimpleVar & var = static_cast<ast::SimpleVar &>(e.left_exp_get());
456           symbol::Symbol & sym = var.name_get();
457
458           e.right_exp_get().accept(*this);
459           Result & RR = getResult();
460           // Don't remove tmp... temp.remove(RR);
461           var.getDecorator().res = RR;
462
463           set_sym_use(sym, SymInfo::REPLACE);
464           set_sym_type(sym, getResult().get_type());
465           }
466           elseg
467           {
468           // TODO: handle this case
469           }*/
470
471         if (e.getLeftExp().isSimpleVar())
472         {
473             ast::SimpleVar & var = static_cast<ast::SimpleVar &>(e.getLeftExp());
474             symbol::Symbol & sym = var.getSymbol();
475
476             if (e.getRightExp().isSimpleVar())
477             {
478                 // We have a=b (so the data associated to b is shared with a)
479                 symbol::Symbol & symR = static_cast<ast::SimpleVar &>(e.getRightExp()).getSymbol();
480                 dm.share(sym, symR, getSymInfo(symR).getType(), &e);
481             }
482             else
483             {
484                 // We have something like a=expression
485                 if (e.getRightExp().isCallExp())
486                 {
487                     visit(static_cast<ast::CallExp &>(e.getRightExp()), /* LHS */ 1);
488                 }
489                 else
490                 {
491                     e.getRightExp().accept(*this);
492                 }
493                 Result & RR = getResult();
494                 // Don't remove tmp... temp.remove(RR);
495                 var.getDecorator().res = RR;
496                 Info & info = dm.define(sym, RR.getType(), &e);
497                 double value;
498                 if (asDouble(e.getRightExp(), value) || RR.getConstant().getDblValue(value))
499                 {
500                     info.getConstant().set(value);
501                 }
502                 if (GVN::Value * gvnValue = RR.getConstant().getGVNValue())
503                 {
504                     info.getConstant().set(gvnValue);
505                 }
506             }
507         }
508         else if (e.getLeftExp().isCallExp())
509         {
510             // We have something like a(12)=...
511             ast::CallExp & ce = static_cast<ast::CallExp &>(e.getLeftExp());
512             if (ce.getName().isSimpleVar())
513             {
514                 symbol::Symbol & symL = static_cast<ast::SimpleVar &>(ce.getName()).getSymbol();
515                 e.getRightExp().accept(*this);
516                 Result & RR = getResult();
517                 ce.getDecorator().res = RR;
518                 dm.write(symL, RR.getType(), &e);
519             }
520         }
521         else if (e.getLeftExp().isAssignListExp())
522         {
523             ast::AssignListExp & ale = static_cast<ast::AssignListExp &>(e.getLeftExp());
524             if (e.getRightExp().isCallExp())
525             {
526                 const ast::exps_t & exps = ale.getExps();
527                 visit(static_cast<ast::CallExp &>(e.getRightExp()), /* LHS */ exps.size());
528                 std::vector<Result>::iterator j = multipleLHS.begin();
529                 for (const auto exp : exps)
530                 {
531                     // TODO: handle fields...
532                     if (exp->isSimpleVar() && j != multipleLHS.end())
533                     {
534                         ast::SimpleVar & var = *static_cast<ast::SimpleVar *>(exp);
535                         symbol::Symbol & sym = var.getSymbol();
536                         Info & info = dm.define(sym, j->getType(), exp);
537                         info.setConstant(j->getConstant());
538                         ++j;
539                     }
540                 }
541             }
542         }
543     }
544
545     void visit(ast::IfExp & e)
546     {
547         dm.addBlock(Block::EXCLUSIVE, &e);
548         // TODO: analyze the test, e.g. a=argn(2); if a==1....
549         // When we analyze a macro call, argn(2) is known so we are able to take the good branch and skip the analysis
550         // the others.
551         // There is a lot of code with: rhs=argn(2) or if argn(2)==1 ... then...
552         e.getTest().accept(*this);
553         dm.addBlock(Block::NORMAL, &e.getThen());
554         e.getThen().accept(*this);
555         dm.finalizeBlock();
556         dm.addBlock(Block::NORMAL, e.hasElse() ? &e.getElse() : nullptr);
557         if (e.hasElse())
558         {
559             e.getElse().accept(*this);
560         }
561         dm.finalizeBlock();
562         dm.finalizeBlock();
563     }
564
565     void visit(ast::WhileExp & e)
566     {
567         e.getTest().accept(*this);
568         e.getBody().accept(*this);
569     }
570
571     void visit(ast::ForExp & e)
572     {
573         dm.addBlock(Block::LOOP, &e);
574         e.getVardec().accept(*this);
575         dm.addBlock(Block::NORMAL, &e.getBody());
576         e.getBody().accept(*this);
577
578         if (dm.requiresAnotherTrip())
579         {
580             std::cerr << "Invalid forexp: types or refcount are not the same before and after the loop" << std::endl;
581
582             dm.finalizeBlock();
583             dm.addBlock(Block::NORMAL, &e.getBody());
584             e.getBody().accept(*this);
585         }
586
587         dm.finalizeBlock();
588         dm.finalizeBlock();
589     }
590
591     void visit(ast::BreakExp & e)
592     {
593         // nothing to do
594     }
595
596     void visit(ast::ContinueExp & e)
597     {
598         // nothing to do
599     }
600
601     void visit(ast::TryCatchExp & e)
602     {
603         e.getTry().accept(*this);
604         e.getCatch().accept(*this);
605     }
606
607     void visit(ast::SelectExp & e)
608     {
609         dm.addBlock(Block::EXCLUSIVE, &e);
610         e.getSelect()->accept(*this);
611         ast::exps_t cases = e.getCases();
612         for (auto exp : cases)
613         {
614             dm.addBlock(Block::NORMAL, exp);
615             exp->accept(*this);
616             dm.finalizeBlock();
617         }
618
619         if (e.getDefaultCase())
620         {
621             dm.addBlock(Block::NORMAL, e.getDefaultCase());
622             e.getDefaultCase()->accept(*this);
623             dm.finalizeBlock();
624         }
625         dm.finalizeBlock();
626     }
627
628     void visit(ast::CaseExp & e)
629     {
630         e.getTest()->accept(*this);
631         e.getBody()->accept(*this);
632     }
633
634     void visit(ast::ReturnExp & e)
635     {
636         // Bug with return;
637         //e.exp_get().accept(*this);
638     }
639
640     void visit(ast::FieldExp & e)
641     {
642         // a.b.c <=> (a.b).c where a.b is the head and c is the tail
643
644         //e.head_get()->accept(*this);
645         //e.tail_get()->accept(*this);
646     }
647
648     void visit(ast::NotExp & e)
649     {
650         e.getExp().accept(*this);
651     }
652
653     void visit(ast::TransposeExp & e)
654     {
655         e.getExp().accept(*this);
656         Result & res = getResult();
657         const TIType & type = res.getType();
658         e.getDecorator().res = Result(TIType(dm.getGVN(), type.type, type.cols, type.rows));
659         setResult(e.getDecorator().res);
660     }
661
662     void visit(ast::MatrixExp & e);
663     void visit(ast::MatrixLineExp & e) { }
664
665     void visit(ast::CellExp & e)
666     {
667         visit(static_cast<ast::MatrixExp &>(e));
668     }
669
670     void visit(ast::SeqExp & e)
671     {
672         for (const auto exp : e.getExps())
673         {
674             if (exp->isCallExp())
675             {
676                 visit(*static_cast<ast::CallExp *>(exp), /* LHS */ 0);
677             }
678             else
679             {
680                 exp->accept(*this);
681             }
682         }
683     }
684
685     void visit(ast::ArrayListExp & e)
686     {
687         const ast::exps_t & exps = e.getExps();
688         for (const auto exp : e.getExps())
689         {
690             exp->accept(*this);
691         }
692     }
693
694     void visit(ast::AssignListExp & e)
695     {
696         visit(static_cast<ast::ArrayListExp &>(e));
697     }
698
699     void visit(ast::VarDec & e)
700     {
701         // VarDec is only used in For loop for iterator declaration
702         const symbol::Symbol & sym = e.getSymbol();
703         if (e.getInit().isListExp())
704         {
705             ast::ListExp & le = static_cast<ast::ListExp &>(e.getInit());
706             double start, step, end;
707             if (asDouble(le.getStart(), start) && asDouble(le.getStep(), step) && asDouble(le.getEnd(), end))
708             {
709                 ForList64 fl(start, step, end);
710                 e.setListInfo(fl);
711                 dm.define(sym, fl.getType(), &e).isint = true;
712                 // No need to visit the list (it has been visited just before)
713             }
714             else
715             {
716                 e.setListInfo(ForList64());
717                 le.accept(*this);
718             }
719         }
720     }
721
722     void visit(ast::FunctionDec & e)
723     {
724         /*e.args_get().accept(*this);
725           e.returns_get().accept(*this);
726           e.body_get().accept(*this);*/
727         dm.macrodef(&e);
728     }
729
730     void visit(ast::ListExp & e);
731
732     void visit(ast::OptimizedExp & e)
733     {
734     }
735
736     void visit(ast::DAXPYExp & e)
737     {
738     }
739 };
740
741 } // namespace analysis
742
743 #endif // __ANALYSIS_VISITOR_HXX__