Create a new #include "Support/..." directory structure to move things

from "llvm/Support/..." that are not llvm dependant.

Move files and fix #includes


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

30 files changed, 1613 insertions, 43 deletions

diff --git a/include/Support/CommandLine.h b/include/Support/CommandLine.h
new file mode 100644
index 0000000000..84a3bc9b59
--- /dev/null
+++ b/include/Support/CommandLine.h
@@ -0,0 +1,399 @@
+//===- Support/CommandLine.h - Flexible Command line parser ------*- C++ -*--=//
+//
+// This class implements a command line argument processor that is useful when
+// creating a tool.  It provides a simple, minimalistic interface that is easily
+// extensible and supports nonlocal (library) command line options.
+//
+// Note that rather than trying to figure out what this code does, you could try
+// reading the library documentation located in docs/CommandLine.html
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_COMMANDLINE_H
+#define LLVM_SUPPORT_COMMANDLINE_H
+
+#include <string>
+#include <vector>
+#include <utility>
+#include <stdarg.h>
+
+namespace cl {   // Short namespace to make usage concise
+
+//===----------------------------------------------------------------------===//
+// ParseCommandLineOptions - Minimalistic command line option processing entry
+//
+void cl::ParseCommandLineOptions(int &argc, char **argv,
+				 const char *Overview = 0,
+				 int Flags = 0);
+
+// ParserOptions - This set of option is use to control global behavior of the
+// command line processor.
+//
+enum ParserOptions {
+  // DisableSingleLetterArgGrouping - With this option enabled, multiple letter
+  // options are allowed to bunch together with only a single hyphen for the
+  // whole group.  This allows emulation of the behavior that ls uses for
+  // example:  ls -la === ls -l -a    Providing this option, disables this.
+  //
+  DisableSingleLetterArgGrouping = 0x0001,
+
+  // EnableSingleLetterArgValue - This option allows arguments that are
+  // otherwise unrecognized to match single letter flags that take a value. 
+  // This is useful for cases like a linker, where options are typically of the
+  // form '-lfoo' or '-L../../include' where -l or -L are the actual flags.
+  //
+  EnableSingleLetterArgValue     = 0x0002,
+};
+
+
+//===----------------------------------------------------------------------===//
+// Global flags permitted to be passed to command line arguments
+
+enum FlagsOptions {
+  NoFlags         = 0x00,      // Marker to make explicit that we have no flags
+  Default         = 0x00,      // Equally, marker to use the default flags
+
+  GlobalsMask     = 0x80, 
+};
+
+enum NumOccurances {           // Flags for the number of occurances allowed...
+  Optional        = 0x01,      // Zero or One occurance
+  ZeroOrMore      = 0x02,      // Zero or more occurances allowed
+  Required        = 0x03,      // One occurance required
+  OneOrMore       = 0x04,      // One or more occurances required
+
+  // ConsumeAfter - Marker for a null ("") flag that can be used to indicate
+  // that anything that matches the null marker starts a sequence of options
+  // that all get sent to the null marker.  Thus, for example, all arguments
+  // to LLI are processed until a filename is found.  Once a filename is found,
+  // all of the succeeding arguments are passed, unprocessed, to the null flag.
+  //
+  ConsumeAfter    = 0x05,
+
+  OccurancesMask  = 0x07,
+};
+
+enum ValueExpected {           // Is a value required for the option?
+  ValueOptional   = 0x08,      // The value can oppear... or not
+  ValueRequired   = 0x10,      // The value is required to appear!
+  ValueDisallowed = 0x18,      // A value may not be specified (for flags)
+  ValueMask       = 0x18,
+};
+
+enum OptionHidden {            // Control whether -help shows this option
+  NotHidden       = 0x20,      // Option included in --help & --help-hidden
+  Hidden          = 0x40,      // -help doesn't, but --help-hidden does
+  ReallyHidden    = 0x60,      // Neither --help nor --help-hidden show this arg
+  HiddenMask      = 0x60,
+};
+
+
+//===----------------------------------------------------------------------===//
+// Option Base class
+//
+class Alias;
+class Option {
+  friend void cl::ParseCommandLineOptions(int &, char **, const char *, int);
+  friend class Alias;
+
+  // handleOccurances - Overriden by subclasses to handle the value passed into
+  // an argument.  Should return true if there was an error processing the
+  // argument and the program should exit.
+  //
+  virtual bool handleOccurance(const char *ArgName, const string &Arg) = 0;
+
+  virtual enum NumOccurances getNumOccurancesFlagDefault() const { 
+    return Optional;
+  }
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueOptional; 
+  }
+  virtual enum OptionHidden getOptionHiddenFlagDefault() const {
+    return NotHidden;
+  }
+
+  int NumOccurances;          // The number of times specified
+  const int Flags;            // Flags for the argument
+public:
+  const char * const ArgStr;  // The argument string itself (ex: "help", "o")
+  const char * const HelpStr; // The descriptive text message for --help
+
+  inline enum NumOccurances getNumOccurancesFlag() const {
+    int NO = Flags & OccurancesMask;
+    return NO ? (enum NumOccurances)NO : getNumOccurancesFlagDefault();
+  }
+  inline enum ValueExpected getValueExpectedFlag() const {
+    int VE = Flags & ValueMask;
+    return VE ? (enum ValueExpected)VE : getValueExpectedFlagDefault();
+  }
+  inline enum OptionHidden getOptionHiddenFlag() const {
+    int OH = Flags & HiddenMask;
+    return OH ? (enum OptionHidden)OH : getOptionHiddenFlagDefault();
+  }
+
+protected:
+  Option(const char *ArgStr, const char *Message, int Flags);
+  Option(int flags) : NumOccurances(0), Flags(flags), ArgStr(""), HelpStr("") {}
+
+public:
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+
+  // addOccurance - Wrapper around handleOccurance that enforces Flags
+  //
+  bool addOccurance(const char *ArgName, const string &Value);
+
+  // Prints option name followed by message.  Always returns true.
+  bool error(string Message, const char *ArgName = 0);
+
+public:
+  inline int getNumOccurances() const { return NumOccurances; }
+  virtual ~Option() {}
+};
+
+
+//===----------------------------------------------------------------------===//
+// Aliased command line option (alias this name to a preexisting name)
+//
+class Alias : public Option {
+  Option &AliasFor;
+  virtual bool handleOccurance(const char *ArgName, const string &Arg) {
+    return AliasFor.handleOccurance(AliasFor.ArgStr, Arg);
+  }
+  virtual enum OptionHidden getOptionHiddenFlagDefault() const {return Hidden;}
+public:
+  inline Alias(const char *ArgStr, const char *Message, int Flags,
+	       Option &aliasFor) : Option(ArgStr, Message, Flags), 
+				   AliasFor(aliasFor) {}
+};
+
+//===----------------------------------------------------------------------===//
+// Boolean/flag command line option
+//
+class Flag : public Option {
+  bool Value;
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+public:
+  inline Flag(const char *ArgStr, const char *Message, int Flags = 0, 
+	      bool DefaultVal = 0) : Option(ArgStr, Message, Flags), 
+				     Value(DefaultVal) {}
+  operator const bool() const { return Value; }
+  inline bool operator=(bool Val) { Value = Val; return Val; }
+};
+
+
+
+//===----------------------------------------------------------------------===//
+// Integer valued command line option
+//
+class Int : public Option {
+  int Value;
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired; 
+  }
+public:
+  inline Int(const char *ArgStr, const char *Help, int Flags = 0,
+	     int DefaultVal = 0) : Option(ArgStr, Help, Flags),
+				   Value(DefaultVal) {}
+  inline operator int() const { return Value; }
+  inline int operator=(int Val) { Value = Val; return Val; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// String valued command line option
+//
+class String : public Option, public string {
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired; 
+  }
+public:
+  inline String(const char *ArgStr, const char *Help, int Flags = 0, 
+		const char *DefaultVal = "") 
+    : Option(ArgStr, Help, Flags), string(DefaultVal) {}
+
+  inline const string &operator=(const string &Val) { 
+    return string::operator=(Val);
+  }
+};
+
+
+//===----------------------------------------------------------------------===//
+// String list command line option
+//
+class StringList : public Option, public vector<string> {
+
+  virtual enum NumOccurances getNumOccurancesFlagDefault() const { 
+    return ZeroOrMore;
+  }
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired;
+  }
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+
+public:
+  inline StringList(const char *ArgStr, const char *Help, int Flags = 0)
+    : Option(ArgStr, Help, Flags) {}
+};
+
+
+//===----------------------------------------------------------------------===//
+// Enum valued command line option
+//
+#define clEnumVal(ENUMVAL, DESC) #ENUMVAL, ENUMVAL, DESC
+#define clEnumValN(ENUMVAL, FLAGNAME, DESC) FLAGNAME, ENUMVAL, DESC
+
+// EnumBase - Base class for all enum/varargs related argument types...
+class EnumBase : public Option {
+protected:
+  // Use a vector instead of a map, because the lists should be short,
+  // the overhead is less, and most importantly, it keeps them in the order
+  // inserted so we can print our option out nicely.
+  vector<pair<const char *, pair<int, const char *> > > ValueMap;
+
+  inline EnumBase(const char *ArgStr, const char *Help, int Flags)
+    : Option(ArgStr, Help, Flags) {}
+  inline EnumBase(int Flags) : Option(Flags) {}
+
+  // processValues - Incorporate the specifed varargs arglist into the 
+  // ValueMap.
+  //
+  void processValues(va_list Vals);
+
+  // registerArgs - notify the system about these new arguments
+  void registerArgs();
+
+public:
+  // Turn an enum into the arg name that activates it
+  const char *getArgName(int ID) const;
+  const char *getArgDescription(int ID) const;
+};
+
+class EnumValueBase : public EnumBase {
+protected:
+  int Value;
+  inline EnumValueBase(const char *ArgStr, const char *Help, int Flags)
+    : EnumBase(ArgStr, Help, Flags) {}
+  inline EnumValueBase(int Flags) : EnumBase(Flags) {}
+
+  // handleOccurance - Set Value to the enum value specified by Arg
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+};
+
+template <class E>  // The enum we are representing
+class Enum : public EnumValueBase {
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired;
+  }
+public:
+  inline Enum(const char *ArgStr, int Flags, const char *Help, ...)
+    : EnumValueBase(ArgStr, Help, Flags) {
+    va_list Values;
+    va_start(Values, Help);
+    processValues(Values);
+    va_end(Values);
+    Value = ValueMap.front().second.first; // Grab default value
+  }
+
+  inline operator E() const { return (E)Value; }
+  inline E operator=(E Val) { Value = Val; return Val; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// Enum flags command line option
+//
+class EnumFlagsBase : public EnumValueBase {
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueDisallowed;
+  }
+protected:
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+  inline EnumFlagsBase(int Flags) : EnumValueBase(Flags) {}
+
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+};
+
+template <class E>  // The enum we are representing
+class EnumFlags : public EnumFlagsBase {
+public:
+  inline EnumFlags(int Flags, ...) : EnumFlagsBase(Flags) {
+    va_list Values;
+    va_start(Values, Flags);
+    processValues(Values);
+    va_end(Values);
+    registerArgs();
+    Value = ValueMap.front().second.first; // Grab default value
+  }
+
+  inline operator E() const { return (E)Value; }
+  inline E operator=(E Val) { Value = Val; return Val; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// Enum list command line option
+//
+class EnumListBase : public EnumBase {
+  virtual enum NumOccurances getNumOccurancesFlagDefault() const { 
+    return ZeroOrMore;
+  }
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueDisallowed;
+  }
+protected:
+  vector<int> Values;  // The options specified so far.
+
+  inline EnumListBase(int Flags) 
+    : EnumBase(Flags) {}
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+public:
+  inline unsigned size() { return Values.size(); }
+};
+
+template <class E>  // The enum we are representing
+class EnumList : public EnumListBase {
+public:
+  inline EnumList(int Flags, ...) : EnumListBase(Flags) {
+    va_list Values;
+    va_start(Values, Flags);
+    processValues(Values);
+    va_end(Values);
+    registerArgs();
+  }
+  inline E  operator[](unsigned i) const { return (E)Values[i]; }
+  inline E &operator[](unsigned i)       { return (E&)Values[i]; }
+};
+
+} // End namespace cl
+
+#endif
diff --git a/include/llvm/Support/DepthFirstIterator.h b/include/Support/DepthFirstIterator.h
index 73017067b3..a2d5a9df68 100644
--- a/include/llvm/Support/DepthFirstIterator.h
+++ b/include/Support/DepthFirstIterator.h
@@ -1,4 +1,4 @@
-//===- llvm/Support/DepthFirstIterator.h - Depth First iterators -*- C++ -*--=//
+//===- Support/DepthFirstIterator.h - Depth First iterator -------*- C++ -*--=//
 //
 // This file builds on the Support/GraphTraits.h file to build generic depth
 // first graph iterator.
