123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420 |
- /********************************************************************
- * Checks for reducibility of a graph by intervals, and
- * constructs an equivalent reducible graph if one is not found.
- * (C) Cristina Cifuentes
- ********************************************************************/
- #include "dcc.h"
- #include <stdio.h>
- #ifdef __BORLAND__
- #include <alloc.h>
- #else
- #include <malloc.h> /* For free() */
- #endif
- #include <string.h>
- static Int numInt; /* Number of intervals */
- #define nonEmpty(q) (q != NULL)
- /* Returns whether the queue q is empty or not */
- #define trivialGraph(G) (G->numOutEdges == 0)
- /* Returns whether the graph is a trivial graph or not */
- static BB *firstOfQueue (queue **Q)
- /* Returns the first element in the queue Q, and removes this element
- * from the list. Q is not an empty queue. */
- { queue *elim;
- BB *first;
- elim = *Q; /* Pointer to first node */
- first = (*Q)->node; /* First element */
- *Q = (*Q)->next; /* Pointer to next node */
- free (elim); /* Free storage */
- return (first);
- }
- queue *appendQueue (queue **Q, BB *node)
- /* Appends pointer to node at the end of the queue Q if node is not present
- * in this queue. Returns the queue node just appended. */
- { queue *pq, *l;
- pq = allocStruc(queue);
- pq->node = node;
- pq->next = NULL;
- if (Q)
- if (*Q)
- {
- for (l = *Q; l->next && l->node != node; l = l->next)
- ;
- if (l->node != node)
- l->next = pq;
- }
- else /* (*Q) == NULL */
- *Q = pq;
- return (pq);
- }
- static BB *firstOfInt (interval *pI)
- /* Returns the next unprocessed node of the interval list (pointed to by
- * pI->currNode). Removes this element logically from the list, by updating
- * the currNode pointer to the next unprocessed element. */
- { queue *pq;
- pq = pI->currNode;
- if (pq == NULL)
- return (NULL);
- pI->currNode = pq->next;
- return (pq->node);
- }
- static queue *appendNodeInt (queue *pqH, BB *node, interval *pI)
- /* Appends node node to the end of the interval list I, updates currNode
- * if necessary, and removes the node from the header list H if it is
- * there. The interval header information is placed in the field
- * node->inInterval.
- * Note: nodes are added to the interval list in interval order (which
- * topsorts the dominance relation). */
- { queue *pq, /* Pointer to current node of the list */
- *prev; /* Pointer to previous node in the list */
- /* Append node if it is not already in the interval list */
- pq = appendQueue (&pI->nodes, node);
- /* Update currNode if necessary */
- if (pI->currNode == NULL)
- pI->currNode = pq;
- /* Check header list for occurrence of node, if found, remove it
- * and decrement number of out-edges from this interval. */
- if (node->beenOnH && pqH)
- {
- prev = pqH;
- for (pq = prev; pq && pq->node != node; pq = pq->next)
- prev = pq;
- if (pq == prev)
- {
- pqH = pqH->next;
- pI->numOutEdges -= (byte)pq->node->numInEdges - 1;
- }
- else if (pq)
- {
- prev->next = pq->next;
- pI->numOutEdges -= (byte)pq->node->numInEdges - 1;
- }
- }
- /* Update interval header information for this basic block */
- node->inInterval = pI;
- return (pqH);
- }
- static void findIntervals (derSeq *derivedGi)
- /* Finds the intervals of graph derivedGi->Gi and places them in the list
- * of intervals derivedGi->Ii.
- * Algorithm by M.S.Hecht. */
- { interval *pI, /* Interval being processed */
- *J; /* ^ last interval in derivedGi->Ii */
- BB *h, /* Node being processed */
- *header, /* Current interval's header node */
- *succ; /* Successor basic block */
- Int i; /* Counter */
- queue *H; /* Queue of possible header nodes */
- boolT first = TRUE; /* First pass through the loop */
- H = appendQueue (NULL, derivedGi->Gi); /* H = {first node of G} */
- derivedGi->Gi->beenOnH = TRUE;
- derivedGi->Gi->reachingInt = allocStruc(BB); /* ^ empty BB */
- memset (derivedGi->Gi->reachingInt, 0, sizeof(BB));
- /* Process header nodes list H */
- while (nonEmpty (H))
- {
- header = firstOfQueue (&H);
- pI = allocStruc(interval);
- memset (pI, 0, sizeof(interval));
- pI->numInt = (byte)numInt++;
- if (first) /* ^ to first interval */
- derivedGi->Ii = J = pI;
- H = appendNodeInt (H, header, pI); /* pI(header) = {header} */
- /* Process all nodes in the current interval list */
- while ((h = firstOfInt (pI)) != NULL)
- {
- /* Check all immediate successors of h */
- for (i = 0; i < h->numOutEdges; i++)
- {
- succ = h->edges[i].BBptr;
- succ->inEdgeCount--;
- if (succ->reachingInt == NULL) /* first visit */
- {
- succ->reachingInt = header;
- if (succ->inEdgeCount == 0)
- H = appendNodeInt (H, succ, pI);
- else if (! succ->beenOnH) /* out edge */
- {
- appendQueue (&H, succ);
- succ->beenOnH = TRUE;
- pI->numOutEdges++;
- }
- }
- else /* node has been visited before */
- if (succ->inEdgeCount == 0)
- {
- if (succ->reachingInt == header ||
- succ->inInterval == pI) /* same interval */
- {
- if (succ != header)
- H = appendNodeInt (H, succ, pI);
- }
- else /* out edge */
- pI->numOutEdges++;
- }
- else if (succ != header && succ->beenOnH)
- pI->numOutEdges++;
- }
- }
- /* Link interval I to list of intervals */
- if (! first)
- {
- J->next = pI;
- J = pI;
- }
- else /* first interval */
- first = FALSE;
- }
- }
- static void displayIntervals (interval *pI)
- /* Displays the intervals of the graph Gi. */
- { queue *nodePtr;
- while (pI)
- {
- nodePtr = pI->nodes;
- printf (" Interval #: %ld\t#OutEdges: %ld\n",
- pI->numInt, pI->numOutEdges);
- while (nodePtr)
- {
- if (nodePtr->node->correspInt == NULL) /* real BBs */
- printf (" Node: %ld\n", nodePtr->node->start);
- else /* BBs represent intervals */
- printf (" Node (corresp int): %d\n",
- nodePtr->node->correspInt->numInt);
- nodePtr = nodePtr->next;
- }
- pI = pI->next;
- }
- }
- static derSeq *newDerivedSeq()
- /* Allocates space for a new derSeq node. */
- { derSeq *pder;
- pder = allocStruc(derSeq);
- memset (pder, 0, sizeof(derSeq));
- return (pder);
- }
- static void freeQueue (queue **q)
- /* Frees the storage allocated for the queue q*/
- { queue *queuePtr;
- for (queuePtr = *q; queuePtr; queuePtr = *q)
- {
- *q = (*q)->next;
- free (queuePtr);
- }
- }
- static void freeInterval (interval **pI)
- /* Frees the storage allocated for the interval pI */
- { interval *Iptr;
- while (*pI)
- {
- freeQueue (&((*pI)->nodes));
- Iptr = *pI;
- *pI = (*pI)->next;
- free (Iptr);
- }
- }
- void freeDerivedSeq(derSeq *derivedG)
- /* Frees the storage allocated by the derived sequence structure, except
- * for the original graph cfg (derivedG->Gi). */
- { derSeq *derivedGi;
- while (derivedG)
- {
- freeInterval (&(derivedG->Ii));
- if (derivedG->Gi->nodeType == INTERVAL_NODE)
- freeCFG (derivedG->Gi);
- derivedGi = derivedG;
- derivedG = derivedG->next;
- free (derivedGi);
- }
- }
- static boolT nextOrderGraph (derSeq *derivedGi)
- /* Finds the next order graph of derivedGi->Gi according to its intervals
- * (derivedGi->Ii), and places it in derivedGi->next->Gi. */
- { interval *Ii; /* Interval being processed */
- BB *BBnode, /* New basic block of intervals */
- *curr, /* BB being checked for out edges */
- *succ, /* Successor node */
- derInt;
- queue *listIi; /* List of intervals */
- Int i, /* Index to outEdges array */
- j; /* Index to successors */
- boolT sameGraph; /* Boolean, isomorphic graphs */
- /* Process Gi's intervals */
- derivedGi->next = newDerivedSeq();
- Ii = derivedGi->Ii;
- sameGraph = TRUE;
- derInt.next = NULL;
- BBnode = &derInt;
- while (Ii) {
- i = 0;
- BBnode = newBB (BBnode, -1, -1, INTERVAL_NODE, Ii->numOutEdges, NULL);
- BBnode->correspInt = Ii;
- listIi = Ii->nodes;
- /* Check for more than 1 interval */
- if (sameGraph && listIi->next)
- sameGraph = FALSE;
- /* Find out edges */
- if (BBnode->numOutEdges > 0)
- while (listIi) {
- curr = listIi->node;
- for (j = 0; j < curr->numOutEdges; j++) {
- succ = curr->edges[j].BBptr;
- if (succ->inInterval != curr->inInterval)
- BBnode->edges[i++].intPtr = succ->inInterval;
- }
- listIi = listIi->next;
- }
- /* Next interval */
- Ii = Ii->next;
- }
- /* Convert list of pointers to intervals into a real graph.
- * Determines the number of in edges to each new BB, and places it
- * in numInEdges and inEdgeCount for later interval processing. */
- curr = derivedGi->next->Gi = derInt.next;
- while (curr) {
- for (i = 0; i < curr->numOutEdges; i++) {
- BBnode = derivedGi->next->Gi; /* BB of an interval */
- while (BBnode && curr->edges[i].intPtr != BBnode->correspInt)
- BBnode = BBnode->next;
- if (BBnode) {
- curr->edges[i].BBptr = BBnode;
- BBnode->numInEdges++;
- BBnode->inEdgeCount++;
- }
- else
- fatalError (INVALID_INT_BB);
- }
- curr = curr->next;
- }
- return (boolT)(! sameGraph);
- }
- static byte findDerivedSeq (derSeq *derivedGi)
- /* Finds the derived sequence of the graph derivedG->Gi (ie. cfg).
- * Constructs the n-th order graph and places all the intermediate graphs
- * in the derivedG list sequence. */
- { BB *Gi; /* Current derived sequence graph */
- Gi = derivedGi->Gi;
- while (! trivialGraph (Gi))
- {
- /* Find the intervals of Gi and place them in derivedGi->Ii */
- findIntervals (derivedGi);
- /* Create Gi+1 and check if it is equivalent to Gi */
- if (! nextOrderGraph (derivedGi))
- break;
- derivedGi = derivedGi->next;
- Gi = derivedGi->Gi;
- stats.nOrder++;
- }
- if (! trivialGraph (Gi))
- {
- freeDerivedSeq(derivedGi->next); /* remove Gi+1 */
- derivedGi->next = NULL;
- return FALSE;
- }
- findIntervals (derivedGi);
- return TRUE;
- }
- static void nodeSplitting (BB *G)
- /* Converts the irreducible graph G into an equivalent reducible one, by
- * means of node splitting. */
- {
- }
- void displayDerivedSeq(derSeq *derGi)
- /* Displays the derived sequence and intervals of the graph G */
- {
- Int n = 1; /* Derived sequence number */
- printf ("\nDerived Sequence Intervals\n");
- while (derGi)
- {
- printf ("\nIntervals for G%lX\n", n++);
- displayIntervals (derGi->Ii);
- derGi = derGi->next;
- }
- }
- void checkReducibility (PPROC pProc, derSeq **derivedG)
- /* Checks whether the control flow graph, cfg, is reducible or not.
- * If it is not reducible, it is converted into an equivalent reducible
- * graph by node splitting. The derived sequence of graphs built from cfg
- * are returned in the pointer *derivedG.
- */
- { byte reducible; /* Reducible graph flag */
- numInt = 1; /* reinitialize no. of intervals*/
- stats.nOrder = 1; /* nOrder(cfg) = 1 */
- *derivedG = newDerivedSeq();
- (*derivedG)->Gi = pProc->cfg;
- reducible = findDerivedSeq(*derivedG);
- if (! reducible) {
- pProc->flg |= GRAPH_IRRED;
- nodeSplitting (pProc->cfg);
- }
- }
|