blob: 99b21f8771350a99a5243693ba2ca2999c64ccd1 [file] [log] [blame]
/*
* 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 "base/stringprintf.h"
#include "file_output_stream.h"
#include "instruction_tools.h"
#include "sea.h"
#include "code_gen.h"
#define MAX_REACHING_DEF_ITERERATIONS (10)
// TODO: When development is done, this define should not
// be needed, it is currently used as a cutoff
// for cases where the iterative fixed point algorithm
// does not reach a fixed point because of a bug.
namespace sea_ir {
int SeaNode::current_max_node_id_ = 0;
void IRVisitor::Traverse(Region* region) {
std::vector<PhiInstructionNode*>* phis = region->GetPhiNodes();
for (std::vector<PhiInstructionNode*>::const_iterator cit = phis->begin();
cit != phis->end(); cit++) {
(*cit)->Accept(this);
}
std::vector<InstructionNode*>* instructions = region->GetInstructions();
for (std::vector<InstructionNode*>::const_iterator cit = instructions->begin();
cit != instructions->end(); cit++) {
(*cit)->Accept(this);
}
}
void IRVisitor::Traverse(SeaGraph* graph) {
for (std::vector<Region*>::const_iterator cit = ordered_regions_.begin();
cit != ordered_regions_.end(); cit++ ) {
(*cit)->Accept(this);
}
}
SeaGraph* SeaGraph::GetCurrentGraph(const art::DexFile& dex_file) {
return new SeaGraph(dex_file);
}
void SeaGraph::DumpSea(std::string filename) const {
LOG(INFO) << "Starting to write SEA string to file.";
std::string result;
result += "digraph seaOfNodes {\ncompound=true\n";
for (std::vector<Region*>::const_iterator cit = regions_.begin(); cit != regions_.end(); cit++) {
(*cit)->ToDot(result, dex_file_);
}
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::ComputeRPO(Region* current_region, int& current_rpo) {
current_region->SetRPO(VISITING);
std::vector<sea_ir::Region*>* succs = current_region->GetSuccessors();
for (std::vector<sea_ir::Region*>::iterator succ_it = succs->begin();
succ_it != succs->end(); ++succ_it) {
if (NOT_VISITED == (*succ_it)->GetRPO()) {
SeaGraph::ComputeRPO(*succ_it, current_rpo);
}
}
current_region->SetRPO(current_rpo--);
}
void SeaGraph::ComputeIDominators() {
bool changed = true;
while (changed) {
changed = false;
// Entry node has itself as IDOM.
std::vector<Region*>::iterator crt_it;
std::set<Region*> processedNodes;
// Find and mark the entry node(s).
for (crt_it = regions_.begin(); crt_it != regions_.end(); ++crt_it) {
if ((*crt_it)->GetPredecessors()->size() == 0) {
processedNodes.insert(*crt_it);
(*crt_it)->SetIDominator(*crt_it);
}
}
for (crt_it = regions_.begin(); crt_it != regions_.end(); ++crt_it) {
if ((*crt_it)->GetPredecessors()->size() == 0) {
continue;
}
// NewIDom = first (processed) predecessor of b.
Region* new_dom = NULL;
std::vector<Region*>* preds = (*crt_it)->GetPredecessors();
DCHECK(NULL != preds);
Region* root_pred = NULL;
for (std::vector<Region*>::iterator pred_it = preds->begin();
pred_it != preds->end(); ++pred_it) {
if (processedNodes.end() != processedNodes.find((*pred_it))) {
root_pred = *pred_it;
new_dom = root_pred;
break;
}
}
// For all other predecessors p of b, if idom is not set,
// then NewIdom = Intersect(p, NewIdom)
for (std::vector<Region*>::const_iterator pred_it = preds->begin();
pred_it != preds->end(); ++pred_it) {
DCHECK(NULL != *pred_it);
// if IDOMS[p] != UNDEFINED
if ((*pred_it != root_pred) && (*pred_it)->GetIDominator() != NULL) {
DCHECK(NULL != new_dom);
new_dom = SeaGraph::Intersect(*pred_it, new_dom);
}
}
DCHECK(NULL != *crt_it);
if ((*crt_it)->GetIDominator() != new_dom) {
(*crt_it)->SetIDominator(new_dom);
changed = true;
}
processedNodes.insert(*crt_it);
}
}
// For easily ordering of regions we need edges dominator->dominated.
for (std::vector<Region*>::iterator region_it = regions_.begin();
region_it != regions_.end(); region_it++) {
Region* idom = (*region_it)->GetIDominator();
if (idom != *region_it) {
idom->AddToIDominatedSet(*region_it);
}
}
}
Region* SeaGraph::Intersect(Region* i, Region* j) {
Region* finger1 = i;
Region* finger2 = j;
while (finger1 != finger2) {
while (finger1->GetRPO() > finger2->GetRPO()) {
DCHECK(NULL != finger1);
finger1 = finger1->GetIDominator(); // should have: finger1 != NULL
DCHECK(NULL != finger1);
}
while (finger1->GetRPO() < finger2->GetRPO()) {
DCHECK(NULL != finger2);
finger2 = finger2->GetIDominator(); // should have: finger1 != NULL
DCHECK(NULL != finger2);
}
}
return finger1; // finger1 should be equal to finger2 at this point.
}
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::BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
const art::DexFile& dex_file, uint32_t class_def_idx, uint32_t method_idx) {
class_def_idx_ = class_def_idx;
method_idx_ = method_idx;
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.
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();
}
Region* r = GetNewRegion();
// 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++) {
SignatureNode* parameter_def_node =
new sea_ir::SignatureNode(code_item->registers_size_ - 1 - crt_offset);
AddParameterNode(parameter_def_node);
r->AddChild(parameter_def_node);
}
// Pass: Assign instructions to region nodes and
// assign branches their control flow successors.
i = 0;
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]);
std::vector<InstructionNode*> sea_instructions_for_dalvik =
sea_ir::InstructionNode::Create(inst);
for (std::vector<InstructionNode*>::const_iterator cit = sea_instructions_for_dalvik.begin();
sea_instructions_for_dalvik.end() != cit; ++cit) {
last_node = node;
node = *cit;
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();
}
}
void SeaGraph::ComputeRPO() {
int rpo_id = regions_.size() - 1;
for (std::vector<Region*>::const_iterator crt_it = regions_.begin(); crt_it != regions_.end();
++crt_it) {
if ((*crt_it)->GetPredecessors()->size() == 0) {
ComputeRPO(*crt_it, rpo_id);
}
}
}
// Performs the renaming phase in traditional SSA transformations.
// See: Cooper & Torczon, "Engineering a Compiler", second edition, page 505.)
void SeaGraph::RenameAsSSA() {
utils::ScopedHashtable<int, InstructionNode*> scoped_table;
scoped_table.OpenScope();
for (std::vector<Region*>::iterator region_it = regions_.begin(); region_it != regions_.end();
region_it++) {
if ((*region_it)->GetIDominator() == *region_it) {
RenameAsSSA(*region_it, &scoped_table);
}
}
scoped_table.CloseScope();
}
void SeaGraph::ConvertToSSA() {
// Pass: find global names.
// The map @block maps registers to the blocks in which they are defined.
std::map<int, std::set<Region*> > blocks;
// The set @globals records registers whose use
// is in a different block than the corresponding definition.
std::set<int> globals;
for (std::vector<Region*>::iterator region_it = regions_.begin(); region_it != regions_.end();
region_it++) {
std::set<int> var_kill;
std::vector<InstructionNode*>* instructions = (*region_it)->GetInstructions();
for (std::vector<InstructionNode*>::iterator inst_it = instructions->begin();
inst_it != instructions->end(); inst_it++) {
std::vector<int> used_regs = (*inst_it)->GetUses();
for (std::size_t i = 0; i < used_regs.size(); i++) {
int used_reg = used_regs[i];
if (var_kill.find(used_reg) == var_kill.end()) {
globals.insert(used_reg);
}
}
const int reg_def = (*inst_it)->GetResultRegister();
if (reg_def != NO_REGISTER) {
var_kill.insert(reg_def);
}
blocks.insert(std::pair<int, std::set<Region*> >(reg_def, std::set<Region*>()));
std::set<Region*>* reg_def_blocks = &(blocks.find(reg_def)->second);
reg_def_blocks->insert(*region_it);
}
}
// Pass: Actually add phi-nodes to regions.
for (std::set<int>::const_iterator globals_it = globals.begin();
globals_it != globals.end(); globals_it++) {
int global = *globals_it;
// Copy the set, because we will modify the worklist as we go.
std::set<Region*> worklist((*(blocks.find(global))).second);
for (std::set<Region*>::const_iterator b_it = worklist.begin();
b_it != worklist.end(); b_it++) {
std::set<Region*>* df = (*b_it)->GetDominanceFrontier();
for (std::set<Region*>::const_iterator df_it = df->begin(); df_it != df->end(); df_it++) {
if ((*df_it)->InsertPhiFor(global)) {
// Check that the dominance frontier element is in the worklist already
// because we only want to break if the element is actually not there yet.
if (worklist.find(*df_it) == worklist.end()) {
worklist.insert(*df_it);
b_it = worklist.begin();
break;
}
}
}
}
}
// Pass: Build edges to the definition corresponding to each use.
// (This corresponds to the renaming phase in traditional SSA transformations.
// See: Cooper & Torczon, "Engineering a Compiler", second edition, page 505.)
RenameAsSSA();
}
void SeaGraph::RenameAsSSA(Region* crt_region,
utils::ScopedHashtable<int, InstructionNode*>* scoped_table) {
scoped_table->OpenScope();
// Rename phi nodes defined in the current region.
std::vector<PhiInstructionNode*>* phis = crt_region->GetPhiNodes();
for (std::vector<PhiInstructionNode*>::iterator phi_it = phis->begin();
phi_it != phis->end(); phi_it++) {
int reg_no = (*phi_it)->GetRegisterNumber();
scoped_table->Add(reg_no, (*phi_it));
}
// Rename operands of instructions from the current region.
std::vector<InstructionNode*>* instructions = crt_region->GetInstructions();
for (std::vector<InstructionNode*>::const_iterator instructions_it = instructions->begin();
instructions_it != instructions->end(); instructions_it++) {
InstructionNode* current_instruction = (*instructions_it);
// Rename uses.
std::vector<int> used_regs = current_instruction->GetUses();
for (std::vector<int>::const_iterator reg_it = used_regs.begin();
reg_it != used_regs.end(); reg_it++) {
int current_used_reg = (*reg_it);
InstructionNode* definition = scoped_table->Lookup(current_used_reg);
current_instruction->RenameToSSA(current_used_reg, definition);
}
// Update scope table with latest definitions.
std::vector<int> def_regs = current_instruction->GetDefinitions();
for (std::vector<int>::const_iterator reg_it = def_regs.begin();
reg_it != def_regs.end(); reg_it++) {
int current_defined_reg = (*reg_it);
scoped_table->Add(current_defined_reg, current_instruction);
}
}
// Fill in uses of phi functions in CFG successor regions.
const std::vector<Region*>* successors = crt_region->GetSuccessors();
for (std::vector<Region*>::const_iterator successors_it = successors->begin();
successors_it != successors->end(); successors_it++) {
Region* successor = (*successors_it);
successor->SetPhiDefinitionsForUses(scoped_table, crt_region);
}
// Rename all successors in the dominators tree.
const std::set<Region*>* dominated_nodes = crt_region->GetIDominatedSet();
for (std::set<Region*>::const_iterator dominated_nodes_it = dominated_nodes->begin();
dominated_nodes_it != dominated_nodes->end(); dominated_nodes_it++) {
Region* dominated_node = (*dominated_nodes_it);
RenameAsSSA(dominated_node, scoped_table);
}
scoped_table->CloseScope();
}
void SeaGraph::GenerateLLVM() {
// Pass: Generate LLVM IR.
CodeGenPrepassVisitor code_gen_prepass_visitor;
std::cout << "Generating code..." << std::endl;
std::cout << "=== PRE VISITING ===" << std::endl;
Accept(&code_gen_prepass_visitor);
CodeGenVisitor code_gen_visitor(code_gen_prepass_visitor.GetData());
std::cout << "=== VISITING ===" << std::endl;
Accept(&code_gen_visitor);
std::cout << "=== POST VISITING ===" << std::endl;
CodeGenPostpassVisitor code_gen_postpass_visitor(code_gen_visitor.GetData());
Accept(&code_gen_postpass_visitor);
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) {
// 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);
// Pass: Compute reverse post-order of regions.
ComputeRPO();
// Multiple passes: compute immediate dominators.
ComputeIDominators();
// Pass: compute downward-exposed definitions.
ComputeDownExposedDefs();
// Multiple Passes (iterative fixed-point algorithm): Compute reaching definitions
ComputeReachingDefs();
// Pass (O(nlogN)): Compute the dominance frontier for region nodes.
ComputeDominanceFrontier();
// Two Passes: Phi node insertion.
ConvertToSSA();
// Pass: Generate LLVM IR.
GenerateLLVM();
}
void SeaGraph::ComputeDominanceFrontier() {
for (std::vector<Region*>::iterator region_it = regions_.begin();
region_it != regions_.end(); region_it++) {
std::vector<Region*>* preds = (*region_it)->GetPredecessors();
if (preds->size() > 1) {
for (std::vector<Region*>::iterator pred_it = preds->begin();
pred_it != preds->end(); pred_it++) {
Region* runner = *pred_it;
while (runner != (*region_it)->GetIDominator()) {
runner->AddToDominanceFrontier(*region_it);
runner = runner->GetIDominator();
}
}
}
}
}
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 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);
}
*/
void Region::AddChild(sea_ir::InstructionNode* instruction) {
DCHECK(instruction) << "Tried to add NULL instruction to region node.";
instructions_.push_back(instruction);
instruction->SetRegion(this);
}
SeaNode* Region::GetLastChild() const {
if (instructions_.size() > 0) {
return instructions_.back();
}
return NULL;
}
void Region::ToDot(std::string& result, const art::DexFile& dex_file) const {
result += "\n// Region: \nsubgraph " + StringId() + " { label=\"region " + StringId() + "(rpo=";
result += art::StringPrintf("%d", rpo_number_);
if (NULL != GetIDominator()) {
result += " dom=" + GetIDominator()->StringId();
}
result += ")\";\n";
for (std::vector<PhiInstructionNode*>::const_iterator cit = phi_instructions_.begin();
cit != phi_instructions_.end(); cit++) {
result += (*cit)->StringId() +";\n";
}
for (std::vector<InstructionNode*>::const_iterator cit = instructions_.begin();
cit != instructions_.end(); cit++) {
result += (*cit)->StringId() +";\n";
}
result += "} // End Region.\n";
// Save phi-nodes.
for (std::vector<PhiInstructionNode*>::const_iterator cit = phi_instructions_.begin();
cit != phi_instructions_.end(); cit++) {
(*cit)->ToDot(result, dex_file);
}
// Save instruction nodes.
for (std::vector<InstructionNode*>::const_iterator cit = instructions_.begin();
cit != instructions_.end(); cit++) {
(*cit)->ToDot(result, dex_file);
}
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)->GetLastChild()->StringId() +
"[lhead=" + (*cit)->StringId() + ", " + "ltail=" + StringId() + "];\n\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));
}
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;
}
bool Region::InsertPhiFor(int reg_no) {
if (!ContainsPhiFor(reg_no)) {
phi_set_.insert(reg_no);
PhiInstructionNode* new_phi = new PhiInstructionNode(reg_no);
new_phi->SetRegion(this);
phi_instructions_.push_back(new_phi);
return true;
}
return false;
}
void Region::SetPhiDefinitionsForUses(
const utils::ScopedHashtable<int, InstructionNode*>* scoped_table, Region* predecessor) {
int predecessor_id = -1;
for (unsigned int crt_pred_id = 0; crt_pred_id < predecessors_.size(); crt_pred_id++) {
if (predecessors_.at(crt_pred_id) == predecessor) {
predecessor_id = crt_pred_id;
}
}
DCHECK_NE(-1, predecessor_id);
for (std::vector<PhiInstructionNode*>::iterator phi_it = phi_instructions_.begin();
phi_it != phi_instructions_.end(); phi_it++) {
PhiInstructionNode* phi = (*phi_it);
int reg_no = phi->GetRegisterNumber();
InstructionNode* definition = scoped_table->Lookup(reg_no);
phi->RenameToSSA(reg_no, definition, predecessor_id);
}
}
std::vector<InstructionNode*> InstructionNode::Create(const art::Instruction* in) {
std::vector<InstructionNode*> sea_instructions;
switch (in->Opcode()) {
case art::Instruction::CONST_4:
sea_instructions.push_back(new ConstInstructionNode(in));
break;
case art::Instruction::RETURN:
sea_instructions.push_back(new ReturnInstructionNode(in));
break;
case art::Instruction::IF_NE:
sea_instructions.push_back(new IfNeInstructionNode(in));
break;
case art::Instruction::ADD_INT_LIT8:
sea_instructions.push_back(new UnnamedConstInstructionNode(in, in->VRegB_22b()));
sea_instructions.push_back(new AddIntLitInstructionNode(in));
break;
case art::Instruction::MOVE_RESULT:
sea_instructions.push_back(new MoveResultInstructionNode(in));
break;
case art::Instruction::INVOKE_STATIC:
sea_instructions.push_back(new InvokeStaticInstructionNode(in));
break;
case art::Instruction::ADD_INT:
sea_instructions.push_back(new AddIntInstructionNode(in));
break;
case art::Instruction::GOTO:
sea_instructions.push_back(new GotoInstructionNode(in));
break;
case art::Instruction::IF_EQZ:
sea_instructions.push_back(new IfEqzInstructionNode(in));
break;
default:
// Default, generic IR instruction node; default case should never be reached
// when support for all instructions ahs been added.
sea_instructions.push_back(new InstructionNode(in));
}
return sea_instructions;
}
void InstructionNode::ToDotSSAEdges(std::string& result) const {
// SSA definitions:
for (std::map<int, InstructionNode*>::const_iterator def_it = definition_edges_.begin();
def_it != definition_edges_.end(); def_it++) {
if (NULL != def_it->second) {
result += def_it->second->StringId() + " -> " + StringId() + "[color=gray,label=\"";
result += art::StringPrintf("vR = %d", def_it->first);
result += "\"] ; // ssa edge\n";
}
}
// SSA used-by:
if (DotConversion::SaveUseEdges()) {
for (std::vector<InstructionNode*>::const_iterator cit = used_in_.begin();
cit != used_in_.end(); cit++) {
result += (*cit)->StringId() + " -> " + StringId() + "[color=gray,label=\"";
result += "\"] ; // SSA used-by edge\n";
}
}
}
void InstructionNode::ToDot(std::string& result, const art::DexFile& dex_file) const {
result += "// Instruction ("+StringId()+"): \n" + StringId() +
" [label=\"" + instruction_->DumpString(&dex_file) + "\"";
if (de_def_) {
result += "style=bold";
}
result += "];\n";
ToDotSSAEdges(result);
}
void InstructionNode::MarkAsDEDef() {
de_def_ = true;
}
int InstructionNode::GetResultRegister() const {
if (instruction_->HasVRegA() && InstructionTools::IsDefinition(instruction_)) {
return instruction_->VRegA();
}
return NO_REGISTER;
}
std::vector<int> InstructionNode::GetDefinitions() const {
// TODO: Extend this to handle instructions defining more than one register (if any)
// The return value should be changed to pointer to field then; for now it is an object
// so that we avoid possible memory leaks from allocating objects dynamically.
std::vector<int> definitions;
int result = GetResultRegister();
if (NO_REGISTER != result) {
definitions.push_back(result);
}
return definitions;
}
std::vector<int> InstructionNode::GetUses() {
std::vector<int> uses; // Using vector<> instead of set<> because order matters.
if (!InstructionTools::IsDefinition(instruction_) && (instruction_->HasVRegA())) {
int vA = instruction_->VRegA();
uses.push_back(vA);
}
if (instruction_->HasVRegB()) {
int vB = instruction_->VRegB();
uses.push_back(vB);
}
if (instruction_->HasVRegC()) {
int vC = instruction_->VRegC();
uses.push_back(vC);
}
return uses;
}
void PhiInstructionNode::ToDot(std::string& result, const art::DexFile& dex_file) const {
result += "// PhiInstruction: \n" + StringId() +
" [label=\"" + "PHI(";
result += art::StringPrintf("%d", register_no_);
result += ")\"";
result += "];\n";
ToDotSSAEdges(result);
}
} // namespace sea_ir