/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You 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. */ /** * @author Intel, Mikhail Y. Fursov * */ /** * @file * The baseline implementation of control flow graph (CFG) and * CFG level routines. * * The implementation can be reused and extended by different * components as a base level for IR representation. */ #ifndef _CONTROLFLOWGRAPH_ #define _CONTROLFLOWGRAPH_ #include #include #include "Dlink.h" #include "Stl.h" #include "open/types.h" namespace Jitrino { class Edge; class Node; class CFGInst; class ControlFlowGraph; class Type; class DominatorTree; class LoopTree; typedef StlVector Edges; typedef StlVector Nodes; /** * The edge connecting two nodes in CFG and having a direction and type. * To extend the given class with a custom properties, * override the createEdge method * of the ControlFlowGraphFactory class. */ class Edge { /** * The ControlFlowGraph class that requires additional privileges to * initialize protected fields of the Edge instance. */ friend class ControlFlowGraph; /** * The ControlFlowGraphFactory class that requires additional access privileges * to access the protected constructor. */ friend class ControlFlowGraphFactory; public: /** * The edge kind. * The edge kind depends on the Source and the * Target node kinds and is calculated * every time the getKind method is invoked. */ enum Kind { /// All edges to the Dispatch node (DN) are Dispatch edges. Kind_Dispatch = 1, /// Jump, fall-through with no branch, indirect jump or edge to the Exit node. Kind_Unconditional = 2, /// Fall-through after a not-taken branch, default target of switches (max one out-edge per node). Kind_False = 4, /// A taken branch. Kind_True = 8, /// All edges from DN to Block node (BNCFGInst::next() == CFGInst::prev() ) are Catch edges. Kind_Catch = 16 }; /// The destructor. Does nothing. virtual ~Edge() {} /** * ID is constant for the lifetime of the edge. * * @return The unique edge ID that is constant for lifetime of this edge. */ U_32 getId() const {return id;} /** * Returns the edge kind. * * @return The kind of the given edge. */ virtual Kind getKind() const; /** * Checks whether the edge is a Dispatch one, that is if the * edge is of the Edge::Kind_Dispatch kind. * * @return TRUE for the Edge::Kind_Dispatch * edge; otherwise, FALSE. */ bool isDispatchEdge() const {return getKind() == Edge::Kind_Dispatch;} /** * Checks whether the edge is an Unconditional one, that is if * the edge is of the Edge::Kind_Unconditional kind. * * @return TRUE for the Edge::Kind_Unconditional * edge; otherwise, FALSE. */ bool isUnconditionalEdge() const {return getKind() == Edge::Kind_Unconditional;} /** * Checks whether the edge is a False one, that is if the * edge is of the Edge::Kind_False kind. * * @return TRUE for the Edge::Kind_False * edge; otherwise, FALSE. */ bool isFalseEdge() const {return getKind() == Edge::Kind_False;} /** * Checks whether the edge is a True one, that is if the edge is * of the Edge::Kind_True kind. * * @return TRUE for the Edge::Kind_True * edge; otherwise, FALSE. */ bool isTrueEdge() const {return getKind() == Edge::Kind_True;} /** * Checks whether the edge is a Catch one, that is if the edge * is of the Edge::Kind_Catch kind. * * @return TRUE for the Edge::Kind_Catch * edge; otherwise, FALSE. */ bool isCatchEdge() const {return getKind() == Edge::Kind_Catch;} /** * Returns the Source node of the edge. The Source * node is also called the Tail or From * node. * * @return The Source node of the edge. */ Node* getSourceNode() const {return source;} /** * Returns the Target node of the edge. The Target * node is also called the Head or To node. * * @return The Target node of the edge. */ Node* getTargetNode() const {return target;} /** * Returns the Target or the Source node depending * on the isForward parameter. * * @param[in] isForward - tells which node to return * * @return If the isForward parameter is True, * returns the Target node; otherwise, * the Source node. */ Node* getNode(bool isForward) const {return isForward ? target : source;} /** * @return The probability of the edge. */ double getEdgeProb() const {return prob;} /** * Sets the probability of the edge. * * @param[in] val - a new edge probability */ void setEdgeProb(double val) {prob = val;} protected: /** * Initializes a new Edge instance. * The ID field is initialized with MAX_UINT32, * all other fields are initialized with 0. */ Edge() : id (MAX_UINT32), source(NULL), target(NULL), prob(0) {} /** * The helper method to set ID to the edge * * @param[in] _id - a new edge ID */ void setId(U_32 _id) {id = _id;} /// The unique edge ID within CFG. U_32 id; /// The Source or the Tail node of the edge. Node *source; /// The Target or the Head node of the edge. Node *target; /** The edge probability. * If the ControlFlowGraph edge profile is valid, the sum of all * outgoing edge probabilities for a node is equal to 1. */ double prob; }; #define ILLEGAL_BC_MAPPING_VALUE 0xFFFF /** * The base abstract class for all CFG instructions. * The given class keeps information about the node this instruction belongs * to, about previous and next instructions in the node and about instruction * properties needed to perform CFG validity checks and to detect edge types * for block-to-block edges correctly. * * @note The CFGInst class behaves like DLink, * when none node is assigned to the instruction. */ class CFGInst : protected Dlink { /** * The Node class needs additional privileges to * initialize protected fields of the CFGInst instance. */ friend class Node; /** * The Edge class needs additional privileges to * initialize protected fields of the CFGInst instance. */ friend class Edge; /** * The ControlFlowGraph class needs additional privileges to * initialize protected fields of the CFGInst instance. */ friend class ControlFlowGraph; public: virtual ~CFGInst(){} /** * Gets the current node the instruction belongs to. * * @return The node instance the given instruction belongs to or * NULL if the instruction was unlinked or never added * to any node. */ Node* getNode() const {return node;} /** * Gets the next instruction. * * @return The next instruction in the node, or NULL if the * instruction is the last instruction in the node. * * @note The CFGInst class behaves like DLink when none * node is assigned to the instruction. */ CFGInst* next() const; /** * Gets the previous instruction. * * @return Returns the previous instruction in the node; if the instruction * is the first one in the node, returns NULL. * * @note The CFGInst class behaves like DLinkM when none node * is assigned to the instruction. */ CFGInst* prev() const; /** * Removes the instruction from the node. * * @note The CFGInst class behaves like DLink when none node * is assigned to the instruction.
* CFGInst::next() == CFGInst::prev() == this after the call. */ void unlink() {node = NULL; Dlink::unlink();} /** * Inserts the instruction before instBefore. * Assigns the node from instBefore to the instruction. * * @param[in] instBefore - the insertion point, before which the instruction * goes * * @note If the instruction is followed by other instructions, the call * inserts and assigns them to the node. Only instructions with the * NULL node can be inserted. */ void insertBefore(CFGInst* instBefore); /** * Inserts the instruction after instAfter. * Assigns the node from instAfter to the instruction. * * @param[in] instAfter - the insertion point, before which the instruction * goes * * @note If the instruction is followed by other instructions, the call * inserts and assigns them to the node. * Only instructions with the NULL node can * be inserted. */ void insertAfter(CFGInst* instAfter); /** * Checks whether the instruction is the header critical one. * Only another header critical instruction can precede the * header critical instruction. * CFG uses the given property to check validity when adding * or removing instructions to the node. * * @return TRUE for the header critical instruction. */ virtual bool isHeaderCriticalInst() const {return isLabel();} /** * Checks whether the instruction is the label one. * Only one label instruction per node can exist. * CFG uses the given property to check validity when adding * or removing instructions to the node. * * @return TRUE for the label instruction. * * @note The label instruction is also a header critical instruction. */ virtual bool isLabel() const {return false;} /// Returns byte-code offset the inst uint16 getBCOffset() const { return bcOffset;} /// Sets byte-code offset the inst void setBCOffset(uint16 newVal) {bcOffset = newVal;} protected: /// Called from CFG to detect edge kinds for BN to BN edges. virtual Edge::Kind getEdgeKind(const Edge* edge) const = 0; /// Called from CFG, when the edge target is replaced. virtual void updateControlTransferInst(Node* oldTarget, Node* newTarget) {} /// Called from CFG when two blocks are merging and one of the branches is redundant. virtual void removeRedundantBranch(){}; protected: /** * The default constructor. * Initializes the Node instance field with the NULL * value. */ CFGInst() : node(NULL), bcOffset(ILLEGAL_BC_MAPPING_VALUE) {} /// The owner node of the instruction. Node* node; ///offset in byte-code uint16 bcOffset; }; /** * The node representation and the base class for all nodes in CFG. * Three node classes in the control flow graph exist: * Block nodes, Dispatch nodes, and the * Exit node. * All of them can contain an instruction. */ class Node { /** * The ControlFlowGraph class that requires additional privileges to * initialize protected fields of the Node instance. */ friend class ControlFlowGraph; /** * The ControlFlowGraphFactory class that requires additional privileges to * access to the protected constructor of the Node instance. */ friend class ControlFlowGraphFactory; /** * The CFGInst class that requires additional privileges to * initialize protected fields of the Node instance. */ friend class CFGInst; public: /** * The kind of the node. * CFG has three node kinds:
*
  • * Kind_Block - used for usual nodes with instructions
    *
  • Kind_Dispatch - used for exceptions paths. The * Dispatch node connects the Block * node throwing exception with another Block * node catching the exception. * If none Block node catches all possible * exception types, the Dispatch node can also * be connected with another Dispatch node. * To represent a path when an exception is not caught in * a current method, the Unwind node is used.
    *
  • Kind_Exit - CFG has only one Exit node. The * Exit node postdominates any exit path from * the methods. Only CFG without exits, like * While(True); patterns, can have no * Exit node at all.
