1 files changed, 108 insertions, 8 deletions

diff --git a/utils/TableGen/IntrinsicEmitter.cpp b/utils/TableGen/IntrinsicEmitter.cpp
index f7d852d725..567973a3ca 100644
--- a/utils/TableGen/IntrinsicEmitter.cpp
+++ b/utils/TableGen/IntrinsicEmitter.cpp
@@ -338,6 +338,112 @@ EmitGCCBuiltinList(const std::vector<CodeGenIntrinsic> &Ints, std::ostream &OS){
   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<std::string, std::string>::const_iterator StrMapIterator;
+static void EmitBuiltinComparisons(StrMapIterator Start, StrMapIterator End,
+                                   unsigned CharStart, unsigned Indent,
+                                   std::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 = 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, 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, OS);
+    OS << std::string(Indent*2, ' ') << "  break;\n";
+    I = NextChar;
+  }
+  OS << std::string(Indent*2, ' ') << "}\n";
+}
+
+/// EmitTargetBuiltins - All of the builtins in the specified map are for the
+/// same target, and we already checked it.
+static void EmitTargetBuiltins(const std::map<std::string, std::string> &BIM,
+                               std::ostream &OS) {
+  // Rearrange the builtins by length.
+  std::vector<std::map<std::string, std::string> > 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, OS);
+    OS << "      break;\n";
+  }
+  OS << "    }\n";
+}
+
+        
 void IntrinsicEmitter::
 EmitIntrinsicToGCCBuiltinMap(const std::vector<CodeGenIntrinsic> &Ints, 
                              std::ostream &OS) {
@@ -361,6 +467,7 @@ EmitIntrinsicToGCCBuiltinMap(const std::vector<CodeGenIntrinsic> &Ints,
   OS << "// in as TargetPrefix.  The result is assigned to 'IntrinsicID'.\n";
   OS << "#ifdef GET_LLVM_INTRINSIC_FOR_GCC_BUILTIN\n";
   OS << "  IntrinsicID = Intrinsic::not_intrinsic;\n";
+  
   // Note: this could emit significantly better code if we cared.
   for (BIMTy::iterator I = BuiltinMap.begin(), E = BuiltinMap.end();I != E;++I){
     OS << "  ";
@@ -370,15 +477,8 @@ EmitIntrinsicToGCCBuiltinMap(const std::vector<CodeGenIntrinsic> &Ints,
       OS << "/* Target Independent Builtins */ ";
     OS << "{\n";
 
-    OS << "    if (0);\n";
-
     // Emit the comparisons for this target prefix.
-    std::map<std::string, std::string> &BIM = I->second;
-    for (std::map<std::string, std::string>::iterator J = BIM.begin(),
-         E = BIM.end(); J != E; ++J) {
-      OS << "    else if (!strcmp(BuiltinName, \"" << J->first << "\"))\n";
-      OS << "      IntrinsicID = Intrinsic::" << J->second << ";\n";
-    }    
+    EmitTargetBuiltins(I->second, OS);
     OS << "  }\n";
   }
   OS << "#endif\n\n";