harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mfur...@apache.org
Subject svn commit: r637935 - /harmony/enhanced/drlvm/trunk/vm/jitrino/src/codegenerator/ia32/Ia32BranchTrans.cpp
Date Mon, 17 Mar 2008 15:14:31 GMT
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
 }



Mime
View raw message