Global Value Numbering.
Implement the Global Value Numbering for optimization
purposes. Use it for the null check and range check
elimination as the LVN used to do.
The order of evaluation of basic blocks needs improving as
we currently fail to recognize some obviously identical
values in methods with more than one loop. (There are three
disabled tests that check this. This is just a missed
optimization, not a correctness issue.)
Change-Id: I0d0ce16b2495b5a3b17ad1b2b32931cd69f5a25a
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 6566e03..dc1057f 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -15,8 +15,10 @@
*/
#include "compiler_internals.h"
+#include "global_value_numbering.h"
#include "local_value_numbering.h"
#include "dataflow_iterator-inl.h"
+#include "dex/global_value_numbering.h"
#include "dex/quick/dex_file_method_inliner.h"
#include "dex/quick/dex_file_to_method_inliner_map.h"
#include "utils/scoped_arena_containers.h"
@@ -318,12 +320,15 @@
if (bb->block_type == kDead) {
return true;
}
- bool use_lvn = bb->use_lvn;
+ // Don't do a separate LVN if we did the GVN.
+ bool use_lvn = bb->use_lvn && (cu_->disable_opt & (1 << kGlobalValueNumbering)) != 0;
std::unique_ptr<ScopedArenaAllocator> allocator;
+ std::unique_ptr<GlobalValueNumbering> global_valnum;
std::unique_ptr<LocalValueNumbering> local_valnum;
if (use_lvn) {
allocator.reset(ScopedArenaAllocator::Create(&cu_->arena_stack));
- local_valnum.reset(new (allocator.get()) LocalValueNumbering(cu_, allocator.get()));
+ global_valnum.reset(new (allocator.get()) GlobalValueNumbering(cu_, allocator.get()));
+ local_valnum.reset(new (allocator.get()) LocalValueNumbering(global_valnum.get(), bb->id));
}
while (bb != NULL) {
for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
@@ -558,7 +563,7 @@
}
bb = ((cu_->disable_opt & (1 << kSuppressExceptionEdges)) != 0) ? NextDominatedBlock(bb) : NULL;
}
- if (use_lvn && UNLIKELY(!local_valnum->Good())) {
+ if (use_lvn && UNLIKELY(!global_valnum->Good())) {
LOG(WARNING) << "LVN overflow in " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
}
@@ -1136,6 +1141,60 @@
temp_scoped_alloc_.reset();
}
+bool MIRGraph::ApplyGlobalValueNumberingGate() {
+ if ((cu_->disable_opt & (1 << kGlobalValueNumbering)) != 0) {
+ return false;
+ }
+
+ if ((merged_df_flags_ & DF_LVN) == 0) {
+ return false;
+ }
+
+ DCHECK(temp_scoped_alloc_ == nullptr);
+ temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack));
+ DCHECK(temp_gvn_ == nullptr);
+ temp_gvn_.reset(
+ new (temp_scoped_alloc_.get()) GlobalValueNumbering(cu_, temp_scoped_alloc_.get()));
+ return true;
+}
+
+bool MIRGraph::ApplyGlobalValueNumbering(BasicBlock* bb) {
+ DCHECK(temp_gvn_ != nullptr);
+ LocalValueNumbering* lvn = temp_gvn_->PrepareBasicBlock(bb);
+ if (lvn != nullptr) {
+ for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
+ lvn->GetValueNumber(mir);
+ }
+ }
+ bool change = (lvn != nullptr) && temp_gvn_->FinishBasicBlock(bb);
+ return change;
+}
+
+void MIRGraph::ApplyGlobalValueNumberingEnd() {
+ // Perform modifications.
+ if (temp_gvn_->Good()) {
+ temp_gvn_->AllowModifications();
+ PreOrderDfsIterator iter(this);
+ for (BasicBlock* bb = iter.Next(); bb != nullptr; bb = iter.Next()) {
+ LocalValueNumbering* lvn = temp_gvn_->PrepareBasicBlock(bb);
+ if (lvn != nullptr) {
+ for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
+ lvn->GetValueNumber(mir);
+ }
+ bool change = temp_gvn_->FinishBasicBlock(bb);
+ DCHECK(!change);
+ }
+ }
+ } else {
+ LOG(WARNING) << "GVN failed for " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
+ }
+
+ DCHECK(temp_gvn_ != nullptr);
+ temp_gvn_.reset();
+ DCHECK(temp_scoped_alloc_ != nullptr);
+ temp_scoped_alloc_.reset();
+}
+
void MIRGraph::ComputeInlineIFieldLoweringInfo(uint16_t field_idx, MIR* invoke, MIR* iget_or_iput) {
uint32_t method_index = invoke->meta.method_lowering_info;
if (temp_bit_vector_->IsBitSet(method_index)) {