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