[patch] Adding Consumed Analysis to Clang

[chriswailes]

Summary

This patch adds the beginnings of an analysis that tracks the "consumed" state of objects (this was previously mentioned on the list as uniqueness analysis).

The analysis currently provides enough functionality to detect when a class like std::unique_ptr is dereferenced after it is created with a default constructor. It can also track the state of an object across the branches of an if-statement if the statement contains a single test of a tracked variable. Lastly, the state of a value that is passed as a RValue References to a function is correctly tracked.

Future work, to follow in the next couple of weeks, will include more precise handling of for- and while-loops, support for member functions that consume an object, and tracking of state across function boundaries.

[chriswailes]

Changed the code to correctly test for UO_LNot instead of UO_Not, and removed a leftover print statement. Added a test cast for the negation of a test.

[dblaikie]

Here's a few ideas, mostly micro details. I haven't quite got the macro design sufficiently in my head to respond to that yet.

include/clang/Analysis/Analyses/Consumed.h

40

See the naming conventions for enumerators here: http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

57

Might want to run clang-format over the code, it'll add things like the space for * here (to become "const VarDecl *")

63

Drop the section headers like this - they're not really done in LLVM code so far as I know.

73

Drop 'void' from the parameter list. This isn't necessary in C++ & not prevalent in the LLVM codebase. (see comment below about removing unnecessarily explicit ctor implementations)

74

I assume this should be a const reference parameter (non-const copy constructors are weird)

Better than that - can you just not define either constructor & rely on the defaults? That way you should hopefully get a move ctor for free. (OK, granted DenseMap would have to be movable for that - but that's someone else's problem unless you want to make it yours)

80

Another 'void' in the param list. Consider this general feedback & I won't call out any other instances I see.

include/clang/Basic/DiagnosticSemaKinds.td

2175

Notice that other diagnostics don't begin with an uppercase - they're sentence fragments, not sentences. Rephrase these diagnostics in a similar manner.

If possible, it'd be nice not to talk about "states" explicitly. Perhaps:

"attempt to use '%0' on a consumed object '%1'" ? Open to other wordsmithing...

lib/Analysis/Consumed.cpp

53

more big headers we don't tend to write - file-local functions are basically by definition 'helper functions'.

61

Clang-format should tidy this up, probably dropping the empty lines & maybe one-lining the case+returns (& perhaps outdenting the cases to line up with the switch - at least I think that's LLVM's preferred style)

104

Could do this in the ctor init list with "ModeStack(1, Disabled)" but I don't know if that's much/any better.

Or you could call "reset" to keep the functionality in one place.

150

Could this ever be less than Call->getNumArgs? (perhaps with variadic functions?)

191

consider having a short return with an inverted condition here, then outdenting the body of this instead of having it all inside the 'if'

196

FIXMEs are by definition deferred, so you don't really need "(Deferred)".

200

Another possible early return.

202

& a 3rd

362

(*x).y -> x->y

368

(*x).y -> x->y

383

(*x).y -> x->y

385

Else after return (just write it as "if (x) return; return;" rather than "if (x) return; else return;" )

398

Do you need to erase/insert just to change the value? You should just be able to do it with "I->second = Unknown";

