123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728 |
- /*********************************************************************
- * Description : Performs control flow analysis on the CFG
- * (C) Cristina Cifuentes
- ********************************************************************/
- #include "dcc.h"
- #include <stdio.h>
- #include <string.h>
- #if __BORLAND__
- #include <alloc.h>
- #else
- #include <malloc.h>
- #endif
- typedef struct list {
- Int nodeIdx; /* dfsLast index to the node */
- struct list *next;
- } nodeList;
- #define ancestor(a,b) ((a->dfsLastNum < b->dfsLastNum) && (a->dfsFirstNum < b->dfsFirstNum))
- /* there is a path on the DFST from a to b if the a was first visited in a
- * dfs, and a was later visited than b when doing the last visit of each
- * node. */
- static boolT isBackEdge (PBB p,PBB s)
- /* Checks if the edge (p,s) is a back edge. If node s was visited first
- * during the dfs traversal (ie. s has a smaller dfsFirst number) or s == p,
- * then it is a backedge.
- * Also incrementes the number of backedges entries to the header node. */
- {
- if (p->dfsFirstNum >= s->dfsFirstNum)
- {
- s->numBackEdges++;
- return (TRUE);
- }
- return (FALSE);
- }
- static Int commonDom (Int currImmDom, Int predImmDom, PPROC pProc)
- /* Finds the common dominator of the current immediate dominator
- * currImmDom and its predecessor's immediate dominator predImmDom */
- {
- if (currImmDom == NO_DOM)
- return (predImmDom);
- if (predImmDom == NO_DOM) /* predecessor is the root */
- return (currImmDom);
- while ((currImmDom != NO_DOM) && (predImmDom != NO_DOM) &&
- (currImmDom != predImmDom))
- {
- if (currImmDom < predImmDom)
- predImmDom = pProc->dfsLast[predImmDom]->immedDom;
- else
- currImmDom = pProc->dfsLast[currImmDom]->immedDom;
- }
- return (currImmDom);
- }
- static void findImmedDom (PPROC pProc)
- /* Finds the immediate dominator of each node in the graph pProc->cfg.
- * Adapted version of the dominators algorithm by Hecht and Ullman; finds
- * immediate dominators only.
- * Note: graph should be reducible */
- { PBB currNode;
- Int currIdx, j, predIdx;
- for (currIdx = 0; currIdx < pProc->numBBs; currIdx++)
- {
- currNode = pProc->dfsLast[currIdx];
- if (currNode->flg & INVALID_BB) /* Do not process invalid BBs */
- continue;
- for (j = 0; j < currNode->numInEdges; j++)
- {
- predIdx = currNode->inEdges[j]->dfsLastNum;
- if (predIdx < currIdx)
- currNode->immedDom = commonDom (currNode->immedDom,
- predIdx, pProc);
- }
- }
- }
- static void insertList (nodeList **l, Int n)
- /* Inserts the node n to the list l. */
- {
- nodeList *newNode;
- newNode = allocStruc(nodeList);
- memset(newNode, 0, sizeof(nodeList));
- newNode->nodeIdx = n;
- newNode->next = *l;
- *l = newNode;
- }
- static boolT inList (nodeList *l, Int n)
- /* Returns whether or not the node n (dfsLast numbering of a basic block)
- * is on the list l. */
- {
- while (l)
- if (l->nodeIdx == n)
- return (TRUE);
- else
- l = l->next;
- return (FALSE);
- }
- static void freeList (nodeList **l)
- /* Frees space allocated by the list l. */
- { nodeList *next;
- if (*l)
- {
- next = (*l)->next;
- free (*l);
- *l = next;
- }
- *l = NULL;
- }
- static boolT inInt(PBB n, queue *q)
- /* Returns whether the node n belongs to the queue list q. */
- {
- while (q)
- if (q->node == n)
- return (TRUE);
- else
- q = q->next;
- return (FALSE);
- }
- static void findEndlessFollow (PPROC pProc, nodeList *loopNodes, PBB head)
- /* Finds the follow of the endless loop headed at node head (if any).
- * The follow node is the closest node to the loop. */
- { nodeList *p;
- Int j, succ;
- head->loopFollow = MAX;
- p = loopNodes;
- while (p != NULL)
- {
- for (j = 0; j < pProc->dfsLast[p->nodeIdx]->numOutEdges; j++)
- {
- succ = pProc->dfsLast[p->nodeIdx]->edges[j].BBptr->dfsLastNum;
- if ((! inList(loopNodes, succ)) && (succ < head->loopFollow))
- head->loopFollow = succ;
- }
- p = p->next;
- }
- }
- static void findNodesInLoop(PBB latchNode,PBB head,PPROC pProc,queue *intNodes)
- /* Flags nodes that belong to the loop determined by (latchNode, head) and
- * determines the type of loop. */
- { Int i, headDfsNum, intNodeType, j;
- nodeList *loopNodes = NULL, p;
- Int immedDom, /* dfsLast index to immediate dominator */
- thenDfs, elseDfs; /* dsfLast index for THEN and ELSE nodes */
- PBB pbb;
- /* Flag nodes in loop headed by head (except header node) */
- headDfsNum = head->dfsLastNum;
- head->loopHead = headDfsNum;
- insertList (&loopNodes, headDfsNum);
- for (i = headDfsNum + 1; i < latchNode->dfsLastNum; i++)
- {
- if (pProc->dfsLast[i]->flg & INVALID_BB) /* skip invalid BBs */
- continue;
- immedDom = pProc->dfsLast[i]->immedDom;
- if (inList (loopNodes, immedDom) && inInt(pProc->dfsLast[i], intNodes))
- {
- insertList (&loopNodes, i);
- if (pProc->dfsLast[i]->loopHead == NO_NODE)/*not in other loop*/
- pProc->dfsLast[i]->loopHead = headDfsNum;
- }
- }
- latchNode->loopHead = headDfsNum;
- if (latchNode != head)
- insertList (&loopNodes, latchNode->dfsLastNum);
- /* Determine type of loop and follow node */
- intNodeType = head->nodeType;
- if (latchNode->nodeType == TWO_BRANCH)
- if ((intNodeType == TWO_BRANCH) || (latchNode == head))
- if ((latchNode == head) ||
- (inList (loopNodes, head->edges[THEN].BBptr->dfsLastNum) &&
- inList (loopNodes, head->edges[ELSE].BBptr->dfsLastNum)))
- {
- head->loopType = REPEAT_TYPE;
- if (latchNode->edges[0].BBptr == head)
- head->loopFollow = latchNode->edges[ELSE].BBptr->dfsLastNum;
- else
- head->loopFollow = latchNode->edges[THEN].BBptr->dfsLastNum;
- pProc->Icode.SetLlFlag(latchNode->start + latchNode->length - 1,
- JX_LOOP);
- }
- else
- {
- head->loopType = WHILE_TYPE;
- if (inList (loopNodes, head->edges[THEN].BBptr->dfsLastNum))
- head->loopFollow = head->edges[ELSE].BBptr->dfsLastNum;
- else
- head->loopFollow = head->edges[THEN].BBptr->dfsLastNum;
- pProc->Icode.SetLlFlag(head->start + head->length - 1, JX_LOOP);
- }
- else /* head = anything besides 2-way, latch = 2-way */
- {
- head->loopType = REPEAT_TYPE;
- if (latchNode->edges[THEN].BBptr == head)
- head->loopFollow = latchNode->edges[ELSE].BBptr->dfsLastNum;
- else
- head->loopFollow = latchNode->edges[THEN].BBptr->dfsLastNum;
- pProc->Icode.SetLlFlag(latchNode->start + latchNode->length - 1,
- JX_LOOP);
- }
- else /* latch = 1-way */
- if (latchNode->nodeType == LOOP_NODE)
- {
- head->loopType = REPEAT_TYPE;
- head->loopFollow = latchNode->edges[0].BBptr->dfsLastNum;
- }
- else if (intNodeType == TWO_BRANCH)
- {
- head->loopType = WHILE_TYPE;
- pbb = latchNode;
- thenDfs = head->edges[THEN].BBptr->dfsLastNum;
- elseDfs = head->edges[ELSE].BBptr->dfsLastNum;
- while (1)
- {
- if (pbb->dfsLastNum == thenDfs)
- {
- head->loopFollow = elseDfs;
- break;
- }
- else if (pbb->dfsLastNum == elseDfs)
- {
- head->loopFollow = thenDfs;
- break;
- }
- /* Check if couldn't find it, then it is a strangely formed
- * loop, so it is safer to consider it an endless loop */
- if (pbb->dfsLastNum <= head->dfsLastNum)
- {
- head->loopType = ENDLESS_TYPE;
- findEndlessFollow (pProc, loopNodes, head);
- break;
- }
- pbb = pProc->dfsLast[pbb->immedDom];
- }
- if (pbb->dfsLastNum > head->dfsLastNum)
- pProc->dfsLast[head->loopFollow]->loopHead = NO_NODE; /*****/
- pProc->Icode.SetLlFlag(head->start + head->length - 1, JX_LOOP);
- }
- else
- {
- head->loopType = ENDLESS_TYPE;
- findEndlessFollow (pProc, loopNodes, head);
- }
- freeList(&loopNodes);
- }
- static void findNodesInInt (queue **intNodes, Int level, interval *Ii)
- /* Recursive procedure to find nodes that belong to the interval (ie. nodes
- * from G1). */
- { queue *l;
- if (level == 1)
- for (l = Ii->nodes; l; l = l->next)
- appendQueue (intNodes, l->node);
- else
- for (l = Ii->nodes; l; l= l->next)
- findNodesInInt (intNodes, level - 1, l->node->correspInt);
- }
- static void structLoops(PPROC pProc, derSeq *derivedG)
- /* Algorithm for structuring loops */
- { interval *Ii;
- PBB intHead, /* interval header node */
- pred, /* predecessor node */
- latchNode; /* latching node (in case of loops) */
- Int i, /* counter */
- level = 0; /* derived sequence level */
- interval *initInt; /* initial interval */
- queue *intNodes; /* list of interval nodes */
- /* Structure loops */
- while (derivedG) /* for all derived sequences Gi */
- {
- level++;
- Ii = derivedG->Ii;
- while (Ii) /* for all intervals Ii of Gi */
- {
- latchNode = NULL;
- intNodes = NULL;
- /* Find interval head (original BB node in G1) and create
- * list of nodes of interval Ii. */
- initInt = Ii;
- for (i = 1; i < level; i++)
- initInt = initInt->nodes->node->correspInt;
- intHead = initInt->nodes->node;
- /* Find nodes that belong to the interval (nodes from G1) */
- findNodesInInt (&intNodes, level, Ii);
- /* Find greatest enclosing back edge (if any) */
- for (i = 0; i < intHead->numInEdges; i++)
- {
- pred = intHead->inEdges[i];
- if (inInt(pred, intNodes) && isBackEdge(pred, intHead))
- if (! latchNode)
- latchNode = pred;
- else
- {
- if (pred->dfsLastNum > latchNode->dfsLastNum)
- latchNode = pred;
- }
- }
- /* Find nodes in the loop and the type of loop */
- if (latchNode)
- {
- /* Check latching node is at the same nesting level of case
- * statements (if any) and that the node doesn't belong to
- * another loop. */
- if ((latchNode->caseHead == intHead->caseHead) &&
- (latchNode->loopHead == NO_NODE))
- {
- intHead->latchNode = latchNode->dfsLastNum;
- findNodesInLoop(latchNode, intHead, pProc, intNodes);
- latchNode->flg |= IS_LATCH_NODE;
- }
- }
- /* Next interval */
- Ii = Ii->next;
- }
- /* Next derived sequence */
- derivedG = derivedG->next;
- }
- }
- static boolT successor (Int s, Int h, PPROC pProc)
- /* Returns whether the BB indexed by s is a successor of the BB indexed by
- * h. Note that h is a case node. */
- { Int i;
- PBB header;
- header = pProc->dfsLast[h];
- for (i = 0; i < header->numOutEdges; i++)
- if (header->edges[i].BBptr->dfsLastNum == s)
- return (TRUE);
- return (FALSE);
- }
- static void tagNodesInCase (PBB pBB, nodeList **l, Int head, Int tail)
- /* Recursive procedure to tag nodes that belong to the case described by
- * the list l, head and tail (dfsLast index to first and exit node of the
- * case). */
- { Int current, /* index to current node */
- i;
- pBB->traversed = DFS_CASE;
- current = pBB->dfsLastNum;
- if ((current != tail) && (pBB->nodeType != MULTI_BRANCH) &&
- (inList (*l, pBB->immedDom)))
- {
- insertList (l, current);
- pBB->caseHead = head;
- for (i = 0; i < pBB->numOutEdges; i++)
- if (pBB->edges[i].BBptr->traversed != DFS_CASE)
- tagNodesInCase (pBB->edges[i].BBptr, l, head, tail);
- }
- }
- static void structCases(PPROC pProc)
- /* Structures case statements. This procedure is invoked only when pProc
- * has a case node. */
- { Int i, j;
- PBB caseHeader; /* case header node */
- Int exitNode = NO_NODE; /* case exit node */
- nodeList *caseNodes = NULL; /* temporary: list of nodes in case */
- /* Linear scan of the nodes in reverse dfsLast order, searching for
- * case nodes */
- for (i = pProc->numBBs - 1; i >= 0; i--)
- if (pProc->dfsLast[i]->nodeType == MULTI_BRANCH)
- {
- caseHeader = pProc->dfsLast[i];
- /* Find descendant node which has as immediate predecessor
- * the current header node, and is not a successor. */
- for (j = i + 2; j < pProc->numBBs; j++)
- {
- if ((!successor(j, i, pProc)) &&
- (pProc->dfsLast[j]->immedDom == i))
- if (exitNode == NO_NODE)
- exitNode = j;
- else if (pProc->dfsLast[exitNode]->numInEdges <
- pProc->dfsLast[j]->numInEdges)
- exitNode = j;
- }
- pProc->dfsLast[i]->caseTail = exitNode;
-
- /* Tag nodes that belong to the case by recording the
- * header field with caseHeader. */
- insertList (&caseNodes, i);
- pProc->dfsLast[i]->caseHead = i;
- for (j = 0; j < caseHeader->numOutEdges; j++)
- tagNodesInCase (caseHeader->edges[j].BBptr, &caseNodes, i,
- exitNode);
- if (exitNode != NO_NODE)
- pProc->dfsLast[exitNode]->caseHead = i;
- }
- }
- static void flagNodes (nodeList **l, Int f, PPROC pProc)
- /* Flags all nodes in the list l as having follow node f, and deletes all
- * nodes from the list. */
- { nodeList *p;
- p = *l;
- while (p)
- {
- pProc->dfsLast[p->nodeIdx]->ifFollow = f;
- p = p->next;
- free (*l);
- *l = p;
- }
- *l = NULL;
- }
- static void structIfs (PPROC pProc)
- /* Structures if statements */
- { Int curr, /* Index for linear scan of nodes */
- desc, /* Index for descendant */
- followInEdges, /* Largest # in-edges so far */
- follow; /* Possible follow node */
- nodeList *domDesc = NULL, /* List of nodes dominated by curr */
- *unresolved = NULL, /* List of unresolved if nodes */
- *l; /* Temporary list */
- PBB currNode, /* Pointer to current node */
- pbb;
- /* Linear scan of nodes in reverse dfsLast order */
- for (curr = pProc->numBBs - 1; curr >= 0; curr--)
- {
- currNode = pProc->dfsLast[curr];
- if (currNode->flg & INVALID_BB) /* Do not process invalid BBs */
- continue;
- if ((currNode->nodeType == TWO_BRANCH) &&
- (! (pProc->Icode.GetLlFlag(currNode->start + currNode->length - 1)
- & JX_LOOP)))
- {
- followInEdges = 0;
- follow = 0;
- /* Find all nodes that have this node as immediate dominator */
- for (desc = curr+1; desc < pProc->numBBs; desc++)
- {
- if (pProc->dfsLast[desc]->immedDom == curr) {
- insertList (&domDesc, desc);
- pbb = pProc->dfsLast[desc];
- if ((pbb->numInEdges - pbb->numBackEdges) >= followInEdges)
- {
- follow = desc;
- followInEdges = pbb->numInEdges - pbb->numBackEdges;
- }
- }
- }
- /* Determine follow according to number of descendants
- * immediately dominated by this node */
- if ((follow != 0) && (followInEdges > 1))
- {
- currNode->ifFollow = follow;
- if (unresolved)
- flagNodes (&unresolved, follow, pProc);
- }
- else
- insertList (&unresolved, curr);
- }
- freeList (&domDesc);
- }
- }
- void compoundCond (PPROC pproc)
- /* Checks for compound conditions of basic blocks that have only 1 high
- * level instruction. Whenever these blocks are found, they are merged
- * into one block with the appropriate condition */
- { Int i, j, k, numOutEdges;
- PBB pbb, t, e, obb, pred;
- PICODE picode, ticode;
- COND_EXPR *exp;
- TYPEADR_TYPE *edges;
- boolT change;
- change = TRUE;
- while (change)
- {
- change = FALSE;
- /* Traverse nodes in postorder, this way, the header node of a
- * compound condition is analysed first */
- for (i = 0; i < pproc->numBBs; i++)
- {
- pbb = pproc->dfsLast[i];
- if (pbb->flg & INVALID_BB)
- continue;
- if (pbb->nodeType == TWO_BRANCH)
- {
- t = pbb->edges[THEN].BBptr;
- e = pbb->edges[ELSE].BBptr;
- /* Check (X || Y) case */
- if ((t->nodeType == TWO_BRANCH) && (t->numHlIcodes == 1) &&
- (t->numInEdges == 1) && (t->edges[ELSE].BBptr == e))
- {
- obb = t->edges[THEN].BBptr;
- /* Construct compound DBL_OR expression */
- picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
- ticode = pproc->Icode.GetIcode(t->start + t->length -1);
- exp = boolCondExp (picode->ic.hl.oper.exp,
- ticode->ic.hl.oper.exp, DBL_OR);
- picode->ic.hl.oper.exp = exp;
- /* Replace in-edge to obb from t to pbb */
- for (j = 0; j < obb->numInEdges; j++)
- if (obb->inEdges[j] == t)
- {
- obb->inEdges[j] = pbb;
- break;
- }
- /* New THEN out-edge of pbb */
- pbb->edges[THEN].BBptr = obb;
- /* Remove in-edge t to e */
- for (j = 0; j < (e->numInEdges-1); j++)
- if (e->inEdges[j] == t)
- {
- memmove (&e->inEdges[j], &e->inEdges[j+1],
- (size_t)((e->numInEdges - j - 1) * sizeof(PBB)));
- break;
- }
- e->numInEdges--; /* looses 1 arc */
- t->flg |= INVALID_BB;
- if (pbb->flg & IS_LATCH_NODE)
- pproc->dfsLast[t->dfsLastNum] = pbb;
- else
- i--; /* to repeat this analysis */
- change = TRUE;
- }
- /* Check (!X && Y) case */
- else if ((t->nodeType == TWO_BRANCH) && (t->numHlIcodes == 1) &&
- (t->numInEdges == 1) && (t->edges[THEN].BBptr == e))
- {
- obb = t->edges[ELSE].BBptr;
- /* Construct compound DBL_AND expression */
- picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
- ticode = pproc->Icode.GetIcode(t->start + t->length -1);
- inverseCondOp (&picode->ic.hl.oper.exp);
- exp = boolCondExp (picode->ic.hl.oper.exp,
- ticode->ic.hl.oper.exp, DBL_AND);
- picode->ic.hl.oper.exp = exp;
- /* Replace in-edge to obb from t to pbb */
- for (j = 0; j < obb->numInEdges; j++)
- if (obb->inEdges[j] == t)
- {
- obb->inEdges[j] = pbb;
- break;
- }
- /* New THEN and ELSE out-edges of pbb */
- pbb->edges[THEN].BBptr = e;
- pbb->edges[ELSE].BBptr = obb;
-
- /* Remove in-edge t to e */
- for (j = 0; j < (e->numInEdges-1); j++)
- if (e->inEdges[j] == t)
- {
- memmove (&e->inEdges[j], &e->inEdges[j+1],
- (size_t)((e->numInEdges - j - 1) * sizeof(PBB)));
- break;
- }
- e->numInEdges--; /* looses 1 arc */
- t->flg |= INVALID_BB;
- if (pbb->flg & IS_LATCH_NODE)
- pproc->dfsLast[t->dfsLastNum] = pbb;
- else
- i--; /* to repeat this analysis */
- change = TRUE;
- }
- /* Check (X && Y) case */
- else if ((e->nodeType == TWO_BRANCH) && (e->numHlIcodes == 1) &&
- (e->numInEdges == 1) && (e->edges[THEN].BBptr == t))
- {
- obb = e->edges[ELSE].BBptr;
- /* Construct compound DBL_AND expression */
- picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
- ticode = pproc->Icode.GetIcode(t->start + t->length -1);
- exp = boolCondExp (picode->ic.hl.oper.exp,
- ticode->ic.hl.oper.exp, DBL_AND);
- picode->ic.hl.oper.exp = exp;
-
- /* Replace in-edge to obb from e to pbb */
- for (j = 0; j < obb->numInEdges; j++)
- if (obb->inEdges[j] == e)
- {
- obb->inEdges[j] = pbb;
- break;
- }
- /* New ELSE out-edge of pbb */
- pbb->edges[ELSE].BBptr = obb;
- /* Remove in-edge e to t */
- for (j = 0; j < (t->numInEdges-1); j++)
- if (t->inEdges[j] == e)
- {
- memmove (&t->inEdges[j], &t->inEdges[j+1],
- (size_t)((t->numInEdges - j - 1) * sizeof(PBB)));
- break;
- }
- t->numInEdges--; /* looses 1 arc */
- e->flg |= INVALID_BB;
- if (pbb->flg & IS_LATCH_NODE)
- pproc->dfsLast[e->dfsLastNum] = pbb;
- else
- i--; /* to repeat this analysis */
- change = TRUE;
- }
- /* Check (!X || Y) case */
- else if ((e->nodeType == TWO_BRANCH) && (e->numHlIcodes == 1) &&
- (e->numInEdges == 1) && (e->edges[ELSE].BBptr == t))
- {
- obb = e->edges[THEN].BBptr;
- /* Construct compound DBL_OR expression */
- picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
- ticode = pproc->Icode.GetIcode(t->start + t->length -1);
- inverseCondOp (&picode->ic.hl.oper.exp);
- exp = boolCondExp (picode->ic.hl.oper.exp,
- ticode->ic.hl.oper.exp, DBL_OR);
- picode->ic.hl.oper.exp = exp;
-
- /* Replace in-edge to obb from e to pbb */
- for (j = 0; j < obb->numInEdges; j++)
- if (obb->inEdges[j] == e)
- {
- obb->inEdges[j] = pbb;
- break;
- }
- /* New THEN and ELSE out-edges of pbb */
- pbb->edges[THEN].BBptr = obb;
- pbb->edges[ELSE].BBptr = t;
- /* Remove in-edge e to t */
- for (j = 0; j < (t->numInEdges-1); j++)
- if (t->inEdges[j] == e)
- {
- memmove (&t->inEdges[j], &t->inEdges[j+1],
- (size_t)((t->numInEdges - j - 1) * sizeof(PBB)));
- break;
- }
- t->numInEdges--; /* looses 1 arc */
- e->flg |= INVALID_BB;
- if (pbb->flg & IS_LATCH_NODE)
- pproc->dfsLast[e->dfsLastNum] = pbb;
- else
- i--; /* to repeat this analysis */
- change = TRUE;
- }
- }
- }
- }
- }
- void structure(PPROC pProc, derSeq *derivedG)
- /* Structuring algorithm to find the structures of the graph pProc->cfg */
- {
- /* Find immediate dominators of the graph */
- findImmedDom(pProc);
- if (pProc->hasCase)
- structCases(pProc);
- structLoops(pProc, derivedG);
- structIfs(pProc);
- }
|