| /* |
| * 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 George A. Timoshenko |
| */ |
| |
| #include "Ia32IRManager.h" |
| #include "VMInterface.h" |
| #include "Ia32Tls.h" |
| #include <open/hythread_ext.h> |
| |
| namespace Jitrino |
| { |
| namespace Ia32{ |
| |
| const U_32 BBPollingMaxVersion = 6; |
| |
| //======================================================================================== |
| // class BBPolling |
| //======================================================================================== |
| /** |
| class BBPolling implements utilities for back branch polling pass |
| |
| */ |
| class BBPolling |
| { |
| typedef ::std::pair<U_32,U_32> targetIdDispatchIdPair; |
| typedef StlMap<targetIdDispatchIdPair,Node*> BBPControllersMap; |
| public: |
| |
| BBPolling(IRManager& ir,U_32 ver) : |
| irManager(ir), |
| version(ver), |
| hasThreadInterruptablePoint(irManager.getMemoryManager(), irManager.getFlowGraph()->getMaxNodeId(), false), |
| hasNativeInterruptablePoint(irManager.getMemoryManager(), irManager.getFlowGraph()->getMaxNodeId(), false), |
| isOnThreadInterruptablePath(irManager.getMemoryManager(), irManager.getFlowGraph()->getMaxNodeId(), false), |
| tlsBaseRegForLoopHeader(irManager.getMemoryManager(), irManager.getFlowGraph()->getMaxNodeId(), NULL), |
| bbpCFGControllerForNode(irManager.getMemoryManager()), |
| toppestLoopHeader(irManager.getMemoryManager(), irManager.getFlowGraph()->getMaxNodeId(), NULL), |
| otherStartNdx(irManager.getMemoryManager(), irManager.getFlowGraph()->getMaxNodeId(), 0), |
| loopHeaders(irManager.getMemoryManager()), |
| otherEdges(irManager.getMemoryManager()), |
| eligibleEdges(irManager.getMemoryManager()), |
| #ifdef _DEBUG |
| interruptablePoints(0), |
| pollingPoints(0), |
| #endif |
| loopHeaderOfEdge(irManager.getMemoryManager()) |
| { |
| gcFlagOffsetOffset = VMInterface::flagTLSSuspendRequestOffset(); |
| calculateInitialInterruptability(version == 5 || version == 6); |
| if (version == 2 || version == 3) |
| calculateInterruptablePathes(); |
| // no more calculations here, just collect the edges! |
| switch (version) { |
| case 1: collectEligibleEdges(); break; |
| case 2: collectEligibleEdges2(); break; |
| case 3: collectEligibleEdgesRecursive(); break; |
| case 4: collectEligibleEdges(); break; |
| case 5: collectEligibleEdges(); break; |
| case 6: collectEligibleEdges(); break; |
| default: assert(0); |
| } |
| if (Log::isEnabled()) { |
| dumpEligibleEdges(); |
| } |
| #ifdef _DEBUG |
| if (version == 2 || version == 3) |
| verify(); |
| #endif |
| } |
| |
| U_32 numberOfAffectedEdges() { return (U_32)eligibleEdges.size(); } |
| Edge* getAffectedEdge(U_32 i) { assert(i < eligibleEdges.size()); return eligibleEdges[i]; } |
| |
| Opnd* getOrCreateTLSBaseReg(Edge* e); |
| |
| static bool isThreadInterruptablePoint(const Inst* inst); |
| |
| static bool hasNativeInterruptablePoints(const Node* node); |
| |
| bool hasAllThreadInterruptablePredecessors(const Node* node); |
| |
| Node* getBBPSubCFGController(U_32 targetId, U_32 dispatchId); |
| void setBBPSubCFGController(U_32 targetId, U_32 dispatchId, Node* node); |
| ControlFlowGraph* createBBPSubCFG(IRManager& ir, Opnd* tlsBaseReg); |
| |
| private: |
| |
| bool isInterruptable(const BasicBlock* b) { |
| return hasThreadInterruptablePoint[b->getId()]; |
| } |
| // select all loopHeaders |
| // identify all nodes which hasNativeInterruptablePoints |
| // mark all successors of such nodes as hasThreadInterruptablePoint |
| void calculateInitialInterruptability(bool doPassingDown); |
| // identify the nodes which are on the way from a loopHeader to a node which hasThreadInterruptablePoints |
| void calculateInterruptablePathes(); |
| bool isOnInterruptablePath(Node* node); |
| |
| // collect the edges for substition by subCFG that checks the flag and call the helper if the flag. |
| // These edges are those from a Node which isOnInterruptablePath to it's succ_node which is not. |
| void collectEligibleEdges(); // all backedges |
| void collectEligibleEdges2(); // all pairs [isOnThreadInterruptablePath]->[!isOnThreadInterruptablePath] |
| void collectEligibleEdgesRecursive(); // recursive selecting of 2 |
| void collectEdgesDeeper(Node* node); |
| |
| void dumpEligibleEdges(); |
| |
| #ifdef _DEBUG |
| bool isEligible(Edge* e); |
| void verify(); |
| void verifyDeeper(Node* node, Node* enwind, Node* exit); |
| #endif // _DEBUG |
| |
| IRManager& irManager; |
| |
| // version of BBPolling: |
| // 0 - must be discarded in runImpl() |
| // 1 - insert bbpCFG at all backedges except those going from initiallyInterruptable nodes |
| // (initialInterruptability is not being propagated to the successors. This is the feature of version 5) |
| // 2 - path analysis based on searching of pairs [isOnThreadInterruptablePath]->[!isOnThreadInterruptablePath] |
| // 3 - recursive version of "2" |
| // 4 - "1" + suspension flag addr [TLS base + offset] is calculated before the loop header |
| // 5 - like "1" but some backedges are not patched (if all paths through it are uninterpretable) |
| // 6 - "4" + "5" |
| // 7.. illegal |
| U_32 version; |
| // storage for ThreadInterruptablePoints information |
| // hasThreadInterruptablePoint[Node->getId()] == true means that the Node is a LoopHeader |
| // OR It has at least one instruction that isThreadInterruptablePoint(inst) |
| // OR all predecessors hasThreadInterruptablePoint or incoming edge is a loopExit |
| StlVector<bool> hasThreadInterruptablePoint; |
| StlVector<bool> hasNativeInterruptablePoint; // only those that hase at least one InterruptablePoint(inst) |
| // storage for InterruptablePathes information |
| // isOnThreadInterruptablePath[Node->getId()] == true means that there is a way from the Node |
| // to another a_node which hasThreadInterruptablePoint[a_node->getId()] |
| StlVector<bool> isOnThreadInterruptablePath; |
| // tlsBaseRegs pointers. One per each affected loopHeader |
| StlVector<Opnd*> tlsBaseRegForLoopHeader; |
| // pointers to already prepared bbpCFG. bbpCFG is placed "before" a node to collect all eligible edges. |
| // pair.first - targetNode id |
| // pair.second - sourceNode dispatch edge target id |
| BBPControllersMap bbpCFGControllerForNode; |
| // to get the toppest loop header of the given without calling getLoopHeader |
| StlVector<Node*> toppestLoopHeader; |
| // start index in otheredges collection for the topmost loop headers |
| StlVector<U_32> otherStartNdx; |
| |
| // just a collection of loop headers of the method (Basic blocks only!) |
| StlVector<Node*> loopHeaders; |
| // edges which are not a back edge |
| StlVector<Edge*> otherEdges; |
| // edges for inserting BBPolling subCFG |
| StlVector<Edge*> eligibleEdges; |
| |
| /// Offset of the suspension flag in the VM's structure stored in TLS. |
| U_32 gcFlagOffsetOffset; |
| |
| #ifdef _DEBUG |
| U_32 interruptablePoints; |
| U_32 pollingPoints; |
| #endif |
| StlHashMap<Edge*, Node *> loopHeaderOfEdge; |
| |
| }; // BBPolling class |
| |
| //___________________________________________________________________________________________________ |
| |
| class BBPollingTransformer : public SessionAction { |
| public: |
| BBPollingTransformer() : hasSideEffects(false){} |
| |
| bool hasSideEffects; |
| |
| void runImpl(){ |
| LoopTree* lt = irManager->getFlowGraph()->getLoopTree(); |
| if(!lt->hasLoops()) { |
| return; |
| } |
| version = getIntArg("version", 6); |
| if(version == 0) { |
| return; |
| } |
| if(version > BBPollingMaxVersion) { |
| assert(0); |
| return; |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "BBPolling transformer version="<< version <<" STARTED" << ::std::endl; |
| } |
| BBPolling bbp = BBPolling(*irManager, version); |
| U_32 numOfAffectedEdges = bbp.numberOfAffectedEdges(); |
| hasSideEffects = numOfAffectedEdges != 0; |
| ControlFlowGraph* fg = irManager->getFlowGraph(); |
| // Foreach eligible backedge create bbpCFG and inline it between the backedge's Tail and it's target |
| for (U_32 j = 0; j < numOfAffectedEdges; j++) { |
| Edge* edge = bbp.getAffectedEdge(j); |
| |
| // get or create and insert before the loopHeade a basic block for calculating TLS base |
| Opnd* tlsBaseReg = bbp.getOrCreateTLSBaseReg(edge); |
| |
| U_32 originalTargetId = edge->getTargetNode()->getId(); |
| Edge* srcDispatchEdge = edge->getSourceNode()->getExceptionEdge(); |
| U_32 sourceDispatchId = srcDispatchEdge ? srcDispatchEdge->getTargetNode()->getId() : 0; |
| // CFG for inlining |
| Node* bbpCFGController = bbp.getBBPSubCFGController(originalTargetId,sourceDispatchId); |
| if (bbpCFGController) { // just retarget the edge |
| fg->replaceEdgeTarget(edge, bbpCFGController, true); |
| } else { // we need a new bbpCFG |
| ControlFlowGraph* bbpCFG = bbp.createBBPSubCFG(*irManager, tlsBaseReg); |
| |
| // Inlining bbpCFG at edge |
| if (fg->getUnwindNode()==NULL) {//inlined cfg has dispatch flow -> add unwind to parent if needed |
| Node* unwind = fg->createDispatchNode(); |
| fg->addEdge(unwind, fg->getExitNode()); |
| fg->setUnwindNode(unwind); |
| } |
| fg->spliceFlowGraphInline(edge, *bbpCFG); |
| bbp.setBBPSubCFGController(originalTargetId,sourceDispatchId,bbpCFG->getEntryNode()); |
| } |
| } |
| if (Log::isEnabled()) |
| Log::out() << "BBPolling transformer FINISHED" << ::std::endl; |
| } //runImpl() |
| U_32 getNeedInfo()const{ return NeedInfo_LoopInfo; } |
| U_32 getSideEffects()const{ return hasSideEffects ? SideEffect_InvalidatesLoopInfo|SideEffect_InvalidatesLivenessInfo : 0; } |
| bool isIRDumpEnabled(){ return true; } |
| U_32 version; |
| }; |
| |
| static ActionFactory<BBPollingTransformer> _bbp("bbp"); |
| |
| Opnd* |
| BBPolling::getOrCreateTLSBaseReg(Edge* e) |
| { |
| // TLS base reg is one per each nested loop |
| Node* loopHeader = toppestLoopHeader[loopHeaderOfEdge[e]->getId()]; |
| assert(loopHeader); |
| |
| const U_32 id = loopHeader->getId(); |
| |
| Opnd* tlsBaseReg = tlsBaseRegForLoopHeader[id]; |
| if ( tlsBaseReg ) { // it is already created for this loop |
| return tlsBaseReg; |
| } |
| |
| Type* tlsBaseType = irManager.getTypeManager().getUnmanagedPtrType(irManager.getTypeManager().getIntPtrType()); |
| |
| #ifdef HYX86_64 |
| tlsBaseReg = irManager.newOpnd(tlsBaseType, Constraint(OpndKind_GPReg)); |
| #else |
| tlsBaseReg = irManager.newOpnd(tlsBaseType, Constraint(RegName_EAX)| |
| RegName_EBX | |
| RegName_ECX | |
| RegName_EDX | |
| RegName_EBP | |
| RegName_ESI | |
| RegName_EDI); |
| #endif |
| // Basic Block for flag address calculating. (To be inserted before the loopHeaders) |
| Node * bbpFlagAddrBlock = irManager.getFlowGraph()->createBlockNode(); |
| Opnd* tlsBase = createTlsBaseLoadSequence(irManager, bbpFlagAddrBlock); |
| |
| if (version == 4 || version == 6) { |
| Opnd * offset = irManager.newImmOpnd(tlsBaseType, gcFlagOffsetOffset); |
| bbpFlagAddrBlock->appendInst(irManager.newInstEx(Mnemonic_ADD, 1, tlsBaseReg, tlsBase, offset)); |
| } else { |
| bbpFlagAddrBlock->appendInst(irManager.newInst(Mnemonic_MOV, tlsBaseReg, tlsBase)); |
| } |
| |
| // inserting bbpFlagAddrBlock before the given loopHeader |
| U_32 startIndex = otherStartNdx[id]; |
| |
| ControlFlowGraph* fg = irManager.getFlowGraph(); |
| for (U_32 otherIdx = startIndex; ; otherIdx++) { |
| if (otherIdx == otherEdges.size()) |
| break; |
| Edge* other = otherEdges[otherIdx]; |
| if (other->getTargetNode() != loopHeader) |
| break; |
| fg->replaceEdgeTarget(other, bbpFlagAddrBlock, true); |
| } |
| |
| assert(loopHeader->isBlockNode()); |
| fg->addEdge(bbpFlagAddrBlock, loopHeader, 1); |
| |
| tlsBaseRegForLoopHeader[id] = tlsBaseReg; |
| return tlsBaseReg; |
| } |
| |
| Node* |
| BBPolling::getBBPSubCFGController(U_32 targetId, U_32 dispatchId) |
| { |
| const BBPControllersMap::iterator iter = bbpCFGControllerForNode.find(::std::make_pair(targetId,dispatchId)); |
| if (iter == bbpCFGControllerForNode.end()) { |
| return NULL; |
| } else { |
| return (*iter).second; |
| } |
| } |
| |
| void |
| BBPolling::setBBPSubCFGController(U_32 targetId, U_32 dispatchId, Node* node) |
| { |
| assert(node); |
| assert(!bbpCFGControllerForNode.has(::std::make_pair(targetId,dispatchId))); |
| bbpCFGControllerForNode[::std::make_pair(targetId,dispatchId)] = node; |
| } |
| |
| // This is a debug hack. It does not work with gcc (warning when casting to int64 below) |
| #if 0 |
| static void callerStarter() |
| { |
| ::std::cout << "Caller started!" << ::std::endl; |
| // DebugBreak(); |
| } |
| |
| static void controllerStarter() |
| { |
| ::std::cout << "Controller started!" << ::std::endl; |
| // DebugBreak(); |
| } |
| #endif |
| |
| ControlFlowGraph* |
| BBPolling::createBBPSubCFG(IRManager& irManager, Opnd* tlsBaseReg) |
| { |
| Type* typeInt32 = irManager.getTypeManager().getPrimitiveType(Type::Int32); |
| // CFG for inlining |
| ControlFlowGraph* bbpCFG = irManager.createSubCFG(true, true); |
| Node* bbpBBController=bbpCFG->getEntryNode(); |
| Node* bbpBBHelpCaller=bbpCFG->createBlockNode(); |
| Node* bbpReturn =bbpCFG->getReturnNode(); |
| |
| // Controller node |
| |
| // This is a debug hack. It does not work with gcc (warning when casting to int64) |
| #if 0 |
| Opnd * target = irManager.newImmOpnd( irManager.getTypeManager().getUnmanagedPtrType(irManager.getTypeManager().getIntPtrType()), |
| (int64)controllerStarter); |
| Inst* dbgCall = irManager.newCallInst(target, &CallingConvention_STDCALL, 0, NULL, NULL, NULL); |
| bbpBBController->appendInsts(dbgCall); |
| #endif |
| |
| Opnd* gcFlag = NULL; |
| if (version == 4 || version == 6) { |
| gcFlag = irManager.newMemOpnd(typeInt32, MemOpndKind_Any, tlsBaseReg, 0); |
| } else { |
| gcFlag = irManager.newMemOpnd(typeInt32, MemOpndKind_Any, tlsBaseReg, gcFlagOffsetOffset); |
| } |
| |
| Opnd* zero = irManager.newImmOpnd(typeInt32, 0); |
| bbpBBController->appendInst(irManager.newInst(Mnemonic_CMP, gcFlag, zero)); |
| bbpBBController->appendInst(irManager.newBranchInst(Mnemonic_JNZ, bbpBBHelpCaller, bbpReturn)); |
| |
| |
| // Helper Caller node |
| |
| // This is a debug hack. It does not work with gcc (warning when casting to int64) |
| #if 0 |
| target = irManager.newImmOpnd( irManager.getTypeManager().getUnmanagedPtrType(irManager.getTypeManager().getIntPtrType()), |
| (int64)callerStarter); |
| dbgCall = irManager.newCallInst(target, &CallingConvention_STDCALL, 0, NULL, NULL, NULL); |
| bbpBBHelpCaller->appendInsts(dbgCall); |
| #endif |
| |
| bbpBBHelpCaller->appendInst(irManager.newRuntimeHelperCallInst( |
| VM_RT_GC_SAFE_POINT, 0, NULL, NULL) |
| ); |
| |
| bbpCFG->addEdge(bbpBBController,bbpBBHelpCaller, 0); |
| bbpCFG->addEdge(bbpBBController, bbpReturn, 1); |
| bbpCFG->addEdge(bbpBBHelpCaller, bbpReturn, 1); |
| bbpCFG->addEdge(bbpBBHelpCaller, bbpCFG->getUnwindNode(), 0); |
| |
| return bbpCFG; |
| } |
| |
| bool |
| BBPolling::isThreadInterruptablePoint(const Inst* inst) { |
| if ( inst->getMnemonic() == Mnemonic_CALL ) { |
| Opnd::RuntimeInfo* ri = inst->getOpnd(((ControlTransferInst*)inst)->getTargetOpndIndex())->getRuntimeInfo(); |
| if (!ri) { |
| return false; |
| } else { |
| if ( ri->getKind() == Opnd::RuntimeInfo::Kind_MethodDirectAddr && |
| ((MethodDesc*)ri->getValue(0))->isNative() ) |
| { |
| return true; |
| } |
| CompilationInterface* ci = CompilationContext::getCurrentContext()->getVMCompilationInterface(); |
| if ( ri->getKind() == Opnd::RuntimeInfo::Kind_HelperAddress && |
| ci->isInterruptible((VM_RT_SUPPORT)(POINTER_SIZE_INT)ri->getValue(0)) ) |
| { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| bool |
| BBPolling::hasNativeInterruptablePoints(const Node* node) { |
| if (node->isBlockNode()) { |
| // If current BB has an inst that is ThreadInterruptablePoint itself |
| // the hasThreadInterruptablePoint becomes true for it |
| for (Inst* inst = (Inst*)node->getFirstInst(); inst!=NULL; inst = inst->getNextInst()) { |
| if (BBPolling::isThreadInterruptablePoint(inst)) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| bool |
| BBPolling::hasAllThreadInterruptablePredecessors(const Node* node) { |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| assert(lt->isValid()); |
| const Edges& edges = node->getInEdges(); |
| |
| if (edges.size()==0) return false; |
| |
| // All the predecessors must be processed earlier! |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e = *ite; |
| if (!hasThreadInterruptablePoint[e->getSourceNode()->getId()] && !lt->isLoopExit(e)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| void |
| BBPolling::calculateInitialInterruptability(bool doPassingDown) |
| { |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| assert(lt->isValid()); |
| const Nodes& postOrder = irManager.getFlowGraph()->getNodesPostOrder(); |
| for (Nodes::const_reverse_iterator it = postOrder.rbegin(), end = postOrder.rend(); it!=end; ++it) { |
| Node* node = *it; |
| const U_32 id = node->getId(); |
| |
| if (lt->isLoopHeader(node) && node->isBlockNode()) { |
| loopHeaders.push_back(node); |
| // here we calculate loopHeaders with depth == 0, and otherEdges for them |
| // to create only one TLS base loader per each nested loop |
| Node* loopHeader = node; |
| LoopNode* loop = lt->getLoopNode(loopHeader, false); |
| assert(loopHeader == loop->getHeader()); |
| while (loop->getDepth() > 1) { |
| loop = loop->getParent(); |
| } |
| loopHeader = loop->getHeader(); |
| if ( !toppestLoopHeader[id] ) { |
| toppestLoopHeader[id] = loopHeader; |
| // here we need to remember all otheredges and their start index for particular loopHeader |
| otherStartNdx[loopHeader->getId()] = (U_32)otherEdges.size(); |
| const Edges& edges = loopHeader->getInEdges(); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e = *ite; |
| if ( !lt->isBackEdge(e) ) { |
| otherEdges.push_back(e); |
| } |
| } |
| } |
| } |
| |
| // If current BB has an inst that is ThreadInterruptablePoint itself |
| // or it is a Dispatch Node |
| // the hasThreadInterruptablePoint becomes true for it |
| hasNativeInterruptablePoint[id] = BBPolling::hasNativeInterruptablePoints(node); |
| if (hasNativeInterruptablePoint[id]) { |
| hasThreadInterruptablePoint[id] = true; |
| if (Log::isEnabled()) |
| Log::out() << " hasNativeInterruptablePoint["<<id<<"] == true" << ::std::endl; |
| } |
| |
| if (doPassingDown) { |
| // if all the predecessors hasThreadInterruptablePoint or incoming edge is a loopExit |
| // mark the node as it hasThreadInterruptablePoint (if it is not a loop header) |
| if (!hasThreadInterruptablePoint[id] && !lt->isLoopHeader(node) ) { |
| if ( hasThreadInterruptablePoint[id] = hasAllThreadInterruptablePredecessors(node) && |
| Log::isEnabled() ) |
| { |
| Log::out() << " (inherited) hasThreadInterruptablePoint["<<id<<"] == true" << ::std::endl; |
| } |
| } |
| } |
| } |
| } // calculateInitialInterruptability |
| |
| void |
| BBPolling::calculateInterruptablePathes() |
| { |
| assert(loopHeaders.size()); |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| U_32 maxLoopDepth = lt->getMaxLoopDepth(); |
| |
| // process the deepest firstly |
| for (U_32 currDepth = maxLoopDepth; currDepth > 0; currDepth--) |
| { |
| for (U_32 i=0; i < loopHeaders.size(); i++) |
| { |
| Node* loopHeader = loopHeaders[i]; |
| LoopNode* loop = lt->getLoopNode(loopHeader, false); |
| assert(loopHeader == loop->getHeader()); |
| const U_32 loopHeaderId = loopHeader->getId(); |
| if (loop->getDepth() == currDepth - 1) { |
| if (hasNativeInterruptablePoint[loopHeaderId]) { |
| // fortunately we can skip this loop, because it is already interruptable ( it has respective |
| // instructions and it was calculated earlier in calculateInitialInterruptability() ) |
| continue; |
| } |
| |
| // Process all successors of the loopHeader |
| const Edges& edges = loopHeader->getOutEdges(); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e = *ite; |
| Node* succ = e->getTargetNode(); |
| if( loop->inLoop(succ) && succ == loopHeader) { |
| isOnInterruptablePath(succ); |
| } else { |
| // this edge does not go into the loop. Skip it. |
| // OR our loop consist of only one BB (the loopHeader itself). Skip the backedge. |
| } |
| } |
| // After the loop is processed it gets hasThreadInterruptablePoint mark |
| // to prvent the outer loop processing from going inside the current one |
| // Also it gets isOnThreadInterruptablePath mark for further selection of eligibleEdges |
| hasThreadInterruptablePoint[loopHeaderId] = true; |
| isOnThreadInterruptablePath[loopHeaderId] = true; |
| if (Log::isEnabled()) { |
| Log::out() << " loopHeader:" << ::std::endl; |
| Log::out() << " hasThreadInterruptablePoint["<<loopHeaderId<<"] == true" << ::std::endl; |
| Log::out() << " isOnThreadInterruptablePath["<<loopHeaderId<<"] == true" << ::std::endl; |
| } |
| } |
| } |
| } |
| } // calculateInterruptablePathes |
| |
| bool |
| BBPolling::isOnInterruptablePath(Node* node) |
| { |
| const U_32 id = node->getId(); |
| // the order of these check is essential! (because in case of nested loops |
| // if the node is a loopHeader of a nested loop we must return true) |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| if( hasThreadInterruptablePoint[id] ) { |
| isOnThreadInterruptablePath[id] = true; |
| if (Log::isEnabled()) |
| Log::out() << " isOnThreadInterruptablePath["<<id<<"] == true" << ::std::endl; |
| return true; |
| } else if ( lt->isLoopHeader(node) ) { |
| return false; // loopHeader also breaks the recursion |
| } |
| |
| bool retValue = false; |
| const Edges& edges = node->getOutEdges(); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e= *ite; |
| Node* succ = e->getTargetNode(); |
| |
| if( !lt->isLoopExit(e) && isOnInterruptablePath(succ) ) { |
| if (Log::isEnabled()) |
| Log::out() << " isOnThreadInterruptablePath["<<id<<"] == true" << ::std::endl; |
| isOnThreadInterruptablePath[id] = true; |
| // Must not break here. |
| // All outgoing ways must be passed till the LoopHeader or hasThreadInterruptablePoint |
| // The LoopHeader at the edge's head means |
| // - that the edge is a LoopExit |
| // - or it is a header of nested loop which must be processed earlier |
| // so it hasThreadInterruptablePoint |
| retValue = true; |
| } |
| } |
| return retValue; |
| } // isOnInterruptablePath |
| |
| void |
| BBPolling::collectEligibleEdges() |
| { |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| for (U_32 i=0; i < loopHeaders.size(); i++) { |
| Node* node = loopHeaders[i]; |
| const Edges& edges = node->getInEdges(); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e = *ite; |
| if ( lt->isBackEdge(e) && !e->isCatchEdge() && |
| !hasThreadInterruptablePoint[e->getSourceNode()->getId()] |
| ) |
| { |
| eligibleEdges.push_back(e); |
| loopHeaderOfEdge[e] = node; |
| } |
| } |
| } |
| |
| } // collectEligibleEdges |
| |
| void |
| BBPolling::collectEligibleEdges2() |
| { |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| const Nodes& nodes = irManager.getFlowGraph()->getNodes(); |
| for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) { |
| Node* node = *it; |
| const U_32 id = node->getId(); |
| if ( isOnThreadInterruptablePath[id] && ! hasNativeInterruptablePoint[id] ) { |
| const Edges& edges = node->getOutEdges(); |
| LoopNode* nodeLoop = lt->getLoopNode(node, false); |
| assert(nodeLoop!=NULL); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e = *ite; |
| Node* succ = e->getTargetNode(); |
| U_32 succId = succ->getId(); |
| if (nodeLoop->inLoop(succ)) { |
| if( !isOnThreadInterruptablePath[succId] ) { |
| eligibleEdges.push_back(e); |
| loopHeaderOfEdge[e] = nodeLoop->getHeader(); |
| } |
| } else { |
| continue; // the edge leaves our loop |
| } |
| } |
| } |
| } |
| |
| } // collectEligibleEdges2 |
| |
| void |
| BBPolling::collectEligibleEdgesRecursive() |
| { |
| for (U_32 i=0; i < loopHeaders.size(); i++) |
| { |
| collectEdgesDeeper(loopHeaders[i]); |
| } |
| std::sort(eligibleEdges.begin(), eligibleEdges.end()); |
| StlVector<Edge*>::iterator newEnd = std::unique(eligibleEdges.begin(), eligibleEdges.end()); |
| eligibleEdges.resize(newEnd - eligibleEdges.begin()); |
| |
| } // collectEligibleEdgesRecursive |
| |
| void |
| BBPolling::collectEdgesDeeper(Node* node) |
| { |
| U_32 id = node->getId(); |
| if (hasNativeInterruptablePoint[id]) { |
| return; |
| } |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| if ( isOnThreadInterruptablePath[id] ) { |
| // if the node has an outgoing edge to the node which: |
| // - is not OnThreadInterruptablePath |
| // - OR this ougoing edge points to the node itself |
| // add the edge to eligibleEdges if it is not a loopExit |
| const Edges& edges = node->getOutEdges(); |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e = *ite; |
| Node* succ = e->getTargetNode(); |
| U_32 succId = succ->getId(); |
| if ( succ == node ) { |
| eligibleEdges.push_back(e); |
| loopHeaderOfEdge[e] = node; |
| } |
| LoopNode* nodeLoop= lt->getLoopNode(node, false); |
| assert(nodeLoop); |
| if ( nodeLoop->inLoop(succ) && succ != nodeLoop->getHeader()) { |
| if(!isOnThreadInterruptablePath[succId]) |
| { |
| eligibleEdges.push_back(e); |
| loopHeaderOfEdge[e] = nodeLoop->getHeader(); |
| } else { |
| if (lt->isLoopHeader(succ)) { |
| continue; // there are no eligible edges deeper (nested loop) |
| } else { |
| collectEdgesDeeper(succ); |
| } |
| } |
| } else if (lt->isBackEdge(e)) { |
| // get a backedge and have not met any interruptable points earlier |
| assert(e->getTargetNode() == nodeLoop->getHeader()); |
| eligibleEdges.push_back(e); |
| loopHeaderOfEdge[e] = nodeLoop->getHeader(); |
| } else { |
| continue; // the edge leaves our loop |
| } |
| } |
| } else { |
| assert(0); |
| } |
| } // collectEdgesDeeper |
| |
| void |
| BBPolling::dumpEligibleEdges() |
| { |
| assert(Log::isEnabled()); |
| Log::out() << " EligibleEdges:" << ::std::endl; |
| for (U_32 i = 0; eligibleEdges.size() > i; i++) { |
| Edge* e = eligibleEdges[i]; |
| U_32 srcId = e->getSourceNode()->getId(); |
| U_32 succId = e->getTargetNode()->getId(); |
| Log::out() << " eligibleEdge ["<<srcId<<"]-->["<<succId<<"]" << ::std::endl; |
| } |
| Log::out() << " EligibleEdges END! " << ::std::endl; |
| } |
| |
| #ifdef _DEBUG |
| |
| bool |
| BBPolling::isEligible(Edge* e) |
| { |
| return ::std::find(eligibleEdges.begin(),eligibleEdges.end(),e) == eligibleEdges.end(); |
| } // isEligible |
| |
| void |
| BBPolling::verify() |
| { |
| if (Log::isEnabled()) |
| Log::out() << "BBPolling verification started" << ::std::endl; |
| interruptablePoints = 0; |
| pollingPoints = 0; |
| |
| Node* unwind = irManager.getFlowGraph()->getUnwindNode(); |
| Node* exit = irManager.getFlowGraph()->getExitNode(); |
| |
| for (U_32 i=0; i < loopHeaders.size(); i++) |
| { |
| assert(interruptablePoints == 0); |
| assert(pollingPoints == 0); |
| |
| Node* loopHeader = loopHeaders[i]; |
| bool nativelyInterruptable = BBPolling::hasNativeInterruptablePoints(loopHeader); |
| |
| if(nativelyInterruptable) |
| interruptablePoints++; |
| |
| if (Log::isEnabled()) |
| Log::out() << " verification for loopHeader id=" << loopHeader->getId() << "STARTED" << ::std::endl; |
| verifyDeeper(loopHeader,unwind,exit); |
| |
| if (Log::isEnabled()) |
| Log::out() << " verification for loopHeader id=" << loopHeader->getId() << "FINISHED" << ::std::endl; |
| if(nativelyInterruptable) |
| interruptablePoints--; |
| } |
| |
| assert(interruptablePoints == 0); |
| assert(pollingPoints == 0); |
| if (Log::isEnabled()) |
| Log::out() << "BBPolling verification successfully finished" << ::std::endl; |
| } // verify |
| |
| void |
| BBPolling::verifyDeeper(Node* node, Node* unwind, Node* exit) |
| { |
| const Edges& edges = node->getOutEdges(); |
| if (Log::isEnabled()) { |
| Log::out() << " verification: NODE id=" << node->getId() << ::std::endl; |
| } |
| |
| LoopTree* lt = irManager.getFlowGraph()->getLoopTree(); |
| |
| for (Edges::const_iterator ite = edges.begin(), ende = edges.end(); ite!=ende; ++ite) { |
| Edge* e= *ite; |
| bool eligible = isEligible(e); |
| Node* succ = e->getTargetNode(); |
| |
| if ( lt->isLoopExit(e) || succ == unwind ) { |
| continue; |
| } |
| if (Log::isEnabled()) |
| Log::out() << " verification: succ id=" << succ->getId() << ::std::endl; |
| if ( lt->isBackEdge(e)) { |
| if (Log::isEnabled()) |
| Log::out() << " verification BackEdge ["<<node->getId()<<"]-->["<<succ->getId()<<"]" << ::std::endl; |
| if(pollingPoints == 0 && eligible) |
| continue; |
| if(pollingPoints == 1 && !eligible) |
| continue; |
| if(pollingPoints == 0 && interruptablePoints > 0 && !eligible) |
| continue; |
| assert(0); |
| } |
| if (lt->isLoopHeader(succ)) { // nested loop |
| if (Log::isEnabled()) { |
| Log::out() << " verification NestedLoop" << ::std::endl; |
| } |
| if(pollingPoints == 0 && !eligible) { |
| continue; |
| } |
| assert(0); |
| } |
| |
| bool nativelyInterruptable = BBPolling::hasNativeInterruptablePoints(succ); |
| if (nativelyInterruptable) |
| interruptablePoints++; |
| if (eligible) |
| pollingPoints++; |
| |
| verifyDeeper(succ,unwind,exit); |
| |
| if (nativelyInterruptable) |
| interruptablePoints--; |
| if (eligible) |
| pollingPoints--; |
| } |
| } // verifyDeeper |
| |
| #endif // _DEBUG |
| |
| }}; // namespace Ia32 |
| |
| |
