| /* |
| * 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, Pavel A. Ozhdikhin |
| * |
| */ |
| |
| #include <assert.h> |
| #include <iostream> |
| #include <algorithm> |
| #include "Stl.h" |
| #include "Log.h" |
| #include "open/types.h" |
| #include "Inst.h" |
| #include "irmanager.h" |
| #include "Dominator.h" |
| #include "Loop.h" |
| #include "Opcode.h" |
| #include "walkers.h" |
| #include "opndmap.h" |
| #include "dataflow.h" |
| #include "unionfind.h" |
| #include "syncopt.h" |
| #include "FlowGraph.h" |
| #include "PMFAction.h" |
| |
| namespace Jitrino { |
| |
| #define EXTRA_DEBUGGING 0 |
| |
| DEFINE_SESSION_ACTION(SyncOptPass, syncopt, "Synchronization Optimization") |
| |
| void |
| SyncOptPass::_run(IRManager& irm) { |
| SyncOpt opt(irm, irm.getNestedMemoryManager()); |
| opt.runPass(); |
| } |
| |
| |
| SyncOpt::SyncOpt(IRManager &irManager0, |
| MemoryManager& memManager) |
| : irManager(irManager0), |
| mm(memManager), |
| flags(*irManager.getOptimizerFlags().syncOptFlags), |
| lockType(0), |
| lockAddrType(0), |
| lockVar(memManager) |
| { |
| } |
| |
| SyncOpt::~SyncOpt() |
| { |
| } |
| |
| void |
| SyncOpt::readFlags(Action* argSource, SyncOptFlags* flags) { |
| IAction::HPipeline p = NULL; //default pipeline for argSource |
| flags->optimistic = argSource->getBoolArg(p, "sync.optimistic", false); |
| flags->use_IncRecCount = argSource->getBoolArg(p, "sync.use_increccount", false); |
| flags->balance = argSource->getBoolArg(p, "sync.balance", true); |
| flags->transform = argSource->getBoolArg(p, "sync.transform", true); |
| flags->transform2 = argSource->getBoolArg(p, "sync.transform2", true); |
| } |
| |
| void SyncOpt::showFlags(std::ostream& os) { |
| os << " syncopt flags:"<<std::endl; |
| os << " sync.optimistic[={OFF|on}] - convert region with a call to optimistic balanced enter/exit" << std::endl; |
| os << " sync.use_increccount[={OFF|on}] - use increccount [not working yet]" << std::endl; |
| os << " sync.balance[={off|ON}] - do balancing" << ::std::endl; |
| os << " sync.transform[={off|ON}] - do rewriting that facilitates balancing" << std::endl; |
| os << " sync.transform2[={OFF|on}] - give dispatch nodes a dispatch succ" << std::endl; |
| } |
| |
| |
| // a NodeWalker |
| class FixupSyncEdgesWalker { |
| protected: |
| SyncOpt *thePass; |
| IRManager &irm; |
| MemoryManager &mm; |
| ControlFlowGraph &fg; |
| Node *unwind; |
| public: |
| FixupSyncEdgesWalker(IRManager &irm0, |
| MemoryManager& mm0) |
| : irm(irm0), mm(mm0), fg(irm0.getFlowGraph()), unwind(0) |
| { |
| unwind = fg.getUnwindNode(); |
| }; |
| |
| void applyToCFGNode(Node *node); |
| bool applyToNode1(Node *node); |
| bool applyToNode2(Node *node); |
| bool applyToNode3(Node *node); |
| |
| bool isDispatchNode(Node *node) { return node->isDispatchNode(); }; |
| bool isCatchAll(Node *node, Opnd *&caughtOpnd, Node *&catchInstNode); |
| bool isMonExit(Node *node, Opnd *&monOpnd, Node *&dispatchNode, |
| Edge *&dispatchEdge); |
| bool isCatchAllAndMonExit(Node *node, Opnd *&caughtOpnd, Opnd *&monOpnd, Node *&dispatchNode, |
| Edge *&dispatchEdge, |
| Node *&catchInstNode); |
| bool isJustThrow(Node *node, Opnd *&thrownOpnd, Node *&dispatchNode); |
| bool isUnwind(Node *node) { return (node == unwind); }; |
| Node *getFirstCatchNode(Node *dispatchNode); |
| }; |
| |
| bool FixupSyncEdgesWalker::isCatchAll(Node *node, Opnd *&caughtOpnd, |
| Node *&catchInstNode) |
| { |
| Inst *firstInst = (Inst*)node->getFirstInst(); |
| if (!firstInst->isCatchLabel()) return false; |
| CatchLabelInst *catchLabelInst = firstInst->asCatchLabelInst(); |
| Type *exceptionType = catchLabelInst->getExceptionType(); |
| if (exceptionType != irm.getTypeManager().getSystemObjectType()) { |
| if (Log::isEnabled()) { |
| Log::out() << " isCatchAll case 1" << ::std::endl; |
| } |
| return false; |
| } |
| |
| Inst *nextInst = firstInst->getNextInst(); |
| Node *ciNode = node; |
| int counter = 0; |
| while ( (nextInst && nextInst->getOpcode() != Op_Catch) || !nextInst ) { |
| if (nextInst == NULL) { |
| if (++counter > 3) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " isCatchAll case 5" << ::std::endl; |
| } |
| // don't think this is possible, but bound the loop just in case. |
| return false; |
| } |
| if (!ciNode->hasOnlyOneSuccEdge()) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " isCatchAll case 4" << ::std::endl; |
| } |
| return false; |
| } |
| Node *succ = (*(ciNode->getOutEdges().begin()))->getTargetNode(); |
| ciNode = succ; |
| firstInst = (Inst*)succ->getFirstInst(); |
| nextInst = firstInst->getNextInst(); |
| } |
| } |
| Opnd *opnd = nextInst->getDst(); |
| |
| if (opnd->getType() == irm.getTypeManager().getSystemObjectType()) { |
| // yes |
| catchInstNode = ciNode; |
| caughtOpnd = opnd; |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " isCatchAll case 2" << ::std::endl; |
| } |
| return true; |
| } |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " isCatchAll case 3" << ::std::endl; |
| } |
| return false; |
| } |
| |
| bool FixupSyncEdgesWalker::isMonExit(Node *node, Opnd *&monOpnd, Node *&dispatchNode, |
| Edge *&dispatchEdge) |
| { |
| Inst *lastInst = (Inst*)node->getLastInst(); |
| Opcode opcode = lastInst->getOpcode(); |
| if (!((opcode == Op_TauMonitorExit) || |
| (opcode == Op_OptimisticBalancedMonitorExit))) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << "isMonExit opcode is " << (int) opcode << ::std::endl; |
| } |
| return false; |
| } |
| |
| monOpnd = lastInst->getSrc(0); |
| const Edges &outEdges = node->getOutEdges(); |
| Edges::const_iterator |
| eiter = outEdges.begin(), |
| eend = outEdges.end(); |
| for ( ; eiter != eend; ++eiter) { |
| Edge *e = *eiter; |
| Node *target = e->getTargetNode(); |
| if (target->isDispatchNode()) { |
| dispatchNode = target; |
| dispatchEdge = e; |
| return true; |
| } |
| } |
| assert(0); |
| return false; |
| } |
| |
| bool FixupSyncEdgesWalker::isCatchAllAndMonExit(Node *node, Opnd *&caughtOpnd, |
| Opnd *&monOpnd, Node *&dispatchNode, |
| Edge *&dispatchEdge, |
| Node *&catchInstNode) |
| { |
| catchInstNode = 0; |
| if (node && isCatchAll(node, caughtOpnd, catchInstNode) && |
| isMonExit(catchInstNode, monOpnd, dispatchNode, dispatchEdge)) { |
| // make sure that's all it is |
| assert(catchInstNode); |
| Inst *labelInst = (Inst*)catchInstNode->getFirstInst(); |
| Inst *catchInst = labelInst->getNextInst(); |
| // with DPGO, we may see an incCounter here |
| Inst *thirdInst = catchInst == NULL ? NULL : catchInst->getNextInst(); // monexit or tausafe or incCounter |
| Inst *fourthInst = thirdInst == NULL ? NULL : thirdInst->getNextInst(); // label or monexit or tausafe or incCounter |
| Inst *fifthInst, *sixthInst; |
| if ( fourthInst && fourthInst->getNextInst() == NULL ) { |
| fifthInst = labelInst; |
| }else{ |
| fifthInst = fourthInst == NULL ? NULL : fourthInst->getNextInst(); // label or taumonexit(tausafe) |
| } |
| if ( fifthInst && fifthInst->getNextInst() == NULL ) { |
| sixthInst = labelInst; |
| }else{ |
| sixthInst = fifthInst == NULL ? NULL : fifthInst->getNextInst(); // .. or label |
| } |
| return ((labelInst == fourthInst) |
| || ((labelInst == fifthInst) && |
| ((thirdInst->getOpcode() == Op_TauSafe) || |
| (thirdInst->getOpcode() == Op_IncCounter))) // fourthInst is monExit |
| || ((labelInst == sixthInst) && |
| ((thirdInst->getOpcode() == Op_TauSafe) || |
| (thirdInst->getOpcode() == Op_IncCounter)) && |
| ((fourthInst->getOpcode() == Op_TauSafe) || |
| (fourthInst->getOpcode() == Op_IncCounter))) // fifthInst is monExit |
| ); |
| } |
| return false; |
| } |
| |
| bool FixupSyncEdgesWalker::isJustThrow(Node *node, Opnd *&thrownOpnd, Node *&dispatchNode) |
| { |
| Inst *lastInst = (Inst*)node->getLastInst(); |
| Opcode opcode = lastInst->getOpcode(); |
| if (opcode != Op_Throw) { |
| return false; |
| } |
| Inst *prevInst = lastInst->getPrevInst(); |
| if (prevInst->isLabel()) { |
| // check for dispatchNode |
| assert(node->hasOnlyOneSuccEdge()); |
| const Edges &outEdges = node->getOutEdges(); |
| assert(outEdges.size() == 1); |
| Edge *e = *(outEdges.begin()); |
| Node *target = e->getTargetNode(); |
| assert((target == unwind) || (target->isDispatchNode())); |
| |
| thrownOpnd = lastInst->getSrc(0); |
| dispatchNode = target; |
| return true; |
| } |
| return false; |
| } |
| |
| Node *FixupSyncEdgesWalker::getFirstCatchNode(Node *dispatchNode) |
| { |
| assert(dispatchNode->isDispatchNode()); |
| const Edges &outEdges = dispatchNode->getOutEdges(); |
| Edges::const_iterator |
| eiter = outEdges.begin(), |
| eend = outEdges.end(); |
| for ( ; eiter != eend; ++eiter) { |
| Edge *e = *eiter; |
| Node *target = e->getTargetNode(); |
| if (!target->isDispatchNode()) { |
| return target; |
| } |
| } |
| return NULL; |
| } |
| |
| // look for a particular idiom: |
| // monexit t1 --> Dispatch1 --> Catch(t2:object); monexit t1 --> throw t2 --> Dispatch2 |
| // and convert it to |
| // monexit t1 --> Dispatch2 |
| // unless Dispatch2 == Dispatch1, in which case remove the second monexit and add a self-loop |
| // on the throw node |
| |
| |
| bool |
| FixupSyncEdgesWalker::applyToNode1(Node *node) |
| { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << "applyToNode1 examining node"; FlowGraph::print(Log::out(), node); Log::out() << ::std::endl; |
| } |
| |
| Node *dispatch1 = 0; |
| Edge *dispatch1edge = 0; |
| Opnd *monOpnd1 = 0; |
| if (!isMonExit(node, monOpnd1, dispatch1, dispatch1edge)) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 1" << ::std::endl; |
| } |
| return false; |
| } |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 1b" << ::std::endl; |
| } |
| |
| Node *catchNode = getFirstCatchNode(dispatch1); |
| Opnd *caughtOpnd = 0; |
| Opnd *monOpnd2 = 0; |
| Node *dispatchNode2ignore = 0; |
| Edge *dispatchEdge2ignore = 0; |
| Node *catchInstNode = 0; |
| if (!isCatchAllAndMonExit(catchNode, caughtOpnd, monOpnd2, |
| dispatchNode2ignore, |
| dispatchEdge2ignore, |
| catchInstNode)) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 2" << ::std::endl; |
| } |
| return false; |
| } |
| |
| Edge *outEdge = (Edge *)catchInstNode->getUnconditionalEdge(); |
| assert(outEdge); |
| |
| Node *nextNode = outEdge->getTargetNode(); |
| Opnd *thrownOpnd = 0; |
| Node *dispatch2 = 0; |
| if (!isJustThrow(nextNode, thrownOpnd, dispatch2)) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 3, nextNode is "; |
| FlowGraph::print(Log::out(), nextNode); |
| Log::out() << ::std::endl; |
| } |
| return false; |
| } |
| |
| if (!((monOpnd1 == monOpnd2) && (caughtOpnd == thrownOpnd))) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 4" << ::std::endl; |
| } |
| return false; |
| } |
| |
| // found it |
| if (dispatch1 == dispatch2) { |
| // it's a self-loop |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 5" << ::std::endl; |
| } |
| assert(0); |
| } |
| |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 6" << ::std::endl; |
| } |
| fg.replaceEdgeTarget(dispatch1edge, dispatch2); |
| return true; |
| } |
| |
| // check for Dispatch -> catchall, eliminate any exception edge on the dispatch |
| bool |
| FixupSyncEdgesWalker::applyToNode2(Node *node) |
| { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << "applyToNode2 examining node"; FlowGraph::print(Log::out(), node); Log::out() << ::std::endl; |
| } |
| |
| if (node == unwind) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 1" << ::std::endl; |
| } |
| return false; |
| } |
| if (!node->isDispatchNode()) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 2" << ::std::endl; |
| } |
| return false; |
| } |
| |
| const Edges &outEdges = node->getOutEdges(); |
| Edge *dispatchEdge = 0; |
| |
| Edges::const_iterator |
| eiter = outEdges.begin(), |
| eend = outEdges.end(); |
| for ( ; eiter != eend; ++eiter) { |
| Edge *e = *eiter; |
| Node *target = e->getTargetNode(); |
| if (target->isDispatchNode()) { |
| assert(!dispatchEdge); |
| dispatchEdge = e; |
| } |
| } |
| |
| if (!dispatchEdge) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 3" << ::std::endl; |
| } |
| return false; |
| } |
| |
| Edge *catchEdge = 0; |
| for (eiter = outEdges.begin() ; eiter != eend; ++eiter) { |
| Edge *e = *eiter; |
| if (e->getKind() == Edge::Kind_Catch) { |
| catchEdge = e; |
| |
| Node *catchNode = catchEdge->getTargetNode(); |
| Opnd *scratch; |
| Node *catchInstNode; |
| if (!isCatchAll(catchNode, scratch, catchInstNode)) { |
| continue; |
| } |
| |
| // dispatch node has a catch-all, doesn't need fall-through |
| fg.removeEdge(dispatchEdge); |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 6" << ::std::endl; |
| } |
| return true; |
| } |
| } |
| |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 4" << ::std::endl; |
| } |
| return false; |
| } |
| |
| // look for a particular idiom: |
| // L1:Catch(t2:object); monexit t1 -->(1) Dispatch1 --> L1 |
| // and convert it to |
| // monexit t1 --> Dispatch2 --> Catch(t2:object); --> L1': goto L1' |
| |
| bool |
| FixupSyncEdgesWalker::applyToNode3(Node *node) |
| { |
| |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << "applyToNode3 examining node"; FlowGraph::print(Log::out(), node); Log::out() << ::std::endl; |
| } |
| |
| Node *catchNode = node; |
| Opnd *caughtOpnd = 0; |
| Opnd *monOpnd2 = 0; |
| Node *dispatchNode1 = 0; |
| Edge *dispatchEdge1 = 0; |
| Node *catchInstNode = 0; |
| if (!isCatchAllAndMonExit(catchNode, caughtOpnd, monOpnd2, |
| dispatchNode1, |
| dispatchEdge1, |
| catchInstNode)) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 1" << ::std::endl; |
| } |
| return false; |
| } |
| |
| Inst *catchNodeFirstInst = (Inst*)catchNode->getFirstInst(); |
| CatchLabelInst *catchLabelInst = catchNodeFirstInst->asCatchLabelInst(); |
| assert(catchLabelInst); |
| |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 2" << ::std::endl; |
| } |
| |
| // must be high-priority catch node |
| U_32 order = catchLabelInst->getOrder(); |
| if (order != 0) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 3" << ::std::endl; |
| } |
| return false; |
| } |
| |
| assert(dispatchNode1 && (dispatchNode1->isDispatchNode())); |
| |
| // must be only exception edge to this dispatch |
| if (dispatchNode1->getInEdges().size() != 1) { |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 4" << ::std::endl; |
| } |
| return false; |
| } |
| |
| // find the catch node edge |
| const Edges &outEdges = dispatchNode1->getOutEdges(); |
| Edges::const_iterator |
| eiter = outEdges.begin(), |
| eend = outEdges.end(); |
| for ( ; eiter != eend; ++eiter) { |
| Edge *e = *eiter; |
| Node *target = e->getTargetNode(); |
| if (target == catchNode) { |
| |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 5" << ::std::endl; |
| } |
| |
| TypeManager &typeManager = irm.getTypeManager(); |
| InstFactory &instFactory = irm.getInstFactory(); |
| OpndManager &opndManager = irm.getOpndManager(); |
| Opnd* ex = opndManager.createSsaTmpOpnd(typeManager.getSystemObjectType()); |
| Node *newCatchNode = fg.createBlockNode(instFactory.makeCatchLabel(0, ex->getType())); |
| newCatchNode->appendInst(instFactory.makeCatch(ex)); |
| |
| Node *newLoopNode = fg.createBlockNode(instFactory.makeLabel()); |
| #ifdef _DEBUG |
| Inst *newLoopFirstInst = (Inst*)newLoopNode->getFirstInst(); |
| assert(newLoopFirstInst); |
| LabelInst *newLoopLabelInst = newLoopFirstInst->asLabelInst(); |
| #endif |
| assert(newLoopLabelInst); |
| |
| fg.replaceEdgeTarget(e, newCatchNode); |
| fg.addEdge(newCatchNode, newLoopNode); |
| fg.addEdge(newLoopNode, newLoopNode); |
| return true; |
| } |
| } |
| if (EXTRA_DEBUGGING && Log::isEnabled()) { |
| Log::out() << " case 6" << ::std::endl; |
| } |
| return false; |
| } |
| |
| void |
| FixupSyncEdgesWalker::applyToCFGNode(Node *node) |
| { |
| applyToNode1(node); |
| applyToNode2(node); |
| applyToNode3(node); |
| } |
| |
| class FixupSyncEdgesWalker2 : public FixupSyncEdgesWalker { |
| public: |
| FixupSyncEdgesWalker2(IRManager &irm0, |
| MemoryManager& mm0) |
| : FixupSyncEdgesWalker(irm0, mm0) |
| { |
| }; |
| ~FixupSyncEdgesWalker2() {}; |
| void applyToCFGNode(Node *node); |
| }; |
| |
| void FixupSyncEdgesWalker2::applyToCFGNode(Node *node) |
| { |
| if (node->isDispatchNode() && (node != unwind)) { |
| const Edges &outEdges = node->getOutEdges(); |
| Edges::const_iterator |
| eiter = outEdges.begin(), |
| eend = outEdges.end(); |
| for ( ; eiter != eend; ++eiter) { |
| Edge *e = *eiter; |
| Node *target = e->getTargetNode(); |
| if (target->isDispatchNode()) { |
| return; |
| } |
| } |
| // add an edge to unwind |
| |
| fg.addEdge(node, unwind); |
| } |
| } |
| |
| // synchronization inlining |
| struct ObjectSynchronizationInfo { |
| U_32 threadIdReg; // the register number that holds id of the current thread |
| U_32 syncHeaderOffset; // offset in bytes of the sync header from the start of the object |
| U_32 syncHeaderWidth; // width in bytes of the sync header |
| U_32 lockOwnerOffset; // offset in bytes of the lock owner field from the start of the object |
| U_32 lockOwnerWidth; // width in bytes of the lock owner field in the sync header |
| bool jitClearsCcv; // whether the JIT needs to clear ar.ccv |
| }; |
| |
| // should flush to zero be allowed for floating-point operations ? |
| //bool isFlushToZeroAllowed() { |
| // return flushToZeroAllowed; |
| //} |
| // |
| // Returns true if jit may inline VM functionality for monitorenter and monitorexit |
| // If true is returned 'syncInfo' is filled in with the synchronization parameters. |
| // |
| bool mayInlineObjectSynchronization(ObjectSynchronizationInfo & syncInfo) { |
| assert(0); |
| return false; |
| } |
| |
| |
| void SyncOpt::runPass() |
| { |
| if (Log::isEnabled()) { |
| Log::out() << "Starting SyncOpt Pass" << ::std::endl; |
| Log::out() << " MemManager bytes_allocated= " |
| << (int) mm.bytes_allocated() << ::std::endl; |
| } |
| |
| { |
| const Nodes &nodes = irManager.getFlowGraph().getNodes(); |
| Nodes::const_iterator |
| iter = nodes.begin(), |
| end = nodes.end(); |
| for (; iter != end; ++iter) { |
| Node *node = *iter; |
| Inst *firstInst = (Inst*)node->getFirstInst(); |
| Inst *inst = firstInst->getNextInst(); |
| while (inst != NULL) { |
| Opcode opcode = inst->getOpcode(); |
| switch (opcode) { |
| case Op_TauMonitorEnter: |
| case Op_TauMonitorExit: |
| case Op_TypeMonitorEnter: |
| case Op_TypeMonitorExit: |
| case Op_TauOptimisticBalancedMonitorEnter: |
| case Op_OptimisticBalancedMonitorExit: |
| goto found; |
| default: |
| break; |
| } |
| inst = inst->getNextInst(); |
| } |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "No sync found, skipping SyncOpt Pass" << ::std::endl; |
| Log::out() << " MemManager bytes_allocated= " |
| << (int) mm.bytes_allocated() << ::std::endl; |
| } |
| return; |
| found: |
| ; |
| } |
| |
| if (flags.transform) { |
| if (Log::isEnabled()) { |
| Log::out() << "Preprocessing graph to reduce monExit->monExit loops" << ::std::endl; |
| Log::out() << "PRINTING LOG: IR before sync exception edge fixup" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| } |
| |
| FixupSyncEdgesWalker fixupEdges(irManager, mm); |
| NodeWalk<FixupSyncEdgesWalker>(irManager.getFlowGraph(), fixupEdges); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "PRINTING LOG: IR after sync exception edge fixup" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| } |
| } |
| |
| U_32 lockWidth = 2; |
| |
| ObjectSynchronizationInfo syncInfo; |
| if (mayInlineObjectSynchronization(syncInfo)) |
| lockWidth = syncInfo.lockOwnerWidth; |
| |
| ObjectSynchronizationInfo syncInfoFromVM; |
| bool mayInlineSync = mayInlineObjectSynchronization(syncInfoFromVM); |
| if (flags.balance && mayInlineSync) |
| { |
| TypeManager &typeManager = irManager.getTypeManager(); |
| // should be in the if above, but for debugging on IA32, do it anyway |
| switch (lockWidth) { |
| case 1: |
| lockType = typeManager.getInt8Type(); break; |
| case 2: |
| lockType = typeManager.getInt16Type(); break; |
| case 4: |
| lockType = typeManager.getInt32Type(); break; |
| case 8: |
| lockType = typeManager.getInt64Type(); break; |
| default: |
| assert(0); |
| } |
| lockAddrType = typeManager.getManagedPtrType(lockType); |
| |
| // For each MonitorExit(x) which is preceded on every path by a MonitorEnter(x) without |
| // an intervening call, replace it by BalancedMonitorExit() and all preceding MonitorEnters by |
| // BalancedMonitorEnter(). On any path leading from a BalancedMonitorEnter without a |
| // following BalancedMonitorExit, insert an IncRecCount() |
| |
| if (Log::isEnabled()) { |
| Log::out() << "PRINTING LOG: IR before sync pass 1" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| } |
| |
| findBalancedExits(false, false); // not optimistic, no increccount |
| |
| if (Log::isEnabled()) { |
| Log::out() << "PRINTING LOG: IR after sync pass 1" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| } |
| |
| if (flags.optimistic) { |
| Opnd *syncMethodOpnd = 0; |
| Node *tmpDispatchNode = 0; |
| Node *tmpCatchNode = 0; |
| Node *tmpRethrowNode = 0; |
| |
| MethodDesc &desc = irManager.getMethodDesc(); |
| if (desc.isSynchronized() && !desc.isStatic()) { |
| // synchronized on first param |
| ControlFlowGraph &fg = irManager.getFlowGraph(); |
| Node *entry = fg.getEntryNode(); |
| Inst *firstInst = (Inst*)entry->getFirstInst(); |
| Inst *inst = firstInst->getNextInst(); |
| while (inst != NULL) { |
| if (inst->getOpcode() == Op_DefArg) { |
| break; |
| } |
| inst = inst->getNextInst(); |
| } |
| assert((inst != NULL) && (inst->getOpcode() == Op_DefArg)); |
| Opnd *thisOpnd = inst->getDst(); |
| |
| assert(!syncMethodOpnd); |
| syncMethodOpnd = thisOpnd; |
| } else { |
| } |
| |
| bool needToPatchUnwind = syncMethodOpnd && (irManager.getFlowGraph().getUnwindNode() != NULL); |
| if (needToPatchUnwind) { |
| insertUnwindMonitorExit(syncMethodOpnd, tmpDispatchNode, tmpCatchNode, |
| tmpRethrowNode); |
| } |
| findBalancedExits(true, false); // optimistic, no increccount |
| |
| if (needToPatchUnwind) { |
| removeUnwindMonitorExit(syncMethodOpnd, tmpDispatchNode, tmpCatchNode, |
| tmpRethrowNode); |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "PRINTING LOG: IR after sync pass 2" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| } |
| } |
| } |
| |
| if (flags.transform2) { |
| if (Log::isEnabled()) { |
| Log::out() << "Postrocessing graph to add dispatch edges" << ::std::endl; |
| Log::out() << "PRINTING LOG: IR before dispatch edge fixup" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| } |
| |
| FixupSyncEdgesWalker2 fixupEdges(irManager, mm); |
| NodeWalk<FixupSyncEdgesWalker2>(irManager.getFlowGraph(), fixupEdges); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "PRINTING LOG: IR after dispatch edge fixup" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| } |
| } |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Finished SyncOpt Pass" << ::std::endl; |
| Log::out() << " MemManager bytes_allocated= " |
| << (int) mm.bytes_allocated() << ::std::endl; |
| } |
| } |
| |
| class SyncClique : public UnionFind { |
| private: |
| SyncClique(const SyncClique &o) { assert(0); }; |
| void operator= (const SyncClique &o) { assert(0); }; |
| public: |
| Opnd *opnd; |
| VarOpnd *oldValueVar; |
| U_32 id; |
| static U_32 counter; |
| |
| SyncClique() : UnionFind(), opnd(0), oldValueVar(0), id(++counter) {}; |
| SyncClique(Opnd *opnd0) : UnionFind(), opnd(opnd0), oldValueVar(0), id(++counter) {}; |
| void link(SyncClique *other) { |
| UnionFind::link(other); |
| }; |
| SyncClique *find() { |
| return (SyncClique *) UnionFind::find(); |
| }; |
| void print(::std::ostream &os) { |
| os << "clique" << (int) id; |
| if (opnd) { |
| os << "["; |
| opnd->print(os); |
| os << "]"; |
| } |
| }; |
| }; |
| |
| U_32 SyncClique::counter = 0; |
| #define SYNC_STACK_TOP_DEPTH 20 |
| |
| class SyncOptDfValue { |
| enum State { Top, Normal, Bottom } state; |
| U_32 depth; |
| public: |
| U_32 getDepth() { return depth; }; |
| SyncOptDfValue() |
| : state(Top), depth(SYNC_STACK_TOP_DEPTH) { }; |
| SyncOptDfValue(int) |
| : state(Bottom), depth(0) { }; |
| void init(MemoryManager* mm) { } |
| void print(::std::ostream &os) { |
| switch (state) { |
| case Top: |
| os << "Top"; break; |
| case Normal: |
| os << "[" << (int) depth << "]"; break; |
| case Bottom: |
| os << "Bottom"; break; |
| }; |
| } |
| bool isTop() const { return (state == Top); }; |
| bool isBottom() const { return (state == Bottom); } |
| // returns true when changed |
| bool meetWith(const SyncOptDfValue &other) { |
| if (other.isTop() || isBottom()) { |
| return false; |
| } if (isTop() || other.isBottom()) { |
| *this = other; |
| return true; |
| } else { |
| assert((state == Normal) && (other.state == Normal)); |
| if (depth <= other.depth) { |
| return false; |
| } else { |
| depth = other.depth; |
| return true; |
| } |
| } |
| }; |
| void invalidateMonitors(bool optimistic, bool use_IncRecCount) { |
| if (Log::isEnabled()) { |
| Log::out() << " before invalidateMonitors(): "; |
| print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| if (optimistic) { |
| // no effect; |
| } else { |
| state = Bottom; depth = 0; |
| } |
| if (Log::isEnabled()) { |
| Log::out() << " after invalidateMonitors(): "; |
| print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| }; |
| void openMonitor(Inst *monitorEnter, Opnd *obj) { |
| if (Log::isEnabled()) { |
| Log::out() << " before openMonitor(" |
| << (int) monitorEnter->getId() |
| << "): "; |
| print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| if (isBottom()) { |
| state = Normal; |
| depth = 1; |
| } else if (isTop()) { |
| // no change; |
| } else { |
| assert(state==Normal); |
| if (depth < SYNC_STACK_TOP_DEPTH) { |
| depth += 1; |
| } else { |
| state = Bottom; |
| depth = 0; |
| } |
| } |
| if (Log::isEnabled()) { |
| Log::out() << " after openMonitor(" |
| << (int) monitorEnter->getId() |
| << "): "; |
| print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| } |
| void closeMonitor(Inst *monitorExit, Opnd *obj) { |
| if (Log::isEnabled()) { |
| Log::out() << " before closeMonitor("; |
| monitorExit->print(Log::out()); |
| Log::out() << ", "; |
| obj->print(Log::out()); |
| Log::out() << "): "; |
| print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| if (state == Normal) { |
| depth -= 1; |
| if (depth == 0) { |
| state = Bottom; |
| } |
| } |
| if (Log::isEnabled()) { |
| Log::out() << " after closeMonitor("; |
| obj->print(Log::out()); |
| Log::out() << "): "; |
| print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| }; |
| // applies given inst to this value |
| void apply(Inst *i, MemoryManager &mm, bool optimistic, |
| bool use_IncRecCount) { |
| if (Log::isEnabled()) { |
| Log::out() << "SyncOptDfValue visiting instr "; |
| i->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| switch (i->getOpcode()) { |
| case Op_TauBalancedMonitorEnter: |
| case Op_TauOptimisticBalancedMonitorEnter: |
| if (optimistic) break; // we can ignore this if optimistic |
| case Op_TauMonitorEnter: |
| { |
| Opnd *obj = i->getSrc(0); |
| openMonitor(i, obj); |
| }; break; |
| case Op_OptimisticBalancedMonitorExit: |
| case Op_BalancedMonitorExit: |
| if (optimistic) break; // we can ignore this if optimistic |
| case Op_TauMonitorExit: |
| { |
| Opnd *obj = i->getSrc(0); |
| closeMonitor(i, obj); |
| } break; |
| case Op_DirectCall: |
| case Op_TauVirtualCall: |
| case Op_IndirectCall: |
| case Op_IndirectMemoryCall: |
| case Op_JSR: |
| invalidateMonitors(optimistic, use_IncRecCount); |
| default: |
| break; |
| } |
| } |
| }; |
| |
| class SyncOptTfValue : public DataflowTF<SyncOptDfValue> { |
| MemoryManager &mem; |
| Node *node; |
| bool optimistic; |
| bool use_IncRecCount; |
| public: |
| SyncOptTfValue(MemoryManager &mm, Node *theNode, bool optimistic0, |
| bool use_IncRecCount0) |
| : mem(mm), node(theNode), |
| optimistic(optimistic0), |
| use_IncRecCount(use_IncRecCount0) {}; |
| // returns true if changed |
| bool apply(const SyncOptDfValue &in, SyncOptDfValue &out) { |
| SyncOptDfValue res = in; |
| Inst* firstInst = (Inst*)node->getFirstInst(); |
| Inst * inst = firstInst; |
| do { |
| if (Log::isEnabled()) { |
| Log::out() << "visiting instr "; inst->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| res.apply(inst, mem, optimistic, use_IncRecCount); |
| inst = inst->getNextInst(); |
| } while (inst != NULL); |
| |
| return out.meetWith(res); |
| } |
| }; |
| |
| class SyncOptForwardInstance : public DataflowInstance<SyncOptDfValue> { |
| MemoryManager &mm; |
| bool optimistic; |
| bool use_IncRecCount; |
| public: |
| SyncOptForwardInstance(MemoryManager &mm0, bool optimistic0, bool use_IncRecCount0) |
| : mm(mm0), optimistic(optimistic0), use_IncRecCount(use_IncRecCount0) |
| {}; |
| |
| typedef SyncOptDfValue ValueType; |
| DataflowTF<SyncOptDfValue> *getNodeBehavior(Node *node) { |
| SyncOptTfValue *res = new (mm) SyncOptTfValue(mm, node, |
| optimistic, use_IncRecCount); |
| return res; |
| } |
| SyncOptDfValue getEntryValue() { |
| return SyncOptDfValue(3); // bottom |
| }; |
| }; |
| |
| // an InstWalker |
| class BuildSyncCliquesWalker { |
| friend class SyncOpt; |
| MemoryManager &mem; |
| |
| StlVector<SyncClique *> *currentStack; |
| U_32 currentDepth; |
| SyncClique *bottomClique; |
| |
| StlMap<Inst *, SyncClique *> &monitorCliques; |
| bool optimistic; |
| bool use_IncRecCount; |
| StlMap<Inst *, StlVectorSet<SyncClique *> *> &needRecCount; |
| public: |
| StlVector<SyncClique *> *getStack() { return currentStack; }; |
| U_32 getDepth() { return currentDepth; }; |
| BuildSyncCliquesWalker(MemoryManager &mm, |
| SyncClique *bottomClique0, |
| StlMap<Inst *, SyncClique *> &monitorCliques0, |
| bool optimistic0, |
| bool use_IncRecCount0, |
| StlMap<Inst *, StlVectorSet<SyncClique *> *> &needRecCount0) |
| : mem(mm), |
| currentStack(0), currentDepth(0), |
| bottomClique(bottomClique0), |
| monitorCliques(monitorCliques0), |
| optimistic(optimistic0), |
| use_IncRecCount(use_IncRecCount0), |
| needRecCount(needRecCount0) |
| {}; |
| void startNode(StlVector<SyncClique *> *entryStack, |
| U_32 entryDepth) |
| { |
| currentStack = entryStack; |
| currentDepth = entryDepth; |
| }; |
| SyncClique *newMonitor(Opnd *obj) { |
| return new (mem) SyncClique(obj); |
| }; |
| void applyToInst(Inst *i) { |
| if (Log::isEnabled()) { |
| Log::out() << "SyncOptDfValue visiting instr "; |
| i->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| switch (i->getOpcode()) { |
| case Op_TauBalancedMonitorEnter: |
| case Op_TauOptimisticBalancedMonitorEnter: |
| if (optimistic) break; // we can ignore this if optimistic |
| case Op_TauMonitorEnter: |
| { |
| Opnd *obj = i->getSrc(0); |
| openMonitor(i, obj); |
| }; break; |
| case Op_OptimisticBalancedMonitorExit: |
| case Op_BalancedMonitorExit: |
| if (optimistic) break; // we can ignore this if optimistic |
| case Op_TauMonitorExit: |
| { |
| Opnd *obj = i->getSrc(0); |
| closeMonitor(i, obj); |
| } break; |
| case Op_DirectCall: |
| case Op_TauVirtualCall: |
| case Op_IndirectCall: |
| case Op_IndirectMemoryCall: |
| case Op_JSR: |
| invalidateMonitors(i); |
| break; |
| default: |
| break; |
| } |
| } |
| void invalidateMonitors(Inst *i) { |
| if (Log::isEnabled()) { |
| Log::out() << " before invalidateMonitors(" |
| << (int) i->getId() |
| << "), depth=" |
| << (int) currentDepth |
| << ::std::endl; |
| } |
| if (!optimistic) { |
| if (currentDepth != 0) { |
| assert(currentStack); |
| if (use_IncRecCount) { |
| StlVectorSet<SyncClique *> *openSet = new (mem) StlVectorSet<SyncClique *>(mem); |
| for (U_32 j=0; j < currentDepth; ++j) { |
| openSet->insert((*currentStack)[j]); |
| } |
| needRecCount[i] = openSet; |
| // leaving a balanced area, cancel all monitors. |
| currentDepth = 0; |
| } else { |
| for (U_32 i=0; i<currentDepth; ++i) { |
| // invalidate all open monitors |
| if (Log::isEnabled()) { |
| Log::out() << " linking01 "; |
| (*currentStack)[i]->print(Log::out()); |
| Log::out() << " to "; |
| bottomClique->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| (*currentStack)[i]->link(bottomClique); |
| } |
| currentDepth = 0; |
| } |
| } |
| } |
| if (Log::isEnabled()) { |
| Log::out() << " after invalidateMonitors(" |
| << (int) i->getId() |
| << "), depth=" |
| << (int) currentDepth |
| << ::std::endl; |
| } |
| }; |
| void openMonitor(Inst *monitorEnter, Opnd *obj) { |
| if (Log::isEnabled()) { |
| Log::out() << " before openMonitor(" |
| << (int) monitorEnter->getId() |
| << ", "; |
| obj->print(Log::out()); |
| Log::out() << "), depth=" |
| << (int) currentDepth |
| << ::std::endl; |
| } |
| assert(currentDepth <= SYNC_STACK_TOP_DEPTH); |
| |
| SyncClique *clique = newMonitor(obj); |
| |
| monitorCliques[monitorEnter] = clique; |
| (*currentStack)[currentDepth] = clique; |
| currentDepth += 1; |
| |
| if (Log::isEnabled()) { |
| Log::out() << " after openMonitor(" |
| << (int) monitorEnter->getId() |
| << ", "; |
| obj->print(Log::out()); |
| Log::out() << "): depth=" |
| << (int) currentDepth |
| << ::std::endl; |
| } |
| } |
| void closeMonitor(Inst *monitorExit, Opnd *obj) { |
| if (Log::isEnabled()) { |
| Log::out() << " before closeMonitor(" |
| << (int) monitorExit->getId() |
| << ", "; |
| obj->print(Log::out()); |
| Log::out() << "): depth=" |
| << (int) currentDepth |
| << ::std::endl; |
| } |
| |
| if (currentDepth > 0) { |
| assert(currentStack); |
| SyncClique *currentMonitor = (*currentStack)[currentDepth-1]; |
| currentMonitor = currentMonitor->find(); |
| if (Log::isEnabled()) { |
| Log::out() << " setting monitorCliques[" |
| << (int) monitorExit->getId() |
| << "] = "; |
| currentMonitor->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| monitorCliques[monitorExit] = currentMonitor; |
| |
| // now, we can't check whether opnd == obj at this point, since opnd |
| // may not be set yet (it may come from another block); instead, we |
| // assume it is correct, but record the cliques which must be invalidated |
| // or corrected (with RecCount) if it is found to be unbalanced when |
| // code is modified. |
| |
| currentDepth -= 1; |
| if (currentDepth > 0) { |
| assert(currentStack); |
| // record cliques which depend on this opnd matching |
| StlVectorSet<SyncClique *> *openSet = new (mem) StlVectorSet<SyncClique *>(mem); |
| for (U_32 j=0; j < currentDepth; ++j) { |
| openSet->insert((*currentStack)[j]); |
| } |
| needRecCount[monitorExit] = openSet; |
| } |
| } else { |
| if (Log::isEnabled()) { |
| Log::out() << " currentDepth is 0 at monitorExit; setting " |
| << " monitorCliques[monitorExit] = bottom" << ::std::endl; |
| } |
| monitorCliques[monitorExit] = bottomClique; |
| } |
| if (Log::isEnabled()) { |
| Log::out() << " after closeMonitor(" |
| << (int) monitorExit->getId() |
| << ", "; |
| obj->print(Log::out()); |
| Log::out() << "), depth=" |
| << (int) currentDepth |
| << ::std::endl; |
| } |
| }; |
| }; |
| |
| VarOpnd * |
| SyncOpt::getLockVar(Opnd *obj) |
| { |
| OpndManager &opndManager = irManager.getOpndManager(); |
| InstFactory &instFactory = irManager.getInstFactory(); |
| VarOpnd *thisLockVar = lockVar[obj]; |
| if (!thisLockVar) { |
| thisLockVar = opndManager.createVarOpnd(lockAddrType, |
| false); |
| |
| Opnd *lockAddrTmp = opndManager.createSsaTmpOpnd(lockAddrType); |
| Inst *ldLockInst = instFactory.makeLdLockAddr(lockAddrTmp, obj); |
| |
| Inst *stVarLockAddr = instFactory.makeStVar(thisLockVar, lockAddrTmp); |
| |
| Inst *objDef = obj->getInst(); |
| if (objDef->getOperation().mustEndBlock()) { |
| // can't insert right after objectdef |
| Node *objDefNode = objDef->getNode(); |
| Edge *outEdge = objDefNode->getUnconditionalEdge(); |
| assert(outEdge); |
| Node *nextNode = outEdge->getTargetNode(); |
| Inst *nextInst = (Inst*)nextNode->getSecondInst(); |
| while (nextInst!=NULL && nextInst->getOpcode() == Op_Phi) { |
| nextInst = nextInst->getNextInst(); |
| } |
| ldLockInst->insertBefore(nextInst); |
| } else { |
| ldLockInst->insertAfter(objDef); |
| } |
| stVarLockAddr->insertAfter(ldLockInst); |
| |
| lockVar[obj] = thisLockVar; |
| } |
| return thisLockVar; |
| } |
| |
| VarOpnd * |
| SyncOpt::getOldValueOpnd(SyncClique *clique) |
| { |
| VarOpnd *oldValueVar = clique->oldValueVar; |
| if (!oldValueVar) { |
| OpndManager &opndManager = irManager.getOpndManager(); |
| oldValueVar = opndManager.createVarOpnd(lockType, |
| false); |
| clique->oldValueVar = oldValueVar; |
| } |
| return oldValueVar; |
| } |
| |
| |
| // Stage 1(a): solve a DF problem to find depth of stack of open monitors at each |
| // block; this gives balanced exits; returns |
| // we ignore exception edges for now |
| // The result is the total count of stack elements in entrySolution and exitSolution, |
| // which are also initialized here |
| |
| U_32 SyncOpt::findBalancedExits_Stage1(bool optimistic, bool use_IncRecCount, U_32 numNodes, |
| SyncOptDfValue *&entrySolution, SyncOptDfValue *&exitSolution) |
| { |
| SyncOptForwardInstance findBalancedExits(mm, optimistic, use_IncRecCount); |
| |
| ControlFlowGraph &fg = irManager.getFlowGraph(); |
| solve<SyncOptDfValue>(&fg, findBalancedExits, true, // forwards |
| mm, |
| entrySolution, exitSolution, true); // ignore exception edges |
| U_32 numCliques = 0; |
| { |
| for (U_32 i = 0; i<numNodes; i++) { |
| numCliques += entrySolution[i].getDepth(); |
| numCliques += exitSolution[i].getDepth(); |
| } |
| } |
| return numCliques; |
| } |
| |
| void SyncOpt::linkStacks(U_32 depth1, SyncClique *stack1, |
| U_32 depth2, SyncClique *stack2, |
| SyncClique *bottomClique) |
| { |
| // link |
| // stack1[depth1-1],..,stack1[0],bot,.. |
| // stack2[depth2-1],..,stack2[0],bot,.. |
| U_32 mindepth = ::std::min(depth1, depth2); |
| U_32 i = 0; |
| for ( ; i < mindepth; ++i) { |
| if (Log::isEnabled()) { |
| Log::out() << " linking02 "; |
| stack2[depth2-1-i].print(Log::out()); |
| Log::out() << " with "; |
| stack1[depth1-1-i].print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| stack2[depth2-1-i].link(&stack1[depth1-1-i]); |
| } |
| for ( ; i < depth1; ++i) { |
| if (Log::isEnabled()) { |
| Log::out() << " linking03 "; |
| stack1[depth1-1-i].print(Log::out()); |
| Log::out() << " with bottom ("; |
| bottomClique->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| stack1[depth1-1-i].link(bottomClique); |
| } |
| for ( ; i < depth2; ++i) { |
| if (Log::isEnabled()) { |
| Log::out() << " linking04 "; |
| stack2[depth2-1-i].print(Log::out()); |
| Log::out() << " with bottom ("; |
| bottomClique->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| stack2[depth2-1-i].link(bottomClique); |
| } |
| } |
| |
| // starting with cliques in inStack[0..depthIn-1], walk node with walker |
| // and union result with outStack[0..depthOut-1]. stackspace is available for scratch. |
| void SyncOpt::findBalancedExits_Stage2a(Node *node, |
| U_32 depthIn, |
| SyncClique *inStack, |
| U_32 depthOut, |
| SyncClique *outStack, |
| BuildSyncCliquesWalker &walker, |
| StlVector<SyncClique *> &stackspace, // scratch area |
| SyncClique *bottomClique) |
| { |
| if (depthIn > 0) { |
| assert(depthIn <= SYNC_STACK_TOP_DEPTH); |
| for (U_32 i=0; i<depthIn; i++) { |
| stackspace[i] = &inStack[i]; |
| } |
| } |
| assert(&walker.mem == &mm); |
| if (Log::isEnabled()) { |
| Log::out() << " Before walk, depthIn=" << (int) depthIn |
| << ", stack = "; |
| for (U_32 i=0; i<depthIn; i++) { |
| stackspace[i]->print(Log::out()); |
| Log::out() << " "; |
| } |
| Log::out() << ::std::endl; |
| } |
| assert(&walker.mem == &mm); |
| walker.startNode(&stackspace, depthIn); |
| assert(&walker.mem == &mm); |
| WalkInstsInBlock<true, BuildSyncCliquesWalker>(node, walker); // in order |
| |
| assert(&walker.mem == &mm); |
| U_32 currentDepth = walker.getDepth(); |
| StlVector<SyncClique *> *currentStack = walker.getStack(); |
| assert(currentStack); |
| |
| if (Log::isEnabled()) { |
| Log::out() << " After walk of node #" |
| << (int) node->getId() |
| << ", currentDepth=" |
| << (int) currentDepth |
| << ", stack = "; |
| for (U_32 i=0; i<currentDepth; i++) { |
| (*currentStack)[i]->print(Log::out()); |
| Log::out() << " "; |
| } |
| Log::out() << ::std::endl; |
| } |
| |
| U_32 mindepth = ::std::min(currentDepth, depthOut); |
| if (Log::isEnabled()) { |
| Log::out() << " Linking05 with outstack of depth " |
| << (int) depthOut |
| << ", outstack = "; |
| for (U_32 i=0; i<currentDepth; i++) { |
| outStack[i].print(Log::out()); |
| Log::out() << " "; |
| } |
| Log::out() << ::std::endl; |
| } |
| { |
| U_32 i = 0; |
| for ( ; i < mindepth; ++i) { |
| if (Log::isEnabled()) { |
| Log::out() << " linking06 "; |
| (*currentStack)[currentDepth-1-i]->print(Log::out()); |
| Log::out() << " with "; |
| outStack[depthOut-1-i].print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| (*currentStack)[currentDepth-1-i]->link(&outStack[depthOut-1-i]); |
| } |
| for ( ; i < currentDepth; ++i) { |
| if (Log::isEnabled()) { |
| Log::out() << " linking07 "; |
| (*currentStack)[currentDepth-1-i]->print(Log::out()); |
| Log::out() << " with bottom ("; |
| bottomClique->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| (*currentStack)[currentDepth-1-i]->link(bottomClique); |
| } |
| for ( ; i < depthOut; ++i) { |
| if (Log::isEnabled()) { |
| Log::out() << " linking08 "; |
| outStack[depthOut-1-i].print(Log::out()); |
| Log::out() << " with bottom ("; |
| bottomClique->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| outStack[depthOut-1-i].link(bottomClique); |
| } |
| } |
| } |
| |
| // Stage 2: associate a SyncClique with every open monitor, apply nodes to unify |
| // cliques with appropriate successors, and associate a clique with each |
| // monitor operation |
| // now we ignore exception edges out of monitorexit nodes unless optimistic |
| void SyncOpt::findBalancedExits_Stage2(bool optimistic, bool use_IncRecCount, |
| SyncOptDfValue *entrySolution, |
| SyncOptDfValue *exitSolution, |
| SyncClique *bottomClique, |
| SyncClique **entryCliques, SyncClique **exitCliques, |
| StlMap<Inst *, StlVectorSet<SyncClique *> *> &needRecCount, |
| StlMap<Inst *, SyncClique *> &monitorCliques) |
| { |
| BuildSyncCliquesWalker walker(mm, bottomClique, monitorCliques, |
| optimistic, use_IncRecCount, |
| needRecCount); |
| StlVector<SyncClique *>stackspace(mm, SYNC_STACK_TOP_DEPTH+1, 0); |
| |
| ControlFlowGraph &fg = irManager.getFlowGraph(); |
| const Nodes &nodes = fg.getNodes(); |
| assert(&walker.mem == &mm); |
| Nodes::const_iterator |
| iter = nodes.begin(), |
| end = nodes.end(); |
| for (; iter != end; ++iter) { |
| Node *node = *iter; |
| U_32 nodeId = node->getId(); |
| U_32 depthIn = entrySolution[nodeId].getDepth(); |
| if (Log::isEnabled()) { |
| Log::out() << "Considering node " << (int) nodeId |
| << " with depthIn=" << (int) depthIn |
| << ::std::endl; |
| } |
| if (Log::isEnabled()) { |
| if (!entrySolution[nodeId].isTop()) { |
| Log::out() << "Node solution is not Top" << ::std::endl; |
| } else { |
| Log::out() << "Node solution is Top" << ::std::endl; |
| } |
| } |
| // propagate node solution through node to exits |
| |
| U_32 depthOut = exitSolution[nodeId].getDepth(); |
| assert(&walker.mem == &mm); |
| findBalancedExits_Stage2a(node, |
| depthIn, entryCliques[nodeId], |
| depthOut, exitCliques[nodeId], |
| walker, stackspace, bottomClique); |
| |
| // link with every successor except for exception edges from MonitorExit |
| const Edges &outEdges = node->getOutEdges(); |
| Edges::const_iterator |
| eiter = outEdges.begin(), |
| eend = outEdges.end(); |
| for ( ; eiter != eend; ++eiter) { |
| Edge *e = *eiter; |
| Node *target = e->getTargetNode(); |
| |
| // skip any exception edge from a MonitorExit unless optimistic |
| if (!optimistic && target->isDispatchNode()) { |
| Inst *lastInst = (Inst*)node->getLastInst(); |
| if ((lastInst->getOpcode() == Op_TauMonitorExit) || |
| (lastInst->getOpcode() == Op_OptimisticBalancedMonitorExit)) { |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Skipping monitor exception edge from node #" |
| << (int) nodeId |
| << " to dispatch node #" |
| << (int) target->getId() |
| << ::std::endl; |
| } |
| |
| // skip this edge |
| continue; |
| } |
| } |
| |
| // link with successor inputs |
| U_32 targetId = target->getId(); |
| SyncClique *targetStack = entryCliques[targetId]; |
| U_32 targetDepth = entrySolution[targetId].getDepth(); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Linking09 output of node #" |
| << (int) nodeId |
| << " with input of node #" |
| << (int) targetId |
| << ::std::endl; |
| } |
| linkStacks(depthOut, exitCliques[nodeId], |
| targetDepth, targetStack, |
| bottomClique); |
| } |
| } |
| // link any open monitor at the exit node with bottom |
| { |
| Node *exitNode = fg.getExitNode(); |
| U_32 exitId = exitNode->getId(); |
| U_32 depthIn = entrySolution[exitId].getDepth(); |
| SyncClique *exitStack = entryCliques[exitId]; |
| for (U_32 i=0; i< depthIn; ++i) { |
| if (Log::isEnabled()) { |
| Log::out() << " for exit node: i=" |
| << (int) i; |
| Log::out() << " linking10 "; |
| exitStack[i].print(Log::out()); |
| Log::out() << " to bottom ("; |
| bottomClique->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| exitStack[i].link(bottomClique); |
| } |
| } |
| } |
| |
| bool SyncOpt::monitorExitIsBad(Inst *monExit, SyncClique *clique, |
| SyncClique *cliqueRoot, SyncClique *bottomCliqueRoot) { |
| if (Log::isEnabled()) { |
| Log::out() << "Considering monitorExit instruction: "; |
| monExit->print(Log::out()); |
| Log::out() << " with "; |
| clique->print(Log::out()); |
| Log::out() << ", with root = "; |
| cliqueRoot->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| |
| if (cliqueRoot == bottomCliqueRoot) { |
| if (Log::isEnabled()) { |
| Log::out() << " clique == bottom" << ::std::endl; |
| } |
| return true; |
| } else if (!cliqueRoot->opnd) { |
| if (Log::isEnabled()) { |
| Log::out() << " cliqueRoot->opnd = NULL" << ::std::endl; |
| } |
| return true; |
| } else if (cliqueRoot->opnd != monExit->getSrc(0)) { |
| if (Log::isEnabled()) { |
| Log::out() << " clique->opnd != monitorExit->opnd:" << ::std::endl; |
| Log::out() << " Clique="; |
| if (cliqueRoot->opnd) |
| cliqueRoot->opnd->print(Log::out()); |
| else |
| Log::out() << "NULL"; |
| Log::out() << "; obj = "; |
| monExit->getSrc(0)->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| return true; |
| } |
| return false; |
| } |
| |
| // stage 3a: |
| // iteratively find bad monitor Insts |
| // on each iteration, |
| // find new bad monitor exit Insts (those whose clique =~ bottom, which haven't been processed) |
| // union their cliques with bottom |
| // also union their dependent monitors with bottom |
| // add the effect of the exception edge from the bad monitor exit (may union more with bottom) |
| // repeat until it is stable |
| void SyncOpt::findBalancedExits_Stage3(bool optimistic, bool use_IncRecCount, |
| SyncOptDfValue *entrySolution, |
| SyncOptDfValue *exitSolution, |
| SyncClique *bottomClique, |
| SyncClique **entryCliques, SyncClique **exitCliques, |
| StlMap<Inst *, StlVectorSet<SyncClique *> *> &needRecCount, |
| StlMap<Inst *, SyncClique *> &monitorCliques) |
| { |
| // first scan all monitor instructions and make sure their Opnd matches |
| // match their clique's Opnd; if not, link to bottom. |
| { |
| StlMap<Inst *, SyncClique *>::iterator |
| miter = monitorCliques.begin(), |
| mend = monitorCliques.end(); |
| for ( ; miter != mend; ++miter) { |
| Inst *inst = (*miter).first; |
| SyncClique *clique = (*miter).second; |
| |
| Opnd *obj = inst->getSrc(0); |
| clique = clique->find(); |
| if (clique->opnd) { |
| if (clique->opnd != obj) { |
| clique->link(bottomClique); |
| } |
| } else { |
| clique->opnd = obj; |
| } |
| } |
| bottomClique = bottomClique->find(); |
| } |
| // now any monitor inst in a clique with another monitor inst with |
| // un-matching opnd has been linked to bottom. |
| |
| StlVectorSet<SyncClique *> badMonitors(mm); |
| |
| StlVectorSet<SyncClique *> dependentOnBadMonitors(mm); |
| StlVectorSet<Inst *> badMonitorExits(mm); |
| StlVector<Inst *> newBadMonitorExits(mm); |
| SyncClique *bottomCliqueRoot = bottomClique->find(); |
| |
| if (Log::isEnabled()) { |
| Log::out() << " beginning Stage3" << ::std::endl; |
| } |
| |
| bool needToCheckAgain = true; |
| while (needToCheckAgain) { |
| needToCheckAgain = false; |
| |
| if (Log::isEnabled()) { |
| Log::out() << " beginning Stage3 iteration" << ::std::endl; |
| } |
| |
| StlMap<Inst *, SyncClique *>::iterator |
| miter = monitorCliques.begin(), |
| mend = monitorCliques.end(); |
| for ( ; miter != mend; ++miter) { |
| Inst *inst = (*miter).first; |
| if ((inst->getOpcode() != Op_TauMonitorExit) && |
| (inst->getOpcode() != Op_OptimisticBalancedMonitorExit)) |
| continue; |
| |
| SyncClique *clique = (*miter).second; |
| SyncClique *cliqueRoot = clique->find(); |
| |
| if (badMonitorExits.has(inst)) { |
| continue; |
| } |
| bool badclique = false; |
| |
| badclique = monitorExitIsBad(inst, clique, cliqueRoot, bottomCliqueRoot); |
| |
| // at this point, opnd should be set for each clique root; check whether |
| // monitorExit opnd matches the clique opnd, if not, add it to newBadMonitorExits. |
| if (badclique) { |
| newBadMonitorExits.push_back(inst); |
| |
| // process any exception edge to merge monitors. If anything changed, we |
| // will have to re-process everything. |
| |
| StlMap<Inst *, StlVectorSet<SyncClique *> *>::iterator |
| foundDeps = needRecCount.find(inst), |
| endDeps = needRecCount.end(); |
| if (foundDeps != endDeps) { |
| StlVectorSet<SyncClique *> *deps = (*foundDeps).second; |
| dependentOnBadMonitors.insert(deps->begin(), deps->end()); |
| } |
| } |
| } |
| |
| if (Log::isEnabled()) { |
| Log::out() << " done Stage3a" << ::std::endl; |
| } |
| |
| // union all new badMonitorExits with bottom |
| StlVectorSet<Inst *>::iterator |
| monExitIter = newBadMonitorExits.begin(), |
| monExitEnd = newBadMonitorExits.end(); |
| for ( ; monExitIter != monExitEnd; ++monExitIter) { |
| Inst *monExit = *monExitIter; |
| |
| SyncClique *clique = monitorCliques[monExit]; |
| if (Log::isEnabled()) { |
| Log::out() << " linking11 badMonitor "; |
| clique->print(Log::out()); |
| Log::out() << " with bottom ("; |
| bottomClique->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| bottomCliqueRoot->link(clique); |
| } |
| bottomCliqueRoot = bottomCliqueRoot->find(); |
| |
| if (Log::isEnabled()) { |
| Log::out() << " done Stage3b" << ::std::endl; |
| } |
| |
| // merge any new dependent monitors from dependentOnBadMonitors |
| bool foundDependentMonitor = false; |
| StlVectorSet<SyncClique *>::iterator |
| depMonIter = dependentOnBadMonitors.begin(), |
| depMonEnd = dependentOnBadMonitors.end(); |
| for ( ; depMonIter != depMonEnd; ++depMonIter) { |
| SyncClique *depMonitor = *depMonIter; |
| SyncClique *depMonRoot = depMonitor->find(); |
| if (depMonRoot != bottomCliqueRoot) { |
| foundDependentMonitor = true; // we need to re-iterate |
| |
| if (Log::isEnabled()) { |
| Log::out() << " linking12 depMonRoot "; |
| depMonRoot->print(Log::out()); |
| Log::out() << " with bottom ("; |
| bottomCliqueRoot->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| |
| bottomCliqueRoot->link(depMonRoot); |
| bottomCliqueRoot = bottomCliqueRoot->find(); // may have changed |
| } |
| } |
| |
| if (Log::isEnabled()) { |
| Log::out() << " done Stage3c" << ::std::endl; |
| } |
| |
| // add effect of the exception edge from each newly bad exit, |
| // unless optimistic (in which case we included it previously) |
| bool differs = foundDependentMonitor; |
| if (!optimistic) { |
| StlVectorSet<Inst *>::iterator |
| newBadExitIter = newBadMonitorExits.begin(), |
| newBadExitEnd = newBadMonitorExits.end(); |
| for ( ; newBadExitIter != newBadExitEnd; ++newBadExitIter) { |
| Inst *newBadExit = *newBadExitIter; |
| Node *node = newBadExit->getNode(); |
| U_32 nodeId = node->getId(); |
| U_32 nodeDepth = exitSolution[nodeId].getDepth(); |
| |
| Edge *e = (Edge *)node->getExceptionEdge(); |
| Node *target = e->getTargetNode(); |
| U_32 targetId = target->getId(); |
| U_32 targetDepth = entrySolution[targetId].getDepth(); |
| |
| SyncClique *nodeStack = exitCliques[nodeId]; |
| SyncClique *targetStack = entryCliques[targetId]; |
| if (!differs) { |
| if (targetDepth != nodeDepth) { |
| differs = true; |
| } else { |
| for (U_32 i = 0; i < targetDepth; ++i) { |
| if (nodeStack[i].find() != targetStack[i].find()) { |
| differs = true; |
| break; |
| } |
| } |
| } |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "Linking13 exception edge from bad monexit at node #" |
| << (int) nodeId |
| << " to dispatch node #" |
| << (int) targetId |
| << ::std::endl; |
| } |
| linkStacks(nodeDepth, nodeStack, |
| targetDepth, targetStack, |
| bottomCliqueRoot); |
| } |
| } |
| |
| if (Log::isEnabled()) { |
| Log::out() << " done Stage3d" << ::std::endl; |
| } |
| |
| badMonitorExits.insert(newBadMonitorExits.begin(), newBadMonitorExits.end()); |
| newBadMonitorExits.clear(); |
| |
| needToCheckAgain = differs; |
| |
| if (Log::isEnabled()) { |
| Log::out() << " done Stage3 iteration" << ::std::endl; |
| } |
| } |
| } |
| |
| |
| void SyncOpt::findBalancedExits(bool optimistic, bool use_IncRecCount) |
| { |
| OpndManager &opndManager = irManager.getOpndManager(); |
| InstFactory &instFactory = irManager.getInstFactory(); |
| |
| ControlFlowGraph &fg = irManager.getFlowGraph(); |
| U_32 numNodes = fg.getMaxNodeId(); |
| SyncOptDfValue *entrySolution, *exitSolution; |
| U_32 numCliques = findBalancedExits_Stage1(optimistic, use_IncRecCount, numNodes, |
| entrySolution, exitSolution); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "numNodes is " << (int) numNodes << ::std::endl; |
| Log::out() << "numCliques is " << (int) numCliques << ::std::endl; |
| } |
| |
| SyncClique *cliquesHeap = new (mm) SyncClique[numCliques]; |
| SyncClique **entryCliques = new (mm) SyncClique *[numNodes]; |
| SyncClique **exitCliques = new (mm) SyncClique *[numNodes]; |
| U_32 cliqueHeapIndex = 0; |
| { |
| for (U_32 i = 0; i<numNodes; i++) { |
| U_32 lin = entrySolution[i].getDepth(); |
| U_32 lout = exitSolution[i].getDepth(); |
| |
| entryCliques[i] = &cliquesHeap[cliqueHeapIndex]; |
| cliqueHeapIndex += lin; |
| exitCliques[i] = &cliquesHeap[cliqueHeapIndex]; |
| cliqueHeapIndex += lout; |
| |
| if (Log::isEnabled()) { |
| Log::out() << " node " << (int) i << " has " << (int) lin << " cliques in: [ "; |
| for (U_32 j = 0; j<lin; ++j) { |
| entryCliques[i][j].print(Log::out()); |
| Log::out() << " "; |
| } |
| Log::out() << "]" << ::std::endl; |
| |
| Log::out() << " node " << (int) i << " has " << (int) lout << " cliques out: [ "; |
| for (U_32 jout = 0; jout<lout; ++jout) { |
| exitCliques[i][jout].print(Log::out()); |
| Log::out() << " "; |
| } |
| Log::out() << "]" << ::std::endl; |
| } |
| } |
| } |
| assert(cliqueHeapIndex <= numCliques); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "finished dataflow solution" << ::std::endl; |
| } |
| |
| SyncClique *bottomClique = new (mm) SyncClique(); |
| if (Log::isEnabled()) { |
| Log::out() << "Bottom clique is "; |
| bottomClique->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| |
| // process each node and edge (except exception edges) to union monitor cliques |
| StlMap<Inst *, StlVectorSet<SyncClique *> *> needRecCount(mm); |
| StlMap<Inst *, SyncClique *> monitorCliques(mm); |
| findBalancedExits_Stage2(optimistic, use_IncRecCount, |
| entrySolution, exitSolution, |
| bottomClique, entryCliques, exitCliques, |
| needRecCount, monitorCliques); |
| |
| // now, each monitorEnter/Exit has an associated clique, |
| // and we have applied UnionFind::link to them appropriately (ignoring monexit exceptions) |
| // if usereccount, then needRecCount[invalidateInst]=cliques to be incremented |
| // before the invalidating instruction |
| // also, needRecCount[monitorExit]=cliques to be invalidated if monitorExit opnd |
| // doesn't match, or if the monitorExit clique is/was invalidated |
| SyncClique *bottomCliqueRoot = bottomClique->find(); |
| if (Log::isEnabled()) { |
| Log::out() << "Bottom clique root is "; |
| bottomCliqueRoot->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| |
| // stage 3a |
| |
| // stage 3b: |
| // at this point, opnd should be set for each clique root; check whether |
| // monitorExit opnd matches the clique opnd, if not, add it to newBadMonitorExits. |
| |
| findBalancedExits_Stage3(optimistic, use_IncRecCount, |
| entrySolution, exitSolution, |
| bottomClique, entryCliques, exitCliques, |
| needRecCount, monitorCliques); |
| |
| // at this point, a monitor inst monInst is unbalanced if monitorCliques[monInst] =~ bottom |
| |
| // stage 3: Now that we know which cliques are balanceable, modify code. |
| // Other cliques we don't bother with. |
| { |
| StlMap<Inst *, SyncClique *>::iterator |
| miter = monitorCliques.begin(), |
| mend = monitorCliques.end(); |
| for ( ; miter != mend; ++miter) { |
| Inst *inst = (*miter).first; |
| SyncClique *clique = (*miter).second; |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Considering balancing instruction: "; |
| inst->print(Log::out()); |
| Log::out() << " with "; |
| clique->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| |
| clique = clique->find(); |
| if ((clique == bottomCliqueRoot)) { |
| if (Log::isEnabled()) { |
| Log::out() << " Clique == bottom" << ::std::endl; |
| } |
| continue; |
| } |
| { |
| // we can balance it |
| Opnd *obj = inst->getSrc(0); |
| assert(obj == clique->opnd); |
| |
| VarOpnd *lockVar = getLockVar(obj); |
| VarOpnd *oldValueVar = getOldValueOpnd(clique); |
| |
| Opnd *lockAddrTmp = opndManager.createSsaTmpOpnd(lockAddrType); |
| Opnd *oldValueTmp = opndManager.createSsaTmpOpnd(lockType); |
| |
| Opnd *tau = 0; |
| switch (inst->getOpcode()) { |
| case Op_TauOptimisticBalancedMonitorEnter: |
| if (optimistic) break; // we can ignore this if optimistic, otherwise try to convert it to unoptimistic balmonenter |
| tau = inst->getSrc(2); |
| case Op_TauMonitorEnter: |
| { |
| if (!tau) |
| tau = inst->getSrc(1); |
| assert(tau->getType()->tag == Type::Tau); |
| |
| Inst *ldVarLockAddr = instFactory.makeLdVar(lockAddrTmp, lockVar); |
| Inst *balmonenter = (optimistic |
| ? instFactory.makeTauOptimisticBalancedMonitorEnter(oldValueTmp, |
| obj, |
| lockAddrTmp, |
| tau) |
| : instFactory.makeTauBalancedMonitorEnter(oldValueTmp, |
| obj, |
| lockAddrTmp, |
| tau)); |
| Inst *stVarOldValue = instFactory.makeStVar(oldValueVar, oldValueTmp); |
| ldVarLockAddr->insertAfter(inst); |
| balmonenter->insertAfter(ldVarLockAddr); |
| stVarOldValue->insertAfter(balmonenter); |
| inst->unlink(); |
| } |
| break; |
| case Op_OptimisticBalancedMonitorExit: |
| if (optimistic) break; // we can ignore this if optimistic, otherwise convert it to un-optimistic balmonexit |
| case Op_TauMonitorExit: |
| { |
| Inst *ldVarLockAddr = instFactory.makeLdVar(lockAddrTmp, lockVar); |
| Inst *ldVarOldValue = instFactory.makeLdVar(oldValueTmp, |
| oldValueVar); |
| Inst *balmonexit = (optimistic |
| ? instFactory.makeOptimisticBalancedMonitorExit(obj, |
| lockAddrTmp, |
| oldValueTmp) |
| : instFactory.makeBalancedMonitorExit(obj, |
| lockAddrTmp, |
| oldValueTmp)); |
| ldVarLockAddr->insertAfter(inst); |
| ldVarOldValue->insertAfter(ldVarLockAddr); |
| balmonexit->insertAfter(ldVarOldValue); |
| |
| if (!optimistic) { |
| // remove exception edge |
| Node *node = inst->getNode(); |
| Edge* edge = (Edge *)node->getExceptionEdge(); |
| assert(edge != NULL); |
| fg.removeEdge(edge); |
| } |
| |
| inst->unlink(); |
| } |
| break; |
| default: |
| break; |
| } |
| } |
| } |
| } |
| if (use_IncRecCount) { |
| StlVectorSet<SyncClique *> doneCliques(mm); |
| StlMap<Inst *, StlVectorSet<SyncClique *> *>::iterator |
| miter = needRecCount.begin(), |
| mend = needRecCount.end(); |
| for ( ; miter != mend; ++miter) { |
| Inst *invalidatingInst = (*miter).first; |
| StlVectorSet<SyncClique *> *cliques = (*miter).second; |
| assert(cliques); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Considering increccount for instruction: "; |
| invalidatingInst->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| |
| doneCliques.clear(); |
| |
| StlVectorSet<SyncClique *>::iterator |
| cliter = cliques->begin(), |
| clend = cliques->end(); |
| for ( ; cliter != clend; ++cliter) { |
| SyncClique *thisClique = *cliter; |
| thisClique = thisClique->find(); |
| |
| if ((thisClique != bottomCliqueRoot) && |
| !doneCliques.has(thisClique)) { |
| doneCliques.insert(thisClique); |
| |
| Opnd *obj = thisClique->opnd; |
| assert(obj); |
| |
| // insert incrreccount |
| VarOpnd *oldValueVar = getOldValueOpnd(thisClique); |
| Opnd *oldValueTmp = opndManager.createSsaTmpOpnd(lockType); |
| Inst *ldVarOldValue = instFactory.makeLdVar(oldValueTmp, |
| oldValueVar); |
| Inst *increcInst = instFactory.makeIncRecCount(obj, oldValueTmp); |
| |
| ldVarOldValue->insertBefore(invalidatingInst); |
| increcInst->insertAfter(ldVarOldValue); |
| } |
| } |
| } |
| } |
| } |
| |
| void SyncOpt::insertUnwindMonitorExit(Opnd *syncMethodOpnd, |
| Node *&tmpDispatchNode, Node *&tmpCatchNode, |
| Node *&tmpRethrowNode) |
| { |
| assert(flags.optimistic); |
| assert(syncMethodOpnd); |
| InstFactory &instFactory = irManager.getInstFactory(); |
| OpndManager &opndManager = irManager.getOpndManager(); |
| TypeManager &typeManager = irManager.getTypeManager(); |
| ControlFlowGraph &fg = irManager.getFlowGraph(); |
| Node *unwind = fg.getUnwindNode(); |
| assert(unwind); // use it if we have an unwind node only |
| |
| Node *newDispatchNode = fg.createDispatchNode(instFactory.makeLabel()); |
| |
| Opnd* ex = opndManager.createSsaTmpOpnd(typeManager.getSystemObjectType()); |
| Node *newCatchNode = fg.createBlockNode(instFactory.makeCatchLabel(0, ex->getType())); |
| newCatchNode->appendInst(instFactory.makeCatch(ex)); |
| bool insertedMethodExit = false; |
| |
| Node *rethrowNode = fg.createBlockNode(instFactory.makeLabel()); |
| rethrowNode->appendInst(instFactory.makeThrow(Throw_NoModifier, ex)); |
| |
| // Redirect exception exits that aren't from a node whose successor's successor |
| // is return, to newDispatchNode |
| const Edges& unwindEdges = unwind->getInEdges(); |
| Edges::const_iterator eiter; |
| for(eiter = unwindEdges.begin(); eiter != unwindEdges.end(); ) { |
| bool redirectEdge = true; |
| Edge* edge = *eiter; |
| ++eiter; |
| Node *source = edge->getSourceNode(); |
| |
| // check whether source is a return-path monitorExit(this) |
| Inst *sourceLastInst = (Inst*)source->getLastInst(); |
| if (((sourceLastInst->getOpcode() == Op_TauMonitorExit) || |
| (sourceLastInst->getOpcode() == Op_OptimisticBalancedMonitorExit)) && |
| (sourceLastInst->getSrc(0) == syncMethodOpnd)) { |
| // is a monitorExit(this) |
| |
| if (!insertedMethodExit) { |
| insertedMethodExit = true; |
| if (sourceLastInst->getOpcode() == Op_TauMonitorExit) { |
| Opnd *tauSrcNonNull = sourceLastInst->getSrc(1); |
| assert(tauSrcNonNull->getType()->tag == Type::Tau); |
| newCatchNode->appendInst(instFactory.makeTauMonitorExit(syncMethodOpnd, tauSrcNonNull)); |
| } else { |
| Opnd *lockAddrOpnd = sourceLastInst->getSrc(1); |
| Opnd *oldValueOpnd = sourceLastInst->getSrc(1); |
| newCatchNode->appendInst(instFactory.makeOptimisticBalancedMonitorExit(syncMethodOpnd, |
| lockAddrOpnd, |
| oldValueOpnd)); |
| } |
| } |
| |
| // now check whether other successor is a return node |
| const Edges& sourceEdges = source->getOutEdges(); |
| Edges::const_iterator |
| sourceEdgesIter = sourceEdges.begin(), |
| sourceEdgesEnd = sourceEdges.end(); |
| for(; sourceEdgesIter != sourceEdgesEnd; ++sourceEdgesIter) { |
| Edge *sourceEdge = *sourceEdgesIter; |
| Node *target = sourceEdge->getTargetNode(); |
| if (target == unwind) continue; |
| |
| // check if it ends in return |
| Inst *targetLastInst = (Inst*)target->getLastInst(); |
| if (targetLastInst->getOpcode() == Op_Return) { |
| // do not redirect |
| redirectEdge = false; |
| break; |
| } |
| } |
| |
| } |
| // otherwise, redirect the edge. |
| if (redirectEdge) |
| fg.replaceEdgeTarget(edge, newDispatchNode); |
| } |
| if (!insertedMethodExit) { |
| |
| } |
| |
| fg.addEdge(newDispatchNode, newCatchNode); |
| fg.addEdge(newCatchNode, rethrowNode); |
| fg.addEdge(newCatchNode, unwind); |
| fg.addEdge(rethrowNode, unwind); |
| |
| tmpDispatchNode = newDispatchNode; |
| tmpCatchNode = newCatchNode; |
| tmpRethrowNode = rethrowNode; |
| } |
| |
| void SyncOpt::removeUnwindMonitorExit(Opnd *syncMethodOpnd, |
| Node *tmpDispatchNode, Node *tmpCatchNode, |
| Node *tmpRethrowNode) |
| { |
| assert(flags.optimistic); |
| assert(syncMethodOpnd); |
| ControlFlowGraph &fg = irManager.getFlowGraph(); |
| Node *unwind = fg.getUnwindNode(); |
| |
| const Edges& tmpDispatchInEdges = tmpDispatchNode->getInEdges(); |
| Edges::const_iterator eiter; |
| for(eiter = tmpDispatchInEdges.begin(); eiter != tmpDispatchInEdges.end(); ) { |
| Edge* edge = *eiter; |
| ++eiter; |
| fg.replaceEdgeTarget(edge, unwind); |
| } |
| |
| fg.removeEdge(tmpDispatchNode, tmpCatchNode); |
| fg.removeEdge(tmpCatchNode, tmpRethrowNode); |
| fg.removeEdge(tmpCatchNode, unwind); |
| fg.removeEdge(tmpRethrowNode, unwind); |
| fg.removeNode(tmpDispatchNode); |
| fg.removeNode(tmpCatchNode); |
| fg.removeNode(tmpRethrowNode); |
| } |
| |
| |
| |
| |
| DEFINE_SESSION_ACTION(SO2, so2, "Nested synchronizations removal") |
| |
| class SyncOpt2 { |
| public: |
| SyncOpt2(IRManager& irm) |
| : irManager(irm) {}; |
| void runPass(); |
| void eliminateClosestMonExits(Node* enterNode, Opnd* monObject, int& nExits, BitSet& monexits); |
| private: |
| IRManager& irManager; |
| }; |
| |
| void SO2::_run(IRManager& irm) { |
| SyncOpt2 opt(irm); |
| opt.runPass(); |
| } |
| |
| void SyncOpt2::runPass() { |
| MemoryManager tmpMM("SO2MM"); |
| ControlFlowGraph& flowGraph = irManager.getFlowGraph(); |
| OptPass::computeDominators(irManager); |
| DominatorTree* domTree = flowGraph.getDominatorTree(); |
| StlVector<Inst*> monenters(tmpMM); |
| const Nodes& nodes = flowGraph.getNodesPostOrder(); |
| |
| for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) { |
| Node* node = *it; |
| for (Inst* inst = (Inst*)node->getFirstInst(); inst!=NULL; inst = inst->getNextInst()) { |
| if (inst->getOpcode()== Op_TauMonitorEnter) { |
| monenters.push_back(inst); |
| for (size_t i = 0; i<monenters.size()-1; i++) { |
| Inst* child = monenters[i]; |
| if (child->getNode()==NULL) { |
| continue; |
| } |
| Opnd* monObject = child->getSrc(0); |
| if ((monObject == inst->getSrc(0)) && domTree->dominates(inst->getNode(), child->getNode())) { |
| // Find a proper child to clean |
| int nExits = 0; |
| Node* enterNode = child->getNode(); |
| BitSet monexits(tmpMM,flowGraph.getMaxNodeId()); |
| |
| eliminateClosestMonExits(enterNode, monObject, nExits, monexits); |
| |
| assert(nExits > 0); |
| child->unlink(); |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| void SyncOpt2::eliminateClosestMonExits(Node* enterNode, Opnd* monObject, int& nExits, BitSet& monexits) { |
| ControlFlowGraph& flowGraph = irManager.getFlowGraph(); |
| const Edges& outEdges = enterNode->getOutEdges(); |
| Edges::const_iterator eit; |
| Node* exitNode; |
| for (eit = outEdges.begin(); eit != outEdges.end(); ++eit) { |
| exitNode = (*eit)->getTargetNode(); |
| assert(exitNode != flowGraph.getExitNode()); |
| if (monexits.getBit(exitNode->getId())) { |
| continue; |
| } |
| Inst* exit = (Inst*)exitNode->getLastInst(); |
| if ((exit->getOpcode() == Op_TauMonitorExit) && (exit->getSrc(0) == monObject)) { |
| Edge* excEdge = exitNode->getExceptionEdge(); |
| flowGraph.removeEdge(excEdge); |
| exit->unlink(); |
| nExits++; |
| monexits.setBit(exitNode->getId()); |
| } else { |
| eliminateClosestMonExits(exitNode, monObject, nExits, monexits); |
| } |
| } |
| } |
| |
| } //namespace Jitrino |