<commit_before>/*
 * 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 "Inliner.h"

#include <utility>

#include "ApiLevelChecker.h"
#include "CFGInliner.h"
#include "ConcurrentContainers.h"
#include "ConstantPropagationAnalysis.h"
#include "ConstantPropagationWholeProgramState.h"
#include "ConstructorAnalysis.h"
#include "ControlFlow.h"
#include "DexUtil.h"
#include "EditableCfgAdapter.h"
#include "IRInstruction.h"
#include "InlineForSpeed.h"
#include "LocalDce.h"
#include "MethodProfiles.h"
#include "Mutators.h"
#include "OptData.h"
#include "Purity.h"
#include "Resolver.h"
#include "Timer.h"
#include "Transform.h"
#include "UnknownVirtuals.h"
#include "Walkers.h"
#include "WorkQueue.h"

using namespace opt_metadata;

namespace {

// The following costs are in terms of code-units (2 bytes).

// Typical overhead of calling a method with a result. This isn't just the
// overhead of the invoke instruction itself, but possibly some setup and
// consumption of result.
const size_t COST_INVOKE_WITH_RESULT = 5;

// Typical overhead of calling a method without a result.
const size_t COST_INVOKE_WITHOUT_RESULT = 3;

// Overhead of having a method and its metadata.
const size_t COST_METHOD = 16;

// When to consider running constant-propagation to better estimate inlined
// cost. It just takes too much time to run the analysis for large methods.
const size_t MAX_COST_FOR_CONSTANT_PROPAGATION = 272;

// Minimum number of instructions needed across all constant arguments
// variations before parallelizing constant-propagation.
const size_t MIN_COST_FOR_PARALLELIZATION = 1977;

/*
 * This is the maximum size of method that Dex bytecode can encode.
 * The table of instructions is indexed by a 32 bit unsigned integer.
 */
constexpr uint64_t HARD_MAX_INSTRUCTION_SIZE = 1L << 32;

/*
 * Some versions of ART (5.0.0 - 5.0.2) will fail to verify a method if it
 * is too large. See https://code.google.com/p/android/issues/detail?id=66655.
 *
 * The verifier rounds up to the next power of two, and doesn't support any
 * size greater than 16. See
 * http://androidxref.com/5.0.0_r2/xref/art/compiler/dex/verified_method.cc#107
 */
constexpr uint32_t SOFT_MAX_INSTRUCTION_SIZE = 1 << 15;
constexpr uint32_t INSTRUCTION_BUFFER = 1 << 12;

} // namespace

MultiMethodInliner::MultiMethodInliner(
    const std::vector<DexClass*>& scope,
    DexStoresVector& stores,
    const std::unordered_set<DexMethod*>& candidates,
    std::function<DexMethod*(DexMethodRef*, MethodSearch)> resolve_fn,
    const inliner::InlinerConfig& config,
    MultiMethodInlinerMode mode /* default is InterDex */,
    const CalleeCallerInsns& true_virtual_callers,
    const method_profiles::MethodProfiles* method_profiles,
    const std::unordered_map<const DexMethod*, size_t>*
        same_method_implementations,
    bool analyze_and_prune_inits,
    const std::unordered_set<DexMethodRef*>& configured_pure_methods)
    : resolver(std::move(resolve_fn)),
      xstores(stores),
      m_scope(scope),
      m_config(config),
      m_mode(mode),
      m_inline_for_speed(method_profiles),
      m_same_method_implementations(same_method_implementations),
      m_pure_methods(get_pure_methods()),
      m_analyze_and_prune_inits(analyze_and_prune_inits) {
  for (const auto& callee_callers : true_virtual_callers) {
    for (const auto& caller_insns : callee_callers.second) {
      for (auto insn : caller_insns.second) {
        caller_virtual_callee[caller_insns.first][insn] = callee_callers.first;
      }
    }
  }
  // Walk every opcode in scope looking for calls to inlinable candidates and
  // build a map of callers to callees and the reverse callees to callers. If
  // intra_dex is false, we build the map for all the candidates. If intra_dex
  // is true, we properly exclude methods who have callers being located in
  // another dex from the candidates.
  if (mode == IntraDex) {
    std::unordered_set<DexMethod*> candidate_callees(candidates.begin(),
                                                     candidates.end());
    XDexRefs x_dex(stores);
    walk::opcodes(scope, [](DexMethod* caller) { return true; },
                  [&](DexMethod* caller, IRInstruction* insn) {
                    if (is_invoke(insn->opcode())) {
                      auto callee =
                          resolver(insn->get_method(), opcode_to_search(insn));
                      if (callee != nullptr && callee->is_concrete() &&
                          candidate_callees.count(callee) &&
                          true_virtual_callers.count(callee) == 0) {
                        if (x_dex.cross_dex_ref(caller, callee)) {
                          candidate_callees.erase(callee);
                          if (callee_caller.count(callee)) {
                            callee_caller.erase(callee);
                          }
                        } else {
                          callee_caller[callee].push_back(caller);
                        }
                      }
                    }
                  });
    for (const auto& callee_callers : true_virtual_callers) {
      auto callee = callee_callers.first;
      for (const auto& caller_insns : callee_callers.second) {
        auto caller = caller_insns.first;
        if (x_dex.cross_dex_ref(callee, caller)) {
          callee_caller.erase(callee);
          break;
        }
        callee_caller[callee].push_back(caller);
      }
    }
    for (auto& pair : callee_caller) {
      DexMethod* callee = const_cast<DexMethod*>(pair.first);
      const auto& callers = pair.second;
      for (auto caller : callers) {
        caller_callee[caller].push_back(callee);
      }
    }
  } else if (mode == InterDex) {
    walk::opcodes(
        scope, [](DexMethod* caller) { return true; },
        [&](DexMethod* caller, IRInstruction* insn) {
          if (is_invoke(insn->opcode())) {
            auto callee = resolver(insn->get_method(), opcode_to_search(insn));
            if (true_virtual_callers.count(callee) == 0 && callee != nullptr &&
                callee->is_concrete() && candidates.count(callee)) {
              callee_caller[callee].push_back(caller);
              caller_callee[caller].push_back(callee);
            }
          }
        });
    for (const auto& callee_callers : true_virtual_callers) {
      auto callee = callee_callers.first;
      for (const auto& caller_insns : callee_callers.second) {
        auto caller = caller_insns.first;
        callee_caller[callee].push_back(caller);
        caller_callee[caller].push_back(callee);
      }
    }
  }

  m_shrinking_enabled = m_config.run_const_prop || m_config.run_cse ||
                        m_config.run_copy_prop || m_config.run_local_dce ||
                        m_config.run_dedup_blocks;

  if (m_config.run_cse || m_config.run_local_dce) {
    m_pure_methods.insert(configured_pure_methods.begin(),
                          configured_pure_methods.end());
    auto rstate_pure_method = get_rstate_pure_methods(scope);
    m_pure_methods.insert(rstate_pure_method.begin(), rstate_pure_method.end());
    if (m_config.run_cse) {
      m_cse_shared_state =
          std::make_unique<cse_impl::SharedState>(m_pure_methods);
    }
    if (m_config.run_local_dce) {
      std::unique_ptr<const method_override_graph::Graph> owned_override_graph;
      const method_override_graph::Graph* override_graph;
      if (m_config.run_cse) {
        override_graph = m_cse_shared_state->get_method_override_graph();
      } else {
        owned_override_graph = method_override_graph::build_graph(scope);
        override_graph = owned_override_graph.get();
      }
      std::unordered_set<const DexMethod*> computed_no_side_effects_methods;
      auto computed_no_side_effects_methods_iterations =
          compute_no_side_effects_methods(scope, override_graph, m_pure_methods,
                                          &computed_no_side_effects_methods);
      for (auto m : computed_no_side_effects_methods) {
        m_pure_methods.insert(const_cast<DexMethod*>(m));
      }
    }
  }
}

/*
 * The key of a constant-arguments data structure is a string representation
 * that approximates the constant arguments.
 */
