lib/AsmParser/llvmAsmParser.y

   1 //===-- llvmAsmParser.y - Parser for llvm assembly files ---------*- C++ -*--=//
   2 //
   3 //  This file implements the bison parser for LLVM assembly languages files.
   4 //
   5 //===------------------------------------------------------------------------=//
   6
   7 //
   8 // TODO: Parse comments and add them to an internal node... so that they may
   9 // be saved in the bytecode format as well as everything else.  Very important
  10 // for a general IR format.
  11 //
  12
  13 %{
  14 #include "ParserInternals.h"
  15 #include "llvm/BasicBlock.h"
  16 #include "llvm/Method.h"
  17 #include "llvm/SymbolTable.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/Type.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Assembly/Parser.h"
  22 #include "llvm/ConstantPool.h"
  23 #include "llvm/iTerminators.h"
  24 #include "llvm/iMemory.h"
  25 #include <list>
  26 #include <utility>            // Get definition of pair class
  27 #include <algorithm>          // Get definition of find_if
  28 #include <stdio.h>            // This embarasment is due to our flex lexer...
  29
  30 int yyerror(const char *ErrorMsg); // Forward declarations to prevent "implicit
  31 int yylex();                       // declaration" of xxx warnings.
  32 int yyparse();
  33
  34 static Module *ParserResult;
  35 string CurFilename;
  36
  37 // This contains info used when building the body of a method.  It is destroyed
  38 // when the method is completed.
  39 //
  40 typedef vector<Value *> ValueList;           // Numbered defs
  41 static void ResolveDefinitions(vector<ValueList> &LateResolvers);
  42
  43 static struct PerModuleInfo {
  44   Module *CurrentModule;
  45   vector<ValueList> Values;     // Module level numbered definitions
  46   vector<ValueList> LateResolveValues;
  47
  48   void ModuleDone() {
  49     // If we could not resolve some blocks at parsing time (forward branches)
  50     // resolve the branches now...
  51     ResolveDefinitions(LateResolveValues);
  52
  53     Values.clear();         // Clear out method local definitions
  54     CurrentModule = 0;
  55   }
  56 } CurModule;
  57
  58 static struct PerMethodInfo {
  59   Method *CurrentMethod;         // Pointer to current method being created
  60
  61   vector<ValueList> Values;      // Keep track of numbered definitions
  62   vector<ValueList> LateResolveValues;
  63   bool isDeclare;                // Is this method a forward declararation?
  64
  65   inline PerMethodInfo() {
  66     CurrentMethod = 0;
  67     isDeclare = false;
  68   }
  69
  70   inline ~PerMethodInfo() {}
  71
  72   inline void MethodStart(Method *M) {
  73     CurrentMethod = M;
  74   }
  75
  76   void MethodDone() {
  77     // If we could not resolve some blocks at parsing time (forward branches)
  78     // resolve the branches now...
  79     ResolveDefinitions(LateResolveValues);
  80
  81     Values.clear();         // Clear out method local definitions
  82     CurrentMethod = 0;
  83     isDeclare = false;
  84   }
  85 } CurMeth;  // Info for the current method...
  86
  87
  88 //===----------------------------------------------------------------------===//
  89 //               Code to handle definitions of all the types
  90 //===----------------------------------------------------------------------===//
  91
  92 static void InsertValue(Value *D, vector<ValueList> &ValueTab = CurMeth.Values) {
  93   if (!D->hasName()) {             // Is this a numbered definition?
  94     unsigned type = D->getType()->getUniqueID();
  95     if (ValueTab.size() <= type)
  96       ValueTab.resize(type+1, ValueList());
  97     //printf("Values[%d][%d] = %d\n", type, ValueTab[type].size(), D);
  98     ValueTab[type].push_back(D);
  99   }
 100 }
 101
 102 static Value *getVal(const Type *Type, ValID &D,
 103                      bool DoNotImprovise = false) {
 104   switch (D.Type) {
 105   case 0: {                 // Is it a numbered definition?
 106     unsigned type = Type->getUniqueID();
 107     unsigned Num = (unsigned)D.Num;
 108
 109     // Module constants occupy the lowest numbered slots...
 110     if (type < CurModule.Values.size()) {
 111       if (Num < CurModule.Values[type].size())
 112         return CurModule.Values[type][Num];
 113
 114       Num -= CurModule.Values[type].size();
 115     }
 116
 117     // Make sure that our type is within bounds
 118     if (CurMeth.Values.size() <= type)
 119       break;
 120
 121     // Check that the number is within bounds...
 122     if (CurMeth.Values[type].size() <= Num)
 123       break;
 124
 125     return CurMeth.Values[type][Num];
 126   }
 127   case 1: {                // Is it a named definition?
 128     string Name(D.Name);
 129     SymbolTable *SymTab = 0;
 130     if (CurMeth.CurrentMethod)
 131       SymTab = CurMeth.CurrentMethod->getSymbolTable();
 132     Value *N = SymTab ? SymTab->lookup(Type, Name) : 0;
 133
 134     if (N == 0) {
 135       SymTab = CurModule.CurrentModule->getSymbolTable();
 136       if (SymTab)
 137         N = SymTab->lookup(Type, Name);
 138       if (N == 0) break;
 139     }
 140
 141     D.destroy();  // Free old strdup'd memory...
 142     return N;
 143   }
 144
 145   case 2:                 // Is it a constant pool reference??
 146   case 3:                 // Is it an unsigned const pool reference?
 147   case 4:                 // Is it a string const pool reference?
 148   case 5:{                // Is it a floating point const pool reference?
 149     ConstPoolVal *CPV = 0;
 150
 151     // Check to make sure that "Type" is an integral type, and that our
 152     // value will fit into the specified type...
 153     switch (D.Type) {
 154     case 2:
 155       if (Type == Type::BoolTy) {  // Special handling for boolean data
 156         CPV = new ConstPoolBool(D.ConstPool64 != 0);
 157       } else {
 158         if (!ConstPoolSInt::isValueValidForType(Type, D.ConstPool64))
 159           ThrowException("Symbolic constant pool value '" +
 160                          itostr(D.ConstPool64) + "' is invalid for type '" +
 161                          Type->getName() + "'!");
 162         CPV = new ConstPoolSInt(Type, D.ConstPool64);
 163       }
 164       break;
 165     case 3:
 166       if (!ConstPoolUInt::isValueValidForType(Type, D.UConstPool64)) {
 167         if (!ConstPoolSInt::isValueValidForType(Type, D.ConstPool64)) {
 168           ThrowException("Integral constant pool reference is invalid!");
 169         } else {     // This is really a signed reference.  Transmogrify.
 170           CPV = new ConstPoolSInt(Type, D.ConstPool64);
 171         }
 172       } else {
 173         CPV = new ConstPoolUInt(Type, D.UConstPool64);
 174       }
 175       break;
 176     case 4:
 177       cerr << "FIXME: TODO: String constants [sbyte] not implemented yet!\n";
 178       abort();
 179       //CPV = new ConstPoolString(D.Name);
 180       D.destroy();   // Free the string memory
 181       break;
 182     case 5:
 183       if (!ConstPoolFP::isValueValidForType(Type, D.ConstPoolFP))
 184         ThrowException("FP constant invalid for type!!");
 185       else
 186         CPV = new ConstPoolFP(Type, D.ConstPoolFP);
 187       break;
 188     }
 189     assert(CPV && "How did we escape creating a constant??");
 190
 191     // Scan through the constant table and see if we already have loaded this
 192     // constant.
 193     //
 194     ConstantPool &CP = CurMeth.CurrentMethod ?
 195                          CurMeth.CurrentMethod->getConstantPool() :
 196                            CurModule.CurrentModule->getConstantPool();
 197     ConstPoolVal *C = CP.find(CPV);      // Already have this constant?
 198     if (C) {
 199       delete CPV;  // Didn't need this after all, oh well.
 200       return C;    // Yup, we already have one, recycle it!
 201     }
 202     CP.insert(CPV);
 203
 204     // Success, everything is kosher. Lets go!
 205     return CPV;
 206   }   // End of case 2,3,4
 207   }   // End of switch
 208
 209
 210   // If we reached here, we referenced either a symbol that we don't know about
 211   // or an id number that hasn't been read yet.  We may be referencing something
 212   // forward, so just create an entry to be resolved later and get to it...
 213   //
 214   if (DoNotImprovise) return 0;  // Do we just want a null to be returned?
 215
 216   // TODO: Attempt to coallecse nodes that are the same with previous ones.
 217   Value *d = 0;
 218   switch (Type->getPrimitiveID()) {
 219   case Type::LabelTyID: d = new    BBPlaceHolder(Type, D); break;
 220   case Type::MethodTyID:
 221     d = new MethPlaceHolder(Type, D);
 222     InsertValue(d, CurModule.LateResolveValues);
 223     return d;
 224 //case Type::ClassTyID:      d = new ClassPlaceHolder(Type, D); break;
 225   default:                   d = new   DefPlaceHolder(Type, D); break;
 226   }
 227
 228   assert(d != 0 && "How did we not make something?");
 229   InsertValue(d, CurMeth.LateResolveValues);
 230   return d;
 231 }
 232
 233
 234 //===----------------------------------------------------------------------===//
 235 //              Code to handle forward references in instructions
 236 //===----------------------------------------------------------------------===//
 237 //
 238 // This code handles the late binding needed with statements that reference
 239 // values not defined yet... for example, a forward branch, or the PHI node for
 240 // a loop body.
 241 //
 242 // This keeps a table (CurMeth.LateResolveValues) of all such forward references
 243 // and back patchs after we are done.
 244 //
 245
 246 // ResolveDefinitions - If we could not resolve some defs at parsing
 247 // time (forward branches, phi functions for loops, etc...) resolve the
 248 // defs now...
 249 //
 250 static void ResolveDefinitions(vector<ValueList> &LateResolvers) {
 251   // Loop over LateResolveDefs fixing up stuff that couldn't be resolved
 252   for (unsigned ty = 0; ty < LateResolvers.size(); ty++) {
 253     while (!LateResolvers[ty].empty()) {
 254       Value *V = LateResolvers[ty].back();
 255       LateResolvers[ty].pop_back();
 256       ValID &DID = getValIDFromPlaceHolder(V);
 257
 258       Value *TheRealValue = getVal(Type::getUniqueIDType(ty), DID, true);
 259
 260       if (TheRealValue == 0 && DID.Type == 1)
 261         ThrowException("Reference to an invalid definition: '" +DID.getName() +
 262                        "' of type '" + V->getType()->getName() + "'");
 263       else if (TheRealValue == 0)
 264         ThrowException("Reference to an invalid definition: #" +itostr(DID.Num)+
 265                        " of type '" + V->getType()->getName() + "'");
 266
 267       V->replaceAllUsesWith(TheRealValue);
 268       assert(V->use_empty());
 269       delete V;
 270     }
 271   }
 272
 273   LateResolvers.clear();
 274 }
 275
 276 // addConstValToConstantPool - This code is used to insert a constant into the
 277 // current constant pool.  This is designed to make maximal (but not more than
 278 // possible) reuse (merging) of constants in the constant pool.  This means that
 279 // multiple references to %4, for example will all get merged.
 280 //
 281 static ConstPoolVal *addConstValToConstantPool(ConstPoolVal *C) {
 282   vector<ValueList> &ValTab = CurMeth.CurrentMethod ?
 283                                   CurMeth.Values : CurModule.Values;
 284   ConstantPool &CP = CurMeth.CurrentMethod ?
 285                           CurMeth.CurrentMethod->getConstantPool() :
 286                           CurModule.CurrentModule->getConstantPool();
 287
 288   if (ConstPoolVal *CPV = CP.find(C)) {
 289     // Constant already in constant pool. Try to merge the two constants
 290     if (CPV->hasName() && !C->hasName()) {
 291       // Merge the two values, we inherit the existing CPV's name.
 292       // InsertValue requires that the value have no name to insert correctly
 293       // (because we want to fill the slot this constant would have filled)
 294       //
 295       string Name = CPV->getName();
 296       CPV->setName("");
 297       InsertValue(CPV, ValTab);
 298       CPV->setName(Name);
 299       delete C;
 300       return CPV;
 301     } else if (!CPV->hasName() && C->hasName()) {
 302       // If we have a name on this value and there isn't one in the const
 303       // pool val already, propogate it.
 304       //
 305       CPV->setName(C->getName());
 306       delete C;   // Sorry, you're toast
 307       return CPV;
 308     } else if (CPV->hasName() && C->hasName()) {
 309       // Both values have distinct names.  We cannot merge them.
 310       CP.insert(C);
 311       InsertValue(C, ValTab);
 312       return C;
 313     } else if (!CPV->hasName() && !C->hasName()) {
 314       // Neither value has a name, trivially merge them.
 315       InsertValue(CPV, ValTab);
 316       delete C;
 317       return CPV;
 318     }
 319
 320     assert(0 && "Not reached!");
 321     return 0;
 322   } else {           // No duplication of value.
 323     CP.insert(C);
 324     InsertValue(C, ValTab);
 325     return C;
 326   }
 327 }
 328
 329
 330 struct EqualsType {
 331   const Type *T;
 332   inline EqualsType(const Type *t) { T = t; }
 333   inline bool operator()(const ConstPoolVal *CPV) const {
 334     return static_cast<const ConstPoolType*>(CPV)->getValue() == T;
 335   }
 336 };
 337
 338
 339 // checkNewType - We have to be careful to add all types referenced by the
 340 // program to the constant pool of the method or module.  Because of this, we
 341 // often want to check to make sure that types used are in the constant pool,
 342 // and add them if they aren't.  That's what this function does.
 343 //
 344 static const Type *checkNewType(const Type *Ty) {
 345   ConstantPool &CP = CurMeth.CurrentMethod ?
 346                           CurMeth.CurrentMethod->getConstantPool() :
 347                           CurModule.CurrentModule->getConstantPool();
 348
 349   // TODO: This should use ConstantPool::ensureTypeAvailable
 350
 351   // Get the type type plane...
 352   ConstantPool::PlaneType &P = CP.getPlane(Type::TypeTy);
 353   ConstantPool::PlaneType::const_iterator PI = find_if(P.begin(), P.end(),
 354                                                        EqualsType(Ty));
 355   if (PI == P.end()) {
 356     vector<ValueList> &ValTab = CurMeth.CurrentMethod ?
 357                                 CurMeth.Values : CurModule.Values;
 358     ConstPoolVal *CPT = new ConstPoolType(Ty);
 359     CP.insert(CPT);
 360     InsertValue(CPT, ValTab);
 361   }
 362   return Ty;
 363 }
 364
 365
 366 //===----------------------------------------------------------------------===//
 367 //            RunVMAsmParser - Define an interface to this parser
 368 //===----------------------------------------------------------------------===//
 369 //
 370 Module *RunVMAsmParser(const string &Filename, FILE *F) {
 371   llvmAsmin = F;
 372   CurFilename = Filename;
 373   llvmAsmlineno = 1;      // Reset the current line number...
 374
 375   CurModule.CurrentModule = new Module();  // Allocate a new module to read
 376   yyparse();       // Parse the file.
 377   Module *Result = ParserResult;
 378   llvmAsmin = stdin;    // F is about to go away, don't use it anymore...
 379   ParserResult = 0;
 380
 381   return Result;
 382 }
 383
 384 %}
 385
 386 %union {
 387   Module                  *ModuleVal;
 388   Method                  *MethodVal;
 389   MethodArgument          *MethArgVal;
 390   BasicBlock              *BasicBlockVal;
 391   TerminatorInst          *TermInstVal;
 392   Instruction             *InstVal;
 393   ConstPoolVal            *ConstVal;
 394   const Type              *TypeVal;
 395
 396   list<MethodArgument*>   *MethodArgList;
 397   list<Value*>            *ValueList;
 398   list<const Type*>       *TypeList;
 399   list<pair<Value*, BasicBlock*> > *PHIList;   // Represent the RHS of PHI node
 400   list<pair<ConstPoolVal*, BasicBlock*> > *JumpTable;
 401   vector<ConstPoolVal*>   *ConstVector;
 402
 403   int64_t                  SInt64Val;
 404   uint64_t                 UInt64Val;
 405   int                      SIntVal;
 406   unsigned                 UIntVal;
 407   double                   FPVal;
 408
 409   char                    *StrVal;   // This memory is allocated by strdup!
 410   ValID                    ValIDVal; // May contain memory allocated by strdup
 411
 412   Instruction::UnaryOps    UnaryOpVal;
 413   Instruction::BinaryOps   BinaryOpVal;
 414   Instruction::TermOps     TermOpVal;
 415   Instruction::MemoryOps   MemOpVal;
 416   Instruction::OtherOps    OtherOpVal;
 417 }
 418
 419 %type <ModuleVal>     Module MethodList
 420 %type <MethodVal>     Method MethodProto MethodHeader BasicBlockList
 421 %type <BasicBlockVal> BasicBlock InstructionList
 422 %type <TermInstVal>   BBTerminatorInst
 423 %type <InstVal>       Inst InstVal MemoryInst
 424 %type <ConstVal>      ConstVal
 425 %type <ConstVector>   ConstVector UByteList
 426 %type <MethodArgList> ArgList ArgListH
 427 %type <MethArgVal>    ArgVal
 428 %type <PHIList>       PHIList
 429 %type <ValueList>     ValueRefList ValueRefListE  // For call param lists
 430 %type <TypeList>      TypeList
 431 %type <JumpTable>     JumpTable
 432
 433 %type <ValIDVal>      ValueRef ConstValueRef // Reference to a definition or BB
 434
 435 // Tokens and types for handling constant integer values
 436 //
 437 // ESINT64VAL - A negative number within long long range
 438 %token <SInt64Val> ESINT64VAL
 439
 440 // EUINT64VAL - A positive number within uns. long long range
 441 %token <UInt64Val> EUINT64VAL
 442 %type  <SInt64Val> EINT64VAL
 443
 444 %token  <SIntVal>   SINTVAL   // Signed 32 bit ints...
 445 %token  <UIntVal>   UINTVAL   // Unsigned 32 bit ints...
 446 %type   <SIntVal>   INTVAL
 447 %token  <FPVal>     FPVAL     // Float or Double constant
 448
 449 // Built in types...
 450 %type  <TypeVal> Types TypesV SIntType UIntType IntType FPType
 451 %token <TypeVal> VOID BOOL SBYTE UBYTE SHORT USHORT INT UINT LONG ULONG
 452 %token <TypeVal> FLOAT DOUBLE STRING TYPE LABEL
 453
 454 %token <StrVal>     VAR_ID LABELSTR STRINGCONSTANT
 455 %type  <StrVal>  OptVAR_ID OptAssign
 456
 457
 458 %token IMPLEMENTATION TRUE FALSE BEGINTOK END DECLARE TO
 459
 460 // Basic Block Terminating Operators
 461 %token <TermOpVal> RET BR SWITCH
 462
 463 // Unary Operators
 464 %type  <UnaryOpVal> UnaryOps  // all the unary operators
 465 %token <UnaryOpVal> NOT
 466
 467 // Binary Operators
 468 %type  <BinaryOpVal> BinaryOps  // all the binary operators
 469 %token <BinaryOpVal> ADD SUB MUL DIV REM
 470 %token <BinaryOpVal> SETLE SETGE SETLT SETGT SETEQ SETNE  // Binary Comarators
 471
 472 // Memory Instructions
 473 %token <MemoryOpVal> MALLOC ALLOCA FREE LOAD STORE GETELEMENTPTR
 474
 475 // Other Operators
 476 %type  <OtherOpVal> ShiftOps
 477 %token <OtherOpVal> PHI CALL CAST SHL SHR
 478
 479 %start Module
 480 %%
 481
 482 // Handle constant integer size restriction and conversion...
 483 //
 484
 485 INTVAL : SINTVAL
 486 INTVAL : UINTVAL {
 487   if ($1 > (uint32_t)INT32_MAX)     // Outside of my range!
 488     ThrowException("Value too large for type!");
 489   $$ = (int32_t)$1;
 490 }
 491
 492
 493 EINT64VAL : ESINT64VAL       // These have same type and can't cause problems...
 494 EINT64VAL : EUINT64VAL {
 495   if ($1 > (uint64_t)INT64_MAX)     // Outside of my range!
 496     ThrowException("Value too large for type!");
 497   $$ = (int64_t)$1;
 498 }
 499
 500 // Types includes all predefined types... except void, because you can't do
 501 // anything with it except for certain specific things...
 502 //
 503 // User defined types are added later...
 504 //
 505 Types     : BOOL | SBYTE | UBYTE | SHORT | USHORT | INT | UINT
 506 Types     : LONG | ULONG | FLOAT | DOUBLE | STRING | TYPE | LABEL
 507
 508 // TypesV includes all of 'Types', but it also includes the void type.
 509 TypesV    : Types | VOID
 510
 511 // Operations that are notably excluded from this list include:
 512 // RET, BR, & SWITCH because they end basic blocks and are treated specially.
 513 //
 514 UnaryOps  : NOT
 515 BinaryOps : ADD | SUB | MUL | DIV | REM
 516 BinaryOps : SETLE | SETGE | SETLT | SETGT | SETEQ | SETNE
 517 ShiftOps  : SHL | SHR
 518
 519 // These are some types that allow classification if we only want a particular
 520 // thing... for example, only a signed, unsigned, or integral type.
 521 SIntType :  LONG |  INT |  SHORT | SBYTE
 522 UIntType : ULONG | UINT | USHORT | UBYTE
 523 IntType : SIntType | UIntType
 524 FPType  : FLOAT | DOUBLE
 525
 526 // OptAssign - Value producing statements have an optional assignment component
 527 OptAssign : VAR_ID '=' {
 528     $$ = $1;
 529   }
 530   | /*empty*/ {
 531     $$ = 0;
 532   }
 533
 534 // ConstVal - The various declarations that go into the constant pool.  This
 535 // includes all forward declarations of types, constants, and functions.
 536 //
 537 ConstVal : SIntType EINT64VAL {     // integral constants
 538     if (!ConstPoolSInt::isValueValidForType($1, $2))
 539       ThrowException("Constant value doesn't fit in type!");
 540     $$ = new ConstPoolSInt($1, $2);
 541   }
 542   | UIntType EUINT64VAL {           // integral constants
 543     if (!ConstPoolUInt::isValueValidForType($1, $2))
 544       ThrowException("Constant value doesn't fit in type!");
 545     $$ = new ConstPoolUInt($1, $2);
 546   }
 547   | BOOL TRUE {                     // Boolean constants
 548     $$ = new ConstPoolBool(true);
 549   }
 550   | BOOL FALSE {                    // Boolean constants
 551     $$ = new ConstPoolBool(false);
 552   }
 553   | FPType FPVAL {                   // Float & Double constants
 554     $$ = new ConstPoolFP($1, $2);
 555   }
 556   | STRING STRINGCONSTANT {         // String constants
 557     cerr << "FIXME: TODO: String constants [sbyte] not implemented yet!\n";
 558     abort();
 559     //$$ = new ConstPoolString($2);
 560     free($2);
 561   }
 562   | TYPE Types {                    // Type constants
 563     $$ = new ConstPoolType($2);
 564   }
 565   | '[' Types ']' '[' ConstVector ']' {      // Nonempty array constant
 566     // Verify all elements are correct type!
 567     const ArrayType *AT = ArrayType::getArrayType($2);
 568     for (unsigned i = 0; i < $5->size(); i++) {
 569       if ($2 != (*$5)[i]->getType())
 570         ThrowException("Element #" + utostr(i) + " is not of type '" +
 571                        $2->getName() + "' as required!\nIt is of type '" +
 572                        (*$5)[i]->getType()->getName() + "'.");
 573     }
 574
 575     $$ = new ConstPoolArray(AT, *$5);
 576     delete $5;
 577   }
 578   | '[' Types ']' '[' ']' {                  // Empty array constant
 579     vector<ConstPoolVal*> Empty;
 580     $$ = new ConstPoolArray(ArrayType::getArrayType($2), Empty);
 581   }
 582   | '[' EUINT64VAL 'x' Types ']' '[' ConstVector ']' {
 583     // Verify all elements are correct type!
 584     const ArrayType *AT = ArrayType::getArrayType($4, (int)$2);
 585     if ($2 != $7->size())
 586       ThrowException("Type mismatch: constant sized array initialized with " +
 587                      utostr($7->size()) +  " arguments, but has size of " +
 588                      itostr((int)$2) + "!");
 589
 590     for (unsigned i = 0; i < $7->size(); i++) {
 591       if ($4 != (*$7)[i]->getType())
 592         ThrowException("Element #" + utostr(i) + " is not of type '" +
 593                        $4->getName() + "' as required!\nIt is of type '" +
 594                        (*$7)[i]->getType()->getName() + "'.");
 595     }
 596
 597     $$ = new ConstPoolArray(AT, *$7);
 598     delete $7;
 599   }
 600   | '[' EUINT64VAL 'x' Types ']' '[' ']' {
 601     if ($2 != 0)
 602       ThrowException("Type mismatch: constant sized array initialized with 0"
 603                      " arguments, but has size of " + itostr((int)$2) + "!");
 604     vector<ConstPoolVal*> Empty;
 605     $$ = new ConstPoolArray(ArrayType::getArrayType($4, 0), Empty);
 606   }
 607   | '{' TypeList '}' '{' ConstVector '}' {
 608     StructType::ElementTypes Types($2->begin(), $2->end());
 609     delete $2;
 610
 611     const StructType *St = StructType::getStructType(Types);
 612     $$ = new ConstPoolStruct(St, *$5);
 613     delete $5;
 614   }
 615   | '{' '}' '{' '}' {
 616     const StructType *St =
 617       StructType::getStructType(StructType::ElementTypes());
 618     vector<ConstPoolVal*> Empty;
 619     $$ = new ConstPoolStruct(St, Empty);
 620   }
 621 /*
 622   | Types '*' ConstVal {
 623     assert(0);
 624     $$ = 0;
 625   }
 626 */
 627
 628 // ConstVector - A list of comma seperated constants.
 629 ConstVector : ConstVector ',' ConstVal {
 630     ($$ = $1)->push_back(addConstValToConstantPool($3));
 631   }
 632   | ConstVal {
 633     $$ = new vector<ConstPoolVal*>();
 634     $$->push_back(addConstValToConstantPool($1));
 635   }
 636
 637 //ExternMethodDecl : EXTERNAL TypesV '(' TypeList ')' {
 638 //  }
 639 //ExternVarDecl :
 640
 641 // ConstPool - Constants with optional names assigned to them.
 642 ConstPool : ConstPool OptAssign ConstVal {
 643     if ($2) {
 644       $3->setName($2);
 645       free($2);
 646     }
 647
 648     addConstValToConstantPool($3);
 649   }
 650 /*
 651   | ConstPool OptAssign GlobalDecl {     // Global declarations appear in CP
 652     if ($2) {
 653       $3->setName($2);
 654       free($2);
 655     }
 656     //CurModule.CurrentModule->
 657   }
 658 */
 659   | /* empty: end of list */ {
 660   }
 661
 662
 663 //===----------------------------------------------------------------------===//
 664 //                             Rules to match Modules
 665 //===----------------------------------------------------------------------===//
 666
 667 // Module rule: Capture the result of parsing the whole file into a result
 668 // variable...
 669 //
 670 Module : MethodList {
 671   $$ = ParserResult = $1;
 672   CurModule.ModuleDone();
 673 }
 674
 675 // MethodList - A list of methods, preceeded by a constant pool.
 676 //
 677 MethodList : MethodList Method {
 678     $$ = $1;
 679     if (!$2->getParent())
 680       $1->getMethodList().push_back($2);
 681     CurMeth.MethodDone();
 682   }
 683   | MethodList MethodProto {
 684     $$ = $1;
 685     if (!$2->getParent())
 686       $1->getMethodList().push_back($2);
 687     CurMeth.MethodDone();
 688   }
 689   | ConstPool IMPLEMENTATION {
 690     $$ = CurModule.CurrentModule;
 691   }
 692
 693
 694 //===----------------------------------------------------------------------===//
 695 //                       Rules to match Method Headers
 696 //===----------------------------------------------------------------------===//
 697
 698 OptVAR_ID : VAR_ID | /*empty*/ { $$ = 0; }
 699
 700 ArgVal : Types OptVAR_ID {
 701   $$ = new MethodArgument($1);
 702   if ($2) {      // Was the argument named?
 703     $$->setName($2);
 704     free($2);    // The string was strdup'd, so free it now.
 705   }
 706 }
 707
 708 ArgListH : ArgVal ',' ArgListH {
 709     $$ = $3;
 710     $3->push_front($1);
 711   }
 712   | ArgVal {
 713     $$ = new list<MethodArgument*>();
 714     $$->push_front($1);
 715   }
 716
 717 ArgList : ArgListH {
 718     $$ = $1;
 719   }
 720   | /* empty */ {
 721     $$ = 0;
 722   }
 723
 724 MethodHeaderH : TypesV STRINGCONSTANT '(' ArgList ')' {
 725   MethodType::ParamTypes ParamTypeList;
 726   if ($4)
 727     for (list<MethodArgument*>::iterator I = $4->begin(); I != $4->end(); ++I)
 728       ParamTypeList.push_back((*I)->getType());
 729
 730   const MethodType *MT = MethodType::getMethodType($1, ParamTypeList);
 731
 732   Method *M = 0;
 733   if (SymbolTable *ST = CurModule.CurrentModule->getSymbolTable()) {
 734     if (Value *V = ST->lookup(MT, $2)) {  // Method already in symtab?
 735       M = V->castMethodAsserting();
 736
 737       // Yes it is.  If this is the case, either we need to be a forward decl,
 738       // or it needs to be.
 739       if (!CurMeth.isDeclare && !M->isExternal())
 740         ThrowException("Redefinition of method '" + string($2) + "'!");
 741     }
 742   }
 743
 744   if (M == 0) {  // Not already defined?
 745     M = new Method(MT, $2);
 746     InsertValue(M, CurModule.Values);
 747   }
 748
 749   free($2);  // Free strdup'd memory!
 750
 751   CurMeth.MethodStart(M);
 752
 753   // Add all of the arguments we parsed to the method...
 754   if ($4 && !CurMeth.isDeclare) {        // Is null if empty...
 755     Method::ArgumentListType &ArgList = M->getArgumentList();
 756
 757     for (list<MethodArgument*>::iterator I = $4->begin(); I != $4->end(); ++I) {
 758       InsertValue(*I);
 759       ArgList.push_back(*I);
 760     }
 761     delete $4;                     // We're now done with the argument list
 762   }
 763 }
 764
 765 MethodHeader : MethodHeaderH ConstPool BEGINTOK {
 766   $$ = CurMeth.CurrentMethod;
 767 }
 768
 769 Method : BasicBlockList END {
 770   $$ = $1;
 771 }
 772
 773 MethodProto : DECLARE { CurMeth.isDeclare = true; } MethodHeaderH {
 774   $$ = CurMeth.CurrentMethod;
 775 }
 776
 777 //===----------------------------------------------------------------------===//
 778 //                        Rules to match Basic Blocks
 779 //===----------------------------------------------------------------------===//
 780
 781 ConstValueRef : ESINT64VAL {    // A reference to a direct constant
 782     $$ = ValID::create($1);
 783   }
 784   | EUINT64VAL {
 785     $$ = ValID::create($1);
 786   }
 787   | FPVAL {                     // Perhaps it's an FP constant?
 788     $$ = ValID::create($1);
 789   }
 790   | TRUE {
 791     $$ = ValID::create((int64_t)1);
 792   }
 793   | FALSE {
 794     $$ = ValID::create((int64_t)0);
 795   }
 796   | STRINGCONSTANT {        // Quoted strings work too... especially for methods
 797     $$ = ValID::create_conststr($1);
 798   }
 799
 800 // ValueRef - A reference to a definition...
 801 ValueRef : INTVAL {           // Is it an integer reference...?
 802     $$ = ValID::create($1);
 803   }
 804   | VAR_ID {                 // Is it a named reference...?
 805     $$ = ValID::create($1);
 806   }
 807   | ConstValueRef {
 808     $$ = $1;
 809   }
 810
 811 // The user may refer to a user defined type by its typeplane... check for this
 812 // now...
 813 //
 814 Types : ValueRef {
 815     Value *D = getVal(Type::TypeTy, $1, true);
 816     if (D == 0) ThrowException("Invalid user defined type: " + $1.getName());
 817
 818     // User defined type not in const pool!
 819     ConstPoolType *CPT = (ConstPoolType*)D->castConstantAsserting();
 820     $$ = CPT->getValue();
 821   }
 822   | TypesV '(' TypeList ')' {               // Method derived type?
 823     MethodType::ParamTypes Params($3->begin(), $3->end());
 824     delete $3;
 825     $$ = checkNewType(MethodType::getMethodType($1, Params));
 826   }
 827   | TypesV '(' ')' {               // Method derived type?
 828     MethodType::ParamTypes Params;     // Empty list
 829     $$ = checkNewType(MethodType::getMethodType($1, Params));
 830   }
 831   | '[' Types ']' {
 832     $$ = checkNewType(ArrayType::getArrayType($2));
 833   }
 834   | '[' EUINT64VAL 'x' Types ']' {
 835     $$ = checkNewType(ArrayType::getArrayType($4, (int)$2));
 836   }
 837   | '{' TypeList '}' {
 838     StructType::ElementTypes Elements($2->begin(), $2->end());
 839     delete $2;
 840     $$ = checkNewType(StructType::getStructType(Elements));
 841   }
 842   | '{' '}' {
 843     $$ = checkNewType(StructType::getStructType(StructType::ElementTypes()));
 844   }
 845   | Types '*' {
 846     $$ = checkNewType(PointerType::getPointerType($1));
 847   }
 848
 849
 850 TypeList : Types {
 851     $$ = new list<const Type*>();
 852     $$->push_back($1);
 853   }
 854   | TypeList ',' Types {
 855     ($$=$1)->push_back($3);
 856   }
 857
 858
 859 BasicBlockList : BasicBlockList BasicBlock {
 860     $1->getBasicBlocks().push_back($2);
 861     $$ = $1;
 862   }
 863   | MethodHeader BasicBlock { // Do not allow methods with 0 basic blocks
 864     $$ = $1;                  // in them...
 865     $1->getBasicBlocks().push_back($2);
 866   }
 867
 868
 869 // Basic blocks are terminated by branching instructions:
 870 // br, br/cc, switch, ret
 871 //
 872 BasicBlock : InstructionList BBTerminatorInst  {
 873     $1->getInstList().push_back($2);
 874     InsertValue($1);
 875     $$ = $1;
 876   }
 877   | LABELSTR InstructionList BBTerminatorInst  {
 878     $2->getInstList().push_back($3);
 879     $2->setName($1);
 880     free($1);         // Free the strdup'd memory...
 881
 882     InsertValue($2);
 883     $$ = $2;
 884   }
 885
 886 InstructionList : InstructionList Inst {
 887     $1->getInstList().push_back($2);
 888     $$ = $1;
 889   }
 890   | /* empty */ {
 891     $$ = new BasicBlock();
 892   }
 893
 894 BBTerminatorInst : RET Types ValueRef {              // Return with a result...
 895     $$ = new ReturnInst(getVal($2, $3));
 896   }
 897   | RET VOID {                                       // Return with no result...
 898     $$ = new ReturnInst();
 899   }
 900   | BR LABEL ValueRef {                         // Unconditional Branch...
 901     $$ = new BranchInst((BasicBlock*)getVal(Type::LabelTy, $3));
 902   }                                                  // Conditional Branch...
 903   | BR BOOL ValueRef ',' LABEL ValueRef ',' LABEL ValueRef {
 904     $$ = new BranchInst((BasicBlock*)getVal(Type::LabelTy, $6),
 905                         (BasicBlock*)getVal(Type::LabelTy, $9),
 906                         getVal(Type::BoolTy, $3));
 907   }
 908   | SWITCH IntType ValueRef ',' LABEL ValueRef '[' JumpTable ']' {
 909     SwitchInst *S = new SwitchInst(getVal($2, $3),
 910                                    (BasicBlock*)getVal(Type::LabelTy, $6));
 911     $$ = S;
 912
 913     list<pair<ConstPoolVal*, BasicBlock*> >::iterator I = $8->begin(),
 914                                                       end = $8->end();
 915     for (; I != end; ++I)
 916       S->dest_push_back(I->first, I->second);
 917   }
 918
 919 JumpTable : JumpTable IntType ConstValueRef ',' LABEL ValueRef {
 920     $$ = $1;
 921     ConstPoolVal *V = (ConstPoolVal*)getVal($2, $3, true);
 922     if (V == 0)
 923       ThrowException("May only switch on a constant pool value!");
 924
 925     $$->push_back(make_pair(V, (BasicBlock*)getVal($5, $6)));
 926   }
 927   | IntType ConstValueRef ',' LABEL ValueRef {
 928     $$ = new list<pair<ConstPoolVal*, BasicBlock*> >();
 929     ConstPoolVal *V = (ConstPoolVal*)getVal($1, $2, true);
 930
 931     if (V == 0)
 932       ThrowException("May only switch on a constant pool value!");
 933
 934     $$->push_back(make_pair(V, (BasicBlock*)getVal($4, $5)));
 935   }
 936
 937 Inst : OptAssign InstVal {
 938   if ($1)              // Is this definition named??
 939     $2->setName($1);   // if so, assign the name...
 940
 941   InsertValue($2);
 942   $$ = $2;
 943 }
 944
 945 PHIList : Types '[' ValueRef ',' ValueRef ']' {    // Used for PHI nodes
 946     $$ = new list<pair<Value*, BasicBlock*> >();
 947     $$->push_back(make_pair(getVal($1, $3),
 948                             (BasicBlock*)getVal(Type::LabelTy, $5)));
 949   }
 950   | PHIList ',' '[' ValueRef ',' ValueRef ']' {
 951     $$ = $1;
 952     $1->push_back(make_pair(getVal($1->front().first->getType(), $4),
 953                             (BasicBlock*)getVal(Type::LabelTy, $6)));
 954   }
 955
 956
 957 ValueRefList : Types ValueRef {    // Used for call statements...
 958     $$ = new list<Value*>();
 959     $$->push_back(getVal($1, $2));
 960   }
 961   | ValueRefList ',' Types ValueRef {
 962     $$ = $1;
 963     $1->push_back(getVal($3, $4));
 964   }
 965
 966 // ValueRefListE - Just like ValueRefList, except that it may also be empty!
 967 ValueRefListE : ValueRefList | /*empty*/ { $$ = 0; }
 968
 969 InstVal : BinaryOps Types ValueRef ',' ValueRef {
 970     $$ = BinaryOperator::create($1, getVal($2, $3), getVal($2, $5));
 971     if ($$ == 0)
 972       ThrowException("binary operator returned null!");
 973   }
 974   | UnaryOps Types ValueRef {
 975     $$ = UnaryOperator::create($1, getVal($2, $3));
 976     if ($$ == 0)
 977       ThrowException("unary operator returned null!");
 978   }
 979   | ShiftOps Types ValueRef ',' Types ValueRef {
 980     if ($5 != Type::UByteTy) ThrowException("Shift amount must be ubyte!");
 981     $$ = new ShiftInst($1, getVal($2, $3), getVal($5, $6));
 982   }
 983   | CAST Types ValueRef TO Types {
 984     $$ = new CastInst(getVal($2, $3), $5);
 985   }
 986   | PHI PHIList {
 987     const Type *Ty = $2->front().first->getType();
 988     $$ = new PHINode(Ty);
 989     while ($2->begin() != $2->end()) {
 990       if ($2->front().first->getType() != Ty)
 991         ThrowException("All elements of a PHI node must be of the same type!");
 992       ((PHINode*)$$)->addIncoming($2->front().first, $2->front().second);
 993       $2->pop_front();
 994     }
 995     delete $2;  // Free the list...
 996   }
 997   | CALL Types ValueRef '(' ValueRefListE ')' {
 998     if (!$2->isMethodType())
 999       ThrowException("Can only call methods: invalid type '" +
1000                      $2->getName() + "'!");
1001
1002     const MethodType *Ty = (const MethodType*)$2;
1003
1004     Value *V = getVal(Ty, $3);
1005     if (!V->isMethod() || V->getType() != Ty)
1006       ThrowException("Cannot call: " + $3.getName() + "!");
1007
1008     // Create or access a new type that corresponds to the function call...
1009     vector<Value *> Params;
1010
1011     if ($5) {
1012       // Pull out just the arguments...
1013       Params.insert(Params.begin(), $5->begin(), $5->end());
1014       delete $5;
1015
1016       // Loop through MethodType's arguments and ensure they are specified
1017       // correctly!
1018       //
1019       MethodType::ParamTypes::const_iterator I = Ty->getParamTypes().begin();
1020       unsigned i;
1021       for (i = 0; i < Params.size() && I != Ty->getParamTypes().end(); ++i,++I){
1022         if (Params[i]->getType() != *I)
1023           ThrowException("Parameter " + utostr(i) + " is not of type '" +
1024                          (*I)->getName() + "'!");
1025       }
1026
1027       if (i != Params.size() || I != Ty->getParamTypes().end())
1028         ThrowException("Invalid number of parameters detected!");
1029     }
1030
1031     // Create the call node...
1032     $$ = new CallInst((Method*)V, Params);
1033   }
1034   | MemoryInst {
1035     $$ = $1;
1036   }
1037
1038 // UByteList - List of ubyte values for load and store instructions
1039 UByteList : ',' ConstVector {
1040   $$ = $2;
1041 } | /* empty */ {
1042   $$ = new vector<ConstPoolVal*>();
1043 }
1044
1045 MemoryInst : MALLOC Types {
1046     $$ = new MallocInst(checkNewType(PointerType::getPointerType($2)));
1047   }
1048   | MALLOC Types ',' UINT ValueRef {
1049     if (!$2->isArrayType() || ((const ArrayType*)$2)->isSized())
1050       ThrowException("Trying to allocate " + $2->getName() +
1051                      " as unsized array!");
1052     const Type *Ty = checkNewType(PointerType::getPointerType($2));
1053     $$ = new MallocInst(Ty, getVal($4, $5));
1054   }
1055   | ALLOCA Types {
1056     $$ = new AllocaInst(checkNewType(PointerType::getPointerType($2)));
1057   }
1058   | ALLOCA Types ',' UINT ValueRef {
1059     if (!$2->isArrayType() || ((const ArrayType*)$2)->isSized())
1060       ThrowException("Trying to allocate " + $2->getName() +
1061                      " as unsized array!");
1062     const Type *Ty = checkNewType(PointerType::getPointerType($2));
1063     Value *ArrSize = getVal($4, $5);
1064     $$ = new AllocaInst(Ty, ArrSize);
1065   }
1066   | FREE Types ValueRef {
1067     if (!$2->isPointerType())
1068       ThrowException("Trying to free nonpointer type " + $2->getName() + "!");
1069     $$ = new FreeInst(getVal($2, $3));
1070   }
1071
1072   | LOAD Types ValueRef UByteList {
1073     if (!$2->isPointerType())
1074       ThrowException("Can't load from nonpointer type: " + $2->getName());
1075     if (LoadInst::getIndexedType($2, *$4) == 0)
1076       ThrowException("Invalid indices for load instruction!");
1077
1078     $$ = new LoadInst(getVal($2, $3), *$4);
1079     delete $4;   // Free the vector...
1080   }
1081   | STORE Types ValueRef ',' Types ValueRef UByteList {
1082     if (!$5->isPointerType())
1083       ThrowException("Can't store to a nonpointer type: " + $5->getName());
1084     const Type *ElTy = StoreInst::getIndexedType($5, *$7);
1085     if (ElTy == 0)
1086       ThrowException("Can't store into that field list!");
1087     if (ElTy != $2)
1088       ThrowException("Can't store '" + $2->getName() + "' into space of type '"+
1089                      ElTy->getName() + "'!");
1090     $$ = new StoreInst(getVal($2, $3), getVal($5, $6), *$7);
1091     delete $7;
1092   }
1093   | GETELEMENTPTR Types ValueRef UByteList {
1094     if (!$2->isPointerType())
1095       ThrowException("getelementptr insn requires pointer operand!");
1096     if (!GetElementPtrInst::getIndexedType($2, *$4, true))
1097       ThrowException("Can't get element ptr '" + $2->getName() + "'!");
1098     $$ = new GetElementPtrInst(getVal($2, $3), *$4);
1099     delete $4;
1100     checkNewType($$->getType());
1101   }
1102
1103 %%
1104 int yyerror(const char *ErrorMsg) {
1105   ThrowException(string("Parse error: ") + ErrorMsg);
1106   return 0;
1107 }