@@ -8,7 +8,7 @@
 #ifndef LLVM_SUPPORT_DEPTH_FIRST_ITERATOR_H
 #define LLVM_SUPPORT_DEPTH_FIRST_ITERATOR_H
 
-#include "llvm/Support/GraphTraits.h"
+#include "Support/GraphTraits.h"
 #include <iterator>
 #include <stack>
 #include <set>
diff --git a/include/llvm/Support/GraphTraits.h b/include/Support/GraphTraits.h
index 67fe7c9360..00973d59fa 100644
--- a/include/llvm/Support/GraphTraits.h
+++ b/include/Support/GraphTraits.h
@@ -1,4 +1,4 @@
-//===-- llvm/Support/GraphTraits.h - Graph traits template -------*- C++ -*--=//
+//===-- Support/GraphTraits.h - Graph traits template ------------*- C++ -*--=//
 //
 // This file defines the little GraphTraits<X> template class that should be 
 // specialized by classes that want to be iteratable by generic graph iterators.
diff --git a/include/llvm/Support/HashExtras.h b/include/Support/HashExtras.h
index 6ea831e78f..6ea831e78f 100644
--- a/include/llvm/Support/HashExtras.h
+++ b/include/Support/HashExtras.h
diff --git a/include/Support/MathExtras.h b/include/Support/MathExtras.h
new file mode 100644
index 0000000000..f3dc3de17b
--- /dev/null
+++ b/include/Support/MathExtras.h
@@ -0,0 +1,32 @@
+// $Id$ -*-c++-*-
+//***************************************************************************
+// File:
+//	MathExtras.h
+// 
+// Purpose:
+//	
+// History:
+//	8/25/01	 -  Vikram Adve  -  Created
+//**************************************************************************/
+
+#ifndef LLVM_SUPPORT_MATH_EXTRAS_H
+#define LLVM_SUPPORT_MATH_EXTRAS_H
+
+#include <sys/types.h>
+
+inline bool	IsPowerOf2	(int64_t C, unsigned& getPow);
+
+inline
+bool IsPowerOf2(int64_t C, unsigned& getPow)
+{
+  if (C < 0)
+    C = -C;
+  bool isBool = C > 0 && (C == (C & ~(C - 1)));
+  if (isBool)
+    for (getPow = 0; C > 1; getPow++)
+      C = C >> 1;
+  
+  return isBool;
+}
+
+#endif /*LLVM_SUPPORT_MATH_EXTRAS_H*/
diff --git a/include/llvm/Support/NonCopyable.h b/include/Support/NonCopyable.h
index f4fc26805a..f4fc26805a 100644
--- a/include/llvm/Support/NonCopyable.h
+++ b/include/Support/NonCopyable.h
diff --git a/include/llvm/Support/PostOrderIterator.h b/include/Support/PostOrderIterator.h
index fa135f8785..89a9b4db86 100644
--- a/include/llvm/Support/PostOrderIterator.h
+++ b/include/Support/PostOrderIterator.h
@@ -1,4 +1,4 @@
-//===-- llvm/Support/PostOrderIterator.h - Generic PO iterator ---*- C++ -*--=//
+//===-- Support/PostOrderIterator.h - Generic PostOrder iterator -*- C++ -*--=//
 //
 // This file builds on the Support/GraphTraits.h file to build a generic graph
 // post order iterator.  This should work over any graph type that has a
@@ -9,7 +9,7 @@
 #ifndef LLVM_SUPPORT_POSTORDER_ITERATOR_H
 #define LLVM_SUPPORT_POSTORDER_ITERATOR_H
 
