ssa_phi_elimination.cc revision 6b879ddc0959df1cec871f0d41f11cce35a11716
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(); 257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 267dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 277dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (phi->HasEnvironmentUses()) { 287dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // TODO: Do we want to keep that phi alive? 293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray worklist_.Add(phi); 303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray phi->SetLive(); 317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 337dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) { 347dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HUseListNode<HInstruction>* current = it.Current(); 357dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!user->IsPhi()) { 377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(phi); 387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->SetLive(); 397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } else { 407dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->SetDead(); 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 } 577dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 583ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Remove phis that are not live. Visit in post order so that phis 593ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // that are not inputs of loop phis can be removed when they have 603ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // no users left (dead phis might use dead phis). 617dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 627dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 637dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* current = block->GetFirstPhi(); 647dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* next = nullptr; 657dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (current != nullptr) { 667dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray next = current->GetNext(); 677dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (current->AsPhi()->IsDead()) { 683ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray if (current->HasUses()) { 693ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray for (HUseIterator<HInstruction> it(current->GetUses()); !it.Done(); it.Advance()) { 703ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray HUseListNode<HInstruction>* user_node = it.Current(); 713ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray HInstruction* user = user_node->GetUser(); 723ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray DCHECK(user->IsLoopHeaderPhi()); 733ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray DCHECK(user->AsPhi()->IsDead()); 743ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Just put itself as an input. The phi will be removed in this loop anyway. 753ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray user->SetRawInputAt(user_node->GetIndex(), user); 763ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray current->RemoveUser(user, user_node->GetIndex()); 773ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 783ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 797dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray block->RemovePhi(current->AsPhi()); 807dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 817dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray current = next; 827dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 837dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 847dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 857dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 867dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffrayvoid SsaRedundantPhiElimination::Run() { 877dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Add all phis in the worklist. 887dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 897dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 907dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 917dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(it.Current()->AsPhi()); 927dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 937dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 947dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 957dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (!worklist_.IsEmpty()) { 967dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = worklist_.Pop(); 977dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 987dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the phi has already been processed, continue. 997dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!phi->IsInBlock()) { 1007dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1017dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1027dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1037dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Find if the inputs of the phi are the same instruction. 1047dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* candidate = phi->InputAt(0); 105604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // A loop phi cannot have itself as the first phi. Note that this 106604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // check relies on our simplification pass ensuring the pre-header 107604c6e4764edb2fd244e9f47626868cda5644a7aNicolas Geoffray // block is first in the list of predecessors of the loop header. 1086b879ddc0959df1cec871f0d41f11cce35a11716Roland Levillain DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 1097dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray DCHECK_NE(phi, candidate); 1107dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1117dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (size_t i = 1; i < phi->InputCount(); ++i) { 1127dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* input = phi->InputAt(i); 1133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // For a loop phi, if the input is the phi, the phi is still candidate for 1147dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // elimination. 1157dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (input != candidate && input != phi) { 1167dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray candidate = nullptr; 1177dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray break; 1187dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1197dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1207dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1217dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the inputs are not the same, continue. 1227dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (candidate == nullptr) { 1237dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1267dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (phi->IsInLoop()) { 1277dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Because we're updating the users of this phi, we may have new 1287dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // phis candidate for elimination if this phi is in a loop. Add phis that 1297dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // used this phi to the worklist. 1307dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) { 1317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HUseListNode<HInstruction>* current = it.Current(); 1327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 1337dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (user->IsPhi()) { 1347dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(user->AsPhi()); 1357dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->ReplaceWith(candidate); 1397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->GetBlock()->RemovePhi(phi); 1407dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1417dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 1427dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1437dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} // namespace art 144