projects/Stacker/lib/compiler/StackerCompiler.cpp

   1 //===-- StackerCompiler.cpp - Parser for llvm assembly files ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Reid Spencer and donated to the LLVM research
   6 // group and is distributed under the University of Illinois Open Source
   7 // License. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10 //
  11 //  This file implements the compiler for the "Stacker" language.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 //===----------------------------------------------------------------------===//
  16 //            Globasl - Global variables we use
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/PassManager.h"
  20 #include "llvm/Analysis/LoadValueNumbering.h"
  21 #include "llvm/Analysis/Verifier.h"
  22 #include "llvm/Assembly/Parser.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/Transforms/IPO.h"
  25 #include "llvm/Transforms/Scalar.h"
  26 #include "llvm/Instructions.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "StackerCompiler.h"
  29 #include "StackerParser.h"
  30 #include <string>
  31
  32 // Lexer/Parser defined variables and functions
  33 extern std::FILE *Stackerin;
  34 extern int Stackerlineno;
  35 extern char* Stackertext;
  36 extern int Stackerleng;
  37 extern int Stackerparse();
  38
  39 StackerCompiler* StackerCompiler::TheInstance = 0;
  40
  41 static Statistic NumDefinitions(
  42         "numdefs","The # of definitions encoutered while compiling Stacker");
  43
  44 StackerCompiler::StackerCompiler()
  45     : CurFilename("")
  46     , TheModule(0)
  47     , TheFunction(0)
  48     , DefinitionType(0)
  49     , TheStack(0)
  50     , TheIndex(0)
  51     , TheScanf(0)
  52     , ThePrintf(0)
  53     , TheExit(0)
  54     , StrFormat(0)
  55     , NumFormat(0)
  56     , ChrFormat(0)
  57     , InStrFormat(0)
  58     , InNumFormat(0)
  59     , InChrFormat(0)
  60     , Zero(0)
  61     , One(0)
  62     , Two(0)
  63     , Three(0)
  64     , Four(0)
  65     , Five(0)
  66     , no_arguments()
  67     , echo(false)
  68     , stack_size(256)
  69     , stack_type(0)
  70 {
  71 }
  72
  73 StackerCompiler::~StackerCompiler()
  74 {
  75     // delete TheModule; << don't do this!
  76     // TheModule is passed to caller of the compile() method .. its their
  77     // problem.  Likewise for the other allocated objects (which become part
  78     // of TheModule.
  79     TheModule = 0;
  80     DefinitionType = 0;
  81     TheStack = 0;
  82     TheIndex = 0;
  83 }
  84
  85 Module*
  86 StackerCompiler::compile(
  87     const std::string& filename,
  88     bool should_echo,
  89     unsigned optLevel,
  90     size_t the_stack_size
  91 )
  92 {
  93     // TODO: Provide a global lock to protect the singled-threaded compiler
  94     // and its global variables. Should be in guard object on the stack so
  95     // that its destructor causes lock to be released (multiple exits from
  96     // this function).
  97
  98     // Assign parameters
  99     CurFilename = filename;
 100     echo = should_echo;
 101     stack_size = the_stack_size;
 102
 103     /// Default the file to read
 104     FILE *F = stdin;
 105
 106     ///
 107     if (filename != "-")
 108     {
 109         F = fopen(filename.c_str(), "r");
 110
 111         if (F == 0)
 112         {
 113           ParseError Err;
 114           Err.setError(filename, "Could not open file '" + filename + "'");
 115           throw Err;
 116         }
 117     }
 118
 119     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(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(createPromoteMemoryToRegisterPass());
 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 = CastInst::createSExtOrBitCast( 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 = CastInst::createSExtOrBitCast( 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 = CastInst::createSExtOrBitCast( 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     Instruction::CastOps opcode =
 452        (isa<PointerType>(val->getType()) ? Instruction::PtrToInt :
 453         (val->getType()->getPrimitiveSizeInBits() < 64 ? Instruction::SExt :
 454          Instruction::BitCast));
 455     CastInst* cast_inst = CastInst::create(opcode, val, Type::LongTy );
 456     bb->getInstList().push_back( cast_inst );
 457
 458     // Store the value
 459     StoreInst* storeop = new StoreInst( cast_inst, gep );
 460     bb->getInstList().push_back( storeop );
 461
 462     return storeop;
 463 }
 464
 465 Instruction*
 466 StackerCompiler::push_integer(BasicBlock* bb, int64_t value )
 467 {
 468     // Just push a constant integer value
 469     return push_value( bb, ConstantInt::get( Type::LongTy, value ) );
 470 }
 471
 472 Instruction*
 473 StackerCompiler::pop_integer( BasicBlock*bb )
 474 {
 475     // Get the stack pointer
 476     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 477         get_stack_pointer( bb ));
 478
 479     // Load the value
 480     LoadInst* load_inst = new LoadInst( gep );
 481     bb->getInstList().push_back( load_inst );
 482
 483     // Decrement the stack index
 484     decr_stack_index( bb );
 485
 486     // Return the value
 487     return load_inst;
 488 }
 489
 490 Instruction*
 491 StackerCompiler::push_string( BasicBlock* bb, const char* value )
 492 {
 493     // Get length of the string
 494     size_t len = strlen( value );
 495
 496     // Create a type for the string constant. Length is +1 for
 497     // the terminating 0.
 498     ArrayType* char_array = ArrayType::get( Type::SByteTy, len + 1 );
 499
 500     // Create an initializer for the value
 501     Constant* initVal = ConstantArray::get( value );
 502
 503     // Create an internal linkage global variable to hold the constant.
 504     GlobalVariable* strconst = new GlobalVariable(
 505         char_array,
 506         /*isConstant=*/true,
 507         GlobalValue::InternalLinkage,
 508         /*initializer=*/initVal,
 509         "",
 510         TheModule
 511     );
 512
 513     // Push the casted value
 514     return push_value( bb, strconst );
 515 }
 516
 517 Instruction*
 518 StackerCompiler::pop_string( BasicBlock* bb )
 519 {
 520     // Get location of stack pointer
 521     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 522         get_stack_pointer( bb ));
 523
 524     // Load the value from the stack
 525     LoadInst* loader = new LoadInst( gep );
 526     bb->getInstList().push_back( loader );
 527
 528     // Cast the integer to a sbyte*
 529     CastInst* caster =
 530       new IntToPtrInst(loader, PointerType::get(Type::SByteTy));
 531     bb->getInstList().push_back( caster );
 532
 533     // Decrement stack index
 534     decr_stack_index( bb );
 535
 536     // Return the value
 537     return caster;
 538 }
 539
 540 Instruction*
 541 StackerCompiler::replace_top( BasicBlock* bb, Value* new_top, Value* index = 0 )
 542 {
 543     // Get the stack pointer
 544     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 545             get_stack_pointer( bb, index ));
 546
 547     // Store the value there
 548     StoreInst* store_inst = new StoreInst( new_top, gep );
 549     bb->getInstList().push_back( store_inst );
 550
 551     // Return the value
 552     return store_inst;
 553 }
 554
 555 Instruction*
 556 StackerCompiler::stack_top( BasicBlock* bb, Value* index = 0 )
 557 {
 558     // Get the stack pointer
 559     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 560         get_stack_pointer( bb, index ));
 561
 562     // Load the value
 563     LoadInst* load_inst = new LoadInst( gep );
 564     bb->getInstList().push_back( load_inst );
 565
 566     // Return the value
 567     return load_inst;
 568 }
 569
 570 Instruction*
 571 StackerCompiler::stack_top_string( BasicBlock* bb, Value* index = 0 )
 572 {
 573     // Get location of stack pointer
 574     GetElementPtrInst* gep = cast<GetElementPtrInst>(
 575         get_stack_pointer( bb, index ));
 576
 577     // Load the value from the stack
 578     LoadInst* loader = new LoadInst( gep );
 579     bb->getInstList().push_back( loader );
 580
 581     // Cast the integer to a sbyte*
 582     CastInst* caster =
 583       new IntToPtrInst(loader, PointerType::get(Type::SByteTy) );
 584     bb->getInstList().push_back( caster );
 585
 586     // Return the value
 587     return caster;
 588 }
 589
 590 static void
 591 add_block( Function*f, BasicBlock* bb )
 592 {
 593     if ( ! f->empty() && f->back().getTerminator() == 0 )
 594     {
 595         BranchInst* branch = new BranchInst(bb);
 596         f->back().getInstList().push_back( branch );
 597     }
 598     f->getBasicBlockList().push_back( bb );
 599 }
 600
 601
 602 //===----------------------------------------------------------------------===//
 603 //            handleXXX - Handle semantics of parser productions
 604 //===----------------------------------------------------------------------===//
 605
 606 Module*
 607 StackerCompiler::handle_module_start( )
 608 {
 609     // Return the newly created module
 610     return TheModule;
 611 }
 612
 613 Module*
 614 StackerCompiler::handle_module_end( Module* mod )
 615 {
 616     // Return the module.
 617     return mod;
 618 }
 619
 620 Module*
 621 StackerCompiler::handle_definition_list_start()
 622 {
 623     return TheModule;
 624 }
 625
 626 Module*
 627 StackerCompiler::handle_definition_list_end( Module* mod, Function* definition )
 628 {
 629     if ( ! definition->empty() )
 630     {
 631         BasicBlock& last_block = definition->back();
 632         if ( last_block.getTerminator() == 0 )
 633         {
 634             last_block.getInstList().push_back( new ReturnInst() );
 635         }
 636     }
 637     // Insert the definition into the module
 638     mod->getFunctionList().push_back( definition );
 639
 640     // Bump our (sample) statistic.
 641     ++NumDefinitions;
 642     return mod;
 643 }
 644
 645 Function*
 646 StackerCompiler::handle_main_definition( Function* func )
 647 {
 648     // Set the name of the function defined as the Stacker main
 649     // This will get called by the "main" that is defined in
 650     // the runtime library.
 651     func->setName( "_MAIN_");
 652
 653     // Turn "_stack_" into an initialized variable since this is the main
 654     // module. This causes it to not be "external" but defined in this module.
 655     TheStack->setInitializer( Constant::getNullValue(stack_type) );
 656     TheStack->setLinkage( GlobalValue::LinkOnceLinkage );
 657
 658     // Turn "_index_" into an intialized variable for the same reason.
 659     TheIndex->setInitializer( Constant::getNullValue(Type::LongTy) );
 660     TheIndex->setLinkage( GlobalValue::LinkOnceLinkage );
 661
 662     return func;
 663 }
 664
 665 Function*
 666 StackerCompiler::handle_forward( char * name )
 667 {
 668     // Just create a placeholder function
 669     Function* the_function = new Function (
 670         DefinitionType,
 671         GlobalValue::ExternalLinkage,
 672         name );
 673     assert( the_function->isExternal() );
 674
 675     free( name );
 676     return the_function;
 677 }
 678
 679 Function*
 680 StackerCompiler::handle_definition( char * name, Function* f )
 681 {
 682     // Look up the function name in the module to see if it was forward
 683     // declared.
 684 #if 0
 685     Function* existing_function = TheModule->getNamedFunction( name );
 686
 687     // If the function already exists...
 688     if ( existing_function )
 689     {
 690         // Just get rid of the placeholder
 691         existing_function->dropAllReferences();
 692         delete existing_function;
 693     }
 694 #endif
 695
 696     // Just set the name of the function now that we know what it is.
 697     f->setName( name );
 698
 699     free( name );
 700
 701     return f;
 702 }
 703
 704 Function*
 705 StackerCompiler::handle_word_list_start()
 706 {
 707     TheFunction = new Function(DefinitionType, GlobalValue::ExternalLinkage);
 708     return TheFunction;
 709 }
 710
 711 Function*
 712 StackerCompiler::handle_word_list_end( Function* f, BasicBlock* bb )
 713 {
 714     add_block( f, bb );
 715     return f;
 716 }
 717
 718 BasicBlock*
 719 StackerCompiler::handle_if( char* ifTrue, char* ifFalse )
 720 {
 721     // Create a basic block for the preamble
 722     BasicBlock* bb = new BasicBlock((echo?"if":""));
 723
 724     // Get the condition value
 725     LoadInst* cond = cast<LoadInst>( pop_integer(bb) );
 726
 727     // Compare the condition against 0
 728     SetCondInst* cond_inst = new SetCondInst( Instruction::SetNE, cond,
 729         ConstantInt::get( Type::LongTy, 0) );
 730     bb->getInstList().push_back( cond_inst );
 731
 732     // Create an exit block
 733     BasicBlock* exit_bb = new BasicBlock((echo?"endif":""));
 734
 735     // Create the true_block
 736     BasicBlock* true_bb = new BasicBlock((echo?"then":""));
 737
 738     // Create the false_block
 739     BasicBlock* false_bb = 0;
 740     if ( ifFalse ) false_bb = new BasicBlock((echo?"else":""));
 741
 742     // Create a branch on the SetCond
 743     BranchInst* br_inst = new BranchInst( true_bb,
 744         ( ifFalse ? false_bb : exit_bb ), cond_inst );
 745     bb->getInstList().push_back( br_inst );
 746
 747     // Fill the true block
 748     std::vector<Value*> args;
 749     if ( Function* true_func = TheModule->getNamedFunction(ifTrue) )
 750     {
 751         true_bb->getInstList().push_back(
 752                 new CallInst( true_func, args ) );
 753         true_bb->getInstList().push_back(
 754                 new BranchInst( exit_bb ) );
 755     }
 756     else
 757     {
 758         ThrowException(std::string("Function '") + ifTrue +
 759             "' must be declared first.'");
 760     }
 761
 762     free( ifTrue );
 763
 764     // Fill the false block
 765     if ( false_bb )
 766     {
 767         if ( Function* false_func = TheModule->getNamedFunction(ifFalse) )
 768         {
 769             false_bb->getInstList().push_back(
 770                     new CallInst( false_func, args ) );
 771             false_bb->getInstList().push_back(
 772                     new BranchInst( exit_bb ) );
 773         }
 774         else
 775         {
 776             ThrowException(std::string("Function '") + ifFalse +
 777                     "' must be declared first.'");
 778         }
 779         free( ifFalse );
 780     }
 781
 782     // Add the blocks to the function
 783     add_block( TheFunction, bb );
 784     add_block( TheFunction, true_bb );
 785     if ( false_bb ) add_block( TheFunction, false_bb );
 786
 787     return exit_bb;
 788 }
 789
 790 BasicBlock*
 791 StackerCompiler::handle_while( char* todo )
 792 {
 793
 794     // Create a basic block for the loop test
 795     BasicBlock* test = new BasicBlock((echo?"while":""));
 796
 797     // Create an exit block
 798     BasicBlock* exit = new BasicBlock((echo?"end":""));
 799
 800     // Create a loop body block
 801     BasicBlock* body = new BasicBlock((echo?"do":""));
 802
 803     // Create a root node
 804     BasicBlock* bb = new BasicBlock((echo?"root":""));
 805     BranchInst* root_br_inst = new BranchInst( test );
 806     bb->getInstList().push_back( root_br_inst );
 807
 808     // Examine the condition value
 809     LoadInst* cond = cast<LoadInst>( stack_top(test) );
 810
 811     // Compare the condition against 0
 812     SetCondInst* cond_inst = new SetCondInst(
 813         Instruction::SetNE, cond, ConstantInt::get( Type::LongTy, 0));
 814     test->getInstList().push_back( cond_inst );
 815
 816     // Add the branch instruction
 817     BranchInst* br_inst = new BranchInst( body, exit, cond_inst );
 818     test->getInstList().push_back( br_inst );
 819
 820     // Fill in the body
 821     std::vector<Value*> args;
 822     if ( Function* body_func = TheModule->getNamedFunction(todo) )
 823     {
 824         body->getInstList().push_back( new CallInst( body_func, args ) );
 825         body->getInstList().push_back( new BranchInst( test ) );
 826     }
 827     else
 828     {
 829         ThrowException(std::string("Function '") + todo +
 830             "' must be declared first.'");
 831     }
 832
 833     free( todo );
 834
 835     // Add the blocks
 836     add_block( TheFunction, bb );
 837     add_block( TheFunction, test );
 838     add_block( TheFunction, body );
 839
 840     return exit;
 841 }
 842
 843 BasicBlock*
 844 StackerCompiler::handle_identifier( char * name )
 845 {
 846     Function* func = TheModule->getNamedFunction( name );
 847     BasicBlock* bb = new BasicBlock((echo?"call":""));
 848     if ( func )
 849     {
 850         CallInst* call_def = new CallInst( func , no_arguments );
 851         bb->getInstList().push_back( call_def );
 852     }
 853     else
 854     {
 855         ThrowException(std::string("Definition '") + name +
 856             "' must be defined before it can be used.");
 857     }
 858
 859     free( name );
 860     return bb;
 861 }
 862
 863 BasicBlock*
 864 StackerCompiler::handle_string( char * value )
 865 {
 866     // Create a new basic block for the push operation
 867     BasicBlock* bb = new BasicBlock((echo?"string":""));
 868
 869     // Push the string onto the stack
 870     push_string(bb, value);
 871
 872     // Free the strdup'd string
 873     free( value );
 874
 875     return bb;
 876 }
 877
 878 BasicBlock*
 879 StackerCompiler::handle_integer( const int64_t value )
 880 {
 881     // Create a new basic block for the push operation
 882     BasicBlock* bb = new BasicBlock((echo?"int":""));
 883
 884     // Push the integer onto the stack
 885     push_integer(bb, value );
 886
 887     return bb;
 888 }
 889
 890 BasicBlock*
 891 StackerCompiler::handle_word( int tkn )
 892 {
 893     // Create a new basic block to hold the instruction(s)
 894     BasicBlock* bb = new BasicBlock();
 895
 896     /* Fill the basic block with the appropriate instructions */
 897     switch ( tkn )
 898     {
 899     case DUMP :  // Dump the stack (debugging aid)
 900     {
 901         if (echo) bb->setName("DUMP");
 902         Function* f = TheModule->getOrInsertFunction(
 903             "_stacker_dump_stack_", DefinitionType);
 904         std::vector<Value*> args;
 905         bb->getInstList().push_back( new CallInst( f, args ) );
 906         break;
 907     }
 908
 909     // Logical Operations
 910     case TRUETOK :  // -- -1
 911     {
 912         if (echo) bb->setName("TRUE");
 913         push_integer(bb,-1);
 914         break;
 915     }
 916     case FALSETOK : // -- 0
 917     {
 918         if (echo) bb->setName("FALSE");
 919         push_integer(bb,0);
 920         break;
 921     }
 922     case LESS : // w1 w2 -- w2<w1
 923     {
 924         if (echo) bb->setName("LESS");
 925         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 926         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 927         SetCondInst* cond_inst =
 928             new SetCondInst( Instruction::SetLT, op1, op2 );
 929         bb->getInstList().push_back( cond_inst );
 930         push_value( bb, cond_inst );
 931         break;
 932     }
 933     case MORE : // w1 w2 -- w2>w1
 934     {
 935         if (echo) bb->setName("MORE");
 936         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 937         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 938         SetCondInst* cond_inst =
 939             new SetCondInst( Instruction::SetGT, op1, op2 );
 940         bb->getInstList().push_back( cond_inst );
 941         push_value( bb, cond_inst );
 942         break;
 943     }
 944     case LESS_EQUAL : // w1 w2 -- w2<=w1
 945     {
 946         if (echo) bb->setName("LE");
 947         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 948         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 949         SetCondInst* cond_inst =
 950             new SetCondInst( Instruction::SetLE, op1, op2 );
 951         bb->getInstList().push_back( cond_inst );
 952         push_value( bb, cond_inst );
 953         break;
 954     }
 955     case MORE_EQUAL : // w1 w2 -- w2>=w1
 956     {
 957         if (echo) bb->setName("GE");
 958         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 959         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 960         SetCondInst* cond_inst =
 961             new SetCondInst( Instruction::SetGE, op1, op2 );
 962         bb->getInstList().push_back( cond_inst );
 963         push_value( bb, cond_inst );
 964         break;
 965     }
 966     case NOT_EQUAL : // w1 w2 -- w2!=w1
 967     {
 968         if (echo) bb->setName("NE");
 969         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 970         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 971         SetCondInst* cond_inst =
 972             new SetCondInst( Instruction::SetNE, op1, op2 );
 973         bb->getInstList().push_back( cond_inst );
 974         push_value( bb, cond_inst );
 975         break;
 976     }
 977     case EQUAL : // w1 w2 -- w1==w2
 978     {
 979         if (echo) bb->setName("EQ");
 980         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 981         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 982         SetCondInst* cond_inst =
 983             new SetCondInst( Instruction::SetEQ, op1, op2 );
 984         bb->getInstList().push_back( cond_inst );
 985         push_value( bb, cond_inst );
 986         break;
 987     }
 988
 989     // Arithmetic Operations
 990     case PLUS : // w1 w2 -- w2+w1
 991     {
 992         if (echo) bb->setName("ADD");
 993         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
 994         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
 995         BinaryOperator* addop =
 996             BinaryOperator::create( Instruction::Add, op1, op2);
 997         bb->getInstList().push_back( addop );
 998         push_value( bb, addop );
 999         break;
1000     }
1001     case MINUS : // w1 w2 -- w2-w1
1002     {
1003         if (echo) bb->setName("SUB");
1004         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1005         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1006         BinaryOperator* subop =
1007             BinaryOperator::create( Instruction::Sub, op1, op2);
1008         bb->getInstList().push_back( subop );
1009         push_value( bb, subop );
1010         break;
1011     }
1012     case INCR :  // w1 -- w1+1
1013     {
1014         if (echo) bb->setName("INCR");
1015         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1016         BinaryOperator* addop =
1017             BinaryOperator::create( Instruction::Add, op1, One );
1018         bb->getInstList().push_back( addop );
1019         push_value( bb, addop );
1020         break;
1021     }
1022     case DECR : // w1 -- w1-1
1023     {
1024         if (echo) bb->setName("DECR");
1025         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1026         BinaryOperator* subop = BinaryOperator::create( Instruction::Sub, op1,
1027             ConstantInt::get( Type::LongTy, 1 ) );
1028         bb->getInstList().push_back( subop );
1029         push_value( bb, subop );
1030         break;
1031     }
1032     case MULT : // w1 w2 -- w2*w1
1033     {
1034         if (echo) bb->setName("MUL");
1035         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1036         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1037         BinaryOperator* multop =
1038             BinaryOperator::create( Instruction::Mul, op1, op2);
1039         bb->getInstList().push_back( multop );
1040         push_value( bb, multop );
1041         break;
1042     }
1043     case DIV :// w1 w2 -- w2/w1
1044     {
1045         if (echo) bb->setName("DIV");
1046         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1047         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1048         BinaryOperator* divop =
1049             BinaryOperator::create( Instruction::SDiv, op1, op2);
1050         bb->getInstList().push_back( divop );
1051         push_value( bb, divop );
1052         break;
1053     }
1054     case MODULUS : // w1 w2 -- w2%w1
1055     {
1056         if (echo) bb->setName("MOD");
1057         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1058         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1059         BinaryOperator* divop =
1060             BinaryOperator::create( Instruction::SRem, op1, op2);
1061         bb->getInstList().push_back( divop );
1062         push_value( bb, divop );
1063         break;
1064     }
1065     case STAR_SLASH : // w1 w2 w3 -- (w3*w2)/w1
1066     {
1067         if (echo) bb->setName("STAR_SLASH");
1068         // Get the operands
1069         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1070         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1071         LoadInst* op3 = cast<LoadInst>(pop_integer(bb));
1072
1073         // Multiply the first two
1074         BinaryOperator* multop =
1075             BinaryOperator::create( Instruction::Mul, op1, op2);
1076         bb->getInstList().push_back( multop );
1077
1078         // Divide by the third operand
1079         BinaryOperator* divop =
1080             BinaryOperator::create( Instruction::SDiv, multop, op3);
1081         bb->getInstList().push_back( divop );
1082
1083         // Push the result
1084         push_value( bb, divop );
1085
1086         break;
1087     }
1088     case NEGATE : // w1 -- -w1
1089     {
1090         if (echo) bb->setName("NEG");
1091         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1092         // APPARENTLY, the following doesn't work:
1093         // BinaryOperator* negop = BinaryOperator::createNeg( op1 );
1094         // bb->getInstList().push_back( negop );
1095         // So we'll multiply by -1 (ugh)
1096         BinaryOperator* multop = BinaryOperator::create( Instruction::Mul, op1,
1097             ConstantInt::get( Type::LongTy, -1 ) );
1098         bb->getInstList().push_back( multop );
1099         push_value( bb, multop );
1100         break;
1101     }
1102     case ABS : // w1 -- |w1|
1103     {
1104         if (echo) bb->setName("ABS");
1105         // Get the top of stack value
1106         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1107
1108         // Determine if its negative
1109         SetCondInst* cond_inst =
1110             new SetCondInst( Instruction::SetLT, op1, Zero );
1111         bb->getInstList().push_back( cond_inst );
1112
1113         // Create a block for storing the result
1114         BasicBlock* exit_bb = new BasicBlock((echo?"exit":""));
1115
1116         // Create a block for making it a positive value
1117         BasicBlock* pos_bb = new BasicBlock((echo?"neg":""));
1118
1119         // Create the branch on the SetCond
1120         BranchInst* br_inst = new BranchInst( pos_bb, exit_bb, cond_inst );
1121         bb->getInstList().push_back( br_inst );
1122
1123         // Fill out the negation block
1124         LoadInst* pop_op = cast<LoadInst>( pop_integer(pos_bb) );
1125         BinaryOperator* neg_op = BinaryOperator::createNeg( pop_op );
1126         pos_bb->getInstList().push_back( neg_op );
1127         push_value( pos_bb, neg_op );
1128         pos_bb->getInstList().push_back( new BranchInst( exit_bb ) );
1129
1130         // Add the new blocks in the correct order
1131         add_block( TheFunction, bb );
1132         add_block( TheFunction, pos_bb );
1133         bb = exit_bb;
1134         break;
1135     }
1136     case MIN : // w1 w2 -- (w2<w1?w2:w1)
1137     {
1138         if (echo) bb->setName("MIN");
1139
1140         // Create the three blocks
1141         BasicBlock* exit_bb  = new BasicBlock((echo?"exit":""));
1142         BasicBlock* op1_block = new BasicBlock((echo?"less":""));
1143         BasicBlock* op2_block = new BasicBlock((echo?"more":""));
1144
1145         // Get the two operands
1146         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1147         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1148
1149         // Compare them
1150         SetCondInst* cond_inst =
1151             new SetCondInst( Instruction::SetLT, op1, op2);
1152         bb->getInstList().push_back( cond_inst );
1153
1154         // Create a branch on the SetCond
1155         BranchInst* br_inst =
1156             new BranchInst( op1_block, op2_block, cond_inst );
1157         bb->getInstList().push_back( br_inst );
1158
1159         // Create a block for pushing the first one
1160         push_value(op1_block, op1);
1161         op1_block->getInstList().push_back( new BranchInst( exit_bb ) );
1162
1163         // Create a block for pushing the second one
1164         push_value(op2_block, op2);
1165         op2_block->getInstList().push_back( new BranchInst( exit_bb ) );
1166
1167         // Add the blocks
1168         add_block( TheFunction, bb );
1169         add_block( TheFunction, op1_block );
1170         add_block( TheFunction, op2_block );
1171         bb = exit_bb;
1172         break;
1173     }
1174     case MAX : // w1 w2 -- (w2>w1?w2:w1)
1175     {
1176         if (echo) bb->setName("MAX");
1177         // Get the two operands
1178         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1179         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1180
1181         // Compare them
1182         SetCondInst* cond_inst =
1183             new SetCondInst( Instruction::SetGT, op1, op2);
1184         bb->getInstList().push_back( cond_inst );
1185
1186         // Create an exit block
1187         BasicBlock* exit_bb = new BasicBlock((echo?"exit":""));
1188
1189         // Create a block for pushing the larger one
1190         BasicBlock* op1_block = new BasicBlock((echo?"more":""));
1191         push_value(op1_block, op1);
1192         op1_block->getInstList().push_back( new BranchInst( exit_bb ) );
1193
1194         // Create a block for pushing the smaller or equal one
1195         BasicBlock* op2_block = new BasicBlock((echo?"less":""));
1196         push_value(op2_block, op2);
1197         op2_block->getInstList().push_back( new BranchInst( exit_bb ) );
1198
1199         // Create a banch on the SetCond
1200         BranchInst* br_inst =
1201             new BranchInst( op1_block, op2_block, cond_inst );
1202         bb->getInstList().push_back( br_inst );
1203
1204         // Add the blocks
1205         add_block( TheFunction, bb );
1206         add_block( TheFunction, op1_block );
1207         add_block( TheFunction, op2_block );
1208
1209         bb = exit_bb;
1210         break;
1211     }
1212
1213     // Bitwise Operators
1214     case AND : // w1 w2 -- w2&w1
1215     {
1216         if (echo) bb->setName("AND");
1217         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1218         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1219         BinaryOperator* andop =
1220             BinaryOperator::create( Instruction::And, op1, op2);
1221         bb->getInstList().push_back( andop );
1222         push_value( bb, andop );
1223         break;
1224     }
1225     case OR : // w1 w2 -- w2|w1
1226     {
1227         if (echo) bb->setName("OR");
1228         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1229         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1230         BinaryOperator* orop =
1231             BinaryOperator::create( Instruction::Or, op1, op2);
1232         bb->getInstList().push_back( orop );
1233         push_value( bb, orop );
1234         break;
1235     }
1236     case XOR : // w1 w2 -- w2^w1
1237     {
1238         if (echo) bb->setName("XOR");
1239         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1240         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1241         BinaryOperator* xorop =
1242             BinaryOperator::create( Instruction::Xor, op1, op2);
1243         bb->getInstList().push_back( xorop );
1244         push_value( bb, xorop );
1245         break;
1246     }
1247     case LSHIFT : // w1 w2 -- w1<<w2
1248     {
1249         if (echo) bb->setName("SHL");
1250         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1251         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1252         CastInst* castop = new TruncInst( op1, Type::UByteTy );
1253         bb->getInstList().push_back( castop );
1254         ShiftInst* shlop = new ShiftInst( Instruction::Shl, op2, castop );
1255         bb->getInstList().push_back( shlop );
1256         push_value( bb, shlop );
1257         break;
1258     }
1259     case RSHIFT :  // w1 w2 -- w1>>w2
1260     {
1261         if (echo) bb->setName("SHR");
1262         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1263         LoadInst* op2 = cast<LoadInst>(pop_integer(bb));
1264         CastInst* castop = new TruncInst( op1, Type::UByteTy );
1265         bb->getInstList().push_back( castop );
1266         ShiftInst* shrop = new ShiftInst( Instruction::AShr, op2, castop );
1267         bb->getInstList().push_back( shrop );
1268         push_value( bb, shrop );
1269         break;
1270     }
1271
1272     // Stack Manipulation Operations
1273     case DROP:          // w --
1274     {
1275         if (echo) bb->setName("DROP");
1276         decr_stack_index(bb, One);
1277         break;
1278     }
1279     case DROP2: // w1 w2 --
1280     {
1281         if (echo) bb->setName("DROP2");
1282         decr_stack_index( bb, Two );
1283         break;
1284     }
1285     case NIP:   // w1 w2 -- w2
1286     {
1287         if (echo) bb->setName("NIP");
1288         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1289         decr_stack_index( bb  );
1290         replace_top( bb, w2 );
1291         break;
1292     }
1293     case NIP2:  // w1 w2 w3 w4 -- w3 w4
1294     {
1295         if (echo) bb->setName("NIP2");
1296         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1297         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1298         decr_stack_index( bb, Two );
1299         replace_top( bb, w4 );
1300         replace_top( bb, w3, One );
1301         break;
1302     }
1303     case DUP:   // w -- w w
1304     {
1305         if (echo) bb->setName("DUP");
1306         LoadInst* w = cast<LoadInst>( stack_top( bb ) );
1307         push_value( bb, w );
1308         break;
1309     }
1310     case DUP2:  // w1 w2 -- w1 w2 w1 w2
1311     {
1312         if (echo) bb->setName("DUP2");
1313         LoadInst* w2 = cast<LoadInst>( stack_top(bb) );
1314         LoadInst* w1 = cast<LoadInst>( stack_top(bb, One ) );
1315         incr_stack_index( bb, Two );
1316         replace_top( bb, w1, One );
1317         replace_top( bb, w2 );
1318         break;
1319     }
1320     case SWAP:  // w1 w2 -- w2 w1
1321     {
1322         if (echo) bb->setName("SWAP");
1323         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1324         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1325         replace_top( bb, w1 );
1326         replace_top( bb, w2, One );
1327         break;
1328     }
1329     case SWAP2: // w1 w2 w3 w4 -- w3 w4 w1 w2
1330     {
1331         if (echo) bb->setName("SWAP2");
1332         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1333         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1334         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1335         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three ) );
1336         replace_top( bb, w2 );
1337         replace_top( bb, w1, One );
1338         replace_top( bb, w4, Two );
1339         replace_top( bb, w3, Three );
1340         break;
1341     }
1342     case OVER:  // w1 w2 -- w1 w2 w1
1343     {
1344         if (echo) bb->setName("OVER");
1345         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1346         push_value( bb, w1 );
1347         break;
1348     }
1349     case OVER2: // w1 w2 w3 w4 -- w1 w2 w3 w4 w1 w2
1350     {
1351         if (echo) bb->setName("OVER2");
1352         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1353         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three ) );
1354         incr_stack_index( bb, Two );
1355         replace_top( bb, w2 );
1356         replace_top( bb, w1, One );
1357         break;
1358     }
1359     case ROT:   // w1 w2 w3 -- w2 w3 w1
1360     {
1361         if (echo) bb->setName("ROT");
1362         LoadInst* w3 = cast<LoadInst>( stack_top( bb ) );
1363         LoadInst* w2 = cast<LoadInst>( stack_top( bb, One ) );
1364         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Two ) );
1365         replace_top( bb, w1 );
1366         replace_top( bb, w3, One );
1367         replace_top( bb, w2, Two );
1368         break;
1369     }
1370     case ROT2:  // w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2
1371     {
1372         if (echo) bb->setName("ROT2");
1373         LoadInst* w6 = cast<LoadInst>( stack_top( bb ) );
1374         LoadInst* w5 = cast<LoadInst>( stack_top( bb, One ) );
1375         LoadInst* w4 = cast<LoadInst>( stack_top( bb, Two ) );
1376         LoadInst* w3 = cast<LoadInst>( stack_top( bb, Three) );
1377         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Four ) );
1378         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Five ) );
1379         replace_top( bb, w2 );
1380         replace_top( bb, w1, One );
1381         replace_top( bb, w6, Two );
1382         replace_top( bb, w5, Three );
1383         replace_top( bb, w4, Four );
1384         replace_top( bb, w3, Five );
1385         break;
1386     }
1387     case RROT:  // w1 w2 w3 -- w3 w1 w2
1388     {
1389         if (echo) bb->setName("RROT2");
1390         LoadInst* w3 = cast<LoadInst>( stack_top( bb ) );
1391         LoadInst* w2 = cast<LoadInst>( stack_top( bb, One ) );
1392         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Two ) );
1393         replace_top( bb, w2 );
1394         replace_top( bb, w1, One );
1395         replace_top( bb, w3, Two );
1396         break;
1397     }
1398     case RROT2: // w1 w2 w3 w4 w5 w6 -- w5 w6 w1 w2 w3 w4
1399     {
1400         if (echo) bb->setName("RROT2");
1401         LoadInst* w6 = cast<LoadInst>( stack_top( bb ) );
1402         LoadInst* w5 = cast<LoadInst>( stack_top( bb, One ) );
1403         LoadInst* w4 = cast<LoadInst>( stack_top( bb, Two ) );
1404         LoadInst* w3 = cast<LoadInst>( stack_top( bb, Three) );
1405         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Four ) );
1406         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Five ) );
1407         replace_top( bb, w4 );
1408         replace_top( bb, w3, One );
1409         replace_top( bb, w2, Two );
1410         replace_top( bb, w1, Three );
1411         replace_top( bb, w6, Four );
1412         replace_top( bb, w5, Five );
1413         break;
1414     }
1415     case TUCK:  // w1 w2 -- w2 w1 w2
1416     {
1417         if (echo) bb->setName("TUCK");
1418         LoadInst* w2 = cast<LoadInst>( stack_top( bb ) );
1419         LoadInst* w1 = cast<LoadInst>( stack_top( bb, One ) );
1420         incr_stack_index( bb );
1421         replace_top( bb, w2 );
1422         replace_top( bb, w1, One );
1423         replace_top( bb, w2, Two );
1424         break;
1425     }
1426     case TUCK2: // w1 w2 w3 w4 -- w3 w4 w1 w2 w3 w4
1427     {
1428         if (echo) bb->setName("TUCK2");
1429         LoadInst* w4 = cast<LoadInst>( stack_top( bb ) );
1430         LoadInst* w3 = cast<LoadInst>( stack_top( bb, One ) );
1431         LoadInst* w2 = cast<LoadInst>( stack_top( bb, Two ) );
1432         LoadInst* w1 = cast<LoadInst>( stack_top( bb, Three) );
1433         incr_stack_index( bb, Two );
1434         replace_top( bb, w4 );
1435         replace_top( bb, w3, One );
1436         replace_top( bb, w2, Two );
1437         replace_top( bb, w1, Three );
1438         replace_top( bb, w4, Four );
1439         replace_top( bb, w3, Five );
1440         break;
1441     }
1442     case ROLL:  // x0 x1 .. xn n -- x1 .. xn x0
1443     {
1444         /// THIS OEPRATOR IS OMITTED PURPOSEFULLY AND IS LEFT TO THE
1445         /// READER AS AN EXERCISE. THIS IS ONE OF THE MORE COMPLICATED
1446         /// OPERATORS. IF YOU CAN GET THIS ONE RIGHT, YOU COMPLETELY
1447         /// UNDERSTAND HOW BOTH LLVM AND STACKER WOR.
1448         /// HINT: LOOK AT PICK AND SELECT. ROLL IS SIMILAR.
1449         if (echo) bb->setName("ROLL");
1450         break;
1451     }
1452     case PICK:  // x0 ... Xn n -- x0 ... Xn x0
1453     {
1454         if (echo) bb->setName("PICK");
1455         LoadInst* n = cast<LoadInst>( stack_top( bb ) );
1456         BinaryOperator* addop =
1457             BinaryOperator::create( Instruction::Add, n, One );
1458         bb->getInstList().push_back( addop );
1459         LoadInst* x0 = cast<LoadInst>( stack_top( bb, addop ) );
1460         replace_top( bb, x0 );
1461         break;
1462     }
1463     case SELECT:        // m n X0..Xm Xm+1 .. Xn -- Xm
1464     {
1465         if (echo) bb->setName("SELECT");
1466         LoadInst* m = cast<LoadInst>( stack_top(bb) );
1467         LoadInst* n = cast<LoadInst>( stack_top(bb, One) );
1468         BinaryOperator* index =
1469             BinaryOperator::create( Instruction::Add, m, One );
1470         bb->getInstList().push_back( index );
1471         LoadInst* Xm = cast<LoadInst>( stack_top(bb, index ) );
1472         BinaryOperator* n_plus_1 =
1473             BinaryOperator::create( Instruction::Add, n, One );
1474         bb->getInstList().push_back( n_plus_1 );
1475         decr_stack_index( bb, n_plus_1 );
1476         replace_top( bb, Xm );
1477         break;
1478     }
1479     case MALLOC : // n -- p
1480     {
1481         if (echo) bb->setName("MALLOC");
1482         // Get the number of bytes to mallocate
1483         LoadInst* op1 = cast<LoadInst>( pop_integer(bb) );
1484
1485         // Make sure its a UIntTy
1486         CastInst* caster = CastInst::createTruncOrBitCast( op1, Type::UIntTy );
1487         bb->getInstList().push_back( caster );
1488
1489         // Allocate the bytes
1490         MallocInst* mi = new MallocInst( Type::SByteTy, caster );
1491         bb->getInstList().push_back( mi );
1492
1493         // Push the pointer
1494         push_value( bb, mi );
1495         break;
1496     }
1497     case FREE :  // p --
1498     {
1499         if (echo) bb->setName("FREE");
1500         // Pop the value off the stack
1501         CastInst* ptr = cast<CastInst>( pop_string(bb) );
1502
1503         // Free the memory
1504         FreeInst* fi = new FreeInst( ptr );
1505         bb->getInstList().push_back( fi );
1506
1507         break;
1508     }
1509     case GET : // p w1 -- p w2
1510     {
1511         if (echo) bb->setName("GET");
1512         // Get the character index
1513         LoadInst* op1 = cast<LoadInst>( stack_top(bb) );
1514         CastInst* chr_idx = CastInst::createSExtOrBitCast( op1, Type::LongTy );
1515         bb->getInstList().push_back( chr_idx );
1516
1517         // Get the String pointer
1518         CastInst* ptr = cast<CastInst>( stack_top_string(bb,One) );
1519
1520         // Get address of op1'th element of the string
1521         std::vector<Value*> indexVec;
1522         indexVec.push_back( chr_idx );
1523         GetElementPtrInst* gep = new GetElementPtrInst( ptr, indexVec );
1524         bb->getInstList().push_back( gep );
1525
1526         // Get the value and push it
1527         LoadInst* loader = new LoadInst( gep );
1528         bb->getInstList().push_back( loader );
1529         CastInst* caster = CastInst::createTruncOrBitCast(loader, Type::IntTy);
1530         bb->getInstList().push_back( caster );
1531
1532         // Push the result back on stack
1533         replace_top( bb, caster );
1534
1535         break;
1536     }
1537     case PUT : // p w2 w1  -- p
1538     {
1539         if (echo) bb->setName("PUT");
1540
1541         // Get the value to put
1542         LoadInst* w1 = cast<LoadInst>( pop_integer(bb) );
1543
1544         // Get the character index
1545         LoadInst* w2 = cast<LoadInst>( pop_integer(bb) );
1546         CastInst* chr_idx = CastInst::createSExtOrBitCast( w2, Type::LongTy );
1547         bb->getInstList().push_back( chr_idx );
1548
1549         // Get the String pointer
1550         CastInst* ptr = cast<CastInst>( stack_top_string(bb) );
1551
1552         // Get address of op2'th element of the string
1553         std::vector<Value*> indexVec;
1554         indexVec.push_back( chr_idx );
1555         GetElementPtrInst* gep = new GetElementPtrInst( ptr, indexVec );
1556         bb->getInstList().push_back( gep );
1557
1558         // Cast the value and put it
1559         CastInst* caster = new TruncInst( w1, Type::SByteTy );
1560         bb->getInstList().push_back( caster );
1561         StoreInst* storer = new StoreInst( caster, gep );
1562         bb->getInstList().push_back( storer );
1563
1564         break;
1565     }
1566     case RECURSE :
1567     {
1568         if (echo) bb->setName("RECURSE");
1569         std::vector<Value*> params;
1570         CallInst* call_inst = new CallInst( TheFunction, params );
1571         bb->getInstList().push_back( call_inst );
1572         break;
1573     }
1574     case RETURN :
1575     {
1576         if (echo) bb->setName("RETURN");
1577         bb->getInstList().push_back( new ReturnInst() );
1578         break;
1579     }
1580     case EXIT :
1581     {
1582         if (echo) bb->setName("EXIT");
1583         // Get the result value
1584         LoadInst* op1 = cast<LoadInst>(pop_integer(bb));
1585
1586         // Cast down to an integer
1587         CastInst* caster = new TruncInst( op1, Type::IntTy );
1588         bb->getInstList().push_back( caster );
1589
1590         // Call exit(3)
1591         std::vector<Value*> params;
1592         params.push_back(caster);
1593         CallInst* call_inst = new CallInst( TheExit, params );
1594         bb->getInstList().push_back( call_inst );
1595         break;
1596     }
1597     case TAB :
1598     {
1599         if (echo) bb->setName("TAB");
1600         // Get the format string for a character
1601         std::vector<Value*> indexVec;
1602         indexVec.push_back( Zero );
1603         indexVec.push_back( Zero );
1604         GetElementPtrInst* format_gep =
1605             new GetElementPtrInst( ChrFormat, indexVec );
1606         bb->getInstList().push_back( format_gep );
1607
1608         // Get the character to print (a tab)
1609         ConstantInt* newline = ConstantInt::get(Type::IntTy,
1610             static_cast<int>('\t'));
1611
1612         // Call printf
1613         std::vector<Value*> args;
1614         args.push_back( format_gep );
1615         args.push_back( newline );
1616         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1617         break;
1618     }
1619     case SPACE :
1620     {
1621         if (echo) bb->setName("SPACE");
1622         // Get the format string for a character
1623         std::vector<Value*> indexVec;
1624         indexVec.push_back( Zero );
1625         indexVec.push_back( Zero );
1626         GetElementPtrInst* format_gep =
1627             new GetElementPtrInst( ChrFormat, indexVec );
1628         bb->getInstList().push_back( format_gep );
1629
1630         // Get the character to print (a space)
1631         ConstantInt* newline = ConstantInt::get(Type::IntTy,
1632             static_cast<int>(' '));
1633
1634         // Call printf
1635         std::vector<Value*> args;
1636         args.push_back( format_gep );
1637         args.push_back( newline );
1638         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1639         break;
1640     }
1641     case CR :
1642     {
1643         if (echo) bb->setName("CR");
1644         // Get the format string for a character
1645         std::vector<Value*> indexVec;
1646         indexVec.push_back( Zero );
1647         indexVec.push_back( Zero );
1648         GetElementPtrInst* format_gep =
1649             new GetElementPtrInst( ChrFormat, indexVec );
1650         bb->getInstList().push_back( format_gep );
1651
1652         // Get the character to print (a newline)
1653         ConstantInt* newline = ConstantInt::get(Type::IntTy,
1654             static_cast<int>('\n'));
1655
1656         // Call printf
1657         std::vector<Value*> args;
1658         args.push_back( format_gep );
1659         args.push_back( newline );
1660         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1661         break;
1662     }
1663     case IN_STR :
1664     {
1665         if (echo) bb->setName("IN_STR");
1666         // Make room for the value result
1667         incr_stack_index(bb);
1668         GetElementPtrInst* gep_value =
1669           cast<GetElementPtrInst>(get_stack_pointer(bb));
1670         CastInst* caster =
1671           new BitCastInst(gep_value, PointerType::get(Type::SByteTy));
1672
1673         // Make room for the count result
1674         incr_stack_index(bb);
1675         GetElementPtrInst* gep_count =
1676             cast<GetElementPtrInst>(get_stack_pointer(bb));
1677
1678         // Call scanf(3)
1679         std::vector<Value*> args;
1680         args.push_back( InStrFormat );
1681         args.push_back( caster );
1682         CallInst* scanf = new CallInst( TheScanf, args );
1683         bb->getInstList().push_back( scanf );
1684
1685         // Store the result
1686         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1687         break;
1688     }
1689     case IN_NUM :
1690     {
1691         if (echo) bb->setName("IN_NUM");
1692         // Make room for the value result
1693         incr_stack_index(bb);
1694         GetElementPtrInst* gep_value =
1695             cast<GetElementPtrInst>(get_stack_pointer(bb));
1696
1697         // Make room for the count result
1698         incr_stack_index(bb);
1699         GetElementPtrInst* gep_count =
1700             cast<GetElementPtrInst>(get_stack_pointer(bb));
1701
1702         // Call scanf(3)
1703         std::vector<Value*> args;
1704         args.push_back( InStrFormat );
1705         args.push_back( gep_value );
1706         CallInst* scanf = new CallInst( TheScanf, args );
1707         bb->getInstList().push_back( scanf );
1708
1709         // Store the result
1710         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1711         break;
1712     }
1713     case IN_CHAR :
1714     {
1715         if (echo) bb->setName("IN_CHAR");
1716         // Make room for the value result
1717         incr_stack_index(bb);
1718         GetElementPtrInst* gep_value =
1719             cast<GetElementPtrInst>(get_stack_pointer(bb));
1720
1721         // Make room for the count result
1722         incr_stack_index(bb);
1723         GetElementPtrInst* gep_count =
1724             cast<GetElementPtrInst>(get_stack_pointer(bb));
1725
1726         // Call scanf(3)
1727         std::vector<Value*> args;
1728         args.push_back( InChrFormat );
1729         args.push_back( gep_value );
1730         CallInst* scanf = new CallInst( TheScanf, args );
1731         bb->getInstList().push_back( scanf );
1732
1733         // Store the result
1734         bb->getInstList().push_back( new StoreInst( scanf, gep_count ) );
1735         break;
1736     }
1737     case OUT_STR :
1738     {
1739         if (echo) bb->setName("OUT_STR");
1740         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1741
1742         // Get the address of the format string
1743         std::vector<Value*> indexVec;
1744         indexVec.push_back( Zero );
1745         indexVec.push_back( Zero );
1746         GetElementPtrInst* format_gep =
1747             new GetElementPtrInst( StrFormat, indexVec );
1748         bb->getInstList().push_back( format_gep );
1749         // Build function call arguments
1750         std::vector<Value*> args;
1751         args.push_back( format_gep );
1752         args.push_back( op1 );
1753         // Call printf
1754         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1755         break;
1756     }
1757     case OUT_NUM :
1758     {
1759         if (echo) bb->setName("OUT_NUM");
1760         // Pop the numeric operand off the stack
1761         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1762
1763         // Get the address of the format string
1764         std::vector<Value*> indexVec;
1765         indexVec.push_back( Zero );
1766         indexVec.push_back( Zero );
1767         GetElementPtrInst* format_gep =
1768             new GetElementPtrInst( NumFormat, indexVec );
1769         bb->getInstList().push_back( format_gep );
1770
1771         // Build function call arguments
1772         std::vector<Value*> args;
1773         args.push_back( format_gep );
1774         args.push_back( op1 );
1775
1776         // Call printf
1777         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1778         break;
1779     }
1780     case OUT_CHAR :
1781     {
1782         if (echo) bb->setName("OUT_CHAR");
1783         // Pop the character operand off the stack
1784         LoadInst* op1 = cast<LoadInst>(stack_top(bb));
1785
1786         // Get the address of the format string
1787         std::vector<Value*> indexVec;
1788         indexVec.push_back( Zero );
1789         indexVec.push_back( Zero );
1790         GetElementPtrInst* format_gep =
1791             new GetElementPtrInst( ChrFormat, indexVec );
1792         bb->getInstList().push_back( format_gep );
1793
1794         // Build function call arguments
1795         std::vector<Value*> args;
1796         args.push_back( format_gep );
1797         args.push_back( op1 );
1798         // Call printf
1799         bb->getInstList().push_back( new CallInst( ThePrintf, args ) );
1800         break;
1801     }
1802     default :
1803     {
1804         ThrowException(std::string("Compiler Error: Unhandled token #"));
1805     }
1806     }
1807
1808     // Return the basic block
1809     return bb;
1810 }