ssa_phi_elimination.cc revision 1abb4191a2e56d8dbf518efcaeefb266c1acdf2b
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 197dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffraynamespace art { 207dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 217dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffrayvoid SsaDeadPhiElimination::Run() { 22d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray MarkDeadPhis(); 23d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray EliminateDeadPhis(); 24d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray} 25d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 26d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffrayvoid SsaDeadPhiElimination::MarkDeadPhis() { 277dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Add to the worklist phis referenced by non-phi instructions. 287dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 297dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 30277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 31277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HPhi* phi = inst_it.Current()->AsPhi(); 323159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray // Set dead ahead of running through uses. The phi may have no use. 333159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray phi->SetDead(); 34ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { 35ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil HUseListNode<HInstruction*>* current = use_it.Current(); 367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!user->IsPhi()) { 387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(phi); 397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->SetLive(); 40102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 417dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 427dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 437dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 447dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 457dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 467dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Process the worklist by propagating liveness to phi inputs. 477dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (!worklist_.IsEmpty()) { 487dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = worklist_.Pop(); 497dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HInputIterator it(phi); !it.Done(); it.Advance()) { 507dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* input = it.Current(); 517dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (input->IsPhi() && input->AsPhi()->IsDead()) { 527dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(input->AsPhi()); 537dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray input->AsPhi()->SetLive(); 547dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 557dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 567dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 57d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray} 587dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 59d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffrayvoid SsaDeadPhiElimination::EliminateDeadPhis() { 603ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Remove phis that are not live. Visit in post order so that phis 613ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // that are not inputs of loop phis can be removed when they have 623ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // no users left (dead phis might use dead phis). 637dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 647dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 657dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* current = block->GetFirstPhi(); 667dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* next = nullptr; 671abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil HPhi* phi; 687dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (current != nullptr) { 691abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi = current->AsPhi(); 707dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray next = current->GetNext(); 711abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil if (phi->IsDead()) { 721abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Make sure the phi is only used by other dead phis. 731abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil if (kIsDebugBuild) { 741abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); 75277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe use_it.Advance()) { 761abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil HInstruction* user = use_it.Current()->GetUser(); 773159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray DCHECK(user->IsLoopHeaderPhi()) << user->GetId(); 783159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray DCHECK(user->AsPhi()->IsDead()) << user->GetId(); 793ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 803ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 811abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Remove the phi from use lists of its inputs. 821abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 831abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->RemoveAsUserOfInput(i); 841abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil } 851abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Remove the phi from environments that use it. 861abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil for (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done(); 871abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil use_it.Advance()) { 881abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil HUseListNode<HEnvironment*>* user_node = use_it.Current(); 891abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil HEnvironment* user = user_node->GetUser(); 901abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil user->SetRawEnvAt(user_node->GetIndex(), nullptr); 91102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 921abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil // Delete it from the instruction list. 931abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil block->RemovePhi(phi, /*ensure_safety=*/ false); 947dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 957dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray current = next; 967dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 977dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 987dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 997dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1007dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffrayvoid SsaRedundantPhiElimination::Run() { 1017dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Add all phis in the worklist. 1027dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 1037dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 104277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 105277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe worklist_.Add(inst_it.Current()->AsPhi()); 1067dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1077dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1087dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1097dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (!worklist_.IsEmpty()) { 1107dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = worklist_.Pop(); 1117dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1127dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the phi has already been processed, continue. 1137dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!phi->IsInBlock()) { 1147dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1157dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1167dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1177dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Find if the inputs of the phi are the same instruction. 1187dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* candidate = phi->InputAt(0); 119604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // A loop phi cannot have itself as the first phi. Note that this 120604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // check relies on our simplification pass ensuring the pre-header 121604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // block is first in the list of predecessors of the loop header. 1226b879ddc0959df1cec871f0d41f11cce35a11716Roland Levillain DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 1237dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray DCHECK_NE(phi, candidate); 1247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (size_t i = 1; i < phi->InputCount(); ++i) { 1267dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* input = phi->InputAt(i); 1273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // For a loop phi, if the input is the phi, the phi is still candidate for 1287dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // elimination. 1297dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (input != candidate && input != phi) { 1307dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray candidate = nullptr; 1317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray break; 1327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1337dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1347dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1357dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the inputs are not the same, continue. 1367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (candidate == nullptr) { 1377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1407dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (phi->IsInLoop()) { 1417dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Because we're updating the users of this phi, we may have new 1427dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // phis candidate for elimination if this phi is in a loop. Add phis that 1437dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // used this phi to the worklist. 144ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) { 145ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil HUseListNode<HInstruction*>* current = it.Current(); 1467dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 1477dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (user->IsPhi()) { 1487dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(user->AsPhi()); 1497dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1507dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1517dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1527dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->ReplaceWith(candidate); 1537dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->GetBlock()->RemovePhi(phi); 1547dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1557dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 1567dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1577dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} // namespace art 158