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::LinkOnceLinkage,
 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         Constant* 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         Constant* 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         Constant* 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         Constant* 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         Constant* 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         Constant* 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     Constant* 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     // This will get called by the "main" that is defined in
 563     // the runtime library.
 564     func->setName( "_MAIN_");
 565
 566     // Turn "_stack_" into an initialized variable since this is the main
 567     // module. This causes it to not be "external" but defined in this module.
 568     TheStack->setInitializer( Constant::getNullValue(stack_type) );
 569     TheStack->setLinkage( GlobalValue::LinkOnceLinkage );
 570
 571     // Turn "_index_" into an intialized variable for the same reason.
 572     TheIndex->setInitializer( Constant::getNullValue(Type::LongTy) );
 573     TheIndex->setLinkage( GlobalValue::LinkOnceLinkage );
 574
 575     return func;
 576 }
 577
 578 Function*
 579 StackerCompiler::handle_forward( char * name )
 580 {
 581     // Just create a placeholder function
 582     Function* the_function = new Function (
 583         DefinitionType,
 584         GlobalValue::ExternalLinkage,
 585         name );
 586     assert( the_function->isExternal() );
 587
 588     free( name );
 589     return the_function;
 590 }
 591
 592 Function*
 593 StackerCompiler::handle_definition( char * name, Function* f )
 594 {
 595     // Look up the function name in the module to see if it was forward
 596     // declared.
 597     Function* existing_function = TheModule->getNamedFunction( name );
 598
 599 #if 0
 600     // If the function already exists...
 601     if ( existing_function )
 602     {
 603         // Just get rid of the placeholder
 604         existing_function->dropAllReferences();
 605         delete existing_function;
 606     }
 607 #endif
 608
 609     // Just set the name of the function now that we know what it is.
 610     f->setName( name );
 611
 612     free( name );
 613
 614     return f;
 615 }
 616
 617 Function*
 618 StackerCompiler::handle_word_list_start()
 619 {
 620     TheFunction = new Function(DefinitionType, GlobalValue::ExternalLinkage);
 621     return TheFunction;
 622 }
 623
 624 Function*
 625 StackerCompiler::handle_word_list_end( Function* f, BasicBlock* bb )
 626 {
 627     add_block( f, bb );
 628     return f;
 629 }
 630
 631 BasicBlock*
 632 StackerCompiler::handle_if( char* ifTrue, char* ifFalse )
 633 {
 634     // Create a basic block for the preamble
 635     BasicBlock* bb = new BasicBlock((echo?"if":""));
 636
 637     // Get the condition value
 638     LoadInst* cond = cast<LoadInst>( pop_integer(bb) );
 639
 640     // Compare the condition against 0
 641     SetCondInst* cond_inst = new SetCondInst( Instruction::SetNE, cond,
 642         ConstantSInt::get( Type::IntTy, 0) );
 643     bb->getInstList().push_back( cond_inst );
 644
 645     // Create an exit block
 646     BasicBlock* exit_bb = new BasicBlock((echo?"endif":""));
 647
 648     // Create the true_block
 649     BasicBlock* true_bb = new BasicBlock((echo?"then":""));
 650
 651     // Create the false_block
 652     BasicBlock* false_bb = 0;
 653     if ( ifFalse ) false_bb = new BasicBlock((echo?"else":""));
 654
 655     // Create a branch on the SetCond
 656     BranchInst* br_inst = new BranchInst( true_bb,
 657         ( ifFalse ? false_bb : exit_bb ), cond_inst );
 658     bb->getInstList().push_back( br_inst );
 659
 660     // Fill the true block
 661     std::vector<Value*> args;
 662     if ( Function* true_func = TheModule->getNamedFunction(ifTrue) )
 663     {
 664         true_bb->getInstList().push_back(
 665                 new CallInst( true_func, args ) );
 666         true_bb->getInstList().push_back(
 667                 new BranchInst( exit_bb ) );
 668     }
 669     else
 670     {
 671         ThrowException(std::string("Function '") + ifTrue +
 672             "' must be declared first.'");
 673     }
 674
 675     free( ifTrue );
 676
 677     // Fill the false block
 678     if ( false_bb )
 679     {
 680         if ( Function* false_func = TheModule->getNamedFunction(ifFalse) )
 681         {
 682             false_bb->getInstList().push_back(
 683                     new CallInst( false_func, args ) );
 684             false_bb->getInstList().push_back(
 685                     new BranchInst( exit_bb ) );
 686         }
 687         else
 688         {
 689             ThrowException(std::string("Function '") + ifFalse +
 690                     "' must be declared first.'");
 691         }
 692         free( ifFalse );
 693     }
 694
 695     // Add the blocks to the function
 696     add_block( TheFunction, bb );
 697     add_block( TheFunction, true_bb );
 698     if ( false_bb ) add_block( TheFunction, false_bb );
 699
 700     return exit_bb;
 701 }
 702
 703 BasicBlock*
 704 StackerCompiler::handle_while( char* todo )
 705 {
 706
 707     // Create a basic block for the loop test
 708     BasicBlock* test = new BasicBlock((echo?"while":""));
 709
 710     // Create an exit block
 711     BasicBlock* exit = new BasicBlock((echo?"end":""));
 712
 713     // Create a loop body block
 714     BasicBlock* body = new BasicBlock((echo?"do":""));
 715
 716     // Create a root node
 717     BasicBlock* bb = new BasicBlock((echo?"root":""));
 718     BranchInst* root_br_inst = new BranchInst( test );
 719     bb->getInstList().push_back( root_br_inst );
 720
 721     // Pop the condition value
 722     LoadInst* cond = cast<LoadInst>( stack_top(test) );
 723
 724     // Compare the condition against 0
 725     SetCondInst* cond_inst = new SetCondInst(
 726         Instruction::SetNE, cond, ConstantSInt::get( Type::IntTy, 0) );
 727     test->getInstList().push_back( cond_inst );
 728
 729     // Add the branch instruction
 730     BranchInst* br_inst = new BranchInst( body, exit, cond_inst );
 731     test->getInstList().push_back( br_inst );
 732
 733     // Fill in the body
 734     std::vector<Value*> args;
 735     if ( Function* body_func = TheModule->getNamedFunction(todo) )
 736     {
 737         body->getInstList().push_back( new CallInst( body_func, args ) );
 738         body->getInstList().push_back( new BranchInst( test ) );
 739     }
 740     else
 741     {
 742         ThrowException(std::string("Function '") + todo +
 743             "' must be declared first.'");
 744     }
 745
 746     free( todo );
 747
 748     // Add the blocks
 749     add_block( TheFunction, bb );
 750     add_block( TheFunction, test );
 751     add_block( TheFunction, body );
 752
 753     return exit;
 754 }
 755
 756 BasicBlock*
 757 StackerCompiler::handle_identifier( char * name )
 758 {
 759     Function* func = TheModule->getNamedFunction( name );
 760     BasicBlock* bb = new BasicBlock((echo?"call":""));
 761     if ( func )
 762     {
 763         CallInst* call_def = new CallInst( func , no_arguments );
 764         bb->getInstList().push_back( call_def );
 765     }
 766     else
 767     {
 768         ThrowException(std::string("Definition '") + name +
 769             "' must be defined before it can be used.");
 770     }
 771
 772     free( name );
 773     return bb;
 774 }
 775
 776 BasicBlock*
 777 StackerCompiler::handle_string( char * value )
 778 {
 779     // Create a new basic block for the push operation
 780     BasicBlock* bb = new BasicBlock((echo?"string":""));
 781
 782     // Push the string onto the stack
 783     push_string(bb, value);
 784
 785     // Free the strdup'd string
 786     free( value );
 787
 788     return bb;
 789 }
 790
 791 BasicBlock*
 792 StackerCompiler::handle_integer( const int32_t value )
 793 {
 794     // Create a new basic block for the push operation
 795     BasicBlock* bb = new BasicBlock((echo?"int":""));
 796
 797     // Push the integer onto the stack
 798     push_integer(bb, value );
 799
 800     return bb;
 801 }
 802
 803 BasicBlock*
 804 StackerCompiler::handle_word( int tkn )
 805 {
 806     // Create a new basic block to hold the instruction(s)
 807     BasicBlock* bb = new BasicBlock();
 808
 809     /* Fill the basic block with the appropriate instructions */
 810     switch ( tkn )
 811     {
 812     case DUMP :  // Dump the stack (debugging aid)
 813     {
 814         if (echo) bb->setName("DUMP");
 815         Function* f = TheModule->getOrInsertFunction(
 816             "_stacker_dump_stack_", DefinitionType);
 817         std::vector<Value*> args;
 818         bb->getInstList().push_back( new CallInst( f, args ) );
 819         break;
 820     }
 821
 822     // Logical Operations
 823     case TRUE :  // -- -1
 824     {
 825         if (echo) bb->setName("TRUE");
 826         push_integer(bb,-1);
 827         break;
 828     }
 829     case FALSE : // -- 0
 830     {
 831         if (echo) bb->setName("FALSE");
 832         push_integer(bb,0);
 833         break;
 834     }
 835     case LESS : // w1 w2 -- w2<w1
 836     {
 837         if (echo) bb->setName("LESS");
 838         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 839         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 840         SetCondInst* cond_inst =
 841             new SetCondInst( Instruction::SetLT, op1, op2 );
 842         bb->getInstList().push_back( cond_inst );
 843         push_value( bb, cond_inst );
 844         break;
 845     }
 846     case MORE : // w1 w2 -- w2>w1
 847     {
 848         if (echo) bb->setName("MORE");
 849         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 850         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 851         SetCondInst* cond_inst =
 852             new SetCondInst( Instruction::SetGT, op1, op2 );
 853         bb->getInstList().push_back( cond_inst );
 854         push_value( bb, cond_inst );
 855         break;
 856     }
 857     case LESS_EQUAL : // w1 w2 -- w2<=w1
 858     {
 859         if (echo) bb->setName("LE");
 860         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 861         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 862         SetCondInst* cond_inst =
 863             new SetCondInst( Instruction::SetLE, op1, op2 );
 864         bb->getInstList().push_back( cond_inst );
 865         push_value( bb, cond_inst );
 866         break;
 867     }
 868     case MORE_EQUAL : // w1 w2 -- w2>=w1
 869     {
 870         if (echo) bb->setName("GE");
 871         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 872         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 873         SetCondInst* cond_inst =
 874             new SetCondInst( Instruction::SetGE, op1, op2 );
 875         bb->getInstList().push_back( cond_inst );
 876         push_value( bb, cond_inst );
 877         break;
 878     }
 879     case NOT_EQUAL : // w1 w2 -- w2!=w1
 880     {
 881         if (echo) bb->setName("NE");
 882         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 883         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 884         SetCondInst* cond_inst =
 885             new SetCondInst( Instruction::SetNE, op1, op2 );
 886         bb->getInstList().push_back( cond_inst );
 887         push_value( bb, cond_inst );
 888         break;
 889     }
 890     case EQUAL : // w1 w2 -- w1==w2
 891     {
 892         if (echo) bb->setName("EQ");
 893         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 894         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 895         SetCondInst* cond_inst =
 896             new SetCondInst( Instruction::SetEQ, op1, op2 );
 897         bb->getInstList().push_back( cond_inst );
 898         push_value( bb, cond_inst );
 899         break;
 900     }
 901
 902     // Arithmetic Operations
 903     case PLUS : // w1 w2 -- w2+w1
 904     {
 905         if (echo) bb->setName("ADD");
 906         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 907         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 908         BinaryOperator* addop =
 909             BinaryOperator::create( Instruction::Add, op1, op2);
 910         bb->getInstList().push_back( addop );
 911         push_value( bb, addop );
 912         break;
 913     }
 914     case MINUS : // w1 w2 -- w2-w1
 915     {
 916         if (echo) bb->setName("SUB");
 917         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 918         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 919         BinaryOperator* subop =
 920             BinaryOperator::create( Instruction::Sub, op1, op2);
 921         bb->getInstList().push_back( subop );
 922         push_value( bb, subop );
 923         break;
 924     }
 925     case INCR :  // w1 -- w1+1
 926     {
 927         if (echo) bb->setName("INCR");
 928         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 929         BinaryOperator* addop =
 930             BinaryOperator::create( Instruction::Add, op1, IOne );
 931         bb->getInstList().push_back( addop );
 932         push_value( bb, addop );
 933         break;
 934     }
 935     case DECR : // w1 -- w1-1
 936     {
 937         if (echo) bb->setName("DECR");
 938         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 939         BinaryOperator* subop = BinaryOperator::create( Instruction::Sub, op1,
 940             ConstantSInt::get( Type::IntTy, 1 ) );
 941         bb->getInstList().push_back( subop );
 942         push_value( bb, subop );
 943         break;
 944     }
 945     case MULT : // w1 w2 -- w2*w1
 946     {
 947         if (echo) bb->setName("MUL");
 948         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 949         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 950         BinaryOperator* multop =
 951             BinaryOperator::create( Instruction::Mul, op1, op2);
 952         bb->getInstList().push_back( multop );
 953         push_value( bb, multop );
 954         break;
 955     }
 956     case DIV :// w1 w2 -- w2/w1
 957     {
 958         if (echo) bb->setName("DIV");
 959         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 960         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 961         BinaryOperator* divop =
 962             BinaryOperator::create( Instruction::Div, op1, op2);
 963         bb->getInstList().push_back( divop );
 964         push_value( bb, divop );
 965         break;
 966     }
 967     case MODULUS : // w1 w2 -- w2%w1
 968     {
 969         if (echo) bb->setName("MOD");
 970         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 971         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 972         BinaryOperator* divop =
 973             BinaryOperator::create( Instruction::Rem, op1, op2);
 974         bb->getInstList().push_back( divop );
 975         push_value( bb, divop );
 976         break;
 977     }
 978     case STAR_SLASH : // w1 w2 w3 -- (w3*w2)/w1
 979     {
 980         if (echo) bb->setName("STAR_SLASH");
 981         // Get the operands
 982         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 983         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 984         LoadInst* op3 = cast<LoadInst>(pop_integer(bb));
 985
 986         // Multiply the first two
 987         BinaryOperator* multop =
 988             BinaryOperator::create( Instruction::Mul, op1, op2);
 989         bb->getInstList().push_back( multop );
 990
 991         // Divide by the third operand
 992         BinaryOperator* divop =
 993             BinaryOperator::create( Instruction::Div, multop, op3);
 994         bb->getInstList().push_back( divop );
 995
 996         // Push the result
 997         push_value( bb, divop );
 998
 999         break;
1000     }
1001     case NEGATE : // w1 -- -w1
1002     {
1003         if (echo) bb->setName("NEG");
1004         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1005         // APPARENTLY, the following doesn't work:
1006         // BinaryOperator* negop = BinaryOperator::createNeg( op1 );
1007         // bb->getInstList().push_back( negop );
1008         // So we'll multiply by -1 (ugh)
1009         BinaryOperator* multop = BinaryOperator::create( Instruction::Mul, op1,
1010             ConstantSInt::get( Type::IntTy, -1 ) );
1011         bb->getInstList().push_back( multop );
1012         push_value( bb, multop );
1013         break;
1014     }
1015     case ABS : // w1 -- |w1|
1016     {
1017         if (echo) bb->setName("ABS");
1018         // Get the top of stack value
1019         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1020
1021         // Determine if its negative
1022         SetCondInst* cond_inst =
1023             new SetCondInst( Instruction::SetLT, op1, IZero );
1024         bb->getInstList().push_back( cond_inst );
1025
1026         // Create a block for storing the result
1027         BasicBlock* exit_bb = new BasicBlock((echo?"exit":""));
1028
1029         // Create a block for making it a positive value
1030         BasicBlock* pos_bb = new BasicBlock((echo?"neg":""));
1031
1032         // Create the branch on the SetCond
1033         BranchInst* br_inst = new BranchInst( pos_bb, exit_bb, cond_inst );
1034         bb->getInstList().push_back( br_inst );
1035
1036         // Fill out the negation block
1037         LoadInst* pop_op = cast<LoadInst>( pop_integer(pos_bb) );
1038         BinaryOperator* neg_op = BinaryOperator::createNeg( pop_op );
1039         pos_bb->getInstList().push_back( neg_op );
1040         push_value( pos_bb, neg_op );
1041         pos_bb->getInstList().push_back( new BranchInst( exit_bb ) );
1042
1043         // Add the new blocks in the correct order
1044         add_block( TheFunction, bb );
1045         add_block( TheFunction, pos_bb );
1046         bb = exit_bb;
1047         break;
1048     }
1049     case MIN : // w1 w2 -- (w2<w1?w2:w1)
1050     {
1051         if (echo) bb->setName("MIN");
1052
1053         // Create the three blocks
1054         BasicBlock* exit_bb  = new BasicBlock((echo?"exit":""));
1055         BasicBlock* op1_block = new BasicBlock((echo?"less":""));
1056         BasicBlock* op2_block = new BasicBlock((echo?"more":""));
1057
1058         // Get the two operands
1059         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1060         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1061
1062         // Compare them
1063         SetCondInst* cond_inst =
1064             new SetCondInst( Instruction::SetLT, op1, op2);
1065         bb->getInstList().push_back( cond_inst );
1066
1067         // Create a branch on the SetCond
1068         BranchInst* br_inst =
1069             new BranchInst( op1_block, op2_block, cond_inst );
1070         bb->getInstList().push_back( br_inst );
1071
1072         // Create a block for pushing the first one
1073         push_value(op1_block, op1);
1074         op1_block->getInstList().push_back( new BranchInst( exit_bb ) );
1075
1076         // Create a block for pushing the second one
1077         push_value(op2_block, op2);
1078         op2_block->getInstList().push_back( new BranchInst( exit_bb ) );
1079
1080         // Add the blocks
1081         add_block( TheFunction, bb );
1082         add_block( TheFunction, op1_block );
1083         add_block( TheFunction, op2_block );
1084         bb = exit_bb;
1085         break;
1086     }
1087     case MAX : // w1 w2 -- (w2>w1?w2:w1)
1088     {
1089         if (echo) bb->setName("MAX");
1090         // Get the two operands
1091         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1092         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1093
1094         // Compare them
1095         SetCondInst* cond_inst =
1096             new SetCondInst( Instruction::SetGT, op1, op2);
1097         bb->getInstList().push_back( cond_inst );
1098
1099         // Create an exit block
1100         BasicBlock* exit_bb = new BasicBlock((echo?"exit":""));
1101
1102         // Create a block for pushing the larger one
1103         BasicBlock* op1_block = new BasicBlock((echo?"more":""));
1104         push_value(op1_block, op1);
1105         op1_block->getInstList().push_back( new BranchInst( exit_bb ) );
1106
1107         // Create a block for pushing the smaller or equal one
1108         BasicBlock* op2_block = new BasicBlock((echo?"less":""));
1109         push_value(op2_block, op2);
1110         op2_block->getInstList().push_back( new BranchInst( exit_bb ) );
1111
1112         // Create a banch on the SetCond
1113         BranchInst* br_inst =
1114             new BranchInst( op1_block, op2_block, cond_inst );
1115         bb->getInstList().push_back( br_inst );
1116
1117         // Add the blocks
1118         add_block( TheFunction, bb );
1119         add_block( TheFunction, op1_block );
1120         add_block( TheFunction, op2_block );
1121
1122         bb = exit_bb;
1123         break;
1124     }
1125
1126     // Bitwise Operators
1127     case AND : // w1 w2 -- w2&w1
1128     {
1129         if (echo) bb->setName("AND");
1130         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1131         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1132         BinaryOperator* andop =
1133             BinaryOperator::create( Instruction::And, op1, op2);
1134         bb->getInstList().push_back( andop );
1135         push_value( bb, andop );
1136         break;
1137     }
1138     case OR : // w1 w2 -- w2|w1
1139     {
1140         if (echo) bb->setName("OR");
1141         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1142         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1143         BinaryOperator* orop =
1144             BinaryOperator::create( Instruction::Or, op1, op2);
1145         bb->getInstList().push_back( orop );
1146         push_value( bb, orop );
1147         break;
1148     }
1149     case XOR : // w1 w2 -- w2^w1
1150     {
1151         if (echo) bb->setName("XOR");
1152         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1153         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1154         BinaryOperator* xorop =
1155             BinaryOperator::create( Instruction::Xor, op1, op2);
1156         bb->getInstList().push_back( xorop );
1157         push_value( bb, xorop );
1158         break;
1159     }
1160     case LSHIFT : // w1 w2 -- w1<<w2
1161     {
1162         if (echo) bb->setName("SHL");
1163         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1164         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1165         CastInst* castop = new CastInst( op1, Type::UByteTy );
1166         bb->getInstList().push_back( castop );
1167         ShiftInst* shlop = new ShiftInst( Instruction::Shl, op2, castop );
1168         bb->getInstList().push_back( shlop );
1169         push_value( bb, shlop );
1170         break;
1171     }
1172     case RSHIFT :  // w1 w2 -- w1>>w2
1173     {
1174         if (echo) bb->setName("SHR");
1175         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1176         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1177         CastInst* castop = new CastInst( op1, Type::UByteTy );
1178         bb->getInstList().push_back( castop );
1179         ShiftInst* shrop = new ShiftInst( Instruction::Shr, op2, castop );
1180         bb->getInstList().push_back( shrop );
1181         push_value( bb, shrop );
1182         break;
1183     }
1184
1185     // Stack Manipulation Operations
1186     case DROP:          // w --
1187     {
1188         if (echo) bb->setName("DROP");
1189         decr_stack_index(bb, One);
1190         break;
1191     }
1192     case DROP2: // w1 w2 --
1193     {
1194         if (echo) bb->setName("DROP2");
1195         decr_stack_index( bb, Two );
1196         break;
1197     }
1198     case NIP:   // w1 w2 -- w2
1199     {
1200         if (echo) bb->setName("NIP");
1201         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1202         decr_stack_index( bb  );
1203         replace_top( bb, w2 );
1204         break;
1205     }
1206     case NIP2:  // w1 w2 w3 w4 -- w3 w4
1207     {
1208         if (echo) bb->setName("NIP2");
1209         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1210         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1211         decr_stack_index( bb, Two );
1212         replace_top( bb, w4 );
1213         replace_top( bb, w3, One );
1214         break;
1215     }
1216     case DUP:   // w -- w w
1217     {
1218         if (echo) bb->setName("DUP");
1219         LoadInst* w = cast<LoadInst>( stack_top( bb ) );
1220         push_value( bb, w );
1221         break;
1222     }
1223     case DUP2:  // w1 w2 -- w1 w2 w1 w2
1224     {
1225         if (echo) bb->setName("DUP2");
1226         LoadInst* w2 = cast<LoadInst>( stack_top(bb) );
1227         LoadInst* w1 = cast<LoadInst>( stack_top(bb, One ) );
1228         incr_stack_index( bb, Two );
1229         replace_top( bb, w1, One );
1230         replace_top( bb, w2 );
1231         break;
1232     }
1233     case SWAP:  // w1 w2 -- w2 w1
1234     {
1235         if (echo) bb->setName("SWAP");
1236         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1237         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1238         replace_top( bb, w1 );
1239         replace_top( bb, w2, One );
1240         break;
1241     }
1242     case SWAP2: // w1 w2 w3 w4 -- w3 w4 w1 w2
1243     {
1244         if (echo) bb->setName("SWAP2");
1245         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1246         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1247         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1248         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three ) );
1249         replace_top( bb, w2 );
1250         replace_top( bb, w1, One );
1251         replace_top( bb, w4, Two );
1252         replace_top( bb, w3, Three );
1253         break;
1254     }
1255     case OVER:  // w1 w2 -- w1 w2 w1
1256     {
1257         if (echo) bb->setName("OVER");
1258         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1259         push_value( bb, w1 );
1260         break;
1261     }
1262     case OVER2: // w1 w2 w3 w4 -- w1 w2 w3 w4 w1 w2
1263     {
1264         if (echo) bb->setName("OVER2");
1265         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1266         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three ) );
1267         incr_stack_index( bb, Two );
1268         replace_top( bb, w2 );
1269         replace_top( bb, w1, One );
1270         break;
1271     }
1272     case ROT:   // w1 w2 w3 -- w2 w3 w1
1273     {
1274         if (echo) bb->setName("ROT");
1275         LoadInst* w3 = cast<LoadInst>( stack_top( bb ) );
1276         LoadInst* w2 = cast<LoadInst>( stack_top( bb, One ) );
1277         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Two ) );
1278         replace_top( bb, w1 );
1279         replace_top( bb, w3, One );
1280         replace_top( bb, w2, Two );
1281         break;
1282     }
1283     case ROT2:  // w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2
1284     {
1285         if (echo) bb->setName("ROT2");
1286         LoadInst* w6 = cast<LoadInst>( stack_top( bb ) );
1287         LoadInst* w5 = cast<LoadInst>( stack_top( bb, One ) );
1288         LoadInst* w4 = cast<LoadInst>( stack_top( bb, Two ) );
1289         LoadInst* w3 = cast<LoadInst>( stack_top( bb, Three) );
1290         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Four ) );
1291         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Five ) );
1292         replace_top( bb, w2 );
1293         replace_top( bb, w1, One );
1294         replace_top( bb, w6, Two );
1295         replace_top( bb, w5, Three );
1296         replace_top( bb, w4, Four );
1297         replace_top( bb, w3, Five );
1298         break;
1299     }
1300     case RROT:  // w1 w2 w3 -- w3 w1 w2
1301     {
1302         if (echo) bb->setName("RROT2");
1303         LoadInst* w3 = cast<LoadInst>( stack_top( bb ) );
1304         LoadInst* w2 = cast<LoadInst>( stack_top( bb, One ) );
1305         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Two ) );
1306         replace_top( bb, w2 );
1307         replace_top( bb, w1, One );
1308         replace_top( bb, w3, Two );
1309         break;
1310     }
1311     case RROT2: // w1 w2 w3 w4 w5 w6 -- w5 w6 w1 w2 w3 w4
1312     {
1313         if (echo) bb->setName("RROT2");
1314         LoadInst* w6 = cast<LoadInst>( stack_top( bb ) );
1315         LoadInst* w5 = cast<LoadInst>( stack_top( bb, One ) );
1316         LoadInst* w4 = cast<LoadInst>( stack_top( bb, Two ) );
1317         LoadInst* w3 = cast<LoadInst>( stack_top( bb, Three) );
1318         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Four ) );
1319         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Five ) );
1320         replace_top( bb, w4 );
1321         replace_top( bb, w3, One );
1322         replace_top( bb, w2, Two );
1323         replace_top( bb, w1, Three );
1324         replace_top( bb, w6, Four );
1325         replace_top( bb, w5, Five );
1326         break;
1327     }
1328     case TUCK:  // w1 w2 -- w2 w1 w2
1329     {
1330         if (echo) bb->setName("TUCK");
1331         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1332         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1333         incr_stack_index( bb );
1334         replace_top( bb, w2 );
1335         replace_top( bb, w1, One );
1336         replace_top( bb, w2, Two );
1337         break;
1338     }
1339     case TUCK2: // w1 w2 w3 w4 -- w3 w4 w1 w2 w3 w4
1340     {
1341         if (echo) bb->setName("TUCK2");
1342         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1343         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1344         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1345         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three) );
1346         incr_stack_index( bb, Two );
1347         replace_top( bb, w4 );
1348         replace_top( bb, w3, One );
1349         replace_top( bb, w2, Two );
1350         replace_top( bb, w1, Three );
1351         replace_top( bb, w4, Four );
1352         replace_top( bb, w3, Five );
1353         break;
1354     }
1355     case ROLL:  // x0 x1 .. xn n -- x1 .. xn x0
1356     {
1357         /// THIS OEPRATOR IS OMITTED PURPOSEFULLY AND IS LEFT TO THE
1358         /// READER AS AN EXERCISE. THIS IS ONE OF THE MORE COMPLICATED
1359         /// OPERATORS. IF YOU CAN GET THIS ONE RIGHT, YOU COMPLETELY
1360         /// UNDERSTAND HOW BOTH LLVM AND STACKER WOR.
1361         /// HINT: LOOK AT PICK AND SELECT. ROLL IS SIMILAR.
1362         if (echo) bb->setName("ROLL");
1363         break;
1364     }
1365     case PICK:  // x0 ... Xn n -- x0 ... Xn x0
1366     {
1367         if (echo) bb->setName("PICK");
1368         LoadInst* n = cast<LoadInst>( stack_top( bb ) );
1369         BinaryOperator* addop =
1370             BinaryOperator::create( Instruction::Add, n, IOne );
1371         bb->getInstList().push_back( addop );
1372         LoadInst* x0 = cast<LoadInst>( stack_top( bb, addop ) );
1373         replace_top( bb, x0 );
1374         break;
1375     }
1376     case SELECT:        // m n X0..Xm Xm+1 .. Xn -- Xm
1377     {
1378         if (echo) bb->setName("SELECT");
1379         LoadInst* m = cast<LoadInst>( stack_top(bb) );
1380         LoadInst* n = cast<LoadInst>( stack_top(bb, One) );
1381         BinaryOperator* index =
1382             BinaryOperator::create( Instruction::Add, m, IOne );
1383         bb->getInstList().push_back( index );
1384         LoadInst* Xm = cast<LoadInst>( stack_top(bb, index ) );
1385         BinaryOperator* n_plus_1 =
1386             BinaryOperator::create( Instruction::Add, n, IOne );
1387         bb->getInstList().push_back( n_plus_1 );
1388         decr_stack_index( bb, n_plus_1 );
1389         replace_top( bb, Xm );
1390         break;
1391     }
1392     case MALLOC : // n -- p
1393     {
1394         if (echo) bb->setName("MALLOC");
1395         // Get the number of bytes to mallocate
1396         LoadInst* op1 = cast<LoadInst>( pop_integer(bb) );
1397
1398         // Make sure its a UIntTy
1399         CastInst* caster = new CastInst( op1, Type::UIntTy );
1400         bb->getInstList().push_back( caster );
1401
1402         // Allocate the bytes
1403         MallocInst* mi = new MallocInst( Type::SByteTy, caster );
1404         bb->getInstList().push_back( mi );
1405
1406         // Push the pointer
1407         push_value( bb, mi );
1408         break;
1409     }
1410     case FREE :  // p --
1411     {
1412         if (echo) bb->setName("FREE");
1413         // Pop the value off the stack
1414         CastInst* ptr = cast<CastInst>( pop_string(bb) );
1415
1416         // Free the memory
1417         FreeInst* fi = new FreeInst( ptr );
1418         bb->getInstList().push_back( fi );
1419
1420         break;
1421     }
1422     case GET : // p w1 -- p w2
1423     {
1424         if (echo) bb->setName("GET");
1425         // Get the character index
1426         LoadInst* op1 = cast<LoadInst>( stack_top(bb) );
1427         CastInst* chr_idx = new CastInst( op1, Type::LongTy );
1428         bb->getInstList().push_back( chr_idx );
1429
1430         // Get the String pointer
1431         CastInst* ptr = cast<CastInst>( stack_top_string(bb,One) );
1432
1433         // Get address of op1'th element of the string
1434         std::vector<Value*> indexVec;
1435         indexVec.push_back( chr_idx );
1436         GetElementPtrInst* gep = new GetElementPtrInst( ptr, indexVec );
1437         bb->getInstList().push_back( gep );
1438
1439         // Get the value and push it
1440         LoadInst* loader = new LoadInst( gep );
1441         bb->getInstList().push_back( loader );
1442         CastInst* caster = new CastInst( loader, Type::IntTy );
1443         bb->getInstList().push_back( caster );
1444
1445         // Push the result back on stack
1446         replace_top( bb, caster );
1447
1448         break;
1449     }
1450     case PUT : // p w2 w1  -- p
1451     {
1452         if (echo) bb->setName("PUT");
1453
1454         // Get the value to put
1455         LoadInst* w1 = cast<LoadInst>( pop_integer(bb) );
1456
1457         // Get the character index
1458         LoadInst* w2 = cast<LoadInst>( pop_integer(bb) );
1459         CastInst* chr_idx = new CastInst( w2, Type::LongTy );
1460         bb->getInstList().push_back( chr_idx );
1461
1462         // Get the String pointer
1463         CastInst* ptr = cast<CastInst>( stack_top_string(bb) );
1464
1465         // Get address of op2'th element of the string
1466         std::vector<Value*> indexVec;
1467         indexVec.push_back( chr_idx );
1468         GetElementPtrInst* gep = new GetElementPtrInst( ptr, indexVec );
1469         bb->getInstList().push_back( gep );
1470
1471         // Cast the value and put it
1472         CastInst* caster = new CastInst( w1, Type::SByteTy );
1473         bb->getInstList().push_back( caster );
1474         StoreInst* storer = new StoreInst( caster, gep );
1475         bb->getInstList().push_back( storer );
1476
1477         break;
1478     }
1479     case RECURSE :
1480     {
1481         if (echo) bb->setName("RECURSE");
1482         std::vector<Value*> params;
1483         CallInst* call_inst = new CallInst( TheFunction, params );
1484         bb->getInstList().push_back( call_inst );
1485         break;
1486     }
1487     case RETURN :
1488     {
1489         if (echo) bb->setName("RETURN");
1490         bb->getInstList().push_back( new ReturnInst() );
1491         break;
1492     }
1493     case EXIT :
1494     {
1495         if (echo) bb->setName("EXIT");
1496         // Get the result value
1497         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1498
1499         // Call exit(3)
1500         std::vector<Value*> params;
1501         params.push_back(op1);
1502         CallInst* call_inst = new CallInst( TheExit, params );
1503         bb->getInstList().push_back( call_inst );
1504         break;
1505     }
1506     case TAB :
1507     {
1508         if (echo) bb->setName("TAB");
1509         // Get the format string for a character
1510         std::vector<Value*> indexVec;
1511         indexVec.push_back( Zero );
1512         indexVec.push_back( Zero );
1513         GetElementPtrInst* format_gep =
1514             new GetElementPtrInst( ChrFormat, indexVec );
1515         bb->getInstList().push_back( format_gep );
1516
1517         // Get the character to print (a newline)
1518         ConstantSInt* newline = ConstantSInt::get(Type::IntTy,
1519             static_cast<int>('\t'));
1520
1521         // Call printf
1522         std::vector<Value*> args;
1523         args.push_back( format_gep );
1524         args.push_back( newline );
1525         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1526         break;
1527     }
1528     case SPACE :
1529     {
1530         if (echo) bb->setName("SPACE");
1531         // Get the format string for a character
1532         std::vector<Value*> indexVec;
1533         indexVec.push_back( Zero );
1534         indexVec.push_back( Zero );
1535         GetElementPtrInst* format_gep =
1536             new GetElementPtrInst( ChrFormat, indexVec );
1537         bb->getInstList().push_back( format_gep );
1538
1539         // Get the character to print (a newline)
1540         ConstantSInt* newline = ConstantSInt::get(Type::IntTy,
1541             static_cast<int>(' '));
1542
1543         // Call printf
1544         std::vector<Value*> args;
1545         args.push_back( format_gep );
1546         args.push_back( newline );
1547         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1548         break;
1549     }
1550     case CR :
1551     {
1552         if (echo) bb->setName("CR");
1553         // Get the format string for a character
1554         std::vector<Value*> indexVec;
1555         indexVec.push_back( Zero );
1556         indexVec.push_back( Zero );
1557         GetElementPtrInst* format_gep =
1558             new GetElementPtrInst( ChrFormat, indexVec );
1559         bb->getInstList().push_back( format_gep );
1560
1561         // Get the character to print (a newline)
1562         ConstantSInt* newline = ConstantSInt::get(Type::IntTy,
1563             static_cast<int>('\n'));
1564
1565         // Call printf
1566         std::vector<Value*> args;
1567         args.push_back( format_gep );
1568         args.push_back( newline );
1569         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1570         break;
1571     }
1572     case IN_STR :
1573     {
1574         if (echo) bb->setName("IN_STR");
1575         // Make room for the value result
1576         incr_stack_index(bb);
1577         GetElementPtrInst* gep_value =
1578             cast<GetElementPtrInst>(get_stack_pointer(bb));
1579         CastInst* caster =
1580             new CastInst( gep_value, PointerType::get( Type::SByteTy ) );
1581
1582         // Make room for the count result
1583         incr_stack_index(bb);
1584         GetElementPtrInst* gep_count =
1585             cast<GetElementPtrInst>(get_stack_pointer(bb));
1586
1587         // Call scanf(3)
1588         std::vector<Value*> args;
1589         args.push_back( InStrFormat );
1590         args.push_back( caster );
1591         CallInst* scanf = new CallInst( TheScanf, args );
1592         bb->getInstList().push_back( scanf );
1593
1594         // Store the result
1595         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1596         break;
1597     }
1598     case IN_NUM :
1599     {
1600         if (echo) bb->setName("IN_NUM");
1601         // Make room for the value result
1602         incr_stack_index(bb);
1603         GetElementPtrInst* gep_value =
1604             cast<GetElementPtrInst>(get_stack_pointer(bb));
1605
1606         // Make room for the count result
1607         incr_stack_index(bb);
1608         GetElementPtrInst* gep_count =
1609             cast<GetElementPtrInst>(get_stack_pointer(bb));
1610
1611         // Call scanf(3)
1612         std::vector<Value*> args;
1613         args.push_back( InStrFormat );
1614         args.push_back( gep_value );
1615         CallInst* scanf = new CallInst( TheScanf, args );
1616         bb->getInstList().push_back( scanf );
1617
1618         // Store the result
1619         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1620         break;
1621     }
1622     case IN_CHAR :
1623     {
1624         if (echo) bb->setName("IN_CHAR");
1625         // Make room for the value result
1626         incr_stack_index(bb);
1627         GetElementPtrInst* gep_value =
1628             cast<GetElementPtrInst>(get_stack_pointer(bb));
1629
1630         // Make room for the count result
1631         incr_stack_index(bb);
1632         GetElementPtrInst* gep_count =
1633             cast<GetElementPtrInst>(get_stack_pointer(bb));
1634
1635         // Call scanf(3)
1636         std::vector<Value*> args;
1637         args.push_back( InChrFormat );
1638         args.push_back( gep_value );
1639         CallInst* scanf = new CallInst( TheScanf, args );
1640         bb->getInstList().push_back( scanf );
1641
1642         // Store the result
1643         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1644         break;
1645     }
1646     case OUT_STR :
1647     {
1648         if (echo) bb->setName("OUT_STR");
1649         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1650
1651         // Get the address of the format string
1652         std::vector<Value*> indexVec;
1653         indexVec.push_back( Zero );
1654         indexVec.push_back( Zero );
1655         GetElementPtrInst* format_gep =
1656             new GetElementPtrInst( StrFormat, indexVec );
1657         bb->getInstList().push_back( format_gep );
1658         // Build function call arguments
1659         std::vector<Value*> args;
1660         args.push_back( format_gep );
1661         args.push_back( op1 );
1662         // Call printf
1663         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1664         break;
1665     }
1666     case OUT_NUM :
1667     {
1668         if (echo) bb->setName("OUT_NUM");
1669         // Pop the numeric operand off the stack
1670         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1671
1672         // Get the address of the format string
1673         std::vector<Value*> indexVec;
1674         indexVec.push_back( Zero );
1675         indexVec.push_back( Zero );
1676         GetElementPtrInst* format_gep =
1677             new GetElementPtrInst( NumFormat, indexVec );
1678         bb->getInstList().push_back( format_gep );
1679
1680         // Build function call arguments
1681         std::vector<Value*> args;
1682         args.push_back( format_gep );
1683         args.push_back( op1 );
1684
1685         // Call printf
1686         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1687         break;
1688     }
1689     case OUT_CHAR :
1690     {
1691         if (echo) bb->setName("OUT_CHAR");
1692         // Pop the character operand off the stack
1693         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1694
1695         // Get the address of the format string
1696         std::vector<Value*> indexVec;
1697         indexVec.push_back( Zero );
1698         indexVec.push_back( Zero );
1699         GetElementPtrInst* format_gep =
1700             new GetElementPtrInst( ChrFormat, indexVec );
1701         bb->getInstList().push_back( format_gep );
1702
1703         // Build function call arguments
1704         std::vector<Value*> args;
1705         args.push_back( format_gep );
1706         args.push_back( op1 );
1707         // Call printf
1708         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1709         break;
1710     }
1711     default :
1712     {
1713         ThrowException(std::string("Compiler Error: Unhandled token #"));
1714     }
1715     }
1716
1717     // Return the basic block
1718     return bb;
1719 }