Improve GVN performance when merging null-checked values.
And ignore the limit on maximum number of processed basic
blocks once the GVN has actually converged and we're just
applying optimizations.
Bug: 16398693
Change-Id: Ie5aa0386ea4e0e9ae2bbf13963e2424e1713b22f
diff --git a/compiler/dex/global_value_numbering.cc b/compiler/dex/global_value_numbering.cc
index d7ef6f0..3575ade 100644
--- a/compiler/dex/global_value_numbering.cc
+++ b/compiler/dex/global_value_numbering.cc
@@ -56,8 +56,11 @@
return nullptr;
}
if (UNLIKELY(bbs_processed_ == max_bbs_to_process_)) {
- last_value_ = kNoValue; // Make bad.
- return nullptr;
+ // If we're still trying to converge, stop now. Otherwise, proceed to apply optimizations.
+ if (!modifications_allowed_) {
+ last_value_ = kNoValue; // Make bad.
+ return nullptr;
+ }
}
if (allocator == nullptr) {
allocator = allocator_;
diff --git a/compiler/dex/global_value_numbering.h b/compiler/dex/global_value_numbering.h
index c06ff6f..1a38692 100644
--- a/compiler/dex/global_value_numbering.h
+++ b/compiler/dex/global_value_numbering.h
@@ -214,7 +214,7 @@
static constexpr uint32_t kMaxBbsToProcessMultiplyFactor = 20u;
uint32_t bbs_processed_;
- uint32_t max_bbs_to_process_;
+ uint32_t max_bbs_to_process_; // Doesn't apply after the main GVN has converged.
// We have 32-bit last_value_ so that we can detect when we run out of value names, see Good().
// We usually don't check Good() until the end of LVN unless we're about to modify code.
diff --git a/compiler/dex/local_value_numbering.cc b/compiler/dex/local_value_numbering.cc
index 5997568..8b02269 100644
--- a/compiler/dex/local_value_numbering.cc
+++ b/compiler/dex/local_value_numbering.cc
@@ -656,13 +656,37 @@
}
}
-void LocalValueNumbering::MergeNullChecked(const ValueNameSet::value_type& entry,
- ValueNameSet::iterator hint) {
- // Merge null_checked_ for this ref.
- merge_names_.clear();
- merge_names_.resize(gvn_->merge_lvns_.size(), entry);
- if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
- null_checked_.insert(hint, entry);
+void LocalValueNumbering::MergeNullChecked() {
+ DCHECK_GE(gvn_->merge_lvns_.size(), 2u);
+
+ // Find the LVN with the least entries in the set.
+ const LocalValueNumbering* least_entries_lvn = gvn_->merge_lvns_[0];
+ for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
+ if (lvn->null_checked_.size() < least_entries_lvn->null_checked_.size()) {
+ least_entries_lvn = lvn;
+ }
+ }
+
+ // For each null-checked value name check if it's null-checked in all the LVNs.
+ for (const auto& value_name : least_entries_lvn->null_checked_) {
+ // Merge null_checked_ for this ref.
+ merge_names_.clear();
+ merge_names_.resize(gvn_->merge_lvns_.size(), value_name);
+ if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
+ null_checked_.insert(null_checked_.end(), value_name);
+ }
+ }
+
+ // Now check if the least_entries_lvn has a null-check as the last insn.
+ 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);
+ merge_names_.clear();
+ merge_names_.resize(gvn_->merge_lvns_.size(), value_name);
+ if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
+ null_checked_.insert(value_name);
+ }
}
}
@@ -896,8 +920,7 @@
IntersectSets<RangeCheckSet, &LocalValueNumbering::range_checked_>();
// Merge null_checked_. We may later insert more, such as merged object field values.
- MergeSets<ValueNameSet, &LocalValueNumbering::null_checked_,
- &LocalValueNumbering::MergeNullChecked>();
+ MergeNullChecked();
if (merge_type == kCatchMerge) {
// Memory is clobbered. New memory version already created, don't merge aliasing locations.
diff --git a/compiler/dex/local_value_numbering.h b/compiler/dex/local_value_numbering.h
index 855d66d..f6a454b 100644
--- a/compiler/dex/local_value_numbering.h
+++ b/compiler/dex/local_value_numbering.h
@@ -343,11 +343,11 @@
EscapedIFieldClobberSet::iterator hint);
void MergeEscapedArrayClobberSets(const EscapedArrayClobberSet::value_type& entry,
EscapedArrayClobberSet::iterator hint);
- void MergeNullChecked(const ValueNameSet::value_type& entry, ValueNameSet::iterator hint);
void MergeSFieldValues(const SFieldToValueMap::value_type& entry,
SFieldToValueMap::iterator hint);
void MergeNonAliasingIFieldValues(const IFieldLocToValueMap::value_type& entry,
IFieldLocToValueMap::iterator hint);
+ void MergeNullChecked();
template <typename Map, Map LocalValueNumbering::*map_ptr, typename Versions>
void MergeAliasingValues(const typename Map::value_type& entry, typename Map::iterator hint);