You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by mf...@apache.org on 2008/03/17 16:14:31 UTC
svn commit: r637935 -
/harmony/enhanced/drlvm/trunk/vm/jitrino/src/codegenerator/ia32/Ia32BranchTrans.cpp
Author: mfursov
Date: Mon Mar 17 08:14:30 2008
New Revision: 637935
URL: http://svn.apache.org/viewvc?rev=637935&view=rev
Log:
Fix for HARMONY-5580 [drlvm][jit] Branch translator improvements
Modified:
harmony/enhanced/drlvm/trunk/vm/jitrino/src/codegenerator/ia32/Ia32BranchTrans.cpp
Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/codegenerator/ia32/Ia32BranchTrans.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/codegenerator/ia32/Ia32BranchTrans.cpp?rev=637935&r1=637934&r2=637935&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/codegenerator/ia32/Ia32BranchTrans.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/codegenerator/ia32/Ia32BranchTrans.cpp Mon Mar 17 08:14:30 2008
@@ -49,8 +49,12 @@
* The implementation of this transformer is located Ia32BranchTrans.cpp.
*/
class BranchTranslator : public SessionAction {
-
+protected:
void runImpl();
+ void removeConstCompare();
+ void eliminateSignCheck();
+ void insertCMOVs();
+
};
static ActionFactory<BranchTranslator> _btr("btr");
@@ -169,200 +173,232 @@
void
BranchTranslator::runImpl()
{
- const Nodes& nodes = irManager->getFlowGraph()->getNodesPostOrder();
irManager->calculateOpndStatistics();
- bool consts = false;
- getArg("removeConstCompare", consts);
-
+ bool consts = getBoolArg("removeConstCompare", false);
if (consts) {
- StlMap<Node *, bool> loopHeaders(irManager->getMemoryManager());
- LoopTree * lt = irManager->getFlowGraph()->getLoopTree();
- 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;
- }
+ removeConstCompare();
+ }
- for (Nodes::const_reverse_iterator it = nodes.rbegin(),end = nodes.rend();it!=end; ++it) {
- Node* bb = *it;
- if (bb->isBlockNode()){
- if(bb->isEmpty())
- continue;
+ bool signcheck = getBoolArg("eliminateSignCheck", false);
+ if (signcheck) {
+ eliminateSignCheck();
+ }
- 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;
+ bool cmovs = getBoolArg("insertCMOVs", false);
+ if (cmovs) {
+ insertCMOVs();
+ }
+
+ irManager->getFlowGraph()->purgeEmptyNodes();
+ irManager->getFlowGraph()->purgeUnreachableNodes();
+}
- Node * trueBB = bb->getTrueEdge()->getTargetNode();
- Node * falseBB = bb->getFalseEdge()->getTargetNode();
- ConditionMnemonic condMnem = ConditionMnemonic(inst->getMnemonic() - getBaseConditionMnemonic(inst->getMnemonic()));
+void BranchTranslator::removeConstCompare() {
+ MemoryManager tmpMM("Ia32BranchTransl::removeConstCompare");
+ StlMap<Node *, bool> loopHeaders(tmpMM);
+ LoopTree * lt = irManager->getFlowGraph()->getLoopTree();
- //****start check for constants comparison****
+ 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;
+ }
- Inst * cmpInst = inst->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
- inst->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<Edge *, Opnd *> defInsts(irManager->getMemoryManager());
- mapDefsPerEdge(defInsts, bb, propogatedOp1);
- for (StlMap<Edge *, Opnd *>::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 != inst && 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);
- }
- }
- }
+ 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<Edge *, Opnd *> defInsts(irManager->getMemoryManager());
+ mapDefsPerEdge(defInsts, bb, propogatedOp1);
+ for (StlMap<Edge *, Opnd *>::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
+ }
+ }
+ }
+ } 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 == (inst->getMnemonic()- getBaseConditionMnemonic(inst->getMnemonic()))) {
- defInst->unlink();
- cmpInst->unlink();
- inst->unlink();
- bb->appendInst(irManager->newBranchInst((Mnemonic)(Mnemonic_Jcc+reverseConditionMnemonic(cm)),((BranchInst*)inst)->getTrueTarget(),((BranchInst*)inst)->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))
+ 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;
}
- continue;
}
}
+ Inst::Opnds flags(defInst,Inst::OpndRole_Def|Inst::OpndRole_Implicit);
+ if (stopSearch || ((flags.begin() != flags.end()) && defInst->getOpnd(flags.begin())->getRegName() == RegName_EFLAGS)) {
+ break;
+ }
}
- //****end check for constants comparison****
+ continue;
}
}
+ //****end check for constants comparison****
}
}
+}
- bool cmovs = false;
- getArg("insertCMOVs", cmovs);
-
- if (cmovs) {
- 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;
-
- Node * trueBB = bb->getTrueEdge()->getTargetNode();
- Node * falseBB = bb->getFalseEdge()->getTargetNode();
+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
- ConditionMnemonic condMnem = ConditionMnemonic(inst->getMnemonic() - getBaseConditionMnemonic(inst->getMnemonic()));
+ 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) {
+ uint32 prevDefCount = cmpInst->getOpndCount(Inst::OpndRole_InstLevel|Inst::OpndRole_Def);
+ uint32 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 is both successors have only instruction
- 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
+ //check if trueBB is successor of falseBB
bool canBeRemoved = true;
- Node * nextBB = trueBB->getOutEdges().front()->getTargetNode();
+ Node * nextBB = trueBB;
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;
- }
+ //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;
@@ -371,46 +407,122 @@
}
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);
-
+
+ // 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
}
-
- irManager->getFlowGraph()->purgeEmptyNodes();
- irManager->getFlowGraph()->purgeUnreachableNodes();
}
+
+
+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
}