(oh, you'd need the iterators to be non-const iterators)

403

Looks like 'Other' is unconditionally dereferenced and thus cannot be null - perhaps it should be be passed by const reference instead of pointer?

406

For a short scope iterator, consider just calling it 'I'

409

Not strictly unacceptable, but consider not copying this local and just using I->first or I->second. For a short loop I personally find it easier to read as I can quickly spot the "this is the current element" code" when it directly uses the iterator. Open to disagreement/other ideas, though.

413

Unnecessary { on one expression block

415

Unnecessary blank line

417

Could make this one line (& drop the braces) by calling setState?

426

Map[Var] = State; should suffice for this function

444

I'd consider moving this declaration down to just before the loop so it's clearer what it's for (& since it's not needed for the intervening line of code - so this would adhere to the general principle of least scope)

456

It'd be more idiomatic to name this variable "RD".

456

There's a function further down ( ConsumedAnalyzer::run) that starts with a dyn_cast_or_null and then an "if (!D) return" - this seems tidier than nesting the whole body of the function. Consider doing the same here.

459

Microoptimization:

Rather than find+insert, if you use insert here (with a default value for the boolean 'value'), test the second element of the pair returned and then populate the value if it was newly inserted. Something like this might be nice:

std::pair<CacheMapType::iterator, bool> Entry = ConsumableTypeCache.insert(std::make_pair(RD, false));

if (Entry.second)

Entry.first->second = hasConsumableAttributes(*RD);

return Entry.first->second;

(where the loop over the CXXRecordDecl's methods and attributes is pulled out into a 'hasConsumableAttributes' function)

462

-> rather than (*x).y

462

remove {} from one line block

489

Is this fixme still valid? I remember you spoke to me about this issue & thought you'd ended up punting on this & classifying loop blocks as causing an "unspecified" state.

514

Trailing blank line in a block seems strange (& there's a few more blank lines than I'd expect here - could be wrong though. Again, whatever clang-format does, I'm OK with (though I'm not sure it touches blank lines, in which case I'll express some preferences))

524

This indentation isn't really common in LLVM - clang-format should choose appropriately.

531

Unnecessary {}. Once you remove those, clang-format should choose whether to put the return on the same line as the 'if' or a separate line. I forget which way it goes.

566

Any idea how bad this'll hurt the compiler for large functions? I assume we only track variables with these annotations - so we're not going to kill the compiler tomorrow since nothing is annotated, right?

575

Should this case just be moved to the end of this if/else if chain and just be an unconditional 'else'?

(& what happens if there are more than 2 successors? (switch block?))

596

An owning smart pointer would be nice - perhaps CurrStates should be an OwningPtr<T>?

Will this lead to a double-delete when you cleanup the contents of BlockInfo (hmm, don't seem to be cleaning those up at all)? I'd like a bit more clear ownership (perhaps keeping the ConsumedStateMaps directly in the BlockInfo, rather than pointers)

642

just "return Method->hasAttr<TestsUnconsumedAttr>();" instead? Or perhaps skip the function and make this call directly at the callsites if it's sufficiently legible.

lib/Sema/SemaDeclAttr.cpp

1096

not -> !

(& several more)

1109

Comment (& the one up at 1009) seem a bit unnecessary. The function name is self explanatory.

1155

More one-statement blocks with {}

test/SemaCXX/warn-consumed-analysis.cpp

34

I think we should drop the "unnecessary test" warning for now. Feel free to leave a comment where it would go (probably not even to the level of FIXME, just "A warning could be emitted here about a constant test, but care should be taken regarding things such as macro expansions & templates.")

36

I wonder whether there's a way we could make these diagnostics more legible for the unique_ptr case. Could we have some verbs in the attributes? (I guess at that point we'd need a class level attribute for a consumable type - which would make it easier to decide whether a type was consumable (save you the member search). Is there any other way in which we'd benefit from/use a class level attribute?)

46

Line wrapping here is strange (comment, newline escape, then another comment starter?). Generally we don't worry about 80 cols in tests, so you can just remove the line wrapping.

74

As we discussed - unknown state objects should allow all operations (operations allowable only on valid or only on invalid objects)

test/SemaCXX/warn-consumed-parsing.cpp

11

Weird line wrapping again. If you'd really like to put these on separate lines you can use the @-1 notation (check other tests for examples - I think that's the syntax) to refer to lines by offset, rather than the current line.

If you're going to do that, I'd consider putting the comment above the line, rather than below.

[delesley]

Overall, looks good. I'm letting David comment on style issues, and I agree with his other concerns. My comments are specific to the tracking algorithm.

lib/Analysis/Consumed.cpp

284

I don't think this should be a recursive visitor, or possibly even a visitor at all. You are only looking for very specific patterns in the AST, rather than visiting every sub-expression.

413

Note that when merging two maps, if a variable is defined in one map, but not the other, then the variable is no longer in scope. In that case the variable should be removed from the map, rather than added.

492

// TODO: Handle variable definitions, e.g. bool valid = x.isValid(); if (valid) ...; ...;

575

This case should be a general succ_size() > 1 case.

577

Be careful when reusing CurrStates in a new block. You need to remove the pointer from BlockInfo, otherwise a subsequent back-jump to the current block will end up modifying the variable map for some successor to the current block.

582

You need to distinguish here between a successor to a block that you've already processed (which is jump back to the beginning of a loop) and a successor that you haven't yet processed. In the case of backward jump, you shouldn't do an ordinary merge, you should just check that the assumptions at the end of the loop match those on entry.

596

As David mentions, you need to write a destructor for BlockInfo; this is a memory leak.

[chriswailes]

Rewrote the visitor due to the behavior of the CFG traversal. Responded to feedback.

[delesley]

include/clang/Analysis/Analyses/Consumed.h

67

CFG blocks are numbered from 0 to N, so you can save both time and memory by using a vector indexed by the block number, rather than a hash table on the pointer.

70

Again, this should be a BitVector, indexed by the block ID, rather than a set.

lib/Analysis/Consumed.cpp

145

Use getOverloadedOperator() == OO_Equal, rather than string comparisons.

466

Indent by 4?

[chriswailes]

Switched from using DenseSet and DenseMap to a BlockSet and a dynamically allocated array. Moved from using a RecursiveASTVisitor to a StmtVisitor for ConsumedStmtVisitor.

[chriswailes]

Made the code link under release build.

[dblaikie]

This was committed in r188206

include/clang/Analysis/Analyses/Consumed.h

+//===- Consumed.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 checking consumed properties.  This is based,
+// in part, on research on linear types.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_UNIQUENESS_H
+#define LLVM_CLANG_UNIQUENESS_H
+
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/AST/StmtCXX.h"
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Sema/Sema.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace consumed {
+  
+  typedef SmallVector<PartialDiagnosticAt, 1> OptionalNotes;
+  typedef std::pair<PartialDiagnosticAt, OptionalNotes> DelayedDiag;
+  typedef std::list<DelayedDiag> DiagList;
+  
+  enum ConsumedState {
+    // No state information for the given variable.
+    CS_None,
+    
+    CS_Unknown,
+    CS_Unconsumed,
+    CS_Consumed
+  };
+  
+  class ConsumedStateMap {
+    
+    typedef llvm::DenseMap<const VarDecl *, ConsumedState> MapType;
+    typedef std::pair<const VarDecl *, ConsumedState> PairType;
+    
+  protected:
+    
+    MapType Map;
+    
+  public:
+    /// \brief Get the consumed state of a given variable.
+    ConsumedState getState(const VarDecl *Var);
+    
+    /// \brief Merge this state map with another map.
+    void intersect(const ConsumedStateMap *Other);
+    
+    /// \brief Mark all variables as unknown.
+    void makeUnknown();
+    
+    /// \brief Set the consumed state of a given variable.
+    void setState(const VarDecl *Var, ConsumedState State);
+  };
+  
+  class ConsumedBlockInfo {
+    
+    typedef llvm::DenseMap<const CFGBlock *, ConsumedStateMap *> MapType;
+    typedef std::pair<const CFGBlock *, ConsumedStateMap *> PairType;
+    
+    typedef llvm::DenseSet<const CFGBlock *> SetType;
+    
+    MapType Map;
+    SetType VisitedBlocks;
+    
+  public:
+    
+    bool addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap,
+                 bool AlreadyOwned);
+    
+    ConsumedStateMap* getInfo(const CFGBlock *Block);
+    
+    void markVisited(const CFGBlock *Block);
+  };
+  
+  struct VarTestResult {
+    const VarDecl *Var;
+    SourceLocation Loc;
+    bool UnconsumedInTrueBranch;
+    
+    VarTestResult() : Var(NULL), Loc(), UnconsumedInTrueBranch(true) {}
+    
+    VarTestResult(const VarDecl *Var, SourceLocation Loc,
+                  bool UnconsumedInTrueBranch)
+      : Var(Var), Loc(Loc), UnconsumedInTrueBranch(UnconsumedInTrueBranch) {}
+  };
+
+  /// A class that handles the analysis of uniqueness violations.
+  class ConsumedAnalyzer {
+    
+    typedef llvm::DenseMap<const CXXRecordDecl *, bool> CacheMapType;
+    typedef std::pair<const CXXRecordDecl *, bool> CachePairType;
+    
+    Sema &S;
+    
+    DiagList Warnings;
+    SourceLocation FL, FEL;
+    
+    ConsumedBlockInfo BlockInfo;
+    ConsumedStateMap *CurrStates;
+    
+    CacheMapType ConsumableTypeCache;
+    
+    /// \brief Emit the warnings and notes left by the analysis.
+    void emitDiagnostics();
+    bool hasConsumableAttributes(const CXXRecordDecl *RD);
+    void splitState(const CFGBlock *CurrBlock, const IfStmt *Terminator);
+    
+  public:
+
+    ConsumedAnalyzer(Sema &S) : S(S) {}
+    
+    /// \brief Get a constant reference to the Sema object.
+    const Sema & getSema();
+    
+    /// \brief Check to see if the type is a consumable type.
+    bool isConsumableType(QualType Type);
+    
+    /// \brief Check a function's CFG for consumed violations.
+    ///
+    /// We traverse the blocks in the CFG, keeping track of the state of each
+    /// value who's type has uniquness annotations.  If methods are invoked in
+    /// the wrong state a warning is issued.  Each block in the CFG is traversed
+    /// exactly once.
+    void run(AnalysisDeclContext &AC);
+    
+    /// Warn about unnecessary-test errors.
+    /// \param VariableName -- The name of the variable that holds the unique
+    /// value.
+    ///
+    /// \param Loc -- The SourceLocation of the unnecessary test.
+    void warnUnnecessaryTest(StringRef VariableName, StringRef VariableState,
+                             SourceLocation Loc);
+    
+    /// Warn about use-while-consumed errors.
+    /// \param MethodName -- The name of the method that was incorrectly
+    /// invoked.
+    /// 
+    /// \param VariableName -- The name of the variable that holds the unique
+    /// value.
+    ///
+    /// \param Loc -- The SourceLocation of the method invocation.
+    void warnUseOfTempWhileConsumed(StringRef MethodName, SourceLocation Loc);
+    
+    /// Warn about use-in-unknown-state errors.
+    /// \param MethodName -- The name of the method that was incorrectly
+    /// invoked.
+    ///
+    /// \param VariableName -- The name of the variable that holds the unique
+    /// value.
+    ///
+    /// \param Loc -- The SourceLocation of the method invocation.
+    void warnUseOfTempInUnknownState(StringRef MethodName, SourceLocation Loc);
+    
+    /// Warn about use-while-consumed errors.
+    /// \param MethodName -- The name of the method that was incorrectly
+    /// invoked.
+    ///
+    /// \param VariableName -- The name of the variable that holds the unique
+    /// value.
+    ///
+    /// \param Loc -- The SourceLocation of the method invocation.
+    void warnUseWhileConsumed(StringRef MethodName, StringRef VariableName,
+                              SourceLocation Loc);
+    
+    /// Warn about use-in-unknown-state errors.
+    /// \param MethodName -- The name of the method that was incorrectly
+    /// invoked.
+    ///
+    /// \param VariableName -- The name of the variable that holds the unique
+    /// value.
+    ///
+    /// \param Loc -- The SourceLocation of the method invocation.
+    void warnUseInUnknownState(StringRef MethodName, StringRef VariableName,
+                               SourceLocation Loc);
+  };
+  
+  unsigned checkEnabled(DiagnosticsEngine &D);
+  /// \brief Check to see if a function tests an object's validity.
+  bool isTestingFunction(const CXXMethodDecl *MethodDecl);
+  
+}} // end namespace clang::consumed
+
+#endif

include/clang/Basic/Attr.td

   let TemplateDependent = 1;
 }
 
