Merge branch 'master' of ssh://bitbucket.org/czan/honours

23 files changed, 2651 insertions, 0 deletions

diff --git a/clang/include/clang/Analysis/Analyses/.#Interval.h b/clang/include/clang/Analysis/Analyses/.#Interval.h
new file mode 120000
index 0000000..235903b
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/.#Interval.h
@@ -0,0 +1 @@
+carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file
diff --git a/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h b/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h
new file mode 120000
index 0000000..235903b
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h
@@ -0,0 +1 @@
+carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file
diff --git a/clang/include/clang/Analysis/Analyses/.#LiveVariables.h b/clang/include/clang/Analysis/Analyses/.#LiveVariables.h
new file mode 120000
index 0000000..235903b
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/.#LiveVariables.h
@@ -0,0 +1 @@
+carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file
diff --git a/clang/include/clang/Analysis/Analyses/.#LiveVariables_flymake.h b/clang/include/clang/Analysis/Analyses/.#LiveVariables_flymake.h
new file mode 120000
index 0000000..235903b
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/.#LiveVariables_flymake.h
@@ -0,0 +1 @@
+carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file
diff --git a/clang/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/clang/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h
new file mode 100644
index 0000000..a61d9e4
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h
@@ -0,0 +1,49 @@
+//==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a flow-sensitive, (mostly) path-insensitive reachability
+// analysis based on Clang's CFGs.  Clients can query if a given basic block
+// is reachable within the CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_ANALYSIS_CFG_REACHABILITY
+#define CLANG_ANALYSIS_CFG_REACHABILITY
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace clang {
+
+class CFG;
+class CFGBlock;
+  
+// A class that performs reachability queries for CFGBlocks. Several internal
+// checks in this checker require reachability information. The requests all
+// tend to have a common destination, so we lazily do a predecessor search
+// from the destination node and cache the results to prevent work
+// duplication.
+class CFGReverseBlockReachabilityAnalysis {
+  typedef llvm::BitVector ReachableSet;
+  typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap;
+  ReachableSet analyzed;
+  ReachableMap reachable;
+public:
+  CFGReverseBlockReachabilityAnalysis(const CFG &cfg);
+
+  /// Returns true if the block 'Dst' can be reached from block 'Src'.
+  bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
+
+private:
+  void mapReachability(const CFGBlock *Dst);
+};
+  
+}
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/Dominators.h b/clang/include/clang/Analysis/Analyses/Dominators.h
new file mode 100644
index 0000000..e9a431a
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/Dominators.h
@@ -0,0 +1,212 @@
+//==- Dominators.h - Implementation of dominators tree for Clang CFG C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the dominators tree functionality for Clang CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_DOMINATORS_H
+#define LLVM_CLANG_DOMINATORS_H
+
+#include "clang/Analysis/AnalysisContext.h"
+
+#include "llvm/Module.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/DominatorInternals.h"
+
+namespace clang {
+
+class CFGBlock;
+typedef llvm::DomTreeNodeBase<CFGBlock> DomTreeNode;
+
+/// \brief Concrete subclass of DominatorTreeBase for Clang
+/// This class implements the dominators tree functionality given a Clang CFG.
+///
+class DominatorTree : public ManagedAnalysis {
+  virtual void anchor();
+public:
+  llvm::DominatorTreeBase<CFGBlock>* DT;
+
+  DominatorTree() {
+    DT = new llvm::DominatorTreeBase<CFGBlock>(false);
+  }
+
+  ~DominatorTree() {
+    delete DT;
+  }
+
+  llvm::DominatorTreeBase<CFGBlock>& getBase() { return *DT; }
+
+  /// \brief This method returns the root CFGBlock of the dominators tree.
+  ///
+  inline CFGBlock *getRoot() const {
+    return DT->getRoot();
+  }
+
+  /// \brief This method returns the root DomTreeNode, which is the wrapper
+  /// for CFGBlock.
+  inline DomTreeNode *getRootNode() const {
+    return DT->getRootNode();
+  }
+
+  /// \brief This method compares two dominator trees.
+  /// The method returns false if the other dominator tree matches this
+  /// dominator tree, otherwise returns true.
+  ///
+  inline bool compare(DominatorTree &Other) const {
+    DomTreeNode *R = getRootNode();
+    DomTreeNode *OtherR = Other.getRootNode();
+
+    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
+      return true;
+
+    if (DT->compare(Other.getBase()))
+      return true;
+
+    return false;
+  }
+
+  /// \brief This method builds the dominator tree for a given CFG
+  /// The CFG information is passed via AnalysisDeclContext
+  ///
+  void buildDominatorTree(AnalysisDeclContext &AC) {
+    cfg = AC.getCFG();
+    DT->recalculate(*cfg);
+  }
+
+  /// \brief This method dumps immediate dominators for each block,
+  /// mainly used for debug purposes.
+  ///
+  void dump() {
+    llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
+    for (CFG::const_iterator I = cfg->begin(),
+        E = cfg->end(); I != E; ++I) {
+      if(DT->getNode(*I)->getIDom())
+        llvm::errs() << "(" << (*I)->getBlockID()
+                     << ","
+                     << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
+                     << ")\n";
+      else llvm::errs() << "(" << (*I)->getBlockID()
+                        << "," << (*I)->getBlockID() << ")\n";
+    }
+  }
+
+  /// \brief This method tests if one CFGBlock dominates the other.
+  /// The method return true if A dominates B, false otherwise.
+  /// Note a block always dominates itself.
+  ///
+  inline bool dominates(const CFGBlock* A, const CFGBlock* B) const {
+    return DT->dominates(A, B);
+  }
+
+  /// \brief This method tests if one CFGBlock properly dominates the other.
+  /// The method return true if A properly dominates B, false otherwise.
+  ///
+  bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const {
+    return DT->properlyDominates(A, B);
+  }
+
+  /// \brief This method finds the nearest common dominator CFG block
+  /// for CFG block A and B. If there is no such block then return NULL.
+  ///
+  inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
+    return DT->findNearestCommonDominator(A, B);
+  }
+
+  inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
+                                                      const CFGBlock *B) {
+    return DT->findNearestCommonDominator(A, B);
+  }
+
+  /// \brief This method is used to update the dominator
+  /// tree information when a node's immediate dominator changes.
+  ///
+  inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
+    DT->changeImmediateDominator(N, NewIDom);
+  }
+
+  /// \brief This method tests if the given CFGBlock can be reachable from root.
+  /// Returns true if reachable, false otherwise.
+  ///
+  bool isReachableFromEntry(const CFGBlock *A) {
+    return DT->isReachableFromEntry(A);
+  }
+
+  /// \brief This method releases the memory held by the dominator tree.
+  ///
+  virtual void releaseMemory() {
+    DT->releaseMemory();
+  }
+
+  /// \brief This method converts the dominator tree to human readable form.
+  ///
+  virtual void print(raw_ostream &OS, const llvm::Module* M= 0) const {
+    DT->print(OS);
+  }
+
+private:
+  CFG *cfg;
+};
+
+inline void WriteAsOperand(raw_ostream &OS, const CFGBlock *BB,
+                          bool t) {
+  OS << "BB#" << BB->getBlockID();
+}
+
+} // end namespace clang
+
+//===-------------------------------------
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
+namespace llvm {
+template <> struct GraphTraits< ::clang::DomTreeNode* > {
+  typedef ::clang::DomTreeNode NodeType;
+  typedef NodeType::iterator  ChildIteratorType;
+
+  static NodeType *getEntryNode(NodeType *N) {
+    return N;
+  }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->end();
+  }
+
+  typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator;
+
+  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
+    return df_begin(getEntryNode(N));
+  }
+
+  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
+    return df_end(getEntryNode(N));
+  }
+};
+
+template <> struct GraphTraits< ::clang::DominatorTree* >
+  : public GraphTraits< ::clang::DomTreeNode* > {
+  static NodeType *getEntryNode(::clang::DominatorTree *DT) {
+    return DT->getRootNode();
+  }
+
+  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
+    return df_begin(getEntryNode(N));
+  }
+
+  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
+    return df_end(getEntryNode(N));
+  }
+};
+} // end namespace llvm
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/FormatString.h b/clang/include/clang/Analysis/Analyses/FormatString.h
new file mode 100644
index 0000000..9ec27ce
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/FormatString.h
@@ -0,0 +1,652 @@
+//= FormatString.h - Analysis of printf/fprintf format strings --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines APIs for analyzing the format strings of printf, fscanf,
+// and friends.
+//
+// The structure of format strings for fprintf are described in C99 7.19.6.1.
+//
+// The structure of format strings for fscanf are described in C99 7.19.6.2.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_FORMAT_H
+#define LLVM_CLANG_FORMAT_H
+
+#include "clang/AST/CanonicalType.h"
+
+namespace clang {
+
+//===----------------------------------------------------------------------===//
+/// Common components of both fprintf and fscanf format strings.
+namespace analyze_format_string {
+
+/// Class representing optional flags with location and representation
+/// information.
+class OptionalFlag {
+public:
+  OptionalFlag(const char *Representation)
+      : representation(Representation), flag(false) {}
+  bool isSet() { return flag; }
+  void set() { flag = true; }
+  void clear() { flag = false; }
+  void setPosition(const char *position) {
+    assert(position);
+    this->position = position;
+  }
+  const char *getPosition() const {
+    assert(position);
+    return position;
+  }
+  const char *toString() const { return representation; }
+
+  // Overloaded operators for bool like qualities
+  operator bool() const { return flag; }
+  OptionalFlag& operator=(const bool &rhs) {
+    flag = rhs;
+    return *this;  // Return a reference to myself.
+  }
+private:
+  const char *representation;
+  const char *position;
+  bool flag;
+};
+
+/// Represents the length modifier in a format string in scanf/printf.
+class LengthModifier {
+public:
+  enum Kind {
+    None,
+    AsChar,       // 'hh'
+    AsShort,      // 'h'
+    AsLong,       // 'l'
+    AsLongLong,   // 'll'
+    AsQuad,       // 'q' (BSD, deprecated, for 64-bit integer types)
+    AsIntMax,     // 'j'
+    AsSizeT,      // 'z'
+    AsPtrDiff,    // 't'
+    AsLongDouble, // 'L'
+    AsAllocate,   // for '%as', GNU extension to C90 scanf
+    AsMAllocate,  // for '%ms', GNU extension to scanf
+    AsWideChar = AsLong // for '%ls', only makes sense for printf
+  };
+
+  LengthModifier()
+    : Position(0), kind(None) {}
+  LengthModifier(const char *pos, Kind k)
+    : Position(pos), kind(k) {}
+
+  const char *getStart() const {
+    return Position;
+  }
+
+  unsigned getLength() const {
+    switch (kind) {
+      default:
+        return 1;
+      case AsLongLong:
+      case AsChar:
+        return 2;
+      case None:
+        return 0;
+    }
+  }
+
+  Kind getKind() const { return kind; }
+  void setKind(Kind k) { kind = k; }
+
+  const char *toString() const;
+
+private:
+  const char *Position;
+  Kind kind;
+};
+
+class ConversionSpecifier {
+public:
+  enum Kind {
+    InvalidSpecifier = 0,
+      // C99 conversion specifiers.
+    cArg,
+    dArg,
+    iArg,
+    IntArgBeg = cArg, IntArgEnd = iArg,
+
+    oArg,
+    uArg,
+    xArg,
+    XArg,
+    UIntArgBeg = oArg, UIntArgEnd = XArg,
+
+    fArg,
+    FArg,
+    eArg,
+    EArg,
+    gArg,
+    GArg,
+    aArg,
+    AArg,
+    DoubleArgBeg = fArg, DoubleArgEnd = AArg,
+
+    sArg,
+    pArg,
+    nArg,
+    PercentArg,
+    CArg,
+    SArg,
+
+    // ** Printf-specific **
+
+    // Objective-C specific specifiers.
+    ObjCObjArg,  // '@'
+    ObjCBeg = ObjCObjArg, ObjCEnd = ObjCObjArg,
+
+    // GlibC specific specifiers.
+    PrintErrno,   // 'm'
+
+    PrintfConvBeg = ObjCObjArg, PrintfConvEnd = PrintErrno,
+
+    // ** Scanf-specific **
+    ScanListArg, // '['
+    ScanfConvBeg = ScanListArg, ScanfConvEnd = ScanListArg
+  };
+
+  ConversionSpecifier(bool isPrintf)
+    : IsPrintf(isPrintf), Position(0), EndScanList(0), kind(InvalidSpecifier) {}
+
+  ConversionSpecifier(bool isPrintf, const char *pos, Kind k)
+    : IsPrintf(isPrintf), Position(pos), EndScanList(0), kind(k) {}
+
+  const char *getStart() const {
+    return Position;
+  }
+
+  StringRef getCharacters() const {
+    return StringRef(getStart(), getLength());
+  }
+
+  bool consumesDataArgument() const {
+    switch (kind) {
+      case PrintErrno:
+        assert(IsPrintf);
+      case PercentArg:
+        return false;
+      default:
+        return true;
+    }
+  }
+
+  Kind getKind() const { return kind; }
+  void setKind(Kind k) { kind = k; }
+  unsigned getLength() const {
+    return EndScanList ? EndScanList - Position : 1;
+  }
+
+  bool isUIntArg() const { return kind >= UIntArgBeg && kind <= UIntArgEnd; }
+  const char *toString() const;
+
+  bool isPrintfKind() const { return IsPrintf; }
+
+protected:
+  bool IsPrintf;
+  const char *Position;
+  const char *EndScanList;
+  Kind kind;
+};
+
+class ArgTypeResult {
+public:
+  enum Kind { UnknownTy, InvalidTy, SpecificTy, ObjCPointerTy, CPointerTy,
+              AnyCharTy, CStrTy, WCStrTy, WIntTy };
+private:
+  const Kind K;
+  QualType T;
+  const char *Name;
+  ArgTypeResult(bool) : K(InvalidTy), Name(0) {}
+public:
+  ArgTypeResult(Kind k = UnknownTy) : K(k), Name(0) {}
+  ArgTypeResult(Kind k, const char *n) : K(k), Name(n) {}
+  ArgTypeResult(QualType t) : K(SpecificTy), T(t), Name(0) {}
+  ArgTypeResult(QualType t, const char *n) : K(SpecificTy), T(t), Name(n)  {}
+  ArgTypeResult(CanQualType t) : K(SpecificTy), T(t), Name(0) {}
+
+  static ArgTypeResult Invalid() { return ArgTypeResult(true); }
+
+  bool isValid() const { return K != InvalidTy; }
+
+  const QualType *getSpecificType() const {
+    return K == SpecificTy ? &T : 0;
+  }
+
+  bool matchesType(ASTContext &C, QualType argTy) const;
+
+  bool matchesAnyObjCObjectRef() const { return K == ObjCPointerTy; }
+
+  QualType getRepresentativeType(ASTContext &C) const;
+
+  std::string getRepresentativeTypeName(ASTContext &C) const;
+};
+
+class OptionalAmount {
+public:
+  enum HowSpecified { NotSpecified, Constant, Arg, Invalid };
+
+  OptionalAmount(HowSpecified howSpecified,
+                 unsigned amount,
+                 const char *amountStart,
+                 unsigned amountLength,
+                 bool usesPositionalArg)
+  : start(amountStart), length(amountLength), hs(howSpecified), amt(amount),
+  UsesPositionalArg(usesPositionalArg), UsesDotPrefix(0) {}
+
+  OptionalAmount(bool valid = true)
+  : start(0),length(0), hs(valid ? NotSpecified : Invalid), amt(0),
+  UsesPositionalArg(0), UsesDotPrefix(0) {}
+
+  bool isInvalid() const {
+    return hs == Invalid;
+  }
+
+  HowSpecified getHowSpecified() const { return hs; }
+  void setHowSpecified(HowSpecified h) { hs = h; }
+
+  bool hasDataArgument() const { return hs == Arg; }
+
+  unsigned getArgIndex() const {
+    assert(hasDataArgument());
+    return amt;
+  }
+
+  unsigned getConstantAmount() const {
+    assert(hs == Constant);
+    return amt;
+  }
+
+  const char *getStart() const {
+      // We include the . character if it is given.
+    return start - UsesDotPrefix;
+  }
+
+  unsigned getConstantLength() const {
+    assert(hs == Constant);
+    return length + UsesDotPrefix;
+  }
+
+  ArgTypeResult getArgType(ASTContext &Ctx) const;
+
+  void toString(raw_ostream &os) const;
+
+  bool usesPositionalArg() const { return (bool) UsesPositionalArg; }
+  unsigned getPositionalArgIndex() const {
+    assert(hasDataArgument());
+    return amt + 1;
+  }
+
+  bool usesDotPrefix() const { return UsesDotPrefix; }
+  void setUsesDotPrefix() { UsesDotPrefix = true; }
+
+private:
+  const char *start;
+  unsigned length;
+  HowSpecified hs;
+  unsigned amt;
+  bool UsesPositionalArg : 1;
+  bool UsesDotPrefix;
+};
+
+
+class FormatSpecifier {
+protected:
+  LengthModifier LM;
+  OptionalAmount FieldWidth;
+  ConversionSpecifier CS;
+  /// Positional arguments, an IEEE extension:
+  ///  IEEE Std 1003.1, 2004 Edition
+  ///  http://www.opengroup.org/onlinepubs/009695399/functions/printf.html
+  bool UsesPositionalArg;
+  unsigned argIndex;
+public:
+  FormatSpecifier(bool isPrintf)
+    : CS(isPrintf), UsesPositionalArg(false), argIndex(0) {}
+
+  void setLengthModifier(LengthModifier lm) {
+    LM = lm;
+  }
+
+  void setUsesPositionalArg() { UsesPositionalArg = true; }
+
+  void setArgIndex(unsigned i) {
+    argIndex = i;
+  }
+
+  unsigned getArgIndex() const {
+    return argIndex;
+  }
+
+  unsigned getPositionalArgIndex() const {
+    return argIndex + 1;
+  }
+
+  const LengthModifier &getLengthModifier() const {
+    return LM;
+  }
+
+  const OptionalAmount &getFieldWidth() const {
+    return FieldWidth;
+  }
+
+  void setFieldWidth(const OptionalAmount &Amt) {
+    FieldWidth = Amt;
+  }
+
+  bool usesPositionalArg() const { return UsesPositionalArg; }
+
+  bool hasValidLengthModifier() const;
+
+  bool hasStandardLengthModifier() const;
+
+  bool hasStandardConversionSpecifier(const LangOptions &LangOpt) const;
+
+  bool hasStandardLengthConversionCombination() const;
+};
+
+} // end analyze_format_string namespace
+
+//===----------------------------------------------------------------------===//
+/// Pieces specific to fprintf format strings.
+
+namespace analyze_printf {
+
+class PrintfConversionSpecifier :
+  public analyze_format_string::ConversionSpecifier  {
+public:
+  PrintfConversionSpecifier()
+    : ConversionSpecifier(true, 0, InvalidSpecifier) {}
+
+  PrintfConversionSpecifier(const char *pos, Kind k)
+    : ConversionSpecifier(true, pos, k) {}
+
+  bool isObjCArg() const { return kind >= ObjCBeg && kind <= ObjCEnd; }
+  bool isIntArg() const { return kind >= IntArgBeg && kind <= IntArgEnd; }
+  bool isDoubleArg() const { return kind >= DoubleArgBeg &&
+                                    kind <= DoubleArgEnd; }
+  unsigned getLength() const {
+      // Conversion specifiers currently only are represented by
+      // single characters, but we be flexible.
+    return 1;
+  }
+
+  static bool classof(const analyze_format_string::ConversionSpecifier *CS) {
+    return CS->isPrintfKind();
+  }
+};
+
+using analyze_format_string::ArgTypeResult;
+using analyze_format_string::LengthModifier;
+using analyze_format_string::OptionalAmount;
+using analyze_format_string::OptionalFlag;
+
+class PrintfSpecifier : public analyze_format_string::FormatSpecifier {
+  OptionalFlag HasThousandsGrouping; // ''', POSIX extension.
+  OptionalFlag IsLeftJustified; // '-'
+  OptionalFlag HasPlusPrefix; // '+'
+  OptionalFlag HasSpacePrefix; // ' '
+  OptionalFlag HasAlternativeForm; // '#'
+  OptionalFlag HasLeadingZeroes; // '0'
+  OptionalAmount Precision;
+public:
+  PrintfSpecifier() :
+    FormatSpecifier(/* isPrintf = */ true),
+    HasThousandsGrouping("'"), IsLeftJustified("-"), HasPlusPrefix("+"),
+    HasSpacePrefix(" "), HasAlternativeForm("#"), HasLeadingZeroes("0") {}
+
+  static PrintfSpecifier Parse(const char *beg, const char *end);
+
+    // Methods for incrementally constructing the PrintfSpecifier.
+  void setConversionSpecifier(const PrintfConversionSpecifier &cs) {
+    CS = cs;
+  }
+  void setHasThousandsGrouping(const char *position) {
+    HasThousandsGrouping = true;
+    HasThousandsGrouping.setPosition(position);
+  }
+  void setIsLeftJustified(const char *position) {
+    IsLeftJustified = true;
+    IsLeftJustified.setPosition(position);
+  }
+  void setHasPlusPrefix(const char *position) {
+    HasPlusPrefix = true;
+    HasPlusPrefix.setPosition(position);
+  }
+  void setHasSpacePrefix(const char *position) {
+    HasSpacePrefix = true;
+    HasSpacePrefix.setPosition(position);
+  }
+  void setHasAlternativeForm(const char *position) {
+    HasAlternativeForm = true;
+    HasAlternativeForm.setPosition(position);
+  }
+  void setHasLeadingZeros(const char *position) {
+    HasLeadingZeroes = true;
+    HasLeadingZeroes.setPosition(position);
+  }
+  void setUsesPositionalArg() { UsesPositionalArg = true; }
+
+    // Methods for querying the format specifier.
+
+  const PrintfConversionSpecifier &getConversionSpecifier() const {
+    return cast<PrintfConversionSpecifier>(CS);
+  }
+
+  void setPrecision(const OptionalAmount &Amt) {
+    Precision = Amt;
+    Precision.setUsesDotPrefix();
+  }
+
+  const OptionalAmount &getPrecision() const {
+    return Precision;
+  }
+
+  bool consumesDataArgument() const {
+    return getConversionSpecifier().consumesDataArgument();
+  }
+
+  /// \brief Returns the builtin type that a data argument
+  /// paired with this format specifier should have.  This method
+  /// will return null if the format specifier does not have
+  /// a matching data argument or the matching argument matches
+  /// more than one type.
+  ArgTypeResult getArgType(ASTContext &Ctx, bool IsObjCLiteral) const;
+
+  const OptionalFlag &hasThousandsGrouping() const {
+      return HasThousandsGrouping;
+  }
+  const OptionalFlag &isLeftJustified() const { return IsLeftJustified; }
+  const OptionalFlag &hasPlusPrefix() const { return HasPlusPrefix; }
+  const OptionalFlag &hasAlternativeForm() const { return HasAlternativeForm; }
+  const OptionalFlag &hasLeadingZeros() const { return HasLeadingZeroes; }
+  const OptionalFlag &hasSpacePrefix() const { return HasSpacePrefix; }
+  bool usesPositionalArg() const { return UsesPositionalArg; }
+
+  /// Changes the specifier and length according to a QualType, retaining any
+  /// flags or options. Returns true on success, or false when a conversion
+  /// was not successful.
+  bool fixType(QualType QT, const LangOptions &LangOpt, ASTContext &Ctx,
+               bool IsObjCLiteral);
+
+  void toString(raw_ostream &os) const;
+
+  // Validation methods - to check if any element results in undefined behavior
+  bool hasValidPlusPrefix() const;
+  bool hasValidAlternativeForm() const;
+  bool hasValidLeadingZeros() const;
+  bool hasValidSpacePrefix() const;
+  bool hasValidLeftJustified() const;
+  bool hasValidThousandsGroupingPrefix() const;
+
+  bool hasValidPrecision() const;
+  bool hasValidFieldWidth() const;
+};
+}  // end analyze_printf namespace
+
+//===----------------------------------------------------------------------===//
+/// Pieces specific to fscanf format strings.
+
+namespace analyze_scanf {
+
+class ScanfConversionSpecifier :
+    public analyze_format_string::ConversionSpecifier  {
+public:
+  ScanfConversionSpecifier()
+    : ConversionSpecifier(false, 0, InvalidSpecifier) {}
+
+  ScanfConversionSpecifier(const char *pos, Kind k)
+    : ConversionSpecifier(false, pos, k) {}
+
+  void setEndScanList(const char *pos) { EndScanList = pos; }
+
+  static bool classof(const analyze_format_string::ConversionSpecifier *CS) {
+    return !CS->isPrintfKind();
+  }
+};
+
+using analyze_format_string::ArgTypeResult;
+using analyze_format_string::LengthModifier;
+using analyze_format_string::OptionalAmount;
+using analyze_format_string::OptionalFlag;
+
+class ScanfArgTypeResult : public ArgTypeResult {
+public:
+  enum Kind { UnknownTy, InvalidTy, CStrTy, WCStrTy, PtrToArgTypeResultTy };
+private:
+  Kind K;
+  ArgTypeResult A;
+  const char *Name;
+  QualType getRepresentativeType(ASTContext &C) const;
+public:
+  ScanfArgTypeResult(Kind k = UnknownTy, const char* n = 0) : K(k), Name(n) {}
+  ScanfArgTypeResult(ArgTypeResult a, const char *n = 0)
+      : K(PtrToArgTypeResultTy), A(a), Name(n) {
+    assert(A.isValid());
+  }
+
+  static ScanfArgTypeResult Invalid() { return ScanfArgTypeResult(InvalidTy); }
+
+  bool isValid() const { return K != InvalidTy; }
+
+  bool matchesType(ASTContext& C, QualType argTy) const;
+
+  std::string getRepresentativeTypeName(ASTContext& C) const;
+};
+
+class ScanfSpecifier : public analyze_format_string::FormatSpecifier {
+  OptionalFlag SuppressAssignment; // '*'
+public:
+  ScanfSpecifier() :
+    FormatSpecifier(/* isPrintf = */ false),
+    SuppressAssignment("*") {}
+
+  void setSuppressAssignment(const char *position) {
+    SuppressAssignment = true;
+    SuppressAssignment.setPosition(position);
+  }
+
+  const OptionalFlag &getSuppressAssignment() const {
+    return SuppressAssignment;
+  }
+
+  void setConversionSpecifier(const ScanfConversionSpecifier &cs) {
+    CS = cs;
+  }
+
+  const ScanfConversionSpecifier &getConversionSpecifier() const {
+    return cast<ScanfConversionSpecifier>(CS);
+  }
+
+  bool consumesDataArgument() const {
+    return CS.consumesDataArgument() && !SuppressAssignment;
+  }
+
+  ScanfArgTypeResult getArgType(ASTContext &Ctx) const;
+
+  bool fixType(QualType QT, const LangOptions &LangOpt, ASTContext &Ctx);
+
+  void toString(raw_ostream &os) const;
+
+  static ScanfSpecifier Parse(const char *beg, const char *end);
+};
+
+} // end analyze_scanf namespace
+
+//===----------------------------------------------------------------------===//
+// Parsing and processing of format strings (both fprintf and fscanf).
+
+namespace analyze_format_string {
+
+enum PositionContext { FieldWidthPos = 0, PrecisionPos = 1 };
+
+class FormatStringHandler {
+public:
+  FormatStringHandler() {}
+  virtual ~FormatStringHandler();
+
+  virtual void HandleNullChar(const char *nullCharacter) {}
+
+  virtual void HandlePosition(const char *startPos, unsigned posLen) {}
+
+  virtual void HandleInvalidPosition(const char *startPos, unsigned posLen,
+                                     PositionContext p) {}
+
+  virtual void HandleZeroPosition(const char *startPos, unsigned posLen) {}
+
+  virtual void HandleIncompleteSpecifier(const char *startSpecifier,
+                                         unsigned specifierLen) {}
+
+  // Printf-specific handlers.
+
+  virtual bool HandleInvalidPrintfConversionSpecifier(
+                                      const analyze_printf::PrintfSpecifier &FS,
+                                      const char *startSpecifier,
+                                      unsigned specifierLen) {
+    return true;
+  }
+
+  virtual bool HandlePrintfSpecifier(const analyze_printf::PrintfSpecifier &FS,
+                                     const char *startSpecifier,
+                                     unsigned specifierLen) {
+    return true;
+  }
+
+    // Scanf-specific handlers.
+
+  virtual bool HandleInvalidScanfConversionSpecifier(
+                                        const analyze_scanf::ScanfSpecifier &FS,
+                                        const char *startSpecifier,
+                                        unsigned specifierLen) {
+    return true;
+  }
+
+  virtual bool HandleScanfSpecifier(const analyze_scanf::ScanfSpecifier &FS,
+                                    const char *startSpecifier,
+                                    unsigned specifierLen) {
+    return true;
+  }
+
+  virtual void HandleIncompleteScanList(const char *start, const char *end) {}
+};
+
+bool ParsePrintfString(FormatStringHandler &H,
+                       const char *beg, const char *end, const LangOptions &LO);
+
+bool ParseScanfString(FormatStringHandler &H,
+                      const char *beg, const char *end, const LangOptions &LO);
+
+} // end analyze_format_string namespace
+} // end clang namespace
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/Interval.h b/clang/include/clang/Analysis/Analyses/Interval.h
new file mode 100644
index 0000000..6c0d5cf
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/Interval.h
@@ -0,0 +1,50 @@
+//===- Interval.h - Integer Interval Analysis for Source CFGs     -*- C++ --*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements Live Variables analysis for source-level CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_INTERVAL_ANALYSIS_H
+#define LLVM_CLANG_INTERVAL_ANALYSIS_H
+
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/AST/Decl.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/ImmutableSet.h"
+
+namespace clang {
+
+class CFG;
+class CFGBlock;
+class Stmt;
+class DeclRefExpr;
+class SourceManager;
+  
+class IntervalAnalysis : public ManagedAnalysis {
+public:
+
+  IntervalAnalysis(AnalysisDeclContext &analysisContext);
+  virtual ~IntervalAnalysis();
+
+  void runOnAllBlocks();
+  
+  static IntervalAnalysis *create(AnalysisDeclContext &analysisContext) {
+    return new IntervalAnalysis(analysisContext);
+  }
+  
+  static const void *getTag();
+  
+private:
+  AnalysisDeclContext* context;
+};
+  
+} // end namespace clang
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
new file mode 100644
index 0000000..9acb9d0
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
@@ -0,0 +1,125 @@
+#ifndef COMPLETE_HPP
+#define COMPLETE_HPP
+
+#include <ostream>
+#include <istream>
+
+template<typename T>
+T infinity() { }
+
+template<typename T>
+struct Complete {
+  Complete()
+    : _value(0), _infinity(false) { }
+  Complete(const T& value)
+    : _value(value), _infinity(false) { }
+  Complete(const T& value, const bool& infinity)
+    : _value(value), _infinity(infinity) {
+    assert(value != 0 || infinity == false);
+  }
+  Complete(const Complete& other)
+    : _value(other._value), _infinity(other._infinity) { }
+
+  Complete& operator=(const Complete& other) {
+    _value = other._value;
+    _infinity = other._infinity;
+    return *this;
+  }
+  Complete& operator+=(const Complete& other) {
+    return (*this) = (*this) + other;
+  }
+  Complete& operator-=(const Complete& other) {
+    return (*this) = (*this) - other;
+  }
+  Complete& operator*=(const Complete& other) {
+    return (*this) = (*this) * other;
+  }
+
+  Complete operator-() const {
+    return Complete<T>(- _value, _infinity);
+  }
+  Complete operator+(const Complete& other) const {
+    if (_infinity) {
+      return *this;
+    } else if (other._infinity) {
+      return other;
+    } else {
+      return Complete(_value + other._value, false);
+    }
+  }
+  Complete operator-(const Complete& other) const {
+    return *this + (- other);
+  }
+  Complete operator*(const Complete& other) const {
+    return Complete(_value * other._value, (_infinity || other._infinity));
+  }
+
+  bool operator!() const {
+    return _value == 0;
+  }
+  bool operator<(const Complete& other) const {
+    if (*this == other)
+      return false;
+    if (_infinity) {
+      return _value < 0;
+    } else if (other._infinity) {
+      return other._value > 0;
+    } else {
+      return _value < other._value;
+    }
+  }
+  bool operator>=(const Complete& other) const {
+    return !(*this < other);
+  }
+  bool operator>(const Complete& other) const {
+    return other < *this;
+  }
+  bool operator<=(const Complete& other) const {
+    return !(*this > other);
+  }
+  bool operator==(const Complete& other) const {
+    if (_infinity) {
+      return other._infinity && ((_value < 0 && other._value < 0) ||
+                                 (_value > 0 && other._value > 0));
+    } else {
+      return !other._infinity && (_value == other._value);
+    }
+  }
+  bool operator!=(const Complete& other) const {
+    return !(*this == other);
+  }
+
+  template<typename Z>
+  friend std::istream& operator<<(std::istream&, Complete<Z>&);
+  template<typename Z>
+  friend std::ostream& operator<<(std::ostream&, const Complete<Z>&);
+
+  private:
+  T _value;
+  bool _infinity;
+};
+
+template<typename Z>
+std::istream& operator>>(std::istream& cin, Complete<Z>& num) {
+  Z value;
+  cin >> value;
+  num = Complete<Z>(value, false);
+  return cin;
+}
+
+template<typename Z>
+std::ostream& operator<<(std::ostream& cout, const Complete<Z>& num) {
+  if (num._infinity) {
+    cout << (num._value > 0 ? "inf" : "-inf");
+  } else {
+    cout << num._value;
+  }
+  return cout;
+}
+
+template<>
+Complete<int> infinity() {
+  return Complete<int>(1, true);
+}
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
new file mode 100644
index 0000000..d95366d
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
@@ -0,0 +1,149 @@
+#ifndef EQUATION_SYSTEM_HPP
+#define EQUATION_SYSTEM_HPP
+
+#include <vector>
+#include <set>
+#include <map>
+#include "Operator.hpp"
+#include "Expression.hpp"
+#include "VariableAssignment.hpp"
+#include "IdMap.hpp"
+
+template<typename Domain>
+struct MaxStrategy;
+
+template<typename Domain>
+struct EquationSystem {
+  EquationSystem()
+    : _expr_to_var(NULL) { }
+
+  virtual ~EquationSystem() {
+    for (typename std::set<Expression<Domain>*>::iterator it = _expressions.begin();
+         it != _expressions.end();
+         ++it) {
+      delete *it;
+    }
+    for (typename std::set<Operator<Domain>*>::iterator it = _operators.begin();
+         it != _operators.end();
+         ++it) {
+      delete *it;
+    }
+    delete _expr_to_var;
+  }
+
+  MaxExpression<Domain>& maxExpression(const std::vector<Expression<Domain>*>& arguments) {
+    unsigned int id = _max_expressions.size();
+    Maximum<Domain>* max = new Maximum<Domain>();
+    MaxExpression<Domain>* expr = new MaxExpression<Domain>(id, *max, arguments);
+    _operators.insert(max);
+    _max_expressions.push_back(expr);
+    _expressions.insert(expr);
+    return *expr;
+  }
+  MaxExpression<Domain>& maxExpression(unsigned int i) const {
+    return *_max_expressions[i];
+  }
+  unsigned int maxExpressionCount() const {
+    return _max_expressions.size();
+  }
+
+  Expression<Domain>& expression(Operator<Domain>* op, const std::vector<Expression<Domain>*>& arguments) {
+    Expression<Domain>* expr = new OperatorExpression<Domain>(*op, arguments);
+    _operators.insert(op);
+    _expressions.insert(expr);
+    return *expr;
+  }
+
+  Variable<Domain>& variable(const std::string& name) {
+    if (_variable_names.find(name) == _variable_names.end()) {
+      // not found - create a new variable and whatnot
+      unsigned int id = _variables.size();
+      Variable<Domain>* var = new Variable<Domain>(id, name);
+      _variables.push_back(var);
+      _right_sides.push_back(NULL);
+      _expressions.insert(var);
+      _variable_names[name] = var;
+      return *var;
+    } else {
+      return *_variable_names[name];
+    }
+  }
+  Variable<Domain>& variable(unsigned int id) const {
+    return *_variables[id];
+  }
+  unsigned int variableCount() const {
+    return _variables.size();
+  }
+
+  Constant<Domain>& constant(const Domain& value) {
+    Constant<Domain>* constant = new Constant<Domain>(value);
+    _expressions.insert(constant);
+    return *constant;
+  }
+
+  MaxExpression<Domain>* operator[](const Variable<Domain>& var) const {
+    return _right_sides[var.id()];
+  }
+  MaxExpression<Domain>*& operator[](const Variable<Domain>& var) {
+    return _right_sides[var.id()];
+  }
+
+  void indexMaxExpressions() {
+    _expr_to_var = new IdMap<MaxExpression<Domain>,Variable<Domain>*>(maxExpressionCount(), NULL); 
+    for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) {
+      if (_right_sides[i])
+        _right_sides[i]->mapTo(*_variables[i], *_expr_to_var);
+    }
+  }
+
+  Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+    assert(_expr_to_var != NULL); // ensure we've indexed
+    const MaxExpression<Domain>* maxExpr = expr.toMaxExpression();//dynamic_cast<const MaxExpression<Domain>*>(&expr);
+    if (maxExpr) {
+      return (*_expr_to_var)[*maxExpr];
+    } else {
+      return NULL;
+    }
+  }
+
+  virtual bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
+    for (unsigned int i = 0, length = _variables.size();
+         i < length;
+         ++i) {
+      const Variable<Domain>& var = *_variables[i];
+      if (l[var] != r[var])
+        return false;
+    }
+    return true;
+  }
+
+  void print(std::ostream& cout) const {
+    for (unsigned int i = 0, length = _variables.size();
+         i < length;
+         ++i) {
+      if (_right_sides[i])
+        cout << *_variables[i] << " = " << *_right_sides[i] << std::endl;
+      else
+        cout << *_variables[i] << " = NULL" << std::endl;
+    }
+  }
+
+  private:
+  std::set<Operator<Domain>*> _operators;
+  std::set<Expression<Domain>*> _expressions;
+  std::vector<Variable<Domain>*> _variables;
+  std::map<std::string, Variable<Domain>*> _variable_names;
+  IdMap<MaxExpression<Domain>, Variable<Domain>*>* _expr_to_var;
+  std::vector<MaxExpression<Domain>*> _max_expressions;
+  std::vector<MaxExpression<Domain>*> _right_sides;
+};
+
+template<typename T>
+std::ostream& operator<<(std::ostream& cout, const EquationSystem<T>& system) {
+  system.print(cout);
+  return cout;
+}
+
+#include "MaxStrategy.hpp"
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp
new file mode 100644
index 0000000..ac9b052
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp
@@ -0,0 +1,203 @@
+#ifndef EXPRESSION_HPP
+#define EXPRESSION_HPP
+
+#include <string>
+#include <vector>
+#include <sstream>
+#include "IdMap.hpp"
+#include "Operator.hpp"
+
+template<typename Domain>
+struct VariableAssignment;
+
+template<typename Domain>
+struct MaxStrategy;
+
+template<typename Domain>
+struct Variable;
+
+template<typename Domain>
+struct MaxExpression;
+
+template<typename Domain>
+struct Expression {
+  virtual ~Expression() { }
+
+  virtual const MaxExpression<Domain>* toMaxExpression() const {
+    return NULL;
+  }
+
+  virtual Domain eval(const VariableAssignment<Domain>&) const = 0;
+  virtual Domain evalWithStrat(const VariableAssignment<Domain>& rho,
+                      const MaxStrategy<Domain>&) const {
+    return eval(rho);
+  }
+
+  virtual void mapTo(Variable<Domain>&, IdMap<MaxExpression<Domain>, Variable<Domain>*>&) const {
+  }
+
+  virtual void print(std::ostream&) const = 0;
+};
+
+template<typename Domain>
+struct Constant : public Expression<Domain> {
+  Constant(const Domain& value)
+    : _value(value) { }
+
+  virtual Domain eval(const VariableAssignment<Domain>&) const {
+    return _value;
+  }
+
+  void print(std::ostream& cout) const {
+    cout << _value;
+  }
+
+  private:
+  Domain _value;
+};
+
+template<typename Domain>
+struct Variable : public Expression<Domain> {
+  Variable(const unsigned int& id, const std::string& name)
+    : _id(id), _name(name) { }
+
+  unsigned int id() const {
+    return _id;
+  }
+  std::string name() const {
+    return _name;
+  }
+
+  virtual Domain eval(const VariableAssignment<Domain>& rho) const {
+    return rho[*this];
+  }
+
+  void print(std::ostream& cout) const {
+    cout << _name;
+  }
+
+  private:
+  const unsigned int _id;
+  const std::string _name;
+};
+
+template<typename Domain>
+struct OperatorExpression : public Expression<Domain> {
+  OperatorExpression(const Operator<Domain>& op, const std::vector<Expression<Domain>*>& arguments)
+    : _operator(op), _arguments(arguments) {
+    assert(!arguments.empty());
+  }
+
+  virtual Domain eval(const VariableAssignment<Domain>& rho) const {
+    std::vector<Domain> argumentValues;
+    for (typename std::vector<Expression<Domain>*>::const_iterator it = _arguments.begin();
+         it != _arguments.end();
+         ++it) {
+      argumentValues.push_back((*it)->eval(rho));
+    }
+    return _operator.eval(argumentValues);
+  }
+
+  virtual Domain evalWithStrat(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+    std::vector<Domain> argumentValues;
+    for (typename std::vector<Expression<Domain>*>::const_iterator it = _arguments.begin();
+         it != _arguments.end();
+         ++it) {
+      argumentValues.push_back((*it)->evalWithStrat(rho, strat));
+    }
+    return _operator.eval(argumentValues);
+  }
+
+  std::vector<Expression<Domain>*>& arguments() {
+    return _arguments;
+  }
+
+  const std::vector<Expression<Domain>*>& arguments() const {
+    return _arguments;
+  }
+
+  const Operator<Domain>& op() const {
+    return _operator;
+  }
+
+  virtual void mapTo(Variable<Domain>& v, IdMap<MaxExpression<Domain>, Variable<Domain>*>& m) const {
+    for (unsigned int i = 0, length = _arguments.size();
+         i < length;
+         ++i) {
+      _arguments[i]->mapTo(v, m);
+    }
+  }
+
+  void print(std::ostream& cout) const {
+    cout << _operator << "(";
+    for (unsigned int i = 0, length = _arguments.size();
+         i < length;
+         ++i) {
+      if (i > 0)
+        cout << ", ";
+      cout << *_arguments[i];
+    }
+    cout << ")";
+  }
+
+  private:
+  const Operator<Domain>& _operator;
+  protected:
+  std::vector<Expression<Domain>*> _arguments;
+};
+
+template<typename Domain>
+struct MaxExpression : public OperatorExpression<Domain> {
+  MaxExpression(const unsigned int& id, const Maximum<Domain>& op, const std::vector<Expression<Domain>*>& arguments)
+    : OperatorExpression<Domain>(op, arguments), _id(id) { }
+
+  const MaxExpression* toMaxExpression() const {
+    return this;
+  }
+
+  virtual Domain evalWithStrat(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+    return this->_arguments[strat.get(*this)]->evalWithStrat(rho, strat);
+  }
+
+  unsigned int bestStrategy(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+    Domain bestValue = this->evalWithStrat(rho, strat);
+    unsigned int bestIndex = strat.get(*this);
+
+    for (unsigned int i = 0, length = this->_arguments.size();
+         i < length;
+         ++i) {
+      const Domain value = this->_arguments[i]->evalWithStrat(rho, strat);
+      if (bestValue < value) {
+        bestValue = value;
+        bestIndex = i;
+      }
+    }
+    return bestIndex;
+  }
+
+  virtual void mapTo(Variable<Domain>& v, IdMap<MaxExpression<Domain>, Variable<Domain>*>& m) const {
+    m[*this] = &v;
+    for (unsigned int i = 0, length = this->_arguments.size();
+         i < length;
+         ++i) {
+      this->_arguments[i]->mapTo(v, m);
+    }
+  }
+
+  unsigned int id() const {
+    return _id;
+  }
+
+  private:
+  const unsigned int _id;
+};
+
+template<typename T>
+std::ostream& operator<<(std::ostream& cout, const Expression<T>& exp) {
+  exp.print(cout);
+  return cout;
+}
+
+#include "VariableAssignment.hpp"
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp
new file mode 100644
index 0000000..5e3aa3b
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp
@@ -0,0 +1,82 @@
+#ifndef ID_MAP_HPP
+#define ID_MAP_HPP
+
+#include <ostream>
+
+template<typename T, typename V>
+struct IdMap {
+  IdMap(unsigned int length, V initial)
+    : _length(length), _assignment(new V[length]) {
+    for (unsigned int i = 0; i < length; ++i) {
+      _assignment[i] = initial;
+    }
+  }
+  IdMap(const IdMap& other)
+    : _length(other._length), _assignment(new V[other._length]) {
+    for (unsigned int i = 0; i < _length; ++i) {
+      _assignment[i] = other._assignment[i];
+    }
+  }
+  virtual ~IdMap() {
+    delete[] _assignment;
+  }
+  virtual IdMap& operator=(const IdMap& other) {
+    if (_length != other._length) {
+      delete[] _assignment;
+      _length = other._length;
+      _assignment = new V[_length];
+    }
+    for (unsigned int i = 0; i < _length; ++i) {
+      _assignment[i] = other._assignment[i];
+    }
+    return *this;
+  }
+  virtual const V& operator[] (const T& x) const {
+    if (x.id() >= _length) {
+      std::cout << "throw exception" << *(char*)NULL;
+      //throw "Array out of bounds";
+    }
+    return _assignment[x.id()];
+  }
+  virtual V& operator[] (const T& x) {
+    if (x.id() >= _length) {
+      std::cout << "throw exception" << *(char*)NULL;
+      //throw "Array out of bounds";
+    }
+    return _assignment[x.id()];
+  }
+
+  virtual bool operator==(const IdMap& other) const {
+    if (_length != other._length)
+      return false;
+    for (unsigned int i = 0; i < _length; ++i) {
+      if (_assignment[i] != other._assignment[i]) {
+        return false;
+      }
+    }
+    return true;
+  }
+  virtual bool operator!=(const IdMap& other) const {
+    return !(*this == other);
+  }
+
+  template<typename Q,typename Z>
+  friend std::ostream& operator<<(std::ostream& cout, const IdMap<Q, Z>& rho);
+
+  protected:
+  unsigned int _length;
+  V* _assignment;
+};
+
+template<typename T, typename V>
+std::ostream& operator<<(std::ostream& cout, const IdMap<T,V>& rho) {
+  cout << "{";
+  for (unsigned int i = 0; i < rho._length; ++i) {
+    if (i != 0) cout << ", ";
+    cout << i << ": " << rho._assignment[i];
+  }
+  cout << "}";
+  return cout;
+}
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp
new file mode 100644
index 0000000..950b1e1
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp
@@ -0,0 +1,116 @@
+#ifndef IDSET_HPP
+#define IDSET_HPP
+
+#include <ostream>
+
+#define CELL_TYPE unsigned int 
+#define CELL_SIZE (8 * sizeof(CELL_TYPE))
+#define DIV_ROUND_UP(NUM, DEM) ((NUM + DEM - 1) / DEM)
+
+template<typename T>
+class IdSet {
+  public:
+  IdSet() : _range(0) { }
+  IdSet(unsigned int length)
+    : _range(length) { }
+
+  virtual ~IdSet() {
+  }
+
+  IdSet(const IdSet& other) {
+    _range = other._range;
+    _set = other._set;
+  }
+
+  IdSet& operator=(const IdSet& other) {
+    _range = other._range;
+    _set = other._set;
+    return *this;
+  }
+
+  void invert() {
+    for (unsigned int i = 0; i < _range; ++i) {
+      iterator it = _set.find(i);
+      if (it == _set.end()) {
+        _set.insert(i);
+      } else {
+        _set.erase(it);
+      }
+    }
+  }
+
+  IdSet inverse() const {
+    IdSet other(_range);
+    for (unsigned int i = 0; i < _range; ++i) {
+      if (_set.find(i) == _set.end()) {
+        other._set.insert(i);
+      }
+    }
+    return other;
+  }
+
+  bool contains(const T& obj) const {
+    return _set.find(obj.id()) != _set.end();
+  }
+  void insert(const T& obj) {
+    _set.insert(obj.id());
+  }
+  void remove(const T& obj) {
+    _set.erase(obj.id());
+  }
+  void clear() {
+    _set.clear();
+  }
+
+  void absorb(const IdSet& other) {
+    for (iterator it = other.begin(), end = other.end();
+         it != end;
+         ++it) {
+      _set.insert(*it);
+    }
+  }
+  void filter(const IdSet& other) {
+    for (iterator it = other.begin(), end = other.end();
+         it != end;
+         ++it) {
+      _set.erase(*it);
+    }
+  }
+
+  bool operator==(const IdSet& other) const {
+    return _set == other._set;
+  }
+  bool operator!=(const IdSet& other) const {
+    return !(*this == other);
+  }
+
+  typedef std::set<unsigned int>::const_iterator iterator;
+  iterator begin() const {
+    return _set.begin();
+  }
+  iterator end() const {
+    return _set.end();
+  }
+
+  unsigned int size() const {
+    return _set.size();
+  }
+
+  private:
+  unsigned int _range;
+  std::set<unsigned int> _set;
+};
+
+template<typename T>
+std::ostream& operator<<(std::ostream& cout, const IdSet<T>& set) {
+  cout << "{";
+  for (typename IdSet<T>::iterator it = set.begin();
+       it != set.end();
+       ++it) {
+    cout << *it << ", ";
+  }
+  cout << "}";
+  return cout;
+}
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
new file mode 100644
index 0000000..f9af7f2
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
@@ -0,0 +1,32 @@
+#ifndef LOG_HPP
+#define LOG_HPP
+
+#include <string>
+#include <iostream>
+#include <map>
+#include <cstdio>
+
+namespace solver_log {
+
+  struct Logger : public std::ostream {
+    Logger(std::streambuf*, const std::string&)
+      : std::ostream(NULL) { }
+
+    bool enabled() const {
+      return false;
+    }
+
+    bool enabled(bool) {
+      return false;
+    }
+
+  private:
+  };
+
+  Logger strategy(std::cerr.rdbuf(), "strategy");
+  Logger fixpoint(std::cerr.rdbuf(), "fixpoint");
+  Logger debug(std::cerr.rdbuf(), "debug");
+
+}
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
new file mode 100644
index 0000000..57dcdeb
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
@@ -0,0 +1,156 @@
+#ifndef MAX_EXPRESSION_HPP
+#define MAX_EXPRESSION_HPP
+
+#include <ostream>
+#include "Expression.hpp"
+#include "EquationSystem.hpp"
+#include "IdSet.hpp"
+
+template<typename Domain>
+struct MaxStrategy {
+  virtual ~MaxStrategy() { }
+  virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
+};
+
+unsigned int stack_depth = 1;
+
+std::string indent() {
+  std::string result = "";
+  for (unsigned int i = 0; i < stack_depth; ++i) {
+    result += '\t';
+  }
+  return result;
+}
+
+#include "VariableAssignment.hpp"
+
+template<typename Domain>
+struct DynamicVariableAssignment;
+
+template<typename Domain>
+struct DynamicMaxStrategy : public MaxStrategy<Domain> {
+  DynamicMaxStrategy(
+    const EquationSystem<Domain>& system
+  ) : _system(system),
+      _rho(NULL),
+      _values(system.maxExpressionCount(), 0),
+      _stable(system.maxExpressionCount()),
+      _influence(system.maxExpressionCount(),
+                 IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
+      _var_influence(system.variableCount(),
+                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
+  {}
+
+  void setRho(DynamicVariableAssignment<Domain>& rho) {
+    _rho = &rho;
+  }
+
+  unsigned int get(const MaxExpression<Domain>& e) const {
+    solve(e);
+    return _values[e];
+  }
+
+  void invalidate(const Variable<Domain>& v) const {
+    solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
+    _stable.filter(_var_influence[v]);
+
+    IdSet<MaxExpression<Domain> > infl = _var_influence[v];
+    _var_influence[v].clear();
+
+    for (typename IdSet<MaxExpression<Domain> >::iterator
+           it = infl.begin(),
+           end = infl.end();
+         it != end;
+         ++it) {
+      solve(_system.maxExpression(*it));
+    }
+  }
+
+private:
+  void solve(const MaxExpression<Domain>& x) const {
+    if (!_stable.contains(x)) {
+      _stable.insert(x);
+      solver_log::strategy << indent() << "Stabilise " << x << std::endl;
+
+      stack_depth++;
+      unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
+                                        DependencyStrategy(*this, x));
+      stack_depth--;
+
+      if (val != _values[x]) {
+        solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl;
+
+        IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
+        _influence[x].clear();
+        _values[x] = val;
+
+        _rho->invalidate(*_system.varFromExpr(x));
+
+        _stable.filter(oldInfluence);
+
+        for (typename IdSet<MaxExpression<Domain> >::iterator
+               it = oldInfluence.begin(),
+               end = oldInfluence.end();
+             it != end;
+             ++it) {
+          solve(_system.maxExpression(*it));
+        }
+      } else {
+        solver_log::strategy << indent() << x << " did not change" << std::endl;
+      }
+    } else {
+      solver_log::strategy << indent() << x << " is stable" << std::endl;
+    }
+  }
+
+  struct DependencyAssignment : public VariableAssignment<Domain>{
+    DependencyAssignment(const DynamicMaxStrategy& strat,
+                         VariableAssignment<Domain>& rho,
+                         const MaxExpression<Domain>& expr)
+      : _strat(strat),
+        _rho(rho),
+        _expr(expr) {
+    }
+    const Domain& operator[](const Variable<Domain>& var) const {
+      _strat._var_influence[var].insert(_expr);
+      return _rho[var];
+    }
+  private:
+    const DynamicMaxStrategy& _strat;
+    VariableAssignment<Domain>& _rho;
+    const MaxExpression<Domain>& _expr;
+  };
+
+  struct DependencyStrategy : public MaxStrategy<Domain> {
+    DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+      : _strat(strat),
+        _expr(expr) {
+    }
+    unsigned int get(const MaxExpression<Domain>& e) const {
+      _strat.solve(e);
+      if (&_expr != &e) {
+        _strat._influence[e].insert(_expr);
+      }
+      return _strat._values[e];
+    }
+  private:
+    const DynamicMaxStrategy& _strat;
+    const MaxExpression<Domain>& _expr;
+  };
+
+private:
+  const EquationSystem<Domain>& _system;
+  mutable DynamicVariableAssignment<Domain>* _rho;
+  mutable IdMap<MaxExpression<Domain>,unsigned int> _values;
+  mutable IdSet<MaxExpression<Domain> > _stable;
+  mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
+  mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
+};
+
+/*template<typename Domain>
+std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) {
+  strat.print(cout);
+  return cout;
+}*/
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
new file mode 100644
index 0000000..08c66ff
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
@@ -0,0 +1,173 @@
+#ifndef OPERATOR_HPP
+#define OPERATOR_HPP
+
+#include <vector>
+
+template<typename Domain>
+struct Operator {
+  virtual ~Operator() { }
+
+  virtual Domain eval(const std::vector<Domain>&) const = 0;
+
+  virtual void print(std::ostream&) const = 0;
+};
+
+template<typename Domain>
+struct Maximum : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    Domain result = -infinity<Domain>();
+    for (typename std::vector<Domain>::const_iterator it = arguments.begin();
+         it != arguments.end();
+         ++it) {
+      result = (result < *it ? *it : result);
+    }
+    return result;
+  }
+  void print(std::ostream& cout) const {
+    cout << "max";
+  }
+};
+
+
+template<class T>
+T minimum(const T& l, const T& r) {
+  return (l < r ? l : r);
+}
+template<typename Domain>
+struct Minimum : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    Domain result = infinity<Domain>();
+    for (typename std::vector<Domain>::const_iterator it = arguments.begin();
+         it != arguments.end();
+         ++it) {
+      result = minimum(*it, result); //*it < result ? *it : result);
+    }
+    return result;
+  }
+  void print(std::ostream& cout) const {
+    cout << "min";
+  }
+};
+
+template<typename Domain>
+struct Negation : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    if (arguments.size() > 1)
+      throw "Too many arguments to a negation.";
+    return -arguments[0];
+  }
+  void print(std::ostream& cout) const {
+    cout << "-";
+  }
+};
+
+template<typename Domain>
+struct Addition : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    Domain result = 0;
+    for (typename std::vector<Domain>::const_iterator it = arguments.begin();
+         it != arguments.end();
+         ++it) {
+      result += *it;
+    }
+    return result;
+  }
+  void print(std::ostream& cout) const {
+    cout << "add";
+  }
+};
+
+template<typename Domain>
+struct Subtraction : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    Domain result = 0;
+    for (typename std::vector<Domain>::const_iterator it = arguments.begin();
+         it != arguments.end();
+         ++it) {
+      if (it == arguments.begin())
+        result = *it;
+      else
+        result -= *it;
+    }
+    return result;
+  }
+  void print(std::ostream& cout) const {
+    cout << "sub";
+  }
+};
+
+template<typename Domain>
+struct Multiplication : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    Domain result = 1;
+    for (typename std::vector<Domain>::const_iterator it = arguments.begin(),
+           end = arguments.end();
+         it != end;
+         ++it) {
+      result *= *it;
+    }
+    return result;
+  }
+  void print(std::ostream& cout) const {
+    cout << "mult";
+  }
+};
+
+template<typename Domain>
+struct Comma : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    if (arguments[0] == -infinity<Domain>()) {
+      return -infinity<Domain>();
+    }
+    return arguments[1];
+  }
+  void print(std::ostream& cout) const {
+    cout << "comma";
+  }
+};
+
+template<typename Domain>
+struct Guard : public Operator<Domain> {
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    Domain result = arguments[2];
+    if (arguments[0] < arguments[1]) {
+      result = -infinity<Domain>();
+    }
+    return result;
+  }
+  void print(std::ostream& cout) const {
+    cout << "guard";
+  }
+};
+
+/*#include "TemplateConstraintMatrix.hpp"
+
+template<typename Domain>
+struct MinimumCostFlow : public Operator<Domain> {
+  MinimumCostFlow() {
+  }
+  Domain solve(const Domain& d) const {
+  
+  }
+  virtual Domain eval(const std::vector<Domain>& arguments) const {
+    if (arguments.size() != 1)
+      throw "Incorrect number of arguments.";
+    return solve(arguments[0]);
+  }
+  void print(std::ostream& cout) const {
+    cout << "minCostFlow";
+  }
+private:
+  TemplateConstraintMatrix& constraint; // T
+  std::vector<Domain> guard; // c
+  std::vector<std::vector<Domain>> multiplication; //A
+  unsigned int row;
+};*/
+
+template<typename T>
+std::ostream& operator<<(std::ostream& cout, const Operator<T>& op) {
+  op.print(cout);
+  return cout;
+}
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
new file mode 100644
index 0000000..ba5f650
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
@@ -0,0 +1,104 @@
+#ifndef VARIABLE_ASSIGNMENT_HPP
+#define VARIABLE_ASSIGNMENT_HPP
+
+#include "Expression.hpp"
+#include "IdMap.hpp"
+
+template<typename Domain>
+struct VariableAssignment {
+  virtual ~VariableAssignment() { }
+  virtual const Domain& operator[](const Variable<Domain>&) const = 0;
+};
+
+#include "EquationSystem.hpp"
+
+template<typename Domain>
+struct DynamicMaxStrategy;
+
+template<typename Domain>
+struct DynamicVariableAssignment : public VariableAssignment<Domain> {
+  DynamicVariableAssignment(
+    const EquationSystem<Domain>& system,
+    const DynamicMaxStrategy<Domain>& strat
+  ) : _system(system),
+      _strategy(strat),
+      _values(system.variableCount(), infinity<Domain>()),
+      _stable(system.variableCount()),
+      _influence(system.variableCount(),
+                 IdSet<Variable<Domain> >(system.variableCount()))
+  { }
+
+  const Domain& operator[](const Variable<Domain>& var) const {
+    solve(var);
+    return _values[var];
+  }
+
+  void invalidate(const Variable<Domain>& x) const {
+    solver_log::fixpoint << indent() << "Invalidating " << x << std::endl;
+    if (_stable.contains(x)) {
+      _stable.remove(x);
+      _values[x] = infinity<Domain>();
+      
+      solve(x);
+    }
+  }
+
+private:
+
+  void solve(const Variable<Domain>& x) const {
+    if (!_stable.contains(x)) {
+      _stable.insert(x);
+      solver_log::fixpoint << indent() << "Stabilise " << x << std::endl;
+
+      stack_depth++;
+      if (!_system[x])
+        return;
+      Domain val = _system[x]->evalWithStrat(DependencyAssignment(*this, x),
+					     _strategy);
+      stack_depth--;
+
+      if (val != _values[x]) {
+        solver_log::fixpoint << x << " = " << val << std::endl;
+
+        IdSet<Variable<Domain> > oldInfluence = _influence[x];
+        _influence[x].clear();
+        _values[x] = val;
+
+        _strategy.invalidate(x);
+
+        _stable.filter(oldInfluence);
+
+        for (typename IdSet<Variable<Domain> >::iterator it = oldInfluence.begin();
+             it != oldInfluence.end();
+             ++it) {
+          solve(_system.variable(*it));
+        }
+      } else {
+        solver_log::fixpoint << indent() << x << " did not change" << std::endl;
+      }
+    } else {
+      solver_log::fixpoint << indent() << x << " is stable" << std::endl;
+    }
+  }
+
+  struct DependencyAssignment : public VariableAssignment<Domain> {
+    DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var)
+      : _assignment(assignment), _var(var) { }
+    const Domain& operator[](const Variable<Domain>& x) const {
+      const Domain& result = _assignment[x];
+      _assignment._influence[x].insert(_var);
+      return result;
+    }
+  private:
+    const DynamicVariableAssignment& _assignment;
+    const Variable<Domain>& _var;
+  };
+
+  const EquationSystem<Domain>& _system;
+  const DynamicMaxStrategy<Domain>& _strategy;
+  mutable IdMap<Variable<Domain>, Domain> _values;
+  mutable IdSet<Variable<Domain> > _stable;
+  mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+};
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/LiveVariables.h b/clang/include/clang/Analysis/Analyses/LiveVariables.h
new file mode 100644
index 0000000..c9f39b4
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/LiveVariables.h
@@ -0,0 +1,120 @@
+//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements Live Variables analysis for source-level CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIVEVARIABLES_H
+#define LLVM_CLANG_LIVEVARIABLES_H
+
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/AST/Decl.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/ImmutableSet.h"
+
+namespace clang {
+
+class CFG;
+class CFGBlock;
+class Stmt;
+class DeclRefExpr;
+class SourceManager;
+  
+class LiveVariables : public ManagedAnalysis {
+public:
+  class LivenessValues {
+  public:
+
+    llvm::ImmutableSet<const Stmt *> liveStmts;
+    llvm::ImmutableSet<const VarDecl *> liveDecls;
+    
+    bool equals(const LivenessValues &V) const;
+
+    LivenessValues()
+      : liveStmts(0), liveDecls(0) {}
+
+    LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts,
+                   llvm::ImmutableSet<const VarDecl *> LiveDecls)
+      : liveStmts(LiveStmts), liveDecls(LiveDecls) {}
+
+    ~LivenessValues() {}
+    
+    bool isLive(const Stmt *S) const;
+    bool isLive(const VarDecl *D) const;
+    
+    friend class LiveVariables;    
+  };
+  
+  class Observer {
+    virtual void anchor();
+  public:
+    virtual ~Observer() {}
+    
+    /// A callback invoked right before invoking the
+    ///  liveness transfer function on the given statement.
+    virtual void observeStmt(const Stmt *S,
+                             const CFGBlock *currentBlock,
+                             const LivenessValues& V) {}
+    
+    /// Called when the live variables analysis registers
+    /// that a variable is killed.
+    virtual void observerKill(const DeclRefExpr *DR) {}
+  };    
+
+
+  virtual ~LiveVariables();
+  
+  /// Compute the liveness information for a given CFG.
+  static LiveVariables *computeLiveness(AnalysisDeclContext &analysisContext,
+                                        bool killAtAssign);
+  
+  /// Return true if a variable is live at the end of a
+  /// specified block.
+  bool isLive(const CFGBlock *B, const VarDecl *D);
+  
+  /// Returns true if a variable is live at the beginning of the
+  ///  the statement.  This query only works if liveness information
+  ///  has been recorded at the statement level (see runOnAllBlocks), and
+  ///  only returns liveness information for block-level expressions.
+  bool isLive(const Stmt *S, const VarDecl *D);
+  
+  /// Returns true the block-level expression "value" is live
+  ///  before the given block-level expression (see runOnAllBlocks).
+  bool isLive(const Stmt *Loc, const Stmt *StmtVal);
+    
+  /// Print to stderr the liveness information associated with
+  /// each basic block.
+  void dumpBlockLiveness(const SourceManager& M);
+
+  void runOnAllBlocks(Observer &obs);
+  
+  static LiveVariables *create(AnalysisDeclContext &analysisContext) {
+    return computeLiveness(analysisContext, true);
+  }
+  
+  static const void *getTag();
+  
+private:
+  LiveVariables(void *impl);
+  void *impl;
+};
+  
+class RelaxedLiveVariables : public LiveVariables {
+public:
+  static LiveVariables *create(AnalysisDeclContext &analysisContext) {
+    return computeLiveness(analysisContext, false);
+  }
+  
+  static const void *getTag();
+};
+  
+} // end namespace clang
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h b/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h
new file mode 100644
index 0000000..4e3244e
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h
@@ -0,0 +1,111 @@
+//===- PostOrderCFGView.h - Post order view of CFG blocks ---------*- C++ --*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements post order view of the blocks in a CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_POSTORDER_CFGVIEW
+#define LLVM_CLANG_POSTORDER_CFGVIEW
+
+#include <vector>
+//#include <algorithm>
+
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/BitVector.h"
+
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Analysis/CFG.h"
+
+namespace clang {
+
+class PostOrderCFGView : public ManagedAnalysis {
+  virtual void anchor();
+public:
+  /// \brief Implements a set of CFGBlocks using a BitVector.
+  ///
+  /// This class contains a minimal interface, primarily dictated by the SetType
+  /// template parameter of the llvm::po_iterator template, as used with
+  /// external storage. We also use this set to keep track of which CFGBlocks we
+  /// visit during the analysis.
+  class CFGBlockSet {
+    llvm::BitVector VisitedBlockIDs;
+  public:
+    // po_iterator requires this iterator, but the only interface needed is the
+    // value_type typedef.
+    struct iterator { typedef const CFGBlock *value_type; };
+
+    CFGBlockSet() {}
+    CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
+
+    /// \brief Set the bit associated with a particular CFGBlock.
+    /// This is the important method for the SetType template parameter.
+    bool insert(const CFGBlock *Block) {
+      // Note that insert() is called by po_iterator, which doesn't check to
+      // make sure that Block is non-null.  Moreover, the CFGBlock iterator will
+      // occasionally hand out null pointers for pruned edges, so we catch those
+      // here.
+      if (Block == 0)
+        return false;  // if an edge is trivially false.
+      if (VisitedBlockIDs.test(Block->getBlockID()))
+        return false;
+      VisitedBlockIDs.set(Block->getBlockID());
+      return true;
+    }
+
+    /// \brief Check if the bit for a CFGBlock has been already set.
+    /// This method is for tracking visited blocks in the main threadsafety
+    /// loop. Block must not be null.
+    bool alreadySet(const CFGBlock *Block) {
+      return VisitedBlockIDs.test(Block->getBlockID());
+    }
+  };
+
+private:
+  typedef llvm::po_iterator<const CFG*, CFGBlockSet, true>  po_iterator;
+  std::vector<const CFGBlock*> Blocks;
+
+  typedef llvm::DenseMap<const CFGBlock *, unsigned> BlockOrderTy;
+  BlockOrderTy BlockOrder;
+
+public:
+  typedef std::vector<const CFGBlock*>::reverse_iterator iterator;
+
+  PostOrderCFGView(const CFG *cfg);
+
+  iterator begin() { return Blocks.rbegin(); }
+  iterator end()   { return Blocks.rend(); }
+
+  bool empty() { return begin() == end(); }
+
+  struct BlockOrderCompare;
+  friend struct BlockOrderCompare;
+
+  struct BlockOrderCompare {
+    const PostOrderCFGView &POV;
+  public:
+    BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
+    bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
+  };
+
+  BlockOrderCompare getComparator() const {
+    return BlockOrderCompare(*this);
+  }
+
+  // Used by AnalyisContext to construct this object.
+  static const void *getTag();
+
+  static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
+};
+
+} // end clang namespace
+
+#endif
+
diff --git a/clang/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h b/clang/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h
new file mode 100644
index 0000000..cb73850
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h
@@ -0,0 +1,45 @@
+//== PseudoConstantAnalysis.h - Find Pseudo-constants in the AST -*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file tracks the usage of variables in a Decl body to see if they are
+// never written to, implying that they constant. This is useful in static
+// analysis to see if a developer might have intended a variable to be const.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_PSEUDOCONSTANTANALYSIS
+#define LLVM_CLANG_ANALYSIS_PSEUDOCONSTANTANALYSIS
+
+#include "clang/AST/Stmt.h"
+
+namespace clang {
+
+class PseudoConstantAnalysis {
+public:
+  PseudoConstantAnalysis(const Stmt *DeclBody);
+  ~PseudoConstantAnalysis();
+
+  bool isPseudoConstant(const VarDecl *VD);
+  bool wasReferenced(const VarDecl *VD);
+
+private:
+  void RunAnalysis();
+  inline static const Decl *getDecl(const Expr *E);
+
+  // for storing the result of analyzed ValueDecls
+  void *NonConstantsImpl;
+  void *UsedVarsImpl;
+
+  const Stmt *DeclBody;
+  bool Analyzed;
+};
+
+}
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/ReachableCode.h b/clang/include/clang/Analysis/Analyses/ReachableCode.h
new file mode 100644
index 0000000..30c5b2d
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/ReachableCode.h
@@ -0,0 +1,56 @@
+//===- ReachableCode.h -----------------------------------------*- C++ --*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// A flow-sensitive, path-insensitive analysis of unreachable code.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_REACHABLECODE_H
+#define LLVM_CLANG_REACHABLECODE_H
+
+#include "clang/Basic/SourceLocation.h"
+
+//===----------------------------------------------------------------------===//
+// Forward declarations.
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+  class BitVector;
+}
+
+namespace clang {
+  class AnalysisDeclContext;
+  class CFGBlock;
+}
+
+//===----------------------------------------------------------------------===//
+// API.
+//===----------------------------------------------------------------------===//
+
+namespace clang {
+namespace reachable_code {
+
+class Callback {
+  virtual void anchor();
+public:
+  virtual ~Callback() {}
+  virtual void HandleUnreachable(SourceLocation L, SourceRange R1,
+                                 SourceRange R2) = 0;
+};
+
+/// ScanReachableFromBlock - Mark all blocks reachable from Start.
+/// Returns the total number of blocks that were marked reachable.  
+unsigned ScanReachableFromBlock(const CFGBlock *Start,
+                                llvm::BitVector &Reachable);
+
+void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB);
+
+}} // end namespace clang::reachable_code
+
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafety.h b/clang/include/clang/Analysis/Analyses/ThreadSafety.h
new file mode 100644
index 0000000..26e258d
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/ThreadSafety.h
@@ -0,0 +1,159 @@
+//===- ThreadSafety.h ------------------------------------------*- C++ --*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//
+// A intra-procedural analysis for thread safety (e.g. deadlocks and race
+// conditions), based off of an annotation system.
+//
+// See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more
+// information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_THREADSAFETY_H
+#define LLVM_CLANG_THREADSAFETY_H
+
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace thread_safety {
+
+/// This enum distinguishes between different kinds of operations that may
+/// need to be protected by locks. We use this enum in error handling.
+enum ProtectedOperationKind {
+  POK_VarDereference, /// Dereferencing a variable (e.g. p in *p = 5;)
+  POK_VarAccess, /// Reading or writing a variable (e.g. x in x = 5;)
+  POK_FunctionCall /// Making a function call (e.g. fool())
+};
+
+/// This enum distinguishes between different kinds of lock actions. For
+/// example, it is an error to write a variable protected by shared version of a
+/// mutex.
+enum LockKind {
+  LK_Shared, /// Shared/reader lock of a mutex
+  LK_Exclusive /// Exclusive/writer lock of a mutex
+};
+
+/// This enum distinguishes between different ways to access (read or write) a
+/// variable.
+enum AccessKind {
+  AK_Read, /// Reading a variable
+  AK_Written /// Writing a variable
+};
+
+/// This enum distinguishes between different situations where we warn due to
+/// inconsistent locking.
+/// \enum SK_LockedSomeLoopIterations -- a mutex is locked for some but not all
+/// loop iterations.
+/// \enum SK_LockedSomePredecessors -- a mutex is locked in some but not all
+/// predecessors of a CFGBlock.
+/// \enum SK_LockedAtEndOfFunction -- a mutex is still locked at the end of a
+/// function.
+enum LockErrorKind {
+  LEK_LockedSomeLoopIterations,
+  LEK_LockedSomePredecessors,
+  LEK_LockedAtEndOfFunction
+};
+
+/// Handler class for thread safety warnings.
+class ThreadSafetyHandler {
+public:
+  typedef llvm::StringRef Name;
+  virtual ~ThreadSafetyHandler();
+
+  /// Warn about lock expressions which fail to resolve to lockable objects.
+  /// \param Loc -- the SourceLocation of the unresolved expression.
+  virtual void handleInvalidLockExp(SourceLocation Loc) {}
+
+  /// Warn about unlock function calls that do not have a prior matching lock
+  /// expression.
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Loc -- The SourceLocation of the Unlock
+  virtual void handleUnmatchedUnlock(Name LockName, SourceLocation Loc) {}
+
+  /// Warn about lock function calls for locks which are already held.
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Loc -- The location of the second lock expression.
+  virtual void handleDoubleLock(Name LockName, SourceLocation Loc) {}
+
+  /// Warn about situations where a mutex is sometimes held and sometimes not.
+  /// The three situations are:
+  /// 1. a mutex is locked on an "if" branch but not the "else" branch,
+  /// 2, or a mutex is only held at the start of some loop iterations,
+  /// 3. or when a mutex is locked but not unlocked inside a function.
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param LocLocked -- The location of the lock expression where the mutex is
+  ///               locked
+  /// \param LocEndOfScope -- The location of the end of the scope where the
+  ///               mutex is no longer held
+  /// \param LEK -- which of the three above cases we should warn for
+  virtual void handleMutexHeldEndOfScope(Name LockName,
+                                         SourceLocation LocLocked,
+                                         SourceLocation LocEndOfScope,
+                                         LockErrorKind LEK){}
+
+  /// Warn when a mutex is held exclusively and shared at the same point. For
+  /// example, if a mutex is locked exclusively during an if branch and shared
+  /// during the else branch.
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Loc1 -- The location of the first lock expression.
+  /// \param Loc2 -- The location of the second lock expression.
+  virtual void handleExclusiveAndShared(Name LockName, SourceLocation Loc1,
+                                        SourceLocation Loc2) {}
+
+  /// Warn when a protected operation occurs while no locks are held.
+  /// \param D -- The decl for the protected variable or function
+  /// \param POK -- The kind of protected operation (e.g. variable access)
+  /// \param AK -- The kind of access (i.e. read or write) that occurred
+  /// \param Loc -- The location of the protected operation.
+  virtual void handleNoMutexHeld(const NamedDecl *D, ProtectedOperationKind POK,
+                                 AccessKind AK, SourceLocation Loc) {}
+
+  /// Warn when a protected operation occurs while the specific mutex protecting
+  /// the operation is not locked.
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param D -- The decl for the protected variable or function
+  /// \param POK -- The kind of protected operation (e.g. variable access)
+  /// \param AK -- The kind of access (i.e. read or write) that occurred
+  /// \param Loc -- The location of the protected operation.
+  virtual void handleMutexNotHeld(const NamedDecl *D,
+                                  ProtectedOperationKind POK, Name LockName,
+                                  LockKind LK, SourceLocation Loc) {}
+
+  /// Warn when a function is called while an excluded mutex is locked. For
+  /// example, the mutex may be locked inside the function.
+  /// \param FunName -- The name of the function
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Loc -- The location of the function call.
+  virtual void handleFunExcludesLock(Name FunName, Name LockName,
+                                     SourceLocation Loc) {}
+};
+
+/// \brief Check a function's CFG for thread-safety violations.
+///
+/// We traverse the blocks in the CFG, compute the set of mutexes that are held
+/// at the end of each block, and issue warnings for thread safety violations.
+/// Each block in the CFG is traversed exactly once.
+void runThreadSafetyAnalysis(AnalysisDeclContext &AC,
+                             ThreadSafetyHandler &Handler);
+
+/// \brief Helper function that returns a LockKind required for the given level
+/// of access.
+LockKind getLockKindFromAccessKind(AccessKind AK);
+
+}} // end namespace clang::thread_safety
+#endif
diff --git a/clang/include/clang/Analysis/Analyses/UninitializedValues.h b/clang/include/clang/Analysis/Analyses/UninitializedValues.h
new file mode 100644
index 0000000..4ee6698
--- /dev/null
+++ b/clang/include/clang/Analysis/Analyses/UninitializedValues.h
@@ -0,0 +1,53 @@
+//= UninitializedValues.h - Finding uses of uninitialized values -*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines APIs for invoking and reported uninitialized values
+// warnings.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_UNINIT_VALS_H
+#define LLVM_CLANG_UNINIT_VALS_H
+
+namespace clang {
+
+class AnalysisDeclContext;
+class CFG;
+class DeclContext;
+class Expr;
+class VarDecl;
+
+class UninitVariablesHandler {
+public:
+  UninitVariablesHandler() {}
+  virtual ~UninitVariablesHandler();
+
+  /// Called when the uninitialized variable is used at the given expression.
+  virtual void handleUseOfUninitVariable(const Expr *ex,
+                                         const VarDecl *vd,
+                                         bool isAlwaysUninit) {}
+
+  /// Called when the uninitialized variable analysis detects the
+  /// idiom 'int x = x'.  All other uses of 'x' within the initializer
+  /// are handled by handleUseOfUninitVariable.
+  virtual void handleSelfInit(const VarDecl *vd) {}
+};
+
+struct UninitVariablesAnalysisStats {
+  unsigned NumVariablesAnalyzed;
+  unsigned NumBlockVisits;
+};
+
+void runUninitializedVariablesAnalysis(const DeclContext &dc, const CFG &cfg,
+                                       AnalysisDeclContext &ac,
+                                       UninitVariablesHandler &handler,
+                                       UninitVariablesAnalysisStats &stats);
+
+}
+#endif