From 1e6810005f426798ce2541c26f0cdc7a08670846 Mon Sep 17 00:00:00 2001 From: Will Dietz Date: Wed, 16 Oct 2013 04:10:06 +0000 Subject: TypeFinder: prefer iterative algorithm to keep stack usage low. Introduce subtype_reverse_iterator to maintain the numbering assigned during the recursive type walk. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192770 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/IR/TypeFinder.cpp | 28 ++++++++++++++++++---------- 1 file changed, 18 insertions(+), 10 deletions(-) (limited to 'lib/IR') diff --git a/lib/IR/TypeFinder.cpp b/lib/IR/TypeFinder.cpp index dd933026ea..689b903891 100644 --- a/lib/IR/TypeFinder.cpp +++ b/lib/IR/TypeFinder.cpp @@ -94,19 +94,27 @@ void TypeFinder::clear() { /// incorporateType - This method adds the type to the list of used structures /// if it's not in there already. void TypeFinder::incorporateType(Type *Ty) { - // Check to see if we're already visited this type. + // Check to see if we've already visited this type. if (!VisitedTypes.insert(Ty).second) return; - // If this is a structure or opaque type, add a name for the type. - if (StructType *STy = dyn_cast(Ty)) - if (!OnlyNamed || STy->hasName()) - StructTypes.push_back(STy); - - // Recursively walk all contained types. - for (Type::subtype_iterator I = Ty->subtype_begin(), - E = Ty->subtype_end(); I != E; ++I) - incorporateType(*I); + SmallVector TypeWorklist; + TypeWorklist.push_back(Ty); + do { + Ty = TypeWorklist.pop_back_val(); + + // If this is a structure or opaque type, add a name for the type. + if (StructType *STy = dyn_cast(Ty)) + if (!OnlyNamed || STy->hasName()) + StructTypes.push_back(STy); + + // Add all unvisited subtypes to worklist for processing + for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(), + E = Ty->subtype_rend(); + I != E; ++I) + if (VisitedTypes.insert(*I).second) + TypeWorklist.push_back(*I); + } while (!TypeWorklist.empty()); } /// incorporateValue - This method is used to walk operand lists finding types -- cgit v1.2.3