compiler/sea_ir/sea.cc

/*
 * 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.h"

#include "file_output_stream.h"

#define MAX_REACHING_DEF_ITERERATIONS (10)

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++) {
    (*cit)->ToDot(result);
  }
  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::AddEdge(Region* src, Region* dst) const {
  src->AddSuccessor(dst);
  dst->AddPredecessor(src);
}

void SeaGraph::ComputeDownExposedDefs() {
  for (std::vector<Region*>::iterator region_it = regions_.begin();
        region_it != regions_.end(); region_it++) {
      (*region_it)->ComputeDownExposedDefs();
    }
}

void SeaGraph::ComputeReachingDefs() {
  // Iterate until the reaching definitions set doesn't change anymore.
  // (See Cooper & Torczon, "Engineering a Compiler", second edition, page 487)
  bool changed = true;
  int iteration = 0;
  while (changed && (iteration < MAX_REACHING_DEF_ITERERATIONS)) {
    iteration++;
    changed = false;
    // TODO: optimize the ordering if this becomes performance bottleneck.
    for (std::vector<Region*>::iterator regions_it = regions_.begin();
        regions_it != regions_.end();
        regions_it++) {
      changed |= (*regions_it)->UpdateReachingDefs();
    }
  }
  DCHECK(!changed) << "Reaching definitions computation did not reach a fixed point.";
}


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: Find the start instruction of basic blocks
  //         by locating targets and flow-though instructions 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->CanFlowThrough() &&
          (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: Assign instructions to region nodes and
  //         assign branches their control flow successors.
  i = 0;
  r = GetNewRegion();
  sea_ir::InstructionNode* last_node = NULL;
  sea_ir::InstructionNode* 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::InstructionNode(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());
      AddEdge(r, it->second); // Add edge to branch target.
    }

    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()->CanFlowThrough()) {
        AddEdge(r, it->second); // Add flow-through edge.
      }
      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();
  }

  // Pass: compute downward-exposed definitions.
  ComputeDownExposedDefs();

  // Multiple Passes: Compute reaching definitions (iterative fixed-point algorithm)
  ComputeReachingDefs();
}

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::InstructionNode* instruction) {
  DCHECK(instruction) << "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;
}

void InstructionNode::ToDot(std::string& result) const {
  result += "// Instruction: \n" + StringId() +
      " [label=\"" + instruction_->DumpString(NULL) + "\"";
  if (de_def_) {
    result += "style=bold";
  }
  result += "];\n";
}

int InstructionNode::GetResultRegister() const {
  if (!InstructionTools::IsDefinition(instruction_)) {
    return NO_REGISTER;
  }
  return instruction_->VRegA();
}

void InstructionNode::MarkAsDEDef() {
  de_def_ = true;
}

void Region::ToDot(std::string& result) const {
  result += "\n// Region: \n" + StringId() + " [label=\"region " + StringId() + "\"];";
  // Save instruction nodes that belong to this region.
  for (std::vector<InstructionNode*>::const_iterator cit = instructions_.begin();
      cit != instructions_.end(); cit++) {
    (*cit)->ToDot(result);
    result += StringId() + " -> " + (*cit)->StringId() + ";\n";
  }

  for (std::vector<Region*>::const_iterator cit = successors_.begin(); cit != successors_.end();
      cit++) {
    DCHECK(NULL != *cit) << "Null successor found for SeaNode" << GetLastChild()->StringId() << ".";
    result += GetLastChild()->StringId() + " -> " + (*cit)->StringId() + ";\n\n";
  }

  // Save reaching definitions.
  for (std::map<int, std::set<sea_ir::InstructionNode*>* >::const_iterator cit =
      reaching_defs_.begin();
      cit != reaching_defs_.end(); cit++) {
    for (std::set<sea_ir::InstructionNode*>::const_iterator
        reaching_set_it = (*cit).second->begin();
        reaching_set_it != (*cit).second->end();
        reaching_set_it++) {
      result += (*reaching_set_it)->StringId() +
         " -> " + StringId() +
         " [style=dotted]; // Reaching def.\n";
    }
  }

  result += "// End Region.\n";
}


void Region::ComputeDownExposedDefs() {
  for (std::vector<InstructionNode*>::const_iterator inst_it = instructions_.begin();
      inst_it != instructions_.end(); inst_it++) {
    int reg_no = (*inst_it)->GetResultRegister();
    std::map<int, InstructionNode*>::iterator res = de_defs_.find(reg_no);
    if ((reg_no != NO_REGISTER) && (res == de_defs_.end())) {
      de_defs_.insert(std::pair<int, InstructionNode*>(reg_no, *inst_it));
    } else {
      res->second = *inst_it;
    }
  }

  for (std::map<int, sea_ir::InstructionNode*>::const_iterator cit = de_defs_.begin();
      cit != de_defs_.end(); cit++) {
    (*cit).second->MarkAsDEDef();
  }
}


const std::map<int, sea_ir::InstructionNode*>* Region::GetDownExposedDefs() const {
  return &de_defs_;
}

std::map<int, std::set<sea_ir::InstructionNode*>* >* Region::GetReachingDefs() {
  return &reaching_defs_;
}

bool Region::UpdateReachingDefs() {
  std::map<int, std::set<sea_ir::InstructionNode*>* > new_reaching;
  for (std::vector<Region*>::const_iterator pred_it = predecessors_.begin();
      pred_it != predecessors_.end(); pred_it++) {
    // The reaching_defs variable will contain reaching defs __for current predecessor only__
    std::map<int, std::set<sea_ir::InstructionNode*>* > reaching_defs;
    std::map<int, std::set<sea_ir::InstructionNode*>* >* pred_reaching = (*pred_it)->GetReachingDefs();
    const std::map<int, InstructionNode*>* de_defs = (*pred_it)->GetDownExposedDefs();

    // The definitions from the reaching set of the predecessor
    // may be shadowed by downward exposed definitions from the predecessor,
    // otherwise the defs from the reaching set are still good.
    for (std::map<int, InstructionNode*>::const_iterator de_def = de_defs->begin();
        de_def != de_defs->end(); de_def++) {
      std::set<InstructionNode*>* solo_def;
      solo_def = new std::set<InstructionNode*>();
      solo_def->insert(de_def->second);
      reaching_defs.insert(
          std::pair<int const, std::set<InstructionNode*>*>(de_def->first, solo_def));
    }
    LOG(INFO) << "Adding to " <<StringId() << "reaching set of " << (*pred_it)->StringId();
    reaching_defs.insert(pred_reaching->begin(), pred_reaching->end());

    // Now we combine the reaching map coming from the current predecessor (reaching_defs)
    // with the accumulated set from all predecessors so far (from new_reaching).
    std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it = reaching_defs.begin();
    for (; reaching_it != reaching_defs.end(); reaching_it++) {
      std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator crt_entry =
          new_reaching.find(reaching_it->first);
      if (new_reaching.end() != crt_entry) {
        crt_entry->second->insert(reaching_it->second->begin(), reaching_it->second->end());
      } else {
        new_reaching.insert(
            std::pair<int, std::set<sea_ir::InstructionNode*>*>(
                reaching_it->first,
                reaching_it->second) );
      }
    }
  }
  bool changed = false;
  // Because the sets are monotonically increasing,
  // we can compare sizes instead of using set comparison.
  // TODO: Find formal proof.
  int old_size = 0;
  if (-1 == reaching_defs_size_) {
    std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it = reaching_defs_.begin();
    for (; reaching_it != reaching_defs_.end(); reaching_it++) {
      old_size += (*reaching_it).second->size();
    }
  } else {
    old_size = reaching_defs_size_;
  }
  int new_size = 0;
  std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it = new_reaching.begin();
  for (; reaching_it != new_reaching.end(); reaching_it++) {
    new_size += (*reaching_it).second->size();
  }
  if (old_size != new_size) {
    changed = true;
  }
  if (changed) {
    reaching_defs_ = new_reaching;
    reaching_defs_size_ = new_size;
  }
  return changed;
}

void SeaNode::AddSuccessor(Region* successor) {
  DCHECK(successor) << "Tried to add NULL successor to SEA node.";
  successors_.push_back(successor);
  return;
}

void SeaNode::AddPredecessor(Region* predecessor) {
  DCHECK(predecessor) << "Tried to add NULL predecessor to SEA node.";
  predecessors_.push_back(predecessor);
}

} // end namespace sea_ir