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 #include "ParserInternals.h"
   9 #include "llvm/SymbolTable.h"
  10 #include "llvm/Module.h"
  11 #include "llvm/iTerminators.h"
  12 #include "llvm/iMemory.h"
  13 #include "llvm/iPHINode.h"
  14 #include "Support/STLExtras.h"
  15 #include "Support/DepthFirstIterator.h"
  16 #include <list>
  17 #include <utility>
  18 #include <algorithm>
  19 using std::list;
  20 using std::vector;
  21 using std::pair;
  22 using std::map;
  23 using std::pair;
  24 using std::make_pair;
  25 using std::cerr;
  26 using std::string;
  27
  28 int yyerror(const char *ErrorMsg); // Forward declarations to prevent "implicit
  29 int yylex();                       // declaration" of xxx warnings.
  30 int yyparse();
  31
  32 static Module *ParserResult;
  33 string CurFilename;
  34
  35 // DEBUG_UPREFS - Define this symbol if you want to enable debugging output
  36 // relating to upreferences in the input stream.
  37 //
  38 //#define DEBUG_UPREFS 1
  39 #ifdef DEBUG_UPREFS
  40 #define UR_OUT(X) cerr << X
  41 #else
  42 #define UR_OUT(X)
  43 #endif
  44
  45 #define YYERROR_VERBOSE 1
  46
  47 // This contains info used when building the body of a function.  It is
  48 // destroyed when the function is completed.
  49 //
  50 typedef vector<Value *> ValueList;           // Numbered defs
  51 static void ResolveDefinitions(vector<ValueList> &LateResolvers,
  52                                vector<ValueList> *FutureLateResolvers = 0);
  53
  54 static struct PerModuleInfo {
  55   Module *CurrentModule;
  56   vector<ValueList>    Values;     // Module level numbered definitions
  57   vector<ValueList>    LateResolveValues;
  58   vector<PATypeHolder> Types;
  59   map<ValID, PATypeHolder> LateResolveTypes;
  60
  61   // GlobalRefs - This maintains a mapping between <Type, ValID>'s and forward
  62   // references to global values.  Global values may be referenced before they
  63   // are defined, and if so, the temporary object that they represent is held
  64   // here.  This is used for forward references of ConstantPointerRefs.
  65   //
  66   typedef map<pair<const PointerType *, ValID>, GlobalVariable*> GlobalRefsType;
  67   GlobalRefsType GlobalRefs;
  68
  69   void ModuleDone() {
  70     // If we could not resolve some functions at function compilation time
  71     // (calls to functions before they are defined), resolve them now...  Types
  72     // are resolved when the constant pool has been completely parsed.
  73     //
  74     ResolveDefinitions(LateResolveValues);
  75
  76     // Check to make sure that all global value forward references have been
  77     // resolved!
  78     //
  79     if (!GlobalRefs.empty()) {
  80       string UndefinedReferences = "Unresolved global references exist:\n";
  81
  82       for (GlobalRefsType::iterator I = GlobalRefs.begin(), E =GlobalRefs.end();
  83            I != E; ++I) {
  84         UndefinedReferences += "  " + I->first.first->getDescription() + " " +
  85                                I->first.second.getName() + "\n";
  86       }
  87       ThrowException(UndefinedReferences);
  88     }
  89
  90     Values.clear();         // Clear out function local definitions
  91     Types.clear();
  92     CurrentModule = 0;
  93   }
  94
  95
  96   // DeclareNewGlobalValue - Called every time a new GV has been defined.  This
  97   // is used to remove things from the forward declaration map, resolving them
  98   // to the correct thing as needed.
  99   //
 100   void DeclareNewGlobalValue(GlobalValue *GV, ValID D) {
 101     // Check to see if there is a forward reference to this global variable...
 102     // if there is, eliminate it and patch the reference to use the new def'n.
 103     GlobalRefsType::iterator I = GlobalRefs.find(make_pair(GV->getType(), D));
 104
 105     if (I != GlobalRefs.end()) {
 106       GlobalVariable *OldGV = I->second;   // Get the placeholder...
 107       I->first.second.destroy();  // Free string memory if neccesary
 108
 109       // Loop over all of the uses of the GlobalValue.  The only thing they are
 110       // allowed to be is ConstantPointerRef's.
 111       assert(OldGV->use_size() == 1 && "Only one reference should exist!");
 112       while (!OldGV->use_empty()) {
 113         User *U = OldGV->use_back();  // Must be a ConstantPointerRef...
 114         ConstantPointerRef *CPR = cast<ConstantPointerRef>(U);
 115         assert(CPR->getValue() == OldGV && "Something isn't happy");
 116
 117         // Change the const pool reference to point to the real global variable
 118         // now.  This should drop a use from the OldGV.
 119         CPR->mutateReferences(OldGV, GV);
 120       }
 121
 122       // Remove OldGV from the module...
 123       CurrentModule->getGlobalList().remove(OldGV);
 124       delete OldGV;                        // Delete the old placeholder
 125
 126       // Remove the map entry for the global now that it has been created...
 127       GlobalRefs.erase(I);
 128     }
 129   }
 130
 131 } CurModule;
 132
 133 static struct PerFunctionInfo {
 134   Function *CurrentFunction;     // Pointer to current function being created
 135
 136   vector<ValueList> Values;      // Keep track of numbered definitions
 137   vector<ValueList> LateResolveValues;
 138   vector<PATypeHolder> Types;
 139   map<ValID, PATypeHolder> LateResolveTypes;
 140   bool isDeclare;                // Is this function a forward declararation?
 141
 142   inline PerFunctionInfo() {
 143     CurrentFunction = 0;
 144     isDeclare = false;
 145   }
 146
 147   inline ~PerFunctionInfo() {}
 148
 149   inline void FunctionStart(Function *M) {
 150     CurrentFunction = M;
 151   }
 152
 153   void FunctionDone() {
 154     // If we could not resolve some blocks at parsing time (forward branches)
 155     // resolve the branches now...
 156     ResolveDefinitions(LateResolveValues, &CurModule.LateResolveValues);
 157
 158     Values.clear();         // Clear out function local definitions
 159     Types.clear();
 160     CurrentFunction = 0;
 161     isDeclare = false;
 162   }
 163 } CurMeth;  // Info for the current function...
 164
 165 static bool inFunctionScope() { return CurMeth.CurrentFunction != 0; }
 166
 167
 168 //===----------------------------------------------------------------------===//
 169 //               Code to handle definitions of all the types
 170 //===----------------------------------------------------------------------===//
 171
 172 static int InsertValue(Value *D, vector<ValueList> &ValueTab = CurMeth.Values) {
 173   if (D->hasName()) return -1;           // Is this a numbered definition?
 174
 175   // Yes, insert the value into the value table...
 176   unsigned type = D->getType()->getUniqueID();
 177   if (ValueTab.size() <= type)
 178     ValueTab.resize(type+1, ValueList());
 179   //printf("Values[%d][%d] = %d\n", type, ValueTab[type].size(), D);
 180   ValueTab[type].push_back(D);
 181   return ValueTab[type].size()-1;
 182 }
 183
 184 // TODO: FIXME when Type are not const
 185 static void InsertType(const Type *Ty, vector<PATypeHolder> &Types) {
 186   Types.push_back(Ty);
 187 }
 188
 189 static const Type *getTypeVal(const ValID &D, bool DoNotImprovise = false) {
 190   switch (D.Type) {
 191   case ValID::NumberVal: {                 // Is it a numbered definition?
 192     unsigned Num = (unsigned)D.Num;
 193
 194     // Module constants occupy the lowest numbered slots...
 195     if (Num < CurModule.Types.size())
 196       return CurModule.Types[Num];
 197
 198     Num -= CurModule.Types.size();
 199
 200     // Check that the number is within bounds...
 201     if (Num <= CurMeth.Types.size())
 202       return CurMeth.Types[Num];
 203     break;
 204   }
 205   case ValID::NameVal: {                // Is it a named definition?
 206     string Name(D.Name);
 207     SymbolTable *SymTab = 0;
 208     if (inFunctionScope()) SymTab = CurMeth.CurrentFunction->getSymbolTable();
 209     Value *N = SymTab ? SymTab->lookup(Type::TypeTy, Name) : 0;
 210
 211     if (N == 0) {
 212       // Symbol table doesn't automatically chain yet... because the function
 213       // hasn't been added to the module...
 214       //
 215       SymTab = CurModule.CurrentModule->getSymbolTable();
 216       if (SymTab)
 217         N = SymTab->lookup(Type::TypeTy, Name);
 218       if (N == 0) break;
 219     }
 220
 221     D.destroy();  // Free old strdup'd memory...
 222     return cast<const Type>(N);
 223   }
 224   default:
 225     ThrowException("Internal parser error: Invalid symbol type reference!");
 226   }
 227
 228   // If we reached here, we referenced either a symbol that we don't know about
 229   // or an id number that hasn't been read yet.  We may be referencing something
 230   // forward, so just create an entry to be resolved later and get to it...
 231   //
 232   if (DoNotImprovise) return 0;  // Do we just want a null to be returned?
 233
 234   map<ValID, PATypeHolder> &LateResolver = inFunctionScope() ?
 235     CurMeth.LateResolveTypes : CurModule.LateResolveTypes;
 236
 237   map<ValID, PATypeHolder>::iterator I = LateResolver.find(D);
 238   if (I != LateResolver.end()) {
 239     return I->second;
 240   }
 241
 242   Type *Typ = OpaqueType::get();
 243   LateResolver.insert(make_pair(D, Typ));
 244   return Typ;
 245 }
 246
 247 static Value *lookupInSymbolTable(const Type *Ty, const string &Name) {
 248   SymbolTable *SymTab =
 249     inFunctionScope() ? CurMeth.CurrentFunction->getSymbolTable() :
 250                         CurModule.CurrentModule->getSymbolTable();
 251   return SymTab ? SymTab->lookup(Ty, Name) : 0;
 252 }
 253
 254 // getValNonImprovising - Look up the value specified by the provided type and
 255 // the provided ValID.  If the value exists and has already been defined, return
 256 // it.  Otherwise return null.
 257 //
 258 static Value *getValNonImprovising(const Type *Ty, const ValID &D) {
 259   if (isa<FunctionType>(Ty))
 260     ThrowException("Functions are not values and "
 261                    "must be referenced as pointers");
 262
 263   switch (D.Type) {
 264   case ValID::NumberVal: {                 // Is it a numbered definition?
 265     unsigned type = Ty->getUniqueID();
 266     unsigned Num = (unsigned)D.Num;
 267
 268     // Module constants occupy the lowest numbered slots...
 269     if (type < CurModule.Values.size()) {
 270       if (Num < CurModule.Values[type].size())
 271         return CurModule.Values[type][Num];
 272
 273       Num -= CurModule.Values[type].size();
 274     }
 275
 276     // Make sure that our type is within bounds
 277     if (CurMeth.Values.size() <= type) return 0;
 278
 279     // Check that the number is within bounds...
 280     if (CurMeth.Values[type].size() <= Num) return 0;
 281
 282     return CurMeth.Values[type][Num];
 283   }
 284
 285   case ValID::NameVal: {                // Is it a named definition?
 286     Value *N = lookupInSymbolTable(Ty, string(D.Name));
 287     if (N == 0) return 0;
 288
 289     D.destroy();  // Free old strdup'd memory...
 290     return N;
 291   }
 292
 293   // Check to make sure that "Ty" is an integral type, and that our
 294   // value will fit into the specified type...
 295   case ValID::ConstSIntVal:    // Is it a constant pool reference??
 296     if (Ty == Type::BoolTy) {  // Special handling for boolean data
 297       return ConstantBool::get(D.ConstPool64 != 0);
 298     } else {
 299       if (!ConstantSInt::isValueValidForType(Ty, D.ConstPool64))
 300         ThrowException("Signed integral constant '" +
 301                        itostr(D.ConstPool64) + "' is invalid for type '" +
 302                        Ty->getDescription() + "'!");
 303       return ConstantSInt::get(Ty, D.ConstPool64);
 304     }
 305
 306   case ValID::ConstUIntVal:     // Is it an unsigned const pool reference?
 307     if (!ConstantUInt::isValueValidForType(Ty, D.UConstPool64)) {
 308       if (!ConstantSInt::isValueValidForType(Ty, D.ConstPool64)) {
 309         ThrowException("Integral constant '" + utostr(D.UConstPool64) +
 310                        "' is invalid or out of range!");
 311       } else {     // This is really a signed reference.  Transmogrify.
 312         return ConstantSInt::get(Ty, D.ConstPool64);
 313       }
 314     } else {
 315       return ConstantUInt::get(Ty, D.UConstPool64);
 316     }
 317
 318   case ValID::ConstFPVal:        // Is it a floating point const pool reference?
 319     if (!ConstantFP::isValueValidForType(Ty, D.ConstPoolFP))
 320       ThrowException("FP constant invalid for type!!");
 321     return ConstantFP::get(Ty, D.ConstPoolFP);
 322
 323   case ValID::ConstNullVal:      // Is it a null value?
 324     if (!isa<PointerType>(Ty))
 325       ThrowException("Cannot create a a non pointer null!");
 326     return ConstantPointerNull::get(cast<PointerType>(Ty));
 327
 328   default:
 329     assert(0 && "Unhandled case!");
 330     return 0;
 331   }   // End of switch
 332
 333   assert(0 && "Unhandled case!");
 334   return 0;
 335 }
 336
 337
 338 // getVal - This function is identical to getValNonImprovising, except that if a
 339 // value is not already defined, it "improvises" by creating a placeholder var
 340 // that looks and acts just like the requested variable.  When the value is
 341 // defined later, all uses of the placeholder variable are replaced with the
 342 // real thing.
 343 //
 344 static Value *getVal(const Type *Ty, const ValID &D) {
 345   assert(Ty != Type::TypeTy && "Should use getTypeVal for types!");
 346
 347   // See if the value has already been defined...
 348   Value *V = getValNonImprovising(Ty, D);
 349   if (V) return V;
 350
 351   // If we reached here, we referenced either a symbol that we don't know about
 352   // or an id number that hasn't been read yet.  We may be referencing something
 353   // forward, so just create an entry to be resolved later and get to it...
 354   //
 355   Value *d = 0;
 356   switch (Ty->getPrimitiveID()) {
 357   case Type::LabelTyID:  d = new   BBPlaceHolder(Ty, D); break;
 358   default:               d = new ValuePlaceHolder(Ty, D); break;
 359   }
 360
 361   assert(d != 0 && "How did we not make something?");
 362   if (inFunctionScope())
 363     InsertValue(d, CurMeth.LateResolveValues);
 364   else
 365     InsertValue(d, CurModule.LateResolveValues);
 366   return d;
 367 }
 368
 369
 370 //===----------------------------------------------------------------------===//
 371 //              Code to handle forward references in instructions
 372 //===----------------------------------------------------------------------===//
 373 //
 374 // This code handles the late binding needed with statements that reference
 375 // values not defined yet... for example, a forward branch, or the PHI node for
 376 // a loop body.
 377 //
 378 // This keeps a table (CurMeth.LateResolveValues) of all such forward references
 379 // and back patchs after we are done.
 380 //
 381
 382 // ResolveDefinitions - If we could not resolve some defs at parsing
 383 // time (forward branches, phi functions for loops, etc...) resolve the
 384 // defs now...
 385 //
 386 static void ResolveDefinitions(vector<ValueList> &LateResolvers,
 387                                vector<ValueList> *FutureLateResolvers) {
 388   // Loop over LateResolveDefs fixing up stuff that couldn't be resolved
 389   for (unsigned ty = 0; ty < LateResolvers.size(); ty++) {
 390     while (!LateResolvers[ty].empty()) {
 391       Value *V = LateResolvers[ty].back();
 392       assert(!isa<Type>(V) && "Types should be in LateResolveTypes!");
 393
 394       LateResolvers[ty].pop_back();
 395       ValID &DID = getValIDFromPlaceHolder(V);
 396
 397       Value *TheRealValue = getValNonImprovising(Type::getUniqueIDType(ty),DID);
 398       if (TheRealValue) {
 399         V->replaceAllUsesWith(TheRealValue);
 400         delete V;
 401       } else if (FutureLateResolvers) {
 402         // Functions have their unresolved items forwarded to the module late
 403         // resolver table
 404         InsertValue(V, *FutureLateResolvers);
 405       } else {
 406         if (DID.Type == ValID::NameVal)
 407           ThrowException("Reference to an invalid definition: '" +DID.getName()+
 408                          "' of type '" + V->getType()->getDescription() + "'",
 409                          getLineNumFromPlaceHolder(V));
 410         else
 411           ThrowException("Reference to an invalid definition: #" +
 412                          itostr(DID.Num) + " of type '" +
 413                          V->getType()->getDescription() + "'",
 414                          getLineNumFromPlaceHolder(V));
 415       }
 416     }
 417   }
 418
 419   LateResolvers.clear();
 420 }
 421
 422 // ResolveTypeTo - A brand new type was just declared.  This means that (if
 423 // name is not null) things referencing Name can be resolved.  Otherwise, things
 424 // refering to the number can be resolved.  Do this now.
 425 //
 426 static void ResolveTypeTo(char *Name, const Type *ToTy) {
 427   vector<PATypeHolder> &Types = inFunctionScope() ?
 428      CurMeth.Types : CurModule.Types;
 429
 430    ValID D;
 431    if (Name) D = ValID::create(Name);
 432    else      D = ValID::create((int)Types.size());
 433
 434    map<ValID, PATypeHolder> &LateResolver = inFunctionScope() ?
 435      CurMeth.LateResolveTypes : CurModule.LateResolveTypes;
 436
 437    map<ValID, PATypeHolder>::iterator I = LateResolver.find(D);
 438    if (I != LateResolver.end()) {
 439      ((DerivedType*)I->second.get())->refineAbstractTypeTo(ToTy);
 440      LateResolver.erase(I);
 441    }
 442 }
 443
 444 // ResolveTypes - At this point, all types should be resolved.  Any that aren't
 445 // are errors.
 446 //
 447 static void ResolveTypes(map<ValID, PATypeHolder> &LateResolveTypes) {
 448   if (!LateResolveTypes.empty()) {
 449     const ValID &DID = LateResolveTypes.begin()->first;
 450
 451     if (DID.Type == ValID::NameVal)
 452       ThrowException("Reference to an invalid type: '" +DID.getName() + "'");
 453     else
 454       ThrowException("Reference to an invalid type: #" + itostr(DID.Num));
 455   }
 456 }
 457
 458
 459 // setValueName - Set the specified value to the name given.  The name may be
 460 // null potentially, in which case this is a noop.  The string passed in is
 461 // assumed to be a malloc'd string buffer, and is freed by this function.
 462 //
 463 // This function returns true if the value has already been defined, but is
 464 // allowed to be redefined in the specified context.  If the name is a new name
 465 // for the typeplane, false is returned.
 466 //
 467 static bool setValueName(Value *V, char *NameStr) {
 468   if (NameStr == 0) return false;
 469
 470   string Name(NameStr);           // Copy string
 471   free(NameStr);                  // Free old string
 472
 473   if (V->getType() == Type::VoidTy)
 474     ThrowException("Can't assign name '" + Name +
 475                    "' to a null valued instruction!");
 476
 477   SymbolTable *ST = inFunctionScope() ?
 478     CurMeth.CurrentFunction->getSymbolTableSure() :
 479     CurModule.CurrentModule->getSymbolTableSure();
 480
 481   Value *Existing = ST->lookup(V->getType(), Name);
 482   if (Existing) {    // Inserting a name that is already defined???
 483     // There is only one case where this is allowed: when we are refining an
 484     // opaque type.  In this case, Existing will be an opaque type.
 485     if (const Type *Ty = dyn_cast<const Type>(Existing)) {
 486       if (const OpaqueType *OpTy = dyn_cast<OpaqueType>(Ty)) {
 487         // We ARE replacing an opaque type!
 488         ((OpaqueType*)OpTy)->refineAbstractTypeTo(cast<Type>(V));
 489         return true;
 490       }
 491     }
 492
 493     // Otherwise, we are a simple redefinition of a value, check to see if it
 494     // is defined the same as the old one...
 495     if (const Type *Ty = dyn_cast<const Type>(Existing)) {
 496       if (Ty == cast<const Type>(V)) return true;  // Yes, it's equal.
 497       // cerr << "Type: " << Ty->getDescription() << " != "
 498       //      << cast<const Type>(V)->getDescription() << "!\n";
 499     } else if (GlobalVariable *EGV = dyn_cast<GlobalVariable>(Existing)) {
 500       // We are allowed to redefine a global variable in two circumstances:
 501       // 1. If at least one of the globals is uninitialized or
 502       // 2. If both initializers have the same value.
 503       //
 504       // This can only be done if the const'ness of the vars is the same.
 505       //
 506       if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
 507         if (EGV->isConstant() == GV->isConstant() &&
 508             (!EGV->hasInitializer() || !GV->hasInitializer() ||
 509              EGV->getInitializer() == GV->getInitializer())) {
 510
 511           // Make sure the existing global version gets the initializer!
 512           if (GV->hasInitializer() && !EGV->hasInitializer())
 513             EGV->setInitializer(GV->getInitializer());
 514
 515           delete GV;     // Destroy the duplicate!
 516           return true;   // They are equivalent!
 517         }
 518       }
 519     }
 520     ThrowException("Redefinition of value named '" + Name + "' in the '" +
 521                    V->getType()->getDescription() + "' type plane!");
 522   }
 523
 524   V->setName(Name, ST);
 525   return false;
 526 }
 527
 528
 529 //===----------------------------------------------------------------------===//
 530 // Code for handling upreferences in type names...
 531 //
 532
 533 // TypeContains - Returns true if Ty contains E in it.
 534 //
 535 static bool TypeContains(const Type *Ty, const Type *E) {
 536   return find(df_begin(Ty), df_end(Ty), E) != df_end(Ty);
 537 }
 538
 539
 540 static vector<pair<unsigned, OpaqueType *> > UpRefs;
 541
 542 static PATypeHolder HandleUpRefs(const Type *ty) {
 543   PATypeHolder Ty(ty);
 544   UR_OUT("Type '" << ty->getDescription() <<
 545          "' newly formed.  Resolving upreferences.\n" <<
 546          UpRefs.size() << " upreferences active!\n");
 547   for (unsigned i = 0; i < UpRefs.size(); ) {
 548     UR_OUT("  UR#" << i << " - TypeContains(" << Ty->getDescription() << ", "
 549            << UpRefs[i].second->getDescription() << ") = "
 550            << (TypeContains(Ty, UpRefs[i].second) ? "true" : "false") << endl);
 551     if (TypeContains(Ty, UpRefs[i].second)) {
 552       unsigned Level = --UpRefs[i].first;   // Decrement level of upreference
 553       UR_OUT("  Uplevel Ref Level = " << Level << endl);
 554       if (Level == 0) {                     // Upreference should be resolved!
 555         UR_OUT("  * Resolving upreference for "
 556                << UpRefs[i].second->getDescription() << endl;
 557                string OldName = UpRefs[i].second->getDescription());
 558         UpRefs[i].second->refineAbstractTypeTo(Ty);
 559         UpRefs.erase(UpRefs.begin()+i);     // Remove from upreference list...
 560         UR_OUT("  * Type '" << OldName << "' refined upreference to: "
 561                << (const void*)Ty << ", " << Ty->getDescription() << endl);
 562         continue;
 563       }
 564     }
 565
 566     ++i;                                  // Otherwise, no resolve, move on...
 567   }
 568   // FIXME: TODO: this should return the updated type
 569   return Ty;
 570 }
 571
 572
 573 //===----------------------------------------------------------------------===//
 574 //            RunVMAsmParser - Define an interface to this parser
 575 //===----------------------------------------------------------------------===//
 576 //
 577 Module *RunVMAsmParser(const string &Filename, FILE *F) {
 578   llvmAsmin = F;
 579   CurFilename = Filename;
 580   llvmAsmlineno = 1;      // Reset the current line number...
 581
 582   CurModule.CurrentModule = new Module();  // Allocate a new module to read
 583   yyparse();       // Parse the file.
 584   Module *Result = ParserResult;
 585   llvmAsmin = stdin;    // F is about to go away, don't use it anymore...
 586   ParserResult = 0;
 587
 588   return Result;
 589 }
 590
 591 %}
 592
 593 %union {
 594   Module                           *ModuleVal;
 595   Function                         *FunctionVal;
 596   std::pair<Argument*, char*>      *ArgVal;
 597   BasicBlock                       *BasicBlockVal;
 598   TerminatorInst                   *TermInstVal;
 599   Instruction                      *InstVal;
 600   Constant                         *ConstVal;
 601
 602   const Type                       *PrimType;
 603   PATypeHolder                     *TypeVal;
 604   Value                            *ValueVal;
 605
 606   std::list<std::pair<Argument*,char*> > *ArgList;
 607   std::vector<Value*>              *ValueList;
 608   std::list<PATypeHolder>          *TypeList;
 609   std::list<std::pair<Value*,
 610                       BasicBlock*> > *PHIList; // Represent the RHS of PHI node
 611   std::vector<std::pair<Constant*, BasicBlock*> > *JumpTable;
 612   std::vector<Constant*>           *ConstVector;
 613
 614   int64_t                           SInt64Val;
 615   uint64_t                          UInt64Val;
 616   int                               SIntVal;
 617   unsigned                          UIntVal;
 618   double                            FPVal;
 619   bool                              BoolVal;
 620
 621   char                             *StrVal;   // This memory is strdup'd!
 622   ValID                             ValIDVal; // strdup'd memory maybe!
 623
 624   Instruction::UnaryOps             UnaryOpVal;
 625   Instruction::BinaryOps            BinaryOpVal;
 626   Instruction::TermOps              TermOpVal;
 627   Instruction::MemoryOps            MemOpVal;
 628   Instruction::OtherOps             OtherOpVal;
 629 }
 630
 631 %type <ModuleVal>     Module FunctionList
 632 %type <FunctionVal>   Function FunctionProto FunctionHeader BasicBlockList
 633 %type <BasicBlockVal> BasicBlock InstructionList
 634 %type <TermInstVal>   BBTerminatorInst
 635 %type <InstVal>       Inst InstVal MemoryInst
 636 %type <ConstVal>      ConstVal ConstExpr
 637 %type <ConstVector>   ConstVector
 638 %type <ArgList>       ArgList ArgListH
 639 %type <ArgVal>        ArgVal
 640 %type <PHIList>       PHIList
 641 %type <ValueList>     ValueRefList ValueRefListE  // For call param lists
 642 %type <ValueList>     IndexList                   // For GEP derived indices
 643 %type <TypeList>      TypeListI ArgTypeListI
 644 %type <JumpTable>     JumpTable
 645 %type <BoolVal>       GlobalType OptInternal      // GLOBAL or CONSTANT? Intern?
 646
 647 // ValueRef - Unresolved reference to a definition or BB
 648 %type <ValIDVal>      ValueRef ConstValueRef SymbolicValueRef
 649 %type <ValueVal>      ResolvedVal            // <type> <valref> pair
 650 // Tokens and types for handling constant integer values
 651 //
 652 // ESINT64VAL - A negative number within long long range
 653 %token <SInt64Val> ESINT64VAL
 654
 655 // EUINT64VAL - A positive number within uns. long long range
 656 %token <UInt64Val> EUINT64VAL
 657 %type  <SInt64Val> EINT64VAL
 658
 659 %token  <SIntVal>   SINTVAL   // Signed 32 bit ints...
 660 %token  <UIntVal>   UINTVAL   // Unsigned 32 bit ints...
 661 %type   <SIntVal>   INTVAL
 662 %token  <FPVal>     FPVAL     // Float or Double constant
 663
 664 // Built in types...
 665 %type  <TypeVal> Types TypesV UpRTypes UpRTypesV
 666 %type  <PrimType> SIntType UIntType IntType FPType PrimType   // Classifications
 667 %token <PrimType> VOID BOOL SBYTE UBYTE SHORT USHORT INT UINT LONG ULONG
 668 %token <PrimType> FLOAT DOUBLE TYPE LABEL
 669
 670 %token <StrVal>     VAR_ID LABELSTR STRINGCONSTANT
 671 %type  <StrVal>  OptVAR_ID OptAssign FuncName
 672
 673
 674 %token IMPLEMENTATION TRUE FALSE BEGINTOK ENDTOK DECLARE GLOBAL CONSTANT UNINIT
 675 %token TO EXCEPT DOTDOTDOT STRING NULL_TOK CONST INTERNAL OPAQUE
 676
 677 // Basic Block Terminating Operators
 678 %token <TermOpVal> RET BR SWITCH
 679
 680 // Unary Operators
 681 %type  <UnaryOpVal> UnaryOps  // all the unary operators
 682 %token <UnaryOpVal> NOT
 683
 684 // Binary Operators
 685 %type  <BinaryOpVal> BinaryOps  // all the binary operators
 686 %token <BinaryOpVal> ADD SUB MUL DIV REM AND OR XOR
 687 %token <BinaryOpVal> SETLE SETGE SETLT SETGT SETEQ SETNE  // Binary Comarators
 688
 689 // Memory Instructions
 690 %token <MemOpVal> MALLOC ALLOCA FREE LOAD STORE GETELEMENTPTR
 691
 692 // Other Operators
 693 %type  <OtherOpVal> ShiftOps
 694 %token <OtherOpVal> PHI CALL INVOKE CAST SHL SHR
 695
 696 %start Module
 697 %%
 698
 699 // Handle constant integer size restriction and conversion...
 700 //
 701
 702 INTVAL : SINTVAL;
 703 INTVAL : UINTVAL {
 704   if ($1 > (uint32_t)INT32_MAX)     // Outside of my range!
 705     ThrowException("Value too large for type!");
 706   $$ = (int32_t)$1;
 707 };
 708
 709
 710 EINT64VAL : ESINT64VAL;      // These have same type and can't cause problems...
 711 EINT64VAL : EUINT64VAL {
 712   if ($1 > (uint64_t)INT64_MAX)     // Outside of my range!
 713     ThrowException("Value too large for type!");
 714   $$ = (int64_t)$1;
 715 };
 716
 717 // Operations that are notably excluded from this list include:
 718 // RET, BR, & SWITCH because they end basic blocks and are treated specially.
 719 //
 720 UnaryOps  : NOT;
 721 BinaryOps : ADD | SUB | MUL | DIV | REM | AND | OR | XOR;
 722 BinaryOps : SETLE | SETGE | SETLT | SETGT | SETEQ | SETNE;
 723 ShiftOps  : SHL | SHR;
 724
 725 // These are some types that allow classification if we only want a particular
 726 // thing... for example, only a signed, unsigned, or integral type.
 727 SIntType :  LONG |  INT |  SHORT | SBYTE;
 728 UIntType : ULONG | UINT | USHORT | UBYTE;
 729 IntType  : SIntType | UIntType;
 730 FPType   : FLOAT | DOUBLE;
 731
 732 // OptAssign - Value producing statements have an optional assignment component
 733 OptAssign : VAR_ID '=' {
 734     $$ = $1;
 735   }
 736   | /*empty*/ {
 737     $$ = 0;
 738   };
 739
 740 OptInternal : INTERNAL { $$ = true; } | /*empty*/ { $$ = false; };
 741
 742 //===----------------------------------------------------------------------===//
 743 // Types includes all predefined types... except void, because it can only be
 744 // used in specific contexts (function returning void for example).  To have
 745 // access to it, a user must explicitly use TypesV.
 746 //
 747
 748 // TypesV includes all of 'Types', but it also includes the void type.
 749 TypesV    : Types    | VOID { $$ = new PATypeHolder($1); };
 750 UpRTypesV : UpRTypes | VOID { $$ = new PATypeHolder($1); };
 751
 752 Types     : UpRTypes {
 753     if (UpRefs.size())
 754       ThrowException("Invalid upreference in type: " + (*$1)->getDescription());
 755     $$ = $1;
 756   };
 757
 758
 759 // Derived types are added later...
 760 //
 761 PrimType : BOOL | SBYTE | UBYTE | SHORT  | USHORT | INT   | UINT ;
 762 PrimType : LONG | ULONG | FLOAT | DOUBLE | TYPE   | LABEL;
 763 UpRTypes : OPAQUE {
 764     $$ = new PATypeHolder(OpaqueType::get());
 765   }
 766   | PrimType {
 767     $$ = new PATypeHolder($1);
 768   };
 769 UpRTypes : ValueRef {                    // Named types are also simple types...
 770   $$ = new PATypeHolder(getTypeVal($1));
 771 };
 772
 773 // Include derived types in the Types production.
 774 //
 775 UpRTypes : '\\' EUINT64VAL {                   // Type UpReference
 776     if ($2 > (uint64_t)INT64_MAX) ThrowException("Value out of range!");
 777     OpaqueType *OT = OpaqueType::get();        // Use temporary placeholder
 778     UpRefs.push_back(make_pair((unsigned)$2, OT));  // Add to vector...
 779     $$ = new PATypeHolder(OT);
 780     UR_OUT("New Upreference!\n");
 781   }
 782   | UpRTypesV '(' ArgTypeListI ')' {           // Function derived type?
 783     vector<const Type*> Params;
 784     mapto($3->begin(), $3->end(), std::back_inserter(Params),
 785           std::mem_fun_ref(&PATypeHandle<Type>::get));
 786     bool isVarArg = Params.size() && Params.back() == Type::VoidTy;
 787     if (isVarArg) Params.pop_back();
 788
 789     $$ = new PATypeHolder(HandleUpRefs(FunctionType::get(*$1,Params,isVarArg)));
 790     delete $3;      // Delete the argument list
 791     delete $1;      // Delete the old type handle
 792   }
 793   | '[' EUINT64VAL 'x' UpRTypes ']' {          // Sized array type?
 794     $$ = new PATypeHolder(HandleUpRefs(ArrayType::get(*$4, (unsigned)$2)));
 795     delete $4;
 796   }
 797   | '{' TypeListI '}' {                        // Structure type?
 798     vector<const Type*> Elements;
 799     mapto($2->begin(), $2->end(), std::back_inserter(Elements),
 800         std::mem_fun_ref(&PATypeHandle<Type>::get));
 801
 802     $$ = new PATypeHolder(HandleUpRefs(StructType::get(Elements)));
 803     delete $2;
 804   }
 805   | '{' '}' {                                  // Empty structure type?
 806     $$ = new PATypeHolder(StructType::get(vector<const Type*>()));
 807   }
 808   | UpRTypes '*' {                             // Pointer type?
 809     $$ = new PATypeHolder(HandleUpRefs(PointerType::get(*$1)));
 810     delete $1;
 811   };
 812
 813 // TypeList - Used for struct declarations and as a basis for function type
 814 // declaration type lists
 815 //
 816 TypeListI : UpRTypes {
 817     $$ = new list<PATypeHolder>();
 818     $$->push_back(*$1); delete $1;
 819   }
 820   | TypeListI ',' UpRTypes {
 821     ($$=$1)->push_back(*$3); delete $3;
 822   };
 823
 824 // ArgTypeList - List of types for a function type declaration...
 825 ArgTypeListI : TypeListI
 826   | TypeListI ',' DOTDOTDOT {
 827     ($$=$1)->push_back(Type::VoidTy);
 828   }
 829   | DOTDOTDOT {
 830     ($$ = new list<PATypeHolder>())->push_back(Type::VoidTy);
 831   }
 832   | /*empty*/ {
 833     $$ = new list<PATypeHolder>();
 834   };
 835
 836 // ConstVal - The various declarations that go into the constant pool.  This
 837 // includes all forward declarations of types, constants, and functions.
 838 //
 839 ConstVal: Types '[' ConstVector ']' { // Nonempty unsized arr
 840     const ArrayType *ATy = dyn_cast<const ArrayType>($1->get());
 841     if (ATy == 0)
 842       ThrowException("Cannot make array constant with type: '" +
 843                      (*$1)->getDescription() + "'!");
 844     const Type *ETy = ATy->getElementType();
 845     int NumElements = ATy->getNumElements();
 846
 847     // Verify that we have the correct size...
 848     if (NumElements != -1 && NumElements != (int)$3->size())
 849       ThrowException("Type mismatch: constant sized array initialized with " +
 850                      utostr($3->size()) +  " arguments, but has size of " +
 851                      itostr(NumElements) + "!");
 852
 853     // Verify all elements are correct type!
 854     for (unsigned i = 0; i < $3->size(); i++) {
 855       if (ETy != (*$3)[i]->getType())
 856         ThrowException("Element #" + utostr(i) + " is not of type '" +
 857                        ETy->getDescription() +"' as required!\nIt is of type '"+
 858                        (*$3)[i]->getType()->getDescription() + "'.");
 859     }
 860
 861     $$ = ConstantArray::get(ATy, *$3);
 862     delete $1; delete $3;
 863   }
 864   | Types '[' ']' {
 865     const ArrayType *ATy = dyn_cast<const ArrayType>($1->get());
 866     if (ATy == 0)
 867       ThrowException("Cannot make array constant with type: '" +
 868                      (*$1)->getDescription() + "'!");
 869
 870     int NumElements = ATy->getNumElements();
 871     if (NumElements != -1 && NumElements != 0)
 872       ThrowException("Type mismatch: constant sized array initialized with 0"
 873                      " arguments, but has size of " + itostr(NumElements) +"!");
 874     $$ = ConstantArray::get(ATy, vector<Constant*>());
 875     delete $1;
 876   }
 877   | Types 'c' STRINGCONSTANT {
 878     const ArrayType *ATy = dyn_cast<const ArrayType>($1->get());
 879     if (ATy == 0)
 880       ThrowException("Cannot make array constant with type: '" +
 881                      (*$1)->getDescription() + "'!");
 882
 883     int NumElements = ATy->getNumElements();
 884     const Type *ETy = ATy->getElementType();
 885     char *EndStr = UnEscapeLexed($3, true);
 886     if (NumElements != -1 && NumElements != (EndStr-$3))
 887       ThrowException("Can't build string constant of size " +
 888                      itostr((int)(EndStr-$3)) +
 889                      " when array has size " + itostr(NumElements) + "!");
 890     vector<Constant*> Vals;
 891     if (ETy == Type::SByteTy) {
 892       for (char *C = $3; C != EndStr; ++C)
 893         Vals.push_back(ConstantSInt::get(ETy, *C));
 894     } else if (ETy == Type::UByteTy) {
 895       for (char *C = $3; C != EndStr; ++C)
 896         Vals.push_back(ConstantUInt::get(ETy, *C));
 897     } else {
 898       free($3);
 899       ThrowException("Cannot build string arrays of non byte sized elements!");
 900     }
 901     free($3);
 902     $$ = ConstantArray::get(ATy, Vals);
 903     delete $1;
 904   }
 905   | Types '{' ConstVector '}' {
 906     const StructType *STy = dyn_cast<const StructType>($1->get());
 907     if (STy == 0)
 908       ThrowException("Cannot make struct constant with type: '" +
 909                      (*$1)->getDescription() + "'!");
 910     // FIXME: TODO: Check to see that the constants are compatible with the type
 911     // initializer!
 912     $$ = ConstantStruct::get(STy, *$3);
 913     delete $1; delete $3;
 914   }
 915   | Types NULL_TOK {
 916     const PointerType *PTy = dyn_cast<const PointerType>($1->get());
 917     if (PTy == 0)
 918       ThrowException("Cannot make null pointer constant with type: '" +
 919                      (*$1)->getDescription() + "'!");
 920
 921     $$ = ConstantPointerNull::get(PTy);
 922     delete $1;
 923   }
 924   | Types SymbolicValueRef {
 925     const PointerType *Ty = dyn_cast<const PointerType>($1->get());
 926     if (Ty == 0)
 927       ThrowException("Global const reference must be a pointer type!");
 928
 929     Value *V = getValNonImprovising(Ty, $2);
 930
 931     // If this is an initializer for a constant pointer, which is referencing a
 932     // (currently) undefined variable, create a stub now that shall be replaced
 933     // in the future with the right type of variable.
 934     //
 935     if (V == 0) {
 936       assert(isa<PointerType>(Ty) && "Globals may only be used as pointers!");
 937       const PointerType *PT = cast<PointerType>(Ty);
 938
 939       // First check to see if the forward references value is already created!
 940       PerModuleInfo::GlobalRefsType::iterator I =
 941         CurModule.GlobalRefs.find(make_pair(PT, $2));
 942
 943       if (I != CurModule.GlobalRefs.end()) {
 944         V = I->second;             // Placeholder already exists, use it...
 945       } else {
 946         // TODO: Include line number info by creating a subclass of
 947         // TODO: GlobalVariable here that includes the said information!
 948
 949         // Create a placeholder for the global variable reference...
 950         GlobalVariable *GV = new GlobalVariable(PT->getElementType(),
 951                                                 false, true);
 952         // Keep track of the fact that we have a forward ref to recycle it
 953         CurModule.GlobalRefs.insert(make_pair(make_pair(PT, $2), GV));
 954
 955         // Must temporarily push this value into the module table...
 956         CurModule.CurrentModule->getGlobalList().push_back(GV);
 957         V = GV;
 958       }
 959     }
 960
 961     GlobalValue *GV = cast<GlobalValue>(V);
 962     $$ = ConstantPointerRef::get(GV);
 963     delete $1;            // Free the type handle
 964   }
 965   | ConstExpr {
 966     $$ = $1;
 967   };
 968
 969
 970 // FIXME: ConstExpr::get never return null!  Do checking here in the parser.
 971 ConstExpr: Types CAST ConstVal {
 972     $$ = ConstantExpr::get(Instruction::Cast, $3, $1->get());
 973     if ($$ == 0) ThrowException("constant expression builder returned null!");
 974     delete $1;
 975   }
 976   | Types GETELEMENTPTR '(' ConstVal IndexList ')' {
 977     if (!isa<PointerType>($4->getType()))
 978       ThrowException("GetElementPtr requires a pointer operand!");
 979
 980     const Type *IdxTy =
 981       GetElementPtrInst::getIndexedType($4->getType(), *$5, true);
 982     if (!IdxTy)
 983       ThrowException("Index list invalid for constant getelementptr!");
 984     if (PointerType::get(IdxTy) != $1->get())
 985       ThrowException("Declared type of constant getelementptr is incorrect!");
 986
 987     vector<Constant*> IdxVec;
 988     for (unsigned i = 0, e = $5->size(); i != e; ++i)
 989       if (Constant *C = dyn_cast<Constant>((*$5)[i]))
 990         IdxVec.push_back(C);
 991       else
 992         ThrowException("Indices to constant getelementptr must be constants!");
 993
 994     delete $5;
 995
 996     $$ = ConstantExpr::getGetElementPtr($4, IdxVec);
 997     delete $1;
 998   }
 999   | Types UnaryOps ConstVal {
1000     $$ = ConstantExpr::get($2, $3, $1->get());
1001     delete $1;
1002   }
1003   | Types BinaryOps ConstVal ',' ConstVal {
1004     if ($3->getType() != $5->getType())
1005       ThrowException("Binary operator types must match!");
1006     if ($1->get() != $3->getType())
1007       ThrowException("Return type of binary constant must match arguments!");
1008     $$ = ConstantExpr::get($2, $3, $5);
1009     delete $1;
1010   }
1011   | Types ShiftOps ConstVal ',' ConstVal {
1012     if ($1->get() != $3->getType())
1013       ThrowException("Return type of shift constant must match argument!");
1014     if ($5->getType() != Type::UByteTy)
1015       ThrowException("Shift count for shift constant must be unsigned byte!");
1016
1017     $$ = ConstantExpr::get($2, $3, $5);
1018     delete $1;
1019   }
1020   ;
1021
1022
1023 ConstVal : SIntType EINT64VAL {     // integral constants
1024     if (!ConstantSInt::isValueValidForType($1, $2))
1025       ThrowException("Constant value doesn't fit in type!");
1026     $$ = ConstantSInt::get($1, $2);
1027   }
1028   | UIntType EUINT64VAL {           // integral constants
1029     if (!ConstantUInt::isValueValidForType($1, $2))
1030       ThrowException("Constant value doesn't fit in type!");
1031     $$ = ConstantUInt::get($1, $2);
1032   }
1033   | BOOL TRUE {                     // Boolean constants
1034     $$ = ConstantBool::True;
1035   }
1036   | BOOL FALSE {                    // Boolean constants
1037     $$ = ConstantBool::False;
1038   }
1039   | FPType FPVAL {                   // Float & Double constants
1040     $$ = ConstantFP::get($1, $2);
1041   };
1042
1043 // ConstVector - A list of comma seperated constants.
1044 ConstVector : ConstVector ',' ConstVal {
1045     ($$ = $1)->push_back($3);
1046   }
1047   | ConstVal {
1048     $$ = new vector<Constant*>();
1049     $$->push_back($1);
1050   };
1051
1052
1053 // GlobalType - Match either GLOBAL or CONSTANT for global declarations...
1054 GlobalType : GLOBAL { $$ = false; } | CONSTANT { $$ = true; };
1055
1056
1057 //===----------------------------------------------------------------------===//
1058 //                             Rules to match Modules
1059 //===----------------------------------------------------------------------===//
1060
1061 // Module rule: Capture the result of parsing the whole file into a result
1062 // variable...
1063 //
1064 Module : FunctionList {
1065   $$ = ParserResult = $1;
1066   CurModule.ModuleDone();
1067 };
1068
1069 // FunctionList - A list of functions, preceeded by a constant pool.
1070 //
1071 FunctionList : FunctionList Function {
1072     $$ = $1;
1073     assert($2->getParent() == 0 && "Function already in module!");
1074     $1->getFunctionList().push_back($2);
1075     CurMeth.FunctionDone();
1076   }
1077   | FunctionList FunctionProto {
1078     $$ = $1;
1079   }
1080   | FunctionList IMPLEMENTATION {
1081     $$ = $1;
1082   }
1083   | ConstPool {
1084     $$ = CurModule.CurrentModule;
1085     // Resolve circular types before we parse the body of the module
1086     ResolveTypes(CurModule.LateResolveTypes);
1087   };
1088
1089 // ConstPool - Constants with optional names assigned to them.
1090 ConstPool : ConstPool OptAssign CONST ConstVal {
1091     if (setValueName($4, $2)) { assert(0 && "No redefinitions allowed!"); }
1092     InsertValue($4);
1093   }
1094   | ConstPool OptAssign TYPE TypesV {  // Types can be defined in the const pool
1095     // Eagerly resolve types.  This is not an optimization, this is a
1096     // requirement that is due to the fact that we could have this:
1097     //
1098     // %list = type { %list * }
1099     // %list = type { %list * }    ; repeated type decl
1100     //
1101     // If types are not resolved eagerly, then the two types will not be
1102     // determined to be the same type!
1103     //
1104     ResolveTypeTo($2, $4->get());
1105
1106     // TODO: FIXME when Type are not const
1107     if (!setValueName(const_cast<Type*>($4->get()), $2)) {
1108       // If this is not a redefinition of a type...
1109       if (!$2) {
1110         InsertType($4->get(),
1111                    inFunctionScope() ? CurMeth.Types : CurModule.Types);
1112       }
1113     }
1114
1115     delete $4;
1116   }
1117   | ConstPool FunctionProto {       // Function prototypes can be in const pool
1118   }
1119   | ConstPool OptAssign OptInternal GlobalType ConstVal {
1120     const Type *Ty = $5->getType();
1121     // Global declarations appear in Constant Pool
1122     Constant *Initializer = $5;
1123     if (Initializer == 0)
1124       ThrowException("Global value initializer is not a constant!");
1125
1126     GlobalVariable *GV = new GlobalVariable(Ty, $4, $3, Initializer);
1127     if (!setValueName(GV, $2)) {   // If not redefining...
1128       CurModule.CurrentModule->getGlobalList().push_back(GV);
1129       int Slot = InsertValue(GV, CurModule.Values);
1130
1131       if (Slot != -1) {
1132         CurModule.DeclareNewGlobalValue(GV, ValID::create(Slot));
1133       } else {
1134         CurModule.DeclareNewGlobalValue(GV, ValID::create(
1135                                                 (char*)GV->getName().c_str()));
1136       }
1137     }
1138   }
1139   | ConstPool OptAssign OptInternal UNINIT GlobalType Types {
1140     const Type *Ty = *$6;
1141     // Global declarations appear in Constant Pool
1142     GlobalVariable *GV = new GlobalVariable(Ty, $5, $3);
1143     if (!setValueName(GV, $2)) {   // If not redefining...
1144       CurModule.CurrentModule->getGlobalList().push_back(GV);
1145       int Slot = InsertValue(GV, CurModule.Values);
1146
1147       if (Slot != -1) {
1148         CurModule.DeclareNewGlobalValue(GV, ValID::create(Slot));
1149       } else {
1150         assert(GV->hasName() && "Not named and not numbered!?");
1151         CurModule.DeclareNewGlobalValue(GV, ValID::create(
1152                                                 (char*)GV->getName().c_str()));
1153       }
1154     }
1155     delete $6;
1156   }
1157   | /* empty: end of list */ {
1158   };
1159
1160
1161 //===----------------------------------------------------------------------===//
1162 //                       Rules to match Function Headers
1163 //===----------------------------------------------------------------------===//
1164
1165 OptVAR_ID : VAR_ID | /*empty*/ { $$ = 0; };
1166
1167 ArgVal : Types OptVAR_ID {
1168   $$ = new pair<Argument*, char*>(new Argument(*$1), $2);
1169   delete $1;  // Delete the type handle..
1170 };
1171
1172 ArgListH : ArgVal ',' ArgListH {
1173     $$ = $3;
1174     $3->push_front(*$1);
1175     delete $1;
1176   }
1177   | ArgVal {
1178     $$ = new list<pair<Argument*,char*> >();
1179     $$->push_front(*$1);
1180     delete $1;
1181   }
1182   | DOTDOTDOT {
1183     $$ = new list<pair<Argument*, char*> >();
1184     $$->push_front(pair<Argument*,char*>(new Argument(Type::VoidTy), 0));
1185   };
1186
1187 ArgList : ArgListH {
1188     $$ = $1;
1189   }
1190   | /* empty */ {
1191     $$ = 0;
1192   };
1193
1194 FuncName : VAR_ID | STRINGCONSTANT;
1195
1196 FunctionHeaderH : OptInternal TypesV FuncName '(' ArgList ')' {
1197   UnEscapeLexed($3);
1198   string FunctionName($3);
1199
1200   vector<const Type*> ParamTypeList;
1201   if ($5)
1202     for (list<pair<Argument*,char*> >::iterator I = $5->begin();
1203          I != $5->end(); ++I)
1204       ParamTypeList.push_back(I->first->getType());
1205
1206   bool isVarArg = ParamTypeList.size() && ParamTypeList.back() == Type::VoidTy;
1207   if (isVarArg) ParamTypeList.pop_back();
1208
1209   const FunctionType *MT = FunctionType::get(*$2, ParamTypeList, isVarArg);
1210   const PointerType *PMT = PointerType::get(MT);
1211   delete $2;
1212
1213   Function *M = 0;
1214   if (SymbolTable *ST = CurModule.CurrentModule->getSymbolTable()) {
1215     // Is the function already in symtab?
1216     if (Value *V = ST->lookup(PMT, FunctionName)) {
1217       M = cast<Function>(V);
1218
1219       // Yes it is.  If this is the case, either we need to be a forward decl,
1220       // or it needs to be.
1221       if (!CurMeth.isDeclare && !M->isExternal())
1222         ThrowException("Redefinition of function '" + FunctionName + "'!");
1223
1224       // Make sure that we keep track of the internal marker, even if there was
1225       // a previous "declare".
1226       if ($1)
1227         M->setInternalLinkage(true);
1228
1229       // If we found a preexisting function prototype, remove it from the
1230       // module, so that we don't get spurious conflicts with global & local
1231       // variables.
1232       //
1233       CurModule.CurrentModule->getFunctionList().remove(M);
1234     }
1235   }
1236
1237   if (M == 0) {  // Not already defined?
1238     M = new Function(MT, $1, FunctionName);
1239     InsertValue(M, CurModule.Values);
1240     CurModule.DeclareNewGlobalValue(M, ValID::create($3));
1241   }
1242   free($3);  // Free strdup'd memory!
1243
1244   CurMeth.FunctionStart(M);
1245
1246   // Add all of the arguments we parsed to the function...
1247   if ($5 && !CurMeth.isDeclare) {        // Is null if empty...
1248     for (list<pair<Argument*, char*> >::iterator I = $5->begin();
1249          I != $5->end(); ++I) {
1250       if (setValueName(I->first, I->second)) {  // Insert into symtab...
1251         assert(0 && "No arg redef allowed!");
1252       }
1253
1254       InsertValue(I->first);
1255       M->getArgumentList().push_back(I->first);
1256     }
1257     delete $5;                     // We're now done with the argument list
1258   } else if ($5) {
1259     // If we are a declaration, we should free the memory for the argument list!
1260     for (list<pair<Argument*, char*> >::iterator I = $5->begin(), E = $5->end();
1261          I != E; ++I) {
1262       if (I->second) free(I->second);   // Free the memory for the name...
1263       delete I->first;                  // Free the unused function argument
1264     }
1265     delete $5;                          // Free the memory for the list itself
1266   }
1267 };
1268
1269 BEGIN : BEGINTOK | '{';                // Allow BEGIN or '{' to start a function
1270
1271 FunctionHeader : FunctionHeaderH BEGIN {
1272   $$ = CurMeth.CurrentFunction;
1273
1274   // Resolve circular types before we parse the body of the function.
1275   ResolveTypes(CurMeth.LateResolveTypes);
1276 };
1277
1278 END : ENDTOK | '}';                    // Allow end of '}' to end a function
1279
1280 Function : BasicBlockList END {
1281   $$ = $1;
1282 };
1283
1284 FunctionProto : DECLARE { CurMeth.isDeclare = true; } FunctionHeaderH {
1285   $$ = CurMeth.CurrentFunction;
1286   assert($$->getParent() == 0 && "Function already in module!");
1287   CurModule.CurrentModule->getFunctionList().push_back($$);
1288   CurMeth.FunctionDone();
1289 };
1290
1291 //===----------------------------------------------------------------------===//
1292 //                        Rules to match Basic Blocks
1293 //===----------------------------------------------------------------------===//
1294
1295 ConstValueRef : ESINT64VAL {    // A reference to a direct constant
1296     $$ = ValID::create($1);
1297   }
1298   | EUINT64VAL {
1299     $$ = ValID::create($1);
1300   }
1301   | FPVAL {                     // Perhaps it's an FP constant?
1302     $$ = ValID::create($1);
1303   }
1304   | TRUE {
1305     $$ = ValID::create((int64_t)1);
1306   }
1307   | FALSE {
1308     $$ = ValID::create((int64_t)0);
1309   }
1310   | NULL_TOK {
1311     $$ = ValID::createNull();
1312   }
1313   ;
1314
1315 // SymbolicValueRef - Reference to one of two ways of symbolically refering to
1316 // another value.
1317 //
1318 SymbolicValueRef : INTVAL {  // Is it an integer reference...?
1319     $$ = ValID::create($1);
1320   }
1321   | VAR_ID {                 // Is it a named reference...?
1322     $$ = ValID::create($1);
1323   };
1324
1325 // ValueRef - A reference to a definition... either constant or symbolic
1326 ValueRef : SymbolicValueRef | ConstValueRef;
1327
1328
1329 // ResolvedVal - a <type> <value> pair.  This is used only in cases where the
1330 // type immediately preceeds the value reference, and allows complex constant
1331 // pool references (for things like: 'ret [2 x int] [ int 12, int 42]')
1332 ResolvedVal : Types ValueRef {
1333     $$ = getVal(*$1, $2); delete $1;
1334   }
1335   | ConstExpr {
1336     $$ = $1;
1337   };
1338
1339 BasicBlockList : BasicBlockList BasicBlock {
1340     ($$ = $1)->getBasicBlockList().push_back($2);
1341   }
1342   | FunctionHeader BasicBlock { // Do not allow functions with 0 basic blocks
1343     ($$ = $1)->getBasicBlockList().push_back($2);
1344   };
1345
1346
1347 // Basic blocks are terminated by branching instructions:
1348 // br, br/cc, switch, ret
1349 //
1350 BasicBlock : InstructionList OptAssign BBTerminatorInst  {
1351     if (setValueName($3, $2)) { assert(0 && "No redefn allowed!"); }
1352     InsertValue($3);
1353
1354     $1->getInstList().push_back($3);
1355     InsertValue($1);
1356     $$ = $1;
1357   }
1358   | LABELSTR InstructionList OptAssign BBTerminatorInst  {
1359     if (setValueName($4, $3)) { assert(0 && "No redefn allowed!"); }
1360     InsertValue($4);
1361
1362     $2->getInstList().push_back($4);
1363     if (setValueName($2, $1)) { assert(0 && "No label redef allowed!"); }
1364
1365     InsertValue($2);
1366     $$ = $2;
1367   };
1368
1369 InstructionList : InstructionList Inst {
1370     $1->getInstList().push_back($2);
1371     $$ = $1;
1372   }
1373   | /* empty */ {
1374     $$ = new BasicBlock();
1375   };
1376
1377 BBTerminatorInst : RET ResolvedVal {              // Return with a result...
1378     $$ = new ReturnInst($2);
1379   }
1380   | RET VOID {                                       // Return with no result...
1381     $$ = new ReturnInst();
1382   }
1383   | BR LABEL ValueRef {                         // Unconditional Branch...
1384     $$ = new BranchInst(cast<BasicBlock>(getVal(Type::LabelTy, $3)));
1385   }                                                  // Conditional Branch...
1386   | BR BOOL ValueRef ',' LABEL ValueRef ',' LABEL ValueRef {
1387     $$ = new BranchInst(cast<BasicBlock>(getVal(Type::LabelTy, $6)),
1388                         cast<BasicBlock>(getVal(Type::LabelTy, $9)),
1389                         getVal(Type::BoolTy, $3));
1390   }
1391   | SWITCH IntType ValueRef ',' LABEL ValueRef '[' JumpTable ']' {
1392     SwitchInst *S = new SwitchInst(getVal($2, $3),
1393                                    cast<BasicBlock>(getVal(Type::LabelTy, $6)));
1394     $$ = S;
1395
1396     vector<pair<Constant*,BasicBlock*> >::iterator I = $8->begin(),
1397       E = $8->end();
1398     for (; I != E; ++I)
1399       S->dest_push_back(I->first, I->second);
1400   }
1401   | INVOKE TypesV ValueRef '(' ValueRefListE ')' TO ResolvedVal
1402     EXCEPT ResolvedVal {
1403     const PointerType *PMTy;
1404     const FunctionType *Ty;
1405
1406     if (!(PMTy = dyn_cast<PointerType>($2->get())) ||
1407         !(Ty = dyn_cast<FunctionType>(PMTy->getElementType()))) {
1408       // Pull out the types of all of the arguments...
1409       vector<const Type*> ParamTypes;
1410       if ($5) {
1411         for (vector<Value*>::iterator I = $5->begin(), E = $5->end(); I!=E; ++I)
1412           ParamTypes.push_back((*I)->getType());
1413       }
1414
1415       bool isVarArg = ParamTypes.size() && ParamTypes.back() == Type::VoidTy;
1416       if (isVarArg) ParamTypes.pop_back();
1417
1418       Ty = FunctionType::get($2->get(), ParamTypes, isVarArg);
1419       PMTy = PointerType::get(Ty);
1420     }
1421     delete $2;
1422
1423     Value *V = getVal(PMTy, $3);   // Get the function we're calling...
1424
1425     BasicBlock *Normal = dyn_cast<BasicBlock>($8);
1426     BasicBlock *Except = dyn_cast<BasicBlock>($10);
1427
1428     if (Normal == 0 || Except == 0)
1429       ThrowException("Invoke instruction without label destinations!");
1430
1431     // Create the call node...
1432     if (!$5) {                                   // Has no arguments?
1433       $$ = new InvokeInst(V, Normal, Except, vector<Value*>());
1434     } else {                                     // Has arguments?
1435       // Loop through FunctionType's arguments and ensure they are specified
1436       // correctly!
1437       //
1438       FunctionType::ParamTypes::const_iterator I = Ty->getParamTypes().begin();
1439       FunctionType::ParamTypes::const_iterator E = Ty->getParamTypes().end();
1440       vector<Value*>::iterator ArgI = $5->begin(), ArgE = $5->end();
1441
1442       for (; ArgI != ArgE && I != E; ++ArgI, ++I)
1443         if ((*ArgI)->getType() != *I)
1444           ThrowException("Parameter " +(*ArgI)->getName()+ " is not of type '" +
1445                          (*I)->getDescription() + "'!");
1446
1447       if (I != E || (ArgI != ArgE && !Ty->isVarArg()))
1448         ThrowException("Invalid number of parameters detected!");
1449
1450       $$ = new InvokeInst(V, Normal, Except, *$5);
1451     }
1452     delete $5;
1453   };
1454
1455
1456
1457 JumpTable : JumpTable IntType ConstValueRef ',' LABEL ValueRef {
1458     $$ = $1;
1459     Constant *V = cast<Constant>(getValNonImprovising($2, $3));
1460     if (V == 0)
1461       ThrowException("May only switch on a constant pool value!");
1462
1463     $$->push_back(make_pair(V, cast<BasicBlock>(getVal($5, $6))));
1464   }
1465   | IntType ConstValueRef ',' LABEL ValueRef {
1466     $$ = new vector<pair<Constant*, BasicBlock*> >();
1467     Constant *V = cast<Constant>(getValNonImprovising($1, $2));
1468
1469     if (V == 0)
1470       ThrowException("May only switch on a constant pool value!");
1471
1472     $$->push_back(make_pair(V, cast<BasicBlock>(getVal($4, $5))));
1473   };
1474
1475 Inst : OptAssign InstVal {
1476   // Is this definition named?? if so, assign the name...
1477   if (setValueName($2, $1)) { assert(0 && "No redefin allowed!"); }
1478   InsertValue($2);
1479   $$ = $2;
1480 };
1481
1482 PHIList : Types '[' ValueRef ',' ValueRef ']' {    // Used for PHI nodes
1483     $$ = new list<pair<Value*, BasicBlock*> >();
1484     $$->push_back(make_pair(getVal(*$1, $3),
1485                             cast<BasicBlock>(getVal(Type::LabelTy, $5))));
1486     delete $1;
1487   }
1488   | PHIList ',' '[' ValueRef ',' ValueRef ']' {
1489     $$ = $1;
1490     $1->push_back(make_pair(getVal($1->front().first->getType(), $4),
1491                             cast<BasicBlock>(getVal(Type::LabelTy, $6))));
1492   };
1493
1494
1495 ValueRefList : ResolvedVal {    // Used for call statements, and memory insts...
1496     $$ = new vector<Value*>();
1497     $$->push_back($1);
1498   }
1499   | ValueRefList ',' ResolvedVal {
1500     $$ = $1;
1501     $1->push_back($3);
1502   };
1503
1504 // ValueRefListE - Just like ValueRefList, except that it may also be empty!
1505 ValueRefListE : ValueRefList | /*empty*/ { $$ = 0; };
1506
1507 InstVal : BinaryOps Types ValueRef ',' ValueRef {
1508     $$ = BinaryOperator::create($1, getVal(*$2, $3), getVal(*$2, $5));
1509     if ($$ == 0)
1510       ThrowException("binary operator returned null!");
1511     delete $2;
1512   }
1513   | UnaryOps ResolvedVal {
1514     $$ = UnaryOperator::create($1, $2);
1515     if ($$ == 0)
1516       ThrowException("unary operator returned null!");
1517   }
1518   | ShiftOps ResolvedVal ',' ResolvedVal {
1519     if ($4->getType() != Type::UByteTy)
1520       ThrowException("Shift amount must be ubyte!");
1521     $$ = new ShiftInst($1, $2, $4);
1522   }
1523   | CAST ResolvedVal TO Types {
1524     $$ = new CastInst($2, *$4);
1525     delete $4;
1526   }
1527   | PHI PHIList {
1528     const Type *Ty = $2->front().first->getType();
1529     $$ = new PHINode(Ty);
1530     while ($2->begin() != $2->end()) {
1531       if ($2->front().first->getType() != Ty)
1532         ThrowException("All elements of a PHI node must be of the same type!");
1533       cast<PHINode>($$)->addIncoming($2->front().first, $2->front().second);
1534       $2->pop_front();
1535     }
1536     delete $2;  // Free the list...
1537   }
1538   | CALL TypesV ValueRef '(' ValueRefListE ')' {
1539     const PointerType *PMTy;
1540     const FunctionType *Ty;
1541
1542     if (!(PMTy = dyn_cast<PointerType>($2->get())) ||
1543         !(Ty = dyn_cast<FunctionType>(PMTy->getElementType()))) {
1544       // Pull out the types of all of the arguments...
1545       vector<const Type*> ParamTypes;
1546       if ($5) {
1547         for (vector<Value*>::iterator I = $5->begin(), E = $5->end(); I!=E; ++I)
1548           ParamTypes.push_back((*I)->getType());
1549       }
1550
1551       bool isVarArg = ParamTypes.size() && ParamTypes.back() == Type::VoidTy;
1552       if (isVarArg) ParamTypes.pop_back();
1553
1554       Ty = FunctionType::get($2->get(), ParamTypes, isVarArg);
1555       PMTy = PointerType::get(Ty);
1556     }
1557     delete $2;
1558
1559     Value *V = getVal(PMTy, $3);   // Get the function we're calling...
1560
1561     // Create the call node...
1562     if (!$5) {                                   // Has no arguments?
1563       // Make sure no arguments is a good thing!
1564       if (Ty->getNumParams() != 0)
1565         ThrowException("No arguments passed to a function that "
1566                        "expects arguments!");
1567
1568       $$ = new CallInst(V, vector<Value*>());
1569     } else {                                     // Has arguments?
1570       // Loop through FunctionType's arguments and ensure they are specified
1571       // correctly!
1572       //
1573       FunctionType::ParamTypes::const_iterator I = Ty->getParamTypes().begin();
1574       FunctionType::ParamTypes::const_iterator E = Ty->getParamTypes().end();
1575       vector<Value*>::iterator ArgI = $5->begin(), ArgE = $5->end();
1576
1577       for (; ArgI != ArgE && I != E; ++ArgI, ++I)
1578         if ((*ArgI)->getType() != *I)
1579           ThrowException("Parameter " +(*ArgI)->getName()+ " is not of type '" +
1580                          (*I)->getDescription() + "'!");
1581
1582       if (I != E || (ArgI != ArgE && !Ty->isVarArg()))
1583         ThrowException("Invalid number of parameters detected!");
1584
1585       $$ = new CallInst(V, *$5);
1586     }
1587     delete $5;
1588   }
1589   | MemoryInst {
1590     $$ = $1;
1591   };
1592
1593
1594 // IndexList - List of indices for GEP based instructions...
1595 IndexList : ',' ValueRefList {
1596   $$ = $2;
1597 } | /* empty */ {
1598   $$ = new vector<Value*>();
1599 };
1600
1601 MemoryInst : MALLOC Types {
1602     $$ = new MallocInst(PointerType::get(*$2));
1603     delete $2;
1604   }
1605   | MALLOC Types ',' UINT ValueRef {
1606     const Type *Ty = PointerType::get(*$2);
1607     $$ = new MallocInst(Ty, getVal($4, $5));
1608     delete $2;
1609   }
1610   | ALLOCA Types {
1611     $$ = new AllocaInst(PointerType::get(*$2));
1612     delete $2;
1613   }
1614   | ALLOCA Types ',' UINT ValueRef {
1615     const Type *Ty = PointerType::get(*$2);
1616     Value *ArrSize = getVal($4, $5);
1617     $$ = new AllocaInst(Ty, ArrSize);
1618     delete $2;
1619   }
1620   | FREE ResolvedVal {
1621     if (!isa<PointerType>($2->getType()))
1622       ThrowException("Trying to free nonpointer type " +
1623                      $2->getType()->getDescription() + "!");
1624     $$ = new FreeInst($2);
1625   }
1626
1627   | LOAD Types ValueRef IndexList {
1628     if (!isa<PointerType>($2->get()))
1629       ThrowException("Can't load from nonpointer type: " +
1630                      (*$2)->getDescription());
1631     if (LoadInst::getIndexedType(*$2, *$4) == 0)
1632       ThrowException("Invalid indices for load instruction!");
1633
1634     $$ = new LoadInst(getVal(*$2, $3), *$4);
1635     delete $4;   // Free the vector...
1636     delete $2;
1637   }
1638   | STORE ResolvedVal ',' Types ValueRef IndexList {
1639     if (!isa<PointerType>($4->get()))
1640       ThrowException("Can't store to a nonpointer type: " +
1641                      (*$4)->getDescription());
1642     const Type *ElTy = StoreInst::getIndexedType(*$4, *$6);
1643     if (ElTy == 0)
1644       ThrowException("Can't store into that field list!");
1645     if (ElTy != $2->getType())
1646       ThrowException("Can't store '" + $2->getType()->getDescription() +
1647                      "' into space of type '" + ElTy->getDescription() + "'!");
1648     $$ = new StoreInst($2, getVal(*$4, $5), *$6);
1649     delete $4; delete $6;
1650   }
1651   | GETELEMENTPTR Types ValueRef IndexList {
1652     if (!isa<PointerType>($2->get()))
1653       ThrowException("getelementptr insn requires pointer operand!");
1654     if (!GetElementPtrInst::getIndexedType(*$2, *$4, true))
1655       ThrowException("Can't get element ptr '" + (*$2)->getDescription()+ "'!");
1656     $$ = new GetElementPtrInst(getVal(*$2, $3), *$4);
1657     delete $2; delete $4;
1658   };
1659
1660 %%
1661 int yyerror(const char *ErrorMsg) {
1662   string where  = string((CurFilename == "-")? string("<stdin>") : CurFilename)
1663                   + ":" + utostr((unsigned) llvmAsmlineno) + ": ";
1664   string errMsg = string(ErrorMsg) + string("\n") + where + " while reading ";
1665   if (yychar == YYEMPTY)
1666     errMsg += "end-of-file.";
1667   else
1668     errMsg += "token: '" + string(llvmAsmtext, llvmAsmleng) + "'";
1669   ThrowException(errMsg);
1670   return 0;
1671 }