diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h
index c32b23a..487cbfc 100644
--- a/utils/TableGen/CodeGenDAGPatterns.h
+++ b/utils/TableGen/CodeGenDAGPatterns.h
@@ -15,14 +15,14 @@
 #ifndef CODEGEN_DAGPATTERNS_H
 #define CODEGEN_DAGPATTERNS_H
 
-#include <set>
-#include <algorithm>
-#include <vector>
-
 #include "CodeGenTarget.h"
 #include "CodeGenIntrinsics.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
+#include <set>
+#include <algorithm>
+#include <vector>
+#include <map>
 
 namespace llvm {
   class Record;
diff --git a/utils/TableGen/CodeGenTarget.cpp b/utils/TableGen/CodeGenTarget.cpp
index d697217..a0c2c21 100644
--- a/utils/TableGen/CodeGenTarget.cpp
+++ b/utils/TableGen/CodeGenTarget.cpp
@@ -135,11 +135,6 @@
 }
 
 
-CodeGenInstruction &CodeGenTarget::getInstruction(const Record *InstRec) const {
-  return getInstruction(InstRec->getName());
-}
-
-
 /// getAsmParser - Return the AssemblyParser definition for this target.
 ///
 Record *CodeGenTarget::getAsmParser() const {
@@ -279,25 +274,37 @@
 
   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
     std::string AsmStr = Insts[i]->getValueAsString(InstFormatName);
-    Instructions.insert(std::make_pair(Insts[i]->getName(),
-                                       CodeGenInstruction(Insts[i], AsmStr)));
+    Instructions[Insts[i]] = new CodeGenInstruction(Insts[i], AsmStr);
   }
 }
 
 static const CodeGenInstruction *
 GetInstByName(const char *Name,
-              const std::map<std::string, CodeGenInstruction> &Insts) {
-  std::map<std::string, CodeGenInstruction>::const_iterator
-    I = Insts.find(Name);
-  if (I == Insts.end())
+              const DenseMap<const Record*, CodeGenInstruction*> &Insts) {
+  const Record *Rec = Records.getDef(Name);
+  
+  DenseMap<const Record*, CodeGenInstruction*>::const_iterator
+    I = Insts.find(Rec);
+  if (Rec == 0 || I == Insts.end())
     throw std::string("Could not find '") + Name + "' instruction!";
-  return &I->second;
+  return I->second;
+}
+
+namespace {
+/// SortInstByName - Sorting predicate to sort instructions by name.
+///
+struct SortInstByName {
+  bool operator()(const CodeGenInstruction *Rec1,
+                  const CodeGenInstruction *Rec2) const {
+    return Rec1->TheDef->getName() < Rec2->TheDef->getName();
+  }
+};
 }
 
 /// getInstructionsByEnumValue - Return all of the instructions defined by the
 /// target, ordered by their enum value.
 void CodeGenTarget::ComputeInstrsByEnum() const {
-  const std::map<std::string, CodeGenInstruction> &Insts = getInstructions();
+  const DenseMap<const Record*, CodeGenInstruction*> &Insts = getInstructions();
   const CodeGenInstruction *PHI = GetInstByName("PHI", Insts);
   const CodeGenInstruction *INLINEASM = GetInstByName("INLINEASM", Insts);
   const CodeGenInstruction *DBG_LABEL = GetInstByName("DBG_LABEL", Insts);
@@ -329,10 +336,11 @@
   InstrsByEnum.push_back(COPY_TO_REGCLASS);
   InstrsByEnum.push_back(DBG_VALUE);
   
-  for (std::map<std::string, CodeGenInstruction>::const_iterator
-       I = Insts.begin(), E = Insts.end(); I != E; ++I) {
-    const CodeGenInstruction *CGI = &I->second;
+  unsigned EndOfPredefines = InstrsByEnum.size();
   
+  for (DenseMap<const Record*, CodeGenInstruction*>::const_iterator
+       I = Insts.begin(), E = Insts.end(); I != E; ++I) {
+    const CodeGenInstruction *CGI = I->second;
     if (CGI != PHI &&
         CGI != INLINEASM &&
         CGI != DBG_LABEL &&
@@ -347,6 +355,11 @@
         CGI != DBG_VALUE)
       InstrsByEnum.push_back(CGI);
   }
+  
+  // All of the instructions are now in random order based on the map iteration.
+  // Sort them by name.
+  std::sort(InstrsByEnum.begin()+EndOfPredefines, InstrsByEnum.end(),
+            SortInstByName());
 }
 
 
diff --git a/utils/TableGen/CodeGenTarget.h b/utils/TableGen/CodeGenTarget.h
index a0e631e..f5952bc 100644
--- a/utils/TableGen/CodeGenTarget.h
+++ b/utils/TableGen/CodeGenTarget.h
@@ -17,11 +17,11 @@
 #ifndef CODEGEN_TARGET_H
 #define CODEGEN_TARGET_H
 
-#include "llvm/Support/raw_ostream.h"
 #include "CodeGenRegisters.h"
 #include "CodeGenInstruction.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/DenseMap.h"
 #include <algorithm>
-#include <map>
 
 namespace llvm {
 
@@ -62,7 +62,7 @@
 class CodeGenTarget {
   Record *TargetRec;
 
-  mutable std::map<std::string, CodeGenInstruction> Instructions;
+  mutable DenseMap<const Record*, CodeGenInstruction*> Instructions;
   mutable std::vector<CodeGenRegister> Registers;
   mutable std::vector<CodeGenRegisterClass> RegisterClasses;
   mutable std::vector<MVT::SimpleValueType> LegalValueTypes;
@@ -185,25 +185,20 @@
     return false;    
   }
 
-  /// getInstructions - Return all of the instructions defined for this target.
-  ///
 private:
-  const std::map<std::string, CodeGenInstruction> &getInstructions() const {
+  DenseMap<const Record*, CodeGenInstruction*> &getInstructions() const {
     if (Instructions.empty()) ReadInstructions();
     return Instructions;
   }
-  std::map<std::string, CodeGenInstruction> &getInstructions() {
-    if (Instructions.empty()) ReadInstructions();
-    return Instructions;
-  }
-  CodeGenInstruction &getInstruction(const std::string &Name) const {
-    const std::map<std::string, CodeGenInstruction> &Insts = getInstructions();
-    assert(Insts.count(Name) && "Not an instruction!");
-    return const_cast<CodeGenInstruction&>(Insts.find(Name)->second);
-  }
 public:
   
-  CodeGenInstruction &getInstruction(const Record *InstRec) const;  
+  CodeGenInstruction &getInstruction(const Record *InstRec) const {
+    if (Instructions.empty()) ReadInstructions();
+    DenseMap<const Record*, CodeGenInstruction*>::iterator I =
+      Instructions.find(InstRec);
+    assert(I != Instructions.end() && "Not an instruction");
+    return *I->second;
+  }
 
   /// getInstructionsByEnumValue - Return all of the instructions defined by the
   /// target, ordered by their enum value.
diff --git a/utils/TableGen/InstrInfoEmitter.cpp b/utils/TableGen/InstrInfoEmitter.cpp
index 72c4e73..8f7550b 100644
--- a/utils/TableGen/InstrInfoEmitter.cpp
+++ b/utils/TableGen/InstrInfoEmitter.cpp
@@ -39,16 +39,10 @@
 // Instruction Itinerary Information.
 //===----------------------------------------------------------------------===//
 
-struct RecordNameComparator {
-  bool operator()(const Record *Rec1, const Record *Rec2) const {
-    return Rec1->getName() < Rec2->getName();
-  }
-};
-
 void InstrInfoEmitter::GatherItinClasses() {
   std::vector<Record*> DefList =
   Records.getAllDerivedDefinitions("InstrItinClass");
-  std::sort(DefList.begin(), DefList.end(), RecordNameComparator());
+  std::sort(DefList.begin(), DefList.end(), LessRecord());
   
   for (unsigned i = 0, N = DefList.size(); i < N; i++)
     ItinClassMap[DefList[i]->getName()] = i;