Merge "Quick: Fix wide Phi detection in GVN, clean up INVOKEs."

5 files changed, 173 insertions, 38 deletions

diff --git a/compiler/dex/global_value_numbering.cc b/compiler/dex/global_value_numbering.cc
index f0f7a70..d311bc7 100644
--- a/compiler/dex/global_value_numbering.cc
+++ b/compiler/dex/global_value_numbering.cc
@@ -70,12 +70,7 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb,
   DCHECK(work_lvn_.get() == nullptr);
   work_lvn_.reset(new (allocator) LocalValueNumbering(this, bb->id, allocator));
   if (bb->block_type == kEntryBlock) {
-    if ((cu_->access_flags & kAccStatic) == 0) {
-      // If non-static method, mark "this" as non-null
-      int this_reg = cu_->mir_graph->GetFirstInVR();
-      uint16_t value_name = work_lvn_->GetSRegValueName(this_reg);
-      work_lvn_->SetValueNameNullChecked(value_name);
-    }
+    work_lvn_->PrepareEntryBlock();
     DCHECK(bb->first_mir_insn == nullptr);  // modifications_allowed_ is irrelevant.
   } else {
     // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member.
@@ -127,12 +122,6 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb,
     CHECK(!merge_lvns_.empty());
     if (merge_lvns_.size() == 1u) {
       work_lvn_->MergeOne(*merge_lvns_[0], merge_type);
-      BasicBlock* pred_bb = mir_graph_->GetBasicBlock(merge_lvns_[0]->Id());
-      if (HasNullCheckLastInsn(pred_bb, bb->id)) {
-        int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
-        uint16_t value_name = merge_lvns_[0]->GetSRegValueName(s_reg);
-        work_lvn_->SetValueNameNullChecked(value_name);
-      }
     } else {
       work_lvn_->Merge(merge_type);
     }
diff --git a/compiler/dex/global_value_numbering.h b/compiler/dex/global_value_numbering.h
index df554cd..a4a7602 100644
--- a/compiler/dex/global_value_numbering.h
+++ b/compiler/dex/global_value_numbering.h
@@ -105,6 +105,19 @@ class GlobalValueNumbering {
     return res;
   }
 
+  // Look up a value in the global value map, don't add a new entry if there was none before.
+  uint16_t FindValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
+    uint16_t res;
+    uint64_t key = BuildKey(op, operand1, operand2, modifier);
+    ValueMap::iterator lb = global_value_map_.lower_bound(key);
+    if (lb != global_value_map_.end() && lb->first == key) {
+      res = lb->second;
+    } else {
+      res = kNoValue;
+    }
+    return res;
+  }
+
   // Check if the exact value is stored in the global value map.
   bool HasValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier,
                 uint16_t value) const {
@@ -253,6 +266,7 @@ class GlobalValueNumbering {
   ScopedArenaVector<const LocalValueNumbering*> merge_lvns_;  // Not owning.
 
   friend class LocalValueNumbering;
+  friend class GlobalValueNumberingTest;
 
   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumbering);
 };
