1c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray/* 2c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * 4c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * you may not use this file except in compliance with the License. 6c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * You may obtain a copy of the License at 7c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * 8c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * 10c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * See the License for the specific language governing permissions and 14c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * limitations under the License. 15c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray */ 16c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 17c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray#ifndef ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 18c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray#define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 19c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 2071bf8090663d02869cafafdd530976f7f2a9db7fVladimir Marko#include "base/arena_containers.h" 21c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray#include "nodes.h" 223159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray#include "optimization.h" 23c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 24c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffraynamespace art { 25c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 26e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray/** 27e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * Transforms a graph into SSA form. The liveness guarantees of 28e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * this transformation are listed below. A DEX register 29e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * being killed means its value at a given position in the code 30e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * will not be available to its environment uses. A merge in the 31e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * following text is materialized as a `HPhi`. 32e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * 33e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * (a) Dex registers that do not require merging (that is, they do not 34e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * have different values at a join block) are available to all their 35915b9d0c13bb5091875d868fbfa551d7b65d7477Nicolas Geoffray * environment uses. Note that it does not imply the instruction will 36915b9d0c13bb5091875d868fbfa551d7b65d7477Nicolas Geoffray * have a physical location after register allocation. See the 37915b9d0c13bb5091875d868fbfa551d7b65d7477Nicolas Geoffray * SsaLivenessAnalysis phase. 38e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * 39e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * (b) Dex registers that require merging, and the merging gives 40e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * incompatible types, will be killed for environment uses of that merge. 41e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * 42e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * (c) When the `debuggable` flag is passed to the compiler, Dex registers 43e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * that require merging and have a proper type after the merge, are 44e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * available to all their environment uses. If the `debuggable` flag 45e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * is not set, values of Dex registers only used by environments 46e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * are killed. 47e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray */ 48dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdilclass SsaBuilder : public ValueObject { 49c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray public: 50a4336d253b88f95c49891a8084579a4599785e90Vladimir Marko SsaBuilder(HGraph* graph, 51a4336d253b88f95c49891a8084579a4599785e90Vladimir Marko Handle<mirror::DexCache> dex_cache, 52a4336d253b88f95c49891a8084579a4599785e90Vladimir Marko StackHandleScopeCollection* handles) 53dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil : graph_(graph), 54a4336d253b88f95c49891a8084579a4599785e90Vladimir Marko dex_cache_(dex_cache), 554833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil handles_(handles), 564833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil agets_fixed_(false), 57dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)), 58dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil ambiguous_asets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)), 59dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil uninitialized_strings_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)) { 60dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil graph_->InitializeInexactObjectRTI(handles); 61c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 62c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 6315bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray GraphAnalysisResult BuildSsa(); 64c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 65dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil HInstruction* GetFloatOrDoubleEquivalent(HInstruction* instruction, Primitive::Type type); 66dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); 67dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil 68dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil void MaybeAddAmbiguousArrayGet(HArrayGet* aget) { 69dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil Primitive::Type type = aget->GetType(); 70dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil DCHECK(!Primitive::IsFloatingPointType(type)); 71dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil if (Primitive::IsIntOrLongType(type)) { 72dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil ambiguous_agets_.push_back(aget); 73dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 74dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 75dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil 76dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil void MaybeAddAmbiguousArraySet(HArraySet* aset) { 77dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil Primitive::Type type = aset->GetValue()->GetType(); 78dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil if (Primitive::IsIntOrLongType(type)) { 79dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil ambiguous_asets_.push_back(aset); 80dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 81dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 82c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 83dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil void AddUninitializedString(HNewInstance* string) { 84dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // In some rare cases (b/27847265), the same NewInstance may be seen 85dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // multiple times. We should only consider it once for removal, so we 86dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // ensure it is not added more than once. 87dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // Note that we cannot check whether this really is a NewInstance of String 88dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // before RTP. We DCHECK that in RemoveRedundantUninitializedStrings. 89dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil if (!ContainsElement(uninitialized_strings_, string)) { 90dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil uninitialized_strings_.push_back(string); 91dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 92dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 93d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 94c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray private: 95809d70f5b268227dbd59432dc038c74d8351be29David Brazdil void SetLoopHeaderPhiInputs(); 964833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil void FixEnvironmentPhis(); 97a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle void FixNullConstantType(); 98a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle void EquivalentPhisCleanup(); 994833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil void RunPrimitiveTypePropagation(); 1004833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 10115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // Attempts to resolve types of aget(-wide) instructions and type values passed 10215693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // to aput(-wide) instructions from reference type information on the array 10315693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // input. Returns false if the type of an array is unknown. 10415693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil bool FixAmbiguousArrayOps(); 1054833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 1064833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil bool TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist); 1074833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil bool UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist); 1084833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil void ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist); 109a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 1104833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HFloatConstant* GetFloatEquivalent(HIntConstant* constant); 1114833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); 1124833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); 1134833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget); 1144833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 11565902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil void RemoveRedundantUninitializedStrings(); 11665902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil 117dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil HGraph* graph_; 118a4336d253b88f95c49891a8084579a4599785e90Vladimir Marko Handle<mirror::DexCache> dex_cache_; 1194833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil StackHandleScopeCollection* const handles_; 1204833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 1214833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // True if types of ambiguous ArrayGets have been resolved. 1224833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil bool agets_fixed_; 1238d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 1244833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil ArenaVector<HArrayGet*> ambiguous_agets_; 12515693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil ArenaVector<HArraySet*> ambiguous_asets_; 12665902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil ArenaVector<HNewInstance*> uninitialized_strings_; 1274833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 128c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(SsaBuilder); 129c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray}; 130c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 131c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} // namespace art 132c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 133c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray#endif // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 134