/* * 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 Nikolay A. Sidelnikov */ #include "Ia32IRManager.h" namespace Jitrino { namespace Ia32 { //======================================================================================== // class BranchTranslator //======================================================================================== /** * class BranchTranslator is implementation of replacing branching for a * single loading of an operand with a conditional CMOVcc or SETcc * instruction * The algorithm takes one-pass over CFG. * * This transformer allows to reduce count of branches * * This transformer is recommended to be inserted before all optimizations * because it unites basic blocks * * The algorithm works as follows: * * 1) Finds branch instruction which performs branch to basic blocks with * only instructions MOV with the same def-operand. * * 2) If each of thus blocks has only one predecessor they and branch * instruction is replaced with conditional instruction * * The implementation of this transformer is located Ia32BranchTrans.cpp. */ class BranchTranslator : public SessionAction { protected: void runImpl(); void removeConstCompare(); void eliminateSignCheck(); void insertCMOVs(); }; static ActionFactory _btr("btr"); static Inst* findDefInstWithMove(Inst* currentInst, Opnd* opnd) { if (opnd->getDefScope() != Opnd::DefScope_Temporary) { //For variables with semi-temporary or global def scope process only moves in current block for (Inst* inst= currentInst->getPrevInst(); inst!=NULL; inst = inst->getPrevInst()) { Inst::Opnds defs(inst,Inst::OpndRole_Def|Inst::OpndRole_Explicit|Inst::OpndRole_Auxilary); if (defs.begin()!= defs.end()) { Opnd* tmpOpnd = inst->getOpnd(defs.begin()); if (tmpOpnd == opnd) { if (inst->getMnemonic()!=Mnemonic_MOV) { //op is not supporter by BTR return NULL; } return inst; } } } return NULL; //no more defs for this var/semitemporal in the block } else { Inst* inst = opnd->getDefiningInst(); if (!inst || inst->getMnemonic()!=Mnemonic_MOV) { return NULL; } return inst; } } static Opnd * getMOVsChainSource(Inst* inst, Opnd * opnd) { Inst * instUp = findDefInstWithMove(inst, opnd); Opnd * resOpnd = opnd; while(instUp!=NULL) { assert(instUp->getMnemonic() == Mnemonic_MOV); resOpnd = instUp->getOpnd(1); instUp = findDefInstWithMove(instUp, resOpnd); } return resOpnd; } static bool branchDirection (int64 v1, int64 v2, OpndSize sz,ConditionMnemonic mn) { switch (sz) { case OpndSize_8: v1 = int64(I_8(v1)); v2 = int64(I_8(v2)); break; case OpndSize_16: v1 = int64(int16(v1)); v2 = int64(int16(v2)); break; case OpndSize_32: v1 = int64(I_32(v1)); v2 = int64(I_32(v2)); break; default: break; } bool branchDirection = false; switch (mn) { case ConditionMnemonic_E: branchDirection = v1 == v2; break; case ConditionMnemonic_NE: branchDirection = v1 != v2; break; case ConditionMnemonic_G: branchDirection = v1 > v2; break; case ConditionMnemonic_GE: branchDirection = v1>= v2; break; case ConditionMnemonic_L: branchDirection = v1 < v2; break; case ConditionMnemonic_LE: branchDirection = v1 <= v2; break; case ConditionMnemonic_AE: branchDirection = (uint64)v1 >= (uint64)v2; break; case ConditionMnemonic_A: branchDirection = (uint64)v1 > (uint64)v2; break; case ConditionMnemonic_BE: branchDirection = (uint64)v1<= (uint64)v2; break; case ConditionMnemonic_B: branchDirection = (uint64)v1 < (uint64)v2; break; default: assert(0); break; } return branchDirection; } static void mapDefsPerEdge(StlMap& defsPerEdge, Node* node, Opnd* opnd) { assert(opnd->getDefScope() == Opnd::DefScope_Variable); const Edges& inEdges = node->getInEdges(); for (Edges::const_iterator ite = inEdges.begin(), ende = inEdges.end(); ite!=ende; ++ite) { Edge* edge = *ite; Node* prevNode = edge->getSourceNode(); Inst* lastInst = (Inst*)prevNode->getLastInst(); if (lastInst == NULL) { defsPerEdge[edge] = NULL; continue; } Opnd* opndDef = getMOVsChainSource(lastInst, opnd); defsPerEdge[edge] = opndDef; } } void BranchTranslator::runImpl() { irManager->calculateOpndStatistics(); bool consts = getBoolArg("removeConstCompare", false); if (consts) { removeConstCompare(); } bool signcheck = getBoolArg("eliminateSignCheck", false); if (signcheck) { eliminateSignCheck(); } bool cmovs = getBoolArg("insertCMOVs", false); if (cmovs) { insertCMOVs(); } irManager->getFlowGraph()->purgeEmptyNodes(); irManager->getFlowGraph()->purgeUnreachableNodes(); } void BranchTranslator::removeConstCompare() { MemoryManager tmpMM("Ia32BranchTransl::removeConstCompare"); StlMap loopHeaders(tmpMM); LoopTree * lt = irManager->getFlowGraph()->getLoopTree(); const Nodes& nodes = irManager->getFlowGraph()->getNodesPostOrder(); for (Nodes::const_reverse_iterator it = nodes.rbegin(),end = nodes.rend();it!=end; ++it) { Node* bb = *it; if (lt->isLoopHeader(bb)) loopHeaders[bb] = true; else loopHeaders[bb] = false; } for (Nodes::const_reverse_iterator it = nodes.rbegin(),end = nodes.rend();it!=end; ++it) { Node* bb = *it; if (!bb->isBlockNode() || bb->isEmpty() || bb->getOutDegree() == 1) { continue; } Inst * branchInst = (Inst *)bb->getLastInst(); //check is last instruction in basic block is a conditional branch instruction if (branchInst==NULL || !branchInst->hasKind(Inst::Kind_BranchInst)) { continue; } Node * trueBB = bb->getTrueEdge()->getTargetNode(); Node * falseBB = bb->getFalseEdge()->getTargetNode(); ConditionMnemonic condMnem = ConditionMnemonic(branchInst->getMnemonic() - getBaseConditionMnemonic(branchInst->getMnemonic())); //****start check for constants comparison**** Inst * cmpInst = branchInst->getPrevInst(); if (cmpInst && cmpInst->getMnemonic() == Mnemonic_CMP) { Inst::Opnds uses(cmpInst,Inst::OpndRole_Use|Inst::OpndRole_Explicit|Inst::OpndRole_Auxilary); Opnd * cmpOp1 = cmpInst->getOpnd(uses.begin()); Opnd * cmpOp2 = cmpInst->getOpnd(uses.begin()+1); Opnd * propogatedOp1 = getMOVsChainSource(cmpInst, cmpOp1); Opnd * propogatedOp2 = getMOVsChainSource(cmpInst, cmpOp2); if (propogatedOp1->isPlacedIn(OpndKind_Imm) && propogatedOp2->isPlacedIn(OpndKind_Imm)) { //If both operands are constants we can just remove the branch irManager->resolveRuntimeInfo(propogatedOp1); irManager->resolveRuntimeInfo(propogatedOp2); //remove "dead" edges if (branchDirection(propogatedOp1->getImmValue(), propogatedOp2->getImmValue(), propogatedOp1->getSize(),condMnem)) { irManager->getFlowGraph()->removeEdge(bb->getFalseEdge()); } else { irManager->getFlowGraph()->removeEdge(bb->getTrueEdge()); } //remove CMP and Jcc instructions branchInst->unlink(); cmpInst->unlink(); continue; } else if (cmpOp1->getDefScope() != Opnd::DefScope_Temporary) { //The following optimizations works correctly only if variables //propagation was done within single basic block (i.e. only for variables //with semi-temporary or global def scope). if (propogatedOp1->getDefScope() == Opnd::DefScope_Variable && cmpOp2->isPlacedIn(OpndKind_Imm) && cmpInst->getPrevInst()== NULL) { //If first operand is variable and second is const and no side effects are //done in the current basic block we still can try to make some optimizations. //All the assignments to first operands in previous block(s) are propagated //and in case if it was assigned to constant blocks are merged and conditional //jump removed with single branch. if(loopHeaders[bb]) continue; assert(cmpOp1->getDefScope() != Opnd::DefScope_Temporary); StlMap defInsts(irManager->getMemoryManager()); mapDefsPerEdge(defInsts, bb, propogatedOp1); for (StlMap::iterator eit = defInsts.begin(); eit != defInsts.end(); eit++) { Edge * edge = eit->first; Opnd * opnd = eit->second; if (opnd == NULL || !opnd->isPlacedIn(OpndKind_Imm)) { continue; //can't retarget this edge -> var is not a const } if (branchDirection(opnd->getImmValue(), cmpOp2->getImmValue(),cmpOp1->getSize(),condMnem)) { irManager->getFlowGraph()->replaceEdgeTarget(edge, trueBB, true); } else { irManager->getFlowGraph()->replaceEdgeTarget(edge, falseBB, true); } for(Inst * copy = (Inst *)bb->getFirstInst();copy!=NULL; copy=copy->getNextInst()) { if (copy != branchInst && copy !=cmpInst) { Node * sourceBB = edge->getSourceNode(); Inst * lastInst = (Inst*)sourceBB->getLastInst(); Inst * newInst = copy->getKind() == Inst::Kind_I8PseudoInst? irManager->newI8PseudoInst(Mnemonic_MOV,1,copy->getOpnd(0),copy->getOpnd(1)): irManager->newCopyPseudoInst(Mnemonic_MOV,copy->getOpnd(0),copy->getOpnd(1)); if (lastInst->getKind()== Inst::Kind_BranchInst) { //WAS: sourceBB->prependInst(newInst, lastInst); //create new block instead of prepending to branchInst //some algorithms like I8Lowerer are very sensitive to CMP/JCC pattern //and fails if any inst is inserted between CMP and JCC irManager->getFlowGraph()->spliceBlockOnEdge(edge, newInst, true); } else { sourceBB->appendInst(newInst); } } } } } else if (propogatedOp1->getDefScope() == Opnd::DefScope_SemiTemporary) { //TODO: merge DefScope_SemiTemporary & DefScope_Variable if-branches assert(cmpOp1->getDefScope() != Opnd::DefScope_Temporary); //try to reduce ObjMonitorEnter pattern Inst * defInst = cmpInst; bool stopSearch = false; //look for Mnemonic_SETcc def for cmpOp1 in the current block (it has SemiTemporary kind) while (1) { defInst = defInst->getPrevInst(); if (defInst == NULL) { break; } Inst::Opnds defs(defInst,Inst::OpndRole_Def|Inst::OpndRole_Explicit|Inst::OpndRole_Auxilary); for (Inst::Opnds::iterator ito = defs.begin(); ito != defs.end(); ito = defs.next(ito)){ Opnd * opnd = defInst->getOpnd(ito); if (opnd == cmpOp1) { Mnemonic mnem = getBaseConditionMnemonic(defInst->getMnemonic()); ConditionMnemonic cm = ConditionMnemonic(defInst->getMnemonic()-mnem); if (mnem == Mnemonic_SETcc && cmpOp2->isPlacedIn(OpndKind_Imm) && cmpOp2->getImmValue() == 0) { if(cm == condMnem) { defInst->unlink(); cmpInst->unlink(); branchInst->unlink(); bb->appendInst(irManager->newBranchInst((Mnemonic)(Mnemonic_Jcc+reverseConditionMnemonic(cm)),((BranchInst*)branchInst)->getTrueTarget(),((BranchInst*)branchInst)->getFalseTarget())); stopSearch = true; break; } } else { stopSearch = true; break; } } } Inst::Opnds flags(defInst,Inst::OpndRole_Def|Inst::OpndRole_Implicit); if (stopSearch || ((flags.begin() != flags.end()) && defInst->getOpnd(flags.begin())->getRegName() == RegName_EFLAGS)) { break; } } continue; } } //****end check for constants comparison**** } } } void BranchTranslator::eliminateSignCheck() { const Nodes& nodes = irManager->getFlowGraph()->getNodesPostOrder(); for (Nodes::const_reverse_iterator it = nodes.rbegin(),end = nodes.rend();it!=end; ++it) { Node* bb = *it; if (!bb->isBlockNode() || bb->isEmpty() || bb->getOutDegree()== 1){ continue; } Inst * brachInst = (Inst *)bb->getLastInst(); //check is last instruction in basic block is a conditional branch instruction if(brachInst == NULL || !brachInst->hasKind(Inst::Kind_BranchInst)) { continue; } //get successors of bb Edge * trueEdge = bb->getTrueEdge(); Edge * falseEdge = bb->getFalseEdge(); Node * trueBB = trueEdge->getTargetNode(); Node * falseBB = falseEdge->getTargetNode(); Inst * falseInst = (Inst *)falseBB->getFirstInst(); Inst * cmpInst = brachInst->getPrevInst(); if (cmpInst && falseInst) { U_32 prevDefCount = cmpInst->getOpndCount(Inst::OpndRole_InstLevel|Inst::OpndRole_Def); U_32 falseDefCount = falseInst->getOpndCount(Inst::OpndRole_InstLevel|Inst::OpndRole_Def); Inst * nextFalse = falseInst->getNextInst(); // check if we have following in current BB: // cmp x, 0 // jge trueBB if ( cmpInst->getMnemonic() == Mnemonic_CMP && brachInst->getMnemonic() == Mnemonic_JGE && cmpInst->getOpnd(prevDefCount+1)->isPlacedIn(OpndKind_Imm) && cmpInst->getOpnd(prevDefCount+1)->getImmValue() == 0) { // check if we have following in false BB: // w = add x, y if ( falseInst->getMnemonic() == Mnemonic_ADD && falseInst->getOpnd(falseDefCount) == cmpInst->getOpnd(prevDefCount)) { // check if that was the only instruction in false BB or there was also // mov v, w if ( falseBB->getInstCount() == 1 || (falseBB->getInstCount() == 2 && nextFalse->getMnemonic() == Mnemonic_MOV && nextFalse->getOpnd(1) == falseInst->getOpnd(0)) ) { //check if trueBB is successor of falseBB bool canBeRemoved = true; Node * nextBB = trueBB; if (falseBB->getOutEdges().front()->getTargetNode() != nextBB) canBeRemoved = false; //check if bb is the only predecessor of falseBB const Edges& fEdges = falseBB->getInEdges(); for (Edges::const_iterator edge = fEdges.begin(); edge != fEdges.end(); ++edge) { Edge * e = *edge; if (e->getSourceNode() != bb) canBeRemoved = false; } if (!canBeRemoved) continue; // eliminating branch if (nextFalse) nextFalse->unlink(); Opnd* x = cmpInst->getOpnd(prevDefCount); Opnd* tmp = irManager->newOpnd(x->getType()); // mov tmp, x bb->appendInst(irManager->newCopyPseudoInst(Mnemonic_MOV, tmp, x)); // sar tmp, 31 (spreading sign for the whole register) bb->appendInst(irManager->newInstEx(Mnemonic_SAR, 1, tmp, tmp, irManager->newImmOpnd(irManager->getTypeManager().getInt8Type(), 31))); // and tmp, y bb->appendInst(irManager->newInstEx(Mnemonic_AND, 1, tmp, tmp, falseInst->getOpnd(falseDefCount+1))); // add w, tmp bb->appendInst(irManager->newInstEx(Mnemonic_ADD, 1, falseInst->getOpnd(0), x, tmp)); if (nextFalse) bb->appendInst(nextFalse); irManager->getFlowGraph()->removeEdge(trueEdge); irManager->getFlowGraph()->removeEdge(falseEdge); irManager->getFlowGraph()->addEdge(bb, nextBB); irManager->getFlowGraph()->removeNode(falseBB); cmpInst->unlink(); brachInst->unlink(); } } }//end if BasicBlock }//end for() by Nodes } } void BranchTranslator::insertCMOVs() { const Nodes& nodes = irManager->getFlowGraph()->getNodesPostOrder(); for (Nodes::const_reverse_iterator it = nodes.rbegin(),end = nodes.rend();it!=end; ++it) { Node* bb = *it; if (bb->isBlockNode()){ if(bb->isEmpty()) continue; Inst * inst = (Inst *)bb->getLastInst(); //check is last instruction in basic block is a conditional branch instruction if(inst && inst->hasKind(Inst::Kind_BranchInst)) { //get successors of bb if(bb->getOutEdges().size() == 1) continue; Edge * trueEdge = bb->getTrueEdge(); Edge * falseEdge = bb->getFalseEdge(); Node * trueBB = trueEdge->getTargetNode(); Node * falseBB = falseEdge->getTargetNode(); ConditionMnemonic condMnem = ConditionMnemonic(inst->getMnemonic() - getBaseConditionMnemonic(inst->getMnemonic())); Inst * trueInst = (Inst *)trueBB->getFirstInst(); Inst * falseInst = (Inst *)falseBB->getFirstInst(); if(trueBB && falseInst && trueBB->getInstCount() == 1 && falseBB->getInstCount() == 1 && trueInst->getMnemonic() == Mnemonic_MOV && falseInst->getMnemonic() == Mnemonic_MOV && trueInst->getOpnd(0) == falseInst->getOpnd(0) && trueInst->getOpnd(0)->getMemOpndKind() == MemOpndKind_Null) { //check is bb is only predecessor for trueBB and falseBB bool canBeRemoved = true; Node * nextBB = trueBB->getOutEdges().front()->getTargetNode(); if (falseBB->getOutEdges().front()->getTargetNode() != nextBB) canBeRemoved = false; const Edges& tEdges = trueBB->getInEdges(); for (Edges::const_iterator edge = tEdges.begin(); edge != tEdges.end(); ++edge) { Edge * e = *edge; if (e->getSourceNode() != bb) canBeRemoved = false; } const Edges& fEdges = falseBB->getInEdges(); for (Edges::const_iterator edge = fEdges.begin(); edge != fEdges.end(); ++edge) { Edge * e = *edge; if (e->getSourceNode() != bb) canBeRemoved = false; } if (!canBeRemoved) continue; Opnd * tfOp= trueInst->getOpnd(0); Opnd * tsOp= trueInst->getOpnd(1); Opnd * fsOp= falseInst->getOpnd(1); int64 v1 = tsOp->getImmValue(); int64 v2 = fsOp->getImmValue(); if (tsOp->isPlacedIn(OpndKind_Imm) && fsOp->isPlacedIn(OpndKind_Imm) && ((v1==0 && v2==1)|| (v1==1 && v2==0))) { bb->prependInst(irManager->newCopyPseudoInst(Mnemonic_MOV, tfOp, v1?fsOp:tsOp), inst); bb->prependInst(irManager->newInstEx(Mnemonic(Mnemonic_SETcc+(v1?condMnem:reverseConditionMnemonic(condMnem))), 1, tfOp,tfOp),inst); } else { //insert loading of initial value for operand bb->prependInst(irManager->newCopyPseudoInst(Mnemonic_MOV, tfOp, fsOp), inst); if (tsOp->isPlacedIn(OpndKind_Imm)) { Opnd * tempOpnd = irManager->newOpnd(tsOp->getType()); Inst * tempInst = irManager->newCopyPseudoInst(Mnemonic_MOV, tempOpnd, tsOp); bb->prependInst(tempInst, inst); tsOp = tempOpnd; } //insert conditional CMOVcc instruction bb->prependInst(irManager->newInstEx(Mnemonic(Mnemonic_CMOVcc+condMnem), 1, tfOp,tfOp,tsOp),inst); } //link bb with successor of trueBB and falseBB irManager->getFlowGraph()->replaceEdgeTarget(bb->getFalseEdge(), nextBB, true); irManager->getFlowGraph()->removeEdge(bb->getTrueEdge()); inst->unlink(); irManager->getFlowGraph()->removeNode(falseBB); irManager->getFlowGraph()->removeNode(trueBB); } } }//end if BasicBlock }//end for() by Nodes } } //end namespace Ia32 }