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