aseba: aseba: tree-optimize.cpp Source File

00001 /*
00002         Aseba - an event-based framework for distributed robot control
00003         Copyright (C) 2007--2012:
00004                 Stephane Magnenat <stephane at magnenat dot net>
00005                 (http://stephane.magnenat.net)
00006                 and other contributors, see authors.txt for details
00007         
00008         This program is free software: you can redistribute it and/or modify
00009         it under the terms of the GNU Lesser General Public License as published
00010         by the Free Software Foundation, version 3 of the License.
00011         
00012         This program is distributed in the hope that it will be useful,
00013         but WITHOUT ANY WARRANTY; without even the implied warranty of
00014         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015         GNU Lesser General Public License for more details.
00016         
00017         You should have received a copy of the GNU Lesser General Public License
00018         along with this program. If not, see <http://www.gnu.org/licenses/>.
00019 */
00020 
00021 #include "tree.h"
00022 #include "power-of-two.h"
00023 #include "../utils/FormatableString.h"
00024 #include "../utils/utils.h"
00025 #include <cassert>
00026 #include <cstdlib>
00027 
00028 
00029 namespace Aseba
00030 {
00033         
00034         Node* BlockNode::optimize(std::wostream* dump)
00035         {
00036                 for (NodesVector::iterator it = children.begin(); it != children.end();)
00037                 {
00038                         // generic optimization and removal
00039                         Node *optimizedChild = (*it)->optimize(dump);
00040                         if (!optimizedChild)
00041                         {
00042                                 it = children.erase(it);
00043                                 continue;
00044                         }
00045                         else
00046                                 *it = optimizedChild;
00047                         
00048                         // special case for empty blocks
00049                         if (dynamic_cast<BlockNode *>(*it) && (*it)->children.empty())
00050                         {
00051                                 delete *it;
00052                                 it = children.erase(it);
00053                                 continue;
00054                         }
00055                         
00056                         ++it;
00057                 }
00058                 
00059                 return this;
00060         }
00061         
00062         Node* AssignmentNode::optimize(std::wostream* dump)
00063         {
00064                 children[0] = children[0]->optimize(dump);
00065                 assert(children[0]);
00066                 children[1] = children[1]->optimize(dump);
00067                 assert(children[1]);
00068                 return this;
00069         }
00070         
00071         Node* IfWhenNode::optimize(std::wostream* dump)
00072         {
00073                 children[0] = children[0]->optimize(dump);
00074                 assert(children[0]);
00075                 
00076                 // optimise true block, which may be NULL afterwards
00077                 children[1] = children[1]->optimize(dump);
00078                 Node *trueBlock = children[1];
00079                 
00080                 // optimise false block, which may be NULL afterwards
00081                 Node *falseBlock;
00082                 if (children.size() > 2)
00083                 {
00084                         children[2] = children[2]->optimize(dump);
00085                         falseBlock = children[2];
00086                         if (children[2] == 0)
00087                                 children.resize(2);
00088                 }
00089                 else
00090                         falseBlock = 0;
00091                 
00092                 // check if both block are NULL or do not contain any data, in this case return
00093                 if (
00094                         ((trueBlock == 0) || (dynamic_cast<BlockNode*>(trueBlock) && trueBlock->children.empty())) && 
00095                         ((falseBlock == 0) || (dynamic_cast<BlockNode*>(falseBlock) && falseBlock->children.empty()))
00096                 )
00097                 {
00098                         if (dump)
00099                                 *dump << sourcePos.toWString() << L": if test removed because it had no associated code\n";
00100                         delete this;
00101                         return NULL;
00102                 }
00103                 
00104                 // check for if on constants
00105                 ImmediateNode* constantExpression = dynamic_cast<ImmediateNode*>(children[0]);
00106                 if (constantExpression)
00107                 {
00108                         if (constantExpression->value != 0)
00109                         {
00110                                 if (dump)
00111                                         *dump << sourcePos.toWString() << L": if test simplified because condition was always true\n";
00112                                 children[1] = 0;
00113                                 delete this;
00114                                 return trueBlock;
00115                         }
00116                         else
00117                         {
00118                                 if (dump)
00119                                         *dump << sourcePos.toWString() << L": if test simplified because condition was always false\n";
00120                                 if (children.size() > 2)
00121                                         children[2] = 0;
00122                                 delete this;
00123                                 return falseBlock;
00124                         }
00125                 }
00126                 
00127                 // create a dummy block for true if none exist
00128                 if (trueBlock == 0)
00129                         children[1] = new BlockNode(sourcePos);
00130                 
00131                 // fold operation inside if
00132                 BinaryArithmeticNode* operation = polymorphic_downcast<BinaryArithmeticNode*>(children[0]);
00133                 FoldedIfWhenNode *foldedNode = new FoldedIfWhenNode(sourcePos);
00134                 foldedNode->op = operation->op;
00135                 foldedNode->edgeSensitive = edgeSensitive;
00136                 foldedNode->endLine = endLine;
00137                 foldedNode->children.push_back(operation->children[0]);
00138                 foldedNode->children.push_back(operation->children[1]);
00139                 operation->children.clear();
00140                 foldedNode->children.push_back(children[1]);
00141                 children[1] = 0;
00142                 if (children.size() > 2)
00143                 {
00144                         foldedNode->children.push_back(children[2]);
00145                         children[2] = 0;
00146                 }
00147                 
00148                 if (dump)
00149                         *dump << sourcePos.toWString() << L": if condition folded inside node\n";
00150                 
00151                 delete this;
00152                 
00153                 return foldedNode;
00154         }
00155         
00156         Node* FoldedIfWhenNode::optimize(std::wostream* dump)
00157         {
00158                 abort();
00159                 return 0;
00160         }
00161         
00162         Node* WhileNode::optimize(std::wostream* dump)
00163         {
00164                 children[0] = children[0]->optimize(dump);
00165                 assert(children[0]);
00166                 
00167                 // block may be NULL
00168                 children[1] = children[1]->optimize(dump);
00169                 
00170                 // check for loops on constants
00171                 ImmediateNode* constantExpression = dynamic_cast<ImmediateNode*>(children[0]);
00172                 if (constantExpression)
00173                 {
00174                         if (constantExpression->value != 0)
00175                         {
00176                                 throw TranslatableError(sourcePos, ERROR_INFINITE_LOOP);
00177                         }
00178                         else
00179                         {
00180                                 if (dump)
00181                                         *dump << sourcePos.toWString() << L": while removed because condition is always false\n";
00182                                 delete this;
00183                                 return NULL;
00184                         }
00185                 }
00186                 
00187                 // check for loops with empty content
00188                 if ((children[1] == 0) || (dynamic_cast<BlockNode*>(children[1]) && children[1]->children.empty()))
00189                 {
00190                         if (dump)
00191                                 *dump << sourcePos.toWString() << L": while removed because it contained no statement\n";
00192                         delete this;
00193                         return NULL;
00194                 }
00195                 
00196                 // fold operation inside loop
00197                 BinaryArithmeticNode* operation = polymorphic_downcast<BinaryArithmeticNode*>(children[0]);
00198                 FoldedWhileNode *foldedNode = new FoldedWhileNode(sourcePos);
00199                 foldedNode->op = operation->op;
00200                 foldedNode->children.push_back(operation->children[0]);
00201                 foldedNode->children.push_back(operation->children[1]);
00202                 operation->children.clear();
00203                 foldedNode->children.push_back(children[1]);
00204                 children[1] = 0;
00205                 
00206                 if (dump)
00207                         *dump << sourcePos.toWString() << L": while condition folded inside node\n";
00208                 
00209                 delete this;
00210                 
00211                 return foldedNode;
00212         }
00213         
00214         Node* FoldedWhileNode::optimize(std::wostream* dump)
00215         {
00216                 abort();
00217                 return 0;
00218         }
00219         
00220         Node* EventDeclNode::optimize(std::wostream* dump)
00221         {
00222                 return this;
00223         }
00224         
00225         Node* EmitNode::optimize(std::wostream* dump)
00226         {
00227                 for (NodesVector::iterator it = children.begin(); it != children.end();)
00228                 {
00229                         // generic optimization and removal
00230                         *it = (*it)->optimize(dump);
00231                         ++it;
00232                 }
00233 
00234                 return this;
00235         }
00236         
00237         Node* SubDeclNode::optimize(std::wostream* dump)
00238         {
00239                 return this;
00240         }
00241         
00242         Node* CallSubNode::optimize(std::wostream* dump)
00243         {
00244                 return this;
00245         }
00246         
00247         Node* BinaryArithmeticNode::optimize(std::wostream* dump)
00248         {
00249                 children[0] = children[0]->optimize(dump);
00250                 assert(children[0]);
00251                 children[1] = children[1]->optimize(dump);
00252                 assert(children[1]);
00253                 
00254                 // constants elimination
00255                 ImmediateNode* immediateLeftChild = dynamic_cast<ImmediateNode*>(children[0]);
00256                 ImmediateNode* immediateRightChild = dynamic_cast<ImmediateNode*>(children[1]);
00257                 if (immediateLeftChild && immediateRightChild)
00258                 {
00259                         int valueOne = immediateLeftChild->value;
00260                         int valueTwo = immediateRightChild->value;
00261                         int result;
00262                         SourcePos pos = sourcePos;
00263                         
00264                         switch (op)
00265                         {
00266                                 case ASEBA_OP_SHIFT_LEFT: result = valueOne << valueTwo; break;
00267                                 case ASEBA_OP_SHIFT_RIGHT: result = valueOne >> valueTwo; break;
00268                                 case ASEBA_OP_ADD: result = valueOne + valueTwo; break;
00269                                 case ASEBA_OP_SUB: result = valueOne - valueTwo; break;
00270                                 case ASEBA_OP_MULT: result = valueOne * valueTwo; break;
00271                                 case ASEBA_OP_DIV: 
00272                                         if (valueTwo == 0)
00273                                                 throw TranslatableError(sourcePos, ERROR_DIVISION_BY_ZERO);
00274                                         else
00275                                                 result = valueOne / valueTwo;
00276                                 break;
00277                                 case ASEBA_OP_MOD: result = valueOne % valueTwo; break;
00278                                 
00279                                 case ASEBA_OP_EQUAL: result = valueOne == valueTwo; break;
00280                                 case ASEBA_OP_NOT_EQUAL: result = valueOne != valueTwo; break;
00281                                 case ASEBA_OP_BIGGER_THAN: result = valueOne > valueTwo; break;
00282                                 case ASEBA_OP_BIGGER_EQUAL_THAN: result = valueOne >= valueTwo; break;
00283                                 case ASEBA_OP_SMALLER_THAN: result = valueOne < valueTwo; break;
00284                                 case ASEBA_OP_SMALLER_EQUAL_THAN: result = valueOne <= valueTwo; break;
00285                                 
00286                                 case ASEBA_OP_OR: result = valueOne || valueTwo; break;
00287                                 case ASEBA_OP_AND: result = valueOne && valueTwo; break;
00288                                 
00289                                 default: abort();
00290                         }
00291                         
00292                         if (dump)
00293                                 *dump << sourcePos.toWString() << L": binary arithmetic expression simplified\n";
00294                         delete this;
00295                         return new ImmediateNode(pos, result);
00296                 }
00297                 
00298                 // multiplications by 1 or addition of 0
00299                 // TODO: make more generic the concept of neutral element
00300                 if (op == ASEBA_OP_MULT || op == ASEBA_OP_DIV || op == ASEBA_OP_ADD || op == ASEBA_OP_SUB)
00301                 {
00302                         Node **survivor(0);
00303                         if (op == ASEBA_OP_MULT || op == ASEBA_OP_DIV)
00304                         {
00305                                 if (immediateRightChild && (immediateRightChild->value == 1))
00306                                         survivor = &children[0];
00307                                 if (immediateLeftChild && (immediateLeftChild->value == 1))
00308                                         survivor = &children[1];
00309                         }
00310                         else
00311                         {
00312                                 if (immediateRightChild && (immediateRightChild->value == 0))
00313                                         survivor = &children[0];
00314                                 if (immediateLeftChild && (immediateLeftChild->value == 0))
00315                                         survivor = &children[1];
00316                         }
00317                         if (survivor)
00318                         {
00319                                 if (dump)
00320                                         *dump << sourcePos.toWString() << L": operation with neutral element removed\n";
00321                                 Node *returNode = *survivor;
00322                                 *survivor = 0;
00323                                 delete this;
00324                                 return returNode;
00325                         }
00326                 }
00327                 
00328                 // POT mult/div to shift conversion
00329                 if (immediateRightChild && isPOT(immediateRightChild->value))
00330                 {
00331                         if (op == ASEBA_OP_MULT)
00332                         {
00333                                 op = ASEBA_OP_SHIFT_LEFT;
00334                                 immediateRightChild->value = shiftFromPOT(immediateRightChild->value);
00335                                 if (dump)
00336                                         *dump << sourcePos.toWString() << L": multiplication transformed to left shift\n";
00337                         }
00338                         else if (op == ASEBA_OP_DIV)
00339                         {
00340                                 if (immediateRightChild->value == 0)
00341                                         throw TranslatableError(sourcePos, ERROR_DIVISION_BY_ZERO);
00342                                 op = ASEBA_OP_SHIFT_RIGHT;
00343                                 immediateRightChild->value = shiftFromPOT(immediateRightChild->value);
00344                                 if (dump)
00345                                         *dump << sourcePos.toWString() << L": division transformed to right shift\n";
00346                         }
00347                 }
00348                 
00349                 return this;
00350         }
00351         
00353         void BinaryArithmeticNode::deMorganNotRemoval()
00354         {
00355                 switch (op)
00356                 {
00357                         // comparison: invert
00358                         case ASEBA_OP_EQUAL: op = ASEBA_OP_NOT_EQUAL; break;
00359                         case ASEBA_OP_NOT_EQUAL: op = ASEBA_OP_EQUAL; break;
00360                         case ASEBA_OP_BIGGER_THAN: op = ASEBA_OP_SMALLER_EQUAL_THAN; break;
00361                         case ASEBA_OP_BIGGER_EQUAL_THAN: op = ASEBA_OP_SMALLER_THAN; break;
00362                         case ASEBA_OP_SMALLER_THAN: op = ASEBA_OP_BIGGER_EQUAL_THAN; break;
00363                         case ASEBA_OP_SMALLER_EQUAL_THAN: op = ASEBA_OP_BIGGER_THAN; break;
00364                         // logic: invert and call recursively
00365                         case ASEBA_OP_OR:
00366                                 op = ASEBA_OP_AND;
00367                                 polymorphic_downcast<BinaryArithmeticNode*>(children[0])->deMorganNotRemoval();
00368                                 polymorphic_downcast<BinaryArithmeticNode*>(children[1])->deMorganNotRemoval();
00369                         break;
00370                         case ASEBA_OP_AND:
00371                                 op = ASEBA_OP_OR;
00372                                 polymorphic_downcast<BinaryArithmeticNode*>(children[0])->deMorganNotRemoval();
00373                                 polymorphic_downcast<BinaryArithmeticNode*>(children[1])->deMorganNotRemoval();
00374                         break;
00375                         default: abort();
00376                 };
00377         }
00378         
00379         Node* UnaryArithmeticNode::optimize(std::wostream* dump)
00380         {
00381                 children[0] = children[0]->optimize(dump);
00382                 assert(children[0]);
00383                 
00384                 // constants elimination
00385                 ImmediateNode* immediateChild = dynamic_cast<ImmediateNode*>(children[0]);
00386                 if (immediateChild)
00387                 {
00388                         int result;
00389                         SourcePos pos = sourcePos;
00390                         
00391                         switch (op)
00392                         {
00393                                 case ASEBA_UNARY_OP_SUB: result = -immediateChild->value; break;
00394                                 case ASEBA_UNARY_OP_ABS: 
00395                                         if (immediateChild->value == -32768)
00396                                                 throw TranslatableError(sourcePos, ERROR_ABS_NOT_POSSIBLE);
00397                                         else
00398                                                 result = abs(immediateChild->value);
00399                                 break;
00400                                 case ASEBA_UNARY_OP_BIT_NOT: result = ~immediateChild->value; break;
00401                                 
00402                                 default: abort();
00403                         }
00404                         
00405                         if (dump)
00406                                 *dump << sourcePos.toWString() << L": unary arithmetic expression simplified\n";
00407                         delete this;
00408                         return new ImmediateNode(pos, result);
00409                 }
00410                 else if (op == ASEBA_UNARY_OP_NOT)
00411                 {
00412                         BinaryArithmeticNode* binaryNodeChild(dynamic_cast<BinaryArithmeticNode*>(children[0]));
00413                         if (binaryNodeChild)
00414                         {
00415                                 // de Morgan removal of not
00416                                 if (dump)
00417                                         *dump << sourcePos.toWString() << L": not removed using de Morgan\n";
00418                                 binaryNodeChild->deMorganNotRemoval();
00419                                 children.clear();
00420                                 delete this;
00421                                 return binaryNodeChild;
00422                         }
00423                         else
00424                                 return this;
00425                 }
00426                 else
00427                         return this;
00428         }
00429         
00430         Node* ImmediateNode::optimize(std::wostream* dump)
00431         {
00432                 return this;
00433         }
00434         
00435         Node* LoadNode::optimize(std::wostream* dump)
00436         {
00437                 return this;
00438         }
00439         
00440         Node* StoreNode::optimize(std::wostream* dump)
00441         {
00442                 return this;
00443         }
00444         
00445         Node* ArrayReadNode::optimize(std::wostream* dump)
00446         {
00447                 // optimize index expression
00448                 children[0] = children[0]->optimize(dump);
00449                 assert(children[0]);
00450                 
00451                 // if the index is just an integer and not an expression of any variable,
00452                 // replace array acces by simple load and verify boundary conditions
00453                 ImmediateNode* immediateChild = dynamic_cast<ImmediateNode*>(children[0]);
00454                 if (immediateChild)
00455                 {
00456                         unsigned index = immediateChild->value;
00457                         if (index >= arraySize)
00458                         {
00459                                 throw TranslatableError(sourcePos,
00460                                         ERROR_ARRAY_OUT_OF_BOUND_READ).arg(index).arg(arrayName).arg(arraySize);
00461                         }
00462                         
00463                         unsigned varAddr = arrayAddr + index;
00464                         SourcePos pos = sourcePos;
00465                         
00466                         if (dump)
00467                                 *dump << sourcePos.toWString() << L": array access transformed to single variable access\n";
00468                         delete this;
00469                         return new LoadNode(pos, varAddr);
00470                 }
00471                 else
00472                         return this;
00473         }
00474         
00475         Node* ArrayWriteNode::optimize(std::wostream* dump)
00476         {
00477                 // optimize index expression
00478                 children[0] = children[0]->optimize(dump);
00479                 assert(children[0]);
00480                 
00481                 // if the index is just an integer and not an expression of any variable,
00482                 // replace array acces by simple load and verify boundary conditions
00483                 ImmediateNode* immediateChild = dynamic_cast<ImmediateNode*>(children[0]);
00484                 if (immediateChild)
00485                 {
00486                         unsigned index = immediateChild->value;
00487                         if (index >= arraySize)
00488                         {
00489                                 throw TranslatableError(sourcePos,
00490                                         ERROR_ARRAY_OUT_OF_BOUND_WRITE).arg(index).arg(arrayName).arg(arraySize);
00491                         }
00492                         
00493                         unsigned varAddr = arrayAddr + index;
00494                         SourcePos pos = sourcePos;
00495                         
00496                         if (dump)
00497                                 *dump << sourcePos.toWString() << L": array access transformed to single variable access\n";
00498                         delete this;
00499                         return new StoreNode(pos, varAddr);
00500                 }
00501                 else
00502                         return this;
00503         }
00504         
00505         Node* CallNode::optimize(std::wostream* dump)
00506         {
00507                 for (NodesVector::iterator it = children.begin(); it != children.end();)
00508                 {
00509                         // generic optimization and removal
00510                         *it = (*it)->optimize(dump);
00511                         ++it;
00512                 }
00513 
00514                 return this;
00515         }
00516         
00519 }; // Aseba