utils/TableGen/IntrinsicEmitter.cpp

   1 //===- IntrinsicEmitter.cpp - Generate intrinsic information --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This tablegen backend emits information about intrinsic functions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "CodeGenTarget.h"
  15 #include "IntrinsicEmitter.h"
  16 #include "Record.h"
  17 #include "llvm/ADT/StringExtras.h"
  18 #include <algorithm>
  19 using namespace llvm;
  20
  21 //===----------------------------------------------------------------------===//
  22 // IntrinsicEmitter Implementation
  23 //===----------------------------------------------------------------------===//
  24
  25 void IntrinsicEmitter::run(std::ostream &OS) {
  26   EmitSourceFileHeader("Intrinsic Function Source Fragment", OS);
  27
  28   std::vector<CodeGenIntrinsic> Ints = LoadIntrinsics(Records, TargetOnly);
  29
  30   if (TargetOnly && !Ints.empty())
  31     TargetPrefix = Ints[0].TargetPrefix;
  32
  33   // Emit the enum information.
  34   EmitEnumInfo(Ints, OS);
  35
  36   // Emit the intrinsic ID -> name table.
  37   EmitIntrinsicToNameTable(Ints, OS);
  38
  39   // Emit the function name recognizer.
  40   EmitFnNameRecognizer(Ints, OS);
  41
  42   // Emit the intrinsic verifier.
  43   EmitVerifier(Ints, OS);
  44
  45   // Emit the intrinsic declaration generator.
  46   EmitGenerator(Ints, OS);
  47
  48   // Emit the intrinsic parameter attributes.
  49   EmitAttributes(Ints, OS);
  50
  51   // Emit intrinsic alias analysis mod/ref behavior.
  52   EmitModRefBehavior(Ints, OS);
  53
  54   // Emit a list of intrinsics with corresponding GCC builtins.
  55   EmitGCCBuiltinList(Ints, OS);
  56
  57   // Emit code to translate GCC builtins into LLVM intrinsics.
  58   EmitIntrinsicToGCCBuiltinMap(Ints, OS);
  59 }
  60
  61 void IntrinsicEmitter::EmitEnumInfo(const std::vector<CodeGenIntrinsic> &Ints,
  62                                     std::ostream &OS) {
  63   OS << "// Enum values for Intrinsics.h\n";
  64   OS << "#ifdef GET_INTRINSIC_ENUM_VALUES\n";
  65   for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
  66     OS << "    " << Ints[i].EnumName;
  67     OS << ((i != e-1) ? ", " : "  ");
  68     OS << std::string(40-Ints[i].EnumName.size(), ' ')
  69       << "// " << Ints[i].Name << "\n";
  70   }
  71   OS << "#endif\n\n";
  72 }
  73
  74 void IntrinsicEmitter::
  75 EmitFnNameRecognizer(const std::vector<CodeGenIntrinsic> &Ints,
  76                      std::ostream &OS) {
  77   // Build a function name -> intrinsic name mapping.
  78   std::map<std::string, unsigned> IntMapping;
  79   for (unsigned i = 0, e = Ints.size(); i != e; ++i)
  80     IntMapping[Ints[i].Name] = i;
  81
  82   OS << "// Function name -> enum value recognizer code.\n";
  83   OS << "#ifdef GET_FUNCTION_RECOGNIZER\n";
  84   OS << "  switch (Name[5]) {\n";
  85   OS << "  default:\n";
  86   // Emit the intrinsics in sorted order.
  87   char LastChar = 0;
  88   for (std::map<std::string, unsigned>::iterator I = IntMapping.begin(),
  89        E = IntMapping.end(); I != E; ++I) {
  90     if (I->first[5] != LastChar) {
  91       LastChar = I->first[5];
  92       OS << "    break;\n";
  93       OS << "  case '" << LastChar << "':\n";
  94     }
  95
  96     // For overloaded intrinsics, only the prefix needs to match
  97     if (Ints[I->second].isOverloaded)
  98       OS << "    if (Len > " << I->first.size()
  99        << " && !memcmp(Name, \"" << I->first << ".\", "
 100        << (I->first.size() + 1) << ")) return " << TargetPrefix << "Intrinsic::"
 101        << Ints[I->second].EnumName << ";\n";
 102     else
 103       OS << "    if (Len == " << I->first.size()
 104          << " && !memcmp(Name, \"" << I->first << "\", "
 105          << I->first.size() << ")) return " << TargetPrefix << "Intrinsic::"
 106          << Ints[I->second].EnumName << ";\n";
 107   }
 108   OS << "  }\n";
 109   OS << "#endif\n\n";
 110 }
 111
 112 void IntrinsicEmitter::
 113 EmitIntrinsicToNameTable(const std::vector<CodeGenIntrinsic> &Ints,
 114                          std::ostream &OS) {
 115   OS << "// Intrinsic ID to name table\n";
 116   OS << "#ifdef GET_INTRINSIC_NAME_TABLE\n";
 117   OS << "  // Note that entry #0 is the invalid intrinsic!\n";
 118   for (unsigned i = 0, e = Ints.size(); i != e; ++i)
 119     OS << "  \"" << Ints[i].Name << "\",\n";
 120   OS << "#endif\n\n";
 121 }
 122
 123 static void EmitTypeForValueType(std::ostream &OS, MVT::SimpleValueType VT) {
 124   if (MVT(VT).isInteger()) {
 125     unsigned BitWidth = MVT(VT).getSizeInBits();
 126     OS << "IntegerType::get(" << BitWidth << ")";
 127   } else if (VT == MVT::Other) {
 128     // MVT::OtherVT is used to mean the empty struct type here.
 129     OS << "StructType::get(std::vector<const Type *>())";
 130   } else if (VT == MVT::f32) {
 131     OS << "Type::FloatTy";
 132   } else if (VT == MVT::f64) {
 133     OS << "Type::DoubleTy";
 134   } else if (VT == MVT::f80) {
 135     OS << "Type::X86_FP80Ty";
 136   } else if (VT == MVT::f128) {
 137     OS << "Type::FP128Ty";
 138   } else if (VT == MVT::ppcf128) {
 139     OS << "Type::PPC_FP128Ty";
 140   } else if (VT == MVT::isVoid) {
 141     OS << "Type::VoidTy";
 142   } else {
 143     assert(false && "Unsupported ValueType!");
 144   }
 145 }
 146
 147 static void EmitTypeGenerate(std::ostream &OS, const Record *ArgType,
 148                              unsigned &ArgNo);
 149
 150 static void EmitTypeGenerate(std::ostream &OS,
 151                              const std::vector<Record*> &ArgTypes,
 152                              unsigned &ArgNo) {
 153   if (ArgTypes.size() == 1) {
 154     EmitTypeGenerate(OS, ArgTypes.front(), ArgNo);
 155     return;
 156   }
 157
 158   OS << "StructType::get(";
 159
 160   for (std::vector<Record*>::const_iterator
 161          I = ArgTypes.begin(), E = ArgTypes.end(); I != E; ++I) {
 162     EmitTypeGenerate(OS, *I, ArgNo);
 163     OS << ", ";
 164   }
 165
 166   OS << " NULL)";
 167 }
 168
 169 static void EmitTypeGenerate(std::ostream &OS, const Record *ArgType,
 170                              unsigned &ArgNo) {
 171   MVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT"));
 172
 173   if (ArgType->isSubClassOf("LLVMMatchType")) {
 174     unsigned Number = ArgType->getValueAsInt("Number");
 175     assert(Number < ArgNo && "Invalid matching number!");
 176     if (ArgType->isSubClassOf("LLVMExtendedElementVectorType"))
 177       OS << "VectorType::getExtendedElementVectorType"
 178          << "(dyn_cast<VectorType>(Tys[" << Number << "]))";
 179     else if (ArgType->isSubClassOf("LLVMTruncatedElementVectorType"))
 180       OS << "VectorType::getTruncatedElementVectorType"
 181          << "(dyn_cast<VectorType>(Tys[" << Number << "]))";
 182     else
 183       OS << "Tys[" << Number << "]";
 184   } else if (VT == MVT::iAny || VT == MVT::fAny) {
 185     // NOTE: The ArgNo variable here is not the absolute argument number, it is
 186     // the index of the "arbitrary" type in the Tys array passed to the
 187     // Intrinsic::getDeclaration function. Consequently, we only want to
 188     // increment it when we actually hit an overloaded type. Getting this wrong
 189     // leads to very subtle bugs!
 190     OS << "Tys[" << ArgNo++ << "]";
 191   } else if (MVT(VT).isVector()) {
 192     MVT VVT = VT;
 193     OS << "VectorType::get(";
 194     EmitTypeForValueType(OS, VVT.getVectorElementType().getSimpleVT());
 195     OS << ", " << VVT.getVectorNumElements() << ")";
 196   } else if (VT == MVT::iPTR) {
 197     OS << "PointerType::getUnqual(";
 198     EmitTypeGenerate(OS, ArgType->getValueAsDef("ElTy"), ArgNo);
 199     OS << ")";
 200   } else if (VT == MVT::iPTRAny) {
 201     // Make sure the user has passed us an argument type to overload. If not,
 202     // treat it as an ordinary (not overloaded) intrinsic.
 203     OS << "(" << ArgNo << " < numTys) ? Tys[" << ArgNo
 204     << "] : PointerType::getUnqual(";
 205     EmitTypeGenerate(OS, ArgType->getValueAsDef("ElTy"), ArgNo);
 206     OS << ")";
 207     ++ArgNo;
 208   } else if (VT == MVT::isVoid) {
 209     if (ArgNo == 0)
 210       OS << "Type::VoidTy";
 211     else
 212       // MVT::isVoid is used to mean varargs here.
 213       OS << "...";
 214   } else {
 215     EmitTypeForValueType(OS, VT);
 216   }
 217 }
 218
 219 /// RecordListComparator - Provide a determinstic comparator for lists of
 220 /// records.
 221 namespace {
 222   typedef std::pair<std::vector<Record*>, std::vector<Record*> > RecPair;
 223   struct RecordListComparator {
 224     bool operator()(const RecPair &LHS,
 225                     const RecPair &RHS) const {
 226       unsigned i = 0;
 227       const std::vector<Record*> *LHSVec = &LHS.first;
 228       const std::vector<Record*> *RHSVec = &RHS.first;
 229       unsigned RHSSize = RHSVec->size();
 230       unsigned LHSSize = LHSVec->size();
 231
 232       do {
 233         if (i == RHSSize) return false;  // RHS is shorter than LHS.
 234         if ((*LHSVec)[i] != (*RHSVec)[i])
 235           return (*LHSVec)[i]->getName() < (*RHSVec)[i]->getName();
 236       } while (++i != LHSSize);
 237
 238       if (i != RHSSize) return true;
 239
 240       i = 0;
 241       LHSVec = &LHS.second;
 242       RHSVec = &RHS.second;
 243       RHSSize = RHSVec->size();
 244       LHSSize = LHSVec->size();
 245
 246       for (i = 0; i != LHSSize; ++i) {
 247         if (i == RHSSize) return false;  // RHS is shorter than LHS.
 248         if ((*LHSVec)[i] != (*RHSVec)[i])
 249           return (*LHSVec)[i]->getName() < (*RHSVec)[i]->getName();
 250       }
 251
 252       return i != RHSSize;
 253     }
 254   };
 255 }
 256
 257 void IntrinsicEmitter::EmitVerifier(const std::vector<CodeGenIntrinsic> &Ints,
 258                                     std::ostream &OS) {
 259   OS << "// Verifier::visitIntrinsicFunctionCall code.\n";
 260   OS << "#ifdef GET_INTRINSIC_VERIFIER\n";
 261   OS << "  switch (ID) {\n";
 262   OS << "  default: assert(0 && \"Invalid intrinsic!\");\n";
 263
 264   // This checking can emit a lot of very common code.  To reduce the amount of
 265   // code that we emit, batch up cases that have identical types.  This avoids
 266   // problems where GCC can run out of memory compiling Verifier.cpp.
 267   typedef std::map<RecPair, std::vector<unsigned>, RecordListComparator> MapTy;
 268   MapTy UniqueArgInfos;
 269
 270   // Compute the unique argument type info.
 271   for (unsigned i = 0, e = Ints.size(); i != e; ++i)
 272     UniqueArgInfos[make_pair(Ints[i].IS.RetTypeDefs,
 273                              Ints[i].IS.ParamTypeDefs)].push_back(i);
 274
 275   // Loop through the array, emitting one comparison for each batch.
 276   for (MapTy::iterator I = UniqueArgInfos.begin(),
 277        E = UniqueArgInfos.end(); I != E; ++I) {
 278     for (unsigned i = 0, e = I->second.size(); i != e; ++i)
 279       OS << "  case Intrinsic::" << Ints[I->second[i]].EnumName << ":\t\t// "
 280          << Ints[I->second[i]].Name << "\n";
 281
 282     const RecPair &ArgTypes = I->first;
 283     const std::vector<Record*> &RetTys = ArgTypes.first;
 284     const std::vector<Record*> &ParamTys = ArgTypes.second;
 285
 286     OS << "    VerifyIntrinsicPrototype(ID, IF, " << RetTys.size() << ", "
 287        << ParamTys.size();
 288
 289     // Emit return types.
 290     for (unsigned j = 0, je = RetTys.size(); j != je; ++j) {
 291       Record *ArgType = RetTys[j];
 292       OS << ", ";
 293
 294       if (ArgType->isSubClassOf("LLVMMatchType")) {
 295         unsigned Number = ArgType->getValueAsInt("Number");
 296         assert(Number < j && "Invalid matching number!");
 297         if (ArgType->isSubClassOf("LLVMExtendedElementVectorType"))
 298           OS << "~(ExtendedElementVectorType | " << Number << ")";
 299         else if (ArgType->isSubClassOf("LLVMTruncatedElementVectorType"))
 300           OS << "~(TruncatedElementVectorType | " << Number << ")";
 301         else
 302           OS << "~" << Number;
 303       } else {
 304         MVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT"));
 305         OS << getEnumName(VT);
 306
 307         if (VT == MVT::isVoid && j != 0 && j != je - 1)
 308           throw "Var arg type not last argument";
 309       }
 310     }
 311
 312     // Emit the parameter types.
 313     for (unsigned j = 0, je = ParamTys.size(); j != je; ++j) {
 314       Record *ArgType = ParamTys[j];
 315       OS << ", ";
 316
 317       if (ArgType->isSubClassOf("LLVMMatchType")) {
 318         unsigned Number = ArgType->getValueAsInt("Number");
 319         assert(Number < j + RetTys.size() && "Invalid matching number!");
 320         if (ArgType->isSubClassOf("LLVMExtendedElementVectorType"))
 321           OS << "~(ExtendedElementVectorType | " << Number << ")";
 322         else if (ArgType->isSubClassOf("LLVMTruncatedElementVectorType"))
 323           OS << "~(TruncatedElementVectorType | " << Number << ")";
 324         else
 325           OS << "~" << Number;
 326       } else {
 327         MVT::SimpleValueType VT = getValueType(ArgType->getValueAsDef("VT"));
 328         OS << getEnumName(VT);
 329
 330         if (VT == MVT::isVoid && j != 0 && j != je - 1)
 331           throw "Var arg type not last argument";
 332       }
 333     }
 334
 335     OS << ");\n";
 336     OS << "    break;\n";
 337   }
 338   OS << "  }\n";
 339   OS << "#endif\n\n";
 340 }
 341
 342 void IntrinsicEmitter::EmitGenerator(const std::vector<CodeGenIntrinsic> &Ints,
 343                                      std::ostream &OS) {
 344   OS << "// Code for generating Intrinsic function declarations.\n";
 345   OS << "#ifdef GET_INTRINSIC_GENERATOR\n";
 346   OS << "  switch (id) {\n";
 347   OS << "  default: assert(0 && \"Invalid intrinsic!\");\n";
 348
 349   // Similar to GET_INTRINSIC_VERIFIER, batch up cases that have identical
 350   // types.
 351   typedef std::map<RecPair, std::vector<unsigned>, RecordListComparator> MapTy;
 352   MapTy UniqueArgInfos;
 353
 354   // Compute the unique argument type info.
 355   for (unsigned i = 0, e = Ints.size(); i != e; ++i)
 356     UniqueArgInfos[make_pair(Ints[i].IS.RetTypeDefs,
 357                              Ints[i].IS.ParamTypeDefs)].push_back(i);
 358
 359   // Loop through the array, emitting one generator for each batch.
 360   std::string IntrinsicStr = TargetPrefix + "Intrinsic::";
 361
 362   for (MapTy::iterator I = UniqueArgInfos.begin(),
 363        E = UniqueArgInfos.end(); I != E; ++I) {
 364     for (unsigned i = 0, e = I->second.size(); i != e; ++i)
 365       OS << "  case " << IntrinsicStr << Ints[I->second[i]].EnumName
 366          << ":\t\t// " << Ints[I->second[i]].Name << "\n";
 367
 368     const RecPair &ArgTypes = I->first;
 369     const std::vector<Record*> &RetTys = ArgTypes.first;
 370     const std::vector<Record*> &ParamTys = ArgTypes.second;
 371
 372     unsigned N = ParamTys.size();
 373
 374     if (N > 1 &&
 375         getValueType(ParamTys[N - 1]->getValueAsDef("VT")) == MVT::isVoid) {
 376       OS << "    IsVarArg = true;\n";
 377       --N;
 378     }
 379
 380     unsigned ArgNo = 0;
 381     OS << "    ResultTy = ";
 382     EmitTypeGenerate(OS, RetTys, ArgNo);
 383     OS << ";\n";
 384
 385     for (unsigned j = 0; j != N; ++j) {
 386       OS << "    ArgTys.push_back(";
 387       EmitTypeGenerate(OS, ParamTys[j], ArgNo);
 388       OS << ");\n";
 389     }
 390
 391     OS << "    break;\n";
 392   }
 393
 394   OS << "  }\n";
 395   OS << "#endif\n\n";
 396 }
 397
 398 /// EmitAttributes - This emits the Intrinsic::getAttributes method.
 399 void IntrinsicEmitter::
 400 EmitAttributes(const std::vector<CodeGenIntrinsic> &Ints, std::ostream &OS) {
 401   OS << "// Add parameter attributes that are not common to all intrinsics.\n";
 402   OS << "#ifdef GET_INTRINSIC_ATTRIBUTES\n";
 403   if (TargetOnly)
 404     OS << "static AttrListPtr getAttributes(" << TargetPrefix
 405        << "Intrinsic::ID id) {";
 406   else
 407     OS << "AttrListPtr Intrinsic::getAttributes(ID id) {";
 408   OS << "  // No intrinsic can throw exceptions.\n";
 409   OS << "  Attributes Attr = Attribute::NoUnwind;\n";
 410   OS << "  switch (id) {\n";
 411   OS << "  default: break;\n";
 412   unsigned MaxArgAttrs = 0;
 413   for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
 414     MaxArgAttrs =
 415       std::max(MaxArgAttrs, unsigned(Ints[i].ArgumentAttributes.size()));
 416     switch (Ints[i].ModRef) {
 417     default: break;
 418     case CodeGenIntrinsic::NoMem:
 419       OS << "  case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName
 420          << ":\n";
 421       break;
 422     }
 423   }
 424   OS << "    Attr |= Attribute::ReadNone; // These do not access memory.\n";
 425   OS << "    break;\n";
 426   for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
 427     switch (Ints[i].ModRef) {
 428     default: break;
 429     case CodeGenIntrinsic::ReadArgMem:
 430     case CodeGenIntrinsic::ReadMem:
 431       OS << "  case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName
 432          << ":\n";
 433       break;
 434     }
 435   }
 436   OS << "    Attr |= Attribute::ReadOnly; // These do not write memory.\n";
 437   OS << "    break;\n";
 438   OS << "  }\n";
 439   OS << "  AttributeWithIndex AWI[" << MaxArgAttrs+1 << "];\n";
 440   OS << "  unsigned NumAttrs = 0;\n";
 441   OS << "  switch (id) {\n";
 442   OS << "  default: break;\n";
 443
 444   // Add argument attributes for any intrinsics that have them.
 445   for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
 446     if (Ints[i].ArgumentAttributes.empty()) continue;
 447
 448     OS << "  case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName
 449        << ":\n";
 450
 451     std::vector<std::pair<unsigned, CodeGenIntrinsic::ArgAttribute> > ArgAttrs =
 452       Ints[i].ArgumentAttributes;
 453     // Sort by argument index.
 454     std::sort(ArgAttrs.begin(), ArgAttrs.end());
 455
 456     unsigned NumArgsWithAttrs = 0;
 457
 458     while (!ArgAttrs.empty()) {
 459       unsigned ArgNo = ArgAttrs[0].first;
 460
 461       OS << "    AWI[" << NumArgsWithAttrs++ << "] = AttributeWithIndex::get("
 462          << ArgNo+1 << ", 0";
 463
 464       while (!ArgAttrs.empty() && ArgAttrs[0].first == ArgNo) {
 465         switch (ArgAttrs[0].second) {
 466         default: assert(0 && "Unknown arg attribute");
 467         case CodeGenIntrinsic::NoCapture:
 468           OS << "|Attribute::NoCapture";
 469           break;
 470         }
 471         ArgAttrs.erase(ArgAttrs.begin());
 472       }
 473       OS << ");\n";
 474     }
 475
 476     OS << "    NumAttrs = " << NumArgsWithAttrs << ";\n";
 477     OS << "    break;\n";
 478   }
 479
 480   OS << "  }\n";
 481   OS << "  AWI[NumAttrs] = AttributeWithIndex::get(~0, Attr);\n";
 482   OS << "  return AttrListPtr::get(AWI, NumAttrs+1);\n";
 483   OS << "}\n";
 484   OS << "#endif // GET_INTRINSIC_ATTRIBUTES\n\n";
 485 }
 486
 487 /// EmitModRefBehavior - Determine intrinsic alias analysis mod/ref behavior.
 488 void IntrinsicEmitter::
 489 EmitModRefBehavior(const std::vector<CodeGenIntrinsic> &Ints, std::ostream &OS){
 490   OS << "// Determine intrinsic alias analysis mod/ref behavior.\n";
 491   OS << "#ifdef GET_INTRINSIC_MODREF_BEHAVIOR\n";
 492   OS << "switch (id) {\n";
 493   OS << "default:\n    return UnknownModRefBehavior;\n";
 494   for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
 495     if (Ints[i].ModRef == CodeGenIntrinsic::WriteMem)
 496       continue;
 497     OS << "case " << TargetPrefix << "Intrinsic::" << Ints[i].EnumName
 498       << ":\n";
 499     switch (Ints[i].ModRef) {
 500     default:
 501       assert(false && "Unknown Mod/Ref type!");
 502     case CodeGenIntrinsic::NoMem:
 503       OS << "  return DoesNotAccessMemory;\n";
 504       break;
 505     case CodeGenIntrinsic::ReadArgMem:
 506     case CodeGenIntrinsic::ReadMem:
 507       OS << "  return OnlyReadsMemory;\n";
 508       break;
 509     case CodeGenIntrinsic::WriteArgMem:
 510       OS << "  return AccessesArguments;\n";
 511       break;
 512     }
 513   }
 514   OS << "}\n";
 515   OS << "#endif // GET_INTRINSIC_MODREF_BEHAVIOR\n\n";
 516 }
 517
 518 void IntrinsicEmitter::
 519 EmitGCCBuiltinList(const std::vector<CodeGenIntrinsic> &Ints, std::ostream &OS){
 520   OS << "// Get the GCC builtin that corresponds to an LLVM intrinsic.\n";
 521   OS << "#ifdef GET_GCC_BUILTIN_NAME\n";
 522   OS << "  switch (F->getIntrinsicID()) {\n";
 523   OS << "  default: BuiltinName = \"\"; break;\n";
 524   for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
 525     if (!Ints[i].GCCBuiltinName.empty()) {
 526       OS << "  case Intrinsic::" << Ints[i].EnumName << ": BuiltinName = \""
 527          << Ints[i].GCCBuiltinName << "\"; break;\n";
 528     }
 529   }
 530   OS << "  }\n";
 531   OS << "#endif\n\n";
 532 }
 533
 534 /// EmitBuiltinComparisons - Emit comparisons to determine whether the specified
 535 /// sorted range of builtin names is equal to the current builtin.  This breaks
 536 /// it down into a simple tree.
 537 ///
 538 /// At this point, we know that all the builtins in the range have the same name
 539 /// for the first 'CharStart' characters.  Only the end of the name needs to be
 540 /// discriminated.
 541 typedef std::map<std::string, std::string>::const_iterator StrMapIterator;
 542 static void EmitBuiltinComparisons(StrMapIterator Start, StrMapIterator End,
 543                                    unsigned CharStart, unsigned Indent,
 544                                    std::string TargetPrefix, std::ostream &OS) {
 545   if (Start == End) return; // empty range.
 546
 547   // Determine what, if anything, is the same about all these strings.
 548   std::string CommonString = Start->first;
 549   unsigned NumInRange = 0;
 550   for (StrMapIterator I = Start; I != End; ++I, ++NumInRange) {
 551     // Find the first character that doesn't match.
 552     const std::string &ThisStr = I->first;
 553     unsigned NonMatchChar = CharStart;
 554     while (NonMatchChar < CommonString.size() &&
 555            NonMatchChar < ThisStr.size() &&
 556            CommonString[NonMatchChar] == ThisStr[NonMatchChar])
 557       ++NonMatchChar;
 558     // Truncate off pieces that don't match.
 559     CommonString.resize(NonMatchChar);
 560   }
 561
 562   // Just compare the rest of the string.
 563   if (NumInRange == 1) {
 564     if (CharStart != CommonString.size()) {
 565       OS << std::string(Indent*2, ' ') << "if (!memcmp(BuiltinName";
 566       if (CharStart) OS << "+" << CharStart;
 567       OS << ", \"" << (CommonString.c_str()+CharStart) << "\", ";
 568       OS << CommonString.size() - CharStart << "))\n";
 569       ++Indent;
 570     }
 571     OS << std::string(Indent*2, ' ') << "IntrinsicID = " << TargetPrefix
 572        << "Intrinsic::";
 573     OS << Start->second << ";\n";
 574     return;
 575   }
 576
 577   // At this point, we potentially have a common prefix for these builtins, emit
 578   // a check for this common prefix.
 579   if (CommonString.size() != CharStart) {
 580     OS << std::string(Indent*2, ' ') << "if (!memcmp(BuiltinName";
 581     if (CharStart) OS << "+" << CharStart;
 582     OS << ", \"" << (CommonString.c_str()+CharStart) << "\", ";
 583     OS << CommonString.size()-CharStart << ")) {\n";
 584
 585     EmitBuiltinComparisons(Start, End, CommonString.size(), Indent+1,
 586                            TargetPrefix, OS);
 587     OS << std::string(Indent*2, ' ') << "}\n";
 588     return;
 589   }
 590
 591   // Output a switch on the character that differs across the set.
 592   OS << std::string(Indent*2, ' ') << "switch (BuiltinName[" << CharStart
 593       << "]) {";
 594   if (CharStart)
 595     OS << "  // \"" << std::string(Start->first.begin(),
 596                                    Start->first.begin()+CharStart) << "\"";
 597   OS << "\n";
 598
 599   for (StrMapIterator I = Start; I != End; ) {
 600     char ThisChar = I->first[CharStart];
 601     OS << std::string(Indent*2, ' ') << "case '" << ThisChar << "':\n";
 602     // Figure out the range that has this common character.
 603     StrMapIterator NextChar = I;
 604     for (++NextChar; NextChar != End && NextChar->first[CharStart] == ThisChar;
 605          ++NextChar)
 606       /*empty*/;
 607     EmitBuiltinComparisons(I, NextChar, CharStart+1, Indent+1, TargetPrefix,OS);
 608     OS << std::string(Indent*2, ' ') << "  break;\n";
 609     I = NextChar;
 610   }
 611   OS << std::string(Indent*2, ' ') << "}\n";
 612 }
 613
 614 /// EmitTargetBuiltins - All of the builtins in the specified map are for the
 615 /// same target, and we already checked it.
 616 static void EmitTargetBuiltins(const std::map<std::string, std::string> &BIM,
 617                                const std::string &TargetPrefix,
 618                                std::ostream &OS) {
 619   // Rearrange the builtins by length.
 620   std::vector<std::map<std::string, std::string> > BuiltinsByLen;
 621   BuiltinsByLen.reserve(100);
 622
 623   for (StrMapIterator I = BIM.begin(), E = BIM.end(); I != E; ++I) {
 624     if (I->first.size() >= BuiltinsByLen.size())
 625       BuiltinsByLen.resize(I->first.size()+1);
 626     BuiltinsByLen[I->first.size()].insert(*I);
 627   }
 628
 629   // Now that we have all the builtins by their length, emit a switch stmt.
 630   OS << "    switch (strlen(BuiltinName)) {\n";
 631   OS << "    default: break;\n";
 632   for (unsigned i = 0, e = BuiltinsByLen.size(); i != e; ++i) {
 633     if (BuiltinsByLen[i].empty()) continue;
 634     OS << "    case " << i << ":\n";
 635     EmitBuiltinComparisons(BuiltinsByLen[i].begin(), BuiltinsByLen[i].end(),
 636                            0, 3, TargetPrefix, OS);
 637     OS << "      break;\n";
 638   }
 639   OS << "    }\n";
 640 }
 641
 642
 643 void IntrinsicEmitter::
 644 EmitIntrinsicToGCCBuiltinMap(const std::vector<CodeGenIntrinsic> &Ints,
 645                              std::ostream &OS) {
 646   typedef std::map<std::string, std::map<std::string, std::string> > BIMTy;
 647   BIMTy BuiltinMap;
 648   for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
 649     if (!Ints[i].GCCBuiltinName.empty()) {
 650       // Get the map for this target prefix.
 651       std::map<std::string, std::string> &BIM =BuiltinMap[Ints[i].TargetPrefix];
 652
 653       if (!BIM.insert(std::make_pair(Ints[i].GCCBuiltinName,
 654                                      Ints[i].EnumName)).second)
 655         throw "Intrinsic '" + Ints[i].TheDef->getName() +
 656               "': duplicate GCC builtin name!";
 657     }
 658   }
 659
 660   OS << "// Get the LLVM intrinsic that corresponds to a GCC builtin.\n";
 661   OS << "// This is used by the C front-end.  The GCC builtin name is passed\n";
 662   OS << "// in as BuiltinName, and a target prefix (e.g. 'ppc') is passed\n";
 663   OS << "// in as TargetPrefix.  The result is assigned to 'IntrinsicID'.\n";
 664   OS << "#ifdef GET_LLVM_INTRINSIC_FOR_GCC_BUILTIN\n";
 665
 666   if (TargetOnly) {
 667     OS << "static " << TargetPrefix << "Intrinsic::ID "
 668        << "getIntrinsicForGCCBuiltin(const char "
 669        << "*TargetPrefix, const char *BuiltinName) {\n";
 670     OS << "  " << TargetPrefix << "Intrinsic::ID IntrinsicID = ";
 671   } else {
 672     OS << "Intrinsic::ID Intrinsic::getIntrinsicForGCCBuiltin(const char "
 673        << "*TargetPrefix, const char *BuiltinName) {\n";
 674     OS << "  Intrinsic::ID IntrinsicID = ";
 675   }
 676
 677   if (TargetOnly)
 678     OS << "(" << TargetPrefix<< "Intrinsic::ID)";
 679
 680   OS << "Intrinsic::not_intrinsic;\n";
 681
 682   // Note: this could emit significantly better code if we cared.
 683   for (BIMTy::iterator I = BuiltinMap.begin(), E = BuiltinMap.end();I != E;++I){
 684     OS << "  ";
 685     if (!I->first.empty())
 686       OS << "if (!strcmp(TargetPrefix, \"" << I->first << "\")) ";
 687     else
 688       OS << "/* Target Independent Builtins */ ";
 689     OS << "{\n";
 690
 691     // Emit the comparisons for this target prefix.
 692     EmitTargetBuiltins(I->second, TargetPrefix, OS);
 693     OS << "  }\n";
 694   }
 695   OS << "  return IntrinsicID;\n";
 696   OS << "}\n";
 697   OS << "#endif\n\n";
 698 }