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