<commit_before>/**
 * Copyright (c) 2016-present, Facebook, Inc.
 * All rights reserved.
 *
 * This source code is licensed under the BSD-style license found in the
 * LICENSE file in the root directory of this source tree. An additional grant
 * of patent rights can be found in the PATENTS file in the same directory.
 */

#include "LocalDce.h"

#include <iostream>
#include <array>
#include <unordered_set>
#include <vector>

#include <boost/dynamic_bitset.hpp>

#include "DexClass.h"
#include "DexInstruction.h"
#include "DexUtil.h"
#include "Transform.h"
#include "Walkers.h"

namespace {
/*
 * These instructions have observable side effects so must always be considered
 * live, regardless of whether their output is consumed by another instruction.
 */
static bool has_side_effects(DexOpcode opc) {
  switch (opc) {
  case OPCODE_RETURN_VOID:
  case OPCODE_RETURN:
  case OPCODE_RETURN_WIDE:
  case OPCODE_RETURN_OBJECT:
  case OPCODE_MONITOR_ENTER:
  case OPCODE_MONITOR_EXIT:
  case OPCODE_CHECK_CAST:
  case OPCODE_FILL_ARRAY_DATA:
  case OPCODE_THROW:
  case OPCODE_GOTO:
  case OPCODE_GOTO_16:
  case OPCODE_GOTO_32:
  case OPCODE_PACKED_SWITCH:
  case OPCODE_SPARSE_SWITCH:
  case OPCODE_IF_EQ:
  case OPCODE_IF_NE:
  case OPCODE_IF_LT:
  case OPCODE_IF_GE:
  case OPCODE_IF_GT:
  case OPCODE_IF_LE:
  case OPCODE_IF_EQZ:
  case OPCODE_IF_NEZ:
  case OPCODE_IF_LTZ:
  case OPCODE_IF_GEZ:
  case OPCODE_IF_GTZ:
  case OPCODE_IF_LEZ:
  case OPCODE_APUT:
  case OPCODE_APUT_WIDE:
  case OPCODE_APUT_OBJECT:
  case OPCODE_APUT_BOOLEAN:
  case OPCODE_APUT_BYTE:
  case OPCODE_APUT_CHAR:
  case OPCODE_APUT_SHORT:
  case OPCODE_IPUT:
  case OPCODE_IPUT_WIDE:
  case OPCODE_IPUT_OBJECT:
  case OPCODE_IPUT_BOOLEAN:
  case OPCODE_IPUT_BYTE:
  case OPCODE_IPUT_CHAR:
  case OPCODE_IPUT_SHORT:
  case OPCODE_SPUT:
  case OPCODE_SPUT_WIDE:
  case OPCODE_SPUT_OBJECT:
  case OPCODE_SPUT_BOOLEAN:
  case OPCODE_SPUT_BYTE:
  case OPCODE_SPUT_CHAR:
  case OPCODE_SPUT_SHORT:
  case OPCODE_INVOKE_VIRTUAL:
  case OPCODE_INVOKE_SUPER:
  case OPCODE_INVOKE_DIRECT:
  case OPCODE_INVOKE_STATIC:
  case OPCODE_INVOKE_INTERFACE:
  case OPCODE_INVOKE_VIRTUAL_RANGE:
  case OPCODE_INVOKE_SUPER_RANGE:
  case OPCODE_INVOKE_DIRECT_RANGE:
  case OPCODE_INVOKE_STATIC_RANGE:
  case OPCODE_INVOKE_INTERFACE_RANGE:
  case FOPCODE_PACKED_SWITCH:
  case FOPCODE_SPARSE_SWITCH:
  case FOPCODE_FILLED_ARRAY:
    return true;
  default:
    return false;
  }
  not_reached();
}

/*
 * Pure methods have no observable side effects, so they can be removed if
 * their outputs are not used.
 *
 * TODO: Derive this list with static analysis rather than hard-coding it.
 */
std::unordered_set<DexMethod*> init_pure_methods() {
  std::unordered_set<DexMethod*> pure_methods;
  pure_methods.emplace(DexMethod::make_method(
      "Ljava/lang/Class;", "getSimpleName", "Ljava/lang/String;", {}));
  return pure_methods;
}

bool is_pure(DexMethod* method) {
  static std::unordered_set<DexMethod*> pure_methods = init_pure_methods();
  return pure_methods.find(method) != pure_methods.end();
}

template <typename... T>
std::string show(const boost::dynamic_bitset<T...>& bits) {
  std::string ret;
  to_string(bits, ret);
  return ret;
}

////////////////////////////////////////////////////////////////////////////////

class LocalDce {
 private:
  const Scope& m_scope;
  size_t m_instructions_eliminated{0};
  size_t m_total_instructions{0};

