Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- CFG.h - Classes for representing and building CFGs -------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

//  This file defines the CFG and CFGBuilder classes for representing and

//  building Control-Flow Graphs (CFGs) from ASTs.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_CFG_H

#define LLVM_CLANG_ANALYSIS_CFG_H

#include "clang/Analysis/Support/BumpVector.h"

#include "clang/Analysis/ConstructionContext.h"

#include "clang/AST/ExprCXX.h"

#include "clang/AST/ExprObjC.h"

#include "clang/Basic/LLVM.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/GraphTraits.h"

#include "llvm/ADT/PointerIntPair.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Support/Allocator.h"

#include "llvm/Support/raw_ostream.h"

#include <bitset>

#include <cassert>

#include <cstddef>

#include <iterator>

#include <memory>

#include <optional>

#include <vector>

namespace clang {

class ASTContext;

class BinaryOperator;

class CFG;

class CXXBaseSpecifier;

class CXXBindTemporaryExpr;

class CXXCtorInitializer;

class CXXDeleteExpr;

class CXXDestructorDecl;

class CXXNewExpr;

class CXXRecordDecl;

class Decl;

class FieldDecl;

class LangOptions;

class VarDecl;

/// Represents a top-level expression in a basic block.

class CFGElement {

public:

  enum Kind {

    // main kind

    Initializer,

    ScopeBegin,

    ScopeEnd,

    NewAllocator,

    LifetimeEnds,

    LoopExit,

    // stmt kind

    Statement,

    Constructor,

    CXXRecordTypedCall,

    STMT_BEGIN = Statement,

    STMT_END = CXXRecordTypedCall,

    // dtor kind

    AutomaticObjectDtor,

    DeleteDtor,

    BaseDtor,

    MemberDtor,

    TemporaryDtor,

    DTOR_BEGIN = AutomaticObjectDtor,

    DTOR_END = TemporaryDtor

  };

protected:

  // The int bits are used to mark the kind.

  llvm::PointerIntPair<void *, 2> Data1;

  llvm::PointerIntPair<void *, 2> Data2;

  CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr)

      : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),

        Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {

    assert(getKind() == kind);

  }

  CFGElement() = default;

public:

  /// Convert to the specified CFGElement type, asserting that this

  /// CFGElement is of the desired type.

  template<typename T>

  T castAs() const {

    assert(T::isKind(*this));

    T t;

    CFGElement& e = t;

    e = *this;

    return t;

  }

  /// Convert to the specified CFGElement type, returning std::nullopt if this

  /// CFGElement is not of the desired type.

  template <typename T> std::optional<T> getAs() const {

    if (!T::isKind(*this))

      return std::nullopt;

    T t;

    CFGElement& e = t;

    e = *this;

    return t;

  }

  Kind getKind() const {

    unsigned x = Data2.getInt();

    x <<= 2;

    x |= Data1.getInt();

    return (Kind) x;

  }

  void dumpToStream(llvm::raw_ostream &OS) const;

  void dump() const {

    dumpToStream(llvm::errs());

  }

};

class CFGStmt : public CFGElement {

public:

  explicit CFGStmt(const Stmt *S, Kind K = Statement) : CFGElement(K, S) {

    assert(isKind(*this));

  }

  const Stmt *getStmt() const {

    return static_cast<const Stmt *>(Data1.getPointer());

  }

private:

  friend class CFGElement;

  static bool isKind(const CFGElement &E) {

    return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END;

  }

protected:

  CFGStmt() = default;

};

/// 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(const 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;

  }

};

/// 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(const Expr *E) {

    assert(isa<CallExpr>(E) || isa<ObjCMessageExpr>(E));

    // There is no such thing as reference-type expression. If the function

    // returns a reference, it'll return the respective lvalue or xvalue

    // instead, and we're only interested in objects.

    return !E->isGLValue() &&

           E->getType().getCanonicalType()->getAsCXXRecordDecl();

  }

  explicit CFGCXXRecordTypedCall(const Expr *E, const ConstructionContext *C)

      : CFGStmt(E, CXXRecordTypedCall) {

    assert(isCXXRecordTypedCall(E));

    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) ||

                 isa<ArgumentConstructionContext>(C) ||

                 isa<LambdaCaptureConstructionContext>(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() == CXXRecordTypedCall;

  }

};

