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