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
23namespace art {
24
25GlobalValueNumbering::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
44GlobalValueNumbering::~GlobalValueNumbering() {
45  STLDeleteElements(&lvns_);
46}
47
48LocalValueNumbering* 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
125bool 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
149uint16_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
163bool 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
188bool 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
204bool 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
221bool 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