asebaros: /opt/ros/diamondback/stacks/ethzasl_aseba/asebaros/aseba/svn/compiler/tree-optimize.cpp Source File

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