/// Represents C++ base or member initializer from constructor's initialization

/// list.

class CFGInitializer : public CFGElement {

public:

  explicit CFGInitializer(const CXXCtorInitializer *initializer)

      : CFGElement(Initializer, initializer) {}

  CXXCtorInitializer* getInitializer() const {

    return static_cast<CXXCtorInitializer*>(Data1.getPointer());

  }

private:

  friend class CFGElement;

  CFGInitializer() = default;

  static bool isKind(const CFGElement &E) {

    return E.getKind() == Initializer;

  }

};

/// Represents C++ allocator call.

class CFGNewAllocator : public CFGElement {

public:

  explicit CFGNewAllocator(const CXXNewExpr *S)

    : CFGElement(NewAllocator, S) {}

  // Get the new expression.

  const CXXNewExpr *getAllocatorExpr() const {

    return static_cast<CXXNewExpr *>(Data1.getPointer());

  }

private:

  friend class CFGElement;

  CFGNewAllocator() = default;

  static bool isKind(const CFGElement &elem) {

    return elem.getKind() == NewAllocator;

  }

};

/// Represents the point where a loop ends.

/// This element is only produced when building the CFG for the static

/// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.

///

/// Note: a loop exit element can be reached even when the loop body was never

/// entered.

class CFGLoopExit : public CFGElement {

public:

  explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {}

  const Stmt *getLoopStmt() const {

    return static_cast<Stmt *>(Data1.getPointer());

  }

private:

  friend class CFGElement;

  CFGLoopExit() = default;

  static bool isKind(const CFGElement &elem) {

    return elem.getKind() == LoopExit;

  }

};

/// Represents the point where the lifetime of an automatic object ends

class CFGLifetimeEnds : public CFGElement {

public:

  explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt)

      : CFGElement(LifetimeEnds, var, stmt) {}

  const VarDecl *getVarDecl() const {

    return static_cast<VarDecl *>(Data1.getPointer());

  }

  const Stmt *getTriggerStmt() const {

    return static_cast<Stmt *>(Data2.getPointer());

  }

private:

  friend class CFGElement;

  CFGLifetimeEnds() = default;

  static bool isKind(const CFGElement &elem) {

    return elem.getKind() == LifetimeEnds;

  }

};

/// 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;

  }

};

/// Represents C++ object destructor implicitly generated by compiler on various

/// occasions.

class CFGImplicitDtor : public CFGElement {

protected:

  CFGImplicitDtor() = default;

  CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr)

    : CFGElement(kind, data1, data2) {

    assert(kind >= DTOR_BEGIN && kind <= DTOR_END);

  }

public:

  const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const;

  bool isNoReturn(ASTContext &astContext) const;

private:

  friend class CFGElement;

  static bool isKind(const CFGElement &E) {

    Kind kind = E.getKind();

    return kind >= DTOR_BEGIN && kind <= DTOR_END;

  }

};

/// Represents C++ object destructor implicitly generated for automatic object

/// or temporary bound to const reference at the point of leaving its local

/// scope.

class CFGAutomaticObjDtor: public CFGImplicitDtor {

public:

  CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)

      : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {}

  const VarDecl *getVarDecl() const {

    return static_cast<VarDecl*>(Data1.getPointer());

  }

  // Get statement end of which triggered the destructor call.

  const Stmt *getTriggerStmt() const {

    return static_cast<Stmt*>(Data2.getPointer());

  }

private:

  friend class CFGElement;

  CFGAutomaticObjDtor() = default;

  static bool isKind(const CFGElement &elem) {

    return elem.getKind() == AutomaticObjectDtor;

  }

};

/// Represents C++ object destructor generated from a call to delete.

