| /* |
| * 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. |
| */ |
| |
| |
| #ifndef SEA_IR_H_ |
| #define SEA_IR_H_ |
| |
| #include <set> |
| #include <map> |
| |
| #include "dex_file.h" |
| #include "dex_instruction.h" |
| #include "sea_ir/instruction_tools.h" |
| #include "utils/scoped_hashtable.h" |
| |
| |
| namespace sea_ir { |
| |
| #define NO_REGISTER (-1) |
| |
| // Reverse post-order numbering constants |
| enum RegionNumbering { |
| NOT_VISITED = -1, |
| VISITING = -2 |
| }; |
| |
| class Region; |
| class InstructionNode; |
| class PhiInstructionNode; |
| |
| class SeaNode { |
| public: |
| explicit SeaNode():id_(GetNewId()), string_id_(), successors_(), predecessors_() { |
| std::stringstream ss; |
| ss << id_; |
| string_id_.append(ss.str()); |
| } |
| // Adds CFG predecessors and successors to each block. |
| void AddSuccessor(Region* successor); |
| void AddPredecessor(Region* predecesor); |
| |
| std::vector<sea_ir::Region*>* GetSuccessors() { |
| return &successors_; |
| } |
| std::vector<sea_ir::Region*>* GetPredecessors() { |
| return &predecessors_; |
| } |
| // Returns the id of the current block as string |
| const std::string& StringId() const { |
| return string_id_; |
| } |
| // Appends to @result 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, but without prolog ("digraph {") and epilog ("}"). |
| virtual void ToDot(std::string& result) const = 0; |
| |
| virtual ~SeaNode() {} |
| |
| protected: |
| static int GetNewId() { |
| return current_max_node_id_++; |
| } |
| |
| const int id_; |
| std::string string_id_; |
| std::vector<sea_ir::Region*> successors_; // CFG successor nodes (regions) |
| std::vector<sea_ir::Region*> predecessors_; // CFG predecessor nodes (instructions/regions) |
| |
| private: |
| static int current_max_node_id_; |
| }; |
| |
| class InstructionNode: public SeaNode { |
| public: |
| explicit InstructionNode(const art::Instruction* in): |
| SeaNode(), instruction_(in), de_def_(false) {} |
| // Returns the Dalvik instruction around which this InstructionNode is wrapped. |
| const art::Instruction* GetInstruction() const { |
| DCHECK(NULL != instruction_) << "Tried to access NULL instruction in an InstructionNode."; |
| return instruction_; |
| } |
| // Returns the register that is defined by the current instruction, or NO_REGISTER otherwise. |
| virtual int GetResultRegister() const; |
| // Returns the set of registers defined by the current instruction. |
| virtual std::vector<int> GetDefinitions() const; |
| // Returns the set of register numbers that are used by the instruction. |
| virtual std::vector<int> GetUses(); |
| // Appends to @result the .dot string representation of the instruction. |
| void ToDot(std::string& result) const; |
| // Mark the current instruction as a dowward exposed definition. |
| void MarkAsDEDef(); |
| // Rename the use of @reg_no to refer to the instruction @definition, |
| // essentially creating SSA form. |
| void RenameToSSA(int reg_no, InstructionNode* definition) { |
| definition_edges_.insert(std::pair<int, InstructionNode*>(reg_no, definition)); |
| } |
| |
| private: |
| const art::Instruction* const instruction_; |
| std::map<int, InstructionNode* > definition_edges_; |
| bool de_def_; |
| }; |
| |
| class SignatureNode: public InstructionNode { |
| public: |
| explicit SignatureNode(unsigned int start_register, unsigned int count): |
| InstructionNode(NULL), defined_regs_() { |
| for (unsigned int crt_offset = 0; crt_offset < count; crt_offset++) { |
| defined_regs_.push_back(start_register - crt_offset); |
| } |
| } |
| |
| void ToDot(std::string& result) const { |
| result += StringId() +"[label=\"signature:"; |
| std::stringstream vector_printer; |
| if (!defined_regs_.empty()) { |
| for (unsigned int crt_el = 0; crt_el < defined_regs_.size()-1; crt_el++) { |
| vector_printer << defined_regs_[crt_el] <<","; |
| } |
| vector_printer << defined_regs_[defined_regs_.size()-1] <<";"; |
| } |
| result += "\"] // signature node\n"; |
| } |
| |
| std::vector<int> GetDefinitions() const { |
| return defined_regs_; |
| } |
| |
| int GetResultRegister() const { |
| return NO_REGISTER; |
| } |
| |
| std::vector<int> GetUses() { |
| return std::vector<int>(); |
| } |
| |
| private: |
| std::vector<int> defined_regs_; |
| }; |
| |
| |
| class PhiInstructionNode: public InstructionNode { |
| public: |
| explicit PhiInstructionNode(int register_no): |
| InstructionNode(NULL), register_no_(register_no), definition_edges_() {} |
| // Appends to @result the .dot string representation of the instruction. |
| void ToDot(std::string& result) const; |
| // Returns the register on which this phi-function is used. |
| int GetRegisterNumber() { |
| return register_no_; |
| } |
| |
| // Rename the use of @reg_no to refer to the instruction @definition. |
| // Phi-functions are different than normal instructions in that they |
| // have multiple predecessor regions; this is why RenameToSSA has |
| // the additional parameter specifying that @parameter_id is the incoming |
| // edge for @definition, essentially creating SSA form. |
| void RenameToSSA(int reg_no, InstructionNode* definition, unsigned int predecessor_id) { |
| DCHECK(NULL != definition) << "Tried to rename to SSA using a NULL definition for " |
| << StringId() << " register " << reg_no; |
| if (definition_edges_.size() < predecessor_id+1) { |
| definition_edges_.resize(predecessor_id+1, NULL); |
| } |
| |
| if (NULL == definition_edges_.at(predecessor_id)) { |
| definition_edges_[predecessor_id] = new std::map<int, InstructionNode*>(); |
| } |
| definition_edges_[predecessor_id]->insert(std::pair<int, InstructionNode*>(reg_no, definition)); |
| } |
| |
| private: |
| int register_no_; |
| std::vector<std::map<int, InstructionNode*>*> definition_edges_; |
| }; |
| |
| class Region : public SeaNode { |
| public: |
| explicit Region(): |
| SeaNode(), reaching_defs_size_(0), rpo_(NOT_VISITED), idom_(NULL), |
| idominated_set_(), df_(), phi_set_() {} |
| |
| // Adds @instruction as an instruction node child in the current region. |
| void AddChild(sea_ir::InstructionNode* insttruction); |
| |
| // Returns the last instruction node child of the current region. |
| // This child has the CFG successors pointing to the new regions. |
| SeaNode* GetLastChild() const; |
| // Returns all the child instructions of this region, in program order. |
| std::vector<InstructionNode*>* GetInstructions() { |
| return &instructions_; |
| } |
| // Appends to @result 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 void ToDot(std::string& result) const; |
| // Computes Downward Exposed Definitions for the current node. |
| |
| void ComputeDownExposedDefs(); |
| const std::map<int, sea_ir::InstructionNode*>* GetDownExposedDefs() const; |
| |
| // Performs one iteration of the reaching definitions algorithm |
| // and returns true if the reaching definitions set changed. |
| bool UpdateReachingDefs(); |
| // Returns the set of reaching definitions for the current region. |
| std::map<int, std::set<sea_ir::InstructionNode*>* >* GetReachingDefs(); |
| |
| void SetRPO(int rpo) { |
| rpo_ = rpo; |
| } |
| |
| int GetRPO() { |
| return rpo_; |
| } |
| |
| void SetIDominator(Region* dom) { |
| idom_ = dom; |
| } |
| |
| Region* GetIDominator() const { |
| return idom_; |
| } |
| |
| void AddToIDominatedSet(Region* dominated) { |
| idominated_set_.insert(dominated); |
| } |
| |
| const std::set<Region*>* GetIDominatedSet() { |
| return &idominated_set_; |
| } |
| |
| // Adds @df_reg to the dominance frontier of the current region. |
| void AddToDominanceFrontier(Region* df_reg) { |
| df_.insert(df_reg); |
| } |
| // Returns the dominance frontier of the current region. |
| // Preconditions: SeaGraph.ComputeDominanceFrontier() |
| std::set<Region*>* GetDominanceFrontier() { |
| return &df_; |
| } |
| // Returns true if the region contains a phi function for @reg_no. |
| bool ContainsPhiFor(int reg_no) { |
| return (phi_set_.end() != phi_set_.find(reg_no)); |
| } |
| // Returns the phi-functions from the region. |
| std::vector<PhiInstructionNode*>* GetPhiNodes() { |
| return &phi_instructions_; |
| } |
| // Adds a phi-function for @reg_no to this region. |
| // Note: The insertion order does not matter, as phi-functions |
| // are conceptually executed at the same time. |
| bool InsertPhiFor(int reg_no); |
| // Sets the phi-function uses to be as defined in @scoped_table for predecessor @@predecessor. |
| void SetPhiDefinitionsForUses(const utils::ScopedHashtable<int, InstructionNode*>* scoped_table, |
| Region* predecessor); |
| |
| private: |
| std::vector<sea_ir::InstructionNode*> instructions_; |
| std::map<int, sea_ir::InstructionNode*> de_defs_; |
| std::map<int, std::set<sea_ir::InstructionNode*>* > reaching_defs_; |
| int reaching_defs_size_; |
| int rpo_; |
| // Immediate dominator node. |
| Region* idom_; |
| // The set of nodes immediately dominated by the region. |
| std::set<Region*> idominated_set_; |
| // Records the dominance frontier. |
| std::set<Region*> df_; |
| // Records the set of register numbers that have phi nodes in this region. |
| std::set<int> phi_set_; |
| std::vector<PhiInstructionNode*> phi_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; |
| // Recursively computes the reverse postorder value for @crt_bb and successors. |
| static void ComputeRPO(Region* crt_bb, int& crt_rpo); |
| // Returns the "lowest common ancestor" of @i and @j in the dominator tree. |
| static Region* Intersect(Region* i, Region* j); |
| |
| private: |
| // Registers @childReg as a region belonging to the SeaGraph instance. |
| void AddRegion(Region* childReg); |
| // Returns new region and registers it with the SeaGraph instance. |
| Region* GetNewRegion(); |
| // Adds a CFG edge from @src node to @dst node. |
| void AddEdge(Region* src, Region* dst) const; |
| // Builds the non-SSA sea-ir representation of the function @code_item from @dex_file. |
| void BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item, const art::DexFile& dex_file); |
| // Computes immediate dominators for each region. |
| // Precondition: ComputeMethodSeaGraph() |
| void ComputeIDominators(); |
| // Computes Downward Exposed Definitions for all regions in the graph. |
| void ComputeDownExposedDefs(); |
| // Computes the reaching definitions set following the equations from |
| // Cooper & Torczon, "Engineering a Compiler", second edition, page 491. |
| // Precondition: ComputeDEDefs() |
| void ComputeReachingDefs(); |
| // Computes the reverse-postorder numbering for the region nodes. |
| // Precondition: ComputeDEDefs() |
| void ComputeRPO(); |
| // Computes the dominance frontier for all regions in the graph, |
| // following the algorithm from |
| // Cooper & Torczon, "Engineering a Compiler", second edition, page 499. |
| // Precondition: ComputeIDominators() |
| void ComputeDominanceFrontier(); |
| |
| void ConvertToSSA(); |
| // Identifies the definitions corresponding to uses for region @node |
| // by using the scoped hashtable of names @ scoped_table. |
| void RenameAsSSA(Region* node, utils::ScopedHashtable<int, InstructionNode*>* scoped_table); |
| void RenameAsSSA(); |
| |
| static SeaGraph graph_; |
| std::vector<Region*> regions_; |
| }; |
| } // end namespace sea_ir |
| #endif |