static std::string get_key(const ConstantArguments& constant_arguments) {
  always_assert(!constant_arguments.is_bottom());
  if (constant_arguments.is_top()) {
    return "";
  }
  // We'll normalize the order by putting things into a std::map
  std::map<reg_t, SignedConstantDomain> bindings;
  for (auto& p : constant_arguments.bindings()) {
    always_assert(!p.second.is_top());
    if (const auto& signed_value = p.second.maybe_get<SignedConstantDomain>()) {
      bindings.emplace(p.first, *signed_value);
    }
  }
  std::ostringstream oss;
  for (auto& p : bindings) {
    if (p.first != bindings.begin()->first) {
      oss << ",";
    }
    oss << p.first << ":";
    auto& d = p.second;
    if (d.get_constant()) {
      oss << *d.get_constant();
    } else {
      oss << d.interval();
    }
  }
  return oss.str();
}

void MultiMethodInliner::compute_callee_constant_arguments() {
  if (!m_config.use_constant_propagation_for_callee_size) {
    return;
  }

  Timer t("compute_callee_constant_arguments");
  struct CalleeInfo {
    std::unordered_map<std::string, ConstantArguments> constant_arguments;
    std::unordered_map<std::string, size_t> occurrences;
  };
  ConcurrentMap<DexMethod*, CalleeInfo> concurrent_callee_constant_arguments;
  auto wq = workqueue_foreach<DexMethod*>(
      [&](DexMethod* caller) {
        auto& callees = caller_callee.at(caller);
        auto res = get_invoke_constant_arguments(caller, callees);
        if (!res) {
          return;
        }
        for (auto& p : res->invoke_constant_arguments) {
          auto insn = p.first->insn;
          auto callee = resolver(insn->get_method(), opcode_to_search(insn));
          const auto& constant_arguments = p.second;
          auto key = get_key(constant_arguments);
          concurrent_callee_constant_arguments.update(
              callee, [&](const DexMethod*, CalleeInfo& ci, bool /* exists */) {
                ci.constant_arguments.emplace(key, constant_arguments);
                ++ci.occurrences[key];
              });
          m_call_constant_arguments.emplace(insn, constant_arguments);
        }
        info.constant_invoke_callers_analyzed++;
        info.constant_invoke_callers_unreachable_blocks += res->dead_blocks;
      },
      redex_parallel::default_num_threads());
  for (auto& p : caller_callee) {
    wq.add_item(p.first);
  };
  wq.run_all();
  for (auto& p : concurrent_callee_constant_arguments) {
    auto& v = m_callee_constant_arguments[p.first];
    const auto& ci = p.second;
    for (const auto& q : ci.occurrences) {
      const auto& key = q.first;
      const auto& constant_arguments = q.second;
      v.emplace_back(ci.constant_arguments.at(key), constant_arguments);
    }
  }
}

void MultiMethodInliner::inline_methods() {
  compute_callee_constant_arguments();

  // Inlining and shrinking initiated from within this method will be done
  // in parallel.
  m_async_method_executor.set_num_threads(
      m_config.debug ? 1 : redex_parallel::default_num_threads());

  // The order in which we inline is such that once a callee is considered to
  // be inlined, it's code will no longer change. So we can cache...
  // - its size
  // - its set of type refs
  // - its set of method refs
  // - whether all callers are in the same class, and are called from how many
  //   classes
  m_callee_insn_sizes =
      std::make_unique<ConcurrentMap<const DexMethod*, size_t>>();
  m_callee_type_refs = std::make_unique<
      ConcurrentMap<const DexMethod*, std::vector<DexType*>>>();
  m_callee_method_refs =
      std::make_unique<ConcurrentMap<const DexMethod*, size_t>>();
  m_callee_caller_refs =
      std::make_unique<ConcurrentMap<const DexMethod*, CalleeCallerRefs>>();

  // Instead of changing visibility as we inline, blocking other work on the
  // critical path, we do it all in parallel at the end.
  m_delayed_change_visibilities = std::make_unique<
      ConcurrentMap<DexMethod*, std::unordered_set<DexType*>>>();

  // we want to inline bottom up, so as a first step we identify all the
  // top level callers, then we recurse into all inlinable callees until we
  // hit a leaf and we start inlining from there.
  // First, we just gather data on caller/non-recursive-callees pairs for each
  // stack depth.
  std::unordered_map<DexMethod*, size_t> visited;
  CallerNonrecursiveCalleesByStackDepth
      caller_nonrecursive_callees_by_stack_depth;
  for (const auto& it : caller_callee) {
    auto caller = it.first;
    TraceContext context(caller->get_deobfuscated_name());
    // if the caller is not a top level keep going, it will be traversed
    // when inlining a top level caller
    if (callee_caller.find(caller) != callee_caller.end()) continue;
    sparta::PatriciaTreeSet<DexMethod*> call_stack;
    auto stack_depth = compute_caller_nonrecursive_callees_by_stack_depth(
        caller, it.second, call_stack, &visited,
        &caller_nonrecursive_callees_by_stack_depth);
    info.max_call_stack_depth =
        std::max(info.max_call_stack_depth, stack_depth);
  }

  std::vector<size_t> ordered_stack_depths;
  for (auto& p : caller_nonrecursive_callees_by_stack_depth) {
    ordered_stack_depths.push_back(p.first);
  }
  std::sort(ordered_stack_depths.begin(), ordered_stack_depths.end());

  // Second, compute caller priorities --- the callers get a priority assigned
  // that reflects how many other callers will be waiting for them.
  // We also compute the set of callers and some other auxiliary data structures
  // along the way.
  // TODO: Instead of just considering the length of the critical path as the
  // priority, consider some variations, e.g. include the fan-out of the
  // dependencies divided by the number of threads.
  for (int i = ((int)ordered_stack_depths.size()) - 1; i >= 0; i--) {
    auto stack_depth = ordered_stack_depths.at(i);
    auto& caller_nonrecursive_callees =
        caller_nonrecursive_callees_by_stack_depth.at(stack_depth);
    for (auto& p : caller_nonrecursive_callees) {
      auto caller = p.first;
      auto& callees = p.second;
      always_assert(!callees.empty());
      int caller_priority = 0;
      auto method_priorities_it = m_async_callee_priorities.find(caller);
      if (method_priorities_it != m_async_callee_priorities.end()) {
        caller_priority = method_priorities_it->second;
      }
      for (auto callee : callees) {
        auto& callee_priority = m_async_callee_priorities[callee];
        callee_priority = std::max(callee_priority, caller_priority + 1);
        m_async_callee_callers[callee].push_back(caller);
      }
      m_async_caller_wait_counts.emplace(caller, callees.size());
      m_async_caller_callees.emplace(caller, callees);
    }
  }
  for (auto& p : m_async_callee_callers) {
    auto callee = p.first;
    auto& callers = p.second;
    auto& callee_priority = m_async_callee_priorities[callee];
    info.critical_path_length =
        std::max(info.critical_path_length, callee_priority);
    callee_priority = (callee_priority << 16) + callers.size();
  }

  // Kick off (shrinking and) pre-computing the should-inline cache.
  // Once all callees of a caller have been processed, then postprocessing
  // will in turn kick off processing of the caller.
  for (auto& p : m_async_callee_priorities) {
    auto callee = p.first;
    auto priority = p.second;
    always_assert(priority > 0);
    if (m_async_caller_callees.count(callee) == 0) {
      async_postprocess_method(const_cast<DexMethod*>(callee));
    }
  }

  if (m_shrinking_enabled && m_config.shrink_other_methods) {
    walk::code(m_scope, [&](DexMethod* method, IRCode& code) {
      // If a method is not tracked as a caller, and not already in the
      // processing pool because it's a callee, then process it.
      if (m_async_caller_callees.count(method) == 0 &&
          m_async_callee_priorities.count(method) == 0) {
        async_postprocess_method(const_cast<DexMethod*>(method));
      }
    });
  }

  m_async_method_executor.join();
  delayed_change_visibilities();
  info.waited_seconds = m_async_method_executor.get_waited_seconds();
}

