X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAsmParser%2FllvmAsmParser.y;h=0f5c11e1eae514ad55b904a0ba05884722b78e36;hb=cee8f9ae67104576b2028125b56e9ba4856a1d66;hp=28a768d1ff280ef7b3303ce389b5634deca63f5a;hpb=a28504313d4c3fe87173a71b511dd4c8e25c3312;p=oota-llvm.git diff --git a/lib/AsmParser/llvmAsmParser.y b/lib/AsmParser/llvmAsmParser.y index 28a768d1ff2..0f5c11e1eae 100644 --- a/lib/AsmParser/llvmAsmParser.y +++ b/lib/AsmParser/llvmAsmParser.y @@ -12,47 +12,120 @@ %{ #include "ParserInternals.h" -#include "llvm/BasicBlock.h" -#include "llvm/Method.h" +#include "llvm/Assembly/Parser.h" #include "llvm/SymbolTable.h" #include "llvm/Module.h" -#include "llvm/Type.h" +#include "llvm/GlobalVariable.h" +#include "llvm/Method.h" +#include "llvm/BasicBlock.h" #include "llvm/DerivedTypes.h" -#include "llvm/Assembly/Parser.h" -#include "llvm/ConstantPool.h" #include "llvm/iTerminators.h" #include "llvm/iMemory.h" +#include "Support/STLExtras.h" +#include "Support/DepthFirstIterator.h" #include #include // Get definition of pair class -#include // Get definition of find_if +#include #include // This embarasment is due to our flex lexer... -int yyerror(const char *ErrorMsg); // Forward declarations to prevent "implicit +int yyerror(const char *ErrorMsg); // Forward declarations to prevent "implicit int yylex(); // declaration" of xxx warnings. int yyparse(); static Module *ParserResult; string CurFilename; +// DEBUG_UPREFS - Define this symbol if you want to enable debugging output +// relating to upreferences in the input stream. +// +//#define DEBUG_UPREFS 1 +#ifdef DEBUG_UPREFS +#define UR_OUT(X) cerr << X +#else +#define UR_OUT(X) +#endif + // This contains info used when building the body of a method. It is destroyed // when the method is completed. // typedef vector ValueList; // Numbered defs -static void ResolveDefinitions(vector &LateResolvers); +static void ResolveDefinitions(vector &LateResolvers, + vector *FutureLateResolvers = 0); +static void ResolveTypes (vector > &LateResolveTypes); static struct PerModuleInfo { Module *CurrentModule; - vector Values; // Module level numbered definitions - vector LateResolveValues; + vector Values; // Module level numbered definitions + vector LateResolveValues; + vector > Types; + map > LateResolveTypes; + + // GlobalRefs - This maintains a mapping between 's and forward + // references to global values. Global values may be referenced before they + // are defined, and if so, the temporary object that they represent is held + // here. This is used for forward references of ConstPoolPointerRefs. + // + typedef map, GlobalVariable*> GlobalRefsType; + GlobalRefsType GlobalRefs; void ModuleDone() { - // If we could not resolve some blocks at parsing time (forward branches) - // resolve the branches now... + // If we could not resolve some methods at method compilation time (calls to + // methods before they are defined), resolve them now... Types are resolved + // when the constant pool has been completely parsed. + // ResolveDefinitions(LateResolveValues); + // Check to make sure that all global value forward references have been + // resolved! + // + if (!GlobalRefs.empty()) { + // TODO: Make this more detailed! Loop over each undef value and print + // info + ThrowException("TODO: Make better error - Unresolved forward constant " + "references exist!"); + } + Values.clear(); // Clear out method local definitions + Types.clear(); CurrentModule = 0; } + + + // DeclareNewGlobalValue - Called every type a new GV has been defined. This + // is used to remove things from the forward declaration map, resolving them + // to the correct thing as needed. + // + void DeclareNewGlobalValue(GlobalValue *GV, ValID D) { + // Check to see if there is a forward reference to this global variable... + // if there is, eliminate it and patch the reference to use the new def'n. + GlobalRefsType::iterator I = GlobalRefs.find(make_pair(GV->getType(), D)); + + if (I != GlobalRefs.end()) { + GlobalVariable *OldGV = I->second; // Get the placeholder... + I->first.second.destroy(); // Free string memory if neccesary + + // Loop over all of the uses of the GlobalValue. The only thing they are + // allowed to be at this point is ConstPoolPointerRef's. + assert(OldGV->use_size() == 1 && "Only one reference should exist!"); + while (!OldGV->use_empty()) { + User *U = OldGV->use_back(); // Must be a ConstPoolPointerRef... + ConstPoolPointerRef *CPPR = cast(U); + assert(CPPR->getValue() == OldGV && "Something isn't happy"); + + // Change the const pool reference to point to the real global variable + // now. This should drop a use from the OldGV. + CPPR->mutateReference(GV); + } + + // Remove GV from the module... + CurrentModule->getGlobalList().remove(OldGV); + delete OldGV; // Delete the old placeholder + + // Remove the map entry for the global now that it has been created... + GlobalRefs.erase(I); + } + } + } CurModule; static struct PerMethodInfo { @@ -60,6 +133,8 @@ static struct PerMethodInfo { vector Values; // Keep track of numbered definitions vector LateResolveValues; + vector > Types; + map > LateResolveTypes; bool isDeclare; // Is this method a forward declararation? inline PerMethodInfo() { @@ -76,34 +151,125 @@ static struct PerMethodInfo { void MethodDone() { // If we could not resolve some blocks at parsing time (forward branches) // resolve the branches now... - ResolveDefinitions(LateResolveValues); + ResolveDefinitions(LateResolveValues, &CurModule.LateResolveValues); Values.clear(); // Clear out method local definitions + Types.clear(); CurrentMethod = 0; isDeclare = false; } } CurMeth; // Info for the current method... +static bool inMethodScope() { return CurMeth.CurrentMethod != 0; } + //===----------------------------------------------------------------------===// // Code to handle definitions of all the types //===----------------------------------------------------------------------===// -static void InsertValue(Value *D, vector &ValueTab = CurMeth.Values) { - if (!D->hasName()) { // Is this a numbered definition? - unsigned type = D->getType()->getUniqueID(); - if (ValueTab.size() <= type) - ValueTab.resize(type+1, ValueList()); - //printf("Values[%d][%d] = %d\n", type, ValueTab[type].size(), D); - ValueTab[type].push_back(D); - } +static int InsertValue(Value *D, vector &ValueTab = CurMeth.Values) { + if (D->hasName()) return -1; // Is this a numbered definition? + + // Yes, insert the value into the value table... + unsigned type = D->getType()->getUniqueID(); + if (ValueTab.size() <= type) + ValueTab.resize(type+1, ValueList()); + //printf("Values[%d][%d] = %d\n", type, ValueTab[type].size(), D); + ValueTab[type].push_back(D); + return ValueTab[type].size()-1; +} + +// TODO: FIXME when Type are not const +static void InsertType(const Type *Ty, vector > &Types) { + Types.push_back(Ty); } -static Value *getVal(const Type *Type, ValID &D, - bool DoNotImprovise = false) { +static const Type *getTypeVal(const ValID &D, bool DoNotImprovise = false) { switch (D.Type) { case 0: { // Is it a numbered definition? - unsigned type = Type->getUniqueID(); + unsigned Num = (unsigned)D.Num; + + // Module constants occupy the lowest numbered slots... + if (Num < CurModule.Types.size()) + return CurModule.Types[Num]; + + Num -= CurModule.Types.size(); + + // Check that the number is within bounds... + if (Num <= CurMeth.Types.size()) + return CurMeth.Types[Num]; + break; + } + case 1: { // Is it a named definition? + string Name(D.Name); + SymbolTable *SymTab = 0; + if (inMethodScope()) SymTab = CurMeth.CurrentMethod->getSymbolTable(); + Value *N = SymTab ? SymTab->lookup(Type::TypeTy, Name) : 0; + + if (N == 0) { + // Symbol table doesn't automatically chain yet... because the method + // hasn't been added to the module... + // + SymTab = CurModule.CurrentModule->getSymbolTable(); + if (SymTab) + N = SymTab->lookup(Type::TypeTy, Name); + if (N == 0) break; + } + + D.destroy(); // Free old strdup'd memory... + return cast(N); + } + default: + ThrowException("Invalid symbol type reference!"); + } + + // If we reached here, we referenced either a symbol that we don't know about + // or an id number that hasn't been read yet. We may be referencing something + // forward, so just create an entry to be resolved later and get to it... + // + if (DoNotImprovise) return 0; // Do we just want a null to be returned? + + map > &LateResolver = inMethodScope() ? + CurMeth.LateResolveTypes : CurModule.LateResolveTypes; + + map >::iterator I = LateResolver.find(D); + if (I != LateResolver.end()) { + return I->second; + } + + Type *Typ = OpaqueType::get(); + LateResolver.insert(make_pair(D, Typ)); + return Typ; +} + +static Value *lookupInSymbolTable(const Type *Ty, const string &Name) { + SymbolTable *SymTab = + inMethodScope() ? CurMeth.CurrentMethod->getSymbolTable() : 0; + Value *N = SymTab ? SymTab->lookup(Ty, Name) : 0; + + if (N == 0) { + // Symbol table doesn't automatically chain yet... because the method + // hasn't been added to the module... + // + SymTab = CurModule.CurrentModule->getSymbolTable(); + if (SymTab) + N = SymTab->lookup(Ty, Name); + } + + return N; +} + +// getValNonImprovising - Look up the value specified by the provided type and +// the provided ValID. If the value exists and has already been defined, return +// it. Otherwise return null. +// +static Value *getValNonImprovising(const Type *Ty, const ValID &D) { + if (isa(Ty)) + ThrowException("Methods are not values and must be referenced as pointers"); + + switch (D.Type) { + case ValID::NumberVal: { // Is it a numbered definition? + unsigned type = Ty->getUniqueID(); unsigned Num = (unsigned)D.Num; // Module constants occupy the lowest numbered slots... @@ -115,118 +281,99 @@ static Value *getVal(const Type *Type, ValID &D, } // Make sure that our type is within bounds - if (CurMeth.Values.size() <= type) - break; + if (CurMeth.Values.size() <= type) return 0; // Check that the number is within bounds... - if (CurMeth.Values[type].size() <= Num) - break; + if (CurMeth.Values[type].size() <= Num) return 0; return CurMeth.Values[type][Num]; } - case 1: { // Is it a named definition? - string Name(D.Name); - SymbolTable *SymTab = 0; - if (CurMeth.CurrentMethod) - SymTab = CurMeth.CurrentMethod->getSymbolTable(); - Value *N = SymTab ? SymTab->lookup(Type, Name) : 0; - if (N == 0) { - SymTab = CurModule.CurrentModule->getSymbolTable(); - if (SymTab) - N = SymTab->lookup(Type, Name); - if (N == 0) break; - } + case ValID::NameVal: { // Is it a named definition? + Value *N = lookupInSymbolTable(Ty, string(D.Name)); + if (N == 0) return 0; D.destroy(); // Free old strdup'd memory... return N; } - case 2: // Is it a constant pool reference?? - case 3: // Is it an unsigned const pool reference? - case 4: // Is it a string const pool reference? - case 5:{ // Is it a floating point const pool reference? - ConstPoolVal *CPV = 0; + // Check to make sure that "Ty" is an integral type, and that our + // value will fit into the specified type... + case ValID::ConstSIntVal: // Is it a constant pool reference?? + if (Ty == Type::BoolTy) { // Special handling for boolean data + return ConstPoolBool::get(D.ConstPool64 != 0); + } else { + if (!ConstPoolSInt::isValueValidForType(Ty, D.ConstPool64)) + ThrowException("Symbolic constant pool value '" + + itostr(D.ConstPool64) + "' is invalid for type '" + + Ty->getName() + "'!"); + return ConstPoolSInt::get(Ty, D.ConstPool64); + } - // Check to make sure that "Type" is an integral type, and that our - // value will fit into the specified type... - switch (D.Type) { - case 2: - if (Type == Type::BoolTy) { // Special handling for boolean data - CPV = new ConstPoolBool(D.ConstPool64 != 0); - } else { - if (!ConstPoolSInt::isValueValidForType(Type, D.ConstPool64)) - ThrowException("Symbolic constant pool value '" + - itostr(D.ConstPool64) + "' is invalid for type '" + - Type->getName() + "'!"); - CPV = new ConstPoolSInt(Type, D.ConstPool64); - } - break; - case 3: - if (!ConstPoolUInt::isValueValidForType(Type, D.UConstPool64)) { - if (!ConstPoolSInt::isValueValidForType(Type, D.ConstPool64)) { - ThrowException("Integral constant pool reference is invalid!"); - } else { // This is really a signed reference. Transmogrify. - CPV = new ConstPoolSInt(Type, D.ConstPool64); - } - } else { - CPV = new ConstPoolUInt(Type, D.UConstPool64); + case ValID::ConstUIntVal: // Is it an unsigned const pool reference? + if (!ConstPoolUInt::isValueValidForType(Ty, D.UConstPool64)) { + if (!ConstPoolSInt::isValueValidForType(Ty, D.ConstPool64)) { + ThrowException("Integral constant pool reference is invalid!"); + } else { // This is really a signed reference. Transmogrify. + return ConstPoolSInt::get(Ty, D.ConstPool64); } - break; - case 4: - cerr << "FIXME: TODO: String constants [sbyte] not implemented yet!\n"; - abort(); - //CPV = new ConstPoolString(D.Name); - D.destroy(); // Free the string memory - break; - case 5: - if (!ConstPoolFP::isValueValidForType(Type, D.ConstPoolFP)) - ThrowException("FP constant invalid for type!!"); - else - CPV = new ConstPoolFP(Type, D.ConstPoolFP); - break; + } else { + return ConstPoolUInt::get(Ty, D.UConstPool64); } - assert(CPV && "How did we escape creating a constant??"); - // Scan through the constant table and see if we already have loaded this - // constant. - // - ConstantPool &CP = CurMeth.CurrentMethod ? - CurMeth.CurrentMethod->getConstantPool() : - CurModule.CurrentModule->getConstantPool(); - ConstPoolVal *C = CP.find(CPV); // Already have this constant? - if (C) { - delete CPV; // Didn't need this after all, oh well. - return C; // Yup, we already have one, recycle it! - } - CP.insert(CPV); - - // Success, everything is kosher. Lets go! - return CPV; - } // End of case 2,3,4 + case ValID::ConstStringVal: // Is it a string const pool reference? + cerr << "FIXME: TODO: String constants [sbyte] not implemented yet!\n"; + abort(); + return 0; + + case ValID::ConstFPVal: // Is it a floating point const pool reference? + if (!ConstPoolFP::isValueValidForType(Ty, D.ConstPoolFP)) + ThrowException("FP constant invalid for type!!"); + return ConstPoolFP::get(Ty, D.ConstPoolFP); + + case ValID::ConstNullVal: // Is it a null value? + if (!Ty->isPointerType()) + ThrowException("Cannot create a a non pointer null!"); + return ConstPoolPointerNull::get(cast(Ty)); + + default: + assert(0 && "Unhandled case!"); + return 0; } // End of switch + assert(0 && "Unhandled case!"); + return 0; +} + + +// getVal - This function is identical to getValNonImprovising, except that if a +// value is not already defined, it "improvises" by creating a placeholder var +// that looks and acts just like the requested variable. When the value is +// defined later, all uses of the placeholder variable are replaced with the +// real thing. +// +static Value *getVal(const Type *Ty, const ValID &D) { + assert(Ty != Type::TypeTy && "Should use getTypeVal for types!"); + + // See if the value has already been defined... + Value *V = getValNonImprovising(Ty, D); + if (V) return V; // If we reached here, we referenced either a symbol that we don't know about // or an id number that hasn't been read yet. We may be referencing something // forward, so just create an entry to be resolved later and get to it... // - if (DoNotImprovise) return 0; // Do we just want a null to be returned? - - // TODO: Attempt to coallecse nodes that are the same with previous ones. Value *d = 0; - switch (Type->getPrimitiveID()) { - case Type::LabelTyID: d = new BBPlaceHolder(Type, D); break; - case Type::MethodTyID: - d = new MethPlaceHolder(Type, D); - InsertValue(d, CurModule.LateResolveValues); - return d; -//case Type::ClassTyID: d = new ClassPlaceHolder(Type, D); break; - default: d = new DefPlaceHolder(Type, D); break; + switch (Ty->getPrimitiveID()) { + case Type::LabelTyID: d = new BBPlaceHolder(Ty, D); break; + default: d = new ValuePlaceHolder(Ty, D); break; } assert(d != 0 && "How did we not make something?"); - InsertValue(d, CurMeth.LateResolveValues); + if (inMethodScope()) + InsertValue(d, CurMeth.LateResolveValues); + else + InsertValue(d, CurModule.LateResolveValues); return d; } @@ -247,121 +394,224 @@ static Value *getVal(const Type *Type, ValID &D, // time (forward branches, phi functions for loops, etc...) resolve the // defs now... // -static void ResolveDefinitions(vector &LateResolvers) { +static void ResolveDefinitions(vector &LateResolvers, + vector *FutureLateResolvers = 0) { // Loop over LateResolveDefs fixing up stuff that couldn't be resolved for (unsigned ty = 0; ty < LateResolvers.size(); ty++) { while (!LateResolvers[ty].empty()) { Value *V = LateResolvers[ty].back(); + assert(!isa(V) && "Types should be in LateResolveTypes!"); + LateResolvers[ty].pop_back(); ValID &DID = getValIDFromPlaceHolder(V); - Value *TheRealValue = getVal(Type::getUniqueIDType(ty), DID, true); - - if (TheRealValue == 0 && DID.Type == 1) - ThrowException("Reference to an invalid definition: '" +DID.getName() + - "' of type '" + V->getType()->getName() + "'"); - else if (TheRealValue == 0) - ThrowException("Reference to an invalid definition: #" +itostr(DID.Num)+ - " of type '" + V->getType()->getName() + "'"); - - V->replaceAllUsesWith(TheRealValue); - assert(V->use_empty()); - delete V; + Value *TheRealValue = getValNonImprovising(Type::getUniqueIDType(ty),DID); + if (TheRealValue) { + V->replaceAllUsesWith(TheRealValue); + delete V; + } else if (FutureLateResolvers) { + // Methods have their unresolved items forwarded to the module late + // resolver table + InsertValue(V, *FutureLateResolvers); + } else { + if (DID.Type == 1) + ThrowException("Reference to an invalid definition: '" +DID.getName()+ + "' of type '" + V->getType()->getDescription() + "'", + getLineNumFromPlaceHolder(V)); + else + ThrowException("Reference to an invalid definition: #" + + itostr(DID.Num) + " of type '" + + V->getType()->getDescription() + "'", + getLineNumFromPlaceHolder(V)); + } } } LateResolvers.clear(); } -// addConstValToConstantPool - This code is used to insert a constant into the -// current constant pool. This is designed to make maximal (but not more than -// possible) reuse (merging) of constants in the constant pool. This means that -// multiple references to %4, for example will all get merged. +// ResolveType - Take a specified unresolved type and resolve it. If there is +// nothing to resolve it to yet, return true. Otherwise resolve it and return +// false. +// +static bool ResolveType(PATypeHolder &T) { + const Type *Ty = T; + ValID &DID = getValIDFromPlaceHolder(Ty); + + const Type *TheRealType = getTypeVal(DID, true); + if (TheRealType == 0 || TheRealType == Ty) return true; + + // Refine the opaque type we had to the new type we are getting. + cast(Ty)->refineAbstractTypeTo(TheRealType); + return false; +} + +// ResolveTypeTo - A brand new type was just declared. This means that (if +// name is not null) things referencing Name can be resolved. Otherwise, things +// refering to the number can be resolved. Do this now. +// +static void ResolveTypeTo(char *Name, const Type *ToTy) { + vector > &Types = inMethodScope() ? + CurMeth.Types : CurModule.Types; + + ValID D; + if (Name) D = ValID::create(Name); + else D = ValID::create((int)Types.size()); + + map > &LateResolver = inMethodScope() ? + CurMeth.LateResolveTypes : CurModule.LateResolveTypes; + + map >::iterator I = LateResolver.find(D); + if (I != LateResolver.end()) { + cast(I->second.get())->refineAbstractTypeTo(ToTy); + LateResolver.erase(I); + } +} + +// ResolveTypes - At this point, all types should be resolved. Any that aren't +// are errors. +// +static void ResolveTypes(map > &LateResolveTypes) { + if (!LateResolveTypes.empty()) { + const ValID &DID = LateResolveTypes.begin()->first; + + if (DID.Type == ValID::NameVal) + ThrowException("Reference to an invalid type: '" +DID.getName() + "'"); + else + ThrowException("Reference to an invalid type: #" + itostr(DID.Num)); + } +} + + +// setValueName - Set the specified value to the name given. The name may be +// null potentially, in which case this is a noop. The string passed in is +// assumed to be a malloc'd string buffer, and is freed by this function. // -static ConstPoolVal *addConstValToConstantPool(ConstPoolVal *C) { - vector &ValTab = CurMeth.CurrentMethod ? - CurMeth.Values : CurModule.Values; - ConstantPool &CP = CurMeth.CurrentMethod ? - CurMeth.CurrentMethod->getConstantPool() : - CurModule.CurrentModule->getConstantPool(); - - if (ConstPoolVal *CPV = CP.find(C)) { - // Constant already in constant pool. Try to merge the two constants - if (CPV->hasName() && !C->hasName()) { - // Merge the two values, we inherit the existing CPV's name. - // InsertValue requires that the value have no name to insert correctly - // (because we want to fill the slot this constant would have filled) +// This function returns true if the value has already been defined, but is +// allowed to be redefined in the specified context. If the name is a new name +// for the typeplane, false is returned. +// +static bool setValueName(Value *V, char *NameStr) { + if (NameStr == 0) return false; + + string Name(NameStr); // Copy string + free(NameStr); // Free old string + + if (V->getType() == Type::VoidTy) + ThrowException("Can't assign name '" + Name + + "' to a null valued instruction!"); + + SymbolTable *ST = inMethodScope() ? + CurMeth.CurrentMethod->getSymbolTableSure() : + CurModule.CurrentModule->getSymbolTableSure(); + + Value *Existing = ST->lookup(V->getType(), Name); + if (Existing) { // Inserting a name that is already defined??? + // There is only one case where this is allowed: when we are refining an + // opaque type. In this case, Existing will be an opaque type. + if (const Type *Ty = dyn_cast(Existing)) { + if (OpaqueType *OpTy = dyn_cast(Ty)) { + // We ARE replacing an opaque type! + OpTy->refineAbstractTypeTo(cast(V)); + return true; + } + } + + // Otherwise, we are a simple redefinition of a value, check to see if it + // is defined the same as the old one... + if (const Type *Ty = dyn_cast(Existing)) { + if (Ty == cast(V)) return true; // Yes, it's equal. + // cerr << "Type: " << Ty->getDescription() << " != " + // << cast(V)->getDescription() << "!\n"; + } else if (GlobalVariable *EGV = dyn_cast(Existing)) { + // We are allowed to redefine a global variable in two circumstances: + // 1. If at least one of the globals is uninitialized or + // 2. If both initializers have the same value. // - string Name = CPV->getName(); - CPV->setName(""); - InsertValue(CPV, ValTab); - CPV->setName(Name); - delete C; - return CPV; - } else if (!CPV->hasName() && C->hasName()) { - // If we have a name on this value and there isn't one in the const - // pool val already, propogate it. + // This can only be done if the const'ness of the vars is the same. // - CPV->setName(C->getName()); - delete C; // Sorry, you're toast - return CPV; - } else if (CPV->hasName() && C->hasName()) { - // Both values have distinct names. We cannot merge them. - CP.insert(C); - InsertValue(C, ValTab); - return C; - } else if (!CPV->hasName() && !C->hasName()) { - // Neither value has a name, trivially merge them. - InsertValue(CPV, ValTab); - delete C; - return CPV; + if (GlobalVariable *GV = dyn_cast(V)) { + if (EGV->isConstant() == GV->isConstant() && + (!EGV->hasInitializer() || !GV->hasInitializer() || + EGV->getInitializer() == GV->getInitializer())) { + + // Make sure the existing global version gets the initializer! + if (GV->hasInitializer() && !EGV->hasInitializer()) + EGV->setInitializer(GV->getInitializer()); + + delete GV; // Destroy the duplicate! + return true; // They are equivalent! + } + } } + ThrowException("Redefinition of value named '" + Name + "' in the '" + + V->getType()->getDescription() + "' type plane!"); + } - assert(0 && "Not reached!"); - return 0; - } else { // No duplication of value. - CP.insert(C); - InsertValue(C, ValTab); - return C; - } + V->setName(Name, ST); + return false; } -struct EqualsType { - const Type *T; - inline EqualsType(const Type *t) { T = t; } - inline bool operator()(const ConstPoolVal *CPV) const { - return static_cast(CPV)->getValue() == T; - } -}; - +//===----------------------------------------------------------------------===// +// Code for handling upreferences in type names... +// -// checkNewType - We have to be careful to add all types referenced by the -// program to the constant pool of the method or module. Because of this, we -// often want to check to make sure that types used are in the constant pool, -// and add them if they aren't. That's what this function does. +// TypeContains - Returns true if Ty contains E in it. // -static const Type *checkNewType(const Type *Ty) { - ConstantPool &CP = CurMeth.CurrentMethod ? - CurMeth.CurrentMethod->getConstantPool() : - CurModule.CurrentModule->getConstantPool(); - - // TODO: This should use ConstantPool::ensureTypeAvailable - - // Get the type type plane... - ConstantPool::PlaneType &P = CP.getPlane(Type::TypeTy); - ConstantPool::PlaneType::const_iterator PI = find_if(P.begin(), P.end(), - EqualsType(Ty)); - if (PI == P.end()) { - vector &ValTab = CurMeth.CurrentMethod ? - CurMeth.Values : CurModule.Values; - ConstPoolVal *CPT = new ConstPoolType(Ty); - CP.insert(CPT); - InsertValue(CPT, ValTab); +static bool TypeContains(const Type *Ty, const Type *E) { + return find(df_begin(Ty), df_end(Ty), E) != df_end(Ty); +} + + +static vector > UpRefs; + +static PATypeHolder HandleUpRefs(const Type *ty) { + PATypeHolder Ty(ty); + UR_OUT("Type '" << ty->getDescription() << + "' newly formed. Resolving upreferences.\n" << + UpRefs.size() << " upreferences active!\n"); + for (unsigned i = 0; i < UpRefs.size(); ) { + UR_OUT(" UR#" << i << " - TypeContains(" << Ty->getDescription() << ", " + << UpRefs[i].second->getDescription() << ") = " + << (TypeContains(Ty, UpRefs[i].second) ? "true" : "false") << endl); + if (TypeContains(Ty, UpRefs[i].second)) { + unsigned Level = --UpRefs[i].first; // Decrement level of upreference + UR_OUT(" Uplevel Ref Level = " << Level << endl); + if (Level == 0) { // Upreference should be resolved! + UR_OUT(" * Resolving upreference for " + << UpRefs[i].second->getDescription() << endl; + string OldName = UpRefs[i].second->getDescription()); + UpRefs[i].second->refineAbstractTypeTo(Ty); + UpRefs.erase(UpRefs.begin()+i); // Remove from upreference list... + UR_OUT(" * Type '" << OldName << "' refined upreference to: " + << (const void*)Ty << ", " << Ty->getDescription() << endl); + continue; + } + } + + ++i; // Otherwise, no resolve, move on... } + // FIXME: TODO: this should return the updated type return Ty; } +template +inline static void TypeDone(PATypeHolder *Ty) { + if (UpRefs.size()) + ThrowException("Invalid upreference in type: " + (*Ty)->getDescription()); +} + +// newTH - Allocate a new type holder for the specified type +template +inline static PATypeHolder *newTH(const TypeTy *Ty) { + return new PATypeHolder(Ty); +} +template +inline static PATypeHolder *newTH(const PATypeHolder &TH) { + return new PATypeHolder(TH); +} + //===----------------------------------------------------------------------===// // RunVMAsmParser - Define an interface to this parser @@ -384,36 +634,40 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) { %} %union { - Module *ModuleVal; - Method *MethodVal; - MethodArgument *MethArgVal; - BasicBlock *BasicBlockVal; - TerminatorInst *TermInstVal; - Instruction *InstVal; - ConstPoolVal *ConstVal; - const Type *TypeVal; - - list *MethodArgList; - list *ValueList; - list *TypeList; + Module *ModuleVal; + Method *MethodVal; + MethodArgument *MethArgVal; + BasicBlock *BasicBlockVal; + TerminatorInst *TermInstVal; + Instruction *InstVal; + ConstPoolVal *ConstVal; + + const Type *PrimType; + PATypeHolder *TypeVal; + Value *ValueVal; + + list *MethodArgList; + vector *ValueList; + list > *TypeList; list > *PHIList; // Represent the RHS of PHI node list > *JumpTable; - vector *ConstVector; - - int64_t SInt64Val; - uint64_t UInt64Val; - int SIntVal; - unsigned UIntVal; - double FPVal; - - char *StrVal; // This memory is allocated by strdup! - ValID ValIDVal; // May contain memory allocated by strdup - - Instruction::UnaryOps UnaryOpVal; - Instruction::BinaryOps BinaryOpVal; - Instruction::TermOps TermOpVal; - Instruction::MemoryOps MemOpVal; - Instruction::OtherOps OtherOpVal; + vector *ConstVector; + + int64_t SInt64Val; + uint64_t UInt64Val; + int SIntVal; + unsigned UIntVal; + double FPVal; + bool BoolVal; + + char *StrVal; // This memory is strdup'd! + ValID ValIDVal; // strdup'd memory maybe! + + Instruction::UnaryOps UnaryOpVal; + Instruction::BinaryOps BinaryOpVal; + Instruction::TermOps TermOpVal; + Instruction::MemoryOps MemOpVal; + Instruction::OtherOps OtherOpVal; } %type Module MethodList @@ -422,16 +676,19 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) { %type BBTerminatorInst %type Inst InstVal MemoryInst %type ConstVal -%type ConstVector UByteList +%type ConstVector %type ArgList ArgListH %type ArgVal %type PHIList %type ValueRefList ValueRefListE // For call param lists -%type TypeList +%type IndexList // For GEP derived indices +%type TypeListI ArgTypeListI %type JumpTable +%type GlobalType OptInternal // GLOBAL or CONSTANT? Intern? -%type ValueRef ConstValueRef // Reference to a definition or BB - +// ValueRef - Unresolved reference to a definition or BB +%type ValueRef ConstValueRef SymbolicValueRef +%type ResolvedVal // pair // Tokens and types for handling constant integer values // // ESINT64VAL - A negative number within long long range @@ -447,15 +704,18 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) { %token FPVAL // Float or Double constant // Built in types... -%type Types TypesV SIntType UIntType IntType FPType -%token VOID BOOL SBYTE UBYTE SHORT USHORT INT UINT LONG ULONG -%token FLOAT DOUBLE STRING TYPE LABEL +%type Types TypesV UpRTypes UpRTypesV +%type SIntType UIntType IntType FPType PrimType // Classifications +%token OPAQUE +%token VOID BOOL SBYTE UBYTE SHORT USHORT INT UINT LONG ULONG +%token FLOAT DOUBLE TYPE LABEL %token VAR_ID LABELSTR STRINGCONSTANT %type OptVAR_ID OptAssign -%token IMPLEMENTATION TRUE FALSE BEGINTOK END DECLARE TO +%token IMPLEMENTATION TRUE FALSE BEGINTOK END DECLARE GLOBAL CONSTANT UNINIT +%token TO EXCEPT DOTDOTDOT STRING NULL_TOK CONST INTERNAL // Basic Block Terminating Operators %token RET BR SWITCH @@ -466,7 +726,7 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) { // Binary Operators %type BinaryOps // all the binary operators -%token ADD SUB MUL DIV REM +%token ADD SUB MUL DIV REM AND OR XOR %token SETLE SETGE SETLT SETGT SETEQ SETNE // Binary Comarators // Memory Instructions @@ -474,7 +734,7 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) { // Other Operators %type ShiftOps -%token PHI CALL CAST SHL SHR +%token PHI CALL INVOKE CAST SHL SHR %start Module %% @@ -497,22 +757,11 @@ EINT64VAL : EUINT64VAL { $$ = (int64_t)$1; } -// Types includes all predefined types... except void, because you can't do -// anything with it except for certain specific things... -// -// User defined types are added later... -// -Types : BOOL | SBYTE | UBYTE | SHORT | USHORT | INT | UINT -Types : LONG | ULONG | FLOAT | DOUBLE | STRING | TYPE | LABEL - -// TypesV includes all of 'Types', but it also includes the void type. -TypesV : Types | VOID - // Operations that are notably excluded from this list include: // RET, BR, & SWITCH because they end basic blocks and are treated specially. // UnaryOps : NOT -BinaryOps : ADD | SUB | MUL | DIV | REM +BinaryOps : ADD | SUB | MUL | DIV | REM | AND | OR | XOR BinaryOps : SETLE | SETGE | SETLT | SETGT | SETEQ | SETNE ShiftOps : SHL | SHR @@ -520,8 +769,8 @@ ShiftOps : SHL | SHR // thing... for example, only a signed, unsigned, or integral type. SIntType : LONG | INT | SHORT | SBYTE UIntType : ULONG | UINT | USHORT | UBYTE -IntType : SIntType | UIntType -FPType : FLOAT | DOUBLE +IntType : SIntType | UIntType +FPType : FLOAT | DOUBLE // OptAssign - Value producing statements have an optional assignment component OptAssign : VAR_ID '=' { @@ -531,131 +780,331 @@ OptAssign : VAR_ID '=' { $$ = 0; } -// ConstVal - The various declarations that go into the constant pool. This -// includes all forward declarations of types, constants, and functions. +OptInternal : INTERNAL { $$ = true; } | /*empty*/ { $$ = false; } + +//===----------------------------------------------------------------------===// +// Types includes all predefined types... except void, because it can only be +// used in specific contexts (method returning void for example). To have +// access to it, a user must explicitly use TypesV. // -ConstVal : SIntType EINT64VAL { // integral constants - if (!ConstPoolSInt::isValueValidForType($1, $2)) - ThrowException("Constant value doesn't fit in type!"); - $$ = new ConstPoolSInt($1, $2); - } - | UIntType EUINT64VAL { // integral constants - if (!ConstPoolUInt::isValueValidForType($1, $2)) - ThrowException("Constant value doesn't fit in type!"); - $$ = new ConstPoolUInt($1, $2); - } - | BOOL TRUE { // Boolean constants - $$ = new ConstPoolBool(true); + +// TypesV includes all of 'Types', but it also includes the void type. +TypesV : Types | VOID { $$ = newTH($1); } +UpRTypesV : UpRTypes | VOID { $$ = newTH($1); } + +Types : UpRTypes { + TypeDone($$ = $1); } - | BOOL FALSE { // Boolean constants - $$ = new ConstPoolBool(false); + + +// Derived types are added later... +// +PrimType : BOOL | SBYTE | UBYTE | SHORT | USHORT | INT | UINT +PrimType : LONG | ULONG | FLOAT | DOUBLE | TYPE | LABEL +UpRTypes : OPAQUE | PrimType { $$ = newTH($1); } +UpRTypes : ValueRef { // Named types are also simple types... + $$ = newTH(getTypeVal($1)); +} + +// Include derived types in the Types production. +// +UpRTypes : '\\' EUINT64VAL { // Type UpReference + if ($2 > (uint64_t)INT64_MAX) ThrowException("Value out of range!"); + OpaqueType *OT = OpaqueType::get(); // Use temporary placeholder + UpRefs.push_back(make_pair((unsigned)$2, OT)); // Add to vector... + $$ = newTH(OT); + UR_OUT("New Upreference!\n"); + } + | UpRTypesV '(' ArgTypeListI ')' { // Method derived type? + vector Params; + mapto($3->begin(), $3->end(), back_inserter(Params), + mem_fun_ref(&PATypeHandle::get)); + bool isVarArg = Params.size() && Params.back() == Type::VoidTy; + if (isVarArg) Params.pop_back(); + + $$ = newTH(HandleUpRefs(MethodType::get(*$1, Params, isVarArg))); + delete $3; // Delete the argument list + delete $1; // Delete the old type handle + } + | '[' UpRTypesV ']' { // Unsized array type? + $$ = newTH(HandleUpRefs(ArrayType::get(*$2))); + delete $2; } - | FPType FPVAL { // Float & Double constants - $$ = new ConstPoolFP($1, $2); + | '[' EUINT64VAL 'x' UpRTypes ']' { // Sized array type? + $$ = newTH(HandleUpRefs(ArrayType::get(*$4, (int)$2))); + delete $4; } - | STRING STRINGCONSTANT { // String constants - cerr << "FIXME: TODO: String constants [sbyte] not implemented yet!\n"; - abort(); - //$$ = new ConstPoolString($2); - free($2); - } - | TYPE Types { // Type constants - $$ = new ConstPoolType($2); + | '{' TypeListI '}' { // Structure type? + vector Elements; + mapto($2->begin(), $2->end(), back_inserter(Elements), + mem_fun_ref(&PATypeHandle::get)); + + $$ = newTH(HandleUpRefs(StructType::get(Elements))); + delete $2; + } + | '{' '}' { // Empty structure type? + $$ = newTH(StructType::get(vector())); + } + | UpRTypes '*' { // Pointer type? + $$ = newTH(HandleUpRefs(PointerType::get(*$1))); + delete $1; } - | '[' Types ']' '[' ConstVector ']' { // Nonempty array constant - // Verify all elements are correct type! - const ArrayType *AT = ArrayType::getArrayType($2); - for (unsigned i = 0; i < $5->size(); i++) { - if ($2 != (*$5)[i]->getType()) - ThrowException("Element #" + utostr(i) + " is not of type '" + - $2->getName() + "' as required!\nIt is of type '" + - (*$5)[i]->getType()->getName() + "'."); - } - $$ = new ConstPoolArray(AT, *$5); - delete $5; +// TypeList - Used for struct declarations and as a basis for method type +// declaration type lists +// +TypeListI : UpRTypes { + $$ = new list >(); + $$->push_back(*$1); delete $1; } - | '[' Types ']' '[' ']' { // Empty array constant - vector Empty; - $$ = new ConstPoolArray(ArrayType::getArrayType($2), Empty); + | TypeListI ',' UpRTypes { + ($$=$1)->push_back(*$3); delete $3; } - | '[' EUINT64VAL 'x' Types ']' '[' ConstVector ']' { - // Verify all elements are correct type! - const ArrayType *AT = ArrayType::getArrayType($4, (int)$2); - if ($2 != $7->size()) + +// ArgTypeList - List of types for a method type declaration... +ArgTypeListI : TypeListI + | TypeListI ',' DOTDOTDOT { + ($$=$1)->push_back(Type::VoidTy); + } + | DOTDOTDOT { + ($$ = new list >())->push_back(Type::VoidTy); + } + | /*empty*/ { + $$ = new list >(); + } + + +// ConstVal - The various declarations that go into the constant pool. This +// includes all forward declarations of types, constants, and functions. +// +ConstVal: Types '[' ConstVector ']' { // Nonempty unsized arr + const ArrayType *ATy = dyn_cast($1->get()); + if (ATy == 0) + ThrowException("Cannot make array constant with type: '" + + (*$1)->getDescription() + "'!"); + const Type *ETy = ATy->getElementType(); + int NumElements = ATy->getNumElements(); + + // Verify that we have the correct size... + if (NumElements != -1 && NumElements != (int)$3->size()) ThrowException("Type mismatch: constant sized array initialized with " + - utostr($7->size()) + " arguments, but has size of " + - itostr((int)$2) + "!"); + utostr($3->size()) + " arguments, but has size of " + + itostr(NumElements) + "!"); - for (unsigned i = 0; i < $7->size(); i++) { - if ($4 != (*$7)[i]->getType()) + // Verify all elements are correct type! + for (unsigned i = 0; i < $3->size(); i++) { + if (ETy != (*$3)[i]->getType()) ThrowException("Element #" + utostr(i) + " is not of type '" + - $4->getName() + "' as required!\nIt is of type '" + - (*$7)[i]->getType()->getName() + "'."); + ETy->getName() + "' as required!\nIt is of type '" + + (*$3)[i]->getType()->getName() + "'."); } - $$ = new ConstPoolArray(AT, *$7); - delete $7; + $$ = ConstPoolArray::get(ATy, *$3); + delete $1; delete $3; } - | '[' EUINT64VAL 'x' Types ']' '[' ']' { - if ($2 != 0) + | Types '[' ']' { + const ArrayType *ATy = dyn_cast($1->get()); + if (ATy == 0) + ThrowException("Cannot make array constant with type: '" + + (*$1)->getDescription() + "'!"); + + int NumElements = ATy->getNumElements(); + if (NumElements != -1 && NumElements != 0) ThrowException("Type mismatch: constant sized array initialized with 0" - " arguments, but has size of " + itostr((int)$2) + "!"); - vector Empty; - $$ = new ConstPoolArray(ArrayType::getArrayType($4, 0), Empty); + " arguments, but has size of " + itostr(NumElements) +"!"); + $$ = ConstPoolArray::get(ATy, vector()); + delete $1; + } + | Types 'c' STRINGCONSTANT { + const ArrayType *ATy = dyn_cast($1->get()); + if (ATy == 0) + ThrowException("Cannot make array constant with type: '" + + (*$1)->getDescription() + "'!"); + + int NumElements = ATy->getNumElements(); + const Type *ETy = ATy->getElementType(); + char *EndStr = UnEscapeLexed($3, true); + if (NumElements != -1 && NumElements != (EndStr-$3)) + ThrowException("Can't build string constant of size " + + itostr((int)(EndStr-$3)) + + " when array has size " + itostr(NumElements) + "!"); + vector Vals; + if (ETy == Type::SByteTy) { + for (char *C = $3; C != EndStr; ++C) + Vals.push_back(ConstPoolSInt::get(ETy, *C)); + } else if (ETy == Type::UByteTy) { + for (char *C = $3; C != EndStr; ++C) + Vals.push_back(ConstPoolUInt::get(ETy, *C)); + } else { + free($3); + ThrowException("Cannot build string arrays of non byte sized elements!"); + } + free($3); + $$ = ConstPoolArray::get(ATy, Vals); + delete $1; + } + | Types '{' ConstVector '}' { + const StructType *STy = dyn_cast($1->get()); + if (STy == 0) + ThrowException("Cannot make struct constant with type: '" + + (*$1)->getDescription() + "'!"); + // FIXME: TODO: Check to see that the constants are compatible with the type + // initializer! + $$ = ConstPoolStruct::get(STy, *$3); + delete $1; delete $3; + } + | Types NULL_TOK { + const PointerType *PTy = dyn_cast($1->get()); + if (PTy == 0) + ThrowException("Cannot make null pointer constant with type: '" + + (*$1)->getDescription() + "'!"); + + $$ = ConstPoolPointerNull::get(PTy); + delete $1; + } + | Types SymbolicValueRef { + const PointerType *Ty = dyn_cast($1->get()); + if (Ty == 0) + ThrowException("Global const reference must be a pointer type!"); + + Value *V = getValNonImprovising(Ty, $2); + + // If this is an initializer for a constant pointer, which is referencing a + // (currently) undefined variable, create a stub now that shall be replaced + // in the future with the right type of variable. + // + if (V == 0) { + assert(isa(Ty) && "Globals may only be used as pointers!"); + const PointerType *PT = cast(Ty); + + // First check to see if the forward references value is already created! + PerModuleInfo::GlobalRefsType::iterator I = + CurModule.GlobalRefs.find(make_pair(PT, $2)); + + if (I != CurModule.GlobalRefs.end()) { + V = I->second; // Placeholder already exists, use it... + } else { + // TODO: Include line number info by creating a subclass of + // TODO: GlobalVariable here that includes the said information! + + // Create a placeholder for the global variable reference... + GlobalVariable *GV = new GlobalVariable(PT->getValueType(), false,true); + // Keep track of the fact that we have a forward ref to recycle it + CurModule.GlobalRefs.insert(make_pair(make_pair(PT, $2), GV)); + + // Must temporarily push this value into the module table... + CurModule.CurrentModule->getGlobalList().push_back(GV); + V = GV; + } + } + + GlobalValue *GV = cast(V); + $$ = ConstPoolPointerRef::get(GV); + delete $1; // Free the type handle } - | '{' TypeList '}' '{' ConstVector '}' { - StructType::ElementTypes Types($2->begin(), $2->end()); - delete $2; - const StructType *St = StructType::getStructType(Types); - $$ = new ConstPoolStruct(St, *$5); - delete $5; + +ConstVal : SIntType EINT64VAL { // integral constants + if (!ConstPoolSInt::isValueValidForType($1, $2)) + ThrowException("Constant value doesn't fit in type!"); + $$ = ConstPoolSInt::get($1, $2); + } + | UIntType EUINT64VAL { // integral constants + if (!ConstPoolUInt::isValueValidForType($1, $2)) + ThrowException("Constant value doesn't fit in type!"); + $$ = ConstPoolUInt::get($1, $2); + } + | BOOL TRUE { // Boolean constants + $$ = ConstPoolBool::True; } - | '{' '}' '{' '}' { - const StructType *St = - StructType::getStructType(StructType::ElementTypes()); - vector Empty; - $$ = new ConstPoolStruct(St, Empty); + | BOOL FALSE { // Boolean constants + $$ = ConstPoolBool::False; } -/* - | Types '*' ConstVal { - assert(0); - $$ = 0; + | FPType FPVAL { // Float & Double constants + $$ = ConstPoolFP::get($1, $2); } -*/ // ConstVector - A list of comma seperated constants. ConstVector : ConstVector ',' ConstVal { - ($$ = $1)->push_back(addConstValToConstantPool($3)); + ($$ = $1)->push_back($3); } | ConstVal { $$ = new vector(); - $$->push_back(addConstValToConstantPool($1)); + $$->push_back($1); } -//ExternMethodDecl : EXTERNAL TypesV '(' TypeList ')' { -// } -//ExternVarDecl : + +// GlobalType - Match either GLOBAL or CONSTANT for global declarations... +GlobalType : GLOBAL { $$ = false; } | CONSTANT { $$ = true; } + // ConstPool - Constants with optional names assigned to them. -ConstPool : ConstPool OptAssign ConstVal { - if ($2) { - $3->setName($2); - free($2); +ConstPool : ConstPool OptAssign CONST ConstVal { + if (setValueName($4, $2)) { assert(0 && "No redefinitions allowed!"); } + InsertValue($4); + } + | ConstPool OptAssign TYPE TypesV { // Types can be defined in the const pool + // Eagerly resolve types. This is not an optimization, this is a + // requirement that is due to the fact that we could have this: + // + // %list = type { %list * } + // %list = type { %list * } ; repeated type decl + // + // If types are not resolved eagerly, then the two types will not be + // determined to be the same type! + // + ResolveTypeTo($2, $4->get()); + + // TODO: FIXME when Type are not const + if (!setValueName(const_cast($4->get()), $2)) { + // If this is not a redefinition of a type... + if (!$2) { + InsertType($4->get(), + inMethodScope() ? CurMeth.Types : CurModule.Types); + } } - addConstValToConstantPool($3); + delete $4; } -/* - | ConstPool OptAssign GlobalDecl { // Global declarations appear in CP - if ($2) { - $3->setName($2); - free($2); + | ConstPool MethodProto { // Method prototypes can be in const pool + } + | ConstPool OptAssign OptInternal GlobalType ConstVal { + const Type *Ty = $5->getType(); + // Global declarations appear in Constant Pool + ConstPoolVal *Initializer = $5; + if (Initializer == 0) + ThrowException("Global value initializer is not a constant!"); + + GlobalVariable *GV = new GlobalVariable(Ty, $4, $3, Initializer); + if (!setValueName(GV, $2)) { // If not redefining... + CurModule.CurrentModule->getGlobalList().push_back(GV); + int Slot = InsertValue(GV, CurModule.Values); + + if (Slot != -1) { + CurModule.DeclareNewGlobalValue(GV, ValID::create(Slot)); + } else { + CurModule.DeclareNewGlobalValue(GV, ValID::create( + (char*)GV->getName().c_str())); + } + } + } + | ConstPool OptAssign OptInternal UNINIT GlobalType Types { + const Type *Ty = *$6; + // Global declarations appear in Constant Pool + GlobalVariable *GV = new GlobalVariable(Ty, $5, $3); + if (!setValueName(GV, $2)) { // If not redefining... + CurModule.CurrentModule->getGlobalList().push_back(GV); + int Slot = InsertValue(GV, CurModule.Values); + + if (Slot != -1) { + CurModule.DeclareNewGlobalValue(GV, ValID::create(Slot)); + } else { + assert(GV->hasName() && "Not named and not numbered!?"); + CurModule.DeclareNewGlobalValue(GV, ValID::create( + (char*)GV->getName().c_str())); + } } - //CurModule.CurrentModule-> } -*/ | /* empty: end of list */ { } @@ -682,12 +1131,11 @@ MethodList : MethodList Method { } | MethodList MethodProto { $$ = $1; - if (!$2->getParent()) - $1->getMethodList().push_back($2); - CurMeth.MethodDone(); } | ConstPool IMPLEMENTATION { $$ = CurModule.CurrentModule; + // Resolve circular types before we parse the body of the module + ResolveTypes(CurModule.LateResolveTypes); } @@ -698,11 +1146,8 @@ MethodList : MethodList Method { OptVAR_ID : VAR_ID | /*empty*/ { $$ = 0; } ArgVal : Types OptVAR_ID { - $$ = new MethodArgument($1); - if ($2) { // Was the argument named? - $$->setName($2); - free($2); // The string was strdup'd, so free it now. - } + $$ = new MethodArgument(*$1); delete $1; + if (setValueName($$, $2)) { assert(0 && "No arg redef allowed!"); } } ArgListH : ArgVal ',' ArgListH { @@ -713,6 +1158,10 @@ ArgListH : ArgVal ',' ArgListH { $$ = new list(); $$->push_front($1); } + | DOTDOTDOT { + $$ = new list(); + $$->push_front(new MethodArgument(Type::VoidTy)); + } ArgList : ArgListH { $$ = $1; @@ -721,49 +1170,60 @@ ArgList : ArgListH { $$ = 0; } -MethodHeaderH : TypesV STRINGCONSTANT '(' ArgList ')' { - MethodType::ParamTypes ParamTypeList; - if ($4) - for (list::iterator I = $4->begin(); I != $4->end(); ++I) +MethodHeaderH : OptInternal TypesV STRINGCONSTANT '(' ArgList ')' { + UnEscapeLexed($3); + string MethodName($3); + + vector ParamTypeList; + if ($5) + for (list::iterator I = $5->begin(); I != $5->end(); ++I) ParamTypeList.push_back((*I)->getType()); - const MethodType *MT = MethodType::getMethodType($1, ParamTypeList); + bool isVarArg = ParamTypeList.size() && ParamTypeList.back() == Type::VoidTy; + if (isVarArg) ParamTypeList.pop_back(); + + const MethodType *MT = MethodType::get(*$2, ParamTypeList, isVarArg); + const PointerType *PMT = PointerType::get(MT); + delete $2; Method *M = 0; if (SymbolTable *ST = CurModule.CurrentModule->getSymbolTable()) { - if (Value *V = ST->lookup(MT, $2)) { // Method already in symtab? - M = V->castMethodAsserting(); + if (Value *V = ST->lookup(PMT, MethodName)) { // Method already in symtab? + M = cast(V); // Yes it is. If this is the case, either we need to be a forward decl, // or it needs to be. if (!CurMeth.isDeclare && !M->isExternal()) - ThrowException("Redefinition of method '" + string($2) + "'!"); + ThrowException("Redefinition of method '" + MethodName + "'!"); } } if (M == 0) { // Not already defined? - M = new Method(MT, $2); + M = new Method(MT, $1, MethodName); InsertValue(M, CurModule.Values); + CurModule.DeclareNewGlobalValue(M, ValID::create($3)); } - - free($2); // Free strdup'd memory! + free($3); // Free strdup'd memory! CurMeth.MethodStart(M); // Add all of the arguments we parsed to the method... - if ($4 && !CurMeth.isDeclare) { // Is null if empty... + if ($5 && !CurMeth.isDeclare) { // Is null if empty... Method::ArgumentListType &ArgList = M->getArgumentList(); - for (list::iterator I = $4->begin(); I != $4->end(); ++I) { + for (list::iterator I = $5->begin(); I != $5->end(); ++I) { InsertValue(*I); ArgList.push_back(*I); } - delete $4; // We're now done with the argument list + delete $5; // We're now done with the argument list } } MethodHeader : MethodHeaderH ConstPool BEGINTOK { $$ = CurMeth.CurrentMethod; + + // Resolve circular types before we parse the body of the method. + ResolveTypes(CurMeth.LateResolveTypes); } Method : BasicBlockList END { @@ -772,6 +1232,9 @@ Method : BasicBlockList END { MethodProto : DECLARE { CurMeth.isDeclare = true; } MethodHeaderH { $$ = CurMeth.CurrentMethod; + if (!$$->getParent()) + CurModule.CurrentModule->getMethodList().push_back($$); + CurMeth.MethodDone(); } //===----------------------------------------------------------------------===// @@ -793,91 +1256,63 @@ ConstValueRef : ESINT64VAL { // A reference to a direct constant | FALSE { $$ = ValID::create((int64_t)0); } + | NULL_TOK { + $$ = ValID::createNull(); + } + +/* | STRINGCONSTANT { // Quoted strings work too... especially for methods $$ = ValID::create_conststr($1); } +*/ -// ValueRef - A reference to a definition... -ValueRef : INTVAL { // Is it an integer reference...? +// SymbolicValueRef - Reference to one of two ways of symbolically refering to +// another value. +// +SymbolicValueRef : INTVAL { // Is it an integer reference...? $$ = ValID::create($1); } | VAR_ID { // Is it a named reference...? $$ = ValID::create($1); } - | ConstValueRef { - $$ = $1; - } -// The user may refer to a user defined type by its typeplane... check for this -// now... -// -Types : ValueRef { - Value *D = getVal(Type::TypeTy, $1, true); - if (D == 0) ThrowException("Invalid user defined type: " + $1.getName()); +// ValueRef - A reference to a definition... either constant or symbolic +ValueRef : SymbolicValueRef | ConstValueRef - // User defined type not in const pool! - ConstPoolType *CPT = (ConstPoolType*)D->castConstantAsserting(); - $$ = CPT->getValue(); - } - | TypesV '(' TypeList ')' { // Method derived type? - MethodType::ParamTypes Params($3->begin(), $3->end()); - delete $3; - $$ = checkNewType(MethodType::getMethodType($1, Params)); - } - | TypesV '(' ')' { // Method derived type? - MethodType::ParamTypes Params; // Empty list - $$ = checkNewType(MethodType::getMethodType($1, Params)); - } - | '[' Types ']' { - $$ = checkNewType(ArrayType::getArrayType($2)); - } - | '[' EUINT64VAL 'x' Types ']' { - $$ = checkNewType(ArrayType::getArrayType($4, (int)$2)); - } - | '{' TypeList '}' { - StructType::ElementTypes Elements($2->begin(), $2->end()); - delete $2; - $$ = checkNewType(StructType::getStructType(Elements)); - } - | '{' '}' { - $$ = checkNewType(StructType::getStructType(StructType::ElementTypes())); - } - | Types '*' { - $$ = checkNewType(PointerType::getPointerType($1)); - } - -TypeList : Types { - $$ = new list(); - $$->push_back($1); - } - | TypeList ',' Types { - ($$=$1)->push_back($3); +// ResolvedVal - a pair. This is used only in cases where the +// type immediately preceeds the value reference, and allows complex constant +// pool references (for things like: 'ret [2 x int] [ int 12, int 42]') +ResolvedVal : Types ValueRef { + $$ = getVal(*$1, $2); delete $1; } BasicBlockList : BasicBlockList BasicBlock { - $1->getBasicBlocks().push_back($2); - $$ = $1; + ($$ = $1)->getBasicBlocks().push_back($2); } | MethodHeader BasicBlock { // Do not allow methods with 0 basic blocks - $$ = $1; // in them... - $1->getBasicBlocks().push_back($2); + ($$ = $1)->getBasicBlocks().push_back($2); } // Basic blocks are terminated by branching instructions: // br, br/cc, switch, ret // -BasicBlock : InstructionList BBTerminatorInst { - $1->getInstList().push_back($2); +BasicBlock : InstructionList OptAssign BBTerminatorInst { + if (setValueName($3, $2)) { assert(0 && "No redefn allowed!"); } + InsertValue($3); + + $1->getInstList().push_back($3); InsertValue($1); $$ = $1; } - | LABELSTR InstructionList BBTerminatorInst { - $2->getInstList().push_back($3); - $2->setName($1); - free($1); // Free the strdup'd memory... + | LABELSTR InstructionList OptAssign BBTerminatorInst { + if (setValueName($4, $3)) { assert(0 && "No redefn allowed!"); } + InsertValue($4); + + $2->getInstList().push_back($4); + if (setValueName($2, $1)) { assert(0 && "No label redef allowed!"); } InsertValue($2); $$ = $2; @@ -891,23 +1326,23 @@ InstructionList : InstructionList Inst { $$ = new BasicBlock(); } -BBTerminatorInst : RET Types ValueRef { // Return with a result... - $$ = new ReturnInst(getVal($2, $3)); +BBTerminatorInst : RET ResolvedVal { // Return with a result... + $$ = new ReturnInst($2); } | RET VOID { // Return with no result... $$ = new ReturnInst(); } | BR LABEL ValueRef { // Unconditional Branch... - $$ = new BranchInst((BasicBlock*)getVal(Type::LabelTy, $3)); + $$ = new BranchInst(cast(getVal(Type::LabelTy, $3))); } // Conditional Branch... | BR BOOL ValueRef ',' LABEL ValueRef ',' LABEL ValueRef { - $$ = new BranchInst((BasicBlock*)getVal(Type::LabelTy, $6), - (BasicBlock*)getVal(Type::LabelTy, $9), + $$ = new BranchInst(cast(getVal(Type::LabelTy, $6)), + cast(getVal(Type::LabelTy, $9)), getVal(Type::BoolTy, $3)); } | SWITCH IntType ValueRef ',' LABEL ValueRef '[' JumpTable ']' { SwitchInst *S = new SwitchInst(getVal($2, $3), - (BasicBlock*)getVal(Type::LabelTy, $6)); + cast(getVal(Type::LabelTy, $6))); $$ = S; list >::iterator I = $8->begin(), @@ -915,73 +1350,131 @@ BBTerminatorInst : RET Types ValueRef { // Return with a result... for (; I != end; ++I) S->dest_push_back(I->first, I->second); } + | INVOKE TypesV ValueRef '(' ValueRefListE ')' TO ResolvedVal + EXCEPT ResolvedVal { + const PointerType *PMTy; + const MethodType *Ty; + + if (!(PMTy = dyn_cast($2->get())) || + !(Ty = dyn_cast(PMTy->getValueType()))) { + // Pull out the types of all of the arguments... + vector ParamTypes; + if ($5) { + for (vector::iterator I = $5->begin(), E = $5->end(); I!=E; ++I) + ParamTypes.push_back((*I)->getType()); + } + + bool isVarArg = ParamTypes.size() && ParamTypes.back() == Type::VoidTy; + if (isVarArg) ParamTypes.pop_back(); + + Ty = MethodType::get($2->get(), ParamTypes, isVarArg); + PMTy = PointerType::get(Ty); + } + delete $2; + + Value *V = getVal(PMTy, $3); // Get the method we're calling... + + BasicBlock *Normal = dyn_cast($8); + BasicBlock *Except = dyn_cast($10); + + if (Normal == 0 || Except == 0) + ThrowException("Invoke instruction without label destinations!"); + + // Create the call node... + if (!$5) { // Has no arguments? + $$ = new InvokeInst(V, Normal, Except, vector()); + } else { // Has arguments? + // Loop through MethodType's arguments and ensure they are specified + // correctly! + // + MethodType::ParamTypes::const_iterator I = Ty->getParamTypes().begin(); + MethodType::ParamTypes::const_iterator E = Ty->getParamTypes().end(); + vector::iterator ArgI = $5->begin(), ArgE = $5->end(); + + for (; ArgI != ArgE && I != E; ++ArgI, ++I) + if ((*ArgI)->getType() != *I) + ThrowException("Parameter " +(*ArgI)->getName()+ " is not of type '" + + (*I)->getName() + "'!"); + + if (I != E || (ArgI != ArgE && !Ty->isVarArg())) + ThrowException("Invalid number of parameters detected!"); + + $$ = new InvokeInst(V, Normal, Except, *$5); + } + delete $5; + } + + JumpTable : JumpTable IntType ConstValueRef ',' LABEL ValueRef { $$ = $1; - ConstPoolVal *V = (ConstPoolVal*)getVal($2, $3, true); + ConstPoolVal *V = cast(getValNonImprovising($2, $3)); if (V == 0) ThrowException("May only switch on a constant pool value!"); - $$->push_back(make_pair(V, (BasicBlock*)getVal($5, $6))); + $$->push_back(make_pair(V, cast(getVal($5, $6)))); } | IntType ConstValueRef ',' LABEL ValueRef { $$ = new list >(); - ConstPoolVal *V = (ConstPoolVal*)getVal($1, $2, true); + ConstPoolVal *V = cast(getValNonImprovising($1, $2)); if (V == 0) ThrowException("May only switch on a constant pool value!"); - $$->push_back(make_pair(V, (BasicBlock*)getVal($4, $5))); + $$->push_back(make_pair(V, cast(getVal($4, $5)))); } Inst : OptAssign InstVal { - if ($1) // Is this definition named?? - $2->setName($1); // if so, assign the name... - + // Is this definition named?? if so, assign the name... + if (setValueName($2, $1)) { assert(0 && "No redefin allowed!"); } InsertValue($2); $$ = $2; } PHIList : Types '[' ValueRef ',' ValueRef ']' { // Used for PHI nodes $$ = new list >(); - $$->push_back(make_pair(getVal($1, $3), - (BasicBlock*)getVal(Type::LabelTy, $5))); + $$->push_back(make_pair(getVal(*$1, $3), + cast(getVal(Type::LabelTy, $5)))); + delete $1; } | PHIList ',' '[' ValueRef ',' ValueRef ']' { $$ = $1; $1->push_back(make_pair(getVal($1->front().first->getType(), $4), - (BasicBlock*)getVal(Type::LabelTy, $6))); + cast(getVal(Type::LabelTy, $6)))); } -ValueRefList : Types ValueRef { // Used for call statements... - $$ = new list(); - $$->push_back(getVal($1, $2)); +ValueRefList : ResolvedVal { // Used for call statements, and memory insts... + $$ = new vector(); + $$->push_back($1); } - | ValueRefList ',' Types ValueRef { + | ValueRefList ',' ResolvedVal { $$ = $1; - $1->push_back(getVal($3, $4)); + $1->push_back($3); } // ValueRefListE - Just like ValueRefList, except that it may also be empty! ValueRefListE : ValueRefList | /*empty*/ { $$ = 0; } InstVal : BinaryOps Types ValueRef ',' ValueRef { - $$ = BinaryOperator::create($1, getVal($2, $3), getVal($2, $5)); + $$ = BinaryOperator::create($1, getVal(*$2, $3), getVal(*$2, $5)); if ($$ == 0) ThrowException("binary operator returned null!"); + delete $2; } - | UnaryOps Types ValueRef { - $$ = UnaryOperator::create($1, getVal($2, $3)); + | UnaryOps ResolvedVal { + $$ = UnaryOperator::create($1, $2); if ($$ == 0) ThrowException("unary operator returned null!"); } - | ShiftOps Types ValueRef ',' Types ValueRef { - if ($5 != Type::UByteTy) ThrowException("Shift amount must be ubyte!"); - $$ = new ShiftInst($1, getVal($2, $3), getVal($5, $6)); + | ShiftOps ResolvedVal ',' ResolvedVal { + if ($4->getType() != Type::UByteTy) + ThrowException("Shift amount must be ubyte!"); + $$ = new ShiftInst($1, $2, $4); } - | CAST Types ValueRef TO Types { - $$ = new CastInst(getVal($2, $3), $5); + | CAST ResolvedVal TO Types { + $$ = new CastInst($2, *$4); + delete $4; } | PHI PHIList { const Type *Ty = $2->front().first->getType(); @@ -989,115 +1482,131 @@ InstVal : BinaryOps Types ValueRef ',' ValueRef { while ($2->begin() != $2->end()) { if ($2->front().first->getType() != Ty) ThrowException("All elements of a PHI node must be of the same type!"); - ((PHINode*)$$)->addIncoming($2->front().first, $2->front().second); + cast($$)->addIncoming($2->front().first, $2->front().second); $2->pop_front(); } delete $2; // Free the list... } - | CALL Types ValueRef '(' ValueRefListE ')' { - if (!$2->isMethodType()) - ThrowException("Can only call methods: invalid type '" + - $2->getName() + "'!"); - - const MethodType *Ty = (const MethodType*)$2; + | CALL TypesV ValueRef '(' ValueRefListE ')' { + const PointerType *PMTy; + const MethodType *Ty; + + if (!(PMTy = dyn_cast($2->get())) || + !(Ty = dyn_cast(PMTy->getValueType()))) { + // Pull out the types of all of the arguments... + vector ParamTypes; + if ($5) { + for (vector::iterator I = $5->begin(), E = $5->end(); I!=E; ++I) + ParamTypes.push_back((*I)->getType()); + } - Value *V = getVal(Ty, $3); - if (!V->isMethod() || V->getType() != Ty) - ThrowException("Cannot call: " + $3.getName() + "!"); + bool isVarArg = ParamTypes.size() && ParamTypes.back() == Type::VoidTy; + if (isVarArg) ParamTypes.pop_back(); - // Create or access a new type that corresponds to the function call... - vector Params; + Ty = MethodType::get($2->get(), ParamTypes, isVarArg); + PMTy = PointerType::get(Ty); + } + delete $2; - if ($5) { - // Pull out just the arguments... - Params.insert(Params.begin(), $5->begin(), $5->end()); - delete $5; + Value *V = getVal(PMTy, $3); // Get the method we're calling... + // Create the call node... + if (!$5) { // Has no arguments? + $$ = new CallInst(V, vector()); + } else { // Has arguments? // Loop through MethodType's arguments and ensure they are specified // correctly! // MethodType::ParamTypes::const_iterator I = Ty->getParamTypes().begin(); - unsigned i; - for (i = 0; i < Params.size() && I != Ty->getParamTypes().end(); ++i,++I){ - if (Params[i]->getType() != *I) - ThrowException("Parameter " + utostr(i) + " is not of type '" + + MethodType::ParamTypes::const_iterator E = Ty->getParamTypes().end(); + vector::iterator ArgI = $5->begin(), ArgE = $5->end(); + + for (; ArgI != ArgE && I != E; ++ArgI, ++I) + if ((*ArgI)->getType() != *I) + ThrowException("Parameter " +(*ArgI)->getName()+ " is not of type '" + (*I)->getName() + "'!"); - } - if (i != Params.size() || I != Ty->getParamTypes().end()) + if (I != E || (ArgI != ArgE && !Ty->isVarArg())) ThrowException("Invalid number of parameters detected!"); - } - // Create the call node... - $$ = new CallInst((Method*)V, Params); + $$ = new CallInst(V, *$5); + } + delete $5; } | MemoryInst { $$ = $1; } -// UByteList - List of ubyte values for load and store instructions -UByteList : ',' ConstVector { + +// IndexList - List of indices for GEP based instructions... +IndexList : ',' ValueRefList { $$ = $2; } | /* empty */ { - $$ = new vector(); + $$ = new vector(); } MemoryInst : MALLOC Types { - $$ = new MallocInst(checkNewType(PointerType::getPointerType($2))); + $$ = new MallocInst(PointerType::get(*$2)); + delete $2; } | MALLOC Types ',' UINT ValueRef { - if (!$2->isArrayType() || ((const ArrayType*)$2)->isSized()) - ThrowException("Trying to allocate " + $2->getName() + + if (!(*$2)->isArrayType() || cast($2->get())->isSized()) + ThrowException("Trying to allocate " + (*$2)->getName() + " as unsized array!"); - const Type *Ty = checkNewType(PointerType::getPointerType($2)); + const Type *Ty = PointerType::get(*$2); $$ = new MallocInst(Ty, getVal($4, $5)); + delete $2; } | ALLOCA Types { - $$ = new AllocaInst(checkNewType(PointerType::getPointerType($2))); + $$ = new AllocaInst(PointerType::get(*$2)); + delete $2; } | ALLOCA Types ',' UINT ValueRef { - if (!$2->isArrayType() || ((const ArrayType*)$2)->isSized()) - ThrowException("Trying to allocate " + $2->getName() + + if (!(*$2)->isArrayType() || cast($2->get())->isSized()) + ThrowException("Trying to allocate " + (*$2)->getName() + " as unsized array!"); - const Type *Ty = checkNewType(PointerType::getPointerType($2)); + const Type *Ty = PointerType::get(*$2); Value *ArrSize = getVal($4, $5); $$ = new AllocaInst(Ty, ArrSize); + delete $2; } - | FREE Types ValueRef { - if (!$2->isPointerType()) - ThrowException("Trying to free nonpointer type " + $2->getName() + "!"); - $$ = new FreeInst(getVal($2, $3)); + | FREE ResolvedVal { + if (!$2->getType()->isPointerType()) + ThrowException("Trying to free nonpointer type " + + $2->getType()->getName() + "!"); + $$ = new FreeInst($2); } - | LOAD Types ValueRef UByteList { - if (!$2->isPointerType()) - ThrowException("Can't load from nonpointer type: " + $2->getName()); - if (LoadInst::getIndexedType($2, *$4) == 0) + | LOAD Types ValueRef IndexList { + if (!(*$2)->isPointerType()) + ThrowException("Can't load from nonpointer type: " + + (*$2)->getDescription()); + if (LoadInst::getIndexedType(*$2, *$4) == 0) ThrowException("Invalid indices for load instruction!"); - $$ = new LoadInst(getVal($2, $3), *$4); + $$ = new LoadInst(getVal(*$2, $3), *$4); delete $4; // Free the vector... + delete $2; } - | STORE Types ValueRef ',' Types ValueRef UByteList { - if (!$5->isPointerType()) - ThrowException("Can't store to a nonpointer type: " + $5->getName()); - const Type *ElTy = StoreInst::getIndexedType($5, *$7); + | STORE ResolvedVal ',' Types ValueRef IndexList { + if (!(*$4)->isPointerType()) + ThrowException("Can't store to a nonpointer type: " + (*$4)->getName()); + const Type *ElTy = StoreInst::getIndexedType(*$4, *$6); if (ElTy == 0) ThrowException("Can't store into that field list!"); - if (ElTy != $2) - ThrowException("Can't store '" + $2->getName() + "' into space of type '"+ - ElTy->getName() + "'!"); - $$ = new StoreInst(getVal($2, $3), getVal($5, $6), *$7); - delete $7; - } - | GETELEMENTPTR Types ValueRef UByteList { - if (!$2->isPointerType()) + if (ElTy != $2->getType()) + ThrowException("Can't store '" + $2->getType()->getName() + + "' into space of type '" + ElTy->getName() + "'!"); + $$ = new StoreInst($2, getVal(*$4, $5), *$6); + delete $4; delete $6; + } + | GETELEMENTPTR Types ValueRef IndexList { + if (!(*$2)->isPointerType()) ThrowException("getelementptr insn requires pointer operand!"); - if (!GetElementPtrInst::getIndexedType($2, *$4, true)) - ThrowException("Can't get element ptr '" + $2->getName() + "'!"); - $$ = new GetElementPtrInst(getVal($2, $3), *$4); - delete $4; - checkNewType($$->getType()); + if (!GetElementPtrInst::getIndexedType(*$2, *$4, true)) + ThrowException("Can't get element ptr '" + (*$2)->getName() + "'!"); + $$ = new GetElementPtrInst(getVal(*$2, $3), *$4); + delete $2; delete $4; } %%