+// C/C++ consumed attributes.
+
+def CallableWhenUnconsumed : InheritableAttr {
+  let Spellings = [GNU<"callable_when_unconsumed">];
+  let Subjects = [CXXMethod];
+}
+
+def TestsUnconsumed : InheritableAttr {
+  let Spellings = [GNU<"tests_unconsumed">];
+  let Subjects = [CXXMethod];
+}
+
+def Consumes : InheritableAttr {
+  let Spellings = [GNU<"consumes">];
+  let Subjects = [CXXMethod];
+}
+
+def CallableAlways : InheritableAttr {
+  let Spellings = [GNU<"callable_always">];
+  let Subjects = [CXXMethod];
+}
+
+def TestsConsumed : InheritableAttr {
+  let Spellings = [GNU<"tests_consumed">];
+  let Subjects = [CXXMethod];
+}
+
 // Type safety attributes for `void *' pointers and type tags.
 
 def ArgumentWithTypeTag : InheritableAttr {

include/clang/Basic/DiagnosticGroups.td

                               ThreadSafetyPrecise]>;
 def ThreadSafetyBeta : DiagGroup<"thread-safety-beta">;
 
+// Uniqueness Analysis warnings
+def Consumed       : DiagGroup<"consumed">;
+def ConsumedStrict : DiagGroup<"consumed-strict", [Consumed]>;
+
 // Note that putting warnings in -Wall will not disable them by default. If a
 // warning should be active _only_ when -Wall is passed in, mark it as
 // DefaultIgnore in addition to putting it here.

include/clang/Basic/DiagnosticSemaKinds.td

 def warn_thread_safety_beta : Warning<
   "Thread safety beta warning.">, InGroup<ThreadSafetyBeta>, DefaultIgnore;
 
+// Consumed warnings
+def warn_use_while_consumed : Warning<
+  "invocation of method '%0' on object '%1' while it is in the 'consumed' "
+  "state">, InGroup<Consumed>, DefaultIgnore;
+def warn_use_of_temp_while_consumed : Warning<
+  "invocation of method '%0' on a temporary object while it is in the "
+  "'consumed' state">, InGroup<Consumed>, DefaultIgnore;
+def warn_uniqueness_attribute_wrong_decl_type : Warning<
+  "%0 attribute only applies to methods">,
+  InGroup<Consumed>, DefaultIgnore;
+
+// ConsumedStrict warnings
+def warn_use_in_unknown_state : Warning<
+  "invocation of method '%0' on object '%1' while it is in an unknown state">,
+  InGroup<ConsumedStrict>, DefaultIgnore;
+def warn_use_of_temp_in_unknown_state : Warning<
+  "invocation of method '%0' on a temporary object while it is in an unknown "
+  "state">, InGroup<ConsumedStrict>, DefaultIgnore;
+def warn_unnecessary_test : Warning<
+  "unnecessary test. Variable '%0' is known to be in the '%1' state">,
+  InGroup<ConsumedStrict>, DefaultIgnore;
+
 def warn_impcast_vector_scalar : Warning<
   "implicit conversion turns vector to scalar: %0 to %1">,
   InGroup<Conversion>, DefaultIgnore;

include/clang/Sema/AnalysisBasedWarnings.h

     unsigned enableCheckFallThrough : 1;
     unsigned enableCheckUnreachable : 1;
     unsigned enableThreadSafetyAnalysis : 1;
+    unsigned enableConsumedAnalysis : 1;
   public:
     Policy();
     void disableCheckFallThrough() { enableCheckFallThrough = 0; }

lib/Analysis/CMakeLists.txt

   CFGStmtMap.cpp
   CallGraph.cpp
   CocoaConventions.cpp
+  Consumed.cpp
   Dominators.cpp
   FormatString.cpp
   LiveVariables.cpp

lib/Analysis/Consumed.cpp

