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