17dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray/* 27dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 37dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * 47dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 57dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * you may not use this file except in compliance with the License. 67dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * You may obtain a copy of the License at 77dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * 87dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 97dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * 107dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 117dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 127dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * See the License for the specific language governing permissions and 147dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * limitations under the License. 157dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray */ 167dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 177dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray#include "ssa_phi_elimination.h" 187dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 19c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko#include "base/arena_bit_vector.h" 20f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko#include "base/scoped_arena_allocator.h" 21f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko#include "base/scoped_arena_containers.h" 22f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray#include "base/bit_vector-inl.h" 23809d70f5b268227dbd59432dc038c74d8351be29David Brazdil 247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffraynamespace art { 257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 267dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffrayvoid SsaDeadPhiElimination::Run() { 27d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray MarkDeadPhis(); 28d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray EliminateDeadPhis(); 29d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray} 30d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 31d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffrayvoid SsaDeadPhiElimination::MarkDeadPhis() { 32f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko // Use local allocator for allocating memory used by this optimization. 33f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko ScopedArenaAllocator allocator(graph_->GetArenaStack()); 34f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko 35f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko static constexpr size_t kDefaultWorklistSize = 8; 36f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko ScopedArenaVector<HPhi*> worklist(allocator.Adapter(kArenaAllocSsaPhiElimination)); 37f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.reserve(kDefaultWorklistSize); 38f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko 39809d70f5b268227dbd59432dc038c74d8351be29David Brazdil // Phis are constructed live and should not be revived if previously marked 40809d70f5b268227dbd59432dc038c74d8351be29David Brazdil // dead. This algorithm temporarily breaks that invariant but we DCHECK that 41809d70f5b268227dbd59432dc038c74d8351be29David Brazdil // only phis which were initially live are revived. 42f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko ScopedArenaSet<HPhi*> initially_live(allocator.Adapter(kArenaAllocSsaPhiElimination)); 43809d70f5b268227dbd59432dc038c74d8351be29David Brazdil 447dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Add to the worklist phis referenced by non-phi instructions. 452c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HBasicBlock* block : graph_->GetReversePostOrder()) { 46277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 47277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HPhi* phi = inst_it.Current()->AsPhi(); 48809d70f5b268227dbd59432dc038c74d8351be29David Brazdil if (phi->IsDead()) { 49809d70f5b268227dbd59432dc038c74d8351be29David Brazdil continue; 50809d70f5b268227dbd59432dc038c74d8351be29David Brazdil } 51809d70f5b268227dbd59432dc038c74d8351be29David Brazdil 52d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses()); 53d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil if (!keep_alive) { 5446817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { 5546817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko if (!use.GetUser()->IsPhi()) { 56d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil keep_alive = true; 57d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil break; 58d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil } 597dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 607dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 61809d70f5b268227dbd59432dc038c74d8351be29David Brazdil 62d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil if (keep_alive) { 63f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.push_back(phi); 64809d70f5b268227dbd59432dc038c74d8351be29David Brazdil } else { 65809d70f5b268227dbd59432dc038c74d8351be29David Brazdil phi->SetDead(); 66809d70f5b268227dbd59432dc038c74d8351be29David Brazdil if (kIsDebugBuild) { 67809d70f5b268227dbd59432dc038c74d8351be29David Brazdil initially_live.insert(phi); 68809d70f5b268227dbd59432dc038c74d8351be29David Brazdil } 69809d70f5b268227dbd59432dc038c74d8351be29David Brazdil } 707dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 717dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 727dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 737dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Process the worklist by propagating liveness to phi inputs. 74f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko while (!worklist.empty()) { 75f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko HPhi* phi = worklist.back(); 76f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.pop_back(); 77372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko for (HInstruction* raw_input : phi->GetInputs()) { 78372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko HPhi* input = raw_input->AsPhi(); 79809d70f5b268227dbd59432dc038c74d8351be29David Brazdil if (input != nullptr && input->IsDead()) { 80809d70f5b268227dbd59432dc038c74d8351be29David Brazdil // Input is a dead phi. Revive it and add to the worklist. We make sure 81809d70f5b268227dbd59432dc038c74d8351be29David Brazdil // that the phi was not dead initially (see definition of `initially_live`). 82809d70f5b268227dbd59432dc038c74d8351be29David Brazdil DCHECK(ContainsElement(initially_live, input)); 83809d70f5b268227dbd59432dc038c74d8351be29David Brazdil input->SetLive(); 84f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.push_back(input); 857dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 867dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 877dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 88d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray} 897dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 90d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffrayvoid SsaDeadPhiElimination::EliminateDeadPhis() { 913ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Remove phis that are not live. Visit in post order so that phis 923ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // that are not inputs of loop phis can be removed when they have 933ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // no users left (dead phis might use dead phis). 942c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HBasicBlock* block : graph_->GetPostOrder()) { 957dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* current = block->GetFirstPhi(); 967dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* next = nullptr; 971abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil HPhi* phi; 987dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (current != nullptr) { 991abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi = current->AsPhi(); 1007dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray next = current->GetNext(); 1011abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil if (phi->IsDead()) { 1021abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Make sure the phi is only used by other dead phis. 1031abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil if (kIsDebugBuild) { 10446817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { 10546817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko HInstruction* user = use.GetUser(); 106d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil DCHECK(user->IsLoopHeaderPhi()); 107d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil DCHECK(user->AsPhi()->IsDead()); 1083ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 1093ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 1101abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Remove the phi from use lists of its inputs. 111372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko phi->RemoveAsUserOfAllInputs(); 1121abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Remove the phi from environments that use it. 11346817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) { 11446817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko HEnvironment* user = use.GetUser(); 11546817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko user->SetRawEnvAt(use.GetIndex(), nullptr); 116102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1171abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Delete it from the instruction list. 1181abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil block->RemovePhi(phi, /*ensure_safety=*/ false); 1197dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1207dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray current = next; 1217dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1227dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1237dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 1247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffrayvoid SsaRedundantPhiElimination::Run() { 126f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko // Use local allocator for allocating memory used by this optimization. 127f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko ScopedArenaAllocator allocator(graph_->GetArenaStack()); 128f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko 129f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko static constexpr size_t kDefaultWorklistSize = 8; 130f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko ScopedArenaVector<HPhi*> worklist(allocator.Adapter(kArenaAllocSsaPhiElimination)); 131f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.reserve(kDefaultWorklistSize); 132f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko 13377b022dfb8e73564b00c4724f7078cb1d5a57a65David Brazdil // Add all phis in the worklist. Order does not matter for correctness, and 13477b022dfb8e73564b00c4724f7078cb1d5a57a65David Brazdil // neither will necessarily converge faster. 1352c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HBasicBlock* block : graph_->GetReversePostOrder()) { 136277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 137f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.push_back(inst_it.Current()->AsPhi()); 1387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1407dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 141f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko ArenaBitVector visited_phis_in_cycle(&allocator, 142c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko graph_->GetCurrentInstructionId(), 143c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko /* expandable */ false, 144c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko kArenaAllocSsaPhiElimination); 145f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko visited_phis_in_cycle.ClearAllBits(); 146f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko ScopedArenaVector<HPhi*> cycle_worklist(allocator.Adapter(kArenaAllocSsaPhiElimination)); 147f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray 148f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko while (!worklist.empty()) { 149f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko HPhi* phi = worklist.back(); 150f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.pop_back(); 1517dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1527dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the phi has already been processed, continue. 1537dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!phi->IsInBlock()) { 1547dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1557dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1567dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 15705b3fa02ed8ef62841a92cd96526ba3a06bf1f63Nicolas Geoffray // If the phi is dead, we know we won't revive it and it will be removed, 15805b3fa02ed8ef62841a92cd96526ba3a06bf1f63Nicolas Geoffray // so don't process it. 15905b3fa02ed8ef62841a92cd96526ba3a06bf1f63Nicolas Geoffray if (phi->IsDead()) { 160ffee3d33f3ea39aa6031c3d2ff29c4806c8dcc51David Brazdil continue; 161ffee3d33f3ea39aa6031c3d2ff29c4806c8dcc51David Brazdil } 162ffee3d33f3ea39aa6031c3d2ff29c4806c8dcc51David Brazdil 163f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray HInstruction* candidate = nullptr; 164c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko visited_phis_in_cycle.ClearAllBits(); 165f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray cycle_worklist.clear(); 166f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray 167f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray cycle_worklist.push_back(phi); 168c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko visited_phis_in_cycle.SetBit(phi->GetId()); 169f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray bool catch_phi_in_cycle = phi->IsCatchPhi(); 17015bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray bool irreducible_loop_phi_in_cycle = phi->IsIrreducibleLoopHeaderPhi(); 171f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray 172f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // First do a simple loop over inputs and check if they are all the same. 173372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko for (HInstruction* input : phi->GetInputs()) { 174f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray if (input == phi) { 175f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray continue; 176f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } else if (candidate == nullptr) { 177f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray candidate = input; 178f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } else if (candidate != input) { 1797dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray candidate = nullptr; 1807dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray break; 1817dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1827dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1837dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 184f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // If we haven't found a candidate, check for a phi cycle. Note that we need to detect 185f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // such cycles to avoid having reference and non-reference equivalents. We check this 186f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // invariant in the graph checker. 1877dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (candidate == nullptr) { 188f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // We iterate over the array as long as it grows. 189f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray for (size_t i = 0; i < cycle_worklist.size(); ++i) { 190f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray HPhi* current = cycle_worklist[i]; 191f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray DCHECK(!current->IsLoopHeaderPhi() || 192f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray current->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 193f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray 194372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko for (HInstruction* input : current->GetInputs()) { 195f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray if (input == current) { 196f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray continue; 197f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } else if (input->IsPhi()) { 198c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko if (!visited_phis_in_cycle.IsBitSet(input->GetId())) { 199f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray cycle_worklist.push_back(input->AsPhi()); 200c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko visited_phis_in_cycle.SetBit(input->GetId()); 201f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi(); 20215bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray irreducible_loop_phi_in_cycle |= input->IsIrreducibleLoopHeaderPhi(); 203f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } else { 204f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // Already visited, nothing to do. 205f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } 206f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } else if (candidate == nullptr) { 207f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray candidate = input; 208f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } else if (candidate != input) { 209f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray candidate = nullptr; 210f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // Clear the cycle worklist to break out of the outer loop. 211f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray cycle_worklist.clear(); 212f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray break; 213f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } 214f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } 215f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } 2167dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 2177dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 218f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray if (candidate == nullptr) { 219ffee3d33f3ea39aa6031c3d2ff29c4806c8dcc51David Brazdil continue; 220ffee3d33f3ea39aa6031c3d2ff29c4806c8dcc51David Brazdil } 221ffee3d33f3ea39aa6031c3d2ff29c4806c8dcc51David Brazdil 22215bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray if (irreducible_loop_phi_in_cycle && !candidate->IsConstant()) { 22315bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // For irreducible loops, we need to keep the phis to satisfy our linear scan 22415bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // algorithm. 22515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // There is one exception for constants, as the type propagation requires redundant 22615bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // cyclic phis of a constant to be removed. This is ok for the linear scan as it 22715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // has to deal with constants anyway, and they can trivially be rematerialized. 22815bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray continue; 22915bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray } 23015bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray 231f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray for (HPhi* current : cycle_worklist) { 232f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // The candidate may not dominate a phi in a catch block: there may be non-throwing 233f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // instructions at the beginning of a try range, that may be the first input of 234f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // catch phis. 235f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions 236f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // before the try entry. 237f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray if (catch_phi_in_cycle) { 238f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray if (!candidate->StrictlyDominates(current)) { 239f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray continue; 240f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } 241f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } else { 242f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray DCHECK(candidate->StrictlyDominates(current)); 243f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } 244f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray 245f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // Because we're updating the users of this phi, we may have new candidates 246f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray // for elimination. Add phis that use this phi to the worklist. 24746817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (const HUseListNode<HInstruction*>& use : current->GetUses()) { 24846817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko HInstruction* user = use.GetUser(); 249c9ef168bfabd118d112a054dffe2c27d4d4db4fcVladimir Marko if (user->IsPhi() && !visited_phis_in_cycle.IsBitSet(user->GetId())) { 250f361267ff86e775ed146138220c5a2f70b4a4b3dVladimir Marko worklist.push_back(user->AsPhi()); 251f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray } 2527dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 253f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray DCHECK(candidate->StrictlyDominates(current)); 254f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray current->ReplaceWith(candidate); 255f5f64efda943000168d34bfe44ccbbadd284e55fNicolas Geoffray current->GetBlock()->RemovePhi(current); 2567dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 2577dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 2587dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 2597dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 2607dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} // namespace art 261