1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 18 #define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 19 20 #include "base/scoped_arena_allocator.h" 21 #include "base/scoped_arena_containers.h" 22 #include "nodes.h" 23 #include "optimization.h" 24 25 namespace art { 26 27 /** 28 * Transforms a graph into SSA form. The liveness guarantees of 29 * this transformation are listed below. A DEX register 30 * being killed means its value at a given position in the code 31 * will not be available to its environment uses. A merge in the 32 * following text is materialized as a `HPhi`. 33 * 34 * (a) Dex registers that do not require merging (that is, they do not 35 * have different values at a join block) are available to all their 36 * environment uses. Note that it does not imply the instruction will 37 * have a physical location after register allocation. See the 38 * SsaLivenessAnalysis phase. 39 * 40 * (b) Dex registers that require merging, and the merging gives 41 * incompatible types, will be killed for environment uses of that merge. 42 * 43 * (c) When the `debuggable` flag is passed to the compiler, Dex registers 44 * that require merging and have a proper type after the merge, are 45 * available to all their environment uses. If the `debuggable` flag 46 * is not set, values of Dex registers only used by environments 47 * are killed. 48 */ 49 class SsaBuilder : public ValueObject { 50 public: SsaBuilder(HGraph * graph,Handle<mirror::ClassLoader> class_loader,Handle<mirror::DexCache> dex_cache,VariableSizedHandleScope * handles,ScopedArenaAllocator * local_allocator)51 SsaBuilder(HGraph* graph, 52 Handle<mirror::ClassLoader> class_loader, 53 Handle<mirror::DexCache> dex_cache, 54 VariableSizedHandleScope* handles, 55 ScopedArenaAllocator* local_allocator) 56 : graph_(graph), 57 class_loader_(class_loader), 58 dex_cache_(dex_cache), 59 handles_(handles), 60 agets_fixed_(false), 61 local_allocator_(local_allocator), 62 ambiguous_agets_(local_allocator->Adapter(kArenaAllocGraphBuilder)), 63 ambiguous_asets_(local_allocator->Adapter(kArenaAllocGraphBuilder)), 64 uninitialized_strings_(local_allocator->Adapter(kArenaAllocGraphBuilder)), 65 uninitialized_string_phis_(local_allocator->Adapter(kArenaAllocGraphBuilder)) { 66 graph_->InitializeInexactObjectRTI(handles); 67 } 68 69 GraphAnalysisResult BuildSsa(); 70 71 HInstruction* GetFloatOrDoubleEquivalent(HInstruction* instruction, DataType::Type type); 72 HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); 73 MaybeAddAmbiguousArrayGet(HArrayGet * aget)74 void MaybeAddAmbiguousArrayGet(HArrayGet* aget) { 75 DataType::Type type = aget->GetType(); 76 DCHECK(!DataType::IsFloatingPointType(type)); 77 if (DataType::IsIntOrLongType(type)) { 78 ambiguous_agets_.push_back(aget); 79 } 80 } 81 MaybeAddAmbiguousArraySet(HArraySet * aset)82 void MaybeAddAmbiguousArraySet(HArraySet* aset) { 83 DataType::Type type = aset->GetValue()->GetType(); 84 if (DataType::IsIntOrLongType(type)) { 85 ambiguous_asets_.push_back(aset); 86 } 87 } 88 AddUninitializedString(HNewInstance * string)89 void AddUninitializedString(HNewInstance* string) { 90 // In some rare cases (b/27847265), the same NewInstance may be seen 91 // multiple times. We should only consider it once for removal, so we 92 // ensure it is not added more than once. 93 // Note that we cannot check whether this really is a NewInstance of String 94 // before RTP. We DCHECK that in RemoveRedundantUninitializedStrings. 95 if (!ContainsElement(uninitialized_strings_, string)) { 96 uninitialized_strings_.push_back(string); 97 } 98 } 99 AddUninitializedStringPhi(HInvoke * invoke)100 void AddUninitializedStringPhi(HInvoke* invoke) { 101 uninitialized_string_phis_.push_back(invoke); 102 } 103 104 private: 105 void SetLoopHeaderPhiInputs(); 106 void FixEnvironmentPhis(); 107 void FixNullConstantType(); 108 void EquivalentPhisCleanup(); 109 void RunPrimitiveTypePropagation(); 110 111 // Attempts to resolve types of aget(-wide) instructions and type values passed 112 // to aput(-wide) instructions from reference type information on the array 113 // input. Returns false if the type of an array is unknown. 114 bool FixAmbiguousArrayOps(); 115 116 bool TypeInputsOfPhi(HPhi* phi, ScopedArenaVector<HPhi*>* worklist); 117 bool UpdatePrimitiveType(HPhi* phi, ScopedArenaVector<HPhi*>* worklist); 118 void ProcessPrimitiveTypePropagationWorklist(ScopedArenaVector<HPhi*>* worklist); 119 120 HFloatConstant* GetFloatEquivalent(HIntConstant* constant); 121 HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); 122 HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, DataType::Type type); 123 HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget); 124 125 void RemoveRedundantUninitializedStrings(); 126 bool ReplaceUninitializedStringPhis(); 127 bool HasAliasInEnvironments(HInstruction* instruction); 128 129 HGraph* const graph_; 130 Handle<mirror::ClassLoader> class_loader_; 131 Handle<mirror::DexCache> dex_cache_; 132 VariableSizedHandleScope* const handles_; 133 134 // True if types of ambiguous ArrayGets have been resolved. 135 bool agets_fixed_; 136 137 ScopedArenaAllocator* const local_allocator_; 138 ScopedArenaVector<HArrayGet*> ambiguous_agets_; 139 ScopedArenaVector<HArraySet*> ambiguous_asets_; 140 ScopedArenaVector<HNewInstance*> uninitialized_strings_; 141 ScopedArenaVector<HInvoke*> uninitialized_string_phis_; 142 143 DISALLOW_COPY_AND_ASSIGN(SsaBuilder); 144 }; 145 146 } // namespace art 147 148 #endif // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 149