1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "global_value_numbering.h" 18 19 #include "base/bit_vector-inl.h" 20 #include "base/stl_util.h" 21 #include "local_value_numbering.h" 22 23 namespace art { 24 25 GlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator, 26 Mode mode) 27 : cu_(cu), 28 mir_graph_(cu->mir_graph.get()), 29 allocator_(allocator), 30 bbs_processed_(0u), 31 max_bbs_to_process_(kMaxBbsToProcessMultiplyFactor * mir_graph_->GetNumReachableBlocks()), 32 last_value_(kNullValue), 33 modifications_allowed_(true), 34 mode_(mode), 35 global_value_map_(std::less<uint64_t>(), allocator->Adapter()), 36 array_location_map_(ArrayLocationComparator(), allocator->Adapter()), 37 array_location_reverse_map_(allocator->Adapter()), 38 ref_set_map_(std::less<ValueNameSet>(), allocator->Adapter()), 39 lvns_(mir_graph_->GetNumBlocks(), nullptr, allocator->Adapter()), 40 work_lvn_(nullptr), 41 merge_lvns_(allocator->Adapter()) { 42 } 43 44 GlobalValueNumbering::~GlobalValueNumbering() { 45 STLDeleteElements(&lvns_); 46 } 47 48 LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb, 49 ScopedArenaAllocator* allocator) { 50 if (UNLIKELY(!Good())) { 51 return nullptr; 52 } 53 if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock) { 54 DCHECK(bb->first_mir_insn == nullptr); 55 return nullptr; 56 } 57 if (mode_ == kModeGvn && UNLIKELY(bbs_processed_ == max_bbs_to_process_)) { 58 // If we're still trying to converge, stop now. Otherwise, proceed to apply optimizations. 59 last_value_ = kNoValue; // Make bad. 60 return nullptr; 61 } 62 if (mode_ == kModeGvnPostProcessing && 63 mir_graph_->GetTopologicalSortOrderLoopHeadStack()->empty()) { 64 // Modifications outside loops are performed during the main phase. 65 return nullptr; 66 } 67 if (allocator == nullptr) { 68 allocator = allocator_; 69 } 70 DCHECK(work_lvn_.get() == nullptr); 71 work_lvn_.reset(new (allocator) LocalValueNumbering(this, bb->id, allocator)); 72 if (bb->block_type == kEntryBlock) { 73 work_lvn_->PrepareEntryBlock(); 74 DCHECK(bb->first_mir_insn == nullptr); // modifications_allowed_ is irrelevant. 75 } else { 76 // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member. 77 DCHECK(merge_lvns_.empty()); 78 // If we're running the full GVN, the RepeatingTopologicalSortIterator keeps the loop 79 // head stack in the MIRGraph up to date and for a loop head we need to check whether 80 // we're making the initial computation and need to merge only preceding blocks in the 81 // topological order, or we're recalculating a loop head and need to merge all incoming 82 // LVNs. When we're not at a loop head (including having an empty loop head stack) all 83 // predecessors should be preceding blocks and we shall merge all of them anyway. 84 bool use_all_predecessors = true; 85 uint16_t loop_head_idx = 0u; // Used only if !use_all_predecessors. 86 if (mode_ == kModeGvn && mir_graph_->GetTopologicalSortOrderLoopHeadStack()->size() != 0) { 87 // Full GVN inside a loop, see if we're at the loop head for the first time. 88 modifications_allowed_ = false; 89 auto top = mir_graph_->GetTopologicalSortOrderLoopHeadStack()->back(); 90 loop_head_idx = top.first; 91 bool recalculating = top.second; 92 use_all_predecessors = recalculating || 93 loop_head_idx != mir_graph_->GetTopologicalSortOrderIndexes()[bb->id]; 94 } else { 95 modifications_allowed_ = true; 96 } 97 for (BasicBlockId pred_id : bb->predecessors) { 98 DCHECK_NE(pred_id, NullBasicBlockId); 99 if (lvns_[pred_id] != nullptr && 100 (use_all_predecessors || 101 mir_graph_->GetTopologicalSortOrderIndexes()[pred_id] < loop_head_idx)) { 102 merge_lvns_.push_back(lvns_[pred_id]); 103 } 104 } 105 // Determine merge type. 106 LocalValueNumbering::MergeType merge_type = LocalValueNumbering::kNormalMerge; 107 if (bb->catch_entry) { 108 merge_type = LocalValueNumbering::kCatchMerge; 109 } else if (bb->last_mir_insn != nullptr && 110 IsInstructionReturn(bb->last_mir_insn->dalvikInsn.opcode) && 111 bb->GetFirstNonPhiInsn() == bb->last_mir_insn) { 112 merge_type = LocalValueNumbering::kReturnMerge; 113 } 114 // At least one predecessor must have been processed before this bb. 115 CHECK(!merge_lvns_.empty()); 116 if (merge_lvns_.size() == 1u) { 117 work_lvn_->MergeOne(*merge_lvns_[0], merge_type); 118 } else { 119 work_lvn_->Merge(merge_type); 120 } 121 } 122 return work_lvn_.get(); 123 } 124 125 bool GlobalValueNumbering::FinishBasicBlock(BasicBlock* bb) { 126 DCHECK(work_lvn_ != nullptr); 127 DCHECK_EQ(bb->id, work_lvn_->Id()); 128 ++bbs_processed_; 129 merge_lvns_.clear(); 130 131 bool change = false; 132 if (mode_ == kModeGvn) { 133 change = (lvns_[bb->id] == nullptr) || !lvns_[bb->id]->Equals(*work_lvn_); 134 // In GVN mode, keep the latest LVN even if Equals() indicates no change. This is 135 // to keep the correct values of fields that do not contribute to Equals() as long 136 // as they depend only on predecessor LVNs' fields that do contribute to Equals(). 137 // Currently, that's LVN::merge_map_ used by LVN::GetStartingVregValueNumberImpl(). 138 std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]); 139 lvns_[bb->id] = work_lvn_.release(); 140 } else { 141 DCHECK_EQ(mode_, kModeGvnPostProcessing); // kModeLvn doesn't use FinishBasicBlock(). 142 DCHECK(lvns_[bb->id] != nullptr); 143 DCHECK(lvns_[bb->id]->Equals(*work_lvn_)); 144 work_lvn_.reset(); 145 } 146 return change; 147 } 148 149 uint16_t GlobalValueNumbering::GetArrayLocation(uint16_t base, uint16_t index) { 150 auto cmp = array_location_map_.key_comp(); 151 ArrayLocation key = { base, index }; 152 auto lb = array_location_map_.lower_bound(key); 153 if (lb != array_location_map_.end() && !cmp(key, lb->first)) { 154 return lb->second; 155 } 156 uint16_t location = static_cast<uint16_t>(array_location_reverse_map_.size()); 157 DCHECK_EQ(location, array_location_reverse_map_.size()); // No overflow. 158 auto it = array_location_map_.PutBefore(lb, key, location); 159 array_location_reverse_map_.push_back(&*it); 160 return location; 161 } 162 163 bool GlobalValueNumbering::NullCheckedInAllPredecessors( 164 const ScopedArenaVector<uint16_t>& merge_names) const { 165 // Implicit parameters: 166 // - *work_lvn_: the LVN for which we're checking predecessors. 167 // - merge_lvns_: the predecessor LVNs. 168 DCHECK_EQ(merge_lvns_.size(), merge_names.size()); 169 for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) { 170 const LocalValueNumbering* pred_lvn = merge_lvns_[i]; 171 uint16_t value_name = merge_names[i]; 172 if (!pred_lvn->IsValueNullChecked(value_name)) { 173 // Check if the predecessor has an IF_EQZ/IF_NEZ as the last insn. 174 const BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_lvn->Id()); 175 if (!HasNullCheckLastInsn(pred_bb, work_lvn_->Id())) { 176 return false; 177 } 178 // IF_EQZ/IF_NEZ checks some sreg, see if that sreg contains the value_name. 179 int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0]; 180 if (pred_lvn->GetSregValue(s_reg) != value_name) { 181 return false; 182 } 183 } 184 } 185 return true; 186 } 187 188 bool GlobalValueNumbering::DivZeroCheckedInAllPredecessors( 189 const ScopedArenaVector<uint16_t>& merge_names) const { 190 // Implicit parameters: 191 // - *work_lvn_: the LVN for which we're checking predecessors. 192 // - merge_lvns_: the predecessor LVNs. 193 DCHECK_EQ(merge_lvns_.size(), merge_names.size()); 194 for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) { 195 const LocalValueNumbering* pred_lvn = merge_lvns_[i]; 196 uint16_t value_name = merge_names[i]; 197 if (!pred_lvn->IsValueDivZeroChecked(value_name)) { 198 return false; 199 } 200 } 201 return true; 202 } 203 204 bool GlobalValueNumbering::IsBlockEnteredOnTrue(uint16_t cond, BasicBlockId bb_id) { 205 DCHECK_NE(cond, kNoValue); 206 BasicBlock* bb = mir_graph_->GetBasicBlock(bb_id); 207 if (bb->predecessors.size() == 1u) { 208 BasicBlockId pred_id = bb->predecessors[0]; 209 BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_id); 210 if (pred_bb->BranchesToSuccessorOnlyIfNotZero(bb_id)) { 211 DCHECK(lvns_[pred_id] != nullptr); 212 uint16_t operand = lvns_[pred_id]->GetSregValue(pred_bb->last_mir_insn->ssa_rep->uses[0]); 213 if (operand == cond) { 214 return true; 215 } 216 } 217 } 218 return false; 219 } 220 221 bool GlobalValueNumbering::IsTrueInBlock(uint16_t cond, BasicBlockId bb_id) { 222 // We're not doing proper value propagation, so just see if the condition is used 223 // with if-nez/if-eqz to branch/fall-through to this bb or one of its dominators. 224 DCHECK_NE(cond, kNoValue); 225 if (IsBlockEnteredOnTrue(cond, bb_id)) { 226 return true; 227 } 228 BasicBlock* bb = mir_graph_->GetBasicBlock(bb_id); 229 for (uint32_t dom_id : bb->dominators->Indexes()) { 230 if (IsBlockEnteredOnTrue(cond, dom_id)) { 231 return true; 232 } 233 } 234 return false; 235 } 236 237 } // namespace art 238
