Added support for SEA IR.

- Modified makefile to take the existance of SEA_IR_ART
  file to mean "switch to sea ir mode".
- Switching SEA IR mode on leads to the new compiler being
  fed the fibonacci methods only, if they are used as input.
- Added partial support for the control flow subgraph of
  the SEA IR (instruction nodes and region nodes for
  conditional and unconditional branches).

Change-Id: I29020b8e2df5a00fde75715c3683cc25038589f4

Conflicts:
	src/compiler/driver/compiler_driver.cc

7 files changed, 387 insertions, 2 deletions

diff --git a/src/compiler/dex/frontend.cc b/src/compiler/dex/frontend.cc
index e015645584..c528d8680c 100644
--- a/src/compiler/dex/frontend.cc
+++ b/src/compiler/dex/frontend.cc
@@ -29,6 +29,8 @@
 #include "backend.h"
 #include "base/logging.h"
 
+
+
 namespace {
 #if !defined(ART_USE_PORTABLE_COMPILER)
   pthread_once_t llvm_multi_init = PTHREAD_ONCE_INIT;
@@ -104,6 +106,7 @@ static uint32_t kCompilerDebugFlags = 0 |     // Enable debug/testing modes
   //(1 << kDebugShowSummaryMemoryUsage) |
   0;
 
+
 static CompiledMethod* CompileMethod(CompilerDriver& compiler,
                                      const CompilerBackend compiler_backend,
                                      const DexFile::CodeItem* code_item,
@@ -277,6 +280,8 @@ CompiledMethod* CompileOneMethod(CompilerDriver& compiler,
                        );
 }
 
+
+
 }  // namespace art
 
 extern "C" art::CompiledMethod*
diff --git a/src/compiler/dex/frontend.h b/src/compiler/dex/frontend.h
index dc57a23485..69d7f7728c 100644
--- a/src/compiler/dex/frontend.h
+++ b/src/compiler/dex/frontend.h
@@ -20,6 +20,11 @@
 #include "dex_file.h"
 #include "dex_instruction.h"
 