size_t MultiMethodInliner::compute_caller_nonrecursive_callees_by_stack_depth(
    DexMethod* caller,
    const std::vector<DexMethod*>& callees,
    sparta::PatriciaTreeSet<DexMethod*> call_stack,
    std::unordered_map<DexMethod*, size_t>* visited,
    CallerNonrecursiveCalleesByStackDepth*
        caller_nonrecursive_callees_by_stack_depth) {
  always_assert(!callees.empty());

  auto visited_it = visited->find(caller);
  if (visited_it != visited->end()) {
    return visited_it->second;
  }

  // We'll only know the exact call stack depth at the end.
  visited->emplace(caller, std::numeric_limits<size_t>::max());
  call_stack.insert(caller);

  std::vector<DexMethod*> nonrecursive_callees;
  nonrecursive_callees.reserve(callees.size());
  size_t stack_depth = 0;
  // recurse into the callees in case they have something to inline on
  // their own. We want to inline bottom up so that a callee is
  // completely resolved by the time it is inlined.
  for (auto callee : callees) {
    if (call_stack.contains(callee)) {
      // we've found recursion in the current call stack
      always_assert(visited->at(callee) == std::numeric_limits<size_t>::max());
      info.recursive++;
      continue;
    }
    size_t callee_stack_depth = 0;
    auto maybe_caller = caller_callee.find(callee);
    if (maybe_caller != caller_callee.end()) {
      callee_stack_depth = compute_caller_nonrecursive_callees_by_stack_depth(
          callee, maybe_caller->second, call_stack, visited,
          caller_nonrecursive_callees_by_stack_depth);
    }

    if (!for_speed()) {
      nonrecursive_callees.push_back(callee);
    } else if (m_inline_for_speed.should_inline(caller, callee)) {
      nonrecursive_callees.push_back(callee);
    }

    stack_depth = std::max(stack_depth, callee_stack_depth + 1);
  }

  (*visited)[caller] = stack_depth;
  if (!nonrecursive_callees.empty()) {
    (*caller_nonrecursive_callees_by_stack_depth)[stack_depth].push_back(
        std::make_pair(caller, nonrecursive_callees));
  }
  return stack_depth;
}

void MultiMethodInliner::caller_inline(
    DexMethod* caller, const std::vector<DexMethod*>& nonrecursive_callees) {
  // We select callees to inline into this caller
  std::vector<DexMethod*> selected_callees;
  std::vector<DexMethod*> optional_selected_callees;
  selected_callees.reserve(nonrecursive_callees.size());
  for (auto callee : nonrecursive_callees) {
    if (should_inline(callee)) {
      selected_callees.push_back(callee);
    } else {
      optional_selected_callees.push_back(callee);
    }
  }

  if (!selected_callees.empty() || !optional_selected_callees.empty()) {
    inline_callees(caller, selected_callees, optional_selected_callees);
  }
}

boost::optional<InvokeConstantArgumentsAndDeadBlocks>
MultiMethodInliner::get_invoke_constant_arguments(
    DexMethod* caller, const std::vector<DexMethod*>& callees) {
  IRCode* code = caller->get_code();
  if (!code->editable_cfg_built()) {
    return boost::none;
  }

  InvokeConstantArgumentsAndDeadBlocks res;
  std::unordered_set<DexMethod*> callees_set(callees.begin(), callees.end());
  auto& cfg = code->cfg();
  constant_propagation::intraprocedural::FixpointIterator intra_cp(
      cfg, constant_propagation::ConstantPrimitiveAnalyzer());
  auto initial_env = constant_propagation::interprocedural::env_with_params(
      is_static(caller), code, ConstantArguments());
  intra_cp.run(initial_env);
  for (const auto& block : cfg.blocks()) {
    auto env = intra_cp.get_entry_state_at(block);
    if (env.is_bottom()) {
      res.dead_blocks++;
      // we found an unreachable block; ignore invoke instructions in it
      continue;
    }
    auto last_insn = block->get_last_insn();
    for (auto& mie : InstructionIterable(block)) {
      auto insn = mie.insn;
      if (is_invoke(insn->opcode())) {
        auto callee = resolver(insn->get_method(), opcode_to_search(insn));
        if (callees_set.count(callee)) {
          ConstantArguments constant_arguments;
          const auto& srcs = insn->srcs();
          for (size_t i = is_static(callee) ? 0 : 1; i < srcs.size(); ++i) {
            auto val = env.get(srcs[i]);
            always_assert(!val.is_bottom());
            constant_arguments.set(i, val);
          }
          res.invoke_constant_arguments.emplace_back(code->iterator_to(mie),
                                                     constant_arguments);
        }
      }
      intra_cp.analyze_instruction(insn, &env, insn == last_insn->insn);
      if (env.is_bottom()) {
        // Can happen in the absence of throw edges when dereferencing null
        break;
      }
    }
  }

  return res;
}

void MultiMethodInliner::inline_callees(
    DexMethod* caller,
    const std::vector<DexMethod*>& callees,
    const std::vector<DexMethod*>& optional_callees) {
  size_t found = 0;

  // walk the caller opcodes collecting all candidates to inline
  // Build a callee to opcode map
  std::vector<Inlinable> inlinables;
  auto max = callees.size() + optional_callees.size();
  editable_cfg_adapter::iterate_with_iterator(
      caller->get_code(), [&](const IRList::iterator& it) {
        auto insn = it->insn;
        if (!is_invoke(insn->opcode())) {
          return editable_cfg_adapter::LOOP_CONTINUE;
        }
        auto callee = resolver(insn->get_method(), opcode_to_search(insn));
        if (caller_virtual_callee.count(caller) &&
            caller_virtual_callee[caller].count(insn)) {
          callee = caller_virtual_callee[caller][insn];
          always_assert(callee);
        }
        if (callee == nullptr) {
          return editable_cfg_adapter::LOOP_CONTINUE;
        }
        bool optional{false};
        if (std::find(callees.begin(), callees.end(), callee) ==
            callees.end()) {
          // If a callee wasn't in the list of general callees, that means that
          // it's not beneficial on average (across all callsites) to inline the
          // callee. However, let's see if it's beneficial for this particular
          // callsite, taking into account constant-arguments (if any).
          if (std::find(optional_callees.begin(), optional_callees.end(),
                        callee) != optional_callees.end() &&
              should_inline_optional(caller, insn, callee)) {
            optional = true;
          } else {
            return editable_cfg_adapter::LOOP_CONTINUE;
          }
        }
        always_assert(callee->is_concrete());
        if (m_analyze_and_prune_inits && method::is_init(callee)) {
          if (!callee->get_code()->editable_cfg_built()) {
            return editable_cfg_adapter::LOOP_CONTINUE;
          }
          if (!can_inline_init(callee)) {
            if (!method::is_init(caller) ||
                caller->get_class() != callee->get_class() ||
                !caller->get_code()->editable_cfg_built() ||
                !constructor_analysis::can_inline_inits_in_same_class(
                    caller, callee, insn)) {
              return editable_cfg_adapter::LOOP_CONTINUE;
            }
          }
        }

        inlinables.push_back((Inlinable){callee, it, insn, optional});
        if (++found == max) {
          return editable_cfg_adapter::LOOP_BREAK;
        }
        return editable_cfg_adapter::LOOP_CONTINUE;
      });
  if (found != max) {
    always_assert(found <= max);
    info.not_found += max - found;
  }

  if (!inlinables.empty()) {
    inline_inlinables(caller, inlinables);
  }
}

void MultiMethodInliner::inline_callees(
    DexMethod* caller, const std::unordered_set<IRInstruction*>& insns) {
  std::vector<Inlinable> inlinables;
  editable_cfg_adapter::iterate_with_iterator(
      caller->get_code(), [&](const IRList::iterator& it) {
        auto insn = it->insn;
        if (insns.count(insn)) {
          auto callee = resolver(insn->get_method(), opcode_to_search(insn));
          if (caller_virtual_callee.count(caller) &&
              caller_virtual_callee[caller].count(insn)) {
            callee = caller_virtual_callee[caller][insn];
          }
          if (callee == nullptr) {
            return editable_cfg_adapter::LOOP_CONTINUE;
          }
          always_assert(callee->is_concrete());
          inlinables.push_back((Inlinable){callee, it, insn});
        }
        return editable_cfg_adapter::LOOP_CONTINUE;
      });

  inline_inlinables(caller, inlinables);
}

bool MultiMethodInliner::inline_inlinables_need_deconstruct(DexMethod* method) {
  // The mixed CFG, IRCode is used by Switch Inline (only?) where the caller is
  // an IRCode and the callee is a CFG.
  return m_config.use_cfg_inliner && !method->get_code()->editable_cfg_built();
}

