text: /**
   * Copyright (c) Facebook, Inc. and its affiliates.
   *
   * This source code is licensed under the MIT license found in the
   * LICENSE file in the root directory of this source tree.
   */
  
  #include "PointsToSemantics.h"
  
  #include <algorithm>
  #include <cstdint>
  #include <deque>
  #include <iomanip>
  #include <iterator>
  #include <limits>
  #include <memory>
  #include <ostream>
  #include <sstream>
  #include <tuple>
  #include <unordered_map>
  #include <unordered_set>
  #include <utility>
  
  #include <boost/container/flat_set.hpp>
  #include <boost/functional/hash.hpp>
  #include <boost/functional/hash_fwd.hpp>
  #include <boost/optional.hpp>
  
  #include "ControlFlow.h"
  #include "Debug.h"
  #include "DexAccess.h"
  #include "DexClass.h"
  #include "DexUtil.h"
  #include "IRCode.h"
  #include "IRInstruction.h"
  #include "IROpcode.h"
  #include "MonotonicFixpointIterator.h"
  #include "PatriciaTreeMapAbstractEnvironment.h"
  #include "PatriciaTreeSetAbstractDomain.h"
  #include "PointsToSemanticsUtils.h"
  #include "RedexContext.h"
  #include "Trace.h"
  #include "Walkers.h"
  
  using namespace sparta;
  
  s_expr PointsToVariable::to_s_expr() const {
    return s_expr({s_expr("V"), s_expr(m_id)});
  }
  
  boost::optional<PointsToVariable> PointsToVariable::from_s_expr(
      const s_expr& e) {
    int32_t id;
    if (!s_patn({s_patn("V"), s_patn(&id)}).match_with(e)) {
      return {};
    }
    return {PointsToVariable(id)};
  }
  
  size_t hash_value(const PointsToVariable& v) {
    boost::hash<int32_t> hasher;
    return hasher(v.m_id);
  }
  
  bool operator==(const PointsToVariable& v, const PointsToVariable& w) {
    return v.m_id == w.m_id;
  }
  
  bool operator<(const PointsToVariable& v, const PointsToVariable& w) {
    return v.m_id < w.m_id;
  }
  
  std::ostream& operator<<(std::ostream& o, const PointsToVariable& v) {
    if (v.m_id == PointsToVariable::null_var_id()) {
      o << "NULL";
    } else if (v.m_id == PointsToVariable::this_var_id()) {
      o << "THIS";
    } else {
      o << "V" << v.m_id;
    }
    return o;
  }
  
  namespace pts_impl {
  
  #define OP_STRING_TABLE                 \
    {                                     \
      OP_STRING(PTS_CONST_STRING),        \
      OP_STRING(PTS_CONST_CLASS),         \
      OP_STRING(PTS_NEW_OBJECT),          \
      OP_STRING(PTS_GET_CLASS),           \
      OP_STRING(PTS_CHECK_CAST),          \
      OP_STRING(PTS_GET_EXCEPTION),       \
      OP_STRING(PTS_LOAD_PARAM),          \
      OP_STRING(PTS_RETURN),              \
      OP_STRING(PTS_DISJUNCTION),         \
      OP_STRING(PTS_IGET),                \
      OP_STRING(PTS_SGET),                \
      OP_STRING(PTS_IPUT),                \
      OP_STRING(PTS_SPUT),                \
      OP_STRING(PTS_IGET_SPECIAL),        \
      OP_STRING(PTS_IPUT_SPECIAL),        \
      OP_STRING(PTS_INVOKE_VIRTUAL),      \
      OP_STRING(PTS_INVOKE_SUPER),        \
      OP_STRING(PTS_INVOKE_DIRECT),       \
      OP_STRING(PTS_INVOKE_INTERFACE),    \
      OP_STRING(PTS_INVOKE_STATIC),       \
    }                                     \
  
  #define OP_STRING(X) {X, #X}
  std::unordered_map<PointsToOperationKind, std::string, std::hash<int>>
      op_to_string_table = OP_STRING_TABLE;
  #undef OP_STRING
  
  #define OP_STRING(X) {#X, X}
  std::unordered_map<std::string, PointsToOperationKind> string_to_op_table =
      OP_STRING_TABLE;
  #undef OP_STRING
  
  s_expr op_kind_to_s_expr(PointsToOperationKind kind) {
    auto it = op_to_string_table.find(kind);
    always_assert(it != op_to_string_table.end());
    return s_expr(it->second);
  }
  
  boost::optional<PointsToOperationKind> string_to_op_kind(
      const std::string& str) {
    auto it = string_to_op_table.find(str);
    if (it == string_to_op_table.end()) {
      return {};
    }
    return boost::optional<PointsToOperationKind>(it->second);
  }
  
  s_expr special_edge_to_s_expr(SpecialPointsToEdge edge) {
    switch (edge) {
    case PTS_ARRAY_ELEMENT: {
      return s_expr("PTS_ARRAY_ELEMENT");
    }
    }
  }
  
  boost::optional<SpecialPointsToEdge> string_to_special_edge(
      const std::string& str) {
    if (str == "PTS_ARRAY_ELEMENT") {
      return {PTS_ARRAY_ELEMENT};
    }
    return {};
  }
  
  s_expr dex_method_to_s_expr(DexMethodRef* dex_method) {
    DexProto* proto = dex_method->get_proto();
    std::vector<s_expr> signature;
    for (DexType* arg : proto->get_args()->get_type_list()) {
      signature.push_back(s_expr(arg->get_name()->str()));
    }
    return s_expr({s_expr(dex_method->get_class()->get_name()->str()),
                   s_expr(dex_method->get_name()->str()),
                   s_expr(proto->get_rtype()->get_name()->str()),
                   s_expr(signature)});
  }
  
  boost::optional<DexMethodRef*> s_expr_to_dex_method(const s_expr& e) {
    std::string type_str;
    std::string name_str;
    std::string rtype_str;
    s_expr signature;
    if (!s_patn({s_patn(&type_str),
                 s_patn(&name_str),
                 s_patn(&rtype_str),
                 s_patn({}, signature)})
             .match_with(e)) {
      return {};
    }
    std::deque<DexType*> types;
    for (size_t arg = 0; arg < signature.size(); ++arg) {
      if (!signature[arg].is_string()) {
        return {};
      }
      types.push_back(DexType::make_type(signature[arg].get_string().c_str()));
    }
    return {DexMethod::make_method(
        DexType::make_type(type_str.c_str()),
        DexString::make_string(name_str),
        DexProto::make_proto(DexType::make_type(rtype_str.c_str()),
                             DexTypeList::make_type_list(std::move(types))))};
  }
  
  } // namespace pts_impl
  
  s_expr PointsToOperation::to_s_expr() const {
    using namespace pts_impl;
    switch (kind) {
    case PTS_CONST_STRING: {
      return s_expr({op_kind_to_s_expr(kind), s_expr(dex_string->str())});
    }
    case PTS_CONST_CLASS:
    case PTS_NEW_OBJECT:
    case PTS_CHECK_CAST: {
      return s_expr(
          {op_kind_to_s_expr(kind), s_expr(dex_type->get_name()->str())});
    }
    case PTS_GET_EXCEPTION:
    case PTS_GET_CLASS:
    case PTS_RETURN:
    case PTS_DISJUNCTION: {
      return s_expr({op_kind_to_s_expr(kind)});
    }
    case PTS_LOAD_PARAM: {
      return s_expr(
          {op_kind_to_s_expr(kind), s_expr(static_cast<int32_t>(parameter))});
    }
    case PTS_IGET:
    case PTS_SGET:
    case PTS_IPUT:
    case PTS_SPUT: {
      return s_expr({op_kind_to_s_expr(kind),
                     s_expr(dex_field->get_class()->get_name()->str()),
                     s_expr(dex_field->get_name()->str()),
                     s_expr(dex_field->get_type()->get_name()->str())});
    }
    case PTS_IGET_SPECIAL:
    case PTS_IPUT_SPECIAL: {
      return s_expr(
          {op_kind_to_s_expr(kind), special_edge_to_s_expr(special_edge)});
    }
    case PTS_INVOKE_VIRTUAL:
    case PTS_INVOKE_SUPER:
    case PTS_INVOKE_DIRECT:
    case PTS_INVOKE_INTERFACE:
    case PTS_INVOKE_STATIC: {
      return s_expr({op_kind_to_s_expr(kind), dex_method_to_s_expr(dex_method)});
    }
    }
  }
  
  boost::optional<PointsToOperation> PointsToOperation::from_s_expr(
      const s_expr& e) {
    using namespace pts_impl;
    std::string op_kind_str;
    s_expr args;
    if (!s_patn({s_patn(&op_kind_str)}, args).match_with(e)) {
      return {};
    }
    auto op_kind_opt = string_to_op_kind(op_kind_str);
    if (!op_kind_opt) {
      return {};
    }
    PointsToOperationKind op_kind = *op_kind_opt;
    switch (op_kind) {
    case PTS_CONST_STRING: {
      std::string dex_string_str;
      if (!s_patn({s_patn(&dex_string_str)}).match_with(args)) {
        return {};
      }
      return {PointsToOperation(op_kind, DexString::make_string(dex_string_str))};
    }
    case PTS_CONST_CLASS:
    case PTS_NEW_OBJECT:
    case PTS_CHECK_CAST: {
      std::string dex_type_str;
      if (!s_patn({s_patn(&dex_type_str)}).match_with(args)) {
        return {};
      }
      return {
          PointsToOperation(op_kind, DexType::make_type(dex_type_str.c_str()))};
    }
    case PTS_GET_EXCEPTION:
    case PTS_GET_CLASS:
    case PTS_RETURN:
    case PTS_DISJUNCTION: {
      return {PointsToOperation(op_kind)};
    }
    case PTS_LOAD_PARAM: {
      int32_t parameter;
      if (!s_patn({s_patn(&parameter)}).match_with(args)) {
        return {};
      }
      return {PointsToOperation(op_kind, static_cast<size_t>(parameter))};
    }
    case PTS_IGET:
    case PTS_SGET:
    case PTS_IPUT:
    case PTS_SPUT: {
      std::string container_str;
      std::string name_str;
      std::string type_str;
      if (!s_patn({s_patn(&container_str), s_patn(&name_str), s_patn(&type_str)})
               .match_with(args)) {
        return {};
      }
      return {PointsToOperation(
          op_kind,
          DexField::make_field(DexType::make_type(container_str.c_str()),
                               DexString::make_string(name_str),
                               DexType::make_type(type_str.c_str())))};
    }
    case PTS_IGET_SPECIAL:
    case PTS_IPUT_SPECIAL: {
      std::string edge_str;
      if (!s_patn({s_patn(&edge_str)}).match_with(args)) {
        return {};
      }
      auto edge = string_to_special_edge(edge_str);
      if (!edge) {
        return {};
      }
      return {PointsToOperation(op_kind, *edge)};
    }
    case PTS_INVOKE_VIRTUAL:
    case PTS_INVOKE_SUPER:
    case PTS_INVOKE_DIRECT:
    case PTS_INVOKE_INTERFACE:
    case PTS_INVOKE_STATIC: {
      s_expr dex_method_expr;
      if (!s_patn({s_patn(dex_method_expr)}).match_with(args)) {
        return {};
      }
      auto dex_method_opt = s_expr_to_dex_method(dex_method_expr);
      if (!dex_method_opt) {
        return {};
      }
      return {PointsToOperation(op_kind, *dex_method_opt)};
    }
    }
  }
  
  namespace pts_impl {
  
  // A wrapper for a set of variables. We use this structure for the generation of
  // disjunctions.
  class PointsToVariableSet {
   public:
    struct Hash {
      size_t operator()(const PointsToVariableSet& s) const {
        return boost::hash_range(s.m_set.begin(), s.m_set.end());
      }
    };
  
    struct EqualTo {
      bool operator()(const PointsToVariableSet& s1,
                      const PointsToVariableSet& s2) const {
        return s1.m_set == s2.m_set;
      }
    };
  
    using iterator = boost::container::flat_set<PointsToVariable>::const_iterator;
  
    PointsToVariableSet() = default;
  
    template <typename InputIterator>
    PointsToVariableSet(InputIterator begin, InputIterator end)
        : m_set(begin, end) {}
  
    void insert(const PointsToVariable& v) { m_set.insert(v); }
  
    iterator begin() const { return m_set.begin(); }
  
    iterator end() const { return m_set.end(); }
  
   private:
    // Sets of variables correspond to sets of anchors and are generally small
    // (most of the time, just a singleton). We use a flat set (i.e., an ordered
    // associative array) in order to optimize memory usage.
    boost::container::flat_set<PointsToVariable> m_set;
  };
  
  } // namespace pts_impl
  
  std::vector<std::pair<size_t, PointsToVariable>> PointsToAction::get_arguments()
      const {
    always_assert(m_operation.is_invoke() || m_operation.is_disjunction());
    std::vector<std::pair<size_t, PointsToVariable>> args;
    for (const auto& binding : m_arguments) {
      if (binding.first >= 0) {
        // We filter out special arguments (like the destination variable), which
        // all have a negative index.
        args.push_back(binding);
      }
    }
    return args;
  }
  
  PointsToAction PointsToAction::load_operation(
      const PointsToOperation& operation, PointsToVariable dest) {
    always_assert(operation.is_load());
    return PointsToAction(operation, {{dest_key(), dest}});
  }
  
  PointsToAction PointsToAction::get_class_operation(PointsToVariable dest,
                                                     PointsToVariable src) {
    return PointsToAction(PointsToOperation(PTS_GET_CLASS),
                          {{dest_key(), dest}, {src_key(), src}});
  }
  
  PointsToAction PointsToAction::check_cast_operation(DexType* dex_type,
                                                      PointsToVariable dest,
                                                      PointsToVariable src) {
    return PointsToAction(PointsToOperation(PTS_CHECK_CAST, dex_type),
                          {{dest_key(), dest}, {src_key(), src}});
  }
  
  PointsToAction PointsToAction::get_operation(
      const PointsToOperation& operation,
      PointsToVariable dest,
      boost::optional<PointsToVariable> instance) {
    always_assert(operation.is_get());
    always_assert(!(instance && operation.kind == PTS_SPUT));
    if (instance) {
      return PointsToAction(operation,
                            {{dest_key(), dest}, {instance_key(), *instance}});
    } else {
      return PointsToAction(operation, {{dest_key(), dest}});
    }
  }
  
  PointsToAction PointsToAction::put_operation(
      const PointsToOperation& operation,
      PointsToVariable rhs,
      boost::optional<PointsToVariable> lhs) {
    always_assert(operation.is_put());
    always_assert(!(lhs && operation.kind == PTS_SPUT));
    if (lhs) {
      return PointsToAction(operation, {{lhs_key(), *lhs}, {rhs_key(), rhs}});
    } else {
      return PointsToAction(operation, {{rhs_key(), rhs}});
    }
  }
  
  PointsToAction PointsToAction::invoke_operation(
      const PointsToOperation& operation,
      boost::optional<PointsToVariable> dest,
      boost::optional<PointsToVariable> instance,
      const std::vector<std::pair<int32_t, PointsToVariable>>& args) {
    always_assert(operation.is_invoke());
    always_assert(!(instance && operation.kind == PTS_INVOKE_STATIC));
    std::vector<std::pair<int32_t, PointsToVariable>> bindings;
    bindings.reserve(args.size() + 2);
    if (dest) {
      bindings.push_back({dest_key(), *dest});
    }
    if (instance) {
      bindings.push_back({instance_key(), *instance});
    }
    bindings.insert(bindings.end(), args.begin(), args.end());
    return PointsToAction(operation, bindings);
  }
  
  PointsToAction PointsToAction::return_operation(PointsToVariable src) {
    return PointsToAction(PointsToOperation(PTS_RETURN), {{src_key(), src}});
  }
  
  template <typename InputIterator>
  PointsToAction PointsToAction::disjunction(PointsToVariable dest,
                                             InputIterator first,
                                             InputIterator last) {
    pts_impl::PointsToVariableSet vars(first, last);
    std::vector<std::pair<int32_t, PointsToVariable>> args;
    int32_t arg = 0;
    for (const auto& var : vars) {
      args.push_back({arg++, var});
    }
    args.push_back({dest_key(), dest});
    return PointsToAction(PointsToOperation(PTS_DISJUNCTION), args);
  }
  
  PointsToAction::PointsToAction(
      const PointsToOperation& operation,
      const std::vector<std::pair<int32_t, PointsToVariable>>& arguments)
      : m_operation(operation) {
    for (const auto& binding : arguments) {
      auto status = m_arguments.insert(binding);
      // Making sure that there's no duplicate binding in the argument list.
      always_assert(status.second);
    }
    m_arguments.shrink_to_fit();
  }
  
  PointsToVariable PointsToAction::get_arg(int32_t key) const {
    auto it = m_arguments.find(key);
    always_assert(it != m_arguments.end());
    return it->second;
  }
  
  s_expr PointsToAction::to_s_expr() const {
    std::vector<s_expr> args;
    for (const auto& arg : m_arguments) {
      args.push_back(s_expr({s_expr(arg.first), arg.second.to_s_expr()}));
    }
    return s_expr({m_operation.to_s_expr(), s_expr(args)});
  }
  
  boost::optional<PointsToAction> PointsToAction::from_s_expr(const s_expr& e) {
    s_expr operation;
    s_expr args;
    if (!s_patn({s_patn(operation), s_patn({}, args)}).match_with(e)) {
      return {};
    }
    auto operation_opt = PointsToOperation::from_s_expr(operation);
    if (!operation_opt) {
      return {};
    }
    std::vector<std::pair<int32_t, PointsToVariable>> arguments;
    for (size_t i = 0; i < args.size(); ++i) {
      int32_t arg;
      s_expr var;
      if (!s_patn({s_patn(&arg), s_patn(var)}).match_with(args[i])) {
        return {};
      }
      auto var_opt = PointsToVariable::from_s_expr(var);
      if (!var_opt) {
        return {};
      }
      arguments.push_back({arg, *var_opt});
    }
    return {PointsToAction(*operation_opt, arguments)};
  }
  
  namespace pts_impl {
  
  std::string special_edge_to_string(SpecialPointsToEdge e) {
    switch (e) {
    case PTS_ARRAY_ELEMENT: {
      return "ARRAY_ELEM";
    }
    default:
      not_reached();
    }
  }
  
  } // namespace pts_impl
  
  std::ostream& operator<<(std::ostream& o, const PointsToAction& a) {
    const PointsToOperation& op = a.operation();
    switch (op.kind) {
    case PTS_CONST_STRING: {
      o << a.dest() << " = " << std::quoted(op.dex_string->str());
      break;
    }
    case PTS_CONST_CLASS: {
      o << a.dest() << " = CLASS<" << op.dex_type->get_name()->str() << ">";
      break;
    }
    case PTS_GET_EXCEPTION: {
      o << a.dest() << " = EXCEPTION";
      break;
    }
    case PTS_NEW_OBJECT: {
      o << a.dest() << " = NEW " << op.dex_type->get_name()->str();
      break;
    }
    case PTS_LOAD_PARAM: {
      o << a.dest() << " = PARAM " << op.parameter;
      break;
    }
    case PTS_GET_CLASS: {
      o << a.dest() << " = GET_CLASS(" << a.src() << ")";
      break;
    }
    case PTS_CHECK_CAST: {
      o << a.dest() << " = CAST<" << op.dex_type->get_name()->str() << ">("
        << a.src() << ")";
      break;
    }
    case PTS_IGET: {
      o << a.dest() << " = " << a.instance() << "."
        << op.dex_field->get_class()->get_name()->str() << "#"
        << op.dex_field->get_name()->str();
      break;
    }
    case PTS_IGET_SPECIAL: {
      o << a.dest() << " = " << pts_impl::special_edge_to_string(op.special_edge)
        << "(" << a.instance() << ")";
      break;
    }
    case PTS_SGET: {
      o << a.dest() << " = " << op.dex_field->get_class()->get_name()->str()
        << "#" << op.dex_field->get_name()->str();
      break;
    }
    case PTS_IPUT: {
      o << a.lhs() << "." << op.dex_field->get_class()->get_name()->str() << "#"
        << op.dex_field->get_name()->str() << " = " << a.rhs();
      break;
    }
    case PTS_IPUT_SPECIAL: {
      o << pts_impl::special_edge_to_string(op.special_edge) << "(" << a.lhs()
        << ") = " << a.rhs();
      break;
    }
    case PTS_SPUT: {
      o << op.dex_field->get_class()->get_name()->str() << "#"
        << op.dex_field->get_name()->str() << " = " << a.rhs();
      break;
    }
    case PTS_INVOKE_VIRTUAL:
    case PTS_INVOKE_SUPER:
    case PTS_INVOKE_DIRECT:
    case PTS_INVOKE_INTERFACE:
    case PTS_INVOKE_STATIC: {
      if (a.has_dest()) {
        o << a.dest() << " = ";
      }
      if (!op.is_static_call()) {
        o << a.instance() << ".{";
        switch (op.kind) {
        case PTS_INVOKE_VIRTUAL: {
          o << "V";
          break;
        }
        case PTS_INVOKE_SUPER: {
          o << "S";
          break;
        }
        case PTS_INVOKE_DIRECT: {
          o << "D";
          break;
        }
        case PTS_INVOKE_INTERFACE: {
          o << "I";
          break;
        }
        default: { always_assert(false); }
        }
        o << "}";
      }
      o << op.dex_method->get_class()->get_name()->str() << "#"
        << op.dex_method->get_name()->str() << "(";
      auto args = a.get_arguments();
      for (auto it = args.begin(); it != args.end(); ++it) {
        o << it->first << " => " << it->second;
        if (std::next(it) != args.end()) {
          o << ", ";
        }
      }
      o << ")";
      break;
    }
    case PTS_RETURN: {
      o << "RETURN " << a.src();
      break;
    }
    case PTS_DISJUNCTION: {
      o << a.dest() << " = ";
      auto args = a.get_arguments();
      for (auto it = args.begin(); it != args.end(); ++it) {
        o << it->second;
        if (std::next(it) != args.end()) {
          o << " U ";
        }
      }
      break;
    }
    }
    return o;
  }
  
  namespace pts_impl {
  
  /*
   * In Andersen's approach to points-to analysis, a program is translated into a
   * system of set constraints by modeling pointers as sets. This model is
   * flow-insensitive, i.e., control-flow dependencies among statements are
   * abstracted away. While this makes the analysis more tractable, applying this
   * approach naively can lead to major precision problems. For example, consider
   * the following piece of Java code:
   *
   *   x = new A();
   *   x.field1 = new B();
   *   x.field2 = new C();
   *
   * The corresponding Dex code may look like:
   *
   *   new-instance v0, LA;
   *   invoke-direct {v0}, LA;.<init>:()V
   *   new-instance v1, LB;
   *   invoke-direct {v1}, LB;.<init>:()V
   *   iput-object v1, v0, LA;.field1:LB;
   *   new-instance v1, LC;
   *   invoke-direct {v1}, LC;.<init>:()V
   *   iput-object v1, v0, LA;.field2:LC;
   *
   * Applying Andersen's approach directly, we would assign a set variable to each
   * register in the code, thus obtaining the following system of set constraints:
   *
   *   V0 = NEW LA;
   *   V0.{D}LA;#<init>()
   *   V1 = NEW LB;
   *   V1.{D}LB;#<init>()
   *   V1 = NEW LC;
   *   V1.{D}LB;#<init>()
   *   V0.LA;#field1 = V1
   *   V0.LA;#field2 = V1
   *
   * This is obviously very bad, as the points-to sets of field1 and field2 are
   * equated. The problem here is that register v1 is reused in two different
   * contexts and that information is lost by the flow-insensitive abstraction. In
   * order to avoid this pitfall, we use the notion of `anchor` introduced in the
   * following paper:
   *
   *   A. Venet. A Scalable Nonuniform Pointer Analysis for Embedded Programs.
   *   In Proceedings of the International Static Analysis Symposium, 2004.
   *
   * Each operation returning a pointer is associated a unique `anchor`. A
   * preliminary intraprocedural, flow-sensitive analysis assigns a set of anchors
   * to each register. When the points-to equations are generated, we use the
   * anchors and not the registers as the basis for creating set variables. Hence,
   * the points-to equations for the code snippet above would look like:
   *
   *   V0 = NEW LA;
   *   V0.{D}LA;#<init>()
   *   V1 = NEW LB;
   *   V1.{D}LB;#<init>()
   *   V2 = NEW LC;
   *   V2.{D}LB;#<init>()
   *   V0.LA;#field1 = V1
   *   V0.LA;#field2 = V2
   *
   * The points-to sets of field1 and field2 are thus kept separate. We get the
   * same level of precision as if the code were in SSA form, without incurring
   * the cost of managing the SSA representation.
   */
  
  using namespace std::placeholders;
  
  using register_t = uint32_t;
  
  // We use this special register to denote the result of a method invocation or a
  // filled-array creation.
  register_t RESULT_REGISTER = std::numeric_limits<register_t>::max();
  
  // We represent an anchor by a pointer to the corresponding instruction. An
  // empty anchor set is semantically equivalent to the `null` reference.
  using AnchorDomain = PatriciaTreeSetAbstractDomain<IRInstruction*>;
  
  using AnchorEnvironment =
      PatriciaTreeMapAbstractEnvironment<register_t, AnchorDomain>;
  
  class AnchorPropagation final
      : public MonotonicFixpointIterator<cfg::GraphInterface, AnchorEnvironment> {
   public:
    using NodeId = cfg::Block*;
  
    AnchorPropagation(const cfg::ControlFlowGraph& cfg,
                      bool is_static_method,
                      IRCode* code)
        : MonotonicFixpointIterator(cfg, cfg.blocks().size()),
          m_is_static_method(is_static_method),
          m_code(code),
          m_this_anchor(nullptr) {}
  
    void analyze_node(const NodeId& node,
                      AnchorEnvironment* current_state) const override {
      for (const MethodItemEntry& mie : *node) {
        if (mie.type == MFLOW_OPCODE) {
          analyze_instruction(mie.insn, current_state);
        }
      }
    }
  
    AnchorEnvironment analyze_edge(
        const EdgeId&,
        const AnchorEnvironment& exit_state_at_source) const override {
      return exit_state_at_source;
    }
  
    void analyze_instruction(IRInstruction* insn,
                             AnchorEnvironment* current_state) const {
      switch (insn->opcode()) {
      case IOPCODE_LOAD_PARAM_OBJECT: {
        // There's nothing to do, since this instruction has been taken care of
        // during the initialization of the analysis.
        break;
      }
      case OPCODE_MOVE_EXCEPTION: {
        current_state->set(insn->dest(), AnchorDomain(insn));
        break;
      }
      case OPCODE_CONST_STRING:
      case OPCODE_CONST_CLASS:
      case OPCODE_CHECK_CAST:
      case OPCODE_NEW_INSTANCE:
      case OPCODE_NEW_ARRAY:
      case OPCODE_AGET_OBJECT:
      case OPCODE_IGET_OBJECT:
      case OPCODE_SGET_OBJECT:
      case OPCODE_FILLED_NEW_ARRAY: {
        current_state->set(RESULT_REGISTER, AnchorDomain(insn));
        break;
      }
      case OPCODE_MOVE_OBJECT: {
        current_state->set(insn->dest(), current_state->get(insn->src(0)));
        break;
      }
      case IOPCODE_MOVE_RESULT_PSEUDO_OBJECT: {
      case OPCODE_MOVE_RESULT_OBJECT:
        current_state->set(insn->dest(), current_state->get(RESULT_REGISTER));
        break;
      }
      case OPCODE_INVOKE_STATIC:
      case OPCODE_INVOKE_VIRTUAL:
      case OPCODE_INVOKE_SUPER:
      case OPCODE_INVOKE_DIRECT:
      case OPCODE_INVOKE_INTERFACE: {
        DexMethodRef* dex_method = insn->get_method();
        if (is_object(dex_method->get_proto()->get_rtype())) {
          // We attach an anchor to a method invocation only if the method returns
          // an object.
          current_state->set(RESULT_REGISTER, AnchorDomain(insn));
        }
        break;
      }
      default: {
        // Since registers can be reused in different contexts, we need to
        // invalidate the corresponding anchor sets. Note that this case also
        // encompasses the initialization to null, like `const v1, 0`.
        if (insn->dests_size() > 0) {
          current_state->set(insn->dest(), AnchorDomain());
          if (insn->dest_is_wide()) {
            current_state->set(insn->dest() + 1, AnchorDomain());
          }
        }
        // There is no need to invalidate RESULT_REGISTER, because all operations
        // that may write a reference into RESULT_REGISTER are handled in the
        // switch statement.
      }
      }
    }
  
    void run() { MonotonicFixpointIterator::run(initial_environment()); }
  
    bool is_this_anchor(IRInstruction* insn) const {
      return insn == m_this_anchor;
    }
  
   private:
    // We initialize all registers to the empty anchor set, i.e. the semantic
    // equivalent of `null` in our analysis. However, the parameters of the method
    // are initialized to the anchors of the corresponding LOAD_PARAM
    // instructions.
    AnchorEnvironment initial_environment() {
      AnchorEnvironment env;
      // We first initialize all registers to `null`.
      env.set(RESULT_REGISTER, AnchorDomain());
      for (size_t reg = 0; reg < m_code->get_registers_size(); ++reg) {
        env.set(reg, AnchorDomain());
      }
      // We then initialize the parameters of the method.
      bool first_param = true;
      for (const MethodItemEntry& mie :
           InstructionIterable(m_code->get_param_instructions())) {
        IRInstruction* insn = mie.insn;
        if (first_param && !m_is_static_method) {
          always_assert_log(insn->opcode() == IOPCODE_LOAD_PARAM_OBJECT,
                            "Unexpected instruction '%s' in virtual method\n",
                            SHOW(insn));
          m_this_anchor = insn;
        }
        switch (insn->opcode()) {
        case IOPCODE_LOAD_PARAM_OBJECT: {
          env.set(insn->dest(), AnchorDomain(insn));
          break;
        }
        case IOPCODE_LOAD_PARAM:
        case IOPCODE_LOAD_PARAM_WIDE: {
          break;
        }
        default: {
          always_assert_log(false, "Unexpected instruction '%s'\n", SHOW(insn));
        }
        }
        first_param = false;
      }
      return env;
    }
  
    bool m_is_static_method;
    IRCode* m_code;
    IRInstruction* m_this_anchor;
  };
  
  // Generates the points-to actions for a single method.
  class PointsToActionGenerator final {
   public:
    explicit PointsToActionGenerator(DexMethod* dex_method,
                                     PointsToMethodSemantics* semantics,
                                     const TypeSystem& type_system,
                                     const PointsToSemanticsUtils& utils)
        : m_dex_method(dex_method),
          m_semantics(semantics),
          m_type_system(type_system),
          m_utils(utils) {}
  
    void run() {
      IRCode* code = m_dex_method->get_code();
      always_assert(code != nullptr);
      code->build_cfg();
      cfg::ControlFlowGraph& cfg = code->cfg();
      cfg.calculate_exit_block();
  
      // We first propagate the anchors across the code.
      m_analysis =
          std::make_unique<AnchorPropagation>(cfg, is_static(m_dex_method), code);
      m_analysis->run();
  
      // Then we assign a unique variable to each anchor.
      name_anchors(cfg);
  
      // The LOAD_PARAM_* instructions sit next to each other at the beginning of
      // the entry block. We need to process them first.
      size_t param_cursor = 0;
      bool first_param = true;
      for (const MethodItemEntry& mie : *cfg.entry_block()) {
        if (mie.type == MFLOW_OPCODE) {
          IRInstruction* insn = mie.insn;
          switch (insn->opcode()) {
          case IOPCODE_LOAD_PARAM_OBJECT: {
            if (first_param && !is_static(m_dex_method)) {
              // If the method is not static, the first parameter corresponds to
              // `this`, which is represented using a special points-to variable.
            } else {
              m_semantics->add(PointsToAction::load_operation(
                  PointsToOperation(PTS_LOAD_PARAM, param_cursor++),
                  get_variable_from_anchor(insn)));
            }
            break;
          }
          case IOPCODE_LOAD_PARAM:
          case IOPCODE_LOAD_PARAM_WIDE: {
            ++param_cursor;
            break;
          }
          default: {
            // We've reached the end of the LOAD_PARAM_* instruction block and we
            // simply exit the loop. Note that premature loop exit is probably the
            // only legitimate use of goto in C++ code.
            goto done;
          }
          }
          first_param = false;
        }
      }
    done:
      // We go over each IR instruction and generate the corresponding points-to
      // actions.
      for (cfg::Block* block : cfg.blocks()) {
        AnchorEnvironment state = m_analysis->get_entry_state_at(block);
        for (const MethodItemEntry& mie : InstructionIterable(*block)) {
          IRInstruction* insn = mie.insn;
          generate_action(insn, state);
          m_analysis->analyze_instruction(insn, &state);
        }
      }
      m_semantics->shrink();
    }
  
   private:
    // We associate each anchor with a unique points-to variable.
    void name_anchors(const cfg::ControlFlowGraph& cfg) {
      for (cfg::Block* block : cfg.blocks()) {
        for (const MethodItemEntry& mie : *block) {
          if (mie.type == MFLOW_OPCODE) {
            IRInstruction* insn = mie.insn;
            if (is_anchored_instruction(insn)) {
              m_anchors.insert({insn, m_semantics->get_new_variable()});
            }
          }
        }
      }
    }
  
    // Each IR instruction that returns a result of reference type is assigned an
    // anchor.
    bool is_anchored_instruction(IRInstruction* insn) const {
      switch (insn->opcode()) {
      case IOPCODE_LOAD_PARAM_OBJECT:
      case OPCODE_MOVE_EXCEPTION:
      case OPCODE_CONST_STRING:
      case OPCODE_CONST_CLASS:
      case OPCODE_CHECK_CAST:
      case OPCODE_NEW_INSTANCE:
      case OPCODE_NEW_ARRAY:
      case OPCODE_AGET_OBJECT:
      case OPCODE_IGET_OBJECT:
      case OPCODE_SGET_OBJECT:
      case OPCODE_FILLED_NEW_ARRAY: {
        return true;
      }
      case OPCODE_INVOKE_STATIC:
      case OPCODE_INVOKE_VIRTUAL:
      case OPCODE_INVOKE_SUPER:
      case OPCODE_INVOKE_DIRECT:
      case OPCODE_INVOKE_INTERFACE: {
        return is_object(insn->get_method()->get_proto()->get_rtype());
      }
      default: { return false; }
      }
    }
  
    void generate_action(IRInstruction* insn, const AnchorEnvironment& state) {
      switch (insn->opcode()) {
      case OPCODE_MOVE_EXCEPTION: {
        m_semantics->add(
            PointsToAction::load_operation(PointsToOperation(PTS_GET_EXCEPTION),
                                           get_variable_from_anchor(insn)));
        break;
      }
      case OPCODE_RETURN_OBJECT: {
        m_semantics->add(PointsToAction::return_operation(
            get_variable_from_anchor_set(state.get(insn->src(0)))));
        break;
      }
      case OPCODE_CONST_STRING: {
        m_semantics->add(PointsToAction::load_operation(
            PointsToOperation(PTS_CONST_STRING, insn->get_string()),
            get_variable_from_anchor(insn)));
        break;
      }
      case OPCODE_CONST_CLASS: {
        m_semantics->add(PointsToAction::load_operation(
            PointsToOperation(PTS_CONST_CLASS, insn->get_type()),
            get_variable_from_anchor(insn)));
        break;
      }
      case OPCODE_CHECK_CAST: {
        m_semantics->add(PointsToAction::check_cast_operation(
            insn->get_type(),
            get_variable_from_anchor(insn),
            get_variable_from_anchor_set(state.get(insn->src(0)))));
        break;
      }
      case OPCODE_NEW_INSTANCE: {
        DexType* dex_type = insn->get_type();
        if (m_type_system.is_subtype(m_utils.get_throwable_type(), dex_type)) {
          // If the object created is an exception (i.e., its type inherits from
          // java.lang.Throwable), we use PTS_GET_EXCEPTION. In our semantic
          // model, the exact identity of an exception is abstracted away for
          // simplicity. The operation PTS_GET_EXCEPTION can be interpreted as a
          // nondeterministic choice among all abstract object instances that are
          // exceptions.
          m_semantics->add(
              PointsToAction::load_operation(PointsToOperation(PTS_GET_EXCEPTION),
                                             get_variable_from_anchor(insn)));
          break;
        }
        // Otherwise, we fall through to the generic case.
      }
      case OPCODE_NEW_ARRAY:
      case OPCODE_FILLED_NEW_ARRAY: {
        m_semantics->add(PointsToAction::load_operation(
            PointsToOperation(PTS_NEW_OBJECT, insn->get_type()),
            get_variable_from_anchor(insn)));
        if (insn->opcode() == OPCODE_FILLED_NEW_ARRAY) {
          const DexType* element_type = get_array_type(insn->get_type());
          if (!is_object(element_type)) {
            break;
          }
          auto lhs =
              boost::optional<PointsToVariable>(get_variable_from_anchor(insn));
          for (size_t i = 0; i < insn->srcs_size(); ++i) {
            m_semantics->add(PointsToAction::put_operation(
                PointsToOperation(PTS_IPUT_SPECIAL, PTS_ARRAY_ELEMENT),
                get_variable_from_anchor_set(state.get(insn->src(i))),
                lhs));
          }
        }
        break;
      }
      case OPCODE_APUT_OBJECT: {
        PointsToVariable rhs =
            get_variable_from_anchor_set(state.get(insn->src(0)));
        PointsToVariable lhs =
            get_variable_from_anchor_set(state.get(insn->src(1)));
        m_semantics->add(PointsToAction::put_operation(
            PointsToOperation(PTS_IPUT_SPECIAL, PTS_ARRAY_ELEMENT),
            rhs,
            boost::optional<PointsToVariable>(lhs)));
        break;
      }
      case OPCODE_IPUT_OBJECT: {
        PointsToVariable rhs =
            get_variable_from_anchor_set(state.get(insn->src(0)));
        PointsToVariable lhs =
            get_variable_from_anchor_set(state.get(insn->src(1)));
        m_semantics->add(PointsToAction::put_operation(
            PointsToOperation(PTS_IPUT, insn->get_field()),
            rhs,
            boost::optional<PointsToVariable>(lhs)));
        break;
      }
      case OPCODE_SPUT_OBJECT: {
        m_semantics->add(PointsToAction::put_operation(
            PointsToOperation(PTS_SPUT, insn->get_field()),
            get_variable_from_anchor_set(state.get(insn->src(0)))));
        break;
      }
      case OPCODE_AGET_OBJECT: {
        PointsToVariable instance =
            get_variable_from_anchor_set(state.get(insn->src(0)));
        m_semantics->add(PointsToAction::get_operation(
            PointsToOperation(PTS_IGET_SPECIAL, PTS_ARRAY_ELEMENT),
            get_variable_from_anchor(insn),
            boost::optional<PointsToVariable>(instance)));
        break;
      }
      case OPCODE_IGET_OBJECT: {
        PointsToVariable instance =
            get_variable_from_anchor_set(state.get(insn->src(0)));
        m_semantics->add(PointsToAction::get_operation(
            PointsToOperation(PTS_IGET, insn->get_field()),
            get_variable_from_anchor(insn),
            boost::optional<PointsToVariable>(instance)));
        break;
      }
      case OPCODE_SGET_OBJECT: {
        // One way to get the java.lang.Class object of a primitive type is by
        // querying the `TYPE` field of the corresponding wrapper class. We
        // translate those kind of sget-object instructions into equivalent
        // PTS_CONST_CLASS operations.
        if (m_utils.is_primitive_type_class_object_retrieval(insn)) {
          m_semantics->add(PointsToAction::load_operation(
              PointsToOperation(PTS_CONST_CLASS, insn->get_field()->get_class()),
              get_variable_from_anchor(insn)));
          break;
        }
        m_semantics->add(PointsToAction::get_operation(
            PointsToOperation(PTS_SGET, insn->get_field()),
            get_variable_from_anchor(insn)));
        break;
      }
      case OPCODE_INVOKE_STATIC:
      case OPCODE_INVOKE_VIRTUAL:
      case OPCODE_INVOKE_SUPER:
      case OPCODE_INVOKE_DIRECT:
      case OPCODE_INVOKE_INTERFACE: {
        translate_invoke(insn, state);
        break;
      }
      default: {
        // All other instructions are either transparent to points-to analysis or
        // have already been taken care of (LOAD_PARAM_*).
      }
      }
    }
  
    // This is where we can provide the semantics of external API calls that are
    // relevant to points-to analysis and for which the source code is either
    // unavailable or hard to process automatically (e.g., native methods).
    void translate_invoke(IRInstruction* insn, const AnchorEnvironment& state) {
      // Calls to java.lang.Object#getClass() are converted to a points-to
      // operation in order to simplify the analysis.
      if (m_utils.is_get_class_invocation(insn)) {
        m_semantics->add(PointsToAction::get_class_operation(
            get_variable_from_anchor(insn),
            get_variable_from_anchor_set(state.get(insn->src(0)))));
        return;
      }
      // Otherwise, we default to the general translation of method calls.
      default_invoke_translation(insn, state);
    }
  
    void default_invoke_translation(IRInstruction* insn,
                                    const AnchorEnvironment& state) {
      DexMethodRef* dex_method = insn->get_method();
      DexProto* proto = dex_method->get_proto();
      const auto& signature = proto->get_args()->get_type_list();
      std::vector<std::pair<int32_t, PointsToVariable>> args;
      size_t src_idx{0};
  
      // Allocate a variable for the returned object if any.
      boost::optional<PointsToVariable> dest;
      if (is_object(insn->get_method()->get_proto()->get_rtype())) {
        dest = {get_variable_from_anchor(insn)};
      }
  
      // Allocate a variable for the instance object if any.
      boost::optional<PointsToVariable> instance;
      if (insn->opcode() != OPCODE_INVOKE_STATIC) {
        // The first argument is a reference to the object instance on which the
        // method is invoked.
        instance = {
            get_variable_from_anchor_set(state.get(insn->src(src_idx++)))};
      }
  
      // Process the arguments of the method invocation.
      int32_t arg_pos = 0;
      for (DexType* dex_type : signature) {
        if (is_object(dex_type)) {
          args.push_back(
              {arg_pos,
               get_variable_from_anchor_set(state.get(insn->src(src_idx++)))});
        } else {
          // We skip this argument.
          ++src_idx;
        }
        ++arg_pos;
      }
  
      // Select the right points-to operation.
      PointsToOperationKind invoke_kind;
      switch (insn->opcode()) {
      case OPCODE_INVOKE_STATIC: {
        invoke_kind = PTS_INVOKE_STATIC;
        break;
      }
      case OPCODE_INVOKE_VIRTUAL: {
        invoke_kind = PTS_INVOKE_VIRTUAL;
        break;
      }
      case OPCODE_INVOKE_SUPER: {
        invoke_kind = PTS_INVOKE_SUPER;
        break;
      }
      case OPCODE_INVOKE_DIRECT: {
        invoke_kind = PTS_INVOKE_DIRECT;
        break;
      }
      case OPCODE_INVOKE_INTERFACE: {
        invoke_kind = PTS_INVOKE_INTERFACE;
        break;
      }
      default: {
        // This function is only called on invoke instructions.
        always_assert(false);
      }
      }
  
      m_semantics->add(PointsToAction::invoke_operation(
          PointsToOperation(invoke_kind, insn->get_method()),
          dest,
          instance,
          args));
    }
  
    PointsToVariable get_variable_from_anchor(IRInstruction* insn) {
      if (m_analysis->is_this_anchor(insn)) {
        return PointsToVariable::this_variable();
      }
      auto it = m_anchors.find(insn);
      always_assert(it != m_anchors.end());
      return it->second;
    }
  
    // If the anchor set is not a singleton, we need to introduce a disjunction
    // operation.
    PointsToVariable get_variable_from_anchor_set(const AnchorDomain& s) {
      // By design, the analysis can't generate the Top value.
      always_assert(!s.is_top());
      if (s.is_bottom()) {
        // This means that some code in the method is unreachable.
        TRACE(PTA, 2, "Unreachable code in %s\n", SHOW(m_dex_method));
        return PointsToVariable();
      }
      auto anchors = s.elements();
      if (anchors.size() == 0) {
        // The denotation of the anchor set is just the `null` reference. This is
        // represented by a special points-to variable.
        return PointsToVariable::null_variable();
      }
      if (anchors.size() == 1) {
        // When the anchor set is a singleton, there is no need to introduce a
        // disjunction.
        return get_variable_from_anchor(*anchors.begin());
      }
      // Otherwise, we need a disjunction.
      PointsToVariableSet ptv_set;
      for (IRInstruction* insn : anchors) {
        ptv_set.insert(get_variable_from_anchor(insn));
      }
      auto it = m_anchor_sets.find(ptv_set);
      if (it != m_anchor_sets.end()) {
        // The disjunction has already been generated.
        return it->second;
      }
      // Otherwise, we create a new disjunction.
      PointsToVariable new_v = m_semantics->get_new_variable();
      m_anchor_sets.emplace(ptv_set, new_v);
      // We insert the newly created disjunction before its first use.
      m_semantics->add(
          PointsToAction::disjunction(new_v, ptv_set.begin(), ptv_set.end()));
      return new_v;
    }
  
    DexMethod* m_dex_method;
    PointsToMethodSemantics* m_semantics;
    const TypeSystem& m_type_system;
    const PointsToSemanticsUtils& m_utils;
    std::unique_ptr<AnchorPropagation> m_analysis;
    // We assign each anchor a points-to variable. This map keeps track of the
    // naming.
    std::unordered_map<IRInstruction*, PointsToVariable> m_anchors;
    // A table that keeps track of all disjunctions already created, so that we
    // only generate one disjuction per anchor set.
    std::unordered_map<PointsToVariableSet,
                       PointsToVariable,
                       PointsToVariableSet::Hash,
                       PointsToVariableSet::EqualTo>
        m_anchor_sets;
  };
  
  // Removes points-to equations that have no effect on the computation of the
  // points-to analysis. We compute the dependency graph of the points-to
  // equations and we discard all variables that are not involved in any relevant
  // computation.
  class Shrinker final {
   public:
    explicit Shrinker(std::vector<PointsToAction>* pt_actions)
        : m_pt_actions(pt_actions) {}
  
    void run() {
      // We first identify all the variables that we surely need to keep in order
      // to perform the points-to analysis.
      find_root_vars();
      // We then compute the dependency graph: there is an edge v -> w between
      // points-to variables v and w iff the value of w is needed to compute the
      // value of v.
      build_dependency_graph();
      // We compute the set of variables that are reachable from any one of the
      // root variables in the dependency graph.
      collect_reachable_vars();
      // We remove any points-to equation assigning a value to a variable that
      // hasn't been marked as reachable in the previous step.
      shrink_points_to_actions();
    }
  
   private:
    using VariableSet =
        std::unordered_set<PointsToVariable, boost::hash<PointsToVariable>>;
  
    // We keep all `put`, `invoke` and `return` operations, since they presumably
    // have an effect on the analysis.
    void find_root_vars() {
      for (const PointsToAction& pt_action : *m_pt_actions) {
        const PointsToOperation& op = pt_action.operation();
        if (op.is_put()) {
          if (!op.is_sput()) {
            m_root_vars.insert(pt_action.lhs());
          }
          m_root_vars.insert(pt_action.rhs());
          continue;
        }
        if (op.is_invoke()) {
          if (op.is_virtual_call()) {
            m_root_vars.insert(pt_action.instance());
          }
          for (const auto& arg : pt_action.get_arguments()) {
            m_root_vars.insert(arg.second);
          }
          continue;
        }
        if (op.is_return()) {
          m_root_vars.insert(pt_action.src());
          continue;
        }
      }
    }
  
    // When building the dependency graph, we are only interested in operations
    // that assign a value to a variable but don't create any points-to relation
    // between objects (unlike a `put` operation, for example). We don't consider
    // `load` operations, because they can't create dependencies among variables.
    // An edge v -> w in the dependency graph means that computing the value of
    // variable v requires the value of variable w.
    void build_dependency_graph() {
      for (const PointsToAction& pt_action : *m_pt_actions) {
        const PointsToOperation& op = pt_action.operation();
        if (op.is_get_class() || op.is_check_cast()) {
          add_dependency(pt_action.dest(), pt_action.src());
          continue;
        }
        if (op.is_get() && !op.is_sget()) {
          add_dependency(pt_action.dest(), pt_action.instance());
          continue;
        }
        if (op.is_disjunction()) {
          for (const auto& arg : pt_action.get_arguments()) {
            add_dependency(pt_action.dest(), arg.second);
          }
          continue;
        }
      }
    }
  
    void add_dependency(const PointsToVariable& x, const PointsToVariable& y) {
      m_dependency_graph[x].insert(y);
    }
  
    // If there exists a path from any root variable to a variable v, this means
    // that the value of variable v is required for performing the points-to
    // analysis. All other variables can safely be discarded. We compute the set
    // of reachable variables using a simple breadth-first traversal of the graph.
    void collect_reachable_vars() {
      std::deque<PointsToVariable> queue(m_root_vars.begin(), m_root_vars.end());
      while (!queue.empty()) {
        PointsToVariable v = queue.back();
        queue.pop_back();
        // Note that the variables already visited are exactly the variables that
        // we need to keep.
        if (m_vars_to_keep.count(v) != 0) {
          continue;
        }
        m_vars_to_keep.insert(v);
        const auto& deps = m_dependency_graph[v];
        queue.insert(queue.begin(), deps.begin(), deps.end());
      }
    }
  
    void shrink_points_to_actions() {
      // Any `load`, `check_cast`, `get` or `disjunction` operation assigning a
      // value to a variable that hasn't been marked to keep can safely be
      // discarded.
      m_pt_actions->erase(
          std::remove_if(m_pt_actions->begin(),
                         m_pt_actions->end(),
                         [this](const PointsToAction& pt_action) {
                           const PointsToOperation& op = pt_action.operation();
                           return (op.is_load() || op.is_check_cast() ||
                                   op.is_get() || op.is_disjunction()) &&
                                  (m_vars_to_keep.count(pt_action.dest()) == 0);
                         }),
          m_pt_actions->end());
      m_pt_actions->shrink_to_fit();
  
      // We can also safely remove the `dest` variable of a method call if it
      // hasn't been marked to keep. Computing the return value of a virtual call
      // during the analysis may entail performing the join of multiple points-to
      // sets, which is costly. Hence, removing unneeded return values is a
      // valuable optimization.
      for (PointsToAction& pt_action : *m_pt_actions) {
        if (pt_action.operation().is_invoke() && pt_action.has_dest() &&
            (m_vars_to_keep.count(pt_action.dest()) == 0)) {
          pt_action.remove_dest();
        }
      }
    }
  
    std::vector<PointsToAction>* m_pt_actions;
    std::unordered_map<PointsToVariable,
                       VariableSet,
                       boost::hash<PointsToVariable>>
        m_dependency_graph;
    VariableSet m_root_vars;
    VariableSet m_vars_to_keep;
  };
  
  #define KIND_STRING_TABLE         \
    {                               \
      KIND_STRING(PTS_APK),         \
      KIND_STRING(PTS_ABSTRACT),    \
      KIND_STRING(PTS_NATIVE),      \
      KIND_STRING(PTS_STUB),        \
    }                               \
  
  #define KIND_STRING(X) {X, #X}
  std::unordered_map<MethodKind, std::string, std::hash<int>>
      method_kind_to_string_table = KIND_STRING_TABLE;
  #undef KIND_STRING
  
  #define KIND_STRING(X) {#X, X}
  std::unordered_map<std::string, MethodKind> string_to_method_kind_table =
      KIND_STRING_TABLE;
  #undef KIND_STRING
  
  s_expr method_kind_to_s_expr(MethodKind kind) {
    auto it = method_kind_to_string_table.find(kind);
    always_assert(it != method_kind_to_string_table.end());
    return s_expr(it->second);
  }
  
  boost::optional<MethodKind> string_to_method_kind(const std::string& str) {
    auto it = string_to_method_kind_table.find(str);
    if (it == string_to_method_kind_table.end()) {
      return {};
    }
    return boost::optional<MethodKind>(it->second);
  }
  
  } // namespace pts_impl
  
  PointsToMethodSemantics::PointsToMethodSemantics(DexMethodRef* dex_method,
                                                   MethodKind kind,
                                                   size_t start_var_id,
                                                   size_t size_hint)
      : m_dex_method(dex_method), m_kind(kind), m_variable_counter(start_var_id) {
    m_points_to_actions.reserve(size_hint);
  }
  
  void PointsToMethodSemantics::shrink() {
    pts_impl::Shrinker shrinker(&m_points_to_actions);
    shrinker.run();
  }
  
  s_expr PointsToMethodSemantics::to_s_expr() const {
    using namespace pts_impl;
    std::vector<s_expr> actions;
    std::transform(m_points_to_actions.begin(),
                   m_points_to_actions.end(),
                   std::back_inserter(actions),
                   [](const PointsToAction& a) { return a.to_s_expr(); });
    return s_expr({dex_method_to_s_expr(m_dex_method),
                   method_kind_to_s_expr(m_kind),
                   s_expr(static_cast<int32_t>(m_variable_counter)),
                   s_expr(actions)});
  }
  
  boost::optional<PointsToMethodSemantics> PointsToMethodSemantics::from_s_expr(
      const s_expr& e) {
    using namespace pts_impl;
    s_expr dex_method_expr;
    std::string kind_str;
    int32_t var_counter;
    s_expr actions_expr;
    if (!s_patn({s_patn(dex_method_expr),
                 s_patn(&kind_str),
                 s_patn(&var_counter),
                 s_patn({}, actions_expr)})
             .match_with(e)) {
      return {};
    }
    auto dex_method_op = s_expr_to_dex_method(dex_method_expr);
    if (!dex_method_op) {
      return {};
    }
    auto kind_opt = string_to_method_kind(kind_str);
    if (!kind_opt) {
      return {};
    }
    PointsToMethodSemantics semantics(
        *dex_method_op, *kind_opt, var_counter, actions_expr.size());
    for (size_t i = 0; i < actions_expr.size(); ++i) {
      auto action_opt = PointsToAction::from_s_expr(actions_expr[i]);
      if (!action_opt) {
        return {};
      }
      semantics.add(*action_opt);
    }
    return boost::optional<PointsToMethodSemantics>(semantics);
  }
  
  std::ostream& operator<<(std::ostream& o, const PointsToMethodSemantics& s) {
    o << s.m_dex_method->get_class()->get_name()->str() << "#"
      << s.m_dex_method->get_name()->str() << ": "
      << SHOW(s.m_dex_method->get_proto()) << " ";
    switch (s.kind()) {
    case PTS_ABSTRACT: {
      o << "= ABSTRACT";
      break;
    }
    case PTS_NATIVE: {
      o << "= NATIVE";
      break;
    }
    case PTS_APK:
    case PTS_STUB: {
      o << "{" << std::endl;
      for (const auto& a : s.get_points_to_actions()) {
        o << " " << a << std::endl;
      }
      o << "}";
      break;
    }
    }
    o << std::endl;
    return o;
  }
  
  PointsToSemantics::PointsToSemantics(const Scope& scope, bool generate_stubs)
      : m_generate_stubs(generate_stubs), m_type_system(scope) {
    // We size the hash table so as to fit all the methods in scope.
    size_t method_count = 0;
    for (DexClass* dex_class : scope) {
      method_count +=
          dex_class->get_dmethods().size() + dex_class->get_vmethods().size();
    }
    m_method_semantics.reserve(method_count);
  
    // We initialize all entries in the hash table, which can then be concurrently
    // accessed by the workers using the thread-safe find() operation of
    // std::unordered_map.
    for (DexClass* dex_class : scope) {
      for (DexMethod* dmethod : dex_class->get_dmethods()) {
        initialize_entry(dmethod);
      }
      for (DexMethod* vmethod : dex_class->get_vmethods()) {
        initialize_entry(vmethod);
      }
    }
  
    // We generate a system of points-to actions for each Dex method in parallel.
    walk::parallel::methods(scope, [this](DexMethod* dex_method) {
      generate_points_to_actions(dex_method);
    });
  }
  
  void PointsToSemantics::load_stubs(const std::string& file_name) {
    std::ifstream file_input(file_name);
    s_expr_istream s_expr_input(file_input);
    while (s_expr_input.good()) {
      s_expr expr;
      s_expr_input >> expr;
      if (s_expr_input.eoi()) {
        break;
      }
      always_assert_log(
          !s_expr_input.fail(), "%s\n", s_expr_input.what().c_str());
      auto semantics_opt = PointsToMethodSemantics::from_s_expr(expr);
      always_assert_log(
          semantics_opt, "Couldn't parse S-expression: %s\n", expr.str().c_str());
      DexMethodRef* dex_method = semantics_opt->get_method();
      auto it = m_method_semantics.find(dex_method);
      if (it == m_method_semantics.end()) {
        m_method_semantics.emplace(dex_method, *semantics_opt);
      } else {
        TRACE(PTA, 2, "Collision with stub for method %s\n", SHOW(dex_method));
      }
    }
  }
  
  boost::optional<PointsToMethodSemantics*>
  PointsToSemantics::get_method_semantics(DexMethodRef* dex_method) {
    auto entry = m_method_semantics.find(dex_method);
    if (entry == m_method_semantics.end()) {
      return {};
    }
    return boost::optional<PointsToMethodSemantics*>(&entry->second);
  }
  
  MethodKind PointsToSemantics::default_method_kind() const {
    return m_generate_stubs ? PTS_STUB : PTS_APK;
  }
  
  void PointsToSemantics::initialize_entry(DexMethod* dex_method) {
    DexAccessFlags access_flags = dex_method->get_access();
    MethodKind kind;
    if (dex_method->get_code() == nullptr) {
      if ((access_flags & DexAccessFlags::ACC_ABSTRACT)) {
        kind = PTS_ABSTRACT;
      } else if ((access_flags & DexAccessFlags::ACC_NATIVE)) {
        kind = PTS_NATIVE;
      } else {
        // The definition of a method that is neither abstract nor native should
        // always have an associated IRCode component.
        always_assert_log(false,
                          "Method %s has no associated code component",
                          SHOW(dex_method->get_name()));
      }
    } else {
      kind = default_method_kind();
    }
    m_method_semantics.emplace(std::piecewise_construct,
                               std::forward_as_tuple(dex_method),
                               std::forward_as_tuple(/* dex_method */ dex_method,
                                                     /* kind */ kind,
                                                     /* start_var_id */ 0,
                                                     /* size_hint */ 8));
  }
  
  void PointsToSemantics::generate_points_to_actions(DexMethod* dex_method) {
    // According to section [container.requirements.dataraces] of the C++ standard
    // definition document, the find() method of std::unordered_map is
    // thread-safe. Since this function operates on a single Dex method and the
    // hash table m_method_semantics is indexed by Dex methods, the following code
    // is not subject to data races.
    auto entry = m_method_semantics.find(dex_method);
    // All hash table entries have been initialized in the constructor.
    always_assert(entry != m_method_semantics.end());
    PointsToMethodSemantics* semantics = &entry->second;
    if (semantics->kind() == default_method_kind()) {
      pts_impl::PointsToActionGenerator generator(
          dex_method, semantics, m_type_system, m_utils);
      generator.run();
    }
  }
  
  std::ostream& operator<<(std::ostream& o, const PointsToSemantics& s) {
    for (const auto& entry : s.m_method_semantics) {
      o << entry.second;
    }
    return o;
  }
  