class CFGDeleteDtor : public CFGImplicitDtor {

public:

  CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE)

      : CFGImplicitDtor(DeleteDtor, RD, DE) {}

  const CXXRecordDecl *getCXXRecordDecl() const {

    return static_cast<CXXRecordDecl*>(Data1.getPointer());

  }

  // Get Delete expression which triggered the destructor call.

  const CXXDeleteExpr *getDeleteExpr() const {

    return static_cast<CXXDeleteExpr *>(Data2.getPointer());

  }

private:

  friend class CFGElement;

  CFGDeleteDtor() = default;

  static bool isKind(const CFGElement &elem) {

    return elem.getKind() == DeleteDtor;

  }

};

/// Represents C++ object destructor implicitly generated for base object in

/// destructor.

class CFGBaseDtor : public CFGImplicitDtor {

public:

  CFGBaseDtor(const CXXBaseSpecifier *base)

      : CFGImplicitDtor(BaseDtor, base) {}

  const CXXBaseSpecifier *getBaseSpecifier() const {

    return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());

  }

private:

  friend class CFGElement;

  CFGBaseDtor() = default;

  static bool isKind(const CFGElement &E) {

    return E.getKind() == BaseDtor;

  }

};

/// Represents C++ object destructor implicitly generated for member object in

/// destructor.

class CFGMemberDtor : public CFGImplicitDtor {

public:

  CFGMemberDtor(const FieldDecl *field)

      : CFGImplicitDtor(MemberDtor, field, nullptr) {}

  const FieldDecl *getFieldDecl() const {

    return static_cast<const FieldDecl*>(Data1.getPointer());

  }

private:

  friend class CFGElement;

  CFGMemberDtor() = default;

  static bool isKind(const CFGElement &E) {

    return E.getKind() == MemberDtor;

  }

};

/// Represents C++ object destructor implicitly generated at the end of full

/// expression for temporary object.

class CFGTemporaryDtor : public CFGImplicitDtor {

public:

  CFGTemporaryDtor(const CXXBindTemporaryExpr *expr)

      : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {}

  const CXXBindTemporaryExpr *getBindTemporaryExpr() const {

    return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer());

  }

private:

  friend class CFGElement;

  CFGTemporaryDtor() = default;

  static bool isKind(const CFGElement &E) {

    return E.getKind() == TemporaryDtor;

  }

};

/// Represents CFGBlock terminator statement.

///

class CFGTerminator {

public:

  enum Kind {

    /// A branch that corresponds to a statement in the code,

    /// such as an if-statement.

    StmtBranch,

    /// A branch in control flow of destructors of temporaries. In this case

    /// terminator statement is the same statement that branches control flow

    /// in evaluation of matching full expression.

    TemporaryDtorsBranch,

    /// A shortcut around virtual base initializers. It gets taken when

    /// virtual base classes have already been initialized by the constructor

    /// of the most derived class while we're in the base class.

    VirtualBaseBranch,

    /// Number of different kinds, for assertions. We subtract 1 so that

    /// to keep receiving compiler warnings when we don't cover all enum values

    /// in a switch.

    NumKindsMinusOne = VirtualBaseBranch

  };

private:

  static constexpr int KindBits = 2;

  static_assert((1 << KindBits) > NumKindsMinusOne,

                "Not enough room for kind!");

  llvm::PointerIntPair<Stmt *, KindBits> Data;

public:

  CFGTerminator() { assert(!isValid()); }

  CFGTerminator(Stmt *S, Kind K = StmtBranch) : Data(S, K) {}

  bool isValid() const { return Data.getOpaqueValue() != nullptr; }

  Stmt *getStmt() { return Data.getPointer(); }

  const Stmt *getStmt() const { return Data.getPointer(); }

  Kind getKind() const { return static_cast<Kind>(Data.getInt()); }

  bool isStmtBranch() const {

    return getKind() == StmtBranch;

  }

  bool isTemporaryDtorsBranch() const {

    return getKind() == TemporaryDtorsBranch;

  }

