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
24namespace 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 */
48class SsaBuilder : public ValueObject {
49 public:
50  SsaBuilder(HGraph* graph,
51             Handle<mirror::DexCache> dex_cache,
52             StackHandleScopeCollection* handles)
53      : graph_(graph),
54        dex_cache_(dex_cache),
55        handles_(handles),
56        agets_fixed_(false),
57        ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
58        ambiguous_asets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
59        uninitialized_strings_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)) {
60    graph_->InitializeInexactObjectRTI(handles);
61  }
62
63  GraphAnalysisResult BuildSsa();
64
65  HInstruction* GetFloatOrDoubleEquivalent(HInstruction* instruction, Primitive::Type type);
66  HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction);
67
68  void MaybeAddAmbiguousArrayGet(HArrayGet* aget) {
69    Primitive::Type type = aget->GetType();
70    DCHECK(!Primitive::IsFloatingPointType(type));
71    if (Primitive::IsIntOrLongType(type)) {
72      ambiguous_agets_.push_back(aget);
73    }
74  }
75
76  void MaybeAddAmbiguousArraySet(HArraySet* aset) {
77    Primitive::Type type = aset->GetValue()->GetType();
78    if (Primitive::IsIntOrLongType(type)) {
79      ambiguous_asets_.push_back(aset);
80    }
81  }
82
83  void AddUninitializedString(HNewInstance* string) {
84    // In some rare cases (b/27847265), the same NewInstance may be seen
85    // multiple times. We should only consider it once for removal, so we
86    // ensure it is not added more than once.
87    // Note that we cannot check whether this really is a NewInstance of String
88    // before RTP. We DCHECK that in RemoveRedundantUninitializedStrings.
89    if (!ContainsElement(uninitialized_strings_, string)) {
90      uninitialized_strings_.push_back(string);
91    }
92  }
93
94 private:
95  void SetLoopHeaderPhiInputs();
96  void FixEnvironmentPhis();
97  void FixNullConstantType();
98  void EquivalentPhisCleanup();
99  void RunPrimitiveTypePropagation();
100
101  // Attempts to resolve types of aget(-wide) instructions and type values passed
102  // to aput(-wide) instructions from reference type information on the array
103  // input. Returns false if the type of an array is unknown.
104  bool FixAmbiguousArrayOps();
105
106  bool TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist);
107  bool UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist);
108  void ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist);
109
110  HFloatConstant* GetFloatEquivalent(HIntConstant* constant);
111  HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant);
112  HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type);
113  HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget);
114
115  void RemoveRedundantUninitializedStrings();
116
117  HGraph* graph_;
118  Handle<mirror::DexCache> dex_cache_;
119  StackHandleScopeCollection* const handles_;
120
121  // True if types of ambiguous ArrayGets have been resolved.
122  bool agets_fixed_;
123
124  ArenaVector<HArrayGet*> ambiguous_agets_;
125  ArenaVector<HArraySet*> ambiguous_asets_;
126  ArenaVector<HNewInstance*> uninitialized_strings_;
127
128  DISALLOW_COPY_AND_ASSIGN(SsaBuilder);
129};
130
131}  // namespace art
132
133#endif  // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
134