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