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" 180b9203e7996ee1856f620f95d95d8a273c43a3dfAndreas Gampe 1922fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko#include "base/bit_vector-inl.h" 200b9203e7996ee1856f620f95d95d8a273c43a3dfAndreas Gampe#include "base/stl_util.h" 2195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko#include "local_value_numbering.h" 2295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 2395a059793c4c194f026afc74c713cc295d75d91aVladimir Markonamespace art { 2495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 25415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir MarkoGlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator, 26415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko Mode mode) 2795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko : cu_(cu), 2855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko mir_graph_(cu->mir_graph.get()), 2995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko allocator_(allocator), 3055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bbs_processed_(0u), 3155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko max_bbs_to_process_(kMaxBbsToProcessMultiplyFactor * mir_graph_->GetNumReachableBlocks()), 327a01dc2107d4255b445c32867d15d45fcebb3acdVladimir Marko last_value_(kNullValue), 33415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko modifications_allowed_(true), 34415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko mode_(mode), 3595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko global_value_map_(std::less<uint64_t>(), allocator->Adapter()), 3695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko array_location_map_(ArrayLocationComparator(), allocator->Adapter()), 3795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko array_location_reverse_map_(allocator->Adapter()), 3895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko ref_set_map_(std::less<ValueNameSet>(), allocator->Adapter()), 3955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko lvns_(mir_graph_->GetNumBlocks(), nullptr, allocator->Adapter()), 4095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko work_lvn_(nullptr), 4195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko merge_lvns_(allocator->Adapter()) { 4295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 4395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 4495a059793c4c194f026afc74c713cc295d75d91aVladimir MarkoGlobalValueNumbering::~GlobalValueNumbering() { 4595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko STLDeleteElements(&lvns_); 4695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 4795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 48b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir MarkoLocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb, 49b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko ScopedArenaAllocator* allocator) { 5095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (UNLIKELY(!Good())) { 5195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return nullptr; 5295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 53415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock) { 5495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK(bb->first_mir_insn == nullptr); 5595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return nullptr; 5695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 57415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (mode_ == kModeGvn && UNLIKELY(bbs_processed_ == max_bbs_to_process_)) { 582d2365cdaa54583b47c18a6506ccd0fd723ab6d0Vladimir Marko // If we're still trying to converge, stop now. Otherwise, proceed to apply optimizations. 59415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko last_value_ = kNoValue; // Make bad. 60415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko return nullptr; 61415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko } 62415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (mode_ == kModeGvnPostProcessing && 63415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko mir_graph_->GetTopologicalSortOrderLoopHeadStack()->empty()) { 64415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko // Modifications outside loops are performed during the main phase. 65415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko return nullptr; 6695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 67b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko if (allocator == nullptr) { 68b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko allocator = allocator_; 69b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko } 7095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK(work_lvn_.get() == nullptr); 71b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko work_lvn_.reset(new (allocator) LocalValueNumbering(this, bb->id, allocator)); 7295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (bb->block_type == kEntryBlock) { 73a4426cff8a81e6af05aa8cc44c162110ccf2d397Vladimir Marko work_lvn_->PrepareEntryBlock(); 74415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko DCHECK(bb->first_mir_insn == nullptr); // modifications_allowed_ is irrelevant. 7595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } else { 7695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member. 7795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK(merge_lvns_.empty()); 7855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // If we're running the full GVN, the RepeatingTopologicalSortIterator keeps the loop 7955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // head stack in the MIRGraph up to date and for a loop head we need to check whether 8055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // we're making the initial computation and need to merge only preceding blocks in the 8155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // topological order, or we're recalculating a loop head and need to merge all incoming 8255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // LVNs. When we're not at a loop head (including having an empty loop head stack) all 8355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // predecessors should be preceding blocks and we shall merge all of them anyway. 8455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bool use_all_predecessors = true; 8555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko uint16_t loop_head_idx = 0u; // Used only if !use_all_predecessors. 86415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko if (mode_ == kModeGvn && mir_graph_->GetTopologicalSortOrderLoopHeadStack()->size() != 0) { 8755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Full GVN inside a loop, see if we're at the loop head for the first time. 88415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko modifications_allowed_ = false; 89e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko auto top = mir_graph_->GetTopologicalSortOrderLoopHeadStack()->back(); 9055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_idx = top.first; 9155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bool recalculating = top.second; 9255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko use_all_predecessors = recalculating || 93e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko loop_head_idx != mir_graph_->GetTopologicalSortOrderIndexes()[bb->id]; 94415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko } else { 95415ac88a6471792a28cf2b457fe4ba9dc099396eVladimir Marko modifications_allowed_ = true; 9655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 97e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko for (BasicBlockId pred_id : bb->predecessors) { 98e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko DCHECK_NE(pred_id, NullBasicBlockId); 99e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko if (lvns_[pred_id] != nullptr && 10055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko (use_all_predecessors || 101e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko mir_graph_->GetTopologicalSortOrderIndexes()[pred_id] < loop_head_idx)) { 102e39c54ea575ec710d5e84277fcdcc049f8acb3c9Vladimir Marko merge_lvns_.push_back(lvns_[pred_id]); 10395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 10495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 10595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // Determine merge type. 10695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko LocalValueNumbering::MergeType merge_type = LocalValueNumbering::kNormalMerge; 10795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (bb->catch_entry) { 10895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko merge_type = LocalValueNumbering::kCatchMerge; 10995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } else if (bb->last_mir_insn != nullptr && 110321b987ef037c44c0ed4e0e82661c88959a6239fVladimir Marko IsInstructionReturn(bb->last_mir_insn->dalvikInsn.opcode) && 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 131be8f57d3a5ff121f1056791ed0910435c834b211Vladimir Marko bool change = false; 1327a01dc2107d4255b445c32867d15d45fcebb3acdVladimir Marko if (mode_ == kModeGvn) { 133be8f57d3a5ff121f1056791ed0910435c834b211Vladimir Marko change = (lvns_[bb->id] == nullptr) || !lvns_[bb->id]->Equals(*work_lvn_); 1347a01dc2107d4255b445c32867d15d45fcebb3acdVladimir Marko // In GVN mode, keep the latest LVN even if Equals() indicates no change. This is 1357a01dc2107d4255b445c32867d15d45fcebb3acdVladimir Marko // to keep the correct values of fields that do not contribute to Equals() as long 1367a01dc2107d4255b445c32867d15d45fcebb3acdVladimir Marko // as they depend only on predecessor LVNs' fields that do contribute to Equals(). 1377a01dc2107d4255b445c32867d15d45fcebb3acdVladimir Marko // Currently, that's LVN::merge_map_ used by LVN::GetStartingVregValueNumberImpl(). 138b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]); 139b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko lvns_[bb->id] = work_lvn_.release(); 140b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko } else { 141be8f57d3a5ff121f1056791ed0910435c834b211Vladimir Marko DCHECK_EQ(mode_, kModeGvnPostProcessing); // kModeLvn doesn't use FinishBasicBlock(). 142be8f57d3a5ff121f1056791ed0910435c834b211Vladimir Marko DCHECK(lvns_[bb->id] != nullptr); 143be8f57d3a5ff121f1056791ed0910435c834b211Vladimir Marko DCHECK(lvns_[bb->id]->Equals(*work_lvn_)); 144b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko work_lvn_.reset(); 145b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko } 146b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko return change; 14795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 14895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 14995a059793c4c194f026afc74c713cc295d75d91aVladimir Markouint16_t GlobalValueNumbering::GetArrayLocation(uint16_t base, uint16_t index) { 15095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko auto cmp = array_location_map_.key_comp(); 15195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko ArrayLocation key = { base, index }; 15295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko auto lb = array_location_map_.lower_bound(key); 15395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (lb != array_location_map_.end() && !cmp(key, lb->first)) { 15495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return lb->second; 15595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 15695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko uint16_t location = static_cast<uint16_t>(array_location_reverse_map_.size()); 15795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK_EQ(location, array_location_reverse_map_.size()); // No overflow. 15895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko auto it = array_location_map_.PutBefore(lb, key, location); 15995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko array_location_reverse_map_.push_back(&*it); 16095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return location; 16195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 16295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 16395a059793c4c194f026afc74c713cc295d75d91aVladimir Markobool GlobalValueNumbering::NullCheckedInAllPredecessors( 16495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko const ScopedArenaVector<uint16_t>& merge_names) const { 16595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // Implicit parameters: 1669f7687cb5c1390ec4bcc2f8fa10dbee33aff3d6aVladimir Marko // - *work_lvn_: the LVN for which we're checking predecessors. 16795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // - merge_lvns_: the predecessor LVNs. 16895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko DCHECK_EQ(merge_lvns_.size(), merge_names.size()); 16995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) { 17095a059793c4c194f026afc74c713cc295d75d91aVladimir Marko const LocalValueNumbering* pred_lvn = merge_lvns_[i]; 17195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko uint16_t value_name = merge_names[i]; 17295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (!pred_lvn->IsValueNullChecked(value_name)) { 17395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // Check if the predecessor has an IF_EQZ/IF_NEZ as the last insn. 17455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko const BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_lvn->Id()); 17595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko if (!HasNullCheckLastInsn(pred_bb, work_lvn_->Id())) { 17695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return false; 17795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 17895a059793c4c194f026afc74c713cc295d75d91aVladimir Marko // IF_EQZ/IF_NEZ checks some sreg, see if that sreg contains the value_name. 17995a059793c4c194f026afc74c713cc295d75d91aVladimir Marko int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0]; 1807a01dc2107d4255b445c32867d15d45fcebb3acdVladimir Marko if (pred_lvn->GetSregValue(s_reg) != value_name) { 18195a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return false; 18295a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 18395a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 18495a059793c4c194f026afc74c713cc295d75d91aVladimir Marko } 18595a059793c4c194f026afc74c713cc295d75d91aVladimir Marko return true; 18695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} 18795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko 188e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusorubool GlobalValueNumbering::DivZeroCheckedInAllPredecessors( 189e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru const ScopedArenaVector<uint16_t>& merge_names) const { 190e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru // Implicit parameters: 1919f7687cb5c1390ec4bcc2f8fa10dbee33aff3d6aVladimir Marko // - *work_lvn_: the LVN for which we're checking predecessors. 192e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru // - merge_lvns_: the predecessor LVNs. 193e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru DCHECK_EQ(merge_lvns_.size(), merge_names.size()); 194e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) { 195e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru const LocalValueNumbering* pred_lvn = merge_lvns_[i]; 196e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru uint16_t value_name = merge_names[i]; 197e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru if (!pred_lvn->IsValueDivZeroChecked(value_name)) { 198e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru return false; 199e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru } 200e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru } 201e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru return true; 202e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru} 203e0951144d71a4791a5319ec507d84fce373018e0Razvan A Lupusoru 20422fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Markobool GlobalValueNumbering::IsBlockEnteredOnTrue(uint16_t cond, BasicBlockId bb_id) { 20522fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko DCHECK_NE(cond, kNoValue); 20622fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko BasicBlock* bb = mir_graph_->GetBasicBlock(bb_id); 20722fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko if (bb->predecessors.size() == 1u) { 20822fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko BasicBlockId pred_id = bb->predecessors[0]; 20922fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_id); 2109f7687cb5c1390ec4bcc2f8fa10dbee33aff3d6aVladimir Marko if (pred_bb->BranchesToSuccessorOnlyIfNotZero(bb_id)) { 2119f7687cb5c1390ec4bcc2f8fa10dbee33aff3d6aVladimir Marko DCHECK(lvns_[pred_id] != nullptr); 2129f7687cb5c1390ec4bcc2f8fa10dbee33aff3d6aVladimir Marko uint16_t operand = lvns_[pred_id]->GetSregValue(pred_bb->last_mir_insn->ssa_rep->uses[0]); 2139f7687cb5c1390ec4bcc2f8fa10dbee33aff3d6aVladimir Marko if (operand == cond) { 2149f7687cb5c1390ec4bcc2f8fa10dbee33aff3d6aVladimir Marko return true; 21522fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko } 21622fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko } 21722fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko } 21822fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko return false; 21922fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko} 22022fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko 22122fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Markobool GlobalValueNumbering::IsTrueInBlock(uint16_t cond, BasicBlockId bb_id) { 22222fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko // We're not doing proper value propagation, so just see if the condition is used 22322fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko // with if-nez/if-eqz to branch/fall-through to this bb or one of its dominators. 22422fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko DCHECK_NE(cond, kNoValue); 22522fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko if (IsBlockEnteredOnTrue(cond, bb_id)) { 22622fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko return true; 22722fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko } 22822fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko BasicBlock* bb = mir_graph_->GetBasicBlock(bb_id); 22922fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko for (uint32_t dom_id : bb->dominators->Indexes()) { 23022fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko if (IsBlockEnteredOnTrue(cond, dom_id)) { 23122fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko return true; 23222fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko } 23322fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko } 23422fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko return false; 23522fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko} 23622fe45de11ed7afdf21400d2de3abd23f3a62800Vladimir Marko 23795a059793c4c194f026afc74c713cc295d75d91aVladimir Marko} // namespace art 238