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 
GlobalValueNumbering(CompilationUnit * cu,ScopedArenaAllocator * allocator,Mode mode)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 
~GlobalValueNumbering()44 GlobalValueNumbering::~GlobalValueNumbering() {
45   STLDeleteElements(&lvns_);
46 }
47 
PrepareBasicBlock(BasicBlock * bb,ScopedArenaAllocator * allocator)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 
FinishBasicBlock(BasicBlock * bb)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 
GetArrayLocation(uint16_t base,uint16_t index)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 
NullCheckedInAllPredecessors(const ScopedArenaVector<uint16_t> & merge_names) const163 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 
DivZeroCheckedInAllPredecessors(const ScopedArenaVector<uint16_t> & merge_names) const188 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 
IsBlockEnteredOnTrue(uint16_t cond,BasicBlockId bb_id)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 
IsTrueInBlock(uint16_t cond,BasicBlockId bb_id)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