global_value_numbering.cc revision 26e7d454b9924f3673b075b05e4c604ad658a062
195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko/* 295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * Copyright (C) 2014 The Android Open Source Project 395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * 495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * Licensed under the Apache License, Version 2.0 (the "License"); 595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * you may not use this file except in compliance with the License. 695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * You may obtain a copy of the License at 795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * 895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * http://www.apache.org/licenses/LICENSE-2.0 995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * 1095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * Unless required by applicable law or agreed to in writing, software 1195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * distributed under the License is distributed on an "AS IS" BASIS, 1295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * See the License for the specific language governing permissions and 1495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko * limitations under the License. 1595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko */ 1695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 1795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko#include "global_value_numbering.h" 1895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko#include "local_value_numbering.h" 1995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 2095a059793c4c194f026afc74c713cc295d75d91aVladimir Markonamespace art { 2195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 22415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir MarkoGlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator, 23415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko Mode mode) 2495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko : cu_(cu), 2555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko mir_graph_(cu->mir_graph.get()), 2695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko allocator_(allocator), 2755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bbs_processed_(0u), 2855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko max_bbs_to_process_(kMaxBbsToProcessMultiplyFactor * mir_graph_->GetNumReachableBlocks()), 2995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko last_value_(0u), 30415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko modifications_allowed_(true), 31415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko mode_(mode), 3295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko global_value_map_(std::less<uint64_t>(), allocator->Adapter()), 3395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko array_location_map_(ArrayLocationComparator(), allocator->Adapter()), 3495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko array_location_reverse_map_(allocator->Adapter()), 3595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko ref_set_map_(std::less<ValueNameSet>(), allocator->Adapter()), 3655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko lvns_(mir_graph_->GetNumBlocks(), nullptr, allocator->Adapter()), 3795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko work_lvn_(nullptr), 3895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko merge_lvns_(allocator->Adapter()) { 3995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 4095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 4195a059793c4c194f026afc74c713cc295d75d91aVladimir MarkoGlobalValueNumbering::~GlobalValueNumbering() { 4295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko STLDeleteElements(&lvns_); 4395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 4495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 45b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir MarkoLocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb, 46b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko ScopedArenaAllocator* allocator) { 4795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (UNLIKELY(!Good())) { 4895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return nullptr; 4995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 50415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock) { 5195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK(bb->first_mir_insn == nullptr); 5295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return nullptr; 5395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 54415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (mode_ == kModeGvn && UNLIKELY(bbs_processed_ == max_bbs_to_process_)) { 552d2365cdaa54583b47c18a6506ccd0fd723ab6d0Vladimir Marko // If we're still trying to converge, stop now. Otherwise, proceed to apply optimizations. 56415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko last_value_ = kNoValue; // Make bad. 57415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko return nullptr; 58415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko } 59415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (mode_ == kModeGvnPostProcessing && 60415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko mir_graph_->GetTopologicalSortOrderLoopHeadStack()->empty()) { 61415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko // Modifications outside loops are performed during the main phase. 62415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko return nullptr; 6395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 64b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko if (allocator == nullptr) { 65b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko allocator = allocator_; 66b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko } 6795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK(work_lvn_.get() == nullptr); 68b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko work_lvn_.reset(new (allocator) LocalValueNumbering(this, bb->id, allocator)); 6995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (bb->block_type == kEntryBlock) { 70a4426cff8a81e6af05aa8cc44c162110ccf2d397Vladimir Marko work_lvn_->PrepareEntryBlock(); 71415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko DCHECK(bb->first_mir_insn == nullptr); // modifications_allowed_ is irrelevant. 7295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } else { 7395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member. 7495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK(merge_lvns_.empty()); 7555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // If we're running the full GVN, the RepeatingTopologicalSortIterator keeps the loop 7655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // head stack in the MIRGraph up to date and for a loop head we need to check whether 7755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // we're making the initial computation and need to merge only preceding blocks in the 7855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // topological order, or we're recalculating a loop head and need to merge all incoming 7955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // LVNs. When we're not at a loop head (including having an empty loop head stack) all 8055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // predecessors should be preceding blocks and we shall merge all of them anyway. 8155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bool use_all_predecessors = true; 8255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko uint16_t loop_head_idx = 0u; // Used only if !use_all_predecessors. 83415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (mode_ == kModeGvn && mir_graph_->GetTopologicalSortOrderLoopHeadStack()->size() != 0) { 8455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Full GVN inside a loop, see if we're at the loop head for the first time. 85415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko modifications_allowed_ = false; 86e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko auto top = mir_graph_->GetTopologicalSortOrderLoopHeadStack()->back(); 8755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_idx = top.first; 8855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bool recalculating = top.second; 8955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko use_all_predecessors = recalculating || 90e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko loop_head_idx != mir_graph_->GetTopologicalSortOrderIndexes()[bb->id]; 91415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko } else { 92415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko modifications_allowed_ = true; 9355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 94e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko for (BasicBlockId pred_id : bb->predecessors) { 95e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko DCHECK_NE(pred_id, NullBasicBlockId); 96e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko if (lvns_[pred_id] != nullptr && 9755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko (use_all_predecessors || 98e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko mir_graph_->GetTopologicalSortOrderIndexes()[pred_id] < loop_head_idx)) { 99e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko merge_lvns_.push_back(lvns_[pred_id]); 10095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 10195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 10295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // Determine merge type. 10395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko LocalValueNumbering::MergeType merge_type = LocalValueNumbering::kNormalMerge; 10495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (bb->catch_entry) { 10595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko merge_type = LocalValueNumbering::kCatchMerge; 10695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } else if (bb->last_mir_insn != nullptr && 10755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko (bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_VOID || 10855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN || 10995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_OBJECT || 11095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_WIDE) && 11126e7d454b9924f3673b075b05e4c604ad658a062Vladimir Marko bb->GetFirstNonPhiInsn() == bb->last_mir_insn) { 11295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko merge_type = LocalValueNumbering::kReturnMerge; 11395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 11495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // At least one predecessor must have been processed before this bb. 11595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko CHECK(!merge_lvns_.empty()); 11695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (merge_lvns_.size() == 1u) { 11795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko work_lvn_->MergeOne(*merge_lvns_[0], merge_type); 11895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } else { 11995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko work_lvn_->Merge(merge_type); 12095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 12195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 12295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return work_lvn_.get(); 12395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 12495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 12595a059793c4c194f026afc74c713cc295d75d91aVladimir Markobool GlobalValueNumbering::FinishBasicBlock(BasicBlock* bb) { 12695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK(work_lvn_ != nullptr); 12755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK_EQ(bb->id, work_lvn_->Id()); 12855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ++bbs_processed_; 12995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko merge_lvns_.clear(); 13095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 131b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko bool change = (lvns_[bb->id] == nullptr) || !lvns_[bb->id]->Equals(*work_lvn_); 132b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko if (change) { 133b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]); 134b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko lvns_[bb->id] = work_lvn_.release(); 135b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko } else { 136b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko work_lvn_.reset(); 137b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko } 138b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko return change; 13995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 14095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 14195a059793c4c194f026afc74c713cc295d75d91aVladimir Markouint16_t GlobalValueNumbering::GetArrayLocation(uint16_t base, uint16_t index) { 14295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko auto cmp = array_location_map_.key_comp(); 14395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko ArrayLocation key = { base, index }; 14495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko auto lb = array_location_map_.lower_bound(key); 14595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (lb != array_location_map_.end() && !cmp(key, lb->first)) { 14695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return lb->second; 14795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 14895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko uint16_t location = static_cast<uint16_t>(array_location_reverse_map_.size()); 14995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK_EQ(location, array_location_reverse_map_.size()); // No overflow. 15095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko auto it = array_location_map_.PutBefore(lb, key, location); 15195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko array_location_reverse_map_.push_back(&*it); 15295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return location; 15395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 15495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 15595a059793c4c194f026afc74c713cc295d75d91aVladimir Markobool GlobalValueNumbering::HasNullCheckLastInsn(const BasicBlock* pred_bb, 15695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko BasicBlockId succ_id) { 15795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (pred_bb->block_type != kDalvikByteCode || pred_bb->last_mir_insn == nullptr) { 15895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return false; 15995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 16095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko Instruction::Code last_opcode = pred_bb->last_mir_insn->dalvikInsn.opcode; 16195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return ((last_opcode == Instruction::IF_EQZ && pred_bb->fall_through == succ_id) || 16295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko (last_opcode == Instruction::IF_NEZ && pred_bb->taken == succ_id)); 16395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 16495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 16595a059793c4c194f026afc74c713cc295d75d91aVladimir Markobool GlobalValueNumbering::NullCheckedInAllPredecessors( 16695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko const ScopedArenaVector<uint16_t>& merge_names) const { 16795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // Implicit parameters: 16895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // - *work_lvn: the LVN for which we're checking predecessors. 16995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // - merge_lvns_: the predecessor LVNs. 17095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK_EQ(merge_lvns_.size(), merge_names.size()); 17195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) { 17295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko const LocalValueNumbering* pred_lvn = merge_lvns_[i]; 17395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko uint16_t value_name = merge_names[i]; 17495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (!pred_lvn->IsValueNullChecked(value_name)) { 17595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // Check if the predecessor has an IF_EQZ/IF_NEZ as the last insn. 17655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko const BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_lvn->Id()); 17795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (!HasNullCheckLastInsn(pred_bb, work_lvn_->Id())) { 17895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return false; 17995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 18095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // IF_EQZ/IF_NEZ checks some sreg, see if that sreg contains the value_name. 18195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0]; 18295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (!pred_lvn->IsSregValue(s_reg, value_name)) { 18395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return false; 18495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 18595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 18695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 18795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return true; 18895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 18995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 19095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} // namespace art 191