+//===- Consumed.cpp --------------------------------------------*- 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 checking consumed properties.  This is based,
+// in part, on research on linear types.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Attr.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/StmtCXX.h"
+#include "clang/AST/Type.h"
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/Analyses/Consumed.h"
+#include "clang/Basic/OperatorKinds.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Sema/SemaDiagnostic.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace clang;
+using namespace consumed;
+
+// TODO: Mark variables as Consumed going into while- or for-loops only if they
+//       are referenced inside that block. (Deferred)
+// TODO: Support CONSUME methods. (Deferred)
+// TODO: Add a method(s) to identify which method calls perform what state
+//       transitions. (Deferred)
+// TODO: Take notes on state transitions to provide better warning messages.
+//        (Deferred)
+// TODO: Test nested conditionals: A) Checking the same value multiple times,
+//       and 2) Checking different values. (Deferred)
+// TODO: Test IsFalseVisitor with values in the unknown state. (Deferred)
+// TODO: Look into combining IsFalseVisitor and TestedVarsVisitor. (Deferred)
+
+static StringRef stateToString(ConsumedState State) {
+  switch (State) {
+    case consumed::CS_None:
+      return "none";
+    
+    case consumed::CS_Unknown:
+      return "unknown";
+    
+    case consumed::CS_Unconsumed:
+      return "unconsumed";
+    
+    case consumed::CS_Consumed:
+      return "consumed";
+  }
+}
+
+namespace {
+class ConsumedStmtVisitor
+  : public RecursiveASTVisitor<ConsumedStmtVisitor> {
+  
+  union PropagationUnion {
+    ConsumedState State;
+    VarDecl *Var;
+  };
+  
+  class PropagationInfo {
+    PropagationUnion StateOrVar;
+  
+  public:
+    bool IsVar;
+    
+    PropagationInfo() : IsVar(false) {
+      StateOrVar.State = consumed::CS_None;
+    }
+    
+    PropagationInfo(ConsumedState State) : IsVar(false) {
+      StateOrVar.State = State;
+    }
+    
+    PropagationInfo(VarDecl *Var) : IsVar(true) {
+      StateOrVar.Var = Var;
+    }
+    
+    ConsumedState getState() { return StateOrVar.State; };
+    
+    VarDecl * getVar() { return IsVar ? StateOrVar.Var : NULL; };
+  };
+  
+  typedef llvm::DenseMap<Stmt *, PropagationInfo> MapType;
+  typedef std::pair<Stmt *, PropagationInfo> PairType;
+  typedef MapType::iterator InfoEntry;
+  
+  ConsumedAnalyzer &Analyzer;
+  ConsumedStateMap *StateMap;
+  MapType PropagationMap;
+  
+  void forwardInfo(Stmt *From, Stmt *To);
+  bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl);
+  
+public:
+  
+  bool TraverseStmt(Stmt *StmtNode);
+  
+  bool VisitBinaryOperator(BinaryOperator *BinOp);
+  bool VisitCallExpr(CallExpr *Call);
+  bool VisitCastExpr(CastExpr *Cast);
+  bool VisitCXXConstructExpr(CXXConstructExpr *Call);
+  bool VisitCXXMemberCallExpr(CXXMemberCallExpr *Call);
+  bool VisitCXXOperatorCallExpr(CXXOperatorCallExpr *Call);
+  bool VisitDeclRefExpr(DeclRefExpr *DeclRef);
+  bool VisitDeclStmt(DeclStmt *DelcS);
+  bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *Temp);
+  bool VisitMemberExpr(MemberExpr *MExpr);
+  bool VisitUnaryOperator(UnaryOperator *UOp);
+  bool VisitVarDecl(VarDecl *Var);
+  
+  ConsumedStmtVisitor(ConsumedAnalyzer &Analyzer, ConsumedStateMap *StateMap) :
+    Analyzer(Analyzer), StateMap(StateMap) {}
+  
+  void reset() {
+    PropagationMap.clear();
+  }
+};
+
+void ConsumedStmtVisitor::forwardInfo(Stmt *From, Stmt *To) {
+  InfoEntry Entry = PropagationMap.find(From);
+  
+  if (Entry != PropagationMap.end()) {
+    PropagationMap.insert(PairType(To, PropagationInfo(Entry->second)));
+  }
+}
+
+bool ConsumedStmtVisitor::isLikeMoveAssignment(
+  const CXXMethodDecl *MethodDecl) {
+  
+  return MethodDecl->isMoveAssignmentOperator() ||
+         (MethodDecl->getNameAsString() == "operator=" &&
+          MethodDecl->getNumParams()    == 1 &&
+          MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType());
+}
+
+bool ConsumedStmtVisitor::VisitBinaryOperator(BinaryOperator *BinOp) {
+  switch (BinOp->getOpcode()) {
+  case BO_PtrMemD:
+  case BO_PtrMemI:
+    forwardInfo(BinOp->getLHS(), BinOp);
+    break;
+    
+  default:
+    break;
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::TraverseStmt(Stmt *StmtNode) {
+  bool RetVal = RecursiveASTVisitor::TraverseStmt(StmtNode);
+  
+  for (Stmt::child_iterator CI = StmtNode->child_begin(),
+       CE = StmtNode->child_end(); CI != CE; ++CI) {
+    
+    PropagationMap.erase(*CI);
+  }
+  
+  return RetVal;
+}
+
+bool ConsumedStmtVisitor::VisitCallExpr(CallExpr *Call) {
+  if (const FunctionDecl *FunDecl =
+    dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
+    
+    if (const CXXMethodDecl *MethodDecl =
+      dyn_cast_or_null<CXXMethodDecl>(FunDecl)) {
+      
+      if (isLikeMoveAssignment(MethodDecl)) {
+        
+        InfoEntry LEntry = PropagationMap.find(Call->getArg(0));
+        InfoEntry REntry = PropagationMap.find(Call->getArg(1));
+        
+        PropagationInfo LPState, RPState;
+        
+        if (LEntry != PropagationMap.end() &&
+            REntry != PropagationMap.end()) {
+          
+          LPState = LEntry->second;
+          RPState = REntry->second;
+          
+          if (LPState.IsVar && RPState.IsVar) {
+            StateMap->setState(LPState.getVar(),
+              StateMap->getState(RPState.getVar()));
+            
+            StateMap->setState(RPState.getVar(), consumed::CS_Consumed);
+            
+            PropagationMap.insert(PairType(Call, LPState));
+            
+          } else if (LPState.IsVar && !RPState.IsVar) {
+            StateMap->setState(LPState.getVar(), RPState.getState());
+            
+            PropagationMap.insert(PairType(Call, LPState));
+            
+          } else if (!LPState.IsVar && RPState.IsVar) {
+            PropagationMap.insert(PairType(Call,
+              PropagationInfo(StateMap->getState(RPState.getVar()))));
+            
+            StateMap->setState(RPState.getVar(), consumed::CS_Consumed);
+            
+          } else {
+            PropagationMap.insert(PairType(Call, RPState));
+          }
+          
+        } else if (LEntry != PropagationMap.end() &&
+                   REntry == PropagationMap.end()) {
+          
+          LPState = LEntry->second;
+          
+          if (LPState.IsVar) {
+            StateMap->setState(LPState.getVar(), consumed::CS_Unknown);
+            
+            PropagationMap.insert(PairType(Call, LPState));
+            
+          } else {
+            PropagationMap.insert(PairType(Call,
+              PropagationInfo(consumed::CS_Unknown)));
+          }
+          
+        } else if (LEntry == PropagationMap.end() &&
+                   REntry != PropagationMap.end()) {
+          
+          RPState = REntry->second;
+          
+          if (RPState.IsVar) {
+            VarDecl *Var = RPState.getVar();
+            
+            PropagationMap.insert(PairType(Call,
+              PropagationInfo(StateMap->getState(Var))));
+            
+            StateMap->setState(Var, consumed::CS_Consumed);
+            
+          } else {
+            PropagationMap.insert(PairType(Call, RPState));
+          }
+        }
+        
+        return false;
+      }
+    }
+    
+    // Special case for the std::move function.
+    // TODO: Make this more specific. (Deferred)
+    if (FunDecl->getNameAsString() == "move") {
+      InfoEntry Entry = PropagationMap.find(Call->getArg(0));
+      
+      if (Entry != PropagationMap.end()) {
+        PropagationMap.insert(PairType(Call, Entry->second));
+      }
+      
+      return false;
+    }
+    
+    unsigned Offset = !(Call->getNumArgs() == FunDecl->getNumParams());
+    
+    for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) {
+      QualType ParamType = FunDecl->getParamDecl(Index - Offset)->getType();
+      
+      InfoEntry Entry = PropagationMap.find(Call->getArg(Index));
+      
+      if (Entry == PropagationMap.end() || !Entry->second.IsVar) {
+        continue;
+      }
+      
+      PropagationInfo PState = Entry->second;
+      
+      if (ParamType->isRValueReferenceType() ||
+          (ParamType->isLValueReferenceType() &&
+           !cast<LValueReferenceType>(*ParamType).isSpelledAsLValue())) {
+        
+        StateMap->setState(PState.getVar(), consumed::CS_Consumed);
+        
+      } else if (!(ParamType.isConstQualified() ||
+                   ((ParamType->isReferenceType() ||
+                     ParamType->isPointerType()) &&
+                    ParamType->getPointeeType().isConstQualified()))) {
+        
+        StateMap->setState(PState.getVar(), consumed::CS_Unknown);
+      }
+    }
+  }
+  
+  return true;
+}
+
+bool ConsumedStmtVisitor::VisitCastExpr(CastExpr *Cast) {
+  InfoEntry Entry = PropagationMap.find(Cast->getSubExpr());
+  
+  if (Entry != PropagationMap.end()) {
+    PropagationMap.insert(PairType(Cast, Entry->second));
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitCXXConstructExpr(CXXConstructExpr *Call) {
+  CXXConstructorDecl *Constructor = Call->getConstructor();
+  
+  ASTContext &CurrContext = Analyzer.getSema().getASTContext();
+  QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType();
+  
+  if (Analyzer.isConsumableType(ThisType)) {
+    
+    if (Constructor->isDefaultConstructor()) {
+      
+      PropagationMap.insert(PairType(Call,
+        PropagationInfo(consumed::CS_Consumed)));
+      
+    } else if (Constructor->isMoveConstructor()) {
+      
+      PropagationInfo PState =
+        PropagationMap.find(Call->getArg(0))->second;
+      
+      if (PState.IsVar) {
+        VarDecl* Var = PState.getVar();
+        
+        PropagationMap.insert(PairType(Call,
+          PropagationInfo(StateMap->getState(Var))));
+        
+        StateMap->setState(Var, consumed::CS_Consumed);
+        
+      } else {
+        
+        PropagationMap.insert(PairType(Call, PState));
+      }
+        
+    } else if (Constructor->isCopyConstructor()) {
+      MapType::iterator Entry = PropagationMap.find(Call->getArg(0));
+    
+      if (Entry != PropagationMap.end()) {
+        PropagationMap.insert(PairType(Call, Entry->second));
+      }
+      
+    } else {
+      
+      PropagationMap.insert(PairType(Call,
+        PropagationInfo(consumed::CS_Unconsumed)));
+    }
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitCXXMemberCallExpr(CXXMemberCallExpr *Call) {
+  if (!Call->getMethodDecl()->isConst()) {
+    InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens());
+    
+    if (Entry != PropagationMap.end()) {
+      PropagationInfo PState = Entry->second;
+      
+      if (PState.IsVar) {
+        StateMap->setState(PState.getVar(), consumed::CS_Unknown);
+      }
+    }
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitCXXOperatorCallExpr(CXXOperatorCallExpr *Call) {
+  
+  if (const FunctionDecl *FunDecl =
+    dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
+    
+    InfoEntry Entry = PropagationMap.find(Call->getArg(0));
+    
+    if (Entry != PropagationMap.end()) {
+      
+      PropagationInfo PState = Entry->second;
+      
+      // TODO: When we support CallableAlways (or CallableWhenConsumed) this
+      //       will have to check for the different attributes and change the
+      //       behavior bellow. (Deferred)
+      if (FunDecl->hasAttr<CallableWhenUnconsumedAttr>()) {
+        if (PState.IsVar) {
+          VarDecl *Var = PState.getVar();
+          
+          switch (StateMap->getState(Var)) {
+          case CS_Consumed:
+            Analyzer.warnUseWhileConsumed(FunDecl->getNameAsString(),
+              Var->getNameAsString(), Call->getExprLoc());
+            break;
+          
+          case CS_Unknown:
+            Analyzer.warnUseInUnknownState(FunDecl->getNameAsString(),
+              Var->getNameAsString(), Call->getExprLoc());
+            break;
+            
+          default:
+            break;
+          }
+          
+        } else {
+          switch (PState.getState()) {
+          case CS_Consumed:
+            Analyzer.warnUseOfTempWhileConsumed(FunDecl->getNameAsString(),
+              Call->getExprLoc());
+            break;
+          
+          case CS_Unknown:
+            Analyzer.warnUseOfTempInUnknownState(FunDecl->getNameAsString(),
+              Call->getExprLoc());
+            break;
+            
+          default:
+            break;
+          }
+        }
+      }
+      
+      // Handle non-constant member operators.
+      if (const CXXMethodDecl *MethodDecl =
+        dyn_cast_or_null<CXXMethodDecl>(FunDecl)) {
+        
+        if (!MethodDecl->isConst() && PState.IsVar) {
+          StateMap->setState(PState.getVar(), consumed::CS_Unknown);
+        }
+      }
+    }
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
+  if (VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl())) {
+    if (StateMap->getState(Var) != consumed::CS_None) {
+      PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var)));
+    }
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitDeclStmt(DeclStmt *DeclS) {
+  for (DeclStmt::decl_iterator DI = DeclS->decl_begin(), DE = DeclS->decl_end();
+       DI != DE; ++DI) {
+    
+    TraverseDecl(*DI);
+  }
+  
+  if (DeclS->isSingleDecl()) {
+    if (VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl())) {
+      PropagationMap.insert(PairType(DeclS, PropagationInfo(Var)));
+    }
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitMaterializeTemporaryExpr(
+  MaterializeTemporaryExpr *Temp) {
+  
+  InfoEntry Entry = PropagationMap.find(Temp->GetTemporaryExpr());
+  
+  if (Entry != PropagationMap.end()) {
+    PropagationMap.insert(PairType(Temp, Entry->second));
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitMemberExpr(MemberExpr *MExpr) {
+  forwardInfo(MExpr->getBase(), MExpr);
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitUnaryOperator(UnaryOperator *UOp) {
+  
+  if (UOp->getOpcode() == UO_AddrOf) {
+    InfoEntry Entry = PropagationMap.find(UOp->getSubExpr());
+    
+    if (Entry != PropagationMap.end()) {
+      PropagationMap.insert(PairType(UOp, Entry->second));
+    }
+  }
+  
+  return false;
+}
+
+bool ConsumedStmtVisitor::VisitVarDecl(VarDecl *Var) {
+  if (Analyzer.isConsumableType(Var->getType())) {
+    PropagationInfo PState =
+      PropagationMap.find(Var->getInit())->second;
+    
+    StateMap->setState(Var, PState.IsVar ?
+      StateMap->getState(PState.getVar()) : PState.getState());
+  }
+  
+  return false;
+}
+}
+
+namespace {
+struct SortDiagBySourceLocation {
+  SourceManager &SM;
+  SortDiagBySourceLocation(SourceManager &SM) : SM(SM) {}
+
+  bool operator()(const DelayedDiag &Left, const DelayedDiag &Right);
+};
+
+bool SortDiagBySourceLocation::operator()(const DelayedDiag &Left,
+                                          const DelayedDiag &Right) {
+  
+  // Although this call will be slow, this is only called when outputting
+  // multiple warnings.
+  return SM.isBeforeInTranslationUnit(Left.first.first, Right.first.first);
+}
+}
+
+namespace {
+
+// TODO: Handle variable definitions, e.g. bool valid = x.isValid();
+//       if (valid) ...; (Deferred)
+class TestedVarsVisitor : public RecursiveASTVisitor<TestedVarsVisitor> {
+  
+  bool Invert;
+  SourceLocation CurrTestLoc;
+  
+  ConsumedStateMap *StateMap;
+  
+public:
+  bool IsUsefulConditional;
+  VarTestResult Test;
+  
+  TestedVarsVisitor(ConsumedStateMap *StateMap) : Invert(false),
+    StateMap(StateMap), IsUsefulConditional(false) {}
+  
+  bool VisitCallExpr(CallExpr *Call);
+  bool VisitDeclRefExpr(DeclRefExpr *DeclRef);
+  bool VisitUnaryOperator(UnaryOperator *UnaryOp);
+};
+
+bool TestedVarsVisitor::VisitCallExpr(CallExpr *Call) {
+  if (const CXXMethodDecl *Method =
+    dyn_cast_or_null<CXXMethodDecl>(Call->getDirectCallee())) {
+    
+    if (isTestingFunction(Method)) {
+      CurrTestLoc = Call->getExprLoc();
+      IsUsefulConditional = true;
+      return true;
+    }
+    
+    IsUsefulConditional = false;
+  }
+  
+  return false;
+}
+
+bool TestedVarsVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
+  if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl())) {
+    if (StateMap->getState(Var) != consumed::CS_None) {
+      Test = VarTestResult(Var, CurrTestLoc, !Invert);
+    }
+    
+  } else {
+    IsUsefulConditional = false;
+  }
+  
+  return IsUsefulConditional;
+}
+
+bool TestedVarsVisitor::VisitUnaryOperator(UnaryOperator *UnaryOp) {
+  if (UnaryOp->getOpcode() == UO_LNot) {
+    Invert = true;
+    TraverseStmt(UnaryOp->getSubExpr());
+    
+  } else {
+    IsUsefulConditional = false;
+  }
+  
+  return false;
+}
+}
+
+namespace clang {
+namespace consumed {
+
+bool ConsumedBlockInfo::addInfo(const CFGBlock *Block,
+                                ConsumedStateMap *StateMap,
+                                bool AlreadyOwned) {
+  
+  if (VisitedBlocks.find(Block) != VisitedBlocks.end()) {
+    return false;
+  }
+  
+  std::pair<MapType::iterator, bool> Entry = Map.insert(PairType(Block, NULL));
+  
+  if (!Entry.second) {
+    Entry.first->second->intersect(StateMap);
+    
+  } else if (AlreadyOwned) {
+    Entry.first->second = new ConsumedStateMap(*StateMap);
+    
+  } else {
+    Entry.first->second = StateMap;
+    return true;
+  }
+  
+  return false;
+}
+
+ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
+  ConsumedStateMap *RetValue = Map.find(Block)->second;
+  Map.erase(Block);
+  return RetValue;
+}
+
+void ConsumedBlockInfo::markVisited(const CFGBlock *Block) {
+  VisitedBlocks.insert(Block);
+}
+
+ConsumedState ConsumedStateMap::getState(const VarDecl *Var) {
+  MapType::const_iterator Entry = Map.find(Var);
+  
+  if (Entry != Map.end()) {
+    return Entry->second;
+    
+  } else {
+    return CS_None;
+  }
+}
+
+void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
+  ConsumedState LocalState;
+  
+  for (MapType::const_iterator DMI = Other->Map.begin(),
+       DME = Other->Map.end(); DMI != DME; ++DMI) {
+    
+    LocalState = this->getState(DMI->first);
+    
+    if (LocalState != CS_None && LocalState != DMI->second)
+      setState(DMI->first, CS_Unknown);
+  }
+}
+
+void ConsumedStateMap::makeUnknown() {
+  PairType Pair;
+  
+  for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME;
+       ++DMI) {
+    
+    Pair = *DMI;
+    
+    Map.erase(Pair.first);
+    Map.insert(PairType(Pair.first, CS_Unknown));
+  }
+}
+
+void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
+  Map[Var] = State;
+}
+
+const Sema & ConsumedAnalyzer::getSema() {
+  return S;
+}
+
+
+bool ConsumedAnalyzer::isConsumableType(QualType Type) {
+  const CXXRecordDecl *RD =
+    dyn_cast_or_null<CXXRecordDecl>(Type->getAsCXXRecordDecl());
+  
+  if (!RD) return false;
+  
+  std::pair<CacheMapType::iterator, bool> Entry =
+    ConsumableTypeCache.insert(std::make_pair(RD, false));
+  
+  if (Entry.second)
+    Entry.first->second = hasConsumableAttributes(RD);
+  
+  return Entry.first->second;
+}
+
+// TODO: Walk the base classes to see if any of them are unique types.
+//       (Deferred)
+bool ConsumedAnalyzer::hasConsumableAttributes(const CXXRecordDecl *RD) {
+  for (CXXRecordDecl::method_iterator MI = RD->method_begin(),
+       ME = RD->method_end(); MI != ME; ++MI) {
+    
+    for (Decl::attr_iterator AI = (*MI)->attr_begin(), AE = (*MI)->attr_end();
+         AI != AE; ++AI) {
+      
+      switch ((*AI)->getKind()) {
+      case attr::CallableWhenUnconsumed:
+      case attr::TestsUnconsumed:
+        return true;
+      
+      default:
+        break;
+      }
+    }
+  }
+  
+  return false;
+}
+
+// TODO: Handle other forms of branching with precision, including while- and
+//       for-loops. (Deferred)
+void ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock,
+                                  const IfStmt *Terminator) {
+  
+  TestedVarsVisitor Visitor(CurrStates);
+  Visitor.TraverseStmt(const_cast<Expr*>(Terminator->getCond()));
+  
+  bool HasElse = Terminator->getElse() != NULL;
+  
+  ConsumedStateMap *ElseOrMergeStates = new ConsumedStateMap(*CurrStates);
+  
+  if (Visitor.IsUsefulConditional) {
+    ConsumedState VarState = CurrStates->getState(Visitor.Test.Var);
+    
+    if (VarState != CS_Unknown) {
+      // FIXME: Make this not warn if the test is from a macro expansion.
+      //        (Deferred)
+      warnUnnecessaryTest(Visitor.Test.Var->getNameAsString(),
+        stateToString(VarState), Visitor.Test.Loc);
+    }
+    
+    if (Visitor.Test.UnconsumedInTrueBranch) {
+      CurrStates->setState(Visitor.Test.Var, CS_Unconsumed);
+      if (HasElse) ElseOrMergeStates->setState(Visitor.Test.Var, CS_Consumed);
+      
+    } else {
+      CurrStates->setState(Visitor.Test.Var, CS_Consumed);
+      if (HasElse) ElseOrMergeStates->setState(Visitor.Test.Var, CS_Unconsumed);
+    }
+  }
+    
+  CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin();
+  
+  BlockInfo.addInfo(*SI, CurrStates, false);
+  BlockInfo.addInfo(*++SI, ElseOrMergeStates, false);
+}
+
+void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
+  const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl());
+  
+  if (!D) return;
+  
+  FL  = AC.getDecl()->getLocation();
+  FEL = AC.getDecl()->getLocEnd();
+  
+  PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+  
+  CurrStates = new ConsumedStateMap();
+  
+  // Visit all of the function's basic blocks.
+  for (PostOrderCFGView::iterator I = SortedGraph->begin(),
+       E = SortedGraph->end(); I != E; ++I) {
+    
+    const CFGBlock *CurrBlock = *I;
+    BlockInfo.markVisited(CurrBlock);
+    
+    if (CurrStates == NULL) {
+      CurrStates = BlockInfo.getInfo(CurrBlock); 
+    }
+    
+    ConsumedStmtVisitor Visitor(*this, CurrStates);
+    
+    // Visit all of the basic block's statements.
+    for (CFGBlock::const_iterator BI = CurrBlock->begin(),
+         BE = CurrBlock->end(); BI != BE; ++BI) {
+      
+      if (BI->getKind() == CFGElement::Statement) {
+        Stmt *StmtNode = const_cast<Stmt*>(BI->castAs<CFGStmt>().getStmt());
+        
+        Visitor.TraverseStmt(StmtNode);
+      }
+    }
+    
+    // TODO: Remove any variables that have reached the end of their
+    //       lifetimes from the state map. (Deferred)
+    
+    if (const IfStmt *Terminator =
+      dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) {
+      
+      splitState(CurrBlock, Terminator);
+      CurrStates = NULL;
+    
+    } else if (CurrBlock->succ_size() > 1) {
+      CurrStates->makeUnknown();
+      
+      bool OwnershipTaken = false;
+      
+      for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
+           SE = CurrBlock->succ_end(); SI != SE; ++SI) {
+        
+        OwnershipTaken = BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
+      }
+      
+      if (!OwnershipTaken) delete CurrStates;
+      
+      CurrStates = NULL;
+      
+    } else if (CurrBlock->succ_size() == 1 &&
+               (*CurrBlock->succ_begin())->pred_size() > 1) {
+      
+      if (!BlockInfo.addInfo(*CurrBlock->succ_begin(), CurrStates, false))
+        delete CurrStates;
+      
+      CurrStates = NULL;
+    }
+    
+    Visitor.reset();
+  } // End of block iterator.
+  
+  // Delete the last existing state map.
+  delete CurrStates;
+  
+  emitDiagnostics();
+}
+
+/// \brief Emit all buffered diagnostics in order of sourcelocation.
+/// We need to output diagnostics produced while checking operations on
+/// unique types in deterministic order, so this function orders diagnostics
+/// and outputs them.
+void ConsumedAnalyzer::emitDiagnostics() {
+  Warnings.sort(SortDiagBySourceLocation(S.getSourceManager()));
+  
+  for (DiagList::iterator I = Warnings.begin(), E = Warnings.end();
+       I != E; ++I) {
+    
+    const OptionalNotes &Notes = I->second;
+    S.Diag(I->first.first, I->first.second);
+    
+    for (unsigned NoteI = 0, NoteN = Notes.size(); NoteI != NoteN; ++NoteI) {
+      S.Diag(Notes[NoteI].first, Notes[NoteI].second);
+    }
+  }
+}
+
+void ConsumedAnalyzer::warnUnnecessaryTest(StringRef VariableName,
+                                           StringRef VariableState,
+                                           SourceLocation Loc) {
+
+  PartialDiagnosticAt Warning(Loc, S.PDiag(diag::warn_unnecessary_test) <<
+                               VariableName << VariableState);
+  
+  Warnings.push_back(DelayedDiag(Warning, OptionalNotes()));
+}
+
+void ConsumedAnalyzer::warnUseOfTempWhileConsumed(StringRef MethodName,
+                                                  SourceLocation Loc) {
+                                                    
+  PartialDiagnosticAt Warning(Loc, S.PDiag(
+    diag::warn_use_of_temp_while_consumed) << MethodName);
+  
+  Warnings.push_back(DelayedDiag(Warning, OptionalNotes()));
+}
+
+void ConsumedAnalyzer::warnUseOfTempInUnknownState(StringRef MethodName,
+                                                   SourceLocation Loc) {
+  
+  PartialDiagnosticAt Warning(Loc, S.PDiag(
+    diag::warn_use_of_temp_in_unknown_state) << MethodName);
+  
+  Warnings.push_back(DelayedDiag(Warning, OptionalNotes()));
+}
+
+void ConsumedAnalyzer::warnUseWhileConsumed(StringRef MethodName,
+                                            StringRef VariableName,
+                                            SourceLocation Loc) {
+  
+  PartialDiagnosticAt Warning(Loc, S.PDiag(diag::warn_use_while_consumed) <<
+                              MethodName << VariableName);
+  
+  Warnings.push_back(DelayedDiag(Warning, OptionalNotes()));
+}
+
+void ConsumedAnalyzer::warnUseInUnknownState(StringRef MethodName,
+                                             StringRef VariableName,
+                                             SourceLocation Loc) {
+
+  PartialDiagnosticAt Warning(Loc, S.PDiag(diag::warn_use_in_unknown_state) <<
+                              MethodName << VariableName);
+  
+  Warnings.push_back(DelayedDiag(Warning, OptionalNotes()));
+}
+
+unsigned checkEnabled(DiagnosticsEngine &D) {
+  return (unsigned)
+    (D.getDiagnosticLevel(diag::warn_use_while_consumed, SourceLocation()) !=
+     DiagnosticsEngine::Ignored);
+}
+
+bool isTestingFunction(const CXXMethodDecl *Method) {
+  return Method->hasAttr<TestsUnconsumedAttr>();
+}
+
+}} // end namespace clang::consumed

