1 /*
2  * Copyright (C) 2015 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 <sstream>
18 
19 #include "gvn_dead_code_elimination.h"
20 
21 #include "base/bit_vector-inl.h"
22 #include "base/macros.h"
23 #include "base/allocator.h"
24 #include "compiler_enums.h"
25 #include "dataflow_iterator-inl.h"
26 #include "dex_instruction.h"
27 #include "dex/mir_graph.h"
28 #include "local_value_numbering.h"
29 #include "utils/arena_bit_vector.h"
30 
31 namespace art {
32 
33 constexpr uint16_t GvnDeadCodeElimination::kNoValue;
34 constexpr uint16_t GvnDeadCodeElimination::kNPos;
35 
PrevChange(int v_reg) const36 inline uint16_t GvnDeadCodeElimination::MIRData::PrevChange(int v_reg) const {
37   DCHECK(has_def);
38   DCHECK(v_reg == vreg_def || v_reg == vreg_def + 1);
39   return (v_reg == vreg_def) ? prev_value.change : prev_value_high.change;
40 }
41 
SetPrevChange(int v_reg,uint16_t change)42 inline void GvnDeadCodeElimination::MIRData::SetPrevChange(int v_reg, uint16_t change) {
43   DCHECK(has_def);
44   DCHECK(v_reg == vreg_def || v_reg == vreg_def + 1);
45   if (v_reg == vreg_def) {
46     prev_value.change = change;
47   } else {
48     prev_value_high.change = change;
49   }
50 }
51 
RemovePrevChange(int v_reg,MIRData * prev_data)52 inline void GvnDeadCodeElimination::MIRData::RemovePrevChange(int v_reg, MIRData* prev_data) {
53   DCHECK_NE(PrevChange(v_reg), kNPos);
54   DCHECK(v_reg == prev_data->vreg_def || v_reg == prev_data->vreg_def + 1);
55   if (vreg_def == v_reg) {
56     if (prev_data->vreg_def == v_reg) {
57       prev_value = prev_data->prev_value;
58       low_def_over_high_word = prev_data->low_def_over_high_word;
59     } else {
60       prev_value = prev_data->prev_value_high;
61       low_def_over_high_word = !prev_data->high_def_over_low_word;
62     }
63   } else {
64     if (prev_data->vreg_def == v_reg) {
65       prev_value_high = prev_data->prev_value;
66       high_def_over_low_word = !prev_data->low_def_over_high_word;
67     } else {
68       prev_value_high = prev_data->prev_value_high;
69       high_def_over_low_word = prev_data->high_def_over_low_word;
70     }
71   }
72 }
73 
VRegChains(uint32_t num_vregs,ScopedArenaAllocator * alloc)74 GvnDeadCodeElimination::VRegChains::VRegChains(uint32_t num_vregs, ScopedArenaAllocator* alloc)
75     : num_vregs_(num_vregs),
76       vreg_data_(alloc->AllocArray<VRegValue>(num_vregs, kArenaAllocMisc)),
77       vreg_high_words_(false, Allocator::GetNoopAllocator(),
78                        BitVector::BitsToWords(num_vregs),
79                        alloc->AllocArray<uint32_t>(BitVector::BitsToWords(num_vregs))),
80       mir_data_(alloc->Adapter()) {
81   mir_data_.reserve(100);
82 }
83 
Reset()84 inline void GvnDeadCodeElimination::VRegChains::Reset() {
85   DCHECK(mir_data_.empty());
86   std::fill_n(vreg_data_, num_vregs_, VRegValue());
87   vreg_high_words_.ClearAllBits();
88 }
89 
AddMIRWithDef(MIR * mir,int v_reg,bool wide,uint16_t new_value)90 void GvnDeadCodeElimination::VRegChains::AddMIRWithDef(MIR* mir, int v_reg, bool wide,
91                                                        uint16_t new_value) {
92   uint16_t pos = mir_data_.size();
93   mir_data_.emplace_back(mir);
94   MIRData* data = &mir_data_.back();
95   data->has_def = true;
96   data->wide_def = wide;
97   data->vreg_def = v_reg;
98 
99   DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
100   data->prev_value = vreg_data_[v_reg];
101   data->low_def_over_high_word =
102       (vreg_data_[v_reg].change != kNPos)
103       ? GetMIRData(vreg_data_[v_reg].change)->vreg_def + 1 == v_reg
104       : vreg_high_words_.IsBitSet(v_reg);
105   vreg_data_[v_reg].value = new_value;
106   vreg_data_[v_reg].change = pos;
107   vreg_high_words_.ClearBit(v_reg);
108 
109   if (wide) {
110     DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
111     data->prev_value_high = vreg_data_[v_reg + 1];
112     data->high_def_over_low_word =
113         (vreg_data_[v_reg + 1].change != kNPos)
114         ? GetMIRData(vreg_data_[v_reg + 1].change)->vreg_def == v_reg + 1
115         : !vreg_high_words_.IsBitSet(v_reg + 1);
116     vreg_data_[v_reg + 1].value = new_value;
117     vreg_data_[v_reg + 1].change = pos;
118     vreg_high_words_.SetBit(v_reg + 1);
119   }
120 }
121 
AddMIRWithoutDef(MIR * mir)122 inline void GvnDeadCodeElimination::VRegChains::AddMIRWithoutDef(MIR* mir) {
123   mir_data_.emplace_back(mir);
124 }
125 
RemoveLastMIRData()126 void GvnDeadCodeElimination::VRegChains::RemoveLastMIRData() {
127   MIRData* data = LastMIRData();
128   if (data->has_def) {
129     DCHECK_EQ(vreg_data_[data->vreg_def].change, NumMIRs() - 1u);
130     vreg_data_[data->vreg_def] = data->prev_value;
131     DCHECK(!vreg_high_words_.IsBitSet(data->vreg_def));
132     if (data->low_def_over_high_word) {
133       vreg_high_words_.SetBit(data->vreg_def);
134     }
135     if (data->wide_def) {
136       DCHECK_EQ(vreg_data_[data->vreg_def + 1].change, NumMIRs() - 1u);
137       vreg_data_[data->vreg_def + 1] = data->prev_value_high;
138       DCHECK(vreg_high_words_.IsBitSet(data->vreg_def + 1));
139       if (data->high_def_over_low_word) {
140         vreg_high_words_.ClearBit(data->vreg_def + 1);
141       }
142     }
143   }
144   mir_data_.pop_back();
145 }
146 
RemoveTrailingNops()147 void GvnDeadCodeElimination::VRegChains::RemoveTrailingNops() {
148   // There's at least one NOP to drop. There may be more.
149   MIRData* last_data = LastMIRData();
150   DCHECK(!last_data->must_keep && !last_data->has_def);
151   do {
152     DCHECK_EQ(static_cast<int>(last_data->mir->dalvikInsn.opcode), static_cast<int>(kMirOpNop));
153     mir_data_.pop_back();
154     if (mir_data_.empty()) {
155       break;
156     }
157     last_data = LastMIRData();
158   } while (!last_data->must_keep && !last_data->has_def);
159 }
160 
NumMIRs() const161 inline size_t GvnDeadCodeElimination::VRegChains::NumMIRs() const {
162   return mir_data_.size();
163 }
164 
GetMIRData(size_t pos)165 inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::GetMIRData(size_t pos) {
166   DCHECK_LT(pos, mir_data_.size());
167   return &mir_data_[pos];
168 }
169 
LastMIRData()170 inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::LastMIRData() {
171   DCHECK(!mir_data_.empty());
172   return &mir_data_.back();
173 }
174 
NumVRegs() const175 uint32_t GvnDeadCodeElimination::VRegChains::NumVRegs() const {
176   return num_vregs_;
177 }
178 
InsertInitialValueHigh(int v_reg,uint16_t value)179 void GvnDeadCodeElimination::VRegChains::InsertInitialValueHigh(int v_reg, uint16_t value) {
180   DCHECK_NE(value, kNoValue);
181   DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
182   uint16_t change = vreg_data_[v_reg].change;
183   if (change == kNPos) {
184     vreg_data_[v_reg].value = value;
185     vreg_high_words_.SetBit(v_reg);
186   } else {
187     while (true) {
188       MIRData* data = &mir_data_[change];
189       DCHECK(data->vreg_def == v_reg || data->vreg_def + 1 == v_reg);
190       if (data->vreg_def == v_reg) {  // Low word, use prev_value.
191         if (data->prev_value.change == kNPos) {
192           DCHECK_EQ(data->prev_value.value, kNoValue);
193           data->prev_value.value = value;
194           data->low_def_over_high_word = true;
195           break;
196         }
197         change = data->prev_value.change;
198       } else {  // High word, use prev_value_high.
199         if (data->prev_value_high.change == kNPos) {
200           DCHECK_EQ(data->prev_value_high.value, kNoValue);
201           data->prev_value_high.value = value;
202           break;
203         }
204         change = data->prev_value_high.change;
205       }
206     }
207   }
208 }
209 
UpdateInitialVRegValue(int v_reg,bool wide,const LocalValueNumbering * lvn)210 void GvnDeadCodeElimination::VRegChains::UpdateInitialVRegValue(int v_reg, bool wide,
211                                                                 const LocalValueNumbering* lvn) {
212   DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
213   if (!wide) {
214     if (vreg_data_[v_reg].value == kNoValue) {
215       uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg);
216       if (old_value == kNoValue) {
217         // Maybe there was a wide value in v_reg before. Do not check for wide value in v_reg-1,
218         // that will be done only if we see a definition of v_reg-1, otherwise it's unnecessary.
219         old_value = lvn->GetStartingVregValueNumberWide(v_reg);
220         if (old_value != kNoValue) {
221           InsertInitialValueHigh(v_reg + 1, old_value);
222         }
223       }
224       vreg_data_[v_reg].value = old_value;
225       DCHECK(!vreg_high_words_.IsBitSet(v_reg));  // Keep marked as low word.
226     }
227   } else {
228     DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
229     bool check_high = true;
230     if (vreg_data_[v_reg].value == kNoValue) {
231       uint16_t old_value = lvn->GetStartingVregValueNumberWide(v_reg);
232       if (old_value != kNoValue) {
233         InsertInitialValueHigh(v_reg + 1, old_value);
234         check_high = false;  // High word has been processed.
235       } else {
236         // Maybe there was a narrow value before. Do not check for wide value in v_reg-1,
237         // that will be done only if we see a definition of v_reg-1, otherwise it's unnecessary.
238         old_value = lvn->GetStartingVregValueNumber(v_reg);
239       }
240       vreg_data_[v_reg].value = old_value;
241       DCHECK(!vreg_high_words_.IsBitSet(v_reg));  // Keep marked as low word.
242     }
243     if (check_high && vreg_data_[v_reg + 1].value == kNoValue) {
244       uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg + 1);
245       if (old_value == kNoValue && static_cast<size_t>(v_reg + 2) < num_vregs_) {
246         // Maybe there was a wide value before.
247         old_value = lvn->GetStartingVregValueNumberWide(v_reg + 1);
248         if (old_value != kNoValue) {
249           InsertInitialValueHigh(v_reg + 2, old_value);
250         }
251       }
252       vreg_data_[v_reg + 1].value = old_value;
253       DCHECK(!vreg_high_words_.IsBitSet(v_reg + 1));  // Keep marked as low word.
254     }
255   }
256 }
257 
LastChange(int v_reg)258 inline uint16_t GvnDeadCodeElimination::VRegChains::LastChange(int v_reg) {
259   DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
260   return vreg_data_[v_reg].change;
261 }
262 
CurrentValue(int v_reg)263 inline uint16_t GvnDeadCodeElimination::VRegChains::CurrentValue(int v_reg) {
264   DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
265   return vreg_data_[v_reg].value;
266 }
267 
FindKillHead(int v_reg,uint16_t cutoff)268 uint16_t GvnDeadCodeElimination::VRegChains::FindKillHead(int v_reg, uint16_t cutoff) {
269   uint16_t current_value = this->CurrentValue(v_reg);
270   DCHECK_NE(current_value, kNoValue);
271   uint16_t change = LastChange(v_reg);
272   DCHECK_LT(change, mir_data_.size());
273   DCHECK_GE(change, cutoff);
274   bool match_high_word = (mir_data_[change].vreg_def != v_reg);
275   do {
276     MIRData* data = &mir_data_[change];
277     DCHECK(data->vreg_def == v_reg || data->vreg_def + 1 == v_reg);
278     if (data->vreg_def == v_reg) {  // Low word, use prev_value.
279       if (data->prev_value.value == current_value &&
280           match_high_word == data->low_def_over_high_word) {
281         break;
282       }
283       change = data->prev_value.change;
284     } else {  // High word, use prev_value_high.
285       if (data->prev_value_high.value == current_value &&
286           match_high_word != data->high_def_over_low_word) {
287         break;
288       }
289       change = data->prev_value_high.change;
290     }
291     if (change < cutoff) {
292       change = kNPos;
293     }
294   } while (change != kNPos);
295   return change;
296 }
297 
FindFirstChangeAfter(int v_reg,uint16_t change) const298 uint16_t GvnDeadCodeElimination::VRegChains::FindFirstChangeAfter(int v_reg,
299                                                                   uint16_t change) const {
300   DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
301   DCHECK_LT(change, mir_data_.size());
302   uint16_t result = kNPos;
303   uint16_t search_change = vreg_data_[v_reg].change;
304   while (search_change != kNPos && search_change > change) {
305     result = search_change;
306     search_change = mir_data_[search_change].PrevChange(v_reg);
307   }
308   return result;
309 }
310 
ReplaceChange(uint16_t old_change,uint16_t new_change)311 void GvnDeadCodeElimination::VRegChains::ReplaceChange(uint16_t old_change, uint16_t new_change) {
312   const MIRData* old_data = GetMIRData(old_change);
313   DCHECK(old_data->has_def);
314   int count = old_data->wide_def ? 2 : 1;
315   for (int v_reg = old_data->vreg_def, end = old_data->vreg_def + count; v_reg != end; ++v_reg) {
316     uint16_t next_change = FindFirstChangeAfter(v_reg, old_change);
317     if (next_change == kNPos) {
318       DCHECK_EQ(vreg_data_[v_reg].change, old_change);
319       vreg_data_[v_reg].change = new_change;
320       DCHECK_EQ(vreg_high_words_.IsBitSet(v_reg), v_reg == old_data->vreg_def + 1);
321       // No change in vreg_high_words_.
322     } else {
323       DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), old_change);
324       mir_data_[next_change].SetPrevChange(v_reg, new_change);
325     }
326   }
327 }
328 
RemoveChange(uint16_t change)329 void GvnDeadCodeElimination::VRegChains::RemoveChange(uint16_t change) {
330   MIRData* data = &mir_data_[change];
331   DCHECK(data->has_def);
332   int count = data->wide_def ? 2 : 1;
333   for (int v_reg = data->vreg_def, end = data->vreg_def + count; v_reg != end; ++v_reg) {
334     uint16_t next_change = FindFirstChangeAfter(v_reg, change);
335     if (next_change == kNPos) {
336       DCHECK_EQ(vreg_data_[v_reg].change, change);
337       vreg_data_[v_reg] = (data->vreg_def == v_reg) ? data->prev_value : data->prev_value_high;
338       DCHECK_EQ(vreg_high_words_.IsBitSet(v_reg), v_reg == data->vreg_def + 1);
339       if (data->vreg_def == v_reg && data->low_def_over_high_word) {
340         vreg_high_words_.SetBit(v_reg);
341       } else if (data->vreg_def != v_reg && data->high_def_over_low_word) {
342         vreg_high_words_.ClearBit(v_reg);
343       }
344     } else {
345       DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), change);
346       mir_data_[next_change].RemovePrevChange(v_reg, data);
347     }
348   }
349 }
350 
IsTopChange(uint16_t change) const351 inline bool GvnDeadCodeElimination::VRegChains::IsTopChange(uint16_t change) const {
352   DCHECK_LT(change, mir_data_.size());
353   const MIRData* data = &mir_data_[change];
354   DCHECK(data->has_def);
355   DCHECK_LT(data->wide_def ? data->vreg_def + 1u : data->vreg_def, num_vregs_);
356   return vreg_data_[data->vreg_def].change == change &&
357       (!data->wide_def || vreg_data_[data->vreg_def + 1u].change == change);
358 }
359 
IsSRegUsed(uint16_t first_change,uint16_t last_change,int s_reg) const360 bool GvnDeadCodeElimination::VRegChains::IsSRegUsed(uint16_t first_change, uint16_t last_change,
361                                                     int s_reg) const {
362   DCHECK_LE(first_change, last_change);
363   DCHECK_LE(last_change, mir_data_.size());
364   for (size_t c = first_change; c != last_change; ++c) {
365     SSARepresentation* ssa_rep = mir_data_[c].mir->ssa_rep;
366     for (int i = 0; i != ssa_rep->num_uses; ++i) {
367       if (ssa_rep->uses[i] == s_reg) {
368         return true;
369       }
370     }
371   }
372   return false;
373 }
374 
IsVRegUsed(uint16_t first_change,uint16_t last_change,int v_reg,MIRGraph * mir_graph) const375 bool GvnDeadCodeElimination::VRegChains::IsVRegUsed(uint16_t first_change, uint16_t last_change,
376                                                     int v_reg, MIRGraph* mir_graph) const {
377   DCHECK_LE(first_change, last_change);
378   DCHECK_LE(last_change, mir_data_.size());
379   for (size_t c = first_change; c != last_change; ++c) {
380     SSARepresentation* ssa_rep = mir_data_[c].mir->ssa_rep;
381     for (int i = 0; i != ssa_rep->num_uses; ++i) {
382       if (mir_graph->SRegToVReg(ssa_rep->uses[i]) == v_reg) {
383         return true;
384       }
385     }
386   }
387   return false;
388 }
389 
RenameSRegUses(uint16_t first_change,uint16_t last_change,int old_s_reg,int new_s_reg,bool wide)390 void GvnDeadCodeElimination::VRegChains::RenameSRegUses(uint16_t first_change, uint16_t last_change,
391                                                         int old_s_reg, int new_s_reg, bool wide) {
392   for (size_t c = first_change; c != last_change; ++c) {
393     SSARepresentation* ssa_rep = mir_data_[c].mir->ssa_rep;
394     for (int i = 0; i != ssa_rep->num_uses; ++i) {
395       if (ssa_rep->uses[i] == old_s_reg) {
396         ssa_rep->uses[i] = new_s_reg;
397         if (wide) {
398           ++i;
399           DCHECK_LT(i, ssa_rep->num_uses);
400           ssa_rep->uses[i] = new_s_reg + 1;
401         }
402       }
403     }
404   }
405 }
406 
RenameVRegUses(uint16_t first_change,uint16_t last_change,int old_s_reg,int old_v_reg,int new_s_reg,int new_v_reg)407 void GvnDeadCodeElimination::VRegChains::RenameVRegUses(uint16_t first_change, uint16_t last_change,
408                                                     int old_s_reg, int old_v_reg,
409                                                     int new_s_reg, int new_v_reg) {
410   for (size_t c = first_change; c != last_change; ++c) {
411     MIR* mir = mir_data_[c].mir;
412     if (IsInstructionBinOp2Addr(mir->dalvikInsn.opcode) &&
413         mir->ssa_rep->uses[0] == old_s_reg && old_v_reg != new_v_reg) {
414       // Rewrite binop_2ADDR with plain binop before doing the register rename.
415       ChangeBinOp2AddrToPlainBinOp(mir);
416     }
417     uint64_t df_attr = MIRGraph::GetDataFlowAttributes(mir);
418     size_t use = 0u;
419 #define REPLACE_VREG(REG) \
420     if ((df_attr & DF_U##REG) != 0) {                                         \
421       if (mir->ssa_rep->uses[use] == old_s_reg) {                             \
422         DCHECK_EQ(mir->dalvikInsn.v##REG, static_cast<uint32_t>(old_v_reg));  \
423         mir->dalvikInsn.v##REG = new_v_reg;                                   \
424         mir->ssa_rep->uses[use] = new_s_reg;                                  \
425         if ((df_attr & DF_##REG##_WIDE) != 0) {                               \
426           DCHECK_EQ(mir->ssa_rep->uses[use + 1], old_s_reg + 1);              \
427           mir->ssa_rep->uses[use + 1] = new_s_reg + 1;                        \
428         }                                                                     \
429       }                                                                       \
430       use += ((df_attr & DF_##REG##_WIDE) != 0) ? 2 : 1;                      \
431     }
432     REPLACE_VREG(A)
433     REPLACE_VREG(B)
434     REPLACE_VREG(C)
435 #undef REPLACE_VREG
436     // We may encounter an out-of-order Phi which we need to ignore, otherwise we should
437     // only be asked to rename registers specified by DF_UA, DF_UB and DF_UC.
438     DCHECK_EQ(use,
439               static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi
440               ? 0u
441               : static_cast<size_t>(mir->ssa_rep->num_uses));
442   }
443 }
444 
GvnDeadCodeElimination(const GlobalValueNumbering * gvn,ScopedArenaAllocator * alloc)445 GvnDeadCodeElimination::GvnDeadCodeElimination(const GlobalValueNumbering* gvn,
446                                          ScopedArenaAllocator* alloc)
447     : gvn_(gvn),
448       mir_graph_(gvn_->GetMirGraph()),
449       vreg_chains_(mir_graph_->GetNumOfCodeAndTempVRs(), alloc),
450       bb_(nullptr),
451       lvn_(nullptr),
452       no_uses_all_since_(0u),
453       unused_vregs_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)),
454       vregs_to_kill_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)),
455       kill_heads_(alloc->AllocArray<uint16_t>(vreg_chains_.NumVRegs(), kArenaAllocMisc)),
456       changes_to_kill_(alloc->Adapter()),
457       dependent_vregs_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)) {
458   changes_to_kill_.reserve(16u);
459 }
460 
Apply(BasicBlock * bb)461 void GvnDeadCodeElimination::Apply(BasicBlock* bb) {
462   bb_ = bb;
463   lvn_ = gvn_->GetLvn(bb->id);
464 
465   RecordPass();
466   BackwardPass();
467 
468   DCHECK_EQ(no_uses_all_since_, 0u);
469   lvn_ = nullptr;
470   bb_ = nullptr;
471 }
472 
RecordPass()473 void GvnDeadCodeElimination::RecordPass() {
474   // Record MIRs with vreg definition data, eliminate single instructions.
475   vreg_chains_.Reset();
476   DCHECK_EQ(no_uses_all_since_, 0u);
477   for (MIR* mir = bb_->first_mir_insn; mir != nullptr; mir = mir->next) {
478     if (RecordMIR(mir)) {
479       RecordPassTryToKillOverwrittenMoveOrMoveSrc();
480       RecordPassTryToKillLastMIR();
481     }
482   }
483 }
484 
BackwardPass()485 void GvnDeadCodeElimination::BackwardPass() {
486   // Now process MIRs in reverse order, trying to eliminate them.
487   unused_vregs_->ClearAllBits();  // Implicitly depend on all vregs at the end of BB.
488   while (vreg_chains_.NumMIRs() != 0u) {
489     if (BackwardPassTryToKillLastMIR()) {
490       continue;
491     }
492     BackwardPassProcessLastMIR();
493   }
494 }
495 
KillMIR(MIRData * data)496 void GvnDeadCodeElimination::KillMIR(MIRData* data) {
497   DCHECK(!data->must_keep);
498   DCHECK(!data->uses_all_vregs);
499   DCHECK(data->has_def);
500   DCHECK(data->mir->ssa_rep->num_defs == 1 || data->mir->ssa_rep->num_defs == 2);
501 
502   KillMIR(data->mir);
503   data->has_def = false;
504   data->is_move = false;
505   data->is_move_src = false;
506 }
507 
KillMIR(MIR * mir)508 void GvnDeadCodeElimination::KillMIR(MIR* mir) {
509   mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
510   mir->ssa_rep->num_uses = 0;
511   mir->ssa_rep->num_defs = 0;
512 }
513 
ChangeBinOp2AddrToPlainBinOp(MIR * mir)514 void GvnDeadCodeElimination::ChangeBinOp2AddrToPlainBinOp(MIR* mir) {
515   mir->dalvikInsn.vC = mir->dalvikInsn.vB;
516   mir->dalvikInsn.vB = mir->dalvikInsn.vA;
517   mir->dalvikInsn.opcode = static_cast<Instruction::Code>(
518       mir->dalvikInsn.opcode - Instruction::ADD_INT_2ADDR +  Instruction::ADD_INT);
519 }
520 
CreatePhi(int s_reg)521 MIR* GvnDeadCodeElimination::CreatePhi(int s_reg) {
522   int v_reg = mir_graph_->SRegToVReg(s_reg);
523   MIR* phi = mir_graph_->NewMIR();
524   phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi);
525   phi->dalvikInsn.vA = v_reg;
526   phi->offset = bb_->start_offset;
527   phi->m_unit_index = 0;  // Arbitrarily assign all Phi nodes to outermost method.
528 
529   phi->ssa_rep = static_cast<struct SSARepresentation *>(mir_graph_->GetArena()->Alloc(
530       sizeof(SSARepresentation), kArenaAllocDFInfo));
531 
532   mir_graph_->AllocateSSADefData(phi, 1);
533   phi->ssa_rep->defs[0] = s_reg;
534 
535   size_t num_uses = bb_->predecessors.size();
536   mir_graph_->AllocateSSAUseData(phi, num_uses);
537   size_t idx = 0u;
538   for (BasicBlockId pred_id : bb_->predecessors) {
539     BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_id);
540     DCHECK(pred_bb != nullptr);
541     phi->ssa_rep->uses[idx] = pred_bb->data_flow_info->vreg_to_ssa_map_exit[v_reg];
542     DCHECK_NE(phi->ssa_rep->uses[idx], INVALID_SREG);
543     idx++;
544   }
545 
546   phi->meta.phi_incoming = static_cast<BasicBlockId*>(mir_graph_->GetArena()->Alloc(
547       sizeof(BasicBlockId) * num_uses, kArenaAllocDFInfo));
548   std::copy(bb_->predecessors.begin(), bb_->predecessors.end(), phi->meta.phi_incoming);
549   bb_->PrependMIR(phi);
550   return phi;
551 }
552 
RenameSRegDefOrCreatePhi(uint16_t def_change,uint16_t last_change,MIR * mir_to_kill)553 MIR* GvnDeadCodeElimination::RenameSRegDefOrCreatePhi(uint16_t def_change, uint16_t last_change,
554                                                       MIR* mir_to_kill) {
555   DCHECK(mir_to_kill->ssa_rep->num_defs == 1 || mir_to_kill->ssa_rep->num_defs == 2);
556   bool wide = (mir_to_kill->ssa_rep->num_defs != 1);
557   int new_s_reg = mir_to_kill->ssa_rep->defs[0];
558 
559   // Just before we kill mir_to_kill, we need to replace the previous SSA reg assigned to the
560   // same dalvik reg to keep consistency with subsequent instructions. However, if there's no
561   // defining MIR for that dalvik reg, the preserved values must come from its predecessors
562   // and we need to create a new Phi (a degenerate Phi if there's only a single predecessor).
563   if (def_change == kNPos) {
564     if (wide) {
565       DCHECK_EQ(new_s_reg + 1, mir_to_kill->ssa_rep->defs[1]);
566       DCHECK_EQ(mir_graph_->SRegToVReg(new_s_reg) + 1, mir_graph_->SRegToVReg(new_s_reg + 1));
567       CreatePhi(new_s_reg + 1);  // High word Phi.
568     }
569     MIR* phi = CreatePhi(new_s_reg);
570     // If this is a degenerate Phi with all inputs being the same SSA reg, we need to its uses.
571     DCHECK_NE(phi->ssa_rep->num_uses, 0u);
572     int old_s_reg = phi->ssa_rep->uses[0];
573     bool all_same = true;
574     for (size_t i = 1u, num = phi->ssa_rep->num_uses; i != num; ++i) {
575       if (phi->ssa_rep->uses[i] != old_s_reg) {
576         all_same = false;
577         break;
578       }
579     }
580     if (all_same) {
581       vreg_chains_.RenameSRegUses(0u, last_change, old_s_reg, new_s_reg, wide);
582     }
583     return phi;
584   } else {
585     DCHECK_LT(def_change, last_change);
586     DCHECK_LE(last_change, vreg_chains_.NumMIRs());
587     MIRData* def_data = vreg_chains_.GetMIRData(def_change);
588     DCHECK(def_data->has_def);
589     int old_s_reg = def_data->mir->ssa_rep->defs[0];
590     DCHECK_NE(old_s_reg, new_s_reg);
591     DCHECK_EQ(mir_graph_->SRegToVReg(old_s_reg), mir_graph_->SRegToVReg(new_s_reg));
592     def_data->mir->ssa_rep->defs[0] = new_s_reg;
593     if (wide) {
594       if (static_cast<int>(def_data->mir->dalvikInsn.opcode) == kMirOpPhi) {
595         // Currently the high word Phi is always located after the low word Phi.
596         MIR* phi_high = def_data->mir->next;
597         DCHECK(phi_high != nullptr && static_cast<int>(phi_high->dalvikInsn.opcode) == kMirOpPhi);
598         DCHECK_EQ(phi_high->ssa_rep->defs[0], old_s_reg + 1);
599         phi_high->ssa_rep->defs[0] = new_s_reg + 1;
600       } else {
601         DCHECK_EQ(def_data->mir->ssa_rep->defs[1], old_s_reg + 1);
602         def_data->mir->ssa_rep->defs[1] = new_s_reg + 1;
603       }
604     }
605     vreg_chains_.RenameSRegUses(def_change + 1u, last_change, old_s_reg, new_s_reg, wide);
606     return nullptr;
607   }
608 }
609 
610 
BackwardPassProcessLastMIR()611 void GvnDeadCodeElimination::BackwardPassProcessLastMIR() {
612   MIRData* data = vreg_chains_.LastMIRData();
613   if (data->uses_all_vregs) {
614     DCHECK(data->must_keep);
615     unused_vregs_->ClearAllBits();
616     DCHECK_EQ(no_uses_all_since_, vreg_chains_.NumMIRs());
617     --no_uses_all_since_;
618     while (no_uses_all_since_ != 0u &&
619         !vreg_chains_.GetMIRData(no_uses_all_since_ - 1u)->uses_all_vregs) {
620       --no_uses_all_since_;
621     }
622   } else {
623     if (data->has_def) {
624       unused_vregs_->SetBit(data->vreg_def);
625       if (data->wide_def) {
626         unused_vregs_->SetBit(data->vreg_def + 1);
627       }
628     }
629     for (int i = 0, num_uses = data->mir->ssa_rep->num_uses; i != num_uses; ++i) {
630       int v_reg = mir_graph_->SRegToVReg(data->mir->ssa_rep->uses[i]);
631       unused_vregs_->ClearBit(v_reg);
632     }
633   }
634   vreg_chains_.RemoveLastMIRData();
635 }
636 
RecordPassKillMoveByRenamingSrcDef(uint16_t src_change,uint16_t move_change)637 void GvnDeadCodeElimination::RecordPassKillMoveByRenamingSrcDef(uint16_t src_change,
638                                                                 uint16_t move_change) {
639   DCHECK_LT(src_change, move_change);
640   MIRData* src_data = vreg_chains_.GetMIRData(src_change);
641   MIRData* move_data = vreg_chains_.GetMIRData(move_change);
642   DCHECK(src_data->is_move_src);
643   DCHECK_EQ(src_data->wide_def, move_data->wide_def);
644   DCHECK(move_data->prev_value.change == kNPos || move_data->prev_value.change <= src_change);
645   DCHECK(!move_data->wide_def || move_data->prev_value_high.change == kNPos ||
646          move_data->prev_value_high.change <= src_change);
647 
648   int old_s_reg = src_data->mir->ssa_rep->defs[0];
649   // NOTE: old_s_reg may differ from move_data->mir->ssa_rep->uses[0]; value names must match.
650   int new_s_reg = move_data->mir->ssa_rep->defs[0];
651   DCHECK_NE(old_s_reg, new_s_reg);
652 
653   if (IsInstructionBinOp2Addr(src_data->mir->dalvikInsn.opcode) &&
654       src_data->vreg_def != move_data->vreg_def) {
655     // Rewrite binop_2ADDR with plain binop before doing the register rename.
656     ChangeBinOp2AddrToPlainBinOp(src_data->mir);
657   }
658   // Remove src_change from the vreg chain(s).
659   vreg_chains_.RemoveChange(src_change);
660   // Replace the move_change with the src_change, copying all necessary data.
661   src_data->is_move_src = move_data->is_move_src;
662   src_data->low_def_over_high_word = move_data->low_def_over_high_word;
663   src_data->high_def_over_low_word = move_data->high_def_over_low_word;
664   src_data->vreg_def = move_data->vreg_def;
665   src_data->prev_value = move_data->prev_value;
666   src_data->prev_value_high = move_data->prev_value_high;
667   src_data->mir->dalvikInsn.vA = move_data->vreg_def;
668   src_data->mir->ssa_rep->defs[0] = new_s_reg;
669   if (move_data->wide_def) {
670     DCHECK_EQ(src_data->mir->ssa_rep->defs[1], old_s_reg + 1);
671     src_data->mir->ssa_rep->defs[1] = new_s_reg + 1;
672   }
673   vreg_chains_.ReplaceChange(move_change, src_change);
674 
675   // Rename uses and kill the move.
676   vreg_chains_.RenameVRegUses(src_change + 1u, vreg_chains_.NumMIRs(),
677                               old_s_reg, mir_graph_->SRegToVReg(old_s_reg),
678                               new_s_reg, mir_graph_->SRegToVReg(new_s_reg));
679   KillMIR(move_data);
680 }
681 
RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_t check_change)682 void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_t check_change) {
683   MIRData* data = vreg_chains_.GetMIRData(check_change);
684   DCHECK(data->is_move || data->is_move_src);
685   int32_t dest_s_reg = data->mir->ssa_rep->defs[0];
686 
687   if (data->is_move) {
688     // Check if source vreg has changed since the MOVE.
689     int32_t src_s_reg = data->mir->ssa_rep->uses[0];
690     uint32_t src_v_reg = mir_graph_->SRegToVReg(src_s_reg);
691     uint16_t src_change = vreg_chains_.FindFirstChangeAfter(src_v_reg, check_change);
692     bool wide = data->wide_def;
693     if (wide) {
694       uint16_t src_change_high = vreg_chains_.FindFirstChangeAfter(src_v_reg + 1, check_change);
695       if (src_change_high != kNPos && (src_change == kNPos || src_change_high < src_change)) {
696         src_change = src_change_high;
697       }
698     }
699     if (src_change == kNPos ||
700         !vreg_chains_.IsSRegUsed(src_change + 1u, vreg_chains_.NumMIRs(), dest_s_reg)) {
701       // We can simply change all uses of dest to src.
702       size_t rename_end = (src_change != kNPos) ? src_change + 1u : vreg_chains_.NumMIRs();
703       vreg_chains_.RenameVRegUses(check_change + 1u, rename_end,
704                                   dest_s_reg, mir_graph_->SRegToVReg(dest_s_reg),
705                                   src_s_reg,  mir_graph_->SRegToVReg(src_s_reg));
706 
707       // Now, remove the MOVE from the vreg chain(s) and kill it.
708       vreg_chains_.RemoveChange(check_change);
709       KillMIR(data);
710       return;
711     }
712   }
713 
714   if (data->is_move_src) {
715     // Try to find a MOVE to a vreg that wasn't changed since check_change.
716     uint16_t value_name =
717         data->wide_def ? lvn_->GetSregValueWide(dest_s_reg) : lvn_->GetSregValue(dest_s_reg);
718     uint32_t dest_v_reg = mir_graph_->SRegToVReg(dest_s_reg);
719     for (size_t c = check_change + 1u, size = vreg_chains_.NumMIRs(); c != size; ++c) {
720       MIRData* d = vreg_chains_.GetMIRData(c);
721       if (d->is_move && d->wide_def == data->wide_def &&
722           (d->prev_value.change == kNPos || d->prev_value.change <= check_change) &&
723           (!d->wide_def ||
724            d->prev_value_high.change == kNPos || d->prev_value_high.change <= check_change)) {
725         // Compare value names to find move to move.
726         int32_t src_s_reg = d->mir->ssa_rep->uses[0];
727         uint16_t src_name =
728             (d->wide_def ? lvn_->GetSregValueWide(src_s_reg) : lvn_->GetSregValue(src_s_reg));
729         if (value_name == src_name) {
730           // Check if the move's destination vreg is unused between check_change and the move.
731           uint32_t new_dest_v_reg = mir_graph_->SRegToVReg(d->mir->ssa_rep->defs[0]);
732           if (!vreg_chains_.IsVRegUsed(check_change + 1u, c, new_dest_v_reg, mir_graph_) &&
733               (!d->wide_def ||
734                !vreg_chains_.IsVRegUsed(check_change + 1u, c, new_dest_v_reg + 1, mir_graph_))) {
735             // If the move's destination vreg changed, check if the vreg we're trying
736             // to rename is unused after that change.
737             uint16_t dest_change = vreg_chains_.FindFirstChangeAfter(new_dest_v_reg, c);
738             if (d->wide_def) {
739               uint16_t dest_change_high = vreg_chains_.FindFirstChangeAfter(new_dest_v_reg + 1, c);
740               if (dest_change_high != kNPos &&
741                   (dest_change == kNPos || dest_change_high < dest_change)) {
742                 dest_change = dest_change_high;
743               }
744             }
745             if (dest_change == kNPos ||
746                 !vreg_chains_.IsVRegUsed(dest_change + 1u, size, dest_v_reg, mir_graph_)) {
747               RecordPassKillMoveByRenamingSrcDef(check_change, c);
748               return;
749             }
750           }
751         }
752       }
753     }
754   }
755 }
756 
RecordPassTryToKillOverwrittenMoveOrMoveSrc()757 void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc() {
758   // Check if we're overwriting a the result of a move or the definition of a source of a move.
759   // For MOVE_WIDE, we may be overwriting partially; if that's the case, check that the other
760   // word wasn't previously overwritten - we would have tried to rename back then.
761   MIRData* data = vreg_chains_.LastMIRData();
762   if (!data->has_def) {
763     return;
764   }
765   // NOTE: Instructions such as new-array implicitly use all vregs (if they throw) but they can
766   // define a move source which can be renamed. Therefore we allow the checked change to be the
767   // change before no_uses_all_since_. This has no effect on moves as they never use all vregs.
768   if (data->prev_value.change != kNPos && data->prev_value.change + 1u >= no_uses_all_since_) {
769     MIRData* check_data = vreg_chains_.GetMIRData(data->prev_value.change);
770     bool try_to_kill = false;
771     if (!check_data->is_move && !check_data->is_move_src) {
772       DCHECK(!try_to_kill);
773     } else if (!check_data->wide_def) {
774       // Narrow move; always fully overwritten by the last MIR.
775       try_to_kill = true;
776     } else if (data->low_def_over_high_word) {
777       // Overwriting only the high word; is the low word still valid?
778       DCHECK_EQ(check_data->vreg_def + 1u, data->vreg_def);
779       if (vreg_chains_.LastChange(check_data->vreg_def) == data->prev_value.change) {
780         try_to_kill = true;
781       }
782     } else if (!data->wide_def) {
783       // Overwriting only the low word, is the high word still valid?
784       if (vreg_chains_.LastChange(data->vreg_def + 1) == data->prev_value.change) {
785         try_to_kill = true;
786       }
787     } else {
788       // Overwriting both words; was the high word still from the same move?
789       if (data->prev_value_high.change == data->prev_value.change) {
790         try_to_kill = true;
791       }
792     }
793     if (try_to_kill) {
794       RecordPassTryToKillOverwrittenMoveOrMoveSrc(data->prev_value.change);
795     }
796   }
797   if (data->wide_def && data->high_def_over_low_word &&
798       data->prev_value_high.change != kNPos &&
799       data->prev_value_high.change + 1u >= no_uses_all_since_) {
800     MIRData* check_data = vreg_chains_.GetMIRData(data->prev_value_high.change);
801     bool try_to_kill = false;
802     if (!check_data->is_move && !check_data->is_move_src) {
803       DCHECK(!try_to_kill);
804     } else if (!check_data->wide_def) {
805       // Narrow move; always fully overwritten by the last MIR.
806       try_to_kill = true;
807     } else if (vreg_chains_.LastChange(check_data->vreg_def + 1) ==
808         data->prev_value_high.change) {
809       // High word is still valid.
810       try_to_kill = true;
811     }
812     if (try_to_kill) {
813       RecordPassTryToKillOverwrittenMoveOrMoveSrc(data->prev_value_high.change);
814     }
815   }
816 }
817 
RecordPassTryToKillLastMIR()818 void GvnDeadCodeElimination::RecordPassTryToKillLastMIR() {
819   MIRData* last_data = vreg_chains_.LastMIRData();
820   if (last_data->must_keep) {
821     return;
822   }
823   if (UNLIKELY(!last_data->has_def)) {
824     // Must be an eliminated MOVE. Drop its data and data of all eliminated MIRs before it.
825     vreg_chains_.RemoveTrailingNops();
826     return;
827   }
828 
829   // Try to kill a sequence of consecutive definitions of the same vreg. Allow mixing
830   // wide and non-wide defs; consider high word dead if low word has been overwritten.
831   uint16_t current_value = vreg_chains_.CurrentValue(last_data->vreg_def);
832   uint16_t change = vreg_chains_.NumMIRs() - 1u;
833   MIRData* data = last_data;
834   while (data->prev_value.value != current_value) {
835     --change;
836     if (data->prev_value.change == kNPos || data->prev_value.change != change) {
837       return;
838     }
839     data = vreg_chains_.GetMIRData(data->prev_value.change);
840     if (data->must_keep || !data->has_def || data->vreg_def != last_data->vreg_def) {
841       return;
842     }
843   }
844 
845   bool wide = last_data->wide_def;
846   if (wide) {
847     // Check that the low word is valid.
848     if (data->low_def_over_high_word) {
849       return;
850     }
851     // Check that the high word is valid.
852     MIRData* high_data = data;
853     if (!high_data->wide_def) {
854       uint16_t high_change = vreg_chains_.FindFirstChangeAfter(data->vreg_def + 1, change);
855       DCHECK_NE(high_change, kNPos);
856       high_data = vreg_chains_.GetMIRData(high_change);
857       DCHECK_EQ(high_data->vreg_def, data->vreg_def);
858     }
859     if (high_data->prev_value_high.value != current_value || high_data->high_def_over_low_word) {
860       return;
861     }
862   }
863 
864   MIR* phi = RenameSRegDefOrCreatePhi(data->prev_value.change, change, last_data->mir);
865   for (size_t i = 0, count = vreg_chains_.NumMIRs() - change; i != count; ++i) {
866     KillMIR(vreg_chains_.LastMIRData()->mir);
867     vreg_chains_.RemoveLastMIRData();
868   }
869   if (phi != nullptr) {
870     // Though the Phi has been added to the beginning, we can put the MIRData at the end.
871     vreg_chains_.AddMIRWithDef(phi, phi->dalvikInsn.vA, wide, current_value);
872     // Reset the previous value to avoid eventually eliminating the Phi itself (unless unused).
873     last_data = vreg_chains_.LastMIRData();
874     last_data->prev_value.value = kNoValue;
875     last_data->prev_value_high.value = kNoValue;
876   }
877 }
878 
FindChangesToKill(uint16_t first_change,uint16_t last_change)879 uint16_t GvnDeadCodeElimination::FindChangesToKill(uint16_t first_change, uint16_t last_change) {
880   // Process dependencies for changes in range [first_change, last_change) and record all
881   // changes that we need to kill. Return kNPos if there's a dependent change that must be
882   // kept unconditionally; otherwise the end of the range processed before encountering
883   // a change that defines a dalvik reg that we need to keep (last_change on full success).
884   changes_to_kill_.clear();
885   dependent_vregs_->ClearAllBits();
886   for (size_t change = first_change; change != last_change; ++change) {
887     MIRData* data = vreg_chains_.GetMIRData(change);
888     DCHECK(!data->uses_all_vregs);
889     bool must_not_depend = data->must_keep;
890     bool depends = false;
891     // Check if the MIR defines a vreg we're trying to eliminate.
892     if (data->has_def && vregs_to_kill_->IsBitSet(data->vreg_def)) {
893       if (change < kill_heads_[data->vreg_def]) {
894         must_not_depend = true;
895       } else {
896         depends = true;
897       }
898     }
899     if (data->has_def && data->wide_def && vregs_to_kill_->IsBitSet(data->vreg_def + 1)) {
900       if (change < kill_heads_[data->vreg_def + 1]) {
901         must_not_depend = true;
902       } else {
903         depends = true;
904       }
905     }
906     if (!depends) {
907       // Check for dependency through SSA reg uses.
908       SSARepresentation* ssa_rep = data->mir->ssa_rep;
909       for (int i = 0; i != ssa_rep->num_uses; ++i) {
910         if (dependent_vregs_->IsBitSet(mir_graph_->SRegToVReg(ssa_rep->uses[i]))) {
911           depends = true;
912           break;
913         }
914       }
915     }
916     // Now check if we can eliminate the insn if we need to.
917     if (depends && must_not_depend) {
918       return kNPos;
919     }
920     if (depends && data->has_def &&
921         vreg_chains_.IsTopChange(change) && !vregs_to_kill_->IsBitSet(data->vreg_def) &&
922         !unused_vregs_->IsBitSet(data->vreg_def) &&
923         (!data->wide_def || !unused_vregs_->IsBitSet(data->vreg_def + 1))) {
924       // This is a top change but neither unnecessary nor one of the top kill changes.
925       return change;
926     }
927     // Finally, update the data.
928     if (depends) {
929       changes_to_kill_.push_back(change);
930       if (data->has_def) {
931         dependent_vregs_->SetBit(data->vreg_def);
932         if (data->wide_def) {
933           dependent_vregs_->SetBit(data->vreg_def + 1);
934         }
935       }
936     } else {
937       if (data->has_def) {
938         dependent_vregs_->ClearBit(data->vreg_def);
939         if (data->wide_def) {
940           dependent_vregs_->ClearBit(data->vreg_def + 1);
941         }
942       }
943     }
944   }
945   return last_change;
946 }
947 
BackwardPassTryToKillRevertVRegs()948 void GvnDeadCodeElimination::BackwardPassTryToKillRevertVRegs() {
949 }
950 
BackwardPassTryToKillLastMIR()951 bool GvnDeadCodeElimination::BackwardPassTryToKillLastMIR() {
952   MIRData* last_data = vreg_chains_.LastMIRData();
953   if (last_data->must_keep) {
954     return false;
955   }
956   DCHECK(!last_data->uses_all_vregs);
957   if (!last_data->has_def) {
958     // Previously eliminated.
959     DCHECK_EQ(static_cast<int>(last_data->mir->dalvikInsn.opcode), static_cast<int>(kMirOpNop));
960     vreg_chains_.RemoveTrailingNops();
961     return true;
962   }
963   if (unused_vregs_->IsBitSet(last_data->vreg_def) ||
964       (last_data->wide_def && unused_vregs_->IsBitSet(last_data->vreg_def + 1))) {
965     if (last_data->wide_def) {
966       // For wide defs, one of the vregs may still be considered needed, fix that.
967       unused_vregs_->SetBit(last_data->vreg_def);
968       unused_vregs_->SetBit(last_data->vreg_def + 1);
969     }
970     KillMIR(last_data->mir);
971     vreg_chains_.RemoveLastMIRData();
972     return true;
973   }
974 
975   vregs_to_kill_->ClearAllBits();
976   size_t num_mirs = vreg_chains_.NumMIRs();
977   DCHECK_NE(num_mirs, 0u);
978   uint16_t kill_change = num_mirs - 1u;
979   uint16_t start = num_mirs;
980   size_t num_killed_top_changes = 0u;
981   while (num_killed_top_changes != kMaxNumTopChangesToKill &&
982       kill_change != kNPos && kill_change != num_mirs) {
983     ++num_killed_top_changes;
984 
985     DCHECK(vreg_chains_.IsTopChange(kill_change));
986     MIRData* data = vreg_chains_.GetMIRData(kill_change);
987     int count = data->wide_def ? 2 : 1;
988     for (int v_reg = data->vreg_def, end = data->vreg_def + count; v_reg != end; ++v_reg) {
989       uint16_t kill_head = vreg_chains_.FindKillHead(v_reg, no_uses_all_since_);
990       if (kill_head == kNPos) {
991         return false;
992       }
993       kill_heads_[v_reg] = kill_head;
994       vregs_to_kill_->SetBit(v_reg);
995       start = std::min(start, kill_head);
996     }
997     DCHECK_LT(start, vreg_chains_.NumMIRs());
998 
999     kill_change = FindChangesToKill(start, num_mirs);
1000   }
1001 
1002   if (kill_change != num_mirs) {
1003     return false;
1004   }
1005 
1006   // Kill all MIRs marked as dependent.
1007   for (uint32_t v_reg : vregs_to_kill_->Indexes()) {
1008     // Rename s_regs or create Phi only once for each MIR (only for low word).
1009     MIRData* data = vreg_chains_.GetMIRData(vreg_chains_.LastChange(v_reg));
1010     DCHECK(data->has_def);
1011     if (data->vreg_def == v_reg) {
1012       MIRData* kill_head_data = vreg_chains_.GetMIRData(kill_heads_[v_reg]);
1013       RenameSRegDefOrCreatePhi(kill_head_data->PrevChange(v_reg), num_mirs, data->mir);
1014     } else {
1015       DCHECK_EQ(data->vreg_def + 1u, v_reg);
1016       DCHECK_EQ(vreg_chains_.GetMIRData(kill_heads_[v_reg - 1u])->PrevChange(v_reg - 1u),
1017                 vreg_chains_.GetMIRData(kill_heads_[v_reg])->PrevChange(v_reg));
1018     }
1019   }
1020   for (auto it = changes_to_kill_.rbegin(), end = changes_to_kill_.rend(); it != end; ++it) {
1021     MIRData* data = vreg_chains_.GetMIRData(*it);
1022     DCHECK(!data->must_keep);
1023     DCHECK(data->has_def);
1024     vreg_chains_.RemoveChange(*it);
1025     KillMIR(data);
1026   }
1027 
1028   // Each dependent register not in vregs_to_kill_ is either already marked unused or
1029   // it's one word of a wide register where the other word has been overwritten.
1030   unused_vregs_->UnionIfNotIn(dependent_vregs_, vregs_to_kill_);
1031 
1032   vreg_chains_.RemoveTrailingNops();
1033   return true;
1034 }
1035 
RecordMIR(MIR * mir)1036 bool GvnDeadCodeElimination::RecordMIR(MIR* mir) {
1037   bool must_keep = false;
1038   bool uses_all_vregs = false;
1039   bool is_move = false;
1040   uint16_t opcode = mir->dalvikInsn.opcode;
1041   switch (opcode) {
1042     case kMirOpPhi: {
1043       // Determine if this Phi is merging wide regs.
1044       RegLocation raw_dest = gvn_->GetMirGraph()->GetRawDest(mir);
1045       if (raw_dest.high_word) {
1046         // This is the high part of a wide reg. Ignore the Phi.
1047         return false;
1048       }
1049       bool wide = raw_dest.wide;
1050       // Record the value.
1051       DCHECK_EQ(mir->ssa_rep->num_defs, 1);
1052       int s_reg = mir->ssa_rep->defs[0];
1053       uint16_t new_value = wide ? lvn_->GetSregValueWide(s_reg) : lvn_->GetSregValue(s_reg);
1054 
1055       int v_reg = mir_graph_->SRegToVReg(s_reg);
1056       DCHECK_EQ(vreg_chains_.CurrentValue(v_reg), kNoValue);  // No previous def for v_reg.
1057       if (wide) {
1058         DCHECK_EQ(vreg_chains_.CurrentValue(v_reg + 1), kNoValue);
1059       }
1060       vreg_chains_.AddMIRWithDef(mir, v_reg, wide, new_value);
1061       return true;  // Avoid the common processing.
1062     }
1063 
1064     case kMirOpNop:
1065     case Instruction::NOP:
1066       // Don't record NOPs.
1067       return false;
1068 
1069     case kMirOpCheck:
1070       must_keep = true;
1071       uses_all_vregs = true;
1072       break;
1073 
1074     case Instruction::RETURN_VOID:
1075     case Instruction::RETURN:
1076     case Instruction::RETURN_OBJECT:
1077     case Instruction::RETURN_WIDE:
1078     case Instruction::GOTO:
1079     case Instruction::GOTO_16:
1080     case Instruction::GOTO_32:
1081     case Instruction::PACKED_SWITCH:
1082     case Instruction::SPARSE_SWITCH:
1083     case Instruction::IF_EQ:
1084     case Instruction::IF_NE:
1085     case Instruction::IF_LT:
1086     case Instruction::IF_GE:
1087     case Instruction::IF_GT:
1088     case Instruction::IF_LE:
1089     case Instruction::IF_EQZ:
1090     case Instruction::IF_NEZ:
1091     case Instruction::IF_LTZ:
1092     case Instruction::IF_GEZ:
1093     case Instruction::IF_GTZ:
1094     case Instruction::IF_LEZ:
1095     case kMirOpFusedCmplFloat:
1096     case kMirOpFusedCmpgFloat:
1097     case kMirOpFusedCmplDouble:
1098     case kMirOpFusedCmpgDouble:
1099     case kMirOpFusedCmpLong:
1100       must_keep = true;
1101       uses_all_vregs = true;  // Keep the implicit dependencies on all vregs.
1102       break;
1103 
1104     case Instruction::CONST_CLASS:
1105     case Instruction::CONST_STRING:
1106     case Instruction::CONST_STRING_JUMBO:
1107       // NOTE: While we're currently treating CONST_CLASS, CONST_STRING and CONST_STRING_JUMBO
1108       // as throwing but we could conceivably try and eliminate those exceptions if we're
1109       // retrieving the class/string repeatedly.
1110       must_keep = true;
1111       uses_all_vregs = true;
1112       break;
1113 
1114     case Instruction::MONITOR_ENTER:
1115     case Instruction::MONITOR_EXIT:
1116       // We can actually try and optimize across the acquire operation of MONITOR_ENTER,
1117       // the value names provided by GVN reflect the possible changes to memory visibility.
1118       // NOTE: In ART, MONITOR_ENTER and MONITOR_EXIT can throw only NPE.
1119       must_keep = true;
1120       uses_all_vregs = (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0;
1121       break;
1122 
1123     case Instruction::INVOKE_DIRECT:
1124     case Instruction::INVOKE_DIRECT_RANGE:
1125     case Instruction::INVOKE_VIRTUAL:
1126     case Instruction::INVOKE_VIRTUAL_RANGE:
1127     case Instruction::INVOKE_SUPER:
1128     case Instruction::INVOKE_SUPER_RANGE:
1129     case Instruction::INVOKE_INTERFACE:
1130     case Instruction::INVOKE_INTERFACE_RANGE:
1131     case Instruction::INVOKE_STATIC:
1132     case Instruction::INVOKE_STATIC_RANGE:
1133     case Instruction::THROW:
1134     case Instruction::FILLED_NEW_ARRAY:
1135     case Instruction::FILLED_NEW_ARRAY_RANGE:
1136     case Instruction::FILL_ARRAY_DATA:
1137       must_keep = true;
1138       uses_all_vregs = true;
1139       break;
1140 
1141     case Instruction::NEW_INSTANCE:
1142     case Instruction::NEW_ARRAY:
1143       must_keep = true;
1144       uses_all_vregs = true;
1145       break;
1146 
1147     case Instruction::CHECK_CAST:
1148       DCHECK_EQ(mir->ssa_rep->num_uses, 1);
1149       must_keep = true;  // Keep for type information even if MIR_IGNORE_CHECK_CAST.
1150       uses_all_vregs = (mir->optimization_flags & MIR_IGNORE_CHECK_CAST) == 0;
1151       break;
1152 
1153     case kMirOpNullCheck:
1154       DCHECK_EQ(mir->ssa_rep->num_uses, 1);
1155       if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) {
1156         mir->ssa_rep->num_uses = 0;
1157         mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
1158         return false;
1159       }
1160       must_keep = true;
1161       uses_all_vregs = true;
1162       break;
1163 
1164     case Instruction::MOVE_RESULT:
1165     case Instruction::MOVE_RESULT_OBJECT:
1166     case Instruction::MOVE_RESULT_WIDE:
1167       break;
1168 
1169     case Instruction::INSTANCE_OF:
1170       break;
1171 
1172     case Instruction::MOVE_EXCEPTION:
1173       must_keep = true;
1174       break;
1175 
1176     case kMirOpCopy:
1177     case Instruction::MOVE:
1178     case Instruction::MOVE_FROM16:
1179     case Instruction::MOVE_16:
1180     case Instruction::MOVE_WIDE:
1181     case Instruction::MOVE_WIDE_FROM16:
1182     case Instruction::MOVE_WIDE_16:
1183     case Instruction::MOVE_OBJECT:
1184     case Instruction::MOVE_OBJECT_FROM16:
1185     case Instruction::MOVE_OBJECT_16: {
1186       is_move = true;
1187       // If the MIR defining src vreg is known, allow renaming all uses of src vreg to dest vreg
1188       // while updating the defining MIR to directly define dest vreg. However, changing Phi's
1189       // def this way doesn't work without changing MIRs in other BBs.
1190       int src_v_reg = mir_graph_->SRegToVReg(mir->ssa_rep->uses[0]);
1191       int src_change = vreg_chains_.LastChange(src_v_reg);
1192       if (src_change != kNPos) {
1193         MIRData* src_data = vreg_chains_.GetMIRData(src_change);
1194         if (static_cast<int>(src_data->mir->dalvikInsn.opcode) != kMirOpPhi) {
1195           src_data->is_move_src = true;
1196         }
1197       }
1198       break;
1199     }
1200 
1201     case Instruction::CONST_4:
1202     case Instruction::CONST_16:
1203     case Instruction::CONST:
1204     case Instruction::CONST_HIGH16:
1205     case Instruction::CONST_WIDE_16:
1206     case Instruction::CONST_WIDE_32:
1207     case Instruction::CONST_WIDE:
1208     case Instruction::CONST_WIDE_HIGH16:
1209     case Instruction::CMPL_FLOAT:
1210     case Instruction::CMPG_FLOAT:
1211     case Instruction::CMPL_DOUBLE:
1212     case Instruction::CMPG_DOUBLE:
1213     case Instruction::CMP_LONG:
1214     case Instruction::NEG_INT:
1215     case Instruction::NOT_INT:
1216     case Instruction::NEG_LONG:
1217     case Instruction::NOT_LONG:
1218     case Instruction::NEG_FLOAT:
1219     case Instruction::NEG_DOUBLE:
1220     case Instruction::INT_TO_LONG:
1221     case Instruction::INT_TO_FLOAT:
1222     case Instruction::INT_TO_DOUBLE:
1223     case Instruction::LONG_TO_INT:
1224     case Instruction::LONG_TO_FLOAT:
1225     case Instruction::LONG_TO_DOUBLE:
1226     case Instruction::FLOAT_TO_INT:
1227     case Instruction::FLOAT_TO_LONG:
1228     case Instruction::FLOAT_TO_DOUBLE:
1229     case Instruction::DOUBLE_TO_INT:
1230     case Instruction::DOUBLE_TO_LONG:
1231     case Instruction::DOUBLE_TO_FLOAT:
1232     case Instruction::INT_TO_BYTE:
1233     case Instruction::INT_TO_CHAR:
1234     case Instruction::INT_TO_SHORT:
1235     case Instruction::ADD_INT:
1236     case Instruction::SUB_INT:
1237     case Instruction::MUL_INT:
1238     case Instruction::AND_INT:
1239     case Instruction::OR_INT:
1240     case Instruction::XOR_INT:
1241     case Instruction::SHL_INT:
1242     case Instruction::SHR_INT:
1243     case Instruction::USHR_INT:
1244     case Instruction::ADD_LONG:
1245     case Instruction::SUB_LONG:
1246     case Instruction::MUL_LONG:
1247     case Instruction::AND_LONG:
1248     case Instruction::OR_LONG:
1249     case Instruction::XOR_LONG:
1250     case Instruction::SHL_LONG:
1251     case Instruction::SHR_LONG:
1252     case Instruction::USHR_LONG:
1253     case Instruction::ADD_FLOAT:
1254     case Instruction::SUB_FLOAT:
1255     case Instruction::MUL_FLOAT:
1256     case Instruction::DIV_FLOAT:
1257     case Instruction::REM_FLOAT:
1258     case Instruction::ADD_DOUBLE:
1259     case Instruction::SUB_DOUBLE:
1260     case Instruction::MUL_DOUBLE:
1261     case Instruction::DIV_DOUBLE:
1262     case Instruction::REM_DOUBLE:
1263     case Instruction::ADD_INT_2ADDR:
1264     case Instruction::SUB_INT_2ADDR:
1265     case Instruction::MUL_INT_2ADDR:
1266     case Instruction::AND_INT_2ADDR:
1267     case Instruction::OR_INT_2ADDR:
1268     case Instruction::XOR_INT_2ADDR:
1269     case Instruction::SHL_INT_2ADDR:
1270     case Instruction::SHR_INT_2ADDR:
1271     case Instruction::USHR_INT_2ADDR:
1272     case Instruction::ADD_LONG_2ADDR:
1273     case Instruction::SUB_LONG_2ADDR:
1274     case Instruction::MUL_LONG_2ADDR:
1275     case Instruction::AND_LONG_2ADDR:
1276     case Instruction::OR_LONG_2ADDR:
1277     case Instruction::XOR_LONG_2ADDR:
1278     case Instruction::SHL_LONG_2ADDR:
1279     case Instruction::SHR_LONG_2ADDR:
1280     case Instruction::USHR_LONG_2ADDR:
1281     case Instruction::ADD_FLOAT_2ADDR:
1282     case Instruction::SUB_FLOAT_2ADDR:
1283     case Instruction::MUL_FLOAT_2ADDR:
1284     case Instruction::DIV_FLOAT_2ADDR:
1285     case Instruction::REM_FLOAT_2ADDR:
1286     case Instruction::ADD_DOUBLE_2ADDR:
1287     case Instruction::SUB_DOUBLE_2ADDR:
1288     case Instruction::MUL_DOUBLE_2ADDR:
1289     case Instruction::DIV_DOUBLE_2ADDR:
1290     case Instruction::REM_DOUBLE_2ADDR:
1291     case Instruction::ADD_INT_LIT16:
1292     case Instruction::RSUB_INT:
1293     case Instruction::MUL_INT_LIT16:
1294     case Instruction::AND_INT_LIT16:
1295     case Instruction::OR_INT_LIT16:
1296     case Instruction::XOR_INT_LIT16:
1297     case Instruction::ADD_INT_LIT8:
1298     case Instruction::RSUB_INT_LIT8:
1299     case Instruction::MUL_INT_LIT8:
1300     case Instruction::AND_INT_LIT8:
1301     case Instruction::OR_INT_LIT8:
1302     case Instruction::XOR_INT_LIT8:
1303     case Instruction::SHL_INT_LIT8:
1304     case Instruction::SHR_INT_LIT8:
1305     case Instruction::USHR_INT_LIT8:
1306       break;
1307 
1308     case Instruction::DIV_INT:
1309     case Instruction::REM_INT:
1310     case Instruction::DIV_LONG:
1311     case Instruction::REM_LONG:
1312     case Instruction::DIV_INT_2ADDR:
1313     case Instruction::REM_INT_2ADDR:
1314     case Instruction::DIV_LONG_2ADDR:
1315     case Instruction::REM_LONG_2ADDR:
1316       if ((mir->optimization_flags & MIR_IGNORE_DIV_ZERO_CHECK) == 0) {
1317         must_keep = true;
1318         uses_all_vregs = true;
1319       }
1320       break;
1321 
1322     case Instruction::DIV_INT_LIT16:
1323     case Instruction::REM_INT_LIT16:
1324     case Instruction::DIV_INT_LIT8:
1325     case Instruction::REM_INT_LIT8:
1326       if (mir->dalvikInsn.vC == 0) {  // Explicit division by 0?
1327         must_keep = true;
1328         uses_all_vregs = true;
1329       }
1330       break;
1331 
1332     case Instruction::ARRAY_LENGTH:
1333       if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0) {
1334         must_keep = true;
1335         uses_all_vregs = true;
1336       }
1337       break;
1338 
1339     case Instruction::AGET_OBJECT:
1340     case Instruction::AGET:
1341     case Instruction::AGET_WIDE:
1342     case Instruction::AGET_BOOLEAN:
1343     case Instruction::AGET_BYTE:
1344     case Instruction::AGET_CHAR:
1345     case Instruction::AGET_SHORT:
1346       if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
1347           (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) == 0) {
1348         must_keep = true;
1349         uses_all_vregs = true;
1350       }
1351       break;
1352 
1353     case Instruction::APUT_OBJECT:
1354     case Instruction::APUT:
1355     case Instruction::APUT_WIDE:
1356     case Instruction::APUT_BYTE:
1357     case Instruction::APUT_BOOLEAN:
1358     case Instruction::APUT_SHORT:
1359     case Instruction::APUT_CHAR:
1360       must_keep = true;
1361       if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
1362           (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) == 0) {
1363         uses_all_vregs = true;
1364       }
1365       break;
1366 
1367     case Instruction::IGET_OBJECT:
1368     case Instruction::IGET:
1369     case Instruction::IGET_WIDE:
1370     case Instruction::IGET_BOOLEAN:
1371     case Instruction::IGET_BYTE:
1372     case Instruction::IGET_CHAR:
1373     case Instruction::IGET_SHORT: {
1374       const MirIFieldLoweringInfo& info = mir_graph_->GetIFieldLoweringInfo(mir);
1375       if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
1376           !info.IsResolved() || !info.FastGet()) {
1377         must_keep = true;
1378         uses_all_vregs = true;
1379       } else if (info.IsVolatile()) {
1380         must_keep = true;
1381       }
1382       break;
1383     }
1384 
1385     case Instruction::IPUT_OBJECT:
1386     case Instruction::IPUT:
1387     case Instruction::IPUT_WIDE:
1388     case Instruction::IPUT_BOOLEAN:
1389     case Instruction::IPUT_BYTE:
1390     case Instruction::IPUT_CHAR:
1391     case Instruction::IPUT_SHORT: {
1392       must_keep = true;
1393       const MirIFieldLoweringInfo& info = mir_graph_->GetIFieldLoweringInfo(mir);
1394       if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
1395           !info.IsResolved() || !info.FastPut()) {
1396         uses_all_vregs = true;
1397       }
1398       break;
1399     }
1400 
1401     case Instruction::SGET_OBJECT:
1402     case Instruction::SGET:
1403     case Instruction::SGET_WIDE:
1404     case Instruction::SGET_BOOLEAN:
1405     case Instruction::SGET_BYTE:
1406     case Instruction::SGET_CHAR:
1407     case Instruction::SGET_SHORT: {
1408       const MirSFieldLoweringInfo& info = mir_graph_->GetSFieldLoweringInfo(mir);
1409       if ((mir->optimization_flags & MIR_CLASS_IS_INITIALIZED) == 0 ||
1410           !info.IsResolved() || !info.FastGet()) {
1411         must_keep = true;
1412         uses_all_vregs = true;
1413       } else if (info.IsVolatile()) {
1414         must_keep = true;
1415       }
1416       break;
1417     }
1418 
1419     case Instruction::SPUT_OBJECT:
1420     case Instruction::SPUT:
1421     case Instruction::SPUT_WIDE:
1422     case Instruction::SPUT_BOOLEAN:
1423     case Instruction::SPUT_BYTE:
1424     case Instruction::SPUT_CHAR:
1425     case Instruction::SPUT_SHORT: {
1426       must_keep = true;
1427       const MirSFieldLoweringInfo& info = mir_graph_->GetSFieldLoweringInfo(mir);
1428       if ((mir->optimization_flags & MIR_CLASS_IS_INITIALIZED) == 0 ||
1429           !info.IsResolved() || !info.FastPut()) {
1430         uses_all_vregs = true;
1431       }
1432       break;
1433     }
1434 
1435     default:
1436       LOG(FATAL) << "Unexpected opcode: " << opcode;
1437       UNREACHABLE();
1438   }
1439 
1440   if (mir->ssa_rep->num_defs != 0) {
1441     DCHECK(mir->ssa_rep->num_defs == 1 || mir->ssa_rep->num_defs == 2);
1442     bool wide = (mir->ssa_rep->num_defs == 2);
1443     int s_reg = mir->ssa_rep->defs[0];
1444     int v_reg = mir_graph_->SRegToVReg(s_reg);
1445     uint16_t new_value = wide ? lvn_->GetSregValueWide(s_reg) : lvn_->GetSregValue(s_reg);
1446     DCHECK_NE(new_value, kNoValue);
1447 
1448     vreg_chains_.UpdateInitialVRegValue(v_reg, wide, lvn_);
1449     vreg_chains_.AddMIRWithDef(mir, v_reg, wide, new_value);
1450     if (is_move) {
1451       // Allow renaming all uses of dest vreg to src vreg.
1452       vreg_chains_.LastMIRData()->is_move = true;
1453     }
1454   } else {
1455     vreg_chains_.AddMIRWithoutDef(mir);
1456     DCHECK(!is_move) << opcode;
1457   }
1458 
1459   if (must_keep) {
1460     MIRData* last_data = vreg_chains_.LastMIRData();
1461     last_data->must_keep = true;
1462     if (uses_all_vregs) {
1463       last_data->uses_all_vregs = true;
1464       no_uses_all_since_ = vreg_chains_.NumMIRs();
1465     }
1466   } else {
1467     DCHECK_NE(mir->ssa_rep->num_defs, 0) << opcode;
1468     DCHECK(!uses_all_vregs) << opcode;
1469   }
1470   return true;
1471 }
1472 
1473 }  // namespace art
1474