ssa_phi_elimination.cc revision 3ac17fcce8773388512ce72cb491b202872ca1c1
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? 297dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 307dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) { 327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HUseListNode<HInstruction>* current = it.Current(); 337dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 347dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!user->IsPhi()) { 357dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(phi); 367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->SetLive(); 377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } else { 387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->SetDead(); 397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 407dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 417dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 427dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 437dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 447dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Process the worklist by propagating liveness to phi inputs. 457dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (!worklist_.IsEmpty()) { 467dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = worklist_.Pop(); 477dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HInputIterator it(phi); !it.Done(); it.Advance()) { 487dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* input = it.Current(); 497dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (input->IsPhi() && input->AsPhi()->IsDead()) { 507dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(input->AsPhi()); 517dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray input->AsPhi()->SetLive(); 527dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 537dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 547dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 557dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 563ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Remove phis that are not live. Visit in post order so that phis 573ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // that are not inputs of loop phis can be removed when they have 583ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // no users left (dead phis might use dead phis). 597dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 607dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 617dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* current = block->GetFirstPhi(); 627dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* next = nullptr; 637dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (current != nullptr) { 647dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray next = current->GetNext(); 657dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (current->AsPhi()->IsDead()) { 663ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray if (current->HasUses()) { 673ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray for (HUseIterator<HInstruction> it(current->GetUses()); !it.Done(); it.Advance()) { 683ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray HUseListNode<HInstruction>* user_node = it.Current(); 693ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray HInstruction* user = user_node->GetUser(); 703ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray DCHECK(user->IsLoopHeaderPhi()); 713ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray DCHECK(user->AsPhi()->IsDead()); 723ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray // Just put itself as an input. The phi will be removed in this loop anyway. 733ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray user->SetRawInputAt(user_node->GetIndex(), user); 743ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray current->RemoveUser(user, user_node->GetIndex()); 753ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 763ac17fcce8773388512ce72cb491b202872ca1c1Nicolas Geoffray } 777dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray block->RemovePhi(current->AsPhi()); 787dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 797dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray current = next; 807dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 817dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 827dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 837dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 847dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffrayvoid SsaRedundantPhiElimination::Run() { 857dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Add all phis in the worklist. 867dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 877dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HBasicBlock* block = it.Current(); 887dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 897dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(it.Current()->AsPhi()); 907dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 917dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 927dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 937dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray while (!worklist_.IsEmpty()) { 947dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HPhi* phi = worklist_.Pop(); 957dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 967dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the phi has already been processed, continue. 977dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (!phi->IsInBlock()) { 987dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 997dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1007dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1017dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Find if the inputs of the phi are the same instruction. 1027dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* candidate = phi->InputAt(0); 1037dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // A loop phi cannot have itself as the first phi. 1047dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray DCHECK_NE(phi, candidate); 1057dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1067dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (size_t i = 1; i < phi->InputCount(); ++i) { 1077dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* input = phi->InputAt(i); 1087dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // For a loop phi, If the input is the phi, the phi is still candidate for 1097dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // elimination. 1107dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (input != candidate && input != phi) { 1117dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray candidate = nullptr; 1127dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray break; 1137dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1147dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1157dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1167dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // If the inputs are not the same, continue. 1177dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (candidate == nullptr) { 1187dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray continue; 1197dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1207dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1217dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (phi->IsInLoop()) { 1227dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // Because we're updating the users of this phi, we may have new 1237dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // phis candidate for elimination if this phi is in a loop. Add phis that 1247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray // used this phi to the worklist. 1257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) { 1267dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HUseListNode<HInstruction>* current = it.Current(); 1277dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray HInstruction* user = current->GetUser(); 1287dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray if (user->IsPhi()) { 1297dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray worklist_.Add(user->AsPhi()); 1307dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1337dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->ReplaceWith(candidate); 1347dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray phi->GetBlock()->RemovePhi(phi); 1357dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray } 1367dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} 1377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 1387dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} // namespace art 139