struct Init -> class Init.
[oota-llvm.git] / utils / TableGen / Record.h
index 44d64abd4090d88013714d3f913dbdac9127951d..60e026ad2063e7b91482b635285fbe9e1fd1f893 100644 (file)
 #ifndef RECORD_H
 #define RECORD_H
 
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/Support/Allocator.h"
 #include "llvm/Support/SourceMgr.h"
-#include "llvm/System/DataTypes.h"
+#include "llvm/Support/DataTypes.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 
@@ -34,7 +36,7 @@ class DagRecTy;
 class RecordRecTy;
 
 // Init subclasses.
-struct Init;
+class Init;
 class UnsetInit;
 class BitInit;
 class BitsInit;
@@ -57,6 +59,7 @@ class VarListElementInit;
 class Record;
 class RecordVal;
 struct MultiClass;
+class RecordKeeper;
 
 //===----------------------------------------------------------------------===//
 //  Type Classes
@@ -74,31 +77,31 @@ struct RecTy {
   virtual bool typeIsConvertibleTo(const RecTy *RHS) const = 0;
 
 public:   // These methods should only be called from subclasses of Init
-  virtual Init *convertValue( UnsetInit *UI) { return 0; }
-  virtual Init *convertValue(   BitInit *BI) { return 0; }
-  virtual Init *convertValue(  BitsInit *BI) { return 0; }
-  virtual Init *convertValue(   IntInit *II) { return 0; }
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue( UnOpInit *UI) {
-    return convertValue((TypedInit*)UI);
+  virtual const Init *convertValue(const  UnsetInit *UI) { return 0; }
+  virtual const Init *convertValue(const    BitInit *BI) { return 0; }
+  virtual const Init *convertValue(const   BitsInit *BI) { return 0; }
+  virtual const Init *convertValue(const    IntInit *II) { return 0; }
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   UnOpInit *UI) {
+    return convertValue((const TypedInit*)UI);
   }
-  virtual Init *convertValue( BinOpInit *UI) {
-    return convertValue((TypedInit*)UI);
+  virtual const Init *convertValue(const  BinOpInit *UI) {
+    return convertValue((const TypedInit*)UI);
   }
-  virtual Init *convertValue( TernOpInit *UI) {
-    return convertValue((TypedInit*)UI);
+  virtual const Init *convertValue(const TernOpInit *UI) {
+    return convertValue((const TypedInit*)UI);
   }
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( TypedInit *TI) { return 0; }
-  virtual Init *convertValue(   VarInit *VI) {
-    return convertValue((TypedInit*)VI);
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const  TypedInit *TI) { return 0; }
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return convertValue((const TypedInit*)VI);
   }
-  virtual Init *convertValue( FieldInit *FI) {
-    return convertValue((TypedInit*)FI);
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return convertValue((const TypedInit*)FI);
   }
 
 public:   // These methods should only be called by subclasses of RecTy.
@@ -124,22 +127,38 @@ inline raw_ostream &operator<<(raw_ostream &OS, const RecTy &Ty) {
 ///
 class BitRecTy : public RecTy {
 public:
-  virtual Init *convertValue( UnsetInit *UI) { return (Init*)UI; }
-  virtual Init *convertValue(   BitInit *BI) { return (Init*)BI; }
-  virtual Init *convertValue(  BitsInit *BI);
-  virtual Init *convertValue(   IntInit *II);
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return (Init*)VB; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( UnOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( BinOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TernOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TypedInit *TI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI) {
+    return (const Init*)UI;
+  }
+  virtual const Init *convertValue(const    BitInit *BI) {
+    return (const Init*)BI;
+  }
+  virtual const Init *convertValue(const   BitsInit *BI);
+  virtual const Init *convertValue(const    IntInit *II);
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) {
+    return (const Init*)VB;
+  }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const   UnOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  BinOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const TernOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TypedInit *TI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const { return "bit"; }
 
@@ -168,22 +187,32 @@ public:
 
   unsigned getNumBits() const { return Size; }
 
-  virtual Init *convertValue( UnsetInit *UI);
-  virtual Init *convertValue(   BitInit *UI);
-  virtual Init *convertValue(  BitsInit *BI);
-  virtual Init *convertValue(   IntInit *II);
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( UnOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( BinOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TernOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TypedInit *TI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI);
+  virtual const Init *convertValue(const    BitInit *UI);
+  virtual const Init *convertValue(const   BitsInit *BI);
+  virtual const Init *convertValue(const    IntInit *II);
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const   UnOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  BinOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const TernOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TypedInit *TI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const;
 
@@ -208,22 +237,36 @@ public:
 ///
 class IntRecTy : public RecTy {
 public:
-  virtual Init *convertValue( UnsetInit *UI) { return (Init*)UI; }
-  virtual Init *convertValue(   BitInit *BI);
-  virtual Init *convertValue(  BitsInit *BI);
-  virtual Init *convertValue(   IntInit *II) { return (Init*)II; }
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( UnOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( BinOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TernOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TypedInit *TI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI) {
+    return (const Init*)UI;
+  }
+  virtual const Init *convertValue(const    BitInit *BI);
+  virtual const Init *convertValue(const   BitsInit *BI);
+  virtual const Init *convertValue(const    IntInit *II) {
+    return (const Init*)II;
+  }
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const  UnOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  BinOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TernOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TypedInit *TI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const { return "int"; }
 
@@ -246,23 +289,33 @@ public:
 ///
 class StringRecTy : public RecTy {
 public:
-  virtual Init *convertValue( UnsetInit *UI) { return (Init*)UI; }
-  virtual Init *convertValue(   BitInit *BI) { return 0; }
-  virtual Init *convertValue(  BitsInit *BI) { return 0; }
-  virtual Init *convertValue(   IntInit *II) { return 0; }
-  virtual Init *convertValue(StringInit *SI) { return (Init*)SI; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue( UnOpInit *BO);
-  virtual Init *convertValue( BinOpInit *BO);
-  virtual Init *convertValue( TernOpInit *BO) { return RecTy::convertValue(BO);}
-
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( TypedInit *TI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI) {
+    return (const Init*)UI;
+  }
+  virtual const Init *convertValue(const    BitInit *BI) { return 0; }
+  virtual const Init *convertValue(const   BitsInit *BI) { return 0; }
+  virtual const Init *convertValue(const    IntInit *II) { return 0; }
+  virtual const Init *convertValue(const StringInit *SI) {
+    return (const Init*)SI;
+  }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   UnOpInit *BO);
+  virtual const Init *convertValue(const  BinOpInit *BO);
+  virtual const Init *convertValue(const TernOpInit *BO) {
+    return RecTy::convertValue(BO);
+  }
+
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const  TypedInit *TI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const { return "string"; }
 
@@ -292,22 +345,34 @@ public:
 
   RecTy *getElementType() const { return Ty; }
 
-  virtual Init *convertValue( UnsetInit *UI) { return (Init*)UI; }
-  virtual Init *convertValue(   BitInit *BI) { return 0; }
-  virtual Init *convertValue(  BitsInit *BI) { return 0; }
-  virtual Init *convertValue(   IntInit *II) { return 0; }
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI);
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( UnOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( BinOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TernOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TypedInit *TI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI) {
+    return (const Init*)UI;
+  }
+  virtual const Init *convertValue(const    BitInit *BI) { return 0; }
+  virtual const Init *convertValue(const   BitsInit *BI) { return 0; }
+  virtual const Init *convertValue(const    IntInit *II) { return 0; }
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI);
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const  UnOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  BinOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TernOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TypedInit *TI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const;
 
@@ -331,22 +396,36 @@ public:
 ///
 class CodeRecTy : public RecTy {
 public:
-  virtual Init *convertValue( UnsetInit *UI) { return (Init*)UI; }
-  virtual Init *convertValue(   BitInit *BI) { return 0; }
-  virtual Init *convertValue(  BitsInit *BI) { return 0; }
-  virtual Init *convertValue(   IntInit *II) { return 0; }
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue(  CodeInit *CI) { return (Init*)CI; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( UnOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( BinOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TernOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TypedInit *TI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI) {
+    return (const Init*)UI;
+  }
+  virtual const Init *convertValue(const    BitInit *BI) { return 0; }
+  virtual const Init *convertValue(const   BitsInit *BI) { return 0; }
+  virtual const Init *convertValue(const    IntInit *II) { return 0; }
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   CodeInit *CI) {
+    return (const Init*)CI;
+  }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const  UnOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  BinOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TernOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TypedInit *TI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const { return "code"; }
 
@@ -367,22 +446,32 @@ public:
 ///
 class DagRecTy : public RecTy {
 public:
-  virtual Init *convertValue( UnsetInit *UI) { return (Init*)UI; }
-  virtual Init *convertValue(   BitInit *BI) { return 0; }
-  virtual Init *convertValue(  BitsInit *BI) { return 0; }
-  virtual Init *convertValue(   IntInit *II) { return 0; }
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue(   DefInit *DI) { return 0; }
-  virtual Init *convertValue( UnOpInit *BO);
-  virtual Init *convertValue( BinOpInit *BO);
-  virtual Init *convertValue( TernOpInit *BO) { return RecTy::convertValue(BO);}
-  virtual Init *convertValue(   DagInit *CI) { return (Init*)CI; }
-  virtual Init *convertValue( TypedInit *TI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI) {
+    return (const Init*)UI;
+  }
+  virtual const Init *convertValue(const    BitInit *BI) { return 0; }
+  virtual const Init *convertValue(const   BitsInit *BI) { return 0; }
+  virtual const Init *convertValue(const    IntInit *II) { return 0; }
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const    DefInit *DI) { return 0; }
+  virtual const Init *convertValue(const  UnOpInit *BO);
+  virtual const Init *convertValue(const  BinOpInit *BO);
+  virtual const Init *convertValue(const  TernOpInit *BO) {
+    return RecTy::convertValue(BO);
+  }
+  virtual const Init *convertValue(const    DagInit *CI) {
+    return (const Init*)CI;
+  }
+  virtual const Init *convertValue(const  TypedInit *TI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const { return "dag"; }
 
@@ -411,22 +500,34 @@ public:
 
   Record *getRecord() const { return Rec; }
 
-  virtual Init *convertValue( UnsetInit *UI) { return (Init*)UI; }
-  virtual Init *convertValue(   BitInit *BI) { return 0; }
-  virtual Init *convertValue(  BitsInit *BI) { return 0; }
-  virtual Init *convertValue(   IntInit *II) { return 0; }
-  virtual Init *convertValue(StringInit *SI) { return 0; }
-  virtual Init *convertValue(  ListInit *LI) { return 0; }
-  virtual Init *convertValue(  CodeInit *CI) { return 0; }
-  virtual Init *convertValue(VarBitInit *VB) { return 0; }
-  virtual Init *convertValue( UnOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( BinOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue( TernOpInit *UI) { return RecTy::convertValue(UI);}
-  virtual Init *convertValue(   DefInit *DI);
-  virtual Init *convertValue(   DagInit *DI) { return 0; }
-  virtual Init *convertValue( TypedInit *VI);
-  virtual Init *convertValue(   VarInit *VI) { return RecTy::convertValue(VI);}
-  virtual Init *convertValue( FieldInit *FI) { return RecTy::convertValue(FI);}
+  virtual const Init *convertValue(const  UnsetInit *UI) {
+    return (const Init*)UI;
+  }
+  virtual const Init *convertValue(const    BitInit *BI) { return 0; }
+  virtual const Init *convertValue(const   BitsInit *BI) { return 0; }
+  virtual const Init *convertValue(const    IntInit *II) { return 0; }
+  virtual const Init *convertValue(const StringInit *SI) { return 0; }
+  virtual const Init *convertValue(const   ListInit *LI) { return 0; }
+  virtual const Init *convertValue(const   CodeInit *CI) { return 0; }
+  virtual const Init *convertValue(const VarBitInit *VB) { return 0; }
+  virtual const Init *convertValue(const  UnOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  BinOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const  TernOpInit *UI) {
+    return RecTy::convertValue(UI);
+  }
+  virtual const Init *convertValue(const    DefInit *DI);
+  virtual const Init *convertValue(const    DagInit *DI) { return 0; }
+  virtual const Init *convertValue(const  TypedInit *VI);
+  virtual const Init *convertValue(const    VarInit *VI) {
+    return RecTy::convertValue(VI);
+  }
+  virtual const Init *convertValue(const  FieldInit *FI) {
+    return RecTy::convertValue(FI);
+  }
 
   std::string getAsString() const;
 
@@ -452,9 +553,43 @@ RecTy *resolveTypes(RecTy *T1, RecTy *T2);
 //  Initializer Classes
 //===----------------------------------------------------------------------===//
 
-struct Init {
+class Init : public FastFoldingSetNode {
+  Init(const Init &);  // Do not define.
+  Init &operator=(const Init &);  // Do not define.
+
+protected:
+  Init(const FoldingSetNodeID &ID) : FastFoldingSetNode(ID) {}
+
+  static FoldingSet<Init> UniqueInits;
+  static BumpPtrAllocator InitAllocator;
+
+  enum Type {
+    initUnset,
+    initBit,
+    initBits,
+    initInt,
+    initString,
+    initCode,
+    initList,
+    initUnOp,
+    initBinOp,
+    initTernOp,
+    initQuadOp,
+    initVar,
+    initVarBit,
+    initVarListElement,
+    initDef,
+    initField,
+    initDag
+  };
+
+public:
   virtual ~Init() {}
 
+  static void ReleaseMemory() {
+    InitAllocator.Reset();
+  }
+
   /// isComplete - This virtual method should be overridden by values that may
   /// not be completely specified yet.
   virtual bool isComplete() const { return true; }
@@ -473,14 +608,15 @@ struct Init {
   /// function that should be overridden to call the appropriate
   /// RecTy::convertValue method.
   ///
-  virtual Init *convertInitializerTo(RecTy *Ty) = 0;
+  virtual const Init *convertInitializerTo(RecTy *Ty) const = 0;
 
   /// convertInitializerBitRange - This method is used to implement the bitrange
   /// selection operator.  Given an initializer, it selects the specified bits
   /// out, returning them as a new init of bits type.  If it is not legal to use
   /// the bit subscript operator on this initializer, return null.
   ///
-  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits) {
+  virtual const Init *
+  convertInitializerBitRange(const std::vector<unsigned> &Bits) const {
     return 0;
   }
 
@@ -489,7 +625,8 @@ struct Init {
   /// elements, returning them as a new init of list type.  If it is not legal
   /// to take a slice of this, return null.
   ///
-  virtual Init *convertInitListSlice(const std::vector<unsigned> &Elements) {
+  virtual const Init *
+  convertInitListSlice(const std::vector<unsigned> &Elements) const {
     return 0;
   }
 
@@ -503,8 +640,8 @@ struct Init {
   /// initializer for the specified field.  If getFieldType returns non-null
   /// this method should return non-null, otherwise it returns null.
   ///
-  virtual Init *getFieldInit(Record &R, const RecordVal *RV,
-                             const std::string &FieldName) const {
+  virtual const Init *getFieldInit(Record &R, const RecordVal *RV,
+                                   const std::string &FieldName) const {
     return 0;
   }
 
@@ -513,7 +650,8 @@ struct Init {
   /// If a value is set for the variable later, this method will be called on
   /// users of the value to allow the value to propagate out.
   ///
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV) {
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const {
     return this;
   }
 };
@@ -527,13 +665,20 @@ inline raw_ostream &operator<<(raw_ostream &OS, const Init &I) {
 ///
 class TypedInit : public Init {
   RecTy *Ty;
-public:
-  explicit TypedInit(RecTy *T) : Ty(T) {}
 
+  TypedInit(const TypedInit &Other);  // Do not define.
+  TypedInit &operator=(const TypedInit &Other);  // Do not define.
+
+protected:
+  explicit TypedInit(const FoldingSetNodeID &ID, RecTy *T) : Init(ID), Ty(T) {}
+
+public:
   RecTy *getType() const { return Ty; }
 
-  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
-  virtual Init *convertInitListSlice(const std::vector<unsigned> &Elements);
+  virtual const Init *
+  convertInitializerBitRange(const std::vector<unsigned> &Bits) const;
+  virtual const Init *
+  convertInitListSlice(const std::vector<unsigned> &Elements) const;
 
   /// getFieldType - This method is used to implement the FieldInit class.
   /// Implementors of this method should return the type of the named field if
@@ -545,22 +690,29 @@ public:
   /// VarBitInit::resolveReferences.  If the bit is able to be resolved, we
   /// simply return the resolved value, otherwise we return null.
   ///
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit) = 0;
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const = 0;
 
   /// resolveListElementReference - This method is used to implement
   /// VarListElementInit::resolveReferences.  If the list element is resolvable
   /// now, we return the resolved value, otherwise we return null.
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt) = 0;
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const = 0;
 };
 
 
 /// UnsetInit - ? - Represents an uninitialized value
 ///
 class UnsetInit : public Init {
+  UnsetInit(const FoldingSetNodeID &ID) : Init(ID) {}
+  UnsetInit(const UnsetInit &);  // Do not define.
+  UnsetInit &operator=(const UnsetInit &Other);  // Do not define.
+
 public:
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  static const UnsetInit *Create();
+
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
@@ -573,12 +725,17 @@ public:
 ///
 class BitInit : public Init {
   bool Value;
+
+  explicit BitInit(const FoldingSetNodeID &ID, bool V) : Init(ID), Value(V) {}
+  BitInit(const BitInit &Other);  // Do not define.
+  BitInit &operator=(BitInit &Other);  // Do not define.
+
 public:
-  explicit BitInit(bool V) : Value(V) {}
+  static const BitInit *Create(bool V);
 
   bool getValue() const { return Value; }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
@@ -589,26 +746,56 @@ public:
 /// It contains a vector of bits, whose size is determined by the type.
 ///
 class BitsInit : public Init {
-  std::vector<Init*> Bits;
+  std::vector<const Init*> Bits;
+
+  BitsInit(const FoldingSetNodeID &ID, unsigned Size)
+      : Init(ID), Bits(Size) {}
+
+  template<typename InputIterator>
+  BitsInit(const FoldingSetNodeID &ID, InputIterator start, InputIterator end) 
+      : Init(ID), Bits(start, end) {}
+
+  BitsInit(const BitsInit &Other);  // Do not define.
+  BitsInit &operator=(const BitsInit &Other);  // Do not define.
+
 public:
-  explicit BitsInit(unsigned Size) : Bits(Size) {}
+  template<typename InputIterator>
+  static const BitsInit *Create(InputIterator Start, InputIterator End) {
+    FoldingSetNodeID ID;
+    ID.AddInteger(initBits);
+    ID.AddInteger(std::distance(Start, End));
+
+    InputIterator S = Start;
+    while (S != End)
+      ID.AddPointer(*S++);
+
+    void *IP = 0;
+    if (const Init *I = UniqueInits.FindNodeOrInsertPos(ID, IP))
+      return static_cast<const BitsInit *>(I);
+
+    BitsInit *I = InitAllocator.Allocate<BitsInit>();
+    new (I) BitsInit(ID, Start, End);
+    UniqueInits.InsertNode(I, IP);
+    return I;
+  }
 
   unsigned getNumBits() const { return Bits.size(); }
 
-  Init *getBit(unsigned Bit) const {
+  const Init *getBit(unsigned Bit) const {
     assert(Bit < Bits.size() && "Bit index out of range!");
     return Bits[Bit];
   }
-  void setBit(unsigned Bit, Init *V) {
+  void setBit(unsigned Bit, const Init *V) {
     assert(Bit < Bits.size() && "Bit index out of range!");
     assert(Bits[Bit] == 0 && "Bit already set!");
     Bits[Bit] = V;
   }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
-  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
+  virtual const Init *
+  convertInitializerBitRange(const std::vector<unsigned> &Bits) const;
 
   virtual bool isComplete() const {
     for (unsigned i = 0; i != getNumBits(); ++i)
@@ -622,7 +809,8 @@ public:
   }
   virtual std::string getAsString() const;
 
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 };
 
 
@@ -630,15 +818,23 @@ public:
 ///
 class IntInit : public TypedInit {
   int64_t Value;
+
+  explicit IntInit(const FoldingSetNodeID &ID, int64_t V)
+      : TypedInit(ID, new IntRecTy), Value(V) {}
+
+  IntInit(const IntInit &Other);  // Do not define.
+  IntInit &operator=(const IntInit &Other);  // Do note define.
+
 public:
-  explicit IntInit(int64_t V) : TypedInit(new IntRecTy), Value(V) {}
+  static const IntInit *Create(int64_t V);
 
   int64_t getValue() const { return Value; }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
-  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
+  virtual const Init *
+  convertInitializerBitRange(const std::vector<unsigned> &Bits) const;
 
   virtual std::string getAsString() const;
 
@@ -646,8 +842,8 @@ public:
   /// VarBitInit::resolveReferences.  If the bit is able to be resolved, we
   /// simply return the resolved value, otherwise we return null.
   ///
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit) {
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const {
     assert(0 && "Illegal bit reference off int");
     return 0;
   }
@@ -655,8 +851,9 @@ public:
   /// resolveListElementReference - This method is used to implement
   /// VarListElementInit::resolveReferences.  If the list element is resolvable
   /// now, we return the resolved value, otherwise we return null.
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt) {
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const {
     assert(0 && "Illegal element reference off int");
     return 0;
   }
@@ -667,13 +864,19 @@ public:
 ///
 class StringInit : public TypedInit {
   std::string Value;
+
+  explicit StringInit(const FoldingSetNodeID &ID, const std::string &V)
+      : TypedInit(ID, new StringRecTy), Value(V) {}
+
+  StringInit(const StringInit &Other);  // Do not define.
+  StringInit &operator=(const StringInit &Other);  // Do not define.
+
 public:
-  explicit StringInit(const std::string &V)
-    : TypedInit(new StringRecTy), Value(V) {}
+  static const StringInit *Create(const std::string &V);
 
   const std::string &getValue() const { return Value; }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
@@ -683,8 +886,8 @@ public:
   /// VarBitInit::resolveReferences.  If the bit is able to be resolved, we
   /// simply return the resolved value, otherwise we return null.
   ///
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit) {
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const {
     assert(0 && "Illegal bit reference off string");
     return 0;
   }
@@ -692,8 +895,9 @@ public:
   /// resolveListElementReference - This method is used to implement
   /// VarListElementInit::resolveReferences.  If the list element is resolvable
   /// now, we return the resolved value, otherwise we return null.
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt) {
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const {
     assert(0 && "Illegal element reference off string");
     return 0;
   }
@@ -703,12 +907,19 @@ public:
 ///
 class CodeInit : public Init {
   std::string Value;
+
+  explicit CodeInit(const FoldingSetNodeID &ID, const std::string &V)
+      : Init(ID), Value(V) {}
+
+  CodeInit(const CodeInit &Other);  // Do not define.
+  CodeInit &operator=(const CodeInit &Other);  // Do not define.
+
 public:
-  explicit CodeInit(const std::string &V) : Value(V) {}
+  static const CodeInit *Create(const std::string &V);
 
-  const std::string getValue() const { return Value; }
+  const std::string &getValue() const { return Value; }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
@@ -718,29 +929,61 @@ public:
 /// ListInit - [AL, AH, CL] - Represent a list of defs
 ///
 class ListInit : public TypedInit {
-  std::vector<Init*> Values;
+  std::vector<const Init*> Values;
+
 public:
-  typedef std::vector<Init*>::iterator       iterator;
-  typedef std::vector<Init*>::const_iterator const_iterator;
+  typedef std::vector<const Init*>::const_iterator const_iterator;
 
-  explicit ListInit(std::vector<Init*> &Vs, RecTy *EltTy)
-    : TypedInit(new ListRecTy(EltTy)) {
+private:
+  ListInit(const FoldingSetNodeID &ID, std::vector<const Init*> &Vs,
+           RecTy *EltTy)
+      : TypedInit(ID, new ListRecTy(EltTy)) {
     Values.swap(Vs);
   }
-  explicit ListInit(iterator Start, iterator End, RecTy *EltTy)
-      : TypedInit(new ListRecTy(EltTy)), Values(Start, End) {}
+
+  template<typename InputIterator>
+  ListInit(const FoldingSetNodeID &ID, InputIterator Start, InputIterator End,
+           RecTy *EltTy)
+      : TypedInit(ID, new ListRecTy(EltTy)), Values(Start, End) {}
+
+  ListInit(const ListInit &Other);  // Do not define.
+  ListInit &operator=(const ListInit &Other);  // Do not define.
+
+public:
+  static const ListInit *Create(std::vector<const Init*> &Vs, RecTy *EltTy);
+
+  template<typename InputIterator>
+  static const ListInit *Create(InputIterator Start, InputIterator End,
+                                RecTy *EltTy) {
+    FoldingSetNodeID ID;
+    ID.AddInteger(initList);
+    ID.AddString(EltTy->getAsString());
+
+    InputIterator S = Start;
+    while (S != End)
+      ID.AddPointer(*S++); 
+
+    void *IP = 0;
+    if (const Init *I = UniqueInits.FindNodeOrInsertPos(ID, IP))
+      return static_cast<const ListInit *>(I);
+
+    ListInit *I = InitAllocator.Allocate<ListInit>();
+    new (I) ListInit(ID, Start, End, EltTy);
+    UniqueInits.InsertNode(I, IP);
+    return I;
+  }
 
   unsigned getSize() const { return Values.size(); }
-  Init *getElement(unsigned i) const {
+  const Init *getElement(unsigned i) const {
     assert(i < Values.size() && "List element index out of range!");
     return Values[i];
   }
 
   Record *getElementAsRecord(unsigned i) const;
 
-  Init *convertInitListSlice(const std::vector<unsigned> &Elements);
+  const Init *convertInitListSlice(const std::vector<unsigned> &Elements) const;
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
@@ -749,13 +992,12 @@ public:
   /// If a value is set for the variable later, this method will be called on
   /// users of the value to allow the value to propagate out.
   ///
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 
   virtual std::string getAsString() const;
 
-  inline iterator       begin()       { return Values.begin(); }
   inline const_iterator begin() const { return Values.begin(); }
-  inline iterator       end  ()       { return Values.end();   }
   inline const_iterator end  () const { return Values.end();   }
 
   inline size_t         size () const { return Values.size();  }
@@ -765,8 +1007,8 @@ public:
   /// VarBitInit::resolveReferences.  If the bit is able to be resolved, we
   /// simply return the resolved value, otherwise we return null.
   ///
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit) {
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const {
     assert(0 && "Illegal bit reference off list");
     return 0;
   }
@@ -774,35 +1016,42 @@ public:
   /// resolveListElementReference - This method is used to implement
   /// VarListElementInit::resolveReferences.  If the list element is resolvable
   /// now, we return the resolved value, otherwise we return null.
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt);
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const;
 };
 
 
 /// OpInit - Base class for operators
 ///
 class OpInit : public TypedInit {
-public:
-  OpInit(RecTy *Type) : TypedInit(Type) {}
+  OpInit(const OpInit &Other);  // Do not define.
+  OpInit &operator=(OpInit &Other);  // Do not define.
+
+protected:
+  explicit OpInit(const FoldingSetNodeID &ID, RecTy *Type)
+      : TypedInit(ID, Type) {}
 
+public:
   // Clone - Clone this operator, replacing arguments with the new list
-  virtual OpInit *clone(std::vector<Init *> &Operands) = 0;
+  virtual const OpInit *clone(std::vector<const Init *> &Operands) const = 0;
 
   virtual int getNumOperands() const = 0;
-  virtual Init *getOperand(int i) = 0;
+  virtual const Init *getOperand(int i) const = 0;
 
   // Fold - If possible, fold this to a simpler init.  Return this if not
   // possible to fold.
-  virtual Init *Fold(Record *CurRec, MultiClass *CurMultiClass) = 0;
+  virtual const Init *Fold(Record *CurRec, MultiClass *CurMultiClass) const = 0;
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit);
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt);
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const;
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const;
 };
 
 
@@ -810,36 +1059,43 @@ public:
 ///
 class UnOpInit : public OpInit {
 public:
-  enum UnaryOp { CAST, CAR, CDR, LNULL };
+  enum UnaryOp { CAST, HEAD, TAIL, EMPTY };
 private:
   UnaryOp Opc;
-  Init *LHS;
+  const Init *LHS;
+
+  UnOpInit(const FoldingSetNodeID &ID, UnaryOp opc, const Init *lhs,
+           RecTy *Type)
+      : OpInit(ID, Type), Opc(opc), LHS(lhs) {}
+
+  UnOpInit(const UnOpInit &Other);  // Do not define.
+  UnOpInit &operator=(const UnOpInit &Other);  // Do not define.
+
 public:
-  UnOpInit(UnaryOp opc, Init *lhs, RecTy *Type) :
-      OpInit(Type), Opc(opc), LHS(lhs) {
-  }
+  static const UnOpInit *Create(UnaryOp opc, const Init *lhs, RecTy *Type);
 
   // Clone - Clone this operator, replacing arguments with the new list
-  virtual OpInit *clone(std::vector<Init *> &Operands) {
+  virtual const OpInit *clone(std::vector<const Init *> &Operands) const {
     assert(Operands.size() == 1 &&
            "Wrong number of operands for unary operation");
-    return new UnOpInit(getOpcode(), *Operands.begin(), getType());
+    return UnOpInit::Create(getOpcode(), *Operands.begin(), getType());
   }
 
   int getNumOperands() const { return 1; }
-  Init *getOperand(int i) {
+  const Init *getOperand(int i) const {
     assert(i == 0 && "Invalid operand id for unary operator");
     return getOperand();
   }
 
   UnaryOp getOpcode() const { return Opc; }
-  Init *getOperand() const { return LHS; }
+  const Init *getOperand() const { return LHS; }
 
   // Fold - If possible, fold this to a simpler init.  Return this if not
   // possible to fold.
-  Init *Fold(Record *CurRec, MultiClass *CurMultiClass);
+  const Init *Fold(Record *CurRec, MultiClass *CurMultiClass)const ;
 
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 
   virtual std::string getAsString() const;
 };
@@ -851,21 +1107,28 @@ public:
   enum BinaryOp { SHL, SRA, SRL, STRCONCAT, CONCAT, EQ };
 private:
   BinaryOp Opc;
-  Init *LHS, *RHS;
+  const Init *LHS, *RHS;
+
+  BinOpInit(const FoldingSetNodeID &ID, BinaryOp opc, const Init *lhs,
+            const Init *rhs, RecTy *Type) :
+      OpInit(ID, Type), Opc(opc), LHS(lhs), RHS(rhs) {}
+
+  BinOpInit(const BinOpInit &Other);  // Do not define.
+  BinOpInit &operator=(const BinOpInit &Other);  // Do not define.
+
 public:
-  BinOpInit(BinaryOp opc, Init *lhs, Init *rhs, RecTy *Type) :
-      OpInit(Type), Opc(opc), LHS(lhs), RHS(rhs) {
-  }
+  static const BinOpInit *Create(BinaryOp opc, const Init *lhs, const Init *rhs,
+                                 RecTy *Type);
 
   // Clone - Clone this operator, replacing arguments with the new list
-  virtual OpInit *clone(std::vector<Init *> &Operands) {
+  virtual const OpInit *clone(std::vector<const Init *> &Operands) const {
     assert(Operands.size() == 2 &&
            "Wrong number of operands for binary operation");
-    return new BinOpInit(getOpcode(), Operands[0], Operands[1], getType());
+    return BinOpInit::Create(getOpcode(), Operands[0], Operands[1], getType());
   }
 
   int getNumOperands() const { return 2; }
-  Init *getOperand(int i) {
+  const Init *getOperand(int i) const {
     assert((i == 0 || i == 1) && "Invalid operand id for binary operator");
     if (i == 0) {
       return getLHS();
@@ -875,14 +1138,15 @@ public:
   }
 
   BinaryOp getOpcode() const { return Opc; }
-  Init *getLHS() const { return LHS; }
-  Init *getRHS() const { return RHS; }
+  const Init *getLHS() const { return LHS; }
+  const Init *getRHS() const { return RHS; }
 
   // Fold - If possible, fold this to a simpler init.  Return this if not
   // possible to fold.
-  Init *Fold(Record *CurRec, MultiClass *CurMultiClass);
+  const Init *Fold(Record *CurRec, MultiClass *CurMultiClass) const;
 
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 
   virtual std::string getAsString() const;
 };
@@ -894,22 +1158,30 @@ public:
   enum TernaryOp { SUBST, FOREACH, IF };
 private:
   TernaryOp Opc;
-  Init *LHS, *MHS, *RHS;
+  const Init *LHS, *MHS, *RHS;
+
+  TernOpInit(const FoldingSetNodeID &ID, TernaryOp opc, const Init *lhs,
+             const Init *mhs, const Init *rhs, RecTy *Type) :
+      OpInit(ID, Type), Opc(opc), LHS(lhs), MHS(mhs), RHS(rhs) {}
+
+  TernOpInit(const TernOpInit &Other);  // Do not define.
+  TernOpInit &operator=(const TernOpInit &Other);  // Do not define.
+
 public:
-  TernOpInit(TernaryOp opc, Init *lhs, Init *mhs, Init *rhs, RecTy *Type) :
-      OpInit(Type), Opc(opc), LHS(lhs), MHS(mhs), RHS(rhs) {
-  }
+  static const TernOpInit *Create(TernaryOp opc, const Init *lhs,
+                                  const Init *mhs, const Init *rhs,
+                                  RecTy *Type);
 
   // Clone - Clone this operator, replacing arguments with the new list
-  virtual OpInit *clone(std::vector<Init *> &Operands) {
+  virtual const OpInit *clone(std::vector<const Init *> &Operands) const {
     assert(Operands.size() == 3 &&
            "Wrong number of operands for ternary operation");
-    return new TernOpInit(getOpcode(), Operands[0], Operands[1], Operands[2],
-                          getType());
+    return TernOpInit::Create(getOpcode(), Operands[0], Operands[1],
+                              Operands[2], getType());
   }
 
   int getNumOperands() const { return 3; }
-  Init *getOperand(int i) {
+  const Init *getOperand(int i) const {
     assert((i == 0 || i == 1 || i == 2) &&
            "Invalid operand id for ternary operator");
     if (i == 0) {
@@ -922,15 +1194,18 @@ public:
   }
 
   TernaryOp getOpcode() const { return Opc; }
-  Init *getLHS() const { return LHS; }
-  Init *getMHS() const { return MHS; }
-  Init *getRHS() const { return RHS; }
+  const Init *getLHS() const { return LHS; }
+  const Init *getMHS() const { return MHS; }
+  const Init *getRHS() const { return RHS; }
 
   // Fold - If possible, fold this to a simpler init.  Return this if not
   // possible to fold.
-  Init *Fold(Record *CurRec, MultiClass *CurMultiClass);
+  const Init *Fold(Record *CurRec, MultiClass *CurMultiClass) const;
+
+  virtual bool isComplete() const { return false; }
 
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 
   virtual std::string getAsString() const;
 };
@@ -940,23 +1215,31 @@ public:
 ///
 class VarInit : public TypedInit {
   std::string VarName;
+
+  explicit VarInit(const FoldingSetNodeID &ID, const std::string &VN, RecTy *T)
+      : TypedInit(ID, T), VarName(VN) {}
+
+  VarInit(const VarInit &Other);  // Do not define.
+  VarInit &operator=(const VarInit &Other);  // Do not define.
+
 public:
-  explicit VarInit(const std::string &VN, RecTy *T)
-    : TypedInit(T), VarName(VN) {}
+  static const VarInit *Create(const std::string &VN, RecTy *T);
+  static const VarInit *Create(const Init *VN, RecTy *T);
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
   const std::string &getName() const { return VarName; }
 
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit);
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt);
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const;
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const;
 
   virtual RecTy *getFieldType(const std::string &FieldName) const;
-  virtual Init *getFieldInit(Record &R, const RecordVal *RV,
+  virtual const Init *getFieldInit(Record &R, const RecordVal *RV,
                              const std::string &FieldName) const;
 
   /// resolveReferences - This method is used by classes that refer to other
@@ -964,7 +1247,8 @@ public:
   /// If a value is set for the variable later, this method will be called on
   /// users of the value to allow the value to propagate out.
   ///
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 
   virtual std::string getAsString() const { return VarName; }
 };
@@ -973,76 +1257,101 @@ public:
 /// VarBitInit - Opcode{0} - Represent access to one bit of a variable or field.
 ///
 class VarBitInit : public Init {
-  TypedInit *TI;
+  const TypedInit *TI;
   unsigned Bit;
-public:
-  VarBitInit(TypedInit *T, unsigned B) : TI(T), Bit(B) {
+
+  VarBitInit(const FoldingSetNodeID &ID, const TypedInit *T, unsigned B)
+      : Init(ID), TI(T), Bit(B) {
     assert(T->getType() && dynamic_cast<BitsRecTy*>(T->getType()) &&
            ((BitsRecTy*)T->getType())->getNumBits() > B &&
            "Illegal VarBitInit expression!");
   }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  VarBitInit(const VarBitInit &Other);  // Do not define.
+  VarBitInit &operator=(const VarBitInit &Other);  // Do not define.
+
+public:
+  static const VarBitInit *Create(const TypedInit *T, unsigned B);
+
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
-  TypedInit *getVariable() const { return TI; }
+  const TypedInit *getVariable() const { return TI; }
   unsigned getBitNum() const { return Bit; }
 
   virtual std::string getAsString() const;
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 };
 
 /// VarListElementInit - List[4] - Represent access to one element of a var or
 /// field.
 class VarListElementInit : public TypedInit {
-  TypedInit *TI;
+  const TypedInit *TI;
   unsigned Element;
-public:
-  VarListElementInit(TypedInit *T, unsigned E)
-    : TypedInit(dynamic_cast<ListRecTy*>(T->getType())->getElementType()),
+
+  VarListElementInit(const FoldingSetNodeID &ID, const TypedInit *T, unsigned E)
+      : TypedInit(ID, dynamic_cast<ListRecTy*>(T->getType())->getElementType()),
                 TI(T), Element(E) {
     assert(T->getType() && dynamic_cast<ListRecTy*>(T->getType()) &&
            "Illegal VarBitInit expression!");
   }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  VarListElementInit(const VarListElementInit &Other);  // Do not define.
+  VarListElementInit &operator=(const VarListElementInit &Other);  // Do
+                                                                   // not
+                                                                   // define.
+
+public:
+  static const VarListElementInit *Create(const TypedInit *T, unsigned E);
+
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
-  TypedInit *getVariable() const { return TI; }
+  const TypedInit *getVariable() const { return TI; }
   unsigned getElementNum() const { return Element; }
 
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit);
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const;
 
   /// resolveListElementReference - This method is used to implement
   /// VarListElementInit::resolveReferences.  If the list element is resolvable
   /// now, we return the resolved value, otherwise we return null.
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt);
+  virtual const Init *resolveListElementReference(Record &R, const RecordVal *RV,
+                                            unsigned Elt) const;
 
   virtual std::string getAsString() const;
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 };
 
 /// DefInit - AL - Represent a reference to a 'def' in the description
 ///
 class DefInit : public TypedInit {
   Record *Def;
+
+  explicit DefInit(const FoldingSetNodeID &ID, Record *D)
+      : TypedInit(ID, new RecordRecTy(D)), Def(D) {}
+
+  DefInit(const DefInit &Other);  // Do not define.
+  DefInit &operator=(const DefInit &Other);  // Do not define.
+
 public:
-  explicit DefInit(Record *D) : TypedInit(new RecordRecTy(D)), Def(D) {}
+  static const DefInit *Create(Record *D);
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
   Record *getDef() const { return Def; }
 
-  //virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
+  //virtual const Init *
+  //convertInitializerBitRange(const std::vector<unsigned> &Bits) const;
 
   virtual RecTy *getFieldType(const std::string &FieldName) const;
-  virtual Init *getFieldInit(Record &R, const RecordVal *RV,
+  virtual const Init *getFieldInit(Record &R, const RecordVal *RV,
                              const std::string &FieldName) const;
 
   virtual std::string getAsString() const;
@@ -1051,8 +1360,8 @@ public:
   /// VarBitInit::resolveReferences.  If the bit is able to be resolved, we
   /// simply return the resolved value, otherwise we return null.
   ///
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit) {
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const {
     assert(0 && "Illegal bit reference off def");
     return 0;
   }
@@ -1060,8 +1369,9 @@ public:
   /// resolveListElementReference - This method is used to implement
   /// VarListElementInit::resolveReferences.  If the list element is resolvable
   /// now, we return the resolved value, otherwise we return null.
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt) {
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const {
     assert(0 && "Illegal element reference off def");
     return 0;
   }
@@ -1071,24 +1381,33 @@ public:
 /// FieldInit - X.Y - Represent a reference to a subfield of a variable
 ///
 class FieldInit : public TypedInit {
-  Init *Rec;                // Record we are referring to
+  const Init *Rec;                // Record we are referring to
   std::string FieldName;    // Field we are accessing
-public:
-  FieldInit(Init *R, const std::string &FN)
-    : TypedInit(R->getFieldType(FN)), Rec(R), FieldName(FN) {
+
+  FieldInit(const FoldingSetNodeID &ID, const Init *R, const std::string &FN)
+      : TypedInit(ID, R->getFieldType(FN)), Rec(R), FieldName(FN) {
     assert(getType() && "FieldInit with non-record type!");
   }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  FieldInit(const FieldInit &Other);  // Do not define.
+  FieldInit &operator=(const FieldInit &Other);  // Do not define.
+
+public:
+  static const FieldInit *Create(const Init *R, const std::string &FN);
+  static const FieldInit *Create(const Init *R, const Init *FN);
+
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit);
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt);
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const;
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const;
 
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 
   virtual std::string getAsString() const {
     return Rec->getAsString() + "." + FieldName;
@@ -1100,14 +1419,14 @@ public:
 /// argument can have a name associated with it.
 ///
 class DagInit : public TypedInit {
-  Init *Val;
+  const Init *Val;
   std::string ValName;
-  std::vector<Init*> Args;
+  std::vector<const Init*> Args;
   std::vector<std::string> ArgNames;
-public:
-  DagInit(Init *V, std::string VN,
-          const std::vector<std::pair<Init*, std::string> > &args)
-    : TypedInit(new DagRecTy), Val(V), ValName(VN) {
+
+  DagInit(const FoldingSetNodeID &ID, const Init *V, const std::string &VN,
+          const std::vector<std::pair<const Init*, std::string> > &args)
+      : TypedInit(ID, new DagRecTy), Val(V), ValName(VN) {
     Args.reserve(args.size());
     ArgNames.reserve(args.size());
     for (unsigned i = 0, e = args.size(); i != e; ++i) {
@@ -1115,21 +1434,33 @@ public:
       ArgNames.push_back(args[i].second);
     }
   }
-  DagInit(Init *V, std::string VN, const std::vector<Init*> &args,
+  DagInit(const FoldingSetNodeID &ID, const Init *V, const std::string &VN,
+          const std::vector<const Init*> &args,
           const std::vector<std::string> &argNames)
-    : TypedInit(new DagRecTy), Val(V), ValName(VN), Args(args),
+      : TypedInit(ID, new DagRecTy), Val(V), ValName(VN), Args(args),
       ArgNames(argNames) { }
 
-  virtual Init *convertInitializerTo(RecTy *Ty) {
+  DagInit(const DagInit &Other);  // Do not define.
+  DagInit &operator=(const DagInit &Other);  // Do not define.
+
+public:
+  static const DagInit *Create(const Init *V, const std::string &VN,
+                               const std::vector<
+                                 std::pair<const Init*, std::string> > &args);
+  static const DagInit *Create(const Init *V, const std::string &VN,
+                               const std::vector<const Init*> &args,
+                               const std::vector<std::string> &argNames);
+
+  virtual const Init *convertInitializerTo(RecTy *Ty) const {
     return Ty->convertValue(this);
   }
 
-  Init *getOperator() const { return Val; }
+  const Init *getOperator() const { return Val; }
 
   const std::string &getName() const { return ValName; }
 
   unsigned getNumArgs() const { return Args.size(); }
-  Init *getArg(unsigned Num) const {
+  const Init *getArg(unsigned Num) const {
     assert(Num < Args.size() && "Arg number out of range!");
     return Args[Num];
   }
@@ -1138,17 +1469,18 @@ public:
     return ArgNames[Num];
   }
 
-  void setArg(unsigned Num, Init *I) {
+  void setArg(unsigned Num, const Init *I) {
     assert(Num < Args.size() && "Arg number out of range!");
     Args[Num] = I;
   }
 
-  virtual Init *resolveReferences(Record &R, const RecordVal *RV);
+  virtual const Init *resolveReferences(Record &R,
+                                        const RecordVal *RV) const;
 
   virtual std::string getAsString() const;
 
-  typedef std::vector<Init*>::iterator             arg_iterator;
-  typedef std::vector<Init*>::const_iterator       const_arg_iterator;
+  typedef std::vector<const Init*>::iterator             arg_iterator;
+  typedef std::vector<const Init*>::const_iterator       const_arg_iterator;
   typedef std::vector<std::string>::iterator       name_iterator;
   typedef std::vector<std::string>::const_iterator const_name_iterator;
 
@@ -1168,14 +1500,15 @@ public:
   inline size_t              name_size () const { return ArgNames.size();  }
   inline bool                name_empty() const { return ArgNames.empty(); }
 
-  virtual Init *resolveBitReference(Record &R, const RecordVal *RV,
-                                    unsigned Bit) {
+  virtual const Init *resolveBitReference(Record &R, const RecordVal *RV,
+                                          unsigned Bit) const {
     assert(0 && "Illegal bit reference off dag");
     return 0;
   }
 
-  virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
-                                            unsigned Elt) {
+  virtual const Init *resolveListElementReference(Record &R,
+                                                  const RecordVal *RV,
+                                                  unsigned Elt) const {
     assert(0 && "Illegal element reference off dag");
     return 0;
   }
@@ -1189,7 +1522,7 @@ class RecordVal {
   std::string Name;
   RecTy *Ty;
   unsigned Prefix;
-  Init *Value;
+  const Init *Value;
 public:
   RecordVal(const std::string &N, RecTy *T, unsigned P);
 
@@ -1197,9 +1530,9 @@ public:
 
   unsigned getPrefix() const { return Prefix; }
   RecTy *getType() const { return Ty; }
-  Init *getValue() const { return Value; }
+  const Init *getValue() const { return Value; }
 
-  bool setValue(Init *V) {
+  bool setValue(const Init *V) {
     if (V) {
       Value = V->convertInitializerTo(Ty);
       return Value == 0;
@@ -1227,10 +1560,15 @@ class Record {
   std::vector<std::string> TemplateArgs;
   std::vector<RecordVal> Values;
   std::vector<Record*> SuperClasses;
+
+  // Tracks Record instances. Not owned by Record.
+  RecordKeeper &TrackedRecords;
+
 public:
 
-  explicit Record(const std::string &N, SMLoc loc) :
-    ID(LastID++), Name(N), Loc(loc) {}
+  // Constructs a record.
+  explicit Record(const std::string &N, SMLoc loc, RecordKeeper &records) :
+    ID(LastID++), Name(N), Loc(loc), TrackedRecords(records) {}
   ~Record() {}
 
 
@@ -1315,6 +1653,10 @@ public:
   /// possible references.
   void resolveReferencesTo(const RecordVal *RV);
 
+  RecordKeeper &getRecords() const {
+    return TrackedRecords;
+  }
+
   void dump() const;
 
   //===--------------------------------------------------------------------===//
@@ -1324,7 +1666,7 @@ public:
   /// getValueInit - Return the initializer for a value with the specified name,
   /// or throw an exception if the field does not exist.
   ///
-  Init *getValueInit(StringRef FieldName) const;
+  const Init *getValueInit(StringRef FieldName) const;
 
   /// getValueAsString - This method looks up the specified field and returns
   /// its value as a string, throwing an exception if the field does not exist
@@ -1336,13 +1678,13 @@ public:
   /// its value as a BitsInit, throwing an exception if the field does not exist
   /// or if the value is not the right type.
   ///
-  BitsInit *getValueAsBitsInit(StringRef FieldName) const;
+  const BitsInit *getValueAsBitsInit(StringRef FieldName) const;
 
   /// getValueAsListInit - This method looks up the specified field and returns
   /// its value as a ListInit, throwing an exception if the field does not exist
   /// or if the value is not the right type.
   ///
-  ListInit *getValueAsListInit(StringRef FieldName) const;
+  const ListInit *getValueAsListInit(StringRef FieldName) const;
 
   /// getValueAsListOfDefs - This method looks up the specified field and
   /// returns its value as a vector of records, throwing an exception if the
@@ -1356,6 +1698,12 @@ public:
   ///
   std::vector<int64_t> getValueAsListOfInts(StringRef FieldName) const;
 
+  /// getValueAsListOfStrings - This method looks up the specified field and
+  /// returns its value as a vector of strings, throwing an exception if the
+  /// field does not exist or if the value is not the right type.
+  ///
+  std::vector<std::string> getValueAsListOfStrings(StringRef FieldName) const;
+
   /// getValueAsDef - This method looks up the specified field and returns its
   /// value as a Record, throwing an exception if the field does not exist or if
   /// the value is not the right type.
@@ -1378,7 +1726,7 @@ public:
   /// value as an Dag, throwing an exception if the field does not exist or if
   /// the value is not the right type.
   ///
-  DagInit *getValueAsDag(StringRef FieldName) const;
+  const DagInit *getValueAsDag(StringRef FieldName) const;
 
   /// getValueAsCode - This method looks up the specified field and returns
   /// its value as the string data in a CodeInit, throwing an exception if the
@@ -1396,7 +1744,8 @@ struct MultiClass {
 
   void dump() const;
 
-  MultiClass(const std::string &Name, SMLoc Loc) : Rec(Name, Loc) {}
+  MultiClass(const std::string &Name, SMLoc Loc, RecordKeeper &Records) : 
+    Rec(Name, Loc, Records) {}
 };
 
 class RecordKeeper {
@@ -1453,7 +1802,6 @@ public:
   std::vector<Record*>
   getAllDerivedDefinitions(const std::string &ClassName) const;
 
-
   void dump() const;
 };
 
@@ -1474,24 +1822,8 @@ struct LessRecordFieldName {
   }
 };
 
-
-class TGError {
-  SMLoc Loc;
-  std::string Message;
-public:
-  TGError(SMLoc loc, const std::string &message) : Loc(loc), Message(message) {}
-
-  SMLoc getLoc() const { return Loc; }
-  const std::string &getMessage() const { return Message; }
-};
-
-
 raw_ostream &operator<<(raw_ostream &OS, const RecordKeeper &RK);
 
-extern RecordKeeper Records;
-
-void PrintError(SMLoc ErrorLoc, const Twine &Msg);
-
 } // End llvm namespace
 
 #endif