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/arena_containers.h"
21 #include "nodes.h"
22 #include "optimization.h"
23 
24 namespace art {
25 
26 /**
27  * Transforms a graph into SSA form. The liveness guarantees of
28  * this transformation are listed below. A DEX register
29  * being killed means its value at a given position in the code
30  * will not be available to its environment uses. A merge in the
31  * following text is materialized as a `HPhi`.
32  *
33  * (a) Dex registers that do not require merging (that is, they do not
34  *     have different values at a join block) are available to all their
35  *     environment uses. Note that it does not imply the instruction will
36  *     have a physical location after register allocation. See the
37  *     SsaLivenessAnalysis phase.
38  *
39  * (b) Dex registers that require merging, and the merging gives
40  *     incompatible types, will be killed for environment uses of that merge.
41  *
42  * (c) When the `debuggable` flag is passed to the compiler, Dex registers
43  *     that require merging and have a proper type after the merge, are
44  *     available to all their environment uses. If the `debuggable` flag
45  *     is not set, values of Dex registers only used by environments
46  *     are killed.
47  */
48 class SsaBuilder : public ValueObject {
49  public:
SsaBuilder(HGraph * graph,Handle<mirror::ClassLoader> class_loader,Handle<mirror::DexCache> dex_cache,VariableSizedHandleScope * handles)50   SsaBuilder(HGraph* graph,
51              Handle<mirror::ClassLoader> class_loader,
52              Handle<mirror::DexCache> dex_cache,
53              VariableSizedHandleScope* handles)
54       : graph_(graph),
55         class_loader_(class_loader),
56         dex_cache_(dex_cache),
57         handles_(handles),
58         agets_fixed_(false),
59         ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
60         ambiguous_asets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
61         uninitialized_strings_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)) {
62     graph_->InitializeInexactObjectRTI(handles);
63   }
64 
65   GraphAnalysisResult BuildSsa();
66 
67   HInstruction* GetFloatOrDoubleEquivalent(HInstruction* instruction, Primitive::Type type);
68   HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction);
69 
MaybeAddAmbiguousArrayGet(HArrayGet * aget)70   void MaybeAddAmbiguousArrayGet(HArrayGet* aget) {
71     Primitive::Type type = aget->GetType();
72     DCHECK(!Primitive::IsFloatingPointType(type));
73     if (Primitive::IsIntOrLongType(type)) {
74       ambiguous_agets_.push_back(aget);
75     }
76   }
77 
MaybeAddAmbiguousArraySet(HArraySet * aset)78   void MaybeAddAmbiguousArraySet(HArraySet* aset) {
79     Primitive::Type type = aset->GetValue()->GetType();
80     if (Primitive::IsIntOrLongType(type)) {
81       ambiguous_asets_.push_back(aset);
82     }
83   }
84 
AddUninitializedString(HNewInstance * string)85   void AddUninitializedString(HNewInstance* string) {
86     // In some rare cases (b/27847265), the same NewInstance may be seen
87     // multiple times. We should only consider it once for removal, so we
88     // ensure it is not added more than once.
89     // Note that we cannot check whether this really is a NewInstance of String
90     // before RTP. We DCHECK that in RemoveRedundantUninitializedStrings.
91     if (!ContainsElement(uninitialized_strings_, string)) {
92       uninitialized_strings_.push_back(string);
93     }
94   }
95 
96  private:
97   void SetLoopHeaderPhiInputs();
98   void FixEnvironmentPhis();
99   void FixNullConstantType();
100   void EquivalentPhisCleanup();
101   void RunPrimitiveTypePropagation();
102 
103   // Attempts to resolve types of aget(-wide) instructions and type values passed
104   // to aput(-wide) instructions from reference type information on the array
105   // input. Returns false if the type of an array is unknown.
106   bool FixAmbiguousArrayOps();
107 
108   bool TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist);
109   bool UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist);
110   void ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist);
111 
112   HFloatConstant* GetFloatEquivalent(HIntConstant* constant);
113   HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant);
114   HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type);
115   HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget);
116 
117   void RemoveRedundantUninitializedStrings();
118 
119   HGraph* graph_;
120   Handle<mirror::ClassLoader> class_loader_;
121   Handle<mirror::DexCache> dex_cache_;
122   VariableSizedHandleScope* const handles_;
123 
124   // True if types of ambiguous ArrayGets have been resolved.
125   bool agets_fixed_;
126 
127   ArenaVector<HArrayGet*> ambiguous_agets_;
128   ArenaVector<HArraySet*> ambiguous_asets_;
129   ArenaVector<HNewInstance*> uninitialized_strings_;
130 
131   DISALLOW_COPY_AND_ASSIGN(SsaBuilder);
132 };
133 
134 }  // namespace art
135 
136 #endif  // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
137