lib/Sema/AnalysisBasedWarnings.cpp

 #include "clang/AST/StmtObjC.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
+#include "clang/Analysis/Analyses/Consumed.h"
 #include "clang/Analysis/Analyses/ReachableCode.h"
 #include "clang/Analysis/Analyses/ThreadSafety.h"
 #include "clang/Analysis/Analyses/UninitializedValues.h"

   enableCheckFallThrough = 1;
   enableCheckUnreachable = 0;
   enableThreadSafetyAnalysis = 0;
+  enableConsumedAnalysis = 0;
 }
 
 clang::sema::AnalysisBasedWarnings::AnalysisBasedWarnings(Sema &s)

   DefaultPolicy.enableThreadSafetyAnalysis = (unsigned)
     (D.getDiagnosticLevel(diag::warn_double_lock, SourceLocation()) !=
      DiagnosticsEngine::Ignored);
+  DefaultPolicy.enableConsumedAnalysis = consumed::checkEnabled(D);
 
 }
 

   // prototyping, but we need a way for analyses to say what expressions they
   // expect to always be CFGElements and then fill in the BuildOptions
   // appropriately.  This is essentially a layering violation.
-  if (P.enableCheckUnreachable || P.enableThreadSafetyAnalysis) {
+  if (P.enableCheckUnreachable || P.enableThreadSafetyAnalysis ||
+      P.enableConsumedAnalysis) {
     // Unreachable code analysis and thread safety require a linearized CFG.
     AC.getCFGBuildOptions().setAllAlwaysAdd();
   }

     Reporter.emitDiagnostics();
   }
 
