X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FType.cpp;h=e4a0dcae7655355b856fc33e36c1d5924d8a3a0e;hb=95586b8c833aeca112907e69f545a6ea6e2103ff;hp=647bad09f7ad05e7d60faf605925a9de936f4bab;hpb=3f59b7e933f920f82d02b1a413b17865152cf393;p=oota-llvm.git

diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp
index 647bad09f7a..e4a0dcae765 100644
--- a/lib/VMCore/Type.cpp
+++ b/lib/VMCore/Type.cpp
@@ -6,9 +6,11 @@
 
 #include "llvm/DerivedTypes.h"
 #include "llvm/SymbolTable.h"
+#include "llvm/Constants.h"
 #include "Support/StringExtras.h"
 #include "Support/STLExtras.h"
 #include <iostream>
+#include <algorithm>
 
 using std::vector;
 using std::string;
@@ -36,6 +38,7 @@ void PATypeHolder::dump() const {
   cerr << "PATypeHolder(" << (void*)this << ")\n";
 }
 
+
 Type::Type(const string &name, PrimitiveID id)
   : Value(Type::TypeTy, Value::TypeVal) {
   setDescription(name);
@@ -84,8 +87,8 @@ const Type *Type::getPrimitiveType(PrimitiveID IDNumber) {
 //
 bool Type::isLosslesslyConvertableTo(const Type *Ty) const {
   if (this == Ty) return true;
-  if ((!isPrimitiveType()   && !isPointerType()) ||
-      (!Ty->isPointerType() && !Ty->isPrimitiveType())) return false;
+  if ((!isPrimitiveType()    && !isa<PointerType>(this)) ||
+      (!isa<PointerType>(Ty) && !Ty->isPrimitiveType())) return false;
 
   if (getPrimitiveID() == Ty->getPrimitiveID())
     return true;  // Handles identity cast, and cast of differing pointer types
@@ -101,13 +104,24 @@ bool Type::isLosslesslyConvertableTo(const Type *Ty) const {
   case Type::ULongTyID:
   case Type::LongTyID:
   case Type::PointerTyID:
-    return Ty == Type::ULongTy || Ty == Type::LongTy ||
-           Ty->getPrimitiveID() == Type::PointerTyID;
+    return Ty == Type::ULongTy || Ty == Type::LongTy || isa<PointerType>(Ty);
   default:
     return false;  // Other types have no identity values
   }
 }
 
+// getPrimitiveSize - Return the basic size of this type if it is a primative
+// type.  These are fixed by LLVM and are not target dependant.  This will
+// return zero if the type does not have a size or is not a primitive type.
+//
+unsigned Type::getPrimitiveSize() const {
+  switch (getPrimitiveID()) {
+#define HANDLE_PRIM_TYPE(TY,SIZE)  case TY##TyID: return SIZE;
+#include "llvm/Type.def"
+  default: return 0;
+  }
+}
+
 
 bool StructType::indexValid(const Value *V) const {
   if (!isa<Constant>(V)) return false;
@@ -414,11 +428,10 @@ class TypeMap : public AbstractTypeUser {
   typedef map<ValType, PATypeHandle<TypeClass> > MapTy;
   MapTy Map;
 public:
-
   ~TypeMap() { print("ON EXIT"); }
 
   inline TypeClass *get(const ValType &V) {
-    map<ValType, PATypeHandle<TypeClass> >::iterator I = Map.find(V);
+    typename map<ValType, PATypeHandle<TypeClass> >::iterator I = Map.find(V);
     // TODO: FIXME: When Types are not CONST.
     return (I != Map.end()) ? (TypeClass*)I->second.get() : 0;
   }
@@ -432,7 +445,7 @@ public:
   // structurally equivalent to the specified type.
   //
   inline const TypeClass *containsEquivalent(const TypeClass *Ty) {
-    for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
+    for (typename MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
       if (I->second.get() != Ty && TypesEqual(Ty, I->second.get()))
 	return (TypeClass*)I->second.get();  // FIXME TODO when types not const
     return 0;
@@ -444,32 +457,22 @@ public:
   // corrected.
   //
   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
-    if (OldTy == NewTy) {
-      if (!OldTy->isAbstract()) {
-        // Check to see if the type just became concrete.
-        // If so, remove self from user list.
-        for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
-          if (I->second == OldTy)
-            I->second.removeUserFromConcrete();
-      }
-      return;
-    }
 #ifdef DEBUG_MERGE_TYPES
     cerr << "Removing Old type from Tab: " << (void*)OldTy << ", "
 	 << OldTy->getDescription() << "  replacement == " << (void*)NewTy
 	 << ", " << NewTy->getDescription() << endl;
 #endif
-    for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
+    for (typename MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
       if (I->second == OldTy) {
-	Map.erase(I);
-	print("refineAbstractType after");
-	return;
+        // Check to see if the type just became concrete.  If so, remove self
+        // from user list.
+        I->second.removeUserFromConcrete();
+        I->second = cast<TypeClass>(NewTy);
       }
-    assert(0 && "Abstract type not found in table!");
   }
 
   void remove(const ValType &OldVal) {
-    MapTy::iterator I = Map.find(OldVal);
+    typename MapTy::iterator I = Map.find(OldVal);
     assert(I != Map.end() && "TypeMap::remove, element not found!");
     Map.erase(I);
   }
@@ -508,21 +511,22 @@ protected:
   virtual void typeBecameConcrete(const DerivedType *Ty) = 0;
   
   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
-    if (OldTy == NewTy) {
-      if (!OldTy->isAbstract())
-        typeBecameConcrete(OldTy);
-      return;
-    }
+    assert(OldTy == NewTy || OldTy->isAbstract());
+
+    if (!OldTy->isAbstract())
+      typeBecameConcrete(OldTy);
+
     TypeMap<ValType, TypeClass> &Table = MyTable;     // Copy MyTable reference
     ValType Tmp(*(ValType*)this);                     // Copy this.
     PATypeHandle<TypeClass> OldType(Table.get(*(ValType*)this), this);
     Table.remove(*(ValType*)this);                    // Destroy's this!
-#if 1
+
     // Refine temporary to new state...
-    Tmp.doRefinement(OldTy, NewTy); 
+    if (OldTy != NewTy)
+      Tmp.doRefinement(OldTy, NewTy); 
 
+    // FIXME: when types are not const!
     Table.add((ValType&)Tmp, (TypeClass*)OldType.get());
-#endif
   }
 
   void dump() const {
@@ -565,7 +569,7 @@ public:
   // Subclass should override this... to update self as usual
   virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
     if (RetTy == OldType) RetTy = NewType;
-    for (unsigned i = 0; i < ArgTypes.size(); ++i)
+    for (unsigned i = 0, e = ArgTypes.size(); i != e; ++i)
       if (ArgTypes[i] == OldType) ArgTypes[i] = NewType;
   }
 
@@ -623,7 +627,8 @@ public:
 
   // Subclass should override this... to update self as usual
   virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
-    if (ValTy == OldType) ValTy = NewType;
+    assert(ValTy == OldType);
+    ValTy = NewType;
   }
 
   virtual void typeBecameConcrete(const DerivedType *Ty) {
@@ -668,7 +673,8 @@ public:
   StructValType(const vector<const Type*> &args,
 		TypeMap<StructValType, StructType> &Tab)
     : ValTypeBase<StructValType, StructType>(Tab) {
-    for (unsigned i = 0; i < args.size(); ++i)
+    ElTypes.reserve(args.size());
+    for (unsigned i = 0, e = args.size(); i != e; ++i)
       ElTypes.push_back(PATypeHandle<Type>(args[i], this));
   }
 
@@ -678,7 +684,7 @@ public:
   StructValType(const StructValType &SVT) 
     : ValTypeBase<StructValType, StructType>(SVT){
     ElTypes.reserve(SVT.ElTypes.size());
-    for (unsigned i = 0; i < SVT.ElTypes.size(); ++i)
+    for (unsigned i = 0, e = SVT.ElTypes.size(); i != e; ++i)
       ElTypes.push_back(PATypeHandle<Type>(SVT.ElTypes[i], this));
   }
 
@@ -689,8 +695,9 @@ public:
   }
 
   virtual void typeBecameConcrete(const DerivedType *Ty) {
-    for (unsigned i = 0; i < ElTypes.size(); ++i)
-      if (ElTypes[i] == Ty) ElTypes[i].removeUserFromConcrete();
+    for (unsigned i = 0, e = ElTypes.size(); i != e; ++i)
+      if (ElTypes[i] == Ty)
+        ElTypes[i].removeUserFromConcrete();
   }
 
   inline bool operator<(const StructValType &STV) const {
@@ -734,7 +741,8 @@ public:
 
   // Subclass should override this... to update self as usual
   virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
-    if (ValTy == OldType) ValTy = NewType;
+    assert(ValTy == OldType);
+    ValTy = NewType;
   }
 
   virtual void typeBecameConcrete(const DerivedType *Ty) {
@@ -766,12 +774,32 @@ PointerType *PointerType::get(const Type *ValueType) {
   return PT;
 }
 
+void debug_type_tables() {
+  FunctionTypes.dump();
+  ArrayTypes.dump();
+  StructTypes.dump();
+  PointerTypes.dump();
+}
 
 
 //===----------------------------------------------------------------------===//
 //                     Derived Type Refinement Functions
 //===----------------------------------------------------------------------===//
 
+// addAbstractTypeUser - Notify an abstract type that there is a new user of
+// it.  This function is called primarily by the PATypeHandle class.
+//
+void DerivedType::addAbstractTypeUser(AbstractTypeUser *U) const {
+  assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!");
+
+#if DEBUG_MERGE_TYPES
+  cerr << "  addAbstractTypeUser[" << (void*)this << ", " << getDescription() 
+       << "][" << AbstractTypeUsers.size() << "] User = " << U << endl;
+#endif
+  AbstractTypeUsers.push_back(U);
+}
+
+
 // removeAbstractTypeUser - Notify an abstract type that a user of the class
 // no longer has a handle to the type.  This function is called primarily by
 // the PATypeHandle class.  When there are no users of the abstract type, it
@@ -861,10 +889,9 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) {
 #endif
       User->refineAbstractType(this, NewTy);
 
-      if (AbstractTypeUsers.size() == OldSize)
-        User->refineAbstractType(this, NewTy);
-
+#ifdef DEBUG_MERGE_TYPES
       if (AbstractTypeUsers.size() == OldSize) {
+        User->refineAbstractType(this, NewTy);
         if (AbstractTypeUsers.back() != User)
           cerr << "User changed!\n";
         cerr << "Top of user list is:\n";
@@ -873,7 +900,7 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) {
         cerr <<"\nOld User=\n";
         User->dump();
       }
-
+#endif
       assert(AbstractTypeUsers.size() != OldSize &&
 	     "AbsTyUser did not remove self from user list!");
     }
@@ -898,20 +925,40 @@ void DerivedType::typeIsRefined() {
   ++isRefining;
 
 #ifdef DEBUG_MERGE_TYPES
-  cerr << "typeIsREFINED type: " << (void*)this <<" "<<getDescription() << endl;
+  cerr << "typeIsREFINED type: " << (void*)this <<" "<<getDescription() << "\n";
 #endif
-  for (unsigned i = 0; i < AbstractTypeUsers.size(); ) {
-    AbstractTypeUser *ATU = AbstractTypeUsers[i];
+
+  // In this loop we have to be very careful not to get into infinite loops and
+  // other problem cases.  Specifically, we loop through all of the abstract
+  // type users in the user list, notifying them that the type has been refined.
+  // At their choice, they may or may not choose to remove themselves from the
+  // list of users.  Regardless of whether they do or not, we have to be sure
+  // that we only notify each user exactly once.  Because the refineAbstractType
+  // method can cause an arbitrary permutation to the user list, we cannot loop
+  // through it in any particular order and be guaranteed that we will be
+  // successful at this aim.  Because of this, we keep track of all the users we
+  // have visited and only visit users we have not seen.  Because this user list
+  // should be small, we use a vector instead of a full featured set to keep
+  // track of what users we have notified so far.
+  //
+  vector<AbstractTypeUser*> Refined;
+  while (1) {
+    unsigned i;
+    for (i = AbstractTypeUsers.size(); i != 0; --i)
+      if (find(Refined.begin(), Refined.end(), AbstractTypeUsers[i-1]) ==
+          Refined.end())
+        break;    // Found an unrefined user?
+    
+    if (i == 0) break;  // Noone to refine left, break out of here!
+
+    AbstractTypeUser *ATU = AbstractTypeUsers[--i];
+    Refined.push_back(ATU);  // Keep track of which users we have refined!
+
 #ifdef DEBUG_MERGE_TYPES
-    cerr << " typeIsREFINED user " << i << " of abstract type ["
+    cerr << " typeIsREFINED user " << i << "[" << ATU << "] of abstract type ["
 	 << (void*)this << " " << getDescription() << "]\n";
 #endif
     ATU->refineAbstractType(this, this);
-    
-    // If the user didn't remove itself from the list, continue...
-    if (AbstractTypeUsers.size() > i && AbstractTypeUsers[i] == ATU) {
-      ++i;
-    }
   }
 
   --isRefining;
@@ -921,7 +968,9 @@ void DerivedType::typeIsRefined() {
     for (unsigned i = 0; i < AbstractTypeUsers.size(); ++i) {
       if (AbstractTypeUsers[i] != this) {
         // Debugging hook
-        cerr << "FOUND FAILURE\n";
+        cerr << "FOUND FAILURE\nUser: ";
+        AbstractTypeUsers[i]->dump();
+        cerr << "\nCatch:\n";
         AbstractTypeUsers[i]->refineAbstractType(this, this);
         assert(0 && "Type became concrete,"
                " but it still has abstract type users hanging around!");
@@ -944,19 +993,16 @@ void FunctionType::refineAbstractType(const DerivedType *OldType,
        << OldType->getDescription() << "], " << (void*)NewType << " [" 
        << NewType->getDescription() << "])\n";
 #endif
-
-  if (!OldType->isAbstract()) {
-    if (ResultType == OldType) ResultType.removeUserFromConcrete();
-    for (unsigned i = 0; i < ParamTys.size(); ++i)
-      if (ParamTys[i] == OldType) ParamTys[i].removeUserFromConcrete();
-  }
-
-  if (OldType != NewType) {
-    if (ResultType == OldType) ResultType = NewType;
-
-    for (unsigned i = 0; i < ParamTys.size(); ++i)
-      if (ParamTys[i] == OldType) ParamTys[i] = NewType;
+  // Find the type element we are refining...
+  if (ResultType == OldType) {
+    ResultType.removeUserFromConcrete();
+    ResultType = NewType;
   }
+  for (unsigned i = 0, e = ParamTys.size(); i != e; ++i)
+    if (ParamTys[i] == OldType) {
+      ParamTys[i].removeUserFromConcrete();
+      ParamTys[i] = NewType;
+    }
 
   const FunctionType *MT = FunctionTypes.containsEquivalent(this);
   if (MT && MT != this) {
@@ -980,12 +1026,10 @@ void ArrayType::refineAbstractType(const DerivedType *OldType,
        << NewType->getDescription() << "])\n";
 #endif
 
-  if (!OldType->isAbstract()) {
-    assert(getElementType() == OldType);
-    ElementType.removeUserFromConcrete();
-  }
-
+  assert(getElementType() == OldType);
+  ElementType.removeUserFromConcrete();
   ElementType = NewType;
+
   const ArrayType *AT = ArrayTypes.containsEquivalent(this);
   if (AT && AT != this) {
     refineAbstractTypeTo(AT);          // Different type altogether...
@@ -1007,18 +1051,13 @@ void StructType::refineAbstractType(const DerivedType *OldType,
        << OldType->getDescription() << "], " << (void*)NewType << " [" 
        << NewType->getDescription() << "])\n";
 #endif
-  if (!OldType->isAbstract()) {
-    for (unsigned i = 0; i < ETypes.size(); ++i)
-      if (ETypes[i] == OldType)
-        ETypes[i].removeUserFromConcrete();
-  }
+  for (unsigned i = 0, e = ETypes.size(); i != e; ++i)
+    if (ETypes[i] == OldType) {
+      ETypes[i].removeUserFromConcrete();
 
-  if (OldType != NewType) {
-    // Update old type to new type in the array...
-    for (unsigned i = 0; i < ETypes.size(); ++i)
-      if (ETypes[i] == OldType)
-        ETypes[i] = NewType;
-  } 
+      // Update old type to new type in the array...
+      ETypes[i] = NewType;
+    }
 
   const StructType *ST = StructTypes.containsEquivalent(this);
   if (ST && ST != this) {
@@ -1041,14 +1080,11 @@ void PointerType::refineAbstractType(const DerivedType *OldType,
        << NewType->getDescription() << "])\n";
 #endif
 
-  if (!OldType->isAbstract()) {
-    assert(ElementType == OldType);
-    ElementType.removeUserFromConcrete();
-  }
-
+  assert(ElementType == OldType);
+  ElementType.removeUserFromConcrete();
   ElementType = NewType;
-  const PointerType *PT = PointerTypes.containsEquivalent(this);
 
+  const PointerType *PT = PointerTypes.containsEquivalent(this);
   if (PT && PT != this) {
     refineAbstractTypeTo(PT);          // Different type altogether...
   } else {