-#include "llvm/Support/GraphTraits.h"
+#include "Support/GraphTraits.h"
 #include <iterator>
 #include <stack>
 #include <set>
diff --git a/include/llvm/Support/STLExtras.h b/include/Support/STLExtras.h
index 44d789dcf2..44d789dcf2 100644
--- a/include/llvm/Support/STLExtras.h
+++ b/include/Support/STLExtras.h
diff --git a/include/llvm/Support/StringExtras.h b/include/Support/StringExtras.h
index aaae8577ef..e67e25ced5 100644
--- a/include/llvm/Support/StringExtras.h
+++ b/include/Support/StringExtras.h
@@ -1,17 +1,15 @@
-//===-- StringExtras.h - Useful string functions -----------------*- C++ -*--=//
+//===-- Support/StringExtras.h - Useful string functions ---------*- C++ -*--=//
 //
 // This file contains some functions that are useful when dealing with strings.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_TOOLS_STRING_EXTRAS_H
-#define LLVM_TOOLS_STRING_EXTRAS_H
+#ifndef SUPPORT_STRING_EXTRAS_H
+#define SUPPORT_STRING_EXTRAS_H
 
+#include "Support/DataTypes.h"
 #include <string>
 #include <stdio.h>
-#include "Support/DataTypes.h"
-
-class ConstPoolArray;
 
 static inline string utostr(uint64_t X, bool isNeg = false) {
   char Buffer[40];
@@ -68,21 +66,4 @@ static inline string ftostr(double V) {
   return Buffer;
 }
 
-static inline void
-printIndent(unsigned int indent, ostream& os=cout, const char* const istr="  ")
-{
-  for (unsigned i=0; i < indent; i++)
-    os << istr;
-}
-
-// Can we treat the specified array as a string?  Only if it is an array of
-// ubytes or non-negative sbytes.
-//
-bool isStringCompatible(ConstPoolArray *CPA);
-
-// getAsCString - Return the specified array as a C compatible string, only if
-// the predicate isStringCompatible is true.
-//
-string getAsCString(ConstPoolArray *CPA);
-
 #endif
diff --git a/include/llvm/Support/Tree.h b/include/Support/Tree.h
index 679b6dfd83..33b0bb7b03 100644
--- a/include/llvm/Support/Tree.h
+++ b/include/Support/Tree.h
@@ -1,4 +1,4 @@
-//===- llvm/Support/Tree.h - Generic n-way tree structure --------*- C++ -*--=//
+//===- Support/Tree.h - Generic n-way tree structure -------------*- C++ -*--=//
 //
 // This class defines a generic N way tree node structure.  The tree structure
 // is immutable after creation, but the payload contained within it is not.
diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h
new file mode 100644
index 0000000000..a2d5a9df68
--- /dev/null
+++ b/include/llvm/ADT/DepthFirstIterator.h
@@ -0,0 +1,147 @@
+//===- Support/DepthFirstIterator.h - Depth First iterator -------*- C++ -*--=//
+//
+// This file builds on the Support/GraphTraits.h file to build generic depth
+// first graph iterator.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_DEPTH_FIRST_ITERATOR_H
+#define LLVM_SUPPORT_DEPTH_FIRST_ITERATOR_H
+
+#include "Support/GraphTraits.h"
+#include <iterator>
+#include <stack>
+#include <set>
+
+// Generic Depth First Iterator
+template<class GraphT, class GT = GraphTraits<GraphT> >
+class df_iterator : public std::forward_iterator<typename GT::NodeType,
+                                                 ptrdiff_t> {
+  typedef typename GT::NodeType          NodeType;
+  typedef typename GT::ChildIteratorType ChildItTy;
+
+  set<NodeType *>   Visited;    // All of the blocks visited so far...
+  // VisitStack - Used to maintain the ordering.  Top = current block
+  // First element is node pointer, second is the 'next child' to visit
+  stack<pair<NodeType *, ChildItTy> > VisitStack;
+  const bool Reverse;         // Iterate over children before self?
+private:
+  void reverseEnterNode() {
+    pair<NodeType *, ChildItTy> &Top = VisitStack.top();
+    NodeType *Node = Top.first;
+    ChildItTy &It  = Top.second;
+    for (; It != GT::child_end(Node); ++It) {
+      NodeType *Child = *It;
+      if (!Visited.count(Child)) {
+	Visited.insert(Child);
+	VisitStack.push(make_pair(Child, GT::child_begin(Child)));
+	reverseEnterNode();
+	return;
+      }
+    }
+  }
+
+  inline df_iterator(NodeType *Node, bool reverse) : Reverse(reverse) {
+    Visited.insert(Node);
+    VisitStack.push(make_pair(Node, GT::child_begin(Node)));
+    if (Reverse) reverseEnterNode();
+  }
+  inline df_iterator() { /* End is when stack is empty */ }
+
+public:
+  typedef df_iterator<GraphT, GT> _Self;
+
+  // Provide static begin and end methods as our public "constructors"
+  static inline _Self begin(GraphT G, bool Reverse = false) {
+    return _Self(GT::getEntryNode(G), Reverse);
+  }
+  static inline _Self end(GraphT G) { return _Self(); }
+
+
+  inline bool operator==(const _Self& x) const { 
+    return VisitStack == x.VisitStack;
+  }
+  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
+  inline pointer operator*() const { 
+    return VisitStack.top().first;
+  }
+
+  // This is a nonstandard operator-> that dereferences the pointer an extra
+  // time... so that you can actually call methods ON the Node, because
+  // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
+  //
+  inline NodeType *operator->() const { return operator*(); }
+
+  inline _Self& operator++() {   // Preincrement
+    if (Reverse) {               // Reverse Depth First Iterator
+      if (VisitStack.top().second == GT::child_end(VisitStack.top().first))
+	VisitStack.pop();
+      if (!VisitStack.empty())
+	reverseEnterNode();
+    } else {                     // Normal Depth First Iterator
+      do {
+	pair<NodeType *, ChildItTy> &Top = VisitStack.top();
+	NodeType *Node = Top.first;
+	ChildItTy &It  = Top.second;
+
+	while (It != GT::child_end(Node)) {
+	  NodeType *Next = *It++;
+	  if (!Visited.count(Next)) {  // Has our next sibling been visited?
+	    // No, do it now.
+	    Visited.insert(Next);
+	    VisitStack.push(make_pair(Next, GT::child_begin(Next)));
+	    return *this;
+	  }
+	}
+	
+	// Oops, ran out of successors... go up a level on the stack.
+	VisitStack.pop();
+      } while (!VisitStack.empty());
+    }
+    return *this; 
+  }
+
+  inline _Self operator++(int) { // Postincrement
+    _Self tmp = *this; ++*this; return tmp; 
+  }
+
+  // nodeVisited - return true if this iterator has already visited the
+  // specified node.  This is public, and will probably be used to iterate over
+  // nodes that a depth first iteration did not find: ie unreachable nodes.
+  //
+  inline bool nodeVisited(NodeType *Node) const { 
+    return Visited.count(Node) != 0;
+  }
+};
+
+
+// Provide global constructors that automatically figure out correct types...
+//
+template <class T>
+df_iterator<T> df_begin(T G, bool Reverse = false) {
+  return df_iterator<T>::begin(G, Reverse);
+}
+
+template <class T>
+df_iterator<T> df_end(T G) {
+  return df_iterator<T>::end(G);
+}
+
+// Provide global definitions of inverse depth first iterators...
+template <class T>
+struct idf_iterator : public df_iterator<Inverse<T> > {
+  idf_iterator(const df_iterator<Inverse<T> > &V) :df_iterator<Inverse<T> >(V){}
+};
+
+template <class T>
+idf_iterator<T> idf_begin(T G, bool Reverse = false) {
+  return idf_iterator<T>::begin(G, Reverse);
+}
+
+template <class T>
+idf_iterator<T> idf_end(T G){
+  return idf_iterator<T>::end(G);
+}
+
+#endif
diff --git a/include/llvm/ADT/GraphTraits.h b/include/llvm/ADT/GraphTraits.h
new file mode 100644
index 0000000000..00973d59fa
--- /dev/null
+++ b/include/llvm/ADT/GraphTraits.h
@@ -0,0 +1,65 @@
+//===-- Support/GraphTraits.h - Graph traits template ------------*- C++ -*--=//
+//
+// This file defines the little GraphTraits<X> template class that should be 
+// specialized by classes that want to be iteratable by generic graph iterators.
+//
+// This file also defines the marker class Inverse that is used to iterate over
+// graphs in a graph defined, inverse ordering...
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_GRAPH_TRAITS_H
+#define LLVM_SUPPORT_GRAPH_TRAITS_H
+
+// GraphTraits - This class should be specialized by different graph types...
+// which is why the default version is empty.
+//
+template<class GraphType>
+struct GraphTraits {
+  // Elements to provide:
+
+  // typedef NodeType          - Type of Node in the graph
+  // typedef ChildIteratorType - Type used to iterate over children in graph
+
+  // static NodeType *getEntryNode(GraphType *)
+  //    Return the entry node of the graph
+
+  // static ChildIteratorType child_begin(NodeType *)
+  // static ChildIteratorType child_end  (NodeType *)
+  //    Return iterators that point to the beginning and ending of the child 
+  //    node list for the specified node.
+  //  
+
+
+  // If anyone tries to use this class without having an appropriate
+  // specialization, make an error.  If you get this error, it's because you
+  // need to include the appropriate specialization of GraphTraits<> for your
+  // graph, or you need to define it for a new graph type. Either that or 
+  // your argument to XXX_begin(...) is unknown or needs to have the proper .h
+  // file #include'd.
+  //
+  typedef typename GraphType::UnknownGraphTypeError NodeType;
+};
+
+
+// Inverse - This class is used as a little marker class to tell the graph
+// iterator to iterate over the graph in a graph defined "Inverse" ordering.
+// Not all graphs define an inverse ordering, and if they do, it depends on
+// the graph exactly what that is.  Here's an example of usage with the
+// df_iterator:
+//
+// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
+// for (; I != E; ++I) { ... }
+//
+// Which is equivalent to:
+// df_iterator<Inverse<Method*> > I = idf_begin(M), E = idf_end(M);
+// for (; I != E; ++I) { ... }
+//
+template <class GraphType>
+struct Inverse {
+  GraphType &Graph;
+
+  inline Inverse(GraphType &G) : Graph(G) {}
+};
+
+#endif
diff --git a/include/llvm/ADT/HashExtras.h b/include/llvm/ADT/HashExtras.h
new file mode 100644
index 0000000000..6ea831e78f
--- /dev/null
+++ b/include/llvm/ADT/HashExtras.h
@@ -0,0 +1,27 @@
+//===-- HashExtras.h - Useful functions for STL hash containers --*- C++ -*--=//
+//
+// This file contains some templates that are useful if you are working with the
+// STL Hashed containers.
+//
+// No library is required when using these functinons.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_HASHEXTRAS_H
+#define LLVM_SUPPORT_HASHEXTRAS_H
+
+#include <string>
+#include <hash_map>
+
+template <> struct hash<string> {
+  size_t operator()(string const &str) const {
+    return hash<char const *>()(str.c_str());
+  }
+};
+
+// Provide a hash function for arbitrary pointers...
+template <class T> struct hash<T *> {
+  inline size_t operator()(const T *Val) const { return (size_t)Val; }
+};
+
+#endif
diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h
new file mode 100644
index 0000000000..89a9b4db86
--- /dev/null
+++ b/include/llvm/ADT/PostOrderIterator.h
@@ -0,0 +1,145 @@
+//===-- Support/PostOrderIterator.h - Generic PostOrder iterator -*- C++ -*--=//
+//
+// This file builds on the Support/GraphTraits.h file to build a generic graph
+// post order iterator.  This should work over any graph type that has a
+// GraphTraits specialization.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_POSTORDER_ITERATOR_H
+#define LLVM_SUPPORT_POSTORDER_ITERATOR_H
+
+#include "Support/GraphTraits.h"
+#include <iterator>
+#include <stack>
+#include <set>
+
+template<class GraphT, class GT = GraphTraits<GraphT> >
+class po_iterator : public std::forward_iterator<typename GT::NodeType,
+                                                 ptrdiff_t> {
+  typedef typename GT::NodeType          NodeType;
+  typedef typename GT::ChildIteratorType ChildItTy;
+
+  set<NodeType *>   Visited;    // All of the blocks visited so far...
+  // VisitStack - Used to maintain the ordering.  Top = current block
+  // First element is basic block pointer, second is the 'next child' to visit
+  stack<pair<NodeType *, ChildItTy> > VisitStack;
+
+  void traverseChild() {
+    while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) {
+      NodeType *BB = *VisitStack.top().second++;
+      if (!Visited.count(BB)) {  // If the block is not visited...
+	Visited.insert(BB);
+	VisitStack.push(make_pair(BB, GT::child_begin(BB)));
+      }
+    }
+  }
+
+  inline po_iterator(NodeType *BB) {
+    Visited.insert(BB);
+    VisitStack.push(make_pair(BB, GT::child_begin(BB)));
+    traverseChild();
+  }
+  inline po_iterator() { /* End is when stack is empty */ }
+public:
+  typedef po_iterator<GraphT, GT> _Self;
+
+  // Provide static "constructors"...
+  static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); }
+  static inline _Self end  (GraphT G) { return _Self(); }
+
+  inline bool operator==(const _Self& x) const { 
+    return VisitStack == x.VisitStack;
+  }
+  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
+  inline pointer operator*() const { 
+    return VisitStack.top().first;
+  }
+
+  // This is a nonstandard operator-> that dereferences the pointer an extra
+  // time... so that you can actually call methods ON the BasicBlock, because
+  // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
+  //
+  inline NodeType *operator->() const { return operator*(); }
+
+  inline _Self& operator++() {   // Preincrement
+    VisitStack.pop();
+    if (!VisitStack.empty())
+      traverseChild();
+    return *this; 
+  }
+
+  inline _Self operator++(int) { // Postincrement
+    _Self tmp = *this; ++*this; return tmp; 
+  }
+};
+
+// Provide global constructors that automatically figure out correct types...
+//
+template <class T>
+po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); }
+template <class T>
+po_iterator<T> po_end  (T G) { return po_iterator<T>::end(G); }
+
+// Provide global definitions of inverse post order iterators...
+template <class T>
+struct ipo_iterator : public po_iterator<Inverse<T> > {
+  ipo_iterator(const po_iterator<Inverse<T> > &V) :po_iterator<Inverse<T> >(V){}
+};
+
+template <class T>
+ipo_iterator<T> ipo_begin(T G, bool Reverse = false) {
+  return ipo_iterator<T>::begin(G, Reverse);
+}
+
+template <class T>
+ipo_iterator<T> ipo_end(T G){
+  return ipo_iterator<T>::end(G);
+}
+
+
+//===--------------------------------------------------------------------===//
+// Reverse Post Order CFG iterator code
+//===--------------------------------------------------------------------===//
+// 
+// This is used to visit basic blocks in a method in reverse post order.  This
+// class is awkward to use because I don't know a good incremental algorithm to
+// computer RPO from a graph.  Because of this, the construction of the 
+// ReversePostOrderTraversal object is expensive (it must walk the entire graph
+// with a postorder iterator to build the data structures).  The moral of this
+// story is: Don't create more ReversePostOrderTraversal classes than neccesary.
+//
+// This class should be used like this:
+// {
+//   cfg::ReversePostOrderTraversal RPOT(MethodPtr);   // Expensive to create
+//   for (cfg::rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
+//      ...
+//   }
+//   for (cfg::rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
+//      ...
+//   }
+// }
+//
+
+typedef reverse_iterator<vector<BasicBlock*>::iterator> rpo_iterator;
+// TODO: FIXME: ReversePostOrderTraversal is not generic!
+class ReversePostOrderTraversal {
+  vector<BasicBlock*> Blocks;       // Block list in normal PO order
+  inline void Initialize(BasicBlock *BB) {
+    copy(po_begin(BB), po_end(BB), back_inserter(Blocks));
+  }
+public:
+  inline ReversePostOrderTraversal(Method *M) {
+    Initialize(M->front());
+  }
+  inline ReversePostOrderTraversal(BasicBlock *BB) {
+    Initialize(BB);
+  }
+
+  // Because we want a reverse post order, use reverse iterators from the vector
+  inline rpo_iterator begin() { return Blocks.rbegin(); }
+  inline rpo_iterator end()   { return Blocks.rend(); }
+};
+
+#endif
diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
new file mode 100644
index 0000000000..44d789dcf2
--- /dev/null
+++ b/include/llvm/ADT/STLExtras.h
@@ -0,0 +1,222 @@
+//===-- STLExtras.h - Useful functions when working with the STL -*- C++ -*--=//
+//
+// This file contains some templates that are useful if you are working with the
+// STL at all.
+//
+// No library is required when using these functinons.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_STL_EXTRAS_H
+#define LLVM_SUPPORT_STL_EXTRAS_H
+
+#include <functional>
+
+//===----------------------------------------------------------------------===//
+//     Extra additions to <functional>
+//===----------------------------------------------------------------------===//
+
+// bind_obj - Often times you want to apply the member function of an object
+// as a unary functor.  This macro is shorthand that makes it happen less
+// verbosely.
+//
+// Example:
+//  struct Summer { void accumulate(int x); }
+//  vector<int> Numbers;
+//  Summer MyS;
+//  for_each(Numbers.begin(), Numbers.end(),
+//           bind_obj(&MyS, &Summer::accumulate));
+//
+// TODO: When I get lots of extra time, convert this from an evil macro
+//
+#define bind_obj(OBJ, METHOD) std::bind1st(std::mem_fun(METHOD), OBJ)
+
+
+// bitwise_or - This is a simple functor that applys operator| on its two 
+// arguments to get a boolean result.
+//
+template<class Ty>
+struct bitwise_or : public binary_function<Ty, Ty, bool> {
+  bool operator()(const Ty& left, const Ty& right) const {
+    return left | right;
+  }
+};
+
+
+// deleter - Very very very simple method that is used to invoke operator
+// delete on something.  It is used like this: 
+//
+//   for_each(V.begin(), B.end(), deleter<cfg::Interval>);
+//
+template <class T> 
+static inline void deleter(T *Ptr) { 
+  delete Ptr; 
+}
+
+
+
+//===----------------------------------------------------------------------===//
+//     Extra additions to <iterator>
+//===----------------------------------------------------------------------===//
+
+// mapped_iterator - This is a simple iterator adapter that causes a function to
+// be dereferenced whenever operator* is invoked on the iterator.
+//
+// It turns out that this is disturbingly similar to boost::transform_iterator
+//
+#if 1
+template <class RootIt, class UnaryFunc>
+class mapped_iterator {
+  RootIt current;
+  UnaryFunc Fn;
+public:
+  typedef typename iterator_traits<RootIt>::iterator_category
+          iterator_category;
+  typedef typename iterator_traits<RootIt>::difference_type
+          difference_type;
+  typedef typename UnaryFunc::result_type value_type;
+  typedef typename UnaryFunc::result_type *pointer;
+  typedef void reference;        // Can't modify value returned by fn
+
+  typedef RootIt iterator_type;
+  typedef mapped_iterator<RootIt, UnaryFunc> _Self;
+
+  inline RootIt &getCurrent() const { return current; }
+
+  inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
+    : current(I), Fn(F) {}
+  inline mapped_iterator(const mapped_iterator &It)
+    : current(It.current), Fn(It.Fn) {}
+
+  inline value_type operator*() const {   // All this work to do this 
+    return Fn(*current);         // little change
+  }
+
+  _Self& operator++() { ++current; return *this; }
+  _Self& operator--() { --current; return *this; }
+  _Self  operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
+  _Self  operator--(int) { _Self __tmp = *this; --current; return __tmp; }
+  _Self  operator+    (difference_type n) const { return _Self(current + n); }
+  _Self& operator+=   (difference_type n) { current += n; return *this; }
+  _Self  operator-    (difference_type n) const { return _Self(current - n); }
+  _Self& operator-=   (difference_type n) { current -= n; return *this; }
+  reference operator[](difference_type n) const { return *(*this + n); }  
+
+  inline bool operator==(const _Self &X) const { return current == X.current; }
+  inline bool operator< (const _Self &X) const { return current <  X.current; }
+
+  inline difference_type operator-(const _Self &X) const {
+    return current - X.current;
+  }
+};
+
+template <class _Iterator, class Func>
+inline mapped_iterator<_Iterator, Func> 
+operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
+          const mapped_iterator<_Iterator, Func>& X) {
+  return mapped_iterator<_Iterator, Func>(X.getCurrent() - N);
+}
+
+#else
+
+// This fails to work, because some iterators are not classes, for example
+// vector iterators are commonly value_type **'s
+template <class RootIt, class UnaryFunc>
+class mapped_iterator : public RootIt {
+  UnaryFunc Fn;
+public:
+  typedef typename UnaryFunc::result_type value_type;
+  typedef typename UnaryFunc::result_type *pointer;
+  typedef void reference;        // Can't modify value returned by fn
+
+  typedef mapped_iterator<RootIt, UnaryFunc> _Self;
+  typedef RootIt super;
+  inline explicit mapped_iterator(const RootIt &I) : super(I) {}
+  inline mapped_iterator(const super &It) : super(It) {}
+
+  inline value_type operator*() const {     // All this work to do 
+    return Fn(super::operator*());   // this little thing
+  }
+};
+#endif
+
+// map_iterator - Provide a convenient way to create mapped_iterators, just like
+// make_pair is useful for creating pairs...
+//
+template <class ItTy, class FuncTy>
+inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
+  return mapped_iterator<ItTy, FuncTy>(I, F);
+}
+
+
+//===----------------------------------------------------------------------===//
+//     Extra additions to <algorithm>
+//===----------------------------------------------------------------------===//
+
+// apply_until - Apply a functor to a sequence continually, unless the
+// functor returns true.  Return true if the functor returned true, return false
+// if the functor never returned true.
+//
+template <class InputIt, class Function>
+bool apply_until(InputIt First, InputIt Last, Function Func) {
+  for ( ; First != Last; ++First)
+    if (Func(*First)) return true;
+  return false;
+}
+
+
+// reduce - Reduce a sequence values into a single value, given an initial
+// value and an operator.
+//
+template <class InputIt, class Function, class ValueType>
+ValueType reduce(InputIt First, InputIt Last, Function Func, ValueType Value) {
+  for ( ; First != Last; ++First)
+    Value = Func(*First, Value);
+  return Value;
+}
+
+#if 1   // This is likely to be more efficient
+
+// reduce_apply - Reduce the result of applying a function to each value in a
+// sequence, given an initial value, an operator, a function, and a sequence.
+//
+template <class InputIt, class Function, class ValueType, class TransFunc>
+inline ValueType reduce_apply(InputIt First, InputIt Last, Function Func, 
+			      ValueType Value, TransFunc XForm) {
+  for ( ; First != Last; ++First)
+    Value = Func(XForm(*First), Value);
+  return Value;
+}
+
+#else  // This is arguably more elegant
+
+// reduce_apply - Reduce the result of applying a function to each value in a
+// sequence, given an initial value, an operator, a function, and a sequence.
+//
+template <class InputIt, class Function, class ValueType, class TransFunc>
+inline ValueType reduce_apply2(InputIt First, InputIt Last, Function Func, 
+			       ValueType Value, TransFunc XForm) {
+  return reduce(map_iterator(First, XForm), map_iterator(Last, XForm),
+		Func, Value);
+}
+#endif
+
+
+// reduce_apply_bool - Reduce the result of applying a (bool returning) function
+// to each value in a sequence.  All of the bools returned by the mapped
+// function are bitwise or'd together, and the result is returned.
+//
+template <class InputIt, class Function>
+inline bool reduce_apply_bool(InputIt First, InputIt Last, Function Func) {
+  return reduce_apply(First, Last, bitwise_or<bool>(), false, Func);
+}
+
+
+// map - This function maps the specified input sequence into the specified
+// output iterator, applying a unary function in between.
+//
+template <class InIt, class OutIt, class Functor>
+inline OutIt mapto(InIt Begin, InIt End, OutIt Dest, Functor F) {
+  return copy(map_iterator(Begin, F), map_iterator(End, F), Dest);
+}
+#endif
diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h
new file mode 100644
index 0000000000..e67e25ced5
--- /dev/null
+++ b/include/llvm/ADT/StringExtras.h
@@ -0,0 +1,69 @@
+//===-- Support/StringExtras.h - Useful string functions ---------*- C++ -*--=//
+//
+// This file contains some functions that are useful when dealing with strings.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SUPPORT_STRING_EXTRAS_H
+#define SUPPORT_STRING_EXTRAS_H
+
+#include "Support/DataTypes.h"
+#include <string>
+#include <stdio.h>
+
+static inline string utostr(uint64_t X, bool isNeg = false) {
+  char Buffer[40];
+  char *BufPtr = Buffer+39;
+
+  *BufPtr = 0;                  // Null terminate buffer...
+  if (X == 0) *--BufPtr = '0';  // Handle special case...
+
+  while (X) {
+    *--BufPtr = '0' + (X % 10);
+    X /= 10;
+  }
+
+  if (isNeg) *--BufPtr = '-';   // Add negative sign...
+
+  return string(BufPtr);
+}
+
+static inline string itostr(int64_t X) {
+  if (X < 0) 
+    return utostr((uint64_t)-X, true);
+  else
+    return utostr((uint64_t)X);
+}
+
+
+static inline string utostr(unsigned X, bool isNeg = false) {
+  char Buffer[20];
+  char *BufPtr = Buffer+19;
+
+  *BufPtr = 0;                  // Null terminate buffer...
+  if (X == 0) *--BufPtr = '0';  // Handle special case...
+
+  while (X) {
+    *--BufPtr = '0' + (X % 10);
+    X /= 10;
+  }
+
+  if (isNeg) *--BufPtr = '-';   // Add negative sign...
+
+  return string(BufPtr);
+}
+
+static inline string itostr(int X) {
+  if (X < 0) 
+    return utostr((unsigned)-X, true);
+  else
+    return utostr((unsigned)X);
+}
+
+static inline string ftostr(double V) {
+  char Buffer[200];
+  snprintf(Buffer, 200, "%e", V);
+  return Buffer;
+}
+
+#endif
diff --git a/include/llvm/ADT/Tree.h b/include/llvm/ADT/Tree.h
new file mode 100644
index 0000000000..33b0bb7b03
--- /dev/null
+++ b/include/llvm/ADT/Tree.h
@@ -0,0 +1,52 @@
+//===- Support/Tree.h - Generic n-way tree structure -------------*- C++ -*--=//
+//
+// This class defines a generic N way tree node structure.  The tree structure
+// is immutable after creation, but the payload contained within it is not.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_TREE_H
+#define LLVM_SUPPORT_TREE_H
+
+#include <vector>
+
+template<class ConcreteTreeNode, class Payload>
+class Tree {
+  vector<ConcreteTreeNode*>    Children;        // This nodes children, if any
+  ConcreteTreeNode            *Parent;          // Parent of this node...
+  Payload                      Data;            // Data held in this node...
+
+protected:
+  void setChildren(const vector<ConcreteTreeNode*> &children) {
+    Children = children;
+  }
+public:
+  inline Tree(ConcreteTreeNode *parent) : Parent(parent) {}
+  inline Tree(const vector<ConcreteTreeNode*> &children, ConcreteTreeNode *par)
+    : Children(children), Parent(par) {}
+
+  inline Tree(const vector<ConcreteTreeNode*> &children, ConcreteTreeNode *par,
+	      const Payload &data) 
+    : Children(children), Parent(parent), Data(data) {}
+
+  // Tree dtor - Free all children
+  inline ~Tree() {
+    for (unsigned i = Children.size(); i > 0; --i)
+      delete Children[i-1];
+  }
+
+  // Tree manipulation/walking routines...
+  inline ConcreteTreeNode *getParent() const { return Parent; }
+  inline unsigned getNumChildren() const { return Children.size(); }
+  inline ConcreteTreeNode *getChild(unsigned i) const {
+    assert(i < Children.size() && "Tree::getChild with index out of range!");
+    return Children[i];
+  }
+
+  // Payload access...
+  inline Payload &getTreeData() { return Data; }
+  inline const Payload &getTreeData() const { return Data; }
+};
+
+
+#endif
diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h
index 62b1846952..8365a4f397 100644
--- a/include/llvm/Analysis/CallGraph.h
+++ b/include/llvm/Analysis/CallGraph.h
@@ -16,7 +16,7 @@
 #ifndef LLVM_ANALYSIS_CALLGRAPH_H
 #define LLVM_ANALYSIS_CALLGRAPH_H
 