+  // Check for violations of consumed properties.
+  if (P.enableConsumedAnalysis) {
+    consumed::ConsumedAnalyzer Analyzer(S);
+    Analyzer.run(AC);
+  }
+
   if (Diags.getDiagnosticLevel(diag::warn_uninit_var, D->getLocStart())
       != DiagnosticsEngine::Ignored ||
       Diags.getDiagnosticLevel(diag::warn_sometimes_uninit_var,D->getLocStart())

lib/Sema/SemaDeclAttr.cpp

                                Attr.getAttributeSpellingListIndex()));
 }
 
+static void handleConsumesAttr(Sema &S, Decl *D,
+                               const AttributeList &Attr) {
+  assert(!Attr.isInvalid());
+  if (!checkAttributeNumArgs(S, Attr, 0)) return;
+
+  if (!isa<CXXMethodDecl>(D)) {
+    S.Diag(Attr.getLoc(), diag::warn_uniqueness_attribute_wrong_decl_type) <<
+      Attr.getName();
+    return;
+  }
+  
+  D->addAttr(::new (S.Context)
+             ConsumesAttr(Attr.getRange(), S.Context,
+              Attr.getAttributeSpellingListIndex()));
+}
+
+static void handleCallableAlwaysAttr(Sema &S, Decl *D,
+                                     const AttributeList &Attr) {
+  assert(!Attr.isInvalid());
+  if (!checkAttributeNumArgs(S, Attr, 0)) return;
+
+  if (!isa<CXXMethodDecl>(D)) {
+    S.Diag(Attr.getLoc(), diag::warn_uniqueness_attribute_wrong_decl_type) <<
+      Attr.getName();
+    return;
+  }
+  
+  D->addAttr(::new (S.Context)
+             CallableAlwaysAttr(Attr.getRange(), S.Context,
+              Attr.getAttributeSpellingListIndex()));
+}
+
+static void handleCallableWhenUnconsumedAttr(Sema &S, Decl *D,
+                                             const AttributeList &Attr) {
+  assert(!Attr.isInvalid());
+  if (!checkAttributeNumArgs(S, Attr, 0)) return;
+
+  if (!isa<CXXMethodDecl>(D)) {
+    S.Diag(Attr.getLoc(), diag::warn_uniqueness_attribute_wrong_decl_type) <<
+      Attr.getName();
+    return;
+  }
+  
+  D->addAttr(::new (S.Context)
+             CallableWhenUnconsumedAttr(Attr.getRange(), S.Context,
+              Attr.getAttributeSpellingListIndex()));
+}
+
+static void handleTestsConsumedAttr(Sema &S, Decl *D,
+                                    const AttributeList &Attr) {
+  assert(!Attr.isInvalid());
+  if (!checkAttributeNumArgs(S, Attr, 0)) return;
+
+  if (!isa<CXXMethodDecl>(D)) {
+    S.Diag(Attr.getLoc(), diag::warn_uniqueness_attribute_wrong_decl_type) <<
+      Attr.getName();
+    return;
+  }
+  
+  D->addAttr(::new (S.Context)
+             TestsConsumedAttr(Attr.getRange(), S.Context,
+              Attr.getAttributeSpellingListIndex()));
+}
+
+static void handleTestsUnconsumedAttr(Sema &S, Decl *D,
+                                      const AttributeList &Attr) {
+  assert(!Attr.isInvalid());
+  if (!checkAttributeNumArgs(S, Attr, 0)) return;
+
+  if (!isa<CXXMethodDecl>(D)) {
+    S.Diag(Attr.getLoc(), diag::warn_uniqueness_attribute_wrong_decl_type) <<
+      Attr.getName();
+    return;
+  }
+  
+  D->addAttr(::new (S.Context)
+             TestsUnconsumedAttr(Attr.getRange(), S.Context,
+              Attr.getAttributeSpellingListIndex()));
+}
 
 static void handleExtVectorTypeAttr(Sema &S, Scope *scope, Decl *D,
                                     const AttributeList &Attr) {

     handleAcquiredAfterAttr(S, D, Attr);
     break;
 
+  // Uniqueness analysis attributes.
+  case AttributeList::AT_Consumes:
+    handleConsumesAttr(S, D, Attr);
+    break;
+  case AttributeList::AT_CallableAlways:
+    handleCallableAlwaysAttr(S, D, Attr);
+    break;
+  case AttributeList::AT_CallableWhenUnconsumed:
+    handleCallableWhenUnconsumedAttr(S, D, Attr);
+    break;
+  case AttributeList::AT_TestsConsumed:
+    handleTestsConsumedAttr(S, D, Attr);
+    break;
+  case AttributeList::AT_TestsUnconsumed:
+    handleTestsUnconsumedAttr(S, D, Attr);
+    break;
+
   // Type safety attributes.
   case AttributeList::AT_ArgumentWithTypeTag:
     handleArgumentWithTypeTagAttr(S, D, Attr);

test/SemaCXX/warn-consumed-analysis-strict.cpp

+// RUN: %clang_cc1 -fsyntax-only -verify -Wconsumed-strict -std=c++11 %s
+
+#define CALLABLE_WHEN_UNCONSUMED __attribute__ ((callable_when_unconsumed))
+#define TESTS_UNCONSUMED __attribute__ ((tests_unconsumed))
+
+typedef decltype(nullptr) nullptr_t;
+
+template <typename T>
+class Bar {
+  T var;
+  
+  public:
+  Bar(void);
+  Bar(T val);
+  Bar(Bar<T> &other);
+  Bar(Bar<T> &&other);
+  
+  Bar<T>& operator=(Bar<T>  &other);
+  Bar<T>& operator=(Bar<T> &&other);
+  Bar<T>& operator=(nullptr_t);
+  
+  template <typename U>
+  Bar<T>& operator=(Bar<U>  &other);
+  
+  template <typename U>
+  Bar<T>& operator=(Bar<U> &&other);
+  
+  void operator*() const CALLABLE_WHEN_UNCONSUMED;
+  
+  bool isValid() const TESTS_UNCONSUMED;
+  
+  void constCall() const;
+  void nonconstCall();
+};
+
+void baf0(Bar<int>  &var);
+void baf1(Bar<int>  *var);
+
+void testIfStmt() {
+  Bar<int> var;
+  
+  if (var.isValid()) { // expected-warning {{unnecessary test. Variable 'var' is known to be in the 'consumed' state}}
+    
+    // Empty
+    
+  } else {
+    // Empty
+  }
+}
+
+void testConditionalMerge() {
+  Bar<int> var;
+  
+  if (var.isValid()) {// expected-warning {{unnecessary test. Variable 'var' is known to be in the 'consumed' state}}
+    
+    // Empty
+  }
+  
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+  
+  if (var.isValid()) {
+    // Empty
+    
+  } else {
+    // Empty
+  }
+  
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+}
+
+void testCallingConventions() {
+  Bar<int> var(42);
+  
+  baf0(var);  
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+  
+  var = Bar<int>(42);
+  baf1(&var);  
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+}
+
+void testMoveAsignmentish() {
+  Bar<int> var;
+  
+  var = nullptr;
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+}
+
+void testConstAndNonConstMemberFunctions() {
+  Bar<int> var(42);
+  
+  var.constCall();
+  *var;
+  
+  var.nonconstCall();
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+}
+
+void testSimpleForLoop() {
+  Bar<int> var;
+  
+  for (int i = 0; i < 10; ++i) {
+    *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+  }
+  
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+}
+
+void testSimpleWhileLoop() {
+  int i = 0;
+  
+  Bar<int> var;
+  
+  while (i < 10) {
+    *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+    ++i;
+  }
+  
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in an unknown state}}
+}