+
+
+
+
+
 namespace llvm {
   class Module;
   class LLVMContext;
@@ -116,4 +121,6 @@ extern "C" art::CompiledMethod* ArtCompileMethod(art::CompilerDriver& driver,
                                                  jobject class_loader,
                                                  const art::DexFile& dex_file);
 
+
+
 #endif // ART_SRC_COMPILER_DEX_COMPILER_H_
diff --git a/src/compiler/driver/compiler_driver.cc b/src/compiler/driver/compiler_driver.cc
index 4a6eb962e3..122988aa5b 100644
--- a/src/compiler/driver/compiler_driver.cc
+++ b/src/compiler/driver/compiler_driver.cc
@@ -374,6 +374,11 @@ CompilerDriver::CompilerDriver(CompilerBackend compiler_backend, InstructionSet
 
   dex_to_dex_compiler_ = FindFunction<CompilerFn>(compiler_so_name, compiler_library_, "ArtCompileDEX");
 
+  sea_ir_compiler_ = NULL;
+  if (Runtime::Current()->IsSeaIRMode()) {
+    sea_ir_compiler_ = FindFunction<CompilerFn>(compiler_so_name, compiler_library_, "SeaIrCompileMethod");
+  }
+
   init_compiler_context(*this);
 
   if (compiler_backend_ == kPortable) {
@@ -2149,10 +2154,22 @@ void CompilerDriver::CompileMethod(const DexFile::CodeItem* code_item, uint32_t
     // Do compile small methods.
       dont_compile = false;
     }
-
     if (!dont_compile) {
-      compiled_method = (*compiler_)(*this, code_item, access_flags, invoke_type, class_def_idx,
+      bool use_sea = false;
+
+      if (Runtime::Current()->IsSeaIRMode()) {
+        use_sea = true;
+      }
+      if (use_sea) {
+        use_sea = (std::string::npos != PrettyMethod(method_idx, dex_file).find("fibonacci"));
+      }
+      if (!use_sea) {
+        compiled_method = (*compiler_)(*this, code_item, access_flags, invoke_type, class_def_idx,
                                      method_idx, class_loader, dex_file);
+      } else {
+        compiled_method = (*sea_ir_compiler_)(*this, code_item, access_flags, invoke_type, class_def_idx,
+                                             method_idx, class_loader, dex_file);
+      }
       CHECK(compiled_method != NULL) << PrettyMethod(method_idx, dex_file);
     } else if (allow_dex_to_dex_compilation) {
       // TODO: add a mode to disable DEX-to-DEX compilation ?
diff --git a/src/compiler/driver/compiler_driver.h b/src/compiler/driver/compiler_driver.h
index fdd2149f7f..b37b74b042 100644
--- a/src/compiler/driver/compiler_driver.h
+++ b/src/compiler/driver/compiler_driver.h
@@ -404,6 +404,7 @@ class CompilerDriver {
                                         uint32_t class_dex_idx, uint32_t method_idx,
                                         jobject class_loader, const DexFile& dex_file);
   CompilerFn compiler_;
+  CompilerFn sea_ir_compiler_;
 
   CompilerFn dex_to_dex_compiler_;
 
diff --git a/src/compiler/sea_ir/frontend.cc b/src/compiler/sea_ir/frontend.cc
new file mode 100644
index 0000000000..d4e1c7e740
--- /dev/null
+++ b/src/compiler/sea_ir/frontend.cc
@@ -0,0 +1,81 @@
+
+#include <llvm/Support/Threading.h>
+
+#include "compiler/driver/compiler_driver.h"
+
+
+#include "compiler/llvm/llvm_compilation_unit.h"
+#include "compiler/dex/portable/mir_to_gbc.h"
+
+#include "leb128.h"
+#include "mirror/object.h"
+#include "runtime.h"
+#include "base/logging.h"
+
+#ifdef ART_SEA_IR_MODE
+#include "compiler/sea_ir/sea.h"
+#endif
+
+
+
+
+#ifdef ART_SEA_IR_MODE
+#include "compiler/sea_ir/sea.h"
+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 class_def_idx, uint32_t method_idx,
+                                     jobject class_loader, const DexFile& dex_file
+#if defined(ART_USE_PORTABLE_COMPILER)
+                                     , llvm::LlvmCompilationUnit* llvm_compilation_unit
+#endif
+)
+{
+  VLOG(compiler) << "Compiling " << PrettyMethod(method_idx, dex_file) << "...";
+  sea_ir::SeaGraph* sg = sea_ir::SeaGraph::GetCurrentGraph();
+  sg->CompileMethod(code_item, class_def_idx, method_idx, dex_file);
+  sg->DumpSea("/tmp/temp.dot");
+  CHECK(0 && "No SEA compiled function exists yet.");
+  return NULL;
+}
+
+
+CompiledMethod* SeaIrCompileOneMethod(CompilerDriver& compiler,
+                                 const CompilerBackend backend,
+                                 const DexFile::CodeItem* code_item,
+                                 uint32_t 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, class_def_idx,
+                       method_idx, class_loader, dex_file
+#if defined(ART_USE_PORTABLE_COMPILER)
+                       , llvm_compilation_unit
+#endif
+
+                       );
+}
+
+extern "C" art::CompiledMethod*
+    SeaIrCompileMethod(art::CompilerDriver& compiler,
+                          const art::DexFile::CodeItem* code_item,
+                          uint32_t 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,
+                               class_def_idx, method_idx, class_loader, dex_file,
+                               NULL /* use thread llvm_info */);
+}
+#endif
+
+} // end namespace art
diff --git a/src/compiler/sea_ir/sea.cc b/src/compiler/sea_ir/sea.cc
new file mode 100644
index 0000000000..e08558fa2d
--- /dev/null
+++ b/src/compiler/sea_ir/sea.cc
@@ -0,0 +1,172 @@
+/*
+ * 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 "compiler/sea_ir/sea.h"
+#include "file_output_stream.h"
+
+
+
+namespace sea_ir {
+
+
+SeaGraph SeaGraph::graph_;
+int SeaNode::current_max_node_id_ = 0;
+
+SeaGraph* SeaGraph::GetCurrentGraph() {
+  return &sea_ir::SeaGraph::graph_;
+}
+
+void SeaGraph::DumpSea(std::string filename) const {
+  std::string result;
+  result += "digraph seaOfNodes {\n";
+  for(std::vector<Region*>::const_iterator cit = regions_.begin(); cit != regions_.end(); cit++) {
+    result += (*cit)->ToDot();
+  }
+  result += "}\n";
+  art::File* file = art::OS::OpenFile(filename.c_str(), true, true);
+  art::FileOutputStream fos(file);
+  fos.WriteFully(result.c_str(), result.size());
+  LOG(INFO) << "Written SEA string to file...";
+}
+
+void SeaGraph::CompileMethod(const art::DexFile::CodeItem* code_item,
+  uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file) {
+  const uint16_t* code = code_item->insns_;
+  const size_t size_in_code_units = code_item->insns_size_in_code_units_;
+
+  Region* r = NULL;
+  // This maps  target instruction pointers to their corresponding region objects.
+  std::map<const uint16_t*, Region*> target_regions;
+  size_t i = 0;
+
+  // Pass 1: Find the start instruction of basic blocks, as targets and flow-though of branches.
+  while (i < size_in_code_units) {
+    const art::Instruction* inst = art::Instruction::At(&code[i]);
+    if (inst->IsBranch()||inst->IsUnconditional()) {
+      int32_t offset = inst->GetTargetOffset();
+      if (target_regions.end() == target_regions.find(&code[i+offset])) {
+        Region* region = GetNewRegion();
+        target_regions.insert(std::pair<const uint16_t*, Region*>(&code[i+offset], region));
+      }
+      if (inst->IsFlowthrough() &&
+          (target_regions.end() == target_regions.find(&code[i+inst->SizeInCodeUnits()]))) {
+        Region* region = GetNewRegion();
+        target_regions.insert(std::pair<const uint16_t*, Region*>(&code[i+inst->SizeInCodeUnits()], region));
+      }
+    }
+    i += inst->SizeInCodeUnits();
+  }
+
+
+  // Pass 2: Assign instructions to region nodes and
+  //         assign branches their control flow successors.
+  i = 0;
+  r = GetNewRegion();
+  sea_ir::SeaNode* last_node = NULL;
+  sea_ir::SeaNode* node = NULL;
+  while (i < size_in_code_units) {
+    const art::Instruction* inst = art::Instruction::At(&code[i]); //TODO: find workaround for this
+    last_node = node;
+    node = new sea_ir::SeaNode(inst);
+
+    if (inst->IsBranch() || inst->IsUnconditional()) {
+      int32_t offset = inst->GetTargetOffset();
+      std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i+offset]);
+      DCHECK(it != target_regions.end());
+      node->AddSuccessor(it->second);
+    }
+
+    std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i]);
+    if (target_regions.end() != it) {
+      // Get the already created region because this is a branch target.
+      Region* nextRegion = it->second;
+      if (last_node->GetInstruction()->IsBranch() && last_node->GetInstruction()->IsFlowthrough()) {
+        last_node->AddSuccessor(nextRegion);
+
+      }
+      r = nextRegion;
+    }
+
+    LOG(INFO) << inst->GetDexPc(code) << "*** " << inst->DumpString(&dex_file)
+            << " region:" <<r->StringId() << std::endl;
+    r->AddChild(node);
+    i += inst->SizeInCodeUnits();
+  }
+
+}
+
+
+Region* SeaGraph::GetNewRegion() {
+  Region* new_region = new Region();
+  AddRegion(new_region);
+  return new_region;
+}
+
+void SeaGraph::AddRegion(Region* r) {
+  DCHECK(r) << "Tried to add NULL region to SEA graph.";
+  regions_.push_back(r);
+}
+void Region::AddChild(sea_ir::SeaNode* instruction) {
+  DCHECK(inst) << "Tried to add NULL instruction to region node.";
+  instructions_.push_back(instruction);
+}
+
+SeaNode* Region::GetLastChild() const {
+  if (instructions_.size()>0) {
+    return instructions_.back();
+  }
+  return NULL;
+}
+
+std::string SeaNode::ToDot() const {
+  std::string node = "// Instruction: \n" + StringId() +
+      " [label=\"" + instruction_->DumpString(NULL) + "\"];\n";
+
+  for(std::vector<SeaNode*>::const_iterator cit = successors_.begin();
+      cit != successors_.end(); cit++) {
+    DCHECK(NULL != *cit) << "Null successor found for SeaNode" << StringId() << ".";
+    node += StringId() + " -> " + (*cit)->StringId() + ";\n\n";
+  }
+  return node;
+}
+
+std::string SeaNode::StringId() const {
+  std::stringstream ss;
+  ss << id_;
+  return ss.str();
+}
+
+std::string Region::ToDot() const {
+  std::string result = "// Region: \n" +
+      StringId() + " [label=\"region " + StringId() + "\"];";
+
+  for(std::vector<SeaNode*>::const_iterator cit = instructions_.begin();
+      cit != instructions_.end(); cit++) {
+    result += (*cit)->ToDot();
+    result += StringId() + " -> " + (*cit)->StringId() + ";\n";
+  }
+
+  result += "// End Region.\n";
+  return result;
+}
+
+void SeaNode::AddSuccessor(SeaNode* successor) {
+  DCHECK(successor) << "Tried to add NULL successor to SEA node.";
+  successors_.push_back(successor);
+  return;
+}
+
+} // end namespace
diff --git a/src/compiler/sea_ir/sea.h b/src/compiler/sea_ir/sea.h
new file mode 100644
index 0000000000..0ebd4d02d4
--- /dev/null
+++ b/src/compiler/sea_ir/sea.h
@@ -0,0 +1,102 @@
+/*
+ * 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 "dex_file.h"
+#include "dex_instruction.h"
+
+#ifndef SEA_IR_H_
+#define SEA_IR_H_
+
+#include <set>
+#include <map>
+
+namespace sea_ir {
+
+
+class SeaNode {
+ public:
+  explicit SeaNode(const art::Instruction* in):id_(GetNewId()), instruction_(in), successors_() {};
+  explicit SeaNode():id_(GetNewId()), instruction_(NULL) {};
+  void AddSuccessor(SeaNode* successor);
+  const art::Instruction* GetInstruction() {
+    DCHECK(NULL != instruction_);
+    return instruction_;
+  }
+  std::string StringId() const;
+  // Returns a dot language formatted string representing the node and
+  //    (by convention) outgoing edges, so that the composition of theToDot() of all nodes
+  //    builds a complete dot graph (without prolog and epilog though).
+  virtual std::string ToDot() const;
+  virtual ~SeaNode(){};
+
+ protected:
+  // Returns the id of the current block as string
+
+  static int GetNewId() {
+    return current_max_node_id_++;
+  }
+
+
+ private:
+  const int id_;
+  const art::Instruction* const instruction_;
+  std::vector<sea_ir::SeaNode*> successors_;
+  static int current_max_node_id_;
+};
+
+
+
+class Region : public SeaNode {
+ public:
+  explicit Region():SeaNode() {}
+  void AddChild(sea_ir::SeaNode* instruction);
+  SeaNode* GetLastChild() const;
+
+  // Returns a dot language formatted string representing the node and
+  //    (by convention) outgoing edges, so that the composition of theToDot() of all nodes
+  //    builds a complete dot graph (without prolog and epilog though).
+  virtual std::string ToDot() const;
+
+ private:
+  std::vector<sea_ir::SeaNode*> instructions_;
+};
+
+
+
+class SeaGraph {
+ public:
+  static SeaGraph* GetCurrentGraph();
+  void CompileMethod(const art::DexFile::CodeItem* code_item,
+      uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file);
+  // Returns a string representation of the region and its Instruction children
+  void DumpSea(std::string filename) const;
+  /*** Static helper functions follow: ***/
+  static int ParseInstruction(const uint16_t* code_ptr,
+      art::DecodedInstruction* decoded_instruction);
+  static bool IsInstruction(const uint16_t* code_ptr);
+
+ private:
+  // Registers the parameter as a child region of the SeaGraph instance
+  void AddRegion(Region* r);
+  // Returns new region and registers it with the  SeaGraph instance
+  Region* GetNewRegion();
+  static SeaGraph graph_;
+  std::vector<Region*> regions_;
+};
+
+
+} // end namespace sea_ir
+#endif