| /* |
| * 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 |
| * |
| */ |
| |
| /* |
| * the following file contains utilities to convert/deconvert to/from SSA form |
| * for comments on the de-converter, see the second part of this file |
| */ |
| |
| |
| |
| #include "Dominator.h" |
| #include "SSA.h" |
| #include "Inst.h" |
| #include "opndmap.h" |
| #include "walkers.h" |
| #include "Log.h" |
| #include "unionfind.h" |
| #include "BitSet.h" |
| #include "optimizer.h" |
| #include "CompilationContext.h" |
| |
| namespace Jitrino { |
| |
| DEFINE_SESSION_ACTION(FixupVarsPass, fixupvars, "Fixup SSA Vars") |
| |
| void |
| FixupVarsPass::_run(IRManager& irm) { |
| OptPass::computeDominators(irm); |
| DominatorTree* dominatorTree = irm.getDominatorTree(); |
| ControlFlowGraph& flowGraph = irm.getFlowGraph(); |
| |
| DomFrontier frontier(irm.getNestedMemoryManager(),*dominatorTree,&flowGraph); |
| SSABuilder ssaBuilder(irm.getOpndManager(),irm.getInstFactory(),frontier,&flowGraph, irm.getOptimizerFlags()); |
| bool phiInserted = ssaBuilder.fixupVars(&irm.getFlowGraph(), irm.getMethodDesc()); |
| irm.setInSsa(true); |
| if (phiInserted) |
| irm.setSsaUpdated(); |
| } |
| |
| DEFINE_SESSION_ACTION(SSAPass, ssa, "SSA Construction") |
| |
| void |
| SSAPass::_run(IRManager& irm) { |
| OptPass::computeDominators(irm); |
| DominatorTree* dominatorTree = irm.getDominatorTree(); |
| ControlFlowGraph& flowGraph = irm.getFlowGraph(); |
| |
| DomFrontier frontier(irm.getNestedMemoryManager(),*dominatorTree,&flowGraph); |
| SSABuilder ssaBuilder(irm.getOpndManager(),irm.getInstFactory(),frontier,&flowGraph, irm.getOptimizerFlags()); |
| ssaBuilder.convertSSA(irm.getMethodDesc()); |
| irm.setInSsa(true); |
| irm.setSsaUpdated(); |
| } |
| |
| DEFINE_SESSION_ACTION(DeSSAPass, dessa, "SSA Deconstruction") |
| |
| void |
| DeSSAPass::_run(IRManager& irm) { |
| SSABuilder::deconvertSSA(&irm.getFlowGraph(),irm.getOpndManager()); |
| irm.setInSsa(false); |
| } |
| |
| DEFINE_SESSION_ACTION(SplitSSAPass, splitssa, "SSA Variable Web Splitting") |
| |
| void |
| SplitSSAPass::_run(IRManager& irm) { |
| SSABuilder::splitSsaWebs(&irm.getFlowGraph(), irm.getOpndManager()); |
| } |
| |
| |
| //#define DEBUG_SSA |
| |
| class RenameStack : public SparseScopedMap<Opnd *, SsaVarOpnd *> { |
| public: |
| typedef SparseScopedMap<Opnd *, SsaVarOpnd *> BaseMap; |
| RenameStack(MemoryManager& mm, U_32 n, const OptimizerFlags& optimizerFlags) |
| : BaseMap(n, mm, |
| optimizerFlags.hash_init_factor, |
| optimizerFlags.hash_resize_factor, |
| optimizerFlags.hash_resize_to) |
| {} |
| ~RenameStack() |
| {}; |
| }; |
| |
| |
| // Checks that phi insts can start from the second or third position only |
| // and goes in a row |
| // The first instruction is usually a LabelInst. |
| // The second one is Phi (if any). But in catch blocks the second inst |
| // is a CatchInst, and phi may be shifted to the third position. |
| |
| bool SSABuilder::phiInstsOnRightPositionsInBB(Node* node) { |
| Inst* inst = (Inst*)node->getSecondInst(); |
| if(inst && !inst->isPhi()) { |
| // try the next one (third) |
| inst = inst->getNextInst(); |
| } |
| // skip all phis |
| while ( inst!=NULL && inst->isPhi() ) { |
| inst = inst->getNextInst(); |
| } |
| // 'true' only if there is no any other phis in the node |
| while ( inst!=NULL ) { |
| if(inst->isPhi()) { |
| return false; |
| } |
| inst = inst->getNextInst(); |
| } |
| return true; |
| } |
| |
| // |
| // find def sites (blocks) of var operand |
| // |
| void SSABuilder::findDefSites(DefSites& allDefSites) { |
| const Nodes& nodes = fg->getNodes(); |
| Nodes::const_iterator niter; |
| for(niter = nodes.begin(); niter != nodes.end(); ++niter) { |
| Node* node = *niter; |
| if (!node->isBlockNode()) continue; |
| |
| // go over each instruction to find var definition |
| Inst* first = (Inst*)node->getFirstInst(); |
| for (Inst* inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst()) { |
| // look for var definitions |
| if (!inst->isStVar()) |
| continue; |
| |
| assert(inst->isVarAccess()); |
| // if inst->getVar() return NULL, then inst is accessing SSAOpnd. |
| // Hence, there is no need to do SSA transformation (addVarDefSite() |
| // immediately returns. |
| allDefSites.addVarDefSite(((VarAccessInst*)inst)->getVar(),node); |
| } |
| } |
| } |
| |
| void SSABuilder::addPhiSrc(PhiInst* i, |
| SsaVarOpnd* src) { |
| assert(i->isPhi()); |
| U_32 numOpnds = i->getNumSrcOperands(); |
| for (U_32 j = 0; j < numOpnds; j++) { |
| // no duplicate SSA opnd |
| if (i->getSrc(j) == src) |
| return; |
| } |
| instFactory.appendSrc(i, src); |
| } |
| |
| // a DomWalker, to be used pre-order |
| class SsaRenameWalker { |
| MemoryManager &localMemManager; |
| SSABuilder *ssaBuilder; |
| RenameStack *rs; |
| U_32 n; |
| const StlVectorSet<VarOpnd *> *whatVars; |
| const OptimizerFlags& optimizerFlags; |
| public: |
| SsaRenameWalker(SSABuilder *builder0, |
| MemoryManager &localMM, |
| U_32 num, const OptimizerFlags& _optimizerFlags) |
| : localMemManager(localMM), |
| ssaBuilder(builder0), |
| rs(0), |
| n(num), |
| whatVars(0), |
| optimizerFlags(_optimizerFlags) |
| {}; |
| |
| void setChangedVarsSet(const StlVectorSet<VarOpnd *> *whatVars0) { |
| whatVars = whatVars0; |
| } |
| |
| void applyToDominatorNode(DominatorNode *domNode) { |
| ssaBuilder->renameNode(rs, domNode, whatVars); |
| } |
| void enterScope() { |
| if (!rs) |
| rs = new (localMemManager) |
| RenameStack(localMemManager, n, optimizerFlags); |
| rs->enter_scope(); |
| } |
| void exitScope() { |
| rs->exit_scope(); |
| }; |
| }; |
| |
| // |
| // traverse dominator tree and rename variables |
| // |
| void SSABuilder::renameNode(RenameStack *renameStack, DominatorNode* dt, |
| const StlVectorSet<VarOpnd *> *whatVars) |
| { |
| if (dt == NULL) return; |
| Node* node = dt->getNode(); |
| |
| Inst* head = (Inst*)node->getFirstInst(); |
| #ifdef DEBUG_SSA |
| std::ostream &cout = Log::out(); |
| if (Log::isEnabled()) { |
| cout << "renameNode "; FlowGraph::printLabel(cout, node); cout << std::endl; |
| } |
| #endif |
| for (Inst* i = head->getNextInst(); i != NULL; i = i->getNextInst()) { |
| if (!i->isPhi()) { |
| // replace src with ssa opnd |
| U_32 nSrcs = i->getNumSrcOperands(); |
| for (U_32 j = 0; j < nSrcs; j++) { |
| Opnd *srcj = i->getSrc(j); |
| VarOpnd *srcjVar = (srcj->isSsaVarOpnd() |
| ? srcj->asSsaVarOpnd()->getVar() |
| : srcj->asVarOpnd()); |
| if (!(srcjVar && !srcjVar->isAddrTaken())) |
| continue; |
| if (whatVars && !whatVars->has(srcjVar)) continue; |
| SsaVarOpnd* ssa = renameStack->lookup(srcjVar); |
| assert(ssa); |
| i->setSrc(j,ssa); |
| } |
| } |
| |
| // for both Phi and non-Phi |
| // we replace any non-ssa dst with a new ssa opnd |
| // and record it in the RenameStack map |
| Opnd* dst = i->getDst(); |
| VarOpnd *theVar = dst->asVarOpnd(); |
| |
| if (theVar && (!theVar->isAddrTaken()) |
| && !(whatVars && !whatVars->has(theVar))) { |
| |
| SsaVarOpnd* ssaDst = opndManager.createSsaVarOpnd((VarOpnd*)dst); |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| cout << "SSA "; ssaDst->print(cout); cout << ::std::endl; |
| } |
| #endif |
| renameStack->insert((VarOpnd*)dst, ssaDst); |
| i->setDst(ssaDst); |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| i->print(cout); cout << ::std::endl; |
| } |
| #endif |
| // record stVar inst |
| } else if (dst->isSsaVarOpnd()) { |
| SsaVarOpnd* ssaDst = dst->asSsaVarOpnd(); |
| theVar = ssaDst->getVar(); |
| if (whatVars && !whatVars->has(theVar)) |
| continue; |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| cout << "SSA "; ssaDst->print(cout); cout << ::std::endl; |
| } |
| #endif |
| renameStack->insert(ssaDst->getVar(), ssaDst); |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| i->print(cout); cout << ::std::endl; |
| } |
| #endif |
| } |
| } |
| |
| // add var sources to following phi instructions |
| const Edges& edges = node->getOutEdges(); |
| Edges::const_iterator |
| eiter = edges.begin(), |
| eend = edges.end(); |
| for(eiter = edges.begin(); eiter != eend; ++eiter) { |
| Edge* e = *eiter; |
| Node* succ = e->getTargetNode(); |
| // Phi insts are inserted to the beginning of the block |
| // if succ does not have phi insts, then we can skip it |
| Inst *phi = (Inst*)succ->getSecondInst(); |
| if (phi==NULL || !phi->isPhi()) continue; |
| |
| // node is jth predecessor for succ |
| |
| |
| // replace jth var of phi insts |
| Inst* nextphi = phi->getNextInst(); |
| for (;phi!=NULL && phi->isPhi(); phi = nextphi) { |
| nextphi = phi->getNextInst(); |
| // get var |
| Opnd *theopnd = phi->getDst(); |
| VarOpnd *thevar = theopnd->asVarOpnd(); |
| |
| if (!thevar) { |
| SsaVarOpnd *theSsaVar = theopnd->asSsaVarOpnd(); |
| assert(theSsaVar); |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "case 2" << ::std::endl; |
| } |
| #endif |
| thevar = theSsaVar->getVar(); |
| } |
| |
| if (whatVars && !whatVars->has(thevar)) continue; |
| |
| SsaVarOpnd* ssa = renameStack->lookup((VarOpnd*)thevar); |
| |
| if (ssa != NULL) { |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| cout << "redge"; |
| // cout << (I_32)j; |
| cout << " with ssa "; ssa->print(cout); cout << ::std::endl; |
| } |
| #endif |
| addPhiSrc((PhiInst*)phi,ssa); |
| } else { |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| cout << "no source for phi of var "; |
| thevar->print(cout); |
| cout << ::std::endl; |
| } |
| #endif |
| // if ssa is NULL, then the phi must be a dead phi inst |
| // (no more use of var afterwards). it will be removed. |
| } |
| } |
| } |
| } |
| |
| void SSABuilder::insertPhi(DefSites& allDefSites) { |
| HashTableIter<void,VarDefSites> tableIter(allDefSites.getVarDefSites()); |
| void* var; |
| VarDefSites* defSites; |
| while (tableIter.getNextElem(var,defSites)) { |
| VarOpnd* varOpnd = (VarOpnd*)var; |
| // |
| // skip var opnd whose address has been taken |
| // |
| if (varOpnd->isAddrTaken()) |
| continue; |
| |
| Node* node; |
| Node *returnNode = fg->getReturnNode(); |
| Node *unwindNode = fg->getUnwindNode(); |
| Node *exitNode = fg->getExitNode(); |
| |
| while ((node = defSites->removeDefSite()) != NULL) { |
| List<Node>* df = frontier.getFrontiersOf(node); |
| for (; df != NULL; df = df->getNext()) { |
| // block where phi inst is going to be inserted |
| Node* insertedLoc = df->getElem(); |
| // if phi has been inserted, then skip |
| // no need to insert phi inst in the epilog, |
| // return node, or unwind node because |
| // there is no var use in these nodes |
| |
| if (!defSites->beenInsertedPhi(insertedLoc) && |
| !((insertedLoc == unwindNode) || |
| (insertedLoc == returnNode) || |
| (insertedLoc == exitNode))) { |
| // create a new phi instruction for varOpnd |
| createPhiInst(varOpnd,insertedLoc); |
| // record phi(var) inst is created in df->getElem() block |
| defSites->insertPhiSite(insertedLoc); |
| } |
| } |
| } |
| } |
| } |
| |
| void SSABuilder::createPhiInst(VarOpnd* var, Node* insertedLoc) { |
| // create phi instruction |
| Inst* phi = instFactory.makePhi(var,0, 0); |
| // insert to the beginning of insertedLoc |
| insertedLoc->prependInst(phi); |
| createPhi = true; |
| } |
| |
| // this is the main function which returns true if a PHI node has been inserted |
| bool SSABuilder::convertSSA(MethodDesc& methodDesc) { |
| // create structure recording the blocks that define var opnds |
| MemoryManager ssaMemManager("SSABuilder::convertSSA.ssaMemManager"); |
| DefSites allDefSites(ssaMemManager,frontier.getNumNodes()); |
| |
| // find out where vars are defined |
| findDefSites(allDefSites); |
| |
| // insert phi nodes |
| insertPhi(allDefSites); |
| |
| // rename |
| SsaRenameWalker renameWalker(this, ssaMemManager, |
| optimizerFlags.hash_node_var_factor * |
| (U_32) fg->getNodes().size(), optimizerFlags); |
| |
| DomTreeWalk<true, // pre-order |
| SsaRenameWalker>(frontier.getDominator(), renameWalker, ssaMemManager); |
| |
| return createPhi; |
| } |
| |
| // a NodeWalker |
| class ClearPhiSrcsWalker { |
| SSABuilder *thePass; |
| const StlVectorSet<VarOpnd *> *whatVars; |
| public: |
| void applyToCFGNode(Node *node) { thePass->clearPhiSrcs(node, |
| whatVars); }; |
| |
| ClearPhiSrcsWalker(SSABuilder *thePass0) |
| : thePass(thePass0), |
| whatVars(0) |
| { |
| }; |
| void setChangedVarsSet(const StlVectorSet<VarOpnd *> *changedVarsSet) { |
| whatVars = changedVarsSet; |
| } |
| }; |
| |
| // a NodeWalker |
| class ClearPhiSrcsWalker2 { |
| SSABuilder *thePass; |
| const StlVectorSet<VarOpnd *> *oldVars; // vars of interest |
| StlVector<VarOpnd *> *newVars; // vars which we have changed |
| const StlVectorSet<Opnd *> *removedVars; // vars defined by removed Phis |
| StlVector<Node *> &tmpNodeList; |
| public: |
| void applyToCFGNode(Node *node) { thePass->clearPhiSrcs2(node, |
| oldVars, |
| newVars, |
| removedVars, |
| tmpNodeList); }; |
| ClearPhiSrcsWalker2(SSABuilder *thePass0, |
| const StlVectorSet<VarOpnd *> *oldVars0, |
| StlVector<VarOpnd *> *newVars0, |
| const StlVectorSet<Opnd *> *removedVars0, |
| StlVector<Node *> &tmpNodeList0) |
| : thePass(thePass0), |
| oldVars(oldVars0), newVars(newVars0), |
| removedVars(removedVars0), |
| tmpNodeList(tmpNodeList0) |
| { |
| }; |
| void setOldVars(const StlVectorSet<VarOpnd *> *vars) { |
| oldVars = vars; |
| } |
| void setNewVars(StlVector<VarOpnd *> *vars) { |
| newVars = vars; |
| } |
| void setRemovedVars(const StlVectorSet<Opnd *> *vars) { |
| removedVars = vars; |
| } |
| }; |
| |
| void SSABuilder::clearPhiSrcs(Node *node, const StlVectorSet<VarOpnd *> *whatVars) |
| { |
| Inst* phi = (Inst*)node->getSecondInst(); |
| if (whatVars) { |
| for (;phi!=NULL && phi->isPhi(); phi = phi->getNextInst()) { |
| Opnd *dstOp = phi->getDst(); |
| VarOpnd *varOpnd = dstOp->asVarOpnd(); |
| if (!varOpnd) { |
| SsaVarOpnd *ssaOpnd = dstOp->asSsaVarOpnd(); |
| assert(ssaOpnd); |
| varOpnd = ssaOpnd->getVar(); |
| } |
| if (whatVars->has(varOpnd)) { |
| PhiInst *phiInst = phi->asPhiInst(); |
| assert(phiInst); |
| phiInst->setNumSrcs(0); |
| } |
| } |
| } else { |
| for (;phi!=NULL && phi->isPhi(); phi = phi->getNextInst()) { |
| PhiInst *phiInst = phi->asPhiInst(); |
| assert(phiInst); |
| phiInst->setNumSrcs(0); |
| } |
| } |
| } |
| |
| void SSABuilder::clearPhiSrcs2(Node *node, |
| const StlVectorSet<VarOpnd *> *whatVars, |
| StlVector<VarOpnd *> *changedVars, |
| const StlVectorSet<Opnd *> *removedVars, |
| StlVector<Node *> &scratchNodeList) |
| { |
| bool needPreds = true; |
| StlVector<Node *> &preds = scratchNodeList; |
| |
| Inst* inst = (Inst*)node->getSecondInst(); |
| for (;inst!=NULL && inst->isPhi(); inst = inst->getNextInst()) { |
| Opnd *dstOp =inst->getDst(); |
| VarOpnd *varOpnd = 0; |
| if (whatVars) { |
| varOpnd = dstOp->asVarOpnd(); |
| if (!varOpnd) { |
| SsaVarOpnd *ssaOpnd = dstOp->asSsaVarOpnd(); |
| assert(ssaOpnd); |
| varOpnd = ssaOpnd->getVar(); |
| } |
| if (!whatVars->has(varOpnd)) |
| continue; |
| } |
| bool changed=false; |
| U_32 numSrcs = inst->getNumSrcOperands(); |
| for (U_32 i=0; i<numSrcs; ++i) { |
| Opnd *thisOpnd = inst->getSrc(i); |
| |
| if (!(removedVars && removedVars->has(thisOpnd))) { |
| // need to test whether need to remove |
| if (needPreds) { |
| needPreds = false; |
| |
| const Edges& edges2 = node->getInEdges(); |
| preds.clear(); |
| preds.reserve(edges2.size()); |
| Edges::const_iterator eiter2; |
| for(eiter2 = edges2.begin(); eiter2 != edges2.end(); ++eiter2){ |
| preds.push_back((*eiter2)->getSourceNode()); |
| } |
| } |
| DominatorTree &domTree = frontier.getDominator(); |
| Inst *thisOpndInst = thisOpnd->getInst(); |
| Node *thisOpndInstNode = thisOpndInst->getNode(); |
| if (thisOpndInstNode) { |
| // the operand's source instruction was not already dead. |
| StlVector<Node *>::const_iterator |
| predIter = preds.begin(), |
| predEnd = preds.end(); |
| bool foundDom = false; |
| for ( ; predIter != predEnd; ++predIter) { |
| Node *predNode = *predIter; |
| if (domTree.dominates(thisOpndInstNode, predNode)) { |
| // we found it, leave this operand alone. |
| foundDom = true; |
| break; |
| } |
| } |
| if (foundDom) continue; // leave operand alone. |
| } |
| } |
| // remove this operand; |
| if (i < numSrcs-1) { |
| inst->setSrc(i, inst->getSrc(numSrcs-1)); |
| --i; // re-examine this operand, which is now the last |
| } |
| --numSrcs; // we deleted one operand |
| PhiInst *phiInst = inst->asPhiInst(); |
| assert(phiInst); |
| phiInst->setNumSrcs(numSrcs); |
| changed = true; |
| } |
| if (changed) { |
| // note the changed var; |
| if (!varOpnd) { |
| varOpnd = dstOp->asVarOpnd(); |
| if (!varOpnd) { |
| SsaVarOpnd *ssaOpnd = dstOp->asSsaVarOpnd(); |
| assert(ssaOpnd); |
| varOpnd = ssaOpnd->getVar(); |
| } |
| } |
| changedVars->push_back(varOpnd); |
| } |
| } |
| } |
| |
| // a NodeWalker |
| class CheckForTrivialPhisWalker { |
| SSABuilder *thePass; |
| MemoryManager &localMemManager; |
| bool removedPhi; |
| bool removedPhiRecently; |
| StlVector<VarOpnd *> changedVars; |
| StlVectorSet<VarOpnd *> changedVarsSet; |
| public: |
| void applyToCFGNode(Node *node) { |
| if (thePass->checkForTrivialPhis(node, changedVars)) { |
| removedPhi = true; |
| removedPhiRecently = true; |
| } |
| }; |
| |
| CheckForTrivialPhisWalker(SSABuilder *thePass0, |
| MemoryManager &localMM) |
| : thePass(thePass0), localMemManager(localMM), |
| removedPhi(false), removedPhiRecently(false), changedVars(localMM), |
| changedVarsSet(localMM) |
| { |
| }; |
| bool foundTrivial() { return removedPhi; } |
| void resetFound() { removedPhi = false; changedVars.clear(); changedVarsSet.clear(); } |
| const StlVectorSet<VarOpnd *> *getChangedVarsSet() { |
| if (changedVars.empty()) { |
| return 0; |
| } else { |
| if (removedPhiRecently) { |
| changedVarsSet.clear(); |
| changedVarsSet.insert(changedVars.begin(), changedVars.end()); |
| removedPhiRecently = false; |
| } |
| return &changedVarsSet; |
| } |
| }; |
| }; |
| |
| bool SSABuilder::checkForTrivialPhis(Node *node, |
| StlVector<VarOpnd *> &changedVars) |
| { |
| // Check that phi insts can start from the second or third position only |
| // and goes in a row |
| assert(phiInstsOnRightPositionsInBB(node)); |
| |
| Inst* phi = (Inst*)node->getSecondInst(); |
| if(phi && !phi->isPhi()) { |
| // try the next one (third) |
| phi = phi->getNextInst(); |
| } |
| |
| bool removedPhi = false; |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "Checking node " << (int)node->getId() |
| << " for trivial phis" << ::std::endl; |
| } |
| #endif |
| Inst* nextphi = NULL; |
| for (;phi!=NULL && phi->isPhi(); phi = nextphi) { |
| nextphi = phi->getNextInst(); |
| #ifdef _DEBUG |
| PhiInst *phiInst = phi->asPhiInst(); |
| assert(phiInst); |
| #endif |
| U_32 nSrcs = phi->getNumSrcOperands(); |
| if (nSrcs <= 1) { |
| // phi must be trivial |
| #ifdef DEBUG_SSA |
| ::std::ostream &cout = Log::out(); |
| if (Log::isEnabled()) { |
| cout << "removing trivial instruction "; phi->print(cout); cout << ::std::endl; |
| } |
| #endif |
| Opnd *dstOp = phi->getDst(); |
| VarOpnd *varOp = dstOp->asVarOpnd(); |
| if (!varOp) { |
| SsaVarOpnd *ssaOp = dstOp->asSsaVarOpnd(); |
| assert(ssaOp); |
| varOp = ssaOp->getVar(); |
| } |
| changedVars.push_back(varOp); |
| removedPhi = true; |
| phi->unlink(); |
| } |
| } |
| return removedPhi; |
| } |
| |
| // a NodeWalker |
| class CheckForTrivialPhisWalker2 { |
| SSABuilder *thePass; |
| const StlVectorSet<VarOpnd *> *lookatVars; // vars to look at |
| StlVector<VarOpnd *> *changedVars; // note which vars are changed |
| StlVector<Opnd *> *removedVars; // record dst of removed Phis |
| public: |
| void applyToCFGNode(Node *node) { |
| thePass->checkForTrivialPhis2(node, lookatVars, changedVars, |
| removedVars); |
| }; |
| CheckForTrivialPhisWalker2(SSABuilder *thePass0, |
| StlVectorSet<VarOpnd *> *lookatVars0, |
| StlVector<VarOpnd *> *changedVars0, |
| StlVector<Opnd *> *removedVars0) |
| : thePass(thePass0), |
| lookatVars(lookatVars0), changedVars(changedVars0), |
| removedVars(removedVars0) |
| { |
| }; |
| void setLookatVars(const StlVectorSet<VarOpnd *> *vars) { lookatVars = vars; } |
| void setChangedVars(StlVector<VarOpnd *> *vars) { changedVars = vars; } |
| }; |
| |
| void SSABuilder::checkForTrivialPhis2(Node *node, |
| const StlVectorSet<VarOpnd *> *lookatVars, |
| StlVector<VarOpnd *> *changedVars, |
| StlVector<Opnd *> *removedVars) |
| { |
| // Check that phi insts can start from the second or third position only |
| // and goes in a row |
| assert(phiInstsOnRightPositionsInBB(node)); |
| |
| Inst* phi = (Inst*)node->getSecondInst(); |
| if(phi && !phi->isPhi()) { |
| // try the next one (third) |
| phi = phi->getNextInst(); |
| } |
| |
| Inst *nextphi = NULL; |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "Checking node " << (int)node->getId() |
| << " for trivial phis2" << ::std::endl; |
| } |
| #endif |
| for (;phi->isPhi(); phi = nextphi) { |
| nextphi = phi->getNextInst(); |
| #ifdef _DEBUG |
| PhiInst *phiInst = phi->asPhiInst(); |
| assert(phiInst); |
| #endif |
| U_32 nSrcs = phi->getNumSrcOperands(); |
| if (nSrcs <= 1) { |
| // phi must be trivial |
| #ifdef DEBUG_SSA |
| ::std::ostream &cout = Log::out(); |
| if (Log::isEnabled()) { |
| cout << "removing trivial2 instruction "; phi->print(cout); cout << ::std::endl; |
| } |
| #endif |
| Opnd *dstOp = phi->getDst(); |
| VarOpnd *varOp = dstOp->asVarOpnd(); |
| if (!varOp) { |
| SsaVarOpnd *ssaOp = dstOp->asSsaVarOpnd(); |
| assert(ssaOp); |
| varOp = ssaOp->getVar(); |
| } |
| assert(!lookatVars || (lookatVars->has(varOp))); |
| changedVars->push_back(varOp); |
| removedVars->push_back(dstOp); |
| phi->unlink(); |
| } |
| } |
| } |
| |
| bool SSABuilder::fixupSSA(MethodDesc& methodDesc, bool useBetter) { |
| // clear out all Phi args |
| MemoryManager localMM("SSABuilder::fixupSSA::memManager"); |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "Starting fixupSSA" << ::std::endl; |
| |
| FlowGraph::printDotFile(*fg, methodDesc, "midfixup-0"); |
| } |
| #endif |
| |
| if (useBetter) { |
| StlVector<VarOpnd *> newChangedVars(localMM); |
| StlVector<Opnd *> removedVars(localMM); |
| StlVector<Node *> tmpNodeList(localMM); |
| |
| // first cleanup trivial Phis to avoid mess later |
| CheckForTrivialPhisWalker2 checkTrivialWalker(this, |
| 0, |
| &newChangedVars, |
| &removedVars); |
| NodeWalk<CheckForTrivialPhisWalker2>(*fg, checkTrivialWalker); |
| |
| StlVectorSet<Opnd *> removedVarsSet(localMM); |
| removedVarsSet.insert(removedVars.begin(), removedVars.end()); |
| |
| // checks for vars which don't dominate an in-edge of the phi |
| ClearPhiSrcsWalker2 clearPhisWalker2(this, |
| 0, |
| &newChangedVars, |
| &removedVarsSet, |
| tmpNodeList); |
| NodeWalk<ClearPhiSrcsWalker2>(*fg, clearPhisWalker2); |
| if (newChangedVars.empty()) { |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "newChangedVars is empty" << ::std::endl; |
| } |
| #endif |
| return false; // nothing changed, should still be non-trivial |
| } |
| |
| // do renaming to propagate vars to Phis which had vars removed |
| SsaRenameWalker renameWalker(this, localMM, |
| optimizerFlags.hash_node_var_factor * |
| (U_32) fg->getNodes().size(), optimizerFlags); |
| |
| // oldChangedVarsSet will be the set for looking up Vars to consider |
| StlVectorSet<VarOpnd *> oldChangedVarsSet(localMM); |
| oldChangedVarsSet.insert(newChangedVars.begin(), newChangedVars.end()); |
| renameWalker.setChangedVarsSet(&oldChangedVarsSet); |
| |
| DomTreeWalk<true, // preorder |
| SsaRenameWalker>(frontier.getDominator(), renameWalker, localMM); |
| |
| // check for Phis which are now trivial, but only need to look at oldChangedVarsSet |
| newChangedVars.clear(); // note that the checkTrivialWalker updates newChangedVars |
| checkTrivialWalker.setLookatVars(&oldChangedVarsSet); |
| NodeWalk<CheckForTrivialPhisWalker2>(*fg, checkTrivialWalker); |
| |
| while (!newChangedVars.empty()) { |
| // lather, rinse, repeat |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "beginning iteration" << ::std::endl; |
| } |
| #endif |
| oldChangedVarsSet.clear(); |
| oldChangedVarsSet.insert(newChangedVars.begin(), newChangedVars.end()); |
| newChangedVars.clear(); |
| |
| // clear phis with unreaching parameters |
| clearPhisWalker2.setOldVars(&oldChangedVarsSet); |
| |
| NodeWalk<ClearPhiSrcsWalker2>(*fg, clearPhisWalker2); |
| if (newChangedVars.empty()) { |
| return true; // nothing changed, still non-trivial |
| } |
| |
| // rename just newVars |
| DomTreeWalk<true, // pre-order |
| SsaRenameWalker>(frontier.getDominator(), renameWalker, |
| localMM); |
| |
| |
| oldChangedVarsSet.clear(); |
| oldChangedVarsSet.insert(newChangedVars.begin(), newChangedVars.end()); |
| newChangedVars.clear(); |
| |
| // check oldChangedVars for trivial Phis |
| NodeWalk<CheckForTrivialPhisWalker2>(*fg, checkTrivialWalker); |
| } |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "done iteration" << ::std::endl; |
| } |
| #endif |
| } else { |
| // old algorithm |
| ClearPhiSrcsWalker clearPhisWalker(this); |
| NodeWalk<ClearPhiSrcsWalker>(*fg, clearPhisWalker); |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| FlowGraph::printDotFile(*fg, methodDesc, "midfixup-1"); |
| } |
| #endif |
| |
| SsaRenameWalker renameWalker(this, localMM, |
| optimizerFlags.hash_node_var_factor * |
| (I_32) fg->getNodes().size(), optimizerFlags); |
| DomTreeWalk<true, // pre-order |
| SsaRenameWalker>(frontier.getDominator(), renameWalker, |
| localMM); |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| FlowGraph::printDotFile(*fg, methodDesc, "midfixup-2"); |
| } |
| #endif |
| |
| CheckForTrivialPhisWalker checkTrivialWalker(this, localMM); |
| NodeWalk<CheckForTrivialPhisWalker>(*fg, checkTrivialWalker); |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "before iteration" << ::std::endl; |
| } |
| #endif |
| while (checkTrivialWalker.foundTrivial()) { |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "starting iteration" << ::std::endl; |
| } |
| #endif |
| |
| // we deleted some Phi instruction(s) |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| FlowGraph::printDotFile(*fg, methodDesc, "midfixup-3"); |
| } |
| #endif |
| // clear all other Phis for that var(s) |
| clearPhisWalker.setChangedVarsSet(checkTrivialWalker.getChangedVarsSet()); |
| NodeWalk<ClearPhiSrcsWalker>(*fg, clearPhisWalker); |
| |
| // do renaming for that var(s) |
| renameWalker.setChangedVarsSet(checkTrivialWalker.getChangedVarsSet()); |
| DomTreeWalk<true, // pre-order |
| SsaRenameWalker>(frontier.getDominator(), renameWalker, |
| localMM); |
| |
| // check again |
| checkTrivialWalker.resetFound(); |
| NodeWalk<CheckForTrivialPhisWalker>(*fg, checkTrivialWalker); |
| } |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "done iteration" << ::std::endl; |
| } |
| #endif |
| } |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| FlowGraph::printDotFile(*fg, methodDesc, "midfixup-4"); |
| |
| Log::out() << "Finished fixupSSA" << ::std::endl; |
| } |
| #endif |
| |
| return true; |
| } |
| |
| // an InstWalker, arbitrary order |
| class ScanSsaVarsWalker { |
| SSABuilder *thePass; |
| StlVectorSet<VarOpnd *> &usedOutOfSsa; |
| |
| public: |
| ScanSsaVarsWalker(SSABuilder *from, |
| StlVectorSet<VarOpnd *> &usedOutOfSsa0) |
| : thePass(from), |
| usedOutOfSsa(usedOutOfSsa0) |
| { |
| }; |
| |
| void recordOpnd(Opnd *thisOpnd) { |
| assert(thisOpnd); |
| if (thisOpnd->isSsaVarOpnd()) { |
| SsaVarOpnd *ssaOpnd = thisOpnd->asSsaVarOpnd(); |
| ssaOpnd->getVar(); |
| } else if (thisOpnd->isVarOpnd()) { |
| VarOpnd *var = thisOpnd->asVarOpnd(); |
| usedOutOfSsa.insert(var); |
| } |
| }; |
| |
| void applyToInst(Inst *inst) { |
| U_32 numSrcs = inst->getNumSrcOperands(); |
| for (U_32 i=0; i<numSrcs; ++i) { |
| Opnd *thisOpnd = inst->getSrc(i); |
| recordOpnd(thisOpnd); |
| } |
| Opnd *dstOpnd = inst->getDst(); |
| recordOpnd(dstOpnd); |
| } |
| }; |
| |
| // an InstWalker, arbitrary order |
| class DeSsaVarsWalker { |
| SSABuilder *thePass; |
| StlVectorSet<VarOpnd *> &usedOutOfSsa; |
| |
| public: |
| DeSsaVarsWalker(SSABuilder *from, |
| StlVectorSet<VarOpnd *> &usedOutOfSsa0) |
| : thePass(from), |
| usedOutOfSsa(usedOutOfSsa0) |
| { |
| }; |
| |
| VarOpnd *needToDeSsaOpnd(Opnd *thisOpnd) { |
| assert(thisOpnd); |
| if (thisOpnd->isSsaVarOpnd()) { |
| SsaVarOpnd *ssaOpnd = thisOpnd->asSsaVarOpnd(); |
| VarOpnd *var = ssaOpnd->getVar(); |
| if (usedOutOfSsa.has(var)) { |
| return var; |
| } |
| } |
| return 0; |
| }; |
| |
| void applyToInst(Inst *inst) { |
| if (inst->getOpcode() == Op_Phi) { |
| // we should just delete the whole thing. |
| Opnd *dstOpnd = inst->getDst(); |
| |
| if (dstOpnd->isSsaVarOpnd()) { |
| SsaVarOpnd *ssaOpnd = dstOpnd->asSsaVarOpnd(); |
| VarOpnd *var = ssaOpnd->getVar(); |
| if (usedOutOfSsa.has(var)) { |
| // remove instruction |
| inst->unlink(); |
| return; |
| } |
| } else if (dstOpnd->isVarOpnd()) { |
| VarOpnd *var = dstOpnd->asVarOpnd(); |
| if (usedOutOfSsa.has(var)) { |
| // remove instruction |
| inst->unlink(); |
| return; |
| } |
| } |
| } |
| U_32 numSrcs = inst->getNumSrcOperands(); |
| for (U_32 i=0; i<numSrcs; ++i) { |
| Opnd *thisOpnd = inst->getSrc(i); |
| VarOpnd *varOpnd = needToDeSsaOpnd(thisOpnd); |
| if (varOpnd) { |
| inst->setSrc(i, varOpnd); |
| } |
| } |
| Opnd *dstOpnd = inst->getDst(); |
| VarOpnd *varDstOpnd = needToDeSsaOpnd(dstOpnd); |
| if (varDstOpnd) { |
| inst->setDst(varDstOpnd); |
| } |
| } |
| }; |
| |
| |
| // check for new Vars which are not in SSA form; if there are any, fix up all occurrences of |
| // that var, put into SSA form. |
| bool SSABuilder::fixupVars(ControlFlowGraph*fg, MethodDesc& methodDesc) { |
| // clear out all Phi args |
| MemoryManager localMM("SSABuilder::fixupVars::memManager"); |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| Log::out() << "Starting fixupVars" << ::std::endl; |
| |
| FlowGraph::printDotFile(*fg, methodDesc, "midfixupvars-0"); |
| } |
| #endif |
| |
| StlVectorSet<VarOpnd *> usedOutOfSsa(localMM); |
| ScanSsaVarsWalker firstWalker(this, usedOutOfSsa); |
| typedef Inst2NodeWalker<true, ScanSsaVarsWalker> ScanSsaVarsNodeWalker; |
| ScanSsaVarsNodeWalker scanSsaVarsNodeWalker(firstWalker); |
| NodeWalk<ScanSsaVarsNodeWalker>(*fg, scanSsaVarsNodeWalker); |
| |
| // now usedOutOfSsa has vars that need to be fixed up |
| |
| if (!usedOutOfSsa.empty()) { |
| // cleanup in case there are any other uses still. |
| DeSsaVarsWalker cleanupWalker(this, usedOutOfSsa); |
| |
| typedef Inst2NodeWalker<true, DeSsaVarsWalker> DeSsaVarsNodeWalker; |
| DeSsaVarsNodeWalker cleanupNodeWalker(cleanupWalker); |
| |
| NodeWalk<DeSsaVarsNodeWalker>(*fg, cleanupNodeWalker); |
| |
| // now all vars in usedOutOfSsa are not used in SSA form, and have no Phis. |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| FlowGraph::printDotFile(*fg,methodDesc, "midfixupvars-1"); |
| } |
| #endif |
| |
| // just run the conversion pass |
| convertSSA(methodDesc); |
| } |
| |
| #ifdef DEBUG_SSA |
| if (Log::isEnabled()) { |
| FlowGraph::printDotFile(*fg, methodDesc, "midfixupvars-3"); |
| |
| Log::out() << "Finished fixupVars" << ::std::endl; |
| } |
| #endif |
| |
| return !usedOutOfSsa.empty(); |
| } |
| |
| |
| |
| /* END OF CONVERTER ********************************************************************************/ |
| |
| |
| /* the second part of this file contains the de-converter. |
| * CAUTION: the de-converter is currently very simple, assumes that the |
| * live ranges of SSA variables never overlap, which could be caused |
| * by optimizations such as copy propagation and code motion. |
| */ |
| |
| |
| void SSABuilder::deconvertSSA(ControlFlowGraph* fg,OpndManager& opndManager) { |
| const Nodes& nodes = fg->getNodes(); |
| Nodes::const_iterator niter; |
| for(niter = nodes.begin(); niter != nodes.end(); ++niter) { |
| Node* node = *niter; |
| Inst *headInst = (Inst*)node->getFirstInst(); |
| for (Inst *inst = headInst->getNextInst(); inst != NULL; ) { |
| Inst *nextInst = inst->getNextInst(); |
| if (inst->isPhi()) { |
| inst->unlink(); |
| } else { |
| for (U_32 i = 0; i < inst->getNumSrcOperands(); i++) { |
| Opnd *opnd = inst->getSrc(i); |
| if (opnd->isSsaVarOpnd()) { |
| SsaVarOpnd *ssa = (SsaVarOpnd *)opnd; |
| VarOpnd *var = ssa->getVar(); |
| inst->setSrc(i,var); |
| } else if (opnd->isVarOpnd()) { |
| } |
| } |
| Opnd *dst = inst->getDst(); |
| if (dst->isSsaVarOpnd()) { |
| SsaVarOpnd *ssa = (SsaVarOpnd *)dst; |
| inst->setDst(ssa->getVar()); |
| } |
| } |
| inst = nextInst; |
| } |
| } |
| } |
| |
| struct SsaVarClique : private UnionFind { |
| VarOpnd *var; |
| SsaVarClique(VarOpnd *var0) : var(var0) {}; |
| SsaVarClique() : var(0) {}; |
| SsaVarClique *getRoot() { |
| UnionFind *root = find(); |
| return (SsaVarClique *) root; |
| } |
| void link(SsaVarClique *other) { |
| UnionFind::link(other); |
| } |
| }; |
| |
| // rename vars to make un-overlapping live ranges of a variable into |
| // different variables. |
| void SSABuilder::splitSsaWebs(ControlFlowGraph* fg,OpndManager& opndManager) { |
| U_32 numSsaOpnds = opndManager.getNumSsaOpnds(); |
| MemoryManager localMM("SSABuilder::splitSsaWebs::memManager"); |
| SsaVarClique *cliques = new (localMM) SsaVarClique[numSsaOpnds]; |
| |
| const Nodes& nodes = fg->getNodes(); |
| Nodes::const_iterator niter; |
| for(niter = nodes.begin(); niter != nodes.end(); ++niter) { |
| Node* node = *niter; |
| Inst *headInst = (Inst*)node->getFirstInst(); |
| for (Inst *inst = headInst->getNextInst(); inst != NULL; ) { |
| Inst *nextInst = inst->getNextInst(); |
| if (inst->isPhi()) { |
| // do something |
| VarOpnd *var0 = 0; |
| SsaVarClique *clique = 0; |
| for (U_32 i = 0; i < inst->getNumSrcOperands(); i++) { |
| Opnd *opnd = inst->getSrc(i); |
| if (opnd->isSsaVarOpnd()) { |
| SsaVarOpnd *ssa = (SsaVarOpnd *)opnd; |
| U_32 id = ssa->getId(); |
| if (var0) { |
| assert(ssa->getVar()==var0); |
| cliques[id].link(clique); |
| } else { |
| var0 = ssa->getVar(); |
| clique = &cliques[id]; |
| } |
| } |
| } |
| Opnd *dst = inst->getDst(); |
| if (dst->isSsaVarOpnd()) { |
| SsaVarOpnd *ssa = (SsaVarOpnd *)dst; |
| ssa->getVar(); |
| U_32 id = ssa->getId(); |
| if (var0) { |
| assert(ssa->getVar()==var0); |
| cliques[id].link(clique); |
| } else { |
| var0 = ssa->getVar(); |
| clique = &cliques[id]; |
| } |
| } |
| } |
| inst = nextInst; |
| } |
| } |
| U_32 numvars = opndManager.getNumVarOpnds(); |
| bool *used = new (localMM) bool[numvars]; |
| for (U_32 i=0; i<numvars; i++) { |
| used[i] = false; |
| } |
| |
| for(niter = nodes.begin(); niter != nodes.end(); ++niter) { |
| Node* node = *niter; |
| Inst *headInst = (Inst*)node->getFirstInst(); |
| for (Inst *inst = headInst->getNextInst(); inst != NULL; ) { |
| Inst *nextInst = inst->getNextInst(); |
| |
| for (U_32 i = 0; i < inst->getNumSrcOperands(); i++) { |
| Opnd *opnd = inst->getSrc(i); |
| if (opnd->isSsaVarOpnd()) { |
| SsaVarOpnd *ssa = (SsaVarOpnd *)opnd; |
| VarOpnd *var = ssa->getVar(); |
| U_32 id=ssa->getId(); |
| SsaVarClique *clique = &cliques[id]; |
| clique = clique->getRoot(); |
| VarOpnd *cvar = clique->var; |
| if (cvar == 0) { |
| U_32 varId = var->getId(); |
| if (used[varId]) { |
| cvar = opndManager.createVarOpnd(var->getType(), |
| var->isPinned()); |
| } else { |
| cvar = var; |
| used[varId] = true; |
| } |
| clique->var = cvar; |
| } |
| if (cvar != var) { |
| ssa->setVar(cvar); |
| } |
| } |
| } |
| Opnd *dst = inst->getDst(); |
| if (dst->isSsaVarOpnd()) { |
| SsaVarOpnd *ssa = (SsaVarOpnd *)dst; |
| VarOpnd *var = ssa->getVar(); |
| U_32 id=ssa->getId(); |
| |
| SsaVarClique *clique = &cliques[id]; |
| clique = clique->getRoot(); |
| VarOpnd *cvar = clique->var; |
| if (cvar == 0) { |
| U_32 varId = var->getId(); |
| if (used[varId]) { |
| cvar = opndManager.createVarOpnd(var->getType(), |
| var->isPinned()); |
| } else { |
| cvar = var; |
| used[varId] = true; |
| } |
| clique->var = cvar; |
| } |
| if (cvar != var) { |
| ssa->setVar(cvar); |
| } |
| } |
| |
| inst = nextInst; |
| } |
| } |
| } |
| |
| } //namespace Jitrino |