void MultiMethodInliner::inline_inlinables(
    DexMethod* caller_method, const std::vector<Inlinable>& inlinables) {

  auto caller = caller_method->get_code();
  std::unordered_set<IRCode*> need_deconstruct;
  if (inline_inlinables_need_deconstruct(caller_method)) {
    need_deconstruct.reserve(1 + inlinables.size());
    need_deconstruct.insert(caller);
    for (const auto& inlinable : inlinables) {
      need_deconstruct.insert(inlinable.callee->get_code());
    }
    for (auto code : need_deconstruct) {
      always_assert(!code->editable_cfg_built());
      code->build_cfg(/* editable */ true);
    }
  }

  // attempt to inline all inlinable candidates
  size_t estimated_insn_size = caller->editable_cfg_built()
                                   ? caller->cfg().sum_opcode_sizes()
                                   : caller->sum_opcode_sizes();

  // Prefer inlining smaller methods first, so that we are less likely to hit
  // overall size limit.
  std::vector<Inlinable> ordered_inlinables(inlinables.begin(),
                                            inlinables.end());

  std::stable_sort(ordered_inlinables.begin(), ordered_inlinables.end(),
                   [&](const Inlinable& a, const Inlinable& b) {
                     // First, prefer non-optional inlinables, as they were
                     // (potentially) selected with a global cost model, taking
                     // into account the savings achieved when eliminating all
                     // calls
                     if (a.optional != b.optional) {
                       return a.optional < b.optional;
                     }
                     // Second, prefer smaller methods, to avoid hitting size
                     // limits too soon
                     return get_callee_insn_size(a.callee) <
                            get_callee_insn_size(b.callee);
                   });

  std::vector<DexMethod*> inlined_callees;
  boost::optional<reg_t> cfg_next_caller_reg;
  if (m_config.use_cfg_inliner && !m_config.unique_inlined_registers) {
    cfg_next_caller_reg = caller->cfg().get_registers_size();
  }
  size_t calls_not_inlinable{0}, calls_not_inlined{0};
  for (const auto& inlinable : ordered_inlinables) {
    auto callee_method = inlinable.callee;
    auto callee = callee_method->get_code();
    auto callsite_insn = inlinable.insn;

    std::vector<DexMethod*> make_static;
    if (!is_inlinable(caller_method, callee_method, callsite_insn,
                      estimated_insn_size, &make_static)) {
      calls_not_inlinable++;
      continue;
    }
    // Only now, when are about actually inline the method, we'll record
    // the fact that we'll have to make some methods static.
    make_static_inlinable(make_static);

    TRACE(MMINL, 4, "inline %s (%d) in %s (%d)", SHOW(callee),
          caller->get_registers_size(), SHOW(caller),
          callee->get_registers_size());

    if (m_config.use_cfg_inliner) {
      if (m_config.unique_inlined_registers) {
        cfg_next_caller_reg = caller->cfg().get_registers_size();
      }
      bool success = inliner::inline_with_cfg(
          caller_method, callee_method, callsite_insn, *cfg_next_caller_reg);
      if (!success) {
        calls_not_inlined++;
        continue;
      }
    } else {
      // Logging before the call to inline_method to get the most relevant line
      // number near callsite before callsite gets replaced. Should be ok as
      // inline_method does not fail to inline.
      log_opt(INLINED, caller_method, callsite_insn);

      auto callsite = inlinable.iterator;
      always_assert(callsite->insn == callsite_insn);
      inliner::inline_method_unsafe(caller_method, caller, callee, callsite);
    }
    TRACE(INL, 2, "caller: %s\tcallee: %s", SHOW(caller), SHOW(callee));
    estimated_insn_size += get_callee_insn_size(callee_method);

    inlined_callees.push_back(callee_method);
  }

  if (!inlined_callees.empty()) {
    for (auto callee_method : inlined_callees) {
      if (m_delayed_change_visibilities) {
        m_delayed_change_visibilities->update(
            callee_method, [caller_method](const DexMethod*,
                                           std::unordered_set<DexType*>& value,
                                           bool /*exists*/) {
              value.insert(caller_method->get_class());
            });
      } else {
        std::lock_guard<std::mutex> guard(m_change_visibility_mutex);
        change_visibility(callee_method, caller_method->get_class());
      }
      m_inlined.insert(callee_method);
    }
  }

  for (IRCode* code : need_deconstruct) {
    code->clear_cfg();
  }

  info.calls_inlined += inlined_callees.size();
  if (calls_not_inlinable) {
    info.calls_not_inlinable += calls_not_inlinable;
  }
  if (calls_not_inlined) {
    info.calls_not_inlined += calls_not_inlined;
  }
}

void MultiMethodInliner::async_prioritized_method_execute(
    DexMethod* method, const std::function<void()>& f) {
  int priority = std::numeric_limits<int>::min();
  auto it = m_async_callee_priorities.find(method);
  if (it != m_async_callee_priorities.end()) {
    priority = it->second;
  }
  m_async_method_executor.post(priority, f);
}

void MultiMethodInliner::async_postprocess_method(DexMethod* method) {
  if (m_async_callee_priorities.count(method) == 0 &&
      (!m_shrinking_enabled || method->rstate.no_optimizations())) {
    return;
  }

  async_prioritized_method_execute(
      method, [method, this]() { postprocess_method(method); });
}

