59378cde1383814f0f12db20e2960da8b3f49033
[scilab.git] / scilab / modules / ast / includes / analysis / data / LoopAnalyzer.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 __LOOP_ANALYZER_HXX__
14 #define __LOOP_ANALYZER_HXX__
15
16 #include <iostream>
17 #include <string>
18 #include <sstream>
19 #include <stack>
20 #include <unordered_map>
21
22 #include "visitor.hxx"
23 #include "execvisitor.hxx"
24 #include "allexp.hxx"
25 #include "allvar.hxx"
26 #include "Chrono.hxx"
27 #include "tools.hxx"
28
29 namespace analysis
30 {
31
32 class LoopAnalyzer : public ast::Visitor, public Chrono
33 {
34     std::unordered_map<ast::Exp *, tools::SymbolSet> assigned;
35     std::unordered_map<ast::Exp *, tools::SymbolSet> inserted;
36     std::unordered_map<ast::Exp *, tools::SymbolSet> shared;
37     std::stack<ast::Exp *> loops;
38     ast::Exp * seq;
39
40 public:
41
42     LoopAnalyzer(ast::Exp * _seq) : seq(_seq)
43     {
44         //start_chrono();
45         static_cast<ast::SeqExp *>(seq)->accept(*this);
46         //stop_chrono();
47     }
48
49     virtual ~LoopAnalyzer()
50     {
51     }
52
53     virtual LoopAnalyzer* clone()
54     {
55         return new LoopAnalyzer(seq->clone());
56     }
57
58
59     inline bool isAssigned(ast::Exp * e, const symbol::Symbol & sym) const
60     {
61         if (e)
62         {
63             const auto i = assigned.find(e);
64             if (i != assigned.end())
65             {
66                 return i->second.find(sym) != i->second.end();
67             }
68         }
69         return false;
70     }
71
72     inline const tools::SymbolSet * getInserted(ast::Exp * e) const
73     {
74         if (e)
75         {
76             const auto i = inserted.find(e);
77             if (i != inserted.end())
78             {
79                 return &i->second;
80             }
81         }
82         return nullptr;
83     }
84
85     inline const tools::SymbolSet * getShared(ast::Exp * e) const
86     {
87         if (e)
88         {
89             const auto i = shared.find(e);
90             if (i != shared.end())
91             {
92                 return &i->second;
93             }
94         }
95         return nullptr;
96     }
97
98     friend std::wostream & operator<<(std::wostream & out, const LoopAnalyzer & la)
99     {
100         if (!la.assigned.empty())
101         {
102             out << L" Assigned:\n";
103             for (const auto & p : la.assigned)
104             {
105                 out << L"  -Loop at " << p.first->getLocation().getLocationString() << L": ";
106                 tools::printSet(p.second, out);
107                 out << L"\n";
108             }
109         }
110
111         if (!la.inserted.empty())
112         {
113             out << L" Inserted:\n";
114             for (const auto & p : la.inserted)
115             {
116                 out << L"  -Loop at " << p.first->getLocation().getLocationString() << L": ";
117                 tools::printSet(p.second, out);
118                 out << L"\n";
119             }
120         }
121
122         if (!la.shared.empty())
123         {
124             out << L" Shared:\n";
125             for (const auto & p : la.shared)
126             {
127                 out << L"  -Loop at " << p.first->getLocation().getLocationString() << L": ";
128                 tools::printSet(p.second, out);
129                 out << L"\n";
130             }
131         }
132
133         return out;
134     }
135
136     inline void print_info()
137     {
138         std::wcerr << L"Loop analyze: " << *static_cast<Chrono *>(this) << std::endl
139                    << *this << std::endl;
140     }
141
142 private:
143
144     inline void emplace(std::unordered_map<ast::Exp *, tools::SymbolSet> & map, const symbol::Symbol & sym)
145     {
146         ast::Exp * loop = loops.top();
147         auto i = map.find(loop);
148         if (i == map.end())
149         {
150             i = map.emplace(loop, tools::SymbolSet()).first;
151         }
152         i->second.emplace(sym);
153     }
154
155     inline void pushAssigned()
156     {
157         ast::Exp * last = loops.top();
158         loops.pop();
159
160         if (!loops.empty())
161         {
162             ast::Exp * penult = loops.top();
163             const auto i = assigned.find(last);
164             if (i != assigned.end())
165             {
166                 const auto j = assigned.find(penult);
167                 if (j == assigned.end())
168                 {
169                     assigned.emplace(penult, i->second);
170                 }
171                 else
172                 {
173                     j->second.insert(i->second.begin(), i->second.end());
174                 }
175             }
176         }
177     }
178
179     void visit(ast::SimpleVar & e)
180     {
181     }
182
183     void visit(ast::DollarVar & e)
184     {
185     }
186
187     void visit(ast::ColonVar & e)
188     {
189     }
190
191     void visit(ast::ArrayListVar & e)
192     {
193     }
194
195     void visit(ast::DoubleExp & e)
196     {
197     }
198
199     void visit(ast::BoolExp & e)
200     {
201     }
202
203     void visit(ast::StringExp & e)
204     {
205     }
206
207     void visit(ast::CommentExp & e)
208     {
209     }
210
211     void visit(ast::NilExp & e)
212     {
213     }
214
215     void visit(ast::CallExp & e)
216     {
217     }
218
219     void visit(ast::CellCallExp & e)
220     {
221     }
222
223     void visit(ast::OpExp & e)
224     {
225     }
226
227     void visit(ast::LogicalOpExp & e)
228     {
229     }
230
231     void visit(ast::AssignExp & e)
232     {
233         if (e.getLeftExp().isSimpleVar())
234         {
235             // A = ....
236             const symbol::Symbol & Lsym = static_cast<ast::SimpleVar &>(e.getLeftExp()).getSymbol();
237             emplace(assigned, Lsym);
238             if (e.getRightExp().isSimpleVar())
239             {
240                 const symbol::Symbol & Rsym = static_cast<ast::SimpleVar &>(e.getRightExp()).getSymbol();
241                 emplace(shared, Lsym);
242                 emplace(shared, Rsym);
243             }
244         }
245         else if (e.getLeftExp().isCallExp())
246         {
247             // A(...) = ...
248             ast::CallExp & ce = static_cast<ast::CallExp &>(e.getLeftExp());
249             if (ce.getName().isSimpleVar())
250             {
251                 const symbol::Symbol & Lsym = static_cast<ast::SimpleVar &>(ce.getName()).getSymbol();
252                 emplace(inserted, Lsym);
253                 emplace(assigned, Lsym);
254             }
255         }
256         else if (e.getLeftExp().isAssignListExp())
257         {
258             // [A, ...] =
259             ast::AssignListExp & ale = static_cast<ast::AssignListExp &>(e.getLeftExp());
260             for (const auto re : ale.getExps())
261             {
262                 if (re->isSimpleVar())
263                 {
264                     const symbol::Symbol & Lsym = static_cast<const ast::SimpleVar *>(re)->getSymbol();
265                     emplace(assigned, Lsym);
266                 }
267             }
268         }
269     }
270
271     void visit(ast::IfExp & e)
272     {
273         e.getThen().accept(*this);
274         if (e.hasElse())
275         {
276             e.getElse().accept(*this);
277         }
278     }
279
280     void visit(ast::WhileExp & e)
281     {
282         loops.push(&e);
283         e.getBody().accept(*this);
284
285         // pushAssigned pops loops
286         pushAssigned();
287     }
288
289     void visit(ast::ForExp & e)
290     {
291         loops.push(&e);
292         e.getVardec().accept(*this);
293         e.getBody().accept(*this);
294         pushAssigned();
295     }
296
297     void visit(ast::BreakExp & e)
298     {
299     }
300
301     void visit(ast::ContinueExp & e)
302     {
303     }
304
305     void visit(ast::TryCatchExp & e)
306     {
307         e.getTry().accept(*this);
308         e.getCatch().accept(*this);
309     }
310
311     void visit(ast::SelectExp & e)
312     {
313         e.getSelect()->accept(*this);
314         for (auto _e : e.getCases())
315         {
316             _e->accept(*this);
317         }
318         if (ast::Exp * def = e.getDefaultCase())
319         {
320             def->accept(*this);
321         }
322     }
323
324     void visit(ast::CaseExp & e)
325     {
326         e.getBody()->accept(*this);
327     }
328
329     void visit(ast::ReturnExp & e)
330     {
331     }
332
333     void visit(ast::FieldExp & e)
334     {
335     }
336
337     void visit(ast::NotExp & e)
338     {
339     }
340
341     void visit(ast::TransposeExp & e)
342     {
343     }
344
345     void visit(ast::MatrixExp & e)
346     {
347     }
348
349     void visit(ast::MatrixLineExp & e)
350     {
351     }
352
353     void visit(ast::CellExp & e)
354     {
355     }
356
357     void visit(ast::SeqExp & e)
358     {
359         if (loops.empty())
360         {
361             for (auto _e : e.getExps())
362             {
363                 if (_e->isForExp() || _e->isWhileExp())
364                 {
365                     _e->accept(*this);
366                 }
367             }
368         }
369         else
370         {
371             for (auto _e : e.getExps())
372             {
373                 _e->accept(*this);
374             }
375         }
376     }
377
378     void visit(ast::ArrayListExp & e)
379     {
380     }
381
382     void visit(ast::AssignListExp & e)
383     {
384     }
385
386     void visit(ast::VarDec & e)
387     {
388         emplace(assigned, e.getSymbol());
389     }
390
391     void visit(ast::FunctionDec & e)
392     {
393     }
394
395     void visit(ast::ListExp & e)
396     {
397     }
398
399     void visit(ast::OptimizedExp & e)
400     {
401     }
402
403     void visit(ast::MemfillExp & e)
404     {
405     }
406
407     void visit(ast::DAXPYExp & e)
408     {
409     }
410
411     void visit(ast::IntSelectExp & e)
412     {
413         visit(static_cast<ast::SelectExp &>(e));
414     }
415
416     void visit(ast::StringSelectExp & e)
417     {
418         visit(static_cast<ast::SelectExp &>(e));
419     }
420 };
421
422 } // namespace analysis
423
424 #endif // __LOOP_ANALYZER_HXX__
425