123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541 |
- /**************************************************************************
- * File : propLong.c
- * Purpose: propagate the value of long variables (local variables and
- * registers) along the graph. Structure the graph in this way.
- * (C) Cristina Cifuentes
- **************************************************************************/
- #include <string.h>
- #include <memory.h>
- #include <cassert>
- #include <algorithm>
- #include "dcc.h"
- static boolT isJCond (llIcode opcode)
- /* Returns whether the given icode opcode is within the range of valid
- * high-level conditional jump icodes (iJB..iJG) */
- {
- if ((opcode >= iJB) && (opcode <= iJG))
- return (TRUE);
- return (FALSE);
- }
- static boolT isLong23 (Int i, BB * pbb, ICODE * icode, Int *off, Int *arc)
- /* Returns whether the conditions for a 2-3 long variable are satisfied */
- { BB * t, * e, * obb2;
- if (pbb->nodeType != TWO_BRANCH)
- return (FALSE);
- t = pbb->edges[THEN].BBptr;
- e = pbb->edges[ELSE].BBptr;
- /* Check along the THEN path */
- if ((t->length == 1) && (t->nodeType == TWO_BRANCH) && (t->numInEdges == 1))
- {
- obb2 = t->edges[THEN].BBptr;
- if ((obb2->length == 2) && (obb2->nodeType == TWO_BRANCH) &&
- (icode[obb2->start].ic.ll.opcode == iCMP))
- {
- *off = obb2->start - i;
- *arc = THEN;
- return (TRUE);
- }
- }
- /* Check along the ELSE path */
- else if ((e->length == 1) && (e->nodeType == TWO_BRANCH) &&
- (e->numInEdges == 1))
- {
- obb2 = e->edges[THEN].BBptr;
- if ((obb2->length == 2) && (obb2->nodeType == TWO_BRANCH) &&
- (icode[obb2->start].ic.ll.opcode == iCMP))
- {
- *off = obb2->start - i;
- *arc = ELSE;
- return (TRUE);
- }
- }
- return (FALSE);
- }
- /* Returns whether the conditions for a 2-2 long variable are satisfied */
- static boolT isLong22 (ICODE * pIcode, ICODE * pEnd, Int *off)
- {
- if (((pIcode+2) < pEnd) && ((pIcode+2)->ic.ll.opcode == iCMP) &&
- (isJCond ((pIcode+1)->ic.ll.opcode)) &&
- (isJCond ((pIcode+3)->ic.ll.opcode)))
- {
- *off = 2;
- return (TRUE);
- }
- return (FALSE);
- }
- /* Creates a long conditional <=, >=, <, or > at (pIcode+1).
- * Removes excess nodes from the graph by flagging them, and updates
- * the new edges for the remaining nodes. */
- static void longJCond23 (COND_EXPR *rhs, COND_EXPR *lhs, ICODE * pIcode,
- Int *idx, Function * pProc, Int arc, Int off)
- { Int j;
- BB * pbb, * obb1, * obb2, * tbb;
- if (arc == THEN)
- {
- /* Find intermediate basic blocks and target block */
- pbb = pIcode->inBB;
- obb1 = pbb->edges[THEN].BBptr;
- obb2 = obb1->edges[THEN].BBptr;
- tbb = obb2->edges[THEN].BBptr;
- /* Modify out edge of header basic block */
- pbb->edges[THEN].BBptr = tbb;
- /* Modify in edges of target basic block */
- auto newlast=std::remove_if(tbb->inEdges.begin(),tbb->inEdges.end(),
- [obb1,obb2](BB *b) -> bool
- {
- return (b==obb1) || (b==obb2);
- }
- );
- tbb->inEdges.erase(newlast,tbb->inEdges.end());
- tbb->numInEdges--; /* looses 2 arcs, gains 1 arc */
- tbb->inEdges.push_back(pbb);
- assert(tbb->inEdges.size()==tbb->numInEdges);
- /* Modify in edges of the ELSE basic block */
- tbb = pbb->edges[ELSE].BBptr;
- auto iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb2);
- assert(iter!=tbb->inEdges.end());
- tbb->inEdges.erase(iter);
- tbb->numInEdges--; /* looses 1 arc */
- assert(tbb->inEdges.size()==tbb->numInEdges);
- /* Update icode index */
- (*idx) += 5;
- }
- else /* ELSE arc */
- {
- /* Find intermediate basic blocks and target block */
- pbb = pIcode->inBB;
- obb1 = pbb->edges[ELSE].BBptr;
- obb2 = obb1->edges[THEN].BBptr;
- tbb = obb2->edges[THEN].BBptr;
- /* Modify in edges of target basic block */
- auto iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb2);
- assert(iter!=tbb->inEdges.end());
- tbb->inEdges.erase(iter);
- tbb->numInEdges--; /* looses 1 arc */
- assert(tbb->inEdges.size()==tbb->numInEdges);
- /* Modify in edges of the ELSE basic block */
- tbb = obb2->edges[ELSE].BBptr;
- auto newlast=std::remove_if(tbb->inEdges.begin(),tbb->inEdges.end(),
- [obb1,obb2](BB *b) -> bool
- {
- return (b==obb1) || (b==obb2);
- }
- );
- tbb->inEdges.erase(newlast,tbb->inEdges.end());
- tbb->numInEdges--; /* looses 2 arcs, gains 1 arc */
- tbb->inEdges.push_back(pbb);
- assert(tbb->inEdges.size()==tbb->numInEdges);
- /* Modify out edge of header basic block */
- pbb->edges[ELSE].BBptr = tbb;
- /* Update icode index */
- (*idx) += 2;
- }
- /* Create new HLI_JCOND and condition */
- lhs = COND_EXPR::boolOp (lhs, rhs, condOpJCond[(pIcode+off+1)->ic.ll.opcode-iJB]);
- (pIcode+1)->setJCond(lhs);
- copyDU (pIcode+1, pIcode, eUSE, eUSE);
- (pIcode+1)->du.use |= (pIcode+off)->du.use;
- /* Update statistics */
- obb1->flg |= INVALID_BB;
- obb2->flg |= INVALID_BB;
- stats.numBBaft -= 2;
- pIcode->invalidate();
- pProc->Icode.GetIcode(obb1->start)->invalidate();
- pProc->Icode.GetIcode(obb2->start)->invalidate();
- pProc->Icode.GetIcode(obb2->start+1)->invalidate();
- }
- /* Creates a long conditional equality or inequality at (pIcode+1).
- * Removes excess nodes from the graph by flagging them, and updates
- * the new edges for the remaining nodes. */
- static void longJCond22 (COND_EXPR *rhs, COND_EXPR *lhs, ICODE * pIcode,
- Int *idx)
- {
- Int j;
- BB * pbb, * obb1, * tbb;
- /* Form conditional expression */
- lhs = COND_EXPR::boolOp (lhs, rhs, condOpJCond[(pIcode+3)->ic.ll.opcode - iJB]);
- (pIcode+1)->setJCond(lhs);
- copyDU (pIcode+1, pIcode, eUSE, eUSE);
- (pIcode+1)->du.use |= (pIcode+2)->du.use;
- /* Adjust outEdges[0] to the new target basic block */
- pbb = pIcode->inBB;
- if ((pbb->start + pbb->length - 1) == (*idx + 1))
- {
- /* Find intermediate and target basic blocks */
- obb1 = pbb->edges[THEN].BBptr;
- tbb = obb1->edges[THEN].BBptr;
- /* Modify THEN out edge of header basic block */
- pbb->edges[THEN].BBptr = tbb;
- /* Modify in edges of target basic block */
- auto iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb1);
- assert(iter!=tbb->inEdges.end());
- tbb->inEdges.erase(iter);
- if ((pIcode+3)->ic.ll.opcode == iJE)
- tbb->numInEdges--; /* looses 1 arc */
- else /* iJNE => replace arc */
- tbb->inEdges.push_back(pbb);
- assert(tbb->inEdges.size()==tbb->numInEdges);
- /* Modify ELSE out edge of header basic block */
- tbb = obb1->edges[ELSE].BBptr;
- pbb->edges[ELSE].BBptr = tbb;
- iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb1);
- assert(iter!=tbb->inEdges.end());
- tbb->inEdges.erase(iter);
- if ((pIcode+3)->ic.ll.opcode == iJE) /* replace */
- tbb->inEdges.push_back(pbb);
- else
- tbb->numInEdges--; /* iJNE => looses 1 arc */
- assert(tbb->inEdges.size()==tbb->numInEdges);
- /* Update statistics */
- obb1->flg |= INVALID_BB;
- stats.numBBaft--;
- }
- pIcode->invalidate();
- (pIcode+2)->invalidate();
- (pIcode+3)->invalidate();
- (*idx) += 4;
- }
- /* Propagates TYPE_LONG_(UN)SIGN icode information to the current pIcode
- * Pointer.
- * Arguments: i : index into the local identifier table
- * pLocId: ptr to the long local identifier
- * pProc : ptr to current procedure's record. */
- static void propLongStk (Int i, ID *pLocId, Function * pProc)
- {
- Int idx, off, arc;
- COND_EXPR *lhs, *rhs; /* Pointers to left and right hand expression */
- ICODE * pIcode, * pEnd;
- /* Check all icodes for offHi:offLo */
- pEnd = pProc->Icode.GetIcode(pProc->Icode.GetNumIcodes() -1);
- for (idx = 0; idx < (pProc->Icode.GetNumIcodes() - 1); idx++)
- {
- pIcode = pProc->Icode.GetIcode(idx);
- if ((pIcode->type == HIGH_LEVEL) || (pIcode->invalid == TRUE))
- continue;
- if (pIcode->ic.ll.opcode == (pIcode+1)->ic.ll.opcode)
- {
- switch (pIcode->ic.ll.opcode) {
- case iMOV:
- if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, pProc,
- &rhs, &lhs, 1) == TRUE)
- {
- pIcode->setAsgn(lhs, rhs);
- (pIcode+1)->invalidate();
- idx++;
- }
- break;
- case iAND: case iOR: case iXOR:
- if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, pProc,
- &rhs, &lhs, 1) == TRUE)
- {
- switch (pIcode->ic.ll.opcode) {
- case iAND: rhs = COND_EXPR::boolOp (lhs, rhs, AND);
- break;
- case iOR: rhs = COND_EXPR::boolOp (lhs, rhs, OR);
- break;
- case iXOR: rhs = COND_EXPR::boolOp (lhs, rhs, XOR);
- break;
- }
- pIcode->setAsgn(lhs, rhs);
- (pIcode+1)->invalidate();
- idx++;
- }
- break;
- case iPUSH:
- if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, pProc,
- &rhs, &lhs, 1) == TRUE)
- {
- pIcode->setUnary( HLI_PUSH, lhs);
- (pIcode+1)->invalidate();
- idx++;
- }
- break;
- } /*eos*/
- }
- /* Check long conditional (i.e. 2 CMPs and 3 branches */
- else if ((pIcode->ic.ll.opcode == iCMP) && (isLong23 (idx, pIcode->inBB, pProc->Icode.GetFirstIcode(),&off, &arc)))
- {
- if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, pProc, &rhs, &lhs, off) == TRUE)
- longJCond23 (rhs, lhs, pIcode, &idx, pProc, arc, off);
- }
- /* Check for long conditional equality or inequality. This requires
- * 2 CMPs and 2 branches */
- else if ((pIcode->ic.ll.opcode == iCMP) &&
- isLong22 (pIcode, pEnd, &off))
- {
- if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, pProc,
- &rhs, &lhs, off) == TRUE)
- longJCond22 (rhs, lhs, pIcode, &idx);
- }
- }
- }
- /* Finds the definition of the long register pointed to by pLocId, and
- * transforms that instruction into a HIGH_LEVEL icode instruction.
- * Arguments: i : index into the local identifier table
- * pLocId: ptr to the long local identifier
- * pProc : ptr to current procedure's record. */
- static void propLongReg (Int i, ID *pLocId, Function * pProc)
- {
- COND_EXPR *lhs, *rhs;
- Int idx, j, off, arc;
- ICODE * pIcode, * pEnd;
- ICODEMEM * pmH,* pmL; /* Pointers to dst LOW_LEVEL icodes */
- /* Process all definitions/uses of long registers at an icode position */
- pEnd = pProc->Icode.GetIcode(pProc->Icode.GetNumIcodes() -1);
- for (j = 0; j < pLocId->idx.size(); j++)
- {
- /* Check backwards for a definition of this long register */
- for (idx = pLocId->idx[j] - 1; idx > 0 ; idx--)
- {
- pIcode = pProc->Icode.GetIcode(idx-1);
- if ((pIcode->type == HIGH_LEVEL) || (pIcode->invalid == TRUE))
- continue;
- if (pIcode->ic.ll.opcode == (pIcode+1)->ic.ll.opcode)
- switch (pIcode->ic.ll.opcode)
- {
- case iMOV:
- pmH = &pIcode->ic.ll.dst;
- pmL = &(pIcode+1)->ic.ll.dst;
- if ((pLocId->id.longId.h == pmH->regi) && (pLocId->id.longId.l == pmL->regi))
- {
- lhs = COND_EXPR::idLongIdx (i);
- pProc->localId.id_arr[i].idx.push_back(idx-1);
- pIcode->setRegDU( pmL->regi, eDEF);
- rhs = COND_EXPR::idLong (&pProc->localId, SRC, pIcode, HIGH_FIRST, idx, eUSE, 1);
- pIcode->setAsgn(lhs, rhs);
- (pIcode+1)->invalidate();
- idx = 0; /* to exit the loop */
- }
- break;
- case iPOP:
- pmH = &(pIcode+1)->ic.ll.dst;
- pmL = &pIcode->ic.ll.dst;
- if ((pLocId->id.longId.h == pmH->regi) && (pLocId->id.longId.l == pmL->regi))
- {
- lhs = COND_EXPR::idLongIdx (i);
- pIcode->setRegDU( pmH->regi, eDEF);
- pIcode->setUnary(HLI_POP, lhs);
- (pIcode+1)->invalidate();
- idx = 0; /* to exit the loop */
- }
- break;
- /**** others missing ***/
- case iAND: case iOR: case iXOR:
- pmL = &pIcode->ic.ll.dst;
- pmH = &(pIcode+1)->ic.ll.dst;
- if ((pLocId->id.longId.h == pmH->regi) && (pLocId->id.longId.l == pmL->regi))
- {
- lhs = COND_EXPR::idLongIdx (i);
- pIcode->setRegDU( pmH->regi, USE_DEF);
- rhs = COND_EXPR::idLong (&pProc->localId, SRC, pIcode, LOW_FIRST, idx, eUSE, 1);
- switch (pIcode->ic.ll.opcode) {
- case iAND: rhs = COND_EXPR::boolOp (lhs, rhs, AND);
- break;
- case iOR:
- rhs = COND_EXPR::boolOp (lhs, rhs, OR);
- break;
- case iXOR: rhs = COND_EXPR::boolOp (lhs, rhs, XOR);
- break;
- } /* eos */
- pIcode->setAsgn(lhs, rhs);
- (pIcode+1)->invalidate();
- idx = 0;
- }
- break;
- } /* eos */
- }
- /* If no definition backwards, check forward for a use of this long reg */
- if (idx <= 0)
- for (idx = pLocId->idx[j] + 1; idx < pProc->Icode.GetNumIcodes() - 1; idx++)
- {
- pIcode = pProc->Icode.GetIcode(idx);
- if ((pIcode->type == HIGH_LEVEL) || (pIcode->invalid == TRUE))
- continue;
- if (pIcode->ic.ll.opcode == (pIcode+1)->ic.ll.opcode)
- switch (pIcode->ic.ll.opcode) {
- case iMOV:
- if ((pLocId->id.longId.h == pIcode->ic.ll.src.regi) &&
- (pLocId->id.longId.l == (pIcode+1)->ic.ll.src.regi))
- {
- rhs = COND_EXPR::idLongIdx (i);
- pIcode->setRegDU( (pIcode+1)->ic.ll.src.regi, eUSE);
- lhs = COND_EXPR::idLong (&pProc->localId, DST, pIcode,
- HIGH_FIRST, idx, eDEF, 1);
- pIcode->setAsgn(lhs, rhs);
- (pIcode+1)->invalidate();
- idx = pProc->Icode.GetNumIcodes(); /* to exit the loop */
- }
- break;
- case iPUSH:
- if ((pLocId->id.longId.h == pIcode->ic.ll.src.regi) &&
- (pLocId->id.longId.l == (pIcode+1)->ic.ll.src.regi))
- {
- rhs = COND_EXPR::idLongIdx (i);
- pIcode->setRegDU( (pIcode+1)->ic.ll.src.regi, eUSE);
- pIcode->setUnary(HLI_PUSH, lhs);
- (pIcode+1)->invalidate();
- }
- idx = pProc->Icode.GetNumIcodes(); /* to exit the loop */
- break;
- /*** others missing ****/
- case iAND: case iOR: case iXOR:
- pmL = &pIcode->ic.ll.dst;
- pmH = &(pIcode+1)->ic.ll.dst;
- if ((pLocId->id.longId.h == pmH->regi) &&
- (pLocId->id.longId.l == pmL->regi))
- {
- lhs = COND_EXPR::idLongIdx (i);
- pIcode->setRegDU( pmH->regi, USE_DEF);
- rhs = COND_EXPR::idLong (&pProc->localId, SRC, pIcode,
- LOW_FIRST, idx, eUSE, 1);
- switch (pIcode->ic.ll.opcode) {
- case iAND: rhs = COND_EXPR::boolOp (lhs, rhs, AND);
- break;
- case iOR: rhs = COND_EXPR::boolOp (lhs, rhs, OR);
- break;
- case iXOR: rhs = COND_EXPR::boolOp (lhs, rhs, XOR);
- break;
- }
- pIcode->setAsgn(lhs, rhs);
- (pIcode+1)->invalidate();
- idx = 0;
- }
- break;
- } /* eos */
- /* Check long conditional (i.e. 2 CMPs and 3 branches */
- else if ((pIcode->ic.ll.opcode == iCMP) &&
- (isLong23 (idx, pIcode->inBB, pProc->Icode.GetFirstIcode(),
- &off, &arc)))
- {
- if (checkLongRegEq (pLocId->id.longId, pIcode, i, idx, pProc,
- &rhs, &lhs, off) == TRUE)
- longJCond23 (rhs, lhs, pIcode, &idx, pProc, arc, off);
- }
- /* Check for long conditional equality or inequality. This requires
- * 2 CMPs and 2 branches */
- else if ((pIcode->ic.ll.opcode == iCMP) &&
- (isLong22 (pIcode, pEnd, &off)))
- {
- if (checkLongRegEq (pLocId->id.longId, pIcode, i, idx, pProc,
- &rhs, &lhs, off) == TRUE)
- longJCond22 (rhs, lhs, pIcode, &idx);
- }
- /* Check for OR regH, regL
- * JX lab
- * => HLI_JCOND (regH:regL X 0) lab
- * This is better code than HLI_JCOND (HI(regH:regL) | LO(regH:regL)) */
- else if ((pIcode->ic.ll.opcode == iOR) && ((pIcode+1) < pEnd) &&
- (isJCond ((pIcode+1)->ic.ll.opcode)))
- {
- if ((pIcode->ic.ll.dst.regi == pLocId->id.longId.h) &&
- (pIcode->ic.ll.src.regi == pLocId->id.longId.l))
- {
- lhs = COND_EXPR::idLongIdx (i);
- rhs = COND_EXPR::idKte (0, 4); /* long 0 */
- lhs = COND_EXPR::boolOp (lhs, rhs,
- condOpJCond[(pIcode+1)->ic.ll.opcode - iJB]);
- (pIcode+1)->setJCond(lhs);
- copyDU (pIcode+1, pIcode, eUSE, eUSE);
- pIcode->invalidate();
- }
- }
- } /* end for */
- } /* end for */
- }
- /* Propagates the long global address across all LOW_LEVEL icodes.
- * Transforms some LOW_LEVEL icodes into HIGH_LEVEL */
- static void propLongGlb (Int i, ID *pLocId, Function * pProc)
- {
- }
- /* Propagated identifier information, thus converting some LOW_LEVEL icodes
- * into HIGH_LEVEL icodes. */
- void Function::propLong()
- {
- Int i;
- ID *pLocId; /* Pointer to current local identifier */
- for (i = 0; i < localId.csym(); i++)
- {
- pLocId = &localId.id_arr[i];
- if ((pLocId->type==TYPE_LONG_SIGN) || (pLocId->type==TYPE_LONG_UNSIGN))
- {
- switch (pLocId->loc)
- {
- case STK_FRAME:
- propLongStk (i, pLocId, this);
- break;
- case REG_FRAME:
- propLongReg (i, pLocId, this);
- break;
- case GLB_FRAME:
- propLongGlb (i, pLocId, this);
- break;
- }
- }
- }
- }
|