  bool isVirtualBaseBranch() const {

    return getKind() == VirtualBaseBranch;

  }

};

/// Represents a single basic block in a source-level CFG.

///  It consists of:

///

///  (1) A set of statements/expressions (which may contain subexpressions).

///  (2) A "terminator" statement (not in the set of statements).

///  (3) A list of successors and predecessors.

///

/// Terminator: The terminator represents the type of control-flow that occurs

/// at the end of the basic block.  The terminator is a Stmt* referring to an

/// AST node that has control-flow: if-statements, breaks, loops, etc.

/// If the control-flow is conditional, the condition expression will appear

/// within the set of statements in the block (usually the last statement).

///

/// Predecessors: the order in the set of predecessors is arbitrary.

///

/// Successors: the order in the set of successors is NOT arbitrary.  We

///  currently have the following orderings based on the terminator:

///

///     Terminator     |   Successor Ordering

///  ------------------|------------------------------------

///       if           |  Then Block;  Else Block

///     ? operator     |  LHS expression;  RHS expression

///     logical and/or |  expression that consumes the op, RHS

///     vbase inits    |  already handled by the most derived class; not yet

///

/// But note that any of that may be NULL in case of optimized-out edges.

class CFGBlock {

  class ElementList {

    using ImplTy = BumpVector<CFGElement>;

    ImplTy Impl;

  public:

    ElementList(BumpVectorContext &C) : Impl(C, 4) {}

    using iterator = std::reverse_iterator<ImplTy::iterator>;

    using const_iterator = std::reverse_iterator<ImplTy::const_iterator>;

    using reverse_iterator = ImplTy::iterator;

    using const_reverse_iterator = ImplTy::const_iterator;

    using const_reference = ImplTy::const_reference;

    void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }

    reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,