  /*
   * Eliminate dead code using a standard backward dataflow analysis for
   * liveness.  The algorithm is as follows:
   *
   * - Maintain a bitvector for each block representing the liveness for each
   *   register.  Function call results are represented by bit #num_regs.
   *
   * - Walk the blocks in postorder. Compute each block's output state by
   *   OR-ing the liveness of its successors
   *
   * - Walk each block's instructions in reverse to determine its input state.
   *   An instruction's input registers are live if (a) it has side effects, or
   *   (b) its output registers are live.
   *
   * - If the liveness of any block changes during a pass, repeat it.  Since
   *   anything live in one pass is guaranteed to be live in the next, this is
   *   guaranteed to reach a fixed point and terminate.  Visiting blocks in
   *   postorder guarantees a minimum number of passes.
   *
   * - Catch blocks are handled slightly differently; since any instruction
   *   inside a `try` region can jump to a catch block, we assume that any
   *   registers that are live-in to a catch block must be kept live throughout
   *   the `try` region.  (This is actually conservative, since only
   *   potentially-excepting instructions can jump to a catch.)
   */
  void dce(DexMethod* method) {
    auto transform =
        MethodTransform::get_method_transform(method, true /* want_cfg */);
    auto& cfg = transform->cfg();
    auto blocks = PostOrderSort(cfg).get();
    auto regs = method->get_code()->get_registers_size();
    std::vector<boost::dynamic_bitset<>> liveness(
        cfg.size(), boost::dynamic_bitset<>(regs + 1));
    bool changed;
    std::vector<DexInstruction*> dead_instructions;

    TRACE(DCE, 5, "%s\n", show(method).c_str());
    TRACE(DCE, 5, "%s", show(cfg).c_str());

    // Iterate liveness analysis to a fixed point.
    do {
      changed = false;
      dead_instructions.clear();
      for (auto& b : blocks) {
        auto prev_liveness = liveness.at(b->id());
        auto& bliveness = liveness.at(b->id());
        bliveness.reset();
        TRACE(DCE, 5, "B%lu: %s\n", b->id(), show(bliveness).c_str());

        // Compute live-out for this block from its successors.
        for (auto& s : b->succs()) {
          TRACE(DCE,
                5,
                "  S%lu: %s\n",
                s->id(),
                show(liveness[s->id()]).c_str());
          bliveness |= liveness[s->id()];
        }

        // Compute live-in for this block by walking its instruction list in
        // reverse and applying the liveness rules.
        for (auto it = b->rbegin(); it != b->rend(); ++it) {
          m_total_instructions++;
          if (it->type != MFLOW_OPCODE) {
            continue;
          }
          bool required = is_required(it->insn, bliveness);
          if (required) {
            update_liveness(it->insn, bliveness);
          } else {
            dead_instructions.push_back(it->insn);
          }
          TRACE(CFG,
                5,
                "%s\n%s\n",
                show(it->insn).c_str(),
                show(bliveness).c_str());
        }
        if (bliveness != prev_liveness) {
          changed = true;
        }
      }
    } while (changed);

    // Remove dead instructions.
    TRACE(DCE, 2, "%s\n", show(method).c_str());<commit_msg>Update LocalDCE to fix instrumentation test error<commit_after>/**
 * Copyright (c) 2016-present, Facebook, Inc.
 * All rights reserved.
 *
 * This source code is licensed under the BSD-style license found in the
 * LICENSE file in the root directory of this source tree. An additional grant
 * of patent rights can be found in the PATENTS file in the same directory.
 */

#include "LocalDce.h"

#include <iostream>
#include <array>
#include <unordered_set>
#include <vector>

#include <boost/dynamic_bitset.hpp>

#include "DexClass.h"
#include "DexInstruction.h"
#include "DexUtil.h"
#include "Transform.h"
#include "Walkers.h"

namespace {
/*
 * These instructions have observable side effects so must always be considered
 * live, regardless of whether their output is consumed by another instruction.
 */
static bool has_side_effects(DexOpcode opc) {
  switch (opc) {
  case OPCODE_RETURN_VOID:
  case OPCODE_RETURN:
  case OPCODE_RETURN_WIDE:
  case OPCODE_RETURN_OBJECT:
  case OPCODE_MONITOR_ENTER:
  case OPCODE_MONITOR_EXIT:
  case OPCODE_CHECK_CAST:
  case OPCODE_FILL_ARRAY_DATA:
  case OPCODE_THROW:
  case OPCODE_GOTO:
  case OPCODE_GOTO_16:
  case OPCODE_GOTO_32:
  case OPCODE_PACKED_SWITCH:
  case OPCODE_SPARSE_SWITCH:
  case OPCODE_IF_EQ:
  case OPCODE_IF_NE:
  case OPCODE_IF_LT:
  case OPCODE_IF_GE:
  case OPCODE_IF_GT:
  case OPCODE_IF_LE:
  case OPCODE_IF_EQZ:
  case OPCODE_IF_NEZ:
  case OPCODE_IF_LTZ:
  case OPCODE_IF_GEZ:
  case OPCODE_IF_GTZ:
  case OPCODE_IF_LEZ:
  case OPCODE_APUT:
  case OPCODE_APUT_WIDE:
  case OPCODE_APUT_OBJECT:
  case OPCODE_APUT_BOOLEAN:
  case OPCODE_APUT_BYTE:
  case OPCODE_APUT_CHAR:
  case OPCODE_APUT_SHORT:
  case OPCODE_IPUT:
  case OPCODE_IPUT_WIDE:
  case OPCODE_IPUT_OBJECT:
  case OPCODE_IPUT_BOOLEAN:
  case OPCODE_IPUT_BYTE:
  case OPCODE_IPUT_CHAR:
  case OPCODE_IPUT_SHORT:
  case OPCODE_SPUT:
  case OPCODE_SPUT_WIDE:
  case OPCODE_SPUT_OBJECT:
  case OPCODE_SPUT_BOOLEAN:
  case OPCODE_SPUT_BYTE:
  case OPCODE_SPUT_CHAR:
  case OPCODE_SPUT_SHORT:
  case OPCODE_INVOKE_VIRTUAL:
  case OPCODE_INVOKE_SUPER:
  case OPCODE_INVOKE_DIRECT:
  case OPCODE_INVOKE_STATIC:
  case OPCODE_INVOKE_INTERFACE:
  case OPCODE_INVOKE_VIRTUAL_RANGE:
  case OPCODE_INVOKE_SUPER_RANGE:
  case OPCODE_INVOKE_DIRECT_RANGE:
  case OPCODE_INVOKE_STATIC_RANGE:
  case OPCODE_INVOKE_INTERFACE_RANGE:
  case FOPCODE_PACKED_SWITCH:
  case FOPCODE_SPARSE_SWITCH:
  case FOPCODE_FILLED_ARRAY:
    return true;
  default:
    return false;
  }
  not_reached();
}

/*
 * Pure methods have no observable side effects, so they can be removed if
 * their outputs are not used.
 *
 * TODO: Derive this list with static analysis rather than hard-coding it.
 */
std::unordered_set<DexMethod*> init_pure_methods() {
  std::unordered_set<DexMethod*> pure_methods;
  pure_methods.emplace(DexMethod::make_method(
      "Ljava/lang/Class;", "getSimpleName", "Ljava/lang/String;", {}));
  return pure_methods;
}

bool is_pure(DexMethod* method) {
  static std::unordered_set<DexMethod*> pure_methods = init_pure_methods();
  return pure_methods.find(method) != pure_methods.end();
}

template <typename... T>
std::string show(const boost::dynamic_bitset<T...>& bits) {
  std::string ret;
  to_string(bits, ret);
  return ret;
}

////////////////////////////////////////////////////////////////////////////////

class LocalDce {
 private:
  const Scope& m_scope;
  size_t m_instructions_eliminated{0};
  size_t m_total_instructions{0};

  /*
   * Eliminate dead code using a standard backward dataflow analysis for
   * liveness.  The algorithm is as follows:
   *
   * - Maintain a bitvector for each block representing the liveness for each
   *   register.  Function call results are represented by bit #num_regs.
   *
   * - Walk the blocks in postorder. Compute each block's output state by
   *   OR-ing the liveness of its successors
   *
   * - Walk each block's instructions in reverse to determine its input state.
   *   An instruction's input registers are live if (a) it has side effects, or
   *   (b) its output registers are live.
   *
   * - If the liveness of any block changes during a pass, repeat it.  Since
   *   anything live in one pass is guaranteed to be live in the next, this is
   *   guaranteed to reach a fixed point and terminate.  Visiting blocks in
   *   postorder guarantees a minimum number of passes.
   *
   * - Catch blocks are handled slightly differently; since any instruction
   *   inside a `try` region can jump to a catch block, we assume that any
   *   registers that are live-in to a catch block must be kept live throughout
   *   the `try` region.  (This is actually conservative, since only
   *   potentially-excepting instructions can jump to a catch.)
   */
  void dce(DexMethod* method) {
    auto transform =
        MethodTransform::get_method_transform(method, true /* want_cfg */);
    auto& cfg = transform->cfg();
    auto blocks = PostOrderSort(cfg).get();
    auto regs = method->get_code()->get_registers_size();
    std::vector<boost::dynamic_bitset<>> liveness(
        cfg.size(), boost::dynamic_bitset<>(regs + 1));
    bool changed;
    std::vector<DexInstruction*> dead_instructions;

    TRACE(DCE, 5, "%s\n", show(method).c_str());
    TRACE(DCE, 5, "%s", show(cfg).c_str());

    // Iterate liveness analysis to a fixed point.
    do {
      changed = false;
      dead_instructions.clear();
      for (auto& b : blocks) {
        auto prev_liveness = liveness.at(b->id());
        auto& bliveness = liveness.at(b->id());
        bliveness.reset();
        TRACE(DCE, 5, "B%lu: %s\n", b->id(), show(bliveness).c_str());
        bool loop = false;

        // Compute live-out for this block from its successors.
        for (auto& s : b->succs()) {
          if(s->id() == b->id()) {
            loop = true;
          }
          TRACE(DCE,
                5,
                "  S%lu: %s\n",
                s->id(),
                show(liveness[s->id()]).c_str());
          bliveness |= liveness[s->id()];
        }

        if (loop) {
          for (auto it = b->rbegin(); it != b->rend(); ++it) {
            if (it->type != MFLOW_OPCODE) {
              continue;
            }
            if (is_required(it->insn, bliveness)) {
              update_liveness(it->insn, bliveness);
            }
          }
          for (auto& s : b->succs()) {
            bliveness |= liveness[s->id()];
          }
        }

        // Compute live-in for this block by walking its instruction list in
        // reverse and applying the liveness rules.
        for (auto it = b->rbegin(); it != b->rend(); ++it) {
          m_total_instructions++;
          if (it->type != MFLOW_OPCODE) {
            continue;
          }
          bool required = is_required(it->insn, bliveness);
          if (required) {
            update_liveness(it->insn, bliveness);
          } else {
            dead_instructions.push_back(it->insn);
          }
          TRACE(CFG,
                5,
                "%s\n%s\n",
                show(it->insn).c_str(),
                show(bliveness).c_str());
        }
        if (bliveness != prev_liveness) {
          changed = true;
        }
      }
    } while (changed);

    // Remove dead instructions.
    TRACE(DCE, 2, "%s\n", show(method).c_str());
{'fraction_non_alphanumeric': 0.11055776892430279, 'fraction_numerical': 0.002418895845190666, 'mean_word_length': 2.8724517906336087, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 74, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5739238', 'n_tokens_mistral': 4735, 'n_tokens_neox': 4885, 'n_words': 1272}