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#ifndef ART_COMPILER_OPTIMIZING_SSA_PHI_ELIMINATION_H_ 187dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray#define ART_COMPILER_OPTIMIZING_SSA_PHI_ELIMINATION_H_ 197dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 202aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko#include "base/arena_containers.h" 217dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray#include "nodes.h" 225e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffray#include "optimization.h" 237dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 247dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffraynamespace art { 257dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 267dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray/** 277dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * Optimization phase that removes dead phis from the graph. Dead phis are unused 287dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * phis, or phis only used by other phis. 297dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray */ 305e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffrayclass SsaDeadPhiElimination : public HOptimization { 317dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray public: 327dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray explicit SsaDeadPhiElimination(HGraph* graph) 3369ba7b7112c2277ac225615b37e6df74c055740dDavid Brazdil : HOptimization(graph, kSsaDeadPhiEliminationPassName), 342aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko worklist_(graph->GetArena()->Adapter(kArenaAllocSsaPhiElimination)) { 352aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko worklist_.reserve(kDefaultWorklistSize); 362aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } 377dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 385e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffray void Run() OVERRIDE; 397dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 40d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray void MarkDeadPhis(); 41d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray void EliminateDeadPhis(); 42d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 437c3952f423b8213083d60596a5f0bf4237ca3f7bAndreas Gampe static constexpr const char* kSsaDeadPhiEliminationPassName = "dead_phi_elimination"; 447c3952f423b8213083d60596a5f0bf4237ca3f7bAndreas Gampe 457dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray private: 462aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<HPhi*> worklist_; 477dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 487dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray static constexpr size_t kDefaultWorklistSize = 8; 497dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 507dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(SsaDeadPhiElimination); 517dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray}; 527dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 537dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray/** 547dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * Removes redundant phis that may have been introduced when doing SSA conversion. 557dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * For example, when entering a loop, we create phis for all live registers. These 567dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * registers might be updated with the same value, or not updated at all. We can just 577dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray * replace the phi with the value when entering the loop. 587dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray */ 595e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffrayclass SsaRedundantPhiElimination : public HOptimization { 607dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray public: 617dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray explicit SsaRedundantPhiElimination(HGraph* graph) 6269ba7b7112c2277ac225615b37e6df74c055740dDavid Brazdil : HOptimization(graph, kSsaRedundantPhiEliminationPassName), 632aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko worklist_(graph->GetArena()->Adapter(kArenaAllocSsaPhiElimination)) { 642aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko worklist_.reserve(kDefaultWorklistSize); 652aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } 667dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 675e6916cea259897baaca019c5c7a5d05746306edNicolas Geoffray void Run() OVERRIDE; 687dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 697c3952f423b8213083d60596a5f0bf4237ca3f7bAndreas Gampe static constexpr const char* kSsaRedundantPhiEliminationPassName = "redundant_phi_elimination"; 707c3952f423b8213083d60596a5f0bf4237ca3f7bAndreas Gampe 717dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray private: 722aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<HPhi*> worklist_; 737dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 747dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray static constexpr size_t kDefaultWorklistSize = 8; 757dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 767dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(SsaRedundantPhiElimination); 777dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray}; 787dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 797dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray} // namespace art 807dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray 817dc206a53a42a658f52d5cb0b7e79b47da370c9bNicolas Geoffray#endif // ART_COMPILER_OPTIMIZING_SSA_PHI_ELIMINATION_H_ 82