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/global_value_numbering.cc b/compiler/dex/global_value_numbering.cc
new file mode 100644
index 0000000..614e826
--- /dev/null
+++ b/compiler/dex/global_value_numbering.cc
@@ -0,0 +1,205 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "global_value_numbering.h"
+
+#include "local_value_numbering.h"
+
+namespace art {
+
+GlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator)
+ : cu_(cu),
+ allocator_(allocator),
+ repeat_count_(0u),
+ last_value_(0u),
+ modifications_allowed_(false),
+ global_value_map_(std::less<uint64_t>(), allocator->Adapter()),
+ field_index_map_(FieldReferenceComparator(), allocator->Adapter()),
+ field_index_reverse_map_(allocator->Adapter()),
+ array_location_map_(ArrayLocationComparator(), allocator->Adapter()),
+ array_location_reverse_map_(allocator->Adapter()),
+ ref_set_map_(std::less<ValueNameSet>(), allocator->Adapter()),
+ lvns_(cu_->mir_graph->GetNumBlocks(), nullptr, allocator->Adapter()),
+ work_lvn_(nullptr),
+ merge_lvns_(allocator->Adapter()) {
+ cu_->mir_graph->ClearAllVisitedFlags();
+}
+
+GlobalValueNumbering::~GlobalValueNumbering() {
+ STLDeleteElements(&lvns_);
+}
+
+LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb) {
+ if (UNLIKELY(!Good())) {
+ return nullptr;
+ }
+ if (bb->data_flow_info == nullptr) {
+ return nullptr;
+ }
+ if (bb->block_type == kEntryBlock) {
+ repeat_count_ += 1u;
+ if (repeat_count_ > kMaxRepeatCount) {
+ last_value_ = kNoValue; // Make bad.
+ return nullptr;
+ }
+ }
+ if (bb->block_type == kExitBlock) {
+ DCHECK(bb->first_mir_insn == nullptr);
+ return nullptr;
+ }
+ if (bb->visited) {
+ return nullptr;
+ }
+ DCHECK(work_lvn_.get() == nullptr);
+ work_lvn_.reset(new (allocator_) LocalValueNumbering(this, bb->id));
+ if (bb->block_type == kEntryBlock) {
+ if ((cu_->access_flags & kAccStatic) == 0) {
+ // If non-static method, mark "this" as non-null
+ int this_reg = cu_->num_dalvik_registers - cu_->num_ins;
+ work_lvn_->SetSRegNullChecked(this_reg);
+ }
+ } else {
+ // Merge all incoming arcs.
+ // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member.
+ DCHECK(merge_lvns_.empty());
+ GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
+ for (BasicBlock* pred_bb = cu_->mir_graph->GetBasicBlock(iter.Next());
+ pred_bb != nullptr; pred_bb = cu_->mir_graph->GetBasicBlock(iter.Next())) {
+ if (lvns_[pred_bb->id] != nullptr) {
+ merge_lvns_.push_back(lvns_[pred_bb->id]);
+ }
+ }
+ // Determine merge type.
+ LocalValueNumbering::MergeType merge_type = LocalValueNumbering::kNormalMerge;
+ if (bb->catch_entry) {
+ merge_type = LocalValueNumbering::kCatchMerge;
+ } else if (bb->last_mir_insn != nullptr &&
+ (bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN ||
+ bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_OBJECT ||
+ bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_WIDE) &&
+ (bb->first_mir_insn == bb->last_mir_insn ||
+ (bb->first_mir_insn->next == bb->last_mir_insn &&
+ static_cast<int>(bb->first_mir_insn->dalvikInsn.opcode) == kMirOpPhi))) {
+ merge_type = LocalValueNumbering::kReturnMerge;
+ }
+ // At least one predecessor must have been processed before this bb.
+ CHECK(!merge_lvns_.empty());
+ if (merge_lvns_.size() == 1u) {
+ work_lvn_->MergeOne(*merge_lvns_[0], merge_type);
+ BasicBlock* pred_bb = cu_->mir_graph->GetBasicBlock(merge_lvns_[0]->Id());
+ if (HasNullCheckLastInsn(pred_bb, bb->id)) {
+ work_lvn_->SetSRegNullChecked(pred_bb->last_mir_insn->ssa_rep->uses[0]);
+ }
+ } else {
+ work_lvn_->Merge(merge_type);
+ }
+ }
+ return work_lvn_.get();
+}
+
+bool GlobalValueNumbering::FinishBasicBlock(BasicBlock* bb) {
+ DCHECK(work_lvn_ != nullptr);
+ DCHECK(bb->id == work_lvn_->Id());
+ merge_lvns_.clear();
+
+ bool change = false;
+ // Look for a branch to self or an already processed child.
+ // (No need to repeat the LVN if all children are processed later.)
+ ChildBlockIterator iter(bb, cu_->mir_graph.get());
+ for (BasicBlock* child = iter.Next(); child != nullptr; child = iter.Next()) {
+ if (child == bb || lvns_[child->id] != nullptr) {
+ // If we found an already processed child, check if the LVN actually differs.
+ change = (lvns_[bb->id] == nullptr || !lvns_[bb->id]->Equals(*work_lvn_));
+ break;
+ }
+ }
+
+ std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]);
+ lvns_[bb->id] = work_lvn_.release();
+
+ bb->visited = true;
+ if (change) {
+ ChildBlockIterator iter(bb, cu_->mir_graph.get());
+ for (BasicBlock* child = iter.Next(); child != nullptr; child = iter.Next()) {
+ child->visited = false;
+ }
+ }
+ return change;
+}
+
+uint16_t GlobalValueNumbering::GetFieldId(const MirFieldInfo& field_info, uint16_t type) {
+ FieldReference key = { field_info.DeclaringDexFile(), field_info.DeclaringFieldIndex(), type };
+ auto lb = field_index_map_.lower_bound(key);
+ if (lb != field_index_map_.end() && !field_index_map_.key_comp()(key, lb->first)) {
+ return lb->second;
+ }
+ DCHECK_LT(field_index_map_.size(), kNoValue);
+ uint16_t id = field_index_map_.size();
+ auto it = field_index_map_.PutBefore(lb, key, id);
+ field_index_reverse_map_.push_back(&*it);
+ return id;
+}
+
+uint16_t GlobalValueNumbering::GetArrayLocation(uint16_t base, uint16_t index) {
+ auto cmp = array_location_map_.key_comp();
+ ArrayLocation key = { base, index };
+ auto lb = array_location_map_.lower_bound(key);
+ if (lb != array_location_map_.end() && !cmp(key, lb->first)) {
+ return lb->second;
+ }
+ uint16_t location = static_cast<uint16_t>(array_location_reverse_map_.size());
+ DCHECK_EQ(location, array_location_reverse_map_.size()); // No overflow.
+ auto it = array_location_map_.PutBefore(lb, key, location);
+ array_location_reverse_map_.push_back(&*it);
+ return location;
+}
+
+bool GlobalValueNumbering::HasNullCheckLastInsn(const BasicBlock* pred_bb,
+ BasicBlockId succ_id) {
+ if (pred_bb->block_type != kDalvikByteCode || pred_bb->last_mir_insn == nullptr) {
+ return false;
+ }
+ Instruction::Code last_opcode = pred_bb->last_mir_insn->dalvikInsn.opcode;
+ return ((last_opcode == Instruction::IF_EQZ && pred_bb->fall_through == succ_id) ||
+ (last_opcode == Instruction::IF_NEZ && pred_bb->taken == succ_id));
+}
+
+bool GlobalValueNumbering::NullCheckedInAllPredecessors(
+ const ScopedArenaVector<uint16_t>& merge_names) const {
+ // Implicit parameters:
+ // - *work_lvn: the LVN for which we're checking predecessors.
+ // - merge_lvns_: the predecessor LVNs.
+ DCHECK_EQ(merge_lvns_.size(), merge_names.size());
+ for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) {
+ const LocalValueNumbering* pred_lvn = merge_lvns_[i];
+ uint16_t value_name = merge_names[i];
+ if (!pred_lvn->IsValueNullChecked(value_name)) {
+ // Check if the predecessor has an IF_EQZ/IF_NEZ as the last insn.
+ const BasicBlock* pred_bb = cu_->mir_graph->GetBasicBlock(pred_lvn->Id());
+ if (!HasNullCheckLastInsn(pred_bb, work_lvn_->Id())) {
+ return false;
+ }
+ // IF_EQZ/IF_NEZ checks some sreg, see if that sreg contains the value_name.
+ int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
+ if (!pred_lvn->IsSregValue(s_reg, value_name)) {
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+} // namespace art