projects/Stacker/lib/compiler/StackerCompiler.cpp

   1 //===-- StackerCompiler.cpp - Parser for llvm assembly files ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Reid Spencer and donated to the LLVM research
   6 // group and is distributed under the University of Illinois Open Source
   7 // License. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10 //
  11 //  This file implements the compiler for the "Stacker" language.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 //===----------------------------------------------------------------------===//
  16 //            Globasl - Global variables we use
  17 //===----------------------------------------------------------------------===//
  18
  19 #include <llvm/Analysis/Verifier.h>
  20 #include <llvm/iMemory.h>
  21 #include <llvm/iOperators.h>
  22 #include <llvm/iOther.h>
  23 #include <llvm/iTerminators.h>
  24 #include <Support/Statistic.h>
  25 #include "StackerCompiler.h"
  26 #include "StackerParser.h"
  27 #include <string>
  28
  29 // Lexer/Parser defined variables and functions
  30 extern std::FILE *Stackerin;
  31 extern int Stackerlineno;
  32 extern char* Stackertext;
  33 extern int Stackerleng;
  34 extern int Stackerparse();
  35
  36 StackerCompiler* StackerCompiler::TheInstance = 0;
  37
  38 static Statistic<> NumDefinitions(
  39         "numdefs","The # of definitions encoutered while compiling Stacker");
  40
  41 StackerCompiler::StackerCompiler()
  42     : CurFilename("")
  43     , TheModule(0)
  44     , TheFunction(0)
  45     , DefinitionType(0)
  46     , TheStack(0)
  47     , TheIndex(0)
  48     , TheScanf(0)
  49     , ThePrintf(0)
  50     , TheExit(0)
  51     , StrFormat(0)
  52     , NumFormat(0)
  53     , ChrFormat(0)
  54     , InStrFormat(0)
  55     , InNumFormat(0)
  56     , InChrFormat(0)
  57     , Zero(0)
  58     , One(0)
  59     , Two(0)
  60     , Three(0)
  61     , Four(0)
  62     , Five(0)
  63     , IZero(0)
  64     , IOne(0)
  65     , ITwo(0)
  66     , no_arguments()
  67     , echo(false)
  68     , stack_size(256)
  69     , stack_type(0)
  70 {
  71 }
  72
  73 StackerCompiler::~StackerCompiler()
  74 {
  75     // delete TheModule; << don't do this!
  76     // TheModule is passed to caller of the compile() method .. its their
  77     // problem.  Likewise for the other allocated objects (which become part
  78     // of TheModule.
  79     TheModule = 0;
  80     DefinitionType = 0;
  81     TheStack = 0;
  82     TheIndex = 0;
  83 }
  84
  85 Module*
  86 StackerCompiler::compile(
  87     const std::string& filename,
  88     bool should_echo,
  89     size_t the_stack_size
  90 )
  91 {
  92     // TODO: Provide a global lock to protect the singled-threaded compiler
  93     // and its global variables. Should be in guard object on the stack so
  94     // that its destructor causes lock to be released (multiple exits from
  95     // this function).
  96
  97     // Assign parameters
  98     CurFilename = filename;
  99     echo = should_echo;
 100     stack_size = the_stack_size;
 101
 102     /// Default the file to read
 103     FILE *F = stdin;
 104
 105     ///
 106     if (filename != "-")
 107     {
 108         F = fopen(filename.c_str(), "r");
 109
 110         if (F == 0)
 111         {
 112             throw ParseException(filename,
 113                 "Could not open file '" + filename + "'");
 114         }
 115     }
 116
 117     Module *Result;
 118     try
 119     {
 120         // Create the module we'll return
 121         TheModule = new Module( CurFilename );
 122
 123         // Create a type to represent the stack. This is the same as the LLVM
 124         // Assembly type [ 256 x int ]
 125         stack_type = ArrayType::get( Type::IntTy, stack_size );
 126
 127         // Create a global variable for the stack. Note the use of appending
 128         // linkage linkage so that multiple modules will make the stack larger.
 129         // Also note that the last argument causes the global to be inserted
 130         // automatically into the module.
 131         TheStack = new GlobalVariable(
 132             /*type=*/ stack_type,
 133             /*isConstant=*/ false,
 134             /*Linkage=*/ GlobalValue::AppendingLinkage,
 135             /*initializer=*/Constant::getNullValue(stack_type),
 136             /*name=*/ "_stack_",
 137             /*parent=*/ TheModule
 138         );
 139
 140         // Create a global variable for indexing into the stack. Note the use
 141         // of LinkOnce linkage. Only one copy of _index_ will be retained
 142         // after linking
 143         TheIndex = new GlobalVariable(
 144             /*type=*/Type::LongTy,
 145             /*isConstant=*/false,
 146             /*Linkage=*/GlobalValue::LinkOnceLinkage,
 147             /*initializer=*/Constant::getNullValue(Type::LongTy),
 148             /*name=*/"_index_",
 149             /*parent=*/TheModule
 150         );
 151
 152         // Create a function prototype for definitions. No parameters, no
 153         // result.  This is used below any time a function is created.
 154         std::vector<const Type*> params; // No parameters
 155         DefinitionType = FunctionType::get( Type::VoidTy, params, false );
 156
 157         // Create a function for printf(3)
 158         params.push_back( PointerType::get( Type::SByteTy ) );
 159         FunctionType* printf_type =
 160             FunctionType::get( Type::IntTy, params, true );
 161         ThePrintf = new Function(
 162             printf_type, GlobalValue::ExternalLinkage, "printf", TheModule);
 163
 164         // Create a function for scanf(3)
 165         TheScanf = new Function(
 166             printf_type, GlobalValue::ExternalLinkage, "scanf", TheModule);
 167
 168         // Create a function for exit(3)
 169         params.clear();
 170         params.push_back( Type::IntTy );
 171         FunctionType* exit_type =
 172             FunctionType::get( Type::VoidTy, params, false );
 173         TheExit = new Function(
 174             exit_type, GlobalValue::ExternalLinkage, "exit", TheModule);
 175
 176         ConstantArray* str_format = ConstantArray::get("%s");
 177         StrFormat = new GlobalVariable(
 178             /*type=*/ArrayType::get( Type::SByteTy,  3 ),
 179             /*isConstant=*/true,
 180             /*Linkage=*/GlobalValue::LinkOnceLinkage,
 181             /*initializer=*/str_format,
 182             /*name=*/"_str_format_",
 183             /*parent=*/TheModule
 184         );
 185
 186         ConstantArray* in_str_format = ConstantArray::get(" %as");
 187         InStrFormat = new GlobalVariable(
 188             /*type=*/ArrayType::get( Type::SByteTy,  5 ),
 189             /*isConstant=*/true,
 190             /*Linkage=*/GlobalValue::LinkOnceLinkage,
 191             /*initializer=*/in_str_format,
 192             /*name=*/"_in_str_format_",
 193             /*parent=*/TheModule
 194         );
 195
 196         ConstantArray* num_format = ConstantArray::get("%d");
 197         NumFormat = new GlobalVariable(
 198             /*type=*/ArrayType::get( Type::SByteTy,  3 ),
 199             /*isConstant=*/true,
 200             /*Linkage=*/GlobalValue::LinkOnceLinkage,
 201             /*initializer=*/num_format,
 202             /*name=*/"_num_format_",
 203             /*parent=*/TheModule
 204         );
 205
 206         ConstantArray* in_num_format = ConstantArray::get(" %d");
 207         InNumFormat = new GlobalVariable(
 208             /*type=*/ArrayType::get( Type::SByteTy,  4 ),
 209             /*isConstant=*/true,
 210             /*Linkage=*/GlobalValue::LinkOnceLinkage,
 211             /*initializer=*/in_num_format,
 212             /*name=*/"_in_num_format_",
 213             /*parent=*/TheModule
 214         );
 215
 216         ConstantArray* chr_format = ConstantArray::get("%c");
 217         ChrFormat = new GlobalVariable(
 218             /*type=*/ArrayType::get( Type::SByteTy,  3 ),
 219             /*isConstant=*/true,
 220             /*Linkage=*/GlobalValue::LinkOnceLinkage,
 221             /*initializer=*/chr_format,
 222             /*name=*/"_chr_format_",
 223             /*parent=*/TheModule
 224         );
 225
 226         ConstantArray* in_chr_format = ConstantArray::get(" %c");
 227         InChrFormat = new GlobalVariable(
 228             /*type=*/ArrayType::get( Type::SByteTy,  4 ),
 229             /*isConstant=*/true,
 230             /*Linkage=*/GlobalValue::LinkOnceLinkage,
 231             /*initializer=*/in_chr_format,
 232             /*name=*/"_in_chr_format_",
 233             /*parent=*/TheModule
 234         );
 235
 236         // Get some constants so we aren't always creating them
 237         Zero = ConstantInt::get( Type::LongTy, 0 );
 238         One = ConstantInt::get( Type::LongTy, 1 );
 239         Two = ConstantInt::get( Type::LongTy, 2 );
 240         Three = ConstantInt::get( Type::LongTy, 3 );
 241         Four = ConstantInt::get( Type::LongTy, 4 );
 242         Five = ConstantInt::get( Type::LongTy, 5 );
 243         IZero = ConstantInt::get( Type::IntTy, 0 );
 244         IOne = ConstantInt::get( Type::IntTy, 1 );
 245         ITwo = ConstantInt::get( Type::IntTy, 2 );
 246
 247         // Reset the current line number
 248         Stackerlineno = 1;
 249
 250         // Reset the parser's input to F
 251         Stackerin = F;          // Set the input file.
 252
 253         // Let the parse know about this instance
 254         TheInstance = this;
 255
 256         // Parse the file. The parser (see StackParser.y) will call back to
 257         // the StackCompiler via the "handle*" methods
 258         Stackerparse();
 259
 260         // Avoid potential illegal use (TheInstance might be on the stack)
 261         TheInstance = 0;
 262
 263     } catch (...) {
 264         if (F != stdin) fclose(F);      // Make sure to close file descriptor
 265         throw;                          // if an exception is thrown
 266     }
 267
 268     // Close the file
 269     if (F != stdin) fclose(F);
 270
 271     // Return the compiled module to the caller
 272     return TheModule;
 273 }
 274
 275 //===----------------------------------------------------------------------===//
 276 //            Internal Functions, used by handleXXX below.
 277 //            These represent the basic stack operations.
 278 //===----------------------------------------------------------------------===//
 279
 280 Instruction*
 281 StackerCompiler::incr_stack_index( BasicBlock* bb, Value* ival = 0 )
 282 {
 283     // Load the value from the TheIndex
 284     LoadInst* loadop = new LoadInst( TheIndex );
 285     bb->getInstList().push_back( loadop );
 286
 287     // Increment the loaded index value
 288     if ( ival == 0 ) ival = One;
 289     CastInst* caster = new CastInst( ival, Type::LongTy );
 290     bb->getInstList().push_back( caster );
 291     BinaryOperator* addop = BinaryOperator::create( Instruction::Add,
 292             loadop, caster);
 293     bb->getInstList().push_back( addop );
 294
 295     // Store the incremented value
 296     StoreInst* storeop = new StoreInst( addop, TheIndex );
 297     bb->getInstList().push_back( storeop );
 298     return storeop;
 299 }
 300
 301 Instruction*
 302 StackerCompiler::decr_stack_index( BasicBlock* bb, Value* ival = 0 )
 303 {
 304     // Load the value from the TheIndex
 305     LoadInst* loadop = new LoadInst( TheIndex );
 306     bb->getInstList().push_back( loadop );
 307
 308     // Decrement the loaded index value
 309     if ( ival == 0 ) ival = One;
 310     CastInst* caster = new CastInst( ival, Type::LongTy );
 311     bb->getInstList().push_back( caster );
 312     BinaryOperator* subop = BinaryOperator::create( Instruction::Sub,
 313             loadop, caster);
 314     bb->getInstList().push_back( subop );
 315
 316     // Store the incremented value
 317     StoreInst* storeop = new StoreInst( subop, TheIndex );
 318     bb->getInstList().push_back( storeop );
 319
 320     return storeop;
 321 }
 322
 323 Instruction*
 324 StackerCompiler::get_stack_pointer( BasicBlock* bb, Value* index = 0 )
 325 {
 326     // Load the value of the Stack Index
 327     LoadInst* loadop = new LoadInst( TheIndex );
 328     bb->getInstList().push_back( loadop );
 329
 330     // Index into the stack to get its address. NOTE the use of two
 331     // elements in this vector. The first de-references the pointer that
 332     // "TheStack" represents. The second indexes into the pointed to array.
 333     // Think of the first index as getting the address of the 0th element
 334     // of the array.
 335     std::vector<Value*> indexVec;
 336     indexVec.push_back( Zero );
 337
 338     if ( index == 0 )
 339     {
 340         indexVec.push_back(loadop);
 341     }
 342     else
 343     {
 344         CastInst* caster = new CastInst( index, Type::LongTy );
 345         bb->getInstList().push_back( caster );
 346         BinaryOperator* subop = BinaryOperator::create(
 347             Instruction::Sub, loadop, caster );
 348         bb->getInstList().push_back( subop );
 349         indexVec.push_back(subop);
 350     }
 351
 352     // Get the address of the indexed stack element
 353     GetElementPtrInst* gep = new GetElementPtrInst( TheStack, indexVec );
 354     bb->getInstList().push_back( gep );         // Put GEP in Block
 355
 356     return gep;
 357 }
 358
 359 Instruction*
 360 StackerCompiler::push_value( BasicBlock* bb, Value* val )
 361 {
 362     // Get location of
 363     incr_stack_index(bb);
 364
 365     // Get the stack pointer
 366     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 367             get_stack_pointer( bb ) );
 368
 369     // Cast the value to an integer .. hopefully it works
 370     CastInst* cast_inst = new CastInst( val, Type::IntTy );
 371     bb->getInstList().push_back( cast_inst );
 372
 373     // Store the value
 374     StoreInst* storeop = new StoreInst( cast_inst, gep );
 375     bb->getInstList().push_back( storeop );
 376
 377     return storeop;
 378 }
 379
 380 Instruction*
 381 StackerCompiler::push_integer(BasicBlock* bb, int32_t value )
 382 {
 383     // Just push a constant integer value
 384     return push_value( bb, ConstantSInt::get( Type::IntTy, value ) );
 385 }
 386
 387 Instruction*
 388 StackerCompiler::pop_integer( BasicBlock*bb )
 389 {
 390     // Get the stack pointer
 391     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 392         get_stack_pointer( bb ));
 393
 394     // Load the value
 395     LoadInst* load_inst = new LoadInst( gep );
 396     bb->getInstList().push_back( load_inst );
 397
 398     // Decrement the stack index
 399     decr_stack_index( bb );
 400
 401     // Return the value
 402     return load_inst;
 403 }
 404
 405 Instruction*
 406 StackerCompiler::push_string( BasicBlock* bb, const char* value )
 407 {
 408     // Get length of the string
 409     size_t len = strlen( value );
 410
 411     // Create a type for the string constant. Length is +1 for
 412     // the terminating 0.
 413     ArrayType* char_array = ArrayType::get( Type::SByteTy, len + 1 );
 414
 415     // Create an initializer for the value
 416     ConstantArray* initVal = ConstantArray::get( value );
 417
 418     // Create an internal linkage global variable to hold the constant.
 419     GlobalVariable* strconst = new GlobalVariable(
 420         char_array,
 421         /*isConstant=*/true,
 422         GlobalValue::InternalLinkage,
 423         /*initializer=*/initVal,
 424         "",
 425         TheModule
 426     );
 427
 428     // Push the casted value
 429     return push_value( bb, strconst );
 430 }
 431
 432 Instruction*
 433 StackerCompiler::pop_string( BasicBlock* bb )
 434 {
 435     // Get location of stack pointer
 436     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 437         get_stack_pointer( bb ));
 438
 439     // Load the value from the stack
 440     LoadInst* loader = new LoadInst( gep );
 441     bb->getInstList().push_back( loader );
 442
 443     // Cast the integer to a sbyte*
 444     CastInst* caster = new CastInst( loader, PointerType::get(Type::SByteTy) );
 445     bb->getInstList().push_back( caster );
 446
 447     // Decrement stack index
 448     decr_stack_index( bb );
 449
 450     // Return the value
 451     return caster;
 452 }
 453
 454 Instruction*
 455 StackerCompiler::replace_top( BasicBlock* bb, Value* new_top, Value* index = 0 )
 456 {
 457     // Get the stack pointer
 458     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 459             get_stack_pointer( bb, index ));
 460
 461     // Store the value there
 462     StoreInst* store_inst = new StoreInst( new_top, gep );
 463     bb->getInstList().push_back( store_inst );
 464
 465     // Return the value
 466     return store_inst;
 467 }
 468
 469 Instruction*
 470 StackerCompiler::stack_top( BasicBlock* bb, Value* index = 0 )
 471 {
 472     // Get the stack pointer
 473     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 474         get_stack_pointer( bb, index ));
 475
 476     // Load the value
 477     LoadInst* load_inst = new LoadInst( gep );
 478     bb->getInstList().push_back( load_inst );
 479
 480     // Return the value
 481     return load_inst;
 482 }
 483
 484 Instruction*
 485 StackerCompiler::stack_top_string( BasicBlock* bb, Value* index = 0 )
 486 {
 487     // Get location of stack pointer
 488     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 489         get_stack_pointer( bb, index ));
 490
 491     // Load the value from the stack
 492     LoadInst* loader = new LoadInst( gep );
 493     bb->getInstList().push_back( loader );
 494
 495     // Cast the integer to a sbyte*
 496     CastInst* caster = new CastInst( loader, PointerType::get(Type::SByteTy) );
 497     bb->getInstList().push_back( caster );
 498
 499     // Return the value
 500     return caster;
 501 }
 502
 503 static void
 504 add_block( Function*f, BasicBlock* bb )
 505 {
 506     if ( ! f->empty() && f->back().getTerminator() == 0 )
 507     {
 508         BranchInst* branch = new BranchInst(bb);
 509         f->back().getInstList().push_back( branch );
 510     }
 511     f->getBasicBlockList().push_back( bb );
 512 }
 513
 514
 515 //===----------------------------------------------------------------------===//
 516 //            handleXXX - Handle semantics of parser productions
 517 //===----------------------------------------------------------------------===//
 518
 519 Module*
 520 StackerCompiler::handle_module_start( )
 521 {
 522     // Return the newly created module
 523     return TheModule;
 524 }
 525
 526 Module*
 527 StackerCompiler::handle_module_end( Module* mod )
 528 {
 529     // Return the module.
 530     return mod;
 531 }
 532
 533 Module*
 534 StackerCompiler::handle_definition_list_start()
 535 {
 536     return TheModule;
 537 }
 538
 539 Module*
 540 StackerCompiler::handle_definition_list_end( Module* mod, Function* definition )
 541 {
 542     if ( ! definition->empty() )
 543     {
 544         BasicBlock& last_block = definition->back();
 545         if ( last_block.getTerminator() == 0 )
 546         {
 547             last_block.getInstList().push_back( new ReturnInst() );
 548         }
 549     }
 550     // Insert the definition into the module
 551     mod->getFunctionList().push_back( definition );
 552
 553     // Bump our (sample) statistic.
 554     ++NumDefinitions;
 555     return mod;
 556 }
 557
 558 Function*
 559 StackerCompiler::handle_main_definition( Function* func )
 560 {
 561     // Set the name of the function defined as the Stacker main
 562     func->setName( "_MAIN_");
 563
 564     // Create the actual main for the runtime system.
 565     //std::vector<const Type*> params; // No parameters
 566     //FunctionType* main_type = FunctionType::get( Type::IntTy, params, false );
 567     Function* SystemMain = new Function(
 568         DefinitionType,
 569         GlobalValue::ExternalLinkage,
 570         "main", TheModule);
 571
 572     // Create a basic block that just calls the STACKERMAIN function. Note
 573     // that the basic block is automatically inserted into the end of SystemMain
 574     BasicBlock* bb = new BasicBlock( (echo?"main":"a"), SystemMain ) ;
 575     bb->getInstList().push_back( new CallInst( func, no_arguments) );
 576     bb->getInstList().push_back( new ReturnInst() );
 577
 578     // Turn "_stack_" into an initialized variable since this is the main
 579     // module. This causes it to not be "external" but defined in this module.
 580     TheStack->setInitializer( Constant::getNullValue(stack_type) );
 581
 582     // Turn "_index_" into an intialized variable for the same reason.
 583     TheIndex->setInitializer( Constant::getNullValue(Type::LongTy) );
 584     return func;
 585 }
 586
 587 Function*
 588 StackerCompiler::handle_forward( char * name )
 589 {
 590     // Just create a placeholder function
 591     Function* the_function = new Function (
 592         DefinitionType,
 593         GlobalValue::ExternalLinkage,
 594         name );
 595     assert( the_function->isExternal() );
 596
 597     free( name );
 598     return the_function;
 599 }
 600
 601 Function*
 602 StackerCompiler::handle_definition( char * name, Function* f )
 603 {
 604     // Look up the function name in the module to see if it was forward
 605     // declared.
 606     Function* existing_function = TheModule->getNamedFunction( name );
 607
 608 #if 0
 609     // If the function already exists...
 610     if ( existing_function )
 611     {
 612         // Just get rid of the placeholder
 613         existing_function->dropAllReferences();
 614         delete existing_function;
 615     }
 616 #endif
 617
 618     // Just set the name of the function now that we know what it is.
 619     f->setName( name );
 620
 621     free( name );
 622
 623     return f;
 624 }
 625
 626 Function*
 627 StackerCompiler::handle_word_list_start()
 628 {
 629     TheFunction = new Function(DefinitionType, GlobalValue::ExternalLinkage);
 630     return TheFunction;
 631 }
 632
 633 Function*
 634 StackerCompiler::handle_word_list_end( Function* f, BasicBlock* bb )
 635 {
 636     add_block( f, bb );
 637     return f;
 638 }
 639
 640 BasicBlock*
 641 StackerCompiler::handle_if( char* ifTrue, char* ifFalse )
 642 {
 643     // Create a basic block for the preamble
 644     BasicBlock* bb = new BasicBlock((echo?"if":""));
 645
 646     // Get the condition value
 647     LoadInst* cond = cast<LoadInst>( pop_integer(bb) );
 648
 649     // Compare the condition against 0
 650     SetCondInst* cond_inst = new SetCondInst( Instruction::SetNE, cond,
 651         ConstantSInt::get( Type::IntTy, 0) );
 652     bb->getInstList().push_back( cond_inst );
 653
 654     // Create an exit block
 655     BasicBlock* exit_bb = new BasicBlock((echo?"endif":""));
 656
 657     // Create the true_block
 658     BasicBlock* true_bb = new BasicBlock((echo?"then":""));
 659
 660     // Create the false_block
 661     BasicBlock* false_bb = 0;
 662     if ( ifFalse ) false_bb = new BasicBlock((echo?"else":""));
 663
 664     // Create a branch on the SetCond
 665     BranchInst* br_inst = new BranchInst( true_bb,
 666         ( ifFalse ? false_bb : exit_bb ), cond_inst );
 667     bb->getInstList().push_back( br_inst );
 668
 669     // Fill the true block
 670     std::vector<Value*> args;
 671     if ( Function* true_func = TheModule->getNamedFunction(ifTrue) )
 672     {
 673         true_bb->getInstList().push_back(
 674                 new CallInst( true_func, args ) );
 675         true_bb->getInstList().push_back(
 676                 new BranchInst( exit_bb ) );
 677     }
 678     else
 679     {
 680         ThrowException(std::string("Function '") + ifTrue +
 681             "' must be declared first.'");
 682     }
 683
 684     free( ifTrue );
 685
 686     // Fill the false block
 687     if ( false_bb )
 688     {
 689         if ( Function* false_func = TheModule->getNamedFunction(ifFalse) )
 690         {
 691             false_bb->getInstList().push_back(
 692                     new CallInst( false_func, args ) );
 693             false_bb->getInstList().push_back(
 694                     new BranchInst( exit_bb ) );
 695         }
 696         else
 697         {
 698             ThrowException(std::string("Function '") + ifFalse +
 699                     "' must be declared first.'");
 700         }
 701         free( ifFalse );
 702     }
 703
 704     // Add the blocks to the function
 705     add_block( TheFunction, bb );
 706     add_block( TheFunction, true_bb );
 707     if ( false_bb ) add_block( TheFunction, false_bb );
 708
 709     return exit_bb;
 710 }
 711
 712 BasicBlock*
 713 StackerCompiler::handle_while( char* todo )
 714 {
 715
 716     // Create a basic block for the loop test
 717     BasicBlock* test = new BasicBlock((echo?"while":""));
 718
 719     // Create an exit block
 720     BasicBlock* exit = new BasicBlock((echo?"end":""));
 721
 722     // Create a loop body block
 723     BasicBlock* body = new BasicBlock((echo?"do":""));
 724
 725     // Create a root node
 726     BasicBlock* bb = new BasicBlock((echo?"root":""));
 727     BranchInst* root_br_inst = new BranchInst( test );
 728     bb->getInstList().push_back( root_br_inst );
 729
 730     // Pop the condition value
 731     LoadInst* cond = cast<LoadInst>( stack_top(test) );
 732
 733     // Compare the condition against 0
 734     SetCondInst* cond_inst = new SetCondInst(
 735         Instruction::SetNE, cond, ConstantSInt::get( Type::IntTy, 0) );
 736     test->getInstList().push_back( cond_inst );
 737
 738     // Add the branch instruction
 739     BranchInst* br_inst = new BranchInst( body, exit, cond_inst );
 740     test->getInstList().push_back( br_inst );
 741
 742     // Fill in the body
 743     std::vector<Value*> args;
 744     if ( Function* body_func = TheModule->getNamedFunction(todo) )
 745     {
 746         body->getInstList().push_back( new CallInst( body_func, args ) );
 747         body->getInstList().push_back( new BranchInst( test ) );
 748     }
 749     else
 750     {
 751         ThrowException(std::string("Function '") + todo +
 752             "' must be declared first.'");
 753     }
 754
 755     free( todo );
 756
 757     // Add the blocks
 758     add_block( TheFunction, bb );
 759     add_block( TheFunction, test );
 760     add_block( TheFunction, body );
 761
 762     return exit;
 763 }
 764
 765 BasicBlock*
 766 StackerCompiler::handle_identifier( char * name )
 767 {
 768     Function* func = TheModule->getNamedFunction( name );
 769     BasicBlock* bb = new BasicBlock((echo?"call":""));
 770     if ( func )
 771     {
 772         CallInst* call_def = new CallInst( func , no_arguments );
 773         bb->getInstList().push_back( call_def );
 774     }
 775     else
 776     {
 777         ThrowException(std::string("Definition '") + name +
 778             "' must be defined before it can be used.");
 779     }
 780
 781     free( name );
 782     return bb;
 783 }
 784
 785 BasicBlock*
 786 StackerCompiler::handle_string( char * value )
 787 {
 788     // Create a new basic block for the push operation
 789     BasicBlock* bb = new BasicBlock((echo?"string":""));
 790
 791     // Push the string onto the stack
 792     push_string(bb, value);
 793
 794     // Free the strdup'd string
 795     free( value );
 796
 797     return bb;
 798 }
 799
 800 BasicBlock*
 801 StackerCompiler::handle_integer( const int32_t value )
 802 {
 803     // Create a new basic block for the push operation
 804     BasicBlock* bb = new BasicBlock((echo?"int":""));
 805
 806     // Push the integer onto the stack
 807     push_integer(bb, value );
 808
 809     return bb;
 810 }
 811
 812 BasicBlock*
 813 StackerCompiler::handle_word( int tkn )
 814 {
 815     // Create a new basic block to hold the instruction(s)
 816     BasicBlock* bb = new BasicBlock();
 817
 818     /* Fill the basic block with the appropriate instructions */
 819     switch ( tkn )
 820     {
 821     case DUMP :  // Dump the stack (debugging aid)
 822     {
 823         if (echo) bb->setName("DUMP");
 824         Function* f = TheModule->getOrInsertFunction(
 825             "_stacker_dump_stack_", DefinitionType);
 826         std::vector<Value*> args;
 827         bb->getInstList().push_back( new CallInst( f, args ) );
 828         break;
 829     }
 830
 831     // Logical Operations
 832     case TRUE :  // -- -1
 833     {
 834         if (echo) bb->setName("TRUE");
 835         push_integer(bb,-1);
 836         break;
 837     }
 838     case FALSE : // -- 0
 839     {
 840         if (echo) bb->setName("FALSE");
 841         push_integer(bb,0);
 842         break;
 843     }
 844     case LESS : // w1 w2 -- w2<w1
 845     {
 846         if (echo) bb->setName("LESS");
 847         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 848         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 849         SetCondInst* cond_inst =
 850             new SetCondInst( Instruction::SetLT, op1, op2 );
 851         bb->getInstList().push_back( cond_inst );
 852         push_value( bb, cond_inst );
 853         break;
 854     }
 855     case MORE : // w1 w2 -- w2>w1
 856     {
 857         if (echo) bb->setName("MORE");
 858         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 859         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 860         SetCondInst* cond_inst =
 861             new SetCondInst( Instruction::SetGT, op1, op2 );
 862         bb->getInstList().push_back( cond_inst );
 863         push_value( bb, cond_inst );
 864         break;
 865     }
 866     case LESS_EQUAL : // w1 w2 -- w2<=w1
 867     {
 868         if (echo) bb->setName("LE");
 869         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 870         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 871         SetCondInst* cond_inst =
 872             new SetCondInst( Instruction::SetLE, op1, op2 );
 873         bb->getInstList().push_back( cond_inst );
 874         push_value( bb, cond_inst );
 875         break;
 876     }
 877     case MORE_EQUAL : // w1 w2 -- w2>=w1
 878     {
 879         if (echo) bb->setName("GE");
 880         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 881         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 882         SetCondInst* cond_inst =
 883             new SetCondInst( Instruction::SetGE, op1, op2 );
 884         bb->getInstList().push_back( cond_inst );
 885         push_value( bb, cond_inst );
 886         break;
 887     }
 888     case NOT_EQUAL : // w1 w2 -- w2!=w1
 889     {
 890         if (echo) bb->setName("NE");
 891         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 892         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 893         SetCondInst* cond_inst =
 894             new SetCondInst( Instruction::SetNE, op1, op2 );
 895         bb->getInstList().push_back( cond_inst );
 896         push_value( bb, cond_inst );
 897         break;
 898     }
 899     case EQUAL : // w1 w2 -- w1==w2
 900     {
 901         if (echo) bb->setName("EQ");
 902         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 903         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 904         SetCondInst* cond_inst =
 905             new SetCondInst( Instruction::SetEQ, op1, op2 );
 906         bb->getInstList().push_back( cond_inst );
 907         push_value( bb, cond_inst );
 908         break;
 909     }
 910
 911     // Arithmetic Operations
 912     case PLUS : // w1 w2 -- w2+w1
 913     {
 914         if (echo) bb->setName("ADD");
 915         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 916         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 917         BinaryOperator* addop =
 918             BinaryOperator::create( Instruction::Add, op1, op2);
 919         bb->getInstList().push_back( addop );
 920         push_value( bb, addop );
 921         break;
 922     }
 923     case MINUS : // w1 w2 -- w2-w1
 924     {
 925         if (echo) bb->setName("SUB");
 926         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 927         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 928         BinaryOperator* subop =
 929             BinaryOperator::create( Instruction::Sub, op1, op2);
 930         bb->getInstList().push_back( subop );
 931         push_value( bb, subop );
 932         break;
 933     }
 934     case INCR :  // w1 -- w1+1
 935     {
 936         if (echo) bb->setName("INCR");
 937         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 938         BinaryOperator* addop =
 939             BinaryOperator::create( Instruction::Add, op1, IOne );
 940         bb->getInstList().push_back( addop );
 941         push_value( bb, addop );
 942         break;
 943     }
 944     case DECR : // w1 -- w1-1
 945     {
 946         if (echo) bb->setName("DECR");
 947         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 948         BinaryOperator* subop = BinaryOperator::create( Instruction::Sub, op1,
 949             ConstantSInt::get( Type::IntTy, 1 ) );
 950         bb->getInstList().push_back( subop );
 951         push_value( bb, subop );
 952         break;
 953     }
 954     case MULT : // w1 w2 -- w2*w1
 955     {
 956         if (echo) bb->setName("MUL");
 957         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 958         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 959         BinaryOperator* multop =
 960             BinaryOperator::create( Instruction::Mul, op1, op2);
 961         bb->getInstList().push_back( multop );
 962         push_value( bb, multop );
 963         break;
 964     }
 965     case DIV :// w1 w2 -- w2/w1
 966     {
 967         if (echo) bb->setName("DIV");
 968         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 969         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 970         BinaryOperator* divop =
 971             BinaryOperator::create( Instruction::Div, op1, op2);
 972         bb->getInstList().push_back( divop );
 973         push_value( bb, divop );
 974         break;
 975     }
 976     case MODULUS : // w1 w2 -- w2%w1
 977     {
 978         if (echo) bb->setName("MOD");
 979         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 980         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 981         BinaryOperator* divop =
 982             BinaryOperator::create( Instruction::Rem, op1, op2);
 983         bb->getInstList().push_back( divop );
 984         push_value( bb, divop );
 985         break;
 986     }
 987     case STAR_SLASH : // w1 w2 w3 -- (w3*w2)/w1
 988     {
 989         if (echo) bb->setName("STAR_SLASH");
 990         // Get the operands
 991         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 992         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 993         LoadInst* op3 = cast<LoadInst>(pop_integer(bb));
 994
 995         // Multiply the first two
 996         BinaryOperator* multop =
 997             BinaryOperator::create( Instruction::Mul, op1, op2);
 998         bb->getInstList().push_back( multop );
 999
1000         // Divide by the third operand
1001         BinaryOperator* divop =
1002             BinaryOperator::create( Instruction::Div, multop, op3);
1003         bb->getInstList().push_back( divop );
1004
1005         // Push the result
1006         push_value( bb, divop );
1007
1008         break;
1009     }
1010     case NEGATE : // w1 -- -w1
1011     {
1012         if (echo) bb->setName("NEG");
1013         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1014         // APPARENTLY, the following doesn't work:
1015         // BinaryOperator* negop = BinaryOperator::createNeg( op1 );
1016         // bb->getInstList().push_back( negop );
1017         // So we'll multiply by -1 (ugh)
1018         BinaryOperator* multop = BinaryOperator::create( Instruction::Mul, op1,
1019             ConstantSInt::get( Type::IntTy, -1 ) );
1020         bb->getInstList().push_back( multop );
1021         push_value( bb, multop );
1022         break;
1023     }
1024     case ABS : // w1 -- |w1|
1025     {
1026         if (echo) bb->setName("ABS");
1027         // Get the top of stack value
1028         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1029
1030         // Determine if its negative
1031         SetCondInst* cond_inst =
1032             new SetCondInst( Instruction::SetLT, op1, IZero );
1033         bb->getInstList().push_back( cond_inst );
1034
1035         // Create a block for storing the result
1036         BasicBlock* exit_bb = new BasicBlock((echo?"exit":""));
1037
1038         // Create a block for making it a positive value
1039         BasicBlock* pos_bb = new BasicBlock((echo?"neg":""));
1040
1041         // Create the branch on the SetCond
1042         BranchInst* br_inst = new BranchInst( pos_bb, exit_bb, cond_inst );
1043         bb->getInstList().push_back( br_inst );
1044
1045         // Fill out the negation block
1046         LoadInst* pop_op = cast<LoadInst>( pop_integer(pos_bb) );
1047         BinaryOperator* neg_op = BinaryOperator::createNeg( pop_op );
1048         pos_bb->getInstList().push_back( neg_op );
1049         push_value( pos_bb, neg_op );
1050         pos_bb->getInstList().push_back( new BranchInst( exit_bb ) );
1051
1052         // Add the new blocks in the correct order
1053         add_block( TheFunction, bb );
1054         add_block( TheFunction, pos_bb );
1055         bb = exit_bb;
1056         break;
1057     }
1058     case MIN : // w1 w2 -- (w2<w1?w2:w1)
1059     {
1060         if (echo) bb->setName("MIN");
1061
1062         // Create the three blocks
1063         BasicBlock* exit_bb  = new BasicBlock((echo?"exit":""));
1064         BasicBlock* op1_block = new BasicBlock((echo?"less":""));
1065         BasicBlock* op2_block = new BasicBlock((echo?"more":""));
1066
1067         // Get the two operands
1068         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1069         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1070
1071         // Compare them
1072         SetCondInst* cond_inst =
1073             new SetCondInst( Instruction::SetLT, op1, op2);
1074         bb->getInstList().push_back( cond_inst );
1075
1076         // Create a branch on the SetCond
1077         BranchInst* br_inst =
1078             new BranchInst( op1_block, op2_block, cond_inst );
1079         bb->getInstList().push_back( br_inst );
1080
1081         // Create a block for pushing the first one
1082         push_value(op1_block, op1);
1083         op1_block->getInstList().push_back( new BranchInst( exit_bb ) );
1084
1085         // Create a block for pushing the second one
1086         push_value(op2_block, op2);
1087         op2_block->getInstList().push_back( new BranchInst( exit_bb ) );
1088
1089         // Add the blocks
1090         add_block( TheFunction, bb );
1091         add_block( TheFunction, op1_block );
1092         add_block( TheFunction, op2_block );
1093         bb = exit_bb;
1094         break;
1095     }
1096     case MAX : // w1 w2 -- (w2>w1?w2:w1)
1097     {
1098         if (echo) bb->setName("MAX");
1099         // Get the two operands
1100         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1101         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1102
1103         // Compare them
1104         SetCondInst* cond_inst =
1105             new SetCondInst( Instruction::SetGT, op1, op2);
1106         bb->getInstList().push_back( cond_inst );
1107
1108         // Create an exit block
1109         BasicBlock* exit_bb = new BasicBlock((echo?"exit":""));
1110
1111         // Create a block for pushing the larger one
1112         BasicBlock* op1_block = new BasicBlock((echo?"more":""));
1113         push_value(op1_block, op1);
1114         op1_block->getInstList().push_back( new BranchInst( exit_bb ) );
1115
1116         // Create a block for pushing the smaller or equal one
1117         BasicBlock* op2_block = new BasicBlock((echo?"less":""));
1118         push_value(op2_block, op2);
1119         op2_block->getInstList().push_back( new BranchInst( exit_bb ) );
1120
1121         // Create a banch on the SetCond
1122         BranchInst* br_inst =
1123             new BranchInst( op1_block, op2_block, cond_inst );
1124         bb->getInstList().push_back( br_inst );
1125
1126         // Add the blocks
1127         add_block( TheFunction, bb );
1128         add_block( TheFunction, op1_block );
1129         add_block( TheFunction, op2_block );
1130
1131         bb = exit_bb;
1132         break;
1133     }
1134
1135     // Bitwise Operators
1136     case AND : // w1 w2 -- w2&w1
1137     {
1138         if (echo) bb->setName("AND");
1139         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1140         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1141         BinaryOperator* andop =
1142             BinaryOperator::create( Instruction::And, op1, op2);
1143         bb->getInstList().push_back( andop );
1144         push_value( bb, andop );
1145         break;
1146     }
1147     case OR : // w1 w2 -- w2|w1
1148     {
1149         if (echo) bb->setName("OR");
1150         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1151         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1152         BinaryOperator* orop =
1153             BinaryOperator::create( Instruction::Or, op1, op2);
1154         bb->getInstList().push_back( orop );
1155         push_value( bb, orop );
1156         break;
1157     }
1158     case XOR : // w1 w2 -- w2^w1
1159     {
1160         if (echo) bb->setName("XOR");
1161         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1162         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1163         BinaryOperator* xorop =
1164             BinaryOperator::create( Instruction::Xor, op1, op2);
1165         bb->getInstList().push_back( xorop );
1166         push_value( bb, xorop );
1167         break;
1168     }
1169     case LSHIFT : // w1 w2 -- w1<<w2
1170     {
1171         if (echo) bb->setName("SHL");
1172         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1173         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1174         CastInst* castop = new CastInst( op1, Type::UByteTy );
1175         bb->getInstList().push_back( castop );
1176         ShiftInst* shlop = new ShiftInst( Instruction::Shl, op2, castop );
1177         bb->getInstList().push_back( shlop );
1178         push_value( bb, shlop );
1179         break;
1180     }
1181     case RSHIFT :  // w1 w2 -- w1>>w2
1182     {
1183         if (echo) bb->setName("SHR");
1184         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1185         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1186         CastInst* castop = new CastInst( op1, Type::UByteTy );
1187         bb->getInstList().push_back( castop );
1188         ShiftInst* shrop = new ShiftInst( Instruction::Shr, op2, castop );
1189         bb->getInstList().push_back( shrop );
1190         push_value( bb, shrop );
1191         break;
1192     }
1193
1194     // Stack Manipulation Operations
1195     case DROP:          // w --
1196     {
1197         if (echo) bb->setName("DROP");
1198         decr_stack_index(bb, One);
1199         break;
1200     }
1201     case DROP2: // w1 w2 --
1202     {
1203         if (echo) bb->setName("DROP2");
1204         decr_stack_index( bb, Two );
1205         break;
1206     }
1207     case NIP:   // w1 w2 -- w2
1208     {
1209         if (echo) bb->setName("NIP");
1210         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1211         decr_stack_index( bb  );
1212         replace_top( bb, w2 );
1213         break;
1214     }
1215     case NIP2:  // w1 w2 w3 w4 -- w3 w4
1216     {
1217         if (echo) bb->setName("NIP2");
1218         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1219         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1220         decr_stack_index( bb, Two );
1221         replace_top( bb, w4 );
1222         replace_top( bb, w3, One );
1223         break;
1224     }
1225     case DUP:   // w -- w w
1226     {
1227         if (echo) bb->setName("DUP");
1228         LoadInst* w = cast<LoadInst>( stack_top( bb ) );
1229         push_value( bb, w );
1230         break;
1231     }
1232     case DUP2:  // w1 w2 -- w1 w2 w1 w2
1233     {
1234         if (echo) bb->setName("DUP2");
1235         LoadInst* w2 = cast<LoadInst>( stack_top(bb) );
1236         LoadInst* w1 = cast<LoadInst>( stack_top(bb, One ) );
1237         incr_stack_index( bb, Two );
1238         replace_top( bb, w1, One );
1239         replace_top( bb, w2 );
1240         break;
1241     }
1242     case SWAP:  // w1 w2 -- w2 w1
1243     {
1244         if (echo) bb->setName("SWAP");
1245         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1246         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1247         replace_top( bb, w1 );
1248         replace_top( bb, w2, One );
1249         break;
1250     }
1251     case SWAP2: // w1 w2 w3 w4 -- w3 w4 w1 w2
1252     {
1253         if (echo) bb->setName("SWAP2");
1254         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1255         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1256         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1257         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three ) );
1258         replace_top( bb, w2 );
1259         replace_top( bb, w1, One );
1260         replace_top( bb, w4, Two );
1261         replace_top( bb, w3, Three );
1262         break;
1263     }
1264     case OVER:  // w1 w2 -- w1 w2 w1
1265     {
1266         if (echo) bb->setName("OVER");
1267         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1268         push_value( bb, w1 );
1269         break;
1270     }
1271     case OVER2: // w1 w2 w3 w4 -- w1 w2 w3 w4 w1 w2
1272     {
1273         if (echo) bb->setName("OVER2");
1274         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1275         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three ) );
1276         incr_stack_index( bb, Two );
1277         replace_top( bb, w2 );
1278         replace_top( bb, w1, One );
1279         break;
1280     }
1281     case ROT:   // w1 w2 w3 -- w2 w3 w1
1282     {
1283         if (echo) bb->setName("ROT");
1284         LoadInst* w3 = cast<LoadInst>( stack_top( bb ) );
1285         LoadInst* w2 = cast<LoadInst>( stack_top( bb, One ) );
1286         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Two ) );
1287         replace_top( bb, w1 );
1288         replace_top( bb, w3, One );
1289         replace_top( bb, w2, Two );
1290         break;
1291     }
1292     case ROT2:  // w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2
1293     {
1294         if (echo) bb->setName("ROT2");
1295         LoadInst* w6 = cast<LoadInst>( stack_top( bb ) );
1296         LoadInst* w5 = cast<LoadInst>( stack_top( bb, One ) );
1297         LoadInst* w4 = cast<LoadInst>( stack_top( bb, Two ) );
1298         LoadInst* w3 = cast<LoadInst>( stack_top( bb, Three) );
1299         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Four ) );
1300         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Five ) );
1301         replace_top( bb, w2 );
1302         replace_top( bb, w1, One );
1303         replace_top( bb, w6, Two );
1304         replace_top( bb, w5, Three );
1305         replace_top( bb, w4, Four );
1306         replace_top( bb, w3, Five );
1307         break;
1308     }
1309     case RROT:  // w1 w2 w3 -- w3 w1 w2
1310     {
1311         if (echo) bb->setName("RROT2");
1312         LoadInst* w3 = cast<LoadInst>( stack_top( bb ) );
1313         LoadInst* w2 = cast<LoadInst>( stack_top( bb, One ) );
1314         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Two ) );
1315         replace_top( bb, w2 );
1316         replace_top( bb, w1, One );
1317         replace_top( bb, w3, Two );
1318         break;
1319     }
1320     case RROT2: // w1 w2 w3 w4 w5 w6 -- w5 w6 w1 w2 w3 w4
1321     {
1322         if (echo) bb->setName("RROT2");
1323         LoadInst* w6 = cast<LoadInst>( stack_top( bb ) );
1324         LoadInst* w5 = cast<LoadInst>( stack_top( bb, One ) );
1325         LoadInst* w4 = cast<LoadInst>( stack_top( bb, Two ) );
1326         LoadInst* w3 = cast<LoadInst>( stack_top( bb, Three) );
1327         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Four ) );
1328         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Five ) );
1329         replace_top( bb, w4 );
1330         replace_top( bb, w3, One );
1331         replace_top( bb, w2, Two );
1332         replace_top( bb, w1, Three );
1333         replace_top( bb, w6, Four );
1334         replace_top( bb, w5, Five );
1335         break;
1336     }
1337     case TUCK:  // w1 w2 -- w2 w1 w2
1338     {
1339         if (echo) bb->setName("TUCK");
1340         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1341         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1342         incr_stack_index( bb );
1343         replace_top( bb, w2 );
1344         replace_top( bb, w1, One );
1345         replace_top( bb, w2, Two );
1346         break;
1347     }
1348     case TUCK2: // w1 w2 w3 w4 -- w3 w4 w1 w2 w3 w4
1349     {
1350         if (echo) bb->setName("TUCK2");
1351         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1352         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1353         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1354         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three) );
1355         incr_stack_index( bb, Two );
1356         replace_top( bb, w4 );
1357         replace_top( bb, w3, One );
1358         replace_top( bb, w2, Two );
1359         replace_top( bb, w1, Three );
1360         replace_top( bb, w4, Four );
1361         replace_top( bb, w3, Five );
1362         break;
1363     }
1364     case ROLL:  // x0 x1 .. xn n -- x1 .. xn x0
1365     {
1366         /// THIS OEPRATOR IS OMITTED PURPOSEFULLY AND IS LEFT TO THE
1367         /// READER AS AN EXERCISE. THIS IS ONE OF THE MORE COMPLICATED
1368         /// OPERATORS. IF YOU CAN GET THIS ONE RIGHT, YOU COMPLETELY
1369         /// UNDERSTAND HOW BOTH LLVM AND STACKER WOR.
1370         /// HINT: LOOK AT PICK AND SELECT. ROLL IS SIMILAR.
1371         if (echo) bb->setName("ROLL");
1372         break;
1373     }
1374     case PICK:  // x0 ... Xn n -- x0 ... Xn x0
1375     {
1376         if (echo) bb->setName("PICK");
1377         LoadInst* n = cast<LoadInst>( stack_top( bb ) );
1378         BinaryOperator* addop =
1379             BinaryOperator::create( Instruction::Add, n, IOne );
1380         bb->getInstList().push_back( addop );
1381         LoadInst* x0 = cast<LoadInst>( stack_top( bb, addop ) );
1382         replace_top( bb, x0 );
1383         break;
1384     }
1385     case SELECT:        // m n X0..Xm Xm+1 .. Xn -- Xm
1386     {
1387         if (echo) bb->setName("SELECT");
1388         LoadInst* m = cast<LoadInst>( stack_top(bb) );
1389         LoadInst* n = cast<LoadInst>( stack_top(bb, One) );
1390         BinaryOperator* index =
1391             BinaryOperator::create( Instruction::Add, m, IOne );
1392         bb->getInstList().push_back( index );
1393         LoadInst* Xm = cast<LoadInst>( stack_top(bb, index ) );
1394         BinaryOperator* n_plus_1 =
1395             BinaryOperator::create( Instruction::Add, n, IOne );
1396         bb->getInstList().push_back( n_plus_1 );
1397         decr_stack_index( bb, n_plus_1 );
1398         replace_top( bb, Xm );
1399         break;
1400     }
1401     case MALLOC : // n -- p
1402     {
1403         if (echo) bb->setName("MALLOC");
1404         // Get the number of bytes to mallocate
1405         LoadInst* op1 = cast<LoadInst>( pop_integer(bb) );
1406
1407         // Make sure its a UIntTy
1408         CastInst* caster = new CastInst( op1, Type::UIntTy );
1409         bb->getInstList().push_back( caster );
1410
1411         // Allocate the bytes
1412         MallocInst* mi = new MallocInst( Type::SByteTy, caster );
1413         bb->getInstList().push_back( mi );
1414
1415         // Push the pointer
1416         push_value( bb, mi );
1417         break;
1418     }
1419     case FREE :  // p --
1420     {
1421         if (echo) bb->setName("FREE");
1422         // Pop the value off the stack
1423         CastInst* ptr = cast<CastInst>( pop_string(bb) );
1424
1425         // Free the memory
1426         FreeInst* fi = new FreeInst( ptr );
1427         bb->getInstList().push_back( fi );
1428
1429         break;
1430     }
1431     case GET : // p w1 -- p w2
1432     {
1433         if (echo) bb->setName("GET");
1434         // Get the character index
1435         LoadInst* op1 = cast<LoadInst>( stack_top(bb) );
1436         CastInst* chr_idx = new CastInst( op1, Type::LongTy );
1437         bb->getInstList().push_back( chr_idx );
1438
1439         // Get the String pointer
1440         CastInst* ptr = cast<CastInst>( stack_top_string(bb,One) );
1441
1442         // Get address of op1'th element of the string
1443         std::vector<Value*> indexVec;
1444         indexVec.push_back( chr_idx );
1445         GetElementPtrInst* gep = new GetElementPtrInst( ptr, indexVec );
1446         bb->getInstList().push_back( gep );
1447
1448         // Get the value and push it
1449         LoadInst* loader = new LoadInst( gep );
1450         bb->getInstList().push_back( loader );
1451         CastInst* caster = new CastInst( loader, Type::IntTy );
1452         bb->getInstList().push_back( caster );
1453
1454         // Push the result back on stack
1455         replace_top( bb, caster );
1456
1457         break;
1458     }
1459     case PUT : // p w2 w1  -- p
1460     {
1461         if (echo) bb->setName("PUT");
1462
1463         // Get the value to put
1464         LoadInst* w1 = cast<LoadInst>( pop_integer(bb) );
1465
1466         // Get the character index
1467         LoadInst* w2 = cast<LoadInst>( pop_integer(bb) );
1468         CastInst* chr_idx = new CastInst( w2, Type::LongTy );
1469         bb->getInstList().push_back( chr_idx );
1470
1471         // Get the String pointer
1472         CastInst* ptr = cast<CastInst>( stack_top_string(bb) );
1473
1474         // Get address of op2'th element of the string
1475         std::vector<Value*> indexVec;
1476         indexVec.push_back( chr_idx );
1477         GetElementPtrInst* gep = new GetElementPtrInst( ptr, indexVec );
1478         bb->getInstList().push_back( gep );
1479
1480         // Cast the value and put it
1481         CastInst* caster = new CastInst( w1, Type::SByteTy );
1482         bb->getInstList().push_back( caster );
1483         StoreInst* storer = new StoreInst( caster, gep );
1484         bb->getInstList().push_back( storer );
1485
1486         break;
1487     }
1488     case RECURSE :
1489     {
1490         if (echo) bb->setName("RECURSE");
1491         std::vector<Value*> params;
1492         CallInst* call_inst = new CallInst( TheFunction, params );
1493         bb->getInstList().push_back( call_inst );
1494         break;
1495     }
1496     case RETURN :
1497     {
1498         if (echo) bb->setName("RETURN");
1499         bb->getInstList().push_back( new ReturnInst() );
1500         break;
1501     }
1502     case EXIT :
1503     {
1504         if (echo) bb->setName("EXIT");
1505         // Get the result value
1506         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1507
1508         // Call exit(3)
1509         std::vector<Value*> params;
1510         params.push_back(op1);
1511         CallInst* call_inst = new CallInst( TheExit, params );
1512         bb->getInstList().push_back( call_inst );
1513         break;
1514     }
1515     case TAB :
1516     {
1517         if (echo) bb->setName("TAB");
1518         // Get the format string for a character
1519         std::vector<Value*> indexVec;
1520         indexVec.push_back( Zero );
1521         indexVec.push_back( Zero );
1522         GetElementPtrInst* format_gep =
1523             new GetElementPtrInst( ChrFormat, indexVec );
1524         bb->getInstList().push_back( format_gep );
1525
1526         // Get the character to print (a newline)
1527         ConstantSInt* newline = ConstantSInt::get(Type::IntTy,
1528             static_cast<int>('\t'));
1529
1530         // Call printf
1531         std::vector<Value*> args;
1532         args.push_back( format_gep );
1533         args.push_back( newline );
1534         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1535         break;
1536     }
1537     case SPACE :
1538     {
1539         if (echo) bb->setName("SPACE");
1540         // Get the format string for a character
1541         std::vector<Value*> indexVec;
1542         indexVec.push_back( Zero );
1543         indexVec.push_back( Zero );
1544         GetElementPtrInst* format_gep =
1545             new GetElementPtrInst( ChrFormat, indexVec );
1546         bb->getInstList().push_back( format_gep );
1547
1548         // Get the character to print (a newline)
1549         ConstantSInt* newline = ConstantSInt::get(Type::IntTy,
1550             static_cast<int>(' '));
1551
1552         // Call printf
1553         std::vector<Value*> args;
1554         args.push_back( format_gep );
1555         args.push_back( newline );
1556         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1557         break;
1558     }
1559     case CR :
1560     {
1561         if (echo) bb->setName("CR");
1562         // Get the format string for a character
1563         std::vector<Value*> indexVec;
1564         indexVec.push_back( Zero );
1565         indexVec.push_back( Zero );
1566         GetElementPtrInst* format_gep =
1567             new GetElementPtrInst( ChrFormat, indexVec );
1568         bb->getInstList().push_back( format_gep );
1569
1570         // Get the character to print (a newline)
1571         ConstantSInt* newline = ConstantSInt::get(Type::IntTy,
1572             static_cast<int>('\n'));
1573
1574         // Call printf
1575         std::vector<Value*> args;
1576         args.push_back( format_gep );
1577         args.push_back( newline );
1578         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1579         break;
1580     }
1581     case IN_STR :
1582     {
1583         if (echo) bb->setName("IN_STR");
1584         // Make room for the value result
1585         incr_stack_index(bb);
1586         GetElementPtrInst* gep_value =
1587             cast<GetElementPtrInst>(get_stack_pointer(bb));
1588         CastInst* caster =
1589             new CastInst( gep_value, PointerType::get( Type::SByteTy ) );
1590
1591         // Make room for the count result
1592         incr_stack_index(bb);
1593         GetElementPtrInst* gep_count =
1594             cast<GetElementPtrInst>(get_stack_pointer(bb));
1595
1596         // Call scanf(3)
1597         std::vector<Value*> args;
1598         args.push_back( InStrFormat );
1599         args.push_back( caster );
1600         CallInst* scanf = new CallInst( TheScanf, args );
1601         bb->getInstList().push_back( scanf );
1602
1603         // Store the result
1604         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1605         break;
1606     }
1607     case IN_NUM :
1608     {
1609         if (echo) bb->setName("IN_NUM");
1610         // Make room for the value result
1611         incr_stack_index(bb);
1612         GetElementPtrInst* gep_value =
1613             cast<GetElementPtrInst>(get_stack_pointer(bb));
1614
1615         // Make room for the count result
1616         incr_stack_index(bb);
1617         GetElementPtrInst* gep_count =
1618             cast<GetElementPtrInst>(get_stack_pointer(bb));
1619
1620         // Call scanf(3)
1621         std::vector<Value*> args;
1622         args.push_back( InStrFormat );
1623         args.push_back( gep_value );
1624         CallInst* scanf = new CallInst( TheScanf, args );
1625         bb->getInstList().push_back( scanf );
1626
1627         // Store the result
1628         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1629         break;
1630     }
1631     case IN_CHAR :
1632     {
1633         if (echo) bb->setName("IN_CHAR");
1634         // Make room for the value result
1635         incr_stack_index(bb);
1636         GetElementPtrInst* gep_value =
1637             cast<GetElementPtrInst>(get_stack_pointer(bb));
1638
1639         // Make room for the count result
1640         incr_stack_index(bb);
1641         GetElementPtrInst* gep_count =
1642             cast<GetElementPtrInst>(get_stack_pointer(bb));
1643
1644         // Call scanf(3)
1645         std::vector<Value*> args;
1646         args.push_back( InChrFormat );
1647         args.push_back( gep_value );
1648         CallInst* scanf = new CallInst( TheScanf, args );
1649         bb->getInstList().push_back( scanf );
1650
1651         // Store the result
1652         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1653         break;
1654     }
1655     case OUT_STR :
1656     {
1657         if (echo) bb->setName("OUT_STR");
1658         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1659
1660         // Get the address of the format string
1661         std::vector<Value*> indexVec;
1662         indexVec.push_back( Zero );
1663         indexVec.push_back( Zero );
1664         GetElementPtrInst* format_gep =
1665             new GetElementPtrInst( StrFormat, indexVec );
1666         bb->getInstList().push_back( format_gep );
1667         // Build function call arguments
1668         std::vector<Value*> args;
1669         args.push_back( format_gep );
1670         args.push_back( op1 );
1671         // Call printf
1672         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1673         break;
1674     }
1675     case OUT_NUM :
1676     {
1677         if (echo) bb->setName("OUT_NUM");
1678         // Pop the numeric operand off the stack
1679         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1680
1681         // Get the address of the format string
1682         std::vector<Value*> indexVec;
1683         indexVec.push_back( Zero );
1684         indexVec.push_back( Zero );
1685         GetElementPtrInst* format_gep =
1686             new GetElementPtrInst( NumFormat, indexVec );
1687         bb->getInstList().push_back( format_gep );
1688
1689         // Build function call arguments
1690         std::vector<Value*> args;
1691         args.push_back( format_gep );
1692         args.push_back( op1 );
1693
1694         // Call printf
1695         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1696         break;
1697     }
1698     case OUT_CHAR :
1699     {
1700         if (echo) bb->setName("OUT_CHAR");
1701         // Pop the character operand off the stack
1702         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1703
1704         // Get the address of the format string
1705         std::vector<Value*> indexVec;
1706         indexVec.push_back( Zero );
1707         indexVec.push_back( Zero );
1708         GetElementPtrInst* format_gep =
1709             new GetElementPtrInst( ChrFormat, indexVec );
1710         bb->getInstList().push_back( format_gep );
1711
1712         // Build function call arguments
1713         std::vector<Value*> args;
1714         args.push_back( format_gep );
1715         args.push_back( op1 );
1716         // Call printf
1717         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1718         break;
1719     }
1720     default :
1721     {
1722         ThrowException(std::string("Compiler Error: Unhandled token #"));
1723     }
1724     }
1725
1726     // Return the basic block
1727     return bb;
1728 }