SEA IR type handling complete for fibonacci.
types.h: Encapsulated types map into separate class.
code_gen.*, visitor.h: Added visitor function for
unnamed constants to enable correct
.dot display and type handling.
type_inference_visitor.cc: Propagated types through
phi functions, invoke, add-int instructions. Added
SEA IR type merging functions.
Change-Id: I0fb1c4d40e3af43dc295133a826ce125a787cc33
diff --git a/compiler/sea_ir/code_gen.cc b/compiler/sea_ir/code_gen.cc
index 0ef21b4..7fd6c86 100644
--- a/compiler/sea_ir/code_gen.cc
+++ b/compiler/sea_ir/code_gen.cc
@@ -114,6 +114,14 @@
std::string instr = instruction->GetInstruction()->DumpString(NULL);
DCHECK(0); // This whole function is useful only during development.
}
+
+void CodeGenVisitor::Visit(UnnamedConstInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "1.Instruction: " << instr << std::endl;
+ llvm_data_->AddValue(instruction,
+ llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, instruction->GetConstValue())));
+}
+
void CodeGenVisitor::Visit(ConstInstructionNode* instruction) {
std::string instr = instruction->GetInstruction()->DumpString(NULL);
std::cout << "1.Instruction: " << instr << std::endl;
diff --git a/compiler/sea_ir/code_gen.h b/compiler/sea_ir/code_gen.h
index 5fea79a..edef19d 100644
--- a/compiler/sea_ir/code_gen.h
+++ b/compiler/sea_ir/code_gen.h
@@ -101,6 +101,8 @@
void Visit(SignatureNode* region);
void Visit(Region* region);
void Visit(InstructionNode* instruction) { }
+
+ void Visit(UnnamedConstInstructionNode* instruction) { }
void Visit(ConstInstructionNode* instruction) { }
void Visit(ReturnInstructionNode* instruction) { }
void Visit(IfNeInstructionNode* instruction) { }
@@ -120,6 +122,7 @@
void Visit(SignatureNode* region);
void Visit(Region* region);
void Visit(InstructionNode* region) { }
+ void Visit(UnnamedConstInstructionNode* instruction) { }
void Visit(ConstInstructionNode* instruction) { }
void Visit(ReturnInstructionNode* instruction) { }
void Visit(IfNeInstructionNode* instruction) { }
@@ -139,10 +142,10 @@
void Visit(SignatureNode* region);
void Visit(Region* region);
void Visit(InstructionNode* region);
+ void Visit(UnnamedConstInstructionNode* instruction);
void Visit(ConstInstructionNode* instruction);
void Visit(ReturnInstructionNode* instruction);
void Visit(IfNeInstructionNode* instruction);
- // void Visit(AddIntLitInstructionNode* instruction);
void Visit(MoveResultInstructionNode* instruction);
void Visit(InvokeStaticInstructionNode* instruction);
void Visit(AddIntInstructionNode* instruction);
diff --git a/compiler/sea_ir/debug/dot_gen.cc b/compiler/sea_ir/debug/dot_gen.cc
index ecb641e..9442684 100644
--- a/compiler/sea_ir/debug/dot_gen.cc
+++ b/compiler/sea_ir/debug/dot_gen.cc
@@ -14,6 +14,7 @@
* limitations under the License.
*/
+
#include "scoped_thread_state_change.h"
#include "sea_ir/debug/dot_gen.h"
@@ -50,7 +51,7 @@
dot_text_ += def_it->second->StringId() + " -> ";
dot_text_ += instruction->StringId() + "[color=gray,label=\"";
dot_text_ += art::StringPrintf("vR = %d", def_it->first);
- std::map<int, const Type*>::const_iterator type_it = types_->find(def_it->second->Id());
+ art::SafeMap<int, const Type*>::const_iterator type_it = types_->find(def_it->second->Id());
if (type_it != types_->end()) {
art::ScopedObjectAccess soa(art::Thread::Current());
dot_text_ += "(" + type_it->second->Dump() + ")";
@@ -82,7 +83,7 @@
dot_text_ += (*def_it)->StringId() + " -> ";
dot_text_ += instruction->StringId() + "[color=gray,label=\"";
dot_text_ += art::StringPrintf("vR = %d", instruction->GetRegisterNumber());
- std::map<int, const Type*>::const_iterator type_it = types_->find((*def_it)->Id());
+ art::SafeMap<int, const Type*>::const_iterator type_it = types_->find((*def_it)->Id());
if (type_it != types_->end()) {
art::ScopedObjectAccess soa(art::Thread::Current());
dot_text_ += "(" + type_it->second->Dump() + ")";
diff --git a/compiler/sea_ir/debug/dot_gen.h b/compiler/sea_ir/debug/dot_gen.h
index df74901..301c70f 100644
--- a/compiler/sea_ir/debug/dot_gen.h
+++ b/compiler/sea_ir/debug/dot_gen.h
@@ -17,6 +17,7 @@
#ifndef ART_COMPILER_SEA_IR_DEBUG_DOT_GEN_H_
#define ART_COMPILER_SEA_IR_DEBUG_DOT_GEN_H_
+#include "safe_map.h"
#include "base/stringprintf.h"
#include "file_output_stream.h"
#include "sea_ir/sea.h"
@@ -37,7 +38,7 @@
class DotGenerationVisitor: public IRVisitor {
public:
explicit DotGenerationVisitor(const DotConversionOptions* const options,
- std::map<int, const Type*>* types): graph_(), types_(types), options_(options) { }
+ art::SafeMap<int, const Type*>* types): graph_(), types_(types), options_(options) { }
virtual void Initialize(SeaGraph* graph);
// Saves the ssa def->use edges corresponding to @instruction.
@@ -88,7 +89,7 @@
private:
std::string dot_text_;
SeaGraph* graph_;
- std::map<int, const Type*>* types_;
+ art::SafeMap<int, const Type*>* types_;
const DotConversionOptions* const options_;
};
@@ -97,7 +98,8 @@
public:
DotConversion(): options_() { }
// Saves to @filename the .dot representation of @graph with the options @options.
- void DumpSea(SeaGraph* graph, std::string filename, std::map<int, const Type*>* types) const {
+ void DumpSea(SeaGraph* graph, std::string filename,
+ art::SafeMap<int, const Type*>* types) const {
LOG(INFO) << "Starting to write SEA string to file.";
DotGenerationVisitor dgv = DotGenerationVisitor(&options_, types);
graph->Accept(&dgv);
diff --git a/compiler/sea_ir/frontend.cc b/compiler/sea_ir/frontend.cc
index 951273c..b6f84ee 100644
--- a/compiler/sea_ir/frontend.cc
+++ b/compiler/sea_ir/frontend.cc
@@ -23,7 +23,7 @@
#include "llvm/llvm_compilation_unit.h"
#include "mirror/object.h"
#include "runtime.h"
-
+#include "safe_map.h"
#include "sea_ir/sea.h"
#include "sea_ir/debug/dot_gen.h"
@@ -46,8 +46,8 @@
sea_ir::SeaGraph* ir_graph = sea_ir::SeaGraph::GetCurrentGraph(dex_file);
ir_graph->CompileMethod(code_item, class_def_idx, method_idx, method_access_flags, dex_file);
sea_ir::DotConversion dc;
- std::map<int, const sea_ir::Type*> types = ir_graph->ti_->GetTypeMap();
- dc.DumpSea(ir_graph, "/tmp/temp.dot", &types);
+ SafeMap<int, const sea_ir::Type*>* types = ir_graph->ti_->GetTypeMap();
+ dc.DumpSea(ir_graph, "/tmp/temp.dot", types);
CHECK(0 && "No SEA compiled function exists yet.");
return NULL;
}
diff --git a/compiler/sea_ir/types/type_inference.cc b/compiler/sea_ir/types/type_inference.cc
index 78888f3..77470c2 100644
--- a/compiler/sea_ir/types/type_inference.cc
+++ b/compiler/sea_ir/types/type_inference.cc
@@ -13,7 +13,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
+#include "scoped_thread_state_change.h"
#include "sea_ir/types/type_inference.h"
#include "sea_ir/types/type_inference_visitor.h"
#include "sea_ir/sea.h"
@@ -44,8 +44,29 @@
declaring_class_ = &(type_cache_->FromDescriptor(NULL, descriptor, false));
}
-std::vector<const Type*> FunctionTypeInfo::GetDeclaredArgumentTypes()
- SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+FunctionTypeInfo::FunctionTypeInfo(const SeaGraph* graph, InstructionNode* inst,
+ art::verifier::RegTypeCache* types): dex_file_(graph->GetDexFile()),
+ dex_method_idx_(inst->GetInstruction()->VRegB_35c()), type_cache_(types),
+ method_access_flags_(0) {
+ // TODO: Test that GetDeclaredArgumentTypes() works correctly when using this constructor.
+ const art::DexFile::MethodId& method_id = dex_file_->GetMethodId(dex_method_idx_);
+ const char* descriptor = dex_file_->GetTypeDescriptor(dex_file_->GetTypeId(method_id.class_idx_));
+ declaring_class_ = &(type_cache_->FromDescriptor(NULL, descriptor, false));
+}
+
+const Type* FunctionTypeInfo::GetReturnValueType() {
+ const art::DexFile::MethodId& method_id = dex_file_->GetMethodId(dex_method_idx_);
+ uint32_t return_type_idx = dex_file_->GetProtoId(method_id.proto_idx_).return_type_idx_;
+ const char* descriptor = dex_file_->StringByTypeIdx(return_type_idx);
+ art::ScopedObjectAccess soa(art::Thread::Current());
+ const Type& return_type = type_cache_->FromDescriptor(NULL, descriptor, false);
+ return &return_type;
+}
+
+
+
+std::vector<const Type*> FunctionTypeInfo::GetDeclaredArgumentTypes() {
+ art::ScopedObjectAccess soa(art::Thread::Current());
std::vector<const Type*> argument_types;
// Include the "this" pointer.
size_t cur_arg = 0;
@@ -127,7 +148,7 @@
std::vector<InstructionNode*>* instructions = (*region_it)->GetInstructions();
std::copy(instructions->begin(), instructions->end(), std::back_inserter(worklist));
}
- TypeInferenceVisitor tiv(graph, type_cache_);
+ TypeInferenceVisitor tiv(graph, &type_data_, type_cache_);
// Sparse (SSA) fixed-point algorithm that processes each instruction in the work-list,
// adding consumers of instructions whose result changed type back into the work-list.
// Note: According to [1] list iterators should not be invalidated on insertion,
@@ -140,15 +161,13 @@
instruction_it != worklist.end(); instruction_it++) {
std::cout << "[TI] Instruction: " << (*instruction_it)->Id() << std::endl;
(*instruction_it)->Accept(&tiv);
- std::map<int, const Type*>::const_iterator old_result_it =
- type_map_.find((*instruction_it)->Id());
+ const Type* old_type = type_data_.FindTypeOf((*instruction_it)->Id());
const Type* new_type = tiv.GetType();
- bool first_time_set = (old_result_it == type_map_.end()) && (new_type != NULL);
- bool type_changed = (old_result_it != type_map_.end()) && ((*old_result_it).second != new_type);
- if (first_time_set || type_changed) {
+ bool type_changed = (old_type != new_type);
+ if (type_changed) {
std::cout << " New type:" << new_type->IsIntegralTypes() << std::endl;
- std::cout << " Descrip:" << new_type->Dump()<< "on " << (*instruction_it)->Id() << std::endl;
- type_map_[(*instruction_it)->Id()] = new_type;
+ std::cout << " Descrip:" << new_type->Dump()<< " on " << (*instruction_it)->Id() << std::endl;
+ type_data_.SetTypeOf((*instruction_it)->Id(), new_type);
// Add SSA consumers of the current instruction to the work-list.
std::vector<InstructionNode*>* consumers = (*instruction_it)->GetSSAConsumers();
for (std::vector<InstructionNode*>::iterator consumer = consumers->begin();
diff --git a/compiler/sea_ir/types/type_inference.h b/compiler/sea_ir/types/type_inference.h
index 9014c96..d951d82 100644
--- a/compiler/sea_ir/types/type_inference.h
+++ b/compiler/sea_ir/types/type_inference.h
@@ -17,16 +17,18 @@
#ifndef ART_COMPILER_SEA_IR_TYPES_TYPE_INFERENCE_H_
#define ART_COMPILER_SEA_IR_TYPES_TYPE_INFERENCE_H_
+#include "safe_map.h"
#include "dex_file-inl.h"
#include "sea_ir/types/types.h"
namespace sea_ir {
class SeaGraph;
+class InstructionNode;
// The type inference in SEA IR is different from the verifier in that it is concerned
// with a rich type hierarchy (TODO) usable in optimization and does not perform
-// precise verification which is the job of the verifier.
+// precise verification (which is the job of the verifier).
class TypeInference {
public:
TypeInference() {
@@ -36,26 +38,37 @@
// Computes the types for the method with SEA IR representation provided by @graph.
void ComputeTypes(SeaGraph* graph);
- std::map<int, const Type*> GetTypeMap() const {
- return type_map_;
+ art::SafeMap<int, const Type*>* GetTypeMap() {
+ return type_data_.GetTypeMap();
}
// Returns true if @descriptor corresponds to a primitive type.
static bool IsPrimitiveDescriptor(char descriptor);
protected:
art::verifier::RegTypeCache* type_cache_;
- std::map<int, const Type*> type_map_;
+ TypeData type_data_;
};
// Stores information about the exact type of a function.
class FunctionTypeInfo {
public:
+ // Finds method information about the method encoded by a SEA IR graph.
// @graph provides the input method SEA IR representation.
// @types provides the input cache of types from which the
// parameter types of the function are found.
FunctionTypeInfo(const SeaGraph* graph, art::verifier::RegTypeCache* types);
+ // Finds method information about the method encoded by
+ // an invocation instruction in a SEA IR graph.
+ // @graph provides the input method SEA IR representation.
+ // @inst is an invocation instruction for the desired method.
+ // @types provides the input cache of types from which the
+ // parameter types of the function are found.
+ FunctionTypeInfo(const SeaGraph* graph, InstructionNode* inst,
+ art::verifier::RegTypeCache* types);
// Returns the ordered vector of types corresponding to the function arguments.
std::vector<const Type*> GetDeclaredArgumentTypes();
+ // Returns the declared return value type.
+ const Type* GetReturnValueType();
// Returns the type corresponding to the class that declared the method.
const Type& GetDeclaringClass() {
return *declaring_class_;
diff --git a/compiler/sea_ir/types/type_inference_visitor.cc b/compiler/sea_ir/types/type_inference_visitor.cc
index 8faa4d5..bafe5c5 100644
--- a/compiler/sea_ir/types/type_inference_visitor.cc
+++ b/compiler/sea_ir/types/type_inference_visitor.cc
@@ -14,6 +14,7 @@
* limitations under the License.
*/
+#include "scoped_thread_state_change.h"
#include "sea_ir/types/type_inference_visitor.h"
#include "sea_ir/types/type_inference.h"
#include "sea_ir/sea.h"
@@ -21,13 +22,81 @@
namespace sea_ir {
void TypeInferenceVisitor::Visit(SignatureNode* parameter) {
- std::cout << "[TI] Visiting signature node:" << parameter->GetResultRegister() << std::endl;
FunctionTypeInfo fti(graph_, type_cache_);
std::vector<const Type*> arguments = fti.GetDeclaredArgumentTypes();
- crt_type_.clear();
DCHECK_LT(parameter->GetPositionInSignature(), arguments.size())
<< "Signature node position not present in signature.";
crt_type_.push_back(arguments.at(parameter->GetPositionInSignature()));
}
+void TypeInferenceVisitor::Visit(UnnamedConstInstructionNode* instruction) {
+ crt_type_.push_back(&type_cache_->Integer());
+}
+
+void TypeInferenceVisitor::Visit(PhiInstructionNode* instruction) {
+ std::vector<const Type*> types_to_merge = GetOperandTypes(instruction);
+ const Type* result_type = MergeTypes(types_to_merge);
+ crt_type_.push_back(result_type);
+}
+
+void TypeInferenceVisitor::Visit(AddIntInstructionNode* instruction) {
+ std::vector<const Type*> operand_types = GetOperandTypes(instruction);
+ for (std::vector<const Type*>::const_iterator cit = operand_types.begin();
+ cit != operand_types.end(); cit++) {
+ if (*cit != NULL) {
+ DCHECK((*cit)->IsInteger());
+ }
+ }
+ crt_type_.push_back(&type_cache_->Integer());
+}
+
+void TypeInferenceVisitor::Visit(MoveResultInstructionNode* instruction) {
+ std::vector<const Type*> operand_types = GetOperandTypes(instruction);
+ const Type* operand_type = operand_types.at(0);
+ crt_type_.push_back(operand_type);
+}
+
+void TypeInferenceVisitor::Visit(InvokeStaticInstructionNode* instruction) {
+ FunctionTypeInfo fti(graph_, instruction, type_cache_);
+ const Type* result_type = fti.GetReturnValueType();
+ crt_type_.push_back(result_type);
+}
+
+std::vector<const Type*> TypeInferenceVisitor::GetOperandTypes(InstructionNode* instruction) {
+ std::vector<InstructionNode*> sources = instruction->GetSSAProducers();
+ std::vector<const Type*> types_to_merge;
+ for (std::vector<InstructionNode*>::const_iterator cit = sources.begin(); cit != sources.end();
+ cit++) {
+ const Type* source_type = type_data_->FindTypeOf((*cit)->Id());
+ if (source_type != NULL) {
+ types_to_merge.push_back(source_type);
+ }
+ }
+ return types_to_merge;
+}
+
+const Type* TypeInferenceVisitor::MergeTypes(std::vector<const Type*>& types) const {
+ const Type* type = NULL;
+ if (types.size()>0) {
+ type = *(types.begin());
+ if (types.size()>1) {
+ for (std::vector<const Type*>::const_iterator cit = types.begin();
+ cit != types.end(); cit++) {
+ if (!type->Equals(**cit)) {
+ type = MergeTypes(type, *cit);
+ }
+ }
+ }
+ }
+ return type;
+}
+
+const Type* TypeInferenceVisitor::MergeTypes(const Type* t1, const Type* t2) const {
+ DCHECK(t2 != NULL);
+ DCHECK(t1 != NULL);
+ art::ScopedObjectAccess soa(art::Thread::Current());
+ const Type* result = &(t1->Merge(*t2, type_cache_));
+ return result;
+}
+
} // namespace sea_ir
diff --git a/compiler/sea_ir/types/type_inference_visitor.h b/compiler/sea_ir/types/type_inference_visitor.h
index bf7f4c0..889557d 100644
--- a/compiler/sea_ir/types/type_inference_visitor.h
+++ b/compiler/sea_ir/types/type_inference_visitor.h
@@ -34,26 +34,31 @@
// version 2: with template return value).
class TypeInferenceVisitor: public IRVisitor {
public:
- TypeInferenceVisitor(SeaGraph* graph, art::verifier::RegTypeCache* types):
- graph_(graph), type_cache_(types), crt_type_() {
+ TypeInferenceVisitor(SeaGraph* graph, TypeData* type_data,
+ art::verifier::RegTypeCache* types):
+ graph_(graph), type_data_(type_data), type_cache_(types), crt_type_() {
}
// There are no type related actions to be performed on these classes.
void Initialize(SeaGraph* graph) { }
void Visit(SeaGraph* graph) { }
void Visit(Region* region) { }
- void Visit(PhiInstructionNode* instruction) { }
+ void Visit(PhiInstructionNode* instruction);
void Visit(SignatureNode* parameter);
void Visit(InstructionNode* instruction) { }
+ void Visit(UnnamedConstInstructionNode* instruction);
void Visit(ConstInstructionNode* instruction) { }
void Visit(ReturnInstructionNode* instruction) { }
void Visit(IfNeInstructionNode* instruction) { }
- void Visit(MoveResultInstructionNode* instruction) { }
- void Visit(InvokeStaticInstructionNode* instruction) { }
- void Visit(AddIntInstructionNode* instruction) { }
+ void Visit(MoveResultInstructionNode* instruction);
+ void Visit(InvokeStaticInstructionNode* instruction);
+ void Visit(AddIntInstructionNode* instruction);
void Visit(GotoInstructionNode* instruction) { }
void Visit(IfEqzInstructionNode* instruction) { }
+ const Type* MergeTypes(std::vector<const Type*>& types) const;
+ const Type* MergeTypes(const Type* t1, const Type* t2) const;
+
const Type* GetType() {
// TODO: Currently multiple defined types are not supported.
if (crt_type_.size()>0) {
@@ -66,8 +71,12 @@
protected:
const SeaGraph* const graph_;
+ TypeData* type_data_;
art::verifier::RegTypeCache* type_cache_;
std::vector<const Type*> crt_type_; // Stored temporarily between two calls to Visit.
+
+ private:
+ std::vector<const Type*> GetOperandTypes(InstructionNode* instruction);
};
} // namespace sea_ir
diff --git a/compiler/sea_ir/types/types.h b/compiler/sea_ir/types/types.h
index 8aa5d16..64f2524 100644
--- a/compiler/sea_ir/types/types.h
+++ b/compiler/sea_ir/types/types.h
@@ -17,6 +17,7 @@
#ifndef ART_COMPILER_SEA_IR_TYPES_TYPES_H_
#define ART_COMPILER_SEA_IR_TYPES_TYPES_H_
+#include "safe_map.h"
#include "verifier/reg_type.h"
#include "verifier/reg_type_cache.h"
@@ -25,5 +26,33 @@
// TODO: Replace typedef with an actual class implementation when we have more types.
typedef art::verifier::RegType Type;
+// Stores information about the result type of each instruction.
+// Note: Main purpose is to encapsulate the map<instruction id, type*>,
+// so that we can replace the underlying storage at any time.
+class TypeData {
+ public:
+ art::SafeMap<int, const Type*>* GetTypeMap() {
+ return &type_map_;
+ }
+ // Returns the type associated with instruction with @instruction_id.
+ const Type* FindTypeOf(int instruction_id) {
+ art::SafeMap<int, const Type*>::const_iterator result_it = type_map_.find(instruction_id);
+ if (type_map_.end() != result_it) {
+ return result_it->second;
+ }
+ return NULL;
+ }
+
+ // Saves the fact that instruction @instruction_id produces a value of type @type.
+ void SetTypeOf(int instruction_id, const Type* type) {
+ type_map_.Overwrite(instruction_id, type);
+ }
+
+ private:
+ art::SafeMap<int, const Type*> type_map_;
+};
+
+
+
} // namespace sea_ir
#endif // ART_COMPILER_SEA_IR_TYPES_TYPES_H_
diff --git a/compiler/sea_ir/visitor.h b/compiler/sea_ir/visitor.h
index ffb073e..4f207da 100644
--- a/compiler/sea_ir/visitor.h
+++ b/compiler/sea_ir/visitor.h
@@ -24,6 +24,7 @@
class InstructionNode;
class PhiInstructionNode;
class SignatureNode;
+class UnnamedConstInstructionNode;
class ConstInstructionNode;
class ReturnInstructionNode;
class IfNeInstructionNode;
@@ -49,9 +50,9 @@
virtual void Visit(InstructionNode* region) = 0;
virtual void Visit(ConstInstructionNode* instruction) = 0;
+ virtual void Visit(UnnamedConstInstructionNode* instruction) = 0;
virtual void Visit(ReturnInstructionNode* instruction) = 0;
virtual void Visit(IfNeInstructionNode* instruction) = 0;
- // virtual void Visit(AddIntLitInstructionNode* instruction) = 0;
virtual void Visit(MoveResultInstructionNode* instruction) = 0;
virtual void Visit(InvokeStaticInstructionNode* instruction) = 0;
virtual void Visit(AddIntInstructionNode* instruction) = 0;
