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