Added SEA IR type infrastructure (and a bit of cleanup).

compiler/Android.mk: Added new files to compile.
instruction_nodes.h,
code_gen.cc: Renamed GetSSAUses to GetSSAProducers to avoid confusion
             (uses of what?).
sea.cc: Added invoke of type inference framework.
sea.h: Expose dex_file through GetDexFile().
       Added GetPositionInSIgnature() for SignatureNodes.
sea.cc: Cleanup of debug output.
visitor.h: Removed dependence on LLVM (now only in code_gen.*).
           Corrected minor typo in comment.
frontend.cc: Renamed access_flags for clarity.

Change-Id: I211d2e9ff1e0c4f910de73a52a5ac2c50e4ca7df

10 files changed, 369 insertions, 42 deletions

diff --git a/compiler/Android.mk b/compiler/Android.mk
index df77853abf..86f521369a 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -96,7 +96,8 @@ LIBART_COMPILER_SRC_FILES += \
 	sea_ir/frontend.cc \
 	sea_ir/instruction_tools.cc \
 	sea_ir/sea.cc \
-	sea_ir/code_gen.cc
+	sea_ir/code_gen.cc \
+	sea_ir/types/type_inference.cc
 endif
 
 LIBART_COMPILER_CFLAGS :=
diff --git a/compiler/sea_ir/code_gen.cc b/compiler/sea_ir/code_gen.cc
index a513907b38..0ef21b4800 100644
--- a/compiler/sea_ir/code_gen.cc
+++ b/compiler/sea_ir/code_gen.cc
@@ -123,14 +123,14 @@ void CodeGenVisitor::Visit(ConstInstructionNode* instruction) {
 void CodeGenVisitor::Visit(ReturnInstructionNode* instruction) {
   std::string instr = instruction->GetInstruction()->DumpString(NULL);
   std::cout << "2.Instruction: " << instr << std::endl;
-  DCHECK_GT(instruction->GetSSAUses().size(), 0u);
-  llvm::Value* return_value = llvm_data_->GetValue(instruction->GetSSAUses().at(0));
+  DCHECK_GT(instruction->GetSSAProducers().size(), 0u);
+  llvm::Value* return_value = llvm_data_->GetValue(instruction->GetSSAProducers().at(0));
   llvm_data_->builder_.CreateRet(return_value);
 }
 void CodeGenVisitor::Visit(IfNeInstructionNode* instruction) {
   std::string instr = instruction->GetInstruction()->DumpString(NULL);
   std::cout << "3.Instruction: " << instr << std::endl;
-  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers();
   DCHECK_GT(ssa_uses.size(), 1u);
   InstructionNode* use_l = ssa_uses.at(0);
   llvm::Value* left = llvm_data_->GetValue(use_l);
@@ -171,7 +171,7 @@ void CodeGenVisitor::Visit(MoveResultInstructionNode* instruction) {
   // since their purpose of minimizing the number of opcodes in dex is
   // not relevant for the IR. (Will need to have different
   // instruction subclasses for functions and procedures.)
-  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers();
   InstructionNode* use_l = ssa_uses.at(0);
   llvm::Value* left = llvm_data_->GetValue(use_l);
   llvm::Value* right = llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, 0));
@@ -187,7 +187,7 @@ void CodeGenVisitor::Visit(InvokeStaticInstructionNode* invoke) {
   // TODO: Add proper checking of the matching between formal and actual signature.
   DCHECK(NULL != callee);
   std::vector<llvm::Value*> parameter_values;
-  std::vector<InstructionNode*> parameter_sources = invoke->GetSSAUses();
+  std::vector<InstructionNode*> parameter_sources = invoke->GetSSAProducers();
   for (std::vector<InstructionNode*>::const_iterator cit = parameter_sources.begin();
       cit != parameter_sources.end(); ++cit) {
     llvm::Value* parameter_value = llvm_data_->GetValue((*cit));
@@ -201,7 +201,7 @@ void CodeGenVisitor::Visit(InvokeStaticInstructionNode* invoke) {
 void CodeGenVisitor::Visit(AddIntInstructionNode* instruction) {
   std::string instr = instruction->GetInstruction()->DumpString(NULL);
   std::cout << "7.Instruction: " << instr << std::endl;
-  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers();
   DCHECK_GT(ssa_uses.size(), 1u);
   InstructionNode* use_l = ssa_uses.at(0);
   InstructionNode* use_r = ssa_uses.at(1);
@@ -221,7 +221,7 @@ void CodeGenVisitor::Visit(GotoInstructionNode* instruction) {
 void CodeGenVisitor::Visit(IfEqzInstructionNode* instruction) {
   std::string instr = instruction->GetInstruction()->DumpString(NULL);
   std::cout << "9. Instruction: " << instr << "; Id: " <<instruction << std::endl;
-  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+  std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers();
   DCHECK_GT(ssa_uses.size(), 0u);
   InstructionNode* use_l = ssa_uses.at(0);
   llvm::Value* left = llvm_data_->GetValue(use_l);
diff --git a/compiler/sea_ir/code_gen.h b/compiler/sea_ir/code_gen.h
index aba8d5c7f8..f656453559 100644
--- a/compiler/sea_ir/code_gen.h
+++ b/compiler/sea_ir/code_gen.h
@@ -17,6 +17,7 @@
 #ifndef ART_COMPILER_SEA_IR_CODE_GEN_H_
 #define ART_COMPILER_SEA_IR_CODE_GEN_H_
 
+#include "llvm/Analysis/Verifier.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
diff --git a/compiler/sea_ir/frontend.cc b/compiler/sea_ir/frontend.cc
index 5843388c42..cc49ea58f2 100644
--- a/compiler/sea_ir/frontend.cc
+++ b/compiler/sea_ir/frontend.cc
@@ -30,7 +30,7 @@ namespace art {
 static CompiledMethod* CompileMethodWithSeaIr(CompilerDriver& compiler,
                                      const CompilerBackend compiler_backend,
                                      const DexFile::CodeItem* code_item,
-                                     uint32_t access_flags, InvokeType invoke_type,
+                                     uint32_t method_access_flags, InvokeType invoke_type,
                                      uint32_t class_def_idx, uint32_t method_idx,
                                      jobject class_loader, const DexFile& dex_file
 #if defined(ART_USE_PORTABLE_COMPILER)
@@ -41,7 +41,7 @@ static CompiledMethod* CompileMethodWithSeaIr(CompilerDriver& compiler,
   //       and silencing the cpplint.py warning, I just corrected the formatting.
   VLOG(compiler) << "Compiling " << PrettyMethod(method_idx, dex_file) << "...";
   sea_ir::SeaGraph* sg = sea_ir::SeaGraph::GetCurrentGraph(dex_file);
-  sg->CompileMethod(code_item, class_def_idx, method_idx, dex_file);
+  sg->CompileMethod(code_item, class_def_idx, method_idx, method_access_flags, dex_file);
   sg->DumpSea("/tmp/temp.dot");
   CHECK(0 && "No SEA compiled function exists yet.");
   return NULL;
@@ -50,14 +50,14 @@ static CompiledMethod* CompileMethodWithSeaIr(CompilerDriver& compiler,
 CompiledMethod* SeaIrCompileOneMethod(CompilerDriver& compiler,
                                  const CompilerBackend backend,
                                  const DexFile::CodeItem* code_item,
-                                 uint32_t access_flags,
+                                 uint32_t method_access_flags,
                                  InvokeType invoke_type,
                                  uint32_t class_def_idx,
                                  uint32_t method_idx,
                                  jobject class_loader,
                                  const DexFile& dex_file,
                                  llvm::LlvmCompilationUnit* llvm_compilation_unit) {
-  return CompileMethodWithSeaIr(compiler, backend, code_item, access_flags, invoke_type,
+  return CompileMethodWithSeaIr(compiler, backend, code_item, method_access_flags, invoke_type,
       class_def_idx, method_idx, class_loader, dex_file
 #if defined(ART_USE_PORTABLE_COMPILER)
                        , llvm_compilation_unit
@@ -68,13 +68,13 @@ CompiledMethod* SeaIrCompileOneMethod(CompilerDriver& compiler,
 extern "C" art::CompiledMethod*
     SeaIrCompileMethod(art::CompilerDriver& compiler,
                           const art::DexFile::CodeItem* code_item,
-                          uint32_t access_flags, art::InvokeType invoke_type,
+                          uint32_t method_access_flags, art::InvokeType invoke_type,
                           uint32_t class_def_idx, uint32_t method_idx, jobject class_loader,
                           const art::DexFile& dex_file) {
   // TODO: Check method fingerprint here to determine appropriate backend type.
   //       Until then, use build default
   art::CompilerBackend backend = compiler.GetCompilerBackend();
-  return art::SeaIrCompileOneMethod(compiler, backend, code_item, access_flags, invoke_type,
+  return art::SeaIrCompileOneMethod(compiler, backend, code_item, method_access_flags, invoke_type,
                                class_def_idx, method_idx, class_loader, dex_file,
                                NULL /* use thread llvm_info */);
 }
diff --git a/compiler/sea_ir/instruction_nodes.h b/compiler/sea_ir/instruction_nodes.h
index 6f9bdddf77..1b81e9add3 100644
--- a/compiler/sea_ir/instruction_nodes.h
+++ b/compiler/sea_ir/instruction_nodes.h
@@ -61,7 +61,7 @@ class InstructionNode: public SeaNode {
   }
   // Returns the ordered set of Instructions that define the input operands of this instruction.
   // Precondition: SeaGraph.ConvertToSSA().
-  std::vector<InstructionNode*> GetSSAUses() {
+  std::vector<InstructionNode*> GetSSAProducers() {
     std::vector<int> uses = GetUses();
     std::vector<InstructionNode*> ssa_uses;
     for (std::vector<int>::const_iterator cit = uses.begin(); cit != uses.end(); cit++) {
@@ -70,6 +70,10 @@ class InstructionNode: public SeaNode {
     return ssa_uses;
   }
 
+  std::vector<InstructionNode*> GetSSAConsumers() {
+    return used_in_;
+  }
+
   virtual void AddSSAUse(InstructionNode* use) {
     used_in_.push_back(use);
   }
diff --git a/compiler/sea_ir/sea.cc b/compiler/sea_ir/sea.cc
index 99b21f8771..585b2aa83c 100644
--- a/compiler/sea_ir/sea.cc
+++ b/compiler/sea_ir/sea.cc
@@ -18,6 +18,7 @@
 #include "instruction_tools.h"
 #include "sea.h"
 #include "code_gen.h"
+#include "types/type_inference.h"
 
 #define MAX_REACHING_DEF_ITERERATIONS (10)
 // TODO: When development is done, this define should not
@@ -191,10 +192,12 @@ void SeaGraph::ComputeReachingDefs() {
 
 
 void SeaGraph::BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
-    const art::DexFile& dex_file, uint32_t class_def_idx, uint32_t method_idx) {
+    const art::DexFile& dex_file, uint32_t class_def_idx,
+    uint32_t method_idx, uint32_t method_access_flags) {
+  code_item_ = code_item;
   class_def_idx_ = class_def_idx;
   method_idx_ = method_idx;
-
+  method_access_flags_ = method_access_flags;
   const uint16_t* code = code_item->insns_;
   const size_t size_in_code_units = code_item->insns_size_in_code_units_;
   // This maps target instruction pointers to their corresponding region objects.
@@ -225,8 +228,9 @@ void SeaGraph::BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
   // Insert one SignatureNode per function argument,
   // to serve as placeholder definitions in dataflow analysis.
   for (unsigned int crt_offset = 0; crt_offset < code_item->ins_size_; crt_offset++) {
+    int position = crt_offset;  // TODO: Is this the correct offset in the signature?
     SignatureNode* parameter_def_node =
-        new sea_ir::SignatureNode(code_item->registers_size_ - 1 - crt_offset);
+        new sea_ir::SignatureNode(code_item->registers_size_ - 1 - crt_offset, position);
     AddParameterNode(parameter_def_node);
     r->AddChild(parameter_def_node);
   }
@@ -260,12 +264,7 @@ void SeaGraph::BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
         }
         r = nextRegion;
       }
-      bool definesRegister = (0 != InstructionTools::instruction_attributes_[inst->Opcode()]
-          && (1 << kDA));
-      LOG(INFO)<< inst->GetDexPc(code) << "*** " << inst->DumpString(&dex_file)
-      << " region:" <<r->StringId() << "Definition?" << definesRegister << std::endl;
-      r->AddChild(node);
-      }
+    }
     i += inst->SizeInCodeUnits();
   }
 }
@@ -417,10 +416,10 @@ void SeaGraph::GenerateLLVM() {
   code_gen_postpass_visitor.Write(std::string("my_file.llvm"));
 }
 
-void SeaGraph::CompileMethod(const art::DexFile::CodeItem* code_item,
-  uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file) {
+void SeaGraph::CompileMethod(const art::DexFile::CodeItem* code_item, uint32_t class_def_idx,
+    uint32_t method_idx, uint32_t method_access_flags, const art::DexFile& dex_file) {
   // Two passes: Builds the intermediate structure (non-SSA) of the sea-ir for the function.
-  BuildMethodSeaGraph(code_item, dex_file, class_def_idx, method_idx);
+  BuildMethodSeaGraph(code_item, dex_file, class_def_idx, method_idx, method_access_flags);
   // Pass: Compute reverse post-order of regions.
   ComputeRPO();
   // Multiple passes: compute immediate dominators.
@@ -433,6 +432,9 @@ void SeaGraph::CompileMethod(const art::DexFile::CodeItem* code_item,
   ComputeDominanceFrontier();
   // Two Passes: Phi node insertion.
   ConvertToSSA();
+  // Pass: type inference
+  TypeInference ti = TypeInference();
+  ti.ComputeTypes(this);
   // Pass: Generate LLVM IR.
   GenerateLLVM();
 }
diff --git a/compiler/sea_ir/sea.h b/compiler/sea_ir/sea.h
index 5cb84240ae..efdbb3b135 100644
--- a/compiler/sea_ir/sea.h
+++ b/compiler/sea_ir/sea.h
@@ -57,8 +57,10 @@ class SignatureNode;
 // can return from the GetSSAUses() calls, instead of having missing SSA edges.
 class SignatureNode: public InstructionNode {
  public:
-  explicit SignatureNode(unsigned int parameter_register):InstructionNode(NULL),
-    parameter_register_(parameter_register) { }
+  // Creates a new signature node representing the initial definition of the
+  // register @parameter_register which is the @position-th argument to the method.
+  explicit SignatureNode(unsigned int parameter_register, unsigned int position):
+    InstructionNode(NULL), parameter_register_(parameter_register), position_(position) { }
 
   void ToDot(std::string& result, const art::DexFile& dex_file) const {
     result += StringId() +" [label=\"signature:";
@@ -71,6 +73,10 @@ class SignatureNode: public InstructionNode {
     return parameter_register_;
   }
 
+  unsigned int GetPositionInSignature() {
+    return position_;
+  }
+
   std::vector<int> GetUses() {
     return std::vector<int>();
   }
@@ -82,6 +88,7 @@ class SignatureNode: public InstructionNode {
 
  private:
   unsigned int parameter_register_;
+  unsigned int position_;  // The position of this parameter node is in the function parameter list.
 };
 
 class PhiInstructionNode: public InstructionNode {
@@ -259,8 +266,8 @@ class SeaGraph: IVisitable {
  public:
   static SeaGraph* GetCurrentGraph(const art::DexFile&);
 
-  void CompileMethod(const art::DexFile::CodeItem* code_item,
-      uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file);
+  void CompileMethod(const art::DexFile::CodeItem* code_item, uint32_t class_def_idx,
+      uint32_t method_idx, uint32_t method_access_flags, const art::DexFile& dex_file);
   // Returns all regions corresponding to this SeaGraph.
   std::vector<Region*>* GetRegions() {
     return &regions_;
@@ -275,12 +282,19 @@ class SeaGraph: IVisitable {
   std::vector<SignatureNode*>* GetParameterNodes() {
     return &parameters_;
   }
+
+  const art::DexFile* GetDexFile() const {
+    return &dex_file_;
+  }
+
   uint32_t class_def_idx_;
   uint32_t method_idx_;
+  uint32_t method_access_flags_;
 
  private:
   explicit SeaGraph(const art::DexFile& df):
-    class_def_idx_(0), method_idx_(0), regions_(), parameters_(), dex_file_(df) {
+    class_def_idx_(0), method_idx_(0),  method_access_flags_(), regions_(),
+    parameters_(), dex_file_(df), code_item_(NULL) {
   }
   // Registers @childReg as a region belonging to the SeaGraph instance.
   void AddRegion(Region* childReg);
@@ -295,7 +309,8 @@ class SeaGraph: IVisitable {
   // Builds the non-SSA sea-ir representation of the function @code_item from @dex_file
   // with class id @class_def_idx and method id @method_idx.
   void BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
-      const art::DexFile& dex_file, uint32_t class_def_idx, uint32_t method_idx);
+      const art::DexFile& dex_file, uint32_t class_def_idx,
+      uint32_t method_idx, uint32_t method_access_flags);
   // Computes immediate dominators for each region.
   // Precondition: ComputeMethodSeaGraph()
   void ComputeIDominators();
@@ -336,6 +351,7 @@ class SeaGraph: IVisitable {
   std::vector<Region*> regions_;
   std::vector<SignatureNode*> parameters_;
   const art::DexFile& dex_file_;
+  const art::DexFile::CodeItem* code_item_;
 };
 }  // namespace sea_ir
 #endif  // ART_COMPILER_SEA_IR_SEA_H_
diff --git a/compiler/sea_ir/types/type_inference.cc b/compiler/sea_ir/types/type_inference.cc
new file mode 100644
index 0000000000..ad81310468
--- /dev/null
+++ b/compiler/sea_ir/types/type_inference.cc
@@ -0,0 +1,159 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "sea_ir/types/type_inference.h"
+
+namespace sea_ir {
+
+bool TypeInference::IsPrimitiveDescriptor(char descriptor) {
+  switch (descriptor) {
+  case 'I':
+  case 'C':
+  case 'S':
+  case 'B':
+  case 'Z':
+  case 'F':
+  case 'D':
+  case 'J':
+    return true;
+  default:
+    return false;
+  }
+}
+
+FunctionTypeInfo::FunctionTypeInfo(const SeaGraph* graph, art::verifier::RegTypeCache* types)
+    : dex_file_(graph->GetDexFile()), dex_method_idx_(graph->method_idx_), type_cache_(types),
+    method_access_flags_(graph->method_access_flags_) {
+  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));
+}
+
+std::vector<const Type*> FunctionTypeInfo::GetDeclaredArgumentTypes()
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  std::vector<const Type*> argument_types;
+  // Include the "this" pointer.
+  size_t cur_arg = 0;
+  if (!IsStatic()) {
+    // If this is a constructor for a class other than java.lang.Object, mark the first ("this")
+    // argument as uninitialized. This restricts field access until the superclass constructor is
+    // called.
+    const art::verifier::RegType& declaring_class = GetDeclaringClass();
+    if (IsConstructor() && !declaring_class.IsJavaLangObject()) {
+      argument_types.push_back(&(type_cache_->UninitializedThisArgument(declaring_class)));
+    } else {
+      argument_types.push_back(&declaring_class);
+    }
+    cur_arg++;
+  }
+
+  const art::DexFile::ProtoId& proto_id =
+      dex_file_->GetMethodPrototype(dex_file_->GetMethodId(dex_method_idx_));
+  art::DexFileParameterIterator iterator(*dex_file_, proto_id);
+
+  for (; iterator.HasNext(); iterator.Next()) {
+    const char* descriptor = iterator.GetDescriptor();
+    if (descriptor == NULL) {
+      LOG(FATAL) << "Error: Encountered null type descriptor for function argument.";
+    }
+    switch (descriptor[0]) {
+      case 'L':
+      case '[':
+        // We assume that reference arguments are initialized. The only way it could be otherwise
+        // (assuming the caller was verified) is if the current method is <init>, but in that case
+        // it's effectively considered initialized the instant we reach here (in the sense that we
+        // can return without doing anything or call virtual methods).
+        {
+          const Type& reg_type = type_cache_->FromDescriptor(NULL, descriptor, false);
+          argument_types.push_back(&reg_type);
+        }
+        break;
+      case 'Z':
+        argument_types.push_back(&type_cache_->Boolean());
+        break;
+      case 'C':
+        argument_types.push_back(&type_cache_->Char());
+        break;
+      case 'B':
+        argument_types.push_back(&type_cache_->Byte());
+        break;
+      case 'I':
+        argument_types.push_back(&type_cache_->Integer());
+        break;
+      case 'S':
+        argument_types.push_back(&type_cache_->Short());
+        break;
+      case 'F':
+        argument_types.push_back(&type_cache_->Float());
+        break;
+      case 'J':
+      case 'D': {
+        // TODO: Figure out strategy for two-register operands (double, long)
+        LOG(FATAL) << "Error: Type inference for 64-bit variables has not been implemented.";
+        break;
+      }
+      default:
+        LOG(FATAL) << "Error: Unexpected signature encountered during type inference.";
+    }
+    cur_arg++;
+  }
+  return argument_types;
+}
+
+// TODO: Lock is only used for dumping types (during development). Remove this for performance.
+void TypeInference::ComputeTypes(SeaGraph* graph) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  std::vector<Region*>* regions = graph->GetRegions();
+  std::list<InstructionNode*> worklist;
+  // Fill the work-list with all instructions.
+  for (std::vector<Region*>::const_iterator region_it = regions->begin();
+      region_it != regions->end(); region_it++) {
+    std::vector<PhiInstructionNode*>* phi_instructions = (*region_it)->GetPhiNodes();
+    std::copy(phi_instructions->begin(), phi_instructions->end(), std::back_inserter(worklist));
+    std::vector<InstructionNode*>* instructions = (*region_it)->GetInstructions();
+    std::copy(instructions->begin(), instructions->end(), std::back_inserter(worklist));
+  }
+  TypeInferenceVisitor tiv(graph, 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,
+  //       which simplifies the implementation; not 100% sure other STL implementations
+  //       maintain this invariant, but they should.
+  //       [1] http://www.sgi.com/tech/stl/List.html
+  // TODO: Making this conditional (as in sparse conditional constant propagation) would be good.
+  for (std::list<InstructionNode*>::const_iterator instruction_it = worklist.begin();
+        instruction_it != worklist.end(); instruction_it++) {
+    std::cout << "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* 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) {
+      std::cout << " New type:" << new_type->IsIntegralTypes() << std::endl;
+      std::cout << " Descriptor:" << new_type->Dump() << std::endl;
+      type_map_[(*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();
+          consumer != consumers.end(); consumer++) {
+        worklist.push_back(*consumer);
+      }
+    }
+  }
+}
+
+}   // namespace sea_ir
diff --git a/compiler/sea_ir/types/type_inference.h b/compiler/sea_ir/types/type_inference.h
new file mode 100644
index 0000000000..1c0d42ec29
--- /dev/null
+++ b/compiler/sea_ir/types/type_inference.h
@@ -0,0 +1,152 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_SEA_IR_TYPES_TYPE_INFERENCE_H_
+#define ART_COMPILER_SEA_IR_TYPES_TYPE_INFERENCE_H_
+
+#include "sea_ir/sea.h"
+#include "dex_file-inl.h"
+#include "verifier/reg_type.h"
+#include "verifier/reg_type_cache.h"
+#include "verifier/reg_type_cache.h"
+namespace sea_ir {
+
+typedef art::verifier::RegType Type;
+
+
+// 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.
+class TypeInference {
+ public:
+  TypeInference() {
+    type_cache_ = new art::verifier::RegTypeCache(false);
+  }
+
+  // Computes the types for the method with SEA IR representation provided by @graph.
+  void ComputeTypes(SeaGraph* graph);
+
+  // 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_;
+};
+
+// Stores information about the exact type of  a function.
+class FunctionTypeInfo {
+ public:
+  // @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);
+  // Returns the ordered vector of types corresponding to the function arguments.
+  std::vector<const Type*> GetDeclaredArgumentTypes();
+  // Returns the type corresponding to the class that declared the method.
+  const Type& GetDeclaringClass() {
+    return *declaring_class_;
+  }
+
+  bool IsConstructor() const {
+    return (method_access_flags_ & kAccConstructor) != 0;
+  }
+
+  bool IsStatic() const {
+    return (method_access_flags_ & kAccStatic) != 0;
+  }
+
+ protected:
+  const Type* declaring_class_;
+  const art::DexFile* dex_file_;
+  const uint32_t dex_method_idx_;
+  art::verifier::RegTypeCache* type_cache_;
+  const uint32_t method_access_flags_;  // Method's access flags.
+};
+
+// The TypeInferenceVisitor visits each instruction and computes its type taking into account
+//   the current type of the operands. The type is stored in the visitor.
+// We may be better off by using a separate visitor type hierarchy that has return values
+//   or that passes data as parameters, than to use fields to store information that should
+//   in fact be returned after visiting each element. Ideally, I would prefer to use templates
+//   to specify the returned value type, but I am not aware of a possible implementation
+//   that does not horribly duplicate the visitor infrastructure code (version 1: no return value,
+//   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_() { }
+  void Initialize(SeaGraph* graph) { }
+  // There are no type related actions to be performed on these classes.
+  void Visit(SeaGraph* graph) { }
+  void Visit(Region* region) { }
+
+  void Visit(PhiInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(SignatureNode* parameter) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    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();
+    std::cout << "Pos:" << parameter->GetPositionInSignature() << "/" << arguments.size() <<std::endl;
+    DCHECK_LT(parameter->GetPositionInSignature(), arguments.size())
+      << "Signature node position not present in signature.";
+    crt_type_.push_back(arguments.at(parameter->GetPositionInSignature()));
+  }
+  void Visit(InstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(ConstInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(ReturnInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(IfNeInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(MoveResultInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(InvokeStaticInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(AddIntInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(GotoInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+  void Visit(IfEqzInstructionNode* instruction) {
+    std::cout << "[TI] Visiting node:" << instruction->Id() << std::endl;
+  }
+
+  const Type* GetType() const {
+    // TODO: Currently multiple defined types are not supported.
+    if (crt_type_.size()>0) return crt_type_.at(0);
+    return NULL;
+  }
+
+ protected:
+  const SeaGraph* graph_;
+  art::verifier::RegTypeCache* type_cache_;
+  std::vector<const Type*> crt_type_;             // Stored temporarily between two calls to Visit.
+};
+
+}  // namespace sea_ir
+
+#endif  // ART_COMPILER_SEA_IR_TYPES_TYPE_INFERENCE_H_
diff --git a/compiler/sea_ir/visitor.h b/compiler/sea_ir/visitor.h
index a4fec7b8a9..f4cecd8519 100644
--- a/compiler/sea_ir/visitor.h
+++ b/compiler/sea_ir/visitor.h
@@ -17,14 +17,6 @@
 #ifndef ART_COMPILER_SEA_IR_VISITOR_H_
 #define ART_COMPILER_SEA_IR_VISITOR_H_
 
-#include "llvm/IR/IRBuilder.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/Module.h"
-#include "llvm/Analysis/Verifier.h"
-// TODO: Separating the root visitor from the code_gen visitor
-// would allow me to not include llvm headers here.
-
-
 namespace sea_ir {
 
 class SeaGraph;
@@ -66,7 +58,7 @@ class IRVisitor {
   virtual void Visit(GotoInstructionNode* instruction) = 0;
   virtual void Visit(IfEqzInstructionNode* instruction) = 0;
 
-  // Note: This favor of visitor separates the traversal functions from the actual visiting part
+  // Note: This flavor of visitor separates the traversal functions from the actual visiting part
   //       so that the Visitor subclasses don't duplicate code and can't get the traversal wrong.
   //       The disadvantage is the increased number of functions (and calls).
   virtual void Traverse(SeaGraph* graph);