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