global_value_numbering.cc revision 1fd4821f6b3ac57a44c2ce91025686da4641d197 
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 "local_value_numbering.h"
20
21namespace art {
22
23GlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator)
24    : cu_(cu),
25      mir_graph_(cu->mir_graph.get()),
26      allocator_(allocator),
27      bbs_processed_(0u),
28      max_bbs_to_process_(kMaxBbsToProcessMultiplyFactor * mir_graph_->GetNumReachableBlocks()),
29      last_value_(0u),
30      modifications_allowed_(false),
31      global_value_map_(std::less<uint64_t>(), allocator->Adapter()),
32      field_index_map_(FieldReferenceComparator(), allocator->Adapter()),
33      field_index_reverse_map_(allocator->Adapter()),
34      array_location_map_(ArrayLocationComparator(), allocator->Adapter()),
35      array_location_reverse_map_(allocator->Adapter()),
36      ref_set_map_(std::less<ValueNameSet>(), allocator->Adapter()),
37      lvns_(mir_graph_->GetNumBlocks(), nullptr, allocator->Adapter()),
38      work_lvn_(nullptr),
39      merge_lvns_(allocator->Adapter()) {
40}
41
42GlobalValueNumbering::~GlobalValueNumbering() {
43  STLDeleteElements(&lvns_);
44}
45
46LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb) {
47  if (UNLIKELY(!Good())) {
48    return nullptr;
49  }
50  if (UNLIKELY(bb->data_flow_info == nullptr)) {
51    return nullptr;
52  }
53  if (UNLIKELY(bb->block_type == kExitBlock)) {
54    DCHECK(bb->first_mir_insn == nullptr);
55    return nullptr;
56  }
57  if (UNLIKELY(bbs_processed_ == max_bbs_to_process_)) {
58    last_value_ = kNoValue;  // Make bad.
59    return nullptr;
60  }
61  DCHECK(work_lvn_.get() == nullptr);
62  work_lvn_.reset(new (allocator_) LocalValueNumbering(this, bb->id));
63  if (bb->block_type == kEntryBlock) {
64    if ((cu_->access_flags & kAccStatic) == 0) {
65      // If non-static method, mark "this" as non-null
66      int this_reg = cu_->num_dalvik_registers - cu_->num_ins;
67      work_lvn_->SetSRegNullChecked(this_reg);
68    }
69  } else {
70    // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member.
71    DCHECK(merge_lvns_.empty());
72    // If we're running the full GVN, the RepeatingTopologicalSortIterator keeps the loop
73    // head stack in the MIRGraph up to date and for a loop head we need to check whether
74    // we're making the initial computation and need to merge only preceding blocks in the
75    // topological order, or we're recalculating a loop head and need to merge all incoming
76    // LVNs. When we're not at a loop head (including having an empty loop head stack) all
77    // predecessors should be preceding blocks and we shall merge all of them anyway.
78    //
79    // If we're running the modification phase of the full GVN, the loop head stack will be
80    // empty and we need to merge all incoming LVNs. If we're running just a simple LVN,
81    // the loop head stack will also be empty and there will be nothing to merge anyway.
82    bool use_all_predecessors = true;
83    uint16_t loop_head_idx = 0u;  // Used only if !use_all_predecessors.
84    if (mir_graph_->GetTopologicalSortOrderLoopHeadStack()->Size() != 0) {
85      // Full GVN inside a loop, see if we're at the loop head for the first time.
86      auto top = mir_graph_->GetTopologicalSortOrderLoopHeadStack()->Peek();
87      loop_head_idx = top.first;
88      bool recalculating = top.second;
89      use_all_predecessors = recalculating ||
90          loop_head_idx != mir_graph_->GetTopologicalSortOrderIndexes()->Get(bb->id);
91    }
92    GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
93    for (BasicBlock* pred_bb = mir_graph_->GetBasicBlock(iter.Next());
94         pred_bb != nullptr; pred_bb = mir_graph_->GetBasicBlock(iter.Next())) {
95      if (lvns_[pred_bb->id] != nullptr &&
96          (use_all_predecessors ||
97              mir_graph_->GetTopologicalSortOrderIndexes()->Get(pred_bb->id) < loop_head_idx)) {
98        merge_lvns_.push_back(lvns_[pred_bb->id]);
99      }
100    }
101    // Determine merge type.
102    LocalValueNumbering::MergeType merge_type = LocalValueNumbering::kNormalMerge;
103    if (bb->catch_entry) {
104      merge_type = LocalValueNumbering::kCatchMerge;
105    } else if (bb->last_mir_insn != nullptr &&
106        (bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_VOID ||
107         bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN ||
108         bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_OBJECT ||
109         bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_WIDE) &&
110        (bb->first_mir_insn == bb->last_mir_insn ||
111         (static_cast<int>(bb->first_mir_insn->dalvikInsn.opcode) == kMirOpPhi &&
112          (bb->first_mir_insn->next == bb->last_mir_insn ||
113           (static_cast<int>(bb->first_mir_insn->next->dalvikInsn.opcode) == kMirOpPhi &&
114            bb->first_mir_insn->next->next == bb->last_mir_insn))))) {
115      merge_type = LocalValueNumbering::kReturnMerge;
116    }
117    // At least one predecessor must have been processed before this bb.
118    CHECK(!merge_lvns_.empty());
119    if (merge_lvns_.size() == 1u) {
120      work_lvn_->MergeOne(*merge_lvns_[0], merge_type);
121      BasicBlock* pred_bb = mir_graph_->GetBasicBlock(merge_lvns_[0]->Id());
122      if (HasNullCheckLastInsn(pred_bb, bb->id)) {
123        work_lvn_->SetSRegNullChecked(pred_bb->last_mir_insn->ssa_rep->uses[0]);
124      }
125    } else {
126      work_lvn_->Merge(merge_type);
127    }
128  }
129  return work_lvn_.get();
130}
131
132bool GlobalValueNumbering::FinishBasicBlock(BasicBlock* bb) {
133  DCHECK(work_lvn_ != nullptr);
134  DCHECK_EQ(bb->id, work_lvn_->Id());
135  ++bbs_processed_;
136  merge_lvns_.clear();
137
138  std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]);
139  lvns_[bb->id] = work_lvn_.release();
140  return (old_lvn == nullptr) || !old_lvn->Equals(*lvns_[bb->id]);
141}
142
143uint16_t GlobalValueNumbering::GetFieldId(const MirFieldInfo& field_info, uint16_t type) {
144  FieldReference key = { field_info.DeclaringDexFile(), field_info.DeclaringFieldIndex(), type };
145  auto lb = field_index_map_.lower_bound(key);
146  if (lb != field_index_map_.end() && !field_index_map_.key_comp()(key, lb->first)) {
147    return lb->second;
148  }
149  DCHECK_LT(field_index_map_.size(), kNoValue);
150  uint16_t id = field_index_map_.size();
151  auto it = field_index_map_.PutBefore(lb, key, id);
152  field_index_reverse_map_.push_back(&*it);
153  return id;
154}
155
156uint16_t GlobalValueNumbering::GetArrayLocation(uint16_t base, uint16_t index) {
157  auto cmp = array_location_map_.key_comp();
158  ArrayLocation key = { base, index };
159  auto lb = array_location_map_.lower_bound(key);
160  if (lb != array_location_map_.end() && !cmp(key, lb->first)) {
161    return lb->second;
162  }
163  uint16_t location = static_cast<uint16_t>(array_location_reverse_map_.size());
164  DCHECK_EQ(location, array_location_reverse_map_.size());  // No overflow.
165  auto it = array_location_map_.PutBefore(lb, key, location);
166  array_location_reverse_map_.push_back(&*it);
167  return location;
168}
169
170bool GlobalValueNumbering::HasNullCheckLastInsn(const BasicBlock* pred_bb,
171                                                BasicBlockId succ_id) {
172  if (pred_bb->block_type != kDalvikByteCode || pred_bb->last_mir_insn == nullptr) {
173    return false;
174  }
175  Instruction::Code last_opcode = pred_bb->last_mir_insn->dalvikInsn.opcode;
176  return ((last_opcode == Instruction::IF_EQZ && pred_bb->fall_through == succ_id) ||
177      (last_opcode == Instruction::IF_NEZ && pred_bb->taken == succ_id));
178}
179
180bool GlobalValueNumbering::NullCheckedInAllPredecessors(
181    const ScopedArenaVector<uint16_t>& merge_names) const {
182  // Implicit parameters:
183  //   - *work_lvn: the LVN for which we're checking predecessors.
184  //   - merge_lvns_: the predecessor LVNs.
185  DCHECK_EQ(merge_lvns_.size(), merge_names.size());
186  for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) {
187    const LocalValueNumbering* pred_lvn = merge_lvns_[i];
188    uint16_t value_name = merge_names[i];
189    if (!pred_lvn->IsValueNullChecked(value_name)) {
190      // Check if the predecessor has an IF_EQZ/IF_NEZ as the last insn.
191      const BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_lvn->Id());
192      if (!HasNullCheckLastInsn(pred_bb, work_lvn_->Id())) {
193        return false;
194      }
195      // IF_EQZ/IF_NEZ checks some sreg, see if that sreg contains the value_name.
196      int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
197      if (!pred_lvn->IsSregValue(s_reg, value_name)) {
198        return false;
199      }
200    }
201  }
202  return true;
203}
204
205}  // namespace art
206