Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===------------------------ MapLattice.h ----------------------*- 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 a parameterized lattice that maps keys to individual

//  lattice elements (of the parameter lattice type). A typical usage is lifting

//  a particular lattice to all variables in a lexical scope.

//

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

#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H

#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H

#include <ostream>

#include <string>

#include <utility>

#include "DataflowAnalysis.h"

#include "clang/AST/Decl.h"

#include "clang/Analysis/FlowSensitive/DataflowLattice.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/StringRef.h"

namespace clang {

namespace dataflow {

/// A lattice that maps keys to individual lattice elements. When instantiated

/// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is

/// itself a bounded semi-lattice, so long as the user limits themselves to a

/// finite number of keys. In that case, `top` is (implicitly), the map

/// containing all valid keys mapped to `top` of `ElementLattice`.

///

/// Requirements on `ElementLattice`:

/// * Provides standard declarations of a bounded semi-lattice.

template <typename Key, typename ElementLattice> class MapLattice {

  using Container = llvm::DenseMap<Key, ElementLattice>;

  Container C;

public:

  using key_type = Key;

  using mapped_type = ElementLattice;

  using value_type = typename Container::value_type;

  using iterator = typename Container::iterator;

  using const_iterator = typename Container::const_iterator;

  MapLattice() = default;

  explicit MapLattice(Container C) { C = std::move(C); }

  // The `bottom` element is the empty map.

  static MapLattice bottom() { return MapLattice(); }

  std::pair<iterator, bool>

  insert(const std::pair<const key_type, mapped_type> &P) {

    return C.insert(P);

  }

  std::pair<iterator, bool> insert(std::pair<const key_type, mapped_type> &&P) {

    return C.insert(std::move(P));

  }

  unsigned size() const { return C.size(); }

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

  iterator begin() { return C.begin(); }

  iterator end() { return C.end(); }

  const_iterator begin() const { return C.begin(); }

  const_iterator end() const { return C.end(); }

  // Equality is direct equality of underlying map entries. One implication of

  // this definition is that a map with (only) keys that map to bottom is not

  // equal to the empty map.

  friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) {

    return LHS.C == RHS.C;

  }

  friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) {

    return !(LHS == RHS);

  }

  bool contains(const key_type &K) const { return C.find(K) != C.end(); }

  iterator find(const key_type &K) { return C.find(K); }

  const_iterator find(const key_type &K) const { return C.find(K); }

  mapped_type &operator[](const key_type &K) { return C[K]; }

  /// If an entry exists in one map but not the other, the missing entry is

  /// treated as implicitly mapping to `bottom`. So, the joined map contains the

  /// entry as it was in the source map.

  LatticeJoinEffect join(const MapLattice &Other) {

    LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged;

    for (const auto &O : Other.C) {

      auto It = C.find(O.first);

      if (It == C.end()) {

        C.insert(O);

        Effect = LatticeJoinEffect::Changed;

      } else if (It->second.join(O.second) == LatticeJoinEffect::Changed)

        Effect = LatticeJoinEffect::Changed;

    }

    return Effect;

  }

};

/// Convenience alias that captures the common use of map lattices to model

/// in-scope variables.

template <typename ElementLattice>

using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>;

template <typename Key, typename ElementLattice>

std::ostream &

operator<<(std::ostream &Os,

           const clang::dataflow::MapLattice<Key, ElementLattice> &M) {

  std::string Separator;

  Os << "{";

  for (const auto &E : M) {

    Os << std::exchange(Separator, ", ") << E.first << " => " << E.second;

  }

  Os << "}";

  return Os;

}

template <typename ElementLattice>

std::ostream &

operator<<(std::ostream &Os,

           const clang::dataflow::VarMapLattice<ElementLattice> &M) {

  std::string Separator;

  Os << "{";

  for (const auto &E : M) {

    Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => "

       << E.second;

  }

  Os << "}";

  return Os;

}

} // namespace dataflow

} // namespace clang

#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H