ssa_phi_elimination.cc revision 3159674c0863f53cfbc1913d493550221ac47f02
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() { 227dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Add to the worklist phis referenced by non-phi instructions. 237dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 25277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 26277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HPhi* phi = inst_it.Current()->AsPhi(); 273159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray // Set dead ahead of running through uses. The phi may have no use. 283159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray phi->SetDead(); 29277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HUseIterator<HInstruction> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { 30277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HUseListNode<HInstruction>* current = use_it.Current(); 317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!user->IsPhi()) { 337dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(phi); 347dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->SetLive(); 35102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 407dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 417dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Process the worklist by propagating liveness to phi inputs. 427dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (!worklist_.IsEmpty()) { 437dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = worklist_.Pop(); 447dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HInputIterator it(phi); !it.Done(); it.Advance()) { 457dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* input = it.Current(); 467dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (input->IsPhi() && input->AsPhi()->IsDead()) { 477dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(input->AsPhi()); 487dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray input->AsPhi()->SetLive(); 497dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 507dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 517dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 527dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 533ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Remove phis that are not live. Visit in post order so that phis 543ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // that are not inputs of loop phis can be removed when they have 553ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // no users left (dead phis might use dead phis). 567dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 577dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 587dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* current = block->GetFirstPhi(); 597dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* next = nullptr; 607dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (current != nullptr) { 617dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray next = current->GetNext(); 627dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (current->AsPhi()->IsDead()) { 633ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray if (current->HasUses()) { 64277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HUseIterator<HInstruction> use_it(current->GetUses()); !use_it.Done(); 65277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe use_it.Advance()) { 66277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HUseListNode<HInstruction>* user_node = use_it.Current(); 673ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray HInstruction* user = user_node->GetUser(); 683159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray DCHECK(user->IsLoopHeaderPhi()) << user->GetId(); 693159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray DCHECK(user->AsPhi()->IsDead()) << user->GetId(); 703ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Just put itself as an input. The phi will be removed in this loop anyway. 713ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray user->SetRawInputAt(user_node->GetIndex(), user); 723ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray current->RemoveUser(user, user_node->GetIndex()); 733ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 743ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 75102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (current->HasEnvironmentUses()) { 76277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HUseIterator<HEnvironment> use_it(current->GetEnvUses()); !use_it.Done(); 77277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe use_it.Advance()) { 78277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HUseListNode<HEnvironment>* user_node = use_it.Current(); 79102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HEnvironment* user = user_node->GetUser(); 80102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray user->SetRawEnvAt(user_node->GetIndex(), nullptr); 81102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray current->RemoveEnvironmentUser(user, user_node->GetIndex()); 82102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 83102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 847dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray block->RemovePhi(current->AsPhi()); 857dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 867dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray current = next; 877dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 887dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 897dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 907dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 917dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffrayvoid SsaRedundantPhiElimination::Run() { 927dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Add all phis in the worklist. 937dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 947dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 95277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 96277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe worklist_.Add(inst_it.Current()->AsPhi()); 977dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 987dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 997dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1007dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (!worklist_.IsEmpty()) { 1017dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = worklist_.Pop(); 1027dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1037dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the phi has already been processed, continue. 1047dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!phi->IsInBlock()) { 1057dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1067dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1077dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1087dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Find if the inputs of the phi are the same instruction. 1097dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* candidate = phi->InputAt(0); 110604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // A loop phi cannot have itself as the first phi. Note that this 111604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // check relies on our simplification pass ensuring the pre-header 112604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // block is first in the list of predecessors of the loop header. 1136b879ddc0959df1cec871f0d41f11cce35a11716Roland Levillain DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 1147dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray DCHECK_NE(phi, candidate); 1157dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1167dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (size_t i = 1; i < phi->InputCount(); ++i) { 1177dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* input = phi->InputAt(i); 1183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // For a loop phi, if the input is the phi, the phi is still candidate for 1197dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // elimination. 1207dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (input != candidate && input != phi) { 1217dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray candidate = nullptr; 1227dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray break; 1237dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1267dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the inputs are not the same, continue. 1277dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (candidate == nullptr) { 1287dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1297dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1307dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (phi->IsInLoop()) { 1327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Because we're updating the users of this phi, we may have new 1337dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // phis candidate for elimination if this phi is in a loop. Add phis that 1347dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // used this phi to the worklist. 1357dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) { 1367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HUseListNode<HInstruction>* current = it.Current(); 1377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 1387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (user->IsPhi()) { 1397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(user->AsPhi()); 1407dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1417dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1427dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1437dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->ReplaceWith(candidate); 1447dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->GetBlock()->RemovePhi(phi); 1457dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1467dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 1477dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1487dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} // namespace art 149