Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===------------------------ MapLattice.h ----------------------*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. //  This file defines a parameterized lattice that maps keys to individual
  10. //  lattice elements (of the parameter lattice type). A typical usage is lifting
  11. //  a particular lattice to all variables in a lexical scope.
  12. //
  13. //===----------------------------------------------------------------------===//
  14.  
  15. #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
  16. #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
  17.  
  18. #include <ostream>
  19. #include <string>
  20. #include <utility>
  21.  
  22. #include "DataflowAnalysis.h"
  23. #include "clang/AST/Decl.h"
  24. #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
  25. #include "llvm/ADT/DenseMap.h"
  26. #include "llvm/ADT/StringRef.h"
  27.  
  28. namespace clang {
  29. namespace dataflow {
  30.  
  31. /// A lattice that maps keys to individual lattice elements. When instantiated
  32. /// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is
  33. /// itself a bounded semi-lattice, so long as the user limits themselves to a
  34. /// finite number of keys. In that case, `top` is (implicitly), the map
  35. /// containing all valid keys mapped to `top` of `ElementLattice`.
  36. ///
  37. /// Requirements on `ElementLattice`:
  38. /// * Provides standard declarations of a bounded semi-lattice.
  39. template <typename Key, typename ElementLattice> class MapLattice {
  40.   using Container = llvm::DenseMap<Key, ElementLattice>;
  41.   Container C;
  42.  
  43. public:
  44.   using key_type = Key;
  45.   using mapped_type = ElementLattice;
  46.   using value_type = typename Container::value_type;
  47.   using iterator = typename Container::iterator;
  48.   using const_iterator = typename Container::const_iterator;
  49.  
  50.   MapLattice() = default;
  51.  
  52.   explicit MapLattice(Container C) { C = std::move(C); }
  53.  
  54.   // The `bottom` element is the empty map.
  55.   static MapLattice bottom() { return MapLattice(); }
  56.  
  57.   std::pair<iterator, bool>
  58.   insert(const std::pair<const key_type, mapped_type> &P) {
  59.     return C.insert(P);
  60.   }
  61.  
  62.   std::pair<iterator, bool> insert(std::pair<const key_type, mapped_type> &&P) {
  63.     return C.insert(std::move(P));
  64.   }
  65.  
  66.   unsigned size() const { return C.size(); }
  67.   bool empty() const { return C.empty(); }
  68.  
  69.   iterator begin() { return C.begin(); }
  70.   iterator end() { return C.end(); }
  71.   const_iterator begin() const { return C.begin(); }
  72.   const_iterator end() const { return C.end(); }
  73.  
  74.   // Equality is direct equality of underlying map entries. One implication of
  75.   // this definition is that a map with (only) keys that map to bottom is not
  76.   // equal to the empty map.
  77.   friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) {
  78.     return LHS.C == RHS.C;
  79.   }
  80.  
  81.   friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) {
  82.     return !(LHS == RHS);
  83.   }
  84.  
  85.   bool contains(const key_type &K) const { return C.find(K) != C.end(); }
  86.  
  87.   iterator find(const key_type &K) { return C.find(K); }
  88.   const_iterator find(const key_type &K) const { return C.find(K); }
  89.  
  90.   mapped_type &operator[](const key_type &K) { return C[K]; }
  91.  
  92.   /// If an entry exists in one map but not the other, the missing entry is
  93.   /// treated as implicitly mapping to `bottom`. So, the joined map contains the
  94.   /// entry as it was in the source map.
  95.   LatticeJoinEffect join(const MapLattice &Other) {
  96.     LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged;
  97.     for (const auto &O : Other.C) {
  98.       auto It = C.find(O.first);
  99.       if (It == C.end()) {
  100.         C.insert(O);
  101.         Effect = LatticeJoinEffect::Changed;
  102.       } else if (It->second.join(O.second) == LatticeJoinEffect::Changed)
  103.         Effect = LatticeJoinEffect::Changed;
  104.     }
  105.     return Effect;
  106.   }
  107. };
  108.  
  109. /// Convenience alias that captures the common use of map lattices to model
  110. /// in-scope variables.
  111. template <typename ElementLattice>
  112. using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>;
  113.  
  114. template <typename Key, typename ElementLattice>
  115. std::ostream &
  116. operator<<(std::ostream &Os,
  117.            const clang::dataflow::MapLattice<Key, ElementLattice> &M) {
  118.   std::string Separator;
  119.   Os << "{";
  120.   for (const auto &E : M) {
  121.     Os << std::exchange(Separator, ", ") << E.first << " => " << E.second;
  122.   }
  123.   Os << "}";
  124.   return Os;
  125. }
  126.  
  127. template <typename ElementLattice>
  128. std::ostream &
  129. operator<<(std::ostream &Os,
  130.            const clang::dataflow::VarMapLattice<ElementLattice> &M) {
  131.   std::string Separator;
  132.   Os << "{";
  133.   for (const auto &E : M) {
  134.     Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => "
  135.        << E.second;
  136.   }
  137.   Os << "}";
  138.   return Os;
  139. }
  140. } // namespace dataflow
  141. } // namespace clang
  142.  
  143. #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
  144.