1 /*
2 * Copyright (C) 2013 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 #include "scoped_thread_state_change.h"
17 #include "sea_ir/types/type_inference.h"
18 #include "sea_ir/types/type_inference_visitor.h"
19 #include "sea_ir/ir/sea.h"
20
21 namespace sea_ir {
22
IsPrimitiveDescriptor(char descriptor)23 bool TypeInference::IsPrimitiveDescriptor(char descriptor) {
24 switch (descriptor) {
25 case 'I':
26 case 'C':
27 case 'S':
28 case 'B':
29 case 'Z':
30 case 'F':
31 case 'D':
32 case 'J':
33 return true;
34 default:
35 return false;
36 }
37 }
38
FunctionTypeInfo(const SeaGraph * graph,art::verifier::RegTypeCache * types)39 FunctionTypeInfo::FunctionTypeInfo(const SeaGraph* graph, art::verifier::RegTypeCache* types)
40 : dex_file_(graph->GetDexFile()), dex_method_idx_(graph->method_idx_), type_cache_(types),
41 method_access_flags_(graph->method_access_flags_) {
42 const art::DexFile::MethodId& method_id = dex_file_->GetMethodId(dex_method_idx_);
43 const char* descriptor = dex_file_->GetTypeDescriptor(dex_file_->GetTypeId(method_id.class_idx_));
44 declaring_class_ = &(type_cache_->FromDescriptor(NULL, descriptor, false));
45 }
46
FunctionTypeInfo(const SeaGraph * graph,InstructionNode * inst,art::verifier::RegTypeCache * types)47 FunctionTypeInfo::FunctionTypeInfo(const SeaGraph* graph, InstructionNode* inst,
48 art::verifier::RegTypeCache* types): dex_file_(graph->GetDexFile()),
49 dex_method_idx_(inst->GetInstruction()->VRegB_35c()), type_cache_(types),
50 method_access_flags_(0) {
51 // TODO: Test that GetDeclaredArgumentTypes() works correctly when using this constructor.
52 const art::DexFile::MethodId& method_id = dex_file_->GetMethodId(dex_method_idx_);
53 const char* descriptor = dex_file_->GetTypeDescriptor(dex_file_->GetTypeId(method_id.class_idx_));
54 declaring_class_ = &(type_cache_->FromDescriptor(NULL, descriptor, false));
55 }
56
GetReturnValueType()57 const Type* FunctionTypeInfo::GetReturnValueType() {
58 const art::DexFile::MethodId& method_id = dex_file_->GetMethodId(dex_method_idx_);
59 uint32_t return_type_idx = dex_file_->GetProtoId(method_id.proto_idx_).return_type_idx_;
60 const char* descriptor = dex_file_->StringByTypeIdx(return_type_idx);
61 art::ScopedObjectAccess soa(art::Thread::Current());
62 const Type& return_type = type_cache_->FromDescriptor(NULL, descriptor, false);
63 return &return_type;
64 }
65
66
67
GetDeclaredArgumentTypes()68 std::vector<const Type*> FunctionTypeInfo::GetDeclaredArgumentTypes() {
69 art::ScopedObjectAccess soa(art::Thread::Current());
70 std::vector<const Type*> argument_types;
71 // TODO: The additional (fake) Method parameter is added on the first position,
72 // but is represented as integer because we don't support pointers yet.
73 argument_types.push_back(&(type_cache_->Integer()));
74 // Include the "this" pointer.
75 size_t cur_arg = 0;
76 if (!IsStatic()) {
77 // If this is a constructor for a class other than java.lang.Object, mark the first ("this")
78 // argument as uninitialized. This restricts field access until the superclass constructor is
79 // called.
80 const art::verifier::RegType& declaring_class = GetDeclaringClass();
81 if (IsConstructor() && !declaring_class.IsJavaLangObject()) {
82 argument_types.push_back(&(type_cache_->UninitializedThisArgument(declaring_class)));
83 } else {
84 argument_types.push_back(&declaring_class);
85 }
86 cur_arg++;
87 }
88 // Include the types of the parameters in the Java method signature.
89 const art::DexFile::ProtoId& proto_id =
90 dex_file_->GetMethodPrototype(dex_file_->GetMethodId(dex_method_idx_));
91 art::DexFileParameterIterator iterator(*dex_file_, proto_id);
92
93 for (; iterator.HasNext(); iterator.Next()) {
94 const char* descriptor = iterator.GetDescriptor();
95 if (descriptor == NULL) {
96 LOG(FATAL) << "Error: Encountered null type descriptor for function argument.";
97 }
98 switch (descriptor[0]) {
99 case 'L':
100 case '[':
101 // We assume that reference arguments are initialized. The only way it could be otherwise
102 // (assuming the caller was verified) is if the current method is <init>, but in that case
103 // it's effectively considered initialized the instant we reach here (in the sense that we
104 // can return without doing anything or call virtual methods).
105 {
106 const Type& reg_type = type_cache_->FromDescriptor(NULL, descriptor, false);
107 argument_types.push_back(®_type);
108 }
109 break;
110 case 'Z':
111 argument_types.push_back(&type_cache_->Boolean());
112 break;
113 case 'C':
114 argument_types.push_back(&type_cache_->Char());
115 break;
116 case 'B':
117 argument_types.push_back(&type_cache_->Byte());
118 break;
119 case 'I':
120 argument_types.push_back(&type_cache_->Integer());
121 break;
122 case 'S':
123 argument_types.push_back(&type_cache_->Short());
124 break;
125 case 'F':
126 argument_types.push_back(&type_cache_->Float());
127 break;
128 case 'J':
129 case 'D': {
130 // TODO: Figure out strategy for two-register operands (double, long)
131 LOG(FATAL) << "Error: Type inference for 64-bit variables has not been implemented.";
132 break;
133 }
134 default:
135 LOG(FATAL) << "Error: Unexpected signature encountered during type inference.";
136 }
137 cur_arg++;
138 }
139 return argument_types;
140 }
141
142 // TODO: Lock is only used for dumping types (during development). Remove this for performance.
ComputeTypes(SeaGraph * graph)143 void TypeInference::ComputeTypes(SeaGraph* graph) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
144 std::vector<Region*>* regions = graph->GetRegions();
145 std::list<InstructionNode*> worklist;
146 // Fill the work-list with all instructions.
147 for (std::vector<Region*>::const_iterator region_it = regions->begin();
148 region_it != regions->end(); region_it++) {
149 std::vector<PhiInstructionNode*>* phi_instructions = (*region_it)->GetPhiNodes();
150 std::copy(phi_instructions->begin(), phi_instructions->end(), std::back_inserter(worklist));
151 std::vector<InstructionNode*>* instructions = (*region_it)->GetInstructions();
152 std::copy(instructions->begin(), instructions->end(), std::back_inserter(worklist));
153 }
154 TypeInferenceVisitor tiv(graph, &type_data_, type_cache_);
155 // Record return type of the function.
156 graph->Accept(&tiv);
157 const Type* new_type = tiv.GetType();
158 type_data_.SetTypeOf(-1, new_type); // TODO: Record this info in a way that
159 // does not need magic constants.
160 // Make SeaGraph a SeaNode?
161
162 // Sparse (SSA) fixed-point algorithm that processes each instruction in the work-list,
163 // adding consumers of instructions whose result changed type back into the work-list.
164 // Note: According to [1] list iterators should not be invalidated on insertion,
165 // which simplifies the implementation; not 100% sure other STL implementations
166 // maintain this invariant, but they should.
167 // [1] http://www.sgi.com/tech/stl/List.html
168 // TODO: Making this conditional (as in sparse conditional constant propagation) would be good.
169 // TODO: Remove elements as I go.
170 for (std::list<InstructionNode*>::const_iterator instruction_it = worklist.begin();
171 instruction_it != worklist.end(); instruction_it++) {
172 (*instruction_it)->Accept(&tiv);
173 const Type* old_type = type_data_.FindTypeOf((*instruction_it)->Id());
174 const Type* new_type = tiv.GetType();
175 bool type_changed = (old_type != new_type);
176 if (type_changed) {
177 type_data_.SetTypeOf((*instruction_it)->Id(), new_type);
178 // Add SSA consumers of the current instruction to the work-list.
179 std::vector<InstructionNode*>* consumers = (*instruction_it)->GetSSAConsumers();
180 for (std::vector<InstructionNode*>::iterator consumer = consumers->begin();
181 consumer != consumers->end(); consumer++) {
182 worklist.push_back(*consumer);
183 }
184 }
185 }
186 }
187 } // namespace sea_ir
188