-#include "llvm/Support/GraphTraits.h"
+#include "Support/GraphTraits.h"
 #include <map>
 #include <vector>
 class Method;
diff --git a/include/llvm/Analysis/InstForest.h b/include/llvm/Analysis/InstForest.h
index 967ed45ec9..497bb46188 100644
--- a/include/llvm/Analysis/InstForest.h
+++ b/include/llvm/Analysis/InstForest.h
@@ -14,8 +14,8 @@
 #ifndef LLVM_ANALYSIS_INSTFOREST_H
 #define LLVM_ANALYSIS_INSTFOREST_H
 
-#include "llvm/Support/Tree.h"
 #include "llvm/Instruction.h"
+#include "Support/Tree.h"
 #include <map>
 
 namespace analysis {
diff --git a/include/llvm/BasicBlock.h b/include/llvm/BasicBlock.h
index cf29cbd00e..df9447fb09 100644
--- a/include/llvm/BasicBlock.h
+++ b/include/llvm/BasicBlock.h
@@ -24,8 +24,8 @@
 
 #include "llvm/Value.h"
 #include "llvm/ValueHolder.h"
-#include "llvm/Support/GraphTraits.h"
 #include "llvm/InstrTypes.h"
+#include "Support/GraphTraits.h"
 #include <iterator>
 
 class Instruction;
diff --git a/include/llvm/CodeGen/InstrForest.h b/include/llvm/CodeGen/InstrForest.h
index 1b9af714b9..e7bd3ad145 100644
--- a/include/llvm/CodeGen/InstrForest.h
+++ b/include/llvm/CodeGen/InstrForest.h
@@ -24,9 +24,9 @@
 #ifndef LLVM_CODEGEN_INSTRFOREST_H
 #define LLVM_CODEGEN_INSTRFOREST_H
 
-#include "llvm/Support/NonCopyable.h"
-#include "llvm/Support/HashExtras.h"
 #include "llvm/Instruction.h"
+#include "Support/NonCopyable.h"
+#include "Support/HashExtras.h"
 #include <hash_map>
 #include <hash_set>
 
diff --git a/include/llvm/CodeGen/InstrScheduling.h b/include/llvm/CodeGen/InstrScheduling.h
index 8f88a61590..69390fae96 100644
--- a/include/llvm/CodeGen/InstrScheduling.h
+++ b/include/llvm/CodeGen/InstrScheduling.h
@@ -12,8 +12,8 @@
 #ifndef LLVM_CODEGEN_INSTR_SCHEDULING_H
 #define LLVM_CODEGEN_INSTR_SCHEDULING_H
 
-#include "llvm/Support/CommandLine.h"
 #include "llvm/CodeGen/MachineInstr.h"
+#include "Support/CommandLine.h"
 
 class Method;
 class SchedulingManager;
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 91ae9def7f..a20431848e 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -15,13 +15,13 @@
 #ifndef LLVM_CODEGEN_MACHINEINSTR_H
 #define LLVM_CODEGEN_MACHINEINSTR_H
 
-#include <iterator>
-#include "llvm/CodeGen/InstrForest.h"
 #include "Support/DataTypes.h"
-#include "llvm/Support/NonCopyable.h"
+#include "Support/NonCopyable.h"
+#include "llvm/CodeGen/InstrForest.h"
 #include "llvm/Target/MachineInstrInfo.h"
 #include "llvm/Annotation.h"
 #include "llvm/Method.h"
+#include <iterator>
 #include <hash_map>
 #include <hash_set>
 #include <values.h>
diff --git a/include/llvm/CodeGen/RegAllocCommon.h b/include/llvm/CodeGen/RegAllocCommon.h
index 5fa51c034f..02b3331132 100644
--- a/include/llvm/CodeGen/RegAllocCommon.h
+++ b/include/llvm/CodeGen/RegAllocCommon.h
@@ -1,5 +1,5 @@
 
-#include "llvm/Support/CommandLine.h"
+#include "Support/CommandLine.h"
 
 #ifndef REG_ALLOC_COMMON_H
 #define  REG_ALLOC_COMMON_H
diff --git a/include/llvm/Support/CommandLine.h b/include/llvm/Support/CommandLine.h
new file mode 100644
index 0000000000..84a3bc9b59
--- /dev/null
+++ b/include/llvm/Support/CommandLine.h
@@ -0,0 +1,399 @@
+//===- Support/CommandLine.h - Flexible Command line parser ------*- C++ -*--=//
+//
+// This class implements a command line argument processor that is useful when
+// creating a tool.  It provides a simple, minimalistic interface that is easily
+// extensible and supports nonlocal (library) command line options.
+//
+// Note that rather than trying to figure out what this code does, you could try
+// reading the library documentation located in docs/CommandLine.html
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_COMMANDLINE_H
+#define LLVM_SUPPORT_COMMANDLINE_H
+
+#include <string>
+#include <vector>
+#include <utility>
+#include <stdarg.h>
+
+namespace cl {   // Short namespace to make usage concise
+
+//===----------------------------------------------------------------------===//
+// ParseCommandLineOptions - Minimalistic command line option processing entry
+//
+void cl::ParseCommandLineOptions(int &argc, char **argv,
+				 const char *Overview = 0,
+				 int Flags = 0);
+
+// ParserOptions - This set of option is use to control global behavior of the
+// command line processor.
+//
+enum ParserOptions {
+  // DisableSingleLetterArgGrouping - With this option enabled, multiple letter
+  // options are allowed to bunch together with only a single hyphen for the
+  // whole group.  This allows emulation of the behavior that ls uses for
+  // example:  ls -la === ls -l -a    Providing this option, disables this.
+  //
+  DisableSingleLetterArgGrouping = 0x0001,
+
+  // EnableSingleLetterArgValue - This option allows arguments that are
+  // otherwise unrecognized to match single letter flags that take a value. 
+  // This is useful for cases like a linker, where options are typically of the
+  // form '-lfoo' or '-L../../include' where -l or -L are the actual flags.
+  //
+  EnableSingleLetterArgValue     = 0x0002,
+};
+
+
+//===----------------------------------------------------------------------===//
+// Global flags permitted to be passed to command line arguments
+
+enum FlagsOptions {
+  NoFlags         = 0x00,      // Marker to make explicit that we have no flags
+  Default         = 0x00,      // Equally, marker to use the default flags
+
+  GlobalsMask     = 0x80, 
+};
+
+enum NumOccurances {           // Flags for the number of occurances allowed...
+  Optional        = 0x01,      // Zero or One occurance
+  ZeroOrMore      = 0x02,      // Zero or more occurances allowed
+  Required        = 0x03,      // One occurance required
+  OneOrMore       = 0x04,      // One or more occurances required
+
+  // ConsumeAfter - Marker for a null ("") flag that can be used to indicate
+  // that anything that matches the null marker starts a sequence of options
+  // that all get sent to the null marker.  Thus, for example, all arguments
+  // to LLI are processed until a filename is found.  Once a filename is found,
+  // all of the succeeding arguments are passed, unprocessed, to the null flag.
+  //
+  ConsumeAfter    = 0x05,
+
+  OccurancesMask  = 0x07,
+};
+
+enum ValueExpected {           // Is a value required for the option?
+  ValueOptional   = 0x08,      // The value can oppear... or not
+  ValueRequired   = 0x10,      // The value is required to appear!
+  ValueDisallowed = 0x18,      // A value may not be specified (for flags)
+  ValueMask       = 0x18,
+};
+
+enum OptionHidden {            // Control whether -help shows this option
+  NotHidden       = 0x20,      // Option included in --help & --help-hidden
+  Hidden          = 0x40,      // -help doesn't, but --help-hidden does
+  ReallyHidden    = 0x60,      // Neither --help nor --help-hidden show this arg
+  HiddenMask      = 0x60,
+};
+
+
+//===----------------------------------------------------------------------===//
+// Option Base class
+//
+class Alias;
+class Option {
+  friend void cl::ParseCommandLineOptions(int &, char **, const char *, int);
+  friend class Alias;
+
+  // handleOccurances - Overriden by subclasses to handle the value passed into
+  // an argument.  Should return true if there was an error processing the
+  // argument and the program should exit.
+  //
+  virtual bool handleOccurance(const char *ArgName, const string &Arg) = 0;
+
+  virtual enum NumOccurances getNumOccurancesFlagDefault() const { 
+    return Optional;
+  }
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueOptional; 
+  }
+  virtual enum OptionHidden getOptionHiddenFlagDefault() const {
+    return NotHidden;
+  }
+
+  int NumOccurances;          // The number of times specified
+  const int Flags;            // Flags for the argument
+public:
+  const char * const ArgStr;  // The argument string itself (ex: "help", "o")
+  const char * const HelpStr; // The descriptive text message for --help
+
+  inline enum NumOccurances getNumOccurancesFlag() const {
+    int NO = Flags & OccurancesMask;
+    return NO ? (enum NumOccurances)NO : getNumOccurancesFlagDefault();
+  }
+  inline enum ValueExpected getValueExpectedFlag() const {
+    int VE = Flags & ValueMask;
+    return VE ? (enum ValueExpected)VE : getValueExpectedFlagDefault();
+  }
+  inline enum OptionHidden getOptionHiddenFlag() const {
+    int OH = Flags & HiddenMask;
+    return OH ? (enum OptionHidden)OH : getOptionHiddenFlagDefault();
+  }
+
+protected:
+  Option(const char *ArgStr, const char *Message, int Flags);
+  Option(int flags) : NumOccurances(0), Flags(flags), ArgStr(""), HelpStr("") {}
+
+public:
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+
+  // addOccurance - Wrapper around handleOccurance that enforces Flags
+  //
+  bool addOccurance(const char *ArgName, const string &Value);
+
+  // Prints option name followed by message.  Always returns true.
+  bool error(string Message, const char *ArgName = 0);
+
+public:
+  inline int getNumOccurances() const { return NumOccurances; }
+  virtual ~Option() {}
+};
+
+
+//===----------------------------------------------------------------------===//
+// Aliased command line option (alias this name to a preexisting name)
+//
+class Alias : public Option {
+  Option &AliasFor;
+  virtual bool handleOccurance(const char *ArgName, const string &Arg) {
+    return AliasFor.handleOccurance(AliasFor.ArgStr, Arg);
+  }
+  virtual enum OptionHidden getOptionHiddenFlagDefault() const {return Hidden;}
+public:
+  inline Alias(const char *ArgStr, const char *Message, int Flags,
+	       Option &aliasFor) : Option(ArgStr, Message, Flags), 
+				   AliasFor(aliasFor) {}
+};
+
+//===----------------------------------------------------------------------===//
+// Boolean/flag command line option
+//
+class Flag : public Option {
+  bool Value;
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+public:
+  inline Flag(const char *ArgStr, const char *Message, int Flags = 0, 
+	      bool DefaultVal = 0) : Option(ArgStr, Message, Flags), 
+				     Value(DefaultVal) {}
+  operator const bool() const { return Value; }
+  inline bool operator=(bool Val) { Value = Val; return Val; }
+};
+
+
+
+//===----------------------------------------------------------------------===//
+// Integer valued command line option
+//
+class Int : public Option {
+  int Value;
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired; 
+  }
+public:
+  inline Int(const char *ArgStr, const char *Help, int Flags = 0,
+	     int DefaultVal = 0) : Option(ArgStr, Help, Flags),
+				   Value(DefaultVal) {}
+  inline operator int() const { return Value; }
+  inline int operator=(int Val) { Value = Val; return Val; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// String valued command line option
+//
+class String : public Option, public string {
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired; 
+  }
+public:
+  inline String(const char *ArgStr, const char *Help, int Flags = 0, 
+		const char *DefaultVal = "") 
+    : Option(ArgStr, Help, Flags), string(DefaultVal) {}
+
+  inline const string &operator=(const string &Val) { 
+    return string::operator=(Val);
+  }
+};
+
+
+//===----------------------------------------------------------------------===//
+// String list command line option
+//
+class StringList : public Option, public vector<string> {
+
+  virtual enum NumOccurances getNumOccurancesFlagDefault() const { 
+    return ZeroOrMore;
+  }
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired;
+  }
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+
+public:
+  inline StringList(const char *ArgStr, const char *Help, int Flags = 0)
+    : Option(ArgStr, Help, Flags) {}
+};
+
+
+//===----------------------------------------------------------------------===//
+// Enum valued command line option
+//
+#define clEnumVal(ENUMVAL, DESC) #ENUMVAL, ENUMVAL, DESC
+#define clEnumValN(ENUMVAL, FLAGNAME, DESC) FLAGNAME, ENUMVAL, DESC
+
+// EnumBase - Base class for all enum/varargs related argument types...
+class EnumBase : public Option {
+protected:
+  // Use a vector instead of a map, because the lists should be short,
+  // the overhead is less, and most importantly, it keeps them in the order
+  // inserted so we can print our option out nicely.
+  vector<pair<const char *, pair<int, const char *> > > ValueMap;
+
+  inline EnumBase(const char *ArgStr, const char *Help, int Flags)
+    : Option(ArgStr, Help, Flags) {}
+  inline EnumBase(int Flags) : Option(Flags) {}
+
+  // processValues - Incorporate the specifed varargs arglist into the 
+  // ValueMap.
+  //
+  void processValues(va_list Vals);
+
+  // registerArgs - notify the system about these new arguments
+  void registerArgs();
+
+public:
+  // Turn an enum into the arg name that activates it
+  const char *getArgName(int ID) const;
+  const char *getArgDescription(int ID) const;
+};
+
+class EnumValueBase : public EnumBase {
+protected:
+  int Value;
+  inline EnumValueBase(const char *ArgStr, const char *Help, int Flags)
+    : EnumBase(ArgStr, Help, Flags) {}
+  inline EnumValueBase(int Flags) : EnumBase(Flags) {}
+
+  // handleOccurance - Set Value to the enum value specified by Arg
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+};
+
+template <class E>  // The enum we are representing
+class Enum : public EnumValueBase {
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueRequired;
+  }
+public:
+  inline Enum(const char *ArgStr, int Flags, const char *Help, ...)
+    : EnumValueBase(ArgStr, Help, Flags) {
+    va_list Values;
+    va_start(Values, Help);
+    processValues(Values);
+    va_end(Values);
+    Value = ValueMap.front().second.first; // Grab default value
+  }
+
+  inline operator E() const { return (E)Value; }
+  inline E operator=(E Val) { Value = Val; return Val; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// Enum flags command line option
+//
+class EnumFlagsBase : public EnumValueBase {
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueDisallowed;
+  }
+protected:
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+  inline EnumFlagsBase(int Flags) : EnumValueBase(Flags) {}
+
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+};
+
+template <class E>  // The enum we are representing
+class EnumFlags : public EnumFlagsBase {
+public:
+  inline EnumFlags(int Flags, ...) : EnumFlagsBase(Flags) {
+    va_list Values;
+    va_start(Values, Flags);
+    processValues(Values);
+    va_end(Values);
+    registerArgs();
+    Value = ValueMap.front().second.first; // Grab default value
+  }
+
+  inline operator E() const { return (E)Value; }
+  inline E operator=(E Val) { Value = Val; return Val; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// Enum list command line option
+//
+class EnumListBase : public EnumBase {
+  virtual enum NumOccurances getNumOccurancesFlagDefault() const { 
+    return ZeroOrMore;
+  }
+  virtual enum ValueExpected getValueExpectedFlagDefault() const {
+    return ValueDisallowed;
+  }
+protected:
+  vector<int> Values;  // The options specified so far.
+
+  inline EnumListBase(int Flags) 
+    : EnumBase(Flags) {}
+  virtual bool handleOccurance(const char *ArgName, const string &Arg);
+
+  // Return the width of the option tag for printing...
+  virtual unsigned getOptionWidth() const;
+
+  // printOptionInfo - Print out information about this option.  The 
+  // to-be-maintained width is specified.
+  //
+  virtual void printOptionInfo(unsigned GlobalWidth) const;
+public:
+  inline unsigned size() { return Values.size(); }
+};
+
+template <class E>  // The enum we are representing
+class EnumList : public EnumListBase {
+public:
+  inline EnumList(int Flags, ...) : EnumListBase(Flags) {
+    va_list Values;
+    va_start(Values, Flags);
+    processValues(Values);
+    va_end(Values);
+    registerArgs();
+  }
+  inline E  operator[](unsigned i) const { return (E)Values[i]; }
+  inline E &operator[](unsigned i)       { return (E&)Values[i]; }
+};
+
+} // End namespace cl
+
+#endif
diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h
new file mode 100644
index 0000000000..f3dc3de17b
--- /dev/null
+++ b/include/llvm/Support/MathExtras.h
@@ -0,0 +1,32 @@
+// $Id$ -*-c++-*-
+//***************************************************************************
+// File:
+//	MathExtras.h
+// 
+// Purpose:
+//	
+// History:
+//	8/25/01	 -  Vikram Adve  -  Created
+//**************************************************************************/
+
+#ifndef LLVM_SUPPORT_MATH_EXTRAS_H
+#define LLVM_SUPPORT_MATH_EXTRAS_H
+
+#include <sys/types.h>
+
+inline bool	IsPowerOf2	(int64_t C, unsigned& getPow);
+
+inline
+bool IsPowerOf2(int64_t C, unsigned& getPow)
+{
+  if (C < 0)
+    C = -C;
+  bool isBool = C > 0 && (C == (C & ~(C - 1)));
+  if (isBool)
+    for (getPow = 0; C > 1; getPow++)
+      C = C >> 1;
+  
+  return isBool;
+}
+
+#endif /*LLVM_SUPPORT_MATH_EXTRAS_H*/
diff --git a/include/llvm/Target/TargetFrameInfo.h b/include/llvm/Target/TargetFrameInfo.h
index 4f19cc95c3..df16c730b2 100644
--- a/include/llvm/Target/TargetFrameInfo.h
+++ b/include/llvm/Target/TargetFrameInfo.h
@@ -13,7 +13,7 @@
 #ifndef LLVM_CODEGEN_FRAMEINFO_H
 #define LLVM_CODEGEN_FRAMEINFO_H
 
-#include "llvm/Support/NonCopyable.h"
+#include "Support/NonCopyable.h"
 #include <vector>
 
 
diff --git a/include/llvm/Target/TargetMachine.h b/include/llvm/Target/TargetMachine.h
index 4f0b934bb9..ad1f105958 100644
--- a/include/llvm/Target/TargetMachine.h
+++ b/include/llvm/Target/TargetMachine.h
@@ -8,7 +8,7 @@
 #define LLVM_TARGET_TARGETMACHINE_H
 
 #include "llvm/Target/TargetData.h"
-#include "llvm/Support/NonCopyable.h"
+#include "Support/NonCopyable.h"
 
 class TargetMachine;
 class MachineInstrInfo;
diff --git a/include/llvm/Target/TargetRegInfo.h b/include/llvm/Target/TargetRegInfo.h
index 8f7fad5711..4bd2319d02 100644
--- a/include/llvm/Target/TargetRegInfo.h
+++ b/include/llvm/Target/TargetRegInfo.h
@@ -8,7 +8,7 @@
 #ifndef LLVM_TARGET_MACHINEREGINFO_H
 #define LLVM_TARGET_MACHINEREGINFO_H
 
-#include "llvm/Support/NonCopyable.h"
+#include "Support/NonCopyable.h"
 #include <hash_map>
 #include <string>
 
diff --git a/include/llvm/Type.h b/include/llvm/Type.h
index 04780e9e3c..905aa2d11f 100644
--- a/include/llvm/Type.h
+++ b/include/llvm/Type.h
@@ -27,7 +27,7 @@
 #define LLVM_TYPE_H
 
 #include "llvm/Value.h"
-#include "llvm/Support/GraphTraits.h"
+#include "Support/GraphTraits.h"
 
 class DerivedType;
 class MethodType;