test/SemaCXX/warn-consumed-analysis.cpp

+// RUN: %clang_cc1 -fsyntax-only -verify -Wconsumed -std=c++11 %s
+
+#define CALLABLE_WHEN_UNCONSUMED __attribute__ ((callable_when_unconsumed))
+#define TESTS_UNCONSUMED __attribute__ ((tests_unconsumed))
+
+typedef decltype(nullptr) nullptr_t;
+
+template <typename T>
+class Bar {
+  T var;
+  
+  public:
+  Bar(void);
+  Bar(T val);
+  Bar(Bar<T> &other);
+  Bar(Bar<T> &&other);
+  
+  Bar<T>& operator=(Bar<T>  &other);
+  Bar<T>& operator=(Bar<T> &&other);
+  Bar<T>& operator=(nullptr_t);
+  
+  template <typename U>
+  Bar<T>& operator=(Bar<U>  &other);
+  
+  template <typename U>
+  Bar<T>& operator=(Bar<U> &&other);
+  
+  void operator*() const CALLABLE_WHEN_UNCONSUMED;
+  
+  bool isValid() const TESTS_UNCONSUMED;
+  
+  void constCall() const;
+  void nonconstCall();
+};
+
+void baf0(const Bar<int>  var);
+void baf1(const Bar<int> &var);
+void baf2(const Bar<int> *var);
+
+void baf3(Bar<int> &&var);
+
+void testInitialization() {
+  Bar<int> var0;
+  Bar<int> var1 = Bar<int>();
+  
+  var0 = Bar<int>();
+  
+  *var0; // expected-warning {{invocation of method 'operator*' on object 'var0' while it is in the 'consumed' state}}
+  *var1; // expected-warning {{invocation of method 'operator*' on object 'var1' while it is in the 'consumed' state}}
+  
+  if (var0.isValid()) {
+    *var0;
+    *var1;  // expected-warning {{invocation of method 'operator*' on object 'var1' while it is in the 'consumed' state}}
+    
+  } else {
+    *var0;  // expected-warning {{invocation of method 'operator*' on object 'var0' while it is in the 'consumed' state}}
+  }
+}
+
+void testSimpleRValueRefs() {
+  Bar<int> var0;
+  Bar<int> var1(42);
+  
+  *var0; // expected-warning {{invocation of method 'operator*' on object 'var0' while it is in the 'consumed' state}}
+  *var1;
+  
+  var0 = static_cast<Bar<int>&&>(var1);
+  
+  *var0;
+  *var1; // expected-warning {{invocation of method 'operator*' on object 'var1' while it is in the 'consumed' state}}
+}
+
+void testIfStmt() {
+  Bar<int> var;
+  
+  if (var.isValid()) {
+    // Empty
+    
+  } else {
+    *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in the 'consumed' state}}
+  }
+  
+  if (!var.isValid()) {
+    *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in the 'consumed' state}}
+    
+  } else {
+    *var;
+  }
+}
+
+void testCallingConventions() {
+  Bar<int> var(42);
+  
+  baf0(var);  
+  *var;
+  
+  baf1(var);  
+  *var;
+  
+  baf2(&var);  
+  *var;
+  
+  baf3(static_cast<Bar<int>&&>(var));  
+  *var; // expected-warning {{invocation of method 'operator*' on object 'var' while it is in the 'consumed' state}}
+}
+
+void testMoveAsignmentish() {
+  Bar<int>  var0;
+  Bar<long> var1(42);
+  
+  *var0; // expected-warning {{invocation of method 'operator*' on object 'var0' while it is in the 'consumed' state}}
+  *var1;
+  
+  var0 = static_cast<Bar<long>&&>(var1);
+  
+  *var0;
+  *var1; // expected-warning {{invocation of method 'operator*' on object 'var1' while it is in the 'consumed' state}}
+}
+
+void testConditionalMerge() {
+  Bar<int> var;
+  
+  if (var.isValid()) {
+    // Empty
+  }
+  
+  *var;
+  
+  if (var.isValid()) {
+    // Empty
+    
+  } else {
+    // Empty
+  }
+  
+  *var;
+}
+
+void testSimpleForLoop() {
+  Bar<int> var;
+  
+  for (int i = 0; i < 10; ++i) {
+    *var;
+  }
+  
+  *var;
+}
+
+void testSimpleWhileLoop() {
+  int i = 0;
+  
+  Bar<int> var;
+  
+  while (i < 10) {
+    *var;
+    ++i;
+  }
+  
+  *var;
+}