void MultiMethodInliner::shrink_method(DexMethod* method) {
  auto code = method->get_code();
  bool editable_cfg_built = code->editable_cfg_built();

  constant_propagation::Transform::Stats const_prop_stats;
  cse_impl::Stats cse_stats;
  copy_propagation_impl::Stats copy_prop_stats;
  LocalDce::Stats local_dce_stats;
  dedup_blocks_impl::Stats dedup_blocks_stats;

  if (m_config.run_const_prop) {
    if (editable_cfg_built) {
      code->clear_cfg();
    }
    if (!code->cfg_built()) {
      code->build_cfg(/* editable */ false);
    }
    {
      constant_propagation::intraprocedural::FixpointIterator fp_iter(
          code->cfg(), constant_propagation::ConstantPrimitiveAnalyzer());
      fp_iter.run(ConstantEnvironment());
      constant_propagation::Transform::Config config;
      constant_propagation::Transform tf(config);
      const_prop_stats = tf.apply_on_uneditable_cfg(
          fp_iter, constant_propagation::WholeProgramState(), code, &xstores,
          method->get_class());
    }
    always_assert(!code->editable_cfg_built());
    code->build_cfg(/* editable */ true);
    code->cfg().calculate_exit_block();
    {
      constant_propagation::intraprocedural::FixpointIterator fp_iter(
          code->cfg(), constant_propagation::ConstantPrimitiveAnalyzer());
      fp_iter.run(ConstantEnvironment());
      constant_propagation::Transform::Config config;
      constant_propagation::Transform tf(config);
      const_prop_stats += tf.apply(fp_iter, code->cfg(), method, &xstores);
    }
  }

  // The following default 'features' of copy propagation would only
  // interfere with what CSE is trying to do.
  copy_propagation_impl::Config copy_prop_config;
  copy_prop_config.eliminate_const_classes = false;
  copy_prop_config.eliminate_const_strings = false;
  copy_prop_config.static_finals = false;

  if (m_config.run_cse) {
    if (!code->editable_cfg_built()) {
      code->build_cfg(/* editable */ true);
    }

    cse_impl::CommonSubexpressionElimination cse(
        m_cse_shared_state.get(), code->cfg(), is_static(method),
        method::is_init(method) || method::is_clinit(method),
        method->get_class(), method->get_proto()->get_args());
    cse.patch();
    cse_stats = cse.get_stats();
  }

  if (m_config.run_copy_prop) {
    copy_propagation_impl::Config config;
    copy_propagation_impl::CopyPropagation copy_propagation(config);
    copy_prop_stats = copy_propagation.run(code, method);
  }

  if (m_config.run_local_dce) {
    // LocalDce doesn't care if editable_cfg_built
    auto local_dce = LocalDce(m_pure_methods);
    local_dce.dce(code);<commit_msg>Remove unused config from Inliner<commit_after>/*
 * 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 "Inliner.h"

#include <utility>

#include "ApiLevelChecker.h"
#include "CFGInliner.h"
#include "ConcurrentContainers.h"
#include "ConstantPropagationAnalysis.h"
#include "ConstantPropagationWholeProgramState.h"
#include "ConstructorAnalysis.h"
#include "ControlFlow.h"
#include "DexUtil.h"
#include "EditableCfgAdapter.h"
#include "IRInstruction.h"
#include "InlineForSpeed.h"
#include "LocalDce.h"
#include "MethodProfiles.h"
#include "Mutators.h"
#include "OptData.h"
#include "Purity.h"
#include "Resolver.h"
#include "Timer.h"
#include "Transform.h"
#include "UnknownVirtuals.h"
#include "Walkers.h"
#include "WorkQueue.h"

using namespace opt_metadata;

namespace {

// The following costs are in terms of code-units (2 bytes).

// Typical overhead of calling a method with a result. This isn't just the
// overhead of the invoke instruction itself, but possibly some setup and
// consumption of result.
const size_t COST_INVOKE_WITH_RESULT = 5;

// Typical overhead of calling a method without a result.
const size_t COST_INVOKE_WITHOUT_RESULT = 3;

// Overhead of having a method and its metadata.
const size_t COST_METHOD = 16;

// When to consider running constant-propagation to better estimate inlined
// cost. It just takes too much time to run the analysis for large methods.
const size_t MAX_COST_FOR_CONSTANT_PROPAGATION = 272;

// Minimum number of instructions needed across all constant arguments
// variations before parallelizing constant-propagation.
const size_t MIN_COST_FOR_PARALLELIZATION = 1977;

/*
 * This is the maximum size of method that Dex bytecode can encode.
 * The table of instructions is indexed by a 32 bit unsigned integer.
 */
constexpr uint64_t HARD_MAX_INSTRUCTION_SIZE = 1L << 32;

/*
 * Some versions of ART (5.0.0 - 5.0.2) will fail to verify a method if it
 * is too large. See https://code.google.com/p/android/issues/detail?id=66655.
 *
 * The verifier rounds up to the next power of two, and doesn't support any
 * size greater than 16. See
 * http://androidxref.com/5.0.0_r2/xref/art/compiler/dex/verified_method.cc#107
 */
constexpr uint32_t SOFT_MAX_INSTRUCTION_SIZE = 1 << 15;
constexpr uint32_t INSTRUCTION_BUFFER = 1 << 12;

} // namespace

MultiMethodInliner::MultiMethodInliner(
    const std::vector<DexClass*>& scope,
    DexStoresVector& stores,
    const std::unordered_set<DexMethod*>& candidates,
    std::function<DexMethod*(DexMethodRef*, MethodSearch)> resolve_fn,
    const inliner::InlinerConfig& config,
    MultiMethodInlinerMode mode /* default is InterDex */,
    const CalleeCallerInsns& true_virtual_callers,
    const method_profiles::MethodProfiles* method_profiles,
    const std::unordered_map<const DexMethod*, size_t>*
        same_method_implementations,
    bool analyze_and_prune_inits,
    const std::unordered_set<DexMethodRef*>& configured_pure_methods)
    : resolver(std::move(resolve_fn)),
      xstores(stores),
      m_scope(scope),
      m_config(config),
      m_mode(mode),
      m_inline_for_speed(method_profiles),
      m_same_method_implementations(same_method_implementations),
      m_pure_methods(get_pure_methods()),
      m_analyze_and_prune_inits(analyze_and_prune_inits) {
  for (const auto& callee_callers : true_virtual_callers) {
    for (const auto& caller_insns : callee_callers.second) {
      for (auto insn : caller_insns.second) {
        caller_virtual_callee[caller_insns.first][insn] = callee_callers.first;
      }
    }
  }
  // Walk every opcode in scope looking for calls to inlinable candidates and
  // build a map of callers to callees and the reverse callees to callers. If
  // intra_dex is false, we build the map for all the candidates. If intra_dex
  // is true, we properly exclude methods who have callers being located in
  // another dex from the candidates.
  if (mode == IntraDex) {
    std::unordered_set<DexMethod*> candidate_callees(candidates.begin(),
                                                     candidates.end());
    XDexRefs x_dex(stores);
    walk::opcodes(scope, [](DexMethod* caller) { return true; },
                  [&](DexMethod* caller, IRInstruction* insn) {
                    if (is_invoke(insn->opcode())) {
                      auto callee =
                          resolver(insn->get_method(), opcode_to_search(insn));
                      if (callee != nullptr && callee->is_concrete() &&
                          candidate_callees.count(callee) &&
                          true_virtual_callers.count(callee) == 0) {
                        if (x_dex.cross_dex_ref(caller, callee)) {
                          candidate_callees.erase(callee);
                          if (callee_caller.count(callee)) {
                            callee_caller.erase(callee);
                          }
                        } else {
                          callee_caller[callee].push_back(caller);
                        }
                      }
                    }
                  });
    for (const auto& callee_callers : true_virtual_callers) {
      auto callee = callee_callers.first;
      for (const auto& caller_insns : callee_callers.second) {
        auto caller = caller_insns.first;
        if (x_dex.cross_dex_ref(callee, caller)) {
          callee_caller.erase(callee);
          break;
        }
        callee_caller[callee].push_back(caller);
      }
    }
    for (auto& pair : callee_caller) {
      DexMethod* callee = const_cast<DexMethod*>(pair.first);
      const auto& callers = pair.second;
      for (auto caller : callers) {
        caller_callee[caller].push_back(callee);
      }
    }
  } else if (mode == InterDex) {
    walk::opcodes(
        scope, [](DexMethod* caller) { return true; },
        [&](DexMethod* caller, IRInstruction* insn) {
          if (is_invoke(insn->opcode())) {
            auto callee = resolver(insn->get_method(), opcode_to_search(insn));
            if (true_virtual_callers.count(callee) == 0 && callee != nullptr &&
                callee->is_concrete() && candidates.count(callee)) {
              callee_caller[callee].push_back(caller);
              caller_callee[caller].push_back(callee);
            }
          }
        });
    for (const auto& callee_callers : true_virtual_callers) {
      auto callee = callee_callers.first;
      for (const auto& caller_insns : callee_callers.second) {
        auto caller = caller_insns.first;
        callee_caller[callee].push_back(caller);
        caller_callee[caller].push_back(callee);
      }
    }
  }

  m_shrinking_enabled = m_config.run_const_prop || m_config.run_cse ||
                        m_config.run_copy_prop || m_config.run_local_dce ||
                        m_config.run_dedup_blocks;

  if (m_config.run_cse || m_config.run_local_dce) {
    m_pure_methods.insert(configured_pure_methods.begin(),
                          configured_pure_methods.end());
    auto rstate_pure_method = get_rstate_pure_methods(scope);
    m_pure_methods.insert(rstate_pure_method.begin(), rstate_pure_method.end());
    if (m_config.run_cse) {
      m_cse_shared_state =
          std::make_unique<cse_impl::SharedState>(m_pure_methods);
    }
    if (m_config.run_local_dce) {
      std::unique_ptr<const method_override_graph::Graph> owned_override_graph;
      const method_override_graph::Graph* override_graph;
      if (m_config.run_cse) {
        override_graph = m_cse_shared_state->get_method_override_graph();
      } else {
        owned_override_graph = method_override_graph::build_graph(scope);
        override_graph = owned_override_graph.get();
      }
      std::unordered_set<const DexMethod*> computed_no_side_effects_methods;
      auto computed_no_side_effects_methods_iterations =
          compute_no_side_effects_methods(scope, override_graph, m_pure_methods,
                                          &computed_no_side_effects_methods);
      for (auto m : computed_no_side_effects_methods) {
        m_pure_methods.insert(const_cast<DexMethod*>(m));
      }
    }
  }
}

/*
 * The key of a constant-arguments data structure is a string representation
 * that approximates the constant arguments.
 */
static std::string get_key(const ConstantArguments& constant_arguments) {
  always_assert(!constant_arguments.is_bottom());
  if (constant_arguments.is_top()) {
    return "";
  }
  // We'll normalize the order by putting things into a std::map
  std::map<reg_t, SignedConstantDomain> bindings;
  for (auto& p : constant_arguments.bindings()) {
    always_assert(!p.second.is_top());
    if (const auto& signed_value = p.second.maybe_get<SignedConstantDomain>()) {
      bindings.emplace(p.first, *signed_value);
    }
  }
  std::ostringstream oss;
  for (auto& p : bindings) {
    if (p.first != bindings.begin()->first) {
      oss << ",";
    }
    oss << p.first << ":";
    auto& d = p.second;
    if (d.get_constant()) {
      oss << *d.get_constant();
    } else {
      oss << d.interval();
    }
  }
  return oss.str();
}

void MultiMethodInliner::compute_callee_constant_arguments() {
  if (!m_config.use_constant_propagation_for_callee_size) {
    return;
  }

  Timer t("compute_callee_constant_arguments");
  struct CalleeInfo {
    std::unordered_map<std::string, ConstantArguments> constant_arguments;
    std::unordered_map<std::string, size_t> occurrences;
  };
  ConcurrentMap<DexMethod*, CalleeInfo> concurrent_callee_constant_arguments;
  auto wq = workqueue_foreach<DexMethod*>(
      [&](DexMethod* caller) {
        auto& callees = caller_callee.at(caller);
        auto res = get_invoke_constant_arguments(caller, callees);
        if (!res) {
          return;
        }
        for (auto& p : res->invoke_constant_arguments) {
          auto insn = p.first->insn;
          auto callee = resolver(insn->get_method(), opcode_to_search(insn));
          const auto& constant_arguments = p.second;
          auto key = get_key(constant_arguments);
          concurrent_callee_constant_arguments.update(
              callee, [&](const DexMethod*, CalleeInfo& ci, bool /* exists */) {
                ci.constant_arguments.emplace(key, constant_arguments);
                ++ci.occurrences[key];
              });
          m_call_constant_arguments.emplace(insn, constant_arguments);
        }
        info.constant_invoke_callers_analyzed++;
        info.constant_invoke_callers_unreachable_blocks += res->dead_blocks;
      },
      redex_parallel::default_num_threads());
  for (auto& p : caller_callee) {
    wq.add_item(p.first);
  };
  wq.run_all();
  for (auto& p : concurrent_callee_constant_arguments) {
    auto& v = m_callee_constant_arguments[p.first];
    const auto& ci = p.second;
    for (const auto& q : ci.occurrences) {
      const auto& key = q.first;
      const auto& constant_arguments = q.second;
      v.emplace_back(ci.constant_arguments.at(key), constant_arguments);
    }
  }
}

void MultiMethodInliner::inline_methods() {
  compute_callee_constant_arguments();

  // Inlining and shrinking initiated from within this method will be done
  // in parallel.
  m_async_method_executor.set_num_threads(
      m_config.debug ? 1 : redex_parallel::default_num_threads());

  // The order in which we inline is such that once a callee is considered to
  // be inlined, it's code will no longer change. So we can cache...
  // - its size
  // - its set of type refs
  // - its set of method refs
  // - whether all callers are in the same class, and are called from how many
  //   classes
  m_callee_insn_sizes =
      std::make_unique<ConcurrentMap<const DexMethod*, size_t>>();
  m_callee_type_refs = std::make_unique<
      ConcurrentMap<const DexMethod*, std::vector<DexType*>>>();
  m_callee_method_refs =
      std::make_unique<ConcurrentMap<const DexMethod*, size_t>>();
  m_callee_caller_refs =
      std::make_unique<ConcurrentMap<const DexMethod*, CalleeCallerRefs>>();

  // Instead of changing visibility as we inline, blocking other work on the
  // critical path, we do it all in parallel at the end.
  m_delayed_change_visibilities = std::make_unique<
      ConcurrentMap<DexMethod*, std::unordered_set<DexType*>>>();

  // we want to inline bottom up, so as a first step we identify all the
  // top level callers, then we recurse into all inlinable callees until we
  // hit a leaf and we start inlining from there.
  // First, we just gather data on caller/non-recursive-callees pairs for each
  // stack depth.
  std::unordered_map<DexMethod*, size_t> visited;
  CallerNonrecursiveCalleesByStackDepth
      caller_nonrecursive_callees_by_stack_depth;
  for (const auto& it : caller_callee) {
    auto caller = it.first;
    TraceContext context(caller->get_deobfuscated_name());
    // if the caller is not a top level keep going, it will be traversed
    // when inlining a top level caller
    if (callee_caller.find(caller) != callee_caller.end()) continue;
    sparta::PatriciaTreeSet<DexMethod*> call_stack;
    auto stack_depth = compute_caller_nonrecursive_callees_by_stack_depth(
        caller, it.second, call_stack, &visited,
        &caller_nonrecursive_callees_by_stack_depth);
    info.max_call_stack_depth =
        std::max(info.max_call_stack_depth, stack_depth);
  }

  std::vector<size_t> ordered_stack_depths;
  for (auto& p : caller_nonrecursive_callees_by_stack_depth) {
    ordered_stack_depths.push_back(p.first);
  }
  std::sort(ordered_stack_depths.begin(), ordered_stack_depths.end());

  // Second, compute caller priorities --- the callers get a priority assigned
  // that reflects how many other callers will be waiting for them.
  // We also compute the set of callers and some other auxiliary data structures
  // along the way.
  // TODO: Instead of just considering the length of the critical path as the
  // priority, consider some variations, e.g. include the fan-out of the
  // dependencies divided by the number of threads.
  for (int i = ((int)ordered_stack_depths.size()) - 1; i >= 0; i--) {
    auto stack_depth = ordered_stack_depths.at(i);
    auto& caller_nonrecursive_callees =
        caller_nonrecursive_callees_by_stack_depth.at(stack_depth);
    for (auto& p : caller_nonrecursive_callees) {
      auto caller = p.first;
      auto& callees = p.second;
      always_assert(!callees.empty());
      int caller_priority = 0;
      auto method_priorities_it = m_async_callee_priorities.find(caller);
      if (method_priorities_it != m_async_callee_priorities.end()) {
        caller_priority = method_priorities_it->second;
      }
      for (auto callee : callees) {
        auto& callee_priority = m_async_callee_priorities[callee];
        callee_priority = std::max(callee_priority, caller_priority + 1);
        m_async_callee_callers[callee].push_back(caller);
      }
      m_async_caller_wait_counts.emplace(caller, callees.size());
      m_async_caller_callees.emplace(caller, callees);
    }
  }
  for (auto& p : m_async_callee_callers) {
    auto callee = p.first;
    auto& callers = p.second;
    auto& callee_priority = m_async_callee_priorities[callee];
    info.critical_path_length =
        std::max(info.critical_path_length, callee_priority);
    callee_priority = (callee_priority << 16) + callers.size();
  }

  // Kick off (shrinking and) pre-computing the should-inline cache.
  // Once all callees of a caller have been processed, then postprocessing
  // will in turn kick off processing of the caller.
  for (auto& p : m_async_callee_priorities) {
    auto callee = p.first;
    auto priority = p.second;
    always_assert(priority > 0);
    if (m_async_caller_callees.count(callee) == 0) {
      async_postprocess_method(const_cast<DexMethod*>(callee));
    }
  }

  if (m_shrinking_enabled && m_config.shrink_other_methods) {
    walk::code(m_scope, [&](DexMethod* method, IRCode& code) {
      // If a method is not tracked as a caller, and not already in the
      // processing pool because it's a callee, then process it.
      if (m_async_caller_callees.count(method) == 0 &&
          m_async_callee_priorities.count(method) == 0) {
        async_postprocess_method(const_cast<DexMethod*>(method));
      }
    });
  }

  m_async_method_executor.join();
  delayed_change_visibilities();
  info.waited_seconds = m_async_method_executor.get_waited_seconds();
}

size_t MultiMethodInliner::compute_caller_nonrecursive_callees_by_stack_depth(
    DexMethod* caller,
    const std::vector<DexMethod*>& callees,
    sparta::PatriciaTreeSet<DexMethod*> call_stack,
    std::unordered_map<DexMethod*, size_t>* visited,
    CallerNonrecursiveCalleesByStackDepth*
        caller_nonrecursive_callees_by_stack_depth) {
  always_assert(!callees.empty());

  auto visited_it = visited->find(caller);
  if (visited_it != visited->end()) {
    return visited_it->second;
  }

  // We'll only know the exact call stack depth at the end.
  visited->emplace(caller, std::numeric_limits<size_t>::max());
  call_stack.insert(caller);

  std::vector<DexMethod*> nonrecursive_callees;
  nonrecursive_callees.reserve(callees.size());
  size_t stack_depth = 0;
  // recurse into the callees in case they have something to inline on
  // their own. We want to inline bottom up so that a callee is
  // completely resolved by the time it is inlined.
  for (auto callee : callees) {
    if (call_stack.contains(callee)) {
      // we've found recursion in the current call stack
      always_assert(visited->at(callee) == std::numeric_limits<size_t>::max());
      info.recursive++;
      continue;
    }
    size_t callee_stack_depth = 0;
    auto maybe_caller = caller_callee.find(callee);
    if (maybe_caller != caller_callee.end()) {
      callee_stack_depth = compute_caller_nonrecursive_callees_by_stack_depth(
          callee, maybe_caller->second, call_stack, visited,
          caller_nonrecursive_callees_by_stack_depth);
    }

    if (!for_speed()) {
      nonrecursive_callees.push_back(callee);
    } else if (m_inline_for_speed.should_inline(caller, callee)) {
      nonrecursive_callees.push_back(callee);
    }

    stack_depth = std::max(stack_depth, callee_stack_depth + 1);
  }

  (*visited)[caller] = stack_depth;
  if (!nonrecursive_callees.empty()) {
    (*caller_nonrecursive_callees_by_stack_depth)[stack_depth].push_back(
        std::make_pair(caller, nonrecursive_callees));
  }
  return stack_depth;
}

void MultiMethodInliner::caller_inline(
    DexMethod* caller, const std::vector<DexMethod*>& nonrecursive_callees) {
  // We select callees to inline into this caller
  std::vector<DexMethod*> selected_callees;
  std::vector<DexMethod*> optional_selected_callees;
  selected_callees.reserve(nonrecursive_callees.size());
  for (auto callee : nonrecursive_callees) {
    if (should_inline(callee)) {
      selected_callees.push_back(callee);
    } else {
      optional_selected_callees.push_back(callee);
    }
  }

  if (!selected_callees.empty() || !optional_selected_callees.empty()) {
    inline_callees(caller, selected_callees, optional_selected_callees);
  }
}

boost::optional<InvokeConstantArgumentsAndDeadBlocks>
MultiMethodInliner::get_invoke_constant_arguments(
    DexMethod* caller, const std::vector<DexMethod*>& callees) {
  IRCode* code = caller->get_code();
  if (!code->editable_cfg_built()) {
    return boost::none;
  }

  InvokeConstantArgumentsAndDeadBlocks res;
  std::unordered_set<DexMethod*> callees_set(callees.begin(), callees.end());
  auto& cfg = code->cfg();
  constant_propagation::intraprocedural::FixpointIterator intra_cp(
      cfg, constant_propagation::ConstantPrimitiveAnalyzer());
  auto initial_env = constant_propagation::interprocedural::env_with_params(
      is_static(caller), code, ConstantArguments());
  intra_cp.run(initial_env);
  for (const auto& block : cfg.blocks()) {
    auto env = intra_cp.get_entry_state_at(block);
    if (env.is_bottom()) {
      res.dead_blocks++;
      // we found an unreachable block; ignore invoke instructions in it
      continue;
    }
    auto last_insn = block->get_last_insn();
    for (auto& mie : InstructionIterable(block)) {
      auto insn = mie.insn;
      if (is_invoke(insn->opcode())) {
        auto callee = resolver(insn->get_method(), opcode_to_search(insn));
        if (callees_set.count(callee)) {
          ConstantArguments constant_arguments;
          const auto& srcs = insn->srcs();
          for (size_t i = is_static(callee) ? 0 : 1; i < srcs.size(); ++i) {
            auto val = env.get(srcs[i]);
            always_assert(!val.is_bottom());
            constant_arguments.set(i, val);
          }
          res.invoke_constant_arguments.emplace_back(code->iterator_to(mie),
                                                     constant_arguments);
        }
      }
      intra_cp.analyze_instruction(insn, &env, insn == last_insn->insn);
      if (env.is_bottom()) {
        // Can happen in the absence of throw edges when dereferencing null
        break;
      }
    }
  }

  return res;
}

void MultiMethodInliner::inline_callees(
    DexMethod* caller,
    const std::vector<DexMethod*>& callees,
    const std::vector<DexMethod*>& optional_callees) {
  size_t found = 0;

  // walk the caller opcodes collecting all candidates to inline
  // Build a callee to opcode map
  std::vector<Inlinable> inlinables;
  auto max = callees.size() + optional_callees.size();
  editable_cfg_adapter::iterate_with_iterator(
      caller->get_code(), [&](const IRList::iterator& it) {
        auto insn = it->insn;
        if (!is_invoke(insn->opcode())) {
          return editable_cfg_adapter::LOOP_CONTINUE;
        }
        auto callee = resolver(insn->get_method(), opcode_to_search(insn));
        if (caller_virtual_callee.count(caller) &&
            caller_virtual_callee[caller].count(insn)) {
          callee = caller_virtual_callee[caller][insn];
          always_assert(callee);
        }
        if (callee == nullptr) {
          return editable_cfg_adapter::LOOP_CONTINUE;
        }
        bool optional{false};
        if (std::find(callees.begin(), callees.end(), callee) ==
            callees.end()) {
          // If a callee wasn't in the list of general callees, that means that
          // it's not beneficial on average (across all callsites) to inline the
          // callee. However, let's see if it's beneficial for this particular
          // callsite, taking into account constant-arguments (if any).
          if (std::find(optional_callees.begin(), optional_callees.end(),
                        callee) != optional_callees.end() &&
              should_inline_optional(caller, insn, callee)) {
            optional = true;
          } else {
            return editable_cfg_adapter::LOOP_CONTINUE;
          }
        }
        always_assert(callee->is_concrete());
        if (m_analyze_and_prune_inits && method::is_init(callee)) {
          if (!callee->get_code()->editable_cfg_built()) {
            return editable_cfg_adapter::LOOP_CONTINUE;
          }
          if (!can_inline_init(callee)) {
            if (!method::is_init(caller) ||
                caller->get_class() != callee->get_class() ||
                !caller->get_code()->editable_cfg_built() ||
                !constructor_analysis::can_inline_inits_in_same_class(
                    caller, callee, insn)) {
              return editable_cfg_adapter::LOOP_CONTINUE;
            }
          }
        }

        inlinables.push_back((Inlinable){callee, it, insn, optional});
        if (++found == max) {
          return editable_cfg_adapter::LOOP_BREAK;
        }
        return editable_cfg_adapter::LOOP_CONTINUE;
      });
  if (found != max) {
    always_assert(found <= max);
    info.not_found += max - found;
  }

  if (!inlinables.empty()) {
    inline_inlinables(caller, inlinables);
  }
}

void MultiMethodInliner::inline_callees(
    DexMethod* caller, const std::unordered_set<IRInstruction*>& insns) {
  std::vector<Inlinable> inlinables;
  editable_cfg_adapter::iterate_with_iterator(
      caller->get_code(), [&](const IRList::iterator& it) {
        auto insn = it->insn;
        if (insns.count(insn)) {
          auto callee = resolver(insn->get_method(), opcode_to_search(insn));
          if (caller_virtual_callee.count(caller) &&
              caller_virtual_callee[caller].count(insn)) {
            callee = caller_virtual_callee[caller][insn];
          }
          if (callee == nullptr) {
            return editable_cfg_adapter::LOOP_CONTINUE;
          }
          always_assert(callee->is_concrete());
          inlinables.push_back((Inlinable){callee, it, insn});
        }
        return editable_cfg_adapter::LOOP_CONTINUE;
      });

  inline_inlinables(caller, inlinables);
}

bool MultiMethodInliner::inline_inlinables_need_deconstruct(DexMethod* method) {
  // The mixed CFG, IRCode is used by Switch Inline (only?) where the caller is
  // an IRCode and the callee is a CFG.
  return m_config.use_cfg_inliner && !method->get_code()->editable_cfg_built();
}

void MultiMethodInliner::inline_inlinables(
    DexMethod* caller_method, const std::vector<Inlinable>& inlinables) {

  auto caller = caller_method->get_code();
  std::unordered_set<IRCode*> need_deconstruct;
  if (inline_inlinables_need_deconstruct(caller_method)) {
    need_deconstruct.reserve(1 + inlinables.size());
    need_deconstruct.insert(caller);
    for (const auto& inlinable : inlinables) {
      need_deconstruct.insert(inlinable.callee->get_code());
    }
    for (auto code : need_deconstruct) {
      always_assert(!code->editable_cfg_built());
      code->build_cfg(/* editable */ true);
    }
  }

  // attempt to inline all inlinable candidates
  size_t estimated_insn_size = caller->editable_cfg_built()
                                   ? caller->cfg().sum_opcode_sizes()
                                   : caller->sum_opcode_sizes();

  // Prefer inlining smaller methods first, so that we are less likely to hit
  // overall size limit.
  std::vector<Inlinable> ordered_inlinables(inlinables.begin(),
                                            inlinables.end());

  std::stable_sort(ordered_inlinables.begin(), ordered_inlinables.end(),
                   [&](const Inlinable& a, const Inlinable& b) {
                     // First, prefer non-optional inlinables, as they were
                     // (potentially) selected with a global cost model, taking
                     // into account the savings achieved when eliminating all
                     // calls
                     if (a.optional != b.optional) {
                       return a.optional < b.optional;
                     }
                     // Second, prefer smaller methods, to avoid hitting size
                     // limits too soon
                     return get_callee_insn_size(a.callee) <
                            get_callee_insn_size(b.callee);
                   });

  std::vector<DexMethod*> inlined_callees;
  boost::optional<reg_t> cfg_next_caller_reg;
  if (m_config.use_cfg_inliner && !m_config.unique_inlined_registers) {
    cfg_next_caller_reg = caller->cfg().get_registers_size();
  }
  size_t calls_not_inlinable{0}, calls_not_inlined{0};
  for (const auto& inlinable : ordered_inlinables) {
    auto callee_method = inlinable.callee;
    auto callee = callee_method->get_code();
    auto callsite_insn = inlinable.insn;

    std::vector<DexMethod*> make_static;
    if (!is_inlinable(caller_method, callee_method, callsite_insn,
                      estimated_insn_size, &make_static)) {
      calls_not_inlinable++;
      continue;
    }
    // Only now, when are about actually inline the method, we'll record
    // the fact that we'll have to make some methods static.
    make_static_inlinable(make_static);

    TRACE(MMINL, 4, "inline %s (%d) in %s (%d)", SHOW(callee),
          caller->get_registers_size(), SHOW(caller),
          callee->get_registers_size());

    if (m_config.use_cfg_inliner) {
      if (m_config.unique_inlined_registers) {
        cfg_next_caller_reg = caller->cfg().get_registers_size();
      }
      bool success = inliner::inline_with_cfg(
          caller_method, callee_method, callsite_insn, *cfg_next_caller_reg);
      if (!success) {
        calls_not_inlined++;
        continue;
      }
    } else {
      // Logging before the call to inline_method to get the most relevant line
      // number near callsite before callsite gets replaced. Should be ok as
      // inline_method does not fail to inline.
      log_opt(INLINED, caller_method, callsite_insn);

      auto callsite = inlinable.iterator;
      always_assert(callsite->insn == callsite_insn);
      inliner::inline_method_unsafe(caller_method, caller, callee, callsite);
    }
    TRACE(INL, 2, "caller: %s\tcallee: %s", SHOW(caller), SHOW(callee));
    estimated_insn_size += get_callee_insn_size(callee_method);

    inlined_callees.push_back(callee_method);
  }

  if (!inlined_callees.empty()) {
    for (auto callee_method : inlined_callees) {
      if (m_delayed_change_visibilities) {
        m_delayed_change_visibilities->update(
            callee_method, [caller_method](const DexMethod*,
                                           std::unordered_set<DexType*>& value,
                                           bool /*exists*/) {
              value.insert(caller_method->get_class());
            });
      } else {
        std::lock_guard<std::mutex> guard(m_change_visibility_mutex);
        change_visibility(callee_method, caller_method->get_class());
      }
      m_inlined.insert(callee_method);
    }
  }

  for (IRCode* code : need_deconstruct) {
    code->clear_cfg();
  }

  info.calls_inlined += inlined_callees.size();
  if (calls_not_inlinable) {
    info.calls_not_inlinable += calls_not_inlinable;
  }
  if (calls_not_inlined) {
    info.calls_not_inlined += calls_not_inlined;
  }
}

void MultiMethodInliner::async_prioritized_method_execute(
    DexMethod* method, const std::function<void()>& f) {
  int priority = std::numeric_limits<int>::min();
  auto it = m_async_callee_priorities.find(method);
  if (it != m_async_callee_priorities.end()) {
    priority = it->second;
  }
  m_async_method_executor.post(priority, f);
}

void MultiMethodInliner::async_postprocess_method(DexMethod* method) {
  if (m_async_callee_priorities.count(method) == 0 &&
      (!m_shrinking_enabled || method->rstate.no_optimizations())) {
    return;
  }

  async_prioritized_method_execute(
      method, [method, this]() { postprocess_method(method); });
}

void MultiMethodInliner::shrink_method(DexMethod* method) {
  auto code = method->get_code();
  bool editable_cfg_built = code->editable_cfg_built();

  constant_propagation::Transform::Stats const_prop_stats;
  cse_impl::Stats cse_stats;
  copy_propagation_impl::Stats copy_prop_stats;
  LocalDce::Stats local_dce_stats;
  dedup_blocks_impl::Stats dedup_blocks_stats;

  if (m_config.run_const_prop) {
    if (editable_cfg_built) {
      code->clear_cfg();
    }
    if (!code->cfg_built()) {
      code->build_cfg(/* editable */ false);
    }
    {
      constant_propagation::intraprocedural::FixpointIterator fp_iter(
          code->cfg(), constant_propagation::ConstantPrimitiveAnalyzer());
      fp_iter.run(ConstantEnvironment());
      constant_propagation::Transform::Config config;
      constant_propagation::Transform tf(config);
      const_prop_stats = tf.apply_on_uneditable_cfg(
          fp_iter, constant_propagation::WholeProgramState(), code, &xstores,
          method->get_class());
    }
    always_assert(!code->editable_cfg_built());
    code->build_cfg(/* editable */ true);
    code->cfg().calculate_exit_block();
    {
      constant_propagation::intraprocedural::FixpointIterator fp_iter(
          code->cfg(), constant_propagation::ConstantPrimitiveAnalyzer());
      fp_iter.run(ConstantEnvironment());
      constant_propagation::Transform::Config config;
      constant_propagation::Transform tf(config);
      const_prop_stats += tf.apply(fp_iter, code->cfg(), method, &xstores);
    }
  }

  if (m_config.run_cse) {
    if (!code->editable_cfg_built()) {
      code->build_cfg(/* editable */ true);
    }

    cse_impl::CommonSubexpressionElimination cse(
        m_cse_shared_state.get(), code->cfg(), is_static(method),
        method::is_init(method) || method::is_clinit(method),
        method->get_class(), method->get_proto()->get_args());
    cse.patch();
    cse_stats = cse.get_stats();
  }

  if (m_config.run_copy_prop) {
    copy_propagation_impl::Config config;
    copy_propagation_impl::CopyPropagation copy_propagation(config);
    copy_prop_stats = copy_propagation.run(code, method);
  }

  if (m_config.run_local_dce) {
    // LocalDce doesn't care if editable_cfg_built
    auto local_dce = LocalDce(m_pure_methods);
    local_dce.dce(code);
{'fraction_non_alphanumeric': 0.10940096063800864, 'fraction_numerical': 0.0022354469383439567, 'mean_word_length': 3.1555987948782325, 'pattern_counts': {'":': 2, '<': 171, '<?xml version=': 0, '>': 297, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3610042', 'n_tokens_mistral': 21501, 'n_tokens_neox': 21076, 'n_words': 4292}