lib/AsmParser/LLParser.cpp

   1 //===-- LLParser.cpp - Parser Class ---------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines the parser class for .ll files.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "LLParser.h"
  15 #include "llvm/AutoUpgrade.h"
  16 #include "llvm/CallingConv.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/InlineAsm.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Module.h"
  22 #include "llvm/ValueSymbolTable.h"
  23 #include "llvm/ADT/SmallPtrSet.h"
  24 #include "llvm/ADT/StringExtras.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 using namespace llvm;
  27
  28 namespace llvm {
  29   /// ValID - Represents a reference of a definition of some sort with no type.
  30   /// There are several cases where we have to parse the value but where the
  31   /// type can depend on later context.  This may either be a numeric reference
  32   /// or a symbolic (%var) reference.  This is just a discriminated union.
  33   struct ValID {
  34     enum {
  35       t_LocalID, t_GlobalID,      // ID in UIntVal.
  36       t_LocalName, t_GlobalName,  // Name in StrVal.
  37       t_APSInt, t_APFloat,        // Value in APSIntVal/APFloatVal.
  38       t_Null, t_Undef, t_Zero,    // No value.
  39       t_EmptyArray,               // No value:  []
  40       t_Constant,                 // Value in ConstantVal.
  41       t_InlineAsm                 // Value in StrVal/StrVal2/UIntVal.
  42     } Kind;
  43
  44     LLParser::LocTy Loc;
  45     unsigned UIntVal;
  46     std::string StrVal, StrVal2;
  47     APSInt APSIntVal;
  48     APFloat APFloatVal;
  49     Constant *ConstantVal;
  50     ValID() : APFloatVal(0.0) {}
  51   };
  52 }
  53
  54 /// Run: module ::= toplevelentity*
  55 bool LLParser::Run() {
  56   // Prime the lexer.
  57   Lex.Lex();
  58
  59   return ParseTopLevelEntities() ||
  60          ValidateEndOfModule();
  61 }
  62
  63 /// ValidateEndOfModule - Do final validity and sanity checks at the end of the
  64 /// module.
  65 bool LLParser::ValidateEndOfModule() {
  66   if (!ForwardRefTypes.empty())
  67     return Error(ForwardRefTypes.begin()->second.second,
  68                  "use of undefined type named '" +
  69                  ForwardRefTypes.begin()->first + "'");
  70   if (!ForwardRefTypeIDs.empty())
  71     return Error(ForwardRefTypeIDs.begin()->second.second,
  72                  "use of undefined type '%" +
  73                  utostr(ForwardRefTypeIDs.begin()->first) + "'");
  74
  75   if (!ForwardRefVals.empty())
  76     return Error(ForwardRefVals.begin()->second.second,
  77                  "use of undefined value '@" + ForwardRefVals.begin()->first +
  78                  "'");
  79
  80   if (!ForwardRefValIDs.empty())
  81     return Error(ForwardRefValIDs.begin()->second.second,
  82                  "use of undefined value '@" +
  83                  utostr(ForwardRefValIDs.begin()->first) + "'");
  84
  85   // Look for intrinsic functions and CallInst that need to be upgraded
  86   for (Module::iterator FI = M->begin(), FE = M->end(); FI != FE; )
  87     UpgradeCallsToIntrinsic(FI++); // must be post-increment, as we remove
  88
  89   return false;
  90 }
  91
  92 //===----------------------------------------------------------------------===//
  93 // Top-Level Entities
  94 //===----------------------------------------------------------------------===//
  95
  96 bool LLParser::ParseTopLevelEntities() {
  97   while (1) {
  98     switch (Lex.getKind()) {
  99     default:         return TokError("expected top-level entity");
 100     case lltok::Eof: return false;
 101     //case lltok::kw_define:
 102     case lltok::kw_declare: if (ParseDeclare()) return true; break;
 103     case lltok::kw_define:  if (ParseDefine()) return true; break;
 104     case lltok::kw_module:  if (ParseModuleAsm()) return true; break;
 105     case lltok::kw_target:  if (ParseTargetDefinition()) return true; break;
 106     case lltok::kw_deplibs: if (ParseDepLibs()) return true; break;
 107     case lltok::kw_type:    if (ParseUnnamedType()) return true; break;
 108     case lltok::StringConstant: // FIXME: REMOVE IN LLVM 3.0
 109     case lltok::LocalVar:   if (ParseNamedType()) return true; break;
 110     case lltok::GlobalVar:  if (ParseNamedGlobal()) return true; break;
 111
 112     // The Global variable production with no name can have many different
 113     // optional leading prefixes, the production is:
 114     // GlobalVar ::= OptionalLinkage OptionalVisibility OptionalThreadLocal
 115     //               OptionalAddrSpace ('constant'|'global') ...
 116     case lltok::kw_private:       // OptionalLinkage
 117     case lltok::kw_internal:      // OptionalLinkage
 118     case lltok::kw_weak:          // OptionalLinkage
 119     case lltok::kw_weak_odr:      // OptionalLinkage
 120     case lltok::kw_linkonce:      // OptionalLinkage
 121     case lltok::kw_linkonce_odr:  // OptionalLinkage
 122     case lltok::kw_appending:     // OptionalLinkage
 123     case lltok::kw_dllexport:     // OptionalLinkage
 124     case lltok::kw_common:        // OptionalLinkage
 125     case lltok::kw_dllimport:     // OptionalLinkage
 126     case lltok::kw_extern_weak:   // OptionalLinkage
 127     case lltok::kw_external: {    // OptionalLinkage
 128       unsigned Linkage, Visibility;
 129       if (ParseOptionalLinkage(Linkage) ||
 130           ParseOptionalVisibility(Visibility) ||
 131           ParseGlobal("", 0, Linkage, true, Visibility))
 132         return true;
 133       break;
 134     }
 135     case lltok::kw_default:       // OptionalVisibility
 136     case lltok::kw_hidden:        // OptionalVisibility
 137     case lltok::kw_protected: {   // OptionalVisibility
 138       unsigned Visibility;
 139       if (ParseOptionalVisibility(Visibility) ||
 140           ParseGlobal("", 0, 0, false, Visibility))
 141         return true;
 142       break;
 143     }
 144
 145     case lltok::kw_thread_local:  // OptionalThreadLocal
 146     case lltok::kw_addrspace:     // OptionalAddrSpace
 147     case lltok::kw_constant:      // GlobalType
 148     case lltok::kw_global:        // GlobalType
 149       if (ParseGlobal("", 0, 0, false, 0)) return true;
 150       break;
 151     }
 152   }
 153 }
 154
 155
 156 /// toplevelentity
 157 ///   ::= 'module' 'asm' STRINGCONSTANT
 158 bool LLParser::ParseModuleAsm() {
 159   assert(Lex.getKind() == lltok::kw_module);
 160   Lex.Lex();
 161
 162   std::string AsmStr;
 163   if (ParseToken(lltok::kw_asm, "expected 'module asm'") ||
 164       ParseStringConstant(AsmStr)) return true;
 165
 166   const std::string &AsmSoFar = M->getModuleInlineAsm();
 167   if (AsmSoFar.empty())
 168     M->setModuleInlineAsm(AsmStr);
 169   else
 170     M->setModuleInlineAsm(AsmSoFar+"\n"+AsmStr);
 171   return false;
 172 }
 173
 174 /// toplevelentity
 175 ///   ::= 'target' 'triple' '=' STRINGCONSTANT
 176 ///   ::= 'target' 'datalayout' '=' STRINGCONSTANT
 177 bool LLParser::ParseTargetDefinition() {
 178   assert(Lex.getKind() == lltok::kw_target);
 179   std::string Str;
 180   switch (Lex.Lex()) {
 181   default: return TokError("unknown target property");
 182   case lltok::kw_triple:
 183     Lex.Lex();
 184     if (ParseToken(lltok::equal, "expected '=' after target triple") ||
 185         ParseStringConstant(Str))
 186       return true;
 187     M->setTargetTriple(Str);
 188     return false;
 189   case lltok::kw_datalayout:
 190     Lex.Lex();
 191     if (ParseToken(lltok::equal, "expected '=' after target datalayout") ||
 192         ParseStringConstant(Str))
 193       return true;
 194     M->setDataLayout(Str);
 195     return false;
 196   }
 197 }
 198
 199 /// toplevelentity
 200 ///   ::= 'deplibs' '=' '[' ']'
 201 ///   ::= 'deplibs' '=' '[' STRINGCONSTANT (',' STRINGCONSTANT)* ']'
 202 bool LLParser::ParseDepLibs() {
 203   assert(Lex.getKind() == lltok::kw_deplibs);
 204   Lex.Lex();
 205   if (ParseToken(lltok::equal, "expected '=' after deplibs") ||
 206       ParseToken(lltok::lsquare, "expected '=' after deplibs"))
 207     return true;
 208
 209   if (EatIfPresent(lltok::rsquare))
 210     return false;
 211
 212   std::string Str;
 213   if (ParseStringConstant(Str)) return true;
 214   M->addLibrary(Str);
 215
 216   while (EatIfPresent(lltok::comma)) {
 217     if (ParseStringConstant(Str)) return true;
 218     M->addLibrary(Str);
 219   }
 220
 221   return ParseToken(lltok::rsquare, "expected ']' at end of list");
 222 }
 223
 224 /// toplevelentity
 225 ///   ::= 'type' type
 226 bool LLParser::ParseUnnamedType() {
 227   assert(Lex.getKind() == lltok::kw_type);
 228   LocTy TypeLoc = Lex.getLoc();
 229   Lex.Lex(); // eat kw_type
 230
 231   PATypeHolder Ty(Type::VoidTy);
 232   if (ParseType(Ty)) return true;
 233
 234   unsigned TypeID = NumberedTypes.size();
 235
 236   // See if this type was previously referenced.
 237   std::map<unsigned, std::pair<PATypeHolder, LocTy> >::iterator
 238     FI = ForwardRefTypeIDs.find(TypeID);
 239   if (FI != ForwardRefTypeIDs.end()) {
 240     if (FI->second.first.get() == Ty)
 241       return Error(TypeLoc, "self referential type is invalid");
 242
 243     cast<DerivedType>(FI->second.first.get())->refineAbstractTypeTo(Ty);
 244     Ty = FI->second.first.get();
 245     ForwardRefTypeIDs.erase(FI);
 246   }
 247
 248   NumberedTypes.push_back(Ty);
 249
 250   return false;
 251 }
 252
 253 /// toplevelentity
 254 ///   ::= LocalVar '=' 'type' type
 255 bool LLParser::ParseNamedType() {
 256   std::string Name = Lex.getStrVal();
 257   LocTy NameLoc = Lex.getLoc();
 258   Lex.Lex();  // eat LocalVar.
 259
 260   PATypeHolder Ty(Type::VoidTy);
 261
 262   if (ParseToken(lltok::equal, "expected '=' after name") ||
 263       ParseToken(lltok::kw_type, "expected 'type' after name") ||
 264       ParseType(Ty))
 265     return true;
 266
 267   // Set the type name, checking for conflicts as we do so.
 268   bool AlreadyExists = M->addTypeName(Name, Ty);
 269   if (!AlreadyExists) return false;
 270
 271   // See if this type is a forward reference.  We need to eagerly resolve
 272   // types to allow recursive type redefinitions below.
 273   std::map<std::string, std::pair<PATypeHolder, LocTy> >::iterator
 274   FI = ForwardRefTypes.find(Name);
 275   if (FI != ForwardRefTypes.end()) {
 276     if (FI->second.first.get() == Ty)
 277       return Error(NameLoc, "self referential type is invalid");
 278
 279     cast<DerivedType>(FI->second.first.get())->refineAbstractTypeTo(Ty);
 280     Ty = FI->second.first.get();
 281     ForwardRefTypes.erase(FI);
 282   }
 283
 284   // Inserting a name that is already defined, get the existing name.
 285   const Type *Existing = M->getTypeByName(Name);
 286   assert(Existing && "Conflict but no matching type?!");
 287
 288   // Otherwise, this is an attempt to redefine a type. That's okay if
 289   // the redefinition is identical to the original.
 290   // FIXME: REMOVE REDEFINITIONS IN LLVM 3.0
 291   if (Existing == Ty) return false;
 292
 293   // Any other kind of (non-equivalent) redefinition is an error.
 294   return Error(NameLoc, "redefinition of type named '" + Name + "' of type '" +
 295                Ty->getDescription() + "'");
 296 }
 297
 298
 299 /// toplevelentity
 300 ///   ::= 'declare' FunctionHeader
 301 bool LLParser::ParseDeclare() {
 302   assert(Lex.getKind() == lltok::kw_declare);
 303   Lex.Lex();
 304
 305   Function *F;
 306   return ParseFunctionHeader(F, false);
 307 }
 308
 309 /// toplevelentity
 310 ///   ::= 'define' FunctionHeader '{' ...
 311 bool LLParser::ParseDefine() {
 312   assert(Lex.getKind() == lltok::kw_define);
 313   Lex.Lex();
 314
 315   Function *F;
 316   return ParseFunctionHeader(F, true) ||
 317          ParseFunctionBody(*F);
 318 }
 319
 320 /// ParseGlobalType
 321 ///   ::= 'constant'
 322 ///   ::= 'global'
 323 bool LLParser::ParseGlobalType(bool &IsConstant) {
 324   if (Lex.getKind() == lltok::kw_constant)
 325     IsConstant = true;
 326   else if (Lex.getKind() == lltok::kw_global)
 327     IsConstant = false;
 328   else {
 329     IsConstant = false;
 330     return TokError("expected 'global' or 'constant'");
 331   }
 332   Lex.Lex();
 333   return false;
 334 }
 335
 336 /// ParseNamedGlobal:
 337 ///   GlobalVar '=' OptionalVisibility ALIAS ...
 338 ///   GlobalVar '=' OptionalLinkage OptionalVisibility ...   -> global variable
 339 bool LLParser::ParseNamedGlobal() {
 340   assert(Lex.getKind() == lltok::GlobalVar);
 341   LocTy NameLoc = Lex.getLoc();
 342   std::string Name = Lex.getStrVal();
 343   Lex.Lex();
 344
 345   bool HasLinkage;
 346   unsigned Linkage, Visibility;
 347   if (ParseToken(lltok::equal, "expected '=' in global variable") ||
 348       ParseOptionalLinkage(Linkage, HasLinkage) ||
 349       ParseOptionalVisibility(Visibility))
 350     return true;
 351
 352   if (HasLinkage || Lex.getKind() != lltok::kw_alias)
 353     return ParseGlobal(Name, NameLoc, Linkage, HasLinkage, Visibility);
 354   return ParseAlias(Name, NameLoc, Visibility);
 355 }
 356
 357 /// ParseAlias:
 358 ///   ::= GlobalVar '=' OptionalVisibility 'alias' OptionalLinkage Aliasee
 359 /// Aliasee
 360 ///   ::= TypeAndValue | 'bitcast' '(' TypeAndValue 'to' Type ')'
 361 ///
 362 /// Everything through visibility has already been parsed.
 363 ///
 364 bool LLParser::ParseAlias(const std::string &Name, LocTy NameLoc,
 365                           unsigned Visibility) {
 366   assert(Lex.getKind() == lltok::kw_alias);
 367   Lex.Lex();
 368   unsigned Linkage;
 369   LocTy LinkageLoc = Lex.getLoc();
 370   if (ParseOptionalLinkage(Linkage))
 371     return true;
 372
 373   if (Linkage != GlobalValue::ExternalLinkage &&
 374       Linkage != GlobalValue::WeakAnyLinkage &&
 375       Linkage != GlobalValue::WeakODRLinkage &&
 376       Linkage != GlobalValue::InternalLinkage &&
 377       Linkage != GlobalValue::PrivateLinkage)
 378     return Error(LinkageLoc, "invalid linkage type for alias");
 379
 380   Constant *Aliasee;
 381   LocTy AliaseeLoc = Lex.getLoc();
 382   if (Lex.getKind() != lltok::kw_bitcast) {
 383     if (ParseGlobalTypeAndValue(Aliasee)) return true;
 384   } else {
 385     // The bitcast dest type is not present, it is implied by the dest type.
 386     ValID ID;
 387     if (ParseValID(ID)) return true;
 388     if (ID.Kind != ValID::t_Constant)
 389       return Error(AliaseeLoc, "invalid aliasee");
 390     Aliasee = ID.ConstantVal;
 391   }
 392
 393   if (!isa<PointerType>(Aliasee->getType()))
 394     return Error(AliaseeLoc, "alias must have pointer type");
 395
 396   // Okay, create the alias but do not insert it into the module yet.
 397   GlobalAlias* GA = new GlobalAlias(Aliasee->getType(),
 398                                     (GlobalValue::LinkageTypes)Linkage, Name,
 399                                     Aliasee);
 400   GA->setVisibility((GlobalValue::VisibilityTypes)Visibility);
 401
 402   // See if this value already exists in the symbol table.  If so, it is either
 403   // a redefinition or a definition of a forward reference.
 404   if (GlobalValue *Val =
 405         cast_or_null<GlobalValue>(M->getValueSymbolTable().lookup(Name))) {
 406     // See if this was a redefinition.  If so, there is no entry in
 407     // ForwardRefVals.
 408     std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator
 409       I = ForwardRefVals.find(Name);
 410     if (I == ForwardRefVals.end())
 411       return Error(NameLoc, "redefinition of global named '@" + Name + "'");
 412
 413     // Otherwise, this was a definition of forward ref.  Verify that types
 414     // agree.
 415     if (Val->getType() != GA->getType())
 416       return Error(NameLoc,
 417               "forward reference and definition of alias have different types");
 418
 419     // If they agree, just RAUW the old value with the alias and remove the
 420     // forward ref info.
 421     Val->replaceAllUsesWith(GA);
 422     Val->eraseFromParent();
 423     ForwardRefVals.erase(I);
 424   }
 425
 426   // Insert into the module, we know its name won't collide now.
 427   M->getAliasList().push_back(GA);
 428   assert(GA->getNameStr() == Name && "Should not be a name conflict!");
 429
 430   return false;
 431 }
 432
 433 /// ParseGlobal
 434 ///   ::= GlobalVar '=' OptionalLinkage OptionalVisibility OptionalThreadLocal
 435 ///       OptionalAddrSpace GlobalType Type Const
 436 ///   ::= OptionalLinkage OptionalVisibility OptionalThreadLocal
 437 ///       OptionalAddrSpace GlobalType Type Const
 438 ///
 439 /// Everything through visibility has been parsed already.
 440 ///
 441 bool LLParser::ParseGlobal(const std::string &Name, LocTy NameLoc,
 442                            unsigned Linkage, bool HasLinkage,
 443                            unsigned Visibility) {
 444   unsigned AddrSpace;
 445   bool ThreadLocal, IsConstant;
 446   LocTy TyLoc;
 447
 448   PATypeHolder Ty(Type::VoidTy);
 449   if (ParseOptionalToken(lltok::kw_thread_local, ThreadLocal) ||
 450       ParseOptionalAddrSpace(AddrSpace) ||
 451       ParseGlobalType(IsConstant) ||
 452       ParseType(Ty, TyLoc))
 453     return true;
 454
 455   // If the linkage is specified and is external, then no initializer is
 456   // present.
 457   Constant *Init = 0;
 458   if (!HasLinkage || (Linkage != GlobalValue::DLLImportLinkage &&
 459                       Linkage != GlobalValue::ExternalWeakLinkage &&
 460                       Linkage != GlobalValue::ExternalLinkage)) {
 461     if (ParseGlobalValue(Ty, Init))
 462       return true;
 463   }
 464
 465   if (isa<FunctionType>(Ty) || Ty == Type::LabelTy)
 466     return Error(TyLoc, "invalid type for global variable");
 467
 468   GlobalVariable *GV = 0;
 469
 470   // See if the global was forward referenced, if so, use the global.
 471   if (!Name.empty()) {
 472     if ((GV = M->getGlobalVariable(Name, true)) &&
 473         !ForwardRefVals.erase(Name))
 474       return Error(NameLoc, "redefinition of global '@" + Name + "'");
 475   } else {
 476     std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator
 477       I = ForwardRefValIDs.find(NumberedVals.size());
 478     if (I != ForwardRefValIDs.end()) {
 479       GV = cast<GlobalVariable>(I->second.first);
 480       ForwardRefValIDs.erase(I);
 481     }
 482   }
 483
 484   if (GV == 0) {
 485     GV = new GlobalVariable(Ty, false, GlobalValue::ExternalLinkage, 0, Name,
 486                             M, false, AddrSpace);
 487   } else {
 488     if (GV->getType()->getElementType() != Ty)
 489       return Error(TyLoc,
 490             "forward reference and definition of global have different types");
 491
 492     // Move the forward-reference to the correct spot in the module.
 493     M->getGlobalList().splice(M->global_end(), M->getGlobalList(), GV);
 494   }
 495
 496   if (Name.empty())
 497     NumberedVals.push_back(GV);
 498
 499   // Set the parsed properties on the global.
 500   if (Init)
 501     GV->setInitializer(Init);
 502   GV->setConstant(IsConstant);
 503   GV->setLinkage((GlobalValue::LinkageTypes)Linkage);
 504   GV->setVisibility((GlobalValue::VisibilityTypes)Visibility);
 505   GV->setThreadLocal(ThreadLocal);
 506
 507   // Parse attributes on the global.
 508   while (Lex.getKind() == lltok::comma) {
 509     Lex.Lex();
 510
 511     if (Lex.getKind() == lltok::kw_section) {
 512       Lex.Lex();
 513       GV->setSection(Lex.getStrVal());
 514       if (ParseToken(lltok::StringConstant, "expected global section string"))
 515         return true;
 516     } else if (Lex.getKind() == lltok::kw_align) {
 517       unsigned Alignment;
 518       if (ParseOptionalAlignment(Alignment)) return true;
 519       GV->setAlignment(Alignment);
 520     } else {
 521       TokError("unknown global variable property!");
 522     }
 523   }
 524
 525   return false;
 526 }
 527
 528
 529 //===----------------------------------------------------------------------===//
 530 // GlobalValue Reference/Resolution Routines.
 531 //===----------------------------------------------------------------------===//
 532
 533 /// GetGlobalVal - Get a value with the specified name or ID, creating a
 534 /// forward reference record if needed.  This can return null if the value
 535 /// exists but does not have the right type.
 536 GlobalValue *LLParser::GetGlobalVal(const std::string &Name, const Type *Ty,
 537                                     LocTy Loc) {
 538   const PointerType *PTy = dyn_cast<PointerType>(Ty);
 539   if (PTy == 0) {
 540     Error(Loc, "global variable reference must have pointer type");
 541     return 0;
 542   }
 543
 544   // Look this name up in the normal function symbol table.
 545   GlobalValue *Val =
 546     cast_or_null<GlobalValue>(M->getValueSymbolTable().lookup(Name));
 547
 548   // If this is a forward reference for the value, see if we already created a
 549   // forward ref record.
 550   if (Val == 0) {
 551     std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator
 552       I = ForwardRefVals.find(Name);
 553     if (I != ForwardRefVals.end())
 554       Val = I->second.first;
 555   }
 556
 557   // If we have the value in the symbol table or fwd-ref table, return it.
 558   if (Val) {
 559     if (Val->getType() == Ty) return Val;
 560     Error(Loc, "'@" + Name + "' defined with type '" +
 561           Val->getType()->getDescription() + "'");
 562     return 0;
 563   }
 564
 565   // Otherwise, create a new forward reference for this value and remember it.
 566   GlobalValue *FwdVal;
 567   if (const FunctionType *FT = dyn_cast<FunctionType>(PTy->getElementType())) {
 568     // Function types can return opaque but functions can't.
 569     if (isa<OpaqueType>(FT->getReturnType())) {
 570       Error(Loc, "function may not return opaque type");
 571       return 0;
 572     }
 573
 574     FwdVal = Function::Create(FT, GlobalValue::ExternalWeakLinkage, Name, M);
 575   } else {
 576     FwdVal = new GlobalVariable(PTy->getElementType(), false,
 577                                 GlobalValue::ExternalWeakLinkage, 0, Name, M);
 578   }
 579
 580   ForwardRefVals[Name] = std::make_pair(FwdVal, Loc);
 581   return FwdVal;
 582 }
 583
 584 GlobalValue *LLParser::GetGlobalVal(unsigned ID, const Type *Ty, LocTy Loc) {
 585   const PointerType *PTy = dyn_cast<PointerType>(Ty);
 586   if (PTy == 0) {
 587     Error(Loc, "global variable reference must have pointer type");
 588     return 0;
 589   }
 590
 591   GlobalValue *Val = ID < NumberedVals.size() ? NumberedVals[ID] : 0;
 592
 593   // If this is a forward reference for the value, see if we already created a
 594   // forward ref record.
 595   if (Val == 0) {
 596     std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator
 597       I = ForwardRefValIDs.find(ID);
 598     if (I != ForwardRefValIDs.end())
 599       Val = I->second.first;
 600   }
 601
 602   // If we have the value in the symbol table or fwd-ref table, return it.
 603   if (Val) {
 604     if (Val->getType() == Ty) return Val;
 605     Error(Loc, "'@" + utostr(ID) + "' defined with type '" +
 606           Val->getType()->getDescription() + "'");
 607     return 0;
 608   }
 609
 610   // Otherwise, create a new forward reference for this value and remember it.
 611   GlobalValue *FwdVal;
 612   if (const FunctionType *FT = dyn_cast<FunctionType>(PTy->getElementType())) {
 613     // Function types can return opaque but functions can't.
 614     if (isa<OpaqueType>(FT->getReturnType())) {
 615       Error(Loc, "function may not return opaque type");
 616       return 0;
 617     }
 618     FwdVal = Function::Create(FT, GlobalValue::ExternalWeakLinkage, "", M);
 619   } else {
 620     FwdVal = new GlobalVariable(PTy->getElementType(), false,
 621                                 GlobalValue::ExternalWeakLinkage, 0, "", M);
 622   }
 623
 624   ForwardRefValIDs[ID] = std::make_pair(FwdVal, Loc);
 625   return FwdVal;
 626 }
 627
 628
 629 //===----------------------------------------------------------------------===//
 630 // Helper Routines.
 631 //===----------------------------------------------------------------------===//
 632
 633 /// ParseToken - If the current token has the specified kind, eat it and return
 634 /// success.  Otherwise, emit the specified error and return failure.
 635 bool LLParser::ParseToken(lltok::Kind T, const char *ErrMsg) {
 636   if (Lex.getKind() != T)
 637     return TokError(ErrMsg);
 638   Lex.Lex();
 639   return false;
 640 }
 641
 642 /// ParseStringConstant
 643 ///   ::= StringConstant
 644 bool LLParser::ParseStringConstant(std::string &Result) {
 645   if (Lex.getKind() != lltok::StringConstant)
 646     return TokError("expected string constant");
 647   Result = Lex.getStrVal();
 648   Lex.Lex();
 649   return false;
 650 }
 651
 652 /// ParseUInt32
 653 ///   ::= uint32
 654 bool LLParser::ParseUInt32(unsigned &Val) {
 655   if (Lex.getKind() != lltok::APSInt || Lex.getAPSIntVal().isSigned())
 656     return TokError("expected integer");
 657   uint64_t Val64 = Lex.getAPSIntVal().getLimitedValue(0xFFFFFFFFULL+1);
 658   if (Val64 != unsigned(Val64))
 659     return TokError("expected 32-bit integer (too large)");
 660   Val = Val64;
 661   Lex.Lex();
 662   return false;
 663 }
 664
 665
 666 /// ParseOptionalAddrSpace
 667 ///   := /*empty*/
 668 ///   := 'addrspace' '(' uint32 ')'
 669 bool LLParser::ParseOptionalAddrSpace(unsigned &AddrSpace) {
 670   AddrSpace = 0;
 671   if (!EatIfPresent(lltok::kw_addrspace))
 672     return false;
 673   return ParseToken(lltok::lparen, "expected '(' in address space") ||
 674          ParseUInt32(AddrSpace) ||
 675          ParseToken(lltok::rparen, "expected ')' in address space");
 676 }
 677
 678 /// ParseOptionalAttrs - Parse a potentially empty attribute list.  AttrKind
 679 /// indicates what kind of attribute list this is: 0: function arg, 1: result,
 680 /// 2: function attr.
 681 /// 3: function arg after value: FIXME: REMOVE IN LLVM 3.0
 682 bool LLParser::ParseOptionalAttrs(unsigned &Attrs, unsigned AttrKind) {
 683   Attrs = Attribute::None;
 684   LocTy AttrLoc = Lex.getLoc();
 685
 686   while (1) {
 687     switch (Lex.getKind()) {
 688     case lltok::kw_sext:
 689     case lltok::kw_zext:
 690       // Treat these as signext/zeroext if they occur in the argument list after
 691       // the value, as in "call i8 @foo(i8 10 sext)".  If they occur before the
 692       // value, as in "call i8 @foo(i8 sext (" then it is part of a constant
 693       // expr.
 694       // FIXME: REMOVE THIS IN LLVM 3.0
 695       if (AttrKind == 3) {
 696         if (Lex.getKind() == lltok::kw_sext)
 697           Attrs |= Attribute::SExt;
 698         else
 699           Attrs |= Attribute::ZExt;
 700         break;
 701       }
 702       // FALL THROUGH.
 703     default:  // End of attributes.
 704       if (AttrKind != 2 && (Attrs & Attribute::FunctionOnly))
 705         return Error(AttrLoc, "invalid use of function-only attribute");
 706
 707       if (AttrKind != 0 && AttrKind != 3 && (Attrs & Attribute::ParameterOnly))
 708         return Error(AttrLoc, "invalid use of parameter-only attribute");
 709
 710       return false;
 711     case lltok::kw_zeroext:      Attrs |= Attribute::ZExt; break;
 712     case lltok::kw_signext:      Attrs |= Attribute::SExt; break;
 713     case lltok::kw_inreg:        Attrs |= Attribute::InReg; break;
 714     case lltok::kw_sret:         Attrs |= Attribute::StructRet; break;
 715     case lltok::kw_noalias:      Attrs |= Attribute::NoAlias; break;
 716     case lltok::kw_nocapture:    Attrs |= Attribute::NoCapture; break;
 717     case lltok::kw_byval:        Attrs |= Attribute::ByVal; break;
 718     case lltok::kw_nest:         Attrs |= Attribute::Nest; break;
 719
 720     case lltok::kw_noreturn:     Attrs |= Attribute::NoReturn; break;
 721     case lltok::kw_nounwind:     Attrs |= Attribute::NoUnwind; break;
 722     case lltok::kw_noinline:     Attrs |= Attribute::NoInline; break;
 723     case lltok::kw_readnone:     Attrs |= Attribute::ReadNone; break;
 724     case lltok::kw_readonly:     Attrs |= Attribute::ReadOnly; break;
 725     case lltok::kw_alwaysinline: Attrs |= Attribute::AlwaysInline; break;
 726     case lltok::kw_optsize:      Attrs |= Attribute::OptimizeForSize; break;
 727     case lltok::kw_ssp:          Attrs |= Attribute::StackProtect; break;
 728     case lltok::kw_sspreq:       Attrs |= Attribute::StackProtectReq; break;
 729
 730
 731     case lltok::kw_align: {
 732       unsigned Alignment;
 733       if (ParseOptionalAlignment(Alignment))
 734         return true;
 735       Attrs |= Attribute::constructAlignmentFromInt(Alignment);
 736       continue;
 737     }
 738     }
 739     Lex.Lex();
 740   }
 741 }
 742
 743 /// ParseOptionalLinkage
 744 ///   ::= /*empty*/
 745 ///   ::= 'private'
 746 ///   ::= 'internal'
 747 ///   ::= 'weak'
 748 ///   ::= 'weak_odr'
 749 ///   ::= 'linkonce'
 750 ///   ::= 'linkonce_odr'
 751 ///   ::= 'appending'
 752 ///   ::= 'dllexport'
 753 ///   ::= 'common'
 754 ///   ::= 'dllimport'
 755 ///   ::= 'extern_weak'
 756 ///   ::= 'external'
 757 bool LLParser::ParseOptionalLinkage(unsigned &Res, bool &HasLinkage) {
 758   HasLinkage = false;
 759   switch (Lex.getKind()) {
 760   default:                     Res = GlobalValue::ExternalLinkage; return false;
 761   case lltok::kw_private:      Res = GlobalValue::PrivateLinkage; break;
 762   case lltok::kw_internal:     Res = GlobalValue::InternalLinkage; break;
 763   case lltok::kw_weak:         Res = GlobalValue::WeakAnyLinkage; break;
 764   case lltok::kw_weak_odr:     Res = GlobalValue::WeakODRLinkage; break;
 765   case lltok::kw_linkonce:     Res = GlobalValue::LinkOnceAnyLinkage; break;
 766   case lltok::kw_linkonce_odr: Res = GlobalValue::LinkOnceODRLinkage; break;
 767   case lltok::kw_appending:    Res = GlobalValue::AppendingLinkage; break;
 768   case lltok::kw_dllexport:    Res = GlobalValue::DLLExportLinkage; break;
 769   case lltok::kw_common:       Res = GlobalValue::CommonLinkage; break;
 770   case lltok::kw_dllimport:    Res = GlobalValue::DLLImportLinkage; break;
 771   case lltok::kw_extern_weak:  Res = GlobalValue::ExternalWeakLinkage; break;
 772   case lltok::kw_external:     Res = GlobalValue::ExternalLinkage; break;
 773   }
 774   Lex.Lex();
 775   HasLinkage = true;
 776   return false;
 777 }
 778
 779 /// ParseOptionalVisibility
 780 ///   ::= /*empty*/
 781 ///   ::= 'default'
 782 ///   ::= 'hidden'
 783 ///   ::= 'protected'
 784 ///
 785 bool LLParser::ParseOptionalVisibility(unsigned &Res) {
 786   switch (Lex.getKind()) {
 787   default:                  Res = GlobalValue::DefaultVisibility; return false;
 788   case lltok::kw_default:   Res = GlobalValue::DefaultVisibility; break;
 789   case lltok::kw_hidden:    Res = GlobalValue::HiddenVisibility; break;
 790   case lltok::kw_protected: Res = GlobalValue::ProtectedVisibility; break;
 791   }
 792   Lex.Lex();
 793   return false;
 794 }
 795
 796 /// ParseOptionalCallingConv
 797 ///   ::= /*empty*/
 798 ///   ::= 'ccc'
 799 ///   ::= 'fastcc'
 800 ///   ::= 'coldcc'
 801 ///   ::= 'x86_stdcallcc'
 802 ///   ::= 'x86_fastcallcc'
 803 ///   ::= 'cc' UINT
 804 ///
 805 bool LLParser::ParseOptionalCallingConv(unsigned &CC) {
 806   switch (Lex.getKind()) {
 807   default:                       CC = CallingConv::C; return false;
 808   case lltok::kw_ccc:            CC = CallingConv::C; break;
 809   case lltok::kw_fastcc:         CC = CallingConv::Fast; break;
 810   case lltok::kw_coldcc:         CC = CallingConv::Cold; break;
 811   case lltok::kw_x86_stdcallcc:  CC = CallingConv::X86_StdCall; break;
 812   case lltok::kw_x86_fastcallcc: CC = CallingConv::X86_FastCall; break;
 813   case lltok::kw_cc:             Lex.Lex(); return ParseUInt32(CC);
 814   }
 815   Lex.Lex();
 816   return false;
 817 }
 818
 819 /// ParseOptionalAlignment
 820 ///   ::= /* empty */
 821 ///   ::= 'align' 4
 822 bool LLParser::ParseOptionalAlignment(unsigned &Alignment) {
 823   Alignment = 0;
 824   if (!EatIfPresent(lltok::kw_align))
 825     return false;
 826   LocTy AlignLoc = Lex.getLoc();
 827   if (ParseUInt32(Alignment)) return true;
 828   if (!isPowerOf2_32(Alignment))
 829     return Error(AlignLoc, "alignment is not a power of two");
 830   return false;
 831 }
 832
 833 /// ParseOptionalCommaAlignment
 834 ///   ::= /* empty */
 835 ///   ::= ',' 'align' 4
 836 bool LLParser::ParseOptionalCommaAlignment(unsigned &Alignment) {
 837   Alignment = 0;
 838   if (!EatIfPresent(lltok::comma))
 839     return false;
 840   return ParseToken(lltok::kw_align, "expected 'align'") ||
 841          ParseUInt32(Alignment);
 842 }
 843
 844 /// ParseIndexList
 845 ///    ::=  (',' uint32)+
 846 bool LLParser::ParseIndexList(SmallVectorImpl<unsigned> &Indices) {
 847   if (Lex.getKind() != lltok::comma)
 848     return TokError("expected ',' as start of index list");
 849
 850   while (EatIfPresent(lltok::comma)) {
 851     unsigned Idx;
 852     if (ParseUInt32(Idx)) return true;
 853     Indices.push_back(Idx);
 854   }
 855
 856   return false;
 857 }
 858
 859 //===----------------------------------------------------------------------===//
 860 // Type Parsing.
 861 //===----------------------------------------------------------------------===//
 862
 863 /// ParseType - Parse and resolve a full type.
 864 bool LLParser::ParseType(PATypeHolder &Result, bool AllowVoid) {
 865   LocTy TypeLoc = Lex.getLoc();
 866   if (ParseTypeRec(Result)) return true;
 867
 868   // Verify no unresolved uprefs.
 869   if (!UpRefs.empty())
 870     return Error(UpRefs.back().Loc, "invalid unresolved type up reference");
 871
 872   if (!AllowVoid && Result.get() == Type::VoidTy)
 873     return Error(TypeLoc, "void type only allowed for function results");
 874
 875   return false;
 876 }
 877
 878 /// HandleUpRefs - Every time we finish a new layer of types, this function is
 879 /// called.  It loops through the UpRefs vector, which is a list of the
 880 /// currently active types.  For each type, if the up-reference is contained in
 881 /// the newly completed type, we decrement the level count.  When the level
 882 /// count reaches zero, the up-referenced type is the type that is passed in:
 883 /// thus we can complete the cycle.
 884 ///
 885 PATypeHolder LLParser::HandleUpRefs(const Type *ty) {
 886   // If Ty isn't abstract, or if there are no up-references in it, then there is
 887   // nothing to resolve here.
 888   if (!ty->isAbstract() || UpRefs.empty()) return ty;
 889
 890   PATypeHolder Ty(ty);
 891 #if 0
 892   errs() << "Type '" << Ty->getDescription()
 893          << "' newly formed.  Resolving upreferences.\n"
 894          << UpRefs.size() << " upreferences active!\n";
 895 #endif
 896
 897   // If we find any resolvable upreferences (i.e., those whose NestingLevel goes
 898   // to zero), we resolve them all together before we resolve them to Ty.  At
 899   // the end of the loop, if there is anything to resolve to Ty, it will be in
 900   // this variable.
 901   OpaqueType *TypeToResolve = 0;
 902
 903   for (unsigned i = 0; i != UpRefs.size(); ++i) {
 904     // Determine if 'Ty' directly contains this up-references 'LastContainedTy'.
 905     bool ContainsType =
 906       std::find(Ty->subtype_begin(), Ty->subtype_end(),
 907                 UpRefs[i].LastContainedTy) != Ty->subtype_end();
 908
 909 #if 0
 910     errs() << "  UR#" << i << " - TypeContains(" << Ty->getDescription() << ", "
 911            << UpRefs[i].LastContainedTy->getDescription() << ") = "
 912            << (ContainsType ? "true" : "false")
 913            << " level=" << UpRefs[i].NestingLevel << "\n";
 914 #endif
 915     if (!ContainsType)
 916       continue;
 917
 918     // Decrement level of upreference
 919     unsigned Level = --UpRefs[i].NestingLevel;
 920     UpRefs[i].LastContainedTy = Ty;
 921
 922     // If the Up-reference has a non-zero level, it shouldn't be resolved yet.
 923     if (Level != 0)
 924       continue;
 925
 926 #if 0
 927     errs() << "  * Resolving upreference for " << UpRefs[i].UpRefTy << "\n";
 928 #endif
 929     if (!TypeToResolve)
 930       TypeToResolve = UpRefs[i].UpRefTy;
 931     else
 932       UpRefs[i].UpRefTy->refineAbstractTypeTo(TypeToResolve);
 933     UpRefs.erase(UpRefs.begin()+i);     // Remove from upreference list.
 934     --i;                                // Do not skip the next element.
 935   }
 936
 937   if (TypeToResolve)
 938     TypeToResolve->refineAbstractTypeTo(Ty);
 939
 940   return Ty;
 941 }
 942
 943
 944 /// ParseTypeRec - The recursive function used to process the internal
 945 /// implementation details of types.
 946 bool LLParser::ParseTypeRec(PATypeHolder &Result) {
 947   switch (Lex.getKind()) {
 948   default:
 949     return TokError("expected type");
 950   case lltok::Type:
 951     // TypeRec ::= 'float' | 'void' (etc)
 952     Result = Lex.getTyVal();
 953     Lex.Lex();
 954     break;
 955   case lltok::kw_opaque:
 956     // TypeRec ::= 'opaque'
 957     Result = OpaqueType::get();
 958     Lex.Lex();
 959     break;
 960   case lltok::lbrace:
 961     // TypeRec ::= '{' ... '}'
 962     if (ParseStructType(Result, false))
 963       return true;
 964     break;
 965   case lltok::lsquare:
 966     // TypeRec ::= '[' ... ']'
 967     Lex.Lex(); // eat the lsquare.
 968     if (ParseArrayVectorType(Result, false))
 969       return true;
 970     break;
 971   case lltok::less: // Either vector or packed struct.
 972     // TypeRec ::= '<' ... '>'
 973     Lex.Lex();
 974     if (Lex.getKind() == lltok::lbrace) {
 975       if (ParseStructType(Result, true) ||
 976           ParseToken(lltok::greater, "expected '>' at end of packed struct"))
 977         return true;
 978     } else if (ParseArrayVectorType(Result, true))
 979       return true;
 980     break;
 981   case lltok::LocalVar:
 982   case lltok::StringConstant:  // FIXME: REMOVE IN LLVM 3.0
 983     // TypeRec ::= %foo
 984     if (const Type *T = M->getTypeByName(Lex.getStrVal())) {
 985       Result = T;
 986     } else {
 987       Result = OpaqueType::get();
 988       ForwardRefTypes.insert(std::make_pair(Lex.getStrVal(),
 989                                             std::make_pair(Result,
 990                                                            Lex.getLoc())));
 991       M->addTypeName(Lex.getStrVal(), Result.get());
 992     }
 993     Lex.Lex();
 994     break;
 995
 996   case lltok::LocalVarID:
 997     // TypeRec ::= %4
 998     if (Lex.getUIntVal() < NumberedTypes.size())
 999       Result = NumberedTypes[Lex.getUIntVal()];
1000     else {
1001       std::map<unsigned, std::pair<PATypeHolder, LocTy> >::iterator
1002         I = ForwardRefTypeIDs.find(Lex.getUIntVal());
1003       if (I != ForwardRefTypeIDs.end())
1004         Result = I->second.first;
1005       else {
1006         Result = OpaqueType::get();
1007         ForwardRefTypeIDs.insert(std::make_pair(Lex.getUIntVal(),
1008                                                 std::make_pair(Result,
1009                                                                Lex.getLoc())));
1010       }
1011     }
1012     Lex.Lex();
1013     break;
1014   case lltok::backslash: {
1015     // TypeRec ::= '\' 4
1016     Lex.Lex();
1017     unsigned Val;
1018     if (ParseUInt32(Val)) return true;
1019     OpaqueType *OT = OpaqueType::get();        // Use temporary placeholder.
1020     UpRefs.push_back(UpRefRecord(Lex.getLoc(), Val, OT));
1021     Result = OT;
1022     break;
1023   }
1024   }
1025
1026   // Parse the type suffixes.
1027   while (1) {
1028     switch (Lex.getKind()) {
1029     // End of type.
1030     default: return false;
1031
1032     // TypeRec ::= TypeRec '*'
1033     case lltok::star:
1034       if (Result.get() == Type::LabelTy)
1035         return TokError("basic block pointers are invalid");
1036       if (Result.get() == Type::VoidTy)
1037         return TokError("pointers to void are invalid; use i8* instead");
1038       Result = HandleUpRefs(PointerType::getUnqual(Result.get()));
1039       Lex.Lex();
1040       break;
1041
1042     // TypeRec ::= TypeRec 'addrspace' '(' uint32 ')' '*'
1043     case lltok::kw_addrspace: {
1044       if (Result.get() == Type::LabelTy)
1045         return TokError("basic block pointers are invalid");
1046       if (Result.get() == Type::VoidTy)
1047         return TokError("pointers to void are invalid; use i8* instead");
1048       unsigned AddrSpace;
1049       if (ParseOptionalAddrSpace(AddrSpace) ||
1050           ParseToken(lltok::star, "expected '*' in address space"))
1051         return true;
1052
1053       Result = HandleUpRefs(PointerType::get(Result.get(), AddrSpace));
1054       break;
1055     }
1056
1057     /// Types '(' ArgTypeListI ')' OptFuncAttrs
1058     case lltok::lparen:
1059       if (ParseFunctionType(Result))
1060         return true;
1061       break;
1062     }
1063   }
1064 }
1065
1066 /// ParseParameterList
1067 ///    ::= '(' ')'
1068 ///    ::= '(' Arg (',' Arg)* ')'
1069 ///  Arg
1070 ///    ::= Type OptionalAttributes Value OptionalAttributes
1071 bool LLParser::ParseParameterList(SmallVectorImpl<ParamInfo> &ArgList,
1072                                   PerFunctionState &PFS) {
1073   if (ParseToken(lltok::lparen, "expected '(' in call"))
1074     return true;
1075
1076   while (Lex.getKind() != lltok::rparen) {
1077     // If this isn't the first argument, we need a comma.
1078     if (!ArgList.empty() &&
1079         ParseToken(lltok::comma, "expected ',' in argument list"))
1080       return true;
1081
1082     // Parse the argument.
1083     LocTy ArgLoc;
1084     PATypeHolder ArgTy(Type::VoidTy);
1085     unsigned ArgAttrs1, ArgAttrs2;
1086     Value *V;
1087     if (ParseType(ArgTy, ArgLoc) ||
1088         ParseOptionalAttrs(ArgAttrs1, 0) ||
1089         ParseValue(ArgTy, V, PFS) ||
1090         // FIXME: Should not allow attributes after the argument, remove this in
1091         // LLVM 3.0.
1092         ParseOptionalAttrs(ArgAttrs2, 3))
1093       return true;
1094     ArgList.push_back(ParamInfo(ArgLoc, V, ArgAttrs1|ArgAttrs2));
1095   }
1096
1097   Lex.Lex();  // Lex the ')'.
1098   return false;
1099 }
1100
1101
1102
1103 /// ParseArgumentList - Parse the argument list for a function type or function
1104 /// prototype.  If 'inType' is true then we are parsing a FunctionType.
1105 ///   ::= '(' ArgTypeListI ')'
1106 /// ArgTypeListI
1107 ///   ::= /*empty*/
1108 ///   ::= '...'
1109 ///   ::= ArgTypeList ',' '...'
1110 ///   ::= ArgType (',' ArgType)*
1111 ///
1112 bool LLParser::ParseArgumentList(std::vector<ArgInfo> &ArgList,
1113                                  bool &isVarArg, bool inType) {
1114   isVarArg = false;
1115   assert(Lex.getKind() == lltok::lparen);
1116   Lex.Lex(); // eat the (.
1117
1118   if (Lex.getKind() == lltok::rparen) {
1119     // empty
1120   } else if (Lex.getKind() == lltok::dotdotdot) {
1121     isVarArg = true;
1122     Lex.Lex();
1123   } else {
1124     LocTy TypeLoc = Lex.getLoc();
1125     PATypeHolder ArgTy(Type::VoidTy);
1126     unsigned Attrs;
1127     std::string Name;
1128
1129     // If we're parsing a type, use ParseTypeRec, because we allow recursive
1130     // types (such as a function returning a pointer to itself).  If parsing a
1131     // function prototype, we require fully resolved types.
1132     if ((inType ? ParseTypeRec(ArgTy) : ParseType(ArgTy)) ||
1133         ParseOptionalAttrs(Attrs, 0)) return true;
1134
1135     if (ArgTy == Type::VoidTy)
1136       return Error(TypeLoc, "argument can not have void type");
1137
1138     if (Lex.getKind() == lltok::LocalVar ||
1139         Lex.getKind() == lltok::StringConstant) { // FIXME: REMOVE IN LLVM 3.0
1140       Name = Lex.getStrVal();
1141       Lex.Lex();
1142     }
1143
1144     if (!ArgTy->isFirstClassType() && !isa<OpaqueType>(ArgTy))
1145       return Error(TypeLoc, "invalid type for function argument");
1146
1147     ArgList.push_back(ArgInfo(TypeLoc, ArgTy, Attrs, Name));
1148
1149     while (EatIfPresent(lltok::comma)) {
1150       // Handle ... at end of arg list.
1151       if (EatIfPresent(lltok::dotdotdot)) {
1152         isVarArg = true;
1153         break;
1154       }
1155
1156       // Otherwise must be an argument type.
1157       TypeLoc = Lex.getLoc();
1158       if ((inType ? ParseTypeRec(ArgTy) : ParseType(ArgTy)) ||
1159           ParseOptionalAttrs(Attrs, 0)) return true;
1160
1161       if (ArgTy == Type::VoidTy)
1162         return Error(TypeLoc, "argument can not have void type");
1163
1164       if (Lex.getKind() == lltok::LocalVar ||
1165           Lex.getKind() == lltok::StringConstant) { // FIXME: REMOVE IN LLVM 3.0
1166         Name = Lex.getStrVal();
1167         Lex.Lex();
1168       } else {
1169         Name = "";
1170       }
1171
1172       if (!ArgTy->isFirstClassType() && !isa<OpaqueType>(ArgTy))
1173         return Error(TypeLoc, "invalid type for function argument");
1174
1175       ArgList.push_back(ArgInfo(TypeLoc, ArgTy, Attrs, Name));
1176     }
1177   }
1178
1179   return ParseToken(lltok::rparen, "expected ')' at end of argument list");
1180 }
1181
1182 /// ParseFunctionType
1183 ///  ::= Type ArgumentList OptionalAttrs
1184 bool LLParser::ParseFunctionType(PATypeHolder &Result) {
1185   assert(Lex.getKind() == lltok::lparen);
1186
1187   if (!FunctionType::isValidReturnType(Result))
1188     return TokError("invalid function return type");
1189
1190   std::vector<ArgInfo> ArgList;
1191   bool isVarArg;
1192   unsigned Attrs;
1193   if (ParseArgumentList(ArgList, isVarArg, true) ||
1194       // FIXME: Allow, but ignore attributes on function types!
1195       // FIXME: Remove in LLVM 3.0
1196       ParseOptionalAttrs(Attrs, 2))
1197     return true;
1198
1199   // Reject names on the arguments lists.
1200   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
1201     if (!ArgList[i].Name.empty())
1202       return Error(ArgList[i].Loc, "argument name invalid in function type");
1203     if (!ArgList[i].Attrs != 0) {
1204       // Allow but ignore attributes on function types; this permits
1205       // auto-upgrade.
1206       // FIXME: REJECT ATTRIBUTES ON FUNCTION TYPES in LLVM 3.0
1207     }
1208   }
1209
1210   std::vector<const Type*> ArgListTy;
1211   for (unsigned i = 0, e = ArgList.size(); i != e; ++i)
1212     ArgListTy.push_back(ArgList[i].Type);
1213
1214   Result = HandleUpRefs(FunctionType::get(Result.get(), ArgListTy, isVarArg));
1215   return false;
1216 }
1217
1218 /// ParseStructType: Handles packed and unpacked types.  </> parsed elsewhere.
1219 ///   TypeRec
1220 ///     ::= '{' '}'
1221 ///     ::= '{' TypeRec (',' TypeRec)* '}'
1222 ///     ::= '<' '{' '}' '>'
1223 ///     ::= '<' '{' TypeRec (',' TypeRec)* '}' '>'
1224 bool LLParser::ParseStructType(PATypeHolder &Result, bool Packed) {
1225   assert(Lex.getKind() == lltok::lbrace);
1226   Lex.Lex(); // Consume the '{'
1227
1228   if (EatIfPresent(lltok::rbrace)) {
1229     Result = StructType::get(std::vector<const Type*>(), Packed);
1230     return false;
1231   }
1232
1233   std::vector<PATypeHolder> ParamsList;
1234   LocTy EltTyLoc = Lex.getLoc();
1235   if (ParseTypeRec(Result)) return true;
1236   ParamsList.push_back(Result);
1237
1238   if (Result == Type::VoidTy)
1239     return Error(EltTyLoc, "struct element can not have void type");
1240
1241   while (EatIfPresent(lltok::comma)) {
1242     EltTyLoc = Lex.getLoc();
1243     if (ParseTypeRec(Result)) return true;
1244
1245     if (Result == Type::VoidTy)
1246       return Error(EltTyLoc, "struct element can not have void type");
1247
1248     ParamsList.push_back(Result);
1249   }
1250
1251   if (ParseToken(lltok::rbrace, "expected '}' at end of struct"))
1252     return true;
1253
1254   std::vector<const Type*> ParamsListTy;
1255   for (unsigned i = 0, e = ParamsList.size(); i != e; ++i)
1256     ParamsListTy.push_back(ParamsList[i].get());
1257   Result = HandleUpRefs(StructType::get(ParamsListTy, Packed));
1258   return false;
1259 }
1260
1261 /// ParseArrayVectorType - Parse an array or vector type, assuming the first
1262 /// token has already been consumed.
1263 ///   TypeRec
1264 ///     ::= '[' APSINTVAL 'x' Types ']'
1265 ///     ::= '<' APSINTVAL 'x' Types '>'
1266 bool LLParser::ParseArrayVectorType(PATypeHolder &Result, bool isVector) {
1267   if (Lex.getKind() != lltok::APSInt || Lex.getAPSIntVal().isSigned() ||
1268       Lex.getAPSIntVal().getBitWidth() > 64)
1269     return TokError("expected number in address space");
1270
1271   LocTy SizeLoc = Lex.getLoc();
1272   uint64_t Size = Lex.getAPSIntVal().getZExtValue();
1273   Lex.Lex();
1274
1275   if (ParseToken(lltok::kw_x, "expected 'x' after element count"))
1276       return true;
1277
1278   LocTy TypeLoc = Lex.getLoc();
1279   PATypeHolder EltTy(Type::VoidTy);
1280   if (ParseTypeRec(EltTy)) return true;
1281
1282   if (EltTy == Type::VoidTy)
1283     return Error(TypeLoc, "array and vector element type cannot be void");
1284
1285   if (ParseToken(isVector ? lltok::greater : lltok::rsquare,
1286                  "expected end of sequential type"))
1287     return true;
1288
1289   if (isVector) {
1290     if (Size == 0)
1291       return Error(SizeLoc, "zero element vector is illegal");
1292     if ((unsigned)Size != Size)
1293       return Error(SizeLoc, "size too large for vector");
1294     if (!EltTy->isFloatingPoint() && !EltTy->isInteger())
1295       return Error(TypeLoc, "vector element type must be fp or integer");
1296     Result = VectorType::get(EltTy, unsigned(Size));
1297   } else {
1298     if (!EltTy->isFirstClassType() && !isa<OpaqueType>(EltTy))
1299       return Error(TypeLoc, "invalid array element type");
1300     Result = HandleUpRefs(ArrayType::get(EltTy, Size));
1301   }
1302   return false;
1303 }
1304
1305 //===----------------------------------------------------------------------===//
1306 // Function Semantic Analysis.
1307 //===----------------------------------------------------------------------===//
1308
1309 LLParser::PerFunctionState::PerFunctionState(LLParser &p, Function &f)
1310   : P(p), F(f) {
1311
1312   // Insert unnamed arguments into the NumberedVals list.
1313   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
1314        AI != E; ++AI)
1315     if (!AI->hasName())
1316       NumberedVals.push_back(AI);
1317 }
1318
1319 LLParser::PerFunctionState::~PerFunctionState() {
1320   // If there were any forward referenced non-basicblock values, delete them.
1321   for (std::map<std::string, std::pair<Value*, LocTy> >::iterator
1322        I = ForwardRefVals.begin(), E = ForwardRefVals.end(); I != E; ++I)
1323     if (!isa<BasicBlock>(I->second.first)) {
1324       I->second.first->replaceAllUsesWith(UndefValue::get(I->second.first
1325                                                           ->getType()));
1326       delete I->second.first;
1327       I->second.first = 0;
1328     }
1329
1330   for (std::map<unsigned, std::pair<Value*, LocTy> >::iterator
1331        I = ForwardRefValIDs.begin(), E = ForwardRefValIDs.end(); I != E; ++I)
1332     if (!isa<BasicBlock>(I->second.first)) {
1333       I->second.first->replaceAllUsesWith(UndefValue::get(I->second.first
1334                                                           ->getType()));
1335       delete I->second.first;
1336       I->second.first = 0;
1337     }
1338 }
1339
1340 bool LLParser::PerFunctionState::VerifyFunctionComplete() {
1341   if (!ForwardRefVals.empty())
1342     return P.Error(ForwardRefVals.begin()->second.second,
1343                    "use of undefined value '%" + ForwardRefVals.begin()->first +
1344                    "'");
1345   if (!ForwardRefValIDs.empty())
1346     return P.Error(ForwardRefValIDs.begin()->second.second,
1347                    "use of undefined value '%" +
1348                    utostr(ForwardRefValIDs.begin()->first) + "'");
1349   return false;
1350 }
1351
1352
1353 /// GetVal - Get a value with the specified name or ID, creating a
1354 /// forward reference record if needed.  This can return null if the value
1355 /// exists but does not have the right type.
1356 Value *LLParser::PerFunctionState::GetVal(const std::string &Name,
1357                                           const Type *Ty, LocTy Loc) {
1358   // Look this name up in the normal function symbol table.
1359   Value *Val = F.getValueSymbolTable().lookup(Name);
1360
1361   // If this is a forward reference for the value, see if we already created a
1362   // forward ref record.
1363   if (Val == 0) {
1364     std::map<std::string, std::pair<Value*, LocTy> >::iterator
1365       I = ForwardRefVals.find(Name);
1366     if (I != ForwardRefVals.end())
1367       Val = I->second.first;
1368   }
1369
1370   // If we have the value in the symbol table or fwd-ref table, return it.
1371   if (Val) {
1372     if (Val->getType() == Ty) return Val;
1373     if (Ty == Type::LabelTy)
1374       P.Error(Loc, "'%" + Name + "' is not a basic block");
1375     else
1376       P.Error(Loc, "'%" + Name + "' defined with type '" +
1377               Val->getType()->getDescription() + "'");
1378     return 0;
1379   }
1380
1381   // Don't make placeholders with invalid type.
1382   if (!Ty->isFirstClassType() && !isa<OpaqueType>(Ty) && Ty != Type::LabelTy) {
1383     P.Error(Loc, "invalid use of a non-first-class type");
1384     return 0;
1385   }
1386
1387   // Otherwise, create a new forward reference for this value and remember it.
1388   Value *FwdVal;
1389   if (Ty == Type::LabelTy)
1390     FwdVal = BasicBlock::Create(Name, &F);
1391   else
1392     FwdVal = new Argument(Ty, Name);
1393
1394   ForwardRefVals[Name] = std::make_pair(FwdVal, Loc);
1395   return FwdVal;
1396 }
1397
1398 Value *LLParser::PerFunctionState::GetVal(unsigned ID, const Type *Ty,
1399                                           LocTy Loc) {
1400   // Look this name up in the normal function symbol table.
1401   Value *Val = ID < NumberedVals.size() ? NumberedVals[ID] : 0;
1402
1403   // If this is a forward reference for the value, see if we already created a
1404   // forward ref record.
1405   if (Val == 0) {
1406     std::map<unsigned, std::pair<Value*, LocTy> >::iterator
1407       I = ForwardRefValIDs.find(ID);
1408     if (I != ForwardRefValIDs.end())
1409       Val = I->second.first;
1410   }
1411
1412   // If we have the value in the symbol table or fwd-ref table, return it.
1413   if (Val) {
1414     if (Val->getType() == Ty) return Val;
1415     if (Ty == Type::LabelTy)
1416       P.Error(Loc, "'%" + utostr(ID) + "' is not a basic block");
1417     else
1418       P.Error(Loc, "'%" + utostr(ID) + "' defined with type '" +
1419               Val->getType()->getDescription() + "'");
1420     return 0;
1421   }
1422
1423   if (!Ty->isFirstClassType() && !isa<OpaqueType>(Ty) && Ty != Type::LabelTy) {
1424     P.Error(Loc, "invalid use of a non-first-class type");
1425     return 0;
1426   }
1427
1428   // Otherwise, create a new forward reference for this value and remember it.
1429   Value *FwdVal;
1430   if (Ty == Type::LabelTy)
1431     FwdVal = BasicBlock::Create("", &F);
1432   else
1433     FwdVal = new Argument(Ty);
1434
1435   ForwardRefValIDs[ID] = std::make_pair(FwdVal, Loc);
1436   return FwdVal;
1437 }
1438
1439 /// SetInstName - After an instruction is parsed and inserted into its
1440 /// basic block, this installs its name.
1441 bool LLParser::PerFunctionState::SetInstName(int NameID,
1442                                              const std::string &NameStr,
1443                                              LocTy NameLoc, Instruction *Inst) {
1444   // If this instruction has void type, it cannot have a name or ID specified.
1445   if (Inst->getType() == Type::VoidTy) {
1446     if (NameID != -1 || !NameStr.empty())
1447       return P.Error(NameLoc, "instructions returning void cannot have a name");
1448     return false;
1449   }
1450
1451   // If this was a numbered instruction, verify that the instruction is the
1452   // expected value and resolve any forward references.
1453   if (NameStr.empty()) {
1454     // If neither a name nor an ID was specified, just use the next ID.
1455     if (NameID == -1)
1456       NameID = NumberedVals.size();
1457
1458     if (unsigned(NameID) != NumberedVals.size())
1459       return P.Error(NameLoc, "instruction expected to be numbered '%" +
1460                      utostr(NumberedVals.size()) + "'");
1461
1462     std::map<unsigned, std::pair<Value*, LocTy> >::iterator FI =
1463       ForwardRefValIDs.find(NameID);
1464     if (FI != ForwardRefValIDs.end()) {
1465       if (FI->second.first->getType() != Inst->getType())
1466         return P.Error(NameLoc, "instruction forward referenced with type '" +
1467                        FI->second.first->getType()->getDescription() + "'");
1468       FI->second.first->replaceAllUsesWith(Inst);
1469       ForwardRefValIDs.erase(FI);
1470     }
1471
1472     NumberedVals.push_back(Inst);
1473     return false;
1474   }
1475
1476   // Otherwise, the instruction had a name.  Resolve forward refs and set it.
1477   std::map<std::string, std::pair<Value*, LocTy> >::iterator
1478     FI = ForwardRefVals.find(NameStr);
1479   if (FI != ForwardRefVals.end()) {
1480     if (FI->second.first->getType() != Inst->getType())
1481       return P.Error(NameLoc, "instruction forward referenced with type '" +
1482                      FI->second.first->getType()->getDescription() + "'");
1483     FI->second.first->replaceAllUsesWith(Inst);
1484     ForwardRefVals.erase(FI);
1485   }
1486
1487   // Set the name on the instruction.
1488   Inst->setName(NameStr);
1489
1490   if (Inst->getNameStr() != NameStr)
1491     return P.Error(NameLoc, "multiple definition of local value named '" +
1492                    NameStr + "'");
1493   return false;
1494 }
1495
1496 /// GetBB - Get a basic block with the specified name or ID, creating a
1497 /// forward reference record if needed.
1498 BasicBlock *LLParser::PerFunctionState::GetBB(const std::string &Name,
1499                                               LocTy Loc) {
1500   return cast_or_null<BasicBlock>(GetVal(Name, Type::LabelTy, Loc));
1501 }
1502
1503 BasicBlock *LLParser::PerFunctionState::GetBB(unsigned ID, LocTy Loc) {
1504   return cast_or_null<BasicBlock>(GetVal(ID, Type::LabelTy, Loc));
1505 }
1506
1507 /// DefineBB - Define the specified basic block, which is either named or
1508 /// unnamed.  If there is an error, this returns null otherwise it returns
1509 /// the block being defined.
1510 BasicBlock *LLParser::PerFunctionState::DefineBB(const std::string &Name,
1511                                                  LocTy Loc) {
1512   BasicBlock *BB;
1513   if (Name.empty())
1514     BB = GetBB(NumberedVals.size(), Loc);
1515   else
1516     BB = GetBB(Name, Loc);
1517   if (BB == 0) return 0; // Already diagnosed error.
1518
1519   // Move the block to the end of the function.  Forward ref'd blocks are
1520   // inserted wherever they happen to be referenced.
1521   F.getBasicBlockList().splice(F.end(), F.getBasicBlockList(), BB);
1522
1523   // Remove the block from forward ref sets.
1524   if (Name.empty()) {
1525     ForwardRefValIDs.erase(NumberedVals.size());
1526     NumberedVals.push_back(BB);
1527   } else {
1528     // BB forward references are already in the function symbol table.
1529     ForwardRefVals.erase(Name);
1530   }
1531
1532   return BB;
1533 }
1534
1535 //===----------------------------------------------------------------------===//
1536 // Constants.
1537 //===----------------------------------------------------------------------===//
1538
1539 /// ParseValID - Parse an abstract value that doesn't necessarily have a
1540 /// type implied.  For example, if we parse "4" we don't know what integer type
1541 /// it has.  The value will later be combined with its type and checked for
1542 /// sanity.
1543 bool LLParser::ParseValID(ValID &ID) {
1544   ID.Loc = Lex.getLoc();
1545   switch (Lex.getKind()) {
1546   default: return TokError("expected value token");
1547   case lltok::GlobalID:  // @42
1548     ID.UIntVal = Lex.getUIntVal();
1549     ID.Kind = ValID::t_GlobalID;
1550     break;
1551   case lltok::GlobalVar:  // @foo
1552     ID.StrVal = Lex.getStrVal();
1553     ID.Kind = ValID::t_GlobalName;
1554     break;
1555   case lltok::LocalVarID:  // %42
1556     ID.UIntVal = Lex.getUIntVal();
1557     ID.Kind = ValID::t_LocalID;
1558     break;
1559   case lltok::LocalVar:  // %foo
1560   case lltok::StringConstant:  // "foo" - FIXME: REMOVE IN LLVM 3.0
1561     ID.StrVal = Lex.getStrVal();
1562     ID.Kind = ValID::t_LocalName;
1563     break;
1564   case lltok::APSInt:
1565     ID.APSIntVal = Lex.getAPSIntVal();
1566     ID.Kind = ValID::t_APSInt;
1567     break;
1568   case lltok::APFloat:
1569     ID.APFloatVal = Lex.getAPFloatVal();
1570     ID.Kind = ValID::t_APFloat;
1571     break;
1572   case lltok::kw_true:
1573     ID.ConstantVal = ConstantInt::getTrue();
1574     ID.Kind = ValID::t_Constant;
1575     break;
1576   case lltok::kw_false:
1577     ID.ConstantVal = ConstantInt::getFalse();
1578     ID.Kind = ValID::t_Constant;
1579     break;
1580   case lltok::kw_null: ID.Kind = ValID::t_Null; break;
1581   case lltok::kw_undef: ID.Kind = ValID::t_Undef; break;
1582   case lltok::kw_zeroinitializer: ID.Kind = ValID::t_Zero; break;
1583
1584   case lltok::lbrace: {
1585     // ValID ::= '{' ConstVector '}'
1586     Lex.Lex();
1587     SmallVector<Constant*, 16> Elts;
1588     if (ParseGlobalValueVector(Elts) ||
1589         ParseToken(lltok::rbrace, "expected end of struct constant"))
1590       return true;
1591
1592     ID.ConstantVal = ConstantStruct::get(&Elts[0], Elts.size(), false);
1593     ID.Kind = ValID::t_Constant;
1594     return false;
1595   }
1596   case lltok::less: {
1597     // ValID ::= '<' ConstVector '>'         --> Vector.
1598     // ValID ::= '<' '{' ConstVector '}' '>' --> Packed Struct.
1599     Lex.Lex();
1600     bool isPackedStruct = EatIfPresent(lltok::lbrace);
1601
1602     SmallVector<Constant*, 16> Elts;
1603     LocTy FirstEltLoc = Lex.getLoc();
1604     if (ParseGlobalValueVector(Elts) ||
1605         (isPackedStruct &&
1606          ParseToken(lltok::rbrace, "expected end of packed struct")) ||
1607         ParseToken(lltok::greater, "expected end of constant"))
1608       return true;
1609
1610     if (isPackedStruct) {
1611       ID.ConstantVal = ConstantStruct::get(&Elts[0], Elts.size(), true);
1612       ID.Kind = ValID::t_Constant;
1613       return false;
1614     }
1615
1616     if (Elts.empty())
1617       return Error(ID.Loc, "constant vector must not be empty");
1618
1619     if (!Elts[0]->getType()->isInteger() &&
1620         !Elts[0]->getType()->isFloatingPoint())
1621       return Error(FirstEltLoc,
1622                    "vector elements must have integer or floating point type");
1623
1624     // Verify that all the vector elements have the same type.
1625     for (unsigned i = 1, e = Elts.size(); i != e; ++i)
1626       if (Elts[i]->getType() != Elts[0]->getType())
1627         return Error(FirstEltLoc,
1628                      "vector element #" + utostr(i) +
1629                     " is not of type '" + Elts[0]->getType()->getDescription());
1630
1631     ID.ConstantVal = ConstantVector::get(&Elts[0], Elts.size());
1632     ID.Kind = ValID::t_Constant;
1633     return false;
1634   }
1635   case lltok::lsquare: {   // Array Constant
1636     Lex.Lex();
1637     SmallVector<Constant*, 16> Elts;
1638     LocTy FirstEltLoc = Lex.getLoc();
1639     if (ParseGlobalValueVector(Elts) ||
1640         ParseToken(lltok::rsquare, "expected end of array constant"))
1641       return true;
1642
1643     // Handle empty element.
1644     if (Elts.empty()) {
1645       // Use undef instead of an array because it's inconvenient to determine
1646       // the element type at this point, there being no elements to examine.
1647       ID.Kind = ValID::t_EmptyArray;
1648       return false;
1649     }
1650
1651     if (!Elts[0]->getType()->isFirstClassType())
1652       return Error(FirstEltLoc, "invalid array element type: " +
1653                    Elts[0]->getType()->getDescription());
1654
1655     ArrayType *ATy = ArrayType::get(Elts[0]->getType(), Elts.size());
1656
1657     // Verify all elements are correct type!
1658     for (unsigned i = 0, e = Elts.size(); i != e; ++i) {
1659       if (Elts[i]->getType() != Elts[0]->getType())
1660         return Error(FirstEltLoc,
1661                      "array element #" + utostr(i) +
1662                      " is not of type '" +Elts[0]->getType()->getDescription());
1663     }
1664
1665     ID.ConstantVal = ConstantArray::get(ATy, &Elts[0], Elts.size());
1666     ID.Kind = ValID::t_Constant;
1667     return false;
1668   }
1669   case lltok::kw_c:  // c "foo"
1670     Lex.Lex();
1671     ID.ConstantVal = ConstantArray::get(Lex.getStrVal(), false);
1672     if (ParseToken(lltok::StringConstant, "expected string")) return true;
1673     ID.Kind = ValID::t_Constant;
1674     return false;
1675
1676   case lltok::kw_asm: {
1677     // ValID ::= 'asm' SideEffect? STRINGCONSTANT ',' STRINGCONSTANT
1678     bool HasSideEffect;
1679     Lex.Lex();
1680     if (ParseOptionalToken(lltok::kw_sideeffect, HasSideEffect) ||
1681         ParseStringConstant(ID.StrVal) ||
1682         ParseToken(lltok::comma, "expected comma in inline asm expression") ||
1683         ParseToken(lltok::StringConstant, "expected constraint string"))
1684       return true;
1685     ID.StrVal2 = Lex.getStrVal();
1686     ID.UIntVal = HasSideEffect;
1687     ID.Kind = ValID::t_InlineAsm;
1688     return false;
1689   }
1690
1691   case lltok::kw_trunc:
1692   case lltok::kw_zext:
1693   case lltok::kw_sext:
1694   case lltok::kw_fptrunc:
1695   case lltok::kw_fpext:
1696   case lltok::kw_bitcast:
1697   case lltok::kw_uitofp:
1698   case lltok::kw_sitofp:
1699   case lltok::kw_fptoui:
1700   case lltok::kw_fptosi:
1701   case lltok::kw_inttoptr:
1702   case lltok::kw_ptrtoint: {
1703     unsigned Opc = Lex.getUIntVal();
1704     PATypeHolder DestTy(Type::VoidTy);
1705     Constant *SrcVal;
1706     Lex.Lex();
1707     if (ParseToken(lltok::lparen, "expected '(' after constantexpr cast") ||
1708         ParseGlobalTypeAndValue(SrcVal) ||
1709         ParseToken(lltok::kw_to, "expected 'to' int constantexpr cast") ||
1710         ParseType(DestTy) ||
1711         ParseToken(lltok::rparen, "expected ')' at end of constantexpr cast"))
1712       return true;
1713     if (!CastInst::castIsValid((Instruction::CastOps)Opc, SrcVal, DestTy))
1714       return Error(ID.Loc, "invalid cast opcode for cast from '" +
1715                    SrcVal->getType()->getDescription() + "' to '" +
1716                    DestTy->getDescription() + "'");
1717     ID.ConstantVal = ConstantExpr::getCast((Instruction::CastOps)Opc, SrcVal,
1718                                            DestTy);
1719     ID.Kind = ValID::t_Constant;
1720     return false;
1721   }
1722   case lltok::kw_extractvalue: {
1723     Lex.Lex();
1724     Constant *Val;
1725     SmallVector<unsigned, 4> Indices;
1726     if (ParseToken(lltok::lparen, "expected '(' in extractvalue constantexpr")||
1727         ParseGlobalTypeAndValue(Val) ||
1728         ParseIndexList(Indices) ||
1729         ParseToken(lltok::rparen, "expected ')' in extractvalue constantexpr"))
1730       return true;
1731     if (!isa<StructType>(Val->getType()) && !isa<ArrayType>(Val->getType()))
1732       return Error(ID.Loc, "extractvalue operand must be array or struct");
1733     if (!ExtractValueInst::getIndexedType(Val->getType(), Indices.begin(),
1734                                           Indices.end()))
1735       return Error(ID.Loc, "invalid indices for extractvalue");
1736     ID.ConstantVal = ConstantExpr::getExtractValue(Val,
1737                                                    &Indices[0], Indices.size());
1738     ID.Kind = ValID::t_Constant;
1739     return false;
1740   }
1741   case lltok::kw_insertvalue: {
1742     Lex.Lex();
1743     Constant *Val0, *Val1;
1744     SmallVector<unsigned, 4> Indices;
1745     if (ParseToken(lltok::lparen, "expected '(' in insertvalue constantexpr")||
1746         ParseGlobalTypeAndValue(Val0) ||
1747         ParseToken(lltok::comma, "expected comma in insertvalue constantexpr")||
1748         ParseGlobalTypeAndValue(Val1) ||
1749         ParseIndexList(Indices) ||
1750         ParseToken(lltok::rparen, "expected ')' in insertvalue constantexpr"))
1751       return true;
1752     if (!isa<StructType>(Val0->getType()) && !isa<ArrayType>(Val0->getType()))
1753       return Error(ID.Loc, "extractvalue operand must be array or struct");
1754     if (!ExtractValueInst::getIndexedType(Val0->getType(), Indices.begin(),
1755                                           Indices.end()))
1756       return Error(ID.Loc, "invalid indices for insertvalue");
1757     ID.ConstantVal = ConstantExpr::getInsertValue(Val0, Val1,
1758                                                   &Indices[0], Indices.size());
1759     ID.Kind = ValID::t_Constant;
1760     return false;
1761   }
1762   case lltok::kw_icmp:
1763   case lltok::kw_fcmp:
1764   case lltok::kw_vicmp:
1765   case lltok::kw_vfcmp: {
1766     unsigned PredVal, Opc = Lex.getUIntVal();
1767     Constant *Val0, *Val1;
1768     Lex.Lex();
1769     if (ParseCmpPredicate(PredVal, Opc) ||
1770         ParseToken(lltok::lparen, "expected '(' in compare constantexpr") ||
1771         ParseGlobalTypeAndValue(Val0) ||
1772         ParseToken(lltok::comma, "expected comma in compare constantexpr") ||
1773         ParseGlobalTypeAndValue(Val1) ||
1774         ParseToken(lltok::rparen, "expected ')' in compare constantexpr"))
1775       return true;
1776
1777     if (Val0->getType() != Val1->getType())
1778       return Error(ID.Loc, "compare operands must have the same type");
1779
1780     CmpInst::Predicate Pred = (CmpInst::Predicate)PredVal;
1781
1782     if (Opc == Instruction::FCmp) {
1783       if (!Val0->getType()->isFPOrFPVector())
1784         return Error(ID.Loc, "fcmp requires floating point operands");
1785       ID.ConstantVal = ConstantExpr::getFCmp(Pred, Val0, Val1);
1786     } else if (Opc == Instruction::ICmp) {
1787       if (!Val0->getType()->isIntOrIntVector() &&
1788           !isa<PointerType>(Val0->getType()))
1789         return Error(ID.Loc, "icmp requires pointer or integer operands");
1790       ID.ConstantVal = ConstantExpr::getICmp(Pred, Val0, Val1);
1791     } else if (Opc == Instruction::VFCmp) {
1792       // FIXME: REMOVE VFCMP Support
1793       if (!Val0->getType()->isFPOrFPVector() ||
1794           !isa<VectorType>(Val0->getType()))
1795         return Error(ID.Loc, "vfcmp requires vector floating point operands");
1796       ID.ConstantVal = ConstantExpr::getVFCmp(Pred, Val0, Val1);
1797     } else if (Opc == Instruction::VICmp) {
1798       // FIXME: REMOVE VICMP Support
1799       if (!Val0->getType()->isIntOrIntVector() ||
1800           !isa<VectorType>(Val0->getType()))
1801         return Error(ID.Loc, "vicmp requires vector floating point operands");
1802       ID.ConstantVal = ConstantExpr::getVICmp(Pred, Val0, Val1);
1803     }
1804     ID.Kind = ValID::t_Constant;
1805     return false;
1806   }
1807
1808   // Binary Operators.
1809   case lltok::kw_add:
1810   case lltok::kw_sub:
1811   case lltok::kw_mul:
1812   case lltok::kw_udiv:
1813   case lltok::kw_sdiv:
1814   case lltok::kw_fdiv:
1815   case lltok::kw_urem:
1816   case lltok::kw_srem:
1817   case lltok::kw_frem: {
1818     unsigned Opc = Lex.getUIntVal();
1819     Constant *Val0, *Val1;
1820     Lex.Lex();
1821     if (ParseToken(lltok::lparen, "expected '(' in binary constantexpr") ||
1822         ParseGlobalTypeAndValue(Val0) ||
1823         ParseToken(lltok::comma, "expected comma in binary constantexpr") ||
1824         ParseGlobalTypeAndValue(Val1) ||
1825         ParseToken(lltok::rparen, "expected ')' in binary constantexpr"))
1826       return true;
1827     if (Val0->getType() != Val1->getType())
1828       return Error(ID.Loc, "operands of constexpr must have same type");
1829     if (!Val0->getType()->isIntOrIntVector() &&
1830         !Val0->getType()->isFPOrFPVector())
1831       return Error(ID.Loc,"constexpr requires integer, fp, or vector operands");
1832     ID.ConstantVal = ConstantExpr::get(Opc, Val0, Val1);
1833     ID.Kind = ValID::t_Constant;
1834     return false;
1835   }
1836
1837   // Logical Operations
1838   case lltok::kw_shl:
1839   case lltok::kw_lshr:
1840   case lltok::kw_ashr:
1841   case lltok::kw_and:
1842   case lltok::kw_or:
1843   case lltok::kw_xor: {
1844     unsigned Opc = Lex.getUIntVal();
1845     Constant *Val0, *Val1;
1846     Lex.Lex();
1847     if (ParseToken(lltok::lparen, "expected '(' in logical constantexpr") ||
1848         ParseGlobalTypeAndValue(Val0) ||
1849         ParseToken(lltok::comma, "expected comma in logical constantexpr") ||
1850         ParseGlobalTypeAndValue(Val1) ||
1851         ParseToken(lltok::rparen, "expected ')' in logical constantexpr"))
1852       return true;
1853     if (Val0->getType() != Val1->getType())
1854       return Error(ID.Loc, "operands of constexpr must have same type");
1855     if (!Val0->getType()->isIntOrIntVector())
1856       return Error(ID.Loc,
1857                    "constexpr requires integer or integer vector operands");
1858     ID.ConstantVal = ConstantExpr::get(Opc, Val0, Val1);
1859     ID.Kind = ValID::t_Constant;
1860     return false;
1861   }
1862
1863   case lltok::kw_getelementptr:
1864   case lltok::kw_shufflevector:
1865   case lltok::kw_insertelement:
1866   case lltok::kw_extractelement:
1867   case lltok::kw_select: {
1868     unsigned Opc = Lex.getUIntVal();
1869     SmallVector<Constant*, 16> Elts;
1870     Lex.Lex();
1871     if (ParseToken(lltok::lparen, "expected '(' in constantexpr") ||
1872         ParseGlobalValueVector(Elts) ||
1873         ParseToken(lltok::rparen, "expected ')' in constantexpr"))
1874       return true;
1875
1876     if (Opc == Instruction::GetElementPtr) {
1877       if (Elts.size() == 0 || !isa<PointerType>(Elts[0]->getType()))
1878         return Error(ID.Loc, "getelementptr requires pointer operand");
1879
1880       if (!GetElementPtrInst::getIndexedType(Elts[0]->getType(),
1881                                              (Value**)&Elts[1], Elts.size()-1))
1882         return Error(ID.Loc, "invalid indices for getelementptr");
1883       ID.ConstantVal = ConstantExpr::getGetElementPtr(Elts[0],
1884                                                       &Elts[1], Elts.size()-1);
1885     } else if (Opc == Instruction::Select) {
1886       if (Elts.size() != 3)
1887         return Error(ID.Loc, "expected three operands to select");
1888       if (const char *Reason = SelectInst::areInvalidOperands(Elts[0], Elts[1],
1889                                                               Elts[2]))
1890         return Error(ID.Loc, Reason);
1891       ID.ConstantVal = ConstantExpr::getSelect(Elts[0], Elts[1], Elts[2]);
1892     } else if (Opc == Instruction::ShuffleVector) {
1893       if (Elts.size() != 3)
1894         return Error(ID.Loc, "expected three operands to shufflevector");
1895       if (!ShuffleVectorInst::isValidOperands(Elts[0], Elts[1], Elts[2]))
1896         return Error(ID.Loc, "invalid operands to shufflevector");
1897       ID.ConstantVal = ConstantExpr::getShuffleVector(Elts[0], Elts[1],Elts[2]);
1898     } else if (Opc == Instruction::ExtractElement) {
1899       if (Elts.size() != 2)
1900         return Error(ID.Loc, "expected two operands to extractelement");
1901       if (!ExtractElementInst::isValidOperands(Elts[0], Elts[1]))
1902         return Error(ID.Loc, "invalid extractelement operands");
1903       ID.ConstantVal = ConstantExpr::getExtractElement(Elts[0], Elts[1]);
1904     } else {
1905       assert(Opc == Instruction::InsertElement && "Unknown opcode");
1906       if (Elts.size() != 3)
1907       return Error(ID.Loc, "expected three operands to insertelement");
1908       if (!InsertElementInst::isValidOperands(Elts[0], Elts[1], Elts[2]))
1909         return Error(ID.Loc, "invalid insertelement operands");
1910       ID.ConstantVal = ConstantExpr::getInsertElement(Elts[0], Elts[1],Elts[2]);
1911     }
1912
1913     ID.Kind = ValID::t_Constant;
1914     return false;
1915   }
1916   }
1917
1918   Lex.Lex();
1919   return false;
1920 }
1921
1922 /// ParseGlobalValue - Parse a global value with the specified type.
1923 bool LLParser::ParseGlobalValue(const Type *Ty, Constant *&V) {
1924   V = 0;
1925   ValID ID;
1926   return ParseValID(ID) ||
1927          ConvertGlobalValIDToValue(Ty, ID, V);
1928 }
1929
1930 /// ConvertGlobalValIDToValue - Apply a type to a ValID to get a fully resolved
1931 /// constant.
1932 bool LLParser::ConvertGlobalValIDToValue(const Type *Ty, ValID &ID,
1933                                          Constant *&V) {
1934   if (isa<FunctionType>(Ty))
1935     return Error(ID.Loc, "functions are not values, refer to them as pointers");
1936
1937   switch (ID.Kind) {
1938   default: assert(0 && "Unknown ValID!");
1939   case ValID::t_LocalID:
1940   case ValID::t_LocalName:
1941     return Error(ID.Loc, "invalid use of function-local name");
1942   case ValID::t_InlineAsm:
1943     return Error(ID.Loc, "inline asm can only be an operand of call/invoke");
1944   case ValID::t_GlobalName:
1945     V = GetGlobalVal(ID.StrVal, Ty, ID.Loc);
1946     return V == 0;
1947   case ValID::t_GlobalID:
1948     V = GetGlobalVal(ID.UIntVal, Ty, ID.Loc);
1949     return V == 0;
1950   case ValID::t_APSInt:
1951     if (!isa<IntegerType>(Ty))
1952       return Error(ID.Loc, "integer constant must have integer type");
1953     ID.APSIntVal.extOrTrunc(Ty->getPrimitiveSizeInBits());
1954     V = ConstantInt::get(ID.APSIntVal);
1955     return false;
1956   case ValID::t_APFloat:
1957     if (!Ty->isFloatingPoint() ||
1958         !ConstantFP::isValueValidForType(Ty, ID.APFloatVal))
1959       return Error(ID.Loc, "floating point constant invalid for type");
1960
1961     // The lexer has no type info, so builds all float and double FP constants
1962     // as double.  Fix this here.  Long double does not need this.
1963     if (&ID.APFloatVal.getSemantics() == &APFloat::IEEEdouble &&
1964         Ty == Type::FloatTy) {
1965       bool Ignored;
1966       ID.APFloatVal.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven,
1967                             &Ignored);
1968     }
1969     V = ConstantFP::get(ID.APFloatVal);
1970
1971     if (V->getType() != Ty)
1972       return Error(ID.Loc, "floating point constant does not have type '" +
1973                    Ty->getDescription() + "'");
1974
1975     return false;
1976   case ValID::t_Null:
1977     if (!isa<PointerType>(Ty))
1978       return Error(ID.Loc, "null must be a pointer type");
1979     V = ConstantPointerNull::get(cast<PointerType>(Ty));
1980     return false;
1981   case ValID::t_Undef:
1982     // FIXME: LabelTy should not be a first-class type.
1983     if ((!Ty->isFirstClassType() || Ty == Type::LabelTy) &&
1984         !isa<OpaqueType>(Ty))
1985       return Error(ID.Loc, "invalid type for undef constant");
1986     V = UndefValue::get(Ty);
1987     return false;
1988   case ValID::t_EmptyArray:
1989     if (!isa<ArrayType>(Ty) || cast<ArrayType>(Ty)->getNumElements() != 0)
1990       return Error(ID.Loc, "invalid empty array initializer");
1991     V = UndefValue::get(Ty);
1992     return false;
1993   case ValID::t_Zero:
1994     // FIXME: LabelTy should not be a first-class type.
1995     if (!Ty->isFirstClassType() || Ty == Type::LabelTy)
1996       return Error(ID.Loc, "invalid type for null constant");
1997     V = Constant::getNullValue(Ty);
1998     return false;
1999   case ValID::t_Constant:
2000     if (ID.ConstantVal->getType() != Ty)
2001       return Error(ID.Loc, "constant expression type mismatch");
2002     V = ID.ConstantVal;
2003     return false;
2004   }
2005 }
2006
2007 bool LLParser::ParseGlobalTypeAndValue(Constant *&V) {
2008   PATypeHolder Type(Type::VoidTy);
2009   return ParseType(Type) ||
2010          ParseGlobalValue(Type, V);
2011 }
2012
2013 /// ParseGlobalValueVector
2014 ///   ::= /*empty*/
2015 ///   ::= TypeAndValue (',' TypeAndValue)*
2016 bool LLParser::ParseGlobalValueVector(SmallVectorImpl<Constant*> &Elts) {
2017   // Empty list.
2018   if (Lex.getKind() == lltok::rbrace ||
2019       Lex.getKind() == lltok::rsquare ||
2020       Lex.getKind() == lltok::greater ||
2021       Lex.getKind() == lltok::rparen)
2022     return false;
2023
2024   Constant *C;
2025   if (ParseGlobalTypeAndValue(C)) return true;
2026   Elts.push_back(C);
2027
2028   while (EatIfPresent(lltok::comma)) {
2029     if (ParseGlobalTypeAndValue(C)) return true;
2030     Elts.push_back(C);
2031   }
2032
2033   return false;
2034 }
2035
2036
2037 //===----------------------------------------------------------------------===//
2038 // Function Parsing.
2039 //===----------------------------------------------------------------------===//
2040
2041 bool LLParser::ConvertValIDToValue(const Type *Ty, ValID &ID, Value *&V,
2042                                    PerFunctionState &PFS) {
2043   if (ID.Kind == ValID::t_LocalID)
2044     V = PFS.GetVal(ID.UIntVal, Ty, ID.Loc);
2045   else if (ID.Kind == ValID::t_LocalName)
2046     V = PFS.GetVal(ID.StrVal, Ty, ID.Loc);
2047   else if (ID.Kind == ValID::t_InlineAsm) {
2048     const PointerType *PTy = dyn_cast<PointerType>(Ty);
2049     const FunctionType *FTy =
2050       PTy ? dyn_cast<FunctionType>(PTy->getElementType()) : 0;
2051     if (!FTy || !InlineAsm::Verify(FTy, ID.StrVal2))
2052       return Error(ID.Loc, "invalid type for inline asm constraint string");
2053     V = InlineAsm::get(FTy, ID.StrVal, ID.StrVal2, ID.UIntVal);
2054     return false;
2055   } else {
2056     Constant *C;
2057     if (ConvertGlobalValIDToValue(Ty, ID, C)) return true;
2058     V = C;
2059     return false;
2060   }
2061
2062   return V == 0;
2063 }
2064
2065 bool LLParser::ParseValue(const Type *Ty, Value *&V, PerFunctionState &PFS) {
2066   V = 0;
2067   ValID ID;
2068   return ParseValID(ID) ||
2069          ConvertValIDToValue(Ty, ID, V, PFS);
2070 }
2071
2072 bool LLParser::ParseTypeAndValue(Value *&V, PerFunctionState &PFS) {
2073   PATypeHolder T(Type::VoidTy);
2074   return ParseType(T) ||
2075          ParseValue(T, V, PFS);
2076 }
2077
2078 /// FunctionHeader
2079 ///   ::= OptionalLinkage OptionalVisibility OptionalCallingConv OptRetAttrs
2080 ///       Type GlobalName '(' ArgList ')' OptFuncAttrs OptSection
2081 ///       OptionalAlign OptGC
2082 bool LLParser::ParseFunctionHeader(Function *&Fn, bool isDefine) {
2083   // Parse the linkage.
2084   LocTy LinkageLoc = Lex.getLoc();
2085   unsigned Linkage;
2086
2087   unsigned Visibility, CC, RetAttrs;
2088   PATypeHolder RetType(Type::VoidTy);
2089   LocTy RetTypeLoc = Lex.getLoc();
2090   if (ParseOptionalLinkage(Linkage) ||
2091       ParseOptionalVisibility(Visibility) ||
2092       ParseOptionalCallingConv(CC) ||
2093       ParseOptionalAttrs(RetAttrs, 1) ||
2094       ParseType(RetType, RetTypeLoc, true /*void allowed*/))
2095     return true;
2096
2097   // Verify that the linkage is ok.
2098   switch ((GlobalValue::LinkageTypes)Linkage) {
2099   case GlobalValue::ExternalLinkage:
2100     break; // always ok.
2101   case GlobalValue::DLLImportLinkage:
2102   case GlobalValue::ExternalWeakLinkage:
2103     if (isDefine)
2104       return Error(LinkageLoc, "invalid linkage for function definition");
2105     break;
2106   case GlobalValue::PrivateLinkage:
2107   case GlobalValue::InternalLinkage:
2108   case GlobalValue::LinkOnceAnyLinkage:
2109   case GlobalValue::LinkOnceODRLinkage:
2110   case GlobalValue::WeakAnyLinkage:
2111   case GlobalValue::WeakODRLinkage:
2112   case GlobalValue::DLLExportLinkage:
2113     if (!isDefine)
2114       return Error(LinkageLoc, "invalid linkage for function declaration");
2115     break;
2116   case GlobalValue::AppendingLinkage:
2117   case GlobalValue::GhostLinkage:
2118   case GlobalValue::CommonLinkage:
2119     return Error(LinkageLoc, "invalid function linkage type");
2120   }
2121
2122   if (!FunctionType::isValidReturnType(RetType) ||
2123       isa<OpaqueType>(RetType))
2124     return Error(RetTypeLoc, "invalid function return type");
2125
2126   LocTy NameLoc = Lex.getLoc();
2127
2128   std::string FunctionName;
2129   if (Lex.getKind() == lltok::GlobalVar) {
2130     FunctionName = Lex.getStrVal();
2131   } else if (Lex.getKind() == lltok::GlobalID) {     // @42 is ok.
2132     unsigned NameID = Lex.getUIntVal();
2133
2134     if (NameID != NumberedVals.size())
2135       return TokError("function expected to be numbered '%" +
2136                       utostr(NumberedVals.size()) + "'");
2137   } else {
2138     return TokError("expected function name");
2139   }
2140
2141   Lex.Lex();
2142
2143   if (Lex.getKind() != lltok::lparen)
2144     return TokError("expected '(' in function argument list");
2145
2146   std::vector<ArgInfo> ArgList;
2147   bool isVarArg;
2148   unsigned FuncAttrs;
2149   std::string Section;
2150   unsigned Alignment;
2151   std::string GC;
2152
2153   if (ParseArgumentList(ArgList, isVarArg, false) ||
2154       ParseOptionalAttrs(FuncAttrs, 2) ||
2155       (EatIfPresent(lltok::kw_section) &&
2156        ParseStringConstant(Section)) ||
2157       ParseOptionalAlignment(Alignment) ||
2158       (EatIfPresent(lltok::kw_gc) &&
2159        ParseStringConstant(GC)))
2160     return true;
2161
2162   // If the alignment was parsed as an attribute, move to the alignment field.
2163   if (FuncAttrs & Attribute::Alignment) {
2164     Alignment = Attribute::getAlignmentFromAttrs(FuncAttrs);
2165     FuncAttrs &= ~Attribute::Alignment;
2166   }
2167
2168   // Okay, if we got here, the function is syntactically valid.  Convert types
2169   // and do semantic checks.
2170   std::vector<const Type*> ParamTypeList;
2171   SmallVector<AttributeWithIndex, 8> Attrs;
2172   // FIXME : In 3.0, stop accepting zext, sext and inreg as optional function
2173   // attributes.
2174   unsigned ObsoleteFuncAttrs = Attribute::ZExt|Attribute::SExt|Attribute::InReg;
2175   if (FuncAttrs & ObsoleteFuncAttrs) {
2176     RetAttrs |= FuncAttrs & ObsoleteFuncAttrs;
2177     FuncAttrs &= ~ObsoleteFuncAttrs;
2178   }
2179
2180   if (RetAttrs != Attribute::None)
2181     Attrs.push_back(AttributeWithIndex::get(0, RetAttrs));
2182
2183   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
2184     ParamTypeList.push_back(ArgList[i].Type);
2185     if (ArgList[i].Attrs != Attribute::None)
2186       Attrs.push_back(AttributeWithIndex::get(i+1, ArgList[i].Attrs));
2187   }
2188
2189   if (FuncAttrs != Attribute::None)
2190     Attrs.push_back(AttributeWithIndex::get(~0, FuncAttrs));
2191
2192   AttrListPtr PAL = AttrListPtr::get(Attrs.begin(), Attrs.end());
2193
2194   if (PAL.paramHasAttr(1, Attribute::StructRet) &&
2195       RetType != Type::VoidTy)
2196     return Error(RetTypeLoc, "functions with 'sret' argument must return void");
2197
2198   const FunctionType *FT = FunctionType::get(RetType, ParamTypeList, isVarArg);
2199   const PointerType *PFT = PointerType::getUnqual(FT);
2200
2201   Fn = 0;
2202   if (!FunctionName.empty()) {
2203     // If this was a definition of a forward reference, remove the definition
2204     // from the forward reference table and fill in the forward ref.
2205     std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator FRVI =
2206       ForwardRefVals.find(FunctionName);
2207     if (FRVI != ForwardRefVals.end()) {
2208       Fn = M->getFunction(FunctionName);
2209       ForwardRefVals.erase(FRVI);
2210     } else if ((Fn = M->getFunction(FunctionName))) {
2211       // If this function already exists in the symbol table, then it is
2212       // multiply defined.  We accept a few cases for old backwards compat.
2213       // FIXME: Remove this stuff for LLVM 3.0.
2214       if (Fn->getType() != PFT || Fn->getAttributes() != PAL ||
2215           (!Fn->isDeclaration() && isDefine)) {
2216         // If the redefinition has different type or different attributes,
2217         // reject it.  If both have bodies, reject it.
2218         return Error(NameLoc, "invalid redefinition of function '" +
2219                      FunctionName + "'");
2220       } else if (Fn->isDeclaration()) {
2221         // Make sure to strip off any argument names so we can't get conflicts.
2222         for (Function::arg_iterator AI = Fn->arg_begin(), AE = Fn->arg_end();
2223              AI != AE; ++AI)
2224           AI->setName("");
2225       }
2226     }
2227
2228   } else if (FunctionName.empty()) {
2229     // If this is a definition of a forward referenced function, make sure the
2230     // types agree.
2231     std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator I
2232       = ForwardRefValIDs.find(NumberedVals.size());
2233     if (I != ForwardRefValIDs.end()) {
2234       Fn = cast<Function>(I->second.first);
2235       if (Fn->getType() != PFT)
2236         return Error(NameLoc, "type of definition and forward reference of '@" +
2237                      utostr(NumberedVals.size()) +"' disagree");
2238       ForwardRefValIDs.erase(I);
2239     }
2240   }
2241
2242   if (Fn == 0)
2243     Fn = Function::Create(FT, GlobalValue::ExternalLinkage, FunctionName, M);
2244   else // Move the forward-reference to the correct spot in the module.
2245     M->getFunctionList().splice(M->end(), M->getFunctionList(), Fn);
2246
2247   if (FunctionName.empty())
2248     NumberedVals.push_back(Fn);
2249
2250   Fn->setLinkage((GlobalValue::LinkageTypes)Linkage);
2251   Fn->setVisibility((GlobalValue::VisibilityTypes)Visibility);
2252   Fn->setCallingConv(CC);
2253   Fn->setAttributes(PAL);
2254   Fn->setAlignment(Alignment);
2255   Fn->setSection(Section);
2256   if (!GC.empty()) Fn->setGC(GC.c_str());
2257
2258   // Add all of the arguments we parsed to the function.
2259   Function::arg_iterator ArgIt = Fn->arg_begin();
2260   for (unsigned i = 0, e = ArgList.size(); i != e; ++i, ++ArgIt) {
2261     // If the argument has a name, insert it into the argument symbol table.
2262     if (ArgList[i].Name.empty()) continue;
2263
2264     // Set the name, if it conflicted, it will be auto-renamed.
2265     ArgIt->setName(ArgList[i].Name);
2266
2267     if (ArgIt->getNameStr() != ArgList[i].Name)
2268       return Error(ArgList[i].Loc, "redefinition of argument '%" +
2269                    ArgList[i].Name + "'");
2270   }
2271
2272   return false;
2273 }
2274
2275
2276 /// ParseFunctionBody
2277 ///   ::= '{' BasicBlock+ '}'
2278 ///   ::= 'begin' BasicBlock+ 'end'  // FIXME: remove in LLVM 3.0
2279 ///
2280 bool LLParser::ParseFunctionBody(Function &Fn) {
2281   if (Lex.getKind() != lltok::lbrace && Lex.getKind() != lltok::kw_begin)
2282     return TokError("expected '{' in function body");
2283   Lex.Lex();  // eat the {.
2284
2285   PerFunctionState PFS(*this, Fn);
2286
2287   while (Lex.getKind() != lltok::rbrace && Lex.getKind() != lltok::kw_end)
2288     if (ParseBasicBlock(PFS)) return true;
2289
2290   // Eat the }.
2291   Lex.Lex();
2292
2293   // Verify function is ok.
2294   return PFS.VerifyFunctionComplete();
2295 }
2296
2297 /// ParseBasicBlock
2298 ///   ::= LabelStr? Instruction*
2299 bool LLParser::ParseBasicBlock(PerFunctionState &PFS) {
2300   // If this basic block starts out with a name, remember it.
2301   std::string Name;
2302   LocTy NameLoc = Lex.getLoc();
2303   if (Lex.getKind() == lltok::LabelStr) {
2304     Name = Lex.getStrVal();
2305     Lex.Lex();
2306   }
2307
2308   BasicBlock *BB = PFS.DefineBB(Name, NameLoc);
2309   if (BB == 0) return true;
2310
2311   std::string NameStr;
2312
2313   // Parse the instructions in this block until we get a terminator.
2314   Instruction *Inst;
2315   do {
2316     // This instruction may have three possibilities for a name: a) none
2317     // specified, b) name specified "%foo =", c) number specified: "%4 =".
2318     LocTy NameLoc = Lex.getLoc();
2319     int NameID = -1;
2320     NameStr = "";
2321
2322     if (Lex.getKind() == lltok::LocalVarID) {
2323       NameID = Lex.getUIntVal();
2324       Lex.Lex();
2325       if (ParseToken(lltok::equal, "expected '=' after instruction id"))
2326         return true;
2327     } else if (Lex.getKind() == lltok::LocalVar ||
2328                // FIXME: REMOVE IN LLVM 3.0
2329                Lex.getKind() == lltok::StringConstant) {
2330       NameStr = Lex.getStrVal();
2331       Lex.Lex();
2332       if (ParseToken(lltok::equal, "expected '=' after instruction name"))
2333         return true;
2334     }
2335
2336     if (ParseInstruction(Inst, BB, PFS)) return true;
2337
2338     BB->getInstList().push_back(Inst);
2339
2340     // Set the name on the instruction.
2341     if (PFS.SetInstName(NameID, NameStr, NameLoc, Inst)) return true;
2342   } while (!isa<TerminatorInst>(Inst));
2343
2344   return false;
2345 }
2346
2347 //===----------------------------------------------------------------------===//
2348 // Instruction Parsing.
2349 //===----------------------------------------------------------------------===//
2350
2351 /// ParseInstruction - Parse one of the many different instructions.
2352 ///
2353 bool LLParser::ParseInstruction(Instruction *&Inst, BasicBlock *BB,
2354                                 PerFunctionState &PFS) {
2355   lltok::Kind Token = Lex.getKind();
2356   if (Token == lltok::Eof)
2357     return TokError("found end of file when expecting more instructions");
2358   LocTy Loc = Lex.getLoc();
2359   unsigned KeywordVal = Lex.getUIntVal();
2360   Lex.Lex();  // Eat the keyword.
2361
2362   switch (Token) {
2363   default:                    return Error(Loc, "expected instruction opcode");
2364   // Terminator Instructions.
2365   case lltok::kw_unwind:      Inst = new UnwindInst(); return false;
2366   case lltok::kw_unreachable: Inst = new UnreachableInst(); return false;
2367   case lltok::kw_ret:         return ParseRet(Inst, BB, PFS);
2368   case lltok::kw_br:          return ParseBr(Inst, PFS);
2369   case lltok::kw_switch:      return ParseSwitch(Inst, PFS);
2370   case lltok::kw_invoke:      return ParseInvoke(Inst, PFS);
2371   // Binary Operators.
2372   case lltok::kw_add:
2373   case lltok::kw_sub:
2374   case lltok::kw_mul:    return ParseArithmetic(Inst, PFS, KeywordVal, 0);
2375
2376   case lltok::kw_udiv:
2377   case lltok::kw_sdiv:
2378   case lltok::kw_urem:
2379   case lltok::kw_srem:   return ParseArithmetic(Inst, PFS, KeywordVal, 1);
2380   case lltok::kw_fdiv:
2381   case lltok::kw_frem:   return ParseArithmetic(Inst, PFS, KeywordVal, 2);
2382   case lltok::kw_shl:
2383   case lltok::kw_lshr:
2384   case lltok::kw_ashr:
2385   case lltok::kw_and:
2386   case lltok::kw_or:
2387   case lltok::kw_xor:    return ParseLogical(Inst, PFS, KeywordVal);
2388   case lltok::kw_icmp:
2389   case lltok::kw_fcmp:
2390   case lltok::kw_vicmp:
2391   case lltok::kw_vfcmp:  return ParseCompare(Inst, PFS, KeywordVal);
2392   // Casts.
2393   case lltok::kw_trunc:
2394   case lltok::kw_zext:
2395   case lltok::kw_sext:
2396   case lltok::kw_fptrunc:
2397   case lltok::kw_fpext:
2398   case lltok::kw_bitcast:
2399   case lltok::kw_uitofp:
2400   case lltok::kw_sitofp:
2401   case lltok::kw_fptoui:
2402   case lltok::kw_fptosi:
2403   case lltok::kw_inttoptr:
2404   case lltok::kw_ptrtoint:       return ParseCast(Inst, PFS, KeywordVal);
2405   // Other.
2406   case lltok::kw_select:         return ParseSelect(Inst, PFS);
2407   case lltok::kw_va_arg:         return ParseVA_Arg(Inst, PFS);
2408   case lltok::kw_extractelement: return ParseExtractElement(Inst, PFS);
2409   case lltok::kw_insertelement:  return ParseInsertElement(Inst, PFS);
2410   case lltok::kw_shufflevector:  return ParseShuffleVector(Inst, PFS);
2411   case lltok::kw_phi:            return ParsePHI(Inst, PFS);
2412   case lltok::kw_call:           return ParseCall(Inst, PFS, false);
2413   case lltok::kw_tail:           return ParseCall(Inst, PFS, true);
2414   // Memory.
2415   case lltok::kw_alloca:
2416   case lltok::kw_malloc:         return ParseAlloc(Inst, PFS, KeywordVal);
2417   case lltok::kw_free:           return ParseFree(Inst, PFS);
2418   case lltok::kw_load:           return ParseLoad(Inst, PFS, false);
2419   case lltok::kw_store:          return ParseStore(Inst, PFS, false);
2420   case lltok::kw_volatile:
2421     if (EatIfPresent(lltok::kw_load))
2422       return ParseLoad(Inst, PFS, true);
2423     else if (EatIfPresent(lltok::kw_store))
2424       return ParseStore(Inst, PFS, true);
2425     else
2426       return TokError("expected 'load' or 'store'");
2427   case lltok::kw_getresult:     return ParseGetResult(Inst, PFS);
2428   case lltok::kw_getelementptr: return ParseGetElementPtr(Inst, PFS);
2429   case lltok::kw_extractvalue:  return ParseExtractValue(Inst, PFS);
2430   case lltok::kw_insertvalue:   return ParseInsertValue(Inst, PFS);
2431   }
2432 }
2433
2434 /// ParseCmpPredicate - Parse an integer or fp predicate, based on Kind.
2435 bool LLParser::ParseCmpPredicate(unsigned &P, unsigned Opc) {
2436   // FIXME: REMOVE vicmp/vfcmp!
2437   if (Opc == Instruction::FCmp || Opc == Instruction::VFCmp) {
2438     switch (Lex.getKind()) {
2439     default: TokError("expected fcmp predicate (e.g. 'oeq')");
2440     case lltok::kw_oeq: P = CmpInst::FCMP_OEQ; break;
2441     case lltok::kw_one: P = CmpInst::FCMP_ONE; break;
2442     case lltok::kw_olt: P = CmpInst::FCMP_OLT; break;
2443     case lltok::kw_ogt: P = CmpInst::FCMP_OGT; break;
2444     case lltok::kw_ole: P = CmpInst::FCMP_OLE; break;
2445     case lltok::kw_oge: P = CmpInst::FCMP_OGE; break;
2446     case lltok::kw_ord: P = CmpInst::FCMP_ORD; break;
2447     case lltok::kw_uno: P = CmpInst::FCMP_UNO; break;
2448     case lltok::kw_ueq: P = CmpInst::FCMP_UEQ; break;
2449     case lltok::kw_une: P = CmpInst::FCMP_UNE; break;
2450     case lltok::kw_ult: P = CmpInst::FCMP_ULT; break;
2451     case lltok::kw_ugt: P = CmpInst::FCMP_UGT; break;
2452     case lltok::kw_ule: P = CmpInst::FCMP_ULE; break;
2453     case lltok::kw_uge: P = CmpInst::FCMP_UGE; break;
2454     case lltok::kw_true: P = CmpInst::FCMP_TRUE; break;
2455     case lltok::kw_false: P = CmpInst::FCMP_FALSE; break;
2456     }
2457   } else {
2458     switch (Lex.getKind()) {
2459     default: TokError("expected icmp predicate (e.g. 'eq')");
2460     case lltok::kw_eq:  P = CmpInst::ICMP_EQ; break;
2461     case lltok::kw_ne:  P = CmpInst::ICMP_NE; break;
2462     case lltok::kw_slt: P = CmpInst::ICMP_SLT; break;
2463     case lltok::kw_sgt: P = CmpInst::ICMP_SGT; break;
2464     case lltok::kw_sle: P = CmpInst::ICMP_SLE; break;
2465     case lltok::kw_sge: P = CmpInst::ICMP_SGE; break;
2466     case lltok::kw_ult: P = CmpInst::ICMP_ULT; break;
2467     case lltok::kw_ugt: P = CmpInst::ICMP_UGT; break;
2468     case lltok::kw_ule: P = CmpInst::ICMP_ULE; break;
2469     case lltok::kw_uge: P = CmpInst::ICMP_UGE; break;
2470     }
2471   }
2472   Lex.Lex();
2473   return false;
2474 }
2475
2476 //===----------------------------------------------------------------------===//
2477 // Terminator Instructions.
2478 //===----------------------------------------------------------------------===//
2479
2480 /// ParseRet - Parse a return instruction.
2481 ///   ::= 'ret' void
2482 ///   ::= 'ret' TypeAndValue
2483 ///   ::= 'ret' TypeAndValue (',' TypeAndValue)+  [[obsolete: LLVM 3.0]]
2484 bool LLParser::ParseRet(Instruction *&Inst, BasicBlock *BB,
2485                         PerFunctionState &PFS) {
2486   PATypeHolder Ty(Type::VoidTy);
2487   if (ParseType(Ty, true /*void allowed*/)) return true;
2488
2489   if (Ty == Type::VoidTy) {
2490     Inst = ReturnInst::Create();
2491     return false;
2492   }
2493
2494   Value *RV;
2495   if (ParseValue(Ty, RV, PFS)) return true;
2496
2497   // The normal case is one return value.
2498   if (Lex.getKind() == lltok::comma) {
2499     // FIXME: LLVM 3.0 remove MRV support for 'ret i32 1, i32 2', requiring use
2500     // of 'ret {i32,i32} {i32 1, i32 2}'
2501     SmallVector<Value*, 8> RVs;
2502     RVs.push_back(RV);
2503
2504     while (EatIfPresent(lltok::comma)) {
2505       if (ParseTypeAndValue(RV, PFS)) return true;
2506       RVs.push_back(RV);
2507     }
2508
2509     RV = UndefValue::get(PFS.getFunction().getReturnType());
2510     for (unsigned i = 0, e = RVs.size(); i != e; ++i) {
2511       Instruction *I = InsertValueInst::Create(RV, RVs[i], i, "mrv");
2512       BB->getInstList().push_back(I);
2513       RV = I;
2514     }
2515   }
2516   Inst = ReturnInst::Create(RV);
2517   return false;
2518 }
2519
2520
2521 /// ParseBr
2522 ///   ::= 'br' TypeAndValue
2523 ///   ::= 'br' TypeAndValue ',' TypeAndValue ',' TypeAndValue
2524 bool LLParser::ParseBr(Instruction *&Inst, PerFunctionState &PFS) {
2525   LocTy Loc, Loc2;
2526   Value *Op0, *Op1, *Op2;
2527   if (ParseTypeAndValue(Op0, Loc, PFS)) return true;
2528
2529   if (BasicBlock *BB = dyn_cast<BasicBlock>(Op0)) {
2530     Inst = BranchInst::Create(BB);
2531     return false;
2532   }
2533
2534   if (Op0->getType() != Type::Int1Ty)
2535     return Error(Loc, "branch condition must have 'i1' type");
2536
2537   if (ParseToken(lltok::comma, "expected ',' after branch condition") ||
2538       ParseTypeAndValue(Op1, Loc, PFS) ||
2539       ParseToken(lltok::comma, "expected ',' after true destination") ||
2540       ParseTypeAndValue(Op2, Loc2, PFS))
2541     return true;
2542
2543   if (!isa<BasicBlock>(Op1))
2544     return Error(Loc, "true destination of branch must be a basic block");
2545   if (!isa<BasicBlock>(Op2))
2546     return Error(Loc2, "true destination of branch must be a basic block");
2547
2548   Inst = BranchInst::Create(cast<BasicBlock>(Op1), cast<BasicBlock>(Op2), Op0);
2549   return false;
2550 }
2551
2552 /// ParseSwitch
2553 ///  Instruction
2554 ///    ::= 'switch' TypeAndValue ',' TypeAndValue '[' JumpTable ']'
2555 ///  JumpTable
2556 ///    ::= (TypeAndValue ',' TypeAndValue)*
2557 bool LLParser::ParseSwitch(Instruction *&Inst, PerFunctionState &PFS) {
2558   LocTy CondLoc, BBLoc;
2559   Value *Cond, *DefaultBB;
2560   if (ParseTypeAndValue(Cond, CondLoc, PFS) ||
2561       ParseToken(lltok::comma, "expected ',' after switch condition") ||
2562       ParseTypeAndValue(DefaultBB, BBLoc, PFS) ||
2563       ParseToken(lltok::lsquare, "expected '[' with switch table"))
2564     return true;
2565
2566   if (!isa<IntegerType>(Cond->getType()))
2567     return Error(CondLoc, "switch condition must have integer type");
2568   if (!isa<BasicBlock>(DefaultBB))
2569     return Error(BBLoc, "default destination must be a basic block");
2570
2571   // Parse the jump table pairs.
2572   SmallPtrSet<Value*, 32> SeenCases;
2573   SmallVector<std::pair<ConstantInt*, BasicBlock*>, 32> Table;
2574   while (Lex.getKind() != lltok::rsquare) {
2575     Value *Constant, *DestBB;
2576
2577     if (ParseTypeAndValue(Constant, CondLoc, PFS) ||
2578         ParseToken(lltok::comma, "expected ',' after case value") ||
2579         ParseTypeAndValue(DestBB, BBLoc, PFS))
2580       return true;
2581
2582     if (!SeenCases.insert(Constant))
2583       return Error(CondLoc, "duplicate case value in switch");
2584     if (!isa<ConstantInt>(Constant))
2585       return Error(CondLoc, "case value is not a constant integer");
2586     if (!isa<BasicBlock>(DestBB))
2587       return Error(BBLoc, "case destination is not a basic block");
2588
2589     Table.push_back(std::make_pair(cast<ConstantInt>(Constant),
2590                                    cast<BasicBlock>(DestBB)));
2591   }
2592
2593   Lex.Lex();  // Eat the ']'.
2594
2595   SwitchInst *SI = SwitchInst::Create(Cond, cast<BasicBlock>(DefaultBB),
2596                                       Table.size());
2597   for (unsigned i = 0, e = Table.size(); i != e; ++i)
2598     SI->addCase(Table[i].first, Table[i].second);
2599   Inst = SI;
2600   return false;
2601 }
2602
2603 /// ParseInvoke
2604 ///   ::= 'invoke' OptionalCallingConv OptionalAttrs Type Value ParamList
2605 ///       OptionalAttrs 'to' TypeAndValue 'unwind' TypeAndValue
2606 bool LLParser::ParseInvoke(Instruction *&Inst, PerFunctionState &PFS) {
2607   LocTy CallLoc = Lex.getLoc();
2608   unsigned CC, RetAttrs, FnAttrs;
2609   PATypeHolder RetType(Type::VoidTy);
2610   LocTy RetTypeLoc;
2611   ValID CalleeID;
2612   SmallVector<ParamInfo, 16> ArgList;
2613
2614   Value *NormalBB, *UnwindBB;
2615   if (ParseOptionalCallingConv(CC) ||
2616       ParseOptionalAttrs(RetAttrs, 1) ||
2617       ParseType(RetType, RetTypeLoc, true /*void allowed*/) ||
2618       ParseValID(CalleeID) ||
2619       ParseParameterList(ArgList, PFS) ||
2620       ParseOptionalAttrs(FnAttrs, 2) ||
2621       ParseToken(lltok::kw_to, "expected 'to' in invoke") ||
2622       ParseTypeAndValue(NormalBB, PFS) ||
2623       ParseToken(lltok::kw_unwind, "expected 'unwind' in invoke") ||
2624       ParseTypeAndValue(UnwindBB, PFS))
2625     return true;
2626
2627   if (!isa<BasicBlock>(NormalBB))
2628     return Error(CallLoc, "normal destination is not a basic block");
2629   if (!isa<BasicBlock>(UnwindBB))
2630     return Error(CallLoc, "unwind destination is not a basic block");
2631
2632   // If RetType is a non-function pointer type, then this is the short syntax
2633   // for the call, which means that RetType is just the return type.  Infer the
2634   // rest of the function argument types from the arguments that are present.
2635   const PointerType *PFTy = 0;
2636   const FunctionType *Ty = 0;
2637   if (!(PFTy = dyn_cast<PointerType>(RetType)) ||
2638       !(Ty = dyn_cast<FunctionType>(PFTy->getElementType()))) {
2639     // Pull out the types of all of the arguments...
2640     std::vector<const Type*> ParamTypes;
2641     for (unsigned i = 0, e = ArgList.size(); i != e; ++i)
2642       ParamTypes.push_back(ArgList[i].V->getType());
2643
2644     if (!FunctionType::isValidReturnType(RetType))
2645       return Error(RetTypeLoc, "Invalid result type for LLVM function");
2646
2647     Ty = FunctionType::get(RetType, ParamTypes, false);
2648     PFTy = PointerType::getUnqual(Ty);
2649   }
2650
2651   // Look up the callee.
2652   Value *Callee;
2653   if (ConvertValIDToValue(PFTy, CalleeID, Callee, PFS)) return true;
2654
2655   // FIXME: In LLVM 3.0, stop accepting zext, sext and inreg as optional
2656   // function attributes.
2657   unsigned ObsoleteFuncAttrs = Attribute::ZExt|Attribute::SExt|Attribute::InReg;
2658   if (FnAttrs & ObsoleteFuncAttrs) {
2659     RetAttrs |= FnAttrs & ObsoleteFuncAttrs;
2660     FnAttrs &= ~ObsoleteFuncAttrs;
2661   }
2662
2663   // Set up the Attributes for the function.
2664   SmallVector<AttributeWithIndex, 8> Attrs;
2665   if (RetAttrs != Attribute::None)
2666     Attrs.push_back(AttributeWithIndex::get(0, RetAttrs));
2667
2668   SmallVector<Value*, 8> Args;
2669
2670   // Loop through FunctionType's arguments and ensure they are specified
2671   // correctly.  Also, gather any parameter attributes.
2672   FunctionType::param_iterator I = Ty->param_begin();
2673   FunctionType::param_iterator E = Ty->param_end();
2674   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
2675     const Type *ExpectedTy = 0;
2676     if (I != E) {
2677       ExpectedTy = *I++;
2678     } else if (!Ty->isVarArg()) {
2679       return Error(ArgList[i].Loc, "too many arguments specified");
2680     }
2681
2682     if (ExpectedTy && ExpectedTy != ArgList[i].V->getType())
2683       return Error(ArgList[i].Loc, "argument is not of expected type '" +
2684                    ExpectedTy->getDescription() + "'");
2685     Args.push_back(ArgList[i].V);
2686     if (ArgList[i].Attrs != Attribute::None)
2687       Attrs.push_back(AttributeWithIndex::get(i+1, ArgList[i].Attrs));
2688   }
2689
2690   if (I != E)
2691     return Error(CallLoc, "not enough parameters specified for call");
2692
2693   if (FnAttrs != Attribute::None)
2694     Attrs.push_back(AttributeWithIndex::get(~0, FnAttrs));
2695
2696   // Finish off the Attributes and check them
2697   AttrListPtr PAL = AttrListPtr::get(Attrs.begin(), Attrs.end());
2698
2699   InvokeInst *II = InvokeInst::Create(Callee, cast<BasicBlock>(NormalBB),
2700                                       cast<BasicBlock>(UnwindBB),
2701                                       Args.begin(), Args.end());
2702   II->setCallingConv(CC);
2703   II->setAttributes(PAL);
2704   Inst = II;
2705   return false;
2706 }
2707
2708
2709
2710 //===----------------------------------------------------------------------===//
2711 // Binary Operators.
2712 //===----------------------------------------------------------------------===//
2713
2714 /// ParseArithmetic
2715 ///  ::= ArithmeticOps TypeAndValue ',' Value
2716 ///
2717 /// If OperandType is 0, then any FP or integer operand is allowed.  If it is 1,
2718 /// then any integer operand is allowed, if it is 2, any fp operand is allowed.
2719 bool LLParser::ParseArithmetic(Instruction *&Inst, PerFunctionState &PFS,
2720                                unsigned Opc, unsigned OperandType) {
2721   LocTy Loc; Value *LHS, *RHS;
2722   if (ParseTypeAndValue(LHS, Loc, PFS) ||
2723       ParseToken(lltok::comma, "expected ',' in arithmetic operation") ||
2724       ParseValue(LHS->getType(), RHS, PFS))
2725     return true;
2726
2727   bool Valid;
2728   switch (OperandType) {
2729   default: assert(0 && "Unknown operand type!");
2730   case 0: // int or FP.
2731     Valid = LHS->getType()->isIntOrIntVector() ||
2732             LHS->getType()->isFPOrFPVector();
2733     break;
2734   case 1: Valid = LHS->getType()->isIntOrIntVector(); break;
2735   case 2: Valid = LHS->getType()->isFPOrFPVector(); break;
2736   }
2737
2738   if (!Valid)
2739     return Error(Loc, "invalid operand type for instruction");
2740
2741   Inst = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
2742   return false;
2743 }
2744
2745 /// ParseLogical
2746 ///  ::= ArithmeticOps TypeAndValue ',' Value {
2747 bool LLParser::ParseLogical(Instruction *&Inst, PerFunctionState &PFS,
2748                             unsigned Opc) {
2749   LocTy Loc; Value *LHS, *RHS;
2750   if (ParseTypeAndValue(LHS, Loc, PFS) ||
2751       ParseToken(lltok::comma, "expected ',' in logical operation") ||
2752       ParseValue(LHS->getType(), RHS, PFS))
2753     return true;
2754
2755   if (!LHS->getType()->isIntOrIntVector())
2756     return Error(Loc,"instruction requires integer or integer vector operands");
2757
2758   Inst = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
2759   return false;
2760 }
2761
2762
2763 /// ParseCompare
2764 ///  ::= 'icmp' IPredicates TypeAndValue ',' Value
2765 ///  ::= 'fcmp' FPredicates TypeAndValue ',' Value
2766 ///  ::= 'vicmp' IPredicates TypeAndValue ',' Value
2767 ///  ::= 'vfcmp' FPredicates TypeAndValue ',' Value
2768 bool LLParser::ParseCompare(Instruction *&Inst, PerFunctionState &PFS,
2769                             unsigned Opc) {
2770   // Parse the integer/fp comparison predicate.
2771   LocTy Loc;
2772   unsigned Pred;
2773   Value *LHS, *RHS;
2774   if (ParseCmpPredicate(Pred, Opc) ||
2775       ParseTypeAndValue(LHS, Loc, PFS) ||
2776       ParseToken(lltok::comma, "expected ',' after compare value") ||
2777       ParseValue(LHS->getType(), RHS, PFS))
2778     return true;
2779
2780   if (Opc == Instruction::FCmp) {
2781     if (!LHS->getType()->isFPOrFPVector())
2782       return Error(Loc, "fcmp requires floating point operands");
2783     Inst = new FCmpInst(CmpInst::Predicate(Pred), LHS, RHS);
2784   } else if (Opc == Instruction::ICmp) {
2785     if (!LHS->getType()->isIntOrIntVector() &&
2786         !isa<PointerType>(LHS->getType()))
2787       return Error(Loc, "icmp requires integer operands");
2788     Inst = new ICmpInst(CmpInst::Predicate(Pred), LHS, RHS);
2789   } else if (Opc == Instruction::VFCmp) {
2790     if (!LHS->getType()->isFPOrFPVector() || !isa<VectorType>(LHS->getType()))
2791       return Error(Loc, "vfcmp requires vector floating point operands");
2792     Inst = new VFCmpInst(CmpInst::Predicate(Pred), LHS, RHS);
2793   } else if (Opc == Instruction::VICmp) {
2794     if (!LHS->getType()->isIntOrIntVector() || !isa<VectorType>(LHS->getType()))
2795       return Error(Loc, "vicmp requires vector floating point operands");
2796     Inst = new VICmpInst(CmpInst::Predicate(Pred), LHS, RHS);
2797   }
2798   return false;
2799 }
2800
2801 //===----------------------------------------------------------------------===//
2802 // Other Instructions.
2803 //===----------------------------------------------------------------------===//
2804
2805
2806 /// ParseCast
2807 ///   ::= CastOpc TypeAndValue 'to' Type
2808 bool LLParser::ParseCast(Instruction *&Inst, PerFunctionState &PFS,
2809                          unsigned Opc) {
2810   LocTy Loc;  Value *Op;
2811   PATypeHolder DestTy(Type::VoidTy);
2812   if (ParseTypeAndValue(Op, Loc, PFS) ||
2813       ParseToken(lltok::kw_to, "expected 'to' after cast value") ||
2814       ParseType(DestTy))
2815     return true;
2816
2817   if (!CastInst::castIsValid((Instruction::CastOps)Opc, Op, DestTy)) {
2818     CastInst::castIsValid((Instruction::CastOps)Opc, Op, DestTy);
2819     return Error(Loc, "invalid cast opcode for cast from '" +
2820                  Op->getType()->getDescription() + "' to '" +
2821                  DestTy->getDescription() + "'");
2822   }
2823   Inst = CastInst::Create((Instruction::CastOps)Opc, Op, DestTy);
2824   return false;
2825 }
2826
2827 /// ParseSelect
2828 ///   ::= 'select' TypeAndValue ',' TypeAndValue ',' TypeAndValue
2829 bool LLParser::ParseSelect(Instruction *&Inst, PerFunctionState &PFS) {
2830   LocTy Loc;
2831   Value *Op0, *Op1, *Op2;
2832   if (ParseTypeAndValue(Op0, Loc, PFS) ||
2833       ParseToken(lltok::comma, "expected ',' after select condition") ||
2834       ParseTypeAndValue(Op1, PFS) ||
2835       ParseToken(lltok::comma, "expected ',' after select value") ||
2836       ParseTypeAndValue(Op2, PFS))
2837     return true;
2838
2839   if (const char *Reason = SelectInst::areInvalidOperands(Op0, Op1, Op2))
2840     return Error(Loc, Reason);
2841
2842   Inst = SelectInst::Create(Op0, Op1, Op2);
2843   return false;
2844 }
2845
2846 /// ParseVA_Arg
2847 ///   ::= 'va_arg' TypeAndValue ',' Type
2848 bool LLParser::ParseVA_Arg(Instruction *&Inst, PerFunctionState &PFS) {
2849   Value *Op;
2850   PATypeHolder EltTy(Type::VoidTy);
2851   LocTy TypeLoc;
2852   if (ParseTypeAndValue(Op, PFS) ||
2853       ParseToken(lltok::comma, "expected ',' after vaarg operand") ||
2854       ParseType(EltTy, TypeLoc))
2855     return true;
2856
2857   if (!EltTy->isFirstClassType())
2858     return Error(TypeLoc, "va_arg requires operand with first class type");
2859
2860   Inst = new VAArgInst(Op, EltTy);
2861   return false;
2862 }
2863
2864 /// ParseExtractElement
2865 ///   ::= 'extractelement' TypeAndValue ',' TypeAndValue
2866 bool LLParser::ParseExtractElement(Instruction *&Inst, PerFunctionState &PFS) {
2867   LocTy Loc;
2868   Value *Op0, *Op1;
2869   if (ParseTypeAndValue(Op0, Loc, PFS) ||
2870       ParseToken(lltok::comma, "expected ',' after extract value") ||
2871       ParseTypeAndValue(Op1, PFS))
2872     return true;
2873
2874   if (!ExtractElementInst::isValidOperands(Op0, Op1))
2875     return Error(Loc, "invalid extractelement operands");
2876
2877   Inst = new ExtractElementInst(Op0, Op1);
2878   return false;
2879 }
2880
2881 /// ParseInsertElement
2882 ///   ::= 'insertelement' TypeAndValue ',' TypeAndValue ',' TypeAndValue
2883 bool LLParser::ParseInsertElement(Instruction *&Inst, PerFunctionState &PFS) {
2884   LocTy Loc;
2885   Value *Op0, *Op1, *Op2;
2886   if (ParseTypeAndValue(Op0, Loc, PFS) ||
2887       ParseToken(lltok::comma, "expected ',' after insertelement value") ||
2888       ParseTypeAndValue(Op1, PFS) ||
2889       ParseToken(lltok::comma, "expected ',' after insertelement value") ||
2890       ParseTypeAndValue(Op2, PFS))
2891     return true;
2892
2893   if (!InsertElementInst::isValidOperands(Op0, Op1, Op2))
2894     return Error(Loc, "invalid extractelement operands");
2895
2896   Inst = InsertElementInst::Create(Op0, Op1, Op2);
2897   return false;
2898 }
2899
2900 /// ParseShuffleVector
2901 ///   ::= 'shufflevector' TypeAndValue ',' TypeAndValue ',' TypeAndValue
2902 bool LLParser::ParseShuffleVector(Instruction *&Inst, PerFunctionState &PFS) {
2903   LocTy Loc;
2904   Value *Op0, *Op1, *Op2;
2905   if (ParseTypeAndValue(Op0, Loc, PFS) ||
2906       ParseToken(lltok::comma, "expected ',' after shuffle mask") ||
2907       ParseTypeAndValue(Op1, PFS) ||
2908       ParseToken(lltok::comma, "expected ',' after shuffle value") ||
2909       ParseTypeAndValue(Op2, PFS))
2910     return true;
2911
2912   if (!ShuffleVectorInst::isValidOperands(Op0, Op1, Op2))
2913     return Error(Loc, "invalid extractelement operands");
2914
2915   Inst = new ShuffleVectorInst(Op0, Op1, Op2);
2916   return false;
2917 }
2918
2919 /// ParsePHI
2920 ///   ::= 'phi' Type '[' Value ',' Value ']' (',' '[' Value ',' Valueß ']')*
2921 bool LLParser::ParsePHI(Instruction *&Inst, PerFunctionState &PFS) {
2922   PATypeHolder Ty(Type::VoidTy);
2923   Value *Op0, *Op1;
2924   LocTy TypeLoc = Lex.getLoc();
2925
2926   if (ParseType(Ty) ||
2927       ParseToken(lltok::lsquare, "expected '[' in phi value list") ||
2928       ParseValue(Ty, Op0, PFS) ||
2929       ParseToken(lltok::comma, "expected ',' after insertelement value") ||
2930       ParseValue(Type::LabelTy, Op1, PFS) ||
2931       ParseToken(lltok::rsquare, "expected ']' in phi value list"))
2932     return true;
2933
2934   SmallVector<std::pair<Value*, BasicBlock*>, 16> PHIVals;
2935   while (1) {
2936     PHIVals.push_back(std::make_pair(Op0, cast<BasicBlock>(Op1)));
2937
2938     if (!EatIfPresent(lltok::comma))
2939       break;
2940
2941     if (ParseToken(lltok::lsquare, "expected '[' in phi value list") ||
2942         ParseValue(Ty, Op0, PFS) ||
2943         ParseToken(lltok::comma, "expected ',' after insertelement value") ||
2944         ParseValue(Type::LabelTy, Op1, PFS) ||
2945         ParseToken(lltok::rsquare, "expected ']' in phi value list"))
2946       return true;
2947   }
2948
2949   if (!Ty->isFirstClassType())
2950     return Error(TypeLoc, "phi node must have first class type");
2951
2952   PHINode *PN = PHINode::Create(Ty);
2953   PN->reserveOperandSpace(PHIVals.size());
2954   for (unsigned i = 0, e = PHIVals.size(); i != e; ++i)
2955     PN->addIncoming(PHIVals[i].first, PHIVals[i].second);
2956   Inst = PN;
2957   return false;
2958 }
2959
2960 /// ParseCall
2961 ///   ::= 'tail'? 'call' OptionalCallingConv OptionalAttrs Type Value
2962 ///       ParameterList OptionalAttrs
2963 bool LLParser::ParseCall(Instruction *&Inst, PerFunctionState &PFS,
2964                          bool isTail) {
2965   unsigned CC, RetAttrs, FnAttrs;
2966   PATypeHolder RetType(Type::VoidTy);
2967   LocTy RetTypeLoc;
2968   ValID CalleeID;
2969   SmallVector<ParamInfo, 16> ArgList;
2970   LocTy CallLoc = Lex.getLoc();
2971
2972   if ((isTail && ParseToken(lltok::kw_call, "expected 'tail call'")) ||
2973       ParseOptionalCallingConv(CC) ||
2974       ParseOptionalAttrs(RetAttrs, 1) ||
2975       ParseType(RetType, RetTypeLoc, true /*void allowed*/) ||
2976       ParseValID(CalleeID) ||
2977       ParseParameterList(ArgList, PFS) ||
2978       ParseOptionalAttrs(FnAttrs, 2))
2979     return true;
2980
2981   // If RetType is a non-function pointer type, then this is the short syntax
2982   // for the call, which means that RetType is just the return type.  Infer the
2983   // rest of the function argument types from the arguments that are present.
2984   const PointerType *PFTy = 0;
2985   const FunctionType *Ty = 0;
2986   if (!(PFTy = dyn_cast<PointerType>(RetType)) ||
2987       !(Ty = dyn_cast<FunctionType>(PFTy->getElementType()))) {
2988     // Pull out the types of all of the arguments...
2989     std::vector<const Type*> ParamTypes;
2990     for (unsigned i = 0, e = ArgList.size(); i != e; ++i)
2991       ParamTypes.push_back(ArgList[i].V->getType());
2992
2993     if (!FunctionType::isValidReturnType(RetType))
2994       return Error(RetTypeLoc, "Invalid result type for LLVM function");
2995
2996     Ty = FunctionType::get(RetType, ParamTypes, false);
2997     PFTy = PointerType::getUnqual(Ty);
2998   }
2999
3000   // Look up the callee.
3001   Value *Callee;
3002   if (ConvertValIDToValue(PFTy, CalleeID, Callee, PFS)) return true;
3003
3004   // FIXME: In LLVM 3.0, stop accepting zext, sext and inreg as optional
3005   // function attributes.
3006   unsigned ObsoleteFuncAttrs = Attribute::ZExt|Attribute::SExt|Attribute::InReg;
3007   if (FnAttrs & ObsoleteFuncAttrs) {
3008     RetAttrs |= FnAttrs & ObsoleteFuncAttrs;
3009     FnAttrs &= ~ObsoleteFuncAttrs;
3010   }
3011
3012   // Set up the Attributes for the function.
3013   SmallVector<AttributeWithIndex, 8> Attrs;
3014   if (RetAttrs != Attribute::None)
3015     Attrs.push_back(AttributeWithIndex::get(0, RetAttrs));
3016
3017   SmallVector<Value*, 8> Args;
3018
3019   // Loop through FunctionType's arguments and ensure they are specified
3020   // correctly.  Also, gather any parameter attributes.
3021   FunctionType::param_iterator I = Ty->param_begin();
3022   FunctionType::param_iterator E = Ty->param_end();
3023   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
3024     const Type *ExpectedTy = 0;
3025     if (I != E) {
3026       ExpectedTy = *I++;
3027     } else if (!Ty->isVarArg()) {
3028       return Error(ArgList[i].Loc, "too many arguments specified");
3029     }
3030
3031     if (ExpectedTy && ExpectedTy != ArgList[i].V->getType())
3032       return Error(ArgList[i].Loc, "argument is not of expected type '" +
3033                    ExpectedTy->getDescription() + "'");
3034     Args.push_back(ArgList[i].V);
3035     if (ArgList[i].Attrs != Attribute::None)
3036       Attrs.push_back(AttributeWithIndex::get(i+1, ArgList[i].Attrs));
3037   }
3038
3039   if (I != E)
3040     return Error(CallLoc, "not enough parameters specified for call");
3041
3042   if (FnAttrs != Attribute::None)
3043     Attrs.push_back(AttributeWithIndex::get(~0, FnAttrs));
3044
3045   // Finish off the Attributes and check them
3046   AttrListPtr PAL = AttrListPtr::get(Attrs.begin(), Attrs.end());
3047
3048   CallInst *CI = CallInst::Create(Callee, Args.begin(), Args.end());
3049   CI->setTailCall(isTail);
3050   CI->setCallingConv(CC);
3051   CI->setAttributes(PAL);
3052   Inst = CI;
3053   return false;
3054 }
3055
3056 //===----------------------------------------------------------------------===//
3057 // Memory Instructions.
3058 //===----------------------------------------------------------------------===//
3059
3060 /// ParseAlloc
3061 ///   ::= 'malloc' Type (',' TypeAndValue)? (',' OptionalAlignment)?
3062 ///   ::= 'alloca' Type (',' TypeAndValue)? (',' OptionalAlignment)?
3063 bool LLParser::ParseAlloc(Instruction *&Inst, PerFunctionState &PFS,
3064                           unsigned Opc) {
3065   PATypeHolder Ty(Type::VoidTy);
3066   Value *Size = 0;
3067   LocTy SizeLoc = 0;
3068   unsigned Alignment = 0;
3069   if (ParseType(Ty)) return true;
3070
3071   if (EatIfPresent(lltok::comma)) {
3072     if (Lex.getKind() == lltok::kw_align) {
3073       if (ParseOptionalAlignment(Alignment)) return true;
3074     } else if (ParseTypeAndValue(Size, SizeLoc, PFS) ||
3075                ParseOptionalCommaAlignment(Alignment)) {
3076       return true;
3077     }
3078   }
3079
3080   if (Size && Size->getType() != Type::Int32Ty)
3081     return Error(SizeLoc, "element count must be i32");
3082
3083   if (Opc == Instruction::Malloc)
3084     Inst = new MallocInst(Ty, Size, Alignment);
3085   else
3086     Inst = new AllocaInst(Ty, Size, Alignment);
3087   return false;
3088 }
3089
3090 /// ParseFree
3091 ///   ::= 'free' TypeAndValue
3092 bool LLParser::ParseFree(Instruction *&Inst, PerFunctionState &PFS) {
3093   Value *Val; LocTy Loc;
3094   if (ParseTypeAndValue(Val, Loc, PFS)) return true;
3095   if (!isa<PointerType>(Val->getType()))
3096     return Error(Loc, "operand to free must be a pointer");
3097   Inst = new FreeInst(Val);
3098   return false;
3099 }
3100
3101 /// ParseLoad
3102 ///   ::= 'volatile'? 'load' TypeAndValue (',' 'align' uint)?
3103 bool LLParser::ParseLoad(Instruction *&Inst, PerFunctionState &PFS,
3104                          bool isVolatile) {
3105   Value *Val; LocTy Loc;
3106   unsigned Alignment;
3107   if (ParseTypeAndValue(Val, Loc, PFS) ||
3108       ParseOptionalCommaAlignment(Alignment))
3109     return true;
3110
3111   if (!isa<PointerType>(Val->getType()) ||
3112       !cast<PointerType>(Val->getType())->getElementType()->isFirstClassType())
3113     return Error(Loc, "load operand must be a pointer to a first class type");
3114
3115   Inst = new LoadInst(Val, "", isVolatile, Alignment);
3116   return false;
3117 }
3118
3119 /// ParseStore
3120 ///   ::= 'volatile'? 'store' TypeAndValue ',' TypeAndValue (',' 'align' uint)?
3121 bool LLParser::ParseStore(Instruction *&Inst, PerFunctionState &PFS,
3122                           bool isVolatile) {
3123   Value *Val, *Ptr; LocTy Loc, PtrLoc;
3124   unsigned Alignment;
3125   if (ParseTypeAndValue(Val, Loc, PFS) ||
3126       ParseToken(lltok::comma, "expected ',' after store operand") ||
3127       ParseTypeAndValue(Ptr, PtrLoc, PFS) ||
3128       ParseOptionalCommaAlignment(Alignment))
3129     return true;
3130
3131   if (!isa<PointerType>(Ptr->getType()))
3132     return Error(PtrLoc, "store operand must be a pointer");
3133   if (!Val->getType()->isFirstClassType())
3134     return Error(Loc, "store operand must be a first class value");
3135   if (cast<PointerType>(Ptr->getType())->getElementType() != Val->getType())
3136     return Error(Loc, "stored value and pointer type do not match");
3137
3138   Inst = new StoreInst(Val, Ptr, isVolatile, Alignment);
3139   return false;
3140 }
3141
3142 /// ParseGetResult
3143 ///   ::= 'getresult' TypeAndValue ',' uint
3144 /// FIXME: Remove support for getresult in LLVM 3.0
3145 bool LLParser::ParseGetResult(Instruction *&Inst, PerFunctionState &PFS) {
3146   Value *Val; LocTy ValLoc, EltLoc;
3147   unsigned Element;
3148   if (ParseTypeAndValue(Val, ValLoc, PFS) ||
3149       ParseToken(lltok::comma, "expected ',' after getresult operand") ||
3150       ParseUInt32(Element, EltLoc))
3151     return true;
3152
3153   if (!isa<StructType>(Val->getType()) && !isa<ArrayType>(Val->getType()))
3154     return Error(ValLoc, "getresult inst requires an aggregate operand");
3155   if (!ExtractValueInst::getIndexedType(Val->getType(), Element))
3156     return Error(EltLoc, "invalid getresult index for value");
3157   Inst = ExtractValueInst::Create(Val, Element);
3158   return false;
3159 }
3160
3161 /// ParseGetElementPtr
3162 ///   ::= 'getelementptr' TypeAndValue (',' TypeAndValue)*
3163 bool LLParser::ParseGetElementPtr(Instruction *&Inst, PerFunctionState &PFS) {
3164   Value *Ptr, *Val; LocTy Loc, EltLoc;
3165   if (ParseTypeAndValue(Ptr, Loc, PFS)) return true;
3166
3167   if (!isa<PointerType>(Ptr->getType()))
3168     return Error(Loc, "base of getelementptr must be a pointer");
3169
3170   SmallVector<Value*, 16> Indices;
3171   while (EatIfPresent(lltok::comma)) {
3172     if (ParseTypeAndValue(Val, EltLoc, PFS)) return true;
3173     if (!isa<IntegerType>(Val->getType()))
3174       return Error(EltLoc, "getelementptr index must be an integer");
3175     Indices.push_back(Val);
3176   }
3177
3178   if (!GetElementPtrInst::getIndexedType(Ptr->getType(),
3179                                          Indices.begin(), Indices.end()))
3180     return Error(Loc, "invalid getelementptr indices");
3181   Inst = GetElementPtrInst::Create(Ptr, Indices.begin(), Indices.end());
3182   return false;
3183 }
3184
3185 /// ParseExtractValue
3186 ///   ::= 'extractvalue' TypeAndValue (',' uint32)+
3187 bool LLParser::ParseExtractValue(Instruction *&Inst, PerFunctionState &PFS) {
3188   Value *Val; LocTy Loc;
3189   SmallVector<unsigned, 4> Indices;
3190   if (ParseTypeAndValue(Val, Loc, PFS) ||
3191       ParseIndexList(Indices))
3192     return true;
3193
3194   if (!isa<StructType>(Val->getType()) && !isa<ArrayType>(Val->getType()))
3195     return Error(Loc, "extractvalue operand must be array or struct");
3196
3197   if (!ExtractValueInst::getIndexedType(Val->getType(), Indices.begin(),
3198                                         Indices.end()))
3199     return Error(Loc, "invalid indices for extractvalue");
3200   Inst = ExtractValueInst::Create(Val, Indices.begin(), Indices.end());
3201   return false;
3202 }
3203
3204 /// ParseInsertValue
3205 ///   ::= 'insertvalue' TypeAndValue ',' TypeAndValue (',' uint32)+
3206 bool LLParser::ParseInsertValue(Instruction *&Inst, PerFunctionState &PFS) {
3207   Value *Val0, *Val1; LocTy Loc0, Loc1;
3208   SmallVector<unsigned, 4> Indices;
3209   if (ParseTypeAndValue(Val0, Loc0, PFS) ||
3210       ParseToken(lltok::comma, "expected comma after insertvalue operand") ||
3211       ParseTypeAndValue(Val1, Loc1, PFS) ||
3212       ParseIndexList(Indices))
3213     return true;
3214
3215   if (!isa<StructType>(Val0->getType()) && !isa<ArrayType>(Val0->getType()))
3216     return Error(Loc0, "extractvalue operand must be array or struct");
3217
3218   if (!ExtractValueInst::getIndexedType(Val0->getType(), Indices.begin(),
3219                                         Indices.end()))
3220     return Error(Loc0, "invalid indices for insertvalue");
3221   Inst = InsertValueInst::Create(Val0, Val1, Indices.begin(), Indices.end());
3222   return false;
3223 }