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, const 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   Value                   *ValueVal;
 396
 397   list<MethodArgument*>   *MethodArgList;
 398   list<Value*>            *ValueList;
 399   list<const Type*>       *TypeList;
 400   list<pair<Value*, BasicBlock*> > *PHIList;   // Represent the RHS of PHI node
 401   list<pair<ConstPoolVal*, BasicBlock*> > *JumpTable;
 402   vector<ConstPoolVal*>   *ConstVector;
 403
 404   int64_t                  SInt64Val;
 405   uint64_t                 UInt64Val;
 406   int                      SIntVal;
 407   unsigned                 UIntVal;
 408   double                   FPVal;
 409
 410   char                    *StrVal;   // This memory is allocated by strdup!
 411   ValID                    ValIDVal; // May contain memory allocated by strdup
 412
 413   Instruction::UnaryOps    UnaryOpVal;
 414   Instruction::BinaryOps   BinaryOpVal;
 415   Instruction::TermOps     TermOpVal;
 416   Instruction::MemoryOps   MemOpVal;
 417   Instruction::OtherOps    OtherOpVal;
 418 }
 419
 420 %type <ModuleVal>     Module MethodList
 421 %type <MethodVal>     Method MethodProto MethodHeader BasicBlockList
 422 %type <BasicBlockVal> BasicBlock InstructionList
 423 %type <TermInstVal>   BBTerminatorInst
 424 %type <InstVal>       Inst InstVal MemoryInst
 425 %type <ConstVal>      ConstVal ExtendedConstVal
 426 %type <ConstVector>   ConstVector UByteList
 427 %type <MethodArgList> ArgList ArgListH
 428 %type <MethArgVal>    ArgVal
 429 %type <PHIList>       PHIList
 430 %type <ValueList>     ValueRefList ValueRefListE  // For call param lists
 431 %type <TypeList>      TypeList ArgTypeList
 432 %type <JumpTable>     JumpTable
 433
 434 %type <ValIDVal>      ValueRef ConstValueRef // Reference to a definition or BB
 435 %type <ValueVal>      ResolvedVal            // <type> <valref> pair
 436 // Tokens and types for handling constant integer values
 437 //
 438 // ESINT64VAL - A negative number within long long range
 439 %token <SInt64Val> ESINT64VAL
 440
 441 // EUINT64VAL - A positive number within uns. long long range
 442 %token <UInt64Val> EUINT64VAL
 443 %type  <SInt64Val> EINT64VAL
 444
 445 %token  <SIntVal>   SINTVAL   // Signed 32 bit ints...
 446 %token  <UIntVal>   UINTVAL   // Unsigned 32 bit ints...
 447 %type   <SIntVal>   INTVAL
 448 %token  <FPVal>     FPVAL     // Float or Double constant
 449
 450 // Built in types...
 451 %type  <TypeVal> Types TypesV SIntType UIntType IntType FPType
 452 %token <TypeVal> VOID BOOL SBYTE UBYTE SHORT USHORT INT UINT LONG ULONG
 453 %token <TypeVal> FLOAT DOUBLE STRING TYPE LABEL
 454
 455 %token <StrVal>     VAR_ID LABELSTR STRINGCONSTANT
 456 %type  <StrVal>  OptVAR_ID OptAssign
 457
 458
 459 %token IMPLEMENTATION TRUE FALSE BEGINTOK END DECLARE TO DOTDOTDOT
 460
 461 // Basic Block Terminating Operators
 462 %token <TermOpVal> RET BR SWITCH
 463
 464 // Unary Operators
 465 %type  <UnaryOpVal> UnaryOps  // all the unary operators
 466 %token <UnaryOpVal> NOT
 467
 468 // Binary Operators
 469 %type  <BinaryOpVal> BinaryOps  // all the binary operators
 470 %token <BinaryOpVal> ADD SUB MUL DIV REM
 471 %token <BinaryOpVal> SETLE SETGE SETLT SETGT SETEQ SETNE  // Binary Comarators
 472
 473 // Memory Instructions
 474 %token <MemoryOpVal> MALLOC ALLOCA FREE LOAD STORE GETELEMENTPTR
 475
 476 // Other Operators
 477 %type  <OtherOpVal> ShiftOps
 478 %token <OtherOpVal> PHI CALL CAST SHL SHR
 479
 480 %start Module
 481 %%
 482
 483 // Handle constant integer size restriction and conversion...
 484 //
 485
 486 INTVAL : SINTVAL
 487 INTVAL : UINTVAL {
 488   if ($1 > (uint32_t)INT32_MAX)     // Outside of my range!
 489     ThrowException("Value too large for type!");
 490   $$ = (int32_t)$1;
 491 }
 492
 493
 494 EINT64VAL : ESINT64VAL       // These have same type and can't cause problems...
 495 EINT64VAL : EUINT64VAL {
 496   if ($1 > (uint64_t)INT64_MAX)     // Outside of my range!
 497     ThrowException("Value too large for type!");
 498   $$ = (int64_t)$1;
 499 }
 500
 501 // Types includes all predefined types... except void, because you can't do
 502 // anything with it except for certain specific things...
 503 //
 504 // User defined types are added later...
 505 //
 506 Types     : BOOL | SBYTE | UBYTE | SHORT | USHORT | INT | UINT
 507 Types     : LONG | ULONG | FLOAT | DOUBLE | STRING | TYPE | LABEL
 508
 509 // TypesV includes all of 'Types', but it also includes the void type.
 510 TypesV    : Types | VOID
 511
 512 // Operations that are notably excluded from this list include:
 513 // RET, BR, & SWITCH because they end basic blocks and are treated specially.
 514 //
 515 UnaryOps  : NOT
 516 BinaryOps : ADD | SUB | MUL | DIV | REM
 517 BinaryOps : SETLE | SETGE | SETLT | SETGT | SETEQ | SETNE
 518 ShiftOps  : SHL | SHR
 519
 520 // These are some types that allow classification if we only want a particular
 521 // thing... for example, only a signed, unsigned, or integral type.
 522 SIntType :  LONG |  INT |  SHORT | SBYTE
 523 UIntType : ULONG | UINT | USHORT | UBYTE
 524 IntType : SIntType | UIntType
 525 FPType  : FLOAT | DOUBLE
 526
 527 // OptAssign - Value producing statements have an optional assignment component
 528 OptAssign : VAR_ID '=' {
 529     $$ = $1;
 530   }
 531   | /*empty*/ {
 532     $$ = 0;
 533   }
 534
 535 // ConstVal - The various declarations that go into the constant pool.  This
 536 // includes all forward declarations of types, constants, and functions.
 537 //
 538 // This is broken into two sections: ExtendedConstVal and ConstVal
 539 //
 540 ExtendedConstVal: '[' Types ']' '[' ConstVector ']' { // Nonempty unsized array
 541     // Verify all elements are correct type!
 542     const ArrayType *AT = ArrayType::getArrayType($2);
 543     for (unsigned i = 0; i < $5->size(); i++) {
 544       if ($2 != (*$5)[i]->getType())
 545         ThrowException("Element #" + utostr(i) + " is not of type '" +
 546                        $2->getName() + "' as required!\nIt is of type '" +
 547                        (*$5)[i]->getType()->getName() + "'.");
 548     }
 549
 550     $$ = new ConstPoolArray(AT, *$5);
 551     delete $5;
 552   }
 553   | '[' Types ']' '[' ']' {                  // Empty unsized array constant
 554     vector<ConstPoolVal*> Empty;
 555     $$ = new ConstPoolArray(ArrayType::getArrayType($2), Empty);
 556   }
 557   | '[' EUINT64VAL 'x' Types ']' '[' ConstVector ']' {
 558     // Verify all elements are correct type!
 559     const ArrayType *AT = ArrayType::getArrayType($4, (int)$2);
 560     if ($2 != $7->size())
 561       ThrowException("Type mismatch: constant sized array initialized with " +
 562                      utostr($7->size()) +  " arguments, but has size of " +
 563                      itostr((int)$2) + "!");
 564
 565     for (unsigned i = 0; i < $7->size(); i++) {
 566       if ($4 != (*$7)[i]->getType())
 567         ThrowException("Element #" + utostr(i) + " is not of type '" +
 568                        $4->getName() + "' as required!\nIt is of type '" +
 569                        (*$7)[i]->getType()->getName() + "'.");
 570     }
 571
 572     $$ = new ConstPoolArray(AT, *$7);
 573     delete $7;
 574   }
 575   | '[' EUINT64VAL 'x' Types ']' '[' ']' {
 576     if ($2 != 0)
 577       ThrowException("Type mismatch: constant sized array initialized with 0"
 578                      " arguments, but has size of " + itostr((int)$2) + "!");
 579     vector<ConstPoolVal*> Empty;
 580     $$ = new ConstPoolArray(ArrayType::getArrayType($4, 0), Empty);
 581   }
 582   | '{' TypeList '}' '{' ConstVector '}' {
 583     StructType::ElementTypes Types($2->begin(), $2->end());
 584     delete $2;
 585
 586     const StructType *St = StructType::getStructType(Types);
 587     $$ = new ConstPoolStruct(St, *$5);
 588     delete $5;
 589   }
 590   | '{' '}' '{' '}' {
 591     const StructType *St =
 592       StructType::getStructType(StructType::ElementTypes());
 593     vector<ConstPoolVal*> Empty;
 594     $$ = new ConstPoolStruct(St, Empty);
 595   }
 596 /*
 597   | Types '*' ConstVal {
 598     assert(0);
 599     $$ = 0;
 600   }
 601 */
 602
 603 ConstVal : ExtendedConstVal
 604   | TYPE Types {                    // Type constants
 605     $$ = new ConstPoolType($2);
 606   }
 607   | SIntType EINT64VAL {     // integral constants
 608     if (!ConstPoolSInt::isValueValidForType($1, $2))
 609       ThrowException("Constant value doesn't fit in type!");
 610     $$ = new ConstPoolSInt($1, $2);
 611   }
 612   | UIntType EUINT64VAL {           // integral constants
 613     if (!ConstPoolUInt::isValueValidForType($1, $2))
 614       ThrowException("Constant value doesn't fit in type!");
 615     $$ = new ConstPoolUInt($1, $2);
 616   }
 617   | BOOL TRUE {                     // Boolean constants
 618     $$ = new ConstPoolBool(true);
 619   }
 620   | BOOL FALSE {                    // Boolean constants
 621     $$ = new ConstPoolBool(false);
 622   }
 623   | FPType FPVAL {                   // Float & Double constants
 624     $$ = new ConstPoolFP($1, $2);
 625   }
 626   | STRING STRINGCONSTANT {         // String constants
 627     cerr << "FIXME: TODO: String constants [sbyte] not implemented yet!\n";
 628     abort();
 629     //$$ = new ConstPoolString($2);
 630     free($2);
 631   }
 632
 633 // ConstVector - A list of comma seperated constants.
 634 ConstVector : ConstVector ',' ConstVal {
 635     ($$ = $1)->push_back(addConstValToConstantPool($3));
 636   }
 637   | ConstVal {
 638     $$ = new vector<ConstPoolVal*>();
 639     $$->push_back(addConstValToConstantPool($1));
 640   }
 641
 642
 643 //ExternMethodDecl : EXTERNAL TypesV '(' TypeList ')' {
 644 //  }
 645 //ExternVarDecl :
 646
 647 // ConstPool - Constants with optional names assigned to them.
 648 ConstPool : ConstPool OptAssign ConstVal {
 649     if ($2) {
 650       $3->setName($2);
 651       free($2);
 652     }
 653
 654     addConstValToConstantPool($3);
 655   }
 656 /*
 657   | ConstPool OptAssign GlobalDecl {     // Global declarations appear in CP
 658     if ($2) {
 659       $3->setName($2);
 660       free($2);
 661     }
 662     //CurModule.CurrentModule->
 663   }
 664 */
 665   | /* empty: end of list */ {
 666   }
 667
 668
 669 //===----------------------------------------------------------------------===//
 670 //                             Rules to match Modules
 671 //===----------------------------------------------------------------------===//
 672
 673 // Module rule: Capture the result of parsing the whole file into a result
 674 // variable...
 675 //
 676 Module : MethodList {
 677   $$ = ParserResult = $1;
 678   CurModule.ModuleDone();
 679 }
 680
 681 // MethodList - A list of methods, preceeded by a constant pool.
 682 //
 683 MethodList : MethodList Method {
 684     $$ = $1;
 685     if (!$2->getParent())
 686       $1->getMethodList().push_back($2);
 687     CurMeth.MethodDone();
 688   }
 689   | MethodList MethodProto {
 690     $$ = $1;
 691     if (!$2->getParent())
 692       $1->getMethodList().push_back($2);
 693     CurMeth.MethodDone();
 694   }
 695   | ConstPool IMPLEMENTATION {
 696     $$ = CurModule.CurrentModule;
 697   }
 698
 699
 700 //===----------------------------------------------------------------------===//
 701 //                       Rules to match Method Headers
 702 //===----------------------------------------------------------------------===//
 703
 704 OptVAR_ID : VAR_ID | /*empty*/ { $$ = 0; }
 705
 706 ArgVal : Types OptVAR_ID {
 707   $$ = new MethodArgument($1);
 708   if ($2) {      // Was the argument named?
 709     $$->setName($2);
 710     free($2);    // The string was strdup'd, so free it now.
 711   }
 712 }
 713
 714 ArgListH : ArgVal ',' ArgListH {
 715     $$ = $3;
 716     $3->push_front($1);
 717   }
 718   | ArgVal {
 719     $$ = new list<MethodArgument*>();
 720     $$->push_front($1);
 721   }
 722   | DOTDOTDOT {
 723     $$ = new list<MethodArgument*>();
 724     $$->push_back(new MethodArgument(Type::VoidTy));
 725   }
 726
 727 ArgList : ArgListH {
 728     $$ = $1;
 729   }
 730   | /* empty */ {
 731     $$ = 0;
 732   }
 733
 734 MethodHeaderH : TypesV STRINGCONSTANT '(' ArgList ')' {
 735   MethodType::ParamTypes ParamTypeList;
 736   if ($4)
 737     for (list<MethodArgument*>::iterator I = $4->begin(); I != $4->end(); ++I)
 738       ParamTypeList.push_back((*I)->getType());
 739
 740   const MethodType *MT = MethodType::getMethodType($1, ParamTypeList);
 741
 742   Method *M = 0;
 743   if (SymbolTable *ST = CurModule.CurrentModule->getSymbolTable()) {
 744     if (Value *V = ST->lookup(MT, $2)) {  // Method already in symtab?
 745       M = V->castMethodAsserting();
 746
 747       // Yes it is.  If this is the case, either we need to be a forward decl,
 748       // or it needs to be.
 749       if (!CurMeth.isDeclare && !M->isExternal())
 750         ThrowException("Redefinition of method '" + string($2) + "'!");
 751     }
 752   }
 753
 754   if (M == 0) {  // Not already defined?
 755     M = new Method(MT, $2);
 756     InsertValue(M, CurModule.Values);
 757   }
 758
 759   free($2);  // Free strdup'd memory!
 760
 761   CurMeth.MethodStart(M);
 762
 763   // Add all of the arguments we parsed to the method...
 764   if ($4 && !CurMeth.isDeclare) {        // Is null if empty...
 765     Method::ArgumentListType &ArgList = M->getArgumentList();
 766
 767     for (list<MethodArgument*>::iterator I = $4->begin(); I != $4->end(); ++I) {
 768       InsertValue(*I);
 769       ArgList.push_back(*I);
 770     }
 771     delete $4;                     // We're now done with the argument list
 772   }
 773 }
 774
 775 MethodHeader : MethodHeaderH ConstPool BEGINTOK {
 776   $$ = CurMeth.CurrentMethod;
 777 }
 778
 779 Method : BasicBlockList END {
 780   $$ = $1;
 781 }
 782
 783 MethodProto : DECLARE { CurMeth.isDeclare = true; } MethodHeaderH {
 784   $$ = CurMeth.CurrentMethod;
 785 }
 786
 787 //===----------------------------------------------------------------------===//
 788 //                        Rules to match Basic Blocks
 789 //===----------------------------------------------------------------------===//
 790
 791 ConstValueRef : ESINT64VAL {    // A reference to a direct constant
 792     $$ = ValID::create($1);
 793   }
 794   | EUINT64VAL {
 795     $$ = ValID::create($1);
 796   }
 797   | FPVAL {                     // Perhaps it's an FP constant?
 798     $$ = ValID::create($1);
 799   }
 800   | TRUE {
 801     $$ = ValID::create((int64_t)1);
 802   }
 803   | FALSE {
 804     $$ = ValID::create((int64_t)0);
 805   }
 806   | STRINGCONSTANT {        // Quoted strings work too... especially for methods
 807     $$ = ValID::create_conststr($1);
 808   }
 809
 810 // ValueRef - A reference to a definition...
 811 ValueRef : INTVAL {           // Is it an integer reference...?
 812     $$ = ValID::create($1);
 813   }
 814   | VAR_ID {                 // Is it a named reference...?
 815     $$ = ValID::create($1);
 816   }
 817   | ConstValueRef {
 818     $$ = $1;
 819   }
 820
 821 // ResolvedVal - a <type> <value> pair.  This is used only in cases where the
 822 // type immediately preceeds the value reference, and allows complex constant
 823 // pool references (for things like: 'ret [2 x int] [ int 12, int 42]')
 824 ResolvedVal : ExtendedConstVal {
 825     $$ = addConstValToConstantPool($1);
 826   }
 827   | Types ValueRef {
 828     $$ = getVal($1, $2);
 829   }
 830
 831
 832 // The user may refer to a user defined type by its typeplane... check for this
 833 // now...
 834 //
 835 Types : ValueRef {
 836     Value *D = getVal(Type::TypeTy, $1, true);
 837     if (D == 0) ThrowException("Invalid user defined type: " + $1.getName());
 838
 839     // User defined type not in const pool!
 840     ConstPoolType *CPT = (ConstPoolType*)D->castConstantAsserting();
 841     $$ = CPT->getValue();
 842   }
 843   | TypesV '(' ArgTypeList ')' {               // Method derived type?
 844     MethodType::ParamTypes Params($3->begin(), $3->end());
 845     delete $3;
 846     $$ = checkNewType(MethodType::getMethodType($1, Params));
 847   }
 848   | TypesV '(' ')' {               // Method derived type?
 849     MethodType::ParamTypes Params;     // Empty list
 850     $$ = checkNewType(MethodType::getMethodType($1, Params));
 851   }
 852   | '[' Types ']' {
 853     $$ = checkNewType(ArrayType::getArrayType($2));
 854   }
 855   | '[' EUINT64VAL 'x' Types ']' {
 856     $$ = checkNewType(ArrayType::getArrayType($4, (int)$2));
 857   }
 858   | '{' TypeList '}' {
 859     StructType::ElementTypes Elements($2->begin(), $2->end());
 860     delete $2;
 861     $$ = checkNewType(StructType::getStructType(Elements));
 862   }
 863   | '{' '}' {
 864     $$ = checkNewType(StructType::getStructType(StructType::ElementTypes()));
 865   }
 866   | Types '*' {
 867     $$ = checkNewType(PointerType::getPointerType($1));
 868   }
 869
 870 TypeList : Types {
 871     $$ = new list<const Type*>();
 872     $$->push_back($1);
 873   }
 874   | TypeList ',' Types {
 875     ($$=$1)->push_back($3);
 876   }
 877
 878 ArgTypeList : TypeList
 879   | TypeList ',' DOTDOTDOT {
 880     ($$=$1)->push_back(Type::VoidTy);
 881   }
 882
 883
 884 BasicBlockList : BasicBlockList BasicBlock {
 885     $1->getBasicBlocks().push_back($2);
 886     $$ = $1;
 887   }
 888   | MethodHeader BasicBlock { // Do not allow methods with 0 basic blocks
 889     $$ = $1;                  // in them...
 890     $1->getBasicBlocks().push_back($2);
 891   }
 892
 893
 894 // Basic blocks are terminated by branching instructions:
 895 // br, br/cc, switch, ret
 896 //
 897 BasicBlock : InstructionList BBTerminatorInst  {
 898     $1->getInstList().push_back($2);
 899     InsertValue($1);
 900     $$ = $1;
 901   }
 902   | LABELSTR InstructionList BBTerminatorInst  {
 903     $2->getInstList().push_back($3);
 904     $2->setName($1);
 905     free($1);         // Free the strdup'd memory...
 906
 907     InsertValue($2);
 908     $$ = $2;
 909   }
 910
 911 InstructionList : InstructionList Inst {
 912     $1->getInstList().push_back($2);
 913     $$ = $1;
 914   }
 915   | /* empty */ {
 916     $$ = new BasicBlock();
 917   }
 918
 919 BBTerminatorInst : RET ResolvedVal {              // Return with a result...
 920     $$ = new ReturnInst($2);
 921   }
 922   | RET VOID {                                       // Return with no result...
 923     $$ = new ReturnInst();
 924   }
 925   | BR LABEL ValueRef {                         // Unconditional Branch...
 926     $$ = new BranchInst(getVal(Type::LabelTy, $3)->castBasicBlockAsserting());
 927   }                                                  // Conditional Branch...
 928   | BR BOOL ValueRef ',' LABEL ValueRef ',' LABEL ValueRef {
 929     $$ = new BranchInst(getVal(Type::LabelTy, $6)->castBasicBlockAsserting(),
 930                         getVal(Type::LabelTy, $9)->castBasicBlockAsserting(),
 931                         getVal(Type::BoolTy, $3));
 932   }
 933   | SWITCH IntType ValueRef ',' LABEL ValueRef '[' JumpTable ']' {
 934     SwitchInst *S = new SwitchInst(getVal($2, $3),
 935                           getVal(Type::LabelTy, $6)->castBasicBlockAsserting());
 936     $$ = S;
 937
 938     list<pair<ConstPoolVal*, BasicBlock*> >::iterator I = $8->begin(),
 939                                                       end = $8->end();
 940     for (; I != end; ++I)
 941       S->dest_push_back(I->first, I->second);
 942   }
 943
 944 JumpTable : JumpTable IntType ConstValueRef ',' LABEL ValueRef {
 945     $$ = $1;
 946     ConstPoolVal *V = getVal($2, $3, true)->castConstantAsserting();
 947     if (V == 0)
 948       ThrowException("May only switch on a constant pool value!");
 949
 950     $$->push_back(make_pair(V, getVal($5, $6)->castBasicBlockAsserting()));
 951   }
 952   | IntType ConstValueRef ',' LABEL ValueRef {
 953     $$ = new list<pair<ConstPoolVal*, BasicBlock*> >();
 954     ConstPoolVal *V = getVal($1, $2, true)->castConstantAsserting();
 955
 956     if (V == 0)
 957       ThrowException("May only switch on a constant pool value!");
 958
 959     $$->push_back(make_pair(V, getVal($4, $5)->castBasicBlockAsserting()));
 960   }
 961
 962 Inst : OptAssign InstVal {
 963   if ($1)              // Is this definition named??
 964     $2->setName($1);   // if so, assign the name...
 965
 966   InsertValue($2);
 967   $$ = $2;
 968 }
 969
 970 PHIList : Types '[' ValueRef ',' ValueRef ']' {    // Used for PHI nodes
 971     $$ = new list<pair<Value*, BasicBlock*> >();
 972     $$->push_back(make_pair(getVal($1, $3),
 973                          getVal(Type::LabelTy, $5)->castBasicBlockAsserting()));
 974   }
 975   | PHIList ',' '[' ValueRef ',' ValueRef ']' {
 976     $$ = $1;
 977     $1->push_back(make_pair(getVal($1->front().first->getType(), $4),
 978                          getVal(Type::LabelTy, $6)->castBasicBlockAsserting()));
 979   }
 980
 981
 982 ValueRefList : ResolvedVal {    // Used for call statements...
 983     $$ = new list<Value*>();
 984     $$->push_back($1);
 985   }
 986   | ValueRefList ',' ResolvedVal {
 987     $$ = $1;
 988     $1->push_back($3);
 989   }
 990
 991 // ValueRefListE - Just like ValueRefList, except that it may also be empty!
 992 ValueRefListE : ValueRefList | /*empty*/ { $$ = 0; }
 993
 994 InstVal : BinaryOps Types ValueRef ',' ValueRef {
 995     $$ = BinaryOperator::create($1, getVal($2, $3), getVal($2, $5));
 996     if ($$ == 0)
 997       ThrowException("binary operator returned null!");
 998   }
 999   | UnaryOps ResolvedVal {
1000     $$ = UnaryOperator::create($1, $2);
1001     if ($$ == 0)
1002       ThrowException("unary operator returned null!");
1003   }
1004   | ShiftOps ResolvedVal ',' ResolvedVal {
1005     if ($4->getType() != Type::UByteTy)
1006       ThrowException("Shift amount must be ubyte!");
1007     $$ = new ShiftInst($1, $2, $4);
1008   }
1009   | CAST ResolvedVal TO Types {
1010     $$ = new CastInst($2, $4);
1011   }
1012   | PHI PHIList {
1013     const Type *Ty = $2->front().first->getType();
1014     $$ = new PHINode(Ty);
1015     while ($2->begin() != $2->end()) {
1016       if ($2->front().first->getType() != Ty)
1017         ThrowException("All elements of a PHI node must be of the same type!");
1018       ((PHINode*)$$)->addIncoming($2->front().first, $2->front().second);
1019       $2->pop_front();
1020     }
1021     delete $2;  // Free the list...
1022   }
1023   | CALL Types ValueRef '(' ValueRefListE ')' {
1024     const MethodType *Ty;
1025
1026     if (!(Ty = $2->isMethodType())) {
1027       // Pull out the types of all of the arguments...
1028       vector<const Type*> ParamTypes;
1029       for (list<Value*>::iterator I = $5->begin(), E = $5->end(); I != E; ++I)
1030         ParamTypes.push_back((*I)->getType());
1031       Ty = MethodType::get($2, ParamTypes);
1032     }
1033
1034     Value *V = getVal(Ty, $3);   // Get the method we're calling...
1035
1036     // Create the call node...
1037     if (!$5) {                                   // Has no arguments?
1038       $$ = new CallInst(V->castMethodAsserting(), vector<Value*>());
1039     } else {                                     // Has arguments?
1040       // Loop through MethodType's arguments and ensure they are specified
1041       // correctly!
1042       //
1043       MethodType::ParamTypes::const_iterator I = Ty->getParamTypes().begin();
1044       MethodType::ParamTypes::const_iterator E = Ty->getParamTypes().end();
1045       list<Value*>::iterator ArgI = $5->begin(), ArgE = $5->end();
1046
1047       for (; ArgI != ArgE && I != E; ++ArgI, ++I)
1048         if ((*ArgI)->getType() != *I)
1049           ThrowException("Parameter " +(*ArgI)->getName()+ " is not of type '" +
1050                          (*I)->getName() + "'!");
1051
1052       if (I != E || (ArgI != ArgE && !Ty->isVarArg()))
1053         ThrowException("Invalid number of parameters detected!");
1054
1055       $$ = new CallInst(V->castMethodAsserting(),
1056                         vector<Value*>($5->begin(), $5->end()));
1057     }
1058     delete $5;
1059   }
1060   | MemoryInst {
1061     $$ = $1;
1062   }
1063
1064 // UByteList - List of ubyte values for load and store instructions
1065 UByteList : ',' ConstVector {
1066   $$ = $2;
1067 } | /* empty */ {
1068   $$ = new vector<ConstPoolVal*>();
1069 }
1070
1071 MemoryInst : MALLOC Types {
1072     $$ = new MallocInst(checkNewType(PointerType::getPointerType($2)));
1073   }
1074   | MALLOC Types ',' UINT ValueRef {
1075     if (!$2->isArrayType() || ((const ArrayType*)$2)->isSized())
1076       ThrowException("Trying to allocate " + $2->getName() +
1077                      " as unsized array!");
1078     const Type *Ty = checkNewType(PointerType::getPointerType($2));
1079     $$ = new MallocInst(Ty, getVal($4, $5));
1080   }
1081   | ALLOCA Types {
1082     $$ = new AllocaInst(checkNewType(PointerType::getPointerType($2)));
1083   }
1084   | ALLOCA Types ',' UINT ValueRef {
1085     if (!$2->isArrayType() || ((const ArrayType*)$2)->isSized())
1086       ThrowException("Trying to allocate " + $2->getName() +
1087                      " as unsized array!");
1088     const Type *Ty = checkNewType(PointerType::getPointerType($2));
1089     Value *ArrSize = getVal($4, $5);
1090     $$ = new AllocaInst(Ty, ArrSize);
1091   }
1092   | FREE ResolvedVal {
1093     if (!$2->getType()->isPointerType())
1094       ThrowException("Trying to free nonpointer type " +
1095                      $2->getType()->getName() + "!");
1096     $$ = new FreeInst($2);
1097   }
1098
1099   | LOAD Types ValueRef UByteList {
1100     if (!$2->isPointerType())
1101       ThrowException("Can't load from nonpointer type: " + $2->getName());
1102     if (LoadInst::getIndexedType($2, *$4) == 0)
1103       ThrowException("Invalid indices for load instruction!");
1104
1105     $$ = new LoadInst(getVal($2, $3), *$4);
1106     delete $4;   // Free the vector...
1107   }
1108   | STORE ResolvedVal ',' Types ValueRef UByteList {
1109     if (!$4->isPointerType())
1110       ThrowException("Can't store to a nonpointer type: " + $4->getName());
1111     const Type *ElTy = StoreInst::getIndexedType($4, *$6);
1112     if (ElTy == 0)
1113       ThrowException("Can't store into that field list!");
1114     if (ElTy != $2->getType())
1115       ThrowException("Can't store '" + $2->getType()->getName() +
1116                      "' into space of type '" + ElTy->getName() + "'!");
1117     $$ = new StoreInst($2, getVal($4, $5), *$6);
1118     delete $6;
1119   }
1120   | GETELEMENTPTR Types ValueRef UByteList {
1121     if (!$2->isPointerType())
1122       ThrowException("getelementptr insn requires pointer operand!");
1123     if (!GetElementPtrInst::getIndexedType($2, *$4, true))
1124       ThrowException("Can't get element ptr '" + $2->getName() + "'!");
1125     $$ = new GetElementPtrInst(getVal($2, $3), *$4);
1126     delete $4;
1127     checkNewType($$->getType());
1128   }
1129
1130 %%
1131 int yyerror(const char *ErrorMsg) {
1132   ThrowException(string("Parse error: ") + ErrorMsg);
1133   return 0;
1134 }