aboutsummaryrefslogtreecommitdiffstats
path: root/lib/VMCore
diff options
context:
space:
mode:
authorChris Lattner <sabre@nondot.org>2004-10-06 16:36:46 +0000
committerChris Lattner <sabre@nondot.org>2004-10-06 16:36:46 +0000
commitb5c16705fdf778f5f1dfbfdf67218932f1d8ca7d (patch)
tree9d64f5fe226cdaffe56a443e3a80a058f76bc719 /lib/VMCore
parentdf00115aa4ee3fd400cc32889a353a461a471daa (diff)
downloadexternal_llvm-b5c16705fdf778f5f1dfbfdf67218932f1d8ca7d.zip
external_llvm-b5c16705fdf778f5f1dfbfdf67218932f1d8ca7d.tar.gz
external_llvm-b5c16705fdf778f5f1dfbfdf67218932f1d8ca7d.tar.bz2
Change Type::isAbstract to have better comments, a more correct name
(PromoteAbstractToConcrete), and to use a set to avoid recomputation. In particular, this set eliminates the potentially exponential cases from this little recursive algorithm. On a particularly nasty testcase, llvm-dis on the .bc file went from 34 minutes (which is when I killed it, it still hadn't finished) to 0.57s. Remember kids, exponential algorithms are bad. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16772 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore')
-rw-r--r--lib/VMCore/Type.cpp31
1 files changed, 19 insertions, 12 deletions
diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp
index 0c76d16..af3a81e 100644
--- a/lib/VMCore/Type.cpp
+++ b/lib/VMCore/Type.cpp
@@ -443,19 +443,26 @@ void DerivedType::dropAllTypeUses() {
}
}
-// isTypeAbstract - This is a recursive function that walks a type hierarchy
-// calculating whether or not a type is abstract. Worst case it will have to do
-// a lot of traversing if you have some whacko opaque types, but in most cases,
-// it will do some simple stuff when it hits non-abstract types that aren't
-// recursive.
+// PromoteAbstractToConcrete - This is a recursive function that walks a type
+// graph calculating whether or not a type is abstract.
//
-bool Type::isTypeAbstract() {
+// This method returns true if the type is found to still be abstract.
+//
+bool Type::PromoteAbstractToConcrete(void *Ptr) {
if (!isAbstract()) // Base case for the recursion
return false; // Primitive = leaf type
if (isa<OpaqueType>(this)) // Base case for the recursion
return true; // This whole type is abstract!
+ /// KnownAbstractTypes - This set contains all of the types that we know for
+ /// sure are abstract. Once we discover that a type really is abstract, we
+ /// remember this so we don't have to do potentially exponential amounts of
+ /// checking in some cases.
+ std::set<Type*> &KnownAbstractTypes = *(std::set<Type*>*)Ptr;
+ if (KnownAbstractTypes.count(this))
+ return true; // We already know this type is abstract!
+
// We have to guard against recursion. To do this, we temporarily mark this
// type as concrete, so that if we get back to here recursively we will think
// it's not abstract, and thus not scan it again.
@@ -465,15 +472,14 @@ bool Type::isTypeAbstract() {
// one!
for (Type::subtype_iterator I = subtype_begin(), E = subtype_end();
I != E; ++I)
- if (const_cast<Type*>(I->get())->isTypeAbstract()) {
+ if (const_cast<Type*>(I->get())->PromoteAbstractToConcrete(Ptr)) {
+ KnownAbstractTypes.insert(this);
setAbstract(true); // Restore the abstract bit.
return true; // This type is abstract if subtype is abstract!
}
- // Restore the abstract bit.
- setAbstract(true);
-
- // Nothing looks abstract here...
+ // Nothing looks abstract here.
+ setAbstract(false);
return false;
}
@@ -725,7 +731,8 @@ public:
// If the type is currently thought to be abstract, rescan all of our
// subtypes to see if the type has just become concrete!
if (Ty->isAbstract()) {
- Ty->setAbstract(Ty->isTypeAbstract());
+ std::set<Type*> KnownAbstractTypes;
+ Ty->PromoteAbstractToConcrete(&KnownAbstractTypes);
// If the type just became concrete, notify all users!
if (!Ty->isAbstract())