Move the "findUsedStructTypes" functionality outside of the Module class.

The "findUsedStructTypes" method is very expensive to run. It needs to be
optimized so that LTO can run faster. Splitting this method out of the Module
class will help this occur. For instance, it can keep a list of seen objects so
that it doesn't process them over and over again.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161228 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 78 insertions, 5 deletions

diff --git a/include/llvm/Module.h b/include/llvm/Module.h
index cb7c1dc36a..e6303ac775 100644
--- a/include/llvm/Module.h
+++ b/include/llvm/Module.h
@@ -301,11 +301,6 @@ public:
   typedef DenseMap<StructType*, unsigned, DenseMapInfo<StructType*> >
                    NumeredTypesMapTy;
 
-  /// findUsedStructTypes - Walk the entire module and find all of the
-  /// struct types that are in use, returning them in a vector.
-  void findUsedStructTypes(std::vector<StructType*> &StructTypes,
-                           bool OnlyNamed = false) const;
-  
   /// getTypeByName - Return the type with the specified name, or null if there
   /// is none by that name.
   StructType *getTypeByName(StringRef Name) const;
diff --git a/include/llvm/TypeFinder.h b/include/llvm/TypeFinder.h
new file mode 100644
index 0000000000..5d807057a3
--- /dev/null
+++ b/include/llvm/TypeFinder.h
@@ -0,0 +1,78 @@
+//===-- llvm/TypeFinder.h - Class for finding used struct types -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the declaration of the TypeFinder class. 
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TYPEFINDER_H
+#define LLVM_TYPEFINDER_H
+
+#include "llvm/ADT/DenseSet.h"
+#include <vector>
+
+namespace llvm {
+
+class MDNode;
+class Module;
+class StructType;
+class Type;
+class Value;
+
+/// TypeFinder - Walk over a module, identifying all of the types that are
+/// used by the module.
+class TypeFinder {
+  // To avoid walking constant expressions multiple times and other IR
+  // objects, we keep several helper maps.
+  DenseSet<const Value*> VisitedConstants;
+  DenseSet<Type*> VisitedTypes;
+
+  std::vector<StructType*> StructTypes;
+  bool OnlyNamed;
+
+public:
+  TypeFinder() : OnlyNamed(false) {}
+
+  void run(const Module &M, bool onlyNamed);
+  void clear();
+
+  typedef std::vector<StructType*>::iterator iterator;
+  typedef std::vector<StructType*>::const_iterator const_iterator;
+
+  iterator begin() { return StructTypes.begin(); }
+  iterator end() { return StructTypes.end(); }
+
+  const_iterator begin() const { return StructTypes.begin(); }
+  const_iterator end() const { return StructTypes.end(); }
+
+  bool empty() const { return StructTypes.empty(); }
+  size_t size() const { return StructTypes.size(); }
+  iterator erase(iterator I, iterator E) { return StructTypes.erase(I, E); }
+
+  StructType *&operator[](unsigned Idx) { return StructTypes[Idx]; }
+
+private:
+  /// incorporateType - This method adds the type to the list of used
+  /// structures if it's not in there already.
+  void incorporateType(Type *Ty);
+
+  /// incorporateValue - This method is used to walk operand lists finding types
+  /// hiding in constant expressions and other operands that won't be walked in
+  /// other ways.  GlobalValues, basic blocks, instructions, and inst operands
+  /// are all explicitly enumerated.
+  void incorporateValue(const Value *V);
+
+  /// incorporateMDNode - This method is used to walk the operands of an MDNode
+  /// to find types hiding within.
+  void incorporateMDNode(const MDNode *V);
+};
+
+} // end llvm namespace
+
+#endif