Line data    Source code

       1             : #include "optimizer/controlflow.hpp"
       2             : #include "common/tables.hpp"
       3             : #include "common/obstacle.hpp"
       4             : #include "optimizer/util.hpp"
       5             : #include <iterator>
       6             : #include <iostream>
       7             : 
       8             : std::vector<int> flowTree::checked {0};
       9             : 
      10        6685 : flowTree* flowTree::getFT(int id, bool head) {
      11        6685 :     if (ID == id) return this;
      12             :     
      13        6489 :     if ((ID < id) && (id < ID + block.getSize()))
      14          17 :         return split(id);
      15             : 
      16        6472 :     flowTree * ret = nullptr;
      17        6472 :     checked.emplace(checked.end(), ID);
      18             : 
      19       11976 :     for (auto node: next) {
      20        5543 :         if (find(checked, node.first->ID) == -1) {
      21        1515 :             ret = node.first->getFT(id, false);
      22             :         }
      23        5543 :         if (ret != nullptr) break;
      24             :     }
      25             : 
      26        6472 :     if (ret == nullptr)
      27       11906 :         for (auto node: prev) {
      28        5535 :             if (find(checked, node.first->ID) == -1) {
      29        3563 :                 ret = node.first->getFT(id, false);
      30             :             }
      31        5535 :             if (ret != nullptr) break;
      32             :         }
      33             :     
      34        6472 :     if (head) checked.clear();
      35        6472 :     return ret;
      36             : }
      37             : 
      38          17 : flowTree* flowTree::split(int id) {
      39             :     #ifdef DEBUG
      40             :     std::cout << "split " << ID << " | " << id << "\n";
      41             :     #endif
      42             : 
      43          17 :     flowTree * fb = new flowTree(id);
      44          17 :     fb->splitted = true;
      45             : 
      46          17 :     copyPOLIZ(block, fb->block, id - ID, block.getSize());
      47             : 
      48          78 :     for (int i = block.getSize(); i > id - ID; i--)
      49          61 :         block.pop();
      50             : 
      51          34 :     for (auto p: next) {
      52          17 :         fb->next.push_back(p);
      53             :         int idx;
      54          34 :         while ((idx = find(p.first->prev, this)) != -1) {
      55          17 :             p.first->prev[idx].first = fb;
      56             :         }
      57             :     }
      58             : 
      59          17 :     next.clear();
      60          17 :     next.push_back(std::make_pair(fb, 0));
      61          17 :     fb->prev.push_back(std::make_pair(this, 0));
      62             : 
      63          17 :     return fb;
      64             : }
      65             : 
      66         182 : void ControlFlowGraph::newBlock(int blockId, POLIZ * p, flowTree * curBlock, char cond) {
      67             :     #ifdef DEBUG
      68             :     std::cout << "newBlock " << blockId << "\n";
      69             :     #endif
      70         182 :     bool exists = true;
      71         182 :     flowTree * fb = curBlock->getFT(blockId);
      72         182 :     if (fb == nullptr) {
      73         150 :         fb = new flowTree(blockId);
      74         150 :         exists = false;
      75         150 :         blocksNum++;
      76             :     }
      77         182 :     if (fb->splitted) {
      78          17 :         fb->splitted = false;
      79          17 :         jumpsNum++;
      80          17 :         blocksNum++;
      81             :     }
      82         182 :     fb->prev.push_back(std::make_pair(curBlock, cond));
      83         182 :     curBlock->next.push_back(std::make_pair(fb, cond));
      84         182 :     jumpsNum++;
      85         182 :     makeBranch(p, curBlock, fb, exists);
      86         182 : }
      87             : 
      88             : #ifdef CFG_STEPBYSTEP
      89             : int drawIterator = 0;
      90             : #endif
      91             : 
      92         211 : void ControlFlowGraph::makeBranch(POLIZ * p, flowTree * curBlock, flowTree * fb, bool exists) {
      93             :     #ifdef CFG_STEPBYSTEP
      94             :     draw(std::to_string(drawIterator++));
      95             :     #endif
      96             : 
      97         211 :     if (fb != nullptr) {
      98             :         #ifdef DEBUG
      99             :         std::cout << "makeBranch " << curBlock->ID << " (";
     100             :         std::cout << curBlock << ") -> " << fb->ID << " (";
     101             :         std::cout << fb << ")\n";
     102             :         #endif
     103         182 :         if (exists) return;
     104         150 :         curBlock = fb;
     105             :     }
     106             : 
     107         179 :     int eip = curBlock->ID;
     108             :     void* blockId;
     109        1454 :     while(eip < p->getSize()) {
     110        1425 :         flowTree * existingPart = curBlock->getFT(eip);
     111             : 
     112        1425 :         if ((eip != curBlock->ID) && (existingPart != nullptr)) {
     113           2 :             newBlock(eip, p, curBlock);
     114           2 :             break;
     115             :         }
     116             :  
     117        1423 :         op_t op = p->getProg()[eip];
     118        1423 :         if (p->getEB()[eip]) {
     119         714 :             if ((op & 0xFF) == JMP) {
     120          84 :                 curBlock->block.pop(); // удалить LABEL
     121          84 :                 blockId = IT_FROM_POLIZ((*p), eip - 1)->getVal();
     122          84 :                 newBlock(*static_cast<int*>(blockId), p, curBlock);
     123          84 :                 break;
     124             :             }
     125             : 
     126         630 :             if ((op & 0xFF) == JIT) {
     127          29 :                 curBlock->block.pop(); // удалить LABEL
     128          29 :                 int bsize = curBlock->block.getSize();
     129          29 :                 blockId = IT_FROM_POLIZ((*p), eip - 1)->getVal();
     130          29 :                 newBlock(*static_cast<int*>(blockId), p, curBlock, 1); // Блок True
     131          29 :                 if (curBlock->block.getSize() != bsize)
     132          10 :                     curBlock = curBlock->next[0].first;
     133          29 :                 newBlock(eip + 1, p, curBlock, 2);        // Блок False
     134          29 :                 break;
     135             :             }
     136             : 
     137         601 :             if (((op & 0xFF) == CALL) || ((op & 0xFF) == FORK)) {
     138          19 :                 curBlock->block.pop(); // удалить LABEL
     139          19 :                 curBlock->block.push(op, true);
     140          19 :                 blockId = IT_FROM_POLIZ((*p), eip - 1)->getVal();
     141          19 :                 newBlock(*static_cast<int*>(blockId), p, curBlock, 1);
     142          19 :                 newBlock(eip + 1, p, curBlock, 2);
     143          19 :                 break;
     144             :             }
     145             : 
     146         582 :             if ((op & 0xFF) == RET) {
     147          16 :                 curBlock->block.push(op, true);
     148          16 :                 break;
     149             :             }
     150             :         }
     151        1275 :         curBlock->block.push(op, p->getEB()[eip]);
     152        1275 :         eip++;
     153             :     }
     154             : }
     155             : 
     156          29 : void ControlFlowGraph::make(POLIZ * p) {
     157          29 :     makeBranch(p, &ft, nullptr, false);
     158          29 :     blocksNum++;
     159          29 :     ft.checked.clear();
     160          29 :     findTails(&ft);
     161          29 : }
     162             : 
     163         196 : void ControlFlowGraph::findTails(flowTree * ft) {
     164         196 :     int s = ft->block.getSize();
     165         196 :     if (s > 0) {
     166         149 :         operation_t op = (operation_t) (ft->block.getProg()[s-1] & 0xFF);
     167         149 :         if ((op == STOP) || (op == RET)) {
     168          49 :             for (auto node: ft->next) {
     169           2 :                 auto vec = node.first->prev;
     170           2 :                 int idx = find(vec, ft);
     171           2 :                 if (idx == -1) throw Obstacle(PANIC);
     172           2 :                 vec.erase(vec.begin() + idx);
     173             :             }
     174          47 :             ft->next.clear();
     175             :         }
     176         149 :         if (op == STOP) {
     177          31 :             tails.insert(tails.begin(), ft);
     178          31 :             return;
     179             :         }
     180         118 :         if (op == RET) {
     181          16 :             funcsNum++;
     182          16 :             tails.insert(tails.end(), ft);
     183          16 :             return;
     184             :         }
     185             :     }
     186         346 :     for (auto node: ft->next) {
     187         197 :         if (find(ft->checked, node.first->ID) == -1) {
     188         167 :             ft->checked.push_back(node.first->ID);
     189         167 :             findTails(node.first);
     190             :         }
     191             :     }
     192             : }
     193             : 
     194           0 : void ControlFlowGraph::info(void) const {
     195           0 :     std::cout << "Граф потока управления построен. Статистика:\n";
     196           0 :     std::cout << "\tВсего блоков: " << blocksNum << "\n";
     197           0 :     std::cout << "\tВсего переходов: " << jumpsNum << "\n";
     198           0 :     std::cout << "\tВсего функций: " << funcsNum << "\n";
     199           0 : }
     200             : 
     201             : #ifdef DRAW_GRAPH
     202             : 
     203             : void ControlFlowGraph::draw(const std::string & filename) {
     204             :     graph.open(filename + ".dot");
     205             : 
     206             :     graph << "digraph CFG {\n";
     207             : 
     208             :     std::streambuf *coutbuf = std::cout.rdbuf();
     209             :     std::cout.rdbuf(graph.rdbuf());
     210             :     
     211             :     drawNode(ft);
     212             :     drawed.clear();
     213             :     drawEdge(ft);
     214             :     drawed.clear();
     215             :     
     216             :     std::cout.rdbuf(coutbuf);
     217             : 
     218             :     graph << "}\n";
     219             :     graph.close();
     220             : 
     221             :     std::system(("dot -v -Tsvg -o./" + filename + ".svg ./" +
     222             :                 filename + ".dot 2>&1 | grep -i error").data() );
     223             : }
     224             : 
     225             : void ControlFlowGraph::drawNode(flowTree p) {
     226             :     graph << "\tNODE" << p.ID << "  [shape=record, label=\"{";
     227             :     graph << "BlockID: " << p.ID << " | ";
     228             :     p.block.repr(true);
     229             :     graph << "}\"];\n";
     230             :     drawed.emplace(drawed.end(), p.ID);
     231             :     if (!p.next.empty()) {
     232             :         for (auto node: p.next) {
     233             :             if (find(drawed, node.first->ID) == -1)
     234             :                 drawNode(* node.first);
     235             :         }
     236             :     }
     237             : }
     238             : 
     239             : void ControlFlowGraph::drawEdge(flowTree & p) {
     240             :     if (find(drawed, p.ID) != -1)
     241             :         return;
     242             :     
     243             :     drawed.push_back(p.ID);
     244             : 
     245             :     for (auto node: p.next) {
     246             :         graph << "\tNODE" << p.ID << " -> NODE" << node.first->ID;
     247             : 
     248             :         if (node.second == 1)
     249             :             graph << " [label=\"True\"]";
     250             :         else if (node.second == 2)
     251             :             graph << " [label=\"False\"]";
     252             : 
     253             :         graph << ";\n";
     254             : 
     255             :         drawEdge(* node.first);
     256             :     }
     257             : }
     258             : 
     259             : #endif
     260             : 
     261         197 : void ControlFlowGraph::newConn(POLIZ* poliz, flowTree * curBlock, 
     262             :                                    std::vector<int> * ls, std::vector<flowTree *> * eb) {
     263         197 :     if (find(*eb, curBlock) == -1) {
     264             :         // Вписываем сюда
     265         167 :         insertBlock(poliz, curBlock, ls, eb);
     266             :     } else {
     267             :         // Прыжок назад
     268          30 :         ls->push_back(poliz->getSize());
     269          30 :         poliz->push((op_t) curBlock, false);
     270          30 :         poliz->pushOp(_NONE_, _LABEL_, JMP);
     271             :     }
     272         197 : }
     273             : 
     274         196 : void ControlFlowGraph::insertBlock(POLIZ* poliz, flowTree * curBlock, 
     275             :                                    std::vector<int> * ls, std::vector<flowTree *> * eb) {
     276         196 :     int bsize = curBlock->block.getSize();
     277         196 :     curBlock->ID = poliz->getSize();
     278         196 :     eb->push_back(curBlock);
     279         196 :     copyPOLIZ(curBlock->block, *poliz, 0, bsize);
     280             : 
     281         196 :     if (curBlock->next.size() == 1) {
     282         101 :         newConn(poliz, curBlock->next[0].first, ls, eb);
     283          95 :     } else if (curBlock->next.size() == 2) {
     284          48 :         flowTree * falseb = curBlock->next[find(curBlock->next, (char)2)].first;
     285          48 :         flowTree * trueb  = curBlock->next[find(curBlock->next, (char)1)].first;
     286             : 
     287          48 :         op_t lastop = curBlock->block.getProg()[bsize - 1];
     288          48 :         if (((lastop & 0xFF) == CALL) || ((lastop & 0xFF) == FORK))
     289          19 :             poliz->pop();
     290          48 :         ls->push_back(poliz->getSize());
     291          48 :         poliz->push((op_t) trueb, false);
     292          48 :         if (((lastop & 0xFF) == CALL) || ((lastop & 0xFF) == FORK))
     293          19 :             poliz->push(lastop, true);
     294             :         else
     295          29 :             poliz->pushOp(_BOOLEAN_, _LABEL_, JIT);
     296          48 :         newConn(poliz, falseb, ls, eb);
     297          48 :         newConn(poliz, trueb, ls, eb);
     298          47 :     } else if (curBlock->next.size() > 2) throw Obstacle(PANIC);
     299         196 : }
     300             : 
     301          29 : IdentTable * ControlFlowGraph::decompose(IdentTable* IT, POLIZ* poliz) {
     302          29 :     IT = IT->deleteLabels();
     303          29 :     poliz->clear();
     304          58 :     std::vector<int> labelStorage;
     305          29 :     std::vector<flowTree*> existingBlocks;
     306          29 :     insertBlock(poliz, &ft, &labelStorage, &existingBlocks);
     307         107 :     for (auto lpos: labelStorage) {
     308          78 :         flowTree * block = reinterpret_cast<flowTree *>(poliz->getProg()[lpos]);
     309          78 :         IT->pushVal(new int (block->ID));
     310          78 :         IT->pushType(_LABEL_);
     311          78 :         poliz->getProg()[lpos] = (op_t) IT->confirm();
     312             :     }
     313          58 :     return IT;
     314             : }
     315             : 
     316         196 : void ControlFlowGraph::deleteBranch(std::vector<std::pair<flowTree *, char>> vec, std::vector<flowTree*> * del) {
     317         393 :     for (auto node: vec) {
     318         197 :         if (find(*del, node.first) == -1) {
     319         167 :             del->push_back(node.first);
     320         167 :             deleteBranch(node.first->next, del);
     321         167 :             delete node.first;
     322             :         }
     323             :     }
     324         196 : }
     325             : 
     326          29 : void ControlFlowGraph::clear(void) {
     327          29 :     std::vector<flowTree*> deleted;
     328             : 
     329          29 :     deleteBranch(ft.next, &deleted);
     330          29 :     ft.next.clear();
     331          29 :     ft.prev.clear();
     332          29 :     drawed.clear();
     333          29 :     blocksNum = 0;
     334          29 :     jumpsNum = 0;
     335          29 : }
     336             : 
     337          58 : flowTree * ControlFlowGraph::head(void) {
     338          58 :     return &ft;
     339             : }
     340             : 
     341          29 : ControlFlowGraph::~ControlFlowGraph() {
     342          29 :     clear();
     343          29 : }