diff options
Diffstat (limited to 'include/clang/Analysis')
20 files changed, 1547 insertions, 752 deletions
diff --git a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h index cc14c7bd33db..da59514c4fa6 100644 --- a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h +++ b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h @@ -1,4 +1,4 @@ -//==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- C++ -*-==// +//===- CFGReachabilityAnalysis.h - Basic reachability analysis --*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -30,10 +30,12 @@ class CFGBlock; // from the destination node and cache the results to prevent work // duplication. class CFGReverseBlockReachabilityAnalysis { - typedef llvm::BitVector ReachableSet; - typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap; + using ReachableSet = llvm::BitVector; + using ReachableMap = llvm::DenseMap<unsigned, ReachableSet>; + ReachableSet analyzed; ReachableMap reachable; + public: CFGReverseBlockReachabilityAnalysis(const CFG &cfg); @@ -44,6 +46,6 @@ private: void mapReachability(const CFGBlock *Dst); }; -} +} // namespace clang -#endif +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H diff --git a/include/clang/Analysis/Analyses/Consumed.h b/include/clang/Analysis/Analyses/Consumed.h index 5ba42b475c83..6003d665fd88 100644 --- a/include/clang/Analysis/Analyses/Consumed.h +++ b/include/clang/Analysis/Analyses/Consumed.h @@ -1,4 +1,4 @@ -//===- Consumed.h ----------------------------------------------*- C++ --*-===// +//===- Consumed.h -----------------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,16 +15,32 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H #define LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H -#include "clang/AST/DeclCXX.h" -#include "clang/AST/ExprCXX.h" -#include "clang/AST/StmtCXX.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" -#include "clang/Analysis/AnalysisDeclContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Basic/LLVM.h" +#include "clang/Basic/PartialDiagnostic.h" #include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include <list> +#include <memory> +#include <utility> +#include <vector> namespace clang { + +class AnalysisDeclContext; +class CXXBindTemporaryExpr; +class FunctionDecl; +class PostOrderCFGView; +class Stmt; +class VarDecl; + namespace consumed { + class ConsumedStmtVisitor; + enum ConsumedState { // No state information for the given variable. CS_None, @@ -34,22 +50,18 @@ namespace consumed { CS_Consumed }; - class ConsumedStmtVisitor; - - typedef SmallVector<PartialDiagnosticAt, 1> OptionalNotes; - typedef std::pair<PartialDiagnosticAt, OptionalNotes> DelayedDiag; - typedef std::list<DelayedDiag> DiagList; + using OptionalNotes = SmallVector<PartialDiagnosticAt, 1>; + using DelayedDiag = std::pair<PartialDiagnosticAt, OptionalNotes>; + using DiagList = std::list<DelayedDiag>; class ConsumedWarningsHandlerBase { - public: - virtual ~ConsumedWarningsHandlerBase(); - /// \brief Emit the warnings and notes left by the analysis. + /// Emit the warnings and notes left by the analysis. virtual void emitDiagnostics() {} - /// \brief Warn that a variable's state doesn't match at the entry and exit + /// Warn that a variable's state doesn't match at the entry and exit /// of a loop. /// /// \param Loc -- The location of the end of the loop. @@ -59,7 +71,7 @@ namespace consumed { virtual void warnLoopStateMismatch(SourceLocation Loc, StringRef VariableName) {} - /// \brief Warn about parameter typestate mismatches upon return. + /// Warn about parameter typestate mismatches upon return. /// /// \param Loc -- The SourceLocation of the return statement. /// @@ -80,7 +92,7 @@ namespace consumed { // FIXME: This can be removed when the attr propagation fix for templated // classes lands. - /// \brief Warn about return typestates set for unconsumable types. + /// Warn about return typestates set for unconsumable types. /// /// \param Loc -- The location of the attributes. /// @@ -88,7 +100,7 @@ namespace consumed { virtual void warnReturnTypestateForUnconsumableType(SourceLocation Loc, StringRef TypeName) {} - /// \brief Warn about return typestate mismatches. + /// Warn about return typestate mismatches. /// /// \param Loc -- The SourceLocation of the return statement. /// @@ -101,7 +113,7 @@ namespace consumed { StringRef ExpectedState, StringRef ObservedState) {} - /// \brief Warn about use-while-consumed errors. + /// Warn about use-while-consumed errors. /// \param MethodName -- The name of the method that was incorrectly /// invoked. /// @@ -112,7 +124,7 @@ namespace consumed { StringRef State, SourceLocation Loc) {} - /// \brief Warn about use-while-consumed errors. + /// Warn about use-while-consumed errors. /// \param MethodName -- The name of the method that was incorrectly /// invoked. /// @@ -129,66 +141,64 @@ namespace consumed { }; class ConsumedStateMap { - - typedef llvm::DenseMap<const VarDecl *, ConsumedState> VarMapType; - typedef llvm::DenseMap<const CXXBindTemporaryExpr *, ConsumedState> - TmpMapType; + using VarMapType = llvm::DenseMap<const VarDecl *, ConsumedState>; + using TmpMapType = + llvm::DenseMap<const CXXBindTemporaryExpr *, ConsumedState>; protected: - - bool Reachable; - const Stmt *From; + bool Reachable = true; + const Stmt *From = nullptr; VarMapType VarMap; TmpMapType TmpMap; public: - ConsumedStateMap() : Reachable(true), From(nullptr) {} + ConsumedStateMap() = default; ConsumedStateMap(const ConsumedStateMap &Other) - : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap), - TmpMap() {} + : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap), + TmpMap() {} - /// \brief Warn if any of the parameters being tracked are not in the state + /// Warn if any of the parameters being tracked are not in the state /// they were declared to be in upon return from a function. void checkParamsForReturnTypestate(SourceLocation BlameLoc, ConsumedWarningsHandlerBase &WarningsHandler) const; - /// \brief Clear the TmpMap. + /// Clear the TmpMap. void clearTemporaries(); - /// \brief Get the consumed state of a given variable. + /// Get the consumed state of a given variable. ConsumedState getState(const VarDecl *Var) const; - /// \brief Get the consumed state of a given temporary value. + /// Get the consumed state of a given temporary value. ConsumedState getState(const CXXBindTemporaryExpr *Tmp) const; - /// \brief Merge this state map with another map. + /// Merge this state map with another map. void intersect(const ConsumedStateMap &Other); void intersectAtLoopHead(const CFGBlock *LoopHead, const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates, ConsumedWarningsHandlerBase &WarningsHandler); - /// \brief Return true if this block is reachable. + /// Return true if this block is reachable. bool isReachable() const { return Reachable; } - /// \brief Mark the block as unreachable. + /// Mark the block as unreachable. void markUnreachable(); - /// \brief Set the source for a decision about the branching of states. + /// Set the source for a decision about the branching of states. /// \param Source -- The statement that was the origin of a branching /// decision. void setSource(const Stmt *Source) { this->From = Source; } - /// \brief Set the consumed state of a given variable. + /// Set the consumed state of a given variable. void setState(const VarDecl *Var, ConsumedState State); - /// \brief Set the consumed state of a given temporary value. + /// Set the consumed state of a given temporary value. void setState(const CXXBindTemporaryExpr *Tmp, ConsumedState State); - /// \brief Remove the temporary value from our state map. + /// Remove the temporary value from our state map. void remove(const CXXBindTemporaryExpr *Tmp); - /// \brief Tests to see if there is a mismatch in the states stored in two + /// Tests to see if there is a mismatch in the states stored in two /// maps. /// /// \param Other -- The second map to compare against. @@ -205,10 +215,8 @@ namespace consumed { ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph) : StateMapsArray(NumBlocks), VisitOrder(NumBlocks, 0) { unsigned int VisitOrderCounter = 0; - for (PostOrderCFGView::iterator BI = SortedGraph->begin(), - BE = SortedGraph->end(); BI != BE; ++BI) { - VisitOrder[(*BI)->getBlockID()] = VisitOrderCounter++; - } + for (const auto BI : *SortedGraph) + VisitOrder[BI->getBlockID()] = VisitOrderCounter++; } bool allBackEdgesVisited(const CFGBlock *CurrBlock, @@ -231,7 +239,6 @@ namespace consumed { /// A class that handles the analysis of uniqueness violations. class ConsumedAnalyzer { - ConsumedBlockInfo BlockInfo; std::unique_ptr<ConsumedStateMap> CurrStates; @@ -243,7 +250,6 @@ namespace consumed { const ConsumedStmtVisitor &Visitor); public: - ConsumedWarningsHandlerBase &WarningsHandler; ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler) @@ -251,7 +257,7 @@ namespace consumed { ConsumedState getExpectedReturnState() const { return ExpectedReturnState; } - /// \brief Check a function's CFG for consumed violations. + /// 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 @@ -259,6 +265,9 @@ namespace consumed { /// exactly once. void run(AnalysisDeclContext &AC); }; -}} // end namespace clang::consumed -#endif +} // namespace consumed + +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H diff --git a/include/clang/Analysis/Analyses/Dominators.h b/include/clang/Analysis/Analyses/Dominators.h index 6cb161ab37c8..a9cdc5560bc0 100644 --- a/include/clang/Analysis/Analyses/Dominators.h +++ b/include/clang/Analysis/Analyses/Dominators.h @@ -1,4 +1,4 @@ -//==- Dominators.h - Implementation of dominators tree for Clang CFG C++ -*-==// +//- Dominators.h - Implementation of dominators tree for Clang CFG -*- C++ -*-// // // The LLVM Compiler Infrastructure // @@ -16,29 +16,35 @@ #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" +#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/iterator.h" #include "llvm/Support/GenericDomTree.h" -#include "llvm/Support/GenericDomTreeConstruction.h" +#include "llvm/Support/GenericDomTreeConstruction.h" +#include "llvm/Support/raw_ostream.h" // FIXME: There is no good reason for the domtree to require a print method // which accepts an LLVM Module, so remove this (and the method's argument that // needs it) when that is fixed. + namespace llvm { + class Module; -} + +} // namespace llvm namespace clang { -class CFGBlock; -typedef llvm::DomTreeNodeBase<CFGBlock> DomTreeNode; +using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>; -/// \brief Concrete subclass of DominatorTreeBase for Clang +/// 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::DomTreeBase<CFGBlock>* DT; + llvm::DomTreeBase<CFGBlock> *DT; DominatorTree() { DT = new llvm::DomTreeBase<CFGBlock>(); @@ -48,23 +54,21 @@ public: llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; } - /// \brief This method returns the root CFGBlock of the dominators tree. - /// - inline CFGBlock *getRoot() const { + /// This method returns the root CFGBlock of the dominators tree. + CFGBlock *getRoot() const { return DT->getRoot(); } - /// \brief This method returns the root DomTreeNode, which is the wrapper + /// This method returns the root DomTreeNode, which is the wrapper /// for CFGBlock. - inline DomTreeNode *getRootNode() const { + DomTreeNode *getRootNode() const { return DT->getRootNode(); } - /// \brief This method compares two dominator trees. + /// 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 { + bool compare(DominatorTree &Other) const { DomTreeNode *R = getRootNode(); DomTreeNode *OtherR = Other.getRootNode(); @@ -77,17 +81,15 @@ public: return false; } - /// \brief This method builds the dominator tree for a given CFG + /// 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, + /// 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(), @@ -102,55 +104,48 @@ public: } } - /// \brief This method tests if one CFGBlock dominates the other. + /// 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 { + 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. + /// 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 { + bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const { return DT->properlyDominates(A, B); } - /// \brief This method finds the nearest common dominator CFG block + /// 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) { + CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) { return DT->findNearestCommonDominator(A, B); } - inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A, - const CFGBlock *B) { + const CFGBlock *findNearestCommonDominator(const CFGBlock *A, + const CFGBlock *B) { return DT->findNearestCommonDominator(A, B); } - /// \brief This method is used to update the dominator + /// This method is used to update the dominator /// tree information when a node's immediate dominator changes. - /// - inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { + void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - /// \brief This method tests if the given CFGBlock can be reachable from root. + /// 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. - /// + /// 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. - /// + /// This method converts the dominator tree to human readable form. virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const { DT->print(OS); } @@ -159,23 +154,24 @@ private: CFG *cfg; }; -} // end namespace clang +} // 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 *NodeRef; - typedef ::clang::DomTreeNode::iterator ChildIteratorType; + using NodeRef = ::clang::DomTreeNode *; + using ChildIteratorType = ::clang::DomTreeNode::iterator; static NodeRef getEntryNode(NodeRef N) { return N; } static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } static ChildIteratorType child_end(NodeRef N) { return N->end(); } - typedef llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>> - nodes_iterator; + using nodes_iterator = + llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>; static nodes_iterator nodes_begin(::clang::DomTreeNode *N) { return nodes_iterator(df_begin(getEntryNode(N))); @@ -187,7 +183,7 @@ template <> struct GraphTraits< ::clang::DomTreeNode* > { }; template <> struct GraphTraits< ::clang::DominatorTree* > - : public GraphTraits< ::clang::DomTreeNode* > { + : public GraphTraits< ::clang::DomTreeNode* > { static NodeRef getEntryNode(::clang::DominatorTree *DT) { return DT->getRootNode(); } @@ -200,6 +196,7 @@ template <> struct GraphTraits< ::clang::DominatorTree* > return nodes_iterator(df_end(getEntryNode(N))); } }; -} // end namespace llvm -#endif +} // namespace llvm + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H diff --git a/include/clang/Analysis/Analyses/FormatString.h b/include/clang/Analysis/Analyses/FormatString.h index 8c531d638cc2..6f8bb9b4095f 100644 --- a/include/clang/Analysis/Analyses/FormatString.h +++ b/include/clang/Analysis/Analyses/FormatString.h @@ -256,18 +256,26 @@ public: private: const Kind K; QualType T; - const char *Name; - bool Ptr; + const char *Name = nullptr; + bool Ptr = false; + + /// The TypeKind identifies certain well-known types like size_t and + /// ptrdiff_t. + enum class TypeKind { DontCare, SizeT, PtrdiffT }; + TypeKind TK = TypeKind::DontCare; + public: - ArgType(Kind k = UnknownTy, const char *n = nullptr) - : K(k), Name(n), Ptr(false) {} - ArgType(QualType t, const char *n = nullptr) - : K(SpecificTy), T(t), Name(n), Ptr(false) {} - ArgType(CanQualType t) : K(SpecificTy), T(t), Name(nullptr), Ptr(false) {} + ArgType(Kind K = UnknownTy, const char *N = nullptr) : K(K), Name(N) {} + ArgType(QualType T, const char *N = nullptr) : K(SpecificTy), T(T), Name(N) {} + ArgType(CanQualType T) : K(SpecificTy), T(T) {} static ArgType Invalid() { return ArgType(InvalidTy); } bool isValid() const { return K != InvalidTy; } + bool isSizeT() const { return TK == TypeKind::SizeT; } + + bool isPtrdiffT() const { return TK == TypeKind::PtrdiffT; } + /// Create an ArgType which corresponds to the type pointer to A. static ArgType PtrTo(const ArgType& A) { assert(A.K >= InvalidTy && "ArgType cannot be pointer to invalid/unknown"); @@ -276,6 +284,21 @@ public: return Res; } + /// Create an ArgType which corresponds to the size_t/ssize_t type. + static ArgType makeSizeT(const ArgType &A) { + ArgType Res = A; + Res.TK = TypeKind::SizeT; + return Res; + } + + /// Create an ArgType which corresponds to the ptrdiff_t/unsigned ptrdiff_t + /// type. + static ArgType makePtrdiffT(const ArgType &A) { + ArgType Res = A; + Res.TK = TypeKind::PtrdiffT; + return Res; + } + MatchKind matchesType(ASTContext &C, QualType argTy) const; QualType getRepresentativeType(ASTContext &C) const; @@ -510,7 +533,7 @@ public: return getConversionSpecifier().consumesDataArgument(); } - /// \brief Returns the builtin type that a data argument + /// 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 diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h index 6a1222386bae..21c3ba255c36 100644 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ b/include/clang/Analysis/Analyses/LiveVariables.h @@ -33,15 +33,18 @@ public: llvm::ImmutableSet<const Stmt *> liveStmts; llvm::ImmutableSet<const VarDecl *> liveDecls; + llvm::ImmutableSet<const BindingDecl *> liveBindings; bool equals(const LivenessValues &V) const; LivenessValues() - : liveStmts(nullptr), liveDecls(nullptr) {} + : liveStmts(nullptr), liveDecls(nullptr), liveBindings(nullptr) {} LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts, - llvm::ImmutableSet<const VarDecl *> LiveDecls) - : liveStmts(LiveStmts), liveDecls(LiveDecls) {} + llvm::ImmutableSet<const VarDecl *> LiveDecls, + llvm::ImmutableSet<const BindingDecl *> LiveBindings) + : liveStmts(LiveStmts), liveDecls(LiveDecls), + liveBindings(LiveBindings) {} bool isLive(const Stmt *S) const; bool isLive(const VarDecl *D) const; diff --git a/include/clang/Analysis/Analyses/PostOrderCFGView.h b/include/clang/Analysis/Analyses/PostOrderCFGView.h index c0a93528373e..7df3dc66c311 100644 --- a/include/clang/Analysis/Analyses/PostOrderCFGView.h +++ b/include/clang/Analysis/Analyses/PostOrderCFGView.h @@ -1,4 +1,4 @@ -//===- PostOrderCFGView.h - Post order view of CFG blocks ---------*- C++ --*-// +//===- PostOrderCFGView.h - Post order view of CFG blocks -------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,22 +14,23 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H #define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H -#include <vector> -//#include <algorithm> - -#include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/BitVector.h" - #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/PostOrderIterator.h" +#include <utility> +#include <vector> namespace clang { class PostOrderCFGView : public ManagedAnalysis { virtual void anchor(); + public: - /// \brief Implements a set of CFGBlocks using a BitVector. + /// 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 @@ -37,15 +38,16 @@ public: /// 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; }; + // value_type type. + struct iterator { using value_type = const CFGBlock *; }; - CFGBlockSet() {} + CFGBlockSet() = default; CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} - /// \brief Set the bit associated with a particular CFGBlock. + /// Set the bit associated with a particular CFGBlock. /// This is the important method for the SetType template parameter. std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) { // Note that insert() is called by po_iterator, which doesn't check to @@ -60,7 +62,7 @@ public: return std::make_pair(None, true); } - /// \brief Check if the bit for a CFGBlock has been already set. + /// 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) { @@ -69,33 +71,34 @@ public: }; private: - typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; - std::vector<const CFGBlock*> Blocks; + using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>; + std::vector<const CFGBlock *> Blocks; - typedef llvm::DenseMap<const CFGBlock *, unsigned> BlockOrderTy; + using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>; BlockOrderTy BlockOrder; public: - typedef std::vector<const CFGBlock *>::reverse_iterator iterator; - typedef std::vector<const CFGBlock *>::const_reverse_iterator const_iterator; + friend struct BlockOrderCompare; + + using iterator = std::vector<const CFGBlock *>::reverse_iterator; + using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator; PostOrderCFGView(const CFG *cfg); iterator begin() { return Blocks.rbegin(); } - iterator end() { return Blocks.rend(); } + iterator end() { return Blocks.rend(); } const_iterator begin() const { return Blocks.rbegin(); } const_iterator end() const { return Blocks.rend(); } bool empty() const { 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; }; @@ -109,7 +112,6 @@ public: static PostOrderCFGView *create(AnalysisDeclContext &analysisContext); }; -} // end clang namespace - -#endif +} // namespace clang +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H diff --git a/include/clang/Analysis/Analyses/ThreadSafety.h b/include/clang/Analysis/Analyses/ThreadSafety.h index 7e403b1f4090..c72db6f2b24b 100644 --- a/include/clang/Analysis/Analyses/ThreadSafety.h +++ b/include/clang/Analysis/Analyses/ThreadSafety.h @@ -1,4 +1,4 @@ -//===- ThreadSafety.h ------------------------------------------*- C++ --*-===// +//===- ThreadSafety.h -------------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -19,11 +19,15 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H -#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Basic/SourceLocation.h" #include "llvm/ADT/StringRef.h" namespace clang { + +class AnalysisDeclContext; +class FunctionDecl; +class NamedDecl; + namespace threadSafety { class BeforeSet; @@ -31,27 +35,44 @@ class BeforeSet; /// 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()) - POK_PassByRef, ///< Passing a guarded variable by reference. - POK_PtPassByRef, ///< Passing a pt-guarded variable by reference. + /// Dereferencing a variable (e.g. p in *p = 5;) + POK_VarDereference, + + /// Reading or writing a variable (e.g. x in x = 5;) + POK_VarAccess, + + /// Making a function call (e.g. fool()) + POK_FunctionCall, + + /// Passing a guarded variable by reference. + POK_PassByRef, + + /// Passing a pt-guarded variable by reference. + POK_PtPassByRef }; /// 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. - LK_Generic ///< Can be either Shared or Exclusive + /// Shared/reader lock of a mutex. + LK_Shared, + + /// Exclusive/writer lock of a mutex. + LK_Exclusive, + + /// Can be either Shared or Exclusive. + LK_Generic }; /// 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. + /// Reading a variable. + AK_Read, + + /// Writing a variable. + AK_Written }; /// This enum distinguishes between different situations where we warn due to @@ -72,8 +93,9 @@ enum LockErrorKind { /// Handler class for thread safety warnings. class ThreadSafetyHandler { public: - typedef StringRef Name; - ThreadSafetyHandler() : IssueBetaWarnings(false) { } + using Name = StringRef; + + ThreadSafetyHandler() = default; virtual ~ThreadSafetyHandler(); /// Warn about lock expressions which fail to resolve to lockable objects. @@ -185,7 +207,6 @@ public: virtual void handleFunExcludesLock(StringRef Kind, Name FunName, Name LockName, SourceLocation Loc) {} - /// Warn that L1 cannot be acquired before L2. virtual void handleLockAcquiredBefore(StringRef Kind, Name L1Name, Name L2Name, SourceLocation Loc) {} @@ -204,10 +225,10 @@ public: void setIssueBetaWarnings(bool b) { IssueBetaWarnings = b; } private: - bool IssueBetaWarnings; + bool IssueBetaWarnings = false; }; -/// \brief Check a function's CFG for thread-safety violations. +/// 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. @@ -218,9 +239,11 @@ void runThreadSafetyAnalysis(AnalysisDeclContext &AC, void threadSafetyCleanup(BeforeSet *Cache); -/// \brief Helper function that returns a LockKind required for the given level +/// Helper function that returns a LockKind required for the given level /// of access. LockKind getLockKindFromAccessKind(AccessKind AK); -}} // end namespace clang::threadSafety -#endif +} // namespace threadSafety +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H diff --git a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index 414645b7231b..580872e17ef4 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -1,4 +1,4 @@ -//===- ThreadSafetyCommon.h ------------------------------------*- C++ --*-===// +//===- ThreadSafetyCommon.h -------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -22,20 +22,41 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H +#include "clang/AST/Decl.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" +#include "clang/Analysis/Analyses/ThreadSafetyUtil.h" #include "clang/Analysis/AnalysisDeclContext.h" -#include "clang/Basic/OperatorKinds.h" -#include <memory> -#include <ostream> +#include "clang/Analysis/CFG.h" +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Casting.h" #include <sstream> +#include <string> +#include <utility> #include <vector> - namespace clang { -namespace threadSafety { +class AbstractConditionalOperator; +class ArraySubscriptExpr; +class BinaryOperator; +class CallExpr; +class CastExpr; +class CXXDestructorDecl; +class CXXMemberCallExpr; +class CXXOperatorCallExpr; +class CXXThisExpr; +class DeclRefExpr; +class DeclStmt; +class Expr; +class MemberExpr; +class Stmt; +class UnaryOperator; + +namespace threadSafety { // Various helper functions on til::SExpr namespace sx { @@ -72,9 +93,7 @@ inline std::string toString(const til::SExpr *E) { return ss.str(); } -} // end namespace sx - - +} // namespace sx // This class defines the interface of a clang CFG Visitor. // CFGWalker will invoke the following methods. @@ -123,11 +142,10 @@ class CFGVisitor { void exitCFG(const CFGBlock *Last) {} }; - // Walks the clang CFG, and invokes methods on a given CFGVisitor. class CFGWalker { public: - CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {} + CFGWalker() = default; // Initialize the CFGWalker. This setup only needs to be done once, even // if there are multiple passes over the CFG. @@ -186,15 +204,15 @@ public: // Process statements for (const auto &BI : *CurrBlock) { switch (BI.getKind()) { - case CFGElement::Statement: { + case CFGElement::Statement: V.handleStatement(BI.castAs<CFGStmt>().getStmt()); break; - } + case CFGElement::AutomaticObjectDtor: { CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); - CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( + auto *DD = const_cast<CXXDestructorDecl *>( AD.getDestructorDecl(ACtx->getASTContext())); - VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); + auto *VD = const_cast<VarDecl *>(AD.getVarDecl()); V.handleDestructorCall(VD, DD); break; } @@ -242,28 +260,27 @@ public: const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } private: - CFG *CFGraph; - AnalysisDeclContext *ACtx; - PostOrderCFGView *SortedGraph; + CFG *CFGraph = nullptr; + AnalysisDeclContext *ACtx = nullptr; + PostOrderCFGView *SortedGraph = nullptr; }; - - - +// TODO: move this back into ThreadSafety.cpp +// This is specific to thread safety. It is here because +// translateAttrExpr needs it, but that should be moved too. class CapabilityExpr { - // TODO: move this back into ThreadSafety.cpp - // This is specific to thread safety. It is here because - // translateAttrExpr needs it, but that should be moved too. - private: - const til::SExpr* CapExpr; ///< The capability expression. - bool Negated; ///< True if this is a negative capability + /// The capability expression. + const til::SExpr* CapExpr; + + /// True if this is a negative capability. + bool Negated; public: CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} - const til::SExpr* sexpr() const { return CapExpr; } - bool negative() const { return Negated; } + const til::SExpr* sexpr() const { return CapExpr; } + bool negative() const { return Negated; } CapabilityExpr operator!() const { return CapabilityExpr(CapExpr, !Negated); @@ -289,9 +306,9 @@ public: const ValueDecl* valueDecl() const { if (Negated || CapExpr == nullptr) return nullptr; - if (auto *P = dyn_cast<til::Project>(CapExpr)) + if (const auto *P = dyn_cast<til::Project>(CapExpr)) return P->clangDecl(); - if (auto *P = dyn_cast<til::LiteralPtr>(CapExpr)) + if (const auto *P = dyn_cast<til::LiteralPtr>(CapExpr)) return P->clangDecl(); return nullptr; } @@ -309,12 +326,10 @@ public: bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); } }; - - // Translate clang::Expr to til::SExpr. class SExprBuilder { public: - /// \brief Encapsulates the lexical context of a function call. The lexical + /// Encapsulates the lexical context of a function call. The lexical /// context includes the arguments to the call, including the implicit object /// argument. When an attribute containing a mutex expression is attached to /// a method, the expression may refer to formal parameters of the method. @@ -324,22 +339,29 @@ public: /// should be evaluated; multiple calling contexts can be chained together /// by the lock_returned attribute. struct CallingContext { - CallingContext *Prev; // The previous context; or 0 if none. - const NamedDecl *AttrDecl; // The decl to which the attr is attached. - const Expr *SelfArg; // Implicit object argument -- e.g. 'this' - unsigned NumArgs; // Number of funArgs - const Expr *const *FunArgs; // Function arguments - bool SelfArrow; // is Self referred to with -> or .? + // The previous context; or 0 if none. + CallingContext *Prev; + + // The decl to which the attr is attached. + const NamedDecl *AttrDecl; + + // Implicit object argument -- e.g. 'this' + const Expr *SelfArg = nullptr; + + // Number of funArgs + unsigned NumArgs = 0; + + // Function arguments + const Expr *const *FunArgs = nullptr; + + // is Self referred to with -> or .? + bool SelfArrow = false; CallingContext(CallingContext *P, const NamedDecl *D = nullptr) - : Prev(P), AttrDecl(D), SelfArg(nullptr), - NumArgs(0), FunArgs(nullptr), SelfArrow(false) - {} + : Prev(P), AttrDecl(D) {} }; - SExprBuilder(til::MemRegionRef A) - : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr), - CurrentBlockInfo(nullptr) { + SExprBuilder(til::MemRegionRef A) : Arena(A) { // FIXME: we don't always have a self-variable. SelfVar = new (Arena) til::Variable(nullptr); SelfVar->setKind(til::Variable::VK_SFun); @@ -368,6 +390,9 @@ public: til::SCFG *getCFG() { return Scfg; } private: + // We implement the CFGVisitor API + friend class CFGWalker; + til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, CallingContext *Ctx) ; til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); @@ -397,31 +422,30 @@ private: til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); // Map from statements in the clang CFG to SExprs in the til::SCFG. - typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap; + using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>; // Map from clang local variables to indices in a LVarDefinitionMap. - typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap; + using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>; // Map from local variable indices to SSA variables (or constants). - typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair; - typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap; + using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>; + using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>; struct BlockInfo { LVarDefinitionMap ExitMap; - bool HasBackEdges; - unsigned UnprocessedSuccessors; // Successors yet to be processed - unsigned ProcessedPredecessors; // Predecessors already processed + bool HasBackEdges = false; - BlockInfo() - : HasBackEdges(false), UnprocessedSuccessors(0), - ProcessedPredecessors(0) {} + // Successors yet to be processed + unsigned UnprocessedSuccessors = 0; + + // Predecessors already processed + unsigned ProcessedPredecessors = 0; + + BlockInfo() = default; BlockInfo(BlockInfo &&) = default; BlockInfo &operator=(BlockInfo &&) = default; }; - // We implement the CFGVisitor API - friend class CFGWalker; - void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); void enterCFGBlock(const CFGBlock *B); bool visitPredecessors() { return true; } @@ -440,6 +464,7 @@ private: void insertStmt(const Stmt *S, til::SExpr *E) { SMap.insert(std::make_pair(S, E)); } + til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); til::SExpr *addStatement(til::SExpr *E, const Stmt *S, @@ -459,30 +484,36 @@ private: static const bool CapabilityExprMode = true; til::MemRegionRef Arena; - til::Variable *SelfVar; // Variable to use for 'this'. May be null. - til::SCFG *Scfg; - StatementMap SMap; // Map from Stmt to TIL Variables - LVarIndexMap LVarIdxMap; // Indices of clang local vars. - std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs. - std::vector<BlockInfo> BBInfo; // Extra information per BB. - // Indexed by clang BlockID. + // Variable to use for 'this'. May be null. + til::Variable *SelfVar = nullptr; + + til::SCFG *Scfg = nullptr; + + // Map from Stmt to TIL Variables + StatementMap SMap; + + // Indices of clang local vars. + LVarIndexMap LVarIdxMap; + + // Map from clang to til BBs. + std::vector<til::BasicBlock *> BlockMap; + + // Extra information per BB. Indexed by clang BlockID. + std::vector<BlockInfo> BBInfo; LVarDefinitionMap CurrentLVarMap; - std::vector<til::Phi*> CurrentArguments; - std::vector<til::SExpr*> CurrentInstructions; - std::vector<til::Phi*> IncompleteArgs; - til::BasicBlock *CurrentBB; - BlockInfo *CurrentBlockInfo; + std::vector<til::Phi *> CurrentArguments; + std::vector<til::SExpr *> CurrentInstructions; + std::vector<til::Phi *> IncompleteArgs; + til::BasicBlock *CurrentBB = nullptr; + BlockInfo *CurrentBlockInfo = nullptr; }; - // Dump an SCFG to llvm::errs(). void printSCFG(CFGWalker &Walker); +} // namespace threadSafety +} // namespace clang -} // end namespace threadSafety - -} // end namespace clang - -#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H +#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H diff --git a/include/clang/Analysis/Analyses/ThreadSafetyLogical.h b/include/clang/Analysis/Analyses/ThreadSafetyLogical.h index bc78021343a4..2508af1af107 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyLogical.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyLogical.h @@ -29,7 +29,7 @@ public: }; Opcode kind() const { return Kind; } - /// \brief Logical implication. Returns true if the LExpr implies RHS, i.e. if + /// Logical implication. Returns true if the LExpr implies RHS, i.e. if /// the LExpr holds, then RHS must hold. For example, (A & B) implies A. inline bool implies(const LExpr *RHS) const; @@ -92,7 +92,7 @@ public: static bool classof(const LExpr *E) { return E->kind() == LExpr::Not; } }; -/// \brief Logical implication. Returns true if LHS implies RHS, i.e. if LHS +/// Logical implication. Returns true if LHS implies RHS, i.e. if LHS /// holds, then RHS must hold. For example, (A & B) implies A. bool implies(const LExpr *LHS, const LExpr *RHS); diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h index 0a58d2a80250..810f2052b7a5 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h @@ -1,4 +1,4 @@ -//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// +//===- ThreadSafetyTIL.h ----------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -47,20 +47,33 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H -// All clang include dependencies for this file must be put in -// ThreadSafetyUtil.h. -#include "ThreadSafetyUtil.h" +#include "clang/AST/Decl.h" +#include "clang/Analysis/Analyses/ThreadSafetyUtil.h" +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/raw_ostream.h" #include <algorithm> #include <cassert> #include <cstddef> -#include <stdint.h> +#include <cstdint> +#include <iterator> +#include <string> #include <utility> - namespace clang { + +class CallExpr; +class Expr; +class Stmt; + namespace threadSafety { namespace til { +class BasicBlock; /// Enum for the different distinct classes of SExpr enum TIL_Opcode { @@ -100,11 +113,21 @@ enum TIL_BinaryOpcode : unsigned char { /// Opcode for cast operations. enum TIL_CastOpcode : unsigned char { CAST_none = 0, - CAST_extendNum, // extend precision of numeric type - CAST_truncNum, // truncate precision of numeric type - CAST_toFloat, // convert to floating point type - CAST_toInt, // convert to integer type - CAST_objToPtr // convert smart pointer to pointer (C++ only) + + // Extend precision of numeric type + CAST_extendNum, + + // Truncate precision of numeric type + CAST_truncNum, + + // Convert to floating point type + CAST_toFloat, + + // Convert to integer type + CAST_toInt, + + // Convert smart pointer to pointer (C++ only) + CAST_objToPtr }; const TIL_Opcode COP_Min = COP_Future; @@ -122,7 +145,6 @@ StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); /// Return the name of a binary opcode. StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); - /// ValueTypes are data types that can actually be held in registers. /// All variables and expressions must have a value type. /// Pointer types are further subdivided into the various heap-allocated @@ -150,22 +172,22 @@ struct ValueType { ST_128 }; + ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) + : Base(B), Size(Sz), Signed(S), VectSize(VS) {} + inline static SizeType getSizeType(unsigned nbytes); template <class T> inline static ValueType getValueType(); - ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) - : Base(B), Size(Sz), Signed(S), VectSize(VS) - { } + BaseType Base; + SizeType Size; + bool Signed; - BaseType Base; - SizeType Size; - bool Signed; - unsigned char VectSize; // 0 for scalar, otherwise num elements in vector + // 0 for scalar, otherwise num elements in vector + unsigned char VectSize; }; - inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { switch (nbytes) { case 1: return ST_8; @@ -177,7 +199,6 @@ inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { } } - template<> inline ValueType ValueType::getValueType<void>() { return ValueType(BT_Void, ST_0, false, 0); @@ -253,13 +274,11 @@ inline ValueType ValueType::getValueType<void*>() { return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); } - -class BasicBlock; - - /// Base class for AST nodes in the typed intermediate language. class SExpr { public: + SExpr() = delete; + TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } // Subclasses of SExpr must define the following: @@ -280,6 +299,9 @@ public: return ::operator new(S, R); } + /// SExpr objects must be created in an arena. + void *operator new(size_t) = delete; + /// SExpr objects cannot be deleted. // This declaration is public to workaround a gcc bug that breaks building // with REQUIRES_EH=1. @@ -291,45 +313,33 @@ public: /// Returns the block, if this is an instruction in a basic block, /// otherwise returns null. - BasicBlock* block() const { return Block; } + BasicBlock *block() const { return Block; } /// Set the basic block and instruction ID for this expression. void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } protected: - SExpr(TIL_Opcode Op) - : Opcode(Op), Reserved(0), Flags(0), SExprID(0), Block(nullptr) {} - SExpr(const SExpr &E) - : Opcode(E.Opcode), Reserved(0), Flags(E.Flags), SExprID(0), - Block(nullptr) {} + SExpr(TIL_Opcode Op) : Opcode(Op) {} + SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {} const unsigned char Opcode; - unsigned char Reserved; - unsigned short Flags; - unsigned SExprID; - BasicBlock* Block; - -private: - SExpr() = delete; - - /// SExpr objects must be created in an arena. - void *operator new(size_t) = delete; + unsigned char Reserved = 0; + unsigned short Flags = 0; + unsigned SExprID = 0; + BasicBlock *Block = nullptr; }; - // Contains various helper functions for SExprs. namespace ThreadSafetyTIL { - inline bool isTrivial(const SExpr *E) { - unsigned Op = E->opcode(); - return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; - } + +inline bool isTrivial(const SExpr *E) { + unsigned Op = E->opcode(); + return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; } -// Nodes which declare variables -class Function; -class SFunction; -class Let; +} // namespace ThreadSafetyTIL +// Nodes which declare variables /// A named variable, e.g. "x". /// @@ -345,28 +355,35 @@ class Let; /// pointer to the original declaration. class Variable : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } - enum VariableKind { - VK_Let, ///< Let-variable - VK_Fun, ///< Function parameter - VK_SFun ///< SFunction (self) parameter + /// Let-variable + VK_Let, + + /// Function parameter + VK_Fun, + + /// SFunction (self) parameter + VK_SFun }; Variable(StringRef s, SExpr *D = nullptr) - : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) { + : SExpr(COP_Variable), Name(s), Definition(D) { Flags = VK_Let; } - Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr) + + Variable(SExpr *D, const ValueDecl *Cvd = nullptr) : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), Definition(D), Cvdecl(Cvd) { Flags = VK_Let; } + Variable(const Variable &Vd, SExpr *D) // rewrite constructor : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { Flags = Vd.kind(); } + static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } + /// Return the kind of variable (let, function param, or self) VariableKind kind() const { return static_cast<VariableKind>(Flags); } @@ -374,7 +391,7 @@ public: StringRef name() const { return Name; } /// Return the clang declaration for this variable, if any. - const clang::ValueDecl *clangDecl() const { return Cvdecl; } + const ValueDecl *clangDecl() const { return Cvdecl; } /// Return the definition of the variable. /// For let-vars, this is the setting expression. @@ -385,7 +402,7 @@ public: void setName(StringRef S) { Name = S; } void setKind(VariableKind K) { Flags = K; } void setDefinition(SExpr *E) { Definition = E; } - void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } + void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -399,42 +416,41 @@ public: } private: - friend class Function; - friend class SFunction; friend class BasicBlock; + friend class Function; friend class Let; + friend class SFunction; - StringRef Name; // The name of the variable. - SExpr* Definition; // The TIL type or definition - const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. -}; + // The name of the variable. + StringRef Name; + + // The TIL type or definition. + SExpr *Definition; + // The clang declaration for this variable. + const ValueDecl *Cvdecl = nullptr; +}; /// Placeholder for an expression that has not yet been created. /// Used to implement lazy copy and rewriting strategies. class Future : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } - enum FutureStatus { FS_pending, FS_evaluating, FS_done }; - Future() : SExpr(COP_Future), Status(FS_pending), Result(nullptr) {} - -private: + Future() : SExpr(COP_Future) {} virtual ~Future() = delete; -public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } + // A lazy rewriting strategy should subclass Future and override this method. virtual SExpr *compute() { return nullptr; } // Return the result of this future if it exists, otherwise return null. - SExpr *maybeGetResult() const { - return Result; - } + SExpr *maybeGetResult() const { return Result; } // Return the result of this future; forcing it if necessary. SExpr *result() { @@ -464,19 +480,18 @@ public: private: SExpr* force(); - FutureStatus Status; - SExpr *Result; + FutureStatus Status = FS_pending; + SExpr *Result = nullptr; }; - /// Placeholder for expressions that cannot be represented in the TIL. class Undefined : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } - - Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} + Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } + template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { return Vs.reduceUndefined(*this); @@ -488,17 +503,16 @@ public: } private: - const clang::Stmt *Cstmt; + const Stmt *Cstmt; }; - /// Placeholder for a wildcard that matches any other expression. class Wildcard : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } - Wildcard() : SExpr(COP_Wildcard) {} - Wildcard(const Wildcard &W) : SExpr(W) {} + Wildcard(const Wildcard &) = default; + + static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { return Vs.reduceWildcard(*this); @@ -510,22 +524,20 @@ public: } }; - template <class T> class LiteralT; // Base class for literal values. class Literal : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } + Literal(const Expr *C) + : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {} + Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {} + Literal(const Literal &) = default; - Literal(const clang::Expr *C) - : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) - { } - Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {} - Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } // The clang expression for this literal. - const clang::Expr *clangExpr() const { return Cexpr; } + const Expr *clangExpr() const { return Cexpr; } ValueType valueType() const { return ValType; } @@ -546,26 +558,23 @@ public: private: const ValueType ValType; - const clang::Expr *Cexpr; + const Expr *Cexpr = nullptr; }; - // Derived class for literal values, which stores the actual value. template<class T> class LiteralT : public Literal { public: - LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { } - LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { } + LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {} + LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {} - T value() const { return Val;} + T value() const { return Val;} T& value() { return Val; } private: T Val; }; - - template <class V> typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { if (Cexpr) @@ -622,18 +631,17 @@ typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { return Vs.reduceLiteral(*this); } - /// A Literal pointer to an object allocated in memory. /// At compile time, pointer literals are represented by symbolic names. class LiteralPtr : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } + LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} + LiteralPtr(const LiteralPtr &) = default; - LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} - LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } // The clang declaration for the value that this pointer points to. - const clang::ValueDecl *clangDecl() const { return Cvdecl; } + const ValueDecl *clangDecl() const { return Cvdecl; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -646,26 +654,26 @@ public: } private: - const clang::ValueDecl *Cvdecl; + const ValueDecl *Cvdecl; }; - /// A function -- a.k.a. lambda abstraction. /// Functions with multiple arguments are created by currying, /// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) class Function : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } - Function(Variable *Vd, SExpr *Bd) : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { Vd->setKind(Variable::VK_Fun); } + Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor : SExpr(F), VarDecl(Vd), Body(Bd) { Vd->setKind(Variable::VK_Fun); } + static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } + Variable *variableDecl() { return VarDecl; } const Variable *variableDecl() const { return VarDecl; } @@ -700,20 +708,18 @@ private: SExpr* Body; }; - /// A self-applicable function. /// A self-applicable function can be applied to itself. It's useful for /// implementing objects and late binding. class SFunction : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } - SFunction(Variable *Vd, SExpr *B) : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { assert(Vd->Definition == nullptr); Vd->setKind(Variable::VK_SFun); Vd->Definition = this; } + SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor : SExpr(F), VarDecl(Vd), Body(B) { assert(Vd->Definition == nullptr); @@ -721,6 +727,8 @@ public: Vd->Definition = this; } + static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } + Variable *variableDecl() { return VarDecl; } const Variable *variableDecl() const { return VarDecl; } @@ -752,16 +760,15 @@ private: SExpr* Body; }; - /// A block of code -- e.g. the body of a function. class Code : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } - Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor : SExpr(C), ReturnType(T), Body(B) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } + SExpr *returnType() { return ReturnType; } const SExpr *returnType() const { return ReturnType; } @@ -788,16 +795,15 @@ private: SExpr* Body; }; - /// A typed, writable location in memory class Field : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } - Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor : SExpr(C), Range(R), Body(B) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } + SExpr *range() { return Range; } const SExpr *range() const { return Range; } @@ -824,7 +830,6 @@ private: SExpr* Body; }; - /// Apply an argument to a function. /// Note that this does not actually call the function. Functions are curried, /// so this returns a closure in which the first parameter has been applied. @@ -832,12 +837,11 @@ private: /// function. class Apply : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } - Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor - : SExpr(A), Fun(F), Arg(Ar) - {} + : SExpr(A), Fun(F), Arg(Ar) {} + + static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } SExpr *fun() { return Fun; } const SExpr *fun() const { return Fun; } @@ -865,16 +869,15 @@ private: SExpr* Arg; }; - /// Apply a self-argument to a self-applicable function. class SApply : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } - SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor : SExpr(A), Sfun(Sf), Arg(Ar) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } + SExpr *sfun() { return Sfun; } const SExpr *sfun() const { return Sfun; } @@ -904,23 +907,23 @@ private: SExpr* Arg; }; - /// Project a named slot from a C++ struct or class. class Project : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } - - Project(SExpr *R, const clang::ValueDecl *Cvd) + Project(SExpr *R, const ValueDecl *Cvd) : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) { assert(Cvd && "ValueDecl must not be null"); } + static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } + SExpr *record() { return Rec; } const SExpr *record() const { return Rec; } - const clang::ValueDecl *clangDecl() const { return Cvdecl; } + const ValueDecl *clangDecl() const { return Cvdecl; } bool isArrow() const { return (Flags & 0x01) != 0; } + void setArrow(bool b) { if (b) Flags |= 0x01; else Flags &= 0xFFFE; @@ -954,23 +957,22 @@ public: private: SExpr* Rec; mutable llvm::Optional<std::string> SlotName; - const clang::ValueDecl *Cvdecl; + const ValueDecl *Cvdecl; }; - /// Call a function (after all arguments have been applied). class Call : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } - - Call(SExpr *T, const clang::CallExpr *Ce = nullptr) + Call(SExpr *T, const CallExpr *Ce = nullptr) : SExpr(COP_Call), Target(T), Cexpr(Ce) {} Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } + SExpr *target() { return Target; } const SExpr *target() const { return Target; } - const clang::CallExpr *clangCallExpr() const { return Cexpr; } + const CallExpr *clangCallExpr() const { return Cexpr; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -985,15 +987,12 @@ public: private: SExpr* Target; - const clang::CallExpr *Cexpr; + const CallExpr *Cexpr; }; - /// Allocate memory for a new value on the heap or stack. class Alloc : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } - enum AllocKind { AK_Stack, AK_Heap @@ -1002,6 +1001,8 @@ public: Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } + static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } + AllocKind kind() const { return static_cast<AllocKind>(Flags); } SExpr *dataType() { return Dtype; } @@ -1025,15 +1026,14 @@ private: SExpr* Dtype; }; - /// Load a value from memory. class Load : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } - Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } + SExpr *pointer() { return Ptr; } const SExpr *pointer() const { return Ptr; } @@ -1052,16 +1052,15 @@ private: SExpr* Ptr; }; - /// Store a value to memory. /// The destination is a pointer to a field, the source is the value to store. class Store : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } - Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } + SExpr *destination() { return Dest; } // Address to store to const SExpr *destination() const { return Dest; } @@ -1088,16 +1087,15 @@ private: SExpr* Source; }; - /// If p is a reference to an array, then p[i] is a reference to the i'th /// element of the array. class ArrayIndex : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } - ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) - : SExpr(E), Array(A), Index(N) {} + : SExpr(E), Array(A), Index(N) {} + + static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } SExpr *array() { return Array; } const SExpr *array() const { return Array; } @@ -1125,17 +1123,16 @@ private: SExpr* Index; }; - /// Pointer arithmetic, restricted to arrays only. /// If p is a reference to an array, then p + n, where n is an integer, is /// a reference to a subarray. class ArrayAdd : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } - ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) - : SExpr(E), Array(A), Index(N) {} + : SExpr(E), Array(A), Index(N) {} + + static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } SExpr *array() { return Array; } const SExpr *array() const { return Array; } @@ -1163,18 +1160,18 @@ private: SExpr* Index; }; - /// Simple arithmetic unary operations, e.g. negate and not. /// These operations have no side-effects. class UnaryOp : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } - UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { Flags = Op; } + UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } + static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } + TIL_UnaryOpcode unaryOpcode() const { return static_cast<TIL_UnaryOpcode>(Flags); } @@ -1201,22 +1198,22 @@ private: SExpr* Expr0; }; - /// Simple arithmetic binary operations, e.g. +, -, etc. /// These operations have no side effects. class BinaryOp : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } - BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { Flags = Op; } + BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) : SExpr(B), Expr0(E0), Expr1(E1) { Flags = B.Flags; } + static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } + TIL_BinaryOpcode binaryOpcode() const { return static_cast<TIL_BinaryOpcode>(Flags); } @@ -1251,17 +1248,16 @@ private: SExpr* Expr1; }; - /// Cast expressions. /// Cast expressions are essentially unary operations, but we treat them /// as a distinct AST node because they only change the type of the result. class Cast : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } - Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } + static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } + TIL_CastOpcode castOpcode() const { return static_cast<TIL_CastOpcode>(Flags); } @@ -1288,16 +1284,14 @@ private: SExpr* Expr0; }; - class SCFG; - /// Phi Node, for code in SSA form. /// Each Phi node has an array of possible values that it can take, /// depending on where control flow comes from. class Phi : public SExpr { public: - typedef SimpleArray<SExpr *> ValArray; + using ValArray = SimpleArray<SExpr *>; // In minimal SSA form, all Phi nodes are MultiVal. // During conversion to SSA, incomplete Phi nodes may be introduced, which @@ -1308,14 +1302,11 @@ public: PH_Incomplete // Phi node is incomplete }; - static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } + Phi() : SExpr(COP_Phi) {} + Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} + Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} - Phi() - : SExpr(COP_Phi), Cvdecl(nullptr) {} - Phi(MemRegionRef A, unsigned Nvals) - : SExpr(COP_Phi), Values(A, Nvals), Cvdecl(nullptr) {} - Phi(const Phi &P, ValArray &&Vs) - : SExpr(P), Values(std::move(Vs)), Cvdecl(nullptr) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } const ValArray &values() const { return Values; } ValArray &values() { return Values; } @@ -1324,19 +1315,18 @@ public: void setStatus(Status s) { Flags = s; } /// Return the clang declaration of the variable for this Phi node, if any. - const clang::ValueDecl *clangDecl() const { return Cvdecl; } + const ValueDecl *clangDecl() const { return Cvdecl; } /// Set the clang variable associated with this Phi node. - void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; } + void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { typename V::template Container<typename V::R_SExpr> Nvs(Vs, Values.size()); - for (auto *Val : Values) { + for (const auto *Val : Values) Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); - } return Vs.reducePhi(*this, Nvs); } @@ -1348,31 +1338,28 @@ public: private: ValArray Values; - const clang::ValueDecl* Cvdecl; + const ValueDecl* Cvdecl = nullptr; }; - /// Base class for basic block terminators: Branch, Goto, and Return. class Terminator : public SExpr { +protected: + Terminator(TIL_Opcode Op) : SExpr(Op) {} + Terminator(const SExpr &E) : SExpr(E) {} + public: static bool classof(const SExpr *E) { return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; } -protected: - Terminator(TIL_Opcode Op) : SExpr(Op) {} - Terminator(const SExpr &E) : SExpr(E) {} - -public: /// Return the list of basic blocks that this terminator can branch to. - ArrayRef<BasicBlock*> successors(); + ArrayRef<BasicBlock *> successors(); - ArrayRef<BasicBlock*> successors() const { + ArrayRef<BasicBlock *> successors() const { return const_cast<Terminator*>(this)->successors(); } }; - /// Jump to another basic block. /// A goto instruction is essentially a tail-recursive call into another /// block. In addition to the block pointer, it specifies an index into the @@ -1380,13 +1367,13 @@ public: /// of the call. class Goto : public Terminator { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } - Goto(BasicBlock *B, unsigned I) : Terminator(COP_Goto), TargetBlock(B), Index(I) {} Goto(const Goto &G, BasicBlock *B, unsigned I) : Terminator(COP_Goto), TargetBlock(B), Index(I) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } + const BasicBlock *targetBlock() const { return TargetBlock; } BasicBlock *targetBlock() { return TargetBlock; } @@ -1394,9 +1381,7 @@ public: unsigned index() const { return Index; } /// Return the list of basic blocks that this terminator can branch to. - ArrayRef<BasicBlock*> successors() { - return TargetBlock; - } + ArrayRef<BasicBlock *> successors() { return TargetBlock; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1415,25 +1400,25 @@ private: unsigned Index; }; - /// A conditional branch to two other blocks. /// Note that unlike Goto, Branch does not have an index. The target blocks /// must be child-blocks, and cannot have Phi nodes. class Branch : public Terminator { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } - Branch(SExpr *C, BasicBlock *T, BasicBlock *E) : Terminator(COP_Branch), Condition(C) { Branches[0] = T; Branches[1] = E; } + Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) : Terminator(Br), Condition(C) { Branches[0] = T; Branches[1] = E; } + static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } + const SExpr *condition() const { return Condition; } SExpr *condition() { return Condition; } @@ -1463,24 +1448,21 @@ public: } private: - SExpr* Condition; + SExpr *Condition; BasicBlock *Branches[2]; }; - /// Return from the enclosing function, passing the return value to the caller. /// Only the exit block should end with a return statement. class Return : public Terminator { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } - Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } + /// Return an empty list. - ArrayRef<BasicBlock*> successors() { - return None; - } + ArrayRef<BasicBlock *> successors() { return None; } SExpr *returnValue() { return Retval; } const SExpr *returnValue() const { return Retval; } @@ -1500,7 +1482,6 @@ private: SExpr* Retval; }; - inline ArrayRef<BasicBlock*> Terminator::successors() { switch (opcode()) { case COP_Goto: return cast<Goto>(this)->successors(); @@ -1511,7 +1492,6 @@ inline ArrayRef<BasicBlock*> Terminator::successors() { } } - /// A basic block is part of an SCFG. It can be treated as a function in /// continuation passing style. A block consists of a sequence of phi nodes, /// which are "arguments" to the function, followed by a sequence of @@ -1519,15 +1499,23 @@ inline ArrayRef<BasicBlock*> Terminator::successors() { /// another basic block in the same SCFG. class BasicBlock : public SExpr { public: - typedef SimpleArray<SExpr*> InstrArray; - typedef SimpleArray<BasicBlock*> BlockArray; + using InstrArray = SimpleArray<SExpr *>; + using BlockArray = SimpleArray<BasicBlock *>; // TopologyNodes are used to overlay tree structures on top of the CFG, // such as dominator and postdominator trees. Each block is assigned an // ID in the tree according to a depth-first search. Tree traversals are // always up, towards the parents. struct TopologyNode { - TopologyNode() : NodeID(0), SizeOfSubTree(0), Parent(nullptr) {} + int NodeID = 0; + + // Includes this node, so must be > 1. + int SizeOfSubTree = 0; + + // Pointer to parent. + BasicBlock *Parent = nullptr; + + TopologyNode() = default; bool isParentOf(const TopologyNode& OtherNode) { return OtherNode.NodeID > NodeID && @@ -1538,22 +1526,17 @@ public: return OtherNode.NodeID >= NodeID && OtherNode.NodeID < NodeID + SizeOfSubTree; } - - int NodeID; - int SizeOfSubTree; // Includes this node, so must be > 1. - BasicBlock *Parent; // Pointer to parent. }; - static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } - explicit BasicBlock(MemRegionRef A) - : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), - Visited(0), TermInstr(nullptr) {} + : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {} BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, Terminator *T) - : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),Visited(0), + : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false), Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} + static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } + /// Returns the block ID. Every block has a unique ID in the CFG. int blockID() const { return BlockID; } @@ -1600,11 +1583,13 @@ public: Args.reserveCheck(1, Arena); Args.push_back(V); } + /// Add a new instruction. void addInstruction(SExpr *V) { Instrs.reserveCheck(1, Arena); Instrs.push_back(V); } + // Add a new predecessor, and return the phi-node index for it. // Will add an argument to all phi-nodes, initialized to nullptr. unsigned addPredecessor(BasicBlock *Pred); @@ -1632,11 +1617,11 @@ public: // Entering the basic block should do any scope initialization. Vs.enterBasicBlock(*this); - for (auto *E : Args) { + for (const auto *E : Args) { auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); Nas.push_back(Ne); } - for (auto *E : Instrs) { + for (const auto *E : Instrs) { auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); Nis.push_back(Ne); } @@ -1657,43 +1642,56 @@ public: private: friend class SCFG; - int renumberInstrs(int id); // assign unique ids to all instructions - int topologicalSort(SimpleArray<BasicBlock*>& Blocks, int ID); - int topologicalFinalSort(SimpleArray<BasicBlock*>& Blocks, int ID); + // assign unique ids to all instructions + int renumberInstrs(int id); + + int topologicalSort(SimpleArray<BasicBlock *> &Blocks, int ID); + int topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, int ID); void computeDominator(); void computePostDominator(); -private: - MemRegionRef Arena; // The arena used to allocate this block. - SCFG *CFGPtr; // The CFG that contains this block. - int BlockID : 31; // unique id for this BB in the containing CFG. - // IDs are in topological order. - bool Visited : 1; // Bit to determine if a block has been visited - // during a traversal. - BlockArray Predecessors; // Predecessor blocks in the CFG. - InstrArray Args; // Phi nodes. One argument per predecessor. - InstrArray Instrs; // Instructions. - Terminator* TermInstr; // Terminating instruction - - TopologyNode DominatorNode; // The dominator tree - TopologyNode PostDominatorNode; // The post-dominator tree -}; + // The arena used to allocate this block. + MemRegionRef Arena; + + // The CFG that contains this block. + SCFG *CFGPtr = nullptr; + + // Unique ID for this BB in the containing CFG. IDs are in topological order. + int BlockID : 31; + // Bit to determine if a block has been visited during a traversal. + bool Visited : 1; + + // Predecessor blocks in the CFG. + BlockArray Predecessors; + + // Phi nodes. One argument per predecessor. + InstrArray Args; + + // Instructions. + InstrArray Instrs; + + // Terminating instruction. + Terminator *TermInstr = nullptr; + + // The dominator tree. + TopologyNode DominatorNode; + + // The post-dominator tree. + TopologyNode PostDominatorNode; +}; /// An SCFG is a control-flow graph. It consists of a set of basic blocks, /// each of which terminates in a branch to another basic block. There is one /// entry point, and one exit point. class SCFG : public SExpr { public: - typedef SimpleArray<BasicBlock *> BlockArray; - typedef BlockArray::iterator iterator; - typedef BlockArray::const_iterator const_iterator; - - static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } + using BlockArray = SimpleArray<BasicBlock *>; + using iterator = BlockArray::iterator; + using const_iterator = BlockArray::const_iterator; SCFG(MemRegionRef A, unsigned Nblocks) - : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks), - Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { + : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) { Entry = new (A) BasicBlock(A); Exit = new (A) BasicBlock(A); auto *V = new (A) Phi(); @@ -1702,12 +1700,14 @@ public: add(Entry); add(Exit); } + SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba - : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)), - Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { + : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) { // TODO: set entry and exit! } + static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } + /// Return true if this CFG is valid. bool valid() const { return Entry && Exit && Blocks.size() > 0; } @@ -1756,7 +1756,7 @@ public: Vs.enterCFG(*this); typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); - for (auto *B : Blocks) { + for (const auto *B : Blocks) { Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); } Vs.exitCFG(*this); @@ -1770,27 +1770,25 @@ public: } private: - void renumberInstrs(); // assign unique ids to all instructions + // assign unique ids to all instructions + void renumberInstrs(); -private: MemRegionRef Arena; - BlockArray Blocks; - BasicBlock *Entry; - BasicBlock *Exit; - unsigned NumInstructions; - bool Normal; + BlockArray Blocks; + BasicBlock *Entry = nullptr; + BasicBlock *Exit = nullptr; + unsigned NumInstructions = 0; + bool Normal = false; }; - - /// An identifier, e.g. 'foo' or 'x'. /// This is a pseduo-term; it will be lowered to a variable or projection. class Identifier : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } + Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {} + Identifier(const Identifier &) = default; - Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { } - Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { } + static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } StringRef name() const { return Name; } @@ -1808,19 +1806,16 @@ private: StringRef Name; }; - /// An if-then-else expression. /// This is a pseduo-term; it will be lowered to a branch in a CFG. class IfThenElse : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } - IfThenElse(SExpr *C, SExpr *T, SExpr *E) - : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) - { } + : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {} IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) - : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) - { } + : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {} + + static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } SExpr *condition() { return Condition; } // Address to store to const SExpr *condition() const { return Condition; } @@ -1856,20 +1851,20 @@ private: SExpr* ElseExpr; }; - /// A let-expression, e.g. let x=t; u. /// This is a pseduo-term; it will be lowered to instructions in a CFG. class Let : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } - Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { Vd->setKind(Variable::VK_Let); } + Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { Vd->setKind(Variable::VK_Let); } + static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } + Variable *variableDecl() { return VarDecl; } const Variable *variableDecl() const { return VarDecl; } @@ -1904,15 +1899,13 @@ private: SExpr* Body; }; - - const SExpr *getCanonicalVal(const SExpr *E); SExpr* simplifyToCanonicalVal(SExpr *E); void simplifyIncompleteArg(til::Phi *Ph); +} // namespace til +} // namespace threadSafety -} // end namespace til -} // end namespace threadSafety -} // end namespace clang +} // namespace clang -#endif +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h index 705fe910d092..49031010a75b 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h @@ -1,4 +1,4 @@ -//===- ThreadSafetyTraverse.h ----------------------------------*- C++ --*-===// +//===- ThreadSafetyTraverse.h -----------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -17,7 +17,13 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H -#include "ThreadSafetyTIL.h" +#include "clang/AST/Decl.h" +#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" +#include "clang/Analysis/Analyses/ThreadSafetyUtil.h" +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Casting.h" +#include <cstdint> #include <ostream> namespace clang { @@ -26,7 +32,7 @@ namespace til { // Defines an interface used to traverse SExprs. Traversals have been made as // generic as possible, and are intended to handle any kind of pass over the -// AST, e.g. visiters, copying, non-destructive rewriting, destructive +// AST, e.g. visitors, copying, non-destructive rewriting, destructive // (in-place) rewriting, hashing, typing, etc. // // Traversals implement the functional notion of a "fold" operation on SExprs. @@ -92,21 +98,27 @@ public: #undef TIL_OPCODE_DEF }; - // Base class for simple reducers that don't much care about the context. class SimpleReducerBase { public: enum TraversalKind { - TRV_Normal, // ordinary subexpressions - TRV_Decl, // declarations (e.g. function bodies) - TRV_Lazy, // expressions that require lazy evaluation - TRV_Type // type expressions + // Ordinary subexpressions. + TRV_Normal, + + // Declarations (e.g. function bodies). + TRV_Decl, + + // Expressions that require lazy evaluation. + TRV_Lazy, + + // Type expressions. + TRV_Type }; // R_Ctx defines a "context" for the traversal, which encodes information // about where a term appears. This can be used to encoding the // "current continuation" for CPS transforms, or other information. - typedef TraversalKind R_Ctx; + using R_Ctx = TraversalKind; // Create context for an ordinary subexpression. R_Ctx subExprCtx(R_Ctx Ctx) { return TRV_Normal; } @@ -123,14 +135,13 @@ public: R_Ctx typeCtx(R_Ctx Ctx) { return TRV_Type; } }; - // Base class for traversals that rewrite an SExpr to another SExpr. class CopyReducerBase : public SimpleReducerBase { public: // R_SExpr is the result type for a traversal. // A copy or non-destructive rewrite returns a newly allocated term. - typedef SExpr *R_SExpr; - typedef BasicBlock *R_BasicBlock; + using R_SExpr = SExpr *; + using R_BasicBlock = BasicBlock *; // Container is a minimal interface used to store results when traversing // SExprs of variable arity, such as Phi, Goto, and SCFG. @@ -151,32 +162,31 @@ protected: MemRegionRef Arena; }; - // Base class for visit traversals. class VisitReducerBase : public SimpleReducerBase { public: // A visitor returns a bool, representing success or failure. - typedef bool R_SExpr; - typedef bool R_BasicBlock; + using R_SExpr = bool; + using R_BasicBlock = bool; // A visitor "container" is a single bool, which accumulates success. template <class T> class Container { public: - Container(VisitReducerBase &S, unsigned N) : Success(true) {} - void push_back(bool E) { Success = Success && E; } + bool Success = true; - bool Success; + Container(VisitReducerBase &S, unsigned N) {} + + void push_back(bool E) { Success = Success && E; } }; }; - // Implements a traversal that visits each subexpression, and returns either // true or false. template <class Self> class VisitReducer : public Traversal<Self, VisitReducerBase>, public VisitReducerBase { public: - VisitReducer() {} + VisitReducer() = default; public: R_SExpr reduceNull() { return true; } @@ -191,54 +201,70 @@ public: R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) { return Nvd && E0; } + R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) { return Nvd && E0; } + R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; } R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; } R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; } R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; } R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; } + R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; } R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) { return Bbs.Success; } + R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<R_SExpr> &As, Container<R_SExpr> &Is, R_SExpr T) { return (As.Success && Is.Success && T); } + R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) { return As.Success; } + R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) { return true; } + R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { return C; } + R_SExpr reduceReturn(Return &O, R_SExpr E) { return E; } @@ -246,9 +272,11 @@ public: R_SExpr reduceIdentifier(Identifier &Orig) { return true; } + R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) { return C && T && E; } + R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) { return Nvd && B; } @@ -260,7 +288,7 @@ public: void enterBasicBlock(BasicBlock &BB) {} void exitBasicBlock(BasicBlock &BB) {} - Variable *reduceVariableRef (Variable *Ovd) { return Ovd; } + Variable *reduceVariableRef(Variable *Ovd) { return Ovd; } BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } public: @@ -278,7 +306,6 @@ private: bool Success; }; - // Basic class for comparison operations over expressions. template <typename Self> class Comparator { @@ -298,19 +325,18 @@ public: } }; - class EqualsComparator : public Comparator<EqualsComparator> { public: // Result type for the comparison, e.g. bool for simple equality, // or int for lexigraphic comparison (-1, 0, 1). Must have one value which // denotes "true". - typedef bool CType; + using CType = bool; CType trueResult() { return true; } bool notTrue(CType ct) { return !ct; } - bool compareIntegers(unsigned i, unsigned j) { return i == j; } - bool compareStrings (StringRef s, StringRef r) { return s == r; } + bool compareIntegers(unsigned i, unsigned j) { return i == j; } + bool compareStrings (StringRef s, StringRef r) { return s == r; } bool comparePointers(const void* P, const void* Q) { return P == Q; } bool compare(const SExpr *E1, const SExpr* E2) { @@ -320,10 +346,10 @@ public: } // TODO -- handle alpha-renaming of variables - void enterScope(const Variable* V1, const Variable* V2) { } - void leaveScope() { } + void enterScope(const Variable *V1, const Variable *V2) {} + void leaveScope() {} - bool compareVariableRefs(const Variable* V1, const Variable* V2) { + bool compareVariableRefs(const Variable *V1, const Variable *V2) { return V1 == V2; } @@ -333,23 +359,21 @@ public: } }; - - class MatchComparator : public Comparator<MatchComparator> { public: // Result type for the comparison, e.g. bool for simple equality, // or int for lexigraphic comparison (-1, 0, 1). Must have one value which // denotes "true". - typedef bool CType; + using CType = bool; CType trueResult() { return true; } bool notTrue(CType ct) { return !ct; } - bool compareIntegers(unsigned i, unsigned j) { return i == j; } - bool compareStrings (StringRef s, StringRef r) { return s == r; } - bool comparePointers(const void* P, const void* Q) { return P == Q; } + bool compareIntegers(unsigned i, unsigned j) { return i == j; } + bool compareStrings (StringRef s, StringRef r) { return s == r; } + bool comparePointers(const void *P, const void *Q) { return P == Q; } - bool compare(const SExpr *E1, const SExpr* E2) { + bool compare(const SExpr *E1, const SExpr *E2) { // Wildcards match anything. if (E1->opcode() == COP_Wildcard || E2->opcode() == COP_Wildcard) return true; @@ -360,8 +384,8 @@ public: } // TODO -- handle alpha-renaming of variables - void enterScope(const Variable* V1, const Variable* V2) { } - void leaveScope() { } + void enterScope(const Variable* V1, const Variable* V2) {} + void leaveScope() {} bool compareVariableRefs(const Variable* V1, const Variable* V2) { return V1 == V2; @@ -373,8 +397,6 @@ public: } }; - - // inline std::ostream& operator<<(std::ostream& SS, StringRef R) { // return SS.write(R.data(), R.size()); // } @@ -383,14 +405,18 @@ public: template <typename Self, typename StreamType> class PrettyPrinter { private: - bool Verbose; // Print out additional information - bool Cleanup; // Omit redundant decls. - bool CStyle; // Print exprs in C-like syntax. + // Print out additional information. + bool Verbose; + + // Omit redundant decls. + bool Cleanup; + + // Print exprs in C-like syntax. + bool CStyle; public: PrettyPrinter(bool V = false, bool C = true, bool CS = true) - : Verbose(V), Cleanup(C), CStyle(CS) - {} + : Verbose(V), Cleanup(C), CStyle(CS) {} static void print(const SExpr *E, StreamType &SS) { Self printer; @@ -470,7 +496,6 @@ protected: } } - void printSExpr(const SExpr *E, StreamType &SS, unsigned P, bool Sub=true) { if (!E) { self()->printNull(SS); @@ -531,18 +556,16 @@ protected: else { ValueType VT = E->valueType(); switch (VT.Base) { - case ValueType::BT_Void: { + case ValueType::BT_Void: SS << "void"; return; - } - case ValueType::BT_Bool: { + case ValueType::BT_Bool: if (E->as<bool>().value()) SS << "true"; else SS << "false"; return; - } - case ValueType::BT_Int: { + case ValueType::BT_Int: switch (VT.Size) { case ValueType::ST_8: if (VT.Signed) @@ -572,8 +595,7 @@ protected: break; } break; - } - case ValueType::BT_Float: { + case ValueType::BT_Float: switch (VT.Size) { case ValueType::ST_32: printLiteralT(&E->as<float>(), SS); @@ -585,22 +607,18 @@ protected: break; } break; - } - case ValueType::BT_String: { + case ValueType::BT_String: SS << "\""; printLiteralT(&E->as<StringRef>(), SS); SS << "\""; return; - } - case ValueType::BT_Pointer: { + case ValueType::BT_Pointer: SS << "#ptr"; return; - } - case ValueType::BT_ValueRef: { + case ValueType::BT_ValueRef: SS << "#vref"; return; } - } } SS << "#lit"; } @@ -688,8 +706,8 @@ protected: void printProject(const Project *E, StreamType &SS) { if (CStyle) { // Omit the this-> - if (const SApply *SAP = dyn_cast<SApply>(E->record())) { - if (const Variable *V = dyn_cast<Variable>(SAP->sfun())) { + if (const auto *SAP = dyn_cast<SApply>(E->record())) { + if (const auto *V = dyn_cast<Variable>(SAP->sfun())) { if (!SAP->isDelegation() && V->kind() == Variable::VK_SFun) { SS << E->slotName(); return; @@ -704,12 +722,10 @@ protected: } } self()->printSExpr(E->record(), SS, Prec_Postfix); - if (CStyle && E->isArrow()) { + if (CStyle && E->isArrow()) SS << "->"; - } - else { + else SS << "."; - } SS << E->slotName(); } @@ -780,18 +796,16 @@ protected: void printSCFG(const SCFG *E, StreamType &SS) { SS << "CFG {\n"; - for (auto BBI : *E) { + for (const auto *BBI : *E) printBasicBlock(BBI, SS); - } SS << "}"; newline(SS); } - void printBBInstr(const SExpr *E, StreamType &SS) { bool Sub = false; if (E->opcode() == COP_Variable) { - auto *V = cast<Variable>(E); + const auto *V = cast<Variable>(E); SS << "let " << V->name() << V->id() << " = "; E = V->definition(); Sub = true; @@ -810,10 +824,10 @@ protected: SS << " BB_" << E->parent()->blockID(); newline(SS); - for (auto *A : E->arguments()) + for (const auto *A : E->arguments()) printBBInstr(A, SS); - for (auto *I : E->instructions()) + for (const auto *I : E->instructions()) printBBInstr(I, SS); const SExpr *T = E->terminator(); @@ -831,7 +845,7 @@ protected: self()->printSExpr(E->values()[0], SS, Prec_MAX); else { unsigned i = 0; - for (auto V : E->values()) { + for (const auto *V : E->values()) { if (i++ > 0) SS << ", "; self()->printSExpr(V, SS, Prec_MAX); @@ -890,13 +904,10 @@ protected: } }; +class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> {}; -class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> { }; - - - -} // end namespace til -} // end namespace threadSafety -} // end namespace clang +} // namespace til +} // namespace threadSafety +} // namespace clang -#endif // LLVM_CLANG_THREAD_SAFETY_TRAVERSE_H +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H diff --git a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/include/clang/Analysis/Analyses/ThreadSafetyUtil.h index cb80ce5da8d2..16583939d542 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyUtil.h @@ -1,4 +1,4 @@ -//===- ThreadSafetyUtil.h --------------------------------------*- C++ --*-===// +//===- ThreadSafetyUtil.h ---------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,18 +14,23 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H -#include "clang/AST/ExprCXX.h" +#include "clang/AST/Decl.h" +#include "clang/Basic/LLVM.h" #include "llvm/ADT/StringRef.h" -#include "llvm/Support/AlignOf.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" -#include "llvm/Support/Compiler.h" #include <cassert> #include <cstddef> +#include <cstring> +#include <iterator> #include <ostream> -#include <utility> +#include <string> #include <vector> namespace clang { + +class Expr; + namespace threadSafety { namespace til { @@ -41,7 +46,7 @@ private: }; public: - MemRegionRef() : Allocator(nullptr) {} + MemRegionRef() = default; MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {} void *allocate(size_t Sz) { @@ -55,12 +60,13 @@ public: } private: - llvm::BumpPtrAllocator *Allocator; + llvm::BumpPtrAllocator *Allocator = nullptr; }; -} // end namespace til -} // end namespace threadSafety -} // end namespace clang +} // namespace til +} // namespace threadSafety + +} // namespace clang inline void *operator new(size_t Sz, clang::threadSafety::til::MemRegionRef &R) { @@ -70,10 +76,7 @@ inline void *operator new(size_t Sz, namespace clang { namespace threadSafety { -std::string getSourceLiteralString(const clang::Expr *CE); - -using llvm::StringRef; -using clang::SourceLocation; +std::string getSourceLiteralString(const Expr *CE); namespace til { @@ -81,11 +84,13 @@ namespace til { // suitable for use with bump pointer allocation. template <class T> class SimpleArray { public: - SimpleArray() : Data(nullptr), Size(0), Capacity(0) {} + SimpleArray() = default; SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) : Data(Dat), Size(Sz), Capacity(Cp) {} SimpleArray(MemRegionRef A, size_t Cp) - : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {} + : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {} + SimpleArray(const SimpleArray<T> &A) = delete; + SimpleArray(SimpleArray<T> &&A) : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { A.Data = nullptr; @@ -123,10 +128,10 @@ public: reserve(u_max(Size + N, Capacity * 2), A); } - typedef T *iterator; - typedef const T *const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + using iterator = T *; + using const_iterator = const T *; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; size_t size() const { return Size; } size_t capacity() const { return Capacity; } @@ -135,27 +140,30 @@ public: assert(i < Size && "Array index out of bounds."); return Data[i]; } + const T &operator[](unsigned i) const { assert(i < Size && "Array index out of bounds."); return Data[i]; } + T &back() { assert(Size && "No elements in the array."); return Data[Size - 1]; } + const T &back() const { assert(Size && "No elements in the array."); return Data[Size - 1]; } iterator begin() { return Data; } - iterator end() { return Data + Size; } + iterator end() { return Data + Size; } const_iterator begin() const { return Data; } - const_iterator end() const { return Data + Size; } + const_iterator end() const { return Data + Size; } const_iterator cbegin() const { return Data; } - const_iterator cend() const { return Data + Size; } + const_iterator cend() const { return Data + Size; } reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } @@ -163,6 +171,7 @@ public: const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } + const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } @@ -198,6 +207,7 @@ public: llvm::iterator_range<reverse_iterator> reverse() { return llvm::make_range(rbegin(), rend()); } + llvm::iterator_range<const_reverse_iterator> reverse() const { return llvm::make_range(rbegin(), rend()); } @@ -209,14 +219,12 @@ private: static const size_t InitialCapacity = 4; - SimpleArray(const SimpleArray<T> &A) = delete; - - T *Data; - size_t Size; - size_t Capacity; + T *Data = nullptr; + size_t Size = 0; + size_t Capacity = 0; }; -} // end namespace til +} // namespace til // A copy on write vector. // The vector can be in one of three states: @@ -228,20 +236,28 @@ template<typename T> class CopyOnWriteVector { class VectorData { public: - VectorData() : NumRefs(1) { } - VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { } - - unsigned NumRefs; + unsigned NumRefs = 1; std::vector<T> Vect; - }; - // No copy constructor or copy assignment. Use clone() with move assignment. - CopyOnWriteVector(const CopyOnWriteVector &V) = delete; - void operator=(const CopyOnWriteVector &V) = delete; + VectorData() = default; + VectorData(const VectorData &VD) : Vect(VD.Vect) {} + }; public: - CopyOnWriteVector() : Data(nullptr) {} + CopyOnWriteVector() = default; CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; } + + CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { + destroy(); + Data = V.Data; + V.Data = nullptr; + return *this; + } + + // No copy constructor or copy assignment. Use clone() with move assignment. + CopyOnWriteVector(const CopyOnWriteVector &) = delete; + CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete; + ~CopyOnWriteVector() { destroy(); } // Returns true if this holds a valid vector. @@ -283,14 +299,7 @@ public: // Create a lazy copy of this vector. CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } - CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { - destroy(); - Data = V.Data; - V.Data = nullptr; - return *this; - } - - typedef typename std::vector<T>::const_iterator const_iterator; + using const_iterator = typename std::vector<T>::const_iterator; const std::vector<T> &elements() const { return Data->Vect; } @@ -336,14 +345,14 @@ private: ++Data->NumRefs; } - VectorData *Data; + VectorData *Data = nullptr; }; inline std::ostream& operator<<(std::ostream& ss, const StringRef str) { return ss.write(str.data(), str.size()); } -} // end namespace threadSafety -} // end namespace clang +} // namespace threadSafety +} // namespace clang #endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H diff --git a/include/clang/Analysis/Analyses/UninitializedValues.h b/include/clang/Analysis/Analyses/UninitializedValues.h index 53ff20c23560..79d89e0633fd 100644 --- a/include/clang/Analysis/Analyses/UninitializedValues.h +++ b/include/clang/Analysis/Analyses/UninitializedValues.h @@ -1,4 +1,4 @@ -//= UninitializedValues.h - Finding uses of uninitialized values -*- C++ -*-==// +//=- UninitializedValues.h - Finding uses of uninitialized values -*- C++ -*-=// // // The LLVM Compiler Infrastructure // @@ -15,7 +15,7 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H #define LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H -#include "clang/AST/Stmt.h" +#include "clang/Basic/LLVM.h" #include "llvm/ADT/SmallVector.h" namespace clang { @@ -24,6 +24,7 @@ class AnalysisDeclContext; class CFG; class DeclContext; class Expr; +class Stmt; class VarDecl; /// A use of a variable, which might be uninitialized. @@ -39,10 +40,10 @@ private: const Expr *User; /// Is this use uninitialized whenever the function is called? - bool UninitAfterCall; + bool UninitAfterCall = false; /// Is this use uninitialized whenever the variable declaration is reached? - bool UninitAfterDecl; + bool UninitAfterDecl = false; /// Does this use always see an uninitialized value? bool AlwaysUninit; @@ -53,8 +54,7 @@ private: public: UninitUse(const Expr *User, bool AlwaysUninit) - : User(User), UninitAfterCall(false), UninitAfterDecl(false), - AlwaysUninit(AlwaysUninit) {} + : User(User), AlwaysUninit(AlwaysUninit) {} void addUninitBranch(Branch B) { UninitBranches.push_back(B); @@ -70,14 +70,18 @@ public: enum Kind { /// The use might be uninitialized. Maybe, + /// The use is uninitialized whenever a certain branch is taken. Sometimes, + /// The use is uninitialized the first time it is reached after we reach /// the variable's declaration. AfterDecl, + /// The use is uninitialized the first time it is reached after the function /// is called. AfterCall, + /// The use is always uninitialized. Always }; @@ -90,7 +94,8 @@ public: !branch_empty() ? Sometimes : Maybe; } - typedef SmallVectorImpl<Branch>::const_iterator branch_iterator; + using branch_iterator = SmallVectorImpl<Branch>::const_iterator; + /// Branches which inevitably result in the variable being used uninitialized. branch_iterator branch_begin() const { return UninitBranches.begin(); } branch_iterator branch_end() const { return UninitBranches.end(); } @@ -99,7 +104,7 @@ public: class UninitVariablesHandler { public: - UninitVariablesHandler() {} + UninitVariablesHandler() = default; virtual ~UninitVariablesHandler(); /// Called when the uninitialized variable is used at the given expression. @@ -122,5 +127,6 @@ void runUninitializedVariablesAnalysis(const DeclContext &dc, const CFG &cfg, UninitVariablesHandler &handler, UninitVariablesAnalysisStats &stats); -} -#endif +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H diff --git a/include/clang/Analysis/AnalysisDeclContext.h b/include/clang/Analysis/AnalysisDeclContext.h index 03ff4a9516da..8c391b5ee1e5 100644 --- a/include/clang/Analysis/AnalysisDeclContext.h +++ b/include/clang/Analysis/AnalysisDeclContext.h @@ -1,4 +1,4 @@ -//=== AnalysisDeclContext.h - Analysis context for Path Sens analysis --*- C++ -*-// +// AnalysisDeclContext.h - Analysis context for Path Sens analysis -*- C++ -*-// // // The LLVM Compiler Infrastructure // @@ -15,37 +15,42 @@ #ifndef LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H #define LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H -#include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" #include "clang/Analysis/BodyFarm.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/CodeInjector.h" +#include "clang/Basic/LLVM.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" +#include <functional> #include <memory> namespace clang { -class Stmt; +class AnalysisDeclContextManager; +class ASTContext; +class BlockDecl; +class BlockInvocationContext; class CFGReverseBlockReachabilityAnalysis; class CFGStmtMap; -class LiveVariables; -class ManagedAnalysis; +class ImplicitParamDecl; +class LocationContext; +class LocationContextManager; class ParentMap; class PseudoConstantAnalysis; -class LocationContextManager; class StackFrameContext; -class BlockInvocationContext; -class AnalysisDeclContextManager; -class LocationContext; - -namespace idx { class TranslationUnit; } +class Stmt; +class VarDecl; /// The base class of a hierarchy of objects representing analyses tied /// to AnalysisDeclContext. class ManagedAnalysis { protected: - ManagedAnalysis() {} + ManagedAnalysis() = default; + public: virtual ~ManagedAnalysis(); @@ -61,7 +66,6 @@ public: // which creates the analysis object given an AnalysisDeclContext. }; - /// AnalysisDeclContext contains the context data for the function or method /// under analysis. class AnalysisDeclContext { @@ -75,18 +79,19 @@ class AnalysisDeclContext { std::unique_ptr<CFGStmtMap> cfgStmtMap; CFG::BuildOptions cfgBuildOptions; - CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; + CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs = nullptr; - bool builtCFG, builtCompleteCFG; + bool builtCFG = false; + bool builtCompleteCFG = false; std::unique_ptr<ParentMap> PM; std::unique_ptr<PseudoConstantAnalysis> PCA; std::unique_ptr<CFGReverseBlockReachabilityAnalysis> CFA; llvm::BumpPtrAllocator A; - llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; + llvm::DenseMap<const BlockDecl *,void *> *ReferencedBlockVars = nullptr; - void *ManagedAnalyses; + void *ManagedAnalyses = nullptr; public: AnalysisDeclContext(AnalysisDeclContextManager *Mgr, @@ -130,22 +135,22 @@ public: void registerForcedBlockExpression(const Stmt *stmt); const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt); - /// \brief Get the body of the Declaration. + /// Get the body of the Declaration. Stmt *getBody() const; - /// \brief Get the body of the Declaration. + /// Get the body of the Declaration. /// \param[out] IsAutosynthesized Specifies if the body is auto-generated /// by the BodyFarm. Stmt *getBody(bool &IsAutosynthesized) const; - /// \brief Checks if the body of the Decl is generated by the BodyFarm. + /// Checks if the body of the Decl is generated by the BodyFarm. /// /// Note, the lookup is not free. We are going to call getBody behind /// the scenes. /// \sa getBody bool isBodyAutosynthesized() const; - /// \brief Checks if the body of the Decl is generated by the BodyFarm from a + /// Checks if the body of the Decl is generated by the BodyFarm from a /// model file. /// /// Note, the lookup is not free. We are going to call getBody behind @@ -164,7 +169,7 @@ public: void dumpCFG(bool ShowColors); - /// \brief Returns true if we have built a CFG for this analysis context. + /// Returns true if we have built a CFG for this analysis context. /// Note that this doesn't correspond to whether or not a valid CFG exists, it /// corresponds to whether we *attempted* to build one. bool isCFGBuilt() const { return builtCFG; } @@ -172,7 +177,7 @@ public: ParentMap &getParentMap(); PseudoConstantAnalysis *getPseudoConstantAnalysis(); - typedef const VarDecl * const * referenced_decls_iterator; + using referenced_decls_iterator = const VarDecl * const *; llvm::iterator_range<referenced_decls_iterator> getReferencedBlockVars(const BlockDecl *BD); @@ -200,12 +205,13 @@ public: if (!data) { data = T::create(*this); } - return static_cast<T*>(data); + return static_cast<T *>(data); } /// Returns true if the root namespace of the given declaration is the 'std' /// C++ namespace. static bool isInStdNamespace(const Decl *D); + private: ManagedAnalysis *&getAnalysisImpl(const void* tag); @@ -228,7 +234,7 @@ private: protected: LocationContext(ContextKind k, AnalysisDeclContext *ctx, const LocationContext *parent) - : Kind(k), Ctx(ctx), Parent(parent) {} + : Kind(k), Ctx(ctx), Parent(parent) {} public: virtual ~LocationContext(); @@ -258,14 +264,18 @@ public: return Ctx->getSelfDecl(); } - const StackFrameContext *getCurrentStackFrame() const; + const StackFrameContext *getStackFrame() const; /// Return true if the current LocationContext has no caller context. virtual bool inTopFrame() const; virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; - void dumpStack(raw_ostream &OS, StringRef Indent = "") const; + void dumpStack( + raw_ostream &OS, StringRef Indent = {}, const char *NL = "\n", + const char *Sep = "", + std::function<void(const LocationContext *)> printMoreInfoPerContext = + [](const LocationContext *) {}) const; void dumpStack() const; public: @@ -277,6 +287,8 @@ public: }; class StackFrameContext : public LocationContext { + friend class LocationContextManager; + // The callsite where this stack frame is established. const Stmt *CallSite; @@ -286,15 +298,14 @@ class StackFrameContext : public LocationContext { // The index of the callsite in the CFGBlock. unsigned Index; - friend class LocationContextManager; StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s, const CFGBlock *blk, unsigned idx) - : LocationContext(StackFrame, ctx, parent), CallSite(s), - Block(blk), Index(idx) {} + : LocationContext(StackFrame, ctx, parent), CallSite(s), + Block(blk), Index(idx) {} public: - ~StackFrameContext() override {} + ~StackFrameContext() override = default; const Stmt *getCallSite() const { return CallSite; } @@ -321,15 +332,16 @@ public: }; class ScopeContext : public LocationContext { + friend class LocationContextManager; + const Stmt *Enter; - friend class LocationContextManager; ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s) - : LocationContext(Scope, ctx, parent), Enter(s) {} + : LocationContext(Scope, ctx, parent), Enter(s) {} public: - ~ScopeContext() override {} + ~ScopeContext() override = default; void Profile(llvm::FoldingSetNodeID &ID) override; @@ -344,20 +356,20 @@ public: }; class BlockInvocationContext : public LocationContext { + friend class LocationContextManager; + const BlockDecl *BD; // FIXME: Come up with a more type-safe way to model context-sensitivity. const void *ContextData; - friend class LocationContextManager; - BlockInvocationContext(AnalysisDeclContext *ctx, const LocationContext *parent, const BlockDecl *bd, const void *contextData) - : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} + : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} public: - ~BlockInvocationContext() override {} + ~BlockInvocationContext() override = default; const BlockDecl *getBlockDecl() const { return BD; } @@ -379,6 +391,7 @@ public: class LocationContextManager { llvm::FoldingSet<LocationContext> Contexts; + public: ~LocationContextManager(); @@ -407,8 +420,8 @@ private: }; class AnalysisDeclContextManager { - typedef llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>> - ContextMap; + using ContextMap = + llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>>; ContextMap Contexts; LocationContextManager LocContexts; @@ -431,10 +444,14 @@ public: bool addImplicitDtors = false, bool addInitializers = false, bool addTemporaryDtors = false, - bool addLifetime = false, bool addLoopExit = false, + bool addLifetime = false, + bool addLoopExit = false, + bool addScopes = false, bool synthesizeBodies = false, bool addStaticInitBranches = false, bool addCXXNewAllocator = true, + bool addRichCXXConstructors = true, + bool markElidedCXXConstructors = true, CodeInjector *injector = nullptr); AnalysisDeclContext *getContext(const Decl *D); @@ -488,5 +505,6 @@ private: } }; -} // end clang namespace -#endif +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h index cfedb2aa8ed5..f25789822d16 100644 --- a/include/clang/Analysis/CFG.h +++ b/include/clang/Analysis/CFG.h @@ -15,8 +15,9 @@ #ifndef LLVM_CLANG_ANALYSIS_CFG_H #define LLVM_CLANG_ANALYSIS_CFG_H -#include "clang/AST/Stmt.h" +#include "clang/AST/ExprCXX.h" #include "clang/Analysis/Support/BumpVector.h" +#include "clang/Analysis/ConstructionContext.h" #include "clang/Basic/LLVM.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/GraphTraits.h" @@ -55,11 +56,18 @@ class CFGElement { public: enum Kind { // main kind - Statement, Initializer, + ScopeBegin, + ScopeEnd, NewAllocator, LifetimeEnds, LoopExit, + // stmt kind + Statement, + Constructor, + CXXRecordTypedCall, + STMT_BEGIN = Statement, + STMT_END = CXXRecordTypedCall, // dtor kind AutomaticObjectDtor, DeleteDtor, @@ -84,7 +92,7 @@ protected: CFGElement() = default; public: - /// \brief Convert to the specified CFGElement type, asserting that this + /// Convert to the specified CFGElement type, asserting that this /// CFGElement is of the desired type. template<typename T> T castAs() const { @@ -95,7 +103,7 @@ public: return t; } - /// \brief Convert to the specified CFGElement type, returning None if this + /// Convert to the specified CFGElement type, returning None if this /// CFGElement is not of the desired type. template<typename T> Optional<T> getAs() const { @@ -117,7 +125,9 @@ public: class CFGStmt : public CFGElement { public: - CFGStmt(Stmt *S) : CFGElement(Statement, S) {} + explicit CFGStmt(Stmt *S, Kind K = Statement) : CFGElement(K, S) { + assert(isKind(*this)); + } const Stmt *getStmt() const { return static_cast<const Stmt *>(Data1.getPointer()); @@ -126,10 +136,77 @@ public: private: friend class CFGElement; + static bool isKind(const CFGElement &E) { + return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END; + } + +protected: CFGStmt() = default; +}; + +/// CFGConstructor - Represents C++ constructor call. Maintains information +/// necessary to figure out what memory is being initialized by the +/// constructor expression. For now this is only used by the analyzer's CFG. +class CFGConstructor : public CFGStmt { +public: + explicit CFGConstructor(CXXConstructExpr *CE, const ConstructionContext *C) + : CFGStmt(CE, Constructor) { + assert(C); + Data2.setPointer(const_cast<ConstructionContext *>(C)); + } + + const ConstructionContext *getConstructionContext() const { + return static_cast<ConstructionContext *>(Data2.getPointer()); + } + +private: + friend class CFGElement; + + CFGConstructor() = default; + + static bool isKind(const CFGElement &E) { + return E.getKind() == Constructor; + } +}; + +/// CFGCXXRecordTypedCall - Represents a function call that returns a C++ object +/// by value. This, like constructor, requires a construction context in order +/// to understand the storage of the returned object . In C such tracking is not +/// necessary because no additional effort is required for destroying the object +/// or modeling copy elision. Like CFGConstructor, this element is for now only +/// used by the analyzer's CFG. +class CFGCXXRecordTypedCall : public CFGStmt { +public: + /// Returns true when call expression \p CE needs to be represented + /// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt. + static bool isCXXRecordTypedCall(CallExpr *CE, const ASTContext &ACtx) { + return CE->getCallReturnType(ACtx).getCanonicalType()->getAsCXXRecordDecl(); + } + + explicit CFGCXXRecordTypedCall(CallExpr *CE, const ConstructionContext *C) + : CFGStmt(CE, CXXRecordTypedCall) { + // FIXME: This is not protected against squeezing a non-record-typed-call + // into the constructor. An assertion would require passing an ASTContext + // which would mean paying for something we don't use. + assert(C && (isa<TemporaryObjectConstructionContext>(C) || + // These are possible in C++17 due to mandatory copy elision. + isa<ReturnedValueConstructionContext>(C) || + isa<VariableConstructionContext>(C) || + isa<ConstructorInitializerConstructionContext>(C))); + Data2.setPointer(const_cast<ConstructionContext *>(C)); + } + + const ConstructionContext *getConstructionContext() const { + return static_cast<ConstructionContext *>(Data2.getPointer()); + } + +private: + friend class CFGElement; + + CFGCXXRecordTypedCall() = default; static bool isKind(const CFGElement &E) { - return E.getKind() == Statement; + return E.getKind() == CXXRecordTypedCall; } }; @@ -137,7 +214,7 @@ private: /// constructor's initialization list. class CFGInitializer : public CFGElement { public: - CFGInitializer(CXXCtorInitializer *initializer) + explicit CFGInitializer(CXXCtorInitializer *initializer) : CFGElement(Initializer, initializer) {} CXXCtorInitializer* getInitializer() const { @@ -223,6 +300,55 @@ private: } }; +/// Represents beginning of a scope implicitly generated +/// by the compiler on encountering a CompoundStmt +class CFGScopeBegin : public CFGElement { +public: + CFGScopeBegin() {} + CFGScopeBegin(const VarDecl *VD, const Stmt *S) + : CFGElement(ScopeBegin, VD, S) {} + + // Get statement that triggered a new scope. + const Stmt *getTriggerStmt() const { + return static_cast<Stmt*>(Data2.getPointer()); + } + + // Get VD that triggered a new scope. + const VarDecl *getVarDecl() const { + return static_cast<VarDecl *>(Data1.getPointer()); + } + +private: + friend class CFGElement; + static bool isKind(const CFGElement &E) { + Kind kind = E.getKind(); + return kind == ScopeBegin; + } +}; + +/// Represents end of a scope implicitly generated by +/// the compiler after the last Stmt in a CompoundStmt's body +class CFGScopeEnd : public CFGElement { +public: + CFGScopeEnd() {} + CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {} + + const VarDecl *getVarDecl() const { + return static_cast<VarDecl *>(Data1.getPointer()); + } + + const Stmt *getTriggerStmt() const { + return static_cast<Stmt *>(Data2.getPointer()); + } + +private: + friend class CFGElement; + static bool isKind(const CFGElement &E) { + Kind kind = E.getKind(); + return kind == ScopeEnd; + } +}; + /// CFGImplicitDtor - Represents C++ object destructor implicitly generated /// by compiler on various occasions. class CFGImplicitDtor : public CFGElement { @@ -747,6 +873,17 @@ public: Elements.push_back(CFGStmt(statement), C); } + void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC, + BumpVectorContext &C) { + Elements.push_back(CFGConstructor(CE, CC), C); + } + + void appendCXXRecordTypedCall(CallExpr *CE, + const ConstructionContext *CC, + BumpVectorContext &C) { + Elements.push_back(CFGCXXRecordTypedCall(CE, CC), C); + } + void appendInitializer(CXXCtorInitializer *initializer, BumpVectorContext &C) { Elements.push_back(CFGInitializer(initializer), C); @@ -757,6 +894,24 @@ public: Elements.push_back(CFGNewAllocator(NE), C); } + void appendScopeBegin(const VarDecl *VD, const Stmt *S, + BumpVectorContext &C) { + Elements.push_back(CFGScopeBegin(VD, S), C); + } + + void prependScopeBegin(const VarDecl *VD, const Stmt *S, + BumpVectorContext &C) { + Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C); + } + + void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { + Elements.push_back(CFGScopeEnd(VD, S), C); + } + + void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { + Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C); + } + void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { Elements.push_back(CFGBaseDtor(BS), C); } @@ -810,9 +965,22 @@ public: *I = CFGLifetimeEnds(VD, S); return ++I; } + + // Scope leaving must be performed in reversed order. So insertion is in two + // steps. First we prepare space for some number of elements, then we insert + // the elements beginning at the last position in prepared space. + iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) { + return iterator( + Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C)); + } + iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S) { + *I = CFGScopeEnd(VD, S); + return ++I; + } + }; -/// \brief CFGCallback defines methods that should be called when a logical +/// CFGCallback defines methods that should be called when a logical /// operator error is found when building the CFG. class CFGCallback { public: @@ -852,9 +1020,12 @@ public: bool AddLifetime = false; bool AddLoopExit = false; bool AddTemporaryDtors = false; + bool AddScopes = false; bool AddStaticInitBranches = false; bool AddCXXNewAllocator = false; bool AddCXXDefaultInitExprInCtors = false; + bool AddRichCXXConstructors = false; + bool MarkElidedCXXConstructors = false; BuildOptions() = default; diff --git a/include/clang/Analysis/CallGraph.h b/include/clang/Analysis/CallGraph.h index bdcdfecddc3e..ae0f392ed969 100644 --- a/include/clang/Analysis/CallGraph.h +++ b/include/clang/Analysis/CallGraph.h @@ -34,7 +34,7 @@ class Decl; class DeclContext; class Stmt; -/// \brief The AST-based call graph. +/// The AST-based call graph. /// /// The call graph extends itself with the given declarations by implementing /// the recursive AST visitor, which constructs the graph by visiting the given @@ -55,7 +55,7 @@ public: CallGraph(); ~CallGraph(); - /// \brief Populate the call graph with the functions in the given + /// Populate the call graph with the functions in the given /// declaration. /// /// Recursively walks the declaration to find all the dependent Decls as well. @@ -63,13 +63,13 @@ public: TraverseDecl(D); } - /// \brief Determine if a declaration should be included in the graph. + /// Determine if a declaration should be included in the graph. static bool includeInGraph(const Decl *D); - /// \brief Lookup the node for the given declaration. + /// Lookup the node for the given declaration. CallGraphNode *getNode(const Decl *) const; - /// \brief Lookup the node for the given declaration. If none found, insert + /// Lookup the node for the given declaration. If none found, insert /// one into the graph. CallGraphNode *getOrInsertNode(Decl *); @@ -83,7 +83,7 @@ public: const_iterator begin() const { return FunctionMap.begin(); } const_iterator end() const { return FunctionMap.end(); } - /// \brief Get the number of nodes in the graph. + /// Get the number of nodes in the graph. unsigned size() const { return FunctionMap.size(); } /// \ brief Get the virtual root of the graph, all the functions available @@ -133,10 +133,10 @@ public: bool shouldWalkTypesOfTypeLocs() const { return false; } private: - /// \brief Add the given declaration to the call graph. + /// Add the given declaration to the call graph. void addNodeForDecl(Decl *D, bool IsGlobal); - /// \brief Allocate a new node in the graph. + /// Allocate a new node in the graph. CallGraphNode *allocateNewNode(Decl *); }; @@ -145,10 +145,10 @@ public: using CallRecord = CallGraphNode *; private: - /// \brief The function/method declaration. + /// The function/method declaration. Decl *FD; - /// \brief The list of functions called from this node. + /// The list of functions called from this node. SmallVector<CallRecord, 5> CalledFunctions; public: diff --git a/include/clang/Analysis/CloneDetection.h b/include/clang/Analysis/CloneDetection.h index 051b9236658c..955777a11a65 100644 --- a/include/clang/Analysis/CloneDetection.h +++ b/include/clang/Analysis/CloneDetection.h @@ -161,7 +161,7 @@ public: /// The result of findClones can be further constrained with the constrainClones /// method. /// -/// This class only searches for clones in exectuable source code +/// This class only searches for clones in executable source code /// (e.g. function bodies). Other clones (e.g. cloned comments or declarations) /// are not supported. class CloneDetector { @@ -351,7 +351,7 @@ struct FilenamePatternConstraint { /// Analyzes the pattern of the referenced variables in a statement. class VariablePattern { - /// Describes an occurence of a variable reference in a statement. + /// Describes an occurrence of a variable reference in a statement. struct VariableOccurence { /// The index of the associated VarDecl in the Variables vector. size_t KindID; @@ -362,7 +362,7 @@ class VariablePattern { : KindID(KindID), Mention(Mention) {} }; - /// All occurences of referenced variables in the order of appearance. + /// All occurrences of referenced variables in the order of appearance. std::vector<VariableOccurence> Occurences; /// List of referenced variables in the order of appearance. /// Every item in this list is unique. diff --git a/include/clang/Analysis/CodeInjector.h b/include/clang/Analysis/CodeInjector.h index 413a55b05b07..2c87cde996f2 100644 --- a/include/clang/Analysis/CodeInjector.h +++ b/include/clang/Analysis/CodeInjector.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// /// /// \file -/// \brief Defines the clang::CodeInjector interface which is responsible for +/// Defines the clang::CodeInjector interface which is responsible for /// injecting AST of function definitions that may not be available in the /// original source. /// @@ -23,7 +23,7 @@ class Stmt; class FunctionDecl; class ObjCMethodDecl; -/// \brief CodeInjector is an interface which is responsible for injecting AST +/// CodeInjector is an interface which is responsible for injecting AST /// of function definitions that may not be available in the original source. /// /// The getBody function will be called each time the static analyzer examines a diff --git a/include/clang/Analysis/ConstructionContext.h b/include/clang/Analysis/ConstructionContext.h new file mode 100644 index 000000000000..40cb0e7e5dda --- /dev/null +++ b/include/clang/Analysis/ConstructionContext.h @@ -0,0 +1,474 @@ +//===- ConstructionContext.h - CFG constructor information ------*- 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 the ConstructionContext class and its sub-classes, +// which represent various different ways of constructing C++ objects +// with the additional information the users may want to know about +// the constructor. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CONSTRUCTIONCONTEXT_H +#define LLVM_CLANG_ANALYSIS_CONSTRUCTIONCONTEXT_H + +#include "clang/Analysis/Support/BumpVector.h" +#include "clang/AST/ExprCXX.h" + +namespace clang { + +/// Construction context is a linked list of multiple layers. Layers are +/// created gradually while traversing the AST, and layers that represent +/// the outmost AST nodes are built first, while the node that immediately +/// contains the constructor would be built last and capture the previous +/// layers as its parents. Construction context captures the last layer +/// (which has links to the previous layers) and classifies the seemingly +/// arbitrary chain of layers into one of the possible ways of constructing +/// an object in C++ for user-friendly experience. +class ConstructionContextLayer { +public: + typedef llvm::PointerUnion<Stmt *, CXXCtorInitializer *> TriggerTy; + +private: + /// The construction site - the statement that triggered the construction + /// for one of its parts. For instance, stack variable declaration statement + /// triggers construction of itself or its elements if it's an array, + /// new-expression triggers construction of the newly allocated object(s). + TriggerTy Trigger; + + /// Sometimes a single trigger is not enough to describe the construction + /// site. In this case we'd have a chain of "partial" construction context + /// layers. + /// Some examples: + /// - A constructor within in an aggregate initializer list within a variable + /// would have a construction context of the initializer list with + /// the parent construction context of a variable. + /// - A constructor for a temporary that needs to be both destroyed + /// and materialized into an elidable copy constructor would have a + /// construction context of a CXXBindTemporaryExpr with the parent + /// construction context of a MaterializeTemproraryExpr. + /// Not all of these are currently supported. + const ConstructionContextLayer *Parent = nullptr; + + ConstructionContextLayer(TriggerTy Trigger, + const ConstructionContextLayer *Parent) + : Trigger(Trigger), Parent(Parent) {} + +public: + static const ConstructionContextLayer * + create(BumpVectorContext &C, TriggerTy Trigger, + const ConstructionContextLayer *Parent = nullptr); + + const ConstructionContextLayer *getParent() const { return Parent; } + bool isLast() const { return !Parent; } + + const Stmt *getTriggerStmt() const { + return Trigger.dyn_cast<Stmt *>(); + } + + const CXXCtorInitializer *getTriggerInit() const { + return Trigger.dyn_cast<CXXCtorInitializer *>(); + } + + /// Returns true if these layers are equal as individual layers, even if + /// their parents are different. + bool isSameLayer(const ConstructionContextLayer *Other) const { + assert(Other); + return (Trigger == Other->Trigger); + } + + /// See if Other is a proper initial segment of this construction context + /// in terms of the parent chain - i.e. a few first parents coincide and + /// then the other context terminates but our context goes further - i.e., + /// we are providing the same context that the other context provides, + /// and a bit more above that. + bool isStrictlyMoreSpecificThan(const ConstructionContextLayer *Other) const; +}; + + +/// ConstructionContext's subclasses describe different ways of constructing +/// an object in C++. The context re-captures the essential parent AST nodes +/// of the CXXConstructExpr it is assigned to and presents these nodes +/// through easy-to-understand accessor methods. +class ConstructionContext { +public: + enum Kind { + SimpleVariableKind, + CXX17ElidedCopyVariableKind, + VARIABLE_BEGIN = SimpleVariableKind, + VARIABLE_END = CXX17ElidedCopyVariableKind, + SimpleConstructorInitializerKind, + CXX17ElidedCopyConstructorInitializerKind, + INITIALIZER_BEGIN = SimpleConstructorInitializerKind, + INITIALIZER_END = CXX17ElidedCopyConstructorInitializerKind, + NewAllocatedObjectKind, + SimpleTemporaryObjectKind, + ElidedTemporaryObjectKind, + TEMPORARY_BEGIN = SimpleTemporaryObjectKind, + TEMPORARY_END = ElidedTemporaryObjectKind, + SimpleReturnedValueKind, + CXX17ElidedCopyReturnedValueKind, + RETURNED_VALUE_BEGIN = SimpleReturnedValueKind, + RETURNED_VALUE_END = CXX17ElidedCopyReturnedValueKind + }; + +protected: + Kind K; + + // Do not make public! These need to only be constructed + // via createFromLayers(). + explicit ConstructionContext(Kind K) : K(K) {} + +private: + // A helper function for constructing an instance into a bump vector context. + template <typename T, typename... ArgTypes> + static T *create(BumpVectorContext &C, ArgTypes... Args) { + auto *CC = C.getAllocator().Allocate<T>(); + return new (CC) T(Args...); + } + +public: + /// Consume the construction context layer, together with its parent layers, + /// and wrap it up into a complete construction context. May return null + /// if layers do not form any supported construction context. + static const ConstructionContext * + createFromLayers(BumpVectorContext &C, + const ConstructionContextLayer *TopLayer); + + Kind getKind() const { return K; } +}; + +/// An abstract base class for local variable constructors. +class VariableConstructionContext : public ConstructionContext { + const DeclStmt *DS; + +protected: + VariableConstructionContext(ConstructionContext::Kind K, const DeclStmt *DS) + : ConstructionContext(K), DS(DS) { + assert(classof(this)); + assert(DS); + } + +public: + const DeclStmt *getDeclStmt() const { return DS; } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() >= VARIABLE_BEGIN && + CC->getKind() <= VARIABLE_END; + } +}; + +/// Represents construction into a simple local variable, eg. T var(123);. +/// If a variable has an initializer, eg. T var = makeT();, then the final +/// elidable copy-constructor from makeT() into var would also be a simple +/// variable constructor handled by this class. +class SimpleVariableConstructionContext : public VariableConstructionContext { + friend class ConstructionContext; // Allows to create<>() itself. + + explicit SimpleVariableConstructionContext(const DeclStmt *DS) + : VariableConstructionContext(ConstructionContext::SimpleVariableKind, + DS) {} + +public: + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == SimpleVariableKind; + } +}; + +/// Represents construction into a simple variable with an initializer syntax, +/// with a single constructor, eg. T var = makeT();. Such construction context +/// may only appear in C++17 because previously it was split into a temporary +/// object constructor and an elidable simple variable copy-constructor and +/// we were producing separate construction contexts for these constructors. +/// In C++17 we have a single construction context that combines both. +/// Note that if the object has trivial destructor, then this code is +/// indistinguishable from a simple variable constructor on the AST level; +/// in this case we provide a simple variable construction context. +class CXX17ElidedCopyVariableConstructionContext + : public VariableConstructionContext { + const CXXBindTemporaryExpr *BTE; + + friend class ConstructionContext; // Allows to create<>() itself. + + explicit CXX17ElidedCopyVariableConstructionContext( + const DeclStmt *DS, const CXXBindTemporaryExpr *BTE) + : VariableConstructionContext(CXX17ElidedCopyVariableKind, DS), BTE(BTE) { + assert(BTE); + } + +public: + const CXXBindTemporaryExpr *getCXXBindTemporaryExpr() const { return BTE; } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == CXX17ElidedCopyVariableKind; + } +}; + +// An abstract base class for constructor-initializer-based constructors. +class ConstructorInitializerConstructionContext : public ConstructionContext { + const CXXCtorInitializer *I; + +protected: + explicit ConstructorInitializerConstructionContext( + ConstructionContext::Kind K, const CXXCtorInitializer *I) + : ConstructionContext(K), I(I) { + assert(classof(this)); + assert(I); + } + +public: + const CXXCtorInitializer *getCXXCtorInitializer() const { return I; } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() >= INITIALIZER_BEGIN && + CC->getKind() <= INITIALIZER_END; + } +}; + +/// Represents construction into a field or a base class within a bigger object +/// via a constructor initializer, eg. T(): field(123) { ... }. +class SimpleConstructorInitializerConstructionContext + : public ConstructorInitializerConstructionContext { + friend class ConstructionContext; // Allows to create<>() itself. + + explicit SimpleConstructorInitializerConstructionContext( + const CXXCtorInitializer *I) + : ConstructorInitializerConstructionContext( + ConstructionContext::SimpleConstructorInitializerKind, I) {} + +public: + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == SimpleConstructorInitializerKind; + } +}; + +/// Represents construction into a field or a base class within a bigger object +/// via a constructor initializer, with a single constructor, eg. +/// T(): field(Field(123)) { ... }. Such construction context may only appear +/// in C++17 because previously it was split into a temporary object constructor +/// and an elidable simple constructor-initializer copy-constructor and we were +/// producing separate construction contexts for these constructors. In C++17 +/// we have a single construction context that combines both. Note that if the +/// object has trivial destructor, then this code is indistinguishable from +/// a simple constructor-initializer constructor on the AST level; in this case +/// we provide a simple constructor-initializer construction context. +class CXX17ElidedCopyConstructorInitializerConstructionContext + : public ConstructorInitializerConstructionContext { + const CXXBindTemporaryExpr *BTE; + + friend class ConstructionContext; // Allows to create<>() itself. + + explicit CXX17ElidedCopyConstructorInitializerConstructionContext( + const CXXCtorInitializer *I, const CXXBindTemporaryExpr *BTE) + : ConstructorInitializerConstructionContext( + CXX17ElidedCopyConstructorInitializerKind, I), + BTE(BTE) { + assert(BTE); + } + +public: + const CXXBindTemporaryExpr *getCXXBindTemporaryExpr() const { return BTE; } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == CXX17ElidedCopyConstructorInitializerKind; + } +}; + +/// Represents immediate initialization of memory allocated by operator new, +/// eg. new T(123);. +class NewAllocatedObjectConstructionContext : public ConstructionContext { + const CXXNewExpr *NE; + + friend class ConstructionContext; // Allows to create<>() itself. + + explicit NewAllocatedObjectConstructionContext(const CXXNewExpr *NE) + : ConstructionContext(ConstructionContext::NewAllocatedObjectKind), + NE(NE) { + assert(NE); + } + +public: + const CXXNewExpr *getCXXNewExpr() const { return NE; } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == NewAllocatedObjectKind; + } +}; + +/// Represents a temporary object, eg. T(123), that does not immediately cross +/// function boundaries "by value"; constructors that construct function +/// value-type arguments or values that are immediately returned from the +/// function that returns a value receive separate construction context kinds. +class TemporaryObjectConstructionContext : public ConstructionContext { + const CXXBindTemporaryExpr *BTE; + const MaterializeTemporaryExpr *MTE; + +protected: + explicit TemporaryObjectConstructionContext( + ConstructionContext::Kind K, const CXXBindTemporaryExpr *BTE, + const MaterializeTemporaryExpr *MTE) + : ConstructionContext(K), BTE(BTE), MTE(MTE) { + // Both BTE and MTE can be null here, all combinations possible. + // Even though for now at least one should be non-null, we simply haven't + // implemented the other case yet (this would be a temporary in the middle + // of nowhere that doesn't have a non-trivial destructor). + } + +public: + /// CXXBindTemporaryExpr here is non-null as long as the temporary has + /// a non-trivial destructor. + const CXXBindTemporaryExpr *getCXXBindTemporaryExpr() const { + return BTE; + } + + /// MaterializeTemporaryExpr is non-null as long as the temporary is actually + /// used after construction, eg. by binding to a reference (lifetime + /// extension), accessing a field, calling a method, or passing it into + /// a function (an elidable copy or move constructor would be a common + /// example) by reference. + const MaterializeTemporaryExpr *getMaterializedTemporaryExpr() const { + return MTE; + } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() >= TEMPORARY_BEGIN && CC->getKind() <= TEMPORARY_END; + } +}; + +/// Represents a temporary object that is not constructed for the purpose of +/// being immediately copied/moved by an elidable copy/move-constructor. +/// This includes temporary objects "in the middle of nowhere" like T(123) and +/// lifetime-extended temporaries. +class SimpleTemporaryObjectConstructionContext + : public TemporaryObjectConstructionContext { + friend class ConstructionContext; // Allows to create<>() itself. + + explicit SimpleTemporaryObjectConstructionContext( + const CXXBindTemporaryExpr *BTE, const MaterializeTemporaryExpr *MTE) + : TemporaryObjectConstructionContext( + ConstructionContext::SimpleTemporaryObjectKind, BTE, MTE) {} + +public: + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == SimpleTemporaryObjectKind; + } +}; + +/// Represents a temporary object that is constructed for the sole purpose +/// of being immediately copied by an elidable copy/move constructor. +/// For example, T t = T(123); includes a temporary T(123) that is immediately +/// copied to variable t. In such cases the elidable copy can (but not +/// necessarily should) be omitted ("elided") accodring to the rules of the +/// language; the constructor would then construct variable t directly. +/// This construction context contains information of the elidable constructor +/// and its respective construction context. +class ElidedTemporaryObjectConstructionContext + : public TemporaryObjectConstructionContext { + const CXXConstructExpr *ElidedCE; + const ConstructionContext *ElidedCC; + + friend class ConstructionContext; // Allows to create<>() itself. + + explicit ElidedTemporaryObjectConstructionContext( + const CXXBindTemporaryExpr *BTE, const MaterializeTemporaryExpr *MTE, + const CXXConstructExpr *ElidedCE, const ConstructionContext *ElidedCC) + : TemporaryObjectConstructionContext( + ConstructionContext::ElidedTemporaryObjectKind, BTE, MTE), + ElidedCE(ElidedCE), ElidedCC(ElidedCC) { + // Elided constructor and its context should be either both specified + // or both unspecified. In the former case, the constructor must be + // elidable. + assert(ElidedCE && ElidedCE->isElidable() && ElidedCC); + } + +public: + const CXXConstructExpr *getConstructorAfterElision() const { + return ElidedCE; + } + + const ConstructionContext *getConstructionContextAfterElision() const { + return ElidedCC; + } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == ElidedTemporaryObjectKind; + } +}; + +class ReturnedValueConstructionContext : public ConstructionContext { + const ReturnStmt *RS; + +protected: + explicit ReturnedValueConstructionContext(ConstructionContext::Kind K, + const ReturnStmt *RS) + : ConstructionContext(K), RS(RS) { + assert(classof(this)); + assert(RS); + } + +public: + const ReturnStmt *getReturnStmt() const { return RS; } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() >= RETURNED_VALUE_BEGIN && + CC->getKind() <= RETURNED_VALUE_END; + } +}; + +/// Represents a temporary object that is being immediately returned from a +/// function by value, eg. return t; or return T(123);. In this case there is +/// always going to be a constructor at the return site. However, the usual +/// temporary-related bureaucracy (CXXBindTemporaryExpr, +/// MaterializeTemporaryExpr) is normally located in the caller function's AST. +class SimpleReturnedValueConstructionContext + : public ReturnedValueConstructionContext { + friend class ConstructionContext; // Allows to create<>() itself. + + explicit SimpleReturnedValueConstructionContext(const ReturnStmt *RS) + : ReturnedValueConstructionContext( + ConstructionContext::SimpleReturnedValueKind, RS) {} + +public: + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == SimpleReturnedValueKind; + } +}; + +/// Represents a temporary object that is being immediately returned from a +/// function by value, eg. return t; or return T(123); in C++17. +/// In C++17 there is not going to be an elidable copy constructor at the +/// return site. However, the usual temporary-related bureaucracy (CXXBindTemporaryExpr, +/// MaterializeTemporaryExpr) is normally located in the caller function's AST. +/// Note that if the object has trivial destructor, then this code is +/// indistinguishable from a simple returned value constructor on the AST level; +/// in this case we provide a simple returned value construction context. +class CXX17ElidedCopyReturnedValueConstructionContext + : public ReturnedValueConstructionContext { + const CXXBindTemporaryExpr *BTE; + + friend class ConstructionContext; // Allows to create<>() itself. + + explicit CXX17ElidedCopyReturnedValueConstructionContext( + const ReturnStmt *RS, const CXXBindTemporaryExpr *BTE) + : ReturnedValueConstructionContext( + ConstructionContext::CXX17ElidedCopyReturnedValueKind, RS), + BTE(BTE) { + assert(BTE); + } + +public: + const CXXBindTemporaryExpr *getCXXBindTemporaryExpr() const { return BTE; } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == CXX17ElidedCopyReturnedValueKind; + } +}; + +} // end namespace clang + +#endif // LLVM_CLANG_ANALYSIS_CONSTRUCTIONCONTEXT_H diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h index 2d59dec48a88..e8f0d61617eb 100644 --- a/include/clang/Analysis/ProgramPoint.h +++ b/include/clang/Analysis/ProgramPoint.h @@ -73,8 +73,9 @@ public: PostStoreKind, PostConditionKind, PostLValueKind, + PostAllocatorCallKind, MinPostStmtKind = PostStmtKind, - MaxPostStmtKind = PostLValueKind, + MaxPostStmtKind = PostAllocatorCallKind, PostInitializerKind, CallEnterKind, CallExitBeginKind, @@ -97,7 +98,7 @@ private: llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag; protected: - ProgramPoint() {} + ProgramPoint() = default; ProgramPoint(const void *P, Kind k, const LocationContext *l, @@ -134,7 +135,7 @@ public: getLocationContext(), tag); } - /// \brief Convert to the specified ProgramPoint type, asserting that this + /// Convert to the specified ProgramPoint type, asserting that this /// ProgramPoint is of the desired type. template<typename T> T castAs() const { @@ -145,7 +146,7 @@ public: return t; } - /// \brief Convert to the specified ProgramPoint type, returning None if this + /// Convert to the specified ProgramPoint type, returning None if this /// ProgramPoint is not of the desired type. template<typename T> Optional<T> getAs() const { @@ -166,7 +167,7 @@ public: return (Kind) x; } - /// \brief Is this a program point corresponding to purge/removal of dead + /// Is this a program point corresponding to purge/removal of dead /// symbols and bindings. bool isPurgeKind() { Kind K = getKind(); @@ -180,6 +181,10 @@ public: return L.getPointer(); } + const StackFrameContext *getStackFrame() const { + return getLocationContext()->getStackFrame(); + } + // For use with DenseMap. This hash is probably slow. unsigned getHashValue() const { llvm::FoldingSetNodeID ID; @@ -233,7 +238,7 @@ public: private: friend class ProgramPoint; - BlockEntrance() {} + BlockEntrance() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == BlockEntranceKind; } @@ -254,7 +259,7 @@ public: private: friend class ProgramPoint; - BlockExit() {} + BlockExit() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == BlockExitKind; } @@ -274,7 +279,7 @@ public: const T* getStmtAs() const { return dyn_cast<T>(getStmt()); } protected: - StmtPoint() {} + StmtPoint() = default; private: friend class ProgramPoint; static bool isKind(const ProgramPoint &Location) { @@ -294,7 +299,7 @@ public: private: friend class ProgramPoint; - PreStmt() {} + PreStmt() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PreStmtKind; } @@ -302,7 +307,7 @@ private: class PostStmt : public StmtPoint { protected: - PostStmt() {} + PostStmt() = default; PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L, const ProgramPointTag *tag = nullptr) : StmtPoint(S, data, k, L, tag) {} @@ -333,7 +338,7 @@ public: private: friend class ProgramPoint; - PostCondition() {} + PostCondition() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostConditionKind; } @@ -341,7 +346,7 @@ private: class LocationCheck : public StmtPoint { protected: - LocationCheck() {} + LocationCheck() = default; LocationCheck(const Stmt *S, const LocationContext *L, ProgramPoint::Kind K, const ProgramPointTag *tag) : StmtPoint(S, nullptr, K, L, tag) {} @@ -362,7 +367,7 @@ public: private: friend class ProgramPoint; - PreLoad() {} + PreLoad() = default; static bool isKind(const ProgramPoint &location) { return location.getKind() == PreLoadKind; } @@ -376,7 +381,7 @@ public: private: friend class ProgramPoint; - PreStore() {} + PreStore() = default; static bool isKind(const ProgramPoint &location) { return location.getKind() == PreStoreKind; } @@ -390,13 +395,13 @@ public: private: friend class ProgramPoint; - PostLoad() {} + PostLoad() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostLoadKind; } }; -/// \brief Represents a program point after a store evaluation. +/// Represents a program point after a store evaluation. class PostStore : public PostStmt { public: /// Construct the post store point. @@ -409,7 +414,7 @@ public: setData2(Loc); } - /// \brief Returns the information about the location used in the store, + /// Returns the information about the location used in the store, /// how it was uttered in the code. const void *getLocationValue() const { return getData2(); @@ -417,7 +422,7 @@ public: private: friend class ProgramPoint; - PostStore() {} + PostStore() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostStoreKind; } @@ -431,7 +436,7 @@ public: private: friend class ProgramPoint; - PostLValue() {} + PostLValue() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostLValueKind; } @@ -447,7 +452,7 @@ public: private: friend class ProgramPoint; - PreStmtPurgeDeadSymbols() {} + PreStmtPurgeDeadSymbols() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PreStmtPurgeDeadSymbolsKind; } @@ -463,7 +468,7 @@ public: private: friend class ProgramPoint; - PostStmtPurgeDeadSymbols() {} + PostStmtPurgeDeadSymbols() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostStmtPurgeDeadSymbolsKind; } @@ -487,7 +492,7 @@ public: private: friend class ProgramPoint; - BlockEdge() {} + BlockEdge() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == BlockEdgeKind; } @@ -495,7 +500,7 @@ private: class PostInitializer : public ProgramPoint { public: - /// \brief Construct a PostInitializer point that represents a location after + /// Construct a PostInitializer point that represents a location after /// CXXCtorInitializer expression evaluation. /// /// \param I The initializer. @@ -509,14 +514,14 @@ public: return static_cast<const CXXCtorInitializer *>(getData1()); } - /// \brief Returns the location of the field. + /// Returns the location of the field. const void *getLocationValue() const { return getData2(); } private: friend class ProgramPoint; - PostInitializer() {} + PostInitializer() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostInitializerKind; } @@ -537,7 +542,7 @@ public: } protected: - ImplicitCallPoint() {} + ImplicitCallPoint() = default; private: friend class ProgramPoint; static bool isKind(const ProgramPoint &Location) { @@ -557,7 +562,7 @@ public: private: friend class ProgramPoint; - PreImplicitCall() {} + PreImplicitCall() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PreImplicitCallKind; } @@ -574,12 +579,26 @@ public: private: friend class ProgramPoint; - PostImplicitCall() {} + PostImplicitCall() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostImplicitCallKind; } }; +class PostAllocatorCall : public StmtPoint { +public: + PostAllocatorCall(const Stmt *S, const LocationContext *L, + const ProgramPointTag *Tag = nullptr) + : StmtPoint(S, nullptr, PostAllocatorCallKind, L, Tag) {} + +private: + friend class ProgramPoint; + PostAllocatorCall() = default; + static bool isKind(const ProgramPoint &Location) { + return Location.getKind() == PostAllocatorCallKind; + } +}; + /// Represents a point when we begin processing an inlined call. /// CallEnter uses the caller's location context. class CallEnter : public ProgramPoint { @@ -605,7 +624,7 @@ public: private: friend class ProgramPoint; - CallEnter() {} + CallEnter() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == CallEnterKind; } @@ -626,9 +645,13 @@ public: CallExitBegin(const StackFrameContext *L, const ReturnStmt *RS) : ProgramPoint(RS, CallExitBeginKind, L, nullptr) { } + const ReturnStmt *getReturnStmt() const { + return static_cast<const ReturnStmt *>(getData1()); + } + private: friend class ProgramPoint; - CallExitBegin() {} + CallExitBegin() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == CallExitBeginKind; } @@ -649,7 +672,7 @@ public: private: friend class ProgramPoint; - CallExitEnd() {} + CallExitEnd() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == CallExitEndKind; } @@ -672,7 +695,7 @@ public: private: friend class ProgramPoint; - LoopExit() {} + LoopExit() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == LoopExitKind; } @@ -691,7 +714,7 @@ public: private: friend class ProgramPoint; - EpsilonPoint() {} + EpsilonPoint() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == EpsilonKind; } |