        BumpVectorContext &C) {

      return Impl.insert(I, Cnt, E, C);

    }

    const_reference front() const { return Impl.back(); }

    const_reference back() const { return Impl.front(); }

    iterator begin() { return Impl.rbegin(); }

    iterator end() { return Impl.rend(); }

    const_iterator begin() const { return Impl.rbegin(); }

    const_iterator end() const { return Impl.rend(); }

    reverse_iterator rbegin() { return Impl.begin(); }

    reverse_iterator rend() { return Impl.end(); }

    const_reverse_iterator rbegin() const { return Impl.begin(); }

    const_reverse_iterator rend() const { return Impl.end(); }

    CFGElement operator[](size_t i) const  {

      assert(i < Impl.size());

      return Impl[Impl.size() - 1 - i];

    }

    size_t size() const { return Impl.size(); }

    bool empty() const { return Impl.empty(); }

  };

  /// A convenience class for comparing CFGElements, since methods of CFGBlock

  /// like operator[] return CFGElements by value. This is practically a wrapper

  /// around a (CFGBlock, Index) pair.

  template <bool IsConst> class ElementRefImpl {

    template <bool IsOtherConst> friend class ElementRefImpl;

    using CFGBlockPtr =

        std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>;

    using CFGElementPtr =

        std::conditional_t<IsConst, const CFGElement *, CFGElement *>;

  protected:

    CFGBlockPtr Parent;

    size_t Index;

  public:

    ElementRefImpl(CFGBlockPtr Parent, size_t Index)

        : Parent(Parent), Index(Index) {}

    template <bool IsOtherConst>

    ElementRefImpl(ElementRefImpl<IsOtherConst> Other)

        : ElementRefImpl(Other.Parent, Other.Index) {}

    size_t getIndexInBlock() const { return Index; }

    CFGBlockPtr getParent() { return Parent; }

    CFGBlockPtr getParent() const { return Parent; }

    bool operator<(ElementRefImpl Other) const {

      return std::make_pair(Parent, Index) <

             std::make_pair(Other.Parent, Other.Index);

    }

    bool operator==(ElementRefImpl Other) const {

      return Parent == Other.Parent && Index == Other.Index;

    }

    bool operator!=(ElementRefImpl Other) const { return !(*this == Other); }

    CFGElement operator*() const { return (*Parent)[Index]; }

    CFGElementPtr operator->() const { return &*(Parent->begin() + Index); }

    void dumpToStream(llvm::raw_ostream &OS) const {

      OS << getIndexInBlock() + 1 << ": ";

      (*this)->dumpToStream(OS);

    }

    void dump() const {

      dumpToStream(llvm::errs());

    }

  };

  template <bool IsReverse, bool IsConst> class ElementRefIterator {

    template <bool IsOtherReverse, bool IsOtherConst>

    friend class ElementRefIterator;

    using CFGBlockRef =

        std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>;

    using UnderlayingIteratorTy = std::conditional_t<

        IsConst,

        std::conditional_t<IsReverse, ElementList::const_reverse_iterator,

                           ElementList::const_iterator>,

        std::conditional_t<IsReverse, ElementList::reverse_iterator,

                           ElementList::iterator>>;

    using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>;

    using ElementRef = typename CFGBlock::ElementRefImpl<IsConst>;

  public:

    using difference_type = typename IteratorTraits::difference_type;

    using value_type = ElementRef;

    using pointer = ElementRef *;

    using iterator_category = typename IteratorTraits::iterator_category;

  private:

    CFGBlockRef Parent;

    UnderlayingIteratorTy Pos;

  public:

    ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos)

        : Parent(Parent), Pos(Pos) {}

    template <bool IsOtherConst>

    ElementRefIterator(ElementRefIterator<false, IsOtherConst> E)

        : ElementRefIterator(E.Parent, E.Pos.base()) {}

    template <bool IsOtherConst>

    ElementRefIterator(ElementRefIterator<true, IsOtherConst> E)

        : ElementRefIterator(E.Parent, std::make_reverse_iterator(E.Pos)) {}

    bool operator<(ElementRefIterator Other) const {

      assert(Parent == Other.Parent);

      return Pos < Other.Pos;

    }

    bool operator==(ElementRefIterator Other) const {

      return Parent == Other.Parent && Pos == Other.Pos;

    }

    bool operator!=(ElementRefIterator Other) const {

      return !(*this == Other);

    }

  private:

    template <bool IsOtherConst>

    static size_t

    getIndexInBlock(CFGBlock::ElementRefIterator<true, IsOtherConst> E) {

      return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1;

    }

    template <bool IsOtherConst>

    static size_t

    getIndexInBlock(CFGBlock::ElementRefIterator<false, IsOtherConst> E) {

      return E.Pos - E.Parent->begin();

    }

  public:

    value_type operator*() { return {Parent, getIndexInBlock(*this)}; }

    difference_type operator-(ElementRefIterator Other) const {

      return Pos - Other.Pos;

    }

    ElementRefIterator operator++() {

      ++this->Pos;

      return *this;

    }

    ElementRefIterator operator++(int) {

      ElementRefIterator Ret = *this;

      ++*this;

      return Ret;

    }

    ElementRefIterator operator+(size_t count) {

      this->Pos += count;

      return *this;

    }

    ElementRefIterator operator-(size_t count) {

      this->Pos -= count;

      return *this;

    }

  };

public:

  /// The set of statements in the basic block.

  ElementList Elements;

  /// An (optional) label that prefixes the executable statements in the block.

  /// When this variable is non-NULL, it is either an instance of LabelStmt,

  /// SwitchCase or CXXCatchStmt.

  Stmt *Label = nullptr;

  /// The terminator for a basic block that indicates the type of control-flow

  /// that occurs between a block and its successors.

  CFGTerminator Terminator;

  /// Some blocks are used to represent the "loop edge" to the start of a loop

  /// from within the loop body. This Stmt* will be refer to the loop statement

  /// for such blocks (and be null otherwise).

  const Stmt *LoopTarget = nullptr;

  /// A numerical ID assigned to a CFGBlock during construction of the CFG.

  unsigned BlockID;