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 31namespace art { 32 33constexpr uint16_t GvnDeadCodeElimination::kNoValue; 34constexpr uint16_t GvnDeadCodeElimination::kNPos; 35 36inline 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 42inline 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 52inline 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 74GvnDeadCodeElimination::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 84inline 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 90void 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 122inline void GvnDeadCodeElimination::VRegChains::AddMIRWithoutDef(MIR* mir) { 123 mir_data_.emplace_back(mir); 124} 125 126void 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 147void 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 161inline size_t GvnDeadCodeElimination::VRegChains::NumMIRs() const { 162 return mir_data_.size(); 163} 164 165inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::GetMIRData(size_t pos) { 166 DCHECK_LT(pos, mir_data_.size()); 167 return &mir_data_[pos]; 168} 169 170inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::LastMIRData() { 171 DCHECK(!mir_data_.empty()); 172 return &mir_data_.back(); 173} 174 175uint32_t GvnDeadCodeElimination::VRegChains::NumVRegs() const { 176 return num_vregs_; 177} 178 179void 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 210void 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 258inline 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 263inline 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 268uint16_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 298uint16_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 311void 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 329void 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 351inline 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 360bool 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 375bool 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 390void 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 407void 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 445GvnDeadCodeElimination::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 461void 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 473void 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 485void 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 496void 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 508void 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 514void 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 521MIR* 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 553MIR* 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 611void 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 637void 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 682void 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 757void 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 818void 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 879uint16_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 948void GvnDeadCodeElimination::BackwardPassTryToKillRevertVRegs() { 949} 950 951bool 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 1036bool 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