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