Analysis: infer when a refcount is required and add colors in DebugVisitor
[scilab.git] / scilab / modules / ast / src / cpp / analysis / Block.cpp
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 #include "AnalysisVisitor.hxx"
14 #include "data/Block.hxx"
15 #include "data/LoopBlock.hxx"
16 #include "data/XBlock.hxx"
17 #include "data/DataManager.hxx"
18
19 #include <algorithm>
20
21 namespace analysis
22 {
23
24 Block::Block(DataManager * _dm) : dm(_dm), parent(nullptr), exp(nullptr), gvn(&dm->getDefaultGVN()), isReturn(false), id(0) { }
25
26 Block::~Block()
27 {
28     std::for_each(blocks.begin(), blocks.end(), [](Block * b)
29     {
30         delete b;
31     });
32 }
33
34 void Block::addGlobal(const symbol::Symbol & sym)
35 {
36     dm->addGlobal(sym);
37 }
38
39 GVN & Block::getGVN()
40 {
41     return *gvn;
42 }
43
44 Info & Block::setDefaultData(const symbol::Symbol & sym)
45 {
46     Info & i = addSym(sym, new Data(false, sym));
47     i.local = Info::Local::INFO_FALSE;
48     i.type = DataManager::getSymInScilabContext(getGVN(), sym, i.exists);
49     addGlobal(sym);
50     dm->registerData(i.data);//, __LINE__, __FILE__);
51
52     return i;
53 }
54
55 void Block::clone(Info & info, const symbol::Symbol & sym, ast::Exp * exp)
56 {
57     if (info.data->valid && !info.data->hasOneOwner())
58     {
59         // data is shared between several symbols => we need to clone it
60         info.data->rem(sym);
61         info.data = new Data(info.isknown(), sym);
62         dm->registerData(info.data);//, __LINE__, __FILE__);
63         clone(sym, exp);
64     }
65 }
66
67 void Block::clone(const symbol::Symbol & sym, ast::Exp * exp)
68 {
69     if (parent)
70     {
71         parent->clone(sym, exp);
72     }
73     else
74     {
75         exp->getDecorator().addClone(sym);
76     }
77 }
78
79 Info & Block::putSymsInScope(const symbol::Symbol & sym, Block * block, Info & info)
80 {
81     // We put the sym (which is defined in block) in this block and pull all its companions too.
82     Info & i = addSym(sym, info);
83     Data * data = i.data;
84     // emplace called the Info's copy ctor so a new Data has been allocated
85     dm->registerData(data);//, __LINE__, __FILE__);
86     // We put all the shared syms in this scope
87     if (!data->hasOneOwner())
88     {
89         for (const auto & _sym : data->sharedSyms)
90         {
91             if (sym != _sym)
92             {
93                 Info & _i = block->symMap.find(_sym)->second;
94                 Data * old = _i.data;
95                 // we set _i.data to nullptr to avoid the data copy when cloning _i
96                 _i.data = nullptr;
97                 addSym(_sym, _i).data = data;
98                 _i.data = old;
99             }
100         }
101     }
102
103     return i;
104 }
105
106 Info & Block::putSymsInScope(const symbol::Symbol & sym)
107 {
108     tools::SymbolMap<Info>::iterator it;
109     Block * block = getDefBlock(sym, it, false);
110     if (!block)
111     {
112         Info & info = dm->root->setDefaultData(sym);
113         block = dm->root;
114         if (block != this)
115         {
116             return putSymsInScope(sym, block, info);
117         }
118         return info;
119     }
120
121     if (block != this)
122     {
123         return putSymsInScope(sym, block, it->second);
124     }
125
126     return it->second;
127 }
128
129 Block * Block::getDefBlock(const symbol::Symbol & sym, tools::SymbolMap<Info>::iterator & it, const bool global)
130 {
131     it = symMap.find(sym);
132     if (it != symMap.end())
133     {
134         return this;
135     }
136     else if (parent)
137     {
138         // search sym in the previous block
139         return parent->getDefBlock(sym, it, global);
140     }
141
142     return nullptr;
143 }
144
145 Info & Block::getInfo(const symbol::Symbol & sym)
146 {
147     tools::SymbolMap<Info>::iterator i = symMap.find(sym);
148     if (i != symMap.end())
149     {
150         // The sym has been already used in this block
151         return i->second;
152     }
153     else if (parent)
154     {
155         // search sym in the previous block
156         return parent->getInfo(sym);
157     }
158     else
159     {
160         // We are in the root block (parent == nullptr) and the sym doesn't exist here
161         // so we can presumed that it exists in the previous scope
162         return setDefaultData(sym);
163     }
164 }
165
166 Info & Block::addRead(const symbol::Symbol & sym, ast::Exp * exp)
167 {
168     /* READ:
169        - no type modification
170        - no refcount modification
171     */
172     Info & info = getInfo(sym);
173     info.R = true;
174
175     return info;
176 }
177
178 Info & Block::addWrite(const symbol::Symbol & sym, const TIType & Rtype, ast::Exp * exp)
179 {
180     /* WRITE:
181        - TODO: if x is scalar and x(2)=3 then x is a matrix !
182        - type can be modified: a=1:3; a(1)=%i or $; a is typed complex or polynomial
183        - if associated data is shared then we need to clone it
184     */
185     Info & info = putSymsInScope(sym);
186     if (info.exists)
187     {
188         if (info.type.type == TIType::Type::DOUBLE)
189         {
190             if (Rtype.type == TIType::Type::COMPLEX)
191             {
192                 info.type.type = TIType::Type::COMPLEX;
193             }
194             else if (Rtype.type == TIType::Type::POLYNOMIAL)
195             {
196                 info.type.type = TIType::Type::POLYNOMIAL;
197             }
198         }
199     }
200     else
201     {
202         info.type = Rtype;
203         info.exists = true;
204     }
205
206     clone(info, sym, exp);
207     info.W = true;
208
209     return info;
210 }
211
212 void Block::addLocal(const symbol::Symbol & sym, const TIType & type, const bool isAnInt)
213 {
214     if (parent)
215     {
216         parent->addLocal(sym, type, isAnInt);
217     }
218 }
219
220 int Block::getTmpId(const TIType & type, const bool isAnInt)
221 {
222     if (parent)
223     {
224         return parent->getTmpId(type, isAnInt);
225     }
226
227     return -1;
228 }
229
230 void Block::releaseTmp(const int id, ast::Exp * exp)
231 {
232     if (parent)
233     {
234         parent->releaseTmp(id, exp);
235     }
236 }
237
238 Info & Block::addDefine(const symbol::Symbol & sym, const TIType & Rtype, const bool isIntIterator, ast::Exp * exp)
239 {
240     /* DEFINE:
241        - if associated data is shared then we need to clone it
242     */
243     addLocal(sym, Rtype, isIntIterator);
244     Info & info = putAndClear(sym, exp);
245     info.cleared = false;
246     info.data = new Data(true, sym);
247     info.type = Rtype;
248     info.exists = true;
249     dm->registerData(info.data);//, __LINE__, __FILE__);
250
251     return info;
252 }
253
254 Info & Block::addShare(const symbol::Symbol & Lsym, const symbol::Symbol & Rsym, const TIType & Rtype, ast::Exp * exp)
255 {
256     addLocal(Lsym, Rtype, /* isIntIterator */ false);
257     Info & Linfo = putAndClear(Lsym, exp);
258     Info & Rinfo = putSymsInScope(Rsym);
259     Linfo.cleared = false;
260     Linfo.type = Rtype;
261     Linfo.data = Rinfo.data;
262     Linfo.isint = Rinfo.isint;
263     Linfo.data->add(Lsym);
264     Linfo.exists = true;
265
266     return Linfo;
267 }
268
269 Info & Block::addClear(const symbol::Symbol & sym, ast::Exp * exp)
270 {
271     return putAndClear(sym, exp);
272 }
273
274 Info & Block::addMacroDef(ast::FunctionDec * dec)
275 {
276     TIType ty(getGVN(), TIType::MACRO);
277     Info & i = addDefine(dec->getSymbol(), ty, false, dec);
278     i.exp = dec;
279
280     return i;
281 }
282
283 std::vector<TIType> Block::addCall(AnalysisVisitor & visitor, const unsigned int lhs, const symbol::Symbol & sym, std::vector<TIType> & in, ast::CallExp * callexp)
284 {
285     tools::SymbolMap<Info>::iterator it;
286     Block * block = getDefBlock(sym, it, false);
287     types::InternalType * pIT = nullptr;
288     std::vector<TIType> out(lhs, TIType(visitor.getGVN()));
289     TIType type;
290
291     if (block)
292     {
293         type = it->second.type;
294     }
295     else
296     {
297         type = DataManager::getSymInScilabContext(getGVN(), sym, pIT);
298     }
299
300     switch (type.type)
301     {
302         case TIType::FUNCTION:
303         {
304             if (lhs > 0)
305             {
306                 TIType ty = Checkers::check(getGVN(), sym.getName(), in);
307                 if (ty.type != TIType::UNKNOWN && ty.hasInvalidDims())
308                 {
309                     out[0] = ty.asUnknownMatrix();
310                 }
311                 else
312                 {
313                     out[0] = ty;
314                 }
315             }
316             break;
317         }
318         case TIType::MACRO:
319         {
320             if (pIT)
321             {
322                 visitor.getPMC().getOutTypes(visitor, dm->getMacroDef(static_cast<types::Macro *>(pIT)), in, out);
323             }
324             else
325             {
326                 if (it->second.exp && it->second.exp->isFunctionDec())
327                 {
328                     DeclaredMacroDef macrodef(static_cast<ast::FunctionDec *>(it->second.exp));
329                     visitor.getPMC().getOutTypes(visitor, &macrodef, in, out);
330                 }
331                 else
332                 {
333                     DataManager::getSymInScilabContext(getGVN(), sym, pIT);
334                     visitor.getPMC().getOutTypes(visitor, dm->getMacroDef(static_cast<types::Macro *>(pIT)), in, out);
335                 }
336             }
337             break;
338         }
339         case TIType::MACROFILE:
340         {
341             DataManager::getSymInScilabContext(getGVN(), sym, pIT);
342             visitor.getPMC().getOutTypes(visitor, dm->getMacroDef(static_cast<types::MacroFile *>(pIT)->getMacro()), in, out);
343             break;
344         }
345         default:
346         {
347         }
348     }
349
350     return out;
351 }
352
353 Info & Block::putAndClear(const symbol::Symbol & sym, ast::Exp * exp)
354 {
355     tools::SymbolMap<Info>::iterator it;
356     Block * block = getDefBlock(sym, it, false);
357     if (block)
358     {
359         Info & info = it->second;
360         if (block == this)
361         {
362             if (info.data->hasOneOwner())
363             {
364                 info.cleared = true;
365                 exp->getDecorator().deleteData = true;
366                 info.local = Info::Local::INFO_TRUE;
367                 return info;
368             }
369             else
370             {
371                 info.data->rem(sym);
372                 info.data = nullptr;
373                 info.cleared = true;
374                 info.local = Info::Local::INFO_TRUE;
375                 return info;
376             }
377         }
378         else
379         {
380             if (info.data->hasOneOwner())
381             {
382                 Data * old = info.data;
383                 info.data = nullptr;
384                 Info & i = addSym(sym, info);
385                 info.data = old;
386                 i.cleared = true;
387                 exp->getDecorator().deleteData = true;
388                 i.local = Info::Local::INFO_TRUE;
389                 return i;
390             }
391             else
392             {
393                 Info & i = putSymsInScope(sym, block, info);
394                 i.data->rem(sym);
395                 i.data = nullptr;
396                 i.cleared = true;
397                 i.local = Info::Local::INFO_TRUE;
398                 return i;
399             }
400         }
401     }
402     else
403     {
404         Info & i = addSym(sym, nullptr);
405         i.local = Info::Local::INFO_TRUE;
406
407         return i;
408     }
409 }
410
411 Block * Block::addBlock(const unsigned int id, BlockKind kind, ast::Exp * exp)
412 {
413     Block * b;
414     switch (kind)
415     {
416         case NORMAL:
417             b = new Block(id, this, exp);
418             break;
419         case LOOP:
420             b = new LoopBlockHead(id, this, exp);
421             break;
422         case EXCLUSIVE:
423             b = new XBlockHead(id, this, exp);
424             break;
425         case MACRO:
426             b = new FunctionBlock(id, this, exp);
427             break;
428     }
429     blocks.push_back(b);
430
431     return b;
432 }
433
434 void Block::finalize()
435 {
436     pullup(symMap);
437 }
438
439 bool Block::requiresAnotherTrip()
440 {
441     return false;
442 }
443
444 void Block::needRefCount(const tools::SymbolSet & set)
445 {
446     if (parent)
447     {
448         parent->needRefCount(set);
449     }
450 }
451
452 void Block::needRefCount(const tools::SymbolSet & set1, const tools::SymbolSet & set2)
453 {
454     tools::SymbolSet res;
455     for (const auto & sym : set1)
456     {
457         res.emplace(sym);
458     }
459     for (const auto & sym : set2)
460     {
461         res.emplace(sym);
462     }
463     needRefCount(res);
464 }
465
466 void Block::merge(tools::SymbolMap<Info> & M, tools::SymbolMap<Info> & N)
467 {
468     // TODO: when we merge double and double* we should mark the sym to convert the double into a double*
469     // and in the LLVM side, make a phi node to set the correct value !
470     for (auto & p : M)
471     {
472         bool isSameData;
473         tools::SymbolMap<Info>::iterator i = N.find(p.first);
474         if (i != N.end())
475         {
476             // sym is common to the two maps
477             p.second.merge(i->second, isSameData);
478             if (!isSameData)
479             {
480                 // the variable requires a reference counter
481                 needRefCount(p.second.data->sharedSyms, i->second.data->sharedSyms);
482             }
483
484             N.erase(i);
485         }
486         else
487         {
488             // sym is in M and not in N
489             const Info & i = getInfo(p.first);
490             p.second.merge(i, isSameData);
491             if (!isSameData)
492             {
493                 // the variable requires a reference counter
494                 needRefCount(p.second.data->sharedSyms, i.data->sharedSyms);
495             }
496         }
497     }
498
499     // We erased common syms in N, so the remainder is the syms which are in N and not in M
500     for (auto & p : N)
501     {
502         bool isSameData;
503         Info & i1 = Block::addSym(M, p.first, p.second);
504         Info & i2 = getInfo(p.first);
505         i1.merge(i2, isSameData);
506         if (!isSameData)
507         {
508             // the variable requires a reference counter
509             needRefCount(i1.data->sharedSyms, i2.data->sharedSyms);
510         }
511     }
512 }
513
514 void Block::pullup(tools::SymbolMap<Info> & M)
515 {
516     if (parent)
517     {
518         tools::SymbolMap<Info> & map = parent->symMap;
519         tools::SymbolMap<Info>::iterator end = map.end();
520         for (auto & p : M)
521         {
522             tools::SymbolMap<Info>::iterator i = map.find(p.first);
523             if (i != end)
524             {
525                 i->second = p.second;
526             }
527             else
528             {
529                 Block::addSym(map, p.first, p.second);
530             }
531         }
532     }
533 }
534
535 Info & Block::addSym(tools::SymbolMap<Info> & M, const symbol::Symbol & sym, Info & info)
536 {
537     Data * old = info.data;
538     info.data = nullptr;
539     Info & i = M.emplace(sym, info).first->second;
540     i.data = old;
541     info.data = old;
542
543     return i;
544 }
545
546 std::wostream & operator<<(std::wostream & out, const Block & block)
547 {
548     const unsigned int n = block.blocks.size();
549     out << L"Table " << block.id;
550     if (block.exp)
551     {
552         out << L" at " << block.exp->getLocation();
553     }
554     out << L" (" << n << ((n >= 2) ? L" children):" : L" child):") << std::endl;
555
556     for (const auto & p : block.symMap)
557     {
558         out << L" -" << p.first << L"  " << p.second << std::endl;
559     }
560     //#ifdef DEBUG_DATAMANAGER
561     //for (const auto b : block.blocks)
562     //{
563
564     //}
565     std::for_each(block.blocks.begin(), block.blocks.end(), [&](Block * b)
566     {
567         out << *b << std::endl;
568     });
569     //#endif
570
571     return out;
572 }
573
574 } // namespace analysis