| /* |
| * 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 |
| * |
| */ |
| |
| #include "ControlFlowGraph.h" |
| #include "LoopTree.h" //required for edge profile smoothing |
| #include <algorithm> |
| |
| namespace Jitrino { |
| |
| ////////////////////////////////////////////////////////////////////////// |
| // ControlFlowGraphFactory methods |
| Node* ControlFlowGraphFactory::createNode(MemoryManager& mm, Node::Kind kind) { |
| return new (mm) Node(mm, kind); |
| } |
| |
| Edge* ControlFlowGraphFactory::createEdge(MemoryManager& mm, Node::Kind srcKind, Node::Kind dstKind) { |
| return new (mm) Edge(); |
| } |
| |
| |
| ////////////////////////////////////////////////////////////////////////// |
| // Edge methods |
| |
| Edge::Kind Edge::getKind() const { |
| Edge::Kind kind = Edge::Kind_Unconditional; |
| if (source->isBlockNode()) { |
| if (target->isBlockNode()) { |
| if (source->getOutDegree() > 1) { |
| CFGInst* inst = source->getLastInst(); |
| if (inst!=NULL) { |
| kind = inst->getEdgeKind(this); |
| } else { //empty node with dispatch and unconditional edges. B->B edge is unconditional |
| #ifdef _DEBUG //do some checks |
| assert(source->getOutDegree() == 2); |
| const Edges& outEdges = source->getOutEdges(); |
| Edge* secondEdge = outEdges.front() == this ? outEdges.back() : outEdges.front(); |
| assert(secondEdge->getTargetNode()->isDispatchNode()); |
| #endif |
| //edge kind stays unconditional |
| } |
| } |
| } else if (target->isDispatchNode()) { |
| kind = Edge::Kind_Dispatch; |
| } else { |
| assert(target->isExitNode());//kind is unconditional |
| } |
| } else { |
| assert(source->isDispatchNode()); |
| if (target->isDispatchNode() || target->isExitNode()) { |
| kind = Edge::Kind_Dispatch; |
| } else { |
| assert(target->isBlockNode()); |
| kind = Edge::Kind_Catch; |
| } |
| } |
| return kind; |
| } |
| |
| ////////////////////////////////////////////////////////////////////////// |
| // Node methods |
| |
| class HeadInst : public CFGInst { |
| public: |
| HeadInst(Node* _node) {node = _node;} |
| // must never be called on head inst |
| virtual Edge::Kind getEdgeKind(const Edge* edge) const {assert(false); return Edge::Kind_Unconditional;} |
| }; |
| |
| Node::Node(MemoryManager& mm, Kind _kind) |
| : id(MAX_UINT32), dfNumber(0), preNumber(0), postNumber(0), traversalNumber(0), |
| kind(_kind), inEdges(mm), outEdges(mm), instsHead(NULL), execCount(0) |
| { |
| instsHead = new (mm) HeadInst(this); |
| } |
| |
| Edge* Node::getOutEdge(Edge::Kind edgeKind) const { |
| for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) { |
| Edge* edge = *ite; |
| if (edge->getKind() == edgeKind) { |
| return edge; |
| } |
| } |
| return NULL; |
| } |
| |
| |
| Edge* Node::findEdge(bool isForward, const Node* node) const { |
| const Edges& edges = getEdges(isForward); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* edge = *ite; |
| if (edge->getNode(isForward) == node) { |
| return edge; |
| } |
| } |
| return NULL; |
| } |
| |
| |
| // appends inst to the end of node list. |
| void Node::appendInst(CFGInst* newInst, CFGInst* instAfter) { |
| if (instAfter==NULL) { |
| newInst->insertBefore(instsHead); |
| } else { |
| assert(instAfter->getNode() == this); |
| newInst->insertAfter(instAfter); |
| } |
| |
| } |
| |
| // appends inst to the beginning of node list. Checks "block header critical inst" property |
| void Node::prependInst(CFGInst* newInst, CFGInst* instBefore) { |
| if (instBefore==NULL) { |
| instBefore = instsHead; |
| for (CFGInst* inst = getFirstInst(); inst!=NULL; inst = inst->next()) { |
| if (inst->isLabel()) { |
| continue; |
| } |
| if (newInst->isHeaderCriticalInst() || !inst->isHeaderCriticalInst()) { |
| instBefore = inst; |
| break; |
| } |
| } |
| } |
| assert(instBefore->getNode() == this); |
| newInst->insertBefore(instBefore); |
| } |
| |
| void Node::insertInst(CFGInst* prev, CFGInst* newInst) { |
| #ifdef _DEBUG |
| assert(newInst->getNode() == NULL); |
| if (newInst->isHeaderCriticalInst()) { //check prev inst is also critical |
| if (prev != instsHead) { //check only if newInst will not be the first |
| CFGInst* prevInst = (CFGInst*)prev; |
| assert(prevInst->isHeaderCriticalInst()); |
| assert(!newInst->isLabel()); //label must be the first |
| } |
| } else { //check next inst is not critical |
| Dlink* nextLink = prev->getNext(); |
| if (nextLink!=instsHead) {//check only if newInst will not be the last |
| CFGInst* nextInst = (CFGInst*)nextLink; |
| assert(!nextInst->isHeaderCriticalInst()); |
| } |
| } |
| #endif |
| ((Dlink*)newInst)->insertAfter(prev); |
| newInst->node = this; |
| } |
| |
| |
| U_32 Node::getInstCount(bool ignoreLabels) const { |
| U_32 count = 0; |
| CFGInst* first = getFirstInst(); |
| while (ignoreLabels && first!=NULL && first->isLabel()) { |
| first = first->next(); |
| } |
| for (CFGInst* inst = first; inst!=NULL; inst = inst->next()) { |
| count++; |
| } |
| return count; |
| } |
| |
| Edge* Node::findEdgeTo(bool isForward, Node* node) const { |
| const Edges& edges = getEdges(isForward); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* edge = *ite; |
| if (edge->getNode(isForward) == node) { |
| return edge; |
| } |
| } |
| return NULL; |
| |
| } |
| |
| uint16 Node::getNodeStartBCOffset() const { |
| if (!isBlockNode()) { |
| return ILLEGAL_BC_MAPPING_VALUE; |
| } |
| CFGInst* inst = getFirstInst(); |
| while (inst!=NULL && inst->getBCOffset()==ILLEGAL_BC_MAPPING_VALUE) { |
| inst = inst->next(); |
| } |
| return inst==NULL ? ILLEGAL_BC_MAPPING_VALUE : inst->getBCOffset(); |
| } |
| |
| uint16 Node::getNodeEndBCOffset() const { |
| if (!isBlockNode()) { |
| return ILLEGAL_BC_MAPPING_VALUE; |
| } |
| CFGInst* inst = getLastInst(); |
| while (inst!=NULL && inst->getBCOffset()==ILLEGAL_BC_MAPPING_VALUE) { |
| inst = inst->prev(); |
| } |
| return inst==NULL ? ILLEGAL_BC_MAPPING_VALUE : inst->getBCOffset(); |
| } |
| |
| |
| |
| ////////////////////////////////////////////////////////////////////////// |
| // CFG methods |
| |
| ControlFlowGraph::ControlFlowGraph(MemoryManager& _mm, ControlFlowGraphFactory* _factory) |
| : mm (_mm), factory(_factory), entryNode (NULL), returnNode(NULL), exitNode(NULL), unwindNode(NULL), |
| nodes(_mm), postOrderCache(_mm), nodeIDGenerator(0), edgeIDGenerator(0), nodeCount(0), |
| traversalNumber(0), lastModifiedTraversalNumber(0), lastOrderingTraversalNumber(0), |
| lastEdgeRemovalTraversalNumber(0), lastProfileUpdateTraversalNumber(0), currentPreNumber(0), currentPostNumber(0), |
| annotatedWithEdgeProfile(false), domTree(NULL), postDomTree(NULL), loopTree(NULL) |
| { |
| if (factory == NULL) { //use default factory |
| factory = new (mm) ControlFlowGraphFactory(); |
| } |
| } |
| |
| Node* ControlFlowGraph::createNode(Node::Kind kind, CFGInst* inst) { |
| Node* node = factory->createNode(mm, kind); |
| addNode(node); |
| if (inst!=NULL) { |
| node->appendInst(inst); |
| } |
| return node; |
| } |
| |
| |
| void ControlFlowGraph::removeNode(Node* node) { |
| removeNode(std::find(nodes.begin(), nodes.end(), node), true); |
| } |
| |
| void ControlFlowGraph::removeNode(Nodes::iterator pos, bool erase) { |
| Node* node = *pos; |
| |
| if (node == entryNode) { |
| entryNode=NULL; |
| } |
| if (node == returnNode) { |
| returnNode = NULL; |
| } else if(node == unwindNode) { |
| unwindNode = NULL; |
| } else if (node == exitNode) { |
| exitNode = NULL; |
| } |
| |
| // Remove incident edges |
| while (!node->inEdges.empty()) { |
| Edge* edge = node->inEdges.front(); |
| assert(edge->getTargetNode() == node); |
| removeEdge(edge); |
| } |
| |
| while (!node->outEdges.empty()) { |
| Edge* edge = node->outEdges.front(); |
| assert(edge->getSourceNode() == node); |
| removeEdge(edge); |
| } |
| |
| // Erase the node itself |
| if (erase) { |
| *pos = *nodes.rbegin(); |
| nodes.pop_back(); |
| } else { |
| *pos = NULL; |
| } |
| |
| // Mark the graph modified. |
| lastModifiedTraversalNumber = traversalNumber; |
| } |
| |
| Edge* ControlFlowGraph::addEdge(Node* source, Node* target, double edgeProb) { |
| assert(target!=entryNode); |
| assert(source!=exitNode); |
| assert (source->findTargetEdge(target) == NULL); |
| Edge* edge = factory->createEdge(mm, source->getKind(), target->getKind()); |
| addEdge(source, target, edge, edgeProb); |
| return edge; |
| } |
| |
| void ControlFlowGraph::addEdge(Node* source, Node* target, Edge* edge, double edgeProb) { |
| // Set ID |
| edge->setId(edgeIDGenerator); |
| edgeIDGenerator++; |
| |
| // Out edge for source node |
| edge->source = source; |
| source->outEdges.push_back(edge); |
| |
| // In edge for target node |
| edge->target = target; |
| target->inEdges.push_back(edge); |
| |
| edge->setEdgeProb(edgeProb); |
| |
| // Mark the graph modified. |
| lastModifiedTraversalNumber = traversalNumber; |
| } |
| |
| |
| void ControlFlowGraph::removeEdge(Edge* edge) { |
| // Remove out edge from source node |
| Node* source = edge->getSourceNode(); |
| Edges& outEdges = source->outEdges; |
| outEdges.erase(std::remove(outEdges.begin(), outEdges.end(), edge)); |
| |
| // Remove in edge from target node |
| Node* target = edge->getTargetNode(); |
| Edges& inEdges = target->inEdges; |
| inEdges.erase(std::remove(inEdges.begin(), inEdges.end(), edge)); |
| |
| // Mark the graph modified. |
| lastModifiedTraversalNumber = traversalNumber; |
| lastEdgeRemovalTraversalNumber = traversalNumber; |
| } |
| |
| Edge* ControlFlowGraph::replaceEdgeTarget(Edge* edge, Node* newTarget, bool keepOldBody) { |
| Node* source = edge->getSourceNode(); |
| Node* oldTarget = edge->getTargetNode(); |
| CFGInst* lastInst = source->getLastInst(); |
| |
| Edge* newEdge = NULL; |
| if (keepOldBody) { |
| edge->target = newTarget; |
| newTarget->inEdges.push_back(edge); |
| Edges& oldInEdges = oldTarget->inEdges; |
| oldInEdges.erase(std::remove(oldInEdges.begin(), oldInEdges.end(), edge)); |
| newEdge = edge; |
| // Mark the graph modified. |
| lastModifiedTraversalNumber = traversalNumber; |
| } else { |
| removeEdge(edge); |
| newEdge = addEdge(source, newTarget); |
| } |
| if (lastInst!=NULL) { |
| lastInst->updateControlTransferInst(oldTarget, newTarget); |
| } |
| return newEdge; |
| } |
| |
| |
| #define PROFILE_ERROR_ALLOWED 0.000000001 |
| #define ABS(a) (((a) > (0)) ? (a) : -(a)) |
| |
| |
| // Check the profile consistency of the CFG. |
| // Return true if the profile is consistent. Otherwise, return false. |
| bool ControlFlowGraph::isEdgeProfileConsistent(bool checkEdgeProbs, bool checkExecCounts, bool doAssertForClient) { |
| assert(hasEdgeProfile()); |
| bool profileIsUptodate= lastProfileUpdateTraversalNumber > getModificationTraversalNum(); |
| #ifndef _DEBUG |
| if (profileIsUptodate) { |
| return true; |
| } |
| #else |
| //do self test in debug version |
| bool doAssert = profileIsUptodate || doAssertForClient; |
| #endif |
| |
| const Nodes& postOrdered = getNodesPostOrder(); |
| for (Nodes::const_iterator it = postOrdered.begin(), end = postOrdered.end(); it!=end; ++it) { |
| Node* node = *it; |
| if (checkEdgeProbs) { |
| const Edges& outEdges = node->getOutEdges(); |
| if (!outEdges.empty()) { |
| double probSum = 0; |
| for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) { |
| Edge* edge = *ite; |
| double prob = edge->getEdgeProb(); |
| if (prob <= 0 || prob > 1) { |
| assert(doAssert?false:true); |
| return false; |
| } |
| probSum+=prob; |
| } |
| if (ABS(probSum-1) > PROFILE_ERROR_ALLOWED) { |
| assert(doAssert?false:true); |
| return false; |
| } |
| } |
| } |
| if (checkExecCounts) { |
| const Edges& inEdges = node->getInEdges(); |
| bool hasInfiniteLoops = false; |
| if (!inEdges.empty()) { |
| double freqSum = 0; |
| for (Edges::const_iterator ite = inEdges.begin(), ende = inEdges.end(); ite!=ende; ++ite) { |
| Edge* edge = *ite; |
| Node* sourceNode = edge->getSourceNode(); |
| double freq = edge->getEdgeProb() * sourceNode->getExecCount(); |
| if (sourceNode->getTraversalNum()!=node->getTraversalNum()) { |
| freq = 0; |
| } |
| if (freq <=0) { |
| assert(doAssert?false:true); |
| return false; |
| } |
| freqSum+=freq; |
| } |
| if (freqSum <=0 ) { |
| assert(doAssert?false:true); |
| return false; |
| } |
| double nodeFreq = node->getExecCount(); |
| if (nodeFreq > 1/PROFILE_ERROR_ALLOWED) { |
| hasInfiniteLoops = true; |
| } else if (ABS(nodeFreq / freqSum - 1) >= PROFILE_ERROR_ALLOWED) { |
| assert(doAssert?false:true); |
| return false; |
| } |
| } |
| if (!hasInfiniteLoops && exitNode!=NULL) { |
| double exitFreq = exitNode->getExecCount(); |
| double entryFreq = entryNode->getExecCount(); |
| bool ok = ABS(exitFreq - entryFreq) < PROFILE_ERROR_ALLOWED * entryFreq; |
| if (!ok) { |
| assert(doAssert ? false : true); |
| return false; |
| } |
| } |
| } |
| } |
| if (!profileIsUptodate && checkEdgeProbs && checkExecCounts) { |
| lastProfileUpdateTraversalNumber = getTraversalNum(); |
| } |
| return true; |
| } |
| |
| // this utility splits a node at a particular instruction, leaving the instruction in the |
| // same node and moving all insts (before inst : splitAfter=false/after inst : splitAfter=true |
| // to the newly created node |
| // returns the new node created |
| Node* ControlFlowGraph::splitNodeAtInstruction(CFGInst *inst, bool splitAfter, bool keepDispatch, CFGInst* labelInst) { |
| Node *node = inst->getNode(); |
| Node* dispatchNode = keepDispatch ? node->getExceptionEdgeTarget() : NULL; |
| Node* newNode = splitNode(node, true, labelInst); |
| if (inst == node->getLastInst()) { |
| assert(!splitAfter || (node->getOutDegree() == 1 && node->getUnconditionalEdge()!=NULL) |
| || (node->getOutDegree()==2 && node->getExceptionEdgeTarget()!=NULL)); |
| } |
| |
| //keeping dispatch node is useful for extended basis blocks |
| if (keepDispatch && dispatchNode!=NULL) { |
| assert(node->getExceptionEdgeTarget() == NULL); |
| addEdge(node, dispatchNode, 0); |
| } |
| |
| // now move the instructions |
| for (CFGInst *ins = splitAfter ? inst->next() : inst; ins != NULL; ) { |
| CFGInst *nextins = ins->next(); |
| ins->unlink(); |
| newNode->appendInst(ins); |
| ins = nextins; |
| } |
| newNode->setExecCount(node->getExecCount()); |
| node->findTargetEdge(newNode)->setEdgeProb(1.0); |
| return newNode; |
| } |
| |
| // Splice a new empty block on the CFG edge. |
| Node* ControlFlowGraph::spliceBlockOnEdge(Edge* edge, CFGInst* inst, bool keepOldEdge) { |
| Node* source = edge->getSourceNode(); |
| double edgeProb = edge->getEdgeProb(); |
| double edgeFreq = source->getExecCount()*edgeProb; |
| |
| // Split the edge |
| Node* split = splitEdge(edge, inst, keepOldEdge); |
| split->setExecCount(edgeFreq); |
| |
| // Set the incoming edge probability |
| assert(split->getInDegree() == 1); |
| split->getInEdges().front()->setEdgeProb(edgeProb); |
| |
| // Set the outgoing edge probability |
| assert(split->getOutDegree() == 1); |
| split->getOutEdges().front()->setEdgeProb(1.0); |
| |
| return split; |
| } |
| |
| |
| void ControlFlowGraph::splitCriticalEdges(bool includeExceptionEdges, Nodes* newNodes) { |
| // go backwards through collection so appending won't hurt us. |
| Nodes::reverse_iterator iter = nodes.rbegin(), end = nodes.rend(); |
| for (int idx = (int)nodes.size(); --idx<=0;) { |
| Node* target = nodes[idx]; |
| // exception edges go to a dispatch node. |
| // only look at nodes with multiple in edges. |
| if (target->isDispatchNode() || includeExceptionEdges) { |
| restart: |
| if (target->getInDegree() > 1) { |
| Edges& inEdges = target->inEdges; |
| Edges::iterator iterEdge = inEdges.begin(), endEdge = inEdges.end(); |
| for (; iterEdge != endEdge; ++iterEdge) { |
| Edge* thisEdge = *iterEdge; |
| Node* source = thisEdge->getSourceNode(); |
| if ((source->getOutDegree() > 1) && (includeExceptionEdges || !source->isDispatchNode())) { |
| // it's a critical edge, split it |
| Node* newNode = splitEdge(thisEdge, NULL, false); //TODO: keep old edge? |
| if (newNodes) { |
| newNodes->push_back(newNode); |
| } |
| goto restart; |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| |
| bool ControlFlowGraph::isBlockMergeAllowed(Node* source, Node* target, bool allowMergeDispatch) const { |
| assert(source->isBlockNode() && target->isBlockNode()); |
| if (target == returnNode) { |
| return false; |
| } |
| if (source->getUnconditionalEdgeTarget()!=target) { |
| return false; |
| } |
| if (target->getInDegree()!=1 || source->getOutDegree() > 2) { |
| return false; |
| } |
| |
| Node* sourceDispatch = source->getExceptionEdgeTarget(); |
| Node* targetDispatch = target->getExceptionEdgeTarget(); |
| |
| //check if there is no problem with header critical insts |
| if (source->getLastInst()!=NULL && !source->getLastInst()->isHeaderCriticalInst()) { |
| //we can't allow target to have critical insts except label |
| CFGInst* inst = target->getFirstInst(); |
| inst = inst!=NULL?(inst->isLabel() ? inst->next() : inst) : NULL; |
| if (inst!=NULL && inst->isHeaderCriticalInst()) { |
| return false; |
| } |
| } |
| |
| if (source->getOutDegree() == 2 && sourceDispatch == 0) { |
| return false; // 2 uncond edges, e.g. indirect jumps |
| } |
| |
| if (!allowMergeDispatch) { |
| return sourceDispatch==NULL && targetDispatch==NULL; |
| } |
| |
| bool allowMergeByDispatch = sourceDispatch == targetDispatch |
| || (sourceDispatch == unwindNode && targetDispatch == NULL) |
| || (sourceDispatch == NULL && targetDispatch == unwindNode); |
| |
| return allowMergeByDispatch; |
| } |
| |
| |
| void ControlFlowGraph::mergeBlocks(Node* source, Node* target, bool keepFirst) { |
| assert(isBlockMergeAllowed(source, target, true)); |
| |
| Edge* edge = target->inEdges.front(); |
| assert(edge->getSourceNode() == source); |
| removeEdge(edge); |
| |
| if(keepFirst) { |
| // Merge second block into first |
| moveInstructions(target, source, false); |
| moveOutEdges(target, source); |
| removeNode(target); |
| } else { |
| // Merge first block into second |
| moveInstructions(source, target, true); |
| moveInEdges(source, target); |
| removeNode(source); |
| } |
| } |
| |
| void ControlFlowGraph::mergeAdjacentNodes(bool skipEntry, bool mergeByDispatch) { |
| for(U_32 idx = 0; idx < nodes.size(); idx++) { |
| Node* node = nodes[idx]; |
| if (node->isBlockNode() && (!skipEntry || node!=entryNode)) { |
| Node* succ = node->getUnconditionalEdgeTarget(); |
| if (succ!=NULL && succ->getInDegree() == 1 && !succ->isExitNode()) { |
| if (isBlockMergeAllowed(node, succ, mergeByDispatch)){ |
| mergeBlocks(node, succ); |
| idx--; |
| } |
| } |
| } else if (node->isDispatchNode()) { |
| if (node->getOutDegree() == 1 && node->isEmpty()) { |
| Node* succ = node->getOutEdges().front()->getTargetNode(); |
| if (succ->isDispatchNode()) { |
| // This dispatch has no handlers. |
| // Forward edges to this dispatch node to the successor. |
| moveInstructions(node, succ, true); |
| moveInEdges(node, succ); |
| removeNode(nodes.begin() + idx, true); |
| idx--; |
| } |
| } |
| } |
| } |
| } |
| |
| |
| void ControlFlowGraph::purgeEmptyNodes(bool preserveCriticalEdges, bool removeEmptyCatchBlocks) { |
| for(Nodes::iterator it = nodes.begin(),end = nodes.end(); it != end; ++it) { |
| Node* node = *it; |
| if(node->isBlockNode() && node->isEmpty()) { |
| // Preserve entry node |
| if(node == getEntryNode() || node == getReturnNode() || (!removeEmptyCatchBlocks && node->isCatchBlock())) { |
| continue; |
| } |
| // Node must have one unconditional successor if it is empty. |
| assert(node->getOutDegree() == 1 || (node->getOutDegree()==2 && node->getExceptionEdge()!=NULL)); |
| Node* succ = node->getUnconditionalEdgeTarget(); |
| assert(succ->isBlockNode() || (succ->isExitNode() && getReturnNode() == NULL)); //cfg without special support for return node... |
| if(succ == node) { |
| // This is an empty infinite loop. |
| continue; |
| } |
| |
| // Preserve this node if it breaks a critical edge if requested. |
| bool preserve = false; |
| if(preserveCriticalEdges && succ->getInDegree() > 1) { |
| // Preserve this block if any predecessors have multiple out edges. |
| Edges::const_iterator eiter; |
| for(eiter = node->getInEdges().begin(); !preserve && eiter != node->getInEdges().end(); ++eiter) { |
| if((*eiter)->getSourceNode()->getOutDegree() > 1) |
| // This node breaks a critical edge. |
| preserve = true; |
| } |
| } |
| |
| if(!preserve) { |
| moveInEdges(node, succ); |
| removeNode(it, false); |
| } |
| } |
| } |
| nodes.erase(std::remove(nodes.begin(), nodes.end(), (Node*)NULL), nodes.end()); |
| } |
| |
| void ControlFlowGraph::addNode(Node* node) { |
| // Set ID |
| node->setId(nodeIDGenerator); |
| nodeIDGenerator++; |
| |
| // Add node |
| nodes.push_back(node); |
| |
| // Reset node traversal number |
| node->traversalNumber = 0; |
| |
| // Mark the graph modified. |
| lastModifiedTraversalNumber = traversalNumber; |
| } |
| |
| |
| // Splice inlineFG into this CFG. |
| void ControlFlowGraph::spliceFlowGraphInline(Edge* edge, ControlFlowGraph& inlineFG) { |
| assert(!edge->isDispatchEdge() && !edge->isCatchEdge()); |
| |
| Node* nodeBeforeEntry = edge->getSourceNode(); |
| Node* nodeAfterReturn = edge->getTargetNode(); |
| Node* dispatchNode = nodeBeforeEntry->getExceptionEdgeTarget(); |
| |
| Node* inlineEntryNode = inlineFG.getEntryNode(); |
| Node* inlineReturnNode = inlineFG.getReturnNode(); |
| Node* inlineUnwindNode = inlineFG.getUnwindNode(); |
| Node* inlineExitNode = inlineFG.getExitNode(); |
| |
| bool returnSeen = false; |
| bool unwindSeen = false; |
| |
| |
| // Add nodes to CFG |
| assert(&getMemoryManager() == &inlineFG.getMemoryManager()); |
| const Nodes& inlineNodes = inlineFG.getNodes(); |
| for(Nodes::const_iterator i = inlineNodes.begin(), end = inlineNodes.end(); i != end; ++i) { |
| Node* n = *i; |
| if (n != inlineExitNode) { |
| addNode(n); |
| const Edges& oEdges = n->getOutEdges(); |
| Edges::const_iterator e; |
| for(e = oEdges.begin(); e != oEdges.end(); ++e) { |
| setNewEdgeId(*e); |
| } |
| if (n == inlineReturnNode) { |
| returnSeen = true; |
| } else if (n == inlineUnwindNode) { |
| unwindSeen = true; |
| } |
| } |
| |
| } |
| |
| // Connect nodes. |
| replaceEdgeTarget(edge, inlineEntryNode); |
| if(returnSeen) { |
| removeEdge(inlineReturnNode, inlineExitNode); |
| addEdge(inlineReturnNode, nodeAfterReturn, 1); |
| } |
| if(unwindSeen) { |
| removeEdge(inlineUnwindNode, inlineExitNode); |
| if (dispatchNode == NULL) { |
| dispatchNode = getUnwindNode(); |
| } |
| assert(dispatchNode != NULL); |
| addEdge(inlineUnwindNode, dispatchNode, 1); |
| } |
| } |
| |
| |
| void ControlFlowGraph::spliceFlowGraphInline(CFGInst* instAfter, ControlFlowGraph& inlineFG) { |
| Node* node = instAfter->getNode(); |
| Edge* edgeToInlined = NULL; |
| if (node->getLastInst() == instAfter) { |
| edgeToInlined = node->getUnconditionalEdge(); |
| } else {//WARN: no label inst created -> possible problems if method is used in HLO |
| Node* newBlock = splitNodeAtInstruction(instAfter, true, false, NULL); |
| assert(newBlock->getInDegree() == 1); |
| edgeToInlined = newBlock->getInEdges().front(); |
| } |
| assert(edgeToInlined!=NULL); |
| spliceFlowGraphInline(edgeToInlined, inlineFG); |
| } |
| |
| |
| void ControlFlowGraph::moveInEdges(Node* oldNode, Node* newNode) { |
| assert(oldNode != newNode); |
| assert(oldNode->getKind() == newNode->getKind() || (getReturnNode()==NULL && newNode->isExitNode())); |
| Edges& oldIns = oldNode->inEdges; |
| Edges& newIns = newNode->inEdges; |
| newIns.insert(newIns.begin(), oldIns.begin(), oldIns.end()); |
| oldIns.clear(); |
| // Reset edge pointers and update branch instructions. |
| resetInEdges(newNode); |
| assert(oldNode->getInDegree() == 0); |
| |
| // Mark the graph modified. |
| lastModifiedTraversalNumber = traversalNumber; |
| } |
| |
| void |
| ControlFlowGraph::moveOutEdges(Node* oldNode, Node* newNode) { |
| assert(oldNode->getKind() == newNode->getKind()); |
| Edges& oldOuts = oldNode->outEdges; |
| Edges& newOuts = newNode->outEdges; |
| newOuts.insert(newOuts.end(), oldOuts.begin(), oldOuts.end()); |
| oldOuts.clear(); |
| resetOutEdges(newNode); |
| assert(oldNode->getOutDegree() == 0); |
| |
| // Mark the graph modified. |
| lastModifiedTraversalNumber = traversalNumber; |
| } |
| |
| |
| void ControlFlowGraph::resetInEdges(Node* node) { |
| Edges& edges = node->inEdges; |
| for(int i=(int)edges.size(); --i>=0;) { |
| Edge* edge = edges[i]; |
| // The old successor; node is the new successor |
| Node* old = edge->getTargetNode(); |
| if(old != node) { |
| Node* pred = edge->getSourceNode(); |
| // Check if another edge already goes to node. . |
| bool redundant = (pred->findTargetEdge(node) != NULL); |
| // Set this edge to point to node. Note, we do this even if the |
| // edge is to be deleted. removeEdge only works if the edge |
| // is well-formed. |
| edge->target = node; |
| // Update control transfer instruction in source. |
| CFGInst* lastInst = pred->getLastInst(); |
| if(pred->isBlockNode() && lastInst!=NULL) { |
| lastInst->updateControlTransferInst(old, node); |
| } |
| if(redundant) { |
| // Edge is redundant - eliminate. |
| if(pred->getOutDegree() == 2 || (pred->getOutDegree()==3 && pred->getExceptionEdge()!=NULL)) { |
| // Pred already has edge to node and succ, and no other successors. |
| // We can eliminate the branch and the edge to succ. |
| // Another case is branch+exception for extended form |
| if(pred->isBlockNode()) { |
| lastInst->removeRedundantBranch(); |
| } |
| } |
| removeEdge(edge); |
| } |
| } |
| } |
| } |
| |
| void ControlFlowGraph::resetOutEdges(Node* node) { |
| Edges& edges = node->outEdges; |
| for(int i=(int)edges.size(); --i>=0;) { |
| Edge* edge = edges[i]; |
| // The old predecessor; node is the new predecessor |
| Node* old = edge->getSourceNode(); |
| if(old != node) { |
| Node* succ = edge->getTargetNode(); |
| // Check if another edge already comes from node. |
| bool redundant = (succ->findSourceEdge(node) != NULL); |
| // Set this edge to point to node. Note, we do this even if the |
| // edge is to be deleted. removeEdge only works if the edge |
| // is well-formed. |
| edge->source = node; |
| if(redundant) { |
| // Edge is redundant - eliminate. |
| removeEdge(edge); |
| } |
| } |
| } |
| } |
| |
| Node* ControlFlowGraph::splitNode(Node* node, bool newBlockAtEnd, CFGInst* inst) { |
| assert(node->isBlockNode()); |
| Node* newNode = createBlockNode(inst); |
| if(newBlockAtEnd) { |
| // move out edges |
| moveOutEdges(node, newNode); |
| addEdge(node, newNode); |
| } else { // new block at beginning |
| // move in edges |
| moveInEdges(node, newNode); |
| addEdge(newNode, node); |
| } |
| return newNode; |
| } |
| |
| Node* ControlFlowGraph::splitEdge(Edge *edge, CFGInst* inst, bool keepOldEdge) { |
| Node* target = edge->getTargetNode(); |
| Node* newNode = createBlockNode(inst); |
| if (inst!=NULL && target->getFirstInst()!=NULL) { |
| inst->setBCOffset(target->getFirstInst()->getBCOffset()); |
| } |
| |
| replaceEdgeTarget(edge, newNode, keepOldEdge); |
| addEdge(newNode, target); |
| |
| return newNode; |
| } |
| |
| void ControlFlowGraph::moveInstructions(Node* fromNode, Node* toNode, bool prepend) { |
| CFGInst* to = prepend ? toNode->getFirstInst() : toNode->getLastInst(); |
| CFGInst *inst = fromNode->getFirstInst(); |
| if (inst!=NULL && inst->isLabel()) { //skip block label if exists |
| inst = inst->next(); |
| } |
| for (; inst != NULL; ) { |
| CFGInst *next = inst->next(); |
| inst->unlink(); |
| if (to == NULL) { |
| if (prepend) { |
| toNode->prependInst(inst); |
| } else { |
| toNode->appendInst(inst); |
| } |
| } else { |
| inst->insertAfter(to); |
| } |
| to = inst; |
| assert(prepend || to == toNode->getLastInst()); |
| inst = next; |
| } |
| } |
| |
| class CountFreqsAlgorithm { |
| public: |
| CountFreqsAlgorithm(MemoryManager& _mm, ControlFlowGraph* _fg) : |
| mm(_mm), fg(_fg), loopTree(fg->getLoopTree()), |
| useCyclicFreqs(false), cyclicFreqs(NULL), exitEdges(mm) |
| { |
| if (!loopTree->isValid()) { |
| loopTree->rebuild(false); |
| } |
| U_32 nNodes = fg->getNodeCount(); |
| cyclicFreqs = new (mm) double[nNodes]; |
| std::fill(cyclicFreqs, cyclicFreqs + nNodes, 1); |
| } |
| |
| void estimate() { |
| smoothLinearFrequencies(); |
| LoopNode* topLevelLoops = (LoopNode*)loopTree->getRoot(); |
| if (topLevelLoops->getChild()!=NULL) { //if there are loops in method |
| useCyclicFreqs = true; |
| for (LoopNode* loopHead = topLevelLoops->getChild(); loopHead!=NULL; loopHead = loopHead->getSiblings()) { |
| estimateCyclicFrequencies(loopHead); |
| } |
| smoothLinearFrequencies(); |
| } |
| } |
| |
| |
| void smoothLinearFrequencies() { |
| const Nodes& nodes = fg->getNodesPostOrder(); |
| for (Nodes::const_reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) { |
| Node* node = *it; |
| const Edges& inEdges = node->getInEdges(); |
| if (inEdges.empty()) { |
| //node is entry, do nothing |
| assert (node == fg->getEntryNode()); |
| continue; |
| } |
| double freq = 0.0; |
| for(Edges::const_iterator it = inEdges.begin(), itEnd = inEdges.end(); it!=itEnd; it++) { |
| Edge* edge = *it; |
| if (loopTree->isBackEdge(edge)) { |
| continue; //only linear freq estimation |
| } |
| Node* fromNode = edge->getSourceNode(); |
| if (fromNode->getTraversalNum()!=node->getTraversalNum()) { |
| continue;//unreachable source node |
| } |
| double fromFreq = fromNode->getExecCount(); |
| freq += fromFreq * edge->getEdgeProb(); |
| } |
| if (useCyclicFreqs && loopTree->isLoopHeader(node)) { |
| freq *= cyclicFreqs[node->getDfNum()]; |
| } |
| node->setExecCount(freq); |
| } |
| } |
| |
| void estimateCyclicFrequencies(LoopNode* loopHead) { |
| //process all child loops first |
| bool hasChildLoop = loopHead->getChild()!=NULL; |
| if (hasChildLoop) { |
| for (LoopNode* childHead = loopHead->getChild(); childHead!=NULL; childHead = childHead->getSiblings()) { |
| estimateCyclicFrequencies(childHead); |
| } |
| } |
| findLoopExits(loopHead); |
| if (hasChildLoop) { |
| smoothLinearFrequencies(); |
| } |
| Node* cfgLoopHead = loopHead->getHeader(); |
| double inFlow = cfgLoopHead->getExecCount(); //node has linear freq here |
| double exitsFlow = 0; |
| //sum all exits flow |
| for (Edges::const_iterator it = exitEdges.begin(), end = exitEdges.end(); it!=end; ++it) { |
| Edge* edge = *it; |
| Node* fromNode = edge->getSourceNode(); |
| exitsFlow += edge->getEdgeProb() * fromNode->getExecCount(); |
| } |
| // if loop will make multiple iteration exitsFlow becomes equals to inFlow |
| double loopCycles = inFlow / exitsFlow; |
| if (loopCycles < 1) { |
| assert(ABS(inFlow-exitsFlow) < PROFILE_ERROR_ALLOWED); |
| loopCycles = 1; |
| } |
| cyclicFreqs[cfgLoopHead->getDfNum()] = loopCycles; |
| } |
| |
| void findLoopExits(LoopNode* loop) { |
| exitEdges.clear(); |
| const Nodes& nodes = loop->getNodesInLoop(); |
| for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) { |
| Node* node = *it; |
| const Edges& outEdges = node->getOutEdges(); |
| for(Edges::const_iterator eit = outEdges.begin(), eend = outEdges.end(); eit!=eend; ++eit) { |
| Edge* edge = *eit; |
| if (loop->isLoopExit(edge)) { |
| exitEdges.push_back(edge); |
| } |
| } |
| } |
| } |
| private: |
| MemoryManager& mm; |
| ControlFlowGraph* fg; |
| LoopTree* loopTree; |
| bool useCyclicFreqs; |
| double* cyclicFreqs; |
| Edges exitEdges; |
| }; |
| |
| //count node exec count from probs |
| void ControlFlowGraph::smoothEdgeProfile() { |
| assert(isEdgeProfileConsistent(true, false, true)); |
| if (isEdgeProfileConsistent(true, true)) { |
| return; |
| } |
| assert(entryNode->getExecCount()!=0); |
| CountFreqsAlgorithm c(mm, this); |
| c.estimate(); |
| lastProfileUpdateTraversalNumber = traversalNumber; |
| assert(isEdgeProfileConsistent(true, true, true)); |
| } |
| |
| ////////////////////////////////////////////////////////////////////////// |
| /// CFGInst methods |
| |
| CFGInst* CFGInst::next() const { |
| CFGInst* next = (CFGInst*)getNext(); |
| return (node!=NULL && next == node->instsHead) ? NULL : next; |
| } |
| |
| CFGInst* CFGInst::prev() const { |
| CFGInst* prev = (CFGInst*)getPrev(); |
| return (node!=NULL && prev == node->instsHead) ? NULL : prev; |
| } |
| |
| void CFGInst::insertBefore(CFGInst* inst) { |
| assert(node == NULL); |
| CFGInst* nextInst = next(); |
| unlink(); |
| Node* newNode = inst->getNode(); |
| if (newNode!= NULL) { |
| newNode->insertInst((CFGInst*)inst->getPrev(), this); |
| } else { |
| ((Dlink*)this)->insertBefore(inst); |
| } |
| if (nextInst!=this) { |
| nextInst->insertBefore(inst); |
| } |
| } |
| |
| void CFGInst::insertAfter(CFGInst* inst) { |
| assert(node == NULL); |
| CFGInst* nextInst = next(); |
| unlink(); |
| Node* newNode = inst->getNode(); |
| if (newNode!=NULL) { |
| newNode->insertInst(inst, this); |
| } else { |
| ((Dlink*)this)->insertAfter(inst); |
| } |
| if (nextInst!=this) { |
| nextInst->insertAfter(this); |
| } |
| } |
| |
| } //namespace |
