X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=utils%2FTableGen%2FIntrinsicEmitter.cpp;h=9c024a4981aff6a5f9cd7463acdcf386ce4ce299;hp=79874b1629b2292778db3ebf6025ea7eb2f6df18;hb=908a831a9a1fb043bc4758d6712d78255099ae51;hpb=61fc4cf7aa0b87ceab62082cee8ef5ce3f574ffc diff --git a/utils/TableGen/IntrinsicEmitter.cpp b/utils/TableGen/IntrinsicEmitter.cpp index 79874b1629b..9c024a4981a 100644 --- a/utils/TableGen/IntrinsicEmitter.cpp +++ b/utils/TableGen/IntrinsicEmitter.cpp @@ -13,7 +13,9 @@ #include "CodeGenTarget.h" #include "IntrinsicEmitter.h" -#include "Record.h" +#include "SequenceToOffsetTable.h" +#include "llvm/TableGen/Record.h" +#include "llvm/TableGen/StringMatcher.h" #include "llvm/ADT/StringExtras.h" #include using namespace llvm; @@ -30,6 +32,8 @@ void IntrinsicEmitter::run(raw_ostream &OS) { if (TargetOnly && !Ints.empty()) TargetPrefix = Ints[0].TargetPrefix; + EmitPrefix(OS); + // Emit the enum information. EmitEnumInfo(Ints, OS); @@ -54,11 +58,28 @@ void IntrinsicEmitter::run(raw_ostream &OS) { // Emit intrinsic alias analysis mod/ref behavior. EmitModRefBehavior(Ints, OS); - // Emit a list of intrinsics with corresponding GCC builtins. - EmitGCCBuiltinList(Ints, OS); - // Emit code to translate GCC builtins into LLVM intrinsics. EmitIntrinsicToGCCBuiltinMap(Ints, OS); + + EmitSuffix(OS); +} + +void IntrinsicEmitter::EmitPrefix(raw_ostream &OS) { + OS << "// VisualStudio defines setjmp as _setjmp\n" + "#if defined(_MSC_VER) && defined(setjmp) && \\\n" + " !defined(setjmp_undefined_for_msvc)\n" + "# pragma push_macro(\"setjmp\")\n" + "# undef setjmp\n" + "# define setjmp_undefined_for_msvc\n" + "#endif\n\n"; +} + +void IntrinsicEmitter::EmitSuffix(raw_ostream &OS) { + OS << "#if defined(_MSC_VER) && defined(setjmp_undefined_for_msvc)\n" + "// let's return it to _setjmp state\n" + "# pragma pop_macro(\"setjmp\")\n" + "# undef setjmp_undefined_for_msvc\n" + "#endif\n\n"; } void IntrinsicEmitter::EmitEnumInfo(const std::vector &Ints, @@ -77,37 +98,48 @@ void IntrinsicEmitter::EmitEnumInfo(const std::vector &Ints, void IntrinsicEmitter:: EmitFnNameRecognizer(const std::vector &Ints, raw_ostream &OS) { - // Build a function name -> intrinsic name mapping. - std::map IntMapping; + // Build a 'first character of function name' -> intrinsic # mapping. + std::map > IntMapping; for (unsigned i = 0, e = Ints.size(); i != e; ++i) - IntMapping[Ints[i].Name] = i; - + IntMapping[Ints[i].Name[5]].push_back(i); + OS << "// Function name -> enum value recognizer code.\n"; OS << "#ifdef GET_FUNCTION_RECOGNIZER\n"; - OS << " switch (Name[5]) {\n"; - OS << " default:\n"; - // Emit the intrinsics in sorted order. - char LastChar = 0; - for (std::map::iterator I = IntMapping.begin(), + OS << " StringRef NameR(Name+6, Len-6); // Skip over 'llvm.'\n"; + OS << " switch (Name[5]) { // Dispatch on first letter.\n"; + OS << " default: break;\n"; + // Emit the intrinsic matching stuff by first letter. + for (std::map >::iterator I = IntMapping.begin(), E = IntMapping.end(); I != E; ++I) { - if (I->first[5] != LastChar) { - LastChar = I->first[5]; - OS << " break;\n"; - OS << " case '" << LastChar << "':\n"; + OS << " case '" << I->first << "':\n"; + std::vector &IntList = I->second; + + // Emit all the overloaded intrinsics first, build a table of the + // non-overloaded ones. + std::vector MatchTable; + + for (unsigned i = 0, e = IntList.size(); i != e; ++i) { + unsigned IntNo = IntList[i]; + std::string Result = "return " + TargetPrefix + "Intrinsic::" + + Ints[IntNo].EnumName + ";"; + + if (!Ints[IntNo].isOverloaded) { + MatchTable.push_back(std::make_pair(Ints[IntNo].Name.substr(6),Result)); + continue; + } + + // For overloaded intrinsics, only the prefix needs to match + std::string TheStr = Ints[IntNo].Name.substr(6); + TheStr += '.'; // Require "bswap." instead of bswap. + OS << " if (NameR.startswith(\"" << TheStr << "\")) " + << Result << '\n'; } - // For overloaded intrinsics, only the prefix needs to match - if (Ints[I->second].isOverloaded) - OS << " if (Len > " << I->first.size() - << " && !memcmp(Name, \"" << I->first << ".\", " - << (I->first.size() + 1) << ")) return " << TargetPrefix << "Intrinsic::" - << Ints[I->second].EnumName << ";\n"; - else - OS << " if (Len == " << I->first.size() - << " && !memcmp(Name, \"" << I->first << "\", " - << I->first.size() << ")) return " << TargetPrefix << "Intrinsic::" - << Ints[I->second].EnumName << ";\n"; + // Emit the matcher logic for the fixed length strings. + StringMatcher("NameR", MatchTable, OS).Emit(1); + OS << " break; // end of '" << I->first << "' case.\n"; } + OS << " }\n"; OS << "#endif\n\n"; } @@ -126,118 +158,23 @@ EmitIntrinsicToNameTable(const std::vector &Ints, void IntrinsicEmitter:: EmitIntrinsicToOverloadTable(const std::vector &Ints, raw_ostream &OS) { - OS << "// Intrinsic ID to overload table\n"; + OS << "// Intrinsic ID to overload bitset\n"; OS << "#ifdef GET_INTRINSIC_OVERLOAD_TABLE\n"; - OS << " // Note that entry #0 is the invalid intrinsic!\n"; + OS << "static const uint8_t OTable[] = {\n"; + OS << " 0"; for (unsigned i = 0, e = Ints.size(); i != e; ++i) { - OS << " "; + // Add one to the index so we emit a null bit for the invalid #0 intrinsic. + if ((i+1)%8 == 0) + OS << ",\n 0"; if (Ints[i].isOverloaded) - OS << "true"; - else - OS << "false"; - OS << ",\n"; + OS << " | (1<<" << (i+1)%8 << ')'; } + OS << "\n};\n\n"; + // OTable contains a true bit at the position if the intrinsic is overloaded. + OS << "return (OTable[id/8] & (1 << (id%8))) != 0;\n"; OS << "#endif\n\n"; } -static void EmitTypeForValueType(raw_ostream &OS, EVT::SimpleValueType VT) { - if (EVT(VT).isInteger()) { - unsigned BitWidth = EVT(VT).getSizeInBits(); - OS << "IntegerType::get(" << BitWidth << ")"; - } else if (VT == EVT::Other) { - // EVT::OtherVT is used to mean the empty struct type here. - OS << "StructType::get(Context)"; - } else if (VT == EVT::f32) { - OS << "Type::FloatTy"; - } else if (VT == EVT::f64) { - OS << "Type::DoubleTy"; - } else if (VT == EVT::f80) { - OS << "Type::X86_FP80Ty"; - } else if (VT == EVT::f128) { - OS << "Type::FP128Ty"; - } else if (VT == EVT::ppcf128) { - OS << "Type::PPC_FP128Ty"; - } else if (VT == EVT::isVoid) { - OS << "Type::VoidTy"; - } else if (VT == EVT::Metadata) { - OS << "Type::MetadataTy"; - } else { - assert(false && "Unsupported ValueType!"); - } -} - -static void EmitTypeGenerate(raw_ostream &OS, const Record *ArgType, - unsigned &ArgNo); - -static void EmitTypeGenerate(raw_ostream &OS, - const std::vector &ArgTypes, - unsigned &ArgNo) { - if (ArgTypes.size() == 1) { - EmitTypeGenerate(OS, ArgTypes.front(), ArgNo); - return; - } - - OS << "StructType::get(Context, "; - - for (std::vector::const_iterator - I = ArgTypes.begin(), E = ArgTypes.end(); I != E; ++I) { - EmitTypeGenerate(OS, *I, ArgNo); - OS << ", "; - } - - OS << " NULL)"; -} - -static void EmitTypeGenerate(raw_ostream &OS, const Record *ArgType, - unsigned &ArgNo) { - EVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT")); - - if (ArgType->isSubClassOf("LLVMMatchType")) { - unsigned Number = ArgType->getValueAsInt("Number"); - assert(Number < ArgNo && "Invalid matching number!"); - if (ArgType->isSubClassOf("LLVMExtendedElementVectorType")) - OS << "VectorType::getExtendedElementVectorType" - << "(dyn_cast(Tys[" << Number << "]))"; - else if (ArgType->isSubClassOf("LLVMTruncatedElementVectorType")) - OS << "VectorType::getTruncatedElementVectorType" - << "(dyn_cast(Tys[" << Number << "]))"; - else - OS << "Tys[" << Number << "]"; - } else if (VT == EVT::iAny || VT == EVT::fAny || VT == EVT::vAny) { - // NOTE: The ArgNo variable here is not the absolute argument number, it is - // the index of the "arbitrary" type in the Tys array passed to the - // Intrinsic::getDeclaration function. Consequently, we only want to - // increment it when we actually hit an overloaded type. Getting this wrong - // leads to very subtle bugs! - OS << "Tys[" << ArgNo++ << "]"; - } else if (EVT(VT).isVector()) { - EVT VVT = VT; - OS << "VectorType::get("; - EmitTypeForValueType(OS, VVT.getVectorElementType().getSimpleVT()); - OS << ", " << VVT.getVectorNumElements() << ")"; - } else if (VT == EVT::iPTR) { - OS << "PointerType::getUnqual("; - EmitTypeGenerate(OS, ArgType->getValueAsDef("ElTy"), ArgNo); - OS << ")"; - } else if (VT == EVT::iPTRAny) { - // Make sure the user has passed us an argument type to overload. If not, - // treat it as an ordinary (not overloaded) intrinsic. - OS << "(" << ArgNo << " < numTys) ? Tys[" << ArgNo - << "] : PointerType::getUnqual("; - EmitTypeGenerate(OS, ArgType->getValueAsDef("ElTy"), ArgNo); - OS << ")"; - ++ArgNo; - } else if (VT == EVT::isVoid) { - if (ArgNo == 0) - OS << "Type::VoidTy"; - else - // EVT::isVoid is used to mean varargs here. - OS << "..."; - } else { - EmitTypeForValueType(OS, VT); - } -} - /// RecordListComparator - Provide a deterministic comparator for lists of /// records. namespace { @@ -251,11 +188,11 @@ namespace { unsigned RHSSize = RHSVec->size(); unsigned LHSSize = LHSVec->size(); - do { + for (; i != LHSSize; ++i) { if (i == RHSSize) return false; // RHS is shorter than LHS. if ((*LHSVec)[i] != (*RHSVec)[i]) return (*LHSVec)[i]->getName() < (*RHSVec)[i]->getName(); - } while (++i != LHSSize); + } if (i != RHSSize) return true; @@ -281,7 +218,7 @@ void IntrinsicEmitter::EmitVerifier(const std::vector &Ints, OS << "// Verifier::visitIntrinsicFunctionCall code.\n"; OS << "#ifdef GET_INTRINSIC_VERIFIER\n"; OS << " switch (ID) {\n"; - OS << " default: assert(0 && \"Invalid intrinsic!\");\n"; + OS << " default: llvm_unreachable(\"Invalid intrinsic!\");\n"; // This checking can emit a lot of very common code. To reduce the amount of // code that we emit, batch up cases that have identical types. This avoids @@ -326,13 +263,13 @@ void IntrinsicEmitter::EmitVerifier(const std::vector &Ints, else OS << "~" << Number; } else { - EVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT")); + MVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT")); OS << getEnumName(VT); if (EVT(VT).isOverloaded()) OverloadedTypeIndices.push_back(j); - if (VT == EVT::isVoid && j != 0 && j != je - 1) + if (VT == MVT::isVoid && j != 0 && j != je - 1) throw "Var arg type not last argument"; } } @@ -354,13 +291,13 @@ void IntrinsicEmitter::EmitVerifier(const std::vector &Ints, else OS << "~" << Number; } else { - EVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT")); + MVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT")); OS << getEnumName(VT); if (EVT(VT).isOverloaded()) OverloadedTypeIndices.push_back(j + RetTys.size()); - if (VT == EVT::isVoid && j != 0 && j != je - 1) + if (VT == MVT::isVoid && j != 0 && j != je - 1) throw "Var arg type not last argument"; } } @@ -372,60 +309,295 @@ void IntrinsicEmitter::EmitVerifier(const std::vector &Ints, OS << "#endif\n\n"; } -void IntrinsicEmitter::EmitGenerator(const std::vector &Ints, - raw_ostream &OS) { - OS << "// Code for generating Intrinsic function declarations.\n"; - OS << "#ifdef GET_INTRINSIC_GENERATOR\n"; - OS << " switch (id) {\n"; - OS << " default: assert(0 && \"Invalid intrinsic!\");\n"; + +// NOTE: This must be kept in synch with the copy in lib/VMCore/Function.cpp! +enum IIT_Info { + // Common values should be encoded with 0-15. + IIT_Done = 0, + IIT_I1 = 1, + IIT_I8 = 2, + IIT_I16 = 3, + IIT_I32 = 4, + IIT_I64 = 5, + IIT_F32 = 6, + IIT_F64 = 7, + IIT_V2 = 8, + IIT_V4 = 9, + IIT_V8 = 10, + IIT_V16 = 11, + IIT_V32 = 12, + IIT_MMX = 13, + IIT_PTR = 14, + IIT_ARG = 15, - // Similar to GET_INTRINSIC_VERIFIER, batch up cases that have identical - // types. - typedef std::map, RecordListComparator> MapTy; - MapTy UniqueArgInfos; + // Values from 16+ are only encodable with the inefficient encoding. + IIT_METADATA = 16, + IIT_EMPTYSTRUCT = 17, + IIT_STRUCT2 = 18, + IIT_STRUCT3 = 19, + IIT_STRUCT4 = 20, + IIT_STRUCT5 = 21, + IIT_EXTEND_VEC_ARG = 22, + IIT_TRUNC_VEC_ARG = 23, + IIT_ANYPTR = 24 +}; + + +static void EncodeFixedValueType(MVT::SimpleValueType VT, + std::vector &Sig) { + if (EVT(VT).isInteger()) { + unsigned BitWidth = EVT(VT).getSizeInBits(); + switch (BitWidth) { + default: throw "unhandled integer type width in intrinsic!"; + case 1: return Sig.push_back(IIT_I1); + case 8: return Sig.push_back(IIT_I8); + case 16: return Sig.push_back(IIT_I16); + case 32: return Sig.push_back(IIT_I32); + case 64: return Sig.push_back(IIT_I64); + } + } - // Compute the unique argument type info. - for (unsigned i = 0, e = Ints.size(); i != e; ++i) - UniqueArgInfos[make_pair(Ints[i].IS.RetTypeDefs, - Ints[i].IS.ParamTypeDefs)].push_back(i); + switch (VT) { + default: throw "unhandled MVT in intrinsic!"; + case MVT::f32: return Sig.push_back(IIT_F32); + case MVT::f64: return Sig.push_back(IIT_F64); + case MVT::Metadata: return Sig.push_back(IIT_METADATA); + case MVT::x86mmx: return Sig.push_back(IIT_MMX); + // MVT::OtherVT is used to mean the empty struct type here. + case MVT::Other: return Sig.push_back(IIT_EMPTYSTRUCT); + } +} + +#ifdef _MSC_VER +#pragma optimize("",off) // MSVC 2010 optimizer can't deal with this function. +#endif - // Loop through the array, emitting one generator for each batch. - std::string IntrinsicStr = TargetPrefix + "Intrinsic::"; +static void EncodeFixedType(Record *R, std::vector &ArgCodes, + std::vector &Sig) { - for (MapTy::iterator I = UniqueArgInfos.begin(), - E = UniqueArgInfos.end(); I != E; ++I) { - for (unsigned i = 0, e = I->second.size(); i != e; ++i) - OS << " case " << IntrinsicStr << Ints[I->second[i]].EnumName - << ":\t\t// " << Ints[I->second[i]].Name << "\n"; + if (R->isSubClassOf("LLVMMatchType")) { + unsigned Number = R->getValueAsInt("Number"); + assert(Number < ArgCodes.size() && "Invalid matching number!"); + if (R->isSubClassOf("LLVMExtendedElementVectorType")) + Sig.push_back(IIT_EXTEND_VEC_ARG); + else if (R->isSubClassOf("LLVMTruncatedElementVectorType")) + Sig.push_back(IIT_TRUNC_VEC_ARG); + else + Sig.push_back(IIT_ARG); + return Sig.push_back((Number << 2) | ArgCodes[Number]); + } + + MVT::SimpleValueType VT = getValueType(R->getValueAsDef("VT")); + + unsigned Tmp = 0; + switch (VT) { + default: break; + case MVT::iPTRAny: ++Tmp; // FALL THROUGH. + case MVT::vAny: ++Tmp; // FALL THROUGH. + case MVT::fAny: ++Tmp; // FALL THROUGH. + case MVT::iAny: { + // If this is an "any" valuetype, then the type is the type of the next + // type in the list specified to getIntrinsic(). + Sig.push_back(IIT_ARG); - const RecPair &ArgTypes = I->first; - const std::vector &RetTys = ArgTypes.first; - const std::vector &ParamTys = ArgTypes.second; + // Figure out what arg # this is consuming, and remember what kind it was. + unsigned ArgNo = ArgCodes.size(); + ArgCodes.push_back(Tmp); + + // Encode what sort of argument it must be in the low 2 bits of the ArgNo. + return Sig.push_back((ArgNo << 2) | Tmp); + } + + case MVT::iPTR: { + unsigned AddrSpace = 0; + if (R->isSubClassOf("LLVMQualPointerType")) { + AddrSpace = R->getValueAsInt("AddrSpace"); + assert(AddrSpace < 256 && "Address space exceeds 255"); + } + if (AddrSpace) { + Sig.push_back(IIT_ANYPTR); + Sig.push_back(AddrSpace); + } else { + Sig.push_back(IIT_PTR); + } + return EncodeFixedType(R->getValueAsDef("ElTy"), ArgCodes, Sig); + } + } + + if (EVT(VT).isVector()) { + EVT VVT = VT; + switch (VVT.getVectorNumElements()) { + default: throw "unhandled vector type width in intrinsic!"; + case 2: Sig.push_back(IIT_V2); break; + case 4: Sig.push_back(IIT_V4); break; + case 8: Sig.push_back(IIT_V8); break; + case 16: Sig.push_back(IIT_V16); break; + case 32: Sig.push_back(IIT_V32); break; + } + + return EncodeFixedValueType(VVT.getVectorElementType(). + getSimpleVT().SimpleTy, Sig); + } + + EncodeFixedValueType(VT, Sig); +} - unsigned N = ParamTys.size(); +#ifdef _MSC_VER +#pragma optimize("",on) +#endif + +/// ComputeFixedEncoding - If we can encode the type signature for this +/// intrinsic into 32 bits, return it. If not, return ~0U. +static void ComputeFixedEncoding(const CodeGenIntrinsic &Int, + std::vector &TypeSig) { + std::vector ArgCodes; + + if (Int.IS.RetVTs.empty()) + TypeSig.push_back(IIT_Done); + else if (Int.IS.RetVTs.size() == 1 && + Int.IS.RetVTs[0] == MVT::isVoid) + TypeSig.push_back(IIT_Done); + else { + switch (Int.IS.RetVTs.size()) { + case 1: break; + case 2: TypeSig.push_back(IIT_STRUCT2); break; + case 3: TypeSig.push_back(IIT_STRUCT3); break; + case 4: TypeSig.push_back(IIT_STRUCT4); break; + case 5: TypeSig.push_back(IIT_STRUCT5); break; + default: assert(0 && "Unhandled case in struct"); + } + + for (unsigned i = 0, e = Int.IS.RetVTs.size(); i != e; ++i) + EncodeFixedType(Int.IS.RetTypeDefs[i], ArgCodes, TypeSig); + } + + for (unsigned i = 0, e = Int.IS.ParamTypeDefs.size(); i != e; ++i) + EncodeFixedType(Int.IS.ParamTypeDefs[i], ArgCodes, TypeSig); +} + +void printIITEntry(raw_ostream &OS, unsigned char X) { + OS << (unsigned)X; +} - if (N > 1 && - getValueType(ParamTys[N - 1]->getValueAsDef("VT")) == EVT::isVoid) { - OS << " IsVarArg = true;\n"; - --N; +void IntrinsicEmitter::EmitGenerator(const std::vector &Ints, + raw_ostream &OS) { + // If we can compute a 32-bit fixed encoding for this intrinsic, do so and + // capture it in this vector, otherwise store a ~0U. + std::vector FixedEncodings; + + SequenceToOffsetTable > LongEncodingTable; + + std::vector TypeSig; + + // Compute the unique argument type info. + for (unsigned i = 0, e = Ints.size(); i != e; ++i) { + // Get the signature for the intrinsic. + TypeSig.clear(); + ComputeFixedEncoding(Ints[i], TypeSig); + + // Check to see if we can encode it into a 32-bit word. We can only encode + // 8 nibbles into a 32-bit word. + if (TypeSig.size() <= 8) { + bool Failed = false; + unsigned Result = 0; + for (unsigned i = 0, e = TypeSig.size(); i != e; ++i) { + // If we had an unencodable argument, bail out. + if (TypeSig[i] > 15) { + Failed = true; + break; + } + Result = (Result << 4) | TypeSig[e-i-1]; + } + + // If this could be encoded into a 31-bit word, return it. + if (!Failed && (Result >> 31) == 0) { + FixedEncodings.push_back(Result); + continue; + } } - unsigned ArgNo = 0; - OS << " ResultTy = "; - EmitTypeGenerate(OS, RetTys, ArgNo); - OS << ";\n"; + // Otherwise, we're going to unique the sequence into the + // LongEncodingTable, and use its offset in the 32-bit table instead. + LongEncodingTable.add(TypeSig); + + // This is a placehold that we'll replace after the table is laid out. + FixedEncodings.push_back(~0U); + } + + LongEncodingTable.layout(); + + OS << "// Global intrinsic function declaration type table.\n"; + OS << "#ifdef GET_INTRINSIC_GENERATOR_GLOBAL\n"; + + OS << "static const unsigned IIT_Table[] = {\n "; + + for (unsigned i = 0, e = FixedEncodings.size(); i != e; ++i) { + if ((i & 7) == 7) + OS << "\n "; - for (unsigned j = 0; j != N; ++j) { - OS << " ArgTys.push_back("; - EmitTypeGenerate(OS, ParamTys[j], ArgNo); - OS << ");\n"; + // If the entry fit in the table, just emit it. + if (FixedEncodings[i] != ~0U) { + OS << "0x" << utohexstr(FixedEncodings[i]) << ", "; + continue; } + + TypeSig.clear(); + ComputeFixedEncoding(Ints[i], TypeSig); - OS << " break;\n"; + + // Otherwise, emit the offset into the long encoding table. We emit it this + // way so that it is easier to read the offset in the .def file. + OS << "(1U<<31) | " << LongEncodingTable.get(TypeSig) << ", "; + } + + OS << "0\n};\n\n"; + + // Emit the shared table of register lists. + OS << "static const unsigned char IIT_LongEncodingTable[] = {\n"; + if (!LongEncodingTable.empty()) + LongEncodingTable.emit(OS, printIITEntry); + OS << " 255\n};\n\n"; + + OS << "#endif\n\n"; // End of GET_INTRINSIC_GENERATOR_GLOBAL +} + +namespace { + enum ModRefKind { + MRK_none, + MRK_readonly, + MRK_readnone + }; + + ModRefKind getModRefKind(const CodeGenIntrinsic &intrinsic) { + switch (intrinsic.ModRef) { + case CodeGenIntrinsic::NoMem: + return MRK_readnone; + case CodeGenIntrinsic::ReadArgMem: + case CodeGenIntrinsic::ReadMem: + return MRK_readonly; + case CodeGenIntrinsic::ReadWriteArgMem: + case CodeGenIntrinsic::ReadWriteMem: + return MRK_none; + } + llvm_unreachable("bad mod-ref kind"); } - OS << " }\n"; - OS << "#endif\n\n"; + struct AttributeComparator { + bool operator()(const CodeGenIntrinsic *L, const CodeGenIntrinsic *R) const { + // Sort throwing intrinsics after non-throwing intrinsics. + if (L->canThrow != R->canThrow) + return R->canThrow; + + // Try to order by readonly/readnone attribute. + ModRefKind LK = getModRefKind(*L); + ModRefKind RK = getModRefKind(*R); + if (LK != RK) return (LK > RK); + + // Order by argument attributes. + // This is reliable because each side is already sorted internally. + return (L->ArgumentAttributes < R->ArgumentAttributes); + } + }; } /// EmitAttributes - This emits the Intrinsic::getAttributes method. @@ -435,84 +607,110 @@ EmitAttributes(const std::vector &Ints, raw_ostream &OS) { OS << "#ifdef GET_INTRINSIC_ATTRIBUTES\n"; if (TargetOnly) OS << "static AttrListPtr getAttributes(" << TargetPrefix - << "Intrinsic::ID id) {"; + << "Intrinsic::ID id) {\n"; else - OS << "AttrListPtr Intrinsic::getAttributes(ID id) {"; - OS << " // No intrinsic can throw exceptions.\n"; - OS << " Attributes Attr = Attribute::NoUnwind;\n"; - OS << " switch (id) {\n"; - OS << " default: break;\n"; - unsigned MaxArgAttrs = 0; + OS << "AttrListPtr Intrinsic::getAttributes(ID id) {\n"; + + // Compute the maximum number of attribute arguments and the map + typedef std::map UniqAttrMapTy; + UniqAttrMapTy UniqAttributes; + unsigned maxArgAttrs = 0; + unsigned AttrNum = 0; for (unsigned i = 0, e = Ints.size(); i != e; ++i) { - MaxArgAttrs = - std::max(MaxArgAttrs, unsigned(Ints[i].ArgumentAttributes.size())); - switch (Ints[i].ModRef) { - default: break; - case CodeGenIntrinsic::NoMem: - OS << " case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName - << ":\n"; - break; - } + const CodeGenIntrinsic &intrinsic = Ints[i]; + maxArgAttrs = + std::max(maxArgAttrs, unsigned(intrinsic.ArgumentAttributes.size())); + unsigned &N = UniqAttributes[&intrinsic]; + if (N) continue; + assert(AttrNum < 256 && "Too many unique attributes for table!"); + N = ++AttrNum; } - OS << " Attr |= Attribute::ReadNone; // These do not access memory.\n"; - OS << " break;\n"; + + // Emit an array of AttributeWithIndex. Most intrinsics will have + // at least one entry, for the function itself (index ~1), which is + // usually nounwind. + OS << " static const uint8_t IntrinsicsToAttributesMap[] = {\n"; + for (unsigned i = 0, e = Ints.size(); i != e; ++i) { - switch (Ints[i].ModRef) { - default: break; - case CodeGenIntrinsic::ReadArgMem: - case CodeGenIntrinsic::ReadMem: - OS << " case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName - << ":\n"; - break; - } + const CodeGenIntrinsic &intrinsic = Ints[i]; + + OS << " " << UniqAttributes[&intrinsic] << ", // " + << intrinsic.Name << "\n"; } - OS << " Attr |= Attribute::ReadOnly; // These do not write memory.\n"; - OS << " break;\n"; - OS << " }\n"; - OS << " AttributeWithIndex AWI[" << MaxArgAttrs+1 << "];\n"; + OS << " };\n\n"; + + OS << " AttributeWithIndex AWI[" << maxArgAttrs+1 << "];\n"; OS << " unsigned NumAttrs = 0;\n"; - OS << " switch (id) {\n"; - OS << " default: break;\n"; - - // Add argument attributes for any intrinsics that have them. - for (unsigned i = 0, e = Ints.size(); i != e; ++i) { - if (Ints[i].ArgumentAttributes.empty()) continue; - - OS << " case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName - << ":\n"; + OS << " if (id != 0) {\n"; + OS << " switch(IntrinsicsToAttributesMap[id - "; + if (TargetOnly) + OS << "Intrinsic::num_intrinsics"; + else + OS << "1"; + OS << "]) {\n"; + OS << " default: llvm_unreachable(\"Invalid attribute number\");\n"; + for (UniqAttrMapTy::const_iterator I = UniqAttributes.begin(), + E = UniqAttributes.end(); I != E; ++I) { + OS << " case " << I->second << ":\n"; - std::vector > ArgAttrs = - Ints[i].ArgumentAttributes; - // Sort by argument index. - std::sort(ArgAttrs.begin(), ArgAttrs.end()); + const CodeGenIntrinsic &intrinsic = *(I->first); - unsigned NumArgsWithAttrs = 0; + // Keep track of the number of attributes we're writing out. + unsigned numAttrs = 0; - while (!ArgAttrs.empty()) { - unsigned ArgNo = ArgAttrs[0].first; - - OS << " AWI[" << NumArgsWithAttrs++ << "] = AttributeWithIndex::get(" - << ArgNo+1 << ", 0"; + // The argument attributes are alreadys sorted by argument index. + for (unsigned ai = 0, ae = intrinsic.ArgumentAttributes.size(); ai != ae;) { + unsigned argNo = intrinsic.ArgumentAttributes[ai].first; + + OS << " AWI[" << numAttrs++ << "] = AttributeWithIndex::get(" + << argNo+1 << ", "; - while (!ArgAttrs.empty() && ArgAttrs[0].first == ArgNo) { - switch (ArgAttrs[0].second) { - default: assert(0 && "Unknown arg attribute"); + bool moreThanOne = false; + + do { + if (moreThanOne) OS << '|'; + + switch (intrinsic.ArgumentAttributes[ai].second) { case CodeGenIntrinsic::NoCapture: - OS << "|Attribute::NoCapture"; + OS << "Attribute::NoCapture"; break; } - ArgAttrs.erase(ArgAttrs.begin()); + + ++ai; + moreThanOne = true; + } while (ai != ae && intrinsic.ArgumentAttributes[ai].first == argNo); + + OS << ");\n"; + } + + ModRefKind modRef = getModRefKind(intrinsic); + + if (!intrinsic.canThrow || modRef) { + OS << " AWI[" << numAttrs++ << "] = AttributeWithIndex::get(~0, "; + if (!intrinsic.canThrow) { + OS << "Attribute::NoUnwind"; + if (modRef) OS << '|'; + } + switch (modRef) { + case MRK_none: break; + case MRK_readonly: OS << "Attribute::ReadOnly"; break; + case MRK_readnone: OS << "Attribute::ReadNone"; break; } OS << ");\n"; } - - OS << " NumAttrs = " << NumArgsWithAttrs << ";\n"; - OS << " break;\n"; + + if (numAttrs) { + OS << " NumAttrs = " << numAttrs << ";\n"; + OS << " break;\n"; + } else { + OS << " return AttrListPtr();\n"; + } } + OS << " }\n"; OS << " }\n"; - OS << " AWI[NumAttrs] = AttributeWithIndex::get(~0, Attr);\n"; - OS << " return AttrListPtr::get(AWI, NumAttrs+1);\n"; + OS << " return AttrListPtr::get(AWI, NumAttrs);\n"; OS << "}\n"; OS << "#endif // GET_INTRINSIC_ATTRIBUTES\n\n"; } @@ -520,128 +718,36 @@ EmitAttributes(const std::vector &Ints, raw_ostream &OS) { /// EmitModRefBehavior - Determine intrinsic alias analysis mod/ref behavior. void IntrinsicEmitter:: EmitModRefBehavior(const std::vector &Ints, raw_ostream &OS){ - OS << "// Determine intrinsic alias analysis mod/ref behavior.\n"; - OS << "#ifdef GET_INTRINSIC_MODREF_BEHAVIOR\n"; - OS << "switch (id) {\n"; - OS << "default:\n return UnknownModRefBehavior;\n"; + OS << "// Determine intrinsic alias analysis mod/ref behavior.\n" + << "#ifdef GET_INTRINSIC_MODREF_BEHAVIOR\n" + << "assert(iid <= Intrinsic::" << Ints.back().EnumName << " && " + << "\"Unknown intrinsic.\");\n\n"; + + OS << "static const uint8_t IntrinsicModRefBehavior[] = {\n" + << " /* invalid */ UnknownModRefBehavior,\n"; for (unsigned i = 0, e = Ints.size(); i != e; ++i) { - if (Ints[i].ModRef == CodeGenIntrinsic::WriteMem) - continue; - OS << "case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName - << ":\n"; + OS << " /* " << TargetPrefix << Ints[i].EnumName << " */ "; switch (Ints[i].ModRef) { - default: - assert(false && "Unknown Mod/Ref type!"); case CodeGenIntrinsic::NoMem: - OS << " return DoesNotAccessMemory;\n"; + OS << "DoesNotAccessMemory,\n"; break; case CodeGenIntrinsic::ReadArgMem: + OS << "OnlyReadsArgumentPointees,\n"; + break; case CodeGenIntrinsic::ReadMem: - OS << " return OnlyReadsMemory;\n"; + OS << "OnlyReadsMemory,\n"; break; - case CodeGenIntrinsic::WriteArgMem: - OS << " return AccessesArguments;\n"; + case CodeGenIntrinsic::ReadWriteArgMem: + OS << "OnlyAccessesArgumentPointees,\n"; + break; + case CodeGenIntrinsic::ReadWriteMem: + OS << "UnknownModRefBehavior,\n"; break; } } - OS << "}\n"; - OS << "#endif // GET_INTRINSIC_MODREF_BEHAVIOR\n\n"; -} - -void IntrinsicEmitter:: -EmitGCCBuiltinList(const std::vector &Ints, raw_ostream &OS){ - OS << "// Get the GCC builtin that corresponds to an LLVM intrinsic.\n"; - OS << "#ifdef GET_GCC_BUILTIN_NAME\n"; - OS << " switch (F->getIntrinsicID()) {\n"; - OS << " default: BuiltinName = \"\"; break;\n"; - for (unsigned i = 0, e = Ints.size(); i != e; ++i) { - if (!Ints[i].GCCBuiltinName.empty()) { - OS << " case Intrinsic::" << Ints[i].EnumName << ": BuiltinName = \"" - << Ints[i].GCCBuiltinName << "\"; break;\n"; - } - } - OS << " }\n"; - OS << "#endif\n\n"; -} - -/// EmitBuiltinComparisons - Emit comparisons to determine whether the specified -/// sorted range of builtin names is equal to the current builtin. This breaks -/// it down into a simple tree. -/// -/// At this point, we know that all the builtins in the range have the same name -/// for the first 'CharStart' characters. Only the end of the name needs to be -/// discriminated. -typedef std::map::const_iterator StrMapIterator; -static void EmitBuiltinComparisons(StrMapIterator Start, StrMapIterator End, - unsigned CharStart, unsigned Indent, - std::string TargetPrefix, raw_ostream &OS) { - if (Start == End) return; // empty range. - - // Determine what, if anything, is the same about all these strings. - std::string CommonString = Start->first; - unsigned NumInRange = 0; - for (StrMapIterator I = Start; I != End; ++I, ++NumInRange) { - // Find the first character that doesn't match. - const std::string &ThisStr = I->first; - unsigned NonMatchChar = CharStart; - while (NonMatchChar < CommonString.size() && - NonMatchChar < ThisStr.size() && - CommonString[NonMatchChar] == ThisStr[NonMatchChar]) - ++NonMatchChar; - // Truncate off pieces that don't match. - CommonString.resize(NonMatchChar); - } - - // Just compare the rest of the string. - if (NumInRange == 1) { - if (CharStart != CommonString.size()) { - OS << std::string(Indent*2, ' ') << "if (!memcmp(BuiltinName"; - if (CharStart) OS << "+" << CharStart; - OS << ", \"" << (CommonString.c_str()+CharStart) << "\", "; - OS << CommonString.size() - CharStart << "))\n"; - ++Indent; - } - OS << std::string(Indent*2, ' ') << "IntrinsicID = " << TargetPrefix - << "Intrinsic::"; - OS << Start->second << ";\n"; - return; - } - - // At this point, we potentially have a common prefix for these builtins, emit - // a check for this common prefix. - if (CommonString.size() != CharStart) { - OS << std::string(Indent*2, ' ') << "if (!memcmp(BuiltinName"; - if (CharStart) OS << "+" << CharStart; - OS << ", \"" << (CommonString.c_str()+CharStart) << "\", "; - OS << CommonString.size()-CharStart << ")) {\n"; - - EmitBuiltinComparisons(Start, End, CommonString.size(), Indent+1, - TargetPrefix, OS); - OS << std::string(Indent*2, ' ') << "}\n"; - return; - } - - // Output a switch on the character that differs across the set. - OS << std::string(Indent*2, ' ') << "switch (BuiltinName[" << CharStart - << "]) {"; - if (CharStart) - OS << " // \"" << std::string(Start->first.begin(), - Start->first.begin()+CharStart) << "\""; - OS << "\n"; - - for (StrMapIterator I = Start; I != End; ) { - char ThisChar = I->first[CharStart]; - OS << std::string(Indent*2, ' ') << "case '" << ThisChar << "':\n"; - // Figure out the range that has this common character. - StrMapIterator NextChar = I; - for (++NextChar; NextChar != End && NextChar->first[CharStart] == ThisChar; - ++NextChar) - /*empty*/; - EmitBuiltinComparisons(I, NextChar, CharStart+1, Indent+1, TargetPrefix,OS); - OS << std::string(Indent*2, ' ') << " break;\n"; - I = NextChar; - } - OS << std::string(Indent*2, ' ') << "}\n"; + OS << "};\n\n" + << "return static_cast(IntrinsicModRefBehavior[iid]);\n" + << "#endif // GET_INTRINSIC_MODREF_BEHAVIOR\n\n"; } /// EmitTargetBuiltins - All of the builtins in the specified map are for the @@ -649,27 +755,17 @@ static void EmitBuiltinComparisons(StrMapIterator Start, StrMapIterator End, static void EmitTargetBuiltins(const std::map &BIM, const std::string &TargetPrefix, raw_ostream &OS) { - // Rearrange the builtins by length. - std::vector > BuiltinsByLen; - BuiltinsByLen.reserve(100); - - for (StrMapIterator I = BIM.begin(), E = BIM.end(); I != E; ++I) { - if (I->first.size() >= BuiltinsByLen.size()) - BuiltinsByLen.resize(I->first.size()+1); - BuiltinsByLen[I->first.size()].insert(*I); - } - // Now that we have all the builtins by their length, emit a switch stmt. - OS << " switch (strlen(BuiltinName)) {\n"; - OS << " default: break;\n"; - for (unsigned i = 0, e = BuiltinsByLen.size(); i != e; ++i) { - if (BuiltinsByLen[i].empty()) continue; - OS << " case " << i << ":\n"; - EmitBuiltinComparisons(BuiltinsByLen[i].begin(), BuiltinsByLen[i].end(), - 0, 3, TargetPrefix, OS); - OS << " break;\n"; + std::vector Results; + + for (std::map::const_iterator I = BIM.begin(), + E = BIM.end(); I != E; ++I) { + std::string ResultCode = + "return " + TargetPrefix + "Intrinsic::" + I->second + ";"; + Results.push_back(StringMatcher::StringPair(I->first, ResultCode)); } - OS << " }\n"; + + StringMatcher("BuiltinName", Results, OS).Emit(); } @@ -699,24 +795,20 @@ EmitIntrinsicToGCCBuiltinMap(const std::vector &Ints, if (TargetOnly) { OS << "static " << TargetPrefix << "Intrinsic::ID " << "getIntrinsicForGCCBuiltin(const char " - << "*TargetPrefix, const char *BuiltinName) {\n"; - OS << " " << TargetPrefix << "Intrinsic::ID IntrinsicID = "; + << "*TargetPrefixStr, const char *BuiltinNameStr) {\n"; } else { OS << "Intrinsic::ID Intrinsic::getIntrinsicForGCCBuiltin(const char " - << "*TargetPrefix, const char *BuiltinName) {\n"; - OS << " Intrinsic::ID IntrinsicID = "; + << "*TargetPrefixStr, const char *BuiltinNameStr) {\n"; } - if (TargetOnly) - OS << "(" << TargetPrefix<< "Intrinsic::ID)"; - - OS << "Intrinsic::not_intrinsic;\n"; + OS << " StringRef BuiltinName(BuiltinNameStr);\n"; + OS << " StringRef TargetPrefix(TargetPrefixStr);\n\n"; // Note: this could emit significantly better code if we cared. for (BIMTy::iterator I = BuiltinMap.begin(), E = BuiltinMap.end();I != E;++I){ OS << " "; if (!I->first.empty()) - OS << "if (!strcmp(TargetPrefix, \"" << I->first << "\")) "; + OS << "if (TargetPrefix == \"" << I->first << "\") "; else OS << "/* Target Independent Builtins */ "; OS << "{\n"; @@ -725,7 +817,10 @@ EmitIntrinsicToGCCBuiltinMap(const std::vector &Ints, EmitTargetBuiltins(I->second, TargetPrefix, OS); OS << " }\n"; } - OS << " return IntrinsicID;\n"; + OS << " return "; + if (!TargetPrefix.empty()) + OS << "(" << TargetPrefix << "Intrinsic::ID)"; + OS << "Intrinsic::not_intrinsic;\n"; OS << "}\n"; OS << "#endif\n\n"; }