improve tracking in DedupBlocks

Summary: Previously, DedupBlocks in instrumentation mode overcounted source blocks, because the deduplicated block's source block was copied from the source block of the block it was split from. Now, DedupBlocks considers source blocks when searching for common instructions. When joining the split off blocks into a common block, set the source block's ID to `SourceBlock::kSyntheticId`, and merge in the interactions of the source blocks from the deleted block. Add support for source blocks in DedupBlockValueNumbering when running instrumentation mode. Two source blocks are equivalent if they have the same source block id. automation_fbandroid_redexunstable_art_hdpi_arm64_release redex_stats violation changes: P1226822496 Reviewed By: jimmycFB Differential Revision: D54130542 fbshipit-source-id: e752a8c8ad2f1cb7e3fea629ad540af790b32f36
joychic · Apr 30, 2024 · f6e06c8 · f6e06c8
1 parent f672d2f
commit f6e06c8
Show file tree

Hide file tree

Showing 7 changed files with 1,104 additions and 80 deletions.
diff --git a/opt/insert-source-blocks/InsertSourceBlocks.h b/opt/insert-source-blocks/InsertSourceBlocks.h
@@ -45,4 +45,5 @@ class InsertSourceBlocksPass : public Pass {
   bool m_always_inject{true};
 
   friend class SourceBlocksTest;
+  friend class SourceBlocksDedupTest;
 };
diff --git a/service/dedup-blocks/DedupBlockValueNumbering.cpp b/service/dedup-blocks/DedupBlockValueNumbering.cpp
@@ -7,10 +7,24 @@
 
 #include "DedupBlockValueNumbering.h"
 
+#include "RedexContext.h"
 #include "StlUtil.h"
 
 using namespace DedupBlkValueNumbering;
 
+void next_opcode_or_srcblk(IRList::iterator& block_it, cfg::Block* block) {
+  if (g_redex->instrument_mode) {
+    while (block_it != block->end() && block_it->type != MFLOW_OPCODE &&
+           block_it->type != MFLOW_SOURCE_BLOCK) {
+      ++block_it;
+    }
+  } else {
+    while (block_it != block->end() && block_it->type != MFLOW_OPCODE) {
+      ++block_it;
+    }
+  }
+}
+
 // Return BlockValue hash for the given block.
 const BlockValue* BlockValues::get_block_value(cfg::Block* block) const {
   // Check if we have already computed.
@@ -22,27 +36,39 @@ const BlockValue* BlockValues::get_block_value(cfg::Block* block) const {
   std::unique_ptr<BlockValue> block_value = std::make_unique<BlockValue>();
   auto& regs = block_value->out_regs;
   auto& ordered_operations = block_value->ordered_operations;
-  for (auto& mie : InstructionIterable(block)) {
-    auto operation = get_operation(regs, mie.insn);
-    bool is_ordered = is_ordered_operation(operation);
-    if (is_ordered) {
-      ordered_operations.push_back(operation);
-    } else {
-      always_assert(operation.opcode == OPCODE_NOP || mie.insn->has_dest());
-    }
-    if (mie.insn->has_dest()) {
-      if (is_ordered) {
-        operation.opcode = IOPCODE_OPERATION_RESULT;
-        operation.srcs.clear();
-        operation.operation_index = ordered_operations.size() - 1;
-      }
-      auto value = opcode::is_a_move(operation.opcode)
-                       ? operation.srcs.at(0)
-                       : get_value_id(operation);
-      regs[mie.insn->dest()] = value;
-      if (mie.insn->dest_is_wide()) {
-        regs.erase(mie.insn->dest() + 1);
+  auto block_it = block->begin();
+  while (block_it != block->end()) {
+    next_opcode_or_srcblk(block_it, block);
+    if (block_it != block->end()) {
+      if (block_it->type == MFLOW_OPCODE) {
+        auto operation = get_operation(regs, block_it->insn);
+        bool is_ordered = is_ordered_operation(operation);
+        if (is_ordered) {
+          ordered_operations.push_back(operation);
+        } else {
+          always_assert(operation.opcode == OPCODE_NOP ||
+                        block_it->insn->has_dest());
+        }
+        if (block_it->insn->has_dest()) {
+          if (is_ordered) {
+            operation.opcode = IOPCODE_OPERATION_RESULT;
+            operation.srcs.clear();
+            operation.operation_index = ordered_operations.size() - 1;
+          }
+          auto value = opcode::is_a_move(operation.opcode)
+                           ? operation.srcs.at(0)
+                           : get_value_id(operation);
+          regs[block_it->insn->dest()] = value;
+          if (block_it->insn->dest_is_wide()) {
+            regs.erase(block_it->insn->dest() + 1);
+          }
+        }
+      } else if (block_it->type == MFLOW_SOURCE_BLOCK) {
+        IROperation operation;
+        operation.src_blk_id = block_it->src_block->id;
+        ordered_operations.push_back(operation);
       }
+      block_it++;
     }
   }
   const auto& live_out_vars =

diff --git a/service/dedup-blocks/DedupBlockValueNumbering.h b/service/dedup-blocks/DedupBlockValueNumbering.h
@@ -41,7 +41,7 @@ const IROpcode IOPCODE_OPERATION_RESULT = IROpcode(0xFFFE);
 // implementation.
 
 struct IROperation {
-  IROpcode opcode;
+  IROpcode opcode{0};
   std::vector<value_id_t> srcs;
   union {
     // Zero-initialize this union with the uint64_t member instead of a
@@ -54,6 +54,7 @@ struct IROperation {
     const DexOpcodeData* data;
     reg_t in_reg;
     size_t operation_index;
+    uint32_t src_blk_id;
   };
 };
 
@@ -62,12 +63,14 @@ struct IROperationHasher {
     size_t hash = tv.opcode;
     boost::hash_combine(hash, tv.srcs);
     boost::hash_combine(hash, (size_t)tv.literal);
+    boost::hash_combine(hash, tv.src_blk_id);
     return hash;
   }
 };
 
 inline bool operator==(const IROperation& a, const IROperation& b) {
-  return a.opcode == b.opcode && a.srcs == b.srcs && a.literal == b.literal;
+  return a.opcode == b.opcode && a.srcs == b.srcs && a.literal == b.literal &&
+         a.src_blk_id == b.src_blk_id;
 }
 
 struct BlockValue {