test/SemaCXX/warn-consumed-parsing.cpp

+// RUN: %clang_cc1 -fsyntax-only -verify -Wconsumed -std=c++11 %s
+
+#define CONSUMES                  __attribute__ ((consumes))
+#define TESTS_UNCONSUMED          __attribute__ ((tests_unconsumed))
+#define CALLABLE_ALWAYS           __attribute__ ((callable_always))
+#define CALLABLE_WHEN_UNCONSUMED  __attribute__ ((callable_when_unconsumed))
+
+class AttrTester0 {
+  void Consumes(void)        __attribute__ ((consumes(42))); // \
+  // expected-error {{attribute takes no arguments}}
+  bool TestsUnconsumed(void) __attribute__ ((tests_unconsumed(42))); // \
+  // expected-error {{attribute takes no arguments}}
+  void CallableAlways(void)  __attribute__ ((callable_always(42))); // \
+  // expected-error {{attribute takes no arguments}}
+  void CallableWhenUnconsumed(void) 
+    __attribute__ ((callable_when_unconsumed(42))); // \
+  // expected-error {{attribute takes no arguments}}
+};
+
+int var0 CONSUMES; // \
+\\ expected-warning {{'consumes' attribute only applies to methods}}
+int var1 TESTS_UNCONSUMED; // \
+\\ expected-warning {{'tests_unconsumed' attribute only applies to methods}}
+int var2 CALLABLE_ALWAYS; // \
+\\ expected-warning {{'callable_always' attribute only applies to methods}}
+int var3 CALLABLE_WHEN_UNCONSUMED; // \
+\\ expected-warning {{'callable_when_unconsumed' attribute only applies to methods}}
+
+void function0(void) CONSUMES; // \
+\\ expected-warning {{'consumes' attribute only applies to methods}}
+void function0(void) TESTS_UNCONSUMED; // \
+\\ expected-warning {{'tests_unconsumed' attribute only applies to methods}}
+void function0(void) CALLABLE_ALWAYS; // \
+\\ expected-warning {{'callable_always' attribute only applies to methods}}
+void function0(void) CALLABLE_WHEN_UNCONSUMED; // \
+\\ expected-warning {{'callable_when_unconsumed' attribute only applies to methods}}
+
+class AttrTester1 {
+  void Consumes(void)        CONSUMES;
+  bool TestsUnconsumed(void) TESTS_UNCONSUMED;
+  void CallableAlways(void)  CALLABLE_ALWAYS;
+};
+
+class AttrTester2 {
+  void CallableWhenUnconsumed(void) CALLABLE_WHEN_UNCONSUMED;
+};