1//===-- LLParser.h - Parser Class -------------------------------*- C++ -*-===//
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#ifndef LLVM_ASMPARSER_LLPARSER_H
15#define LLVM_ASMPARSER_LLPARSER_H
16
17#include "LLLexer.h"
18#include "llvm/Attributes.h"
19#include "llvm/Instructions.h"
20#include "llvm/Module.h"
21#include "llvm/Type.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/StringMap.h"
24#include "llvm/Support/ValueHandle.h"
25#include <map>
26
27namespace llvm {
28  class Module;
29  class OpaqueType;
30  class Function;
31  class Value;
32  class BasicBlock;
33  class Instruction;
34  class Constant;
35  class GlobalValue;
36  class MDString;
37  class MDNode;
38  class StructType;
39
40  /// ValID - Represents a reference of a definition of some sort with no type.
41  /// There are several cases where we have to parse the value but where the
42  /// type can depend on later context.  This may either be a numeric reference
43  /// or a symbolic (%var) reference.  This is just a discriminated union.
44  struct ValID {
45    enum {
46      t_LocalID, t_GlobalID,      // ID in UIntVal.
47      t_LocalName, t_GlobalName,  // Name in StrVal.
48      t_APSInt, t_APFloat,        // Value in APSIntVal/APFloatVal.
49      t_Null, t_Undef, t_Zero,    // No value.
50      t_EmptyArray,               // No value:  []
51      t_Constant,                 // Value in ConstantVal.
52      t_InlineAsm,                // Value in StrVal/StrVal2/UIntVal.
53      t_MDNode,                   // Value in MDNodeVal.
54      t_MDString,                 // Value in MDStringVal.
55      t_ConstantStruct,           // Value in ConstantStructElts.
56      t_PackedConstantStruct      // Value in ConstantStructElts.
57    } Kind;
58
59    LLLexer::LocTy Loc;
60    unsigned UIntVal;
61    std::string StrVal, StrVal2;
62    APSInt APSIntVal;
63    APFloat APFloatVal;
64    Constant *ConstantVal;
65    MDNode *MDNodeVal;
66    MDString *MDStringVal;
67    Constant **ConstantStructElts;
68
69    ValID() : Kind(t_LocalID), APFloatVal(0.0) {}
70    ~ValID() {
71      if (Kind == t_ConstantStruct || Kind == t_PackedConstantStruct)
72        delete [] ConstantStructElts;
73    }
74
75    bool operator<(const ValID &RHS) const {
76      if (Kind == t_LocalID || Kind == t_GlobalID)
77        return UIntVal < RHS.UIntVal;
78      assert((Kind == t_LocalName || Kind == t_GlobalName ||
79              Kind == t_ConstantStruct || Kind == t_PackedConstantStruct) &&
80             "Ordering not defined for this ValID kind yet");
81      return StrVal < RHS.StrVal;
82    }
83  };
84
85  class LLParser {
86  public:
87    typedef LLLexer::LocTy LocTy;
88  private:
89    LLVMContext &Context;
90    LLLexer Lex;
91    Module *M;
92
93    // Instruction metadata resolution.  Each instruction can have a list of
94    // MDRef info associated with them.
95    //
96    // The simpler approach of just creating temporary MDNodes and then calling
97    // RAUW on them when the definition is processed doesn't work because some
98    // instruction metadata kinds, such as dbg, get stored in the IR in an
99    // "optimized" format which doesn't participate in the normal value use
100    // lists. This means that RAUW doesn't work, even on temporary MDNodes
101    // which otherwise support RAUW. Instead, we defer resolving MDNode
102    // references until the definitions have been processed.
103    struct MDRef {
104      SMLoc Loc;
105      unsigned MDKind, MDSlot;
106    };
107    DenseMap<Instruction*, std::vector<MDRef> > ForwardRefInstMetadata;
108
109    // Type resolution handling data structures.  The location is set when we
110    // have processed a use of the type but not a definition yet.
111    StringMap<std::pair<Type*, LocTy> > NamedTypes;
112    std::vector<std::pair<Type*, LocTy> > NumberedTypes;
113
114    std::vector<TrackingVH<MDNode> > NumberedMetadata;
115    std::map<unsigned, std::pair<TrackingVH<MDNode>, LocTy> > ForwardRefMDNodes;
116
117    // Global Value reference information.
118    std::map<std::string, std::pair<GlobalValue*, LocTy> > ForwardRefVals;
119    std::map<unsigned, std::pair<GlobalValue*, LocTy> > ForwardRefValIDs;
120    std::vector<GlobalValue*> NumberedVals;
121
122    // References to blockaddress.  The key is the function ValID, the value is
123    // a list of references to blocks in that function.
124    std::map<ValID, std::vector<std::pair<ValID, GlobalValue*> > >
125      ForwardRefBlockAddresses;
126
127  public:
128    LLParser(MemoryBuffer *F, SourceMgr &SM, SMDiagnostic &Err, Module *m) :
129      Context(m->getContext()), Lex(F, SM, Err, m->getContext()),
130      M(m) {}
131    bool Run();
132
133    LLVMContext &getContext() { return Context; }
134
135  private:
136
137    bool Error(LocTy L, const Twine &Msg) const {
138      return Lex.Error(L, Msg);
139    }
140    bool TokError(const Twine &Msg) const {
141      return Error(Lex.getLoc(), Msg);
142    }
143
144    /// GetGlobalVal - Get a value with the specified name or ID, creating a
145    /// forward reference record if needed.  This can return null if the value
146    /// exists but does not have the right type.
147    GlobalValue *GetGlobalVal(const std::string &N, Type *Ty, LocTy Loc);
148    GlobalValue *GetGlobalVal(unsigned ID, Type *Ty, LocTy Loc);
149
150    // Helper Routines.
151    bool ParseToken(lltok::Kind T, const char *ErrMsg);
152    bool EatIfPresent(lltok::Kind T) {
153      if (Lex.getKind() != T) return false;
154      Lex.Lex();
155      return true;
156    }
157    bool ParseOptionalToken(lltok::Kind T, bool &Present, LocTy *Loc = 0) {
158      if (Lex.getKind() != T) {
159        Present = false;
160      } else {
161        if (Loc)
162          *Loc = Lex.getLoc();
163        Lex.Lex();
164        Present = true;
165      }
166      return false;
167    }
168    bool ParseStringConstant(std::string &Result);
169    bool ParseUInt32(unsigned &Val);
170    bool ParseUInt32(unsigned &Val, LocTy &Loc) {
171      Loc = Lex.getLoc();
172      return ParseUInt32(Val);
173    }
174
175    bool ParseTLSModel(GlobalVariable::ThreadLocalMode &TLM);
176    bool ParseOptionalThreadLocal(GlobalVariable::ThreadLocalMode &TLM);
177    bool ParseOptionalAddrSpace(unsigned &AddrSpace);
178    bool ParseOptionalAttrs(Attributes &Attrs, unsigned AttrKind);
179    bool ParseOptionalLinkage(unsigned &Linkage, bool &HasLinkage);
180    bool ParseOptionalLinkage(unsigned &Linkage) {
181      bool HasLinkage; return ParseOptionalLinkage(Linkage, HasLinkage);
182    }
183    bool ParseOptionalVisibility(unsigned &Visibility);
184    bool ParseOptionalCallingConv(CallingConv::ID &CC);
185    bool ParseOptionalAlignment(unsigned &Alignment);
186    bool ParseScopeAndOrdering(bool isAtomic, SynchronizationScope &Scope,
187                               AtomicOrdering &Ordering);
188    bool ParseOptionalStackAlignment(unsigned &Alignment);
189    bool ParseOptionalCommaAlign(unsigned &Alignment, bool &AteExtraComma);
190    bool ParseIndexList(SmallVectorImpl<unsigned> &Indices,bool &AteExtraComma);
191    bool ParseIndexList(SmallVectorImpl<unsigned> &Indices) {
192      bool AteExtraComma;
193      if (ParseIndexList(Indices, AteExtraComma)) return true;
194      if (AteExtraComma)
195        return TokError("expected index");
196      return false;
197    }
198
199    // Top-Level Entities
200    bool ParseTopLevelEntities();
201    bool ValidateEndOfModule();
202    bool ParseTargetDefinition();
203    bool ParseDepLibs();
204    bool ParseModuleAsm();
205    bool ParseUnnamedType();
206    bool ParseNamedType();
207    bool ParseDeclare();
208    bool ParseDefine();
209
210    bool ParseGlobalType(bool &IsConstant);
211    bool ParseUnnamedGlobal();
212    bool ParseNamedGlobal();
213    bool ParseGlobal(const std::string &Name, LocTy Loc, unsigned Linkage,
214                     bool HasLinkage, unsigned Visibility);
215    bool ParseAlias(const std::string &Name, LocTy Loc, unsigned Visibility);
216    bool ParseStandaloneMetadata();
217    bool ParseNamedMetadata();
218    bool ParseMDString(MDString *&Result);
219    bool ParseMDNodeID(MDNode *&Result);
220    bool ParseMDNodeID(MDNode *&Result, unsigned &SlotNo);
221
222    // Type Parsing.
223    bool ParseType(Type *&Result, bool AllowVoid = false);
224    bool ParseType(Type *&Result, LocTy &Loc, bool AllowVoid = false) {
225      Loc = Lex.getLoc();
226      return ParseType(Result, AllowVoid);
227    }
228    bool ParseAnonStructType(Type *&Result, bool Packed);
229    bool ParseStructBody(SmallVectorImpl<Type*> &Body);
230    bool ParseStructDefinition(SMLoc TypeLoc, StringRef Name,
231                               std::pair<Type*, LocTy> &Entry,
232                               Type *&ResultTy);
233
234    bool ParseArrayVectorType(Type *&Result, bool isVector);
235    bool ParseFunctionType(Type *&Result);
236
237    // Function Semantic Analysis.
238    class PerFunctionState {
239      LLParser &P;
240      Function &F;
241      std::map<std::string, std::pair<Value*, LocTy> > ForwardRefVals;
242      std::map<unsigned, std::pair<Value*, LocTy> > ForwardRefValIDs;
243      std::vector<Value*> NumberedVals;
244
245      /// FunctionNumber - If this is an unnamed function, this is the slot
246      /// number of it, otherwise it is -1.
247      int FunctionNumber;
248    public:
249      PerFunctionState(LLParser &p, Function &f, int FunctionNumber);
250      ~PerFunctionState();
251
252      Function &getFunction() const { return F; }
253
254      bool FinishFunction();
255
256      /// GetVal - Get a value with the specified name or ID, creating a
257      /// forward reference record if needed.  This can return null if the value
258      /// exists but does not have the right type.
259      Value *GetVal(const std::string &Name, Type *Ty, LocTy Loc);
260      Value *GetVal(unsigned ID, Type *Ty, LocTy Loc);
261
262      /// SetInstName - After an instruction is parsed and inserted into its
263      /// basic block, this installs its name.
264      bool SetInstName(int NameID, const std::string &NameStr, LocTy NameLoc,
265                       Instruction *Inst);
266
267      /// GetBB - Get a basic block with the specified name or ID, creating a
268      /// forward reference record if needed.  This can return null if the value
269      /// is not a BasicBlock.
270      BasicBlock *GetBB(const std::string &Name, LocTy Loc);
271      BasicBlock *GetBB(unsigned ID, LocTy Loc);
272
273      /// DefineBB - Define the specified basic block, which is either named or
274      /// unnamed.  If there is an error, this returns null otherwise it returns
275      /// the block being defined.
276      BasicBlock *DefineBB(const std::string &Name, LocTy Loc);
277    };
278
279    bool ConvertValIDToValue(Type *Ty, ValID &ID, Value *&V,
280                             PerFunctionState *PFS);
281
282    bool ParseValue(Type *Ty, Value *&V, PerFunctionState *PFS);
283    bool ParseValue(Type *Ty, Value *&V, PerFunctionState &PFS) {
284      return ParseValue(Ty, V, &PFS);
285    }
286    bool ParseValue(Type *Ty, Value *&V, LocTy &Loc,
287                    PerFunctionState &PFS) {
288      Loc = Lex.getLoc();
289      return ParseValue(Ty, V, &PFS);
290    }
291
292    bool ParseTypeAndValue(Value *&V, PerFunctionState *PFS);
293    bool ParseTypeAndValue(Value *&V, PerFunctionState &PFS) {
294      return ParseTypeAndValue(V, &PFS);
295    }
296    bool ParseTypeAndValue(Value *&V, LocTy &Loc, PerFunctionState &PFS) {
297      Loc = Lex.getLoc();
298      return ParseTypeAndValue(V, PFS);
299    }
300    bool ParseTypeAndBasicBlock(BasicBlock *&BB, LocTy &Loc,
301                                PerFunctionState &PFS);
302    bool ParseTypeAndBasicBlock(BasicBlock *&BB, PerFunctionState &PFS) {
303      LocTy Loc;
304      return ParseTypeAndBasicBlock(BB, Loc, PFS);
305    }
306
307
308    struct ParamInfo {
309      LocTy Loc;
310      Value *V;
311      Attributes Attrs;
312      ParamInfo(LocTy loc, Value *v, Attributes attrs)
313        : Loc(loc), V(v), Attrs(attrs) {}
314    };
315    bool ParseParameterList(SmallVectorImpl<ParamInfo> &ArgList,
316                            PerFunctionState &PFS);
317
318    // Constant Parsing.
319    bool ParseValID(ValID &ID, PerFunctionState *PFS = NULL);
320    bool ParseGlobalValue(Type *Ty, Constant *&V);
321    bool ParseGlobalTypeAndValue(Constant *&V);
322    bool ParseGlobalValueVector(SmallVectorImpl<Constant*> &Elts);
323    bool ParseMetadataListValue(ValID &ID, PerFunctionState *PFS);
324    bool ParseMetadataValue(ValID &ID, PerFunctionState *PFS);
325    bool ParseMDNodeVector(SmallVectorImpl<Value*> &, PerFunctionState *PFS);
326    bool ParseInstructionMetadata(Instruction *Inst, PerFunctionState *PFS);
327
328    // Function Parsing.
329    struct ArgInfo {
330      LocTy Loc;
331      Type *Ty;
332      Attributes Attrs;
333      std::string Name;
334      ArgInfo(LocTy L, Type *ty, Attributes Attr, const std::string &N)
335        : Loc(L), Ty(ty), Attrs(Attr), Name(N) {}
336    };
337    bool ParseArgumentList(SmallVectorImpl<ArgInfo> &ArgList, bool &isVarArg);
338    bool ParseFunctionHeader(Function *&Fn, bool isDefine);
339    bool ParseFunctionBody(Function &Fn);
340    bool ParseBasicBlock(PerFunctionState &PFS);
341
342    // Instruction Parsing.  Each instruction parsing routine can return with a
343    // normal result, an error result, or return having eaten an extra comma.
344    enum InstResult { InstNormal = 0, InstError = 1, InstExtraComma = 2 };
345    int ParseInstruction(Instruction *&Inst, BasicBlock *BB,
346                         PerFunctionState &PFS);
347    bool ParseCmpPredicate(unsigned &Pred, unsigned Opc);
348
349    bool ParseRet(Instruction *&Inst, BasicBlock *BB, PerFunctionState &PFS);
350    bool ParseBr(Instruction *&Inst, PerFunctionState &PFS);
351    bool ParseSwitch(Instruction *&Inst, PerFunctionState &PFS);
352    bool ParseIndirectBr(Instruction *&Inst, PerFunctionState &PFS);
353    bool ParseInvoke(Instruction *&Inst, PerFunctionState &PFS);
354    bool ParseResume(Instruction *&Inst, PerFunctionState &PFS);
355
356    bool ParseArithmetic(Instruction *&I, PerFunctionState &PFS, unsigned Opc,
357                         unsigned OperandType);
358    bool ParseLogical(Instruction *&I, PerFunctionState &PFS, unsigned Opc);
359    bool ParseCompare(Instruction *&I, PerFunctionState &PFS, unsigned Opc);
360    bool ParseCast(Instruction *&I, PerFunctionState &PFS, unsigned Opc);
361    bool ParseSelect(Instruction *&I, PerFunctionState &PFS);
362    bool ParseVA_Arg(Instruction *&I, PerFunctionState &PFS);
363    bool ParseExtractElement(Instruction *&I, PerFunctionState &PFS);
364    bool ParseInsertElement(Instruction *&I, PerFunctionState &PFS);
365    bool ParseShuffleVector(Instruction *&I, PerFunctionState &PFS);
366    int ParsePHI(Instruction *&I, PerFunctionState &PFS);
367    bool ParseLandingPad(Instruction *&I, PerFunctionState &PFS);
368    bool ParseCall(Instruction *&I, PerFunctionState &PFS, bool isTail);
369    int ParseAlloc(Instruction *&I, PerFunctionState &PFS);
370    int ParseLoad(Instruction *&I, PerFunctionState &PFS);
371    int ParseStore(Instruction *&I, PerFunctionState &PFS);
372    int ParseCmpXchg(Instruction *&I, PerFunctionState &PFS);
373    int ParseAtomicRMW(Instruction *&I, PerFunctionState &PFS);
374    int ParseFence(Instruction *&I, PerFunctionState &PFS);
375    int ParseGetElementPtr(Instruction *&I, PerFunctionState &PFS);
376    int ParseExtractValue(Instruction *&I, PerFunctionState &PFS);
377    int ParseInsertValue(Instruction *&I, PerFunctionState &PFS);
378
379    bool ResolveForwardRefBlockAddresses(Function *TheFn,
380                             std::vector<std::pair<ValID, GlobalValue*> > &Refs,
381                                         PerFunctionState *PFS);
382  };
383} // End llvm namespace
384
385#endif
386