diff --git a/compiler/dex/global_value_numbering_test.cc b/compiler/dex/global_value_numbering_test.cc
index 82a11a5..d1bca29 100644
--- a/compiler/dex/global_value_numbering_test.cc
+++ b/compiler/dex/global_value_numbering_test.cc
@@ -25,6 +25,8 @@ namespace art {
 
 class GlobalValueNumberingTest : public testing::Test {
  protected:
+  static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
+
   struct IFieldDef {
     uint16_t field_idx;
     uintptr_t declaring_dex_file;
@@ -125,6 +127,8 @@ class GlobalValueNumberingTest : public testing::Test {
     { bb, opcode, 0u, 0u, 1, { reg }, 0, { } }
 #define DEF_MOVE(bb, opcode, reg, src) \
     { bb, opcode, 0u, 0u, 1, { src }, 1, { reg } }
+#define DEF_MOVE_WIDE(bb, opcode, reg, src) \
+    { bb, opcode, 0u, 0u, 2, { src, src + 1 }, 2, { reg, reg + 1 } }
 #define DEF_PHI2(bb, reg, src1, src2) \
     { bb, static_cast<Instruction::Code>(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } }
 
@@ -341,6 +345,8 @@ class GlobalValueNumberingTest : public testing::Test {
       cu_.mir_graph->ssa_base_vregs_.push_back(i);
       cu_.mir_graph->ssa_subscripts_.push_back(0);
     }
+    // Set shorty for a void-returning method without arguments.
+    cu_.shorty = "V";
   }
 
   static constexpr size_t kMaxSsaRegs = 16384u;
@@ -356,6 +362,8 @@ class GlobalValueNumberingTest : public testing::Test {
   ArenaBitVector* live_in_v_;
 };
 
+constexpr uint16_t GlobalValueNumberingTest::kNoValue;
+
 class GlobalValueNumberingTestDiamond : public GlobalValueNumberingTest {
  public:
   GlobalValueNumberingTestDiamond();
@@ -981,6 +989,92 @@ TEST_F(GlobalValueNumberingTestDiamond, Phi) {
   EXPECT_EQ(value_names_[18], value_names_[21]);
 }
 
+TEST_F(GlobalValueNumberingTestDiamond, PhiWide) {
+  static const MIRDef mirs[] = {
+      DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000),
+      DEF_CONST_WIDE(4, Instruction::CONST_WIDE, 2u, 2000),
+      DEF_CONST_WIDE(5, Instruction::CONST_WIDE, 4u, 3000),
+      DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 6u, 0u),
+      DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 8u, 2u),
+      DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 10u, 0u),
+      DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 12u, 4u),
+      DEF_PHI2(6, 14u, 6u, 10u),    // Same as CONST_WIDE 0u (1000).
+      DEF_PHI2(6, 15u, 7u, 11u),    // Same as CONST_WIDE 0u (1000), high word.
+      DEF_PHI2(6, 16u, 6u,  0u),    // Same as CONST_WIDE 0u (1000).
+      DEF_PHI2(6, 17u, 7u,  1u),    // Same as CONST_WIDE 0u (1000), high word.
+      DEF_PHI2(6, 18u, 0u, 10u),    // Same as CONST_WIDE 0u (1000).
+      DEF_PHI2(6, 19u, 1u, 11u),    // Same as CONST_WIDE 0u (1000), high word.
+      DEF_PHI2(6, 20u, 8u, 10u),    // Merge 2u (2000) and 0u (1000).
+      DEF_PHI2(6, 21u, 9u, 11u),    // Merge 2u (2000) and 0u (1000), high word.
+      DEF_PHI2(6, 22u, 2u, 10u),    // Merge 2u (2000) and 0u (1000).
+      DEF_PHI2(6, 23u, 3u, 11u),    // Merge 2u (2000) and 0u (1000), high word.
+      DEF_PHI2(6, 24u, 8u,  0u),    // Merge 2u (2000) and 0u (1000).
+      DEF_PHI2(6, 25u, 9u,  1u),    // Merge 2u (2000) and 0u (1000), high word.
+      DEF_PHI2(6, 26u, 2u,  0u),    // Merge 2u (2000) and 0u (1000).
+      DEF_PHI2(6, 27u, 5u,  1u),    // Merge 2u (2000) and 0u (1000), high word.
+      DEF_PHI2(6, 28u, 6u, 12u),    // Merge 0u (1000) and 4u (3000).
+      DEF_PHI2(6, 29u, 7u, 13u),    // Merge 0u (1000) and 4u (3000), high word.
+      DEF_PHI2(6, 30u, 0u, 12u),    // Merge 0u (1000) and 4u (3000).
+      DEF_PHI2(6, 31u, 1u, 13u),    // Merge 0u (1000) and 4u (3000), high word.
+      DEF_PHI2(6, 32u, 6u,  4u),    // Merge 0u (1000) and 4u (3000).
+      DEF_PHI2(6, 33u, 7u,  5u),    // Merge 0u (1000) and 4u (3000), high word.
+      DEF_PHI2(6, 34u, 0u,  4u),    // Merge 0u (1000) and 4u (3000).
+      DEF_PHI2(6, 35u, 1u,  5u),    // Merge 0u (1000) and 4u (3000), high word.
+      DEF_PHI2(6, 36u, 8u, 12u),    // Merge 2u (2000) and 4u (3000).
+      DEF_PHI2(6, 37u, 9u, 13u),    // Merge 2u (2000) and 4u (3000), high word.
+      DEF_PHI2(6, 38u, 2u, 12u),    // Merge 2u (2000) and 4u (3000).
+      DEF_PHI2(6, 39u, 3u, 13u),    // Merge 2u (2000) and 4u (3000), high word.
+      DEF_PHI2(6, 40u, 8u,  4u),    // Merge 2u (2000) and 4u (3000).
+      DEF_PHI2(6, 41u, 9u,  5u),    // Merge 2u (2000) and 4u (3000), high word.
+      DEF_PHI2(6, 42u, 2u,  4u),    // Merge 2u (2000) and 4u (3000).
+      DEF_PHI2(6, 43u, 3u,  5u),    // Merge 2u (2000) and 4u (3000), high word.
+  };
+
+  PrepareMIRs(mirs);
+  PerformGVN();
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  EXPECT_EQ(value_names_[0], value_names_[7]);
+  EXPECT_EQ(value_names_[0], value_names_[9]);
+  EXPECT_EQ(value_names_[0], value_names_[11]);
+  EXPECT_NE(value_names_[13], value_names_[0]);
+  EXPECT_NE(value_names_[13], value_names_[1]);
+  EXPECT_NE(value_names_[13], value_names_[2]);
+  EXPECT_EQ(value_names_[13], value_names_[15]);
+  EXPECT_EQ(value_names_[13], value_names_[17]);
+  EXPECT_EQ(value_names_[13], value_names_[19]);
+  EXPECT_NE(value_names_[21], value_names_[0]);
+  EXPECT_NE(value_names_[21], value_names_[1]);
+  EXPECT_NE(value_names_[21], value_names_[2]);
+  EXPECT_NE(value_names_[21], value_names_[13]);
+  EXPECT_EQ(value_names_[21], value_names_[23]);
+  EXPECT_EQ(value_names_[21], value_names_[25]);
+  EXPECT_EQ(value_names_[21], value_names_[27]);
+  EXPECT_NE(value_names_[29], value_names_[0]);
+  EXPECT_NE(value_names_[29], value_names_[1]);
+  EXPECT_NE(value_names_[29], value_names_[2]);
+  EXPECT_NE(value_names_[29], value_names_[13]);
+  EXPECT_NE(value_names_[29], value_names_[21]);
+  EXPECT_EQ(value_names_[29], value_names_[31]);
+  EXPECT_EQ(value_names_[29], value_names_[33]);
+  EXPECT_EQ(value_names_[29], value_names_[35]);
+  // High words should get kNoValue.
+  EXPECT_EQ(value_names_[8], kNoValue);
+  EXPECT_EQ(value_names_[10], kNoValue);
+  EXPECT_EQ(value_names_[12], kNoValue);
+  EXPECT_EQ(value_names_[14], kNoValue);
+  EXPECT_EQ(value_names_[16], kNoValue);
+  EXPECT_EQ(value_names_[18], kNoValue);
+  EXPECT_EQ(value_names_[20], kNoValue);
+  EXPECT_EQ(value_names_[22], kNoValue);
+  EXPECT_EQ(value_names_[24], kNoValue);
+  EXPECT_EQ(value_names_[26], kNoValue);
+  EXPECT_EQ(value_names_[28], kNoValue);
+  EXPECT_EQ(value_names_[30], kNoValue);
+  EXPECT_EQ(value_names_[32], kNoValue);
+  EXPECT_EQ(value_names_[34], kNoValue);
+  EXPECT_EQ(value_names_[36], kNoValue);
+}
+
 TEST_F(GlobalValueNumberingTestLoop, NonAliasingIFields) {
   static const IFieldDef ifields[] = {
       { 0u, 1u, 0u, false },  // Int.
diff --git a/compiler/dex/local_value_numbering.cc b/compiler/dex/local_value_numbering.cc
index 8b7ae20..5456f4d 100644
--- a/compiler/dex/local_value_numbering.cc
+++ b/compiler/dex/local_value_numbering.cc
@@ -374,6 +374,12 @@ void LocalValueNumbering::MergeOne(const LocalValueNumbering& other, MergeType m
   range_checked_ = other.range_checked_;
   null_checked_ = other.null_checked_;
 
+  const BasicBlock* pred_bb = gvn_->GetBasicBlock(other.Id());
+  if (GlobalValueNumbering::HasNullCheckLastInsn(pred_bb, Id())) {
+    int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
+    null_checked_.insert(other.GetOperandValue(s_reg));
+  }
+
   if (merge_type == kCatchMerge) {
     // Memory is clobbered. Use new memory version and don't merge aliasing locations.
     global_memory_version_ = NewMemoryVersion(&merge_new_memory_version_);
@@ -465,10 +471,7 @@ void LocalValueNumbering::PruneNonAliasingRefsForCatch() {
     DCHECK(mir != nullptr);
     // Only INVOKEs can leak and clobber non-aliasing references if they throw.
     if ((mir->dalvikInsn.FlagsOf() & Instruction::kInvoke) != 0) {
-      for (uint16_t i = 0u; i != mir->ssa_rep->num_uses; ++i) {
-        uint16_t value_name = lvn->GetOperandValue(mir->ssa_rep->uses[i]);
-        non_aliasing_refs_.erase(value_name);
-      }
+      HandleInvokeArgs(mir, lvn);
     }
   }
 }
@@ -681,7 +684,7 @@ void LocalValueNumbering::MergeNullChecked() {
   const BasicBlock* least_entries_bb = gvn_->GetBasicBlock(least_entries_lvn->Id());
   if (gvn_->HasNullCheckLastInsn(least_entries_bb, id_)) {
     int s_reg = least_entries_bb->last_mir_insn->ssa_rep->uses[0];
-    uint32_t value_name = least_entries_lvn->GetSRegValueName(s_reg);
+    uint32_t value_name = least_entries_lvn->GetOperandValue(s_reg);
     merge_names_.clear();
     merge_names_.resize(gvn_->merge_lvns_.size(), value_name);
     if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
@@ -953,6 +956,26 @@ void LocalValueNumbering::Merge(MergeType merge_type) {
                 AliasingArrayVersions>>();
 }
 
+void LocalValueNumbering::PrepareEntryBlock() {
+  uint32_t vreg = gvn_->GetMirGraph()->GetFirstInVR();
+  CompilationUnit* cu = gvn_->GetCompilationUnit();
+  const char* shorty = cu->shorty;
+  ++shorty;  // Skip return value.
+  if ((cu->access_flags & kAccStatic) == 0) {
+    // If non-static method, mark "this" as non-null
+    uint16_t value_name = GetOperandValue(vreg);
+    ++vreg;
+    null_checked_.insert(value_name);
+  }
+  for ( ; *shorty != 0; ++shorty, ++vreg) {
+    if (*shorty == 'J' || *shorty == 'D') {
+      uint16_t value_name = GetOperandValueWide(vreg);
+      SetOperandValueWide(vreg, value_name);
+      ++vreg;
+    }
+  }
+}
+
 uint16_t LocalValueNumbering::MarkNonAliasingNonNull(MIR* mir) {
   uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]);
   DCHECK(null_checked_.find(res) == null_checked_.end());
@@ -1039,12 +1062,30 @@ void LocalValueNumbering::HandleEscapingRef(uint16_t base) {
   }
 }
 
+void LocalValueNumbering::HandleInvokeArgs(const MIR* mir, const LocalValueNumbering* mir_lvn) {
+  const int32_t* uses = mir->ssa_rep->uses;
+  const int32_t* uses_end = uses + mir->ssa_rep->num_uses;
+  while (uses != uses_end) {
+    uint16_t sreg = *uses;
+    ++uses;
+    // Avoid LookupValue() so that we don't store new values in the global value map.
+    auto local_it = mir_lvn->sreg_value_map_.find(sreg);
+    if (local_it != mir_lvn->sreg_value_map_.end()) {
+      non_aliasing_refs_.erase(local_it->second);
+    } else {
+      uint16_t value_name = gvn_->FindValue(kNoValue, sreg, kNoValue, kNoValue);
+      if (value_name != kNoValue) {
+        non_aliasing_refs_.erase(value_name);
+      }
+    }
+  }
+}
+
 uint16_t LocalValueNumbering::HandlePhi(MIR* mir) {
   if (gvn_->merge_lvns_.empty()) {
     // Running LVN without a full GVN?
     return kNoValue;
   }
-  int16_t num_uses = mir->ssa_rep->num_uses;
   int32_t* uses = mir->ssa_rep->uses;
   // Try to find out if this is merging wide regs.
   if (mir->ssa_rep->defs[0] != 0 &&
@@ -1052,18 +1093,20 @@ uint16_t LocalValueNumbering::HandlePhi(MIR* mir) {
     // This is the high part of a wide reg. Ignore the Phi.
     return kNoValue;
   }
-  bool wide = false;
-  for (int16_t i = 0; i != num_uses; ++i) {
-    if (sreg_wide_value_map_.count(uses[i]) != 0u) {
-      wide = true;
-      break;
-    }
+  BasicBlockId* incoming = mir->meta.phi_incoming;
+  int16_t pos = 0;
+  // Check if we're merging a wide value based on the first merged LVN.
+  const LocalValueNumbering* first_lvn = gvn_->merge_lvns_[0];
+  DCHECK_LT(pos, mir->ssa_rep->num_uses);
+  while (incoming[pos] != first_lvn->Id()) {
+    ++pos;
+    DCHECK_LT(pos, mir->ssa_rep->num_uses);
   }
+  int first_s_reg = uses[pos];
+  bool wide = (first_lvn->sreg_wide_value_map_.count(first_s_reg) != 0u);
   // Iterate over *merge_lvns_ and skip incoming sregs for BBs without associated LVN.
   uint16_t value_name = kNoValue;
   merge_names_.clear();
-  BasicBlockId* incoming = mir->meta.phi_incoming;
-  int16_t pos = 0;
   bool same_values = true;
   for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
     DCHECK_LT(pos, mir->ssa_rep->num_uses);
@@ -1468,10 +1511,7 @@ uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) {
     case Instruction::INVOKE_STATIC:
     case Instruction::INVOKE_STATIC_RANGE:
       // Make ref args aliasing.
-      for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) {
-        uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]);
-        non_aliasing_refs_.erase(reg);
-      }
+      HandleInvokeArgs(mir, this);
       HandleInvokeOrClInitOrAcquireOp(mir);
       break;
 
diff --git a/compiler/dex/local_value_numbering.h b/compiler/dex/local_value_numbering.h
index c60da32..dd8d2db 100644
--- a/compiler/dex/local_value_numbering.h
+++ b/compiler/dex/local_value_numbering.h
@@ -44,14 +44,6 @@ class LocalValueNumbering {
 
   bool Equals(const LocalValueNumbering& other) const;
 
-  uint16_t GetSRegValueName(uint16_t s_reg) const {
-    return GetOperandValue(s_reg);
-  }
-
-  void SetValueNameNullChecked(uint16_t value_name) {
-    null_checked_.insert(value_name);
-  }
-
   bool IsValueNullChecked(uint16_t value_name) const {
     return null_checked_.find(value_name) != null_checked_.end();
   }
@@ -73,6 +65,7 @@ class LocalValueNumbering {
 
   void MergeOne(const LocalValueNumbering& other, MergeType merge_type);
   void Merge(MergeType merge_type);  // Merge gvn_->merge_lvns_.
+  void PrepareEntryBlock();
 
   uint16_t GetValueNumber(MIR* mir);
 
@@ -121,18 +114,22 @@ class LocalValueNumbering {
   }
 
   void SetOperandValue(uint16_t s_reg, uint16_t value) {
+    DCHECK_EQ(sreg_wide_value_map_.count(s_reg), 0u);
     SetOperandValueImpl(s_reg, value, &sreg_value_map_);
   }
 
   uint16_t GetOperandValue(int s_reg) const {
+    DCHECK_EQ(sreg_wide_value_map_.count(s_reg), 0u);
     return GetOperandValueImpl(s_reg, &sreg_value_map_);
   }
 
   void SetOperandValueWide(uint16_t s_reg, uint16_t value) {
+    DCHECK_EQ(sreg_value_map_.count(s_reg), 0u);
     SetOperandValueImpl(s_reg, value, &sreg_wide_value_map_);
   }
 
   uint16_t GetOperandValueWide(int s_reg) const {
+    DCHECK_EQ(sreg_value_map_.count(s_reg), 0u);
     return GetOperandValueImpl(s_reg, &sreg_wide_value_map_);
   }
 
@@ -300,6 +297,7 @@ class LocalValueNumbering {
   void HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index);
   void HandlePutObject(MIR* mir);
   void HandleEscapingRef(uint16_t base);
+  void HandleInvokeArgs(const MIR* mir, const LocalValueNumbering* mir_lvn);
   uint16_t HandlePhi(MIR* mir);
   uint16_t HandleAGet(MIR* mir, uint16_t opcode);
   void HandleAPut(MIR* mir, uint16_t opcode);