*/ enum Kind { /// Basic Block node Kind_Block, /// Dispatch node Kind_Dispatch, /// Exit node Kind_Exit }; virtual ~Node() {} /** * Gets the kind of the node. * * @return The kind of the node. */ Kind getKind() const {return kind;} /** * Gets the unique node ID. The ID is unique for all nodes in the containing * flow graph and is constant for the lifetime of this node. * This method provides a sparse ID between zero * and the graph getMaxNodeId() value. * * @return The unique node ID in the containing flow graph. */ U_32 getId() const {return id;} /** * Gets the depth-first numbering of the given node computed during the last * pass. * Use this number as a dense ID of the node until CFG is not modified. * * @return The depth of the first numbering of the given node. * * @note Df-numbering differes from pre-numbering by being recalculated only * after the direct graph ordering, that is when the * isForward parameter is TRUE in the * orderNodes(isForward) method call. */ U_32 getDfNum() const {return dfNumber;} /** * Gets the pre-num numbering of the given node computed during the last pass. * Use this number as a dense ID of the node until CFG is not modified. * * @return The pre-num numbering of the given node. */ U_32 getPreNum() const {return preNumber;} /** * Gets the post-num numbering of the given node computed during the last pass. * Use this number as a dense ID of the node until CFG is not modified. * * @return The post-num numbering of the given node. */ U_32 getPostNum() const {return postNumber;} /** * Checks whether the node is a Block one. * * @return TRUE for the Node::Kind_Block node. */ bool isBlockNode() const {return getKind() == Node::Kind_Block;} /** * Checks whether the node is a Dispatch one. * * @return TRUE for the Node::Kind_Dispatch node. */ bool isDispatchNode() const {return getKind() == Node::Kind_Dispatch;} /** * Checks whether the node is an Exit one. * * @return TRUE for the Node::Kind_Exit node. */ bool isExitNode() const {return getKind() == Node::Kind_Exit;} /** * Checks whether the node is a Catch one. * * @return TRUE if the node is of the Node::Kind_Block kind and * the only incoming edge of the node is of the Edge::Kind_CatchEdge * kind. */ bool isCatchBlock() const {return getInDegree() >=1 && getInEdges().front()->isCatchEdge();} /** * Gets the incoming edges to the node. * * @return The collection of the incoming edges to the node. * * @note The ordering of edges in the collection is not specified. */ const Edges& getInEdges() const {return inEdges;} /** * Gets the outgoing edges to the node. * * @return The collection of the outgoing edges to the node. * * @note The ordering of edges in the collection is not specified. */ const Edges& getOutEdges() const {return outEdges;} /** * Gets the incoming or outgoing edges to the node. * * @param[in] isForward - tells what kind of edges, incoming or outgoing, * to return * * @return If the isForwarisForward parameter is TRUE, * returns the collection of incoming edges; * otherwise, the collection of outgoing ones. * * @note The ordering of edges in the collection is not specified. */ const Edges& getEdges(bool isForward) const {return isForward ? outEdges : inEdges;} /** * Gets the first outgoing edge that matches the edgeKind kind. * * @param[in] edgeKind - the kind of the edge to find * * @return The first outgoing edge matching the edgeKind parameter; * NULL if no edge of the specified kind has been found. * */ Edge* getOutEdge(Edge::Kind edgeKind) const; /** * Gets the first unconditional outgoing edge. * * @return The first outgoing edge matching the Edge::Kind_Unconditional * parameter; NULL if no edge of the specified * kind has been found. * * @note The edge collections ordering is not specified. */ Edge* getUnconditionalEdge() const {return getOutEdge(Edge::Kind_Unconditional);} /** * Gets the outgoing edge with the Edge::Kind_False kind. * * @return The first outgoing edge matching the Edge::Kind_False * parameter; NULL if no edge of the specified * kind has been found. * * @note The only one outgoing edge of the Edge::Kind_False kind is * allowed per node. */ Edge* getFalseEdge() const {return getOutEdge(Edge::Kind_False);} /** * Gets the first True outgoing edge. * * @return The first outgoing edge matching the Edge::Kind_True * parameter; NULL if no edge of the specified * kind has been found. * * @note The edge collections ordering is not specified. */ Edge* getTrueEdge() const {return getOutEdge(Edge::Kind_True);} /** * Gets the outgoing edge of the Edge::Kind_Dispatch kind. * * @return The first outgoing edge matching the Edge::Kind_Dispatch * parameter; NULL if no edge of the specified * kind has been found. * * @note The only one outgoing edge of the Edge::Kind_Dispatch kind is * allowed per node. */ Edge* getExceptionEdge() const {return getOutEdge(Edge::Kind_Dispatch);} /** * Checks whether the node is connected to anotherNode. * * @param[in] isForward - the direction of the connection. If TRUE * the outgoing edges are checked, if FALSE * the incoming edges are checked. * * @param[in] anotherNode - the node to check connection with * * @return TRUE if the node is connected with anotherNode * using isForward edges; otherwise, returns FALSE, * or TRUE. */ bool isConnectedTo(bool isForward, Node* anotherNode) const {return findEdgeTo(isForward, anotherNode)!=NULL;} /** * Finds the edge connected to anotherNode. * * @param[in] isForward - the direction of the connection. If TRUE * the outgoing edges are checked, if FALSE * the incoming edges are checked. * * @param[in] anotherNode - the node that the edge connects to * * @return The edge connects the node and the anotherNode with * the direction isForwarisForward; * otherwise NULL. */ Edge* findEdgeTo(bool isForward, Node* anotherNode) const; /** * Finds the first outgoing edge with the specified kind * and returns its Target node. * * @param[in] edgeKind - the kind of the edge to find * * @return The Target node of the outgoing edge of the * edgeKind kind; NULL if such an * edge has not beed found. * */ Node* getEdgeTarget(Edge::Kind edgeKind) const {Edge* edge = getOutEdge(edgeKind); return edge == NULL ? NULL : edge->getTargetNode();} /** * Finds the first unconditional outgoing edge and returns its * Target node. * * @return The Target node of the outgoing edge of * the Edge::Kind_Unconditional kind; NULL * if such an edge has not beed found. * */ Node* getUnconditionalEdgeTarget() const {return getEdgeTarget(Edge::Kind_Unconditional);} /** * Finds the False outgoing edge and returns its * Target node. * * @return The Target node of the outgoing edge of * the Edge::Kind_False kind; NULL if such an * edge has not beed found. */ Node* getFalseEdgeTarget() const {return getEdgeTarget(Edge::Kind_False);} /** * Finds the first True outgoing edge and returns its * Target node. * * @return The Target node of the outgoing edge of the * Edge::Kind_True kind; NULL if such an edge * has not beed found. * */ Node* getTrueEdgeTarget() const {return getEdgeTarget(Edge::Kind_True);} /** * Finds the Dispatch edge and returns its Target * node. * * @return The Target node of the outgoing edge of the * Edge::Kind_Dispatch kind; NULL if such an edge * has not beed found. */ Node* getExceptionEdgeTarget() const {return getEdgeTarget(Edge::Kind_Dispatch);} /** * Finds the edge connecting the node with anotherNode. * * @param[in] isForward - the search in the outgoing edges, if TRUE; otherwise, in the incoming edges * @param[in] anotherNode - the node connected with the given node by the edge * * @return The edge connecting the node with anotherNode; * otherwise, NULL. */ Edge* findEdge(bool isForward, const Node* anotherNode) const; /** * Finds the incoming edge connecting the node with anotherNode. * * @param[in] anotherNode - the node connected with the given node by the edge * * @return The incoming edge connecting the node with anotherNode; * otherwise, NULL. */ Edge* findSourceEdge(const Node* source) const {return findEdge(false, source);} /** * Finds the outgoing edge connecting the node with anotherNode. * * @param[in] anotherNode - the node connected with the given node by the edge * * @return The outgoing edge connecting the node with anotherNode; * otherwise, NULL. */ Edge* findTargetEdge(const Node* target) const {return findEdge(true, target);} /** * Gets the number of outgoing edges of the node. * * @return The number of outgoing edges of the node. */ U_32 getOutDegree() const {return (U_32)getOutEdges().size();} /** * Gets the number of incoming edges to the node. * * @return The number of incoming edges to the node. */ U_32 getInDegree() const {return (U_32)getInEdges().size();} /** * Checks whether the node has only one outgoing edge. * * @return TRUE if the node has only one outgoing edge; * otherwise, FALSE. */ bool hasOnlyOneSuccEdge() const {return getOutDegree() == 1;} /** * Checks whether the node has only one incoming edge. * * @return TRUE if the node has only one incoming edge; * otherwise, FALSE. */ bool hasOnlyOnePredEdge() const {return getInDegree() == 1;} /** * Checks whether the node has two or more outgoing edges. * * @return TRUE if the node has two or more outgoing edges; * otherwise, FALSE. */ bool hasTwoOrMoreSuccEdges() const {return getOutDegree() >= 2;} /** * Checks whether the node has two or more incoming edges. * * @return TRUE if the node has two or more incoming edges; * otherwise, FALSE. */ bool hasTwoOrMorePredEdges() const {return getInDegree() >= 2;} /** * Appends the instruction to the node instruction list after the * instBefore instruction. * If the instruction is a list, then the whole list is added. * * @param[in] newInst - a new instruction/instructions list to add * @param[in] instBefore - the location where to insert new instructions. * If instBefore is NULL, * new instructions are appended to the end of the * node list; otherwise, they are inserted right * after instBefore. */ void appendInst(CFGInst* newInst, CFGInst* instBefore = NULL); /** * Prepends the instruction to the node instruction list before the * instAfter instruction. * If the instruction is a list, then the whole list is added. * * @param[in] newInst - a new instruction/instructions list to add * @param[in] instAfter - the location where to insert new instructions. * If instAfter is NULL, new * instructions are prepended to the beginning of the * node list; otherwise, they are inserted right * before instBefore. */ void prependInst(CFGInst* newInst, CFGInst* instAfter = NULL); /** * Counts the number of instructions in the node. The complexity of * the algorithm is proportional to the number of instructions. * * @return The number of instructions in the node. */ U_32 getInstCount(bool ignoreLabels = true) const; /** * Checks whether not a single instruction is in the node. * * @param[in] ignoreLabels - tells whether to count label instructions * * @return TRUE not a single instruction is in the node. */ bool isEmpty(bool ignoreLabels = true) const {CFGInst* inst = getFirstInst(); return inst == NULL || (ignoreLabels && inst->isLabel() && inst->next() == NULL);} /** * Gets the first instruction in the node. * * @return The first instruction in the node; * NULL if the node is empty. */ CFGInst* getFirstInst() const {return instsHead->getNext() != instsHead ? (CFGInst*)instsHead->getNext() : NULL;} /** * Gets the last instruction in the node. * * @return The last instruction in the node; * NULL if the node is empty. */ CFGInst* getLastInst() const {return instsHead->getPrev() != instsHead ? (CFGInst*)instsHead->getPrev() : NULL;} /** * Gets the execution count of the node. Execution count of the node is * a number of times the code of this node was executed at run time. * This number can be the result of profiling of static estimation. * * @return The number of times the code of the given node was executed. */ double getExecCount() const {return execCount;} /** * Sets the execution count for the node. * * @param[in] val - a new execution count value */ void setExecCount(double val) {execCount = val;} /** * Gets the current node traversal number used by internal and external * algorithms to mark node as visited. * * @return The traversal number for the node. */ U_32 getTraversalNum() const {return traversalNumber;} /** * Sets a new traversal number of the node, usually * oldTraversalNumber + 1. * * @param[in] num - a new traversal number */ void setTraversalNum(U_32 num) {traversalNumber = num;} /** * Gets the second instruction in the node. * * @return The second instruction in the node; * NULL if the node is empty or has only one * instruction. */ CFGInst* getSecondInst() const {return isEmpty() ? NULL : getFirstInst()->next();} /** * Gets the label instruction. The label instruction is always the first * instruction in the node. Check additionally whether the first instruction * is a label one. * * @return The first instruction or NULL. * Checks whether the first instruction is a label one. */ CFGInst* getLabelInst() const {CFGInst* first = getFirstInst(); assert(first==NULL || first->isLabel()); return first;} /** * Gets bytecode offset of the first inst with bc-mapping in the node * * @return bytecode offset of the first inst with bc-mapping in the node */ uint16 getNodeStartBCOffset() const; /** * Gets bytecode offset of the last inst with bc-mapping in the node * * @return bytecode offset of the last inst with bc-mapping in the node */ uint16 getNodeEndBCOffset() const; protected: /** * The constructor of Node. * Initializes all instance fields with default values. * * @param[in] mm - the memory manager to use * @param[in] kind - the node kind */ Node(MemoryManager& mm, Kind kind); /** * Sets the node ID. * * @param[in] _id - a new node ID */ void setId(U_32 _id) {id = _id;} /** * Inserts the newInst instruction right after * the prev instruction. * Assigns the node to the newInst. */ void insertInst(CFGInst* prev, CFGInst* newInst); /// The unique ID of the node in CFG. U_32 id; /** * The depth-first number of the node in CFG. * It is updated every time CFG is ordered. */ U_32 dfNumber; /** * The pre-number of the node in CFG. * It is updated every time CFG is ordered. */ U_32 preNumber; /** * The post-number of the node in CFG. * It is updated every time CFG is ordered. */ U_32 postNumber; /** * The number of times the node was traversed by the * ordering algorithms. * It is updated every time CFG is ordered. */ U_32 traversalNumber; /// The type of the node. Kind kind; /** * The collection of all incoming edges to the node. * The order of edges in this collection if not specified. */ Edges inEdges; /** * The collection of all outgoing edges from the node. * The order of edges in this collection if not specified. */ Edges outEdges; /** * The stub for the node instructions list. * The first user's instruction in the node is the first instruction * after the instHead stub. * The last user's instruction in the node is the first instruction * before the instHead stub. */ CFGInst* instsHead; /// Profiling information. The number of times this node was executed. double execCount; }; /** * The factory class for nodes and edges. * Creates nodes and edges at ControlFlowGraph requests. * The default implementation of the given class creates default nodes * and edges of the Node and Edge classes. * To create custom Node and Edge subclasses,overload * the methods of the given factory class. */ class ControlFlowGraphFactory { public: ///The default constructor for the ControlFlowGraphFactory class. Does nothing. ControlFlowGraphFactory(){} ///The default destructor for the ControlFlowGraphFactory class. Does nothing. virtual ~ControlFlowGraphFactory(){} /** * Creates a new Edge of the specified kind using the memory manager as the * allocator. * * @param[in] mm - the memory manager for the newly created node * @param[in] kind - the kind of the newly created node * * @return A new specified node allocated on the memory manager. */ virtual Node* createNode(MemoryManager& mm, Node::Kind kind); /** * Creates a new Edge of the specified kind to connect nodes of * srcKind and dstKind kinds. * * @param[in] mm - the memory manager for the newly created edge * @param[in] srcKind - the kind of Source node for the edge * @param[in] dstKind - the kind of source Target for the edge * * @return A new edge allocated on the memory manager to be connected with * nodes of srcKind and dstKind kinds. */ virtual Edge* createEdge(MemoryManager& mm, Node::Kind srcKind, Node::Kind dstKind); }; /** * The base class for CFG. * The container class for nodes, edges, global states of nodes and edges and * related algorithms. */ class ControlFlowGraph { public: /** * Creates new CFG. * * @param[in] mm - the memory manager for CFG nodes, edges and internal data * @param[in] factory - the factory to create new nodes and edges * * If no factory is specified, the default factory implementation is used. */ ControlFlowGraph(MemoryManager& mm, ControlFlowGraphFactory* factory = NULL); virtual ~ControlFlowGraph(){}; /** * Gets a collection of all nodes in the graph. * Certain nodes in the collection can be unreachable. * The order of nodes is arbitrary. * * @return A collection of nodes in the control flow graph. * * @note All iterators to the collection become invalid when new nodes * are added or old ones deleted. */ const Nodes& getNodes() const {return nodes;} /** * Gets the unique Entry node. The given node dominates all other nodes in * the graph. * The Entry node has the Node::Kind_BlockNode kind. * * @return The Entry node. */ Node* getEntryNode() const {return entryNode;} /** * Sets the Entry node. The given node dominates all other nodes * in the graph. * The Entry node must be a block one. * * @param[in] e - a new Entry node */ void setEntryNode(Node* e) {assert(e!=NULL); entryNode = e; lastModifiedTraversalNumber = traversalNumber;} /** * Gets the unique Exit node. The given node postdominates all other nodes * in the graph except child nodes of infinite loops. * The Exit node has the Node::Kind_ExitNode kind. * * @return The Exit node. */ Node* getExitNode() const {return exitNode;} /** * Sets the Exit node. The given node postdominates all other * nodes in the graph except child nodes of infinite loops. * The Exit node has the Node::Kind_ExitNode kind. * * @return The Exit node. */ void setExitNode(Node* e) {assert(e!=NULL); exitNode = e; lastModifiedTraversalNumber = traversalNumber;} /** * Gets the unique block node that postdominates all nodes * in all paths that are non-dispatch exits from the method. * * @return The Return node of the graph. */ Node* getReturnNode() const {return returnNode; } /** * Sets the Return node for the graph. * The Return node is a block node that postdominates all * nodes in all paths that are non-dispatch exits from the method. * * @return The Return node of the graph. */ void setReturnNode(Node* node) {assert(returnNode==NULL); assert(node->isBlockNode()); returnNode = node;} /** * Gets the unique dispatch node that postdominates all nodes * in all paths that are dispatch exits from the method. * * @return The Unwind node of the graph. */ Node* getUnwindNode() const {return unwindNode;} /** * Sets the Unwind node for the graph. * The Unwind node is a dispatch node that postdominates all * nodes in all paths that are dispatch exits from the method. * * @return The Unwind node of the graph. */ void setUnwindNode(Node* node) {assert(node->isDispatchNode()); unwindNode = node;} /** * Gets the maximum node ID. * The given ID is incremented any time the node is added to the graph. * * @return The maximum node ID. */ U_32 getMaxNodeId() const {return nodeIDGenerator;} /** * Creates a new specified node. Add instruction to the node. * * @param[in] kind - the kind of the node * @param[in] inst - the instruction to add to the node instructions list * * @return A newly created node. */ Node* createNode(Node::Kind kind, CFGInst* inst = NULL); /** * Creates a new Block node and adds the instruction * to it. * * @param[in] inst - the instruction to add to the node instructions list * * @return A newly created node. */ Node* createBlockNode(CFGInst* inst = NULL) {return createNode(Node::Kind_Block, inst);} /** * Creates a new Dispatch node and adds the instruction * to it. * * @param[in] inst - the instruction to add to the node instructions list * * @return A newly created node. */ Node* createDispatchNode(CFGInst* inst = NULL) {return createNode(Node::Kind_Dispatch, inst);} /** * Creates a new Exit node and adds the instruction * to it. * * @param[in] inst - the instruction to add to the node instructions list * * @return A newly created node. */ Node* createExitNode(CFGInst* inst = NULL) {return createNode(Node::Kind_Exit, inst);} /** * Removes the node and all its incoming and outgoing edges from the graph. * * @param[in] node - a node to remove */ void removeNode(Node* node); /** * Gets the number of nodes in the graph that are reachable from the Entry node. * Orders nodes and updates traversal and ordering numbers of the graph and all * nodes if the graph has been modified from the last ordering. * * @return The number of reachable nodes in the graph. */ U_32 getNodeCount() { if(!hasValidOrdering()) orderNodes(); return nodeCount; } /** * Gets the cached postorder collection of nodes in the graph. * * @return The collection of nodes ordered in postorder. */ const Nodes& getNodesPostOrder() {if (!hasValidOrdering()) orderNodes(); return postOrderCache;} /** * Copies pointers to all nodes of the graph to the container. * * @param[in] container - a container to put node pointers to * * The container must provide the Insert(iterator * insertLocation, iterator start, iterator * end) method. */ template void getNodes(Container& container) { container.insert(container.begin(), nodes.begin(), nodes.end()); } /** * Copies post-ordered nodes sequence to the container. * If isForwarisForward is TRUE, the method starts * ordering the DFS algorithm from the Entry node. * If isForwarisForward is FALSE, the method starts * ordering the DFS algorithm from the Exit node. * * @param[in] container - the container to add nodes * @param[in] isForward - whether to start DFS ordering from the Entry * (TRUE) or Exit * (FALSE) node * * @note The container class must provide the push_back(Node*) * method. */ template void getNodesPostOrder(Container& container, bool isForward=true) { runDFS((Container*) NULL, &container, isForward); } /** * Copies pre-ordered nodes sequence to the container. * If isForwarisForward is TRUE, the method starts * ordering the DFS algorithm from the Entry node. * If isForwarisForward is FALSE, the method starts * ordering the DFS algorithm from the Exit node. * * @param[in] container - the container to add nodes * @param[in] isForward - whether to start DFS ordering from the Entry * (TRUE) or Exit * (FALSE) node * @note The container class must provide the push_back(Node*) * method. */ template void getNodesPreOrder(Container& container, bool isForward=true) { runDFS(&container, (Container*) NULL, isForward); } /** * Orders the nodes in the graph. * If isForward is TRUE, updates the * internal CFG collection of nodes and node df-numbers. * Affects nodes and graph traversal and ordering numbers. * * @param[in] isForward - whether to start DFS ordering from the Entry * (TRUE) or Exit * (FALSE) node * */ void orderNodes(bool isForward=true) { runDFS((Nodes*) NULL, (Nodes*) NULL, isForward); } /** * Creates a new edge from the Source node to the * Target one. * * @param[in] source - the Source or Tail * node for the edge * @param[in] target - the Target or Head * node for the edge * @param[in] edgeProb - the probability of the edge * * @return The newly created edge. */ Edge* addEdge(Node* source, Node* target, double edgeProb = 1.0); /** * Gets the maximum edge ID. * The given ID is incremented every time the edge is added to the graph. * * @return The maximum edge ID. */ U_32 getMaxEdgeId() const {return edgeIDGenerator;} /** * Removes the edge from CFG. Updates Source and * Target nodes. * Does not affect other edge probabilities. * * @param[in] edge - the edge to remove */ void removeEdge(Edge* edge); /** * Removes the edge connecting Source and * Target nodes. * Updates Source and Target nodes. Does not * affect other edge probabilities. * * @param[in] source - the Source node for the edge * @param[in] target - the Target node for the edge */ void removeEdge(Node* source, Node* target) {removeEdge(source->findTargetEdge(target));} /** * Removes the edge, creates a new one and connects it to * the newTarget node. * * @param[in] edge - the edge to change the target * @param[in] newTarget - a new Target node * @param[in] keepOldEdge - modify old or create a new edge * * @return The edge connecting the Source node of the * edge and the newTarget node. * * @note The removal of the old edge is needed * while inlining CFG: edge IDs must be renewed. */ Edge* replaceEdgeTarget(Edge* edge, Node *newTarget, bool keepOldEdge = false); /** * Checks if CFG is annotated with the edge profile information. * * @return TRUE if CFG was annotated with the edge profile. */ bool hasEdgeProfile() const {return annotatedWithEdgeProfile;} /** * Sets if CFG is annotated with the edge profile. * * @param[in] val - marks CFG as annotated if val is TRUE, * CFG is not annotated if val is FALSE. */ void setEdgeProfile(bool val) {annotatedWithEdgeProfile = val;} /** * Checks if the edge profile is consistent. * Checks only reachable nodes and recalculates postorder cache if needed. * * @param[in] checkEdgeProbs - enables edge probs consistency check. If for every * node the sum of the all outgoing edge probs * is equal to 1.0, the edge probs data is consistent. * * @param[in] checkExecCounts - enables exec counts consistency check. If for every * node the sum of exec counts of incoming edges is * equal to the node exec count, the exec count data * is consistent. * @param[in] doAssert - asserts if the consistency error is found. Useful * to position the debugger to the error. */ bool isEdgeProfileConsistent(bool checkEdgeProbs = true, bool checkExecCounts = true, bool doAssert=false); /** * Counts the execution counts of nodes using edge probabilities and execution * count of the Entry node. */ void smoothEdgeProfile(); /** * Gets the traversal number. * The traversal number is analogous to a monotonically increasing timestamp. * It is updated anytime an ordering traversal is performed on CFG. * If a modification was performed after an ordering, the ordering is invalid. * * @return The traversal number */ U_32 getTraversalNum() const {return traversalNumber;} /** * Sets the traversal number. * The traversal number is analogous to a monotonically increasing timestamp. * It is updated anytime an ordering traversal is performed on CFG. * If a modification was performed after an ordering, the ordering is invalid. * * @param[in] newTraversalNum - a new traversal number */ void setTraversalNum(U_32 newTraversalNum) {traversalNumber = newTraversalNum;} /** * The modification traversal number is the traversal number of the * last add/remove of a node/edge in the graph. * * @return The modification traversal number. */ U_32 getModificationTraversalNum() const { return lastModifiedTraversalNumber; } /** * The edge removal traversal number is the modification traversal number of * the last remove of an edge in the graph. * * @return The edge removal traversal number. */ U_32 getEdgeRemovalTraversalNum() const { return lastEdgeRemovalTraversalNumber; } /** * The ordering traversal number is the traversal number after the last depth * first ordering. Node pre/post numbers are valid, if * getOrderingTraversalNum() is greater than getModificationTraversalNum(). * * @return The ordering traversal number. */ U_32 getOrderingTraversalNum() const { return lastOrderingTraversalNumber; } /** * Checks if CFG nodes have valid ordering, that is there was no modification * in graph from the time of the last ordering. * * @return TRUE if ordering is valid; otherwise, FALSE. */ bool hasValidOrdering() const { return getOrderingTraversalNum() > getModificationTraversalNum(); } /** * Gets the memory manager used by CFG to allocate nodes and edges. * * @return The memory manager for given CFG. */ MemoryManager& getMemoryManager() const {return mm;} /** * Splits the Return node in CFG, that is creates a new * Block node before the Return node and retarget * all incoming edges from the Return node to a new * Block node. * After this method call the Return node has only one incoming * edge. * * @param[in] headerInst - the instruction to add to a new node * * @return The newly created node. */ Node* splitReturnNode(CFGInst* headerInst=NULL) {return splitNode(getReturnNode(), false, headerInst);} /** * Splits a node at a particular instruction, leaving the instruction in the * same node and moving all instructions before or after the instruction * to a newly created node. * * @param[in] inst - the place where to split the node * @param[in] splitAfter - indicates whether to split should appear after * TRUE or before * FLASE instruction * @param[in] keepDispatch - indicates if both nodes must have the same dispatch * as the Initial node had * If FLASE the Dispatch node * is moved to the node with a higher post-num. * * @return The newly created node. */ Node* splitNodeAtInstruction(CFGInst *inst, bool splitAfter, bool keepDispatch, CFGInst* headerInst); /** * Creates a new node and targets the edge to it. The old edge target is * connected with a new node by new edge after the given method call. * * @param[in] edge - the edge to splice * @param[in] inst - the instruction to add to a new node * @param[in] keepOldEdge - keep old edge and use it to connect source and new nodes * * @return The newly created node. */ Node* spliceBlockOnEdge(Edge* edge, CFGInst* inst = NULL, bool keepOldEdge=false); /** * Inlines inlineFG into this CFG after instAfter, * splits the Instruction node if needed. * Moves all nodes from inlineFG except the Exit * node to given CFG. * Relies on valid Return and Unwind nodes of * inlinedFG. * * @param[in] instAfter - the place to inline. inlinedFG is * inlined after this instruction * @param[in] inlineFG - the flow graph to inline. Must have valid unwind * and return nodes */ void spliceFlowGraphInline(CFGInst* instAfter, ControlFlowGraph& inlineFG); /** * Inlines inlineFG info given CFG retargeting the edge to the * inlinedFG's Entry node. * Moves all nodes from inlinedFG except the Exit * node to This CFG. * Relies on valid Return and Unwind nodes of the * inlinedFG. * * @param[in] edge - the edge to splice the inlined flow graph on. * @param[in] inlineFG - the flow graph to inline. Must have valid * Return and Unwind nodes. */ void spliceFlowGraphInline(Edge* edge, ControlFlowGraph& inlineFG); /** * Removes all critical edges from the graph. * Does not split exception edges unless the parameter is TRUE. * * @param[in] includeExceptionEdges - process exception edges if TRUE * @param[in] newNodes - all newly created nodes */ void splitCriticalEdges(bool includeExceptionEdges, Nodes* newNodes = NULL); /** * Moves instructions from one node to another. * * @param[in] fromNode - the node to move instructions from * @param[in] toNode - the node to move instructions to * @param[in] prepend - prepends instructions to a new node if TRUE; * appends instructions if FALSE */ void moveInstructions(Node* fromNode, Node* toNode, bool prepend); /** * Combines nodes from CFG that can be folded together. * * @param[in] skipEntry - does not process the Entry node * @param[in] mergeByDispatch - allows merging of nodes with the same dispatch * edge target */ void mergeAdjacentNodes(bool skipEntry = false, bool mergeByDispatch= false); /** * Combines blocks. * * @param[in] first - the first block to merge * @param[in] second - the second block to merger * @param[in] keepFirst - tells whether to keep the first or second block */ void mergeBlocks(Node* first, Node* second, bool keepFirst=true); /** * Removes all empty nodes from CFG. * * @param[in] preserveCriticalEdges - informs if to preserve critical edges * @param[in] removeEmptyCatchBlocks - allows the removal of empty catch blocks * if TRUE */ void purgeEmptyNodes(bool preserveCriticalEdges = false, bool removeEmptyCatchBlocks = false); /** * Removes all unreachable nodes from CFG. * If a path connects the node with the Entry node, the node is * reachable. */ void purgeUnreachableNodes() { purgeUnreachableNodes((Nodes*) NULL); } /** * Removes all unreachable nodes from CFG and adds them to the container. * * @param[in] container - the collection supports the push_back * method to store pointers to all removed nodes * */ template void purgeUnreachableNodes(Container& container) { purgeUnreachableNodes(&container);} /** * Gets the dominator tree. Updates the tree, if it is in the up-to-date state. * * @return The dominator tree; NULL if none dominator tree is * assigned to the given graph. */ DominatorTree* getDominatorTree() const {return domTree;} /** * Gets the post-dominator tree. Updates the tree, if it is in the up-to-date * state. * * @return The post-dominator tree; NULL if none post-dominator * tree is assigned to the given graph. */ DominatorTree* getPostDominatorTree() const {return postDomTree;} /** * Gets the loop tree. Updates the tree, if it is in the up-to-date state. * * @return The loop tree; NULL if none loop tree is * assigned to the given graph. */ LoopTree* getLoopTree() const {return loopTree;} /** * Assigns the dominator tree to the graph. * * param dom - the dominator tree assigned to the graph */ void setDominatorTree(DominatorTree* dom) {domTree = dom;} /** * Assigns the post-dominator tree to the graph. * * @param[in] dom - the post-dominator tree assigned to the graph */ void setPostDominatorTree(DominatorTree* dom) {domTree = dom;} /** * Assigns the loop tree to the graph. * * param dom - the loop tree assigned to the graph */ void setLoopTree(LoopTree* lt) {loopTree= lt;} protected: /** * Adds the node to the graph nodes list. * Assigns new ID to the node, increments the graph modification count. */ void addNode(Node* node); /** * Adds the edge to the graph and connects Source and * Target nodes with this edge. * Assigns a new edge ID to the edge, increments the graph modification * count. */ void addEdge(Node* source, Node* target, Edge* edge, double edgeProb); /** * Removes the node from the graph. * * @param[in] i - the location of the node in the graph node collection * @param[in] erase - informs whether to erase or just NULL the * pointer to the node in the collection */ void removeNode(Nodes::iterator i, bool erase); /** * Sets a new ID to the edge. */ void setNewEdgeId(Edge* edge) { edge->setId(edgeIDGenerator++); } /** * Moves all incoming edges from oldNode to * newNode. * Increments modification traversal number of the graph. */ void moveInEdges(Node* oldNode, Node* newNode); /** * Moves all outgoing edges from oldNode to * newNode. * Increments modification traversal number of the graph. */ void moveOutEdges(Node* oldNode, Node* newNode); /** * Removes duplicate incoming edges. */ void resetInEdges(Node* node); /** * Removes duplicate outgoing edges. */ void resetOutEdges(Node* node); /** * Splits the node: adds a new block before or after the node. * * @warning Low-level helper method. * @warning If newBlockAtEnd is TRUE, the given method does not * keep dispatch on the original block. * @warning Does not move instructions. */ Node* splitNode(Node* node, bool newBlockAtEnd, CFGInst* newBlockInst); /// Splits the edge and adds newBlockInst to a new node. Node* splitEdge(Edge* edge, CFGInst* newBlockInst, bool keepOldEdge); /// Checks whether the Source node can be merged with the Target node. bool isBlockMergeAllowed(Node* source, Node* target, bool allowMergeDispatch) const; /// Helper for public getNodesPre/PostOrder methods above. template void runDFS(Container* preOrderContainer, Container* postOrderContainer, bool isForward) { Node* startNode; traversalNumber++; if (isForward) { lastOrderingTraversalNumber = traversalNumber; postOrderCache.clear(); if (entryNode==NULL) { return; } startNode = entryNode; } else { if (exitNode==NULL) { return; } startNode = exitNode; } currentPreNumber = currentPostNumber = 0; getNodesDFS(preOrderContainer, postOrderContainer, startNode, isForward); assert(currentPreNumber == currentPostNumber); if (isForward) { nodeCount = currentPreNumber; } else { // getNodesDFS changes traversalNum for nodes. But traversalNum assumes direct traversal. // so drop the ordering number here to force CFG recompute ordering before using node->traversalNum values again lastOrderingTraversalNumber = lastModifiedTraversalNumber-1; } } /// Helper for public getNodesPre/PostOrder methods above. Warn: increment cfg traversal num before use. template void getNodesDFS(Container* preOrderContainer, Container* postOrderContainer, Node* node, bool isForward=true) { U_32 marked = traversalNumber; node->setTraversalNum(marked); if(isForward) { node->dfNumber = currentPreNumber; } node->preNumber = currentPreNumber++; if(preOrderContainer != NULL) { preOrderContainer->push_back(node); } Edges::const_iterator i = node->getEdges(isForward).begin(), iend = node->getEdges(isForward).end(); for(; i != iend; i++) { Edge* edge = *i; Node* succ = edge->getNode(isForward); if(succ->getTraversalNum() < marked) { getNodesDFS(preOrderContainer, postOrderContainer, succ, isForward); } } node->postNumber = currentPostNumber++; if (postOrderContainer != NULL) { postOrderContainer->push_back(node); } if (isForward) { postOrderCache.push_back(node); } } /// Removes all nodes unreachable from the entry. template void purgeUnreachableNodes(Container* container) { if(!hasValidOrdering()) { orderNodes(); } Nodes::iterator iter = nodes.begin(), end = nodes.end(); for(; iter != end;) { Nodes::iterator current = iter; Node* node = *iter; ++iter; if(node->traversalNumber < traversalNumber) { removeNode(current, false); if(container != NULL) { container->push_back(node); } } } nodes.erase(std::remove(nodes.begin(), nodes.end(), (Node*)NULL), nodes.end()); } /// The memory manager used by ControlFlowGraph to allocate its data. MemoryManager& mm; /// The factory used by ControlFlowGraph to create nodes and edges. ControlFlowGraphFactory* factory; /// The unique Entry node in ControlFlowGraph. Node* entryNode; /// The unique Return node in ControlFlowGraph. Node* returnNode; /// The unique Exit node in ControlFlowGraph. Node* exitNode; /// The unique Unwind node in ControlFlowGraph. Node* unwindNode; /// The collection of nodes. The order of nodes in the collection is not specified. Nodes nodes; /// The collection of postordered nodes, which is updated every time the graph is ordered. Nodes postOrderCache; /// The ID generator for nodes, which is incremented every time a new node is added to the graph. U_32 nodeIDGenerator; /// The ID generator for edges, which is incremented every time a new edge is added to the graph. U_32 edgeIDGenerator; /// The number of reachable nodes in the graph, which is updated every time the graph is ordered. U_32 nodeCount; /// The last graph traversal number used to track graph modifications. U_32 traversalNumber; /// The given field is assigned to the traversalNumber value every time the graph is modified. U_32 lastModifiedTraversalNumber; /// The given field is assigned to the traversalNumber value every time the graph is ordered. U_32 lastOrderingTraversalNumber; /// The given field is assigned to the traversalNumber value every time any edge is removed from the graph. U_32 lastEdgeRemovalTraversalNumber; /// The given field is assigned to the traversalNumber value every time the profile information is recalculated. U_32 lastProfileUpdateTraversalNumber; /// The temporary field used by ordering algorithms. U_32 currentPreNumber; /// The temporary field used by ordering algorithms. U_32 currentPostNumber; /// Tells whether the graph is annotated with the edge profile. bool annotatedWithEdgeProfile; /// The dominator tree for the graph. NULL if no dominator tree was set. DominatorTree* domTree; /// The post-dominator tree for the graph. NULL if no post-dominator tree was set. DominatorTree* postDomTree; /// The loop tree for the graph. NULL if no loop tree was set. LoopTree* loopTree; }; } //namespace Jitrino #endif // _CONTROLFLOWGRAPH_