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/ADT/SmallPtrSet.h"
  16 #include "llvm/IR/AutoUpgrade.h"
  17 #include "llvm/IR/CallingConv.h"
  18 #include "llvm/IR/Constants.h"
  19 #include "llvm/IR/DerivedTypes.h"
  20 #include "llvm/IR/InlineAsm.h"
  21 #include "llvm/IR/Instructions.h"
  22 #include "llvm/IR/LLVMContext.h"
  23 #include "llvm/IR/Module.h"
  24 #include "llvm/IR/Operator.h"
  25 #include "llvm/IR/ValueSymbolTable.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Support/SaveAndRestore.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 using namespace llvm;
  30
  31 static std::string getTypeString(Type *T) {
  32   std::string Result;
  33   raw_string_ostream Tmp(Result);
  34   Tmp << *T;
  35   return Tmp.str();
  36 }
  37
  38 /// Run: module ::= toplevelentity*
  39 bool LLParser::Run() {
  40   // Prime the lexer.
  41   Lex.Lex();
  42
  43   return ParseTopLevelEntities() ||
  44          ValidateEndOfModule();
  45 }
  46
  47 /// ValidateEndOfModule - Do final validity and sanity checks at the end of the
  48 /// module.
  49 bool LLParser::ValidateEndOfModule() {
  50   // Handle any instruction metadata forward references.
  51   if (!ForwardRefInstMetadata.empty()) {
  52     for (DenseMap<Instruction*, std::vector<MDRef> >::iterator
  53          I = ForwardRefInstMetadata.begin(), E = ForwardRefInstMetadata.end();
  54          I != E; ++I) {
  55       Instruction *Inst = I->first;
  56       const std::vector<MDRef> &MDList = I->second;
  57
  58       for (unsigned i = 0, e = MDList.size(); i != e; ++i) {
  59         unsigned SlotNo = MDList[i].MDSlot;
  60
  61         if (SlotNo >= NumberedMetadata.size() ||
  62             NumberedMetadata[SlotNo] == nullptr)
  63           return Error(MDList[i].Loc, "use of undefined metadata '!" +
  64                        Twine(SlotNo) + "'");
  65         assert(!NumberedMetadata[SlotNo]->isFunctionLocal() &&
  66                "Unexpected function-local metadata");
  67         Inst->setMetadata(MDList[i].MDKind, NumberedMetadata[SlotNo]);
  68       }
  69     }
  70     ForwardRefInstMetadata.clear();
  71   }
  72
  73   for (unsigned I = 0, E = InstsWithTBAATag.size(); I < E; I++)
  74     UpgradeInstWithTBAATag(InstsWithTBAATag[I]);
  75
  76   // Handle any function attribute group forward references.
  77   for (std::map<Value*, std::vector<unsigned> >::iterator
  78          I = ForwardRefAttrGroups.begin(), E = ForwardRefAttrGroups.end();
  79          I != E; ++I) {
  80     Value *V = I->first;
  81     std::vector<unsigned> &Vec = I->second;
  82     AttrBuilder B;
  83
  84     for (std::vector<unsigned>::iterator VI = Vec.begin(), VE = Vec.end();
  85          VI != VE; ++VI)
  86       B.merge(NumberedAttrBuilders[*VI]);
  87
  88     if (Function *Fn = dyn_cast<Function>(V)) {
  89       AttributeSet AS = Fn->getAttributes();
  90       AttrBuilder FnAttrs(AS.getFnAttributes(), AttributeSet::FunctionIndex);
  91       AS = AS.removeAttributes(Context, AttributeSet::FunctionIndex,
  92                                AS.getFnAttributes());
  93
  94       FnAttrs.merge(B);
  95
  96       // If the alignment was parsed as an attribute, move to the alignment
  97       // field.
  98       if (FnAttrs.hasAlignmentAttr()) {
  99         Fn->setAlignment(FnAttrs.getAlignment());
 100         FnAttrs.removeAttribute(Attribute::Alignment);
 101       }
 102
 103       AS = AS.addAttributes(Context, AttributeSet::FunctionIndex,
 104                             AttributeSet::get(Context,
 105                                               AttributeSet::FunctionIndex,
 106                                               FnAttrs));
 107       Fn->setAttributes(AS);
 108     } else if (CallInst *CI = dyn_cast<CallInst>(V)) {
 109       AttributeSet AS = CI->getAttributes();
 110       AttrBuilder FnAttrs(AS.getFnAttributes(), AttributeSet::FunctionIndex);
 111       AS = AS.removeAttributes(Context, AttributeSet::FunctionIndex,
 112                                AS.getFnAttributes());
 113       FnAttrs.merge(B);
 114       AS = AS.addAttributes(Context, AttributeSet::FunctionIndex,
 115                             AttributeSet::get(Context,
 116                                               AttributeSet::FunctionIndex,
 117                                               FnAttrs));
 118       CI->setAttributes(AS);
 119     } else if (InvokeInst *II = dyn_cast<InvokeInst>(V)) {
 120       AttributeSet AS = II->getAttributes();
 121       AttrBuilder FnAttrs(AS.getFnAttributes(), AttributeSet::FunctionIndex);
 122       AS = AS.removeAttributes(Context, AttributeSet::FunctionIndex,
 123                                AS.getFnAttributes());
 124       FnAttrs.merge(B);
 125       AS = AS.addAttributes(Context, AttributeSet::FunctionIndex,
 126                             AttributeSet::get(Context,
 127                                               AttributeSet::FunctionIndex,
 128                                               FnAttrs));
 129       II->setAttributes(AS);
 130     } else {
 131       llvm_unreachable("invalid object with forward attribute group reference");
 132     }
 133   }
 134
 135   // If there are entries in ForwardRefBlockAddresses at this point, the
 136   // function was never defined.
 137   if (!ForwardRefBlockAddresses.empty())
 138     return Error(ForwardRefBlockAddresses.begin()->first.Loc,
 139                  "expected function name in blockaddress");
 140
 141   for (unsigned i = 0, e = NumberedTypes.size(); i != e; ++i)
 142     if (NumberedTypes[i].second.isValid())
 143       return Error(NumberedTypes[i].second,
 144                    "use of undefined type '%" + Twine(i) + "'");
 145
 146   for (StringMap<std::pair<Type*, LocTy> >::iterator I =
 147        NamedTypes.begin(), E = NamedTypes.end(); I != E; ++I)
 148     if (I->second.second.isValid())
 149       return Error(I->second.second,
 150                    "use of undefined type named '" + I->getKey() + "'");
 151
 152   if (!ForwardRefComdats.empty())
 153     return Error(ForwardRefComdats.begin()->second,
 154                  "use of undefined comdat '$" +
 155                      ForwardRefComdats.begin()->first + "'");
 156
 157   if (!ForwardRefVals.empty())
 158     return Error(ForwardRefVals.begin()->second.second,
 159                  "use of undefined value '@" + ForwardRefVals.begin()->first +
 160                  "'");
 161
 162   if (!ForwardRefValIDs.empty())
 163     return Error(ForwardRefValIDs.begin()->second.second,
 164                  "use of undefined value '@" +
 165                  Twine(ForwardRefValIDs.begin()->first) + "'");
 166
 167   if (!ForwardRefMDNodes.empty())
 168     return Error(ForwardRefMDNodes.begin()->second.second,
 169                  "use of undefined metadata '!" +
 170                  Twine(ForwardRefMDNodes.begin()->first) + "'");
 171
 172
 173   // Look for intrinsic functions and CallInst that need to be upgraded
 174   for (Module::iterator FI = M->begin(), FE = M->end(); FI != FE; )
 175     UpgradeCallsToIntrinsic(FI++); // must be post-increment, as we remove
 176
 177   UpgradeDebugInfo(*M);
 178
 179   return false;
 180 }
 181
 182 //===----------------------------------------------------------------------===//
 183 // Top-Level Entities
 184 //===----------------------------------------------------------------------===//
 185
 186 bool LLParser::ParseTopLevelEntities() {
 187   while (1) {
 188     switch (Lex.getKind()) {
 189     default:         return TokError("expected top-level entity");
 190     case lltok::Eof: return false;
 191     case lltok::kw_declare: if (ParseDeclare()) return true; break;
 192     case lltok::kw_define:  if (ParseDefine()) return true; break;
 193     case lltok::kw_module:  if (ParseModuleAsm()) return true; break;
 194     case lltok::kw_target:  if (ParseTargetDefinition()) return true; break;
 195     case lltok::kw_deplibs: if (ParseDepLibs()) return true; break;
 196     case lltok::LocalVarID: if (ParseUnnamedType()) return true; break;
 197     case lltok::LocalVar:   if (ParseNamedType()) return true; break;
 198     case lltok::GlobalID:   if (ParseUnnamedGlobal()) return true; break;
 199     case lltok::GlobalVar:  if (ParseNamedGlobal()) return true; break;
 200     case lltok::ComdatVar:  if (parseComdat()) return true; break;
 201     case lltok::exclaim:    if (ParseStandaloneMetadata()) return true; break;
 202     case lltok::MetadataVar:if (ParseNamedMetadata()) return true; break;
 203
 204     // The Global variable production with no name can have many different
 205     // optional leading prefixes, the production is:
 206     // GlobalVar ::= OptionalLinkage OptionalVisibility OptionalDLLStorageClass
 207     //               OptionalThreadLocal OptionalAddrSpace OptionalUnNammedAddr
 208     //               ('constant'|'global') ...
 209     case lltok::kw_private:             // OptionalLinkage
 210     case lltok::kw_internal:            // OptionalLinkage
 211     case lltok::kw_weak:                // OptionalLinkage
 212     case lltok::kw_weak_odr:            // OptionalLinkage
 213     case lltok::kw_linkonce:            // OptionalLinkage
 214     case lltok::kw_linkonce_odr:        // OptionalLinkage
 215     case lltok::kw_appending:           // OptionalLinkage
 216     case lltok::kw_common:              // OptionalLinkage
 217     case lltok::kw_extern_weak:         // OptionalLinkage
 218     case lltok::kw_external:            // OptionalLinkage
 219     case lltok::kw_default:             // OptionalVisibility
 220     case lltok::kw_hidden:              // OptionalVisibility
 221     case lltok::kw_protected:           // OptionalVisibility
 222     case lltok::kw_dllimport:           // OptionalDLLStorageClass
 223     case lltok::kw_dllexport:           // OptionalDLLStorageClass
 224     case lltok::kw_thread_local:        // OptionalThreadLocal
 225     case lltok::kw_addrspace:           // OptionalAddrSpace
 226     case lltok::kw_constant:            // GlobalType
 227     case lltok::kw_global: {            // GlobalType
 228       unsigned Linkage, Visibility, DLLStorageClass;
 229       bool UnnamedAddr;
 230       GlobalVariable::ThreadLocalMode TLM;
 231       bool HasLinkage;
 232       if (ParseOptionalLinkage(Linkage, HasLinkage) ||
 233           ParseOptionalVisibility(Visibility) ||
 234           ParseOptionalDLLStorageClass(DLLStorageClass) ||
 235           ParseOptionalThreadLocal(TLM) ||
 236           parseOptionalUnnamedAddr(UnnamedAddr) ||
 237           ParseGlobal("", SMLoc(), Linkage, HasLinkage, Visibility,
 238                       DLLStorageClass, TLM, UnnamedAddr))
 239         return true;
 240       break;
 241     }
 242
 243     case lltok::kw_attributes: if (ParseUnnamedAttrGrp()) return true; break;
 244     case lltok::kw_uselistorder: if (ParseUseListOrder()) return true; break;
 245     case lltok::kw_uselistorder_bb:
 246                                  if (ParseUseListOrderBB()) return true; break;
 247     }
 248   }
 249 }
 250
 251
 252 /// toplevelentity
 253 ///   ::= 'module' 'asm' STRINGCONSTANT
 254 bool LLParser::ParseModuleAsm() {
 255   assert(Lex.getKind() == lltok::kw_module);
 256   Lex.Lex();
 257
 258   std::string AsmStr;
 259   if (ParseToken(lltok::kw_asm, "expected 'module asm'") ||
 260       ParseStringConstant(AsmStr)) return true;
 261
 262   M->appendModuleInlineAsm(AsmStr);
 263   return false;
 264 }
 265
 266 /// toplevelentity
 267 ///   ::= 'target' 'triple' '=' STRINGCONSTANT
 268 ///   ::= 'target' 'datalayout' '=' STRINGCONSTANT
 269 bool LLParser::ParseTargetDefinition() {
 270   assert(Lex.getKind() == lltok::kw_target);
 271   std::string Str;
 272   switch (Lex.Lex()) {
 273   default: return TokError("unknown target property");
 274   case lltok::kw_triple:
 275     Lex.Lex();
 276     if (ParseToken(lltok::equal, "expected '=' after target triple") ||
 277         ParseStringConstant(Str))
 278       return true;
 279     M->setTargetTriple(Str);
 280     return false;
 281   case lltok::kw_datalayout:
 282     Lex.Lex();
 283     if (ParseToken(lltok::equal, "expected '=' after target datalayout") ||
 284         ParseStringConstant(Str))
 285       return true;
 286     M->setDataLayout(Str);
 287     return false;
 288   }
 289 }
 290
 291 /// toplevelentity
 292 ///   ::= 'deplibs' '=' '[' ']'
 293 ///   ::= 'deplibs' '=' '[' STRINGCONSTANT (',' STRINGCONSTANT)* ']'
 294 /// FIXME: Remove in 4.0. Currently parse, but ignore.
 295 bool LLParser::ParseDepLibs() {
 296   assert(Lex.getKind() == lltok::kw_deplibs);
 297   Lex.Lex();
 298   if (ParseToken(lltok::equal, "expected '=' after deplibs") ||
 299       ParseToken(lltok::lsquare, "expected '=' after deplibs"))
 300     return true;
 301
 302   if (EatIfPresent(lltok::rsquare))
 303     return false;
 304
 305   do {
 306     std::string Str;
 307     if (ParseStringConstant(Str)) return true;
 308   } while (EatIfPresent(lltok::comma));
 309
 310   return ParseToken(lltok::rsquare, "expected ']' at end of list");
 311 }
 312
 313 /// ParseUnnamedType:
 314 ///   ::= LocalVarID '=' 'type' type
 315 bool LLParser::ParseUnnamedType() {
 316   LocTy TypeLoc = Lex.getLoc();
 317   unsigned TypeID = Lex.getUIntVal();
 318   Lex.Lex(); // eat LocalVarID;
 319
 320   if (ParseToken(lltok::equal, "expected '=' after name") ||
 321       ParseToken(lltok::kw_type, "expected 'type' after '='"))
 322     return true;
 323
 324   if (TypeID >= NumberedTypes.size())
 325     NumberedTypes.resize(TypeID+1);
 326
 327   Type *Result = nullptr;
 328   if (ParseStructDefinition(TypeLoc, "",
 329                             NumberedTypes[TypeID], Result)) return true;
 330
 331   if (!isa<StructType>(Result)) {
 332     std::pair<Type*, LocTy> &Entry = NumberedTypes[TypeID];
 333     if (Entry.first)
 334       return Error(TypeLoc, "non-struct types may not be recursive");
 335     Entry.first = Result;
 336     Entry.second = SMLoc();
 337   }
 338
 339   return false;
 340 }
 341
 342
 343 /// toplevelentity
 344 ///   ::= LocalVar '=' 'type' type
 345 bool LLParser::ParseNamedType() {
 346   std::string Name = Lex.getStrVal();
 347   LocTy NameLoc = Lex.getLoc();
 348   Lex.Lex();  // eat LocalVar.
 349
 350   if (ParseToken(lltok::equal, "expected '=' after name") ||
 351       ParseToken(lltok::kw_type, "expected 'type' after name"))
 352     return true;
 353
 354   Type *Result = nullptr;
 355   if (ParseStructDefinition(NameLoc, Name,
 356                             NamedTypes[Name], Result)) return true;
 357
 358   if (!isa<StructType>(Result)) {
 359     std::pair<Type*, LocTy> &Entry = NamedTypes[Name];
 360     if (Entry.first)
 361       return Error(NameLoc, "non-struct types may not be recursive");
 362     Entry.first = Result;
 363     Entry.second = SMLoc();
 364   }
 365
 366   return false;
 367 }
 368
 369
 370 /// toplevelentity
 371 ///   ::= 'declare' FunctionHeader
 372 bool LLParser::ParseDeclare() {
 373   assert(Lex.getKind() == lltok::kw_declare);
 374   Lex.Lex();
 375
 376   Function *F;
 377   return ParseFunctionHeader(F, false);
 378 }
 379
 380 /// toplevelentity
 381 ///   ::= 'define' FunctionHeader '{' ...
 382 bool LLParser::ParseDefine() {
 383   assert(Lex.getKind() == lltok::kw_define);
 384   Lex.Lex();
 385
 386   Function *F;
 387   return ParseFunctionHeader(F, true) ||
 388          ParseFunctionBody(*F);
 389 }
 390
 391 /// ParseGlobalType
 392 ///   ::= 'constant'
 393 ///   ::= 'global'
 394 bool LLParser::ParseGlobalType(bool &IsConstant) {
 395   if (Lex.getKind() == lltok::kw_constant)
 396     IsConstant = true;
 397   else if (Lex.getKind() == lltok::kw_global)
 398     IsConstant = false;
 399   else {
 400     IsConstant = false;
 401     return TokError("expected 'global' or 'constant'");
 402   }
 403   Lex.Lex();
 404   return false;
 405 }
 406
 407 /// ParseUnnamedGlobal:
 408 ///   OptionalVisibility ALIAS ...
 409 ///   OptionalLinkage OptionalVisibility OptionalDLLStorageClass
 410 ///                                                     ...   -> global variable
 411 ///   GlobalID '=' OptionalVisibility ALIAS ...
 412 ///   GlobalID '=' OptionalLinkage OptionalVisibility OptionalDLLStorageClass
 413 ///                                                     ...   -> global variable
 414 bool LLParser::ParseUnnamedGlobal() {
 415   unsigned VarID = NumberedVals.size();
 416   std::string Name;
 417   LocTy NameLoc = Lex.getLoc();
 418
 419   // Handle the GlobalID form.
 420   if (Lex.getKind() == lltok::GlobalID) {
 421     if (Lex.getUIntVal() != VarID)
 422       return Error(Lex.getLoc(), "variable expected to be numbered '%" +
 423                    Twine(VarID) + "'");
 424     Lex.Lex(); // eat GlobalID;
 425
 426     if (ParseToken(lltok::equal, "expected '=' after name"))
 427       return true;
 428   }
 429
 430   bool HasLinkage;
 431   unsigned Linkage, Visibility, DLLStorageClass;
 432   GlobalVariable::ThreadLocalMode TLM;
 433   bool UnnamedAddr;
 434   if (ParseOptionalLinkage(Linkage, HasLinkage) ||
 435       ParseOptionalVisibility(Visibility) ||
 436       ParseOptionalDLLStorageClass(DLLStorageClass) ||
 437       ParseOptionalThreadLocal(TLM) ||
 438       parseOptionalUnnamedAddr(UnnamedAddr))
 439     return true;
 440
 441   if (Lex.getKind() != lltok::kw_alias)
 442     return ParseGlobal(Name, NameLoc, Linkage, HasLinkage, Visibility,
 443                        DLLStorageClass, TLM, UnnamedAddr);
 444   return ParseAlias(Name, NameLoc, Linkage, Visibility, DLLStorageClass, TLM,
 445                     UnnamedAddr);
 446 }
 447
 448 /// ParseNamedGlobal:
 449 ///   GlobalVar '=' OptionalVisibility ALIAS ...
 450 ///   GlobalVar '=' OptionalLinkage OptionalVisibility OptionalDLLStorageClass
 451 ///                                                     ...   -> global variable
 452 bool LLParser::ParseNamedGlobal() {
 453   assert(Lex.getKind() == lltok::GlobalVar);
 454   LocTy NameLoc = Lex.getLoc();
 455   std::string Name = Lex.getStrVal();
 456   Lex.Lex();
 457
 458   bool HasLinkage;
 459   unsigned Linkage, Visibility, DLLStorageClass;
 460   GlobalVariable::ThreadLocalMode TLM;
 461   bool UnnamedAddr;
 462   if (ParseToken(lltok::equal, "expected '=' in global variable") ||
 463       ParseOptionalLinkage(Linkage, HasLinkage) ||
 464       ParseOptionalVisibility(Visibility) ||
 465       ParseOptionalDLLStorageClass(DLLStorageClass) ||
 466       ParseOptionalThreadLocal(TLM) ||
 467       parseOptionalUnnamedAddr(UnnamedAddr))
 468     return true;
 469
 470   if (Lex.getKind() != lltok::kw_alias)
 471     return ParseGlobal(Name, NameLoc, Linkage, HasLinkage, Visibility,
 472                        DLLStorageClass, TLM, UnnamedAddr);
 473
 474   return ParseAlias(Name, NameLoc, Linkage, Visibility, DLLStorageClass, TLM,
 475                     UnnamedAddr);
 476 }
 477
 478 bool LLParser::parseComdat() {
 479   assert(Lex.getKind() == lltok::ComdatVar);
 480   std::string Name = Lex.getStrVal();
 481   LocTy NameLoc = Lex.getLoc();
 482   Lex.Lex();
 483
 484   if (ParseToken(lltok::equal, "expected '=' here"))
 485     return true;
 486
 487   if (ParseToken(lltok::kw_comdat, "expected comdat keyword"))
 488     return TokError("expected comdat type");
 489
 490   Comdat::SelectionKind SK;
 491   switch (Lex.getKind()) {
 492   default:
 493     return TokError("unknown selection kind");
 494   case lltok::kw_any:
 495     SK = Comdat::Any;
 496     break;
 497   case lltok::kw_exactmatch:
 498     SK = Comdat::ExactMatch;
 499     break;
 500   case lltok::kw_largest:
 501     SK = Comdat::Largest;
 502     break;
 503   case lltok::kw_noduplicates:
 504     SK = Comdat::NoDuplicates;
 505     break;
 506   case lltok::kw_samesize:
 507     SK = Comdat::SameSize;
 508     break;
 509   }
 510   Lex.Lex();
 511
 512   // See if the comdat was forward referenced, if so, use the comdat.
 513   Module::ComdatSymTabType &ComdatSymTab = M->getComdatSymbolTable();
 514   Module::ComdatSymTabType::iterator I = ComdatSymTab.find(Name);
 515   if (I != ComdatSymTab.end() && !ForwardRefComdats.erase(Name))
 516     return Error(NameLoc, "redefinition of comdat '$" + Name + "'");
 517
 518   Comdat *C;
 519   if (I != ComdatSymTab.end())
 520     C = &I->second;
 521   else
 522     C = M->getOrInsertComdat(Name);
 523   C->setSelectionKind(SK);
 524
 525   return false;
 526 }
 527
 528 // MDString:
 529 //   ::= '!' STRINGCONSTANT
 530 bool LLParser::ParseMDString(MDString *&Result) {
 531   std::string Str;
 532   if (ParseStringConstant(Str)) return true;
 533   llvm::UpgradeMDStringConstant(Str);
 534   Result = MDString::get(Context, Str);
 535   return false;
 536 }
 537
 538 // MDNode:
 539 //   ::= '!' MDNodeNumber
 540 //
 541 /// This version of ParseMDNodeID returns the slot number and null in the case
 542 /// of a forward reference.
 543 bool LLParser::ParseMDNodeID(MDNode *&Result, unsigned &SlotNo) {
 544   // !{ ..., !42, ... }
 545   if (ParseUInt32(SlotNo)) return true;
 546
 547   // Check existing MDNode.
 548   if (SlotNo < NumberedMetadata.size() && NumberedMetadata[SlotNo] != nullptr)
 549     Result = NumberedMetadata[SlotNo];
 550   else
 551     Result = nullptr;
 552   return false;
 553 }
 554
 555 bool LLParser::ParseMDNodeID(MDNode *&Result) {
 556   // !{ ..., !42, ... }
 557   unsigned MID = 0;
 558   if (ParseMDNodeID(Result, MID)) return true;
 559
 560   // If not a forward reference, just return it now.
 561   if (Result) return false;
 562
 563   // Otherwise, create MDNode forward reference.
 564   MDNode *FwdNode = MDNode::getTemporary(Context, None);
 565   ForwardRefMDNodes[MID] = std::make_pair(FwdNode, Lex.getLoc());
 566
 567   if (NumberedMetadata.size() <= MID)
 568     NumberedMetadata.resize(MID+1);
 569   NumberedMetadata[MID] = FwdNode;
 570   Result = FwdNode;
 571   return false;
 572 }
 573
 574 /// ParseNamedMetadata:
 575 ///   !foo = !{ !1, !2 }
 576 bool LLParser::ParseNamedMetadata() {
 577   assert(Lex.getKind() == lltok::MetadataVar);
 578   std::string Name = Lex.getStrVal();
 579   Lex.Lex();
 580
 581   if (ParseToken(lltok::equal, "expected '=' here") ||
 582       ParseToken(lltok::exclaim, "Expected '!' here") ||
 583       ParseToken(lltok::lbrace, "Expected '{' here"))
 584     return true;
 585
 586   NamedMDNode *NMD = M->getOrInsertNamedMetadata(Name);
 587   if (Lex.getKind() != lltok::rbrace)
 588     do {
 589       if (ParseToken(lltok::exclaim, "Expected '!' here"))
 590         return true;
 591
 592       MDNode *N = nullptr;
 593       if (ParseMDNodeID(N)) return true;
 594       NMD->addOperand(N);
 595     } while (EatIfPresent(lltok::comma));
 596
 597   if (ParseToken(lltok::rbrace, "expected end of metadata node"))
 598     return true;
 599
 600   return false;
 601 }
 602
 603 /// ParseStandaloneMetadata:
 604 ///   !42 = !{...}
 605 bool LLParser::ParseStandaloneMetadata() {
 606   assert(Lex.getKind() == lltok::exclaim);
 607   Lex.Lex();
 608   unsigned MetadataID = 0;
 609
 610   LocTy TyLoc;
 611   Type *Ty = nullptr;
 612   SmallVector<Value *, 16> Elts;
 613   if (ParseUInt32(MetadataID) ||
 614       ParseToken(lltok::equal, "expected '=' here") ||
 615       ParseType(Ty, TyLoc) ||
 616       ParseToken(lltok::exclaim, "Expected '!' here") ||
 617       ParseToken(lltok::lbrace, "Expected '{' here") ||
 618       ParseMDNodeVector(Elts, nullptr) ||
 619       ParseToken(lltok::rbrace, "expected end of metadata node"))
 620     return true;
 621
 622   MDNode *Init = MDNode::get(Context, Elts);
 623
 624   // See if this was forward referenced, if so, handle it.
 625   std::map<unsigned, std::pair<TrackingVH<MDNode>, LocTy> >::iterator
 626     FI = ForwardRefMDNodes.find(MetadataID);
 627   if (FI != ForwardRefMDNodes.end()) {
 628     MDNode *Temp = FI->second.first;
 629     Temp->replaceAllUsesWith(Init);
 630     MDNode::deleteTemporary(Temp);
 631     ForwardRefMDNodes.erase(FI);
 632
 633     assert(NumberedMetadata[MetadataID] == Init && "Tracking VH didn't work");
 634   } else {
 635     if (MetadataID >= NumberedMetadata.size())
 636       NumberedMetadata.resize(MetadataID+1);
 637
 638     if (NumberedMetadata[MetadataID] != nullptr)
 639       return TokError("Metadata id is already used");
 640     NumberedMetadata[MetadataID] = Init;
 641   }
 642
 643   return false;
 644 }
 645
 646 static bool isValidVisibilityForLinkage(unsigned V, unsigned L) {
 647   return !GlobalValue::isLocalLinkage((GlobalValue::LinkageTypes)L) ||
 648          (GlobalValue::VisibilityTypes)V == GlobalValue::DefaultVisibility;
 649 }
 650
 651 /// ParseAlias:
 652 ///   ::= GlobalVar '=' OptionalLinkage OptionalVisibility
 653 ///                     OptionalDLLStorageClass OptionalThreadLocal
 654 ///                     OptionalUnNammedAddr 'alias' Aliasee
 655 ///
 656 /// Aliasee
 657 ///   ::= TypeAndValue
 658 ///
 659 /// Everything through OptionalUnNammedAddr has already been parsed.
 660 ///
 661 bool LLParser::ParseAlias(const std::string &Name, LocTy NameLoc, unsigned L,
 662                           unsigned Visibility, unsigned DLLStorageClass,
 663                           GlobalVariable::ThreadLocalMode TLM,
 664                           bool UnnamedAddr) {
 665   assert(Lex.getKind() == lltok::kw_alias);
 666   Lex.Lex();
 667
 668   GlobalValue::LinkageTypes Linkage = (GlobalValue::LinkageTypes) L;
 669
 670   if(!GlobalAlias::isValidLinkage(Linkage))
 671     return Error(NameLoc, "invalid linkage type for alias");
 672
 673   if (!isValidVisibilityForLinkage(Visibility, L))
 674     return Error(NameLoc,
 675                  "symbol with local linkage must have default visibility");
 676
 677   Constant *Aliasee;
 678   LocTy AliaseeLoc = Lex.getLoc();
 679   if (Lex.getKind() != lltok::kw_bitcast &&
 680       Lex.getKind() != lltok::kw_getelementptr &&
 681       Lex.getKind() != lltok::kw_addrspacecast &&
 682       Lex.getKind() != lltok::kw_inttoptr) {
 683     if (ParseGlobalTypeAndValue(Aliasee))
 684       return true;
 685   } else {
 686     // The bitcast dest type is not present, it is implied by the dest type.
 687     ValID ID;
 688     if (ParseValID(ID))
 689       return true;
 690     if (ID.Kind != ValID::t_Constant)
 691       return Error(AliaseeLoc, "invalid aliasee");
 692     Aliasee = ID.ConstantVal;
 693   }
 694
 695   Type *AliaseeType = Aliasee->getType();
 696   auto *PTy = dyn_cast<PointerType>(AliaseeType);
 697   if (!PTy)
 698     return Error(AliaseeLoc, "An alias must have pointer type");
 699   Type *Ty = PTy->getElementType();
 700   unsigned AddrSpace = PTy->getAddressSpace();
 701
 702   // Okay, create the alias but do not insert it into the module yet.
 703   std::unique_ptr<GlobalAlias> GA(
 704       GlobalAlias::create(Ty, AddrSpace, (GlobalValue::LinkageTypes)Linkage,
 705                           Name, Aliasee, /*Parent*/ nullptr));
 706   GA->setThreadLocalMode(TLM);
 707   GA->setVisibility((GlobalValue::VisibilityTypes)Visibility);
 708   GA->setDLLStorageClass((GlobalValue::DLLStorageClassTypes)DLLStorageClass);
 709   GA->setUnnamedAddr(UnnamedAddr);
 710
 711   // See if this value already exists in the symbol table.  If so, it is either
 712   // a redefinition or a definition of a forward reference.
 713   if (GlobalValue *Val = M->getNamedValue(Name)) {
 714     // See if this was a redefinition.  If so, there is no entry in
 715     // ForwardRefVals.
 716     std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator
 717       I = ForwardRefVals.find(Name);
 718     if (I == ForwardRefVals.end())
 719       return Error(NameLoc, "redefinition of global named '@" + Name + "'");
 720
 721     // Otherwise, this was a definition of forward ref.  Verify that types
 722     // agree.
 723     if (Val->getType() != GA->getType())
 724       return Error(NameLoc,
 725               "forward reference and definition of alias have different types");
 726
 727     // If they agree, just RAUW the old value with the alias and remove the
 728     // forward ref info.
 729     Val->replaceAllUsesWith(GA.get());
 730     Val->eraseFromParent();
 731     ForwardRefVals.erase(I);
 732   }
 733
 734   // Insert into the module, we know its name won't collide now.
 735   M->getAliasList().push_back(GA.get());
 736   assert(GA->getName() == Name && "Should not be a name conflict!");
 737
 738   // The module owns this now
 739   GA.release();
 740
 741   return false;
 742 }
 743
 744 /// ParseGlobal
 745 ///   ::= GlobalVar '=' OptionalLinkage OptionalVisibility OptionalDLLStorageClass
 746 ///       OptionalThreadLocal OptionalUnNammedAddr OptionalAddrSpace
 747 ///       OptionalExternallyInitialized GlobalType Type Const
 748 ///   ::= OptionalLinkage OptionalVisibility OptionalDLLStorageClass
 749 ///       OptionalThreadLocal OptionalUnNammedAddr OptionalAddrSpace
 750 ///       OptionalExternallyInitialized GlobalType Type Const
 751 ///
 752 /// Everything up to and including OptionalUnNammedAddr has been parsed
 753 /// already.
 754 ///
 755 bool LLParser::ParseGlobal(const std::string &Name, LocTy NameLoc,
 756                            unsigned Linkage, bool HasLinkage,
 757                            unsigned Visibility, unsigned DLLStorageClass,
 758                            GlobalVariable::ThreadLocalMode TLM,
 759                            bool UnnamedAddr) {
 760   if (!isValidVisibilityForLinkage(Visibility, Linkage))
 761     return Error(NameLoc,
 762                  "symbol with local linkage must have default visibility");
 763
 764   unsigned AddrSpace;
 765   bool IsConstant, IsExternallyInitialized;
 766   LocTy IsExternallyInitializedLoc;
 767   LocTy TyLoc;
 768
 769   Type *Ty = nullptr;
 770   if (ParseOptionalAddrSpace(AddrSpace) ||
 771       ParseOptionalToken(lltok::kw_externally_initialized,
 772                          IsExternallyInitialized,
 773                          &IsExternallyInitializedLoc) ||
 774       ParseGlobalType(IsConstant) ||
 775       ParseType(Ty, TyLoc))
 776     return true;
 777
 778   // If the linkage is specified and is external, then no initializer is
 779   // present.
 780   Constant *Init = nullptr;
 781   if (!HasLinkage || (Linkage != GlobalValue::ExternalWeakLinkage &&
 782                       Linkage != GlobalValue::ExternalLinkage)) {
 783     if (ParseGlobalValue(Ty, Init))
 784       return true;
 785   }
 786
 787   if (Ty->isFunctionTy() || Ty->isLabelTy())
 788     return Error(TyLoc, "invalid type for global variable");
 789
 790   GlobalVariable *GV = nullptr;
 791
 792   // See if the global was forward referenced, if so, use the global.
 793   if (!Name.empty()) {
 794     if (GlobalValue *GVal = M->getNamedValue(Name)) {
 795       if (!ForwardRefVals.erase(Name) || !isa<GlobalValue>(GVal))
 796         return Error(NameLoc, "redefinition of global '@" + Name + "'");
 797       GV = cast<GlobalVariable>(GVal);
 798     }
 799   } else {
 800     std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator
 801       I = ForwardRefValIDs.find(NumberedVals.size());
 802     if (I != ForwardRefValIDs.end()) {
 803       GV = cast<GlobalVariable>(I->second.first);
 804       ForwardRefValIDs.erase(I);
 805     }
 806   }
 807
 808   if (!GV) {
 809     GV = new GlobalVariable(*M, Ty, false, GlobalValue::ExternalLinkage, nullptr,
 810                             Name, nullptr, GlobalVariable::NotThreadLocal,
 811                             AddrSpace);
 812   } else {
 813     if (GV->getType()->getElementType() != Ty)
 814       return Error(TyLoc,
 815             "forward reference and definition of global have different types");
 816
 817     // Move the forward-reference to the correct spot in the module.
 818     M->getGlobalList().splice(M->global_end(), M->getGlobalList(), GV);
 819   }
 820
 821   if (Name.empty())
 822     NumberedVals.push_back(GV);
 823
 824   // Set the parsed properties on the global.
 825   if (Init)
 826     GV->setInitializer(Init);
 827   GV->setConstant(IsConstant);
 828   GV->setLinkage((GlobalValue::LinkageTypes)Linkage);
 829   GV->setVisibility((GlobalValue::VisibilityTypes)Visibility);
 830   GV->setDLLStorageClass((GlobalValue::DLLStorageClassTypes)DLLStorageClass);
 831   GV->setExternallyInitialized(IsExternallyInitialized);
 832   GV->setThreadLocalMode(TLM);
 833   GV->setUnnamedAddr(UnnamedAddr);
 834
 835   // Parse attributes on the global.
 836   while (Lex.getKind() == lltok::comma) {
 837     Lex.Lex();
 838
 839     if (Lex.getKind() == lltok::kw_section) {
 840       Lex.Lex();
 841       GV->setSection(Lex.getStrVal());
 842       if (ParseToken(lltok::StringConstant, "expected global section string"))
 843         return true;
 844     } else if (Lex.getKind() == lltok::kw_align) {
 845       unsigned Alignment;
 846       if (ParseOptionalAlignment(Alignment)) return true;
 847       GV->setAlignment(Alignment);
 848     } else {
 849       Comdat *C;
 850       if (parseOptionalComdat(C))
 851         return true;
 852       if (C)
 853         GV->setComdat(C);
 854       else
 855         return TokError("unknown global variable property!");
 856     }
 857   }
 858
 859   return false;
 860 }
 861
 862 /// ParseUnnamedAttrGrp
 863 ///   ::= 'attributes' AttrGrpID '=' '{' AttrValPair+ '}'
 864 bool LLParser::ParseUnnamedAttrGrp() {
 865   assert(Lex.getKind() == lltok::kw_attributes);
 866   LocTy AttrGrpLoc = Lex.getLoc();
 867   Lex.Lex();
 868
 869   assert(Lex.getKind() == lltok::AttrGrpID);
 870   unsigned VarID = Lex.getUIntVal();
 871   std::vector<unsigned> unused;
 872   LocTy BuiltinLoc;
 873   Lex.Lex();
 874
 875   if (ParseToken(lltok::equal, "expected '=' here") ||
 876       ParseToken(lltok::lbrace, "expected '{' here") ||
 877       ParseFnAttributeValuePairs(NumberedAttrBuilders[VarID], unused, true,
 878                                  BuiltinLoc) ||
 879       ParseToken(lltok::rbrace, "expected end of attribute group"))
 880     return true;
 881
 882   if (!NumberedAttrBuilders[VarID].hasAttributes())
 883     return Error(AttrGrpLoc, "attribute group has no attributes");
 884
 885   return false;
 886 }
 887
 888 /// ParseFnAttributeValuePairs
 889 ///   ::= <attr> | <attr> '=' <value>
 890 bool LLParser::ParseFnAttributeValuePairs(AttrBuilder &B,
 891                                           std::vector<unsigned> &FwdRefAttrGrps,
 892                                           bool inAttrGrp, LocTy &BuiltinLoc) {
 893   bool HaveError = false;
 894
 895   B.clear();
 896
 897   while (true) {
 898     lltok::Kind Token = Lex.getKind();
 899     if (Token == lltok::kw_builtin)
 900       BuiltinLoc = Lex.getLoc();
 901     switch (Token) {
 902     default:
 903       if (!inAttrGrp) return HaveError;
 904       return Error(Lex.getLoc(), "unterminated attribute group");
 905     case lltok::rbrace:
 906       // Finished.
 907       return false;
 908
 909     case lltok::AttrGrpID: {
 910       // Allow a function to reference an attribute group:
 911       //
 912       //   define void @foo() #1 { ... }
 913       if (inAttrGrp)
 914         HaveError |=
 915           Error(Lex.getLoc(),
 916               "cannot have an attribute group reference in an attribute group");
 917
 918       unsigned AttrGrpNum = Lex.getUIntVal();
 919       if (inAttrGrp) break;
 920
 921       // Save the reference to the attribute group. We'll fill it in later.
 922       FwdRefAttrGrps.push_back(AttrGrpNum);
 923       break;
 924     }
 925     // Target-dependent attributes:
 926     case lltok::StringConstant: {
 927       std::string Attr = Lex.getStrVal();
 928       Lex.Lex();
 929       std::string Val;
 930       if (EatIfPresent(lltok::equal) &&
 931           ParseStringConstant(Val))
 932         return true;
 933
 934       B.addAttribute(Attr, Val);
 935       continue;
 936     }
 937
 938     // Target-independent attributes:
 939     case lltok::kw_align: {
 940       // As a hack, we allow function alignment to be initially parsed as an
 941       // attribute on a function declaration/definition or added to an attribute
 942       // group and later moved to the alignment field.
 943       unsigned Alignment;
 944       if (inAttrGrp) {
 945         Lex.Lex();
 946         if (ParseToken(lltok::equal, "expected '=' here") ||
 947             ParseUInt32(Alignment))
 948           return true;
 949       } else {
 950         if (ParseOptionalAlignment(Alignment))
 951           return true;
 952       }
 953       B.addAlignmentAttr(Alignment);
 954       continue;
 955     }
 956     case lltok::kw_alignstack: {
 957       unsigned Alignment;
 958       if (inAttrGrp) {
 959         Lex.Lex();
 960         if (ParseToken(lltok::equal, "expected '=' here") ||
 961             ParseUInt32(Alignment))
 962           return true;
 963       } else {
 964         if (ParseOptionalStackAlignment(Alignment))
 965           return true;
 966       }
 967       B.addStackAlignmentAttr(Alignment);
 968       continue;
 969     }
 970     case lltok::kw_alwaysinline:      B.addAttribute(Attribute::AlwaysInline); break;
 971     case lltok::kw_builtin:           B.addAttribute(Attribute::Builtin); break;
 972     case lltok::kw_cold:              B.addAttribute(Attribute::Cold); break;
 973     case lltok::kw_inlinehint:        B.addAttribute(Attribute::InlineHint); break;
 974     case lltok::kw_jumptable:         B.addAttribute(Attribute::JumpTable); break;
 975     case lltok::kw_minsize:           B.addAttribute(Attribute::MinSize); break;
 976     case lltok::kw_naked:             B.addAttribute(Attribute::Naked); break;
 977     case lltok::kw_nobuiltin:         B.addAttribute(Attribute::NoBuiltin); break;
 978     case lltok::kw_noduplicate:       B.addAttribute(Attribute::NoDuplicate); break;
 979     case lltok::kw_noimplicitfloat:   B.addAttribute(Attribute::NoImplicitFloat); break;
 980     case lltok::kw_noinline:          B.addAttribute(Attribute::NoInline); break;
 981     case lltok::kw_nonlazybind:       B.addAttribute(Attribute::NonLazyBind); break;
 982     case lltok::kw_noredzone:         B.addAttribute(Attribute::NoRedZone); break;
 983     case lltok::kw_noreturn:          B.addAttribute(Attribute::NoReturn); break;
 984     case lltok::kw_nounwind:          B.addAttribute(Attribute::NoUnwind); break;
 985     case lltok::kw_optnone:           B.addAttribute(Attribute::OptimizeNone); break;
 986     case lltok::kw_optsize:           B.addAttribute(Attribute::OptimizeForSize); break;
 987     case lltok::kw_readnone:          B.addAttribute(Attribute::ReadNone); break;
 988     case lltok::kw_readonly:          B.addAttribute(Attribute::ReadOnly); break;
 989     case lltok::kw_returns_twice:     B.addAttribute(Attribute::ReturnsTwice); break;
 990     case lltok::kw_ssp:               B.addAttribute(Attribute::StackProtect); break;
 991     case lltok::kw_sspreq:            B.addAttribute(Attribute::StackProtectReq); break;
 992     case lltok::kw_sspstrong:         B.addAttribute(Attribute::StackProtectStrong); break;
 993     case lltok::kw_sanitize_address:  B.addAttribute(Attribute::SanitizeAddress); break;
 994     case lltok::kw_sanitize_thread:   B.addAttribute(Attribute::SanitizeThread); break;
 995     case lltok::kw_sanitize_memory:   B.addAttribute(Attribute::SanitizeMemory); break;
 996     case lltok::kw_uwtable:           B.addAttribute(Attribute::UWTable); break;
 997
 998     // Error handling.
 999     case lltok::kw_inreg:
1000     case lltok::kw_signext:
1001     case lltok::kw_zeroext:
1002       HaveError |=
1003         Error(Lex.getLoc(),
1004               "invalid use of attribute on a function");
1005       break;
1006     case lltok::kw_byval:
1007     case lltok::kw_dereferenceable:
1008     case lltok::kw_inalloca:
1009     case lltok::kw_nest:
1010     case lltok::kw_noalias:
1011     case lltok::kw_nocapture:
1012     case lltok::kw_nonnull:
1013     case lltok::kw_returned:
1014     case lltok::kw_sret:
1015       HaveError |=
1016         Error(Lex.getLoc(),
1017               "invalid use of parameter-only attribute on a function");
1018       break;
1019     }
1020
1021     Lex.Lex();
1022   }
1023 }
1024
1025 //===----------------------------------------------------------------------===//
1026 // GlobalValue Reference/Resolution Routines.
1027 //===----------------------------------------------------------------------===//
1028
1029 /// GetGlobalVal - Get a value with the specified name or ID, creating a
1030 /// forward reference record if needed.  This can return null if the value
1031 /// exists but does not have the right type.
1032 GlobalValue *LLParser::GetGlobalVal(const std::string &Name, Type *Ty,
1033                                     LocTy Loc) {
1034   PointerType *PTy = dyn_cast<PointerType>(Ty);
1035   if (!PTy) {
1036     Error(Loc, "global variable reference must have pointer type");
1037     return nullptr;
1038   }
1039
1040   // Look this name up in the normal function symbol table.
1041   GlobalValue *Val =
1042     cast_or_null<GlobalValue>(M->getValueSymbolTable().lookup(Name));
1043
1044   // If this is a forward reference for the value, see if we already created a
1045   // forward ref record.
1046   if (!Val) {
1047     std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator
1048       I = ForwardRefVals.find(Name);
1049     if (I != ForwardRefVals.end())
1050       Val = I->second.first;
1051   }
1052
1053   // If we have the value in the symbol table or fwd-ref table, return it.
1054   if (Val) {
1055     if (Val->getType() == Ty) return Val;
1056     Error(Loc, "'@" + Name + "' defined with type '" +
1057           getTypeString(Val->getType()) + "'");
1058     return nullptr;
1059   }
1060
1061   // Otherwise, create a new forward reference for this value and remember it.
1062   GlobalValue *FwdVal;
1063   if (FunctionType *FT = dyn_cast<FunctionType>(PTy->getElementType()))
1064     FwdVal = Function::Create(FT, GlobalValue::ExternalWeakLinkage, Name, M);
1065   else
1066     FwdVal = new GlobalVariable(*M, PTy->getElementType(), false,
1067                                 GlobalValue::ExternalWeakLinkage, nullptr, Name,
1068                                 nullptr, GlobalVariable::NotThreadLocal,
1069                                 PTy->getAddressSpace());
1070
1071   ForwardRefVals[Name] = std::make_pair(FwdVal, Loc);
1072   return FwdVal;
1073 }
1074
1075 GlobalValue *LLParser::GetGlobalVal(unsigned ID, Type *Ty, LocTy Loc) {
1076   PointerType *PTy = dyn_cast<PointerType>(Ty);
1077   if (!PTy) {
1078     Error(Loc, "global variable reference must have pointer type");
1079     return nullptr;
1080   }
1081
1082   GlobalValue *Val = ID < NumberedVals.size() ? NumberedVals[ID] : nullptr;
1083
1084   // If this is a forward reference for the value, see if we already created a
1085   // forward ref record.
1086   if (!Val) {
1087     std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator
1088       I = ForwardRefValIDs.find(ID);
1089     if (I != ForwardRefValIDs.end())
1090       Val = I->second.first;
1091   }
1092
1093   // If we have the value in the symbol table or fwd-ref table, return it.
1094   if (Val) {
1095     if (Val->getType() == Ty) return Val;
1096     Error(Loc, "'@" + Twine(ID) + "' defined with type '" +
1097           getTypeString(Val->getType()) + "'");
1098     return nullptr;
1099   }
1100
1101   // Otherwise, create a new forward reference for this value and remember it.
1102   GlobalValue *FwdVal;
1103   if (FunctionType *FT = dyn_cast<FunctionType>(PTy->getElementType()))
1104     FwdVal = Function::Create(FT, GlobalValue::ExternalWeakLinkage, "", M);
1105   else
1106     FwdVal = new GlobalVariable(*M, PTy->getElementType(), false,
1107                                 GlobalValue::ExternalWeakLinkage, nullptr, "");
1108
1109   ForwardRefValIDs[ID] = std::make_pair(FwdVal, Loc);
1110   return FwdVal;
1111 }
1112
1113
1114 //===----------------------------------------------------------------------===//
1115 // Comdat Reference/Resolution Routines.
1116 //===----------------------------------------------------------------------===//
1117
1118 Comdat *LLParser::getComdat(const std::string &Name, LocTy Loc) {
1119   // Look this name up in the comdat symbol table.
1120   Module::ComdatSymTabType &ComdatSymTab = M->getComdatSymbolTable();
1121   Module::ComdatSymTabType::iterator I = ComdatSymTab.find(Name);
1122   if (I != ComdatSymTab.end())
1123     return &I->second;
1124
1125   // Otherwise, create a new forward reference for this value and remember it.
1126   Comdat *C = M->getOrInsertComdat(Name);
1127   ForwardRefComdats[Name] = Loc;
1128   return C;
1129 }
1130
1131
1132 //===----------------------------------------------------------------------===//
1133 // Helper Routines.
1134 //===----------------------------------------------------------------------===//
1135
1136 /// ParseToken - If the current token has the specified kind, eat it and return
1137 /// success.  Otherwise, emit the specified error and return failure.
1138 bool LLParser::ParseToken(lltok::Kind T, const char *ErrMsg) {
1139   if (Lex.getKind() != T)
1140     return TokError(ErrMsg);
1141   Lex.Lex();
1142   return false;
1143 }
1144
1145 /// ParseStringConstant
1146 ///   ::= StringConstant
1147 bool LLParser::ParseStringConstant(std::string &Result) {
1148   if (Lex.getKind() != lltok::StringConstant)
1149     return TokError("expected string constant");
1150   Result = Lex.getStrVal();
1151   Lex.Lex();
1152   return false;
1153 }
1154
1155 /// ParseUInt32
1156 ///   ::= uint32
1157 bool LLParser::ParseUInt32(unsigned &Val) {
1158   if (Lex.getKind() != lltok::APSInt || Lex.getAPSIntVal().isSigned())
1159     return TokError("expected integer");
1160   uint64_t Val64 = Lex.getAPSIntVal().getLimitedValue(0xFFFFFFFFULL+1);
1161   if (Val64 != unsigned(Val64))
1162     return TokError("expected 32-bit integer (too large)");
1163   Val = Val64;
1164   Lex.Lex();
1165   return false;
1166 }
1167
1168 /// ParseUInt64
1169 ///   ::= uint64
1170 bool LLParser::ParseUInt64(uint64_t &Val) {
1171   if (Lex.getKind() != lltok::APSInt || Lex.getAPSIntVal().isSigned())
1172     return TokError("expected integer");
1173   Val = Lex.getAPSIntVal().getLimitedValue();
1174   Lex.Lex();
1175   return false;
1176 }
1177
1178 /// ParseTLSModel
1179 ///   := 'localdynamic'
1180 ///   := 'initialexec'
1181 ///   := 'localexec'
1182 bool LLParser::ParseTLSModel(GlobalVariable::ThreadLocalMode &TLM) {
1183   switch (Lex.getKind()) {
1184     default:
1185       return TokError("expected localdynamic, initialexec or localexec");
1186     case lltok::kw_localdynamic:
1187       TLM = GlobalVariable::LocalDynamicTLSModel;
1188       break;
1189     case lltok::kw_initialexec:
1190       TLM = GlobalVariable::InitialExecTLSModel;
1191       break;
1192     case lltok::kw_localexec:
1193       TLM = GlobalVariable::LocalExecTLSModel;
1194       break;
1195   }
1196
1197   Lex.Lex();
1198   return false;
1199 }
1200
1201 /// ParseOptionalThreadLocal
1202 ///   := /*empty*/
1203 ///   := 'thread_local'
1204 ///   := 'thread_local' '(' tlsmodel ')'
1205 bool LLParser::ParseOptionalThreadLocal(GlobalVariable::ThreadLocalMode &TLM) {
1206   TLM = GlobalVariable::NotThreadLocal;
1207   if (!EatIfPresent(lltok::kw_thread_local))
1208     return false;
1209
1210   TLM = GlobalVariable::GeneralDynamicTLSModel;
1211   if (Lex.getKind() == lltok::lparen) {
1212     Lex.Lex();
1213     return ParseTLSModel(TLM) ||
1214       ParseToken(lltok::rparen, "expected ')' after thread local model");
1215   }
1216   return false;
1217 }
1218
1219 /// ParseOptionalAddrSpace
1220 ///   := /*empty*/
1221 ///   := 'addrspace' '(' uint32 ')'
1222 bool LLParser::ParseOptionalAddrSpace(unsigned &AddrSpace) {
1223   AddrSpace = 0;
1224   if (!EatIfPresent(lltok::kw_addrspace))
1225     return false;
1226   return ParseToken(lltok::lparen, "expected '(' in address space") ||
1227          ParseUInt32(AddrSpace) ||
1228          ParseToken(lltok::rparen, "expected ')' in address space");
1229 }
1230
1231 /// ParseOptionalParamAttrs - Parse a potentially empty list of parameter attributes.
1232 bool LLParser::ParseOptionalParamAttrs(AttrBuilder &B) {
1233   bool HaveError = false;
1234
1235   B.clear();
1236
1237   while (1) {
1238     lltok::Kind Token = Lex.getKind();
1239     switch (Token) {
1240     default:  // End of attributes.
1241       return HaveError;
1242     case lltok::kw_align: {
1243       unsigned Alignment;
1244       if (ParseOptionalAlignment(Alignment))
1245         return true;
1246       B.addAlignmentAttr(Alignment);
1247       continue;
1248     }
1249     case lltok::kw_byval:           B.addAttribute(Attribute::ByVal); break;
1250     case lltok::kw_dereferenceable: {
1251       uint64_t Bytes;
1252       if (ParseOptionalDereferenceableBytes(Bytes))
1253         return true;
1254       B.addDereferenceableAttr(Bytes);
1255       continue;
1256     }
1257     case lltok::kw_inalloca:        B.addAttribute(Attribute::InAlloca); break;
1258     case lltok::kw_inreg:           B.addAttribute(Attribute::InReg); break;
1259     case lltok::kw_nest:            B.addAttribute(Attribute::Nest); break;
1260     case lltok::kw_noalias:         B.addAttribute(Attribute::NoAlias); break;
1261     case lltok::kw_nocapture:       B.addAttribute(Attribute::NoCapture); break;
1262     case lltok::kw_nonnull:         B.addAttribute(Attribute::NonNull); break;
1263     case lltok::kw_readnone:        B.addAttribute(Attribute::ReadNone); break;
1264     case lltok::kw_readonly:        B.addAttribute(Attribute::ReadOnly); break;
1265     case lltok::kw_returned:        B.addAttribute(Attribute::Returned); break;
1266     case lltok::kw_signext:         B.addAttribute(Attribute::SExt); break;
1267     case lltok::kw_sret:            B.addAttribute(Attribute::StructRet); break;
1268     case lltok::kw_zeroext:         B.addAttribute(Attribute::ZExt); break;
1269
1270     case lltok::kw_alignstack:
1271     case lltok::kw_alwaysinline:
1272     case lltok::kw_builtin:
1273     case lltok::kw_inlinehint:
1274     case lltok::kw_jumptable:
1275     case lltok::kw_minsize:
1276     case lltok::kw_naked:
1277     case lltok::kw_nobuiltin:
1278     case lltok::kw_noduplicate:
1279     case lltok::kw_noimplicitfloat:
1280     case lltok::kw_noinline:
1281     case lltok::kw_nonlazybind:
1282     case lltok::kw_noredzone:
1283     case lltok::kw_noreturn:
1284     case lltok::kw_nounwind:
1285     case lltok::kw_optnone:
1286     case lltok::kw_optsize:
1287     case lltok::kw_returns_twice:
1288     case lltok::kw_sanitize_address:
1289     case lltok::kw_sanitize_memory:
1290     case lltok::kw_sanitize_thread:
1291     case lltok::kw_ssp:
1292     case lltok::kw_sspreq:
1293     case lltok::kw_sspstrong:
1294     case lltok::kw_uwtable:
1295       HaveError |= Error(Lex.getLoc(), "invalid use of function-only attribute");
1296       break;
1297     }
1298
1299     Lex.Lex();
1300   }
1301 }
1302
1303 /// ParseOptionalReturnAttrs - Parse a potentially empty list of return attributes.
1304 bool LLParser::ParseOptionalReturnAttrs(AttrBuilder &B) {
1305   bool HaveError = false;
1306
1307   B.clear();
1308
1309   while (1) {
1310     lltok::Kind Token = Lex.getKind();
1311     switch (Token) {
1312     default:  // End of attributes.
1313       return HaveError;
1314     case lltok::kw_dereferenceable: {
1315       uint64_t Bytes;
1316       if (ParseOptionalDereferenceableBytes(Bytes))
1317         return true;
1318       B.addDereferenceableAttr(Bytes);
1319       continue;
1320     }
1321     case lltok::kw_inreg:           B.addAttribute(Attribute::InReg); break;
1322     case lltok::kw_noalias:         B.addAttribute(Attribute::NoAlias); break;
1323     case lltok::kw_nonnull:         B.addAttribute(Attribute::NonNull); break;
1324     case lltok::kw_signext:         B.addAttribute(Attribute::SExt); break;
1325     case lltok::kw_zeroext:         B.addAttribute(Attribute::ZExt); break;
1326
1327     // Error handling.
1328     case lltok::kw_align:
1329     case lltok::kw_byval:
1330     case lltok::kw_inalloca:
1331     case lltok::kw_nest:
1332     case lltok::kw_nocapture:
1333     case lltok::kw_returned:
1334     case lltok::kw_sret:
1335       HaveError |= Error(Lex.getLoc(), "invalid use of parameter-only attribute");
1336       break;
1337
1338     case lltok::kw_alignstack:
1339     case lltok::kw_alwaysinline:
1340     case lltok::kw_builtin:
1341     case lltok::kw_cold:
1342     case lltok::kw_inlinehint:
1343     case lltok::kw_jumptable:
1344     case lltok::kw_minsize:
1345     case lltok::kw_naked:
1346     case lltok::kw_nobuiltin:
1347     case lltok::kw_noduplicate:
1348     case lltok::kw_noimplicitfloat:
1349     case lltok::kw_noinline:
1350     case lltok::kw_nonlazybind:
1351     case lltok::kw_noredzone:
1352     case lltok::kw_noreturn:
1353     case lltok::kw_nounwind:
1354     case lltok::kw_optnone:
1355     case lltok::kw_optsize:
1356     case lltok::kw_returns_twice:
1357     case lltok::kw_sanitize_address:
1358     case lltok::kw_sanitize_memory:
1359     case lltok::kw_sanitize_thread:
1360     case lltok::kw_ssp:
1361     case lltok::kw_sspreq:
1362     case lltok::kw_sspstrong:
1363     case lltok::kw_uwtable:
1364       HaveError |= Error(Lex.getLoc(), "invalid use of function-only attribute");
1365       break;
1366
1367     case lltok::kw_readnone:
1368     case lltok::kw_readonly:
1369       HaveError |= Error(Lex.getLoc(), "invalid use of attribute on return type");
1370     }
1371
1372     Lex.Lex();
1373   }
1374 }
1375
1376 /// ParseOptionalLinkage
1377 ///   ::= /*empty*/
1378 ///   ::= 'private'
1379 ///   ::= 'internal'
1380 ///   ::= 'weak'
1381 ///   ::= 'weak_odr'
1382 ///   ::= 'linkonce'
1383 ///   ::= 'linkonce_odr'
1384 ///   ::= 'available_externally'
1385 ///   ::= 'appending'
1386 ///   ::= 'common'
1387 ///   ::= 'extern_weak'
1388 ///   ::= 'external'
1389 bool LLParser::ParseOptionalLinkage(unsigned &Res, bool &HasLinkage) {
1390   HasLinkage = false;
1391   switch (Lex.getKind()) {
1392   default:                       Res=GlobalValue::ExternalLinkage; return false;
1393   case lltok::kw_private:        Res = GlobalValue::PrivateLinkage;       break;
1394   case lltok::kw_internal:       Res = GlobalValue::InternalLinkage;      break;
1395   case lltok::kw_weak:           Res = GlobalValue::WeakAnyLinkage;       break;
1396   case lltok::kw_weak_odr:       Res = GlobalValue::WeakODRLinkage;       break;
1397   case lltok::kw_linkonce:       Res = GlobalValue::LinkOnceAnyLinkage;   break;
1398   case lltok::kw_linkonce_odr:   Res = GlobalValue::LinkOnceODRLinkage;   break;
1399   case lltok::kw_available_externally:
1400     Res = GlobalValue::AvailableExternallyLinkage;
1401     break;
1402   case lltok::kw_appending:      Res = GlobalValue::AppendingLinkage;     break;
1403   case lltok::kw_common:         Res = GlobalValue::CommonLinkage;        break;
1404   case lltok::kw_extern_weak:    Res = GlobalValue::ExternalWeakLinkage;  break;
1405   case lltok::kw_external:       Res = GlobalValue::ExternalLinkage;      break;
1406   }
1407   Lex.Lex();
1408   HasLinkage = true;
1409   return false;
1410 }
1411
1412 /// ParseOptionalVisibility
1413 ///   ::= /*empty*/
1414 ///   ::= 'default'
1415 ///   ::= 'hidden'
1416 ///   ::= 'protected'
1417 ///
1418 bool LLParser::ParseOptionalVisibility(unsigned &Res) {
1419   switch (Lex.getKind()) {
1420   default:                  Res = GlobalValue::DefaultVisibility; return false;
1421   case lltok::kw_default:   Res = GlobalValue::DefaultVisibility; break;
1422   case lltok::kw_hidden:    Res = GlobalValue::HiddenVisibility; break;
1423   case lltok::kw_protected: Res = GlobalValue::ProtectedVisibility; break;
1424   }
1425   Lex.Lex();
1426   return false;
1427 }
1428
1429 /// ParseOptionalDLLStorageClass
1430 ///   ::= /*empty*/
1431 ///   ::= 'dllimport'
1432 ///   ::= 'dllexport'
1433 ///
1434 bool LLParser::ParseOptionalDLLStorageClass(unsigned &Res) {
1435   switch (Lex.getKind()) {
1436   default:                  Res = GlobalValue::DefaultStorageClass; return false;
1437   case lltok::kw_dllimport: Res = GlobalValue::DLLImportStorageClass; break;
1438   case lltok::kw_dllexport: Res = GlobalValue::DLLExportStorageClass; break;
1439   }
1440   Lex.Lex();
1441   return false;
1442 }
1443
1444 /// ParseOptionalCallingConv
1445 ///   ::= /*empty*/
1446 ///   ::= 'ccc'
1447 ///   ::= 'fastcc'
1448 ///   ::= 'intel_ocl_bicc'
1449 ///   ::= 'coldcc'
1450 ///   ::= 'x86_stdcallcc'
1451 ///   ::= 'x86_fastcallcc'
1452 ///   ::= 'x86_thiscallcc'
1453 ///   ::= 'x86_vectorcallcc'
1454 ///   ::= 'arm_apcscc'
1455 ///   ::= 'arm_aapcscc'
1456 ///   ::= 'arm_aapcs_vfpcc'
1457 ///   ::= 'msp430_intrcc'
1458 ///   ::= 'ptx_kernel'
1459 ///   ::= 'ptx_device'
1460 ///   ::= 'spir_func'
1461 ///   ::= 'spir_kernel'
1462 ///   ::= 'x86_64_sysvcc'
1463 ///   ::= 'x86_64_win64cc'
1464 ///   ::= 'webkit_jscc'
1465 ///   ::= 'anyregcc'
1466 ///   ::= 'preserve_mostcc'
1467 ///   ::= 'preserve_allcc'
1468 ///   ::= 'ghccc'
1469 ///   ::= 'cc' UINT
1470 ///
1471 bool LLParser::ParseOptionalCallingConv(unsigned &CC) {
1472   switch (Lex.getKind()) {
1473   default:                       CC = CallingConv::C; return false;
1474   case lltok::kw_ccc:            CC = CallingConv::C; break;
1475   case lltok::kw_fastcc:         CC = CallingConv::Fast; break;
1476   case lltok::kw_coldcc:         CC = CallingConv::Cold; break;
1477   case lltok::kw_x86_stdcallcc:  CC = CallingConv::X86_StdCall; break;
1478   case lltok::kw_x86_fastcallcc: CC = CallingConv::X86_FastCall; break;
1479   case lltok::kw_x86_thiscallcc: CC = CallingConv::X86_ThisCall; break;
1480   case lltok::kw_x86_vectorcallcc:CC = CallingConv::X86_VectorCall; break;
1481   case lltok::kw_arm_apcscc:     CC = CallingConv::ARM_APCS; break;
1482   case lltok::kw_arm_aapcscc:    CC = CallingConv::ARM_AAPCS; break;
1483   case lltok::kw_arm_aapcs_vfpcc:CC = CallingConv::ARM_AAPCS_VFP; break;
1484   case lltok::kw_msp430_intrcc:  CC = CallingConv::MSP430_INTR; break;
1485   case lltok::kw_ptx_kernel:     CC = CallingConv::PTX_Kernel; break;
1486   case lltok::kw_ptx_device:     CC = CallingConv::PTX_Device; break;
1487   case lltok::kw_spir_kernel:    CC = CallingConv::SPIR_KERNEL; break;
1488   case lltok::kw_spir_func:      CC = CallingConv::SPIR_FUNC; break;
1489   case lltok::kw_intel_ocl_bicc: CC = CallingConv::Intel_OCL_BI; break;
1490   case lltok::kw_x86_64_sysvcc:  CC = CallingConv::X86_64_SysV; break;
1491   case lltok::kw_x86_64_win64cc: CC = CallingConv::X86_64_Win64; break;
1492   case lltok::kw_webkit_jscc:    CC = CallingConv::WebKit_JS; break;
1493   case lltok::kw_anyregcc:       CC = CallingConv::AnyReg; break;
1494   case lltok::kw_preserve_mostcc:CC = CallingConv::PreserveMost; break;
1495   case lltok::kw_preserve_allcc: CC = CallingConv::PreserveAll; break;
1496   case lltok::kw_ghccc:          CC = CallingConv::GHC; break;
1497   case lltok::kw_cc: {
1498       Lex.Lex();
1499       return ParseUInt32(CC);
1500     }
1501   }
1502
1503   Lex.Lex();
1504   return false;
1505 }
1506
1507 /// ParseInstructionMetadata
1508 ///   ::= !dbg !42 (',' !dbg !57)*
1509 bool LLParser::ParseInstructionMetadata(Instruction *Inst,
1510                                         PerFunctionState *PFS) {
1511   do {
1512     if (Lex.getKind() != lltok::MetadataVar)
1513       return TokError("expected metadata after comma");
1514
1515     std::string Name = Lex.getStrVal();
1516     unsigned MDK = M->getMDKindID(Name);
1517     Lex.Lex();
1518
1519     MDNode *Node;
1520     SMLoc Loc = Lex.getLoc();
1521
1522     if (ParseToken(lltok::exclaim, "expected '!' here"))
1523       return true;
1524
1525     // This code is similar to that of ParseMetadataValue, however it needs to
1526     // have special-case code for a forward reference; see the comments on
1527     // ForwardRefInstMetadata for details. Also, MDStrings are not supported
1528     // at the top level here.
1529     if (Lex.getKind() == lltok::lbrace) {
1530       ValID ID;
1531       if (ParseMetadataListValue(ID, PFS))
1532         return true;
1533       assert(ID.Kind == ValID::t_MDNode);
1534       if (ID.MDNodeVal->isFunctionLocal())
1535         return Error(Loc, "unexpected function-local metadata");
1536       Inst->setMetadata(MDK, ID.MDNodeVal);
1537     } else {
1538       unsigned NodeID = 0;
1539       if (ParseMDNodeID(Node, NodeID))
1540         return true;
1541       if (Node) {
1542         // If we got the node, add it to the instruction.
1543         Inst->setMetadata(MDK, Node);
1544       } else {
1545         MDRef R = { Loc, MDK, NodeID };
1546         // Otherwise, remember that this should be resolved later.
1547         ForwardRefInstMetadata[Inst].push_back(R);
1548       }
1549     }
1550
1551     if (MDK == LLVMContext::MD_tbaa)
1552       InstsWithTBAATag.push_back(Inst);
1553
1554     // If this is the end of the list, we're done.
1555   } while (EatIfPresent(lltok::comma));
1556   return false;
1557 }
1558
1559 /// ParseOptionalAlignment
1560 ///   ::= /* empty */
1561 ///   ::= 'align' 4
1562 bool LLParser::ParseOptionalAlignment(unsigned &Alignment) {
1563   Alignment = 0;
1564   if (!EatIfPresent(lltok::kw_align))
1565     return false;
1566   LocTy AlignLoc = Lex.getLoc();
1567   if (ParseUInt32(Alignment)) return true;
1568   if (!isPowerOf2_32(Alignment))
1569     return Error(AlignLoc, "alignment is not a power of two");
1570   if (Alignment > Value::MaximumAlignment)
1571     return Error(AlignLoc, "huge alignments are not supported yet");
1572   return false;
1573 }
1574
1575 /// ParseOptionalDereferenceableBytes
1576 ///   ::= /* empty */
1577 ///   ::= 'dereferenceable' '(' 4 ')'
1578 bool LLParser::ParseOptionalDereferenceableBytes(uint64_t &Bytes) {
1579   Bytes = 0;
1580   if (!EatIfPresent(lltok::kw_dereferenceable))
1581     return false;
1582   LocTy ParenLoc = Lex.getLoc();
1583   if (!EatIfPresent(lltok::lparen))
1584     return Error(ParenLoc, "expected '('");
1585   LocTy DerefLoc = Lex.getLoc();
1586   if (ParseUInt64(Bytes)) return true;
1587   ParenLoc = Lex.getLoc();
1588   if (!EatIfPresent(lltok::rparen))
1589     return Error(ParenLoc, "expected ')'");
1590   if (!Bytes)
1591     return Error(DerefLoc, "dereferenceable bytes must be non-zero");
1592   return false;
1593 }
1594
1595 /// ParseOptionalCommaAlign
1596 ///   ::=
1597 ///   ::= ',' align 4
1598 ///
1599 /// This returns with AteExtraComma set to true if it ate an excess comma at the
1600 /// end.
1601 bool LLParser::ParseOptionalCommaAlign(unsigned &Alignment,
1602                                        bool &AteExtraComma) {
1603   AteExtraComma = false;
1604   while (EatIfPresent(lltok::comma)) {
1605     // Metadata at the end is an early exit.
1606     if (Lex.getKind() == lltok::MetadataVar) {
1607       AteExtraComma = true;
1608       return false;
1609     }
1610
1611     if (Lex.getKind() != lltok::kw_align)
1612       return Error(Lex.getLoc(), "expected metadata or 'align'");
1613
1614     if (ParseOptionalAlignment(Alignment)) return true;
1615   }
1616
1617   return false;
1618 }
1619
1620 /// ParseScopeAndOrdering
1621 ///   if isAtomic: ::= 'singlethread'? AtomicOrdering
1622 ///   else: ::=
1623 ///
1624 /// This sets Scope and Ordering to the parsed values.
1625 bool LLParser::ParseScopeAndOrdering(bool isAtomic, SynchronizationScope &Scope,
1626                                      AtomicOrdering &Ordering) {
1627   if (!isAtomic)
1628     return false;
1629
1630   Scope = CrossThread;
1631   if (EatIfPresent(lltok::kw_singlethread))
1632     Scope = SingleThread;
1633
1634   return ParseOrdering(Ordering);
1635 }
1636
1637 /// ParseOrdering
1638 ///   ::= AtomicOrdering
1639 ///
1640 /// This sets Ordering to the parsed value.
1641 bool LLParser::ParseOrdering(AtomicOrdering &Ordering) {
1642   switch (Lex.getKind()) {
1643   default: return TokError("Expected ordering on atomic instruction");
1644   case lltok::kw_unordered: Ordering = Unordered; break;
1645   case lltok::kw_monotonic: Ordering = Monotonic; break;
1646   case lltok::kw_acquire: Ordering = Acquire; break;
1647   case lltok::kw_release: Ordering = Release; break;
1648   case lltok::kw_acq_rel: Ordering = AcquireRelease; break;
1649   case lltok::kw_seq_cst: Ordering = SequentiallyConsistent; break;
1650   }
1651   Lex.Lex();
1652   return false;
1653 }
1654
1655 /// ParseOptionalStackAlignment
1656 ///   ::= /* empty */
1657 ///   ::= 'alignstack' '(' 4 ')'
1658 bool LLParser::ParseOptionalStackAlignment(unsigned &Alignment) {
1659   Alignment = 0;
1660   if (!EatIfPresent(lltok::kw_alignstack))
1661     return false;
1662   LocTy ParenLoc = Lex.getLoc();
1663   if (!EatIfPresent(lltok::lparen))
1664     return Error(ParenLoc, "expected '('");
1665   LocTy AlignLoc = Lex.getLoc();
1666   if (ParseUInt32(Alignment)) return true;
1667   ParenLoc = Lex.getLoc();
1668   if (!EatIfPresent(lltok::rparen))
1669     return Error(ParenLoc, "expected ')'");
1670   if (!isPowerOf2_32(Alignment))
1671     return Error(AlignLoc, "stack alignment is not a power of two");
1672   return false;
1673 }
1674
1675 /// ParseIndexList - This parses the index list for an insert/extractvalue
1676 /// instruction.  This sets AteExtraComma in the case where we eat an extra
1677 /// comma at the end of the line and find that it is followed by metadata.
1678 /// Clients that don't allow metadata can call the version of this function that
1679 /// only takes one argument.
1680 ///
1681 /// ParseIndexList
1682 ///    ::=  (',' uint32)+
1683 ///
1684 bool LLParser::ParseIndexList(SmallVectorImpl<unsigned> &Indices,
1685                               bool &AteExtraComma) {
1686   AteExtraComma = false;
1687
1688   if (Lex.getKind() != lltok::comma)
1689     return TokError("expected ',' as start of index list");
1690
1691   while (EatIfPresent(lltok::comma)) {
1692     if (Lex.getKind() == lltok::MetadataVar) {
1693       AteExtraComma = true;
1694       return false;
1695     }
1696     unsigned Idx = 0;
1697     if (ParseUInt32(Idx)) return true;
1698     Indices.push_back(Idx);
1699   }
1700
1701   return false;
1702 }
1703
1704 //===----------------------------------------------------------------------===//
1705 // Type Parsing.
1706 //===----------------------------------------------------------------------===//
1707
1708 /// ParseType - Parse a type.
1709 bool LLParser::ParseType(Type *&Result, bool AllowVoid) {
1710   SMLoc TypeLoc = Lex.getLoc();
1711   switch (Lex.getKind()) {
1712   default:
1713     return TokError("expected type");
1714   case lltok::Type:
1715     // Type ::= 'float' | 'void' (etc)
1716     Result = Lex.getTyVal();
1717     Lex.Lex();
1718     break;
1719   case lltok::lbrace:
1720     // Type ::= StructType
1721     if (ParseAnonStructType(Result, false))
1722       return true;
1723     break;
1724   case lltok::lsquare:
1725     // Type ::= '[' ... ']'
1726     Lex.Lex(); // eat the lsquare.
1727     if (ParseArrayVectorType(Result, false))
1728       return true;
1729     break;
1730   case lltok::less: // Either vector or packed struct.
1731     // Type ::= '<' ... '>'
1732     Lex.Lex();
1733     if (Lex.getKind() == lltok::lbrace) {
1734       if (ParseAnonStructType(Result, true) ||
1735           ParseToken(lltok::greater, "expected '>' at end of packed struct"))
1736         return true;
1737     } else if (ParseArrayVectorType(Result, true))
1738       return true;
1739     break;
1740   case lltok::LocalVar: {
1741     // Type ::= %foo
1742     std::pair<Type*, LocTy> &Entry = NamedTypes[Lex.getStrVal()];
1743
1744     // If the type hasn't been defined yet, create a forward definition and
1745     // remember where that forward def'n was seen (in case it never is defined).
1746     if (!Entry.first) {
1747       Entry.first = StructType::create(Context, Lex.getStrVal());
1748       Entry.second = Lex.getLoc();
1749     }
1750     Result = Entry.first;
1751     Lex.Lex();
1752     break;
1753   }
1754
1755   case lltok::LocalVarID: {
1756     // Type ::= %4
1757     if (Lex.getUIntVal() >= NumberedTypes.size())
1758       NumberedTypes.resize(Lex.getUIntVal()+1);
1759     std::pair<Type*, LocTy> &Entry = NumberedTypes[Lex.getUIntVal()];
1760
1761     // If the type hasn't been defined yet, create a forward definition and
1762     // remember where that forward def'n was seen (in case it never is defined).
1763     if (!Entry.first) {
1764       Entry.first = StructType::create(Context);
1765       Entry.second = Lex.getLoc();
1766     }
1767     Result = Entry.first;
1768     Lex.Lex();
1769     break;
1770   }
1771   }
1772
1773   // Parse the type suffixes.
1774   while (1) {
1775     switch (Lex.getKind()) {
1776     // End of type.
1777     default:
1778       if (!AllowVoid && Result->isVoidTy())
1779         return Error(TypeLoc, "void type only allowed for function results");
1780       return false;
1781
1782     // Type ::= Type '*'
1783     case lltok::star:
1784       if (Result->isLabelTy())
1785         return TokError("basic block pointers are invalid");
1786       if (Result->isVoidTy())
1787         return TokError("pointers to void are invalid - use i8* instead");
1788       if (!PointerType::isValidElementType(Result))
1789         return TokError("pointer to this type is invalid");
1790       Result = PointerType::getUnqual(Result);
1791       Lex.Lex();
1792       break;
1793
1794     // Type ::= Type 'addrspace' '(' uint32 ')' '*'
1795     case lltok::kw_addrspace: {
1796       if (Result->isLabelTy())
1797         return TokError("basic block pointers are invalid");
1798       if (Result->isVoidTy())
1799         return TokError("pointers to void are invalid; use i8* instead");
1800       if (!PointerType::isValidElementType(Result))
1801         return TokError("pointer to this type is invalid");
1802       unsigned AddrSpace;
1803       if (ParseOptionalAddrSpace(AddrSpace) ||
1804           ParseToken(lltok::star, "expected '*' in address space"))
1805         return true;
1806
1807       Result = PointerType::get(Result, AddrSpace);
1808       break;
1809     }
1810
1811     /// Types '(' ArgTypeListI ')' OptFuncAttrs
1812     case lltok::lparen:
1813       if (ParseFunctionType(Result))
1814         return true;
1815       break;
1816     }
1817   }
1818 }
1819
1820 /// ParseParameterList
1821 ///    ::= '(' ')'
1822 ///    ::= '(' Arg (',' Arg)* ')'
1823 ///  Arg
1824 ///    ::= Type OptionalAttributes Value OptionalAttributes
1825 bool LLParser::ParseParameterList(SmallVectorImpl<ParamInfo> &ArgList,
1826                                   PerFunctionState &PFS, bool IsMustTailCall,
1827                                   bool InVarArgsFunc) {
1828   if (ParseToken(lltok::lparen, "expected '(' in call"))
1829     return true;
1830
1831   unsigned AttrIndex = 1;
1832   while (Lex.getKind() != lltok::rparen) {
1833     // If this isn't the first argument, we need a comma.
1834     if (!ArgList.empty() &&
1835         ParseToken(lltok::comma, "expected ',' in argument list"))
1836       return true;
1837
1838     // Parse an ellipsis if this is a musttail call in a variadic function.
1839     if (Lex.getKind() == lltok::dotdotdot) {
1840       const char *Msg = "unexpected ellipsis in argument list for ";
1841       if (!IsMustTailCall)
1842         return TokError(Twine(Msg) + "non-musttail call");
1843       if (!InVarArgsFunc)
1844         return TokError(Twine(Msg) + "musttail call in non-varargs function");
1845       Lex.Lex();  // Lex the '...', it is purely for readability.
1846       return ParseToken(lltok::rparen, "expected ')' at end of argument list");
1847     }
1848
1849     // Parse the argument.
1850     LocTy ArgLoc;
1851     Type *ArgTy = nullptr;
1852     AttrBuilder ArgAttrs;
1853     Value *V;
1854     if (ParseType(ArgTy, ArgLoc))
1855       return true;
1856
1857     // Otherwise, handle normal operands.
1858     if (ParseOptionalParamAttrs(ArgAttrs) || ParseValue(ArgTy, V, PFS))
1859       return true;
1860     ArgList.push_back(ParamInfo(ArgLoc, V, AttributeSet::get(V->getContext(),
1861                                                              AttrIndex++,
1862                                                              ArgAttrs)));
1863   }
1864
1865   if (IsMustTailCall && InVarArgsFunc)
1866     return TokError("expected '...' at end of argument list for musttail call "
1867                     "in varargs function");
1868
1869   Lex.Lex();  // Lex the ')'.
1870   return false;
1871 }
1872
1873
1874
1875 /// ParseArgumentList - Parse the argument list for a function type or function
1876 /// prototype.
1877 ///   ::= '(' ArgTypeListI ')'
1878 /// ArgTypeListI
1879 ///   ::= /*empty*/
1880 ///   ::= '...'
1881 ///   ::= ArgTypeList ',' '...'
1882 ///   ::= ArgType (',' ArgType)*
1883 ///
1884 bool LLParser::ParseArgumentList(SmallVectorImpl<ArgInfo> &ArgList,
1885                                  bool &isVarArg){
1886   isVarArg = false;
1887   assert(Lex.getKind() == lltok::lparen);
1888   Lex.Lex(); // eat the (.
1889
1890   if (Lex.getKind() == lltok::rparen) {
1891     // empty
1892   } else if (Lex.getKind() == lltok::dotdotdot) {
1893     isVarArg = true;
1894     Lex.Lex();
1895   } else {
1896     LocTy TypeLoc = Lex.getLoc();
1897     Type *ArgTy = nullptr;
1898     AttrBuilder Attrs;
1899     std::string Name;
1900
1901     if (ParseType(ArgTy) ||
1902         ParseOptionalParamAttrs(Attrs)) return true;
1903
1904     if (ArgTy->isVoidTy())
1905       return Error(TypeLoc, "argument can not have void type");
1906
1907     if (Lex.getKind() == lltok::LocalVar) {
1908       Name = Lex.getStrVal();
1909       Lex.Lex();
1910     }
1911
1912     if (!FunctionType::isValidArgumentType(ArgTy))
1913       return Error(TypeLoc, "invalid type for function argument");
1914
1915     unsigned AttrIndex = 1;
1916     ArgList.push_back(ArgInfo(TypeLoc, ArgTy,
1917                               AttributeSet::get(ArgTy->getContext(),
1918                                                 AttrIndex++, Attrs), Name));
1919
1920     while (EatIfPresent(lltok::comma)) {
1921       // Handle ... at end of arg list.
1922       if (EatIfPresent(lltok::dotdotdot)) {
1923         isVarArg = true;
1924         break;
1925       }
1926
1927       // Otherwise must be an argument type.
1928       TypeLoc = Lex.getLoc();
1929       if (ParseType(ArgTy) || ParseOptionalParamAttrs(Attrs)) return true;
1930
1931       if (ArgTy->isVoidTy())
1932         return Error(TypeLoc, "argument can not have void type");
1933
1934       if (Lex.getKind() == lltok::LocalVar) {
1935         Name = Lex.getStrVal();
1936         Lex.Lex();
1937       } else {
1938         Name = "";
1939       }
1940
1941       if (!ArgTy->isFirstClassType())
1942         return Error(TypeLoc, "invalid type for function argument");
1943
1944       ArgList.push_back(ArgInfo(TypeLoc, ArgTy,
1945                                 AttributeSet::get(ArgTy->getContext(),
1946                                                   AttrIndex++, Attrs),
1947                                 Name));
1948     }
1949   }
1950
1951   return ParseToken(lltok::rparen, "expected ')' at end of argument list");
1952 }
1953
1954 /// ParseFunctionType
1955 ///  ::= Type ArgumentList OptionalAttrs
1956 bool LLParser::ParseFunctionType(Type *&Result) {
1957   assert(Lex.getKind() == lltok::lparen);
1958
1959   if (!FunctionType::isValidReturnType(Result))
1960     return TokError("invalid function return type");
1961
1962   SmallVector<ArgInfo, 8> ArgList;
1963   bool isVarArg;
1964   if (ParseArgumentList(ArgList, isVarArg))
1965     return true;
1966
1967   // Reject names on the arguments lists.
1968   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
1969     if (!ArgList[i].Name.empty())
1970       return Error(ArgList[i].Loc, "argument name invalid in function type");
1971     if (ArgList[i].Attrs.hasAttributes(i + 1))
1972       return Error(ArgList[i].Loc,
1973                    "argument attributes invalid in function type");
1974   }
1975
1976   SmallVector<Type*, 16> ArgListTy;
1977   for (unsigned i = 0, e = ArgList.size(); i != e; ++i)
1978     ArgListTy.push_back(ArgList[i].Ty);
1979
1980   Result = FunctionType::get(Result, ArgListTy, isVarArg);
1981   return false;
1982 }
1983
1984 /// ParseAnonStructType - Parse an anonymous struct type, which is inlined into
1985 /// other structs.
1986 bool LLParser::ParseAnonStructType(Type *&Result, bool Packed) {
1987   SmallVector<Type*, 8> Elts;
1988   if (ParseStructBody(Elts)) return true;
1989
1990   Result = StructType::get(Context, Elts, Packed);
1991   return false;
1992 }
1993
1994 /// ParseStructDefinition - Parse a struct in a 'type' definition.
1995 bool LLParser::ParseStructDefinition(SMLoc TypeLoc, StringRef Name,
1996                                      std::pair<Type*, LocTy> &Entry,
1997                                      Type *&ResultTy) {
1998   // If the type was already defined, diagnose the redefinition.
1999   if (Entry.first && !Entry.second.isValid())
2000     return Error(TypeLoc, "redefinition of type");
2001
2002   // If we have opaque, just return without filling in the definition for the
2003   // struct.  This counts as a definition as far as the .ll file goes.
2004   if (EatIfPresent(lltok::kw_opaque)) {
2005     // This type is being defined, so clear the location to indicate this.
2006     Entry.second = SMLoc();
2007
2008     // If this type number has never been uttered, create it.
2009     if (!Entry.first)
2010       Entry.first = StructType::create(Context, Name);
2011     ResultTy = Entry.first;
2012     return false;
2013   }
2014
2015   // If the type starts with '<', then it is either a packed struct or a vector.
2016   bool isPacked = EatIfPresent(lltok::less);
2017
2018   // If we don't have a struct, then we have a random type alias, which we
2019   // accept for compatibility with old files.  These types are not allowed to be
2020   // forward referenced and not allowed to be recursive.
2021   if (Lex.getKind() != lltok::lbrace) {
2022     if (Entry.first)
2023       return Error(TypeLoc, "forward references to non-struct type");
2024
2025     ResultTy = nullptr;
2026     if (isPacked)
2027       return ParseArrayVectorType(ResultTy, true);
2028     return ParseType(ResultTy);
2029   }
2030
2031   // This type is being defined, so clear the location to indicate this.
2032   Entry.second = SMLoc();
2033
2034   // If this type number has never been uttered, create it.
2035   if (!Entry.first)
2036     Entry.first = StructType::create(Context, Name);
2037
2038   StructType *STy = cast<StructType>(Entry.first);
2039
2040   SmallVector<Type*, 8> Body;
2041   if (ParseStructBody(Body) ||
2042       (isPacked && ParseToken(lltok::greater, "expected '>' in packed struct")))
2043     return true;
2044
2045   STy->setBody(Body, isPacked);
2046   ResultTy = STy;
2047   return false;
2048 }
2049
2050
2051 /// ParseStructType: Handles packed and unpacked types.  </> parsed elsewhere.
2052 ///   StructType
2053 ///     ::= '{' '}'
2054 ///     ::= '{' Type (',' Type)* '}'
2055 ///     ::= '<' '{' '}' '>'
2056 ///     ::= '<' '{' Type (',' Type)* '}' '>'
2057 bool LLParser::ParseStructBody(SmallVectorImpl<Type*> &Body) {
2058   assert(Lex.getKind() == lltok::lbrace);
2059   Lex.Lex(); // Consume the '{'
2060
2061   // Handle the empty struct.
2062   if (EatIfPresent(lltok::rbrace))
2063     return false;
2064
2065   LocTy EltTyLoc = Lex.getLoc();
2066   Type *Ty = nullptr;
2067   if (ParseType(Ty)) return true;
2068   Body.push_back(Ty);
2069
2070   if (!StructType::isValidElementType(Ty))
2071     return Error(EltTyLoc, "invalid element type for struct");
2072
2073   while (EatIfPresent(lltok::comma)) {
2074     EltTyLoc = Lex.getLoc();
2075     if (ParseType(Ty)) return true;
2076
2077     if (!StructType::isValidElementType(Ty))
2078       return Error(EltTyLoc, "invalid element type for struct");
2079
2080     Body.push_back(Ty);
2081   }
2082
2083   return ParseToken(lltok::rbrace, "expected '}' at end of struct");
2084 }
2085
2086 /// ParseArrayVectorType - Parse an array or vector type, assuming the first
2087 /// token has already been consumed.
2088 ///   Type
2089 ///     ::= '[' APSINTVAL 'x' Types ']'
2090 ///     ::= '<' APSINTVAL 'x' Types '>'
2091 bool LLParser::ParseArrayVectorType(Type *&Result, bool isVector) {
2092   if (Lex.getKind() != lltok::APSInt || Lex.getAPSIntVal().isSigned() ||
2093       Lex.getAPSIntVal().getBitWidth() > 64)
2094     return TokError("expected number in address space");
2095
2096   LocTy SizeLoc = Lex.getLoc();
2097   uint64_t Size = Lex.getAPSIntVal().getZExtValue();
2098   Lex.Lex();
2099
2100   if (ParseToken(lltok::kw_x, "expected 'x' after element count"))
2101       return true;
2102
2103   LocTy TypeLoc = Lex.getLoc();
2104   Type *EltTy = nullptr;
2105   if (ParseType(EltTy)) return true;
2106
2107   if (ParseToken(isVector ? lltok::greater : lltok::rsquare,
2108                  "expected end of sequential type"))
2109     return true;
2110
2111   if (isVector) {
2112     if (Size == 0)
2113       return Error(SizeLoc, "zero element vector is illegal");
2114     if ((unsigned)Size != Size)
2115       return Error(SizeLoc, "size too large for vector");
2116     if (!VectorType::isValidElementType(EltTy))
2117       return Error(TypeLoc, "invalid vector element type");
2118     Result = VectorType::get(EltTy, unsigned(Size));
2119   } else {
2120     if (!ArrayType::isValidElementType(EltTy))
2121       return Error(TypeLoc, "invalid array element type");
2122     Result = ArrayType::get(EltTy, Size);
2123   }
2124   return false;
2125 }
2126
2127 //===----------------------------------------------------------------------===//
2128 // Function Semantic Analysis.
2129 //===----------------------------------------------------------------------===//
2130
2131 LLParser::PerFunctionState::PerFunctionState(LLParser &p, Function &f,
2132                                              int functionNumber)
2133   : P(p), F(f), FunctionNumber(functionNumber) {
2134
2135   // Insert unnamed arguments into the NumberedVals list.
2136   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
2137        AI != E; ++AI)
2138     if (!AI->hasName())
2139       NumberedVals.push_back(AI);
2140 }
2141
2142 LLParser::PerFunctionState::~PerFunctionState() {
2143   // If there were any forward referenced non-basicblock values, delete them.
2144   for (std::map<std::string, std::pair<Value*, LocTy> >::iterator
2145        I = ForwardRefVals.begin(), E = ForwardRefVals.end(); I != E; ++I)
2146     if (!isa<BasicBlock>(I->second.first)) {
2147       I->second.first->replaceAllUsesWith(
2148                            UndefValue::get(I->second.first->getType()));
2149       delete I->second.first;
2150       I->second.first = nullptr;
2151     }
2152
2153   for (std::map<unsigned, std::pair<Value*, LocTy> >::iterator
2154        I = ForwardRefValIDs.begin(), E = ForwardRefValIDs.end(); I != E; ++I)
2155     if (!isa<BasicBlock>(I->second.first)) {
2156       I->second.first->replaceAllUsesWith(
2157                            UndefValue::get(I->second.first->getType()));
2158       delete I->second.first;
2159       I->second.first = nullptr;
2160     }
2161 }
2162
2163 bool LLParser::PerFunctionState::FinishFunction() {
2164   if (!ForwardRefVals.empty())
2165     return P.Error(ForwardRefVals.begin()->second.second,
2166                    "use of undefined value '%" + ForwardRefVals.begin()->first +
2167                    "'");
2168   if (!ForwardRefValIDs.empty())
2169     return P.Error(ForwardRefValIDs.begin()->second.second,
2170                    "use of undefined value '%" +
2171                    Twine(ForwardRefValIDs.begin()->first) + "'");
2172   return false;
2173 }
2174
2175
2176 /// GetVal - Get a value with the specified name or ID, creating a
2177 /// forward reference record if needed.  This can return null if the value
2178 /// exists but does not have the right type.
2179 Value *LLParser::PerFunctionState::GetVal(const std::string &Name,
2180                                           Type *Ty, LocTy Loc) {
2181   // Look this name up in the normal function symbol table.
2182   Value *Val = F.getValueSymbolTable().lookup(Name);
2183
2184   // If this is a forward reference for the value, see if we already created a
2185   // forward ref record.
2186   if (!Val) {
2187     std::map<std::string, std::pair<Value*, LocTy> >::iterator
2188       I = ForwardRefVals.find(Name);
2189     if (I != ForwardRefVals.end())
2190       Val = I->second.first;
2191   }
2192
2193   // If we have the value in the symbol table or fwd-ref table, return it.
2194   if (Val) {
2195     if (Val->getType() == Ty) return Val;
2196     if (Ty->isLabelTy())
2197       P.Error(Loc, "'%" + Name + "' is not a basic block");
2198     else
2199       P.Error(Loc, "'%" + Name + "' defined with type '" +
2200               getTypeString(Val->getType()) + "'");
2201     return nullptr;
2202   }
2203
2204   // Don't make placeholders with invalid type.
2205   if (!Ty->isFirstClassType()) {
2206     P.Error(Loc, "invalid use of a non-first-class type");
2207     return nullptr;
2208   }
2209
2210   // Otherwise, create a new forward reference for this value and remember it.
2211   Value *FwdVal;
2212   if (Ty->isLabelTy())
2213     FwdVal = BasicBlock::Create(F.getContext(), Name, &F);
2214   else
2215     FwdVal = new Argument(Ty, Name);
2216
2217   ForwardRefVals[Name] = std::make_pair(FwdVal, Loc);
2218   return FwdVal;
2219 }
2220
2221 Value *LLParser::PerFunctionState::GetVal(unsigned ID, Type *Ty,
2222                                           LocTy Loc) {
2223   // Look this name up in the normal function symbol table.
2224   Value *Val = ID < NumberedVals.size() ? NumberedVals[ID] : nullptr;
2225
2226   // If this is a forward reference for the value, see if we already created a
2227   // forward ref record.
2228   if (!Val) {
2229     std::map<unsigned, std::pair<Value*, LocTy> >::iterator
2230       I = ForwardRefValIDs.find(ID);
2231     if (I != ForwardRefValIDs.end())
2232       Val = I->second.first;
2233   }
2234
2235   // If we have the value in the symbol table or fwd-ref table, return it.
2236   if (Val) {
2237     if (Val->getType() == Ty) return Val;
2238     if (Ty->isLabelTy())
2239       P.Error(Loc, "'%" + Twine(ID) + "' is not a basic block");
2240     else
2241       P.Error(Loc, "'%" + Twine(ID) + "' defined with type '" +
2242               getTypeString(Val->getType()) + "'");
2243     return nullptr;
2244   }
2245
2246   if (!Ty->isFirstClassType()) {
2247     P.Error(Loc, "invalid use of a non-first-class type");
2248     return nullptr;
2249   }
2250
2251   // Otherwise, create a new forward reference for this value and remember it.
2252   Value *FwdVal;
2253   if (Ty->isLabelTy())
2254     FwdVal = BasicBlock::Create(F.getContext(), "", &F);
2255   else
2256     FwdVal = new Argument(Ty);
2257
2258   ForwardRefValIDs[ID] = std::make_pair(FwdVal, Loc);
2259   return FwdVal;
2260 }
2261
2262 /// SetInstName - After an instruction is parsed and inserted into its
2263 /// basic block, this installs its name.
2264 bool LLParser::PerFunctionState::SetInstName(int NameID,
2265                                              const std::string &NameStr,
2266                                              LocTy NameLoc, Instruction *Inst) {
2267   // If this instruction has void type, it cannot have a name or ID specified.
2268   if (Inst->getType()->isVoidTy()) {
2269     if (NameID != -1 || !NameStr.empty())
2270       return P.Error(NameLoc, "instructions returning void cannot have a name");
2271     return false;
2272   }
2273
2274   // If this was a numbered instruction, verify that the instruction is the
2275   // expected value and resolve any forward references.
2276   if (NameStr.empty()) {
2277     // If neither a name nor an ID was specified, just use the next ID.
2278     if (NameID == -1)
2279       NameID = NumberedVals.size();
2280
2281     if (unsigned(NameID) != NumberedVals.size())
2282       return P.Error(NameLoc, "instruction expected to be numbered '%" +
2283                      Twine(NumberedVals.size()) + "'");
2284
2285     std::map<unsigned, std::pair<Value*, LocTy> >::iterator FI =
2286       ForwardRefValIDs.find(NameID);
2287     if (FI != ForwardRefValIDs.end()) {
2288       if (FI->second.first->getType() != Inst->getType())
2289         return P.Error(NameLoc, "instruction forward referenced with type '" +
2290                        getTypeString(FI->second.first->getType()) + "'");
2291       FI->second.first->replaceAllUsesWith(Inst);
2292       delete FI->second.first;
2293       ForwardRefValIDs.erase(FI);
2294     }
2295
2296     NumberedVals.push_back(Inst);
2297     return false;
2298   }
2299
2300   // Otherwise, the instruction had a name.  Resolve forward refs and set it.
2301   std::map<std::string, std::pair<Value*, LocTy> >::iterator
2302     FI = ForwardRefVals.find(NameStr);
2303   if (FI != ForwardRefVals.end()) {
2304     if (FI->second.first->getType() != Inst->getType())
2305       return P.Error(NameLoc, "instruction forward referenced with type '" +
2306                      getTypeString(FI->second.first->getType()) + "'");
2307     FI->second.first->replaceAllUsesWith(Inst);
2308     delete FI->second.first;
2309     ForwardRefVals.erase(FI);
2310   }
2311
2312   // Set the name on the instruction.
2313   Inst->setName(NameStr);
2314
2315   if (Inst->getName() != NameStr)
2316     return P.Error(NameLoc, "multiple definition of local value named '" +
2317                    NameStr + "'");
2318   return false;
2319 }
2320
2321 /// GetBB - Get a basic block with the specified name or ID, creating a
2322 /// forward reference record if needed.
2323 BasicBlock *LLParser::PerFunctionState::GetBB(const std::string &Name,
2324                                               LocTy Loc) {
2325   return cast_or_null<BasicBlock>(GetVal(Name,
2326                                         Type::getLabelTy(F.getContext()), Loc));
2327 }
2328
2329 BasicBlock *LLParser::PerFunctionState::GetBB(unsigned ID, LocTy Loc) {
2330   return cast_or_null<BasicBlock>(GetVal(ID,
2331                                         Type::getLabelTy(F.getContext()), Loc));
2332 }
2333
2334 /// DefineBB - Define the specified basic block, which is either named or
2335 /// unnamed.  If there is an error, this returns null otherwise it returns
2336 /// the block being defined.
2337 BasicBlock *LLParser::PerFunctionState::DefineBB(const std::string &Name,
2338                                                  LocTy Loc) {
2339   BasicBlock *BB;
2340   if (Name.empty())
2341     BB = GetBB(NumberedVals.size(), Loc);
2342   else
2343     BB = GetBB(Name, Loc);
2344   if (!BB) return nullptr; // Already diagnosed error.
2345
2346   // Move the block to the end of the function.  Forward ref'd blocks are
2347   // inserted wherever they happen to be referenced.
2348   F.getBasicBlockList().splice(F.end(), F.getBasicBlockList(), BB);
2349
2350   // Remove the block from forward ref sets.
2351   if (Name.empty()) {
2352     ForwardRefValIDs.erase(NumberedVals.size());
2353     NumberedVals.push_back(BB);
2354   } else {
2355     // BB forward references are already in the function symbol table.
2356     ForwardRefVals.erase(Name);
2357   }
2358
2359   return BB;
2360 }
2361
2362 //===----------------------------------------------------------------------===//
2363 // Constants.
2364 //===----------------------------------------------------------------------===//
2365
2366 /// ParseValID - Parse an abstract value that doesn't necessarily have a
2367 /// type implied.  For example, if we parse "4" we don't know what integer type
2368 /// it has.  The value will later be combined with its type and checked for
2369 /// sanity.  PFS is used to convert function-local operands of metadata (since
2370 /// metadata operands are not just parsed here but also converted to values).
2371 /// PFS can be null when we are not parsing metadata values inside a function.
2372 bool LLParser::ParseValID(ValID &ID, PerFunctionState *PFS) {
2373   ID.Loc = Lex.getLoc();
2374   switch (Lex.getKind()) {
2375   default: return TokError("expected value token");
2376   case lltok::GlobalID:  // @42
2377     ID.UIntVal = Lex.getUIntVal();
2378     ID.Kind = ValID::t_GlobalID;
2379     break;
2380   case lltok::GlobalVar:  // @foo
2381     ID.StrVal = Lex.getStrVal();
2382     ID.Kind = ValID::t_GlobalName;
2383     break;
2384   case lltok::LocalVarID:  // %42
2385     ID.UIntVal = Lex.getUIntVal();
2386     ID.Kind = ValID::t_LocalID;
2387     break;
2388   case lltok::LocalVar:  // %foo
2389     ID.StrVal = Lex.getStrVal();
2390     ID.Kind = ValID::t_LocalName;
2391     break;
2392   case lltok::exclaim:   // !42, !{...}, or !"foo"
2393     return ParseMetadataValue(ID, PFS);
2394   case lltok::APSInt:
2395     ID.APSIntVal = Lex.getAPSIntVal();
2396     ID.Kind = ValID::t_APSInt;
2397     break;
2398   case lltok::APFloat:
2399     ID.APFloatVal = Lex.getAPFloatVal();
2400     ID.Kind = ValID::t_APFloat;
2401     break;
2402   case lltok::kw_true:
2403     ID.ConstantVal = ConstantInt::getTrue(Context);
2404     ID.Kind = ValID::t_Constant;
2405     break;
2406   case lltok::kw_false:
2407     ID.ConstantVal = ConstantInt::getFalse(Context);
2408     ID.Kind = ValID::t_Constant;
2409     break;
2410   case lltok::kw_null: ID.Kind = ValID::t_Null; break;
2411   case lltok::kw_undef: ID.Kind = ValID::t_Undef; break;
2412   case lltok::kw_zeroinitializer: ID.Kind = ValID::t_Zero; break;
2413
2414   case lltok::lbrace: {
2415     // ValID ::= '{' ConstVector '}'
2416     Lex.Lex();
2417     SmallVector<Constant*, 16> Elts;
2418     if (ParseGlobalValueVector(Elts) ||
2419         ParseToken(lltok::rbrace, "expected end of struct constant"))
2420       return true;
2421
2422     ID.ConstantStructElts = new Constant*[Elts.size()];
2423     ID.UIntVal = Elts.size();
2424     memcpy(ID.ConstantStructElts, Elts.data(), Elts.size()*sizeof(Elts[0]));
2425     ID.Kind = ValID::t_ConstantStruct;
2426     return false;
2427   }
2428   case lltok::less: {
2429     // ValID ::= '<' ConstVector '>'         --> Vector.
2430     // ValID ::= '<' '{' ConstVector '}' '>' --> Packed Struct.
2431     Lex.Lex();
2432     bool isPackedStruct = EatIfPresent(lltok::lbrace);
2433
2434     SmallVector<Constant*, 16> Elts;
2435     LocTy FirstEltLoc = Lex.getLoc();
2436     if (ParseGlobalValueVector(Elts) ||
2437         (isPackedStruct &&
2438          ParseToken(lltok::rbrace, "expected end of packed struct")) ||
2439         ParseToken(lltok::greater, "expected end of constant"))
2440       return true;
2441
2442     if (isPackedStruct) {
2443       ID.ConstantStructElts = new Constant*[Elts.size()];
2444       memcpy(ID.ConstantStructElts, Elts.data(), Elts.size()*sizeof(Elts[0]));
2445       ID.UIntVal = Elts.size();
2446       ID.Kind = ValID::t_PackedConstantStruct;
2447       return false;
2448     }
2449
2450     if (Elts.empty())
2451       return Error(ID.Loc, "constant vector must not be empty");
2452
2453     if (!Elts[0]->getType()->isIntegerTy() &&
2454         !Elts[0]->getType()->isFloatingPointTy() &&
2455         !Elts[0]->getType()->isPointerTy())
2456       return Error(FirstEltLoc,
2457             "vector elements must have integer, pointer or floating point type");
2458
2459     // Verify that all the vector elements have the same type.
2460     for (unsigned i = 1, e = Elts.size(); i != e; ++i)
2461       if (Elts[i]->getType() != Elts[0]->getType())
2462         return Error(FirstEltLoc,
2463                      "vector element #" + Twine(i) +
2464                     " is not of type '" + getTypeString(Elts[0]->getType()));
2465
2466     ID.ConstantVal = ConstantVector::get(Elts);
2467     ID.Kind = ValID::t_Constant;
2468     return false;
2469   }
2470   case lltok::lsquare: {   // Array Constant
2471     Lex.Lex();
2472     SmallVector<Constant*, 16> Elts;
2473     LocTy FirstEltLoc = Lex.getLoc();
2474     if (ParseGlobalValueVector(Elts) ||
2475         ParseToken(lltok::rsquare, "expected end of array constant"))
2476       return true;
2477
2478     // Handle empty element.
2479     if (Elts.empty()) {
2480       // Use undef instead of an array because it's inconvenient to determine
2481       // the element type at this point, there being no elements to examine.
2482       ID.Kind = ValID::t_EmptyArray;
2483       return false;
2484     }
2485
2486     if (!Elts[0]->getType()->isFirstClassType())
2487       return Error(FirstEltLoc, "invalid array element type: " +
2488                    getTypeString(Elts[0]->getType()));
2489
2490     ArrayType *ATy = ArrayType::get(Elts[0]->getType(), Elts.size());
2491
2492     // Verify all elements are correct type!
2493     for (unsigned i = 0, e = Elts.size(); i != e; ++i) {
2494       if (Elts[i]->getType() != Elts[0]->getType())
2495         return Error(FirstEltLoc,
2496                      "array element #" + Twine(i) +
2497                      " is not of type '" + getTypeString(Elts[0]->getType()));
2498     }
2499
2500     ID.ConstantVal = ConstantArray::get(ATy, Elts);
2501     ID.Kind = ValID::t_Constant;
2502     return false;
2503   }
2504   case lltok::kw_c:  // c "foo"
2505     Lex.Lex();
2506     ID.ConstantVal = ConstantDataArray::getString(Context, Lex.getStrVal(),
2507                                                   false);
2508     if (ParseToken(lltok::StringConstant, "expected string")) return true;
2509     ID.Kind = ValID::t_Constant;
2510     return false;
2511
2512   case lltok::kw_asm: {
2513     // ValID ::= 'asm' SideEffect? AlignStack? IntelDialect? STRINGCONSTANT ','
2514     //             STRINGCONSTANT
2515     bool HasSideEffect, AlignStack, AsmDialect;
2516     Lex.Lex();
2517     if (ParseOptionalToken(lltok::kw_sideeffect, HasSideEffect) ||
2518         ParseOptionalToken(lltok::kw_alignstack, AlignStack) ||
2519         ParseOptionalToken(lltok::kw_inteldialect, AsmDialect) ||
2520         ParseStringConstant(ID.StrVal) ||
2521         ParseToken(lltok::comma, "expected comma in inline asm expression") ||
2522         ParseToken(lltok::StringConstant, "expected constraint string"))
2523       return true;
2524     ID.StrVal2 = Lex.getStrVal();
2525     ID.UIntVal = unsigned(HasSideEffect) | (unsigned(AlignStack)<<1) |
2526       (unsigned(AsmDialect)<<2);
2527     ID.Kind = ValID::t_InlineAsm;
2528     return false;
2529   }
2530
2531   case lltok::kw_blockaddress: {
2532     // ValID ::= 'blockaddress' '(' @foo ',' %bar ')'
2533     Lex.Lex();
2534
2535     ValID Fn, Label;
2536
2537     if (ParseToken(lltok::lparen, "expected '(' in block address expression") ||
2538         ParseValID(Fn) ||
2539         ParseToken(lltok::comma, "expected comma in block address expression")||
2540         ParseValID(Label) ||
2541         ParseToken(lltok::rparen, "expected ')' in block address expression"))
2542       return true;
2543
2544     if (Fn.Kind != ValID::t_GlobalID && Fn.Kind != ValID::t_GlobalName)
2545       return Error(Fn.Loc, "expected function name in blockaddress");
2546     if (Label.Kind != ValID::t_LocalID && Label.Kind != ValID::t_LocalName)
2547       return Error(Label.Loc, "expected basic block name in blockaddress");
2548
2549     // Try to find the function (but skip it if it's forward-referenced).
2550     GlobalValue *GV = nullptr;
2551     if (Fn.Kind == ValID::t_GlobalID) {
2552       if (Fn.UIntVal < NumberedVals.size())
2553         GV = NumberedVals[Fn.UIntVal];
2554     } else if (!ForwardRefVals.count(Fn.StrVal)) {
2555       GV = M->getNamedValue(Fn.StrVal);
2556     }
2557     Function *F = nullptr;
2558     if (GV) {
2559       // Confirm that it's actually a function with a definition.
2560       if (!isa<Function>(GV))
2561         return Error(Fn.Loc, "expected function name in blockaddress");
2562       F = cast<Function>(GV);
2563       if (F->isDeclaration())
2564         return Error(Fn.Loc, "cannot take blockaddress inside a declaration");
2565     }
2566
2567     if (!F) {
2568       // Make a global variable as a placeholder for this reference.
2569       GlobalValue *&FwdRef = ForwardRefBlockAddresses[Fn][Label];
2570       if (!FwdRef)
2571         FwdRef = new GlobalVariable(*M, Type::getInt8Ty(Context), false,
2572                                     GlobalValue::InternalLinkage, nullptr, "");
2573       ID.ConstantVal = FwdRef;
2574       ID.Kind = ValID::t_Constant;
2575       return false;
2576     }
2577
2578     // We found the function; now find the basic block.  Don't use PFS, since we
2579     // might be inside a constant expression.
2580     BasicBlock *BB;
2581     if (BlockAddressPFS && F == &BlockAddressPFS->getFunction()) {
2582       if (Label.Kind == ValID::t_LocalID)
2583         BB = BlockAddressPFS->GetBB(Label.UIntVal, Label.Loc);
2584       else
2585         BB = BlockAddressPFS->GetBB(Label.StrVal, Label.Loc);
2586       if (!BB)
2587         return Error(Label.Loc, "referenced value is not a basic block");
2588     } else {
2589       if (Label.Kind == ValID::t_LocalID)
2590         return Error(Label.Loc, "cannot take address of numeric label after "
2591                                 "the function is defined");
2592       BB = dyn_cast_or_null<BasicBlock>(
2593           F->getValueSymbolTable().lookup(Label.StrVal));
2594       if (!BB)
2595         return Error(Label.Loc, "referenced value is not a basic block");
2596     }
2597
2598     ID.ConstantVal = BlockAddress::get(F, BB);
2599     ID.Kind = ValID::t_Constant;
2600     return false;
2601   }
2602
2603   case lltok::kw_trunc:
2604   case lltok::kw_zext:
2605   case lltok::kw_sext:
2606   case lltok::kw_fptrunc:
2607   case lltok::kw_fpext:
2608   case lltok::kw_bitcast:
2609   case lltok::kw_addrspacecast:
2610   case lltok::kw_uitofp:
2611   case lltok::kw_sitofp:
2612   case lltok::kw_fptoui:
2613   case lltok::kw_fptosi:
2614   case lltok::kw_inttoptr:
2615   case lltok::kw_ptrtoint: {
2616     unsigned Opc = Lex.getUIntVal();
2617     Type *DestTy = nullptr;
2618     Constant *SrcVal;
2619     Lex.Lex();
2620     if (ParseToken(lltok::lparen, "expected '(' after constantexpr cast") ||
2621         ParseGlobalTypeAndValue(SrcVal) ||
2622         ParseToken(lltok::kw_to, "expected 'to' in constantexpr cast") ||
2623         ParseType(DestTy) ||
2624         ParseToken(lltok::rparen, "expected ')' at end of constantexpr cast"))
2625       return true;
2626     if (!CastInst::castIsValid((Instruction::CastOps)Opc, SrcVal, DestTy))
2627       return Error(ID.Loc, "invalid cast opcode for cast from '" +
2628                    getTypeString(SrcVal->getType()) + "' to '" +
2629                    getTypeString(DestTy) + "'");
2630     ID.ConstantVal = ConstantExpr::getCast((Instruction::CastOps)Opc,
2631                                                  SrcVal, DestTy);
2632     ID.Kind = ValID::t_Constant;
2633     return false;
2634   }
2635   case lltok::kw_extractvalue: {
2636     Lex.Lex();
2637     Constant *Val;
2638     SmallVector<unsigned, 4> Indices;
2639     if (ParseToken(lltok::lparen, "expected '(' in extractvalue constantexpr")||
2640         ParseGlobalTypeAndValue(Val) ||
2641         ParseIndexList(Indices) ||
2642         ParseToken(lltok::rparen, "expected ')' in extractvalue constantexpr"))
2643       return true;
2644
2645     if (!Val->getType()->isAggregateType())
2646       return Error(ID.Loc, "extractvalue operand must be aggregate type");
2647     if (!ExtractValueInst::getIndexedType(Val->getType(), Indices))
2648       return Error(ID.Loc, "invalid indices for extractvalue");
2649     ID.ConstantVal = ConstantExpr::getExtractValue(Val, Indices);
2650     ID.Kind = ValID::t_Constant;
2651     return false;
2652   }
2653   case lltok::kw_insertvalue: {
2654     Lex.Lex();
2655     Constant *Val0, *Val1;
2656     SmallVector<unsigned, 4> Indices;
2657     if (ParseToken(lltok::lparen, "expected '(' in insertvalue constantexpr")||
2658         ParseGlobalTypeAndValue(Val0) ||
2659         ParseToken(lltok::comma, "expected comma in insertvalue constantexpr")||
2660         ParseGlobalTypeAndValue(Val1) ||
2661         ParseIndexList(Indices) ||
2662         ParseToken(lltok::rparen, "expected ')' in insertvalue constantexpr"))
2663       return true;
2664     if (!Val0->getType()->isAggregateType())
2665       return Error(ID.Loc, "insertvalue operand must be aggregate type");
2666     if (!ExtractValueInst::getIndexedType(Val0->getType(), Indices))
2667       return Error(ID.Loc, "invalid indices for insertvalue");
2668     ID.ConstantVal = ConstantExpr::getInsertValue(Val0, Val1, Indices);
2669     ID.Kind = ValID::t_Constant;
2670     return false;
2671   }
2672   case lltok::kw_icmp:
2673   case lltok::kw_fcmp: {
2674     unsigned PredVal, Opc = Lex.getUIntVal();
2675     Constant *Val0, *Val1;
2676     Lex.Lex();
2677     if (ParseCmpPredicate(PredVal, Opc) ||
2678         ParseToken(lltok::lparen, "expected '(' in compare constantexpr") ||
2679         ParseGlobalTypeAndValue(Val0) ||
2680         ParseToken(lltok::comma, "expected comma in compare constantexpr") ||
2681         ParseGlobalTypeAndValue(Val1) ||
2682         ParseToken(lltok::rparen, "expected ')' in compare constantexpr"))
2683       return true;
2684
2685     if (Val0->getType() != Val1->getType())
2686       return Error(ID.Loc, "compare operands must have the same type");
2687
2688     CmpInst::Predicate Pred = (CmpInst::Predicate)PredVal;
2689
2690     if (Opc == Instruction::FCmp) {
2691       if (!Val0->getType()->isFPOrFPVectorTy())
2692         return Error(ID.Loc, "fcmp requires floating point operands");
2693       ID.ConstantVal = ConstantExpr::getFCmp(Pred, Val0, Val1);
2694     } else {
2695       assert(Opc == Instruction::ICmp && "Unexpected opcode for CmpInst!");
2696       if (!Val0->getType()->isIntOrIntVectorTy() &&
2697           !Val0->getType()->getScalarType()->isPointerTy())
2698         return Error(ID.Loc, "icmp requires pointer or integer operands");
2699       ID.ConstantVal = ConstantExpr::getICmp(Pred, Val0, Val1);
2700     }
2701     ID.Kind = ValID::t_Constant;
2702     return false;
2703   }
2704
2705   // Binary Operators.
2706   case lltok::kw_add:
2707   case lltok::kw_fadd:
2708   case lltok::kw_sub:
2709   case lltok::kw_fsub:
2710   case lltok::kw_mul:
2711   case lltok::kw_fmul:
2712   case lltok::kw_udiv:
2713   case lltok::kw_sdiv:
2714   case lltok::kw_fdiv:
2715   case lltok::kw_urem:
2716   case lltok::kw_srem:
2717   case lltok::kw_frem:
2718   case lltok::kw_shl:
2719   case lltok::kw_lshr:
2720   case lltok::kw_ashr: {
2721     bool NUW = false;
2722     bool NSW = false;
2723     bool Exact = false;
2724     unsigned Opc = Lex.getUIntVal();
2725     Constant *Val0, *Val1;
2726     Lex.Lex();
2727     LocTy ModifierLoc = Lex.getLoc();
2728     if (Opc == Instruction::Add || Opc == Instruction::Sub ||
2729         Opc == Instruction::Mul || Opc == Instruction::Shl) {
2730       if (EatIfPresent(lltok::kw_nuw))
2731         NUW = true;
2732       if (EatIfPresent(lltok::kw_nsw)) {
2733         NSW = true;
2734         if (EatIfPresent(lltok::kw_nuw))
2735           NUW = true;
2736       }
2737     } else if (Opc == Instruction::SDiv || Opc == Instruction::UDiv ||
2738                Opc == Instruction::LShr || Opc == Instruction::AShr) {
2739       if (EatIfPresent(lltok::kw_exact))
2740         Exact = true;
2741     }
2742     if (ParseToken(lltok::lparen, "expected '(' in binary constantexpr") ||
2743         ParseGlobalTypeAndValue(Val0) ||
2744         ParseToken(lltok::comma, "expected comma in binary constantexpr") ||
2745         ParseGlobalTypeAndValue(Val1) ||
2746         ParseToken(lltok::rparen, "expected ')' in binary constantexpr"))
2747       return true;
2748     if (Val0->getType() != Val1->getType())
2749       return Error(ID.Loc, "operands of constexpr must have same type");
2750     if (!Val0->getType()->isIntOrIntVectorTy()) {
2751       if (NUW)
2752         return Error(ModifierLoc, "nuw only applies to integer operations");
2753       if (NSW)
2754         return Error(ModifierLoc, "nsw only applies to integer operations");
2755     }
2756     // Check that the type is valid for the operator.
2757     switch (Opc) {
2758     case Instruction::Add:
2759     case Instruction::Sub:
2760     case Instruction::Mul:
2761     case Instruction::UDiv:
2762     case Instruction::SDiv:
2763     case Instruction::URem:
2764     case Instruction::SRem:
2765     case Instruction::Shl:
2766     case Instruction::AShr:
2767     case Instruction::LShr:
2768       if (!Val0->getType()->isIntOrIntVectorTy())
2769         return Error(ID.Loc, "constexpr requires integer operands");
2770       break;
2771     case Instruction::FAdd:
2772     case Instruction::FSub:
2773     case Instruction::FMul:
2774     case Instruction::FDiv:
2775     case Instruction::FRem:
2776       if (!Val0->getType()->isFPOrFPVectorTy())
2777         return Error(ID.Loc, "constexpr requires fp operands");
2778       break;
2779     default: llvm_unreachable("Unknown binary operator!");
2780     }
2781     unsigned Flags = 0;
2782     if (NUW)   Flags |= OverflowingBinaryOperator::NoUnsignedWrap;
2783     if (NSW)   Flags |= OverflowingBinaryOperator::NoSignedWrap;
2784     if (Exact) Flags |= PossiblyExactOperator::IsExact;
2785     Constant *C = ConstantExpr::get(Opc, Val0, Val1, Flags);
2786     ID.ConstantVal = C;
2787     ID.Kind = ValID::t_Constant;
2788     return false;
2789   }
2790
2791   // Logical Operations
2792   case lltok::kw_and:
2793   case lltok::kw_or:
2794   case lltok::kw_xor: {
2795     unsigned Opc = Lex.getUIntVal();
2796     Constant *Val0, *Val1;
2797     Lex.Lex();
2798     if (ParseToken(lltok::lparen, "expected '(' in logical constantexpr") ||
2799         ParseGlobalTypeAndValue(Val0) ||
2800         ParseToken(lltok::comma, "expected comma in logical constantexpr") ||
2801         ParseGlobalTypeAndValue(Val1) ||
2802         ParseToken(lltok::rparen, "expected ')' in logical constantexpr"))
2803       return true;
2804     if (Val0->getType() != Val1->getType())
2805       return Error(ID.Loc, "operands of constexpr must have same type");
2806     if (!Val0->getType()->isIntOrIntVectorTy())
2807       return Error(ID.Loc,
2808                    "constexpr requires integer or integer vector operands");
2809     ID.ConstantVal = ConstantExpr::get(Opc, Val0, Val1);
2810     ID.Kind = ValID::t_Constant;
2811     return false;
2812   }
2813
2814   case lltok::kw_getelementptr:
2815   case lltok::kw_shufflevector:
2816   case lltok::kw_insertelement:
2817   case lltok::kw_extractelement:
2818   case lltok::kw_select: {
2819     unsigned Opc = Lex.getUIntVal();
2820     SmallVector<Constant*, 16> Elts;
2821     bool InBounds = false;
2822     Lex.Lex();
2823     if (Opc == Instruction::GetElementPtr)
2824       InBounds = EatIfPresent(lltok::kw_inbounds);
2825     if (ParseToken(lltok::lparen, "expected '(' in constantexpr") ||
2826         ParseGlobalValueVector(Elts) ||
2827         ParseToken(lltok::rparen, "expected ')' in constantexpr"))
2828       return true;
2829
2830     if (Opc == Instruction::GetElementPtr) {
2831       if (Elts.size() == 0 ||
2832           !Elts[0]->getType()->getScalarType()->isPointerTy())
2833         return Error(ID.Loc, "getelementptr requires pointer operand");
2834
2835       ArrayRef<Constant *> Indices(Elts.begin() + 1, Elts.end());
2836       if (!GetElementPtrInst::getIndexedType(Elts[0]->getType(), Indices))
2837         return Error(ID.Loc, "invalid indices for getelementptr");
2838       ID.ConstantVal = ConstantExpr::getGetElementPtr(Elts[0], Indices,
2839                                                       InBounds);
2840     } else if (Opc == Instruction::Select) {
2841       if (Elts.size() != 3)
2842         return Error(ID.Loc, "expected three operands to select");
2843       if (const char *Reason = SelectInst::areInvalidOperands(Elts[0], Elts[1],
2844                                                               Elts[2]))
2845         return Error(ID.Loc, Reason);
2846       ID.ConstantVal = ConstantExpr::getSelect(Elts[0], Elts[1], Elts[2]);
2847     } else if (Opc == Instruction::ShuffleVector) {
2848       if (Elts.size() != 3)
2849         return Error(ID.Loc, "expected three operands to shufflevector");
2850       if (!ShuffleVectorInst::isValidOperands(Elts[0], Elts[1], Elts[2]))
2851         return Error(ID.Loc, "invalid operands to shufflevector");
2852       ID.ConstantVal =
2853                  ConstantExpr::getShuffleVector(Elts[0], Elts[1],Elts[2]);
2854     } else if (Opc == Instruction::ExtractElement) {
2855       if (Elts.size() != 2)
2856         return Error(ID.Loc, "expected two operands to extractelement");
2857       if (!ExtractElementInst::isValidOperands(Elts[0], Elts[1]))
2858         return Error(ID.Loc, "invalid extractelement operands");
2859       ID.ConstantVal = ConstantExpr::getExtractElement(Elts[0], Elts[1]);
2860     } else {
2861       assert(Opc == Instruction::InsertElement && "Unknown opcode");
2862       if (Elts.size() != 3)
2863       return Error(ID.Loc, "expected three operands to insertelement");
2864       if (!InsertElementInst::isValidOperands(Elts[0], Elts[1], Elts[2]))
2865         return Error(ID.Loc, "invalid insertelement operands");
2866       ID.ConstantVal =
2867                  ConstantExpr::getInsertElement(Elts[0], Elts[1],Elts[2]);
2868     }
2869
2870     ID.Kind = ValID::t_Constant;
2871     return false;
2872   }
2873   }
2874
2875   Lex.Lex();
2876   return false;
2877 }
2878
2879 /// ParseGlobalValue - Parse a global value with the specified type.
2880 bool LLParser::ParseGlobalValue(Type *Ty, Constant *&C) {
2881   C = nullptr;
2882   ValID ID;
2883   Value *V = nullptr;
2884   bool Parsed = ParseValID(ID) ||
2885                 ConvertValIDToValue(Ty, ID, V, nullptr);
2886   if (V && !(C = dyn_cast<Constant>(V)))
2887     return Error(ID.Loc, "global values must be constants");
2888   return Parsed;
2889 }
2890
2891 bool LLParser::ParseGlobalTypeAndValue(Constant *&V) {
2892   Type *Ty = nullptr;
2893   return ParseType(Ty) ||
2894          ParseGlobalValue(Ty, V);
2895 }
2896
2897 bool LLParser::parseOptionalComdat(Comdat *&C) {
2898   C = nullptr;
2899   if (!EatIfPresent(lltok::kw_comdat))
2900     return false;
2901   if (Lex.getKind() != lltok::ComdatVar)
2902     return TokError("expected comdat variable");
2903   LocTy Loc = Lex.getLoc();
2904   StringRef Name = Lex.getStrVal();
2905   C = getComdat(Name, Loc);
2906   Lex.Lex();
2907   return false;
2908 }
2909
2910 /// ParseGlobalValueVector
2911 ///   ::= /*empty*/
2912 ///   ::= TypeAndValue (',' TypeAndValue)*
2913 bool LLParser::ParseGlobalValueVector(SmallVectorImpl<Constant *> &Elts) {
2914   // Empty list.
2915   if (Lex.getKind() == lltok::rbrace ||
2916       Lex.getKind() == lltok::rsquare ||
2917       Lex.getKind() == lltok::greater ||
2918       Lex.getKind() == lltok::rparen)
2919     return false;
2920
2921   Constant *C;
2922   if (ParseGlobalTypeAndValue(C)) return true;
2923   Elts.push_back(C);
2924
2925   while (EatIfPresent(lltok::comma)) {
2926     if (ParseGlobalTypeAndValue(C)) return true;
2927     Elts.push_back(C);
2928   }
2929
2930   return false;
2931 }
2932
2933 bool LLParser::ParseMetadataListValue(ValID &ID, PerFunctionState *PFS) {
2934   assert(Lex.getKind() == lltok::lbrace);
2935   Lex.Lex();
2936
2937   SmallVector<Value*, 16> Elts;
2938   if (ParseMDNodeVector(Elts, PFS) ||
2939       ParseToken(lltok::rbrace, "expected end of metadata node"))
2940     return true;
2941
2942   ID.MDNodeVal = MDNode::get(Context, Elts);
2943   ID.Kind = ValID::t_MDNode;
2944   return false;
2945 }
2946
2947 /// ParseMetadataValue
2948 ///  ::= !42
2949 ///  ::= !{...}
2950 ///  ::= !"string"
2951 bool LLParser::ParseMetadataValue(ValID &ID, PerFunctionState *PFS) {
2952   assert(Lex.getKind() == lltok::exclaim);
2953   Lex.Lex();
2954
2955   // MDNode:
2956   // !{ ... }
2957   if (Lex.getKind() == lltok::lbrace)
2958     return ParseMetadataListValue(ID, PFS);
2959
2960   // Standalone metadata reference
2961   // !42
2962   if (Lex.getKind() == lltok::APSInt) {
2963     if (ParseMDNodeID(ID.MDNodeVal)) return true;
2964     ID.Kind = ValID::t_MDNode;
2965     return false;
2966   }
2967
2968   // MDString:
2969   //   ::= '!' STRINGCONSTANT
2970   if (ParseMDString(ID.MDStringVal)) return true;
2971   ID.Kind = ValID::t_MDString;
2972   return false;
2973 }
2974
2975
2976 //===----------------------------------------------------------------------===//
2977 // Function Parsing.
2978 //===----------------------------------------------------------------------===//
2979
2980 bool LLParser::ConvertValIDToValue(Type *Ty, ValID &ID, Value *&V,
2981                                    PerFunctionState *PFS) {
2982   if (Ty->isFunctionTy())
2983     return Error(ID.Loc, "functions are not values, refer to them as pointers");
2984
2985   switch (ID.Kind) {
2986   case ValID::t_LocalID:
2987     if (!PFS) return Error(ID.Loc, "invalid use of function-local name");
2988     V = PFS->GetVal(ID.UIntVal, Ty, ID.Loc);
2989     return V == nullptr;
2990   case ValID::t_LocalName:
2991     if (!PFS) return Error(ID.Loc, "invalid use of function-local name");
2992     V = PFS->GetVal(ID.StrVal, Ty, ID.Loc);
2993     return V == nullptr;
2994   case ValID::t_InlineAsm: {
2995     PointerType *PTy = dyn_cast<PointerType>(Ty);
2996     FunctionType *FTy =
2997       PTy ? dyn_cast<FunctionType>(PTy->getElementType()) : nullptr;
2998     if (!FTy || !InlineAsm::Verify(FTy, ID.StrVal2))
2999       return Error(ID.Loc, "invalid type for inline asm constraint string");
3000     V = InlineAsm::get(FTy, ID.StrVal, ID.StrVal2, ID.UIntVal&1,
3001                        (ID.UIntVal>>1)&1, (InlineAsm::AsmDialect(ID.UIntVal>>2)));
3002     return false;
3003   }
3004   case ValID::t_MDNode:
3005     if (!Ty->isMetadataTy())
3006       return Error(ID.Loc, "metadata value must have metadata type");
3007     V = ID.MDNodeVal;
3008     return false;
3009   case ValID::t_MDString:
3010     if (!Ty->isMetadataTy())
3011       return Error(ID.Loc, "metadata value must have metadata type");
3012     V = ID.MDStringVal;
3013     return false;
3014   case ValID::t_GlobalName:
3015     V = GetGlobalVal(ID.StrVal, Ty, ID.Loc);
3016     return V == nullptr;
3017   case ValID::t_GlobalID:
3018     V = GetGlobalVal(ID.UIntVal, Ty, ID.Loc);
3019     return V == nullptr;
3020   case ValID::t_APSInt:
3021     if (!Ty->isIntegerTy())
3022       return Error(ID.Loc, "integer constant must have integer type");
3023     ID.APSIntVal = ID.APSIntVal.extOrTrunc(Ty->getPrimitiveSizeInBits());
3024     V = ConstantInt::get(Context, ID.APSIntVal);
3025     return false;
3026   case ValID::t_APFloat:
3027     if (!Ty->isFloatingPointTy() ||
3028         !ConstantFP::isValueValidForType(Ty, ID.APFloatVal))
3029       return Error(ID.Loc, "floating point constant invalid for type");
3030
3031     // The lexer has no type info, so builds all half, float, and double FP
3032     // constants as double.  Fix this here.  Long double does not need this.
3033     if (&ID.APFloatVal.getSemantics() == &APFloat::IEEEdouble) {
3034       bool Ignored;
3035       if (Ty->isHalfTy())
3036         ID.APFloatVal.convert(APFloat::IEEEhalf, APFloat::rmNearestTiesToEven,
3037                               &Ignored);
3038       else if (Ty->isFloatTy())
3039         ID.APFloatVal.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven,
3040                               &Ignored);
3041     }
3042     V = ConstantFP::get(Context, ID.APFloatVal);
3043
3044     if (V->getType() != Ty)
3045       return Error(ID.Loc, "floating point constant does not have type '" +
3046                    getTypeString(Ty) + "'");
3047
3048     return false;
3049   case ValID::t_Null:
3050     if (!Ty->isPointerTy())
3051       return Error(ID.Loc, "null must be a pointer type");
3052     V = ConstantPointerNull::get(cast<PointerType>(Ty));
3053     return false;
3054   case ValID::t_Undef:
3055     // FIXME: LabelTy should not be a first-class type.
3056     if (!Ty->isFirstClassType() || Ty->isLabelTy())
3057       return Error(ID.Loc, "invalid type for undef constant");
3058     V = UndefValue::get(Ty);
3059     return false;
3060   case ValID::t_EmptyArray:
3061     if (!Ty->isArrayTy() || cast<ArrayType>(Ty)->getNumElements() != 0)
3062       return Error(ID.Loc, "invalid empty array initializer");
3063     V = UndefValue::get(Ty);
3064     return false;
3065   case ValID::t_Zero:
3066     // FIXME: LabelTy should not be a first-class type.
3067     if (!Ty->isFirstClassType() || Ty->isLabelTy())
3068       return Error(ID.Loc, "invalid type for null constant");
3069     V = Constant::getNullValue(Ty);
3070     return false;
3071   case ValID::t_Constant:
3072     if (ID.ConstantVal->getType() != Ty)
3073       return Error(ID.Loc, "constant expression type mismatch");
3074
3075     V = ID.ConstantVal;
3076     return false;
3077   case ValID::t_ConstantStruct:
3078   case ValID::t_PackedConstantStruct:
3079     if (StructType *ST = dyn_cast<StructType>(Ty)) {
3080       if (ST->getNumElements() != ID.UIntVal)
3081         return Error(ID.Loc,
3082                      "initializer with struct type has wrong # elements");
3083       if (ST->isPacked() != (ID.Kind == ValID::t_PackedConstantStruct))
3084         return Error(ID.Loc, "packed'ness of initializer and type don't match");
3085
3086       // Verify that the elements are compatible with the structtype.
3087       for (unsigned i = 0, e = ID.UIntVal; i != e; ++i)
3088         if (ID.ConstantStructElts[i]->getType() != ST->getElementType(i))
3089           return Error(ID.Loc, "element " + Twine(i) +
3090                     " of struct initializer doesn't match struct element type");
3091
3092       V = ConstantStruct::get(ST, makeArrayRef(ID.ConstantStructElts,
3093                                                ID.UIntVal));
3094     } else
3095       return Error(ID.Loc, "constant expression type mismatch");
3096     return false;
3097   }
3098   llvm_unreachable("Invalid ValID");
3099 }
3100
3101 bool LLParser::ParseValue(Type *Ty, Value *&V, PerFunctionState *PFS) {
3102   V = nullptr;
3103   ValID ID;
3104   return ParseValID(ID, PFS) ||
3105          ConvertValIDToValue(Ty, ID, V, PFS);
3106 }
3107
3108 bool LLParser::ParseTypeAndValue(Value *&V, PerFunctionState *PFS) {
3109   Type *Ty = nullptr;
3110   return ParseType(Ty) ||
3111          ParseValue(Ty, V, PFS);
3112 }
3113
3114 bool LLParser::ParseTypeAndBasicBlock(BasicBlock *&BB, LocTy &Loc,
3115                                       PerFunctionState &PFS) {
3116   Value *V;
3117   Loc = Lex.getLoc();
3118   if (ParseTypeAndValue(V, PFS)) return true;
3119   if (!isa<BasicBlock>(V))
3120     return Error(Loc, "expected a basic block");
3121   BB = cast<BasicBlock>(V);
3122   return false;
3123 }
3124
3125
3126 /// FunctionHeader
3127 ///   ::= OptionalLinkage OptionalVisibility OptionalCallingConv OptRetAttrs
3128 ///       OptUnnamedAddr Type GlobalName '(' ArgList ')' OptFuncAttrs OptSection
3129 ///       OptionalAlign OptGC OptionalPrefix OptionalPrologue
3130 bool LLParser::ParseFunctionHeader(Function *&Fn, bool isDefine) {
3131   // Parse the linkage.
3132   LocTy LinkageLoc = Lex.getLoc();
3133   unsigned Linkage;
3134
3135   unsigned Visibility;
3136   unsigned DLLStorageClass;
3137   AttrBuilder RetAttrs;
3138   unsigned CC;
3139   Type *RetType = nullptr;
3140   LocTy RetTypeLoc = Lex.getLoc();
3141   if (ParseOptionalLinkage(Linkage) ||
3142       ParseOptionalVisibility(Visibility) ||
3143       ParseOptionalDLLStorageClass(DLLStorageClass) ||
3144       ParseOptionalCallingConv(CC) ||
3145       ParseOptionalReturnAttrs(RetAttrs) ||
3146       ParseType(RetType, RetTypeLoc, true /*void allowed*/))
3147     return true;
3148
3149   // Verify that the linkage is ok.
3150   switch ((GlobalValue::LinkageTypes)Linkage) {
3151   case GlobalValue::ExternalLinkage:
3152     break; // always ok.
3153   case GlobalValue::ExternalWeakLinkage:
3154     if (isDefine)
3155       return Error(LinkageLoc, "invalid linkage for function definition");
3156     break;
3157   case GlobalValue::PrivateLinkage:
3158   case GlobalValue::InternalLinkage:
3159   case GlobalValue::AvailableExternallyLinkage:
3160   case GlobalValue::LinkOnceAnyLinkage:
3161   case GlobalValue::LinkOnceODRLinkage:
3162   case GlobalValue::WeakAnyLinkage:
3163   case GlobalValue::WeakODRLinkage:
3164     if (!isDefine)
3165       return Error(LinkageLoc, "invalid linkage for function declaration");
3166     break;
3167   case GlobalValue::AppendingLinkage:
3168   case GlobalValue::CommonLinkage:
3169     return Error(LinkageLoc, "invalid function linkage type");
3170   }
3171
3172   if (!isValidVisibilityForLinkage(Visibility, Linkage))
3173     return Error(LinkageLoc,
3174                  "symbol with local linkage must have default visibility");
3175
3176   if (!FunctionType::isValidReturnType(RetType))
3177     return Error(RetTypeLoc, "invalid function return type");
3178
3179   LocTy NameLoc = Lex.getLoc();
3180
3181   std::string FunctionName;
3182   if (Lex.getKind() == lltok::GlobalVar) {
3183     FunctionName = Lex.getStrVal();
3184   } else if (Lex.getKind() == lltok::GlobalID) {     // @42 is ok.
3185     unsigned NameID = Lex.getUIntVal();
3186
3187     if (NameID != NumberedVals.size())
3188       return TokError("function expected to be numbered '%" +
3189                       Twine(NumberedVals.size()) + "'");
3190   } else {
3191     return TokError("expected function name");
3192   }
3193
3194   Lex.Lex();
3195
3196   if (Lex.getKind() != lltok::lparen)
3197     return TokError("expected '(' in function argument list");
3198
3199   SmallVector<ArgInfo, 8> ArgList;
3200   bool isVarArg;
3201   AttrBuilder FuncAttrs;
3202   std::vector<unsigned> FwdRefAttrGrps;
3203   LocTy BuiltinLoc;
3204   std::string Section;
3205   unsigned Alignment;
3206   std::string GC;
3207   bool UnnamedAddr;
3208   LocTy UnnamedAddrLoc;
3209   Constant *Prefix = nullptr;
3210   Constant *Prologue = nullptr;
3211   Comdat *C;
3212
3213   if (ParseArgumentList(ArgList, isVarArg) ||
3214       ParseOptionalToken(lltok::kw_unnamed_addr, UnnamedAddr,
3215                          &UnnamedAddrLoc) ||
3216       ParseFnAttributeValuePairs(FuncAttrs, FwdRefAttrGrps, false,
3217                                  BuiltinLoc) ||
3218       (EatIfPresent(lltok::kw_section) &&
3219        ParseStringConstant(Section)) ||
3220       parseOptionalComdat(C) ||
3221       ParseOptionalAlignment(Alignment) ||
3222       (EatIfPresent(lltok::kw_gc) &&
3223        ParseStringConstant(GC)) ||
3224       (EatIfPresent(lltok::kw_prefix) &&
3225        ParseGlobalTypeAndValue(Prefix)) ||
3226       (EatIfPresent(lltok::kw_prologue) &&
3227        ParseGlobalTypeAndValue(Prologue)))
3228     return true;
3229
3230   if (FuncAttrs.contains(Attribute::Builtin))
3231     return Error(BuiltinLoc, "'builtin' attribute not valid on function");
3232
3233   // If the alignment was parsed as an attribute, move to the alignment field.
3234   if (FuncAttrs.hasAlignmentAttr()) {
3235     Alignment = FuncAttrs.getAlignment();
3236     FuncAttrs.removeAttribute(Attribute::Alignment);
3237   }
3238
3239   // Okay, if we got here, the function is syntactically valid.  Convert types
3240   // and do semantic checks.
3241   std::vector<Type*> ParamTypeList;
3242   SmallVector<AttributeSet, 8> Attrs;
3243
3244   if (RetAttrs.hasAttributes())
3245     Attrs.push_back(AttributeSet::get(RetType->getContext(),
3246                                       AttributeSet::ReturnIndex,
3247                                       RetAttrs));
3248
3249   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
3250     ParamTypeList.push_back(ArgList[i].Ty);
3251     if (ArgList[i].Attrs.hasAttributes(i + 1)) {
3252       AttrBuilder B(ArgList[i].Attrs, i + 1);
3253       Attrs.push_back(AttributeSet::get(RetType->getContext(), i + 1, B));
3254     }
3255   }
3256
3257   if (FuncAttrs.hasAttributes())
3258     Attrs.push_back(AttributeSet::get(RetType->getContext(),
3259                                       AttributeSet::FunctionIndex,
3260                                       FuncAttrs));
3261
3262   AttributeSet PAL = AttributeSet::get(Context, Attrs);
3263
3264   if (PAL.hasAttribute(1, Attribute::StructRet) && !RetType->isVoidTy())
3265     return Error(RetTypeLoc, "functions with 'sret' argument must return void");
3266
3267   FunctionType *FT =
3268     FunctionType::get(RetType, ParamTypeList, isVarArg);
3269   PointerType *PFT = PointerType::getUnqual(FT);
3270
3271   Fn = nullptr;
3272   if (!FunctionName.empty()) {
3273     // If this was a definition of a forward reference, remove the definition
3274     // from the forward reference table and fill in the forward ref.
3275     std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator FRVI =
3276       ForwardRefVals.find(FunctionName);
3277     if (FRVI != ForwardRefVals.end()) {
3278       Fn = M->getFunction(FunctionName);
3279       if (!Fn)
3280         return Error(FRVI->second.second, "invalid forward reference to "
3281                      "function as global value!");
3282       if (Fn->getType() != PFT)
3283         return Error(FRVI->second.second, "invalid forward reference to "
3284                      "function '" + FunctionName + "' with wrong type!");
3285
3286       ForwardRefVals.erase(FRVI);
3287     } else if ((Fn = M->getFunction(FunctionName))) {
3288       // Reject redefinitions.
3289       return Error(NameLoc, "invalid redefinition of function '" +
3290                    FunctionName + "'");
3291     } else if (M->getNamedValue(FunctionName)) {
3292       return Error(NameLoc, "redefinition of function '@" + FunctionName + "'");
3293     }
3294
3295   } else {
3296     // If this is a definition of a forward referenced function, make sure the
3297     // types agree.
3298     std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator I
3299       = ForwardRefValIDs.find(NumberedVals.size());
3300     if (I != ForwardRefValIDs.end()) {
3301       Fn = cast<Function>(I->second.first);
3302       if (Fn->getType() != PFT)
3303         return Error(NameLoc, "type of definition and forward reference of '@" +
3304                      Twine(NumberedVals.size()) + "' disagree");
3305       ForwardRefValIDs.erase(I);
3306     }
3307   }
3308
3309   if (!Fn)
3310     Fn = Function::Create(FT, GlobalValue::ExternalLinkage, FunctionName, M);
3311   else // Move the forward-reference to the correct spot in the module.
3312     M->getFunctionList().splice(M->end(), M->getFunctionList(), Fn);
3313
3314   if (FunctionName.empty())
3315     NumberedVals.push_back(Fn);
3316
3317   Fn->setLinkage((GlobalValue::LinkageTypes)Linkage);
3318   Fn->setVisibility((GlobalValue::VisibilityTypes)Visibility);
3319   Fn->setDLLStorageClass((GlobalValue::DLLStorageClassTypes)DLLStorageClass);
3320   Fn->setCallingConv(CC);
3321   Fn->setAttributes(PAL);
3322   Fn->setUnnamedAddr(UnnamedAddr);
3323   Fn->setAlignment(Alignment);
3324   Fn->setSection(Section);
3325   Fn->setComdat(C);
3326   if (!GC.empty()) Fn->setGC(GC.c_str());
3327   Fn->setPrefixData(Prefix);
3328   Fn->setPrologueData(Prologue);
3329   ForwardRefAttrGroups[Fn] = FwdRefAttrGrps;
3330
3331   // Add all of the arguments we parsed to the function.
3332   Function::arg_iterator ArgIt = Fn->arg_begin();
3333   for (unsigned i = 0, e = ArgList.size(); i != e; ++i, ++ArgIt) {
3334     // If the argument has a name, insert it into the argument symbol table.
3335     if (ArgList[i].Name.empty()) continue;
3336
3337     // Set the name, if it conflicted, it will be auto-renamed.
3338     ArgIt->setName(ArgList[i].Name);
3339
3340     if (ArgIt->getName() != ArgList[i].Name)
3341       return Error(ArgList[i].Loc, "redefinition of argument '%" +
3342                    ArgList[i].Name + "'");
3343   }
3344
3345   if (isDefine)
3346     return false;
3347
3348   // Check the declaration has no block address forward references.
3349   ValID ID;
3350   if (FunctionName.empty()) {
3351     ID.Kind = ValID::t_GlobalID;
3352     ID.UIntVal = NumberedVals.size() - 1;
3353   } else {
3354     ID.Kind = ValID::t_GlobalName;
3355     ID.StrVal = FunctionName;
3356   }
3357   auto Blocks = ForwardRefBlockAddresses.find(ID);
3358   if (Blocks != ForwardRefBlockAddresses.end())
3359     return Error(Blocks->first.Loc,
3360                  "cannot take blockaddress inside a declaration");
3361   return false;
3362 }
3363
3364 bool LLParser::PerFunctionState::resolveForwardRefBlockAddresses() {
3365   ValID ID;
3366   if (FunctionNumber == -1) {
3367     ID.Kind = ValID::t_GlobalName;
3368     ID.StrVal = F.getName();
3369   } else {
3370     ID.Kind = ValID::t_GlobalID;
3371     ID.UIntVal = FunctionNumber;
3372   }
3373
3374   auto Blocks = P.ForwardRefBlockAddresses.find(ID);
3375   if (Blocks == P.ForwardRefBlockAddresses.end())
3376     return false;
3377
3378   for (const auto &I : Blocks->second) {
3379     const ValID &BBID = I.first;
3380     GlobalValue *GV = I.second;
3381
3382     assert((BBID.Kind == ValID::t_LocalID || BBID.Kind == ValID::t_LocalName) &&
3383            "Expected local id or name");
3384     BasicBlock *BB;
3385     if (BBID.Kind == ValID::t_LocalName)
3386       BB = GetBB(BBID.StrVal, BBID.Loc);
3387     else
3388       BB = GetBB(BBID.UIntVal, BBID.Loc);
3389     if (!BB)
3390       return P.Error(BBID.Loc, "referenced value is not a basic block");
3391
3392     GV->replaceAllUsesWith(BlockAddress::get(&F, BB));
3393     GV->eraseFromParent();
3394   }
3395
3396   P.ForwardRefBlockAddresses.erase(Blocks);
3397   return false;
3398 }
3399
3400 /// ParseFunctionBody
3401 ///   ::= '{' BasicBlock+ UseListOrderDirective* '}'
3402 bool LLParser::ParseFunctionBody(Function &Fn) {
3403   if (Lex.getKind() != lltok::lbrace)
3404     return TokError("expected '{' in function body");
3405   Lex.Lex();  // eat the {.
3406
3407   int FunctionNumber = -1;
3408   if (!Fn.hasName()) FunctionNumber = NumberedVals.size()-1;
3409
3410   PerFunctionState PFS(*this, Fn, FunctionNumber);
3411
3412   // Resolve block addresses and allow basic blocks to be forward-declared
3413   // within this function.
3414   if (PFS.resolveForwardRefBlockAddresses())
3415     return true;
3416   SaveAndRestore<PerFunctionState *> ScopeExit(BlockAddressPFS, &PFS);
3417
3418   // We need at least one basic block.
3419   if (Lex.getKind() == lltok::rbrace || Lex.getKind() == lltok::kw_uselistorder)
3420     return TokError("function body requires at least one basic block");
3421
3422   while (Lex.getKind() != lltok::rbrace &&
3423          Lex.getKind() != lltok::kw_uselistorder)
3424     if (ParseBasicBlock(PFS)) return true;
3425
3426   while (Lex.getKind() != lltok::rbrace)
3427     if (ParseUseListOrder(&PFS))
3428       return true;
3429
3430   // Eat the }.
3431   Lex.Lex();
3432
3433   // Verify function is ok.
3434   return PFS.FinishFunction();
3435 }
3436
3437 /// ParseBasicBlock
3438 ///   ::= LabelStr? Instruction*
3439 bool LLParser::ParseBasicBlock(PerFunctionState &PFS) {
3440   // If this basic block starts out with a name, remember it.
3441   std::string Name;
3442   LocTy NameLoc = Lex.getLoc();
3443   if (Lex.getKind() == lltok::LabelStr) {
3444     Name = Lex.getStrVal();
3445     Lex.Lex();
3446   }
3447
3448   BasicBlock *BB = PFS.DefineBB(Name, NameLoc);
3449   if (!BB) return true;
3450
3451   std::string NameStr;
3452
3453   // Parse the instructions in this block until we get a terminator.
3454   Instruction *Inst;
3455   do {
3456     // This instruction may have three possibilities for a name: a) none
3457     // specified, b) name specified "%foo =", c) number specified: "%4 =".
3458     LocTy NameLoc = Lex.getLoc();
3459     int NameID = -1;
3460     NameStr = "";
3461
3462     if (Lex.getKind() == lltok::LocalVarID) {
3463       NameID = Lex.getUIntVal();
3464       Lex.Lex();
3465       if (ParseToken(lltok::equal, "expected '=' after instruction id"))
3466         return true;
3467     } else if (Lex.getKind() == lltok::LocalVar) {
3468       NameStr = Lex.getStrVal();
3469       Lex.Lex();
3470       if (ParseToken(lltok::equal, "expected '=' after instruction name"))
3471         return true;
3472     }
3473
3474     switch (ParseInstruction(Inst, BB, PFS)) {
3475     default: llvm_unreachable("Unknown ParseInstruction result!");
3476     case InstError: return true;
3477     case InstNormal:
3478       BB->getInstList().push_back(Inst);
3479
3480       // With a normal result, we check to see if the instruction is followed by
3481       // a comma and metadata.
3482       if (EatIfPresent(lltok::comma))
3483         if (ParseInstructionMetadata(Inst, &PFS))
3484           return true;
3485       break;
3486     case InstExtraComma:
3487       BB->getInstList().push_back(Inst);
3488
3489       // If the instruction parser ate an extra comma at the end of it, it
3490       // *must* be followed by metadata.
3491       if (ParseInstructionMetadata(Inst, &PFS))
3492         return true;
3493       break;
3494     }
3495
3496     // Set the name on the instruction.
3497     if (PFS.SetInstName(NameID, NameStr, NameLoc, Inst)) return true;
3498   } while (!isa<TerminatorInst>(Inst));
3499
3500   return false;
3501 }
3502
3503 //===----------------------------------------------------------------------===//
3504 // Instruction Parsing.
3505 //===----------------------------------------------------------------------===//
3506
3507 /// ParseInstruction - Parse one of the many different instructions.
3508 ///
3509 int LLParser::ParseInstruction(Instruction *&Inst, BasicBlock *BB,
3510                                PerFunctionState &PFS) {
3511   lltok::Kind Token = Lex.getKind();
3512   if (Token == lltok::Eof)
3513     return TokError("found end of file when expecting more instructions");
3514   LocTy Loc = Lex.getLoc();
3515   unsigned KeywordVal = Lex.getUIntVal();
3516   Lex.Lex();  // Eat the keyword.
3517
3518   switch (Token) {
3519   default:                    return Error(Loc, "expected instruction opcode");
3520   // Terminator Instructions.
3521   case lltok::kw_unreachable: Inst = new UnreachableInst(Context); return false;
3522   case lltok::kw_ret:         return ParseRet(Inst, BB, PFS);
3523   case lltok::kw_br:          return ParseBr(Inst, PFS);
3524   case lltok::kw_switch:      return ParseSwitch(Inst, PFS);
3525   case lltok::kw_indirectbr:  return ParseIndirectBr(Inst, PFS);
3526   case lltok::kw_invoke:      return ParseInvoke(Inst, PFS);
3527   case lltok::kw_resume:      return ParseResume(Inst, PFS);
3528   // Binary Operators.
3529   case lltok::kw_add:
3530   case lltok::kw_sub:
3531   case lltok::kw_mul:
3532   case lltok::kw_shl: {
3533     bool NUW = EatIfPresent(lltok::kw_nuw);
3534     bool NSW = EatIfPresent(lltok::kw_nsw);
3535     if (!NUW) NUW = EatIfPresent(lltok::kw_nuw);
3536
3537     if (ParseArithmetic(Inst, PFS, KeywordVal, 1)) return true;
3538
3539     if (NUW) cast<BinaryOperator>(Inst)->setHasNoUnsignedWrap(true);
3540     if (NSW) cast<BinaryOperator>(Inst)->setHasNoSignedWrap(true);
3541     return false;
3542   }
3543   case lltok::kw_fadd:
3544   case lltok::kw_fsub:
3545   case lltok::kw_fmul:
3546   case lltok::kw_fdiv:
3547   case lltok::kw_frem: {
3548     FastMathFlags FMF = EatFastMathFlagsIfPresent();
3549     int Res = ParseArithmetic(Inst, PFS, KeywordVal, 2);
3550     if (Res != 0)
3551       return Res;
3552     if (FMF.any())
3553       Inst->setFastMathFlags(FMF);
3554     return 0;
3555   }
3556
3557   case lltok::kw_sdiv:
3558   case lltok::kw_udiv:
3559   case lltok::kw_lshr:
3560   case lltok::kw_ashr: {
3561     bool Exact = EatIfPresent(lltok::kw_exact);
3562
3563     if (ParseArithmetic(Inst, PFS, KeywordVal, 1)) return true;
3564     if (Exact) cast<BinaryOperator>(Inst)->setIsExact(true);
3565     return false;
3566   }
3567
3568   case lltok::kw_urem:
3569   case lltok::kw_srem:   return ParseArithmetic(Inst, PFS, KeywordVal, 1);
3570   case lltok::kw_and:
3571   case lltok::kw_or:
3572   case lltok::kw_xor:    return ParseLogical(Inst, PFS, KeywordVal);
3573   case lltok::kw_icmp:
3574   case lltok::kw_fcmp:   return ParseCompare(Inst, PFS, KeywordVal);
3575   // Casts.
3576   case lltok::kw_trunc:
3577   case lltok::kw_zext:
3578   case lltok::kw_sext:
3579   case lltok::kw_fptrunc:
3580   case lltok::kw_fpext:
3581   case lltok::kw_bitcast:
3582   case lltok::kw_addrspacecast:
3583   case lltok::kw_uitofp:
3584   case lltok::kw_sitofp:
3585   case lltok::kw_fptoui:
3586   case lltok::kw_fptosi:
3587   case lltok::kw_inttoptr:
3588   case lltok::kw_ptrtoint:       return ParseCast(Inst, PFS, KeywordVal);
3589   // Other.
3590   case lltok::kw_select:         return ParseSelect(Inst, PFS);
3591   case lltok::kw_va_arg:         return ParseVA_Arg(Inst, PFS);
3592   case lltok::kw_extractelement: return ParseExtractElement(Inst, PFS);
3593   case lltok::kw_insertelement:  return ParseInsertElement(Inst, PFS);
3594   case lltok::kw_shufflevector:  return ParseShuffleVector(Inst, PFS);
3595   case lltok::kw_phi:            return ParsePHI(Inst, PFS);
3596   case lltok::kw_landingpad:     return ParseLandingPad(Inst, PFS);
3597   // Call.
3598   case lltok::kw_call:     return ParseCall(Inst, PFS, CallInst::TCK_None);
3599   case lltok::kw_tail:     return ParseCall(Inst, PFS, CallInst::TCK_Tail);
3600   case lltok::kw_musttail: return ParseCall(Inst, PFS, CallInst::TCK_MustTail);
3601   // Memory.
3602   case lltok::kw_alloca:         return ParseAlloc(Inst, PFS);
3603   case lltok::kw_load:           return ParseLoad(Inst, PFS);
3604   case lltok::kw_store:          return ParseStore(Inst, PFS);
3605   case lltok::kw_cmpxchg:        return ParseCmpXchg(Inst, PFS);
3606   case lltok::kw_atomicrmw:      return ParseAtomicRMW(Inst, PFS);
3607   case lltok::kw_fence:          return ParseFence(Inst, PFS);
3608   case lltok::kw_getelementptr: return ParseGetElementPtr(Inst, PFS);
3609   case lltok::kw_extractvalue:  return ParseExtractValue(Inst, PFS);
3610   case lltok::kw_insertvalue:   return ParseInsertValue(Inst, PFS);
3611   }
3612 }
3613
3614 /// ParseCmpPredicate - Parse an integer or fp predicate, based on Kind.
3615 bool LLParser::ParseCmpPredicate(unsigned &P, unsigned Opc) {
3616   if (Opc == Instruction::FCmp) {
3617     switch (Lex.getKind()) {
3618     default: return TokError("expected fcmp predicate (e.g. 'oeq')");
3619     case lltok::kw_oeq: P = CmpInst::FCMP_OEQ; break;
3620     case lltok::kw_one: P = CmpInst::FCMP_ONE; break;
3621     case lltok::kw_olt: P = CmpInst::FCMP_OLT; break;
3622     case lltok::kw_ogt: P = CmpInst::FCMP_OGT; break;
3623     case lltok::kw_ole: P = CmpInst::FCMP_OLE; break;
3624     case lltok::kw_oge: P = CmpInst::FCMP_OGE; break;
3625     case lltok::kw_ord: P = CmpInst::FCMP_ORD; break;
3626     case lltok::kw_uno: P = CmpInst::FCMP_UNO; break;
3627     case lltok::kw_ueq: P = CmpInst::FCMP_UEQ; break;
3628     case lltok::kw_une: P = CmpInst::FCMP_UNE; break;
3629     case lltok::kw_ult: P = CmpInst::FCMP_ULT; break;
3630     case lltok::kw_ugt: P = CmpInst::FCMP_UGT; break;
3631     case lltok::kw_ule: P = CmpInst::FCMP_ULE; break;
3632     case lltok::kw_uge: P = CmpInst::FCMP_UGE; break;
3633     case lltok::kw_true: P = CmpInst::FCMP_TRUE; break;
3634     case lltok::kw_false: P = CmpInst::FCMP_FALSE; break;
3635     }
3636   } else {
3637     switch (Lex.getKind()) {
3638     default: return TokError("expected icmp predicate (e.g. 'eq')");
3639     case lltok::kw_eq:  P = CmpInst::ICMP_EQ; break;
3640     case lltok::kw_ne:  P = CmpInst::ICMP_NE; break;
3641     case lltok::kw_slt: P = CmpInst::ICMP_SLT; break;
3642     case lltok::kw_sgt: P = CmpInst::ICMP_SGT; break;
3643     case lltok::kw_sle: P = CmpInst::ICMP_SLE; break;
3644     case lltok::kw_sge: P = CmpInst::ICMP_SGE; break;
3645     case lltok::kw_ult: P = CmpInst::ICMP_ULT; break;
3646     case lltok::kw_ugt: P = CmpInst::ICMP_UGT; break;
3647     case lltok::kw_ule: P = CmpInst::ICMP_ULE; break;
3648     case lltok::kw_uge: P = CmpInst::ICMP_UGE; break;
3649     }
3650   }
3651   Lex.Lex();
3652   return false;
3653 }
3654
3655 //===----------------------------------------------------------------------===//
3656 // Terminator Instructions.
3657 //===----------------------------------------------------------------------===//
3658
3659 /// ParseRet - Parse a return instruction.
3660 ///   ::= 'ret' void (',' !dbg, !1)*
3661 ///   ::= 'ret' TypeAndValue (',' !dbg, !1)*
3662 bool LLParser::ParseRet(Instruction *&Inst, BasicBlock *BB,
3663                         PerFunctionState &PFS) {
3664   SMLoc TypeLoc = Lex.getLoc();
3665   Type *Ty = nullptr;
3666   if (ParseType(Ty, true /*void allowed*/)) return true;
3667
3668   Type *ResType = PFS.getFunction().getReturnType();
3669
3670   if (Ty->isVoidTy()) {
3671     if (!ResType->isVoidTy())
3672       return Error(TypeLoc, "value doesn't match function result type '" +
3673                    getTypeString(ResType) + "'");
3674
3675     Inst = ReturnInst::Create(Context);
3676     return false;
3677   }
3678
3679   Value *RV;
3680   if (ParseValue(Ty, RV, PFS)) return true;
3681
3682   if (ResType != RV->getType())
3683     return Error(TypeLoc, "value doesn't match function result type '" +
3684                  getTypeString(ResType) + "'");
3685
3686   Inst = ReturnInst::Create(Context, RV);
3687   return false;
3688 }
3689
3690
3691 /// ParseBr
3692 ///   ::= 'br' TypeAndValue
3693 ///   ::= 'br' TypeAndValue ',' TypeAndValue ',' TypeAndValue
3694 bool LLParser::ParseBr(Instruction *&Inst, PerFunctionState &PFS) {
3695   LocTy Loc, Loc2;
3696   Value *Op0;
3697   BasicBlock *Op1, *Op2;
3698   if (ParseTypeAndValue(Op0, Loc, PFS)) return true;
3699
3700   if (BasicBlock *BB = dyn_cast<BasicBlock>(Op0)) {
3701     Inst = BranchInst::Create(BB);
3702     return false;
3703   }
3704
3705   if (Op0->getType() != Type::getInt1Ty(Context))
3706     return Error(Loc, "branch condition must have 'i1' type");
3707
3708   if (ParseToken(lltok::comma, "expected ',' after branch condition") ||
3709       ParseTypeAndBasicBlock(Op1, Loc, PFS) ||
3710       ParseToken(lltok::comma, "expected ',' after true destination") ||
3711       ParseTypeAndBasicBlock(Op2, Loc2, PFS))
3712     return true;
3713
3714   Inst = BranchInst::Create(Op1, Op2, Op0);
3715   return false;
3716 }
3717
3718 /// ParseSwitch
3719 ///  Instruction
3720 ///    ::= 'switch' TypeAndValue ',' TypeAndValue '[' JumpTable ']'
3721 ///  JumpTable
3722 ///    ::= (TypeAndValue ',' TypeAndValue)*
3723 bool LLParser::ParseSwitch(Instruction *&Inst, PerFunctionState &PFS) {
3724   LocTy CondLoc, BBLoc;
3725   Value *Cond;
3726   BasicBlock *DefaultBB;
3727   if (ParseTypeAndValue(Cond, CondLoc, PFS) ||
3728       ParseToken(lltok::comma, "expected ',' after switch condition") ||
3729       ParseTypeAndBasicBlock(DefaultBB, BBLoc, PFS) ||
3730       ParseToken(lltok::lsquare, "expected '[' with switch table"))
3731     return true;
3732
3733   if (!Cond->getType()->isIntegerTy())
3734     return Error(CondLoc, "switch condition must have integer type");
3735
3736   // Parse the jump table pairs.
3737   SmallPtrSet<Value*, 32> SeenCases;
3738   SmallVector<std::pair<ConstantInt*, BasicBlock*>, 32> Table;
3739   while (Lex.getKind() != lltok::rsquare) {
3740     Value *Constant;
3741     BasicBlock *DestBB;
3742
3743     if (ParseTypeAndValue(Constant, CondLoc, PFS) ||
3744         ParseToken(lltok::comma, "expected ',' after case value") ||
3745         ParseTypeAndBasicBlock(DestBB, PFS))
3746       return true;
3747
3748     if (!SeenCases.insert(Constant).second)
3749       return Error(CondLoc, "duplicate case value in switch");
3750     if (!isa<ConstantInt>(Constant))
3751       return Error(CondLoc, "case value is not a constant integer");
3752
3753     Table.push_back(std::make_pair(cast<ConstantInt>(Constant), DestBB));
3754   }
3755
3756   Lex.Lex();  // Eat the ']'.
3757
3758   SwitchInst *SI = SwitchInst::Create(Cond, DefaultBB, Table.size());
3759   for (unsigned i = 0, e = Table.size(); i != e; ++i)
3760     SI->addCase(Table[i].first, Table[i].second);
3761   Inst = SI;
3762   return false;
3763 }
3764
3765 /// ParseIndirectBr
3766 ///  Instruction
3767 ///    ::= 'indirectbr' TypeAndValue ',' '[' LabelList ']'
3768 bool LLParser::ParseIndirectBr(Instruction *&Inst, PerFunctionState &PFS) {
3769   LocTy AddrLoc;
3770   Value *Address;
3771   if (ParseTypeAndValue(Address, AddrLoc, PFS) ||
3772       ParseToken(lltok::comma, "expected ',' after indirectbr address") ||
3773       ParseToken(lltok::lsquare, "expected '[' with indirectbr"))
3774     return true;
3775
3776   if (!Address->getType()->isPointerTy())
3777     return Error(AddrLoc, "indirectbr address must have pointer type");
3778
3779   // Parse the destination list.
3780   SmallVector<BasicBlock*, 16> DestList;
3781
3782   if (Lex.getKind() != lltok::rsquare) {
3783     BasicBlock *DestBB;
3784     if (ParseTypeAndBasicBlock(DestBB, PFS))
3785       return true;
3786     DestList.push_back(DestBB);
3787
3788     while (EatIfPresent(lltok::comma)) {
3789       if (ParseTypeAndBasicBlock(DestBB, PFS))
3790         return true;
3791       DestList.push_back(DestBB);
3792     }
3793   }
3794
3795   if (ParseToken(lltok::rsquare, "expected ']' at end of block list"))
3796     return true;
3797
3798   IndirectBrInst *IBI = IndirectBrInst::Create(Address, DestList.size());
3799   for (unsigned i = 0, e = DestList.size(); i != e; ++i)
3800     IBI->addDestination(DestList[i]);
3801   Inst = IBI;
3802   return false;
3803 }
3804
3805
3806 /// ParseInvoke
3807 ///   ::= 'invoke' OptionalCallingConv OptionalAttrs Type Value ParamList
3808 ///       OptionalAttrs 'to' TypeAndValue 'unwind' TypeAndValue
3809 bool LLParser::ParseInvoke(Instruction *&Inst, PerFunctionState &PFS) {
3810   LocTy CallLoc = Lex.getLoc();
3811   AttrBuilder RetAttrs, FnAttrs;
3812   std::vector<unsigned> FwdRefAttrGrps;
3813   LocTy NoBuiltinLoc;
3814   unsigned CC;
3815   Type *RetType = nullptr;
3816   LocTy RetTypeLoc;
3817   ValID CalleeID;
3818   SmallVector<ParamInfo, 16> ArgList;
3819
3820   BasicBlock *NormalBB, *UnwindBB;
3821   if (ParseOptionalCallingConv(CC) ||
3822       ParseOptionalReturnAttrs(RetAttrs) ||
3823       ParseType(RetType, RetTypeLoc, true /*void allowed*/) ||
3824       ParseValID(CalleeID) ||
3825       ParseParameterList(ArgList, PFS) ||
3826       ParseFnAttributeValuePairs(FnAttrs, FwdRefAttrGrps, false,
3827                                  NoBuiltinLoc) ||
3828       ParseToken(lltok::kw_to, "expected 'to' in invoke") ||
3829       ParseTypeAndBasicBlock(NormalBB, PFS) ||
3830       ParseToken(lltok::kw_unwind, "expected 'unwind' in invoke") ||
3831       ParseTypeAndBasicBlock(UnwindBB, PFS))
3832     return true;
3833
3834   // If RetType is a non-function pointer type, then this is the short syntax
3835   // for the call, which means that RetType is just the return type.  Infer the
3836   // rest of the function argument types from the arguments that are present.
3837   PointerType *PFTy = nullptr;
3838   FunctionType *Ty = nullptr;
3839   if (!(PFTy = dyn_cast<PointerType>(RetType)) ||
3840       !(Ty = dyn_cast<FunctionType>(PFTy->getElementType()))) {
3841     // Pull out the types of all of the arguments...
3842     std::vector<Type*> ParamTypes;
3843     for (unsigned i = 0, e = ArgList.size(); i != e; ++i)
3844       ParamTypes.push_back(ArgList[i].V->getType());
3845
3846     if (!FunctionType::isValidReturnType(RetType))
3847       return Error(RetTypeLoc, "Invalid result type for LLVM function");
3848
3849     Ty = FunctionType::get(RetType, ParamTypes, false);
3850     PFTy = PointerType::getUnqual(Ty);
3851   }
3852
3853   // Look up the callee.
3854   Value *Callee;
3855   if (ConvertValIDToValue(PFTy, CalleeID, Callee, &PFS)) return true;
3856
3857   // Set up the Attribute for the function.
3858   SmallVector<AttributeSet, 8> Attrs;
3859   if (RetAttrs.hasAttributes())
3860     Attrs.push_back(AttributeSet::get(RetType->getContext(),
3861                                       AttributeSet::ReturnIndex,
3862                                       RetAttrs));
3863
3864   SmallVector<Value*, 8> Args;
3865
3866   // Loop through FunctionType's arguments and ensure they are specified
3867   // correctly.  Also, gather any parameter attributes.
3868   FunctionType::param_iterator I = Ty->param_begin();
3869   FunctionType::param_iterator E = Ty->param_end();
3870   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
3871     Type *ExpectedTy = nullptr;
3872     if (I != E) {
3873       ExpectedTy = *I++;
3874     } else if (!Ty->isVarArg()) {
3875       return Error(ArgList[i].Loc, "too many arguments specified");
3876     }
3877
3878     if (ExpectedTy && ExpectedTy != ArgList[i].V->getType())
3879       return Error(ArgList[i].Loc, "argument is not of expected type '" +
3880                    getTypeString(ExpectedTy) + "'");
3881     Args.push_back(ArgList[i].V);
3882     if (ArgList[i].Attrs.hasAttributes(i + 1)) {
3883       AttrBuilder B(ArgList[i].Attrs, i + 1);
3884       Attrs.push_back(AttributeSet::get(RetType->getContext(), i + 1, B));
3885     }
3886   }
3887
3888   if (I != E)
3889     return Error(CallLoc, "not enough parameters specified for call");
3890
3891   if (FnAttrs.hasAttributes())
3892     Attrs.push_back(AttributeSet::get(RetType->getContext(),
3893                                       AttributeSet::FunctionIndex,
3894                                       FnAttrs));
3895
3896   // Finish off the Attribute and check them
3897   AttributeSet PAL = AttributeSet::get(Context, Attrs);
3898
3899   InvokeInst *II = InvokeInst::Create(Callee, NormalBB, UnwindBB, Args);
3900   II->setCallingConv(CC);
3901   II->setAttributes(PAL);
3902   ForwardRefAttrGroups[II] = FwdRefAttrGrps;
3903   Inst = II;
3904   return false;
3905 }
3906
3907 /// ParseResume
3908 ///   ::= 'resume' TypeAndValue
3909 bool LLParser::ParseResume(Instruction *&Inst, PerFunctionState &PFS) {
3910   Value *Exn; LocTy ExnLoc;
3911   if (ParseTypeAndValue(Exn, ExnLoc, PFS))
3912     return true;
3913
3914   ResumeInst *RI = ResumeInst::Create(Exn);
3915   Inst = RI;
3916   return false;
3917 }
3918
3919 //===----------------------------------------------------------------------===//
3920 // Binary Operators.
3921 //===----------------------------------------------------------------------===//
3922
3923 /// ParseArithmetic
3924 ///  ::= ArithmeticOps TypeAndValue ',' Value
3925 ///
3926 /// If OperandType is 0, then any FP or integer operand is allowed.  If it is 1,
3927 /// then any integer operand is allowed, if it is 2, any fp operand is allowed.
3928 bool LLParser::ParseArithmetic(Instruction *&Inst, PerFunctionState &PFS,
3929                                unsigned Opc, unsigned OperandType) {
3930   LocTy Loc; Value *LHS, *RHS;
3931   if (ParseTypeAndValue(LHS, Loc, PFS) ||
3932       ParseToken(lltok::comma, "expected ',' in arithmetic operation") ||
3933       ParseValue(LHS->getType(), RHS, PFS))
3934     return true;
3935
3936   bool Valid;
3937   switch (OperandType) {
3938   default: llvm_unreachable("Unknown operand type!");
3939   case 0: // int or FP.
3940     Valid = LHS->getType()->isIntOrIntVectorTy() ||
3941             LHS->getType()->isFPOrFPVectorTy();
3942     break;
3943   case 1: Valid = LHS->getType()->isIntOrIntVectorTy(); break;
3944   case 2: Valid = LHS->getType()->isFPOrFPVectorTy(); break;
3945   }
3946
3947   if (!Valid)
3948     return Error(Loc, "invalid operand type for instruction");
3949
3950   Inst = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
3951   return false;
3952 }
3953
3954 /// ParseLogical
3955 ///  ::= ArithmeticOps TypeAndValue ',' Value {
3956 bool LLParser::ParseLogical(Instruction *&Inst, PerFunctionState &PFS,
3957                             unsigned Opc) {
3958   LocTy Loc; Value *LHS, *RHS;
3959   if (ParseTypeAndValue(LHS, Loc, PFS) ||
3960       ParseToken(lltok::comma, "expected ',' in logical operation") ||
3961       ParseValue(LHS->getType(), RHS, PFS))
3962     return true;
3963
3964   if (!LHS->getType()->isIntOrIntVectorTy())
3965     return Error(Loc,"instruction requires integer or integer vector operands");
3966
3967   Inst = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
3968   return false;
3969 }
3970
3971
3972 /// ParseCompare
3973 ///  ::= 'icmp' IPredicates TypeAndValue ',' Value
3974 ///  ::= 'fcmp' FPredicates TypeAndValue ',' Value
3975 bool LLParser::ParseCompare(Instruction *&Inst, PerFunctionState &PFS,
3976                             unsigned Opc) {
3977   // Parse the integer/fp comparison predicate.
3978   LocTy Loc;
3979   unsigned Pred;
3980   Value *LHS, *RHS;
3981   if (ParseCmpPredicate(Pred, Opc) ||
3982       ParseTypeAndValue(LHS, Loc, PFS) ||
3983       ParseToken(lltok::comma, "expected ',' after compare value") ||
3984       ParseValue(LHS->getType(), RHS, PFS))
3985     return true;
3986
3987   if (Opc == Instruction::FCmp) {
3988     if (!LHS->getType()->isFPOrFPVectorTy())
3989       return Error(Loc, "fcmp requires floating point operands");
3990     Inst = new FCmpInst(CmpInst::Predicate(Pred), LHS, RHS);
3991   } else {
3992     assert(Opc == Instruction::ICmp && "Unknown opcode for CmpInst!");
3993     if (!LHS->getType()->isIntOrIntVectorTy() &&
3994         !LHS->getType()->getScalarType()->isPointerTy())
3995       return Error(Loc, "icmp requires integer operands");
3996     Inst = new ICmpInst(CmpInst::Predicate(Pred), LHS, RHS);
3997   }
3998   return false;
3999 }
4000
4001 //===----------------------------------------------------------------------===//
4002 // Other Instructions.
4003 //===----------------------------------------------------------------------===//
4004
4005
4006 /// ParseCast
4007 ///   ::= CastOpc TypeAndValue 'to' Type
4008 bool LLParser::ParseCast(Instruction *&Inst, PerFunctionState &PFS,
4009                          unsigned Opc) {
4010   LocTy Loc;
4011   Value *Op;
4012   Type *DestTy = nullptr;
4013   if (ParseTypeAndValue(Op, Loc, PFS) ||
4014       ParseToken(lltok::kw_to, "expected 'to' after cast value") ||
4015       ParseType(DestTy))
4016     return true;
4017
4018   if (!CastInst::castIsValid((Instruction::CastOps)Opc, Op, DestTy)) {
4019     CastInst::castIsValid((Instruction::CastOps)Opc, Op, DestTy);
4020     return Error(Loc, "invalid cast opcode for cast from '" +
4021                  getTypeString(Op->getType()) + "' to '" +
4022                  getTypeString(DestTy) + "'");
4023   }
4024   Inst = CastInst::Create((Instruction::CastOps)Opc, Op, DestTy);
4025   return false;
4026 }
4027
4028 /// ParseSelect
4029 ///   ::= 'select' TypeAndValue ',' TypeAndValue ',' TypeAndValue
4030 bool LLParser::ParseSelect(Instruction *&Inst, PerFunctionState &PFS) {
4031   LocTy Loc;
4032   Value *Op0, *Op1, *Op2;
4033   if (ParseTypeAndValue(Op0, Loc, PFS) ||
4034       ParseToken(lltok::comma, "expected ',' after select condition") ||
4035       ParseTypeAndValue(Op1, PFS) ||
4036       ParseToken(lltok::comma, "expected ',' after select value") ||
4037       ParseTypeAndValue(Op2, PFS))
4038     return true;
4039
4040   if (const char *Reason = SelectInst::areInvalidOperands(Op0, Op1, Op2))
4041     return Error(Loc, Reason);
4042
4043   Inst = SelectInst::Create(Op0, Op1, Op2);
4044   return false;
4045 }
4046
4047 /// ParseVA_Arg
4048 ///   ::= 'va_arg' TypeAndValue ',' Type
4049 bool LLParser::ParseVA_Arg(Instruction *&Inst, PerFunctionState &PFS) {
4050   Value *Op;
4051   Type *EltTy = nullptr;
4052   LocTy TypeLoc;
4053   if (ParseTypeAndValue(Op, PFS) ||
4054       ParseToken(lltok::comma, "expected ',' after vaarg operand") ||
4055       ParseType(EltTy, TypeLoc))
4056     return true;
4057
4058   if (!EltTy->isFirstClassType())
4059     return Error(TypeLoc, "va_arg requires operand with first class type");
4060
4061   Inst = new VAArgInst(Op, EltTy);
4062   return false;
4063 }
4064
4065 /// ParseExtractElement
4066 ///   ::= 'extractelement' TypeAndValue ',' TypeAndValue
4067 bool LLParser::ParseExtractElement(Instruction *&Inst, PerFunctionState &PFS) {
4068   LocTy Loc;
4069   Value *Op0, *Op1;
4070   if (ParseTypeAndValue(Op0, Loc, PFS) ||
4071       ParseToken(lltok::comma, "expected ',' after extract value") ||
4072       ParseTypeAndValue(Op1, PFS))
4073     return true;
4074
4075   if (!ExtractElementInst::isValidOperands(Op0, Op1))
4076     return Error(Loc, "invalid extractelement operands");
4077
4078   Inst = ExtractElementInst::Create(Op0, Op1);
4079   return false;
4080 }
4081
4082 /// ParseInsertElement
4083 ///   ::= 'insertelement' TypeAndValue ',' TypeAndValue ',' TypeAndValue
4084 bool LLParser::ParseInsertElement(Instruction *&Inst, PerFunctionState &PFS) {
4085   LocTy Loc;
4086   Value *Op0, *Op1, *Op2;
4087   if (ParseTypeAndValue(Op0, Loc, PFS) ||
4088       ParseToken(lltok::comma, "expected ',' after insertelement value") ||
4089       ParseTypeAndValue(Op1, PFS) ||
4090       ParseToken(lltok::comma, "expected ',' after insertelement value") ||
4091       ParseTypeAndValue(Op2, PFS))
4092     return true;
4093
4094   if (!InsertElementInst::isValidOperands(Op0, Op1, Op2))
4095     return Error(Loc, "invalid insertelement operands");
4096
4097   Inst = InsertElementInst::Create(Op0, Op1, Op2);
4098   return false;
4099 }
4100
4101 /// ParseShuffleVector
4102 ///   ::= 'shufflevector' TypeAndValue ',' TypeAndValue ',' TypeAndValue
4103 bool LLParser::ParseShuffleVector(Instruction *&Inst, PerFunctionState &PFS) {
4104   LocTy Loc;
4105   Value *Op0, *Op1, *Op2;
4106   if (ParseTypeAndValue(Op0, Loc, PFS) ||
4107       ParseToken(lltok::comma, "expected ',' after shuffle mask") ||
4108       ParseTypeAndValue(Op1, PFS) ||
4109       ParseToken(lltok::comma, "expected ',' after shuffle value") ||
4110       ParseTypeAndValue(Op2, PFS))
4111     return true;
4112
4113   if (!ShuffleVectorInst::isValidOperands(Op0, Op1, Op2))
4114     return Error(Loc, "invalid shufflevector operands");
4115
4116   Inst = new ShuffleVectorInst(Op0, Op1, Op2);
4117   return false;
4118 }
4119
4120 /// ParsePHI
4121 ///   ::= 'phi' Type '[' Value ',' Value ']' (',' '[' Value ',' Value ']')*
4122 int LLParser::ParsePHI(Instruction *&Inst, PerFunctionState &PFS) {
4123   Type *Ty = nullptr;  LocTy TypeLoc;
4124   Value *Op0, *Op1;
4125
4126   if (ParseType(Ty, TypeLoc) ||
4127       ParseToken(lltok::lsquare, "expected '[' in phi value list") ||
4128       ParseValue(Ty, Op0, PFS) ||
4129       ParseToken(lltok::comma, "expected ',' after insertelement value") ||
4130       ParseValue(Type::getLabelTy(Context), Op1, PFS) ||
4131       ParseToken(lltok::rsquare, "expected ']' in phi value list"))
4132     return true;
4133
4134   bool AteExtraComma = false;
4135   SmallVector<std::pair<Value*, BasicBlock*>, 16> PHIVals;
4136   while (1) {
4137     PHIVals.push_back(std::make_pair(Op0, cast<BasicBlock>(Op1)));
4138
4139     if (!EatIfPresent(lltok::comma))
4140       break;
4141
4142     if (Lex.getKind() == lltok::MetadataVar) {
4143       AteExtraComma = true;
4144       break;
4145     }
4146
4147     if (ParseToken(lltok::lsquare, "expected '[' in phi value list") ||
4148         ParseValue(Ty, Op0, PFS) ||
4149         ParseToken(lltok::comma, "expected ',' after insertelement value") ||
4150         ParseValue(Type::getLabelTy(Context), Op1, PFS) ||
4151         ParseToken(lltok::rsquare, "expected ']' in phi value list"))
4152       return true;
4153   }
4154
4155   if (!Ty->isFirstClassType())
4156     return Error(TypeLoc, "phi node must have first class type");
4157
4158   PHINode *PN = PHINode::Create(Ty, PHIVals.size());
4159   for (unsigned i = 0, e = PHIVals.size(); i != e; ++i)
4160     PN->addIncoming(PHIVals[i].first, PHIVals[i].second);
4161   Inst = PN;
4162   return AteExtraComma ? InstExtraComma : InstNormal;
4163 }
4164
4165 /// ParseLandingPad
4166 ///   ::= 'landingpad' Type 'personality' TypeAndValue 'cleanup'? Clause+
4167 /// Clause
4168 ///   ::= 'catch' TypeAndValue
4169 ///   ::= 'filter'
4170 ///   ::= 'filter' TypeAndValue ( ',' TypeAndValue )*
4171 bool LLParser::ParseLandingPad(Instruction *&Inst, PerFunctionState &PFS) {
4172   Type *Ty = nullptr; LocTy TyLoc;
4173   Value *PersFn; LocTy PersFnLoc;
4174
4175   if (ParseType(Ty, TyLoc) ||
4176       ParseToken(lltok::kw_personality, "expected 'personality'") ||
4177       ParseTypeAndValue(PersFn, PersFnLoc, PFS))
4178     return true;
4179
4180   LandingPadInst *LP = LandingPadInst::Create(Ty, PersFn, 0);
4181   LP->setCleanup(EatIfPresent(lltok::kw_cleanup));
4182
4183   while (Lex.getKind() == lltok::kw_catch || Lex.getKind() == lltok::kw_filter){
4184     LandingPadInst::ClauseType CT;
4185     if (EatIfPresent(lltok::kw_catch))
4186       CT = LandingPadInst::Catch;
4187     else if (EatIfPresent(lltok::kw_filter))
4188       CT = LandingPadInst::Filter;
4189     else
4190       return TokError("expected 'catch' or 'filter' clause type");
4191
4192     Value *V;
4193     LocTy VLoc;
4194     if (ParseTypeAndValue(V, VLoc, PFS)) {
4195       delete LP;
4196       return true;
4197     }
4198
4199     // A 'catch' type expects a non-array constant. A filter clause expects an
4200     // array constant.
4201     if (CT == LandingPadInst::Catch) {
4202       if (isa<ArrayType>(V->getType()))
4203         Error(VLoc, "'catch' clause has an invalid type");
4204     } else {
4205       if (!isa<ArrayType>(V->getType()))
4206         Error(VLoc, "'filter' clause has an invalid type");
4207     }
4208
4209     LP->addClause(cast<Constant>(V));
4210   }
4211
4212   Inst = LP;
4213   return false;
4214 }
4215
4216 /// ParseCall
4217 ///   ::= 'call' OptionalCallingConv OptionalAttrs Type Value
4218 ///       ParameterList OptionalAttrs
4219 ///   ::= 'tail' 'call' OptionalCallingConv OptionalAttrs Type Value
4220 ///       ParameterList OptionalAttrs
4221 ///   ::= 'musttail' 'call' OptionalCallingConv OptionalAttrs Type Value
4222 ///       ParameterList OptionalAttrs
4223 bool LLParser::ParseCall(Instruction *&Inst, PerFunctionState &PFS,
4224                          CallInst::TailCallKind TCK) {
4225   AttrBuilder RetAttrs, FnAttrs;
4226   std::vector<unsigned> FwdRefAttrGrps;
4227   LocTy BuiltinLoc;
4228   unsigned CC;
4229   Type *RetType = nullptr;
4230   LocTy RetTypeLoc;
4231   ValID CalleeID;
4232   SmallVector<ParamInfo, 16> ArgList;
4233   LocTy CallLoc = Lex.getLoc();
4234
4235   if ((TCK != CallInst::TCK_None &&
4236        ParseToken(lltok::kw_call, "expected 'tail call'")) ||
4237       ParseOptionalCallingConv(CC) ||
4238       ParseOptionalReturnAttrs(RetAttrs) ||
4239       ParseType(RetType, RetTypeLoc, true /*void allowed*/) ||
4240       ParseValID(CalleeID) ||
4241       ParseParameterList(ArgList, PFS, TCK == CallInst::TCK_MustTail,
4242                          PFS.getFunction().isVarArg()) ||
4243       ParseFnAttributeValuePairs(FnAttrs, FwdRefAttrGrps, false,
4244                                  BuiltinLoc))
4245     return true;
4246
4247   // If RetType is a non-function pointer type, then this is the short syntax
4248   // for the call, which means that RetType is just the return type.  Infer the
4249   // rest of the function argument types from the arguments that are present.
4250   PointerType *PFTy = nullptr;
4251   FunctionType *Ty = nullptr;
4252   if (!(PFTy = dyn_cast<PointerType>(RetType)) ||
4253       !(Ty = dyn_cast<FunctionType>(PFTy->getElementType()))) {
4254     // Pull out the types of all of the arguments...
4255     std::vector<Type*> ParamTypes;
4256     for (unsigned i = 0, e = ArgList.size(); i != e; ++i)
4257       ParamTypes.push_back(ArgList[i].V->getType());
4258
4259     if (!FunctionType::isValidReturnType(RetType))
4260       return Error(RetTypeLoc, "Invalid result type for LLVM function");
4261
4262     Ty = FunctionType::get(RetType, ParamTypes, false);
4263     PFTy = PointerType::getUnqual(Ty);
4264   }
4265
4266   // Look up the callee.
4267   Value *Callee;
4268   if (ConvertValIDToValue(PFTy, CalleeID, Callee, &PFS)) return true;
4269
4270   // Set up the Attribute for the function.
4271   SmallVector<AttributeSet, 8> Attrs;
4272   if (RetAttrs.hasAttributes())
4273     Attrs.push_back(AttributeSet::get(RetType->getContext(),
4274                                       AttributeSet::ReturnIndex,
4275                                       RetAttrs));
4276
4277   SmallVector<Value*, 8> Args;
4278
4279   // Loop through FunctionType's arguments and ensure they are specified
4280   // correctly.  Also, gather any parameter attributes.
4281   FunctionType::param_iterator I = Ty->param_begin();
4282   FunctionType::param_iterator E = Ty->param_end();
4283   for (unsigned i = 0, e = ArgList.size(); i != e; ++i) {
4284     Type *ExpectedTy = nullptr;
4285     if (I != E) {
4286       ExpectedTy = *I++;
4287     } else if (!Ty->isVarArg()) {
4288       return Error(ArgList[i].Loc, "too many arguments specified");
4289     }
4290
4291     if (ExpectedTy && ExpectedTy != ArgList[i].V->getType())
4292       return Error(ArgList[i].Loc, "argument is not of expected type '" +
4293                    getTypeString(ExpectedTy) + "'");
4294     Args.push_back(ArgList[i].V);
4295     if (ArgList[i].Attrs.hasAttributes(i + 1)) {
4296       AttrBuilder B(ArgList[i].Attrs, i + 1);
4297       Attrs.push_back(AttributeSet::get(RetType->getContext(), i + 1, B));
4298     }
4299   }
4300
4301   if (I != E)
4302     return Error(CallLoc, "not enough parameters specified for call");
4303
4304   if (FnAttrs.hasAttributes())
4305     Attrs.push_back(AttributeSet::get(RetType->getContext(),
4306                                       AttributeSet::FunctionIndex,
4307                                       FnAttrs));
4308
4309   // Finish off the Attribute and check them
4310   AttributeSet PAL = AttributeSet::get(Context, Attrs);
4311
4312   CallInst *CI = CallInst::Create(Callee, Args);
4313   CI->setTailCallKind(TCK);
4314   CI->setCallingConv(CC);
4315   CI->setAttributes(PAL);
4316   ForwardRefAttrGroups[CI] = FwdRefAttrGrps;
4317   Inst = CI;
4318   return false;
4319 }
4320
4321 //===----------------------------------------------------------------------===//
4322 // Memory Instructions.
4323 //===----------------------------------------------------------------------===//
4324
4325 /// ParseAlloc
4326 ///   ::= 'alloca' 'inalloca'? Type (',' TypeAndValue)? (',' 'align' i32)?
4327 int LLParser::ParseAlloc(Instruction *&Inst, PerFunctionState &PFS) {
4328   Value *Size = nullptr;
4329   LocTy SizeLoc;
4330   unsigned Alignment = 0;
4331   Type *Ty = nullptr;
4332
4333   bool IsInAlloca = EatIfPresent(lltok::kw_inalloca);
4334
4335   if (ParseType(Ty)) return true;
4336
4337   bool AteExtraComma = false;
4338   if (EatIfPresent(lltok::comma)) {
4339     if (Lex.getKind() == lltok::kw_align) {
4340       if (ParseOptionalAlignment(Alignment)) return true;
4341     } else if (Lex.getKind() == lltok::MetadataVar) {
4342       AteExtraComma = true;
4343     } else {
4344       if (ParseTypeAndValue(Size, SizeLoc, PFS) ||
4345           ParseOptionalCommaAlign(Alignment, AteExtraComma))
4346         return true;
4347     }
4348   }
4349
4350   if (Size && !Size->getType()->isIntegerTy())
4351     return Error(SizeLoc, "element count must have integer type");
4352
4353   AllocaInst *AI = new AllocaInst(Ty, Size, Alignment);
4354   AI->setUsedWithInAlloca(IsInAlloca);
4355   Inst = AI;
4356   return AteExtraComma ? InstExtraComma : InstNormal;
4357 }
4358
4359 /// ParseLoad
4360 ///   ::= 'load' 'volatile'? TypeAndValue (',' 'align' i32)?
4361 ///   ::= 'load' 'atomic' 'volatile'? TypeAndValue
4362 ///       'singlethread'? AtomicOrdering (',' 'align' i32)?
4363 int LLParser::ParseLoad(Instruction *&Inst, PerFunctionState &PFS) {
4364   Value *Val; LocTy Loc;
4365   unsigned Alignment = 0;
4366   bool AteExtraComma = false;
4367   bool isAtomic = false;
4368   AtomicOrdering Ordering = NotAtomic;
4369   SynchronizationScope Scope = CrossThread;
4370
4371   if (Lex.getKind() == lltok::kw_atomic) {
4372     isAtomic = true;
4373     Lex.Lex();
4374   }
4375
4376   bool isVolatile = false;
4377   if (Lex.getKind() == lltok::kw_volatile) {
4378     isVolatile = true;
4379     Lex.Lex();
4380   }
4381
4382   if (ParseTypeAndValue(Val, Loc, PFS) ||
4383       ParseScopeAndOrdering(isAtomic, Scope, Ordering) ||
4384       ParseOptionalCommaAlign(Alignment, AteExtraComma))
4385     return true;
4386
4387   if (!Val->getType()->isPointerTy() ||
4388       !cast<PointerType>(Val->getType())->getElementType()->isFirstClassType())
4389     return Error(Loc, "load operand must be a pointer to a first class type");
4390   if (isAtomic && !Alignment)
4391     return Error(Loc, "atomic load must have explicit non-zero alignment");
4392   if (Ordering == Release || Ordering == AcquireRelease)
4393     return Error(Loc, "atomic load cannot use Release ordering");
4394
4395   Inst = new LoadInst(Val, "", isVolatile, Alignment, Ordering, Scope);
4396   return AteExtraComma ? InstExtraComma : InstNormal;
4397 }
4398
4399 /// ParseStore
4400
4401 ///   ::= 'store' 'volatile'? TypeAndValue ',' TypeAndValue (',' 'align' i32)?
4402 ///   ::= 'store' 'atomic' 'volatile'? TypeAndValue ',' TypeAndValue
4403 ///       'singlethread'? AtomicOrdering (',' 'align' i32)?
4404 int LLParser::ParseStore(Instruction *&Inst, PerFunctionState &PFS) {
4405   Value *Val, *Ptr; LocTy Loc, PtrLoc;
4406   unsigned Alignment = 0;
4407   bool AteExtraComma = false;
4408   bool isAtomic = false;
4409   AtomicOrdering Ordering = NotAtomic;
4410   SynchronizationScope Scope = CrossThread;
4411
4412   if (Lex.getKind() == lltok::kw_atomic) {
4413     isAtomic = true;
4414     Lex.Lex();
4415   }
4416
4417   bool isVolatile = false;
4418   if (Lex.getKind() == lltok::kw_volatile) {
4419     isVolatile = true;
4420     Lex.Lex();
4421   }
4422
4423   if (ParseTypeAndValue(Val, Loc, PFS) ||
4424       ParseToken(lltok::comma, "expected ',' after store operand") ||
4425       ParseTypeAndValue(Ptr, PtrLoc, PFS) ||
4426       ParseScopeAndOrdering(isAtomic, Scope, Ordering) ||
4427       ParseOptionalCommaAlign(Alignment, AteExtraComma))
4428     return true;
4429
4430   if (!Ptr->getType()->isPointerTy())
4431     return Error(PtrLoc, "store operand must be a pointer");
4432   if (!Val->getType()->isFirstClassType())
4433     return Error(Loc, "store operand must be a first class value");
4434   if (cast<PointerType>(Ptr->getType())->getElementType() != Val->getType())
4435     return Error(Loc, "stored value and pointer type do not match");
4436   if (isAtomic && !Alignment)
4437     return Error(Loc, "atomic store must have explicit non-zero alignment");
4438   if (Ordering == Acquire || Ordering == AcquireRelease)
4439     return Error(Loc, "atomic store cannot use Acquire ordering");
4440
4441   Inst = new StoreInst(Val, Ptr, isVolatile, Alignment, Ordering, Scope);
4442   return AteExtraComma ? InstExtraComma : InstNormal;
4443 }
4444
4445 /// ParseCmpXchg
4446 ///   ::= 'cmpxchg' 'weak'? 'volatile'? TypeAndValue ',' TypeAndValue ','
4447 ///       TypeAndValue 'singlethread'? AtomicOrdering AtomicOrdering
4448 int LLParser::ParseCmpXchg(Instruction *&Inst, PerFunctionState &PFS) {
4449   Value *Ptr, *Cmp, *New; LocTy PtrLoc, CmpLoc, NewLoc;
4450   bool AteExtraComma = false;
4451   AtomicOrdering SuccessOrdering = NotAtomic;
4452   AtomicOrdering FailureOrdering = NotAtomic;
4453   SynchronizationScope Scope = CrossThread;
4454   bool isVolatile = false;
4455   bool isWeak = false;
4456
4457   if (EatIfPresent(lltok::kw_weak))
4458     isWeak = true;
4459
4460   if (EatIfPresent(lltok::kw_volatile))
4461     isVolatile = true;
4462
4463   if (ParseTypeAndValue(Ptr, PtrLoc, PFS) ||
4464       ParseToken(lltok::comma, "expected ',' after cmpxchg address") ||
4465       ParseTypeAndValue(Cmp, CmpLoc, PFS) ||
4466       ParseToken(lltok::comma, "expected ',' after cmpxchg cmp operand") ||
4467       ParseTypeAndValue(New, NewLoc, PFS) ||
4468       ParseScopeAndOrdering(true /*Always atomic*/, Scope, SuccessOrdering) ||
4469       ParseOrdering(FailureOrdering))
4470     return true;
4471
4472   if (SuccessOrdering == Unordered || FailureOrdering == Unordered)
4473     return TokError("cmpxchg cannot be unordered");
4474   if (SuccessOrdering < FailureOrdering)
4475     return TokError("cmpxchg must be at least as ordered on success as failure");
4476   if (FailureOrdering == Release || FailureOrdering == AcquireRelease)
4477     return TokError("cmpxchg failure ordering cannot include release semantics");
4478   if (!Ptr->getType()->isPointerTy())
4479     return Error(PtrLoc, "cmpxchg operand must be a pointer");
4480   if (cast<PointerType>(Ptr->getType())->getElementType() != Cmp->getType())
4481     return Error(CmpLoc, "compare value and pointer type do not match");
4482   if (cast<PointerType>(Ptr->getType())->getElementType() != New->getType())
4483     return Error(NewLoc, "new value and pointer type do not match");
4484   if (!New->getType()->isIntegerTy())
4485     return Error(NewLoc, "cmpxchg operand must be an integer");
4486   unsigned Size = New->getType()->getPrimitiveSizeInBits();
4487   if (Size < 8 || (Size & (Size - 1)))
4488     return Error(NewLoc, "cmpxchg operand must be power-of-two byte-sized"
4489                          " integer");
4490
4491   AtomicCmpXchgInst *CXI = new AtomicCmpXchgInst(
4492       Ptr, Cmp, New, SuccessOrdering, FailureOrdering, Scope);
4493   CXI->setVolatile(isVolatile);
4494   CXI->setWeak(isWeak);
4495   Inst = CXI;
4496   return AteExtraComma ? InstExtraComma : InstNormal;
4497 }
4498
4499 /// ParseAtomicRMW
4500 ///   ::= 'atomicrmw' 'volatile'? BinOp TypeAndValue ',' TypeAndValue
4501 ///       'singlethread'? AtomicOrdering
4502 int LLParser::ParseAtomicRMW(Instruction *&Inst, PerFunctionState &PFS) {
4503   Value *Ptr, *Val; LocTy PtrLoc, ValLoc;
4504   bool AteExtraComma = false;
4505   AtomicOrdering Ordering = NotAtomic;
4506   SynchronizationScope Scope = CrossThread;
4507   bool isVolatile = false;
4508   AtomicRMWInst::BinOp Operation;
4509
4510   if (EatIfPresent(lltok::kw_volatile))
4511     isVolatile = true;
4512
4513   switch (Lex.getKind()) {
4514   default: return TokError("expected binary operation in atomicrmw");
4515   case lltok::kw_xchg: Operation = AtomicRMWInst::Xchg; break;
4516   case lltok::kw_add: Operation = AtomicRMWInst::Add; break;
4517   case lltok::kw_sub: Operation = AtomicRMWInst::Sub; break;
4518   case lltok::kw_and: Operation = AtomicRMWInst::And; break;
4519   case lltok::kw_nand: Operation = AtomicRMWInst::Nand; break;
4520   case lltok::kw_or: Operation = AtomicRMWInst::Or; break;
4521   case lltok::kw_xor: Operation = AtomicRMWInst::Xor; break;
4522   case lltok::kw_max: Operation = AtomicRMWInst::Max; break;
4523   case lltok::kw_min: Operation = AtomicRMWInst::Min; break;
4524   case lltok::kw_umax: Operation = AtomicRMWInst::UMax; break;
4525   case lltok::kw_umin: Operation = AtomicRMWInst::UMin; break;
4526   }
4527   Lex.Lex();  // Eat the operation.
4528
4529   if (ParseTypeAndValue(Ptr, PtrLoc, PFS) ||
4530       ParseToken(lltok::comma, "expected ',' after atomicrmw address") ||
4531       ParseTypeAndValue(Val, ValLoc, PFS) ||
4532       ParseScopeAndOrdering(true /*Always atomic*/, Scope, Ordering))
4533     return true;
4534
4535   if (Ordering == Unordered)
4536     return TokError("atomicrmw cannot be unordered");
4537   if (!Ptr->getType()->isPointerTy())
4538     return Error(PtrLoc, "atomicrmw operand must be a pointer");
4539   if (cast<PointerType>(Ptr->getType())->getElementType() != Val->getType())
4540     return Error(ValLoc, "atomicrmw value and pointer type do not match");
4541   if (!Val->getType()->isIntegerTy())
4542     return Error(ValLoc, "atomicrmw operand must be an integer");
4543   unsigned Size = Val->getType()->getPrimitiveSizeInBits();
4544   if (Size < 8 || (Size & (Size - 1)))
4545     return Error(ValLoc, "atomicrmw operand must be power-of-two byte-sized"
4546                          " integer");
4547
4548   AtomicRMWInst *RMWI =
4549     new AtomicRMWInst(Operation, Ptr, Val, Ordering, Scope);
4550   RMWI->setVolatile(isVolatile);
4551   Inst = RMWI;
4552   return AteExtraComma ? InstExtraComma : InstNormal;
4553 }
4554
4555 /// ParseFence
4556 ///   ::= 'fence' 'singlethread'? AtomicOrdering
4557 int LLParser::ParseFence(Instruction *&Inst, PerFunctionState &PFS) {
4558   AtomicOrdering Ordering = NotAtomic;
4559   SynchronizationScope Scope = CrossThread;
4560   if (ParseScopeAndOrdering(true /*Always atomic*/, Scope, Ordering))
4561     return true;
4562
4563   if (Ordering == Unordered)
4564     return TokError("fence cannot be unordered");
4565   if (Ordering == Monotonic)
4566     return TokError("fence cannot be monotonic");
4567
4568   Inst = new FenceInst(Context, Ordering, Scope);
4569   return InstNormal;
4570 }
4571
4572 /// ParseGetElementPtr
4573 ///   ::= 'getelementptr' 'inbounds'? TypeAndValue (',' TypeAndValue)*
4574 int LLParser::ParseGetElementPtr(Instruction *&Inst, PerFunctionState &PFS) {
4575   Value *Ptr = nullptr;
4576   Value *Val = nullptr;
4577   LocTy Loc, EltLoc;
4578
4579   bool InBounds = EatIfPresent(lltok::kw_inbounds);
4580
4581   if (ParseTypeAndValue(Ptr, Loc, PFS)) return true;
4582
4583   Type *BaseType = Ptr->getType();
4584   PointerType *BasePointerType = dyn_cast<PointerType>(BaseType->getScalarType());
4585   if (!BasePointerType)
4586     return Error(Loc, "base of getelementptr must be a pointer");
4587
4588   SmallVector<Value*, 16> Indices;
4589   bool AteExtraComma = false;
4590   while (EatIfPresent(lltok::comma)) {
4591     if (Lex.getKind() == lltok::MetadataVar) {
4592       AteExtraComma = true;
4593       break;
4594     }
4595     if (ParseTypeAndValue(Val, EltLoc, PFS)) return true;
4596     if (!Val->getType()->getScalarType()->isIntegerTy())
4597       return Error(EltLoc, "getelementptr index must be an integer");
4598     if (Val->getType()->isVectorTy() != Ptr->getType()->isVectorTy())
4599       return Error(EltLoc, "getelementptr index type missmatch");
4600     if (Val->getType()->isVectorTy()) {
4601       unsigned ValNumEl = cast<VectorType>(Val->getType())->getNumElements();
4602       unsigned PtrNumEl = cast<VectorType>(Ptr->getType())->getNumElements();
4603       if (ValNumEl != PtrNumEl)
4604         return Error(EltLoc,
4605           "getelementptr vector index has a wrong number of elements");
4606     }
4607     Indices.push_back(Val);
4608   }
4609
4610   if (!Indices.empty() && !BasePointerType->getElementType()->isSized())
4611     return Error(Loc, "base element of getelementptr must be sized");
4612
4613   if (!GetElementPtrInst::getIndexedType(BaseType, Indices))
4614     return Error(Loc, "invalid getelementptr indices");
4615   Inst = GetElementPtrInst::Create(Ptr, Indices);
4616   if (InBounds)
4617     cast<GetElementPtrInst>(Inst)->setIsInBounds(true);
4618   return AteExtraComma ? InstExtraComma : InstNormal;
4619 }
4620
4621 /// ParseExtractValue
4622 ///   ::= 'extractvalue' TypeAndValue (',' uint32)+
4623 int LLParser::ParseExtractValue(Instruction *&Inst, PerFunctionState &PFS) {
4624   Value *Val; LocTy Loc;
4625   SmallVector<unsigned, 4> Indices;
4626   bool AteExtraComma;
4627   if (ParseTypeAndValue(Val, Loc, PFS) ||
4628       ParseIndexList(Indices, AteExtraComma))
4629     return true;
4630
4631   if (!Val->getType()->isAggregateType())
4632     return Error(Loc, "extractvalue operand must be aggregate type");
4633
4634   if (!ExtractValueInst::getIndexedType(Val->getType(), Indices))
4635     return Error(Loc, "invalid indices for extractvalue");
4636   Inst = ExtractValueInst::Create(Val, Indices);
4637   return AteExtraComma ? InstExtraComma : InstNormal;
4638 }
4639
4640 /// ParseInsertValue
4641 ///   ::= 'insertvalue' TypeAndValue ',' TypeAndValue (',' uint32)+
4642 int LLParser::ParseInsertValue(Instruction *&Inst, PerFunctionState &PFS) {
4643   Value *Val0, *Val1; LocTy Loc0, Loc1;
4644   SmallVector<unsigned, 4> Indices;
4645   bool AteExtraComma;
4646   if (ParseTypeAndValue(Val0, Loc0, PFS) ||
4647       ParseToken(lltok::comma, "expected comma after insertvalue operand") ||
4648       ParseTypeAndValue(Val1, Loc1, PFS) ||
4649       ParseIndexList(Indices, AteExtraComma))
4650     return true;
4651
4652   if (!Val0->getType()->isAggregateType())
4653     return Error(Loc0, "insertvalue operand must be aggregate type");
4654
4655   if (!ExtractValueInst::getIndexedType(Val0->getType(), Indices))
4656     return Error(Loc0, "invalid indices for insertvalue");
4657   Inst = InsertValueInst::Create(Val0, Val1, Indices);
4658   return AteExtraComma ? InstExtraComma : InstNormal;
4659 }
4660
4661 //===----------------------------------------------------------------------===//
4662 // Embedded metadata.
4663 //===----------------------------------------------------------------------===//
4664
4665 /// ParseMDNodeVector
4666 ///   ::= Element (',' Element)*
4667 /// Element
4668 ///   ::= 'null' | TypeAndValue
4669 bool LLParser::ParseMDNodeVector(SmallVectorImpl<Value*> &Elts,
4670                                  PerFunctionState *PFS) {
4671   // Check for an empty list.
4672   if (Lex.getKind() == lltok::rbrace)
4673     return false;
4674
4675   bool IsLocal = false;
4676   do {
4677     if (IsLocal)
4678       return TokError("unexpected operand after function-local metadata");
4679
4680     // Null is a special case since it is typeless.
4681     if (EatIfPresent(lltok::kw_null)) {
4682       Elts.push_back(nullptr);
4683       continue;
4684     }
4685
4686     Value *V = nullptr;
4687     if (ParseTypeAndValue(V, PFS)) return true;
4688     Elts.push_back(V);
4689
4690     if (isa<MDNode>(V) && cast<MDNode>(V)->isFunctionLocal())
4691       return TokError("unexpected nested function-local metadata");
4692     if (!V->getType()->isMetadataTy() && !isa<Constant>(V)) {
4693       assert(PFS && "Unexpected function-local metadata without PFS");
4694       if (Elts.size() > 1)
4695         return TokError("unexpected function-local metadata");
4696       IsLocal = true;
4697     }
4698   } while (EatIfPresent(lltok::comma));
4699
4700   return false;
4701 }
4702
4703 //===----------------------------------------------------------------------===//
4704 // Use-list order directives.
4705 //===----------------------------------------------------------------------===//
4706 bool LLParser::sortUseListOrder(Value *V, ArrayRef<unsigned> Indexes,
4707                                 SMLoc Loc) {
4708   if (V->use_empty())
4709     return Error(Loc, "value has no uses");
4710
4711   unsigned NumUses = 0;
4712   SmallDenseMap<const Use *, unsigned, 16> Order;
4713   for (const Use &U : V->uses()) {
4714     if (++NumUses > Indexes.size())
4715       break;
4716     Order[&U] = Indexes[NumUses - 1];
4717   }
4718   if (NumUses < 2)
4719     return Error(Loc, "value only has one use");
4720   if (Order.size() != Indexes.size() || NumUses > Indexes.size())
4721     return Error(Loc, "wrong number of indexes, expected " +
4722                           Twine(std::distance(V->use_begin(), V->use_end())));
4723
4724   V->sortUseList([&](const Use &L, const Use &R) {
4725     return Order.lookup(&L) < Order.lookup(&R);
4726   });
4727   return false;
4728 }
4729
4730 /// ParseUseListOrderIndexes
4731 ///   ::= '{' uint32 (',' uint32)+ '}'
4732 bool LLParser::ParseUseListOrderIndexes(SmallVectorImpl<unsigned> &Indexes) {
4733   SMLoc Loc = Lex.getLoc();
4734   if (ParseToken(lltok::lbrace, "expected '{' here"))
4735     return true;
4736   if (Lex.getKind() == lltok::rbrace)
4737     return Lex.Error("expected non-empty list of uselistorder indexes");
4738
4739   // Use Offset, Max, and IsOrdered to check consistency of indexes.  The
4740   // indexes should be distinct numbers in the range [0, size-1], and should
4741   // not be in order.
4742   unsigned Offset = 0;
4743   unsigned Max = 0;
4744   bool IsOrdered = true;
4745   assert(Indexes.empty() && "Expected empty order vector");
4746   do {
4747     unsigned Index;
4748     if (ParseUInt32(Index))
4749       return true;
4750
4751     // Update consistency checks.
4752     Offset += Index - Indexes.size();
4753     Max = std::max(Max, Index);
4754     IsOrdered &= Index == Indexes.size();
4755
4756     Indexes.push_back(Index);
4757   } while (EatIfPresent(lltok::comma));
4758
4759   if (ParseToken(lltok::rbrace, "expected '}' here"))
4760     return true;
4761
4762   if (Indexes.size() < 2)
4763     return Error(Loc, "expected >= 2 uselistorder indexes");
4764   if (Offset != 0 || Max >= Indexes.size())
4765     return Error(Loc, "expected distinct uselistorder indexes in range [0, size)");
4766   if (IsOrdered)
4767     return Error(Loc, "expected uselistorder indexes to change the order");
4768
4769   return false;
4770 }
4771
4772 /// ParseUseListOrder
4773 ///   ::= 'uselistorder' Type Value ',' UseListOrderIndexes
4774 bool LLParser::ParseUseListOrder(PerFunctionState *PFS) {
4775   SMLoc Loc = Lex.getLoc();
4776   if (ParseToken(lltok::kw_uselistorder, "expected uselistorder directive"))
4777     return true;
4778
4779   Value *V;
4780   SmallVector<unsigned, 16> Indexes;
4781   if (ParseTypeAndValue(V, PFS) ||
4782       ParseToken(lltok::comma, "expected comma in uselistorder directive") ||
4783       ParseUseListOrderIndexes(Indexes))
4784     return true;
4785
4786   return sortUseListOrder(V, Indexes, Loc);
4787 }
4788
4789 /// ParseUseListOrderBB
4790 ///   ::= 'uselistorder_bb' @foo ',' %bar ',' UseListOrderIndexes
4791 bool LLParser::ParseUseListOrderBB() {
4792   assert(Lex.getKind() == lltok::kw_uselistorder_bb);
4793   SMLoc Loc = Lex.getLoc();
4794   Lex.Lex();
4795
4796   ValID Fn, Label;
4797   SmallVector<unsigned, 16> Indexes;
4798   if (ParseValID(Fn) ||
4799       ParseToken(lltok::comma, "expected comma in uselistorder_bb directive") ||
4800       ParseValID(Label) ||
4801       ParseToken(lltok::comma, "expected comma in uselistorder_bb directive") ||
4802       ParseUseListOrderIndexes(Indexes))
4803     return true;
4804
4805   // Check the function.
4806   GlobalValue *GV;
4807   if (Fn.Kind == ValID::t_GlobalName)
4808     GV = M->getNamedValue(Fn.StrVal);
4809   else if (Fn.Kind == ValID::t_GlobalID)
4810     GV = Fn.UIntVal < NumberedVals.size() ? NumberedVals[Fn.UIntVal] : nullptr;
4811   else
4812     return Error(Fn.Loc, "expected function name in uselistorder_bb");
4813   if (!GV)
4814     return Error(Fn.Loc, "invalid function forward reference in uselistorder_bb");
4815   auto *F = dyn_cast<Function>(GV);
4816   if (!F)
4817     return Error(Fn.Loc, "expected function name in uselistorder_bb");
4818   if (F->isDeclaration())
4819     return Error(Fn.Loc, "invalid declaration in uselistorder_bb");
4820
4821   // Check the basic block.
4822   if (Label.Kind == ValID::t_LocalID)
4823     return Error(Label.Loc, "invalid numeric label in uselistorder_bb");
4824   if (Label.Kind != ValID::t_LocalName)
4825     return Error(Label.Loc, "expected basic block name in uselistorder_bb");
4826   Value *V = F->getValueSymbolTable().lookup(Label.StrVal);
4827   if (!V)
4828     return Error(Label.Loc, "invalid basic block in uselistorder_bb");
4829   if (!isa<BasicBlock>(V))
4830     return Error(Label.Loc, "expected basic block in uselistorder_bb");
4831
4832   return sortUseListOrder(V, Indexes, Loc);
4833 }