Line data    Source code

       1             : #include "optimizer/acyclicgraph.hpp"
       2             : #include "common/exprtype.hpp"
       3             : #include "optimizer/util.hpp"
       4             : #include <iostream>
       5             : 
       6             : std::vector<DAGRow *> DAGRow::created;
       7             : 
       8           0 : bool DAGRow::isLast(void) const {
       9           0 :     return (lvar == nullptr) && (rvar == nullptr);
      10             : }
      11             : 
      12             : /*
      13             : DAGRow & DAGRow::operator=(const DAGRow & dr) {
      14             :     if (this == &dr) return *this;
      15             : 
      16             :     ident = dr.ident;
      17             :     opcode = dr.opcode;
      18             :     prev = dr.prev;
      19             :     
      20             :     if (dr.lvar != nullptr) {
      21             :         lvar = new DAGRow;
      22             :         *lvar = *dr.lvar;
      23             :     } else lvar = nullptr;
      24             : 
      25             :     if (dr.rvar != nullptr) {
      26             :         rvar = new DAGRow;
      27             :         *rvar = *dr.rvar;
      28             :     } else rvar = nullptr;
      29             : 
      30             :     assigned = dr.assigned;
      31             : 
      32             :     return *this;
      33             : }
      34             : 
      35             : DAGRow::DAGRow(const DAGRow & dr) {
      36             :     ident = dr.ident;
      37             :     opcode = dr.opcode;
      38             :     prev = dr.prev;
      39             :     
      40             :     if (dr.lvar != nullptr) {
      41             :         lvar = new DAGRow;
      42             :         *lvar = *dr.lvar;
      43             :     } else lvar = nullptr;
      44             : 
      45             :     if (dr.rvar != nullptr) {
      46             :         rvar = new DAGRow;
      47             :         *rvar = *dr.rvar;
      48             :     } else rvar = nullptr;
      49             : 
      50             :     assigned = dr.assigned;
      51             : }
      52             : */
      53             : 
      54           0 : bool operator==(DAGRow & a, DAGRow & b) {
      55           0 :     if (&a == &b) return false;
      56             : 
      57           0 :     bool ret = (a.opcode == b.opcode);
      58             : 
      59           0 :     if (a.lvar != b.lvar) {
      60           0 :         if ((a.lvar == nullptr) || (b.lvar == nullptr))
      61           0 :             return false;
      62           0 :         ret = ret && (*a.lvar == *b.lvar);
      63             :     }
      64             : 
      65           0 :     if (a.rvar != b.rvar) {
      66           0 :         if ((a.rvar == nullptr) || (b.rvar == nullptr))
      67           0 :             return false;
      68           0 :         ret = ret && (*a.rvar == *b.rvar);
      69             :     }
      70             : 
      71           0 :     if (a.isLast() && b.isLast())
      72           0 :         return ret && (*a.ident == *b.ident);
      73             : 
      74           0 :     if ((!a.isLast()) && (!b.isLast()))
      75           0 :         return ret;
      76             : 
      77           0 :     return false;
      78             : }
      79             : 
      80          58 : void DirectedAcyclicGraph::stash(POLIZ & p) {
      81          58 :     int s = p.getSize();
      82             : 
      83          58 :     if (s == 0) return;
      84           0 :     if (!p.getEB()[s - 1])
      85           0 :         return;
      86           0 :     if ((operation_t)(p.getProg()[s - 1] & 0xFF) != CALL)
      87           0 :         return;
      88             :     
      89           0 :     IdentTable * paramit = IT_FROM_POLIZ(p, s - 2);
      90           0 :     int paramNum = * static_cast<int *>(paramit->getVal());
      91           0 :     stashed.clear();
      92           0 :     copyPOLIZ(p, stashed, s - paramNum - 2, s);
      93           0 :     for (int i = 0; i < paramNum + 2; i++)
      94           0 :         p.pop();
      95             : }
      96             : 
      97          58 : void DirectedAcyclicGraph::make(POLIZ p) {
      98         116 :     std::vector<std::pair<IdentTable *, DAGRow *>> changed;
      99          58 :     std::pair<IdentTable *, DAGRow *> rep;
     100         116 :     std::vector<DAGRow *> queue;
     101          58 :     stash(p);
     102          58 :     for (int i = 0; i < p.getSize(); i++) {
     103             :         DAGRow * qrow;
     104           0 :         if (p.getEB()[i]) {
     105           0 :             qrow = new DAGRow;
     106           0 :             operation_t op = (operation_t)(p.getProg()[i] & 0xFF);
     107           0 :             type_t rettype = (type_t) ((p.getProg()[i] >> 24) & 0xFF);
     108           0 :             qrow->type = rettype;
     109           0 :             int opnum = operands(op);
     110           0 :             if ((opnum != 0) && (queue.size() != 0)) {
     111           0 :                 qrow->rvar = queue.back();
     112           0 :                 queue.pop_back();
     113           0 :                 if (qrow->rvar->prev == nullptr)
     114           0 :                     qrow->rvar->prev = qrow;
     115           0 :                 opnum--;
     116             :             }
     117           0 :             if ((opnum != 0) && (queue.size() != 0)) {
     118           0 :                 qrow->lvar = queue.back();
     119           0 :                 queue.pop_back();
     120           0 :                 if (qrow->lvar->prev == nullptr)
     121           0 :                     qrow->lvar->prev = qrow;
     122             :                 //opnum--;
     123             :             }
     124           0 :             qrow->opcode = p.getProg()[i];
     125           0 :             queue.push_back(qrow);
     126             : 
     127           0 :             if ((op == ASSIGN) && (qrow->lvar != nullptr) && (qrow->rvar != nullptr)) {
     128           0 :                 if (qrow->rvar->ident == nullptr)
     129           0 :                     qrow->rvar->ident = qrow->lvar->ident;
     130           0 :                 rep = std::make_pair(qrow->lvar->ident, qrow->rvar);
     131           0 :                 changed.emplace(changed.begin(), rep); 
     132             :             }
     133             :             
     134             :         } else {
     135           0 :             int idx = find(changed, IT_FROM_POLIZ(p, i));
     136           0 :             if (idx != -1) {
     137           0 :                 qrow = changed[idx].second;
     138             :             } else {
     139           0 :                 qrow = new DAGRow;
     140           0 :                 qrow->ident = IT_FROM_POLIZ(p, i);
     141             :             }
     142           0 :             queue.push_back(qrow);
     143             :         }
     144             :     }
     145             : 
     146          58 :     for (auto it = queue.begin(); it != queue.end(); it++)
     147           0 :         rows.push_back(*it);
     148          58 : }
     149             : 
     150           0 : void DAGRow::decompose(POLIZ & p, std::vector<DAGRow *> * asd) {
     151           0 :     if ((ident == nullptr) || (!assigned)) {
     152           0 :         if (lvar != nullptr)
     153           0 :             lvar->decompose(p, asd);
     154           0 :         if (rvar != nullptr)
     155           0 :             rvar->decompose(p, asd);
     156           0 :         if (ident != nullptr) {
     157           0 :             asd->push_back(this);
     158           0 :             assigned = true;
     159             :         }
     160             : 
     161           0 :         bool execBit = (opcode != (op_t) NONE);
     162           0 :         type_t ltype = (lvar == NULL)
     163           0 :                                     ? _NONE_
     164           0 :                                     : lvar->type;
     165           0 :         type_t rtype = (rvar == NULL)
     166           0 :                                     ? _NONE_
     167           0 :                                     : rvar->type;
     168             : 
     169           0 :         op_t newOp = (char) type << 24 | (char) ltype << 16;
     170           0 :         newOp |= (char) rtype << 8 | (char) (opcode & 0xFF);
     171           0 :         op_t op = (execBit)
     172           0 :                         ? newOp
     173           0 :                         : (op_t) ident;
     174           0 :         p.push(op, execBit);
     175           0 :     } else p.push((op_t)ident, false);
     176           0 : }
     177             : 
     178           0 : type_t DAGRow::updateType(std::vector<type_t> * typeOnStack) {
     179             :     type_t ltype, rtype;
     180             :     
     181           0 :     switch ((operation_t) (opcode & 0xFF)) {
     182           0 :         case LOAD:
     183           0 :             if ((!typeOnStack->empty()))
     184           0 :                 typeOnStack->pop_back();
     185           0 :             return type;
     186           0 :         default:
     187           0 :             break;
     188             :     }
     189             : 
     190           0 :     if ((lvar != nullptr)) {
     191           0 :         ltype = lvar->updateType(typeOnStack);
     192           0 :     } else ltype = _NONE_;
     193             :     
     194           0 :     if ((rvar != nullptr)) {
     195           0 :         rtype = rvar->updateType(typeOnStack);
     196           0 :     } else rtype = _NONE_;
     197             : 
     198           0 :     if (opcode != (op_t) NONE) {
     199           0 :         operation_t oper = (operation_t) (opcode & 0xFF);
     200             :         try {
     201           0 :             type = expressionType(ltype, rtype, oper);
     202           0 :         } catch (...) {
     203           0 :             if ((ltype == _NONE_) && (!typeOnStack->empty())) {
     204           0 :                 ltype = typeOnStack->back();
     205           0 :                 typeOnStack->pop_back();
     206             :             }
     207           0 :             if ((rtype == _NONE_) && (!typeOnStack->empty())) {
     208           0 :                 rtype = typeOnStack->back();
     209           0 :                 typeOnStack->pop_back();
     210             :             }
     211           0 :             type = expressionType(ltype, rtype, oper);
     212             :         }
     213             :         
     214             :     } else {
     215           0 :         if (ident != nullptr){
     216           0 :             type = ident->getType();
     217             :         } else
     218           0 :             type = _NONE_;
     219             :     }
     220           0 :     return type;
     221             : }
     222             : 
     223          58 : POLIZ DirectedAcyclicGraph::decompose(std::vector<type_t> * typeOnStack) {
     224          58 :     POLIZ ret;
     225         116 :     std::vector<DAGRow *> asd;
     226             :     type_t t;
     227             : 
     228          58 :     for (auto head: rows) {
     229           0 :         t = head->updateType(typeOnStack);
     230           0 :         if (t != _NONE_) typeOnStack->push_back(t);
     231           0 :         head->decompose(ret, &asd);
     232             :         #ifdef DEBUG
     233             :         //ret.repr();
     234             :         //ret.clear();
     235             :         //std::cout << "\n";
     236             :         #endif
     237             :     }
     238             : 
     239          58 :     for (auto x: asd) {
     240           0 :         x->assigned = false;
     241             :     }
     242             : 
     243          58 :     copyPOLIZ(stashed, ret, 0, stashed.getSize());
     244             :     
     245         116 :     return ret;
     246             : }
     247             : 
     248          58 : void DirectedAcyclicGraph::commonSubExpr(IdentTable * IT) {
     249          58 :     std::pair<std::pair<DAGRow *, DAGRow *>, int> fcret;
     250          58 :     std::pair<DAGRow *, DAGRow *> rowc;
     251             : 
     252          58 :     for (int i = 0; i < (signed int)rows.size(); i++) {
     253           0 :         for (int j = i; j < (signed int)rows.size(); j++) {
     254           0 :             fcret = findCopies(rows[i], rows[j], i, j);
     255           0 :             rowc = fcret.first;
     256           0 :             int left = fcret.second;
     257             :             
     258           0 :             if (rowc.first == nullptr)
     259           0 :                 continue;
     260             : 
     261           0 :             if ((!isExpr((operation_t)(rowc.first->opcode & 0xFF))) ||
     262           0 :                 (!isExpr((operation_t)(rowc.first->prev->opcode & 0xFF))))
     263           0 :                 continue;
     264             :             
     265           0 :             rowc.second->assigned = true;
     266             :                 
     267           0 :             if ((operation_t)(rowc.first->prev->opcode & 0xFF) == ASSIGN) {
     268           0 :                 if (rowc.second->prev->lvar == rowc.second)
     269           0 :                     rowc.second->prev->lvar = rowc.first;
     270             :                 else
     271           0 :                     rowc.second->prev->rvar = rowc.first;
     272             :                 
     273           0 :                 if (verbose) {
     274           0 :                     std::cout << "Исключено подвыражение, значение было вычислено в ";
     275           0 :                     rowc.first->prev->lvar->ident->whoami();
     276           0 :                     std::cout << std::endl;
     277             :                 }
     278           0 :                 continue;
     279             :             }
     280             :             
     281           0 :             type_t tt = (type_t) ((rowc.first->opcode >> 24) & 0xFF);
     282           0 :             DAGRow * temprow = new DAGRow;
     283           0 :             temprow->opcode = (char) tt << 16 | (char) tt << 8 | (char) tt;
     284           0 :             temprow->opcode = temprow->opcode << 8  | (char) ASSIGN;
     285           0 :             temprow->rvar = rowc.first;
     286           0 :             temprow->lvar = new DAGRow;
     287             : 
     288           0 :             temprow->lvar->ident = IT->last();
     289           0 :             temprow->rvar->ident = IT->last();
     290           0 :             temprow->lvar->ident->setType(tt);
     291           0 :             temprow->lvar->ident->setOrd(IT->last()->getOrd() + 1);
     292           0 :             IT->last()->next = new IdentTable;
     293             : 
     294           0 :             rows.insert(rows.begin() + left, temprow);
     295           0 :             if (left == i) i++;
     296           0 :             j++;
     297             : 
     298           0 :             if (rowc.first->prev->lvar == rowc.first)
     299           0 :                 rowc.first->prev->lvar = temprow->rvar;
     300             :             else
     301           0 :                 rowc.first->prev->rvar = temprow->rvar;
     302             : 
     303           0 :             if (rowc.second->prev->lvar == rowc.second)
     304           0 :                 rowc.second->prev->lvar = temprow->rvar;
     305             :             else
     306           0 :                 rowc.second->prev->rvar = temprow->rvar;
     307             : 
     308           0 :             if (verbose) {
     309           0 :                 std::cout << "Исключено подвыражение для двух выражений.\n";
     310             :             }
     311             : 
     312             :             #ifdef DEBUG
     313             :             std::cout << "Итерация i = " << i << " j = " << j << ":\n";
     314             :             std::vector<type_t> typeOnStack;
     315             :             decompose(&typeOnStack).repr(false);
     316             :             #endif
     317             :         }
     318             :     }
     319          58 : }
     320             : 
     321             : // Это очень нагруженная функция! Как сделать лучше?
     322             : std::pair<std::pair<DAGRow *, DAGRow *>, int> 
     323           0 : DirectedAcyclicGraph::findCopies(DAGRow * left, DAGRow * right, int a, int b) {
     324             : 
     325           0 :     if ((left == nullptr) && (right != nullptr))
     326           0 :         return findCopies(right->lvar, right->rvar, b, b);
     327             :     
     328           0 :     if ((left != nullptr) && (right == nullptr))
     329           0 :         return findCopies(left->lvar, left->rvar, a, a);
     330             :     
     331           0 :     if ((left == nullptr) || (right == nullptr))
     332           0 :         return std::make_pair(std::make_pair(nullptr, nullptr), 0);
     333             : 
     334           0 :     if ((*left == *right) && (left->prev != nullptr) &&
     335           0 :         (!left->isLast()) && (!right->isLast())) {
     336             :         #ifdef DEBUG
     337             :         POLIZ temp;
     338             :         std::vector<DAGRow *> asd;
     339             :         left->decompose(temp, &asd);
     340             :         for (auto x: asd) x->assigned = false;
     341             :         std::cout << "Новая копия:\n";
     342             :         temp.repr(false);
     343             :         std::cout << "\n";
     344             :         #endif
     345           0 :         return std::make_pair(std::make_pair(left, right), a);
     346             :     }
     347             :         
     348           0 :     std::pair<std::pair<DAGRow *, DAGRow *>, int> ret;
     349           0 :     ret = findCopies(left->lvar, right, a, b);
     350           0 :     if (ret.first.first != nullptr) return ret;
     351           0 :     ret = findCopies(left->rvar, right, a, b);
     352           0 :     if (ret.first.first != nullptr) return ret;
     353           0 :     ret = findCopies(left, right->lvar, a, b);
     354           0 :     if (ret.first.first != nullptr) return ret;
     355           0 :     ret = findCopies(left, right->rvar, a, b);
     356           0 :     if (ret.first.first != nullptr) return ret;
     357             : 
     358           0 :     return std::make_pair(std::make_pair(nullptr, nullptr), 0);
     359             : }
     360             : 
     361          58 : DirectedAcyclicGraph::~DirectedAcyclicGraph() {
     362          58 :     for (DAGRow * node: DAGRow::created)
     363           0 :         delete node;
     364          58 :     DAGRow::created.clear();
     365          58 : }