aseba: aseba: tree-emit.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 <cassert>
00023 #include <cstdlib>
00024 
00025 namespace Aseba
00026 {
00029 
00031         PreLinkBytecode::PreLinkBytecode()
00032         {
00033                 events[ASEBA_EVENT_INIT] = BytecodeVector();
00034                 current = &events[ASEBA_EVENT_INIT];
00035         };
00036         
00039         void PreLinkBytecode::fixup(const Compiler::SubroutineTable &subroutineTable)
00040         {
00041                 // clear empty events entries
00042                 for (EventsBytecode::iterator it = events.begin(); it != events.end();)
00043                 {
00044                         EventsBytecode::iterator curIt = it;
00045                         ++it;
00046                         size_t bytecodeSize = curIt->second.size();
00047                         if (bytecodeSize == 0)
00048                         {
00049                                 events.erase(curIt);
00050                         }
00051                 }
00052                 
00053                 // add terminals
00054                 for (EventsBytecode::iterator it = events.begin(); it != events.end(); ++it)
00055                 {
00056                         BytecodeVector& bytecode = it->second;
00057                         if (bytecode.getTypeOfLast() != ASEBA_BYTECODE_STOP)
00058                                 bytecode.push_back(BytecodeElement(AsebaBytecodeFromId(ASEBA_BYTECODE_STOP), bytecode.lastLine));
00059                 }
00060                 for (SubroutinesBytecode::iterator it = subroutines.begin(); it != subroutines.end(); ++it)
00061                 {
00062                         BytecodeVector& bytecode = it->second;
00063                         if (bytecode.size())
00064                         {
00065                                 bytecode.changeStopToRetSub();
00066                                 if (bytecode.getTypeOfLast() != ASEBA_BYTECODE_SUB_RET)
00067                                         bytecode.push_back(BytecodeElement(AsebaBytecodeFromId(ASEBA_BYTECODE_SUB_RET), bytecode.lastLine));
00068                         }
00069                         else
00070                                 bytecode.push_back(BytecodeElement(AsebaBytecodeFromId(ASEBA_BYTECODE_SUB_RET), subroutineTable[it->first].line));
00071                 }
00072         }
00073         
00074         
00075         unsigned Node::getStackDepth() const
00076         {
00077                 unsigned stackDepth = 0;
00078                 for (size_t i = 0; i < children.size(); i++)
00079                         stackDepth = std::max(stackDepth, children[i]->getStackDepth());
00080                 return stackDepth;
00081         }
00082         
00083         
00084         void BlockNode::emit(PreLinkBytecode& bytecodes) const
00085         {
00086                 for (size_t i = 0; i < children.size(); i++)
00087                         children[i]->emit(bytecodes);
00088         }
00089         
00090         void ProgramNode::emit(PreLinkBytecode& bytecodes) const
00091         {
00092                 BlockNode::emit(bytecodes);
00093                 
00094                 // analyze blocks for stack depth
00095                 BytecodeVector* currentBytecode = &bytecodes.events[ASEBA_EVENT_INIT];
00096                 unsigned maxStackDepth = 0;
00097                 for (size_t i = 0; i < children.size(); i++)
00098                 {
00099                         EventDeclNode* eventDecl = dynamic_cast<EventDeclNode*>(children[i]);
00100                         SubDeclNode* subDecl = dynamic_cast<SubDeclNode*>(children[i]);
00101                         if (eventDecl || subDecl)
00102                         {
00103                                 currentBytecode->maxStackDepth = maxStackDepth;
00104                                 maxStackDepth = 0;
00105                                 
00106                                 if (eventDecl)
00107                                         currentBytecode = &bytecodes.events[eventDecl->eventId];
00108                                 else
00109                                         currentBytecode = &bytecodes.subroutines[subDecl->subroutineId];
00110                         }
00111                         else
00112                                 maxStackDepth = std::max(maxStackDepth, children[i]->getStackDepth());
00113                 }
00114                 currentBytecode->maxStackDepth = maxStackDepth;
00115         }
00116         
00117         
00118         void AssignmentNode::emit(PreLinkBytecode& bytecodes) const
00119         {
00120                 assert(children.size() % 2 == 0);
00121                 for (size_t i = 0; i < children.size(); i += 2)
00122                 {
00123                         children[i+1]->emit(bytecodes);
00124                         children[i+0]->emit(bytecodes);
00125                 }
00126         }
00127 
00128         
00129         void IfWhenNode::emit(PreLinkBytecode& bytecodes) const
00130         {
00131                 abort();
00132         }
00133         
00134         
00135         void FoldedIfWhenNode::emit(PreLinkBytecode& bytecodes) const
00136         {
00137                 unsigned short bytecode;
00138                 
00139                 /*
00140                         What we want in bytecodes.currentBytecode afterwards:
00141                         
00142                         [ bytecode of left expression (ble) ]
00143                         [ bytecode of right expression (bre) ]
00144                         CondBranch bytecode
00145                         3
00146                         3 + btb.size + 1
00147                         [ bytecode of true block (btb) ]
00148                         Jump bfb.size + 1
00149                         [ bytecode of false block (bfb) ]
00150                 */
00151                 BytecodeVector ble;
00152                 BytecodeVector bre;
00153                 BytecodeVector btb;
00154                 BytecodeVector bfb;
00155                 
00156                 // save real current bytecode
00157                 BytecodeVector* currentBytecode = bytecodes.current;
00158                 
00159                 // generate code for left expression
00160                 bytecodes.current = &ble;
00161                 children[0]->emit(bytecodes);
00162                 // generate code for right expression
00163                 bytecodes.current = &bre;
00164                 children[1]->emit(bytecodes);
00165                 // generate code for true block
00166                 bytecodes.current = &btb;
00167                 children[2]->emit(bytecodes);
00168                 // generate code for false block
00169                 bytecodes.current = &bfb;
00170                 if (children.size() > 3)
00171                         children[3]->emit(bytecodes);
00172                 
00173                 // restore real current bytecode
00174                 bytecodes.current = currentBytecode;
00175                 
00176                 // fit everything together
00177                 std::copy(ble.begin(), ble.end(), std::back_inserter(*bytecodes.current));
00178                 
00179                 std::copy(bre.begin(), bre.end(), std::back_inserter(*bytecodes.current));
00180                 
00181                 bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_CONDITIONAL_BRANCH);
00182                 bytecode |= op;
00183                 bytecode |= edgeSensitive ? (1 << ASEBA_IF_IS_WHEN_BIT) : 0;
00184                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00185                 
00186                 if (children.size() == 4)
00187                         bytecodes.current->push_back(BytecodeElement(2 + btb.size() + 1, sourcePos.row));
00188                 else
00189                         bytecodes.current->push_back(BytecodeElement(2 + btb.size(), sourcePos.row));
00190                 
00191                 
00192                 std::copy(btb.begin(), btb.end(), std::back_inserter(*bytecodes.current));
00193                 
00194                 if (children.size() == 4)
00195                 {
00196                         bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_JUMP) | (bfb.size() + 1);
00197                         unsigned short jumpLine;
00198                         if (btb.size())
00199                                 jumpLine = (btb.end()-1)->line;
00200                         else
00201                                 jumpLine = sourcePos.row;
00202                         bytecodes.current->push_back(BytecodeElement(bytecode , jumpLine));
00203                         
00204                         std::copy(bfb.begin(), bfb.end(), std::back_inserter(*bytecodes.current));
00205                 }
00206                 
00207                 bytecodes.current->lastLine = endLine;
00208         }
00209         
00210         unsigned FoldedIfWhenNode::getStackDepth() const
00211         {
00212                 unsigned stackDepth = children[0]->getStackDepth() + children[1]->getStackDepth();
00213                 stackDepth = std::max(stackDepth, children[2]->getStackDepth());
00214                 if (children.size() == 4)
00215                         stackDepth = std::max(stackDepth, children[3]->getStackDepth());
00216                 return stackDepth;
00217         }
00218         
00219         
00220         void WhileNode::emit(PreLinkBytecode& bytecodes) const
00221         {
00222                 abort();
00223         }
00224         
00225         
00226         void FoldedWhileNode::emit(PreLinkBytecode& bytecodes) const
00227         {
00228                 unsigned short bytecode;
00229                 
00230                 /*
00231                         What we want in bytecodes.currentBytecode afterwards:
00232                         
00233                         [ bytecode of left expression (ble) ]
00234                         [ bytecode of right expression (bre) ]
00235                         CondBranch bytecode
00236                         3
00237                         3 + bb.size + 1
00238                         [ bytecode of block (bb) ]
00239                         Jump -(bb.size + ble.size + bre.size + 3)
00240                 */
00241                 BytecodeVector ble;
00242                 BytecodeVector bre;
00243                 BytecodeVector bb;
00244                 
00245                 // save real current bytecode
00246                 BytecodeVector* currentBytecode = bytecodes.current;
00247                 
00248                 // generate code for left expression
00249                 bytecodes.current = &ble;
00250                 children[0]->emit(bytecodes);
00251                 // generate code for right expression
00252                 bytecodes.current = &bre;
00253                 children[1]->emit(bytecodes);
00254                 // generate code for block
00255                 bytecodes.current = &bb;
00256                 children[2]->emit(bytecodes);
00257                 
00258                 // restore real current bytecode
00259                 bytecodes.current = currentBytecode;
00260                 
00261                 // fit everything together
00262                 std::copy(ble.begin(), ble.end(), std::back_inserter(*bytecodes.current));
00263                 
00264                 std::copy(bre.begin(), bre.end(), std::back_inserter(*bytecodes.current));
00265                 
00266                 bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_CONDITIONAL_BRANCH) | op;
00267                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00268                 bytecodes.current->push_back(BytecodeElement(2 + bb.size() + 1, sourcePos.row));
00269                 
00270                 std::copy(bb.begin(), bb.end(), std::back_inserter(*bytecodes.current));
00271                 
00272                 bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_JUMP);
00273                 bytecode |= ((unsigned)(-(int)(ble.size() + bre.size() + bb.size() + 2))) & 0x0fff;
00274                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00275         }
00276         
00277         unsigned FoldedWhileNode::getStackDepth() const
00278         {
00279                 unsigned stackDepth = children[0]->getStackDepth() + children[1]->getStackDepth();
00280                 stackDepth = std::max(stackDepth, children[2]->getStackDepth());
00281                 return stackDepth;
00282         }
00283         
00284         
00285         void EventDeclNode::emit(PreLinkBytecode& bytecodes) const
00286         {
00287                 // make sure that we do not have twice the same event
00288                 assert(bytecodes.events.find(eventId) == bytecodes.events.end());
00289                 
00290                 // create new bytecode for event
00291                 bytecodes.events[eventId] = BytecodeVector();
00292                 bytecodes.current = &bytecodes.events[eventId];
00293         }
00294         
00295         
00296         void EmitNode::emit(PreLinkBytecode& bytecodes) const
00297         {
00298                 // emit code for children. They might contain code to store constants somewhere
00299                 for (size_t i = 0; i < children.size(); i++)
00300                         children[i]->emit(bytecodes);
00301 
00302                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_EMIT) | eventId;
00303                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00304                 bytecodes.current->push_back(BytecodeElement(arrayAddr, sourcePos.row));
00305                 bytecodes.current->push_back(BytecodeElement(arraySize, sourcePos.row));
00306         }
00307         
00308         
00309         void SubDeclNode::emit(PreLinkBytecode& bytecodes) const
00310         {
00311                 // make sure that we do not have twice the same subroutine
00312                 assert(bytecodes.subroutines.find(subroutineId) == bytecodes.subroutines.end());
00313                 
00314                 // create new bytecode for subroutine
00315                 bytecodes.subroutines[subroutineId] = BytecodeVector();
00316                 bytecodes.current = &bytecodes.subroutines[subroutineId];
00317         }
00318         
00319         
00320         void CallSubNode::emit(PreLinkBytecode& bytecodes) const
00321         {
00322                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_SUB_CALL);
00323                 bytecode |= subroutineId;
00324                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00325         }
00326         
00327         
00328         void BinaryArithmeticNode::emit(PreLinkBytecode& bytecodes) const
00329         {
00330                 children[0]->emit(bytecodes);
00331                 children[1]->emit(bytecodes);
00332                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_BINARY_ARITHMETIC) | op;
00333                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00334         }
00335         
00336         unsigned BinaryArithmeticNode::getStackDepth() const
00337         {
00338                 return children[0]->getStackDepth() + children[1]->getStackDepth();
00339         }
00340         
00341         
00342         void UnaryArithmeticNode::emit(PreLinkBytecode& bytecodes) const
00343         {
00344                 children[0]->emit(bytecodes);
00345                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_UNARY_ARITHMETIC) | op;
00346                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00347         }
00348         
00349         
00350         void ImmediateNode::emit(PreLinkBytecode& bytecodes) const
00351         {
00352                 unsigned short bytecode;
00353                 
00354                 if ((abs(value) >> 11) == 0)
00355                 {
00356                         bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_SMALL_IMMEDIATE);
00357                         bytecode |= ((unsigned)value) & 0x0fff;
00358                         bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00359                 }
00360                 else
00361                 {
00362                         bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_LARGE_IMMEDIATE);
00363                         bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00364                         bytecodes.current->push_back(BytecodeElement(value, sourcePos.row));
00365                 }
00366         }
00367         
00368         unsigned ImmediateNode::getStackDepth() const
00369         {
00370                 return 1;
00371         }
00372         
00373         
00374         void LoadNode::emit(PreLinkBytecode& bytecodes) const
00375         {
00376                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_LOAD) | varAddr;
00377                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00378         }
00379         
00380         unsigned LoadNode::getStackDepth() const
00381         {
00382                 return 1;
00383         }
00384         
00385         
00386         void StoreNode::emit(PreLinkBytecode& bytecodes) const
00387         {
00388                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_STORE) | varAddr;
00389                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00390         }
00391         
00392         
00393         void ArrayReadNode::emit(PreLinkBytecode& bytecodes) const
00394         {
00395                 // constant index should have been optimized out already
00396                 ImmediateNode* immediateChild = dynamic_cast<ImmediateNode*>(children[0]);
00397                 assert(immediateChild == 0);
00398                 
00399                 children[0]->emit(bytecodes);
00400                 
00401                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_LOAD_INDIRECT) | arrayAddr;
00402                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00403                 bytecodes.current->push_back(BytecodeElement(arraySize, sourcePos.row));
00404         }
00405         
00406         
00407         void ArrayWriteNode::emit(PreLinkBytecode& bytecodes) const
00408         {
00409                 // constant index should have been optimized out already
00410                 ImmediateNode* immediateChild = dynamic_cast<ImmediateNode*>(children[0]);
00411                 assert(immediateChild == 0);
00412                 
00413                 children[0]->emit(bytecodes);
00414                 
00415                 unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_STORE_INDIRECT) | arrayAddr;
00416                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00417                 bytecodes.current->push_back(BytecodeElement(arraySize, sourcePos.row));
00418         }
00419         
00420         void CallNode::emit(PreLinkBytecode& bytecodes) const
00421         {
00422                 unsigned short bytecode;
00423                 
00424                 // emit code for children. They might contain code to store constants somewhere
00425                 for (size_t i = 0; i < children.size(); i++)
00426                         children[i]->emit(bytecodes);
00427                 
00428                 // generate load for arguments in reverse order
00429                 int i = (int)argumentsAddr.size() - 1;
00430                 while (i >= 0)
00431                 {
00432                         if ((abs(argumentsAddr[i]) >> 11) == 0)
00433                         {
00434                                 bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_SMALL_IMMEDIATE);
00435                                 bytecode |= ((unsigned)argumentsAddr[i]) & 0x0fff;
00436                                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00437                         }
00438                         else
00439                         {
00440                                 bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_LARGE_IMMEDIATE);
00441                                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00442                                 bytecodes.current->push_back(BytecodeElement(argumentsAddr[i], sourcePos.row));
00443                         }
00444                         i--;
00445                 }
00446                 
00447                 // generate call itself
00448                 bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_NATIVE_CALL) | funcId;
00449                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00450         }
00451         
00452         unsigned CallNode::getStackDepth() const
00453         {
00454                 size_t stackDepth = Node::getStackDepth();
00455                 
00456                 // get the stack depth for arguments
00457                 stackDepth = std::max(stackDepth, argumentsAddr.size());
00458                 
00459                 return stackDepth;
00460         }
00461         
00462         void ReturnNode::emit(PreLinkBytecode& bytecodes) const
00463         {
00464                 const unsigned short bytecode = AsebaBytecodeFromId(ASEBA_BYTECODE_STOP);
00465                 bytecodes.current->push_back(BytecodeElement(bytecode, sourcePos.row));
00466         }
00467         
00470 }; // Aseba